Concepts.tex

\section{Basic concepts} \label{sec:concepts}

In this section we introduce some basic concepts around the density Hales--Jewett theorem, and also state formally the extensions of DHJ($k$) that we will prove.

\subsection{Points, lines, and line templates} \label{sec:defs} In the density Hales--Jewett theorem the arithmetic properties of $[k] = \{1, 2, \dotsc, k\}$ play no role. It is only important that this set has $k$ elements; this dictates the length of a combinatorial line. Therefore we can equivalently replace $[k]$ by any other \emph{alphabet} $\Omega$ of $k$ \emph{symbols}, treating the elements of $\Omega^n$ as \emph{strings}. We will typically use letters $a$, $b$,~\ldots for symbols, $x$, $y$,~\ldots for strings/points, and $i$, $j$,~\ldots for coordinates; e.g., $x_j = b$ means the $j$th coordinate of string $x$ is symbol $b$.

We have already seen that it was convenient to use a different alphabet $\Omega$ when we took $\Omega = \{0, 1, \dots, k-1\}$ to deduce van der Waerden's theorem from Hales--Jewett. A more interesting observation is that a combinatorial line template over $[k]^n$, i.e.\ a string in $([k] \cup \{\wild\})^n$, is again just a string over an alphabet of size $k+1$. If we use the symbol `$k + 1$' in place of `$\wild$', we see that \emph{a point in $[k+1]^n$ can be interpreted as a line in $[k]^n$}. For example, the point $13332213 \in [3]^8$ corresponds to the length-$2$ line $\{1\bs{1}\bs{1}\bs{1}221\bs{1}, 1\bs{2}\bs{2}\bs{2}221\bs{2}\} \subset [2]^8$. We introduce the notation $ \chg{x}{b}{a} $ for the string formed by changing all occurrences of symbol $b$ to symbol $a$ in string $x$. Thus a line template $\lambda \in ([3] \cup \{\wild\})^n$ corresponds to the line $\{\chg{\lambda}{\wild}{1}, \chg{\lambda}{\wild}{2}, \chg{\lambda}{\wild}{3}\} \subseteq [3]^n$.

Let us give some formal definitions, taking care of the somewhat tedious possibility of degenerate line templates: \begin{definition} We say that $x \in \Omega^n$ is a \emph{degenerate string} if it is missing at least one symbol from~$\Omega$. A \emph{line template over $\Omega^n$ with wildcard symbol $c$} ($\not \in \Omega$) is a string $\lambda \in (\Omega \cup \{c\})^n$. We say $z$ is a \emph{degenerate line template} if $z$ contains no `$c$' symbols. If $\lambda$ is nondegenerate, we associate to it the \emph{combinatorial line} $\{\chg{\lambda}{c}{a} : a \in \Omega\} \subseteq \Omega^n$, which has cardinality $\abs{\Omega}$. \end{definition} We will often blur the distinction between a line template and a line; however, please note that for us a ``line is always nondegenerate, whereas a line template may not be.

\subsection{Subspaces} As mentioned, we will find it useful to think of lines over $[k]^n$ as points in $[k+1]^n$, with $k+1$ serving as the wildcard symbol. It's natural then to ask for an interpretation of a point in, say, $[k+2]^n$. This can be thought of as a combinatorial \emph{plane} over $[k]^n$. For simplicity, let's consider $k = 3$ and replace $[k+2]$ with $[3] \cup \{\wild_1, \wild_2\}$. A string in $([3] \cup \{\wild_1, \wild_2\})^n$ such as \[ \sigma = 1 3 \wild_1 \wild_2 2 1 \wild_1 \wild_1 3 \wild_2 1 \] (here $n = 11$) corresponds to the following $9$-point combinatorial plane: \[ \begin{array}{rcl} \phantom{.[3]^{11} \supset} \{13\bs{1}\bs{1}21\bs{1}\bs{1}3\bs{1}1,&13\bs{2}\bs{1}21\bs{2}\bs{2}3\bs{1}1,&13\bs{3}\bs{1}21\bs{3}\bs{3}3\bs{1}1, \\

 13\bs{1}\bs{2}21\bs{1}\bs{1}3\bs{2}1,&13\bs{2}\bs{2}21\bs{2}\bs{2}3\bs{2}1,&13\bs{3}\bs{2}21\bs{3}\bs{3}3\bs{2}1, \\
 13\bs{1}\bs{3}21\bs{1}\bs{1}3\bs{3}1,&13\bs{2}\bs{3}21\bs{2}\bs{2}3\bs{3}1,&13\bs{3}\bs{3}21\bs{3}\bs{3}3\bs{3}1\} \subset [3]^{11}. \\

\end{array} \] More generally: \begin{definition} For $d \geq 1$, a \emph{$d$-dimensional subspace template over $\Omega^n$ with wildcard symbols $c_1, \dots, c_d$} (distinct symbols not in $\Omega$) is a string $\sigma \in (\Omega \cup \{c_1, \dots, c_d\})^n$. We say $\sigma$ is a \emph{degenerate template} if $\sigma$ is missing any of the $c_i$ symbols. If $\sigma$ is nondegenerate, we associate to it the \emph{$d$-dimensional combinatorial subspace} $\{\chg{\sigma}{(c_1, \dotsc, c_d)}{(a_1, \dotsc, a_d)} : (a_1, \dotsc, a_d) \in \Omega^d\} \subseteq \Omega^n$, which has cardinality $\abs{\Omega}^d$. \end{definition} \noindent Here we have introduced the extended notation $\chg{x}{(c_1, \dotsc, c_d)}{(a_1, \dotsc, a_d)}$ for the string in $\Omega^n$ formed by changing all occurrences of symbol $c_i$ to symbol $a_i$ in string $x$, for all $i \in [d]$.

