A question related to the card game "Set"

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