We can call the $x$th Fibonacci number Fib($x$). What's the best asymptotic lower bounds on the amount of relatively prime Fibonacci numbers between Fib($n$) and Fib($n+m$)?

In other words, if we take the $m$ Fibonacci numbers that lie between Fib($n$) (inclusive) and Fib($n+m$), what is the maximally sized set of these numbers can be pairwise relatively prime to each other, in terms of $n$ and $m$? Of course, I'm looking for some sort of asymptotic bounds - more specifically, a big Omega bound, but we are allowed to pick from any of the $m$ Fibonacci numbers in the sequence, in order to make this bound larger. Note that I'm looking for the maximally sized set, but in the worst case.

  • 2
    $\begingroup$ Relatively prime to what? To each other? What is the maximally sized set of Fibonacci numbers in that range that are all pairwise relatively prime? Is that the question? $\endgroup$ – Zubin Mukerjee Oct 2 '18 at 19:04
  • $\begingroup$ @ZubinMukerjee: Yes, relatively prime to each other, and yes, the maximally sized set that are all pairwise relatively prime - thank you! $\endgroup$ – Matt Groff Oct 2 '18 at 19:05
  • $\begingroup$ Note that every third Fib(n) is even, every fourth is divisible by $3$, every fifth by $5$, and that in general every $d^{th}$ is divisible by Fib(d). If indices are coprime so are the Fibonacci numbers (at least with Fib$(1)=1$, Fib$(2)=1$) So this becomes essentially the same problem as picking coprime integers for the indices. $\endgroup$ – Mark Bennet Oct 2 '18 at 20:04

Although this appears to be intrinsically a question about Fibonacci numbers, in fact the Fibonacci numbers are a guise. The key aspect to notice here is that $$ \gcd(Fib(n), Fib(m)) = Fib(\gcd(n,m)).$$ (This is proved, for instance, in this other post on this site).

Thus $Fib(n)$ and $Fib(m)$ are relatively prime exactly when $\gcd(m,n) = 1$ or $2$. Your question is now a question about relatively prime (or divisible by exactly $2$) sets of numbers.

The relevant question to ask is the following.

What is the size of the largest subset $S \subseteq [m, n]$ such that $x,y \in S$ implies that $\gcd(x,y) = 1$ or $\gcd(x,y) = 2$?

A clear lower bound is the number of primes between $m$ and $n$, $\pi(n) - \pi(m)$. In fact, one can also use numbers which are twice a prime, so a slightly better lower bound is $\pi(n) - \pi(m/2)$. Asymptotically, if $n - m = X$, then this guarantees $X / \log X$ as a lower bound.

It is not clear to me how much better you can actually do. This seems to me to be a nice, hard problem --- precisely the sort of thing that Erdos or Pomerance would be interested in.

| cite | improve this answer | |
  • $\begingroup$ I upvoted and will probably accept your nice answer. Just a comment... From this answer and comments: math.stackexchange.com/a/1816646/2626 See the comments below... We can pick a set of primes $p_k$ that are small, and then use the GCD $g$ of all pairwise differences of the primes to get small Fibonacci's $g+p_k$. I doubt this will be the best bound in most cases, but it seems to me to give a reasonable set of Fibonacci numbers. Anyways, thanks for your nice answer, and maybe some Erdos or Pomerance will come along and help! $\endgroup$ – Matt Groff Oct 3 '18 at 15:37

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.