max3cut_v_e_zero
The maximum cut value of the E-gadget on the constant zero primary coloring fun _ => 0 is 18.
Statement
theorem max3cut_v_e_zero : max3cut_v_e (fun _ => 0) = 18
- 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 1
- 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…
- Used by 1
- 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.
Read back from the Lean
The declaration asserts that max3cut_v_e evaluated at the constant zero function fun _ => 0 on Fin 3 is equal to 18. That is, the maximum over all assignments a : Fin 6 → ZMod 3 of the quantity max3cut_e_cut (fun _ => 0) a is 18.
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 3-cut value of the $E$-gadget under the constant zero primary coloring is 18. Because the auxiliary vertex set has 6 vertices colored in $\mathbb{Z}/3\mathbb{Z}$, there are only $3^6 = 729$ possible configurations to consider. The proof delegates the finite exhaustive check directly to Lean's kernel via `decide +kernel`.
The maximum 3-cut value of the E-gadget with the constant zero coloring on the primary vertices is 18. automation
The cut value `max3cut_v_e` is defined as the maximum cut over all assignments from the 6 auxiliary vertices to $\mathbb{Z}/3\mathbb{Z}$. Since there are only $3^6 = 729$ such assignments, whether the maximum equals 18 is a decidable equality between natural numbers. The `decide +kernel` tactic instructs the Lean kernel to compute the supremum by exhaustive evaluation over all 729 assignments and check that the result is 18.
theorem max3cut_v_e_zero : max3cut_v_e (fun _ => 0) = 18 := by decide +kernel
- The proof is entirely computational: `decide +kernel` instructs Lean's kernel to evaluate the finite supremum over all $3^6 = 729$ possible auxiliary assignments to verify that the maximum cut value is 18.
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.
/-- V_E on the monochromatic primary coloring (0,0,0) is 18. -/theorem max3cut_v_e_zero : max3cut_v_e (fun _ => 0) = 18 := by decide +kernel