{z : |p(z)| = 1}

for each degree n?

Erdős conjectured that the maximum length was obtained by the polynomial p(z) = zⁿ − 1. He was right, as Teng Zhang proved recently.

Examples

Here’s an example for degree five. The maximum length is obtained by p(z) = z⁵ − 1.

This curve has length 15.02.

Here’s the corresponding curve for p(z) = z⁵ − z

which has length 6.909.

In general the level set {z : |p(z)| = 1} need not be connected, in which case the length is the sum of the lengths of the components.

Here’s an example that tweaks the constant parameter of the optimal curve p(z) = z⁵ − 1.1.

This curve has (total) length 14.59.

Details

The length of the maximum curve for given n is the length for the polynomial p(z) = zⁿ − 1. The only curves obtaining the maximum length are translations and rotations of this curve.

Note that for n = 1 the maximum curve is a circle and for n = 2 the curve is the lemniscate of Bernoulli. The general curve is called the Erdős lemniscate of order n, generalizing Bernoulli’s lemniscate.

The maximum length for given n is

2^1/n B(1/n, 1/2n)

where B is the beta function.

The Erdős lemniscates look similar to the “rose” curves r = cos(nθ), but these curves are not polynomial level sets.

Related posts

• Lemniscate functions
• Cassini ovals

The shell !$ saves the last part of the latest command. (Mnemonic: bang often refers to commands, such as !! to redo the previous command, and cash often refers to the last of something, such as the end of a line in a regular expression.)

This comes in handy, for example, when you copy a file to a directory and then want to cd into that directory.

cp myfile /big/long/path
cd !$

The !$ variable is fragile, however. The sequence of commands

cp myfile /big/long/path
ls
cd !$

won’t work because after running ls the variable !$ now contains “ls” rather than “/big/long/path”.

There are two ways to fix this. In the previous example you could change the last command to

cd !-2:$

This says go back two commands (!-2) and extract (:) the last argument ($).

Another possibility is

cd !cp:$

This says to pull up the most recent command that started with “cp” (!cp) and extract the last argument.

This only scratches the surface of conveniences bash offers. To learn about similar features, search on “history expansion” or “event designators.”

Because bash offers so many shortcuts, it’s hard to learn any of them from reading the manual: nothing will stick. It reminds me of when I was in Paris and had one hour to see the Louvre. I should have meandered around a room or two and been content with that. Instead, I blitzed through the museum. I wanted to “see the Louvre” but I didn’t really see anything.

Kepler’s third law

A recent article from Smithsonian magazine says a new dwarf planet candidate is 46 times further from the sun as earth is, and it takes 281.1 years to orbit the sun.

I did a back-of-the-envelope calculation and thought something was wrong. Kepler’s third law says

T² = c a³.

Here T is the orbital period and a is the semimajor axis. If T is measured in years and a is measured in astronomical units (AU) then the proportionality constant c equals 1.

If T = 281.1 years, then a = 42.91 AU, not 46 AU.

Eccentricity

The difference between 46 AU and 42.91 AU is only a contradiction if we assume the dwarf planet is in a circular orbit. The semimajor axis a is the the maximum distance to the center of the orbit, not the distance to the sun. In an elliptical orbit, the focus of the ellipse where the sun sits is not at the center. The orbit is eccentric, meaning off-center.

Assume the dwarf planet candidate ED138 is in an orbit with semimajor axis 42.91 AU. What does the article mean when it says ED138 is “46 times farther from the sun than Earth is”? Does is mean that it is currently 46 AU from the sun, or that its maximum distance from the sun at aphelion is 46 AU? Presumably the latter.

If the distance to the dwarf at aphelion is 46 AU and the semimajor axis is 42.91 AU, then the distance between the sun and the center of the dwarf’s elliptical orbit is c = 3.09 AU. The eccentricity is then

e = c/a = 3.09/46 = 0.067

making the orbit more eccentric than that of Saturn but less than that of Mars. This would make the semiminor axis, the minimum distance to the center of the orbit,

b = a √(1 – e²) = 45.9.

The orbit isn’t far from circular, but far enough to account for the substantial difference between the distance to the sun and the distance to the center of the ellipse.

This touches on something that has come up before, and that is eccentricity doesn’t affect the shape of an orbit so much as the position of the sun in that orbit. The orbit of ED138 isn’t far from being circular, but the sun is significantly off-center in that orbit.

Related posts

• Planetary orbits are very nearly circular
• Mean distance to the sun
• Max and min orbital speed
• GPS satellite orbits
• Monoliths and Lagrange points

Image credit: NSF-DOE Vera C. Rubin Observatory / NOIRLab / SLAC /AURA / R. Proctor

Example

For example, consider the permutation

p = [5, 6, 2, 1, 0, 8, 3, 4, 9, 7]

that sends i to p(i). Here indices start with 0.

The number 2 is a fixed point: p(2) = 2. So it has a cycle length of 1.

The number 1 is part of a cycle of length 3: p(1) = 6, p(6) = 3, and p(3) = 1.

The longest cycle is [0, 5, 8, 9, 7, 4] which has length 6.

Longest cycles

What happens to the length of cycles as you permute longer lists? Obviously the longest possible cycle increases with the length of the list, but what happens to the average length of the longest cycle?

Let L_n be the length of the longest cycle in a random permutation of n items. You’d expect the average value of L_n, written E[L_n], would increase when n increases. But do they increase at the same rate? Conceivably E[L_n] goes to infinity as n goes to infinity, but at a slower rate, say proportional to √n rather than proportional to n. Let’s make a plot to see.

There’s a lot of variance, but the central tendency looks approximately linear in n. Let’s repeat our experiment, this time creating 100 random permutations of each size and averaging their maximum cycle lengths.

As we’d expect from the central limit theorem, averaging over 100 samples reduced the scatter by about a factor of 10.

It appears that the expected value of the maximum cycle length grows in proportion to n, and in fact the expected value is somewhere around 0.6n. In the example at the top of the post, the longest cycle is exactly 0.6n. I didn’t plan that: the permutation example was chosen at random.

Asymptotic value

The limit of the ratio E[L_n]/n is known to be

Shepp and Lloyd [1] proved the result above. The constant on the right hand side is known as the Golomb-Dickman constant. I think Golomb investigated E[L_n]/n and had found that there was a limiting value, but Shepp and Lloyd were the first to give a closed-form expression for the limit. Dickman had run into the same constant in a theorem in number theory.

[1] L. A. Shepp and S. P. Lloyd, “Ordered Cycle Lengths in a Random Permutation,” Transactions of the American Mathematical Society, vol. 121, no. 2, pp. 340–357, February 1966.

If the fertilizer supplies a nutrient that is already abundant in a particular soil, you won’t see as much benefit from that fertilizer on that soil. Plots of land will vary in other ways besides soil composition—some may receive more sun than others, some may have better drainage, etc.—that may interact with the effect of the fertilizer. So you’d like to test your fertilizers on several different plots of land. Call the number of plots b.

