AFTD Auto-Formalizing Theoretical Domains

op75_subset_encoding_length_lower

theoremverified

The number of weights is at most the bit length of the encoded instance.

Statement

lemma op75_subset_encoding_length_lower (as : List ℕ) (t : ℕ) :
    as.length ≤ (op75_subset_encoding as t).length
Source
OP-75: canonical subset-sum input decoder for the width-three ReLU compiler.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
Used by 1
  • op75_parse_subset_specThe total decoder returns a weight list and target exactly when their canonical encoding equals its input.

Lean source view module on GitHub

lemma op75_subset_encoding_length_lower (as : List ℕ) (t : ℕ) :
    as.length ≤ (op75_subset_encoding as t).length := by
  have h : as.length ≤ (as.flatMap (fun a => true :: relu_encode_nat a)).length := by
    induction as with
    | nil => simp
    | cons a as ih =>
        simp only [List.length_cons, List.flatMap_cons, List.length_append] at *
        omega
  simp only [op75_subset_encoding, List.length_append, List.length_cons, List.length_nil]
  omega
See it in the graphDiscuss this resultChallenge it