AFTD Auto-Formalizing Theoretical Domains

CubeFunc

abbrev

The type of functions from the n-dimensional Boolean hypercube {0, 1}^n into {0, 1, ..., k}, represented by Fin (k + 1).

Statement

abbrev CubeFunc (n k : ℕ) : Type
Defined in
arXiv:2611.02374, Sec. 1.2
Verified
06 Nov 2026
Axioms
none listed
Used by 6
  • cube_distThe normalized Hamming distance between two functions f, g : {0, 1}^n → {0, ..., k} is the fraction of points in {0, 1}^n where f and g…
  • is_far_from_submodularA function f is ε-far from submodular if its normalized Hamming distance to every submodular function g with the same domain and codomain…
  • is_submodular_cubeA function f from the Boolean hypercube to {0, ..., k} is submodular if f(x ∨ y) + f(x ∧ y) ≤ f(x) + f(y) for all x, y in {0, 1}^n when…
  • submod_query_tree_evalEvaluates a query decision tree on a function f by querying coordinates along the tree path until reaching a leaf.
  • all_cube_func_one_is_submodularOn the 1-dimensional Boolean hypercube, every function f : {0, 1}^1 → {0, ..., k} is submodular.
  • randomized_submod_tester_accept_probThe probability that a randomized tester accepts an input function f, given by the expected acceptance over its decision trees.

Read back from the Lean

For natural numbers n and k, CubeFunc n k is defined as the type of functions from Fin n → Bool (the $n$-dimensional Boolean hypercube $\{0, 1\}^n$) to Fin (k + 1) (the set $\{0, 1, \dots, k\}$ of cardinality $k + 1$).

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 type of functions from the n-dimensional Boolean hypercube {0, 1}^n into {0, 1, ..., k}. -/
abbrev CubeFunc (n k : ℕ) : Type := (Fin n → Bool) → Fin (k + 1)
See it in the graphDiscuss this resultChallenge it