Timeline for Structure of nonaveraging sets of integers
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 22, 2012 at 15:26 | comment | added | Urban | L. Moser's construction from 1953 is perfectly constructive though. His sequence begins 100000, 1000100100, 1000400200, 1000900300, 1001600400, 1002500500, \ldots and becomes nearly as dense as Behrends: for sufficiently large $n$ it contains at least $n^{1-c/\sqrt{\log n}}$ numbers in an interval of length $n$, for some constant $c$. | |
| Apr 3, 2011 at 7:03 | comment | added | Seva | @Seva: sure - thanks for the correction :-) | |
| Apr 3, 2011 at 7:03 | comment | added | Seva | @Seva: in fact, the "expected average" is about $kq^2/12$ rather than $kq^2/16$ (for $q$ large). | |
| Apr 3, 2011 at 6:00 | comment | added | Seva | @Ewan: although the number of representations as a sum of two squares is not a particularly smooth function, the number of representations as a sum of a large number of squares exhibits a very regular behavior. In the former case you look at the "convolution square", in the latter case at the "high convolution power". | |
| Apr 3, 2011 at 5:47 | comment | added | Ewan Delanoy | @ Seva : your idea about derandomizing Behrend's argument looks highly doubtful to me. The function f(r)=Number of solution to x^2+y^2=r is a discontinuous function, and there is no reason to think that f(r) is close to f(s) when r is close to s. | |
| Apr 2, 2011 at 21:19 | vote | accept | Ewan Delanoy | ||
| Apr 3, 2011 at 10:29 | |||||
| Apr 2, 2011 at 21:19 | vote | accept | Ewan Delanoy | ||
| Apr 2, 2011 at 21:19 | |||||
| Apr 2, 2011 at 20:49 | comment | added | user9072 | @Seva: Thank you for the explanation. | |
| Apr 2, 2011 at 20:44 | comment | added | Seva | @unknown: there does not seem to be a problem with it. Indeed, presenting Behrend's construction, one usually says something like "by averaging, one of the spheres is rich", but I think this can be derandomized without any problem. Suppose we consider integers with the base-$q$ representation $a_{k-1}...a_0$, where the $q$-ary digits $a_i\in[0,q/2)$ satisfy $a_{k-1}^2+\dots+a_0^2=r$. If we just choose $r$ close to the "expected average" of $kq^2/16$, I believe it should not be difficult to show that the resulting sphere is nearly optimal. | |
| Apr 2, 2011 at 20:09 | comment | added | user9072 | Regarding your first point: while I also found the insistence of the questioner on the nonconstructiveness a bit surprising, I am now also surprised by your 'perfectly constructive'. As I was under the impression that (at least the proof I know of) Behrend is mildly nonconstructive; as one does not know which of the spheres is 'good' and one only gets by averaging that some radius is good (but not which one). Do you have a different argument in mind, or perhaps we just mean different things by constructive? | |
| Apr 2, 2011 at 19:41 | history | answered | Seva | CC BY-SA 2.5 |