The card game Set lead to the following question. Lets call a subset $A$ of $(\mathbb{Z}/3)^n$ dependent, if there is $\{x,y,z\}\subset A$ with $x+y+z=0$. (So unlike the case of linear dependence we are not allowing any coefficients here).

Let $f(n)$ denote the maximal size of a independent subset of $(\mathbb{Z}/3)^n$. Is there an explicit expression / a recursion for $f(n)$? Can anything be said about its asymptotic behaviour (like $f\in O(c^n)$ for some minimal $c$)?

As $\{0;1\}^n$ is independent, we know that $f(n)\ge 2^n$. And so $c\ge 2$. The card game set deals with the case $n=4$ and $f(4)=20$ if i remember correctly.

  • $\begingroup$ You may be interested in some of the discussion around Polymath1, which I believe tackles similar questions. $\endgroup$ – Qiaochu Yuan Oct 6 '10 at 12:01
  • $\begingroup$ $f(4)=20$ is correct--that is, 20 is the minimum number of SET cards needed to guarantee a "set" in the context of the game. $\endgroup$ – Isaac Oct 6 '10 at 16:23
  • $\begingroup$ I am a bit confused. Both answers I got are contradicting each other, as the given recursion does not satisfy the claimed lower bound c>2. Furthermore In this presentation is sounded like its unknown,whether this recursion holds (it is in the chapter further work and it is followed by a ?-sign). Anyhow I am a bit confused right now. $\endgroup$ – HenrikRueping Oct 7 '10 at 0:16
  • $\begingroup$ You claimed c≥2, which the formulas I gave do satisfy (as it is O(2^n), so c=2). On a second look, you're right that the presentation to which I linked does not quite make it clear whether or not these formulas (which are not recursive) are correct, but that was how I read it and the formulas do seem to work for n=2, 3, 4, 5, and 6. $\endgroup$ – Isaac Oct 7 '10 at 0:40
  • $\begingroup$ "We have a lower bound of order c^n for some c > 2" I think this statement in harrisons answer contradicts the suggested formula. $\endgroup$ – HenrikRueping Oct 7 '10 at 9:37

Mathematicians call these "independent sets" capsets, and they're fairly widely studied. But surprisingly, we don't know much about their asymptotic behavior! We have a lower bound of order c^n for some c > 2; and we have an upper bound of order about 3^n/n (although this is not in the least trivial to prove!) Most mathematicians seem to suspect that the upper bound can't be improved to c^n for c strictly less than 3, but no one's sure how to prove this.

For more information (perhaps a little out-of-date, but I don't think much has changed) see Terry Tao's discussion.


Based on this presentation (PPT; Google-based HTML conversion), I think a formula for your $f(n)$ is: $$f(n)=\begin{cases} \frac{2^{n+2}-4}{3} & \text{ if }n\text{ is even} \\ \frac{2^{n+2}-5}{3} & \text{ if }n>1\text{ is odd} \end{cases}$$


Recently, Jordan Ellenberg and Dion Gijswijt have proved using the ideas of Croot-Lev-Pach, that $f(n) \in O(2.756^n)$.

This is the best possible bound we have so far. See the preprints, https://quomodocumque.files.wordpress.com/2016/05/cap-set.pdf and http://homepage.tudelft.nl/64a8q/progressions.pdf. Also see the blog post ``Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem!'' by Gil Kalai.

The upper bound they have obtained can also be stated as "a cap set has size bounded above by the number of monomials $x_1^{e_1}x_2^{e_2}\cdots x_n^{e_n}$ of total degree at most $2n/3$ that satisfy $0 \leq e_i \leq 2$ for all $i$.}".

The beautiful proof can be summarised as follows (take $q = 3$ for capsets).

Let $q$ be an odd prime power and let $\mathcal{P}_d(n, q)$ denote the set of all polynomials $f$ in $\mathbb{F}_q[x_1, \dots, x_n]$ that satisfy $\deg f \leq d$ and $\deg_{x_i} f \leq q - 1$ for all $i$, aka, the set of reduced polynomials of degree at most $d$. The set of all reduced polynomials with no restriction on the total degree is simply denoted by $\mathcal{P}(n, q)$. There is a vector space isomorphism between $\mathcal{P}(n, q)$ and the space of all $\mathbb{F}_q$-valued functions on $\mathbb{F}_q^n$ given by evaluating the polynomial.

For a $3$-term arithmetic progression free subset $A$ of $\mathbb{F}_q^n$, the sets $A + A = \{a + a' : a, a' \in A, a \neq a'\}$ and $2A = \{a + a : a \in A\}$ are disjoint. Let $U$ be the subspace of $\mathcal{P}(n, q)$ consisting of all the polynomials that vanish on the complement of $2A$. Then $\dim U = |2A| = |A|$ (since $q$ is odd) and thus we try to find upper bounds on $\dim U$. For any integer $d \in \{0, 1, \dots, n(q - 1)\}$ let $U_d$ be the intersection of $\mathcal{P}_d(n, q)$ with $U$. Then since $\langle U, \mathcal{P}_d(n, q) \rangle \leq \mathcal{P}(n, q)$ we have $\dim U \leq \dim \mathcal{P}(n, q) - \dim \mathcal{P}_d(n, q) + \dim U_d$.

Now the crux of the proof is Proposition 1 in Jordan's preprint, which says that every (reduced) polynomial of degree at most $d$ which vanishes on $A + A$ has at most $2 \dim P_{d/2}(n, q)$ non-zeros in $2A$. Since $A + A$ is a subset of the complement of $2A$, we see that every element of $U_d$, when seen as an element of $\mathbb{F}_q^{\mathbb{F}_q^n}$ via the evaluation isomorphism, has at most $2 \dim \mathcal{P}_{d/2} (n, q)$ non-zero coordinates, and thus $\dim U_d \leq 2 \dim \mathcal{P}_{d/2}(n, q)$.

Therefore, we get $|A| = \dim U \leq q^n - \dim \mathcal{P}_d(n, q) + 2 \dim \mathcal{P}_{d/2}(n, q) = \dim \mathcal{P}_{n(q - 1) - d} (n, q) + 2\dim P_{d/2}(n, q)$. Finally observe that $n(q - 1) - d = d/2$ when $d = 2(q - 1)n/3$ which gives us the bound $$|A| \leq 3 \dim \mathcal{P}_{(q - 1)n/3}(n, q)$$ (whenever $(q - 1)n/3$ is an integer). The reason why this is a good bound is that $\dim \mathcal{P}_{d}(n, q)$ is bounded above by $q^{\lambda n}$ for some $\lambda < 1$ when $d < (q - 1)n/2$ (see the preprints).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.