Polymath REU

I am excited to announce a new program for undergraduates: The Polymath REU will run during the summer of 2020.

Due to the pandemic, many students are stuck at home without a summer program. The aim of the Polymath REU program is to provide research opportunities for such students. The program consists of research projects in a variety of mathematical topics and runs in the spirit of the Polymath Project. Each research project is mentored by an active researcher with experience in undergraduate mentoring.

My collaborators in the program are Ben Brubaker, Steven Miller, and Yunus Zeytuncu. I like this group! Each person has experience with running an REU program and together we cover a variety of mathematical fields.

The program is open to all undergraduate students, with no nationality or geographic restrictions. Acceptance is not automatic. However, the program is open to the majority of undergraduates having experience with writing mathematical proofs.

The research part of the program begins June 22nd and ends August 15th. The applications deadline is June 10th. For more information, see our website.

If you can, please help us spread the word. We would love to reach many undergraduates who are stuck at home this summer.


Math Summer Programs

The virus is causing some math summer programs to cancel. Surprisingly, this led to something wonderful. Unusually strong undergrads are starting to run their own online summer math programs for high school students.

1. The MORPH program is run by the Harvard math club. It offers a variety of mathematical topics at different levels of difficulty. It is not only free, but also subsidizes books for admitted students.

2. Alec Sun’s program seems to be more focused towards research.

I know students from the staff of both programs and believe that (math-wise) they are some of the strongest in the country.

(As usual, high-school students who wish to do a research project are also welcome to contact me. Unlike the above, this is not for a summer project. This is for students who wish to spend a large amount of time spread over a many months, with the goal of producing their own research paper. See more here.)


An Algorithms Course with Minimal Prerequisites

There are amazing materials for teaching theoretical algorithms courses: excellent books, lecture notes, and online courses. But none of the resources I am familiar with fits the algorithms course I was supposed to prepare. I wanted to teach a course for students who hardly have any prerequisites.

My students are non-CS majors (mostly math majors), so they did not take a data structures course. I also cannot assume that they have experience with probability, graph theory, linear algebra, writing proofs, and so on. So I made a class that only has two basic requirements:

  • Basic programming background: being comfortable with loops, if-else statements, and recursion.
  • No mathematical knowledge beyond calculus is required. However, the course is aimed at people who are comfortable with mathematical/abstract thinking.

Even though the course assumes minimum prerequisites, it gets into the technical details and some of the problems require a lot of thinking (although not at the beginning of course).

I made an effort to include many real-world applications, historical anecdotes, horrible jokes, and more. You can find the lecture notes and assignments by clicking on this sentence.

Any comments, questions, and complaints are welcome!


Teenagers doing Mathematical Research

I’d like to ramble about another program that our group is running. We are searching for unusually promising high-school-age students and mentor each in a serious research project. We started doing this already before our REU program. However, I never advertised this program before, because I felt that we were still learning how to do such mentoring. We are still learning, but I now feel more comfortable talking about this.

A couple of recent students. Let’s start with a couple of examples. These are the two most recent young students we worked with.

Kiki Pichini is currently 16 years old. She lives in a small town in the middle of Washington State, far from any big city. A few years ago, she wanted to learn more advanced mathematics but did not wish to leave home at her age. So she enrolled to an online undergraduate program of Indiana University. She will complete her undergraduate degree this upcoming spring.

While working on her degree at 15, Kiki wanted to continue to even more advanced projects, so I started working with her on a research project. This was done purely by email and video chats. Kiki just submitted her paper to a combinatorics journal. It can also be found on arXiv here. Kiki improved the current best upper bound on the number of rectangulations a planar point set can have – a bound that remained unchanged since 2006.


Our second most recent student is Michael Manta. Michael is a high-school student in Xavier High School in New York City. He was studying more advanced mathematics through an NYC-based program called Math-M-Addicts. We met Michael in the summer after his sophomore high-school year. He worked under the mentorship of Frank de Zeeuw and proved a new result about triangle colorings of the plane. He submitted his paper to a combinatorics journal a few months ago and it is currently being refereed. The paper can also be found on arXiv.

Michael was accepted to many top colleges. Eventually he chose to attend Caltech. After finishing his research project, he wanted to do more math. So he is currently taking a couple of the more advanced courses our department has to offer.

Continue reading

Incidences: Open Problems (part 2)

We now continue our journey of seeing how we still don’t know much about geometric incidences. So far, we looked at two main problems concerning incidences with curves in the plane (see the first post of the series). It might make sense to move to study incidences in higher dimensions. Instead, we are now regressing to discuss a problem about incidences with lines in the plane.

Problem 3. Structure for point-line incidences.

