Moser.tex - Revision history

Teorth at 06:42, 16 January 2010

2010-01-16T06:42:18Z

Teorth at 23:12, 25 July 2009

2009-07-25T23:12:41Z

← Older revision		Revision as of 16:12, 25 July 2009
Line 223:		Line 223:

	\begin{figure}[tb]		\begin{figure}[tb]
	\~~centered~~{\tiny		\begin{center}{\tiny
	$(3, 16, 24, 0, 0)$,		$(3, 16, 24, 0, 0)$,
	$(4, 14, 19, 2, 0)$,		$(4, 14, 19, 2, 0)$,
Line 613:		Line 613:
	$(14, 8, 0, 0, 0)$,		$(14, 8, 0, 0, 0)$,
	$(15, 4, 0, 0, 0)$,		$(15, 4, 0, 0, 0)$,
	$(16, 0, 0, 0, 0)$}}		$(16, 0, 0, 0, 0)$}
			\end{center}
	\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}}		\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}		\label{table4}

Teorth at 22:52, 25 July 2009

2009-07-25T22:52:00Z

← Older revision		Revision as of 15:52, 25 July 2009
Line 923:		Line 923:
	\item For all other $A$, $D(A) \geq 6$.		\item For all other $A$, $D(A) \geq 6$.
	\item If $a(A) = 4$, then $D(A) \geq 8$.		\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 7$, then $D(A) \geq 16$ (with equality iff $A$ has statistics $(7,11,12,6,0)$).
	\item If $a(A) \geq 8$, then $D(A) \geq 30$.		\item If $a(A) \geq 8$, then $D(A) \geq 30$.
	\item If $a(A) \geq 9$, then $D(A) \geq 86$.		\item If $a(A) \geq 9$, then $D(A) \geq 86$.
Line 936:		Line 936:
	\begin{proof} For any four-dimensional slice $V$ of $A$, define		\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),$$		$$ 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.		and define an \emph{edge slice} to be one of the $60$ permutations or reflections of $12****$. From double counting we see that $\|A\|-a(A)$ is equal to the average of the $60$ 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		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}{60} f(A)$, and so
	$$ \|A\| - a(A) \leq 336 - \frac{40 \times 5}{30} f(A)$$		$$ \|A\| - a(A) \leq 336 - \frac{40 \times 5}{60} f(A)$$
	which we can rearrange (using $\|A\|=354$) as		which we can rearrange (using $\|A\|=354$) as
	$$ a(A) \geq 18 + \frac{20}{3} f(A).$$		$$ a(A) \geq 18 + \frac{10}{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~~.		Suppose first that $f(A) \geq 3$; then $a(A) \geq 28$. 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 $7$, or two slices with $a$ value at least $8$, or one slice with $a$ value $8$ and two of $a$ value at least $7$, leading to a total defect of at least $60$ by Lemma \ref{defects}. Thus the average defect is at least $15$; on the other hand, the average defect is $2+f(A) \leq 2+12$, a contradiction.

			Now suppose that $f(A)=2$; 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)=4$. From Lemma \ref{defects}, this implies that in any given family, three of the corner slices have statistics $(6,12,18,4,0)$ and the last one has statistics $(7,11,12,6,0)$. But this forces $b(A)=70.5$ by double counting, which is absurd.

			The remaining case is when $f(A)=1$. Here we need a different argument. Without loss of generality we may take $122222 \in A$. The average defect among all $60$ slices is $2+f(A)=3$. Equivalently, the average defect among all $15$ families is $12$.

			First suppose that $a(A) \neq 24$. Then in every family, at least one of the corner slices needs to have an $a$ value distinct from six, and so the average defect in each family is at least $4$. Thus the five families $ab***, ab*, ab, ab, a****b$ have an average defect of at most $28$, which implies that the ten corner slices beginning with $1$ (or equivalently, adjacent to an edge slice containing $122222$) is at most $14$. In other words, if $(a,b,c,d,e)$ is the average of the statistics of these ten corner slices, then
			$$ 4a+6b+10c+20d+60e \geq 342.$$
			On the other hand, $(a,b,c,d,e)$ must lie in the convex hull of the statistics of four-dimensional Moser sets, which are described by Lemma \ref{paretop}. Also, as $A$ contains $122222$, one has $c/24, d/8, e \leq 1/2$ by considering lines with centre $122222$. Finally, from \eqref{six} and double-counting one has $7c/24 + 3d/8 + 3e + 1 \leq 6$. Inserting these facts into a standard linear program yield a contradiction (indeed, the maximal value of $4a+6b+10c+20d+60e$ with these constraints is $338 \frac{2}{3}$, attained when $(a,b,c,d,e) = (\frac{17}{3}, 16, 12, 4, \frac{1}{3})$).

			Finally, we consider the case when $f(A)=1$ and $a(A)=24$. The preceding arguments allow the average defect of the ten corner slices beginning with $1$ can be as large as $18$, which implies that $4a+6b+10c+20d+60e \geq 338$. Linear programming shows that this is not possible if $a \geq 6$, thus $a<6$. But this forces one of the corner slices beginning with $3$ to have an $a$ value of at least $7$, and thus to have a defect of at least $16$ by Lemma \ref{paretop}. Repeating the preceding arguments, this increases the lower bound for $4a+6b+10c+20d+60e$ by $\frac{16}{10}$, to $339.6$; but this is now inconsistent with the upper bound of $338 \frac{2}{3}$ from linear programming.
	\end{proof}		\end{proof}

