# 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.

# 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.

# Difference Sets with Local Properties

I recently attended a wonderful workshop about Algebraic methods in combinatorics, which took place in Harvard’s CMSA. There were many interesting participants from a variety of combinatorial fields, and a very friendly/productive atmosphere. My talk focused on a recent work with Cosmin Pohoata, and I also mentioned some distinct distances result that we derived. During the talk Zeev Dvir asked about an additive variant of the problem. After thinking about this variant for a bit, I think that it is a natural interesting problem. Surprisingly, so far I did not manage to find any hint of previous work on it (this might say more about my search capabilities than about the problem…)

Zeev Dvir and Cosmin Pohoata.

Let $\phi(n,k,\ell)$ denote the minimum size $A-A$ can have, when $A$ is a set of $n$ real numbers with the property that for any $A' \subset A$ with $|A'|=k$ we have $|A'-A'|\ge \ell$. That is, by having a local additive property of every small subset, we wish to obtain a global additive property of the entire set. For simplicity, we will ignore zero in the difference set. Similarly, we will ignore negative differences. These assumptions do not change the problem, but make it easier to discuss.

As a first example, note that $\phi(n,3,3)$ is the minimum number of differences determined by a set of $n$ reals with no 3-term arithmetic progressions. Behrend’s construction is a set $A$ of positive integers $a_1< a_2 < \cdots < a_n$ with no 3-term arithmetic progression and $a_n < n2^{O(\sqrt{\log n})}$. Thus, $\phi(n,3,3) < n2^{O(\sqrt{\log n})}$.

For another simple example, Consider a constant $k\ge 4$. Since we consider only positive differences, any set of $k$ reals determines at most $\binom{k}{2}$ differences. If a specific difference $d$ repeats $\lfloor k/2 \rfloor$ times, then by taking the numbers that span $d$ we obtain $A'\subset A$ such that $|A'|\le k$ and $|A'-A'| \le \binom{k}{2}- \lfloor k/2 \rfloor+1$. Thus, by asking every subset of size $k$ to span at least $\binom{k}{2}- \lfloor k/2 \rfloor+2$ differences, we obtain that no difference repeats $\lfloor k/2 \rfloor$ times in $A$. In other words

$\phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +2 \right) = \Omega\left(n^2\right).$

Repeating a simple argument of Erdős and Gyárfás gives

$\phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +1\right) = \Omega\left(n^{4/3}\right).$

That is, when moving from $\ell = \binom{k}{2}-\lfloor k/2 \rfloor +2$ to $\ell = \binom{k}{2}-\lfloor k/2 \rfloor +1$, we move from a trivial problem to a wide open one. My work with Cosmin Pohoata leads to the following result.

Theorem 1. For any $d\ge 2$ there exists $c$ such that

$\phi\left(n,k,\binom{k}{2}-k\frac{d}{d+1}+c\right) =\Omega\left(n^{1+1/d} \right).$

For example, when $d=2$ we get the bound

$\phi\left(n,k,\binom{k}{2}-\frac{2k}{3}+c\right) =\Omega\left(n^{3/2} \right).$

When $d=3$ we get a significant improvement for the range of the Erdős-Gyárfás bound:

$\phi\left(n,k,\binom{k}{2}-\frac{2k}{3}+c\right) =\Omega\left(n^{3/2} \right). \qquad \qquad \qquad (1)$

Since not much is known for this problem, it seems plausible that additional bounds could be obtained using current tools. Our technique does not rely on any additive properties, and holds for a more abstract scenario of graphs with colored edges. Hopefully in the case of difference sets one would be able to use additive properties to improve the bounds. Moreover, so far I know nothing about much smaller values of $\ell$, such as $\phi(n,k,100k)$.

Proof sketch for Theorem 1. For simplicity, let us consider the case of $d=3$, as stated in $(1)$. Other values of $d$ are handled in a similar manner. Let $A$ be a set of $n$ reals, such that any $A'\subset A$ of size $k$ satisfies $|A'-A'|\ge \binom{k}{2}-\frac{3k}{4}+13$. We define the third distance energy of $A$ as

