Combinatorics Seminar
When: Sunday, March 11, 10am
Where: Schreiber 309
Speaker: Chaim Even Zohar, Hebrew University
Title: Compression Methods and Sums of Sets in (Z_2)^n
Abstract:
Denote by F(K) the maximum of the ratio between the
cardinality of the span of A and
that of A
over all subsets A of (Z_2)^n
with |A+A|/|A| <= K. Using methods of subset compression, Green and
Tao and Konyagin found F(K) = Theta( poly(K) 4^K ). Elaborating on
these methods, we explicitly calculate F(K), and in particular show
it is Theta( 4^K / K ). More generally, we give a fairly tight lower
bound on |A+B|, where A and B are two generating subsets of (Z_2)^n
of
prescribed cardinalities.