Hyper-optimistic conjecture

Gil Kalai and Tim Gowers have proposed a “hyper-optimistic” conjecture.

Let [math]\displaystyle{ c^\mu_n }[/math] be the maximum equal-slices measure of a line-free set. For instance, [math]\displaystyle{ c^\mu_0 = 1 }[/math], [math]\displaystyle{ c^\mu_1 = 2 }[/math], and [math]\displaystyle{ c^\mu_2 = 4 }[/math].

As in the unweighted case, every time we find a subset [math]\displaystyle{ B }[/math] of the grid [math]\displaystyle{ \Delta_n := \{ (a,b,c): a+b+c=n\} }[/math] without equilateral triangles, it gives a line-free set [math]\displaystyle{ \Gamma_B := \bigcup_{(a,b,c) \in B} \Gamma_{a,b,c} }[/math]. The equal-slices measure of this set is precisely the cardinality of B. Thus we have the lower bound [math]\displaystyle{ c^\mu_n \geq \overline{c}^\mu_n }[/math], where [math]\displaystyle{ \overline{c}^\mu_n }[/math] is the largest size of an equilateral-triangle-free subset of [math]\displaystyle{ \Delta_n }[/math]. The computation of the [math]\displaystyle{ \overline{c}^\mu_n }[/math] is Fujimura's problem.

Hyper-optimistic conjecture: We in fact have [math]\displaystyle{ c^\mu_n = \overline{c}^\mu_n }[/math]. In other words, to get the optimal equal-slices measure for a line-free set, one should take a set which is a union of slices [math]\displaystyle{ \Gamma_{a,b,c} }[/math].

This conjecture, if true, will imply the DHJ theorem. Note also that all our best lower bounds for the unweighted problem to date have been unions of slices. Also, the k=2 analogue of the conjecture is true, and is known as the LYM inequality (in fact, for k=2 we have [math]\displaystyle{ c^\mu_n = \overline{c}^\mu_n = 1 }[/math] for all n).

Small values of [math]\displaystyle{ c^\mu_n }[/math]

I have now found the extremal solutions for the weighted problem in the hyper-optimistic conjecture, again using integer programming.

The first few values are

• [math]\displaystyle{ c^\mu_0=1 }[/math] (trivial)
• [math]\displaystyle{ c^\mu_1=2 }[/math] (trivial)
• [math]\displaystyle{ c^{\mu}_2=4 }[/math] with 3 solutions
• [math]\displaystyle{ c^{\mu}_3=6 }[/math] with 9 solutions
• [math]\displaystyle{ c^{\mu}_4=9 }[/math] with 1 solution
• [math]\displaystyle{ c^{\mu}_5=12 }[/math] with 1 solution
• [math]\displaystyle{ c^{\mu}_6=15 }[/math] with an incomplete list of solutions

Comparing this with the known bounds for [math]\displaystyle{ \overline{c}^\mu_n }[/math] we see that the hyper-optimistic conjecture is true for [math]\displaystyle{ n \leq 6 }[/math].

Asymptotic lower bound on [math]\displaystyle{ c^\mu_n }[/math]

Let [math]\displaystyle{ S\subset [0,n-2] }[/math] be a free of 3-term APs, with [math]\displaystyle{ |S| = r_3(n-1) }[/math] (the largest possible size of a subset of [math]\displaystyle{ \{1,2,\dots,n-1\} }[/math] without 3-term APs). By replacing [math]\displaystyle{ S }[/math] with [math]\displaystyle{ n-S }[/math] if necessary, we can assume that the number of pairs [math]\displaystyle{ (s,t)\in S\times S }[/math] with [math]\displaystyle{ s+t\lt n }[/math] is at least [math]\displaystyle{ |S|^2/2 }[/math]. We now split [math]\displaystyle{ S \times S }[/math] into 3 pieces according to the congruence class of [math]\displaystyle{ s+t }[/math] modulo 3. One of those pieces must have size at least [math]\displaystyle{ |S|^2/6 }[/math]; call that largest set of pairs [math]\displaystyle{ P }[/math] and denote [math]\displaystyle{ s+t \mod 3 }[/math] by [math]\displaystyle{ \epsilon }[/math]. Unless you care about the technicalities, you can assume that [math]\displaystyle{ n }[/math] is a multiple of 3 and that [math]\displaystyle{ \epsilon=0 }[/math] and still catch the gist.