Suppose each of your plots is large enough to test q < n fertilizers, i.e. the plots are not large enough to test every fertilizer on every plot. You would like to design your experiment so that each fertilizer is tested the same number of times, and so that every pair of fertilizers is tested somewhere on the same plot of land for a direct comparison.

The resulting experimental design is called a balanced incomplete block design or BIBD. The blocks are the plots of land. The design is incomplete because you cannot test everything on every plot. The design is balanced because every pair of fertilizers is tested together the same number of times. BIBDs are important in the design of experiments.

A BIBD is a special case of the combinatorial designs discussed in the previous post with parameters (n, q, 2, λ), i.e. the parameter r is set to 2 because you want every pair to appear in some number of blocks.

A design with parameters (n, q, r, λ) is sometimes called an r-(n, q, λ) design [1]. Steiner systems correspond to λ = 1 and BIBDs correspond to r = 2.

While the number of blocks b is of interest, it is not an independent parameter. For combinatorial designs in general the number of blocks is determined by the other parameters:

Similarly, you may see the number of blocks each treatment appears in given as a parameter, but this count is also determined by the other parameters, namely

Examples

Here is a design to test n = 6 treatments on b = 10 plots, testing q = 3 treatments on each plot, with each pair of treatments (i.e. r = 2) appearing in λ = 2 plots, i.e. a (6, 3, 2) design.

    0000011122
    1123423433
    2345554545

The way to read this is that each treatment is a number 0 through 5, and each column indicates the treatments tested in a particular block (plot).

Here is another example, an (8, 4, 3) design: n = 8 treatments, blocks of size q = 4, with each pair of treatments being tested in λ = 3 blocks.

    00000001111222
    11123342334334
    22554666455455
    34675777677766

[1] Combinatorial designs are sometimes called t-designs, which makes sense if you denote the size of the set you’re looking for in each block by t but not if you denote it by r. You’ll see both conventions. And while we’re mentioning notational variations, the number of treatments is sometimes denoted v for variety, going back to agricultural applications, testing crop varieties.

The posts on finite geometry gave examples of Steiner triples and more generally Steiner systems, introduced in the previous post. Combinatorial designs take this one step further.

The previous post gave the following definition:

A Steiner triple system, written STS(n), is a collection of three-element subsets, called blocks, of a set X with n elements, such that every two-element subset of X belongs to exactly one block.

The post pointed out that the smallest projective plane is STS(7) and the smallest affine plane is STS(9).

The post then defined a general Steiner system:

A Steiner system S(t, k, n) is a collection of k-element subsets, called blocks, of a set X with n elements, such that every t-element subset of X belongs to exactly one block.

Moving from Steiner triples to Steiner systems we generalized the size of the blocks from 3 to k, and generalized the size of sets contained in a unique block from 2 to t.

Combinatorial designs take this one step further by generalizing the number of blocks that a set of t elements falls in from 1 to λ.

Unfortunately when we go from Steiner systems to combinatorial designs the notation changes and the order of the parameters changes.

A design with parameters (n, q, r, λ) is a collection of q-element subsets of an n-element set X such that every r-element subset of X is contained in exactly λ blocks.

So a Steiner system S(t, k, n) corresponds to a (n, k, t, 1) design.

Existence of designs

Given a set of parameters (n, q, r, λ) there may or may not exist a design with these parameters. It’s easy to show that a few consistency conditions are necessary. It was long conjectured that these conditions were sufficient, except possibly for a finite number of values of n. Peter Keevash proved in 2024 that the conjecture is correct.

Theorem [1]: Fix q > r ≥ 1 and λ ≥ 1. There is an N, depending on q, r, and λ, such that for every n > N with

for all 0 ≤ i ≤ r, a design with parameters (n, q, r, λ) exists.

[1] Peter Keevash. The existence of designs. https://arxiv.org/abs/1401.3665v4

The post Combinatorial designs first appeared on John D. Cook.]]> https://www.johndcook.com/blog/2026/11/09/steiner-systems/ Mon, 09 Nov 2026 17:01:43 +0000 https://www.johndcook.com/blog/?p=248186 Steiner triples Several examples from the recent posts on finite geometry are special cases of Steiner triples. A Steiner triple system, written STS(n), is a collection of three-element subsets, called blocks, of a set X with n elements, such that every two-element subset of X belongs to exactly one block. STS(7) is the smallest finite projective […]

Recent posts have looked at finite projective and affine planes. This post will look at finite hyperbolic planes.

Finite projective planes come up far more often in application than finite hyperbolic planes. I’ve seen several resources on finite geometries that don’t mention the hyperbolic case. Finite hyperbolic geometries have less structure than their projective or affine counterparts and so are less useful.

The definition of a finite hyperbolic plane isn’t entirely standardized. We will use the following axioms for this post.

1. Any two distinct points lie on exactly one line.
2. Given a line ℓ and a point P not on ℓ, there exist at least two lines through P parallel to ℓ.
3. There exist four points, no three collinear.
4. Every line contains at least two points.

An example of a system satisfying these axioms is the complete graph of six vertices. The nodes are the points and the edges are the lines. In set-theoretic terms, the points are the one-element subsets of {1, 2, 3, 4, 5, 6} and the lines are all possible two-element subsets.

Note that lines in the finite hyperbolic plane are two element sets. The lines {5, 6} and {1, 3}, for example, are parallel because they do not intersect, even though the representations of {5, 6} and {1, 3} in the visualization above are not parallel in the Euclidean sense.

There are many other examples of system satisfying the hyperbolic plane axioms. Too many in some sense. You could say finite hyperbolic systems are less common in application because they are more common in count.

Discrete geometry posts

• Finite projective planes
• Finite affine planes

Affine geometry is essentially what remains of Euclidean geometry if you keep the incidence properties, e.g. wanting to know whether things intersect, and forget about metric properties such as segment lengths and angle measurements. As with projective planes, affine planes can be finite.

The axioms of an affine plane are as follows.

1. Any two distinct points lie on exactly one line.
2. For any line ℓ and point P not on ℓ, there is exactly one line through P that doesn’t intersect ℓ.
3. There exist three points that are not collinear.

The second axiom says that affine geometry is Euclidean, or maybe Euclidean-lite. It lacks features of Euclidean geometry, but it doesn’t contradict Euclidean geometry.

To construct an example of a finite affine plane, let p be an odd prime and construct a p × p grid with x– and y-coordinates 0, 1, 2, …, p − 1. The affine lines are essentially the Euclidean lines that pass through the grid points, if lines can wrap around the sides, i.e. you’re working on a discrete torus. Algebraically, lines are the solutions to x = c and y = mx + b mod p.

A finite affine plane always has n² points and n² + n lines. The number n can be an odd prime, or any prime power greater than 2. It is unknown whether there are examples in which n is not a prime power. There are no affine planes of order 6 or 10, and the case of n = 12 is open.

The axioms of projective plane geometry are as follows.

