Approximation game

The number 22/7 and the pigeon flocks of Peter Gustav Lejeune Dirichlet

In some of the earlier articles on this blog, we talked about the nature of real numbers and the meanings of infinity. The theory outlined in these posts is interesting but also hopelessly abstract. It’s as if we’re inventing make-believe worlds that have no discernible connection to reality.

In today’s post, let’s look at a cool counterexample: a surprising outcome of an numerical experiment that can be backed up with fairly simple proofs, but that makes sense only if you take a step back to consider the construction of real numbers and rationals.

We start by picking a real number r. Your job is to approximate it as closely as possible using a rational fraction a / b with a reasonably small denominator. Is this task easier if r itself is rational or irrational?

Before we dive in, we ought to specify an additional rule: to avoid trivial solutions, we’re looking for close but inexact matches. In other words, your a / b can’t be the same as r. For simplicity, we’ll also stick to positive r and positive fraction denominators throughout the article.

Defining “good”

For a chosen denominator b, it’s pretty easy to find the value of a that gets us the closest to the target r. We must consider two cases: the largest “low-side” fraction that’s still less than r; and the smallest “high-side” fraction greater than r. Again, if there’s a rational fraction that matches r exactly, that solution is prohibited by the rules of the game; we need to pick one of the nearby values instead.

If you wanted to find an exact match, you could try a_ideal = r · b; this makes the a / b fraction equal to r · b / b = r. That said, r · b might not be an integer (or even a rational number), so even without the added constraint, the approach is usually a bust.

If we round the value up (⌈r · b⌉), we get a number that is equal or greater than a_ideal; if it’s greater, the difference between the two values will be less than 1. In other words, we can write the following inequality:

\(a_{ideal} \leq\lceil r · b\rceil < a_{ideal} + 1\)

This is saying that the rounded-up number may be equal to what we need to match r exactly, or it might overshoot the target, but always by less than the minimum possible increment of the numerator in the a / b fraction.

The result is almost what we need, but once more, the rules prohibit approximations that are exactly equal to r. The workaround is to subtract 1 from all sides of the inequality:

\(a_{ideal} - 1 \leq \lceil r · b \rceil -1 < a_{ideal}\)

The effectively tells us that the middle term — ⌈r · b⌉ - 1 — is always less than the value needed to match r, and the difference is never greater than a single tick of the numerator. We’re as close as we can be; the value of a for the optimal low-side approximation (a / b < r) is:

\(a_{low} = \lceil r \cdot b \rceil - 1 \)

We can follow the same thought process to find the high-side estimate (a / b > r):

\(a_{high} = \lfloor r \cdot b \rfloor + 1 \)

Finally, the error (ε) associated with any a / b can be easily calculated as:

\(\varepsilon = \biggl|r - \frac{a}{b}\biggr|\)

We have previously established that if we pick a_low or a_high, the error can’t exceed one tick of the numerator, which works out to ± 1/b. As a practical example, if we’re trying to approximate r = 2 using b = 5, the best inexact solutions are 9/5 = 1.8 on the low side and 11/5 = 2.2 on the high side; they both have an error of 1/b = 0.2.

Next, we’ll try to examine if the error can be less. If we find any approximations that are better than the worst-case scenario — i.e., that satisfy ε < 1/b — we’re gonna call them 1-good.

As an inspection aid, we can also define a normalized score s calculated by multiplying ε by b:

\(s = \varepsilon \cdot b\)

The equation keeps the maximum error at 1 regardless of the denominator we’ve chosen. By that metric, a 1-good approximation is any with a value of s < 1.

The rational test case

Now that we have the mechanics spelled out, let’s take r = 1/4 and analyze the optimal solutions for a couple of initial values of b:

\(\begin{array}{|r|c|c|c|l|} \hline \mathbf{b} & \textbf{Best a/b} & \textbf{Error (ε)} & \textbf{Score }\mathbf{(s)} & \textbf{1-good?} \\ \hline 1 & 0/1 & 1/4 & 1/4 & yes\\ \hline 2 & 0/2 & 1/4 & 1/2 & yes\\ \hline 3 & 1/3 & 1/12 & 1/4 & yes \\ \hline 4 & 0/4 & 1/4 & 1 & no \\ \hline 5 & 1/5 & 1/20 & 1/4 & yes \\ \hline 6 & 2/6 & 1/12 & 1/2 & yes\\ \hline 7 & 2/7 & 1/28 & 1/4 & yes\\ \hline 8 & 1/8 & 1/8 & 1 & no\\ \hline 9 & 2/9 & 1/36 & 1/4 & yes\\ \hline 10 & 2/10 & 1/20 & 1/2 & yes\\ \hline \end{array}\)

We find that many approximations are 1-good (ε < 1/b, aka s < 1) and outperform their peers; for example, 1/5 = 0.2 is better than 2/6 ≈ 0.333. Nevertheless, the results are underwhelming: the values diverge from the 1/b baseline by small factors that are stuck on repeat. If we plot a larger sample, we get:

Approximations of r = 1/4.

In this log-scale plot, I also included a diagonal line that represents error values decreasing with the square of the denominator (1/b²). Approximations for which the error dips below this line would be markedly better than the ones that merely dip below 1/b. We can label these 1/b² solutions as 2-good.

For rational values of r, we get a handful of initial approximations below the 2-good line, but we can prove that the effect can’t last. We start by rewriting r as a fraction of two integers: r = p / q. The 2-goodness criteria is ε < 1/b². We’ve previously defined ε = | r - a/b | and under the rules of the game, valid solutions must have ε greater than zero. Putting it all together, we can write this inequality:

\(0 < \biggl| \frac{p}{q} - \frac{a}{b}\biggr| < \frac{1}{b^2}\)

To tidy up, we can bring the middle part to a common denominator:

\(0 < \biggl| \frac{b\cdot p - a \cdot q}{b \cdot q}\biggr| < \frac{1}{b^2}\)

The denominator is positive, so there’s no harm in taking it out of the absolute-value section and multiplying all sides of the inequality by it:

\(0 < \bigl|b \cdot p - a \cdot q \bigr|< \frac{q}{b}\)

All the variables here are integers. If b ≥ q, the fraction on the right is necessarily ≤ 1. That creates an issue because it implies the following:

\(0 < \bigl|b \cdot p - a \cdot q \bigr|< 1\)

Again, the middle section is made of integers, so it can’t yield fractions; the only solution that satisfies the right-hand inequality is b · p - a · q = 0. Yet, this solution creates a contradiction on the left: 0 < 0. We conclude that there are no integer a, b, p, and q that satisfy the inequality for b ≥ q. If any inexact 2-good approximations of rational numbers exist, they can only exist for b < q.

That’s where we look next. Note that the variable q is the denominator of the number we’re approximating, so it remains constant for a given r. The b < q condition can only be met by a / b pairs with smaller denominators. In other words, if there are any rule-compliant 2-good solutions for rational r, there’s a tight upper bound on their number, and they must be clustered near the beginning of the plot.

This is about as much as we can squeeze out of that stone. Rational numbers appear to be difficult to approximate using other rationals. The only winning move is to cram more digits into a / b.

Approximating irrationals

If rational fractions are tough, it might be tempting to assume that the situation with irrational numbers is going to be even worse. And yet — here’s the plot of a / b approximations for r = π:

Approximating r = π.

Note that the plot keeps dipping below the 2-good line over and over again. And there are some really nice approximations in there! The first arrow points to 22 / 7 ≈ 3.143 (s ≈ 0.009). The second arrow points to an even better one: 355 / 113 ≈ 3.141593 (s ≈ 0.00003). What’s up with that?

Before we dive in, let’s confirm that π is not special. Luckily for us, these patterns crop up for other irrationals too. Here’s an example for e:

Approximating r = e.

And it’s not just profound, transcendental constants; here’s √42:

Approximation error for r = √42.

To understand what’s going on, we need to build a lengthier proof, although we’ll still stay within the realm of middle-school math.

