## Set — the card game

I’d like to talk about the card game Set. Why? Because the goal is to find affine lines! Huh?

Well, first you have to understand that we’re not working over the usual fields we draw our intuition from. We’re using the field of integers modulo . A bit more explicitly, we start with the ring of integers and quotient out by the ideal of multiples of . This is a maximal ideal, because if we add in any other integer we can subtract off the closest multiple of . Then we’re left with either or , and this gives us all the integers in our expanded ideal. But we know that the quotient of a ring by a maximal ideal is a field! Thus adding and multiplying integers modulo gives us a field. For the three elements of we’ll use (using instead of the usual ).

So what does this have to do with the card game? Well, each one has four features, each picked from three choices:

- Colors: red, green, or purple
- Symbols: squiggles, diamonds, or ovals
- Patterns: solid, striped, or outlined
- Numbers: one, two, or three

Let’s consider the color alone for now. We choose (somewhat arbitrarily) to correlate the colors red, green, and blue with the elements , , and of , respectively. We don’t want to think of them as “being” the field elements, nor even as the elements of a one-dimensional vector space over . The arbitrariness of our correspondence points to the fact that the colors constitute an affine line over !

Similarly, we have lines for symbols, patterns, and numbers. And it’s pretty straightforward to see that we can take the product these affine lines to get a four-dimensional affine space. That is, the cards in Set form an affine four-space over , and this is the stage on which we play our game.

Now what’s the goal of the game? You have to identify a collection of three cards so that in each of the four characteristics they’re all the same or all different. What I assert is that these conditions identify affine lines in the affine four-space. So what’s an affine line in this context?

Well, first let’s move from the affine four-space of cards to the affine four-space of four-tuples of field elements. We’ll just use the lists of choices above and identify them with , , and , respectively, and read them in the same order as above. That is, the four-tuple would mean the card with two purple, striped squiggles. We can do this because (since they’re torsors) all affine spaces of the same dimension over the same field are isomorphic (but not canonically so!).

Now we can say that an affine line is a map from the standard affine line (given by “one-tuples” of field elements) to this affine four-space. But it can’t be just any function. It has to preserve relative differences! Since we have only three points to consider, we can reduce this question somewhat: an affine line is a list of three four-tuples of field elements, and the difference from the first to the second must equal the difference from the second to the third.

So we can take any two points, and then we can work out what the third one has to be from there. And we can tell that each of the four components works independently from all the others. So let’s look at colors alone again. Let’s say that the first two cards have colors and . Then the affine condition says that . That is, . It’s straightforward from here to see that if , then is again the same as those two. On the other hand, if and are different, then must be the remaining choice.

What have we seen here? If we start with two cards with the same color, the third card on the affine line will have the same color as well. If the first two cards have different colors, the third one will be the remaining color. And the same analysis applies to symbols, patterns, and numbers. Thus affine lines are sets of three cards which are all the same or all different in each of the four characteristics.

Now that we know that, what can we do with it? Well, look at the gameplay. We don’t have all of the cards spread out at once: we deal out a certain number at a time. So the question is: how many points in the affine space can we take *without* them containing an affine line? This is analogous to the problem of placing eight queens on a chessboard. A more advanced problem is to give the expected number of affine lines in a subset of size .

You mean “a less advanced problem” in the last sentence, right? (My probabilistic bias is showing.) It’s C(n,3) (the number of sets of three points in the n chosen points) times the probability of three randomly chosen points being an affine line. That probability is 1/79 — once we pick the first two points, exactly one of the remaining 79 points will make an affine line. I happen to know the answer to the problem of finding the maximal set, but I have no idea

whyit’s true.More generally, your second problem is about finding the expected value, and expected values are easy to find. Your first problem is about finding the extreme of some distribution, and extremes are hard.

Here’s another problem — I deal out cards one at a time until there’s a set among the cards. How many cards do I expect to need? My first prediction would be enough that C(n,3) is greater than 79 — so somewhere around nine cards. But I haven’t checked this.

Comment by Isabel Lugo | July 17, 2008 |

Is there a connection to the fact that the collection of Set cards, together with the binary operation * (where a*b is the unique card that forms a set with a and b) is a quandle?

Comment by musesusan | July 17, 2008 |

Isabel: I think of it as being more conceptually advanced, rather than technically. But that’s as maybe.

Susan: Actually I wish WordPress hadn’t given the link to that other post of mine, because I was thinking about this as I wrote the entry, and I think there might be a paper in there. However, it’s pretty squirrelled away, and I hope it’ll stay safe.

However, if someone wanted to discuss the matter not so much out in public where I might tip my hand…

Comment by John Armstrong | July 17, 2008 |

Perhaps. I disagree with your intuition, though — I think I could with significant prodding get the proverbial sophomore to solve your second problem. But not your first problem. (Could they conjecture the answer to the first problem? Sure. But I don’t think they could prove it.)

Comment by Isabel Lugo | July 17, 2008 |

