AFTD Auto-Formalizing Theoretical Domains

op75_compact_network_subset_sum

theoremverifiedoriginal

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 net of 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

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