show/hide this revision's text 3 added omega

This is exercise 1.8.1 of Additive Combinatorics.

Problem

Given $A \in Z^+$ a set of $n$ different integers. Prove that there exists $B\subset A$, $|B| = \Omega ( \log n$, n )$, s.t. $A \cap 2*B = \emptyset$.

Here, $2*B$ means $\{ a + b | a, b \in B, a \neq b \}$.

Strategies:

The dumb thing to try is $P(x \in B) = \frac{\log n}{n}$. Unfortunately, the expected value of $A \cap 2B = \Theta(\log^2 n)$, which is achievable via this example:

$A = ( N + [1 .. k]) \cup (2N + [1..k]) \cup (3M + [1 .. 2k])$

Thus, we can't just uniformly, independently, sample the elements of $B$ from $A$.

The next thing to try is to "segment" $A$ into regions of powers of to, i.e. $[1, 2), [2, 4), [4, 8), ... $. Then try to reason about how many elements to pick from each segment. Nothing interesting has happened from this yet.

Question:

What should I be looking for to solve this problem? (This problem comes from the section on Thin Bases, and the chapter on the Probabilistic Method).
show/hide this revision's text 2 added 64 characters in body; edited title

There exists B subset A, |B| = log n, A \cap 2B 2*B = \emptyset

This is exercise 1.8.1 of Additive Combinatorics.

Problem

Given $A \in Z^+$ a set of $n$ different integers. Prove that there exists $B\subset A$, $|B| = \log n$, s.t. $A \cap 2B 2*B = \emptyset$.

Here, $2*B$ means $\{ a + b | a, b \in B, a \neq b \}$.

Strategies:

The dumb thing to try is $P(x \in B) = \frac{\log n}{n}$. Unfortunately, the expected value of $A \cap 2B = \Theta(\log^2 n)$, which is achievable via this example:

$A = ( N + [1 .. k]) \cup (2N + [1..k]) \cup (3M + [1 .. 2k])$

Thus, we can't just uniformly, independently, sample the elements of $B$ from $A$.

The next thing to try is to "segment" $A$ into regions of powers of to, i.e. $[1, 2), [2, 4), [4, 8), ... $. Then try to reason about how many elements to pick from each segment. Nothing interesting has happened from this yet.

Question:

What should I be looking for to solve this problem? (This problem comes from the section on Thin Bases, and the chapter on the Probabilistic Method).
show/hide this revision's text 1

There exists B subset A, |B| = log n, A \cap 2B = \emptyset

This is exercise 1.8.1 of Additive Combinatorics.

Problem

Given $A \in Z^+$ a set of $n$ different integers. Prove that there exists $B\subset A$, $|B| = \log n$, s.t. $A \cap 2B = \emptyset$.

Strategies:

The dumb thing to try is $P(x \in B) = \frac{\log n}{n}$. Unfortunately, the expected value of $A \cap 2B = \Theta(\log^2 n)$, which is achievable via this example:

$A = ( N + [1 .. k]) \cup (2N + [1..k]) \cup (3M + [1 .. 2k])$

Thus, we can't just uniformly, independently, sample the elements of $B$ from $A$.

The next thing to try is to "segment" $A$ into regions of powers of to, i.e. $[1, 2), [2, 4), [4, 8), ... $. Then try to reason about how many elements to pick from each segment. Nothing interesting has happened from this yet.

Question:

What should I be looking for to solve this problem? (This problem comes from the section on Thin Bases, and the chapter on the Probabilistic Method).