maxcut_cycle71_minimal_cycle_steps
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
- maxcut_unweighted_minimal_deviation_cycle_existsOn the specified unweighted 71-vertex graph there is an infinite three-color strong-deviation sequence returning after 33 steps, and every…
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.
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.
(by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 3
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.
(by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance) 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.
uses
Fin.extintro i by_cases hi : i.val = 0 · have hi0 : i = 0 := Fin.ext (by simpa using hi) subst i
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.
uses
zero_add,maxcut_cycle71_first_deviation_minimalhave 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
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.
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
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.
uses
maxcut_cycle71_return_stepshave hs := maxcut_cycle71_return_steps j dsimp only at hs rw [hfirst, hnext] at hs obtain ⟨hd, hc⟩ := hs rw [hc] refine ⟨hd, ?_⟩
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.
uses
Finset.eq_empty_of_ssubset_singleton,Finset.not_nonempty_emptyintro 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.
- The theorem statement contains inline tactic proofs establishing the decidability of graph adjacency by unfolding the definitions of maxcut_cycle71_graph and maxcut_cycle71_field and invoking typeclass inference. In the i = 0 case, the equality identifying the set of vertices that change color as {v | v.val < 32} is verified by kernel computation (decide +kernel).
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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