On sum-product representations in ℤq.

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 ℤq. We consider the case of very small sets A and composite q for which not much seemed known (non-trivial results were recently obtained when q is prime or when log ∣A∣ ∼ 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 ⟪ log q and log k ⟪ log q, provided the residue sets π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 ∼ 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 mina∊ℤq* maxx∊H ∥ax/q∥ are obtained. This is an extension to the results obtained by Konyagin, Shparlinski and Robinson on the distribution of solutions of xm = a (mod q) to composite modulus q. [ABSTRACT FROM AUTHOR]