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

Lissajous and Bowditch

Posted on by John

I was skimming through David Well’s book The Penguin Dictionary of Curious and Interesting Geometry and was surprised by this entry:

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.

A topological model for provability logic

Posted on by John

Gödel’s incompleteness theorem illustrated the need to distinguish between what is true and what is provable. There are true statements that cannot be proven.

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.