A density version of the Carlson–Simpson theorem

Abstract

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

For every integer $k\ge 2$ and every set $A$ of words over $k$ satisfying

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

there exist a word $c$ over $k$ and a sequence $(w_n)$ of left variable words over $k$ such that the set

$c\cup \{c^{⌢}{w}_0(a_0{)}^{⌢}..{.}^{⌢}{w}_n(a_n):n\in \mathbb{N}\text{ and }{a}_0,...,a_n\in [k]\}$

is contained in $A$.

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