Timeline for Is the set $ AA+A $ always at least as large as $ A+A $?
Current License: CC BY-SA 3.0
33 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 30, 2015 at 12:25 | comment | added | George Shakan | Antal Balog conjectured for $A \subset \mathbb{R}^+$, one has $|A+A \cdot A| \geq |A|^2$ in "A note on sum-product estimates" | |
| Apr 29, 2015 at 16:09 | answer | added | Terry Tao | timeline score: 16 | |
| Apr 28, 2015 at 18:48 | answer | added | Brendan Murphy | timeline score: 9 | |
| Apr 28, 2015 at 14:33 | comment | added | Brendan Murphy | @WillSawin Similar estimates come up in the arithmetic approach to the Kakeya problem, although typically $\lambda$ is small and fixed. Typically more efficient sum-product type estimates use incidence theorems and avoid Ruzsa calculus if possible (e.g. Elekes' or Solymosi's sum product estimates). | |
| S Apr 28, 2015 at 3:41 | history | suggested | Transcendental | CC BY-SA 3.0 |
Edited title.
|
| Apr 28, 2015 at 2:56 | review | Suggested edits | |||
| S Apr 28, 2015 at 3:41 | |||||
| Apr 28, 2015 at 2:49 | answer | added | Terry Tao | timeline score: 57 | |
| Apr 27, 2015 at 21:40 | comment | added | Brendan Murphy | @YaakovBaruch I counted incorrectly, so the inequality I claimed doesn't hold. But the set mentioned by GH from MO would work in it's place (and could be amplified by taking products and projecting). | |
| Apr 27, 2015 at 21:21 | answer | added | GH from MO | timeline score: 18 | |
| Apr 27, 2015 at 20:49 | comment | added | Michael | Erdos result on the size of multiplication table seems to indicate that on average for large |A| the size of |AA+A| is only slightly larger than |A+A|. That reduces the hope for a one-line proof in general case. | |
| Apr 27, 2015 at 18:54 | comment | added | Will Sawin | It seems plausible that estimates giving a lower bound for $|A+ \lambda A|$ or $|A+B|$ in terms of $|A+A|$ would be helpful here, but the best one I've found is by Ruzsa calculus, which gives $|AA||A+A| \leq |A+AA|^2$, which is not helpful at all because it is only useful when $|AA| \geq |A+A|$, and then the identity $|AA+A| \geq |AA|$ already solves the problem. Are there better estimates of this type? | |
| Apr 27, 2015 at 18:47 | comment | added | user9072 | @VladimirDotsenko an explicit example that contains $-1$ would be $\{-1,1,2,3,6,10,11,12\}$ (which is just the set that GH mentions shifted). The paper I would have mentioned but GH's reference is more recent and quotes this one. | |
| Apr 27, 2015 at 17:32 | comment | added | GH from MO | @YaakovBaruch: From Daniel Glasscock's MS thesis (people.math.osu.edu/glasscock.4/MSThesis.pdf): The set $\{-7,-5,-4,-3,0,4,5,7\}$ has 26 sums and 25 differences. It has the smallest diameter and the fewest number of elements of all MSTD sets in the integers, and all 8-element MSTD sets are affinely equivalent to it. Reference to Hegarty's paper Acta Arith. 130 (2007), 61-77. | |
| Apr 27, 2015 at 17:16 | comment | added | Yaakov Baruch | @BrendanMurphy. Why do you mean by distinct pairs? $a-b$ and $b-a$ are distinct numbers. | |
| Apr 27, 2015 at 16:44 | comment | added | Brendan Murphy | @VladimirDotsenko Let $A$ be 6 generic real numbers. Then $|A+A|$ is 21 (15 distinct pairs, 6 sums $a+a$) while $|A-A|$ is 16 (15 distinct pairs and 0). Taking (Cartesian) products of $A$ gives arbitrarily large sets where $|A-A|/|A| \ll |A+A|/|A|$ (since the doubling constant of a product is the product of doubling constants). I believe a generic projection could be used to send the product sets back into the reals. | |
| Apr 27, 2015 at 16:12 | comment | added | Vladimir Dotsenko | @quid can you please give a link or explain an example? thanks! | |
| Apr 27, 2015 at 14:21 | comment | added | user9072 | @YaakovBaruch the idea is good but at least for $a=-1$ there are examples. In fact this question, that is the question of sets with less differences than sums, got study in recent years. | |
| Apr 27, 2015 at 14:04 | comment | added | Lucia | The claim for subsets of the integers holds, and follows from this MO question: mathoverflow.net/questions/168844/… | |
| Apr 27, 2015 at 13:47 | answer | added | Gerald Edgar | timeline score: 11 | |
| Apr 27, 2015 at 13:10 | comment | added | Yaakov Baruch | Is there even a case where $|aA+A|<|A+A|$ for $a\ne 0$? | |
| Apr 27, 2015 at 12:50 | comment | added | Joonas Ilmavirta | The claim is not true if you replace sets of real numbers with sets of $n\times n$ real matrices for any $n\geq2$. Generalizing is interesting, but you can only go so far. | |
| Apr 27, 2015 at 12:43 | answer | added | Neil Strickland | timeline score: 11 | |
| Apr 27, 2015 at 12:33 | comment | added | Oliver Roche-Newton | @YaakovBaruch, good point. I cannot see any obvious reason why the same inequality would fail for complex numbers. | |
| Apr 27, 2015 at 12:27 | comment | added | Yaakov Baruch | Why not ask the question for complex numbers even? | |
| Apr 27, 2015 at 11:44 | answer | added | Yaakov Baruch | timeline score: 0 | |
| Apr 27, 2015 at 11:25 | comment | added | Oliver Roche-Newton | Federico Poloni, $AA$ denotes the product set of $A$, and so $AA:=\{ab:a,b \in A\}$. The notation is standard in the field of sum-product estimates, but I can certainly see the ambiguity. The set you mention in your comment is sometimes denoted as $A^{(2)}$. | |
| Apr 27, 2015 at 11:19 | comment | added | Federico Poloni | What is $AA$? $\{a^2 : a\in A\}$? Is it standard notation? | |
| Apr 27, 2015 at 10:57 | comment | added | Oliver Roche-Newton | Yes, thanks Seva and quid. I have changed the title of the thread to match the non-strict inequality in the body of the question. | |
| Apr 27, 2015 at 10:55 | history | edited | Oliver Roche-Newton | CC BY-SA 3.0 |
edited title
|
| Apr 27, 2015 at 10:41 | comment | added | user9072 | Given the comments above, could you please align the question in the title and in the body that seem slightly different. | |
| Apr 27, 2015 at 10:14 | comment | added | Seva | If $A=\{0,1\}$, then $AA=A$. So, one must assume something like $|A|\ge 3$. | |
| Apr 27, 2015 at 9:57 | history | edited | GH from MO |
edited tags
|
|
| Apr 27, 2015 at 9:46 | history | asked | Oliver Roche-Newton | CC BY-SA 3.0 |