Growth Estimates in Positive Characteristic via Collisions

By E. Yazici, Brendan Murphy, M. Rudnev, Ilya D. Shkredov. 2015

65 citations recorded by the source corpus.

Let $F$ be a field of characteristic $p>2$ and $A\subset F$ have sufficiently small cardinality in terms of $p$. We improve the state of the art of a variety of sum-product type inequalities. In particular, we prove that $$ |AA|^2|A+A|^3 \gg |A|^6,\qquad |A(A+A)|\gg |A|^{3/2}. $$ We also prove several two-variable extractor estimates: ${\displaystyle |A(A+1)| \gg|A|^{9/8},}$ $$ |A+A^2|\gg |A|^{11/10},\; |A+A^3|\gg |A|^{29/28}, \; |A+1/A|\gg |A|^{31/30}.$$ Besides, we address questions of cardinalities $|A+A|$ vs $|f(A)+f(A)|$, for a polynomial $f$, where we establish the inequalities $$ \max(|A+A|,\, |A^2+A^2|)\gg |A|^{8/7}, \;\; \max(|A-A|,\, |A^3+A^3|)\gg |A|^{17/16}. $$ Szemer\'edi-Trotter type implications of the arithmetic estimates in question are that a Cartesian product point set $P=A\times B$ in $F^2$, of $n$ elements, with $|B|\leq |A|< p^{2/3}$ makes $O(n^{3/4}m^{2/3} + m + n)$ incidences with any set of $m$ lines. In particular, when $|A|=|B|$, there are $\ll n^{9/4}$ collinear triples of points in $P$, $\gg n^{3/2}$ distinct lines between pairs of its points, in $\gg n^{3/4}$ distinct directions. Besides, $P=A\times A$ determines $\gg n^{9/16}$ distinct pair-wise distances. These estimates are obtained on the basis of a new plane geometry interpretation of the incidence theorem between points and planes in three dimensions, which we call collisions of images.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/df5da490ce2f0bace384a89e5c04f6352c97b85d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

In Discrete Mathematics and Combinatorics

Citations in the corpus

NEW RESULTS ON SUM‐PRODUCT TYPE GROWTH OVER FIELDS (2017, background): “In this vein [1], it was shown that if A is a subset of a field of characteristic p satisfying |A| < p and |A+ A| ≤ |A|1+ε then |AA| ≫ |A| 3 2 .”
On the energy variant of the sum-product conjecture (2016, methodology): “However, a weaker result can most likely be derived on the basis of Proposition 14 in [1].”
An improved point‐line incidence bound over arbitrary fields (2016, methodology): “Such an approach was explored in a recent work of Aksoy, Murphy, Rudnev and Shkredov [2].”
On asymptotic formulae in some sum–product questions (2018, methodology): “At the moment the best results in the direction can be found in [52], [28], [29], [43] and in [1], [41] for R and Fp, respectively.”