Комбинаторная теорема о нулях

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Комбинаторная теорема о нулях (теорема Алона, сombinatorial nullstellensatz) — алгебраическая теорема, связывающая коэффициент многочлена при определённом одночлене с его значениями. Теорема даёт нижнюю оценку на размеры комбинаторного параллелепипеда, на котором многочлен не равен тождественно нулю. Эта оценка зависит от степени старшего одночлена по каждой переменной.

История[править | править код]

Впервые теорема была доказана и применена в статье Алона и Тарси 1989 года[1] и в дальнейшем развита Алоном, Натанзоном и Рузса в 1995—1996 годах. Впоследствии она была переформулирована Алоном в 1999 году.[2]

Формулировка теоремы[править | править код]

Далее запись означает коэффициент многочлена при одночлене в многочлене .

Пусть  — многочлен над некоторым полем и  — его старший моном в том смысле, что в любом другом мономе (с ненулевым коэффициентом) степень хотя бы одной переменной меньше, чем в данном.

Теорема утверждает, что если , то для любых множеств с мощностями , найдутся такие, что .

Интерполяционный многочлен[править | править код]

Теорема непосредственно следует из обобщения формулы интерполяционного многочлена Лагранжа для многочлена степени .

Из формулы Лагранжа можно вычленить старший коэффициент многочлена .

Далее при заданном условии на степени монома эта формула обобщается:

откуда и следует очевидным образом теорема о нулях.

Применение[править | править код]

Комбинаторная теорема о нулях может использоваться для доказательства теорем существования, когда существование ненулевого значения многочлена в некоторой точке означает удовлетворение некоторого объекта искомому свойству, а множество всех объектов (среди которых нужно доказать существование) взаимно-однозначно сопоставляется со множеством возможных наборов значений переменных.

Теорема Алона — Фридланда — Калаи[править | править код]

Рассмотрим для примера следующую теорему:

Пусть  — простое число и для графа максимальная степень , а средняя степень .

Тогда в есть -регулярный подграф.[3]

Обозначим через множество рёбер, смежных вершине . Для доказательства теоремы рассмотрим многочлен в поле (по модулю ) от переменных, соответствующих рёбрам графа.

В этом многочлене коэффициент при старшем мономе не равен нулю. При этом, очевидно, . Следовательно, существует непустой набор рёбер таких, что если для них положить , а для остальных , то многочлен на таком наборе примет ненулевое значение.

Так как вычитаемое в будет нулём на всяком ненулевом наборе, то в рассматриваемом наборе для всех , то есть в подграфе из этих рёбрер все степени вершин кратны . А так как они все по условию строго меньше чем , то, удалив вершины с нулевой степенью, получим непустой -регулярный подграф.

Усиление теоремы Коши — Давенпорта[править | править код]

Далее  — простое число.

Теорема Коши — Давенпорта, утверждающая, что для , относительно несложно доказывается элементарными методами.

Однако для её усиления вида для пока не удаётся найти комбинаторного доказательства. Но она легко доказывается через комбинаторную теорему о нулях.[4]

Докажем это усиление от противного. Будем предполагать, что , потому что иначе из множеств можно просто убрать некоторые элементы.

Если , то при утверждение теоремы соответствует утверждению оригинальной теоремы Коши-Давенпорта. Если же , то, так как , можно воспользоваться тем фактом, что и провести индукцию по размеру минимального из множеств и .

Следовательно, достаточно рассмотреть случай . Пусть и . Рассмотрим многочлен . Этот многочлен явно имеет ненулевой по модулю коэффициент при мономе , который выражается через разность биномиальных коэффициентов. Однако для , этот многочлен всегда обращается в ноль, что противоречит комбинаторной теореме о нулях.

См. также[править | править код]

Примечания[править | править код]