From Mendeleev to Fourier

Posted on by John

The previous post looked at an inequality discovered by Dmitri Mendeleev and generalized by Andrey Markov:

Theorem (Markov): If P(x) is a real polynomial of degree n, and |P(x)| ≤ 1 on [−1, 1] then |P′(x)| ≤ n² on [−1, 1].

If P(x) is a trigonometric polynomial then Bernstein proved that the bound decreases from n² to n.

Theorem (Bernstein): If P(x) is a trigonometric polynomial of degree n, and |P(z)| ≤ 1 on [−π, π] then |P′(x)| ≤ n on [−π, π].

Now a trigonometric polynomial is a truncated Fourier series

T(x) = a_0 + \sum_{n=1}^N a_n \cos nx + \sum_{n=1}^N b_n \sin nx

and so the max norm of the T′ is no more than n times the max norm of T.

This post and the previous one were motivated by Terence Tao’s latest post on Bernstein theory.

Related posts

Mendeleev’s inequality

Posted on by John

Dmitri Mendeleev is best known for creating the first periodic table of chemical elements. He also discovered an interesting mathematical theorem. Empirical research led him to a question about interpolation, which in turn led him to a theorem about polynomials and their derivatives.

I ran across Mendeleev’s theorem via a paper by Boas [1]. The opening paragraph describes what Mendeleev was working on.

Some years after the chemist Mendeleev invented the periodic table of the elements he made a study of the specific gravity of a solution as a function of the percentage of the dissolved substance. This function is of some practical importance: for example, it is used in testing beer and wine for alcoholic content, and in testing the cooling system of an automobile for concentration of anti-freeze; but present-day physical chemists do not seem to find it as interesting as Mendeleev did.

Mendeleev fit his data by patching together quadratic polynomials, i.e. he used quadratic splines. A question about the slopes of these splines lead to the following.

Theorem (Mendeleev): Let P(x) be a quadratic polynomial on [−1, 1] such that |P(x)| ≤ 1. Then |P′(x)| ≤ 4.

Mendeleev showed his result to mathematician Andrey Markov who generalized it to the following.

Theorem (Markov): If P(x) is a real polynomial of degree n, and |P(x)| ≤ 1 on [−1, 1] then |P′(x)| ≤ n² on [−1, 1].

Both inequalities are sharp with equality if and only if P(x) = ±Tn(x), the nth Chebyshev polynomial. In the special case of Mendeleev’s inequality, equality holds for

T2(x) = 2x² − 1.

Andrey Markov’s brother Vladimir proved an extension of Andrey’s theorem to higher derivatives,

Related posts

[1] R. P. Boas, Jr. Inequalities for the Derivatives of Polynomials. Mathematics Magazine, Vol. 42, No. 4 (Sep., 1969), pp. 165–174

Set intersection and difference at the command line

Posted on by John

A few years ago I wrote about comm, a utility that lets you do set theory at the command line. It’s a really useful little program, but it has two drawbacks: the syntax is hard to remember, and the input files must be sorted.

If A and B are two sorted lists,

    comm A B

prints A − B, B − A, and A ∩ B. You usually don’t want all three, and so comm lets you filter the output. It’s a little quirky in that you specify what you don’t want instead of what you do. And you have to remember that 1, 2, and 3 correspond to A − B, B − A, and A ∩ B respectively.

Venn diagram of comm parameters

A couple little scripts can hide the quirks. I have a script intersect

    comm -12 <(sort "$1") <(sort "$2")

and another script setminus

    comm -23 <(sort "$1") <(sort "$2")

that sort the input files on the fly and eliminate the need to remember comm‘s filtering syntax.

The setminus script computes A − B. To find B − A call the script with the arguments reversed.

Embedded regex flags

Posted on by John

The hardest part of using regular expressions is not crafting regular expressions per se. In my opinion, the two hardest parts are minor syntax variations between implementations, and all the environmental stuff outside of regular expressions per se.

Embedded regular expression modifiers address one of the environmental complications by putting the modifier in the regular expression itself.

For example, if you want to make a grep search case-insensitive, you pass it the -i flag. But if you want to make a regex case-insensitive inside a Python program, you pass a function the argument re.IGNORECASE. But if you put (?i) at the beginning of your regular expression, then the intention to make the match case-insensitive is embedded directly into the regex. You could use the regex in any environment that supports (?i) without having to know how to specify modifiers in that environment.

I was debugging a Python script this morning that worked under one version of Python and not under another. The root of the problem was that it was using re.findall() with several huge regular expression that had embedded modifiers. That was OK up to Python 3.5, then it was a warning between versions 3.6 and 3.10, and it’s an error in versions 3.11 and later.

The problem isn’t with all embedded modifiers, only global modifiers that don’t appear at the beginning of the regex. Older versions of Python, following Perl’s lead, would let you put a modifier like (?i) in the middle of a regex, and apply the modifier from that point to the end of the expression. In the latest versions of Python, you can either place the modifier at the beginning of the regex, or use a scoped modifier like (?:…) in the middle of the expression.

