AFTD Auto-Formalizing Theoretical Domains

maxcut_unweighted_minimal_deviation_cycle_exists

theoremverifiedoriginal

On the specified unweighted 71-vertex graph there is an infinite three-color strong-deviation sequence returning after 33 steps, and every step is inclusion-minimal: no proper subcoalition of its changing players has a profitable deviation from that step’s starting profile.

Statement

theorem maxcut_unweighted_minimal_deviation_cycle_exists :
    ∃ (d : DecidableRel maxcut_cycle71_graph.Adj) (f : ℕ → Fin 71 → Fin 3),
      f 33 = f 0 ∧ ∀ n,
        @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph d 3 (f n)
          (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1)) ∧
        ∀ S : Finset (Fin 71),
          S ⊂ (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) →
          ¬ ∃ τ : Fin 71 → Fin 3,
            @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph d 3 (f n) S τ
Related work
The explicit 71-vertex unweighted minimal-deviation cycle for the potential-function question in arXiv:1810.09278, Section 7; experiments 12443, 12444, 12450 and 12452.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • maxcut_cycle71_graphThe explicit 71-vertex finite simple graph with four core blocks of eight and three anchor blocks of thirteen, with edges determined by…
  • maxcut_cycle71_fieldThe number of anchor neighbors of each fixed color assigned to each core block in the regular 71-vertex construction.
  • maxcut_cycle71_return_stagesThe 33 profiles of the displayed 71-vertex cycle: the initial profile, the joint deviation, and the partial singleton restorations.
  • maxcut_cycle71_minimal_cycle_stepsEvery successive pair of the 33 profiles forms a strong deviation, and no proper subcoalition of its changing vertices has a profitable…
  • is_maxcut_strong_deviationA strong deviation from σ is a nonempty coalition S ⊆ V with a coloring τ agreeing with σ outside S such that u_v(τ) > u_v(σ) for every v…

Read back from the Lean

There exist a decidability instance d for adjacency in the 71-vertex graph maxcut_cycle71_graph and a sequence of 3-colorings (assignments of vertices to {0, 1, 2}) f : ℕ → Fin 71 → Fin 3 such that: 1. f 33 = f 0 (the coloring after 33 steps equals the initial coloring f 0), and 2. For every n : ℕ: (a) The transition from f n to f (n + 1) is a strong deviation by the set of deviating vertices $D_n = \{ v : \text{Fin } 71 \mid f (n + 1)(v) \neq f n(v) \}$. That is, $D_n$ is nonempty, f (n + 1) agrees with f n outside $D_n$, and every vertex $v \in D_n$ strictly increases its Max-Cut utility from f n to f (n + 1). (b) The deviating coalition $D_n$ is minimal: for every strict subset $S \subsetneq D_n$, there does not exist any 3-coloring $\tau : \text{Fin } 71 \to \text{Fin } 3$ such that $(f n, S, \tau)$ is a strong deviation (meaning $S$ is nonempty, $\tau$ agrees with f n outside $S$, and every vertex in $S$ strictly increases its Max-Cut utility from f n to $\tau$).

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 existence of an infinite minimal-deviation cycle is proved by wrapping a pre-constructed 33-step cycle of 3-colorings (maxcut_cycle71_return_stages) into an infinite sequence f(n) indexed by n % 33. Periodicity f 33 = f 0 holds definitionally because 33 % 33 = 0 % 33. Each transition f n → f (n + 1) is shown to correspond to moving from index i = n % 33 to i + 1 in Fin 33, matching the premise of the prerequisite theorem maxcut_cycle71_minimal_cycle_steps which guarantees inclusion-minimal strong deviation at every step.

  1. Adjacency in the 71-vertex graph is decidable.

    We construct d as a decision procedure for adjacency between any two vertices u, v : Fin 71. Unfolding the definitions of maxcut_cycle71_graph, the boundary function maxcut_cycle71_field, and SimpleGraph.fromRel reveals that adjacency is expressed as a finite boolean combination of inequalities and modulo arithmetic on natural numbers, which Lean's typeclass synthesis (infer_instance) decides constructively.

    lines 14–15

      let d : DecidableRel maxcut_cycle71_graph.Adj := by
        intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance
  2. The periodic coloring sequence is defined, reducing the existential claim to periodicity and per-step minimality.

    We define f(n) by evaluating the 33 pre-constructed coloring stages maxcut_cycle71_return_stages at index n % 33, whose validity as an element of Fin 33 is certified by Nat.mod_lt using 0 < 33 (checked by decide). Supplying d and f as witnesses for the existential quantifier leaves two subgoals: proving f 33 = f 0 and showing that every step f n → f (n + 1) is an inclusion-minimal strong deviation.

    lines 16–17

    uses Nat.mod_lt

      let f : ℕ → Fin 71 → Fin 3 := fun n => maxcut_cycle71_return_stages ⟨n % 33, Nat.mod_lt _ (by decide)⟩
      refine ⟨d, f, ?_, ?_⟩
  3. The sequence returns to its initial state after 33 steps: f 33 = f 0.

    Since 33 % 33 = 0 and 0 % 33 = 0, both f 33 and f 0 evaluate definitionally to maxcut_cycle71_return_stages 0, so the equality holds by reflexivity (rfl).

    line 18

      · rfl
  4. In Fin 33, the index for step n + 1 is the successor of the index for step n: ⟨(n + 1) % 33, _⟩ = ⟨n % 33, _⟩ + 1.

    Fixing n, by Fin.ext it suffices to check equality of their underlying natural numbers. By Fin.val_add, the value of ⟨n % 33, _⟩ + 1 in Fin 33 is (n % 33 + 1) % 33, which equals (n + 1) % 33 by Nat.add_mod, allowing the simplifier to close the goal.

    lines 19–23

    uses Fin.ext, Fin.val_add, Nat.add_mod, Nat.mod_lt

      · intro n
        have hn : (⟨(n + 1) % 33, Nat.mod_lt _ (by decide)⟩ : Fin 33) =
            (⟨n % 33, Nat.mod_lt _ (by decide)⟩ : Fin 33) + 1 := by
          apply Fin.ext
          simp [Fin.val_add, Nat.add_mod]
  5. Every transition f n → f (n + 1) is an inclusion-minimal strong deviation.

    Applying the pre-proved theorem maxcut_cycle71_minimal_cycle_steps at index i = ⟨n % 33, _⟩ establishes that transitioning from stage i to stage i + 1 is an inclusion-minimal strong deviation. Rewriting with the definition of f and the equality hn (which equates stage i + 1 with f (n + 1)) completes the proof.

    line 24

    uses maxcut_cycle71_minimal_cycle_steps, Nat.mod_lt

        simpa [f, hn] using maxcut_cycle71_minimal_cycle_steps ⟨n % 33, Nat.mod_lt _ (by decide)⟩
