Strongly regular graphs, I

Strongly regular graphs

Strongly regular graphs "stand on the cusp between the random and the highly structured", says combinatorialist Peter Cameron.  The conditions for the existence and the construction of strongly regular graphs provides a rich source of mathematical investigation, with many applications to algebra, linear algebra and combinatorics.

A graph is regular if every vertex has the same degree.  Let's use the letter k for the degree of our regular graph.

A regular graph is strongly regular if the number of walks of length 2 between two different vertices depends only on the adjacency of the two vertices.  We let  lambda  count the number of paths of length 2 between adjacent vertices and set  mu  as the number of paths of length 2 between non-adjacent vertices.

Given adjacent vertices x and y (in the figure below), the parameter  lambda  counts the number of vertices z adjacent to both.

But if x and y are not adjacent (below), mu counts the number of vertices z in this second configuration.

The parameters of a k-regular graph on v vertices are written as a 4-tuple (v, k, lambda, mu).  The graph below, on 9 vertices, with degree 4, is an example of a (9, 4, 1, 2) strongly regular graph (SRG.)  Each edge (adjacent pair) is on exactly 1 triangle, but each nonadjacent pair form the opposite corners of a 4-cycle and so there are mu=2 walks of length two between the nonadjacent vertices.

The Petersen graph, below, is an example of a (10, 3, 0, 1) SRG.

It is possible for mu and lambda to be equal.  Here (below) is the Shrikhande graph, an SRG with parameters (16, 6, 2, 2).  (This graph was found by S. S. Shrikhande.  I was privileged to work for some time at Central Michigan University with Mohan Shrikhande, son of S. S. Shrikhande.  Both father and son live in Mt. Pleasant, Michigan.)

There is (of course) a nice Wikipedia article on SRGs.  The drawing, above, have been copied from that article.

Fundamental existence question & conditions

A fundamental question in the study of strongly regular graphs is simply, "For which parameters (v, k,  lambda, mu) does there exist a SRG?"  The current progress on this question can be summarized in the tables kept by Andries Brouwer in Eindhoven, Netherlands.  

One first step to eliminating false parameter sets is the "First feasibility condition" created by counting ordered pairs of vertices (y, z) in the configuration below.

We fix the vertex x and count vertices y, z where x and y are adjacent, as are y and z, but x is not adjacent to z.  Given x, there are k choices for the vertex y and then k-lambda-1 choices for z.  (There are k vertices adjacent to y but one of those is x and there are another lambda which are adjacent to x.  Throw those out....)  So, given x, there are k(k-lambda-1) configurations like that, above.

On the other hand, given x, we can hunt for vertices z first -- there are v-k-1 choices for z -- and then hunt for y -- there are mu choices for y once we find z and so there are (v-k-1)mu  configurations like that, above.

Since we got two results for the same count, we know they must be equal and so we have the following condition on the parameters (v, k, lambda, mu) of a SRG:

k(k-lambda-1) = (v-k-1)mu

This is the "first feasibility condition" for SRGs.  There are a few more feasibility conditions, involving more subtle arguments.  We will explore two of those in a later post.

Open parameter sets

Meanwhile, just so one realizes that there are LOTS of open questions on strongly regular graphs, we mention a few "existence" questions here.  It would be very nice to either construct or rule out SRGs with the following parameters:

(65, 32, 15, 16)

(69, 20, 7, 5)

(75, 32, 10, 16)

...

(96, 35 10, 14)

(96, 45, 24, 18)

(99, 14, 1, 2)

(100, 33, 8, 12)

...

(120, 35, 10, 10)

...

(144, 52, 16, 20)

...

(160, 54, 18, 18)

(162, 21, 0, 3)

...

Of the many open cases, I have pulled out in the list above, the parameters that I (and others) find most interesting.  Most of these cases are quite hard and the discovery of a single graph in the list above would be a publishable paper!  (Write me!  Did I mention my Erdos number is 2?!)

All strongly regular graphs on 64 or fewer vertices have been found by exhaustive computer search by Ted Spence.  One might note that there are exactly 32548 distinct (nonisomorphic) graphs with parameters (36,15,6,6).

I have worked pretty hard on the parameter set (99,14,1,2).  A doctoral dissertation in computer science by Majid Behbahani (2009, here in pdf) attempts the most obvious constructions for this strongly regular graph and does not find it.  This does not rule out this SRG but makes it clear that a construction will be somewhat unusual.  In the same vein, Makhnev and Nosov describe a search for the graph (162,21,0,3).   I've also looked into (120,35,10,10) and (160,54,18,18); in both cases there is no abelian Cayley graph with these parameters.  (More on that later.)  

