A Basic Question About Multiplicative Energy

As part of some research project, I got to a basic question about multiplicative energy. Embarrassingly , I wasn’t able to get any non-trivial bound for it. Here is the problem. Any information about it would be highly appreciated.

Problem. Let A=\{1,2,3,\ldots,n^{1/2}\}   . Let B  be a set of n  real numbers. How large can the multiplicative energy E^\times(A,B)   be?

  • Can we prove that E^\times(A,B)  must be asymptotically smaller than n^{2}  ?
  • Is there a B  for which E^\times(A,B)  is asymptotically larger than n^{3/2}  ?

Both questions are about improving the exponent of n  . Sub-polynomial improvements would be less interesting. Multiplicative energy means

E^\times(A,B) = |\{(a,a',b,b')\in A^2\times B^2\ :\ ab=a'b'\}|

Any ideas?

Isn’t this supposed to be an easy problem?!

A variant. Still here and want to read more? We can also consider the case when A  is larger. Let A=\{1,2,3,\ldots,n^{\alpha}\}  , where 1/2 < \alpha <1  .

In this case, a simple argument leads to an upper bound that is better than the trivial one. Let r_A(x) = |\{(a,a')\in A^2:\ a/a'=x \}|  . The Cauchy-Schwarz inequality implies that

E^\times(A,B) = |\{(a,a',b,b')\in A^2\times B^2\ :\ a/a'=b'/b\}|

= \sum_{x\in A/A} r_A(x) \cdot r_B(x) \le \sqrt{\sum_{x}r_A(x)^2} \cdot \sqrt{\sum_x r_B(x)^2}

=\sqrt{E^\times(A) \cdot E^\times(B)}

It is not difficult to show that E^\times(A)=\Theta(n^{2\alpha})  , up to sub-polynomial factors. This implies that E^\times(A,B)=O(n^{3/2+\alpha})  , up to sub-polynomial factors. In this case, the trivial upper bound is E^\times(A,B)=O(n^{1+2\alpha})  .

The above still leaves a large gap between the lower bound O(n^{1+\alpha}) and the upper bound E^\times(A,B)=O(n^{3/2+\alpha})  , up to sub-polynomial factors.

Any ideas?

The 2021 Polymath Jr Program

Summer Opportunity: Polymath Jr Research Experience for Undergraduates. The goal of this remote program is to provide opportunities to undergraduates who wish to explore research mathematics. The program consists of research projects on a wide variety of mathematical topics. Each project is guided by an active researcher with experience in undergraduate mentoring. All undergraduates who have experience with writing mathematical proofs are eligible. Part-time participation is also allowed; preference is given to students who will not have an undergraduate degree by July 2021. 

The program will run from June 21st to August 15th, 2021. For more details, see https://geometrynyc.wixsite.com/polymathreu and apply by early April at https://www.mathprograms.org/db; for additional questions contact adam.sheffer@baruch.cuny.edu.

19th Century Precursors of Polynomial Methods

These days, I’m spending a lot of time revising my book about polynomial methods and incidences (an older draft is available here). This led me to the following conclusion: I am not sure what classifies a proof as a polynomial method. A Wikipedia page states

“… the polynomial method is an algebraic approach to combinatorics problems that involves capturing some combinatorial structure using polynomials and proceeding to argue about their algebraic properties.”

I like this statement a lot, but I still don’t know whether some arguments should be considered as polynomial methods or not. There’s probably no good answer. Still, in this post, I want go over a case that I find interesting: If you have an inclusive view, you could claim that polynomial methods started in the 19th century. Anurag Bishnoi made a wonderful list of early polynomial method results, but it only goes back to 1975.

We can consider results such as the Monge-Cayley-Salmon theorem. However, for simplicity, let’s stick to shorter and more elementary proofs. Pascal’s theorem is from 1640. Two centuries later, Plücker provided an alternative proof for this theorem, which is based on studying basic properties of polynomials. For points {a,b\in {\mathbb R}^2} , we denote the line incident to a  and b  as \overline{ab}  . For a polynomial f  , we denote as {\bf V}(f)  the variety defined by f  (that is, the set of points on which f  vanishes).

Julius Plücker

Pascal’s Theorem. Let \gamma\subset {\mathbb R}^2  be an ellipse, parabola, or hyperbola. Consider six distinct points a,b,c,d,e,f\in \gamma  . Then the three points \overline{ab}\cap \overline{de}  , \overline{cd}\cap \overline{af}  , and \overline{ef}\cap \overline{bc}  are collinear.

Proof. Note that \gamma  is an irreducible curve of degree 2. Let h\in {\mathbb R}[x,y]  be a degree 2 polynomial that satisfies \gamma = {\bf V}(h) . We define two more curves:

L_1 = \overline{ab}\cup \overline{cd} \cup \overline{ef},

L_2 = \overline{de}\cup \overline{af} \cup \overline{bc}.

Both L_1  and L_2  are curves of degree 3, since each can be defined as the product of three linear equations. Let g_1,g_2\in {\mathbb R}[x,y]  be degree 3 polynomials that satisfy L_1 = {\bf V}(g_1)  and L_2 = {\bf V}(g_2)  . Let p  be an arbitrary point of \gamma  that is not one of a,b,c,d,e,f  . There exists \alpha\in {\mathbb R}  such that the polynomial g = g_1 + \alpha g_2  vanishes on p  . Indeed, one can think of g(p)  as a linear polynomial in \alpha  , and set \alpha  to be the unique root of this polynomial. We note that g  is of degree 3 and vanishes on a,b,c,d,e,f,p  .

By Bézout’s theorem, either g  and h  have a common factor or

|{\bf V}(g)\cap {\bf V}(h)| \le \deg g \cdot \deg h = 3 \cdot 2 = 6.

Since both g  and h  vanish on the seven points a,b,c,d,e,f,p  , we get that the two polynomials have a common factor. Since h  is irreducible, h  is a factor of g  . This implies that {\bf V}(g)  is the union of \gamma  and a line \ell  . Since \gamma  cannot contain the three intersection points \overline{ab}\cap \overline{de}  , \overline{cd}\cap \overline{af}  , and \overline{ef}\cap \overline{bc}  , these points are contained in \ell  . That is, the three intersection points are collinear. \Box

Plücker’s proof is a simple application of Bézout’s theorem. Should it be considered as a polynomial method? Purists might argue that polynomial proofs should involve asymptotically large configurations. That is, that the problem should involve n objects and a polynomial of degree that depends on n  . But this is not the case for some recent results. For example, people seem to consider the following proof as a polynomial method. It is also called a polynomial method in Larry Guth’s book about polynomial methods.

A regulus is the union of all lines in {\mathbb R}^3  that intersect three pairwise-skew lines \ell_1,\ell_2,\ell_3  . That is, no two lines of \ell_1,\ell_2,\ell_3  are parallel and no two intersect. One example of a regulus is the hyperbolic paraboloid {\bf V}(z-xy)  , depicted in the figure below. This surface is the union of all lines of the form {\bf V}(x-c,z-cy)  where c\in {\mathbb R}  . It is also the union of all lines of the form {\bf V}(y-c,z-cx)  . The lines in each of these families are pairwise-skew. We obtain {\bf V}(z-xy)  by taking the union of all lines that intersect three lines of the form {\bf V}(y-c,z-cx)  . This is the family of lines of the form {\bf V}(x-c,z-cy)  . Similarly, we obtain {\bf V}(z-xy)  by taking the union of all lines that intersect three lines of the form {\bf V}(x-c,z-cy)  .

A hyperbolic paraboloid

Lemma. Every regulus in {\mathbb R}^3  is contained in an irreducible variety that is defined by a polynomial of degree two.

Proof. Consider a regulus S\subset{\mathbb R}^3  that is defined by the three pairwise-skew lines \ell_1,\ell_2  , and \ell_3  . Let {\mathcal P}  be a set of nine points that is obtained by arbitrarily choosing three points from each of \ell_1,\ell_2  , and \ell_3  . Since \binom{3+2}{3} = 10 > 9  , a standard polynomial parameter counting implies that there exists a nonzero f\in {\mathbb R}[x,y,z]  of degree at most two that vanishes on {\mathcal P}  . We apply Bézout’s theorem in a plane that contains \ell_1  and is not contained in {\bf V}(f)  . That is, we consider a linear bivariate polynomial that defines \ell_1  and a polynomial that defines the intersection of {\bf V}(f)  with the plane. Since \ell_1  intersects {\bf V}(f)  in at least three points, Bézout’s theorem implies that \ell_1 \subset {\bf V}(f)  . For the same reason, we also have that \ell_2,\ell_3\subset {\bf V}(f)  . If {\bf V}(f)  is a plane or a union of two planes, then at least two of \ell_1,\ell_2,\ell_3  are contained in a common plane. This would contradict the assumption that the three lines are pairwise-skew. We conclude that {\bf V}(f)  is an irreducible variety of degree two.

Consider a line \ell'  that intersects all three lines \ell_1,\ell_2,\ell_3  . The three intersection points are distinct since \ell_1,\ell_2,\ell_3  are disjoint. Since \ell'  intersects {\bf V}(f)  in at least three points, Bézout’s theorem implies that \ell' \subset {\bf V}(f)  . Since S  is the union of all lines that intersect \ell_1,\ell_2,\ell_3  , we get that S\subseteq {\bf V}(f)  .

So, can we start saying that polynomial methods go back to the 1840’s?

A younger Adam and a giant regulus.

Combinatorial Journals are Changing

I used to ask most combinatorialists I met for their opinion about the level of various journals. With this feedback, I compiled a rough journal ranking for combinatorics papers (for personal use). This was a very educational experience for me as a new combinatorialist. I learned that different people have rather different opinions. For example, people tend to have a higher opinion of the journals of their own combinatorial sub-field.

However, people’s opinions did not vary much with respect to the very few top combinatorics journals. In particular, I don’t recall a single person who didn’t agree with Journal of Combinatorial Theory Series A being one of those (and similarly Combinatorica). This makes the following announcement quite significant:

“The majority of the JCT A editorial boards have recently notified Elsevier that they will not be renewing their contracts, and will resign after December 2020”

(Thank you Pablo Soberón for telling me about this.) The reason for this development is JCTA belonging to Elsevier. A new substitute journal has been created: Combinatorial Theory. This journal is “mathematician-owned, and fully open access, with no charges for authors or readers.” It already has a very impressive editorial board.

It would be interesting to see what happens next. So far not a lot of information can be found online. Are any combinatorialists plan to stand by JCTA? What about Elsevier’s top graph theory journal: Journal of Combinatorial Theory Series B?

There is one thing I really like about JCTA, and very much hope that Combinatorial Theory would adopt. Out of the stronger combinatorics journals, JCTA seems to be the one most open to all different types of combinatorics. From what I hear and see, all others tend to be at least somewhat biased towards some sub-fields. I’m told that JCTA originally focused on enumerative combinatorics, but this seems to be far from the case in recent years.

If you have more information about these developments, I would be very happy to hear!

Mathematics for Human Flourishing

I read a lot of “popular math” books. I also wrote about some in past posts. But I’ve never read a book similar to Mathematics for Human Flourishing by Francis Su. I already knew the math presented in this book and almost all other topics covered. I even knew some of Su’s personal stories from his past writings. But somehow that did not matter. I got more out of this book than from many other books whose topics were completely new to me.

So what is this unusual book about? Quoting from the first paragraph:

… this is a book that grounds mathematics in what it means to be a human being and to live a more fully human life.

Different people are likely to describe the main topic of the book in different ways. One might be “How one can live a healthy and fulfilling life in mathematics.” Another might be “How to do good in the world through mathematics (and not by solving a millennium prize problem).” There are likely to be many other different descriptions. But hopefully you get a vague idea.

To emphasize his main ideas, Su includes several “subplots” that develop throughout the book. One subplot is Su’s relationship with Christopher Jackson. Jackson is serving a 32-year prison sentence for a string of armed robberies. While in prison, he started reading basic math books, gradually moving to more advanced topics (under Su’s guidance). The correspondence between Jackson and Su exposes a fascinating story of how one finds their place in the world through math.

Another subplot is Su’s personal life. Su shares highly personal stories. Some stories are about his struggles with math and others unrelated to math. At least once I was so shocked by what Su was sharing that I had to stop reading for a few minutes.

A large portion of the book describes the mathematical world to people who are unfamiliar with it. This starts with the basic step of explaining that math is not about plugging numbers into formulas. It develops all the way to advanced topics such as how mentoring works. Su does excellent work explaining these ideas to non-mathematicians, in a fun and clear way. When describing ideas such as searching for patterns, real mathematical examples are provided. I would definitely recommend this book to family and non-math friends who wish to know more about what I do.

I would also recommend this book to students. While discussing how the math world works, it raises various issues that cause anxiety and distance people away from math. When working with students, I am going to steal some sentences, such as

“A popular myth of doing math is that either you see the answer or you don’t. In reality, you demonstrate mathematical power by assembling possible strategies and trying them to see if they will work.”

Since I know how the math world works, the mathematics explained in the book, and even some of Su’s personal stories, how could I get much out of this book? It got me to think about what exactly I like in math and in my work. It helped me see more clearly what my future goals are. It got me to think about how to better handle various tricky interactions with students and mentees. And more. I cannot say that about many books.

If your goal is to learn more math, do not read this book. If you are cynical about topics such as getting students less anxious about math, do not read this book. Read it if you are a mathematician who wants to rethink your attitude towards math and teaching. Or to get others more excited about math. Read it if you are a student who might have some anxiety about math or just want to know more about the math world. Recommend it to non-mathematicians who want to know what you are doing with your life.

Mind-Benders for the Quarantined

Peter Winkler is a world expert on mathematical puzzles (he is also an excellent researcher and this year’s resident mathematician of the MoMath). I just learned about two things that he is currently up to.

Winkler is running Mind-Benders for the Quarantined. After signing up to this free service, you receive a mathematical puzzle every Sunday, by email. You then get a subtle hint on Tuesday, a big hint on Thursday, and the solution on Saturday.


Winkler’s new book should be out around the end of 2020. While he already published wonderful book collections of mathematical puzzles in the past, this one is meant to be a special collection of the world’s top puzzles. For example, the new book would also include the best puzzles from Winkler’s past books.

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. She was recently accepted to a graduate program at Oxford.


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