Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Arbitrarily large primes for the fixed-p=13 LPS arithmetic setup

Proved
OPG37364.exists_lps13_prime_above

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

number-theoryprime-numbersquadratic-reciprocity

For every natural number BBB, there is a prime qqq such that

q>max⁡{B,13},q≡5(mod52),q≡1(mod4),(13q)=−1.q>\max\{B,13\},\qquad q\equiv5\pmod{52},\qquad q\equiv1\pmod4,\qquad \left(\frac{13}{q}\right)=-1.q>max{B,13},q≡5(mod52),q≡1(mod4),(q13​)=−1.

All properties hold for the same prime. Thus suitable primes can be selected above any later size threshold; no effective bound or particular prime is prescribed.

This is the fixed-p=13p=13p=13 arithmetic step in the Feghali–Lucke–Paulusma–Ries/Lubotzky–Phillips–Sarnak route. Dirichlet's theorem supplies primes in the progression 5+52k5+52k5+52k. Reduction modulo 131313 gives (q/13)=(5/13)=−1(q/13)=(5/13)=-1(q/13)=(5/13)=−1, and quadratic reciprocity gives (13/q)=−1(13/q)=-1(13/q)=−1. The conclusion is only arithmetic and makes no graph-construction claim.

Formalization note: Mathlib writes the symbol as legendreSym q 13. The existential prime-proof binder supplies the required Fact q.Prime instance; it does not introduce an additional mathematical assumption.

Preamble
import Mathlib.NumberTheory.LSeries.PrimesInAP
import Mathlib.NumberTheory.LegendreSymbol.QuadraticReciprocity
import Mathlib.Tactic.NormNum.LegendreSymbol
set_option autoImplicit false
Formal statement
namespace OPG37364

theorem exists_lps13_prime_above (B : ℕ) :
    ∃ (q : ℕ) (hq : q.Prime),
      max B 13 < q ∧ q ≡ 5 [MOD 52] ∧ q ≡ 1 [MOD 4] ∧
      @legendreSym q ⟨hq⟩ 13 = -1 := by sorry

end OPG37364
Source
Feghali, Lucke, Paulusma and Ries, Matching Cuts in Graphs of High Girth and H-Free Graphs, Algorithmica 87 (2025), Lemma 4 and the arithmetic hypotheses in Lemma 5, https://link.springer.com/article/10.1007/s00453-025-01318-8 . Lemma 4 states (q/13)=-1; this formalization explicitly applies quadratic reciprocity to obtain (13/q)=-1. LPS: Lubotzky, Phillips and Sarnak, Ramanujan graphs, Combinatorica 8 (1988), p. 262, https://doi.org/10.1007/BF02126799 . Classical Dirichlet/reciprocity specialization, not new 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