The Baruch Distinguished Mathematics Lecture Series

I am happy to announce the beginning of the Baruch Distinguished Mathematics Lecture Series. In this series we will bring established mathematicians to give talks to a general mathematical audience.

Our first Distinguished Lecture, by Bjorn Poonen, will be “Undecidability in Number Theory”. Click here for the full details. The talk is open to everyone, and includes refreshments. After the talk we will also go to lunch with the speaker.


Incidences in a Recent Work of Walsh

Recently, Miguel Walsh posted a very interesting paper on arXiv. The main purpose of the paper is to study various properties of polynomials and varieties. These properties are related to incidence problems – some originally arose from studying incidences. Walsh also presents new incidence bounds as applications of his results. In this post I’ll briefly discuss the incidence aspects of Walsh’s paper. Since this is a rather specialized post for incidence researchers, it assumes familiarity with the problems and notation.

Miguel Walsh

It seems to me that Walsh’s paper makes three main contributions to the study of incidence problems. The first two contributions are explicitly stated in the paper:

  • The paper derives a new polynomial partitioning theorem for points on a variety, with a good dependency on the degree of the variety. This was the missing step for removing an extra \varepsilon  in the exponent from most of the existing incidence bounds in {\mathbb R}^d  . For example, it should remove the extra \varepsilon  in the results of several of my papers, such as this one and that one.
  • As an application of his results, Walsh introduces an incidence problem that I did not see before. In this problem we study incidences between points and varieties in {\mathbb R}^d  , but the degrees of the varieties are not constant. That is, the degrees of the varieties are allowed to depend on the number of points and on the number of varieties. It would be interesting to see how this variant develops. For example, what applications in other subfields it might have.

The two above incidence results are definitely interesting, but I suspect that the paper would have a more significant effect on the incidence community in a different way. The paper makes significant progress in our understanding of polynomials and varieties, which directly affect the algebraic methods used to derive incidence bounds. This improved understanding could potentially be what we need to address some of the main problems that we have been trying to solve for a while. Me and other incidences researchers will definitely spend time reading the paper carefully, and think how it might fit with these problems. Walsh also mentions a follow-up paper, and I wonder if he has something similar in mind. I am planning to soon write a post about the current main open problems in incidence theory, and will then mention more clearly what I am referring to.

It might also be worth discussing the lower bounds part of the paper. The paper contains matching lower bounds for some of its incidence results. However, these lower bounds seem to apply specifically to the new variant of incidences with varieties of non-constant degrees. The “standard” problem of incidences with bounded-degree hypersurfaces in {\mathbb R}^d  remains open. In particular, we have matching lower bounds only in some cases. For an up-to-date discussion of the known lower bounds, see for example the relevant part in the introduction of my recent work with Thao Do.

An Uncitable Result?

My colleague Pablo Soberon just showed me an unusually problematic result to cite, and I wanted to share this weird story. If you have other weird citation stories, do tell!

Yes, this is a second silly post in a row. Lately I’m not finding the time to write more serious ones. And the silly stories need to be documented somewhere…

This story begins with a Japanese anime show called The Melancholy of Haruhi Suzumiya. I don’t know much about this show, but apparently there are several different orders in which one can watch the episodes. This led a fan of the show to ask for the minimum number of episodes one needs to watch, so that you saw all the episodes in every possible order. In other words, the minimum sequence of the numbers from \{1,\ldots,n\}  that contains every possible permutation of the numbers. (if I understand correctly, each order has to appear consecutively, with no additional numbers in between). This was on 4chan in 2011. A solution was then offered by an anonymous user, and this disappeared among the other weird anime discussions around the web.


It turns out that some people have been studying the above question as a serious math problem, prior to the show and not aware of it. The sequence containing all of the possible permutations is referred to as a superpermutation. See for example here and here. One paper about this was even published in the journal “Discrete Mathematics” in 2013.

Now the people coming from the mathematical angle discovered the original 4chan discussion, and in it the solution to the problem. So can they cite this result? It is by an anonymous person and appeared on an anime fans website. If this is not complicated enough, the relevant website no longer exists. Instead, the original discussion was discovered on a site that archives old online discussions. And it’s unclear how stable this archive site is. Luckily, this is not my problem!

Mathematical Energy: Etymology

