MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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).

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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