op75_compact_network_subset_sum
For any finite list of nonnegative integer weights and nonnegative integer target, the explicitly constructed width-three ReLU network has a zero in the unit interval if and only if some subset of the list sums to the target.
Statement
theorem op75_compact_network_subset_sum (as : List ℕ) (t : ℕ) : relu_network_has_unit_interval_zero (op75_compact_network as t) ↔ op75_subset (as.map fun a => (a : ℝ)) (t : ℝ)
- Related work
- OP-75, arXiv:2610.06092, Remark 5.15; the paper leaves width-three verification on the full unit interval open.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- 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_block_effectFor an input in the unit interval and a nonnegative accumulator, the seven-layer block for a nonnegative integer weight transforms the…
- op75_compact_subset_equivalenceFor any list of real weights and real target, the compact-map orbit ends at zero with accumulated digit-weighted sum equal to the target…
- 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_subsetA real target belongs to the subset sums of a list when it can be obtained recursively by either omitting or including the first weight.
- 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… - 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…
- 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_network_evalFor a unit-interval input, the explicit subset-sum network evaluates to the final orbit coordinate plus the absolute difference between…
- 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.
- Used by 2
- op75_invalid_input_fallback_nonmemberThe encoding of the empty-weight target-one network is a no-instance of the width-three unit-interval zero language.
- op75_subset_compiler_semanticsAny total binary function that maps canonical subset-sum instances to their specified networks and maps malformed inputs outside the zero…
Read back from the Lean
For every list of natural numbers as and every natural number t, the ReLU neural network op75_compact_network as t has a zero in the unit interval $[0, 1]$ (that is, there exists $x \in [0, 1]$ such that the network evaluates to $0$ at $x$) if and only if the subset sum predicate op75_subset holds for the list as cast to real numbers and target t cast to real (that is, there exists a subset of the elements of as that sums to t).
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
theorem op75_compact_network_subset_sum (as : List ℕ) (t : ℕ) : relu_network_has_unit_interval_zero (op75_compact_network as t) ↔ op75_subset (as.map fun a => (a : ℝ)) (t : ℝ) := by have htyped : relu_network_has_unit_interval_zero (op75_compact_network as t) ↔ op75_subset (as.map fun a : ℕ => (a:ℝ)) (t:ℝ) := by rw [← op75_compact_subset_equivalence] unfold relu_network_has_unit_interval_zero constructor · rintro ⟨x,hx,hzero⟩ have hq := op75_run_invariants as x hx rw [op75_network_eval as t x hx] at hzero have habs := abs_nonneg ((op75_run op75_compact_map op75_compact_digit (as.map fun a : ℕ => (a:ℝ)) x).2 - (t:ℝ)) have hfirst : (op75_run op75_compact_map op75_compact_digit (as.map fun a : ℕ => (a:ℝ)) x).1 = 0 := by linarith [hq.1.1] have hsecond : (op75_run op75_compact_map op75_compact_digit (as.map fun a : ℕ => (a:ℝ)) x).2 = (t:ℝ) := by have : |(op75_run op75_compact_map op75_compact_digit (as.map fun a : ℕ => (a:ℝ)) x).2 - (t:ℝ)| = 0 := by linarith [hq.1.1] exact sub_eq_zero.mp (abs_eq_zero.mp this) exact ⟨x,hx,hfirst,hsecond⟩ · rintro ⟨x,hx,hfirst,hsecond⟩ refine ⟨x,hx,?_⟩ rw [op75_network_eval as t x hx,hfirst,hsecond] simp simpa [← List.map_eq_flatMap, Function.comp_def] using htyped