On 4/3/15, Warren D Smith <warren.wds@gmail.com> wrote:
The goal of the problem is to determine (or merely bound) F(n), which is the maximum possible number of n-vectors over Z3, such that no three sum to 0. More precisely such that for any three, call them x,y,z, it can only happen that x+y+z=0 if x=y=z.
--Here is a simple randomized lower bound construction. Randomly fill in an nXm matrix with {-1,0,1}. The expected number of triples of columns which sum (mod 3) to 0, not all three columns the same, is (m^2+3*m-4)*(m/6)/3^n. If m+1.5<=6^(1/3) * 3^(n/3), then this expected number is <1. That means there is nonzero chance the matrix will yield a "SET," meaning a SET at least this size must exist. Hence THEOREM F(n) > 6^(1/3) * 3^(n/3) - 3/2. This is an exponential lower bound, although the growth constant is only 3^(1/3) =approx= 1.442 not as good as the best known 2.21. Now we definitely can improve things by using "improved random" constructions. Here is a simple example. Randomly fill in an nXm matrix with {-1,0,1}. Let C be the number of triples of columns which sum (mod 3) to 0, not all three columns the same. Remove one column from each such triple from the matrix, result being an nX(m-C) trit-matrix (or the horizontal size could be larger than m-C if two bad triples overlap) which is a SET. Again the expected number of triples of columns which sum (mod 3) to 0, not all three columns the same, is (m^2+3*m-4)*(m/6)/3^n. There must exist a random matrix fill which causes C to be its expected value or less, hence F(n)>=m-C>=m-(m^2+3*m-4)*(m/6)/3^n. (In fact ">".) This yields THEOREM F(n) > sqrt((216*T^3+756*T^2+882*T+343)/T^2)/(9*sqrt(3))-(T+1)/T where T=3^n. This also grows exponentially, but now with the improved growth constant 3^(2/3) =approx= 2.080. That's nearly as good as the best known constant 2.21 and it was very easy. An alternative "repair scheme" is, not to remove the C bad columns from the matrix, but rather replace their contents with newly made random trits. If (C/2)*(m^2)/3^n<=1, then this has a nonzero chance of being a successful repair, i.e. some successful repair must exist. That scheme sucks because the exponential growth factor we get is at most sqrt(3)=approx=1.732. Better is "keep doing these column replacements one bad column at a time except that whenever one fails, then delete that column instead of replacing it." That scheme definitely does better than the deletion-only scheme, but I haven't figured out how much better. I also suspect better lower bounds are possible by combining arguments involving randomization, with ones involving explicit constructions.