Proof verification and improvement - lower bound for the sum product problem

281 Views Asked by At

Thinking about the sum product conjecture, if we consider a set of distinct elements $A=\{a_1,a_2,\dots,a_n\}$, $\forall a_i\in \mathbb Z^+$, I have derived the following lower bound: $$\max\{|A+A|,|A•A|\}\geq \frac{n^2+5n-2}{4}$$

Proof

It can be easily showed that $$2n-1\leq|A+A|\leq \frac{n^2+n}{2}$$ and $$2n-1\leq|A•A|\leq \frac{n^2+n}{2}$$

This bounds are independent of the correlation between $|A+A|$ and $|A•A|$.

Other hand, $a_i+a_j=a_r+a_s=k$ only if (wlog, $a_i>a_j$,$a_r>a_s$ and $a_i>a_r$) $a_i=a_r+k$ and $a_j=a_s-k$.

Substituting, we get that $$a_ia_j=(a_r+k)(a_s-k)=a_ra_s+k(a_s-a_r)-k^2$$ As $k(a_s-a_r)-k^2<0$ $\forall a_s,a_r,k \in \mathbb Z^+$, we conclude that if $a_i+a_j=a_r+a_s$ then $a_ia_j\neq a_ra_s$. A similar argument can be used conversely to show that if $a_ia_j= a_ra_s$ then $a_i+a_j\neq a_r+a_s$.

Therefore, any decrease in the number of distinct elements of set $A+A$, which ocurr only due to relations $a_i+a_j=a_r+a_s$, implies a non-decrease in the number of distinct elements of set $A•A$; and conversely, any decrease in the number of distinct elements of set $A•A$, which ocurr only due to relations $a_ia_j=a_ra_s$, implies a non-decrease in the number of distinct elements of set $A+A$. Thus, the maximum total decrease for sets $A+A$ and $A•A$ from the upper independent bound of $\frac{n^2+n}{2}$ stated before is $\frac{n^2+n}{2}-(2n-1)$ jointly for both sets.

Subsequently, we can affirm that $$|A+A|+|A•A|\geq \frac {n^2+n}{2}+2n-1$$ and, subsequently, $$\max\{|A+A|,|A•A|\}\geq \frac{\frac{n^2+n}{2}+2n-1}{2}$$ Operating a bit, we get that $$\max\{|A+A|,|A•A|\}\geq \frac{n^2+5n-2}{4}$$ As we wanted to prove.

It would be great if you could confirm that the proof is correct, or point out the errors. Also, I would like to know how to derive a tight asymptotic of the form $\Omega (|A|^{1+\epsilon})$ from the bound proved (even if the proof turns out to be wrong), and if the proof could be extended to cover sets with elements in $\mathbb Z$ or $\mathbb R$.

Thanks in advance!

EDIT

Checking "by hand", I get that: $$\frac{n^2+5n-2}{4}\geq (n^{2-\frac{1}{2}})$$ for all $n\in \mathbb Z^+$; $$\frac{n^2+5n-2}{4}> (n^{2-\frac{1}{3}})$$ for all $n>48$; $$\frac{n^2+5n-2}{4}> (n^{2-\frac{1}{4}})$$ for all $n>235$; $$\frac{n^2+5n-2}{4}> (n^{2-\frac{1}{5}})$$ for all $n>998$; $$\dots$$ It seems that $$\frac{n^2+5n-2}{4}> (n^{2-\frac{1}{k}})$$ for all $n>4^k-5k-1$.

This suggests that, for any $\epsilon > 0$ there exists $n_0$, such that any set $A$ of at least $n_0$ integers satisfies $\max\{|A+A|,|A•A|\}\geq c|A|^{2-\epsilon}$ (Erdös-Szemeredi conjecture) with an explicit constant $c=1$.

1

There are 1 best solutions below

6
On BEST ANSWER

No, this proof is not valid. I'll rephrase your proof as follows: let $\lvert A\rvert=n$ and call a quadruple $(i,j,r,s)$ (with $1\leq i,j,r,s\leq n$) an additive quadruple if $a_i+a_j=a_r+a_s$, and similarly for multiplicative quadruple.

You give a simple argument that a quadruple cannot be simultaneously both additive and multiplicative - aside from the 'diagonal case' when $\{i,j\}=\{r,s\}$. This is correct.

The count of additive quadruples is a well-studied concept in additive combinatorics, and is usually known as the additive energy, denoted $E_+(A)$, and similarly for multiplicative energy.

Where you go wrong is in deducing about the size of $\lvert A+A\rvert$ or $\lvert AA\rvert$ from this. You seem to be implicitly assuming something like $\lvert A+A\rvert = \frac{n^2+n}{2}-E_+(A)$, in saying something like 'any decrease in the number of distinct elements in $A+A$ which occur only due to [additive quadruples]'. This is obviously wrong anyway, since $E_+(A)$ includes the 'diagonal quadruples' where $\{i,j\}=\{r,s\}$, of which there are $\approx n^2/2$. But even redefining energy to not include these, this is still wrong.

(Consider, for example, the case when $A=\{1,\ldots,n\}$ - this has very large additive energy, $\asymp n^3$, but $\lvert A+A\rvert \asymp n$.)

Perhaps you don't mean exactly $\lvert A+A\rvert = \frac{n^2+n}{2}-E_+(A)$, but any similar simple formula between the size of the sumset and the additive energy is doomed to fail. The best you can do is a one-way implication, that $\lvert A+A\rvert \geq \lvert A\rvert^4/E_+(A)$, which is a consequence of the Cauchy-Schwarz inequality.

Assuming that we use this, the observation that non-diagonal quadruples cannot be simultaneously both additive and multiplicative only obviously gives us the relationship that $\min(E_+(A),E_\times(A))\leq \frac{1}{2}n^4$ (since there are $n^4+O(n^2)$ non-diagonal quadruples in total). (As a test case for your argument, think about the potential worst-case - that half of all $n^4$ possible quadruples are additive and the other half are all multiplicative - what does your argument suggest is the size of the sum and product sets?)

Using the Cauchy-Schwarz consequence above, this means that $\max(\lvert A+A\rvert,\lvert AA\rvert)\geq (2+o(1))n$. This is, of course, trivial, since as you point out we automatically have $\lvert A+A\rvert \geq 2n-1$ anyway.

The sum-product conjecture remains wide-open, and has been studied by many people for decades. While it is possible that there is a simple argument which has been overlooked so far, it is very unlikely. I recommend that you read some of the recent progress on the sum-product conjecture, which contains many beautiful elementary ideas you'd find interesting. (e.g. there is a very elegant argument of Solymosi which yields $\max(\lvert A+A\rvert,\lvert AA\rvert)\gg \lvert A\rvert^{4/3-o(1)}$, a nice account of which is written up here: https://web.williams.edu/Mathematics/lg5/Solymosi.pdf.)