Finite Geometry Notes   | Home | Site Map | Author |

A Four-Color Theorem:
Function Decomposition Over a Finite Field
by Steven H. Cullinane

The proof of the diamond theorem involves the following elementary, but new and useful, result:

Every 4-coloring (i.e., every function into a 4-set) can be expressed as a sum of three 2-colorings (into GF(4)).

(Or, equivalently, as a linear combination of three 2-colorings (into GF(2) as a subfield of GF(4))).

How this works:

Let m be a map into a 4-set.

Represent the elements of the 4-set by the elements {0, 1, a, b} of the finite field GF(4), so that m becomes a map f into this field.

Define f(x,y), where x, y are elements of GF(4), as the map into GF(4) that has value 1 wherever f has value x or y, and that has value 0 elsewhere. Then

f = 1f(a,b) + af(1,b) + bf(1,a)
A modest generalization of the decomposition theorem, and a problem disguised as a query, are given by the 1982 research note below.



View original 1982 note.



The decomposition theorem's algebraic formulation above is useful for showing, for instance, that certain four-colored graphic images can form a ring under multiplication.

But in applying the decomposition theorem, we often are interested only in the partition lines separating regions colored by complementary 2-subsets of the 4-color set.

Example:

Four-color decomposition with line diagrams
Example:

Four-color decomposition applied to the 8-point binary affine space

Example:

Kohs Block Design Test illustrating four-color decomposition theorem

Kohs Block Design Test figure
illustrating the four-color decomposition theorem


Application of
Four-Color Decomposition:

The Diamond Theorem


We regard the four-diamond figure D below as a 4x4 array of two-color diagonally-divided square tiles.

Let G be the group of 322,560 permutations of these 16 tiles generated by arbitrarily mixing random permutations of rows and of columns with random permutations of the four 2x2 quadrants.

THEOREM: Every G-image of D (as at right, below) has some ordinary or color-interchange symmetry.

Example:



For an animated version, click here.

For more on how the decomposition theorem
applies to the diamond theorem, click here.

Related material:
Orthogonal Latin Squares as Skew Lines.

Page last maintained August 22, 2008; created Nov. 27, 2001.