21
$\begingroup$

I have been studying the sequence $$\{n\sqrt{2}\}$$ where $\{x\}:= x-\lfloor x\rfloor$ is the "fractional part" function. I am particularly interested in the values of $n$ for which $\{n\sqrt{2}\}$ has an extremely small value - that is, when $n\sqrt 2$ is extremely close to (but greater than) its nearest integer. Of course, for integer $n$, this always takes on values between (but never including) $0$ and $1$.

I have defined the sequence $M_n$ as follows:

  • $M_1=1$
  • $M_{n+1}$ is the smallest positive integer such that $\{M_{n+1}\sqrt 2\}\lt \{M_n\sqrt 2\}$

The first few terms of this sequence are $$1,3,5,17,29,99,169,...$$ And after a quick trip to the OEIS, I have found that this sequence is equal to OEIS entry A079496, as written in the comments. It also provides the recurrence $$a_0=a_1=1$$ $$a_{2n+1}=2a_{2n}-a_{2n-1}$$ $$a_{2n}=4a_{2n-1}-a_{2n-2}$$ How can I prove that the sequence $M_n$ satisfies this recurrence, using the definition I wrote for $M_n$?

Thanks!

EDIT: Here is the closed-form explicit formula for $a_n$, for anyone who wants to know: $$a_{2n}=\frac{(3+2\sqrt 2)^n+(3-2\sqrt 2)^n}{2}$$ $$a_{2n+1}=\frac{(1+\sqrt 2)(3+2\sqrt 2)^n-(1-\sqrt 2)(3-2\sqrt 2)^n}{2\sqrt 2}$$

$\endgroup$
  • $\begingroup$ Have you taken a look to the references on the link you shared? I mean, the comment of Paul. D Hanna there says that this is exactly what you're looking for... $\endgroup$ – Alejandro Nasif Salum Dec 15 '17 at 23:54
  • $\begingroup$ I mean... you want to know if this recurrence is valid for your sequence or you are sure of it and you are just trying to prove it? $\endgroup$ – Alejandro Nasif Salum Dec 15 '17 at 23:55
  • 1
    $\begingroup$ Yeah, that confuses me as well. I'll add the closed form to the question, for anyone who is curious. $\endgroup$ – Franklin Pezzuti Dyer Dec 16 '17 at 0:02
  • 2
    $\begingroup$ According to Kroneckers Approximation Theorem $\{n\sqrt{2}\}$ is dense in $[0,1]$. $\endgroup$ – rtybase Dec 16 '17 at 0:39
  • 1
    $\begingroup$ This can be seen as two interleaved sequences with the recursion $q_n=6q_{n-1}-q_{n-2}$ $\endgroup$ – robjohn Dec 17 '17 at 1:30
1
+150
$\begingroup$

Summary of solution : the originality of your question consists in its use of the floor function to round, when most of the classical results on continued fractions use the nearest integer function. The idea is to reduce the former to the latter.

Details : Let $M_n,a_n$ be as in the OP. Our goal is to show that

$$ M_n=a_n \tag{1} $$

As a convenience, let us use the "normalized" number $\alpha=\sqrt{2}-1$ (which is in the unit interval) rather than $\sqrt{2}$ itself.

It will suffice to show :

$$ \lbrace q\alpha \rbrace \geq \lbrace a_n\alpha \rbrace \textrm{ for } 0 \lt q \lt a_{n+1} \tag{2} $$

We will use a sequence closely related to the continued fraction expansion of $\alpha$, namely $g_n=\frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}}$. Note that $(g_n)$ satisfies $g_0=0,g_1=1$ and $g_{n+2}-2g_{n+1}+g_n=0$, so its values (after $g_1$) are positive integers. The following properties are easy to show by a direct computation or by induction :

$(i)$ $g_ng_{n+2}-g_{n+1}^2=(-1)^{n+1}$

$(ii)$ $a_n=g_n$ when $n$ is odd

