Chamber geometry and specification numbers of Boolean threshold functions

Martin Anthony

cs.DMJun 28, 2026

Chamber geometry and specification numbers of Boolean threshold functions

Authors: Martin Anthony

Abstract

The specification number $σ_n(f)$ of a Boolean threshold function $f$ on $n$ variables is the least number of points whose $f$ -values determine $f$ uniquely among all threshold functions. Its essential points form the unique minimum such set. We develop Zuev's geometric interpretation: the threshold functions are the chambers of a central hyperplane arrangement in the $(n+1)$ -dimensional space of weights and thresholds, and the essential points of a function correspond exactly to the facets of its chamber, so the specification number is the chamber's facet number. The lower bound $σ_n(f)\ge n+1$ becomes the fact that a pointed full-dimensional cone has at least $n+1$ facets, with equality for simplicial chambers. The average specification number $\overlineσ_n$ becomes an average facet count. We evaluate this average exactly via the resonance arrangement and bound it through a theorem of Fukuda, Tamura, and Tokuyama, obtaining $\overlineσ_n\le 2n$ ; hence $\overlineσ_n=Θ(n)$ . This settles a question of Gutekunst, Mészáros, and Petersen. The method also extends to polynomial threshold functions. The same geometry links threshold functions with a threshold zonotope, whose vertices are modified Chow vectors. Its one-skeleton is the one-inclusion graph, and a vertex's degree is the specification number of that function. Finally, we treat the operations of Lozin et al. on functions of minimum specification number. Adding a variable and extending on a variable both take the product of a chamber closure with a half-line, preserving simpliciality. For the symmetric-variables extension we give an exact thresholdness criterion and show that minimum specification number is preserved whenever the extension is a threshold function. We also resolve a question they pose concerning a fourth operation.

Explore similar work

May 2, 2026cs.LG

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions

We introduce the Banach-Butterfly Invariant (BBT), an influence-adaptive Banach geometry on the Walsh-Hadamard butterfly factorization. For a Boolean function

f:\{-1,+1\}^n\to\{-1,+1\}

with coordinate influences

\mathrm{Inf}_\ell(f)

, BBT assigns exponent

p_\ell = 1+\mathrm{Inf}_\ell(f)

to butterfly layer

\ell

, yielding the contraction invariant

μ(f)=\prod_\ell 2^{-\mathrm{Inf}_\ell/(1+\mathrm{Inf}_\ell)}

. We prove a Jensen lower bound

\log_2μ(f) \ge -I(f)/(1+I(f)/n)

and that

μ

is strictly Schur-convex in the influence vector (modulo permutation), giving scaling classes

μ\sim 2^{-n/2}

(parity),

2^{-Θ(\sqrt{n})}

(majority),

2^{-1/2}

(dictators).

\log_2μ

is rational but not polynomial in the Fourier coefficients while

μ

is algebraic, and

μ

separates functions with identical total influence (122 pairs at

n=3

). Using the certified

n \le 4

ternary Walsh-threshold universe from a companion synthesis manuscript as a finite testbed, we compute exact MILP minimum-support certificates for all 65,536 Boolean functions at

n=4

(mean 6.42, max 9, all-odd by a parity argument) and on 10,000 of the 616,126 NPN-canonical representatives we enumerate at

n=5

(matching OEIS A000370). Conditional Spearman

ρ(μ,|\mathrm{supp}|)

at fixed total influence is

+0.571

in the largest stratum at

n=4

but reverses to

-0.38

n=5

under both function-uniform and NPN-canonical sampling:

μ

is a valid Schur-convex concentration invariant, not a universal monotone predictor of minimum support across

n

. A companion application paper validates a real-valued WHT activation-energy proxy inspired by this theory on five pretrained LLMs at W2A16, cutting wikitext-2 perplexity by 15-58% versus vanilla auto-round; the transfer from Boolean theory to the real-valued proxy is qualitative, not formal.

Gorgi Pavlov

Polynomials Binary Decision Thresholds Metric Spaces Theoretical Foundations

Ask PDF

Aug 4, 2026cs.LG

Attention-based representations for multi-task computation

Multi-head attention layers produce vector representations that support multiple downstream tasks. We establish bounds on the number of heads required in two simple and concrete multi-task scenarios. In the first scenario, a vector representation is sought so that linear predictors can compute both the smallest and largest numbers in a given list. In this case, it is known two attention heads with small embedding dimension and bit precision level suffice. We prove that a single attention head requires exponentially higher embedding dimension or precision level. In the second scenario, a vector representation is sought so that a polynomial threshold function can compute the XOR of a given string of

n

bits. This scenario is analogous to the first one for

n=2

, since XOR is readily computed by a linear function using a vector representation that encodes both the AND and the OR of the two bits. We observe that

n

-bit XOR requires the product of the number of heads and the polynomial degree to be at least

n

, and we construct multi-head attention layers that match this lower bound. These results generalize to arbitrary (symmetric) Boolean functions, where the bound is given in terms of the threshold degree.

Daniel Hsu, Mingyue Xu

Multi-Head Attention Attention-Based Methods Multi--Task Learning Multilayer Perceptrons Polynomials Representation Space

Ask PDF

Jul 23, 2026math.CO

Encoding orders and trees in real-valued functions

We prove function-theoretic analogues of a quantitative result of Hodges on extracting the order property from a sufficiently large 2-tree coded in a binary relation. Similar analogues for functions were previously obtained by Daskalakis and Golowich and by Anderson and Benedikt. These results are from statistical learning theory, where 2-trees are captured by sequential fat-shattering dimension, and the order property is controlled by various notions of "thresholds". Our first main result (Theorem 1.11) focuses on extracting a less restrictive kind of threshold from a tree, and yields significantly better bounds compared to what can be obtained from earlier results focusing on more restrictive versions. Part of the motivation for Theorem 1.11 lies in a companion paper, where this theorem is used to obtain efficient bounds in quantitative regularity lemmas for "stable functions". Here will use Theorem 1.11 to reprove a result of Anderson and Benedikt in a stronger form and with improved bounds. We also use Theorem 1.11 to prove an at most double-exponential bound on dual sequential fat-shattering, which resolves an open problem. In our second main result (Theorem 1.14), we give a new proof of a result of Daskalakis and Golowich on extracting "tight thresholds" from large sequential fat-shattering dimension, with improved bounds. This resolves another open problem related to correcting the proof of a result claimed by Jung, Kim, and Tewari.

G Conant, C Terry

Tight Bounds Order Matters Theoretical Foundations Trees

Ask PDF