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 ^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 ^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 ( \cup \{\wild\})^n$ corresponds to the line $\{\chg{\lambda}{\wild}{1}, \chg{\lambda}{\wild}{2}, \chg{\lambda}{\wild}{3}\} \subseteq ^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 $ \cup \{\wild_1, \wild_2\}$. A string in $( \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{.^{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 ^{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 ^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 $^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, $^n$ is to simply choose a line template $\lambda \in ^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 ^n$ according to the uniform distribution $\unif_4^{\ot n}$. Then the distribution on the point $\chg{\lambda}{4}{1} \in ^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 $^n$, meaning that even if $\unif_3^{\ot n}(A) \geq \delta$, the probability that $\chg{\lambda}{4}{1} \in ^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}