To cheer you up in complicated times – A book proof by Rom Pinchasi and Alexandr Polyanskii for a 1978 Conjecture by Erdős and Purdy!

Things do not look that good, and these are difficult times. But here on the blog we have plenty of things to cheer you up and assure you. And today we point to two book proofs — two book proofs to the same theorem– and, as a matter of fact, two book proofs to the same theorem by the same person, Rom Pinchasi.  One of the proofs, the one chosen for presentation, is by Rom Pinchasi and  Alexandr Polyanskii.

Rom Pinchasi has an immense proving power, both for difficult proofs at all costs, for book proofs, and for a large variety of proofs in between. (See, for example,  this post.)

Before moving on, let me mention that there is a timely blog post by Terry Tao on Online teaching, and here is a related MO question about online conferences that I asked last December.

Proofs from the book

Famously, the mathematician Paul Erdős, often referred to “The Book” in which God keeps the most elegant proof of each mathematical theorem. During a lecture in 1985, Erdős said, “You don’t have to believe in God, but you should believe in The Book.” (And you do not have even to believe in the book to enjoy proofs from the book.)

The Theorem: a 1978 conjecture by Erdős and Purdy

Theorem:  Let P be a set of n points in general position in the plane. Suppose that R is a set of red points disjoint from P such that every line determined by P passes through a point in R. Then |R|≥ n for n > 6.

This theorem settles a problem by Erdős and Purdy from 1978. Erdős and Purdy also asked about the case where the set of points is not required to be in general position. For that problem the best known lower bound, also proved by Rom Pinchasi, is n/3.

Book Proof I: An algebraic solution of a problem of Erdős and Purdy, by Rom Pinchasi

Book Proof II: A one-page solution of a problem of Erdős and Purdy, by Rom Pinchasi and Alexandr Polyanskii

Murty’s magic configurations conjecture.

The first proof of the Erdős-Purdy 1978 Conjecture was achieved in 2008 by Eyal Ackerman, Kevin Buchin, Christian Knauer, Rom Pinchasi, and Günter Rote. They derived it from their solution to the 1971 conjecture on magic configurations by Murty. A planar set of points P is called magic if it possible to assign positive weights to the points so that the sum of weights in every line determined by the points is one. Murty conjectured that the only magic configurations are those in general position, and those which have a line missing at most one of the points, and a certain configuration of seven points.

The Pinchasi-Polyanskii Book-Proof:

Here, we very closely follow the Pinchasi-Polyanskii’s paper.

We say that a line is determined by a set of points in the plane if it contains at least two of the points. Since the points in P are in general position, each pair of points determines a different line.

Under the contrary assumption we must have |R| = n−1. Then it must be that every point in R is incident to precisely n/2 lines determined by P and every line determined by P is incident to precisely one point in R. We would like to reach a contradiction.

Preliminary step: apply a projective transformation to the plane such that the convex hull of P becomes a triangle.

Observation 1:  No point of R lies outside the convex hull of P.

Such a point r should be incident to two lines supporting the convex hull of P. Each of these supporting lines must contain precisely two points of P. Since the convex hull of P is a triangle this is impossible.

Regard the points in the plane as complex numbers.

(This is really cool. I am not aware of many examples in discrete geometry that thinking about planar points as complex numbers helps.)

Notation: for every point p in the plane we denote by   the x-coordinate of p.

Crucial definition: For every point p ∈ P define

Observation 2: f(p) is a real number!

The proof will surely make you smile: For every p’ ∈ P \{p} there is a unique r ∈ R such that p, p’, and r are collinear. So (p-r)/(p-p’) is real. And the big ratio between products split to many small fractions that are all real.  Walla!

Note that f(p) is thus also invariant under rotations of the plane.

Now, if the vertical line through p does not contain any other point in P ∪ R, then, for the unique r ∈ R such that p, p’, and r are collinear, we have that:

.

This leads to:

Observation 3:  if the vertical line through p does not contain any other point in P ∪ R, then

Crucial observation 4:  Let p and q be any two points in P and let r be the unique point in R collinear with p and q. Then

f(p)/f(q)=-(p-r)/(q-r).

