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
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.
- (2, 5, 7)
- (2, 5, 9)
- (2, 7, 10)
- (3, 5, 7)
- (3, 5, 9)
- (3, 7, 10)
- (3, 8, 9)
- (3, 9, 10)
- (4, 5, 7)
- (4, 5, 9)
- (4, 7, 9)
- (4, 7, 10)
- (4, 9, 10)
- (5, 5, 7)
- (5, 5, 8)
- (5, 5, 9)
- (5, 6, 7)
- (5, 6, 9)
- (5, 7, 7)
- (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.
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
