A structural Szemerédi–Trotter Theorem for Cartesian Products^††thanks: This research project was done as part of the 2020 NYC Discrete Math REU, supported by NSF awards DMS-1802059, DMS-1851420, DMS-1953141, and DMS-2028892.

The Szemerédi–Trotter theorem [24] is a central result in discrete geometry. The many variants and generalizations of this theorem are now considered as an entire subfield. The Szemerédi-Trotter theorem and its variants have a wide range of applications, in combinatorics, harmonic analysis, theoretical computer science, number theory, model theory, and more (for example, see [2, 3, 4, 14, 22]). It is thus awkward that hardly anything is known about the cases where this theorem is asymptotically tight.

Let $\mathcal{P}$ be a set of points and let $\mathcal{L}$ be a set of lines, both in $\mathbb{R}^{2}$. An incidence is a pair $(p,\ell)\in\mathcal{P}\times\mathcal{L}$, such that the point $p$ is on the line $\ell$. We denote the number of incidences in $\mathcal{P}\times\mathcal{L}$ as $I(\mathcal{P},\mathcal{L})$. The Szemerédi–Trotter theorem provides an asymptotically tight upper bound for $I(\mathcal{P},\mathcal{L})$.

The structural Szemerédi–Trotter problem asks to characterize the point–line configurations that have an asymptotically maximal number of incidences. We focus on sets of $n$ points and $n$ lines that form $\Theta(n^{4/3})$ incidences. Most of our results can be extended to $m$ point and $n$ lines.

Around the middle of the 20th century, Erdős [9] discovered a configuration of $n$ points and $n$ lines that form $\Theta(n^{4/3})$ incidences. In this construction, the point set is a $\sqrt{n}\times\sqrt{n}$ section of the integer lattice $\mathbb{Z}^{2}$. In the early 2000s, Elekes [8] discovered a simpler configuration of $n$ points and $n$ lines that form $\Theta(n^{4/3})$ incidences. In Elekes’s configuration, the point set is an $n^{1/3}\times n^{2/3}$ section of the integer lattice $\mathbb{Z}^{2}$.

To obtain more point-line configurations, we can take one of the above configurations and perform transformations that preserve most of the incidences. We can apply projective transformations, point–line duality, remove some points and lines, and add additional points and lines. Up to such transformations, the only known configurations with $\Theta(n^{4/3})$ incidences were Erdős’s and Elekes’s. This led to questions such as

• •

  Are these the only two configurations?

• •

  If there are more configurations, are there only sporadic configurations? Or is there an infinite family of configurations with continuous parameters?

• •

  Up to the above transformations, is the point set always a lattice?

• •

  What properties must the set of lines satisfy?

Hardly anything is known about such structural questions. The only non-trivial result that we are aware of is by Solymosi [23].

A recent result of Mirzaei and Suk [15] can be seen as quantitative variant of Theorem 1.2, for specific types of subgraphs. A recent result of Hanson, Roche-Newton, and Zhelezov [12, Theorem 1.8] considers the case where the point set is $A\times A$, where $A$ is a set of rational numbers with a very small product set. They show that, in this case, the number of incidences is significantly smaller than $n^{4/3}$.

For a proof of Theorem 1.3 and additional details, see Section 4. This family of constructions answers some structural questions and leads to new ones. For example, in all of the constructions of this family, there are $\Theta(n^{1/3})$ families of $\Theta(n^{2/3})$ parallel lines. We wonder whether there exist configurations with $\Theta(n^{4/3})$ incidences that do not have this property, possibly after applying some transformations.

A follow-up work by Larry Guth and the second author [11] provides constructions where the point set is a Cartesian product of generalized arithmetic progressions. This prompts the question: Do all configurations consist of a Cartesian product of sets with a small sum set? For the definition of a sum set and more information, see Section 3.

We derive properties of the set of lines in the case where the point set is a Cartesian product. Part (b) of the this result relies on additive and multiplicative energies. For a definition of these energies, see Section 3.

We can think of Theorem 1.4(b) as another split into two cases: Either the set of slopes has a large multiplicative energy or many sets of $y$-intercepts have large additive energies. More intuitively and less accurately, either the set of slopes is somewhat similar to a geometric progression, or many sets of $y$-intercepts are somewhat similar to arithmetic progressions. In all of the configurations that we are aware of, there are $\Theta(n^{1/3})$ sets of $\Theta(n^{2/3})$ parallel lines, the energy $E^{\times}(S)$ is small, and the sets of $y$-intercepts have large additive energies. One possibility is that all of the constructions have these properties. For more information, see Section 4.

