Skip to content

The Inscribed Square Problem

October 21, 2018


A remark on an open problem with an application of the Lebesgue Density Theorem

[ Toeplitz ]

Otto Toeplitz was a mathematician who made key contributions to functional analysis. He is famous for many things, including a kind of matrix named after him.

Today we discuss one of his conjectures that remains open.

Over a century ago, in 1911 to be exact, Toeplitz proposed the inscribed square problem (ISP):

Does every Jordan curve contain an inscribed square?

More precisely, if {J} is a Jordan curve, then we want four distinct points on {J} so that they form a square. The dotted curve in Wikipedia’s figure has four squares.

What Are Jordan Curves?

The notion of a curve, now called a Jordan curve, is named for Camille Jordan. Sometimes called a plane simple closed curve, a Jordan curve is a non-self-intersecting continuous loop in the plane. More precisely it is the image {J} of an injective continuous map of a circle into the plane. The famous Jordan curve theorem says:

Every Jordan curve divides the plane into two connected regions—one bounded and one unbounded.

This statement is one of those obvious ones that is actually hard to prove. The reason it is actually hard to prove is critical to our discussion of the ISP. The reason is that Jordan curves can be quite nasty. Here are two key issues with Jordan curves:

  1. There are Jordan curves {J} so that the length of the curve is infinite.

  2. There are Jordan curves {J} so that the area of the curve is positive.

Thus (1) says that a Jordan curve can be infinitely long. This is already a problem with our notion that a curve is just something that you draw with a pen. Or if you draw the curve with a pen, then it takes a very long time to finish drawing the curve. Such curves are strange, but they are perfectly fine examples of Jordan curves. Next (2) says that a curve can have positive area or measure. Curves with positive area are now called Osgood curves after William Osgood who found the first example of such a curve. Intuitively, such a curve hardly seems to be a “curve”, but they are nevertheless.

Even “nice” Jordan curves with finite length can be nasty.

Not very intuitive to me. Even the above which is not one of the examples (1,2) is nasty looking. By the way Jordan found a cool proof of the following:

If {J} is a Jordan curve with finite length, then {J} has zero area.

See if you can figure this out—we supply a proof at the end of this post.

ISP On Nice Jordan Curves

So far the ISP is still open for arbitrary Jordan curves. It has been proved for convex curves and sufficiently smooth curves, but the question remains open in general. Even for polygonal curves—curves that come from polygons that are not self intersecting—it is non trivial. See the references below for some of the main results.

ISP On Nasty Jordan Curves

Curiously, if a Jordan curve {J} is nasty, then the ISP is true. That is:

Theorem: Suppose that a Jordan curve {J} has positive measure. Then there is an inscribed square that lies on {J}. Thus in this case the ISP is true.

The punch line here is that “bad” curves are well behaved with respect to having inscribed squares. The proof is based on a standard probabilistic argument. We will need the Lebesgue’s density theorem. Suppose that {A} is a measurable subset of the plane. Now consider some small enough disk around a random point {x} in the plane. Then either almost all of the disk is in {A} or almost none. This “0-1” type law is a bit surprising, but it is quite useful. In particular, if {A} has positive measure, then almost all points {x} in {A} have the density-1 property. Here is a nice comment on this from Terry Tao’s blog:

In other words, almost all the points {x} of {A} are points of density of {A}, which roughly speaking means that as one passes to finer and finer scales, the immediate vicinity of {x} becomes increasingly saturated with {A}. (Points of density are like robust versions of interior points, thus the Lebesgue density theorem is an assertion that measurable sets are almost like open sets. This is Littlewood’s first principle.)

Now let’s show that ISP is true for Jordan curves with positive measure.

Proof: Suppose that {J} is a Jordan curve that has positive measure. Then by the Lebesgue’s density theorem there is an open disk {D} so that {S=D \cap J} has measure almost {1}. We then argue that if we randomly select a square in the set {D} it has almost probability {1} to be inscribed on {J}. This follows by a standard union bound. This then shows that there must be a square that is inscribed on {J} and that ISP is true for this curve. \Box

I am sure that this is well known to experts, but I include it here to highlight the result. I find it interesting that we can turn the “pathological” properties of a curve to our advantage. When given lemons, make lemonade. This is of course a recurrent theme in complexity theory: For example, we know that random boolean functions have high complexity.

References

