Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Fourteen-regular fixed-p=13 LPS Cayley graph on PGL₂

Proved
OPG37364.lps13Graph_regular14

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. Let SSS be the projective images of the fourteen matrices

Mi(a)=(a0+ia1a2+ia3−a2+ia3a0−ia1),M_i(a)=\begin{pmatrix}a_0+i a_1&a_2+i a_3\\-a_2+i a_3&a_0-i a_1\end{pmatrix},Mi​(a)=(a0​+ia1​−a2​+ia3​​a2​+ia3​a0​−ia1​​),

where aaa ranges over (1,±2,±2,±2)(1,\pm2,\pm2,\pm2)(1,±2,±2,±2) and the six tuples (3,±2,0,0)(3,\pm2,0,0)(3,±2,0,0) with the nonzero imaginary coordinate in any of the three positions. Each matrix has determinant 131313. Projectivization is in PGL⁡2(Fq)\operatorname{PGL}_2(\mathbb F_q)PGL2​(Fq​), modulo all nonzero scalar matrices.

Then the simple Cayley graph on this finite projective group, with edges v∼vsv\sim vsv∼vs for s∈Ss\in Ss∈S, is 141414-regular: every vertex has exactly fourteen neighbors. The formal conclusion is the original OPG37364 set-cardinality predicate IsRegularOfDegree, using neighborSet.encard.

The proof establishes distinct projective images, exclusion of the identity and inverse closure through quaternion conjugation. The chosen root is a transparent parameter, not a graph-property assumption. For primes from the fixed-13 arithmetic selection lemma, q≡1(mod4)q\equiv1\pmod4q≡1(mod4) supplies a root and (13/q)=−1(13/q)=-1(13/q)=−1 identifies the PGL branch of the LPS construction. Nonresiduosity is unnecessary for regularity. Connectedness, bipartiteness, girth and spectral estimates are outside this theorem.

Preamble
import Definitions.Def_opg37364_lps13
set_option autoImplicit false
Formal statement
namespace OPG37364

theorem lps13Graph_regular14 {q : ℕ} [Fact q.Prime]
    (hq : 13 < q) (i : LPS13Root q) :
    IsRegularOfDegree (lps13Graph hq i) 14 := by sorry

end OPG37364
Source
Lubotzky, Phillips and Sarnak, Ramanujan graphs, Combinatorica 8 (1988), p. 262, https://doi.org/10.1007/BF02126799 (positive odd real coordinate and even imaginary coordinates). Davidoff, Sarnak and Valette, Elementary Number Theory, Group Theory, and Ramanujan Graphs, Proposition 2.5.2 (matrix formula with x=i, y=0), Definition 4.1.1 (right Cayley convention), and Section 4.2, especially Lemma 4.2.1 and Remark 4.2.3(c), https://math.bme.hu/~gabor/oktatas/SztoM/DavidoffSarnakValette.pdf . Fixed-p=13 structural formalization of classical mathematics.

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