Dhj-lown.tex - Revision history

Teorth at 06:42, 16 January 2010

2010-01-16T06:42:25Z

← Older revision		Revision as of 23:42, 15 January 2010
Line 136:		Line 136:
	where $a$, $b$ and $c$ have four points each: $a = \{2,3\}^2$, $b = \{1,3\}^2$ and $c = \{1,2\}^2$. $x'$, $y'$ and $z'$ are subsets of $x$, $y$ and $z$ respectively, and have five points each.		where $a$, $b$ and $c$ have four points each: $a = \{2,3\}^2$, $b = \{1,3\}^2$ and $c = \{1,2\}^2$. $x'$, $y'$ and $z'$ are subsets of $x$, $y$ and $z$ respectively, and have five points each.

	Suppose all three slices are subsets of $~~E_j~~$. We can remove at most five points from the full set ~~of three~~ $~~E_j~~$. Consider columns $2,3,4,6,7,8$. At most two of these columns contain $xyz$, so one point must be removed from the other four. This uses up all but one of the removals. So the slices must be $E_2$, $E_1$, $E_0$ or a cyclic permutation of that. Then the cube, which contains the first square of slice $1$; the fifth square of slice $2$; and the ninth square of slice $3$, contains three copies of the same square. It takes more than one point removed to remove all lines from that cube. So we can't have all three slices subsets of $E_j$.		Suppose all three slices are subsets of $E_{j_1}, E_{j_2}, E_{j_3}$ respectively for some $j_1,j_2,j_3 \in \{0,1,2\}$, $E_1$, or $E_2$. We can remove at most five points from the full set $E_{j_1} \uplus E_{j_2} \uplus E_{j_3}$. Consider columns $2,3,4,6,7,8$. At most two of these columns contain $xyz$, so one point must be removed from the other four. This uses up all but one of the removals. So the slices must be $E_2$, $E_1$, $E_0$ or a cyclic permutation of that. Then the cube, which contains the first square of slice $1$; the fifth square of slice $2$; and the ninth square of slice $3$, contains three copies of the same square. It takes more than one point removed to remove all lines from that cube. So we can't have all three slices subsets of $E_j$.

	Suppose one slice is $X$, $Y$ or $Z$, and two others are subsets of $E_j$. We can remove at most three points from the two $E_j$. By symmetry, suppose one slice is $X$. Consider columns $2$, $3$, $4$ and $7$. They must be cyclic permutations of $x$, $y$, $z$, and two of them are not $xyz$, so must lose a point. Columns $6$ and $8$ must both lose a point, and we only have $150$ points left. So if one slice is $X$, $Y$ or $Z$, the full set contains a line.		Suppose one slice is $X$, $Y$ or $Z$, and two others are subsets of $E_j$. We can remove at most three points from the two $E_j$. By symmetry, suppose one slice is $X$. Consider columns $2$, $3$, $4$ and $7$. They must be cyclic permutations of $x$, $y$, $z$, and two of them are not $xyz$, so must lose a point. Columns $6$ and $8$ must both lose a point, and we only have $150$ points left. So if one slice is $X$, $Y$ or $Z$, the full set contains a line.
Line 148:		Line 148:
	\end{corollary}		\end{corollary}

	Note that this argument gives the bound $c_{5,3} \leq 151$.		Note that this argument already gives the bound $c_{5,3} \leq 151$.

	\begin{lemma} \label{151NoX} No slice $j****$ of $A$ is of the form $X$, where $X$ was defined in Lemma \ref{Lemma2}.		\begin{lemma} \label{151NoX} No slice $j****$ of $A$ is of the form $X$, where $X$ was defined in Lemma \ref{Lemma2}.

Teorth at 06:47, 10 July 2009

2009-07-10T06:47:35Z

144.137.196.174 at 10:51, 26 June 2009

2009-06-26T10:51:02Z

← Older revision		Revision as of 03:51, 26 June 2009
Line 63:		Line 63:
	\item The only $52$-element line-free sets in $[3]^4$ are $E_0$, $E_1$, $E_2$.		\item The only $52$-element line-free sets in $[3]^4$ are $E_0$, $E_1$, $E_2$.
	\item The only $51$-element line-free sets in $[3]^4$ are formed by removing a point from $E_0$, $E_1$ or $E_2$.		\item The only $51$-element line-free sets in $[3]^4$ are formed by removing a point from $E_0$, $E_1$ or $E_2$.
	\item The only $50$-element line-free sets in $[3]^4$ are formed by removing two points from $E_0$, $E_1$ or $E_2$ OR is equal to one of the three permutations of the set $X := \Gamma_{3,1,0} \cup \Gamma_{3,0,1} \cup \~~Gamma~~{2,2,0} \cup \Gamma_{2,0,2} \cup \Gamma_{1,1,2} \cup \Gamma_{1,2,1} \cup \Gamma_{0,2,2}$.		\item The only $50$-element line-free sets in $[3]^4$ are formed by removing two points from $E_0$, $E_1$ or $E_2$ OR is equal to one of the three permutations of the set $X := \Gamma_{3,1,0} \cup \Gamma_{3,0,1} \cup \Gamma_{2,2,0} \cup \Gamma_{2,0,2} \cup \Gamma_{1,1,2} \cup \Gamma_{1,2,1} \cup \Gamma_{0,2,2}$.
	\end{itemize}		\end{itemize}
	\end{lemma}		\end{lemma}