1. Any two distinct points lie on exactly one line.
2. Any two distinct lines meet in exactly one point.
3. There exist four points, no three of which are collinear.

The most famous example of a finite projective plane is the Fano plane.

It helps to switch back and forth between thinking of finite geometries geometrically and in terms of set theory. The fact that the Fano plane has an easy-to-understand illustration is fortunate, but not to be taken for granted. Also, it could be misleading to lean to heavily on the fact that the lines and points of finite geometry can, in this case, be represented by points and line segments (and a circle) in the Euclidean plane.

The set-theoretic perspective is that the points are the one-element sets {1}, {2}, …, {7}, and the lines are the sets listed in the legend of the graph: {1, 2, 5}, {1, 3, 7}, …, {5, 6, 7}. It’s simple to confirm that any pair of points lines in exactly one of the three-element sets, that the intersection of any pair of the three-element sets is a one-element set, and that there are three points—1, 2, 3, and 4 will do—such that no three lie on the same line, i.e. no three belong to the same three-element set.

The Fano plane is the unique projective plane with 7 points, but there are four non-equivalent projective planes with 10 points.

There are many other examples of non-isomorphic finite projective planes with the same number of points, but there are also many unsettled conjectures, at least as of an hour ago, regarding the existence of finite projective planes of various orders.

Finite geometry might seem like a technicality, spaces that satisfy the axioms but are not what anyone had in mind when the axioms were codified. So why care about finite geometries? For one thing, unexpected examples are quite valuable since they help separate the consequences of a set of axioms from common expectations.

For another, finite geometries come up in applications, such as combinatorics and cryptography. These discrete applications take advantage of intuition from traditional geometry. This intuition is an imperfect guide, so conclusions need to be verified by concrete calculations, but geometric intuition suggests what one ought to verify.

Related posts

• Misleading plots of elliptic curves
• Linear systems over finite fields
• Projective duality

As stated in the post, you can make this statement rigorous by choosing integers up to size N at random and taking the limit as N goes to infinity.

We can also choose a, b, c, and d uniformly from [0, 1]. This is similar to choosing four integers up to N and dividing all the integers by N, which doesn’t change the probabilities.

Now a/b > c/d if and only if ad > bc, so another way to state the theorem is that

Prob(ad > bc | a + d > b + c) = 11/12.

Or to state it yet another way, pick two pairs of numbers at random. The probability that the pair with the larger sum also has the larger product is 11/12. That seems more intuitive to me than the original statement.

If a + d is greater than b + c, it’s likely that a/b is greater than c/d. It seems plausible that if a + d is much greater than b + c, it’s more likely that a/b is greater than c/d. Or in terms of cross products, the more the sum of one pair is bigger than the sum of the other, the more likely the product of the former is to be greater than the latter. That is

f(r) = Prob(ad > bc | (a + d)/(b + c) ≥ r)

should be an increasing function of r. We know the probability above equals 11/12 when r = 1. We expect that the probability should approach 1 as r goes to infinity.

This is indeed the case, as shown in the plot below.

In particular, f(2) ≈ 0.99 and f(6) ≈ 0.999. So if a + d is two (or six) times bigger than b + c, there is a 0.99 (or 0.999) probability that ad is larger than bc.

You can calculate f(r) analytically or estimate it by simulation. I had Claude do both and they produce comparable results. There is a closed-form expression for f(r) but it’s really complicated.

Euclidean geometry

Here are Euclid’s five postulates, statements about what geometric objects can be constructred.

1. To draw a straight line from any point to any point.
2. To produce (extend) a finite straight line continuously in a straight line.
3. To describe a circle with any centre and distance (radius).
4. That all right angles are equal to one another.
5. That, if a straight line falling on two straight lines makes the interior angles on the same side less than two right angles, the two straight lines, if produced indefinitely, meet on that side on which the angles are less than two right angles.

Clearly there’s something different about the fifth postulate, the parallel postulate. It’s much longer and more complicated than the other postulates. There was speculation from ancient times that the parallel postulate might be unnecessary, that it could be derived as a theorem rather than stated as an axiom.

Non-Euclidean geometry

Giovanni Girolamo Saccheri (1667–1733) tried to prove the fifth postulate by contradiction, and in the process began the study of non-Euclidean geometry. He wasn’t the first to try to prove the fifth postulate. Ptolemy, for example, tried to prove the fifth postulate as a theorem in the second century AD. But Saccheri was the first to try a proof by contradiction, or at least the first to extensively explore contradictions to the parallel postulate.

A more modern formulation of the parallel postulate says

Given a line ℓ and a point P not on ℓ, there is exactly one line through P parallel to ℓ.

Non-Euclidean geometry replaces this axiom with an alternative, such as saying there are multiple lines parallel to ℓ or that there are no lines parallel to ℓ.

Note that non-Euclidean geometry is not an arbitrary tinkering with the axioms of geometry just to see what happens. It tinkers with one specific axiom for motivated reasons.

Spherical geometry

You can create models of non-Euclidean geometry using Euclidean geometry. For example, spherical geometry is constructed by defining a (spherical) point as a (Euclidean) point on a sphere, and defining a (spherical) line to be a great circle, the intersection of a (Euclidean) plane with the sphere. In spherical geometry there are no parallel lines: all lines intersect.

This example shows that non-Euclidean geometry need not be non-physical. If you leave general relativity out of the picture and think of physical space as undeniably Euclidean, it can still be useful to think of different geometries to describe objects in Euclidean space.

Projective geometry

In projective geometry, all distinct lines intersect at one point.

In spherical geometry, all distinct lines intersect at two points, on opposite sides of a great circle. If you consider antipodal pairs of points on a sphere to be a single point in the projective plane, now all lines intersect at a single point. Projective geometry is just one step away from spherical geometry.

The recent thread of posts started with a post a couple weeks ago about two versions of the law of cosines on a sphere, one for sides and one for angles. You can go from one to the other by going from a spherical triangle to its polar triangle. That started me going down the rabbit hole of poles and polars, first in spherical geometry, then in plane geometry, then in projective geometry, culminating here.

Now we have two ways of producing poles and polars on a sphere: the original construction in terms of spherical geometry, and the projective construction. They are consistent: you can do spherical geometry, then identify antipodal points, or you can identify antipodal points, then do projective geometry. You end up at the same place by either path.

One theme in the last few posts has been that projective geometry is not an arbitrary exercise in abstraction but a framework that can simplify how we think about things. For example, when I defined the polar triangle of a spherical triangle here, I said that the vertices of the polar triangle are the poles of the sides of the original triangle. Imagine the side as the equator of the sphere and take one of the poles; that’s where the abstract concept of “pole” comes from. But which pole do you take? There is a convention for answering this question, but in projective geometry it doesn’t matter: both (spherical) poles constitute one (projective) point.

Posts in this series

• Duality in spherical trig
• Poles and polars
• Inversion in an ellipse
• Unified view of poles and polars
• Making peace with the projective plane
• From a hack to a rigorous definition

