Game. SET. Polynomial.

This article will describe an incredibly simple technique that vastly improves a result related to the game of SET...

David AustinDavid Austin
Grand Valley State University
Email David Austin

 

Introduction

A recent Feature Column explored some mathematical ideas that appear while playing the card game SET®, in which players examine a hand of cards searching for a collection of three cards that form a "set." We determined how large a hand could be if it contains no set.

In this column, we will revisit this question and describe a new application of the polynomial method introduced in May of this year (2016) that leads to powerful results about a generalized version of this question. What is most remarkable about this technique is its simplicity. Although the problem we'll describe has been well studied by number theorists for some time, we will obtain dramatic improvements in our understanding using straightforward ideas that are accessible to undergraduates.

The game of SET

To review, SET is played with a deck of 81 cards. On each is printed a number of symbols, as seen on these typical cards.

 

The game centers around four features of the symbols--their color, number, shape, and shading. There are three possibilities for each feature.

Color:
Number:
Shape:
Shading:
 

Each card is unique; the 81 cards are created by choosing one of the three possible values for each of the four features.

Three cards are said to form a set if each of the four features, considered individually, are either the same on each card or different on each card. For instance, these three cards form a set:

 

In playing the game, one is quickly led to ask: "How many cards must be dealt to guarantee the presence of a set?" or, equivalently, "How large can a hand be if it does not contain a set?" In our previous column, we saw that there is a collection of 20 cards that does not contain a set, but that any collection of 21 cards will.

Using ${\Bbb F}_3 = \{0,1,2\}$ to denote the field of three elements, we saw that each SET card may be associated with an element in ${\Bbb F}_3^4$, and that cards $a$, $b$, and $c$ form a set if and only if $$ a+b+c = 0. $$

We then translated our question about the game of SET into this: "How large can a subset $A\subset {\Bbb F}_3^4$ be if it admits no solutions to $a+b+c=0$ with distinct $a$, $b$, and $c$?"

Generalizations

One obvious way to generalize this question is to change the number of features on the cards. For instance, we could add a fifth feature, such as texture, having three possible values and ask how large a hand can be if it does not contain a set.

More generally, we ask "how large can a subset $A\subset {\Bbb F}_3^n$ be if there are no solutions to the equation $a+b+c=0$ with $a$, $b$, and $c$ in $A$ distinct?"

We call such a subset $A$ an $n$-cap and use $C_n$ to denote the maximum cardinality of an $n$-cap. In our previous column, we saw that, for small values of $n$, we have

$n$ 2 3 4 5
$C_n$ 4 9 20 45
 

However, not much is known beyond these small values of $n$. In this column, we will investigate how these numbers grow as $n$ increases. Let's first think about what we can expect.

Shown below is an example of a 2-cap $A$, which has four elements.

 

Moving to $n=3$, we obtain a $3$-cap by placing two copies of $A$ in two layers of ${\Bbb F}_3^3$.

 

It is therefore reasonable to think that $C_n$ will at least double when $n$ increases by 1; perhaps we could even do a bit better. Shown below is a 3-cap obtained by applying an affine transformation to one of the copies of $A\subset{\Bbb F}_3^2$ and then adding another point in the third layer to obtain a $3$-cap with 9 elements.

 

In fact, Edel showed in 2004 that $C_n$ grows at least by a factor of 2.2 every time $n$ increases by 1.

At the same time, it doesn't seem realistic to expect that we could put three copies of $A$, one in each layer, and obtain a 3-cap, even if we artfully apply affine transformations in each layer. Therefore, we expect that $C_n$ grows by a factor no more than $3$. In fact, Brown and Buhler proved this in 1982: $|C_n| = O(3^n)$.

This was improved by Meshulam in 1995. The space ${\Bbb F}_3^n$ has $3^n$ elements; Meshulam showed that the fraction of elements in an $n$-cap is proportionally no more than $1/n$. In 2012, Bateman and Katz improved this estimate by showing that this fraction is proportional to $1/n^{1+\epsilon}$ for some positive value of $\epsilon$. Until this year, their result was the best known.

