Erdős Problem #117

Erdős Problem 117: covering groups by abelian subgroups

Statement and scope

Let $\omega(G)$ be the maximum size of a pairwise noncommuting set. Let $h(n)$ be the least uniform number of abelian subgroups needed to cover every group with $\omega(G)\le n$. Groups may be infinite. The problem asks for good estimates of $h(n)$.

This attempt proves $h(1)=h(2)=1$, $h(3)=3$, and an explicit, very weak bound for every $n$. The sharp estimation problem is unresolved here. These elementary reconstructions revise the earlier GPT-5.2 attempt's restriction to finite groups. The current page https://www.erdosproblems.com/117 records Pyber's much stronger exponential bounds; our general bound does not improve them. The centralizer construction below follows the method of B. H. Neumann, A problem of Paul Erdős on groups, https://doi.org/10.1017/S1446788700019303.

Small parameters

If $x,y$ do not commute, then $x,y,xy$ are pairwise noncommuting. Therefore $\omega(G)\le2$ implies that $G$ is abelian, proving $h(1)=h(2)=1$.

Suppose $\omega(G)\le3$ and $G$ is nonabelian. Choose a maximal noncommuting triple $s_1,s_2,s_3$ and put $H_i=C_G(s_i)$. Maximality gives $G=H_1\cup H_2\cup H_3$, and $s_i$ belongs only to $H_i$.

We first check the elementary three-subgroup structure. For $x\in H_1\cap H_2$, both $s_1s_2$ and $xs_1s_2$ lie in $H_3$, since neither lies in $H_1$ or $H_2$. Their quotient shows $x\in H_3$. Cyclically, all pairwise intersections equal $K=H_1\cap H_2\cap H_3$. If $a,a'\in H_1\setminus K$, then $as_2,a's_2\in H_3$, so $aa'^{-1}\in H_1\cap H_3=K$. Hence $H_1=K\cup Ks_1$; the other two subgroups have the corresponding form.

Every element of $K$ commutes with all $s_i$. If $a,b\in K$ failed to commute, the four elements \[ as_1,\ as_2,\ as_3,\ b \] would be pairwise noncommuting: among the first three the commutation test reduces to that for $s_i,s_j$, and with $b$ it reduces to that for $a,b$. This contradicts $\omega(G)\le3$. Thus $K$ is abelian. Each $H_i=K\cup Ks_i$ is now abelian, so three abelian subgroups cover $G$.

In the quaternion group $Q_8$, the three pairs $\{\pm i\},\{\pm j\},\{\pm k\}$ commute internally and fail to commute across pairs. Thus $\omega(Q_8)=3$, and any abelian cover needs at least three members. This proves $h(3)=3$.

A quantitative finite bound, including infinite groups

Fix $n\ge2$ and put $D=\binom{2n}{n}-1$. Every element $g$ has at most $D$ conjugates. Otherwise choose $\binom{2n}{n}$ elements $t$ with distinct $t^{-1}gt$. The elementary Ramsey bound $R(n+1,n+1)\le\binom{2n}{n}$ gives either $n+1$ pairwise noncommuting $t$'s, or $n+1$ pairwise commuting $t$'s. The first is impossible. In the second case their elements $gt$ are pairwise noncommuting: for commuting $u,v$, the equality $(gu)(gv)=(gv)(gu)$ implies $v^{-1}gv=u^{-1}gu$, a contradiction. Consequently \[ [G:C_G(g)]\le D. \tag{1} \] The Ramsey bound used here follows from $R(a,b)\le R(a-1,b)+R(a,b-1)$ and its boundary values.

There is an abelian common centralizer of at most $2n$ elements. To prove this, inductively maintain pairs $a_i,b_i$ with the $a_i$ pairwise noncommuting, the $b_i$ pairwise commuting, $a_i$ commuting with $b_j$ for $i\ne j$, and $a_i$ not commuting with $b_i$. If their common centralizer $H_j$ is nonabelian, choose noncommuting $a,b\in H_j$ and set \[ a_{j+1}=a b_1\cdots b_j,\qquad b_{j+1}=b. \] All stated conditions persist: in testing commutation with an old $a_i$, the only noncommuting factor is $b_i$, and all other factors commute with both it and $a_i$. Commutation with the old $b_i$ and the new $b$ follows directly. If $H_j$ were nonabelian for every $j\le n$, this would create $n+1$ pairwise noncommuting elements. Thus some $A=H_j$, $j\le n$, is abelian, and $1$ gives \[ q=[G:A]\le D^{2n}. \] Choose $q$ right-coset representatives $R$ for $A$. The subgroup $A\cap C_G(R)$ centralizes both $A$ and $R$, which generate $G$, so it lies in $Z(G)$. Applying $1$ once more, \[ [G:Z(G)]\le qD^q\le D^{\,2n+D^{2n}}. \tag{2} \] Each coset $gZ(G)$ lies in the abelian subgroup $\langle g,Z(G)\rangle$. Therefore $2$ is also an explicit uniform bound for $h(n)$.

Remaining gap

