On sum-product representations in Zq\Bbb Z_q

  • Mei-Chu Chang

    University of California, Riverside, United States


The purpose of this paper is to investigate efficient representations of the residue classes modulo qq, by performing sum and product set operations starting from a given subset AA of Zq\mathbb Z_q. We consider the case of very small sets AA and composite qq for which not much seemed known (nontrivial results were recently obtained when qq is prime or when logAlogq\log |A| \sim \log q). Roughly speaking we show that all residue classes are obtained from a kk-fold sum of an rr-fold product set of AA, where rlogqr\ll \log q and logklogq\log k \ll \log q, provided the residue sets πq(A)\pi_{q'} (A) are large for all large divisors qq' of qq. Even in the special case of prime modulus qq, some results are new, when considering large but bounded sets AA. It follows for instance from our estimates that one can obtain rr as small as r\xfraclogqlogAr\sim\xfrac {\log q}{\log|A|} with similar restriction on kk, 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=HA=H a possibly very small multiplicative subgroup, bounds on exponential sums and lower bounds on minaZqmaxxH\xfracaxq\min_{a \in \mathbb Z_q^*} \max_{x \in H} \Vert\xfrac {ax}q\Vert are obtained. This is an extension to the results obtained by Konyagin, Shparlinski and Robinson on the distribution of solutions of xm=ax^m = a (mod q)q) to composite modulus qq.

Cite this article

Mei-Chu Chang, On sum-product representations in Zq\Bbb Z_q. J. Eur. Math. Soc. 8 (2006), no. 3, pp. 435–463

DOI 10.4171/JEMS/62