AFTD Auto-Formalizing Theoretical Domains

max3cut_e_cut

def

The cut weight in the 18-edge E-gadget for primary coloring x : Fin 3 → ZMod 3 and auxiliary coloring a : Fin 6 → ZMod 3, defined as the sum of the number of pairs (p, v) in the list [(0, 0), (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (1, 4), (1, 5), (2, 0), (2, 1), (2, 4), (2, 5)] with x p ≠ a v, and the number of pairs (u, v) in the list [(0, 5), (0, 3), (1, 2), (1, 4), (2, 5), (3, 4)] with a u ≠ a v.

Statement

def max3cut_e_cut (x : Fin 3 → ZMod 3) (a : Fin 6 → 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_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…

Read back from the Lean

max3cut_e_cut is a function that takes two assignments x : Fin 3 → ZMod 3 and a : Fin 6 → ZMod 3 and returns a natural number equal to the sum of: 1. The number of pairs (p, v) in the 12-element list [(0, 0), (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (1, 4), (1, 5), (2, 0), (2, 1), (2, 4), (2, 5)] (of type List (Fin 3 × Fin 6)) such that x p ≠ a v. 2. The number of pairs (u, v) in the 6-element list [(0, 5), (0, 3), (1, 2), (1, 4), (2, 5), (3, 4)] (of type List (Fin 6 × Fin 6)) such that a u ≠ a v.

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 18-edge E-gadget for colorings x and a. -/
def max3cut_e_cut (x : Fin 3 → ZMod 3) (a : Fin 6 → ZMod 3) : ℕ :=
  (([(0, 0), (0, 1), (0, 2), (0, 3),
     (1, 2), (1, 3), (1, 4), (1, 5),
     (2, 0), (2, 1), (2, 4), (2, 5)] : List (Fin 3 × Fin 6)).filter fun (p, v) => x p ≠ a v).length +
  (([(0, 5), (0, 3), (1, 2), (1, 4), (2, 5), (3, 4)] : List (Fin 6 × Fin 6)).filter fun (u, v) => a u ≠ a v).length
See it in the graphDiscuss this resultChallenge it