Mathematics and Such

Casual Introduction to Group Theory (3)

Posted on September 25, 2012 by limsup

Subgroups

[ This article approximately corresponds to chapter III of the group theory blog. ]

Let G be a group under operation *. If H is a subset of G, we wish to turn H into a group by inheriting the operation from G. Clearly, associativity follows for free, so it only remains to check the following.

Definition. Let H be a subset of group G. We say H is a subgroup if the following hold:

$e\in H$ ;

if $x \in H$ , then $x^{-1} \in H$ ;

if $x, y \in H$ , then $x*y \in H$ .

When that happens, we write H ≤ G.

One can check that if H satisfies these 3 properties, then (H, *) inherits a group structure from (G, *).

Note: it would seem as if we can drop the second axiom; indeed, we can just pick $x \in H$ , and by third axiom, $x^{-1} \in H$ , so by first axiom, we get $e = x*x^{-1} \in H$ . Thus, the second axiom follows from the first and third axioms and seems superfluous… or does it?

Actually, no: the empty set satisfies the first and third axioms but not the second. This causes a problem in the first line of proof since we can’t pick any element x from H. So the empty set is really the odd case out.

Exercise :

Find a subset of some group G which satisfies conditions 1 & 3 but not 2.
Prove that if G is finite, then conditions 1 & 3 imply 2.

Sometimes, it’s more convenient to replace the above three conditions by two:

Alternate Definition. Let H be a subset of group G. We say H is a subgroup if the following hold:

$H \ne \emptyset$ ;

if $x,y \in H$ , then $xy^{-1} \in H$ .

Examples

Let’s look at subgroups of the examples in the previous post.

Z has subgroups mZ for m>0, which is the set of multiples of m. Together with the trivial subgroup {0}, these are the only possible subgroups which can arise.
Q has subgroup Z.
Q* has subgroups Q*² < Q^>0 < Q*, where Q*² is the set of rational squares and Q^>0 is the set of positive rational numbers.
Z/m has subgroup k·(Z/m) for any positive divisor k of m, of order m/k. E.g. when m=12, k=3, we have Z/12 = {0, 1, …, 11} under addition mod 12, and the subgroup is {0, 3, 6, 9}.
The group (Z/m)* has subgroup comprising of the squares, e.g. if m = 21, then (Z/m)* = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20} under multiplication mod 12, and the subgroup is {1, 4, 16}.

Exercise : find the order of the subgroup of squares of (Z/m)*, where $m = 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19$ .

Next, the non-abelian cases.

If m ≤ n, we can think of S_m as a subgroup of S_n, if we let f(x) = x for $f\in S_m, x>m$ .
In the case of A₄, we have a subgroup V = {e, (1,2)(3,4), (1,3)(2,4), (1,4)(2,3)} which is abelian and isomorphic to (Z/2) × (Z/2).
If G denotes the group of symmetries of a shape A, then the set of symmetries of A fixing a vertex (or an edge, or a face) forms a subgroup.
For the group S_R comprising of all bijections R → R, the affine transformations f(x) = ax+b, (for a, b in R) form a subgroup.
In GL_n(R), the subset of matrices of determinant 1 forms a subgroup SL_n(R).

Properties of Subgroups

Naturally we wonder if the usual operations on subsets carry over here.

Intersections are ok. In order words if we have a collection { H_i } of subgroups of of G, then the intersection ∩ H_i is also a subgroup. The proof is easy so we’ll skip it.
Unions are not ok. In fact, if the union of two subgroups is a subgroup, then one is contained in the other. This is not really important but a curious fact to know.

In particular, if we have any subset S of G, then we consider the class of all subgroups of G containing S. The intersection of all these subgroups is then a subgroup which contain S. We call this the subgroup of G generated by S and write:

$\left<S\right> = \bigcap \{ H : H \supset S, H \le G\}$ .

Thus, one often says that $\left<S\right>$ is the smallest subgroup of G which contains S, even though the term “smallest” reminds one of cardinality but that’s not what we mean. Let’s look at two small examples.

Examples of Generated Subgroups

Suppose S = {g}. We just write it as $\left<g\right>$ for short. Then clearly this subgroup comprises of all powers of g : i.e. $\ldots g^{-2}, g^{-1}, e, g, g^2, \ldots$ . If g is infinite, then so is this subgroup; otherwise, the order is precisely the smallest positive m for which $g^m = e$ . In short, the order of the subgroup generated by g is the order of g.
Suppose S = {x, y}. Things become much trickier: now $\left<x, y\right>$ contains all products of the form: $e, x, y, xy, x^{-1}y, \ldots, x^{-1}y^2 x y^{-3},\ldots$ . On the other hand, the set of all such products is clearly closed under multiplication and inverse. In short, the subgroup generated by {x, y} comprises of all word expressions in x, y and their inverses.

Application

For example, to express the group of transformations of the Rubik’s cube, one can consider the various moves $R, R^{-1}, L, L^{-1}, U, U^{-1}, D, D^{-1}, F, F^{-1}, B, B^{-1}$ which comprise of 90-degree rotations of the respective faces. Each such rotation can be written as a permutation of degree 54, so we get a set S of six such permutations. The question is: what do we know about $\left<S\right>$ ?

The Schreier-Sims algorithm is useful for answering such questions. For example, GAP implements this algorithm to compute the exact order of the group within a split second.

Cyclic Groups

Finally, we consider a group G such that $G = \left<g\right>$ for some element g. Thus, the group comprises of all powers of some fixed generator g. It’s (isomorphic to) either Z or Z/m. If we wish to pick a generator g of such a group, how many possible g are there?

Z : clearly +1 or -1, so 2 possibilities;
Z/m : we want g mod m such that gx = y always has a solution mod m, i.e. g is coprime to m. The number of such g is thus the Euler totient function φ(m).

So Z/m is cyclic. But what about (Z/m)*? It’s a classical result that this is cyclic iff m = 1, 2, 4, p^r or 2p^r, where p is an odd prime. For example:

(Z/11)* is generated by 2 since the powers of 2 are 1, 2, 4, 8, 5, 10, 9, 7, 3, 6, then 1.
(Z/18)* is generated by 5 since we get 1, 5, 7, 17, 13, 11, then 1.
(Z/15)* is not cyclic since the subgroup {1, 4, 11, 14} is not cyclic. [ Every subgroup of a cyclic group must be cyclic. ]

Number Theoretic Applications

These elementary group theory concepts can cast a new light on classical number theory problems.

Example 1. Find the number of x such that $x^3 \equiv 1 \pmod p$ , where p>3 is a prime.

We already know that (Z/p)* is cyclic of order p-1. Now, since p can’t be divisible by 3, we have $p \equiv 1, 2 \pmod 3$ .

If $p\equiv 1 \pmod 3$ , (Z/3)* is cyclic of order 3k, where k = (p-1)/3. If we pick a generator g mod p, then {1, g, g²} are the only possible solutions for $x^3 \equiv 1 \pmod p$ .
If $p\equiv 2 \pmod 3$ , then (Z/3)* is cyclic of order coprime to 3, so the only possible solution is x=1.

Let’s look at some concrete examples.

p = 19: let’s pick generator 2. Since o(2) = 18, the solutions are $1, 2^6 = 7, 2^{12} = 11$ . Check that if we had picked the generator 11, we’d still get the same solutions. 🙂
p = 11: you can check by brute-force that x=1 is the only solution.

Example 2. Prove that for any positive integer n, we have $\sum_{d|n, d>0} \phi(d) = n$ , where $\phi(m)$ is the Euler-totient function above.

Consider the group Z/n, which is cyclic of order n. Each element g generates a cyclic subgroup of order d, where d divides n. On the other hand, if d|n, then Z/n has a unique subgroup of order d (since it comprises of all multiples of n/d). This subgroup has $\phi(d)$ generators as we saw above. Thus the result follows.

Exercises

Let p>2 be prime. Find the number of solutions to $x^2 \equiv -1 \pmod p$ . [ Hint: consider 1 (mod 4) and 3 (mod 4). ]
Find the number of solutions to , where
- m = 5 × 7 × 11 × 17 × 19 × 29;
- m = 5² × 7³.

Posted in Notes | Tagged cyclic groups, generated groups, group theory applications, groups, intermediate, number theory, subgroups | 2 Comments

Casual Introduction to Group Theory (2)

Posted on September 23, 2012 by limsup

Axioms of Group Theory

[ This article approximately corresponds to chapter II of the earlier group theory blog. ]

Group theory happens because mathematicians noticed that instead of looking at individual symmetries of an object, it’s far better to take the set of all symmetries. In fact, investigating such a set often reveals deep insights on the structure of the said object. This was the philosophy behind Felix Klein’s ambitious and far-reaching Erlangen program, which was way ahead of its time and rather controversial then.

Back to group theory. Roughly speaking, a group is a set of symmetries. But we’re going to use an axiomatic approach.

