John D. Cook

A few days ago I blogged about the elliptic curve secp256k1 and its use in Bitcoin. This curve has a sibling, secp256r1. Note the “r” in the penultimate position rather than a “k”. Both are defined in SEC 2: Recommended Elliptic Curve Domain Parameters. Both are elliptic curves over a field zp where p is a […]

I wrote a new blog post this morning, but for some reason it posted with an earlier date and so it doesn’t show up at the top of the blog. Here it is: Addition carries and Markov chains

Many consider Ada Lovelace to be the first programmer. An article from a couple days ago asks what did her program do? In a sense, nothing. It was written for a computer that did not exist, so it was never executed. But it was written to compute the 8th Bernoulli number. The article’s author created […]

It’s been known for some time that carbon can form structures with positive curvature (fullerenes) and structures with zero curvature (graphene). Recently researches discovered a form of carbon with negative curvature (schwartzites). News story here. More curvature posts: Squircles Curvature of an egg Curvature and automatic differentiation

Descriptions of cryptography algorithms often start with something like “Let p be a large prime” or maybe more specifically “Let p be a 256 bit prime.” How hard is it to find large prime numbers? Let’s look at the question in base b, so we can address binary and base 10 at the same time. The prime number […]

Schnorr groups, named after Claus Schnorr, are multiplicative subgroups of a finite field. They are designed for cryptographic application, namely as a setting for hard discrete logarithm problems. The application of Schnorr groups to Schnorr signatures was patented, but the patent ran out in 2008. There has been a proposal to include Schnorr signatures in Bitcoin, […]

Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) based on elliptic curve cryptography. The particular elliptic curve is known as secp256k1, which is the curve y² = x³ + 7 over a finite field to be described shortly. Addition on elliptic curves in the plane is defined geometrically in terms of where lines intercept […]

Currying is a simple but useful idea. (It’s named after logician Haskell Curry [1] and has nothing to do with spicy cuisine.) If you have a function of two variables, you can think of it as a function of one variable that returns a function of one variable. So starting with a function f(x, y), […]

There’s no perfectly satisfying way to map the globe on to a flat surface. Every projection has its advantages and disadvantages. The Mercator projection, for example, is much maligned for the way it distorts area, but it has the property that lines of constant bearing correspond to straight lines on the map. Obviously this is […]

The original butterfly effect The butterfly effect is the semi-serious claim that a butterfly flapping its wings can cause a tornado half way around the world. It’s a poetic way of saying that some systems show sensitive dependence on initial conditions, that the slightest change now can make an enormous difference later. Often this comes up […]

In The Big Bang Theory, Sheldon Cooper explains an extension of the game Rock, Paper, Scissors by introducing two more possibilities, Lizard, and Spock. Sam Kass and Karen Bryla invented the game before it became widely known via the television show. The diagram below summarizes the rules: Alternative rules Imagine yourself in the position of Sam […]

Given two objects A and B, Hom(A, B) is simply the set of functions between A and B. From this humble start, things get more interesting quickly. Hom sets To make the above definition precise, we need to say what kinds of objects and what kinds of functions we’re talking about. That is, we specify […]

How do you operate a data-driven application before you have any data? This is known as the cold start problem. We faced this problem all the time when I designed clinical trials at MD Anderson Cancer Center. We uses Bayesian methods to design adaptive clinical trial designs, such as clinical trials for determining chemotherapy dose […]

Today’s exponential sum looks like three octagons, slightly rotated with respect to each other. I thought that the graph was tracing out one octagon, then another, then another. But that’s not what it’s doing at all. You can see for yourself by going to the exponential sum page and clicking the animate link. The curve […]

Today’s the first day of a new month, which means the exponential sum of the day will be simpler than usual. The exponential sum of the day plots the partial sums of where m, d, and y are the month, day, and (two-digit) year. The n/d term is simply n, and integer, when d = 1 and so it has no effect […]

Here’s how to construct what John Horton Conway calls his “subprime fib” sequence. Seed the sequence with any two positive integers. Then at each step, sum the last two elements of the sequence. If the result is prime, append it to the sequence. Otherwise divide it by its smallest prime factor and append that. If […]

