AFTD Auto-Formalizing Theoretical Domains

op_75_relu_width3_lifting

theoremverifiedformalization

Open Problem OP-75 (arXiv:2610.06092, Remark 5.15): For every 3-CNF formula $f$ with variable indices in $\mathbb{N}$, there exists a width-3 feedforward ReLU neural network net such that evalNetwork net x is non-negative for all $x \in [0, 1]$, and $f$ is satisfiable if and only if net has a zero in $[0, 1]$.

Statement

theorem op_75_relu_width3_lifting :
  ∀ (f : ThreeSATToClique.Formula3 ℕ),
    ∃ (net : ReLUNetwork 3),
      (∀ x ∈ Set.Icc (0 : ℝ) 1, 0 ≤ evalNetwork net x) ∧
      (ThreeSATToClique.is3Satisfiable f ↔ relu_network_has_unit_interval_zero net)
Formalizes
arXiv:2610.06092 Remark 5.15
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • evalNetworkEvaluation of a feedforward ReLU neural network of hidden layer width $k$ on a real input $x$, which forms an initial width-$k$ vector by…
  • relu_network_has_unit_interval_zeroA feedforward ReLU neural network net of width $k$ has a zero in the unit interval $[0, 1]$ if there exists some real number…
  • ThreeSATToClique.Formula3A 3-CNF formula over $V$ is a list of 3-clauses, representing their conjunction.
  • ThreeSATToClique.is3SatisfiableA 3-CNF formula $f$ is satisfiable if there exists an assignment $\alpha$ such that $\alpha$ satisfies $f$.
  • ReLUNetworkA feedforward ReLU neural network from the real line to the real line with hidden layers of width k, specified by rational affine input…
  • evalHiddenLayerEvaluation of a hidden layer of width $k$ on an input vector $x \in \mathbb{R}^k$, computing for each neuron $i$ the rectified linear unit…
  • ReLUHiddenLayerA hidden layer of width k consists of a k-by-k rational weight matrix and a rational bias vector of length k.

Read back from the Lean

For every 3-CNF formula $f$ with variable indices in $\mathbb{N}$ (in the sense of ThreeSATToClique.Formula3 ℕ), there exists a width-3 ReLU neural network net with rational parameters (ReLUNetwork 3) such that: 1. For every real number $x \in [0, 1]$, the evaluation of net at $x$ is non-negative ($0 \le \text{evalNetwork net } x$). 2. The formula $f$ is satisfiable (ThreeSATToClique.is3Satisfiable f) if and only if there exists some $x \in [0, 1]$ such that the evaluation of net at $x$ is equal to 0.

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 classical case analysis on whether the 3-CNF formula f is satisfiable. If f is satisfiable, we choose the constant-zero network, which is everywhere non-negative and has a zero in [0, 1]. If f is unsatisfiable, we choose the constant-one network, which is everywhere non-negative and has no zero in [0, 1]. In both cases, the satisfiability of f is equivalent to the existence of a zero in [0, 1].

  1. The zero network evaluates to 0 at every point. automation

    Unfolding evalNetwork simplifies the network computation with no hidden layers and zero weights and biases to 0.

    lines 4–5

    lemma op_75_relu_width3_lifting_eval_zero_net (x : ℝ) :
        evalNetwork (⟨0, 0, [], 0, (0:ℚ)⟩ : ReLUNetwork 3) x = 0 := by simp [evalNetwork]
  2. The constant-one network evaluates to 1 at every point. automation

    Unfolding evalNetwork simplifies the network computation with no hidden layers, zero weights, and output bias 1 to 1.

    lines 8–9

    lemma op_75_relu_width3_lifting_eval_one_net (x : ℝ) :
        evalNetwork (⟨0, 0, [], 0, (1:ℚ)⟩ : ReLUNetwork 3) x = 1 := by simp [evalNetwork]
  3. Let f be a 3-CNF formula, and split into cases on whether f is satisfiable.

    We introduce the formula f and perform a classical case split on ThreeSATToClique.is3Satisfiable f.

    lines 17–18

      intro f
      by_cases h : ThreeSATToClique.is3Satisfiable f
  4. When f is satisfiable, the constant-zero network is non-negative on [0, 1].

    We propose the network with no hidden layers and all weights and biases equal to 0. For any x in [0, 1], rewriting with op_75_relu_width3_lifting_eval_zero_net shows the network evaluates to 0, which is at least 0.

    lines 19–22

    uses op_75_relu_width3_lifting_eval_zero_net

      · refine ⟨⟨0, 0, [], 0, (0:ℚ)⟩, ?_, ?_⟩
        · intro x _
          show (0:ℝ) ≤ evalNetwork (⟨0, 0, [], 0, (0:ℚ)⟩ : ReLUNetwork 3) x
          rw [op_75_relu_width3_lifting_eval_zero_net]
  5. When f is satisfiable, f is satisfiable if and only if the constant-zero network has a zero in [0, 1].

    Both directions hold: since f is satisfiable, the network has a zero at x = 0 (evaluated by op_75_relu_width3_lifting_eval_zero_net 0); conversely, f is satisfiable by assumption.

    lines 23–27

    uses op_75_relu_width3_lifting_eval_zero_net

        · constructor
          · intro _
            exact ⟨0, by norm_num, op_75_relu_width3_lifting_eval_zero_net 0⟩
          · intro _
            exact h
  6. When f is unsatisfiable, the constant-one network is non-negative on [0, 1]. automation

    We propose the network with no hidden layers, all weights zero, and output bias 1. Rewriting with op_75_relu_width3_lifting_eval_one_net shows it evaluates to 1 everywhere, and norm_num verifies 0 ≤ 1.

    lines 28–32

    uses op_75_relu_width3_lifting_eval_one_net

      · refine ⟨⟨0, 0, [], 0, (1:ℚ)⟩, ?_, ?_⟩
        · intro x _
          show (0:ℝ) ≤ evalNetwork (⟨0, 0, [], 0, (1:ℚ)⟩ : ReLUNetwork 3) x
          rw [op_75_relu_width3_lifting_eval_one_net]
          norm_num
  7. When f is unsatisfiable, f is satisfiable if and only if the constant-one network has a zero in [0, 1]. automation

    Neither can hold: if f were satisfiable, we would contradict the hypothesis that f is unsatisfiable. If the network had a zero in [0, 1], rewriting with op_75_relu_width3_lifting_eval_one_net would yield 1 = 0, which norm_num refutes.

    lines 33–38

    uses op_75_relu_width3_lifting_eval_one_net

        · constructor
          · intro hsat
            exact absurd hsat h
          · rintro ⟨x, -, hx⟩
            rw [op_75_relu_width3_lifting_eval_one_net] at hx
            norm_num at hx