The \emph{multidimensional} density Hales--Jewett theorem (also proved by Furstenberg and Katznelson~\cite{FK91}) states that dense subsets of $[k]^n$ contain not just lines but combinatorial subspaces: \begin{named}{Multidimensional density Hales--Jewett theorem} \label{thm:mdhj} For every real $\delta > 0$ and every pair of positive integers $k$ and $d$, there exists a positive integer $\mdhj{k}{\delta}{d}$ such that every subset of $[k]^n$ of density at least $\delta$ contains a $d$-dimensional combinatorial subspace, provided $n \geq \mdhj{k}{\delta}{d}$. \end{named}

Indeed, it is easy to deduce the multidimensional DHJ($k$) from the basic DHJ($k$): \begin{proposition} \label{prop:mdhj-from-dhj} For a given $k$, the multidimensional density Hales--Jewett theorem follows from the density Hales--Jewett theorem. \end{proposition} \begin{proof} By induction on $d$. Suppose we have proven the multidimensional DHJ($k$) theorem for $d-1$, and let $A \subseteq [k]^n$ have density at least $\delta$. Let $m = \mdhj{k}{\delta/2}{d-1}$, and write a generic string $z \in [k]^n$ as $(x,y)$, where $x \in [k]^m$, $y \in [k]^{n-m}$. Call a string $y \in [k]^{n-m}$ ``good if $A_y = \{x \in [k]^m : (x,y) \in A\}$ has density at least $\delta/2$ within $[k]^m$. Let $G \subseteq [k]^{n-m}$ be the set of good $y$'s. By a simple counting argument, the density of $G$ within $[k]^{n-m}$ must be at least $\delta/2$; otherwise, $A$ would not have density at least $\delta$ in $[k]^{n-m}$.

By induction, for any good $y$ the set $A_y$ contains a $(d-1)$-dimensional combinatorial subspace. There are at most $M = (k+d-1)^m$ such subspaces (since each is defined by a template in $[k + (d-1)]^{m}$). Hence there must be a particular subspace $\sigma \subseteq [k]^m$ such that the set \[ G_\sigma = \{y \in [k]^{n-m} : (x,y) \in A\ \forall x \in \sigma\} \] has density at least $(\delta/2)/M$ within $[k]^{n-m}$. Finally, provided $n \geq m + \dhj{k}{\delta/2M}$, we conclude from DHJ($k$) that $G_\sigma$ contains a combinatorial line, $\lambda$. Now $\sigma \times \lambda \subseteq [k]^n$ is the desired $d$-dimensional subspace contained in $A$. \end{proof}

