op75_compact_block_effect
For an input in the unit interval and a nonnegative accumulator, the seven-layer block for a nonnegative integer weight transforms the state (x,p,0) to (F(x),p+a E(x),0), using the compact map F and digit selector E.
Statement
theorem op75_compact_block_effect (x p : ℝ) (a : ℕ) (hx : x ∈ Set.Icc 0 1) (hp : 0 ≤ p) : (op75_compact_block a).foldl (fun v layer => evalHiddenLayer layer v) ![x,p,0] = ![op75_compact_map x, p + (a : ℝ) * op75_compact_digit x, 0]
- Source
- OP-75, arXiv:2610.06092; explicit seven-layer single-pass subset-sum construction.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- op75_compact_blockSeven width-three hidden layers for one nonnegative integer weight in the one-pass subset-sum construction.
- op75_compact_mapThe compact piecewise-affine map x ↦ min(1, 4x, |4x−3|) used in the one-pass reduction.
- op75_compact_digitThe digit selector x ↦ max(0, min(1, 4x−1)) used in the one-pass reduction.
- op75_compact_map_reluOn the unit interval the compact map is computed by the displayed nested rectified affine expression.
- op75_compact_digit_reluThe compact digit selector is the difference of the two rectified affine functions max(4x−1,0) and max(4x−2,0).
- 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.
- Used by 2
- op75_compact_network_subset_sumFor any finite list of nonnegative integer weights and nonnegative integer target, the explicitly constructed width-three ReLU network has…
- op75_fold_blocksFor a nonnegative initial accumulator and an initial point in the unit interval, folding the seven-layer blocks gives the final orbit…
The proof, explained
The theorem shows that feeding the state vector (x, p, 0) through a 7-layer ReLU neural network block with integer weight parameter a ≥ 0 yields (F(x), p + a E(x), 0), where F is the compact map and E is the digit selector. The proof first establishes nonnegativity bounds for intermediate accumulator values and for F(x), allowing all internal ReLU activations to be replaced by their linear arguments. It then evaluates the network block coordinate-wise: coordinate 2 vanishes, while coordinates 0 and 1 match the ReLU representations of F(x) and p + a E(x) via straightforward ring arithmetic.
The digit selector E(x), the weight parameter a, and the intermediate accumulator value p + a * max(4x - 1, 0) are all nonnegative.
By definition, the digit selector E(x) is max 0 (min 1 (4x - 1)), so 0 ≤ E(x) follows from le_max_left. The coerced weight a is nonnegative by Nat.cast_nonneg. Since p ≥ 0, a ≥ 0, and max(4x - 1, 0) ≥ 0, their combination p + a * max(4x - 1, 0) is nonnegative by positivity.
uses
le_max_left,Nat.cast_nonneghave hE : 0 ≤ op75_compact_digit x := le_max_left _ _ have hA : (0:ℝ) ≤ a := Nat.cast_nonneg _ have hpre : 0 ≤ p + (a:ℝ) * max (4*x-1) 0 := by positivity
The updated accumulator value p + a * max(4x - 1, 0) - a * max(4x - 2, 0) is nonnegative.
Since a ≥ 0 and E(x) ≥ 0, their product a * E(x) is nonnegative by mul_nonneg. Rewriting E(x) via op75_compact_digit_relu expresses this product as a * (max(4x - 1, 0) - max(4x - 2, 0)) ≥ 0. Adding the nonnegative initial accumulator p ≥ 0 preserves nonnegativity, which nonlinear arithmetic (nlinarith) verifies.
uses
mul_nonneg,op75_compact_digit_reluhave hpost : 0 ≤ p + (a:ℝ) * max (4*x-1) 0 - (a:ℝ)*max (4*x-2) 0 := by have hh := mul_nonneg hA hE rw [op75_compact_digit_relu] at hh nlinarith
The compact map value F(x) is nonnegative.
Unfolding the definition of op75_compact_map gives min 1 (min (4x) |4x - 3|). Applying le_min reduces this to showing each component is nonnegative: 0 ≤ 1 by numeric computation, 0 ≤ 4x by linear arithmetic since x ≥ 0, and 0 ≤ |4x - 3| by abs_nonneg.
uses
le_min,abs_nonneghave hF : 0 ≤ op75_compact_map x := by unfold op75_compact_map exact le_min (by norm_num) (le_min (by linarith [hx.1]) (abs_nonneg _))
The nested ReLU expression 1 - max(1 - 4x + max(8x - 3 - max(8x - 6, 0), 0), 0) is nonnegative.
Rewriting with the lemma op75_compact_map_relu equates this nested ReLU expression directly to op75_compact_map x for x ∈ [0, 1], which was already shown to be nonnegative.
uses
op75_compact_map_reluhave hpos : 0 ≤ 1 - max (1-4*x + max (8*x-3 - max (8*x-6) 0) 0) 0 := by rw [← op75_compact_map_relu x hx] exact hF
Evaluating the 7-layer block on (x, p, 0) coordinate-wise reduces the third coordinate to 0 and simplifies the first two coordinates to single outer ReLUs.
Function extensionality (funext i) checks vector equality coordinate-wise across i ∈ {0, 1, 2} (fin_cases i). The simplifier evaluates the list fold over the 7 layers, expanding layer evaluation, weights, biases, and matrix-vector sums via Fin.sum_univ_three. The precomputed nonnegativity hypotheses allow inner ReLUs max(y, 0) to simplify to y via max_eq_left. Coordinate 2 simplifies completely to 0 = 0, while coordinates 0 and 1 reduce to single outer maximum expressions.
uses
Fin.sum_univ_three,max_eq_left,op75_compact_digit_relu,op75_compact_map_relufunext i fin_cases i <;> simp [op75_compact_block, op75_compact_layer, evalHiddenLayer, relu, Fin.sum_univ_three, max_eq_left hx.1, max_eq_left hp, max_eq_left hpre, max_eq_left hpost, max_eq_left hpos, op75_compact_digit_relu, op75_compact_map_relu x hx]
All polynomial subexpressions in the hypotheses and remaining goals are in normal form.
The ring normalization tactic ring_nf puts the linear and polynomial expressions in hpos, hpre, hpost, and both remaining goals into canonical form, standardizing term orders.
all_goals ring_nf at hpos hpre hpost ⊢
The first coordinate matches F(x).
For coordinate 0, the goal has the form max y 0 = y where y is the ReLU representation of F(x). Because 0 ≤ y was established in hpos, max_eq_left hpos immediately closes the goal.
uses
max_eq_left· exact max_eq_left hposThe second coordinate matches p + a * E(x).
For coordinate 1, the inner maximum simplifies via max_eq_left hpre. Linear arithmetic (linarith) rearranges hpost into hpost', which shows the outer maximum argument is nonnegative and simplifies via max_eq_left hpost'. Finally, ring arithmetic confirms both sides are identical.
uses
max_eq_left· rw [max_eq_left hpre] have hpost' : 0 ≤ -((a:ℝ)*max (-2+x*4) 0) + (p+(a:ℝ)*max (-1+x*4) 0) := by linarith rw [max_eq_left hpost'] ring
le_max_left- In any linear order, a ≤ max a b.
Nat.cast_nonneg- The image of any natural number in an ordered semiring is nonnegative (0 ≤ (n : α)).
mul_nonneg- If a ≥ 0 and b ≥ 0, then their product satisfies a * b ≥ 0.
op75_compact_digit_relu- For any real number x, op75_compact_digit x = max (4*x - 1) 0 - max (4*x - 2) 0.
le_min- In a linear order, if c ≤ a and c ≤ b, then c ≤ min a b.
abs_nonneg- The absolute value |a| of an element in an ordered additive group is nonnegative.
op75_compact_map_relu- For x ∈ [0, 1], the compact map satisfies op75_compact_map x = 1 - max (1 - 4*x + max (8*x - 3 - max (8*x - 6) 0) 0) 0.
Fin.sum_univ_three- The sum of a function f over the 3-element finite type Fin 3 is f(0) + f(1) + f(2).
max_eq_left- If b ≤ a in a linear order, then max a b = a.
- The 7-layer neural network feedforward computation is evaluated in one step by `simp`, which unrolls the list fold, computes the matrix-vector products and bias additions coordinate-wise, and completely resolves coordinate 2.
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 op75_compact_block_effect (x p : ℝ) (a : ℕ) (hx : x ∈ Set.Icc 0 1) (hp : 0 ≤ p) : (op75_compact_block a).foldl (fun v layer => evalHiddenLayer layer v) ![x,p,0] = ![op75_compact_map x, p + (a : ℝ) * op75_compact_digit x, 0] := by have hE : 0 ≤ op75_compact_digit x := le_max_left _ _ have hA : (0:ℝ) ≤ a := Nat.cast_nonneg _ have hpre : 0 ≤ p + (a:ℝ) * max (4*x-1) 0 := by positivity have hpost : 0 ≤ p + (a:ℝ) * max (4*x-1) 0 - (a:ℝ)*max (4*x-2) 0 := by have hh := mul_nonneg hA hE rw [op75_compact_digit_relu] at hh nlinarith have hF : 0 ≤ op75_compact_map x := by unfold op75_compact_map exact le_min (by norm_num) (le_min (by linarith [hx.1]) (abs_nonneg _)) have hpos : 0 ≤ 1 - max (1-4*x + max (8*x-3 - max (8*x-6) 0) 0) 0 := by rw [← op75_compact_map_relu x hx] exact hF funext i fin_cases i <;> simp [op75_compact_block, op75_compact_layer, evalHiddenLayer, relu, Fin.sum_univ_three, max_eq_left hx.1, max_eq_left hp, max_eq_left hpre, max_eq_left hpost, max_eq_left hpos, op75_compact_digit_relu, op75_compact_map_relu x hx] all_goals ring_nf at hpos hpre hpost ⊢ · exact max_eq_left hpos · rw [max_eq_left hpre] have hpost' : 0 ≤ -((a:ℝ)*max (-2+x*4) 0) + (p+(a:ℝ)*max (-1+x*4) 0) := by linarith rw [max_eq_left hpost'] ring