July 19, 2017 by Adam Sheffer

Incidences in Higher Dimensions: A Conjecture

I recently added to the incidence theory book two chapters about incidences in ${\mathbb R}^d$ (Chapters 8 and 9). At the moment incidence bounds in ${\mathbb R}^d$ are known for several different cases, and it is rather unclear how a general incidence bound in ${\mathbb R}^d$ should look like. In this post I would like to state what I believe this bound should look like. This conjecture is in part a result of conversations with Joshua Zahl over several years (I do not know whether Josh agrees with everything in this post). The post assumes some familiarity with incidence problems.

zahl_photo
Joshua Zahl. A common name in this blog.

Let us start by stating some known bounds for incidences in ${\mathbb R}^d$ . The first general incidence bound that relied on polynomial techniques was by Solymosi and Tao.

Theorem 1. Let ${\cal P}$ be a set of $m$ points and let ${\cal V}$ be a set of $n$ varieties, both in ${\mathbb R}^d$ . The varieties of ${\cal V}$ are of degree at most $k$ and dimension at most $d/2$ . The incidence graph of ${\cal P}\times {\cal V}$ contains no copy of $K_{s,t}$ . Also, whenever two varieties $U_1,U_2 \in {\cal V}$ are incident to a point $p\in {\cal P}$ , the tangent spaces of $U_1$ and $U_2$ at $p$ intersect at a single point. Then for any $\varepsilon>0$

$I({\cal P},{\cal V}) = O_{k,s,t,d,\varepsilon}\left(m^{\frac{s}{2s-1}+\varepsilon}n^{\frac{2s-2}{2s-1}}+m+n\right).$

While Theorem 1 provides a nice incidence bound, the varieties in it are somewhat restricted. A result of Fox et al. holds for varieties of any dimension and without the restriction on the tangent spaces, at the cost of having a weaker bound.

Theorem 2. Let $\cal P$ be a set of $m$ points and let $\cal V$ be a set of $n$ varieties of degree at most $k$ , both in ${\mathbb R}^d$ . Assume that the incidence graph of ${\cal P}\times {\cal V}$ contains no copy of $K_{s,t}$ . Then for any $\varepsilon>0$

$I({\cal P},{\cal V}) = O_{k,s,t,d,\varepsilon}\left(m^{\frac{(d-1)s}{ds-1}+\varepsilon}n^{\frac{d(s-1)}{ds-1}}+m+n\right).$

Finally, a result of Sharir et al. provides a stronger bound for the special case of varieties of dimension one that do not cluster in a low degree surface (for brevity, the following is a simplified weaker variant).

Theorem 3. For every $\varepsilon>0$ there exists a constant $c_\varepsilon$ that satisfies the following. Let $\cal P$ be a set of $m$ points and let $\cal V$ be a set of $n$ irreducible varieties of dimension one and degree at most $k$ , both in ${\mathbb R}^d$ . Assume that the incidence graph of ${\cal P}\times {\cal V}$ contains no copy of $K_{s,t}$ , and that every variety of dimension two and degree at most $c_\varepsilon$ contains at most $q$ elements of $\cal V$ . Then

$I({\cal P},{\cal V}) = O_{k,s,t,d,\varepsilon}\left(m^{\frac{s}{ds-d+1} +\varepsilon}n^{\frac{ds-d}{ds-d+1}} + m^{\frac{s}{2s-1}+\varepsilon}n^{\frac{ds-d}{(d-1)(2s-1)}}q^{\frac{(s-1)(d-2)}{(d-1)(2s-1)}}+m+n\right).$

The incidence theory book describes in detail how to prove the three above bounds. With these result in mind, we are now ready to make a somewhat vague general conjecture.

Conjecture 4. Let $\cal P$ be a set of $m$ points and let $\cal V$ be a set of $n$ varieties of degree at most $k$ and dimension $d'$ , both in ${\mathbb R}^d$ . Assume that the incidence graph contains no copy of $K_{s,t}$ and that the varieties of $\cal V$ satisfy some “reasonable conditions”. Then for any $\varepsilon>0$

