# P2646: Largest girth from two generators of SL(2,101)

- ID: `P2646`
- Reference: `max-girth-sl2-101-generators`
- Page: https://theoremdb.org/statements/P2646
- Record maturity: Reviewed problem with recorded work

## Problem

Among ordered pairs \((A,B)\) that generate \(\mathrm{SL}(2,101)\), determine the maximum girth of the undirected Cayley graph with generators \(A,A^{-1},B,B^{-1}\), requiring these four generators to be distinct.

### Problem setup

- **Definition.** Graph girth is the length of a shortest cycle.
- **Remark.** SL(2,101) has 1030200 elements.

### What counts as a solution

- Give a generating pair attaining the maximum, verify its exact girth, and certify every canonical generating-pair class below that value.

## Status

An explicit generating pair attains girth 17, while the degree-four Moore bound rules out girth 25 and above. [1](#reference-1)

## Work

### Evidence for the current status

**Proposition 1 (The maximum girth is currently certified between 17 and 24).** An explicit generating pair attains girth 17, while the degree-four Moore bound rules out girth 25 and above.

Write \(M\) for the maximum in the problem. The pair
\[
A=\begin{pmatrix}69&82\\70&51\end{pmatrix},\qquad
B=\begin{pmatrix}41&48\\47&92\end{pmatrix}
\quad(\bmod 101)
\]
generates all 1,030,200 elements of \(\mathrm{SL}_2(\mathbf F_{101})\), and its undirected Cayley graph has girth exactly 17. This proves \(M\geq17\).

Every graph under consideration is 4-regular on
\[
101(101^2-1)=1{,}030{,}200
\]
vertices. A 4-regular graph of girth at least 25 would contain a tree ball with
\[
1+4\sum_{i=0}^{11}3^i=1{,}062{,}881
\]
distinct vertices. This exceeds the group order, so \(M\leq24\). Together,
\[
17\leq M\leq24.
\]
The upper bound ranges over every eligible pair. The lower-bound computation certifies one pair and does not enumerate simultaneous-conjugacy classes of all pairs.

### Background and intake notes

The group order supplies a universal Moore-bound ceiling, while each pair has an independently checkable breadth-first certificate.

- Original intake status: Status remains unverified. Large-girth Cayley graphs of matrix groups are well studied, but exact optimization at this prime may be absent.
- Quotient pairs by simultaneous conjugacy, inversion, and swapping. Verify generation separately by a full group orbit before accepting a girth incumbent.
- Trap: the first collision between reduced words can contain free cancellation. A breadth-first graph cycle check is needed for the exact girth.

- Recorded example: One girth-17 pair is A=(69,82;70,51) and B=(41,48;47,92), with entries listed rowwise modulo 101.

### Other known results

- **Theorem 1** (established): Girth 25 would require 1,062,881 vertices, which is 32,681 too many. [1](#reference-1)
- **Computation 1** (reproduced): All reduced words through length eight have distinct values, and a reduced relation of length 17 closes. [1](#reference-1)

### Prior approaches

- **Route 1** (inconclusive): The audit found general constructions and random-generator theorems, with no exact optimization at q=101. [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): A standard-library Python program proves generation, injectivity through radius eight, and a closing relation of length 17. [1](#reference-1)

### Computational notes

- One thousand seeded pairs produced the displayed incumbent. Full breadth-first generation reached all 1030200 group elements, and a separate cycle BFS proved its girth exactly 17. The degree-four Moore bound gives a universal upper bound of 24.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `max-girth-sl2-101-generators`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Alex Gamburd, Shlomo Hoory, Mehrdad Shahshahani, Aner Shalev, and Balint Virag, “On the girth of random Cayley graphs”. Random Structures Algorithms 35 (2009), no. 1, 100-117. DOI 10.1002/rsa.20266. arXiv:0707.1833 (2007). Exact lower-bound certificate in mgsl-artifact-word-and-group-verifier; Moore counting argument included here; Gamburd, Hoory, Shahshahani, Shalev, and Virag, On the girth of random Cayley graphs, Section 1 discusses the Moore counting bound; the numerical specialization is shown here; Gamburd et al., Random Structures & Algorithms 35 (2009), 100-117, especially Theorem 8; Lubotzky, Phillips, and Sarnak, Combinatorica 8 (1988), 261-277, DOI 10.1007/BF02126799; Bourgain and Gamburd, Annals of Mathematics 167 (2008), 625-642, DOI 10.4007/annals.2008.167.625 https://arxiv.org/abs/0707.1833
   - Also cited at Exact lower-bound certificate in mgsl-artifact-word-and-group-verifier; Moore counting argument included here
   - Also cited at Gamburd, Hoory, Shahshahani, Shalev, and Virag, On the girth of random Cayley graphs, Section 1 discusses the Moore counting bound; the numerical specialization is shown here
   - Also cited at Reproduced by mgsl-artifact-word-and-group-verifier on 2026-07-25
   - Also cited at Gamburd et al., Random Structures & Algorithms 35 (2009), 100-117, especially Theorem 8; Lubotzky, Phillips, and Sarnak, Combinatorica 8 (1988), 261-277, DOI 10.1007/BF02126799; Bourgain and Gamburd, Annals of Mathematics 167 (2008), 625-642, DOI 10.4007/annals.2008.167.625
   - Also cited at Inline Python 3 computation executed on 2026-07-25
   - preprint; primary source; arXiv:0707.1833, version checked 2026-07-25; checked 2026-08-01
   - Source use: original_summary
   - For Largest girth from two generators of SL(2,101): The maximum girth is currently certified between 17 and 24. An explicit generating pair attains girth 17, while the degree-four Moore bound rules out girth 25 and above. The Moore bound gives a universal ceiling of 24. Girth 25 would require 1,062,881 vertices, which is 32,681 too many. Large-girth literature gives asymptotic context. The audit found general constructions and random-generator theorems, with no exact optimization at q=101.
   - Source named by the research packet.