To get going, we make a simple observation: given some number r, we can always split it into an integer part v and a fractional part x that lies in the interval of [0, 1). In other words, 0 ≤ x < 1.

We can also apply this logic to any multiple of r. In particular, for each integer k between 0 and some arbitrary upper bound K, we can calculate k · r and then split the result to obtain a sequence of integer parts (v₀ to v_K) and fractional parts (x₀ to x_K). A simple illustration for π is:

\(\begin{alignat}{1} 0 \cdot \pi \quad &\rightarrow \quad v_0 = 0, &&x_0 = 0 \\ 1 \cdot \pi \quad &\rightarrow \quad v_1 = 3, &&x_1 = 0.1415\ldots \\ 2 \cdot \pi \quad &\rightarrow \quad v_2 = 6, &&x_2 = 0.2831\ldots \\ 3 \cdot \pi \quad &\rightarrow \quad v_3 = 9, &&x_3 = 0.4247\ldots \\ 4 \cdot \pi \quad &\rightarrow \quad v_4 = 12, \;\; &&x_4 = 0.5663\ldots \\ &\ldots \end{alignat}\)

The resulting sequence of fractional parts has K + 1 elements; again, each of the elements falls somewhere on the interval [0, 1).

Next, we divide the [0, 1) interval into K sub-intervals (“buckets”) of equal size:

\(\underbrace{\biggl[0, \frac{1}{K}\biggr)}_\textrm{bucket 1}, \underbrace{\biggl[\frac{1}{K}, \frac{2}{K}\biggr)}_\textrm{bucket 2}, \quad \ldots, \quad \underbrace{\biggl[\frac{K-1}{K}, \frac{K}{K}\biggr)}_\textrm{bucket K}\)

We have K buckets and K + 1 fractional parts tossed into them; no matter how we slice and dice it, at least two elements will necessarily end up in the same bucket. This is the pigeonhole principle.

Again, there’s at least one pair of indices, g < h, such that x_g and x_h both ended up in the same bucket. We don’t know anything about the underlying fractional parts, except that by the virtue of where they ended up, they must be spaced less than 1 / K apart:

\(\bigl|x_h - x_g\bigr| < \frac{1}{K}\)

Each fractional part can be restated as the difference between the original multiple of r and the associated integer part v. That is to say, we can rewrite the earlier inequality as:

\(\bigl| \underbrace{h \cdot r - v_h}_{x_h} - (\underbrace{g \cdot r - v_g}_{x_g}) \bigr| < \frac{1}{K}\)

Next, let’s rearrange the terms to split out expressions that appear to form two independent integers: (v_h - v_g) and (h - g). We label these a and b:

\(\bigl| r \cdot \underbrace{(h - g)}_b - \underbrace{(v_h - v_g)}_a \bigr| < \frac{1}{K}\)

Note that the value of b is positive (because we specified g < h) and that it’s necessarily less or equal than K (because it represents the difference of indices in a list with K + 1 elements). We’ll rely on these properties soon.

The simplified form of the inequality is:

\(\bigl| r \cdot b - a \bigr| < \frac{1}{K} \quad \textrm{(⚑)}\)

For now, pay no attention to the flag; let’s power through and divide both sides by b. We get:

\({\bigl| r - \frac{a}{b} \bigr|}< \frac{1}{K\cdot b}\)

The left-hand portion of the expression is the same as our earlier formula for the approximation error, ε = | r - a / b |. As for the right-hand part, recall that b doesn’t exceed K. Therefore, the expression in the denominator — K · b — involves multiplying b by a value that’s equal or greater than b; the result is equal or greater than b². Putting it all together, we have established that for any real number r, there exists some integer a and b such that a / b satisfies ε < 1/b².

This proof is known as Dirichlet’s approximation theorem. At first blush, it only tells us that a single 2-good approximation is guaranteed for every real. In fact, that guaranteed solution might not even comply with the rules of our game because it might be exact (i.e., ε = 0). So, what was all that about?

