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.

Suppose you’re collecting data on the left side of the curve. If there’s even a small amount of error in your data, you won’t be able to predict the asymptotic value with any accuracy. But if you have data on both sides of the inflection point, you can make a good prediction of the limiting value.

I’ve written about this before, explaining that the problem is hard, but I didn’t say why it’s hard. Here I’d like to give an idea why it’s hard.

Suppose you want to fit a logistic equation

to three distinct values of t and the corresponding values of y. There is a unique solution, but in general you cannot find a solution in closed form. However, if the values of t are evenly spaced

there is a method [1] to solve for the parameters L, k, and t₀. For this post we’re only interested in the limiting value L, and it can be found by

independent of h.

To find out how small changes in the y‘s change the estimate of L, we take the partial derivatives of L with respect to the y‘s and find

and

All three derivatives have the same expression in the denominator: y₁² − y₀ y₂.

If the function y(t) were an exponential, this expression would be exactly zero [2]. The function y(t) is not exactly exponential, but it is approximately exponential when the t‘s are in the left or right tail of the logistic curve. The further out in either tail the t‘s are, the closer the expression is to zero.

So when all the t‘s come from the same side of the inflection point, y(t) is nearly exponential the partial derivatives are huge and so the fitted value of L is extremely sensitive to changes in the y‘s.

As a concrete example, set L = k = 1 and t₀ = 0. Evaluate y(t) at −2, −1.5, and −1. Then the values of y are

y₀ = 0.11920292
y₁ = 0.18242552
y₂ = 0.26894142

If you forecast L using exactly these three values you’ll get L = 1.

But if you change y₀ to 0.12374097, the forecasted value of L is infinite. Values of y₀ in the interval [0.11920292, 0.12374097] predict values of K in [1, ∞].

[1] Raymond Pearl and Lowell J. Reed. On the Rate of Growth of the Population of the United States Since 1790 and its Mathematical Representation. Proceedings of the National Academy of Sciences of the United States of America, Vol. 6, No. 6 (Jun. 15, 1920), pp. 275-288

[2] exp(x + h)² = exp(x)² exp(h)² = exp(x) exp(x + 2h)

Lewis Fry Richardson (1881–1953) noticed that the length of the coast of Scotland depended on the size of segments used to measure it. More specifically, he found that the length followed a power law, i.e. that there’s a linear relation between the log of the coastline length and the log of the ruler length.

Here’s a reproduction of Richardson’s plot, taken from [1].

Mandelbrot built on Richardson’s observation and defined the idea of fractal dimension.

I was under the impression that fractals were invented as mathematical novelties that researchers later found applications for. But as is often the case, the applications came first. Or at least some applications came first.

Ideally there’s always a feedback cycle where applications lead to theory and theory leads to applications. As Donald Knuth put it, “The best theory is inspired by practice. The best practice is inspired by theory.”

Related posts

• Minimalist Mandelbrot set
• The fractal nature of Brownian motion
• Randomly generated dragon

[1] Eoghan Bradley and Mark McCartney. Four hundred years of the fractal coastline of Scotland. The Mathematical Gazette, November 2019, Vol. 103, No. 558 (November 2019), pp. 518-521

One of the cards in the book is for Eugene Frank, President of B & F Instruments. His card lists his phone number as

(215) MErcury 9-7100

At first glance I thought the “E” in “MErcury” had been accidentally capitalized. Then I realized the intention was that someone would dial ME (i.e. 63) and ignore “rcury”. So the phone number would be (215) 639-7100.

This card was from 1968, the height of the space race. Maybe the card was alluding to the Project Mercury or the planet Mercury, or both. [1]

The telephone keypad mapping (ITU E.161 standard) is a poor attempt at making phone numbers more memorable. For starters, there’s no way to encode 0 or 1 [2]. It’s unlikely a phone number will correspond to anything memorable unless you come up with the word first and then try to obtain the phone number, such as 800 FLOWERS.