This might be the silliest post I’ve written so far (yes – worse than “Was Disney trying to kill mathematicians?”). I urge you to stop reading now unless (i) you are quite familiar with the mathematical notion of energy (e.g., additive energy), and (ii) you have a horrible sense of humor.

The term energy was coined by Tao and Vu. I like “energy” as a name for this object, but I never had a good answer when asked why this is how it’s called. That is, until a referee report provided me with an answer. And this wonderful referee probably didn’t even know it.

In a recent paper, Cosmin Pohoata and I used “color energy”. We have a graph G=(V,E)  with colored edges. Denote the color of an edge (v_1,v_2)  as \chi(v_1,v_2)  . The color energy of G  is

E(G) = \left|\left\{(v_1,v_2,v_3,v_4)\in V^4 :\ \chi(v_1,v_2) = \chi(v_3,v_4) \right\}\right|.

The referee complained about our notation for the multiplicity of a color c  (the number of edge of color c  ), and asked to change it to m_c  . After this change of notation, the energy is defined by the standard formula

E = \sum m_c^2.

NYC Discrete Geometry: Introductory Meeting

I am excited to announce the official start of our new Discrete Geometry group! This event will also be the first meeting of the NYC Geometry Seminar in the CUNY Graduate Center (midtown Manhattan). It will take place at 2pm of Friday August 31st. If you are in the NYC area and interested in Discrete Geometry and related topics – come join us!

The introductory meeting would not consist of the standard seminar presentation. Instead, the purpose of the event is to meet people who are interested in Discrete Geometry, Computational Geometry, and so on (with people coming from NYU, Princeton, various CUNYs, etc). Participants will introduce themselves to the audience and mention the main topics that interest them. You are welcome to either introduce yourself, or just to come listen and have some pastries. If you introduce yourself, you are encouraged to briefly state a major open problem you wish you could solve.

For the exact location, see the event page. Personally, I plan to have more technical math discussions with some participants before and after this meeting.


Linear Algebra Riddle

I’d like to tell you about a nice riddle, which I heard from Bob Krueger (one of our current REU participants, who already has four papers on arXiv!!). The riddle requires very basic linear algebra and is in the spirit of the previous post.

Riddle. A library has n  books and n+1  subscribers. Each subscriber read at least one book from the library. Prove that there must exist two disjoint sets of subscribers who read exactly the same books (that is, the union of the books read by the subscribers in each set is the same).

Hint: Very basic linear algebra. Try the first thing that comes to mind.

Inside the library of the university of Leuven, Belgium

Discrete Geometry Classic: Two-distance Sets

This post presents another simple and elegant argument in Discrete Geometry. This classic is based on the so-called “Linear Algebra method”.

Warm-up problem. What is the maximum size of a set {\cal P} \subset {\mathbb R}^d  such that the distance between every two points of the set is 1?

By taking the vertices of a d  -dimensional simplex with side length 1 in {\mathbb R}^d  , we obtain d+1  points that span only the distance 1. It is not difficult to show that a set of d+2  points in {\mathbb R}^d  cannot span a single distance.


The two-distance sets problem. A point set \cal P  is a two-distance set if there exist r,s\in {\mathbb R}  such that the distance between every pair of points of \cal P  is either r  or s  . What is the maximum size of a two-distance set in {\mathbb R}^d  ?

There is a simple trick for constructing a two-distance set of size \binom{d}{2}  in {\mathbb R}^d  . You might like to spend a minute or two thinking about it. Here is a picture of Euler to prevent you from seeing the answer before you wish to.


Consider the set of all points in {\mathbb R}^d  that have two coordinates with value 1 and the other d-2  coordinates with value 0. There are \binom{d}{2}  such points, and the distance between every pair of those is either 1 or 2.

Larman, Rogers, and Seidel showed that the above example is not far from being tight.

Theorem. Every two-distance set in {\mathbb R}^d  has size at most \binom{d}{2}+3d+2  .

Proof. Let {\cal P} = \{p_1,p_2,\ldots, p_m\}  be a two-distance set in {\mathbb R}^d  , and denote the two distances as r,s\in {\mathbb R}  . Given points a,b\in {\mathbb R}^d  , we denote the distance between them as D(a,b)  . We refer to a point in {\mathbb R}^d  as x=(x_1,\ldots,x_d)  . For 1\le j \le m  , define the polynomial f_j\in {\mathbb R}[x_1,\ldots,x_d]  as

f_j(x) = \left(D(x,p_j)^2 - r^2\right) \cdot \left(D(x,p_j)^2 - s^2\right).

