sorted_seven_robust_peeling_capacity
Seven decreasing nonnegative counts satisfying the five displayed robust-peeling alternatives have sum at least twenty.
Statement
theorem sorted_seven_robust_peeling_capacity
(d : Fin 7 → ℕ)
(hs : ∀ i j, i ≤ j → d j ≤ d i)
(h0 : 6 ≤ d 0 ∨ 5 ≤ d 2)
(h1 : 5 ≤ d 1 ∨ 4 ≤ d 3)
(h2 : 4 ≤ d 2 ∨ 3 ≤ d 4)
(h3 : 3 ≤ d 3 ∨ 2 ≤ d 5)
(h4 : 2 ≤ d 4 ∨ 1 ≤ d 6) :
20 ≤ ∑ i : Fin 7, d i- Source
- Finite arithmetic for the robust peeling step in the OP-110 campaign; experiment 12598.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- digraph_seven_out_robust_two_cycle_free_cut_ge_twentyA set of at least seven vertices in a digraph of minimum outdegree seven, containing no two disjoint directed cycles, has at least twenty…
The proof, explained
The proof unrolls the sum of the seven values into an explicit addition and reduces the goal to linear integer arithmetic. The sequence's monotonicity is instantiated on each pair of adjacent indices to supply local ordering relations. Finally, an exhaustive case split on the five disjunctive hypotheses produces 32 cases, every one of which is settled by Presburger arithmetic (`omega`).
The adjacent elements of $d$ are non-increasing: $d(1) \le d(0)$, $d(2) \le d(1)$, $d(3) \le d(2)$, $d(4) \le d(3)$, $d(5) \le d(4)$, and $d(6) \le d(5)$.
Specialise the general monotonicity hypothesis `hs` to each adjacent pair of indices $(0, 1), (1, 2), \dots, (5, 6)$, discharging the numeric index inequalities $0 \le 1, \dots, 5 \le 6$ by direct evaluation (`decide`).
have hs01 := hs 0 1 (by decide) have hs12 := hs 1 2 (by decide) have hs23 := hs 2 3 (by decide) have hs34 := hs 3 4 (by decide) have hs45 := hs 4 5 (by decide) have hs56 := hs 5 6 (by decide)
The sum $\sum_{i : \mathrm{Fin}\,7} d(i)$ is expanded into the explicit expression $d(0) + (d(1) + (d(2) + (d(3) + (d(4) + (d(5) + (d(6) + 0))))))$.
Peel off each term of the finite sum one by one using `Fin.sum_univ_succ` until `Fin.sum_univ_zero` eliminates the empty sum, then syntactically simplify the index representations to standard numerals.
uses
Fin.sum_univ_succ,Fin.sum_univ_zerosimp only [Fin.sum_univ_succ, Fin.sum_univ_zero] change 20 ≤ d 0 + (d 1 + (d 2 + (d 3 + (d 4 + (d 5 + (d 6 + 0))))))
The sum is at least 20 under all 32 combinations of the disjunctive lower bounds. automation
Perform an exhaustive case analysis by splitting each of the five disjunctions $h_0, \dots, h_4$ into its two alternatives, yielding $2^5 = 32$ subcases. In every subcase, Presburger arithmetic (`omega`) deduces that the sum is at least 20 from the chosen lower bounds together with the adjacent monotonicity inequalities.
rcases h0 with h0 | h0 <;> rcases h1 with h1 | h1 <;> rcases h2 with h2 | h2 <;> rcases h3 with h3 | h3 <;> rcases h4 with h4 | h4 <;> omega
Fin.sum_univ_succ- A sum of a function over `Fin (n + 1)` equals the value at 0 plus the sum of the remaining terms over `Fin n`.
Fin.sum_univ_zero- A sum of a function over the empty type `Fin 0` equals 0.
- The 32 linear arithmetic subproblems resulting from the case split on the five disjunctions are solved entirely by the `omega` decision procedure.
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.
theorem sorted_seven_robust_peeling_capacity (d : Fin 7 → ℕ) (hs : ∀ i j, i ≤ j → d j ≤ d i) (h0 : 6 ≤ d 0 ∨ 5 ≤ d 2) (h1 : 5 ≤ d 1 ∨ 4 ≤ d 3) (h2 : 4 ≤ d 2 ∨ 3 ≤ d 4) (h3 : 3 ≤ d 3 ∨ 2 ≤ d 5) (h4 : 2 ≤ d 4 ∨ 1 ≤ d 6) : 20 ≤ ∑ i : Fin 7, d i := by have hs01 := hs 0 1 (by decide) have hs12 := hs 1 2 (by decide) have hs23 := hs 2 3 (by decide) have hs34 := hs 3 4 (by decide) have hs45 := hs 4 5 (by decide) have hs56 := hs 5 6 (by decide) simp only [Fin.sum_univ_succ, Fin.sum_univ_zero] change 20 ≤ d 0 + (d 1 + (d 2 + (d 3 + (d 4 + (d 5 + (d 6 + 0)))))) rcases h0 with h0 | h0 <;> rcases h1 with h1 | h1 <;> rcases h2 with h2 | h2 <;> rcases h3 with h3 | h3 <;> rcases h4 with h4 | h4 <;> omega