Four Colour Theorem

We present a new proof of the famous four colour theorem using algebraic and topological methods. Recent research in physics shows that this proof directly implies the Grand Unification of the Standard Model with Quantum Gravity in its physical interpretation and conversely the existence of the standard model of particle physics shows that nature applies this proof of the four colour theorem at the most fundamental level, giving us a grand unified theory. In particular, we have shown how to use this theory to predict the Higgs Boson Mass [arXiv:0912.5189] and Einstein's Cosmological Constant with precision. Thus, nature itself demonstrates the logical completeness and consistency of the proof. Google Scholar Citations © 2000

This proof was first announced by the Canadian Mathematical Society in 2000. The proof appears as the twelfth chapter of the text book Graph Theory published by Orient Longman and Universities Press of India in 2008. This proof has also been published in the Euroacademy Series Baltic Horizons No. 14 (111) dedicated to Fundamental Research in Mathematics in 2010. Finally, the proof features in an exquisitely illustrated edition of The Four Colour Theorem published by Amazon in 2011. The Endowed Chair of the Institute of Mathematics was bestowed upon Distinguished Professor Ashay Dharwadker in 2012 to honour his fundamental contributions to Mathematics and Natural Sciences.

The famous four colour theorem seems to have been first proposed by Möbius in 1840, later by DeMorgan and the Guthrie brothers in 1852, and again by Cayley in 1878. The problem of proving this theorem has a distinguished history, details of which abound in the literature. The statement of the theorem may be introduced as follows. In colouring a geographical map it is customary to give different colours to any two countries that have a segment of their boundaries in common. It has been found empirically that any map, no matter how many countries it contains nor how they are situated, can be so coloured by using only four different colours.

Figure 0. Map of Madhya Pradesh and adjoining states in India

The map of India requires four colours in the states bordering Madhya Pradesh. The fact that no map was ever found whose colouring requires more than four colours suggests the mathematical theorem.

FOUR COLOUR THEOREM. For any subdivision of the plane into non-overlapping regions, it is always possible to mark each of the regions with one of the numbers 0, 1, 2, 3 in such a way that no two adjacent regions receive the same number.

STEPS OF THE PROOF: We shall outline the strategy of the new proof given in this paper. In section I on MAP COLOURING, we define maps on the sphere and their proper colouring. For purposes of proper colouring it is equivalent to consider maps on the plane and furthermore, only maps which have exactly three edges meeting at each vertex. Lemma 1 proves the six colour theorem using Euler's formula, showing that any map on the plane may be properly coloured by using at most six colours. We may then make the following basic definitions.

Define N to be the minimal number of colours required to properly colour any map from the class of all maps on the plane.
Based on the definition of N, select a specific map m(N) on the plane which requires no fewer than N colours to be properly coloured.
Based on the definition of the map m(N), select a proper colouring of the regions of the map m(N) using the N colours 0, 1, ..., N-1.

The whole proof works with the fixed number N, the fixed map m(N) and the fixed proper colouring of the regions of the map m(N). In section II we define STEINER SYSTEMS and prove Tits' inequality and its consequence that if a Steiner system S(N+1, 2N, 6N) exists, then N cannot exceed 4. Now the goal is to demonstrate the existence of such a Steiner system. In section III we define EILENBERG MODULES. The regions of the map m(N) are partitioned into disjoint, nonempty equivalence classes 0, 1, ..., N-1 according to the colour they receive. This set is given the structure of the cyclic group Z_N = {0, 1, ..., N-1} under addition modulo N. We regard Z_N as an Eilenberg module for the symmetric group S₃ on three letters and consider the split extension Z_N]S₃corresponding to the trivial representation of S₃. By section IV on HALL MATCHINGS we are able to choose a common system of coset representatives for the left and right cosets of S₃ in the full symmetric group on |Z_N]S₃| letters. For each such common representative and for each ordered pair of elements of S₃, in section V on RIEMANN SURFACES we establish a certain action of the two-element cyclic group on twelve copies of the partitioned map m(N) by using the twenty-fourth root function of the sheets of the complex plane. Using this action, section VI gives the details of the MAIN CONSTRUCTION. The 6N elements of Z_N]S₃ are regarded as the set of points and lemma 23 builds the blocks of 2N points with every set of N+1 points contained in a unique block. This constructs a Steiner system S(N+1, 2N, 6N) which implies by Tits' inequality that N cannot exceed 4, completing the proof. The lemmas 1-23 and theorem 24 below are written in logical sequence. ☐

A map on the sphere is a subdivision of the surface into finitely many regions. A map is regarded as properly coloured if each region receives a colour and no two regions having a whole segment of their boundaries in common receive the same colour. Since deformations of the regions and their boundary lines do not affect the proper colouring of a map, we shall confine ourselves to maps whose regions are bounded by simple closed polygons. For purposes of proper colouring it is equivalent to consider maps drawn on the plane. Any map on the sphere may be represented on the plane by boring a small hole through the interior of one of the regions and deforming the resulting surface until it is flat. Conversely, by a reversal of this process, any map on the plane may be represented on the sphere. Furthermore, it suffices to consider 3-regular maps, i.e. maps with exactly three edges meeting at each vertex, by the following argument. Replace each vertex at which more than three edges meet by a small circle and join the interior of each such circle to one of the regions meeting at the vertex. A new map is obtained which is 3-regular. If this new map can be properly coloured by using at most n colours, then by shrinking the circles down to points, the desired colouring of the original map using at most n colours is obtained.

Figure 1. A map that requires four colours to be properly coloured

1. LEMMA. Any map on the sphere can be properly coloured by using at most six colours.

PROOF: Assume that the given map is 3-regular. First show that there must be at least one region whose boundary is a polygon with fewer than six sides, as follows. Let E be the number of edges, V the number of vertices, F the number of regions and F_n the number of regions whose boundary is a polygon with n sides in the given map. Then

F = F₂+F₃+F₄+...

2E = 3V = 2F₂+3F₃+4F₄+...

since a region bounded by n edges has n vertices and each vertex belongs to three regions. By Euler's formula V-E+F = 2,

⇒	6V-6E+6F = 12
⇒	4E-6E+6F = 12
⇒	6F-2E = 12
⇒	6(F₂+F₃+F₄+...)-(2F₂+3F₃+4F₄+...) = 12
⇒	4F₂+3F₃+2F₄+F₅+0+NEGATIVE TERMS = 12	.

Hence, at least one of F₂, F₃, F₄, F₅ must be positive. Now, if a region R with fewer than six sides is removed from the map and the resulting map coloured with six colours inductively, there is always a colour left for R. ☐

By lemma 1, the minimal number of colours required to properly colour any map from the class of all maps on the sphere is a well-defined natural number. We may now make the following basic definition.

DEFINITION

Define N to be the minimal number of colours required to properly colour any map from the class of all maps on the sphere. That is, given any map on the sphere, no more than N colours are required to properly colour it and there exists a map on the sphere which requires no fewer than N colours to be properly coloured.
Based on the definition of N, select a specific map m(N) on the sphere which requires no fewer than N colours to be properly coloured.
Based on the definition of the map m(N), select a proper colouring of the regions of the map m(N) using the N colours 0, 1, ..., N-1.

The natural number N, the map m(N) and the proper colouring of the regions of m(N) is fixed for all future reference. By the example shown in figure 1 and lemma 1, 4 ≤ N ≤ 6. The goal is to show that N ≤ 4.

A Steiner system S(t, k, v) is a set P of points together with a set B of blocks such that

There are v points.
Each block consists of k points.
Every set of t points is contained in a unique block.

Note that by definition t, k, v are nonnegative integers with t ≤ k ≤ v. Steiner systems with v = k (only one block that contains all the points) or k = t (every k-element subset of points is a block) are called trivial. An example of a nontrivial Steiner system is S(5, 8, 24) due to Witt, whose blocks are known as Golay codewords of weight eight [see an explicit construction]. The group of automorphisms of S(5, 8, 24) (permutations of points which permute blocks) is the largest of the Mathieu groups, M₂₄.

