A deck where any two cards match once
Worth reading first: Seven points, seven lines · More blocks than points.
There is a card game, sold under several names, in which every card shows eight small pictures and the players race to spot the one picture that two cards have in common. There is always exactly one. Whichever two cards are turned over, from a deck of fifty-five, they share one picture and no more. Designing such a deck by trial and error is hopeless, as this essay will measure; designing it by geometry takes a line.
Seven points and seven lines drew the Fano plane, seven points and seven lines in which any two lines meet in exactly one point and any two points lie on exactly one line. Read each line as a card and each point as a picture, and the Fano plane is a deck of seven cards with three pictures each, any two cards sharing exactly one picture. The game’s deck is the same thing one size up the scale of finite planes — the projective plane of order 7, with 57 lines of 8 points. The game prints 55 of them. This essay deals the plane as cards, recovers the two missing cards from the deck that was sold, and then asks the question the geometry answers and trial and error cannot: how large can such a deck be, and what goes wrong when one tries to build it without the plane?
Thirteen cards of four symbols
The plane of order 3 is built from arithmetic modulo 3, by the recipe a plane in a list of numbers gave. Its points are the triples of numbers mod 3, not all zero, with a triple and its multiples counted as one point; there are of them. Its lines are the same triples read as equations: the line contains the points with . Each line has four points, each point is on four lines, and two distinct lines — two independent equations in three unknowns — have exactly one common solution up to multiples.
Dealt as cards, that is thirteen cards of four symbols each, drawn from thirteen symbols, any two cards sharing exactly one. The figure labels the symbols A to M and checks every pair of cards: all 78 pairs share exactly one symbol. The dual statement is checked too: every pair of symbols appears together on exactly one card, so the 78 pairs of symbols are each used once. Symbols and cards are interchangeable — the plane is self-dual — and the game could be played with the roles swapped.
The same recipe with arithmetic modulo a prime gives cards of symbols. Modulo 2 it is the Fano plane’s seven cards of three; modulo 7 it is fifty-seven cards of eight. Planes also exist for every prime power, using the field with four elements and its relatives, which gives decks of 21 cards with 5 symbols and 73 with 9.
Fifty-seven cards as a table
The plane of order 7 is too big to deal out on a page, so the figure draws it as an incidence table: 57 rows, one per card, and 57 columns, one per symbol, with a square wherever a card carries a symbol. Every row has 8 squares and so does every column, and any two rows have exactly one column in which both have a square. The construction verifies the property for all 1,596 pairs of rows before drawing anything.
The table is also a code. Read each row as a word of 57 zeros and ones; any two words agree in exactly one of their eight ones, so they differ in exactly fourteen places. A set of words all at the same distance from one another is an equidistant code, and the plane’s 57 lines form one with words of weight eight. That is the connection distance is a picture would make: the matching rule is a statement about Hamming distance, and the deck is a code whose every pair of words is equally far apart.
The two shaded rows are the two cards the commercial deck leaves out. Why it prints 55 rather than 57 is not something the mathematics decides — production and packaging have been suggested — but the omission is visible in the deck, as the next figure shows.
Two missing cards, from the counts alone
In the full plane every symbol appears on exactly eight cards. Remove two cards and count again. The two removed cards share one symbol, which loses two appearances and is now on six cards. Each of the other fourteen symbols on the removed cards loses one and is on seven. The remaining forty-two symbols are untouched, still on eight. The figure counts the 55-card deck and finds exactly that pattern: one symbol on six cards, fourteen on seven, forty-two on eight.
The six-count symbol is on both missing cards. Which of the fourteen go with which card? Two symbols lie on exactly one common card in the full plane. For two of the fourteen that were on the same missing card, that common card is missing, so they never appear together on a dealt card; for two on different missing cards, their common card is still in the deck. So the fourteen split into two groups of seven by the single test “do these two ever appear together?”, and each group, with the six-count symbol, is a missing card. The computation runs the test and recovers both cards exactly — the same two the table shaded.
The argument works for any number of missing cards as long as there are few enough, and it is a small instance of the redundancy that makes the plane a good code. Every card is determined by the others; a deck with a card lost, damaged or never printed carries enough information to rebuild it, which is the same property that lets finding the error without reading the message correct a word from its neighbours.
Building a deck without the plane
Suppose someone designing the game did not know about projective planes and built the deck one card at a time: deal a card of eight symbols from fifty-seven, then find a second card sharing exactly one symbol with it, then a third sharing exactly one with each of the first two, and so on. The search for each new card can be made complete. Take the dealt card with the fewest symbols still available to share; the new card must contain exactly one of them, so branch over which; the chosen symbol rules out every other symbol on the cards it now matches; repeat until every dealt card is matched, then fill the rest of the card with symbols no card uses yet. If the search fails, no card can be added at all, and the deck is stuck.
The figure builds forty decks this way, with the ties in the search broken at random, and every one gets stuck — at 22, 23, 24 or 25 cards. Not one comes within thirty of the plane’s 57. Each deck is maximal: no eight-symbol card can be added to it that shares exactly one symbol with every card already there. Yet each is less than half the size the plane shows is possible.
That is the gap between a local procedure and a global structure. Every card the greedy builder adds is a legitimate move, but early choices fix which later cards can exist, and a deck assembled without a plan fills up its room badly — using symbols in combinations that block far more future cards than they need to. The plane is not one of the decks this procedure finds; it has to be constructed whole, from the algebra, and the algebra is what makes all 57 cards fit.
The deck that never stops, and the bound for every other
How large can a matching deck be? There is an embarrassing answer: as large as one likes. Put the same symbol X on every card and fill each card’s other places with symbols used nowhere else. Any two cards share X and nothing more, and the deck can grow for as long as there are new symbols. This is the flower, drawn in the figure’s top row, and it makes a boring game — the answer is always X — but it satisfies the rule.
Exclude it, and the plane is the largest possible. Suppose a deck of cards with symbols each, any two sharing exactly one, has no symbol common to every card. Fix a card , and a symbol on it. Since is not on every card, there is a card without , and meets in a single symbol . Every card other than that carries meets in one symbol; it cannot be , or that card would share both and with ; and two such cards cannot meet in the same symbol, or they would share it as well as . So the cards through , apart from , number at most . Every card other than meets in one of its symbols, so the deck has at most cards. For that is 13, achieved by the plane of order 3 in the second row; for it is 57.
The count is the same double counting more blocks than points used for Fisher’s inequality, run from a single card’s point of view. And it shows that a deck meeting the bound is a projective plane: equality forces every symbol to be on exactly cards and every pair of symbols on exactly one card, which are the axioms. A maximum matching deck and a projective plane are the same object.
Decks that are the same deck, and decks that are not
Two decks are essentially the same if one becomes the other by renaming the pictures and reordering the cards. For the small orders there is no choice at all: every matching deck of the maximum size with three, four, five, six, eight or nine pictures a card is the plane built from arithmetic, under some renaming. In particular, every 57-card deck of eight-picture cards in which any two match once is the same deck, whatever pictures are printed on it and however they were arranged by its designers.
Order 9 is the first where that fails. There are exactly four different projective planes of order 9, and a plane no field built constructed one of the three that do not come from a field. So there are four genuinely different decks of 91 cards with ten pictures each, any two cards matching once in all four, and no renaming turns one into another. A player could not tell them apart by playing — every pair of cards still shares exactly one picture — but a careful count of which triples of pictures lie in particular configurations would. The difference is in the large-scale structure, in whether Desargues’s theorem about triangles in perspective holds, and the matching rule is far too local to see it.
The plane’s other properties become questions about the game as well. Every card meets every other, so any one card’s pictures form a set that every card shows at least one of. Is there a smaller set of pictures with that property that does not contain a whole card? The fewest points that meet every line answered it: such a blocking set needs at least points in a plane of order , and for the order-7 deck the smallest is larger than the eight pictures of a single card. And a schedule where every pair meets once is the same structure read the other way round — pictures as people and cards as meetings — so the 57-card deck is also a timetable for 57 people in which every pair of them meets in exactly one group of eight.
The decks that cannot be printed
A deck of cards with symbols meeting the bound exists exactly when a projective plane of order does. Planes are known for every prime power order, and for no other: the orders a plane cannot have showed that order 6 is impossible — by the Bruck–Ryser theorem, which rules out orders like 6, 14 and 21 by a condition on sums of two squares — and order 10 was ruled out in 1989 by a computer search that took years. So there is no perfect deck of 43 cards with 7 pictures each, nor of 111 cards with 11. A game designer wanting seven pictures a card has to settle for fewer cards, and the greedy figure above suggests how much fewer if the deck is not built from some larger plane by deletion.
Order 12 is the smallest order for which nobody knows. A deck of 157 cards with 13 pictures each, any two sharing exactly one, may or may not exist; the Bruck–Ryser condition does not exclude it, and the search that settled order 10 is far too small for it.
What the figures cannot show
The constructions and counts are exact: every pair of cards in the planes of orders 3 and 7 is checked, the symbol counts and the recovery of the missing cards are computed from the 55-card deck, and each greedy deck is certified stuck by a search that examines every possible next card. What the greedy figure cannot say is how large a maximal deck can be when it is not a plane. The forty decks found are what one randomised procedure produces, not the largest non-plane decks; the true range of sizes of maximal decks between the flower’s unlimited growth and the plane’s 57 is not explored by forty runs, and a cleverer builder might do much better.
Nor does the essay identify the commercial deck. The figure removes two particular lines from one construction of the plane of order 7 to illustrate recovery; the published game is said to have 55 cards and 57 symbols, but its specific cards and which two lines it omits depend on how its designers labelled the plane, and nothing here reproduces their labelling.
Still open: the plane of order twelve
The bound is achieved exactly when a projective plane of order exists, and whether one exists for every order that is not a prime power is the oldest open question of finite geometry. Every known plane has prime power order; orders 6 and 10 are known not to occur; order 12 is the first unknown case. The prime power conjecture says no other orders occur, and nothing close to a proof is known. For the card game that means the first undecided deck has thirteen pictures a card — and that no amount of clever printing can produce a 157-card deck with that property unless a plane of order 12 is found, which most researchers do not expect.
One picture in common
A deck in which any two cards share exactly one picture is a set of lines in which any two meet once: the projective plane of order gives cards of pictures, 13 for order 3 and 57 for order 7. A 55-card deck leaves two out, and they can be rebuilt from how often each picture appears and which pictures never meet. Built one card at a time without the plane, a deck gets stuck at 22 to 25 cards, every one certified maximal by exhaustive search. Unless every card shares one picture — the flower, which can grow for ever — no deck of -picture cards exceeds , and a deck that reaches the bound is a plane. Seven pictures a card can never reach it, and thirteen nobody knows.
Shares its objects with
Essays that name at least two of the same things, and that neither author linked.
- The densest graph without a square — both name counting two ways, exhaustive search, finite field, projective plane
- Every power of x that draws a hyperoval — both name exhaustive search, finite field, projective plane
- The curve that no three points in line define — both name exhaustive search, finite field, projective plane
- The plane hiding in the squares — both name exhaustive search, finite field, projective plane
- Three ordinary lines from a count — both name counting two ways, exhaustive search, projective plane
- Two shares know nothing — both name counting two ways, exhaustive search, finite field
Named objects
A dashed tag is an object no other essay names yet.
Block designCounting two waysExhaustive searchFinite fieldIncidence matrixProjective plane