Today we’ll take a little break from the more intense abstract math stuff I’ve been doing, and do a quick dive into a fun probabilistic puzzle I found on the internet.

Background for the puzzle: In Ancient Israel, there was a court of 23 wise men that tried important cases, known as the Sanhedrin. If you were being tried for a crime by the Sanhedrin and a majority of them found you guilty, you were convicted. But there was an interesting twist on this! According to the Talmud (Tractate Sanhedrin: Folio 17a), if the Sanhedrin unanimously found you guilty, you were to be acquitted.

If the Sanhedrin unanimously find [the accused] guilty, he is acquitted. Why? — Because we have learned by tradition that sentence must be postponed till the morrow in hope of finding new points in favour of the defence. But this cannot be anticipated in this case.

Putting aside the dubious logic of this rule, it gives rise to an interesting probability puzzle with a counterintuitive answer. Imagine that an accused murderer has been brought before the Sanhedrin, and that the evidence is strong enough that no judge has any doubt in their mind about his guilt. Each judge obviously wants for the murderer to be convicted, and would ordinarily vote to convict. But under this Talmudic rule, they need to be worried about the prospect of them all voting guilty and therefore letting him off scot-free!

So: If a probability p can be chosen such that each and every judge votes to convict with probability p, and to acquit with probability 1 – p, which p will give them the highest probability of ultimately convicting the guilty man?

Furthermore, imagine that the number of judges is not 23, but some arbitrarily high number. As the number of judges goes to infinity, what does p converge to?

I want you to think about this for a minute and test your intuitions before moving on.

 

(…)

 

 

(…)

 

 

(…)

 

So, it turns out that the optimal p for 23 judges is actually ≈ 75.3%. And as the number of judges goes to infinity? The optimal value of p converges to…

80%!

This was a big shock to me. I think the natural first thought is that when you have thousands and thousands of judges, you only need a minuscule chance for any one judge to vote ‘acquit’ in order to ensure a majority and prevent him from getting off free. So I initially guessed that p would be something like 99%, and would converge to 100% in the limit of infinite judges.

But this is wrong! And of the small sample of mathematically gifted friends I asked this question to, they mostly guessed the same as me.

There’s clearly a balance going on between the risk of a minority voting to convict and the risk of a unanimous vote to convict. For small p, the first of these is ~1 and the second is ~0, and for p ~ 1, the first is ~0 and the second ~1.  It seems that we are naturally underemphasizing the danger of a minority vote to convict, and overemphasizing the danger of the unanimous vote.

Here are some plots of the various relevant values, for different numbers of judges:

One thing to notice is that as the number of judges gets larger, the graph’s peak becomes more and more of a plateau. And in the limit of infinite judges, you can show that the graph is actually just a simple step function: Pr(conviction) = 0 if p < .5, and 1 if p > .5. This means that while yes, technically, 80% is the optimal value, you can do pretty much equally well by choosing any value of p greater than 50%.

My challenge to you is to come up with some justification for the value 80%. Good luck!

Curiosity Number One

The additive group of polynomials with integer coefficients is isomorphic to the multiplicative group of positive rational numbers: (ℤ[x], +) ≅ (ℚ₊, ⋅).

Any element of ℤ[x] can be written like a₀ + a₁x + a₂x² + … + a_nxⁿ, where all coefficients a₀, a₁, …, a_n are integers. Consider the following mapping: φ: (a₀ + a₁x + a₂x² + … + a_nxⁿ) ↦ (p₀^a0⋅p₁^a1⋅…⋅p_n^an), where p_k refers to the kth prime number. Now, this is a homomorphism from ℤ[x] to ℚ₊ because φ(p(x) + q(x)) = φ(p(x))⋅φ(q(x)). You can also easily show that it is onto and one-to-one, using the uniqueness of prime factorization. Therefore φ is an isomorphism!

I think this is a good example to test the intuitive notion that once one “knows” a group, one also knows all groups that it is isomorphic to. It’s often useful to think of isomorphic groups as being like one book written in two different languages, with the isomorphism being the translation dictionary. But the non-obviousness of the isomorphism here makes it feel like the two groups in fact have a considerably different internal structure.

