The new proof solves the approximation of numbers such as pi

The ancient Greeks were interested in whether it is possible to roughly express irrational numbers in fractions. Proving the long-standing Duffin-Schaffer hypothesis , two mathematicians gave an exhaustive answer.

The binary notation π is infinite. But an infinite number of fractions can approach this number with ever increasing accuracy.



Deep dips on the number line are not as impregnable as it might seem. This is one of the consequences of new meaningful evidence of how complex numbers lend themselves to simple approximations.



The proof solves the problem of almost 80 years ago, known as the Duffin-Shaffer hypothesis. Thus, it gives a final answer that has occupied mathematicians since ancient times: under what conditions is it possible to represent irrational numbers lasting infinitely long - such as pi - with simple fractions of type 22/7? The proof establishes that the answer to this rather general question is found as a result of a single calculation.



“There is a simple criterion for whether you can approximate almost any number or practically no numbers,” said James Maynard of Oxford University, co-author of the proof he made with Dimitris Cuculopoulos of the University of Montreal.



Mathematicians have been suspecting for several decades, this simple criterion is key to understanding when a good approximation can be obtained - but they could not prove it. Kukulopoulos and Maynard were able to do this only after they reformulated this problem of numbers in terms of the connections between points and lines of the graph - a cardinal change in perspective.



“I would say they were confident enough (and that was obviously justified) to take the chosen path,” said Jeffrey Waaler of the University of Texas at Austin, who had a hand in the early results of the Duffin-Schaffer hypothesis. - Great job".

Arithmetic ether

With rational numbers, everything is simple. They include numbers for counting objects and all other numbers that can be written in fractions.



Due to this ability to be written down, rational numbers are best known to us. However, among all real numbers, rational ones are actually quite few. Most of the numbers are irrational , with an infinite decimal notation, and they cannot be written in fractions. Some of them turned out to be important enough to deserve symbolic notation - pi, e, √2. The rest cannot even be called. They are everywhere, but unattainable - like an arithmetic ether.



Perhaps, therefore, it will be natural to think - if we cannot accurately express irrational numbers, how close can we get to them? This is an area of ​​rational approximation. Mathematicians of antiquity realized that the elusive ratio of circumference to diameter can be quite well approximated using the fraction 22/7. Later, mathematicians discovered an even more accurate and almost the same compressed approximation to pi: 355/113.



“Writing pi is very difficult,” said Ben Green of Oxford. “People tried to find the most accurate approximation to pi, and one of the common ways to do this was to use rational numbers.”







In 1837, the mathematician Peter Gustav Lejeune Dirichlet discovered a rule telling us how accurately irrational numbers can be approximated using rational numbers. The approximation is easy to find if you do not set the exact value of the error. But Dirichlet proved the existence of a clear relationship between fractions, irrational numbers and the errors that separate them.



He proved that for any irrational number there are infinitely many fractions approaching him closer and closer. More precisely, the error of each fraction will be no more than 1 divided by the square of the denominator. For example, the fraction 22/7 approximately expresses pi with an accuracy of 1/7 ² , or 1/49. The fraction 355/113 is no further from pi than by 1/113 ² , or 1/12 769. Dirichlet proved that there are infinitely many fractions, getting closer and closer to pi with increasing denominator.



“An amazing and remarkable thing is the ability to approximately express a real number through a fraction, with an error not exceeding one divided by the square of the denominator,” said Andrew Granville of the University of Montreal.





In the 1913 manuscript, the mathematician Srinivasa Ramanujan Iyengor used the fraction 355/113 as a rational approximation of pi.



Dirichlet's discovery was a limited statement regarding rational approximation. It says that for any irrational number you can find infinitely many fractions approaching it, if you can use any integer as the denominator, and you are satisfied with the error in the size of its inverse square. But what if you need the denominators to belong to some (infinite) subset of integers, for example, to the set of primes, or to the set of full squares ? What if you want the approximation error to be 0.00001, or to have any other value? Will you be able to find infinitely many approximating fractions precisely in such conditions?



The Duffin-Shaffer hypothesis is an attempt to create the most generalized platform for working with rational approximations. In 1941, mathematicians R.D. Duffin and A.S. Schafer presented the following scenario. First, choose an endless list of denominators. It can be everything you want: odd numbers, numbers divisible by 10, prime numbers.



Then, for each number in the list, select how accurately you need to approximate the irrational number. Intuition tells us that if we choose sufficiently large errors, we will have more opportunities for approximation. If you choose a small error size, it will be more difficult. “Any sequence will do if enough space is left,” said Kukulopoulos.



Now, given the selected parameters - a sequence of numbers and a certain error - the question arises: is it possible to find infinitely many fractions approximating all irrational numbers?



The hypothesis provides a mathematical function to evaluate this question. Your parameters act as input. The result can be one of two options. Duffin and Schaffer suggested that these two options correspond precisely to whether your sequence can approximate almost all irrational numbers with the required accuracy, or practically none of them (“practically” is mentioned because for any set of denominators there will always be a small number isolated irrational numbers that can or cannot be approximated well enough).



“You get almost everything or almost nothing. There are no intermediate options, ”Maynard said.



This was an extremely general statement, trying to characterize the approximation by rational numbers along and across. The criterion proposed by Duffin and Schaffer seemed correct to mathematicians. However, to prove that the binary output of the function contains everything that is needed to understand whether your approximation works or not, it was much more difficult to do.

Double counting

The proof of the Duffin-Schaffer hypothesis is to understand what benefit you get from each of the denominators available to you. To feel this, it will be useful to consider a smaller version of this task.



