# An exotic sequence

Let $a=\frac{1+i\sqrt 7}{2}$ and $u_n=\Re(a^n)$ show that $(|u_n|)\to +\infty$

I think basics method does not works here.

Any ideas ?

-

This isn't really a calculus problem because it amounts to a subtle question about how close a multiple of $\tan^{-1} \sqrt 7$ can get to an odd multiple of $\pi/2$. Robert Israel already explained why one expects that $|u_n|$ should grow faster than $n^{-\mu} 2^{n/2}$ for some constant $\mu$, which is much more than enough to prove the desired $|u_n| \rightarrow \infty$; and achille lui applied the "heavy sledgehammer" of Baker and Wüstholz to prove this for some explicit $\mu$. Here we give a much simpler approach that yields a result that, though much weaker than the sledgehammer, is still sufficient to prove that $|u_n| \rightarrow \infty$.

It was already noted that $u_n = (a^n + b^n) / 2$ where $b = 1-a$ is the complex conjugate of $a$, and thus that the $u_n$ are half-integers satisfying the recurrence $u_{n+2} = u_{n+1} - 2 u_n$. (The odd integers $2u_n$ are OEIS sequence A002249.) Thus $|u_n| \rightarrow \infty$ if and only if for every integer $m$ there are only finitely many solutions $n$ of $2u_n = m$. We shall show that every $m$ occurs at most once except for $1 = u_1 = u_4$ and $-5 = u_3 = u_9$.

The technique is basically what's known as "Skolem's $p$-adic method", which immediately gives a uniform upper bound on the number of solutions of $2u_n = m$; after some experimentation I was able to reduce this bound to $1$ (with the exception of the two solutions for each of $m=1$ and $m=-5$).

