AFTD Auto-Formalizing Theoretical Domains

op_153_subexp_bound_of_eventually_bound

theoremverified

If a difference-avoiding set in {1, ..., N} satisfies |A| ≤ C·N·exp(−c√(log N · log log N)) for all sufficiently large N (with constants c, C depending on h), then it satisfies the same shape of bound for *all* N ≥ 3, at the cost of enlarging C: the finitely many N below the threshold are absorbed by the trivial bound |A| ≤ N.

Statement

theorem op_153_subexp_bound_of_eventually_bound (h : Polynomial ℤ) :
    (∃ c > 0, ∃ C > 0, ∃ N₀ : ℕ, ∀ N : ℕ, N₀ ≤ N →
      ∀ A ⊆ Finset.Icc 1 N,
      (∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = h.eval (n : ℤ)) →
      (A.card : ℝ) ≤ C * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))))) →
    ∃ c > 0, ∃ C > 0, ∀ N : ℕ, 3 ≤ N →
      ∀ A ⊆ Finset.Icc 1 N,
      (∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = h.eval (n : ℤ)) →
      (A.card : ℝ) ≤ C * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))))
Source
step towards op_153_subexp_bound_intersective_quadratic
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof extends an eventual subexponential upper bound on difference-avoiding subsets $A \subseteq \{1, \dots, N\}$ to all $N \ge 3$ by adjusting the constant $C$. Setting $N_1 = \max(N_0, 3)$ and $C' = \max(C, \exp(c \sqrt{\log N_1 \log \log N_1}))$, we split on whether $N \ge N_1$. For $N \ge N_1$, the assumption applies directly because $N \ge N_0$ and $C \le C'$. For $3 \le N < N_1$, the trivial cardinality bound $|A| \le N$ is absorbed because the decay factor $\exp(-c\sqrt{\log N \log \log N})$ is at least $1/C'$, so $N \le C' N \exp(-c \sqrt{\log N \log \log N})$.

  1. Define threshold $N_1 = \max(N_0, 3)$ and enlarged constant $C' = \max(C, \exp(c \sqrt{\log N_1 \log \log N_1}))$, verifying $C' > 0$.

    From the hypothesis, we obtain constants $c > 0$, $C > 0$, an initial threshold $N_0 \in \mathbb{N}$, and the bound for all $N \ge N_0$. We define $N_1 = \max(N_0, 3)$ to ensure $N_1 \ge 3$, and define $C'$ as the maximum of $C$ and $\exp(c \sqrt{\log N_1 \log \log N_1})$. To satisfy the existential quantifier, we provide $c$ and $C'$, verifying that $C' > 0$ because $C' \ge C > 0$.

    lines 11–16

    uses lt_max_iff.mpr, Or.inl

      rintro ⟨c, hcpos, C, hCpos, N₀, hN₀⟩
      set N₁ : ℕ := max N₀ 3 with hN₁
      set C' : ℝ := max C (Real.exp (c * Real.sqrt (Real.log (N₁ : ℝ) * Real.log (Real.log (N₁ : ℝ))))) with hC'
      refine ⟨c, hcpos, C', ?_, ?_⟩
      · rw [hC']
        exact lt_max_iff.mpr (Or.inl hCpos)
  2. For $N \ge N_1$, the desired subexponential bound holds for any difference-avoiding set $A \subseteq \{1, \dots, N\}$.

    We introduce an integer $N \ge 3$, a subset $A \subseteq \{1, \dots, N\}$, and the hypothesis that differences of distinct elements in $A$ avoid the evaluation of the polynomial $h$ at positive integers. We consider the case $N_1 \le N$. Since $N_1 = \max(N_0, 3) \ge N_0$, transitivity gives $N_0 \le N$. The assumed asymptotic bound therefore applies to $A$, yielding $|A| \le C N \exp(-c \sqrt{\log N \log \log N})$. Since $C \le C'$ and both $N$ and the exponential factor are non-negative, multiplying this inequality by $N \exp(-c \sqrt{\log N \log \log N})$ shows $|A| \le C' N \exp(-c \sqrt{\log N \log \log N})$.

    lines 17–28

    uses le_trans, le_max_left, Nat.cast_nonneg, mul_le_mul_of_nonneg_right, Real.exp_nonneg

      · intro N hN A hA hdiff
        by_cases hNN₁ : N₁ ≤ N
        · have hN₀N : N₀ ≤ N := le_trans (le_max_left N₀ 3) hNN₁
          have hmain := hN₀ N hN₀N A hA hdiff
          have hCle : C ≤ C' := by rw [hC']; exact le_max_left _ _
          have hNnonneg : (0 : ℝ) ≤ (N : ℝ) := Nat.cast_nonneg N
          calc
            (A.card : ℝ) ≤ C * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) := hmain
            _ ≤ C' * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) := by
              apply mul_le_mul_of_nonneg_right
              · apply mul_le_mul_of_nonneg_right hCle hNnonneg
              · exact Real.exp_nonneg _
  3. When $N < N_1$, the logarithmic factors are non-negative and bounded above by those of $N_1$.

    In the remaining case $N < N_1$, the cardinality of $A$ is bounded trivially by $|A| \le N$ because $A \subseteq \{1, \dots, N\}$. Using $3 \le N$ and the numerical inequality $\log 3 > 1$, we establish that $\log N > 1 > 0$ and $\log \log N \ge 0$. The same holds for $N_1$ since $N_1 \ge 3$. Since $N \le N_1$, the monotonicity of the logarithm implies $\log N \le \log N_1$ and $\log \log N \le \log \log N_1$. Moreover, by construction, $\exp(c \sqrt{\log N_1 \log \log N_1}) \le C'$.

    lines 29–56

    uses Nat.lt_of_not_ge, Finset.card_le_card, lt_of_lt_of_le, Real.log_le_log, Real.log_three_gt_d9, Real.log_nonneg, le_max_right, le_of_lt

        · have hNlt : N < N₁ := Nat.lt_of_not_ge hNN₁
          have hAcard : A.card ≤ N := by
            have hcard := Finset.card_le_card hA
            simpa using hcard
          have hAcardR : (A.card : ℝ) ≤ (N : ℝ) := by exact_mod_cast hAcard
          have hN3 : 3 ≤ N := hN
          have hNpos : (0 : ℝ) < (N : ℝ) := by exact_mod_cast (lt_of_lt_of_le (by norm_num : 0 < 3) hN3)
          have hlogN_gt_one : (1 : ℝ) < Real.log (N : ℝ) := by
            have hNR : (3 : ℝ) ≤ (N : ℝ) := by exact_mod_cast hN3
            have hlog3le : Real.log 3 ≤ Real.log (N : ℝ) := Real.log_le_log (by norm_num) hNR
            linarith [Real.log_three_gt_d9, hlog3le]
          have hlogNpos : 0 < Real.log (N : ℝ) := by linarith
          have hloglogN_nonneg : 0 ≤ Real.log (Real.log (N : ℝ)) := Real.log_nonneg hlogN_gt_one.le
          have hN₁3 : 3 ≤ N₁ := le_max_right N₀ 3
          have hlogN₁_gt_one : (1 : ℝ) < Real.log (N₁ : ℝ) := by
            have hN₁R : (3 : ℝ) ≤ (N₁ : ℝ) := by exact_mod_cast hN₁3
            have hlog3le : Real.log 3 ≤ Real.log (N₁ : ℝ) := Real.log_le_log (by norm_num) hN₁R
            linarith [Real.log_three_gt_d9, hlog3le]
          have hlogN₁pos : 0 < Real.log (N₁ : ℝ) := by linarith
          have hlog_le : Real.log (N : ℝ) ≤ Real.log (N₁ : ℝ) := by
            apply Real.log_le_log hNpos
            exact_mod_cast le_of_lt hNlt
          have hloglog_le : Real.log (Real.log (N : ℝ)) ≤ Real.log (Real.log (N₁ : ℝ)) := by
            apply Real.log_le_log hlogNpos
            exact hlog_le
          have hE : Real.exp (c * Real.sqrt (Real.log (N₁ : ℝ) * Real.log (Real.log (N₁ : ℝ)))) ≤ C' := by
            rw [hC']
            exact le_max_right _ _
  4. For $3 \le N < N_1$, the subexponential decay factor satisfies $1 \le C' \exp(-c \sqrt{\log N \log \log N})$.

    By multiplying the inequalities $\log N \le \log N_1$ and $\log \log N \le \log \log N_1$, we obtain $\log N \log \log N \le \log N_1 \log \log N_1$. Taking square roots, scaling by $c > 0$, and exponentiating gives $\exp(c \sqrt{\log N \log \log N}) \le \exp(c \sqrt{\log N_1 \log \log N_1}) \le C'$. Multiplying both sides by the positive factor $\exp(-c \sqrt{\log N \log \log N})$ and using $\exp(x) \exp(-x) = \exp(0) = 1$, we deduce that $1 \le C' \exp(-c \sqrt{\log N \log \log N})$.

    lines 57–80

    uses mul_le_mul, Real.sqrt_le_sqrt, mul_le_mul_of_nonneg_left, Real.exp_le_exp, le_trans, mul_le_mul_of_nonneg_right, Real.exp_nonneg, Real.exp_add, Real.exp_zero

          have hone : (1 : ℝ) ≤ C' * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) := by
            have hprod_le : Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)) ≤
                Real.log (N₁ : ℝ) * Real.log (Real.log (N₁ : ℝ)) := by
              exact mul_le_mul hlog_le hloglog_le hloglogN_nonneg hlogN₁pos.le
            have hsqrt_le : Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))) ≤
                Real.sqrt (Real.log (N₁ : ℝ) * Real.log (Real.log (N₁ : ℝ))) :=
              Real.sqrt_le_sqrt hprod_le
            have hcS_le : c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))) ≤
                c * Real.sqrt (Real.log (N₁ : ℝ) * Real.log (Real.log (N₁ : ℝ))) :=
              mul_le_mul_of_nonneg_left hsqrt_le hcpos.le
            have hexp_le : Real.exp (c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) ≤
                Real.exp (c * Real.sqrt (Real.log (N₁ : ℝ) * Real.log (Real.log (N₁ : ℝ)))) := by
              exact (Real.exp_le_exp).mpr hcS_le
            have hS_le_C' : Real.exp (c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) ≤ C' :=
              le_trans hexp_le hE
            have h := mul_le_mul_of_nonneg_right hS_le_C'
              (Real.exp_nonneg (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))))
            have hL : Real.exp (c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) *
                Real.exp (-(c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))))) = 1 := by
              rw [← Real.exp_add]
              have hzero : c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))) +
                  (-(c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))))) = 0 := by ring
              rw [hzero, Real.exp_zero]
            simpa [hL] using h
  5. The trivial bound $|A| \le N$ yields $|A| \le C' N \exp(-c \sqrt{\log N \log \log N})$ for $N < N_1$.

    Since $|A| \le N = N \cdot 1$ and $1 \le C' \exp(-c \sqrt{\log N \log \log N})$ with $N \ge 0$, multiplying the inequality by $N$ gives $|A| \le C' N \exp(-c \sqrt{\log N \log \log N})$, completing the proof.

    lines 81–86

    uses mul_le_mul_of_nonneg_left

          calc
            (A.card : ℝ) ≤ (N : ℝ) := hAcardR
            _ = (N : ℝ) * 1 := by ring
            _ ≤ (N : ℝ) * (C' * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))))) := by
              exact mul_le_mul_of_nonneg_left hone hNpos.le
            _ = C' * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) := by ring
lt_max_iff.mpr
if $a < b$ or $a < c$, then $a < \max(b, c)$
Or.inl
proves a disjunction $a \lor b$ from a proof of its left conjunct $a$
le_trans
transitivity of inequality: if $a \le b$ and $b \le c$, then $a \le c$
le_max_left
$a \le \max(a, b)$ for any elements $a$ and $b$
Nat.cast_nonneg
the canonical injection of a natural number into an ordered semiring is non-negative: $0 \le n$
mul_le_mul_of_nonneg_right
if $b \le c$ and $0 \le a$, then $b a \le c a$
Real.exp_nonneg
the real exponential is always non-negative: $\exp(x) \ge 0$ for all $x \in \mathbb{R}$
Nat.lt_of_not_ge
for natural numbers, if $b$ is not greater than or equal to $a$, then $b < a$
Finset.card_le_card
if $s \subseteq t$ for finite sets, then $|s| \le |t|$
lt_of_lt_of_le
if $a < b$ and $b \le c$, then $a < c$
Real.log_le_log
the real logarithm is monotone: if $0 < x \le y$, then $\log x \le \log y$
Real.log_three_gt_d9
the numerical lower bound $1.0986122885 < \log 3$
Real.log_nonneg
if $x \ge 1$, then $\log x \ge 0$
le_max_right
$b \le \max(a, b)$ for any elements $a$ and $b$
le_of_lt
strict inequality implies non-strict inequality: if $a < b$, then $a \le b$
mul_le_mul
if $a \le b$ and $c \le d$ with $0 \le c$ and $0 \le b$, then $a c \le b d$
Real.sqrt_le_sqrt
the real square root is monotone: if $x \le y$, then $\sqrt{x} \le \sqrt{y}$
mul_le_mul_of_nonneg_left
if $b \le c$ and $0 \le a$, then $a b \le a c$
Real.exp_le_exp
the real exponential is strictly order-preserving: $\exp(x) \le \exp(y) \iff x \le y$
Real.exp_add
the exponential maps addition to multiplication: $\exp(x + y) = \exp(x) \exp(y)$
Real.exp_zero
the exponential of zero is one: $\exp(0) = 1$

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Small-N absorption: an eventual subexponential difference bound implies the same bound for every N ≥ 3, with a larger constant. -/theorem op_153_subexp_bound_of_eventually_bound (h : Polynomial ℤ) :    (∃ c > 0, ∃ C > 0, ∃ N₀ : ℕ, ∀ N : ℕ, N₀ ≤ N →      ∀ A ⊆ Finset.Icc 1 N,      (∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = h.eval (n : ℤ)) →      (A.card : ℝ) ≤ C * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))))) →    ∃ c > 0, ∃ C > 0, ∀ N : ℕ, 3 ≤ N →      ∀ A ⊆ Finset.Icc 1 N,      (∀ a ∈ A, ∀ b ∈ A, a ≠ b → ¬ ∃ n : ℕ, 0 < n ∧ (a : ℤ) - b = h.eval (n : ℤ)) →      (A.card : ℝ) ≤ C * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) := by  rintro ⟨c, hcpos, C, hCpos, N₀, hN₀⟩  set N₁ : ℕ := max N₀ 3 with hN₁  set C' : ℝ := max C (Real.exp (c * Real.sqrt (Real.log (N₁ : ℝ) * Real.log (Real.log (N₁ : ℝ))))) with hC'  refine ⟨c, hcpos, C', ?_, ?_⟩  · rw [hC']    exact lt_max_iff.mpr (Or.inl hCpos)  · intro N hN A hA hdiff    by_cases hNN₁ : N₁ ≤ N    · have hN₀N : N₀ ≤ N := le_trans (le_max_left N₀ 3) hNN₁      have hmain := hN₀ N hN₀N A hA hdiff      have hCle : C ≤ C' := by rw [hC']; exact le_max_left _ _      have hNnonneg : (0 : ℝ) ≤ (N : ℝ) := Nat.cast_nonneg N      calc        (A.card : ℝ) ≤ C * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) := hmain        _ ≤ C' * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) := by          apply mul_le_mul_of_nonneg_right          · apply mul_le_mul_of_nonneg_right hCle hNnonneg          · exact Real.exp_nonneg _    · have hNlt : N < N₁ := Nat.lt_of_not_ge hNN₁      have hAcard : A.card ≤ N := by        have hcard := Finset.card_le_card hA        simpa using hcard      have hAcardR : (A.card : ℝ) ≤ (N : ℝ) := by exact_mod_cast hAcard      have hN3 : 3 ≤ N := hN      have hNpos : (0 : ℝ) < (N : ℝ) := by exact_mod_cast (lt_of_lt_of_le (by norm_num : 0 < 3) hN3)      have hlogN_gt_one : (1 : ℝ) < Real.log (N : ℝ) := by        have hNR : (3 : ℝ) ≤ (N : ℝ) := by exact_mod_cast hN3        have hlog3le : Real.log 3 ≤ Real.log (N : ℝ) := Real.log_le_log (by norm_num) hNR        linarith [Real.log_three_gt_d9, hlog3le]      have hlogNpos : 0 < Real.log (N : ℝ) := by linarith      have hloglogN_nonneg : 0 ≤ Real.log (Real.log (N : ℝ)) := Real.log_nonneg hlogN_gt_one.le      have hN₁3 : 3 ≤ N₁ := le_max_right N₀ 3      have hlogN₁_gt_one : (1 : ℝ) < Real.log (N₁ : ℝ) := by        have hN₁R : (3 : ℝ) ≤ (N₁ : ℝ) := by exact_mod_cast hN₁3        have hlog3le : Real.log 3 ≤ Real.log (N₁ : ℝ) := Real.log_le_log (by norm_num) hN₁R        linarith [Real.log_three_gt_d9, hlog3le]      have hlogN₁pos : 0 < Real.log (N₁ : ℝ) := by linarith      have hlog_le : Real.log (N : ℝ) ≤ Real.log (N₁ : ℝ) := by        apply Real.log_le_log hNpos        exact_mod_cast le_of_lt hNlt      have hloglog_le : Real.log (Real.log (N : ℝ)) ≤ Real.log (Real.log (N₁ : ℝ)) := by        apply Real.log_le_log hlogNpos        exact hlog_le      have hE : Real.exp (c * Real.sqrt (Real.log (N₁ : ℝ) * Real.log (Real.log (N₁ : ℝ)))) ≤ C' := by        rw [hC']        exact le_max_right _ _      have hone : (1 : ℝ) ≤ C' * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) := by        have hprod_le : Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)) ≤            Real.log (N₁ : ℝ) * Real.log (Real.log (N₁ : ℝ)) := by          exact mul_le_mul hlog_le hloglog_le hloglogN_nonneg hlogN₁pos.le        have hsqrt_le : Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))) ≤            Real.sqrt (Real.log (N₁ : ℝ) * Real.log (Real.log (N₁ : ℝ))) :=          Real.sqrt_le_sqrt hprod_le        have hcS_le : c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))) ≤            c * Real.sqrt (Real.log (N₁ : ℝ) * Real.log (Real.log (N₁ : ℝ))) :=          mul_le_mul_of_nonneg_left hsqrt_le hcpos.le        have hexp_le : Real.exp (c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) ≤            Real.exp (c * Real.sqrt (Real.log (N₁ : ℝ) * Real.log (Real.log (N₁ : ℝ)))) := by          exact (Real.exp_le_exp).mpr hcS_le        have hS_le_C' : Real.exp (c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) ≤ C' :=          le_trans hexp_le hE        have h := mul_le_mul_of_nonneg_right hS_le_C'          (Real.exp_nonneg (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))))        have hL : Real.exp (c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) *            Real.exp (-(c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))))) = 1 := by          rw [← Real.exp_add]          have hzero : c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))) +              (-(c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))))) = 0 := by ring          rw [hzero, Real.exp_zero]        simpa [hL] using h      calc        (A.card : ℝ) ≤ (N : ℝ) := hAcardR        _ = (N : ℝ) * 1 := by ring        _ ≤ (N : ℝ) * (C' * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ))))) := by          exact mul_le_mul_of_nonneg_left hone hNpos.le        _ = C' * (N : ℝ) * Real.exp (-c * Real.sqrt (Real.log (N : ℝ) * Real.log (Real.log (N : ℝ)))) := by ring
See it in the graphDiscuss this resultChallenge it