$(iii)$ $a_n=g_{n+1}-g_n$ when $n$ is even

$(iv)$ $\frac{g_n-g_{n+1}\alpha}{g_{n+1}-g_{n+2}\alpha}=1-\sqrt{2}$

$(v)$ $\frac{a_{n+2}\alpha -(g_{n+2}-g_{n+1})}{a_n\alpha -(g_n-g_{n-1})}=3-2\sqrt{2}$, when $n$ is even.

The following lemma is a very classic continued fraction inequality :

LEMMA. Let $p,q$ be integers with $0 \lt q \lt g_{n+2}$. Then $|p-q\alpha| \geq |g_n-g_{n+1}\alpha|$. Further, if $(p,q)\neq (g_n,g_{n+1})$, the inequality can be strenghtened to $|p-q\alpha| \geq |g_n-g_{n+1}\alpha|+|g_{n+1}-g_{n+2}\alpha|$.

Proof of lemma. By (i), the matrix $\left(\begin{matrix} g_n & g_{n+1} \\ g_{n+1} & g_{n+2} \end{matrix}\right)$ is unimodular. It follows that there are integers $u,v$ such that $p=g_n u+g_{n+1}v$ and $q=g_{n+1}u+g_{n+2}v$. I claim that $uv\leq 0$ ; otherwise, $g_{n+1}u$ and $g_{n+2}v$ would both be nonzero and have the same sign, forcing $|q| = |g_{n+1}u|+|g_{n+2}v| \geq |g_{n+2}|$ which is impossible. So $uv\leq 0$, and also

$$ p-q\alpha= u(g_n-g_{n+1}\alpha) + v (g_{n+1}-g_{n+2}\alpha) \tag{3} $$

The numbers $u(g_n-g_{n+1}\alpha)$ and $v(g_{n+1}-g_{n+2}\alpha)$ have the same sign, so

$$ |p-q\alpha|= |u(g_n-g_{n+1}\alpha)| + |v (g_{n+1}-g_{n+2}\alpha)| \tag{4} $$

Note that $u\neq 0$ because of $q=g_{n+1}u+g_{n+2}v$ and $|q|<g_{n+2}$. So $|u|\geq 1$ and the first inequality follows. If equality holds, we must have $|u|=1$ and $v=0$, from which we easily deduce $(p,q)=(g_n,g_{n+1})$. Suppose now that $(p,q)\neq (g_n,g_{n+1})$. If $|u|\geq 2$, then from (4) we deduce $|p-q\alpha| \geq 2|g_n-g_{n+1}\alpha|$. By (iv), the second inequality holds in this case.

Otherwise $u=1$ and from the reasoning above we have $v\neq 0$, so $|v|\geq 1$ and from (4) again we deduce $|p-q\alpha| \geq |g_n-g_{n+1}\alpha|+|g_{n+1}-g_{n+2}\alpha|$, which finishes the proof of the lemma.

Let us now deduce (2) from the lemma. Suppose first that $n$ is odd. By $(ii)$, $\lbrace a_n\alpha \rbrace=\lbrace g_n\alpha \rbrace=g_{n+1}\alpha-g_n$ by lemma, (iv) and the fact that $g_{n+1}\alpha-g_n >0$. The lemma also shows that $\lbrace q \alpha \rbrace \geq \lbrace a_n \alpha \rbrace$ for $0 \lt q \lt g_{n+2}=a_{n+2}$, as wished.

Suppose now that $n$ is even. Using the lemma with $n-1$ in place of $n$, we have that for any $0 \lt q \lt g_{n+1}=a_{n+1}$ and $(p,q)\neq (g_{n-1},g_n)$, then $$\begin{array}{lcl} |p-q\alpha| &\geq& |g_{n-1}-g_{n}\alpha|+|g_{n}-g_{n+1}\alpha| \\ &=& g_{n-1}-g_{n}\alpha+g_{n+1}\alpha-g_n \\ &=& a_n\alpha -(g_n-g_{n-1}) \\ &=& \lbrace a_n \alpha \rbrace \textrm{ by } (v) \end{array}$$

