Venn diagrams that turn into themselves

John Venn’s diagrams of 1880 drew each class in a logical argument as a closed curve, arranged so that every possible combination of belonging and not belonging appears as a region. Three circles do it for three classes. Four circles cannot do it for four, because two circles cross at most twice, and with too few crossings there are too few regions; ellipses, which cross up to four times, can, and Venn himself drew four ellipses. Carroll’s sorites and the syllogisms before it were decided on such diagrams by shading the regions that the premises empty.

The three-circle picture has a quality the four-ellipse one lacks: it looks the same after a turn of 120°, with each circle carried onto the next. This essay asks for which numbers of curves such a symmetric diagram can exist. The answer is a short counting argument that rules out every number that is not prime, a picture that shows five, and a theorem, proved only in 2004, that every prime works.

What a Venn diagram must do #

A Venn diagram of $n$ curves in the plane is a picture in which, for every subset of the curves, the set of points inside exactly those curves and outside all the others is a single connected region — non-empty, and in one piece. With $n$ curves there are $2^n$ subsets, including the empty one, the region outside everything. So a Venn diagram of five curves has exactly 32 regions, one for each combination.

A diagram is rotationally symmetric if turning the plane through $360°/n$ about some centre carries each curve onto the next, so that after $n$ turns every curve is back where it started. The three circles of the familiar picture, centred at the corners of an equilateral triangle, are symmetric in this sense. So are the five ellipses of the hero: each is the previous one turned through 72°, and turning the whole picture through 72° gives the same picture with the labels shifted round.

Why a logician wants every region #

Venn’s purpose was logical, and it explains the strictness of the definition. A diagram of classes is used by shading the regions an argument declares empty and marking the ones it declares occupied; the 256 syllogistic forms were decided this way, one diagram each, and syllogisms with “most” by weighing the sizes of regions. If some combination of classes had no region, the diagram could not record a statement about it, and if some combination had two regions, a reader could shade one and miss the other. Every combination exactly once is what makes the diagram a faithful picture of the $2^n$ possibilities.

The same $2^n$ regions are the subject of monadic logic, where a sentence about $n$ properties is true or false according to which regions are occupied, and of the random walk on four ellipses that solved small satisfiability problems by moving between regions. For those uses any Venn diagram serves. Symmetry is an extra demand, and it is an aesthetic one at first: a symmetric diagram treats every class alike, so no class is drawn as the special one in the middle and no class as the awkward one round the edge.

Why only primes #

Turning the symmetric diagram through $360°/n$ moves every region to another region. The region outside everything stays outside everything, and the region inside everything stays inside everything. Every other region is carried to a region inside the same number of curves — the curves are relabelled cyclically, but how many of them contain a point does not change.

Now count. There are $\binom{n}{k}$ regions inside exactly $k$ curves, and the rotation permutes them. Could a region be carried to itself by a partial turn? If it were, then joining a point of the region to its image by a path inside the region, and turning that path round, would give a closed loop inside the region winding round the centre of symmetry. Such a loop separates the centre from the far outside. Every curve is a turned copy of every other, so either all the curves cross this loop or none does; they cannot cross it, since the loop lies inside a single region; so all of them lie on the same side of it. If they all lie inside the loop, the region is outside all of them and is the outside region; if they all lie outside it, the region is inside all of them, the innermost region. So every other region has an orbit of exactly $n$ regions, and for $0 < k < n$ the count must satisfy

$$n \text{ divides } \binom{n}{k}.$$

That condition holds exactly when $n$ is prime. If $n$ is prime, $\binom{n}{k} = n!/(k!(n-k)!)$ and none of the factors in the denominator can cancel the prime $n$ in the numerator. If $n$ is composite with a prime factor $p$, then $\binom{n}{p}$ is not divisible by $n$; for $n = 4$, $\binom{4}{2} = 6$ leaves remainder 2. The table shows the pattern for $n$ up to 13: every row with a red cell is composite, and every all-green row is prime. David Henderson made this observation in 1963. It is the same divisibility that underlies Fermat’s little theorem, where the necklaces of $p$ beads that are not single colours fall into orbits of exactly $p$ under rotation.