2. LEMMA. [J. TITS] If there exists a nontrivial Steiner system S(t, k, v) then

v ≥ (t+1)(k-t+1).

PROOF: First show that there exists a set X₀ of t+1 points that is not contained in any block, as follows. Suppose that for every set X of t+1 points there is a block B_X that contains it. Then, this block B_X must be the unique block containing X, since X has more than t points. Let b denote the total number of blocks. Count in two ways the number of pairs (X, B_X) where X is a set of t+1 points and B_X is the unique block containing it. One finds

(

t+1

)

(

t+1

)

Count in two ways the number of pairs (Y, B_Y) where Y is a set of t points and B_Y is the unique block containing it, by definition of a Steiner system. One finds

(

)

(

)

Hence

(

t+1

)

(

)

(

t+1

)

(

)

and it follows that b = 1 and k = v, contradicting the hypothesis that the Steiner system is nontrivial. Now choose a fixed set X₀ of t+1 points that is not contained in any block. For each set Z of t points contained in X₀ there is a unique block B_Z containing Z. Each such B_Z has k-t points not in X₀ and any point not in X₀ is contained in at most one such B_Z, since two such blocks already have t-1 points of X₀ in common. The union of the blocks B_Z contains (t+1)+(t+1)(k-t) points and this number cannot exceed the total number of points v. ☐

Recall the definition from section I that N is the minimal number of colours required to properly colour any map from the class of all maps on the sphere and m(N) is a specific map which requires all of the N colours to properly colour it. The regions of the map m(N) have been properly coloured using the N colours 0, 1, ..., N-1. From the map m(N) and its fixed proper colouring, we shall construct a Steiner system S(N+1, 2N, 6N) by defining the points and blocks in a certain way. The next lemma shows that this construction would force N ≤ 4.

3. LEMMA. Referring to the definition of N in section I, if there exists a Steiner system S(N+1, 2N, 6N) then N ≤ 4.

PROOF: Since 4 ≤ N ≤ 6 by definition, the Steiner system is nontrivial if it exists. By lemma 2, 6N ≥ (N+1+1)(2N-N-1+1) = (N+2)N. Hence 6 ≥ N+2 and it follows that 4 ≥ N. ☐

Now, the goal is to demonstrate the existence of the Steiner system S(N+1, 2N, 6N) based upon the definition of the map m(N).

Let G be a group with identity element e and let Z denote the integers. The integral group algebra (ZG, +, ·) is a ring whose elements are formal sums

Σ	n_gg
^g∈G

with g in G and n_g in Z such that n_g = 0 for all but a finite number of g. Addition and multiplication in ZG are defined by

Σ	n_gg	+	Σ	m_gg	=	Σ	(n_g+m_g)g,
^g∈G			^g∈G			^g∈G

Σ	n_gg	·	Σ	m_gg	=	Σ	(	Σ	n_gh-1m_h	)	g.
^g∈G			^g∈G			^g∈G		^h∈G

The element n of Z is identified with the element n·e of ZG and the element g of G is identified with the element 1·g of ZG, so that Z and G are to be regarded as subsets of ZG. The underlying additive abelian group (ZG, +) is the direct sum of copies of the integers Z indexed by elements of G. If Q is a subgroup of G then ZQ is a subring of ZG in a natural way. For each element g of G, the right multiplication R(g): G → G; x → xg and the left multiplication L(g): G → G; x → gx are permutations of the set G. Denote the group of all permutations of the set G by Sym(G). Then

R	: G → Sym(G); g → R(g)
L^-1	: G → Sym(G) ; g → L^-1(g) = L(g^-1)

are embeddings of the group G in Sym(G). The images R(G), L^-1(G) are called the Cayley right and left regular representations of G, respectively. The subgroup of Sym(G) generated by the set R(G)∪L^-1(G) = {R(g), L(g^-1)|g∈G} is called the combinatorial multiplication group Mlt(G) of G. There is an exact sequence of groups

			_Δ		_T
1	→	C(G)	→	G×G	→	Mlt(G)	→	1

where T(x, y) = R(x)L(y^-1) and Δc = (c, c) for an element c of the center C(G) of G. If Q is a subgroup of G then the relative combinatorial multiplication group Mlt_G(Q) of Q in G is the subgroup of Mlt(G) generated by the set R(Q)∪L^-1(Q) = {R(q), L^-1(q)|q∈Q}. The orbits of the action of Mlt_G(Q) on G are the double cosets QgQ of the subgroup Q in G. The stabilizer of the identity element e is the subgroup of Mlt_G(Q) generated by the set {T(q) = R(q)L^-1(q)|q∈Q}. A representation of the group Q is usually defined as a module, i.e. an abelian group (M, +), for which there is a homomorphism T: Q → Aut(M, +) showing how Q acts as a group of automorphisms of the module. Another approach due to Eilenberg, views a module M for the group Q as follows. The set M×Q equipped with the multiplication

(m₁, q₁)(m₂, q₂) = (m₁ + m₂T(q₁), q₁q₂)

becomes a group M]Q known as the split extension of M by Q. There is an exact sequence of groups

			ι		π
1	→	M	→	M]Q	→	Q	→	1

with ι: M → M]Q; m → (m, e) and π: M]Q → Q; (m, q) → q split by 0: Q → M]Q; q → (0, q). The group action T is recovered from the split extension M]Q by mT(q)ι = mιR((0, q))L^-1((0, q)) for m in M and q in Q. In this context we shall call M an Eilenberg module for the group Q. For example, the trivial representation for the group Q is obtained by defining T: Q → Aut(M, +); q → 1_M, the identity automorphism of (M, +) and the corresponding split extension is the group direct product M×Q. The Cayley right regular representation for the group Q is obtained by defining

T: Q → Aut(ZQ, +); q →	(	Σ	n_gg	→	Σ	n_ggR(q)	)	.
		^g∈Q			^g∈Q

Here T(q) = R(q)L^-1(q) with L^-1(q) acting trivially on the module elements and R(q) acting as the usual right multiplication. The split extension ZQ]Q has multiplication given by

(m₁, q₁)(m₂, q₂) = (m₁+ m₂R(q₁), q₁q₂)

for m₁, m₂ in ZQ and q₁, q₂ in Q.

Referring to the definition in section I, N is the minimal number of colours required to properly colour any map from the class of all maps on the sphere and m(N) is a specific map that requires all of N colours to be properly coloured. Note that m(N) has been properly coloured by using the N colours 0, 1, ..., N-1 and this proper colouring is fixed. The set of regions of m(N) is then partitioned into subsets 0, 1, ..., N-1 where the subset m consists of all the regions which receive the colour m. Note that the subsets 0, 1, ..., N-1 are each nonempty (since m(N) requires all of the N colours to be properly coloured) and form a partition of the set of regions of m(N) (by virtue of proper colouring). Identify the set {0, 1, ..., N-1} with the underlying set of the N-element cyclic group Z_N under addition modulo N. Let S₃ denote the symmetric group on three letters, identified with the dihedral group of order six generated by ρ, σ where |ρ| = 3 and |σ| = 2.

4. LEMMA. (Z_N, +) is an Eilenberg module for the group S₃ with the trivial homomorphism

T₁: S₃ → Aut(Z_N, +); α → 1Z_N

where1Z_N denotes the identity automorphism of Z_N. The corresponding split extension Z_N]S₃has multiplication given by

(m₁, α₁)·(m₂, α₂) = (m₁+ m₂, α₁α₂)

and is a group isomorphic to the direct product Z_N×S₃.

PROOF: Follows from definition. ☐

