POLYNOMIALS WITH 2 VALUES

This paper investigates the minimal degree of polynomials f is an elem ent of R[x] that take exactly two values on a given range of integers {0, ..., n}. We show that the gap, defined as n - deg(f), is O(n(.548) ). The maximal gap for n less than or equal to 128 is 3. As an applica tion, we obtain a bound on the Fourier degree of symmetric Boolean fun ctions.