How do we know that polar triangles exist? There is a geometric construction that starts with a spherical triangle and constructs a unique new spherical triangle, and one can show that this new triangle has the angles and sides described in the previous post.

There is also a linear algebraic construction of polar triangles, and that’s the topic of this post. In a nutshell, take your sphere to be the unit sphere in 3D. Write the coordinates of each vertex as the columns of a matrix. Invert that matrix and normalize each row. Then the rows are the coordinates of the polar vertices.

This process is an involution: the polar of the polar of a triangle is the original triangle.

The following Python code illustrates the process described above. It begins with a triangle on the globe with vertices A, B, and C at Chicago, Quito, and Paris respectively. It computes the polar triangle, then computes the polar of that, and shows that the result is the original triangle.

import numpy as np

def latlon_to_cartesian(lat_deg, lon_deg):
    lat = np.radians(lat_deg)
    lon = np.radians(lon_deg)
    x = np.cos(lat) * np.cos(lon)
    y = np.cos(lat) * np.sin(lon)
    z = np.sin(lat)
    return np.array([x, y, z])

def cartesian_to_latlon(v):
    v = v / np.linalg.norm(v)
    lat = np.degrees(np.arcsin(np.clip(v[2], -1, 1)))
    lon = np.degrees(np.arctan2(v[1], v[0]))
    return lat, lon

def polar_triangle(M):
    """
    Polar triangle via matrix inversion.
    M: 3×3 matrix with columns = unit vectors of the original vertices.
    Returns 3×3 matrix whose columns are the polar unit vectors.
    """
    Minv = np.linalg.inv(M)
    # Normalize each row of the inverse (rows are parallel to the polar directions)
    polar_rows = Minv / np.linalg.norm(Minv, axis=1, keepdims=True)
    return polar_rows.T          # columns = polar vertices

# Original vertices (Chicago, Quito, Paris)
A = latlon_to_cartesian(41.85003, -87.65005)
B = latlon_to_cartesian(-0.22985, -78.52495)
C = latlon_to_cartesian(48.85341,  2.3488)

M = np.column_stack([A, B, C])
print("M (columns = original vertices):\n", M)
print("det(M) =", np.linalg.det(M))

# Polar triangle
M_prime = polar_triangle(M)
print("\nM' (columns = polar vertices):\n", M_prime)

print("\nPolar geographic coordinates (lat, lon):")
for name, col in zip(["A'", "B'", "C'"], range(3)):
    print(name, cartesian_to_latlon(M_prime[:, col]))

# Polar of the polar
M_double = polar_triangle(M_prime)
print("\nPolar-of-polar matrix:\n", M_double)
print("max |difference from original M| =",
      np.max(np.abs(M_double - M)))

cos(c) = cos(a) cos(b) + sin(a) sin(b) cos(C).

But that’s just one of two laws of cosines on a sphere. The equation above is the law of cosines for sides. The law of cosines for angles is typographically very similar, just inverting the case of the letters used as arguments.

cos(C) = cos(A) cos(B) + sin(A) sin(B) cos(c).

Incidentally, the law of cosines for sides shows how the sides of a spherical triangle determine the angles. The law of cosines for angles shows how, unlike in the case of plane geometry, angles determine the sides.

Two kinds of angles

Let’s back up and say what the letters refer to. As is conventional in plane geometry, the sides of a triangle are a, b, and c, and the angles are A, B, and C, with a being the side opposite the angle A, and similarly for the other letters.

However, unlike plane geometry, the sides are also angles, but of a different sort. The sides a, b, and c are central angles, and the “angles” A, B, and C are dihedral angles.

The sides are arcs of a great circle. The side a, for example, is a portion of a great circle, running between the vertices at B and C [1]. Think of a plane that contains the center of the sphere O and the vertices B and C. The length of a is the angle at O.

The angles A, B, and C are the angles at which great circles meet. In the formalism of differential geometry, these angles exist in the tangent plane at the vertices. These angles are intrinsic, measured along the (tangent plane of) the surface of the sphere. The central angles are extrinsic, measured in a plane that cuts through the sphere to its center.

Polar triangles

Now because sides are angles and vertices are angles, we can interchange the two kinds of angles to form the polar triangle of the original triangle. This is a new triangle whose central angles are the complements of the original dihedral angles, and whose dihedral angles are the complements of the original central angles. In symbols,

a′ = π − A
b′ = π − B
c′ = π − C
A′ = π − a
B′ = π − b
C′ = π − c

Now we return to the laws of cosines at the top of the post: the law of cosines for angles is the law of cosines for sides applied to the polar triangle. Every equation in spherical trigonometry has a polar counterpart.

[1] There’s some overloaded terminology here, just as in plane geometry. The symbol a is used to denote a side of a triangle and also the length of that side. The symbol A is used to denote both a vertex and the dihedral angle at that vertex.

I got an error message that said

error: The script contains multiple PEP 723 metadata blocks

I searched on what that means, then took out the blank line in my header

#!/usr/bin/env -S uv run --script

# /// script
# dependencies = ["pyperclip"]
# ///

but I still got the same error message.

The script in question copies miscellaneous snippets of text to the clipboard for me. One of those snippets is the header block that uv requires. The script contains the header block marker # ///, and that was the source of the problem.

According to Grok

The PEP 723 parser is purely textual (it uses a regex that scans the whole file). It does not understand Python syntax, so the # /// sequences inside your triple-quoted string are treated as a second metadata block.

It suggested changing my quoted string to use # / / / and then take out the extra spaces:

"""#!/usr/bin/env -S uv run --script
# / / / script
# dependencies = ["numpy", "matplotlib"]
# / / /
import numpy as np
import matplotlib.pyplot as plt
""".replace("# / / /", "# ///")

This is a dirty hack, but it works.

As I mentioned in an earlier post, eMudrha was using the numbers 4, 56, 115, 155, 156, 230, and 237 as secret keys. I haven’t seen details of how this happened, but in this post I’ll give a plausible account of how it might have happened, what someone could have done to produce those results. I’m not trying to do forensic analysis on this specific incident, just exploring what someone might do.

