Math

You may know that ratios of consecutive Fibonacci numbers tend to the golden ratio in the limit. But do know how they tend to the limit? The ratio oscillates, one above the golden ratio, the next below, each getting closer. The plot shows F(n+1) / F(n) where F(n) is the nth Fibonacci number. The height of the horizontal line is the golden ratio.

We can prove that the ratio oscillates by starting with the formula

where φ = (1 + √5)/2 is the golden ratio.

From there we can work out that

This shows that when n is odd, F(n+1) / F(n) is below the golden ratio and when n is even it is above. It also shows that the absolute error in approximating the golden ratio by F(n+1) / F(n) goes down by a factor of about φ² each time n increases by 1.

Related posts:

Honeybee genealogy
Fibonacci numbers at work
Breastfeeding and the golden ratio

Scientific programmers and algebra students start out with analogous bad habits.

Beginning algebra students rush to enter numbers into a calculator. They find it comforting to reduce expressions to floating point numbers as frequently as possible. This is understandable, but it’s a habit they need to break for numerous reasons: it’s more work, harder for a grader to follow, less accurate, etc. Better to do as much calculation as possible with symbols, then stick in numbers at the end.

A similar phenomena happens in scientific programming. We’re anxious to see numbers, so we print out numbers as soon as we produce them. There’s a tendency to sprinkle code with printf statements, then write scripts to scrape text output to gather results.

It’s better to keep numbers in data structures as long as possible, then dump the data to text as the last step. Why? For one thing, the output format might change: instead of a text dump, maybe you’ll want to put the data in a database or format it as an HTML table. More importantly, the “last step” will often change. What was the last step now becomes the next-to-last step because you think of something else to do. So you do more with the data in memory before producing output, rather than scraping the text output.

I quickly learned to delay plugging numbers into algebraic expressions. It took me longer to learn not to output numeric results until the last moment.

I noticed an ad for Super Bowl XLVI on a pizza box this morning. The Roman numeral XLVI does not repeat any character. This brought up a couple questions.

• How many Roman numerals are possible if you’re not allowed to repeat a character?
• Could you write a (reasonably short) regular expression to find all such numbers?

You can post your solutions to either question in the comments.

There has never been universal agreement on the rules for constructing Roman numerals, so your solution would depend on your choice of rules. For our purposes here, assume the valid characters are I, V, X, L, C, D, and M. Also, assume any character can be subtracted from a larger character. For example, you can assume IL is a valid representation of 49.

For a more challenging problem, you can use the more restrictive subtraction rules.

1. I can be subtracted from V and X only.
2. X can be subtracted from L and C only.
3. C can be subtracted from D and M only.
4. V, L, and D can never be subtracted.

Other puzzle posts:

A Renaissance math puzzle
Technology history quiz
A log puzzle

Here’s a pitfall in C# that keeps coming up. C# has a constant double.Epsilon that programmers coming from C naturally assume is the same as C’s DBL_EPSILON. It’s not. In fact, the former is hundreds of orders of magnitude smaller.

C#’s double.Epsilon is the closest floating point number to 0. C’s DBL_EPSILON is the distance between 1 and the closest floating point number greater than 1. Said another way, DBL_EPSILON is the smallest positive floating point number x such that 1 + x != 1, often called “machine epsilon.”

Typically double.Epsilon is on the order of 10^-324 and DBL_EPSILON is on the order of 10^-16. (These values could potentially change depending on the platform, but they hardly ever do.)

C# has no constant corresponding to DBL_EPSILON. This is unfortunate, since this constant appears frequently in numerical software. Why? Because it tells you, for example, when to stop adding series.

If DBL_EPSILON is on the order of 10^-16, that means that if you add two numbers that differ by more than 16 orders of magnitude, the sum doesn’t change. If you’re summing a decreasing series of numbers, say in order to evaluate a Taylor approximation, you might as well stop once the next term is 16 orders of magnitude smaller than the sum. If you keep going past that point, you’ll burn CPU cycles but you won’t change your answer.

DBL_EPSILON is almost always about 10^-16. But by giving it a name, you avoid having 10^-16 as a mysterious constant throughout code. And if your code should ever move to an environment with different floating point resolution, your code will correctly adjust to the new platform.

Related links:

An introduction to numerical programming in C#
Anatomy of a floating point number

According to historian Clifford Truesdell,

… in a listing of all of the mathematics, physics, mechanics, astronomy, and navigation work produced in the 18th century, a full 25% would have been written by Leonard Euler.

Source

Other posts about Euler:

Publish or perish
Even perfect numbers
Platonic solids end Euler’s formula
Mathematical genealogy

