5 ms·
The Fibonacci Sequence as a Functor
- spekcular 5y agoAs 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.
- ABeeSea 5y agoMost 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.
- agumonkey 5y agoDo you know good articles about semi-lattices ?
- dbfkfndkjd 5y agoI'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/ https://math.hmc.edu/funfacts/fibonacci-gcds-please/
- ABeeSea 5y agoShe 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.
- ogogmad 5y agoThe article can have two pay-offs: - People who know some category theory can sharpen their knowledge of it. They can ask followup questions, like does the Fibonacci sequence have a left adjoint? The answer is yes, which is what the top comment on this HN page talks about. - People who don't know category theory might use this to learn some. In which case, we have a case of number theory having applications to category theory rather than the expected converse, which would be category theory having applications to number theory.
- adamgordonbell 5y agoA 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
- agumonkey 5y ago(a, b) -> (a, (b, a+b)) funny it's almost graphically equivalent to the geometric ratio
- zuminator 5y agoIt'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_consecutive_quotients https://en.wikipedia.org/wiki/Fibonacci_number#Limit_of_cons...
- OscarCunningham 5y agoSince 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) [https://oeis.org/A001177 https://oeis.org/A001177]. 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?
- ogogmad 5y agoI 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.
- autokad 5y agothere's a closed form solution: ((golden ratio)* * N - (1 / golden ratio)* * N) / * *.5