Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Vaughan's identity: truncations, bilinear sums, dyadic blocks

Definition
Vino_vaughan

by tabbott · Sep 3, 2026 · Mathlib 0df444a (Lean v4.33.1)

circle-methodnumber-theoryvaughan-identityvinogradov

Auxiliary objects for Vaughan's identity and the Type I / Type II analysis of the prime exponential sum S(α,N)=∑n<NΛ(n)e(αn)S(\alpha,N)=\sum_{n<N}\Lambda(n)e(\alpha n)S(α,N)=∑n<N​Λ(n)e(αn).

  • trunc f V is the truncation fV(n)=f(n) 1n≤Vf_V(n) = f(n)\,\mathbf 1_{n\le V}fV​(n)=f(n)1n≤V​ of an arithmetic function; muT V =μV=\mu_V=μV​ and lamT U =ΛU=\Lambda_U=ΛU​ are the truncated Möbius and von Mangoldt functions appearing in Vaughan's identity Λ=μV∗log⁡−μV∗ΛU∗1+(μ−μV)∗(Λ−ΛU)∗1+ΛU\Lambda = \mu_V * \log - \mu_V * \Lambda_U * 1 + (\mu-\mu_V)*(\Lambda-\Lambda_U)*1 + \Lambda_UΛ=μV​∗log−μV​∗ΛU​∗1+(μ−μV​)∗(Λ−ΛU​)∗1+ΛU​.
  • bilin f g α N =∑mk<Nf(m)g(k)e(αmk)=\sum_{mk<N} f(m)g(k)e(\alpha mk)=∑mk<N​f(m)g(k)e(αmk) is the bilinear exponential sum attached to a Dirichlet convolution f∗gf*gf∗g.
  • dyad g T j restricts ggg to the dyadic range 2j≤k<2j+12^j\le k<2^{j+1}2j≤k<2j+1, k≤Tk\le Tk≤T; blockT f U T j restricts fff to the dyadic block ⌊log⁡2((m−1)/U)⌋=j\lfloor\log_2((m-1)/U)\rfloor=j⌊log2​((m−1)/U)⌋=j, m≤Tm\le Tm≤T.
  • capMin X θ is a safe form of min⁡(X,1/(2∥θ∥))\min(X, 1/(2\|\theta\|))min(X,1/(2∥θ∥)), equal to XXX when 2∥θ∥X≤12\|\theta\|X\le 12∥θ∥X≤1 (including ∥θ∥=0\|\theta\|=0∥θ∥=0).
Definition code
import Definitions.Def_Vino_primes
import Mathlib.NumberTheory.ArithmeticFunction.VonMangoldt
import Mathlib.NumberTheory.ArithmeticFunction.Moebius
import Mathlib.Algebra.BigOperators.Group.Finset.Basic
import Mathlib.Data.Nat.Log

open Finset ArithmeticFunction

namespace Vaughan

/-- Truncation of an arithmetic function to the range `n ≤ V`. -/
noncomputable def trunc (f : ArithmeticFunction ℝ) (V : ℕ) : ArithmeticFunction ℝ :=
  ⟨fun n => if n ≤ V then f n else 0, by simp⟩

@[simp] theorem trunc_apply (f : ArithmeticFunction ℝ) (V n : ℕ) :
    trunc f V n = if n ≤ V then f n else 0 := rfl

/-- `μ_V`: the Möbius function truncated to `d ≤ V`. -/
noncomputable def muT (V : ℕ) : ArithmeticFunction ℝ := trunc (moebius : ArithmeticFunction ℝ) V

/-- `Λ_U`: the von Mangoldt function truncated to `r ≤ U`. -/
noncomputable def lamT (U : ℕ) : ArithmeticFunction ℝ := trunc vonMangoldt U

/-- The bilinear exponential sum `∑_{m·k < N} f(m) g(k) e(α m k)`. -/
noncomputable def bilin (f g : ArithmeticFunction ℝ) (α : ℝ) (N : ℕ) : ℂ :=
  ∑ m ∈ range N, ∑ k ∈ range N,
    if m * k < N then ((f m * g k : ℝ) : ℂ) * CircleMethod.e (α * ((m * k : ℕ) : ℝ)) else 0

/-- The dyadic restriction of `g` to `[2^j, 2^(j+1)) ∩ [1, T]`. -/
noncomputable def dyad (g : ℕ → ℝ) (T j k : ℕ) : ℝ :=
  if 2 ^ j ≤ k ∧ k < 2 ^ (j + 1) ∧ k ≤ T then g k else 0

/-- A safe form of `min (X, 1/(2‖θ‖))`: it equals `X` whenever `2‖θ‖X ≤ 1` (in particular when
`‖θ‖ = 0`) and `1/(2‖θ‖)` otherwise. -/
noncomputable def capMin (X θ : ℝ) : ℝ :=
  if 2 * CircleMethod.nrm θ * X ≤ 1 then X else 1 / (2 * CircleMethod.nrm θ)

/-- Dyadic block `j` (scale `U 2^j`, i.e. `m` with `⌊log₂ ((m-1)/U)⌋ = j`) of `f`,
truncated to `m ≤ T`. -/
noncomputable def blockT (f : ArithmeticFunction ℝ) (U T j : ℕ) : ArithmeticFunction ℝ :=
  ⟨fun m => if m ≤ T ∧ Nat.log 2 ((m - 1) / U) = j then f m else 0, by simp⟩

@[simp] theorem blockT_apply (f : ArithmeticFunction ℝ) (U T j m : ℕ) :
    blockT f U T j m = if m ≤ T ∧ Nat.log 2 ((m - 1) / U) = j then f m else 0 := rfl

end Vaughan
Source
R. C. Vaughan, The Hardy–Littlewood Method, 2nd ed., Cambridge Tracts 125, Chapter 3, §3.1 (Vaughan's identity, eq. (3.2)) and Lemma 3.1; Davenport, Multiplicative Number Theory, 3rd ed., Chapter 24

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