AFTD Auto-Formalizing Theoretical Domains

max3cut_v_n_eq

theoremverified

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.

  1. 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.

    line 4

      revert x
  2. 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.

    line 5

      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

/-- 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
See it in the graphDiscuss this resultChallenge it