Suppose you want to approximate all irrational numbers on a segment from 0 to 1. Imagine that all natural numbers from 1 to 10 are available as denominators. The list of possible fractions is quite large. First 1/1, then 1/2 and 2/2, then 1/3, 2/3 and 3/3, and so on, up to 9/10 and 10/10. However, there is no benefit from them.



For example, 2/10 is the same as 1/5, and 5/10 is the same as 1/2, 2/4, 3/6 and 4/8. Before the appearance of the Duffin-Schaffer hypothesis, the Soviet mathematician Alexander Y. Khinchin formulated a hypothesis of a rational approximation similar in breadth. However, his theorem did not take into account the fact that equivalent fractions should be counted only once.





Dimitris Cuculopoulos (left) and James Maynard at the presentation of his evidence at a conference in Italy



“Typically, math for first grade should not affect problem solving,” said Granville. “But in this case, surprisingly, she influenced.”



Therefore, the Duffin-Shaffer hypothesis has a term that counts the number of unique fractions (or reduced fractions) for each denominator. This term is called the φ function of Euler in honor of its inventor, the mathematician of the 18th century Leonard Euler. φ (10) is 4, because between 0 and 1 there are only four reduced fractions with a denominator of 10: 1/10, 3/10, 7/10 and 9/10.



The next step is to calculate how many irrational numbers can be approximated using each of the fractions given. It depends on what size error you are willing to accept. The Duffin-Shaffer hypothesis allows us to choose an error for each of the denominators. For example, for fractions with a denominator of 7, you can take a permissible error of 0.02. For denominator 10, you can take the error 0.01.



Having identified the denominators and terms of errors, it is time to put the networks on irrational numbers. Build your fractions on a number line between 0 and 1, and draw errors in the form of networks extending from the fraction on each side. We can say that all the irrational numbers that fall into the network are “satisfactorily approximated” for the given terms. The question is: how many irrational numbers have you caught?







In any interval of the number line contains an infinite number of irrational numbers, so the exact number of caught irrational numbers can not be written. Instead, mathematicians talk about the proportion of the total number of irrational numbers caught by each fraction. They evaluate these proportions using a concept such as the “measure” of a subset of numbers — it’s something like estimating the number of fish caught by weight rather than quantity.



The Duffin-Schaffer hypothesis suggests adding up all the measures of the subsets of irrational numbers caught by each of the approximating fractions. She represents this number as a large arithmetic sum. Then she makes her main prediction: if this sum goes to infinity, then you approximated almost all irrational numbers; if it gives only a finite value, regardless of how many measures you have summed up, then you were not able to approximate almost any irrational number.



A similar question, whether the sum “diverges” to infinity or “converges” to a finite value, arises in many areas of mathematics. The main statement of the Duffin-Shaffer hypothesis is that if you want to understand whether you can approximate almost all irrational numbers using a given set of denominators and errors, then you only need to know one thing: does the infinite sum of measures diverge to infinity, or converges to the final value.



“In the end, no matter how you decide to evaluate the approximation for each denominator, your success entirely depends on only one thing: whether the infinite sequence diverges or not,” said Waaler.

Decision making

You may wonder: what if numbers approximated by one fraction intersect with numbers approximated by another? Could we take them into account twice when calculating measures?



For some approximation sequences, double counting does not matter. Mathematicians several decades ago proved that this hypothesis holds for approximation sequences consisting of primes. But for many other approximation sequences, double counting is a problem. Therefore, mathematicians could not deal with this hypothesis for 80 years.



The degree to which different denominators catch intersecting sets of irrational numbers is reflected in the number of simple divisors common to all denominators. Consider the numbers 12 and 35. The prime divisors of 12 are 2 and 3. The prime divisors of 35 are 5 and 7. In other words, the common prime factors of 12 and 35 do not - as a result, there are many irrational numbers that can be approximated by fractions of denominators 12 and 35 are not particularly intersect.



What about the denominators of 12 and 20? In 20, prime divisors are 2 and 5, intersecting with divisors 12. In the same way, irrational numbers that can be approximated by fractions with a denominator of 20 are intersected with those that can be approximated by fractions with a denominator of 12. The Duffin-Shaffer hypothesis is the hardest to prove in such situations - when the numbers in the approximation sequence have many common small prime divisors, and the intersection of many subsets of numbers that each of the denominators approximates occurs.



“When many of the denominators from which you choose have many small simple divisors, they start to interfere with each other,” said Sam Chau from Oxford.



The key to solving the hypothesis was to find a way to accurately calculate the overlaps of subsets of irrational numbers that are approximated by denominators that have common prime divisors. For 80 years, no one has been able to do this. Cuculopoulos and Maynard succeeded, finding a completely new point of view on the task.





Mutual Overlay Count



In their new proof, they build a graph from their denominators. They construct them as vertices of the graph and connect the vertices with an edge if they have many common prime divisors. The structure of the graph describes the superposition of the subsets of irrational numbers that each of the denominators approximates. And although this overlay is hard to directly investigate, Kukulopoulos and Maynard found a way to analyze the structure of the graph using tools from graph theory - and the information they needed was found in this way.



"The graph helps to visually understand the task, it is a beautiful language in which you can reflect on the problem," said Kukulopulos.



Cuculopoulos and Maynard proved that the Duffin-Shaffer hypothesis is indeed true: if you were given a list of denominators with valid errors, you can determine whether it is possible to approximate almost all irrational numbers, or it is impossible to do this simply by checking whether the corresponding sum of measures diverges to infinity or converges to a finite value.



This is an elegant test, taking an extensive question of the nature of approximation by rational numbers and reducing it to a single calculated value. Having proved the universality of testing, Cuculopoulos and Maynard did one of the greatest things for mathematics: they gave the final answer to a fundamental question in their field.



“Their proof has become a necessary and sufficient result,” Green said. “I suppose he marks the end of the next chapter in mathematics.”