We now define the set [math]\displaystyle{ A }[/math], which will have no combinatorial lines. First, let

[math]\displaystyle{ L=\{(a+s,a+t,a): (s,t)\in P, a=(n-s-t)/3\} }[/math]

if [math]\displaystyle{ \epsilon\equiv n \mod 3 }[/math], and

[math]\displaystyle{ L=\{(a+s+1,a+t,a): (s,t)\in P, a=(n-s-t-1)/3\} }[/math]

if [math]\displaystyle{ \epsilon\equiv n+1 \mod 3 }[/math], and

[math]\displaystyle{ L=\{(a+s+1,a+t+1,a): (s,t)\in P, a=(n-s-t-2)/3\} }[/math]

if [math]\displaystyle{ \epsilon\equiv n+2 \mod 3 }[/math]. In all cases, [math]\displaystyle{ a }[/math] is necessarily a nonnegative integer by the assumption [math]\displaystyle{ s+t\lt n }[/math] and the 3-arity of [math]\displaystyle{ n-\epsilon\equiv n-s-t }[/math]. Now we can define [math]\displaystyle{ A=\bigcup_{x\in L} \Gamma_x }[/math].

Now we explain why [math]\displaystyle{ A }[/math] has no combinatorial lines. If [math]\displaystyle{ \ell_i }[/math] (with [math]\displaystyle{ 1\leq i \leq 3 }[/math]) is a combinatorial line in [math]\displaystyle{ A }[/math], then (as with all combinatorial lines in [math]\displaystyle{ [3]^n }[/math]), the difference of the first and third slice-coordinates (are these what people are calling [math]\displaystyle{ c }[/math]-statistics?) must be an arithmetic progression. These differences are in a translate of [math]\displaystyle{ S }[/math], which has no nontrivial APs, and so the difference must be constant for all of the [math]\displaystyle{ \ell_i }[/math]. Likewise, the difference of the second and third coordinates give an arithmetic progression in a translate of [math]\displaystyle{ S }[/math], and so that difference must also be constant. This, since the coordinates must add up to [math]\displaystyle{ n }[/math], completely ties down all coordinates and so the [math]\displaystyle{ \ell_i }[/math] must all lie in the same slice. Therefore, they form a trivial line.

Now we compute the size of [math]\displaystyle{ A }[/math], in the equal slices measure. Clearly, the size of [math]\displaystyle{ A }[/math] is just the size of [math]\displaystyle{ L }[/math]. The set [math]\displaystyle{ L }[/math] gets one pair for each pair [math]\displaystyle{ (s,t) }[/math] in [math]\displaystyle{ P }[/math], and from the first paragraph we concluded that [math]\displaystyle{ |P| }[/math] is at least [math]\displaystyle{ |S|^2/6 }[/math]. Recall that [math]\displaystyle{ |S|=r_3(n-1) }[/math], and you have the following inequality: [math]\displaystyle{ c_n^{\mu} \geq \frac16 r_3(n-1)^2 }[/math].

The latest and greatest regarding [math]\displaystyle{ r_3(n) }[/math] is: for every [math]\displaystyle{ \epsilon\gt 0 }[/math], if [math]\displaystyle{ n }[/math] is sufficiently large then

[math]\displaystyle{ r_3(n) \geq n(\sqrt{360}/(e\pi^{3/2}) - \epsilon) \sqrt[4]{2\log_2(n)}2^{-2\sqrt{2\log_2(n)}}. }[/math]

This is O'Bryant's optimization of the Green & Wolf simplification of Elkin's strengthening of Behrend's construction. Say that three times fast. It all combines to give

:[math]\displaystyle{ c_n^{\mu} \gt  n^2 \cdot ( \frac{60 \sqrt{2}}{e^2 \pi ^3}-\epsilon) \cdot 2^{-4\sqrt{2} \sqrt{\log_2 n }+1/2 \log_2 \log_2 n} }[/math]

