max3cut_gadget_cut_values
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, and the maximum cut weight of the N-gadget is max3cut_v_n x = if max3cut_s x ≠ 0 then 11 else 9.
Statement
theorem max3cut_gadget_cut_values (x : Fin 3 → ZMod 3) : (max3cut_v_e x = if max3cut_s x = 0 then 18 else 16) ∧ (max3cut_v_n x = if max3cut_s x ≠ 0 then 11 else 9)
- Formalizes
- 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 4
- 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_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.
- max3cut_v_n_eqFor 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.
- Used by 2
- max3cut_v_e_eqFor 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.
- max3cut_v_e_two_equalThe maximum cut value of the E-gadget on the primary coloring ![0, 0, 1] is 16.
Read back from the Lean
For every assignment $x : \mathrm{Fin}\ 3 \to \mathbb{Z}/3\mathbb{Z}$, both of the following hold:
1. The gadget cut value max3cut_v_e x equals $18$ if max3cut_s x = 0 (in $\mathbb{Z}/3\mathbb{Z}$), and equals $16$ otherwise.
2. The gadget cut value max3cut_v_n x equals $11$ if max3cut_s x ≠ 0 (in $\mathbb{Z}/3\mathbb{Z}$), and equals $9$ 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 proof divides into two conjuncts for the E-gadget and N-gadget, respectively. For the E-gadget, the statement quantifies over a finite domain of 27 primary colorings and is verified by exhaustive computation in the kernel. For the N-gadget, the cut value formula is discharged directly by the helper lemma max3cut_v_n_eq.
The goal splits into two parts: determining the maximum cut value of the E-gadget and determining that of the N-gadget.
Applying the conjunction constructor divides the target into two independent subgoals.
constructorFor all primary colorings x, the maximum cut value of the E-gadget max3cut_v_e x is 18 if max3cut_s x = 0 and 16 otherwise. automation
Reverting x produces a universally quantified statement over the finite type Fin 3 → ZMod 3, which contains 3³ = 27 elements. For each coloring, computing max3cut_v_e x involves taking a maximum over 3⁶ = 729 auxiliary assignments. Because the domain and computations are finite, the statement is decidable and is verified exhaustively by Lean's kernel.
· revert x decide +kernelFor the coloring x, the maximum cut weight of the N-gadget max3cut_v_n x is 11 if max3cut_s x ≠ 0 and 9 otherwise.
This is exactly the statement of the previously established lemma max3cut_v_n_eq applied to x.
uses
max3cut_v_n_eq· exact max3cut_v_n_eq x
max3cut_v_n_eq- For any coloring x : Fin 3 → ZMod 3, the maximum cut weight of the N-gadget max3cut_v_n x is 11 if max3cut_s x ≠ 0 and 9 otherwise.
- The cut value formula for the E-gadget is verified via kernel reduction (`decide +kernel`), which evaluates the maximum cut value over all 27 primary colorings and 729 auxiliary assignments without generating step-by-step deductive proof terms.
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 values of the E-gadget and N-gadget for Max-3-Cut (Lemma 3.1). -/theorem max3cut_gadget_cut_values (x : Fin 3 → ZMod 3) : (max3cut_v_e x = if max3cut_s x = 0 then 18 else 16) ∧ (max3cut_v_n x = if max3cut_s x ≠ 0 then 11 else 9) := by constructor · revert x decide +kernel · exact max3cut_v_n_eq x