Positive projections

Positive projections

Tue, 07/02/2012
14:30 		Imre Leader (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Positive projections
If $ A $ is a set of $ n $ positive integers, how small can the set $ \{ x/(x,y) : x,y \in A \} $ be? Here, as usual, $ (x,y) $ denotes the highest common factor of $ x $ and $ y $. This elegant question was raised by Granville and Roesler, who also reformulated it in the following way: given a set $ A $ of $ n $ points in the integer grid $ {\bf Z}^d $, how small can $ (A-A)^+ $, the projection of the difference set of $ A $ onto the positive orthant, be? Freiman and Lev gave an example to show that (in any dimension) the size can be as small as $ n^{2/3} $ (up to a constant factor). Granville and Roesler proved that in two dimensions this bound is correct, i.e. that the size is always at least $ n^{2/3} $, and they asked if this holds in any dimension. After some background material, the talk will focus on recent developments. Joint work with Béla Bollobás.