Here are some references to work on ISP.

{\bullet } “Differentiability of Lipschitz functions, structure of null sets, and other problems”
by Giovanni Alberti, Marianna Csorynei, David Preiss

{\bullet } “Splitting Loops And Necklaces: Variants Of The Square Peg Problem”
by Jai Aslam, Shujian Chen, Florian Frick, Sam Saloff

{\bullet } “Squares and other polygons inscribed in curves”
by Elizabeth Denne

{\bullet } “Transversality in Configuration Spaces and the `Square Peg’ Theorem”
by Jason Cantarella, Elizabeth Denney, and John McCleary

{\bullet } “Every smooth Jordan curve has an inscribed rectangle with aspect ratio equal to {\sqrt{3}}
by Cole Hugelmeyer

{\bullet } “A Combinatorial Approach to the Inscribed Square Problem”
by Elizabeth Kelley

{\bullet } “Squares on Curves”
by Dongryul Kim

{\bullet } “A survey on the Square Peg Problem”
by Benjamin Matschke

{\bullet } “Figures Inscribed in Curves A short tour of an old problem”
by Mark Nielsen

{\bullet } “The Discrete Square Peg Problem”
by Igor Pak

{\bullet } “On The Unfolding Of Simple Closed Curves”
by John Pardon

{\bullet }“On The Number Of Inscribed Squares In A Simple Closed Curve In The Plane”
by Strashimir Popvassilev

{\bullet } “The Jordan curve theorem is non-trivial”
by Fiona Rossa and William Ross

{\bullet } “Two discrete versions of the Inscribed Square Conjecture and some related problems”
by Feliu Sagols and Raul Marin

{\bullet } “A Trichotomy for Rectangles Inscribed in Jordan Loops”
by Richard Schwartz

{\bullet } “An Integration Approach To The Toeplitz Square Peg Problem”
by Terence Tao.

Open Problems

Of course the key problem is the full conjecture, which remains open. But a possible approachable problem seems to be this: If a Jordan curve {J} has infinite length, can we show that conjecture is true?

Jordan’s proof of his claim: Suppose {J} is a curve that has finite length {L}. Partition the plane into a grid of side length {L/n} for some {n} to be selected in a moment. Also divide the curve {J} into {n} parts of length {L/n}. This is possible since {J} has finite length. The key is: each part of the curve hits at most {4} squares of the grid. Thus the area of the curve is easily seen to be bounded by

\displaystyle  4n\cdot \frac{L}{n} \cdot \frac{L}{n},

but this tends to {0} as {n} goes to infinity. Done.


[three->four squares in intro]

Advertisements
9 Comments leave one →
  1. martininmelb permalink
    October 21, 2018 9:27 pm

    > The dotted curve in Wikipedia’s figure has three squares.

    Am I missing something? There appear to be four squares.

    • October 21, 2018 9:35 pm

      Ah, thanks! That got by both of us.

      • eppstein permalink
        October 22, 2018 12:45 am

        Isn’t there a theorem that a nice curve has an odd number of squares? So although four squares are shown in the figure, there must be at least one more somewhere (unless one of the ones shown has even multiplicity, which seems unlikely).

  2. October 22, 2018 1:48 pm

    FYI: The Inscribed Square Problem is closed, and it is confirmed as true! There’s a solution or proof at link below.

    Relevant Reference Link:

    https://www.researchgate.net/post/What_is_the_solution_to_the_inscribed_square_problem_Toeplitz_square_peg_problem

  3. October 25, 2018 6:42 am

    See my proof of P = NP in

    https://www.academia.edu/37469408/P_versus_NP

    Thanks in advance…

    • fnord permalink
      October 31, 2018 5:22 pm

      I skimmed your paper, and after eliminating fluff, it seems your central thesis is that taking square roots modulo something with a known factorization is both in P and NP-Complete.

      It is highly unlikely anything factoring-related is NP-Complete, so I am very skeptical.

      • November 1, 2018 10:33 am

        Factoring is not necessary since is assumed the prime factorization of the number is given in the input 😉

    • Luke permalink
      November 4, 2018 2:29 am

      Lemma 10 is wrong. The length of b is log b = n_1 log p_1 + n_2 log p_2 + … The number of factors (as you correctly stated) is (n_1 + 1)(n_2 + 1)… The latter can be exponentially bigger than the former.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s