Uh-oh… well, I would’ve just pointed out that affine spaces over Z_3 are in natural correspondence with commutative, involutory quandles satisfying (A |> B) |> (C |> D) = (A |> C) |> (B |> D), by taking A |> B to be B + (B – A) [as basically pointed out on Wikipedia at http://en.wikipedia.org/wiki/Affine_space#Affine_spaces_over_the_3-element_field%5D.

(How does one enter LaTeX into WordPress comments?)

Comment by Sridhar Ramesh | July 17, 2008 |

The same as anywhere else on WordPress: begin with $ latex (lose the space between $ and latex) and end with $.

And yes, that’s true. The (cryptic) question now is how does that extend in various ways?

Comment by John Armstrong | July 17, 2008 |

Ah. Not having used WordPress before, I was unaware. Let me test: . Hopefully that works…

Comment by Sridhar Ramesh | July 17, 2008 |

Ah, excellent, it did. Although, heh, the formula I typed is incoherent…

Comment by Sridhar Ramesh | July 17, 2008 |

What I’m curious about is how wordpress figured out the connection. Seriously, I’m baffled as to what wordpress saw that would automatically generate a link there.

Comment by Charles | July 17, 2008 |

“Color” probably had something to do with it. And all the . And some of the other formulæ.

Comment by John Armstrong | July 17, 2008 |

The first problem you mention (generalised to ) is in fact a famous open problem in extremal combinatorics, see my blog post on it at

http://terrytao.wordpress.com/2007/02/23/open-question-best-bounds-for-cap-sets/

Comment by Terence Tao | July 17, 2008 |

Interesting. How do the expected values extend to higher-dimensional affine spaces?

Comment by John Armstrong | July 17, 2008 |

It has occurred to me that if we replace the “3″ in with some larger integer, the game of Set generalizes in different ways. In particular, the actual game is usually explained by saying that you have to find three cards which, along each trait, are either all identical or all different. But as you point out, the goal is also to find affine lines. If 3 is replaced by some larger integer, these are no longer the same thing. In fact, if 3 is replaced by a non-prime, one isn’t even a subset of the other. For example, over , (0,0), (1,2), (2,0), (3,2) form an affine line, but in the second coordinate these pairs are not all the same, nor are they all different.

Comment by Isabel Lugo | July 19, 2008 |

Dear John: I’m not sure the question has been explored much: for small dimensional affine spaces, the known bounds are much the same as in the one-dimensional space. Tom Sanders has recently obtained a slight refinement of the upper bound in the case of , in which progressions of length three are rather special, though his preprint doesn’t seem to be online yet.

Comment by Terence Tao | July 21, 2008 |

Isabel said:

“I happen to know the answer to the problem of finding the maximal set, but I have no idea why it’s true.”

Apparently a geometric proof lies in the following paper:

G. Pellegrino, Sul massimo ordine delle calotte in S4;3, Matematiche (Catania), Vol. 25 (1970) pp. 1–9.

I believe it’s in Italian, which is unfortunate as I can’t read Italian. I have searched in vain for an English version.

Comment by David Turner | July 23, 2008 |

I did a proof of the first problem (maximal subset of containing no affine lines) basically by doing a lot of combinatorics and clever build up for a second year talk “Educating in mathematics” (or whatever the translation of “Overdragen van de Wiskunde” is)

Sketch:

first look at all the possible (up to simple basis transformations) combinations of subsets of

Comment by Jan | July 24, 2008 |

I did a proof of the first problem (maximal subset of containing no affine lines) basically by doing a lot of combinatorics and clever build up for a second year talk “Educating in mathematics” (or whatever the translation of “Overdragen van de Wiskunde” is)

Sketch:

first look at all the possible (up to simple basis transformations) combinations of subsets of , these can easily be seen to be of size 4 or less. Then draw, in some clever way, all the possible combinations of these in such that these contain no affine lines (maximal of nine). Invent a symbol for each set of containing no affine line, and take good note of all possible combinations of these in (of course up to simple basis transformations).

Then for the next step, you suspect the answer (20), so you need to prove that there are no sets with this property of size 21. That means, you can try to build up as follows:

Top line, can start with sets in of size 7. Draw all possible combinations. Then the next line must also be of size 7, and so must the third be. Examine all possibilities and conclude impossibility.

Start with 8, repeat, start with 9, repeat (also by cleverly taking into account symmetries, look from left to right instead of top to bottom, etc.)

It ain’t the prettiest proof (I remember looking at positively hundreds of diagrams), but it works in the end.

Biggest problem is the non-scalability, and the need of an (strong suspect) for an answer beforehand.

Comment by Jan | July 24, 2008 |

[...] be clear, though, let’s look at this one counterexample. Think about the field we used when we talked about Set. The polynomial is not the zero polynomial, but is the zero function. Indeed , , and , which is [...]

Pingback by Roots of Polynomials II « The Unapologetic Mathematician | July 31, 2008 |