AFTD Auto-Formalizing Theoretical Domains

max3cut_v_e_eq

theoremverified

For 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 16.

Statement

theorem max3cut_v_e_eq (x : Fin 3 → ZMod 3) :
    max3cut_v_e x = if max3cut_s x = 0 then 18 else 16
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 7
  • max3cut_v_eThe maximum cut value V_E(x) in the E-gadget for primary coloring x : Fin 3 → ZMod 3, defined as the supremum of max3cut_e_cut x a over…
  • 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.
  • max3cut_v_e_zeroThe maximum cut value of the E-gadget on the constant zero primary coloring fun _ => 0 is 18.
  • max3cut_v_e_rainbowThe maximum cut value of the E-gadget on the rainbow primary coloring ![0, 1, 2] is 18.
  • max3cut_v_e_two_equalThe maximum cut value of the E-gadget on the primary coloring ![0, 0, 1] is 16.
  • 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_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}$, the quantity $\text{max3cut\_v\_e}(x)$ is equal to $18$ if $\text{max3cut\_s}(x) = 0$ in $\mathbb{Z}/3\mathbb{Z}$, and is equal to $16$ otherwise.

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 characterizes the maximum cut value of the E-gadget for every primary coloring x. The result follows immediately by taking the first conjunct of max3cut_gadget_cut_values, which computes the cut values of both the E-gadget and N-gadget simultaneously.

  1. max3cut_v_e x = if max3cut_s x = 0 then 18 else 16

    The claim is the first conjunct of max3cut_gadget_cut_values x, which establishes the maximum cut values for both the E-gadget and the N-gadget. Projecting onto the first component (.1) immediately yields the result.

    line 4

    uses max3cut_gadget_cut_values

      exact (max3cut_gadget_cut_values x).1
max3cut_gadget_cut_values
For any primary coloring x, the cut value of the E-gadget is 18 if the sum of the colors is 0 (mod 3) and 16 otherwise, and the cut value of the N-gadget is 11 if the sum is non-zero (mod 3) and 9 otherwise.

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 E-gadget for all primary colorings. -/theorem max3cut_v_e_eq (x : Fin 3 → ZMod 3) :    max3cut_v_e x = if max3cut_s x = 0 then 18 else 16 := by  exact (max3cut_gadget_cut_values x).1
See it in the graphDiscuss this resultChallenge it