18
$\begingroup$

Consider following polynomial sequence.

$$\begin{cases}a_{-1}=0,~a_0=1, \\a_{n+1}=x \cdot a_n \pm a_{n-1}\end{cases}$$

Here $+$ or $-$ is taken in such a way that all coefficients in $a_n$ do not exceed $1$ by absolute value (i.e. $\forall k \hookrightarrow |[x^k]a_n(x)|\leq 1$). The sequence seems to be infinite, but what is the strict proof of it and what are the properties of such sequence? Maybe it has unique name?

Also it seems that if we will write $0$ each time we use $-$ and $1$ each time we use $+$ in sequence $s_i$, there will be $2^{\lfloor\log_2 n\rfloor+1}$ sequences $s_i$ which generate correct $a_i$. Here is all $16$ possible patterns of first $15$ terms of $s_i$:

001011001011010 110100110100101
001011010011010 110100101100101
001101001010110 110010110101001
001101010010110 110010101101001
010010101101001 101101010010110
010010110101001 101101001010110
010100101100101 101011010011010
010100110100101 101011001011010

Can you see any pattern in here? Note that in the same row it is the sequence and same sequence reversed.

UPD: It seems that $s_0$ does not matter (since it produces $a_1=x$ in any way) and if we consider sequence $g_i$ which generates $\{s_i\}_{i=1}^{2^{n}-2}$, its prefixes can be generated as

$$\begin{cases}g_1=\varepsilon,\\g_{n+1}=g_n + (01|10) + g_n^r\end{cases}$$

where $g_n^r$ stands for reversed $g_n$.

$\endgroup$
  • $\begingroup$ What is $x$? It seems hard to decide if $|a_n|>1$ without knowing what $x$ is. $\endgroup$ – Anthony Quas Nov 3 '17 at 3:50
  • $\begingroup$ You got it wrong, $a_n$ is the polynomial from $x$. So $\forall k \hookrightarrow |[x^k]a_n(x)| \leq 1$. $\endgroup$ – Oleksandr Kulkov Nov 3 '17 at 4:10
15
$\begingroup$

Here is an algebraic formalism that seems to finish off the problem. Let ${\mathbb Z}[x]$ be the ring of integer polynomials in $x$, and let ${\mathbb Z}[x]^{\mathbb N}$ denote the ring of functions $f: {\mathbb N} \to {\mathbb Z}[x]$ that take natural numbers $n \in {\mathbb N} = \{0,1,2,\dots\}$ to polynomials. On this ring we have a shift homomorphism $T: {\mathbb Z}[x]^{\mathbb N} \to {\mathbb Z}[x]^{\mathbb N}$ defined by $Tf(n) := f(n-1)$ (with the convention that $f(n)=0$ for negative $n$). Given a sign pattern $\epsilon \in \{-1,+1\}^{\mathbb N} \subset {\mathbb Z}[x]^{\mathbb N}$, solving the recurrence $$ a(0) = 1$$ $$ a(n) = x a(n-1) + \epsilon(n) a(n-2) \hbox{ for } n \geq 1$$ (with the convention $a(n)=0$ for negative $n$) is equivalent to locating an element $a \in {\mathbb Z}[x]^{\mathbb N}$ obeying the equation $$ (1 - x T - \epsilon T^2) a = \delta$$ where $\delta \in {\mathbb Z}[x]^{\mathbb N}$ is the Kronecker delta, defined by setting $\delta(0)=1$ and $\delta(n) = 0$ for $n > 0$. This has a unique solution that we can write as $a = (1 - xT - \epsilon T^2)^{-1} \delta$, where the inverse is expanded by formal Neumann series.

We introduce the ${\mathbb Z}[x]$-linear operators $A, B_\epsilon: {\mathbb Z}[x]^{\mathbb N} \to {\mathbb Z}[x]^{\mathbb N}$ by $A := xT$ and $B_\epsilon := \epsilon T^2$, thus we are trying to find sign patterns $\epsilon$ such that $(1 - A - B_\epsilon)^{-1} \delta$ takes values in polynomials with coefficients in $\{-1,0,+1\}$.

