The Elekes-Szabó Problem

Consider an NxN grid. Now consider a line crossing this grid. What is the maximum number of points that the line can hit? This is not a particularly difficult question; the answer is N and you can see this by sketching a few pictures. What if we increase the dimension of our objects by one? So consider an NxNxN grid and a plane crossing the grid. How many grid points can the plane contain? The answer is N, as we may choose the plane to be parallel to one of the coordinate axes. The latter question is fairly simple, but by modifying the setup of the question slightly, we arrive at some interesting and highly influential mathematics. We may consider changing the question by replacing the plane with some other more complex surface. In particular, the surface should be defined to be the set of solutions to a polynomial that is sufficiently complicated, or non-degenerate. If we insist that the surface arises from a non-degenerate polynomial then it turns out that the number of grid points the surface can hit is significantly smaller than N. A more precise version of this statement is known as the Elekes-Szab Theorem. The Elekes-Szab Theorem is very general, and this allows for many opportunities to use it. It has been a major driving force for problems in discrete geometry in the last two decades. In particular, it has been used to prove several new results concerning the number of distances determined by sets of points in the plane. Recent developments have seen more applications of this theorem to the sum-product problem. Sum- product theory, very roughly speaking, is concerned with showing that a set of numbers cannot be highly structured in both an additive and multiplicative sense. One may think of an arithmetic progression as an example of an additive structured set. This set is defined by addition (we determine the next element of the set by adding a fixed number to the previous one). Intuitively, it is an additively structured set. One can give several different measures for quantitatively determining how additively structured a set is, and for all of these measures, the arithmetic progression scores highly. Conversely, a prototypical example of a multiplicatively structured set is a geometric progression, where we move from one element to the next by multiplying by a fixed value. However, it seems to be impossible to construct a set which is structured in both of these ways at the same time. A wide-open conjecture of Erdos and Szemerédi describes this idea more precisely, and this is one of the major open problems in combinatorial number theory. In this project, some of the key goals are: Find new applications of the Elekes-Szab Theorem, particularly in sum-product theory. Extend the Elekes-Szab Theorem to hold in other settings. Make it easier for the Elekes-Szab Theorem to be applied. In particular, find an efficient way to compute whether a given polynomial is non-degenerate.