John D. Cook

Splitting N! into N factors is trivial. It’s defined as the product of N integers, the integers 1 through N. 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…

Many words can be spelled by stringing together chemical symbols. For example, sarcasm can be written 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)+…

NIST published a set of elliptic curves for cryptography in 2000. The seeds for the curves were supplied by the NSA, and cryptographers suspected the agency may have installed backdoors in the curves. And not without reason: the NSA did insert a backdoor in the Dual_EC_DRBG random number generator. 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…

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. 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,…

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…

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…

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…

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),…

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…

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…

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

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…

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…

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…

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…

An earlier post presented an elegant plane geometry theorem discovered by the 19th century school teacher Auguste Miquel. This post presents his pentagon theorem. 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 verices of the pentagon and…

The previous post discussed a superficial connection between modal logic and topology, that both give use the terms regular and normal to indicate added sets of axioms. McKinsey and Tarski developed a deeper connection between modal logic and topology that we’ll discuss here. 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 can’t say much about modal logic in general. You have to be more specific to get anywhere. You have to choose some axioms. Ideally the axioms you need for your application correspond to a named set of axioms that has been studied before. 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:…

Euclidean geometry dates back at least to Euclid (circa 300 BC), and so you might think it’s been pretty well picked over by now. And yet people still occasionally discover new plane geometry theorems. 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…

Despite the predictions that no one would ever put build data centers in space, Google is starting on Thursday. Google’s prototype satellite will be one of 130 payloads on SpaceX’s Transporter 18 mission on October 1. 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…

In the novel Carry On, Mr. Bowditch, a sailor asked Nathaniel Bowditch to teach him how to do navigational calculations, but the man only knows how to add and subtract by counting on his fingers. He had not heard of multiplication. Bowditch is surprised, but realizes if he made tables of logs of trig functions, then it would be possible for barely numerate sailors to calculate their position. Carry On, Mr. Bowditch is fiction, but it’s essentially factual, and so I imagine something like the…

A couple days ago a friend told me about the book Carry On, Mr. Bowditch, a fictional account of the life of Nathaniel Bowditch (1773–1838). I’ve been listening to the book on Audible, and apparently it’s only lightly fictionalized. 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…

Suppose you want to solve a triangle. You know two sides and the angle between them. Then you can solve for the third side using the law of cosines. 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…

Nothing grows exponentially forever. What appears to be an exponential curve often turns out to be some sort of S curve, such as a logistic curve. 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…

There’s a common saying in discussion of fractals that the length of a coastline depends on how small a device you use to measure it. I thought this was a hypothetical, say as applied to the steps in the construction of the Koch snowflake. But the saying has its roots in actually surveying. Lewis Fry Richardson discovered in 1803 that the length of the coast of Scotland depended on a the size of segments used to measure it. And he found that the length followed a power law, i.e. that there’s a…

I recently bought a copy of Los Alamos Rolodex, a book displaying business cards from Los Alamos Nation Labs from 1967 to 1978. You can find some examples of the cards here. 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 ingore “rcury”. So the phone…

I’ve written three posts on cosine similarity lately. The first looked at interpreting cosine similarity. The second looked at an approximation related to the first. The third looked at how ranking according to cosine similarity works better than cosine similarity itself. 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…

Yesterday I wrote about the canonical example of how vector embeddings of words add: “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.…

The product of four consecutive Fibonacci numbers equals the product of two consecutive integers. 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 Fn Fn+1 Fn+2 Fn+3 = m(m +…

The previous post looked at how to interpret cosine similarity, or equivalently angles between word vectors. In a high-dimensional space, randomly chosen vectors are likely nearly perpendicular, and so relatively large angles, such as 50°, indicate very closely related words. 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…