Teorema di Szemerédi
# 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 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

Il caso k = 1 and k = 2 sono banali. Il caso k = 3 è stato studiato nel 1953 da Klaus Roth tramite un adattamento del metodo circolare di Hardy-Littlewood. Il caso k = 4 è stata fondata nel 1969 da Endre Szemerédi con un metodo combinatorio. Usando un approccio simile a quella che ha usato per il caso k = 3, Roth ha dato una seconda dimostrazione per questo caso nel 1972. Infine, il caso di k 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 prove 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 le analisi di Fourier che le ultime teorie sul calcolo combinatorio.

## Versione formale

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:

    $N=N(k,\delta )\,$

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

    $C^{\log(1/\delta )^{k-1}}\leq N(k,\delta )\leq 2^{2^{\delta ^{-2^{2^{k+9}}}}}$

con C> 1.

Il limite inferiore è stato studiato da Behrend (per k = 3) e Rankin, e il limite superiore è stato studiato da Gowers.

Nel caso k = 3 ( dove i limiti superiori sono meglio definiti); Bourgain ha dimostrato che

    $N(3,\delta )\leq C^{\delta ^{-2}\log(1/\delta )},$

Quest'ultima è stata migliorata Sanders in:

    $N(3,\delta )\leq C^{\delta ^{-1}(\log(1/\delta ))^{5}}$