$E_3(A) = \left|\left\{(a_1,a_2,a_3,b_1,b_2,b_3) \in A^6 :\, a_1-b_1=a_2-b_2=a_3-b_3 >0 \right\}\right|.$

The proof is based on double counting $E_3(A)$. For $\delta\in {\mathbb R}$, let $m_\delta = \left|\left\{(a,b)\in A^2 : a-b = \delta\right\}\right|$. That is, $m_\delta$ is the number of representations of $\delta$ as a difference of two elements of $A$. Note that the number of 6-tuples that satisfy $a_1-b_1=a_2-b_2=a_3-b_3$ is $m_\delta^3$. A simple application of Hölder ‘s inequality implies

$E_3(A) = \sum_{\delta>0} m_\delta^3 \ge \frac{n^6}{|A-A|^2}.$

To obtain a lower bound for $|A-A|$, it remains to derive an upper bound for $E_3(A)$.

For $j\in {\mathbb N}$ let $k_j$ denote the number of differences $\delta \in {\mathbb R}^+$ such that $m_\delta \ge j$. A dyadic decomposition gives

$E_3(A) = \sum_{\delta>0} m_\delta^3 = \sum_{j=1}^{\log n} \sum_{\substack{\delta>0 \\ 2^j \le m_\delta < 2^{j+1}}} m_\delta^3< \sum_{j=1}^{\log n} k_{2^j} 2^{3(j+1)}. \qquad \qquad \qquad (2)$

For $j\in {\mathbb N}$ let $\Delta_j$ denote the set of $\delta>0$ with $m_\delta\ge j$ (so $|\Delta_j| = k_j$). For $\delta >0$, let $A_\delta$ be the set of points that participate in at least one of the representations of $\delta$. If there exist $\delta_1,\delta_2, \delta_3$ such that $|A_{\delta_1} \cap A_{\delta_2} \cap A_{\delta_3}| \ge k/4$, then there exist a subset $A'\subset A$ with $|A'|=k$ and $|A'-A'|< \binom{k}{2}-\frac{3k}{4}+13$ (see the paper for a full explanation). Thus, for every $\delta_1,\delta_2, \delta_3$ we have that $|A_{\delta_1} \cap A_{\delta_2} \cap A_{\delta_3}| < k/4$.

We have $k_j$ sets $A_\delta$ with $|A_\delta| \ge j$. These are all subsets of the same set $A$ of size $n$, and every three intersect in fewer than $k/4$ elements. We now have a set theoretic problem: How many large subsets can $A$ have with no three having a large intersection. We can use the following counting lemma (for example, see Lemma 2.3 of Jukna’s Extremal Combinatorics) to obtain an upper bound on $k_j$.

Lemma 2. Let $A$ be a set of $n$ elements and let $d\ge 2$ be an integer. Let $A_1,\ldots,A_k$ be subsets of $A$, each of size at least $m$. If $k \ge 2d n^d/m^d$ then there exist $1\le j_1 < \ldots < j_d \le d$ such that $|A_{j_1}\cap \ldots \cap A_{j_d}| \ge \frac{m^d}{2n^{d-1}}$.

Lemma 2 implies the bound $k_j = O(n^3/j^3)$ for large values of $j$. Combining this with $(2)$ and with a couple of standard arguments leads to $E_3(A) = O(n^{10/3})$. Combining this with $E_3(A) \ge \frac{n^6}{|A-A|^2}$ implies $|A-A|=\Omega(n^{4/3})$. $\Box$

# The 2nd Elbe Sandstones Geometry Workshop

I’ve been quiet for a couple of weeks because I am doing some traveling. My first stop was The 2nd Elbe Sandstones Geometry Workshop. This workshop had an interesting location — a mountain in the middle of nowhere in the Czech Republic. Here is a picture of most of the participants.

