Dhj-lown.tex

\section{Upper bounds for the $k=3$ density Hales-Jewett problem}\label{dhj-upper-sec}

To finish the proof of Theorem \ref{dhj-upper} we need to supply the indicated upper bounds for $c_{n,3}$ for $n=0,\ldots,6$.

It is clear that $c_{0,3} = 1$ and $c_{1,3} = 2$. By subdividing a line-free set into three parallel slices we obtain the bound $$ c_{n+1,3} \leq 3 c_{n,3}$$ for all $n$. This is already enough to get the correct upper bounds $c_{2,3} \leq 6$ and $c_{3,3} \leq 18$, and also allows us to deduce the upper bound $c_{6,3} \leq 450$ from $c_{5,3} \leq 150$. So the remaining tasks are to establish the upper bounds \begin{equation}\label{c43} c_{4,3} \leq 52 \end{equation} and \begin{equation}\label{c53} c_{5,3} \leq 150. \end{equation}

In order to establish \eqref{c53}, we will rely on \eqref{c43}, together with a classification of those line-free sets in $[3]^4$ of size close to the maximal number $52$. Similarly, to establish \eqref{c43}, we will need the bound $c_{3,3} \leq 18$, together with a classification of those line-sets in $[3]^3$ of size close to the maximal number $18$. Finally, to achieve the latter aim one needs to classify the line-free subsets of $[3]^2$ with exactly $c_{2,3}=6$ elements.

We begin with the $n=2$ theory.

\begin{lemma}[$n=2$ extremals]\label{2d-ext} There are exactly four line-free subsets of $[3]^2$ of cardinality $6$: \begin{itemize} \item The set $x := A_{B_{2,2}} = \{12, 13, 21, 22, 31, 33\}$; \item The set $y := A_{B_{2,1}} = \{11, 12, 21, 23, 32, 33\}$; \item The set $z := A_{B_{2,0}} = \{11, 13, 22, 23, 31, 32\}$; \item The set $w := \{12, 13, 21, 23, 31, 32\}$. \end{itemize} \end{lemma}

\begin{proof} A line-free subset of $[3]^2$ must have exactly two elements in every row and column. The claim then follows by brute force search. \end{proof}

Now we turn to the $n=3$ theory. We can slice $[3]^3$ as the union of three slices $1**$, $2**$, $3**$, each of which are identified with $[3]^2$ in the obvious manner. Thus every subset $A$ in $[3]^3$ can be viewed as three subsets $A_1, A_2, A_3$ of $[3]^2$ stacked together; if $A$ is line-free then $A_1,A_2,A_3$ are necessarily line-free, but the converse is not true. We write $A = A_1 A_2 A_3$, thus for instance $xyz$ is the set $$ xyz = \{112,113,121,122,131,133\} \cup \{211,212,221,223,232,233\} \cup \{311,313,322,323,331,332\}.$$ Observe that $$ A_{B_{0,3}} = xyz; \quad A_{B_{1,3}} = yzx; \quad A_{B_{2,3}} = zxy.$$

\begin{lemma}[$n=3$ extremals]\label{Lemma1} The only $18$-element line-free subset of $[3]^3$ is $xyz$. The only $17$-element line-free subsets of $[3]^3$ are formed by removing a point from $xyz$, or by removing either $111$, $222$, or $333$ from $yzx$ or $zxy$. \end{lemma}

\begin{proof} We prove the second claim. As $17 = 6 + 6 + 5$, and $c_{2,3} = 6$, at least two of the slices of a $17$-element line-free set must be from $x$, $y$, $z$, $w$, with the third slice having $5$ points. If two of the slices are identical, the last slice must lie in the complement and thus has at most $3$ points, a contradiction. If one of the slices is a $w$, then the $5$-point slice consists of the complement of the other two slices and thus contains a diagonal, contradiction. By symmetry we may now assume that two of the slices are $x$ and $y$, which force the last slice to be $z$ with one point removed. Now one sees that the slices must be in the order $xyz$, $yzx$, or $zxy$, because any other combination has too many lines that need to be removed. The sets $yzx$, $zxy$ contain the diagonal $\{111,222,333\}$ and so one additional point needs to be removed.

