Teorema de Szemerédi

En combinatoria aritmètica, la teorema de Szemerédi (denominat aixina en referència al matemàtic hongarés Endre Szemerédi) és un resultat relatiu a progressions aritmètiques en subconjunts dels número entero. En 1936, Erdős i Turán conjeturaron que cada conjunt de sancers A en densitat natural positiva conté k térmens en progressió aritmètica per a cada k. Endre Szemerédi va demostrar la conjectura en 1975.

Declaració

Es diu que un subconjunt A de número natural té densitat superior positiva si

$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{|A\cap \{1,2,3,\dots ,n\}|}{n}>0$.

La teorema de Szemerédi afirma que un subconjunt dels número natural en densitat superior positiva conté infinites progressions aritmètiques de llongitut k per a tots els número entero positius k.

Una versió finita equivalent d'us freqüent de la teorema establix que per a cada número entero positiu k i número real $\delta \in (0,1]$, existix un número entero positiu

$N=N(k,\delta )$

tal que cada subconjunt de {1, 2, ..., N} de tamany a lo manco δN conté una progressió aritmètica de llongitut k.

Una atra formulació usa la funció r_k(N), el tamany del subconjunt més gran de {1, 2, ..., N} sense una progressió aritmètica de llongitut k. La teorema de Szemerédi és equivalent al llímit asintòtic

$r_k(N)=o(N)$.

És dir, r_k(N) creix menys que linealmente en N.

Història

El teorema de Van der Waerden, un precursor de la teorema de Szemerédi, va ser provat en 1927.

Els casos k = 1 i k = 2 de la teorema de Szemerédi són trivials. El cas k= 3, conegut com teorema de Roth, va ser establit en 1953 per Klaus Roth a través d'una adaptació de método del círcul de Hardy-Littlewood. Endre Szemerédi va demostrar el cas k= 4 per mig d'combinatoria. Usant un enfocament similar al que va usar per al cas k= 3, Roth va donar una segona prova d'esta teorema en 1972.

El cas general es va resoldre en 1975, també per Szemerédi, qui va desenrollar una extensió ingeniosa i complicada del seu anterior argument combinatori per a k= 4 (cridat "una obra mestra del raonament combinatori" per Erdős). Ara es coneixen vàries atres demostracions, sent les més importants les d'Hillel Furstenberg en 1977, usant teoria ergòdica, i les de William Timothy Gowers en 2001, usant tant anàlisis de Fourier com combinatòria. Terence Tao ha cridat a les diverses demostracions de la teorema de Szemerédi la pedra de Rosetta necessària per a conectar camps dispars de les matemàtiques.

Vore també

• Problemes que involucren progressions aritmètiques
• Teoria ergòdica de Ramsey
• Combinatoria aritmètica
• Lema de regularitat de Szemerédi