The (a,b,c)-product problem, II (& a little group theory)

The (a,b,c)-product problem, Part II

In the previous post we looked at some elementary questions on the order of a product in terms of the order of the factors.  If, in some numerical system, x has order a and y has order b, what is the order of yx?

If x and y commute (so that xy=yx) then we argued that one would expect the answer to be the least common multiple (LCM) of a and b.  This is almost true.  (A side exercise: assuming x and y commute, when is the order of yx not the LCM of a and b?)

What if x and y do not commute?  Although our basic (grade school) arithmetics obey the commutative property, most physical systems do not.  Indeed, commutativity is rare!  In most applications, the order of operations (such as "putting on shoes" and "putting on socks") is important.  If the operations of the physical system have a mathematical structure (such as the collection of symmetries of a polygon) then commutativity generally fails.

Consider the composition of functions.  If

f(x) = x^2+1 and g(x)=3x

then the compositions

(fog)(x) = 9x^2+1 and (gof)(x)=3x^2+3

are different. (In the first case we run x through g then f, moving from right to left; in the second case, (gof) is computed by running x through f then g, again moving from right to left.)

Permutations, groups & permutation groups

A permutation of a set X is a one-to-one correspondence from the set X onto itself.  For example, the permutation 

f=(1 2 3 4 5)

takes the number 1 and moves it to 2, moves 2 to 3, 3 to 4, 4 to 5 and (since 5 is at the right end) moves 5 around to 1.  If there are other numbers available (like 6 or 7 ... or 0) then f does not move those.  The permutation f has order 5; apply f five times and everything has cycled back to its starting position.

The permutation g = (1 5 3) moves 1 to 5, 5 to 3 and 3 back to 1.  It has order 3.

The composition (gof), f followed by g, moves 1 to 2 and 2 to 1 (since f moves 2 to 3 and g moves 3 to 1) and so swaps the points 1 and 2.  It also swaps 3 and 4 and fixes the element 5.  In cycle notation, we write

gf=(1 5 3)(1 2 3 4 5) = (1 2)(3 4).

The order of the permutation gf=(1 2)(3 4) is two since it merely swaps pairs of numbers so applying gf again swaps them back  Thus we have found an element, f, of order 5 and an element, g, of order 3 whose product, gf, has order 2.

What are the possible orders of a product?  Given a triple of positive integers (a, b, c), is it possible for there to be an element x of order a and an element y of order b such that yx has order c?

If we focus on permutations, then the answer is generally YES.  A folklore lemma (worked out in detail by my colleague Jordan Webster at Mid-Michigan Community College) is the following:

Lemma.  As long as a, b, and c are all integers greater than or equal to 2, then there is a finite group of permutations with an element x of order a and an element y of order b such that yx has order c.  Futhermore, if we allow infinite groups then any of the values a, b and c may be infinite (independent of the choice of others.)

So -- anything works!!  Pick a, b and c from the set of natural numbers greater than 1 and there are elements x and y that "solve" the (a, b, c) order requirement.

Undergraduate exploration and research

The Lemma (versions of which are folklore) might at first glance seem to completely solve our "(a, b, c)" or "order-of-products" question posed at the top of the post.  What is left to do? However, it is an mathematical proverb that one solution opens an infinitude of questions.  Since the solutions to the (a, b, c) order-of-products problem always exist, what are the best solutions?

There are several ways to define "best" solution.

(At this point, a first course in abstract algebra will be helpful.)  Given an ordered triple like (2, 3, 7) we could ask for the smallest finite group which has an element x of order 2 and an element y of order 3 such that yx has order 7.  By a theorem of Lagrange, such a group must have order divisible by 2, 3 and 7, thus divisible by 42.

Or we could ask for the smallest set X with permutations f and g so that f has order 2, g has order 3 and gf has order 7.  Such a set must have at least 7 elements, since there is a 7-cycle permuting its points.  Is it possible that X = {1, 2, 3, 4, 5, 6, 7}?  Can we really solve the problem with X this small?

Other versions of "best" lead to other problems, other questions.  We could assume that the elements x and y are generated by reflections in Euclidean 3-space.  Or we can consider products of reflections in the hyperbolic plane.  (These are related.)  A general investigation into these reflections in geometry is the theory of triangle groups; investigation into tilings in hyperbolic geometry leads to tesselations in the hyperbolic plane and honeycombs in hyperbolic 3-space.  (Tilings in Euclidean geometry involve wallpaper groups and finite Coxeter groups.)

