Monoliths and Lagrange Points

Posted on by John

This post began as a thread on X last night. I’ve edited the thread to turn it into a blog post, making some additions and corrections.

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.

MISSION ANALYSIS: COMPOSITION OF SECOND MONOLITY ... UNKNOWN. POSITION OF SECOND MONOLITH ... LA GRANGE POINT BETWEEN JUPITER AND IO. POSSITION OF U.S.S. DISCOVERY ... ORBIT AROUND IO. CONDITION OF U.S.S. DISCOVERY ... UNKNOWN.

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

LaTeX package for Pascal-like triangles

Posted on by John

When I wrote about the harmonic triangle yesterday, I displayed the triangle left-aligned using fixed-width text because that was easier than producing the format you usually see for Pascal’s triangle and related triangles.

    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}]

A generalization of the Pythagorean theorem

Posted on by John

G. D. Chakerian [1] discovered the following generalization of the Pythagorean theorem.

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.

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

[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, Bessel, and Drones

Posted on by John

What’s a connection between Edgar Allan Poe and Friedrich Wilhelm Bessel?

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

[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

Harmonic triangle

Posted on by John

Pascal’s triangle is the most famous triangular arrangement of numbers. I’ve written about other numerical triangles, such as Bell’s triangle and the trinomial triangle. There’s another well-known triangle that somehow I never heard of until recently: the harmonic triangle, first explored by Leibniz around 1700.

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

L(r,c) = L(r-1, c-1) - L(r, c - 1)

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].

L(r,c) = \frac{1}{r\binom{r-1}{c-1}} = \beta(c, r-c+1)

Related posts

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

Categorical models of logics

Posted on by John

A few days ago I wrote about topological models of modal logic. If you find general topology more familiar than modal logic, this correspondence could be helpful. If you think the motivation for general topology is evident but the motivation for modal logic is suspect, the correspondence between the two fields might relieve some of your suspicion of the latter.

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.

\begin{tabular}{ll} \hline \textbf{Logic} & \textbf{Category theory} \\ \hline Proposition / formula & Object \\ Proof of \(A\) from \(\Gamma\) & Morphism \(\Gamma\to A\) \\ Truth \(\top\) & Terminal object \(1\) \\ Falsehood \(\bot\) & Initial object \(0\) \\ Conjunction \(A\land B\) & Product \(A\times B\) \\ Disjunction \(A\lor B\) & Coproduct \(A+B\) \\ Implication \(A\to B\) & Exponential \(B^A\) \\ Negation \(\neg A\) & Exponential \(0^A\) \\ \hline \end{tabular}

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

\Box(A\to B)\;\longrightarrow\;(\Box A\to\Box B)

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

[1] More precisely, intuitionistic propositional calculus.

[2] More precisely, bicartesian closed categories.

Privacy policies and modal logic

Posted on by John

If you’ve followed this blog for a while, you may know that I do a lot of work with data privacy and that I have an interest in modal logic. Recently these two worlds collided: I became aware of work that uses modal logic to reason about data privacy.

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.

box, diamond, box minus, diamond minus

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

[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.

Consequences of progress toward the Riemann Hypothesis

Posted on by John

The Riemann Hypothesis (RH) is the conjecture that all the zeros of the Riemann zeta function ζ(s) in the critical strip, i.e. the region of the complex plane with real part between 0 and 1, have real part equal to ½.

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

\pi(x) = \operatorname{Li}(x) + {\cal O} \left(x \exp\!\left(-c\,\frac{(\log x)^{3/5}}{(\log\log x)^{1/5}}\right)\right)

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

\pi(x) = \operatorname{Li}(x) + {\cal O} \left(x^\theta\,\log x\right).
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.

Faster Fourier Transform

Posted on by John

The Fast Fourier Transform (FFT) algorithm can compute the discrete Fourier transform of a sequence of length n in time

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−13.

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

Irrationality exponent of π

Posted on by John

For a real number x, the irrationality index μ(x) is a way of measuring how well x can be approximated by rational numbers. If x is rational, μ(x) = 1. If x is irrational, μ(x) ≥ 2.

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

0 < \left| x - \frac{p}{q} \right| < \frac{1}{q^\nu}

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³.