For the proof of Theorem 1.4, see Section 5. A follow-up work of the first author and Junxuan Shen [20] shows that, for lattices and several other cases, the concurrent case of Theorem 1.4(a) cannot happen. Thus, if the concentric case can happen, then it takes place with very different point sets.

The current work contains several additional related results, which are stated in the part titled Additional results below.

Elekes [5, 6, 7] considered a line $\ell$ that is defined by $y=ax+b$ as the linear function $f_{\ell}(x)=ax+b$. He was then able to compose lines and to consider the inverse of a line. This allowed Elekes to derive new combinatorial properties of lines. Recently, Rudnev and Shkredov [17] further developed Elekes’s ideas. Given a set $\mathcal{L}$ of non-axis-parallel lines, they consider the quantity

We refer to this quantity as the line energy of $\mathcal{L}$ and denote it as $E(\mathcal{L})$. A detailed and rigorous discussion of line energy can be found in Section 3.

Rudnev and Shkredov derived an interesting connection between point-line incidences and line energy.

Rudnev and Shkredov also derived upper bounds for $E(\mathcal{L})$. The following upper bound was derived afterwards by Petridis, Roche-Newton, Rudnev, and Warren [16].

The paper [16] contains a dual formulation of Theorem 1.6. When reading that dual formulation, it may seem as if we need to add the term $m|\mathcal{L}|^{2}$ to the bound of Theorem 1.6. However, since $m\leq|\mathcal{L}|$, we have that $m|\mathcal{L}|^{2}\leq m^{1/2}|\mathcal{L}|^{5/2}$.

Elekes [7] studies lines that contain many points of a Cartesian product.

Petridis, Roche-Newton, Rudnev, and Warren [16] derived a quantitative variant of Theorem 1.8.

While Theorems 1.8 and 1.9 seem similar to Theorem 1.4, there are several significant differences between these two structural problems. First, it is not difficult to find a configuration that satisfies the concurrent case of Theorem 1.8. On the other hand, it is plausible that the concurrent case of Theorem 1.4 does not exist.

To see another difference between the two above scenarios, we apply Theorem 1.9 to the structural problem of Theorem 1.4. When $n$ points and $n$ lines form $\Theta(n^{4/3})$ incidences, those incidences originate from $\Theta(n)$ lines that are incident to $\Theta(n^{1/3})$ points (see the proof of Lemma 5.1 below). In our case there are $|A|^{2}=n^{2}$ points, so $\Theta(n^{2})$ lines are incident to $\Theta(n^{2/3})$ points. That is, $k=n^{2}$ and $\alpha=\Theta(n^{-1/3})$. Then, Theorem 1.9 leads to the trivial statement that there exist $\Omega(1)$ parallel lines. While the two structural problems have a different behavior, the proofs of Theorem 1.9 and of Theorem 1.4(a) both rely on Theorem 1.5 and Theorem 1.6.

We introduce a variant of Theorem 1.9 that does lead to interesting results in the case of $\Theta(n^{4/3})$ incidences. This variant is in the style of Theorem 1.4(b). By the pigeonhole principle, there exists $0\leq\beta\leq 1$ such that $\mathcal{L}$ contains $\Omega(k^{1-\beta}/\log k)$ families of $\Theta(k^{\beta})$ parallel lines, each with a different slope. We provide an upper bound on $k$ in terms of the multiplicative energy of these slopes and of the additive energy of their $y$-intercepts.

The statement of Theorem 1.10 is long and technical, but it also has a simple intuition: If many lines are incident to many points of $A\times A$, then the slopes have a large multiplicative energy or the $y$-intercepts of many parallel families have large additive energies. For a proof of Theorem 1.10, see Section 6.

To see that Theorem 1.10 provides a reasonable bound in the case of $\Theta(n^{4/3})$ incidences, we consider Erdős’s construction with $n^{2}$ points and lines (see for example [19]). Like all of the known constructions, the set of lines contains $n^{2/3}$ families of $n^{4/3}$ parallel lines. Each of those lines forms $\Theta(n^{2/3})$ incidences, so $\alpha=n^{-1/3}$. A simple variant of our proof of Lemma 4.1 shows that $E^{\times}(S)=O(n^{4/3+{\varepsilon}})$, for every ${\varepsilon}>0$. The sets of $y$-intercepts are arithmetic progressions, so $t=\Theta(n^{4})$. Plugging this into Theorem 1.10 leads to the bound $k=O(n^{25/12+{\varepsilon}})$. This is not far from the correct bound $k=\Theta(n^{2})$, so Theorem 1.10 cannot be significantly improved.

