Write My Paper Button

WhatsApp Widget

ASK A QUESTION

additive combinatorics

need only no 4

Problem Set 1

1. (Just checking you can use Cauchy-Schwarz) Suppose that S and T are nonempty
finite sets and ρ a map from S to T show that


t

|ρ−1(t)|2 ≥ |S|
2

|T |
.

(This was the final step in my proof of the combinatorial Cauchy-Schwarz inequality that
I left to you.)

2. (Applying Balog-Szemeredi-Gowers 1) Suppose that A is a nonempty finite subset
of an abelian group Z. Suppose that E(A) = 1

K . Show that there is a constant C
independent of K so that there exist sets A1, A2 ⊂ A with

|A1| >
|A|
CK

,

|A2| >
|A|
CK

,

and
|A1 +A2| ≤ CK8|A|.

(I basically indicated how you can do this in lecture.)

3. (Applying Balog-Szemeredi-Gowers 2) With the same hypotheses as problem 2,
show there is a constant C independent of K (but maybe dependent on the base of log
that appears in this problem) and A1, A2 ⊂ A with

|A1| >
|A|

CK(1 + logK)
,

|A2| >
|A|

CK(1 + logK)
,

and
|A1 +A2| < CK3(1 + logK)5|A|.

Hint: When choosing G, sort together those pairs whose sums have approximately the
same number of representations. If you get a different upper bound than I did, it could
mean that I screwed up this problem. In that case, prove the best upper bound you can.

4. (Applying Balog-Szemeredi-Gowers 3) In both problems 2 and 3, you are given an
upper bound for |A1 +A2|. Can you get a reasonable upper bound for |A1 +A1|. An upper
bound is reasonable if it is a constant times a power of K times a power of (1 + logK) so
for example, the upper bounds you got for |A1 +A2| in problems 2 and 3 were reasonable.

1

C

5. (This is problem 6.4.3 from Tao-Vu.) Let G = G(A, B, E) be a bipartite graph.
Here A

and B are the parts and E is the set of edges, which we’ve been calling G. Here let
|A| = |B| = N with N sufficiently large. Show that there is a function f from (1, ∞) to

2

(1, ∞) so that if |E| > N then G contains a complete bipartite subgraph with at least
f(C) logN vertices in each part. Show that logN is the optimal dependence in N for such
a result.

2

additive combinatorics
Scroll to top