Linear system of equations with nonnegative solutions and a recursion rule

Question

My question derives from reading a recent preprint (arXiv:1209.0827v1, in particular Section 4.1), but it can be phrased quite independently from that paper. The setup is as follows.

Let $A$ be the tridiagonal $n\times n$ matrix with $a_{ii} = -1$ on the main diagonal and $a_{i,i+1} = a_{i+1,i} = 2$ on the other two diagonals. We take the $n\times 1$ vector 1 (consisting of only 1's) as a right-hand side and look for the solution to the linear system of equations. It is not difficult to show that the determinant of the matrix is always an odd integer, the system has a unique solution for each $n$.

Question (asked by the authors). Are there infinitely many $n$ such that all entries of the solution vector are positive?

This would be interesting because each such $n$ gives rise to a solution with a particular property of a toy model for the energy transfer in a nonlinear Schrödinger equation.

---

Out of curiosity, I did a numerical search for solutions up to $n \sim 1000$ and got the following list of valid $n$ for which the solution is indeed nonnegative.

2, 3, 4, 8, 13, 18, 23, 42, 61, 80, 142, 204, 347, 490, 633, 776, 919, ...

I noticed the following for the sequence of consecutive differences, which starts with

1, 1, 4, 5, 5, 5, 19, 19, 19, 62, 62, 143, 143, 143, 143, 143...

Observation. This sequence seems to have the property that each entry is either the previous entry or it is the previous entry multiplied by the number of times the previous entry has appeared in the sequence in total (4 has appeared once, 5 has appeared three times) plus the biggest element that is strictly smaller. We do see that indeed $19 = 3\cdot5+4$, $62 = 3\cdot19+5$ and $143 = 2\cdot62+19$. Furthermore, each element bigger than 1 in the sequence of differences seems to be one larger than an element in the sequence of valid $n$.

One can now use the rule to create much larger matrices and check whether they have the property and this seems to work just fine, though I am not sure up to which size Mathematica as used by a numerical layman is trustworthy.

My question. Does the sequence of differences really observe this rule? Assuming it does, does it create all $n$ with the desired property? What decides whether the next term in the sequence of differences is identical to its predecessor or the sum of previous terms?

I am fairly confident that all of this is well-known (there seems to be a sort of construction algorithm behind it) and would be thankful for any references.

Answer 1

Yes there are infinitely many such values of $n$ and the sequence satisfies the rule you observed. The proof is straightforward but technical.

Let $x_1,\dots,x_n$ be the solution. Add $x_0=0$ and $x_{n+1}=0$, then $2x_{k-1}-x_k+x_{k+1}=1$ for all $k=1,\dots,n$. Introduce $y_k=3x_k-1$, then $y_k$ satisfies a linear recurrence relation $$ 2y_{k-1}-y_k+2y_{k+1}=0 $$ and boundary conditions $y_0=y_{n+1}=-1$. And we are looking for solutions satisfying $y_k\ge -1$.

Solving the recurrence by the standard method yields that $$ y_k = A\sin(k\alpha)+B\cos(k\alpha) $$ for some constants $A$ and $B$, where $\alpha=\arccos\frac14$. (This number comes from the fact that the roots of the equation $2x^2-x+2=0$ are $\cos\alpha\pm i\sin\alpha$).

Since $y_0=-1$, we have $B=-1$. Then $y_k=-1$ if and only if $$ A = A_k := \frac{\cos(k\alpha)-1}{\sin(k\alpha)} = -\tan(k\alpha/2) $$ So for the solution with $y_{n+1}=-1$ we have $A=A_{n+1}$, and the relation $y_k\ge-1$ takes the form $$ \begin{cases} A_k \ge A_{n+1}, & A_{n+1}<0 \\ A_k \le A_{n+1}, & A_{n+1}>0 \end{cases} $$ (note that $\tan(k\alpha/2)$ and $\sin(k\alpha)$ are of the same sign).

So $n$ is included in the sequence iff $A_{n+1}$ is either the minimum of the positive $A_k$'s, or the maximum of the negative $A_k$'s ($k=1,\dots,n+1$). Observe that the order of $-A_k$'s in $\mathbb R$ is the same as of the numbers $k\alpha\bmod 2\pi$ in $(-\pi,\pi)$. So everything boils down to the study of the sequence $\alpha_k:=k\alpha\bmod 2\pi\in(-\pi,\pi)$. A number $n$ is included in the sequence iff $\alpha_{n+1}$ is the best approximation to 0 among entries of the same sign seen so far. Let's add 1 to all these $n$, so we can consider $\alpha_n$ rather than $\alpha_{n+1}$. The indices of the best approximations are $$ 1(+), 3(-),4(-),5(+),9(-),14(-),19(-),24(+),43(+),\dots $$ where the signs indicate whether the approximation is positive or negative. The rule for the best approximations is well-known (and easy to prove): the next index is the sum of the latest "positive" one and the latest "negative" one. For example, $19=5+14$, $24=5+19$, $43=24+19$. In other words, the last "positive" entry keeps adding itself to "negative" entries until a new "positive" one appears. Since $\alpha/\pi$ is irrational, zeroes do not happen. The sequence is infinite because the set $\{\alpha_k\}$ is dense in $(-\pi,\pi)$.

Which entries are "positive" depends on number-theoretical properties of the number $\alpha/2\pi$. More precisely, how many "positive"/"negative" ones follow in a row is determined by the expansion of this number into a continued fraction. In our case, this expansion should be aperiodic because the number is probably not a quadratic irrational. (I believe it is transcendental but I am not sure).