Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Farey covering with coprime numerator

Proved
CircleMethod.farey_cover_coprime

by tabbott · Sep 1, 2026 · Mathlib c5ea003 (Lean v4.30.0)

analytic-number-theorycircle-methodexponential-sumsnumber-theory

Dirichlet's approximation theorem in the form the Farey dissection requires, with the numerator reduced to lowest terms.

For every Q≥1Q\ge 1Q≥1 and every real α\alphaα there exist a∈Za\in\mathbb{Z}a∈Z and q∈Nq\in\mathbb{N}q∈N with

1≤q≤Q,gcd⁡(∣a∣,q)=1,∣α−aq∣≤1q(Q+1).1\le q\le Q,\qquad \gcd(|a|,q)=1,\qquad \left|\alpha-\frac{a}{q}\right|\le\frac{1}{q(Q+1)}.1≤q≤Q,gcd(∣a∣,q)=1,​α−qa​​≤q(Q+1)1​.

The unreduced version is classical; the content added here is that the approximating fraction may be taken in lowest terms without weakening the bound. That matters because the major arcs of the circle method are indexed by coprime pairs (a,q)(a,q)(a,q) — one arc per reduced fraction — and the disjointness of arcs with distinct centres is proved using coprimality. Without the reduction one would count the same arc repeatedly and the sum over major arcs would overcount.

Together with the bound this statement makes the dissection exhaustive: every point of the unit interval lies within 1q(Q+1)\frac{1}{q(Q+1)}q(Q+1)1​ of some reduced fraction with denominator at most QQQ, so declaring the remaining points "minor arcs" is a genuine dichotomy rather than a definition with an empty complement.

Formalization Note. Coprimality is stated as Nat.Coprime a.natAbs q, which is the correct notion when the numerator may be negative. Note that a=0a=0a=0 forces q=1q=1q=1, since gcd⁡(0,q)=q\gcd(0,q)=qgcd(0,q)=q; that instance is the arc centred at the integer 000, which is exactly as intended.

Preamble
import Definitions.Def_CircleMethod_genfun
import Mathlib.Analysis.SpecialFunctions.Pow.Real
import Mathlib.Analysis.SpecialFunctions.Integrals.Basic
import Mathlib.NumberTheory.Divisors
import Mathlib.Data.Fintype.Pi
open Finset
Formal statement
namespace CircleMethod

theorem farey_cover_coprime {Q : ℕ} (hQ : 0 < Q) (α : ℝ) :
    ∃ (a : ℤ) (q : ℕ), 0 < q ∧ q ≤ Q ∧ Nat.Coprime a.natAbs q ∧
      |α - (a : ℝ) / (q : ℝ)| ≤ 1 / ((q : ℝ) * ((Q : ℝ) + 1)) := by sorry

end CircleMethod
Source
R. C. Vaughan, The Hardy-Littlewood Method, 2nd ed., 1997, Section 2.1 (Farey dissection); Dirichlet's approximation theorem as in G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Theorem 36.
Read-back

What the Lean code literally says, in plain math · claude-opus-5

Read-back: CircleMethod.farey_cover_coprime

What the declaration asserts. The statement is parameterized by a natural number QQQ (supplied implicitly, i.e. inferred from the other data rather than written by the caller), together with two explicit hypotheses/inputs: a proof that Q>0Q > 0Q>0, and an arbitrary real number α\alphaα. Under these assumptions the claim is that there exist an integer a∈Za \in \mathbb{Z}a∈Z and a natural number q∈Nq \in \mathbb{N}q∈N such that all four of the following hold simultaneously:

q>0,q≤Q,gcd⁡(∣a∣,q)=1,∣ α−aq ∣  ≤  1q (Q+1).q > 0, \qquad q \le Q, \qquad \gcd(|a|, q) = 1, \qquad \left|\, \alpha - \frac{a}{q} \,\right| \;\le\; \frac{1}{q\,(Q+1)}.q>0,q≤Q,gcd(∣a∣,q)=1,​α−qa​​≤q(Q+1)1​.

