AFTD Auto-Formalizing Theoretical Domains

exists_cycle_labeling_complete_ge_eight

theoremverifiedoriginal

There is an n ≥ 8 and a placement of 1, …, n around the n-cycle that is complete: for n = 8, the order 1, 2, 3, 4, 5, 6, 8, 7.

Statement

theorem exists_cycle_labeling_complete_ge_eight :
    ∃ n ≥ 8, ∃ L : List ℕ, cycle_labeling_complete n L
Related work
List entry OP-121, a question proposed here from arXiv:2610.08889 (Consecutive Cycle Sums), Theorem 1: Theorem 1 shows the increasing order is incomplete for n ≥ 8; the paper does not consider other orders. Answered here by the explicit witness 1, 2, 3, 4, 5, 6, 8, 7 for n = 8.
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • cycle_labeling_completePlacing the labels L (a permutation of 1, …, n) in order around an n-cycle gives a complete cycle: every k ∈ {1, …, n(n+1)/2} is the sum…

The proof, explained

The theorem is proved constructively by providing explicit witnesses: n = 8 and the cyclic arrangement L = [1, 2, 3, 4, 5, 6, 8, 7]. The inequality 8 ≥ 8 is satisfied by reflexivity (le_rfl). Completeness of the labeling is verified by unfolding its definition and using the decide tactic to exhaustively compute that L is a permutation of 1, …, 8 and that every sum from 1 to 36 is attained by a contiguous cyclic subsegment.

  1. There exists an integer n ≥ 8 and a cycle labeling L such that cycle_labeling_complete n L holds, witnessed by n = 8 and L = [1, 2, 3, 4, 5, 6, 8, 7]. automation

    We instantiate the existential quantifiers with n = 8 and the permutation L = [1, 2, 3, 4, 5, 6, 8, 7]. The condition 8 ≥ 8 holds by reflexivity (le_rfl). To verify that L is a complete cycle labeling, we unfold the definition cycle_labeling_complete, which requires L to be a permutation of {1, …, 8} and requires every integer k ∈ {1, …, 36} (where 36 = 8 · 9 / 2) to be the sum of a contiguous cyclic subsegment of L. Because both conditions are finite and decidable, the `decide` tactic checks them by exhaustive computation.

    line 3

    uses le_rfl

      ⟨8, le_rfl, [1, 2, 3, 4, 5, 6, 8, 7], by unfold cycle_labeling_complete; decide⟩
le_rfl
Reflexivity of the ordering: for every element a in a preorder, a ≤ a.

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

theorem exists_cycle_labeling_complete_ge_eight :    ∃ n ≥ 8, ∃ L : List ℕ, cycle_labeling_complete n L :=  ⟨8, le_rfl, [1, 2, 3, 4, 5, 6, 8, 7], by unfold cycle_labeling_complete; decide⟩
See it in the graphDiscuss this resultChallenge it