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 14, 2008

Mathematica 6 and Compiz on Kubuntu Hardy

Filed under: GNU/Linux, Mathematics — Tags: , , , , , — Kevin @ 10:13 am

My school offers the software for “anybody who is on the payroll,” and we’re taught to use it pretty heavily in some of our classes (there is even a 1-credit course on Mathematica) so I went ahead and downloaded it from the department. However, even from the start I’d had some troubles. Now I’ll tell you how to fix those.

When I was running Mathematica 5, I had a nasty issue where running Beryl with XGL (on a nasty ATI card, before AIGLX was supported in the fglrx driver) in the background would make my text and most of the graphics transparent. My method of fixing this was to just put a blank terminal in the background. After the new ATI driver with AIGLX support, the problem was fixed, but now it opened three windows at startup, two of which were blank and I couldn’t close. Upgrading to Mathematica 6 brought no relief, and upgrading to Kubuntu 8.04 brought along another problem with fonts – now everything was white, and changing the color would fix it.

So, here’s the fix.

  1. Fixing fonts: Instead of typing “mathematica” into a terminal to start Mathematica 6, try using “mathematica -defaultvisual” which fixed the fonts for me.
  2. Fixing the three popup windows: The bug was reported here, but I’ll go ahead and summarize it to save you the trouble of searching through other people’s comments. First, go to “Edit->Preferences…”, which should pop up the preferences dialog. Click the “Advanced” tab on the top right and right next to “For all other option settings:” click “Open Option Inspector.” Now on the left bar, go to “Notebook Options->Window Properties” and change “Window Frame” to “Generic.” Below is a screenshot of my preferences (click to blow it up).

Click to see larger image

That’s it! Now close Mathematica and restart it to get only one window and visible fonts!

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 4, 2008

What is a mathematical group? (Part 2)

Filed under: Mathematics — Tags: , , , , , — Kevin @ 9:41 pm

In my previous post, I gave the definition of a group. In this post, I will identify some examples of groups. My objective for this post is to show that many different objects (not just numbers) fit the bill for a group, and so it may be easier to prove things for a group abstractly (that is, without any particular group in mind) using just the properties of the definition of a group.

Example 1: As in the previous post, the integers form a group under addition.
Proof: A general property of addition of integers is that the sum of two gives another. The operation can also be taken for granted to be associative. Previously, I identified 0 as the identity element, and the negative of an element to be its inverse.

(Non) Example: The integers under multiplication do not form a group.
Proof: The operation of multiplication is indeed a binary operation, and it is associative. The identity element is 1 because 1x=x1=x for every x\in\mathbb{Z}. However, no element other than 1 itself has an inverse. Indeed, when multiplication is the operation, the inverse of x is 1/x, but the only x for which this is an integer is x=1. Furthermore, 0 does not even have an inverse in any set of numbers since 0x=x0=0\ne 1. Hence (\mathbb{Z},\times) is not a group.

Example 2: To fix the previous problem, consider the set \mathbb{Q}\setminus\left\{0\right\}, that is, the set of all rational numbers (fractions) minus the number 0, with the operation of multiplication. I will leave it to the reader to verify that this does indeed form a group.

Example 3: Consider the set of all n\times n non-singular (that is, invertible) matrices, together with matrix multiplication. The reader familiar with matrix algebra will be able to easily show that these form a group.

Example 4: One can also form groups out of objects that aren’t necessarily numbers. For example, consider the symmetries of an equilateral triangle, as shown below in the picture.

The symmetries of an equilateral triangle

The picture on the left involves flipping the triangle around the axis indicated. The picture on the right involves rotating the triangle, by either 120°, 240°, or 360°. Any of these operations will return an equilateral triangle in the same orientation as the original.

