# What can be said about the asymptotics of this sequence?

This is a more general version of a question I have asked before. Let $a_1,\dots,a_r\in\mathbb C$ be algebraic numbers and suppose that for every natural number $n$ the sum $$F(n)=\sum_{j=1}^r a_j^n$$ is a non-negative integer. What can be said about the asymptotics of the sequence $F(n)$? For instance, if $a_j=Re^{2\pi ij/r}$, then $F(n)$ is zero except for the case when $n=rm$ for a natural $m$ and then $F(rm)=rR^{rm}$. But what can be said generally? Do the conditions force in that the $a_j$ may be grouped together in a way that each part satisfies the conditions of the example? Or at least the leading one does?

-
The integrality of $F(n)$ implies that the $a_j$'s are all the roots (with proper multiplicity) of an integer polynomial, and $F(n)$ is determined from the coefficients of the polynomial by Newton’s identities. This should tell you something about its asymptotics. – Emil Jeřábek Jul 4 '14 at 12:01

In general, the $a_i$s can't be grouped as in your example, but something not too dissimilar happens. I'll start with two examples when $r=2$.

Example 1. Take and $a_1,a_2$ as the roots of the equation $x^2+2x+10$: they are complex conjugate with $|a_1| = |a_2| = \sqrt{10}$.
In this case, $F(n) = (a_1^n + a_2^n)$ is twice the real part of $a_1^n$. Calling $a_n = \sqrt2\cdot e^{i\theta\pi}$, we have $F(n) = 10^{n/2+1}\cdot\cos(n\theta\pi)$. Since $\theta=\arctan(3)/\pi$ is irrational, on the interval $[1,N]$ we expect to see at least one integer $n$ for which $|\cos(n\theta\pi)|<1/N<1/n$ and at least one $n$ for which $\cos(n\theta\pi) > 1-1/n$ (roughly). It follows that we there are infinitely many $n$s for which $F(n) < 10^{n/2+1}/n$, infinitely many for which $F(n) > 10^{n/2+1}\cdot(1-1/n)$, and infinitely many for which $F(n) < -10^{n/2+1}\cdot(1-1/n)$.

Example 2. Take $a_1 > a_2$ to be the roots of $x^2-5x+2$, then $F(n)$ grows like $a_1^n$.

I would expect the generic behaviour to be similar to one of the two examples above. In general, your $a_i$s will be the set of solutions to a (monic) polynomial $P\in\mathbb{Z}[x]$; generically, the largest roots (in absolute value) of $P$ will be either a pair of conjugate complex roots or a single real root.

In the second case, the asymptotics is clear, like in Example 2 above; in the first case, one gets pretty much the same as Example 1.

To be more precise than I have been above, one should understand how small $\cos(n\theta\pi)$ can be: I would expect that generically this is never smaller than $1/n^k$ for some $k$, which would imply that the sequence $F(n)$ is asymptotically "between" $2\rho^n/n^k$ and $2\rho^n$ (up to lower order terms).

-
I would be curious to see any results on $\cos(n\theta\pi)$: this might be well-known, but I'm quite far outside my area of expertise here. – Marco Golla Jul 4 '14 at 11:04
Sorry, it seems to me that in the first example, $\theta$ is not irrational, but equals 1/4, which leads to a much more regular behavior. – Doug Jul 4 '14 at 11:54
@Corbennick: you are absolutely right. I will edit now (with a new example). – Marco Golla Jul 4 '14 at 12:17
In general, $P \in \mathbb{Z}[x]$ may have many complex-conjugate pairs of roots with maximal absolute value. In that case, even showing $|F(n)| \to \infty$ (assuming no ratio of roots is a root of unity other than $1$), is a rather delicate problem. (All known proofs use $p$-adic methods in some way.) – Vesselin Dimitrov Jul 4 '14 at 12:50
@MarcoGolla: Assuming $\cos(\theta \pi)$ algebraic (as is the case here) and $\theta$ is irrational, your guess is correct: $|\cos(n\theta\pi)| \gg n^{-k}$ for some (explicit) $k = k(\theta)$. This follows from the Gelfond-Baker theory of linear forms in logarithms of algebraic numbers. The trivial (Liouville's) lower bound is $e^{-kn}$. – Vesselin Dimitrov Jul 4 '14 at 13:32