AFTD Auto-Formalizing Theoretical Domains

cycle_gap_merge_pair

theoremverified

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 i of a gap list g representing 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 : ℝ) +…

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.

  1. `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.

    line 2

    uses cycle_gap_merge, nonclairvoyant_scheduling_ratio_bound_of_large_index

    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)
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

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

/-- 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)
See it in the graphDiscuss this resultChallenge it