Kombinatoriskt nollsats

Den kombinatoriska nollsatsen (Alons sats, kombinatoriska nullstellensatz ) är en algebraisk sats som relaterar koefficienten för ett polynom vid ett visst monom till dess värden. Satsen ger en lägre uppskattning för dimensionerna av en kombinatorisk parallellepiped på vilken polynomet inte är identiskt lika med noll. Denna uppskattning beror på graden av den ledande monomialen i varje variabel.

Historik

Teoremet bevisades och tillämpades först i en artikel från 1989 av Noga Alon och Michel Tarcy [1] och vidareutvecklades av Alon, Natanzon och Ruzsa 1995–1996. Den omformulerades av Alon 1999. [2]

Uttalande av satsen

Vidare betyder posten koefficienten för ett polynom vid ett monom i ett polynom . $[{{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$

Låt vara ett polynom över något fält och vara dess ledande monomial i den meningen att i alla andra monomial (med en koefficient som inte är noll) är graden av minst en variabel mindre än i den givna. $f(x_{1},\dots,x_{n})$ $K$ ${x_{1}}^{d_{1}}{x_{2}}^{d_{2}}\dots {x_{n}}^{d_{n}}$

Satsen säger att om , då för alla mängder med kardinaliteter , det finns sådana som . $[{{x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}}]f\not =0$ $A_{1},\dots ,A_{n}$ $|A_{i}|\geq d_{i}+1$ $a_{i}\in A_{i}$ $f(a_{1},\dots ,a_{n})\not =0$

Interpolationspolynom

Satsen följer direkt av en generalisering av Lagrange - interpolationspolynomformeln för ett gradpolynom . $f(x)=\summa \limits _{i=0}^{n}{y_{i}\prod \limits _{i\not =j}{\frac {x-x_{j)) {x_{i}-x_{j}}}}$ $f$ $n$

Från Lagrange-formeln kan du isolera den ledande koefficienten för polynomet . I synnerhet försvinner den högra sidan på alla polynom med grad n − 1. $[x^{n}]f=\sum \limits _{i=0}^{n}{{y_{i}}\prod \limits _{i\not =j}{\frac {1 }{x_{i}-x_{j}}}}$

Därför, under ett givet villkor på graden av en monomial , är denna formel generaliserad: den högra sidan ${x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}$

$[{{x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}}]f=\summa \limits _{a_{1}\in A_ {1}}\dots \sum \limits _{a_{n}\i A_{n}}{\frac {f(a_{1},\dots ,a_{n})}{\prod \limits _{ a_{1}\not =b_{1}\i A_{1}}\dots \prod \limits _{a_{n}\not =b_{n}\i A_{n}}{(a_{1} -b_{1})\dots (a_{n}-b_{n})}}}$

kan bara bero på , varifrån jämlikheten och, uppenbarligen, nollsatsen följer. ${\textstyle [{{x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}}]f}$

Applikationer

Den kombinatoriska nollsatsen kan användas för att bevisa existenssatser , när förekomsten av ett värde som inte är noll i ett polynom vid någon tidpunkt innebär att något objekt uppfyller den önskade egenskapen, och mängden av alla objekt (bland vilka existens måste bevisas) är en-till-en jämfört med uppsättningen av möjliga uppsättningar av variabelvärden.

Alon-Friedland-Kalais sats

Betrakta till exempel följande teorem:

Låta vara ett primtal och för grafen den maximala graden och medelgraden . $sid$ $G=(V,E)$ $\Delta (G)\leq 2p-1$ ${\frac {2|E|}{|V|}}>2p-2$

Sedan finns det en -vanlig subgraf i . [3] $G$ $sid$

Beteckna med uppsättningen kanter som gränsar till vertexet . För att bevisa satsen, överväg ett polynom i fältet (modulo ) i variabler som motsvarar grafens kanter. $E(v)$ $v$ ${\displaystyle {\mathbb {Z} }_{p))$ $sid$ $|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})$

I detta polynom är koefficienten vid det högsta monomet inte lika med noll. Samtidigt så klart . Därför finns det en icke-tom uppsättning kanter så att om vi sätter för dem och för de andra , så kommer polynomet på en sådan uppsättning att ta ett värde som inte är noll. $\prod \limits _{e\in E}{x_{e}}$ $P(0,\dots ,0)=0$ $x_{e}=1$ $x_{e}=0$

Eftersom den subtraherade in kommer att vara noll på alla icke-nolluppsättningar, då i uppsättningen under övervägande för alla , det vill säga i subgrafen av dessa kanter, är alla grader av hörn multiplar av . Och eftersom de alla är strikt mindre än av villkor , då, genom att ta bort hörn med noll grad, får vi en icke-tom -reguljär subgraf. $P$ $\sum \limits _{e\in E(v)}{x_{e}}\equiv 0\ (mod\ p)$ $v$ $sid$ $2p$ $sid$

En förstärkning av Cauchy-Davenports sats

Nästa är ett primtal. $sid$

Cauchy-Davenports sats, som säger att för , är relativt lätt att bevisa med elementära metoder. $|A+B|=|\{{a+b:a\in A,b\in B}\}|\geq \min\{{p,|A|+|B|-1}\ }$ ${\displaystyle A\subset {\mathbb {Z} }_{p},B\subset {\mathbb {Z} }_{p))$

Det har dock ännu inte hittats några kombinatoriska bevis för att stärka formen för . Men det bevisas lätt genom den kombinatoriska nollsatsen. [fyra] $|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$

Låt oss bevisa denna förstärkning genom motsägelse. Vi kommer att anta det , för annars kan vissa element helt enkelt tas bort från uppsättningarna. $|A|+|B|-2\leq p$

Om , då för påståendet om satsen motsvarar påståendet i den ursprungliga Cauchy-Davenport-satsen. Om , då, sedan , kan vi använda det faktum att och utföra induktion på storleken på den minsta av uppsättningarna och . $|A|=|B|$ $A \cap B = \varnothing$ $A\cap B\not =\varnothing$ $A\not =B$ $(A\cap B)\oplus (A\cup B)\subset A\oplus B$ $A$ $B$

Därför räcker det att ta ställning till fallet . Låt och . Låt oss betrakta ett polynom . Detta polynom har uttryckligen en koefficient som inte är noll vid monomialen , vilket uttrycks i termer av skillnaden mellan de binomiska koefficienterna. Men för , detta polynom försvinner alltid, vilket motsäger den kombinatoriska nollsatsen. $|A|\not =|B|$ $(A\oplus B)\subset C$ $|C|=|A|+|B|-3$ ${\displaystyle (xy)\prod \limits _{c\in C}{(x+yc)))$ $sid$ $x^{|A|-1}y^{|B|-1}$ $x\i A$ $y\in B$

Se även

Anteckningar

↑ Alon, Noga ; Tarsi, Michael. En ingenstans-nollpunkt i linjära mappningar (neopr.) . - 1989. - T. 9 , nr 4 . - S. 393-395 . - doi : 10.1007/BF02125351 .
↑ Alon, Noga . Kombinatorisk Nullstellensatz (neopr.) . - 1999. - V. 8 , nr 1-2 . - S. 7-29 . - doi : 10.1017/S0963548398003411 .
↑ Alons nollsats och dess tillämpningar, MIPT, våren 2014 . Hämtad 12 februari 2016. Arkiverad från originalet 17 november 2016. (obestämd)
↑ Additiv kombinatorik, öppet bibliotek med videoföreläsningar, matematiskt laboratorium uppkallat efter P. L. Chebyshev