AFTD Auto-Formalizing Theoretical Domains

mdfrbf_compression_bound

theoremverified

Arithmetic side condition of the compression step: if j ≥ 2, a ≥ 1, b ≥ 2 and j*a + (j-1)*b + 1 ≤ d, then j*a + (j-1)*(b-1) + 1 ≤ d - (j-1).

Statement

theorem mdfrbf_compression_bound (j a b d : ℕ) (hj : 2 ≤ j) (ha : 1 ≤ a) (hb : 2 ≤ b)
    (hd : j * a + (j - 1) * b + 1 ≤ d) :
    j * a + (j - 1) * (b - 1) + 1 ≤ d - (j - 1)
Source
step towards mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours
Verified
18 Oct 2026
Axioms
Quot.soundpropext
Used by 1

The proof, explained

The proof expands the term (j - 1) * b into (j - 1) * (b - 1) + (j - 1) by writing b = (b - 1) + 1 and distributing. Substituting this identity into the given inequality j * a + (j - 1) * b + 1 ≤ d reveals that adding (j - 1) to the desired left-hand side gives at most d, from which the conclusion follows by linear arithmetic.

  1. 1 ≤ b

    This follows immediately from the hypothesis that 2 ≤ b.

    line 5

      have hb1 : 1 ≤ b := by omega
  2. (j - 1) * (b - 1) + (j - 1) = (j - 1) * b

    Because 1 ≤ b, we can express b as (b - 1) + 1 using Nat.sub_add_cancel. Distributing the factor (j - 1) over (b - 1) + 1 using Nat.mul_add and simplifying (j - 1) * 1 with Nat.mul_one yields the desired identity.

    lines 6–8

    uses Nat.sub_add_cancel, Nat.mul_add, Nat.mul_one

      have h1 : (j - 1) * (b - 1) + (j - 1) = (j - 1) * b := by
        conv_rhs => rw [show b = (b - 1) + 1 from (Nat.sub_add_cancel hb1).symm]
        rw [Nat.mul_add, Nat.mul_one]
  3. j * a + (j - 1) * (b - 1) + 1 ≤ d - (j - 1)

    Using the algebraic identity just established, the hypothesis j * a + (j - 1) * b + 1 ≤ d can be rewritten as (j * a + (j - 1) * (b - 1) + 1) + (j - 1) ≤ d. Subtracting (j - 1) from both sides yields the target inequality, which is completed by linear arithmetic.

    line 9

      omega
Nat.sub_add_cancel
For natural numbers m ≤ n, (n - m) + m = n.
Nat.mul_add
Multiplication distributes over addition: n * (m + k) = n * m + n * k.
Nat.mul_one
Multiplying any natural number by one gives the number itself: n * 1 = n.

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

/-- Arithmetic: the (a, b-1) bound at dimension d-(j-1) follows from the (a, b) bound at dimension d. -/theorem mdfrbf_compression_bound (j a b d : ℕ) (hj : 2 ≤ j) (ha : 1 ≤ a) (hb : 2 ≤ b)    (hd : j * a + (j - 1) * b + 1 ≤ d) :    j * a + (j - 1) * (b - 1) + 1 ≤ d - (j - 1) := by  have hb1 : 1 ≤ b := by omega  have h1 : (j - 1) * (b - 1) + (j - 1) = (j - 1) * b := by    conv_rhs => rw [show b = (b - 1) + 1 from (Nat.sub_add_cancel hb1).symm]    rw [Nat.mul_add, Nat.mul_one]  omega
See it in the graphDiscuss this resultChallenge it