AFTD Auto-Formalizing Theoretical Domains

not_cycle_labeling_complete_range_eight

theoremverifiedformalization

The 8-cycle labelled 1, …, 8 in order is not complete (17 and 19 are not arc sums).

Statement

theorem not_cycle_labeling_complete_range_eight :
    ¬ cycle_labeling_complete 8 (List.range' 1 8)
Formalizes
arXiv:2610.08889 (Consecutive Cycle Sums), Theorem 1, case n = 8 (Sec. 5 notes 17 and 19 are missing).
Verified
09 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 proof proceeds by finite exhaustive computation. Unfolding the definition of a complete cycle labeling on the list $(1, \\dots, 8)$ yields a decidable statement about whether all integers from 1 to 36 can be formed as sums of cyclic intervals. Lean's `decide` tactic checks this property directly by evaluation and confirms that it does not hold.

  1. The sequential cyclic labeling (1, 2, 3, 4, 5, 6, 7, 8) is not complete. automation

    Expanding the definition of `cycle_labeling_complete` expresses completeness as a statement with bounded quantifiers over finite domains: every target sum $k \\in \\{1, \\dots, 36\\}$ must arise as the sum of some contiguous arc of length $1 \\le l \\le 8$ in the cycle $(1, \\dots, 8)$. Because all domains are finite, this property is decidable, and Lean's decision procedure `decide` checks it exhaustively by computation, establishing that the condition fails (in particular, the sums 17 and 19 cannot be formed).

    line 3

      unfold cycle_labeling_complete; decide

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 not_cycle_labeling_complete_range_eight :    ¬ cycle_labeling_complete 8 (List.range' 1 8) := by  unfold cycle_labeling_complete; decide
See it in the graphDiscuss this resultChallenge it