That is, f_j  is a polynomial of degree four in x_1,\ldots,x_d  that vanishes on points at distance r  or s  from p_j  . Every such polynomial is a linear combination of the polynomials

\left(\sum_{j=1}^d x_j^2\right)^2,\qquad  x_k \sum_{j=1}^d x_j^2,\qquad x_k,\qquad  x_\ell x_k,\qquad 1,

for every 1\le \ell, k\le d  . Since every f_j  is a linear combination of t = \binom{d}{2}+3d+2  polynomials, we can represent f_j  as a vector in {\mathbb R}^t  . In particular, the vector V = (v_1,\ldots,v_t)  corresponds to the polynomial

v_1 \cdot \left(\sum_{j=1}^d x_j^2\right)^2 + v_2\cdot  x_1 \sum_{j=1}^d x_j^2 + v_3\cdot  x_2 \sum_{j=1}^d x_j^2 + \cdots + v_{t} \cdot 1.

For 1\le j \le m  , let V_j  denote the vector corresponding to f_j  . Consider \alpha_1,\ldots,\alpha_m\in {\mathbb R}  such that \sum_{j=1}^m \alpha_j V_j = 0  . Let g(x) = \sum_{j=1}^m \alpha_j f_j(x)  . By definition, the polynomial g(x)  is identically zero. For some fixed p_k\in {\cal P}  , note that f_j(p_k)=0  for every j\neq k  and that f_j(p_j) = r^2s^2  . Combining the above implies

g(p_k) = \sum_{j=1}^m \alpha_j f_j(p_k) = \alpha_kr^2s^2.

Since g(x)=0  , we have that \alpha_k=0  . That is, the only solution \sum_{j=1}^m \alpha_j V_j = 0  is \alpha_1=\cdots = \alpha_m = 0  . This implies that the vectors V_1,\ldots,V_m  are linearly independent. Since these vectors are in {\mathbb R}^t  , we conclude that m \le t = \binom{d}{2}+3d+2  . \Box

One can improve the above bound by showing that the polynomials f_j  are contained in a smaller vector space. This is left as an exercise of your googling capabilities.

The Math Art of Gábor Damásdi

You may have noticed that the credit for the drawing in my previous post went to Gábor Damásdi. Gábor is a PhD student at the Hebrew University of Jerusalem. He is also one of the top math art creators I have met.

Gábor Damásdi.

I think it took Gábor less than two minutes to prepare the drawing for the previous post, and this is one of his least interesting creations. Check out his site, which contains many more interesting things. You can find there drawings and animation of many mathematical results. Here is an animation of Pascal’s theorem:


Here is a Voronoi diagram of moving points:

I hope that in the future we’d have more of Gábor’s creations in this blog!

Points in General Position

Many Discrete Geometry problems study planar point sets in general position. Most commonly, this definition refers to point sets with no three collinear points and no four cocircular points (that is, no circle contains four points of the set). A few examples of such problems:

  • What is the minimum number of distinct distances that are spanned by a set of n  points in general position?
  • What is the minimum number of convex k  -gons determined by n  points in general position?
  • For even n  , what is the maximum number of distinct ways in which one can cut a set of n  points in general position by a line into two halves, each of cardinality n/2  ?
  • What is the maximum number of points that can be placed on an n \times n  grid so that no three points are collinear. What happens when we also forbid four cocircular points?
Randomly choosing n  points from the plane will lead to a set in general position, but this set is unlikely to have any interesting extremal structure. For example, we expect such a set to span many distinct distances, and it is not clear why such a set should span few convex k  -gons. Problems such as the ones above ask for point sets that are in general position while also having some kind of structure. I often find it useful to have examples of such point sets as part of my “Discrete Geometry toolkit”. I am familiar with two very different constructions of such sets. This post describes these two constructions. If you are familiar with additional constructions, do let me know!

Construction 1: Subsets of the integer lattice. Our first construction involves finding a large subset of an n \times n  section of the integer lattice that is in general position. The basic idea for this construction seems to originate from Erdős (for example, see this paper of Roth), although we will follow a later variant of Thiele.

For a prime p  , we consider the point set

{\cal P} = \left\{\left(t,t^2 \mod p\right)\ :\ 0\le t <p/4 \right\}.

