A subway topologist

One of my favorite books when I was growing up was the Mathematics volume in the LIFE Science Library. I didn’t own the book, but my uncle did, and I’d browse through the book whenever I visited him. I was too young at the time to understand much of what I was reading.

One of the pages that stuck in my mind was a photo of Samuel Eilenberg. His name meant nothing to me at the time, but the caption titled “A subway topologist” caught my imagination.

… Polish-born Professor Samuel Eilenberg sprawls contemplatively in his Greenwich Village apartment in New York City. “Sometimes I like to think lying down,” he says, “but mostly I like to think riding on the subway.” Mainly he thinks about algebraic topology — a field so abstruse that even among mathematicians few understand it. …

I loved the image of Eilenberg staring intensely at the ceiling or riding around on a subway thinking about math. Since then I’ve often thought about math while moving around, though usually not on a subway. I’ve only lived for a few months in an area with a subway system.

The idea that a field of math would be unknown to many mathematicians sounded odd. I had no idea at the time that mathematicians specialized.

Algebraic topology doesn’t seem so abstruse now. It’s a routine graduate course and you might get an introduction to it in an undergraduate course. The book was published in 1963, and I suppose algebraic topology would have been more esoteric at the time.

 

Read More

Making change

How many ways can you make change for a dollar? This post points to two approaches to the problem, one computational and one analytic.

SICP gives a Scheme program to solve the problem:

(define (count-change amount) (cc amount 5))

