Sharper bounds on the Fourier concentration of DNFs

In 1992 Mansour proved that every size-s DNF formula is Fourier-concentrated on$s^{O(\log\log s)}$coefficients. We improve this to$s^{O(\log\log k)}$where$k$is the read number of the DNF. Since$k$is always at most$s$, our bound matches Mansour's for all DNFs and strengthens it for small-read ones. The previous best bound for read-k DNFs was$s^{O(k^{3/2})}$. For$k$up to$\tilde{\Theta}$(log log$s$), we further improve our bound to the optimal poly$(s)$; previously no such bound was known for any$k=\omega_{s}(1)$. Our techniques involve new connections between the term structure of a DNF, viewed as a set system, and its Fourier spectrum. The full version of this paper is available at https://arxiv.org/abs/2109.04525. We strongly recommend reading the full version because it has better typesetting.