Nat.mod_lt
For natural numbers x and y with y > 0, the remainder x % y is strictly less than y.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Fin.val_add
The natural number value of a sum a + b in Fin n equals (val a + val b) % n.
Nat.add_mod
For natural numbers a, b, and n, (a + b) % n = (a % n + b % n) % n.
maxcut_cycle71_minimal_cycle_steps
For each stage index i : Fin 33, transitioning from stage i to stage i + 1 is a strong deviation by all vertices whose colors change, and no proper subcoalition of those vertices can deviate profitably.

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

set_option maxRecDepth 200000set_option maxHeartbeats 0set_option synthInstance.maxSize 200000theorem maxcut_unweighted_minimal_deviation_cycle_exists :    ∃ (d : DecidableRel maxcut_cycle71_graph.Adj) (f : ℕ → Fin 71 → Fin 3),      f 33 = f 0 ∧ ∀ n,        @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph d 3 (f n)          (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1)) ∧        ∀ S : Finset (Fin 71),          S ⊂ (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) →          ¬ ∃ τ : Fin 71 → Fin 3,            @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph d 3 (f n) S τ := by  let d : DecidableRel maxcut_cycle71_graph.Adj := by    intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance  let f : ℕ → Fin 71 → Fin 3 := fun n => maxcut_cycle71_return_stages ⟨n % 33, Nat.mod_lt _ (by decide)⟩  refine ⟨d, f, ?_, ?_⟩  · rfl  · intro n    have hn : (⟨(n + 1) % 33, Nat.mod_lt _ (by decide)⟩ : Fin 33) =        (⟨n % 33, Nat.mod_lt _ (by decide)⟩ : Fin 33) + 1 := by      apply Fin.ext      simp [Fin.val_add, Nat.add_mod]    simpa [f, hn] using maxcut_cycle71_minimal_cycle_steps ⟨n % 33, Nat.mod_lt _ (by decide)⟩
See it in the graphDiscuss this resultChallenge it