eMudrha was using the NIST elliptic curve P-384, and a secret key should be a random number chosen between 1 and 2³⁸⁴. That upper bound isn’t exactly correct, but it’s close. See this post if you want to know the exact number.

Someone might have chosen numbers up to 384 rather than 2³⁸⁴ out of ignorance. Or they might done so by a typo. Maybe they generated a random value that might have been larger than 2³⁸⁴ and then intended to reduce the number mod 2³⁸⁴, but instead of typing

% 2**384

they typed

% 384

It seems more likely, however, that somehow someone took one byte of a random value because all the keys are less than 2⁸ = 256.

The probability of choosing seven numbers from 1 to 384 and all being less than or equal to 237 is around 0.034. But the same probability for numbers chosen between 1 and 256 is about 0.60.

y² = x³ + ax + b

with x and y in F. Typically in cryptography the field F is the integers mod p where p is a very large prime number.

The number of points on E is roughly the number of elements in F. So for a curve over the integers mod p, the curve has roughly p points.

The next section will give an intuitive argument for why the number of points on E should be roughly the number of elements in F. Then the next section will give a rigorous bound. Then after that we’ll work through an example.

Hand-wavy estimate

For a prime p, half the non-zero integers mod p have a square root and half do not. The ones that do have a square root have two square roots. For example, look at the integers mod 7. The numbers 1, 2, and 4 have square roots but the numbers 3, 5, and 6 do not. Here’s a little bit of Python to verify this.

>>> [x**2 % 7 for x in range(1,7)]
[1, 4, 2, 2, 4, 1]

Now if we wanted to count the number of solutions to

y² = x (mod p)

we’d find it equals p. That’s because (0, 0) is a point on the curve, and for (p − 1)/2 values of x there are two values of y, and for the remaining values of x there are no values of y.

To put it another way, if we pick a value of x at random, it will have two square roots or no square roots with roughly equal probability.

Now suppose we pick an x at random and compute x³ + ax + b. We might guess that this process scatters x values in an unbiased way, being no more likely to produce a square than a non-square. Our guess turns out to be approximately correct, though there may be a small bias in favor of squares or non-squares.

Precise bound

Hasse’s theorem gives a precise bound on the number of points on an elliptic curve E. It says

#E = p + 1 − t

where

|t| ≤ 2√p.

So if p is on the order of 2ⁿ, the number of points on E is also on the order of 2ⁿ because √p is far smaller than p. That’s all you need to know at a high level. The rest of this post will look at a particular example in full detail.

Detailed example

The NIST curve P-384 has been in the news lately. For this curve, the based field is integers modulo a 384-bit prime p and so the number of points on the curve is also 384-bit number. Specifically

p = 2³⁸⁴ − 2¹²⁸ − 2⁹⁶ + 2³² − 1,

and so we know a priori that the number of points on the curve equals 2³⁸⁴ plus or minus a factor less than 2¹⁹³.

The number of points on the elliptic curve P-384 is known to be

 n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643

See NIST SP 800-186, §3.2.1.4⁠.

We can calculate t at a Python REPL.

>>> n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
>>>  p = 2**384 - 2**128 - 2**96 + 2**32 - 1
>>> t = p + 1 - n
>>> t
1388124618062372383606759648309780106643088307173319169677

The fact that t is positive means the number of points n on our curve is slightly less than p. Here “slightly” is relative. The value of p − n is a huge number, but it’s small relative to p.

We can verify that |t| is less than our a priori bound of 2√p.

>>> from math import sqrt
>>> t/(2*sqrt(p))
0.11057050503394951

So the actual value of t is about nine times smaller than its bound.

My post a few days ago was about the possibility that the NSA had added a backdoor to the NIST curves. Anthropic researchers showed that this wasn’t the case. The NSA had not been able to defend how the curve seeds were chosen because they forgot, but researchers from Anthropic were able to reverse engineer the source of the seeds.

So apparently the NIST curves do not have a backdoor, but as with all encryption, the Achilles heel is human error. eMudrha was using the NIST curve P-384  with extremely small keys: 4, 56, 115, 155, 156, 230, and 237. To understand why this is a problem, I’ll briefly describe how elliptic curve cryptography works.

P-384 is an elliptic curve designed by NIST, with input from the NSA, for use in cryptography. The curve has on the order of 2³⁸⁴ points because the base field is the integers mod

p = 2³⁸⁴ − 2¹²⁸ − 2⁹⁶ + 2³² − 1,

a 384-bit prime number. Given a basepoint b on the curve and an exponent e, it is practically impossible to recover e from b^e. That’s the discrete logarithm problem [1], the basis for the security of elliptic curve cryptography. If and when cryptographically relevant quantum computers arrive, the discrete logarithm problem will be solvable and elliptic curve cryptography will be broken.

Until the advent of quantum computing, elliptic curve cryptography is presumably safe, unless someone does something negligent, such as using a tiny value of e like 4.

If e is chosen at random from a group with on the order of 2³⁸⁴ elements, you cannot recover e from b^e without brute force. But apparently someone said

Let’s see. Is e = 1? Is it 2? Is it 3? Is it 4? Why yes: e = 4.

Ordinarily this would be hopeless. You can’t just try 2³⁸⁴ exponents. But someone thought to test whether the keys were horrifically bad, and they were right.

[1] The exponentiation here is not over the integers, or over the integers mod p. It’s over the group structure of the elliptic curve, and that is what makes it hard to compute the discrete logarithm.

There is a time for everything,
and a season for every activity under the heavens:

a time to be born and a time to die,
a time to plant and a time to uproot,
a time to kill and a time to heal,
a time to tear down and a time to build,
a time to weep and a time to laugh,
a time to mourn and a time to dance,
a time to scatter stones and a time to gather them,
a time to embrace and a time to refrain from embracing,
a time to search and a time to give up,
a time to keep and a time to throw away,
a time to tear and a time to mend,
a time to be silent and a time to speak,
a time to love and a time to hate,
a time for war and a time for peace.

