\documentclass{amsart}
\input{../../macros}
\begin{document}
[Prize winners: please sit in the front row]

[Introduction]

It's a great pleasure to be here, and it's fun to come to Northwestern.  Thanks for putting the winners up front so I can see who you are, and thanks to the rest of you too.

I want to talk about the card game set.  Let me start by talking about it as a game.  Many of you have played it.  You may have played it as kids.  Let me explain it.  A typical card looks like this (one purple squiggle).  It has a color, purple, a shading pattern, solid, a number, one, and a shape, blob.

This collection is not a ``set.'' For each of the four characteristics, three cards should be all the same or all different.  You may say, why should I play this game, it's unnatural.  Let's look here.  There are all three colors, but there's two and one for shading.  Without checking anything else, it's not a set.  You would need all three numbers, or the same number.  I'll lay out more cards.  We'll have an interactive portion.

For these, there's all three numbers, all three numbers, all three shadings, and all the same shape.

The first combinatorial question you could ask is, how many cards are there?  If you were an applied mathematician, you'd count them.  There's three colors, three shapes, three patterns, and three numbers.  Then the number of possibilities is 81.  This is why they had 4 different attributes.

You take turns setting down these cards.  If a player sees a set, you grab it.  You lay down more and more cards.  If you play with a small child, they will usually beat you.

A natural folk question is, how many cards can you have without a Set?  The answer is not so obvious.  When I first start playing this game, around 1998, I thought I'd figured it out.  It's not 16, I thought that at first.  I worked hard to prove this, it's wrong.  I'll tell you the answer in a little bit.  Something hard computationally is, you could play for years and years and not see these.  In practice I've never seen 16 on the table at once.

We could do a probabilistic analysis, but let's not, since it's not in my notes.  I have the meta question, what kind of math is this?  We could ask, is this math?  I want to try to problematize this question.  For now it's in extremal combinatorics.  You're counting things, and it containes the word largest or smallest, most or fewest.

Let me make the following observations:  let $x$ and $y$ be two distinct cards.  Then there is at most one Set containing them.  

Any two sets intersect in at most one card.  This suggests that thes are not sets, they are lines.  The cards are points.  That's what points and lines are.  That's modern geometery in a nutshell.

So to emphasize this point, we're asking, what is the largest set of points with no three colinear.  Now the geometry is not the usual geometry of Euclidean space.  I want to make another cultural point, when we have a problem to which we don't know the answer, we can replace the problem with an easier problem or replace the problem with a harder problem.  I'll replace the problem with an easier problem.  Let's restrict to two-dimensional Set.  Suppose there were only 9 cards.  I could just fix two of the attributes.  I could only use red ovals, and there ar 9 red ovals in my deck.  I could take those nine.  I've drawn them in a suggestive way.  This is a set.  They are vertical, horizontal lines, and then diagonal lines.
\[\xymatrix{
\bullet&\bullet&\bullet\ar@{-}[d]\\
\bullet&\bullet&\bullet\ar@{-}[d]\\
\bullet&\bullet&\bullet}\]
\[\xymatrix{
\bullet&\circ&\bullet\\
\bullet&\bullet&\circ\\
\circ&\bullet&\bullet}\]
So you can get four, and you can see why we guessed 16.  Surely you can't do any better than this, you think.  I think it's true, any four card that does the trick is like this.  Let me define the function I want to study.  Let $f(d)$ be the maximal number of non-collinear points in $d$-dimensional Set.  We've computed $f(2)=4$.  I'l give you $f(1)=2$.  I started with an extremal combinatorics problem and made it into a combinatorial geometry problem.

I only did this notationally.  Let me make it more formal and like number theory.  Linear structure: we don't like our objects to be things like blob or oval.  We'll encode red, green, and purple as $0$, $1$, and $2$ and likewise for oval, blob, and $1$, empty is $0$, and three is $0$, so three red empty ovals would be $(0,0,0,0)$.  I want $3$ to be zero.  These are elements of $\zZ/3\zZ$, or $\fF_3$.  I will later use the multiplication.  This is a point in $\fF_3^4$.  I'll just state the fact that three cards $x$, $y$, and $z$ are collinear if and only if they are collinear from solid geometry, there exists an $a\in \fF_3$ so that $ax+(1-a)y=z$.  In this particular case, for three elements this is special, if $a=1$ I get $x$, if $a=0$, I get y, and if I choose $2$, it will be $x+y+z=0$.  There are no three points that sum to zero.  You can also ask that no three points are in arithmetic progression.  A lot of popular combinatorics problems collapse into one here.

