AFTD Auto-Formalizing Theoretical Domains

max3cut_v_e_rainbow

theoremverified

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

Statement

theorem max3cut_v_e_rainbow : max3cut_v_e ![0, 1, 2] = 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 value of max3cut_v_e evaluated at the function ![0, 1, 2] : Fin 3 → ZMod 3 (which maps 0 ↦ 0, 1 ↦ 1, 2 ↦ 2) is equal to 18. That is, the supremum (maximum) over all colorings a : Fin 6 → ZMod 3 of the cut size max3cut_e_cut ![0, 1, 2] a equals 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 states that the maximum cut value of the E-gadget on the rainbow primary coloring (0, 1, 2) is 18. Because there are only 3⁶ = 729 possible colorings for the 6 auxiliary vertices, the maximum can be found by exhaustive finite evaluation. Lean establishes this directly by definitional reduction via reflexivity (`rfl`), with the maximum recursion depth increased to allow the computation to complete.

  1. max3cut_v_e ![0, 1, 2] = 18

    The quantity `max3cut_v_e ![0, 1, 2]` is defined as the maximum over all 3⁶ = 729 colorings of the 6 auxiliary vertices of gadget E. This is a finite, computable search. Increasing the recursion depth allows Lean's kernel to evaluate this finite supremum by definitional equality, establishing that the maximum cut value is 18 via reflexivity (`rfl`).

    lines 3–4

      set_option maxRecDepth 50000 in
      rfl

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 rainbow primary coloring (0,1,2) is 18. -/theorem max3cut_v_e_rainbow : max3cut_v_e ![0, 1, 2] = 18 := by  set_option maxRecDepth 50000 in  rfl
See it in the graphDiscuss this resultChallenge it