A strongly regular graph with parameters (3250,57,0,1) is an example of a Moore graph.  Many of us in algebraic combinatorics have looked for that graph and it still eludes us.

It turns out that the most powerful tools for the study of strongly regular come from linear algebra.  That will be the subject of the next post.

Next time: The MERiT conference & undergraduate research.

[Mathematical prerequisites: This article requires a basic introduction to graph theory.]

Follow Ken W. Smith on Twitter @kenwsmith54

Feeding a Family of Four

A statistics student, some time back, posted on Facebook a joke about (1) a large pizza, (2) statisticians, (3) applied mathematicians and (4) theoretical mathematicians.  The punch line was that the first three could each "feed a family of four." 

At the time, the joke seemed to be aimed at “the other half” of our department program, at our students in theoretical (pure) mathematics. As  graduate coordinator in our pure math program, I took the post a little personally.  My frustration with the joke was not just that it seemed to say, “We [stat students] are better than you — we will get jobs and you won’t!” but that it was simply wrong.  

There seems to be a strong demand for students in a theoretical (or “pure”) math program, but a popular belief in our cultural is that all mathematicians ever do is teach.  

Why hire theoretical mathematicians?

A mathematician learns to solve a vague, fuzzy problem by organizing the problem into a coherent form and then using various tools to attack this coherent problem.  Since every problem begins with a vague, poorly defined stage, these problem-solving tools are valuable in industry and in applied mathematics, even if the original training is theoretical.  

Higher education often trains people to be specialists, to be excellent in a narrow field. This can be very good.  We need chemical engineers, actuaries, statisticians, mathematical biologists, petroleum engineers … and nurses and doctors.  But training in theoretical mathematics tends to avoid this specialization, concentrating instead of deep understand of general mathematical principles.  This creates a certain tension in the job market — do companies prefer a specialist, assigned to a particular task, or a generalist who is good at solving problems of all types?  It depends….

From my experience, both specialists and generalists have their place, but it is foolish to require education to focus on a single small specialty.

An undergraduate student timidly knocked on my office door one afternoon, several years ago.  I invited her in and she began to discuss her “problem.”  She liked math but didn’t want to teach.  Her dad wanted her to be a chemist because he wanted her to have a real job (like he did.)  He was convinced that if she pursued her desire to major in math then she would have to be a teacher if she wanted to have a paycheck.  After we chatted a bit, I wrote her a long email (meant to be read by dad) that laid out all the various job opportunities available in mathematics.  Eventually she majored in math, did an undergraduate research project in statistics (yes, statistics!) and received a large fellowship to pursue doctoral studies at a major university.  Yes, you can love mathematics and get paid a lot of money.  (And no, you won’t be teaching.  Obviously if you are making a lot of money, you are not teaching....)

One of our graduate students had a similar problem.  Her father worked for a major international corporation which builds agricultural machinery.  He wasn’t very eager for his daughter to get a masters degree in mathematics because he wanted her to get a job after school.  The delightful part of this story is that after her masters degree, a certain company interviewed her and, due to her mathematical training, offered her a job with a salary higher than her father’s.  What company was interested in her mathematical training? The same company that her dad worked for!   (It was just a different branch.)

Around 1990, I spent a year at the National Security Agency (NSA) as part of a mathematical sabbatical.  The National Security Agency has literally thousands of mathematicians working there (probably over ten thousand -- but the exact number is classified.)  Outside the NSA there are more thousands of mathematicians working for the various defense contractors such as Westinghouse.  (There are also defense contractors in other parts of the country, including Texas.)

Our cell phone technology would not exist without the mathematicians who design the codes to carry the digital signals.  Our internet commerce would not exist were it not for the mathematicians who designed the public key encryption schemes that allow us to securely exchange information through computer servers.

How is this related to undergraduate research?

Underneath the belief that "all you can do with math is teach it", is a belief that mathematics is a dead subject.  Vibrant, growing fields require that people engage in that field; dead, stagnant subjects only have room for teachers.

There are a variety of ways to emphasize the explorative processes in the growing field of mathematics.  Certainly one of the best ways to communicate the living nature of mathematics is to get students engaged in research in the subject!

Some resources

Here I've tried to collect some online sources that talk about the importance of mathematics and its value is science and society.


