Moser's cube problem - Revision history

Charles R Greathouse IV: fix OEIS link

2015-09-30T04:26:55Z

fix OEIS link

← Older revision		Revision as of 21:26, 29 September 2015
Line 1:		Line 1:
	Define a ''Moser set'' to be a subset of <math>[3]^n</math> which does not contain any [[geometric line]], and let <math>c'_n</math> denote the size of the largest Moser set in <math>[3]^n</math>. The first few values are (see [http://~~www~~.~~research.att.com/~njas/sequences~~/A003142 OEIS A003142]):		Define a ''Moser set'' to be a subset of <math>[3]^n</math> which does not contain any [[geometric line]], and let <math>c'_n</math> denote the size of the largest Moser set in <math>[3]^n</math>. The first few values are (see [http://oeis.org/A003142 OEIS A003142]):

	: <math>c'_0 = 1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43; c'_5 = 124; c'_6 = 353.</math>		: <math>c'_0 = 1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43; c'_5 = 124; c'_6 = 353.</math>

Teorth at 22:08, 9 July 2009

2009-07-09T22:08:16Z

← Older revision		Revision as of 15:08, 9 July 2009
Line 1:		Line 1:
	Define a ''Moser set'' to be a subset of <math>[3]^n</math> which does not contain any [[geometric line]], and let <math>c'_n</math> denote the size of the largest Moser set in <math>[3]^n</math>. The first few values are (see [http://www.research.att.com/~njas/sequences/A003142 OEIS A003142]):		Define a ''Moser set'' to be a subset of <math>[3]^n</math> which does not contain any [[geometric line]], and let <math>c'_n</math> denote the size of the largest Moser set in <math>[3]^n</math>. The first few values are (see [http://www.research.att.com/~njas/sequences/A003142 OEIS A003142]):

	: <math>c'_0 = 1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43; c'_5 = 124.</math>		: <math>c'_0 = 1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43; c'_5 = 124; c'_6 = 353.</math>

	Beyond this point, we only have some upper and lower bounds~~, in particular <math>353 \leq c'_6 \leq 354</math>~~; see [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg this spreadsheet] for the latest bounds.		Beyond this point, we only have some upper and lower bounds; see [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg this spreadsheet] for the latest bounds.

	The best known asymptotic lower bound for <math>c'_n</math> is		The best known asymptotic lower bound for <math>c'_n</math> is

Teorth: /* n=6 */

2009-07-09T22:07:20Z

n=6

← Older revision		Revision as of 15:07, 9 July 2009
Line 411:		Line 411:
	'''Note''': in the 353-point example given above, the 11** slices are good (and of type 1111), the 13 slices have statistics (5,12,18,4,0) and consist of the type 3333 slice with the point 133333 removed, and the 33** slices have statistics (6,8,12,8,0), with the slice consisting of the 6 a-points formed by permuting 1133, the 8 b-points formed by permuting 1112 and 3332, the 12 c-points formed by permuting 1122 and 3322, and all 8 d-points.		'''Note''': in the 353-point example given above, the 11** slices are good (and of type 1111), the 13 slices have statistics (5,12,18,4,0) and consist of the type 3333 slice with the point 133333 removed, and the 33** slices have statistics (6,8,12,8,0), with the slice consisting of the 6 a-points formed by permuting 1133, the 8 b-points formed by permuting 1112 and 3332, the 12 c-points formed by permuting 1122 and 3322, and all 8 d-points.

	We now show that it is impossible to have a 356-point set, i.e. one in which all corner slices are good. From the above discussion, we see that if the 111* slice contains its center 111222, then the 113* slice does not, and vice versa. ~~Tthus~~ the d points of the form ***222 consist either of those strings with an even number of 1s, or those with an odd number of 1s.		We now show that it is impossible to have a 356-point set, i.e. one in which all corner slices are good. From the above discussion, we see that if the 111* slice contains its center 111222, then the 113* slice does not, and vice versa. Thus the d points of the form ***222 consist either of those strings with an even number of 1s, or those with an odd number of 1s.

	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. Meanwhile, we see that the (24,72,180,80,0,0,0) set saturates the inequality 4c+3d \leq 960, which is only possible if every line connecting two “c” points to a “d” point meets exactly two elements in the set. 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, which is far too many.		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. Meanwhile, we see that the (24,72,180,80,0,0,0) set saturates the inequality 4c+3d \leq 960, which is only possible if every line connecting two “c” points to a “d” point meets exactly two elements in the set. 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, which is far too many.
Line 516:		Line 516:

	'''Proposition 24''' In any two diagonally opposite slices of a 354-point set, one slice is (6,12,18,4,0) and the other is (5,12,18,4,0), and both slices have the same type.		'''Proposition 24''' In any two diagonally opposite slices of a 354-point set, one slice is (6,12,18,4,0) and the other is (5,12,18,4,0), and both slices have the same type.

			On averaging, we see that the 354-point set has statistics (22,72,180,80,0,0,0).

			'''Theorem 25''' <math>c'_6 = 353</math>.

			'''Proof''' We repeat the previous argument that there is no 356-point set. Suppose for contradiction that we have a 356-point set, i.e. one in which all corner slices are good. From the above discussion, we see that if the 111* slice contains its center 111222, then the 113* slice does not, and vice versa. Thus the d points of the form ***222 consist either of those strings with an even number of 1s, or those with an odd number of 1s.

			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. Meanwhile, we see that the (22,72,180,80,0,0,0) set saturates the inequality 4c+3d \leq 960, which is only possible if every line connecting two “c” points to a “d” point meets exactly two elements in the set. 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, which is far too many.

	== Connection with Fujimura's Problem ==		== Connection with Fujimura's Problem ==

Teorth: /* n=6 */

2009-07-09T17:41:18Z

n=6

← Older revision		Revision as of 10:41, 9 July 2009
Line 515:		Line 515:
	We can define the notion of the "type" of a (5,12,18,4,0) set just as with a (6,12,18,4,0) set. The above observation forces any two adjacent slices (e.g. 11** and 13) to have opposing type, and thus any two diagonally opposite slices (e.g. 11 and 33**) have identical type. By Lemma 14, such slices cannot both be good. Splitting each family into two pairs of diagonally opposing slices, we thus conclude		We can define the notion of the "type" of a (5,12,18,4,0) set just as with a (6,12,18,4,0) set. The above observation forces any two adjacent slices (e.g. 11** and 13) to have opposing type, and thus any two diagonally opposite slices (e.g. 11 and 33**) have identical type. By Lemma 14, such slices cannot both be good. Splitting each family into two pairs of diagonally opposing slices, we thus conclude

	''Proposition 24'' In any two diagonally opposite slices of a 354-point set, one slice is (6,12,18,4,0) and the other is (5,12,18,4,0).		'''Proposition 24''' In any two diagonally opposite slices of a 354-point set, one slice is (6,12,18,4,0) and the other is (5,12,18,4,0), and both slices have the same type.

	== Connection with Fujimura's Problem ==		== Connection with Fujimura's Problem ==

Teorth at 17:40, 9 July 2009

2009-07-09T17:40:36Z

← Older revision		Revision as of 10:40, 9 July 2009
Line 3:		Line 3:
	: <math>c'_0 = 1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43; c'_5 = 124.</math>		: <math>c'_0 = 1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43; c'_5 = 124.</math>

	Beyond this point, we only have some upper and lower bounds, in particular <math>353 \leq c'_6 \leq ~~355~~</math>; see [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg this spreadsheet] for the latest bounds.		Beyond this point, we only have some upper and lower bounds, in particular <math>353 \leq c'_6 \leq 354</math>; see [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg this spreadsheet] for the latest bounds.

	The best known asymptotic lower bound for <math>c'_n</math> is		The best known asymptotic lower bound for <math>c'_n</math> is
Line 489:		Line 489:
	'''Corollary 23''' In a 354-point set, every family consists of ''exactly'' two good slices, plus two bad slices of defect exactly four.		'''Corollary 23''' In a 354-point set, every family consists of ''exactly'' two good slices, plus two bad slices of defect exactly four.

			Now we look at the statistics of center slices of 4D slices (e.g. the 112* stats of the 11** slice). Computer search has revealed the following

			* For a (6,12,18,4,0) slice, the central slice must be (3,9,3,0). [The other two slices are (4,3,3,1) and (2,6,6,0).]
			* For a (5,12,18,4,0) slice, the central slice must be (3,9,3,0). [The other two slices must add up to (5,9,9,1).]
			* For a (5,12,12,4,1) slice, the central slice must be (3,6,3,1). [The other two slices must add up to (5,9,6,1).]
			* For a (6,8,12,8,0) slice, the central slice must be (2,6,6,0). [The other two slices must add up to (6,6,6,2).]

			Now we look at a side 3D slice, e.g. 111*. Because at least two of 11, 13, 31, 33 must be of type (6,12,18,4,0), and such slices have 3D side slices of (4,3,3,1) and (2,6,6,0), we know that the 111* slice must be adjacent to either a (4,3,3,1) slice or a (2,6,6,0) slice. From the above list, we thus see that 111*** is one of the following possibilities:

			# It is a slice of a (6,12,18,4,0) set, and is therefore either (4,3,3,1) or (2,6,6,0).
			# It is a (3,3,3,1) slice of a (5,12,18,4,0) set, with the opposing slice being (2,6,6,0).
			# It is a (1,6,6,0) slice of a (5,12,18,4,0) set, with the opposing slice being (4,3,3,1).
			# It is a (3,3,0,1) slice of a (5,12,12,4,1) set, with the opposing slice being (2,6,6,0).
			# It is a (1,6,3,0) slice of a (5,12,12,4,1) set, with the opposing slice being (4,3,3,1).
			# It is a (2,3,3,1) slice of a (6,8,12,8,0) set, with the opposing slice being (4,3,3,1).

	If one ~~has~~ a 354-point set, ~~then~~ the ~~total defect~~ is ~~at most 120~~.		Furthermore, in all six cases, the opposing slice is a subslice of a (6,12,18,4,0) set.

			Possibility 6 has been eliminated by computer, and possibilities 4,5 have been eliminated by hand. As a consequence, the only possible 3D slices are (4,3,3,1), (2,6,6,0), (3,3,3,1), and (1,6,6,0). This eliminates the (5,12,12,4,1) case.

			The (6,8,12,8,0) case can also be eliminated: if (say) 11** is (6,8,12,8,0), then 111* and 113*** must now be (3,3,3,1), which forces the 11** and 13** slices to be bad, and hence the 31** and 33 slices are good, hence 311* and 313* must be (2,6,6,0) (note that we have no way of matching (3,3,3,1) to (4,3,3,1)), but then there is no consistent choice for the 31** slice.

			The only possible side slices of a (5,12,18,4,0) set are (4,3,3,1)+(1,6,6,0) and (3,3,3,1)+(2,6,6,0). In particular, it contains exactly one of any opposing "d" points (e.g. 1222 and 3222). Similarly for (6,12,18,4,0) sets. We conclude that the same is true for the 6D set, e.g. exactly one of 111222 and 113222 lie in the set.

			We can define the notion of the "type" of a (5,12,18,4,0) set just as with a (6,12,18,4,0) set. The above observation forces any two adjacent slices (e.g. 11** and 13) to have opposing type, and thus any two diagonally opposite slices (e.g. 11 and 33**) have identical type. By Lemma 14, such slices cannot both be good. Splitting each family into two pairs of diagonally opposing slices, we thus conclude

			''Proposition 24'' In any two diagonally opposite slices of a 354-point set, one slice is (6,12,18,4,0) and the other is (5,12,18,4,0).

	== Connection with Fujimura's Problem ==		== Connection with Fujimura's Problem ==

Teorth: /* n=6 */

2009-07-06T17:42:30Z

n=6

← Older revision		Revision as of 10:42, 6 July 2009
Line 465:		Line 465:
	One can divide the 60 slices into fifteen families of four depending on their frozen coordinates, for instance one families of four is 11**, 13, 31, 33. We'll call this family the ab** family, and similarly define the ab** family, etc.		One can divide the 60 slices into fifteen families of four depending on their frozen coordinates, for instance one families of four is 11**, 13, 31, 33. We'll call this family the ab** family, and similarly define the ab** family, etc.

	'''Corollary 20''' A 354-point set can have at most one family ~~of four~~ with a total defect of at least 38.		'''Corollary 20''' A 354-point set can have at most one family with a total defect of at least 38.

	'''Proof''' Suppose there are two sets with defect at least 38. The remaining thirteen sets have defect at least 4 by Corollary 9, leading to a net defect of 382+134=128. But 354-point sets have a net defect of 120, a contradiction.		'''Proof''' Suppose there are two sets with defect at least 38. The remaining thirteen sets have defect at least 4 by Corollary 19, leading to a net defect of 382+134=128. But 354-point sets have a net defect of 120, a contradiction.

	By symmetry we may assume that all families other than the ab**** family ~~have~~ a total defect of ~~less than~~ 38~~. Call such 354-point sets ''normalised''~~.		'''Proposition 21''' A 354-point set cannot have any family with a total defect of at least 38.

	'''~~Corollary 21~~''' ~~Let A be a normalised 354-point set. Then~~ the ab family ~~can have at most two good slices~~ (~~and thus has~~ a ~~net~~ defect of at least 8), ~~and similarly for permutations of the last four indices~~.		'''Proof''' Suppose for contradiction that the ab**** family (say) had a total defect of at least 38, then by Corollary 20 all other families have total defect at least 38.

	~~'''Proof''' Suppose~~ the ab has three good slices, say 11, 13, 33. By Lemma 14, 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 18, one of the families a1*, a1*, 1a, 1a 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 14, 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 18, one of the families a1*, a1*, 1a, 1a 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 19, 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, this means that all bad slices outside of the ab** family have a defect of four, with at most one exception; but then by Lemma 18 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.

			From Proposition 21 and Lemma 18 we conclude

			'''Corollary 22''' In a 354-point set, the slices 11** and 13** can only be good if they have opposite type.

			From this and Lemma 14 we conclude

			'''Corollary 23''' In a 354-point set, every family can have at most two good slices, and thus have a defect of at least eight.

			Since 120 = 15*8, we conclude

			'''Corollary 23''' In a 354-point set, every family consists of ''exactly'' two good slices, plus two bad slices of defect exactly four.

	slices with defect 30, thus already contributing 90 to the total defect of 120. These can occupy at most three of the fifteen sets, so there are twelve remaining sets of four. By Corollary 19, each of these contributes a defect of at least 4, leading to a total defect of at least 138, a contradiction.

Teorth: /* n=6 */

2009-07-06T17:29:53Z

n=6

← Older revision		Revision as of 10:29, 6 July 2009
Line 384:		Line 384:
	Currently only via Maple calculations.		Currently only via Maple calculations.

	Define the ''11** score'' of a 4D Moser set to be 4a+6b+10c+20d+60e. The cardinality of a 6D set with f=g=0 is the average of its 60 scores of its "corner slices" - 11*** and permutations and reflections. From [http://spreadsheets.google.com/ccc?key=rwXB_Rn3Q1Zf5yaeMQL-RDw&hl=en the Pareto optimal list], the largest scores are		Define the ''11** score'' of a 4D Moser set to be 4a+6b+10c+20d+60e. The cardinality of a 6D set with f=g=0 is the average of its 60 scores of its "corner slices" - 11*** and permutations and reflections. Define the ''defect'' of a slice to be 356 minus its score. From [http://spreadsheets.google.com/ccc?key=rwXB_Rn3Q1Zf5yaeMQL-RDw&hl=en the Pareto optimal list], the largest scores are

	* 356 - attained by (6,12,18,4,0)		* 356 (defect 0) - attained by (6,12,18,4,0)
	* 352 - attained by (5,12,18,4,0), (5,12,12,4,1), (6,8,12,8,0)		* 352 (defect 4)- attained by (5,12,18,4,0), (5,12,12,4,1), (6,8,12,8,0)
	* 350 - attained by (6,11,18,4,0), (5,15,12,3,1), (6,11,12,7,0), (5,15,18,3,0)		* 350 (defect 6)- attained by (6,11,18,4,0), (5,15,12,3,1), (6,11,12,7,0), (5,15,18,3,0)
	* 348 - attained by (6,14,12,6,0), (3,16,24,0,0), (4,12,18,4,0), (4,12,12,4,1), (5, 8, 12, 8, 0)		* 348 (defect 8)- attained by (6,14,12,6,0), (3,16,24,0,0), (4,12,18,4,0), (4,12,12,4,1), (5, 8, 12, 8, 0)
	* all other statistics are at most 346.		* all other statistics are at most 346 (defect at least 10).

	This establishes <math>c'_6 \leq 356</math>.		This establishes <math>c'_6 \leq 356</math>.

	Call a corner slice "good" if it has score 356, i.e. has statistics (6,12,18,4,0), and "bad" otherwise (so has score at most 352). ~~Call a slice "very bad" if it has score~~ at ~~most 350 (so these are a subset of the bad slices~~). Thus:		Call a corner slice "good" if it has score 356 (defect 0), i.e. has statistics (6,12,18,4,0), and "bad" otherwise (so has score at most 352, i.e. defect at least 4). Thus:

	* In a 356-point set, all 60 corner slices must be good.		* In a 356-point set, all 60 corner slices must be good.
	* In a 355-point set, at most 15 corner slices can be bad. (In fact, the ~~number~~ of ~~bad slices plus half~~ the ~~number of very bad~~ slices is ~~at most 15~~.)		* In a 355-point set, at most 15 corner slices can be bad. (In fact, the total defect of all the slices is 60.)
	* In a 354-point set, at most 30 corner slices can be bad. (In fact, the ~~number~~ of ~~bad slices plus half~~ the ~~number of very bad~~ slices is ~~at most 30~~.)		* In a 354-point set, at most 30 corner slices can be bad. (In fact, the total defect of all the slices is 120.)

	The (6,12,18,4,0) sets have been [[classification of (6,12,18,4,0) sets\|completely classified]]. The basic example is the set consisting of 1111, 1113, 3333, 1332, 1322, 1222, 3322 and permutations (i.e. (4,0,0), (3,0,1), (0,0,4), (1,1,2), (1,2,1), (1,3,0), (0,2,2) in Gamma-notation). This set has d-points 1222, 2122, 2212, 2221. More generally, given any <math>x,y,z,w \in \{1,3\}</math>, there is a unique (6,12,18,4,0) set with d-points x222, 2y22, 22z2, 222w, and these are the only 16 possibilities. Call this set the (6,12,18,4,0) set of type xyzw. It consists of		The (6,12,18,4,0) sets have been [[classification of (6,12,18,4,0) sets\|completely classified]]. The basic example is the set consisting of 1111, 1113, 3333, 1332, 1322, 1222, 3322 and permutations (i.e. (4,0,0), (3,0,1), (0,0,4), (1,1,2), (1,2,1), (1,3,0), (0,2,2) in Gamma-notation). This set has d-points 1222, 2122, 2212, 2221. More generally, given any <math>x,y,z,w \in \{1,3\}</math>, there is a unique (6,12,18,4,0) set with d-points x222, 2y22, 22z2, 222w, and these are the only 16 possibilities. Call this set the (6,12,18,4,0) set of type xyzw. It consists of
Line 452:		Line 452:

	In particular, one cannot have two parallel bad corner slices. Combining this with Corollary 13, we see that two adjacent parallel good corner slices must necessarily have opposite types. Combining this with Corollary 17, we obtain an opposing pair of parallel good corner slices of the same type, which is not possible by Lemma 14. Thus a 355 point set cannot exist.		In particular, one cannot have two parallel bad corner slices. Combining this with Corollary 13, we see that two adjacent parallel good corner slices must necessarily have opposite types. Combining this with Corollary 17, we obtain an opposing pair of parallel good corner slices of the same type, which is not possible by Lemma 14. Thus a 355 point set cannot exist.

			We now refine the analysis further, with the aim of eliminating 354-point sets.

			'''Lemma 18''' Suppose the 11** and 13** slices are good with types xyzw and x'y'z'w' respectively. If x=x', then the 1x** slice has score at most 326 (defect at least 30), and the 1X slice has score at most 348 (defect at least 8). Also, the 11, 13, 11, 1**3, 1**1, 1*3 slices have score at most 350 (defect at least 6). In particular, the total defect of slices beginning with 1 is at least 74.

			'''Proof''' The 1x** slice has eight "a" points, while the 1X** slice has only four. The other six slices mentioned have six "a" points and at most seven "d" points, and cannot be good by Corollary 12. The claim now follows from [http://spreadsheets.google.com/ccc?key=rwXB_Rn3Q1Zf5yaeMQL-RDw&hl=en the Pareto optimal list].

			'''Corollary 19''' A 354-point set cannot have all four slices 11**, 13, 31, and 33** slices be good.

			'''Proof''' Suppose not. By Lemma 14, 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 18, 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 18, 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 a 354 point set has a total defect of 120, contradiction.

			One can divide the 60 slices into fifteen families of four depending on their frozen coordinates, for instance one families of four is 11**, 13, 31, 33. We'll call this family the ab** family, and similarly define the ab** family, etc.

			'''Corollary 20''' A 354-point set can have at most one family of four with a total defect of at least 38.

			'''Proof''' Suppose there are two sets with defect at least 38. The remaining thirteen sets have defect at least 4 by Corollary 9, leading to a net defect of 382+134=128. But 354-point sets have a net defect of 120, a contradiction.

			By symmetry we may assume that all families other than the ab**** family have a total defect of less than 38. Call such 354-point sets ''normalised''.

			'''Corollary 21''' Let A be a normalised 354-point set. Then the ab family can have at most two good slices (and thus has a net defect of at least 8), and similarly for permutations of the last four indices.

			'''Proof''' Suppose the ab has three good slices, say 11, 13, 33. By Lemma 14, 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 18, one of the families a1*, a1*, 1a, 1a has a net defect of at least 38, contradicting the normalisation.

			slices with defect 30, thus already contributing 90 to the total defect of 120. These can occupy at most three of the fifteen sets, so there are twelve remaining sets of four. By Corollary 19, each of these contributes a defect of at least 4, leading to a total defect of at least 138, a contradiction.




			If one has a 354-point set, then the total defect is at most 120.

	== Connection with Fujimura's Problem ==		== Connection with Fujimura's Problem ==

Teorth: /* n=6 */

2009-07-06T16:39:55Z

n=6

← Older revision		Revision as of 09:39, 6 July 2009
Line 394:		Line 394:
	This establishes <math>c'_6 \leq 356</math>.		This establishes <math>c'_6 \leq 356</math>.

	Call a corner slice "good" if it has score 356, i.e. has statistics (6,12,18,4,0), and "bad" otherwise.. Thus:		Call a corner slice "good" if it has score 356, i.e. has statistics (6,12,18,4,0), and "bad" otherwise (so has score at most 352). Call a slice "very bad" if it has score at most 350 (so these are a subset of the bad slices). Thus:

	* In a 356-point set, all 60 corner slices must be good.		* In a 356-point set, all 60 corner slices must be good.
	* In a 355-point set, at most 15 corner slices can be bad.		* In a 355-point set, at most 15 corner slices can be bad. (In fact, the number of bad slices plus half the number of very bad slices is at most 15.)
	* In a 354-point set, at most 30 corner slices can be bad.		* In a 354-point set, at most 30 corner slices can be bad. (In fact, the number of bad slices plus half the number of very bad slices is at most 30.)

	The (6,12,18,4,0) sets have been [[classification of (6,12,18,4,0) sets\|completely classified]]. The basic example is the set consisting of 1111, 1113, 3333, 1332, 1322, 1222, 3322 and permutations (i.e. (4,0,0), (3,0,1), (0,0,4), (1,1,2), (1,2,1), (1,3,0), (0,2,2) in Gamma-notation). This set has d-points 1222, 2122, 2212, 2221. More generally, given any <math>x,y,z,w \in \{1,3\}</math>, there is a unique (6,12,18,4,0) set with d-points x222, 2y22, 22z2, 222w, and these are the only 16 possibilities. Call this set the (6,12,18,4,0) set of type xyzw. It consists of		The (6,12,18,4,0) sets have been [[classification of (6,12,18,4,0) sets\|completely classified]]. The basic example is the set consisting of 1111, 1113, 3333, 1332, 1322, 1222, 3322 and permutations (i.e. (4,0,0), (3,0,1), (0,0,4), (1,1,2), (1,2,1), (1,3,0), (0,2,2) in Gamma-notation). This set has d-points 1222, 2122, 2212, 2221. More generally, given any <math>x,y,z,w \in \{1,3\}</math>, there is a unique (6,12,18,4,0) set with d-points x222, 2y22, 22z2, 222w, and these are the only 16 possibilities. Call this set the (6,12,18,4,0) set of type xyzw. It consists of
Line 437:		Line 437:
	'''Corollary 13''' Suppose the 11** and 13** slices are good. Then either they have opposite types (xyzw and XYZW) or else at least six of the eight slices beginning with 1* (i.e. 11*, 13*, 11, 13, 11, 1**3, 1**1, 1**3) are bad.		'''Corollary 13''' Suppose the 11** and 13** slices are good. Then either they have opposite types (xyzw and XYZW) or else at least six of the eight slices beginning with 1* (i.e. 11*, 13*, 11, 13, 11, 1**3, 1**1, 1**3) are bad.

	'''Lemma 14''' If the 11** and 33** slices are good and of the same type, then there are at most ~~354~~ points.		'''Lemma 14''' If the 11** and 33** slices are good and of the same type, then there are at most 350 points.

	'''Proof''' By symmetry we may assume that 11** and 33 are of type 1111. This excludes a lot of points from 22. Indeed, 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 slices 11, 13** have 40 points, and the other ~~six~~ slices have at most <math>c'_4=43</math> points, leading to <math>16+402+436 = ~~354~~</math> points in all. The claim follows.		'''Proof''' By symmetry we may assume that 11** and 33 are of type 1111. This excludes a lot of points from 22. Indeed, 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 5D slices 1*, 3* have at most <math>c'_5=124</math> points, and the other two 4D slices 21, 23** slices have at most <math>c'_4=43</math> points, leading to <math>16+1242+432 = 350</math> points in all. The claim follows.

	'''Corollary 15''' If the 11**, 13, and 33** slices of a 355-point set are all (6,12,18,4,0) sets, then either six of the eight slices beginning with 1* are bad, or six of the eight slices beginning with *3 are bad.		'''Corollary 15''' If the 11**, 13, and 33** slices of a 355-point set are all (6,12,18,4,0) sets, then either six of the eight slices beginning with 1* are bad, or six of the eight slices beginning with *3 are bad.

Teorth: /* n=6 */

2009-07-04T16:29:20Z

n=6

← Older revision		Revision as of 09:29, 4 July 2009
Line 365:		Line 365:
	== n=6 ==		== n=6 ==

	We have <math>c'_6 \geq 353</math>. This can be seen for instance by taking the union of the Gamma-cells (6,0,0),(5,0,1),(3,3,0), (3,2,1),(3,1,2),(2,2,2),(1,3,2),(0,3,3),(2,0,4),(0,2,4),(0,1,5).		We have <math>c'_6 \geq 353</math>. This can be seen for instance by taking the union of the Gamma-cells (6,0,0),(5,0,1),(3,3,0), (3,2,1),(3,1,2),(2,2,2),(1,3,2),(0,3,3),(2,0,4),(0,2,4),(0,1,5), or equivalently

			* The 22 a-points consisting of 111111, 111113, 113333 and permutations;
			* The 66 b-points consisting of 111332, 333332 and permutations;
			* The 165 c-points consisting of 111322, 113322, 333322 and permutations;
			* The 100 d-points consisting of 111222, 133222, 333222 and permutations;
			* No e, f, or g points.

	'''Lemma 8''' A 6D Moser set with g=1 has at most 351 points.		'''Lemma 8''' A 6D Moser set with g=1 has at most 351 points.
Line 402:		Line 408:

	In particular, the centre 3D slices of a good corner slice have statistics (3,9,3,0), and two opposing side slices have statistics (2,6,6,0) and (4,3,3,1).		In particular, the centre 3D slices of a good corner slice have statistics (3,9,3,0), and two opposing side slices have statistics (2,6,6,0) and (4,3,3,1).

			'''Note''': in the 353-point example given above, the 11** slices are good (and of type 1111), the 13 slices have statistics (5,12,18,4,0) and consist of the type 3333 slice with the point 133333 removed, and the 33** slices have statistics (6,8,12,8,0), with the slice consisting of the 6 a-points formed by permuting 1133, the 8 b-points formed by permuting 1112 and 3332, the 12 c-points formed by permuting 1122 and 3322, and all 8 d-points.

	We now show that it is impossible to have a 356-point set, i.e. one in which all corner slices are good. From the above discussion, we see that if the 111* slice contains its center 111222, then the 113* slice does not, and vice versa. Tthus the d points of the form ***222 consist either of those strings with an even number of 1s, or those with an odd number of 1s.		We now show that it is impossible to have a 356-point set, i.e. one in which all corner slices are good. From the above discussion, we see that if the 111* slice contains its center 111222, then the 113* slice does not, and vice versa. Tthus the d points of the form ***222 consist either of those strings with an even number of 1s, or those with an odd number of 1s.

Teorth: /* n=6 */

2009-07-02T23:50:55Z

n=6

Show changes