New Proof Settles How to Approximate Numbers Like Pi

The deep recesses of the number line are not as forbidding as they might seem. That’s one consequence of a major new proof about how complicated numbers yield to simple approximations.

The proof resolves a nearly 80-year-old problem known as the Duffin-Schaeffer conjecture. In doing so, it provides a final answer to a question that has preoccupied mathematicians since ancient times: Under what circumstances is it possible to represent irrational numbers that go on forever — like pi — with simple fractions, like $latex \frac{22}{7}$? The proof establishes that the answer to this very general question turns on the outcome of a single calculation.

“There’s a simple criterion for whether you can approximate virtually every number or virtually no numbers,” said James Maynard of the University of Oxford, co-author of the proof with Dimitris Koukoulopoulos of the University of Montreal.

Mathematicians had suspected for decades that this simple criterion was the key to understanding when good approximations are available, but they were never able to prove it. Koukoulopoulos and Maynard were able to do so only after they reimagined this problem about numbers in terms of connections between points and lines in a graph — a dramatic shift in perspective.

“They had what I’d say was a great deal of self-confidence, which was obviously justified, to go down the path they went down,” said Jeffrey Vaaler of the University of Texas, Austin, who contributed important earlier results on the Duffin-Schaeffer conjecture. “It’s a beautiful piece of work.”

The Ether of Arithmetic

Rational numbers are the easy numbers. They include the counting numbers and all other numbers that can be written as fractions.

This amenability to being written down makes rational numbers the ones we know best. But rational numbers are actually rare among all numbers. The vast majority are irrational numbers, never-ending decimals that cannot be written as fractions. A select few are important enough to have earned symbolic representations, such as pi, e and $latex \sqrt{2}$. The rest can’t even be named. They are everywhere but untouchable, the ether of arithmetic.

So maybe it’s natural to wonder — if we can’t express irrational numbers exactly, how close can we get? This is the business of rational approximation. Ancient mathematicians, for instance, recognized that the elusive ratio of a circle’s circumference to its diameter can be well approximated by the fraction $latex \frac{22}{7}$. Later mathematicians discovered an even better and nearly as concise approximation for pi: $latex \frac{355}{113}$.

“It’s hard to write down what pi is,” said Ben Green of Oxford. “What people have tried to do is to find explicit approximations to pi, and one common way of doing that is with rationals.”

In 1837 the mathematician Gustav Lejeune Dirichlet found a rule for how well irrational numbers can be approximated by rational ones. It’s easy to find approximations so long as you’re not too particular about the error. But Dirichlet proved a straightforward relationship between fractions, irrational numbers and the errors separating the two.

He proved that for every irrational number, there exist infinitely many fractions that approximate the number evermore closely. Specifically, the error of each fraction is no more than 1 divided by the square of the denominator. So the fraction $latex \frac{22}{7}$, for example, approximates pi to within $latex \frac{1}{7}^{2}$, or $latex \frac{1}{49}$. The fraction $latex \frac{355}{113}$ gets within $latex \frac{1}{113}^{2}$, or $latex \frac{1}{12,769}$. Dirichlet proved that there is an infinite number of fractions that draw closer and closer to pi as the denominator of the fraction increases.

“It’s a rather beautiful and remarkable thing that you can always approximate a real number by a fraction and the error is no more than 1 over [the denominator squared],” said Andrew Granville of the University of Montreal.

Dirichlet’s discovery was, in a sense, a narrow statement about rational approximation. It said that you can find infinitely many approximating fractions for each irrational number if your denominators can be any whole number, and if you’re willing to accept an error that’s 1 over the denominator squared. But what if you want your denominators to be drawn from some (still infinite) subset of the whole numbers, like all prime numbers, or all perfect squares? And what if you want your approximation error to be 0.00001, or any other values you might choose? Will you succeed at producing infinitely many approximating fractions under such specific conditions?

