AFTD Auto-Formalizing Theoretical Domains

not_submodular_cube_three_two

theoremverified

For dimension n = 3 and range bound k = 2, the conjunction function x ↦ if x 0 ∧ x 1 then 1 else 0 is not submodular.

Statement

theorem not_submodular_cube_three_two :
    ¬ is_submodular_cube (fun (x : Fin 3 → Bool) => (if x 0 && x 1 then (1 : Fin 3) else 0))
Source
arXiv:2611.02374, Sec. 1.2
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_submodular_cubeA function f from the Boolean hypercube to {0, ..., k} is submodular if f(x ∨ y) + f(x ∧ y) ≤ f(x) + f(y) for all x, y in {0, 1}^n when…

Read back from the Lean

The function $f : (\text{Fin } 3 \to \text{Bool}) \to \text{Fin } 3$ defined by $x \mapsto \text{if } x(0) \land x(1) \text{ then } 1 \text{ else } 0$ is not submodular; that is, it is not the case that for all $x, y : \text{Fin } 3 \to \text{Bool}$, $(f(x \sqcup y) : \mathbb{R}) + (f(x \sqcap y) : \mathbb{R}) \le (f(x) : \mathbb{R}) + (f(y) : \mathbb{R})$.

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 proof proceeds by contradiction. Assuming the conjunction function f(x) = (if x 0 ∧ x 1 then 1 else 0) is submodular on {0, 1}³, we specialize the submodularity inequality to the two standard basis vectors x = (1, 0, 0) and y = (0, 1, 0). Their join is (1, 1, 0) where f evaluates to 1, whereas their meet is (0, 0, 0) and the vectors themselves evaluate to 0, producing the false inequality 1 ≤ 0.

  1. Assume for contradiction that the function is submodular.

    We assume the hypothesis `h` that the conjunction function f(x) = (if x 0 ∧ x 1 then 1 else 0) satisfies the submodularity inequality f(x ⊔ y) + f(x ⊓ y) ≤ f(x) + f(y) for all x, y : Fin 3 → Bool.

    line 4

      intro h
  2. Specialize the submodularity condition to the unit vectors for coordinates 0 and 1.

    We instantiate the universally quantified submodularity hypothesis with the vector x = (fun i => i == 0), which has 1 at coordinate 0 and 0 elsewhere, and y = (fun i => i == 1), which has 1 at coordinate 1 and 0 elsewhere.

    line 5

      have h_spec := h (fun i => i == 0) (fun i => i == 1)
  3. Evaluating the inequality on these vectors yields a contradiction. automation

    We move the instantiated inequality into the goal and evaluate it using `norm_num`. On these inputs, the meet x ⊓ y is the all-zeros vector, while the join x ⊔ y has 1 at both coordinates 0 and 1. Hence f(x ⊔ y) = 1, f(x ⊓ y) = 0, and f(x) = f(y) = 0, reducing the inequality to 1 + 0 ≤ 0 + 0 (or 1 ≤ 0), which is false.

    lines 6–7

      revert h_spec
      norm_num

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

/-- A conjunction function on {0, 1}^3 with range Fin 3 is not submodular. -/theorem not_submodular_cube_three_two :    ¬ is_submodular_cube (fun (x : Fin 3 → Bool) => (if x 0 && x 1 then (1 : Fin 3) else 0)) := by  intro h  have h_spec := h (fun i => i == 0) (fun i => i == 1)  revert h_spec  norm_num
See it in the graphDiscuss this resultChallenge it