As mentioned in the previous post, we start by adding some “points at infinity” to Euclidean plane to take care of exceptional situations. For example, instead of saying most pairs of lines intersect at a single point but some don’t intersect at all, you could say all pairs of lines intersect at a point, but for some pairs of lines, namely parallel lines, that intersection point is “at infinity.”

Suppose you need to write a program to find the intersection of two lines. The usual way of doing this would be to implement a partial function that takes two lines as input, and sometimes returns a point of intersection and sometimes does something else: it crashes, or throws an exception, or hangs. But if we add in points at infinity, our program could always return a point.

But how are you going to represent points at infinity? It’s not enough to use a floating point infinity, because different lines intersect at different points at infinity. For example, the lines y = 1 and y = 2 intersect at the point at infinity in the horizontal direction, but the lines x = 1 and x = 2 intersect at the point at infinity in the vertical direction. You could say the former lines intersect at (o, inf) and the latter at (inf, 0), but that won’t work in general.

The lines y = 3x + 1 and y = 3x + 1 intersect at the point at infinity with slope 3, but the lines y = 5x + 1 and y = 5x + 1 intersect at the point at infinity with slope 5. If you say both pairs of lines meet at (inf, inf) you’ve lost information.

So you come up with a hack. You represent points not as (x, y) pairs but as (x, y, f) where x and y are real numbers but f is a Boolean flag. Now (x, y, true) represents the ordinary point (x, y) and (x, y, false) represents the point at infinity in the direction of the line from the origin to (x, y). Problem solved!

After a while, you realize that this hack can be useful for more than just finding the intersection of lines. You discover that if you use a real number instead of a Boolean for the last coordinate, you can implement translations and rotations using matrix multiplication. So you replace true and false with 1 and 0, do your matrix calculation, then divide by the last coordinate so the result ends in 1 or 0 again. And this works really well.

This last coordinate is starting to act more like the other coordinates. You treat it as a peer when you multiply triples by a matrix, but only temporarily. You immediately normalize at the end to get back to more familiar territory.

Maybe it occurs to you after a while that you’re doing something analogous the introduction of imaginary numbers. At first the square root of −1 was seen as a hack that produced correct answers. It wasn’t really a number but something imagined to be a number as an aid to calculation. Over time mathematicians got more comfortable with these imaginary numbers and explored what would happen if they were treated as first class citizens. Maybe you should do the same with this third coordinate that started out as a hack.

This leads you to homogenous coordinates. A point in the extended plane you’ve created is represented by a triple (x, y, z) with the understanding that given a number λ ≠ 0, (x, y, z) and (λx, λy, λz) represent the same point. This is the natural extension of always dividing by the last coordinate, if it’s not zero, so that the triple always ends in 1. And you discover after a while that you need to add in the requirement that not all the coordinates can be zero at the same time.

You show this to a mathematician friend and he puts your construction in fancier language. He says you’re extended plane is ℝ³ minus the origin, modulo non-zero scalar multiplication. In other words, the points in your extended plane are equivalence classes of points in ℝ³.

Now if you think about this geometrically, your equivalence classes are lines through the origin because that’s what you get when you look at all scalar multiples of a given vector. What started out as the plane with extra points added is now the set of all lines though the origin. That’s one way to define the projective plane: a point in the projective plane corresponds to a line through the origin in ℝ³. Furthermore, a line in the projective plane corresponds to a plane through the origin in ℝ³.

Lines through the origin are determined by where they cross the unit sphere, so you could think of the projective plane as a sphere with one modification: because a line through the origin crosses the sphere in two antipodal points, we consider those two points in ℝ³ to be a single point in the projective plane.

Projective space and homogeneous coordinates seemed like arbitrary abstractions when I was a student because they were presented without any motivation. Much later I came to realize that they’re natural, almost inevitable. Exceptional cases and hand-wavy references to objects “at infinity” go away when moving to projective space.

My mathematics education was very top-down: abstractions first, specifics later (if ever). I was OK with that for a while, until I hit my abstraction tolerance sometime in grad school. Now I would advocate more of a bottom-up approach, motivating abstractions first rather than presenting them as a fait accompli.

The first time I saw the projective plane was probably in a topology class where someone said you could construct the plane by starting with a square and gluing opposite edges in a physically impossible way. This seemed like a gimmick, a way to construct a non-orientable manifold but not anything practical. Another construction is to say the projective plane is an ordinary sphere with antipodal points identified. I found that a little more satisfying, but it still unmotivated.

What I would have appreciated was someone saying that the projective plane was invented to make geometry more elegant by eliminating exceptional cases and making rigorous the idea of things “at infinity.” For example, geometric calculations often have to treat vertical lines specially, but vertical lines are not special in projective geometry.

You could start by saying we’re going to represent points in the plane not simply as (x, y) but as (x, y, 1) and use (x, y, 0) for the point at infinity in the direction (x, y). That may seem like a hack, but it’s certainly motivated. It’s exactly the sort of thing a graphics programmer would do. In fact, I imagine many programmers have done just that, independently bumping into projective geometry.

After having introduced this extra coordinate, it’s natural to ask what would it mean if the last coordinate were something other than 0 or 1. You’ll quickly run into this when you start doing calculations on these extended coordinates. You could have a rule that you always normalize by dividing by the last coordinate, if it’s not zero, and then you have essentially discovered homogeneous coordinates. (Update; I develop this idea in more detail in the next post.)

You’ll see something like the approach above in elliptic curve cryptography. Programmers wanting to implement encryption algorithms are thinking concretely in terms of (x, y) points, until they have to worry about a mysterious “point at infinity” and handle it correctly. Then homogenous coordinates appear as a tool for getting out of a bind.

***

I thought about titling this post something like “Dr. Strangelove, or: How I Learned to Stop Worrying and and Love the Projective Plane” but I wasn’t sure how well that would go over. I doubt many readers have seen the 1964 movie this is alluding to, but the trope “How I Learned to Stop Worrying and Love …” is more widely known than the movie itself.

Poles and polars are a little awkward in the plane because you have to pay attention to special cases. Poles and polars are relative to a conic section, and are defined/computed differently depending on whether you’re taking the dual with respect to an ellipse, parabola, or hyperbola. Also, the polar of the center of a conic section isn’t defined.

Projective space

If you move from the Euclidean plane to the projective plane, the exceptions go away, though it may not seem so if you’re talking about points at infinity or lines at infinity. If you fully commit to working in projective space, there aren’t any hand-wavy points or lines “at infinity.” There’s not even a distinction between ellipses, parabolas, and hyperbolas.

There’s no such thing as a free lunch, and the cost of this elegant unification is moving to a bigger geometric space with a different coordinate system. Instead of working in the Euclidean spaces R² or Rⁿ, we work in Pⁿ over a field F which could be R but doesn’t need to be [1].