The poem has a great deal of symmetry, from birth and death to war and peace. It has seven couplets, and the number seven in the Bible is symbolic of perfection.

There is a repeated pattern of groups of four words: a time for X, a time for Y. The rhythm reminds me of Beethoven’s fifth symphony, especially the third movement [1].

Higgins points out that there’s something odd in the middle couplet:

a time to scatter stones and a time to gather them,
a time to embrace and a time to refrain from embracing,

It breaks the rhythm, at least in English translation, and presumably in the original language. The poem goes from intransitive adjectival infinitives —to plant, to uproot, etc.—to transitive—to gather stones. Also, the two parts of the couplet do not obviously fit together. There’s a similarity between birth and planting, between killing and tearing down, etc. But what’s the connection between casting stones and embracing?

Higgins explains that this deliberate symmetry breaking fits the theme of the Ecclesiastes as a whole. There is order to the world, and yet we don’t have it all figured out. Even when everything mostly makes sense, there’s something we don’t understand, like the middle couplet.

[1] This has been called the fate motif. There is an apocryphal story that Beethoven described it as such to his secretary and biographer Anton Schindler. Regardless of whether the story is true, the name stuck. Here’s the particular part I had in mind.

Can you still split N! into N factors if you put a minimum size requirement on the factors?

You can’t split 3! into three factors unless one of the factors is 1, but you can split 4! into factors ≥ 2:

4! = 24 = 2 × 2 × 2 × 3

Define t(N) as the largest number such that N! can be expressed as the product of integers greater than or equal to t(N). So based on the discussion above, t(N) ≥ 1 for all N, t(3) = 1 and t(4) = 2. The t(N) are given in OEIS sequence A034258.

Last Thursday an article came out proving an asymptotic estimate for t(N). You can find a preprint on arXiv.

An upper bound on t(N) would be the Nth root of N! because that would correspond to splitting N! into N factors of equal size. But the Nth root of N! will not be an integer for N > 1, so the bound would not be tight.

If we apply Stirling’s approximation for factorial we get

t(N) / N ≤ 1/e + O(log(N) / N).

It was conjectured that for large N

t(N) / N ∼ 1/e − c₀ / log(N)

and the new paper proves

t(N) / N ∼ 1/e − c₀ / log(N) + O(1 / log^{1 + c} N).

.

S Ar Ca Sm

using the symbols for sulfur, argon, calcium, and samarium.

How would you write a program to determine whether a word can be written by stringing together chemical element abbreviations ignoring case? Obviously this isn’t a practical problem, but it illustrates a practical problem.

You could solve the problem with a regular expression:

(h|he|li|be|b|c|n|o|f|ne|na|mg|al|si| … |og)+

This solution could either be very efficient or very inefficient, depending on the inner workings of the software used to match the regular expression.

A DFA (deterministic finite automata) regular expression engine would find a match, or report failure, linear time, i.e. the execution time would be proportional to the length of the string being matched. A NFA (nondeterministic finite automata) engine that uses backtracking could take exponential time.

The root of the problem is the ambiguity in dividing words into single letters or pairs of letters.

Many two-letter chemical symbols are made of letters that are themselves chemical symbols. For example, the symbol for cobalt, Co, consists of the symbols for carbon, C, and oxygen, O. A traditional NFA regular expression engine uses backtracking and could take exponentially long to test whether the word

cococo…j

matches a regular expression for concatenated chemical symbols. If there are n copies of co, the engine would try all 2ⁿ possibilities of treating each pair as either co (cobalt) or c o (carbon oxygen).

A DFA regular expression engine always runs in O(n) time, but a (traditional) NFA can take exponential time. So why ever use an NFA engine? Because it can match more advanced patterns such as Perl regular expressions (which are not “regular” expressions in the original meaning of the term). Newer NFA engines have added safeguards to eliminate or at least reduce the chance of running into catastrophic backtracking.

Two days ago researchers at Anthropic [1] showed that the NIST curves were not seeded with a backdoor. The rest of this post will give the background necessary to appreciate this result.

The security of elliptic curve cryptography depends on the difficult of solving the discrete logarithm problem. In the context of elliptic curve arithmetic, the analog of exponentiation is easy but the analog of taking logarithms is hard.

In general it’s not practical to compute discrete logarithms over large elliptic curves. But it could be easy for someone with inside information to compute discrete logarithms if something about the curve was not “general.”

Specifically, the NIST curves have the form

y² = x³ − 3x + b (mod p)

for various values of p [2], and the suspicion regards the choice of b. For nearly all values of b encryption over the elliptic curve should be secure, as far as we know, but in principle someone could engineer values of b to weaken the encryption.

So where did the b‘s come from? Were they chosen in good faith?

Concern over the choice of seeds, the b‘s, grew following the Snowden revelations. Daniel J. Bernstein emailed Jerry Solinas of the NSA on September 6, 2014 asking where the seeds had come from. Solinas replied in subsequent emails. He said the seeds were generated by hashing the ASCII representation of a humorous English message, but he could no longer remember the exact message or the precise hashing procedure.

On October 5, 2023 Philippo Valsorda announced a bounty for reverse engineering the origin of the NIST elliptic curve seeds. Two days ago researchers from Anthropic claimed the bounty. Valsorda verified the results and awarded the prize. It turns out Solinas found the curve seeds in good faith, but his memory had faded over the years since the curves were published. We now know he used a date, not a phrase, as part of the process of constructing the seeds.

The NIST curves have some nice properties, such as enabling some clever tricks for arithmetic in their base fields. But adoption of the curves has been held back over suspicion regarding their origin. Now the curves have been exhonorated. As Valdorda notes

… this nicely completes the “rehabilitation arc” of NIST elliptic curve cryptography, which I would now personally recommend over Curve25519/Ed25519/X25519. Just in time for them to be retired in favor of post-quantum signatures.

Related posts

• What is an elliptic curve?
• Monero’s elliptic curve
• Lewis Carroll and zero knowledge proofs

