op75_compact_subset_equivalence
For any list of real weights and real target, the compact-map orbit ends at zero with accumulated digit-weighted sum equal to the target for some input in the unit interval if and only if the target is a subset sum of the list.
Statement
theorem op75_compact_subset_equivalence (as : List ℝ) (t : ℝ) :
(∃ x ∈ Set.Icc (0:ℝ) 1, (op75_run op75_compact_map op75_compact_digit as x).1 = 0 ∧
(op75_run op75_compact_map op75_compact_digit as x).2 = t) ↔ op75_subset as t- Source
- OP-75, arXiv:2610.06092, one-pass subset-sum construction; a helper toward interval verification.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.
- 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 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…
The proof, explained
The proof first establishes an abstract equivalence `op75_subset_orbit` for any dynamical system and digit extraction on $[0, 1]$: by induction on the weight list, each step peels off a weight $a$, where the digit extraction determines whether $a$ is added to the running sum, reducing reachability to whether $t$ or $t - a$ is a subset sum of the tail. It then analyzes the specific compact map $F(x) = \min(1, \min(4x, |4x-3|))$ and digit extractor $E(x) = \max(0, \min(1, 4x-1))$, showing they map $[0, 1]$ into $[0, 1]$, fix $1$, produce boolean digits away from $1$, and admit explicit preimages $y/4$ (with digit $0$) and $(y+3)/4$ (with digit $1$) for every $y \in [0, 1]$. Specializing the general theorem with these five verified properties yields the claimed equivalence.
If $F(1) = 1$, then starting an orbit at state $1$ leaves the state at $1$ after processing any list of weights.
By induction on the list of weights. In the base case of an empty list, the state is $1$ by definition. In the inductive step, the first transition maps $1$ to $F(1) = 1$, so the induction hypothesis on the tail of the list implies the final state remains $1$.
induction as with | nil => rfl | cons a as ih => simpa [op75_run, h1] using ih
For the empty list of weights, an orbit reaches $0$ with sum $t$ if and only if $t$ is a subset sum of the empty list (i.e., $t = 0$). automation
Running an empty list on input $x$ yields $(x, 0)$, so the sum is $0 = t$, matching the empty subset sum definition. Conversely, if $t = 0$, choosing $x = 0 \in [0, 1]$ yields final state $0$ and sum $0$. Linear arithmetic and normalization close the goals.
induction as generalizing t with | nil => constructor · rintro ⟨x, hx, he, hs⟩ simpa [op75_run, op75_subset] using hs.symm · intro ht have ht' : t = 0 := by simpa [op75_subset] using ht subst t exact ⟨0, by norm_num, rfl, rfl⟩
In the inductive step of `op75_subset_orbit`, if an orbit on $a :: as$ reaches state $0$ with sum $t$, then $t$ is a subset sum of $a :: as$.
Let $x \in [0, 1]$ be the starting point. If $F(x) = 1$, then by `op75_run_one` the final state would be $1$, contradicting that it reaches $0$; thus $F(x) \neq 1$. By the boolean digit assumption `hbool`, $E(x) \in \{0, 1\}$. By the induction hypothesis applied to the tail orbit starting at $F(x) \in [0, 1]$, the tail sum is a subset sum of $as$. If $E(x) = 0$, the total sum $t$ equals the tail sum, making $t$ a subset sum of $as$. If $E(x) = 1$, the tail sum equals $t - a$, making $t - a$ a subset sum of $as$. In either case, $t$ is a subset sum of $a :: as$.
uses
op75_run_one| cons a as ih => constructor · rintro ⟨x, hx, he, hs⟩ have hne : F x ≠ 1 := by intro heq have hzero : (op75_run F E as 1).1 = 0 := by simpa [op75_run, heq] using he rw [op75_run_one F E h1 as] at hzero norm_num at hzero have htail : op75_subset as (op75_run F E as (F x)).2 := by apply (ih _).mp exact ⟨F x, hclosed x hx, by simpa [op75_run] using he, rfl⟩ have hsum : a * E x + (op75_run F E as (F x)).2 = t := by simpa [op75_run] using hs rcases hbool x hx hne with hE | hE · left rw [hE] at hsum have : (op75_run F E as (F x)).2 = t := by linarith simpa [this] using htail · right rw [hE] at hsum have : (op75_run F E as (F x)).2 = t-a := by linarith simpa [this] using htailIn the inductive step of `op75_subset_orbit`, if $t$ is a subset sum of $a :: as$, then some orbit reaches state $0$ with sum $t$.
If $t$ is a subset sum of $as$, the induction hypothesis gives a witness $y \in [0, 1]$ whose orbit on $as$ ends at $0$ with sum $t$; by `hpre0`, choose a preimage $x \in [0, 1]$ with $F(x) = y$ and $E(x) = 0$, so the orbit on $a :: as$ transitions to $y$ with contribution $a \cdot 0 = 0$, achieving final state $0$ and sum $t$. If $t - a$ is a subset sum of $as$, the induction hypothesis gives $y \in [0, 1]$ whose orbit ends at $0$ with sum $t - a$; by `hpre1`, choose a preimage $x \in [0, 1]$ with $F(x) = y$ and $E(x) = 1$, where the contribution is $a \cdot 1 = a$ via `mul_one`, yielding total sum $a + (t - a) = t$.
uses
mul_one· intro ht rcases ht with ht | ht · obtain ⟨y, hy, hy0, hys⟩ := (ih t).mpr ht obtain ⟨x, hx, hfx, he0⟩ := hpre0 y hy refine ⟨x, hx, ?_, ?_⟩ · simpa [op75_run, hfx] using hy0 · simpa [op75_run, hfx, he0] using hys · obtain ⟨y, hy, hy0, hys⟩ := (ih (t-a)).mpr ht obtain ⟨x, hx, hfx, he1⟩ := hpre1 y hy refine ⟨x, hx, ?_, ?_⟩ · simpa [op75_run, hfx] using hy0 · simp only [op75_run, hfx, he1, mul_one] linarith
The compact map sends every point in $[0, 1]$ into $[0, 1]$.
The upper bound follows from `min_le_left`. The lower bound follows from `le_min` because $0 \le 1$, $0 \le 4x$ for $x \ge 0$, and the absolute value is non-negative by `abs_nonneg`.
uses
le_min,abs_nonneg,min_le_leftconstructor · exact le_min (by norm_num) (le_min (by linarith [hx.1]) (abs_nonneg _)) · exact min_le_left _ _
The compact map fixes $1$: $op75\_compact\_map(1) = 1$. automation
Unfolding the definition gives $\min(1, \min(4, |1|)) = 1$, verified by direct numerical evaluation.
norm_num [op75_compact_map]For $x \le 1/4$, the extracted digit is $0$.
If $x \le 1/4$, then $4x - 1 \le 0$. Since $\min(1, 4x - 1) \le 4x - 1$ by `min_le_right`, transitivity `le_trans` gives $\min(1, 4x - 1) \le 0$, so $\max(0, \min(1, 4x - 1)) = 0$ by `max_eq_left`.
uses
max_eq_left,le_trans,min_le_rightunfold op75_compact_digit apply max_eq_left exact le_trans (min_le_right _ _) (by linarith)
For $x \ge 1/2$, the extracted digit is $1$.
If $x \ge 1/2$, then $4x - 1 \ge 1$, so $\min(1, 4x - 1) = 1$ by `min_eq_left`, and $\max(0, 1) = 1$.
uses
min_eq_leftunfold op75_compact_digit rw [min_eq_left (by linarith : (1:ℝ) ≤ 4*x-1)] norm_num
For $x \in [0, 1]$, if $op75\_compact\_map(x) \neq 1$, then $op75\_compact\_digit(x) \in \{0, 1\}$.
Case split on $x$: if $x \le 1/4$, the digit is $0$ by `op75_compact_digit_low` via `Or.inl`. If $x \ge 1/2$, the digit is $1$ by `op75_compact_digit_high` via `Or.inr`. Otherwise $1/4 < x < 1/2$, so $4x \ge 1$ and $|4x - 3| \ge -(4x - 3) = 3 - 4x \ge 1$ using `neg_le_abs`. By `le_min` and `min_eq_left`, this implies $op75\_compact\_map(x) = 1$, contradicting the assumption.
uses
Or.inl,op75_compact_digit_low,Or.inr,op75_compact_digit_high,neg_le_abs,min_eq_left,le_minby_cases hlo : x ≤ 1/4 · exact Or.inl (op75_compact_digit_low x hlo) by_cases hhi : 1/2 ≤ x · exact Or.inr (op75_compact_digit_high x hhi) exfalso apply hne have ha : (1:ℝ) ≤ 4*x := by linarith have hb : (1:ℝ) ≤ |4*x-3| := by have h := neg_le_abs (4*x-3) linarith exact min_eq_left (le_min ha hb)
Every $y \in [0, 1]$ has a preimage $x \in [0, 1]$ with $op75\_compact\_map(x) = y$ and extracted digit $0$.
Set $x = y/4$. Then $0 \le x \le 1/4$, so $op75\_compact\_digit(x) = 0$ by `op75_compact_digit_low`. Furthermore $4x - 3 \le 0$, so `abs_of_nonpos` rewrites $|4x - 3| = -(4x - 3) = 3 - y$. Since $y \le 3 - y$ and $y \le 1$, simplifying the minima via `min_eq_left` and `min_eq_right` yields $op75\_compact\_map(x) = 4(y/4) = y$.
uses
op75_compact_digit_low,abs_of_nonpos,min_eq_left,min_eq_rightlet x : ℝ := y/4 have hx0 : 0 ≤ x := by dsimp [x]; linarith [hy.1] have hx1 : x ≤ 1 := by dsimp [x]; linarith [hy.2] have hxb : 4*x-3 ≤ 0 := by dsimp [x]; linarith [hy.2] have hsel : op75_compact_digit x = 0 := op75_compact_digit_low x (by dsimp [x]; linarith [hy.2]) have hfx : op75_compact_map x = y := by unfold op75_compact_map rw [abs_of_nonpos hxb] have hsmall : 4*x ≤ -(4*x-3) := by dsimp [x]; linarith [hy.2] rw [min_eq_left hsmall, min_eq_right (by dsimp [x]; linarith [hy.2])] dsimp [x] ring exact ⟨x, ⟨hx0,hx1⟩, hfx, hsel⟩
Every $y \in [0, 1]$ has a preimage $x \in [0, 1]$ with $op75\_compact\_map(x) = y$ and extracted digit $1$.
Set $x = (y+3)/4$. Then $3/4 \le x \le 1$, so $x \ge 1/2$ and `op75_compact_digit_high` ensures the digit is $1$. Because $4x - 3 = y \ge 0$, `abs_of_nonneg` gives $|4x - 3| = 4x - 3$. Since $4x - 3 \le 4x$ and $4x - 3 \le 1$, `min_eq_right` reduces the compact map to $4x - 3 = y$.
uses
op75_compact_digit_high,abs_of_nonneg,min_eq_rightlet x : ℝ := (y+3)/4 have hx0 : 0 ≤ x := by dsimp [x]; linarith [hy.1] have hx1 : x ≤ 1 := by dsimp [x]; linarith [hy.2] have hxb : 0 ≤ 4*x-3 := by dsimp [x]; linarith [hy.1] have hsel : op75_compact_digit x = 1 := op75_compact_digit_high x (by dsimp [x]; linarith [hy.1]) have hfx : op75_compact_map x = y := by unfold op75_compact_map rw [abs_of_nonneg hxb] have hsmall : 4*x-3 ≤ 4*x := by linarith rw [min_eq_right hsmall, min_eq_right (by dsimp [x]; linarith [hy.2])] dsimp [x] ring exact ⟨x, ⟨hx0,hx1⟩, hfx, hsel⟩
The orbit terminates at state $0$ with accumulated sum $t$ for some initial point in $[0, 1]$ if and only if $t$ is a subset sum of the weights.
Apply the general reduction theorem `op75_subset_orbit` to the compact map and digit extractor, supplying the five verified lemmas: interval closure (`op75_compact_closed`), the fixed point at $1$ (`op75_compact_one`), binary digits away from $1$ (`op75_compact_boolean`), and the existence of preimages with digit $0$ (`op75_compact_pre0`) and digit $1$ (`op75_compact_pre1`).
uses
op75_subset_orbit,op75_compact_closed,op75_compact_one,op75_compact_boolean,op75_compact_pre0,op75_compact_pre1exact op75_subset_orbit op75_compact_map op75_compact_digit op75_compact_closed op75_compact_one op75_compact_boolean op75_compact_pre0 op75_compact_pre1 as t
op75_run_one- If $F(1) = 1$, then starting the dynamical process at $x = 1$ keeps the state at $1$ after processing any list of weights.
mul_one- Multiplying any element by $1$ leaves it unchanged ($a \cdot 1 = a$).
le_min- A value is less than or equal to $\min(a, b)$ if it is less than or equal to both $a$ and $b$.
abs_nonneg- The absolute value of any number is non-negative ($0 \le |a|$).
min_le_left- The minimum of two numbers is less than or equal to the first number ($\min(a, b) \le a$).
max_eq_left- If $b \le a$, then the maximum of $a$ and $b$ is equal to $a$.
le_trans- The inequality relation is transitive: if $a \le b$ and $b \le c$, then $a \le c$.
min_le_right- The minimum of two numbers is less than or equal to the second number ($\min(a, b) \le b$).
min_eq_left- If $a \le b$, then the minimum of $a$ and $b$ is equal to $a$.
Or.inl- If a proposition $A$ holds, then the disjunction $A \lor B$ holds.
op75_compact_digit_low- For any $x \le 1/4$, the extracted digit of $x$ is $0$.
Or.inr- If a proposition $B$ holds, then the disjunction $A \lor B$ holds.
op75_compact_digit_high- For any $x \ge 1/2$, the extracted digit of $x$ is $1$.
neg_le_abs- The negation of any real number is less than or equal to its absolute value ($-a \le |a|$).
abs_of_nonpos- If a real number $a$ is non-positive ($a \le 0$), its absolute value is its negation ($-a$).
min_eq_right- If $b \le a$, then the minimum of $a$ and $b$ is equal to $b$.
abs_of_nonneg- If a real number $a$ is non-negative ($a \ge 0$), its absolute value is itself ($a$).
op75_subset_orbit- For any transition map $F$ and digit extractor $E$ satisfying the five conditions (maps $[0, 1]$ into $[0, 1]$, fixes $1$, produces binary digits away from $1$, and has preimages for every $y \in [0, 1]$ with digit $0$ and digit $1$), an orbit reaches state $0$ with sum $t$ if and only if $t$ is a subset sum of the weight list.
op75_compact_closed- The compact map maps the unit interval $[0, 1]$ into $[0, 1]$.
op75_compact_one- The value of the compact map at $1$ is $1$.
op75_compact_boolean- For any point $x \in [0, 1]$ where the compact map is not equal to $1$, the extracted digit is either $0$ or $1$.
op75_compact_pre0- Every target $y \in [0, 1]$ has a preimage $x \in [0, 1]$ under the compact map with extracted digit $0$.
op75_compact_pre1- Every target $y \in [0, 1]$ has a preimage $x \in [0, 1]$ under the compact map with extracted digit $1$.
- The formalization proves a general reduction `op75_subset_orbit` for any dynamical system and digit extraction satisfying five abstract conditions before verifying those conditions for the specific piecewise-linear compact map and digit function.
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.
open Setlemma op75_run_one (F E : ℝ → ℝ) (h1 : F 1 = 1) (as : List ℝ) : (op75_run F E as 1).1 = 1 := by induction as with | nil => rfl | cons a as ih => simpa [op75_run, h1] using ihtheorem op75_subset_orbit (F E : ℝ → ℝ) (hclosed : ∀ x ∈ Icc (0:ℝ) 1, F x ∈ Icc (0:ℝ) 1) (h1 : F 1 = 1) (hbool : ∀ x ∈ Icc (0:ℝ) 1, F x ≠ 1 → E x = 0 ∨ E x = 1) (hpre0 : ∀ y ∈ Icc (0:ℝ) 1, ∃ x ∈ Icc (0:ℝ) 1, F x = y ∧ E x = 0) (hpre1 : ∀ y ∈ Icc (0:ℝ) 1, ∃ x ∈ Icc (0:ℝ) 1, F x = y ∧ E x = 1) (as : List ℝ) (t : ℝ) : (∃ x ∈ Icc (0:ℝ) 1, (op75_run F E as x).1 = 0 ∧ (op75_run F E as x).2 = t) ↔ op75_subset as t := by induction as generalizing t with | nil => constructor · rintro ⟨x, hx, he, hs⟩ simpa [op75_run, op75_subset] using hs.symm · intro ht have ht' : t = 0 := by simpa [op75_subset] using ht subst t exact ⟨0, by norm_num, rfl, rfl⟩ | cons a as ih => constructor · rintro ⟨x, hx, he, hs⟩ have hne : F x ≠ 1 := by intro heq have hzero : (op75_run F E as 1).1 = 0 := by simpa [op75_run, heq] using he rw [op75_run_one F E h1 as] at hzero norm_num at hzero have htail : op75_subset as (op75_run F E as (F x)).2 := by apply (ih _).mp exact ⟨F x, hclosed x hx, by simpa [op75_run] using he, rfl⟩ have hsum : a * E x + (op75_run F E as (F x)).2 = t := by simpa [op75_run] using hs rcases hbool x hx hne with hE | hE · left rw [hE] at hsum have : (op75_run F E as (F x)).2 = t := by linarith simpa [this] using htail · right rw [hE] at hsum have : (op75_run F E as (F x)).2 = t-a := by linarith simpa [this] using htail · intro ht rcases ht with ht | ht · obtain ⟨y, hy, hy0, hys⟩ := (ih t).mpr ht obtain ⟨x, hx, hfx, he0⟩ := hpre0 y hy refine ⟨x, hx, ?_, ?_⟩ · simpa [op75_run, hfx] using hy0 · simpa [op75_run, hfx, he0] using hys · obtain ⟨y, hy, hy0, hys⟩ := (ih (t-a)).mpr ht obtain ⟨x, hx, hfx, he1⟩ := hpre1 y hy refine ⟨x, hx, ?_, ?_⟩ · simpa [op75_run, hfx] using hy0 · simp only [op75_run, hfx, he1, mul_one] linarithlemma op75_compact_closed (x : ℝ) (hx : x ∈ Icc (0:ℝ) 1) : op75_compact_map x ∈ Icc (0:ℝ) 1 := by constructor · exact le_min (by norm_num) (le_min (by linarith [hx.1]) (abs_nonneg _)) · exact min_le_left _ _lemma op75_compact_one : op75_compact_map 1 = 1 := by norm_num [op75_compact_map]lemma op75_compact_digit_low (x : ℝ) (hx : x ≤ 1/4) : op75_compact_digit x = 0 := by unfold op75_compact_digit apply max_eq_left exact le_trans (min_le_right _ _) (by linarith)lemma op75_compact_digit_high (x : ℝ) (hx : 1/2 ≤ x) : op75_compact_digit x = 1 := by unfold op75_compact_digit rw [min_eq_left (by linarith : (1:ℝ) ≤ 4*x-1)] norm_numlemma op75_compact_boolean (x : ℝ) (_hx : x ∈ Icc (0:ℝ) 1) (hne : op75_compact_map x ≠ 1) : op75_compact_digit x = 0 ∨ op75_compact_digit x = 1 := by by_cases hlo : x ≤ 1/4 · exact Or.inl (op75_compact_digit_low x hlo) by_cases hhi : 1/2 ≤ x · exact Or.inr (op75_compact_digit_high x hhi) exfalso apply hne have ha : (1:ℝ) ≤ 4*x := by linarith have hb : (1:ℝ) ≤ |4*x-3| := by have h := neg_le_abs (4*x-3) linarith exact min_eq_left (le_min ha hb)lemma op75_compact_pre0 (y : ℝ) (hy : y ∈ Icc (0:ℝ) 1) : ∃ x ∈ Icc (0:ℝ) 1, op75_compact_map x = y ∧ op75_compact_digit x = 0 := by let x : ℝ := y/4 have hx0 : 0 ≤ x := by dsimp [x]; linarith [hy.1] have hx1 : x ≤ 1 := by dsimp [x]; linarith [hy.2] have hxb : 4*x-3 ≤ 0 := by dsimp [x]; linarith [hy.2] have hsel : op75_compact_digit x = 0 := op75_compact_digit_low x (by dsimp [x]; linarith [hy.2]) have hfx : op75_compact_map x = y := by unfold op75_compact_map rw [abs_of_nonpos hxb] have hsmall : 4*x ≤ -(4*x-3) := by dsimp [x]; linarith [hy.2] rw [min_eq_left hsmall, min_eq_right (by dsimp [x]; linarith [hy.2])] dsimp [x] ring exact ⟨x, ⟨hx0,hx1⟩, hfx, hsel⟩lemma op75_compact_pre1 (y : ℝ) (hy : y ∈ Icc (0:ℝ) 1) : ∃ x ∈ Icc (0:ℝ) 1, op75_compact_map x = y ∧ op75_compact_digit x = 1 := by let x : ℝ := (y+3)/4 have hx0 : 0 ≤ x := by dsimp [x]; linarith [hy.1] have hx1 : x ≤ 1 := by dsimp [x]; linarith [hy.2] have hxb : 0 ≤ 4*x-3 := by dsimp [x]; linarith [hy.1] have hsel : op75_compact_digit x = 1 := op75_compact_digit_high x (by dsimp [x]; linarith [hy.1]) have hfx : op75_compact_map x = y := by unfold op75_compact_map rw [abs_of_nonneg hxb] have hsmall : 4*x-3 ≤ 4*x := by linarith rw [min_eq_right hsmall, min_eq_right (by dsimp [x]; linarith [hy.2])] dsimp [x] ring exact ⟨x, ⟨hx0,hx1⟩, hfx, hsel⟩theorem op75_compact_subset_equivalence (as : List ℝ) (t : ℝ) : (∃ x ∈ Set.Icc (0:ℝ) 1, (op75_run op75_compact_map op75_compact_digit as x).1 = 0 ∧ (op75_run op75_compact_map op75_compact_digit as x).2 = t) ↔ op75_subset as t := by exact op75_subset_orbit op75_compact_map op75_compact_digit op75_compact_closed op75_compact_one op75_compact_boolean op75_compact_pre0 op75_compact_pre1 as t