Meanwhile, I offer another lemma from the work of Jordan Webster and me: 

Suppose that  (a, b, c) are three distinct primes and suppose G is the smallest group with an element x of order a and an element y of order b such that yx has order c.  Then G is a simple group.

What is the smallest (2, 3, 7) solution?  It should be a simple group with order divisible by 42.  Can you find the smallest such simple group and show that it does indeed have the required elements of orders 2, 3 and 7?

Simple groups form the building blocks of finite groups and almost all simple groups can be described as symmetries of some type of mathematical object.  So this question about orders of elements is probably linked to some deep questions in group theory.

Open questions

Here are the first twenty open parameters sets. I don't know the smallest groups which solve these.  My guess is that they are alternating groups (on c points?) but I don't have any proofs.  In most cases, a computer run using the (free) software package GAP found no solutions of order less than 2000.

A first run at any of these problems would involve creating small permutations x and y to solve the problem.  Eventually proving that one has found a smallest group solution probably requires the fundamental homomorphism theorem (assume a normal subgroup N and look at xN, yN, xyN) and may benefit from the Sylow theorems.

1. (2, 5, 7)
2. (2, 5, 9)
3. (2, 7, 10)
4. (3, 5, 7)
5. (3, 5, 9)
6. (3, 7, 10)
7. (3, 8, 9)
8. (3, 9, 10)
9. (4, 5, 7)
10. (4, 5, 9) 
11. (4, 7, 9)
12. (4, 7, 10)
13. (4, 9, 10)
14. (5, 5, 7)
15. (5, 5, 8)
16. (5, 5, 9)
17. (5, 6, 7)
18. (5, 6, 9)
19. (5, 7, 7)
20. (5, 7, 8)

I would also be interested in the smallest set X for which a permutation group on X solves one of the above problems.  I suspect this answer is driven by c; if c is a prime power then we need X to be of size at least c; if c=10 then (since 10=2*5) we might be able to get by with X of size less than 10.

If you are interested in working on any of these open cases, send me an email or send me a tweet.

Final words

Professor Jordan Webster and I have been exploring the (a, b, c) order-of-products problem for some time.  We think there are some nice open, but accessible, questions involved in finding "best" solutions to the  (a, b, c) order-of-products question.  This is an example of an undergraduate problem with "legs" -- the more we get into it, the more it runs ahead of us into a variety of interesting realms of mathematics.  In many of these areas (such as tilings of the hyperbolic plane or families of simple groups) this problem involves rich work already done by others in the last century.  Whether one works on this problem as a student or directs students on this work, there is a lot of good mathematics to assimilate along the way.

For those who desire applications for their mathematics ....  Many areas of "pure" mathematics lead, in two or three steps, to applied problems in the sciences.  One straightforward version of the order-of-products question leads to tesselations in hyperbolic geometry and hyperbolic geometry itself is useful in our understanding of relativity and space-time.  Our current GPS systems would accumulate errors on the order of 6 miles per day, if the satellite clocks were not set so as to take account for the non-Euclidean geometry of special relativity.

Next time: What make a good undergraduate research question?

[Mathematical prerequisites: Discussion of permutation composition requires experience with one-to-one functions such as in a typical precalculus class.  But a more general attack on this problem requires a college junior/senior level course in abstract algebra.  This project requires no mathematics beyond college.
     I am grateful for this website of Dr. Richard Pogge, Ohio State, for the GPS example.]

Follow Ken W. Smith on Twitter @kenwsmith54

The (a,b,c)-product problem, I (& Fermat & the internet)

Directing research with undergrads in math...

As I enter a sabbatical semester concentrating on undergraduate research, I will both write on interesting undergraduate research problems and also offer some advice on directing research projects with undergrads.  More on the general plan later ....  but instead, as I do in my own classrooms, ... let's worry about the "syllabus" later and jump right into the mathematics!

... and the (a,b,c)-product problem 

Lay a sheet of paper on a table and place your index finger in the middle of the paper.  Rotate the paper around your fixed finger by 30 degrees (say, clockwise.)  How many times must you do that rotation before the paper returns to its original position?

Twelve.  It takes 12 copies of the 30-degree rotation to "return to start".  The positive integer 12 is the order of the rotation by 30 degrees.

Let's multiply integers modulo 13.  (So this is an exploration in modular arithmetic.) Begin with the number 2 and keep multiplying by 2 until you get the number 1.  Here is what happens when you multiply by 2 modulo 13:

2, 2^2=4, 2^3=8, 2^4=16=3, 2^5=2*3=6, 2*6=12=-1, 

2*12= 24=11, 2*11=22=9, 2*9=18=5, 2*5=10, 2*10=20=7, 2*7= 14=1.

It takes 12 multiplicative steps to return to the "identity" number, 1.

2^12=1 modulo 13

and so the order of 2 modulo 13 is 12.

The order of an element f (under a certain operation) is the smallest positive integer n such that

f^n=1.

Since 2^12=1 modulo 13, and 2^n is not 1 for any smaller positive integer n, then the order of 2 modulo 13 is 12.

What is the order of 4 modulo 13?  Since 4=2^2, a moment's thought might suggest that the order of 4 is 6.  We write ord(4)=6.

Although number theory is a typical college class for upper level math undergraduates, modular arithmetic can be taught to elementary school children (usually called "clock arithmetic" in that setting) and so we have not yet gotten into any serious mathematics....

A simple question

One step off the trodden mathematical path can often lead one into the mathematical wilderness.  We begin a mathematical exploration by asking a simple question.

What is the order of a product of two elements?

Suppose I have two elements x and y (and some underlying operation like multiplication modulo 13).  If I know the order of x and the order y, what can I say about the order of yx (or the order of xy?)

For example, if we are doing arithmetic modulo 13 then ord(8) = 4 and ord(3)=3.  Now 3*8=24=11, so can those the two orders (ord(8)=4, ord(3)=3) tell us the order of 11?  Yes.

Since

8^4=1

then

(8^4)^3=1^3=1 

so 

8^12=1.

Since

3^3=1 

then

(3^3)^4=1^4=1

so

3^12=1.

Since

8^12=1 

and

3^12=1 

then

(3*8)^12=(3^12)(8^12)=(1)(1)=1.

A little thought suggests that the order of yx should be the least common multiple of the orders of x and y.  But embedded in this calculation is an assumption.  The assumption is that xy=yx, that is, that x and y commute.

But in most numerical systems, commutativity does not hold!  In the composition of functions or the multiplication of matrices, the order of the operation is important.  Even in the symmetries of planar objects (such as the rotation of the sheet of paper in the first paragraph), the order of the operations can be important.  (Choose two different lines through the center of the sheet of paper and reflect across each of those lines, one after the other.  In this case the order of line choice effects the final answer.)

What if we are composing functions or multiplying matrices or arranging reflections in the plane?  Now what can we say about the order of a product?  Now it gets interesting!

Consider a Rubik's cube: turn the Right face 90 degrees and then turn the Upper face 90 degrees.  Each individual turn (R or U) has order 4 but their product (UR, for example) has order 105!

We can express this question precisely as follows:

Given ord(x)=a, ord(y)=b, what values of c can occur in the computation ord(xy)=c?  

The Rubik's cube gives an example where (a, b, c)=(4, 4, 105).

We will explore this problem in the next post of this blog.  That exploration leads into group theory, geometry and some interesting combinatorics.

Math is addictive (and useful!)

I do math (every day!) because it is fun.  The projects I propose in this blog are driven by the joy of creativity.  Mathematics is creative!

However, some will ask, "What good is this?" presumably seeking applications beyond just fun.  In this case, I must point out that our entire internet commerce, especially any secure exchange of data on the internet, relies on modular arithmetic!  Pierre de Fermat first observed that if p is a prime number (say, p=13) then the order of any nonzero number modulo p must divide p-1.  Precisely, if a is not divisible by p then

a^(p-1)=1 modulo p.

This is Fermat's "Little Theorem". A century after Fermat, Leonhard Euler then observed that if n=pq is the product of two primes, p and q, then the orders of numbers (that are not divisible by either p or q) must then be a divisor of (p-1)(q-1).  If we know n but do not know p and q, then the unsolved problem of factoring integers in polynomial time can be turned into a public key encryption scheme in modular arithmetic.  The RSA algorithm, based on Euler's observation, is the primary mathematical algorithm in SSL & TLS cryptographic protocols.  Anyone purchasing a song or application over iTunes is using these cryptographic protocols and is therefore applying (deep in the background) a version of Fermat's Little Theorem!   How is that for a mathematical application?!

Next time: Partial solutions to the (a,b,c)-product problem.

[Mathematical prerequisites: This article requires no mathematics beyond high school.]

Follow Ken W. Smith on Twitter @kenwsmith54