# Counting polynomials with same coefficient sum and a given value at a point

Call an univariate polynomial $f(x) = \sum_{i=0}^{n}a_{i}x^{i} \in \Bbb{Z}[x]$ symmetric if $a_{i} = a_{n-i}$ and $a_{0} = a_{n} > 0$.

For a given $\sum_{i=0}^{n}a_{i}$ and $a_{i} \geq 0$, how many symmetric polynomials $f(x) = \sum_{i=0}^{n}a_{i}x^{i}$ over $\Bbb{Z}[x]$ are there such that for two fixed integers $r,s$ $f(r)=s$? (two cases: first case - the degree $n$ is same for both the polynomials and second case - the degree $n$ may be different for both the polynomials)

Are there more than one such polynomials (if one exists)?

How does one construct any such polynomial?

-
Is $f(x)=x^2$ a symmetric polynomial? (I.e., do you really want to allow $a_n=0$?) –  Barry Cipra Jul 3 '13 at 22:38
Note that, since you are insisting on nonnegative integer coefficients, you won't get any nonconstant polynomial if $r\ge s$, even before you fix the sum of the coefficients. More generally, it looks like it can be rephrased as a subset sum problem, maybe with extra conditions, and these can be computationally infeasible. –  Gerry Myerson Jul 3 '13 at 23:45
Try $f(x)=x^8+3x^7+x^6+3x^5+2x^4+3x^3+x^2+3x+1$ --- but your polynomial isn't symmetric! –  Gerry Myerson Jul 4 '13 at 10:11
Notice that $3\times3^2+3\times3^0=10\times3^1$. It follows that if $a\ge3$ then the symmetric polynomials $x^4+ax^3+bx^2+ax+1$ and $x^4+(a-3)x^3+(b+10)x^2+(a-3)x+1$ have the same value at $x=3$. If $a$ is large, then iterating this construction will give you arbitrarily many 4th degree symmetric polynomials with the same value at $x=3$. And similar tricks will work for other degrees, other coefficients, and other arguments. –  Gerry Myerson Jul 4 '13 at 12:51
The title does not mention symmetric but the question itself does. The title and your comment suggest a third fixed integer $t$ and the added requirement $f(1)=t$. This is not mentioned in the body of your question. Any motivation for these conditions? –  Aaron Meyerowitz Jul 4 '13 at 18:30

The polynomials $f_1=x^4+9x^3+9x+1$ and $f_2=3x^4+14x^2+3$ both have coefficient sum $f_1(1)=f_2(1)=20$ and the common value $f_1(2)=f_2(2)=107.$ The key is that the difference $f2-f1=g=2x^4-9x^3+14x^2-9x+2$ is symmetric with $g(1)=g(2)=0.$ we could take $f_2=f_1+g$ for any symmetric degree $4$ polynomial with large enough positive coefficients. We can also multiply both $f_1$ and $f_2$ by any symmetric integer polynomial.

In general If $f_1(x)$ and $f_2(x)$ have

• equal degree
• equal value $f_1(r)=f_2(r)=s$ and
• equal coefficient sum $f_1(1)=f_2(1)$
• positive coefficients

then the difference $g(x)=f_2(x)-f_1(x)$ will have $g(r)=g(1)=0$. Once we have a suitable $g(x)$ we can build many eamples $f_1,f_2$

So

• start with a symmetric polynomial having a root $r \ne 0$ say $rx^2-(r^2+1)x+r$
• multiply that by $x^2-2x+1$ to get a symmetric polynomial, in this case $g(x)=r{x}^{4}- \left( {r}^{2}+2\,r+1 \right) {x}^{3}+ \left( 2\,{r}^{2}+2 \,r+2 \right) {x}^{2}- \left( {r}^{2}+2\,r+1 \right) x+r,$ where $g(r)=0$ and also $g(1)=0$ (i.e. the coeffixcients add to $0$).
• Now pick another symmetric polynomial $f_1(x)$ of the same degree with positive coefficients and set $s=f_1(r)$.

Then $f_1$ and $f_2=f_1+g$ will have the first three properties above and will have the fourth property provided the coefficients of $f_1$ are large enough.

If you relax the conditions slightly, then the $g$ above gives $f_1=9x^3+9x$ and $f_2=2x^4+14x^2+2$ with unequal degrees, coefficient sum $18$, and $f_1(2)=f_2(2)=90.$

This does not give an example with unequal degrees yet both with non-zero constant term.

This seems like cheating, but would you consider the polynomials $f_1=x^2+2x+1$ and $f_2=4$ an example with $f(-3)=4$ in both cases? In general $r=-b-1$ and $s=b+2$ for $f_1=x^2+bx+1$ and $f_2=b+2$

It looks less trivial if we, as mentioned above, multiply both sides by $x+1$ or some other symmetric polynomial to get things like $f_1=x^3+3x^2+3x+1$ and $f_2=4x+4$ both with $f(-3)=-8.$

-

What you're asking for is related to the classic Frobenius Problem. Let me illustrate with the example you and Gerry Myerson discussed in comments.

In looking for symmetric polynomials of degree $8$ with non-negative coefficients summing to $\sigma$ (which we'll set shortly to $18$, so that Gerry's polynomial is a solution) for which $f(r)=s$ (soon to be set to $r=3$, $s=14842$), we must have $a(r^8+1)+b(r^7+r)+c(r^6+r^2)+d(r^5+r^3)+er^4=s$ with $2(a+b+c+d)+e=\sigma$. This can be rewritten as

$$a(r^8-2r^4+1)+b(r^7-2r^4+r^3)+c(r^6-2r^4+r^2)+d(r^5-2r^4+r^3)=s-\sigma r^4.$$

Now plugging in $r=3$, $s=14842$ and $\sigma=18$ (and removing what turns out to be a common factor of 4) produces

$$1600a+507b+144c+27d=3346$$

to be solved in non-negative integers $a$, $b$, $c$, and $d$ (after which one must also check that $e=18-2(a+b+c+d)$ is also non-negative). You can check that Gerry's coefficients, $(1,3,1,3)$, satisfy this equation. I'll leave it to someone else to find the rest.

Note that changing $s$ simply changes the number on the right hand side whose sum as a combination of "coins" of value $1600$, $507$, $144$, and $27$ is sought. (To be precise, $s$ can only change by multiples of $4$ in this example.) The Frobenius problem looks for the largest number that cannot be so represented, which in general seems to be difficult to decide. It's possible that the special form of the numbers here (all of the form $r^m-2r^{n/2}+r^{n-m}$) allows for a Frobenius miracle, but if they do I don't see how. Maybe someone with more knowledge of the Frobenius problem can comment or answer with greater authority.

-