Комбінаторна теорема про нулі (теорема Алона, combinatorial nullstellensatz) — алгебрична теорема, що пов'язує коефіцієнт многочлена при певному одночлені з його значеннями. Теорема дає нижню оцінку на розміри комбінаторного паралелепіпеда, на якому многочлен не дорівнює тотожно нулю. Ця оцінка залежить від степеня старшого одночлена за кожною змінною.
Історія
Вперше теорему доведено та застосовано в статті Ноги Алона та Мішеля Тарсі 1989 року, надалі її розвинули Алон, Натанзон і Ружа в 1995—1996 роках. 1999 року Алон переформулював теорему.
Формулювання теореми
Далі запис означає коефіцієнт многочлена при одночлені у многочлені .
Нехай — многочлен над деяким полем і — його старший моном у тому сенсі, що в будь-якому іншому мономі (з ненульовим коефіцієнтом) степінь хоча б однієї змінної менший, ніж у даному.
Теорема стверджує, що якщо , то для будь-яких множин з потужностями , знайдуться такі, що .
Інтерполяційний многочлен
Теорема безпосередньо випливає із узагальнення формули інтерполяційного многочлена Лагранжа для многочлена степеня .
З формули Лагранжа можна виокремити старший коефіцієнт многочлена . Зокрема права частина занулюється на будь-якому многочлені степеня n −1.
Тому за заданої умови на рівні монома ця формула узагальнюється: права частина
може залежати тільки від , звідки й випливає рівність і, очевидно, теорема про нулі.
Застосування
Комбінаторну теорему про нулі можна використати для доведення теорем існування, коли існування ненульового значення многочлена в деякій точці означає задоволення деяким об'єктом шуканої властивості, а множина всіх об'єктів (серед яких потрібно довести існування) взаємно однозначно зіставляється зі множиною можливих наборів значень.
Теорема Алона — Фрідланда — Калаї
Розглянемо для прикладу таку теорему:
Нехай — просте число і для графа найбільший степінь , а середній степінь . Тоді в є -регулярний . |
Позначимо через множину ребер, суміжних вершині . Для доведення теореми розглянемо многочлен у полі (за модулем ) від змінних, відповідних ребрам графа.
У цьому многочлені коефіцієнт при старшому мономі не дорівнює нулю. При цьому, очевидно, . Отже, існує непорожній набір ребер таких, що якщо для них покласти , а для інших , то многочлен на такому наборі набуде ненульового значення.
Оскільки від'ємник у буде нулем на кожному ненульовому наборі, то в аналізованому наборі для всіх , тобто у підграфі з цих ребрер усі степені вершин кратні . А оскільки вони всі за умовою строго менші ніж , то, видаливши вершини з нульовим степенем, отримаємо непорожній -регулярний підграф.
Посилення теореми Коші — Девенпорта
Далі — просте число.
Теорема Коші — Девенпорта, яка стверджує, що для відносно нескладно доводиться елементарними методами.
Однак для її посилення вигляду для поки що не вдається знайти комбінаторного доведення. Але вона легко доводиться через комбінаторну теорему про нулі.
Доведемо це посилення від супротивного. Припускатимемо, що , тому що інакше зі множин можна просто прибрати деякі елементи.
Якщо , то при твердження теореми відповідає твердженню початкової теореми Коші — Девенпорта. Якщо ж , то, оскільки , можна скористатися тим фактом, що і провести індукцію за розміром найменшої зі множин і .
Отже, достатньо розглянути випадок . Нехай і . Розглянемо многочлен . Він явно має ненульовий за модулем коефіцієнт при мономі , що виражається через різницю біноміальних коефіцієнтів. Однак для , цей многочлен завжди перетворюється на нуль, що суперечить комбінаторній теоремі про нулі.
Див. також
Примітки
- Alon, Noga; Tarsi, Michael. A nowhere-zero point in linear mappings. — 1989. — Т. 9, № 4. — С. 393—395. — DOI: .
- Alon, Noga. Combinatorial Nullstellensatz. — 1999. — Т. 8, № 1—2. — С. 7—29. — DOI: . з джерела 3 березня 2016.
- Теорема Алона о нулях и её применения, МФТИ, весна 2014. оригіналу за 17 листопада 2016. Процитовано 12 лютого 2016.
- Аддитивная комбинаторика, открытая библиотека видеолекций, математическая лаборатория имени П. Л. Чебышёва
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Kombinatorna teorema pro nuli teorema Alona combinatorial nullstellensatz algebrichna teorema sho pov yazuye koeficiyent mnogochlena pri pevnomu odnochleni z jogo znachennyami Teorema daye nizhnyu ocinku na rozmiri kombinatornogo paralelepipeda na yakomu mnogochlen ne dorivnyuye totozhno nulyu Cya ocinka zalezhit vid stepenya starshogo odnochlena za kozhnoyu zminnoyu IstoriyaVpershe teoremu dovedeno ta zastosovano v statti Nogi Alona ta Mishelya Tarsi 1989 roku nadali yiyi rozvinuli Alon Natanzon i Ruzha v 1995 1996 rokah 1999 roku Alon pereformulyuvav teoremu Formulyuvannya teoremiDali zapis x1d1 xndn f x1 xn displaystyle x 1 d 1 dots x n d n f x 1 dots x n oznachaye koeficiyent mnogochlena f displaystyle f pri odnochleni x1d1 xndn displaystyle x 1 d 1 dots x n d n u mnogochleni f displaystyle f Nehaj f x1 xn displaystyle f x 1 dots x n mnogochlen nad deyakim polem K displaystyle K i x1d1x2d2 xndn displaystyle x 1 d 1 x 2 d 2 dots x n d n jogo starshij monom u tomu sensi sho v bud yakomu inshomu monomi z nenulovim koeficiyentom stepin hocha b odniyeyi zminnoyi menshij nizh u danomu Teorema stverdzhuye sho yaksho x1d1 xndn f 0 displaystyle x 1 d 1 dots x n d n f not 0 to dlya bud yakih mnozhin A1 An displaystyle A 1 dots A n z potuzhnostyami Ai di 1 displaystyle A i geq d i 1 znajdutsya ai Ai displaystyle a i in A i taki sho f a1 an 0 displaystyle f a 1 dots a n not 0 Interpolyacijnij mnogochlen Teorema bezposeredno viplivaye iz uzagalnennya formuli interpolyacijnogo mnogochlena Lagranzha f x i 0nyi i jx xjxi xj displaystyle f x sum limits i 0 n y i prod limits i not j frac x x j x i x j dlya mnogochlena f displaystyle f stepenya n displaystyle n Z formuli Lagranzha mozhna viokremiti starshij koeficiyent mnogochlena xn f i 0nyi i j1xi xj displaystyle x n f sum limits i 0 n y i prod limits i not j frac 1 x i x j Zokrema prava chastina zanulyuyetsya na bud yakomu mnogochleni stepenya n 1 Tomu za zadanoyi umovi na rivni monoma x1d1 xndn displaystyle x 1 d 1 dots x n d n cya formula uzagalnyuyetsya prava chastina x1d1 xndn f a1 A1 an Anf a1 an a1 b1 A1 an bn An a1 b1 an bn displaystyle x 1 d 1 dots x n d n f sum limits a 1 in A 1 dots sum limits a n in A n frac f a 1 dots a n prod limits a 1 not b 1 in A 1 dots prod limits a n not b n in A n a 1 b 1 dots a n b n mozhe zalezhati tilki vid x1d1 xndn f textstyle x 1 d 1 dots x n d n f zvidki j viplivaye rivnist i ochevidno teorema pro nuli ZastosuvannyaKombinatornu teoremu pro nuli mozhna vikoristati dlya dovedennya teorem isnuvannya koli isnuvannya nenulovogo znachennya mnogochlena v deyakij tochci oznachaye zadovolennya deyakim ob yektom shukanoyi vlastivosti a mnozhina vsih ob yektiv sered yakih potribno dovesti isnuvannya vzayemno odnoznachno zistavlyayetsya zi mnozhinoyu mozhlivih naboriv znachen Teorema Alona Fridlanda Kalayi Rozglyanemo dlya prikladu taku teoremu Nehaj p displaystyle p proste chislo i dlya grafa G V E displaystyle G V E najbilshij stepin D G 2p 1 displaystyle Delta G leq 2p 1 a serednij stepin 2 E V gt 2p 2 displaystyle frac 2 E V gt 2p 2 Todi v G displaystyle G ye p displaystyle p regulyarnij Poznachimo cherez E v displaystyle E v mnozhinu reber sumizhnih vershini v displaystyle v Dlya dovedennya teoremi rozglyanemo mnogochlen u poli Zp displaystyle mathbb Z p za modulem p displaystyle p vid E displaystyle E zminnih vidpovidnih rebram grafa P x1 x E v V 1 e E v xe p 1 e E 1 xe displaystyle P x 1 dots x E prod limits v in V left 1 left sum limits e in E v x e right p 1 right prod limits e in E 1 x e U comu mnogochleni koeficiyent pri starshomu monomi e Exe displaystyle prod limits e in E x e ne dorivnyuye nulyu Pri comu ochevidno P 0 0 0 displaystyle P 0 dots 0 0 Otzhe isnuye neporozhnij nabir reber takih sho yaksho dlya nih poklasti xe 1 displaystyle x e 1 a dlya inshih xe 0 displaystyle x e 0 to mnogochlen na takomu nabori nabude nenulovogo znachennya Oskilki vid yemnik u P displaystyle P bude nulem na kozhnomu nenulovomu nabori to v analizovanomu nabori e E v xe 0 mod p displaystyle sum limits e in E v x e equiv 0 mod p dlya vsih v displaystyle v tobto u pidgrafi z cih rebrer usi stepeni vershin kratni p displaystyle p A oskilki voni vsi za umovoyu strogo menshi nizh 2p displaystyle 2p to vidalivshi vershini z nulovim stepenem otrimayemo neporozhnij p displaystyle p regulyarnij pidgraf Posilennya teoremi Koshi Devenporta Dali p displaystyle p proste chislo Teorema Koshi Devenporta yaka stverdzhuye sho A B a b a A b B min p A B 1 displaystyle A B a b a in A b in B geq min p A B 1 dlya A Zp B Zp displaystyle A subset mathbb Z p B subset mathbb Z p vidnosno neskladno dovoditsya elementarnimi metodami Odnak dlya yiyi posilennya viglyadu A B a b a A b B a b min p A B 2 displaystyle A oplus B a b a in A b in B a not b geq min p A B 2 dlya A Zp B Zp A B displaystyle A subset mathbb Z p B subset mathbb Z p A not B poki sho ne vdayetsya znajti kombinatornogo dovedennya Ale vona legko dovoditsya cherez kombinatornu teoremu pro nuli Dovedemo ce posilennya vid suprotivnogo Pripuskatimemo sho A B 2 p displaystyle A B 2 leq p tomu sho inakshe zi mnozhin mozhna prosto pribrati deyaki elementi Yaksho A B displaystyle A B to pri A B displaystyle A cap B varnothing tverdzhennya teoremi vidpovidaye tverdzhennyu pochatkovoyi teoremi Koshi Devenporta Yaksho zh A B displaystyle A cap B not varnothing to oskilki A B displaystyle A not B mozhna skoristatisya tim faktom sho A B A B A B displaystyle A cap B oplus A cup B subset A oplus B i provesti indukciyu za rozmirom najmenshoyi zi mnozhin A displaystyle A i B displaystyle B Otzhe dostatno rozglyanuti vipadok A B displaystyle A not B Nehaj A B C displaystyle A oplus B subset C i C A B 3 displaystyle C A B 3 Rozglyanemo mnogochlen x y c C x y c displaystyle x y prod limits c in C x y c Vin yavno maye nenulovij za modulem p displaystyle p koeficiyent pri monomi x A 1y B 1 displaystyle x A 1 y B 1 sho virazhayetsya cherez riznicyu binomialnih koeficiyentiv Odnak dlya x A displaystyle x in A y B displaystyle y in B cej mnogochlen zavzhdi peretvoryuyetsya na nul sho superechit kombinatornij teoremi pro nuli Div takozhArifmetichna kombinatorika Mnogochlen LagranzhaPrimitkiAlon Noga Tarsi Michael A nowhere zero point in linear mappings 1989 T 9 4 S 393 395 DOI 10 1007 BF02125351 Alon Noga Combinatorial Nullstellensatz 1999 T 8 1 2 S 7 29 DOI 10 1017 S0963548398003411 z dzherela 3 bereznya 2016 Teorema Alona o nulyah i eyo primeneniya MFTI vesna 2014 originalu za 17 listopada 2016 Procitovano 12 lyutogo 2016 Additivnaya kombinatorika otkrytaya biblioteka videolekcij matematicheskaya laboratoriya imeni P L Chebyshyova