144.137.196.174 at 01:15, 21 June 2009

2009-06-21T01:15:26Z

← Older revision		Revision as of 18:15, 20 June 2009
Line 161:		Line 161:
	So $X$ is in the second or third row. By symmetry, suppose it is in the second row, so that $A$ has the following shape:		So $X$ is in the second or third row. By symmetry, suppose it is in the second row, so that $A$ has the following shape:
	\begin{tabular}{ccc}def & ghi & jkl \\xyz & ybw & zwc \\ mno & pqr & stu \end{tabular}		\begin{tabular}{ccc}def & ghi & jkl \\xyz & ybw & zwc \\ mno & pqr & stu \end{tabular}
	Again, the left-hand nine must contain $52$ points, so it is $E_2$. ~~So either~~ the first row is $E_2~~$ or the third row is $E_0~~$. ~~If the first row is $E_2$ then~~ the only way to have $50$ points in the middle or right-hand nine is if the middle nine is $X$		Again, the left-hand nine must contain $52$ points, so it is $E_2$. Now, to get 52 points in any row, the first row must be $E_2$. Then the only way to have $50$ points in the middle or right-hand nine is if the middle nine is $X$
	\begin{tabular}{ccc}z'xy & xyz & yzx' \\xyz & ybw & zwc \\ yzx' & zwc & stu \end{tabular}		\begin{tabular}{ccc}z'xy & xyz & yzx' \\xyz & ybw & zwc \\ yzx' & zwc & stu \end{tabular}
	In the seventh column, $s$ contains $5$ points and in the eighth column, $t$ contains $4$ points. The final row can now contain at most $48$ points, contradicting Corollary \ref{525049}.		In the seventh column, $s$ contains $5$ points and in the eighth column, $t$ contains $4$ points. The final row can now contain at most $48$ points, contradicting Corollary \ref{525049}.

	If the third row is $E_0$, then neither the middle nine nor the right-hand nine contains $50$ points, by the classification of Lemma \ref{Lemma2} and the formulas at the start of Lemma \ref{151-49}, contradicting Corollary \ref{525049}.\end{proof}		A similar argument is possible if $X$ is in the third row; or if $X$ is replaced by $Y$ or $Z$. Thus, given any decomposition of $A$ into three parallel slices, one slice is a $52$-point set $E_j$ and another slice is $50$ points contained in $E_k$. \end{proof}

	A similar argument is possible if $X$ is in the third row; or if $X$ is replaced by $Y$ or $Z$. Thus, given any decomposition of $A$ into three parallel slices, one slice is a $52$-point set $E_j$ and another slice is $50$ points contained in $E_k$.

	Now we can obtain the desired contradiction:		Now we can obtain the desired contradiction:

Teorth at 18:35, 18 June 2009

2009-06-18T18:35:51Z

Show changes

144.137.196.174 at 16:25, 18 June 2009

2009-06-18T16:25:58Z

← Older revision		Revision as of 09:25, 18 June 2009
Line 41:		Line 41:
	When $n$ is not a multiple of 3, say $n=3m-1$ or $n=3m-2$, one first finds a solution for $n=3m$. Then for $n=3m-1$, one restricts the first digit of the $3m$ sequence to equal 1. This leaves exactly one-third as many points for $3m-1$ as for $3m$. For $n=3m-1$, one restricts the first two digits of the $3m$ sequence to be 12. This leaves roughly one-ninth as many points for $3m-2$ as for $3m$.		When $n$ is not a multiple of 3, say $n=3m-1$ or $n=3m-2$, one first finds a solution for $n=3m$. Then for $n=3m-1$, one restricts the first digit of the $3m$ sequence to equal 1. This leaves exactly one-third as many points for $3m-1$ as for $3m$. For $n=3m-1$, one restricts the first two digits of the $3m$ sequence to be 12. This leaves roughly one-ninth as many points for $3m-2$ as for $3m$.

	The following is an effective method to find good, though not optimal, solutions for any $n=3m$. (For n<21, ignore any triple with a negative entry.)		The following is an effective method to find good, though not optimal, solutions for any $n=3m$. (For $n<21$, ignore any triple with a negative entry.)

	Start with thirteen groups of points in the centre, formed from adding one of the following points, or its permutation, to (M,M,M)~~, when n=3m~~:		Start with thirteen groups of points in the centre, formed from adding one of the following points, or its permutation, to $(m,m,m)$:
	$$(-7,-3,+10), (-7, 0,+7),(-7,+3,+4),(-6,-4,+10),(-6,-1,+7),(-6,+2,+4),(-5,-1,+6),(-5,+2,+3),(-4,-2,+6),(-4,+1,+3),(-3,+1,+2),(-2,0,+2),(-1,0,+1)$$		$$(-7,-3,+10), (-7, 0,+7),(-7,+3,+4),(-6,-4,+10),(-6,-1,+7),(-6,+2,+4),(-5,-1,+6),(-5,+2,+3),(-4,-2,+6),(-4,+1,+3),(-3,+1,+2),(-2,0,+2),(-1,0,+1)$$
	Then include eights string of points, stretching to the edges of the (abc) triangle:		Then include eights string of points, stretching to the edges of the (abc) triangle:

144.137.196.174 at 16:17, 18 June 2009

2009-06-18T16:17:36Z

← Older revision		Revision as of 09:17, 18 June 2009
Line 32:		Line 32:
	gives the lower bound $c_{7,3} \geq 1302$, which we tentatively conjecture to be the correct bound.		gives the lower bound $c_{7,3} \geq 1302$, which we tentatively conjecture to be the correct bound.

	A simplification was found when $n$ is a multiple of 3. See above that for $B_{0,6}$~~, the excluded sets~~ are all permutations of (0,1,5). So the ~~included~~ sets are all permutations of (1,2,3) and (0,2,4). In the same way, sets for $n=9$, 12 and 15 can be described as:		A simplification was found when $n$ is a multiple of 3. See above that for $n=6$, the sets excluded from $B_{0,6}$ are all permutations of $(0,1,5)$. So the remaining sets are all the permutations of $(1,2,3)$ and $(0,2,4)$. In the same way, sets for $n=9$, 12 and 15 can be described as:
	\begin{align*}		\begin{align*}
	(2,3,4),(1,3,5),(0,4,5) and permutations \\		n=9: (2,3,4),(1,3,5),(0,4,5) and permutations \\
	(3,4,5),(2,4,6),(1,5,6),(0,2,10),(0,5,7) and permutations \\		n=12: (3,4,5),(2,4,6),(1,5,6),(0,2,10),(0,5,7) and permutations \\
	(4,5,6),(3,5,7),(2,6,7),(1,3,11),(1,6,8),(0,4,11),(0,7,8) and permutations		n=15: (4,5,6),(3,5,7),(2,6,7),(1,3,11),(1,6,8),(0,4,11),(0,7,8) and permutations
	\end{align*}		\end{align*}

