# P2738: Prime exceptions to connectivity of the Markoff graph

- ID: `P2738`
- Reference: `markoff-graph-prime-connectivity-exceptions`
- Page: https://theoremdb.org/statements/P2738
- Record maturity: Reviewed problem with recorded work

## Problem

For each prime \(p\), let \(G_p\) be the graph whose vertices are the nonzero triples \((x,y,z)\in\mathbb F_p^3\) satisfying \(x^2+y^2+z^2=xyz\). Join two vertices when one is obtained from the other by one of the three Vieta involutions \((x,y,z)\mapsto(yz-x,y,z)\), \((x,y,z)\mapsto(x,xz-y,z)\), or \((x,y,z)\mapsto(x,y,xy-z)\). Determine whether \(G_p\) is connected for every prime \(p\), and if it is not, determine every exceptional prime.

### Problem setup

- **Definition.** A nonzero triple means a triple other than (0,0,0); individual coordinates may be zero.
- **Remark.** Connectivity is ordinary graph connectivity using only the three stated involutions as edges.

### What counts as a solution

- Prove that G_p is connected for every prime p, or exhibit an exceptional prime and two certified components.
- If an exceptional prime is found, give complete component data or a machine-checkable certificate that no sequence of the three stated involutions joins the selected representatives.

## Status

