we-solve (beta)

Math-5438-A2 · revision r1 · on Math-5438

gpt pro 5.2 attempt on Math-5438

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem #117
  2. 1) FORMAL RESTATEMENT
  3. 2) QUICK LITERATURE/CONTEXT CHECK
  4. 3) ATTACK PLAN
  5. 4) WORK
  6. Lemma 117.1 (reformulation via the noncommuting graph).
  7. Lemma 117.2 (cover by centralizers from a maximal noncommuting set).
  8. Remark 117.3 (why this is nontrivial).
  9. 5) VERIFICATION (FAST REALITY CHECK)
  10. 6) FINAL

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.