[1] This does not imply that LLMs are necessarily a threat to encryption. The search for the NIST seeds required a lot of brute force. Some cleverness was required in order to come up with possibilities to check by brute force, but even that is sorta brute force at a higher level of abstraction. There has been speculation that labs are looking for weaknesses in cryptographic primitives and protocols, but that’s a different matter than searching for seeds.

[2] The curves P-192, P-224, P-256, P-384, and P-521 are built over the field of integers mod p, where the number of bits in p corresponds to the number in the name. The P-192 curve, for example, has as its base field the integers mod 2¹⁹² − 2⁶⁴ − 1, a 192-bit prime.

I’m watching 2010: The Year We Make Contact. The movie opens saying the monolith is located at the Lagrange point between Jupiter and Io. I got nerd sniped and wondered where that was.

There are five Lagrange points, but presumably the movie refers to L1 or L2 because these are near Io. Lagrange points L3, L4, and L5 are essentially in the orbit of Io, but 60, 180, and 300 degrees out of phase, all far from Io. (The book says the monolith is at L1.)

Lagrange points L1 and L2 are unstable. Maybe this is a plot hole in the movie, unless there’s an explanation coming.

(In general L1, L2, and L3 are unstable. If the ratio of the masses is large enough, L4 and L5 will be stable. More on that here. The Lagrange points L4 and L5 are indeed stable for the Jupiter-Io system. For the Sun-Earth system L1 is moderately stable over a short time span, but L1 is far less stable for the Jupiter-Io system.)

Here’s a plot of the Lagrange points.

Note that L1 and L2 are very close to Io, about 10,000 km from the moon. The L1 and L2 Lagrange points for the Earth-Sun system are not so close to Earth.

(That’s half true. Yes, Io’s L1 point is closer to it than Earth’s L1 point, in absolute distance. But in relative terms, Io’s L1 point is actually further away. I had been misled by seeing an illustration that exaggerated the distance from Earth to L1.)

Related posts

• Finding L1 and L2
• When do two-body systems have stable Lagrange points?

    1
    1/2  1/2
    1/3  1/6   1/3
    1/4  1/12  1/12  1/4
    1/5  1/20  1/30  1/20  1/5
    …

I asked Claude to write a LaTeX package to make it easier to create Pascal-like triangles and it did a great job, including handy features I didn’t think to ask for. You can download it here: numtriangle.sty.

I used this package to create the more attractive display below.

Here’s the LaTeX code that produced the image above.

\documentclass[border=4pt]{standalone}
\usepackage{numtriangle}
\NewTriangle{\Leibniz}{start=1, edges=1/\n, rule=\L - \P, fractions,
  format=\displaystyle, xsep=2.8em, ysep=2.8em}
\begin{document}
\Leibniz[rows=5]
\end{document}

I then compiled the code to an SVG file with the following.

pdflatex leibniz.pdf
pdftocairo -svg leibniz.pdf leibniz.svg

Bell’s triangle is not defined in a way that the LaTeX package supports, but I can produce the triangle by listing the content. I made the triangle left-aligned rather than centered just to show that this can be done.

The LaTeX code was the following:

\ListTriangle[shape=left]{
    1; 1, 2; 2, 3, 5; 5, 7, 10, 15; 15, 20, 27, 37, 52}

Here’s a particularly photogenic image, Pascal’s triangle with odd numbers highlighted, showing the Sierpiński triangle pattern.

The code to produce the image:

\PascalTriangle[rows=16, mod=2, xsep=1.9em, ysep=1.3em,
  cell style={font=\tiny, minimum size=1.2em},
  highlight style={fill=orange!40}]

Take any triangle and attach squares to each side. From each triangle vertex, extend a line perpendicular to the opposite side and extend the line through the square, as shown in the figure below. Then the areas of the rectangles with the same labels are equal.

It’s not clear at first why this is a generalization of the Pythagorean theorem, but if we make our triangle closer to a right triangle it’s easier to see the connection.

As the angle at B becomes closer to a right angle, the area of the orange triangles labeled II goes to zero. In the limit we’re left a theorem saying that the areas of the blue and green squares add up to the area of the square attached to the hypotenuse.

Update: Kirill Osenkov made an interactive version of the figure above here.

The paper [1] caught my eye because it gives a connection between a geometry problem and a circuit problem, much like this post. However, I find the theorem itself more interesting than the connection to circuits.

The first diagram is my reproduction of the first figure from the paper, with color added. I then moved the vertex A to make the connection to the Pythagorean theorem easier to see.

Related posts

• Four generalizations of the Pythagorean theorem
• Sparse binary Pythagorean triples
• Napoleon’s theorem

[1] G. D. Chakerian and M. S. Klamkin. A Generalization of the Pythagorean Theorem Seen as a Problem of Equivalent Resistances. Mathematics Magazine, Vol. 59, No. 3 (Jun., 1986), pp. 149–153.

The first line of the paper is “The following result (observed several years ago by the first author) may be viewed as a generalization of the Pythagorean Theorem.” The paper also gives two other sources of the theorem. Presumably Chakerian independently discovered a theorem that was already known.

Poe’s story The Pit and the Pendulum describes a pendulum with a semicircular blade being lowered on a cable. This is an interesting variation on the usual harmonic oscillator because the length L of the pendulum is not constant but rather an increasing function of time L(t).

Using the small angle approximation sin(θ) ≈ θ, the equation of motion is

L θ″ + L′ θ′ + g θ = 0.

If we assume the length is increasing at a constant rate, then with a change of variables described in [1], this differential equation becomes Bessel’s equation and its solutions are Bessel functions.

The authors of [1] state that their primary interest is whether a pendulum can have the motion that Poe describes. But as they indicate in their opening sentence,

The study of the motion of a steadily descending pendulum has practical applications (e.g., to the oscillations of a load being lowered by a crane).

A more recent application would be describing the motion of a package being delivered by a Zipline drone.

Related posts

• Pi and The Raven
• The nonlinear pendulum equation
• From Kepler to Bessel

