An almost linear time algorithm testing whether the Markoff graph modulo p is connected

2024/01/01 by Colby Austin Brown, Brown, Colby Austin · 1 citation
Computer Science · Mathematics · #11Y16 #Algorithms and Data Compression #Analytic Number Theory Research #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2401.00630

openalex publication_date 2024/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Markoff graph modulo p is known to be connected for all but finitely many primes p (see Eddy, Fuchs, Litman, Martin, Tripeny, and Vanyo [arxiv:2308.07579]), and it is conjectured that these graphs are connected for all primes. In this paper, we provide an algorithmic realization of the process introduced by Bourgain, Gamburd, and Sarnak [arxiv:1607.01530] to test whether the Markoff graph modulo p is connected for arbitrary primes. Our algorithm runs in o(p^{1 + ε}) time for every ε> 0. We demonstrate this algorithm by confirming that the Markoff graph modulo p is connected for all primes less than one million.

Cited by

• Topological properties of generalized Markoff mod p graphs

Related

• Connectivity of Markoff mod-p graphs and maximal divisors
• Connectedness of special points in the Markoff mod p graphs
• A new proof of Chen's theorem for Markoff graphs
• Bounding Lifts of Markoff Triples mod p
• Experiments with the Markoff surface