title: Teorema di Szemerédi
text: # 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}}$
  