The argument in Proposition~\ref{prop:mdhj-from-dhj} gives a (seemingly) poor bound for large $d$. We note that in the $k = 2$ case, Gunderson, R\"odl, and Sidorenko~\cite{GRS99} have established a much superior bound: \begin{named}{Gunderson--R\"odl--Sidorenko theorem} \label{thm:grs} One may take $\mdhj{2}{\delta}{d} = (10d)^{d2^d} \cdot (1/\delta)^{2^d}$. \end{named} \noindent(To see this from~\cite{GRS99}, combine that paper's Theorem~4.2 and equation~8, and note that its ``$c(d)$ is at most $(10d)^d$. The authors also showed this bound is fairly close to being sharp.) \ignore{ \begin{theorem} Let $A \subseteq [2]^n$ have (uniform) density at least $\delta$, and assume $n \geq (10d)^{d2^d} \cdot (1/\delta)^{2^d}$. Then $A$ contains a nondegenerate $d$-dimensional subspace. \end{theorem} \begin{proof} Theorem 4.2 and equation~(8) of~\cite{GRS99} taken together state that the maximum density of a $d$-dimensional subspace-free subset of $[2]^n$ is at most \[ c(d) \cdot n^{-1/2^d}, \quad \text{where } c(d) = 10^d 2^{-1/2^{d-1}}d^{d - 1/2^d}. \] Note that $c(d) < (10d)^d$. Hence it suffices to check that our lower bound on $n$ implies $\delta \geq (10d)^d n^{-1/2^d}$. \end{proof}}

\subsubsection{Passing to a subspace} \label{sec:pass-subspace} A useful aspect of subspaces is that they ``look like the original space.\noteryan{I plagiarized this phrase from Walters.} More precisely, a $d$-dimensional subspace $\{\chg{\sigma}{(c_1, \dotsc, c_d)}{(a_1, \dotsc, a_d)} : (a_1, \dotsc, a_d) \in \Omega^d\} \subseteq \Omega^n$ is isomorphic to $\Omega^d$, in the sense that $d'$-dimensional subspaces of $\sigma$ map to $d'$-dimensional subspaces of $\Omega^n$. This identification is easiest to see when the subspace template $\sigma$ has exactly one copy of each wildcard symbol $c_i$. In this case, writing $J$ for the set of $d$ wildcard coordinates, we will call $\sigma \cong \Omega^J$ a \emph{restriction} to the coordinates $J$ (see Definition~\ref{def:restriction}).

This isomorphism is useful because it allows us to ``pass to subspaces when looking for a combinatorial line (or subspace) in a subset $A \subseteq [k]^n$. By this we mean the following: Given a $d$-dimensional subspace $\sigma$ of $[k]^n$, ``passing to $\sigma$ means considering $A' = A \cap \sigma$ as a subset of $[k]^d$. Note that if we manage to find a line (or subspace) contained in $A'$, this maps back to a line (subspace) contained in $A$. This is helpful if $A'$ has some kind of improved ``structure; e.g., a higher density (within $[k]^d$). Indeed, finding density increments on subspaces is the basic strategy for our proof of DHJ($k$); see Section~\ref{sec:outline-incr}. We have also seen this technique of passing to a restriction already, in the proof of Proposition~\ref{prop:mdhj-from-dhj}.

When passing to a subspace, we will often not make make a distinction between $A$ and $A'$, writing $A$ for both.

\subsection{Probabilistic DHJ} \label{sec:pdhj} To show that a certain combinatorial object exists, the Probabilistic Method suggests choosing it a random. Could this work for the density Hales--Jewett theorem? A difficulty is that it is not immediately clear how one should choose a random combinatorial line. The most obvious way to choose a line over, say, $[3]^n$ is to simply choose a line template $\lambda \in [4]^n$ uniformly at random (taking care of the extremely unlikely chance of a degenerate template). Unfortunately this has no real chance of working because the uniform distribution on lines is not ``compatible with the uniform distribution on points.

Before clarifying this point, let us introduce some notation. We will be concerned with probability distributions on the set $\Omega^n$, where $\Omega$ is a finite alphabet. We will use letters such as $\distra$, $\distrb$ for generic such distributions, and if $A \subseteq \Omega^n$ we write $\distra(A) = \Pr_{x \sim \distra}[x \in A]$ for the $\distra$-density of $A$. We will often be concerned with product distributions on $\Omega^n$; if $\pi$ is a distribution on $\Omega$ we write $\pi^{\ot n}$ for the associated product distribution on $\Omega^n$. We reserve $\unif$ for the uniform distribution, writing $\unif_\Omega^{\ot n}$ for the uniform distribution on $\Omega^n$ and simply $\unif_k^{\ot n}$ when $\Omega = [k]$. We may abbreviate this further to simply $\unif_k$ or even $\unif$ if the context is clear.

Let us now return to the difficulty with choosing lines uniformly at random. To clarify, suppose we choose $\lambda \in [4]^n$ according to the uniform distribution $\unif_4^{\ot n}$. Then the distribution on the point $\chg{\lambda}{4}{1} \in [3]^n$ will be a product distribution $\prd^{\otimes n}$ in which symbol $1$ has probability $1/2$ and symbols $2$ and $3$ have probability $1/4$ each. However this distribution is very ``far from the uniform distribution on $[3]^n$, meaning that even if $\unif_3^{\ot n}(A) \geq \delta$, the probability that $\chg{\lambda}{4}{1} \in [3]^n$ may be a negligibly small function of $n$.

