A density version of the Carlson–Simpson theorem

  • Pandelis Dodos

    University of Athens, Greece
  • Vassilis Kanellopoulos

    National Technical University of Athens, Greece
  • Konstantinos Tyros

    University of Toronto, Canada


We prove a density version of the Carlson–Simpson Theorem. Specifically we show the following.

For every integer k2k ≥ 2 and every set AA of words over kk satisfying

lim supnA[k]n/kn>0\mathrm {lim \ sup}_{n\to\infty} |A \cap [k]^n|/k^n >0

there exist a word cc over kk and a sequence (wn)(w_n) of left variable words over kk such that the set

c{cw0(a0)...wn(an):nN and a0,...,an[k]}{c}\cup \big\{c^{\smallfrown}w_0(a_0)^{\smallfrown}...^{\smallfrown}w_n(a_n):n\in\mathbb N \text{ and } a_0,...,a_n\in [k]\big\}

is contained in AA.

While the result is infinite-dimensional its proof is based on an appropriate finite and quantitative version, also obtained in the paper.

Cite this article

Pandelis Dodos, Vassilis Kanellopoulos, Konstantinos Tyros, A density version of the Carlson–Simpson theorem. J. Eur. Math. Soc. 16 (2014), no. 10, pp. 2097–2164

DOI 10.4171/JEMS/484