Inserting extra letters, as Mr. Frank did, greatly increases the chances of encoding a phone number as a word. But then you need to denote which letters count and which ones are filler, so there’s not much advantage. Still, I wanted to play around with it for fun. I found 109 words [3] containing the letters from a telephone encoding of 4228646. (I’m using the file /usr/share/dict/words on my laptop as my list of words.)

Here are some of the more interesting hits.

• semicatholicism
• heartburning
• gladiatorism
• diabetogenic
• galactogenetic
• xanthocreatinine

There are over 30,000 words containing an encoding of the area code 832. One of these is traditional, and so I could write my phone number as

TraDitionAl semICAThOlIcisM.

Another choice for 832 is intercosmic, so

inTErCosmic GAlaCTOGeNetic

is another possibility.

Galactogentic can refer to the production of milk by the mammary glands or to the formation of galaxies (e.g. the Milky Way). Here intercosmic fits with the later sense.

I got greedy and tried to find a word containing the full phone number, 8324228646, but didn’t find anything.

Here’s my business card in the style of the Los Alamos Rolodex cards, created by Grok, using (832) GlAdiATOrIsM as the phone number.

Now suppose you remembered “gladiatorism” but not which letters were capitalized. Then you’d have to try up to 792, i.e. 12 choose 7, possible numbers, so this really isn’t a practical mnemonic. If you remembered “traditional semicatholicism” without capitalization it would be worse, with over a million possibilities (11 choose 3 times 15 choose 7). Some possibilities are counted twice, since different ways of selecting letters can lead to the same phone number, but still there are too many possibilities to try.

Related posts

• Major memory system telephone keypad
• What can you learn from a phone number?
• Phone tones inn musical notation

[1] Thanks to Andrew for pointing out in his comment that it was common at one time to encode the first two numbers of the exchange (the second triplet of numbers in a phone number) as letters, and assign a word to those letters. Sometimes this was standardized, such as Pennsylvania 6 for 736, an example made famous by Glenn Miller. But from what I can tell, not all exchanges had standard names, and proposed standards weren’t always adopted in practice.

In the example above, I don’t know whether it was common to encode 639 as Mercury 9, or even ME 9, or whether Mr. Frank chose this. It was common chose some encoding for the first two numbers of the exchange, though that practice was going away by 1968. Perhaps Mr. Frank was an older man who retained a habit he acquired when it was more common. None of the other cards in the book spelled out the exchange.

Update: Thanks to Chuck for pointing out this list of recommended words for exchanges. Note that there are multiple suggestions for most exchanges, including six for 63X.

[2] Not only are there no letters for 0 and 1, the letters O and I represent digits. At one point in time the first digit of an exchange (the middle three digits) could not be a 0 or 1, but these digits could appear anywhere else.

[3] I initially found a list of 185 words, but some of these were duplicates: a word can represent a phone number in more than one way.

Normalized word vectors are points on a high dimensional sphere, and geometry in high dimensions is counterintuitive. See the first post in this series for an explanation.

The set of points within a given angular distance of a point on a hypersphere is called a spherical cap. The ratio of the area of this spherical cap to that of the whole sphere is called cap fraction or concentration ratio. Concentration ratio explains why a modest cosine similarity value corresponds to a tiny portion of the area of the sphere and should be interpreted as a close match.

For this post, I wanted to share a plot of concentration ratio as a function of cosine similarity.

This shows that moderate values of cosine similarity correspond to infinitesimal concentration ratios. And yet, as the third post linked at the top showed, word vectors are very unevenly distributed, and even extremely small regions of the sphere can contain multiple word vectors.

I only included cosine similarity values up to 0.8 because the function plotted above takes a nosedive for larger values, even on a logarithmic scale.

Here’s the Python code to make the plot, using the function cap_fraction from here.

