low_hole_reduction_overtake
Let m, n be natural numbers and let z, z_RL, z_2, z_2A, H, d be integers. If z_RL ≤ z_2, z_2 ≤ z_2A, 0 ≤ H, 0 ≤ d, 2 * (z_2A - z_RL) = recursive_line_hole_budget m n z z_RL - H - d, (d = 0 → z_2A ≤ z_2), and recursive_line_hole_budget m n z z_RL ≤ 2, then z_2A = z_2.
Statement
theorem low_hole_reduction_overtake
(m n : ℕ) (z z_RL z_2 z_2A H d : ℤ)
(hle : z_RL ≤ z_2)
(h_overtake : z_2 ≤ z_2A)
(hH : 0 ≤ H)
(hd : 0 ≤ d)
(h_budget : 2 * (z_2A - z_RL) = recursive_line_hole_budget m n z z_RL - H - d)
(h_limited : d = 0 → z_2A ≤ z_2)
(h_low : recursive_line_hole_budget m n z z_RL ≤ 2) :
z_2A = z_2- Source
- scout/2610-22875-overtake-and-the-recursive-line-equality-for-second-order-z.md:549
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- recursive_line_hole_budgetThe recursive-line hole budget recursive_line_hole_budget m n z z_RL for natural numbers m, n and integers z, z_RL is defined as (m : ℤ) *…
- low_hole_two_mul_sub_ge_twoFor integers z_RL, z_2, and z_2A, if z_RL ≤ z_2 and z_2 < z_2A, then 2 ≤ 2 * (z_2A - z_RL).
- low_hole_reduction_forces_zeroFor integers L, h, H, and d, if 0 ≤ H, 0 ≤ d, L = h - H - d, 2 ≤ L, and h ≤ 2, then h = 2 ∧ H = 0 ∧ d = 0.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- low_hole_reduction_ruling_out_overtakeLet m, n be natural numbers and let z, z_RL, z_2, z_2A be integers such that z_RL ≤ z_2 and z_2 ≤ z_2A. Suppose there exist integers H and…
Read back from the Lean
For all natural numbers $m$ and $n$, and all integers $z$, $z_{RL}$, $z_2$, $z_{2A}$, $H$, and $d$, if: 1. $z_{RL} \le z_2$, 2. $z_2 \le z_{2A}$, 3. $0 \le H$, 4. $0 \le d$, 5. $2(z_{2A} - z_{RL}) = \text{recursive\_line\_hole\_budget}(m, n, z, z_{RL}) - H - d$, 6. $d = 0 \implies z_{2A} \le z_2$, and 7. $\text{recursive\_line\_hole\_budget}(m, n, z, z_{RL}) \le 2$, then $z_{2A} = z_2$.
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
The theorem is proved by contradiction. If z_2A ≠ z_2, then z_2 < z_2A, which together with z_RL ≤ z_2 forces 2 * (z_2A - z_RL) ≥ 2. Because the recursive line hole budget is at most 2 and equals 2 * (z_2A - z_RL) + H + d with H, d ≥ 0, the deficit d must equal 0. By hypothesis, d = 0 implies z_2A ≤ z_2, which contradicts z_2 < z_2A.
z_2 < z_2A
Assume for contradiction that z_2A ≠ z_2. Since z_2 ≤ z_2A by assumption, this inequality must be strict, giving z_2 < z_2A.
uses
lt_of_le_of_ne,Ne.symmby_contra hne have hgt : z_2 < z_2A := lt_of_le_of_ne h_overtake (Ne.symm hne)
2 ≤ 2 * (z_2A - z_RL)
Since z_RL ≤ z_2 and z_2 < z_2A for integers, the difference z_2A - z_RL is at least 1, so twice this difference is at least 2.
uses
low_hole_two_mul_sub_ge_twohave h2 : 2 ≤ 2 * (z_2A - z_RL) := low_hole_two_mul_sub_ge_two z_RL z_2 z_2A hle hgtd = 0
The budget equation expresses 2 * (z_2A - z_RL) as recursive_line_hole_budget m n z z_RL - H - d. With H ≥ 0, d ≥ 0, 2 ≤ 2 * (z_2A - z_RL), and the budget bounded by 2, low_hole_reduction_forces_zero forces the budget to be 2, H to be 0, and d to be 0.
uses
low_hole_reduction_forces_zerohave hzero := low_hole_reduction_forces_zero (2 * (z_2A - z_RL)) (recursive_line_hole_budget m n z z_RL) H d hH hd h_budget h2 h_low have hd0 : d = 0 := hzero.2.2
A contradiction is reached, proving z_2A = z_2
Because d = 0, the hypothesis h_limited yields z_2A ≤ z_2. Linear arithmetic closes the goal by showing this contradicts z_2 < z_2A.
have hle' : z_2A ≤ z_2 := h_limited hd0 linarith
lt_of_le_of_ne- In a partial order, if a ≤ b and a ≠ b, then a < b.
Ne.symm- Symmetry of inequality: if a ≠ b, then b ≠ a.
low_hole_two_mul_sub_ge_two- For integers, if z_RL ≤ z_2 and z_2 < z_2A, then 2 ≤ 2 * (z_2A - z_RL).
low_hole_reduction_forces_zero- If integers satisfy L = h - H - d with 0 ≤ H, 0 ≤ d, 2 ≤ L, and h ≤ 2, then h = 2, H = 0, and d = 0.
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.
/-- Low-hole reduction ruling out overtake for given hole count and deficit. -/theorem low_hole_reduction_overtake (m n : ℕ) (z z_RL z_2 z_2A H d : ℤ) (hle : z_RL ≤ z_2) (h_overtake : z_2 ≤ z_2A) (hH : 0 ≤ H) (hd : 0 ≤ d) (h_budget : 2 * (z_2A - z_RL) = recursive_line_hole_budget m n z z_RL - H - d) (h_limited : d = 0 → z_2A ≤ z_2) (h_low : recursive_line_hole_budget m n z z_RL ≤ 2) : z_2A = z_2 := by by_contra hne have hgt : z_2 < z_2A := lt_of_le_of_ne h_overtake (Ne.symm hne) have h2 : 2 ≤ 2 * (z_2A - z_RL) := low_hole_two_mul_sub_ge_two z_RL z_2 z_2A hle hgt have hzero := low_hole_reduction_forces_zero (2 * (z_2A - z_RL)) (recursive_line_hole_budget m n z z_RL) H d hH hd h_budget h2 h_low have hd0 : d = 0 := hzero.2.2 have hle' : z_2A ≤ z_2 := h_limited hd0 linarith