The exact small cases and the general finite cover are proved without assuming $G$ finite. Bound $2$ is far worse than the known exponential estimates. Determining better constants or sharper asymptotics for $h(n)$ remains outside this argument.

COMPLETION ESTIMATE

COMPLETION: 35%

Erdős Problem #117

1) FORMAL RESTATEMENT

Fix $n\in\mathbb N$. Consider (finite) groups $G$ with the property:

Every subset $S\subseteq G$ with $|S|>n$ contains two distinct commuting elements (i.e. $\exists x\neq y\in S$ with $xy=yx$).

Equivalently, the maximum size of a pairwise noncommuting set in $G$ is at most $n$.

Define $h(n)$ to be the least integer such that every such group $G$ can be covered by at most $h(n)$ abelian subgroups. The task is to estimate $h(n)$ as sharply as possible.

2) QUICK LITERATURE/CONTEXT CHECK

From the problem text:

• Pyber proved there exist constants $c_2>c_1>1$ with $c_1^n<h(n)<c_2^n$.
• Erdős notes the lower bound was already known to Isaacs.

No additional results are assumed here.

3) ATTACK PLAN

Translate the covering problem into graph theory via the noncommuting graph, then relate coverings by abelian subgroups to colorings/centralizers.

4) WORK

Lemma 117.1 (reformulation via the noncommuting graph).

Let $G$ be a finite group and define its noncommuting graph $\Gamma(G)$ to be the simple graph with vertex set $V=G$ and an edge $\{x,y\}$ iff $xy\neq yx$. Then:

1. A subset $S\subseteq G$ is pairwise commuting iff it is an independent set in $\Gamma(G)$.
2. The hypothesis "every subset of size $>n$ contains a commuting pair" is equivalent to $\omega(\Gamma(G))\le n$, where $\omega$ is the clique number.
3. If $G$ is covered by $t$ abelian subgroups, then $\chi(\Gamma(G))\le t$.

Proof. $1$ By definition of edges, $S$ has no edges among its vertices iff every pair commutes.

$2$ A clique in $\Gamma(G)$ is a set of pairwise noncommuting elements. The stated property says no set of size $n+1$ is pairwise noncommuting, i.e. the maximum clique size is at most $n$.

$3$ If $G=\bigcup_{i=1}^t A_i$ with each $A_i$ abelian, then each $A_i$ is pairwise commuting and hence an independent set in $\Gamma(G)$ by $1$. Coloring each vertex by an index $i$ with $x\in A_i$ gives a proper $t$-coloring. Thus $\chi(\Gamma(G))\le t$. $\square$

Lemma 117.2 (cover by centralizers from a maximal noncommuting set).

Let $G$ be a finite group and let $S\subseteq G$ be a maximal (by inclusion) pairwise noncommuting set. Then \[ G=\bigcup_{s\in S} C_G(s), \] where $C_G(s)=\{g\in G: gs=sg\}$ is the centralizer of $s$.

Proof. Take any $g\in G$. If $g$ failed to commute with every $s\in S$, then $S\cup\{g\}$ would still be pairwise noncommuting (since $g$ is noncommuting with each element of $S$), contradicting maximality. Hence there exists $s\in S$ such that $gs=sg$, meaning $g\in C_G(s)$. Therefore $g$ lies in the union of the centralizers. $\square$

Remark 117.3 (why this is nontrivial).

Each $C_G(s)$ need not be abelian. So Lemma 117.2 does not directly yield a cover by abelian subgroups, but it shows that small maximal noncommuting sets force $G$ to be a union of relatively structured subgroups.

5) VERIFICATION (FAST REALITY CHECK)

• For $n=1$, the hypothesis says every 2-element subset contains a commuting pair, hence every pair of elements commutes and $G$ is abelian. Then $h(1)=1$.
• In Lemma 117.2, maximality is essential: if $S$ is not maximal, the union of centralizers may miss elements that commute with none of $S$.

6) FINAL

UNRESOLVED.

(i) Strongest fully proved partial result obtained here. Graph-theoretic translation of the hypothesis (Lemma 117.1) and the centralizer covering lemma (Lemma 117.2).

(ii) Exact first gap. Turn the structural information "$\omega(\Gamma(G))\le n$" into an explicit upper bound on the number of abelian subgroups needed to cover $G$ (equivalently, control $\chi(\Gamma(G))$ by $\omega(\Gamma(G))$ within the class of noncommuting graphs).

(iii) Top 3 next moves.

1. Study extremal examples: groups with large noncommuting graphs but bounded clique number (e.g. families of almost-simple groups) to estimate growth rates.
2. Try to prove that each centralizer $C_G(s)$ (or a bounded number of its abelian subgroups) already covers a positive fraction of $G$, giving exponential-type bounds.
3. Translate to bounds on the index of the center or on conjugacy class sizes, since commuting relations are tightly linked to centralizers.

(iv) Minimal counterexample structure. A counterexample to a proposed bound $h(n)\le C^n$ with small $C$ would be a sequence of finite groups $G_n$ with maximal noncommuting set size $\le n$ but requiring more than $C^n$ abelian subgroups to cover them.