By the nth day of Christmas, my true love had sent to me n(n+1)(n+2)/6 gifts.

Explanation and proof here.

The way to know it all is to change the definition of “all.” Schools do this, for example, by defining “all” to mean everything on a test. Then it’s possible for someone to know it all. Schools create the illusion that the world is finite. You may not know everything, but someone does.

The desire to know it all is pernicious. The only way to accomplish it is to shrink your world. That may be OK for a while to focus your attention. The danger is that you can succeed and forget that you started by drawing arbitrary boundaries.

When I was very young, I thought that if I read every volume of the World Book Encyclopedia, I’d know everything. Of course I wouldn’t know everything, only what the editors of the encyclopedia chose to include.

If you want to learn English by first learning all the vocabulary, you’ll never speak English. Even if you learn every word in a particular dictionary, you still haven’t learned every word in the language.

Computer languages are orders of magnitude simpler than human languages, but they’re still too complex to learn exhaustively. If you want to learn every nuance of C++ before writing programs, you’ll never write a program. And if you think this is because C++ is a large language, it’s hardly possible to understand C exhaustively either if you take into account all the subtleties of how features are actually implemented on various platforms.

A common problem in math is how to select a finite sample from an infinite space. Maybe you have a function defined at an infinite number of points and you want to approximate it by sampling it at a carefully chosen finite set of points. This is a good metaphor for life.

Even when things are finite, it’s often very practical to think of them as being infinite. (See Infinite is easier than big.) Many aspects of life are effectively infinite.

Related post:

Evaluate people at their best or at their worst?

Vi Hart’s videos are amazing. Here’s her latest:

Doodling in Math Class: Triangle Party

The previous post presented a problem first posed by Johannes Müller in 1471.

Where you should stand so that a vertical bar appears longest?

To be more precise, suppose a vertical bar is hanging so that the top of the bar is a distance a above your eye level and the bottom is a distance b above your eye level. Let x be the horizontal distance to the bar. For what value of x does the bar appear longest?

In the following diagram, we wish to maximize the angle θ.

Since tangent is an increasing function, it suffices to maximize tan(θ). Let α = θ + β. Then

Now use tan α = a/x and tan β = b/x to reduce the expression above to

Now we have a function of x to maximize. Take the derivative and find where it is zero. The maximum occurs at √ab, the geometric mean of a and b.

However, when Müller proposed his problem in 1471, calculus had not yet been invented, so we can be pretty sure Müller did not take derivatives. I don’t know how (or even if) Müller solved his problem, but the book where I found the problem showed how it could be solved without calculus. The derivation is a little longer, but it only depends on simple algebra and the arithmetic-geometric mean inequality, i.e. the observation that (a + b) /2 ≥ √ab.

Update: Here is a purely geometric solution by George Papademetriou.

Update: See this post for more historical background.

Other posts about the geometric mean:

Means and inequalities
The middle size of the universe

In 1471, Johannes Müller asked where you should stand so that a vertical bar appears longest.

To be more precise, suppose a vertical bar is hanging so that the top of the bar is a distance a above your eye level and the bottom is a distance b above your eye level. Let x be the horizontal distance to the bar. For what value of x does the bar appear longest?

Note that the apparent length of the bar is determined by the size of the angle between your lines of sight to the top and bottom of the bar.

Please don’t give solutions in the comments. I’ll post my solution tomorrow, and you can give your solutions in the comments to that post if you’d like.

Source

Update: See this post for more historical background.

The comments in the previous post touched on surprising applications of math, so I thought I’d expand this theme into it’s own post. Below I’ll give a couple general examples of surprising applications and then I’ll give a couple more personal applications I found surprising.

Number theory has traditionally been the purest of pure mathematics. People study number theory for the joy of doing so, not to make money. At least that was largely true until the advent of public key cryptography. The difficulty of solving certain number theory problems now ensures the difficulty of decrypting private communication, or so we hope. (By the way, I’ve always thought Euler deserved part of the credit for the RSA encryption scheme. Maybe it should be called RSAE encryption. R, S, and A came up with the brilliant idea to apply E’s theorem to cryptography.)

Non-euclidean geometry started as a pure mathematical abstraction. Of course the physical world is Euclidean, but let’s see what happens if we monkey with Euclid’s fifth postulate. Then along came Einstein and suddenly the real world is non-Euclidean.

One personal application of math that I found surprising was using Fibonacci numbers in practical computation. Computing Fibonacci numbers is a computer science cliché, but I actually needed to compute Fibonacci numbers for a numerical integration problem. I wrote up the details in Fibonacci numbers at work.

