Title: An almost linear time algorithm testing whether the Markoff graph modulo $p$ is connected Show Chinese title

Title: 一个几乎线性时间的算法，用于测试模$p$的 Markoff 图是否连通

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 + \epsilon})$ time for every $\epsilon > 0$. We demonstrate this algorithm by confirming that the Markoff graph modulo $p$ is connected for all primes less than one million. Show Chinese abstract

Abstract: 模$p$的 Markoff 图对于除了有限多个素数$p$之外的所有素数已知是连通的（参见 Eddy, Fuchs, Litman, Martin, Tripeny 和 Vanyo [arxiv:2308.07579]），并且据推测这些图对于所有素数都是连通的。 本文提供了 Bourgain、Gamburd 和 Sarnak [arxiv:1607.01530] 引入的过程的一个算法实现，用于检验模任意素数$p$的 Markoff 图是否连通。 对于每个$\epsilon > 0$，我们的算法运行时间为$o(p^{1 + \epsilon})$。 我们通过确认模$p$的 Markoff 图对于小于一百万的所有素数均连通来展示该算法。