Referring to section II, the goal is to construct a Steiner system S(N+1, 2N, 6N). We shall take the point set of the Steiner system to be the underlying set of the split extension Z_N]S₃. The following lemma is used in section V.

5. LEMMA. Let (Z(Z_N]S₃), +) and (ZS₃, +) denote the underlying additive groups of the integral group algebras Z(Z_N]S₃) and ZS₃, respectively. Then (Z(Z_N]S₃), +) is an Eilenberg module for the group (ZS₃, +) with the trivial homomorphism

T₂:(ZS₃, +) → Aut(Z(Z_N]S₃), +);	Σ	n_αα → 1Z(Z_N]S₃)
	α∈S₃

where 1Z(Z_N]S₃) denotes the identity automorphism of (Z(Z_N]S₃), +). The corresponding split extension Z(Z_N]S₃)]ZS₃ has multiplication given by

(

n_{(m, β)}(m, β)

n_αα

)

(

n'_{(m, β)}(m, β)

n'_αα

)

(m, β)∈Z_N]S₃

α∈S₃

(m, β)∈Z_N]S₃

α∈S₃

=	(	Σ	(n_{(m, β)}+n'_(m, β))(m, β)	,	Σ	(n_α+n'_α)α	)
		(m, β)∈Z_N]S₃			α∈S₃

and is a group isomorphic to the direct product (Z(Z_N]S₃)×ZS₃, +).

PROOF: Follows from definition. ☐

Let Γ be a bipartite graph with vertex set V = X∪Y and edge set E (every edge has one end in X and the other end in Y). A matching from X to Y in Γ is a subset M of E such that no vertex is incident with more than one edge in M. A matching M from X to Y in Γ is called complete if every vertex in X is incident with an edge in M. If A is a subset of V then let adj(A) denote the set of all vertices adjacent to a vertex in A.

6. LEMMA. [P. HALL] If |adj(A)| ≥ |A| for every subset A of X then there exists a complete matching from X to Y in Γ.

PROOF: A matching from X to Y in Γ with |M| = 1 always exists by choosing a single edge in E. Let M be a matching from X to Y in Γ with m edges, m < |X|. Let x₀∈X such that x₀ is not incident with any edge in M. Since |adj({x₀})| ≥ 1, there is a vertex y₁ adjacent to x₀ by an edge in E\M. If y₁ is not incident with an edge in M, then stop. Otherwise, let x₁ be the other end of such an edge. If x₀, x₁, ..., x_k and y₁, ..., y_k have been chosen, then since |adj({x₀, x₁, ..., x_k})| ≥ k+1, there is a vertex y_k₊₁, distinct from y₁, ..., y_k, that is adjacent to at least one vertex in {x₀, x₁, ..., x_k}. If y_k₊₁ is not incident with an edge in M, then stop. Otherwise, let x_k₊₁ be the other end of such an edge. This process must terminate with some vertex, say y_k₊₁. Now build a simple path from y_k₊₁ to x₀ as follows. Start with y_k₊₁ and the edge in E\M joining it to, say xi₁ with i₁ < k+1. Then add the edge in M from xi₁ to yi₁. By construction, yi₁ is joined by an edge in E\M to some xi₂ with i₂ < i₁. Continue adding edges in this way until x₀ is reached. One obtains a path y_k₊₁, xi₁, yi₁, xi₂, yi₂, ..., xi_r, yi_r, x₀ of odd length 2r+1 with the r+1 edges {y_k₊₁, xi₁}, {yi₁, xi₂}, ..., {yi_r, x₀} in E\M and the r edges {xi₁, yi₁}, ..., {xi_r, yi_r} in M. Define

M' = (M\{{xi₁, yi₁}, ..., {xi_r, yi_r}})∪{{y_k₊₁, xi₁}, {yi₁, xi₂}, ..., {yi_r, x₀}}.

Then M' is a matching from X to Y in Γ, with |M'| = |M|-r+r+1 = |M|+1. Repeating this process a finite number of times must yield a complete matching from X to Y in Γ. ☐

7. LEMMA. Referring to section III, let Sym(Z_N]S₃) denote the group of all permutations of the underlying set of the split extension Z_N]S₃of lemma 4. Then S₃embeds in Sym(Z_N]S₃) via the Cayley right regular representation.

PROOF: Note that S₃ = {(0, α)|α∈S₃} is a subgroup of Z_N]S₃. Since S₃ embeds in Sym(S₃) via the Cayley right regular representation α → R(α) and Sym(S₃) is a subgroup of Sym(Z_N]S₃), the lemma follows. ☐

8. LEMMA. By lemma 7, regard S₃ as a subgroup of Sym(Z_N]S₃). There exists a common system of coset representatives φ₁, ..., φ_ksuch that {φ₁S₃, ..., φ_kS₃} is the family of left cosets of S₃ in Sym(Z_N]S₃) and {S₃φ₁, ..., S₃φ_k} is the family of right cosets of S₃ in Sym(Z_N]S₃).

PROOF: By Lagrange's theorem the left cosets of S₃ partition Sym(Z_N]S₃) into k = [Sym(Z_N]S₃):S₃] disjoint nonempty equivalence classes of size |S₃| = 6. The same is true of the right cosets. Define a bipartite graph Γ with vertices X∪Y where X = {ψ₁S₃, ..., ψ_kS₃} is the family of left cosets of S₃ in Sym(Z_N]S₃) and Y = {S₃ψ'₁, ..., S₃ψ'_k} is the family of right cosets of S₃ in Sym(Z_N]S₃) with an edge {ψ_iS₃, S₃ψ'_j} if and only if ψ_iS₃ and S₃ψ'_j have nonempty intersection. Note that we can select representatives of the left cosets that belong to distinct right cosets [see a proof of this fact]. For any subset A = {ψi₁S₃, ..., ψi_rS₃} of X, one has ψi₁∈ψi₁S₃, ..., ψi_r∈ψi_rS₃ and there exist distinct j₁, ..., j_r such that ψi₁∈S₃ψ'j₁, ..., ψi_r∈S₃ψ'j_r. Hence, in the graph Γ, |adj(A)| ≥ |A|. Hall's hypothesis of lemma 6 is satisfied and there exists a complete matching from X to Y in Γ. This is precisely the statement that a common system of coset representatives φ₁, ..., φ_k exists. ☐

Let C denote the complex plane. Consider the function C → C; z → w = zⁿ, where n ≥ 2. There is a one-to-one correspondence between each sector

{z|(k-1)2π/n < arg z < k2π/n} (k = 1, ..., n)

and the whole w-plane except for the positive real axis. The image of each sector is obtained by performing a cut along the positive real axis; this cut has an upper and a lower edge. Corresponding to the n sectors in the z-plane, take n identical copies of the w-plane with the cut. These will be the sheets of the Riemann surface and are distinguished by a label k which serves to identify the corresponding sector. For k = 1, ..., n-1 attach the lower edge of the sheet labeled k with the upper edge of the sheet labeled k+1. To complete the cycle, attach the lower edge of the sheet labeled n to the upper edge of the sheet labeled 1. In a physical sense, this is not possible without self-intersection but the idealized model shall be free of this discrepancy. The result of the construction is a Riemann surface whose points are in one-to-one correspondence with the points of the z-plane [see a geometric model]. This correspondence is continuous in the following sense. When z moves in its plane, the corresponding point w is free to move on the Riemann surface. The point w = 0 connects all the sheets and is called the branch point. A curve must wind n times around the branch point before it closes. Now consider the n-valued relation

z = ⁿ√w.

