2
$\begingroup$

I'm searching for some structure in the sign variation of the coefficients of: $P = \sum_{i>0} p^i\enspace,$ for some polynomial $p \in \mathbb{Z}\langle x\rangle$ with no constant term.

I'm interested in whether there is a simple algorithm which, given $n$, will tell me the sign of the coefficient of $x^n$ in $P$.

In other words, I'm interested in the rational power series $p^*$ for $p$ a quasiregular polynomial, and whether its $\mathbb{N}$-support is in some simple class.

A few tests using Mathematica suggest that there is a lot of structure in there. Any help? Thanks!

  • 1
    @AntonioVargas: I do mean for any $i$. This is not a concern as $p$ has no constant term, hence $p^i$ does not have terms in $x^j$, j < i.2012-05-17

1 Answers 1

0

(Edited because I had some parts of it exactly backward when I first wrote it up).

(Further edit at the bottom).

As noted in the comments, we are talking about $1/(1-p)$ (which differs from $p/(1-p)$ by a constant). So, we are talking about $1/q$, where $q$ is a polynomial with constant term 1.

Write $q(x)=\prod(1-\alpha_jx)$.

In the simplest case, one of the $\alpha_j$, call it $\alpha$, is dominant, that is, $\alpha$ is real and simple, and $|\alpha|\gt|\alpha_k|$ for all $k\ne j$. In this case, the coefficient of $x^n$ is $C\alpha^n+o(\alpha^n)$ for some nonzero constant $C$, so from some point on all coefficients have the same sign or else from some point on the coefficients alternate in sign.

The situation is the same if all the conditions on $\alpha$ given above hold, except that $\alpha$ is a multiple root. Then the coefficient of $x^n$ is $C(n)\alpha^n+o(\alpha^n)$ for some polynomial $C(n)$ of degree one less than the multiplicity of $\alpha$ in the product for $q(x)$, and again we get eventually constant sign or else eventually alternating sign.

Things are more complicated when the $\alpha_j$ of greatest modulus is a nonreal number (together with its complex conjugate). I reckon you get an almost-periodic sequence of signs for $n$ large enough.

Anyway, the people who study recurrence sequences have looked at all this and there is some literature about it, possibly under the heading "exponential polynomials".

EDIT: Some elaboration, in view of the comment.

We have $P(x)=-1+(1/q(x))$, with $q(x)=\prod(1-\alpha_jx)$. In the case where the $\alpha_i$ are all distinct, we have ${1\over q(x)}={C_1\over1-\alpha_1x}+{C_2\over1-\alpha_2x}+\cdots+{C_r\over1-\alpha_rx}$ where $r$ is the degree of $q$ and where $C_1,C_2,\dots,C_r$ are constants determined by the technique of "partial fractions", familiar from intro Calculus. Expanding each term on the right into a geometric series via ${C\over1-\alpha x}=C+C\alpha x+C\alpha^2x^2+\cdots$ we get $1/q(x)=\sum_{n=0}^{\infty}a_nx^n$ where $a_n=C_1\alpha_1^n+C_2\alpha_2^n+\cdots+C_r\alpha_r^n$ If the $\alpha_i$ are not all distinct, it's messier, but partial fractions still does the job, only you get $a_n=C_1(n)\alpha_1^n+C_2(n)\alpha_2^n+\cdots+C_s(n)\alpha_s^n$ where $\alpha_1,\alpha_2,\dots,\alpha_s$ are distinct and $C_i(n)$ are polynomials of degree one less than the multiplicity of $\alpha_i$.

In either case, if, say, $|\alpha_1|\gt|\alpha_i|$ for all $i\ne1$ then the first term is dominant, and $a_n=C_1\alpha_1^n+o(\alpha_1^n)$ or $a_n=C_1(n)\alpha_1^n+o(\alpha_1^n)$, as appropriate.

As for "almost-periodic", take an angle $\theta$, and look at the sequence of angles $0,\theta,2\theta,3\theta,\dots$, remembering that if two angles differ by a full rotation then they are really the same angle. If $\theta$ is a rational fraction of a full rotation (e.g., if $\theta$ is two-sevenths of the way around), then the sequence keeps hitting the same angles over and over again, in the same order; it is periodic. If $\theta$ is not a rational multiple of a full rotation, then you never get exactly the same angle twice, but sometimes you miss a previous angle by a tiny amount, and when that happens, it keeps happening; it's almost-periodic.

  • 0
    Thanks for the edit, Gerry, much much appreciated. By the way, I found a treatment of a similar problem (and the exponential polynomial) in "Noncommutative Rational Series with Applications" by Berstel and Reutenaueur.2012-05-18