Topological properties of generalized Markoff mod p p graphs
Shohei Satake, Yoshinori Yamasaki · 2025
Read Topological properties of generalized Markoff mod p p graphs by Shohei Satake, Yoshinori Yamasaki (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-21963.txt.
Introduction
Markoff-type equations over finite fields generate graphs whose topology is only partly understood. Shohei Satake and Yoshinori Yamasaki study the Markoff graph modulo a prime. They study non-planarity, surface embeddability, and the existence of short cycles.
Their approach constructs subdivisions of the complete bipartite graph K three-three, forcing non-planarity and bounding the surfaces the graph can embed in. The argument integrates graph theory, computer algebra, and number theory. Results of this kind connect the Markoff graph's combinatorics to the genus questions raised for the classical Markoff surface.
Catalog record
| CREATOR | Shohei Satake, Yoshinori Yamasaki |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 100 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-21963
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Topological properties of generalized Markoff mod p p graphs Shohei Satake, Yoshinori Yamasaki Abstract . The generalized Markoff mod p p graph is defined via the equation x 2 + y 2 + z 2 = x y z + κ x^{2}+y^{2}+z^{2}=xyz+\kappa over the finite field 𝔽 p \mathbb{F}_{p} of prime order p p . In this paper, we investigate the topological properties of the graph such as non-planarity, surface embeddability, and the existence of short cycles. Our approach is based on a systematic construction of K 3 , 3 K_{3,3} -subdivisions, integrating techniques from graph theory, computer algebra, and number theory. 2020 Mathematics Subject Classification Primary 11D25; Secondary 05C10, 13P15. 1. Introduction The Diophantine equation (1.1) x^{2}+y^{2}+z^{2}=xyz is called the Markoff equation , and a solution (x,y,z) is called a Markoff triple . For a prime p>3 , let {\mathcal{M}(p)} denote the set of all Markoff triples over {\mathbb{F}_{p}} , the finite field with p elements. The Markoff mod p graph {\mathcal{G}(p)} is a finite 3 -regular graph (possibly with loops) whose vertex set is {\mathcal{M}(p)}\setminus\{(0,0,0)\} , and two triples are adjacent if and only if they are transformed into each other by one of the following Vieta involutions : R_{1}(x,y,z)=(yz-x,y,z),\quad R_{2}(x,y,z)=(x,zx-y,z),\quad R_{3}(x,y,z)=(x,y,xy-z). The graph {\mathcal{G}(p)} has been extensively studied in the literature on “strong approximation” for the Markoff equation ( 1.1 ). Indeed, Bourgain, Gamburd, and Sarnak [ 2 ] conjectured that {\mathcal{G}(p)} is connected for all primes p>3 . Recently Chen [ 9 ] made a breakthrough toward this conjecture by proving that {\mathcal{G}(p)} is connected for any sufficiently large prime p . A key result here is that the size of any component of {\mathcal{G}(p)} must be divisible by p . Furthermore, for any \varepsilon>0 , there are only O(p^{\varepsilon}) vertices that are not contained in the giant component ( [ 2 ] ) while {\mathcal{G}(p)} has approximately p^{2} vertices (see ( 1.3 ) below). Martin [ 24 ] provided an elementary proof of Chen’s result concerning the divisibility of the component sizes of {\mathcal{G}(p)} . In addition, Eddy, Fuchs, Litman, Martin, and Tripeny [ 14 ] established an explicit lower bound for primes p for which the connectivity of {\mathcal{G}(p)} is guaranteed, namely, p>3.448\times 10^{392} . There are several algorithmic results towards the connectivity of {\mathcal{G}(p)} , and it was verified in [ 4 ] that {\mathcal{G}(p)} is connected for p<10^{6} . On the other hand, de Courcy-Ireland [ 9 ] established the non-planarity of {\mathcal{G}(p)} : {\mathcal{G}(p)} is planar if and only if p=7 . This provides (indirect but positive) evidence for another well-known conjecture by Bourgain, Gamburd, and Sarnak [ 2 , 3 ] asserting that \{{\mathcal{G}(p)}\}_{\text{$p$:prime}} is in fact an expander family, which would imply higher connectivity for {\mathcal{G}(p)} (for further details on expander family, see e.g. [ 18 , 23 ] ). The proof of non-planarity consists of two parts: an asymptotic evaluation of the Euler characteristic of {\mathcal{G}(p)} and explicit constructions of subdivisions of the complete bipartite graph K_{3,3} . The Kuratowski-Wagner theorem shows a complete characterization for planar graphs in terms of graph minors, that is, a graph is planar if and only if it contains neither K_{3,3} nor the complete graph K_{5} as a graph minor. Since {\mathcal{G}(p)} is a 3 -regular graph, K_{3,3} is the unique obstruction to planarity of {\mathcal{G}(p)} in the sense that a 3 -regular graph cannot contain a subdivision of K_{5} , and more generally, any 3 -regular graph containing K_{5} as a minor must also contain a subdivision of K_{3,3} . There are several generalizations of ( 1.1 ), such as the following equation: for a (rational) integer \kappa , (1.2) x^{2}+y^{2}+z^{2}=xyz+\kappa. Throughout this paper, we naturally treat \kappa as an element of {\mathbb{F}_{p}} when considering the solutions of ( 1.2 ) modulo p . For the set of all such solutions over {\mathbb{F}_{p}} , denoted by {\mathcal{M}_{\kappa}(p)} , Carlitz [ 5 ] proved that (1.3) \displaystyle\#{\mathcal{M}_{\kappa}(p)}=p^{2}+\left(3+\left(\frac{\kappa}{p}\right)\right)\left(\frac{\kappa-4}{p}\right)p+1, where (\frac{\cdot}{p}) is the Legendre symbol. The generalized Markoff mod p graph {\mathcal{G}_{\kappa}(p)} (with respect to ( 1.2 )) is defined as a 3 -regular graph whose vertex set is {\mathcal{M}_{\kappa}(p)} with the adjacency relation defined in the same manner as for {\mathcal{G}(p)} (hence \mathcal{G}_{0}(p) coincides with {\mathcal{G}(p)}\sqcup\{(0,0,0)\} , where (0,0,0) is an isolated vertex). The graph structure of {\mathcal{G}_{\kappa}(p)} depends sensitively on \kappa and p in general. For example, in the case of \kappa=4 (corresponding to a degenerate surface called the Cayley cubic , cf. [ 8 ] ), the graph \mathcal{G}_{4}(p) possesses many small components. While {\mathcal{G}_{\kappa}(p)} is no longer connected in general, it is still expected that for \kappa\neq 4 , there exists a unique giant component \mathcal{C}_{\kappa}(p) in {\mathcal{G}_{\kappa}(p)} such that \#({\mathcal{G}_{\kappa}(p)}\setminus\mathcal{C}_{\kappa}(p))=o_{\kappa}(p^{2}) . In a recent preprint [ 25 ] , Martin announced that this in fact holds for a majority of primes. Moreover, the main result of [ 25 ] would imply that \#({\mathcal{G}_{\kappa}(p)}\setminus\mathcal{C}_{\kappa}(p))=O(1) , representing a significant advance in the understanding of the global structure of {\mathcal{G}_{\kappa}(p)} . However, the precise structure of {\mathcal{G}_{\kappa}(p)} (and \mathcal{C}_{\kappa}(p) ) is still largely unexplored. In this paper, we investigate the topological properties of the generalized Markoff mod p graph {\mathcal{G}_{\kappa}(p)} by combining perspectives of graph theory, computer algebra, and number theory. In particular, by leveraging computational algebraic methods including resultants and Gröbner bases, in conjunction with the Chebotarev density theorem, we derive the following results based on graph minor theory. Throughout this paper, the term K_{3,3} -subdivision refers to a subdivision of the complete bipartite graph K_{3,3} . Theorem 1.1 . Let \kappa\in\mathbb{Z}\setminus\{4\} . Then the followings hold: (1) (\mathrm{Theorems}~\ref{thm-n=1},\ \ref{thm:n=2 non-planarity}\ \text{and}\ \ref{thm-n=(p-1)/2}) For each such \kappa and for infinitely many primes p (depending on \kappa ) of natural density at least 1/2 , there exists an explicit K_{3,3} -subdivision in {\mathcal{G}_{\kappa}(p)} . (2) (\mathrm{Theorem}~\ref{thm:np density}) Moreover, for almost all \kappa , the natural density of primes p for which (1) holds is at least 13/16 . Theorem 1.1 yields several topological properties of {\mathcal{G}_{\kappa}(p)} . In particular, the following corollary is an immediate consequence of Theorem 1.1 . Corollary 1.2 . Under the same assumptions on \kappa and p of Theorem 1.1 (1) , the followings hold: (1) (\mathrm{Corollary}~\ref{cor:sufficient condition non-planarity}) {\mathcal{G}_{\kappa}(p)} is non-planar. (2) (\mathrm{Corollary}~\ref{cor:cycles}) {\mathcal{G}_{\kappa}(p)} has cycles (i.e. closed paths with no repeated vertices or edges) of lengths 6,9,10,15 , and 18 , all of which can be constructed explicitly. Note that it would be interesting to obtain results analogous to Theorem 1.1 and Corollary 1.2 for other generalizations of the Markoff mod p graph {\mathcal{G}(p)} (e.g. [ 10 ] ); these will be discussed in our subsequent works. Recall that {\mathcal{G}_{\kappa}(p)} admits the following non-trivial graph automorphisms, known as double sign changes : (x,y,z)\mapsto(x,-y,-z),\quad(x,y,z)\mapsto(-x,y,-z),\quad\text{and}\quad(x,y,z)\mapsto(-x,-y,z). These automorphisms, together with the identity, form a group isomorphic to (\mathbb{Z}/2\mathbb{Z})^{2} . Combining this symmetry of {\mathcal{G}_{\kappa}(p)} with Theorem 1.1 , we obtain an explicit construction of mutually vertex-disjoint K_{3,3} -subdivisions. Theorem 1.3 (Theorem 5.1 ) . For each \kappa\in\mathbb{Z}\setminus\{4\} , {\mathcal{G}_{\kappa}(p)} contains at least four mutually vertex-disjoint K_{3,3} -subdivisions for infinitely many primes p (depending on \kappa ) of natural density at least 1/4 if \kappa=2 and 1/2 otherwise. Moreover, for almost all \kappa , the natural density of