The coordinates on Pⁿ are homogeneous coordinates, (n + 1)-tuples of field elements, not all equal to zero, with two (n + 1)-tuples representing the same point if they are proportional, i.e. one is a non-zero multiple of the other.

We can embed Rⁿ in Pⁿ by adding an extra coordinate on the end, set equal to 1. You could think of this extra coordinate as a switch, set to 1 for finite points and set to 0 for infinite points. But this distinction between finite and infinite points is an artifact of the embedding, not a property of Pⁿ: there are no special points in Pⁿ. A point that is “at infinity” in one embedding of Rⁿ in Pⁿ need not be in another embedding.

Poles and polars

Once you accept the need to work in homogeneous coordinates, everything becomes simple and consistent.

A quadric (a conic section when n = 2) is the set of points

{x : xᵀAx = 0}

where A is a non-singular (n + 1) by (n + 1) symmetric matrix over F.

The polar of a point p is the hyperplane

{x : pᵀAx = 0}

and the pole of a hyperplane

H = {x : uᵀx = 0}

is the point

p = A⁻¹ u.

Notice there’s no mention of “infinity” in this section. All the calculations take place in the field F with no points at infinity added.

[1] The only requirement is that the field F cannot have characteristic 2. So F could be the reals, the rationals, the complex numbers, etc. F could even be a finite field as long as the number of elements in F is not a power of 2.

Two days ago Axiom announced it had formalized the proof of CFSG in 43.1 million lines of Lean. If you click on the link for the accompanying paper, you’ll find that the title of the paper is The Unbalanced Group Theorem, not The Classification of Finite Simple Groups. Why is that?

The unbalanced group theorem (UGT) is a key component of the CFSG. In the course of their effort to formalize CFSG Axiom found counterexamples to an assertion that the 1986 proof of UGT depends on. The UGT, and the CFSG that depends on it, is correct, but the proof was flawed. Axiom formalized the entire CFSG but focused their paper on their new proof of the UGT.

***

What exactly does the UGT say? For that matter, what is a finite simple group?

A short post like this can only go into so much detail, but I’ll see what I can do.

A group represents some kind of symmetry. Groups can be built out of simple groups sorta like the way integers can be built out of primes. See more on the comparison between simple groups and prime numbers here.

The CFSG says that every finite simple group is cyclic, alternating, of Lie type, or sporadic. The UGT is a technical result used in proving that nothing is missing from this list of possibilities.

What does it mean for a group to be “unbalanced”? This depends on a few preliminary definitions.

• Define O(G) to be the largest normal subgroup of G with an odd number of elements.
• An element t in G is called an involution if it has order 2: t is not the identity but t² is.
• The centralizer of an element t of a group G, written C_G(t), is the set of elements of G that commute with t.

A group G is unbalanced if O(C_G(t)) is a not a subgroup of O(G) for some involution t.

The UGT is a classification theorem for unbalanced groups.

Related posts

• How big is the monster?
• Orders of finite simple groups
• Overlaps in the CFSG

You can often do better than exhaustive search for a particular problem, but can you always do better, even in the worst case? The Monien–Speckenmeyer branching algorithm, published in 1985, is more efficient than exhaustive search, but it still takes exponential time.

3-SAT

The Boolean satisfiability problem (SAT) asks whether a Boolean expression in conjunctive normal form (CNF) can be satisfied by some assignment of values to the variables. The k-SAT problem is the special case of SAT in which no clause contains more than k variables. The 2-SAT problem can be solved in polynomial time, but the case of the 3-SAT problem is unknown.

The 3-SAT problem is NP-complete, and so if there is a polynomial-time algorithm for solving 3-SAT, every NP problem, including the full SAT problem, can be solved in polynomial time, i.e. P = NP.

The Monien–Speckenmeyer algorithm mentioned above can solve a 3-SAT problem in

O( |F| φⁿ )

time, where |F| is the length of the input formula and φ is the golden ratio. Now φ < 2, and so this is better than exhaustive search, but the run time is still exponential in the number of variables n.

ETH

The exponential time hypothesis (ETH) claims that 3-SAT requires exponential time, which would imply P ≠ NP. Anthropic and OpenAI have both published proofs that ETH is false. The status of P = NP is still unknown: while 3-SAT does not take exponential time, it still takes more than polynomial time as far as anyone knows.

Yesterday Shiva Kintali posted A simplified proof of ETH is false. The abstract of the paper says

For every fixed ε > 0, we give a deterministic 3-SAT algorithm on n variables and m clauses using

C_ε(n + m + 1)^c_ε 2^εn

bit operations, refuting ETH. Our simplified exposition of OpenAI’s proof combines sparsification, bounded occurrences, spectral replacement, and rational interpolation.

Related posts

• Machine learning by satisfiability solving
• Formulating the eight queens problem as a SAT problem
• Lessons learned using the Z3 SAT/SMT solver

The use of poles and polars is that they preserve certain geometric information, and so they can transform one problem into a dual problem. This was illustrated in the first post in the series. Equations in spherical trigonometry have a buy-one-get-one-free property: applying an identity to the dual of a triangle gives another identity.

This post discussed how to define the pole of a line and the polar of a point with respect to a circle in the plane. The post stated that more generally you can do this in the projective plane. Since there’s no difference between conic sections in the projective plane, anything you can do for a circle you can do for an ellipse or hyperbola.

Given a point P, we can define its polar line geometrically or algebraically.

Algebraic approach

Given an ellipse with equation

x²/a² + y²/b² = 1

where a > b, the foci are at ± c where c = √(a² − b²).

For a point P = (x₀, y₀), its polar with respect to the ellipse is the line

(x₀/a²) x + (y₀/b²) y = 1.

Geometric approach

To find the polar of a point P, we start by inverting P in the ellipse. Draw any line through P that meets the ellipse at two points A and B. On that line there is exactly one point Q that divides AB harmonically with P:

QA/QB = PA/PB

with Q on the opposite side of AB from P if P is inside the ellipse, or between A and B if P is outside. The polar is the line through Q parallel to the tangent at R, where R is the point where the ray OP meets the ellipse.

Focus and directrix

Plane and projective geometry are very mature and so some of the terminology sounds quaint. One such term is the directrix of a conic section, explained here. The polar of a focus is a directrix, and the pole of a directrix is a focus.

Related posts

• Polar triangles and linear algebra
• Projective duality
• Posts on ellipses

X (née Twitter)

I have a several X accounts, one personal account (@JohnDCook) and several specialized accounts (@CompSciFact, @AlgebraFact, @DataSciFact, etc.). I announce new blog posts on the most relevant account.

RSS

You can subscribe to the blog via RSS and find out about each post as it’s published.

RSS was very popular before Google killed its RSS reader, but it still works just fine. I use RSS to subscribe to the blogs I read.

The hard part of using RSS is finding a reader you like. I use Inoreader. I’m sure an LLM could help you find an RSS reader for your preferences and help you get started using it.

Mathstodon & Bluesky

