John D. Cook

The idea of proof of work (PoW) was first explained in a paper Cynthia Dwork and Moni Naor [1], though the term “proof of work” came later [2]. It was first proposed as a way to deter spam, but it’s better known these days through its association with cryptocurrency. If it cost more to send […]

The Hagia Sophia (Greek for “Holy Wisdom”) was a Greek Orthodox cathedral from 537 to 1453. When the Ottoman Empire conquered Constantinople the church was converted into a mosque. Then in 1935 it was converted into a museum. No musical performances are allowed in the Hagia Sophia. However, researchers from Stanford have modeled the acoustics […]

There are several things in math and statistics named gamma. Three examples are the gamma function the gamma constant the gamma distribution This post will show how these are related. We’ll also look at the incomplete gamma function which connects with all the above. The gamma function The gamma function is the most important function […]

In 1999, Harvard law professor Lawrence Lessig stated that software is a kind of law. The algorithms of tech giants have an influence comparable to, and maybe in some ways greater than, statutory law. The code is law. … Activists concerned with defending liberty, privacy or access must watch the code coming from the Valley—call […]

Differential privacy is a strong form of privacy protection with a solid mathematical definition. Roughly speaking, a query is differentially private if it makes little difference whether your information is included or not. This intuitive idea can be made precise as follows. Queries and algorithms First of a differential privacy is something that applies to queries, […]

I stopped posting to the @FormalFact Twitter account last July, but I didn’t deactivate the account. Now I’m going to restart it. Unlike my other Twitter accounts, I don’t plan to have a regular posting schedule. I may not post often. We’ll see how it goes. I’ve changed the account name from @FormalFact to @LogicPractice. The […]

Every rational number can be expanded into a continued fraction with positive integer coefficients. And the process can be reversed: given a sequence of positive integers, you can make them the coefficients in a continued fraction and reduce it to a simple fraction. In 1954, Arthur Porges published a one-page article pointing out that continued fractions […]

There’s an old saying that if you want to hide a tree, put it in a forest. An analogous principle in privacy is that a record preserves privacy if it’s like a lot of other records. k-anonymity The idea of k-anonymity is that every database record appears at least k times when you restrict your attention to […]

Since integration is the inverse of differentiation, you can think of integration as “dividing” by d. J. P. Ballantine [1] shows that you can formally divide by d and get the correct integral. For example, he arrives at using long division! [1] J. P. Ballantine. Integration by Long Division. The American Mathematical Monthly, Vol. 58, […]

A few weeks ago I wrote about how there are many ways to summarize the operating characteristics of a test. The most basic terms are accuracy, precision, and recall, but there are many others. Nobody uses all of them. Each application area has their own jargon. Biometric security has its own lingo, and it doesn’t […]

In the previous post, I mentioned that modal logic has a lot of interpretations and a lot of axiom systems. It can also have a lot of operators. This post will look at Security Logic, a modal logic for security applications based on a seminal paper by Glasgow et al [1]. It illustrates how modal and […]

Modal logic extends propositional logic with two new operators, □ (“box”) and ◇ (“diamond”). There are many interpretations of these two symbols, the most common being necessity and possibility respectively. That is, □p means the proposition p is necessary, and ◇p means that p is possible. Another interpretation is using the symbols to represent things a person knows to […]

Many encryption algorithms rely on the difficulty of factoring a large number n. If you want to make n hard to factor, you want it to have only two factors. Otherwise, the more factors n has, the smaller the smallest factor must be. So if you want n to be the product of two large primes, p and q, you want […]

“There is no point in being precise when you don’t know what you’re talking about.” — John Tukey It’s a familiar trope in science fiction that the smartest character will answer questions with excess precision. On Star Trek, Scottie might give a number to one significant figure and Spock will correct him giving the same […]

The idea of format-preserving encryption is to encrypt data while keeping its form, a sort of encryption in kind. An encrypted credit card number would look like a credit card number, a string of text would be replaced with a string of text, etc. Format preserving encryption (FPE) is useful in creating a test or demo […]

I’ve mentioned a couple times that Jacobi elliptic functions are generalizations of sines and cosines. In an earlier post I showed how you can make sn and cn from sine and cosine by a nonlinear rescaling of the input. In this post I’ll look at a linear scaling of the input and a sum of sines or […]

