1
$\begingroup$

Edit Aaron solved the original question with the fourth order $$ a(n)=n2^n+\frac{(-1)^n-1^n}{2} $$ trying to make the question harder.

Let $a(n)$ be a linear recurrence with constant coefficients, of exponential growth and without fixed prime factor after the initial terms (to avoid $b^n$). The order of $a(n)$ is $r$.

Let the roots of the characteristic polynomial of $a(n)$ be $\alpha_1,\alpha_2 \ldots \alpha_k$.

Then $a(n) = \sum_{i=1}^k c_i \alpha_i^n$ where $c_i$ is algebraic number or polynomial in $n$ with algebraic coefficients.

Added Suppose no subset sum $\sum_i c_i \alpha_i^n$ vanishes.

Suppose $a(n)$ contains infinitely many $d$-th powers (I believe this is impossible for binary recurrences).

Q1 Is $d$ bounded by $O(r)$?

Q2 Is there an explicit example of $a(n)$ with $r$ small and $ d \ge 2 r$?

It is possible for all $n$, $a(n)=g(n)^d$, but in this case I believe $ d < r$.

Improve this question
$\endgroup$
6
  • $\begingroup$ I don't understand the question. What about $a(n) = b^n$ where $b$ is a $d^{th}$ power? $\endgroup$
    – Qiaochu Yuan
    Commented Jan 22, 2014 at 4:42
  • $\begingroup$ @QiaochuYuan I tried to disallow your example by not allowing fixed factor ($b$ in your case). $\endgroup$
    – joro
    Commented Jan 22, 2014 at 7:30
  • 2
    $\begingroup$ I'm sure that there is a result, but you may not have the conditions right. What about $a(n)=n2^n+\frac{(-1)^n-1^n}{2}$ which satisfies a $4$th order recurrence. This is a $2d$th power infinitely often but not for an arithmetic progression ( I think.) $\endgroup$
    – Aaron Meyerowitz
    Commented Jan 22, 2014 at 7:31
  • $\begingroup$ @AaronMeyerowitz Thanks, this answers the OP. Indeed the conditions are not right. Ideas to improve the question? For a start I suppose I want no proper subset sum of the coefficient and powers of roots of characteristic polynomial to vanish. $\endgroup$
    – joro
    Commented Jan 22, 2014 at 8:45
  • $\begingroup$ @joro: I don't understand what you mean by a fixed factor. $a(0) = 1$ here. $\endgroup$
    – Qiaochu Yuan
    Commented Jan 22, 2014 at 9:00

1 Answer 1

Reset to default
3
$\begingroup$

If your recurrence has a unique (simple) dominant root at some place (meaning one of strictly maximal absolute value; the $2$ in A.M.'s example does not count because of the multiplicity), then P. Corvaja and U. Zannier have shown that infinitely many $d$-th powers imply an identity of the form $a(qn+r) = g(n)^d$ for all $n$. See their paper "Some new applications of the Subspace theorem," Compositio Math., 2002. I can also refer you to Zannier's survey "Diophantine equations with linear recurrences: an overview of some recent progress," where this is stated as Theorem G.

In the general case, when there is no dominant root, your Q1 is still a wide open problem for all I know.

PS: I looked at your previous edits, and was surprised to see a link included to Zannier's survey. The result which you had stated in your original question would have answered everything you could ask for here, but it has only been proved under the dominant root assumption. It is surely expected to hold in greater generality - for instance, if there is some simple root $\alpha$ such that $\beta/\alpha$ is not a root of unity for any other root $\beta$; - but not in full generality, as the example $a(n) = n$ shows already. Incidentally, as you can see from this example, your addendum does not give the right condition.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks. So Q2 is not clear too? If $a(n)=0$ infinitely often, $a(n)+ C^n$ will be linear recurrence too and will be a power $C^n$ inf. often. So this construction might imply subset sum of $a(n)$ vanishes. $\endgroup$
    – joro
    Commented Jan 23, 2014 at 8:21
  • $\begingroup$ Q2: How about $a(n) = n$? [Apart from such obvious examples, however, it is expected that infinitely many $d$-th powers would yield an identity $a(qn+r)= g(n)^d$ with $g$ a linear recurrence, whence a fortiori $d \leq r$.] $\endgroup$
    – Vesselin Dimitrov
    Commented Jan 23, 2014 at 15:15
  • $\begingroup$ I think your first sentence is missing hypothesis because of the recurrence $2^n+1^n+(-1)^n$. $\endgroup$
    – joro
    Commented Mar 30, 2015 at 11:31
  • $\begingroup$ @joro: This is not a counterexample, as $2^n+1^n+(-1)^n$ is not a square for any $n$. $\endgroup$
    – Vesselin Dimitrov
    Commented Mar 30, 2015 at 16:32
  • $\begingroup$ Why do insist on square? $1^n+(-1)^n$ cancel for odd $n$, leaving $2^{2m+1}$. Appears to me these are all perfect odd powers. $\endgroup$
    – joro
    Commented Mar 30, 2015 at 17:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .