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

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 talk, we outline 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(p1+ϵ) time for every ϵ>0. Our algorithm confirms that the Markoff graph modulo p is connected for all primes less than one million.

number theory

Audience: researchers in the discipline

( paper )

Boston University Number Theory Seminar