You may have played the game “Set”:
Invented in 1974, Set has a simple goal: to find special triples called “sets” within a deck of 81 cards. Each card displays a different design with four attributes—color (which can be red, purple or green), shape (oval, diamond or squiggle), shading (solid, striped or outlined) and number (one, two or three copies of the shape). In typical play, 12 cards are placed face-up and the players search for a set: three cards whose designs, for each attribute, are either all the same or all different.
Occasionally, there’s no set to be found among the 12 cards, so the players add three more cards. Even less frequently, there’s still no set to be found among the 15 cards. How big, one might wonder, is the largest collection of cards that contains no set?
This “largest collection of with no set” is known mathematically as a “cap set.”
I’m not enough of a mathematician to understand the actual proofs here, but three things occur to me as I read the Wired article:
- Simplification almost always comes from clever transformations. Transforming the idea of a “cap set” to an n-dimensional spaces allows reasoning about sets as points in a line; transforming from Fourier analysis to Polynomial method allowed the actual proof to be discovered.
- It’s impossible to guess the implications of mathematical proofs. The method used for this one, for example, allowed other mathematicians to establish “that the proof rules out one of the approaches mathematicians were using to try to create more efficient matrix multiplication algorithms.” Because, obviously.
- Thinking about math (or physics) is good for the brain. These people think hard, and deep, and make almost inconceivable conceptual leaps. The mental gymnastics of trying to follow that along from set theory to hyperdimensional spaces is somewhat inspiring, and my instinct is that it clears the way for other, probably unrelated, personal insights.
I love it when simple things – a card game that’s been around since the seventies! – lead to deep insights. It may not seem important to know how big the largest set of dissimilar cards is, but thinking about it led to insights in matrix algebra, which is at the heart of many machine learning algorithms. Fundamental changes in what we understand matters, even if the topic is innocuous and arcane.
Source: A Simple Proof from the Pattern-matching Card Game “SET” Stuns Mathematicians.
