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}}\le N(k,\delta )\le 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 )\le C^{{\delta }^{-2}\log (1/\delta )},$

Quest'ultima è stata migliorata Sanders in:

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

Collegamenti esterni

• Template:Collegamenti esterni