## 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:**

_{ }

_{Example:}

**Example:**

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.