Higherk.tex

\section{Higher-k DHJ numbers}\label{higherk-sec}

For any $n$, $k$ let $c_{n,k}$ denote the cardinality of the largest subset of $[k]{}^n$ that does not contain a combinatorial line. When $k=3$, the quantity $c_{n,k} = c_n$ is studied in Sections \ref{dhj-lower-sec}, \ref{dhj-upper-sec}. The density Hales-Jewett theorem asserts that for any fixed $k$, $\lim_{n\rightarrow\infty} c_n/k^n = 0$ . We trivially have $c_{n,1} = 0$ for $n > 0$, and Sperner's theorem tells us that $$c_{n,2} = \binom{n}{\lfloor n/2 \rfloor}$$. Now we look at the opposite regime, in which $n$ is small and $k$ is large. We easily have $c_{1,k} = k-1$ together with the trivial bound $c_{n+1,k} \leq kc_{n,k}$. This implies that $$c_{n,k}\leq (k-1)k^{n-1}$$ for any $n\geq 1$. Let us call a pair $(n,k)$ with $n > 0$ \emph{saturated} if $c_{n,k}=(k-1)k^{n-1}$, thus there exists a line-free set with exactly one point omitted from every row and column. The question naturally arises, Which pairs $(n,k)$ are saturated? From the above discussion we see that $(1,k)$ is saturated for all $k \geq 1$, and $(n,1)$ is (rather trivially) saturated for all $n$. Sperner's theorem tells us that $(n,2)$ is saturated only for $n= 1, 2$. Note that if $(n,k)$ is unsaturated then $(n',k)$ will be unsaturated for all $n' > n$. A computer search has found the following $c_{n,k}$ values for different values of dimension $n$ and edgelength $k$. Several of these values reach the upper bound of $(k - 1)k^{n-1}$.

\begin{tabular}{|l|cccccc} $n\backslash k$ & 2& 3 & 4 & 5 & 6 & 7 \\ \hline 2 & 2 & 6 & 12 & 20 & 30 & 42\\ 3 & 3 & 18 & 48 & 100 & 180 & 294\\ 4 & 6 & 52 & 183 & 500 & 1051-1079 & 2058\\ 5 & 10 & 150 & 712-732 & 2500 & 6325-6480 & 14406 \end{tabular}

$(2,k)$ is saturated when $k$ is at least $1$. In dimension two the maximal set size is $k(k-1)$. This can be done by removing the diagonal values $11, 22, 33, \ldots, kk$. Since they are in disjoint lines this removal is minimal. The $k$ missing points are one per line and one per column. So their $y$-coordinates are a shuffle of their $x$-coordinates. There are $k!$ rearrangements of the numbers $1$ to $k$. The $k$ points include a point on the diagonal, so this shuffle is not a derangement. There are $k!/e$ derangements of the numbers $1$ to $k$, so $k!(1-1/e)$ optimal solutions. This number of optimal solutions is sequence A002467 from the Online Encyclopedia of Integer Sequences.

$(3,k)$ is saturated when $k>2$. Let $S$ be a latin square of side $k$ on the symbols $1…k$, with colour $i$ in position $(i,i)$ (This is not possible for $k=2$) Let axis one in $S$ correspond to coordinate $1$ in $[k]{}^3$, axis two to coordinate $2$ and interpret the colour in position $(i,j)$ as the third coordinate. Delete the points so defined. The line with three wild cards has now been removed. A line with two wildcards will be missing the point corresponding to the diagonal in $S$. A line with a single wildcard will be missing a point corresponding to an off diagonal point in $S$.

$(n,k)$ is saturated when all prime divisors of $k$ are at least $n$. First consider the case when $k$ is prime and at least $n$: Delete those points whose coordinates add up to a multiple of $k$. Every combinatorial line has one point deleted, except for the major diagonal of $n=k$, which has all points deleted. Now consider for instance the case $(n,k) = (4,35)$. Select one value modulo $35$ and eliminate it. Combinatorial lines with one, two, three or four moving coordinates will realize all values modulo $35$ as one, two, three, or four are units modulo $35$, thus $(4,35)$ is saturated. The same argument tells us that $(n,k)$ is saturated when all prime divisors of $k$ are at least $n$. On the other hand, computer data shows that $(4,4)$ and $(4,6)$ are not saturated.

\subsection{Failure of Hyper-optimistic conjecture}\label{HOCfailure} Let $\overline{c}^\mu_{n,4}$ be the largest subset of the tetrahedral grid: $$\{(a,b,c,d)\in\mathbb{Z}^4_+ : a+b+c+d = n\}$$ which contains no tetrahedrons $(a + r,b,c,d)$,$(a,b + r,c,d)$,$(a,b,c + r,d)$,$(a,b,c,d + r)$ with $r > 0$; call such sets tetrahedron-free. The first few values, for $n$ from 0 to 7, were found by an integer programming routine, and are given in Figure \ref{Fujimura4}.

\begin{figure}[tb]\centerline{ \begin{tabular}{lllllllll}

                      n & 0 & 1 & 2 & 3  & 4  & 5  & 6  & 7 \\

$\overline{c}^\mu_{n,4}$ & 1 & 3 & 7 & 14 & 24 & 37 & 55 & 78 \end{tabular} } \label{Fujimura4} \caption{Fujimura numbers $\overline{c}^\mu_{n,4}$} \end{figure}

Recall the 'hyper-optimistic' Conjecture \ref{hoc} that the weighted sum of the points in any combinatorial line-free set is at most $\overline{c}^\mu_{n,4}$. The following example with $n=2$ and $k=4$ has a weighted sum of $7.5$, and therefore disproves the conjecture for these values of $n$ and $k$. (Note that for all odd numbers including the case $k=3$, which is at the centre of most of Polymath's interest, is still open.

$$\{(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 4)\}$$

The above counterexample can be extended to all even numbers greater than 2 as follows. One takes one element on the diagonal say $(n,n)$ then one can take $(a,a+1)$ for all $n-1$ values 0 through $n-2$ and $(n-1,0)$ this will block all combinatorial lines and it has weight (n+1)/2. The complement of this thus line free. Its weight is greater than any set of slices. For each such set must contain at least one diagonal blocking point and $n-1$ other blocking points if it has two or more diagonal blocking points the complement will be less than the above set(there must be at least $n$ blocking points so 2 or more diagonal points increase the weight by $1/2$ and pushes it over the limit constructed above. If it has one then because of parity reasons it must have an additional point (there are an odd number of coordinates to take care of and since if $(a,b)$ is in the blocking set $(b,a)$ must be as well, coordinates must be blocked by pairs there is one left over which requires an addition point or an addition point of the form $(a,a)$ which makes the line free set lower than the above construction. The HOC is known to be true for 2 and for even numbers greater than 2 by the above it is false.