The Duffin-Schaeffer conjecture is an attempt to provide the most general possible framework for thinking about rational approximation. In 1941 the mathematicians R.J. Duffin and A.C. Schaeffer imagined the following scenario. First, choose an infinitely long list of denominators. This could be anything you want: all odd numbers, all numbers that are multiples of 10, or the infinite list of prime numbers.

Second, for each of the numbers in your list, choose how closely you’d like to approximate an irrational number. Intuition tells you that if you give yourself very generous error allowances, you’re more likely to be able to pull off the approximation. If you give yourself less leeway, it will be harder. “Any sequence can work provided you leave enough room,” Koukoulopoulos said.

Now, given the parameters you’ve set up — the numbers in your sequence and the defined error terms — you want to know: Can I find infinitely many fractions that approximate all irrational numbers?

The conjecture provides a mathematical function to evaluate this question. Your parameters go in as inputs. Its outcome could go one of two ways. Duffin and Schaeffer conjectured that those two outcomes correspond exactly to whether your sequence can approximate virtually all irrational numbers with the demanded precision, or virtually none. (It’s “virtually” all or none because for any set of denominators, there will always be a negligible number of outlier irrational numbers that can or can’t be well approximated.)

“You get virtually everything or you get virtually nothing. There’s no middle ground at all,” Maynard said.

It was an extremely general statement that tried to characterize the warp and weft of rational approximation. The criterion that Duffin and Schaeffer proposed felt correct to mathematicians. Yet proving that the binary outcome of this function is all you need to know whether your approximations work — that was much harder.

Double Counting

Proving the Duffin-Schaeffer conjecture is really about understanding exactly how much mileage you’re getting out of each of your available denominators. To see this, it’s useful to think about a scaled-down version of the problem.

Imagine that you want to approximate all irrational numbers between 0 and 1. And imagine that your available denominators are the counting numbers 1 to 10. The list of possible fractions is pretty long: First $latex \frac{1}{1}$, then $latex \frac{1}{2}$ and $latex \frac{2}{2}$, then $latex \frac{1}{3}$, $latex \frac{2}{3}$, $latex \frac{3}{3}$ and so on up to $latex \frac{9}{10}$ and $latex \frac{10}{10}$. Yet not all of these fractions are useful.

The fraction $latex \frac{2}{10}$ is the same as $latex \frac{1}{5}$, for example, and $latex \frac{5}{10}$ covers the same ground as $latex \frac{1}{2}$, $latex \frac{2}{4}$, $latex \frac{3}{6}$ and $latex \frac{4}{8}$. Prior to the Duffin-Schaeffer conjecture, a mathematician named Aleksandr Khinchin had formulated a similarly sweeping statement about rational approximation. But his theorem didn’t account for the fact that equivalent fractions should only count once.

“Usually something that’s first-grade mathematics shouldn’t make a difference to the solution,” Granville said. “But in this case surprisingly it did make a difference.”

So the Duffin-Schaeffer conjecture includes a term that calculates the number of unique fractions (also called reduced fractions) you get from each denominator. This term is called the Euler phi function after its inventor, the 18th-century mathematician Leonhard Euler. The Euler phi function of 10 is 4, since there are only four reduced fractions between 0 and 1 with 10 as a denominator: $latex \frac{1}{10}$, $latex \frac{3}{10}$, $latex \frac{7}{10}$ and $latex \frac{9}{10}$.

The next step is to figure out how many irrational numbers you can approximate with each of the reduced fractions. This depends on how much error you’re willing to accept. The Duffin-Schaeffer conjecture lets you choose an error for each of your denominators. So for fractions with denominator 7 you might set the allowable error to 0.02. With denominator 10 you might expect more and set it to 0.01.

Once you’ve identified your fractions and set your error terms, it’s time to go trawling for irrationals. Plot your fractions on the number line between 0 and 1 and picture the error terms as nets extending from either side of the fractions. You can say that all irrationals caught in the nets have been “well approximated” given the terms you set. The question — the big question — is: Just how many irrationals have you caught?