$I({\cal P},{\cal V}) = O_{k,s,t,d,\varepsilon}\left(m^{\frac{sd'}{ds-d+d'}+\varepsilon}n^{\frac{ds-d}{ds-d+d'}} + m + n\right).$

Note that we already have three cases of conjecture 4:

Theorem 1 obtains the conjecture for varieties of dimension $d/2$ .
Theorem 2 obtains the conjecture for varieties of dimension $d-1$ .
Theorem 3 obtains the conjecture for varieties of dimension $1$ .

For varieties of dimension smaller than $d/2$ , the proof of Theorem 1 projects the configuration to a space of dimension that is twice the dimension of the varieties (forcing the dimension of the varieties to be exactly half the dimension of the space). This seems to be an inefficient step, which makes it likely that the theorem is not tight for varieties of dimension smaller than $d/2$ . Indeed, Theorem 3 already obtains a stronger bound for the case of varieties of dimension one. For similar reasons, the proof of Theorem 2 seems not to be tight for varieties of dimension smaller than $d-1$ .

A recent work reduces the distinct distances problem in ${\mathbb R}^d$ to an incidence problem between points and $(d-1)$ -dimensional planes in ${\mathbb R}^{2d-1}$ . Combining this reduction with the bound stated in Conjecture 4 would lead to an asymptotically tight bound for the distinct distances problem in dimension $d\ge3$ . Other problems also reduce to incidence problems with the same dimensions. Thus, the case of $d' = (d-1)/2$ (for odd $d$ ) seems to be a main open case.

While conjecture 4 is known for the cases of varieties of dimension $1,d/2$ , and $d-1$ , so far all of the other cases are open. The bound in the conjecture was not obtained by interpolating the three known cases — there is a better approach that leads to it. Recall that in the polynomial partitioning technique we partition ${\mathbb R}^d$ into cells, bound the number of incidences in each cell, and then bound the number of incidences that are on the partition (not in any cell). The bound stated in Conjecture 4 is obtained by applying this technique while ignoring the incidences on the partition (since bounding the number of incidences in the cells is much easier).

Recently discovered configurations of points and varieties achieve the bound of the conjecture up to extra $\varepsilon$ ‘s in the exponents. Thus, in its most general form the bound of the conjecture is tight. However, these constructions give a tight bound only for certain families of varieties of dimension $d-1$ , for certain ranges of $m$ and $n$ , and when $s=2$ . It seems plausible that the bound of the conjecture is not tight in some other interesting cases. In particular, in ${\mathbb R}^2$ a stronger bound is already known when $s\ge 3$ , and it seems reasonable that the same technique would also work for varieties of dimension one in ${\mathbb R}^d$ . At the moment, it is difficult to guess what should happen with varieties of dimension larger than one. Either way, Conjecture 4 seems to be a reasonable bound for the limits of the current polynomial partitioning technique. It seems that this specific technique could not yield better bounds without major changes.

Let us briefly discuss what the expression “reasonable conditions” in the statement of Conjecture 4 means. We already have two examples of conditions that are considered reasonable:

A non-clustering condition: Not too many varieties of $\cal V$ are contained in a common higher-dimensional variety. For example, this restriction was used in Theorem 3, and more famously in the Guth–Katz proof of the planar distinct distances problem.
A transversality condition: When two varieties meet at a point $p$ , their tangent spaces at $p$ intersect only at one point. This condition was used in Theorem 1.

It is not clear what the “natural” restrictions are. For example, when studying incidences with two-dimensional planes in ${\mathbb R}^4$ most works rely on the transversality condition. In this case, the condition is equivalent to asking every two planes to intersect in at most one point. I recently noticed that the same incidence bound holds with a much weaker restriction of not too many planes in a hyperplane.

There is more to say about Conjecture 4, but this post is already getting longer than I intended.

March 31, 2017 by Adam Sheffer

A First Draft of the Book “Incidence Theory”

You might have noticed that I did not post anything new for quite a while. The past months were unusually busy for me, due to personal reasons such as having my first child born(!), being on the job market, and several other things. I hope to return to my regular posting frequency around July.

The purpose of this post is to announce that I just uploaded the first draft of my book “Incidence Theory”. This book is about our current understanding of incidences (with a focus on the polynomial method), and their applications in other fields. I am trying to achieve two goals in this book: To have a clear and basic introduction of this subfield, while also creating a repository of results and techniques which may be used as a reference to experts. The current draft already contains several folklore results that I have not seen written before. It contains only the first seven chapters. I predict that the final version would contain about 15 chapters, and plan to gradually release the remaining ones.

Comments would be very appreciated, preferably by email. These can point out mistakes, typos, unclear formulations, suggestions for style changes, additional topics, simpler arguments, exercises, or anything else that might help improve the draft. The acknowledgements section is way too short. Please help me to extend it!

July 10, 2016 by Adam Sheffer

The Sum-Product Bound of Konyagin and Shkredov

In Solymosi’s famous 2009 paper, he proved that every finite set $A\subset {\mathbb R}$ satisfies

$|A+A||AA| = \Omega\left(|A|^{4/3}/\log^{1/3}|A|\right).$

In the past couple of years, Konyagin and Shkredov published two papers that extend Solymosi’s argument, obtaining a slightly stronger sum-product bound (one and two). These papers derive several additional results, and apply a variety of tools. I just uploaded to this blog my own exposition to the sum-product proof of Konyagin and Shkredov (a link can also be found in the pdf files page). This exposition ignores the additional results that are in the two papers, and tries to explain in detail every step that is part of the sum-product proof. In this aspect, the document would hopefully also fit beginners. As usual, I’m happy to receive any comments and corrections.

Ilya Shkredov and Sergei Konyagin.

April 7, 2016 by Adam Sheffer

Additive Combinatorics Lecture Notes

I recently started teaching an “Additive combinatorics” class, and am writing lecture notes for it. So far I put the first three chapters online. I’d appreciate any comments about these, from pointing out serious mistakes, to pointing out minor typos, or even a recommendation for the final topic (which I have not chosen yet). The chapters that are already up are:

In Chapter 1 we start to study the principle that sets with small doubling must have structure. We prove some basic results such as Ruzsa’s triangle inequality, Plünnecke’s inequality, and variants of Freiman’s theorem.
Chapter 2 studies the sum-product problem over the reals. In addition to showing the proofs of Elekes and Solymosi, we see how the same techniques can be applied to several other problems.
Chapter 3 discusses the The Balog-Szemerédi-Gowers theorem. Specifically, we present the variant of Schoen and the variant by Sudakov, Szemerédi, and Vu.

As the quarter progresses, I will keep uploading more chapters.

September 30, 2015 by Adam Sheffer

John von Neumann by Norman Macrae

So far, in my posts I have only written about popular science books that I liked. In this post I am making an exception, writing a rather negative review for a book that somewhat bothered me. I hope that writing such a post is not a big mistake. I guess I’ll soon find out…

John von Neumann.

This post is about the biography of the mathematician John von Neumann by Norman Macrae. Perhaps I should start by stating that this is not really a popular science book, in the sense that it seems to avoid any discussion that is even a bit technical. The mathematical research of Von Neumann is stated very vaguely, and one mostly finds statements such as “… number theory, a branch of mathematics that is at once fascinating and frustrating” without any further details. When mentioning various scientists, the focus is usually about anecdotes, political opinions, and how smart they were. This last point usually involves some sort of ranking. According to Macrae, Aristotle was definitely smarter than Von Neumann, which was in turn smarter than any other mathematician of the 20th century. As another example, Von Neumann’s tutor Gabor Szego “was later to become one of the half dozen most distinguished Hungarian mathematicians of the twentieth century.” No explanation is provided for what these rankings are based on (occasionally they appear together with a statement by one person saying that another is very smart).

After reading my previous paragraph, you might claim that having a non-scientific biography of a mathematician can be a good thing, especially for readers who are not mathematicians. So instead of describing what the book does not contain, I now move to describe what it does. One thing that the book is filled with is strong opinions by the author, sometimes stated as facts. These opinions concern which government systems are better, which countries have the best school systems (apparently Japan is at the top), various historical speculation (“If Haber had not found a way to fix nitrogen from the air to make nitrates for explosives, blockaded Germany would have had to surrender from the 1914-18 war in about 1915”), among other topics. Some of these opinions concern someone being right or wrong about a subjective issue, without any further explanation (“… Eckert, whom in 1945 he rightly still wanted in his Princeton project as chief engineer”).

There are two contexts in which I found this abundance of opinions rather problematic. The first is when they appear in relation to mathematics or other exact sciences. My possibly-false impression is that Macrae does not have much of a scientific background. This is of course fine, and many wonderful popular science books were written by non-scientists. However, it makes Macrae’s many unusual assertions about science seem rather awkward. For example, after mentioning how important Von Neumann was to the development of mathematics comes the sentence “happily, and this is not sufficiently realized, it should be possible to get more like him”. The following sentence then explains that this is due to the lower financial needs of a mathematician (that is, paper and pencil). Claiming that von Neumann had a wider conception about computers, Macrae writes “He did not envisage these machines as today’s glorified typewriters. He hoped that experimenting scientists could use computers to start scientific revolutions that would change the planet.” Many such statements gave me a somewhat awkward feeling while reading the book.

The second case in which I found the many opinions in the book somewhat troubling is in the context of people with left-wing opinions. The book is PACKED with anti-left-wing statements, sometime without any visible connection to Von Neumann. One example (that also involves an awkward “technical” statement) is “He thought that those who believed in communism or socialism deserved the same sympathy as other simpletons who could not understand even linear equations.” After mentioning that various scientists supported Stalin or did not sufficiently oppose Hitler, Macrae writes “A common feature of clever men who occasionally supped on too-short spoons with Nazism or Communnism was that as kids they had never adequately learned to laugh”. It is clear that Macrae feels strongly about the subject, as the book contains statements such as “Among people who wanted to believe optimistic nonsense about western Europe or Soviet Russia…” and “… speaks in volumes to those who want to hear.” Such statements appear throughout the book and are possibly the most common topic that is discussed. Often such opinions are attributed to Von Neumann, although almost never with a reference or an actual quote (unlike many of Von Neumann’s statements on other topics). In fact, one finds sentences such as “I cannot find anything in his papers that suggests that he advocated that, although a lot of honest people thought that he did.”

Another issue is the extreme glorification of Von Neumann. I don’t think that many people doubt that Von Neumann was a genius that made a large impact on many fields, but the book takes this to the next level. It actually contains statements such as “the cleverest man in the mathematical world” and “Because Johnny was the world’s leading mathematical logician, he could clearly improve its logical design” (of the EDVAC computer).

I have more to say but I probably wrote too much already, so let me conclude this post. If you would like to hear how the smartest man of the 20th century had hawkish opinions, and that these were much better than all of those silly left-wing scientists such as Einstein, definitely read Macrae’s book. Personally I would appreciate a recommendation for a more standard biography of Von Neumann.

September 10, 2015 by Adam Sheffer

Incidences: Lower Bounds (part 7)

In this post we continue our survey of the known lower bounds for incidence problems (click here for the previous post in the series). In the current post we finally start discussing incidences with objects of dimension larger than one. The simplest such case seems to be incidences with unit spheres in ${\mathbb R}^3$ (i.e., spheres of radius one). We present two rather different constructions for this case. I am not aware of any paper that describes either of these constructions, and they appear to be folklore. If you are aware of a relevant reference, I will be happy to hear about it.

First construction: Inverse gnomonic projection. Our first construction is based on lower bounds for the Szemerédi-Trotter problem (e.g., see the first two posts of this series). It shows that $m$ points and $n$ unit spheres in ${\mathbb R}^3$ can yield $\Omega(m^{2/3}n^{2/3}+m+n)$ incidences.

For the requested values of $m$ and $n$ , consider a set $\cal P$ of $m$ points and a set $\cal L$ of $n$ lines, both in ${\mathbb R}^2$ and with $I({\cal P},{\cal L})=\Theta(m^{2/3}n^{2/3}+m+n)$ . We place this plane as the $xy$ -plane in ${\mathbb R}^3$ . We then perform an inverse gnomonic projection that takes $\cal P$ and $\cal L$ to a sphere in ${\mathbb R}^3$ , as follows. We set $p=(0,0,1/\sqrt{2})$ and denote by $S$ the sphere that is centered $p$ and is of radius $1/\sqrt{2}$ . Notice that $S$ is tangent to the $xy$ -plane at the origin. The inverse projection takes a point $q$ in the $xy$ -plane to the intersection point of the line segment $pq$ and $S$ . One can easily verify that this mapping is a bijection between the $xy$ -plane and the lower half of $S$ ; e.g., see the following figure.

Continue reading →

May 4, 2015 by Adam Sheffer

Polynomial Method Lecture Notes #2

Following my previous post, this is an update about my lecture notes for the “polynomial method” class that I am currently teaching. In the last post I briefly described the first three chapters of the lecture notes. Since then, four more chapters are already online and another will be uploaded in the next couple of days. The new chapters are:

Chapter 4 describes the constant-degree polynomial partitioning technique, which was introduced by Solymosi and Tao. This technique is useful for deriving incidence bounds in higher dimensions. We prove the complex Szemerédi–Trotter theorem using this technique. (I plan to discuss more recent techniques for handling incidences in higher dimensions in a later chapter.)
Chapter 5 consists of a short proof for the joints theorem.
Chapter 6 describes the Elekes-Sharir-Guth-Katz framework, which reduces the distinct distances problem to a problem involving line intersections in ${\mathbb R}^3$ .
Chapter 7 revolves around incidences with lines in ${\mathbb R}^3$ . This is a main step in the proof of Guth and Katz’s distinct distances theorem. The proof of this theorem is completed in Chapter 8.

I am happy to receive corrections and suggestions for improvement. Once again, many thanks to Frank de Zeeuw, for providing a lot of great feedback!

	(More) Local Propert… on Local Properties that imply Ma…
	Adam Sheffer on An End to the Happy Ending…
	bob on An End to the Happy Ending…
	Adam Sheffer on Additive Combinatorics Lecture…
	Brendan Murphy on Additive Combinatorics Lecture…

Some Plane Truths

Discrete geometry and other typos

Uncategorized