Timeline for example just slightly better than the greedy construction
Current License: CC BY-SA 2.5
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 2, 2011 at 17:58 | comment | added | Ewan Delanoy | @ Gil : indeed, one may want to take an unusual order on 1,2, ... ,n, for example beginning by deleting the most central elements (because they are more likely to cause trouble later). | |
| Jan 2, 2011 at 17:57 | comment | added | Ewan Delanoy | @ Seva : you're right, my initial statement was incorrect : the exact formulation is "C is the set of integers n such that the ternary expansion of n-1 contains no 2". I edited the OP accordingly | |
| Jan 2, 2011 at 17:55 | history | edited | Ewan Delanoy | CC BY-SA 2.5 |
Ewan Delanoy edit : update on the construction of T
|
| Jan 2, 2011 at 16:48 | comment | added | Gil Kalai | I suppose that by greedily you take 1,2,...,n in this order one by one and delete an element that creates an AP. Perhaps you can do better by taking them in some other (natural) order. | |
| Jan 2, 2011 at 16:40 | comment | added | Gil Kalai | I like this problem although I do not understand what precisely is the problem. (Of course there are various other not as good construction that were discovered before Behrend.) It is interesting to compare the greedy algorithm with a random construction (if the size is < n^{1/3} the expected number of 3-term AP is <1). We can also consider "large deviation heuristic" which predicts that if (1-p^3)^{n^2} (n choose pn) >>1 there is a set of size pn without 3-term AP. This will suggest another exponent. (but very far from the constructions). | |
| Jan 1, 2011 at 20:46 | comment | added | Seva | I am likely to miss something very basic, but why "if we try to construct such a nonaveraging subset "naively" and "greedily", we obtain a Cantor subset (the integers whose ternary expansion does not contain a 1)"? If we start with $1$, then we already have the "non-Cantor" element $1$ in our set. If you start with $2$, then, to continue greedily, you have to include $3$, which is a non-Cantor number again, etc. | |
| Jan 1, 2011 at 17:14 | history | edited | Kevin O'Bryant | CC BY-SA 2.5 |
corrected statement of Behrend's bound
|
| Jan 1, 2011 at 14:12 | comment | added | fedja | -----It is not clear to me, however, that it will be better for all large enough $n$---- What do you mean? You have power on full $\mathbb N$ versus subpower on a set of positive lower density. The latter wins for all large $n$ hands down. I agree that it is not very explicit though. | |
| Jan 1, 2011 at 9:18 | comment | added | Ewan Delanoy | @fedja : it is obvious that we may construct an infinite set that does better than the Cantor set for infinitely many $n$. It is not clear to me, however, that it will be better for all large enough $n$. In other words, the miscellaneous spheres we will obtain for a fast-growing sequence (say, the powers of 5) do not have to form a "coherent whole". | |
| Jan 1, 2011 at 9:13 | history | edited | Ewan Delanoy | CC BY-SA 2.5 |
added 154 characters in body
|
| Jan 1, 2011 at 7:39 | comment | added | David Feldman | Perhaps the right question asks how high the density can get as a function of how often we have the option to skip the greedy choice? | |
| Dec 31, 2010 at 21:54 | comment | added | fedja | The formal answer is "Yes, of course: just do Behrend's construction on intervals $5^k,2\cdot 5^k$ and skip the rest". You certainly meant something more interesting than that, but I am at loss as to how to state the question to eliminate such "parasitic answers". The word "elementary" might be the key but what is so non-elementary about projecting a sphere? | |
| Dec 31, 2010 at 21:23 | history | asked | Ewan Delanoy | CC BY-SA 2.5 |