[1] Robert L. Borrelli, Courtney S. Coleman, and Dana D. Hobson. Poe’s Pendulum. Mathematics Magazine, Vol. 58, No. 2 (Mar., 1985), pp. 78–83

To create the harmonic triangle, start with the harmonic series

1, 1/2, 1/3, 1/4, 1/5, …

This is the first column of the triangle. Next take the differences of the terms:

(1 − 1/2), (1/2 − 1/3), (1/3 − 1/4), … = 1/2, 1/6, 1/12, …

This, shifted down one space, is the second column of the triangle. Taking differences again gives the third column, and so forth. Column c of the triangle consists of the cth differences of the harmonic series.

    1
    1/2  1/2
    1/3  1/6   1/3
    1/4  1/12  1/12  1/4
    1/5  1/20  1/30  1/20  1/5
    …

Each entry is the difference of the entries to its west and northwest. If we let L(r, c) be the element in the rth row and cth column, then

Every numerator is 1, though it’s not immediately obvious why this should be the case. And every number is a value of the beta function, the function that gives the normalizing constant for the beta distribution [1].

Related posts

• The ellipse hidden inside Pascal’s triangle
• Analogs of binomial coefficients
• Odd numbers in Pascal’s triangle

[1] Ayoub B. Ayoub. The Harmonic Triangle and the Beta Function. Mathematics Magazine, Vol. 60, No. 4 (Oct., 1987), pp. 223-225

Topological models, however, are quite limited. You can’t model provability logic, for example, by the usual approach to constructing topological models, though there is an alternative construction.

Categorical models are less limited. You can model a wide variety of logics using categories via the Curry-Howard-Lambek correspondence. This may be cold comfort if you find category theory and logic equally mysterious. Even so, there’s something intriguing about a correspondence between two things you find mysterious.

Categorical semantics is deep and broad, but I’ll keep this post brief. The correspondence between logic [1] and categories [2] is summarized in the table below.

It’s interesting how model logic fits into this picture. Axiom K, required by normal modal logics, says

In categorial semantics, this says this says the box operator □ is a functor, mapping objects representing propositions to objects representing propositions, and mapping morphisms representing proofs to mapping morphisms representing proofs.

Related posts

• Modeling policies in modal logic
• The mythology of category theory
• Category theory without categories

[1] More precisely, intuitionistic propositional calculus.

[2] More precisely, bicartesian closed categories.

The story begins with Helen Nissenbaum’s paper Privacy as Contextual Integrity [1]. Rather than simply classifying data as public or private, Nissenbaum looks at norms around the context in which data exists and moves.

… the benchmark of privacy is contextual integrity; that in any given situation, a complaint that privacy has been violated is sound in the event that one or the other types of the informational norms has been transgressed.

A couple years later Nissenbaum coauthored a paper [2] with three Stanford computer scientists using modal logic, specifically linear temporal logic (LTL), to reason about contextual integrity. The paper uses four modal operators: the usual box and diamond, plus past tense versions with a minus sign across the middle.

These four operators can be read as “henceforth”, “eventually”, “historically”, and “once.”

Henceforth means something will always be true into the future; historically means something was always true in the past.

Eventually means something will happen at some time in the future; once means something occurred at some time in the past.

You could imagine using these operators to formalize statements such as data sharing in some context is permissible (henceforth) if the data subject has (once) signed a consent form.

Understanding simple stand-alone policies does not require the machinery of formal logic, but analyzing large collections of interacting policies may. It may be, for example, that a collection of policies cannot all be satisfied, though this is not obvious from looking at the individual policies. Formalizing policies in the language modal logic makes their analysis amenable to well established algorithms.

Related posts

• Temporal logic for cybersecurity
• Modal logic and science fiction
• Data privacy consulting

[1] H. Nissenbaum. Privacy as contextual integrity. Washington Law Review, 79(1):119–158, 2004.

[2] A. Barth, A. Datta, J. C. Mitchell, and H. Nissenbaum, “Privacy and contextual integrity: Framework and applications,” in Proc. 2006 IEEE Symp. Security and Privacy (S&P’06), Berkeley/Oakland, CA, USA, 2006, pp. 184–198, doi: 10.1109/SP.2006.32.

The Quasi Riemann Hypothesis (QRH) says that there exists a constant θ < 1 such that no zeros of ζ(s) have real part greater than θ. OpenAI has published a paper claiming QRH with θ = 7/8.

The RH is so important to number theory that even partial results can have big consequences. This post will focus on one consequence: the error term in the Prime Number Theorem.

The Prime Number Theorem says that π(x), the number of primes less than x, is asymptotically equal to Li(x). We’d like to know more specifically at what rate π(x) approaches Li(x).

The best known result before the QRH announcement was

If the QRH holds for some θ, such as OpenAI’s assertion that θ = 7/8,

If RH holds, θ = ½.

Incidentally, you may have seen the Prime Number Theorem stated with x/log(x) rather than Li(x). These two functions are asymptotically equal, so they give the same theorem, if you’re not interested in quantifying the rate of convergence. The function Li(x) gives better error bounds.

O(n log n).

OpenAI recently posted a paper saying there is an algorithm that could compute the discrete Fourier transform in

O(n (log n)^{1 − ε})

time for ε = 10⁻¹³.

This result is amazing. It seemed that O(n log n) was as good as you could do, which it provably is for sorting algorithms.

The result is also of absolutely no practical value, for now. But since the theorem shows that our assumptions were wrong, however slightly, about what is possible, maybe we’re in for further surprises. Maybe the ε crack will grow. It wouldn’t be the first time.

Related posts

• The FFT and big data
• FFT and quadratic reciprocity
• DFT conventions

OpenAI recently published a proof that μ(π) = 2. Almost all real numbers have irrationality exponent 2, so the new result says π is typical in this regard. There are numbers proven to have irrationality index greater than 2 (more on that below), but π isn’t one of them.

The irrationality exponent μ(x) is defined as the supremum of the set of values ν such that

