AFTD Auto-Formalizing Theoretical Domains

one_layered_linear_bound_sum_le

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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.

  1. 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.

    lines 5–8

    uses pow_succ, mul_comm

      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]
  2. 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.

    lines 9–11

      zify [hkr, hm]
      set P : ℤ := (2 : ℤ) ^ (r - 2)
      change P * (↑S - ↑k * ↑r) + ↑k ≤ P * 2 * (↑m - ↑r) + 1
  3. 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 ℕ.

    lines 12–13

    uses one_le_pow₀

      have hP : 1 ≤ P := one_le_pow₀ (by decide)
      have hrZ : 2 ≤ (r : ℤ) := by omega
  4. 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`.

    line 14

    uses mul_nonneg

      have h1 : 0 ≤ P * (2 * (m : ℤ) - (r : ℤ) - (S : ℤ)) := mul_nonneg (by linarith) (by omega)
  5. 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.

    lines 15–17

    uses mul_le_mul

      have h2 : 2 ≤ P * (r : ℤ) := by
        calc (2 : ℤ) = 1 * 2 := by ring
        _ ≤ P * (r : ℤ) := mul_le_mul hP hrZ (by linarith) (by linarith)
  6. 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`.

    line 18

    uses mul_nonneg

      have h3 : 0 ≤ ((k : ℤ) - 1) * (P * (r : ℤ) - 1) := mul_nonneg (by omega) (by linarith)
  7. 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.

    line 19

      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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it