s = np.linspace(0, 0.8, 500)
plt.plot(s, cap_fraction(np.acos(s), 200))
plt.yscale("log")
plt.xlabel("cosine similarity")
plt.ylabel("concentration ratio")
plt.show()

“king” − “man” + “woman” ≈ “queen”

This should be interpreted as saying that the word vector for king, minus the word vector for man, plus the word vector for woman, is in some sense close to the word vector for queen.

This post will look at another example. Is the expression

“coffee” + “milk” ≈ “latte”

true in some sense?

Notation

In this post I will use “foo” to mean the vector embedding of the word foo.

Coffee + milk

The cosine similarity between “coffee” + “milk” and “latte” is about 0.63. And for reasons given in the previous post, this is a large value of cosine similarity. But there are 11 words that are more similar to “milk” + “coffee” than “latte”. Here are the top 12 matches in order.

1. coffee
2. milk
3. tea
4. drink
5. chocolate
6. cream
7. breakfast
8. ice
9. beer
10. vanilla
11. starbucks
12. latte

There are two questions to resolve. First, why isn’t latte one of the closest words? Second, why is the cosine similarity large even though latte is not one of the best matches?

Concept arithmetic

When word vector arithmetic works, as in the king and queen example, the vectors combine concepts. If you replace the male gender component of king with a female component, you get a vector close to the vector for queen.

But when you add the vectors for milk and coffee, you’re not adding concepts, you’re adding ingredients.

The concepts of milk and coffee are similar in that they’re both common beverages, as are tea and even beer. A latte is a beverage, but it’s not as common as milk, coffee, tea, or beer.

Extremely uneven distribution

If you divide word vectors by their norm, you get a point on a high-dimensional sphere. In the case of the glove-twitter-200 vector embedding, you get a point on a sphere in 200 dimensions. As explained in the earlier post, a fairly large cosine similarity corresponds to a tiny portion of the sphere’s surface area.

In the example of “king” − “man” + “woman”, the vector “queen” is the closest match (except for “king” itself).

But there are a lot of words whose vectors are within a tiny region around “coffee” + “milk”. And by tiny, I mean a region that accounts for a proportion of the sphere on the order of 10⁻²³.

The glove-twitter-200 vector list contains vectors for 1.2 million words. If these vectors were roughly evenly distributed on the sphere when normalized, you’d expect each patch representing 10⁻⁶ of the sphere to contain about a word or two. You wouldn’t expect a patch taking up 10⁻¹² of the sphere to contain more than one word, and you certainly wouldn’t expect a patch taking up 10⁻²³ of the sphere to contain 12 words [1].

Rank order

Rank order based on cosine similarity is more robust than cosine similarity itself. This is an example of a phenomenon that occurs regularly: a metric whose values are dubious might still rank things well. Naive Bayes is another example. It naively computes probabilities in a way that is blatantly wrong, and yet ranking things by these spurious probabilities works well in some cases.

The cosine similarity between “king” − “man” + “woman” and “queen” is roughly the same as the cosine similarity between “coffee” + “milk” and “latte.” But in the former example, rank order picks out queen as the best match; rank order works like you’d expect, because you’re working with attributes that can be decomposed.

Dog + infant = puppy?

I wouldn’t be surprised if the Anglo-Saxon word for puppy was something like dogchild. The language was full of colorful compound words, such as hronrad (“whale-road”) for the sea and nosethyrl (“nose-hole”) for nostril.

Here are the top ten matches for “dog” + “infant” along with their cosine similarities.

1. dog, 0.819
2. infant, 0.809
3. toddler, 0.734
4. dogs, 0.697
5. puppy, 0.688
6. cat, 0.682
7. pet, 0.676
8. child, 0.671
9. newborn, 0.670
10. baby, 0.650

This shows that “puppy” is close to “dog” + “infant”, both in terms of cosine similarity and rank order, though it’s not the closet.

This also shows that you have to take the addition of word vectors with a grain of salt. It’s no surprise that puppy was a good match, but it’s surprising that cat is nearly as good.