for sufficiently large [math]\displaystyle{ n }[/math].

Slice densities

Given any [math]\displaystyle{ (a,b,c) \in \Delta_n }[/math] and a line-free set A, define the slice density [math]\displaystyle{ \alpha_{a,b,c} }[/math] to be the quantity [math]\displaystyle{ \alpha_{a,b,c} := |A \cap \Gamma_{a,b,c}|/|\Gamma_{a,b,c}| }[/math]. The equal-slices measure of A is thus the sum of all the slice densities.

Clearly [math]\displaystyle{ 0 \leq \alpha_{a,b,c} \leq 1 }[/math]. We also have that [math]\displaystyle{ \alpha_{a+r,b,c}+\alpha_{a,b+r,c}+\alpha_{a,b,c+r} \leq 2 }[/math] for all upward-pointing triangles (a+r,b,c), (a,b+r,c), (a,b,c+r).

n=2 by hand

One should in fact be able to get the Pareto-optimal and extremal statistics for the slice densities [math]\displaystyle{ \alpha_{a,b,c} }[/math] in this case.

n=3 by hand

[math]\displaystyle{ c^{\mu}_3=6 }[/math]:

If we have all Three points of the form xxx removed Then the remaining points have value 7 and We have covered all lines any set of moving coordinates And all constant points equal to one value this leaves The lines xab a,b not equal. Each point of the set abc covers three of these lines the entire set covers each of these lines there is no duplication the only alternative is to remove a point abc and cover the lines with points of the form aab which have a higher weight and only cover one line each this would lower the weight so the maximum weight occurs when all of abc is omitted along with the three points xxx and the weight is 6

If we have only two points removed of the form xxx then The weight is at most 8 say the point not removed is 222 Then we must cover the lines xx2 and x22 we have three six such Lines and all the xx2 must be covered one at a time by either 112 Or 332 the x22 must be covered one at a time by 322 or 122 These points must be removed and the that lowers the weight To 8 - 3*(2/6) – 3*(2/6) = 6 again we have c^{\mu} must be less than 6

If one point say 111 is removed then we must cover all lines of the form xx2 xx3 and x22 and x33

Look at the pairs of lines such as xx2 and 33x one with moving coordinates in two positions and a fixed coordinate equal to 2 or 3 say 2 the other with fixed coordinates equal to the other value which in this case is 3 so if the fixed coordinate(s) in one point of the pair is 2 in the other they or it will be three Then we must have one of the points 222 112 332 removed to block the first line of the pair and for the second line we can use 333 332 331. However we do not have the points 222 or 333 removed in this case so we must have either 332 or the pair 112 or 331. For every one of the six point 332 or 223 we will have a similar choice forcing either the removal of the point itself or the associated pair. After these choices have been made more points of the form aab can be added but there must be a subset corresponding to one set of the above six choices since in each case there are only two ways to cover the lines noted. If we start with the configuration 111 removed all six points with two 2’s and one three and two 3’s and one two removed and all points of the form abc removed then this configuration has weight 6 then we can perform a series of steps which will reach all combinatorial line free configurations.

These steps are as follows:

1 Making choices as above and allowing the addition Of all possible abcs

2.Removal of points of the form aab and addition of all possible abc’s

3.Removal of abc

It will be shown that with each step the weight decreases or remains the same so the weight is 6 or less This will give all line free configurations as we must have sub configuration corresponding to one of the six choices and all we can do is add points of the form aab and take the resulting set with the most possible Abc’s and them remove any arbitrary abcs that we wish to remove.

