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 ${x}$ and ${y}$ in the group

$\displaystyle xy = yx.$

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 1 Suppose that all the elements of a group ${G}$ have order at most ${2}$. Then ${G}$ 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 ${2}$? 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 ${x}$ and ${y}$ are in a group ${G}$ and that ${x^{2}=1}$ and ${y^{2}=1}$ and ${(xy)^{2}=1}$. Then

$\displaystyle \begin{array}{rcl} xyxy &=& 1 \\ xyxyyx &=& yx \\ x y &=& yx. \end{array}$

This shows that ${G}$ is abelian, since ${x}$ and ${y}$ are arbitrary elements. $\Box$

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

Commute Rule: Let ${x}$ and ${y}$ be so that ${x^{2}=1}$, ${y^{2}=1}$, and ${(xy)^{2}=1}$. Then ${xy=yx}$.

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

Lemma 2 Suppose that ${G}$ is a non-abelian finite group. Define ${\alpha}$ as the probability that two randomly chosen elements ${x}$ and ${y}$ from ${G}$ satisfy ${xy = yx}$. Then ${\alpha \le 5/8}$.

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

Proof: Let ${x^{2}=1}$ for all ${x}$ in ${S}$ a subset of the finite group ${G}$. Now pick ${x}$ and ${y}$ randomly. If ${x}$ and ${y}$ and ${xy}$ are in ${S}$ it follows by the Commute Rule that ${xy=yx}$.

Let ${p}$ be the probability that ${x}$ and ${y}$ and ${xy}$ are all in ${S}$. Thus if ${G}$ is not abelian it follows that

$\displaystyle p=Pr[x,y,xy \in S] \le Pr[x,y \text{ commute }] < 5/8.$

This implies that ${S}$ is not too big.

Let’s bound ${1-p}$. This is clearly by the union bound at most

$\displaystyle Pr[ x \in \bar{S}] + Pr[ y \in \bar{S}] + Pr[ xy \in \bar{S}].$

Note, ${\bar{S}}$ is the complement of the set ${S}$. Thus we get that ${1-p}$ is at most

$\displaystyle 3|\bar{S}|/|G|.$

Hence, ${p}$ is at least

$\displaystyle 1-3|\bar{S}|/|G|.$

This implies that

$\displaystyle 1 - 3(|G|-|S|)/|G| \le p < 5/8,$

and so that

$\displaystyle -2|G| + 3|S| < 5|G|/8.$

Next,

$\displaystyle -16|G| +24|S| < 5|G|.$

This implies finally that

$\displaystyle 24|S| < 21|G|,$

which means that if the group ${G}$ is not abelian

$\displaystyle |S| < 7/8|G|.$

$\Box$

Thus we have proved:

Theorem 3 Suppose that ${G}$ is a finite non-abelian group. Then at most ${\frac{7}{8}|G|}$ elements of ${G}$ can have order ${2}$.

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

$\displaystyle |S| \le 3/4|G|.$

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 ${3/4}$ 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 ${3/4}$ 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: ${yx = yxxyxy = yyxy = xy}$. Yet it really only misses the optimal answer by a small amount—recall we got ${7/8}$. If all we want is to bound ${|S|}$ away from ${|G|}$, 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 “${5/8}$” lemma uses quotients and properties of cyclic groups. But it is simpler than the references for the optimal result. And Ken noticed something else.

Ken noticed that since the equations ${yx = yxxyxy = yyxy = xy}$ 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 ${a}$ be a number such that for any monoid (of a certain kind) in which more than an ${a}$ fraction of pairs commute, the monoid is commutative. Then in any non-commutative monoid (of that kind), the fraction of involutions is at most

$\displaystyle \frac{a+2}{3}|G|.$

At first it was hard to Google for information about whether any ${a}$ with ${\frac{5}{8} \leq a < 1}$ 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 ${M}$ (for instance, identify strings ${x}$ and ${y}$ when they induce the same mapping on states of ${M}$). 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 ${a < 1}$. Ken thought he had a simple proof of this that involved making products of DFAs ${M}$, but it drove up the proportion ${k}$ of commuting pairs only to ${k + o(1)}$.

Finally Google found us two references, the former in 1999 giving non-commutative monoids with ${K > 5/8}$, and the latter in 2012 pushing ${k}$ arbitrarily close to ${1}$. The proof in the latter is not so simple.

## Open Problems

We get ${7/8}$ and just miss the optimal answer which is ${6/8=3/4}$. 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 ${a^2 = 1}$ and ${ab = ba}$?

• for interesting sub-classes of monoids?

• for other structures?

1. September 14, 2018 3:41 pm

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.

• September 14, 2018 4:33 pm

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

September 15, 2018 6:03 am

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?

September 16, 2018 6:21 pm

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$.

• September 17, 2018 11:56 am

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

3. September 17, 2018 6:20 am

Equality with quaternions?