To each w ≠ 0, there correspond n values of z. If the w-plane is replaced by the Riemann surface just constructed, then each complex number w ≠ 0 is represented by n points of the Riemann surface at superposed positions. Let the point on the uppermost sheet represent the principal value and the other n-1 points represent the other values. Then z = ⁿ√w becomes a single-valued, continuous, one-to-one correspondence of the points of the Riemann surface with the points of the z-plane. Now recall the definition of the map m(N) from section I. The map m(N) is on the sphere. Pick a region and deform the sphere so that both 0 and ∞ are two distinct points inside this region when the sphere is regarded as the extended complex plane. Using the stereographic projection one obtains the map m(N) on the complex plane C with the region containing 0 and ∞ forming a ''sea'' surrounding the other regions which form an ''island''. Put this copy of C on each sheet of the Riemann surface corresponding to w = zⁿ. The branch point lies in the ''sea''. The inverse function z = ⁿ√w results in n copies of the map m(N) on the z-plane in the sectors

{z|(k-1)2π/n < arg z < k2π/n} (k = 1, ..., n).

The origin of the z-plane lies in the n ''seas''.


z-plane	w = z⁴ Riemann surface
Figure 2. An example with n = 4

Referring to section III, the full symmetric group Sym(Z_N]S₃) acts faithfully on the set Z_N]S₃. The action of an element ψ of Sym(Z_N]S₃) on an element (m, α) of Z_N]S₃ will be written as (m, α)ψ. This action extends to the integral group algebra Z(Z_N]S₃) by linearity

(	Σ	n_{(m, α)}(m, α)	)	ψ	=	Σ	n_{(m, α)}((m, α)ψ)	.
	(m, α)∈Z_N]S₃					(m, α)∈Z_N]S₃

Referring to lemma 8, fix a common coset representative φ_i of S₃ in Sym(Z_N]S₃) and fix a pair (β, γ)∈S₃×S₃= Mlt(S₃). There are two cases depending on whether β = γ or whether β ≠ γ.

CASE 1. Suppose β ≠ γ. Consider the composition of the functions

C → C; z → t = z² and C → C; t → w = t¹².

The composite is given by the assignment

z → t = z² → w = t¹²= z²⁴.

There are twenty-four superposed copies of the map m(N) on the w-Riemann surface corresponding to the sectors

{z|(k-1)2π/24 < arg z < k2π/24} (k = 1, ..., 24)

on the z-plane. These are divided into two sets. The first set consists of twelve superposed copies of the map m(N) corresponding to the sectors

{z|(k-1)2π/24 < arg z < k2π/24} (k = 1, ..., 12)

of the upper half of the z-plane which comprise the upper sheet of the t-Riemann surface. The second set consists of twelve superposed copies of the map m(N) corresponding to the sectors

{z|(k-1)2π/24 < arg z < k2π/24} (k = 13, ..., 24)

of the lower half of the z-plane which comprise the lower sheet of the t-Riemann surface.

Figure 3. Sheets of the t-Riemann surface

Label the twelve sectors of the upper sheet of the t-Riemann surface by elements of Z(Z_N]S₃)]ZS₃ as shown:

Figure 4. Upper sheet of the t-Riemann surface

Label the twelve sectors of the lower sheet of the t-Riemann surface by elements of Z(Z_N]S₃)]ZS₃ as shown:

Figure 5. Lower sheet of the t-Riemann surface

Referring to section II, the regions of the map m(N) have been partitioned into disjoint, nonempty equivalence classes 0, 1, ..., N-1 and this set of equivalence classes forms the underlying set of the cyclic group Z_N. Hence there are twelve copies of Z_N on the upper sheet and twelve copies of Z_N on the lower sheet of the t-Riemann surface. The copies of Z_N are indexed by the elements of Z(Z_N]S₃)]ZS₃ which label the sectors on a particular sheet. The branch point of the t-Riemann surface is labeled by the element (0, β+γ) of Z(Z_N]S₃)]ZS₃ where 0 denotes the zero element of Z(Z_N]S₃).

9. LEMMA. Referring to lemma 8, fix a common representative φ_iof the left and right cosets of S₃ in Sym(Z_N]S₃). Fix a pair (β, γ)∈S₃×S₃with β ≠ γ. Referring to lemma 5, define a subset T_(β,
γ)of Z(Z_N]S₃)]ZS₃as follows:

T_{(β, γ)} =	{((m, α), β+γ)\|(m, α)∈Z_N]S₃}
	∪
	{(0, β+γ)}
	∪
	{(-(m, α), β+γ)\|(m, α)∈Z_N]S₃}	.

Referring to the preceding discussion, consider the composite function

z → t = z² → w = t¹²= z²⁴

of the complex z-plane to the w-Riemann surface. There is a copy of the set T_(β,
γ)on the upper sheet and a copy of the set T_(β,
γ)on the lower sheet of the t-Riemann surface according to the labels of the sectors in figures 4 and 5 with the branch point labeled by the element (0, β+γ) of both copies. The rotation of the z-plane by π radians induces a permutation

p: T_{(β, γ)} → T_(β,
γ)

given by

(-(m, α)R(γ)φ_i, β+γ)p	=	((m, α)φ_iR(γ), β+γ)
(0, β+γ)p	=	(0, β+γ)
((m, α)φ_iR(β), β+γ)p	=	(-(m, α)R(β)φ_i, β+γ)

for all (m, α)∈Z_N]S₃, such that each point of the copy of T_(β,
γ)on the upper sheet moves continuously along a circular curve that winds exactly once around the branch point, to the point superposed directly below it on the copy of T_(β,
γ)on the lower sheet of the t-Riemann surface.

PROOF: T_{(β, γ)} is seen to be a well-defined subset of Z(Z_N]S₃)]ZS₃ by setting the appropriate coefficients to zero in a typical element as described in lemma 5. Each of R(γ)φ_i, φ_iR(γ), φ_iR(β), R(β)φ_i are permutations of the set Z_N]S₃ and the rotation of the z-plane by π radians clearly induces a permutation p of the set T_(β,
γ) as described. ☐

10. LEMMA. Referring to lemma 9, let Sym(T_(β,
γ)) denote the full permutation group of the set T_(β,
γ). Let denote the cyclic subgroup of Sym(T_(β,
γ)) generated by p. Then is nontrivial and acts faithfully on the set T_(β,
γ).

PROOF: If p = 1, then (-(0,1)R(γ)φ_i, β+γ) = (-(0,1)R(γ)φ_i, β+γ)p = ((0,1)φ_iR(γ), β+γ) which implies that -(0,1)R(γ)φ_i= (0,1)φ_iR(γ) in Z(Z_N]S₃). This is impossible since 1 ≠ -1 in Z. Hence p ≠ 1. Since the full permutation group Sym(T_{(β, γ)}) acts faithfully on T_{(β, γ)}, so does its subgroup . ☐

11. LEMMA. Referring to lemma 9 and lemma 10, let 1: C → C; z → z denote the identity and π: C → C; z → -z denote the rotation through an angle of π radians of the z-plane. Then the two-element cyclic group {1, π} acts faithfully on the set as follows: pⁿ1 = pⁿand pⁿπ = p^1-n, for all n in Z.

PROOF: The set {1, π} forms a two-element cyclic group < π > under function composition. To show that {1, π} acts on as defined, observe that (pⁿπ)π = (p^1-n)π = p^1-(1-n) = p^1-1+n = pⁿ = pⁿ1 = pⁿ(ππ), for all n in Z. To show that the action is faithful, let θ∈{1, π}. If θ belongs to the kernel of the action then pⁿθ = pⁿ for all n in Z so that pθ = p which implies that θ = 1, since p ≠ 1 by lemma 10. ☐

12. LEMMA. Putting together lemma 9, lemma 10 and lemma 11, there is a well-defined action of the two-element cyclic group {1, π} on the set T_(β,
γ)given by

((m, α)φ_iR(γ), β+γ)1	=	((m, α)φ_iR(γ), β+γ)
(0, β+γ)1	=	(0, β+γ)
(-(m, α)R(β)φ_i, β+γ)1	=	(-(m, α)R(β)φ_i, β+γ)

and

