In the past months, I spent as much time as I had on taking online courses at Coursera. One particularly interesting course, both from a mathematical and computational point of view, is Analytic Combinatorics which applies combinatorics (i.e., the art of counting) to the analysis of algorithms by finding formulae, exact or asymptotic, for their running time.
It is notoriously difficult to find exact formulae for general combinatorial constructs. Typically, we want to know how many objects, e.g., trees, permutations, sequences, with certain properties there are of a given size. Famously, the number of binary trees (and about a million other constructions) is governed by the Catalan numbers
I recently spent some time on the formidable website Numberphile which explains mathematical ideas, some important, some recreational, in short and accessible videos. Definitely worth checking out. One of the videos that is most relevant to us explains the Riemann Hypothesis:
On 16 January 1913, a confused manuscript reached the famous mathematician G. H. Hardy in Cambridge. Other researchers have received similar letters before, and rejected it due to the seemingly incoherent formulae mixed with trivial mathematical results. Professional mathematicians are used to receiving manuscripts by amateurs who believe to have solved famous problems, but this particularly odd scribble caught the eye:
Did this amateur mathematician really think that the sum of all natural numbers, a value that will exceed any given boundary at some point, will wind up being a negative fraction? M. J. M. Hill of the University College, London, simply responded that the author must have fallen victim to the pitfalls of divergent series and referred him to a standard textbook on the topic.
So, was this really just the work of a lunatic? Well, recently, the New York Times covered the topic, linking a video in which two physicists explain the importance of this result in modern string theory. While many physicists may not be too far from lunatics, these two make a pretty strong argument in this case: Continue reading Infinity Is Worth No More Than -1/12→
Everything You Always Wanted to Know About Primes (But Were Afraid to Ask)