Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Cofinal prime transference with reduced residue classes

Definition
GreenTaoPort_Wikipedia_GreenTao_ReducedResidueCofinalTransference

by kmehltretter82 · Nov 14, 2026 · Mathlib c5ea003 (Lean v4.30.0)

arithmetic-progressionsgreen-tao-port-8822number-theory

Fix a progression length kkk, a prime-weight scale α\alphaα, a period WWW, and density and counting thresholds δ,c∈R\delta,c\in\mathbb Rδ,c∈R. The cofinal transference predicate requires that, beyond every natural threshold M0M_0M0​, there is M≥M0M\ge M_0M≥M0​ with M+1M+1M+1 prime such that every reduced residue bbb modulo WWW satisfies

mean⁡(fb)≥δ⟹APCount⁡k(fb)≥c,\operatorname{mean}(f_b)\ge\delta\quad\Longrightarrow\quad \operatorname{APCount}_k(f_b)\ge c,mean(fb​)≥δ⟹APCountk​(fb​)≥c,

where fbf_bfb​ is the WWW-tricked prime weight on Z/(M+1)Z\mathbb Z/(M+1)\mathbb ZZ/(M+1)Z. Thus the same selected prime modulus works for all reduced residues whose weight has the required mean. The standard-cutoff obligation asks, for every k≥3k\ge3k≥3, for a primorial period WWW and a positive ccc with this property, using the previously fixed prime scale and density target.

Definition code
import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_CofinalPrimeModulusAssembly
import Definitions.Def_GreenTaoPort_Wikipedia_GreenTao_Transference_RelativeSzemeredi
import Mathlib.Algebra.BigOperators.Expect
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Algebra.BigOperators.Group.Finset.Basic
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Field.ZMod
import Mathlib.Algebra.GCDMonoid.FinsetLemmas
import Mathlib.Algebra.Group.Indicator
import Mathlib.Algebra.Order.BigOperators.Expect
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Algebra.Order.BigOperators.GroupWithZero.Finset
import Mathlib.Algebra.Order.Chebyshev
import Mathlib.Analysis.Calculus.BumpFunction.InnerProduct
import Mathlib.Analysis.Calculus.ContDiff.Deriv
import Mathlib.Analysis.Calculus.Deriv.MeanValue
import Mathlib.Analysis.Calculus.Deriv.Support
import Mathlib.Analysis.Distribution.SchwartzSpace.Fourier
import Mathlib.Analysis.LocallyConvex.Separation
import Mathlib.Analysis.SpecialFunctions.Log.Basic
import Mathlib.Analysis.SpecialFunctions.Pow.Asymptotics
import Mathlib.Analysis.SpecialFunctions.Pow.Complex
import Mathlib.Analysis.SpecificLimits.Basic
import Mathlib.Combinatorics.Pigeonhole
import Mathlib.Data.Fin.Tuple.Basic
import Mathlib.Data.Fin.Tuple.Finset
import Mathlib.Data.Finset.Max
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Data.Fintype.Card
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.Int.Lemmas
import Mathlib.Data.Int.ModEq
import Mathlib.Data.Nat.Lattice
import Mathlib.Data.Nat.Prime.Defs
import Mathlib.Data.Nat.Prime.Factorial
import Mathlib.Data.Nat.Prime.Infinite
import Mathlib.Data.Nat.Totient
import Mathlib.Data.Real.Archimedean
import Mathlib.Data.Real.Basic
import Mathlib.Data.Set.Card
import Mathlib.Data.ZMod.Basic
import Mathlib.Data.ZMod.Units
import Mathlib.GroupTheory.Index
import Mathlib.LinearAlgebra.Pi
import Mathlib.Logic.Equiv.Fin.Basic
import Mathlib.MeasureTheory.Integral.Bochner.Set
import Mathlib.MeasureTheory.Integral.IntegralEqImproper
import Mathlib.MeasureTheory.Integral.Pi
import Mathlib.MeasureTheory.Integral.Prod
import Mathlib.NumberTheory.ArithmeticFunction.Moebius
import Mathlib.NumberTheory.Chebyshev
import Mathlib.NumberTheory.Divisors
import Mathlib.NumberTheory.Harmonic.ZetaAsymp
import Mathlib.NumberTheory.LSeries.Dirichlet
import Mathlib.NumberTheory.Primorial
import Mathlib.Order.Filter.Finite
import Mathlib.Order.Hom.PowersetCard
import Mathlib.Order.Interval.Finset.Nat
import Mathlib.Order.LiminfLimsup
import Mathlib.Order.Partition.Finpartition
import Mathlib.RingTheory.Int.Basic
import Mathlib.Tactic
import Mathlib.Topology.ContinuousMap.Weierstrass
import Mathlib.Topology.MetricSpace.Pseudo.Defs

set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3


/-!
# Cofinal transference on reduced residue classes

The sieve normalization for the W-tricked majorant uses that the selected
shift is coprime to `W`.  The prime-density theorem already selects such a
shift, but the older cofinal interface retained only the weaker inequality
`b < W`.

There is a second quantifier-order issue.  Converting AP cut discrepancy to
simplex face-cut discrepancy requires

```
Nat.Coprime N (Nat.factorial (r + 1)).
```

This is available after the cofinal argument selects a sufficiently large
prime modulus, but need not hold eventually at every natural modulus.

This file records the corrected interface.  Reduced-residue membership is
preserved through density selection, and the relative-counting comparison
is supplied by a callback invoked only after the prime modulus and its
factorial-coprimality proof have been constructed.
-/

namespace Wikipedia.SzemeredisTheorem

open Filter
open scoped Polynomial

/-- Cofinal-prime transference restricted to the reduced residue classes
that are actually produced by the W-trick density theorem. -/
def CofinalPrimeUniformReducedResidueWTrickedPrimeProgressionCount
    (k : ℕ) (α : ℝ) (W : ℕ) (δ c : ℝ) : Prop :=
  ∀ M₀ : ℕ,
    ∃ M : ℕ,
      M₀ ≤ M ∧ Nat.Prime (M + 1) ∧
        ∀ b : ℕ, b ∈ reducedResidues W →
          δ ≤
            mean
              (wTrickedPrimeWeight α W b :
                ZMod (M + 1) → ℝ) →
          c ≤
            cyclicAPCount k (M + 1)
              (wTrickedPrimeWeight α W b)



/-- The standard-cutoff cofinal obligation with reduced-residue membership
retained in the transference predicate. -/
def HasCofinalPrimeStandardReducedResidueWTrickedPrimeProgressionCounts :
    Prop :=
  ∀ k : ℕ, 3 ≤ k →
    ∃ (w : ℕ) (c : ℝ), 0 < c ∧
      CofinalPrimeUniformReducedResidueWTrickedPrimeProgressionCount
        k
        (primeScale k
          standardSmoothSieveCutoff.normalizer)
        (primorial w)
        (densityTarget k
          standardSmoothSieveCutoff.normalizer)
        c





end Wikipedia.SzemeredisTheorem
Source
https://github.com/plby/lean-proofs/blob/8822f7ddef30fadbd92e1c6ab4ed897af356af5e/src/latest/Wikipedia/GreenTao/ReducedResidueCofinalTransference.lean#L32-L172

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