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_{i,n}|$ thus we have $$ 0 \leq a_i(A) \leq |S_{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_{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_{i+1,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_{i,n-1}$). \item Randomly choose an element of $S_{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_{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_{i,n}$. Assign $4-x_j$ to $\overline{x_j}$ for all $1 \leq j \leq n$. \item Pick a random string in $S_{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_{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.
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}).
A brute-force search of the $2^{27}$ subsets of $[3]^3$ reveals that
\begin{lemma}\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}
This then 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*}
{\bf It may be possible to prove these inequalities by hand, thus avoiding the need for brute-force search. Also, only the first, second, and fourth of these inequalites is needed in the sequel.}
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$.
\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 further 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}. Below we give an (admittedly rather lengthy) alternate proof of the same facts, which is computer-free except for its (heavy) reliance on Lemma \ref{paretop}. \end{remark}
\subsection{Proof of (i)}
Let $e=1$; our task is to show that $|A| < 40$. From \eqref{eleven} we have $$ 8 \beta(A) + 6 \gamma(A) + 6 \delta(A) + 2 \leq 11$$ or equivalently that \begin{equation}\label{e1}
b+c+3d \leq 36;
\end{equation}
meanwhile, from \eqref{alpha-1} we have \begin{equation}\label{e2} a \leq 8; b \leq 16; c \leq 12 \end{equation} and hence $$ 3|A| = 3a+3b+3c+3d+3e \leq 3 \times 8 + 2 \times 16 + 2 \times 12 + 36 + 3 < 3 \times 40$$ and the claim follows.
\subsection{Proof of (v)}
From \eqref{eleven} we have $$ b+c+3d+8e \leq 44$$ while from \eqref{eight} we have $$ 4a+b+c+d \leq 64$$ and hence $$ 4|A|+6d+20e = 3(b+c+3d+8e)+(4a+b+c+d) \leq 196$$ and thus $$ d \geq \frac{196-4|A|}{6} \geq 6$$ as required.
\subsection{Proof of (vi), (vii)}
From \eqref{six} we have \begin{equation}\label{six2}
2a+b+c+d \leq 48.
\end{equation} If $|A| \geq 42$, then by (i), $e=0$; subtracting \eqref{six2} from $2|A|=2a+2b+2c+2d$ one concludes that $$ b+c+d \geq 2|A|-48.$$ On the other hand, from \eqref{alpha-2} we have $$ 3b+2c+3d \leq 96$$ and thus $c \geq 3(2|A|-48) - 96$, and the claims (vi), (vii) follow.
\subsection{Proof of (ii)}
Suppose for contradiction that $|A|=43$ and $d \geq 1$. By rotation we may assume that $1222 \in A$, thus by Lemma \ref{paretop} the slice $|A \cap 1***|$ has at most $13$ points. By (vi), $c \geq 18$. On the other hand, $c = c(1***)+b(2***)+c(3***) \leq c(1***)+12+c(3***)$. By Lemma \ref{paretop} (or by considering lines with midpoint $12222$) $b(2***) \leq 3$, and thus $c(3***) \geq 3$. By Lemma \ref{paretop} again this forces $|A \cap 3***| \leq 14$. Since $|A \cap 2***| \leq 16$, we must therefore have $|A \cap 1***|=13$, $|A \cap 2***|=16$, and $|A \cap 3***|=14$. From Lemma \ref{paretop}, the slice $2***$ must have statistics $(4,12,0,0)$, and the slice $1***$ has statistics either $(4,6,2,1)$ or $(3,6,3,1)$. As $A$ contains all of $2*** \cap S_{2,4}$ and six points in $1*** \cap S_{1,4}$, it must avoid six points in $3*** \cap S_{3,4}$, thus $b(3***) \leq 6$; by Lemma \ref{paretop} this forces $3***$ to have statistics $(2,6,6,0)$, $(3,6,5,0)$, or $(4,6,4,0)$. In particular we see that $b = b(1***)+a(2***)+b(3***)=16$ and $d=d(1***)+c(2***)+d(3***)=1$.
Now we look at the $*1**,*2**,*3**$ slices. We have $c(*2**)=1$ and so $b(*2**) \leq 10$ (this can be seen either from Lemma \ref{paretop} or by considering the lines $12x2$, $122x$). Since $c =c(*1**)+b(*2**)+c(*3**)$ is at least $18$, and $c(*1**), c(*3**) \leq 6$, we conclude that $c(*1**), c(*3**) \geq 2$, which by Lemma \ref{paretop} implies that $|A \cap *1**|, |A \cap *3**| \leq 14$. But from $c(*2**)=1$ and Lemma \ref{paretop} we have $|A cap *2**| \leq 14$ as well, leading to $|A| \leq 14+14+14=52$, a contradiction.
\subsection{Proof of (iv)}
Suppose for contradiction that $|A| \geq 41$ and $d \geq 4$. Suppose that $A$ contains two antipodal $d$-points, e.g. $1222$ and $3222$. Then by Lemma \ref{paretop}, $|A \cap 1***|, |A \cap 3***| \leq 13$. Meanwhile, the center slice $2****$ contains $d-2 \geq 2$ $c$-points, so by Lemma \ref{paretop}, $|A \cap 2***| \leq 14$, thus $|A| \leq 13+14+13=40$, a contradiction. So we may assume that no two of the four $d$-points are antipodal; by symmetry we may thus assume that $A$ contains $1222, 2122, 2212, 2221$.
Since $d(1***)=1$, we see from Lemma \ref{paretop} that $|A \cap 1***| \leq 13$. Meanwhile, $|A \cap 3***| \leq c'_{3,3}=16$, thus $|A \cap 2***| \geq 12$. Also, $c(2***)=3$, so by Lemma \ref{paretop} we have $a(2***) \leq 5$. Similarly for permutations; by Lemma \ref{dci} we conclude that $b \leq 20$.
Now suppose that $a(2***)=5$, then by Lemma \ref{paretop} (and $c(2***)=3$) we have $|A \cap 2***| \leq 12$. Since $|A \cap 1***| \leq 13$ and $|A \cap 3***| = 16$, we must have equality for all these slices since $41=12+13+16$. Applying Lemma \ref{paretop} we see that $A \cap 2***$, $A \cap 1***$, $A\cap 3***$ has statistics $(5,4,3,0)$, $(3,6,3,0)$ or $(4,6,2,0)$, and $(4,12,0,0)$ respectively. In particular $b =6+5+12=23 > 20$, a contradiction. Thus $a(2***) \leq 4$, and similarly for permutations; thus by Lemma \ref{dci} $b \leq 16$.
Suppose now that $a(2***) \leq 3$. Again from Lemma \ref{paretop} we have $|A \cap 2***| \leq 13$ and $|A \cap 1***|\leq 13$, which forces $|A \cap 3***| \geq 41-13-13=15$ which (by Lemma \ref{paretop}) forces $b(3***) \geq 11$. Since $b \leq 16$ this forces $b(1***) \leq 5$, which by Lemma \ref{paretop} forces $|A \cap 1***| \leq 12$, which forces $|A \cap 3***| = 16$ and $|A \cap 2***|=13$, which forces $b(3***) \geq 12$ and $a(2***)=3$, $b(1***) \leq 1$, which forces $|A \cap 1***| < 12$, leading to a contradiction since $12+16+13=41$. Thus we must have $a(2***)=4$, and similarly for permutations; in particular, $b$ is exactly $16$.
From Lemma \ref{paretop} $|A \cap 2***| \leq 14$. Suppose that $|A \cap 3***| > 14$, then by Lemma \ref{paretop} $b(3***) \geq 11$; since $a(2***)=4$ and $b=16$ we conclude $b(1***) \leq 1$, which by Lemma \ref{paretop} forces $|A \cap 1***| \leq 9$, and now there are at most $9+14+16 = 39$ points in $A$, a contradiction. Thus we must have $|A \cap 3***| \leq 14$, thus $|A \cap 1***| \geq 13$, which by Lemma \ref{paretop} (and $d(1***)=1$) forces $b(1***)=6$, and similarly for permutations.
Now look at the points $3112, 1312, 1132$. The midpoint of any two of these is known to lie in $A$, so at least two of them lie outside of $A$. Suppose that $1312, 1132 \not \in A$. The pair $\{1312,1132\}$ is a pair in $1*** \cap S_{3,4}$ with midpoint $1222 \in A$. There are five other such pairs, each of which can have at most one point in $A$, and thus $b(1***) \leq 5$, giving the required contradiction.
\subsection{Proof of (iii)}
Suppose for contradiction that $|A| \geq 42$ and $d \geq 3$. By (ii), (iv) we have $|A|=42$ and $d=3$. Also, by the first paragraph in the proof of (iv), $A$ cannot contain a pair of antipodal $d$-points. Thus without loss of generality we may assume that $A$ contains $1222, 2122, 2212$.
Since $d(1***)=1$, we see from Lemma \ref{paretop} that $|A \cap 1***| \leq 13$. Meanwhile, $|A \cap 3***| \leq c'_{3,3}=16$, thus $|A \cap 2***| \geq 13$. Also, $c(2***)=2$, so by Lemma \ref{paretop} we have $a(2***) \leq 4$. Similarly $a(*2**), a(**2*) \leq 4$. Meanwhile, $c(***2)=3$, so by Lemma \ref{paretop} $a(***2) \leq 5$; thus by Lemma \ref{dci} $b \leq 17$.
Suppose now that $a(2***) \leq 3$. Again from Lemma \ref{paretop} we have $|A \cap 2***| \leq 13$ and $|A \cap 1***|\leq 13$, which forces $|A \cap 3***| \geq 41-13-13=16$ which (by Lemma \ref{paretop}) forces $b(3***) = 12$. Since $b \leq 17$ this forces $b(1***) \leq 5$, which by Lemma \ref{paretop} forces $|A \cap 1***| \leq 12$, which forces $|A \cap 3***| > 16$, a contradiction. Thus we must have $a(2***)=4$, and similarly $a(*2**)=a(**2*)=4$.
If $|A \cap 3***| \geq 15$, then by Lemma \ref{paretop} we have $b(3***) \geq 11$; since $b \leq 17$ and $a(2***)=4$ this forces $b(1***) \leq 2$. Together with $d(1***)=1$ and Lemma \ref{paretop}, this implies $|A \cap 1***| \leq 10$, which gives $42=|A| \leq 10+14+16=40$, a contradiction. Thus we have $|A \cap 3***| \leq 14$; since $|A \cap 2***| \leq 14$ and $|A \cap 1***| \leq 13$, this forces $|A \cap 1***|=13$, which by Lemma \ref{paretop} forces $b(1***)=6$. But by repeating the final paragraph of the proof of (iv) we see (without loss of generality) that $b(1***) \leq 5$, giving the required contradiction.
\subsection{Proof of (viii)}
If $|A|=43$, then by (i), (ii) we have $d=e=0$, and then by \eqref{six2} we have $a \leq 5$. Since we trivially have $c \leq 24$, the only set of statistics that are not consistent with the claim $b \geq 15$ is $(5,14,24,0,0)$. But this contradicts \eqref{eleven}.
\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}
To get bounds in the six-dimensional case, we need to return to the four and five dimensional cases and establish some additional inequalities there. Our bounds will now rely much more heavily on computer computations; we give only a sketch of the arguments here.
We begin with a four-dimensional estimate.
\begin{proposition}\label{denso} Let $A \subset [3]^4$ be a Moser set with statistics $(a,b,c,d,e)$, and let $(\alpha,\beta,\gamma,\delta,\epsilon)$ be the associated densities. Then $4 \alpha + 2 \beta + 3 \gamma + 2 \delta + \epsilon \le 6$ and $8\alpha+2\beta+3\gamma+2\delta+\epsilon \leq 8$. \end{proposition}
\begin{proof} Consider the three-dimensional subspace $V := \{ xxyz: x,y,z \in [3] \}$ in $[3]^4$. We define the relative statistics $\alpha_V,\ldots,\epsilon_V$ for this subspace as $$ \alpha_V := \frac{|A \cap V \cap S_{4,4}|}{|V \cap S_{4,4}|}, \ldots, \epsilon_V := \frac{|A \cap V \cap S_{0,4}|}{|V \cap S_{0,4}|}$$ (note that these numbers are distinct from the densities $\alpha(V),\ldots,\delta(V)$ used in preceding sections). A computer exhaustion of the $2^{27}$ different subsets of $V$ reveals that the inequalities $$4 \alpha_V + 2 \beta_V + 3 \gamma_V + 2 \delta_V + \epsilon_V \le 6$$ and $$8\alpha_V+2\beta_V+3\gamma_V+2\delta_V+\epsilon_V \leq 8$$ hold for all Moser sets $A$. Of course, the same bounds then follow for all other spaces obtained from $V$ by the symmetries of the cube. Averaging over all such spaces gives the claim. \end{proof}
\begin{proposition} Let $A \subset [3]^4$ be a Moser set with statistics $(a,b,c,d,e)$. Then $a+b+c+d+5e \leq 43$ and $a+b+c+\frac{3}{2}d+4e \leq 43$. \end{proposition}
\begin{proof} The first inequality follows from the bound $|A| \leq c'_{4,3}=43$ and Proposition \ref{stat}(i), so we turn to the second inequality.
If $e=0$, then $a+b+c+\frac{3}{2}d+4e = |A| + \frac{1}{2} d$. The claim then follows from Proposition \ref{stat}(ii)-(v), and the trivial bound $d \leq 8$ for the cases $|A| < 40$. So we may assume that $e=1$. But then we have \eqref{e1}, \eqref{e2}, and so \begin{align*} a+b+c+\frac{3}{2}d+4e &= a+\frac{b+c}{2} + \frac{b+c+3d}{2} + 4 \\ &\leq 8 + \frac{16+12}{2} + \frac{36}{2} + 4 \\ &= 44. \end{align*} We need to show that $a+b+c+\frac{3}{2}d+4e \leq 43$. An inspection of the above argument shows that we are done unless $a=8$ and $(b+c, b+c+3d)$ is equal to $(28,36)$, $(28,35)$, or $(27,36)$. Since $b+c$ and $b+c+3d$ differ by a multiple of $3$, we must therefore have $b+c=27$ and $b+c+3d=36$, thus $d=3$. But these possibilities contradict Proposition \ref{denso}. \end{proof}
These inequalities for four-dimensional Moser sets of course imply inequalities for higher dimensional Moser sets also, by Proposition \ref{prop}.
In five dimensions, one can modify the proof of Proposition \ref{denso} to give additional inequalities. For instance, by considering the three-dimensional space $\{ xxyyz: x,y,z \in [3]\}$ and averaging over symmetries, one can establish the inequalities \begin{align*}
4\alpha+1\beta+2\gamma+2\delta+1\epsilon+1\zeta &\le \frac{11}{2} \\
24\alpha+0\beta+4\gamma+2\delta+1\epsilon+1\zeta &\le 6 \\
4\alpha+2\beta+2\gamma+2\delta+1\epsilon+1\zeta &\le 6 \\ 7\alpha+1\beta+2\gamma+2\delta+1\epsilon+1\zeta & \le 7 \\ 8\alpha+0\beta+4\gamma+2\delta+1\epsilon+1\zeta &\le 8 \\ 8\alpha+2\beta+2\gamma+2\delta+1\epsilon+1\zeta &\le 8 \\ 4\alpha+2\beta+0\gamma+2\delta+2\epsilon+1\zeta &\le 6\\ 8\alpha+2\beta+0\gamma+2\delta+2\epsilon+1\zeta &\le 8
\end{align*} for the densities $\alpha,\beta,\gamma,\delta,\epsilon,\zeta$ of Moser sets $A \subset [3]^5$, while from considering the space $\{ xxxyz: x,y,z \in [3]\}$ one instead obtains \begin{align*} 8\alpha+4\beta+2\gamma+2\delta+4\epsilon+2\zeta &\leq 11\\ 4\alpha+2\beta+1\gamma+2\delta+2\epsilon+1\zeta &\leq 6\\ 4\alpha+4\beta+1\gamma+0\delta+2\epsilon+1\zeta &\leq 6\\ 7\alpha+2\beta+1\gamma+1\delta+2\epsilon+1\zeta &\leq 7\\ 8\alpha+2\beta+1\gamma+2\delta+2\epsilon+1\zeta &\leq 8\\ 4\alpha+0\beta+2\gamma+0\delta+0\epsilon+1\zeta &\leq 4\\ 4\alpha+0\beta+2\gamma+2\delta+2\epsilon+1\zeta &\leq 6\\ 8\alpha+0\beta+2\gamma+2\delta+2\epsilon+1\zeta &\leq 8\\ 8\alpha+4\beta+1\gamma+0\delta+2\epsilon+1\zeta &\leq 8 \end{align*}
Inserting all the inequalities already established for five dimensions into standard integer programming package (e.g. the one provided by Maple 12), one obtains that $a+b+c+d+e+f \leq 117$ whenever $f=1$. Since we have already established $a+b+c+d+e+f \leq c'_{5,3}=124$ in general, we conclude the new inequality $$ a+b+c+d+e+7f \leq 124.$$
These inequalities of course carry over to give inequalities for six dimensions. Furthermore, by repeating the Proposition \ref{denso} argument with the space $\{ xxxxyz: x,y,z \in [3]\}$ one obtains \begin{align*} 8\alpha+4\beta+2\gamma+2\epsilon+4\zeta+2\eta &\leq 11\\ 0\alpha+0\beta+2\gamma+0\epsilon+0\zeta+1\eta &\leq 2\\ 4\alpha+2\beta+1\gamma+2\epsilon+2\zeta+1\eta &\leq 6\\ 7\alpha+2\beta+1\gamma+1\epsilon+2\zeta+1\eta &\leq 7\\ 4\alpha+0\beta+2\gamma+0\epsilon+0\zeta+1\eta &\leq 4\\ 4\alpha+0\beta+2\gamma+2\epsilon+2\zeta+1\eta &\leq 6\\ 8\alpha+0\beta+2\gamma+2\epsilon+2\zeta+1\eta &\leq 8\\ 8\alpha+2\beta+1\gamma+2\epsilon+2\zeta+1\eta &\leq 8\\ 4\alpha+4\beta+1\gamma+0\epsilon+2\zeta+1\eta &\leq 6\\ 8\alpha+4\beta+1\gamma+0\epsilon+2\zeta+1\eta &\leq 8 \end{align*} for the densities $\alpha,\beta,\gamma,\delta,\epsilon,\zeta,\eta$ of Moser sets $A \subset [3]^6$ (note that the $xxxxyz$ strings never contribute to the $\delta$ density), and similarly by using the space $\{ xxxyyz: x,y,z \in [3]\}$ one obtains \begin{align*} 4\alpha+2\beta+0\gamma+3\delta+1\epsilon+1\zeta+1\eta &\leq 6\\ 4\alpha+0\beta+2\gamma+3\delta+1\epsilon+1\zeta+1\eta &\leq 6\\ 8\alpha+2\beta+0\gamma+3\delta+1\epsilon+1\zeta+1\eta &\leq 8\\ 8\alpha+0\beta+2\gamma+3\delta+1\epsilon+1\zeta+1\eta &\leq 8\\ 0\alpha+4\beta+0\gamma+0\delta+2\epsilon+0\zeta+1\eta &\leq 4\\ 0\alpha+0\beta+4\gamma+0\delta+0\epsilon+2\zeta+1\eta &\leq 4\\ 8\alpha+4\beta+0\gamma+0\delta+2\epsilon+0\zeta+1\eta &\leq 1\\ 8\alpha+0\beta+4\gamma+0\delta+0\epsilon+2\zeta+1\eta &\leq 1 \end{align*} Using all these inequalities and applying a standard integer programming package, we obtained the linear inequality $$ a+b+c+d+e+f+g \leq 361.$$
One can of course continue this method for higher dimensions, but the bounds seem to become far less tight in those cases. In particular, the inequalities propagated by Lemma \ref{prop} seem to be less powerful once the density $|A|/3^n$ drops below $1/2$, which is the case in six and higher dimensions.