The first claim follows by a similar argument to the second. \end{proof}

Now we turn to the $n=4$ theory.

\begin{lemma} $c_{4,3} \leq 52$. \end{lemma}

\begin{proof} Let $A$ be a line-free set in $[3]^4$, and split $A=A_1A_2A_3$ for $A_1,A_2,A_3 \in [3]^3$ as in the $n=3$ theory. If at least two of the slices $A_1,A_2,A_3$ are of cardinality $18$, then by Lemma \ref{Lemma1} they are of the form $xyz$, and so the third slice then lies in the complement and has at most six points, leading to an inferior bound of $18+18+6 = 42$. Thus at most one of the slices can have cardinality $18$, leading to the bound $18+17+17=52$. \end{proof}

Now we classify extremisers. Observe that we have the following (equivalent) $52$-point line-free sets, which were implicitly constructed in the previous section;

\begin{itemize} \item $E_0 := A_{B_{0,4}}\backslash\{1111,2222\}$; \item $E_1 := A_{B_{1,4}}\backslash\{2222,3333\}$; \item $E_2 := A_{B_{2,4}}\backslash\{1111,3333\}$. \end{itemize}

\begin{lemma}\label{Lemma2}\ \begin{itemize} \item The only $52$-element line-free sets in $[3]^4$ are $E_0$, $E_1$, $E_2$. \item The only $51$-element line-free sets in $[3]^4$ are formed by removing a point from $E_0$, $E_1$ or $E_2$. \item The only $50$-element line-free sets in $[3]^4$ are formed by removing two points from $E_0$, $E_1$ or $E_2$ OR is equal to one of the three permutations of the set $X := \Gamma_{3,1,0} \cup \Gamma_{3,0,1} \cup \Gamma_{2,2,0} \cup \Gamma_{2,0,2} \cup \Gamma_{1,1,2} \cup \Gamma_{1,2,1} \cup \Gamma_{0,2,2}$. \end{itemize} \end{lemma}

\begin{proof} We will just prove the third claim, which is the hardest; the first two claims follow from the same argument (and can in fact be deduced directly from the third claim).

It suffices to show that every $50$-point line-free set is either contained in the $54$-point set $A_{B_{j,4}}$ for some $j=0,1,2$, or is some permutation of the set $X$. Indeed, if a $50$-point line-free set is contained in, say, $A_{B_{0,4}}$, then it cannot contain $2222$, since otherwise it must omit one point from each of the four pairs formed from $\{2333, 2111\}$ by permuting the indices, and must also omit one of $\{1111, 1222, 1333\}$, leading to at most $49$ points in all; similarly, it cannot contain $1111$, and so omits the entire diagonal $\{1111,2222,3333\}$, with two more points to be omitted. By symmetry we see the same argument works when $A_{B_{0,4}}$ is replaced by one of the other $A_{B_{j,4}}$.

Next, observe that every three-dimensional slice of a line-free set can have at most $c_{3,3} = 18$ points; thus when one partitions a $50$-point line-free set into three such slices, it must divide either as $18+16+16$, $18+17+15$, $17+17+16$, or some permutation of these. Suppose that we can slice the set into two slices of $17$ points and one slice of $16$ points. By the various symmetries, we may assume that the $1***$ slice and $2***$ slices have $17$ points, and the $3***$ slice has $16$ points. By Lemma \ref{Lemma1}, the $1$-slice is $\{1\}\times D_{3,j}$ with one point removed, and the $2$-slice is $\{2\}\times D_{3,k}$ with one point removed, for some $j,k \in \{0,1,2\}$. If $j=k$, then the $1$-slice and $2$-slice have at least $15$ points in common, so the $3$-slice can have at most $27 - 15 = 12$ points, a contradiction. If $jk = 01$, $12$, or $20$, then observe that from Lemma \ref{Lemma1} the $*1**$, $*2**$, $*3**$ slices cannot equal a $17$-point or $18$-point line-free set, so each have at most $16$ points, leading to only $48$ points in all, a contradiction. Thus we must have $jk = 10$, $21$, or $02$.

