A diameter bound for finite simple groups of large rank

Arindam Biswas, Yilong YangJ. Lond. Math. Soc 2017 · OpenReview

TL;DR

This paper tackles the problem of bounding the "diameter" of finite simple groups of Lie type, which is a measure of how efficiently elements can be generated. The authors provide a new, improved bound that depends more favorably on the group's rank, particularly for groups with large ranks and bounded base fields. This work advances our understanding of the structure and connectivity of these fundamental mathematical objects.

What Problem Does This Paper Address?

The study of finite simple groups, the building blocks of all finite groups, is a central theme in mathematics. A key question is understanding how "connected" these groups are, which is often quantified by the diameter of their Cayley graphs. Given a group $G$ and a generating set $S$, the Cayley graph $\Gamma(G, S)$ has vertices representing elements of $G$, and edges connecting elements that differ by a generator from $S$. The diameter of this graph is the maximum shortest path distance between any two elements in $G$.

A long-standing conjecture by László Babai suggests that for any non-abelian finite simple group $G$ and any symmetric generating set $S$, the diameter of $\Gamma(G, S)$ should be bounded by $(\log |G|)^{O(1)}$. While progress has been made for specific families of groups or for groups with bounded rank, the case of finite simple groups of Lie type with large rank has remained challenging. Previous results often had dependencies on the rank that were too strong, limiting their applicability. This paper aims to provide a better bound for these large-rank groups.

Methods

The paper employs a sophisticated combination of algebraic and number-theoretic techniques. The core strategy involves:

  • Finding "t-transversal sets": These are subsets of the group that can "extend" linear or isometric embeddings of smaller subspaces. This is a generalization of the concept of transitivity in permutation groups. The authors develop these sets for various types of groups (linear, symplectic, unitary, orthogonal).
  • Constructing "P-matrices": These are matrices with specific properties related to roots of unity as eigenvalues. The key idea is that powers of these matrices can have significantly reduced "degree" (related to the dimension of the image of $A-I$). This "degree reduction" is inspired by earlier work and is a crucial step.
  • Leveraging Commutators and Repeated Degree Reduction: The authors use commutators with elements from t-transversal sets and repeatedly apply the degree reduction technique. This process, combined with results on the order of matrices, allows them to construct elements of very small degree.
  • Conjugacy Expansion: Once an element of small degree is found, the paper utilizes results from Liebeck and Shalev, which state that elements of small degree can generate the entire group through conjugation. This allows them to bound the diameter of the group.
  • Number Theory Tools: The proof relies on inequalities involving primes, particularly from the work of Fouvry, to establish bounds on the number of primes with certain properties. These number-theoretic results are essential for controlling the parameters in the algebraic constructions.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Rank and Connectivity: The paper's main contribution is showing that the diameter bound can be made to depend more favorably on the rank ($n$) and the size of the base field ($q$) for finite simple groups of Lie type. This is a significant step towards understanding the structure of these groups.
  • The Power of Degree Reduction: The technique of finding matrices with specific root-of-unity eigenvalues and then reducing their "degree" through matrix powers is a central theme. This allows for a systematic way to construct "small" elements.
  • Generalizing Transitivity: The concept of "t-transversal sets" is a powerful generalization of transitivity, allowing the authors to build up group elements from embeddings of smaller subspaces.
  • Interplay of Algebra and Number Theory: The paper beautifully illustrates how deep results from number theory (prime number theorems, inequalities on primes) are crucial for establishing bounds in abstract algebra and group theory.

Key Results

The main result is a new diameter bound for finite simple groups of Lie type with rank $n$ and base field $\mathbb{F}_q$. Specifically, the diameter is bounded by:

  • $q^{O(n(\log n + \log q)^3)}$ for general finite simple groups of Lie type.
  • $exp(O(n(\log n)^3))$ for the case where the base field has a bounded size.

This bound improves upon previous results by making the dependency on the rank $n$ more manageable. The paper also provides detailed constructions and proofs for various types of groups (linear, symplectic, unitary, orthogonal) and establishes intermediate results on t-transversal sets and P-matrices.

Limitations and Future Work

  • "Modest" Upper Bound: The authors describe their bound as "modest," suggesting that further improvements might be possible.
  • Dependency on Rank: While improved, the bound still depends on the rank $n$. The ultimate goal is to achieve a bound that is independent of $n$ (or depends only logarithmically on $n$), as conjectured by Babai.
  • Assumptions: The results rely on certain assumptions, such as the size of the base field or the rank being "large."
  • Future Directions: The paper implicitly suggests that further refinement of the number-theoretic inequalities and algebraic constructions could lead to even tighter bounds. Exploring the implications for spectral gaps and mixing times of Cayley graphs is also a natural extension.

Summary updated

BibTeX
@article{biswas2017diameter,
  author = {Arindam Biswas and Yilong Yang},
  title = {{A diameter bound for finite simple groups of large rank}},
  journal = {J. Lond. Math. Soc.},
  year = {2017},
  url = {https://openreview.net/forum?id=tYVOUZUQEE},
}
Figure