((m, α)φ_iR(γ), β+γ)π	=	(-(m, α)R(γ)φ_i, β+γ)
(0, β+γ)π	=	(0, β+γ)
(-(m, α)R(β)φ_i, β+γ)π	=	((m,α)φ_iR(β), β+γ)

for all (m, α) in Z_N]S₃. This action is faithful.

PROOF: For each x∈T_(β,
γ), let Orb(x) = {xpⁿ|n∈Z} denote the orbit of x under . The collection {Orb(x)|x∈T_(β,
γ)} forms a partition of the set T_(β,
γ) as follows. Let x, y∈T_(β,
γ). If z∈Orb(x)∩Orb(y) then z = xpⁿ = yp^m for some m, n∈Z. This implies xpⁿ^-m= y ⇒ y∈Orb(x) ⇒ Orb(y)⊆Orb(x) and yp^m^-n= x ⇒ x∈Orb(y) ⇒ Orb(x)⊆Orb(y). Hence Orb(x) = Orb(y). Also each x∈T_(β,
γ) belongs to an orbit, namely x∈Orb(x). Hence the orbits are disjoint, nonempty and their union is all of the set T_(β,
γ). For each fixed x∈T_(β,
γ) define

π: Orb(x) → Orb(x); (xpⁿ)π = xp^1-n.

Then π is well-defined, since xpⁿ= xp^m⇒ xp^n-m= x ⇒ xp^-m= xp^-n⇒ xp^1-m= xp^1-n⇒ (xpⁿ)π = (xp^m)π. Also, π is a permutation of Orb(x) with π²= 1, since for each xpⁿ∈Orb(x) we have ((xpⁿ)π)π = (xp^1-n)π = xp^1-(1-n) = xpⁿ. Now define

π: T_(β,
γ) → T_(β,
γ); (xpⁿ)π = xp^1-n

orbit by orbit. Then, since {Orb(x)|x∈T_(β,
γ)} forms a partition of T_(β,
γ), π is a well-defined permutation of T_(β,
γ) with π²= 1, the identity permutation of T_(β,
γ). Hence, using the definition of p in lemma 9, we obtain an action of the two-element cyclic group {1, π} on T_(β,
γ) as follows. For all (m, α) in Z_N]S₃ define

((-(m, α)R(γ)φ_i, β+γ)p)1	=	(-(m, α)R(γ)φ_i, β+γ)p
((0, β+γ)p)1	=	(0, β+γ)p
(((m, α)φ_iR(β), β+γ)p)1	=	((m, α)φ_iR(β), β+γ)p

and

((-(m, α)R(γ)φ_i, β+γ)p)π	=	(-(m, α)R(γ)φ_i, β+γ)
((0, β+γ)p)π	=	(0, β+γ)
(((m, α)φ_iR(β), β+γ)p)π	=	((m, α)φ_iR(β), β+γ).

Now, using the definition of p in lemma 9, the action of {1, π} on T_(β,
γ) may be rewritten

((m, α)φ_iR(γ), β+γ)1	=	((m, α)φ_iR(γ), β+γ)
(0, β+γ)1	=	(0, β+γ)
(-(m, α)R(β)φ_i, β+γ)1	=	(-(m, α)R(β)φ_i, β+γ)

and

((m, α)φ_iR(γ), β+γ)π	=	(-(m, α)R(γ)φ_i, β+γ)
(0, β+γ)π	=	(0, β+γ)
(-(m, α)R(β)φ_i, β+γ)π	=	((m, α)φ_iR(β), β+γ)

for all (m, α) in Z_N]S₃, as in the statement of this lemma. To verify that the action of {1, π} on T_{(β, γ)} is faithful, note that

1: T_{(β, γ)} → T_(β,
γ); x → x

π: T_(β,
γ) → T_(β,
γ); x → xπ

are permutations of the set T_(β,
γ). If θ∈{1, π}and θ belongs to the kernel of the action then xθ = x for all x∈T_(β,γ). Then θ = 1, since π moves ((0, 1)φ_iR(γ), β+γ) to (-(0, 1)R(γ)φ_i, β+γ) which are distinct elements of Z(Z_N]S₃)]ZS₃. ☐

CASE 2. Suppose β = γ. Note that in the labeling of the sectors of the sheets of the t-Riemann surface in figures 4 and 5, R(β) = R(γ) and β+γ = 2β in the group algebra ZS₃.

13. LEMMA. Referring to lemma 8, fix a common representative φ_iof the left and right cosets of S₃ in Sym(Z_N]S₃). Fix a pair (β, β)∈S₃×S₃. Referring to lemma 5, define a subset T_(β,
β)of Z(Z_N]S₃)]ZS₃as follows:

T_{(β, β)} =	{((m, α), 2β)\|(m, α)∈Z_N]S₃}
	∪
	{(0, 2β)}
	∪
	{(-(m, α), 2β)\|(m, α)∈Z_N]S₃}	.

Referring to the preceding discussion, consider the composite function

z → t = z² → w = t¹²= z²⁴

of the complex z-plane to the w-Riemann surface. There is a copy of the set T_(β,
β)on the upper sheet and a copy of the set T_(β,
β)on the lower sheet of the t-Riemann surface according to the labels of the sectors in figures 4 and 5. Note that in this case R(β) = R(γ) and β+γ = 2β with the branch point labeled by the element (0, 2β) of both copies. The rotation of the z-plane by π radians induces a permutation

p: T_{(β, β)} → T_(β,
β)

given by

(-(m, α)R(β)φ_i, 2β)p	=	((m, α)φ_iR(β), 2β)
(0, 2β)p	=	(0, 2β)
((m, α)φ_iR(β), 2β)p	=	(-(m, α)R(β)φ_i, 2β)

for all (m, α)∈Z_N]S₃, such that each point of the copy of T_(β,
β)on the upper sheet moves continuously along a circular curve that winds exactly once around the branch point, to the point superposed directly below it on the copy of T_(β,
β)on the lower sheet of the t-Riemann surface. Then p = p^-1so that = {1, p} is a two-element cyclic subgroup of the full permutation group Sym(T_{(β, β)}) and acts faithfully on the set T_{(β, β)}.

PROOF: As in the proof of lemma 9, T_(β,
β) is seen to be a well-defined subset of Z(Z_N]S₃)]ZS₃ by setting the appropriate coefficients to zero in a typical element as described in lemma 5. Both φ_iR(β), R(β)φ_i are permutations of the set Z_N]S₃ and the rotation of the z-plane by π radians clearly induces a permutation p of the set T_(β,
β) as described. Furthermore, it is clear from the definition that p = p^-1 by chasing elements of T_(β,
β). Then = {1, p} as a subgroup of Sym(T_(β,
β)) and acts faithfully on the set T_(β,
β). ☐

14. LEMMA. Referring to lemma 13, let 1: C → C; z → z denote the identity and π: C → C; z → -z denote the rotation through an angle of π radians of the z-plane. Then there is a well-defined action of the two-element cyclic group {1, π} on the set T_(β,
β)given by

((m, α)φ_iR(β), 2β)1	=	((m, α)φ_iR(β), 2β)
(0, 2β)1	=	(0, 2β)
(-(m, α)R(β)φ_i, 2β)1	=	(-(m, α)R(β)φ_i, 2β)

and

((m, α)φ_iR(β), 2β)π	=	(-(m, α)R(β)φ_i, 2β)
(0, 2β)π	=	(0, 2β)
(-(m, α)R(β)φ_i, 2β)π	=	((m, α)φ_iR(β), 2β)

for all (m, α) in Z_N]S₃. This action is faithful.

PROOF: The isomorphism 1 → 1, p → π of the two-element cyclic groups {1, p} and {1, π} establishes the lemma. ☐

