AFTD Auto-Formalizing Theoretical Domains

op75_compact_block_effect

theoremverified

For an input in the unit interval and a nonnegative accumulator, the seven-layer block for a nonnegative integer weight transforms the state (x,p,0) to (F(x),p+a E(x),0), using the compact map F and digit selector E.

Statement

theorem op75_compact_block_effect (x p : ℝ) (a : ℕ) (hx : x ∈ Set.Icc 0 1) (hp : 0 ≤ p) : (op75_compact_block a).foldl (fun v layer => evalHiddenLayer layer v) ![x,p,0] = ![op75_compact_map x, p + (a : ℝ) * op75_compact_digit x, 0]
Source
OP-75, arXiv:2610.06092; explicit seven-layer single-pass subset-sum construction.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • op75_compact_blockSeven width-three hidden layers for one nonnegative integer weight in the one-pass subset-sum construction.
  • 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.
  • op75_compact_map_reluOn the unit interval the compact map is computed by the displayed nested rectified affine expression.
  • op75_compact_digit_reluThe compact digit selector is the difference of the two rectified affine functions max(4x−1,0) and max(4x−2,0).
  • 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.
Used by 2
  • op75_compact_network_subset_sumFor any finite list of nonnegative integer weights and nonnegative integer target, the explicitly constructed width-three ReLU network has…
  • op75_fold_blocksFor a nonnegative initial accumulator and an initial point in the unit interval, folding the seven-layer blocks gives the final orbit…

The proof, explained