Call a sign pattern $\epsilon \in \{-1,+1\}^N$ good if it obeys the following properties:

  1. $\epsilon(2n+2)=-\epsilon(2n+3)$ for all $n$.
  2. $\epsilon(2^m(2n+3)) = - \epsilon(2^m(2n+1))$ for all $n$ and all $m \geq 1$.

One can make a good sign pattern by the formula $\epsilon(2^m(2n+1)) = \sigma_m (-1)^n$ for all $m \geq 1$ and all $n$ with arbitrary signs $\sigma_m \in \{-1,+1\}$, and then setting $\epsilon(2n+1) = -\epsilon(2n)$ for all $n$.

The point of a good sign pattern is the following: if $\epsilon$ is good, then one has the anti-commutativity property $(A^{2^m} B_\epsilon^{2^m} + B_\epsilon^{2^m} A^{2^m}) f = 0$ whenever $m \geq 0$ and $f \in {\mathbb Z}[x]^{2^{m+1} {\mathbb N}}$ is supported on the multiples $2^{m+1} {\mathbb N}$ of ${\mathbb N}$. Indeed, this is equivalent to the identity $$ \prod_{j=1}^{2^m} \epsilon(2^{m+1} n + 2j) + \prod_{j=1}^{2^m} \epsilon(2^{m+1} n + 2^m + 2j) = 0$$ for any $n$. For $m=0$ this is exactly property 1 of a good sequence. For $m>0$ we cancel off a common factor of $\prod_{j=2^{m-1}+1}^{2^m} \epsilon(2^{m+1}+2j)$ to write the identity as $$ \prod_{j=1}^{2^{m-1}} \epsilon(2^{m+1} n + 2j) + \prod_{j=1}^{2^{m-1}} \epsilon(2^{m+1} (n+1) + 2j) = 0$$ and then observe from property 2 that $\epsilon(2^{m+1}(n+1) + 2j) = \epsilon(2^{m+1} n + 2j)$ when $1 \leq j < 2^{m-1}$ and $\epsilon(2^{m+1}(n+1)+ 2j) = -\epsilon(2^{m+1} n + 2j)$ for $j = 2^{m-1}$.

Using this anticommutativity and induction we obtain the Frobenius type identity $$ (A + B_\varepsilon)^{2^m} f = (A^{2^m} + B_\varepsilon^{2^m}) f$$ whenever $m \geq 0$ and $f \in {\mathbb Z}[x]^{2^m {\mathbb N}}$ (note that $A^{2^m}$ and $B_\varepsilon^{2^m}$ map ${\mathbb Z}[x]^{2^{m+1} {\mathbb N}}$ to ${\mathbb Z}[x]^{2^{m} {\mathbb N}}$). A similar induction then leads to the identity $$ (1-A-B_\epsilon) \prod_{i=0}^{m-1} (1 + A^{2^i} + B_\epsilon^{2^i}) f = (1 - A^{2^m} - B_\epsilon^{2^m}) f$$ whenever $m \geq 0$ and $f \in \mathbb{Z}[x]^{2^m {\mathbb N}}$, where the product is ordered from left to right, thus $$ \prod_{i=0}^{m-1} (1 + A^{2^i} + B_\epsilon^{2^i}) = (1 + A + B_\epsilon) (1 + A^2 + B_\epsilon^2) \dots (1 + A^{2^{m-1}} + B_\epsilon^{2^{m-1}}).$$ Specialising to $f=\delta$, applying $(1-A-B_\varepsilon)^{-1}$ and then sending $m$ to infinity we obtain the formula $$ (1-A-B_\epsilon)^{-1} \delta = \prod_{i=0}^{\infty} (1 + A^{2^i} + B_\epsilon^{2^i}) \delta$$ (where the product converges pointwise). One can check that every term in this pointwise product gives a different monomial located at a different point with coefficient $\pm 1$, so this indeed gives a sequence $a(n) \in {\mathbb Z}[x]$ for $n \in {\mathbb N}$ with the stated properties, with the explicit form $$ a = (1 + A + B_\epsilon) (1 + A^2 + B_\epsilon^2) (1 + A^4 + B_\epsilon^4) \dots \delta.$$