This article will describe an incredibly simple technique that vastly improves this result to $$ |C_n| = O(2.756~^n). $$ This means that, as $n$ grows, $|C_n|$ will grow by no more than a factor of 2.756, a dramatic improvement on earlier results.

For example, when $n=1000$, Meshulam's result says that the fraction of elements in a $1000$-cap cannot be more than 0.001. By contrast, $(2.756)^{1000}~/~3^{1000} \approx 10^{-37}$ so that we now know that the fraction of elements in a $1000$-cap cannot be more than $10^{-37}$.

Reframing our algebraic condition leads to another type of generalization. Remember that we are working in ${\Bbb F}_3$ where $1+2 = 0$. $$ \begin{align} a+b+c & = 0 \\ a + b & = -c \\ a + b & = 2c \\ \end{align} $$

We may then generalize our question to allow a larger number of possibilities for each of the features on a SET card. Allowing $q$ possibilities, we may ask: "How large can a set $A\subset{\Bbb Z}_q^n$ be for which the equation $a+b=2c$ has no solutions with $a$, $b$, and $c$ distinct?"

Solutions to this equation form three consecutive terms, $a,c,b$, in an arithmetic progression in ${\Bbb Z}_q^n$ so we call a set $A$ having no distinct solutions progression-free. The question of finding an upper bound for the number of elements in a progression-free set has a rich history in number theory. The work we'll describe in this column applies to this problem as well. We will, however, ultimately focus on the case $q=3$, which originally comes from the game SET.

Comments?

Polynomials

In May, Croot, Lev, and Pach introduced a technique for proving that a progression-free subset of ${\Bbb Z}_4^n$ has size $O(c^n)$ for some constant $c\lt 4$. Within a few days, Ellenberg and Gijswijt independently extended their technique to subsets of ${\Bbb F}_q^n$ where $q$ is an odd prime; in particular, their results apply to the SET problem where $q=3$. We will now begin to describe this method.

Let $M_n$ be the set of monomials $x_1^{\alpha_1}x_2^{\alpha_2}\ldots x_n^{\alpha_n}$ where the degree in each variable $0\leq\alpha_i \leq q-1$. By $S_n$, we will mean the set of polynomials with coefficents in ${\Bbb F}_q$ spanned by $M_n$. The dimension of $S_n$ is $q^n$.

A polynomial defines an ${\Bbb F}_q$-valued function on the set ${\Bbb F}_q^n$ by evaluating the polynomial; for instance, if $$ P(x) = \sum_{\alpha_1,\alpha_2,\ldots,\alpha_n} c_{\alpha_1,\alpha_2,\ldots,\alpha_n} x_1^{\alpha_1}x_2^{\alpha_2} \ldots x_n^{\alpha_n} $$ and $a = (a_1,a_2,\ldots, a_n) \in {\Bbb F}_q^n$, then $$P(a) = \sum_{\alpha_1,\alpha_2,\ldots,\alpha_n} c_{\alpha_1,\alpha_2,\ldots,\alpha_n} a_1^{\alpha_1}a_2^{\alpha_2} \ldots a_n^{\alpha_n}. $$

By $\mbox{Map}({\Bbb F}_q^n, {\Bbb F}_q)$, we will denote the set of ${\Bbb F}_q$-valued functions on ${\Bbb F}_q^n$. Notice that this is also an ${\Bbb F}_q$-vector space of dimension $q^n$. In fact, the evaluation map $e:S_n \to \mbox{Map}({\Bbb F}_q^n, {\Bbb F}_q)$ is an isomorphism.

 

To understand why, we only need to show that every function in $\mbox{Map}({\Bbb F}_q^n, {\Bbb F}_q)$ is given by evaluating a polynomial in $S_n$ since the vector spaces have the same dimension.

Let's begin with $n=1$ and denote ${\Bbb F}_q = \{0,1,2,\ldots,q-1\}$. Consider the polynomial $P_j\in S_1$ where $$ P_j(x) = c\prod_{\overset{i = 0}{i\neq j}}^{q-1} (x-i). $$ With an appropriate choice of constant $c$, we have $P(i) = 0$ if $i\neq j$ and $P(j) = 1$.