First suppose that $jk=02$. Then by Lemma \ref{Lemma1}, the $2***$ slice contains the nine points formed from $\{2211, 2322, 2331\}$ and permuting the last three indices, while the $1***$ slice contains at least eight of the nine points formed from $\{1211, 1322, 1311\}$ and permuting the last three indices. Thus the $3***$ slice can contain at most one of the nine points formed from $\{3211, 3322, 3311\}$ and permuting the last three indices. If it does contain one of these points, say $3211$, then it must omit one point from each of the four pairs $\{3222, 3233\}$, $\{3212, 3213\}$, $\{3221, 3231\}$, $\{3111, 3311\}$, leading to at most $15$ points on this slice, a contradiction. So the $3***$ slice must omit all nine points, and is therefore contained in $\{3\}\times D_{3,1}$, and so the $50$-point set is contained in $D_{4,1}$, and we are done by the discussion at the beginning of the proof.

The case $jk=10$ is similar to the $jk=02$ case (indeed one can get from one case to the other by swapping the $1$ and $2$ indices). Now suppose instead that $jk=12$. Then by Lemma \ref{Lemma1}, the $1***$ slice contains the six points from permuting the last three indices of $1123$, and similarly the $2***$ slice contains the six points from permuting the last three indices of $2123$. Thus the $3***$ slice must avoid all six points formed by permuting the last three indices of $3123$. Similarly, as $1133$ lies in the $1***$ slice and $2233$ lies in the $2***$ slice, $3333$ must be avoided in the $3***$ slice.

Now we claim that $3111$ must be avoided also; for if $3111$ was in the set, then one point from each of the six pairs formed from $\{3311, 3211\}$, $\{3331, 3221\}$ and permuting the last three indices must lie outside the $3***$ slice, which reduces the size of that slice to at most $27 - 6 - 1 - 6 = 14$, which is too small. Similarly, $3222$ must be avoided, which puts the $3***$ slice inside $\{3\}\times D_3$ and then places the $50$-point set inside $D_4$, and we are done by the discussion at the beginning of the proof.

We have handled the case in which at least one of the slicings of the $50$-point set is of the form $50=17+17+16$. The only remaining case is when all slicings of the $50$-point set are of the form $18+16+16$ or $18+17+15$ (or a permutation thereof). So each slicing includes an $18$-point slice. By the symmetries of the situation, we may assume that the $1***$ slice has $18$ points, and thus by Lemma \ref{Lemma1} takes the form $\{1\}\times D_3$. Inspecting the $*1**$, $*2**$, $*3**$ slices, we then see (from Lemma \ref{Lemma1}) that only the $*1**$ slice can have $18$ points; since we are assuming that this slicing is some permutation of $18+17+15$ or $18+16+16$, we conclude that the $*1**$ slice must have exactly $18$ points, and is thus described precisely by Lemma \ref{Lemma1}. Similarly for the $**1*$ and $***1$ slices. Indeed, by Lemma \ref{Lemma1}, we see that the 50-point set must agree exactly with $D_{4,1}$ on any of these slices. In particular, there are exactly six points of the 50-point set in the remaining portion $\{2,3\}^4$ of the cube.

Suppose that $3333$ was in the set; then since all permutations of $3311$, $3331$ are known to lie in the set, then $3322$, $3332$ must lie outside the set. Also, as $1222$ lies in the set, at least one of $2222$, $3222$ lie outside the set. This leaves only $5$ points in $\{2,3\}^4$, a contradiction. Thus $3333$ lies outside the set; similarly $2222$ lies outside the set.

Let $a$ be the number of points in the $50$-point set which are some permutation of $2233$, thus $0\leq a\leq 6$. If $a=0$ then the set lies in $D_{4,1}$ and we are done. If $a=6$ then the set is exactly $X$ and we are done. Now suppose $a=1$. By symmetry we may assume that $2233$ lies in the set. Then (since $2133, 1233, 2231, 2213$ are known to lie in the set) $2333, 3233, 2223, 2232$ lie outside the set, which leaves at most $5$ points inside $\{2,3\}^4$, a contradiction. A similar argument holds if $a=2,3$.

