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.)


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.


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.


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.

Leave a Reply

Your email address will not be published. Required fields are marked *