Taking a Problem Down a Peg

Composite crop of src1, src2

Joshua Greene and Andrew Lobb proved last month that every smooth Jordan curve in the plane and real , there are four points on the curve that form a rectangle with sides of ratio .

Today we explain how this result relates to Otto Toeplitz’s famous “square peg conjecture,” which is the case when the curve need not be smooth.

We noticed this via an article last Thursday by Kevin Hartnett for Quanta. Hartnett describes this research advance as a product of the pandemic inducing them to take time for deeper reflection on fundamental problems. We wonder how much is bubbling on hard problems in our own field—this is one reason for our last post’s interest in (good kinds of) “gossip.” He also gives great diagrams for the geometrical intuition.

We will portray this advance instead along lines of things we’ve said recently about how to attack hard problems by seeking and solving simpler ones or special cases as stepping stones. Dick wrote a post two years ago on the original Toeplitz problem, which this work still leaves open. That post focused on ways general Jordan curves can be nasty. This one needs an extra niceness condition but proves a stronger result for all . How much can progress on “nice” inform problems with “nasty”? That kind of question comes up in complexity theory all the time.

Pegging Rectangles

A Jordan curve is the image of a continuous 1-1 map from the circle to the plane. The condition of being 1-1 prevents the image from intersecting itself, so it is a single closed loop. By the Jordan curve theorem, the loop always partitions the rest of the plane into two connected regions, exactly one of which is bounded. Amazingly, a Jordan curve can have positive Lebesgue measure, yet cannot fill all of . Such curves can, however, approach the kind of space-filling curves defined by Giuseppe Peano, and thus have any Lebesgue density less than , as was noted also by William Osgood in his 1903 paper.

The Toeplitz conjecture is that every Jordan curve has four points that form a square. As noted in Dick’s post, the positive-area case is actually an easy yes-case. Nasty cases are where the curve is nowhere-differentiable with zero area. Thus far, the problem has been answered yes only in the presence of some uniformity condition that limits the local nastiness of the curve. The simplest one is for the curve to be smooth in that has a continuous first derivative. Here is a smooth curve that is not convex, so that the square need not be “inside” the curve:

This diagram is from Benjamin Matchske’s wonderful recent survey of the peg problem in the AMS Notices. Four months ago we’d have said it looks like a thin heart or fat boomerang. Now it looks to us like a face mask.

As the survey notes, it is easy to show that every Jordan curve has some rectangle. The rectangle problem is to show that rectangles of every aspect ratio can be pegged to the curve. There are two main reasons the square and rectangle problems are hard and harder:

1. Although any Jordan curve can be written as a limit of nice ones, the squares in the nice ones can degenerate to a single point in the limit.

2. Even for nice curves, a parity property that holds for squares can fail for rectangles.

The property in the second point enables arguments of the kind: for generic curves the number of squares is odd, therefore it is nonzero. This then carries over to sufficiently nice curves in the generic closure. The failure of this property for rectangles is a main reason the results by Greene and Lobb are new.

The Paper

The new paper is written tersely at a high level, and we must confess not being able to catch all details in compressed time. But we can highlight some aspects of the argument. First, as we have said, it exemplifies:

• Solve a Simpler Problem.

This is however coupled with a second aspect:

• Bring Up the Reserves.

It may be that the rectangle conjecture is not only true but “equally true” in the sense that the fundamental reason applies equally well to the case of rectangles. The parity argument that works for cases involving squares may be a crutch that misses the deepest explanations. Promoting arguments that avoid this crutch may marshal resources needed to make a breakthrough on the main problem for completely general Jordan curves.

This runs somewhat counter to what we have said about versus proof attempts recently. The reason for believed by most is that problems like SAT require exponential time, not just super-polynomial time. Yet no one knows even a super-linear lower bound, apart from barely-superlinear bounds that exploit grainy aspects of the multitape Turing machine model and apply only to it. Nor is any super-linear lower bound known on Boolean circuit size. Maybe it is a viable strategy also to “bring up reserves” by finding restricted cases where (conditional) exponential lower bounds can be proven, as well as to explore contingencies like SETH, as we covered here. But both of use have always felt that the super-linear frontier holds the buried keys to further progress.

The Greene-Lobb proof has two aspects that may also resonate in complexity:

• Blow Up the Objects.

The article in Quanta has great diagrams illustrating how the set of pairs of points on the curve corresponds to a Möbius strip in a related space. Cole Hugelmeyer, a graduate student at Princeton, proved last year how to get rectangles covering at least one-third of possible values by embedding the Möbius strips in a four-dimensional space. Intersections between a strip and a rotated copy yield rectangles on the original Jordan curve.

That led Greene and Lobb to consider larger objects with properties like pairs of Möbius strips in the larger space. The Klein bottle is the natural next thing to consider and led to a feature of their proof that made the desired conclusion pop out:

• Identify and Rule Out Obstructions.

The clever point pivots on the fact that a Klein bottle cannot be smoothly embedded into the complex plane as a Lagrangian submanifold. The proof shows that for any prescribed aspect ratio one can construct a mapping that almost succeeds in embedding such a Klein bottle. The fact that it must fail means that the image must yield a point of intersection witnessing the failure. The presence of this point then yields the construction of four other points on the Jordan curve that form the vertices of the needed rectangle.

We have briefly mentioned how the concept of obstructions is integral to the Geometric Complexity Theory attack on . Closer to home, however, is how László Babai's graph isomorphism algorithm and proof works by identifying a subclass of graphs called Johnson graphs as obstructions to a simpler algorithm, as we highlighted here.

Open Problems

Can you find more lessons from the new advance on the Toeplitz problem? Dick and I have considered ideas of blowing up from languages to pairs of languages (and making reductions between problems the fundamental units of analysis) but this has not gone beyond dreamwork.