AFTD Auto-Formalizing Theoretical Domains

max3cut_v_e_two_equal

theoremverified

The maximum cut value of the E-gadget on the primary coloring ![0, 0, 1] is 16.

Statement

theorem max3cut_v_e_two_equal : max3cut_v_e ![0, 0, 1] = 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 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_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…
  • 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_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…
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

max3cut_v_e ![0, 0, 1] = 16, which asserts that evaluating the function max3cut_v_e at the vector ![0, 0, 1] : Fin 3 → ZMod 3 yields 16.

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 maximum cut value of the E-gadget on the boundary coloring ![0, 0, 1] is evaluated using the general characterization max3cut_gadget_cut_values, which asserts that the value is 18 if the sum of the colors is 0 mod 3 and 16 otherwise. Since the sum 0 + 0 + 1 is 1 ≠ 0 mod 3, the conditional expression evaluates directly to 16.

  1. The maximum cut value max3cut_v_e ![0, 0, 1] reduces to evaluating the conditional expression (if max3cut_s ![0, 0, 1] = 0 then 18 else 16).

    We rewrite the cut value using the first component of the lemma max3cut_gadget_cut_values instantiated at x = ![0, 0, 1]. This replaces the maximum cut value max3cut_v_e with a conditional expression depending on whether the color sum max3cut_s vanishes modulo 3.

    line 3

    uses max3cut_gadget_cut_values

      rw [(max3cut_gadget_cut_values ![0, 0, 1]).1]
  2. The equality 16 = 16 holds.

    Evaluating the sum of the components of ![0, 0, 1] in ℤ/3ℤ yields 0 + 0 + 1 = 1 ≠ 0, so the 'else' branch of the conditional evaluates to 16, completing the proof by finite decidable computation.

    line 4

      decide
max3cut_gadget_cut_values
For any coloring x of the three boundary vertices, the maximum cut value of the E-gadget is 18 if the sum of the colors is 0 in ℤ/3ℤ and 16 otherwise, and the maximum cut value of the N-gadget is 11 if the sum is non-zero and 9 if it is zero.

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

/-- V_E on the primary coloring (0,0,1) is 16. -/theorem max3cut_v_e_two_equal : max3cut_v_e ![0, 0, 1] = 16 := by  rw [(max3cut_gadget_cut_values ![0, 0, 1]).1]  decide
See it in the graphDiscuss this resultChallenge it