Prime Venn diagrams

Last time I gave a rigorous proof that if a number, N, was composite then the N-set Venn diagram could not be rotationally symmetric. Further, as we have seen previously, the 2-, 3- and 5-set diagrams (reproduced below) do have rotational symmetric forms.

Surely, the evidence suggests that all Venn diagrams with prime numbers of sets have rotational symmetric forms, right?

Well, of course, "suggestion" isn't good enough for mathematicians. We demand logical proof more rigorous than any other science. 

Surprisingly, this question has only been laid to rest relatively recently. In fact, up until 1992 some people thought that a rotational form of the 7-set diagram did not exist at all. The 7-set rotationally symmetric diagram was first created by Branko Grünbaum, whilst he was actually trying to disprove its existence!

A 7-set rotational Venn diagram.

There the problem stayed until 1999, when Peter Hamburger introduced a new idea of how to generate such diagrams [1]. Using his technique he pushed the bounds to 11 sets. Two examples of such diagrams can be found below.

Building on Hamburger's technique Jerrold Griggs, Carla Savage and Charles Killian demonstrated that it was possible to produce rotationally symmetric Venn diagrams whenever the number of sets is prime [2]. Unfortunately, the proof of this claim is quite complex and far beyond my capabilities to convey in a simple and intuitive way. However, for those seeking more details, the reference can be found below.

So, the question was finally laid to rest. Or was it? As I originally stated when we first started discussing rotationally symmetric diagrams, mathematicians love to abstract any property they can. Hence, once a problem has been solved a mathematician will try to solve the problem once again under heavier constraints.

Thus, mathematicians are now looking for Venn diagrams that are "simple". A Venn diagram is simple if at all points there are at most two sets crossing each other. In the diagrams above the constructions are so complicated that at some points three or more sets cross each other at the same point.

The question of existence and how to create a simple rotationally symmetric Venn diagram is still open. However, in 2012 Khalegh Mamakani and Frank Ruskey produced the first example of a simple symmetric 11-Venn diagram [11]. This has been reproduced below.

Zooming into the Venn diagram (below) we see the intricate details of all the curves passing through one another. Yet, by definition, we can be sure that there are only ever at most two sets crossing at each point.

As we have reached the edges of our current knowledge we come to the end of my posts regarding rotationally symmetric Venn diagrams. I hope you have enjoyed learning about these beautiful diagrams just as much as I have enjoyed creating them.

Next time, something completely different!

________________________________________________________________

________________________________________

[1] Doodles and Doilies, Non-Simple Symmetric Venn Diagrams. Peter Hamburger.
[2] Venn Diagrams and Symmetric Chain Decompositions in the Boolean Lattice. Jerrold Griggs, Charles E. Killian, Carla D. Savage.
[3] A New Rose: The First Simple Symmetric 11-Venn Diagram. Khalegh Mamakani and Frank Ruskey.

Primes, composites and rotationally symmetric Venn diagrams

Last time I boldly stated that if a Venn diagram is made up of $N$ sets, where $N$ is a composite number, i.e. not prime [1], then the Venn diagram can never be rotationally symmetric.

Before we prove the statement we first define the "rank" of the section in a Venn diagram.

The rank of a section is the number of sets, which the section is a part of.

For example, in the 2-set Venn diagram, the region outside of the circles has rank zero, because any point out there is in neither set. The sections on the extreme left and right of the circles each have rank 1, because they are a member of the either the right or left sets only. Finally, the overlapping region in the center has rank 2, because this section belongs to both sets.

Using this definition we can now head towards proving the initial statement. We do this by combining three smaller proofs concerning a general $N$-set Venn diagram. Explicitly, we

1. count how many sections there are of each rank;
2. show that in a rotationally symmetric Venn diagram these ranks must be divisible by $N$;
3. prove that the ranks are divisible by $N$ if and only if $N$ is prime.

Without further delay the three theorems and proofs can be found below.

Theorem 1
Suppose $k$ is an integer where $0\leq k\leq N$ then in an $N$-set Venn diagram there are
\begin{equation}
\frac{N!}{k!(N-k)!},
\end{equation}
sections of rank $k$ [2].

Proof 1
In order to help our intuition in counting the sections of a given rank we consider the 1-, 2-, 3-, 4-set Venn diagrams and summarise their details in the table below.

Number of sections of each rank		Rank
		0	1	2	3	4
Venn diagram size	0 sets	1
	1 set	1	1
	2 sets	1	2	1
	3 sets	1	3	3	1
	4 sets	1	4	6	4	1

The pattern of numbers within the table maybe familiar to you, as it is the famous Pascal's triangle. We may have expected these numbers to appear in this formation, because the numbers in Pascal's triangle represent exactly the quantity we are trying to calculate. Namely, the $(k+1)^{th}$ number in the $(N+1)^{th}$ row of Pascal's triangle tells us how many ways there are of choosing $k$ objects from $N$ objects. Note that we need to use the $(k+1)^{th}$ number and not the $k^{th}$ number, because the first number of each row deals with the trivial section, which is in none of the sets. Similarly, we use $(N+1)^{th}$ row and not the $N^{th}$ row because the first row deals the trivial Venn diagram of 0 sets.

