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.2026-10-26 03:45:05
The previous two posts have been about polar triangles. The first used a polar triangle to derive a theorem, and the second showed how to compute polars using linear algebra. But what exactly is a polar triangle and why is it called that?
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′.
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.
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.
The post Poles and polars first appeared on John D. Cook.2026-10-25 09:01:55
The previous post defined the polar triangle of a spherical triangle in terms of its sides and angles, but it doesn’t construct the triangle. It only specifies one of a family of triangles located anywhere on the sphere.
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)))
The post Computing polar triangles with linear algebra first appeared on John D. Cook.
2026-10-25 08:28:20
I’ve written before about the law of cosines on a sphere:
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.
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.
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.
The post Duality in spherical trigonometry first appeared on John D. Cook.