[1] I poked around a little to get an idea just how unevenly words are distributed. The closest pair of words is jajaja and jajajaja with a cosine similarity of 0.993. The most isolated word, meaning the word whose nearest neighbor is furthest away, the the Thai word เคยไหม. It’s nearest neighbor is the Russian word боль with a cosine similarity of 0.283.

The glove-twitter-200 vectors were created from a corpus that is about half English and about other languages and strings of symbols that are not words in any language. Presumably เคยไหม would have a much closer neighbor in a corpus containing more Thai words.

I didn’t search the entire corpus, only the 50,000 most frequently occurring vectors, because a full search would require running an O(N²) search with N = 1,200,000.

For example,

3 × 5 × 8 × 13 = 39 × 40.

I ran across this theorem in a note [1] that says “The product of any four consecutive Fibonacci numbers is twice a triangular number.” Since triangular numbers have the form n(n + 1)/2, twice a triangular number is the product of two consecutive integers.

The note also gives a way to find the numbers on the right hand side. We have

F_n F_n+1 F_n+2 F_n+3 = m(m + 1)

where m equals

F_n+1 F_n+2

if n is odd and

F_n F_n+3

if n is even.

In the example at the top, 3 is the 4th Fibonacci number, so n = 4. Since 4 is even, m is the product of the 4th and 7th Fibonacci numbers, i.e. m = 3 × 13 = 39.

More Fibonacci posts

• Fibonacci meets Pythagoras
• Certified Fibonacci numbers
• Turning trig identities into Fibonacci identities

[1] K. B. Subramaniam. On a link between Triangular and Fibonacci numbers. The Mathematical Gazette, Vol. 103, No. 558 (November 2019), p. 489.

Another way to look at this, as explained in the previous post, is that in high dimensions, a spherical cap of angular radius θ represents a small portion of a sphere, even for moderately large θ.

The proportion of the area inside the spherical cap, given here, involves the “regularized incomplete beta function” and so it’s hard to have an intuition for the value.

For large dimension n, the approximation

n^−1/2 sin^{n − 1}(θ)

gives the proportion of the area inside the cap to within an order of magnitude. It’s easy to see that this function goes to zero quickly as n increases, provided |θ| < π/2.

If you have the cosine similarity c = cos θ rather than θ itself, the approximation becomes

n^−1/2 (1 − c²)^{(n − 1)/2}.

Python script

Let’s try it on the example from the previous post, in which n = 200 and θ = 49°.

import numpy as np
from scipy.special import betainc

# Fraction of S^{n-1} inside a spherical cap of angular radius theta
# theta is measured from the pole
# Assume 0 < theta < pi/2

def cap_fraction(theta, n):
    x = np.sin(theta) ** 2
    return 0.5 * betainc(0.5 * (n - 1), 0.5, x)

def cap_fraction_approx(theta, n):
    return n**(-0.5) * np.sin(theta)**(n-1)

theta = np.deg2rad(49)
print(cap_fraction(theta, 200)) 
print(cap_fraction_approx(theta, 200)) 

This prints 2.03e-26 and 3.37e-26. The order of magnitude is correct as advertised.

For vectors x and y,

where θ is the angle between the vectors, and so

This is the cosine similarity between the words represented by x and y.

Small angles have large cosines, and so words with larger cosine similarities are closer together than words with smaller cosine similarities. The cosine similarity between a word and itself equals 1, and we’d expect unrelated words to have a cosine similarity near 0.

You can do a sort of arithmetic with vector embeddings of words. The canonical example is that

“king” − “man” + “woman” ≈ “queen”

Implicit in this equation is that we’re really adding vector representations of the words. Let a, b, c, and d be the vector embeddings of the words king, man, woman, and queen. What we’re really asserting is that

a − b + c ≈ d,

except that’s not true! Or at least it’s not true unless you view it in the right context.

