2026-10-08 21:43:02
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.
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.
[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 post Privacy policies and modal logic first appeared on John D. Cook.2026-10-08 06:29:28
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
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.
The post Consequences of progress toward the Riemann Hypothesis first appeared on John D. Cook.2026-10-08 05:41:47
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.
2026-10-08 05:19:20
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
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³.
The post Irrationality exponent of π first appeared on John D. Cook.2026-10-07 08:21:52
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.
The post Lissajous and Bowditch first appeared on John D. Cook.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.
2026-10-07 03:46:28
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.
The post A topological model for provability logic first appeared on John D. Cook.