Even for other natural distributions on lines, it seems inevitable that $\chg{\lambda}{4}{1}$ will ``have more $1$'s than $2$'s or $3$'s, and similarly for $\chg{\lambda}{4}{2}$, $\chg{\lambda}{4}{3}$. To evade this difficulty we take inspiration from the probabilistic proof Sperner's theorem (see, e.g.,~\cite{Spe90})\noteryan{earliest citation I could find; note that Lubell's proof is a bit different} and introduce a new non-uniform, non-product distribution on points in $[k]^n$. We call this distribution the \emph{equal-slices} distribution and denote it by $\eqs{k}^n$. We will discuss $\eqs{2}^n$ in Section~\ref{sec:sperner} on Sperner's theorem, and its generalization $\eqs{k}^n$ in Section~\ref{sec:eqs}. For now we simply explain the name: Thinking of $\Omega = \{0,1\}$, one draws a string $x \in \{0,1\}^n$ from $\eqs{2}^n$ as follows: first choose an integer $s \in \{0, 1, \dots, n\}$ uniformly; then choose $x$ uniformly at random from the $s$th ``slice of the discrete cube, i.e., the set of strings with exactly $s$ many $1$'s. The more general $\eqs{k}^n$ involves choosing the count of each symbol from $[k]$ in a certain uniform manner, then drawing a uniformly random string with the chosen symbol counts.\noteryan{awkward}

As we will see, equal-slices is the natural distribution to use for a probabilistic version of DHJ($k$). There is a small catch, which is that a line template $\lambda \sim \eqs{k}^n$ has a very tiny chance of being being degenerate. To compensate for this, we introduce the very closely related distribution $\ens{k}^n$ (``equal-nondegenerate-slices), which is $\eqs{k}^n$ conditioned on $\lambda$ being a nondegenerate \emph{string} (i.e., having at least one of each symbol in $[k]$). For more details, see Section~\ref{sec:eqs}. We then prove the following two theorems: \begin{theorem} \label{thm:edhj} (Equal-slices density Hales--Jewett theorem.) For every positive integer $k$ and real $\delta>0$ there exists a positive integer $\edhj{k}{\delta}$ such that every $A \subseteq [k]^n$ with $\ens{k}^n(A) \geq \delta$ contains a combinatorial line, provided $n \geq \edhj{k}{\delta}$. \end{theorem} \begin{theorem} \label{thm:pdhj} (Probabilistic density Hales--Jewett theorem.) For every positive integer $k$ and real $\delta>0$ there exists a positive integer $\Pdhj{k}{\delta}$ and a positive real $\pdhj{k}{\delta}$ such that every $A \subseteq [k]^n$ with $\ens{k}^n(A) \geq \delta$satisfies \[ \Pr_{\lambda \sim \ens{k+1}^n}[\lambda \subseteq A] \geq \pdhj{k}{\delta}, \] provided $n \geq \Pdhj{k}{\delta}$. Here we are interpreting $\lambda$ as both a (nondegenerate) line template and as a line. \end{theorem} Theorem~\ref{thm:edhj} follows from the density Hales--Jewett theorem by playing around with probability distributions; see Proposition~\ref{prop:edhj-equiv-dhj}. Theorem~\ref{thm:pdhj} follows almost immediately from Theorem~\ref{thm:edhj}, thanks to some nice properties of the equal-nondegenerate-slices distribution; see Proposition~\ref{prop:pdhj-from-edhj}. Finally, the same two deductions also give us multidimensional versions; the ``equal-slices multidimensional density Hales--Jewett theorem (with parameter ``$\emdhj{k}{\delta}{d}$), and the following: \begin{theorem} \label{thm:pmdhj} (Probabilistic multidimensional density Hales--Jewett theorem.) For every real $\delta > 0$ and every pair of positive integers $k$ and $d$, there exists a positive integer $\Pmdhj{k}{\delta}{d}$ and a positive real $\pmdhj{k}{\delta}{d}$ such that every $A \subseteq [k]^n$ with $\ens{k}^n(A) \geq \delta$ satisfies \[ \Pr_{\sigma \sim \ens{k+d}^n}[\sigma \subseteq A] \geq \pmdhj{k}{\delta}{d}, \] provided $n \geq \Pmdhj{k}{\delta}{d}$. \end{theorem}