one_layered_linear_bound_sum_le
For integers r ≥ 2, k ≥ 1, r ≤ m, and S with k * r ≤ S ≤ 2 * m - r, the block sum 2^(r - 2) * (S - k * r) + k is at most 2^(r - 1) * (m - r) + 1.
Statement
theorem one_layered_linear_bound_sum_le (m r k S : ℕ) (hr : 2 ≤ r) (hk : 1 ≤ k) (hm : r ≤ m)
(hS : S ≤ 2 * m - r) (hkr : k * r ≤ S) :
2 ^ (r - 2) * (S - k * r) + k ≤ 2 ^ (r - 1) * (m - r) + 1- Source
- arXiv:2611.08071 Theorem 2.1
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
Read back from the Lean
For all natural numbers $m$, $r$, $k$, and $S$, if $2 \le r$, $1 \le k$, $r \le m$, $S \le 2m - r$, and $k \cdot r \le S$, then $2^{r - 2} \cdot (S - k \cdot r) + k \le 2^{r - 1} \cdot (m - r) + 1$ (where all subtractions and operations are over $\mathbb{N}$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Setting P = 2^(r - 2), the desired inequality rewrites as P * (S - k * r) + k ≤ 2 * P * (m - r) + 1. The key algebraic insight is that the difference (2 * P * (m - r) + 1) - (P * (S - k * r) + k) decomposes as the sum of two terms: P * (2 * m - r - S) and (k - 1) * (P * r - 1). The first term is non-negative because S ≤ 2 * m - r and P ≥ 1, while the second term is non-negative because k ≥ 1 and P * r ≥ 1 * 2 = 2. After casting to the integers, linear arithmetic combines these facts to conclude the inequality.
The power 2^(r - 1) on the right-hand side factors as 2^(r - 2) * 2.
Since r ≥ 2, we have r - 1 = (r - 2) + 1. By `pow_succ` and commutativity of multiplication (`mul_comm`), 2^(r - 1) = 2^(r - 2) * 2. Rewriting with this identity aligns the base power of 2 with that on the left-hand side.
uses
pow_succ,mul_commhave hr1 : r - 1 = (r - 2) + 1 := by omega have hpow : 2 ^ (r - 1) = 2 ^ (r - 2) * 2 := by rw [hr1, pow_succ, mul_comm] rw [hpow]
The inequality is cast to the integers ℤ, taking the form P * (S - k * r) + k ≤ 2 * P * (m - r) + 1 where P = 2^(r - 2).
Using the hypotheses k * r ≤ S and r ≤ m, the subtractions do not underflow, allowing the goal to be transferred to ℤ. Abbreviating 2^(r - 2) as P simplifies the inequality to P * (S - k * r) + k ≤ P * 2 * (m - r) + 1.
zify [hkr, hm] set P : ℤ := (2 : ℤ) ^ (r - 2) change P * (↑S - ↑k * ↑r) + ↑k ≤ P * 2 * (↑m - ↑r) + 1
P ≥ 1 and r ≥ 2 in ℤ.
Because 1 ≤ 2, any natural power of 2 is at least 1 by `one_le_pow₀`, so P ≥ 1. The bound r ≥ 2 in ℤ follows directly from the assumption r ≥ 2 in ℕ.
uses
one_le_pow₀have hP : 1 ≤ P := one_le_pow₀ (by decide) have hrZ : 2 ≤ (r : ℤ) := by omega
0 ≤ P * (2 * m - r - S).
The hypothesis S ≤ 2 * m - r implies 2 * m - r - S ≥ 0. Since P ≥ 1 > 0, their product is non-negative by `mul_nonneg`.
uses
mul_nonneghave h1 : 0 ≤ P * (2 * (m : ℤ) - (r : ℤ) - (S : ℤ)) := mul_nonneg (by linarith) (by omega)
2 ≤ P * r.
Since 1 ≤ P and 2 ≤ r are both non-negative, multiplying them via `mul_le_mul` yields 2 = 1 * 2 ≤ P * r.
uses
mul_le_mulhave h2 : 2 ≤ P * (r : ℤ) := by calc (2 : ℤ) = 1 * 2 := by ring _ ≤ P * (r : ℤ) := mul_le_mul hP hrZ (by linarith) (by linarith)
0 ≤ (k - 1) * (P * r - 1).
From k ≥ 1 we have k - 1 ≥ 0, and from P * r ≥ 2 we have P * r - 1 ≥ 1 ≥ 0. The product of these two non-negative terms is non-negative by `mul_nonneg`.
uses
mul_nonneghave h3 : 0 ≤ ((k : ℤ) - 1) * (P * (r : ℤ) - 1) := mul_nonneg (by omega) (by linarith)
The desired inequality 2^(r - 2) * (S - k * r) + k ≤ 2^(r - 1) * (m - r) + 1 holds.
The difference (P * 2 * (m - r) + 1) - (P * (S - k * r) + k) expands algebraically to P * (2 * m - r - S) + (k - 1) * (P * r - 1). Since both terms have been shown to be non-negative, linear arithmetic closes the goal.
linarith
pow_succ- In any monoid, a^(n + 1) = a^n * a.
mul_comm- Multiplication is commutative: a * b = b * a.
one_le_pow₀- In an ordered monoid with zero, if 1 ≤ a, then 1 ≤ a^n for all natural numbers n.
mul_nonneg- The product of two non-negative elements is non-negative.
mul_le_mul- If a ≤ b and c ≤ d with 0 ≤ c and 0 ≤ b, then a * c ≤ b * d.
- In Lean, subtraction on natural numbers truncates at 0; the tactic `zify` casts the goal to the integers ℤ, which is sound because the hypotheses k * r ≤ S and r ≤ m guarantee the subtractions do not truncate.
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.
/-- Summation arithmetic bound for the block decomposition in Theorem 2.1. -/theorem one_layered_linear_bound_sum_le (m r k S : ℕ) (hr : 2 ≤ r) (hk : 1 ≤ k) (hm : r ≤ m) (hS : S ≤ 2 * m - r) (hkr : k * r ≤ S) : 2 ^ (r - 2) * (S - k * r) + k ≤ 2 ^ (r - 1) * (m - r) + 1 := by have hr1 : r - 1 = (r - 2) + 1 := by omega have hpow : 2 ^ (r - 1) = 2 ^ (r - 2) * 2 := by rw [hr1, pow_succ, mul_comm] rw [hpow] zify [hkr, hm] set P : ℤ := (2 : ℤ) ^ (r - 2) change P * (↑S - ↑k * ↑r) + ↑k ≤ P * 2 * (↑m - ↑r) + 1 have hP : 1 ≤ P := one_le_pow₀ (by decide) have hrZ : 2 ≤ (r : ℤ) := by omega have h1 : 0 ≤ P * (2 * (m : ℤ) - (r : ℤ) - (S : ℤ)) := mul_nonneg (by linarith) (by omega) have h2 : 2 ≤ P * (r : ℤ) := by calc (2 : ℤ) = 1 * 2 := by ring _ ≤ P * (r : ℤ) := mul_le_mul hP hrZ (by linarith) (by linarith) have h3 : 0 ≤ ((k : ℤ) - 1) * (P * (r : ℤ) - 1) := mul_nonneg (by omega) (by linarith) linarith