Line 51:		Line 51:
	This solution gives $O(2.7 \sqrt(log (n)/n)3^n$ points for values of n up to around 1000. This is asymptotically smaller than the known optimum of $3^{n-O(\sqrt(log(n)))}. When $n=99$, it gives more than $3^n/2$ points.		This solution gives $O(2.7 \sqrt(log (n)/n)3^n$ points for values of n up to around 1000. This is asymptotically smaller than the known optimum of $3^{n-O(\sqrt(log(n)))}. When $n=99$, it gives more than $3^n/2$ points.

	The following solution ~~is believed to give~~ more points for n>1000, but not for moderate n:		The following solution gives more points for $n>1000$, but not for moderate n.

	\begin{align*}		\begin{align*}
	Define a sequence, of all positive numbers which, in base 3, do not contain a 1. Add 1 to all multiples of 3 in this sequence. This sequence does not contain a length-3 arithmetic progression. It starts $1,2,7,8,19,20,25,26,55, \ldots$\\		Define a sequence, of all positive numbers which, in base 3, do not contain a 1. Add 1 to all multiples of 3 in this sequence. This sequence does not contain a length-3 arithmetic progression. It starts $1,2,7,8,19,20,25,26,55, \ldots$\\
	List all the (abc) triples for which the larger two differ by a number from the sequence;\\		List all the $(abc)$ triples that sum to $n$, for which the larger two differ by a number from the sequence;\\
	Exclude the case when the smaller two differ by 1;\\		Exclude the case when the smaller two differ by 1;\\
	Include the case when (a,b,c) is a permutation of $n/3+(-1,0,1)$.		Include the case when $(a,b,c)$ is a permutation of $n/3+(-1,0,1)$.
	\end{align*}		\end{align*}

144.137.196.174 at 16:08, 18 June 2009

2009-06-18T16:08:26Z

@@ Line 32: / Line 32: @@
 gives the lower bound $c_{7,3} \geq 1302$, which we tentatively conjecture to be the correct bound.
-{\bf need discussion here of how one can get lower bounds for higher $n$, e.g. $n=100$.}
+A simplification was found when $n$ is a multiple of 3.  See above that for $B_{0,6}$, the excluded sets are all permutations of (0,1,5).  So the included sets are all permutations of (1,2,3) and (0,2,4).  In the same way, sets for $n=9$, 12 and 15 can be described as:
 Now we prove Theorem \ref{dhj-lower}.

98.113.21.246: commented out k=3 case of Theorem 1.3; Minor formatting changes

2009-06-05T12:26:58Z

commented out k=3 case of Theorem 1.3; Minor formatting changes

← Older revision		Revision as of 05:26, 5 June 2009
Line 10:		Line 10:

	In order to use \eqref{cn3}, one of course needs to build Fujimura sets $B$ which are ``large'' in the sense that the right-hand side of \eqref{cn3} is large. A fruitful starting point for this goal is the sets		In order to use \eqref{cn3}, one of course needs to build Fujimura sets $B$ which are ``large'' in the sense that the right-hand side of \eqref{cn3} is large. A fruitful starting point for this goal is the sets
	$$B_{j,n} := \{ (a,b,c) \in \Delta_{3,n}: a + 2b \neq j \hbox{ mod } 3 \}$$		$$B_{j,n} := \{ (a,b,c) \in \Delta_{3,n}: a + 2b \neq j \hbox{ mod } 3 \}$$
	for $j=0,1,2$. Observe that in order for a triangle $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ to lie in $B_{j,n}$, the length $r$ of the triangle must be a multiple of $3$. This already makes $B_{j,n}$ a Fujimura set for $n < 3$ (and $B_{0,n}$ a Fujimura set for $n = 3$).		for $j=0,1,2$. Observe that in order for a triangle $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ to lie in $B_{j,n}$, the length $r$ of the triangle must be a multiple of $3$. This already makes $B_{j,n}$ a Fujimura set for $n < 3$ (and $B_{0,n}$ a Fujimura set for $n = 3$).

	When $n$ is not a multiple of $3$, the $B_{j,n}$ are all rotations of each other and give equivalent sets (of size $2 \times 3^{n-1}$). When $n$ is a multiple of $3$, the sets $B_{1,n}$ and $B_{2,n}$ are reflections of each other, but $B_{0,n}$ is not equivalent to the other two sets (in particular, it omits all three corners of $\Delta_{3,n}$); the associated set $A_{B_{0,n}}$ is slightly larger than $A_{B_{1,n}}$ and $A_{B_{2,n}}$ and thus is slightly better for constructing line-free sets.		When $n$ is not a multiple of $3$, the $B_{j,n}$ are all rotations of each other and give equivalent sets (of size $2 \times 3^{n-1}$). When $n$ is a multiple of $3$, the sets $B_{1,n}$ and $B_{2,n}$ are reflections of each other, but $B_{0,n}$ is not equivalent to the other two sets (in particular, it omits all three corners of $\Delta_{3,n}$); the associated set $A_{B_{0,n}}$ is slightly larger than $A_{B_{1,n}}$ and $A_{B_{2,n}}$ and thus is slightly better for constructing line-free sets.

	As mentioned already, $B_{0,n}$ is a Fujimura set for $n \leq 3$, and hence $A_{B_{0,n}}$ is line-free for $n \leq 3$. Applying \eqref{cn3} one obtains the lower bounds		As mentioned already, $B_{0,n}$ is a Fujimura set for $n \leq 3$, and hence $A_{B_{0,n}}$ is line-free for $n \leq 3$. Applying~\eqref{cn3} one obtains the lower bounds
	$$ c_{0,3} \geq 1; c_{1,3} \geq 2; c_{2,3} \geq 6; c_{3,3} \geq 18.$$		$$ c_{0,3} \geq 1; c_{1,3} \geq 2; c_{2,3} \geq 6; c_{3,3} \geq 18.$$

	For $n>3$, $B_{0,n}$ contains some triangles $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ and so is not a Fujimura set, but one can remove points from this set to recover the Fujimura property. For instance, for $n \leq 6$, the only triangles in $B_{0,n}$ have side length $r=3$. One can ``delete'' these triangles by removing one vertex from each; in order to optimise the bound \eqref{cn3} it is preferable to delete vertices near the corners of $\Delta_{3,n}$ rather than near the centre. These considerations lead to the Fujimura sets		For $n>3$, $B_{0,n}$ contains some triangles $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ and so is not a Fujimura set, but one can remove points from this set to recover the Fujimura property. For instance, for $n \leq 6$, the only triangles in $B_{0,n}$ have side length $r=3$. One can ``delete'' these triangles by removing one vertex from each; in order to optimise the bound~\eqref{cn3} it is preferable to delete vertices near the corners of $\Delta_{3,n}$ rather than near the centre. These considerations lead to the Fujimura sets
	\begin{align*}		\begin{align*}
	B_{0,4} &\backslash \{ (0,0,4), (0,4,0), (4,0,0) \}\\		B_{0,4} &\backslash \{ (0,0,4), (0,4,0), (4,0,0) \}\\
	B_{0,5} &\backslash \{ (0,4,1), (0,5,0), (4,0,1), (5,0,0) \}\\		B_{0,5} &\backslash \{ (0,4,1), (0,5,0), (4,0,1), (5,0,0) \}\\
	B_{0,6} &\backslash \{ (0,1,5), (0,5,1), (1,0,5), (0,1,5), (1,5,0), (5,1,0) \}		B_{0,6} &\backslash \{ (0,1,5), (0,5,1), (1,0,5), (0,1,5), (1,5,0), (5,1,0) \}
	\end{align*}		\end{align*}
	which by \eqref{cn3} gives the lower bounds		which by \eqref{cn3} gives the lower bounds
	$$ c_{4,3} \geq 52; c_{5,3} \geq 150; c_{6,3} \geq 450.$$		$$ c_{4,3} \geq 52; c_{5,3} \geq 150; c_{6,3} \geq 450.$$
	Thus we have established all the lower bounds needed for Theorem \ref{dhj-upper}.		Thus we have established all the lower bounds needed for Theorem \ref{dhj-upper}.

	One can of course continue this process by hand, for instance the set		One can of course continue this process by hand, for instance the set
	$$ B_{0,7} \backslash \{(0,1,6),(1,0,6),(0,5,2),(5,0,2),(1,5,1),(5,1,1),(1,6,0),(6,1,0) \}$$		$$ B_{0,7} \backslash \{(0,1,6),(1,0,6),(0,5,2),(5,0,2),(1,5,1),(5,1,1),(1,6,0),(6,1,0) \}$$
	gives the lower bound $c_{7,3} \geq 1302$, which we tentatively conjecture to be the correct bound.		gives the lower bound $c_{7,3} \geq 1302$, which we tentatively conjecture to be the correct bound.

Line 36:		Line 36:
	Now we prove Theorem \ref{dhj-lower}.		Now we prove Theorem \ref{dhj-lower}.

	\begin{proof}[Proof of Theorem \ref {dhj-lower}]		%\begin{proof}[Proof of Theorem \ref {dhj-lower}]
	Let $S$ be a subset of the interval $[-\sqrt {n}/2, \sqrt {n}/2)$ that contains no arithmetic progressions of length 3, and let $B\subset\Delta_{n, 3}$ be the set		%Let $S$ be a subset of the interval $[-\sqrt {n}/2, \sqrt {n}/2)$ that contains no arithmetic
	\[ B := \{(n-s-t,s-2t,-2s+t) : s,t \in S\}.\]		%progressions of length 3, and let $B\subset\Delta_{n, 3}$ be the set
	The map $(a,b,c)\mapsto (b+2c,2b+c)$ takes simplices to nonconstant arithmetic progressions, and takes $B$ to $\{-3(s,t)\colon s,t \in S\}$, which is a set containing no nonconstant arithmetic progressions. Thus, $B$ is a Fujimora set and so does not contain any combinatorial lines.		% \[ B := \{(n-s-t,s-2t,-2s+t) : s,t \in S\}.\]
			%The map $(a,b,c)\mapsto (b+2c,2b+c)$ takes simplices to nonconstant arithmetic progressions,
	If all of $a,b,c$ are within $C_1\sqrt{n}$ of $n/3$, then $ \| \Gamma_ {a, b, c} \| \geq C 3^n/n$ (where $C$ depends on $C_1$) by the central limit theorem. By our choice of $S$ and applying~\eqref{cn3}, we obtain		%and takes $B$ to $\{-3(s,t)\colon s,t \in S\}$, which is a set %containing no nonconstant
	$$ c_ {n, 3}\geq C \|S\| ^2 3^n/n. $$		%arithmetic progressions. Thus, $B$ is a Fujimora set and so does not contain any combinatorial lines.
	One can take $S$ to have cardinality $r_ 3 (\sqrt {n}) $, which from the results of Elkin~\cite {elkin} (see also~\cite{greenwolf,obryant}) satisfies (for all sufficiently large $n$)		%
	$$ r_ 3 (\sqrt {n})\geq\sqrt {n} (\log n)^{1/4}\exp_ 2 (-2\sqrt {\log_ 2 n}),$$		%If all of $a,b,c$ are within $C_1\sqrt{n}$ of $n/3$, then $ \| \Gamma_ {a, b, c} \| \geq C 3^n/n$
	which completes the proof.		%(where $C$ depends on $C_1$) by the central limit theorem. By %our choice of $S$ and applying~\eqref{cn3}, we obtain
	\end {proof}		% $$ c_ {n, 3}\geq C \|S\| ^2 3^n/n. $$
			%One can take $S$ to have cardinality $r_ 3 (\sqrt {n}) $, which from the results of Elkin~\cite {elkin}
			%(see also~\cite{greenwolf,obryant}) satisfies (for all sufficiently %large $n$)
			% $$ r_ 3 (\sqrt {n})\geq\sqrt {n} (\log n)^{1/4}\exp_ 2 (-2\sqrt {\log_ 2 n}),$$
			%which completes the proof.
			%\end {proof}

	\begin{proof}[Proof of Theorem \ref {dhj-lower}]		\begin{proof}[Proof of Theorem \ref {dhj-lower}]
Line 54:		Line 59:
	\[ B := \{(n-\sum_{i=1}^{k-1} a_i ,a_1,a_2,\dots, a_{k-1}) :		\[ B := \{(n-\sum_{i=1}^{k-1} a_i ,a_1,a_2,\dots, a_{k-1}) :
	(a_1,\dots,a_{k-1})= \det(M) M^{-1}\vec{s} , \vec{s}\in S^{k-1}\}.\]		(a_1,\dots,a_{k-1})= \det(M) M^{-1}\vec{s} , \vec{s}\in S^{k-1}\}.\]
	The map $(m,a_1,\dots,a_{k-1}) \mapsto M (a_1,\dots,a_{k-1})$ takes simplices to nonconstant arithmetic progressions, and takes $B$ to $\{det(M) \, \vec{s} \colon \vec{s} \in S^{k-1}\}$, which is a set containing no nonconstant arithmetic progressions. Thus, $B$ is a Fujimora set and so does not contain any combinatorial lines.		The map $(m,a_1,\dots,a_{k-1}) \mapsto M (a_1,\dots,a_{k-1})$ takes simplices to nonconstant arithmetic progressions in ${\mathbb Z}^{k-1}$, and takes $B$ to $\{det(M) \, \vec{s} \colon \vec{s} \in S^{k-1}\}$, which is a set containing no nonconstant arithmetic progressions. Thus, $B$ is a Fujimora set and so does not contain any combinatorial lines.

	If all of $a_1,\ldots,a_k$ are within $C_1\sqrt{n}$ of $n/k$, then $ \| \Gamma_{\vec{a}}\| \geq C k^n/n^{(k-1}/2}$ (where $C$ depends on $C_1$) by the central limit theorem. By our choice of $S$ and applying~\eqref{cn3}, we obtain		If all of $a_1,\ldots,a_k$ are within $C_1\sqrt{n}$ of $n/k$, then $\|\Gamma_{\vec{a}}\| \geq C k^n/n^{(k-1}/2}$ (where $C$ depends on $C_1$) by the central limit theorem. By our choice of $S$ and applying~\eqref{cn3}, we obtain
	$$ c_ {n, 3}\geq C \|S\| ^{k-1} k^n/n^{(k-1~~)/2~~}. $$		$$ c_ {n, k}\geq C k^n/n^{(k-1)/2} \|S\|^{k-1} = C k^n \left( \frac{\|S\|}{\sqrt{n}} \right)^{k-1}. $$
	One can take $S$ to have cardinality $r_ k (\sqrt {n}) $, which from the results of O'Bryant~\cite {obryant}) satisfies (for all sufficiently large $n$, some $C>0$, and $k> 2^{\ell-1}$)		One can take $S$ to have cardinality $r_ k (\sqrt {n}) $, which from the results of O'Bryant~\cite {obryant}) satisfies (for all sufficiently large $n$, some $C>0$, and $\ell$ the largest integer satisfying $k> 2^{\ell-1}$)
	$$ r_k (\sqrt{n})~~\geq C~~ \sqrt{n} (\log n)^{1/(2\ell)}\exp_ 2 (-\ell 2^{(\ell-1)/2-1/\ell} \sqrt[\ell]{\log_2 n}),$$		$$ \frac{r_k (\sqrt{n})}{\sqrt{n}} \geq C (\log n)^{1/(2\ell)}\exp_ 2 (-\ell 2^{(\ell-1)/2-1/\ell} \sqrt[\ell]{\log_2 n}),$$
	which completes the proof.		which completes the proof.
	\end {proof}		\end {proof}

OBryant: typo

2009-06-03T20:42:07Z

typo

← Older revision		Revision as of 13:42, 3 June 2009
Line 59:		Line 59:
	$$ c_ {n, 3}\geq C \|S\| ^{k-1} k^n/n^{(k-1)/2}. $$		$$ c_ {n, 3}\geq C \|S\| ^{k-1} k^n/n^{(k-1)/2}. $$
	One can take $S$ to have cardinality $r_ k (\sqrt {n}) $, which from the results of O'Bryant~\cite {obryant}) satisfies (for all sufficiently large $n$, some $C>0$, and $k> 2^{\ell-1}$)		One can take $S$ to have cardinality $r_ k (\sqrt {n}) $, which from the results of O'Bryant~\cite {obryant}) satisfies (for all sufficiently large $n$, some $C>0$, and $k> 2^{\ell-1}$)
	$$ r_k (\sqrt{n})\geq C \sqrt{n} (\log n)^{1/4}\exp_ 2 (-\ell 2^{(\ell-1)/2-1/\ell} \sqrt[\ell]{\log_2 n}),$$		$$ r_k (\sqrt{n})\geq C \sqrt{n} (\log n)^{1/(2\ell)}\exp_ 2 (-\ell 2^{(\ell-1)/2-1/\ell} \sqrt[\ell]{\log_2 n}),$$
	which completes the proof.		which completes the proof.
	\end {proof}		\end {proof}