This finishes the proof.

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

This is about Pell type equations. Absolutely complete detail would be a bit long. I have posted many times about solving $x^2 - n y^2 = T,$ where $T$ is some target number, and $n$ is positive not a square.

Your sequence is this: given positive integer $x,$ let $v = \lfloor x \sqrt 2 \rfloor.$ Your numbers will be $$ 2 x^2 - v^2 \in \{ 1,2 \}. $$

Furthermore, the ratios of consecutive terms are bounded: if $w$ is a number with worse $2 w^2 - w_0^2,$ where $w_0 = \lfloor w \sqrt 2 \rfloor,$ then there is one of your numbers $t$ with $t > w/(2 + \sqrt 2).$

Alright, the positive values of $2x^2 - y^2$ are $1,2,4,7,8,9, 14 \ldots$ where we are allowing common factors of $x,y.$

If $2x^2 - v^2 = 4,$ then both $x,v$ are even, we can take $t = x/2,$ and the fractional part of $t \sqrt 2$ is half the fractional part of $x \sqrt 2,$ meaning $x$ cannot be part of your $M$ sequence. Now that I think of it, the same applies to any number divisible by $4$ or by $9.$ As a result, if we calculated $2x^2 - v^2 = 7$ as a special case (we know how to find all representations) we could then continue with $2 x^2 - v^2 \geq 14.$

It appears we need just the one special case. After this, we may take $$ 2 x^2 - v^2 \geq 7, $$ with $$ \{ x \sqrt 2 \} \geq \frac{7}{x \sqrt 2 + v} \approx \frac{7}{2x \sqrt 2 }\approx \frac{2.4748737}{x } . $$ $$ t > \frac{x}{2 + \sqrt 2}, $$ $$ 2 t^2 - w^2 \in \{ 1,2 \}. $$ $$ (t \sqrt 2 - w)(t \sqrt 2 + w) \leq 2. $$ $$ t \sqrt 2 - w \leq \frac{2}{t \sqrt 2 + w}. $$ $$ \{ t \sqrt 2 \} \leq \frac{2}{t \sqrt 2 + w} \approx \frac{2}{2t \sqrt 2 } \approx \frac{1}{t \sqrt 2 } < \frac{2 + \sqrt 2}{x \sqrt 2 } = \frac{1 + \sqrt 2}{x } \approx \frac{2.1421356}{x } . $$ This is smaller than $$ \{ x \sqrt 2 \} \geq \frac{7}{x \sqrt 2 + v} \approx \frac{7}{2x \sqrt 2 }\approx \frac{2.4748737}{x } . $$

A more careful analysis is possible, correction terms all over, but the heart of it is the observation that the floor of $t \sqrt 2$ is extremely close to the real number itself, when $0 < 2t^2 - w^2 \leq 2$.

Here is the Conway topograph for the negative of your form, $x^2 - 2 y^2.$ Your numbers show up representing negative number, (4,3) gives $-2$, then (7,5) gives $-1,$ then (24,17) give $-2,$ (41,29) gives $-1$

Let's see, it will take an hour or so, but I can draw a topograph for $2x^2 - v^2$ that shows numbers represented up to $17,$ as numbers such as $4,8,9$ are not squarefree, and are not primitively represented (we get $\gcd(x,v) \neq 1$). Will, 9:19 Pacific time

Done. Note that the green coordinate pairs have a motion that gives the same value of $2x^2 - y^2,$ namely $$ (x,y) \mapsto (3x+2y, 4x+3y). $$ For example, $ (1,1) \mapsto (5, 7 ) $ and $ (3,4) \mapsto (17, 24 ). $

Let's see, Cayley Hamilton for the coefficient matrix $$ \left( \begin{array}{cc} 3 & 2 \\ 4 & 3 \end{array} \right) $$ gives the linear recurrence, $$x_{n+4} = 6 x_{n+2} - x_n $$ if we combine the $x$ values in a single list. We need to separate odd index and even index because we are combining $2x^2-v^2 = 1$ and $2x^2 - v^2 = 2$ in one list of $x$ values enter image description here

