Timeline for Nontrivial expansion in sumsets
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 28, 2019 at 4:23 | comment | added | Ryan Alweiss | I just chose it because it is a function that grows to infinity very slowly, so that $|A|=o(p)$ but $A$ would still be pretty large. | |
| Nov 26, 2019 at 9:25 | comment | added | Gerry Myerson | In case anyone else is curious, it's "the number of times the logarithm function must be iteratively applied before the result is less than or equal to $1$." | |
| Nov 26, 2019 at 5:00 | history | edited | Sam Zbarsky | CC BY-SA 4.0 |
added 326 characters in body
|
| Nov 26, 2019 at 4:49 | comment | added | Sam Zbarsky | @GerryMyerson en.wikipedia.org/wiki/Iterated_logarithm | |
| Nov 26, 2019 at 2:39 | comment | added | Gerry Myerson | What is meant by $\log^*p$, please? | |
| Nov 26, 2019 at 0:14 | comment | added | Sam Zbarsky | @SandeepSilwal divide the interval $[p^{2/3},p/(3\log^*p)]$ into intervals of the form $[a,a+\lfloor p/(2a)\rfloor]$, with about $\log^*p$ numbers left over. The elements of each interval are sent to a sequence whose successive differences are $(2+o(1))a$ and which has $\lfloor p/(2a)\rfloor+1$ elements. Thus at least $\frac{p}{4a\sqrt{\log^*p}}$ of them lie in the interval $[1,p/\sqrt{\log^* p}]$, which makes a fraction of $\frac{1}{2\sqrt{\log^*p}}$. Summing over all such intervals, we get the desired result (and the constant 10 has a safety margin). | |
| Nov 25, 2019 at 22:46 | comment | added | Sandeep Silwal | Sorry, can you elaborate a bit more on why $|A| \ge p/10\log^*p$? | |
| Nov 25, 2019 at 22:00 | history | answered | Sam Zbarsky | CC BY-SA 4.0 |