op75_network_eval
theoremverified
For a unit-interval input, the explicit subset-sum network evaluates to the final orbit coordinate plus the absolute difference between its accumulated sum and the target.
Statement
theorem op75_network_eval (as : List ℕ) (t : ℕ) (x : ℝ) (hx : x ∈ Set.Icc 0 1) : evalNetwork (op75_compact_network as t) x = (op75_run op75_compact_map op75_compact_digit (as.map fun a : ℕ => (a:ℝ)) x).1 + |(op75_run op75_compact_map op75_compact_digit (as.map fun a : ℕ => (a:ℝ)) x).2 - (t:ℝ)|
- Source
- OP-75, arXiv:2610.06092: proof of the explicit single-pass subset-sum network.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- op75_compact_networkThe width-three network obtained by concatenating a seven-layer block for each integer weight, followed by the final target-checking layer…
- op75_compact_finalA width-three layer that forwards the orbit coordinate and computes the two positive parts of the accumulated sum minus the target.
- op75_compact_layerA width-three hidden layer formed from a rational three-by-three matrix and rational bias vector.
- op75_fold_blocksFor a nonnegative initial accumulator and an initial point in the unit interval, folding the seven-layer blocks gives the final orbit…
- op75_run_invariantsFor nonnegative integer weights and a starting point in the unit interval, the compact orbit remains in the unit interval and its…
- op75_runFor a map F, a digit function E, and real weights, iteratively apply F and return the final orbit value together with the sum of the…
- 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.
- 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…
- 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.
- op75_compact_blockSeven width-three hidden layers for one nonnegative integer weight in the one-pass subset-sum construction.
- Used by 1
- op75_compact_network_subset_sumFor any finite list of nonnegative integer weights and nonnegative integer target, the explicitly constructed width-three ReLU network has…
Lean source view module on GitHub
theorem op75_network_eval (as : List ℕ) (t : ℕ) (x : ℝ) (hx : x ∈ Set.Icc 0 1) : evalNetwork (op75_compact_network as t) x = (op75_run op75_compact_map op75_compact_digit (as.map fun a : ℕ => (a:ℝ)) x).1 + |(op75_run op75_compact_map op75_compact_digit (as.map fun a : ℕ => (a:ℝ)) x).2 - (t:ℝ)| := by let q := op75_run op75_compact_map op75_compact_digit (as.map fun a : ℕ => (a:ℝ)) x have hq : q.1 ∈ Set.Icc (0:ℝ) 1 ∧ 0 ≤ q.2 := op75_run_invariants as x hx have hfold := op75_fold_blocks as x 0 hx (by norm_num) change ((as.flatMap op75_compact_block).foldl (fun v l => evalHiddenLayer l v) ![x,0,0]) = ![q.1, 0+q.2, 0] at hfold have hinit : (fun i : Fin 3 => (((![1,0,0] : Fin 3 → ℚ) i : ℝ) * x + (((![0,0,0] : Fin 3 → ℚ) i : ℝ)))) = ![x,0,0] := by funext i fin_cases i <;> simp simp only [evalNetwork, op75_compact_network] rw [hinit, List.foldl_append, hfold] simp only [List.foldl_cons, List.foldl_nil, zero_add, Rat.cast_zero] change (∑ i, ((![1,1,1] : Fin 3 → ℚ) i : ℝ) * (evalHiddenLayer (op75_compact_final t) ![q.1,q.2,0]) i) + 0 = q.1 + |q.2 - (t:ℝ)| by_cases h : q.2 ≤ (t:ℝ) · have ha : q.2 - (t:ℝ) ≤ 0 := by linarith have hb : 0 ≤ (t:ℝ) - q.2 := by linarith rw [abs_of_nonpos ha] simp [evalHiddenLayer,op75_compact_final,op75_compact_layer,relu,Fin.sum_univ_three, max_eq_left hq.1.1] have ha' : q.2 + -(t:ℝ) ≤ 0 := by linarith rw [max_eq_right ha'] have hb' : 0 ≤ -q.2 + (t:ℝ) := by linarith rw [max_eq_left hb'] ring · have ha : 0 ≤ q.2 - (t:ℝ) := by linarith have hb : (t:ℝ) - q.2 ≤ 0 := by linarith rw [abs_of_nonneg ha] simp [evalHiddenLayer,op75_compact_final,op75_compact_layer,relu,Fin.sum_univ_three, max_eq_left hq.1.1] have ha' : 0 ≤ q.2 + -(t:ℝ) := by linarith rw [max_eq_left ha'] have hb' : -q.2 + (t:ℝ) ≤ 0 := by linarith rw [max_eq_right hb'] ring