Map Systems:

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 this result, and a problem disguised as a query, are given by the 1982 research note below.

View original 1982 note.

Application: The Diamond Theorem

In the 4x4 case of the diamond theorem, we regard the four-diamond figure D at left, 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.

D

Let e denote transposition of the first two rows, f denote transposition of the last two columns, g denote transposition of the top left and bottom right quadrants, and h denote transposition of the middle two columns. Then Defgh is as at right. Note that Defgh has rotational color-interchange symmetry like that of the famed yin-yang symbol.
Defgh
Remarks on the 4x4 case:

G is isomorphic to the affine group A on the linear 4-space over GF(2). The 35 structures of the 840 = 35 x 24 G-images of D are isomorphic to the 35 lines in the 3-dimensional projective space over GF(2). Orthogonality of structures corresponds to skewness of lines. We can define sums and products so that the G-images of D generate an ideal (1024 patterns characterized by all horizontal or vertical "cuts" being uninterrupted) of a ring of 4096 symmetric patterns. There is an infinite family of such "diamond" rings, isomorphic to rings of matrices over GF(4).

For a movable JavaScript version of these 4x4 patterns, see

The Diamond 16 Puzzle.

For more on map systems in diamond theory, see

Orthogonal Latin Squares as Skew Lines.

Page last maintained Jan. 31, 2005; created Nov. 27, 2001.

Return to home page.