To give some sense of this formula, if we write $a$ as a sequence $a(0),a(1),a(2),\dots$, then $$ \delta = 1, 0, 0, \dots$$ $$ (1+A+B_\epsilon) \delta = 1, x, \epsilon(2), 0, \dots$$ $$ (1+A+B_\epsilon) (1+A^2+B_\epsilon^2) \delta = 1, x, \epsilon(2) + x^2, x^3, \epsilon(2)\epsilon(4) + \epsilon(2) x^2, \epsilon(2)\epsilon(4) x, \epsilon(2)\epsilon(4)\epsilon(6),0, \dots$$ and one converges to $$ a(0) = 1$$ $$ a(1) = x$$ $$ a(2) = \epsilon(2) + x^2$$ $$ a(3) = x^3$$ $$ a(4) = \epsilon(2) \epsilon(4) + \epsilon(2) x^2 + x^4 $$ $$ a(5) = \epsilon(2) \epsilon(4) x + x^5 $$ $$ a(6) = \epsilon(2)\epsilon(4) \epsilon(6) + \epsilon(6)x^4 + x^6 $$ $$ \dots$$ which is a reparameterisation of the previous solutions.

One can show that these are in fact the only sequences of polynomials $a$ that maintain their coefficients in $-1,+1$, but the proof of this uniqueness is a somewhat tedious induction and this answer is already quite long, so I'll leave it as an exercise.

$\endgroup$
9
$\begingroup$

No proofs, just experimental facts (hence cw):