Call rotation by 120° the element \rho, rotation by 240° \rho^2. Clearly, rotation by 360° leaves the triangle unchanged, so let’s call that e, the identity operation. Call the flip furthest left f_1, the middle flip f_2, and the right flip f_3. By labeling the vertices, we can then combine the operations to get a new orientation. For example, a rotation by 120° followed by a rotation by 240° gives a total rotation by 360°. That is, \rho^2\rho=e. Notice that the operations in this notation are applied right to left – that is, first we applied \rho followed by \rho. The set with these operations has the “multiplication table” shown below:

\begin{array}{c||c|c|c|c|c|c} \cdot & e & \rho & \rho^2 & f_1 & f_2 & f_3\\\hline\hline e & e & \rho & \rho^2 & f_1 & f_2 & f_3\\\hline \rho & \rho & \rho^2 & e & f_2 & f_3 & f_1\\\hline \rho^2 & \rho^2 & e & \rho & f_3 & f_1 & f_2 \\\hline f_1 & f_1 & f_3 & f_2 & e & \rho^2 & \rho \\\hline f_2 & f_2 & f_1 & f_3 & \rho & e & \rho^2 \\\hline f_3 & f_3 & f_2 & f_1 & \rho^2 & \rho & e \end{array}

The table is read by taking the row times the column. So for the row marked f_2 and the column marked \rho, the result is f_2\rho=f_1. That is, rotating first by 120° and then flipping along the centerline of the result is the same as flipping the triangle about the f_1 line.

One can check using this table that these operations form a group. Clearly, rotations and flips give another rotation or flip, so the operation is indeed a binary operation. The indentity is rotation by 360°, and each element does indeed have an inverse (for example, \rho^{-1}=\rho^2 since \rho\rho^2=\rho^2\rho=e; this can be checked for each and every element). And the operations are associative, though to show this is left as an exercise to the reader.

One beautiful thing about groups is that a very broad spectrum of objects can be shown to exhibit the properties of a group. It is much more attractive, then, to show things about a group abstractly than it is to show it for a certain set of objects.

For example, notice that in each of the groups in the above examples only had one identity element. This is actually true of any structure that is a group. Hence, the following theorem.

Theorem: In a group, the identity element is unique.
Proof: Suppose that there are two identity elements, e and f. Then by applying properties of the identity element, we have

e=ef=f.

Because there was no reference to integers with addition, rationals with multiplication, invertible matrices, or symmetries of a triangle, I have simultaneously proven that the identity element of each of these structures is unique! Indeed, I have shown it for the countless numbers of groups that one can construct. That is the power of working abstractly!

Next time I’ll start proving a few other useful properties of groups.

(Part 1)(Part 3)

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)

May 26, 2008

Circumference of a Circle

Filed under: Mathematics — Kevin @ 2:06 am

So I was thinking about my previous area problem and the thought occurred to me that the same method could also be used to derive the circumference of the circle.

Using the same setup as before, the perimeter of the polygon is just Nb. So again if we let N\rightarrow\infty we should get the circumference of a circle.

Recall that I found the formula for b in terms of the number of sides and the radius: it was

\displaystyle b=\frac{r\sin(2\pi/N)}{\sin(\pi/2-\pi/N)}

The circumference of a circle is then

\begin{array}{rcl}\displaystyle C&\displaystyle=&\displaystyle \lim_{N\rightarrow \infty}N\frac{r\sin(2\pi/N)}{\sin(\pi/2-\pi/N)}\vspace{0.3 cm}\\&\displaystyle=&\displaystyle \lim_{N\rightarrow \infty}\frac{r\sin(2\pi/N)}{N^{-1}\sin(\pi/2-\pi/N)}\vspace{0.3 cm}\\&\displaystyle=&\displaystyle \lim_{N\rightarrow\infty}\frac{r\cos(2\pi/N)(-2\pi N^{-2})}{-N^{-2}\sin(\pi/2-\pi/N)+\pi N^{-3}\cos(\pi/2-\pi/N)}\vspace{0.3 cm}\\&\displaystyle=&\displaystyle \lim_{N\rightarrow\infty}\frac{r\cos(2\pi/N)(-2\pi)}{-\sin(\pi/2-\pi/N)+\pi N^{-1}\cos(\pi/2-\pi/N)}\vspace{0.3 cm}\\&\displaystyle=&\displaystyle 2\pi r,\end{array}

