Teorema di Szemerédi
Il teorema di Szemeredi è applicabile alle progressioni aritmetiche nei sottoinsiemi dei numeri interi. Nel 1936, Erdős e Turán ipotizzarono[1] che ogni insieme di interi positivi A, di densità maggiore di zero, contiene una progressione aritmetica con k termini per ogni k esistente. Questa congettura, che divenne il teorema di Szemerédi, generalizza la dichiarazione del teorema di van der Waerden.
Storia
[modifica | modifica wikitesto]Il caso k = 1 and k = 2 sono banali. Il caso k = 3 è stato studiato nel 1953 da Klaus Roth[2] tramite un adattamento del metodo circolare di Hardy-Littlewood. Il caso k = 4 è stata fondata nel 1969 da Endre Szemerédi[3] con un metodo combinatorio. Usando un approccio simile a quella che ha usato per il caso k = 3, Roth[4] ha dato una seconda dimostrazione per questo caso nel 1972. Infine, il caso di k generale è stato dimostrato nel 1975, sempre da Szemerédi,[5] con un'estensione elegante della precedente discussione combinatoria (definita " un capolavoro di ragionamento combinatorio" da R. L. Graham). Diverse altre prove sono ormai note, le più importanti sono quella di Hillel Furstenberg[6] nel 1977, usando la teoria ergodica, e quella di Timothy Gowers[7] nel 2001, utilizzando sia le analisi di Fourier che le ultime teorie sul calcolo combinatorio.
Versione formale
[modifica | modifica wikitesto]Sia k un numero intero positivo e sia valida la condizione 0 <δ ≤ 1/2. Una versione formale del teorema afferma che esiste un intero positivo:
tale che ogni sottoinsieme di {1, 2, ..., N} di dimensione almeno δN contiene una progressione aritmetica di lunghezza k .
I limiti noti per N ( k , δ) sono
con C> 1.
Il limite inferiore è stato studiato da Behrend[8] (per k = 3) e Rankin,[9] e il limite superiore è stato studiato da Gowers.[7]
Nel caso k = 3 ( dove i limiti superiori sono meglio definiti); Bourgain[10] ha dimostrato che
Quest'ultima è stata migliorata Sanders[11] in:
Note
[modifica | modifica wikitesto]- ^ Paul Erdős e Paul Turán, On some sequences of integers (PDF), in Journal of the London Mathematical Society, vol. 11, n. 4, 1936, pp. 261–264, DOI:10.1112/jlms/s1-11.4.261..
- ^ Klaus Friedrich Roth, On certain sets of integers, I, in Journal of the London Mathematical Society, vol. 28, 1953, pp. 104–109, DOI:10.1112/jlms/s1-28.1.104, Zbl 0050.04002, MR 0051853..
- ^ Endre Szemerédi, On sets of integers containing no four elements in arithmetic progression, in Acta Math. Acad. Sci. Hung., vol. 20, 1969, pp. 89–104, DOI:10.1007/BF01894569, Zbl 0175.04301, MR 0245555..
- ^ Klaus Friedrich Roth, Irregularities of sequences relative to arithmetic progressions, IV, in Periodica Math. Hungar., vol. 2, 1972, pp. 301–326, DOI:10.1007/BF02018670, MR 0369311..
- ^ Endre Szemerédi, On sets of integers containing no k elements in arithmetic progression (PDF), in Acta Arithmetica, vol. 27, 1975, pp. 199–245, Zbl 0303.10056, MR 0369312..
- ^ Hillel Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, in J. D'Analyse Math., vol. 31, 1977, pp. 204–256, DOI:10.1007/BF02813304, MR 0498471..
- ^ a b Timothy Gowers, A new proof of Szemerédi's theorem, in Geom. Funct. Anal., vol. 11, n. 3, 2001, pp. 465–588, DOI:10.1007/s00039-001-0332-9, MR 1844079..
- ^ Felix A. Behrend, On the sets of integers which contain no three in arithmetic progression, in Proceedings of the National Academy of Sciences, vol. 23, n. 12, 1946, pp. 331–332, DOI:10.1073/pnas.32.12.331, Zbl 0060.10302..
- ^ Robert A. Rankin, Sets of integers containing not more than a given number of terms in arithmetical progression, in Proc. Roy. Soc. Edinburgh Sect. A, vol. 65, 1962, pp. 332–344, Zbl 0104.03705, MR 0142526..
- ^ Jean Bourgain, On triples in arithmetic progression, in Geom. Func. Anal., vol. 9, n. 5, 1999, pp. 968–984, DOI:10.1007/s000390050105, MR 1726234.
- ^ Tom Sanders, On Roth's theorem on progressions, in Annals of Mathematics, vol. 174, n. 1, 2011, pp. 619–636, DOI:10.4007/annals.2011.174.1.20, MR 2811612.
Collegamenti esterni
[modifica | modifica wikitesto]- (EN) Szemerédi’s theorem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
- (EN) Eric W. Weisstein, Teorema di Szemerédi, su MathWorld, Wolfram Research.
