This weekend I got a very exciting text message from Katara:
I have a math question for you
Oh boy! I hope it's one I can answer.
Okay
there's this game called spot it where you have cards with 8 symbols
on them like so
and the goal is to find the one matching symbol on your card and the
one in the middle
how is it possible that given any pair of cards, there is exactly one
matching symbol
Well, whatever my failings as a dad, this is one problem I can solve.
I went a little of overboard in my reply:
You need a particular kind of structure called a projective plane.
They only exist for certain numbers of symbols
A simpler example has 7 cards with 3 symbols each.
One thing that's cool about it is that the symbols and the cards are
"dual": say you give each round card a name. Then make up a new deck
of square cards. There's one square card for each symbol. So there's a
square"Ladybug" card. The Ladybug card has on it the names of the
round cards that have the Ladybug. Now you can play Spot with the
square cards instead of the round ones: each two square cards have
exactly one name in common.
In a geometric plane any two points lie on exactly one common line and
any two lines intersect in exactly one common point. This is a sort of
finite model of that, with cards playing the role of lines and symbols
playing the role of points. Or vice versa, it doesn't matter.
More than you wanted to know 😂
ah thank you, I'm pretty sure I understand, sorry for not responding,
my phone was charging
I still couldn't shut up about the finite projective planes:
No problem! No response necessary.
It is known that all finite projective planes have n²+n+1 points for
some n. So I guess the Spot deck has either 31, 57, or 73 cards and
the same number of symbols. Is 57 correct?
Must be 57 because I see from your picture that each card has 8
symbols.
Katara was very patient:
I guess, I would like to talk about this some more when i get home if
that's okay
Anyway this evening I cut up some index cards, and found a bunch of
stickers in a drawer, and made Katara a projective plane of order 3.
This has 13 cards, each with 4 different stickers, and again, every
two cards share exactly one sticker. She was very pleased and wanted
to know how to make them herself.
Each set of cards has an order, which is a non-negative integer.
Then there must be !!n^2 + n + 1!! cards, each with !!n+1!! stickers
or symbols. When !!n!! is a prime power, you can use field theory to
construct a set of cards from the structure of the (unique) field of
order !!n!!.
Fields to projective planes
Order 2
I'll describe the procedure using the plane of order !!n=2!!, which is
unusually simple. There will be !!2^2+2+1 = 7!! cards, each with
!!3!! of the !!7!! symbols.
Here is the finite field of order 2, called !!GF(2)!!:
+
0
1
0
0
1
1
1
0
×
0
1
0
0
0
1
0
1
The stickers correspond to ordered triples of elements of !!GF(2)!!, except that !!\langle 0,0,0\rangle!! is always omitted. So they are:
Of course, you probably do not want to use these symbols exactly.
You might decide that !!\langle 1,0,0\rangle!! is a sticker with a
picture of a fish, and !!\langle 0,1,0\rangle!! is a sticker with a
ladybug.
Each card will have !!n+1 = 3!! stickers. To generate a card, pick
any two stickers that haven't appeared together before and put them
on the card. Say these stickers correspond to the triples !!\langle
a,b,c\rangle!! and !!\langle x,y,z\rangle!!. To find the triple for
the third sticker on the card, just add the first two triples
componentwise, obtaining !!\langle a+x,b+y,c+z\rangle!!. Remember
that the addition must be done according to the !!GF(2)!! addition table
above! So for example if a card has !!\langle 1,0,1\rangle!! and
!!\langle 0,1,1\rangle!!, its
third triple will be
Observe that it doesn't matter which two triples you add; you always get the third one!
Okay, well, that was simple.
Larger order
After Katara did the order 2 case, which has 7 cards, each with 3 of
the 7 kinds of stickers, she was ready to move on to something
bigger. I had already done the order 3 deck so she decided to do
order 4. This has !!4^2+4+1 = 21!! cards each with 5 of the 21 kinds
of stickers. The arithmetic is more complicated too; it's !!GF(2^2)!! instead
of !!GF(2)!!:
+
0
1
2
3
0
0
1
2
3
1
1
0
3
2
2
2
3
0
1
3
3
2
1
0
×
0
1
2
3
0
0
0
0
0
1
0
1
2
3
2
0
2
3
1
3
0
3
1
2
When the order !!n!! is larger than 2, there is another wrinkle.
There are !!4^3 = 64!! possible triples, and we are throwing away
!!\langle 0,0,0\rangle!! as usual, so we have 63. But we need
!!4^2+4+1 = 21!!, not !!63!!.
Each sticker is represented not by one triple, but by three. The
triples !!\langle a,b,c\rangle, \langle 2a,2b,2c\rangle,!! and
!!\langle 3a,3b,3c\rangle!! must be understood to represent the same
sticker, all the multiplications being done according to the table
above. Then each group of three triples corresponds to a sticker, and
we have 21 as we wanted.
Each triple must have a leftmost non-zero entry, and in each group of
three similar triples, there will be one where this leftmost non-zero
entry is a !!1!!; we will take this as the canonical representative of
its class, and it can wear a costume or a disguise that makes it
appear to begin with a !!2!! or a !!3!!.
We can stop there, because everything after
!!\langle 1,3,3 \rangle!!
begins with a !!2!! or a !!3!!, and so is some other triple in
disguise. For example
what sticker goes with
!!\langle 0,2,3 \rangle!!? That's actually
!!\langle 0,1,2 \rangle!! in disguise, it's
!!2·\langle 0,1,2 \rangle!!, which is “dice”. Okay, how about !!\langle 3,3,1
\rangle!!? That's the same as !!3\cdot\langle 1,1,2 \rangle!!,
which is “ladybug”.
There are !!21!!, as we wanted. Note that the !!21!! naturally
breaks down as !!1+4+4^2!!, depending on how many zeroes are at the
beginning;
that's where that comes from.
Now, just like before, to make a card, we pick two triples that have
not yet gone together, say !!\langle 0,0,1 \rangle!! and !!\langle
0,1,0 \rangle!!. We start adding these together as before, obtaining
!!\langle 0,1,1 \rangle!!. But we must also add together the
disguised versions of these triples, !!\langle 0,0,2 \rangle!! and
!!\langle 0,0,3 \rangle!! for the first, and !!\langle 0,2,0 \rangle!!
and !! \langle 0,3,0 \rangle!! for the second. This gets us two
additional sums, !!\langle 0,2,3 \rangle!!, which is !!\langle 0,1,2
\rangle!! in disguise, and !!\langle 0,3,2 \rangle!!, which is
!!\langle 0,1,3 \rangle!! in disguise.
It might seem like it also gets us !!\langle 0,2,2 \rangle!! and
!!\langle 0,3,3 \rangle!!, but these are just !!\langle 0,1,1
\rangle!! again, in disguise. Since there are three disguises for
!!\langle 0,0,1 \rangle!! and three for !!\langle 0,1,0 \rangle!!, we
have nine possible sums, but it turns out that the nine sums are only
three different triples, each in three different disguises. So our
nine sums get us three additional triples, and, including the two we
started with, that makes five, which is exactly how many we need for
the first card. The first card gets the stickers for triples
!!\langle 0,0,1 \rangle,
\langle 0,1,0 \rangle
\langle 0,1,1 \rangle
\langle 0,1,2 \rangle,!! and
!!\langle 0,1,3 \rangle,!! which are apple, bicycle,
carrot, dice, and elephant.
That was anticlimactic. Let's do one more. We don't have a card yet
with ladybug and trombone. These are !!\langle 1,1,2 \rangle!! and
!!\langle 1,3,2 \rangle!!, and we must add them together, and also the
disguised versions:
These nine results do indeed pick out three triples in three disguises
each, and it's easy to select the three of these that are canonical:
they have a 1 in the leftmost nonzero position, so the three sums are
!!\langle 0,1,0 \rangle,!! !!\langle 1,0,2 \rangle,!! and !!\langle
1,2,2 \rangle!!, which are bicycle, hat, and piano. So the one card
that has a ladybug and a trombone also has a bicycle, a hat, and a
piano, which should not seem obvious. Note that this card does have
the required single overlap with the other card we constructed: both
have bicycles.
Well, that was fun. Katara did hers with colored dots instead of
stickers:
The ABCDE card is in the upper left; the
bicycle-hat-ladybug-piano-trombone one is the second row from the
bottom, second column from the left. The colors look bad in this
picture; the light is too yellow and so all the blues and purples look
black.
After I took this picture, we checked these cards and found a couple
of calculation errors, which we corrected. A correct set of cards is:
This construction always turns a finite field of order !!n!! into a
finite projective plane of order !!n!!.
A finite field of order !!n!! exists exactly when !!n!! is a prime
power and then there is exactly one finite
field. So this construction gives us finite projective planes of
orders !!1,2,3,4,5,7,8,9,11,13,16!!, but not of orders
!!6,10,12,14,15!!. Do finite projective planes of those latter
orders exist?
Is this method the only way to construct a finite projective plane? Yes,
when !!n<9!!. But there are four non-isomorphic projective planes of
order !!9!!, and this only constructs one of them.