The exact asymptotic bound for point-line incidences in {\mathbb R}^2  was derived in the early 1980’s. Although several decades have passed, we still know relatively little about the point-line configurations that lead to many incidences. This is the structural problem: characterizing the point-line configurations that achieve the asymptotically maximal number of incidences.

It is not surprising that we do not know much about the structural problem, since this is the case for most problems in this part of discrete geometry – even after the extremal bound is obtained, we are not able say much about the structure of the extremal solutions. The major exception that comes to mind is the Green-Tao structural result for ordinary lines.

Back to point-line incidences in {\mathbb R}^2  , consider the case of n  points and n  lines. The Szemerédi–Trotter theorem states that the maximum number of incidences in this case is \Theta(n^{4/3})  . We have two constructions that achieve this bound: The original construction of Erdős and a simplified construction by Elekes. The points of the first construction are a \sqrt{n}\times \sqrt{n}  section of the integer lattice {\mathbb Z}^2  . The points in the second construction are an n^{1/3}\times n^{2/3}  section of {\mathbb Z}^2  (see figure below). One can further play with these constructions by applying projective transformations and taking subsets of the lattice.


Here are some structural question one might ask about point-line configurations with \Theta(n^{4/3})  incidences:

  • Are \sqrt{n}\times \sqrt{n}  and n^{1/3}\times n^{2/3}  the only lattice sizes that can achieve \Theta(n^{4/3})  incidences? For example, can we use an n^{2/5}\times n^{3/5}  section of {\mathbb Z}^2  ? Is there a continuous spectrum of lattice sizes or are there only a few sporadic sizes?
  • Must there always be a line that contains \sqrt{n}  of the points? (not necessarily a line from the set of n  lines). It is easy to show that there must exist a line containing n^{1/3}  points. I am not aware of any stronger bound for this problem.
  • Must we rely on a section of {\mathbb Z}^2  ? (possibly with a projective transformation and removing some points) Are there other lattices that work? Are there constructions that do not come from lattices?

Continue reading

New Horizons in Geometry and Micha Sharir

Always wanted to visit Israel? Like discrete or computational geometry, and Micha Sharir? Considering what to do with this year’s travel funds? Join us in Tel Aviv!

https://geometrynyc.wixsite.com/sharir (Open on a computer – does not support mobile yet.) If you can, please help us spread the word.


Partial list of speakers:

  • Pankaj Agarwal (Duke)
  • Noga Alon (Princeton)
  • Boris Aronov (NYU)
  • Shiri Artstein-Avidan (Tel Aviv University)
  • Kenneth Clarkson (IBM Almaden Research center)
  • Herbert Edelsbrunner (IST Austria)
  • Esther Ezra (Bar Ilan University)
  • Leonidas Guibas (Stanford)
  • Dan Halperin (Tel Aviv University)
  • Sariel Har-Peled (University of Illinois at Urbana–Champaign)
  • Gil Kalai (Hebrew University of Jerusalem)
  • Haim Kaplan (Tel Aviv University)
  • Nets Katz (Caltech)
  • Matya Katz (Ben Gurion University)
  • Klara Kedem (Ben Gurion University)
  • Nati Linial (Hebrew University of Jerusalem)
  • Janos Pach (Alfréd Rényi Institute of Mathematics)
  • József Solymosi (UBC)
  • Emo Welzl (ETH Zurich)

The conference is organized by Orit Raz, Natan Rubin, and myself. But the nice list of speakers is not due to us – Micha has a lot of impressive friends!

For any questions about the conference, feel free to contact me.

We’re Hiring!

Come join us! This year our math department has two types of positions available. We have a standard tenure track position, which would hopefully continue our awesome sequence of recent hires. But this post is not about the standard position. Instead, I’d like to talk a bit about our other type of position – a Lecturer position.

The lecturer position is basically a teaching-based “tenure-track” position. This brief description gives the wrong impression about the position. So here is a bit more information:

  • Lecturers must have a Ph.D. in math. They choose whether they wish to continue doing research – some do and others don’t. (This summer one of our lecturers had a paper accepted to the Annals of Mathematics!)
  • Our lecturers are some of the most highly respected people in the department. All of our current lecturers are amazingly professional and productive. They run a large part of the department, work closely with the chair, and so on.
  • After 5 years, a lecturer applies to receive a CCE status (Certificate of Continuous Employment), somewhat similar to tenure.

If you are a strong and enthusiastic teacher, and may be interested to join our team, apply on mathjobs.org. (Here is our standard tenure track position). I very much hope that we will hire someone who could be part of our REU program. But I’m only one person, and others have other priorities.


