Timeline for Trick for the sum-product problem
Current License: CC BY-SA 4.0
33 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Mar 31, 2019 at 17:59 | history | bounty ended | Craig Feinstein | ||
| S Mar 31, 2019 at 17:59 | history | notice removed | Craig Feinstein | ||
| Mar 31, 2019 at 17:59 | vote | accept | Craig Feinstein | ||
| Mar 30, 2019 at 7:16 | answer | added | Mark Lewko | timeline score: 5 | |
| Mar 30, 2019 at 0:54 | comment | added | user114668 | If I'm not mistaken, the set cardinality triangle inequality fails for $A_k = \{0, \ldots, k\}$ first at $k = 16, 18$ and for all $k \ge 20$. | |
| Mar 26, 2019 at 15:38 | comment | added | Craig Feinstein | @PeterTaylor, I want $n$ as close to 2 as possible. | |
| Mar 25, 2019 at 22:00 | comment | added | Peter Taylor | Presumably you also want to bound $1 < n$, since trivially $|A^2 + A^2| \ge |A^2| \ge \frac12 |A|$ | |
| S Mar 25, 2019 at 21:42 | history | bounty started | Craig Feinstein | ||
| S Mar 25, 2019 at 21:42 | history | notice added | Craig Feinstein | Draw attention | |
| Mar 22, 2019 at 22:32 | comment | added | Craig Feinstein | @seva I will think about this more. Thank you again for your help with this. | |
| Mar 22, 2019 at 20:20 | comment | added | Seva | I do not have any counterexample off-hand, but it absolutely does not mean that the inequality is correct, of course. If you manage to prove it, this would be interesting, but I cannot see any reason for it to hold. | |
| Mar 22, 2019 at 20:14 | comment | added | Craig Feinstein | @seva I ask because I still believe that the inequality in my question is true, even though I haven't proven it. | |
| Mar 22, 2019 at 20:00 | comment | added | Craig Feinstein | @Seva, Can you also find a counterexample to $f(x,y)=x^2+y^2-(x+y)^2$ and $g(x,y)=(x+y)^2$. | |
| Mar 22, 2019 at 19:46 | comment | added | Craig Feinstein | @Seva it looks like you are correct. Thank you. | |
| Mar 22, 2019 at 19:39 | comment | added | Seva | Well, unless I am mistaken, here is a counterexample. Take $A=\{0,1,2\}$, $f(x,y)=x$, and $g(x,y)=100y$. Then $|\{f(x,y)\}|=|\{g(x,y)\}|=3$, while $|\{f(x,y)+g(x,y)\}|=9$. | |
| Mar 22, 2019 at 19:26 | comment | added | Craig Feinstein | @seva, do you have a counter-example? | |
| Mar 22, 2019 at 19:19 | comment | added | Seva | Looks nice - but why is this correct? | |
| Mar 22, 2019 at 19:13 | comment | added | Craig Feinstein | @seva $|\{f(x,y):x,y \in A\}|+|\{g(x,y):x,y \in A\}| \geq |\{f(x,y)+g(x,y):x,y \in A\}|$. In this problem, $f(x,y)=x^2+y^2-(x+y)^2$ and $g(x,y)=(x+y)^2$. | |
| Mar 22, 2019 at 19:06 | comment | added | Seva | Still - exactly what is the general inequality you use, and exactly how you apply it? | |
| Mar 22, 2019 at 19:00 | comment | added | Craig Feinstein | @seva it is the triangle inequality for set cardinality. | |
| Mar 22, 2019 at 18:58 | comment | added | Boris Bukh | @CraigFeinstein So you are interested in behavior of $B+B$ for $B$ being a set of squares. That is, as far as I know, open. This is related to the question of whether squares is a $\Lambda(4)$-set. | |
| Mar 22, 2019 at 18:51 | comment | added | Seva | Well, I am suspicious about the only inequality that appears in the computation in question; could you explain it? | |
| Mar 22, 2019 at 18:43 | comment | added | Craig Feinstein | @Seva, if you tell me how it's wrong, I will withdraw the question. | |
| Mar 22, 2019 at 18:37 | comment | added | Seva | Thank you for the reference to the nice Quanta article, but math-wise, your computation (the one starting with $|A\cdot A|+|A+A|$) seems totally wrong to me. | |
| Mar 22, 2019 at 18:31 | comment | added | Craig Feinstein | On the other hand $n=1$ certainly works. But I am trying to get something closer to two. | |
| Mar 22, 2019 at 18:30 | review | Close votes | |||
| Mar 25, 2019 at 21:45 | |||||
| Mar 22, 2019 at 18:20 | comment | added | Craig Feinstein | @BorisBukh, I am assuming that $A$ is a set of integers. I'm not sure if that is the standard assumption for this problem though. | |
| Mar 22, 2019 at 18:14 | comment | added | Boris Bukh | Clearly $n=1$ works because LHS is at least |A|. Clearly, no larger $n$ works because $A$ could be $\{\sqrt{1},\sqrt{2},\dotsc,\sqrt{n}\}$. | |
| S Mar 22, 2019 at 17:43 | history | edited | Craig Feinstein | CC BY-SA 4.0 |
Typos in the title and body are corrected up to the cited link:" But Erdős and Szemerédi’s “sum-product” problem".
|
| S Mar 22, 2019 at 17:43 | history | suggested | user64494 | CC BY-SA 4.0 |
Typos in the title and body are corrected up to the cited link:" But Erdős and Szemerédi’s “sum-product” problem".
|
| Mar 22, 2019 at 17:38 | review | Suggested edits | |||
| S Mar 22, 2019 at 17:43 | |||||
| Mar 22, 2019 at 17:37 | history | edited | Craig Feinstein | CC BY-SA 4.0 |
substituted A for Z
|
| Mar 22, 2019 at 17:30 | history | asked | Craig Feinstein | CC BY-SA 4.0 |