which is again exactly as expected.

And now with that out of the way, I can get some sleep. Good night!

May 24, 2008

Interesting way to derive the area formula for a circle

Filed under: Mathematics — Kevin @ 2:19 pm

I was bored today and looking through some old notebooks of mine and came across an interesting derivation of the circle area formula using some geometry and the concept of a limit. This idea dates back to my freshman or sophomore year.

Consider an N-gon that is broken up into N identical isosceles triangles with their unique angle touching the center. Let the side that is shared by each triangle have length r. This description might be difficult to understand, so I drew the case for N=5, a pentagon.

Clearly if we let N approach infinity, we get smoother and smoother polygons until we finally get a circle, as shown in the picture below.

So, if we’d like to find the area of the N-gon, we can find the area of each triangle we’ve created and multiply by N. Using that and letting N approach infinity should give us the area of a circle.

Now the inner angle on each of these pentagons is 2\pi /N radians, which leaves each of the outer angles to be

\displaystyle\psi=\frac{\pi-2\pi/N}{2}=\pi/2-\pi/N ,

in radians. As a sanity check, as N goes to infinity here, the angle goes to \pi/2, which is expected.

Recall that the area for a triangle is a=\frac 1 2 b h , where b is the base width and h is the height of the triangle. We can find the base by the law of sines. That is:

\begin{array}{rcl}\displaystyle\frac{\sin\theta}{b}&\displaystyle=&\displaystyle\frac{\sin\psi}{r}\vspace{0.3 cm}\\\displaystyle\frac{\sin(2\pi/N)}{b}&\displaystyle=&\displaystyle\frac{\sin(\pi/2-\pi/N)}{r}\end{array}.

This gives us b, but we still don’t have h. Luckily, we can form a right triangle out of half of each isosceles triangle. This new triangle has hypotenuse r and legs h and b/2. Thus

\displaystyle \sin\psi=\frac h r.

Putting things together, we get that

\displaystyle \frac{\sin\theta}{b}=\frac h{r^2},

or after rearrangement,

\begin{array}{rcl}\displaystyle A&=&\displaystyle Na\vspace{0.3 cm}\\&\displaystyle=&\displaystyle N\frac{bh}{2}\vspace{0.3 cm}\\&=&N\left(\frac{r^2\sin\theta}{2}\right)\vspace{0.3 cm}\\&=&N\left(\frac{r^2\sin(2\pi/N)}{2}\right)\end{array}

If we now take the limit as N goes to infinity, we get an indeterminate form. We can, however, apply L’Hopital’s rule after some rearrangement:

\begin{array}{rcl}\displaystyle\lim_{N\rightarrow\infty}\frac{r^2\sin(2\pi/N)}{2N^{-1}}&=&\displaystyle\frac{r^2}{2}\lim_{N\rightarrow\infty}\frac{\cos(2\pi/N)(-2\pi N^{-2})}{-N^{-2}}\vspace{0.3 cm}\\&=&\displaystyle\frac{r^2}{2}\lim_{N\rightarrow\infty}2\pi\cos(2\pi/N)\vspace{0.3 cm}\\&\displaystyle=&\displaystyle\pi r^2\end{array}

Taking the limit gives the familiar formula.

Part of my purpose for this posting is to test out how Blogspot handles mathematical formulas. As far as I can tell, there’s no easy way to do so. I had to use an image renderer here to render the formulas, and I’m not too impressed with it. I’ll be experimenting with MathML here in the next few days to see how it renders.

Update: Fixed all of the math to go with WordPress’s built in \LaTeX capabilities. Looks pretty nice.

Blog at WordPress.com.