Let $a_{n+1}=xa_n+\varepsilon_{n+1}a_{n-1}$, with $\varepsilon_k=\pm1$; then $\varepsilon_{2^k}$ might be arbitrary, while all others are uniquely determined by them. For the first few cases we have $$ \begin{aligned} \varepsilon_{3}&=-\varepsilon_{2}\\ \varepsilon_{5}&=-\varepsilon_{4}\\ \varepsilon_{6}&=-\varepsilon_{2}\\ \varepsilon_{7}&=\varepsilon_{2}\\ \varepsilon_{9}&=-\varepsilon_{8}\\ \varepsilon_{10}&=\varepsilon_{2}\\ \varepsilon_{11}&=-\varepsilon_{2}\\ \varepsilon_{12}&=-\varepsilon_{4}\\ \varepsilon_{13}&=\varepsilon_{4}\\ \varepsilon_{14}&=-\varepsilon_{2}\\ \varepsilon_{15}&=\varepsilon_{2}\\ \varepsilon_{17}&=-\varepsilon_{16}\\ \varepsilon_{18}&=\varepsilon_{2}\\ \varepsilon_{19}&=-\varepsilon_{2}\\ \varepsilon_{20}&=\varepsilon_{4}\\ \varepsilon_{21}&=-\varepsilon_{4}, \end{aligned} $$ the polynomials being, respectively, $$ \begin{aligned} a_1&=x \\ a_2&=x^2+\varepsilon_{2} \\ a_3&=x^3 \\ a_4&=x^4+\varepsilon_{4}x^2 +\varepsilon_{2} \varepsilon_{4} \\ a_5&=x^5+\varepsilon_{2} \varepsilon_{4}x \\ a_6&=x^6-\varepsilon_{2}x^4 -\varepsilon_{4} \\ a_7&=x^7 \\ a_8&=x^8+\varepsilon_{8}x^6 -\varepsilon_{2} \varepsilon_{8}x^4 -\varepsilon_{4} \varepsilon_{8} \\ a_9&=x^9-\varepsilon_{2} \varepsilon_{8}x^5 -\varepsilon_{4} \varepsilon_{8}x \\ a_{10}&=x^{10}+\varepsilon_{2}x^8 -\varepsilon_{8}x^4 - \varepsilon_{4} \varepsilon_{8}x^2-\varepsilon_{2}\varepsilon_{4} \varepsilon_{8} \\ a_{11}&=x^{11}-\varepsilon_{4} \varepsilon_{8}x^3 \\ a_{12}&=x^{12}-\varepsilon_{4}x^{10} -\varepsilon_{2} \varepsilon_{4}x^8 + \varepsilon_{8}x^2+\varepsilon_{2}\varepsilon_{8} \\ a_{13}&=x^{13}-\varepsilon_{2} \varepsilon_{4}x^9 +\varepsilon_{2} \varepsilon_{8}x \\ a_{14}&=x^{14}-\varepsilon_{2}x^{12} +\varepsilon_{4}x^8 - \varepsilon_{8} \\ a_{15}&=x^{15} \\ a_{16}&=x^{16}+\varepsilon_{16}x^{14} -\varepsilon_{2} \varepsilon_{16}x^{12} +\varepsilon_{4} \varepsilon_{16}x^8 -\varepsilon_{8} \varepsilon_{16} \\ a_{17}&=x^{17}-\varepsilon_{2} \varepsilon_{16}x^{13} + \varepsilon_{4} \varepsilon_{16}x^9 - \varepsilon_{8} \varepsilon_{16}x \\ a_{18}&=x^{18}+\varepsilon_{2}x^{16} -\varepsilon_{16}x^{12} +\varepsilon _{4} \varepsilon_{16}x^{10} +\varepsilon_{2}\varepsilon_{4} \varepsilon_{16}x^8 - \varepsilon_{8} \varepsilon_{16}x^2 -\varepsilon_{2} \varepsilon_{8} \varepsilon_{16} \\ a_{19}&=x^{19}+\varepsilon_{4} \varepsilon_{16}x^{11} - \varepsilon_{8} \varepsilon_{16}x^3 \\ a_{20}&=x^{20}+\varepsilon_{4}x^{18} +\varepsilon_{2} \varepsilon_{4}x^{16} +\varepsilon_{16}x^{10} +\varepsilon_{2}\varepsilon_{16}x^8 -\varepsilon_{8} \varepsilon_{16}x^4 -\varepsilon_{4}\varepsilon_{8} \varepsilon _{16}x^2 -\varepsilon_{2}\varepsilon_{4}\varepsilon_{8} \varepsilon_{16} \\ a_{21}&=x^{21}+\varepsilon_{2} \varepsilon_{4}x^{17} +\varepsilon_{2} \varepsilon_{16}x^9 - \varepsilon_{8} \varepsilon_{16}x^5- \varepsilon_{2} \varepsilon_{4} \varepsilon_{8} \varepsilon_{16}x \end{aligned} $$

$\endgroup$
  • 2
    $\begingroup$ It's also interesting that $a_{2^k-1}=x^{2^k-1}$ $\endgroup$ – Oleksandr Kulkov Nov 3 '17 at 7:55
  • 1
    $\begingroup$ Hey, that looks like A065176 ! $\endgroup$ – Oleksandr Kulkov Nov 3 '17 at 7:59
  • 2
    $\begingroup$ As to what coefficients are not zero in $a_n(x)$, note that $a_n(x)=U_n(x/2) \mod 2$, (where $U_n$ are Chebyshev polynomials of second kind), since they solve the same linear recurrence mod 2. $\endgroup$ – Pietro Majer Nov 3 '17 at 11:37
  • 2
    $\begingroup$ And the coefficients of $U_n(x/2)$ are binomial coefficients. $\endgroup$ – Pietro Majer Nov 3 '17 at 12:02
  • 3
    $\begingroup$ So $[x^r]a^n\neq0$ iff $n-r$ is even and $\big({{n+r\over 2} \atop {n-r\over 2}}\big)$ is odd, which is given by Lucas theorem (sorry, bad connection). This explains why $a_{n}=x^n$ for $n=2^k-1$: the binomial coefficients then fall into a one of those large even $\nabla$-shaped regions within the Pascal triangle $\Delta$. $\endgroup$ – Pietro Majer Nov 3 '17 at 12:39