Symmetric Gaussian matrices The previous post looked at the distribution of eigenvalues for very general random matrices. In this post we will look at the eigenvalues of matrices with more structure. Fill an n by n matrix A with values drawn from a standard normal distribution and let M be the average of A and its transpose, i.e. M = ½(A […]

Suppose you create a large matrix M by filling its components with random values. If M has size n by n, then we require the probability distribution for each entry to have mean 0 and variance 1/n. Then the Girko-Ginibri circular law says that the eigenvalues of M are approximately uniformly distributed in the unit disk in the complex plane. […]

Here are the most popular posts on my site according to the number of points given on Hacker News. The most important skill in software development (742) Four hours of concentration (329) Why programmers are not paid in proportion to productivity (278) Golden powers are nearly integers (277) Why isn’t everything normally distributed? (250) Kalman […]

Names for extremely large numbers are kinda pointless. The purpose of a name is to communicate something, and if the meaning of the name is not widely known, the name doesn’t serve that purpose. It’s even counterproductive if two people have incompatible ideas what the word means. It’s much safer to simply use scientific notation […]

Melissa O’Neill has a new post on generating random numbers from a given range. She gives the example of wanting to pick a card from a deck of 52 by first generating a 32-bit random integer, then taking the remainder when dividing by 52. There’s a slight bias because 232 is not a multiple of […]

When mathematicians run out of symbols, they turn to other alphabets. Most math symbols are Latin or Greek letters, but occasionally you’ll run into Russian or Hebrew letters. Sometimes math uses a new font rather than a new alphabet, such as Fraktur. This is common in Lie groups when you want to associate related symbols to […]

I don’t understand homotopy groups of spheres, and it’s OK if you don’t either. Nobody fully understands them. This post is really more about information compression than homotopy. That is, I’ll be looking at ways to summarize what is known without being overly concerned about what the results mean. The task: map two integers to […]

Which has more mobility on an empty chessboard: a rook, a king or a knight? On an ordinary 8 by 8 chessboard, a rook can move to any one of 14 squares, no matter where it starts. A knight and a king both have 8 possible moves from the middle of the board, fewer moves […]

I’ve written before about a knight’s random walk on an ordinary chess board. In this post I’d like to look at the generalization to three dimensions (or more). So what do we mean by 3D chess? For this post, we’ll have a three dimensional lattice of possible positions, of size 8 by 8 by 8. […]

NASA has fueled the development of lots of spinoff technologies: smoke detectors, memory foam, infrared ear thermometers, etc. NASA didn’t pursue these things directly, but they were a useful side effect. Something analogous happens in mathematics. While pursuing one goal, mathematicians spin off tools that are useful for other purposes. Algebraic topology might be the […]

If all you know about a person is that he or she is around 5′ 7″, it’s a toss-up whether this person is male or female. If you know someone is over 6′ tall, they’re probably male. If you hear they are over 7″ tall, they’re almost certainly male. This is a consequence of heights […]

When I was in college, one of the professors seemed to lecture at a sort of quadratic pace, maybe even an exponential pace. He would proceed very slowly at the beginning of the semester, so slowly that you didn’t see how he could possibly cover the course material by the end. But his pace would […]

A friend asked me a question the other day that came out of a graphics application. He needed to trace out an ellipse in such a way that the length of curve traced out each second was constant. For a circle, the problem is simple: (cos(t), sin(t)) will trace out a circle covering a constant […]

The Catalan numbers Cn are closely related to the central binomial coefficients I wrote about recently: In this post I’ll write C(n) rather than Cn because that will be easier to read later on. Catalan numbers come up in all kinds of applications. For example, the number of ways to parenthesize an expression with n terms is the nth Catalan […]

The sum of the squares of consecutive Fibonacci numbers is another Fibonacci number. Specifically we have and so we have the following right triangle. The hypotenuse will always be irrational because the only Fibonacci numbers that are squares are 1 and 144, and 144 is the 12th Fibonacci number.

It’s hard to find bounds on binomial coefficients that are both simple and accurate, but in 1990, E. T. H. Wang upper and lower bounds on the central coefficient that are both, valid for n at least 4. Here are a few numerical results to give an idea of the accuracy of the bounds on a […]

The blog post that kicked off the recent series of posts looked at how far apart xy and yx are for quaternions. There I used the Euclidean distance, i.e. || xy – yx ||. This time I’ll look at the angle between xy and yx, and I’ll make some analogous graphs for octonions. For vectors x and y in three dimensions, the dot […]

An earlier post included code for multiplying quaternions, octonions, and sedenions. The code was a little clunky, so I refactor it here. def conj(x): xstar = -x xstar[0] *= -1 return xstar def CayleyDickson(x, y): n = len(x) if n == 1: return x*y m = n // 2 a, b = x[:m], x[m:] c, […]

Quaternion multiplication is associative but not commutative. An earlier post looked at the average size of the commutator xy – yx as a measure of how far quaternion multiplication is from being commutative. This post looks at an analogous question for octonions. Octonion mulitplication is neither commutative nor associative. So in this post we look at the […]

The previous post discussed octonions. This post will implement octonion multiplication in Python, and then sedenion multiplication. Cayley-Dickson construction There’s a way to bootstrap quaternion multiplication into octonion multiplication, so we’ll reuse the quaternion multiplication code from an earlier post. It’s called the Cayley-Dickson construction. For more on this construction , see John Baez’s treatise […]

A group is a set with a binary operation that closed associative, has an identity, and has inverses. This post will look at each of these properties and what happens if you modify or remove it. Magmas Closed means that applying the binary operation to any two elements of the set yields another elements of […]

Given two quaternions x and y, the product xy might equal the product yx, but in general the two results are different. How different are xy and yx on average? That is, if you selected quaternions x and y at random, how big would you expect the difference xy – yx to be? Since this difference would increase proportionately if you increased the length of x […]

Today’s exponential sum is appropriate for a hot July day. Each day the exponential sum page shows a different exponential sum with the month, day, and year in the denominators of an exponential sum. The graphs are formed by plotting the partial sums and connecting the dots. For example, today’s sum, is based on the […]

Suppose you have an odd prime p and an integer a, with a not a multiple of p. Does a have a square root mod p? That is, does there exist an integer x such that x² is congruent to a mod p? Half the time the answer is yes, and half the time it’s no. (We will remove the restriction that p is prime near […]

The relationship between programming and computer science is hard to describe. Purists will say that computer science has nothing to do with programming, but that goes too far. Computer science is about more than programming, but it’s is all motivated by getting computers to do things. With few exceptions. students major in computer science in […]

A while back I wrote about how planets are evenly spaced on a log scale. I made a bunch of plots, based on our solar system and the extrasolar systems with the most planets, and said noted that they’re all roughly straight lines. Here’s the plot for our solar system, including dwarf planets, with distance […]

Objectives and constraints are symmetrical in a mathematical sense but are asymmetrical in a psychological sense. By taking dual formulations, you can reverse the mathematical role of objectives and constraints, but in application objectives are more obvious than constraints. In the question “What is the minimum value of x² over the interval [1, 5]?” the […]

In the previous post I said that the Jacobi functions are like trig functions. That’s true if you look along the real axis. If you look at the rest of the complex plane you’ll see how they can be very different. The sine function is periodic along the real axis, but it grows exponentially along […]

Jacobi’s elliptic functions are sorta like trig functions. His functions sn and cn have names that reminiscent of sine and cosine for good reason. These functions come up in applications such as the nonlinear pendulum (i.e. when θ is too large to assume θ is a good enough approximation to sin θ) and in conformal […]

The complex numbers make a field out of pairs of real numbers. The quaternions almost make a field out of four-tuples of numbers, though multiplication is not commutatative. Technically, quaternions form a division algebra. Frobenius’s theorem says only real vector spaces that can be made into division algebras are the real numbers, complex numbers, and […]

Here are three things about dominoes, two easy and one more advanced. Counting First, how many pieces are there in a set of dominoes? A domino corresponds to an unordered pair of numbers from 0 to n. The most popular form has n = 6, but there are variations with other values of n. You can show that […]

I asked two questions on twitter yesterday. The previous post summarized the results for a question about books that I asked from my personal Twitter account. This post will summarize the results of a question I asked from @AnalysisFact. If a genie offered to give you a thorough understanding of one theorem, what theorem would […]

I asked on Twitter today for books that people would like to have read, but don’t want to put in the time and effort to read. What’s a book you would like to have read but don’t want to read? — John D. Cook (@JohnDCook) June 15, 2018 Here are the responses I got, organized […]

Here are a couple of linear algebra identities that can be very useful, but aren’t that widely known, somewhere between common knowledge and arcane. Neither result assumes any matrix has low rank, but their most common application, at least in my experience, is in the context of something of low rank added to something of […]