There are infinitely many irrational numbers contained in any interval on the number line, so the captured irrationals can’t be expressed as an exact number. Instead, mathematicians ask about the proportion of the total number of irrationals corralled by each fraction. They quantify these proportions using a concept called the “measure” of a set of numbers — which is like quantifying a catch of fish by total weight rather than number of fish.

The Duffin-Schaeffer conjecture has you add up the measures of the sets of irrational numbers captured by each approximating fraction. It represents this number as a large arithmetic sum. Then it makes its key prediction: If that sum goes off to infinity, then you have approximated virtually all irrational numbers; if that sum instead stops at a finite value, no matter how many measures you sum together, then you’ve approximated virtually no irrational numbers.

This question, of whether an infinite sum “diverges” to infinity or “converges” to a finite value, comes up in many areas of mathematics. The Duffin-Schaeffer conjecture’s main claim is that if you want to figure out whether you can approximate nearly all irrational numbers given a set of denominators and allowable error terms, this is the only feature you need to know: whether that infinite sum of measures diverges to infinity or converges to a finite value.

“At the end of the day, no matter how you’ve decided the degree of approximation for [each denominator], whether or not you’ve succeeded purely depends on whether the associated infinite sequence diverges or not,” Vaaler said.

Plotting a Solution

You may be wondering: What if the numbers approximated by one fraction overlap with the numbers approximated by another fraction? In that case aren’t you double-counting when you add up the measures?

For some approximation sequences the double-counting problem isn’t significant. Mathematicians proved decades ago, for example, that the conjecture is true for approximation sequences composed of all prime numbers. But for many other approximation sequences the double-counting challenge is formidable. It’s why mathematicians were unable to solve the conjecture for 80 years.

The extent to which different denominators capture overlapping sets of irrational numbers is reflected in the number of prime factors the denominators have in common. Consider the numbers 12 and 35. The prime factors of 12 are 2 and 3. The prime factors of 35 are 5 and 7. In other words, 12 and 35 have no prime factors in common — and as a result, there isn’t much overlap in the irrational numbers that can be well approximated by fractions with 12 and 35 in the denominator.

But what about the denominators 12 and 20? The prime factors of 20 are 2 and 5, which overlap with the prime factors of 12. Likewise, the irrational numbers that can be approximated by fractions with denominator 20 overlap with the ones that can be approximated by fractions with denominator 12. The Duffin-Schaeffer conjecture is hardest to prove in situations like these — where the numbers in the approximating sequence have many small prime factors in common and there’s a lot of overlap between the sets of numbers each denominator approximates.

“When a lot of the denominators you have to choose from have a lot of small prime factors then they start to get in the way of each other,” said Sam Chow of Oxford.

The key to solving the conjecture has been to find a way to precisely quantify the overlap in the sets of irrational numbers approximated by denominators with many small prime factors in common. For 80 years no one could do it. Koukoulopoulos and Maynard got there by finding a completely different way to look at the problem.

In their new proof, they create a graph out of their denominators — plotting them as points and connecting the points with a line if they share a lot of prime factors. The structure of this graph encodes the overlap between the irrational numbers approximated by each denominator. And while that overlap is hard to assay directly, Koukoulopoulos and Maynard found a way to analyze the structure of the graph using techniques from graph theory — and the information they cared about fell out from there.

“The graph is a visual aid, it’s a very beautiful language in which to think about the problem,” Koukoulopoulos said.

Koukoulopoulos and Maynard proved that the Duffin-Schaeffer conjecture is indeed true: If you’re handed a list of denominators with allowable error terms, you can determine whether you can approximate virtually all irrational numbers or virtually none just by checking whether the corresponding sum of the measures around each fraction diverges to infinity or converges to a finite value.

It’s an elegant test that takes a vast question about the nature of rational approximation and boils it down to a single calculable value. By proving that the test holds universally, Koukoulopoulos and Maynard have achieved one of the rarest feats in mathematics: They’ve given a final answer to a foundational concern in their field.

“Their proof is a necessary and sufficient result,” Green said. “I suppose this marks the end of a chapter.”

This article was reprinted on Wired.com.