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 .
- 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 covers the whole object without double-covering any part of the object. The set 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 , and a single fundamental domain x, we can construct a unique simple coloring that fulfills the following conditions:
- is the set of transformations in G that preserves the color of x.
Begin by constructing the set of all left cosets of in G: . There are a finite number of distinct cosets, so let’s enumerate them as , , , and so on up to . Only is a subgroup of G, and the others are just subsets.
Now, let’s define subsets of the fundamental domains: . Each domain in 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 is the set of transformations in G that preserve the color of x. When we apply a transformation , the final color of x is equal to the initial color of . This preserves the color of x if and only if . Thus, the set of transformations that preserve the color of x is which is just the same as the set .
Finally, we show that the pattern symmetry group P contains G. I begin with a formal definition of P: . 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 , then we can show 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 .
Given that preserves the color of x, we know that has to be a single color, and that no other domains are the same color.
For every , we require that g is also part of the pattern symmetry group P. Thus, for some number j. We know , and thus each left coset must define one of the sets . 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 .
Suppose that we have a simple coloring, and that . Let be the set of all fundamental domains that have been assigned the color k. All we need to do is choose a fundamental domain , and show that , 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 is a group.
To do this, we’re going to construct some additional sets: . Not all of these sets are groups, but it turns out that is always a group. I start with the observation that always contains the identity transformation. Next I note that if p and q are both elements of , then we have , and hence . Therefore . This is sufficient to show that is a group.
Finally, we show that , and is therefore a group. First, suppose , then p of course preserves the color of all fundamental domains in , and therefore . Next, suppose . We know that , since P contains G. According to the definition of P, that means there exists some j such that . Hence . If we consider the fundamental domain , we know that this is an element of , and we also know that it’s an element of since the transformation p preserves the color of the fundamental domain x. Since the sets are all non-overlapping, this implies that j = 1, and therefore .
Number of colors
Theorem: The number of colors is .
Proof: This follows directly from basic theorems about cosets.
The color symmetry group
Theorem: The color symmetry group C is the normal core of in G.
First let’s formally define C: . In other words, C is the intersection of all as defined earlier.
Now what we want to show is that the groups form a complete set of conjugates. Suppose we have , we can show that , for some value of j. We can conclude that , meaning that is conjugate to . I’m skipping a few steps, but it’s easy to show that all are conjugates of each other, and that no conjugate sets are left out.
Since , we can see that C is the intersection of all conjugates of . This is one of the definitions of the normal core of in G.