Teorema nulă combinatorie

Teorema combinatorie zero (teorema lui Alon, combinatorial nullstellensatz ) este o teoremă algebrică care leagă coeficientul unui polinom la un anumit monom la valorile sale. Teorema oferă o estimare mai mică pentru dimensiunile unui paralelipiped combinatoriu pe care polinomul nu este identic egal cu zero. Această estimare depinde de gradul monomiului principal în fiecare variabilă.

Istorie

Teorema a fost pentru prima dată demonstrată și aplicată într-o lucrare din 1989 de către Noga Alon și Michel Tarcy [1] și dezvoltată în continuare de Alon, Natanzon și Ruzsa în 1995–1996. A fost reformulat de Alon în 1999. [2]

Enunțul teoremei

În plus, intrarea înseamnă coeficientul unui polinom la un monom dintr-un polinom . $[{{x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}}]f(x_{1},\dots,x_{n})$ $f$ ${x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}$ $f$

Fie un polinom peste un anumit câmp și să fie monomul său principal în sensul că în orice alt monom (cu un coeficient diferit de zero) gradul a cel puțin unei variabile este mai mic decât în cea dată. $f(x_{1},\dots,x_{n})$ $K$ ${x_{1}}^{d_{1}}{x_{2}}^{d_{2}}\dots {x_{n}}^{d_{n}}$

Teorema afirmă că dacă , atunci pentru orice mulțimi cu cardinalități , există astfel încât . $[{{x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}}]f\not =0$ $A_{1},\puncte ,A_{n}$ $|A_{i}|\geq d_{i}+1$ $a_{i}\in A_{i}$ $f(a_{1},\dots, a_{n})\not =0$

Polinom de interpolare

Teorema decurge direct dintr-o generalizare a formulei polinomului de interpolare Lagrange pentru un polinom de grad . $f(x)=\sum \limits _{i=0}^{n}{y_{i}\prod \limits _{i\not =j}{\frac {x-x_{j)} {x_{i}-x_{j}}}}}$ $f$ $n$

Din formula Lagrange, puteți izola coeficientul de conducere al polinomului . În special, partea dreaptă dispare pe orice polinom de gradul n - 1. $[x^{n}]f=\sum \limits _{i=0}^{n}{{y_{i}}\prod \limits _{i\not =j}{\frac {1 {x_{i}-x_{j}}}}}$

Prin urmare, într-o anumită condiție asupra gradului unui monom , această formulă este generalizată: partea dreaptă ${x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}$

$[{{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})}}}$

poate depinde doar de , de unde urmează egalitatea și, evident, teorema zero. ${\textstyle [{{x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}}]f}$

Aplicații

Teorema combinatorie zero poate fi folosită pentru a demonstra teoremele de existență , atunci când existența unei valori nenule a unui polinom la un moment dat înseamnă că un anumit obiect satisface proprietatea dorită și mulțimea tuturor obiectelor (printre care existența trebuie dovedită) este unul la unu în comparație cu setul de seturi posibile de valori variabile.

Teorema Alon-Friedland-Kalai

Luați în considerare, de exemplu, următoarea teoremă:

Fie un număr prim și pentru grafic gradul maxim și gradul mediu . $p$ $G=(V,E)$ $\Delta (G)\leq 2p-1$ ${\frac {2|E|}{|V|}}>2p-2$

Apoi există un subgraf -regular în . [3] $G$ $p$

Se notează prin mulțimea muchiilor adiacente vârfului . Pentru a demonstra teorema, considerăm un polinom în câmp (modulo ) în variabile corespunzătoare muchiilor graficului. $E(v)$ $v$ ${\mathbb {Z} }_{p)$ $p$ $|E|$

$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})$

În acest polinom, coeficientul de la cel mai mare monom nu este egal cu zero. În același timp, evident . Prin urmare, există un set nevid de muchii astfel încât dacă punem pentru ele și pentru celelalte , atunci polinomul dintr-o astfel de mulțime va lua o valoare diferită de zero. $\prod \limits _{e\in E}{x_{e}}$ $P(0,\dots ,0)=0$ $x_{e}=1$ $x_{e}=0$

Deoarece scăderea în va fi zero pe orice mulțime diferită de zero, atunci în mulțimea luată în considerare pentru toate , adică în subgraful acestor muchii, toate gradele de vârfuri sunt multipli de . Și deoarece toate sunt strict mai mici decât prin condiție , atunci, prin eliminarea vârfurilor cu grad zero, obținem un subgraf regulat nevid. $P$ $\sum \limits _{e\in E(v)}{x_{e}}\equiv 0\ (mod\p)$ $v$ $p$ $2p$ $p$

O consolidare a teoremei Cauchy-Davenport

Urmează un număr prim. $p$

Teorema Cauchy-Davenport, care afirmă că pentru , este relativ ușor de demonstrat prin metode elementare. $|A+B|=|\{{a+b:a\in A,b\in B}\}|\geq \min\{{p,|A|+|B|-1}\ }$ $A\subset {\mathbb {Z} }_{p}, B\subset {\mathbb {Z} }_{p)$

Cu toate acestea, nu s-a găsit încă nicio dovadă combinatorie care să întărească forma pentru . Dar este ușor de demonstrat prin teorema combinatorie zero. [patru] $|A\oplus B|=|\{{a+b:a\in A,b\in B,a\not =b}\}|\geq \min\{{p,|A|+ |B|-2}\}$ $A\subset {\mathbb {Z} }_{p}, B\subset {\mathbb {Z} }_{p}, A\not =B$

Să dovedim această întărire prin contradicție. Vom presupune că , deoarece altfel unele elemente pot fi pur și simplu eliminate din mulțimi. $|A|+|B|-2\leq p$

Dacă , atunci pentru enunțul teoremei corespunde enunțului teoremei originale Cauchy-Davenport. Dacă , atunci, din moment ce , putem folosi faptul că și efectuăm inducție pe dimensiunea celui mai mic dintre seturi și . $|A|=|B|$ $A \cap B = \varnothing$ $A\cap B\nu =\varnothing$ $A\nu =B$ $(A\cap B)\oplus (A\cup B)\subset A\oplus B$ $A$ $B$

Prin urmare, este suficient să luăm în considerare cazul . Lasă și . Să considerăm un polinom . Acest polinom are în mod explicit un coeficient diferit de zero la monom , care este exprimat în termenii diferenței coeficienților binomi. Totuși, pentru , acest polinom dispare întotdeauna, ceea ce contrazice teorema combinatorie zero. $|A|\not =|B|$ $(A\oplus B)\subset C$ $|C|=|A|+|B|-3$ $(xy)\prod \limits _{c\in C}{(x+yc))$ $p$ $x^{|A|-1}y^{|B|-1}$ $x\în A$ $y\in B$

Vezi și

Note

↑ Alon, Noga ; Tarsi, Michael. Un punct de nicăieri zero în mapările liniare (neopr.) . - 1989. - T. 9 , nr 4 . - S. 393-395 . - doi : 10.1007/BF02125351 .
↑ Alon, Noga . Combinatorial Nullstellensatz (neopr.) . - 1999. - V. 8 , Nr. 1-2 . - S. 7-29 . - doi : 10.1017/S0963548398003411 .
↑ Teorema lui Alon zero și aplicațiile sale, MIPT, primăvara 2014 . Consultat la 12 februarie 2016. Arhivat din original la 17 noiembrie 2016. (nedefinit)
↑ Combinatorică aditivă, bibliotecă deschisă de prelegeri video, laborator de matematică numit după P. L. Chebyshev