In this paper we show examples for applications of the Bombieri--Lang conjecture in additive combinatorics, giving bounds on the cardinality of sumsets of squares and higher powers of integers.

We prove, for a sufficiently small subset $\mathcal{A}$ of a prime residue field, an estimate on the number of solutions to the equation $(a_1-a_2)(a_3-a_4) = (a_5-a_6)(a_7-a_8)$ with all variables in $\mathcal{A}$. We then derive new bounds on trilinear exponential sums and on the total number of residues equaling the product of two differences of elements of $\mathcal{A}$. We also prove a refined estimate on the number of collinear triples in a Cartesian product of multiplicative subgroups and derive stronger bounds for trilinear sums with all variables in multiplicative subgroups.

We prove that if $A\subseteq [N]$ does not contain any solution to the equation $x_1+\dots+x_k=y_1+\dots+y_k$ with distinct $x_1,\dots,x_k,y_1,\dots,y_k\in A$, then $|A|\le 16 {k^{3/2}}N^{1/k},$ provided $N\ge (2k^{2})^{2k}$. This problem was first considered by Ruzsa, and this upper bound improves the previously best known upper bound of $(\frac{1}{4} + o_k (1)) k^2 N^{1/k}$ which was proved by Timmons.

This paper is a sequel to a paper entitled Variations on the sum-product problem by the same authors [SIAM J. Discrete Math., 29 (2015), pp. 514-540]. In this sequel, we quantitatively improve several of the main results of the first paper as well as generalize a method from it to give a near-optimal bound for a new expander. The main new results are the following bounds, which hold for any finite set $A \subset \mathbb R$: $\exists a \in A$ such that $|A(A+a)| \gtrsim |A|^{\frac{3}{2}+\frac{1}{186}}, |A(A-A)| \gtrsim |A|^{\frac{3}{2}+\frac{1}{34}}, |A(A+A)| \gtrsim |A|^{\frac{3}{2}+\frac{5}{242}}, |\{(a_1+a_2+a_3+a_4)^2+\log a_5 : a_i \in A \}| \gg \frac{|A|^2}{\log |A|}$.

A square matrix V is called rigid if every matrix V' obtained by altering a small number of entries of $V$ has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major implications in computational complexity theory. One approach to establishing rigidity of a matrix V is to come up with a property that is satisfied by any collection of vectors arising from a low-dimensional space, but is not satisfied by the rows of V even after alterations. In this paper we propose such a candidate property that has the potential of establishing rigidity of combinatorial design matrices over the field F_2. Stated informally, we conjecture that under a suitable embedding of F_2^n into R^n, vectors arising from a low dimensional F_2-linear space always have somewhat small Kolmogorov width, i.e., admit a non-trivial simultaneous approximation by a low dimensional Euclidean space. This implies rigidity of combinatorial designs, as their rows do not admit such an approximation even after alterations. Our main technical contribution is a collection of results establishing weaker forms and special cases of the conjecture above.

This paper considers various formulations of the sum-product problem. It is shown that, for a finite set $A\subset{\mathbb{R}}$, $|A(A+A)|\gg{|A|^{\frac{3}{2}+\frac{1}{178}}},$ giving a partial answer to a conjecture of Balog. In a similar spirit, it is established that $|A(A+A+A+A)|\gg{\frac{|A|^2}{\log{|A|}}},$ a bound which is optimal up to constant and logarithmic factors. We also prove several new results concerning sum-product estimates and expanders, for example, showing that $|A(A+a)|\gg{|A|^{3/2}}$ holds for a typical element of $A$.