# $\sum_{k=0}^{100} a_k x^{k}=0, a_i \in \mathbb{Z}$ How many equations?

Let $x^{100}+a_{99} x^{99}+a_{98} x^{98}+ \dots +a_{1}x +a_{0}=0, \ \ a_{100}=1, a_i \in \mathbb{Z}$, is an algebraic equation with integer coefficients.

Assume that all (100 with multiplicity) roots are positive real numbers: $0 < x_1\leq x_2\leq x_3 \leq x_4 \leq \dots \leq x_{99} \leq x_{100} < m, \ \ m \in \mathbb{N}$.

The question is: How many such different equations are there for the interval (0, m)?

Update. Maybe I found solution for the case when $x^2+a_1 x+a_2=0, a_1,a_2 \in \mathbb{Z}$. If $0\leq x_1\leq x_2<m$, from $(x-x_1)(x-x_2) = x^2+a_1 x+a_2$ we have a system $x_1 x_2 =a_2; x_1+x_2=-a_1,$ $2m<a_1<0, \ \ 0<a_2<m^2$. So we have $\binom{m+2}{3}=\frac{m(m+1)(m+2)}{6}$ different equations.

Update: Complete answer in case m=3 will be also helpfull. And will be awarded.

-
For most coefficients there will be no multiplicity – Lior B-S Feb 27 '13 at 8:41
The sign of the coefficients changes less than 5 times. So, such equations are not possible. – Ishan Banerjee Feb 27 '13 at 8:59
Applying your idea that $a_i$ can be expressed as a (symmetric) polynomial in the roots, one gets $0 < (-1)^i a_i < \binom{n}{i} m^i$. So you can at least give an upper bound for the number of degree $100$ integer polynomials with roots in $[0,m]$. – Joel Cohen Feb 27 '13 at 13:11
Are you sure you didn't miss a condition? If so, note that the coefficients must satisfy Newton's inequalities as well, and that isn't even sufficient. See math.ucv.ro/~niculescu/articles/2000/NewtonIneq.pdf and jstor.org/discover/10.2307/… – Ivan Loh Feb 28 '13 at 0:43
This is sort of the reverse of the usual "is it homework?" comment. In this case it already says homework. So: for what course? Or: what material was just before this in the textbook? – GEdgar Mar 3 '13 at 13:12

Denote the number of quadratic equations with $x_j\in(0,m)$ by $N(m)$. If you think about the standard solution to a quadratic $x^2+cx+d=0$ where $c$ and $d$ are integers, the midpoint between the two roots will be at $-c/2$, so we'll only want to consider cases where $$-m/2\lt c\lt0$$ (otherwise the roots will be too far apart; the strict bounds follow because we're working on an open interval). From the conditions that $$0\lt \frac{-c-\sqrt{c^2-4d}}{2},\frac{-c+\sqrt{c^2-4d}}{2}\lt m$$ we can solve for $d$ to give the bounds $-(m^2+mc)\lt d\lt0$. Notice that this already contains the condition that the roots are real (though not necessarily distinct). Now in order to count the number of solutions, let $\#d(c,m)$ denote the number of permissible values of $d$ for a given value of $c$ (and $m$, of course). Now we can take $$d=-1,...,-(m^2+mc)+1,$$, which is $(m^2+mc)-1$ choices, so $\#d(c,m)=(m^2+mc)-1$. Hence $$N(m)=\sum_{-\lfloor \frac{m}{2}\rfloor\leq c\leq -1}{\#d(c,m)}$$ (i.e. we're summing over the different possibilities for $c$), and since for an arithmetic series $$a+(a+1)+...+(a+n)=\frac{n(2a+n+1)}{2},$$ we can write $$N(m) = \sum_{-\lfloor \frac{m}{2}\rfloor\leq c\leq -1}{(m^2+mc-1)}=\lfloor \frac{m}{2}\rfloor(m^2-1)+m \sum_{c=-(m-1)}^{-1}{c},$$ or $$N(m)=(m^2-1)\lfloor \frac{m}{2}\rfloor-m\sum_{c=1}^{\lfloor \frac{m}{2}\rfloor}{c}=(m^2-1)\lfloor \frac{m}{2}\rfloor-\frac{m}{2}\lfloor \frac{m}{2}\rfloor(\lfloor \frac{m}{2}\rfloor+1).$$ Now given this explicit form of $N(m)$, we can choose equations to make up the original (with replacement, because you allowed repetition). There are $N(m)^{50}$ ways of doing this, and we're done (the order of the roots doesn't really matter; there exists some order of course, but we don't need to make it explicit for the counting argument). This expression is not terribly elegant of course, you could clean it up slightly by treating odd and even $m$ separately etc.
Edit: I've been a bit hasty in jumping to conclusions with this, apologies. This could be seen as a lower bound, given that the true number would have to be an expression involving the number of irreducible polynomials of every degree $\leq 100$ for every possible partition of $100$, but maybe even that's wrong - it's be necessary to prove that the number of equations is finite (which I've obviously assumed, but perhaps that requires proof). I'm not entirely sure where to take this, but it might be useful to consider the Samuelson-Laguerre inequality http://en.wikipedia.org/wiki/Samuelson%27s_inequality because it allows you to bound the roots.
"The problem can be reduced to finding the number of solutions for a quadratic" - I disagree. Consider the following quartic, with 4 positive real roots, and is irreducible over $Z[x]$: $x^4-20x^3+134x^2-326x+154$. The roots are approximately $0.613269, 5.07846, 5.83697, 8.4713$. – Ivan Loh Mar 7 '13 at 2:09
True, that was a bit naive of me... still, I wonder if it's possible to count irreducible polynomials over the integers subject to $x_i\in (0,m)$ (though no doubt the answer would explode in size for even small $m$). – Ben Z Mar 7 '13 at 15:23