Recognition: unknown
Low-Degree Fourier Threshold for Random Boolean Functions
Pith reviewed 2026-05-10 12:55 UTC · model grok-4.3
The pith
A random Boolean function on p bits is typically uniquely determined by its Fourier coefficients of degree at most d once d exceeds p/2 by an O(sqrt(p log p)) margin.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
If d is at most p/2 minus the square root of (p/2) times (log p plus omega of 1), then with probability 1 minus o(1) there exists another Boolean function g different from f that shares exactly the same coefficients of degree at most d. Conversely, for any fixed eta between 0 and 1, if d is at least p/2 plus the square root of (p/2) times log(6p over eta squared), then with probability at least 1 minus 2 to the minus p the random f is the only bounded function (even among all maps to the interval from minus 1 to 1) that matches those same low-degree coefficients.
What carries the argument
The low-degree Fourier uniqueness threshold, which is the smallest d such that the degree-at-most-d coefficients distinguish a random Boolean function from all other functions with high probability.
If this is right
- Below the lower threshold, most random Boolean functions collide with at least one other distinct Boolean function on all degree-at-most-d coefficients.
- Above the upper threshold, the low-degree coefficients uniquely identify the function even when the comparison class is enlarged to all bounded real-valued functions.
- The uncertain region between the two bounds has width O(sqrt(p log p)), so the transition is relatively sharp.
- The low-degree coefficients contain enough information to separate typical functions from one another only after d surpasses p/2 by that margin.
Where Pith is reading between the lines
- Recovery algorithms that rely solely on low-degree coefficients will succeed for random instances only once d clears the upper bound.
- The same counting-and-concentration approach could be applied to non-uniform distributions on Boolean functions, such as those with bias or noise.
- In the context of learning or testing, this pins down the minimal degree needed for identification queries on random inputs.
Load-bearing premise
The Boolean function is drawn uniformly at random from the set of all possible functions on p input bits.
What would settle it
For large fixed p, set d equal to floor(p/2) and sample many independent random Boolean functions f; the fraction of samples that possess at least one other g sharing the same degree-d coefficients should approach 1 as the lower threshold is approached and approach 0 as the upper threshold is approached.
read the original abstract
We study whether a uniformly random Boolean function $f : \{-1,1\}^p \to \{-1,1\}$ is determined by its Walsh--Fourier coefficients of degree at most $d$. We show that the threshold lies at $p/2$ up to an $O(\sqrt{p \log p})$ window: if \[ d \le \frac{p}{2} - \sqrt{\frac{p}{2}\bigl(\log p + \omega(1)\bigr)}, \] then with probability $1-o(1)$ there exists another Boolean function $g \ne f$ with the same degree-$\le d$ coefficients. Conversely, for every fixed $\eta \in (0,1)$, if \[ d \ge \frac{p}{2} + \sqrt{\frac{p}{2}\log\frac{6p}{\eta^2}}, \] then with probability at least $1-2^{-p}$, the function $f$ is uniquely determined by its degree-$\le d$ coefficients, even among all bounded functions $g : \{-1,1\}^p \to [-1,1]$. This resolves a question of Vershynin.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper establishes a sharp threshold result for the uniqueness of a uniformly random Boolean function f:{-1,1}^p → {-1,1} from its degree-≤d Walsh-Fourier coefficients. It proves that if d ≤ p/2 - sqrt((p/2)(log p + ω(1))), then with probability 1-o(1) there exists g ≠ f with identical low-degree coefficients; conversely, for any fixed η∈(0,1), if d ≥ p/2 + sqrt((p/2) log(6p/η²)), then with probability at least 1-2^{-p} the function f is the unique bounded function (to [-1,1]) sharing those coefficients. The threshold is located at p/2 with an O(sqrt(p log p)) window, resolving a question of Vershynin.
Significance. The result supplies a precise, explicit-constant characterization of the information carried by low-degree Fourier coefficients for random Boolean functions. The lower bound follows from binomial tail estimates on the degree distribution together with a union bound; the upper bound uses a net-plus-energy argument controlling the orthogonal complement. Both directions are parameter-free in the leading terms and yield concrete probability bounds, which is a strength. The work advances the understanding of Fourier analysis on the hypercube for random functions and may inform learning theory and property testing.
minor comments (2)
- In the statement of the upper bound, the dependence on η is explicit but the transition from Boolean to bounded functions could be highlighted more clearly in the introduction to emphasize the strengthening.
- The covering-number estimate for the unit ball in the high-degree subspace (used in the uniqueness argument) is standard but its precise constant factors are not displayed; adding a short display of the entropy integral or covering bound would improve readability.
Simulated Author's Rebuttal
We thank the referee for their positive report, accurate summary of our results, and recommendation to accept the manuscript. We appreciate the recognition of the explicit constants and probability bounds in both directions of the threshold.
Circularity Check
No significant circularity; derivation is direct probabilistic analysis
full rationale
The paper derives the low-degree Fourier threshold for random Boolean functions via binomial tail bounds on the degree distribution under the uniform measure, followed by a union bound for the non-uniqueness direction and a net-plus-energy argument for uniqueness among bounded functions. These steps rely on standard concentration inequalities and covering numbers of the unit ball in the orthogonal complement, without any parameter fitting, self-referential definitions, or load-bearing self-citations that reduce the claimed O(sqrt(p log p)) window to a quantity defined by the result itself. The threshold statements are obtained as explicit consequences of the tail estimates and do not presuppose the final uniqueness or existence claims.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math The Walsh-Fourier characters form an orthonormal basis for functions on the hypercube.
- domain assumption Uniform random Boolean functions are drawn from the product measure on {-1,1}^p.
Reference graph
Works this paper leans on
-
[1]
Onk-wise independent distributions and Boolean functions
Itai Benjamini, Ori Gurel-Gurevich, and Ron Peled. Onk-wise independent distributions and Boolean functions. arXiv preprint arXiv:1201.3261, 2012. doi:10.48550/arXiv.1201.3261
-
[2]
On the characterization of threshold functions
Chao-Kong Chow. On the characterization of threshold functions. InProceedings of the Second Annual Sympo- sium on Switching Circuit Theory and Logical Design, pages 34–38, 1961. doi:10.1109/FOCS.1961.24
-
[3]
Ilias Diakonikolas and Daniel M. Kane. Degree-dChow parameters robustly determine degree-dpoly- nomial threshold functions (and algorithmic applications).arXiv preprint arXiv:1811.03491, 2018. doi:10.48550/arXiv.1811.03491
-
[4]
Probability inequalities for sums of bounded random variables
Wassily Hoeffding. Probability inequalities for sums of bounded random variables.Journal of the American Statistical Association, 58(301):13–30, 1963. doi:10.1080/01621459.1963.10500830
-
[5]
Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications.SIAM Journal on Computing, 22(4):838–856, 1993. doi:10.1137/0222053
-
[6]
Ryan O’Donnell.Analysis of Boolean Functions. Cambridge University Press, Cambridge, 2014. doi:10.1017/CBO9781139814782
-
[7]
Ryan O’Donnell and Rocco A. Servedio. The Chow parameters problem.SIAM Journal on Computing, 40(1):165–199, 2011. doi:10.1137/090756466
-
[8]
Are most Boolean functions determined by low frequencies?arXiv preprint arXiv:2401.13143,
Roman Vershynin. Are most Boolean functions determined by low frequencies?arXiv preprint arXiv:2401.13143,
-
[9]
8 YIMING CHEN School of Mathematical Sciences, Peking University Email address:ymchenmath@math.pku.edu.cn
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.