Since Baruch College is not the most well-known place in the mathematical world, I would like to also tell you a bit about us.

  • Baruch College is highly focused affordability, diversity, and social mobility. It is consistently ranked #1 in Social Mobility Index, towards the top of Money magazine’s Best Colleges For Your Money, WSJ Biggest Bargains Among U.S. Colleges, Affordable elite ranking, and so on.
  • We have a strong group of “junior” mathematicians. For example, Louis-Pierre Arguin‘s work was recently featured in the Bourbaki seminar (Louis-Pierre also holds an NSF career award). Other recent hires include strong people such as Yumeng Ou and Andrew Obus.
  • Our department’s financial math team has several impressive achievements. The master’s program in Financial Engineering is consistently ranked as one of the top in the world (see here and here) and the financial math students keep winning trading competitions (see here).
  • I believe that another advantage of our department is its unusually friendly and positive atmosphere. Somehow one does not see very bad politics here. For example, our last vote for the executive committee (handling hiring, tenure, etc.) was over extremely quickly and was almost unanimous.

Abstraction is Hard

A few weeks ago I read Malcolm Gladwell’s book The Tipping Point. The book doesn’t really deal with mathematics, but it does contain one math-related anecdote. This anecdote demonstrates an interesting principle of learning mathematics, so I wanted to share it.

Problem 1. We have a deck of cards, such that each card contains a digit on one side and an English letter on the other. We are dealing four cards, with the following result:


We are told that behind every vowel there is an even digit. Which of the four cards should we flip to check whether this claim is true?

I suspect that most mathematicians would only need a few seconds to answer this. On the other hand, people who are not used to mathematical logic would probably need a minute to get to the correct answer.

Problem 2. A cop walks into a bar to check for underage drinking and sees four people drinking. From a first glance, the cop notices that the first is a teenager, the second drinks water, the third is middle aged, and the fourth is drinking beer. Which of the four people should the cop check more carefully?

Most people would probably answer this problem immediately. This is interesting, since the two problems are completely identical! The only difference is that the second problem has a social context while the first is abstract. Even experienced mathematicians probably need to think for a couple of seconds to solve the first problem, but not the second.

This is a nice demonstration of why it is difficult to start studying advanced math. I will definitely use it when teaching proofs classes.

Here is another example of abstract things being hard to get:

Light Red Over Black 1957 by Mark Rothko 1903-1970


I did not post anything for almost five months – life has been very busy lately! I hope to get back to posting regularly relatively soon. In the meantime, I wanted to at least have a brief updates post.

I just made a revision of my book about incidences and polynomial methods. Joshua Zahl and I have been running a polynomial methods summer school for graduate students, at MSRI. This led to several topics being added to the book, such as a proof of the cap set theorem and a sum-product bound over finite fields. I also added many exercises, with a focus on clever elegant problems whose solution is not too technical. Many of those exercise have been carefully checked by the participants of the summer school 🙂


If you’d like to see more from the summer school, you can now watch close to 25 hours of Joshua Zahl and myself talking about polynomial methods. Starting here. We were lucky to have Marina Iliopoulou and Cosmin Pohoata helping us run this program. And also lucky to have a group of impressive graduate students participating and solving all of our weird exercise!

Our REU program for this summer is getting close to its end. I am amazed by the amount of strong results this summer’s participants produced. Once some of these results will become available online, this would be a good topic for a separate post.


I plan to soon write about several interesting events that we will be holding this academic year, upcoming hiring, and other news. I just need some time!

Incidences: Open Problems (part 1)

The past decade brought us several breakthroughs in the study of geometric incidences. Most importantly, Guth and Katz introduced polynomial partitioning, and this has become the main technique for studying incidences. The recent breakthroughs sometimes leads to a wrong impression about the state of this field. Actually, most of the main incidence problems are still wide open. At least one of the biggest incidence problems has been completely stuck since the early 1980’s.

This leads me to something that has been bothering me for a while (but probably not a single other person in the world…) For some reason, one can find the following statement in the Wikipedia page for the Szemeredi-Trotter theorem.


Solymosi and Tao indeed obtained an impressive and near sharp bound for an incidence problem. But it was not a general bound for points and varieties. Most incidence problems involving algebraic varieties in higher dimensions remain wide open. (fixed. Thank you David Eppstein!)

This post is the first of a series which will survey some of the main open problems involving incidence geometry. This series will illustrate how much we do not know about geometric incidences. If you are an outsider, you might start to look down at us incidence researchers. Over 35 years have passed since the Szemeredi-Trotter theorem, and since then we managed to resolve very few other incidence problems.

Problem 1. The unit distances problem

One may say that the main open problem involving geometric incidences is Erdös’s unit distances problem. To quote the book Research Problems in Discrete Geometry, this is

“possibly the best known (and simplest to explain) problem in combinatorial geometry”.

