💾 Archived View for dioskouroi.xyz › thread › 29366522 captured on 2021-11-30 at 20:18:30. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
________________________________________________________________________________
Since the Fibonacci sequence preserves limits, the adjoint functor theorem says there must be some function G such that n divides F(m) if and only if G(n) divides m. This is called the sequence of entry points for the Fibonacci sequence, because G(n) is given by the first m such that n divides F(m) [
].
Of course since G is a left adjoint it has the dual property that lcm(G(n),G(m)) = G(lcm(n,m)).
Can we do more advanced category theory here? What is the Kan extension of the Fibonacci sequence along the Mersenne numbers?
I was thinking about finding a left adjoint G. I see you've proven its existence using a sledgehammer: the adjoint functor theorem. Your explicit construction for G(n) as the _smallest_ m such that n divides F(m) is very informative. It goes well with the idea that an adjoint is somehow an optimiser. Thanks.
That entry point sequence is weird.
A fib sequence can be defined corecursively using unfold and its actually a nice way to write it in some languages.
Here is the next fib in a sequence (in psuedocode):
(a, b) -> (a, (b, a+b))
And then you can get a sequence with unfold by giving it some starting numbers:
val fibonacci: Iterator[Int] =
Iterator.unfold((1, 1)) {
case (x, y) => Some((x, (y, x + y)))
}
(That is Scala. But lots of languages have an unfold method)
> fibonacci.take(8).toList
1, 1, 2, 3, 5, 8, 13, 21
(a, b) -> (a, (b, a+b))
funny it's almost graphically equivalent to the geometric ratio
It's not _almost_ equivalent to the geometric ratio, it _is_ the geometric (aka golden) ratio, at the limit, as first observed by none other than Johannes Kepler [0]. You are in heavenly company!
[0]
https://en.wikipedia.org/wiki/Fibonacci_number#Limit_of_cons...
I think the point was that the physical representation of the RHS looks like it's a golden ratio bigger than the LHS.
As the author admits at the end, nothing is gained by introducing category-theoretic language here.
Abstraction should be introduced only when it aids understanding or problem solving. Shoehorning functors into basic topics like the Fibonacci sequence leaves a bad taste in my mouth. It gives the impression that category theory is just some contentless linguistic gloss, instead of, for example, a useful tool for facilitating computations in algebraic topology.
Most of the article is about semi-lattices and posets which are often most usefully described in a categorical framework. Fibonacci sequence is just a toy example to demonstrate the general concept. I have a ton of graduate level math books that torture a toy example to death because they’re concrete.
I'm pretty sure that what actually happened here is is that some category theory enthusiasts noticed a slightly surprising (and elementary) example of a commutative square in number theory. CT doesn't deal with number theory all that much.
I came across this "commutative square" involving GCD and fib myself a couple of years ago. I came at it from noticing that there was a similar structure in iterative fib to the recursive Euclidean algorithm.
Note the "a, b = b, a + b"
def f(n):
a, b = 0, 1
for i in range(0, n):
a, b = b, a + b
return a
and then "a=b, b=a%b" here
def gcd(a,b):
if(b==0):
return a
else:
return gcd(b,a%b)
I googled "gcd fibonacci" and landed here:
https://math.hmc.edu/funfacts/fibonacci-gcds-please/
She has a PhD in category theory.
>Category Theory doesn’t deal with number theory all that much.
Not sure where you are drawing the line here since algebraic geometry (aka modern number theory) makes extensive and extremely deep use of category theory. Ravi Vakil’s Rising Sea being the best intro to this point of view.
This example is just a fun way to talk about posets.
Do you know good articles about semi-lattices ?
there's a closed form solution:
((golden ratio)* * N - (1 / golden ratio)* * N) / * *.5
Finally realized what was missing:
n n
φ - (1/φ)
F(n) = -----------
√5
There's a missing 5 in your presentation of the equation.