The angle between a − b + c and d is about 49°, which corresponds to a cosine similarity of 0.656. Here I’m using the gensim glove-twitter-200 embedding that represents words as 200-dimensional vectors.

The way to interpret the equation above is not that a 49° degree angle is approximately 0, or that a similarity of 0.656 is approximately 1.

In high dimensions, such as 200-dimensional word embeddings, nearly all vectors are nearly perpendicular. I wrote a post about this here. So the angle between randomly selected words will usually be close to 90°, and so in that context an angle of 49° is relatively small. For example, the angle between the vector representations of king and fireplace is 89.25°.

If you divide word vectors by their norm, you can think of each vector as a point on a high-dimensional sphere, in our case a sphere in 200 dimensions. The proportion of vectors within 49° of a given point is surprisingly small in high dimensions.

Let’s say our point of interest is the north pole of an n-dimensional sphere. We’d like to calculate the proportion of the area of the sphere that is within an angle θ of the pole. I go through the calculations here. (Update: I give an approximation here that’s easier to work with than the exact formula.)

When n = 3, 17% of the area is with 49 degrees of the pole. But when n = 200, the proportion is on the order of 10⁻²⁶, essentially zero.

The vector d above representing queen is within a relatively tiny region around the vector a − b + c.

In terms of cosine similarity, 0.656 is a large similarity. Words with a cosine similarity in this range are quite close, even though we wouldn’t normally think of 0.656 being close to 1. In this context, 0.656 is close to 1.

Related posts

• Angles between words
• Area and volume of a hypersphere cap
• Cosine similarity does not satisfy the triangle inequality

Apps on a phone may automatically interpret a 10-digit number as a phone number or a 16-digit number as a package tracking number. And very often these interpretations are correct, given the kinds of things most people use their phones for.

It’s not surprising that a 10-digit number on a phone is a phone number. It’s more interesting that a 16-digit number is likely a tracking number. It could be other things, such as a credit card number. But people don’t usually write out credit card numbers in a text note; credit card numbers likely saved in some more opaque way.

I run into a variation of this problem routinely, trying to infer what a number represents inside medical notes.

A five-digit number could be a US postal code, or it could be a medical procedure code.

A six-digit number could be a date in MMDDYY format, or it could be a medical record number.

A ten-digit number could be a phone number, or it could be an NPI (National Provider Identifier) number.

It’s interesting that it’s possible make a good guess at what a number means inside unstructured text. Context has been lost, but not all context: you know you’re looking at medical notes. And that meager bit of context can be surprisingly useful.

Now suppose an OCR program sees some character that could be a beta or could be an eszett. It could calculate some kind of distance between the pixel pattern of the character and the pixel patterns of beta and eszett. But that would be discarding context.

If you’re scanning a Greek document and run into a beta-like symbol, it’s very likely a beta. If you’re scanning a German document and run into a beta-like symbol, it could be a beta. For example, it could be a scientific paper that mentions beta particles or beta carotene. But most likely the symbol is an eszett.

The previous paragraph is saying you should compute the conditional probability of a set of pixels representing a character given the language of the document. You could be more sophisticated and look at the position of the symbol in a word as well. For example, if you see a symbol at the end of a Greek word that could either be ο (omicron) or σ (sigma), it’s likely an omicron because Greek has a different symbol ς for final sigma.

This post is a follow-on to my earlier post on the error rate in Google’s Ngram database. OCR errors are fairly common in that database, so why don’t they “just” fix the errors by using some sort of Bayesian method? OCR software probably does use some sort of Bayesian method, but it’s not that simple.

In that post I looked at the use of the word grok in English. The Ngram database shows the word being used before it was coined in 1961 due to OCR errors. Why didn’t Google compute the probability of a word being “grok” conditional on the publication date? That would be circular. We happen to know exactly when grok was coined, but in general we might try to determine when a word was coined by looking at a large set of scanned books, like the Ngram database!

