Il teorema di Szemeredi è applicabile alle progressioni aritmetiche nei sottoinsiemi dei numeri interi. Nel 1936, Erdős e Turán ipotizzarono. che ogni insieme di interi positivi di densità maggiore di zero, contiene una progressione aritmetica con termini per ogni esistente. Questa congettura, che divenne il teorema di Szemerédi, generalizza il teorema di van der Waerden.
Storia I casi e sono banali. Il caso è stato studiato nel 1953 da Klaus Roth. tramite un adattamento del metodo del cerchio di Hardy e Littlewood. Il caso è stata dimostrato nel 1969 da Endre Szemerédi. con un metodo combinatorio. Usando un approccio simile a quello che ha usato per il caso Roth. ha dato una seconda dimostrazione per questo caso nel 1972. Infine, il caso generale è stato dimostrato nel 1975, sempre da Szemerédi,. con un'estensione elegante della precedente discussione combinatoria (definita "un capolavoro di ragionamento combinatorio" da R. L. Graham). Diverse altre dimostrazioni sono ormai note, le più importanti sono quella di Hillel Furstenberg. nel 1977, usando la teoria ergodica, e quella di Timothy Gowers. nel 2001, utilizzando sia l'analisi di Fourier che recenti risultati di calcolo combinatorio.
Versione formale Sia un numero intero positivo e sia valida la condizione Una versione formale del teorema afferma che esiste un intero positivo:
tale che ogni sottoinsieme di di cardinalità almeno contiene una progressione aritmetica di lunghezza
Maggioranti e minoranti noti per sono
con I precedenti minoranti sono stato individuati da Behrend. (per ) e Rankin,. e i maggioranti da Gowers.
Nel caso Bourgain ha dimostrato che
Quest'ultima disuguaglianza è stata migliorata da Sanders in:
Note
Collegamenti esterni
Szemerédi