Consider the sequence
$$a_n:=\min_{\substack{A\subseteq\mathbb{Z}\\|A|=n}}|(A+A)\cup (A\cdot A)|.$$
This is A263996 in OEIS. (Actually, they restrict to $\mathbb{N}$, but it makes little difference to my question.) Erdős and Szemeredi conjectured $a_n\gg_\epsilon n^{2-\epsilon}$; see problem 52 on erdosproblems.com and references therein.
Question: How does one compute $a_n$?
I have two ideas for this:
- Restrict the search to $A\subseteq[-M,M]$ for some $M$. But which $M=M(n)$ is large enough to hit $a_n$?
- Get a lower bound on $a_n$ by solving the relaxed version that replaces $\mathbb{Z}$ with $\mathbb{R}$ (this can be computed by quantifier elimination over the reals), and then hunt for $A\subseteq\mathbb{Z}$ that achieves equality in this lower bound. Unfortunately, the relaxation may not be tight. (In fact, it's open whether the sum-product conjecture of Erdős and Szemeredi is equivalent to its analogue over the reals; see exercise 8.3.1 in Tao and Vu's book on additive combinatorics.)
(A part of me wonders how rigorous the entries in A263996 are, since the computation methodology is missing. Another part of me wonders whether A263996 is even computable!)