RÉSUMÉ. Let us review the final goal. Recall the definition made in section I. We have defined N to be the minimal number of colours required to properly colour any map from the class of all maps on the sphere. We know that 4 ≤ N ≤ 6. We have chosen a specific map m(N) on the sphere which requires all of the N colours 0, 1, ..., N-1 to properly colour it. The map m(N) has been properly coloured and the regions of m(N) partitioned into disjoint, nonempty equivalence classes 0, 1, ..., N-1 according to the colour they receive. The set {0, 1, ..., N-1} is endowed with the structure of the cyclic group Z_N under addition modulo N. In section III we have built the split extension Z_N]S₃. The underlying set Z_N]S₃ of cardinality 6N is taken to be the point set of a Steiner system S(N+1, 2N, 6N) which will be constructed in this section. We are required to define the blocks of size 2N and show that every set of N+1 points is contained in a unique block. Once this goal is achieved, lemma 3 shows that N ≤ 4.

15. LEMMA. Let Z_N]S₃denote the split extension defined in lemma 4 and Sym(Z_N]S₃) denote the full permutation group on the set Z_N]S₃. Define

μ: Sym(Z_N]S₃) → Sym(Z_N]S₃)

ψ = R(γ)φ_i → φ_iR(γ) = ψ^μ.

Then μ is a bijection of the set Sym(Z_N]S₃) with itself.

PROOF: Referring to lemma 8, μ is well-defined since each ψ∈Sym(Z_N]S₃) may be written uniquely as ψ = R(γ)φ_i for some γ∈S₃ and some φ_i. Then μ is a surjection because for any ψ∈Sym(Z_N]S₃) one may also write ψ = φ_iR(γ) uniquely for some γ∈S₃ and some φ_i, whence R(γ)φ_i → φ_iR(γ) = ψ. Since Sym(Z_N]S₃) is a finite set, μ must be a bijection by counting. ☐

16. LEMMA. Define the set G as follows:

{

(

ψ^μ

)

ψ∈Sym(Z_N]S₃)

}

{

(

R(γ)φ_i

φ_iR(γ)

)

γ∈S₃

i = 1, ..., k

}

Define multiplication in G as follows:

(

ψ₁

ψ₁^μ

)

(

ψ₂

ψ₂^μ

)

(

(ψ₁ψ₂)

(ψ₁ψ₂)^μ

)

i.e.

(

R(γ₁)φi₁

φi₁R(γ₁)

)

(

R(γ₂)φi₂

φi₂R(γ₂)

)

(

R(γ₃)φi₃

φi₃R(γ₃)

)

where R(γ₃)φi₃ is the unique expression for R(γ₁)φi₁R(γ₂)φi₂ according to the right coset decomposition of S₃ in Sym(Z_N]S₃). Then G is a group.

PROOF: Referring to lemma 8 and lemma 15, the set G is well-defined by the decomposition of Sym(Z_N]S₃) into the left and right cosets of S₃ by the φ_i. Define

μ': Sym(Z_N]S₃) → G ; ψ →

(

ψ^μ

)

Then μ' is a well-defined bijection of the set Sym(Z_N]S₃) with G since μ is a bijection by lemma 15. The definition of multiplication in G mirrors the multiplication in Sym(Z_N]S₃) via μ' and is designed to make G a group and μ' an isomorphism. ☐

17. LEMMA. Consider the set Z_N]S₃and let

(

ψ^μ

)

(

R(γ)φ_i

φ_iR(γ)

)

∈G.

Define

↑

(

ψ^μ

)

: Z_N]S₃ → Z_N]S₃ by

(m, α) → (m, α)

↑

(

ψ^μ

)

(m, α)

↑

(

R(γ)φ_i

φ_iR(γ)

)

= (m, α)R(γ)φ_i.

Define

↓

(

ψ^μ

)

: Z_N]S₃ → Z_N]S₃ by

(m, α) → (m, α)

↓

(

ψ^μ

)

(m, α)

↓

(

R(γ)φ_i

φ_iR(γ)

)

= (m, α)φ_iR(γ).

Then

(m, α)

↑

(

ψ^μ

)

(m, α)

↓

(

ψ^μ

)

for all (m, α)∈Z_N]S₃.

Both ↑ and ↓ are well-defined, faithful and |Z_N]S₃|-transitive right actions of the group G on the set Z_N]S₃.

PROOF: Referring to lemma 12 and lemma 14, put β = 1. Working in the set T_{(1, γ)}, for each (m, α)∈Z_N]S₃ we have

( (m, α) ↓ (

ψ

ψ^μ

) , 1+γ )

= ( (m, α) ↓ (

R(γ)φ_i

φ_iR(γ)

) , 1+γ )

= ( (m, α) φ_iR(γ) , 1+γ )

= ( -(m, α) R(γ)φ_i , 1+γ ) π

= ( -(m, αγ) φ_i , 1+γ ) π

= ( -(m, αγ) R(1)φ_i , 1+γ ) π

= ( (m, αγ) φ_iR(1) , 1+γ )

= ( (m, αγ) φ_i , 1+γ )

= ( (m, α) R(γ)φ_i , 1+γ )

= ( (m, α) ↑ (

R(γ)φ_i

φ_iR(γ)

) , 1+γ )

= ( (m, α) ↑ (

ψ

ψ^μ

) , 1+γ )

using the action of the two-element cyclic group {1, π} on the set T_{(1, γ)} according to lemma 12 and lemma 14. Hence

(m, α)

↑

(

ψ^μ

)

(m, α)

↓

(

ψ^μ

)

for all (m, α)∈Z_N]S₃.

Since the action ↑ is the usual action of Sym(Z_N]S₃) on the set Z_N]S₃, it is faithful and |Z_N]S₃|-transitive. By the last equality, so is the ↓ action. ☐

18. LEMMA. Let (m₁, α₁), ..., (m_r, α_r) be any r distinct elements of Z_N]S₃ and let (n₁, β₁), ..., (n_s, β_s) be any s distinct elements of Z_N]S₃. Let

H_{r, s}

{

(

ψ^μ

)

∈G

(m_i, α_i)

↑

(

ψ^μ

)

= (m_i, α_i) for i = 1, ..., r and

(n_j, β_j)

↓

(

ψ^μ

)

= (n_j, β_j) for j = 1, ..., s

}

then H_{r, s} is a subgroup of G.

PROOF: Note that if ψ = R(γ)φ_i= 1 then φ_i= R(γ)^-1 so that ψ^μ= φ_iR(γ) = R(γ)^-1R(γ) = 1. Then

(

1^μ

)

∈H_{r, s}

since

(m_i, α_i)

↑

(

1^μ

)

= (m_i, α_i)1 = (m_i, α_i)

for i = 1, ..., r and

(n_j, β_j)

↓

(

1^μ

)

= (n_j, β_j)1^μ = (n_j, β_j)1 = (n_j, β_j)

for j = 1, ..., s. If

(

ψ₁

ψ₁^μ

)

and

(

ψ₂

ψ₂^μ

)

∈H_{r, s}

then

(m_i, α_i)

↑

(

ψ₁

ψ₁^μ

)

(

ψ₂

ψ₂^μ

)

= (m_i, α_i)

↑

(

ψ₁

ψ₁^μ

)

↑

(

ψ₂

ψ₂^μ

)

= (m_i, α_i)

↑

(

ψ₂

ψ₂^μ

)

= (m_i, α_i) for i = 1, ..., r

and

(n_j, β_j)

↓

(

ψ₁

ψ₁^μ

)

(

ψ₂

ψ₂^μ

)

= (n_j, β_j)

↓

(

ψ₁

ψ₁^μ

)

↓

(

ψ₂

ψ₂^μ

)

= (n_j, β_j)

↓

(

ψ₂

ψ₂^μ

)

= (n_j, β_j) for j = 1, ..., s.

Hence

(

ψ₁

ψ₁^μ

)

(

ψ₂

ψ₂^μ

)

∈H_{r, s}

Since G is finite, H_{r, s} is a subgroup of G. ☐