Curiosity Number Two

Your friend comes up to you and tells you, “I’m thinking of some finite group. All I’ll tell you is that it has at least two order-2 elements. I’ll give you $20 if you can tell me what the group that’s generated by these two elements is (up to isomorphism)!“

What do you think your chances are of getting this $20 reward? It seems intuitively like your chances are probably pretty dismal… there are probably hundreds or maybe even an infinity of groups that match her description.

But it turns out that you can say exactly what group your friend is thinking of, just from this information!

Call the group G. G is finite and has two order-2 elements, which we’ll call a and b. So we want to find out what <a,b> is. Define r = ab and n = |r|.  Then ara = a(ab)a = (aa)ba = ba = (ab)^-1 = r^-1 = r^n-1. So ara = r^n-1, or in other words ar = r^n-1a. Also, since b = ar, we can write the group we’re looking for either as <a,b> or as <a,r> (these two are equal).

Thus the group we’re looking for can be described as follows:

<a, r | a² = rⁿ = e, ar = r^n-1a>.

Look familiar? This is just the dihedral group of size 2n; it is the group of symmetries of a regular n-gon, where a is a flip and r is a rotation!

So if G is a finite group with at least two order-2 elements a and b, then <a, b> ≅ Dih_|ab|.

This serves to explain the ubiquity and importance of the dihedral groups! Any time a group contains more than one order-two element, it must have a dihedral group of some order as a subgroup.

Curiosity Number Three

If K ◃ H ◃ G, then H/K ◃ G/K and (G/K) / (H/K) ≅ G/H.

(G/K) / (H/K) is a pretty wild object; it is a group of cosets, whose representatives are themselves cosets. But this theorem allows us to treat it as a much less exotic object, an ordinary quotient group with representatives as elements from G.

I don’t have much else to say about this one, besides that I love how the operation of forming a quotient group behaves so much like ordinary division!

The Toolkit

1. The Group Axioms
   1. Closure: ∀a,b ∈ G, a•b ∈ G
   2. Associativity: ∀a,b,c ∈ G, (a•b)•c = a•(b•c)
   3. Identity: ∃e ∈ G s.t. ∀a ∈ G, e•a = a•e = a
   4. Inverses: ∀a ∈ G, ∃a’ ∈ G s.t. a’•a = e
2. Cancellation Rule
   (a•b = a•c) ⇒ (b = c)
3. Order Doesn’t Matter
   You can write a Cayley table with the elements in any order that’s convenient.
4. Sudoku Principle
   Each row and column in the Cayley table for a group G contains every element in G exactly once.
5. Lagrange’s Theorem
   H ≤ G ⇒ |G| is divisible by |H|
6. Elements Generate Subgroups
   ∀g ∈ G, <g> = {g^k for all integer k} ≤ G.
   (|<g>| = n) ⇒ (gⁿ = e).
7. Cauchy’s Theorem
   (|G| = pk for prime p) ⇒ (∃g ∈ G s.t. g^p = e)
8. Classification of Finite Abelian Groups
   Every finite abelian group is isomorphic to Z_n or direct products of Z_n
9. Orbit-Stabilizer Theorem
   |orb(x)||stab(x)| = |G|
10. Partition Equation
    ∑|orb(x)| = |X|. The sum is taken over one representative for each orbit.
11. Center is a Normal Subgroup
    Z(G), the center of G, is a normal subgroup. So G/Z is a group.
12. Class Equation
    |G| = |Z| + ∑|Cl(x)|, where all terms divide |G| and each |Cl(x)| is neither 1 nor |G|. The sum is taken over non-central representatives of conjugacy classes.
13. G/Z is Cyclic Implies G is Abelian
    G/Z is cyclic ⇒ G is abelian
14. Size of Product of Subgroups
    |AB| = |A| |B| / |A ∩ B|
15. Sylow’s First Theorem
    If |G| = pⁿk for prime p and k not divisible by p, then G has a subgroup of size pⁿ.
16. Sylow’s Third Theorem
    If |G| = pⁿk for prime p and k not divisible by p, then the number of subgroups of size pⁿ must be 1 mod p, and must divide k.

