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.

Micha

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.

Updates

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 🙂

MSRI

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.

IMG-0217.JPG

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!

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.

dls

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.

Opening

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…)

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

P1000140

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

rynarice

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.

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