2026-11-02 22:44:02
In my newsletter I give an introduction to the latest few posts and occasionally give some additional commentary. In my latest newsletter I wrote
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.
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.
The post Making peace with the projective plane first appeared on John D. Cook.2026-11-02 04:29:54
I wrote several posts on poles and polars a few days ago. First, I wrote about the dual of a spherical triangle, called the polar triangle. Then I wrote about poles and polars in plane geometry and briefly mentioned the extension to projective geometry.
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.
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 Rn, we work in Pn over a field F which could be R but doesn’t need to be [1].
The coordinates on Pn 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 Rn in Pn 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 Pn: there are no special points in Pn. A point that is “at infinity” in one embedding of Rn in Pn need not be in another embedding.
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−1u.
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.
The post A unified view of poles and polars first appeared on John D. Cook.2026-10-28 19:51:51
The classification of finite simple groups (CFSG) has been called the biggest theorem in mathematics. It is big, not necessarily in terms of its importance, but in the sense that its proof developed over the course of decades and thousands of pages of journal articles.
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.
A group G is unbalanced if O(CG(t)) is a not a subgroup of O(G) for some involution t.
The UGT is a classification theorem for unbalanced groups.
2026-10-27 20:13:21
If you have an expression in n Boolean variables, how long does it take to find out whether some assignment of values to the variables makes the expression true? There is an obvious upper bound: you can find out in 2n steps by exhaustive search, trying all possible ways of setting each variable to true or false.
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.
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| φn )
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.
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.
2026-10-27 02:39:32
The previous three post have been part of a series on geometric duality. The traditional but somewhat mysterious terminology is the pole of a line and the polar of a point. As explained here, the terminology was first coined in the context of spherical geometry where the term “pole” makes sense. It was then extended to the plane where the meaning is less obvious.
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.
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 = (x0, y0), its polar with respect to the ellipse is the line
(x0/a²) x + (y0/b²) y = 1.
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.
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.
2026-10-26 20:04:54
This blog is the main place I write, but I also use other platforms, either to write new content or to announce blog posts.
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.
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.
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.
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.
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.
The post Where else to find me first appeared on John D. Cook.