Exercises

Example 1: Solving the group of size 3

Suppose |G| = 3. By the Identity Axiom (1.3), G has an identity element e. Call the other two elements a and b. So G = {e, a, b}. Let’s write out the Cayley table for the group:

	e	a	b
e	e	a	b
a	a
b	b

By the Cancellation Rule (2), a•a ≠ a. By Lagrange’s Theorem (5), a•a ≠ e, as then the set {e, a} would be a subgroup of size 2, which doesn’t divide 3. Therefore by Closure (1.1), a•a = b.

	e	a	b
e	e	a	b
a	a	b
b	b

We can fill out the rest of the Cayley table by the Sudoku principle (4).

	e	a	b
e	e	a	b
a	a	b	e
b	b	e	a

Example 2: Solving the group of size 5

	e	a	b	c	d
e	e	a	b	c	d
a	a
b	b
c	c
d	d

If a•a = e, then {e,a} would be a subgroup of size 2. By Lagrange’s theorem, then, a•a ≠ e. Also, by the Sudoku principle, a•a ≠ a. Thus we can choose the order of the rows/columns such that a•a = b (3).

	e	a	b	c	d
e	e	a	b	c	d
a	a	b
b	b
c	c
d	d

Now look at a•b = a•(a•a) = a³. If a³ = e, then <a> would be a subgroup of size 3 (by 6). 3 doesn’t divide 5, so a•b ≠ e (Lagrange’s theorem again). By the Sudoku principle, a•b also isn’t a or b. So we can arrange the Cayley table so that a•b = c. Since a•b = a³ =  b•a, b•a = c as well.

	e	a	b	c	d
e	e	a	b	c	d
a	a	b	c
b	b	c
c	c
d	d

Now we can use the Sudoku principle to fill out the rest!

	e	a	b	c	d
e	e	a	b	c	d
a	a	b	c	d	e
b	b	c	d	e	a
c	c	d	e	a	b
d	d	e	a	b	c

Example 3: Solving all groups of prime order

Suppose |G| = p, where p is some prime number. By Lagrange’s theorem every subgroup of G has either size 1 (the trivial subgroup {e}) or size p (G itself). Since the set generated by any element is a subgroup, any element g in G must have the property that |<g>| = 1 or p.

Choose g to be a non-identity element. <g> includes e and g, so |<g>| ≥ 2. So |<g>| = p. So <g> = G. So G is a cyclic group (generated by one of its elements). This fully specifies every entry in the Cayley table (gⁿ•g^m = g^n+m), so there is only one group of size p up to isomorphism.

Example 4: Solving size 6 groups

Suppose |G| = 6.

By Cauchy’s theorem (7), there exists at least one element of order 2 and at least one element of order 3. Name the order-2 element a and the order-3 b. Fill in the Cayley table accordingly:

	e	a	b	?	?	?
e	e	a	b
a	a	e
b	b
?
?
?

Suppose b² = a. Then (b²)² = a² = e, so b is order 4. But b is order 3. So b² ≠ a. Also, b² ≠ e for the same reason, and ≠ b by the Cancellation Rule . So b² is something new, which we’ll put in our next column:

	e	a	b	b2	?	?
e	e	a	b	b2
a	a	e
b	b		b2
b2	b2
?
?

b³ = e, so we can fill out b • b² and b² • b, as well as b² • b² = b³ • b = b

	e	a	b	b2	?	?
e	e	a	b	b2
a	a	e
b	b		b2	e
b2	b2		e	b
?
?

By the Sudoku principle, we can clearly see that a • b is none of e, a, b, or b². So whatever it is, we’ll put it in the next column as “ab”:

	e	a	b	b2	ab	?
e	e	a	b	b2	ab
a	a	e	ab
b	b		b2	e
b2	b2		e	b
ab	ab
?

Looking at a•b², we can again see that it is none of the elements we’ve identified so far. So whatever it is, we’ll put it in the next column as “ab²”.

	e	a	b	b2	ab	ab2
e	e	a	b	b2	ab	ab2
a	a	e	ab	ab2
b	b		b2	e
b2	b2		e	b
ab	ab
ab2	ab2