for infinitely many coprime integers p and q with q > 0.

This means that the approximation error for approximating π with a rational number p/q is typically on the order of 1/q², just like most irrational numbers.

There are numbers with higher irrationality exponents. For example, Cahen’s constant C has irrationality exponent 3. This means C is an irrational number that has infinitely many rational approximations p/q with error less than 1/q³.

Lissajous figures or Bowditch curves First discussed by Nathaniel Bowditch in 1815, and later by Jules Antoine Lissajous in 1857 …

I wrote a couple posts about Lissajous curves years ago, and recently I wrote a couple posts about Nathan Bowditch, but I didn’t realize there was a connection between them.

I asked Claude to pin down Bowditch’s publication to see whether the curves came up in the course of his work on navigation. Here’s the answer I got.

Bowditch’s paper was “On the Motion of a Pendulum Suspended from Two Points,” published in the Memoirs of the American Academy of Arts and Sciences (Vol. 3, Part 2) in 1815.

He studied a compound pendulum hung from two points (a Y-shaped suspension, sometimes called a Blackburn pendulum). This lets the bob swing at different frequencies in two perpendicular directions, and he worked out mathematically the curves the bob traces. Those curves are what we now call Lissajous figures. Jules Antoine Lissajous studied them independently and much more visibly in 1857, using light beams reflected off vibrating tuning forks, and his name stuck. Because of Bowditch’s priority, the curves are sometimes called Bowditch curves.

Let □p denote the assertion that p is provable in Peano arithmetic. The logic with this interpretation for the □ operator is the Gödel-Löb logic, also called provability logic. This is a normal modal logic with the additional axiom

□(□p → p) → □p,

known as Löb’s axiom.

A couple days ago I wrote about topological models for modal logic. Is there a topological model for Gödel-Löb logic? There is, but it’s not quite the same construction as in the previous post.

A topological model of Gödel-Löb logic associates p with a set P and ◇p with the derived set of P rather than its closure.

The difference between the closure of P and the derived set of P is subtle, but important to this discussion. The closure of a set P is the union of P and all of its limit points. The derived set of P is the set of limit points of P. The distinction is that not every point of P is necessarily a limit point of P. A point x is a limit point of P if every open set containing x contains a point of P in addition to x itself.

A topological space X that models Gödel-Löb logic must be scattered, meaning that every open set must contain an isolated point, a point with no limit points. For example, consider

X = {0} ∪ {1, ½, ⅓, ¼, …}

with the topology inherited from the ordinary topology on the real line. Then every point except 0 is isolated, and every open set contains isolated points.

A statement in Gödel-Löb logic is true if its topological interpretation holds for all scattered spaces.

Start with a pentagon. It may be irregular, but it needs to be convex.

Extend each of the sides of the pentagon to form a star, then draw give circles, one through each of the triangles formed by a side of the pentagon and a vertex of the star.

The five circles intersect in pairs at ten points: the five vertices of the pentagon and five new points. The five new points lie on a circle.

The converse of this theorem is known as the five circles theorem.

Starting with a topological space X and a proposition p, define [[p]] as the set of points in X at which p is true. Define □p to be true at points in the interior of [[p]] and define ◇p to be true on the closure of [[p]].

You could think of □p as the points where p is robustly true. Not only is p true at x, there’s some wiggle room around x, i.e. an open set, in which p remains true.

You could think of ◇p as the points where we cannot rule out the possibility of p being true using open sets. If ◇p includes x, any open set containing x also contains part of ◇p, though it may also contain points outside of ◇p.

Regularity

For any topology on X, the logic constructed above is normal. The axiom

holds because the closure of a set is the complement of the interior of its complement [1].

Note that this is a regularity result for the modal logic, not the topology. The topology could be arbitrary, and not necessarily regular or normal in the topological sense.

S4

The logic constructed above also satisfies a couple more axioms. We have

because the interior of a set is a subset of the set, and

because the interior of the interior of a set is simply the interior. This means the modal logic corresponding to a topology satisfies the S4 axioms. You could say S4 is the logic that corresponds to the McKinsey and Tarski logic of all topological spaces.

More logics and more topologies

So S4 is the logic that corresponds to all topologies. We could look at more restricted topologies and ask what are their corresponding logics. Or we could start with a modal logic and ask whether there’s a topology that models that logic.

Interesting logics correspond to badly behaved topological spaces. Familiar topological spaces like the real line correspond to S4.

Trivial modal logic

The discrete topology corresponds to the trivial modal logic. All sets are open, and closed, so any set is the same as its interior and its closure. So □p and ◇p reduce to just p.

S5

For the indiscrete topology, □p corresponds to a proposition holding everywhere and ◇p corresponds to it holding somewhere. If the topological space has infinitely many points, the corresponding modal logic is S5. [2]

Between S4 and S5

The cofinite topology on an infinite set X defines a set U to be open if the complement of U is finite. The McKinsey-Tarski logic of the cofinite topology is somewhere between S4 and S5. You can show that the formula

holds, which doesn’t hold in S4, and the formula

does not hold, though it must hold in S5.

Related posts

• Modal logic and science fiction
• Naming and numbering modal logics
• Modal logic and cybersecurity

[1] We should also verify that if A ∩ B ⊂ C, then Interior(A) ∩ Interior(B) ⊂ Interior(C).

[2] Propositions can only have a finite number of terms. Having infinite points in the topological space prevents the corresponding logic from proving theorems that don’t necessarily hold in S5.

The situation is similar in point-set topology. You can’t say very much about a general topological space. You have to specify some separation axioms to get going.

Bare bones

Modal logic

A modal logic is any set of formulas in the modal language that:

1. contains all propositional tautologies,
2. is closed under modus ponens, and
3. is closed under uniform substitution.

In particular, this definition requires nothing of the modal operator □ (“box”). You just have propositional logic with a funny symbol added that could mean anything.

Topology

A topological space is a set X along with a set of subsets of X called open sets. The empty set and the full space X are open sets. Furthermore, the set of open sets is closed under finite intersections and arbitrary unions.