A recent NPR article describes the search for mathematicians to analyze big data.

A Wall Street Journal article describes the career of mathematician as one of the top, most desired jobs.

One of my favorite blogs to read is FutilityCloset; the blog has an interesting story, "Augury", on the connections between math and science.

Stanford mathematician, Keith Devlin, teaches a MOOC on mathematical thinking.

The Mathematical Association of America has some webpages devoted to the question, "What can I do with a math major?"  Here are some of the sample careers off of the MAA web page:

http://www.maa.org/careers/denbleyker.html  (Janet denBleyker -- actuary)

http://www.maa.org/careers/sford.html 

http://www.maa.org/careers/monticino.html

http://www.maa.org/careers/murray.html (Math major whose interests led him into computer science)

http://www.maa.org/careers/lentz.html  (Biostaticians whose interests led her on to a Ph.D. in animal science)

http://www.maa.org/careers/stabbe.html (Math major whose mathematical training eventually lead him to law school.)

Mathematicians are sought after in almost every area of industry.  The US government has been trying to fix the "crisis" in math and science for some time.  Earlier in this decade (about 2005) Congress had a committee look into the decline in American capabilities in science and technology.  The result was a report, "Rising Above the Gathering Storm: Energizing and Employing America For A Brighter Economic Future."  That report suggested some significant changes in the way the US prepares people for industry.  The top suggestion, coming from that investigation, addressing the country's greatest need, was:  "Action A-1: Annually recruit 10,000 science and mathematics teachers by awarding 4-year scholarships and thereby educating 10 million minds."

The reason for making STEM teaching a top priority is simply that we don't have enough people trained in science and math for the country's needs.  And to get good mathematicians, we need more math teachers!  Now, a lot of people have focused on the "teaching" part of this statement, but the reason the report mentions teachers is because the country desperately needs their students!  There are NOT enough math majors in this country for the jobs we have!

Next time: COURI & EURECA, promoting undergraduate research across campuses.

[Mathematical prerequisites: This article requires no mathematical background.]

Follow Ken W. Smith on Twitter @kenwsmith54

Randomly decomposable graphs, I

The study of "randomly decomposable graphs" requires almost no mathematical background but can quickly lead to some interesting questions whose solutions require hard work and creativity.  I enjoy introducing this research area to students without a deep college math background.  Once the students become intrigued with this problem, they are ready to explore some other, deeper subjects!  (We will explore other, much deeper math topics in later blog posts.)

Edge decompositions of graphs

A graph, such as the cycle of 4 vertices, can be decomposed into two edge-disjoint copies of the path of length two.

This can be done is several different ways.

The bipartite graph K_{2,3} can be decomposed into three edge-disjoint copies of the path of length two.

But when we attempt to decompose this graph with six edges into three copies of the path of length two, we have to be careful how we do it.  If we start wrong, we may discover that we cannot finish the decomposition into three graphs all of which are paths.  For example, in the drawing below, we might remove the blue path of length two and then the black path of length two.  When we do that, we are left with the two reds edges which are not a path!

A general question in the decomposition of graphs begins with a fixed graph H and a larger graph G, where the edges of the graph G can be colored in such a way that each subgraph of a fixed color is isomorphic to H.  If H is the path of length two, all of the examples above give decompositions of a larger graph G into copies of H.

If the subgraph H has q edges then the number of edges in an H-decomposable graph G will be a multiple of q, say e=qa.  The integer a indicates the height of the graph G as a collection of copies of H.  The graph H, itself, has height 1; put together two copies of H to get a graph of height 2, and so on.  The cycle C_4 in the first drawing, above, has height 2 as a P_2-decomposable graph while K_{2,3} has height 3.

The theory of edge decompositions of graphs is a large field of mathematical research.  One may find it the subject of blog posts (here). There is at least one book (by ) published on the subject (which I found in my university library) and there is a study of infinite graphs and their simplicial decompositions (by Diestel).  A nice introduction to the subject is in this brief survey paper (pdf) by Fan Chung and Ron Graham.

Randomly decomposable graphs

If G is decomposable into edge-disjoints copies of a graph H then we say G is H-decomposable.  A partition of edges, each partition giving the subgraph H, is call an H-decomposition.

In 1985, the Chilean mathematician Sergio Ruiz dealt with questions about graphs decompositions which remain decompositions even when the target subgraph H is "randomly" (or "thoughtlessly") removed.  Given a fixed graph H, which graphs G are not just decomposable into copies of H but are decomposable in such a way that the decomposition cannot be "messed up".