Associativity (1.2) allows us to use the algebraic rules a²  = e and b³ = e to fill in a few more spots (like a•ab = a²b = b).

	e	a	b	b2	ab	ab2
e	e	a	b	b2	ab	ab2
a	a	e	ab	ab2	b	b2
b	b		b2	e
b2	b2		e	b
ab	ab		ab2	a
ab2	ab2		a	ab

Now everything else in the table is determined by a single choice: should we assign b•a to ab, or to ab²? Each leads to a Cayley table consistent with the axioms, so we write them both out, using the Sudoku principle to finish each one entirely.

Group 1: (ba = ab)

	e	a	b	b2	ab	ab2
e	e	a	b	b2	ab	ab2
a	a	e	ab	ab2	b	b2
b	b	ab	b2	e	ab2	a
b2	b2	ab2	e	b	a	ab
ab	ab	b	ab2	a	b2	e
ab2	ab2	b2	a	ab	e	b

Group 2: (ba = ab²)

	e	a	b	b2	ab	ab2
e	e	a	b	b2	ab	ab2
a	a	e	ab	ab2	b	b2
b	b	ab2	b2	e	a	ab
b2	b2	ab	e	b	ab2	a
ab	ab	b2	ab2	a	e	b
ab2	ab2	b	a	ab	b2	e

These two groups are clearly not isomorphic, as one is commutative and the other not. This proves that there are two groups of size 6 up to isomorphism!

Example 5: Solving groups of prime order, again

Suppose |G| = p, where p is some prime number. The center of G, Z(G), is a subgroup of G (by 11). So by Lagrange’s theorem, |Z| = 1 or p.

By the Class Equation (12), |G| = |Z| + ∑|Cl(x)|. All terms divide p and each |Cl(x)| ≠ 1, so we have p = |Z| + ∑p. This is only possible if |Z| = 0 or there are no non-central elements. Z contains e, so |Z| ≠ 0. So there are no non-central elements. Thus G = Z, which is to say G is abelian.

By the Classification of Finite Abelian Groups (8), G is isomorphic to Z_p.

Example 6: Prime power groups have non-trivial centers

Suppose |G| = pⁿ, where p is some prime number and n is some positive integer. The Class Equation tells us that |G| = |Z| + ∑|Cl(x)|, where |Z| = 1, p, p², …, or pⁿ and each |Cl(x)| = p, p², …, or p^n-1. Taking the Class Equation modulo p we find that |Z| = 0 (mod p), so |Z| cannot be 1. So G has a non-trivial center!

Example 7: Solving groups of prime-squared order

Suppose |G| = p², where p is some prime number. The Class Equation tells us that |G| = |Z| + ∑|Cl(x)|, where |Z| = 1, p, or p² and each |Cl(x)| = p. So we have p² = |Z| + ∑p. Taking this equation mod p we find that |Z| = 0 (mod p), so |Z| is non-trivial. (This is just a special case of Example 6 above.) So |Z| = p or p².

Suppose |Z| = p. Then |G/Z| = p²/p = p. So G/Z is cyclic. But then G is abelian (by 13). So G = Z, which implies that |Z| = p². Contradiction. So |Z| = p², i.e. G is abelian.

By the classification of finite abelian groups we see that there are two possibilities: G is isomorphic to integers mod p² or G is isomorphic to Z_p x Z_p. These are the only two groups (up to isomorphism) of size p².

Example 8: Proving Cauchy’s Theorem

Suppose |G| = n, where n is divisible by some prime p.

Let X be the subset of p-tuples of elements from G whose product is e. That is, X = {(g₁,g₂,…,g_p) ∈ G^p s.t. g₁g₂…g_p = e}. Notice that the number of elements in X is |G|^p-1 (there are |G| choices for each of the first p-1 elements, and then the final one is fully determined by the constraint). Let the integers mod p (Z_p) act on X by the following rule: the action of 1 on an element of X is 1 • (g₁,g₂,…,g_p) = (g_p,g₁,g_2,…,g_p-1). (From this we can deduce the action of all the other integers mod p.)

