relu_network_width4_lifting
Width-4 lifting theorem (Theorem 5.8 of arXiv:2610.06092): For every 3-CNF formula $f$ with variable indices in $\mathbb{N}$, there exists a width-4 feedforward ReLU neural network net that is non-negative on $[0, 1]$ and satisfies that $f$ is satisfiable if and only if net has a zero in $[0, 1]$.
Statement
theorem relu_network_width4_lifting :
∀ (f : ThreeSATToClique.Formula3 ℕ),
∃ (net : ReLUNetwork 4),
(∀ x ∈ Set.Icc (0 : ℝ) 1, 0 ≤ evalNetwork net x) ∧
(ThreeSATToClique.is3Satisfiable f ↔ relu_network_has_unit_interval_zero net)- Formalizes
- arXiv:2610.06092 Theorem 5.8
- 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-SAT formula $f$ with variables indexed by $\mathbb{N}$ (ThreeSATToClique.Formula3 ℕ), there exists a ReLU neural network net of width 4 (with rational weights and biases, a 1-dimensional input, and a 1-dimensional output) such that:
1. For all $x \in [0, 1]$, the output of net evaluated at $x$ is non-negative ($\ge 0$).
2. The formula $f$ is 3-satisfiable (ThreeSATToClique.is3Satisfiable f) if and only if there exists some $x \in [0, 1]$ such that net evaluates to $0$ at $x$ (relu_network_has_unit_interval_zero net).
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 is proven by a classical case analysis on whether the 3-CNF formula f is satisfiable. If f is satisfiable, the witness is the trivial constant zero network, which is non-negative and has a zero at x = 0. If f is unsatisfiable, the witness is the trivial constant one network, which is non-negative and has no zero anywhere. In both cases, the equivalence between the satisfiability of f and the network possessing a zero on [0, 1] holds immediately.
The constant zero network evaluates to 0 for every real input. automation
By definition of `evalNetwork`, a network with no hidden layers, zero output weights, and zero output bias evaluates to 0 on any real input x. The `simp` tactic unfolds the evaluation function and computes the result.
theorem relu_network_width4_lifting_eval_zero_net (x : ℝ) : evalNetwork ({ in_weight := 0, in_bias := 0, layers := [], out_weight := 0, out_bias := (0:ℚ) } : ReLUNetwork 4) x = 0 := by simp [evalNetwork]
The constant one network evaluates to 1 for every real input. automation
Similarly, a network with no hidden layers, zero output weights, and output bias 1 evaluates to 1 on any real input x. The `simp` tactic unfolds `evalNetwork` and simplifies the arithmetic.
theorem relu_network_width4_lifting_eval_one_net (x : ℝ) : evalNetwork ({ in_weight := 0, in_bias := 0, layers := [], out_weight := 0, out_bias := (1:ℚ) } : ReLUNetwork 4) x = 1 := by simp [evalNetwork]
Given a 3-CNF formula f, we split into cases based on whether f is satisfiable.
We introduce the formula f and apply the law of excluded middle via `by_cases` on `ThreeSATToClique.is3Satisfiable f`, dividing the proof into the case where f is satisfiable and the case where f is unsatisfiable.
intro f by_cases h : ThreeSATToClique.is3Satisfiable f
When f is satisfiable, the constant zero network is non-negative on [0, 1].
We instantiate the existential quantifier with the width-4 network having empty hidden layers, zero weights, and zero bias. For any x ∈ [0, 1], rewriting with `relu_network_width4_lifting_eval_zero_net` simplifies its evaluation to 0, and 0 ≤ 0 holds reflexively.
uses
relu_network_width4_lifting_eval_zero_net· refine ⟨⟨0, 0, [], 0, (0:ℚ)⟩, ?_, ?_⟩ · intro x _ rw [relu_network_width4_lifting_eval_zero_net]
When f is satisfiable, the satisfiability of f is equivalent to the constant zero network having a zero in [0, 1].
For the forward implication, x = 0 ∈ [0, 1] serves as an explicit zero since the network evaluates to 0 everywhere by `relu_network_width4_lifting_eval_zero_net 0`. The reverse implication holds trivially because f is already known to be satisfiable from the case hypothesis.
uses
relu_network_width4_lifting_eval_zero_net· constructor · intro _ exact ⟨0, by norm_num, relu_network_width4_lifting_eval_zero_net 0⟩ · intro _ exact h
When f is unsatisfiable, the constant one network is non-negative on [0, 1].
We instantiate the existential quantifier with the width-4 network having empty hidden layers, zero weights, and output bias 1. For any x ∈ [0, 1], rewriting with `relu_network_width4_lifting_eval_one_net` reduces the evaluation to 1, and `norm_num` confirms that 0 ≤ 1.
uses
relu_network_width4_lifting_eval_one_net· refine ⟨⟨0, 0, [], 0, (1:ℚ)⟩, ?_, ?_⟩ · intro x _ rw [relu_network_width4_lifting_eval_one_net] norm_num
When f is unsatisfiable, the satisfiability of f is equivalent to the constant one network having a zero in [0, 1].
Both directions hold by contradiction: assuming f is satisfiable contradicts the case hypothesis that f is not satisfiable. Conversely, assuming there exists x ∈ [0, 1] where the network evaluates to 0, rewriting by `relu_network_width4_lifting_eval_one_net` produces the false identity 1 = 0, which `norm_num` refutes.
uses
relu_network_width4_lifting_eval_one_net· constructor · intro hsat exact absurd hsat h · rintro ⟨x, -, hx⟩ rw [relu_network_width4_lifting_eval_one_net] at hx norm_num at hx
relu_network_width4_lifting_eval_zero_net- The width-4 feedforward ReLU network with no hidden layers, zero weights, and zero bias evaluates to 0 on every real input x.
relu_network_width4_lifting_eval_one_net- The width-4 feedforward ReLU network with no hidden layers, zero weights, and output bias 1 evaluates to 1 on every real input x.
- Although the docstring references Theorem 5.8 of arXiv:2610.06092 (which on paper establishes NP-hardness via an efficient reduction from 3-SAT to width-4 ReLU verification), the formal Lean statement only requires the existence of a network for each formula. Because Lean uses classical logic, the proof takes a non-constructive shortcut via the law of excluded middle (`by_cases`), choosing either the constant 0 network or the constant 1 network without constructing a reduction.
- The arithmetic evaluation `0 ≤ 1` and the derivation of a contradiction from `1 = 0` in the unsatisfiable case are closed automatically by the decision procedure `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
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.
theorem relu_network_width4_lifting_eval_zero_net (x : ℝ) : evalNetwork ({ in_weight := 0, in_bias := 0, layers := [], out_weight := 0, out_bias := (0:ℚ) } : ReLUNetwork 4) x = 0 := by simp [evalNetwork]theorem relu_network_width4_lifting_eval_one_net (x : ℝ) : evalNetwork ({ in_weight := 0, in_bias := 0, layers := [], out_weight := 0, out_bias := (1:ℚ) } : ReLUNetwork 4) x = 1 := by simp [evalNetwork]/-- Theorem 5.8 of arXiv:2610.06092: 3-SAT lifts to width-4 ReLU verification on [0,1]. -/theorem relu_network_width4_lifting : ∀ (f : ThreeSATToClique.Formula3 ℕ), ∃ (net : ReLUNetwork 4), (∀ 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 _ rw [relu_network_width4_lifting_eval_zero_net] · constructor · intro _ exact ⟨0, by norm_num, relu_network_width4_lifting_eval_zero_net 0⟩ · intro _ exact h · refine ⟨⟨0, 0, [], 0, (1:ℚ)⟩, ?_, ?_⟩ · intro x _ rw [relu_network_width4_lifting_eval_one_net] norm_num · constructor · intro hsat exact absurd hsat h · rintro ⟨x, -, hx⟩ rw [relu_network_width4_lifting_eval_one_net] at hx norm_num at hx