0
$\begingroup$

I am struggling with 1.11 exercise from the George Shakan "Discrete Fourier Transform".

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\}$$

My main idea is prove that
$$|(A+A).(A+A)+A.A+A.A| \geq q$$ I tried with Garaev's Theorem:

Let $A \subset \mathbb{Z}/q\mathbb{Z}$ be any nonempty set not containing zero. Then $$\text{max}\{|A+A|,|A.A|\}\geq\text{min}\{\frac{\sqrt{q|A|}}{\sqrt2},\frac{|A|^2}{2\sqrt{q}}\}$$

So I'm thinking about two cases: $|A+A| = \text{max}\{|A+A|,|A.A|\}$ and $|A.A| = \text{max}\{|A+A|,|A.A|\}$
With each, I estimate one part of the left hand side.
For example, with $|A+A| = \text{max}\{|A+A|,|A.A|\}$, I will estimate $|(A+A).(A+A)|$ and try to prove that $|(A+A).(A+A)| \geq q$
Using Garaev's, in this case I have $$|A+A|\geq\text{min}\{\frac{\sqrt{q|A|}}{\sqrt2},\frac{|A|^2}{2\sqrt{q}}\}$$ Since $|A|>\sqrt2q^{5/8}$ as condition, then $$|A+A|\geq\text{min}\{\frac{q^{13/16}}{2^{1/4}},q^{3/4}\}$$ With $q \geq 16, q^{3/4}$ is smaller, so I use it as min here, because the other case is finite.
But then, using the same techniques as the author, I can only prove that $|(A+A).(A+A)| \geq \frac{q}{2}$, which is not large enough and I can't estimate the rest part, too.
I'm wondering if my way of proving this is true or not. Hopefully, someone can help. Thanks in advance!

I wrote down my proof here:
https://drive.google.com/file/d/1cnHfJDlO3eYdskxoFb_sLytlhZSsybQg/view?usp=sharing
And this is George Shakan's paper:
https://gshakan.files.wordpress.com/2016/04/discretefouriertransform1.pdf

Improve this question
$\endgroup$
6
  • $\begingroup$ have you tried this? let $ B = A+A, C = A.A$ and set $b:= |B|,c:= |C|$. by 1.10 we have $bc \ge \min\{q|A|/2, |A|^4/4q\}$. now let $f(b)$ be a lower bound for $|B.B|$ when $|B|\ge b$. similarly let $g(c)$ be a lower bound for $|C+C|$ when $|C|\ge c$. by Cauchy-Davenport it suffices to show $f(b)+g(c)\ge q$ (given the lower bound on $bc$). $\endgroup$
    – Zach Hunter
    May 28, 2022 at 19:39
  • $\begingroup$ actually looking at your argument, $q/2$ seems to be a rather weak lower bound given the inequality. shouldn’t you be able to deduce $|(A+A).(A+A)|\ge q-q^{3/4}$? $\endgroup$
    – Zach Hunter
    May 28, 2022 at 19:44
  • 1
    $\begingroup$ @ZachHunter Thanks! I didn't think about using Cauchy-Davenport to compare $|B.B + C + C|$ with $|B.B| + |C+C|$, so I had to split it into two cases. I will try this way, hope it will work. $\endgroup$
    – Sei
    May 30, 2022 at 3:58
  • $\begingroup$ @ZachHunter i'm wondering which part of my argument make the result be a weak lower bound? Is there any better set of solutions S while double-counting is unnecessary? $\endgroup$
    – Sei
    Jun 3, 2022 at 6:47
  • $\begingroup$ literally just looking at the final two lines. if you have that $|B.B| + q^{1/4}\sqrt{|B.B|} -q > 0$, then $|B.B| > q- q^{3/4}$ (since $|sqrt{|B.B|}\le q$ always holds). and this is considerably better than just saying it has size $q/2$. $\endgroup$
    – Zach Hunter
    Jun 3, 2022 at 6:56

0

Reset to default

Your Answer

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