Unused Cycles

August 3, 2008

The Gordon Game

Filed under: Mathematics — Tags: , — Kevin @ 11:30 pm

The Gordon game is a game to be played by two people who know a bit about group theory (and by a bit, it’ll suffice to read my introduction to group theory). I found of the game in the book “Adventures in Group Theory: Rubik’s Cube, Merlin’s Magic and Other Mathematical Toys” by David Joyner.

According to the book, the rules are as follows. Take two copies of a set corresponding to the group (G,\ast) and call one M and the other P. The rules are then as follows:

  1. Player one chooses an element p_1 from the group P and m_1 from M. These can be any element he chooses, and once they are chosen they are removed from the sets P and M
  2. The next player chooses an element m_{i+1} and p_{i+1} such that p_{i+1}=m_{i+1}p_{i}. Both elements are removed from their respective sets.
  3. Repeat the previous step. The first player that cannot move loses.

I’ve written a program in C++ that will compile under GCC. The group used here is \mathbb{Z}/7\mathbb{Z}, that is, the integers modulo 7. You can download it here, although this link may change after I graduate. I wrote it hastily, so it’s not commented well and it probably has bugs. To compile, use the command

g++ gordon.cpp -o gordon

I can compile it fine on OpenSUSE 11.0. There’s no AI yet, so it simply switches between two human players. In the future, I may add support for user-defined groups and possibly some rudimentary AI.

Enjoy!

UPDATE: I updated the program a little bit so that you can make your own groups. As a result, you’ll now need to download the default file, z7z.grp, if you  want to be able to run the program.

To make your own groups, follow this recipe:

  1. On the first line, list all of the group elements separated by a space and followed by an exclamation mark.
  2. Now just list the multiplication table, with a space between columns and a new line between rows.

For example, the group \mathbb{Z}/7\mathbb{Z} looks like this:

0 1 2 3 4 5 6 !
0 1 2 3 4 5 6
1 2 3 4 5 6 0
2 3 4 5 6 0 1
3 4 5 6 0 1 2
4 5 6 0 1 2 3
5 6 0 1 2 3 4
6 0 1 2 3 4 5

To use your new group, pass it on as a command line argument, i.e. run

./gordon mygroup.grp

That’s it! Try it with a complicated group, for example a large order dihedral group.

Advertisements

June 11, 2008

What is a mathematical group? (Part 3)

This will be my last post in this little series I’ve started on group theory. Here are parts one and two.

In part one, I defined the terminology needed to identify the axioms for a group. In part two, I gave examples of a group, and began a short taste of what group theory is all about (doing things abstractly). In this part, I’ll giving an only slightly more involved introduction to proofs in group theory, as well as introduce some other so-called “algebraic structures” other than groups.

Previously, I showed that the identity element is unique within a group. Is the same true for an inverse of an element within a group? That is, given an element a within a group, is there only one element a^{-1} such that a^{-1}a=aa^{-1}=e? The claim is:

Theorem: An element a within a group G has a unique inverse.
Proof: Again the argument is by contradiction. Suppose that there are two elements that have this property, b and c. Then

b=eb=(ca)b=c(ab)=ce=c.

We can define the power of an element in a group, a^n to be \underbrace{aaa\ldots a}_{n\text{ times}} just as expected. We can also define it inductively so that a^n=a^{n-1}a for positive n.

Note that there is nothing in the definition of the group G that states that it is necessary that ab=ba for an a,b\in G. This is, in general, not true. Recall that non-singular matrices under matrix multiplication are a group. But matrix multiplication is not always commutative. A group for which every element commutes with every other element is called abelian. Just a small theorem involving abelian groups is the following:

Theorem: If a^2=e for every element a\in G, then G is abelian.
Proof: We can take two elements a,b so that ab\in G since we’re inside a group. Then by assumption (ab)^2=e. But we also have e=ee=a^2b^2 so that (ab)(ab)=(aa)(bb). Right multiplying by b^{-1} and left multiplying by a^{-1} gives ba=ab, the desired equality.

The theory of groups is much more involved and complicated than just simple theorems that show a certain property such as uniqueness of an element or that one property implies another. For further reading on the topic of groups, try reading about cosets, Lagrange’s Theorem, permutations, and isomorphism of groups. You can also try reading the online textbook that we used for my course in abstract algebra here, though be warned it goes more in depth than the topics presented here – it’s definitely for somebody who is not just mildly interested in the subject.

In closing, I’ll introduce other common algebraic structures without doing anything with them.

Definition: A commutative ring is a set R with two binary operations, + and \ast that has the following properties for every a,b,c\in R:

  1. Additive Commutativity: a+b=b+a
  2. Additive Associativity: (a+b)+c=a+(b+c)
  3. Additive Identity: There exists an element, 0, such that a+0=0+a=a
  4. Additive Inverses: There exists an element -a such that a+(-a)=(-a)+a=0
  5. Multiplicative Commutativity: ab=ba
  6. Multiplicative Associativity: a(bc)=(ab)c
  7. Multiplicative Identity: There exists an element 1 such that 1a=a1=a
  8. Distributivity: a(b+c)=ab+ac

