Category Archives: Analysis

Pi and the AGM

In celebration of Pi Day 2024, I would like to explain how the “Arithmetic-Geometric Mean” of Gauss and Legendre can be used to give a rapid method for computing the digits of \pi. By “rapid” here, I mean that the algorithm exhibits quadratic convergence: the number of correct digits roughly doubles with each iteration. I will mainly follow the exposition in Donald J. Newman’s 1985 paper “A Simplified Version of the Fast Algorithms of Brent and Salamin”.

Continue reading →

Algebraic Values of Transcendental Functions at Algebraic Points

In honor of Pi Day 2023, I’d like to discuss Hilbert’s 7th Problem, which in an oversimplified (and rather vague) form asks: under what circumstances can a transcendental function take algebraic values at algebraic points?

The connection with \pi is that Lindemann proved in 1882 that the transcendental function f(z) = e^z takes transcendental values at every nonzero algebraic number. Since e^{\pi i} = -1 by Euler’s formula, this proves that \pi i, and hence \pi itself, is transcendental. In light of this theorem, it is natural to wonder what if anything is special here about the function f(z) = e^z and the point z=0.

Ferdinand von Lindemann

One thing that’s special about z=0 is that if \alpha \neq 0 is algebraic and e^\alpha is also algebraic, then both n\alpha and e^{n \alpha} are algebraic for all n \in {\mathbb Z}, and these numbers are all distinct. So one might be led to speculate that if f is a transcendental entire function then there are only finitely many algebraic numbers \alpha for which f(\alpha) is also algebraic.

Unfortunately, as Hilbert knew, this is completely false. For example, the function f(z) = e^{2\pi iz} is transcendental but it takes the rational value 1 at every integer. In 1886, Weierstrass had given an example of a transcendental entire function that takes rational values at all rational numbers; later, in 1895, Stäckel showed that there is a transcendental entire function that takes rational values at all algebraic points. However, the functions of Weierstrass and Stäckel, are in some sense “pathological”; they have large growth rates and do not occur “in nature”. The challenge is to make this intuitive feeling more precise, and also to distinguish e^z from e^{2\pi iz}.

One thing that is special about e^z, which is not shared by any of the other functions mentioned in the previous paragraph, is that it satisfies a linear differential equation with rational coefficients (namely f'(z) = f(z)). The existence of such a (not necessarily linear) differential equation turns out to be the key idea needed to generalize Lindemann’s theorem in a substantial way.

Another fruitful generalization is to rephrase our original question as an unlikely intersection problem: given two algebraically independent entire functions f_1(z) and f_2(z) satisfying suitable hypotheses, can we conclude that there are only finitely many complex numbers \alpha such that f_1(\alpha) and f_2(\alpha) are simultaneously algebraic? This generalizes our original question by letting f_1(z) = z and f_2(z) = f(z).

Continue reading →

The Eudoxus reals

Let’s call a function f : {\mathbb Z} \to {\mathbb Z} a near-endomorphism of \mathbb Z if there is a constant C>0 such that |f(a+b)-f(a)-f(b)| \leq C for all a,b \in \mathbb Z. The set of near-endomorphisms of \mathbb Z will be denoted by N. We put an equivalence relation \sim on N by declaring that f \sim g iff the function f-g is bounded, and let {\mathbb E} denote the set of equivalence classes.

It’s not difficult to show that defining f+g in terms of pointwise addition and f \cdot g in terms of composition of functions turns {\mathbb E} into a commutative ring. And it turns out that this ring has a more familiar name… Before reading further, can you guess what it is?

Continue reading →

An April Fools’ Day to Remember

Today is the 10th anniversary of the death of Martin Gardner. His books on mathematics had a huge influence on me as a teenager, and I’m a fan of his writing on magic as well, but it was only last year that I branched out into reading some of his essays on philosophy, economics, religion, literature, etc. In this vein, I highly recommend “The Night Is Large”, a book of collected essays which showcases the astonishingly broad range of topics about which Martin had something interesting to say. It’s out of print, but it’s easy to find an inexpensive used copy if you search online.

Thinking back on my favorite Martin Gardner columns, my all-time favorite has to be the April 1975 issue of Scientific American. In that issue, Martin wrote an article about the six most sensational discoveries of 1974. The whole article was an April Fools’ Day prank: among the discoveries he reported were a counterexample to the four-color problem and an artificial-intelligence computer chess program that determined, with a high degree of probability, that P-KR4 is always a winning move for white. The article also contained the following:

Continue reading →

Interlacing via rational functions and spectral decomposition

First of all, I’d like to express my sympathies to everyone who is enduring hardships due to COVID-19. Stay well and be strong.

In this previous post, I discussed two important classical results giving examples of polynomials whose roots interlace:

Theorem 1: The roots of a real-rooted polynomial and its derivative interlace.

Theorem 2: (Cauchy’s interlacing theorem) The eigenvalues of a real symmetric matrix interlace with those of any principal minor.

In this post, I’d like to explain a general method, based on partial fraction expansions of rational functions, which gives a unified approach to proving Theorems 1 and 2 and deserves to be better known.

Continue reading →

Lorentzian Polynomials II: Applications

In this previous post, I described the basic theory of Lorentzian polynomials d’après Brändén and Huh. Now I’d like to describe some of the powerful applications of this theory, culling together results from papers by several different sets of authors. Our first application will be Mason’s Ultra-Log-Concavity Conjecture from 1972, established independently by Brändén-Huh and Anari-Liu-Oveis Gharan-Vinzant in 2018.

Theorem: Let M be a matroid on n elements, and let I_k(M) denote the number of independent sets of size k in M. Then the sequence I_k(M) is ultra-log-concave.

A special case of this result (which seems to be no easier to prove than the general case) is the following: Let E be a set of n vectors in some finite-dimensional vector space, and let I_k denote the number of k-element linearly independent subsets of E. Then the sequence I_k is ULC.

Continue reading →

Lorentzian polynomials I: Theory

I’m organizing a reading seminar this semester on Lorentzian polynomials, mainly following this paper by Brändén and Huh but also covering some of the work of Anari et. al. In this post, I’d like to give a quick introduction to this active and beautiful subject. I’ll concentrate on the basic theory for now, and in a follow-up post I’ll discuss some of the striking applications of this theory.

One major goal of the theory of Lorentzian polynomials is to provide new techniques for proving that various naturally-occurring sequences of non-negative real numbers a_k are log-concave, meaning that a_k^2 \geq a_{k-1} a_{k+1} for all k. More generally, the authors consider homogeneous multivariate polynomials p(x_1,\ldots,x_n) with non-negative coefficients and study certain natural extensions of log-concavity to this setting. (For some background on log-concave sequences, see this survey paper which I wrote for the Bulletin of the AMS.) So let me begin by introducing two “classical” methods for proving (an even sharper version of) log-concavity of the coefficients of certain polynomials.

Continue reading →