an improved bound on the number of dot products determined by a finite point set in the plane
Michalis Kokkinos · 2025
Read an improved bound on the number of dot products determined by a finite point set in the plane by Michalis Kokkinos (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-12727.txt.
Introduction
Michalis Kokkinos improves the lower bound on how many distinct dot products a finite planar point set must determine. The paper from twenty twenty-five sits in incidence geometry, where the question is how much structure a point set forces. Dot products between pairs of points can coincide, but not too often. Building on work by Hanson, Roche-Newton, and Senger, Kokkinos raises the guaranteed count.
The gain is a small extra exponent over the known two-thirds power of the set size. Such increments are hard won in this field, where each shave of the exponent takes new incidence ideas. The proof is a short note, with the bound as its whole payload. It serves the distance and dot product family of problems in discrete geometry.
Catalog record
| CREATOR | Michalis Kokkinos |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 11 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-12727
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
an improved bound on the number of dot products determined by a finite point set in the plane Michalis Kokkinos Abstract . We are interested to bound from below the number of distinct dot products determined by a finite set of points P P in the Euclidean plane. In this paper, we build on [ 3 ] to obtain the improved lower bound | { p ⋅ q : p , q ∈ P } | ≳ | P | 2 3 + 7 1425 . |\{p\cdot q\mathrel{\mathop{\mathchar 58\relax}}p,q\in P\}|\gtrsim|P|^{\frac{2}{3}+\frac{7}{1425}}. 1991 Mathematics Subject Classification 52C10, 11B30 1. Introduction Let P\subseteq\mathbb{R}^{2} be a finite set of points in the Euclidean plane. We define \Lambda(P) to be the set of distinct dot products determined by the set P , that is \Lambda(P)\mathrel{\mathop{\mathchar 58\relax}}=\{p\cdot q\mathrel{\mathop{\mathchar 58\relax}}p,q\in P\}. The goal of this paper is to prove the following bound. Theorem 1.1 . Let P\subseteq\mathbb{R}^{2} be a finite set of points in the plane. Then |\Lambda(P)|\gtrsim|P|^{\frac{2}{3}+\frac{7}{1425}}. This problem is inspired by the Erdős distinct distances problem, which asks how many distinct Euclidean distances are determined by a finite set of N points in the real plane. This question is solved (up to logarithmic factors) by L. Guth and N. Katz [ 1 ] who obtained the lower bound N/\log N . Similar bounds are believed to hold in the dot products problem we are investigating. The first result [ 3 ] appeared in this direction, due to B. Hanson, O. Roche-Newton, and S. Senger, pushes the exponent a positive constant beyond the 2/3 threshold bound that follows from Szemerédi-Trotter Theorem. We squeeze the techniques and ideas used in [ 3 ] to obtain an improvement to the constant on the exponent. Specifically, we utilise more efficiently the Plünnecke-Ruzsa and Ruzsa triangle inequalities and exploit the tool labeled as Lemma 3.5 below. 2. Notation Throughout this paper we adopt the Vinogradov asymptotic notation. Given variable quantities X and Y , we write X\ll Y , or Y\gg X , to denote that there exists an absolute constant c>0 such that X\leq cY . Furthermore, we write X\gtrsim Y , or Y\lesssim X, to denote X\gg Y/(\log_{2}(Y))^{c} for some absolute constant c>0 . 3. Prerequisites The following two results play a crucial role in our analysis and constitute the core of the proof. The first one is a result concerning the growth of the ratio of products of certain shifts of a finite set of real numbers X . Showing that this expander grows faster than |X|^{\frac{5}{2}} was the content of Section 2 in [ 3 ] and entails ideas such as the squeezing technique 1 1 1 illustrated in the proof of Theorem 2.1, in [ 3 ] and similar elementary methods to [ 2 ] . In this paper, we use an improvement of this bound obtained in [ 6 ] by reinforcing these techniques with the Elekes-Szabó Theorem and computer algebra. We will refer to this result as the superquadratic expander . Let A^{(k)}\mathrel{\mathop{\mathchar 58\relax}}=\{a_{1}\dotsm a_{k}\mathrel{\mathop{\mathchar 58\relax}}a_{1},\dotsc,a_{k}\in\ A\} denote the k-fold product set of a real finite set A . Theorem 3.1 . For any finite set X\subseteq\mathbb{R} , there exist x,x^{\prime}\in X such that \Bigg|\frac{(xX+1)^{(2)}(x^{\prime}X+1)^{(2)}}{(xX+1)^{(2)}(x^{\prime}X+1)}\Bigg|\gtrsim|X|^{\frac{31}{12}}. The next result is concerned with pinned dot products in the plane. We omit its proof which is a direct application of the Szemerédi-Trotter Theorem and can be found in [ 3 ] . Lemma 3.2 . Let P be a finite set of points in \mathbb{R}^{2} . Let \mathcal{L} be the set of all lines through the origin covering P . Then, there exists p\in P such that |\{p\cdot q\mathrel{\mathop{\mathchar 58\relax}}q\in P\}|\gg|P|^{\frac{1}{2}}|\mathcal{L}|^{\frac{1}{2}}. We make use of the standard Ruzsa Triangle inequality and a modified Plünnecke-Ruzsa inequality in the multiplicative setting. The former can be found in [Section 2.7, [ 7 ] ] and the latter as Lemma 1.5 in [ 4 ] or Corollary 2.4 in [ 5 ] . Lemma 3.3 . Let X,Y,Z be finite subsets in a commutative group. Then \bigg|\frac{Y}{Z}\bigg|\leq\frac{|XY||XZ|}{|X|}. Lemma 3.4 . Let X,B_{1},\dotsc,B_{k} be finite subsets in a commutative group. Suppose |XB_{i}|\leq\alpha_{i}|X|, for all 1\leq i\leq k . Then, there exists X^{\prime}\subseteq X , with |X^{\prime}|\geq|X|/2, such that |X^{\prime}B_{1}\dotsm B_{k}|\leq\alpha_{1}\alpha_{2}\dotsm\alpha_{k}2^{k}|X|. Furthermore, we apply the following inequality reflecting that pairs of sets with large multiplicative energy have large intersection after scaling. The additive analogue of the inequality can be found as Corollary 2.10 in [ 7 ] . Lemma 3.5 . Let A,B be finite subsets in a commutative group. Then there exists x\in A/B such that |A\cap xB|\geq\frac{E_{*}(A,B)}{|A||B|}\geq\frac{|A||B|}{|AB|}, where E_{*}(A,B) denotes the multiplicative energy of A and B . 4. Proof of Theorem 1.1 Let \mathcal{L} denote the set of lines passing through the origin and incident to P . We will show that |\Lambda(P)|\gtrsim|P|^{\frac{2}{3}+c}, for c=7/1425 . Furthermore, we assume (1) |\mathcal{L}|\leq|P|^{\frac{1}{3}+2c} otherwise the result follows by Lemma 3.2 . It would be convenient to assume that each line in \mathcal{L} passes through roughly the same number of points in P . We achieve this using dyadic decomposition at the cost of a logarithmic factor. Consider |P|=\sum_{l\in\mathcal{L}}|l\cap P|=\sum_{j=1}^{\lceil\log_{2}|P|\rceil}\underset{2^{j-1}\leq|l\cap P|<2^{j}}{\sum_{l\in\mathcal{L}\mathrel{\mathop{\mathchar 58\relax}}}}|l\cap P|. By the Pigeonhole Principle, there exists a j_{0} for which the summand contributes at least the average to the sum. Write M=2^{j_{0}-1} and let \mathcal{L^{\prime}}\subseteq\mathcal{L} be the set of lines satisfying M\leq|l\cap P|\leq 2M. Therefore, |P|\lesssim\frac{|P|}{\log|P|}\ll\sum_{l\in\mathcal{L^{\prime}}}|l\cap P|\ll M|\mathcal{L^{\prime}}|. Importantly, observe that each line l\in\mathcal{L^{\prime}} contains at least M\gtrsim|P|^{\frac{2}{3}-2c} points of P , by ( 1 ). We may use a rotation of the axes in order to assume that all the lines (up to a multiplicative constant) contained in \mathcal{L^{\prime}} have non-negative slope and the line lying on the x -axis is contained in our line set. Moreover, denote by P^{\prime}\subseteq P the subset of points covered by \mathcal{L^{\prime}} . Note that P^{\prime} is a large subset of P , and in fact has the same size as P up to a multiplicative constant and a logarithmic factor, as |P^{\prime}|\geq M|\mathcal{L^{\prime}}|\gtrsim|P| . The next step is to further restrict our attention to another large subset \mathcal{L^{\prime\prime}}\subseteq\mathcal{L^{\prime}}\subseteq\mathcal{L} containing the lines passing through points of P^{\prime} with some fixed x -coordinate. Observe that the set of pinned dot products determined by a point of P^{\prime} that lies on the x -axis is in bijection with the set of all vertical lines covering P^{\prime} , which is in turn in bijection with the set X defined to contain all x -coordinates of points of P^{\prime} . We may therefore assume |X|\leq|P|^{\frac{2}{3}+c} . For each u\in X , define \mathcal{L}(u)\mathrel{\mathop{\mathchar 58\relax}}=\{l\in\mathcal{L^{\prime}}\mathrel{\mathop{\mathchar 58\relax}}l\cap\{x=u\}\in P^{\prime}\}, and consider \sum_{u\in X}|\mathcal{L}(u)|=|P^{\prime}|\gtrsim|P|. Again, by Pigeonhole Principle, there exists some x_{0}\in X for which |\mathcal{L}(x_{0})|\gtrsim\frac{|P|}{|X|}\geq|P|^{\frac{1}{3}-c}. Henceforth, define \mathcal{L^{\prime\prime}}\mathrel{\mathop{\mathchar 58\relax}}=\mathcal{L}(x_{0}) . Let us now denote by S the set of slopes of lines from the line set \mathcal{L^{\prime\prime}} and apply Theorem 3.1 to find two elements s,s^{\prime}\in S such that we have (2) \Bigg|\frac{(sS+1)^{(2)}(s^{\prime}S+1)^{(2)}}{(sS+1)^{(2)}(s^{\prime}S+1)}\Bigg|\gtrsim|S|^{\frac{31}{12}}. Let X(s) and X(s^{\prime}) be the sets containing the x -coordinates of points of P^{\prime} lying on the lines of \mathcal{L^{\prime\prime}} with slopes s and s^{\prime} respectively. We will show that there exists a\in\mathbb{R}\backslash\{0\} such that the intersection Z\mathrel{\mathop{\mathchar 58\relax}}=X(s)\cap aX(s^{\prime}) is large. Consider the subset \Lambda^{\prime}\subseteq\Lambda(P) of all the dot products determined by the points