I gave the Serge Lang lecture today at Berkeley about the card game Set and the related “affine cap problem” — how many cards is it possible to have on the table with no legal play? You can ask this question for the actual card game Set (in which case the answer is known) or for the d-dimensional generalization of Set, where there are 3^d cards. In this case, the question is: how big is the largest subset of (F_3)^d in which no three points are collinear? Our knowledge about the general case is embarrassingly weak.
Years ago I really thought I was going to make progress on this by devising very clever algebraic subvarieties of affine n-space which contained no three collinear F_3-rational points; but this didn’t work. (It works great for d=3 and 4, though! You can write the maximal cap set in (F_3)^4 as the set of nonzero solutions to x^2 + y^2 = zw.)
- Terry Tao explains why this is one of his favorite open problems.
- A really good survey article by Benjamin Davis and Diane MacLagan. “We would never have spend so many hours thinking about the “set-Problem” without Joe Buhler’s goading remark that it was shocking that two Berkeley students couldn’t work out the answer.”
- You can play set on P^5(F_2) instead of A^4(F_3) — and Anton Geraschenko made some cards.
- Heisenberg Set, from the MIT mystery hunt. (Thanks to Denis Auroux for the link.)
- Hungarian Set knockoff (also via Denis)
- The first progress on this problem in a long time is the recent paper of Bateman and Katz. Some discussion by Gowers of the relation between this paper and the polymath project.
Was the lecture recorded?
No, but the math in it is almost totally contained in the Davis – MacLagan survey and Terry’s blog post.
There’s an easier way to map P^5(F_2) set cards that’s used at Canada/USA Mathcamp: Each card either has a pip or doesn’t in each of 6 locations, a set means that for each of the 6 locations you have either 2 pips or 0. You can see an applet for that version here: http://www.stanford.edu/~yli333/proset/
[…] you know I love the affine cap problem: how big can a subset of (Z/3Z)^n be that contains no three elements summing to 0 — or, in […]