Let T=(863#)(53#)(13#)(7#)(5#)3^3 2^5. The graph G_p is connected for every prime 5 <= p < 1,000,000 and every prime p > T; this packet also certifies 40,066 primes with 10,000,000 < p <= 20,000,000. The unresolved p >= 5 cases are the primes in 1,000,000 <= p <= T outside the individual certificates recorded or cited here. Literally, G_2 is connected and G_3 has no vertices, so p=3 still needs a null-graph convention. [2](#reference-2)

## Work

### Evidence for the current status

**Proposition 1 (Connectivity is proved below one million and beyond an explicit threshold).** Let T=(863#)(53#)(13#)(7#)(5#)3^3 2^5. The graph G_p is connected for every prime 5 <= p < 1,000,000 and every prime p > T; this packet also certifies 40,066 primes with 10,000,000 < p <= 20,000,000. The unresolved p >= 5 cases are the primes in 1,000,000 <= p <= T outside the individual certificates recorded or cited here. Literally, G_2 is connected and G_3 has no vertices, so p=3 still needs a null-graph convention.

Brown's Theorem 2 and exhaustive data establish connectivity for every prime \(p<1{,}000{,}000\). Theorem 1.4 of Eddy, Fuchs, Litman, Martin, and Tripeny establishes connectivity for every prime
\[
p>T=(863\#)(53\#)(13\#)(7\#)(5\#)3^3 2^5,
\]
where \(n\#\) is the product of the primes at most \(n\). Their decimal approximation is \(3.448\times10^{392}\).

The packet's complete Vieta enumeration independently checks every prime \(5\leq p\leq3001\). Its maximal-divisor scan applies Eddy et al.'s sufficient criterion to every prime in \(10{,}000{,}000<p\leq20{,}000{,}000\), certifying 40,066 and leaving 565,962 undecided by that criterion. Thus the remaining universal problem for \(p\geq5\) is the finite set of primes in \([1{,}000{,}000,T]\) outside the individual certificates recorded or cited here.

Literal enumeration gives a connected four-vertex graph at \(p=2\) and an empty vertex set at \(p=3\). The canonical acceptance condition asks for two components when a prime is exceptional. It therefore needs an explicit empty-graph convention before \(p=3\) can be classified.

### Background and intake notes

This is a strong-approximation problem with an effective finite residue after current theorems. Independent searches can reuse coordinate-order tables and explicit paths, while a proof can attack the remaining finite range structurally.

- Original intake status: UNKNOWN as of 2026-07-27. Brown reports the graph connected for every prime below one million and states universal connectivity as a conjecture; Eddy, Fuchs, Litman, Martin, Tripeny, and Vanyo prove connectivity outside a finite effective range, but this audit did not establish a complete resolution.
- A 2026-07-27 search checked Brown, arXiv:2401.00630, and Eddy et al., arXiv:2308.07579. Both use the coefficient-one Markoff surface in the statement and report universal prime connectivity as conjectural; the strongest checked computation covers every prime below one million.
- The prime parameter is forced by the strong-approximation question. Search artifacts should retain component representatives, coordinate orders, and the path into the large component, since those data survive improved bounds.
- Trap: including (0,0,0), adding coordinate permutations as edges, or quotienting by sign changes creates a different graph. A computation must follow the edge convention in the statement.

- Recorded example: Over F_5, (3,3,3) is a vertex and applying the first Vieta involution gives the adjacent vertex (1,3,3).

### Other known results

- **Computation 1** (reproduced): An exhaustive exact-integer scan of all 606,028 primes with 10,000,000 < p <= 20,000,000 proves G_p connected for 40,066 of them by the criterion of Eddy, Fuchs, Litman, Martin, and Tripeny. [2](#reference-2)
- **Computation 2** (reproduced): A full breadth-first search visits all 1,169,185,980 nonorigin surface points across all 429 primes with 5 <= p <= 3001 and finds one component at every prime. [4](#reference-4)
- **Computation 3** (reproduced): The p=2 graph is connected. The p=3 vertex set is empty, which exposes a null-graph convention absent from the current acceptance conditions.

### Prior approaches

- **Route 1** (supported): The checked primary literature still treats universal connectivity as open for p>=5, while proving a finite effective remainder and several broad or bounded regions. [1](#reference-1) [4](#reference-4) [2](#reference-2) [8](#reference-8) [3](#reference-3) [5](#reference-5) [6](#reference-6) [7](#reference-7)
- **Route 2** (inconclusive): The route gives complete component and path certificates at small p, while its state count prevents it from crossing the unresolved effective interval. [1](#reference-1)

### Open directions

- **Route 3** (reported): Scan every prime with 20,000,000 < p <= 100,000,000 in ten-million shards, preserve exact violating thresholds, and send criterion failures to Brown's stronger algorithm. [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Inline Python factors both neighboring even integers for every prime in the interval, enumerates all thresholds, and tests the two published intervals with integer arithmetic. [2](#reference-2)
- **Artifact 2** (reproduced): Inline C++17 builds the full coefficient-one surface, checks closed formulas and move closure, enumerates every component, and records replayed shortest paths.
- **Artifact 3** (reproduced): A second implementation scans all p^3 triples and independently reproduces every component field and shortest-path certificate for the 26 primes through 101.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `markoff-graph-prime-connectivity-exceptions`, 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>Colby Austin Brown, “An almost linear time algorithm testing whether the Markoff graph modulo p is connected”. Research in Number Theory 11(1) (2025), 6. DOI 10.1007/s40993-024-00592-9. Brown, Theorem 2 and Sections 1 and 4; source comparison completed 2026-07-28; Theorem 2, definition before Figure 2, and Section 4; Brown, Introduction, comparison with O(p^2) flood fill; packet artifact gives measured small-p execution; Brown, Algorithm 3, Section 4, and the libbgs repository at the pinned commit https://arxiv.org/abs/2401.00630
   - Also cited at Theorem 2, definition before Figure 2, and Section 4
   - Also cited at Brown, Introduction, comparison with O(p^2) flood fill; packet artifact gives measured small-p execution
   - Also cited at Brown, Algorithm 3, Section 4, and the libbgs repository at the pinned commit
   - preprint; reference source; arXiv:2401.00630, version checked 2026-07-28; checked 2026-07-28
   - Source use: citation_only
   - Source used to assess the problem's recorded status.
   - For Prime exceptions to connectivity of the Markoff graph: The route gives complete component and path certificates at small p, while its state count prevents it from crossing the unresolved effective interval.
2. <a id="reference-2"></a>Connectivity of Markoff mod-p graphs and maximal divisors Theorems 1.4 and 1.5 and Section 7 https://arxiv.org/abs/2308.07579
   - Also cited at Eddy et al., Theorem 1.4; Brown, DOI 10.1007/s40993-024-00592-9, Theorem 2; packet claims mgpc-claim-components-through-3001, mgpc-claim-maximal-divisor-10m-20m, and mgpc-claim-small-characteristics
   - Also cited at Theorem 1.5 and Section 7, Data on Connectivity
   - preprint; reference source; arXiv:2308.07579v1; checked 2026-07-28
   - Source use: citation_only
   - Source used to assess the problem's recorded status.
3. <a id="reference-3"></a>William Chen, “Nonabelian level structures, Nielsen equivalence, and Markoff triples”. arXiv:2011.12940 (2020). Primary sources checked on 2026-07-27 call universal connectivity conjectural and provide large theoretical and computational ranges, but the audit did not exhaust later literature. https://arxiv.org/abs/2011.12940
   - Also cited at Markoff transitivity corollary
   - preprint; reference source; arXiv:2011.12940, version checked 2026-07-28; checked 2026-07-28
   - Source use: citation_only
   - Source used to assess the problem's recorded status.
   - For Prime exceptions to connectivity of the Markoff graph: Primary sources checked on 2026-07-27 call universal connectivity conjectural and provide large theoretical and computational ranges, but the audit did not exhaust later literature.
4. <a id="reference-4"></a>Matthew de Courcy-Ireland and Seungjae Lee, “Experiments with the Markoff surface”. arXiv:1812.07275 (2018). Independent exact reproduction and extension through p=3001; compare the p<3000 connectivity computation and Proposition 2.1; Introduction, p<3000 computation, and Proposition 2.1 https://arxiv.org/abs/1812.07275
   - Also cited at Introduction, p<3000 computation, and Proposition 2.1
   - Also cited at Independent exact reproduction and extension through p=3001; compare the p<3000 connectivity computation and Proposition 2.1
   - preprint; reference source; arXiv:1812.07275v2; checked 2026-07-28
   - Source use: citation_only
   - For Prime exceptions to connectivity of the Markoff graph: Exact Vieta enumeration connects every G_p for 5 <= p <= 3001. A full breadth-first search visits all 1,169,185,980 nonorigin surface points across all 429 primes with 5 <= p <= 3001 and finds one component at every prime. Dated source and convention audit. The checked primary literature still treats universal connectivity as open for p>=5, while proving a finite effective remainder and several broad or bounded regions.
5. <a id="reference-5"></a>Daniel E. Martin, “A new proof of Chen's theorem for Markoff graphs”. arXiv:2502.15960 (2025). Abstract and Markoff component-divisibility theorem https://arxiv.org/abs/2502.15960
   - preprint; reference source; arXiv:2502.15960v1; checked 2026-07-28
   - Source use: citation_only
   - For Prime exceptions to connectivity of the Markoff graph: Dated source and convention audit. The checked primary literature still treats universal connectivity as open for p>=5, while proving a finite effective remainder and several broad or bounded regions.
6. <a id="reference-6"></a>Elisa Bellah, Claire Dunn, Vernon Naidu, and Alette Wells, “Connectedness of special points in the Markoff mod $p$ graphs”. arXiv:2511.23401 (2025). Abstract and main theorem https://arxiv.org/abs/2511.23401
   - preprint; reference source; arXiv:2511.23401v1; checked 2026-07-28
   - Source use: citation_only
   - For Prime exceptions to connectivity of the Markoff graph: Dated source and convention audit. The checked primary literature still treats universal connectivity as open for p>=5, while proving a finite effective remainder and several broad or bounded regions.
7. <a id="reference-7"></a>Shohei Satake and Yoshinori Yamasaki, “Topological properties of generalized Markoff mod $p$ graphs”. arXiv:2512.21963 (2025). Abstract; generalized level parameter and topological properties https://arxiv.org/abs/2512.21963
   - preprint; reference source; arXiv:2512.21963v1; checked 2026-07-28
   - Source use: citation_only
   - For Prime exceptions to connectivity of the Markoff graph: nearby generalized-level result, not a universal connectivity theorem for the zero level
   - nearby generalized-level result, not a universal connectivity theorem for the zero level
8. <a id="reference-8"></a>Colby Austin Brown, libbgs, Markoff-graph connectivity software, GitHub commit ff9360aa1ed14a35a55511d59a75d8d95fbbdf60 (2026). Repository implementation used to generate the prime connectivity table https://github.com/colbyaustinbrown/libbgs/tree/ff9360aa1ed14a35a55511d59a75d8d95fbbdf60
   - software; software source; commit ff9360aa1ed14a35a55511d59a75d8d95fbbdf60; checked 2026-07-28
   - Source use: citation_only
   - For Prime exceptions to connectivity of the Markoff graph: Provides the implementation used for the packet's independent connectivity checks.
   - Provides the implementation used for the packet's independent connectivity checks.