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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.