AFTD Auto-Formalizing Theoretical Domains

max3cut_n_cut

def

The cut weight in the N-gadget with primary coloring x : Fin 3 → ZMod 3 and auxiliary coloring q : ZMod 3, consisting of a unit-weight triangle on the three primaries and edges of weight 3 from q to each primary vertex.

Statement

def max3cut_n_cut (x : Fin 3 → ZMod 3) (q : 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 1
  • 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…

Read back from the Lean

A definition of a function max3cut_n_cut that takes an assignment x : Fin 3 → ZMod 3 and an element q : ZMod 3, and returns the natural number given by: (1 if x 0 ≠ x 1 else 0) + (1 if x 1 ≠ x 2 else 0) + (1 if x 2 ≠ x 0 else 0) + 3 * (the number of p : Fin 3 such that x p ≠ q).

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 cut weight in the N-gadget for colorings x and q. -/
def max3cut_n_cut (x : Fin 3 → ZMod 3) (q : ZMod 3) : ℕ :=
  (if x 0 ≠ x 1 then 1 else 0) +
  (if x 1 ≠ x 2 then 1 else 0) +
  (if x 2 ≠ x 0 then 1 else 0) +
  3 * (Finset.univ.filter fun p : Fin 3 => x p ≠ q).card
See it in the graphDiscuss this resultChallenge it