AFTD Auto-Formalizing Theoretical Domains

op75_compact_subset_equivalence

theoremverified

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.

  1. 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$.

    lines 5–7

      induction as with
      | nil => rfl
      | cons a as ih => simpa [op75_run, h1] using ih
  2. 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.

    lines 17–25

      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⟩
  3. 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$.

    lines 26–46

    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 htail
  4. In 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$.

    lines 47–59

    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
  5. 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`.

    lines 63–65

    uses le_min, abs_nonneg, min_le_left

      constructor
      · exact le_min (by norm_num) (le_min (by linarith [hx.1]) (abs_nonneg _))
      · exact min_le_left _ _
  6. 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.

    line 68

      norm_num [op75_compact_map]
  7. 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`.

    lines 71–73

    uses max_eq_left, le_trans, min_le_right

      unfold op75_compact_digit
      apply max_eq_left
      exact le_trans (min_le_right _ _) (by linarith)
  8. 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$.

    lines 76–78

    uses min_eq_left

      unfold op75_compact_digit
      rw [min_eq_left (by linarith : (1:ℝ) ≤ 4*x-1)]
      norm_num
  9. 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.

    lines 82–92

    uses Or.inl, op75_compact_digit_low, Or.inr, op75_compact_digit_high, neg_le_abs, min_eq_left, le_min

      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)
  10. 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$.

    lines 96–108

    uses op75_compact_digit_low, abs_of_nonpos, min_eq_left, min_eq_right

      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⟩
  11. 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$.

    lines 112–124

    uses op75_compact_digit_high, abs_of_nonneg, min_eq_right

      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⟩
  12. 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`).

    lines 129–130

    uses op75_subset_orbit, op75_compact_closed, op75_compact_one, op75_compact_boolean, op75_compact_pre0, op75_compact_pre1

      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
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$.

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

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