1
$\begingroup$

There is an exercise in a paper by George Shakan

George Shakan, Discrete Fourier Transform

say that


Let $A \subset \mathbb{Z}/q\mathbb{Z}$ be any set not containing zero with $|A|>\sqrt2q^{5/8}$. Show that: $$(A+A).(A+A)+A.A+A.A = \mathbb{Z}/q\mathbb{Z}$$ with $$A+B=\{a+b: a\in A, b \in B\}$$ and $$A.B=\{ab: a\in A, b \in B\}$$


so, is there any more ways to expand $\mathbb{Z}/q\mathbb{Z}$? And if there is, which key word I can use to find papers of them?

Thanks.

$\endgroup$
2
  • 1
    $\begingroup$ Representation / decomposition of elements of $Z/pZ$? Another example: if $p$ is prime, every elements of $Z/pZ$ can be written as the sum of two squares. $\endgroup$ Commented Jun 20, 2022 at 11:38
  • $\begingroup$ @ChristopheLeuridan I mean some other variants of expressions for the left side. For example, in the book of T. Tao and V. Vu "Additive Combinatorics" there is a Lemma: Let $F$ be a finite field, and let $A$ be a subset of $F$\{0} such that $|A| > |F|^{3/4}$. Then $3(A.A) = A.A + A.A + A.A = F.$ I want some ways to expand $\mathbb{Z}/q\mathbb{Z}$ to a function of $A.A$ and $A+A$ like this. $\endgroup$
    – Sei
    Commented Jun 20, 2022 at 12:32

1 Answer 1

1
$\begingroup$

There have been a few results of this type published, although I am struggling to remember where to find them right now.

There is a paper of Glibichuk and Rudnev (here is an arxiv version, and here is the published version) which shows that, for any $A,B \subset \mathbb F_q$ $$ |A||B| \geq q \Rightarrow 10A \cdot B = \mathbb F_q. $$ Here $10A \cdot B=A\cdot B+A\cdot B+\dots+A\cdot B$, as in your comment above. I am pretty sure there is a paper of Iosevich and Rudnev (and possibly other authors) which proves that $$ |A| \gg q^{3/4} \Rightarrow AA+AA=\mathbb F_q. $$ Or something close to this statement. Perhaps someone else will be able to dig out the reference.

In Theorem 30 of this long paper, it was proven that, for $A \subset \mathbb F_p$ with $p$ prime, $$ |A| \gg p^{3/5} \Rightarrow (A-A)(A-A)(A-A)(A-A)= \mathbb F_p. $$

I think there are many other variants of these kinds of results out there. A related and somewhat easier question is to consider the threshold for which these expanders are guaranteed to generate a positive proportion of the elements of the finite field. But this answer is already too long.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .