Moser.tex

\section{Upper bounds for the $k=3$ Moser problem in small dimensions}\label{moser-upper-sec}

In this section we finish the proof of Theorem \ref{moser} by obtaining the upper bounds on $c'_{n,3}$ for $n \leq 6$.

\subsection{Statistics, densities and slices}

Our analysis will revolve around various \emph{statistics} of Moser sets $A \subset [3]^n$, their associated \emph{densities}, and the behavior of such statistics and densities with respect to the operation of passing from the cube $[3]^n$ to various \emph{slices} of that cube.

\begin{definition}[Statistics and densities] Let $A \subset [3]^n$ be a set. For any $0 \leq i \leq n$, set $a_i(A) := |A \cap S_{n-i,n}|$; thus we have $$ 0 \leq a_i(A) \leq |S_{n-i,n}| = \binom{n}{i} 2^{n-i}$$ for $0 \leq i \leq n$ and $$ a_0(A) + \ldots + a_n(A) = |A|.$$ We refer to the vector $(a_0(A),\ldots,a_n(A))$ as the \emph{statistics} of $A$. We define the $i^{th}$ \emph{density} $\alpha_i(A)$ to be the quantity $$ \alpha_i(A) := \frac{a_i(A) }{\binom{n}{i} 2^{n-i}},$$ thus $0 \leq \alpha_i(A) \leq 1$ and $$ |A| = \sum_{i=0}^n \binom{n}{i} 2^{n-i} a_i(A).$$ \end{definition}

\begin{example}\label{2mos} Let $n=2$ and $A$ be the Moser set $A := \{ 12, 13, 21, 23, 31, 32 \}$. Then the statistics $(a_0(A), a_1(A), a_2(A))$ of $A$ are $(2,4,0)$, and the densities $(\alpha_0(A), \alpha_1(A), \alpha_2(A))$ are $(\frac{1}{2}, 1, 0)$. \textbf{Include picture here? with colours?} \end{example}

When working with small values of $n$, it will be convenient to write $a(A)$, $b(A)$, $c(A)$, etc. for $a_0(A)$, $a_1(A)$, $a_2(A)$, etc., and similarly write $\alpha(A), \beta(A), \gamma(A)$, etc. for $\alpha_0(A)$, $\alpha_1(A)$, $\alpha_2(A)$, etc. Thus for instance in Example \ref{2mos} we have $b(A) = 4$ and $\alpha(A) = \frac{1}{2}$.

\begin{definition}[Subspace statistics and densities] If $V$ is a $k$-dimensional geometric subspace of $[3]^n$, then we have a map $\phi_V: [3]^k \to [3]^n$ from the $k$-dimensional cube to the $n$-dimensional cube. If $A \subset [3]^n$ is a set and $0 \leq i \leq k$, we write $a_i(V,A)$ for $a_i(\phi_V^{-1}(A))$ and $\alpha_i(V,A)$ for $\alpha_i(\phi_V^{-1}(A))$. If the set $A$ is clear from context, we abbreviate $a_i(V,A)$ as $a_i(V)$ and $\alpha_i(V,A)$ as $\alpha_i(V)$. \end{definition}

For our problem, a particularly important type of subspace of $[3]^n$ will be the \emph{slices} formed by fixing one coordinate and letting the other $n-1$ coordinates vary. We will denote this by a single string in which the $n-1$ varying coordinates are denoted by asterisks. For instance, in $[3]^2$, $1*$ denotes the slice $1*=\{11,12,13\}$, $*2$ denotes the slice $*2=\{12,22,32\}$, etc.; similarly, in $[3]^3$, $1**$ is the slice $\{111, 112, 113, 121, 122, 123, 131, 132, 133\}$, etc. We call a slice a \emph{centre slice} if the fixed coordinate is $2$ and a \emph{side slice} if it is $1$ or $3$.

\begin{example} We continue Example \ref{2mos}. Then the statistics of the side slice $1*$ are $(a(1*),b(1*)) = (1,1)$, while the statistics of the centre slice $2*$ are $(a(2*),b(2*))=(2,0)$. The corresponding densities are $(\alpha(1*),\beta(1*)) = (1/2,1)$ and $(\alpha(2*),\beta(2*))=(1,0)$. \end{example}

A simple double counting argument gives the following useful identity:

\begin{lemma}[Double counting identity]\label{dci} Let $A \subset [3]^n$ and $0 \leq i \leq n-1$. Then we have $$ \frac{1}{n-i-1} \sum_{V \hbox{ a side slice}} a_{i+1}(V) = \frac{1}{i+1} \sum_{W \hbox{ a centre slice}} a_i(W) = a_{i+1}(A)$$ where $V$ ranges over the $2n$ side slices of $[3]^n$, and $W$ ranges over the $n$ centre slices. In other words, the average value of $\alpha_{i+1}(V)$ for side slices $V$ equals the average value of $\alpha_i(W)$ for centre slices $W$, which is in turn equal to $\alpha_{i+1}(A)$. \end{lemma}

Indeed, this lemma follows from the observation that every string in $A \cap S_{n-i-1,n}$ belongs to $i+1$ centre slices $W$ (and contributes to $a_i(W)$) and to $n-i-1$ side slices $V$ (and contributes to $a_{i+1}(V)$). One can also view this lemma probabilistically, as the assertion that there are three equivalent ways to generate a random string of length $n$:

\begin{itemize} \item Pick a side slice $V$ at random, and randomly fill in the wildcards in such a way that $i+1$ of the wildcards are $2$'s (i.e. using an element of $S_{n-i-2,n-1}$). \item Pick a centre slice $V$ at random, and randomly fill in the wildcards in such a way that $i$ of the wildcards are $2$'s (i.e. using an element of $S_{n-i-1,n-1}$). \item Randomly choose an element of $S_{n-i-1,n}$. \end{itemize}

\begin{example} We continue Example \ref{2mos}. The average value of $\beta$ for side slices is equal to the average value of $\alpha$ for centre slices, which is equal to $\beta(A) = 1$. \end{example}

Another very useful fact (essentially due to \cite{chvatal2}) is that linear inequalities for statistics of Moser sets at one dimension propagate to linear inequalities in higher dimensions:

\begin{lemma}[Propagation lemma]\label{prop} Let $n \geq 1$ be an integer. Suppose one has a linear inequality of the form \begin{equation}\label{alphav}

\sum_{i=0}^n v_i \alpha_i(A) \leq s

\end{equation} for all Moser sets $A \subset [3]^n$ and some real numbers $v_0,\ldots,v_n,s$. Then we also have the linear inequality $$ \sum_{i=0}^n v_i \alpha_{qi+r}(A) \leq s$$ whenever $q \geq 1$, $r \geq 0$, $N \geq nq+r$ are integers and $A \subset [3]^N$ is a Moser set. \end{lemma}

\begin{proof} We run a probabilistic argument (one could of course also use a double counting argument instead). Let $n,v_0,\ldots,v_n,s,q,r,N,A$ be as in the lemma. Let $V$ be a random $n$-dimensional geometric subspace of $[3]^N$, created in the following fashion: \begin{itemize} \item Pick $n$ wildcards $x_1,\ldots,x_n$ to run independently from $1$ to $3$. We also introduce dual wildcards $\overline{x_1},\ldots,\overline{x_n}$; each $\overline{x_j}$ will take the value $4-x_j$. \item We randomly subdivide the $N$ coordinates into $n$ groups of $q$ coordinates, plus a remaining group of $N-nq$ ``fixed coordinates. \item For each coordinate in the $j^{th}$ group of $q$ coordinates for $1 \leq j \leq n$, we randomly assign either a $x_j$ or $\overline{x_j}$. \item For each coordinate in the $N-nq$ fixed coordinates, we randomly assign a digit $1,2,3$, but condition on the event that exactly $r$ of the digits are equal to $2$ (i.e. we use a random element of $S_{N-nq-r,N-nq}$). \item Let $V$ be the subspace created by allowing $x_1,\ldots,x_n$ to run independently from $1$ to $3$, and $\overline{x_j}$ to take the value $4-x_j$. \end{itemize}

For instance, if $n=2, q=2, r=1, N=6$, then a typical subspace $V$ generated in this fashion is $$ 2x_1\overline{x_2}3x_2x_1 = \{ 213311, 212321, 211331, 223312, 222322, 221332, 233313, 232323, 231333\}.$$ Observe from that the following two ways to generate a random element of $[3]^N$ are equivalent:

\begin{itemize} \item Pick $V$ randomly as above, and then assign $(x_1,\ldots,x_n)$ randomly from $S_{n-i,n}$. Assign $4-x_j$ to $\overline{x_j}$ for all $1 \leq j \leq n$. \item Pick a random string in $S_{N-qi-r,N}$. \end{itemize}

Indeed, both random variables are invariant under the symmetries of the cube, and both random variables always pick out strings in $S_{N-qi-r,N}$, and the claim follows. As a consequence, we see that the expectation of $\alpha_i(V)$ (as $V$ ranges over the recipe described above) is equal to $\alpha_{qi+r}(A)$. On the other hand, from \eqref{alphav} we have $$ \sum_{i=0}^n v_i \alpha_i(V) \leq s$$ for all such $V$; taking expectations over $V$, we obtain the claim. \end{proof}

In view of Lemma \ref{prop}, it is of interest to locate linear inequalities relating the densities $\alpha_i(A)$, or (equivalently) the statistics $a_i(A)$. For this, it is convenient to introduce the following notation.

\begin{definition} Let $n \geq 1$ be an integer. \begin{itemize} \item A vector $(a_0,\ldots,a_n)$ of non-negative integers is \emph{feasible} if it is the statistics of some Moser set $A$. \item A feasible vector $(a_0,\ldots,a_n)$ is \emph{Pareto-optimal} if there is no other feasible vector $(b_0,\ldots,b_n) \neq (a_0,\ldots,a_n)$ such that $b_i \geq a_i$ for all $0 \leq i \leq n$. \item A Pareto-optimal vector $(a_0,\ldots,a_n)$ is \emph{extremal} if it is not a non-trivial convex linear combination of other Pareto-optimal vectors. \end{itemize} \end{definition}

To establish a linear inequality of the form \eqref{alphav} with the $v_i$ non-negative, it suffices to test the inequality against densities associated to extremal vectors of statistics. (There is no point considering linear inequalities with negative coefficients $v_i$, since one always has the freedom to reduce a density $\alpha_i(A)$ of a Moser set $A$ to zero, simply by removing all elements of $A$ with exactly $i$ $2$'s.)

We will classify exactly the Pareto-optimal and extremal vectors for $n \leq 3$, which by Lemma \ref{prop} will lead to useful linear inequalities for $n \geq 4$. Using a computer, we have also located a partial list of Pareto-optimal and extremal vectors for $n=4$, which are also useful for the $n=5$ and $n=6$ theory.

\subsection{Up to three dimensions}

We now establish Theorem \ref{moser} for $n \leq 3$, and establish some auxiliary inequalities which will be of use in higher dimensions.

The case $n=0$ is trivial. When $n=1$, it is clear that $c'_{1,3} = 2$, and furthermore that the Pareto-optimal statistics are $(2,0)$ and $(1,1)$, which are both extremal. This leads to the linear inequality $$ 2\alpha(A) + \beta(A) \leq 2$$ for all Moser sets $A \subset [3]^1$, which by Lemma \ref{prop} implies that \begin{equation}\label{alpha-1} 2\alpha_r(A) + \alpha_{r+q}(A) \leq 2 \end{equation} whenever $r \geq 0$, $q \geq 1$, $n \geq q+r$, and $A \subset [3]^n$ is a Moser set.

For $n=2$, we see by partitioning $[3]^2$ into three slices that $c'_{2,3} \leq 3 c'_{1,3} = 6$, and so (by the lower bounds in the previous section) $c'_{2,3} = 6$. Writing $(a,b,c) = (a(A),b(A),c(A)) = (4\alpha(A), 4\beta(A), \gamma(A))$, the inequalities \eqref{alpha-1} become \begin{equation}\label{abc} a + 2c \leq 4; b+2c \leq 4; 2a+b <= 8. \end{equation}

\begin{lemma} When $n=2$, the Pareto-optimal statistics are $(4,0,0), (3,2,0), (2,4,0), (2,2,1)$. In particular, the extremal statistics are $(4,0,0), (2,4,0), (2,2,1)$. \end{lemma}

\begin{proof} One easily checks that all the statistics listed above are feasible. Consider the statistics $(a,b,c)$ of a Moser set $A \subset [3]^2$. $c$ is either equal to $0$ or $1$. If $c=1$, then \eqref{abc} implies that $a,b \leq 2$, so the only Pareto-optimal statistic here is $(2,2,1)$. When instead $c=0$, the inequalities \eqref{abc} can easily imply the Pareto-optimality of $(4,0,0), (3,2,0), (2,4,0)$. \end{proof}

From this lemma we see that we obtain a new inequality $2a+b+2c \leq 8$. Converting this back to densities and using Lemma \ref{prop}, we conclude that \begin{equation}\label{alpha-2} 4\alpha_r(A) + 2\alpha_{r+q}(A) + \alpha_{r+2q} \leq 4 \end{equation} whenever $r \geq 0$, $q \geq 1$, $n \geq q+2r$, and $A \subset [3]^n$ is a Moser set.

One can also check by computer that there are exactly $230$ line-free subsets of $[3]^2$.

Now we look at three dimensions. Writing $(a,b,c,d)$ for the statistics of a Moser set $A \subset [3]^n$ (which thus range between $(0,0,0,0)$ and $(8,12,6,1)$), the inequalities \eqref{alpha-1} imply in particular that \begin{equation}\label{abc-3d} a+4d \leq 8; b+6d \leq 12; c+3d \leq 6; 3a+2c \leq 24; b+c \leq 12 \end{equation} while \eqref{alpha-2} implies that \begin{equation}\label{abcd-3d} 3a+b+c \leq 24; b+c+3d \leq 12. \end{equation} Summing the inequalities $b+c \leq 12, 3a+b+c \leq 24, b+c+3d \leq 12$ yields $$ 3(a+b+c+d) \leq 48$$ and hence $|A| = a+b+c+d \leq 16$; comparing this with the lower bounds of the preceding section we obtain $c'_{3,3} = 16$ as required. (This argument is essentially identical to the one in \cite{chvatal2}).

We have the following useful computation:

\begin{lemma}[3D Pareto-optimals]\label{paretop} When $n=3$, the Pareto-optimal statistics are $$(3,6,3,1),(4,4,3,1),(4,6,2,1),(2,6,6,0),(3,6,5,0),(4,4,5,0),(3,7,4,0),(4,6,4,0),$$ $$ (3,9,3,0),(4,7,3,0),(5,4,3,0),(4,9,2,0),(5,6,2,0),(6,3,2,0),(3,10,1,0),(5,7,1,0),$$ $$ (6,4,1,0),(4,12,0,0),(5,9,0,0),(6,6,0,0),(7,3,0,0),(8,0,0,0).$$ In particular, the extremal statistics are $$(3,6,3,1),(4,4,3,1),(4,6,2,1),(2,6,6,0),(4,4,5,0),(4,6,4,0),(4,12,0,0),(8,0,0,0).$$ \end{lemma}

\begin{proof} This can be established by a brute-force search over the $2^{27} \approx 1.3 \times 10^8$ different subsets of $[3]^3$. Actually, one can perform a much faster search than this. Firstly, as noted earlier, there are only $230$ line-free subsets of $[3]^2$, so one could search over $230^3 \approx 1.2 \times 10^7$ configurations instead. Secondly, by symmetry we may assume (after enumerating the $230$ sets in a suitable fashion) that the first slice $A \cap 1**$ has an index less than or equal to the third $A \cap 3**$, leading to $\binom{231}{2} \times 230 \approx 6 \times 10^6$ configurations instead. Finally, using the first and third slice one can quickly determine which elements of the second slice $2**$ are prohibited from $A$. There are $2^9 = 512$ possible choices for the prohibited set in $2**$. By crosschecking these against the list of $230$ line-free sets one can compute the Pareto-optimal statistics for the second slices inside the prohibited set (the lists of such statistics turns out to length at most $23$). Storing these statistics in a lookup table, and then running over all choices of the first and third slice (using symmetry), one now has to perform $O( 512 \times 230 ) + O( \binom{231}{2} \times 23) \approx O( 10^6 )$ computations, which is quite a feasible computation.

One could in principle reduce the computations even further, by a factor of up to $8$, by using the symmetry group $D_4$ of the square $[3]^2$ to reduce the number of cases one needs to consider, but we did not implement this.

A computer-free proof of this lemma can be found at \centerline{{\tt http://michaelnielsen.org/polymath1/index.php?title=Human\_proof\_of\_the\_3D\_Pareto-optimal\_Moser\_statistics}.} \end{proof}

\begin{remark} A similar computation revealed that the total number of line-free subsets of $[3]^3$ was $3813884$. With respect to the $2^3 \times 3!=48$-element group of geometric symmetries of $[3]^3$, these sets partitioned into $83158$ equivalence classes: $$ 3813884 = 76066 \times 48+6527 \times 24+51 \times 16+338 \times 12 +109 \times 8+41 \times 6+13 \times 4 +5 \times 3+3 \times 2+5 \times 1. $$ \end{remark}

Lemma \ref{paretop} yields the following new inequalities: \begin{align*} 2a+b+2c+4d &\leq 22 \\ 3a+2b+3c+6d &\leq 36 \\ 7a+2b+4c+8d &\leq 56 \\ 6a+2b+3c+6d &\leq 48 \\ a+2c+4d &\leq 14 \\ 5a+4c+8d &\leq 40. \end{align*}

Applying Lemma \ref{prop}, we obtain new inequalities: \begin{align} 8\alpha_r(A)+ 6\alpha_{r+q}(A) + 6\alpha_{r+2q}(A) + 2\alpha_{r+3q}(A) &\leq 11 \label{eleven}\\ 4\alpha_r(A)+4\alpha_{r+q}(A)+3\alpha_{r+2q}(A)+\alpha_{r+3q}(A) &\leq 6\label{six}\\ 7\alpha_r(A)+3\alpha_{r+q}(A)+3\alpha_{r+2q}(A)+\alpha_{r+3q}(A) &\leq 7\nonumber\\ 8\alpha_r(A)+3\alpha_{r+q}(A)+3\alpha_{r+2q}(A)+\alpha_{r+3q}(A) &\leq 8\label{eight}\\ 4\alpha_{r+q}(A)+2\alpha_{r+2q}(A)+\alpha_{r+3q}(A) &\leq 4\nonumber\\ 4\alpha_r(A)+6\alpha_{r+2q}(A)+2\alpha_{r+3q}(A) &\leq 7\nonumber\\ 5\alpha_r(A)+3\alpha_{r+2q}(A)+\alpha_{r+3q}(A) &\leq 5\nonumber \end{align} whenever $r \geq 0$, $q \geq 1$, $n \geq r+3q$, and Moser sets $A \subset [3]^n$.

We also note some further corollaries of Lemma \ref{paretop}:

\begin{corollary}[Statistics of large 3D Moser sets]\label{paretop2} Let $(a,b,c,d)$ be the statistics of a Moser set $A$ in $[3]^3$. Then $|A| = a+b+c+d \leq 16$. Furthermore: \begin{itemize} \item If $|A|=16$, then $(a,b,c,d) = (4,12,0,0)$. \item If $|A|=15$, then $(a,b,c,d) = (4,11,0,0)$ or $(3,12,0,0)$. \item If $|A| \geq 14$, then $b \geq 6$ and $d=0$. \item If $|A| = 13$ and $d=1$, then $(a,b,c,d) = (4,6,2,1)$ or $(3,6,3,1)$. \end{itemize} \end{corollary}

\subsection{Four dimensions}

Now we establish the bound $c'_{4,3}=43$. Let $A$ be a Moser set in $[3]^4$, with attendant statistics $(a,b,c,d,e)$, which range between $(0,0,0,0,0)$ and $(16,32,24,8,1)$. In view of the lower bounds, our task here is to establish the upper bound $a+b+c+d+e \leq 43$.

The linear inequalities already established just barely fail to achieve this bound, but we can obtain the upper bound $a+b+c+d+e \leq 44$ as follows. First suppose that $e=1$; then from the inequalities \eqref{alpha-1} (or by considering lines passing through $2222$) we see that $a \leq 8, b \leq 16, c \leq 12, d \leq 4$ and hence $a+b+c+d+e \leq 41$, so we may assume that $e=0$.

From Lemma \ref{dci}, we see that $a+b+c+d+e$ is now equal to the sum of $a(V)/4+b(V)/3+c(V)/2+d(V)$, where $V$ ranges over all side slices of $[3]^4$. But from Lemma \ref{paretop} we see that $a(V)/4+b(V)/3+c(V)/2+d(V)$ is at most $\frac{11}{4}$, with equality occuring only when $(a(V),b(V),c(V),d(V))=(2,6,6,0)$. This gives the upper bound $a+b+c+d+e \leq 44$.

The above argument shows that $a+b+c+d+e=44$ can only occur if $e=0$ and if $(a(V),b(V),c(V),d(V))=(2,6,6,0)$ for all side slices $V$. Applying Lemma \ref{paretop} again this implies $(a,b,c,d,e)=(4,16,24,0,0)$. But then $A$ contains all of the sphere $S_{2,4}$, which implies that the four-element set $A \cap S_{4,4}$ cannot contain a pair of strings which differ in exactly two positions (as their midpoint would then lie in $S_{2,4}$, contradicting the hypothesis that $A$ is a Moser set).

Recall that we may partition $S_{4,4} = S_{4,4}^e \cup S_{4,4}^o$, where $$S_{4,4}^e := \{ 1111, 1133, 1313, 3113, 1331, 3131, 3311, 3333\}$$ is the strings in $S_{4,4}$ with an even number of $1$'s, and $$S_{4,4}^o := \{ 1113, 1131, 1311, 3111, 1333, 3133, 3313, 3331\}$$ are the strings in $S_{4,4}$ with an odd number. Observe that any two distinct elements in $S_{4,4}^e$ differ in exactly two positions unless they are antipodal. Thus $A \cap S_{4,4}^e$ has size at most two, with equality only when $A \cap S_{4,4}^e$ consists of an antipodal pair. Similarly for $A \cap S_{4,4}^o$. Thus $A$ must consist of two antipodal pairs, one from $S_{4,4}^e$ and one from $S_{4,4}^o$.

By the symmetries of the cube we may assume without loss of generality that these pairs are $\{ 1111, 3333\}$ and $\{1113,3331\}$ respectively. But as $A$ is a Moser set, $A$ must now exclude the strings $1112$ and $3332$. These two strings form two corners of the eight-element set $$ ***2 \cap S_{3,4} = \{ 1112, 1132, 1312, 3112, 1332, 3132, 3312, 3332 \}.$$ Any pair of points in this set which are ``adjacent in the sense that they differ by exactly one entry cannot both lie in $A$, as their midpoint would then lie in $S_{3,4}$, and so $A$ can contain at most four elements from this set, with equality only if $A$ contains all the points in $***2 \cap S_{3,4}$ of the same parity (either all the elements with an even number of $3$s, or all the elements with an odd number of $3$s). But because the two corners removed from this set have the opposite parity (one has an even number of $1$s and one has an odd number), we see in fact that $A$ can contain at most $3$ points from this set. Meanwhile, the same arguments give that $A$ contains at most four points from $**2* \cap S_{3,4}$, $*2** \cap S_{3,4}$, and $2*** \cap S_{3,4}$. Summing we see that $b = |A \cap S_{3,4}| \leq 3+4+4+4=15$, a contradiction. Thus we have $c'_{4,3}=43$ as claimed.

We have the following four-dimensional version of Lemma \ref{paretop}:

\begin{lemma}[4D Pareto-optimals]\label{paretop-4} When $n=4$, the Pareto-optimal statistics listed on Table \ref{table4}. \end{lemma}

\begin{figure}[tb] \centered{\tiny $(3, 16, 24, 0, 0)$, $(4, 14, 19, 2, 0)$, $(4, 15, 24, 0, 0)$, $(4, 16, 8, 4, 1)$, $(4, 16, 14, 4, 0)$, $(4, 16, 23, 0, 0)$, $(4, 17, 21, 0, 0)$, $(4, 18, 19, 0, 0)$, $(5, 12, 12, 4, 1)$, $(5, 12, 13, 6, 0)$, $(5, 12, 15, 5, 0)$, $(5, 12, 19, 2, 0)$, $(5, 13, 10, 4, 1)$, $(5, 13, 14, 5, 0)$, $(5, 13, 21, 1, 0)$, $(5, 15, 9, 4, 1)$, $(5, 15, 12, 3, 1)$, $(5, 15, 13, 5, 0)$, $(5, 15, 18, 3, 0)$, $(5, 15, 20, 1, 0)$, $(5, 15, 22, 0, 0)$, $(5, 16, 7, 4, 1)$, $(5, 16, 10, 3, 1)$, $(5, 16, 11, 5, 0)$, $(5, 16, 12, 2, 1)$, $(5, 16, 16, 3, 0)$, $(5, 16, 19, 1, 0)$, $(5, 16, 21, 0, 0)$, $(5, 17, 12, 4, 0)$, $(5, 17, 14, 3, 0)$, $(5, 17, 16, 2, 0)$, $(5, 17, 18, 1, 0)$, $(5, 17, 20, 0, 0)$, $(5, 18, 13, 3, 0)$, $(5, 18, 14, 2, 0)$, $(5, 20, 8, 4, 0)$, $(5, 20, 10, 3, 0)$, $(5, 20, 13, 2, 0)$, $(5, 20, 14, 1, 0)$, $(5, 20, 18, 0, 0)$, $(5, 21, 10, 2, 0)$, $(5, 21, 15, 0, 0)$, $(5, 22, 13, 0, 0)$, $(6, 8, 12, 8, 0)$, $(6, 10, 11, 4, 1)$, $(6, 11, 12, 7, 0)$, $(6, 12, 10, 7, 0)$, $(6, 12, 13, 5, 0)$, $(6, 12, 18, 4, 0)$, $(6, 13, 16, 4, 0)$, $(6, 14, 9, 4, 1)$, $(6, 14, 9, 7, 0)$, $(6, 14, 12, 6, 0)$, $(6, 14, 16, 3, 0)$, $(6, 14, 19, 1, 0)$, $(6, 14, 21, 0, 0)$, $(6, 15, 7, 4, 1)$, $(6, 15, 10, 3, 1)$, $(6, 15, 10, 6, 0)$, $(6, 15, 11, 2, 1)$, $(6, 15, 12, 5, 0)$, $(6, 15, 15, 4, 0)$, $(6, 15, 20, 0, 0)$, $(6, 16, 7, 3, 1)$, $(6, 16, 8, 6, 0)$, $(6, 16, 9, 2, 1)$, $(6, 16, 10, 5, 0)$, $(6, 16, 12, 1, 1)$, $(6, 16, 13, 4, 0)$, $(6, 16, 14, 3, 0)$, $(6, 16, 18, 2, 0)$, $(6, 16, 19, 0, 0)$, $(6, 17, 9, 5, 0)$, $(6, 17, 10, 4, 0)$, $(6, 17, 13, 3, 0)$, $(6, 17, 15, 2, 0)$, $(6, 17, 17, 1, 0)$, $(6, 17, 18, 0, 0)$, $(6, 18, 13, 2, 0)$, $(6, 18, 16, 1, 0)$, $(6, 18, 17, 0, 0)$, $(6, 19, 9, 4, 0)$, $(6, 19, 12, 3, 0)$, $(6, 19, 15, 1, 0)$, $(6, 20, 7, 4, 0)$, $(6, 20, 9, 3, 0)$, $(6, 20, 12, 2, 0)$, $(6, 20, 13, 1, 0)$, $(6, 20, 15, 0, 0)$, $(6, 21, 8, 3, 0)$, $(6, 21, 9, 2, 0)$, $(6, 21, 12, 1, 0)$, $(6, 21, 14, 0, 0)$, $(6, 22, 7, 3, 0)$, $(6, 22, 8, 2, 0)$, $(6, 22, 10, 1, 0)$, $(6, 23, 9, 1, 0)$, $(6, 24, 7, 2, 0)$, $(6, 24, 8, 1, 0)$, $(6, 24, 12, 0, 0)$, $(6, 25, 9, 0, 0)$, $(6, 26, 7, 0, 0)$, $(7, 8, 6, 8, 0)$, $(7, 11, 9, 4, 1)$, $(7, 11, 12, 6, 0)$, $(7, 12, 8, 4, 1)$, $(7, 12, 8, 6, 0)$, $(7, 12, 12, 3, 1)$, $(7, 12, 12, 5, 0)$, $(7, 12, 13, 4, 0)$, $(7, 12, 15, 3, 0)$, $(7, 12, 17, 2, 0)$, $(7, 13, 7, 4, 1)$, $(7, 13, 10, 3, 1)$, $(7, 13, 11, 5, 0)$, $(7, 13, 12, 2, 1)$, $(7, 13, 12, 4, 0)$, $(7, 13, 14, 3, 0)$, $(7, 13, 16, 2, 0)$, $(7, 14, 6, 4, 1)$, $(7, 14, 6, 7, 0)$, $(7, 14, 9, 5, 0)$, $(7, 14, 10, 2, 1)$, $(7, 14, 12, 1, 1)$, $(7, 14, 17, 1, 0)$, $(7, 14, 19, 0, 0)$, $(7, 15, 7, 5, 0)$, $(7, 15, 8, 3, 1)$, $(7, 15, 9, 2, 1)$, $(7, 15, 11, 1, 1)$, $(7, 15, 11, 4, 0)$, $(7, 15, 13, 3, 0)$, $(7, 15, 16, 1, 0)$, $(7, 16, 6, 3, 1)$, $(7, 16, 6, 6, 0)$, $(7, 16, 8, 2, 1)$, $(7, 16, 10, 1, 1)$, $(7, 16, 10, 4, 0)$, $(7, 16, 12, 0, 1)$, $(7, 16, 12, 3, 0)$, $(7, 16, 15, 2, 0)$, $(7, 16, 17, 0, 0)$, $(7, 17, 6, 5, 0)$, $(7, 17, 7, 4, 0)$, $(7, 17, 11, 3, 0)$, $(7, 17, 13, 2, 0)$, $(7, 17, 14, 1, 0)$, $(7, 17, 16, 0, 0)$, $(7, 18, 10, 3, 0)$, $(7, 18, 13, 1, 0)$, $(7, 18, 15, 0, 0)$, $(7, 19, 9, 3, 0)$, $(7, 20, 6, 4, 0)$, $(7, 20, 11, 2, 0)$, $(7, 20, 12, 1, 0)$, $(7, 20, 14, 0, 0)$, $(7, 21, 8, 2, 0)$, $(7, 21, 10, 1, 0)$, $(7, 21, 12, 0, 0)$, $(7, 22, 9, 1, 0)$, $(7, 22, 11, 0, 0)$, $(7, 23, 6, 3, 0)$, $(7, 23, 7, 1, 0)$, $(7, 23, 10, 0, 0)$, $(7, 24, 6, 2, 0)$, $(7, 24, 9, 0, 0)$, $(7, 25, 6, 1, 0)$, $(7, 25, 8, 0, 0)$, $(7, 26, 3, 1, 0)$, $(7, 28, 6, 0, 0)$, $(7, 29, 3, 0, 0)$, $(7, 30, 1, 0, 0)$, $(8, 8, 0, 8, 0)$, $(8, 8, 9, 7, 0)$, $(8, 8, 12, 6, 0)$, $(8, 9, 9, 4, 1)$, $(8, 9, 10, 6, 0)$, $(8, 9, 12, 3, 1)$, $(8, 9, 12, 5, 0)$, $(8, 9, 13, 4, 0)$, $(8, 9, 15, 3, 0)$, $(8, 10, 7, 4, 1)$, $(8, 10, 10, 3, 1)$, $(8, 10, 10, 5, 0)$, $(8, 10, 12, 2, 1)$, $(8, 10, 12, 4, 0)$, $(8, 10, 13, 3, 0)$, $(8, 10, 15, 2, 0)$, $(8, 11, 6, 4, 1)$, $(8, 11, 9, 6, 0)$, $(8, 11, 10, 2, 1)$, $(8, 11, 11, 4, 0)$, $(8, 12, 7, 6, 0)$, $(8, 12, 9, 3, 1)$, $(8, 12, 9, 5, 0)$, $(8, 12, 10, 4, 0)$, $(8, 12, 12, 1, 1)$, $(8, 12, 14, 2, 0)$, $(8, 12, 16, 1, 0)$, $(8, 12, 18, 0, 0)$, $(8, 13, 7, 3, 1)$, $(8, 13, 7, 5, 0)$, $(8, 13, 9, 2, 1)$, $(8, 13, 12, 0, 1)$, $(8, 13, 12, 3, 0)$, $(8, 14, 0, 7, 0)$, $(8, 14, 6, 6, 0)$, $(8, 14, 7, 2, 1)$, $(8, 14, 8, 1, 1)$, $(8, 14, 9, 4, 0)$, $(8, 14, 11, 0, 1)$, $(8, 14, 11, 3, 0)$, $(8, 14, 13, 2, 0)$, $(8, 14, 15, 1, 0)$, $(8, 14, 17, 0, 0)$, $(8, 15, 6, 3, 1)$, $(8, 15, 6, 5, 0)$, $(8, 15, 7, 1, 1)$, $(8, 16, 0, 6, 0)$, $(8, 16, 4, 3, 1)$, $(8, 16, 4, 5, 0)$, $(8, 16, 6, 2, 1)$, $(8, 16, 8, 4, 0)$, $(8, 16, 9, 0, 1)$, $(8, 16, 10, 3, 0)$, $(8, 16, 12, 2, 0)$, $(8, 16, 14, 1, 0)$, $(8, 16, 16, 0, 0)$, $(8, 17, 0, 5, 0)$, $(8, 17, 3, 4, 0)$, $(8, 17, 8, 3, 0)$, $(8, 17, 10, 2, 0)$, $(8, 17, 12, 1, 0)$, $(8, 17, 14, 0, 0)$, $(8, 18, 9, 2, 0)$, $(8, 18, 11, 1, 0)$, $(8, 18, 12, 0, 0)$, $(8, 19, 6, 3, 0)$, $(8, 19, 8, 2, 0)$, $(8, 20, 0, 4, 0)$, $(8, 20, 4, 3, 0)$, $(8, 20, 7, 2, 0)$, $(8, 20, 9, 1, 0)$, $(8, 20, 11, 0, 0)$, $(8, 21, 4, 2, 0)$, $(8, 21, 7, 1, 0)$, $(8, 22, 3, 2, 0)$, $(8, 22, 6, 1, 0)$, $(8, 22, 9, 0, 0)$, $(8, 23, 0, 3, 0)$, $(8, 23, 4, 1, 0)$, $(8, 24, 0, 2, 0)$, $(8, 24, 3, 1, 0)$, $(8, 24, 8, 0, 0)$, $(8, 25, 1, 1, 0)$, $(8, 25, 6, 0, 0)$, $(8, 26, 0, 1, 0)$, $(8, 26, 4, 0, 0)$, $(8, 28, 3, 0, 0)$, $(8, 32, 0, 0, 0)$, $(9, 8, 10, 4, 0)$, $(9, 9, 9, 4, 0)$, $(9, 9, 12, 3, 0)$, $(9, 10, 8, 4, 0)$, $(9, 10, 10, 3, 0)$, $(9, 10, 12, 2, 0)$, $(9, 10, 13, 1, 0)$, $(9, 10, 15, 0, 0)$, $(9, 11, 11, 2, 0)$, $(9, 12, 7, 4, 0)$, $(9, 12, 9, 3, 0)$, $(9, 12, 12, 1, 0)$, $(9, 12, 14, 0, 0)$, $(9, 13, 7, 3, 0)$, $(9, 13, 10, 2, 0)$, $(9, 14, 9, 2, 0)$, $(9, 14, 11, 1, 0)$, $(9, 14, 13, 0, 0)$, $(9, 15, 6, 3, 0)$, $(9, 16, 0, 4, 0)$, $(9, 16, 4, 3, 0)$, $(9, 16, 8, 2, 0)$, $(9, 16, 10, 1, 0)$, $(9, 16, 12, 0, 0)$, $(9, 17, 3, 3, 0)$, $(9, 17, 6, 2, 0)$, $(9, 17, 8, 1, 0)$, $(9, 17, 10, 0, 0)$, $(9, 18, 2, 3, 0)$, $(9, 18, 4, 2, 0)$, $(9, 18, 7, 1, 0)$, $(9, 18, 9, 0, 0)$, $(9, 19, 0, 3, 0)$, $(9, 19, 3, 2, 0)$, $(9, 19, 6, 1, 0)$, $(9, 20, 1, 2, 0)$, $(9, 20, 5, 1, 0)$, $(9, 20, 8, 0, 0)$, $(9, 21, 4, 1, 0)$, $(9, 21, 6, 0, 0)$, $(9, 22, 1, 1, 0)$, $(9, 22, 5, 0, 0)$, $(9, 24, 4, 0, 0)$, $(9, 25, 2, 0, 0)$, $(9, 28, 0, 0, 0)$, $(10, 8, 6, 4, 0)$, $(10, 8, 8, 3, 0)$, $(10, 9, 7, 3, 0)$, $(10, 9, 10, 2, 0)$, $(10, 9, 11, 1, 0)$, $(10, 9, 13, 0, 0)$, $(10, 10, 5, 4, 0)$, $(10, 10, 9, 2, 0)$, $(10, 10, 12, 0, 0)$, $(10, 11, 6, 3, 0)$, $(10, 12, 4, 4, 0)$, $(10, 12, 5, 3, 0)$, $(10, 12, 7, 2, 0)$, $(10, 12, 10, 1, 0)$, $(10, 12, 11, 0, 0)$, $(10, 13, 6, 2, 0)$, $(10, 13, 8, 1, 0)$, $(10, 13, 10, 0, 0)$, $(10, 14, 3, 3, 0)$, $(10, 14, 5, 2, 0)$, $(10, 14, 9, 0, 0)$, $(10, 15, 2, 3, 0)$, $(10, 15, 7, 1, 0)$, $(10, 16, 4, 2, 0)$, $(10, 16, 6, 1, 0)$, $(10, 16, 8, 0, 0)$, $(10, 17, 4, 1, 0)$, $(10, 17, 6, 0, 0)$, $(10, 18, 2, 1, 0)$, $(10, 18, 5, 0, 0)$, $(10, 20, 4, 0, 0)$, $(10, 21, 2, 0, 0)$, $(10, 22, 1, 0, 0)$, $(10, 24, 0, 0, 0)$, $(11, 4, 6, 4, 0)$, $(11, 6, 5, 4, 0)$, $(11, 7, 6, 3, 0)$, $(11, 8, 4, 4, 0)$, $(11, 8, 5, 3, 0)$, $(11, 9, 6, 2, 0)$, $(11, 9, 8, 1, 0)$, $(11, 9, 10, 0, 0)$, $(11, 10, 3, 3, 0)$, $(11, 10, 5, 2, 0)$, $(11, 10, 9, 0, 0)$, $(11, 11, 2, 3, 0)$, $(11, 11, 7, 1, 0)$, $(11, 12, 4, 2, 0)$, $(11, 12, 6, 1, 0)$, $(11, 12, 8, 0, 0)$, $(11, 13, 4, 1, 0)$, $(11, 13, 6, 0, 0)$, $(11, 14, 2, 1, 0)$, $(11, 14, 5, 0, 0)$, $(11, 16, 4, 0, 0)$, $(11, 17, 2, 0, 0)$, $(11, 18, 1, 0, 0)$, $(11, 20, 0, 0, 0)$, $(12, 4, 3, 3, 0)$, $(12, 6, 2, 3, 0)$, $(12, 6, 5, 2, 0)$, $(12, 6, 7, 1, 0)$, $(12, 6, 9, 0, 0)$, $(12, 8, 4, 2, 0)$, $(12, 8, 6, 1, 0)$, $(12, 8, 8, 0, 0)$, $(12, 9, 4, 1, 0)$, $(12, 9, 6, 0, 0)$, $(12, 10, 2, 1, 0)$, $(12, 10, 5, 0, 0)$, $(12, 12, 4, 0, 0)$, $(12, 13, 2, 0, 0)$, $(12, 14, 1, 0, 0)$, $(12, 16, 0, 0, 0)$, $(13, 6, 5, 0, 0)$, $(13, 8, 4, 0, 0)$, $(13, 9, 2, 0, 0)$, $(13, 10, 1, 0, 0)$, $(13, 12, 0, 0, 0)$, $(14, 4, 3, 0, 0)$, $(14, 5, 2, 0, 0)$, $(14, 6, 1, 0, 0)$, $(14, 8, 0, 0, 0)$, $(15, 4, 0, 0, 0)$, $(16, 0, 0, 0, 0)$}} \caption{The Pareto-optimal statistics of Moser sets in $[3]^4$. This table can also be found at {\tt http://spreadsheets.google.com/ccc?key=rwXB\_Rn3Q1Zf5yaeMQL-RDw}} \label{table4} \end{figure}

\begin{proof} This was computed by computer search as follows. First, one observed that if $(a,b,c,d,e)$ was Pareto-optimal, then $a\geq 3$. To see this, it suffices to show that for any Moser set $A \subset [3]^4$ with $a(A)=0$, it is possible to add three points from $S_{4,4}$ to $A$ and still have a Moser set. To show this, suppose first that $A$ contains a point from $S_{1,4}$, such as $2221$. Then $A$ must omit either $2211$ or $2231$; without loss of generality we may assume that it omits $2211$. Similarly we may assume it omits $2121$ and $1221$. Then we can add $1131$, $1311$, $3111$ to $A$, as required. Thus we may assume that $A$ contains no points from $S_{1,4}$. Now suppose that $A$ omits a point from $S_{2,4}$, such as $2211$. Then one can add $3333$, $3111$, $1311$ to $A$, as required. Thus we may assume that A contains all of $S_{2,4}$, which forces $A$ to omit $2222$, as well as at least one point from $S_{3,4}$, such as $2111$. But then $3111$, $1111$, $3333$ can be added to the set, a contradiction.

Thus we only need to search through sets $A \subset [3]^4$ for which $|A \cap S_{4,4}| \geq 3$. A straightforward computer search shows that up to the symmetries of the cube, there are $391$ possible choices for $A \cap S_{4,4}$. For each such choice, we looped through all the possible values of the slices $A \cap 1***$ and $A \cap 3***$, i.e. all three-dimensional Moser sets which had the indicated intersection with $S_{3,3}$. (For fixed $A \cap S_{4,4}$, the number of possibilities for $A \cap 1***$ ranges from $1$ to $87123$, and similarly for $A \cap 3***$). For each pair of slices $A \cap 1***$ and $A \cap 3***$, we computed the lines connecting these two sets to see what subset of $2***$ was excluded from $A$; there are $2^{27}$ possible such exclusion sets. We precomputed a lookup table that gave the Pareto-optimal statistics for $A \cap 2***$ for each such choice of exclusion set; using this lookup table for each choice of $A \cap 1***$ and $A \cap 3***$ and collating the results, we obtained the above list. On a linux cluster, the lookup table took 22 minutes to create, and the loop over the $A \cap 1***$ and $A \cap 3***$ slices took two hours, spread out over $391$ machines (one for each choice of $A \cap S_{4,4}$). Further details (including source code) can be found at \centerline{{\tt http://michaelnielsen.org/polymath1/index.php?title=4D\_Moser\_brute\_force\_search}.} \end{proof}

As a consequence of this data, we have the following facts about the statistics of large Moser sets:

\begin{proposition}\label{stat} Let $A \subset [3]^4$ be a Moser set with statistics $(a,b,c,d,e)$. \begin{itemize} \item[(i)] If $|A| \geq 40$, then $e=0$. \item[(ii)] If $|A| \geq 43$, then $d=0$. \item[(iii)] If $|A| \geq 42$, then $d \leq 2$. \item[(iv)] If $|A| \geq 41$, then $d \leq 3$. \item[(v)] If $|A| \geq 40$, then $d \leq 6$. \item[(vi)] If $|A| \geq 43$, then $c \geq 18$. \item[(vii)] If $|A| \geq 42$, then $c \geq 12$. \item[(viii)] If $|A| \geq 43$, then $b \geq 15$. \end{itemize} \end{proposition}

\begin{remark} This proposition was first established by an integer program, see Appendix \ref{integer-sec}. A computer-free proof can be found at \centerline{{\tt http://terrytao.files.wordpress.com/2009/06/polymath2.pdf}.} \end{remark}

\subsection{Five dimensions}

Now we establish the bound $c'_{5,3}=124$. In view of the lower bounds, it suffices to show that there does not exist a Moser set $A \subset [3]^5$ with $|A|=125$.

We argue by contradiction. Let $A$ be as above, and let $(a(A),\ldots,f(A))$ be the statistics of $A$.

\begin{lemma}\label{fvan} $f(A)=0$. \end{lemma}

\begin{proof} If $f(A)$ is non-zero, then $A$ contains $22222$, then each of the $\frac{3^5-1}{2} = 121$ antipodal pairs in $[3]^5$ can have at most one point in $A$, leading to only $122$ points. \end{proof}

Let us slice $[3]^5$ into three parallel slices, e.g. $1****, 2****, 3****$. The intersection of $A$ with each of these slices has size at most $43$. In particular, this implies that \begin{equation}\label{boo}

|A \cap 1****| + |A \cap 3****| = 125 - |A \cap 2****| \geq 82.

\end{equation} Thus at least one of $A \cap 1****$, $A \cap 3****$ has cardinality at least $41$; by Proposition \ref{stat}(iv) we conclude that \begin{equation}\label{d13} \min( d(1****), d(3****) ) \leq 3. \end{equation} Furthermore, equality can only hold in \eqref{d13} if $A \cap 1****$, $A \cap 3****$ both have cardinality exactly $41$, in which case from Proposition \ref{stat}(iv) again we must have \begin{equation}\label{d13a} d(1****)=d(3****)=3. \end{equation} Of course, we have a similar result for permutations.

Now we improve the bound $|A \cap 2****| \leq 43$:

\begin{lemma} $|A \cap 2****| \leq 41$. \end{lemma}

\begin{proof} Suppose first that $|A \cap 2****|=43$. Let $A' \subset [3]^4$ be the subset of $[3]^4$ corresponding to $A \cap 2****$, thus $A'$ is a Moser set of cardinality $43$. By Proposition \ref{stat}(vi), $c(A') \geq 18$. By Lemma \ref{dci}, the sum of the $c(V)$, where $V$ ranges over the eight side slices of $[3]^4$, is therefore at least $36$. By the pigeonhole principle, we may thus find two opposing side slices, say $1***$ and $3***$, with $c(1***)+c(3****) \geq 9$. Since $c(1***), c(3***)$ cannot exceed $6$, we thus have $c(1***), c(3***) \geq 3$, with at least one of $c(1***), c(3***)$ being at least $5$. Passing back to $A$, this implies that $d(*1***), d(*3***) \geq 3$, with at least one of $d(*1***), d(*3***)$ being at least $5$. But this contradicts \eqref{d13} together with the refinement \eqref{d13a}.

We have just shown that $|A \cap 2****| \leq 42$; we can thus improve \eqref{boo} to $$ |A \cap 1****| + |A \cap 3****| \geq 83.$$ Combining this with Proposition \ref{stat}(ii)-(v) we see that \begin{equation}\label{d13-6}

d(1****)+d(3****) \leq 6

\end{equation} with equality only if $|A \cap 2****|=42$, and similarly for permutations.

Now let $A'$ be defined as before. Then we have $$ c(1***) + c(3***) \leq 6$$ and similarly for permutations. Applying Lemma \ref{dci}, this implies that $c(2****) = c(A') \leq 12$.

Now suppose for contradiction that $|A'|=|A \cap 2****|=42$. Then by Proposition \ref{stat}(vii) we have \begin{equation}\label{coo-1} c(2****) = 12; \end{equation} applying Lemma \ref{dci} again, this forces $c(1***)+c(3***)=6$ and similarly for permutations, which then implies that \begin{equation}\label{doo} d(*1***)+d(*3***) = d(**1**)+d(**3**) = d(***1*)+d(***3*) = d(****1)+d(****3) = 6 \end{equation} and hence $$ |A \cap *2***| = |A \cap **2**| = |A \cap ***2*| = |A \cap ****2| = 42$$ and thus \begin{equation}\label{coo-2} c(*2***) = c(**2**) = c(***2*) = c(****2) = 12. \end{equation} Combining \eqref{coo-1}, \eqref{doo}, \eqref{coo-2} we conclude that $$ d(1****)+d(3****) = 16,$$ contradicting \eqref{d13-6}. \end{proof}

With this proposition, the bound \eqref{boo} now improves to \begin{equation}\label{84} |A \cap 1****| + |A \cap 3****| \geq 84 \end{equation} and in particular \begin{equation}\label{41} |A \cap 1****|, |A \cap 3****| \geq 41. \end{equation} from this and Proposition \ref{stat}(ii)-(iv) we now have \begin{equation}\label{d13-improv}

d(1****)+d(3****) \leq 4

\end{equation} and similarly for permutations.

\begin{lemma}\label{evan} $e(A)=0$. \end{lemma}

\begin{proof} From \eqref{84}, the intersection of $A$ with any side slice has cardinality at least $41$, and thus by Proposition \ref{stat}(i) such a side slice has an $e$-statistic of zero. The claim then follows from Lemma \ref{dci}. \end{proof}

We need a technical lemma:

\begin{lemma}\label{tech} Let $B \subset S_{5,5}$. Then there exist at least $|B|-4$ pairs of strings in $B$ which differ in exactly two positions. \end{lemma}

\begin{proof} The first non-vacuous case is $|B|=5$. It suffices to establish this case, as the higher cases then follow by induction (locating a pair of the desired form, then deleting one element of that pair from $B$).

Suppose for contradiction that one can find a $5$-element set $B \subset S_{5,5}$ such that no two strings in $B$ differ in exactly two positions. Recall that we may split $S_{5,5}=S_{5,5}^e \cup S_{5,5}^o$, where $S_{5,5}^e$ are those strings with an even number of $1$'s, and $S_{5,5}^o$ are those strings with an odd number of $1$'s. By the pigeonhole principle and symmetry we may assume $B$ has at least three elements in $S_{5,5}^o$. Without loss of generality, we can take one of them to be $11111$, thus excluding all elements in $S_{5,5}^o$ with exactly two $3$s, leaving only the elements with exactly four $3$s. But any two of them differ in exactly two positions, a contradiction. \end{proof}

We can now improve the trivial bound $c(A) \leq 80$:

\begin{corollary}[Non-maximal $c$]\label{cmax} $c(A) \leq 79$. If $a(A) \geq 7$, then $c(A) \leq 78$. \end{corollary}

\begin{proof} If $c(A)=80$, then $A$ contains all of $S_{3,5}$, which then implies that no two elements in $A \cap S_{5,5}$ can differ in exactly two places. It also implies (from \eqref{alpha-1}) that $d(A)$ must vanish, and that $b(A)$ is at most $40$. By Lemma \ref{tech}, we also have that $a(A) = |A \cap S_{5,5}|$ is at most $4$. Thus $|A| \leq 4 + 40 + 80 + 0 + 0 = 124$, a contradiction.

Now suppose that $a(A) \geq 7$. Then by Lemma \ref{tech} there are at least three pairs in $A \cap S_{5,5}$ that differ in exactly two places. Each such pair eliminates one point from $A \cap S_{3,5}$; but each point in $S_{3,5}$ can be eliminated by at most two such pairs, and so we have at least two points eliminated from $A \cap S_{3,5}$, i.e. $c(A) \leq 78$ as required. \end{proof}

Next, we rewrite the quantity $125=|A|$ in terms of side slices. From Lemmas \ref{fvan}, \ref{evan} we have $$ a(A) + b(A) + c(A) + d(A) = 125$$ and hence by Lemma \ref{dci}, the quantity $$ s(V) := a(V) + \frac{5}{4} b(V) + \frac{5}{3} c(V) + \frac{5}{2} d(V) - \frac{125}{2},$$ where $V$ ranges over side slices, has an average value of zero.

\begin{proposition}[Large values of $s(V)$]\label{suv} For all side slices, we have $s(V) \leq 1/2$. Furthermore, we have $s(V) < -1/2$ unless the statistics $(a(V), b(V), c(V), d(V), e(V))$ are of one of the following four cases: \begin{itemize} \item (Type 1) $(a(V),b(V),c(V),d(V),e(V)) = (2,16,24,0,0)$ (and $s(V) = -1/2$ and $|A \cap V| = 42$); \item (Type 2) $(a(V),b(V),c(V),d(V),e(V)) = (4,16,23,0,0)$ (and $s(V) = -1/6$ and $|A \cap V| = 43$); \item (Type 3) $(a(V),b(V),c(V),d(V),e(V)) = (4,15,24,0,0)$ (and $s(V) = 1/4$ and $|A \cap V| = 43$); \item (Type 4) $(a(V),b(V),c(V),d(V),e(V)) = (3,16,24,0,0)$ (and $s(V) = 1/2$ and $|A \cap V| = 43$); \end{itemize} \end{proposition}

\begin{proof} Let $V$ be a side slice. From \eqref{41} we have $$ 41 \leq a(V)+b(V)+c(V)+d(V) = |A \cap V| \leq 43.$$ First suppose that $|A \cap V| = 43$, then from Proposition \ref{stat}(ii), (viii), $d(V)=0$ and $b(V) \geq 15$. Also, we have the trivial bound $c(V) \leq 24$, together with the inequality $$ 3b(V) + 2c(V) \leq 96$$ from \eqref{alpha-1}. To exploit these facts, we rewrite $s(V)$ as $$ s(V) = \frac{1}{2} - \frac{1}{2}( 24 - c(V) ) - \frac{1}{12} (96-3b(V)-2c(V)).$$ Thus $s(V) \leq 1/2$ in this case. If $s(V) \geq -1/2$, then $$ 6 (24-c(V)) + (96-3b(V)-2c(V)) \leq 12,$$ which together with the inequalities $b(V) \leq 15$, $c(V) \leq 24$, $3b(V)+2c(V) \leq 96$ we conclude that $(b(V),c(V))$ must be one of $(16,24)$, $(15, 24)$, $(16, 23)$, $(15, 23)$. The first three possibilities lead to Types 4,3,2 respectively. The fourth type would lead to $(a(V),b(V),c(V),d(V),e(V)) = (5,15,23,0,0)$, but this contradicts \eqref{eleven}.

Next, suppose $|A \cap V| = 42$, so by Proposition \ref{stat}(iii) we have $d(V) \leq 2$. From \eqref{alpha-1} we have \begin{equation}\label{2cd} 2c(V) + 3d(V) \leq 48 \end{equation} while from \eqref{alpha-2} we have \begin{equation}\label{3cd} 3b(V)+2c(V)+3d(V) \leq 96 \end{equation} and so we can rewrite $s(V)$ as \begin{equation}\label{sv2} s(V) = -\frac{1}{2} - \frac{1}{4}( 48 - 2c(V) - 3d(V) ) - \frac{1}{12} (96-3b(V)-2c(V)-3d(V)) + \frac{1}{2} d(V). \end{equation} This already gives $s(V) \leq 1/2$. If $d(V)=0$, then $s(V) \leq -1/2$, with equality only in Type 1. If $d(V)=1$, then the set $A' \subset [3]^4$ corresponding to $A \cap V$ contains a point in $S_{3,4}$, which without loss of generality we can take to be $2221$. Considering the three lines $*221$, $2*21$, $22*1$, we see that at least three points in $S_{2,4}$ must be missing from $A'$, thus $c(V) \leq 21$. This forces $48-2c(V)-3d(V) \geq 3$, and so $s(V) < -3/4$. Finally, if $d(V)=2$, then $A'$ contains two points in $S_{3,4}$. If they are antipodal (e.g. $2221$ and $2223$), the same argument as above shows that at least six points in $S_{2,4}$ are missing from $A'$; if they are not antipodal (e.g. $2221$ and $2212$) then by considering the lines $*221$, $2*21$, $22*1$, $*212$, $2*12$ we see that five points are missing. Thus we have $c(V) \leq 19$, which forces $48-2c(V)-3d(V) \geq 4$. This forces $s(V) \leq -1/2$, with equality only when $c(V)=19$ and $3b(V)+2c(V)+3d(V)=96$, but this forces $b(V)$ to be the non-integer $52/3$, a contradiction, which concludes the treatment of the $|A \cap V|=42$ case.

Finally, suppose $|A \cap V| = 41$. Using \eqref{2cd}, \eqref{3cd} as before we have \begin{equation}\label{sv3}

s(V) = -\frac{3}{2} - \frac{1}{4}( 48 - 2c(V) - 3d(V) ) - \frac{1}{12} (96-3b(V)-2c(V)-3d(V)) + \frac{1}{2} d(V),

\end{equation} while from Proposition \ref{stat}(vi) we have $d(V) \leq 3$. This already gives $s(V) \leq 0$, and $s(V) \leq -1$ when $d(V)=1$. In order to have $s(V) \geq -1/2$, we must then have $d(V)=2$ or $d(V)=3$. But then the arguments of the preceding paragraph give $48-2c(V)-3d(V) \geq 4$, and so $s(V) \leq -1$ in this case. \end{proof}

Since the $s(V)$ average to zero, by the pigeonhole principle we may find two opposing side slices (e.g. $1****$ and $3****$), whose total $s$-value is non-negative. Actually we can do a little better:

\begin{lemma}\label{side-off} There exists two opposing side slices whose total $s$-value is strictly positive. \end{lemma}

\begin{proof} If this is not the case, then we must have $s(1****)+s(3****)=0$ and similarly for permutations. Using Proposition \ref{suv} we thus see that for every opposing pair of side slices, one is Type 1 and one is Type 4. In particular $c(V)=24$ for all side slices $V$. But then by Lemma \ref{dci} we have $c(A)=80$, contradicting Lemma \ref{cmax}. \end{proof}

Let $V, V'$ be the side slices in Lemma \ref{side-off} By Proposition \ref{suv}, the $V, V'$ slices must then be either Type 2, Type 3, or Type 4, and they cannot both be Type 2. Since $a(A) = a(V)+a(V')$, we conclude \begin{equation}\label{amix} 6 \leq a(A) \leq 8. \end{equation} In a similar spirit, we have $$ c(V) + c(V') \leq 23+24.$$ On the other hand, by considering the $24$ lines connecting $c$-points of $V, V'$ to $c$-points of the centre slice $W$ between $V$ and $V'$, each of which contains at most two points in $A$, we have $$ c(V) + c(W) + c(V') \leq 24 \times 2.$$ Thus $c(W) \leq 1$; since $$ d(A) = d(V) + d(V') + c(W)$$ we conclude from Proposition \ref{suv} that $d(A) \leq 1$. Actually we can do better:

\begin{lemma} $d(A)=0$. \end{lemma}

\begin{proof} Suppose for contradiction that $d(A)=1$; without loss of generality we may take $11222 \in A$. This implies that $d(1****)=d(*1***)=1$. Also, by the above discussion, $c(**1**)$ and $c(**3**)$ cannot both be $24$, so by Proposition \ref{suv}, $s(**1**)+s(**3**) \leq 1/3$; similarly $s(***1*)+s(***3*) \leq 1/3$ and $s(****1)+s(****3) \leq 1/3$. Since the $s$ average to zero, we see from the pigeonhole principle that either $s(1****)+s(3****) \geq -1/2$ or $s(*1***)+s(*3***) \geq -1/2$. We may assume by symmetry that \begin{equation}\label{star-2} s(1****)+s(3****) \geq -1/2. \end{equation} Since $s(3****) \leq 1/2$ by Proposition \ref{suv}, we conclude that \begin{equation}\label{star}

s(1****) \geq -1.

\end{equation} If $|A \cap 1****|=41$, then by \eqref{sv3} we have $$ s(1****) = -1 - \frac{1}{4}( 48 - 2c(1****) - 3d(1****) ) - \frac{1}{12} (96-3b(1****)-2c(1****)-3d(1****))$$ but the arguments in Proposition \ref{suv} give $48 - 2c(1****) - 3d(1****) \geq 3$ and $96-3b(1****)-2c(1****)-3d(1****) \geq 0$, a contradiction. So we must have $|A \cap 1****|=42$ (by Proposition \ref{stat}(ii) and \eqref{41}). In that case, from \eqref{sv2} we have $$ s(1****) = \frac{1}{4}( 48 - 2c(1****) - 3d(1****) ) - \frac{1}{12} (96-3b(1****)-2c(1****)-3d(1****))$$ while also having $48 - 2c(1****) - 3d(1****) \geq 3$ and $96-3b(1****)-2c(1****)-3d(1****) \geq 0$. Since $s(1****) \geq -1$ and $d(1****)=1$, we soon see that we must have $48 - 2c(1****) - 3d(1****) = 3$ and $96-3b(1****)-2c(1****)-3d(1****) \leq 3$, which forces $c(1****)=21$ and $b(1****)=16$ or $b(1****)=17$; thus the statistics of $1****$ are either $(4,16,21,1,0)$ or $(3,17,21,1,0)$.

We first eliminate the $(3,17,21,1,0)$ case. In this case $s(1****)$ is exactly $-1$. Inspecting the proof of \eqref{star}, we conclude that $s(3****)$ must be $+1/2$ and that $s(**1**)+s(**3**)=1/3$. From the former fact and Proposition \ref{suv} we see that $a(A) = a(1****)+a(3****)=3+3=6$; on the other hand, from the latter fact and Proposition \ref{suv} we have $a(A) = a(**1**)+a(**3**) = 4+3=7$, a contradiction.

So $1****$ has statistics $(4,16,21,1,0)$, which implies that $s(1****)=-3/4$ and $|A \cap 1****|=42$. By \eqref{star-2} we conclude \begin{equation}\label{s3} s(3****) \geq 1/4, \end{equation} which by Proposition \ref{suv} implies that $|A \cap 3****|=43$, and hence $|A \cap 2****|=40$. On the other hand, since $e(A)=f(A)=0$ and $d(A)=1$, with the latter being caused by $11222$, we see that $c(2****)=d(2****)=e(2****)=0$. From \eqref{alpha-1} we have $4a(2****)+b(2****) \leq 64$, and we also have the trivial inequality $b(2****) \leq 32$; these inequalities are only compatible if $2****$ has statistics $(8,32,0,0,0)$, thus $A \cap 2****$ contains $S_{2,5} \cap 2****$.

If $a(3****)=4$, then $a(A)=a(1****)+a(3****)=8$, which by Proposition \ref{suv} implies that $s(**1**)+s(**3**)$ cannot exceed $1/12$, and similarly for permutations. On the other hand, from Proposition \ref{suv} $s(**1**)+s(**3**)$ cannot exceed $-3/4 + 1/4 = -1/2$, and so the average value of $s$ cannot be zero, a contradiction. Thus $a(3****) \neq 4$, which by \eqref{s3} and Proposition \ref{suv} implies that $**3**$ has statistics $(3,16,24,0,0)$.

In particular, $A$ contains $16$ points from $3**** \cap S_{1,5}$ and all of $3**** \cap S_{2,5}$. As a consequence, no pair of the $16$ points in $A \cap 3**** \cap S_{1,5}$ can differ in only one coordinate; partitioning the $32$-point set $3**** \cap S_{1,5}$ into $16$ such pairs, we conclude that every such pair contains exactly one element of $A$. We conclude that $A \cap 3**** \cap S_{1,5}$ is equal to either $3**** \cap S_{1,5}^e$ or $3**** \cap S_{1,5}^o$.

On the other hand, $A$ contains all of $2**** \cap S_{2,5}$, and exactly sixteen points from $1**** \cap S_{1,5}$. Considering the vertical lines $*xyzw$ where $xyzw \in S_{1,4}$, we conclude that $A \cap 1**** \cap S_{1,5}$ is either equal to $1**** \cap S_{1,5}^o$ or $1**** \cap S_{1,5}^e$. But either case is incompatible with the fact that $A$ contains $11222$ (consider either the line $11xx2$ or $11x\overline{x}2$, where $x=1,2,3$ and $\overline{x}=4-x$), obtaining the required contradiction. \end{proof}

We can now eliminate all but three cases for the statistics of $A$:

\begin{proposition}[Statistics of $A$] The statistics $(a(A),b(A),c(A),d(A),e(A),f(A))$ of $A$ must be one of the following three tuples: \begin{itemize} \item (Case 1) $(6,40,79,0,0)$; \item (Case 2) $(7,40,78,0,0)$; \item (Case 3) $(8,39,78,0,0)$. \end{itemize} \end{proposition}

\begin{proof} Since $d(A)=e(A)=f(A)=0$, we have $$ c(2****)=d(2****)=e(2****)=0.$$ On the other hand, from \eqref{alpha-1} we have $4a(2****)+b(2****) \leq 64$ as well as the trivial inequality $b(2****) \leq 24$, and also we have $$ |A \cap 2****| = 125 - |A \cap 1****| - |A \cap 3****| \geq 125 - 43 - 43 = 39.$$ Putting all this together, we see that the only possible statistics for $2****$ are $(8,32,0,0,0)$, $(7,32,0,0,0)$, or $(8,31,0,0,0)$. In particular, $7 \leq a(2****) \leq 8$ and $31 \leq b(2****) \leq 32$, and similarly for permutations. Applying Lemma \ref{dci} we conclude that $$ 35 \leq b(A) \leq 40$$ and $$ 77.5 \leq c(A) \leq 80.$$ Combining this with the first part of Corollary \ref{cmax} we conclude that $c(A)$ is either $78$ or $79$. From this and \eqref{amix} we see that the only cases that remain to be eliminated are $(7,39,79,0,0)$ and $(8,38,79,0,0)$, but these cases are incompatible with the second part of Corollary \ref{cmax}. \end{proof}

We now eliminate each of the three remaining cases in turn.

\subsection{Elimination of $(6,40,79,0,0)$}

Here $A \cap S_{5,5}$ has six points. By Lemma \ref{tech}, there are at least two pairs in this set which differ in two positions. Their midpoints are eliminated from $A \cap S_{3,5}$. But $A$ omits exactly one point from $S_{3,5}$, so these midpoints must be the same. By symmetry, we may then assume that these two pairs are $(11111,11133)$ and $(11113,11131)$. Thus the eliminated point in $S_{3,5}$ is $11122$, i.e. $A$ contains $S_{3,5} \backslash \{11122\}$. Also, $A$ contains $\{11111,11133,11113,11131\}$ and thus must omit $\{11121, 11123, 11112, 11132\}$.

Since $11322 \in A$, at most one of $11312, 11332$ lie in $A$. By symmetry we may assume $11312 \not \in A$, thus there is a pair $(xy1z2, xy3z2)$ with $x,y,z = 1,3$ that is totally omitted from $A$, namely $(11112,11312)$. On the other hand, every other pair of this form can have at most one point in the $A$, thus there are at most seven points in $A$ of the form $xyzw2$ with $x,y,z,w = 1,3$. Similarly there are at most 8 points of the form $xyz2w$, or of $xy2zw$, $x2yzw$, $2xyzw$, leading to $b(A) \leq 7+8+8+8+8=39$, contradicting the statistic $b(A)=40$.

\subsection{Elimination of $(7,40,78,0,0)$}

Here $A \cap S_{5,5}$ has seven points. By Lemma \ref{tech}, there are at least three pairs in this set which differ in two positions. As we can only eliminate two points from $S_{3,5}$, two of the midpoints of these pairs must be the same; thus, as in the previous section, we may assume that $A$ contains $\{11111,11133,11113,11131\}$ and omits $\{11121, 11123, 11112, 11132\}$ and $11122$.

Now consider the $160$ lines $\ell$ connecting two points in $S_{4,5}$ to one point in $S_{3,5}$ (i.e. $*2xyz$ and permutations, where $x,y,z=1,3$). By double counting, the total sum of $|\ell \cap A|$ over all $160$ lines is $4b(A)+2c(A) = 316 = 158 \times 2$. On the other hand, each of these lines contain at most two points in $A$, but two of them (namely $1112*$ and $1112*$) contain no points. Thus we must have $|\ell \cap A|=2$ for the remaining $158$ lines $\ell$.

Since $A$ omits $1112x$ and $111x2$ for $x=1,3$, we thus conclude (by considering the lines $11*2x$ and $11*x2$) that $A$ must contain $1132x$, $113x2$, $1312x$, and $131x2$. Taking midpoints, we conclude that $A$ omits $11322$ and $13122$. But together with $11122$ this implies that at least three points are missing from $A \cap S_{3,5}$, contradicting the hypothesis $c(A)=78$.

\subsection{Elimination of $(8,39,78,0,0)$}

Now $A \cap S_{5,5}$ has eight points. By Lemma \ref{tech}, there are at least three pairs in this set which differ in two positions. As we can only eliminate two points from $S_{3,5}$, two of these pairs $(a,b), (c,d)$ must have the same midpoint $p$, and two other pairs $(a',b'), (c',d')$ must have the same midpoint $p'$, and $A$ contains $S_{3,5} \backslash \{p,p'\}$. As $p,p'$ are distinct, the plane containing $a,b,c,d$ is distinct from the plane containing $a',b',c',d'$.

Again consider the $160$ lines $\ell$ from the previous section. This time, the sum of the $|\ell \cap A|$ is $4b(A)+2c(A) = 312 = 156 \times 2$. But the two lines in the plane of $a,b,c,d$ passing through $p$, and the two lines in the plane of $a',b',c',d'$ passing through $p'$, have no points; thus we must have $|\ell \cap A|=2$ for the remaining $156$ lines $\ell$.

Without loss of generality we have $(a,b)=(11111,11133)$, $(c,d) = (11113,11131)$, thus $p = 11122$. By permuting the first three indices, we may assume that $p'$ is not of the form $x2y2z, x2yz2, xy22z, xy2z2$ for any $x,y,z=1,3$. Then we have $1112x \not \in A$ and $1122x \in A$ for every $x=1,3$, so by the preceding paragraph we have $1132x \in A$; similarly for $113x2, 1312x, 131x2$. Taking midpoints, this implies that $13122, 11322 \not \in A$, but this (together with 11122) shows that at least three points aremissing from $A \cap S_{3,5}$, contradicting the hypothesis $c(A)=78$.

\subsection{Six dimensions}

Now we establish the bound $c'_{6,3}=353$. In view of the lower bounds, it suffices to show that there does not exist a Moser set $A \subset [3]^5$ with $|A|=354$.

We argue by contradiction. Let $A$ be as above, and let $(a(A),\ldots,g(A))$ be the statistics of $A$.

\begin{lemma}\label{g6} $g(A)=0$. \end{lemma}

\begin{proof} For any four-dimensional slice $V$ of $A$, define $$S(V) := 15 a(V) + 5 b(V) + 5 c(V)/2 + 3d(V)/2 + e(V).$$ From Lemma \ref{dci} we see that $|A|$ is equal to $a(A)+b(A)$ plus the average of $S(V)$ where $V$ ranges over the twenty slices which are some permutation of the center slice $22****$.

If $g(A)=1$, then $a(A) \leq 32$ and $b(A) \leq 128$ by \eqref{alpha-1}. Meanwhile, $e(V)=g(A)=1$ for every center slice $V$, so from Lemma \ref{paretop-4}, one can show that $S(V) \leq 223.5$ for every such slice. We conclude that $|A| \leq 351.5$, a contradiction. \end{proof}

For any four-dimensional slice $V$ of $A$, define the \emph{defects} to be $$ D(V) := 356 - [4a(V)+6b(V)+10c(V)+20d(V)+60e(V)].$$ Define a \emph{corner slice} to be one of the permutations or reflections of $11****$, thus there are $60$ corner slices. From Lemma \ref{dci} we see that $356-|A|+f(A)=2+f(A)$ is the average of the defects of all the $60$ corner slices. On the other hand, from Lemma \ref{paretop-4} and a straightforward computation, one concludes

\begin{lemma}\label{defects} Let $A$ be a four-dimensional Moser set. Then $D(A) \geq 0$. Furthermore: \begin{itemize} \item If $A$ has statistics $(6,12,18,4,0)$, then $D(A)=0$. \item If $A$ has statistics $(5,12,18,4,0)$, $(5,12,12,4,1)$, or $(6,8,12,8,0)$, then $D(A)=4$. \item For all other $A$, $D(A) \geq 6$. \item If $a(A) = 4$, then $D(A) \geq 8$. \item If $a(A) \geq 7$, then $D(A) \geq 16$. \item If $a(A) \geq 8$, then $D(A) \geq 30$. \item If $a(A) \geq 9$, then $D(A) \geq 86$. \end{itemize} \end{lemma}

Define a \emph{family} to be a set of four parallel corner slices, thus there are $15$ families, which are all a permutation of $\{11****, 13****, 31****, 33**** \}$. We refer to the family $\{11****, 13****, 31****, 33**** \}$ as $ab****$, and similarly define the family $a*b***$, etc.

\begin{lemma}\label{f6} $f(A)=0$. \end{lemma}

\begin{proof} For any four-dimensional slice $V$ of $A$, define $$ s(V) := 12 a(V)+15 b(V)/2+20 c(V)/3+15 d(V)/2 + 12 e(V),$$ and define an \emph{edge slice} to be one of the $30$ permutations or reflections of $12****$. From double counting we see that $|A|-a(A)$ is equal to the average of the $30$ values of $s(V)$ as $V$ ranges over edge slices.

From Lemma \ref{paretop-4} one can verify that $s(V) \leq 336$, and that $s(V) \leq 296 = 336-40$ if $e(V)=1$. The number of edge slices $V$ for which $e(V)=1$ is equal to $5f(A)$, and so the average value of the $s(V)$ is at most $336 - \frac{40 \times 5}{30} f(A)$, and so $$ |A| - a(A) \leq 336 - \frac{40 \times 5}{30} f(A)$$ which we can rearrange (using $|A|=354$) as $$ a(A) \geq 18 + \frac{20}{3} f(A).$$ Suppose first that $f(A)=1$; then $a(A) \geq 25$. This means that in any given family, one of the four corner slices has an $a$ value of at least $7$, and thus by Lemma \ref{defects} has a defect of at least $16$. Thus the average defect is at least $4$; on the other hand, the average defect is $2+f(A)=3$, a contradiction.

Now suppose that $f(A) \geq 2$; then $a(A) \geq 32$. Then in any given family, there is a corner slice with an $a$ value at least $9$, or four slices with $a$ value at least $8$, leading to a total defect of at least $86$ by Lemma \ref{defects}. Thus the average defect is at least $21.5$; on the other hand, the average defect is $2+f(A) \leq 2+12$, a contradiction. \end{proof}

As a consequence of the above lemma, we see that the average defect of all corner slices is $2$, or equivalently that the total defect of these slices is $120$.

Call a corner slice \emph{good} if it has statistics $(6,12,18,4,0)$, and \emph{bad} otherwise. Thus good slices have zero defect, and bad slices have defect at least four. Since the average defect of the $60$ corner slices is $2$, there are at least $30$ good slices.

One can describe the structure of the good slices completely:

\begin{lemma}\label{sixt} The subset of $[3]^4$ consisting of the strings $1111, 1113, 3333, 1332, 1322, 1222, 3322$ and permutations is a Moser set with statistics $(6,12,18,4,0)$. Conversely, every Moser set with statistics $(6,12,18,4,0)$ is of this form up to the symmetries of the cube $[3]^4$. \end{lemma}

\begin{proof} This can be verified by computer ({\bf need details}). A computer-free proof can be found at \centerline{{\tt http://michaelnielsen.org/polymath1/index.php?title=Classification\_of\_\%286\%2C12\%2C18\%2C4\%2C0\%29\_sets}.} \end{proof}

As a consequence of this lemma, given any $x,y,z,w \in \{1,3\}$, there is a unique good Moser set in $[3]^4$ set whose intersection with $S_{1,4}$ is $\{x222, 2y22, 22z2, 222w\}$, and these are the only 16 possibilities. Call this set the \emph{good set of type $xyzw$}. It consists of \begin{itemize} \item The four points $x222, 2y22, 22z2, 222w$ in $S_{1,4}$; \item All $24$ elements of $S_{2,4}$ except for $xy22, x2z2, x22w, 2yz2, 2y2w, 22zw$; \item The twelve points $xYZ2$, $xY2W$, $x2ZW$, $XyZ2$, $Xy2W$, $2yZW$, $XYz2$, $X2zW$, $2YzW$, $XY2w$, $X2Zw$, $2YZw$ in $S_{3,4}$, where $X=4-x$, $Y=4-y$, $Z=4-z$, $W=4-w$; \item The six points $xyzw, xyzW, xyZw, xYzw, Xyzw, XYZW$ in $S_{4,4}$. \end{itemize}

We can use this to constrain the types of two intersecting good slices:

\begin{lemma}\label{pqs} Suppose that the $pq****$ slice is of type $xyzw$, and the $p*r***$ slice is of type $x'y'z'w'$, where $p,q,r,x,y,z,w,x',y',z',w'$ are in $\{1,3\}$. Then $x'=x$ iff $q=r$, and $y'z'w'$ is equal to either $yzw$ or $YZW$. If $x=r$ (or equivalently if $x'=q$), then $y'z'w'=yzw$. \end{lemma}

\begin{proof} By reflection symmetry we can take $p=q=r=1$. Observe that the $11****$ slice contains $111222$ iff $x=1$, and the $1*1***$ slice similarly contains $111222$ iff $x'=1$. This shows that $x=x'$.

Suppose now that $x=x'=1$. Then the $111***$ slice contains the three elements $111y22, 1112z2, 11122w$, and excludes $111Y22, 1112Z2, 11122W$, and similarly with the primes, which forces $yzw=y'z'w'$ as claimed.

Now suppose that $x=x'=3$. Then the $111***$ slice contains the two elements $111yzw, 111YZW$, but does not contain any of the other six points in $S_{6,6} \cap 111***$, and similarly for the primes. Thus $y'z'w'$ is equal to either $yzw$ or $YZW$ as claimed. \end{proof}

Now we look at two adjacent parallel good slices, such as $11****$ and $13****$. The following lemma asserts that such slices either have opposite type, or else will create a huge amount of defect in other slices:

\begin{lemma}\label{l18} Suppose that the $11****$ and $13****$ slices are good with types $xyzw$ and $x'y'z'w'$ respectively. If $x=x'$, then the $1*x***$ slice has defect at least $30$, and the $1*X***$ slice has defect at least $8$. Also, the $1**1**$, $1**3**$, $1***1*$, $1***3*$, $1****1$, $1****3$ slices have defect at least $6$. In particular, the total defect of slices beginning with $1*$ is at least $74$. \end{lemma}

\begin{proof} Observe from the $11****, 13****$ hypotheses that $a(1*x***)=9$ and $a(1*X***)=4$, which gives the first two claims by Lemma \ref{defects}. For the other claims, one sees from Lemma \ref{pqs} that the other six slices cannot be good; also, they have an $a$-value of $6$ and a $d$-value of at most $7$, and the claims then follow from Lemma \ref{defects}. \end{proof}

Now we look at two diagonally opposite parallel good slices, such as $11****$ and $13****$.

\begin{lemma}\label{l14} The $11****$ and $33****$ slices cannot both be good and of the same type. \end{lemma}

\begin{proof} Suppose not. By symmetry we may assume that $11****$ and $33****$ are of type $1111$. This excludes a lot of points from $22****$. Indeed, by connecting lines between the $11****$ and $33****$ slices, we see that the only points that can still survive in $22****$ are $221133, 221333, 221132, 223332$, and permutations of the last four indices. Double counting the lines $22133*$ and permutations we see that there are at most $12$ points one can place in the permutations of $221133, 221333, 221132$, and so the $22****$ slice has at most $16$ points. Meanwhile, the two five-dimensional slices $1*****, 3*****$ have at most $c'_{5,3} = 124$ points, and the other two four-dimensional slices $21****, 23****$ have at most $c'_{4,3} = 43$ points, leading to at most $16 + 124 * 2 + 43 * 2 = 350$ points in all, a contradiction. \end{proof}

\begin{lemma}\label{l19} It is not possible for all four slices in a family to be good. \end{lemma}

\begin{proof} Suppose not. By symmetry we may assume that $11****, 13****, 31****, 33****$ are good. By Lemma \ref{l14}, the $11****$ and $33****$ slices cannot be of the same type, and so they cannot both be of the opposite type to either $13****$ or $31****$. If $13****$ is not of the opposite type to $11****$, then by (a permutation of) Lemma \ref{l18}, the total defect of slices beginning with $1*$ is at least $74$; otherwise, if $13****$ is not of the opposite type to $33****$, then by (a permutation and reflection of) Lemma \ref{l18}, the total defect of slices beginning with $*3$ is at least $74$. Similarly, the total defect of slices beginning with $3*$ or $*1$ is at least $74$, leading to a total defect of at least $148$. But the total defect of all the corner slices is $2 \times 60 = 120$, a contradiction. \end{proof}

\begin{corollary}\label{l20} At most one family can have a total defect of at least $38$. \end{corollary}

\begin{proof} Suppose there are two families with defect at least $38$. The remaining thirteen family have defect at least $4$ by Lemma \ref{l19} and Lemma \ref{defects}, leading to a total defect of at least $38*2+13*4=128$. But the total defect is $2 \times 60 = 120$, a contradiction. \end{proof}

Actually we can refine this:

\begin{proposition} No family can have a total defect of at least $38$. \end{proposition}

\begin{proof} Suppose for contradiction that the $ab****$ family (say) had a total defect of at least $38$, then by Corollary \ref{l20} all other families have total defect at least $38$.

We claim that the $**ab**$ family can have at most two good slices. Indeed, suppose the $**ab**$ has three good slices, say $**11**, **13**, **33**$. By Lemma \ref{l14}, the $**11**$ and $**33**$ slices cannot be of the same type, and so cannot both be of opposite type to $**13**$. Suppose $**11**$ and $**13**$ are not of opposite type. Then by (a permutation of) Lemma \ref{l18}, one of the families $a*b***, *ab***, **b*a*, **b**a$ has a net defect of at least $38$, contradicting the normalisation.

Thus each of the six families $**ab**, **a*b*, **a**b, ***ab*, ***a*b$ have at least two bad slices. Meanwhile, the eight families $a*b***, a**b**, a***b*, a****b, *ab***, *a*b**, *a**b*, *a***b$ have at least one bad slice by Corollary \ref{l19}, leading to twenty bad slices in addition to the defect of at least $38$ arising from the $ab****$ slice. To add up to a total defect of $120$, we conclude from Lemma \ref{defects} that all bad slices outside of the $ab****$ family have a defect of four, with at most one exception; but then by Lemma \ref{l18} this shows that (for instance) the $1*1***$ and $1*3***$ slices cannot be good unless they are of opposite type. The previous argument then shows that the a*b*** slice cannot have three good slices, which increases the number of bad slices outside of $ab****$ to at least twenty-one, and now there is no way to add up to $120$, a contradiction. \end{proof}

\begin{corollary} Every family can have at most two good slices. \end{corollary}

\begin{proof} If for instance $11****, 13****, 33****$ are both good, then by Lemma \ref{l14} at least one of $11****, 33****$ is not of the opposite type to $13****$, which by Lemma \ref{l18} implies that there is a family with a total defect of at least $38$, contradicting the previous proposition. \end{proof}

From this corollary and Lemma \ref{defects}, we see that every family has a defect of at least $8$. Since there are $15$ families, and $8 \times 15$ is exactly equal to $120$, we conclude

\begin{corollary}\label{coda} Every family has \emph{exactly} two good slices, and the remaining two slices have defect $4$. In particular, by Lemma \ref{defects}, the bad slices must have statistics $(5,12,18,4,0)$, $(5,12,12,4,1)$, or $(6,8,12,8,0)$. \end{corollary}

We now limit how these slices can interact with good slices.

\begin{lemma}\label{goodgood} Suppose that $1*1***$ is a good slice. \begin{itemize} \item[(i)] The $11****$ slice cannot have statistics $(6,8,12,8,0)$. \item[(ii)] The $11****$ slice cannot have statistics $(5,12,12,4,1)$. \item[(iii)] If the $11****$ slice has statistics $(5,12,18,4,0)$, then the $112***$ slice has statistics $(3,9,3,0)$. \end{itemize} \end{lemma}

\begin{proof} This can be verified through computer search; there are $16$ possible configurations for the good slices, and one can calculate that there are $2750$ configurations for the $(5,12,12,4,1)$ slices, $4368$ configurations for the $(5,12,18,4,0)$ slices, and $10000$ configurations for the $(6,8,12,8,0)$ slices. {\bf we could put human proofs for all this somewhere, presumably.}

%We first prove (i). Suppose for contradiction that the $11****$ slice has statistics $(6,8,12,8,0)$, then $A$ contains $111222$, and so the $1*1***$ slice is of type $1xyz$ for some $x,y,z$. By symmetry we may assume it is of type $1111$, thus the $111***$ slice consists of %$111111, 111113, 111332, 111322, 111222$ and permutations of the last three indices. On the other hand, the $11****$ slice has all eight of the points in $11**** \cap S_{2,6}$. Drawing lines between these points and $111111, 111113$ and permutations, we see that the $113***$ slice cannot contain $113111, 113113, 113133$, or permutations, leaving $113333$ as the only possible element of $113*** \cap S_{6,6}$. This makes $a(11****)=5$, a contradiction. \end{proof}

\begin{corollary}\label{slic} The $111***$ slice has statistics $(4,3,3,1)$, $(2,6,6,0)$, $(3,3,3,1)$, or $(1,6,6,0)$. \end{corollary}

\begin{proof} From Corollary \ref{coda}, we know that at least one of the slices $13****, 31****, 11****$ are good. If $11****$ or $1*1***$ is good, then the slice $111***$ has statistics $(4,3,3,1)$ or $(2,6,6,0)$, by Lemma \ref{sixt}. By symmetry we may thus reduce to the case where $13****$ is good and $1*1***$ is bad. Then by Lemma \ref{goodgood}, the $1*1***$ slice has statistics $(5,12,18,4,0)$ and the $121***$ slice has statistics $(3,9,3,0)$. Since the $131***$ slice, as a side slice of the good $13****$ slice, has statistics $(4,3,3,1)$ or $(2,6,6,0)$, we conclude that the $111***$ slice has statistics $(1,6,6,0)$ or $(3,3,3,1)$, and the claim follows. \end{proof}

\begin{corollary}\label{slic2} All corner slices have statistics $(6,12,18,4,0)$ or $(5,12,18,4,0)$. \end{corollary}

\begin{proof} Suppose first that a corner slice, say $11****$ has statistic $(6,8,12,8,0)$. Then $111***$ and $113***$ contain one ``d point each, and have six ``a points between them, so by Corollary \ref{slic}, they both have statistic $(3,3,3,1)$. This forces the $1*1***$, $1*3***$ slices to be bad, which by Corollary \ref{coda} forces the $3*1***,3*3***$ slices to be good. This forces the $311***, 313***$ slices to have statistics either $(2,6,6,0)$ or $(4,3,3,1)$. But the $311***$ slice (say) cannot have statistic $(4,3,3,1)$, since when combined with the $(3,3,3,1)$ statistics of $111***$ would give $a(*11***)=7$, which contradicts Corollary \ref{coda}; thus the $311***$ slice has statistic $(2,6,6,0)$, and similarly for $331***$. But then $a(3*1***)=4$, which again contradicts Corollary \ref{coda}.

Thus no corner slice has statistic $(6,8,12,8,0)$. Now suppose that a corner slice, say $11****$ has statistic $(5,12,12,4,1)$. By Lemma \ref{goodgood}, the $1*1***, 1*3***$ slices are bad, so by repeating the preceding arguments we conclude that the $311***, 313***$ slices have statistics $(2,6,6,0)$ or $(4,3,3,1)$; in particular, their $a$-value is even. However, the $*11***$ and $*13***$ slices are bad by Lemma \ref{goodgood}, and thus have an $a$-value of $5$; thus the $111***$ and $113***$ slices have an odd $a$-value. Thus forces $a(11****)$ to be even; but it is equal to $5$, a contradiction. \end{proof}

From this and Lemma \ref{dci}, we see that $A$ has statistics $(22,72,180,80,0,0,0)$. In particular, we have $2\alpha_2(A)+\alpha_3(A) = 2$, which by double counting (cf. \eqref{alpha-1}) shows that for every line of the form $12222*$ (or a reflection or permutation thereof) intersects $A$ in exactly two points. Note that such lines connect a ``$d$ point to two ``$c$ points.

Also, we observe that two adjacent ``$d$ points, such as $111222$ and $113222$, cannot both lie in $A$; for this would force the $*13***$ and $*11***$ slices to have statistics $(4,3,3,1)$ or $(3,3,3,1)$ by Corollary \ref{slic}, which forces $a(*1****)=6$, and thus $*1****$ must be good by Corollary \ref{slic2}; but this contradicts Lemma \ref{sixt}. Since $\alpha_3(A)=1/2$, we conclude that given any two adjacent ``$d$ points, exactly one of them lies in $A$. In particular, the d points of the form $***222$ consist either of those strings with an even number of $1$s, or those with an odd number of $1$s.

Let's say it's the former, thus the set contains $111222, 133222$, and permutations of the first three coordinates, but omits $113222, 333222$ and permutations of the first three coordinates. Since the ``$d$ points $113222, 333222$ are omitted, we conclude that the ``$c$ points $113122, 113322, 333122, 333322$ must lie in the set, and similarly for permutations of the first three and last three coordinates. But this gives at least $15$ of the $16$ ``$c$ points ending in $22$; by symmetry this leads to $225$ $c$-points in all; but $c(A)=180$, contradiction. This (finally!) completes the proof that $c'_{6,3}=353$.