I announce my math-related posts on Mathstodon at mathstodon.xyz/@johndcook. I also use a service that repeats my Mathstodon posts to Bluesky at johndcook.mathstodon.xyz.ap.brid.gy.

I don’t know why, but more people have started following me on Mathstodon over the last couple weeks.

Substack

Some people like to get email notifications of posts. I used two or three services that sent out such emails and they all stopped working. I tried out Substack and it has worked smoothly ever since.

My Substack newsletter has evolved into a bit more than just blog post announcements. I give a little intro to each post and some additional info such as how a sequence of posts are related or ideas that occurred to me after writing the post.

LinkedIn

Once in a while I post something to LinkedIn. If you’d like to know more about my background, you can see my profile there.

Poles and polars on a sphere

Let’s start with a sphere S and a great circle G. Then G is the intersection of S with a plane through the center of S. The circle G has two poles, two points on opposite sides of S that are as far as possible (i.e. π/2 radians) from G. If you rotate the sphere so that G is the equator, the poles are the north and south pole.

Conversely, if you start with a point P on the sphere S, the polar of P is the great circle for which P is a pole. So if you think of P as the north pole, the polar of P is the equator. The term equator would have been more intuitive than polar, but the terminology was established a couple centuries ago.

In my opinion it would be clearer to call poles and polars both duals. The dual of a great circle is a point, and the dual of a point is a great circle.

Now let’s look at a spherical triangle ABC sides a, b, and c. The vertices of the polar triangle of ABC are the poles of the sides a, b, and c. This definition is essentially correct, but it needs a little refinement.

The pole A′ of the side a is one of the two poles of the great circle containing a, the one that that lies in the same hemisphere as A. Define B′ and C′ similarly, and the polar triangle is the spherical triangle with vertices A′B′C′.

Poles and polars in the plane

The terms pole and polar were coined for spherical geometry, then generalized to plane (projective) geometry. If you think of great circles as the lines of spherical geometry, then you can carry the idea of poles and polars over to plane geometry where the pole (dual) of a line is a point, and the polar (dual) of a point is a line.

However, in the plane you can’t define the pole of a line without more context. You have to start with a circle (or more generally a conic section) and define the pole of a line with respect to the circle and the define the polar of a point with respect to the same circle.

Given a circle S with center O, to find the polar of a point P ≠ O, let Q be the inversion of P in S, and let ℓ be the line through Q perpendicular to the line OP.

Conversely, the pole of a line ℓ with respect to a circle S is the inversion of Q in S where Q is the intersection of ℓ with OQ. Here we assume the line ℓ does not pass through the center of the circle O because otherwise O = Q and it doesn’t make sense to speak of the line OQ.

Projective geometry

The definitions above have a couple holes that can be filled in by extending the Euclidean plane to the projective plane.

We defined the pole of a line ℓ except when ℓ passes through the center of the circle. If ℓ passes through O then the pole of ℓ is the point at infinity in the direction of ℓ. Similarly, we defined the polar of all points except O. In projective geometry, we can define the polar of O to the be the line at infinity, the line containing all the points at infinity.

How do we know that polar triangles exist? There is a geometric construction that starts with a spherical triangle and constructs a unique new spherical triangle, and one can show that this new triangle has the angles and sides described in the previous post.

There is also a linear algebraic construction of polar triangles, and that’s the topic of this post. In a nutshell, take your sphere to be the unit sphere in 3D. Write the coordinates of each vertex as the columns of a matrix. Invert that matrix and normalize each row. Then the rows are the coordinates of the polar vertices.

This process is an involution: the polar of the polar of a triangle is the original triangle.

The following Python code illustrates the process described above. It begins with a triangle on the globe with vertices A, B, and C at Chicago, Quito, and Paris respectively. It computes the polar triangle, then computes the polar of that, and shows that the result is the original triangle.

import numpy as np

def latlon_to_cartesian(lat_deg, lon_deg):
    lat = np.radians(lat_deg)
    lon = np.radians(lon_deg)
    x = np.cos(lat) * np.cos(lon)
    y = np.cos(lat) * np.sin(lon)
    z = np.sin(lat)
    return np.array([x, y, z])

def cartesian_to_latlon(v):
    v = v / np.linalg.norm(v)
    lat = np.degrees(np.arcsin(np.clip(v[2], -1, 1)))
    lon = np.degrees(np.arctan2(v[1], v[0]))
    return lat, lon

def polar_triangle(M):
    """
    Polar triangle via matrix inversion.
    M: 3×3 matrix with columns = unit vectors of the original vertices.
    Returns 3×3 matrix whose columns are the polar unit vectors.
    """
    Minv = np.linalg.inv(M)
    # Normalize each row of the inverse (rows are parallel to the polar directions)
    polar_rows = Minv / np.linalg.norm(Minv, axis=1, keepdims=True)
    return polar_rows.T          # columns = polar vertices

# Original vertices (Chicago, Quito, Paris)
A = latlon_to_cartesian(41.85003, -87.65005)
B = latlon_to_cartesian(-0.22985, -78.52495)
C = latlon_to_cartesian(48.85341,  2.3488)

M = np.column_stack([A, B, C])
print("M (columns = original vertices):\n", M)
print("det(M) =", np.linalg.det(M))

# Polar triangle
M_prime = polar_triangle(M)
print("\nM' (columns = polar vertices):\n", M_prime)

print("\nPolar geographic coordinates (lat, lon):")
for name, col in zip(["A'", "B'", "C'"], range(3)):
    print(name, cartesian_to_latlon(M_prime[:, col]))

# Polar of the polar
M_double = polar_triangle(M_prime)
print("\nPolar-of-polar matrix:\n", M_double)
print("max |difference from original M| =",
      np.max(np.abs(M_double - M)))

cos(c) = cos(a) cos(b) + sin(a) sin(b) cos(C).

But that’s just one of two laws of cosines on a sphere. The equation above is the law of cosines for sides. The law of cosines for angles is typographically very similar, just inverting the case of the letters used as arguments.

cos(C) = cos(A) cos(B) + sin(A) sin(B) cos(c).

Incidentally, the law of cosines for sides shows how the sides of a spherical triangle determine the angles. The law of cosines for angles shows how, unlike in the case of plane geometry, angles determine the sides.

Two kinds of angles

Let’s back up and say what the letters refer to. As is conventional in plane geometry, the sides of a triangle are a, b, and c, and the angles are A, B, and C, with a being the side opposite the angle A, and similarly for the other letters.

However, unlike plane geometry, the sides are also angles, but of a different sort. The sides a, b, and c are central angles, and the “angles” A, B, and C are dihedral angles.

The sides are arcs of a great circle. The side a, for example, is a portion of a great circle, running between the vertices at B and C [1]. Think of a plane that contains the center of the sphere O and the vertices B and C. The length of a is the angle at O.

The angles A, B, and C are the angles at which great circles meet. In the formalism of differential geometry, these angles exist in the tangent plane at the vertices. These angles are intrinsic, measured along the (tangent plane of) the surface of the sphere. The central angles are extrinsic, measured in a plane that cuts through the sphere to its center.