Another application that surprised me was using the trapezoid rule for real work. The trapezoid rule is a crude numerical integration technique. It’s good for teaching because it’s very simple, but it’s not very accurate. Or so I thought. It’s not very accurate in general, but in the right circumstances, it can be extraordinarily accurate. I explain more in Three surprises with the trapezoid rule.

One surprising non-application has been differential equations. For the past three centuries, differential equations have been at the heart of applied math. One could argue that to first approximation, applied math equals differential equations and supporting material. But I personally have not had nearly as much opportunity to use differential equations professionally as I expected, even though that was my specialization in grad school.

Related posts:

Ten surprises in numerical linear algebra
Impure math

I love this trig identity. I could imagine a student believing it for the wrong reason, a grader counting it wrong for the wrong reason, and a teacher counting it right for the right reason.

sin(x – y) sin(x + y) = (sin(x) – sin(y)) (sin(x) + sin(y))

Someone manipulating symbols unknowingly might think this is obviously true: of course you can replace sin(x + y) with sin(x) + sin(y) and replace sin(x – y) with sin(x) – sin(y). All the world is linear.

Someone with a little more experience would say that this identity obviously cannot be true. After all, sin(x ± y) clearly does not equal sin(x) ± sin(y).

But someone with a little more patience might get a pencil and paper and work out that it indeed is true. Even though naive symbol manipulation would be wrong-headed, in this case it happens to lead you to the right result.

For more examples of a novice and an expert agreeing but someone in between disagreeing, see Coming full circle.

Related posts:

How many trig functions are there?
When does the sum of three numbers equal their product?

From C. S. Lewis:

It has always therefore been one of my main endeavors as a teacher to persuade the young that firsthand knowledge is not only more worth acquiring than secondhand knowledge, but it usually much easier and more delightful to acquire.

This quote comes from the essay On the Reading of Old Books, part of the collection God in the Dock: Essays on Theology and Ethics. Lewis says here that it is easier to read Plato or St. Paul, for example, than to read books about Plato or St. Paul.  Lewis says that the fear of reading great authors

… springs from humility. The student is half afraid to meet one of the great philosophers face to face. He feels himself inadequate and thinks he will not understand him. But if he only knew, the great man, just because of his greatness, is much more intelligible than his modern commentators.

This does not only apply to literature. I see the same theme in math. Sometimes early math papers are easier to read because they are more concrete. When I was a postdoc at Vanderbilt I asked Richard Arenstorf about a theorem attributed to him in a book I was reading. He scoffed that he didn’t recognize it. He had done his work in a relatively concrete setting and did not approve of the fancy window dressing the author had placed around his theorem. I sat in on a few lectures by Arenstorf and found them amazingly clear.

The same theme appears in software development. Sometimes you can dive to the bottom of an abstraction hierarchy and find that things are simpler there than you would have supposed. The intervening layers obscure the substance of the program, making its core seem unduly mysterious. Like a mediocre mind commenting on the work of a great mind, developers who build layers of software around core functionality intend to make things easier but may do the opposite.

Related posts:

Endless preparation
Opening black boxes
Why Shakespeare is hard to read
C. S. Lewis on reading old books

Imagine a set of points in three dimensions. You want to connect the points with the shortest possible network. Sometimes you can make the network shorter by adding extra points. (These extra points are called Steiner points.) How much can extra points help? The answer is worth $1,000.

Here’s an example. Suppose our points are the corners of a unit cube. You can connect these points with a network of length 7. If you add a point in the center of the cube and connect every point to the center, you get a network of length 4 √ 3 = 6.928. So in this case, adding an extra point made it possible to reduce the size of the minimal spanning network by about 1%. You could do better by adding more points.

What is the most you can reduce the length of the minimum spanning network in three dimensions by adding extra points? The question concerns all possible sets of points, not just a particular set like the example above. It is conjectured that the most you can save is about 21.6%. That is, for any set of points, the ratio of the length of the shortest network with extra points to that of the shortest network without extra points is bounded below by

In their new book Magical Mathematics, Persi Diaconis and Ron Graham say “We currently offer a thousand dollars for a proof (or disproof) that this ratio is the best possible.”

As unwieldy as the number above appears, it makes some sense. It looks like the square roots come from repeated applications of the Pythagorean theorem. Someone may be able to reverse engineer the example the conjecture is based on by using the form of the proposed lower bound.

(Diaconis and Graham say that the corresponding problem in two dimensions have been solved and the optimal ratio is √ 3 / 2. However, this paper says that the conjecture is still unresolved, contrary to popular belief.)