Note that Z_N is embedded as the subgroup {(m, 1)|m∈Z_N} in Z_N]S₃ and S₃ is embedded as the subgroup {(0, α)|α∈S₃} in Z_N]S₃. Since Z_N]S₃ = Z_N×S₃ is the direct product of groups by lemma 4, both Z_N and S₃ are normal subgroups. Recall the notation

S₃ = < σ, ρ > = {1, ρ, ρ², σ, σρ, σρ²}.

19. LEMMA. Define

{

(

ψ^μ

)

∈G

(m, 1)

↑

(

ψ^μ

)

= (m, 1) for all m∈Z_N and

(0, σ)

↓

(

ψ^μ

)

= (0, σ)

}

Then given

(

ψ^μ

)

∈H

either

(m, α)

↓

(

ψ^μ

)

= (m, α) for all (m, α)∈Z_N]S₃

(m, α)

↓

(

ψ^μ

)

= (m, α^σ) for all (m, α)∈Z_N]S₃.

PROOF: H is a well-defined subgroup of G according to lemma 18. Let

(

ψ^μ

)

(

R(γ)φ_i

φ_iR(γ)

)

∈H

and (m, α)∈Z_N]S₃ be given. Referring to lemmas 12 and 14, put β = γ^-1αγ. Working in the set T_{(β, γ)} we have

( (m, α) ↓ (

ψ

ψ^μ

) , β+γ )

= ( (m, α) ↓ (

R(γ)φ_i

φ_iR(γ)

) , β+γ )

= ( (m, α) φ_iR(γ) , β+γ )

= ( -(m, α) R(γ)φ_i , β+γ ) π

= ( -(m, αγ) φ_i , β+γ ) π

= ( -(m, γβ) φ_i , β+γ ) π

= ( -(m, γ) R(β)φ_i , β+γ ) π

= ( (m, γ) φ_iR(β) , β+γ )

= ( (m, 1) R(γ)φ_iR(β) , β+γ )

= ( (m, 1) R(β) , β+γ )

= ( (m, β) , β+γ )

using the definition of H and the action of the two-element cyclic group {1,π} on the set T_(β,γ). Hence

(m, α)

↓

(

ψ^μ

)

= (m, β) = (m, γ^-1αγ) = (m, α^γ).

Now since

(0, σ) = (0, σ)

↓

(

ψ^μ

)

= (0, σ^γ)

by hypothesis, we have σ = σ^γ. Hence γσ = σγ so that either γ = 1 or γ = σ. ☐

20. LEMMA. Let H be the subgroup of G defined in lemma 19. Then H is a nontrivial group of involutions of the set Z_N]S₃. In particular, every nontrivial element of H is of order 2.

PROOF: Define

ψ: Z_N]S₃ → Z_N]S₃; (m, α) → (m, α^σ).

Then

(m, 1)

↑

(

ψ^μ

)

= (m, 1)ψ = (m, 1^σ) = (m, 1) for all m∈Z_N

and

(0, σ)

↓

(

ψ^μ

)

(0, σ)

↑

(

ψ^μ

)

= (0, σ)ψ = (0, σ^σ) = (0, σ).

Now ψ ≠ 1, so

(

1^μ

)

≠

(

ψ^μ

)

∈H,

hence H is nontrivial. To show that each nontrivial element of H is of order 2, let

(

ψ^μ

)

(

R(γ)φ_i

φ_iR(γ)

)

∈H.

Then by the proof of lemma 19, γ = 1 or γ = σ. In particular γ² = 1. Hence, for any (m, α)∈Z_N]S₃

(m, α) ↓ (

R(γ)φ_i

φ_iR(γ)

) ²

= (m, α) ↓ (

R(γ)φ_i

φ_iR(γ)

) ↓ (

R(γ)φ_i

φ_iR(γ)

)

= (m, α^γ) ↓ (

R(γ)φ_i

φ_iR(γ)

)

= (m, (α^γ)^γ) = (m, α). Since the ↓ action of G on the set Z_N]S₃ is faithful,

(

R(γ)φ_i

φ_iR(γ)

)

(

1^μ

)

the identity element of G. ☐

21. LEMMA. Denote the right cosets of Z_N in Z_N]S₃ by

Z_N, Z_Nρ, Z_Nρ², Z_Nσ, Z_Nσρ, Z_Nσρ².

Define

Fix↓(H) =

{

(m, α)∈Z_N]S₃

(m, α)

↓

(

ψ^μ

)

(m, α)

for all

(

ψ^μ

)

∈H

}

Then Fix↓(H) = {(m, α)∈Z_N]S₃|α = 1 or α = σ}. The ↓ action of a nontrivial element of H transposes the coset Z_Nρ with the coset Z_Nρ²and transposes the coset Z_Nσρ with the coset Z_Nσρ².

PROOF: By lemmas 19 and 20, the elements

(

ψ^μ

)

∈H

are of two kinds:

(i) (m, α) ↓ (

ψ

ψ^μ

) = (m, α) for all (m, α)∈Z_N]S₃

in which case

(

ψ^μ

)

(

1^μ

)

the identity element of H, and

(ii) (m, α) ↓ (

ψ

ψ^μ

) = (m, α^σ) for all (m, α)∈Z_N]S₃

in which case

(

1^μ

)

≠

(

ψ^μ

)

is an element of order 2 in H. In the second case, compute according to the cosets of Z_N in Z_N]S₃:

(m, 1) ↓ (

ψ

ψ^μ

) = (m, 1^σ) = (m, 1) for all m∈Z_N

(m, σ) ↓ (

ψ

ψ^μ

) = (m, σ^σ) = (m, σ) for all m∈Z_N

(m, ρ) ↓ (

ψ

ψ^μ

) = (m, ρ^σ) = (m, ρ²) for all m∈Z_N

(m, ρ²) ↓ (

ψ

ψ^μ

) = (m, (ρ²)^σ) = (m, ρ) for all m∈Z_N

(m, σρ) ↓ (

ψ

ψ^μ

) = (m, (σρ)^σ) = (m, σρ²) for all m∈Z_N

(m, σρ²) ↓ (

ψ

ψ^μ

) = (m, (σρ²)^σ) = (m, σρ) for all m∈Z_N

and the lemma follows. ☐

22. LEMMA. Let Norm_G(H) denote the normalizer of H in G. The action ↓ of G on Z_N]S₃restricts to an action ↓ of Norm_G(H) on Fix↓(H) which is (|Z_N|+1)-transitive.

PROOF: Let

(

ψ^μ

)

∈G.

First show that

Fix↓

(

ψ^μ

)

^-1

(

ψ^μ

)

= Fix↓(H)

↓

(

ψ^μ

)

as follows:

(m, α)∈Fix↓ ( (

ψ

ψ^μ

) ^-1 H (

ψ

ψ^μ

) )

⇔ (m, α)↓ ( (

ψ

ψ^μ

) ^-1 (

ψ^*

ψ^*μ

) (

ψ

ψ^μ

) ) = (m, α) for all (

ψ^*

ψ^*μ

) ∈H

⇔ (m, α)↓ ( (

ψ

ψ^μ

) ^-1 (

ψ^*

ψ^*μ

) ) = (m, α)↓ (

ψ

ψ^μ

) ^-1 for all (

ψ^*

ψ^*μ

) ∈H

⇔ (m, α)↓ (

ψ

ψ^μ

) ^-1 ↓ (

ψ^*

ψ^*μ

) = (m, α)↓ (

ψ

ψ^μ

) ^-1 for all (

ψ^*

ψ^*μ

) ∈H

⇔ (m, α)↓ (

ψ

ψ^μ

) ^-1 ∈Fix↓(H)

⇔ (m, α)∈Fix↓(H)↓ (

ψ

ψ^μ

) .

Now let

(

ψ^μ

)

∈Norm_G(H) =