For example, the cycle C_4 in the top picture is randomly decomposable into copies of H=P_2 while the bipartite graph K_{2,3} in the second and third pictures, is decomposable into copies of P_2, but is not "randomly" decomposable.  The third picture shows a decomposition which fails.

The formal definition of randomly decomposable is the following.  A graph G which is decomposable into copies of H is said to be randomly decomposable if the removal of the edges from any disjoint collection of copies of H leaves a graph which is still H-decomposable.  We say that G is an RDG with respect to H.

For example, if H=P_2 is the path of length 2 then the graph G=K_{2,3} fails the "randomly" decomposable requirement since if we remove -- in the third picture -- the black path 3-2-4 and the blue path 3-1-5, we get a graph which does not even involve a copy of H.  So also C_4 is RDG with respect to P_2, the graph K_{2,3} is not.

We can create a recursive definition equivalent to the one given above.  (The first definition, above, is due to Ruiz.)  The recursive definition defines the graph H to be "randomly" decomposable (of course) and then defines a graph G to be randomly decomposable if the removal of any copy of H leaves a randomly decomposable graph.  This recursive definition suggests that we construct randomly decomposable graphs beginning with graphs of low height and adding copies of H, checking the "randomly" condition as we go.

Let us construct graphs which are randomly decomposable with respect to H=P_2, the path with just two edges.  Pick a copy of H and label the vertices 1, 2 and 3 and assume the edges are {1,2} and {2,3} (so that H is the path 1-2-3.) Now take a second copy of H and assume the vertices are labelled a1, a2, a3 with a1 adjacent to a2 which is adjacent to a3. We may construct various P_2-decomposable graphs of height 2 by identifying certain vertices from the two copies.

First, if the vertices 1, 2, 3, a1, a2, a3 are all distinct, then the graph G is just two disconnected copies of H and so is clearly randomly decomposable.

If we identify the vertex 2 with the vertex a2 then we get the "star" with center 2 and end vertices 1,3, a1, a3.  This graph, often written K_{1,4}, is randomly decomposable.

If we identify the vertex 1 with a1 and the vertex 3 with a3, we instead get the 4-cycle drawn in the first figure. This graph is randomly decomposable.

One can consider other ways to put together two copies of H=P_2, but all of those choices lead to graphs which although decompose into copies of P_2, do not decompose randomly!  For example, if we just identify the vertices 1 and a1, we get a path 3-2-1-a2-a3 of length 4.  This graph is not randomly decomposable since we could remove the path 2-1-a2 and be left with a graph which is not isomorphic to H.

Randomly decomposable graphs where H is a path

When I first heard Sergio Ruiz speak on this topic, I thought it should be fairly easy to find all randomly decomposable graphs in which the subgraph H is a path.  But that turned out to be more complicated than I believed.  For example, suppose H is a path of length 7.  Then the graphs in the figure below are all RDG with respect to H.  And this is just height 2!!

I offer a brief exercise to test these RDG ideas, prior to my next post:

Find all graphs which are RDG with respect to the path of length 3 and have height two.  (Feel free to stop at height two, using just two copies of P_3.)  

I will give the solution to that exercise next time.

Next time: Randomly decomposable graphs, 2 (paths and related subgraphs)

[Mathematical prerequisites: This article requires a basic introduction to graph theory (as seen in the previous blog post).]

Follow Ken W. Smith on Twitter @kenwsmith54

Finite graphs, an entry point for undergraduate research

Many undergraduate research projects delve into areas of graph theory.  Graph theory is a relatively recent area of mathematical research, driven by questions in computing and computer algorithms.

A simple graph consists of a finite set V of vertices, along with a set E of edges, where edges are unordered pairs of vertices.  A simple example might be a set of five people {Alexus, Bernard, Chloe, Dazi, Emily} on Facebook; the set of edges here would represent (Facebook) friendship, so that if Alexus and Bernard were friends, {Alexus, Bernard} would be an "edge."

Finite graphs are the building blocks of discrete structures and their study has applications to modern technology, computer algorithms, discrete systems, ... any finite structures in the modern computer age. Anyone working with computer algorithms must have some understanding of graph theory!