To take the next step — and we’re getting close to the finish line! — note that the proof doesn’t put any special constraint on the value of K. Let’s come back to an intermediate equation flagged (⚑), but rewrite it for some definite K₁. We label the associated 2-good pair as a₁ and b₁:

\(\bigl| r \cdot b_1 - a_1 \bigr| < \frac{1}{K_1} \\\)

The left-hand part is equal to the approximation error (| r - a₁ / b₁ |) multiplied by b₁; we already have a name for this value: s. For rational numbers, s may be equal or greater than zero. For irrational numbers, it’s always positive because subtracting a₁ from b₁ · r (where a ∈ ℤ and b₁ ∈ ℤ₊) will always leave some fractional part.

We’re more interested in the irrational case, so let’s look at that first. We have proof of the existence of a₁ and b₁ associated with K₁ — but what if we choose a different starting value K₂? It will give us some new a₂ and b₂; that said, we don’t know for sure if these values are functionally different from a₁ and b₁.

For a moment, let’s assume they’re not: that the resulting 2-good approximation stays the same for any value of K₂. In essence, we’re saying that s is constant. However, s is a positive real, so it stands to reason that once K₂ becomes large enough, the inequality must flip: s ≥ 1/K₂. This produces a contradiction: at that point, the original solution no longer fits. In other words, it must be that for irrational r and some K₂ > K₁, the equation produces a new, distinct a₂ / b₂. This new pair is vulnerable to the same fate as the values it replaced; when approximating irrational numbers, we can keep incrementing K to conjure as many distinct 2-good pairs as we want.

But what about the rational case? Here, r can be written as p / q, while s can conceivably be zero. This is enough to show that the generation process can’t continue indefinitely. First, we rewrite the left-hand expression from the earlier inequality as:

\(\biggl| r \cdot b_2 - a_2 \biggr| = \biggl| \frac{p}{q} \cdot b_2 - a_2 \biggr| = \biggl| \frac{b_2 \cdot p - a_2 \cdot q}{q} \biggr| \)

The numerator of this fraction is an integer (because so are a₂, b₂, p, and q). The denominator is also an integer and stays constant for a given r. It follows that the minimum decrement for the fraction is 1/q. We might start from a non-zero s, but if we keep ramping up K, the solution will inevitably move in discrete steps toward the degenerate case of s = 0. At that point, s satisfies any 1/K and the generation of new 2-good pairs ceases. And keep in mind that in our game, the s = 0 solution doesn’t count.

In other words, you get an infinite supply of surprisingly accurate approximations of irrational numbers, but only a handful of decent results for rationals.

But… why?

Right. The proofs are interesting but don’t offer an intuitive explanation of why these patterns emerge. This is where we go back to my opening remark: it’s easier to grasp the outcome if you look at how rational numbers and reals are “made”.

From the construction of rationals, we know that the spacing between them is arbitrarily close, but at any “magnification level” — for any chosen denominator b — the values divide the continuum into uniform intervals. Uniform spacing also implies maximal spacing: even though there is no upper or lower bound to the values of a / b, they are as far apart as they can be. Any new value inserted onto the number line will necessarily sit “closer” to an existing rational.

The gaps between rationals is where we find irrational numbers. This comes with a lot of weird baggage explored in the previous article, but it also means that for any given irrational r, we have an inexhaustible supply of unexpectedly accurate rational approximations in the vicinity.

Although the puzzle we started with might seem silly, the study of these structures — known as Diophantine approximations — is taken seriously and gets complicated fast. For example, it’s possible to construct so-called Liouville numbers that have an infinite irrationality exponent (endless n-good approximations for any n), but it’s a lot harder to prove that there’s any commonly-encountered number with an irrationality exponent greater than two. In the same vein, algebraic irrationals (e.g., √2) all have an irrationality measure of two, but the proof of this is fiendishly difficult and netted its discoverer the Fields Medal back in 1958.

---

You might also enjoy my other articles about math, including:

How many dimensions is this?

Folks, we have the best π

You gotta think outside the hypercube

I write well-researched, original articles about geek culture, electronic circuit design, algorithms, and more. If you like the content, please subscribe.