More generally, if $a = (a_1,a_2,\ldots,a_n)\in{\Bbb F}_q^n$, then $$ P(x) = \prod_{i=1}^n P_{a_i}(x_i) $$ is a polynomial in $S_n$ with $P(x) = 0$ if $x\neq a$ and $P(a) = 1$. This is enough to show that the evaluation map is an isomorphism.

The evaluation map will play a significant role in our investigation into the size of subsets of ${\Bbb F}_q^n$. In particular, given a polynomial $P$ in $S_n$, we may consider its support $\Sigma$, the set of points in ${\Bbb F}_q^n$ for which $P$ is nonzero.

For example, the support of the polynomial $$ P(x) = \prod_{i=1}^n P_{a_i}(x_i) $$ is the single point $a$. Notice that the degree of $P(x)$ is the largest possible, $(q-1)n$.

On the other hand, we may consider the constant, or degree 0, polynomial $P(x) = 1$, whose support is all of ${\Bbb F}_q^n$.

These examples point to a relationship between the degree of a polynomial $P$ and the size of its support $\Sigma$. Since the evaluation map is an isomorphism, if we are given a set $C\subset {\Bbb F}_q^n$, we may find a polynomial whose support $\Sigma = C$. The degree of $P$ will provide a means of understanding the size of $C$.

With this thought in mind, we will denote by $M_n^d$ the set of monomials whose total degree is no more than $d$; that is, a monomial $x_1^{\alpha_1} x_2^{\alpha_2} \ldots x_n^{\alpha_n}$ is in $M_n^d$ if $0\leq \alpha_i \leq q-1$ and $\alpha_1 + \alpha_2 + \ldots + \alpha_n \leq d$. The span of these monomials is denoted by $S_n^d$, the set of polynomials of degree no more than $d$, while $m_d$ denotes the dimension of $S_n^d$.

Notice that there is an involution of monomials in $M_n$ given by $$ x_1^{\alpha_1} x_2^{\alpha_2}\ldots x_n^{\alpha_n} \mapsto x_1^{q-1-\alpha_1} x_2^{q-1-\alpha_2}\ldots x_n^{q-1-\alpha_n}. $$ Under this involution, a monomial of degree $d$ is carried into a monomial of degree $(q-1)n - d$. Consequently, this involution is a bijection between the set of monomials whose degree is greater than $d$ and the set of monomials whose degree is less than $(q-1)n-d$. This says that $$ q^n - m_d = m_{(q-1)n-d-1} \leq m_{(q-1)n-d}. $$

A preliminary result

Recall that our aim is to obtain a bound on the size of a progression-free subset $A$ of ${\Bbb F}_q^n$ and that this means the equation $$ a + b = 2c $$ has no solutions in $A$ other than $a=b=c$.

