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:

$P_1$ is the set of transformations in G that preserves the color of x.
$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.

A Trivial Knot

Everything is simple except when not

Using "biology" as a cheaply made, poorly understood label by bigots

Shellshocked

Thanksgiving

ICC arrest warrant for Netanyahu and Galant is a landmark decision

I Guess I Use Social Media After All

If you can keep it

International Mens' Day?

A better masculinity, for those who don't want it

Symmetrical coloring theorem

Definitions

The Symmetrical Coloring Theorem

Further associated theorems

Leave a Reply Cancel reply