Erdős-Szemerédi-lause
On aritmeettinen kombinatoriikka , Erdős-Szemerédi lause varmistaa, että on olemassa ainoastaan positiivisia vakioita c ja sa siten, että mikä tahansa äärellinen joukko on todellinen määrä ,
enint(|AT+AT|,|AT⋅AT|)≥vs.|AT|1+e{\ displaystyle \ max (| A + A |, | A \ cdot A |) \ geq c | A | ^ {1+ \ varepsilon}}
missä | | tarkoittaa kardinaali , summa sarjaa of itsensä kanssa jaAT+AT={klo+b | klo,b∈AT}{\ displaystyle A + A = \ {a + b ~ | ~ a, b \ sisään A \}}
AT⋅AT={klo⋅b | klo,b∈AT}.{\ displaystyle A \ cdot A = \ {a \ cdot b ~ | ~ a, b \ sisään A \}.}
Voi tapahtua, että A on kooltaan verrattavissa A + A : han (jos A on aritmeettisessa etenemisessä ) tai A ∙ A: han (jos A on geometrisesti etenevä ). Erdős-Szemerédi-lause voidaan siis tulkita epävirallisesti sanomalla, että "iso" joukko ei voi "käyttäytyä" samanaikaisesti aritmeettisena etenemisenä ja geometrisena etenemisenä; Voimme myös sanoa, että todellinen rivi ei sisällä joukkoa, joka "näyttää" lopulliselta alijäämältä . Tämä on ensimmäinen esimerkki ns. "Sum-product ilmiöstä", jonka tiedetään tapahtuvan monille renkaille ja kappaleille, mukaan lukien rajalliset kentät .
Erdős ja Szemerédi arvelivat, että ε voidaan valita mielivaltaisesti lähellä arvoa 1. Vuonna 2009 paras tulos tähän suuntaan on Solymosi: ε voidaan valita mielivaltaisesti lähellä 1/3.
Huomautuksia ja viitteitä
(fr) Tämä artikkeli on osittain tai kokonaan peräisin
englanninkielisestä Wikipedia- artikkelista
" Erdős - Szemerédi-lause " ( katso luettelo kirjoittajista ) .
-
(sisään) P. Erdős ja E. Szemerédi , "Se summien ja kokonaislukujen tulokset" julkaisussa P. Erdős, Alpár L.,
G. Halász (hu) ja A. Sárközy , Tutkimukset puhtaasta matematiikasta: Paavalin muistiin Turán , Birkhäuser ,1983( lue verkossa ) , s. 213-218
-
(in) Terence Tao , " Summatuote-ilmiö mielivaltaisissa renkaissa " , Diskreetti matematiikka. , voi. 4, n o 22009, s. 59-82, arXiv : 0806.2497
-
(in) Jozsef Solymosi , " multiplicative muokkausalueen energia, jonka sumset " , Advan. Matematiikka. , voi. 222, n ° 22009, s. 402-408, esipainos arXiv : 0806.1040
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">