1
$\begingroup$

Let $a,b,c,d\in\Bbb N$ with $c<b$.

Let $N_+(a,b,c,d)$ be the number of monic polynomials $f\in \Bbb Z[x]$of degree $d$ with non-negative coefficients such that $$f(a)=b$$ $$f(0)=c$$

What is the value of $$\sum_{d=0}^tN_+(a,b,c,d)?$$

Are there sharp estimates?

$\endgroup$
1
  • $\begingroup$ This looks like something one could examine a bit with a computer. Any special cases that you have looked at? $\endgroup$ Dec 2, 2014 at 9:40

2 Answers 2

10
$\begingroup$

Not a complete answer, but note that by definition $N_+(a,b,c,d)$ is the number of ways of writing $b$ as a sum $b=\sum_{k=0}^d c_ka^k$ with non-negative $c_k$, and with $c_0=c$ and $c_d=1$. In particular it is certainly zero unless $a|(b-c)$ and $b-c\ge a^d$, in which case $N_+(a,b,c,d):=A\big(\frac{b-c-a^d}{a}\big)$, where $A(n)$ is the number of ways of writing $n$ as a sum $n=\sum_{k=0}^{d-2}x_k a^k$, with non-negative integers $x_k$, therefore corresponding to a g.f. $$\sum_{n=0}^\infty A(n)x^n=\frac{1}{(1-x)(1-x^a)(1-x^{a^2})\dots (1-x^{a^{d-2}}) }\ .$$

$\endgroup$
6
  • $\begingroup$ Is there a reference for this generating function and usage? I have not used much generating functions. $\endgroup$
    – Turbo
    Dec 2, 2014 at 16:57
  • $\begingroup$ $c_k$ instead of $x_k$? $\endgroup$
    – Turbo
    Dec 2, 2014 at 17:25
  • $\begingroup$ could you provide a short derivation? $\endgroup$
    – Turbo
    Dec 2, 2014 at 17:29
  • $\begingroup$ yes, $x_k:=c_{k-1}$. $\endgroup$ Dec 2, 2014 at 20:00
  • 1
    $\begingroup$ Short derivation: just expand each geometric series $\frac{1}{1-x^A}=1+x^A+x^{2A}+x^{3A}+x^{4A}\dots$. You can easily convince yourself that, multiplying three (or 2, or more) geometric series $\frac{1}{1-x^A}\cdot\frac{1}{1-x^B}\cdot\frac{1}{1-x^C}$ you get, as a coefficient of $x^n$, the number of nonnegative integer solutions $(X,Y,Z)$ to $n=AX+BY+CZ$. $\endgroup$ Dec 2, 2014 at 20:13
2
$\begingroup$

Really a comment on Pietro's answer: the generating function implies that the number $A(n)$ is asymptotic to a constant times $n^{d-2}$ - since the OP cares about estimates, this seems relevant to point out.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.