The remaining case is when $a=4,5$. Then one of the three pairs $\{2233, 3322\}$, $\{2323, 3232\}$, $\{2332, 3223\}$ lie in the set. By symmetry we may assume that $\{2233, 3322\}$ lie in the set. Then by arguing as before we see that all eight points formed by permuting $2333$ or $3222$ lie outside the set, leading to at most 5 points inside $\{2,3\}^4$, a contradiction. \end{proof}

Finally, we turn to the $n=5$ theory. Our goal is to show that $c_{5,3} \leq 150$. Accordingly, suppose for contradiction that we can find a line-free subset $A$ of $[3]^5$ of cardinality $|A|=151$. We will now prove a series of facts about $A$ which will eventually give the desired contradiction.

\begin{lemma} $A$ is not contained inside $A_{B_{j,5}}$ for any $j=0,1,2$. \end{lemma}

\begin{proof} Suppose for contradiction that $A \subset A_{B_{j,5}}$ for some $j$. By symmetry we may take $j=0$. The set $A_{B_{0,5}}$ has $162$ points. By looking at the triplets $\{10000, 11110, 12220\}$ and cyclic permutations we must lose $5$ points; similarly from the triplets $\{20000,22220, 21110\}$ and cyclic permutations. Finally from $\{11000,11111,11222\}$ and $\{22000,22222,22111\}$ we lose two more points. Since $162-5-5-2=150$, we obtain the desired contradiction. \end{proof}

Observe that every slice of $A$ contains at most $c_{4,3}=52$ points, and hence every slice of $A$ contains at least $151-52-52=47$ points.

\begin{lemma} \label{NoTwo51} $A$ cannot have two parallel $[3]{}^4$ slices, each of which contain at least $51$ points. \end{lemma}

\begin{proof} Suppose not. By symmetry, we may assume that the $1****$ and $2****$ slices have at least $51$ points. Meanwhile, the $3****$ slice has at least $47$ points as discussed above.

By Lemma \ref{Lemma2}, the $1****$ slice takes the form $\{1\}\times D_{4,j}$ for some $j = 0,1,2$ with the diagonal $\{11111,12222,13333\}$ and possibly one more point removed, and similarly the $2****$ slice takes the form $\{2\}\times D_{4,k}$ for some $k = 0,1,2$ with the diagonal $\{21111,22222,23333\}$ and possibly one more point removed.

Suppose first that $j=k$. Then the $1$-slice and $2$-slice have at least $50$ points in common, leaving at most $31$ points for the $3$-slice, a contradiction. Next, suppose that $jk=01$. Then observe that the $*i***$ slice cannot look like any of the configurations in Lemma \ref{Lemma2} and so must have at most $50$ points for $i=1,2,3$, leading to $150$ points in all, a contradiction. Similarly if $jk=12$ or $20$. Thus we must have $jk$ equal to $10$, $21$, or $02$.

Let's suppose first that $jk=10$. The first slice then is equal to $\{1\}\times D_{4,1}$ with the diagonal and possibly one more point removed, while the second slice is equal to $\{2\}\times D_{4,0}$ with the diagonal and possibly one more point removed. Superimposing these slices, we thus see that the third slice is contained in $\{3\}\times D_{4,2}$ except possibly for two additional points, together with the one point $32222$ of the diagonal that lies outside of $\{3\}\times D_{4,2}$.

The lines $x12xx, x13xx$ (plus permutations of the last four digits) must each contain one point outside the set. The first two slices can only absorb two of these, and so at least $14$ of the $16$ points formed by permuting the last four digits of $31233$, $31333$ must lie outside the set. These points all lie in $\{3\}\times D_{4,2}$, and so the $3****$ slice can have at most $| D_{4,2}| - 14 + 3 = 43$ points, a contradiction.

The case $jk=02$ is similar to the case $jk=10$ (indeed one can obtain one from the other by swapping $1$ and $2$). Now we turn to the case $jk=21$. Arguing as before we see that the third slice is contained in $\{3\}\times D_4$ except possibly for two points, together with $33333$.

