max3cut_v_n_eq
For every primary coloring x : Fin 3 → ZMod 3, the maximum cut weight of the N-gadget is V_N(x) = 11 if s(x) ≠ 0 and 9 otherwise.
Statement
theorem max3cut_v_n_eq (x : Fin 3 → ZMod 3) : max3cut_v_n x = if max3cut_s x ≠ 0 then 11 else 9
- Source
- arXiv:2611.01402 Lemma 3.1 -- Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small k
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- max3cut_v_nThe maximum cut weight V_N(x) in the N-gadget for primary coloring x : Fin 3 → ZMod 3, maximized over all 3 colorings q : ZMod 3 of the…
- max3cut_sThe sum s(x) = x 0 + x 1 + x 2 in ZMod 3 of the colors of the three primary vertices for a color tuple x : Fin 3 → ZMod 3.
- Used by 1
- max3cut_gadget_cut_valuesFor every primary coloring x : Fin 3 → ZMod 3, the maximum cut value of the E-gadget is max3cut_v_e x = if max3cut_s x = 0 then 18 else…
Read back from the Lean
For every function $x : \text{Fin } 3 \to \mathbb{Z}/3\mathbb{Z}$, $\text{max3cut\_v\_n}(x)$ equals $11$ if $\text{max3cut\_s}(x) \neq 0$ and $9$ otherwise (i.e., if $\text{max3cut\_s}(x) = 0$).
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 theorem asserts that the maximum cut value V_N(x) of the N-gadget equals 11 if the sum s(x) is nonzero in ZMod 3, and 9 otherwise. Because the space of primary colorings x : Fin 3 → ZMod 3 contains only 3³ = 27 functions, the universal statement is finite and purely computational. The proof moves x into a universal quantifier and verifies all 27 cases by exhaustive evaluation using the decision procedure.
It suffices to prove the identity universally for all colorings x : Fin 3 → ZMod 3.
Reverting x places the coloring back into the goal under a universal quantifier, yielding the closed proposition that the identity holds for all 27 functions from Fin 3 to ZMod 3.
revert x
The identity V_N(x) = (if s(x) ≠ 0 then 11 else 9) holds for every coloring x. automation
The domain Fin 3 → ZMod 3 is finite with exactly 3³ = 27 elements, and the functions involved (summation in ZMod 3, cardinality of filtered sets, and the maximum over ZMod 3) are all computable. The decision procedure decide evaluates both sides for all 27 inputs and verifies that they coincide in every case.
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
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.
/-- Cut value of the N-gadget for all primary colorings. -/theorem max3cut_v_n_eq (x : Fin 3 → ZMod 3) : max3cut_v_n x = if max3cut_s x ≠ 0 then 11 else 9 := by revert x decide