There’s not much you can say about topological spaces in general because, for example, the definition includes extreme cases such as the discrete topology (every subset of X is open) and the indiscrete topology (only the empty set and X are open).

Regular and normal

Like many areas of mathematics, logic and topology use the terms “regular” and “normal” to refer to systems with common choices of extra structure.

Modal logic

A regular modal logic is a normal modal logic with a second modal operator ◇ (“diamond”) that satisfies

◇ p ⇔ ¬ (□ ¬ p)

and has the inference rule (p ∧ q) → r implies (□p ∧ □q) → □r.

A modal logic is normal if it satisfies the axiom

□ (p → q) → (□ p → □ q)

and the inference rule that if p is a theorem, □p is also a theorem.

Topology

Topology also uses regular and normal to refer to adding a few axioms.

A regular topological space is one in which you can separate points from closed sets. Given a point x and a closed set F not containing x, there exist disjoint open sets U and V such that x is contained in U and F is contained in V. [1]

A normal topological space is one in which you can separate disjoint closed sets.

For many mathematicians, a metric space is the weakest topology they’re interested in, and metric spaces are normal. But weaker topologies come up. The Zariski topology in algebraic geometry is not regular, and the weak topology on an infinite dimensional Banach space is regular but not normal.

Related posts

• Modal logic and science fiction
• Naming and numbering modal logics
• Modal logic and cybersecurity

[1] Why do we use F to denote a closed set? It’s a convention that goes back to the French word fermé for “closed.”

Some of these new theorems are complicated, asking question that the ancients would not have asked. But once in a while someone discovers a gem that the ancients could have appreciated but didn’t find.

One example is Miquel’s pivot theorem [1]. The theorem was discovered in 1838, which relative to the timeline of Euclidean geometry makes it a recent discovery.

Choose a point on each side of a triangle. Then for each vertex draw a circle through it and the chosen points on the adjacent sides. Miquel’s theorem says the three circles meet in one point.

Here’s an example. For a trangle ABC, choose points D, E, and F on each side. The three circles described in the theorem intersect at M.

Now the three points D, E, and F don’t have to be limited to the sides of the triangle; they can be on the line segment containing the side. Here’s an example where D is outside the triangle.

And here’s an example where two of the chosen points, D and F, are outside the triangle. The three circles still intersect at one point M.

Related posts

• Equation of a circle through three points
• Van Aubel’s theorem
• Big little hexagon

[1] Miquel, Auguste (1838), “Mémoire de Géométrie”, Journal de Mathématiques Pures et Appliquées, 1: 485–487

The server will follow a dawn-dusk orbit, a special case of a sun-synchronous orbit (SSO), following the terminator line between daylight on dark on the earth below. A dawn-dusk orbit allows the satellite’s solar panels to stay in nearly continuous daylight, while also being in a relatively inexpensive low earth orbit (LEO). Geostationary orbit (GEO) would allow solar panels to always receive sunlight, but launching a satellite into GEO requires more fuel and so is more expensive.

Another advantage of LEO is that radiation levels are a couple orders of magnitude less than at GEO. Lower radiation means electronics do not need to be as hardened against radiation.

A dawn-dusk orbit would not be possible if the earth were perfectly spherical. The earth’s equatorial bulge makes it possible to design an orbit that precesses once per year. David Hammen explains this in an answer to a question on the Space Exploration Stack Exchange site.

If the Earth had a spherically distributed gravitational field, a satellite’s right ascension of ascending node would be constant. … Fortunately, the Earth’s gravitational field is not spherical. The Earth’s rotation results in an equatorial bulge. This equatorial bulge causes RAAN to precess (or recess). …

Sun synchronous orbits are chosen so that RAAN precesses by 360 degrees per year, or a bit less than one degree per day. …

A dawn-dusk satellite is a special case of a sun synchronous orbit. … A dawn-dusk orbit typically does not quite follow the terminator. Following the terminator would require a rather high orbit.

Related posts

• Satellites have a lot of room
• Max and min orbital speed
• Starlink configurations

Carry On, Mr. Bowditch is fiction, but it’s essentially factual, and so I imagine something like the conversation above did happen. I thought about how this might work, and it would be difficult.

It is true that if someone can add, subtract, and look-up numbers in a table of logarithms, they can effectively multiply. To find the product xy, they would look up the logarithms of x and y, add the results, then use the table in reverse to find what number has a logarithm equal to the sum.

Difficulties

But there are a couple difficulties in this imagined scheme. First, every calculation would require a lot of steps, including looking up numbers in multiple tables. It’s likely someone who cannot multiply also cannot read, so writing down instructions might not be viable. Second, carrying out calculations using tables is usually not simply a matter of looking up numbers; there are other things someone would need to know, such as interpolation and range reduction.

Bowditch was trying to train innumerate sailors to do specific calculations, not general mathematics, and so there would be ways to mitigate the problems above. Maybe he could create diagrams that would allow a semi-literate person to carry out an algorithm. The sailor wouldn’t need to be able to read per se. The instructions could be aids to help him recall memorized steps. The specialized nature of the calculations might also eliminate the need for range reduction and interpolation.

Tables

How many tables would be necessary? Someone who understands trigonometry doesn’t need separate tables for sine and cosines. And they wouldn’t need a table with entries for all angles. A table of sines for angles between 0 and 45° would be enough. But someone who doesn’t know multiplication would need more tables and bigger tables. Or they would need instruction in how to get by with less. It would be an interesting trade-off.

The novel mentioned tabulating logs of trig functions. For example, if you need to calculate

cos(a) cos(b)

it would be convenient to be able to look up log(cos(a)) and log(cos(b)) rather than look up the cosines and then look up their logs. But you’d still need to be able to convert

log( cos(a) cos(b) )

into

cos(a) cos(b).

This would require a table of logarithms, if the user is able to infer exponentials by reading a table in reverse. Otherwise you’d need a table of exponentials.

In general, you can assume less sophistication from a user by increasing the number of tables. But this also complicates the instructions the user must follow.