In 1956, Thornton Fry wrote an article entitled “Mathematics as a Profession Today in Industry” [1]. The number of mathematicians working in industry had increased dramatically in the preceding few years, and Fry speculated on what the future might hold. I expected the article might have a few amusing predictions, extrapolations from things that seemed […]

The US government does not prohibit the transfer of PHI (protected health information) offshore [1], but it does subject offshore data processing to extra reporting [2] and more scrutiny in general. The CMS (Centers for Medicare & Medicaid Services, part of the Department of Health and Human Services) has said Given the unique risks associated with […]

It’s much easier to convert meters to kilometers than to convert yards to miles. You know what’s even easier? Not converting meters to kilometers! You only need one unit of length, say a meter. You could express all distances in terms of meters and dispense with kilometers, millimeters, etc. And in fact, this is essentially […]

The US uses a mix of imperial and metric units of measure. Some people, almost all outside the US, are quite agitated by this. In practice, the two systems coexist peacefully. Americans buy milk by the gallon and wine by the milliliter. Milk typically comes in gallon jugs, and wine typically comes in 750 milliliter […]

For every integer m > 1, it’s possible to choose N so that the proportion of primes in the sequence 1, 2, 3, … N is 1/m. To put it another way, you can make the odds against one of the first N natural numbers being prime any integer value you’d like [1]. For example, suppose you wanted […]

There are only three posts on this top 10 list that are also on the top 10 list for Hacker News. Why programmers are not paid in proportion to productivity Selection bias and bombers Automate to save mental energy, not time The most important skill in software development Golden powers are nearly integers Ten life […]

My previous post looked at Jacobi functions from a reference perspective: given a Jacobi function defined one way, how do I relate that to the same function defined another way, and how would you compute it? This post explores the analogy between trigonometric functions and Jacobi elliptic functions. Related basic Jacobi functions to trig functions […]

The Jacobi elliptic functions sn and cn are analogous to the trigonometric functions sine and cosine. The come up in applications such as nonlinear oscillations and conformal mapping. Unfortunately there are multiple conventions for defining these functions. The purpose of this post is to clear up the confusion around these different conventions. The image above is […]

The first time you see matrices, if someone asked you how you multiply two matrices together, your first idea might be to multiply every element of the first matrix by the element in the same position of the corresponding matrix, analogous to the way you add matrices. But that’s not usually how we multiply matrices. […]

Suppose you have a number that you believe to be prime. You start reading your number aloud, and someone interrupts “Stop right there! No prime starts with the digits you’ve read so far.” It turns out the person interrupting you shouldn’t be so sure. There are no restrictions on the digits a prime number can […]

Suppose you have two baseball teams, A and B, playing in the World Series. If you like, say A stands for Houston Astros and B for Milwaukee Brewers. Suppose that in each game the probability that A wins is p, and the probability of A losing is q = 1 – p. What is the probability that A will win the series? […]

You can find a large collection of physical constants in scipy.constants. The most frequently used constants are available directly, and hundreds more are in a dictionary physical_constants. The fine structure constant α is defined as a function of other physical constants: The following code shows that the fine structure constant and the other constants that […]

As you read this blog post, you probably have a hierarchy of contexts in the back of your mind. It comes so naturally to you that you don’t consciously think of it. If you’re reading this in a web browser, you probably know what browser you’re using. If not, you’re at least aware that you […]

For each prime p, there is only one group with p elements, the cyclic group with that many elements. It would be plausible to think there is only one group of order n if and only if n is prime, but this isn’t the case. If p and q are primes, then there are ostensibly at least two groups of order pq: […]

Sturm’s separation theorem says that the zeros of independent solutions to an equation of the form alternate. That is, between any two consecutive zeros of one solution, there is exactly one zero of the other solution. This is an important theorem because a lot of differential equations of this form come up in applications. If […]

Here’s today’s exponential sum, 10/1/2018: And here’s what it would look like if September had 31 days, 9/31/2018:

Last evening my electricity went out and this morning it was restored. This got met thinking about systems that fail occasionally [1]. Electricity goes out often enough that we prepare for it. We have candles and flashlights, my work computer is on a UPS, etc. A residential power outage is usually just an inconvenience, especially […]

If you know the vertices of a polygon, how do you compute its area? This seems like this could be a complicated, with special cases for whether the polygon is convex or maybe other considerations. But as long as the polygon is “simple,” i.e. the sides meet at vertices but otherwise do not intersect each […]

