2026-08-14 09:35:05
Yesterday Levent Alpöge announced that he and his colleagues had discovered a new Hadamard matrix using Claude AI. That motivated a post I wrote this morning on how to construct Hadamard matrices. I mentioned in that post that these matrices arise in applications.
This evening I gave an example, describing how NASA used a Hadamard matrix of order 32 to transmit photos from the Mariner 9 spacecraft in 1971. This post will give another application: sphere packing.
Conway and Sloane [1] give a correspondence between binary codes and sphere packings that they call Construction A. Given an (n, M, d) binary code C, center a sphere on a point x if and only if x is a congruent (mod 2) to codeword in C.
Here (n, M, d) means an error correcting code that encodes M bits of data as strings of n bits, with a minimum Hamming distance between code words of d, i.e. all codewords differ in at least d bits.
The previous post described how to create a (32, 6, 16) code by stacking a Hadamard matrix H of order 32 on top of −H and turning −1’s into 0’s. The analogous construction for a (8, 4, 4) Hadamard code gives E8, the densest packing in ℝ8.
We start with the Hadamard matrix
and obtain the matrix
whose centers form the sphere packing.
This doesn’t look like the E8 sphere packing as it is usually presented, but it’s isomorphic.
[1] J. H. Conway and N. J. A. Sloane. Sphere Packings, Lattices and Groups. Springer. 1999.
The post Hadamard Codes and Sphere Packing first appeared on John D. Cook.
2026-08-14 07:54:21
NASA set Mariner 9 to photograph Mars in 1971. The images had to be encoded for transmission using an error-correcting code, otherwise they would be significantly corrupted when they were received on Earth.
The images were encoded for transmission using a code based on Hadamard matrices, specifically a (32, 6, 16) Hadamard code. This means that each 6-bit pixel value was encoded as a 32-bit code word, with all code words differing in at least 16 positions.
The previous post explained a way to construct Hadamard matrices of order 2n. Use this process to create a 32 × 32 Hadamard matrix H and create a 64 × 32 matrix M by stacking H on top of −H. Then form a matrix M′ by changing all the −1 entries to 0. The rows of M′ are the code words.
For a 6-bit photo pixel value, one of the bits determines whether to read a code word from the top half or bottom half of M′. The other five bits determine which row to choose.
So a pixel is transmitted as a 32-bit codeword c, one of the 64 rows of M′. Ideally c would be received, but possibly some corrupted versions c′ is received with some of bits flipped.
Replace all the 0’s in c′ with −1 to create c″. Now multiply M by c″, thinking of the latter as a column vector. This yields a column vector of length 64. The largest component of this vector corresponds to the row of M′ that was most likely sent.
To see this, suppose there was no corruption: c was transmitted and c was received. Then the product Mc″ has a 32 in the entry corresponding to c and zeros everywhere else. If no more than 7 bits in c were corrupted, the row with the largest entry corresponds to the row that was transmitted.
In practice the product Mc″ can be computed using an algorithm analogous to the FFT using fewer operations than it would take to multiply a general 64 × 32 matrix by a 32 × 1 matrix.
The post How NASA’s Mariner 9 probe encoded images first appeared on John D. Cook.2026-08-13 23:02:41
A Hadamard matrix is an orthogonal matrix whose entires are all either 1 or − 1. For example
is a Hadamard matrix of order 2. True to Stigler’s law of eponymy, James Joseph Sylvester investigated Hadamard matrices before Jacques Hadamard. Sylvester saw how to bootstrap the example above into more examples. If H is a Hadamard matrix, then the partitioned matrix
Sylvester’s construction can be generalized as follows. If Hm is a Hadamard matrix of order m and Hn is a Hadamard matrix of order n, the the Kronecker product Hm⊗Hn is a Hadamard matrix of order mn. That is, you can form a new Hadamard matrix by taking the matrix Hm and replacing ±1 with the matrix ±Hn.
Let S be the set of all possible Hadamard matrix orders. By the construction above, this set is closed under multiplication. Since 2 is in S, every power of 2 is in S. Hadamard proved that all n ≥ 4 in S are multiples of 4. That is, the condition 4 | n is necessary. He conjectured that it was also sufficient, though that has not been proven.
So the big question is what is the set S. Is there some multiple of 4 not in S? Until that question is answered, what is the smallest multiple of 4 not known to be in S? Hadamard matrices are useful in applications, so constructing Hadamard matrices of various orders is useful even while Hadamard’s conjecture remains open. For example, see the next post for how NASA used Hadamard matrices to transmit photographic images back from Mars.
Raymond Paley came up with a way of constructing Hadamard matrices of size q + 1 if q is a prime power congruent to 3 mod 4, and of size 2(q + 1) if q is a prime power congruent to 1 mod 4. Let’s see what we can squeeze out of this.
If p is a prime congruent to 1 mod 4, every power of p is also congruent to 1 mod 4, and so there exist Hadamard matrices of order 2(pk + 1) for every k.
If p is a prime with p = 3 mod 4, then even powers of p are congruent to 1 mod 4 and odd powers of p are congruent to 3 mod 4. So there are Hadamard matrices of order 2(p2k + 1) and of order p2k+1 + 1.
Let’s run a script to see what we can learn from this.
from sympy import primerange
s = set()
for p in primerange(20):
if p % 4 == 1:
s.update([2*(p**k + 1) for k in range(1, 10)])
if p % 4 == 3:
s.update([2*(p**(2*k) + 1) for k in range(1, 6)])
s.update([p**(2*k + 1) + 1 for k in range(1, 6)])
print(sorted(s)[:20])
This prints
12, 20, 28, 36, 52, 100, 164, 244, 252, 340]
We can add 16 to the list because it’s a power of 2, and we can add 24 because it’s 2 × 12, etc. But there doesn’t seem to be any way to get 44. There is a way to create a Hadamard matrix of order 44, but it doesn’t follow from anything we’ve seen so far.
I have a book published in 1996 that says Hadamard’s conjecture had been verified for n up to 428. Until yesterday, the smallest multiple of 4 for which nobody had found a corresponding Hadamard matrix was 668. Then Levent Alpöge announced that he and his and collaborators found an example of size 668 and filled in all remaining gaps below 2000.
So now the set S is known to contain {1, 2, 4, 8, 12, 16, …, 2000}. It also contains all orders that can be obtained by Paley’s method and other methods. And it contains all products of its elements. But it is not yet known to contain 2004.
2026-08-12 21:17:03
Suppose you’ve never worked at the command line and you’re reading a book about the bash shell. You read that !$ is a shortcut to refer to the last word of the previous command. That little fact will almost certainly not stick in your head for a couple reasons. First, you probably see no need for such a shortcut. Second, the syntax seems completely arbitrary.
But then after you use the command line a while, you might begin to notice a pattern. You often have to run a pair of commands with the same last argument, such as when you make a directory then navigate into it.
mkdir /some/long/path/name cd /some/long/path/name
Maybe someone sees you typing this and offers a helpful suggestion: you can type !$ to repeat the last part of the previous command.
mkdir /some/long/path/name cd !$
Once you learn this, you’ll see uses for it regularly. Sorta like when you buy a green Toyota Corolla and suddenly become aware how many green Toyota Corollas there are out there.
So then you start to use !$, but you have some doubts: is the syntax !$ or $!? As long as it’s just two cryptic symbols, you may have a hard time remembering.
Although the command line is cryptic, it is also consistent. On the command line, and in Unix [1] culture more generally, ! refers to a command. For example, you can run a command from inside the Vim text editor with the :! command. And $ often refers to the end of something, such as the end of a string in a regex. So you type !, telling the shell that you’re about to refer to part of a string, then type $ to specify that last part.
The characters !$ are an example of an event designator, a sort of mini language for referring to parts of commands. The syntax may seem mysterious, but every bit of it is analogous to syntax elsewhere in Unix culture. For example,
!:s/foo/bar/
replaces the first instance of foo with bar, and
!:gs/foo/bar/
will replace all instances. This is very similar to commands in sed and in vi For more on event designators, see this recent article by Filip Roséen.
There’s a saying that when the student is ready, the teacher will appear [2]. A less woo-woo version of this saying would be that until the student is ready, it doesn’t matter whether a teacher is there. Once you’ve used the command line to see a need for various shortcuts, there’s a much better chance they’ll stick.
[1] Linux has so thoroughly eclipsed Unix that many people say “Linux” when they’re referring to things inherited from Unix that are now part of Linux and other operating systems, as well as various software packages and programming languages.
Here’s a plot of references to Unix versus Linux over time, via Google’s ngram viewer.
[2] When I first heard this, someone told me it was an Asian proverb. It sure sounds like one. But apparently it comes from a 19th century pastiche of eastern and western ideas.
The post Cryptic but consistent first appeared on John D. Cook.2026-08-11 22:09:46
I was reading a blog post on boat names because it was on Hacker News this morning. The post contained a link to a data set on dog names in NYC and I poked around the data a little. The top names were not at all what I expected, but then again this is limited to NYC; it’s not a sample across the US. These were the top 10 names:
I wondered if the name frequencies might fit a power-law distribution. They do not, but they follow a log-normal distribution remarkably well.
2026-08-11 20:04:24
Suppose you were able to go back in time, to an era before computers, and give someone contemporary cryptography. Encryption methods that are essentially unbreakable now would certainly be unbreakable then. But there’s a catch: not only do attackers not have computers, neither do users.
If you told someone about RSA encryption, for example, you’d lose them right after you said “First you find a couple 1000-digit primes.” But there’s no need for using 1000-digit primes if no attacker has a computer. You could use 100 digit primes. Could you use 10 digit primes? If you chose primes just big enough to make the method unbreakable by hand, could someone implement it by hand?
Kirchoff’s principle says the strength of an encryption method should depend only on keeping the key secret, not the method. If you could keep the method secret, RSA would be unbreakable because nobody thought of anything like it before computers. But to make our thought experiment more interesting, let’s suppose that an enemy has also traveled back in time. If you tell your side about RSA, he can tell his side about it as well. So we’re back to Kirchoff’s principle.
An encryption method combinining substitution and permutation would have been practical to carry our manually. The ADFGVX cipher from 1918 was a start in this direction. That idea could been extended further, with a larger substitution set and longer permutations, and with more than one round of substitution and permutation, approaching what would be come the approach used in modern symmetric encryption. Such a method might have been manually implementable without being manually breakable.
World War II was a time of transition from manual cryptography to computerized cryptography. Encryption machines were attacked by cryptanalysis machines, though these machines were general-purpose computers. If you could implement a symmetric encryption method like AES in a mechanical device, no mechanical device could break it.
You could use something like DES, simpler than AES but still unbreakable at the time. DES is considered broken because now you could throw enough compute power at it to break it by brute force, but that would not be possible with only mechanical devices.
My hunch is that the best approach would be stream ciphers. Maybe it would be practical to implement one of these by hand or with the aid of simple calculating machines. Something like PCG, which is not cryptographically secure today [1], would have been then, though I don’t know how practical it would have been to carry out PCG, say, in the 1940s.
[1] In 2020, Charles Bouillaguet, Florette Martinez, and Julia Sauvage were able to break PCG using 20,000 CPU-hours. See their paper Practical seed-recovery for the PCG Pseudo-Random Number Generator. IACR Transactions on Symmetric Cryptology. ISSN 2519-173X, Vol. 2020, No. 3, pp. 175–196.
The post Manually unbreakable cryptography first appeared on John D. Cook.