The problem simply asks: In a set of {n} points in {\mathbb{R}^2}, what is the maximum number of pairs of point at a distance of one? For example, {n} equally spaced points on a line span {n-1} unit distances. Using a lattice, one can obtain {n^{1+c/\log\log n}} unit distances, for some constant {c}. The current best upper bound states that every {n} points in the plane span {O(n^{4/3})} unit distances. Even though this is a central problem in Discrete Geometry, with many consequences, the last progress for it was obtained in the early 1980’s. The lower bound has not change since the 1940’s!

The unit distances problem is asymptotically equivalent to finding the maximum number of incidences between {n} points and {n} circles or radius one in {\mathbb{R}^2}. Indeed, consider a set of {n} points in {\mathbb{R}^2}. By placing a circle of radius one around every point, the number of point-circle incidences is twice the number of unit distances. One can move from the incidence problem to the unit distances problem in a similar manner.


It turns out that the problem significantly changes for different norms:

  • As already stated, for the Euclidean distance norm (the {\ell_2}-norm) this is a long-standing difficult problem.
  • For the {\ell_1}– and {\ell_\infty}-norms, one can easily find {n} points that span {\Theta(n^2)} unit distances.
  • Valtr showed that there is a simply-defined norm for which the answer is {\Theta(n^{4/3})}.
  • Matoušek showed that for a generic norm the maximum number of unit distances is {O(n \log n \log \log n)}.

Note that the conjectured bound {n^{1+c/\log\log n}} for {\ell_2} is different from all of the bounds stated above. In particular, this bound is asymptotically larger than {n \log n \log \log n}. Thus, any solution for the unit distances problem must rely an a property that is almost unique to the Euclidean distance norm. One may say that this problem is about studying properties of the underlying geometry.

The distinct distances problem is another main problem of the field. Guth and Katz almost completely solved this problem, and their work is often considered as the field’s most significant progress in the past decade. One can think of the unit distances problem as more difficult, since a solution to unit distances implies a solution to distinct distances, up to sub-polynomial factors. (For Harmonic Analysis people, the distinct distances problem seemed to have been the more interesting one, due to its connections with the Kakeya conjecture).

Problem 2. Incidences with other algebraic curves in {\mathbb{R}^2}

We know the maximum number of incidences between {m} points and {n} lines in {\mathbb{R}^2}. But what happens when replacing the lines with {n} circles? Parabolas? Arbitrary polynomial curves of degree three? Unfortunately, all of these problems are wide open. If you would now arbitrarily choose another variant, it will most likely also be wide open. The only other cases that are resolved in {\mathbb{R}^2} are a few very specific 2-parameter families of curves. For example, the problem is solved for parabolas of the form {y=x^2+ax+b}, and also for circles incident to the origin.

One can come up with infinitely many incidence problems with algebraic curves in {\mathbb{R}^2}. So what are the main questions? The previous problem already discussed incidences with unit circles. The problem of incidences with arbitrary circles also has many applications. However, the following conjecture is probably considered to be more important than incidences with arbitrary circles.

When discussing a family of algebraic curves, we may consider the number of parameters necessary to define a member of the family. For example, an arbitrary circle can be defined as {(x-a)^2+(y-b)^2=r^2} for parameters {a,b,r}. That is, the set of circles in {\mathbb{R}^2} is a three-parameter family. Similarly, the parabolas defined as {y=ax^2+bx+c} also form a three-parameter family.

Conjecture 1. Let {P} be a set of {m} points and let {\Gamma} be a family of {n} constant-degre algebraic curves defined using {k} parameters, both in {\mathbb{R}^2}. If {n\le m}, then

\displaystyle  I(P,\Gamma)=O_k\left(m^{2/3}n^{2/3}+m+n\right).

It is known that the restriction {n\le m} in the conjecture is necessary. For examples, see this construction for circles and this construction for parabolas. At the moment, the conjecture is open for any family of algebraic curves defined using at least three parameters. The current best bound, by Sharir and Zahl, is stated in the following theorem.

Theorem 2 Let {P} be a set of {m} points and let {\Gamma} be a set of {n} constant-degree algebraic curves defined using at most {k} parameters, both in {\mathbb{R}^2}. Then for any {\varepsilon>0},

\displaystyle  I(P,\Gamma)=O_k\left(m^{\frac{2k}{5k-4}}n^{\frac{5k-6}{5k-4}+\varepsilon}+m^{2/3}n^{2/3}+m+n\right).

Unlike the conjecture, this bound strongly depends on {k}. Sometimes the conjecture is stated with {k} being the degree of the curves, instead of the number of parameters. This is not so different, since the set of algebraic curves of degree at most {k} is defined using {\binom{k+2}{2}} parameters. (Still, the two cases are not quite the same.)

That’s it for now. More problems will appear in the next post of this series.