Polar triangles

Now because sides are angles and vertices are angles, we can interchange the two kinds of angles to form the polar triangle of the original triangle. This is a new triangle whose central angles are the complements of the original dihedral angles, and whose dihedral angles are the complements of the original central angles. In symbols,

a′ = π − A
b′ = π − B
c′ = π − C
A′ = π − a
B′ = π − b
C′ = π − c

Now we return to the laws of cosines at the top of the post: the law of cosines for angles is the law of cosines for sides applied to the polar triangle. Every equation in spherical trigonometry has a polar counterpart.

[1] There’s some overloaded terminology here, just as in plane geometry. The symbol a is used to denote a side of a triangle and also the length of that side. The symbol A is used to denote both a vertex and the dihedral angle at that vertex.

I got an error message that said

error: The script contains multiple PEP 723 metadata blocks

I searched on what that means, then took out the blank line in my header

#!/usr/bin/env -S uv run --script

# /// script
# dependencies = ["pyperclip"]
# ///

but I still got the same error message.

The script in question copies miscellaneous snippets of text to the clipboard for me. One of those snippets is the header block that uv requires. The script contains the header block marker # ///, and that was the source of the problem.

According to Grok

The PEP 723 parser is purely textual (it uses a regex that scans the whole file). It does not understand Python syntax, so the # /// sequences inside your triple-quoted string are treated as a second metadata block.

It suggested changing my quoted string to use # / / / and then take out the extra spaces:

"""#!/usr/bin/env -S uv run --script
# / / / script
# dependencies = ["numpy", "matplotlib"]
# / / /
import numpy as np
import matplotlib.pyplot as plt
""".replace("# / / /", "# ///")

This is a dirty hack, but it works.

As I mentioned in an earlier post, eMudrha was using the numbers 4, 56, 115, 155, 156, 230, and 237 as secret keys. I haven’t seen details of how this happened, but in this post I’ll give a plausible account of how it might have happened, what someone could have done to produce those results. I’m not trying to do forensic analysis on this specific incident, just exploring what someone might do.

eMudrha was using the NIST elliptic curve P-384, and a secret key should be a random number chosen between 1 and 2³⁸⁴. That upper bound isn’t exactly correct, but it’s close. See this post if you want to know the exact number.

Someone might have chosen numbers up to 384 rather than 2³⁸⁴ out of ignorance. Or they might done so by a typo. Maybe they generated a random value that might have been larger than 2³⁸⁴ and then intended to reduce the number mod 2³⁸⁴, but instead of typing

% 2**384

they typed

% 384

It seems more likely, however, that somehow someone took one byte of a random value because all the keys are less than 2⁸ = 256.

The probability of choosing seven numbers from 1 to 384 and all being less than or equal to 237 is around 0.034. But the same probability for numbers chosen between 1 and 256 is about 0.60.

y² = x³ + ax + b

with x and y in F. Typically in cryptography the field F is the integers mod p where p is a very large prime number.

The number of points on E is roughly the number of elements in F. So for a curve over the integers mod p, the curve has roughly p points.

The next section will give an intuitive argument for why the number of points on E should be roughly the number of elements in F. Then the next section will give a rigorous bound. Then after that we’ll work through an example.

Hand-wavy estimate

For a prime p, half the non-zero integers mod p have a square root and half do not. The ones that do have a square root have two square roots. For example, look at the integers mod 7. The numbers 1, 2, and 4 have square roots but the numbers 3, 5, and 6 do not. Here’s a little bit of Python to verify this.

>>> [x**2 % 7 for x in range(1,7)]
[1, 4, 2, 2, 4, 1]

Now if we wanted to count the number of solutions to

y² = x (mod p)

we’d find it equals p. That’s because (0, 0) is a point on the curve, and for (p − 1)/2 values of x there are two values of y, and for the remaining values of x there are no values of y.

To put it another way, if we pick a value of x at random, it will have two square roots or no square roots with roughly equal probability.

Now suppose we pick an x at random and compute x³ + ax + b. We might guess that this process scatters x values in an unbiased way, being no more likely to produce a square than a non-square. Our guess turns out to be approximately correct, though there may be a small bias in favor of squares or non-squares.

Precise bound

Hasse’s theorem gives a precise bound on the number of points on an elliptic curve E. It says

#E = p + 1 − t

where

|t| ≤ 2√p.

So if p is on the order of 2ⁿ, the number of points on E is also on the order of 2ⁿ because √p is far smaller than p. That’s all you need to know at a high level. The rest of this post will look at a particular example in full detail.

Detailed example

The NIST curve P-384 has been in the news lately. For this curve, the based field is integers modulo a 384-bit prime p and so the number of points on the curve is also 384-bit number. Specifically

p = 2³⁸⁴ − 2¹²⁸ − 2⁹⁶ + 2³² − 1,

and so we know a priori that the number of points on the curve equals 2³⁸⁴ plus or minus a factor less than 2¹⁹³.

The number of points on the elliptic curve P-384 is known to be

 n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643

See NIST SP 800-186, §3.2.1.4⁠.

We can calculate t at a Python REPL.

>>> n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
>>>  p = 2**384 - 2**128 - 2**96 + 2**32 - 1
>>> t = p + 1 - n
>>> t
1388124618062372383606759648309780106643088307173319169677

The fact that t is positive means the number of points n on our curve is slightly less than p. Here “slightly” is relative. The value of p − n is a huge number, but it’s small relative to p.

We can verify that |t| is less than our a priori bound of 2√p.

>>> from math import sqrt
>>> t/(2*sqrt(p))
0.11057050503394951

So the actual value of t is about nine times smaller than its bound.

My post a few days ago was about the possibility that the NSA had added a backdoor to the NIST curves. Anthropic researchers showed that this wasn’t the case. The NSA had not been able to defend how the curve seeds were chosen because they forgot, but researchers from Anthropic were able to reverse engineer the source of the seeds.

So apparently the NIST curves do not have a backdoor, but as with all encryption, the Achilles heel is human error. eMudrha was using the NIST curve P-384  with extremely small keys: 4, 56, 115, 155, 156, 230, and 237. To understand why this is a problem, I’ll briefly describe how elliptic curve cryptography works.

P-384 is an elliptic curve designed by NIST, with input from the NSA, for use in cryptography. The curve has on the order of 2³⁸⁴ points because the base field is the integers mod

p = 2³⁸⁴ − 2¹²⁸ − 2⁹⁶ + 2³² − 1,

a 384-bit prime number. Given a basepoint b on the curve and an exponent e, it is practically impossible to recover e from b^e. That’s the discrete logarithm problem [1], the basis for the security of elliptic curve cryptography. If and when cryptographically relevant quantum computers arrive, the discrete logarithm problem will be solvable and elliptic curve cryptography will be broken.

Until the advent of quantum computing, elliptic curve cryptography is presumably safe, unless someone does something negligent, such as using a tiny value of e like 4.

