Above is a pdf file about an question related to the Sum-product phenomenon introduced by Erdos and Szemeredi.
Fix to be finite and nonempty. We are interested in nontrivial lower bounds for . The best known bounds in such generality come from the Szemeredi-Trotter theorem from incidence geometry giving . Though when one restricts to , one has . We give a short proof of this fact in the above file.
Recently, Oliver Roche-Newton, Imre Ruzsa, Chen-Yen Shen and Ilya Shkredov have made progress! They show both that the previously known upper and lower bounds are not sharp. It is still certainly plausible that for any $\epsilon > 0$, .