← Older revision		Revision as of 23:47, 9 July 2009
Line 59:		Line 59:
	\end{itemize}		\end{itemize}

	\begin{lemma}\label{Lemma2}		\begin{lemma}\label{Lemma2}\
	\begin{itemize}		\begin{itemize}
	\item The only $52$-element line-free sets in $[3]^4$ are $E_0$, $E_1$, $E_2$.		\item The only $52$-element line-free sets in $[3]^4$ are $E_0$, $E_1$, $E_2$.
Line 155:		Line 155:
	\begin{proof} Suppose one slice is $X$; then by the previous discussion one of the parallel slices has $52$ points and is thus of the form $E_j$ for some $j=0,1,2$, by Lemma \ref{Lemma2}.		\begin{proof} Suppose one slice is $X$; then by the previous discussion one of the parallel slices has $52$ points and is thus of the form $E_j$ for some $j=0,1,2$, by Lemma \ref{Lemma2}.

	Suppose that $X$ is the first slice $1****$. We have $X = xyz\ ybw \ zwc$. Label the other rows with letters from the alphabet:		Suppose that $X$ is the first slice $1****$. We have $X = xyz\ ybw \ zwc$. Label the other rows with letters from the alphabet, thus
	\begin{~~tabular}{ccc~~} xyz & ybw & zwc \\ mno & pqr & stu \\def & ghi & jkl \end{~~tabular~~}		$$ A = \begin{pmatrix} xyz & ybw & zwc \\ mno & pqr & stu \\def & ghi & jkl
	Reslice the array into a left nine, middle nine and right nine. One of these squares contains 52 points, and it can only be the left nine. One of its three columns contains $18$ points, and it can only be its left-hand column, $xmd$. So $m=y$ and $d=z$. But none of the $E_j$ begins with $y$ or $z$, which is a contradiction. So $X$ is not in the first row.		\end{pmatrix}$$
			Reslice the array into a left nine, middle nine and right nine. One of these squares contains $52$ points, and it can only be the left nine. One of its three columns contains $18$ points, and it can only be its left-hand column, $xmd$. So $m=y$ and $d=z$. But none of the $E_j$ begins with $y$ or $z$, which is a contradiction. So $X$ is not in the first row.

	So $X$ is in the second or third row. By symmetry, suppose it is in the second row, so that $A$ has the following shape:		So $X$ is in the second or third row. By symmetry, suppose it is in the second row, so that $A$ has the following shape:
	\begin{~~tabular}{ccc~~}def & ghi & jkl \\xyz & ybw & zwc \\ mno & pqr & stu \end{~~tabular~~}		$$ A = \begin{pmatrix} def & ghi & jkl \\xyz & ybw & zwc \\ mno & pqr & stu \end{pmatrix}$$
	Again, the left-hand nine must contain $52$ points, so it is $E_2$. Now, to get 52 points in any row, the first row must be $E_2$. Then the only way to have $50$ points in the middle or right-hand nine is if the middle nine is $X$		Again, the left-hand nine must contain $52$ points, so it is $E_2$. Now, to get $52$ points in any row, the first row must be $E_2$. Then the only way to have $50$ points in the middle or right-hand nine is if the middle nine is $X$:
	\begin{~~tabular}{ccc~~}z'xy & xyz & yzx' \\xyz & ybw & zwc \\ yzx' & zwc & stu \end{~~tabular~~}		$$ A = \begin{pmatrix} z'xy & xyz & yzx' \\xyz & ybw & zwc \\ yzx' & zwc & stu \end{pmatrix}$$
	In the seventh column, $s$ contains $5$ points and in the eighth column, $t$ contains $4$ points. The final row can now contain at most $48$ points, contradicting Corollary \ref{525049}.		In the seventh column, $s$ contains $5$ points and in the eighth column, $t$ contains $4$ points. The final row can now contain at most $48$ points, contradicting Corollary \ref{525049}.

