Альтернативные доказательства леммы Шварца – Циппеля

28

Мне известны только два доказательства леммы Шварца – Циппеля. Первое (более распространенное) доказательство описано в записи википедии . Второе доказательство открыл Дана Мошковиц.

Есть ли другие доказательства, которые используют существенно разные идеи?

Дай Ле
источник
2
Не могли бы вы сказать что-нибудь о вашей мотивации? Ищете обобщения в разных направлениях? Может быть, геометрическое понимание?
В Вогсен
У меня нет особой мотивации. Я буду очень удивлен, что это только два возможных способа доказать эту важную лемму!
Дай Ле
Хотя я согласен с тем, что эта лемма важна, важные леммы не обязательно имеют много разных известных доказательств. Поэтому ваш разум звучит немного странно для меня.
Цуёси Ито
1
@ Tsuyushi Ito: Я согласен с вашим комментарием, что важные леммы могут не иметь много известных доказательств. Но я думаю, что имеет смысл спросить, так ли это и в случае с SZ Lemma. Поскольку SZ имеет фундаментальное значение, вполне вероятно, что он был открыт независимо многими людьми из разных контекстов. Таким образом, выучить разные доказательства иногда ИМХО довольно поучительно. Еще раз спасибо за отличные комментарии от всех!
Дай Ле

Ответы:

16

Вот еще одна идея, которая у меня была для геометрического доказательства. Он использует проективную геометрию существенным образом.

Пусть аффинная точка вне гиперповерхности . Спроецируйте гиперповерхность на гиперплоскость на бесконечности, используя качестве центра; то есть, отображаем каждое на , пересечение единственной прямой через и с гиперплоскостью на бесконечности. Все прообразы под точки на бесконечности лежат на одной прямой, и поэтому (снова сводя задачу к размерности 1) их большинство . Гиперплоскость на бесконечности имеет мощность, поэтому мы получаем знакомую верхнюю границу, S c x S p ( x ) c x p d | F m - 1 | | S | d | F m - 1 |cFmScxSp(x)cxpd|Fm1||S|d |Fm1|

Пер Вогсен
источник
Прекрасный! И просто, чтобы подчеркнуть критическую точку, линия не содержится в гиперповерхности, потому что она проходит через точку с, которая находится за пределами поверхности.
Арнаб
1
@arnab: В самом деле, вы уже высказали эту мысль в своем посте.
Per Vognsen
1
@arnab: Кстати, я надеюсь, что ясно, что я не утверждаю, что эта идея действительно «новая». Все эти доказательства имеют похожий запах. Это, вероятно, следовало ожидать.
Per Vognsen
2
@Per: Да, но по какой-то причине мне нравится ваша версия аргумента лучше, чем версия Мошковица, потому что она кажется более геометрической, и вам не нужно думать о ведущих мономах. Но я согласен, основная идея очень похожа.
Арнаб
@Per: ваш вклад уже был замечательным. Да, они не совсем новые, но мне очень нравится ваша интерпретация. Это как дать новые интерпретации классического музыкального произведения. :-)
Dai Le
18

В качестве продолжения ответа Пера Вогсена доказательство Даны Мошковиц уже предлагает действительно легкое доказательство только для чуть более слабой версии леммы Шварца-Циппеля, которая, как мне кажется, достаточна для большинства приложений.

Пусть - ненулевой многочлен степени , где - конечное поле порядка , и пусть быть точкой такой, что . Есть много различных прямых, проходящих через , так что они разделяют . Ограничение функции на каждую из этих линий является многомерным многочленом степени , который отличен от нуля, поскольку он ненулевой в и, следовательно, имеет не более нулей. Таким образом, общее количество нулей d F q x F n f ( x ) 0 ( q n - 1 ) / ( q - 1 ) x F n - { x } f d x d f d ( q n - 1 ) / ( q - 1 ) d q n - 1f:FnFdFqxFnf(x)0(qn1)/(q1)xFn{x}fd xdfсамое большее . Шварц-Циппель, для сравнения, дает более сильную верхнюю границу .d(qn1)/(q1)dqn1

Учитывая легкость этого доказательства, я уверен, что это фольклор; если нет, то должно быть :) Я был бы признателен, если бы кто-то мог предоставить ссылку.

Арнаб
источник
3
Очень хорошо! Знаете ли вы, что она делает то же самое, только с проекционной точкой на бесконечности, а не аффинной точкой? Я добавил параграф к своему первоначальному ответу, чтобы объяснить отношения подробнее.
Per Vognsen
1
Ах, это отличная интерпретация! Благодарность!
Арнаб
14

Доказательство Мошковица основано на простой геометрии, но в статье не слишком ясно об этом. Вот идея:

Степень полинома от m переменных вырезает гиперповерхность в F m . Пересечение гиперповерхности и независимой линии (т. Е. Пересечение не является всей линией) имеет не более d точек. Если вы можете найти направление, которое не зависит от гиперповерхности, вы можете расслоить F m параллельными линиями в этом направлении и считать пересечения в каждой линии. Слоение параметризовано ортогональным дополнением направления, которое является гиперплоскостью, изоморфной F m - 1 , поэтому общее число точек гиперповерхности по всей F m не превосходит d | FdmFmFmFm1Fm .d |F|m1

Это говорит о том, что другие доказательства в том же духе могут работать.

