A generalization of the SET problem

In the lattice point problem, given $n$ and $d$, one seeks to find the least positive integer $f(n,d)$ such that every collection of $f(n,d)$ $d$-tuples of integers contains $n$ whose average is an integer $d$-tuple (geometrically, the centroid is a lattice point). Erdos, Ziv, and Ginsberg (1961) proved that $f(n,1)=2n-1$. In 2003 Christian Reiher and Carlos di Fiore proved that $f(n,2)=4n-3$. In the SET game, invented by Marsha Falco, there are 81 cards with four attributes of three types each. A set consists of three cards which, in each attribute, all agree or all disagree. The problem of finding the minimum number of cards that force a set is almost the same as the problem of finding $f(3,4)$, except in the SET problem repeated elements are not allowed. Davis and Maclagan, in The Mathematical Intelligencer, 25, No. 3, 2003, 33-40, state that the smallest number of cards that force a set is 21, and they prove that in the 5-dimensional version, the smallest number is 46. The authors mention that the SET problem can be generalized in different directions. Let us say that $g(n,d)$ is the least positive integer such that every collection of $g(n,d)$ $d$-tuples of integers chosen from $\{1,\ldots,n\}$ contains $n$ which in each coordinate all agree or all disagree. (Repeated elements are not allowed.) Notice the main difference between the lattice point problem and the generalized SET problem: for example, $(0,0)$, $(0,1)$, $(0,1)$, $(0,2)$ have a lattice point centroid, but these elements do not constitute a set. It is immediate that $(n-1)^d+1 \leq g(n,d) \leq d^n$. (For the lower bound, exclude one integer from all the $d$-tuples.) It is not difficult to show that the lower bound gives the correct value of the function when $d=2$. The next case is $g(4,3)$.

Does anyone know of a reference to this value, or can someone determine it?

-
I assume the upper bound is meant as n^d. Three more tangential remarks: f(3,6) is also known, 225 (Potechin, 2008); to say the problems f(3,4) and SET are 'almost the same' is potentially misleading, it is not hard to see they are equivalent (for any dimension); it is Ginzburg (also the order is alphabetical on the paper). –  quid Dec 19 '12 at 16:00

1 Answer

Quid, thank you for your comments. Yes, the upper bound is $n^d$. Thanks for mentioning the value $f(3,6)=225$. The difference between $f(3,4)$ and the minimum number of cards that force a set is that in SET no elements may be repeated, but in the lattice point problem there can be repeated elements. Thus Kennitz (1983) showed that $f(3,4)=41$ while the minimum number of cards which force a set is $21$. Thanks for the correction of Ginzburg's name and for the correct name of the theorem: Erdos-Ginzburg-Ziv.

-
You are welcome! A technical and a mathematical point. Math first: yes I know that the defintion are different, what I meant is that if you consider, for n=3 and aribtrary d, the problem without repetition and you take a maximal example where you do not yet have the desired substructure then you can repeat in this example each element twice and do not create the desired substructure. Conversely if you take for repetitions allowed a maximal example without desired substructure then each element appears at most twice and the underlying set must not contain a substructure. –  quid Dec 19 '12 at 17:02
This shows that the sizes of maximal examples without the desired substructure differ exactly by a factor 2. And to get the size guaranteeing substructure add 1 on both sides. Another equivalent notion here is cap or cap-set (in affine ternary spaces); indeed in this language these results date to the 50s (perhaps even 40s); for example Yves Edel's webpage contains a lot of information. –  quid Dec 19 '12 at 17:07
For the technical point: if you register an account (or also just preserve the cookie) you could comment on your question or edit it. This is desirable since on this site there should be a clear distinction between 'question' and 'answer' (and an answer should be really an answer of the question and not a reply). But it is not a 'big problem' either. I hope to have something more to say on the question later, but not yet sure I have some insight. In any case I find it interesting. –  quid Dec 19 '12 at 17:13
Quid, thank you. Yes, you explain clearly that $f(3,d)=2g(3,d)-1$. The function $g(n,d)$ is substantially different from $f(n,d)$ when $n>3$. Therefore I raise the question of the value of $g(4,3)$. Thanks for the reference to Yves Edel's webpage. –  user30099 Dec 19 '12 at 17:19