Are the making of the six choices noted above and the addition of any points of the form abc where possible without forming a combinatorial line. At the start each point of the form abc cannot be added because it has two lines which are some permutations of x12 and x13 now look at the points possibly blocking x12 they are 112 212 and 312 initially point 312 which is removed could not be added because the two points 112 and 212 are not removed as each choice is moved then each of the removed lines of type 113 covers two lines of the form permutations of x13 similarly lines of type 133 covers two lines of the form permutations of x13 now each choice to replace a line of the form 332 increase the number of points removed with two coordinates the same by one thus lowers the weight by one third and blocks four lines of the form x13 or x12 thus after n such choices we have reduced the weight by n/3 and covered 4n such lines since every point of the of the form permutations of 123 starts out with 2 such lines which it is blocking and can only be added when they are filled we can only add at most 2n such points which since they have weight 1/6 at the end of n such steps the weight is unchanged now afterwards if we remove more points of the form aab they cover at most two lines of the form xab and thus allow at most two points of the form abc to be added thus the change in weight is at most -1/3 +1/6 +1/6=0 finally afterwards we can remove points of the form abc but that will only lower the weight.

Finally we have no points of the form xxx removed but then we will have a line of the form xxx.

n=4 by hand

[math]\displaystyle{ c^{\mu}_4=9 }[/math]:

If we have all three points of the form aaaa removed then the remaining points have value 12 and we have covered all lines any set of moving coordinates with all constant points equal to one value this leaves the lines xxab, xabc and xaab. let us also remove the three sets of the form aabc, a, b, c not equal. These block the remaining lines and the size is now 9.

Now suppose we try to replace the removed points of the form aabc by points of the form aaab or aabb. Now we must cover the lines of the form xaab each point of the form aabc covers two and has a weight 1/12 each point of the form aabb covers 4 and has a weight 1/6 each point of the form aaab covers three and has a weight of 1/3 and since each element of the form covers two elements of the form xaab that no other element of the set aabc covers and as noted above all lines of the form xaab are covered by the the elements of the three sets of the form aabc we cannot improve on the weight as we can only cover the xaab’s by the same or higher weight lowering the total from 9 so for this case the value is 9.

If we have two points removed of the form aaaa then the weight is at most 13 say the point not removed is 2222 then we must cover the lines xxx2 and x222 we have eight such lines and all six xx22 must be covered one at a time by either 1122 or 3322 the four x222 must be covered one at a time by 3222 or 1222 the four xxx2 must be covered by 3332 or 1112 these points must be removed and the that lowers the weight To 13 - 4*(6/24) – 6*(1/6) – 4(6/24) = 10. We also have 24 lines of the form xabc which can only be covered two at a time by the aabc which have weight 1/12 so we need to cover these with at least 12 of these which we can do by choosing all points which are permutations of 1123 this reduces the number to 9 and again we have c^{\mu} must be 9.

If one point of the form aaaa is removed say 1111 then we must cover all lines of the form xxx2 xxx3 and xx22 and xx33 and x222 and x333 Look at the pairs of lines such as xxx2 and 333x one with moving coordinates in three positions and a fixed coordinate equal to 2 or 3 say 2 the other with fixed coordinates equal to the other value which in this case is 3.

Then we must have one of the points 2222 1112 3332 removed to block the first line of the pair and for the second line we can use 3333 3332 3331. However we do not have the points 2222 or 3333 removed in this case so we must have either 3332 or the pair 1112 or 3331. For every one of the eight points 3332 or 2223 we will have a similar choice forcing either the removal of the point itself or the associated pair. After these choices have been made more points of the form aaab can be added but there must be a subset corresponding to one set of the above eight choices since in each case there are only two ways to cover the lines noted. Look at the pairs of lines such as 22xx and xx33 one with moving coordinates in two positions and a two fixed coordinates equal to 2 or 3 say 2 the other with two fixed coordinates equal to the other value which in this case is 2 so if the fixed coordinate(s) in one point of the pair is 2 in the other they or it will Then we must have one of the points 2211 2222 2233 removed to block the first line of the pair and for the second line we can use 3333 2233 1133. However we do not have the points 2222 or 3333 removed in this case so we must have either 2233 or the pair 1133 or 2211. For every one of the six points with two threes and two twos we will have a similar choice forcing either the removal of the point itself or the associated pair. After these choices have been made more points of the form aabb can be added but there must be a subset corresponding to one set of the above six choices

If we start with the configuration 1111 removed all eight points with three 2’s and one three and three 3’s and one two removed and all points with two 3’s and two 2’s removed and all points of the form aabc removed then this configuration has weight 8 then we can perform a series of steps in order which will reach all combinatorial line free configurations. These steps are as follows:

1 Making choices as above for elements of the form aaab and allowing the addition of all possible aabc’ss.

2 Making choices as above for elements of the form aabb and allowing the addition of all possible aabc’ss.

3.Removal of points of the form aabb or aaab and addition of all possible aabc’s.

4.Removal of aabc’s.

At present none of the aabc can be added there are lines of the form xx12 and xx13 and x113 and x112 which each have to blocked to allow their addition

What we are going to do is perform the previous steps in order. we will show that each step eliminates twice as much in weight of elements of the form aabc as it adds of all other forms. To facilitate the proof we will have to perform the operations in the order listed. However we will be able to reach every possible configuration. We must have a subconfiguration corresponding to one set of choices above then we can delete various elements of the form aabb and aaab to get all possible line free sets of the elements of the form aabb and aaab and then for each set we add the maximum possible number of elements of the form aabc.

The point is doing this is that we can only add two units in weight of the form aabc as the lines of the form xabc must be covered and they Can only be covered by one unit in weight of elements of the form abc So if we have the two to one ratio or better and have to stop at two we will End up with a net change of 2-1 which will raise the weight to 9 or less And we still have the maximum weight of is 9.

When we make a choice deleting a pair and adding say 2223 which will give 1113 and 2221 we block three lines of the form xx13 and three of the form xx12 thus allowing the addition of 6 points of weight 1/12 which give a total change of weight 1/2 which is exactly twice the net change in weight caused by the addition of 2223 and the removal of 1113 of 2221

Now with each substitution there will also be the blocking of lines of the form x113 or x112 however to allow the point say 2113 To be added we must block both x113 and 211x and to do this We must make choices adding both 2223 and 2333 which unblocks The line 2xx1 and forbids the addition of the point 2113 thus the increase in material of the form aabc is twice the net change in weight of the other types

1122 can block the 11×2 two at a time but their weight is 1/6 so even if they block two of the 11×2 and allow the addition of two 1132’s the weight will remain the same and since each replacement of 2233 by 1133 and 2211 has only one element of the form 2211 we are done with step one.

For the choices of elements of the form aabb if we replace an element of the form 2223 by 1113 and 2221 we will be able to block three lines of the form x113 which gets rid of 3 elements of the form 2113 but the weight of the addional aaab element created is 1/4 and the weight of the removed elements is the same. So step two can not improve the weight. So we are done with the choices mentioned above and move on two steps 3 and 4 deleting individual elements.

If we add an element of the form 2233 and delete 1133 and 2211 then it can unblock two lines of the form x113 and two of the form x112 thus allowing the addition of at most 4 points of the form 3112 thus giving a net change of -1/4 +4/12 and again the ratio is 2 to one.

Then after all the above choices have been made we can delete elements of the form 2223 which will block at most three lines Of the form 2xx3 if created by the above choices And the ratio of points added to points deleted is at most one And so is less than 1/2 and we are done. The case 3332 is handled the same way.

If we delete an element of the form 1112 we unblock three lines Of the form xx12 and three of x112 we free at most 6 points with Weight 1/12 giving a total weight of 1/2 the point removed is weight 1/4 so the ratio is 2 to 1 and we are done the case of 1113 is similar.

If we delete an element of the form 3331 it can unblock three lines of the form xx31 and we free three points for possible addition The have total weight equal to the weight of 3331 so the ratio is less than 2 to 1. The case of an element of the form 2221 is similar.

If we delete a point of the form 2233 We don’t unblock any lines so we can’t Add any points of the form aabc.

If we delete a point of the form 1133 we unblock two lines Of the form xx13 and two of x113 and so can add four points With weight 1/12 which has total 1/3 which is twice the weight Of the point 1133 so the ratio is less than or equal to 2 and we are Done. The case of deleting a point of the form 1122 is handled similarly. So we are done with step three.

If we delete a point of the form aabc the weight is less. So we have gone through all steps and the ratio in them 2 or less and thus in this case the weight is 9 or less and we are done. Since this is the final case we have proved the theorem and the weight is 9.

Finally we have no points of the form aaaa removed but then we will have a line of the form xxxx.