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* deﬁne

**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:**

Continue reading →

### Like this:

Like Loading...