Timeline for There exists B subset A, |B| = log n, A \cap 2*B = \emptyset
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 15, 2012 at 18:33 | answer | added | Noam D. Elkies | timeline score: 5 | |
| Sep 12, 2012 at 19:56 | answer | added | Seva | timeline score: 5 | |
| Sep 12, 2012 at 1:58 | comment | added | Gerhard Paseman | Unknown: indeed that set foils the dumb strategy, but then says that there are no elements between n and 2n-1, so maybe try the logn elements just below n. Gerhard "Ask Me About System Design" Paseman, 2012.09.11 | |
| Sep 11, 2012 at 23:12 | comment | added | user26147 | @Greg Martin: I don't buy this intuition. Thin bases are bases where $r_{k,B}(n) = O(\log n)$, yet I don't see any "doubling" going on in the proof. | |
| Sep 11, 2012 at 23:03 | comment | added | user26147 | @Gerhard: Consider the set [1 ... n] + {2n-1}. | |
| Sep 11, 2012 at 21:04 | comment | added | Greg Martin | My dumb thing to try first would be to build the set $B$ recursively. Something about the desired bound $log n$ makes me think that every time we add an element to $B$, something doubles, and life is okay as long as we stay less than $n$. | |
| Sep 11, 2012 at 16:05 | comment | added | Gerhard Paseman | The dumb thing I would try first is to add the largest log n elements, and analyze why that might not work and what to do when it doesn't. Gerhard "Dumb Ideas Are Often Quick" Paseman, 2012.09.11 | |
| Sep 11, 2012 at 15:44 | comment | added | user9072 | I added a missing Omega. I am not sure if OP just wanted to be very polite or if there might now be some confusion regarding notation, thus and since I got briefly puzzled when looking this up: what is written in the book (or at least some version thereof) is the original version OP posted (including sums of equal elements), however this a known misprint. The current version (with the added Omega) is the one one gets when applying the correction indicated in the errata. | |
| Sep 11, 2012 at 15:29 | history | edited | user9072 | CC BY-SA 3.0 |
added omega
|
| Sep 11, 2012 at 6:47 | history | edited | user26147 | CC BY-SA 3.0 |
added 64 characters in body; edited title
|
| Sep 11, 2012 at 6:46 | comment | added | user26147 | @Noam: I misread the exercise. By 2B, I meant to say "the sum of two distinct elements of B". | |
| Sep 11, 2012 at 5:00 | comment | added | Noam D. Elkies | Does the notation $2B$ mean $\lbrace 2b: b \in B \rbrace$ or $\lbrace b + b': b,b' \in B \rbrace$? Even if it's the former, the result seems false as stated: just let $A = \lbrace 1, 2, 4, 8, \ldots, 2^{n-1} \rbrace$, and then the only $B \subset A$ such that $A \cap 2B = \emptyset$ are $\emptyset$ and $\lbrace 2^{n-1} \rbrace$. Is there some additional hypothesis on $A$? | |
| Sep 11, 2012 at 2:23 | history | asked | user26147 | CC BY-SA 3.0 |