Erdős-Szemerédi sætning

I aritmetiske kombinatorik , de Erdös-Szemerédi sætningen sikrer, at der eksisterer strengt positive konstanter c og Ea sådan, at for enhver endelig mængde A af reelle tal ,

{\ displaystyle \ max (| A + A |, | A \ cdot A |) \ geq c | A | ^ {1+ \ varepsilon}}

hvor | | betegner Kardinalen , den summen af sæt af A med sig selv og ${\ displaystyle A + A = \ {a + b ~ | ~ a, b \ i A \}}$ ${\ displaystyle A \ cdot A = \ {a \ cdot b ~ | ~ a, b \ i A \}.}$

Det kan ske, at A er i størrelse sammenlignelig med A + A (hvis A er i aritmetisk progression ) eller med A ∙ A (hvis A er i geometrisk progression ). Erdős-Szemerédi-sætningen kan derfor fortolkes uformelt ved at sige, at et "stort" sæt ikke kan "opføre sig" samtidigt som en aritmetisk progression og en geometrisk progression; Vi kan også sige, at den virkelige linje ikke indeholder et sæt, der "ligner" en endelig subring . Dette er det første eksempel på det, der nu kaldes "sum-produkt-fænomenet", som man ved, finder sted i mange ringe og kroppe, herunder endelige felter .

Erdős og Szemerédi formodede, at ε kan vælges vilkårligt tæt på 1. I 2009 er det bedste resultat i denne retning Solymosi: ε kan vælges vilkårligt tæt på 1/3.

Noter og referencer

(en) Denne artikel er helt eller delvist hentet fra den engelske Wikipedia- artikel med titlen " Erdős - Szemerédi-sætning " ( se listen over forfattere ) .

(in) P. Erdős og E. Szemerédi , "It sums and products of integers" i P. Erdős, Alpár L., G. Halász (hu) og A. Sárközy , Studies in Pure Mathematics: To the Memory of Paul Turán , Birkhäuser ,1983( læs online ) , s. 213-218
(in) Terence Tao , " Sumproduktfænomenet i vilkårlige ringe " , Diskret matematik. , Vol. 4, n o 22009, s. 59-82, arXiv : 0806.2497
(i) Jozsef Solymosi , " multiplikativ afgrænsningsenergi ved summen " , Advan. Matematik. , Vol. 222, nr . 22009, s. 402-408, fortryk arXiv : 0806.1040