AFTD Auto-Formalizing Theoretical Domains

not_cycle_labeling_complete_range_six

theoremverifiedformalization

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

Statement

theorem not_cycle_labeling_complete_range_six :
    ¬ cycle_labeling_complete 6 (List.range' 1 6)
Formalizes
arXiv:2610.08889 (Consecutive Cycle Sums), Sec. 1 (the 6-cycle is incomplete).
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

A circular labeling of length $n$ is complete if every integer from $1$ to $n(n+1)/2$ is achieved as the sum of some contiguous circular arc. For $n = 6$ and the sequential labeling $(1, 2, 3, 4, 5, 6)$, completeness requires all integers from $1$ to $21$ to appear as arc sums. Unfolding the definition yields a bounded, decidable proposition over finite ranges, which Lean disproves by exhaustive computation.

  1. The standard cyclic arrangement $(1, 2, 3, 4, 5, 6)$ is not a complete cycle labeling. automation

    Unfolding the definition of `cycle_labeling_complete` reduces the goal to checking whether every target sum $k \in \{1, \dots, 21\}$ can be realized as the sum of a contiguous circular arc of length between $1$ and $6$. Because all quantifiers and indices range over finite sets, this assertion is purely computational. The `decide` tactic checks the bounded search space by finite evaluation and confirms the property is false (neither 8 nor 13 can be obtained as an arc sum).

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