I didn’t want to edit the regular expressions in my code—some had over a thousand characters—so I changed re.findall() to regex.findall(). The third-party regex module is generally more Perl-compatible than Python’s standard re module.

A lesser-known characterization of the gamma function

Posted on by John

The gamma function Γ(z) extends the factorial function from integers to complex numbers. (Technically, Γ(z + 1) extends factorial.) There are other ways to extend the factorial function, so what makes the gamma function the right choice?

The most common answer is the Bohr-Mollerup theorem. This theorem says that if f: (0, ∞) → (0, ∞) satisfies

  1. f(x + 1) = x f(x)
  2. f(1) = 1
  3. log f is convex

then f(x) = Γ(x). The theorem applies on the positive real axis, and there is a unique holomorphic continuation of this function to the complex plane.

But the Bohr-Mollerup theorem is not the only theorem characterizing the gamma function. Another theorem was by Helmut Wielandt. His theorem says that if f is holomorphic in the right half-plane and

  1. f(z + 1) = z f(z)
  2. f(1) = 1
  3. f(z) is bounded for {z: 1 ≤ Re z ≤ 2}

then f(x) = Γ(x). In short, Weilandt replaces the log-convexity for positive reals with the requirement that f is bounded in a strip of the complex plane.

You might wonder what is the bound alluded to in Wielandt’s theorem. You can show from the integral definition of Γ(z) that

|Γ(z)| ≤ |Γ(Re z)|

for z in the right half-plane. So the bound on the complex strip {z: 1 ≤ Re z ≤ 2} equals the bound on the real interval [1, 2], which is 1.

Tighter bounds on alternating series remainder

Posted on by John

The alternating series test is part of the standard calculus curriculum. It says that if you truncate an alternating series, the remainder is bounded by the first term that was left out. This fact goes by in a blur for most students, but it becomes useful later if you need to do numerical computing.

To be more precise, assume we have a series of the form

\sum_{i=1}^\infty (-1)^i a_i

where the ai are positive and monotonically converge to zero. Then the tail of the series is bounded by its first term:

\left|R_n\right| = \left| \sum_{i=n+1}^\infty (-1)^i a_i \right| \leq a_{n+1}

The more we can say about the behavior of the ai the more we can say about the remainder. So far we’ve assumed that these terms go monotonically to zero. If their differences

\Delta a_i = a_i - a_{i+1}

also go monotonically to zero, then we have an upper and lower bound on the truncation error:

\frac{a_{n+1}}{2} \leq |R_n| \leq \frac{a_n}{2}

If the differences of the differences,

\Delta^2 a_i = \Delta (\Delta a_i)

also converge monotonically to zero, we can get a larger lower bound and a smaller upper bound on the remainder. In general, if the differences up to order k of the ai go to zero monotonically, then the remainder term can be bounded as follows.

\frac{a_{n+1}}{2} +\frac{\Delta a_{n+1}}{2^2} +\cdots+ \frac{\Delta^k a_{n+1}}{2^{k+1}} < \left|R_n\right| < \frac{a_n}{2} -\left\{ \frac{\Delta a_n}{2^2} +\cdots+ \frac{\Delta^k a_n}{2^{k+1}} \right\}.

Source: Mark B. Villarino. The Error in an Alternating Series. American Mathematical Monthly, April 2018, pp. 360–364.

Related posts

Powers don’t clear fractions

Posted on by John

If a number has a finite but nonzero fractional part, so do all its powers. I recently ran across a proof in [1] that is shorter than I expected.

Theorem: Suppose r is a real number that is not an integer, and the decimal part of r terminates. Then rk is not an integer for any positive integer k.

Proof: The number r can be written as a reduced fraction a / 10m for some positive m. If s = rk were an integer, then

10mk s = ak.

Now the left side of this equation is divisible by 10 but the right side is not, and so s = rk must not be an integer. QED.

The only thing special about base 10 is that we most easily think in terms of base 10, but you could replace 10 with any other base.

What about repeating decimals, like 1/7 = 0.142857142857…? They’re only repeating decimals in our chosen base. Pick the right base, i.e. 7 in this case, and they terminate. So the theorem above extends to repeating decimals.

[1] Eli Leher. √2 is Not 1.41421356237 or Anything of the Sort. The American Mathematical Monthly, Vol. 125, No. 4 (APRIL 2018), page 346.

Tone row operations

Posted on by John

The previous post introduced the idea of a twelve-tone row, a permutation of the twelve pitch classes of a chromatic scale.

The earlier post also introduced a group of operations on a tone row with elements P, R, I, and RI. Here P, which stands for “prime”, is the identity operator: it leaves the tone row alone. R stands for retrograde, which means to reverse the sequence. I stands for inversion, inverting each of the intervals in the row. If you apply R then I, you get the same result as if you first applied I then R. See the previous post for an example of each.

Do these operations always return a new tone row? In other words, are P(t), R(t), I(t), and RI(t) always distinct for all tone rows t?

It’s easy to see that P(t) and R(t) are always different. The first and last elements of t are different, and so the first element of P(t) does not equal the first element of R(t).