If $33333$ was in the set, then each of the lines $xx333$, $xxx33$ (and permutations of the last four digits) must have a point missing from the first two slices, which cannot be absorbed by the two points we are permitted to remove; thus $33333$ is not in the set. For similar reasons, $33331$ is not in the set, as can be seen by looking at $xxx31$ and permutations of the last four digits. Indeed, any string containing four threes does not lie in the set; this means that at least $8$ points are missing from $\{3\}\times D_{4}$, leaving only at most $46$ points inside that set. Furthermore, any point in the $3****$ slice outside of $\{3\}\times D_{4}$ can only be created by removing a point from the first two slices, so the total cardinality is at most $46 + 52 + 52 = 150$, a contradiction. \end{proof}

\begin{remark} This already gives the bound $c_{5,3} \leq 52+50+50=152$, but of course we wish to do better than this. \end{remark}

\begin{lemma}\label{151-49} $A$ has a slice $j****$ with $j=1,2,3$ that has at most $49$ points. \end{lemma}

\begin{proof} Suppose not, thus all three slices of $A$ has at least $50$ points. Using earlier notation, we split subsets of $[3]{}^4$ into nine subsets of $[3]{}^2$. So we think of $x,y,z,a,b$ and $c$ as subsets of a square. By Lemma \ref{Lemma2}, each slice is one of the following: \begin{itemize} \item $E_0 = y'zx,zx'y,xyz$ (with one or two points removed) \item $E_1 = xyz,yz'x,zxy'$ (with one or two points removed) \item $E_2 = z'xy,xyz,yzx'$ (with one or two points removed) \item $X = xyz,ybw,zwc$ \item $Y = axw,xyz,wzc$ \item $Z = awx,wby,xyz$ \end{itemize} where $a$, $b$ and $c$ have four points each: $a = \{2,3\}^2$, $b = \{1,3\}^2$ and $c = \{1,2\}^2$. $x'$, $y'$ and $z'$ are subsets of $x$, $y$ and $z$ respectively, and have five points each.

Suppose all three slices are subsets of $E_j$. We can remove at most five points from the full set of three $E_j$. Consider columns $2,3,4,6,7,8$. At most two of these columns contain $xyz$, so one point must be removed from the other four. This uses up all but one of the removals. So the slices must be $E_2$, $E_1$, $E_0$ or a cyclic permutation of that. Then the cube, which contains the first square of slice $1$; the fifth square of slice $2$; and the ninth square of slice $3$, contains three copies of the same square. It takes more than one point removed to remove all lines from that cube. So we can't have all three slices subsets of $E_j$.

Suppose one slice is $X$, $Y$ or $Z$, and two others are subsets of $E_j$. We can remove at most three points from the two $E_j$. By symmetry, suppose one slice is $X$. Consider columns $2$, $3$, $4$ and $7$. They must be cyclic permutations of $x$, $y$, $z$, and two of them are not $xyz$, so must lose a point. Columns $6$ and $8$ must both lose a point, and we only have $150$ points left. So if one slice is $X$, $Y$ or $Z$, the full set contains a line.

Suppose two slices are from $X$, $Y$ and $Z$, and the other is a subset of $E_j$. By symmetry, suppose two slices are $X$ and $Y$. Columns $3$, $6$, $7$ and $8$ all contain $w$, and therefore at most $16$ points each. Columns $1$, $5$ and $9$ contain $a$, $b$, or $c$, and therefore at most $16$ points. So the total number of points is at most $7 \times 16+2 \times 18 = 148 < 151$, a contradiction. \end{proof}

This, combined with Lemma \ref{NoTwo51}, gives

\begin{corollary}\label{525049} Any three parallel slices of $A$ must have cardinality $52, 50, 49$ (or a permutation thereof). \end{corollary}

Note that this argument gives the bound $c_{5,3} \leq 151$.

\begin{lemma} \label{151NoX} No slice $j****$ of $A$ is of the form $X$, where $X$ was defined in Lemma \ref{Lemma2}. \end{lemma}

\begin{proof} Suppose one slice is $X$; then by the previous discussion one of the parallel slices has $52$ points and is thus of the form $E_j$ for some $j=0,1,2$, by Lemma \ref{Lemma2}.

