recursive_nae
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
- recursive_nae_contractive_normalized_recurrence_implies_upper_boundIf a positive fixed depth b and constants 0 ≤ θ < 1 and K ≥ 0 give a recurrence u(k+b) ≤ θu(k)+K for every k, where u(k) is the exact…
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))))