Uncategorized

by

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!

by

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.

konyaginIlya-00
Ilya Shkredov and Sergei Konyagin.

by

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.

by

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…

JohnvonNeumann-LosAlamos
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.

by

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.

Gnomonic

Continue reading →

by

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!

by

Polynomial Method Lecture Notes

I recently started teaching a “polynomial method” class, and I’m trying to write detailed 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 just to ask about things that are not so clear. The chapters that are already up are:

  • Chapter 1 surveys some classical discrete geometry, and is an introduction to incidences, unit distances, distinct distances, etc.
  • Chapter 2 introduces some of the basic real algebraic geometry that will be required in the following chapters. It defines basic concepts such as varieties, dimension, degree, and singular points.
  • In chapter 3 we finally start to talk about the polynomial method itself. We introduce the technique of polynomial partitioning and show how to use it to derive incidence bounds.
Chapter 4, about constant-sized polynomial partitioning, is more or less written and should be online soon. I have already received many useful comments from Frank de Zeeuw, who is teaching a similar course in EPFL. Many thanks Frank!