We study the sparsity of real polynomials that sign represent parity on n variables, each of which takes values from some finite subset A of integers. While the degree of such polynomials has been well studied [15, 1], relatively little is known about their sparsity. We study this problem using Descartes Rule of Signs, a classical result in algebra, relating the sparsity of a polynomial to its number of real roots.

We show that sign representing parity over \{ 0,1 \ldots ,m - 1\} ^n with the degree in each variable at most m - 1 requires sparsity at least m^n We show a bound of (m - 1)^n for weak representations.We show that a tradeoff exists between sparsity and degree, by constructing a sign representation that has higher degree but lower sparsity. In some cases, the difference in sparsities is exponential. We show a lower bound of n(m - 2) + 1on the sparsity of polynomials of any degree representing parity over \{ 0,1, \cdots ,m - 1\} ^n. We prove exact bounds on the sparsity of such polynomials for any two element subset A

We show that for depth-two AND-OR-NOT circuits with a Threshold Gate at the top, the minimum circuit size for a function f equals the minimum sparsity of a polynomial sign representing f over a certain basis.We use this to give a simple proof that such circuits need size (3/2n) to compute parity, which improves on previous bounds [8]. We also show a tight lower bound of 2^n for the inner product function over \{ 0,1\} ^n \times \{ 0,1\} ^n.

The main technical tool used is Descartes rule of signs. Our bounds hold for various bases where Descartes sign rule is valid.