{

(

ψ^μ

)

∈G

(

ψ^μ

)

^-1

(

ψ^μ

)

= H

}

Then

Fix↓(H) = Fix↓

(

ψ^μ

)

^-1

(

ψ^μ

)

= Fix↓(H)↓

(

ψ^μ

)

showing that the action restricts to an action of Norm_G(H) on Fix↓(H). Now to show that the action ↓ of Norm_G(H) on Fix↓(H) = Z_N∪Z_Nσ is (|Z_N|+1)-transitive, label the elements of Z_N as (m₁, α₁), ..., (m_N, α_N) and label (0, σ) = (m_N₊₁, α_N+1). Let (m^*₁, α^*₁), ..., (m^*_N+1, α^*_N+1) be any |Z_N|+1 distinct points of Fix↓(H). It is enough to show that there exists

(

ψ^μ

)

∈Norm_G(H)

such that

(m^*_i, α^*_i)

↓

(

ψ^μ

)

= (m_i, α_i) for i = 1, ..., N+1.

Now there exists

(

ψ^μ

)

∈G

such that

(m^*_i, α^*_i)

↓

(

ψ^μ

)

= (m_i, α_i) for i = 1, ..., N+1.

Hence

(m^*_i, α^*_i) = (m_i, α_i)

↓

(

ψ^μ

)

^-1

for i = 1, ..., N+1.

Note that for every

(

ψ^*

ψ^*μ

)

∈H

and for i = 1, ..., N+1:

(m_i, α_i)↓ ( (

ψ

ψ^μ

) ^-1 (

ψ^*

ψ^*μ

) (

ψ

ψ^μ

) )

= (m_i, α_i)↓ (

ψ

ψ^μ

) ^-1 ↓ (

ψ^*

ψ^*μ

) ↓ (

ψ

ψ^μ

)

= (m^*_i, α^*_i) ↓ (

ψ^*

ψ^*μ

) ↓ (

ψ

ψ^μ

)

= (m^*_i, α^*_i) ↓ (

ψ

ψ^μ

)

= (m_i, α_i).

Hence

(

ψ

ψ^μ

) ^-1 (

ψ^*

ψ^*μ

) (

ψ

ψ^μ

) ∈H for all (

ψ^*

ψ^*μ

) ∈H ⇒ (

ψ

ψ^μ

) ∈Norm_G(H). ☐

23. LEMMA. There exists a Steiner system S(N+1, 2N, 6N ), where the points are the elements of the set Z_N]S₃and the set of blocks is

{

Fix↓(H)↓

(

ψ^μ

)

(

ψ^μ

)

∈G

}

PROOF: There are 6N = |Z_N]S₃| points. Each block, for a fixed

(

ψ^μ

)

∈G

contains

2N = |Z_N∪Z_Nσ| = |Fix↓(H)| =

Fix↓(H)↓

(

ψ^μ

)

points. Label the elements of Z_N as (m₁, α₁), ..., (m_N, α_N) and label (0, σ) = (m_N₊₁, α_N+1). Let (m^*₁, α^*₁), ..., (m^*_N+1, α^*_N+1) be any |Z_N|+1 distinct points of Z_N]S₃. Then there exists

(

ψ^μ

)

∈G

such that

(m_i, α_i)

↓

(

ψ^μ

)

= (m^*_i, α^*_i) for i = 1, ..., N+1.

Hence, there is at least one block, namely Fix↓(H), that contains the points (m^*₁, α^*₁), ..., (m^*_N+1, α^*_N+1). It remains to show that this is the unique block that contains the points (m^*₁, α^*₁), ..., (m^*_N+1, α^*_N+1). Suppose (m^*₁, α^*₁), ..., (m^*_N+1, α^*_N+1) are contained in

Fix↓(H)↓

(

ψ^*

ψ^*μ

)

for some

(

ψ^*

ψ^*μ

)

∈G.

Then there exist points (m^**₁, α^**₁), ..., (m^**_N+1, α^**_N+1) in Fix↓(H) such that

(m^*_i, α^*_i) = (m^**_i, α^**_i)

↓

(

ψ^*

ψ^*μ

)

for i = 1, ..., N+1.

By lemma 22, there exists

(

ψ^**

ψ^**μ

)

∈Norm_G(H)

such that

(m^**_i, α^**_i) = (m_i, α_i)

↓

(

ψ^**

ψ^**μ

)

for i = 1, ..., N+1.

Hence for i = 1, ..., N+1

(m_i, α_i) ↓ (

ψ

ψ^μ

)

= (m^*_i, α^*_i)

= (m^**_i, α^**_i) ↓ (

ψ^*

ψ^*μ

)

= (m_i, α_i) ↓ (

ψ^**

ψ^**μ

) ↓ (

ψ^*

ψ^*μ

)

⇒ (m_i, α_i) = (m_i, α_i)↓ ( (

ψ^**

ψ^**μ

) (

ψ^*

ψ^*μ

) (

ψ

ψ^μ

) ^-1 ) for i = 1, ..., N+1.

Then by lemma 17

(m_i, α_i) = (m_i, α_i)↑ ( (

ψ^**

ψ^**μ

) (

ψ^*

ψ^*μ

) (

ψ

ψ^μ

) ^-1 ) for i = 1, ..., N

and

(m_N₊₁, α_N+1) = (m_N₊₁, α_N+1)↓ ( (

ψ^**

ψ^**μ

) (

ψ^*

ψ^*μ

) (

ψ

ψ^μ

) ^-1 ) .

Hence

(

ψ^**

ψ^**μ

)

(

ψ^*

ψ^*μ

)

(

ψ^μ

)

^-1

∈H.

Now H is a subgroup of Norm_G(H)

⇒ (

ψ^**

ψ^**μ

) (

ψ^*

ψ^*μ

) (

ψ

ψ^μ

) ^-1 ∈Norm_G(H)

⇒ (

ψ^*

ψ^*μ

) (

ψ

ψ^μ

) _-1 ∈ (

ψ^**

ψ^**μ

) ^-1 Norm_G(H) = Norm_G(H)

⇒ ( (

ψ^*

ψ^*μ

) (

ψ

ψ^μ

) _-1 ) H ( (

ψ^*

ψ^*μ

) (

ψ

ψ^μ

) _-1 ) _-1 = H

⇒ (

ψ^*

ψ^*μ

) (

ψ

ψ^μ

) _-1 H (

ψ

ψ^μ

) (

ψ^*

ψ^*μ

) _-1 = H

⇒ (

ψ

ψ^μ

) ^-1 H (

ψ

ψ^μ

) = (

ψ^*

ψ^*μ

) ^-1 H (

ψ^*

ψ^*μ

) .

Now, using the first fact in the proof of lemma 22

Fix↓(H)↓ (

ψ^*

ψ^*μ

)

= Fix↓ ( (

ψ^*

ψ^*μ

) ^-1 H (

ψ^*

ψ^*μ

) )

= Fix↓ ( (

ψ

ψ^μ

) ^-1 H (

ψ

ψ^μ

) )

= Fix↓(H)↓ (

ψ

ψ^μ

) .

This establishes the uniqueness of the block. ☐

24. THEOREM. Any map on the sphere can be properly coloured by using at most four colours.

PROOF: Referring to section I, we have defined N to be the minimal number of colours required to properly colour any map from the class of all maps on the sphere. Based on the definition of N, we have selected a specific map m(N) on the sphere which requires no fewer than N colours to be properly coloured. Based on the definition of the map m(N) we have selected a proper colouring of its regions using the N colours 0, 1, ..., N-1. Working with the fixed number N, the fixed map m(N), and the fixed proper colouring of the regions of the map m(N), lemma 23 has explicitly constructed a Steiner system S(N+1, 2N, 6N). Now lemma 3 implies that N cannot exceed four. ☐

A NEW PROOF OF

THE FOUR COLOUR THEOREM