op75_compact_map_relu
On the unit interval the compact map is computed by the displayed nested rectified affine expression.
Statement
lemma op75_compact_map_relu (x : ℝ) (hx : x ∈ Set.Icc (0:ℝ) 1) :
op75_compact_map x = 1 - max (1-4*x + max (8*x-3 - max (8*x-6) 0) 0) 0- 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 1
- op75_compact_mapThe compact piecewise-affine map x ↦ min(1, 4x, |4x−3|) used in the one-pass reduction.
- Used by 1
- 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…
The proof, explained
The definition of `op75_compact_map` is unfolded into the explicit piecewise expression min 1 (min (4*x) |4*x - 3|). Totality of the order on ℝ splits the domain into two cases based on the sign of 4*x - 3, eliminating the absolute value in each case. Expanding all minima and maxima into conditional expressions turns both sides into nested piecewise linear functions, which are then completely verified across all subintervals by automated linear arithmetic using the bounds 0 ≤ x ≤ 1.
It suffices to verify the identity in two cases: when 4*x - 3 ≤ 0 and when 4*x - 3 ≥ 0.
Unfolding the definition of op75_compact_map expresses the left-hand side as min 1 (min (4*x) |4*x - 3|). By the totality of the linear order on ℝ (le_total), either 4*x - 3 ≤ 0 or 0 ≤ 4*x - 3, dividing the problem into two cases.
uses
le_totalunfold op75_compact_map rcases le_total (4*x-3) 0 with h | h
The identity holds for all x ∈ [0, 1] such that 4*x - 3 ≤ 0. automation
Since 4*x - 3 ≤ 0, the absolute value |4*x - 3| simplifies to -(4*x - 3) via abs_of_nonpos. Rewriting min and max using min_def and max_def expands both sides into nested conditional (if-then-else) expressions. Splitting all conditional branches (split_ifs) generates the piecewise linear sub-cases; linear real arithmetic (linarith), supplied with the interval bounds 0 ≤ x and x ≤ 1 from the assumption (hx), closes every branch by either identifying mutually contradictory conditions or checking that the simplified affine expressions on both sides coincide.
uses
abs_of_nonpos,min_def,max_def· rw [abs_of_nonpos h] simp only [min_def, max_def] split_ifs <;> linarith [hx.1, hx.2]
The identity holds for all x ∈ [0, 1] such that 4*x - 3 ≥ 0, completing the proof. automation
Similarly, since 0 ≤ 4*x - 3, the absolute value |4*x - 3| simplifies to 4*x - 3 via abs_of_nonneg. As in the first case, min_def and max_def expand all minima and maxima into conditional expressions. Branching over all if-then-else conditions with split_ifs yields the remaining piecewise linear sub-cases, each of which is closed by linear arithmetic (linarith) using the interval bounds 0 ≤ x and x ≤ 1.
uses
abs_of_nonneg,min_def,max_def· rw [abs_of_nonneg h] simp only [min_def, max_def] split_ifs <;> linarith [hx.1, hx.2]
le_total- In any linear order, any two elements a and b satisfy a ≤ b or b ≤ a.
abs_of_nonpos- If a ≤ 0, then |a| = -a.
abs_of_nonneg- If 0 ≤ a, then |a| = a.
min_def- The minimum min a b equals a if a ≤ b, and b otherwise.
max_def- The maximum max a b equals b if a ≤ b, and a otherwise.
- Rather than manually verifying the piecewise linear equality on each individual subinterval of [0, 1], the proof uses `split_ifs` to enumerate all conditional branch combinations and `linarith` to automatically discharge the resulting linear arithmetic goals.
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.
lemma op75_compact_map_relu (x : ℝ) (hx : x ∈ Set.Icc (0:ℝ) 1) : op75_compact_map x = 1 - max (1-4*x + max (8*x-3 - max (8*x-6) 0) 0) 0 := by unfold op75_compact_map rcases le_total (4*x-3) 0 with h | h · rw [abs_of_nonpos h] simp only [min_def, max_def] split_ifs <;> linarith [hx.1, hx.2] · rw [abs_of_nonneg h] simp only [min_def, max_def] split_ifs <;> linarith [hx.1, hx.2]