# On sum-product representations in $Z_{q}$

### Mei-Chu Chang

University of California, Riverside, United States

## 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 $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 $g∣A∣∼gq$). 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≪gq$ and $gk≪gq$, 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∼gq/g∣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∈Z_{q}}max_{x∈H}∥ax/q∥$ 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$.

## Cite this article

Mei-Chu Chang, On sum-product representations in $Z_{q}$. J. Eur. Math. Soc. 8 (2006), no. 3, pp. 435–463

DOI 10.4171/JEMS/62