Advances on an Erdős problem on convex boundaries

Among his around 1525 papers, Paul Erdős considered On sets of distances of n points 1 as his most important contribution to discrete geometry. There, he stated:

On the boundary of every convex body, there exists a point P such that every circle with center P intersects that boundary in at most 2 points.

Credit: Wikimedia Commons
Credit: Wikimedia Commons

(Note that throughout this post all the objects considered will be in the plane). This statement can be rephrased as:

On the boundary of every planar convex body, there exists a point P such that there are no more than 2 points equidistant to P on that boundary.

However, the conjecture turned out to be false. An easy counterexample is an acute triangle, for which any point on the boundary is the center of a circle intersecting that boundary in 4 points. The following figure shows this for a particular point, but you can check the points you want at this interactive GeoGebra construction.

Credit: David Orden
Credit: David Orden

In fact, it turns out that any point on the boundary of a regular (2k+1)-gon is the center of a circle intersecting that boundary in 4 points. Naturally, a question arises:

Is this Erdős’s conjecture true when the upper bound 2 is replaced by 4?

Imre Bárány and Edgardo Roldán-Pensado give a negative answer to this question, constructing a convex body such that the smallest number for which Erdős’s statement holds is 6, i.e., such that for any point P on its boundary there is a circle with center P intersecting that boundary in 6 points.

The convex body they construct is a 15-gon. They consider the points A1= (1000,0) , A2= (906,114) , A3= (645,359) , and A4= (-498,871) , together with the points B_i and C_i , for i\in\{1,2,3,4\} , obtained by rotating the A_i ‘s around the origin by an angle of 2\pi/3 and of 4\pi/3, respectively. The 12-gon defined by these points looks like this

Credit: Bárány and Roldán-Pensado (2013)
Credit: Bárány and Roldán-Pensado (2013)

and it can be checked at this interactive GeoGebra construction. The union of the shaded regions in the figure contains the polygonal chain A_4B_1B_2B_3 and, using a technical lemma, this allows to prove that for any point P in some neighborhood V of the polygonal chain A_4B_1B_2B_3 there is a circle with center P that intersects the polygonal chain C_1C_2C_3C_4 in at least 6 points.

Another technical lemma, together with the fact of the angle \angle A_3A_4B_1 being acute, implies the existence of a suitable point A_5 . By rotational symmetry, there also exist suitable points B_5 and C_5 , such that A_i, B_i, C_i for i\in\{1,2,3,4,5\} form the claimed 15-gon.

In view of this construction, Bárány and Roldán-Pensado 2 conjecture that

On the boundary of every convex body, there exists a point P such that every circle with center P intersects that boundary in at most 6 points (i.e., such that there are no more than 6 points equidistant to P on that boundary).

It is interesting to note that, both the original Erdős’s conjecture and this updated one, state the existence of a universal upper bound for the number of intersections (or equidistant points), independent of the convex body considered.

Although the existence of such a universal constant remains open, Bárány and Roldán-Pensado throw some light on the problem. They prove that for every convex body there is a finite upper bound as in the statement. More formally:

For every convex body K , there is an N(K) being the smallest natural number for which there exists a point P on the boundary of K such that every circle with center P intersects the boundary of K in at most N(K) points (i.e., such that there are no more than N(K) points equidistant to P on that boundary).

This finiteness result is actually a consequence of a stronger one. For a fixed convex body K , one can define the set \Gamma of pairs (Q,\ell) in which Q is a point on the boundary of the convex body and \ell is a normal to that boundary at Q . See the following figure.

Credit: David Orden
Credit: David Orden

Note that there might be several pairs for which the normals intersect at a common point P on the boundary of the convex body, like \ell_1 and \ell_4 in the figure. What Bárány and Roldán-Pensado prove is that there exists a point P for which this can only happen a finite number of times. More formally:

Given a convex body K , there is a point P on the boundary of K for which there is a finite number of pairs (Q,\ell)\in\Gamma such that P\in\ell and P\neq Q .

The reason why this result implies the previous one deserves to be explained before finishing. Consider a point P on the boundary of K such that there are 2 points equidistant to P on that boundary, call them E_1 and E_2 . The distance between P and these two points on the boundary is the same.

Hence, because of Rolle’s theorem, there must be a point Q on the boundary, between E_1 and E_2 , which maximizes or minimizes the distance to P . Then, for this Q there is a normal \ell which contains P . See the following figure.

Credit: David Orden
Credit: David Orden

Hence, if P is a point on the boundary of K for which there are M pairs (Q,\ell)\in\Gamma with P\in\ell and P\neq Q , then any circle centered at P intersects the boundary in at most M+1 points, which implies that N(K)\leq M+1 . If the latter is finite, the former has to be finite as well.

As a final remark, note that this result does not imply the existence of a finite universal constant. There might exist a family of convex bodies K_n with respective constants N(K_n) such that those N(K_n) tend to infinity. In that case, no constant N would be universal, since one could always find a convex K_n for which N(K_n)>N , i.e., for which that N would not be valid.

In summary, this paper by Bárány and Roldán-Pensado includes two significant advances on an Erdős problem which, despite its simple formulation, remains unsolved since 1946.

References

  1. Paul Erdős. On sets of distances of n points. The American Mathematical Monthly 53(5) (1946), 248-250. http://www.jstor.org/stable/2305092
  2. Imre Bárány and Edgardo Roldán-Pensado. A Question from a Famous Paper of Erdős. Discrete and Computational Geometry. DOI: http://dx.doi.org/10.1007/s00454-013-9507-z

2 Comments

Post a comment

drameydramey

As far as I understand the conjecture says that there exists a point P, not that all the points have that special property. Therefore, I think that should not be stated that the conjecture is false because the example of the triangle.

David Orden

Dear dramey. Here comes another explanation, which I hope you find helpful.

Let us focus on the (boundary of the) acute triangle. What Erdős’s statement says is that there exists a “special” point P on the triangle, where special means having the following property:

Every circle with center P intersects the triangle in at most 2 points.”

Why is this is false? For any P you choose on the triangle, the Grinch can find a circle centered on your P and intersecting the triangle in 4 points.

Thus, the Grinch has showed that for your point P:

Not every circle with center P intersects the triangle in at most 2 points.”

because there is one intersecting in 4 points. In other words, the Grinch has showed that your point P is not “special”.

But the Grinch can do the same for any point P you choose, so there is no “special” point and hence the statement is false.

Of course, the counterexample is not mine, I just try to explain it 🙂 You can play around and emulate the Grinch with the GeoGebra interactive construction for the triangle.

Leave a reply

Your email is never shared. Required fields are marked.

Required
Required
Required

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>