cycle_gap_merge_pair
Merging two unit gaps at index 0 on a cycle yields a single gap of length 2.
Statement
theorem cycle_gap_merge_pair : cycle_gap_merge [1, 1] 0 = [2]- Source
- arXiv:2610.15776, Theorem 2
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- cycle_gap_mergeMerges the adjacent gaps at cyclic index
iof a gap listgrepresenting distances between free facilities on a cycle, combining gaps… - nonclairvoyant_scheduling_ratio_bound_of_large_indexFor any natural number n with 2 ≤ n and any natural number s such that (n : ℝ) + 3 < 4 * (s : ℝ), the quantity ((n : ℝ) + 1) * ((n : ℝ) +…
- cycle_gap_mergeMerges the adjacent gaps at cyclic index
Read back from the Lean
Applying cycle_gap_merge to the list [1, 1] (of natural numbers) and index 0 evaluates to [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 states that merging two unit gaps at index 0 on a cycle produces a single gap of length 2. The proof unfolds the definition of `cycle_gap_merge` on the concrete list `[1, 1]` at index 0. The resulting list and arithmetic operations evaluate directly to `[2]`, which the simplifier closes by computation.
`cycle_gap_merge [1, 1] 0 = [2]` automation
Unfolding the definition of `cycle_gap_merge` on the two-element list `[1, 1]` at index `0` yields an expression with length 2 and index modulo length equal to 0. In this branch, the first and last elements (both 1) are summed to 2, and the remaining elements (`[1, 1].tail.dropLast`) form the empty list `[]`. The resulting concatenation `[] ++ [2]` simplifies by direct computation to `[2]`. The simplifier evaluates these ground list and arithmetic operations and closes the goal.
uses
cycle_gap_merge,nonclairvoyant_scheduling_ratio_bound_of_large_indextheorem cycle_gap_merge_pair : cycle_gap_merge [1, 1] 0 = [2] := by first | exact nonclairvoyant_scheduling_ratio_bound_of_large_index | (apply nonclairvoyant_scheduling_ratio_bound_of_large_index <;> assumption) | (apply nonclairvoyant_scheduling_ratio_bound_of_large_index <;> simp_all) | simpa using nonclairvoyant_scheduling_ratio_bound_of_large_index | (simp only [cycle_gap_merge] at *; first | exact nonclairvoyant_scheduling_ratio_bound_of_large_index | (apply nonclairvoyant_scheduling_ratio_bound_of_large_index <;> assumption) | (apply nonclairvoyant_scheduling_ratio_bound_of_large_index <;> simp_all) | simpa using nonclairvoyant_scheduling_ratio_bound_of_large_index)
cycle_gap_merge- the definition of merging adjacent gaps in a cyclic list of gap lengths at a given index
nonclairvoyant_scheduling_ratio_bound_of_large_index- an upper bound of 3/2 on the competitive ratio of a non-clairvoyant scheduler for large job indices; syntactically present in the proof script but unused
- The proof script is produced by an automated tactic search (`first | ...`) that tries several tactic combinations containing the unrelated lemma `nonclairvoyant_scheduling_ratio_bound_of_large_index`. That lemma is never used; the goal is solved entirely by unfolding `cycle_gap_merge` and computing the list and arithmetic operations via `simpa`.
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.
/-- Merging two unit gaps at index 0 produces a single gap of length 2. -/theorem cycle_gap_merge_pair : cycle_gap_merge [1, 1] 0 = [2] := by first | exact nonclairvoyant_scheduling_ratio_bound_of_large_index | (apply nonclairvoyant_scheduling_ratio_bound_of_large_index <;> assumption) | (apply nonclairvoyant_scheduling_ratio_bound_of_large_index <;> simp_all) | simpa using nonclairvoyant_scheduling_ratio_bound_of_large_index | (simp only [cycle_gap_merge] at *; first | exact nonclairvoyant_scheduling_ratio_bound_of_large_index | (apply nonclairvoyant_scheduling_ratio_bound_of_large_index <;> assumption) | (apply nonclairvoyant_scheduling_ratio_bound_of_large_index <;> simp_all) | simpa using nonclairvoyant_scheduling_ratio_bound_of_large_index)