AFTD Auto-Formalizing Theoretical Domains

relu_encode_nat

def

Binary encoding of a natural number as a self-delimiting Bool word: each base-2 digit, least significant first, is preceded by a true marker, and the word ends with false.

Statement

def relu_encode_nat (n : ℕ) : List Bool
Source
Helper encoding serving OP-75 (arXiv:2610.06092, Remark 5.15). Section 2.1 of the paper writes rational entries as pairs of integers in binary; the bit-level layout is a choice made here.
Verified
09 Nov 2026
Axioms
none listed
Used by 16
  • op75_final_encoding_templateThe final target layer encoding is a fixed prefix followed by the negative and positive target coefficient encodings.
  • op75_subset_encodingThe source word encodes each nonnegative integer weight as a true marker followed by its self-delimiting natural encoding, then a false…
  • op75_block_encoding_templateThe seven-layer block encoding is a fixed prefix, the positive coefficient encoding, a fixed middle, the negative coefficient encoding,…
  • op75_subset_encoding_length_lowerThe number of weights is at most the bit length of the encoded instance.
  • relu_encode_intEncoding of an integer as a Bool word: a sign bit followed by the binary encoding of its absolute value.
  • op75_subset_encoding_consEncoding a nonempty weight list emits its marker, the head natural, then the remaining instance.
  • op75_subset_encoding_injectiveThe binary source encoding uniquely determines the finite list of weights and the target.
  • op75_parse_nat_soundEvery successful natural parse exactly consumes the canonical encoding of its returned value and returns the correct nonzero flag.
  • relu_network3_encode_injectiveSanity check of the encoding: distinct width-3 ReLU networks have distinct Bool encodings.
  • op75_parse_subset_aux_soundEvery successful fuel-bounded parse reconstructs exactly the original canonical subset-sum word.
  • op75_parse_subset_aux_completeSufficient fuel makes the parser accept every canonical instance and return its weights and target.
  • op75_negative_rat_bit_encodingThe encoding of the negative of a nonnegative integer has sign bit set exactly when that integer is nonzero, followed by its canonical…
  • relu_encode_ratEncoding of a rational in lowest terms as a Bool word: its numerator and denominator in binary.
  • op75_parse_nat_specA successful natural parse is equivalent to the input being its canonical value encoding followed by the returned suffix, with the correct…
  • op75_positive_rat_bit_encodingThe encoding of a nonnegative integer as a rational is its nonnegative sign bit, canonical natural encoding, and denominator-one encoding.
  • op75_parse_nat_completeThe parser accepts every canonical natural encoding with an arbitrary suffix and returns the value, suffix and correct nonzero flag.

Lean source view module on GitHub

def relu_encode_nat (n : ℕ) : List Bool :=
  (Nat.digits 2 n).flatMap (fun d => [true, decide (d = 1)]) ++ [false]
See it in the graphDiscuss this resultChallenge it