According to this paper [1], the empirical distribution of real passwords follows a power law [2]. In the authors’ terms, a Zipf-like distribution. The frequency of the rth most common password is proportional to something like 1/r. More precisely, fr = C r–s where s is on the order of 1. The value of s that […]

C. A. R. Hoare wrote an article How Did Software Get So Reliable Without Proof? in 1996 that still sounds contemporary for the most part. In the 1980’s many believed that programs could not get much bigger unless we started using formal proof methods. The argument was that bugs are fairly common, and that each bug has […]

This morning Sir Michael Atiyah gave a presentation at the Heidelberg Laureate Forum with a claimed proof of the Riemann hypothesis. The Riemann hypothesis (RH) is the most famous open problem in mathematics, and yet Atiyah claims to have a simple proof. Simple proofs of famous conjectures If anyone else claimed a simple proof of […]

Fermat’s little theorem says that if p is a prime and a is not a multiple of p, then ap-1 = 1 (mod p). Euler’s generalization of Fermat’s little theorem says that if a is relatively prime to m, then aφ(m) = 1 (mod m) where φ(m) is Euler’s so-called totient function. This function counts the number of positive […]

There have been a couple news stories regarding proofs of major theorems. First, an update on Shinichi Mochizuki’s proof of the abc conjecture, then an announcement that Sir Michael Atiyah claims to have proven the Riemann hypothesis. Shinichi Mochizuki’s proof of the abc conjecture Quanta Magazine has a story today saying that two mathematicians have […]

Numberphile has a nice video on the fifth root trick: someone raises a two-digit number to the 5th power, reads the number aloud, and you tell them immediately what the number was. Here’s the trick in a nutshell. For any number n, n5 ends in the same last digit as n. You could prove that […]

The Goldbach conjecture says that every even number bigger than 2 is the sum of two primes. I imagine he tried out his idea on numbers up to a certain point and guessed that he could keep going. He lived in the 18th century, so he would have done all his calculation by hand. What […]

John Baez left a comment on my post on group statistics saying It’s known that the number of groups of order p^n for prime p is p^{2n^3/27+O(n^(8/3))}. It might be fun to compare this to what Mathematica says. Here goes. First let’s let p = 2. Mathematica’s FiniteGroupCount function tops out at n = 10. And […]

How do you keep things you don’t want out of your Twitter stream? You might say just don’t follow people who post things you don’t want to read, but it’s not that simple. Some people post worthwhile original material, but they retweet things that are offensive or just not interesting. You can fix that by […]

I just ran across FiniteGroupData and related functions in Mathematica. That would have made some of my earlier posts easier to write had I used this instead of writing my own code. Here’s something I find interesting. For each n, look at the groups of order at most n and count how many are Abelian […]

Sometimes simple notation can make a big difference. One example of this is the Kronecker delta function δij which is defined to be 1 if i = j and zero otherwise. Because branching logic is built into the symbol, it can keep branching logic outside of your calculation. That is, you don’t have to write “if … […]

Let u be a real-valued function of n variables, and let v be a vector-valued function of n variables, a function from n variables to a vector of size n. Then we have the following product rule: D(uv) = v Du + u Dv. It looks strange that the first term on the right isn’t Du v. The function uv is a function […]

The p-norm of a vector is defined to be the pth root of the sum of its pth powers. Such norms occur frequently in application [1]. Yoshio Koide discovered in 1981 that if you take the masses of the electron, muon, and tau particles, the ratio of the 1 norm to the 1/2 norm is very nearly 2/3. […]

The Great Pacific Garbage Patch (GPGP) is a huge region of ocean trash twice the area of Texas. I’m trying to understand how dense it is, and running into contradictory information. This article describes a project, Ocean Cleanup, that aims to clean up half the GPGP in five years. How could you possibly clean up […]

I’ve written three blog posts lately about the classification of finite simple groups. I’m done with that topic for now. I may come back and revisit it in the future. So if group theory isn’t your favorite topic, don’t worry. I don’t know what I’ll blog about next, but it’ll probably be one of the […]

The previous post defined the groups PSL(n, q) where n is a positive integer and q is a prime power. These are finite simple groups for n ≥ 2 except for PSL(2, 2) and PSL(2, 3). Overlap among PSL(n, q) There are a couple instances where different values of n and q lead to isomorphic groups: PSL(2, 4) and PSL(2, 5) are […]