22
$\begingroup$

Let's call a sequence of nonnegative integers $x_1,x_2,\ldots$ matrix-realizable, if there exists a $k\times k$ nonnegative integer matrix $A$ (for some $k$), as well as nonnegative integer vectors $u,v$, such that

$x_n = u^T A^n v$

for all $n$. (So in particular, all matrix-realizable sequences are linearly recurrent sequences; because of the nonnegative integer constraints, I don't know whether the converse holds.)

I'm interested in the possible patterns of decreases in matrix-realizable sequences. For example:

  • Is there any matrix-realizable sequence $(x_n)$ such that $x_{2n} > x_{3n+1}$ for all $n$?
  • Is there any matrix-realizable sequence $(x_n)$ such that $x_n > x_{n+1}$ whenever $n$ is composite?

In case you care about the motivation: these questions arose from a project I've been working on with Marijn Heule and Luke Schaeffer about computer-generated proofs. If the answers to the questions are "no," then it follows that there can be no computer-generated proofs of a very particular format (which we call "unary matrix proofs") for various interesting statements. In the above two examples, those statements are the Collatz Conjecture and the infinitude of primes, respectively.

$\endgroup$
  • 1
    $\begingroup$ You can't have an infinite descending sequence of non-negative integers. $\endgroup$ – Aaron Meyerowitz May 21 '17 at 19:05
  • 1
    $\begingroup$ @AaronMeyerowitz: Yes, but this on its own doesn't imply anything here, for example one could certainly have a sequence increasing at the primes and decreasing everywhere else. $\endgroup$ – Christian Remling May 21 '17 at 19:35
  • 1
    $\begingroup$ I think these are sequences with $\mathbb N$-rational generating series in the sense of Schutzenberger. See the book of Berstel and Reutenauer on rational series and formal languages for more on these. $\endgroup$ – Benjamin Steinberg May 21 '17 at 23:23
  • 1
    $\begingroup$ Silly question: How is a computer-assisted proof different from a purely computer-generated proof? $\endgroup$ – post.as.a.guest May 22 '17 at 1:48
  • $\begingroup$ Sorry, I could've just as well said "computer-generated" (of course a human needs to find a good reduction of the question to a formal one, define the search strategy, etc., and very often one needs to keep tinkering with these things until the solver works ... but the solver could still be said to be more than just an "assistant"!). I've edited the question to reflect this. Thanks. $\endgroup$ – Scott Aaronson May 22 '17 at 2:07
16
$\begingroup$

The answer is "no" for both questions.

The rational functions $a_0+a_1x+a_2x^2+\cdots$ with non-negative integer entries which can be obtained by $a_n=u^{T}A^nv$ for some nonnegative vectors $u,v$ and matrix $A$ are called $\mathbb N$-rational in the literature. Here are some slides by I. Gessel that provide a quick introduction. For a deeper treatment there is the book "Noncommutative Rational Series with Applications" by Jean Berstel and Christophe Reutenauer, especially the first 8 chapters (the rest of the book deals with noncommutative generalizations).

First, as it was mentioned by others, not only is there no $\mathbb N$ rational series satisfying the second bullet point, there is in fact no such linear recurrence relation. If we take the power series $$h(t)=(t-1)(x_0+x_1t+x_2t^2+\cdots)$$ we get a rational function with positive coefficients at every composite integer. The condition that the $x_i$ are nonnegative implies that $h$ must have infinitely many negative coefficients at a sparse set. However a theorem of Bell and Gerhold says that this is impossible (reference): the set of indices where the coefficients are negative must have positive density!

For the first bullet point I'm not sure what happens for general linear sequences, but we can restrict to $\mathbb N$-rational since these are a bit more special, and are the ones relevant to your question. A theorem of Berstel (see page 318 here, or chapter 8 of the book above), says that for such sequences there exist some $m,p\in \mathbb N$ for which the subsequences $\{x_{m+pk+i}\}_{k=1}^{\infty}$, for $i\in\{0,2,\dots,p-1\}$ are all of the form $P_i(k)\alpha_i^k +o(P_i(k)\alpha_i^k)$. Therefore each such subsequence has terms that are constant or strictly increasing. However if we take $n=qp-1$ for large enough $q$ we have $(3n+1)-(2n)=qp$, so $x_{2n},x_{3n+1}$ are in the same subsequence and therefore we can't have $x_{2n}>x_{3n+1}$.

$\endgroup$
  • $\begingroup$ Thanks for this!! There are several points that I didn't understand at first, which might be useful to spell out for others. First, if an N-rational series has a dominating root > 1, then that dominating root eventually takes over and there can be only finitely many decreases. Hence, if we need an infinite set of decreases, then there can be no such dominating root. But that's why the result of Bell and Gerhold applies, and shows that the decreases must have positive density. We don't actually need the power series h(t) for this; could just look at the series directly. (Is anything mistaken?) $\endgroup$ – Scott Aaronson May 24 '17 at 21:23
8
$\begingroup$

Such sequences are linear combinations of (complex) exponentials times polynomials $p(n)e^{\lambda n}$ (bring $A$ to Jordan normal form to see this, or use the fact you mentioned). So for large $n$, they look like $$ x_n= n^k e^{an} \sum c_j \cos (\omega_j n -\alpha_j) +o(n^ke^{an}) . $$ The quasi-periodic sequence $\sum c_j \cos(\ldots)$ is obtained by evaluating a continuous function on a torus along the orbit of a translation in that group, so if observed long enough, it will come close to all points in the closure of its range and return over and over again. Since there are arbitrarily long gaps in the primes, this is clearly incompatible with your second scenario.

$\endgroup$
  • 1
    $\begingroup$ Thanks, Christian! I had much the same intuition -- namely, that there are arbitrarily long sequences of composites, but that it seems impossible to produce arbitrarily long runs of decreases via a sum of terms of the form $p(n) \lambda^n$ while staying within the nonnegative integers, precisely because exponentials $\lambda^n$ will produce either periodic behavior or else unbounded growth. But I wasn't at all confident that such reasoning constituted a proof, and if not, how to turn it into one. $\endgroup$ – Scott Aaronson May 21 '17 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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