There is one interval that remains the same when inverted, namely the tritone. It’s possible to create a two-tone row that does not change under inversion, such as the sequence [B, F]. A tone row with more than two notes must have an interval that is not a tritone, and so inverting the tone row changes it.

If a tone row t has at least three notes, then P(t), R(t), I(t), and RI(t) are all distinct.

The pitch classes in a tone row are repeated in a cycle, so we might consider all rotations of a tone row to be in a sense the same. In mathematical terms, we can mod out by cyclic permutations.

If we apply R, I, and RI to equivalence classes of tone rows, the results are not always unique. For example, let t be the chromatic scale.

C C♯ D D♯ E F F♯ G G♯ A A♯ B

Then R(t) is

B A♯ A G♯ G F♯ F E D♯ D C♯ C

and I(t) is

C B A♯ A G♯ G F♯ F E D♯ D C♯

which is a rotation of R(t).

The chromatic scale is a boring tone row. For a random tone row t, all the variations P(t), R(t), I(t), and RI(t) will very likely be distinct, including rotations. The following Python code will illustrate the points above and estimate the probability that manipulations of a tone row are distinct even when equating rotations.

import random
import itertools

def inversion(x, m = 12):
    return [(2*x[0] - x[i]) % m for i in range(m)]

def rotate_left(x, n):
    return x[n:] + x[:n]

def rotdiff(x, y):
    for i in range(len(x)):
        if rotate_left(x, i) == y:
            return False
    return True

c = 0
for _ in range(1_000_000):
    P = list(range(12))
    random.shuffle(P) # shuffle in place
    R = list(reversed(P))
    I = list(inversion(P))
    RI = list(reversed(I))
    for pair in combinations([P, R, I, RI], 2):
        assert(pair[0] != pair[1])
        if not rotdiff(pair[0], pair[1]):
            c += 1
print(c)

This generates and tests a million random tone rows. When I ran it, it found 226 tone rows were one manipulation of the tone row was equal to a rotation of another. So when I said the variations are “very likely” to be distinct, you could quantify that as having over a 99.9% chance.

Twelve-tone composition

Posted on by John

Atonal music is difficult to compose because it defies human instincts. It takes discipline to write something so unpleasant to listen to.

One technique that composers use to keep their music from falling into tonal patterns is the twelve-tone row. The composer creates some permutation of the 12 notes in a chromatic scale and then uses these notes strictly in order. The durations of the notes may vary, and the notes may move up or down octaves, but the pitch classes are recycled over and over in order.

There are variations on this technique that allow a small amount of variety, such as allowing the the tone row to be reversed, inverted, or both. The retrograde version of the sequence is the original (prime) sequence of notes in the opposite order. The inverted form of the tone row inverts each of the intervals in the original sequence, going up by k half steps when the original when down by k half steps and vice versa. The retrograde inverted sequence is the inverted sequence in the opposite order.

Here is an example, taken from Arnold Schoenberg’s Suite for Piano, Op. 25.

Some math

Since a tone row is a permutation of 12 notes, there are 12! possible tone rows. However, since the notes of a tone row are played in a cycle, the same sequence of notes starting at a different point shouldn’t count as a distinct tone row. With that way of counting, there are 11! possible tone rows.

The operations of creating the retrograde and inverted forms of a tone row are the generators of an Abelian group. Let P (for prime) be the null operation, leaving a sequence alone. Then the elements of the group are P, R, I, and RI (= IR). The two generators have order 2, i.e. R² = I² = P. Therefore the group is isomorphic to ℤ2 × ℤ2.

Although I enjoy music and math, I do not enjoy most attempts to use math to compose music. I do not like atonal music, though I do like some “math rock.” It seems that math applied to rhythm results in more palatable music than math applied to melody.

Update: More math in the next post. Do the applications of R, I, and RI always produce different sequences of notes? What if you consider two rotations of a tone row to be equivalent?

A concert story

When I was in college I often walked from my dorm over the music building for concerts. I probably heard more concerts in college than I have heard ever since.

One night I went to an organ concert. At the end of the concert the organist took melodies on strips of paper that he had not seen before and improvised a fugue on each. After the concert I ran into a friend in the music building who had not been to the concert. I enthusiastically told him how impressed I was by the improvised fugues, especially the last one that sounded like Schoenberg tone row.

The organist overhead my conversation and walked up to me and said that he was impressed that I recognized the Schoenberg tone row. To be fair, I did not recognize the music per se. The music sounded random, and I came up with the only example of random music I could think of, and said it sounded like a Schoenberg tone row. I certainly did not say “Ah, yes. That was Schoenberg’s tone row from ….” It was a lucky guess.

Langford series

Posted on by John

Notice anything special about the following sequence?

8 6 10 3 1 11 1 3 6 8 12 9 7 10 4 2 5 11 2 4 7 9 5 12

Each of the numbers 1 through 12 appear twice. Between the two 1s there is one number. Between the two 2s there are two numbers. Between the two 3s there are three numbers, etc.

Langford’s problem of order n is to arrange two copies of the integers 1 through n so that there are k numbers between the two ks. This problem has a solution if and only if n is congruent to 0 or 3 mod 4.

You can find much more on Langford’s problem here.