Given a subset $A$, we will form sets $B$ and $C$ where $$ \begin{align} B=&\{a+a'~|~a,a' \in A, a\neq a'\} \\ C=&\{2a ~|~ a \in A\}. \end{align} $$

Notice that $A$ is progression-free if and only if $B$ and $C$ are disjoint. Also, notice that, since $q$ is odd, the cardinality of $C$ is the same as that of $A$; that is, $|A| = |C|$.

We will consider polynomials whose supports are contained in $C$. Since $B$ is disjoint from $C$, these polynomials necessarily vanish on $B$. By studying the degree of such polynomials, we hope to obtain a bound on $|C| = |A|$. In particular, we will demonstrate the following preliminary result:

 

Suppose $P$ is a degree $d$ polynomial such that $P(b) = 0$ for all $b\in B$. Then the number of points in $C$ for which $P(c)\neq 0$ is no more than $2m_{d/2}$: $$ \left|\{c\in C~|~ P(c)\neq 0\}\right| \leq 2m_{d/2}. $$

It may be helpful to have an example to look at as we develop this argument. We will choose $q=3$, $n=2$ and the set $A=\{(0,0), (1,0), (0,1), (1,1)\}$ as shown below.

 

The corresponding sets $B$ and $C$ are as shown.

$B$ $C$
 

Notice that our set $A$ is progression-free since $B$ and $C$ are disjoint. The polymomial $P(x) = (1-x_1)(1-x_2) \in S_2^2$, whose degree is $d=2$, vanishes on $B$. Our result is verified by noting that $P$ is nonzero at each of the four points of $C$ and $$4 \leq 2m_{2/2} = 2\cdot 3 = 6.$$

To explain why this result holds, we will form the $|A|\times|A|$ matrix $R$ whose entries $R_{a,a'} = P(a+a')$. We will look at the rank of $R$ in two ways.

 

  • First, If $a\neq a'$, then $a+a'\in B$, and we have $P(a+a') = 0$ since we are assuming that $P$ is zero on $B$. This means that the only nonzero elements in $R$ must be diagonal entries $R_{a,a} = P(2a)$. Therefore, the rank of $R$ equals the number of elements of $A$ for which $P(2a) \neq 0$, or, equivalently, the number of elements of $C$ for which $P(c) \neq 0$.

  • Let's look at the matrix $R$ in a different way by considering $P(x+y)$. By the binomial theorem, we know that $$ (x+y)^p = \sum_{k=0}^p {p\choose k} x^ky^{p-k}. $$ In particular, $(x+y)^p$ is the sum of terms in $x$ and $y$ and the degree in $x$ and the degree in $y$ add to $p$.

    Similarly, if we now consider $x,y\in{\Bbb F}_q^n$, then \[ \begin{align} P(x+y) = & \sum_{|\alpha| \leq d} c_{\alpha} (x_1+y_1)^{\alpha_1} (x_2+y_2)^{\alpha_2} \ldots (x_n+y_n)^{\alpha_n} \\ = & \sum_{|\alpha|\leq d} c_{\alpha} \sum_{\beta} c'_{\beta} x_1^{\beta_1}x_2^{\beta_2}\ldots x_n^{\beta_n} y_1^{\alpha_1-\beta_1}y_2^{\alpha_2-\beta_2}\ldots x_n^{\alpha_n-\beta_n} \\ = & \sum_{\substack{m,m'\in M_n^d \\ \deg(mm')\leq d}} c_{m,m'}m(x) m'(y). \end{align} \]

    Since the product of monomials $m(x)m'(y)$ in each term of the sum has degree no more than $d$, one of the monomials $m$ or $m'$ must have degree no more than $d/2$. This means that we may write $$ P(x+y) = \sum_{m\in M_n^{d/2}} m(x) F_m(y) + \sum_{m'\in M_n^{d/2}} G_{m'}(x)m'(y). $$

    For instance, in our example above, we have $P(x) = (1-x_1)(1-x_2)=1-x_1-x_2+x_1x_2$ so that we may decompose $$ \begin{align} P(x+y) & = 1 - x_1 - y_1 - x_2 - y_2 + x_1x_2 + x_1y_2 + y_1x_2 + y_1y_2 \\ & = 1 (1+y_1y_2) + x_1 (-1+y_2) + x_2(-1+y_1) \\ & + x_1x_2 (1) + (-1)y_1 + (-1)y_2 \\ \end{align} $$

    Therefore, $$ \begin{array}{lll} F_{1}(y) = 1+y_1y_2, & F_{x_1}(y) = -1+y_2, & F_{x_2}(y) = -1+y_1 \\ G_{1}(x) = x_1x_2, & G_{y_1} = -1, & G_{y_2} = -1. \end{array} $$

    As this example shows, the decomposition is not unique. This does illustrate, however, that the matrix $R$ may be written as a sum of $2m_{d/2}$ matrices. Since $$ R_{a,a'} = P(a+a') = \sum_{m\in M_n^{d/2}} m(a) F_m(a') + \sum_{m'\in M_n^{d/2}} G_{m'}(a)m'(a'), $$ we may define matrices $T_m$ and $U_{m'}$ so that $$(T_m)_{a,a'} = m(a) F_m(a'),\hskip{0.5in} (U_{m'})_{a,a'} = G_{m'}(a) m'(a'). $$

    In our example, $T_{x_1}$ is the matrix \[ \begin{array}{c|cccc} a \backslash a' & (0,0) & (1,0) & (0,1) & (1,1) \\ \hline (0,0) & 0 & 0 & 0 & 0 \\ (1,0) & -1 & -1 & 0 & 0 \\ (0,1) & 0 & 0 & 0 & 0 \\ (1,1) & -1 & -1 & 0 & 0 \end{array} \]

    Since $(T_m)_{a,a'} = m(a) F_m(a')$, every row is a scalar multiple of $F_{m}(a')$ from which it follows that $T_m$ has rank 1.

    In the same way, $(U_{m'})_{a,a'} = G_{m'}(a)m'(a)$, which shows that every column of $U_{m'}$ is a scalar multiple of $G_{m'}(a)$. Therefore, $U_{m'}$ also has rank 1.

    Notice that $R = \sum_{m\in M_n^{d/2}} T_m + \sum_{m'\in M_n^{d/2}} U_{m'}$ is the sum of $2m_{d/2}$ matrices each having rank 1. This means that the rank of $R$ is no more than $2m_{d/2}$.

We saw earlier that the rank of $R$ is equal to the number of elements of $C$ for which $P(c)\neq 0$. This means

The number of elements of $C$ for which $P(c)\neq 0$ is no more than than $2m_{d/2}$.

Comments?

Finding the bound $|A| \leq 3m_{(q-1)n/3}$

Using the bound we just found, we will now bound the size of a progression-free set $|A|$ by the dimension of a space of polynomimals: $$ |A|\leq 3m_{(q-1)n/3}. $$

To this end, we introduce the space $W$ of polynomials whose support is contained in $C$. Since $B$ and $C$ are disjoint, the polynomials in $W$ must vanish on $B$ so that the result of the previous section applies.

Choosing a degree $d$, we will consider $V$, the space of polynomials in $W$ whose degree is no more than $d$; that is, $$ V = S_n^d \cap W. $$

Let's consider the dimension of $V$. By definition, the dimension of $S_n^d$ is $m_d$. Since the evaluation map is an isomorphism, we know that the dimension of $W$ is $|C| = |A|$. This shows that $$ \begin{align} \dim V & \geq \dim S_n^d + \dim W - \dim S_n \\ \dim V & \geq m_d + |A| - q^n. \end{align} $$

If $d$ is large enough, we then know that $\dim V > 0$ and, in particular, $V$ is not empty.

We claim that

There is a polynomial $P\in V$ whose support satisfies $|\Sigma| \geq \dim V.$

To see this, choose a basis $v_1,v_2,\ldots,v_p$ for $V$, where $p=\dim V$. In this basis, the evaluation map $e:V\to \mbox{Map}(C, {\Bbb F}_q)$ is represented by the $|C|\times p$ matrix $E$ where $$ E_{c,j} = v_j(c). $$

Since the evaluation map is injective, the matrix $E$ has rank $p$. We will let $C'$ be the elements of $C$ corresponding to the pivot rows of $E$. It follows that $|C'| = p = \dim V$ and that the $p\times p$ matrix $E'$ whose entries are $E'_{c',j} = v_j(c')$ is invertible. Solving the equation $E'z = (1,1,\ldots,1)$ gives a polynomial $$P=z_1v_1 + z_2v_2 + \ldots + z_pv_p$$ satisfying $P(c') = 1$. Therefore, the support of $P$ contains $C'$ and hence $|\Sigma| \geq |C'| = \dim V$.

We are now in position to explain why $|A|\leq 3m_{(q-1)n/3}$ using a polynomial $P$ in $V$ whose support satisfies $|\Sigma|\geq\dim V$. Since $P(b)=0$ for all $b\in B$, our preliminary result applies so that $\left|\{c\in C~|~P(c)\neq 0\}\right| = |\Sigma| \leq 2m_{d/2}$.

However, we also know that $|\Sigma| \geq \dim V \geq m_d+|A|-q^n$ implying that $$ m_d + |A| - q^n \leq |\Sigma| \leq 2m_{d/2} $$ or $$ |A| \leq 2m_{d/2} + q^n - m_d. $$

Recall from our earlier discussion that $$ q^n - m_d \leq m_{(q-1)n-d} $$ If we apply this when $d = 2(q-1)n/3$ and $d/2 = (q-1)n/3$, we have $$ q^n - m_{2(q-1)n/3} \leq m_{(q-1)n/3}, $$ which implies that $$ |A| \leq 2m_{(q-1)n/3} + q^n - m_{2(q-1)n/3} \leq 3m_{(q-1)n/3}. $$

Finding a bound for $m_d$

We have made good progress since we are able to bound $|A|$ by the dimension of a specific space of polynomials. We would therefore like to understand the dimension of this space.

Recall that $m_d$ is the number of monomials of degree no more than $d$. Of course, the total number of monomials in $M_n$ is $q^n$ so we may rephrase this question by asking to find the fraction of monomials in $M_n$ whose degree is no more than $d$; that is, we seek to understand $m_d/q^n$.

We investigate this probabilistically by choosing exponents $\alpha_1,\alpha_2,\ldots,\alpha_n$ with $0\leq \alpha_i\leq q-1$ randomly and with equal probability. The ratio $m_d/q^n$ is the probability that $\alpha_1+\alpha_2 + \ldots + \alpha_n \leq d$ or the probability that the mean $$ \overline{\alpha}_n=\frac{\alpha_1+\alpha_2 + \ldots + \alpha_n}{n} \leq \frac dn. $$

Shown below are the distributions of the mean $\overline{\alpha}_n$ for $n=50$, $100$, and $200$ when $q=3$. We are interested in understanding the probability that the mean $$\overline{\alpha}_n \leq \frac{(q-1)n/3}{n} = 2/3. $$

 

These figures verify two things that we expect. First, choosing $\alpha_1,\alpha_2,\ldots,\alpha_n$ is the same thing as making $n$ independent choices of $0$, $1$ or $2$ with equal probability. The Law of Large Numbers implies that, as $n$ grows, the distribution $\overline{\alpha}_n$ approaches the mean $(q-1)/2$, which is 1 when $q=3$.

Second, the Central Limit Theorem implies that the distribution of $\alpha_n$ is increasinlgy well approximated, as $n$ grows, by a normal distribution with decreasing variance. This shows that the probability that $\overline{\alpha}_n\leq 2/3$ decreases with $n$; in fact, we will see that it decreases exponentially.

The condition that $\overline{\alpha}_n\leq 2/3$ may be estimated using the theory of large deviations, a rich, well-developed theory into which we simply dip our toes.

First, some notation: given a random variable $X$, the probability that $X$ takes on the value $x$ is ${\Bbb P}(X=x)$ while the expected value of $X$ is ${\Bbb E}[X]$.

We now explain Markov's inequality, which states that for a non-negative random variable $X$ and $c > 0$, then $$ {\Bbb P}(X \geq c) \leq \frac{{\Bbb E}[X]}{c}. $$

To see this, we will assume that $X$ is a discrete random variable. Then Markov's inequality follows from $$ \begin{align} {\Bbb E}[X] & = \sum_{x} x~{\Bbb P}(X=x) \\ & = \sum_{x\lt c} x~{\Bbb P}(X=x) + \sum_{x\geq c} x~{\Bbb P}(X=x) \\ & \geq \sum_{x\geq c} x~{\Bbb P}(X=x) \\ & \geq \sum_{x\geq c} c~{\Bbb P}(X=x) \\ & \geq c\sum_{x\geq c}{\Bbb P}(X=x) \\ & \geq c{\Bbb P}(X\geq c). \end{align} $$

Now, we are interested in estimating $$ m_{d}/q^n = {\Bbb P}\left( \overline{\alpha}_n \leq \frac dn\right) = {\Bbb P}\left(\alpha_1+\alpha_2+\ldots+\alpha_n \leq d\right). $$

In order to apply Markov's inequality, we multiply by a negative constant $\theta<0$ to reverse the inequality and exponentiate to obtain a positive random variable: $$ \begin{align} m_d/q^n & = {\Bbb P}\left(\theta(\alpha_1+\alpha_2+\ldots+\alpha_n) \geq \theta d\right) \\ & = {\Bbb P}\left(\exp\left(\theta\sum_{i=1}^n \alpha_i\right) \geq \exp(\theta d)\right) \\ & \leq \frac{{\Bbb E}\left[\exp(\theta\sum_{i=1}^n\alpha_i)\right]} {\exp(\theta d)} \\ & \leq \frac{{\Bbb E}\left[\prod_{i=1}^n \exp(\theta \alpha_i)\right]} {\exp(\theta d)} \\ & \leq \left(\frac{{\Bbb E}\left[\exp(\theta \alpha_1)\right]} {\exp(\theta d/n)}\right)^n \\ & \leq \left(\frac{(1 + e^{\theta} + e^{2\theta} + \ldots + e^{(q-1)\theta})/q} {e^{\theta d/n}}\right)^n\\ \end{align} $$

We therefore obtain a bound on $m_d/q^n$ by minimizing $$\frac{(1 + e^{\theta} + e^{2\theta} + \ldots + e^{(q-1)\theta})/q} {e^{\theta d/n}} $$

over all $\theta<0$.

In the case that $q=3$, it follows that $d=(q-1)n/3 = 2n/3$. Therefore, we will minimize the function $$ f(\theta) = \frac{(1+e^\theta + e^{2\theta})/3}{e^{2\theta/3}} $$

over the set of real numbers $\theta \lt 0$. Of course, this is equivalent to minimizing $$ g(\theta) = \ln(f(\theta)) = \ln\left((1+e^\theta+e^{2\theta})/3\right) - 2\theta/3. $$

A straightforward exercise in first-year calculus shows that $g$ has a minimum when $e^\theta = (\sqrt{33}-1)/8$ and that $$ f\left(\frac{\sqrt{33}-1}{8}\right) \approx 0.918368 $$

showing that $$ \begin{align} m_{2n/3}/3^n & \leq 0.918368^n \\ m_{2n/3} & \leq (3\cdot 0.918368)^n \leq 2.756^n. \end{align} $$

Remember that our earlier estimate on the size of a progression-free subset $A$ of ${\Bbb F}_3^n$ gave $$ |A| \leq 3m_{2n/3} \leq 3\cdot 2.756^n. $$

We therefore obtain our desired result that the maximum cardinality of an $n$-cap $$|C_n| = O(2.756^n).$$

Similar reasoning shows that, for odd primes $q$, there is a constant $c\lt q$ such that a progression-free subset $A$ of ${\Bbb F}_q^n$ satisfies $$ |A| = O(c^n). $$

Comments?

Summary

The paper of Croot, Lev, and Pach, which applied the polynomial method to progression-free subsets of ${\Bbb F}_4^n$, is only six pages long, speaking to the elegance and simplicity of their work. Indeed, reading it one thinks in one minute, "How did anyone think to do this?" and, in the next, "Why had no one done this before?"

Once public, the Croot-Lev-Pach paper set off a flurry of work, described by Ellenberg as "math at Internet speed," as mathematicians sought to apply this technique to a wide range of combinatorial problems. “The cap set problem we think of as a model problem for all these other questions in Ramsey theory,” says Terence Tao.

Tim Gowers wrote: "I could almost feel my brain expanding as I read Jordan Ellenberg’s preprint and realized that here was a major new technique to add to the toolbox."

In spite of the readability of the original papers and the amount written about these developments on the internet, I wanted in this column to expand some parts of the arguments so that, say, interested undergraduates could more easily participate in these ideas as they are being developed.

References

 

David AustinDavid Austin
Grand Valley State University
Email David Austin