Searching for Regularity in Bounded Functions

07/27/2022

∙

by   Siddharth Iyer, et al.

∙

0

∙

share

Given a function f:𝔽_2^n → [-1,1], this work seeks to find a large affine subspace 𝒰 such that f, when restricted to 𝒰, has small nontrivial Fourier coefficients. We show that for any function f:𝔽_2^n → [-1,1] with Fourier degree d, there exists an affine subspace of dimension at least Ω̃(n^1/d!k^-2), wherein all of f's nontrivial Fourier coefficients become smaller than 2^-k. To complement this result, we show the existence of degree d functions with coefficients larger than 2^-dlog n when restricted to any affine subspace of dimension larger than Ω(dn^1/(d-1)). In addition, we give explicit examples of functions with analogous but weaker properties. Along the way, we provide multiple characterizations of the Fourier coefficients of functions restricted to subspaces of 𝔽_2^n that may be useful in other contexts. Finally, we highlight applications and connections of our results to parity kill number and affine dispersers/extractors.