The 1st Elbe Sandstones Geometry Workshop took place 13 years ago. Following is a picture from there, in front of the same door (it is also the only picture I ever saw of Micha Sharir without a beard).

# Random Stories from IPAM – Part 2

If you are not in Los Angeles but are interested in these topics, you can now view videos of many of the talks that we had here. Talks from the tutorials week can be found here. Talks from the workshop “Combinatorial Geometry Problems at the Algebraic Interface” can be found here. I assume that talks from the workshop “Tools from Algebraic Geometry” will also be available soon.

A talk by Joseph Landsberg.

Another brief update: You might remember that in my previous IPAM post I was excited about a talk by Larry Guth. Not only that you can now watch the video of this talk, but you can also read the paper.

And now for quote of the week:

It is like defining a ham sandwich as “what you have in your lunchbox after taking the apple out”.

Ben Lund, unsatisfied with a famous textbook’s definition of Grassmannians.

After three weeks without any main events, another workshop begins tomorrow. So more updates will follow.

# Random Stories from IPAM – Part1

Since my previous post, I moved from freezing New York to sunny LA. I am participating in a semester on Algebraic Techniques for Combinatorial and Computational Geometry, at the IPAM institute. The lack of posts on the blog in the past several weeks is due to the constant activities and the large number of interesting people to interact with. This post contains some random stories from my stay at IPAM.

During pie day (March 14th), all of the food served in IPAM was round.

So far the main events were a week of tutorials and another week consisting of a workshop about “Combinatorial Geometry Problems at the Algebraic Interface”. These contained many interesting talks, which were also videotaped. Once the videos will be online, I will post a link in the blog. Here I only mention one talk which gave me quite a surprise – Larry Guth‘s talk.

At the beginning of his talk, Larry stated that he will present a significantly simpler variant of part the distinct distances proof (the one by Katz and himself). You might remember that, using the Elekes-Sharir framework, the distinct distances problem is reduced to a point-line incidences problem in ${\mathbb R}^3$: Given a set of $n$ lines, such that every point is incident to at most $O(\sqrt{n})$ of the lines and that every plane and regulus contain at most $O(\sqrt{n})$ of the lines, what is the maximum number of points that can be incident to at least $k$ of the lines (where $2\le k \le \sqrt{n}$). Larry’s new technique proves the following slightly weaker incidences bound.

Theorem (Guth `14). Consider a set $\cal L$ of $n$ lines in ${\mathbb R}^3$, so that any surface of degree at most $c_\varepsilon$ (a constant that depends only on $\varepsilon$) contains at most $\sqrt{n}$ lines of $L$. Then for any $\varepsilon>0$ and $2 \le r \le \sqrt{n}$, the number of points of ${\mathbb R}^3$ that are contained in at least $r$ lines of $L$ is $O(\frac{n^{3/2+\varepsilon}}{r^2}).$

The surprising part is that the new proof was based on constant sized partitioning polynomials (on which I plan to write a couple of expository posts, as part of my expository series about the polynomial method). When using such polynomials for problems of this sort, one encounters a difficultly. It is hard to describe this difficulty without first explaining the technique, but my impression is that this difficulty was the main issue in various other recent incidences-related projects, and that now we might see various other works that rely on Larry’s technique. In his talk, Larry also mentioned that this technique can work for other types of curves, which immediately implies a series of improved point-curve incidence bounds in ${\mathbb R}^3$.

A talk by Tao in IPAM. How many of the mathematicians in the audience can you recognize?

And for something completely different: I had an issue with my visa, and was told that I should exit and reenter the country. This resulted in a 13-hour bus trip to Tijuana and back to LA. My only souvenir from this trip is the following picture of a pharmacy for people that are waiting in line to enter the US. I wonder sort of things people buy at a pharmacy while waiting to go through immigration…

There’s a lot more to tell, so more IPAM stories later on.