Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Bipartiteness of the fixed-p=13 LPS Cayley graph on PGL₂

Proved
OPG37364.lps13Graph_bipartite

by arexychen · Sep 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

cayley-graphsfinite-groupsgraph-theory

Let q>13q>13q>13 be prime and choose i∈Fqi\in\mathbb F_qi∈Fq​ with i2=−1i^2=-1i2=−1. Consider the fixed-p=13p=13p=13 graph OPG37364.lps13Graph, on PGL⁡2(Fq)\operatorname{PGL}_2(\mathbb F_q)PGL2​(Fq​) with the fourteen norm-131313 quaternion generators specified in Definitions.Def_opg37364_lps13. If 131313 is a quadratic nonresidue modulo qqq, then this graph is bipartite: there is a Boolean coloring of its projective vertices for which the endpoints of every edge have different colors.

The coloring records whether the determinant of a matrix representative is a square. This is well-defined because multiplying a representative by a nonzero scalar multiplies its determinant by a square. Every generator has determinant 131313, so multiplication by a generator exchanges the two colors. The formal hypothesis is legendreSym q 13 = -1, with qqq as the modulus. No connectedness assumption is required.

This is a formalization of the classical determinant-square-class bipartition for the LPS construction, specialized to the existing fixed-131313 graph.

Preamble
import Definitions.Def_opg37364_lps13
import Mathlib.NumberTheory.LegendreSymbol.Basic
set_option autoImplicit false
Formal statement
namespace OPG37364

theorem lps13Graph_bipartite {q : ℕ} [Fact q.Prime]
    (hq : 13 < q) (i : LPS13Root q) (hnr : legendreSym q 13 = -1) :
    IsBipartite (lps13Graph hq i) := by sorry

end OPG37364
Source
Davidoff, Sarnak and Valette, Elementary Number Theory, Group Theory, and Ramanujan Graphs, Proposition 4.1.2(d) and Remark 4.2.3(c), printed p. 114, https://math.bme.hu/~gabor/oktatas/SztoM/DavidoffSarnakValette.pdf . The underlying fixed-p=13 convention is the PGL construction of Lubotzky, Phillips and Sarnak, Ramanujan graphs, Combinatorica 8 (1988), p. 262, https://doi.org/10.1007/BF02126799 .

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me