Is every positive integer representable as $N = x^2 + y^2 + z^2 + dw^2, 1 \le d \le 7$ with $x,y,z,w$ as Fibonacci numbers

elementary-number-theoryfibonacci-numbers

This question is related to this other MSE Question in which it was shown that every integer cannot be represented as the sum of four Fibonacci squares and the first exception is $24$.

There is a theorem that states that every positive integer can be represented in the form

$$N = x^2 + y^2 + z^2 + dw^2, 1 \le d \le 7 \tag{1}$$

Question:

Is every positive integer representable in the form given in Eqn. (1) where $w, x, y, z$ are Fibonacci numbers?

For example: $24 = 1^2 + 1^2 + 2^2 + 2\cdot3^2$
If the given range $1 \le d \le 7$ is not possible, how wide should it be?

One approach is to use the fact that $u \in \mathbb{Z}$ is a Fibonacci number iff $\exists v \in \mathbb{Z}$ such that $5u^2 + 4 = v^2 \lor 5u^2 – 4 = v^2$.

So, $5|v^2 – 4$ or $5|v^2 + 4$ is necessary for $u^2$ to be a Fibonacci square.

How do we proceed from here?

Best Answer

Let $[n]$ be the set $\{0,1,...,n\}$ and given a set $X$ of natural numbers, define

$$F_7(X) =\{x^2+y^2+z^2+dw^2| w,x,y,z\in X, d\in[7]\} $$

The first question is, what is the cardinality of $F_7(X)$, if the cardinality of $X$ is $n$?

There isn't a way to determine exactly without knowing more about $X$, but we know that it must be less than $n^4\times 7$, simply by a combinatorial argument.

If we take say the set of the first 20 Fibonacci numbers, lets denote it by $\mathcal{f}_{20}$ then the largest element in $F_7(\mathcal{f}_{20})$ is of course the number created by choosing $x,y,z,w$ as the $20$th Fibonacci number, and $d=7$, the $20th$ Fibonacci number is $6765$, so the largest element in $F_7(\mathcal{f}_{20})$ is $10\times 6765^2 $, which is almost half a billion. We need to remember that we can also take larger Fibonacci numbers than the $20$th one, if we let the others be $1$ for example, so the cardinality of $F_7(f_{20})$ isn't the relavant Cardinality, rather we should ask how many Fibonacci numbers can we include before even one of them squared is too big, and just as an example, the $50$th Fibonacci number is ridiculously big, so we can safely consider the Cardinality of $F_7(\mathcal{f_{50}})$, which is still well below half a billion, so there is no way to create a bijection between $F_7(\mathcal{f_{50}})$ and $[10\times 6765^2]$, so somewhere in there is some number that can't be expressed in this way.

You can repeat this argument if you increase the range of $d$ but I don't think you'll ever find a large enough finite range to ever satisfy even the cardinality requirements, the Fibonacci numbers are just too sparse when you square them

Related Solutions

[Math] Do the Fibonacci numbers contain any run of digits

Yes, there is. We can even demand that the prescribed $x$ appears at the beginning of a Fibonacci number.

For large $n$ the Fibonacci number $F_n$ shares its all but possibly the least significant digit with $$F_n\approx\frac1{\sqrt5}\left(\frac{1+\sqrt5}2\right)^n$$ by Binet's formula.

Because $\theta=\log_{10}((1+\sqrt5)/2)$ is irrational the claim follows from Kronecker's density theorem. The argument is the same as here, where the question is about the string of the most significant digits in the decimal expansion of $2^n$.

For the sake of completeness here's the proof for the irrationality of $\theta$. Assume contrariwise that there exists a rational number $m/n$ such that $$ 10^{m/n}=\frac{1+\sqrt5}2. $$ Raising this to power $n$ would then imply that $$ 10^m=\left(\frac{1+\sqrt5}2\right)^n. $$ But here the left hand side is an integer where as the right hand side differs from an integer by the tiny amount $\left(\frac{1-\sqrt5}2\right)^n$.

A way of finding explicit (but not necessarily anywhere near the smallest) values of $n$ is then to find good rational approximations of $\theta$. Here $\theta=0.2089876\ldots$. A good rational approximation is then $$ \frac{14}{67}=0.20895522\ldots $$ This implies that $$ \left(\frac{1+\sqrt5}2\right)^{67}\approx 1.005013\cdot10^{14} $$ is very close to a power of ten. By Binet's formula this means that $F_{n+67}$ begins with a sequence of digits close to that of $F_n$, only slightly "bigger".

For example, if you want a Fibonacci number beginning $32\cdots$, you can do the calculations $$ \begin{aligned} x&=\log_{10}(32\cdot\sqrt5)\approx1.8546\ldots,\\ y&=67\theta-\lfloor 67\theta\rfloor\approx0.0021718967\ldots,\\ m&=(x-\lfloor x\rfloor)/y\approx 393.47\ldots \end{aligned} $$ Then (thanks to Mathematica) you can calculate $$ \begin{aligned} F_{393\cdot67}=3192055\ldots,\\ F_{394\cdot 67}=3200805\ldots,\\ F_{395\cdot67}=3224142\ldots. \end{aligned} $$ You see how incrementing $n$ by $67$ increases the value of the integer formed by seven most significant digits by about $0.5$ per cent.

When that half per cent resolution is not good enough to give you the string you want (happens inevitably for longer strings), you need to look for better rational approximations for $\theta$. The tool for that is given by the theory of continued fractions (and best rational approximations).

Zeckendorf with Negative Fibonacci Numbers

The negative fibbonacci numbers run as $F(-n)=F(n)$ for odd $n$ and $F(-n)=-F(n)$ for even $n$.

So we get for fibonacci numbers

 -21  13  -8   5  -3   2  -1   1
                          -1
                  -3           1
                  -3
                  -3      -1
          -8           2       1
          -8           2
          -8       t0 12
  -21          5       2       1
  -21     -8       -3     -1

So yes, all of the natural numbers can be expressed as a sum of non-consecutive fibonacci numbers of negative index.

It ought be a straight-forward conversion from the positive to negative schema.

  eg  -21            5     2      1
       21           -5    -2     -1
           13   8   -5    -2    -1
           13           3 -2     -1
           13

It's possible to go both ways, and there is a carry rule to prevent adjacent columns being filled with more than one counter.

Best Answer

Related Solutions

[Math] Do the Fibonacci numbers contain any run of digits

Zeckendorf with Negative Fibonacci Numbers

Related Question