6
$\begingroup$

More experimental facts. I think it should not be too hard prove them by induction, taking into account that we know exactly when the coefficients of $a_n$ are non-zero (see my comment to მამუკა ჯიბლაძე's answer).

Given a sequence $\epsilon_{2^n}\in\{-1,+1\}$ for $n\ge1$, let's define inductively the sequence $(\epsilon_j)_{j\ge1}$ for all positive integers according to the recurrence relations:

$$\epsilon_{2^n+1}=-\epsilon_{2^n}\qquad\text{for }n\ge1 $$

$$\epsilon_{2^n+j}=\epsilon_{2^n-j+1}\qquad\text{for }2\le j< 2^n\ ,$$

and also define

$$ \eta_j:=\begin{cases} (-1)^{ j\over 2},& \text {for even }\ j \\ \\ (-1)^{ j-1\over 2}\epsilon_{j+2}, &\text {for odd } j \ .\\ \end{cases} $$ and $$ \delta_j:=\begin{cases} -1,& \text {for }\ j=0 \\ \\ 1, &\text {for } j\neq0 \ .\\ \end{cases} $$

Then (experimentally) the polynomials $a_k= a_k(x,\epsilon_2,\epsilon_4,\dots,\epsilon_{2^n})$ are determined inductively by $a_{-1}:=0, a_0:=1$, and by the recurrence relation, for any $0\le n$ and any $0\le j< 2^n\ $

$$a_{2^n+j}=x^{2^n}b_j+ {\delta_{2^{n-1}-1-j}}\ \eta_j\ \epsilon_{2^n}\ a_{2^n-2-j},$$

where
$$b_j:=a_j(x,\epsilon_2,\epsilon_4,\dots,\epsilon_{2^{n-2}},-\epsilon_{2^{n-1}})\ .$$

For, instance the above gives $$a_{51}={x}^{51}-\epsilon_{{4}}\epsilon_{{16}}{x}^{43}+ \epsilon_{{8}} \epsilon_{{16}}{x}^{35}+ \epsilon_{{4}}\epsilon_{{32}}{x}^{11}-\epsilon_ {{8}}\epsilon_{{32}}x^3$$

$\endgroup$
  • $\begingroup$ Is there a typo in the definiton of $a_{2^n+j}$? Because the leading term must be $x^{2^n+j}$ while as it stands, degree seems to be $2^n$ only... $\endgroup$ – მამუკა ჯიბლაძე Nov 4 '17 at 15:17
  • 1
    $\begingroup$ No, sorry if it wasn't clear: $b_j$ is itself a polynomial of degree $j$, namely $a_j$ but with the sing of $\epsilon_{2^{n-1}}$ inverted. (I added the the $x$ in the notation for clarity) $\endgroup$ – Pietro Majer Nov 4 '17 at 15:39
  • 1
    $\begingroup$ Still it is complete mystery for me why the constraints completely free themselves up at each power of two precisely... $\endgroup$ – მამუკა ჯიბლაძე Nov 4 '17 at 16:22
  • 3
    $\begingroup$ If $x a_{m-1}$ and $a_{m-2}$ have a non-zero term at the same location then the sign $\pm$ in $a_m = x a_{m-1} + a_{m-2}$ is forced. Presumably one can show using Lucas's theorem that this situation occurs for all $m$ that are not powers of two. Then it should be possible to show by induction that Pietro's recipe above completely parameterises all solutions, which presumably finishes off the problem. $\endgroup$ – Terry Tao Nov 5 '17 at 0:23
  • 2
    $\begingroup$ I think it must be $a_{2^n+j}=x^{2^n}b_j+\epsilon_{2^n} \delta_j a_{2^n-\color{red}{2}-j}$ in your recursion formula. $\endgroup$ – Wolfgang Nov 5 '17 at 9:58
2
$\begingroup$

Not an answer yet but too long for a comment.

For the $a_n$ as in მამუკა ჯიბლაძე's answer, it is worth to look at even and odd indices separately. In fact, for $n$ odd, $a_n$ only seems to have terms for $x^{n-4k}$ and $[x^{n-4k}]a_n=[x^{n-4k-1}]a_{n-1}$, so all the information is contained in the even polynomials.

Writing $r$ for $\varepsilon_{2^r}$ and keeping the signs, we have the following coefficients:

$\begin{array} {rrrrrrrrrrrrrrrr} n&|&x^{n-2}&x^{n-4}&.&x^{n-8}&.&.&.&x^{n-16}\\ \hline 2&|&1\\ \hline 4&|&2&12\\ 6&|&-1&&-2\\ \hline 8&|& 3&-13&&-23\\ 10&|& 1&&-3&-23&-123\\ 12&|& -2&-12&&&3&13\\ 14&|& -1&&2&&&&-3\\ \hline 16&|& 4&-14&&24&&&&-34\\ 18&|& 1&&-4&24&124&&&-34&-134\\ 20&|& 2&12&&&4&14&&-34&-234&-1234\\ 22&|& -1&&-2&&&&-4&-34&134&&234\\ \end{array}$

Except for the signs, which keep some mystery, the patterns of the columns seem already essentially predictable, everything in terms if the A006519 sequence. If you compute some more lines, it should be entirely clear (e.g. what happens in the 5th column?), and from there of course possible to prove that by some induction.

If one adds to your list of $\varepsilon_{n}$'s the lines $\varepsilon_{2^k}=\varepsilon_{2^k}$ for completeness, then the pattern of indices 2,2,4,4,2,2,8,8,2,2,4,4,2,2,16,16... in particular also should be isomorphic to the (doubled) A006519 sequence. But the signs...? (Sadly, $\varepsilon_{22}=-\varepsilon_{2}$.)

Also note that the "main diagonal" of this table (i.e. the array of the absolute terms of the even $a_n$), taken as a binary code, seems to encapsulate a bijection $ 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, ...$ from $\mathbb N\to\mathbb N$, more precisely the Gray code A003188.

$\endgroup$
1
$\begingroup$

On the uniqueness given the data $\{\epsilon_{2^n}\}_{n\ge1}$. As observed by Terry Tao in a comment, the sign in $xa_{m-1}\pm a_{m-2}$ is forced precisely when for some $r$, one has $$[x^r](xa_{m-1})=[x^r]a_{m-2}=1\mod 2$$ (because for integers $a,b$ in $\{-1,0,1\}$ the equation $|a+\epsilon b|\le1$ has a unique solution $\epsilon$ in $\{-1,1\}$ if and only if $|a|=|b|=1$). But the parity of the coefficients of the $a_m$ is known, for $a_m=\sum_{0\le j\le{n/2}}{m-j\choose j}x^{m-2j}\mod 2$ (this follows immediately by induction from the additive formula of binomials).

Therefore, the value of $\epsilon_m$ is free if and only if $ {m-i\choose i-2}{m-i\choose i-1}$ is even for all $i\ge2$. But this is never the case if $m$ is not a power of $2$: indeed, if for some $a$ one has $2^a<m<2^{a+1}$, then $2\le i:=m-2^a+1\le 2^a$, so $m-i=2^a-1$, and both $ {m-i\choose i-2}$ and ${m-i\choose i-1}$ are odd, because all binomial coefficients ${2^a-1 \choose k}$ for $k=0,\dots,2^a-1$ are odd.

$\endgroup$

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.