AFTD Auto-Formalizing Theoretical Domains

relu_width3_unit_interval_zero_language

def

The verification language at width 3 on the unit interval, for the fixed encoding relu_network3_encode: the set of Bool words w such that w = relu_network3_encode net for some width-3 feedforward ReLU network net with rational weights and biases (ReLUNetwork 3) that has a zero in [0, 1] (relu_network_has_unit_interval_zero net).

Statement

def relu_width3_unit_interval_zero_language : Language Bool
Defined in
arXiv:2610.06092 (Fractal Gadgets for Neural Networks: The Complexity of the Narrow Regime), Section 2.1 (network representation: rational entries as pairs of integers written in binary) and Remark 5.15. The bit-level layout is a choice made here; the paper fixes only binary numerators and denominators.
Verified
09 Nov 2026
Axioms
none listed
Built on 3
  • relu_network3_encodeEncoding of a width-3 ReLU network as a Bool word, of length linear in the total bit length of its rational entries: input weights, input…
  • 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…
  • ReLUNetworkA feedforward ReLU neural network from the real line to the real line with hidden layers of width k, specified by rational affine input…
Used by 7

Read back from the Lean

The definition relu_width3_unit_interval_zero_language defines the formal language over the boolean alphabet Bool (i.e., a set of lists of booleans List Bool) consisting of all words w such that there exists a ReLU neural network of width 3 with rational parameters (net : ReLUNetwork 3) satisfying: 1. The binary encoding of net under relu_network3_encode is equal to w, and 2. net has a zero in the closed unit interval $[0, 1]$ (i.e., there exists $x \in [0, 1] \subseteq \mathbb{R}$ such that evalNetwork net x = 0).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

def relu_width3_unit_interval_zero_language : Language Bool :=
  {w | ∃ net : ReLUNetwork 3, relu_network3_encode net = w ∧
    relu_network_has_unit_interval_zero net}
See it in the graphDiscuss this resultChallenge it