Mpeake at 03:48, 23 July 2009

2009-07-23T03:48:03Z

← Older revision		Revision as of 20:48, 22 July 2009
Line 1,062:		Line 1,062:
	\end{proof}		\end{proof}

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

Mpeake at 12:22, 22 July 2009

2009-07-22T12:22:47Z

← Older revision		Revision as of 05:22, 22 July 2009
Line 1,018:		Line 1,018:
	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 $ab*, ab*, ba, ba$ has a net defect of at least $38$, contradicting the normalisation.		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 $ab*, ab*, ba, ba$ has a net defect of at least $38$, contradicting the normalisation.

	Thus each of the six families $ab, *ab, ab, *ab, **ab$ have at least two bad slices. Meanwhile, the eight families $ab, ab, ab, a***b, ab**, ab, a*b, ab$ 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 $11**$ and $13**$ slices cannot be good unless they are of opposite type. The previous argument then shows that the ab* 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.		Thus each of the six families $ab, *ab, ab, *ab, **ab, ***ab$ have at least two bad slices. Meanwhile, the eight families $ab*, ab, ab, a***b, ab**, ab, a*b, ab$ 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 $11**$ and $13**$ slices cannot be good unless they are of opposite type. The previous argument then shows that the ab* 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}		\end{proof}

Line 1,024:		Line 1,024:
	\end{corollary}		\end{corollary}

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

Mpeake at 12:04, 22 July 2009

2009-07-22T12:04:54Z

← Older revision		Revision as of 05:04, 22 July 2009
Line 1,042:		Line 1,042:
	\end{lemma}		\end{lemma}

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

Mpeake at 13:29, 20 July 2009

2009-07-20T13:29:03Z

← Older revision		Revision as of 06:29, 20 July 2009
Line 956:		Line 956:
	\end{lemma}		\end{lemma}

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

Mpeake at 06:45, 14 July 2009

2009-07-14T06:45:44Z

← Older revision		Revision as of 23:45, 13 July 2009
Line 988:		Line 988:
	\end{proof}		\end{proof}

	Now we look at two diagonally opposite parallel good slices, such as $11**$ and $13**$.		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.		\begin{lemma}\label{l14} The $11**$ and $33**$ slices cannot both be good and of the same type.
Line 1,014:		Line 1,014:
	\end{proposition}		\end{proposition}

	\begin{proof} Suppose for contradiction that the $ab****$ family (say) had a total defect of at least $38$, then by Corollary \ref{l20} ~~all~~ other families have total defect at least $38$.		\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 $ab*, ab*, ba, ba$ has a net defect of at least $38$, contradicting the normalisation.		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 $ab*, ab*, ba, ba$ has a net defect of at least $38$, contradicting the normalisation.

Mpeake at 06:44, 14 July 2009

2009-07-14T06:44:13Z

← Older revision		Revision as of 23:44, 13 July 2009
Line 910:		Line 910:
	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****$.		From Lemma \ref{dci} we see that $\|A\|$ is equal to $a(A)+b(A)$ plus the average of $S(V)$ where $V$ ranges over the twenty slices which are some permutation of the center slice $22****$.

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

Teorth at 06:48, 10 July 2009

2009-07-10T06:48:34Z

Show changes