Author: John

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.

Typesetting sheet music with AI

Posted on by John

Lilypond is a TeX-like typesetting language for sheet music. I’ve had good results asking AI to generate Lilypond code, which is surprising given the obscurity of the language. There can’t be that much publicly available Lilypond code to train on.

I’ve mostly generated Lilypond code for posts related to music theory, such as the post on the James Bond chord. I was curious how well AI would work if I uploaded an image of sheet music and asked it to produce corresponding Lilypond code.

In a nutshell, the results were hilariously bad as far as the sheet music produced. But Grok did a good job of recognizing the source of the clips.

Test images

Here are the two images I used, one of classical music

and one of jazz.

I used the same prompt for both images with Grok and ChatGPT: Write Lilypond code corresponding to the attached sheet music image.

Classical results

Grok

Here’s what I got when I compiled the code Grok generated for the first image.

This bears no resemblance to the original, turning one measure into eight. However, Grok correctly inferred that the excerpt was by Bach, and the music it composed (!) is in the style of Bach, though it is not at all what I asked for.

ChatGPT

Here’s the corresponding output from ChatGPT.

Not only did ChatGPT hallucinate, it hallucinated in two-part harmony!

Jazz results

One reason I wanted to try a jazz example was to see what would happen with the chord symbols.

Grok

Here’s what Grok did with the second sheet music image.

The notes are almost unrelated to the original, though the chords are correct. The only difference is that Grok uses the notation Δ for a major 7th chord; both notations are common. And Grok correctly inferred the title of the song.

I edited the image above. I didn’t change any notes, but I moved the title to center it over the music. I also cut out the music and lyrics credits to make the image fit on the page easier. Grok correctly credited Johnny Burke and Jimmy Van Heusen for the lyrics and music.

ChatGPT

Here’s what I got when I compiled the Lilypond code that ChatGPT produced. The chords are correct, as above. The notes bear some similarity to the original, though ChatGPT took the liberty of changing the key and the time signature, and the last measure has seven and a half beats.

ChatGPT did not speculate on the origin of the clip, but when I asked “What song is this music from?” it responded with “The fragment appears to be from the jazz standard ‘Misty.'”

Inverse cosine

Posted on by John

In the previous two posts, we looked at why Mathematica and SymPy did not simplify sinh(arccosh(x)) to √(x² − 1) as one might expect. After understanding why sinh(arccosh(x)) doesn’t simplify nicely, it’s natural to ask why sin(arccos(x)) does simplify nicely.

In this post I sketched a proof of several identities including

sin(arccos(x)) = √(1 − x²)

saying the identities could be proved geometrically. Let x be between 0 and 1. Construct right triangle with hypotenuse of length 1 and one side of length x. Call the acute angle formed by these two sides θ. Then cos θ = x, and so arccos(x) = θ, and sin θ = √(1 − x²). This proves the identity above, but only for 0 < x < 1.

If we make branch cuts along (−∞, −1] and [1, ∞) we can extend arccos(z) uniquely by analytic continuation. We can extend the definition to the branch cuts by continuity, but from one direction. We either have to choose the extension to be continuous from above the branch cuts or from below; we have to choose one or the other because the two limits are not equal. As far as I know, everyone chooses continuity from above, i.e. continuity with quadrant II, by convention.

In any case, we can define arccos(z) for any complex number z, and the result is a number whose cosine is z. Therefore the square of its cosine is z², and the square of its sine is 1 − z². So we have

sin²(arccos(z)) = 1 − z².

But does that mean

sin(arccos(z)) = √(1 − z²)?

Certainly it does if we’re working with real numbers, but does it for complex numbers?

Recall what square root means for complex numbers: it is the analytic function with branch cut (−∞, 0] that agrees with the real square root function along the real line, and is defined along the branch cut to be continuous with quadrant II. Since

sin(arccos(z)) = √(1 − z²)

for real −1 < z < 1, the two sides of the equation are equal on a set with a limit point, and so as analytical functions they are equal on their common domain.

The only remaining detail is whether the two functions are equal along the branch cut (−∞, −1] where we’ve extended the function by continuity. As

Since we’ve defined both the arccos and square root functions by continuous extension from the second quadrant, equality on the branch cut also follows by continuity.

llms

Simplifying expressions in SymPy

Posted on by John

The previous post looked at why Mathematica does not simplify the expression Sinh[ArcCosh[x]] the way you might think it should. This post will be a sort of Python analog of the previous post.

SymPy is a Python library that among other things will simplify mathematical expressions. As before, we seek to verify the entries in the table below, this time using SymPy.

\renewcommand{\arraystretch}{2.2} \begin{array}{c|c|c|c} & \sinh^{-1} & \cosh^{-1} & \tanh^{-1} \\ \hline \sinh & x & \sqrt{x^{2}-1} & \dfrac{x}{\sqrt{1-x^2}} \\ \hline \cosh & \sqrt{x^{2} + 1} & x & \dfrac{1}{\sqrt{1 - x^2}} \\ \hline \tanh & \dfrac{x}{\sqrt{x^{2}+1}} & \dfrac{\sqrt{x^{2}-1}}{x} & x \\ \end{array}

Here’s the code:

from sympy import *

x = symbols('x')

print( simplify(sinh(asinh(x))) )
print( simplify(sinh(acosh(x))) )
print( simplify(sinh(atanh(x))) )
print( simplify(cosh(asinh(x))) )
print( simplify(cosh(acosh(x))) )
print( simplify(cosh(atanh(x))) )
print( simplify(tanh(asinh(x))) )
print( simplify(tanh(acosh(x))) )
print( simplify(tanh(atanh(x))) )

As before, the results are mostly as we’d expect:

x
sqrt(x - 1)*sqrt(x + 1)
x/sqrt(1 - x**2)
sqrt(x**2 + 1)
x
1/sqrt(1 - x**2)
x/sqrt(x**2 + 1)
sqrt(x - 1)*sqrt(x + 1)/x
x

Also as before, sinh(acosh(x)) and tanh(acosh(x)) return more complicated expressions than in the table above. Why doesn’t

√(x − 1) √(x + 1)

simplify to

√(x² − 1)

as you’d expect? Because the equation

√(x − 1) √(x + 1) = √(x² − 1)

does not hold for all x. See the previous post for the subtleties of defining arccosh and sqrt for complex numbers. The equation above does not hold, for example, when x = −2.

As in Mathematica, you can specify the range of variables in SymPy. If we specify that x ≥ 0 we get the result we expect. The code

x = symbols('x', real=True, nonnegative=True)
print( simplify(sinh(acosh(x))) )

prints

sqrt(x**2 - 1)

as expected.