Редактировать: я хотел бы немного рассказать о том, как доказательства Арнаба связаны с доказательством Мошковица. Он берет точку вне гиперповерхности и рассматривает пучок линий через эту точку. Мошковиц рассматривает семейство параллельных линий. Это кажется другим, но это действительно одно и то же! Параллельное семейство - это пучок линий через точку на бесконечности. Алгебра Арнаба применяет дословно, если вы сначала берете гомогенизацию многочлена и ограничиваетесь гиперплоскостью на бесконечности, вставляя , что уничтожает все не ведущие члены.w=0

Изменить: см. Мой другой ответ для нового (но не полностью несвязанного) доказательства.

Per Vognsen
источник
6

Попытка 1:

Вы смотрели на лемму А.36 (стр. 529) книги Ароры / Барака ? Это почти половина страницы, и основано на индукции.

Если у вас нет доступа к книге, я могу привести доказательства здесь.


Попытка 2:

Как насчет Любопытной Истории Леммы Шварца-Циппеля ? Среди прочих, он цитирует статью ДеМилло-Липтона , датируемую 1977 годом. Несколько других статей также названы и сравнены.


Попытка 3:

Также может представлять интерес следующая тема MathOverflow: P / poly алгоритм для проверки полиномиальной идентичности .

М.С. Дусти
источник
Да, я сделал. Но это по сути то же самое, что и из Википедии.
Дай Ле
4

Лемма Шварца-Циппеля является частным случаем теоремы Ноги Алона и Золтана Фюреди, как показано в разделе 4 этой статьи: « О нулях многочлена в конечной сетке , и, следовательно, любое новое доказательство этой теоремы дает новое доказательство Шварца». -Zippel. На данный момент я знаю шесть различных доказательств, два из которых появляются в статье, а другие упоминаются там.

Теорема Алона-Фуреди гласит следующее:

FA=i=1nAiFnfF[t_]=F[t1,,tn]Af(x)0 x AminyixAгде минимум берется по всем натуральным числам с .n i = 1 y i = nyi#Aii=1nyi=i=1n#Aidegf

В этом случае, если вы предполагаете и отрабатываете минимум (который можно легко сделать, используя материал Balls in Bins, упомянутый в статье), вы получите лемму Шварца-Циппеля над полем ( домен).degf<min#Ai

Анураг
источник
Можете ли вы взглянуть на лемму 2.2 в web.stanford.edu/~rrwill/graph-cr.pdf ? Это то, что Райан Уильямс подразумевает под своим комментарием под моим ответом, и с тех пор он находится в моем списке дел, чтобы проверить, можно ли его обобщить на коммутативные кольца. Мне кажется, что вы сейчас гораздо глубже в этом, чем я, так почему бы вам не попробовать?
Томас Климпел
@ThomasKlimpel: я изменю ответ. Я написал это, когда я только начал использовать теорию CS. И да, лемма 2.2 работает над произвольными коммутативными кольцами, поскольку {0,1} ^ n всегда удовлетворяет условию (D).
Анураг,
Подмножество произвольного коммутативного кольца называется удовлетворяет условию (D) , если для всех , не является делителем нуля. Говорят, что «сетка» удовлетворяет этому условию, если все удовлетворяют им. Шварц-Циппель и другие связанные результаты работают под этим обобщением, как показано в статье. R x y S x - y A 1 × × A nR n A iSRxySxyA1××AnRnAi
Анураг,
3

Первоначальная формулировка леммы Шварца – Циппеля относится только к полям:


PF[x1,x2,,xn]d0FSFr1,r2,,rnS
Pr[P(r1,r2,,rn)=0]d|S|.

Можно переформулировать лемму так, чтобы она имела смысл для произвольных коммутативных колец:

Лемма (Йержабек).
Пусть быть ненулевой многочлен полной степени над коммутативным кольцом, . Пусть - конечное подмножество с и пусть быть выбраны случайным образом независимо друг от друга и равномерно из . Тогда d 0 R S R s , t S : ( ( u R : ( u 0 s u = t u ) ) PR[x1,x2,,xn]d0RSRs,tS:((uR:(u0su=tu))s=t) S Pr [ P ( r 1 , r 2 , , r n ) = 0 ] dr1,r2,,rnS
Pr[P(r1,r2,,rn)=0]d|S|.

Преимущество доказательства из Википедии состоит в том, что оно обобщает, чтобы показать, что переформулировка верна для произвольных коммутативных колец, что было замечено и разработано Эмилем Йержабеком здесь .

Это дает альтернативное доказательство леммы Шварца-Циппеля, доказывая переформулировку для общих коммутативных колец и получая нормальную формулировку для полей в качестве следствия.

Томас Климпел
источник
Полиномы являются свободной алгеброй для коммутативных колец, т. Е. Свободной алгеброй, порожденной сложением, аддитивными инверсиями, умножением и константами относительно аксиом коммутативных колец. Первоначальная надежда состояла в том, чтобы найти обобщение леммы Шварца-Циппеля для свободной алгебры, которая дополнительно содержит (обобщенные) мультипликативные инверсии относительно аксиом коммутативных регулярных колец . Смотрите также работу Яна А. Бергстра .
Томас Климпел
1
Zm
1
@RyanWilliams В статье « О нулях многочлена в конечной сетке», цитируемой в недавнем ответе Анурага Бишного, обобщены обе вышеприведенные лемма, теорема Алона-Фуреди и лемма 2.2 из этой статьи SODA'15 (и доказана точность оценки). , Со времени вашего комментария он был в моем списке задач, чтобы найти такое обобщение, так что, с моей точки зрения, это значительное достижение (так что можно поздравить авторов).
Томас Климпел