OK, think I have a new lower bound on the SET problem F(n) which breaks all previous records for all large-enough n, and enjoys exponential growth factor 2.999, well actually 3-epsilon for any fixed epsilon>0, thus matching the upper bound except for the epsilon. Here is the construction. I am going to show F(n+m)>=3^n for all large-enough n, and where m=o(n). Simply put all possible trits {-1,0,1} in the first n locations in the (n+m)-vector, that's 3^n vectors right there. Now, the remaining m vector entries need to be filled in. Compute the sum of squares S of the first n entries in the vector (now as an integer; do not work mod 3). Note 0<=S<=n. Now, if we were to adjoin S as an (n+1)st vector entry, where this extra entry was not handled mod 3, it was just an ordinary integer, then the resulting (n+1)-vectors would do the job because S is a strictly concave-U function of the first n vector entries, hence if the first n happened to be (for three vectors) collinear equispaced, then their S's could not be. Now instead of thinking of S as an "integer," we can represent S by its residues modulo the first ln(2n) (approximately) primes, or they need not be primes, they could be any relatively prime set of numbers. (Chinese remainder theorem. Any residue representation valid for all numbers up to 2n.) That shows that if we instead were to adjoin to the n initial entries of each vector (each handled mod 3), about ln(2n) additional entries, each handled with its own modulus -- but the max modulus is only about ln(2n)*lnln(2n) -- then the resulting set of vectors would do the job too. But that still is not quite good enough since these moduli, although small, are bigger than 3. To fix that remaining flaw, we proceed recursively using the same trick. That is, at the next level of recursion, each one of those residues R, is itself represented via a residue representation valid for all numbers up to 2R. So now we've got about ln(2*n)*ln(2*ln(2*n)) additional entries, with max modulus of lnlnln size. And so on. After about logstar(n) levels of recursing -- where I define my logstar(n) function as the number of iterations of ln(2*x) needed to reduce n below some constant -- we have a set of (n+m)-vectors where m=ln(n)^logstar(n) approximately, and the first n entries of each vector are handled mod 3, but the remaining m entries re handled modulo various moduli <=C for some constant C, which do the job, i.e. no three are collinear. Now you may still complain that 3<C. Yah, but we now can use some constant size dictionary lookup to do the rest. So I claim to have sketchily proved the following ALLEGED THEOREM: For all large-enough integer n, there exists an integer m with 0<m<ln(n)^O(logstar(n)), such that F(n+m) >= 3^n. If true, this result is the new-record lower bound on F, and it is not maximally precisely stated, e.g. could be tightened somewhat further by anybody who wanted to struggle to be precise about the best than can be squeezed out of this argument. Caveat emptor, however, since this has been sketchy. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)