Okay, we've gotten rid of cards.  In this finite field, a four dimensional vector space, what's the largest cardinality of a set of points with no three collinear. 

What we know: first of all, let me put down the insight, the lowest possible value is $2^d$.   The highest value is $3^d$.  With a limited amount of work you could make it a little stronger.  You can make it a little bit better.  A better way to say this is that $2f(d-1)\le f(d)\le 3 f(d-1)$.  If you wanted to solve $3$ dimensional Set, if I want to make a maximal configuration, each level can't have more than $4$.  So $f(3)$ is at most $12$ and at least $8$.

Let me draw an example:
\[
\xymatrix{
\bullet&\bullet &\bullet &\ar@{-}[dd]&\circ&\bullet&\bullet&\ar@{-}[dd]&\bullet&\circ&\circ\\
\bullet&\bullet &\bullet &&\circ&\bullet&\bullet&&\bullet&\circ&\circ\\
\circ&\bullet &\bullet &&\bullet&\circ&\circ&&\bullet&\bullet&\bullet}
\]
So this shows that $f(3)\ge 9$, but it's actually $9$, so $f(4)$ is between $18$ and $27$.  It's better because you can check that $f(d_1+d_2)\ge f(d_1)f(d_2)$ by a Cartesian product construction, which suggests the following.  A consequence, if I want to know, by multiplying copies of this nine element configuration together, we know that $f(3n)\ge 9^n$, where the original lower bound is $8^n$.  One way of looking at this is to say, this is $(3^{\frac{2}{3}})^{3n}$, so $\log\ f(d)$, we should divide, if this were growing like something to the $d$, so we should divide by $d$.  So how does $\frac{\log\ f(d)}{d}$ behave as $d$ goes to $\infty$.  The upper bound says, maybe it's $\infty$.  The lower bound says, it's at least $3^{\frac{2}{3}}$.  This makes it a bit of a rarity.  I have no idea.  Neither do you.  Lots of people who have played this game think about it, and this problem has a long history in combinatorics, the affine cap set problem (see T. Tao's blog).  I want to finish, I have explained how this is a combinatorics and then a number theory problem.  I want to say a little about how it's an algebraic geometry problem.  If I have time I'll report that it's a harmonic analysis problem.  $f(4)$ is $20$.  If you try to construct it, it's pretty hard.  $f(5)$ is $45$ and $f(6)$ is $112$.  This has $2^{3^d}$ subsets.  I don't see a computational way to do this problem.

How would an algebraic geometer approach this?  A maximal nine-card configuration is a solution to $x^2+y^2=z$.  So if $z=0$, then $x$ and $y$ should be $0$.  This solution set, that gives the answer.  Why does this work?  If you're an algebraic geometer of the new school, you say this is a parabolic bowl.  You're doing this for a finite field, but shut up.  Can you find three points on this that are on a line?  No, you can't.  The blessing of modern algebraic geometry is that these arguments can be made rigorous.  Better yet, the twenty card solution is the solutions to $x^2+y^2=zw$ apart from $(0,0,0,0)$.  This is harder to draw, in more coordinates.  A line should strike this in only two points.  I got excited.  This argument doesn't work in more variables.  This does explain some of the smaller solutions.  No one knows how to get lower bounds.

That's the algebraic geometry of set.  Let me say the theorem on the upper bound side, Meshulem, $f(d)<\frac{2}{d}3^d$.  The methods used here were surprisingly enough Fourier analysis.  This involves bounding the Fourier transform of the characteristic function of the set of cards.  This is a way of making it harder.  

Harmonic analysis has changed a lot in the last five years, Gowers, Tao.  Just about two months ago, Bateman and Katz said $f(d)$ is less than a constant over $d^{1+\epsilon} 3^d$.

Gowers said he had an idea he was going to blog, and Katz said to take it down because they were working on it.  There were these secretive blog comments. ``Maybe don't talk about this.''

I'll close with an open question.  I've told you what we know.  The lower bounds we don't know what to do.  The upper and lower bounds are far apart.  I don't think people have worked on this.  Call a set of cards {\em maximal} if no card can be added to it without creating a Set.  That's a different concept than the biggest size possible.  How small can a maximal set be?  For $1$, $2$, and $3$, it's $2$, $4$, and $8$.  It's either $14$ or $15$ for $4$.  I must have written down a set of fifteen cards that you couldn't add to.  I'll leave that as something to work on.  I don't think Terry Tao tried to do this and failed.  I apologize for going over a bit.  Thank you very much.
%f(7) is between 224 and 624.
\end{document}