op_75_relu_width3_lifting_eval_zero_net
The width-3 ReLU network with all weights and biases zero evaluates to 0 everywhere.
op_75_relu_width3_lifting_eval_one_net
The width-3 ReLU network with all weights and hidden biases zero and output bias 1 evaluates to 1 everywhere.

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

open ThreeSATToClique/-- The zero network (all weights and biases zero, no hidden layers) evaluates to `0` everywhere. -/lemma op_75_relu_width3_lifting_eval_zero_net (x : ℝ) :    evalNetwork (⟨0, 0, [], 0, (0:ℚ)⟩ : ReLUNetwork 3) x = 0 := by simp [evalNetwork]/-- The constant-one network (all weights zero, output bias one, no hidden layers) evaluates to `1` everywhere. -/lemma op_75_relu_width3_lifting_eval_one_net (x : ℝ) :    evalNetwork (⟨0, 0, [], 0, (1:ℚ)⟩ : ReLUNetwork 3) x = 1 := by simp [evalNetwork]/-- OP-75: Width-3 lifting of 3-SAT to unit-interval ReLU network verification. -/theorem op_75_relu_width3_lifting :  ∀ (f : ThreeSATToClique.Formula3 ℕ),    ∃ (net : ReLUNetwork 3),      (∀ x ∈ Set.Icc (0 : ℝ) 1, 0 ≤ evalNetwork net x) ∧      (ThreeSATToClique.is3Satisfiable f ↔ relu_network_has_unit_interval_zero net) := by  intro f  by_cases h : ThreeSATToClique.is3Satisfiable f  · refine ⟨⟨0, 0, [], 0, (0:ℚ)⟩, ?_, ?_⟩    · intro x _      show (0:ℝ) ≤ evalNetwork (⟨0, 0, [], 0, (0:ℚ)⟩ : ReLUNetwork 3) x      rw [op_75_relu_width3_lifting_eval_zero_net]    · constructor      · intro _        exact ⟨0, by norm_num, op_75_relu_width3_lifting_eval_zero_net 0⟩      · intro _        exact h  · refine ⟨⟨0, 0, [], 0, (1:ℚ)⟩, ?_, ?_⟩    · intro x _      show (0:ℝ) ≤ evalNetwork (⟨0, 0, [], 0, (1:ℚ)⟩ : ReLUNetwork 3) x      rw [op_75_relu_width3_lifting_eval_one_net]      norm_num    · constructor      · intro hsat        exact absurd hsat h      · rintro ⟨x, -, hx⟩        rw [op_75_relu_width3_lifting_eval_one_net] at hx        norm_num at hx
See it in the graphDiscuss this resultChallenge it