# 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). – user9072 Dec 19 '12 at 16:00

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.
• 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