Reading of each conjunct.

  • q>0q > 0q>0 and q≤Qq \le Qq≤Q: the denominator qqq is a strictly positive natural number, bounded above by QQQ (non-strictly). Both are comparisons of natural numbers.
  • The coprimality clause is the assertion that the greatest common divisor of the natural number ∣a∣|a|∣a∣ (the absolute value of aaa, coerced to N\mathbb{N}N) and the natural number qqq equals 111. Note the first argument is ∣a∣|a|∣a∣, not aaa itself; the condition is symmetric in sign, so it constrains aaa only up to sign.
  • The final clause is an inequality between real numbers. Both aaa and qqq are coerced into R\mathbb{R}R; the quotient a/qa/qa/q and the quotient 1/(q(Q+1))1/(q(Q+1))1/(q(Q+1)) are real divisions, and QQQ is likewise coerced into R\mathbb{R}R before 111 is added to it. The inequality is non-strict (≤\le≤), and the right-hand denominator is q⋅(Q+1)q \cdot (Q+1)q⋅(Q+1), not q(Q+1)q(Q+1)q(Q+1) with any other normalization, nor q⋅Qq \cdot Qq⋅Q, nor qQqQqQ with an exponent.

Quantifier structure. The two witnesses aaa and qqq are existentially quantified and are asserted to exist for every real α\alphaα and every positive QQQ; no uniqueness is claimed, and nothing asserts that the pair (a,q)(a,q)(a,q) depends measurably, continuously, or canonically on α\alphaα. There is no upper or lower bound imposed on aaa beyond what the final inequality forces: aaa may be any integer, of either sign or zero, and in particular the statement does not require 0≤a≤q0 \le a \le q0≤a≤q, ∣a∣≤q|a| \le q∣a∣≤q, or aaa to lie in any fixed residue range.

Degenerate and edge cases silently included.

  • Since the conclusion asserts 0<q≤Q0 < q \le Q0<q≤Q, the hypothesis Q>0Q > 0Q>0 is consistent with, and necessary for, the conclusion; for Q=0Q = 0Q=0 no such qqq could exist, and the hypothesis excludes that case.
  • The value q=1q = 1q=1 is permitted. In that case the coprimality condition gcd⁡(∣a∣,1)=1\gcd(|a|, 1) = 1gcd(∣a∣,1)=1 holds automatically for every integer aaa, including a=0a = 0a=0, so the coprimality clause imposes no restriction at all when q=1q = 1q=1.
  • a=0a = 0a=0 is permitted whenever gcd⁡(0,q)=q=1\gcd(0, q) = q = 1gcd(0,q)=q=1, i.e. exactly when q=1q = 1q=1; note gcd⁡(0,q)=q\gcd(0,q) = qgcd(0,q)=q, so a=0a = 0a=0 forces q=1q = 1q=1.
  • Because q>0q > 0q>0 is asserted, the real divisions a/qa/qa/q and 1/(q(Q+1))1/(q(Q+1))1/(q(Q+1)) never fall back on the division-by-zero convention; and since Q≥1Q \ge 1Q≥1, the factor Q+1≥2Q + 1 \ge 2Q+1≥2 is strictly positive, so the bound on the right-hand side is a positive real number.
  • No claim is made about the number of such pairs, about qqq being maximal or minimal, or about a/qa/qa/q being in lowest terms as a rational number beyond the stated gcd⁡(∣a∣,q)=1\gcd(|a|, q) = 1gcd(∣a∣,q)=1.

Definitions from the surrounding bundle. The statement lives in the namespace CircleMethod, whose ambient definitions include the additive character e(θ)=exp⁡(2πiθ)e(\theta) = \exp(2\pi i \theta)e(θ)=exp(2πiθ), the generating function fA(θ)=∑a∈Ae(aθ)f_A(\theta) = \sum_{a \in A} e(a\theta)fA​(θ)=∑a∈A​e(aθ) for a finite set A⊆ZA \subseteq \mathbb{Z}A⊆Z, and the distance-to-nearest-integer function ∥θ∥=∣θ−round(θ)∣\|\theta\| = |\theta - \mathrm{round}(\theta)|∥θ∥=∣θ−round(θ)∣. None of these appears in this statement: the assertion is expressed purely in terms of ordinary absolute value, real arithmetic, and the gcd of natural numbers. In particular the final inequality uses the ordinary absolute value ∣α−a/q∣|\alpha - a/q|∣α−a/q∣ of a real number, not the distance-to-nearest-integer norm.

Proof status. The declaration is stated as a theorem whose proof is left as sorry; the file therefore contains the assertion above but no proof of it.

Human review
  • Endorsed by tianyipeng · Sep 2, 2026

  • Endorsed by tabbott · Sep 2, 2026

    Confirmed by the mission captain (proposal self-audit).

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