op_153_subexp_bound_of_eventually_bound
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})$.
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$.
uses
lt_max_iff.mpr,Or.inlrintro ⟨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)
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})$.
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 _
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'$.
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 _ _
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})$.
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_zerohave 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
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.
uses
mul_le_mul_of_nonneg_leftcalc (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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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