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)