The purpose of this paper is to investigate efficient representations of the residue classes modulo , by performing sum and product set operations starting from a given subset of . We consider the case of very small sets and composite for which not much seemed known (nontrivial results were recently obtained when is prime or when ). Roughly speaking we show that all residue classes are obtained from a -fold sum of an -fold product set of , where and , provided the residue sets are large for all large divisors of . Even in the special case of prime modulus , some results are new, when considering large but bounded sets . It follows for instance from our estimates that one can obtain as small as with similar restriction on , 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 possibly very small multiplicative subgroup, bounds on exponential sums and lower bounds on are obtained. This is an extension to the results obtained by Konyagin, Shparlinski and Robinson on the distribution of solutions of (mod to composite modulus .
Cite this article
Mei-Chu Chang, On sum-product representations in . J. Eur. Math. Soc. 8 (2006), no. 3, pp. 435–463DOI 10.4171/JEMS/62