Counting orbits under a cyclic rotation is the tool that colourings nobody can tell apart used for necklaces and coloured squares, and the symmetric diagram is a necklace in disguise. Label each region by the subset of curves containing it, write the subset as a string of $n$ bits in the cyclic order of the curves, and the rotation of the diagram becomes the cyclic shift of the string. The orbits of regions are the necklaces of $n$ beads in two colours, and the condition that every orbit except two has full size $n$ is the condition that every necklace except the two single-coloured ones has no rotational symmetry — true exactly for prime $n$. For $n = 4$ the necklace 1010 is carried to itself by a half-turn, and that is the diagonal pair A and C seen in the figure below.

Five ellipses #

The argument says five is possible in principle. Branko Grünbaum showed in 1975 that five congruent ellipses suffice. The ellipses in the hero were found here by searching over the distance of each ellipse’s centre from the centre of symmetry, its two semi-axes and its tilt, and testing every candidate. The one drawn has its centre 0.7 from the middle, semi-axes 1.4 and 0.5, and a tilt of 7.5° against the line to the middle.

Testing a candidate by eye is unreliable. A region can be too small to see, or two regions with the same combination can sit at opposite ends of the picture. The certificate uses two facts. First, a raster of 360 by 360 points finds every combination that occurs anywhere, and all 32 do. Second, the crossings are counted exactly: along each ellipse, the points where it crosses each other ellipse are found as sign changes of the other ellipse’s equation.

Neighbouring ellipses cross four times and ellipses one apart cross twice: $5 \times 4 + 5 \times 2 = 30$. Now treat the diagram as a map on the sphere. Its vertices are the 30 crossings; at each, two curves cross, so four edges meet there, and there are $4 \times 30 / 2 = 60$ edges. Euler’s formula, $V - E + F = 2$, gives $F = 32$ faces. There are exactly 32 regions, and all 32 combinations occur, so each occurs in exactly one region: none is missing and none is split. The raster can see only what its resolution allows; the count of crossings closes the gap. The same use of Euler’s formula is what proved that four circles cannot do it.

The regions in their orbits #

The counting argument can be watched. The 32 regions fall into 8 orbits under rotation: the region outside everything, the region inside everything, and six orbits of five. Regions inside one ellipse form one orbit; inside two, there are ten regions in two orbits, according as the two ellipses are neighbours in the cycle or one apart; inside three, again ten in two orbits; inside four, one orbit of five. The sizes $1, 5, 10, 10, 5, 1$ are the binomial coefficients of 5, and every inner one is a multiple of five.

The innermost region, inside all five, is the small star at the centre, and it contains the centre of symmetry. It is the only region the rotation fixes apart from the outside, as the argument above requires, and every other region has nowhere to go but round.

Four copies cannot work #

Taking four copies of the same ellipse a quarter-turn apart gives a symmetric picture, and it fails in the way the counting predicts. All sixteen combinations occur, but the six combinations with two curves inside each appear as two separate pieces. The two diagonal pairs show why it cannot be repaired by any choice of shape. A quarter-turn sends the pair A and C to the pair B and D, and a half-turn sends each to itself. So the region inside A and C alone would be carried to itself by a half-turn, and by the argument above only the outside region and the innermost region can be. So a symmetric picture must place two copies of that region, carried into each other by the quarter-turn’s square, and a Venn diagram allows only one.

Circles stop at three #

For three curves the familiar circles suffice, and the count of crossings confirms it: three pairs crossing twice each make 6 crossings and, by Euler, 8 faces. For four, circles give at most 12 crossings and 14 faces, so two combinations must be missing, and in the symmetric arrangement they are the two diagonal pairs. Ellipses cross up to four times each, which allows $4\binom{n}{2}$ crossings and, by the same formula, up to $4\binom{n}{2} + 2$ regions: 42 for five ellipses, more than the 32 needed. For six ellipses it allows 62 regions against the 64 needed, so six ellipses can never make a Venn diagram, symmetric or not. That is no obstacle to the prime 7, but it means seven curves must be non-convex.

Seven and beyond #

A symmetric Venn diagram of seven curves was first drawn by Grünbaum in 1992, with curves that are not convex: each is a wiggly closed curve, and the diagram looks like a rose window. Several symmetric seven-curve diagrams are known; later computer searches by Frank Ruskey and his students counted the simple ones — those in which no three curves meet at a point — finding 23 up to symmetry, and the most famous has been named Victoria, after the city where the search was done. Symmetric diagrams of eleven curves were found by Peter Hamburger and colleagues in 2002, and in 2004 Jerrold Griggs, Charles Killian and Carla Savage proved that every prime number has a symmetric Venn diagram, settling the question that Henderson’s counting argument had opened forty years earlier. Their construction builds the diagram from a combinatorial object, a symmetric chain decomposition of the subsets of an $n$-element set, arranged so that its chains become the boundaries between regions.

