Solving hard problems

We help companies solve hard problems in mathematics, statistics, and computing. Let’s explore how we might work together.

Nuclear Tornadoes

Posted on 29 May 2020 by John

Tornado with lightning

I’ve recently started reading One Giant Leap, a book about the Apollo missions. In a section on nuclear testing, the book describes what was believed to be a connection between weapon tests and tornadoes.

In 1953 and 1954 there were all-time record outbreaks of tornadoes across the US, accompanied by fierce thunderstorms. The belief that the tornadoes were caused by the atomic testing in Nevada was so common among the public that Gallup conducted a poll on the topic, which showed that 29% of Americans thought that A-bombs were causing tornadoes many states away; 20% couldn’t say whether they were or not. Members of Congress required the military to provide data on any connection.

It wasn’t unreasonable at the time to speculate that there could be a connection between nuclear testing and tornadoes. No one knew much about the effects of nuclear explosions or about the causes of tornadoes in 1954. But here’s the part that was preventable:

In fact it turned out there weren’t really more tornadoes in those years; it was just that tornado reporting and tracking had gotten much more effective and thorough.

Once the public got the impression that tornadoes were becoming more frequent, confirmation bias would firm up that impression with each tornado citing.

I imagine someone knew this in 1954. Someone must have looked at the data and said “Hey, wait a minute.” This person was probably ridiculed by the few who even listened.

Update: I found a newspaper article cited in One Giant Leap: “A-Bomb Link to Tornadoes is Discounted,” Washington Post. November 18, 1954. The article quoted D. Lee Harris of the United States Weather Bureau saying “Improvement in tornado reporting is largely responsible for the great increase in total number of the storms reported in recent years.”

The Gallup poll was prior to the article cited. It would be interesting if there had been a follow-up poll to see see how much impact Harris’ statement had on public opinion.

Fundamental Theorem of Arithmetic

Posted on 28 May 2020 by John

It’s hard to understand anything from just one example. One of the reason for studying other planets is that it helps us understand Earth. It can even be helpful to have more examples when the examples are purely speculative, such as xenobiology, or even known to be false, i.e. counterfactuals, though here be dragons.

The fundamental theorem of arithmetic seems trivial until you see examples of similar contexts where it isn’t true. The theorem says that integers have a unique factorization into primes, up to the order of the factors. For example, 12 = 2² × 3. You could re-order the right hand side as 3 × 2², but you can’t change the list of prime factors and their exponents.

I was unimpressed when I first heard of fundamental theorem of arithmetic. It seemed obvious, and hardly worth distinguishing as the fundamental theorem of arithmetic. (If not this, what would the fundamental theorem of arithmetic be? Any candidates? I didn’t have one, and still don’t.)

In order to appreciate the unique factorization property of the integers, mathematicians created algebraic structures analogous to the integers, i.e. rings, in which unique factorization may or may not hold. In the language of ring theory, the integers are a “unique factorization domain” but not all rings are.

An easy way to create new rings is to extend the integers by adding new elements, analogous to the way the complex numbers are created by adding i to the reals.

If you extend the integers by appending √-5, i.e. using the set of all numbers of the form a + b√-5 where a and b are integers, you get a ring that is not a unique factorization domain. In this ring, 6 can be factored as 2 × 3 but also as (1 + √-5)(1 – √-5).

However, you can extend the integers by other elements and you may get a unique factorization domain. For example, the Eisenstein [1] integers append (-1 + i√ 3)/2 to the ordinary integers, and the result is a unique factorization domain.

The Fundamental Theorem of Algebra

Posted on 27 May 2020 by John

This post will take a familiar theorem in a few less familiar directions.

The Fundamental Theorem of Algebra (FTA) says that an nth degree polynomial over the complex numbers has n roots. The theorem is commonly presented in high school algebra, but it’s not proved in high school and it’s not proved using algebra! A math major might see a proof midway through college.

You’re most likely to see a proof of the Fundamental Theorem of Algebra in a course in complex analysis. That is because the FTA depends on analytical properties of the complex numbers, not just their algebraic properties. It is an existence theorem that depends on the topological completeness of the complex numbers, and so it cannot be proved from the algebraic properties of the complex numbers alone.

(The dividing lines between areas of math, such as between algebra and analysis, are not always objective or even useful. And for some odd reason, some people get touchy about what belongs where. But the categorization of math subjects implicit in the creation of course catalogs puts the proof of the FTA on the syllabus of complex analysis courses, sometimes topology courses, but not algebra courses.)

Gauss offered a proof of the FTA in 1799, but his proof was flawed because he implicitly assumed the Jordan curve theorem, a seemingly obvious theorem that wasn’t rigorously proven until 1911. In keeping with our the theme above, the hole was due to overlooking a topological subtlety, not due to an algebraic mistake.

The proof of the FTA using complex analysis is a quick corollary of Liouville’s theorem: If a function is analytic everywhere in the complex plane and bounded, then it must be constant. Assume a non-constant polynomial p(z) is nowhere zero. Then 1/p(z) is analytic everywhere in the complex plane. And it must be bounded because p(z) → ∞ as |z| → ∞. We have a contradiction, so p(z) must be zero for some z.

The usual statement of the FTA says that an nth degree polynomial has n roots, but the proof above only says it must have one root. But you can bootstrap your way to the full result from there. The analyst tells the algebraist “I’ve done the hard part for you. You can take it from there.”

In some sense the rest of the theorem properly belongs to algebra, because the bookkeeping of how to count zeros is more of an algebraic matter. In order for every nth degree polynomial to have exactly n roots, some roots must be counted more than once. For example, (z – 42)² has a double root at 42. From a strictly analytical view point, there is one point where (z – 42)² is zero, namely at z = 42, but it is useful, even to analysts, to count this as a double root.

It may seem pedantic, or even Orwellian, so say that some roots count more than others. But a great deal of theorems are simpler to state if we agree to count roots according to multiplicity. This idea is taken further in algebraic geometry. For example, Bézout’s theorem says that if X is an mth degree curve and Y is an nth degree curve, then X and Y intersect in mn points. It takes a lot of prep work for this theorem to have such a simple statement. You have to count intersections with multiplicity, and you have to add points at infinity.

Liouville’s theorem’s is useful for more than proving the FTA. It is also useful in studying elliptic functions. (I believe Liouville proved his theorem for this purpose. Someone into math history can check me on that.) If an analytic function is periodic in two distinct directions in the complex plane (more on that here), it must have a singularity because otherwise it would be bounded.

The FTA may seem less profound than it is. You might object that of course every nth degree polynomial has n roots: you’ve cheated by adding in the roots you need. But that’s not true. The complex numbers are created by adding in one root to one particular polynomial, namely z² = -1. The impressive part is that adding one root of one particular quadratic polynomial is enough to force all quadratic polynomials and even all higher degree polynomials also to also have roots.

This does not happen in finite fields. A finite field cannot be algebraically complete. If you extend a finite field so that every quadratic equation has a root, then only quadratic equations have roots. It does not follow that cubic polynomials, for example, have roots. You could extend it further so that all cubic equations have roots, but then 4th degree polynomials will not all have roots. If you stop the extension process after any finite number of steps, there will be some polynomials without roots.

Fundamental theorem of calculus generalized

Posted on 23 May 2020 by John

The first fundamental theorem of calculus says that integration undoes differentiation.

The second fundamental theorem of calculus says that differentiation undoes integration.

This post looks at the fine print of these two theorems, in their basic forms and when generalized to Lebesgue integration.

Second fundamental theorem of calculus

We’ll start with the second fundamental theorem because it’s simpler. In it’s basic form, it says that if f is a continuous function on an open interval I, and a is a point in I, then the function F defined by

$F(x) = \int_a^x f(t)\, dt$

is an antiderivative for f on the interval I, i.e.

for all x in I. In that sense differentiation undoes integration.

If we remove the requirement that f be continuous, we still have F‘ = f almost everywhere as long as f is absolutely integrable, i.e. the integral of |f| over I is finite. In more detail,

at every Lebesgue point x, i.e. every point x that satisfies

$\lim_{\varepsilon \to 0} \, \frac{1}{2\varepsilon}\int_{x - \varepsilon}^{x + \varepsilon} |f(x) - f(y)| \ dy = 0$

First fundamental theorem of calculus

The first fundamental theorem of calculus says that if the derivative of F is f and f is continuous on an interval [a, b], then

$\int_a^b f(x) \, dx = F(b) - F(a)$

So if F has a continuous derivative, then integration undoes differentiation. What if F is continuous and but differentiable at almost every point rather than at every point? Then the theorem doesn’t necessarily hold. But the theorem does hold if we require F to be absolutely continuous rather than just continuous.

A function is absolutely continuous if it maps sets of measure zero to sets of measure zero. It’s not easy to imagine continuous functions that are not absolutely continuous, but Cantor’s function, a.k.a. the Devil’s staircase, takes the Cantor set, a set of measure zero, to a set of measure one.

The usual definition of absolute continuity, equivalent to the one above, takes the ordinary definition of continuity and chops into n pieces. That is, for every ε > 0 and for every n, there exists a δ > 0 such that for any collection of n intervals of total length less than δ, the sum of the variation in f over all the intervals is less than ε. If n = 1 this is the definition of uniform continuity, so absolute continuity is a more demanding criterion than uniform continuity.

Square wave, triangle wave, and rate of convergence

Posted on 22 May 2020 by John

There are only a few examples of Fourier series that are relatively easy to compute by hand, and so these examples are used repeatedly in introductions to Fourier series. Any introduction is likely to include a square wave or a triangle wave [1].

By square wave we mean the function that is 1 on [0, 1/2] and -1 on [1/2, 1], extended to be periodic.

square wave

Its nth Fourier (sine) coefficient is 4/nπ for odd n and 0 otherwise.

By triangle wave we mean 1 – |2x – 1|, also extended to be periodic.

triangle wave

Its nth Fourier (cosine) coefficient is -2/(nπ)² for odd n and 0 otherwise.

This implies the Fourier coefficients for the square wave are O(1/n) and the Fourier coefficients for the triangle wave are O(1/n²). (If you’re unfamiliar with big-O notation, see these notes.)

In general, the smoother a function is, the faster its Fourier coefficients approach zero. For example, we have the following two theorems.

If a function f has k continuous derivatives, then the Fourier coefficients are O(1/n^k).
If the Fourier coefficients of f are O(1/n^k+1+ε) for some ε > 0 then f has k continuous derivatives.

There is a gap between the two theorems so they’re not converses.

If a function is continuous but not differentiable, the Fourier coefficients cannot decay any faster than 1/n², so the Fourier coefficients for the triangle wave decay as fast as they can for a non-differentiable function.

Clipped sine waves

Posted on 20 May 2020 by John

One source of distortion in electronic music is clipping. The highest and lowest portions of a wave form are truncated due to limitations of equipment. As the gain is increased, the sound doesn’t simply get louder but also becomes more distorted as more of the signal is clipped off.

Clipping 0.2

For example, here is what a sine wave looks like when clipped 20%, i.e. cut off to be between -0.8 and 0.8.

Sine clipped at 0.8

A simple sine wave has only one Fourier component, itself. But when we clip the sine wave, we move energy into higher frequency components. We can see that in the Fourier components below.

Fourier coefficients of sine clipped at 0.8

You can show by symmetry that the even-numbered coefficients are exactly zero.

Clipping 0.6

Here are the corresponding plots for 60% clipping, i.e. the absolute value of the signal is cut off to be 0.4. First the signal

Sine clipped at 0.8

and then its Fourier components.

Fourier coefficients of sine clipped at 0.8

Here are the first five sine waves with the amplitudes given by the Fourier coefficients.

Fourier components

And here we see how the of the sines above do a pretty good job of reconstructing the original clipped sine. We’d need an infinite number of Fourier components to exactly reconstruct the original signal, but the first five components do most of the work.

Adding up the first five Fourier components

Continuous range of clipping

Next let’s look at the ratio of the energy in the 3rd component to that of the 1st component as we continuously vary the amount of clipping.

Ratio of energy in 3rd harmonic to fundamental

Now for the 5th harmonic. This one is interesting because it’s not strictly increasing but rather has a little bump before it starts increasing.

Ratio of energy in 5th harmonic to fundamental

Finally, here’s the ratio of the energy in all higher frequencies to the energy in the fundamental.

Ratio of energy in all higher frequences combined to fundamental

Inverse optimization

Posted on 18 May 2020 by John

This morning Patrick Honner posted the image below on Twitter.

The image was created by Robert Bosch by solving a “traveling salesman” problem, finding a nearly optimal route for passing through 12,000 points.

I find this interesting for a couple reasons. For one thing, I remember when the traveling salesman problem was considered intractable. And in theory it still is! But in practice it is not difficult now to find nearly optimal solutions for very large traveling salesman problems.

Another reason I find this interesting is that there is a higher-level problem in the background, the problem of constructing a problem whose solution gives you a desired image.

Robert Bosch is showing us a solution to two problems. The image above is the solution to an optimization problem, and the problem it solves is itself the solution to another problem in the background. He’s doing a sort of inverse optimization, searching for an optimization problem. He goes into some of his techniques in his recent book Opt Art which I wrote about here.

This gets back to an argument I’ve had with statisticians who are resistant to innovative methods. They’ll say “But our method is optimal. You can’t do any better by definition. End of discussion!” But every method is optimal by some criteria. The question is whether the method is optimal by criteria appropriate to the problem at had or whether it is only optimal according to criteria that were mathematically convenient at the time it was formulated.

Robert Bosch has shown beautifully that any image can be viewed as the solution to an optimization problem. Of course the problem has to be crafted for the image. If he were solving a naturally occurring problem, such as planning a tour for an actual sales rep, and the solution had an uncanny resemblance to a piece of art by Michelangelo, that would be astounding.

Accessible math posts

Posted on 17 May 2020 by John

Several people have told me they can’t understand most of my math posts, but they subscribe because they enjoy the occasional math post that they do understand. If you’re in that boat, thanks for following, and I wanted to let you know there have been a few posts lately that are more accessible than you might think.

The posts I refer to don’t require any advanced math to follow, though they may require some advanced math to fully appreciate.

For example, my latest post on means and sums only requires pre-calculus math to understand, though it introduces ideas that usually aren’t introduced until they’re needed in more advanced courses.

A few days ago I started what turned into a series of four blog posts, all consequences of combining the binomial theorem and Euler’s theorem. Here are the four posts:

These posts do not require calculus, and should be mostly accessible with high school math.

Chebyshev polynomials come up several times in these posts. High school math will not prepare you to appreciate the significance of these particular polynomials, but you can follow along by ignoring the name and just thinking “OK, they’re polynomials. I know what a polynomial is.”

Sum and mean inequalities move in opposite directions

Posted on 17 May 2020 by John

It would seem that sums and means are trivially related; the mean is just the sum divided by the number of items. But when you generalize things a bit, means and sums act differently.

Let x be a list of n non-negative numbers,

$x = (x_1, x_2, \ldots, x_n)$

and let r > 0 [*]. Then the r-mean is defined to be

$M_r(x) = \left( \frac{1}{n} \sum_{i=1}^n x_i^r \right)^{1/r}$

and the r-sum is define to be

$S_r(x) = \left( \sum_{i=1}^n x_i^r \right)^{1/r}$

These definitions come from the classic book Inequalities by Hardy, Littlewood, and Pólya, except the authors use the Fraktur forms of M and S. If r = 1 we have the elementary mean and sum.

Here’s the theorem alluded to in the title of this post:

As r increases, M_r(x) increases and S_r(x) decreases.

If x has at least two non-zero components then M_r(x) is a strictly increasing function of r and S_r(x) is a strictly decreasing function of r. Otherwise M_r(x) and S_r(x) are constant.

The theorem holds under more general definitions of M and S, such letting the sums be infinite and inserting weights. And indeed much of Hardy, Littlewood, and Pólya is devoted to studying variations on M and S in fine detail.

Here are log-log plots of M_r(x) and S_r(x) for x = (1, 2).

Plot of M_r and S_r

Note that both curves asymptotically approach max(x), M from below and S from above.

[*] Note that r is only required to be greater than 0; analysis books typically focus on r ≥ 1.

Pretending OOP never happened

Posted on 15 May 2020 by John

I ran across someone recently who says the way to move past object oriented programming (OOP) is to go back to simply telling the computer what to do, to clear OOP from your mind like it never happened. I don’t think that’s a good idea, but I also don’t think it’s possible.

Object oriented programming, for all its later excesses, was a big step forward in software engineering. It made it possible to develop much larger programs than before, maybe 10x larger. Someone might counter by saying that programs had to be 10x larger because of all the overhead of OOP, but that’s not the case. OOP does add some overhead, and the amount of overhead grew over time as tools and frameworks became more complicated, but OOP made it possible to write programs that could not have been written before.

OOP provides a way for programmers to organize their code. It may not be the best way, depending on the problem, but the way to move past OOP is to replace it with another discipline. And I imagine most people who have learned and then rejected OOP do just that, whether they realize it or not. Maybe they retain some organizational patterns that they learned in the context of OOP.

That has been my experience. I hardly ever write classes anymore; I write functions. But I don’t write functions quite the way I did before I spent years writing classes.

And while I don’t often write classes, I do often use classes that come from libraries. Sometimes these objects seem like they’d be better off as bare functions, but I imagine the same libraries would be harder to use if no functions were wrapped in objects.

There are many alternatives to OOP for organizing code. I generally like functional programming, but in my experience there’s a hockey stick effort curve as you try to push the purity to 100%. James Hague said it well:

100% pure functional programing doesn’t work. Even 98% pure functional programming doesn’t work. But if the slider between functional purity and 1980s BASIC-style imperative messiness is kicked down a few notches — say to 85% — then it really does work. You get all the advantages of functional programming, but without the extreme mental effort and unmaintainability that increases as you get closer and closer to perfectly pure.

It’s possible, and a good idea, to develop large parts of a system in purely functional code. But someone has to write the messy parts that interact with the outside world.