{"id":"arxiv/2604.13493","url":"https://arxiv.org/abs/2604.13493","tags":["math.PR"],"score":0,"title":"Low-Degree Fourier Threshold for Random Boolean Functions","domain":"math.PR","source":"arxiv","authors":["Yiming Chen"],"reviews":0,"subject":"math.PR","summary":"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 + ω(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 $η\\in (0,1)$, if \\[ d \\ge \\frac{p}{2} + \\sqrt{\\frac{p}{2}\\log\\frac{6p}{η^2}}, \\] then with probability at least $1-2^{-p}$, the function $f$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-15","reactions":{}}