"Simple" graphs have undirected edges (there is no direction to "friendship", it is presumably a symmetric relations) and there are no multiple edges (one can't be "friends" twice on Facebook!) and there are no loops (one is a "friend" of someone else, not oneself.)  Since these simple graphs were first systematically studied and promoted by Frank Harary at the University of Michigan, they are sometimes called Michigan graphs.

Here are the four different graphs with three vertices:

And here are the graphs on four vertices.

What makes two graphs "the same"?  This is a mathematical question about functions.  A graph on vertex set V_1 with edge set E_1 is isomorphic to ("the same as") another graph on vertex set V_2 with edge set E_2 if there is a one-to-one onto function (bijection) from V_1 to V_2 which maps the edge set E_1 onto the edge set E_2.  

Given a single graph with vertex set V and edge set E, a one-to-one function from V onto V is a permutation.  If the permutation maps E onto E, is is an automorphism of the graph.  Given a fixed graph G(V,E), the collection of automorphisms of the graph form a group of permutations.

There are a large number of interesting questions which can be posed about graphs, many of them surprisingly difficult.  A very old problem, dating from the 1800's, is the four coloring problem for planar graphs solved only by exhaustive computer search in 1976.  A more difficult problem (involving lots of active research) asks for an algorithm which distinguishes between different (non-isomorphic) graphs.  At this time there is no known list of graph invariants that is guaranteed to always separate two non-isomorphic graphs.

A graph has a collection of symmetries, that is, a group of automorphisms, which permute the vertices of the graph without changing the collection of edges.  The structure of this automorphism group says a lot about the structure of the graph; in a similar way, every finite group may be viewed as the automorphism group of some graph.  Many questions in finite group theory can be phrased in terms of interesting combinatorial structures such as finite graphs.  And, conversely, many interesting questions in graph theory lead to interesting questions in algebra, in group theory, ring theory and linear algebra.

Since graphs are finite and since it is relatively easy to create a list of examples, this is a fertile area in which to engage undergraduates in mathematical exploration.  Future posts will attempt to lay out some interesting research problems.

Next time: A project in randomly decomposable graphs.

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

Follow Ken W. Smith on Twitter @kenwsmith54

A hike in the Himalayas (& directing undergraduate research)

A hike in the Himalayas

In the previous post I suggested six attributes of a good undergraduate research problem. I claimed that a good research problem for undergraduates

1. should be accessible,
2. has "legs",
3. leads to higher math,
4. dreams of mathematical heights,
5. uses "magic",
6. offers alternatives.

In this post I review those characteristics using a common metaphor.

I have never been to the Himalayas.  My wife and I used to backpack in the Colorado Rockies and so I've dreamed about seeing the Himalayas someday.  (Is this a "bucket list" goal?  Possibly.)  Suppose instead of just visiting the Himalayas, one were to truly explore the Himalayas -- not just hike on well-worn trails, but really go into the backcountry and find new trails to build, new peaks to climb, new rivers to raft!

What would this involve?  It would be good to have a guide, a person with local experience, who can suggests areas to explore and who has some understanding of the paths into the wilderness.

Now let's turn the story around.  Suppose that you are the local guide.  What does it take to give your visitor, your client, a good wilderness experience?

I will offer six characteristics of a good guide to the Himalayas.  (If I were to ever get an opportunity to truly explore the Himalayas, here is what I would expect my guide to be able to do.)  These six characteristics deliberately parallel the six characteristics of a good problem from the previous post.

Frankly, I know a lot more about finding good math problems than I do about hiking in the Himalayas.  Still, this is my blog and the Himalayas are my dream so....  (If one prefers a slightly different metaphor, imagine hunting for new snowboarding routes in the Grand Tetons.  Now there is some exciting "research"!)

A good guide meets the trekker client where they are and helps them acclimate

As you (the good guide) meet your trekker customer, you want to assess their abilities and help them acclimate to the mountains.  Begin with some small hikes as your guests adjust to altitude and to the hiking experience.  A good guide knows of nice hikes that are safe and part of a larger experience.  Of course, these hikes are not themselves explorations -- they are just serious walks in the mountains.  Many people have traveled these trails before.  But these introductory hikes set the stage for future exploration.

Be prepared for a serious expedition

As your hiking customer gains experience, he/she will want to do some serious exploration.  Be prepared to lead that trip.  Know the equipment necessary; have access to good resources; be ready to take healthy, energetic explorers deep into the wilderness.

Sure, there are other guides who can take people on enjoyable walks.  But your customers want to explore new territory.  You should have ideas on where to go and how to begin the trip and you should be ready to take them as far as they are capable of going.

Take your clients to interesting places

As you, the expedition guide, adjust to your customers, you want to show them some interesting sights.  It is not enough to hike ten miles somewhere, set up a tent, walk around for a few days and then hike back.  You want them to enjoy their experience and return again to the mountains.  So you should be able to say, "Beyond that ridge is a range of high peaks.  Let's climb that ridge and then see what might be reachable on the other side."

If this is a genuine expedition, you may not know what is on the other side, but you have some ideas.  There are some big mountains out there and so there are lots of interesting smaller ones!

Plan your trip so that your customers ooh and ahh at the scenes they encounter.

Even if you can't climb the top peaks, can we get good views of them?

I don't plan on climbing Mt. Everest.  But if I were hiking in the Himalayas, I would like one day to come around a corner and hear my guide say, "See, there, on the left, that faraway mountain with the plume?  That's Everest."

I've hiked in Colorado and I enjoyed the high peaks there.  So why go to the Himalayas?  Because of Everest.  I don't need to climb Everest myself, but that highest of all peaks draws thousands of visitors to Nepal every year, just so they can see it!

A good guide uses all available resources

Sherpa guides on Everest sometimes climb the mountain without access to fixed ropes or manmade bridges.  But if I have a guide in the Himalayas, I want him (her) to be able to guide me to bridges across ravines, bolted ladders up steep faces, any type of equipment that will help me get further into the wilderness.  As a visitor and guest, I need these manmade (magical?) aids and I hope my guide will not be shy about offering them.  (Indeed, I will surely need an occasional gasp from an oxygen tank, long before we reach even 20,000 feet in elevation!)

A good guide suggests offers alternatives

So I'm not climbing Everest.  But I'd like to climb some ridges and hills, maybe a smaller, gentler peak.  A good guide will have an idea where those are and how to get there.  As the hike goes on, the good guide will recognize the customers' abilities and limits and will be prepared to suggest alternate goals for the expedition.

Find a photo opportunity, a place where all of us can stand together, squeezed into a single frame and later say, "See, I was there!  [I didn't climb Everest but] I climbed this peak!"

"Climbing" the (a,b,c) order-of-products problem

Let's apply the last two posts (on good research problems and good hiking experiences) to the (a,b,c) order-of-products problem (posted Aug 26 & 29.)

The order-of-products problem begins with a simple question from geometrical symmetry or modular arithmetic.  These are ideas often taught in high school and certainly accessible to high school students.  So this problem has some nice entrypoints; there are good ways for undergraduate students to access this problem and acclimate to the mathematics needed.

The order-of-products problem leads fairly quickly to some elementary group theory and then seems to eventually require an understanding of group homomorphisms and subgroup structure, including Sylow Theorems.  It connects with Coxeter groups and groups of Lie type.  So it seems to lead to some interesting higher level problems.  In a search of the literature, I have not yet found any place where this problem is attacked in this generality, although there are places where versions of the problem have been solved.  So this problem seems to lead to some "high peaks" of mathematics and so should take researchers some distance.

I'm not aware of any big conjectures associated with the order-of-products problem.  I do not see an "Everest" on the horizon.   But this may be due to the fact that this problem is not directly in my area of research.  If I am to direct this problem further, I am uncomfortable with the fact that I don't personally know the tools used in creating finite groups.  Maybe I am not the best "guide" for this problem?  A better guide would probably know more about reflection groups, finite Coxeter groups and similar topics in group theory with a "geometric" flavor.

But I do see some smaller peaks; just the existence of triangle groups in hyperbolic geometry seems like an interesting "mountain range" to explore.  So, until better guides come along, I can take students for a good long walk in the mountains!

As students adjust to the order-of-products problem, they can use computer software (like GAP or Sage, which are free) and I am quite willing to give students "magical" results about simple groups and Sylow theorems.

All in all, the order-of-product problem seems like a good, but not great, problem for students.  This problem might be a good B level undergraduate research problem; if I am the director of this exploration, my lack of experience in the finite group theory probably puts the potential of this problem as a B- or C+.

Summary

Imagine breaking new trails across a secluded mountain valley, rafting an unexplored section of a river, or taking your snowboard down a virgin mountain slope.  That is exciting!  Every explorer, every wilderness guide, began as a novice enjoying smaller, safer trips.  Let's get our undergraduate students into short (mathematical) wilderness trips and see if they will catch on to the excitement of the mathematical quest.

Next time: Graph theory as one source for good undergraduate math problems.

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

Follow Ken W. Smith on Twitter @kenwsmith54

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