Sum-product estimates via directed expanders (Q935879): Difference between revisions

The sum-product phenomenon was first observed in 1983 by \textit{P. Erdős} and \textit{E. Szemerédi} [Studies in Pure Mathematics, Mem. of P. Turán, 213--218 (1983; Zbl 0526.10011)], who showed that a finite set of integers \(A\) cannot have both its sumset and product set simultaneously very small. More precisely, there exists \(c>0\) such that \(\max\{|A+A|,|A\cdot A|\} \gg |A|^{1+c}\). This result has since been considered by many authors, improving the exponent and establishing analogues in other domains such as finite fields and rings. The present paper shows that the sum-product phenomenon may be viewed as a more general class of phenomena, where \(A \cdot A\) is replaced by \(P(A) := \{P(x,y): x,y \in A\}\) for some bivariate polynomial \(P(x,y)\). Note that if \(P\) takes the form \(f(ax+by)\) for some polynomial \(f(x)\), then \(A+A\) and \(P(A)\) can both be very small (take \(A\) to be an arithmetic progression). The main theorem of the paper under review is that such a degeneracy is the only possible obstruction in the finite field setting. Specifically, if \(P \in \mathbb F_q[x,y]\) has degree \(k\) and is not of the above form, then for any \(A \subset \mathbb F_q\), \[ \max\big\{|A+A|, |P(A)|\big\} \gg |A| \cdot \min\left\{ \frac{|A|^{1/2}}{kq^{1/4}}, \bigg(\frac{q}{k|A|}\bigg)^{1/3} \right\}. \] Specializing this to the case \(P(x,y) = xy\) gives bounds that are comparable to contemporary sum-product estimates [\textit{D. Hart, A. Iosevich} and \textit{J. Solymosi}, Int. Math. Res. Not. 2007, No. 5, Article ID rnm007, 14 p. (2007; Zbl 1146.11013)]. The paper gives an immediate application to a finite-field \(L^p\)-analogue of the Erdős distinct distances problem. The proof uses the spectral method, establishing an eigenvalue bound for directed Cayley graphs formed from the level sets of \(P(x,y)\) in \(\mathbb F_q^2\). The key ingredient is a bound on the Fourier coefficients of such sets. In the ring setting, \(A \subset \mathbb Z_m\) with \(m>1\) an odd integer, such bounds are not readily available. The author instead uses Kloosterman sums to obtain a similar result for a certain class of binary quadratic forms \(Q\): \[ \max\big\{|A+A|, |Q(A)|\big\} \gg |A| \cdot \min\bigg\{ \bigg(\frac{\gamma(m)^{1/2} |A|}{m \cdot g(m)}\bigg)^{1/2}, \bigg(\frac{m}{|A|}\bigg)^{1/3} \bigg\}. \] Here, \(\gamma(m)\) is the smallest prime dividing \(m\), and \(g(m)\) is a divisor-like function which measures the compositeness of \(m\): we give a precise definition below. The paper is well-organized and written clearly, with a number of interesting remarks and concluding with some natural open questions. It may be worth noting a minor problem with the definition of \(g(m)\). A recursive definition is given by \(g(1) = 0\), \(g(m) = \tau(m) + \sum_d g(m/d)\), where \(\tau\) is the divisor function and \(d\) ranges over non-trivial squarefree divisors of \(m\). In the reviewer's estimation, this function grows roughly as fast as \(k!\), where \(k\) is the number of primes dividing \(m\); in particular as \(k \to \infty\), \(g(m)\) should be larger than any fixed power of \(\tau(m)\). This would contradict the explicit formula given earlier in the paper \(g(m) := \sum_{n\mid m} \tau(m) \tau(m/n)\), which is at most \(\tau^3(m)\). The author accurately notes that the theorem is only effective when \(m\) is the product of a few large primes; indeed, it seems likely that in any application, the effect of \(g(m)\) will be insignificant compared to the gap between \(\gamma(m)\) and \(m\).