Under mild conditions on $n,p$, we give a lower bound on the number of $n$-variable balanced symmetric polynomials over finite fields $GF(p)$, where $p$ is a prime number. The existence of nonlinear balanced symmetric polynomials is an immediate corollary of this bound. Furthermore, we conjecture that $X(2^t,2^{ t+1}l-1)$ are the only nonlinear balanced elementary symmetric polynomials over GF(2), where $X(d,n)=\sum_{ i_1<i_2<...<i_d}x_{ i_1} x_{ i_2}... x_{ i_d}$, and we prove various results in support of this conjecture.
Categories: math.CO