To give a specific example, suppose a sailor wanted to calculate his position using the law of haversines:

hav(c) = hav(a − b) + sin(a) sin(b) hav(C).

A mathematically sophisticated sailor would only need a table of sines to infer c from a, b, and C. He could calculate haversine via

hav(θ) = sin²(θ/2),

though inverting hav(c) to solve for c would require calculating a square root, either directly or via a table.

If one were to minimize the amount of sophistication needed by maximizing the use of tables, the algorithm for finding c would be

1. Subtract b from a and look up the haversine of the difference.
2. Look up log(sin(a)) and log(sin(b)) from one table and log(hav(C)) from another and add the results.
3. Take the exponential of the result in the previous step using a table of exponentials.
4. Add the results of steps 1 and 3, and look up the result in a table of inverse haversine values.

This would require five tables: sine, log sine, log haversine, exponential, and inverse haversine.

Condescension

Bowditch’s effort to make navigation accessible to the uneducated is an example of condescension in its literal and positive sense. If we say a person is condescending, we imagine an arrogant person who belittles those around him. But condescension literally means coming down to be with someone. Theologians use the word to describe the incarnation of Christ.

Like all scholars, Bowditch wrote for his peers, notably in his English edition of Laplace’s magnum opus on celestial mechanics. But unlike most scholars, he also devoted years of his life to a making knowledge accessible to uneducated men, culminating in his book The New American Practical Navigator, still in print here [1].

Related posts

• Using a table of logarithms
• Using a table of trig functions
• Why a slide rule works

[1] The book has been updated over the last couple centuries. Obviously the section on GPS, for example, does not date back to Bowditch.

Bowditch was a self-educated mathematician and astronomer, best known for his book The American Practical Navigator, first published in 1801. The book has been continually revised over the last two centuries and is still in print, available for download from the National Geospatial-Intelligence Agency. The latest edition begins with a brief account of Bowditch’s life, confirming the essential details of the fictional biography.

Two things stand out about Bowditch: his attention to detail and his desire to make ideas accessible. He taught himself Latin in order to read Newton’s Principia and followed the text so closely that he found a number of errors.

Bowditch’s navigation book grew out of the numerous corrections he made to error he found in John Hamilton Moore’s The Practical Navigator, the leading navigation text of the time.

At the beginning of the 19th century it was theoretically possible to determine time, and hence longitude, from lunar observation. However, the method required ideal observation conditions and laborious calculation. Bowditch developed a way to make the necessary measurements under more general conditions, and simplified the necessary calculations. According to the biographical preface mentioned above,

Bowditch vowed while writing this edition [of his navigation text] to “put down in the book nothing I can’t teach the crew,” and it is said that every member of his crew including the cook could take a lunar observation and plot the ship’s position.

After completing The American Practical Navigator, Bowditch began an English translation of Pierre Laplace’s encyclopedic Mecanique Celeste, filling in details to make the work accessible to a wider audience. He was able to translate four out of the five volumes by the end of his life.

Related posts

• The navigational triangle
• Line of position
• Intersecting spheres and GPS

Now suppose you want to solve a big triangle, a triangle on the surface of the earth so large that the curvature of the earth matters. You can still use the law of cosines, but you’ll need the spherical law of cosines:

cos(c) = cos(a) cos(b) + sin(a) sin(b) cos(C).

If you know the (angular) lengths of sides a and b, and (tangential) angle C between the two sides, you can solve for c by taking the inverse cosine of the right hand side above.

Now suppose you want to solve this big triangle because you’re a navigator on a ship a couple centuries ago, doing calculations by looking up trig functions and inverse trig functions in a table. You’re interested in triangles that are so big that you have to account for the fact that you’re living on a sphere. But at the same time, your triangles are still fairly small relative to the size of the globe.

The problem with the law of cosines

The numbers a and b will often be fairly small, and so their cosines will be near 1 and their sines are near zero. So the calculation

cos(a) cos(b) + sin(a) sin(b) cos(C)

will add a number near 1 and a number near zero. That’s a problem.

Say you’re working with five decimal place arithmetic. Then if the second term above is less than 10⁻⁵, its contribution to the sum gets completely lost in the addition to the first term. If the second term is larger than 10⁻⁵ but still small, its contribution to the sum will be partially lost.

Law of haversines

Enter the haversine, defined by

hav(θ) = (1 − cos(θ))/2.

The expression 1 − cos θ was called the versine, and so half of the versine is the haversine.

In terms of the haversine, the law of cosines above becomes the law of haversines:

hav(c) = hav(a − b) + sin(a) sin(b) hav(C).

Now suppose you have a table of haversines and inverse haversines. The law of haversines requires a little less work: you have one less table lookup, and you trade a product for a subtraction.

But the primary advantage is numerical accuracy: the terms on the right side have roughly the same size.

Tables

Note that we’re assuming the values in your table of haversines have been calculated correctly to the given precision. If you calculated your own values of haversines from the definition above, you’d lose precision in the subtraction 1 − cos θ, defeating the advantage of the law of haversines [1].

History

According to Wikipedia.

The first table of haversines in English was published by James Andrew in 1805, but Florian Cajori credits an earlier use by José de Mendoza y Ríos in 1801. The term haversine was coined in 1835 by James Inman.

Experiments

I ran some experiments that carried out arithmetic in float16 (11 bits of precision) to approximate what someone might have done by hand. When the difference between a and b was on the order of 1° or 0.1°, the law of cosine method often overflowed: the right-hand side evaluated to something larger than 1 even though theoretically it should be less than 1. The haversine method never overflowed.

The median error for the haversine method was a couple orders of magnitude less than that of the cosine method.

Related posts

• Lews & Clark navigation
• How many trig functions are there?
• Analog of Heron’s formula for a sphere

[1] hav(θ) = (1 − cos(θ))/2 = sin²(θ/2). If you calculated hav θ by looking up sin(θ/2) and squaring it, you’d be doing extra work, but you wouldn’t have numerical problems.