For the opposite case of Theorem 1.10, we set $A=\{2^{0},2^{1},2^{2},\ldots,2^{n-1}\}$ and consider the lines that are defined by $y=2^{j}\cdot x$ with $j\in\{0,1,2,...,n/2\}$. In this case, there are $k$ families of a single parallel line, so $t=1$. Every line contains $\Theta(n)$ points of $A\times A$, so $\alpha=\Theta(1)$. The line slopes form a geometric progression, so $E^{\times}(S)=\Theta(n^{3})$. Plugging the above into Theorem 1.10 leads to the bound $k=O(n\log^{3}n)$, which is tight up to the polylogarithmic factor.

Many of the results in this paper can be extended to other fields, to $m$ points and $n$ lines, and to other problems.

In this section we introduce a few tools that we use in our proofs. We suggest to quickly skim this section and return to it when necessary.

The following lemma collects a few basic properties of the totient function.

In this section we describe line energy in more detail. We begin with a brief description of additive and multiplicative energies. An expert reader may wish to skip this part.

After fixing the values of $a,b$, and $c$, at most one $d\in A$ satisfies $a+b=c+d$. This implies that $E^{+}(A)\leq|A|^{3}$. By considering the case where $a=c$ and $b=d$, we get that $E^{+}(A)\geq|A|^{2}$.

Additive energy is a central object in additive combinatorics. Intuitively, it provides information about the structure of $A$ under addition. We now consider one example of this. For $x\in\mathbb{R}$, we define

Since every pair from $A^{2}$ contributes to exactly one $r_{A}^{+}(x)$, we have that $\sum_{x\in\mathbb{R}}r_{A}^{+}(x)=|A|^{2}$. For a fixed $x\in\mathbb{R}$, the number of solutions from $A$ to $a+b=c+d=x$ is $r_{A}^{+}(x)^{2}$. This implies that $E^{+}(A)=\sum_{x}r_{A}^{+}(x)^{2}$. Then, the Cauchy-Schwarz inequality leads to

Thus, a small sum set implies a large additive energy. In particular, if $|A+A|=\Theta(|A|)$ then $E^{+}(A)=\Omega(|A|^{3})$.

For finite $A,B\subset\mathbb{R}$, we define the additive energy of $A$ and $B$ as

We can rearrange the above condition as $a-c=d-b$. Then, the Cauchy-Schwarz inequality implies that

The product set of $A$ is

The multiplicative energy of $A$ is

Product sets and multiplicative energies are similar to sum sets and additive energies. For example, a small product set implies a large multiplicative energy. Intuitively, a set with a small product set is similar to a geometric progression.

The set of non-axis-parallel lines under the above composition form the affine group of $\mathbb{R}$. However, for our purposes, we prefer to think of the group elements as lines in $\mathbb{R}^{2}$. We also associate a line $\ell$ that is defined by $y=cx+d$ with the point $(c,d)\in\mathbb{R}^{2}$. We refer to the plane that contains $\ell$ as the primal plane and to the plane that contains $(c,d)$ as the dual plane. With this dual notation, the group operation is

The identity element is $(1,0)$ and the inverse of $(c,d)$ is $(1/c,-d/c)$. This group is non-commutative. For example, we have that

We define the line energy of a set of lines $\mathcal{L}$ as

When writing $f_{\ell_{j}}=c_{j}x+d_{j}$, we also have the dual formulation

Rudnev and Shkredov [17] refer to $E(\mathcal{L})$ as an energy, but do not give it an explicit name. The recent paper [16] refers to $E(\mathcal{L})$ as affine energy, because of its connection with the affine group. We use the name line energy, since think of $E(\mathcal{L})$ as a property of a set of lines.

We note that

Since we only consider non-axis-parallel lines, $c\neq 0$ and the above is well-defined. A quadruple $(\ell_{1},\ell_{2},\ell_{3},\ell_{4})\in\mathcal{L}^{4}$ contributes to $E(\mathcal{L})$ if and only if

Simplifying leads to the system

In this section we prove Theorem 1.3 and Theorem 1.7. We first recall the statement of each theorem.