In this paper we give a new upper bound on the minimal degree of a nonzero Fourier coefficient in any non-linear symmetric Boolean function. Specifically, we prove that for every non-linear and symmetric f:{0,1}^k -> {0,1} there exists a nonempty set S such that |S|=O(\Gamma(n) + \sqrt{n}), and the Fourier coefficient f^(S) is not zero, where \Gamma(m)\le m^{0.525} is the largest gap between consecutive prime numbers in {1,...,m}.

As an application we obtain a new analysis of the PAC learning algorithm for symmetric juntas, under the uniform distribution, of Mossel et al. (STOC '03). In particular, for k \ge log(n)^{1/(1-0.525)} =~ log(n)^{2.1} our analysis matches known lower bounds (up to a polynomial overhead).

Our bound on the degree greatly improves the previous result of Kolountzakis et al. (Combinatorica '09) who showed that |S|=O(k/log k).

This is a joint work with Avishay Tal.