By the Orbit Stabilizer Theorem (9), the possible orbit sizes for this action must divide the size of the cyclic group. That is, for every x ∈ X, |orb(x)| = 1 or p. Let r be the number of orbits of size 1 and s be the number of orbits of size p. Then by the Partition Equation (10), we have r + sp = |X| = |G|^p-1. By our starting assumption, we have that the right hand side is divisible by p. And since sp is divisible by p, r must also be divisible by p. That is, r = 0, or p, or 2p, and so on.

Notice that the p-tuple (e,e,…,e) is in X, and that its orbit size is 1. So r is at least 1. So r = p, or 2p, and so on. That means that there is at least one more element of X with orbit size 1. This element must look like (a,a,…,a) for some a ∈ G. And since it’s in X, it must satisfy our constraint, namely: a^p = e! So there is at least one non-identity element of order p.

Example 9: Subgroups of Group of Size 20

Suppose |G| = 10 = 2²*5

By Cauchy’s Theorem and Sylow’s First Theorem (15), we know there must be subgroups of size 2, 4, and 5. We can learn more about the number of subgroups of sizes 4 and 5 using Sylow’s Third Theorem (16).

If N is the number of subgroups of size 4, then N divides 5 (1 or 5), and N = 1 (mod 2). So N = 1 or 5.

If N is the number of subgroups of size 5, then N divides 4 (1, 2, 4), and N = 1 (mod 5). So N = 1.

Example 10: Subgroups of Group of Size p²q

Suppose |G| = p²q, for primes p and q where 2 < p < q and q-1 is not a multiple of p.

Then by (15) we have subgroups of size p² and q. Again, we use (16) to learn more about these subgroups.

If N is the number of subgroups of size p², then N divides q (1 or q), and N = 1 (mod p). q ≠ 1 (mod p), N cannot be q. So N = 1.

If N is the number of subgroups of size q, then N divides p² (1, p, or p²), and N = 1 (mod q) (so N is 1, or q+1, or 2q+1, and so on). But p is smaller than q, so N can’t be p. And if N = p², then p² – 1 must be a multiple of q. But p² – 1 = (p+1)(p-1). Both of these values are too small to contain factors of q. So their product cannot be a multiple of q. So N ≠ p² either. So N = 1!

Example 11: Subgroups of Group of Size pqⁿ

Suppose |G| = pqⁿ, where p and q are primes and 2 < p < q.

Using Sylow III (16): If N is the number of subgroups of size qⁿ, then N divides p (1 or p) and N = 1 (mod q). p is too small to be a multiple of q plus 1, So N = 1.

Example 12: Classifying Groups of Size 2p

Suppose |G| = 2p for some prime p > 2. Let’s use everything in our toolkit to fully classify the possibilities!

By Cauchy, we have elements of of order 2 and p. Let a be an element of order 2 and b an element of order p. Let A = <a> = {e, a} and B = <b> = {e, b, b², …, b^p-1}. A and B are both cyclic of different orders, so their intersection is trivial. So by (14), |AB| = |A| |B| / |A ∩ B| = 2p. So AB = G. This means we can write all the elements of G as follows:

	e	b	b2	…	bp-1
e	e	b	b2	…	bp-1
a	a	ab	ab2	…	abp-1

So G = {e, b, b², …, b^p-1, a, ab, ab², …, ab^p-1}. Call N₂ the number of subgroups of size 2 and N_p the number of subgroups of size p. Applying Sylow III, it is easy to see that there are two possibilities: (N₂ = 1 and N_p = 1), or (N₂ = p and N_p = 1).

Case 1: N₂ = p and N_p = 1.

Since N₂ = p and N_p = 1, there are p elements of order 2 (one for each subgroup) and p-1 elements of order p. Adding in e, this accounts for all of G.

Order 1: e
Order p: b, b², …, b^p-1
Order 2: a, ab, ab², …, ab^p-1 (the remaining members of G)

Now, since a and b are in G, so must be ba. And since G = AB, ba ∈ AB. It’s not e or a power of b (apply the Cancellation Rule), so ba must be abⁿ for some n. This means that ba is order 2, so (ba)² = e. Expanding and substituting, we get (ba)² = (ba)(ba) = (ba)(abⁿ) = ba²bⁿ = bⁿ⁺¹ = e = b^p.

