3
$\begingroup$

A paper I am reading says that a sequence satisfying a linear recurrence grows either polynomially or exponentially. Is this easy to see?

  • 3
    Hard to know, it is a vague statement. Certainly it is false unless we put some conditions on, like linear recurrence with **constant** coefficients. Even with constant coefficients, we would need to worry about examples like $a_{n+2}=2a_n$, $a_1=1$, $a_2=0$, where we have $1$, $0$, $2$, $0$, $4$, $0$, and so on. Certainly with constant coefficients there is an exponential upper bound.2011-09-22
  • 0
    Assuming constant coefficients, many "garden variety sequences" do satisfy this property; so I can imagine saying such a statement *informally*. But if we attempt to make a formal claim, we run into the objections raised by @André. Can you give a reference to the paper or quote the relevant lines directly so that we get the full context?2011-09-22
  • 0
    It says exactly what I say . But it is not much related to the results of the paper. I just saw it and was curious. Probably the authors were not careful enough at this point.2011-09-22
  • 0
    Is there a link to the paper?2011-09-22
  • 0
    http://u.math.biu.ac.il/~amirgi/papers/amenability_final.pdf look at the bottom of page 6.2011-09-22
  • 0
    I think the authors mean something like this: "polynomial growth" with degree $d$ (a nonnegative integer) would say $\lim \sup_{n \to \infty} |a_n| n^{-d}$ is a nonzero constant; "exponential growth" would say $\lim \sup_{n \to \infty} |a_n| n^{-d} e^{-kn}$ is a nonzero constant for some nonnegative integer $d$ and positive real $k$. There can't be "exponential decay" in their case because their $a_n$ is always a nonnegative integer (it is counting something). I haven't checked whether values of 0 are possible in their application: I don't know what they would call it if $a_n = 0$ eventually.2011-09-22
  • 0
    My guess is that the paper wants an upper bound on the activity growth, rather than a tight upper+lower bound. Specifically, the quantity "number of length-$n$ words $v$ such that the section $a(v)$ is not the identity" is either $O(n^{d})$ for some $d$ (in which case, the degree is defined to be the smallest such $d$; conveniently, it's an integer), or it is not (in which case the degree is defined to be $\infty$). If we care only about the upper bound, and not a tight bound, the current objections (e.g., sequence could be periodic/oscillating and so on) are no longer applicable.2011-09-22
  • 0
    If $a_n$ is zero for some $n$ then it is zero for all higher $n$. The paper is mainly concerned with linear activity growth.2011-09-24

2 Answers 2