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 96$ 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. By symmetry, one assumes 1222,2122,2212 and 2221 are in the set. Then 18 of the 24 'c' points with two 2s must be included; it is quick to check that 1122 and permutations must be the six excluded. Next, one checks that the only possible set of six 'a' points with no 2s is 1111,1113,3333 and permutations. Lastly, in a rather longer computation, one finds there is only possible set of twelve 'b' points, that is points with one 2. 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 $33****$.

\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} no 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, ****ab$ 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 all 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 $27520$ configurations for the $(5,12,12,4,1)$ slices, $4368$ configurations for the $(5,12,18,4,0)$ slices, and $80000$ 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 $11122*$ (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$.