Humans Solve Erdos Problem!!

(In 2008 I wrote a survey of some of the known sum-product theorems, see here. Avi Wigderson has a great slide-set on sum-product theorems and their applications---the slides are on Avi's webpage of talks he has given (all the talks are excellent) which is here. I had a prior post on sum-product theorems here.) If \(A\) is a set then let \(A+A = \{ x+y \ \colon\ x,y\in A \} \), \(A\cdot A = \{ xy \ \colon \ x,y\in A \} \). Let \(A= \{1,\ldots,n\} \). \(|A+A| = \Theta(n) \) which is small. What about \(|A\cdot A|\)? By the prime number theorem there are \( \Theta(\frac{n}{\log n}) \) primes in \(A\) hence \(|A\cdot A| \ge \Omega(\frac{n^2}{\log^2n})\) by taking product of two primes. Or better: look at \(\{ xy \ \colon \ x \hbox{ a prime in } \{n/2,\ldots,n\} , y \in \{1,\ldots,n/2\} \} \).This is a subset of \( A\cdot A \) of size \( \Omega( \frac{n^2}{\log n} ) \). Ford improved this to \[ |A\cdot A| = \Theta\biggl (\frac{n^2}{(\log n)^a\log\log n)^{3/2}} \biggr ) \] where…