Now we could compute the probable value of an ambiguously scanned word by conditioning on the language of the surrounding text. That would be a reasonable thing to do in general, but it could also lead to exactly the kind of errors we see in the Ngram data for grok.

Suppose you see an ambiguously scanned word in a book written in English. There is a higher prior probability that the word is an English word than a German word. Now suppose you see “gro?” where ? could be β, ß, or k. Without any context, perhaps the probability of the symbol being a k is small. But grok is an English word and groß is a German word which may lead you to conclude “?” is a k and the ambiguous word is grok.

Assigning higher prior probability to English words in English texts is the best thing to do on average, but in particular instances it will lead to errors. That’s life.

The Ngram database includes millions of scanned books. Google had to use OCR algorithms that work well on average. A linguist with a special interest in a particular word can be more careful and create a more sophisticated probability model (explicit or implicit) customized for their interests. Google did what they could operating at such a large scale.

Related posts

• Uppercase eszett
• A Bayesian view of Amazon resellers

The proof was simplified over the years, and formalized in Coq in 2005. Everyone is satisfied that the theorem is true, but there has never been a satisfying proof, one that a human could read and say “I see now why any map can be colored using only four colors.” And there may never be one, but see this post for a contrary prediction.

The IBM mainframe that ran the calculations completing the proof of the four color theorem did not generate the proof. It simply executed the FORTRAN program that Haken and Appel (and Koch [1]) gave it.

I don’t see the recent proof of finite-time blowup for solutions to the Navier-Stokes equations as entirely different. Computers did higher-level tasks for the OpenAI team than the mainframe did for Haken and Appel, and these tasks were not as directly programmed as the tasks that were given to the mainframe, but still machines do what they are told to do.

Related posts

• The seven color map theorem
• Detecting errors with the four color theorem

[1] John A. Koch was a programmer who worked on the four color proof with Haken and Appel. I don’t know how much credit he deserves, but I suspect it may be more than he was given.

By all accounts, the best programmers have had the biggest productivity boost from AI. And top tier mathematicians are using AI to settle long-standing mathematical conjectures. AI is a powerful tool, but tools don’t come to life and make things on their own.

I routinely have naive amateurs [1] send me proofs of open conjectures, and naturally more recent such proofs involve AI. I’ll get an email saying something like “I’ve solved the Collatz conjecture using ChatGPT, but I’m not a mathematician so I need some help verifying the proof.” And of course the supposed proof is rubbish.

The recent Navier-Stokes proof is impressive, but AI didn’t initiate the proof any more than LaTeX did. Nor did a child steer AI into proving the conjecture. Professional mathematicians were able to use AI to pursue their ideas at superhuman speed. But someone without an understanding of the Navier-Stokes problem, and familiarity with recent ideas for approaching the problem, could not have directed AI to produce a proof.

Computer scientists have been saying “garbage in, garbage out” from the beginning. A variation on this aphorism for the age of AI would be “mediocrity in, mediocrity out.”

***

[1] Amateurs can and do make contributions to mathematics. For example, in 2022 David Smith, a retired print technician, discovered a single shape that can be used to create an aperiodic tiling of the plane. By “naive amateurs” I mean people who literally do not know what they are talking about.

Quite a few other mathematical conjectures have been settled recently using AI, and these have also been accompanied with formal proofs, using Lean 4 in particular.

Until very recently, generating machine-verifiable formal proofs has been excruciatingly tedious. In 2005, Henk Barendregt and Freek Wiedijk wrote

To give an indication of how much work is needed for formalisation, we estimate that it takes approximately one work-week (five work-days of eight work-hours) to formalise one page from an undergraduate mathematics textbook.

That was the rule of thumb: forty hours per page. And this in the context of undergraduate textbooks. Research publications are much denser than textbooks. Furthermore, page 100 of a textbook probably depends mostly on material on pages 1 through 99. A sentence in a research article could cite anything that has been published before.

