Namespaces
Variants
Actions

Difference between revisions of "Van der Waerden theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(LaTeX)
Line 1: Line 1:
 +
{{TEX|done}}
 +
 
''on arithmetic progressions''
 
''on arithmetic progressions''
  
Given natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v0960501.png" />, there exists a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v0960502.png" /> such that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v0960503.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v0960504.png" /> is partitioned into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v0960505.png" /> sets, then at least one set contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v0960506.png" /> terms in [[Arithmetic progression|arithmetic progression]] [[#References|[a1]]]. Another, equivalent, non-finitary, formulation is as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v0960507.png" /> be a finite partition of the natural numbers; then at least one <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v0960508.png" /> contains arithmetic progressions of arbitrary length. The result was conjectured by A. Baudet. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v0960509.png" /> be a set of natural numbers and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v09605010.png" /> be its upper [[Asymptotic density|asymptotic density]]. When discussing van der Waerden's theorem stated above, P. Erdös and P. Turán conjectured that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v09605011.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v09605012.png" /> contains arbitrary long arithmetic progressions; [[#References|[a2]]].
+
Given natural numbers $\ell,m$, there exists a number $N(\ell,m)$ such that if $n \ge N(\ell,m)$ and $\{1,2,\ldots,n\}$ is partitioned into $m$ sets, then at least one set contains $\ell$ terms in [[Arithmetic progression|arithmetic progression]] [[#References|[a1]]]. Another, equivalent, non-finitary, formulation is as follows. Let $\mathbb{N} = X_1 \cup \cdots \cup X_m$ be a finite partition of the natural numbers; then at least one $X_i$ contains arithmetic progressions of arbitrary length. The result was conjectured by A. Baudet. Let $A \subset \{1,2,\ldots\}$ be a set of natural numbers and let $\bar d(A)$ be its upper [[asymptotic density]]. When discussing van der Waerden's theorem stated above, P. Erdös and P. Turán conjectured that if $\bar d(A) > 0$, then $A$ contains arbitrary long arithmetic progressions; [[#References|[a2]]].
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v09605013.png" /> be a maximally large subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v09605014.png" /> which contains no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v09605015.png" /> elements in arithmetic progression. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v09605016.png" /> be the number of elements in a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v09605017.png" />. Then Szemerédi's theorem, [[#References|[a3]]], says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v09605018.png" />. This implies the Erdös–Turán conjecture. Another proof of Szemerédi's theorem was given by H. Furstenberg, based on ideas from [[Ergodic theory|ergodic theory]], [[#References|[a4]]].
+
Let $B(\ell,n)$ be a maximally large subset of $\{1,2,\ldots,n\}$ which contains no $\ell$ elements in arithmetic progression. Let $b(\ell,n)$ be the number of elements in a $B(\ell,n)$. Then Szemerédi's theorem, [[#References|[a3]]], says that $\lim_{n \rightarrow \infty} n^{-1} b(\ell,n) = 0$. This implies the Erdös–Turán conjecture. Another proof of Szemerédi's theorem was given by H. Furstenberg, based on ideas from [[Ergodic theory|ergodic theory]], [[#References|[a4]]].
  
 
For a personal historical account of the van der Waerden theorem see [[#References|[a6]]].
 
For a personal historical account of the van der Waerden theorem see [[#References|[a6]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  B.L. van der Waerden,  "Beweis einer Baudetschen Vermutung"  ''Nieuw Arch. Wisk.'' , '''15'''  (1927)  pp. 212–216</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Erdös,  P. Turán,  "On some sequences of integers"  ''J. London Math. Soc.'' , '''11'''  (1936)  pp. 261–264</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  E. Szemerédi,  "On sets of integers containing no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096050/v09605019.png" />-elements in arithmetic progression"  ''Acta Arithm.'' , '''27'''  (1975)  pp. 199–245</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  H. Furstenberg,  "Ergodic behaviour of diagonal measures and a theorem of Szemerédi on arithmetic progressions"  ''J. d'Anal. Math.'' , '''31'''  (1977)  pp. 204–256</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  H. Furstenberg,  "Recurrence in ergodic theory and combinatorial number theory" , Princeton Univ. Press  (1981)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  A.Ya. Khinchin,  "Three pearls of number theory" , Graylock  (1952)  (Translated from Russian)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  B.L. van der Waerden,  "Beweis einer Baudetschen Vermutung"  ''Nieuw Arch. Wisk.'' , '''15'''  (1927)  pp. 212–216</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Erdös,  P. Turán,  "On some sequences of integers"  ''J. London Math. Soc.'' , '''11'''  (1936)  pp. 261–264</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  E. Szemerédi,  "On sets of integers containing no $k$-elements in arithmetic progression"  ''Acta Arithm.'' , '''27'''  (1975)  pp. 199–245</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  H. Furstenberg,  "Ergodic behaviour of diagonal measures and a theorem of Szemerédi on arithmetic progressions"  ''J. d'Anal. Math.'' , '''31'''  (1977)  pp. 204–256</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top">  H. Furstenberg,  "Recurrence in ergodic theory and combinatorial number theory" , Princeton Univ. Press  (1981)</TD></TR>
 +
<TR><TD valign="top">[a6]</TD> <TD valign="top">  A.Ya. Khinchin,  "Three pearls of number theory" , Graylock  (1952)  (Translated from Russian)</TD></TR>
 +
</table>

Revision as of 19:29, 6 January 2015


on arithmetic progressions

Given natural numbers $\ell,m$, there exists a number $N(\ell,m)$ such that if $n \ge N(\ell,m)$ and $\{1,2,\ldots,n\}$ is partitioned into $m$ sets, then at least one set contains $\ell$ terms in arithmetic progression [a1]. Another, equivalent, non-finitary, formulation is as follows. Let $\mathbb{N} = X_1 \cup \cdots \cup X_m$ be a finite partition of the natural numbers; then at least one $X_i$ contains arithmetic progressions of arbitrary length. The result was conjectured by A. Baudet. Let $A \subset \{1,2,\ldots\}$ be a set of natural numbers and let $\bar d(A)$ be its upper asymptotic density. When discussing van der Waerden's theorem stated above, P. Erdös and P. Turán conjectured that if $\bar d(A) > 0$, then $A$ contains arbitrary long arithmetic progressions; [a2].

Let $B(\ell,n)$ be a maximally large subset of $\{1,2,\ldots,n\}$ which contains no $\ell$ elements in arithmetic progression. Let $b(\ell,n)$ be the number of elements in a $B(\ell,n)$. Then Szemerédi's theorem, [a3], says that $\lim_{n \rightarrow \infty} n^{-1} b(\ell,n) = 0$. This implies the Erdös–Turán conjecture. Another proof of Szemerédi's theorem was given by H. Furstenberg, based on ideas from ergodic theory, [a4].

For a personal historical account of the van der Waerden theorem see [a6].

References

[a1] B.L. van der Waerden, "Beweis einer Baudetschen Vermutung" Nieuw Arch. Wisk. , 15 (1927) pp. 212–216
[a2] P. Erdös, P. Turán, "On some sequences of integers" J. London Math. Soc. , 11 (1936) pp. 261–264
[a3] E. Szemerédi, "On sets of integers containing no $k$-elements in arithmetic progression" Acta Arithm. , 27 (1975) pp. 199–245
[a4] H. Furstenberg, "Ergodic behaviour of diagonal measures and a theorem of Szemerédi on arithmetic progressions" J. d'Anal. Math. , 31 (1977) pp. 204–256
[a5] H. Furstenberg, "Recurrence in ergodic theory and combinatorial number theory" , Princeton Univ. Press (1981)
[a6] A.Ya. Khinchin, "Three pearls of number theory" , Graylock (1952) (Translated from Russian)
How to Cite This Entry:
Van der Waerden theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Van_der_Waerden_theorem&oldid=12126