Note that {\cal P}  is a set of \lfloor p/4\rfloor  points from a p\times p  section of the integer lattice. We will now show that {\cal P}  does not contain three collinear points or four cocircular points.

An example of the first construction, created by Gábor Damásdi.

Three points (x_1,y_1),(x_2,y_2),  and (x_3,y_3)  are collinear if and only if

\begin{vmatrix} 1 & x_1 & y_1 \\ 1 & x_2 & y_2 \\ 1 & x_3 & y_3 \end{vmatrix} = 0.

It is not difficult to check that for three points (t_1,t_1^2),(t_2,t_2^2),(t_3,t_3^2)  , we get

\begin{vmatrix} 1 & t_1 & t_1^2 \\ 1 & t_2 & t_2^2 \\ 1 & t_3 & t_3^2 \end{vmatrix} = (t_2-t_1)(t_3-t_2)(t_3-t_1).

For distinct integers t_1,t_2,t_3  , this determinant is clearly nonzero. When we also have that 0\le t_1,t_2,t_3 < p  , this determinant is also not a multiple of the prime p  . Thus,

\begin{vmatrix} 1 & t_1 & (t_1^2 \mod p) \\ 1 & t_2 & (t_2^2 \mod p) \\ 1 & t_3 & (t_3^2 \mod p) \end{vmatrix} \neq 0.

We conclude that no three points of {\cal P}  are collinear. We can use a similar argument for the case of cocircular points. Four points (x_1,y_1),(x_2,y_2),(x_3,y_3),  and (x_4,y_4)  are cocircular if and only if

\begin{vmatrix} 1 & x_1 & y_1 & x_1^2 +y_1^2\\ 1 & x_2 & y_2 & x_2^2 +y_2^2\\ 1 & x_3 & y_3 & x_3^2 +y_3^2\\ 1 & x_4 & y_4 & x_4^2 +y_4^2 \end{vmatrix} = 0.

(One can think of this test is as lifting the four points to the paraboloid defined by z=x^2+y^2  in {\mathbb R}^3  , and checking if the four lifted points are coplanar. It is known that the intersections of the paraboloid with planes are exactly the lifting of circles to the paraboloid.)

Taking the points (t_1,t_1^2),(t_2,t_2^2),(t_3,t_3^2),(t_4,t_4^2)  , we get

\begin{vmatrix} 1 & t_1 & t_1^2 & t_1^2 +t_1^4\\ 1 & t_2 & t_2^2 & t_2^2 +t_2^4\\ 1 & t_3 & t_3^2 & t_3^2 +t_3^4\\ 1 & t_4 & t_4^2 & t_4^2 +t_4^4 \end{vmatrix} = (t_1+t_2+t_3+t_4)\prod_{1\le j<k \le 4}(t_k-t_j).

Since 0\le t_1,t_2,t_3,t_4 < p/4  , we have that t_1+t_2+t_3+t_4  is not a multiple of p  . Assuming that the four integers are distinct, none of the elements of the product is a multiple of p  . Repeating the above argument, we get that no four points of {\cal P}  are cocircular.

Now that we know that the above construction is in general position, let us mention a few of its applications:

  • Erdős and Purdy asked for the size of the largest subset of the n\times n  integer lattice with no three points on a line and no four on a circle. The above construction provides the current best lower bound for this problem.
  • Erdős, Hickerson, and Pach asked whether there exists a planar set of n  points in general position that spans no parallelograms and still determines o(n^2)  distinct distances. Dumitrescu provided a positive answer to this question by using the above construction.
  • The Heilbronn triangle problem asks for the smallest \Delta(n)  such that every set of n  points in the unit square determine a triangle of area at most \Delta(n)  . Erdős used a variant of the above construction to produce one of the first non-trivial lower bounds for the problem.
Construction 2: Projection from a hypersphere. In our first construction, the point set has some structure since it is a subset of a p\times p  section of the integer lattice. The structure in our second construction also originates from a lattice, although in a very different way. This construction comes from a paper of Erdős, Füredi, Pach, and Ruzsa, and seems to be influenced by earlier ideas of Behrend.

For a positive integer d  , consider the section of the d  -dimensional integer lattice

{\cal L} = \left\{(x_1,\ldots,x_d)\in {\mathbb Z}^d :\ 0\le x_1,\ldots,x_d <2^d \right\}.

