AFTD Auto-Formalizing Theoretical Domains

maxcut_cycle71_minimal_cycle_steps

theoremverified

Every successive pair of the 33 profiles forms a strong deviation, and no proper subcoalition of its changing vertices has a profitable deviation.

Statement

theorem maxcut_cycle71_minimal_cycle_steps : ∀ i : Fin 33,
    @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph
      (by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3
      (maxcut_cycle71_return_stages i)
      (Finset.univ.filter fun v : Fin 71 => maxcut_cycle71_return_stages (i + 1) v ≠ maxcut_cycle71_return_stages i v)
      (maxcut_cycle71_return_stages (i + 1)) ∧
    ∀ S : Finset (Fin 71),
      S ⊂ (Finset.univ.filter fun v : Fin 71 => maxcut_cycle71_return_stages (i + 1) v ≠ maxcut_cycle71_return_stages i v) →
      ¬ ∃ τ : Fin 71 → Fin 3, @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph
        (by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3
        (maxcut_cycle71_return_stages i) S τ
Source
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 10
  • 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_coloringFive displayed three-color profiles on the regular 71-vertex construction, with anchor colors fixed and four core blocks recolored in…
  • maxcut_cycle71_first_deviation_minimalThe 32 core vertices have a profitable deviation from the first displayed profile to the second, and no proper subcoalition can profitably…
  • 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_return_stepsEvery one of the 32 successive restoration moves, including the wraparound, is a profitable deviation by the displayed single vertex and…
  • 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…
  • maxcut_cycle71_return_rankThe order in which each core vertex is restored during the displayed 71-vertex cycle.
  • maxcut_cycle71_return_vertexThe core vertex restored at each of the 32 singleton stages.
  • maxcut_utilityIn the unweighted Max-k-Cut game on a finite simple graph G, a coloring σ : V → [k] gives player v the utility u_v(σ) = |{w ∈ N(v) : σ(w)…
Used by 1

The proof, explained

The proof considers each profile index i ∈ Fin 33 along the 33-stage cycle, splitting into cases based on whether i = 0. For i = 0, the stage transition coincides with the initial deviation on the first 32 vertices, whose validity and minimality follow directly from maxcut_cycle71_first_deviation_minimal. For i ≥ 1, the step is re-indexed by j = i - 1 ∈ Fin 32, where maxcut_cycle71_return_steps establishes that exactly one vertex changes color in a strong deviation; minimality then holds vacuously because any proper subcoalition of a singleton set is empty, which cannot form a valid deviation.

  1. Adjacency in maxcut_cycle71_graph is decidable for the first deviation condition. automation

    To satisfy the decidability requirement for graph adjacency in is_maxcut_strong_deviation within the theorem statement, we introduce vertices u and v, unfold the definitions of maxcut_cycle71_graph, maxcut_cycle71_field, and SimpleGraph.fromRel, and synthesize the decidability instance via typeclass inference.

    line 7

          (by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3
  2. Adjacency in maxcut_cycle71_graph is decidable for the minimality condition. automation

    Similarly, for the second occurrence of is_maxcut_strong_deviation in the theorem statement, graph adjacency decidability is provided by the same unfolding and typeclass resolution.

    line 14

            (by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3
  3. Introduce the stage index i and split into cases depending on whether i = 0 or i ≠ 0.

    We introduce the profile index i ∈ Fin 33 and consider whether its numerical value is 0. If it is, Fin.ext proves i = 0, and we substitute 0 for i.

    lines 16–19

    uses Fin.ext

      intro i
      by_cases hi : i.val = 0
      · have hi0 : i = 0 := Fin.ext (by simpa using hi)
        subst i
  4. For i = 0, the transition is a minimal strong deviation by reduction to the first deviation lemma. automation

    At stage 0, return stages 0 and 1 reduce by definition to colorings 0 and 1, respectively. Kernel evaluation (decide +kernel) verifies that the set of vertices whose colors differ between coloring 0 and coloring 1 is precisely the set of vertices with index less than 32. Rewriting with these equalities and zero_add, the goal matches maxcut_cycle71_first_deviation_minimal, which asserts that this transition is a strong deviation and has no profitable proper subcoalition.

    lines 20–30

    uses zero_add, maxcut_cycle71_first_deviation_minimal

        have h0 : maxcut_cycle71_return_stages 0 = maxcut_cycle71_coloring 0 := by
          funext v
          simp [maxcut_cycle71_return_stages]
        have h1 : maxcut_cycle71_return_stages 1 = maxcut_cycle71_coloring 1 := by
          funext v
          simp [maxcut_cycle71_return_stages]
        have hc : (Finset.univ.filter fun v : Fin 71 =>
            maxcut_cycle71_coloring 1 v ≠ maxcut_cycle71_coloring 0 v) =
            (Finset.univ.filter fun v : Fin 71 => v.val < 32) := by
          decide +kernel
        simpa only [zero_add, h0, h1, hc] using maxcut_cycle71_first_deviation_minimal
  5. When i ≠ 0, express i as j + 1 and i + 1 as (j + 2) % 33 for an index j : Fin 32. automation

    Since i ≠ 0, its value satisfies 1 ≤ i.val < 33, so j = ⟨i.val - 1, ...⟩ is a well-defined element of Fin 32. Using Fin.ext and linear arithmetic (omega), we show that j + 1 = i in Fin 33, and that (j + 2) % 33 = i + 1 in Fin 33, with the modular bound provided by Nat.mod_lt.

    lines 31–41

    uses Fin.ext, Nat.mod_lt

      · let j : Fin 32 := ⟨i.val - 1, by have := i.isLt; omega⟩
        have hfirst : (⟨j.val + 1, by have := j.isLt; omega⟩ : Fin 33) = i := by
          apply Fin.ext
          dsimp [j]
          omega
        have hnext : (⟨(j.val + 2) % 33, Nat.mod_lt _ (by decide)⟩ : Fin 33) = i + 1 := by
          apply Fin.ext
          change (j.val + 2) % 33 = (i.val + 1) % 33
          congr 1
          dsimp [j]
          omega
  6. For i ≠ 0, the transition from stage i to stage i + 1 is a strong deviation whose changing set is a singleton vertex.

    Applying maxcut_cycle71_return_steps to j and rewriting with the index identities, we obtain that transitioning from stage i to stage i + 1 is a strong deviation and that the set of changing vertices is the singleton {maxcut_cycle71_return_vertex j}. We record this strong deviation to establish the first conjunct.

    lines 42–47

    uses maxcut_cycle71_return_steps

        have hs := maxcut_cycle71_return_steps j
        dsimp only at hs
        rw [hfirst, hnext] at hs
        obtain ⟨hd, hc⟩ := hs
        rw [hc]
        refine ⟨hd, ?_⟩
  7. No proper subcoalition of changing vertices has a profitable deviation.

    Suppose for contradiction that some proper subcoalition S ⊂ {maxcut_cycle71_return_vertex j} has a profitable deviation τ. Because S is a strict subset of a singleton, Finset.eq_empty_of_ssubset_singleton implies S = ∅. But a strong deviation requires the coalition to be nonempty, contradicting Finset.not_nonempty_empty.

    lines 48–52

    uses Finset.eq_empty_of_ssubset_singleton, Finset.not_nonempty_empty

        intro S hS hdev
        have hsempty : S = ∅ := Finset.eq_empty_of_ssubset_singleton hS
        obtain ⟨τ, hτ⟩ := hdev
        rw [hsempty] at hτ
        exact Finset.not_nonempty_empty hτ.1
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural values are equal.
zero_add
Adding zero to any element on the left leaves it unchanged: 0 + a = a.
maxcut_cycle71_first_deviation_minimal
The transition from coloring 0 to coloring 1 on the first 32 vertices is a strong deviation in maxcut_cycle71_graph, and no proper subcoalition has a profitable deviation from coloring 0.
Nat.mod_lt
For any natural numbers x and y with y > 0, the remainder x % y is strictly less than y.
maxcut_cycle71_return_steps
For every index i : Fin 32, the step from return stage i + 1 to (i + 2) % 33 is a strong deviation changing only the single vertex maxcut_cycle71_return_vertex i.
Finset.eq_empty_of_ssubset_singleton
If a finite set is a strict subset of a singleton set {x}, it must be the empty set ∅.
Finset.not_nonempty_empty
The empty set ∅ is not nonempty.

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_cycle71_minimal_cycle_steps : ∀ i : Fin 33,    @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph      (by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3      (maxcut_cycle71_return_stages i)      (Finset.univ.filter fun v : Fin 71 => maxcut_cycle71_return_stages (i + 1) v ≠ maxcut_cycle71_return_stages i v)      (maxcut_cycle71_return_stages (i + 1)) ∧    ∀ S : Finset (Fin 71),      S ⊂ (Finset.univ.filter fun v : Fin 71 => maxcut_cycle71_return_stages (i + 1) v ≠ maxcut_cycle71_return_stages i v) →      ¬ ∃ τ : Fin 71 → Fin 3, @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph        (by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3        (maxcut_cycle71_return_stages i) S τ := by  intro i  by_cases hi : i.val = 0  · have hi0 : i = 0 := Fin.ext (by simpa using hi)    subst i    have h0 : maxcut_cycle71_return_stages 0 = maxcut_cycle71_coloring 0 := by      funext v      simp [maxcut_cycle71_return_stages]    have h1 : maxcut_cycle71_return_stages 1 = maxcut_cycle71_coloring 1 := by      funext v      simp [maxcut_cycle71_return_stages]    have hc : (Finset.univ.filter fun v : Fin 71 =>        maxcut_cycle71_coloring 1 v ≠ maxcut_cycle71_coloring 0 v) =        (Finset.univ.filter fun v : Fin 71 => v.val < 32) := by      decide +kernel    simpa only [zero_add, h0, h1, hc] using maxcut_cycle71_first_deviation_minimal  · let j : Fin 32 := ⟨i.val - 1, by have := i.isLt; omega⟩    have hfirst : (⟨j.val + 1, by have := j.isLt; omega⟩ : Fin 33) = i := by      apply Fin.ext      dsimp [j]      omega    have hnext : (⟨(j.val + 2) % 33, Nat.mod_lt _ (by decide)⟩ : Fin 33) = i + 1 := by      apply Fin.ext      change (j.val + 2) % 33 = (i.val + 1) % 33      congr 1      dsimp [j]      omega    have hs := maxcut_cycle71_return_steps j    dsimp only at hs    rw [hfirst, hnext] at hs    obtain ⟨hd, hc⟩ := hs    rw [hc]    refine ⟨hd, ?_⟩    intro S hS hdev    have hsempty : S = ∅ := Finset.eq_empty_of_ssubset_singleton hS    obtain ⟨τ, hτ⟩ := hdev    rw [hsempty] at hτ    exact Finset.not_nonempty_empty hτ.1
See it in the graphDiscuss this resultChallenge it