# Abelian Groups, Mostly

*Simple probabilistic arguments that apply to monoids too*

Famous Mathematicians source |

Niels Abel is of course a famous mathematician from the 19th century. Many mathematical objects have been named after him, including a type of group. My favorites, besides groups, are: Abel’s binomial theorem, Abel’s functions, and Abel’s summation formula. Not to mention the prize named after him, for which we congratulate Robert Langlands.

Today we will talk about commutative groups and a simple result concerning them.

A commutative group is one where the order of multiplication does not effect the value. More formally, for each and in the group

A group with this property is called an *abelian* group. Following our friends at Wikipedia we note that “abelian” is correctly spelled:

Among mathematical adjectives derived from the proper name of a mathematician, the word “abelian” is rare in that it is often spelled with a lowercase “a”, rather than an uppercase “A”, indicating how ubiquitous the concept is in modern mathematics.

## A Simple Fact

The following is a classic but easy fact from group theory.

Lemma 1Suppose that all the elements of a group have order at most . Then is abelian.

For instance, it is one of the first exercises in the famous John Rose book, *A Course on Group Theory*.

What stuck me recently is: could this lemma be optimal? Why do we require *all* elements to have order at most ? Why not change “all” to “most”?

My instant idea was to search for a reference via Google. But at first I could not find anything relevant so I decided to do it myself.

## A DIY Result

So let’s see what we can prove. Since we need some facts about commutative laws in groups, let’s look at a proof of the above lemma.

*Proof:* Suppose that and are in a group and that and and . Then

This shows that is abelian, since and are arbitrary elements.

This proof is “local” in the sense of involving only and , though they range over the whole group. It really is the following rule:

Commute Rule: Let and be so that , , and . Then .

Our next insight is that we need a way to bound how often can hold if a group is not abelian. Luckily this is well studied:

Lemma 2Suppose that is a non-abelian finite group. Define as the probability that two randomly chosen elements and from satisfy . Then .

Our plan is simple: let’s use the Commute Rule in conjunction with this lemma. Here is our argument.

*Proof:* Let for all in a subset of the finite group . Now pick and randomly. If and and are in it follows by the Commute Rule that .

Let be the probability that and and are all in . Thus if is not abelian it follows that

This implies that is not too big.

Let’s bound . This is clearly by the union bound at most

Note, is the complement of the set . Thus we get that is at most

Hence, is at least

This implies that

and so that

Next,

This implies finally that

which means that if the group is not abelian

Thus we have proved:

Theorem 3Suppose that is a finite non-abelian group. Then at most elements of can have order .

## Google Wins

Of course it should be clear that this simple argument must be known. Well, I eventually found via Google search that similar results were indeed long known. However, the proofs of these results were not so simple as the above—at least in my opinion. Of course I have always felt that “clarity” is just another word for “it’s the argument I wrote.”

Here are some of the earlier results. For starters it is known that the “correct” answer is

Here are two references. The abstract of the former says:

One of the first exercises in group theory is that a group in which all non-identity elements have order two (so-called involutions) is abelian. An almost equally easy exercise states that a finite group is abelian if at least of its elements have order two. This cannot be improved, as the dihedral group of order eight, as well as its direct product with any elementary abelian group, provides examples of groups in which the number of involutions is exactly one less than of the group order.

There is also the paper by Bin Fu, “Testing Group Commutativity in Constant Time,” which sharpened some old work with Zeke Zalcstein as I described in this post.

These references all *use* the full power of group theory. Note that our DIY argument merely substitutes using the hypotheses: . Yet it really only misses the optimal answer by a small amount—recall we got . If all we want is to bound away from , then we have succeeded.

More precisely we have shown that we can replace group theory knowledge by randomness arguments. This is a recurrent theme that we have seen before. OK—not all the group theory knowledge: the argument for the “” lemma uses quotients and properties of cyclic groups. But it is simpler than the references for the optimal result. And Ken noticed something else.

## Google Wins Again

Ken noticed that since the equations use no inverses, the DIY argument works equally well in a *monoid*.

What a monoid lacks compared to a group is inverses for every element. Commutative monoids are studied but they are usually called just that, not “abelian.” Most intriguingly, a notion of “almost commutative monoid” crops up in computing—in the theory of concurrent processes. It even has a simpler name with a Wikipedia page: “trace monoid.”

The DIY argument does imply the following: Let be a number such that for any monoid (of a certain kind) in which more than an fraction of pairs commute, the monoid is commutative. Then in any non-commutative monoid (of that kind), the fraction of involutions is at most

At first it was hard to Google for information about whether any with is known. This was mainly because of extensive literature on monoids *plus* an involutive operation that acts on them. An example is the monoid of strings over an alphabet and the operation of reversing a string. You can make such monoids finite by taking strings modulo a Myhill-Nerode type equivalence relation based on a minimal deterministic finite automaton (for instance, identify strings and when they induce the same mapping on states of ). These hits shadowed ones about monoids having involutions as elements.

So we put our non-Google brains to work—and those had the feeling that over *all* monoids there is no such . Ken thought he had a simple proof of this that involved making products of DFAs , but it drove up the proportion of commuting pairs only to .

Finally Google found us two references, the former in 1999 giving non-commutative monoids with , and the latter in 2012 pushing arbitrarily close to . The proof in the latter is not so simple.

## Open Problems

We get and just miss the optimal answer which is . Our proof relies mostly on a well-known fact about groups and the rest is a probabilistic argument. Can we get the optimal result with a finer probabilistic argument? And what happens with probabilistic arguments—

- for other relations on groups besides and ?
- for interesting sub-classes of monoids?
- for other structures?

There’s an error in Lemma 2 — it should say “α ≥ ⅜”. I was puzzled how it can be that Pr[not (x, y commute)] ≥ ⅝ (as stated in the post) implies Pr[x, y commute] < ⅝, but then I checked the link before Lemma 2.

Thanks! I (Ken) actually kept the 5/8 and fixed the other things—which is how it looked…

Why is $Pr[xy \in \bar S] \le |\bar S|/|G|$?

(Or are you not suggesting this?)

Picking $x, y$ uniformly at random does not mean that also $xy$ is uniformly distributed, right?

It does if you’re in a group: in the equation $xy=z$, you can choose any two of the variables and there’s a unique solution for the third. In particular, there are exactly $|G|$ ways of expressing a given $z \in G$ as a product of two elements of $G$.

Indeed. But in a monoid, this objection may be material…

Equality with quaternions?

Lemma 2 applies to x, y selected at random from entire group. You apply it to x,y non-randomlly selected from S (as xy also need be in S). Maybe you should add some explanation as to why this is correct.