We claim that there exists a hypersphere around the origin that contains many points of {\cal L}  . First, note that |{\cal L}| = 2^{d^2}  . We also note that the distance between a point x\in {\cal L}  and the origin is \sqrt{x_1^2+\cdots+x_d^2}  . Every such distance is the square root of an integer between zero and d\cdot 2^{2d}  . That is, the points of {\cal L}  determine at most d\cdot 2^{2d}  distinct distances from the origin. By the pigeonhole principle, there exists a distance \delta  such that at least 2^{d^2}/(d\cdot 2^{2d})=2^{d(d-2)}/d  points are at distance \delta  from the origin. In other words, the hypersphere S_\delta  centered at the origin and of radius \delta  contains at least 2^{d(d-2)}/d  points of {\cal L}  . Let {\cal P}'  be a set of exactly n=2^{d(d-2)}/d  of these points. To recap, {\cal P}'  is a set of n  points with integer coordinates on the hypersphere S_\delta  .

Let h  be a generic two-dimensional plane in {\mathbb R}^d  (or, if you prefer, a random plane). Let {\cal P}  be the set of points that are projections of the points of {\cal P}'  on h  . It is not difficult to verify that, on a generic plane, no two points of {\cal P}'  are projected to the same point. Similarly, when projecting four points on a generic plane, we do not expect the projections to be cocircular. That is, we may assume that {\cal P}  consists of n  distinct points, no four which are cocircular.

It is not true that the projections of any three points on a generic plane are not collinear. If three points are collinear in {\mathbb R}^d  , then their projections on every plane would remain collinear. This is why we take the points of {\cal P}'  to be on the hypersphere S_\delta  : Since every line intersects the hypersphere in at most two points, no three points of {\cal P}'  are collinear.

Now that we constructed a set {\cal P}  of n  points in general position, it remains to see what structure {\cal P}  has. For this purpose, we return to the lattice {\cal L}  in {\mathbb R}^d  . It is not difficult to verify that the set of vectors determined by pairs of points of {\cal L}  is

\left\{(x_1,\ldots,x_d)\in {\mathbb Z}^d :\ -2^d\le x_1,\ldots,x_d <2^d \right\}.

That is, the number of distinct vectors determined by pairs of points of {\cal L}  is O\left(2^{d(d+1)}\right)  . Since {\cal P}' \subset {\cal L}  , the number of distinct vectors determined by pairs of points of {\cal P}'  is also O(2^{d(d+1)})  . Let p_1,p_2,p_3,p_4\in {\mathbb R}^d  satisfy p_1-p_2=p_3-p_4  , and let \pi(\cdot)  be a projection from {\mathbb R}^d  to a two-dimensional plane. Then \pi(p_1)-\pi(p_2)=\pi(p_3)-\pi(p_4)  . This implies that the number of distinct vectors determined by pairs of points of {\cal P}  is also O(2^{d(d+1)})  .

From the definition n=2^{d(d-2)}/d  we obtain \log n = d(d-2) - \log d  , which in turn implies 2^{d(d+1)} = O(n2^{\sqrt{\log n}})  . Thus, the number of distinct vectors determined by pairs of points of {\cal P}  is O\left(n2^{\sqrt{\log n}}\right)  . (If you are not used to such expressions, note that for every \varepsilon>0  we have n2^{\sqrt{\log n}} = O\left(n^{1+\varepsilon}\right)  .) This property shows that {\cal P}  has a strong structure. For example, it immediately implies that the number of distinct distances determined by {\cal P}  is O\left(n2^{\sqrt{\log n}}\right)  (and similarly for the number of distinct directions). That is, a set in general position can still determine a relatively small number of distinct distances.

Child Care at STOC 2018 + Riddle

I’ve been asked to post the following message by the STOC 2018 local arrangements chairs – Ilias Diakonikolas and David Kempe.

We are pleased to announce that we will provide pooled, subsidized
child care at STOC 2018. The cost will be $40 per day per child for
regular conference attendees, and $20 per day per child for students.
For more detailed information, including how to register for STOC 2018
childcare, see

To have something slightly mathematical in this post, here’s a cute riddle: 100 passengers enter an airplane one at a time. The plane contains 100 seats and every passanger has a ticket with a seat number. The first passanger lost his ticket, so he randomly chooses a seat (uniformly). When any other passanger enters, if their seat is available they use it, and otherwise they randomly choose one of the available seats (uniformly). What is the probability that the last passanger got their correct seat.


Finally the name of this blog makes sense!