We start with some elementary observations. First, $2u_n \bmod 7$ has period $3$ with remainders $1,4,2,1,4,2,\ldots$, so if $u_n = u_{n'}$ then $n' \equiv n \bmod 3$. (This happened for $\{n,n'\} = \{1,4\}$ and $\{3,9\}$.) Likewise, $2u_n \bmod 16$ becomes periodic of period $4$ after the first three terms: $1, -3, -5$, and then then $1, -5, -7, 3, 1, -5, -7, 3,\ldots$. Thus $2u_2=-3$ never recurs, and if $u_n=u_{n'}$ with neither $n$ or $n'$ equal $1$ or $3$ then $n' \equiv n \bmod 4$, whence $n' \equiv n \bmod 12$ because we already knew the congruence mod $3$.

Assume henceforth that $n,n' \geq 4$, so $n' \equiv n \bmod 12$. Then we claim $n' \equiv n \bmod 84$. Indeed for each of the primes $p=29$ and $p=43$ we have $2u_{n+84} \equiv 2u_n \bmod p$ for all $n$, because in each case $-7$ is a square mod $p$ (so $a,b \bmod p$ can be identified with elements of $({\bf Z}/p{\bf Z})^*$) and $p-1$ is a factor of $84$. So it is enough to check that none of the $12$ subsequences $$\{ 2u_n,\, 2u_{n+12},\, 2u_{n+24},\, 2u_{n+36},\, 2u_{n+48},\, 2u_{n+60},\, 2u_{n+72} \} \bmod 29 \cdot 43$$ with $1 \leq n \leq 12$ contains a repeat, and this turns out to be the case. (The odds were in our favor: for $12$ random septuplets mod $29 \cdot 43$ the probability of success is over $90\%$, and by using $n \bmod 12$ we removed the known coincidences $u_1=u_4$ and $u_3=u_9$.)

Now for $p=29$ or $p=43$ each of $a^{84} \bmod p$ and $b^{84} \bmod p$ can be written as $1+pc$, $1+pd$ for some algebraic integers $c,d$. It follows by induction on $k$ that $a^{84p^k}$ and $b^{84p^k}$ are congruent to $1 + p^{k+1} c$ and $1 + p^{k+1} d \bmod p^{k+2}$. We thus find, for each $n_0 = 1, 2, \ldots, 84$, some $e_{n_0} \bmod p$ such that $$2u_{n_0+84p^k t} \equiv 2u_{n_0} + p^{k+1} e_{n_0} t \bmod p^{k+2}$$ for all integers $t$. So if $e_{n_0}$ is not zero mod $p$ then there are no repeats in the sequence $\{u_n \mid n \equiv n_0 \bmod 84\}$: if $n \neq n'$ then $n-n'$ has some finite $p$-valuation $k$, and $2u_n$ is congruent to $2u_{n'} \bmod p^{k+1}$ but not mod $p^{k+2}$. If some $e_{n_0}$ does vanish mod $p$ then we can try congruences mod $p^{k+3}$, $p^{k+4}$, etc. But it turns out that this is not necessary: we have two choices of $p$, and while there are some $n_0 \leq 84$ for which $e_{n_0} \equiv 0 \bmod p$ for one of $p=29$ and $p=43$, there is none for which both $e_{n_0} \bmod p$ vanish. (Again the odds were in our favor: a random $84$-tuple mod $29\cdot 43$ has no zero entries with probability $>93\%$.)

This completes the proof that the sequence $\{u_n \mid n \geq 4\}$ has no repeats, and thus establishes our claim that $|u_n| \rightarrow \infty$ as $n \rightarrow \infty$, QED.

-
In fact I haven't understand the answer by Robert Israel. And when I saw achille hui's answer, I thought that Robert Israel's answer is just a explanation more than a proof. Thanks for your answer, I have to work on it to fully understand. –  Free X Mar 17 '14 at 9:59

No idea if this will help but could not resist posting these striking images. Try plotting the absolute value of the real part of $a^n/2^{n/2}$ for $0\le n\le1000$.

Addendum. Even better, change the plot style to "point" so that you don't have lines joining successive points.

-

I'm sure there is a more elementary method than the heavy sledgehammer I used here.
Since I only know this one, here is the sledgehammer.

Let $\displaystyle c = \frac{1+i\sqrt{7}}{2}$, we are going to prove $\Re(c^k) \to \infty$ as $k \to \infty$.
Consider the sequence $(c_k)_{k\in\mathbb{N}}$ where $c_k = 2\Re(c^k) = \left(\frac{1+i\sqrt{7}}{2}\right)^k + \left(\frac{1-i\sqrt{7}}{2}\right)^k$.
It is easy to check it satisfies a linear recurrence relation of the form

$$c_{k+2} = c_{k+1} - 2c_{k}$$

Since $c_0 = 2$ and $c_1 = 1$, this means for all $k > 0$, $c_k$ is an odd integer and hence $\Re(c^k) \ne 0$.

Let $\mathbb{A}$ be the set of algebraic numbers, there is something general we can say about any $c \in \mathbb{A}$ such that $|c| > 1$ and $\Re(c^k) \ne 0$ for all $k > 0$. For any $a$ in $\mathbb{A}$, let $H(a)$ be its naive height. Let us split $c$ as

$$c = |c| a\quad\text{ with }\quad |c| \in \mathbb{A}\quad\text{ and }\quad a \in \mathbb{A}\setminus\mathbb{R}, |a| = 1$$

Now $\Re(c^k) \ne 0$ for all $k > 0$ implies $a^k \ne i$ or $-i$ for all $k > 0$. This implies for any $b_1, b_2 \in \mathbb{Z}$, not both zero, the linear form of logarithm:

$$L(b_1,b_2) = b_1 \log(a) + b_2 \log(i) \ne 0$$

In 1993, Baker and Wüstholz has proved following theorem$\color{blue}{^{[1],[2]}}$:

For any $a_1, \ldots, a_n$ in $\mathbb{A}$, let $L : \mathbb{Z}^n \to \mathbb{C}$ be the linear form of logarithm $$L(b_1,\ldots,b_n) = b_1 \log(a_1) + \cdots + b_n \log(a_n)$$ $L$ is either $0$ for some non trivial $(b_1,\ldots,b_n)$ or bounded away from $0$ by $$|L| > \exp\left[ -(16nd)^{2n+4} \log(A_1) \cdots \log(A_n) \log(B) \right]$$ where $d = [\mathbb{Q}(a_1,\ldots,a_n) : \mathbb{Q}]$, $A_i = \max( H(a_i), e )$ and $B = \max( |b_1|, \ldots, |b_n|, e )$.

If we apply this theorem to our linear form, we get $| b_1 \log(a) + b_2 \log(i) | > B^{-\mu}$ for some constant $\mu$. This implies for large $k$,

$$| a^k \pm i | > ( \text{constant}\cdot k)^{-\mu} \quad\implies\quad| \Re( c^k ) | > ( \text{constant}\cdot k)^{-\mu} |c|^k$$ As a result, $| \Re( c^k ) | \to \infty$ as $k \to \infty$.

Notes

• $\color{blue}{[1]}$ A. Baker and G. Wüstholz, Logarithmic forms and group varieties, J. Reine Angew. Math. 442 (1993) 19-62
• $\color{blue}{[2]}$ This is theorem 2.15 in A. Baker and G. Wüstholz's book Logarithmic Forms and Diophantine Geometry.
-
"I'm sure there is a more elementary method than the heavy sledgehammer I used here." I wouldn't be so sure. In fact I highly doubt there is a more elementary method (see Robert Israel's answer). –  C-S Mar 18 '14 at 23:09
@Goos, we know a lot about sequence like $2 u_n$. It is a special case of Lucas sequence of second type. We know after at most the first 30 terms, each $2 u_n$ will contain a primitive prime divisor. The first result along this line (for Frobenius sequence) is available in 1920s???. If we can prove such a strong result 100 years ago. It is sort of hard to believe there isn't an elementary method for this much weaker statement. –  achille hui Mar 19 '14 at 1:29
I think the last line should be $|\arg a^k \pm i\pi/2| > (\textrm{constant}\cdot k)^{-\mu}$. –  i707107 Oct 8 '14 at 6:02
@i707107 the last line is correct. what you say is essentially the part $| b_1 \log(a) + b_2 \log(i) | > B^{-\mu}$ which is one step away from last line. –  achille hui Oct 8 '14 at 8:35
I see. The last line is essentially from $\sin x \sim x$, right?. –  i707107 Oct 8 '14 at 15:18

Write $a = r e^{i\theta}$ where $r = \sqrt{2}$ and $\theta = \arctan(\sqrt{7})$. The question is whether for any $N$ there exist infinitely many $n$ such that $|2^{n/2} \cos(n \theta)| < N$.
This can be viewed as a question about whether $2\theta/\pi$ has extremely good rational approximations. Namely, if $$\left| \dfrac{2\theta}{\pi} - \dfrac{m}{n} \right| < \dfrac{2 N}{\pi n} 2^{-n/2}$$ for some odd integer $m$, then we would have $$|\cos(n \theta)| < \left| n \theta - m \pi/2 \right| < N 2^{-n/2}$$ Now almost surely it doesn't, in fact for any $\epsilon > 0$ and almost every real $x$ there are only finitely many pairs of positive integers $(m,n)$ such that $|x - m/n| < 1/(n^2 \log(n)^{1+\epsilon}$. But there are some irrational numbers $x$ that do have extremely good rational approximations (in fact these contain a dense $G_\delta$ subset of $\mathbb R$). As far as I know there is no way to prove that $2 \arctan(\sqrt{7})/\pi$ is not one of those numbers.

-
So this exercise it's harder than it looks..Anyway, it's an interesting idea (+1). –  user119228 Mar 10 '14 at 0:33
Unfortunately I don't understand what have you proved here ? Could you please explain a little more ? –  Free X Mar 17 '14 at 9:51
This is the correct way to look at the problem, but with regards to "As far as I know there is no way to prove..." it seems that achillehui's answer does indeed prove this. –  C-S Mar 18 '14 at 23:08
Correction: "As far as I knew when I wrote that, ..." –  Robert Israel Mar 19 '14 at 3:26
That number $2\arctan(\sqrt 7 )/\pi$ is an irrational number. –  i707107 Oct 7 '14 at 17:28

Here are a couple of ideas - though I think the problem may be harder than it looks.

Let $a=r(\cos \theta+i\sin \theta)$ so that $a^n=r^n (\cos n\theta+i\sin n\theta)$ and $u_n=r^n \cos n\theta$.

You will find that $r=\sqrt 2$ and $\theta = \arctan \sqrt 7$. This shows that the general growth is like $(\sqrt 2)^n$ but you have to bound the trigonometric bit sufficiently away from zero to avoid "too many" values which are "too small".

Let $b=\bar a$ then $u_n=\Re (a^n) = \cfrac {a^n+b^n}{2}$

Now $a+b=1$ and $ab=2$ so that $a$ and $b$ are roots of $x^2-x+2=0$ and hence of $$f_n(x)=x^{n+2}-x^{n+1}+2x^n=0$$ whence $$\frac {f_n(a)+f_n(b)}{2}=u_{n+2}-u_{n+1}+2u_n=0$$ so that $u_{n+2}=u_{n+1}-2u_n$

This gives a convenient way of calculating $u_n$, but shows that if it is growing it will regularly change sign (as we expect from the trigonometric formulation) and the absolute value is not monotone increasing.

Perhaps someone knows a trick which makes this easier.

-
The limit formulation $$\lim_{n\to\infty}2^{n/2}\cos(n\tan^{-1}(\sqrt 7))$$ is quite interesting. I am almost certain there is a theorem about that, but it seems challenging from first principles. –  Ian Mar 9 '14 at 22:30