Комбинаторная теорема о нулях (TkbQnugmkjugx mykjybg k urlx])
Комбинаторная теорема о нулях (теорема Алона, сombinatorial nullstellensatz) — алгебраическая теорема, связывающая коэффициент многочлена при определённом одночлене с его значениями. Теорема даёт нижнюю оценку на размеры комбинаторного параллелепипеда, на котором многочлен не равен тождественно нулю. Эта оценка зависит от степени старшего одночлена по каждой переменной.
История
[править | править код]Впервые теорема была доказана и применена в статье Ноги Алона и Мишеля Тарси 1989 года[1] и в дальнейшем развита Алоном, Натанзоном и Рузса в 1995—1996 годах. Она была переформулирована Алоном в 1999 году.[2]
Формулировка теоремы
[править | править код]Далее запись означает коэффициент многочлена при одночлене в многочлене .
Пусть — многочлен над некоторым полем и — его старший моном в том смысле, что в любом другом мономе (с ненулевым коэффициентом) степень хотя бы одной переменной меньше, чем в данном.
Теорема утверждает, что если , то для любых множеств с мощностями , найдутся такие, что .
Интерполяционный многочлен
[править | править код]Теорема непосредственно следует из обобщения формулы интерполяционного многочлена Лагранжа для многочлена степени .
Из формулы Лагранжа можно вычленить старший коэффициент многочлена . В частности, правая часть зануляется на любом многочлене степени n−1.
Поэтому при заданном условии на степени монома эта формула обобщается: правая часть
может зависеть только от , откуда и следует равенство и, очевидным образом, теорема о нулях.
Приложения
[править | править код]Комбинаторная теорема о нулях может использоваться для доказательства теорем существования, когда существование ненулевого значения многочлена в некоторой точке означает удовлетворение некоторого объекта искомому свойству, а множество всех объектов (среди которых нужно доказать существование) взаимно-однозначно сопоставляется со множеством возможных наборов значений переменных.
Теорема Алона — Фридланда — Калаи
[править | править код]Рассмотрим для примера следующую теорему:
Пусть — простое число и для графа максимальная степень , а средняя степень . Тогда в есть -регулярный подграф.[3] |
Обозначим через множество рёбер, смежных вершине . Для доказательства теоремы рассмотрим многочлен в поле (по модулю ) от переменных, соответствующих рёбрам графа.
В этом многочлене коэффициент при старшем мономе не равен нулю. При этом, очевидно, . Следовательно, существует непустой набор рёбер таких, что если для них положить , а для остальных , то многочлен на таком наборе примет ненулевое значение.
Так как вычитаемое в будет нулём на всяком ненулевом наборе, то в рассматриваемом наборе для всех , то есть в подграфе из этих рёбрер все степени вершин кратны . А так как они все по условию строго меньше чем , то, удалив вершины с нулевой степенью, получим непустой -регулярный подграф.
Усиление теоремы Коши — Давенпорта
[править | править код]Далее — простое число.
Теорема Коши — Давенпорта, утверждающая, что для , относительно несложно доказывается элементарными методами.
Однако для её усиления вида для пока не удаётся найти комбинаторного доказательства. Но она легко доказывается через комбинаторную теорему о нулях.[4]
Докажем это усиление от противного. Будем предполагать, что , потому что иначе из множеств можно просто убрать некоторые элементы.
Если , то при утверждение теоремы соответствует утверждению оригинальной теоремы Коши-Давенпорта. Если же , то, так как , можно воспользоваться тем фактом, что и провести индукцию по размеру минимального из множеств и .
Следовательно, достаточно рассмотреть случай . Пусть и . Рассмотрим многочлен . Этот многочлен явно имеет ненулевой по модулю коэффициент при мономе , который выражается через разность биномиальных коэффициентов. Однако для , этот многочлен всегда обращается в ноль, что противоречит комбинаторной теореме о нулях.
См. также
[править | править код]Примечания
[править | править код]- ↑ Alon, Noga; Tarsi, Michael. A nowhere-zero point in linear mappings (неопр.). — 1989. — Т. 9, № 4. — С. 393—395. — doi:10.1007/BF02125351.
- ↑ Alon, Noga. Combinatorial Nullstellensatz (неопр.). — 1999. — Т. 8, № 1—2. — С. 7—29. — doi:10.1017/S0963548398003411. Архивировано 3 марта 2016 года.
- ↑ Теорема Алона о нулях и её применения, МФТИ, весна 2014 . Дата обращения: 12 февраля 2016. Архивировано 17 ноября 2016 года.
- ↑ Аддитивная комбинаторика, открытая библиотека видеолекций, математическая лаборатория имени П. Л. Чебышёва
Для улучшения этой статьи желательно:
|