To see this rotate the plane so that the x-coordinates of p,q, and r are equal (or nearly equal) and apply Equations (2) and (1). (You will get the same, or nearly the same, contributions for r’ ≠ r  and you are left with the contribution for r. ) This also leads to:

Observation 5: f(p)/f(q) >0  if and only if the unique point r ∈ R that is collinear with p and q lies in the straight line segment delimited by p and q.

A complete graph with green and red edges.

Consider the complete graph G whose vertices are the points in P. For every two points p, q ∈ P we color the edge connecting  p and q red if the unique point in R collinear with p and q lies outside the straight line segment connecting p and q. Otherwise we color the edge green. In other words, the edge is red if f(p)/f(q) < 0, and green if f(p)/f(q) > 0.

The vertices of G can naturally be partitioned into two sets: U = {p ∈ P | f(p) > 0} and W = {p ∈ P | f(p) < 0}.

Without loss of generality assume that the three vertices of the convex hull of P belong to U. (Since no point of R is outside this convex hull all edges of the triangle forming the convex hull are green.)

Observation 6: |U| = n/2 + 1.

To see this let a,b ∈ U be two vertices of the convex hull of P. Let c ∈ R be the point in R collinear with a and b. The point c must be between a and b on the boundary of the convex hull of P. Therefore, all the other n/2 −1 pairs of points of P that are collinear with c must form red edges. Consequently, precisely one point of every such pair belongs to U. Together with a and b, we obtain |U| = n/2+1.

End of proof:

Consider now any triangulation of the convex hull of P using all the vertices of U. This triangulation contains precisely 3|U|−6 edges all of which correspond to green edges in the graph G. Each edge in the triangulation contains a unique point in R. Therefore,

|R|≥ 3|1|−6 = 3n/2 −3.

This expression is greater than or equal to n for every n ≥ 6, as desired. ahla!

(Good old Euler’s theorem is used.)

Related things.

Yesterday, our PM explained on TV what geometric (exponential) growth is.  If I try to describe related results and problems to the theorem presented here, and move on to related results and problems to those and so on, the amount of beautiful results from discrete geometry will grow exponentially but this post will never be completed.

So let me mention just a few things.

1. The result is related to the Motzkin-Rabin Colorful Sylvester-Gallai theorem. Given a set of red points and blue points in the plane, not all on a line, the Motzkin-Rabin theorem asserts that there is a line that contains two or more points in the set, such that all the points on the line have the same color.
2. Starting with the Sylvester-Gallai theorem itself, there is a rich Gallai-Sylvester theory, with recent deep connections to the theory of computing; My third MathOverflow question was about a Sylvester-Gallai type problem and here is a link to Greg Kuperberg remark‘s regarding potential Gylvester-Kalai theorems.
3. Let me mention the 2012 solution by Ben Green and Terry Tao of the ordinary line conjecture and the Orchard conjecture.
4. Let me mention the proof of Andreii Kupavskii and Alexandr Polyanskii to Shur’s conjecture.
5. Here is a link to a very recent paper by Chaya Keller and Rom Pinchasi. There they make the following bold conjecture: Let P be a set of n points in general position and and let R be a set of n points disjoint from P. If every line determined by P passes through a point in R, then P ∪ R is contained in a cubic curve.
6. There is, of course the famous book by Martin Aigner and Günter Ziegler: Proofs from the book.
7. At some point I tried to interest Günter with a companion book: The book of examples. We did not proceed with this project but this motivated my successful MathOverflow questions about fundamental examples.
8. Eventually, Günter and I decided to write instead: the book of examples of polytopes. We went as far as writing a list of chapters of the book! (Which is a very advanced stage of writing a book, I suppose.)
9. When I took a class for high-school students interested in mathematics, the Sylvester problem was a starred problem in the first problem set and the assertion of the Motzkin-Rabin colored theorem was a double starred problem. Among the 20-30 students none of us found a (correct) solution. (We referred to it in a trivia question in this post.) Years later, I gave the same class and gave the same starred problems, and one student managed to prove the Gallai-Sylvester theorem. Can you guess who he was?