Suppose that $X$ is the first slice $1****$. We have $X = xyz\ ybw \ zwc$. Label the other rows with letters from the alphabet, thus $$ A = \begin{pmatrix} xyz & ybw & zwc \\ mno & pqr & stu \\def & ghi & jkl \end{pmatrix}$$ Reslice the array into a left nine, middle nine and right nine. One of these squares contains $52$ points, and it can only be the left nine. One of its three columns contains $18$ points, and it can only be its left-hand column, $xmd$. So $m=y$ and $d=z$. But none of the $E_j$ begins with $y$ or $z$, which is a contradiction. So $X$ is not in the first row.

So $X$ is in the second or third row. By symmetry, suppose it is in the second row, so that $A$ has the following shape: $$ A = \begin{pmatrix} def & ghi & jkl \\xyz & ybw & zwc \\ mno & pqr & stu \end{pmatrix}$$ Again, the left-hand nine must contain $52$ points, so it is $E_2$. Now, to get $52$ points in any row, the first row must be $E_2$. Then the only way to have $50$ points in the middle or right-hand nine is if the middle nine is $X$: $$ A = \begin{pmatrix} z'xy & xyz & yzx' \\xyz & ybw & zwc \\ yzx' & zwc & stu \end{pmatrix}$$ In the seventh column, $s$ contains $5$ points and in the eighth column, $t$ contains $4$ points. The final row can now contain at most $48$ points, contradicting Corollary \ref{525049}.

A similar argument is possible if $X$ is in the third row; or if $X$ is replaced by $Y$ or $Z$. Thus, given any decomposition of $A$ into three parallel slices, one slice is a $52$-point set $E_j$ and another slice is $50$ points contained in $E_k$. \end{proof}

Now we can obtain the desired contradiction:

\begin{lemma} There is no $151$-point line-free set $A \subset [3]^5$. \end{lemma}

\begin{proof} Assume by symmetry that the first row contains $52$ points and the second row contains $50$. If $E_1$ is in the first row, then the second row must be contained in $E_0$: $$ A = \begin{pmatrix} xyz & yz'x & zxy' \\ y'zx & zx'y & xyz \\ def & ghi & jkl\end{pmatrix}$$ But then none of the left nine, middle nine or right nine can contain $52$ points, which contradicts Corollary \ref{525049}. Suppose the first row is $E_0$. Then the second row is contained in $E_2$, otherwise the cubes formed from the nine columns of the diagram would need to remove too many points: $$ A = \begin{pmatrix} y'zx & zx'y & xyz \\ z'xy & xyz & yzx' \\ def & ghi & jkl \end{pmatrix}.$$ But then neither the left nine, middle nine nor right nine contain $52$ points. So the first row contains $E_2$, and the second row is contained in $E_1$. Two points may be removed from the second row of this diagram: $$ A = \begin{pmatrix} z'xy & xyz & yzx' \\ xyz & yz'x & zxy' \\ def & ghi & jkl \end{pmatrix}.$$ Slice it into the left nine, middle nine and right nine. Two of them are contained in $E_j$ so at least two of $def$, $ghi$, and $jkl$ are contained in the corresponding slice of $E_0$. Slice along a different axis, and at least two of $dgj$, $ehk$, $fil$ are contained in the corresponding slice of $E_0$. So eight of the nine squares in the bottom row are contained in the corresponding square of $E_0$. Indeed, slice along other axes, and all points except one are contained within $E_0$. This point is the intersection of all the $49$-point slices. So, if there is a $151$-point solution, then after removal of the specified point, there is a $150$-point solution, within $D_{5,j}$, whose slices in each direction are $52+50+48$. $$ A = \begin{pmatrix} z'xy & xyz & yzx' \\ xyz & yz'x & zxy' \\ y'zx & zx'y & xyz \end{pmatrix}$$ One point must be lost from columns $3$, $6$, $7$ and $8$, and four more from the major diagonal $z'z'z$. That leaves $148$ points instead of $150$. So the $150$-point solution does not exist with $52+50+48$ slices; so the $151$ point solution does not exist. \end{proof}