Definition. A group is a set G together with a map $G \times G \to G$ , given by $(a,b) \mapsto a*b$ such that the following three axioms hold.

(S1) There is an $e\in G$ such that $e*g = g = g*e$ for any $g\in G$ . We call this “e” the identity element.

(S2) For any $x, y, z\in G$ , we have $(x*y)*z = x*(y*z)$ . We say that * is an associative function.

(S3) For any $g\in G$ , there is an element $h\in G$ such that $g*h = h*g = e$ . We say “h” is the inverse of “g”.

Our language highly suggests that the identity is unique, and that the inverse of each element is unique. Indeed, this is true. Also, associative basically means that if we have a sequence of operations, e.g. a*b*c*d*x, then however we choose to form the brackets (e.g. (a*(b*c))*(d*x) or ((a*b)*(c*d))*x, the resulting element is unchanged. Indeed, by repeatedly applying the associative law we get:

(a*(b*c))*(d*x) = ((a*(b*c))*d)*x,
((a*(b*c))*d)*x = (((a*b)*c)*d)*x,
(((a*b)*c)*d)*x = ((a*b)*(c*d))*x.

So as long as the order of the terms is unchanged, the result is still the same element of G. For convenience, we sometimes drop the “*” and just write the above as abcdx. However, the order does matter since g*h ≠ h*g for general elements g, h of G.

Definition. If g*h = h*g for all elements g, h of G, then we say * is commutative. A group where the product * is commutative is called an abelian group.

Note the subtle difference: commutativity refers to the operation * while abelian is an adjective describing the group. In an abelian group, not even the order matters so we can write abcdx = abcxd = bacxd = … . For convenience, one often denotes an abelian group with addition +, i.e. the above is written as a+b+c+d+x = a+b+c+x+d = ….; also the identity is denoted by 0 and inverse of g is –g.

The reason is purely psychological: mathematicians are accustomed to think of addition as commutative but multiplication as non-commutative in general (e.g. as in matrices). By convention, it’s ok to denote an abelian group operation by ×, but denoting a non-abelian group operation by + will lead to no end of grief.

Basic Notations. Given an element $g \in G$ , we define elements $\ldots, g^{-2}, g^{-1}, g^0, g^1, g^2, \ldots$ as follows:

the element $g*g*\ldots*g$ with n>0 terms is gⁿ;

g⁰ is defined to be e;

g^-1 denotes the inverse of g;

the element $g^{-1}*g^{-1}*\ldots*g^{-1}$ with n>0 terms is g^-n.

A bit of checking quickly reveals that the standard rules of exponentiation hold, i.e. $g^{m+n} = g^m * g^n$ for any integers m and n. If we had used addition to denote the operation, then we should write $\ldots, -2g, -g, 0, g, 2g, \ldots$ instead to be consistent.

Comment. Upon one’s first encounter with group theory, one is naturally skeptical: what can we possibly derive from three simple axioms? A priori, it’s not at all clear such an abstract definition has any interesting results. The richness of group theory thus is a pleasantly surprising outcome. We hope the reader will stick with us throughout the ride.

Who first wrote down these axioms? According to recorded history, Cauchy was the first to explicitly define the notion of a group. Earlier, Galois had relied heavily on group-theoretic concepts to prove his famed result that general quintic polynomials over Q cannot be solved via radicals, but because group theory wasn’t available, he had to rely on rather unwieldy notations and constructions.

Examples Galore

Let’s construct many examples of groups to familiarise ourselves with the concepts. First, the abelian (i.e. commutative) case.

the set Z of integers, under addition +;
the set Q of rational numbers, under addition +;
the set Q* of non-zero rational numbers, under multiplication ×;
the set Z/m of integers modulo m, under addition mod m, where m is a positive integer;
the set (Z/m)* of integers mod m which are coprime to m, under multiplication mod m.

For example, Z/5 = {0, 1, 2, 3, 4} and (Z/14)* = {1, 3, 5, 9, 11, 13}. The fact that inverses exist in (Z/m)* is a result of Bezout’s identity. Notice that the group operation for Q is addition but that for Q* is multiplication, so it’s inevitable that we sometimes have to use multiplication for the abelian group’s operation. On the other hand, one almost never sees a structure where addition fails to commute.

Next, the non-abelian case.

the set S_n of all permutations of degree n (i.e. {1, 2, …, n}), under composition (this is called the symmetric group of degree n);
the set A_n of all even permutations of degree n, under composition (this is called the alternating group of degree n);
the set of symmetries of a shape (e.g. square, icosahedron, buckyball), under composition;
more generally if X is any set, then the set S_X of all bijections X → X, under composition;
the set GL_n(R) of invertible real n × n matrices, under matrix product.

Notice that all the above examples of non-abelian groups are really “operations”. For example, permutations are just functions that shuffle indices 1, …, i around. Symmetries are operations that preserve a shape. And matrices correspond to linear functions on a vector space of dimension n. Now it’s easy to see why commutativity fails: a sequence of operations often cannot be arbitrarily permuted around, e.g. you can’t walk through the doorway before opening the door.

And $(ab)^{-1} = b^{-1} a^{-1}$ since you have to undo operations in a reverse order, as the protagonist of Steins Gate realised.

Exercises. Some exercises to test your concept.

If G is the set of odd permutations of degree n, is it a group under composition?
If G is the set of all permutations of arbitrary degree, is it a group under composition?
If G is the set of non-negative integers, is it a group?
If R is the set of real numbers, is it a group under the operation x*y := x+y+1?

Answers. Highlight to read.

No, because it doesn’t have an identity element.
No as it stands, because you can’t compose permutations of different degrees. HOWEVER, you can embed the set G into the group of all permutations of {1, 2, …} so it forms a subgroup, which is something we’ll see in the next chapter.
Undefined, since there’s no operation specified.
Yes. Check that the three axioms are satisfied, where e=-1 is the identity and -2-x is the inverse of x.

From now onwards, instead of saying G is a group under some specified operation, we’ll just say “G is a group”. Usually, the operation is pretty unambiguous. E.g. if we were to say: consider the group Z/37, the reader should automatically think of addition mod 37. As one delves deeper into higher mathematics, one learns to simplify notation to preserve one’s sanity.

Order of Element/Group

The order of a group G refers to the number of its elements. This is usually denoted #G or |G|. We can have |G| = ∞. For example, |Z| = ∞, |Z/m| = m and |(Z/m)*| = φ(m), which is the number of modulo classes mod m which are coprime to m. Also, |A_n| = n!/2 for n > 1, since product with (1, 2) gives a bijection between the set of odd permutations and the set of even permutations.

On the other hand, the order of an element g of G, is the smallest positive integer m such that $g^m = e$ . If no such m exists, then the order is said to be infinite. The notation for order is o(g) or |g|, e.g. in (Z/48)*, we have o(5) = 4, [ Writing |5| = 4 would have been a notational nightmare! ]

Now if $a, b \in G$ are of finite order, say $a^m = b^n = e$ , then it is not necessarily true that ab is of finite order. However, if G is abelian, then since we can swap around the order of ab, we get

$(ab)^{mn} = a^{mn} * b^{mn} = e*e = e$ .

Conclusion: in an abelian group, the product of two elements of finite order is also of finite order.

Challenge : find a group G with elements a, b such that $a^2 = b^2 = e$ but ab is of infinite order. [ Sample answer (highlight to read): consider the group G of all permutations of the set of integers Z. We have functions f(x) = –x and g(x) = 1-x. Then f(f(x)) = g(g(x)) = x but the composition gf(x) = 1+x clearly has infinite order. ]

Isomorphisms

Let G and H be groups. An isomorphism is a bijective map f : G → H such that f(xy) = f(x)f(y) for all elements x, y of G. If such an f exists, we say G and H are isomorphic. Basically, this just means that G and H are structurally identical and one can get from one group to the other by a mere relabeling of elements.

For example, Z/3 = {0, 1, 2} and the alternating group A₃ = {e, (1, 2, 3), (1, 3, 2)} are isomorphic. It’s quite easy to find all isomorphisms, namely f : Z/3 → A₃ must take 0 to e, and either [f(1) = (1,2,3), f(2) = (1,3,2)] or [f(1) = (1,3,2), f(2) = (1,2,3)].

So there are two possible candidates for the isomorphism f.

We shall now expound on this seemingly trivial point in excruciating detail. Please bear with us.

To reiterate, there’re two possibilities for an isomorphism between groups Z/3 and A₃. Furthermore, one isomorphism is as good as the other. Mathematicians say that the two groups are isomorphic but not canonically isomorphic. [ Warning: failure to understand canonical isomorphisms can cause much pain when one ventures into deeper mathematics, so we might as well explain it as thoroughly as we can now. ]

If two groups (or any structures) are said to be canonically isomorphic, it doesn’t mean that there’s a unique isomorphism between them. It just means there’s an unambiguously “right” isomorphism between them which is pleasing to one’s mathematical sensibilities. The whole point is that if we have three different structures A, B and C, then the presence of “canonical” isomorphisms $\phi : A \to B$ , $\psi : B \to C$ , $\theta : A \to C$ , must imply that $\psi\phi = \theta$ .

More generally, when we deal with multiple structures, we must make sure that the resulting function is “path-independent” in the diagram of maps. Mathematicians just say that the diagram commutes. In short, if we write out the algebraic objects and the isomorphisms between them, being canonical usually forces the entire diagram to commute since all are defined in a “natural” manner.

For example, if V is a finite-dimensional real vector space, then the dual V* is defined to be the space of linear maps V → R. Since V and V* have the same dimensions, they’re isomorphic. But there’s no natural way to define an isomorphism without exploiting the structure of V. On the other hand, V and V** are canonically isomorphic, so one often hears mathematicians / physicists saying “the dual of dual of a vector space is itself”.

For another example, the groups Z/6 and (Z/9)* are isomorphic but not canonically so. On the other hand, the group Z/15 is generally considered to be canonically isomorphic to Z/3 × Z/5. Here, (x mod 15) gives the pair (x mod 3, x mod 5); the fact that this is an isomorphism follows from elementary number theory. Likewise, (Z/21)* is generally considered to be canonically isomorphic to (Z/3)* × (Z/7)*.

For yet another example, if G and H are groups, then the set-theoretic product G × H has a group structure by defining (g, h) * (g’, h’) = (g*g’, h*h’). Then the group G × H is canonically isomorphic to H × G since there’s a natural map $G\times H \to H \times G$ which takes (g, h) to (h, g). Likewise, the triple products (G × H) × K and G × (H × K) are canonically isomorphic, so one can say that taking group products is a commutative and associative operation.

We’ll just leave it at that for now, but it’s hard to over-emphasize the importance of thinking in terms of canonical maps.

Posted in Notes | Tagged abelian groups, axioms, canonical maps, group orders, group products, group theory, intermediate, isomorphisms | Leave a comment

Casual Introduction to Group Theory (1)

Posted on September 21, 2012 by limsup

Introduction

Last year, I created a blog which was supposed to introduce concepts to abstract algebra in a systematic manner. Though I was reasonably happy with the end result, I got the sneaky feeling upon completion that the end product wasn’t any different from a typical textbook. The usual problems that plague students still remained. A friend of mine asked the critical question: “to whom are you targeting the notes at?” which set off an alarm. Indeed, the brevity of the notes indeed suggests that the reader is assumed to be relatively proficient, which would be a case of preaching to the choir.

This time, we’ll start by answering the above question.

The target audience is: students who’re interested in learning group theory, but who have little to no experience in concepts of abstract algebra.

What follows now is not a set of stand-alone notes, but a road map of topics to expect when studying group theory. We’ll try to motivate the definitions, theorems and examples as best as we can. We’ll be heavy on intuition and heuristics but low on rigour. Sometimes, instead of the most general statement possible, we’ll be content with a more concrete and down-to-earth version first.

The list of topics will be more or less the same as the above-mentioned blog. Repetitions will undoubtedly occur, since the important concepts are worth revising. Sometimes, we’ll also include comments that hint at stuffs deeper than those that are currently covered, hoping to entice our reader to learn more. So even if you feel reasonably competent in the topic, it may be worth a read.

In short, please don’t be scared off by any mention of unfamiliar/deep concepts.

Motivation (Permutations)

For this first chapter, we’ll be talking only about permutations. Readers who’re anxious to get to the meat of group theory should skip this article.

First, the primary concept which motivates study of groups is that of “symmetry” and “operations”. To fix concepts, we define the following.

Definition. A permutation of degree n to be a bijective map f : {1, 2, …, n} → {1, 2, …, n}.

We can compose two such maps as well as take the inverse of any such map to obtain another permutation. Let’s look at some common examples of permutations.

The (perfect) riffle shuffle of a deck of cards is a fixed permutation of degree 52. [ Note: there are two ways to riffle-shuffle a deck, depending on whether the top card remains at the top or becomes the second card. ]
A symmetry of a square ABCD is a permutation of degree 4 since it’s uniquely determined by where it takes the vertices. Let’s count the number of such symmetries, including reflections. Now, A can be mapped to any other vertex f(A). If we fix f(A), then the edge f(AB) has two possibilities since f(A) has two edges and both give valid symmetries. Thus there are 4 × 2 = 8 symmetries. For a greater challenge, try counting the number of symmetries of a regular icosahedron, making certain assumptions about the nature of the solid.
Sam Loyd’s 15-puzzle corresponds to a permutation of degree 16 (since it permutes the 16 unit squares around, including the blank square). [ Note: purists would say that it forms a groupoid rather than a group, but let’s not worry about that now. ]
The Topspin puzzle corresponds to permutations, typically of degree 20.
A transformation of the Rubik’s cube is permutation of degree 9 × 6 = 54, by looking at how the unit squares move. [ Note: it’s actually possible to compute the exact number of transformations, via a powerful method called the Schreier-Sims algorithm. But that’d take us too far astray. ]

In order to provide a more economical notation for a permutation, we write it in a 2-row matrix form, e.g.:

can be expressed as

$\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & 5 & 9 & 4 & 7 & 1 & 2 & 6 & 8\end{pmatrix}$ .

Or one can also express the same permutation in the form of cycles:

We usually write this as (1, 3, 9, 8, 6)(2, 5, 7), ignoring the fixed point 4.

The order of a permutation f is defined to be the smallest positive m for which $f^m$ is the identity map. Writing as disjoint cycles, it’s very clear that the order is merely the lcm of the length of the cycles. E.g. in the above permutation, the order is lcm(5, 3) = 15. We’ll like to cover two more concepts regarding permutations before moving on to abstract groups.

Exercise: what is the order of the riffle shuffle? [ Consider both variants. ]

Non-commutativity

Two permutations f and g are said to commute if fg = gf. It’s easy to find permutations which don’t commute, e.g. f(1) = 1, f(2) = 3, f(3) = 2 and g(1) = 2, g(2) = 1, g(3) = 3; the result is fg(1) = f(2) = 3 but gf(1) = g(1) = 2. Here, function composition always goes from right to left since fg(i) = f(g(i)).

Conjugate Permutations

This is based on the idea that relabeling the indices (1, 2, 3, 4) by, say, (a, b, x, y) does not substantially alter the nature of the permutations. So instead of the permutation f(1) = 1, f(2) = 3, f(3) = 4, f(4) = 2, we can write f(a) = a, f(b) = x, f(x) = y, f(y) = b, where the letters are dummy symbols here and not variables.

In particular, we can relabel (1, 2, 3, 4) by the same numbers, albeit permuted, say (3, 1, 4, 2). So the above permutation gets the relabeling:

Let’s do this carefully now. Suppose f : {1, 2, …, n} → {1, 2, …, n} is our original permutation. And g : {1, 2, …, n} → {1, 2, …, n} is the relabelling permutation. Now we list the entries of f as a graph or a lookup table, namely as a sequence of pairs:

$(1, f(1)), (2, f(2)), \ldots, (n, f(n)).$

Relabelling simply means that every single entry i in this list is replaced by g(i). So the new lookup table is:

$(g(1), gf(1)), (g(2), gf(2)), \ldots, (g(n), gf(n)).$

From this, a moment of thought tells us that the new permutation is given by $i \mapsto gfg^{-1}(i)$ .

[ Note: I personally find the above picture of a lookup table conceptually helpful, especially when dealing with group actions on function spaces at higher levels. ]

Thus we define two permutations $f_1$ and $f_2$ to be conjugate if there is a permutation g such that $f_2 = g f_1 g^{-1}$ . From the above explanation, it’s clear that two permutations are conjugate if and only if they have the same cycle structure, up to rearragement.

Example

Consider the two permutations of degree 9: $f_1 = (1, 5, 3, 7, 8)(6, 2, 9)$ and $f_2 = (1, 5, 2)(3, 8, 9, 6, 4)$ . Since both have two cycles, of lengths 3 and 5 respectively, the two permutations are conjugate. Now try to find a g such that $f_2 = g f_1 g^{-1}$ . Question: how many such g are there?

Parity of a Permutation

We’ve already seen that every permutation is a product of disjoint cycles. So if we’re only equipped with cycles, we can obtain all permutations by successive compositions. [ Note: you’ll learn later that the technical term is: the set of cycles generates the group of permutations. ]

In fact, every cycle is a product of transpositions, where a transposition is a cycle of length 2, i.e. a swap (a, b) between two indices. E.g.:

$(a_1, a_2, \ldots, a_r) = (a_1, a_2)(a_2, a_3)(a_3, a_4)\ldots (a_{r-1}, a_r)$ .

Clearly, there’s more than one possible way to write a permutation as a product of transpositions. E.g. (1, 3) = (2, 3)(1, 2)(2, 3), so in fact, even the number of transpositions can vary. It’s thus a minor surprise that the parity of the number of transpositions is fixed.

Definition: a permutation is odd (resp. even) if it can be written as a product of an odd (resp. even) number of transpositions.

Hence, a permutation is either odd or even but not both. The proof is not hard: we count the number of cross-overs, i.e. the number of pairs (a, b) such that a < b but f(a) > f(b). It turns out each additional transposition will alter the number of cross-overs by an odd amount. Here it is if you’re interested.

Now, we can use this to solve Loyd’s 15-puzzle.

Loyd asked if it’s possible to swap the “14” and “15” tiles by a series of slides. The answer is no: the above permutation, of degree 16, is a transposition (14, 15) so it is an odd permutation. On the other hand, since the empty square is back to its original position, there must have been an even number of moves, and each move is a transposition (of the empty square “16” and some other piece), so the resulting permutation ought to be even. This creates a contradiction. ♦

There’s actually far more to be said about permutations, but we won’t dwell on them any further. Onward to group theory…

Posted in Notes | Tagged 15 puzzle, abstract algebra, basic, casual, conjugate, group theory, order, permutations, rubik's cube, symmetries | 2 Comments

Combinatorial Game Theory Quiz 3

Posted on September 9, 2012 by limsup

The quiz lasts 75 minutes and covers everything from lessons 1-12.

For each of the following Nim games, find one good move for the first player, if any. (10 points) [ Note : exactly one of the games is a win for the second player.]
1. (5, 7, 8)
2. (3, 4, 8, 9)
3. (3, 5, 10, 12)
4. (1, 6, 8, 9, 10)
Consider the following Wythoff’s Queen game on a non-square board. Start with exactly one Queen. At each player’s turn, he picks up the Queen and moves it in one of the three indicated directions, any positive number of squares. The player who lands the Queen on the bottom-left hand corner wins, since the opponent is unable to make any move. Indicate whether each of the following 36 positions is winning or losing. (10 points)

Consider the game sum G + H.
1. Find G, H, such that G || 0, H || 0, and G + H = 0.
2. Find G, H, such that G || 0, H || 0, and G + H || 0.
3. Find G, H, such that G || 0, H || 0, and G + H > 0.
4. Find G, H, such that G || 0, H || 0, and G + H < 0. (8 points)
Consider the following partial games:

A = {3/8 | 1}, B = {-3/2 | -1/2}, C = {1/16 | 1/2}, D = {0 | 3/4}.

These four games are all numbers. Find their values with the Simplicity Rule and show that A + B + C + D > 0.
Left starts in the sum A + B + C + D and he can win. Among the four components A, B, C and D, which one should he move in? Write down all possibilities.
Left made a move in D. Which component should Right move in, now that it’s his turn? (12 points)

Given the following Toads-and-Frogs configurations:

compute the following configurations (hint: for the first one, do not consider its options). Check that the last game is fuzzy. (12 points)

Compare the following games, and decide whether G > H, G < H, G = H or G || H. (Hint: it may help to analyse the game G – H). (24 points)
- G = 1/8, H = -3/4;
- G = 300↑, H = 1/8;
- G = *1904, H = *2008;
- G = 3/4 + 2↓ + (*5), H = 3/4 + 3↓ + (*4);
- G = 3/4 + 2↓ + (*6), H = 3/4 + 3↓ + (*5);
- G = {5 | 2}, H = 3;
- G = {5 | 2}, H = 1;
- G = {5 | 2}, H = {7 | 3};
- G = { {10 | 5} | {-2 | -3} }, H = 0;
- G = { {0|4}, {1|2} | {4|7}, {5|6} }, H = 3;
- G = {8 | 0} + {-1 | -5}, H = {2 | -4} + {5 | 3}.
Recall the game of Cutcakes : given a cake, divided into m × n unit squares, each player at his turn takes a piece of cake and slices it along the edges of the squares, thus dividing the cake into two pieces. In addition, Left can only cut vertically, while Right can only cut horizontally. The values for m × n Cutcakes are given below: e. g. for a 6 × 8 cake, the value is -1.

Based on the above grid, guess the values for 32 × n for n = 1, 3, 6, 10, 15, 21, 28.
On a 7 × 9 cake, the value is -1, so Right wins. Find all possible winning moves for Right if he starts.
In the midst of the game, there are three cakes of sizes 3 × 10, 8 × 6 and 13 × 5 left,
together with some unit pieces. Given it is now Right‘s turn, can he win? If yes, find a winning move for him. (14 points)

Notes

The class scored an average of 73.1 with a standard deviation of 13.4, out of a class of 20+ students.
I added hints liberally throughout the final quiz; on hindsight these were probably a little unnecessary since the average score ended up approximately the same.

Posted in Homework | Tagged combinatorial game theory, computer science, game numbers, impartial games, intermediate, programming, toads and frogs | Leave a comment

Combinatorial Game Theory XII

Posted on August 29, 2012 by limsup

Lesson 12

Recall the following Domineering configuration in lesson 10:

The above game has a nice theory behind it.

Definition : For any game G, the game –_G (called miny–G) is defined to be:

$-_G = \{\{G\ |\ 0\}\ |\ 0\}.$

The game +_G (called tiny–G) is defined to be the negative of miny-G:

$+_G = -(-_G) = \{0\ |\ \{0\ |\ -G\}\}.$

The above Domineering position thus equals –₂. First, some easy results about tinies and minies:

miny-G is always negative; hence, tiny-G is positive.

If G ≥ H, then $-_G \ge -_H$ ; hence $+_G \le +_H$ .

Proof

(1) is trivial. For (2), since G ≥ H, we have {G | 0} ≥ {H | 0}. Hence it follows that:

$-_G = \{\{G\ |\ 0\}\ |\ 0\} \ge \{\{H\ |\ 0\}\ |\ 0\} = -_H$ .

The second part of (2) follows easily. ♦

Warning: it is not true that if G > H, then –_G > –_H (see exercise 1).

Next, we have:

Let G ≥ 0 be any game. Then +_G is positive and less than any positive number r. Thus +_G is an infinitesimal and not a number.

Proof. Since G ≥ 0, we have +_G ≤ +₀. But $+_0 = \{0 | \{0|0\}\} = \{0|*\} = \uparrow$ . Hence, +_G is a positive game which is smaller than or equal to ↑, which is smaller than any positive number. ♦

More on Minies and Tinies

Consider the games –_m and +_m for a number m. Note that if m is a negative number, then –_m and +_m are also numbers, which are not very interesting. Hence, we consider the case where m is a non-negative number. We introduce the following notation:

Let G and H be positive games. Write G << H if

G + G + … + G < H

for any finite number of copies of G.

In other words, if G << H then G is so much smaller than H that no matter how many copies of G you put together it’s still smaller than H. For example, we know that ↑ << m for any positive number m.

The key result of this section is:

Main Theorem. Let m > n be non-negative numbers. Then

$+_m << +_n$ .

In short, even if m and n differ by just a little bit, the resulting games are miles apart.

Proof.

Let us consider the sum of many copies of +_m = {0 | {0 | –m}} and one –_n = { {n | 0} | 0 }:

{0 | {0 | –m}} + {0 | {0 | –m}} + …. + {0 | {0 | –m}} + {{n | 0} | 0}.

We wish to show that this game is negative, i.e. Right wins. Right‘s strategy, at his turn, is to move +_m → {0 | –m} if there’s such a component available. If Left ignores this component on his next move, then Right proceeds to take {0 | –m} to –m: when that happens, Right is guaranteed a win since none of the components has a number m or above (the best number for Left is n < m).

Hence Left has no choice but to passively take {0 | –m} to 0, and Right may keep repeating this strategy. Eventually, Right‘s left with {{n | 0} | 0} or {n | 0} for his next move. In either case he wins. ♦

Notice that in the above proof, Right is the aggressive party and Left is forced to respond to each of Right’s threat. In Go terminology, we say that Right is sente (先手) and Left is gote (後手).

Hence, we have:

$\ldots << +_3 << +_2 << +_{3/2} << +_1 << +_{1/2} << +_0 = \uparrow$ .

For example, in Domineering we have:

Tiny games also occur rather frequently in Toads-and-Frogs (see exercise).

Advanced Topics

Due to time constraints and practical considerations, we can’t delve into advanced materials. Here’s a sketch of what we’re missing out.

[ Additional note: now that I’ve decided to place these notes online, it’s possible I’ll include some of these topics in a later installation. ]

1. Heating and Cooling

Games like {3 | -1} are considered hot because the next player has a great incentive to move from there. In this game for example, Left and Right are fighting for a possible 4-point difference. Another more complicated example is { {5|1}, 2 | {-1|-2} }. If a game has several hot components, analysing their sum may be quite difficult. A common technique to do this is to cool the game, i.e. make the next player pay a penalty for moving in that component. E.g. cooling {10 | -2} by 6 gives {10 – 6 | -2 + 6} = {4 | 4} = 4*.

Heating is just the opposite of cooling.

2. Thermograph

By cooling a game incrementally and measuring how hot it is, we obtain the thermograph of the game. This is a rather useful device, for given the thermographs of various components A, B, C, … , there is a general strategy to approximately find the best component to play from. The method is convenient but it may go wrong on rare occasions.

3. Go Endgame Analysis

Analysis of Go (Weiqi) endgames has progressed significantly in the last 15 years. In a typical Go endgame, the board is divided into independent components which are then summed up. CGT is very useful for studying the value of each component and simplifying the sum. Usually, we cool a component by 1 in order to effectively evaluate this sum.

4. Theory of Infinitesimals and Atomic Weights

An infinitesimal can be assigned an atomic weight m, which roughly approximates it with m copies of up ↑. E.g., ↑, 2↑ + *, 5↓ + (+₂) have atomic weights 1, 2, -5 respectively.

5. Impartial Misere Games

In misere games, the player who makes the last move loses, i.e. the player who’s unable to make a move wins! In 2005, Thane Plambeck found an ingenuous way of analysing misere games via the theory of monoids. As a result, games previously considered too difficult to analyse (e.g. Misere Kayles) have been effectively solved. This is a huge subject which is impossible to do justice to within a lesson or two.

6. Other Games to Analyse

Various other games are also of interest to researchers. E.g. clobber, konane, ski-jumps, amazons, fox-and-geese. A rather startling application was also found in the children’s game Dots-and-Boxes via the theory of nimstrings, which enabled deep analyses of complex positions. What’s rather ironic is that the theory is based on impartial games, although Dots-and-Boxes itself is clearly a partial game.

Exercises

Find games G > H, such that –_G = –_H. Can you pick your G and H to be infinitesimals? (Hint: let G be ↑ )
Generalise the main theorem: prove that if $m_1, m_2, \dots, m_t > n$ are all numbers, then

$+_{m_1}\ + \ +_{m_2}\ + \ldots +\ +_{m_t}\ < \ +_n$ .

Prove that:
1. if G, H, K are positive games and G < H, H << K, then G << K;
2. if a > c are numbers, then $+_{a*} = +_{\{a|a\}} << +_c$ ;
3. if a > b > c are numbers, then $+_{\{a|b\}} << +_c$ .
We saw in last week’s notes that:

equals $\{\{\frac 1 4\ |\ 0\}\ |\ 0\} = -_{1/4}$ . We can generalise this result as follows:

Suppose a Toads-and-Frogs game G has exactly one empty square. Prove that if Left starts by making a jump, he’ll lose.
Suppose a Toads-and-Frogs game G has exactly one empty square, and the only legal first moves are jumps. What can you say about G?
Consider the following game G_n for n ≥ 2:

Let H_n be the Toads-and-Frogs game obtained by letting Left move two toads consecutively. Prove that $G_n = \{\{H_n\ |\ 0\}\ |\ 0\} = -_{H_n}$ .

Prove that if n ≥ 4, then $H_n = \{n-3 | 1/2\}$ . Hence, $G_n = -_{\{n-3|1/2\}}$ .

Posted in Notes | Tagged combinatorial game theory, computer science, domineering, game infinitesimals, impartial games, intermediate, minies, tinies, toads and frogs | 1 Comment

Combinatorial Game Theory XI

Posted on August 25, 2012 by limsup

Lesson 11

In this lesson, we will cover more on canonical forms. First recall that for m↑ + (*n) with m > 0, this game is positive except when (m, n) = (1, 1). Let’s consider the canonical forms of these games.

First, we know that ↑ = {0 | *}.

What about ↑* = ↑ + * ? By definition, we get:

$\uparrow * = \{0\ |\ *\} + \{0\ |\ 0\} = \{*, \uparrow\ |\ *+*, \uparrow\} = \{*, \uparrow\ |\ 0\}$

since * + * = 0 < ↑. Now let’s consider the Left option ↑. This has a Right option *. Now is it true that * ≤ ↑*. Of course! So we can replace the Left option ↑ by all the Left options of *. This gives:

$\uparrow * = \{0, *\ |\ 0\}.$

We’ll leave it to the reader to check that further simplification is impossible. So we have the canonical form of ↑*.

Next, what about 2↑ = ↑ + ↑? Again, by definition,

$2\uparrow = \{\uparrow\ |\ \uparrow*\}.$

Let’s see if move reversal takes place. Left‘s option to ↑ has the Right option *. Now is it true that * ≤ 2↑ ? Yup! So we can replace Left‘s option ↑ by all Left options of *. This gives $2\uparrow = \{0\ |\ \uparrow*\}$ .

Now let’s consider the Right option to ↑*. Since we already saw that ↑* = {0, * | 0}, this has Left options 0 and *. Now is it true that 0 (or *) ≥ 2↑ ? Nope to both cases! So we obtain the following canonical form:

$2\uparrow = \{0\ |\ \uparrow*\}$ .

We’ll leave it to the reader to calculate the canonical forms of the following and find a pattern among them (see exercise 2).

2↑ + *
3↑
3↑ + *
4↑
4↑ + *

Next, let’s consider G = ↑ + *2. By definition, we have:

$G = \{*2, \uparrow, \uparrow*\ |\ *3, \uparrow, \uparrow*\}$ .

Since ↑ > *2 we can erase the Left option *2. Likewise, since *3 < ↑ and *3 < ↑* we can erase the Right options ↑ and ↑*. This leaves:

$G = \{\uparrow, \uparrow*\ |\ *3\}.$

Any move reversals possible? Let’s consider the Left option ↑, which has Right option *. Since * < G, move reversal happens and we replace ↑ by the Left options of *, thus giving $G = \{0, \uparrow*\ |\ *3\}$ . By the same token, the Left option ↑* has Right option 0 < G, so we shall replace ↑* by the Left options of 0, i.e. nothing! This gives us:

$\uparrow + *2 = \{0\ |\ *3\}$ .

Next, calculate the canonical forms of the following and find a pattern among them (see exercise 3).

↑ + *3
↑ + *4
↑ + *5

More Domineering

It turns out for small m and n, the m-by-n Domineering board has rather nice canonical forms. The following can be calculated on a computer using cgsuite:

	1	2	3	4	5	6
1	0
2	1	±1
3	1	{1/2 \| -2}	±1
4	2	+₂	3/2	G
5	2	1/2	1	-1	0
6	3	{1 \| -1+(+₂)}	{7/2 \| 1}	#&!?*	3/2	Out of mem
7	3	{1/2 \| -3/2}	{3 \| 3/4}	-1

where

–₂ = {{2 | 0} | 0},
+₂ = – (-₂) = {0 | {0 | -2}},
G = {0, H | 0, –H}, and H = {{2|0}, 2+(+₂) | {2|0}, –₂}.

There are also many sequences of Domineering configurations which admit a general formula. E.g.:

Exercises

Guess the canonical forms of the following games (the first game has n+1 Light and n daRk dominoes; the second game has n Light and n daRk dominoes). Can you prove it?

Write down the canonical forms of n↑ and n↑ + *. Prove it. [ For this and the next two problems, take note of the fact that ↑* is fuzzy. ]
Write down the canonical form of ↑ + *m. Prove it.
Even more generally, write down the canonical form of n↑ + *m. Prove it.
Given the following two Domineering games:

simplify the following into canonical form:

Given the following Toads-and-Frogs games:

simplify the following games into canonical forms:

Posted in Notes | Tagged canonical forms, combinatorial game theory, computer science, intermediate, nim values, partial games, toads and frogs, toppling dominoes, up game | Leave a comment

Combinatorial Game Theory X

Posted on August 22, 2012 by limsup

Lesson 10

In lesson 7, we learnt that if A, B are Left’s options in a game with A ≥ B, then we can drop B from the list of options and the game remains equal. In this lesson, we will learn a second type of simplification.

Simplification (II)

This is called move reversal and it takes a certain amount of practice to get used to.

Let G be a game. Suppose there is a Left option A of G, and a Right option X of A satisfying X ≤ G. Then we can replace the Left option A of G with all the Left options of X.

The following diagram illustrates this replacement.

The idea behind the replacement is that if Left makes the move G → A, then it does not hurt for Right to make the move A → X. Hence, we can replace the option A by all Left options of X to obtain the resulting game.

Proof.

We wish to show that these two games are equal:

$G = \{A, B, \dots | Y, Z, \dots\}$ and $H = \{D, E, F, \dots, B, \dots | Y, Z, \dots\}$

For that we consider G – H. For most moves that the first player makes, the second player has a corresponding move in the other component to bring the game to zero. Exceptions are:

Right goes first and moves –H → –D. This results in the sum G – D. On the other hand, this could have occurred if Right moves first in G–X and takes –X → –D. Since G–X≥0, Right loses if he starts in G-X. Hence Left wins if he goes first in G–D.
Left goes first and moves a move G → A. Then Right counters with the move A → X thus giving the game X – H. Now consider the game X–G ≤ 0 : if Left starts first in this game, Right wins. Now let us switch back to X – H, where Left goes next.
- If Left moves –H → –Y, then the resulting game X – Y could have arrived from Left‘s move –G → –Y in X – G. Thus Right wins if he goes next in X – Y.
- If Left moves X → D, then Right can counter –H → –D thus giving a zero sum (and winning).

This completes the proof that second player wins in G-H. ♦

By symmetry, we have the following move reversal as well.

Suppose there is a Right option X of G, and a Left option A of X satisfying A ≥ G. Then we can replace the Right option X of G with all the Right options of A and the game remains equal.

Note: it may not seem advantageous to replace one option by so many options. But now D, E, F are much simpler than the initial option A, so further simplifications can be obtained easily. You’ll see this for yourself in lots of examples.

Let G be a game. An expression $G = \{A, B, \dots | X, Y, \dots \}$ is said to be in canonical form if it cannot be simplified using (I) (in lesson 7) or (II) above.

It turns out that the canonical form of a game is essentially unique! This will be proven at the end of the lecture.

Examples

[ Note: the following examples are much more effective when presented on the board. Otherwise, to get a more in-depth understanding, you should work out the reasoning yourself. ]

Consider the Domineering position:

Left‘s options are 0 and *, while Right‘s option is *. So the above game is: $G = \{0, *\ |\ *\}$ .

From Left‘s option G → *, Right can move * → 0. Is it true that 0 ≤ G ? Indeed, it is easy
to see that if Right starts in G then Left wins. Hence, the Left option * reverses to 0 and we
have to replace it by all Left options of 0. Since 0 has no options, we get $G = \{0\ |\ *\} = \uparrow$ .

Consider the game G = {* | 1}. The Left option G → * has the Right option * → 0. Is it true that 0 ≤ G ? Yes: clearly if Right starts in G, then Left wins. So as before, we shall replace * by all Left options of 0. This gives G = { | 1} = 0.
What about G = {↑ | 1} ? The Left option ↑ has the Right option ↑ → *. Now is * ≤ G ? To answer this question, we look at G – * = G + *. If Right starts this game, he has two options: either G → 1 or * → 0: either way, the result is positive and he loses. So indeed, we have * ≤ G. This means we can replace the option ↑ by all Left options of *, i.e. 0. This gives G = {0 | 1} = 1/2.
Next consider the Frogs-and-Toads position from lesson 8:

We recall that this game is given by G = {↑ | ↓}. Can we simplify this further? Now, Left has the option G → ↑, which has the Right option ↑ → *. Is it true that * ≤ G? Let’s check out G + *. Right has two possible moves: either G → ↓ or * → 0.

In the first case, Left gets ↓* which is a first-player win, i.e. Left wins.
In the second case, Left gets G and promptly responds with G → ↑ to win.

Hence, * ≤ G indeed and we can replace the Left option ↑ by the Left options of *, namely 0. This gives G = {0 | ↓}. Repeat this to get G = {0 | 0} = *.

Consider the following Toppling Dominoes position in the previous lesson.

Recall that this game is G = {0, * | 1}. Let’s consider the Left option *. Here, there exists a Right option * → 0 and we ask whether 0 ≤ G. Indeed, if Right starts in G, he has to move G → 1 and Left wins, so 0 ≤ G. As a result we can replace * by all Left options of 0, namely nothing. So G = {0 | 1} = 1/2.

Consider the game G = {0 | *, ↓}.
- Left‘s move to 0 has no Right option.
- Right‘s move to * has a Left option 0. Now is 0 ≥ G ? Clearly not: Left wins in G if he starts, so Right‘s move to * cannot reverse to 0.
- Right‘s move to ↓ has Left option *. Is * ≥ G ? Looking at G+ *:
  - If Left starts by moving G to 0, then Right moves * to 0 and wins.
  - If Left starts with * to 0, then Right moves G to ↓ leaving a negative game and wins.
  - Hence, Right‘s move to ↓ has to be replaced by all the Right options of *, namely 0. This gives us G = {0 | *, 0}. Check that it cannot be reduced any further.
Consider the game G = { {2 | 1/4} | {3 | 1} }. Left‘s move to {2 | 1/4} gives Right the option to move to 1/4. Now is 1/4 ≤ G ? Indeed, take G+ (-1/4).
- If Right starts by taking G → {3 | 1}, then Left can counter with {3 | 1} → 1 and win.
- If Right starts with (-1/4) = {-1/2 | 0} → 0, then Left wins since G is positive.
- So Left‘s move reverses to 1/4, and we may replace {2 | 1/4} by the Left options of 1/4 = {0 | 1/2}, i.e. 0. Hence, G = {0 | {3|1}}. Similarly, we can replace {3 | 1} by the Right options of 3, so G = {0 | } = 1.

Uniqueness of the Canonical Form

We have the following surprising result.

Theorem (Uniqueness of Canonical Forms). If games G and H are equal, and

$G = \{A, B, \ldots | X, Y, \ldots \}, H =\{A', B', \ldots | X', Y', \ldots \}$

are both in canonical form, then after some reordering, we have A = A’, B = B’, …. , X = X’, Y = Y’, … .

Proof

It suffices to show: for each Left option A of G, there is a Left option A’ of H such that A=A’. For this, let’s look at G-H. Since this is a 2nd-player win, the game A–H is a win for Right if he starts. What could Right‘s winning move be?

Suppose Right‘s winning move is $A-H \to X_0 - H$ for some Right option X₀ of A. Then X₀–H is win for Right if Left starts. Thus, X₀–H ≤ 0 which means X₀≤ H = G. But this means that Left‘s move G → A reverses to X₀, which contradicts our claim that G is already in canonical form.
Suppose Right‘s winning move is $A-H \to A - A'$ for some Right option –A’ of –H. As in the first case, we now have A – A’ ≤ 0 which means A ≤ A’.

In conclusion, for any Left option A of G, we can find a Left option A’ of H such that A ≤ A’. By symmetry, this means we can also find a Left option A” of G such that A’ ≤ A”. But this means: A ≤ A’ ≤ A”.

Since G is already in canonical form, and A ≤ A” are both Left options of G, we see that they’re in fact equal. Thus A = A’ = A”. ♦

Exercises

Simplify the following games as much as you can (using the two methods of simplifications, and/or any shortcut you can think of):
1. {* | 1/4}
2. {0, * | 1}
3. {0, ±1 | 4}
4. {0, *, *2, ↑ | ↑ }
5. { {5|0}, {4|1} | {2|3} }
Prove that if G = {A, B, … | X, Y, … } and there is a number m such that

A, B, … < m < X, Y, …

then G itself is a number. Hint: use the number avoidance theorem from last week. Using this, go back to question 1. Can you tell at one glance which games must be numbers?

Given the following Toads-and-Frogs games:

write the following games in canonical form:

Given the following Domineering games:

write the following in canonical form:

Given the following Domineering games:

write the following in canonical form:

Posted in Notes | Tagged canonical forms, combinatorial game theory, computer science, domineering, intermediate, partial games, programming, toads and frogs, toppling dominoes | Leave a comment

Combinatorial Game Theory Quiz 2

Posted on August 21, 2012 by limsup

This quiz lasts 70 minutes and covers materials from lessons 1-9.

Use the simplicity rule to compute the values of the following games. (10 points)
- {1/2 | }
- {-1/4 | }
- {1/8 | 3/8}
- {0 | 7/8}
- {1/8 | 9/16}
- { | }
Compare the following games by writing G < H, G = H, G > H or G || H. (12 points)
- G = 1 + ↑, H = 1/2 + 10↑
- G = ↑, H = *10
- G = 3↑, H = *10
- G = -1/2 + 3↑ + (*8), H = -1/2 + 3↑ + (*9)
- G = -1/2 + 3↑ + (*8), H = -1/2 + 4↑ + (*9)
- G = -1/2 + 3↑ + (*5), H = -1/2 + 4↑ + (*6)
The game of Maundy’s Cutcakes is played as follows. Take a cake, divided into m × n unit squares. At each player’s turn, he takes a piece of cake and makes any number of slices along the edges of the squares, dividing the piece into two or more pieces of exactly the same dimension. As before, Left can only cut vertically, while Right can only cut horizontally. A typical game may proceed as follows if Left starts:

It turns out this game is a number for all m × n cakes. Find the numbers for all 1 ≤ m ≤ 6, and 1 ≤ n ≤ 6. (16 points)

Compute the values of the following Toads-and-Frogs games (some of them are given). Note that Left has more than one possible move in some of the games. (18 points)

Decide whether each of the following statements is true or false. For false statements, find a counterexample. (18 points)
1. If the first player wins in G, and the first player wins in H, then the first player wins in G+H.
2. If the first player wins in G, and the second player wins in H, then the first player wins in G+H.
3. If the first player wins in G, and Left wins in H, then Left wins in G+H.
4. If x, y are any numbers and m = {x | y}, then x < m < y.
5. If G + G = 2, then either G = 1 or G = 1* = 1+*.
6. If G and H are games which are numbers, then we cannot have G || H.
7. If A < 0 and X || 0, then the game G = {A | X} equals zero.
8. If G + G = 1, then G cannot be negative.
9. If G + G = 1, then G cannot be fuzzy.
Find the values of the following six Hackenbush diagrams:

Find the value of the following Hackenbush game when the length tends to infinity (no rigourous proof required). (16 points in all)

Note

Out of a class of >20 students, the average score was 72.4/90, with a standard deviation of 11.5. This time, I think the quiz is a little simple. 😛

Posted in Homework | Tagged combinatorial game theory, computer science, game numbers, intermediate, partial games, up game | Leave a comment

Combinatorial Game Theory IX

Posted on August 20, 2012 by limsup

Lesson 9

Typically, at the end of a Domineering game, the board is divided into disjoint components, so the overall game is the (game) sum of the individual components. Suppose we have the following 6 components:

How should the next player respond? From an earlier exercise, you know that the components are (respectively):

{1|-1}, {0|0}, {0|-1}, {2|-1/2}, -1/2, {-1|-1}

Intuitively, the next player should pick the fourth component since it gives him 2 points; while if his opponent grabs the chance, it costs him 1/2 point. This creates a difference of 5/2 points depending on who gets to move there, which makes it rather critical.

Let’s take a closer look at games of the form {a | b}.

Games of the Form {a | b}

First, the Simplicity Rule tells us that if a < b, then this game is a number. So let’s assume a ≥ b. We claim that the resulting game satisfies:

$\{a\ |\ b\} + c = \{a+c\ |\ b+c\}$

for any number c. Equivalently, we need to show that $\{a\ |\ b\} + c + \{-b-c\ |\ -a-c\}$ is a 2nd-player win.

Proof.

If the first player moves from the component {-b–c | –a–c} or {a | b}, his opponent can retaliate by moving from the other component to give a zero game. On the other hand, if Left starts first and moves c → d, then by an earlier observation, we may assume d < c. Right then counters by taking –a–c, thus leaving

$\{a\ |\ b\} -a-c+d < \{a\ |\ b\} - a$ .

What can Left do now? Taking {a | b} to a is suicidal since the result is a negative number. And if he moves (-a-c+d) to x with x < –a-c+d < –a, then Right counters by taking {a | b} to b, leaving the number x+b < b-a ≤ 0. Recall that this means if Left goes next, then Right wins. In conclusion, the first player loses even if he moves from the number component. ♦

Key observation: if a ≥ b, then we can write:

$G = \{a\ |\ b\} = \frac{a+b} 2 + \{x\ | -x\}$ , where $x = \frac{a-b} 2$ .

Notation: for convenience, we will use the shorthand ±x for the game {x | –x}. We’ll avoid this when x=0 though, since {0|0} = * and denoting it by ±0 may be awkward.

Examples

Recall that we saw games like {1 | 1}, {-1| -1}, {2 | 2} etc. By the above result, if m is a number then {m | m} = m + {0 | 0} = m*. Thus, the sum {1|1} + {-1|-1} + {2|2} is simply 1 + (-1) + 2 + * + * + * = 2*.
We also saw many games of the form G = {a | b} where a > b. For example:

The combined game is thus given by ±1 + (5/4) + (±3/4) = 5/4 + (±1) + (±3/4). What’s a good way to play this game? Before we can answer this question, let’s have a general result.

Number Avoidance Theoerm

Suppose we have a sum of two games:

G = x + H,

where x is a number, and H is not. Assume that if Left starts in G, he has a winning strategy. Then he can pick his winning strategy by moving from H.

In short, if Left starts in G, there’s no reason for him to make a move from x at all. By symmetry, the same applies for Right: there’s no reason for Right to make a move from the number x.

Proof.

Let’s suppose: if Left starts in G, he can win by moving x to y (y is a number < x). Thus, y+H ≥ 0 (recall that a game ≥ 0 if and only if Left can win whenever Right gets to go next).

Successively, let y‘ be the Left option of y, let y” be the Left option of y‘ etc. Eventually, you’ll run out of options: x > y > y‘ > y” > … . Let z be the smallest of these such that z + H ≥ 0 (since y + H ≥ 0, we can definitely find such a z).

Now H is not a number, so H ≠ -z. Thus z + H > 0. If Left starts in the game H+z, he has a winning move. This move cannot be z → z‘ since by the minimality of z, we do not have z‘ + H ≥ 0. Hence, it must be to some Left option A of H: so z + A ≥ 0. But this gives:

$x+A > z+A \ge 0.$

so Left has a winning move in x+H by moving to x+A. ♦

In short, let’s say we have a sum of several games. If all components are numbers, then so is the sum and the outcome of the game is crystal-clear. Otherwise, there’s at least one component which is not a number, and the Number Avoidance Theorem says that the winning party only needs to look at those components which aren’t numbers. This is concisely summarised as follows.

Avoid making a move in the number,
unless there’s nothing else to do.

Games of the Form ±c

Let’s go back to the game 5/4 + (±1) + (±3/4) in example 2. We’ll see who wins in this game. Suppose Left starts, with no loss of generality.

By Number Avoidance, Left should focus his effort on (±1) or (±3/4).
Suppose he picks the second component (±3/4) → 3/4. Then once again, by Number Avoidance, the only logical move for Right is the remaining (±1) → -1. This gives a grand total of 5/4 + 3/4 – 1 = 1.
On the other hand, if Left picks the first component (±1) → 1, the same analysis tells us that the resulting total is 5/4 – 3/4 + 1 = 3/2 which is clearly better. So Left ought to pick this option.

On the other hand, if Right starts, the final sum would be 5/4 – 1 + 3/4 = 1. In short, if Left starts, the final game value is 3/2, while if Right starts, it would be 1.

In summary, if we have a game x + (±a) + (±b) + (±c) + … , where x is a number and a ≥ b ≥ c ≥ …, the most logical thing for the first player is to play the largest a, then the next player goes for the next largest b, etc.

One can also think of a game (±c) as a cheque for an additional c moves for either player. From this point of view, it becomes clear that the best course of action is to pick the cheque with the largest value.

Now we’re ready to analyse the Domineering game we saw earlier:

with values given by:

±1, *, 1/2 + (±1/2), 3/4 + (±5/4), -1/2, -1*

The two stars cancel each other out, so the final sum is -1/4 + (±5/4) + (±1) + (±1/2).

If Left starts: Left takes ±5/4 to 5/4, Right takes ±1 to -1 and then Left takes ±1/2 to 1/2, thus giving a total of (-1/4) + (3/4) = 1/2: Left wins.
If Right starts, the reverse happens and we get (-1/4) – (3/4) = -1: Right wins.

Warning! This does not mean the sum of the games is {1/2 | -1}. It just means that if these are the only components left, the above outcome would happen if both players were to play optimally.

New Game: Toppling Dominoes

Here’s a new game, called Toppling Dominoes. We have several dominoes (coloured Light or daRk, corresponding to Left or Right) which are placed upright in one or more rows. Each player, at his turn, pushes one of his dominoes over either to its left or right – this will cause a chain reaction, toppling over all dominoes to its immediate left or right. Dominoes which have been toppled do not contribute to further gameplay.

E.g. here’s an example of a game where Left starts:

As usual, the player who runs out of legal moves loses the game. Clearly Right made a bad move above, since he could have toppled the third daRk domino to get rid of the Light domino to its right, thus leaving one additional free move for himself.

If in a row, there are n dominoes for Left and none for Right, then clearly the value of the row is exactly n since Left can start toppling from the leftmost domino one by one (to the
left), which gives him n free moves. The next interesting example is:

Let’s analyse this position:

Left starts: his best move is to topple all of Right‘s dominoes with a single move, leaving n-1 dominoes of his own. This gives n-1.
Right starts: likewise, his best move is to topple all of Left‘s dominoes with a single move, leaving m-1 dominoes of his own. This gives -(m-1).

Thus, the resulting game is {n-1 | -(m-1)}, which we had analysed earlier. In particular, when m = n = 1, this is {0 | 0} = *. Next, consider the following:

If Left starts, he can topple all dominoes or leaves a pair of Left/Right dominoes. If Right starts, he has no choice but to leave 1. Hence, the game is: G = {0, * | 1}.

We will learn a new form of simplification in the next lesson, and see that it is equal to 1/2. For now, you can verify this by proving that {0, * | 1} + (-1/2) is a second-player win.

Exercises

Find a game H = {A | X} which is a number, and a number x such that $H+x \ne \{A+x\ |\ X+x\}$ .
Consider the following game:
number + {2 | -1} + {0 | -3} + {1 | -1} + {3 | 2} + {0 | -1/4}.

Left gets to start. By the theory we learnt earlier, his best move should be in the component {2 | -1} or {0 | -3}. Yet he chooses to move in {1 | -1} → 1 instead. Explain why this move really isn’t bad.
Prove that if a ≥ b ≥ c, then { {a | b} | {b | c} } = b.
Recall the following claim in Lesson VI:

Prove this by proving the more general assertions:

Compute the following Domineering positions (use exercises 2 and 3 if necessary):

(Hard) Guess a general formula for such configurations and prove it.

Posted in Notes | Tagged combinatorial game theory, computer science, domineering, game numbers, intermediate, number avoidance, partial games, programming, toppling dominoes | Leave a comment

Combinatorial Game Theory VIII

Posted on August 18, 2012 by limsup

Lesson 8

In this lesson, we will further familiarise ourselves with games involving numbers. At the end of the lesson, we will encounter our first positive infinitesimal: the “up” ↑. Here, an infinitesimal is a value which is strictly between –r and r for any positive (dyadic) rational number r. We saw in the last lesson that *n is an infinitesimal for any n, but these are fuzzy games. The game ↑ is positive, i.e. 0 < ↑ < r for any positive rational r.

Toads-and-Frogs

Here’s an interesting game which can be analysed effectively using numbers. Without CGT, such a detailed analysis of the game would be difficult!

The game of Toads-and-Frogs is played on several rows of squares as above, where each square contains at most one creature. Each creature can only move in the direction it’s facing. E.g. in the first row, the toads in the first and third square can only go right, and the frog in the fourth square can only go left. By convention, player Left controls the TOads which go from Left to Right, while player Right controls the FROgs which go from Right to Left.

At each player’s turn, he may pick up one of his creatures and perform one and only one of the following moves:

move one square in its direction and land on an empty square; or
jump over an opponent‘s creature and land onto an empty square.

Play proceeds until a player loses for having no available moves.

Stop and think : how do we get the negative of a Toads-and-Frogs game? [ Answer (highlight to read) : we reflect the row about a vertical axis, so that all the toads facing right become frogs facing left, and vice versa. ]

Numbers in Toads-and-Frogs

In the case where there’s one toad and one frog in a row, the solution is usually a number or a * so analysis is quite easy. However, if there’s more than one frog / toad, the situation can become rather complicated.

For starters, consider the following configurations:

Instead of tracing through the whole game tree of each configuration, it is much more efficient to systematically consider a row with a single toad and a single frog. For a row in which the animals have already jumped past each other, it is easy to compute the value. Next, we start from the case where the frog and toad are side-by-side facing each other.

Examples

For the first row, if Right starts, he has no move available. On the other hand, if Left starts, the resulting configuration has 3 free moves for Left and 1 free move for Right. Thus, the first row = {3-1 | } = {2 | } = 3 by the Simplicity Rule.
For the second row, if Right starts, the resulting configuration has 4 free moves for Left and no move for Right. On the other hand, if Left starts, the resulting configuration has 2 free moves for Left and 2 free moves for Right. Thus, the second row = {2-2 | 4} = {0 | 4} = 1 by Simplicity Rule.

Next consider the case where there’s an empty space between them.

E.g. let’s consider the first row. If Left starts, the resulting game is 1, as we saw above. If Right starts, the resulting game is 3. Thus the overall game is {1 | 3} = 2. Now we’ll leave it to the reader to fill in the remaining entries…

To check your answers, click here.

Next we consider the case where there are exactly two toads (going Left to right) and two frogs (going Right to left). There are altogether 30 such configurations. Compute and simplify them as much as you can. [ Hint: recall that a game where the second player wins is a zero game. ] For the answer, click here.

A Positive Infinitesimal Game

The last 3 games are of particular interest to us. Let’s label

$\uparrow = \{0\ |\ *\}$ and $\downarrow = - \uparrow = \{-*\ |\ -0\} = \{*\ |\ 0\}$ .

The final game in the diagram is then equal to $\{ \uparrow\ |\ \downarrow\}$ . In a later lesson, we will learn another simplification rule, which will enable us to show that this is equal to *.

For now, let’s look at ↑ = {0 | *}. The interesting thing is that this game is positive, yet it is less than any positive number. The first claim is easy; as for the second claim, let us use the following useful comparison tool.

Theorem: Consider two games

$G = \{A, B, \ldots | X, Y, \ldots\}$ and $H = \{A', B, \ldots | X, Y, \ldots\}$ ,

where all options are identical except A and A’, where A ≥ A’. Then we must have G ≥ H.

Similarly, if we replace Right option X by X’ where X ≥ X’, then the resulting game H also satisfies G ≥ H.

Proof: We need to show that in G–H, if Right starts then Left wins. The strategy for Left is simple: whatever his opponent does in one component, he just mirrors in the other. The only problem occurs when Right tries moving (-H) to (-A’). To counter this, Left just moves G to A, thus leaving A – A’ for Right. Since this game ≥ 0 and Right goes next, Left wins. ♦

Warning : If A > A’, it does not follow that G > H (see exercise 1).

Now we can show that:

For any n > 0, we have 0 < ↑ < 1/2ⁿ.

Indeed, recall that we have * < 1/2ⁿ for any positive integer n. Hence, we have ↑ = {0 | *} ≤ {0 | 1/2ⁿ} = 1/2ⁿ⁺¹ < 1/2ⁿ. In fact, it turns out that any finite number copies of ↑ is smaller than 1/2ⁿ (see exercise 2).

Finally, we have the following result:

↑ is confused with *, i.e. ↑* is a first-player win.

For other Nim values however, we have:

↑ is larger than *2, *3, *4, … .

Also, for more copies of ↑, we have:

If m > 1 and n ≥ 0, then m↑ is larger than *n, where m↑ refers to the sum of m copies of ↑.

The proofs of all these results are in exercises 3 and 4. Finally since ↓ = -↑ , we also have the corresponding statements for the “down” game ↓.

For any n > 0, we have 0 > ↓ > -1/2ⁿ.
On the other hand, ↓ is confused with *.
But ↓ is smaller than *2, *3, *4, … .
Finally, for each m > 1 and n ≥ 0, m↓ is smaller than *n.

Exercises

Find games A, A’, B, such that A < A’ and {A | B} = {A’ | B}.
We already know that 0 < ↑ < 1/2ⁿ for any positive n. Use this to prove that for any positive integer m and integer n ≥ 0, we have m↑ + *n < 1/2ⁿ.
Prove that if n = 1, then ↑ + *n is a first-player win, and that if n > 1, then ↑ + *n is positive.
Prove that ↑ + ↑ + *n is positive for any n ≥ 0. Hence, prove that for any m > 1, and non-negative integer n, the game m↑ + *n is positive.
Compare the following: is the first expression greater than / less than / confused with / equal to the second expression?
- -1 + 3↑ and -5/4 + 100↑
- -2 + 100↓ + *2 and -1
- -1 + ↑ and -1 + *
- 2 + ↑ and 2 + ↓ + *
- 2 + ↓ + (*7) and 2 + ↑ + (*8)
- -1/2 + 10↑ + (*3) and -1/2 + 11↑ + (*2)
- -1/2 + 10↑ + (*8) and -1/2 + 11↑ + (*7)
State a general method of determining whether a + b↑ + (*c) is positive, negative, fuzzy or zero.
Decide the status of the following Toads-and-Frogs game. For each player, find his best move if he were to go first.

Posted in Notes | Tagged combinatorial game theory, computer science, game infinitesimals, intermediate, partial games, programming, toads and frogs, up game | Leave a comment

Mathematics and Such

Combinatorial Game Theory Quiz 3

Combinatorial Game Theory XII

Lesson 12

More on Minies and Tinies

Advanced Topics

Exercises

Combinatorial Game Theory XI

Lesson 11

More Domineering

More on Toppling Dominoes

Exercises

Combinatorial Game Theory X

Lesson 10

Simplification (II)

Examples

Uniqueness of the Canonical Form

Exercises

Combinatorial Game Theory Quiz 2

Note

Combinatorial Game Theory IX

Lesson 9

Games of the Form {a | b}

Examples

Number Avoidance Theoerm

Games of the Form ±c

New Game: Toppling Dominoes

Exercises

Combinatorial Game Theory VIII

Lesson 8

Toads-and-Frogs

Numbers in Toads-and-Frogs

A Positive Infinitesimal Game

Exercises

Recent Posts

Archives

Categories

Meta

Pages