Notice that this definition says that the set is an abelian group under addition, but it is important to note that it is not a multiplicative group (there is no guarantee of a multiplicative inverse). Examples of rings include the non-negative integers with addition and multiplication, rational numbers with addition and multiplication, and the real numbers with addition and multiplication. The set of n\times n real matrices with matrix multiplication and addition do not form a commutative ring since they are not commutative under multiplication. They do, however, form a “non-commutative” ring.

The next definition “fixes” multiplication in a ring so that it is (almost) a multiplicative group.

Definition: A field is a commutative ring where every non-zero element a\in G has a multiplicative inverse.

Of the previous rings identified, only the rational and real numbers are fields.

The last definition I’m going to give will be a familiar one to most physicists (as they’ve almost surely taken a course in linear algebra).

Definition: A vector space over a field F is a set V of elements called vectors together with a binary operation + on V and a function \ast: F\times V\rightarrow V called scalar multiplication (the asterisks is again usually dropped). Given a,b\in F and x,y,z\in V, the following properties hold:

  1. Additive Associativity: (x+y)+z=x+(y+z)
  2. Additive Commutativity: x+y=y+x
  3. Additive Identity: There exists a vector, called 0, such that x+0=x
  4. Additive Inverse: There exists a vector -x such that x+(-x)=(-x)+x=0
  5. Vector Distributivity: a(x+y)=ax+ay
  6. Scalar Distributivity: (a+b)x=ax+bx
  7. Multiplicative Associativity: (ab)x=a(bx)
  8. Multiplicative Identity: Given the multiplicative identity in F, 1x=x

The reader familiar with linear algebra knows that F=\mathbb{C} and V=\mathbb{C}^n is a vector space. Other examples include F=\mathbb{R} and V as the set of all polynomials of degree less than or equal to n.

That’s it for this introduction to abstract algebra. Give me your thoughts if you found it interesting!

(Part 1)(Part 2)

June 3, 2008

What is a mathematical group? (Part 1)

Last semester, a friend of mine (who has now graduated with his B.S. in physics) asked me the question, “What exactly is a group?”

I was able to answer his question because I had already taken a course in elementary group theory. But I had also taken a course in particle physics, in which the Standard Model relies on groups, and I had not heard anything about defining a group in this class. For the uninformed student, it seemed like the lecturer was doing weird magic with groups and “adding” them together.

I will be writing this short introduction with the physics student in mind. Especially if the student is interested in any type of particle physics, this may be an interesting read.

To begin on the odyssey that is in store for a student of abstract algebra, it pays to know a bit of terminology.

Definition: A binary operation (sometimes law of composition) on a set G is a function \ast:G\times G\rightarrow G . That is, this function takes two elements of the set G and produces another in G. A more familiar way of looking at this for a physicist that has taken a course in linear algebra is that the set is closed under this operation, just as in a vector space – the sum of two vectors in a vector space V is another vector in that same set.

For example, addition (and subtraction as well) is a binary operation on the set of all integers \mathbb{Z}, for if one adds (or subtracts) two integers, the result is another integer.

Typically, this binary operation is not written in the usual fashion of writing a function of multiple variables \ast(g,h), but rather g\ast h. Normally, unless it leads to confusion, the \ast is dropped in favor of just writing gh as in normal multiplication.

Definition: The binary operation is associative if for every a,b,c in the set on which the operation is defined, (ab)c=a(bc). That is, the order of applying the binary operation has no effect on the outcome.

For example, if we examine the example of integers with addition as the binary operation, this binary operation is associative. However, if one takes the operation as subtraction, this is not associative (take, for example, 1 – (2 – 3) = 1 – (-1) = 2, but (1 – 2) – 3 = -1 – 3 = -4).

Definition: An identity element of a set G with a binary operation is an element e where es=se=s for any s\in G.

Note: Mathematicians like to use shorthand (hence all of the symbols used for different operations). The symbol \in is read “is an element of”. So the previous line s\in G is read “…for any s that is an element of G.”

Going back to the example of integers with addition, 0 acts as the identity here, because x+0=0+x=x for every x\in\mathbb{Z}.

Definition: Given an element s in a set G with a binary operation and identity element e, the inverse of s (usually denoted by s^{-1} where appropriate) is one such that ss^{-1}=s^{-1}s=e.

One last reference to the integers under addition shows that the inverse of an integer x is -x since x+(-x)=(-x)+x=0.

The punchline from all of this is the definition of a group:

Definition: A group is a set G together with a binary operation that has the property of associativity, an identity element, and inverses for each element in the set.

Next time, I’ll give some examples of groups and start proving some elementary theorems about them.

(Part 2)(Part 3)

Blog at WordPress.com.