Documentation

MathlibNt.SieveTheory.LinearSieve.LevelSupported.Q1MainTermAbsorption

Q1 main-term absorption #

Scope #

This file proves the q¹ main-term bound q1MainTermAbsorption from SwitchingPrinciple.lean:

∃ C₁ > 0, ∃ N₁, ∀ N ≥ N₁ Even N:
  q1MainTermSum N ≤ C₁·𝔖_trunc(N, z−1)·N/log²N

Here z = correctedChenZ N, y = correctedChenY N, P(N) = correctedChenSiftingProduct N (odd primes r < z with r ∤ N), F(N) = correctedChenForbiddenProduct N (primes r < z with r ≤ 2 or r | N), and Fodd(N) = F(N)/2 (the product of the odd prime factors of F when z ≥ 3).

Mathematical structure (sieve main terms in Halberstam--Richert Ch. 10; Chen 1973) #

For a fixed prime q ∈ [z, y), d | P, and e | F:

q1APMainValue N (lcm(lcm q d) e) = if Even (lcm(lcm q d) e) then [lcm(lcm q d) e | N−2] else li(N)/φ(lcm(lcm q d) e).

The numbers q, d, e are pairwise coprime: q ≥ z, all prime factors of P·F are < z, and P and F have disjoint prime-factor sets. In the odd part, q and d are odd, and e is odd exactly when e | Fodd. Thus lcm(lcm q d) e = q·d·e, and

q1CandidateAPMain N q = li(N)·Σ_{d|P} Σ_{e|Fodd} μ(d)μ(e)/φ(q·d·e) + (even-modulus correction, ≤ 0).

