op_75_relu_width3_lifting
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
netof 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].
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.
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 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.
lemma op_75_relu_width3_lifting_eval_one_net (x : ℝ) : evalNetwork (⟨0, 0, [], 0, (1:ℚ)⟩ : ReLUNetwork 3) x = 1 := by simp [evalNetwork]
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.
intro f by_cases h : ThreeSATToClique.is3Satisfiable f
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.
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]
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.
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
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.
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
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.
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.
- The theorem asserts the existence of a width-3 ReLU network for each 3-CNF formula f, but does not require this network to be computable or efficiently constructible from f. The proof exploits this non-constructively via classical case analysis on whether f is satisfiable, choosing a constant-zero network when f is satisfiable and a constant-one network when f is unsatisfiable.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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