  A real polynomial $P(X_1,..., X_n)$ sign represents $f: A^n \to \{0,1\}$ if
for every $(a_1, ..., a_n) \in A^n$, the sign of $P(a_1,...,a_n)$ equals
$(-1)^{f(a_1,...,a_n)}$. Such sign representations are well-studied in computer
science and have applications to computational complexity and computational
learning theory. In this work, we present a systematic study of tradeoffs
between degree and sparsity of sign representations through the lens of the
parity function. We attempt to prove bounds that hold for any choice of set
$A$. We show that sign representing parity over $\{0,...,m-1\}^n$ with the
degree in each variable at most $m-1$ requires sparsity at least $m^n$. We show
that a tradeoff exists between sparsity and degree, by exhibiting a sign
representation that has higher degree but lower sparsity. We show a lower bound
of $n(m -2) + 1$ on the sparsity of polynomials of any degree representing
parity over $\{0,..., m-1\}^n$. We prove exact bounds on the sparsity of such
polynomials for any two element subset $A$. The main tool used is Descartes'
Rule of Signs, a classical result in algebra, relating the sparsity of a
polynomial to its number of real roots. As an application, we use bounds on
sparsity to derive circuit lower bounds for depth-two AND-OR-NOT circuits with
a Threshold Gate at the top. We use this to give a simple proof that such
circuits need size $1.5^n$ to compute parity, which improves the previous bound
of ${4/3}^{n/2}$ due to Goldmann (1997). We show a tight lower bound of $2^n$
for the inner product function over $\{0,1\}^n \times \{0, 1\}^n$.
