AFTD Auto-Formalizing Theoretical Domains

relu_network_width4_lifting

theoremverifiedformalization

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 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-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.

  1. 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.

    lines 1–3

    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]
  2. 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.

    lines 5–7

    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]
  3. 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.

    lines 15–16

      intro f
      by_cases h : ThreeSATToClique.is3Satisfiable f
  4. 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.

    lines 17–19

    uses relu_network_width4_lifting_eval_zero_net

      · refine ⟨⟨0, 0, [], 0, (0:ℚ)⟩, ?_, ?_⟩
        · intro x _
          rw [relu_network_width4_lifting_eval_zero_net]
  5. 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.

    lines 20–24

    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
  6. 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.

    lines 25–28

    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
  7. 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.

    lines 29–34

    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.

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

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
See it in the graphDiscuss this resultChallenge it