Line 172:		Line 173:

	\begin{proof} Assume by symmetry that the first row contains $52$ points and the second row contains $50$.		\begin{proof} Assume by symmetry that the first row contains $52$ points and the second row contains $50$.
	If $E_1$ is in the first row, then the second row must be contained in $E_0$.		If $E_1$ is in the first row, then the second row must be contained in $E_0$:
	\begin{~~tabular}{ccc~~} xyz & yz'x & zxy' \\ y'zx & zx'y & xyz \\ def & ghi & jkl\end{~~tabular~~}		$$ A = \begin{pmatrix} xyz & yz'x & zxy' \\ y'zx & zx'y & xyz \\ def & ghi & jkl\end{pmatrix}$$
	But then none of the left nine, middle nine or right nine can contain $52$ points, which contradicts Corollary \ref{525049}.		But then none of the left nine, middle nine or right nine can contain $52$ points, which contradicts Corollary \ref{525049}.
	Suppose the first row is $E_0$. Then the second row is contained in $E_2$, otherwise the cubes formed from the nine columns of the diagram would need to remove too many points.		Suppose the first row is $E_0$. Then the second row is contained in $E_2$, otherwise the cubes formed from the nine columns of the diagram would need to remove too many points:
	\begin{~~tabular}{ccc~~} y'zx & zx'y & xyz \\ z'xy & xyz & yzx' \\ def & ghi & jkl \end{~~tabular~~}		$$ A = \begin{pmatrix} y'zx & zx'y & xyz \\ z'xy & xyz & yzx' \\ def & ghi & jkl \end{pmatrix}.$$
	But then neither the left nine, middle nine nor right nine contain $52$ points.		But then neither the left nine, middle nine nor right nine contain $52$ points.
	So the first row contains $E_2$, and the second row is contained in $E_1$. Two points may be removed from the second row of this diagram.		So the first row contains $E_2$, and the second row is contained in $E_1$. Two points may be removed from the second row of this diagram:
	\begin{~~tabular}{ccc~~} z'xy & xyz & yzx' \\ xyz & yz'x & zxy' \\ def & ghi & jkl \end{~~tabular~~}		$$ A = \begin{pmatrix} z'xy & xyz & yzx' \\ xyz & yz'x & zxy' \\ def & ghi & jkl \end{pmatrix}.$$
	Slice it into the left nine, middle nine and right nine. Two of them are contained in $E_j$ so at least two of $def$, $ghi$, and $jkl$ are contained in the corresponding slice of $E_0$. Slice along a different axis, and at least two of $dgj$, $ehk$, $fil$ are contained in the corresponding slice of $E_0$. So eight of the nine squares in the bottom row are contained in the corresponding square of $E_0$. Indeed, slice along other axes, and all points except one are contained within $E_0$. This point is the intersection of all the $49$-point slices.		Slice it into the left nine, middle nine and right nine. Two of them are contained in $E_j$ so at least two of $def$, $ghi$, and $jkl$ are contained in the corresponding slice of $E_0$. Slice along a different axis, and at least two of $dgj$, $ehk$, $fil$ are contained in the corresponding slice of $E_0$. So eight of the nine squares in the bottom row are contained in the corresponding square of $E_0$. Indeed, slice along other axes, and all points except one are contained within $E_0$. This point is the intersection of all the $49$-point slices.
	So, if there is a $151$-point solution, then after removal of the specified point, there is a $150$-point solution, within $D_{5,j}$, whose slices in each direction are $52+50+48$.		So, if there is a $151$-point solution, then after removal of the specified point, there is a $150$-point solution, within $D_{5,j}$, whose slices in each direction are $52+50+48$.
	\begin{~~tabular}{ccc~~}z'xy & xyz & yzx' \\ xyz & yz'x & zxy' \\ y'zx & zx'y & xyz \end{~~tabular~~}		$$ A = \begin{pmatrix} z'xy & xyz & yzx' \\ xyz & yz'x & zxy' \\ y'zx & zx'y & xyz \end{pmatrix}$$
	One point must be lost from columns $3$, $6$, $7$ and $8$, and four more from the major diagonal $z'z'z$. That leaves $148$ points instead of $150$.		One point must be lost from columns $3$, $6$, $7$ and $8$, and four more from the major diagonal $z'z'z$. That leaves $148$ points instead of $150$.
	So the $150$-point solution does not exist with $52+50+48$ slices; so the $151$ point solution does not exist. \end{proof}		So the $150$-point solution does not exist with $52+50+48$ slices; so the $151$ point solution does not exist.
			\end{proof}