# On sum-product representations in ${\mathbb{Z}}_{q}$

Journal of the European Mathematical Society (2006)

- Volume: 008, Issue: 3, page 435-463
- ISSN: 1435-9855

## Access Full Article

top## Abstract

top## How to cite

topChang, Mei-Chu. "On sum-product representations in $\mathbb {Z}_q$." Journal of the European Mathematical Society 008.3 (2006): 435-463. <http://eudml.org/doc/277412>.

@article{Chang2006,

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^\{\prime \}\}(A)$ are large for all large divisors $q^\{\prime \}$ 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$.},

author = {Chang, Mei-Chu},

journal = {Journal of the European Mathematical Society},

language = {eng},

number = {3},

pages = {435-463},

publisher = {European Mathematical Society Publishing House},

title = {On sum-product representations in $\mathbb \{Z\}_q$},

url = {http://eudml.org/doc/277412},

volume = {008},

year = {2006},

}

TY - JOUR

AU - Chang, Mei-Chu

TI - On sum-product representations in $\mathbb {Z}_q$

JO - Journal of the European Mathematical Society

PY - 2006

PB - European Mathematical Society Publishing House

VL - 008

IS - 3

SP - 435

EP - 463

AB - 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^{\prime }}(A)$ are large for all large divisors $q^{\prime }$ 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$.

LA - eng

UR - http://eudml.org/doc/277412

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.