AFTD Auto-Formalizing Theoretical Domains

recursive_nae

def

The k-th recursive block composition F_k = NAE₃^{∘ k} of the ternary not-all-equal Boolean function on 3^k bits.

Statement

def recursive_nae : (k : ℕ) → (Fin (3 ^ k) → Bool) → Bool
Defined in
arXiv:2611.16412 Section 5
Verified
13 Nov 2026
Axioms
none listed
Built on 1
  • ternary_naeThe ternary not-all-equal Boolean function NAE₃ on 3 bits, which outputs 0 on 000 and 111 and 1 otherwise.
Used by 1

Read back from the Lean

The function recursive_nae recursively defines a Boolean function on inputs of length 3^k (represented as Fin (3 ^ k) → Bool for k : ℕ): - For k = 0: it returns x ⟨0, _⟩, the value of the single input bit. - For k + 1: it splits the input x : Fin (3 ^ (k + 1)) → Bool into three blocks of size 3^k via the canonical equivalence split : Fin (3 ^ (k + 1)) ≃ Fin 3 × Fin (3 ^ k) (formed by composing the equivalence from 3 * 3^k = 3^(k+1) with the inverse product equivalence Fin (3 * 3^k) ≃ Fin 3 × Fin (3^k)), recursively evaluates recursive_nae k on each of the three blocks, and returns the result of ternary_nae applied to the three resulting Boolean values.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The k-th recursive block composition of NAE₃ on 3^k bits. -/
def recursive_nae : (k : ℕ) → (Fin (3 ^ k) → Bool) → Bool
| 0 => fun x => x ⟨0, by decide⟩
| k + 1 => fun x =>
  have h : 3 * 3 ^ k = 3 ^ (k + 1) := by ring
  let split : Fin (3 ^ (k + 1)) ≃ Fin 3 × Fin (3 ^ k) :=
    (finCongr h).symm.trans finProdFinEquiv.symm
  ternary_nae (fun i => recursive_nae k (fun j => x (split.symm (i, j))))
See it in the graphDiscuss this resultChallenge it