So n = p – 1, or in other words, ba = ab^p-1. This actually allows us to fully fill out the rest of the Cayley table, as we can take any expression and move the ‘b’s all the way to the right, ending up with something that looks like aⁿb^m.  This is the dihedral group of degree p (the group of symmetries of a regular p-gon)!

Case 2: N₂ = 1 and N_p = 1.

Order 1: e
Order p: b, b², …, b^p-1
Order 2: a

No other elements can be order 1, 2, or p, so all other elements must be order 2p (think Lagrange’s theorem). For instance, (ab)^2p = e and (ab)^p ≠ e . You can show that this only works if ab = ba, which allows you to freely move ‘a’s and ‘b’s around in any expression. ((ab)^2p = a^2p b^2p = (a²)^p (b^p)² = e, and (ab)^p = a^p b^p = a^p = a ≠ e).

Again, we can use this to fill out the entire Cayley table. The group we get is isomorphic to Z_2p (the integers mod 2p)!

So if |G| = 2p for some prime p > 2, then G is either the group of symmetries of a regular p-gon, or it’s the integers mod p. Fantastic! If you follow this whole line of reasoning, then I think that you have a good grasp of how to use the toolkit above.

What comes next?

Let me start this off by saying that if you’re reading this blog and haven’t ever checked out the Youtube channel Numberphile, you need to go there right away and start bingeing their videos. That’s what I’ve been doing for the last few days, and it’s given me tons of cool new puzzles to consider.

Here’s one:

Naturally, after watching this video I wanted to try this out for myself. Here you see the pattern arising beautifully from the randomness:

I urge you to think hard about why the Sierpinski triangle would arise from something as simple as randomly hopping between midpoints. It’s very non-obvious, and although I have a few ideas, I’m still missing a clear intuition.

I also made some visualizations for other shapes. I’ll show some of them, but encourage you to make predictions about what pattern you’d expect to see before scrolling down to see the actual result.

First:

Square

Instead of three points arranged as above, we will start out with four points arranged in a perfect square. Then, as before, we’ll jump from our starting point halfway to one of these four, and will continue this procedure ad infinitum.

What pattern will arise? Do you think that we’ll have “missing regions” where no points can land, like with the triangle?

Scroll down to see the answer…

(…)

(…)

(…)

Okay! So it looks like the whole square gets filled out, with no missing regions. This was pretty surprising to me; given that three points gave rise to a intricate fractal pattern, why wouldn’t four points do the same? What’s special about “3” .

Well, perhaps things will be different if we tweak the positions of the corners slightly? Will any quadrilateral have the same behavior of filling out all the points, or will the blank regions re-arise? Again, make a prediction!

Quadrilaterals

Let’s see:

Okay, now we see that apparently the square was actually a very special case! Pretty much any quadrilateral we can construct will give us a nested infinity of blank regions, as long as at least one angle is not equal to 90º. Again, this is fascinating and puzzling to me. Why do 90º angles invariably cause the whole region to fill out? I’m not sure.

Let’s move on to a pentagon! Do you think that a regular pentagon will behave more like a triangle or a square?

Pentagon

Take a look…

And naturally, the next question is what about a hexagon?

Hexagon

Notice the difference between the hexagon and all the previous ones! Rather than having small areas of points that are never reached, it appears that suddenly we get lines! Again, I encourage you to try to think about why this might be (what’s so special about 6?) and leave a comment if you have any ideas.

Now, I because curious about what other types of patterns we can generate with simple rules like these. I wondered what would happen if instead of simply jumping to the average of the current point and a randomly chosen point, we built a pattern with some “memory”. For instance, what if we didn’t just look at the current point and the randomly chosen point, but also at the last chosen point? We could then take the middle of the triangle formed by these three points as our new point.

It turns out that the patterns that arise from this are even more beautiful than the previous ones! (In my opinion, of course)

Take a look:

Triangle

Square

Pentagon

Hexagon

Heptagon

I’ll stop here, but this is a great example of how beautiful and surprising math can be. I would have never guessed that such intricate fractal patterns would arise from such simple random rules.