There is a book that Allen Hatcher makes available online, here is his diagram for $x^2 - 2 y^2,$ but without the green coordinates that I like to include. The topograph diagram was introduced by J. H. Conway

enter image description here

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

Continued Fraction Approximations

The continued fraction for $\sqrt2$ is $$ \sqrt2=1+\cfrac1{2+\cfrac1{2+\cfrac1{2+\dots}}}\tag1 $$ The approximants alternate between a bit too high and a bit too low, but we always have $$ \left|\,\frac{p_n}{q_n}-\sqrt2\,\right|\le\frac1{2q_n^2}\tag2 $$ because of the continued fraction, we have $$ p_n=2p_{n-1}+p_{n-2}\quad\text{and}\quad q_n=2q_{n-1}+q_{n-2}\tag3 $$ starting with $\frac11$ (low) and $\frac32$ (high). The first several continued fraction approximants are $$ \frac11,\frac32,\frac75,\frac{17}{12},\frac{41}{29},\frac{99}{70},\dots\tag4 $$


Low Approximations

We want to choose the approximations that are a bit low so that $q_n\sqrt2\gt p_n$. Then $$ \left\{q_n\sqrt2\right\}=q_n\sqrt2-p_n\le\frac1{2q_n}\tag5 $$ Since we only want the low approximations, we need to modify the recursion in $(3)$ to skip the high approximations. To that end, we have $$ p_n=6p_{n-2}-p_{n-4}\quad\text{and}\quad q_n=6q_{n-2}-q_{n-4}\tag6 $$ starting with $\frac11$ and $\frac75$. The first several low continued fraction approximations are $$ \frac11,\frac75,\frac{41}{29},\frac{239}{169},\frac{1393}{985},\dots\tag7 $$ We can also make some close low approximations by looking at twice the reciprocals of the high approximations. These will follow the recursion in $(6)$: $$ \frac43,\frac{24}{17},\frac{140}{99},\frac{816}{577},\dots\tag8 $$ The denominators of these two sequences, which follow the recursion in $(6)$, cover all of the elements of the sequences in the question.


Combined Sequence

The combined sequence follows the recursion $$ a_n=6a_{n-2}-a_{n-4} $$ and starts out $$ 1,3,5,17,\dots $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This was my immediate idea too. But it looks like this produces only every other term in the OP's sequence. $\endgroup$ – hmakholm left over Monica Dec 16 '17 at 22:59
  • $\begingroup$ Their sequence seems to include all the continued fraction approximants, even the high ones. The high ones will give $\left\{q_n\sqrt2\right\}$ just less than $1$. Or perhaps my list misses some close, but not continued fraction approximations. Only continued fraction approximations satisfy $(2)$. I will look when I get back home. $\endgroup$ – robjohn Dec 16 '17 at 23:05
  • $\begingroup$ I suspect the additional terms are because leaving out the low approximants leave room for additional multiples of $\sqrt2$ to have a smallest-yet fractional part even though there have been earlier multiples (corresponding to the high approximants) that approached an integer closer from below. $\endgroup$ – hmakholm left over Monica Dec 16 '17 at 23:30
  • $\begingroup$ @HenningMakholm: I figured out where the other terms in the question came from. $\endgroup$ – robjohn Dec 17 '17 at 0:57
  • $\begingroup$ If $x \in (\frac{2}{3},\frac{3}{4})$, then $\lbrace x \rbrace \gt \frac{1}{2} \gt \lbrace 2x \rbrace$, so $2x$ is a record in the sense of the OP, but not a best approximation situation in the classical sense. Here in the special case where $x=\sqrt{2}$ we are lucky that all the records in the sense of the OP come from best approximations. $\endgroup$ – Ewan Delanoy Dec 26 '17 at 8:31

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.