Positive projections
Abstract
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\'ela Bollob\'as.