Say a research article takes 20 times more effort to formalize than page in an undergraduate textbook. Then formalizing the 166-page paper from OpenAI would take 132,800 person-hours. It took OpenAI 17 hours to verify their proof in Lean. I hesitate to use the word “revolutionary,” but lowering the cost of anything by four orders of magnitude is revolutionary.

I’ve used AI to generate formal proofs to check my work just for a little blog post. I wouldn’t dream of doing that if I had to pay someone a week’s salary to check my work.

Formal verification doesn’t just apply to mathematics. You could, for example, formally verify that a set of security policies are consistent and that, given certain assumptions, they accomplish their purpose. You could formally verify that a smart contract imposes a certain maximum liability. You could verify the correctness of mission-critical algorithms. These problems are easier than formalizing mathematics research, and it is easier to quantify the return on investment.

Related posts

• Automation and validation
• Formal methods let you explore the corners
• When are formal methods worth the effort?

The problem concerns technical properties of solutions to the Navier-Stokes equations [1], a set of equations that describe the dynamics of fluid flow. Popular accounts of the problem are often oversimplified and misleading.

Some reports will speak of the problem as “solving the Navier-Stokes equations.” The task is not to write down a closed-form solution, which can’t be done, or solve the equations numerically, which has been done for decades. The problem is to prove theoretical properties of solutions which are of little interest in practice.

There has been progress toward settling the Navier-Stokes problem. Terence Tao wrote a post on this yesterday.

What’s also  interesting is the intrigue around the possible solution. A post this morning says

If I am reading this correctly, Tristan Buckmaster is alleging OAI has a resolution of Navier-Stokes … which maybe used info from Buckmaster and Levent Alpöge’s private Codex sessions.

Buckmaster asked OpenAI whether they used his private sessions and they have not responded. Update: Statement from OpenAI.

Personal note

This topic connects parts of my career spanning decades. My graduate work was in PDEs and I had some interest in the Navier-Stokes equations. Here are some notes I wrote back in the day.

Now I work more with privacy than with PDEs. The question of whether OpenAI uses private data, contradicting their stated policy, is more relevant to my current work than whether the Navier-Stokes equations have global regular solutions.

Related posts

• Engineering a waterpark
• Euler-Lagrange equations
• Data privacy

[1] I never know whether to say equation or equations. You’ll hear both. You could think of Navier-Stokes as one vector-valued PDE or three scalar-valued equations.

grok (v.)

“understand empathically,” 1961, an arbitrary formation by U.S. science fiction writer Robert A. Heinlein (1907-1988) in his book “Stranger in a Strange Land.” In the book it is a transliteration of a Martian word and is said to mean etymologically “to drink.” It attained popular use in 1960s-70s counterculture but is perhaps obsolete now except in internet technology circles.

I don’t believe anything in the statement above is disputed. And yet Google’s Ngram Viewer tells a very different story.

The plot implies that use of the word grok had been increasing before Heinlein’s book came out and is now much more common than it was in the 1970s. Note that the plot ends before the Grok AI came out in late 2023.

Apparently the Ngram data is unreliable, mainly for two reasons: OCR errors and inaccurate date attribution. Presumably the blip around 1900 was due to the former, OCR causing words like crok or grog to be cataloged as grok. And presumably the rise in usage before 1961 was due to the latter, misattributing the date of sources published after 1961.

The supposed rise in usage before 1961 is interesting. You’d expect some lag between the time a word circulates in conversation and when it appears in books, but apparently this lag can be smaller than the effect of date misattribution.

Etymonline speculates that grok is “perhaps obsolete now except in internet technology circles.” That matches my experience. Even in technological circles, the word was uncommon before Grok was released. Maybe it was more common in print than in conversation.

Related posts

Previous posts with Ngram stats. The effects are so large that they’re probably directionally correct after adjusting for a substantial error rate.

• Duodecimal vs. Hexadecimal
• Orwellian vs. Huxleyian