If e is chosen at random from a group with on the order of 2³⁸⁴ elements, you cannot recover e from b^e without brute force. But apparently someone said

Let’s see. Is e = 1? Is it 2? Is it 3? Is it 4? Why yes: e = 4.

Ordinarily this would be hopeless. You can’t just try 2³⁸⁴ exponents. But someone thought to test whether the keys were horrifically bad, and they were right.

[1] The exponentiation here is not over the integers, or over the integers mod p. It’s over the group structure of the elliptic curve, and that is what makes it hard to compute the discrete logarithm.

There is a time for everything,
and a season for every activity under the heavens:

a time to be born and a time to die,
a time to plant and a time to uproot,
a time to kill and a time to heal,
a time to tear down and a time to build,
a time to weep and a time to laugh,
a time to mourn and a time to dance,
a time to scatter stones and a time to gather them,
a time to embrace and a time to refrain from embracing,
a time to search and a time to give up,
a time to keep and a time to throw away,
a time to tear and a time to mend,
a time to be silent and a time to speak,
a time to love and a time to hate,
a time for war and a time for peace.

The poem has a great deal of symmetry, from birth and death to war and peace. It has seven couplets, and the number seven in the Bible is symbolic of perfection.

There is a repeated pattern of groups of four words: a time for X, a time for Y. The rhythm reminds me of Beethoven’s fifth symphony, especially the third movement [1].

Higgins points out that there’s something odd in the middle couplet:

a time to scatter stones and a time to gather them,
a time to embrace and a time to refrain from embracing,

It breaks the rhythm, at least in English translation, and presumably in the original language. The poem goes from intransitive adjectival infinitives —to plant, to uproot, etc.—to transitive—to gather stones. Also, the two parts of the couplet do not obviously fit together. There’s a similarity between birth and planting, between killing and tearing down, etc. But what’s the connection between casting stones and embracing?

Higgins explains that this deliberate symmetry breaking fits the theme of the Ecclesiastes as a whole. There is order to the world, and yet we don’t have it all figured out. Even when everything mostly makes sense, there’s something we don’t understand, like the middle couplet.

[1] This has been called the fate motif. There is an apocryphal story that Beethoven described it as such to his secretary and biographer Anton Schindler. Regardless of whether the story is true, the name stuck. Here’s the particular part I had in mind.

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 for all N, t(3) = 1 and t(4) = 2. The t(N) are given in OEIS sequence A034258.

Last Thursday an article came out proving an asymptotic estimate for t(N). You can find a preprint on arXiv.

An upper bound on t(N) would be the Nth root of N! because that would correspond to splitting N! into N factors of equal size. But the Nth root of N! will not be an integer for N > 1, so the bound would not be tight.

If we apply Stirling’s approximation for factorial we get

t(N) / N ≤ 1/e + O(log(N) / N).

It was conjectured that for large N

t(N) / N ∼ 1/e − c₀ / log(N)

and the new paper proves

t(N) / N ∼ 1/e − c₀ / log(N) + O(1 / log^{1 + c} N).

.

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)+

This solution could either be very efficient or very inefficient, depending on the inner workings of the software used to match the regular expression.

A DFA (deterministic finite automata) regular expression engine would find a match, or report failure, linear time, i.e. the execution time would be proportional to the length of the string being matched. An engine that uses backtracking (informally called an “NFA engine”) could take exponential time. (The classical Thompson simulation of an NFA itself runs in O(mn) time; the exponential behavior comes from the backtracking search strategy.)

The root of the problem is the ambiguity in dividing words into single letters or pairs of letters.

Many two-letter chemical symbols are made of letters that are themselves chemical symbols. For example, the symbol for cobalt, Co, consists of the symbols for carbon, C, and oxygen, O. A traditional NFA regular expression engine uses backtracking and could take exponentially long to test whether the word

cococo…j

matches a regular expression for concatenated chemical symbols. If there are n copies of co, the engine would try all 2ⁿ possibilities of treating each pair as either co (cobalt) or c o (carbon oxygen).

A DFA regular expression engine always runs in O(n) time, while a traditional backtracking engine can take exponential time. So why ever use a backtracking engine? Because such an engine can match more advanced patterns such as Perl regular expressions (which are not “regular” expressions in the original meaning of the term). Newer engines have added safeguards to eliminate or at least reduce the chance of running into catastrophic backtracking.

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 of elliptic curve cryptography depends on the difficult of solving the discrete logarithm problem. In the context of elliptic curve arithmetic, the analog of exponentiation is easy but the analog of taking logarithms is hard.

In general it’s not practical to compute discrete logarithms over large elliptic curves. But it could be easy for someone with inside information to compute discrete logarithms if something about the curve was not “general.”

Specifically, the NIST curves have the form

y² = x³ − 3x + b (mod p)

for various values of p [2], and the suspicion regards the choice of b. For nearly all values of b encryption over the elliptic curve should be secure, as far as we know, but in principle someone could engineer values of b to weaken the encryption.

So where did the b‘s come from? Were they chosen in good faith?

Concern over the choice of seeds, the b‘s, grew following the Snowden revelations. Daniel J. Bernstein emailed Jerry Solinas of the NSA on September 6, 2014 asking where the seeds had come from. Solinas replied in subsequent emails. He said the seeds were generated by hashing the ASCII representation of a humorous English message, but he could no longer remember the exact message or the precise hashing procedure.

On October 5, 2023 Philippo Valsorda announced a bounty for reverse engineering the origin of the NIST elliptic curve seeds. Two days ago researchers from Anthropic claimed the bounty. Valsorda verified the results and awarded the prize. It turns out Solinas found the curve seeds in good faith, but his memory had faded over the years since the curves were published. We now know he used a date, not a phrase, as part of the process of constructing the seeds.

The NIST curves have some nice properties, such as enabling some clever tricks for arithmetic in their base fields. But adoption of the curves has been held back over suspicion regarding their origin. Now the curves have been exonerated. As Valdorda notes

… this nicely completes the “rehabilitation arc” of NIST elliptic curve cryptography, which I would now personally recommend over Curve25519/Ed25519/X25519. Just in time for them to be retired in favor of post-quantum signatures.

Related posts

• What is an elliptic curve?
• Monero’s elliptic curve
• Lewis Carroll and zero knowledge proofs

[1] This does not imply that LLMs are necessarily a threat to encryption. The search for the NIST seeds required a lot of brute force. Some cleverness was required in order to come up with possibilities to check by brute force, but even that is sorta brute force at a higher level of abstraction. There has been speculation that labs are looking for weaknesses in cryptographic primitives and protocols, but that’s a different matter than searching for seeds.

[2] The curves P-192, P-224, P-256, P-384, and P-521 are built over the field of integers mod p, where the number of bits in p corresponds to the number in the name. The P-192 curve, for example, has as its base field the integers mod 2¹⁹² − 2⁶⁴ − 1, a 192-bit prime.