# Symmetrical coloring theorem

This is an appendix to my series about symmetry in origami. Here I will provide a proof that my construction of symmetrical colorings works.

While I try to make the series accessible to people who do not know much about math, I don’t think there’s much point in trying to make this proof broadly accessible. This is intended as a reference for people with some experience with group theory. (You need to know about cosets at the very least.)

### Definitions

Suppose we have an object. I will define the following things:

• The shape symmetry group S is a set of transformations that preserve the object’s geometrical shape.
• The color symmetry group C is a set of transformations that preserve the object’s geometrical shape and colors.
• The pattern symmetry group P is a set of transformations that preserve the object’s geometrical shape, and permute the colors without changing their pattern. Note that $C \subseteq P \subseteq S$.
• If g is a transformation, and x is a piece of the object, then g.x is the piece of the object that we get when we apply the transformation g. This is called the action of g on x.
• x is a fundamental domain of the object with respect to group G, if $\{g.x | g \in G\}$ covers the whole object without double-covering any part of the object. The set $\{g.x | g \in G\}$ is called a fundamental domain partition (my term).
• Given a fundamental domain partition, a simple coloring is an assignment of a single color to each fundamental domain.

### The Symmetrical Coloring Theorem

Theorem: Suppose we have an object with a fundamental domain partition with respect to a group G. Given a group $P_1 \subseteq G$, and a single fundamental domain x, we can construct a unique simple coloring that fulfills the following conditions:

1. $P_1$ is the set of transformations in G that preserves the color of x.
2. $P \supseteq G$.

The construction

Begin by constructing the set of all left cosets of $P_1$ in G: $\{g P_1 | g \in G\}$. There are a finite number of distinct cosets, so let’s enumerate them as $P_1$, $P_2$, $P_3$, and so on up to $P_n$. Only $P_1$ is a subgroup of G, and the others are just subsets.

Now, let’s define subsets of the fundamental domains: $X_k = \{p.x | p \in P_k\}$. Each domain in $X_k$ is assigned the color k. And that’s it, that’s our simple coloring.

Proof that the construction works

First, note that each fundamental domain has exactly one color. This follows immediately from a well-known theorem in group theory, which says that left cosets are disjoint, and their union is the whole group.

Second, we show that $P_1$ is the set of transformations in G that preserve the color of x. When we apply a transformation $g \in G$, the final color of x is equal to the initial color of $g^{-1}.x$. This preserves the color of x if and only if $g^{-1}.x \in X_1$. Thus, the set of transformations that preserve the color of x is $\{g | g^{-1} \in P_1\}$ which is just the same as the set $P_1$.

Finally, we show that the pattern symmetry group P contains G. I begin with a formal definition of P: $P = \{s \in S | \forall X_i \exists X_j ~\mathrm{s.t.}~ s.X_i = X_j\}$. In other words, P is the set of transformations such that each color i is transformed to another color j (and j may be either identical to i or distinct from i). Suppose $s \in G$, then we can show $s.X_i = sP_i.x = P_j.x = X_j$ for some j. Here we’re using the fact that left multiplication of a left coset always produces another left coset.

Proof that the construction is unique

Obviously you can construct distinct colorings by switching your greens and blues, or something like that. When I say that the coloring is “unique”, I mean that if you have a coloring that fulfills the desired conditions, then you will always come up with the same sets $X_k$.

Given that $P_1$ preserves the color of x, we know that $X_1 = P_1.x$ has to be a single color, and that no other domains are the same color.

For every $g \in G$, we require that g is also part of the pattern symmetry group P. Thus, $g.X_1 = X_j$ for some number j. We know $g.X_1 = gP_1.x$, and thus each left coset $gP_1$ must define one of the sets $X_k$. From there the rest of the construction follows.

### Further associated theorems

Exhaustiveness of construction

Theorem: Given an object and a fundamental domain partition with respect to G, the Symmetrical Coloring Theorem can be used to construct all possible simple colorings that have $P \supseteq G$.

Proof:

Suppose that we have a simple coloring, and that $P \supseteq G$. Let $X_k$ be the set of all fundamental domains that have been assigned the color k. All we need to do is choose a fundamental domain $x \in X_1$, and show that $P_1$, the set of transformations in G that preserve the color of x, is a group. From there, we can use the Symmetrical Coloring Theorem to construct a simple coloring, and by uniqueness of that coloring, we know that it is the same coloring that we started with. The hard part is showing that $P_1$ is a group.

To do this, we’re going to construct some additional sets: $P_{i,j} = \{p \in G | p.X_i = X_j\}$. Not all of these sets are groups, but it turns out that $P_{i,i}$ is always a group. I start with the observation that $P_{i,i}$ always contains the identity transformation. Next I note that if p and q are both elements of $P_{i,i}$, then we have $p.X_i = q.X_i$, and hence $q^{-1}p.X_i = X_i$. Therefore $q^{-1}p \in P_{i,i}$. This is sufficient to show that $P_{i,i}$ is a group.

Finally, we show that $P_1 = P_{1,1}$, and is therefore a group. First, suppose $p \in P_{1,1}$, then p of course preserves the color of all fundamental domains in $X_1$, and therefore $p \in P_1$. Next, suppose $p \in P_1$.  We know that $p^{-1} \in P$, since P contains G. According to the definition of P, that means there exists some j such that $p^{-1}.X_1 = X_j$. Hence $p^{-1} \in P_{1,j}$. If we consider the fundamental domain $p^{-1}.x$, we know that this is an element of $X_j$, and we also know that it’s an element of $X_1$ since the transformation p preserves the color of the fundamental domain x. Since the sets $X_k$ are all non-overlapping, this implies that j = 1, and therefore $p \in P_{1,1}$.

Number of colors

Theorem: The number of colors is $|G|/|P_1|$.

Proof: This follows directly from basic theorems about cosets.

The color symmetry group

Theorem: The color symmetry group C is the normal core of $P_1$ in G.

Proof:

First let’s formally define C: $C = \{s \in S | \forall i ~s.X_i = X_i\}$. In other words, C is the intersection of all $P_{i,i}$ as defined earlier.

Now what we want to show is that the groups $P_{i,i}$ form a complete set of conjugates. Suppose we have $g \in G$, we can show that $g \in P_{i,j}$, for some value of j. We can conclude that $gP_{i,i}g^{-1} = P_{j,j}$, meaning that $P_{i,i}$ is conjugate to $P_{j,j}$. I’m skipping a few steps, but it’s easy to show that all $P_{i,i}$ are conjugates of each other, and that no conjugate sets are left out.

Since $P_1 = P_{1,1}$, we can see that C is the intersection of all conjugates of $P_1$. This is one of the definitions of the normal core of $P_1$ in G.