The theorem shows that feeding the state vector (x, p, 0) through a 7-layer ReLU neural network block with integer weight parameter a ≥ 0 yields (F(x), p + a E(x), 0), where F is the compact map and E is the digit selector. The proof first establishes nonnegativity bounds for intermediate accumulator values and for F(x), allowing all internal ReLU activations to be replaced by their linear arguments. It then evaluates the network block coordinate-wise: coordinate 2 vanishes, while coordinates 0 and 1 match the ReLU representations of F(x) and p + a E(x) via straightforward ring arithmetic.

  1. The digit selector E(x), the weight parameter a, and the intermediate accumulator value p + a * max(4x - 1, 0) are all nonnegative.

    By definition, the digit selector E(x) is max 0 (min 1 (4x - 1)), so 0 ≤ E(x) follows from le_max_left. The coerced weight a is nonnegative by Nat.cast_nonneg. Since p ≥ 0, a ≥ 0, and max(4x - 1, 0) ≥ 0, their combination p + a * max(4x - 1, 0) is nonnegative by positivity.

    lines 2–4

    uses le_max_left, Nat.cast_nonneg

      have hE : 0 ≤ op75_compact_digit x := le_max_left _ _
      have hA : (0:ℝ) ≤ a := Nat.cast_nonneg _
      have hpre : 0 ≤ p + (a:ℝ) * max (4*x-1) 0 := by positivity
  2. The updated accumulator value p + a * max(4x - 1, 0) - a * max(4x - 2, 0) is nonnegative.

    Since a ≥ 0 and E(x) ≥ 0, their product a * E(x) is nonnegative by mul_nonneg. Rewriting E(x) via op75_compact_digit_relu expresses this product as a * (max(4x - 1, 0) - max(4x - 2, 0)) ≥ 0. Adding the nonnegative initial accumulator p ≥ 0 preserves nonnegativity, which nonlinear arithmetic (nlinarith) verifies.

    lines 5–8

    uses mul_nonneg, op75_compact_digit_relu

      have hpost : 0 ≤ p + (a:ℝ) * max (4*x-1) 0 - (a:ℝ)*max (4*x-2) 0 := by
        have hh := mul_nonneg hA hE
        rw [op75_compact_digit_relu] at hh
        nlinarith
  3. The compact map value F(x) is nonnegative.

    Unfolding the definition of op75_compact_map gives min 1 (min (4x) |4x - 3|). Applying le_min reduces this to showing each component is nonnegative: 0 ≤ 1 by numeric computation, 0 ≤ 4x by linear arithmetic since x ≥ 0, and 0 ≤ |4x - 3| by abs_nonneg.

    lines 9–11

    uses le_min, abs_nonneg

      have hF : 0 ≤ op75_compact_map x := by
        unfold op75_compact_map
        exact le_min (by norm_num) (le_min (by linarith [hx.1]) (abs_nonneg _))
  4. The nested ReLU expression 1 - max(1 - 4x + max(8x - 3 - max(8x - 6, 0), 0), 0) is nonnegative.

    Rewriting with the lemma op75_compact_map_relu equates this nested ReLU expression directly to op75_compact_map x for x ∈ [0, 1], which was already shown to be nonnegative.

    lines 12–14

    uses op75_compact_map_relu

      have hpos : 0 ≤ 1 - max (1-4*x + max (8*x-3 - max (8*x-6) 0) 0) 0 := by
        rw [← op75_compact_map_relu x hx]
        exact hF
  5. Evaluating the 7-layer block on (x, p, 0) coordinate-wise reduces the third coordinate to 0 and simplifies the first two coordinates to single outer ReLUs.

    Function extensionality (funext i) checks vector equality coordinate-wise across i ∈ {0, 1, 2} (fin_cases i). The simplifier evaluates the list fold over the 7 layers, expanding layer evaluation, weights, biases, and matrix-vector sums via Fin.sum_univ_three. The precomputed nonnegativity hypotheses allow inner ReLUs max(y, 0) to simplify to y via max_eq_left. Coordinate 2 simplifies completely to 0 = 0, while coordinates 0 and 1 reduce to single outer maximum expressions.

    lines 15–20

    uses Fin.sum_univ_three, max_eq_left, op75_compact_digit_relu, op75_compact_map_relu

      funext i
      fin_cases i <;>
        simp [op75_compact_block, op75_compact_layer, evalHiddenLayer, relu,
          Fin.sum_univ_three, max_eq_left hx.1, max_eq_left hp, max_eq_left hpre,
          max_eq_left hpost, max_eq_left hpos, op75_compact_digit_relu,
          op75_compact_map_relu x hx]
  6. All polynomial subexpressions in the hypotheses and remaining goals are in normal form.

    The ring normalization tactic ring_nf puts the linear and polynomial expressions in hpos, hpre, hpost, and both remaining goals into canonical form, standardizing term orders.

    line 21

      all_goals ring_nf at hpos hpre hpost ⊢
  7. The first coordinate matches F(x).

    For coordinate 0, the goal has the form max y 0 = y where y is the ReLU representation of F(x). Because 0 ≤ y was established in hpos, max_eq_left hpos immediately closes the goal.

    line 22

    uses max_eq_left

      · exact max_eq_left hpos
  8. The second coordinate matches p + a * E(x).

    For coordinate 1, the inner maximum simplifies via max_eq_left hpre. Linear arithmetic (linarith) rearranges hpost into hpost', which shows the outer maximum argument is nonnegative and simplifies via max_eq_left hpost'. Finally, ring arithmetic confirms both sides are identical.

    lines 23–26

    uses max_eq_left

      · rw [max_eq_left hpre]
        have hpost' : 0 ≤ -((a:ℝ)*max (-2+x*4) 0) + (p+(a:ℝ)*max (-1+x*4) 0) := by linarith
        rw [max_eq_left hpost']
        ring
le_max_left
In any linear order, a ≤ max a b.
Nat.cast_nonneg
The image of any natural number in an ordered semiring is nonnegative (0 ≤ (n : α)).
mul_nonneg
If a ≥ 0 and b ≥ 0, then their product satisfies a * b ≥ 0.
op75_compact_digit_relu
For any real number x, op75_compact_digit x = max (4*x - 1) 0 - max (4*x - 2) 0.
le_min
In a linear order, if c ≤ a and c ≤ b, then c ≤ min a b.
abs_nonneg
The absolute value |a| of an element in an ordered additive group is nonnegative.
op75_compact_map_relu
For x ∈ [0, 1], the compact map satisfies op75_compact_map x = 1 - max (1 - 4*x + max (8*x - 3 - max (8*x - 6) 0) 0) 0.
Fin.sum_univ_three
The sum of a function f over the 3-element finite type Fin 3 is f(0) + f(1) + f(2).
max_eq_left
If b ≤ a in a linear order, then max a b = a.

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

theorem op75_compact_block_effect (x p : ℝ) (a : ℕ) (hx : x ∈ Set.Icc 0 1) (hp : 0 ≤ p) : (op75_compact_block a).foldl (fun v layer => evalHiddenLayer layer v) ![x,p,0] = ![op75_compact_map x, p + (a : ℝ) * op75_compact_digit x, 0] := by  have hE : 0 ≤ op75_compact_digit x := le_max_left _ _  have hA : (0:ℝ) ≤ a := Nat.cast_nonneg _  have hpre : 0 ≤ p + (a:ℝ) * max (4*x-1) 0 := by positivity  have hpost : 0 ≤ p + (a:ℝ) * max (4*x-1) 0 - (a:ℝ)*max (4*x-2) 0 := by    have hh := mul_nonneg hA hE    rw [op75_compact_digit_relu] at hh    nlinarith  have hF : 0 ≤ op75_compact_map x := by    unfold op75_compact_map    exact le_min (by norm_num) (le_min (by linarith [hx.1]) (abs_nonneg _))  have hpos : 0 ≤ 1 - max (1-4*x + max (8*x-3 - max (8*x-6) 0) 0) 0 := by    rw [← op75_compact_map_relu x hx]    exact hF  funext i  fin_cases i <;>    simp [op75_compact_block, op75_compact_layer, evalHiddenLayer, relu,      Fin.sum_univ_three, max_eq_left hx.1, max_eq_left hp, max_eq_left hpre,      max_eq_left hpost, max_eq_left hpos, op75_compact_digit_relu,      op75_compact_map_relu x hx]  all_goals ring_nf at hpos hpre hpost ⊢  · exact max_eq_left hpos  · rw [max_eq_left hpre]    have hpost' : 0 ≤ -((a:ℝ)*max (-2+x*4) 0) + (p+(a:ℝ)*max (-1+x*4) 0) := by linarith    rw [max_eq_left hpost']    ring
See it in the graphDiscuss this resultChallenge it