A Boolean function's Fourier spectrum splits its "energy" across levels: $W_k[f]$ is the share of the function's variance carried by interactions among exactly $k$ input bits. How this mass spreads across levels decides how many low-order terms a learner must estimate, how noise-sensitive the function is, and how well low-degree polynomials approximate it. The general bounds are loose. Markov's inequality puts all but an $\epsilon$ fraction of the mass below degree $\mathbf{I}[f]/\epsilon$, where $\mathbf{I}[f]$ is the total influence (average sensitivity). Degree and Sensitivity: tails of two distributions improves this to $O(s\log(1/\epsilon))$, with $s$ the maximum sensitivity. That paper also shows that any bound of the form $O(s^c\log(1/\epsilon)^{d})$ with $d<1$ would settle the sensitivity conjecture. So for general functions, a sub-linear dependence on $\log(1/\epsilon)$ is out of reach.
This note proposes a regime where sub-linear dependence can be proved exactly: functions built by bounded-depth, read-once recursion from small gates, the kind of recursion that halving-guarded logics formalize. For these functions the level-weight generating polynomial of a composition is the composition of the gates' generating polynomials. The Fourier degree of the whole function is therefore distributed like the population of a family tree in which each individual has a random number of children, called a Galton–Watson process. Because the result is an iterated polynomial, where its fixed points sit and how its zeros are arranged fix the shape of its coefficient tails. The central prediction is that all but $\epsilon$ of the Fourier mass lies below degree $\mathbf{I}[f]\cdot(\log 1/\epsilon)^{1-\log m/\log d}$. Here $m$ is the gate's total influence and $d$ its fan-in. We would prove this, certify it syntactically from a logical formula, and test how far it survives when variables are read more than once.
Core Claim
Let $P_f(x)=\sum_k W_k[f]\,x^k$. For a balanced $f$ (mean zero), $P_f(\rho)$ equals the noise stability $\mathrm{Stab}_\rho[f]$: the correlation between $f(x)$ and $f(y)$ when each bit of $y$ agrees with $x$ with correlation $\rho$. Take a read-once composition $g\circ f$, in which $g$ is applied to disjoint copies of $f$. The copies' outputs on correlated inputs are then uniform bits with correlation $\mathrm{Stab}_\rho[f]$. Since two polynomials that agree on an interval are identical, this gives
$$P_{g\circ f}(x)=P_g\big(P_f(x)\big).$$
This is an elementary noise-stability calculation, and we do not claim it as new. Evaluating its derivative at $x=1$ recovers the familiar multiplicativity of total influence. Our claim is that the rest of the polynomial carries usable information. Iterating a gate $g$ with fan-in $d$ and influence $m=\mathbf{I}[g]>1$ turns the level distribution of $g^{\circ t}$ into generation $t$ of a Galton–Watson process whose offspring law is $W[g]$.
Classical tail theory for such processes (Harris-type results, not documented in the file) then predicts the following, where $c$ is the multiple of total influence at which the tail is measured and $\gamma$ is the tail exponent:
$$\sum_{k> c\,\mathbf{I}[g^{\circ t}]} W_k[g^{\circ t}] \le \exp\!\big(-\Omega(c^{\gamma})\big),\qquad \gamma=\frac{\log d}{\log d-\log m},$$
uniformly in $t$.
For recursive 3-majority, $m=3/2$ and $d=3$, so the $\epsilon$-concentration degree scales as $\mathbf{I}\cdot(\log 1/\epsilon)^{0.63}$. This is far below the Gopalan et al. bound: $s=2^t$ grows faster than $\mathbf{I}=(3/2)^t$, and their bound is also linear in $\log 1/\epsilon$. The lower tail is governed the same way by the multiplier at zero, which is $W_1[g]$ for balanced gates. Parity is the degenerate case $m=d$: the exponent on $\log(1/\epsilon)$ is $0$, and the degree becomes deterministic. Parity has no spectral spread, and it also has no composition overhead in The composition complexity of majority. We state that coincidence without claiming a causal link.
How the Four Directions Enter
Function composition is the core operation, and the relevant precedent is A composition theorem for the Fourier Entropy-Influence conjecture. O'Donnell and Tan track two scalar quantities, Fourier entropy and influence, through read-once composition. To handle inner functions whose outputs are not balanced, they pass to biased input distributions. We borrow that device. For a biased inner $f$ with mean $\mu$, the composition rule becomes $g$'s $\mu$-biased level polynomial evaluated at the renormalized correlation $(\mathrm{Stab}_\rho[f]-\mu^2)/(1-\mu^2)$. The result is a multi-type branching process, which lets us cover AND-OR trees. We differ from O'Donnell and Tan in tracking the entire level distribution rather than scalars, and in asking about concentration rather than entropy.
The level distribution alone cannot settle the Fourier Entropy-Influence conjecture, because that conjecture concerns entropy within each level. We say this plainly rather than oversell. The Saks notion of a composition limit, from Composition limits and separating examples for some boolean function complexity measures, is the right frame here: $\gamma$ is precisely such a limit for a spectral tail measure.
The direction on root location and coefficient positivity supplies the analytic lens. In the tradition of Coefficients and Roots of Peak Polynomials, where confining complex roots to a region implies positivity of coefficients, we ask which root regions force good behavior of the coefficients $W_k$. One clean fact anchors the question. If a polynomial with nonnegative coefficients has all its roots in the closed left half-plane, it factors into nonnegative factors of degree at most two. Its coefficients are then the distribution of a sum of independent variables taking values in $\{0,1,2\}$, and that sum concentrates.
A small computation shows that this route fails for majority. $P_{\mathrm{Maj}_3}(x)=\tfrac34x+\tfrac14x^3$ has roots $0$ and $\pm i\sqrt3$, but its second iterate already has a root in the right half-plane. Root regions that survive composition must therefore be looser, and identifying them is one of our questions. The motivation is practical. Branching-process theory handles identical gates, but the formulas defined below mix gates, and a region preserved under composition would give tail bounds for mixed-gate compositions directly. As in Log-concave polynomials III, the univariate real-rooted route is too fragile, which constrains our design. Unlike that paper, we do not expect complete log-concavity. The support of $W[g^{\circ t}]$ can be restricted to odd levels, so log-concavity only makes sense along the support lattice.
Resource-bounded recursion supplies both the class of functions and the syntax used to certify them. In Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth, guarded predicative recursion (GPR) requires every recursive call to at least halve its parameter, which caps recursion depth at $O(\log n)$. Its bounded variant captures $\mathrm{NC}^1$, the class of logarithmic-depth circuits built from gates with a bounded number of inputs. We define a read-once fragment of bounded GPR in which each recursive step applies a gate from a finite library to disjoint sub-domains. We then show that the formula's level polynomial is the composition of the gate polynomials along the recursion. This makes influence, noise stability, and the tail exponents readable from the syntax without evaluating the function, which is a partial answer to the file's Gap 1: no logical characterization yet tracks spectral concentration.
The arity restriction matters here. Unbounded fan-in, as in full GPR and $\mathrm{AC}^1$, corresponds to unbounded offspring, and there $\gamma\to 1$. This mirrors the $2^{O(k)}$ arity barrier in O'Donnell–Tan.
Research Program
The first thrust is theory for the read-once case. We would prove the uniform upper-tail bound for iterated balanced gates, with explicit constants obtained by a saddle-point (Chernoff) bound on $P_{g^{\circ t}}(R)$ for $R>1$. We would prove the matching lower-tail law controlled by $W_1[g]$. We would extend both to multi-type and inhomogeneous compositions, including biased gates, AND-OR trees, and a gate choice that depends on the recursion level.
The second thrust is the logic. We would state the read-once GPR fragment and the semantic lemma, and prove that fragment formulas with gate arity at most $d$ admit low-degree learning with degree cutoff $\mathbf{I}\cdot(\log 1/\epsilon)^{1/\gamma}$.
The third thrust targets read-$k$ formulas, which is where the real open problem lies. Once variables are shared, the product structure breaks, as both O'Donnell–Tan and Sharper bounds on the Fourier concentration of DNFs find. We would bound the deviation from the branching-process prediction by the correlation that shared variables introduce. We expect this to degrade gracefully when the read number is $O(1)$. That expectation could be wrong, and the experiments below would reveal it.
Baselines
The naive reference is the Markov cutoff $\mathbf{I}[f]/\epsilon$, which holds for every function and uses only the mean of the level distribution. Any structural result has to beat it by a factor that grows as $\epsilon\to 0$.
The strongest existing general bound is the Gopalan et al. cutoff $O(s\log(1/\epsilon))$ from Degree and Sensitivity: tails of two distributions. It is the right competitor because it is the sharpest file-documented degree-concentration statement, and it applies to all of our target functions. The file reports only its asymptotic form and no numerical instances, so we found no reported result on Lacuna for concrete concentration degrees on recursive majority or AND-OR trees. For a fair comparison we will compute $s$ exactly for each function and, to favor the baseline, set its hidden constant to $1$. Our result beats it if the measured $\epsilon$-concentration degree grows with an exponent of $\log(1/\epsilon)$ that is strictly below $1$ and matches $1/\gamma$.
For read-$k$ DNFs, the competitor is the Lecomte–Tan sparsity bound $s^{O(\log\log k)}$ from Sharper bounds on the Fourier concentration of DNFs. It measures a different quantity, namely the number of coefficients, so we compare implied learning sample counts rather than degrees.
The ablation that isolates the key ingredient keeps only $\mathbf{I}[g]$ and the fan-in $d$ and discards the rest of the gate polynomial. The theory predicts that the exponent $\gamma$ depends on these two quantities alone, while constants and lower tails depend on the full polynomial. We test this by swapping in different gates that share $m$ and $d$.
Why not just…?
Why not just compute the level distribution numerically for each formula? For read-once formulas, exact polynomial composition does compute every $W_k$ in time polynomial in $n$, and we use that as our ground truth. What computation does not give is a bound uniform in $n$. It also cannot certify a whole syntactic class, and it says nothing about read-$k$ formulas, where the composition identity fails.
Why not just apply Chernoff to the composed polynomial and skip the branching process? This is a real threat to the framing. For identical gates, a direct saddle-point bound may recover $\gamma$ without any probability theory. If our Chernoff constants match the branching-process prediction, we will present the Galton–Watson picture as intuition only. The substantive contributions would then be the explicit exponent, the multi-type and biased extensions, and the read-$k$ analysis.
Why not just track influence and entropy as O'Donnell and Tan do? Scalars fix the mean of the level distribution but not its tail. Recursive majority and a mixed-gate function with equal influence can have very different concentration degrees, and the ablation above is designed to show this.
Why not just use Hurwitz-stable (left half-plane) root location directly? It fails already at the second iterate of 3-majority. Part of the program is to find a root region that composition preserves, or to show that no useful one exists.
Proposed Experiments
The first experiment validates the identity by brute force. We will run exact Walsh–Hadamard transforms on read-once formulas with up to 25 variables, covering balanced gates, biased AND/OR trees, and mixed gates, and check agreement with the composed polynomials to machine precision.
The second experiment tests the asymptotics. We will compose polynomials for iterated $\mathrm{Maj}_3$, $\mathrm{Maj}_5$, AND-OR trees, and random gate libraries up to degree around $10^6$, using FFT-based composition. For $\epsilon$ from $10^{-2}$ to $10^{-12}$, we will fit the exponent of $\log(1/\epsilon)$ in the concentration degree against $1/\gamma$; for $\mathrm{Maj}_3$ the target is $0.63$. The result is decisive if the fitted exponent stays within a small tolerance of $1/\gamma$ as $t$ grows, and falsifying if it drifts toward $1$.
The third experiment probes read-$k$ robustness. We will generate read-2 and read-3 variants by duplicating leaves, and extract logic cones of at most 24 inputs from circuits in the EPFL and IWLS suites used in A Circuit Domain Generalization Framework for Efficient Logic Synthesis in Chip Design, processed with the ABC wrapper in AI4LogicSynthesis-PruneX. For each case we will measure the total-variation gap between the true level distribution and the branching-process prediction, as a function of read number. The file reports no Fourier-level figures on these benchmarks.
The fourth experiment is learning. We will run the uniform-distribution low-degree algorithm on recursive majority with $n=3^{8}$, using the Markov, Gopalan, and predicted cutoffs, with the same sample budget for each, and compare the error reached.
The fifth experiment is on roots. We will plot the zeros of $P_{g^{\circ t}}$, search computationally for sectors or regions preserved under composition within each gate library, and test log-concavity along the support lattice.
References
- Degree and Sensitivity: Tails of Two Distributions
- The Composition Complexity of Majority
- A Composition Theorem for the Fourier Entropy-Influence Conjecture
- Composition limits and separating examples for some boolean function complexity measures
- Coefficients and Roots of Peak Polynomials
- Log-concave polynomials III: Mason’s ultra-log-concavity conjecture for independent sets of matroids
- Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth
- Sharper bounds on the Fourier concentration of DNFs
- A Circuit Domain Generalization Framework for Efficient Logic Synthesis in Chip Design