mdfrbf_compression_bound
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
- mixed_diamond_fan_ramsey_bound_all_singletons_fan_coloursCase b ≥ 2 with every singleton fan-coloured: if d ≥ j*a + (j-1)*b + 1 and the statement holds at (a, b-1) in dimension d-(j-1), then χ…
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 ≤ b
This follows immediately from the hypothesis that 2 ≤ b.
have hb1 : 1 ≤ b := by omega
(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.
uses
Nat.sub_add_cancel,Nat.mul_add,Nat.mul_onehave 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]
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.
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
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.
/-- 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