Pairwise coprime odd numbers in short windows (logarithmic form)

Proved

J6Sieve.exists_coprime_in_windows_of_log

by xuanji · Oct 19, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryinteger-multiplicationkappa-improvement

Let $d, X, H$ and $A_i$ ( $i < d$ ) be natural numbers with $A_i + H \le X$ . If

4\,(\log_2(4(d(\log_2 X + 1) + 1)) + 2)^2 \le \log_2 H

(integer binary logarithms), then there are pairwise coprime odd $s_i$ with $A_i < s_i \le A_i + H$ . Thus windows of length $2^{O(\log^2 \log X)}$ suffice when $d$ is polylogarithmic in $X$ .

In Lean:

theorem J6Sieve.exists_coprime_in_windows_of_log (d X H : ℕ) (A : Fin d → ℕ)
    (hA : ∀ i, A i + H ≤ X)
    (hH : 4 * (Nat.log 2 (4 * (d * (Nat.log 2 X + 1) + 1)) + 2) ^ 2 ≤ Nat.log 2 H) :
    ∃ s : Fin d → ℕ, (∀ i, Odd (s i) ∧ A i < s i ∧ s i ≤ A i + H) ∧
      Pairwise (fun i j => Nat.Coprime (s i) (s j))

Formalization Note. Part of the Lean formalization of the round-six κ-improvement (integer-multiplication-kappa campaign, target IntMul.Kappa.jain_round6_framework). The statement is copied verbatim from the Lean development; the platform node carries the same declaration name. Definitions it mentions live in the IntMul_Kappa_R6_Defs* bundles (on top of the published κ bundles IntMul_Kappa_K_Defs*).

Preamble

-- Round-six κ development (integer-multiplication-kappa), generated by skeleton subtraction.

import Mathlib

set_option autoImplicit false
set_option relaxedAutoImplicit false
set_option maxHeartbeats 1000000

open Finset

Formal statement

theorem J6Sieve.exists_coprime_in_windows_of_log (d X H : ℕ) (A : Fin d → ℕ)
    (hA : ∀ i, A i + H ≤ X)
    (hH : 4 * (Nat.log 2 (4 * (d * (Nat.log 2 X + 1) + 1)) + 2) ^ 2 ≤ Nat.log 2 H) :
    ∃ s : Fin d → ℕ, (∀ i, Odd (s i) ∧ A i < s i ∧ s i ≤ A i + H) ∧
      Pairwise (fun i j => Nat.Coprime (s i) (s j)) := by sorry

Source

S. Jain, round-six networks for the integer-multiplication κ-improvement campaign (https://github.com/Swapnil-jain/integer-mult-kappa, commit 5868dc7) and D. Colkitt, integer-mult-bounds (https://github.com/CrocSwap/integer-mult-bounds); target `IntMul.Kappa.jain_round6_framework`. Lean declaration `J6Sieve.exists_coprime_in_windows_of_log`, Solutions/J6Sieve.lean (lines 132–143) of the round-six development.

View graph