On sum-product representations in $\Bbb Z_q$

Source abstract

The purpose of this paper is to investigate efficient representations of the residue classes modulo q , by performing sum and product set operations starting from a given subset A of \mathbb Z_q . We consider the case of very small sets A and composite q for which not much seemed known (nontrivial results were recently obtained when q is prime or when \log |A| \sim \log q ). Roughly speaking we show that all residue classes are obtained from a k -fold sum of an r -fold product set of A , where r\ll \log q and \log k \ll \log q , provided the residue sets \pi_{q'} (A) are large for all large divisors q' of q . Even in the special case of prime modulus q , some results are new, when considering large but bounded sets A . It follows for instance from our estimates that one can obtain r as small as r\sim\log q/\log|A| with similar restriction on k , something not covered by earlier work of Konyagin and Shparlinski. On the technical side, essential use is made of Freiman's structural theorem on sets with small doubling constant. Taking for A=H a possibly very small multiplicative subgroup, bounds on exponential sums and lower bounds on \min_{a \in \mathbb Z_q^*} \max_{x \in H} \Vert ax/q\Vert are obtained. This is an extension to the results obtained by Konyagin, Shparlinski and Robinson on the distribution of solutions of x^m = a (mod q) to composite modulus q .