op75_subset_encoding_injective
theoremverified
The binary source encoding uniquely determines the finite list of weights and the target.
Statement
theorem op75_subset_encoding_injective : Function.Injective (fun v : List ℕ × ℕ => op75_subset_encoding v.1 v.2)
- Source
- OP-75 one-pass subset-sum construction, arXiv:2610.06092; binary source encoding for a machine-level reduction.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- op75_subset_encodingThe source word encodes each nonnegative integer weight as a true marker followed by its self-delimiting natural encoding, then a false…
- relu_encode_natBinary encoding of a natural number as a self-delimiting Bool word: each base-2 digit, least significant first, is preceded by a true…
- relu_network3_encode_injectiveSanity check of the encoding: distinct width-3 ReLU networks have distinct Bool encodings.
Lean source view module on GitHub
lemma op75_encode_parts_injective890 (as bs : List ℕ) (t u : ℕ) (h : op75_subset_encoding as t = op75_subset_encoding bs u) : as = bs ∧ t = u := by induction as generalizing bs with | nil => cases bs with | nil => simp only [op75_subset_encoding, List.flatMap_nil, List.nil_append, List.cons_append, List.nil_append, List.cons.injEq, true_and] at h exact ⟨rfl, (relu_encode_nat_prefix t u [] [] (by simpa using h)).1⟩ | cons b bs => simp [op75_subset_encoding] at h | cons a as ih => cases bs with | nil => simp [op75_subset_encoding] at h | cons b bs => have hp : relu_encode_nat a ++ op75_subset_encoding as t = relu_encode_nat b ++ op75_subset_encoding bs u := by simpa only [op75_subset_encoding, List.flatMap_cons, List.cons_append, List.append_assoc, List.cons.injEq, true_and] using h obtain ⟨hab, hs⟩ := relu_encode_nat_prefix a b _ _ hp obtain ⟨has, htu⟩ := ih bs hs exact ⟨by simp [hab, has], htu⟩ theorem op75_subset_encoding_injective : Function.Injective (fun v : List ℕ × ℕ => op75_subset_encoding v.1 v.2) := by rintro ⟨as,t⟩ ⟨bs,u⟩ h obtain ⟨rfl,rfl⟩ := op75_encode_parts_injective890 as bs t u h rfl