The odd part factors through the Möbius Euler-product identity (Mathlib's prodPrimeFactors_one_sub_of_squarefree):

Σ_{d|P} μ(d)/φ(d) = ∏{p|P} (1 − 1/(p−1)) =: q1SieveProduct N, Σ{e|Fodd} μ(e)/φ(e) = ∏_{p|Fodd} (1 − 1/(p−1)) =: q1ForbiddenOddProduct N,

The even part is exactly zero or negative, by Möbius inversion Σ_{d|m} μ(d) = [m = 1]:

EvenPart = −[q | N−2]·[gcd(P, N−2) = 1]·[gcd(Fodd, (N−2)/2) = 1] ≤ 0.

Consequently, for even N (where p ∤ N automatically excludes p = 2),

q1MainTermSum N ≤ li(N)·goldbachSieveProduct(N, z)·Σ_{q∈[z,y)} 1/φ(q).

Next:

Combining these estimates gives q1MainTermAbsorption, with C₁ = 20·a₂·(2·(log 7 + E)).

The analytic ingredients are the proved prime-reciprocal range bound and the goldbachNu / singularSeriesTruncated definitions in AnalyticNumberTheory.Sieve, the theorems MertensTheorem.primeProduct_asymptotic_order and sieveProduct_identity, and the logarithmic parameter bounds from TripleMain.lean.

Notation and definitions #

@[reducible, inline]

The logarithmic-integral main term for q¹: li(N) = N/log N, using the working definition in AnalyticNumberTheory.Sieve.

Equations
Instances For
    Inspect dependencies

    MathlibNt.SieveTheory.SwitchingPrinciple.q1LogarithmicIntegral · compiled type and proof/definition references.

    Real-valued Möbius weights.

    Equations
    Instances For
      Inspect dependencies

      MathlibNt.SieveTheory.SwitchingPrinciple.q1Mu · compiled type and proof/definition references.

      Inspect dependencies

      MathlibNt.SieveTheory.SwitchingPrinciple.correctedChenForbiddenOddPart · compiled type and proof/definition references.

      Main-term product over sifting primes: ∏_{p | P(N)} (1 − 1/(p−1)).

      Equations
      Instances For
        Inspect dependencies

        MathlibNt.SieveTheory.SwitchingPrinciple.q1SieveProduct · compiled type and proof/definition references.

        Main-term product over the odd forbidden prime factors: ∏_{p | Fodd(N)} (1 − 1/(p−1)).

        Equations
        Instances For
          Inspect dependencies

          MathlibNt.SieveTheory.SwitchingPrinciple.q1ForbiddenOddProduct · compiled type and proof/definition references.

          Even-modulus branch of the main term: if Even m then [m | N−2] else 0.

          Equations
          Instances For
            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1APMainEvenValue · compiled type and proof/definition references.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1CandidateAPMainEvenPart · compiled type and proof/definition references.

            1. Möbius sums: Σ_{d|n} μ(d) = [n = 1], Σ_{d|n, d|m} μ(d) = [gcd(m,n) = 1] #

            Real-valued Möbius inversion: Σ_{d | n} μ(d) = [n = 1].

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.sum_moebius_divisors_eq_if_one · compiled type and proof/definition references.

            Σ_{d | P, d | m} μ(d) = [gcd(m,P) = 1] (P ≠ 0).

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.sum_moebius_if_dvd_eq_if_gcd_one · compiled type and proof/definition references.

            2. Parity and coprimality lemmas #

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.two_dvd_correctedChenForbiddenProduct_of_three_le_z · compiled type and proof/definition references.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.forbiddenProduct_eq_two_mul_oddPart · compiled type and proof/definition references.

            The prime q is coprime to P: q ≥ z and all prime factors of P are < z.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.coprime_q_siftingProduct · compiled type and proof/definition references.

            The prime q is coprime to Fodd: q ≥ z and its prime factors are < z.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.coprime_q_forbiddenOddPart · compiled type and proof/definition references.

            P and Fodd are coprime because their prime-factor sets are disjoint: p ∤ N for p | P, whereas p | N for p | Fodd.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.coprime_sifting_forbiddenOddPart · compiled type and proof/definition references.

            The prime q is coprime to the forbidden-prime product F: all prime factors of F are < z ≤ q.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.coprime_q_forbiddenProduct · compiled type and proof/definition references.

            The sifting product P and the forbidden-prime product F are coprime: their prime-factor sets are disjoint.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.coprime_sifting_forbiddenProduct · compiled type and proof/definition references.

            3. Odd-even decomposition of the q¹ main term #

            Exact odd-even decomposition: q1CandidateAPMain N q = li(N)·Σ_{d|P}Σ_{e|Fodd} μ(d)μ(e)/φ(q·d·e) + q1CandidateAPMainEvenPart N q.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1CandidateAPMain_eq_oddSum_add_evenPart · compiled type and proof/definition references.

            4. Exact evaluation of the even-modulus contribution (Möbius inversion) #

            Exact even-modulus contribution: −[q | N−2]·[gcd(P,N−2)=1]·[gcd(Fodd,(N−2)/2)=1].

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1CandidateAPMainEvenPart_eq · compiled type and proof/definition references.

            The even-modulus contribution is nonpositive: its exact value is the negative of a product of three nonnegative indicator factors.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1CandidateAPMainEvenPart_nonpos · compiled type and proof/definition references.

            5. Möbius Euler-product factorization: Σ_{d|P} μ(d)/φ(d) = ∏_{p|P} (1 − 1/(p−1)) #

            Möbius Euler product for P: Σ_{d | P} μ(d)/φ(d) = q1SieveProduct N.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1Sum_nu_sifting · compiled type and proof/definition references.

            Möbius Euler product for Fodd: Σ_{e | Fodd} μ(e)/φ(e) = q1ForbiddenOddProduct N.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1Sum_nu_forbiddenOddPart · compiled type and proof/definition references.

            Factorization of the odd double sum: Σ_{d|P} Σ_{e|Fodd} μ(d)μ(e)/φ(q·d·e) = (1/φ(q))·q1SieveProduct·q1ForbiddenOddProduct, since q, d, e are pairwise coprime.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1OddSum_eq_products · compiled type and proof/definition references.

            6. Bounds for each q and decomposition of the main-term sum #

            Bound for each q in the q¹ main term: q1CandidateAPMain N q ≤ li(N)/φ(q)·q1SieveProduct·q1ForbiddenOddProduct.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1CandidateAPMain_le · compiled type and proof/definition references.

            The main-term product over sifting primes is nonnegative.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1SieveProduct_nonneg · compiled type and proof/definition references.

            The main-term product over odd forbidden primes is at most 1: each factor lies in (0, 1].

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1ForbiddenOddProduct_le_one · compiled type and proof/definition references.

            The main-term sifting product equals the Goldbach sieve product. For even N, the condition p ∤ N excludes p = 2 on both sides.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1SieveProduct_eq_goldbachSieveProduct · compiled type and proof/definition references.

            Main-term sum decomposition: q1MainTermSum N ≤ li(N)·goldbachSieveProduct(N, z)·Σ_{q∈[z,y)} 1/φ(q).

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1MainTermSum_le · compiled type and proof/definition references.

            7. Combining analytic estimates: prime reciprocals, log(z−1), and absorption #

            theorem MathlibNt.SieveTheory.SwitchingPrinciple.q1_qSum_phi_inv_bound :
            ∃ (C₀ : ℝ), 0 < C₀ ∧ ∀ (N : ℕ), 2 ^ 110 < N → ∑ q ∈ Finset.range (correctedChenY N) with Nat.Prime q ∧ correctedChenZ N ≤ q, 1 / ↑q.totient ≤ C₀

            Reciprocal-totient sum bound: for N > 2^110, Σ_{q∈[z,y)} 1/φ(q) ≤ C₀, by Mertens' second theorem and log y/log z ≤ 7.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1_qSum_phi_inv_bound · compiled type and proof/definition references.

            Lower bound for log(z-1): for N >= 2^40, (1/20)*log N <= log(z-1), since z >= N^{1/10}-1 >= N^{1/20}+1.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1_log_z_sub_one_lower · compiled type and proof/definition references.

            The truncated singular-series definitions in MathlibNt and AnalyticNumberTheory agree: their local-factor formulas are identical.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.chenSingularSeriesTruncated_eq_ant · compiled type and proof/definition references.

            q¹ main-term absorption: the decomposition, Mertens' theorem, and the prime-reciprocal sum bound combine into the form C₁·𝔖_trunc·N/log²N.

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1MainTermAbsorption_holds · compiled type and proof/definition references.

            The finite delta-one Pan bridge for the q¹ error #

            Inspect dependencies

            MathlibNt.SieveTheory.SwitchingPrinciple.q1SwitchingPrimes · compiled type and proof/definition references.

            The product containing both small-prime divisor lanes in the q¹ Möbius expansion. Its two factors are coprime and squarefree.

            Equations
            Instances For
              Inspect dependencies

              MathlibNt.SieveTheory.SwitchingPrinciple.q1SmallModulusProduct · compiled type and proof/definition references.

              The reduced-residue delta-one Pan error used by the q¹ bridge. A non-reduced residue is set to zero and left to the explicit truncation input.

              Equations
              Instances For
                Inspect dependencies

                MathlibNt.SieveTheory.SwitchingPrinciple.q1PanReferenceError · compiled type and proof/definition references.

                On an even modulus and even source, the Pan reduced-residue reference vanishes because 2 divides both the residue and the modulus.

                Inspect dependencies

                MathlibNt.SieveTheory.SwitchingPrinciple.q1PanReferenceError_even_zero · compiled type and proof/definition references.

                The complete diagnostic difference vanishes on every even-modulus lane; the obstruction in q1PanDeltaOneTruncationSum is therefore entirely in the odd non-reduced lanes (apart from the logarithmic-integral shift).

                Inspect dependencies

                MathlibNt.SieveTheory.SwitchingPrinciple.abs_q1APError_sub_panReference_even_zero · compiled type and proof/definition references.

                Exact obstruction on an odd non-reduced lane: the diagnostic "truncation" summand is the full AP error, including its li(N) / φ(m) main term.

                Inspect dependencies

                MathlibNt.SieveTheory.SwitchingPrinciple.abs_q1APError_sub_panReference_of_odd_not_coprime · compiled type and proof/definition references.

                Inspect dependencies

                MathlibNt.SieveTheory.SwitchingPrinciple.q1PanDeltaOneRawSum · compiled type and proof/definition references.

                A diagnostic lcm-fibre majorant for the delta-one Pan sum. After both original coprime divisor lanes are enlarged to all divisors of the squarefree small-prime product, 3^ω(m) is the exact number of pairs in that enlarged square whose lcm is m; it is not the multiplicity of the original lanes.

                Equations
                Instances For
                  Inspect dependencies

                  MathlibNt.SieveTheory.SwitchingPrinciple.q1PanDeltaOneWeightedSum · compiled type and proof/definition references.

                  Everything not supplied by the reduced-residue delta-one Pan maximum: the li(N) versus li(N-2) main shift, the non-reduced residue lane, and the even-modulus normalization (which is actually zero for large even N).

                  Equations
                  Instances For
                    Inspect dependencies

                    MathlibNt.SieveTheory.SwitchingPrinciple.q1PanDeltaOneTruncationSum · compiled type and proof/definition references.

                    Diagnostic full-divisor-lane delta-one estimate. This is strictly stronger than the classical Pan mean-value theorem: m runs through every divisor of the small-prime product and lcm q m has no N^(1/2) / log(N)^B cutoff. It is retained only to audit the finite lcm reindexing, not as an active Chen analytic input.

                    Equations
                    Instances For
                      Inspect dependencies

                      MathlibNt.SieveTheory.SwitchingPrinciple.Q1DeltaOnePanMeanValue · compiled type and proof/definition references.

                      Diagnostic complement to Q1DeltaOnePanMeanValue. Besides the harmless li(N) versus li(N-2) shift, this sum contains every odd non-reduced residue lane. On such a lane q1PanReferenceError is zero while q1APError still contains its li(N) / φ(m) main term, with the full divisor-pair multiplicity. Consequently this is not a proved truncation estimate and is not a canonical literature hypothesis.

                      Equations
                      Instances For
                        Inspect dependencies

                        MathlibNt.SieveTheory.SwitchingPrinciple.Q1DeltaOnePanTruncationInput · compiled type and proof/definition references.

                        Diagnostic form of the former q¹ frontier: arbitrary inverse-log saving for the complete positive Möbius error aggregate. This is not a published Pan/Bombieri--Vinogradov theorem, because its full divisor lanes have no level cutoff. It is retained only to record the old implication to q1APErrorUniformBound.

                        Equations
                        Instances For
                          Inspect dependencies

                          MathlibNt.SieveTheory.SwitchingPrinciple.Q1FullPositiveErrorAggregate · compiled type and proof/definition references.

                          A q¹ AP error is bounded by the reduced-residue Pan maximum plus the explicit exceptional difference.

                          Inspect dependencies

                          MathlibNt.SieveTheory.SwitchingPrinciple.abs_q1APError_le_panMaxY_add_truncation · compiled type and proof/definition references.

                          Exact finite reduction of the q¹ error to the raw delta-one Pan sum and the explicit exceptional/truncation sum.

                          Inspect dependencies

                          MathlibNt.SieveTheory.SwitchingPrinciple.q1ErrorTermSum_le_rawPan_add_truncation · compiled type and proof/definition references.

                          The union of the two small-prime products is squarefree.

                          Inspect dependencies

                          MathlibNt.SieveTheory.SwitchingPrinciple.q1SmallModulusProduct_squarefree · compiled type and proof/definition references.

                          The union of the two small-prime products is nonzero.

                          Inspect dependencies

                          MathlibNt.SieveTheory.SwitchingPrinciple.q1SmallModulusProduct_ne_zero · compiled type and proof/definition references.

                          The raw q¹ Möbius sum is bounded by its canonical 3^ω lcm-fibre packaging.

                          Inspect dependencies

                          MathlibNt.SieveTheory.SwitchingPrinciple.q1PanDeltaOneRawSum_le_weightedSum · compiled type and proof/definition references.

                          Fully finite q¹ error bridge: all Möbius multiplicities and lcm fibres are absorbed into the 3^ω delta-one Pan sum; only the explicit exceptional truncation remains.

                          Inspect dependencies

                          MathlibNt.SieveTheory.SwitchingPrinciple.q1ErrorTermSum_le_deltaOnePan_add_truncation · compiled type and proof/definition references.

                          The fixed-delta-one mean-value theorem and its explicit truncation contract produce the q¹ AP error input. This is a valid implication between diagnostic full-lane predicates, but it is not the canonical literature route.

                          Inspect dependencies

                          MathlibNt.SieveTheory.SwitchingPrinciple.q1APErrorUniformBound_of_deltaOnePan · compiled type and proof/definition references.

                          The obsolete full-positive-error aggregate supplies the single A = 3 estimate used by the legacy diagnostic consumer.

                          Inspect dependencies

                          MathlibNt.SieveTheory.SwitchingPrinciple.q1APErrorUniformBound_of_weightedAggregate · compiled type and proof/definition references.

                          The unconditional q¹ main-term absorption and the diagnostic full-lane Pan bridge give a q¹ count bound.

                          Inspect dependencies

                          MathlibNt.SieveTheory.SwitchingPrinciple.hq1_of_deltaOnePanInputs · compiled type and proof/definition references.

                          A designated q¹ constant extracted from the delta-one Pan bridge. This lets downstream numerical hypotheses refer to the same witness that supplies the q¹ estimate, rather than quantifying over all admissible (and arbitrarily enlargeable) constants.

                          Equations
                          Instances For
                            Inspect dependencies

                            MathlibNt.SieveTheory.SwitchingPrinciple.q1DeltaOnePanConstant · compiled type and proof/definition references.

                            Positivity and the eventual q¹ estimate for the designated bridge constant.

                            Inspect dependencies

                            MathlibNt.SieveTheory.SwitchingPrinciple.q1DeltaOnePanConstant_spec · compiled type and proof/definition references.