Without the demand for symmetry, Venn diagrams exist for every number of curves, and there are simple constructions. Venn himself gave one, adding curves that snake back and forth across all the existing regions. Anthony Edwards gave a more elegant one in 1989, drawing the first three sets as two perpendicular lines and a circle on a sphere and every further set as a “cogwheel” round the circle, with twice as many teeth as the one before, so that each new curve dips in and out of every existing region once. None of these constructions has the cyclic symmetry that carries each curve to the next, and that symmetry is what makes the arithmetic of primes appear.

A drawing question answered by divisibility #

The surprise is that a question about pictures — can these curves be drawn so the drawing has rotational symmetry? — has an answer in elementary number theory, and that the obstruction is the same divisibility that proves Fermat’s little theorem. Nothing about curves, convexity or crossings enters the argument that composite numbers fail; only the orbits of a cyclic group acting on subsets. And conversely, the existence proof for all primes uses no geometry at all until the last step, where a combinatorial chain of subsets is drawn as curves. The geometry is, in both directions, a translation of counting.

The same is true of the two-dimensional counting that certifies the five ellipses. A picture cannot prove that a region is not split, but Euler’s formula, applied to a count of crossings, can. Thirty crossings and thirty-two combinations leave no room for anything to go wrong.

Regions found by raster, certified by Euler #

The raster finds which combinations occur but cannot by itself show that each is connected; that is what the crossing count and Euler’s formula supply, and they require that no three curves pass through one point, which holds here generically but was not separately checked. The crossings are found as sign changes at 4,000 points round each ellipse, and two crossings closer together than one step would be missed; the counts of 4 and 2 are consistent with the geometry of ellipses, which cross at most four times.

The four-ellipse figure shows one failed symmetric arrangement; the impossibility of every symmetric arrangement of four curves is the counting argument, not the picture. And the diagrams for seven and more curves are described, not drawn.

Ellipses searched, the prime theorem quoted #

Computed here: the five ellipses by search over centre distance, semi-axes and tilt; for the chosen five, the 32 combinations on a raster of 360 by 360 points and the 30 crossings, certifying a Venn diagram by Euler’s formula; the binomial coefficients modulo $n$ for $n$ from 2 to 16, zero throughout exactly at the primes; the 8 orbits of regions; the four-ellipse failure, with all six two-set combinations in two pieces; and the circle diagrams, with faces equal to crossings plus two.

Quoted: Venn’s diagrams of 1880; Henderson’s divisibility condition of 1963; Grünbaum’s five ellipses of 1975 and seven-curve diagram of 1992; the census of simple symmetric seven-Venn diagrams; Hamburger’s eleven-curve diagrams; and the theorem of Griggs, Killian and Savage of 2004.

Still open: simple symmetric diagrams #

A Venn diagram is simple if no three curves meet at a point, as in the five ellipses here. Griggs, Killian and Savage’s diagrams for every prime are not simple in general: many curves pass through the same points. Does every prime have a simple symmetric Venn diagram? Simple symmetric diagrams are known for 2, 3, 5, 7, 11 and 13 curves, the last found only in 2012 by Khalegh Mamakani and Frank Ruskey, and for no larger prime. Whether they exist for 17, 19 and beyond is open, and the methods that found the known ones depend on computer searches that grow very fast with the number of curves. A related question asks which symmetric diagrams can be drawn with convex curves, as the five ellipses are, and for seven curves and beyond that is not settled either.

A turn of one fifth #

A Venn diagram that a turn of $1/n$ carries onto itself needs $n$ to divide every binomial coefficient $\binom{n}{k}$ with $0 < k < n$, which happens exactly when $n$ is prime. Five congruent ellipses, found by search, achieve it: all 32 combinations occur and the curves cross 30 times, which Euler’s formula turns into a proof that each combination is one region. Four copies split six regions in two, circles stop at three, and every prime has a symmetric diagram — though whether every prime has a simple one is still unknown.