To cement this idea, suppose we have three objects {A,B,C}. How many different ways are there of choosing two objects from these three (under the assumption that ordering doesn't matter)? Explicitly, there are three ways, {A,B}, {B,C} and {A,C}. This is exactly the answer we get from Pascal's triangle if we look at the third number on the fourth row. Because of this identification we normally call the numbers $N$ choose $k$, or, $_NC_k$, for short.

There are many ways to calculate the coefficients of Pascal's triangle. The quickest way is to use the formula [3]
\begin{equation}
_NC_k= \frac{N!}{k!(N-k)!}.
\end{equation}

Theorem 2
If an $N$-set Venn diagram is rotationally symmetric the number of section of a given rank $k$, where $0\leq k\leq N$, must be divisible by $N$.

Proof 2
By definition, an $N$-set Venn diagram is rotationally symmetric if it has $N$ orders of rotational symmetry. This means that if we find the rotational center of the diagram and split the diagram into equal sectors of $2\pi/N$ radians (or $360/N$ degrees) each sector should "look" identical. For example, have a look at the 3-set Venn diagram which has been split into thirds. Each third contains sections with exactly the same rank.

We deduce that the total sum of sections with rank $k$ (where $0\leq k\leq N$ [4]) must be divisible by $N$. Suppose it wasn't true, we would not be able to divide the sections of rank $k$ into $N$ identical parts and therefore our diagram could not have $N$ identical sectors, suggesting that the diagram wasn't rotationally symmetric. In order to avert this contradiction we conclude that $N$ divides the total number of sections with rank $k$ for all values of $k$, where $0\leq k\leq N$.

  

Theorem 3

\begin{equation}
_NC_k= \frac{N!}{k!(N-k)!},
\end{equation}
is divisible by $N$ for all values of $k$ such that $0\leq k\leq N$ if and only if $N$ is prime.

Proof 3

Firstly, suppose $N$ is prime. Consider $N$ choose $k$, which has a simplified form
\begin{equation}
_NC_k= \frac{N(N-1)(N-2)\dots(N-k+1)}{k(k-1)(k-1)\dots1},
\end{equation}
for all  $0\leq k\leq N$. Note $_NC_k$ is an integer and that the top of the fraction has a prime factor $N$, which does not cancel down because there is no factor of $N$ on the bottom. Thus, $_NC_k$ contains a factor of $N$, and so it is divisible by $N$.

Conversely, suppose $N$ is composite. Choose $p$ to be the smallest prime factor of $N$, and define $n=N/p$ then
\begin{equation}
_NC_p=\frac{N(N-1)(N-2)\dots(N-p+1)}{p!}=\frac{n(N-1)(N-2)\dots(N-p+1)}{(p-1)!}.
\end{equation}
Now if $_NC_p$ is divisible by $N$ the top of the fraction must contain a factor of $N$ and therefore a factor of $p$. Because $N=np$ and we already have a factor of $n$ on the top then $p$ must divide at least one of the factors of $N-1$, $N-2$, ..., or $N-p+1$. But $p$ divides $N$, so it does not divide any of these other factors. Once again the only way out of the contradiction is to conclude that when $N$ is composite $N$ does not divide $_NC_p$ and, hence, $_NC_k$ is divisible by $N$ for all values of $k$ such that  $0\leq k\leq N$ if and only if $N$ is prime.

Putting these three theorems together we generate the proof we were originally searching for.

Theorem 4
If $N$ is a composite number then the $N$-set Venn diagram is not rotationally symmetric.

Proof 4

• By proof 1 the total number of sections of a given rank is given by $_NC_k$.
• By proof 2 if a Venn diagram is rotationally symmetric the total number of sections of a given rank must be divisible by $N$ for all $0\leq k\leq N$ .
• We conclude that if a Venn diagram is rotationally symmetric $_NC_k$ must be divisible by $N$ for all  $0\leq k\leq N$.
• Finally, by  proof 3, $_NC_k$ is be divisible by $N$ for all  $0\leq k\leq N$ if and only if $N$ is prime.

Therefore, if $N$ is composite $N$ does not divide $_NC_k$ for all  $0\leq k\leq N$ and, hence, the Venn diagram cannot be rotationally symmetric.

We finish this week's post by noting that, although we have proven that an $N$-set Venn diagram is not rotationally symmetric when $N$ is composite, this does not mean that it is rotationally symmetric if $N$ is prime. We will discuss more about this point next time.

________________________________________________________________

________________________________________

[1] For those of you who may have forgotten the definition: a positive number is prime if and only if it was only two distinct integer factors, which are itself and 1. For example 2, 3, 5 and 7 are all prime numbers. However, 9 is not a prime number, because 3$\times$3=9 and the factors of 9 are 1, 3 and 9. Any number that is not prime (other than 1) is called composite. The number 1 is a special case as it is neither prime nor composite. It is called a unit.

[2] The exclamation mark symbol $n!$ represents the product of all positive integers up to and including  $n$, i.e. $n!=1\times2\times3\times...\times n$.

[3] Ok, I've slightly cheated and not proven that this formula does give us the numbers that we want. However, if you want to read more about the connection between the Pascal numbers and the formula see this post.

[4] Note that we have excluded $k=0$ and $k=N$, why is that?