AFTD Auto-Formalizing Theoretical Domains

max3cut_s

def

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

Statement

def max3cut_s (x : Fin 3 → ZMod 3) : ZMod 3
Defined in
arXiv:2611.01402 Lemma 3.1 -- Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small k
Verified
03 Nov 2026
Axioms
none listed
Used by 4
  • 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.
  • 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_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_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

Definition of a function max3cut_s that takes an argument x : Fin 3 → ZMod 3 and returns x 0 + x 1 + x 2 in ZMod 3 (the sum of the values of x at indices 0, 1, and 2 modulo 3).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The sum s(x) = x_0 + x_1 + x_2 mod 3 for a primary coloring x. -/
def max3cut_s (x : Fin 3 → ZMod 3) : ZMod 3 := x 0 + x 1 + x 2
See it in the graphDiscuss this resultChallenge it