(define (cc amount kinds-of-coins)
    (cond ((= amount 0) 1)
    ((or (< amount 0) (= kinds-of-coins 0)) 0)
    (else (+ (cc amount
                 (- kinds-of-coins 1))
             (cc (- amount
                    (first-denomination
                     kinds-of-coins))
                     kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
    (cond ((= kinds-of-coins 1) 1)
          ((= kinds-of-coins 2) 5)
          ((= kinds-of-coins 3) 10)
          ((= kinds-of-coins 4) 25)
          ((= kinds-of-coins 5) 50)))

Concrete Mathematics explains that the number of ways to make change for an amount of n cents is the coefficient of z^n in the power series for the following:

\frac{1}{(1 - z)(1 - z^5)(1 - z^{10})(1 - z^{25})(1 - z^{50})}

Later on the book gives a more explicit but complicated formula for the coefficients.

Both show that there are 292 ways to make change for a dollar.

Read More

Iterative linear solvers as metaphor

Gaussian elimination is systematic way to solve systems of linear equations in a finite number of steps. Iterative methods for solving linear systems require an infinite number of steps in theory, but may find solutions faster in practice.

Gaussian elimination tells you nothing about the final solution until it’s almost done. The first phase, factorization, takes O(n^3) steps, where n is the number of unknowns. This is followed by the back-substitution phase which takes O(n^2) steps. The factorization phase tells you nothing about the solution. The back-substitution phase starts filling in the components of the solution one at a time. In application n is often so large that the time required for back-substitution is negligible compared to factorization.

Iterative methods start by taking a guess at the final solution. In some contexts, this guess may be fairly good. For example, when solving differential equations, the solution from one time step gives a good initial guess at the solution for the next time step. Similarly, in sequential Bayesian analysis the posterior distribution mode doesn’t move much as each observation arrives. Iterative methods can take advantage of a good starting guess while methods like Gaussian elimination cannot.

Iterative methods take an initial guess and refine it to a better approximation to the solution. This sequence of approximations converges to the exact solution. In theory, Gaussian elimination produces an exact answer in a finite number of steps, but iterative methods never produce an exact solution after any finite number of steps. But in actual computation with finite precision arithmetic, no method, iterative or not, ever produces an exact answer. The question is not which method is exact but which method produces an acceptably accurate answer first. Often the iterative method wins.

Successful projects often work like iterative numerical methods. They start with an approximation solution and iteratively refine it. All along the way they provide a useful approximation to the final product. Even if, in theory, there is a more direct approach to a final product, the iterative approach may work better in practice.

Algorithms iterate toward a solution because that approach may reach a sufficiently accurate result sooner. That may apply to people, but more important for people is the psychological benefit of having something to show for yourself along the way. Also, iterative methods, whether for linear systems or human projects, are robust to changes in requirements because they are able to take advantage of progress made toward a slightly different goal.

Related post: Ten surprises from numerical linear algebra

Read More

Every exercise in the book

When I did an independent study course with Ted Odell, he told me to get a copy of De Vito’s Functional Analysis and work every exercise. I don’t recall whether I actually worked every problem, though I believe I at least did most of them. I heard of someone who learned algebraic geometry by working every problem in Hartshorne.

Doing all the exercises in a book isn’t a bad way to learn something, though it depends on the book, what you’re trying to accomplish, and on the quality and quantity of the exercises.

Have you ever gone through a book working every exercise? If so, what book? How was your experience?

 

 

Read More

Swedish superellipse

Sergels torg, Stockholm, Sweden. Photo via Wikipedia.

The fountain in Sergels torg (English: Sergel’s Square) in Sockholm is in the shape of a “superellipse.” Piet Hein proposed this shape as a practical and aesthetically pleasing compromise between a circle and a rectangle.

What Piet Hein dubbed a superellipse is a curve satisfying

|x/a|2.5 + |y/b|2.5 = 1

In the case of Sergels torg, a/b = 6/5. A superellipse is what an analyst would call an Lp ball with p = 2.5 and rescaled axes.

Incidentally, I used curves of this form in a dose-finding method a few years ago. A clinical trial design would pick a, b, and p to match a physician’s desired trade-off between probability of efficacy and probability of toxicity.

Update: A few minutes after I posted this, I realized that there was a bowl on my desk shaped like a superellipse:

The bowl came from Ikea, so there’s another connection to Sweden.

Related post: Volumes of Lp balls

Read More

Sometimes definitions are enough

Sometimes you can apply math just by raiding it for vocabulary. You may not need to apply a single theorem.

This has been a surprise to me. I’m more used to creating a mathematical model so you can compute something or apply some theorem. But sometimes you can move a project along just by providing a name for a concept. A meandering discussion can snap into focus because someone has a name for an idea everyone vaguely understands.

Sometimes it may be clear that only part of a mathematical definition applies. In this case math can guide the discussion by asking whether the rest of the definition applies. “It sounds like we’ve got a widget here. A widget has to have these five properties and clearly we have the first three. Let’s think about whether the last two hold.” The answers don’t have to be positive to be useful. You might realize something important in the process of explaining why your thing is not a widget.

Sometimes a definition may not apply at all and still be useful! “This reminds me of a widget. It’s not a widget in any strict sense. But if it were, this is what we’d do next. I wonder whether we can do something like that.”

 

Read More

An algebra and a calculus

One generation develops an area of math and a second generation comes along to tidy up the definitions. Sometimes this leads to odd vocabulary because the new generation wants to retain terms even as it gives them different meanings.

In high school you get used to hearing about “algebra” and “calculus” as subjects, then the first time you hear someone say “an algebra” or “a calculus” it sounds bizarre. Similarly, once you’re used to hearing about logic, statistics, or topology, it sounds exotic to hear someone say “a logic,” “a statistic,” or “a topology,” something like hearing “a speed of light.”

When I signed up for a topology course, visions of “rubber sheet geometry” danced in my head. I was taken aback when the course started out by defining a topology to be a collection of sets closed under finite intersections and arbitrary unions. Where did the rubber sheet go?

Sometimes when a subject takes on an indefinite article, the new definition comes early in the development. For example, “a statistic” is any function of a random sample, a disappointing definition that comes early in a statistics course. But sometimes the definition with the indefinite article comes much later.

You can take a couple courses in algebra in high school and even a college course in algebra (i.e. groups, rings, and fields) without ever hearing the definition of “an algebra.” And you can take several courses in calculus without ever hearing of “a calculus.”

The phrase “an algebra” can have several meanings, and the phrase “a calculus” even more. The core definition of an algebra is a vector space with a bilinear product. But there are more general ideas of an algebra, some so general that they mean “things and operations on things.” (That’s basically universal algebra.)

Often you put an adjective in front of algebra to specify what kind of algebra you’re talking about: Banach algebra, σ-algebra, Boolean algebra, etc. Usually in mathematics, an adjective in front of a noun narrows the definition. For example, an Abelian group is a particular kind of group. But often an algebra with a qualifier, such as a σ-algebra, is not an algebra by what I called the core definition above.

The idea of “a calculus” is even more vague. If it has a formal definition, I’ve never seen it. A calculus is just a subject with a set of useful rules for calculating things. Sometimes there’s a strong analogy to calculus in the sense of differential calculus, as in the calculus of finite differences, a.k.a. umbral calculus. Sometimes the analogy is more of a stretch, as in λ calculus or π calculus.

So what is the point of this post? I don’t really have one. Just throwing out some half-baked musings.

Read More

Electrical hum

If you hear electrical equipment humming, it’s probably at a pitch of about 60 Hz since that’s the frequency of AC power, at least in North America. In Europe and most of Asia it’s a little lower at 50 Hz. Here’s an audio clip in a couple formats: wav, mp3.

The screen shot above comes from a tuner app taken when I was around some electrical equipment. The pitch sometimes registered at A# and sometimes as B, and for good reason. In a previous post I derived the formula for converting frequencies to musical pitches:

h = 12 log(P / C) / log 2.

Here C is the pitch of middle C, 261.626 Hz, P is the frequency of your tone, and h is the number of half steps your tone is above middle C. When we stick P = 60 Hz into this formula, we get h = -25.49, so our electrical hum is half way between 25 and 26 half-steps below middle C. So that’s between a A# and a B two octaves below middle C.

For 50 Hz hum, h = -28.65. That would be between a G and a G#, a little closer to G.

Update: So why would the frequency of the sound match the frequency of the electricity? The magnetic fields generated by the current would push and pull parts, driving mechanical vibrations at the same frequency.

Read More

Rudyard Kipling and applied math

This evening something reminded me of the following line from Rudyard Kipling’s famous poem If:

… If all men count with you, but none too much …

It would be good career advice for a mathematician to say “Let all areas of math count with you, but none too much.” This warns against dismissing something offhand because you’re sure you’ll never use it, and becoming so fond of something that it becomes a solution in search of a problem.

The same applies to technology: Let all technologies count with you, but none too much.

Related posts:

An array of hammers

A couple definitions of applied math

 

Read More

Quintic root

Here’s a curious result I ran across the other day. Suppose you have a quintic equation of the form z x5x – 1 = 0. (It’s possible to reduce a general quintic equation to this form, known as Bring-Jerrard normal form.) There is no elementary formula for the roots of this equation, but the following infinite series does give a root as a function of the leading coefficient z:

\sum_{n=0}^\infty {5n \choose n} \frac{z^n}{4n+1}

One reason this is interesting is that the series above has a special form that makes it a hypergeometric function of z. You can read more about it here.

I could imagine situations where having such an expression for a root is useful, though I doubt the series would be much use if you just wanted to find the roots of a fifth degree polynomial numerically. Direct application of something like Newton’s method would be much simpler.

Read More

Amazing approximation to e

Here’s an approximation to e by Richard Sabey that uses the digits 1 through 9 and is accurate to over a septillion digits. (A septillion is 1024.)

e \approx \left( 1 + 9^{{-4}^{7ḑot6}}\right)^{3^{2^{85}}}

MathWorld says that this approximation is accurate to 18457734525360901453873570 decimal digits. How could you get an idea whether this claim is correct? We could show that the approximation is near e by showing that its logarithm is near 1. That is, we want to show

3^{2^{85}} \log \left( 1 + 9^{{-4}^{42}\right) \approx 1.

Define k to be 3^(2^85) and notice that k also equals 9^(4^42). From the power series for log(1 + x) and the fact that the series alternates, we have

3^{2^{85}} \log \left( 1 + 9^{{-4}^{42}\right) = k \left( \frac{1}{k} - \frac{1}{2\eta^2} \right)

where η is some number between 0 and 1/k. This tells that the error is extremely small because 1/k is extremely small. It also tells us that the approximation underestimates e because its logarithm is slightly less than 1.

Just how small is 1/k? Its log base 10 is around -1.8 × 10^25, so it’s plausible that the approximation is accurate to 10^25 decimal digits. You could tighten this argument up a little and get the exact number of correct digits.

Read More

Log semiring

Here’s a strange way to do arithmetic on the real numbers.

First, we’ll need to include +∞ and -∞ with the reals.

We define the new addition of two elements x and y to be -log (exp(-x) + exp(-y) ).

We define the new multiplication to be ordinary addition. (!)

In this new arithmetic +∞ is the additive identity and 0 is the multiplicative identity.

This new algebraic structure is called the log semiring. It’s called a semiring because it satisfies all the properties of a ring except that elements don’t necessarily have additive inverses. We’ll get into the details of the definition below.

***

Let’s put a subscript S on everything associated with our semiring in order to distinguish them from their more familiar counterparts. Then we can summarize the definitions above as

  • a +S  b = -log (exp(-a) + exp(-b) )
  • a *S  b = a + b
  • 0S = +∞
  • 1S = 0

Note that if we define

f(a, b) = a +S  b

then

f(a, b) = -g(-a, -b)

where g(a, b) is the soft maximum of a and b.

***

Finally, we list the axioms of a semiring. Note that these equations all hold when we interpret +, *, 0, and 1 in the context of S, i.e. we imagine that each has a subscript S and is as defined above.

  • (a + b) + c = a + (b + c)
  • 0 + a = a + 0 = a
  • a + b = b + a
  • (a * b) * c = a * (b * c)
  • 1 * a = a * 1 = a
  • a * (b + c) = (a * b) + (a * c)
  • (a + b) * c = (a * c) + (b * c)
  • 0 * a = a * 0 = 0

Each of these follows immediately from writing out the definitions.

Read More

Imaginary gold, silver, bronze, …

The previous post gave a relationship between the imaginary unit i and the golden ratio. This post highlights a comment to that post explaining that the relationship generalizes to generalizations of the golden ratio.

GlennF pointed out that taking the larger root of the equation

\phi_n = n + \frac{1}{\phi_n}

defines the golden ratio when n = 1, the silver ratio when n = 2, etc. φn is also the continued fraction made entirely of n‘s.

With this definition, we have

2 \sin \left( i \log \phi_n \right)  = ni

Read More