Proof Suppose not. Then for a certain $\xi \in {\mathbb {Z}}^n_{q}$ and $q_1|q$ , $q_1 \geqslant M$ , we find ${A' := A \cap \pi ^{-1}_{q_1} (\xi )}$ with $|A'|\geqslant \frac {|A|}{q^{1-\varepsilon }_1}$ . Clearly, $|\pi _{q_1} (A')| = 1$ and the density of $A'$ in the appropriate shift of ${\mathbb {Z}}^n_{q/q_1}$ is at least $\delta q^\varepsilon _1 \geqslant \delta M^{\varepsilon }$ . Hence, applying the same procedure to the set $A'$ and to the new module $q/q_1$ , we see that our algorithm must stop after at most s steps. Notice that condition (2.1) holds automatically if $\tilde {q} \geqslant \delta ^{-\varepsilon ^{-1}}$ , and hence, at the final step of our procedure, we find a set $A_* \subset A$ , $|\pi _{q/q_*} (A_*)| = 1$ , having all required properties. This completes the proof.

Proof Let $q=p_1^{\rho _1} \dots p_t^{\rho _t}$ , where $p_j$ are different primes, $p_1<\dots <p_t$ . Also, let $M\geqslant 2$ , $\varepsilon \in (0,1)$ be parameters, which we will choose later. First of all, we remove all divisors less than M from q. More precisely, for any $p_j$ , $j\in [t]$ let $\gamma _j \leqslant \rho _j$ be the maximal nonnegative integer such that $p^{\gamma _j}_j \leqslant M$ . Clearly, $\gamma _1 \geqslant \gamma _2 \geqslant \dots \gamma _t \geqslant 0$ and let $t_0 \leqslant t$ be the maximal j with $\gamma _j \neq 0$ . Thus $t_0 \leqslant \pi (M)$ . Now, we define

(2.6) $$ \begin{align} Q_1 := \prod_{j=1}^{t_0} p_j^{\gamma_j} \leqslant M^{t_0} \leqslant \min\{ M^{\pi (M)}, M^{\omega(q)} \}, \end{align} $$

and take $A_1 \subseteq A$ such that a shift of $A_1$ belongs to ${\mathbb {Z}}_{q/Q_1}$ and has density at least $\alpha $ . In particular, $|\pi _{Q_1} (A_1)|=1$ and of course such a shift exists by the Dirichlet principle. Similarly, we can do the same with the set B so as not to lose the density. Secondly, we apply Lemma 2 with $n=1$ , $A=A_1$ to regularize the set $A_1$ and find a set $A_* \subseteq A_1$ and a module $q_*$ that satisfies (2.1) and all other restrictions. Again, using the Dirichlet principle, we take $B_* \subseteq B$ such that the density of B does not decrease. Let $\lambda \in {\mathbb {Z}}_{q_*}$ be an arbitrary number and we first suppose that $\lambda \in {\mathbb {Z}}^*_{q_*}$ . To prove $\lambda \in (A-A)(B-B),$ it is enough to show that $\lambda \in (A_*-A_*)(B_*-B_*)$ or, equivalently, in terms of the Fourier transform, it suffices obtain the inequality

(2.7) $$ \begin{align} \frac{|A_*|^2 |B_*|^2}{q_*}> \frac{1}{q_*} \sum_{r\neq 0} |\widehat{B}_* (r)|^2 \cdot \sum_{a_1,a_2\in A_*} e_{q_*} \left(\frac{\lambda r}{a_1-a_2} \right) := \sigma . \end{align} $$

Now clearly,

(2.8) $$ \begin{align} \sigma \leqslant \frac{1}{q_*} \sum_{q_2|q_*,\, q_2>1}\, \sum_{z\in {\mathbb{Z}}^*_{q_2}} |\widehat{B}_* (zq_* q^{-1}_2)|^2 \left| \sum_{a_1,a_2\in A_*} e_{q_2} \left(\frac{\lambda z}{a_1-a_2} \right) \right| . \end{align} $$

In terms of the Kloosterman sums

$$\begin{align*}K_q (\lambda,r) := \sum_{x\in {\mathbb{Z}}^*_{q}} e_{q} \left( \frac{\lambda}{x} + rx\right) \end{align*}$$

and the density function

(2.9) $$ \begin{align} \eta_{q_2} (\xi) := |\{ a\in A_* ~:~ a \equiv \xi\quad \pmod {q_2} \}|, \end{align} $$

one has (recall that $\lambda \in {\mathbb {Z}}^*_{q_*}$ and $z \in {\mathbb {Z}}^*_{q_2}$ )

(2.10) $$ \begin{align} &\sum_{a_1,a_2\in A_*} e_{q_2} \left(\frac{\lambda z}{a_1-a_2} \right) =\\&\quad \sum_{\xi_1,\xi_2 \in {\mathbb{Z}}_{q_2}} \eta_{q_2}(\xi_1) \eta_{q_2} (\xi_2) e_{q_2} \left(\frac{\lambda z}{\xi_1-\xi_2} \right) = q^{-1}_2 \sum_{\xi \in {\mathbb{Z}}_{q_2}} |\widehat{\eta}_{q_2} (\xi)|^2 K_{q_2} (\lambda z, \xi) \nonumber\end{align} $$

$$\begin{align*}\leqslant 2 \sqrt{q_2} \tau(q_2) \| \eta_{q_2} \|_2^2 . \end{align*}$$

In the last line, we have applied the well-known bound for the Kloosterman sum and the Parseval identity. Now, to estimate $\| \eta _{q_2}\|_2^2$ , we use the regularity property of $A_*$ and derive

(2.11) $$ \begin{align} \| \eta_{q_2}\|_2^2 \leqslant \| \eta_{q_2}\|_\infty \| \eta_{q_2}\|_1 \leqslant \frac{|A_*|^2}{q^{1-\varepsilon}_2} . \end{align} $$

Further, let us obtain a lower bound for divisors $q_2$ . Since $|\pi _{Q_1} (A_1)|=1$ , it follows that for all $q_1|Q_1$ , we have

$$\begin{align*}\frac{1}{q_1} \sum_{\xi \in {\mathbb{Z}}_{q_1}} |\widehat{\eta}_{q_1} (\xi)|^2 K_{q_1} (\lambda z, \xi) = \frac{|A_*|^2}{q_1} \sum_{\xi \in {\mathbb{Z}}_{q_1}} K_{q_1} (\lambda z, \xi) = 0 . \end{align*}$$

Thus, one can see that summations in (2.8) is taken over $q_2 \geqslant M$ . Choosing $\varepsilon =1/4$ , say, and using the last fact, we get in view of the Parseval identity that

$$\begin{align*}\sigma \ll M^{-1/4} \frac{|A_*|^2}{q_*} \sum_{q_2|q_*,\, q_2>1}\, \sum_{z\in {\mathbb{Z}}^*_{q_2}} |\widehat{B}_* (zq_* q^{-1}_2)|^2 \leqslant M^{-1/4} |A_*|^2 |B_*| . \end{align*}$$

Returning to (2.7), we obtain a contradiction provided $|B_*| \gg q_* M^{-1/4}$ . In other words, we have for a certain $s\geqslant 0$ , $\alpha M^{s/4}> 1$ that

$$\begin{align*}|B| M^{s/4} \ll q M^{-1/4}, \end{align*}$$

and this implies $M \ll \beta ^{-4}$ . Thus, in view of our restriction to the divisors of $q_*$ , the condition $\alpha \geqslant \beta $ , the first bound for $Q_1$ from (2.6), and the bound for s, which follows from Lemma 2, we get

$$\begin{align*}d \ll M^{\pi (M)} \exp (O(\log^2 (1/\alpha) / \log (1/\beta)) \ll \exp(O(\beta^{-4})) \end{align*}$$

as required.

Now, let $\lambda \in {\mathbb {Z}}_{q_*}$ be an arbitrary element. Write $\lambda = q' \lambda '$ , where $q' |q$ and $\lambda '\in {\mathbb {Z}}^*_{q_*/q'}$ . Using the Dirichlet principle, choose a subset of $B' \subseteq B_*$ of density at least $\beta $ such that all elements of a shift of $B'$ are divisible by $q'$ . Then our inclusion can be rewritten as $\lambda ' \in (A_*-A_*)(B'-B')$ modulo $q_*/q'$ and we can apply the arguments above replacing module $q_*$ to $q_*/q'$ .

To obtain (2.5), we use the second bound for $Q_1$ from (2.6) and derive as above

$$\begin{align*}d \ll M^{\omega (q)} \exp (O(\log (1/\beta))) \ll \exp (O(\omega (q) \log (1/\beta))) . \end{align*}$$

This completes the proof.

Proof We start with (3.3). The proof follows the arguments of the proof of Theorem 2.3, and thus, we use the notation from this result. In particular, writing $q=p_1^{\rho _1} \dots p_t^{\rho _t}$ , $t=\omega (q)$ with $\rho _j=1$ , $j\in [t]$ we define $Q_1 = \prod _{j=1}^s p_j$ such that (2.6) holds and further we take $\lambda \in {\mathbb {Z}}^*_q$ . The only difference is that one should use Lemma 2 with $n=2$ to regularize the two-dimensional set $\mathcal {A}$ and let $\varepsilon =1/4$ . For a moment, we assume that $M \geqslant 100 t^2$ , say, and we will choose the parameter M later. Finally, with some abuse of the notation, we do not use new letters $\mathcal {A}_*, \mathcal {B}_*$ , $q_*$ below but the old ones $\mathcal {A}, \mathcal {B},$ and q (in other words, one can think that $\mathcal {A}$ is a regularized set already). Also, we utilize the fact that ${\mathbb {Z}}_q = {\mathbb {Z}}_{p^{\rho _1}_1} \times \dots \times {\mathbb {Z}}_{p^{\rho _t}_t} = {\mathbb {Z}}_{p^{}_1} \times \dots \times {\mathbb {Z}}_{p^{}_t}$ thanks the Chinese remainder theorem.

Now, for $a = (a_1,a_2)$ and $b=(b_1,b_2),$ let us write $I(a,b) = 1$ if the pair $a,b$ satisfies (3.2) and $I(a,b) = 0$ , otherwise. Then clearly,

(3.6) $$ \begin{align} N_{\mathcal{A}, \mathcal{B}} (\lambda) = \sum_{a\in \mathcal{A}, b\in \mathcal{B}} I(a,b) . \end{align} $$

Without loosing of the generality, we assume that $\lambda =1$ . Obviously, $I(a,b) = I(b,a)$ and we can rewrite the matrix $I(a,b)$ as $I(a,b) = \sum _{j=1}^{q^2} \mu _j u_j (a) \overline {u}_j (b)$ , where $\mu _j$ are eigenvalues and $u_j (x)$ are correspondent normalized eigenfunctions of I. One can easily check that $u_1 (x) = q^{-1} (1,\dots , 1)$ , $\|u_1\|_2 = 1$ and $\mu _1 = |{\mathbb {Z}}^*_q| = \varphi (q)$ . Writing $I'(a,b) = I(a,b) - \mu _1 u_1 (a) \overline {u}_1 (b)$ , we obtain

(3.7) $$ \begin{align} N_{\mathcal{A}, \mathcal{B}} (\lambda) - \frac{|\mathcal{A}| |\mathcal{B}| \varphi (q)}{q^2} = \sum_{a\in \mathcal{A}, b\in \mathcal{B}} I'(a,b) := N^{\prime}_{\mathcal{A}, \mathcal{B}} (\lambda) . \end{align} $$

By the Cauchy–Schwarz inequality, we get the following.

Here, $(I')^2$ is the second power of the matrix $I'$ . Similarly, $I^2 (a,a') = \sum _{b} I(a,b) I(a',b)$ and the last quantity coincides with the number of the solutions to the equation

(3.8) $$ \begin{align} a_2 - a^{\prime}_2 = \frac{a^{\prime}_1-a_1}{(a_1+x)(a^{\prime}_1+x)} , \end{align} $$

where $b=(x,y)$ , $a=(a_1,a_2)$ and $a'=(a^{\prime }_1,a^{\prime }_2)$ . Assume that $a\neq a'$ and rewrite our equation (3.8) as

(3.9) $$ \begin{align} x^2 + (a_1+a^{\prime}_1)x + a_1 a^{\prime}_1 + \frac{a_1-a^{\prime}_1}{a_2-a^{\prime}_2} = 0 , \end{align} $$

and its discriminant is $D'(a,a') := (a_1-a^{\prime }_1) (a_2-a^{\prime }_2)^{-1} [(a_1-a^{\prime }_1) (a_2-a^{\prime }_2) - 4]$ . Notice that if $a=a'$ , then we have $\varphi (q)$ solutions to equation (3.8). By $\chi _p$ denote the Legendre symbol modulo a prime p and let $\chi _0$ be the main character (modulo p). We have the identity $\chi _p (x^{-1}) = \chi _p (x)$ , $x\in {\mathbb {Z}}_p^*$ and hence $\chi _p (D'(a,a')) = \chi _p ( (a_1-a^{\prime }_1) (a_2-a^{\prime }_2)^{} [(a_1-a^{\prime }_1) (a_2-a^{\prime }_2) - 4] := \chi _p (D(a,a'))$ . In view of the Chinese remainder theorem, and our choice of the regularized set $\mathcal {A},$ one has

(3.10) $$ \begin{align} I^2 (a,a') = \prod_{j=s+1}^t \left( \chi_{p_j} (D(a,a')) + \chi_0 (D(a,a')) + (p_j-1) \delta_{p_j} (a_1-a^{\prime}_1, a_2-a^{\prime}_2) \right) \end{align} $$

(3.11) $$ \begin{align} = \mathcal{E} (a,a') + \prod_{j=s+1}^t (\chi_0 (D(a,a'))+ (p_j-1) \delta_{p_j} (a_1-a^{\prime}_1, a_2-a^{\prime}_2)) = \mathcal{E} (a,a') + \mathcal{E}' (a,a') , \end{align} $$

where for a positive integer $m,$ we have put $\delta _m (z,w) = 1$ if $z \equiv w \equiv 0 \pmod m$ , and 0 otherwise. Equivalently, writing T for the segment $[s+1,t]$ , one has

$$\begin{align*}\mathcal{E} (a,a') = \sum_{\emptyset \neq S \subseteq T}\, \prod_{j\notin S} (\chi_0 (D(a,a')) + (p_j-1) \delta_{p_j} (a_1-a^{\prime}_1, a_2-a^{\prime}_2)) \cdot \prod_{j\in S} \chi_{p_j} ( D(a,a')) \end{align*}$$

$$\begin{align*}= \sum_{\emptyset \neq S \subseteq T}\, \prod_{j\notin S} w_{p_j} (a,a') \cdot \prod_{j\in S} \chi_{p_j} ( D(a,a')) . \end{align*}$$

Notice that $\mathcal {E} (a,a) = 0$ . From (3.10) and (3.11), it follows that $\mathcal {E} u_1 = 0$ . Indeed, we know that $I^2 u_1 = \mu _1^2 u_1 = \varphi ^2 (q) u_1$ and

(3.12) $$ \begin{align} \sum_a \prod_{j=s+1}^t (\chi_0 (D(a,a'))+ (p_j-1) \delta_{p_j} (a_1-a^{\prime}_1, a_2-a^{\prime}_2)) \end{align} $$

(3.13) $$ \begin{align} = \prod_{j=s+1}^t \left( \sum_{z,w\in {\mathbb{Z}}_{p_j}} \chi_0((zw)^2 - 4zw) + p_j-1 \right) \end{align} $$

(3.14) $$ \begin{align} \qquad= \prod_{j=s+1}^t \left( (p_j-1) \sum_{z\in {\mathbb{Z}}_{p_j}} \chi_0(z^2 - 4z) + p_j-1 \right) = \prod_{j=s+1}^t (p_j-1)^2 = \varphi^2 (q) . \end{align} $$

Hence, in very deed $\mathcal {E} u_1 = 0,$ and thus

(3.15) $$ \begin{align} \sigma = \langle (I')^2 \mathcal{A}, \mathcal{A} \rangle = \langle (I')^2 f_{\mathcal{A}}, f_{\mathcal{A}} \rangle = \langle I^2 f_{\mathcal{A}}, f_{\mathcal{A}} \rangle = \langle \mathcal{E} \mathcal{A}, \mathcal{A} \rangle + \langle \mathcal{E}' f_{\mathcal{A}}, f_{\mathcal{A}} \rangle, \end{align} $$

where $f_{\mathcal {A}} (a) = \mathcal {A} (a) - \langle \mathcal {A}, u_1 \rangle u_1 (a)$ , $\sum _a f_{\mathcal {A}} (a) = 0$ . Let us estimate the term ${r:=\langle \mathcal {E}' f_{\mathcal {A}}, f_{\mathcal {A}} \rangle }$ rather roughly. Since the function $f_{\mathcal {A}}$ is orthogonal to $u_1$ and $\| f_{\mathcal {A}}\|_\infty \leqslant 1$ , it follows that:

$$\begin{align*}|r|= \left| \sum_{a,a'} f_{\mathcal{A}} (a) f_{\mathcal{A}} (a') \prod_{j=s+1}^t \left(1- \delta_{p_j} (D(a,a')) +(p_j-1) \delta_{p_j} (a_1-a^{\prime}_1, a_2-a^{\prime}_2) \right) \right| \end{align*}$$

$$\begin{align*}\leqslant \sum_{\emptyset \neq S\subseteq T} \left| \sum_{a,a'} f_{\mathcal{A}} (a) f_{\mathcal{A}} (a') \prod_{j\in S} (- \delta_{p_j} (D(a,a')) +(p_j-1) \delta_{p_j} (a_1-a^{\prime}_1, a_2-a^{\prime}_2) ) \right| \end{align*}$$

$$\begin{align*}\leqslant 2|\mathcal{A}| q^2 \sum_{n=1}^{t-s}\, \sum_{S\subseteq T,\, |S|=n}\, \prod_{j\in S} \left( \frac{3}{p_j} + \frac{p_j-1}{p^2_j} \right) \leqslant 2|\mathcal{A}| q^2 \sum_{n=1}^{t-s}\, \binom{t-s}{n} \left(\frac{4}{M} \right)^n \end{align*}$$

(3.16) $$ \begin{align} \leqslant 10 |\mathcal{A}| q^2 t M^{-1} . \end{align} $$

Now, returning to the definition of the operator $\mathcal {E} (a,a')$ , recalling estimate (3.8) and using the Cauchy–Schwarz inequality, we obtain

$$\begin{align*}\sigma^2 \leqslant |\mathcal{A}| \sum_{a,a' \in \mathcal{A}} \sum_{x,y} \sum_{\emptyset \neq S_1,S_2 \subseteq T}\, \prod_{i\in S_1,\, j\in S_2} \chi_{p_i} (D((x,y),(a_1,a_2)) \chi_{p_j} (D((x,y),(a^{\prime}_1,a^{\prime}_2)) \end{align*}$$

(3.17) $$ \begin{align} \prod_{i\notin S_1,\, j\notin S_2} w_{p_i} ((x,y),(a_1,a_2)) w_{p_j} ((x,y),(a^{\prime}_1,a^{\prime}_2)) . \end{align} $$

The term with $a \equiv a' \pmod q$ gives us a contribution at most $4^{t} |\mathcal {A}| q^2$ into the last sum (see (3.12)—(3.14) to estimate $\| w_{p_j}\|_1$ for $j\notin S$ and use the trivial fact that $\|\chi _p \|_{\infty } \leqslant 1$ to bound the rest). Now, let $a \neq a' \pmod q$ but $a \equiv a' \pmod {q_*}$ with maximal $q_*|q$ . Thus $q_* \neq q$ and $Q_1|q_*$ . We can write $q_* = q_* (W) = Q_1 \prod _{j\in W} p_j$ for a certain (possibly empty) set $W \subseteq T$ . Let us say that all primes p such that $p|(q/q_*)$ (that is, $p|q$ and $p\notin W$ ) are good. In particular, for all good primes $p,$ one has $p>M$ . Now for a good prime $p,$ the sum above $\sum _{x,y \mod {\mathbb {Z}}_p}\chi _p (D(x,y), (a_1,a_2))$ (or, analogously, the sum $\sum _{x,y \mod {\mathbb {Z}}_p}\chi _p (D(x,y), (a^{\prime }_1,a^{\prime }_2))$ ) is either at most $3p^{3/2}$ by Weil, or the sum over y is p if $\frac {2}{x-a_1} + a_2 = \frac {2}{x-a^{\prime }_1} + a^{\prime }_2$ modulo p. The last equation is nontrivial one by our choice of $p,$ hence it has at most two solutions, and thus, in any case, the sum over $x,y \mod {\mathbb {Z}}_p$ is at most $3p^{3/2} < 3p^2/\sqrt {M}$ . Further, we split the sets $S_1,S_2$ as $S_1 = S^*_1 \bigsqcup G_1$ , $S_2 = S^*_2 \bigsqcup G_2$ , where (possibly empty) sets $G_1, G_2$ correspond to good primes and the sets $S^*_1 \subseteq W$ , $S^*_2 \subseteq W$ correspond to the divisors of $q_* (W)$ . Since $S_1, S_2 \neq \emptyset $ , it follows that either $G_1 \bigcup G_2 \neq \emptyset $ or $S^*_1,S^*_2 \neq \emptyset $ . Using the notation as in (2.9), namely,

(3.18) $$ \begin{align} \eta_{\tilde{q}} (\xi) := |\{ a\in \mathcal{A} ~:~ a \equiv \xi\quad \pmod {\tilde{q}} \}| \,, \quad \quad \tilde{q}|q,\, \xi \in {\mathbb{Z}}^2_{\tilde{q}} , \end{align} $$

we see that the number of pairs $a\equiv a' \pmod {\tilde {q}}$ is exactly $\| \eta _{\tilde {q}} \|_2^2$ for any $\tilde {q} |q$ and one can use bound (2.11) to estimate the last quantity. Now, recalling inequality (2.1) and splitting sum (3.17) according the case $W \neq \emptyset $ or not, we get

$$\begin{align*}\sigma^2 |\mathcal{A}|^{-1} \leqslant \end{align*}$$

(3.19) $$ \begin{align} 4^{t} |\mathcal{A}| q^2 + q^2 \sum_{\emptyset \neq W \subseteq T}\, \sum_{a,a' \in \mathcal{A},\, a \equiv a' \pmod {q(W)}} 4^{|W|} + q^2 \sum_{a,a' \in \mathcal{A}} \sum_{n+m\geqslant 1} \binom{t-s}{n} \binom{t-s}{m} \left(\frac{3}{\sqrt{M}} \right)^{n+m} \end{align} $$

$$\begin{align*}\leqslant 4^{t} |\mathcal{A}|^{} q^2 + q^2 |\mathcal{A}|^{2} \sum_{\emptyset \neq W \subseteq T} 4^{|W|} M^{-3|W|/4} + 4 q^2 |\mathcal{A}|^{2} t^{} M^{-1/2} \ll q^2 |\mathcal{A}|^{2} t^{} M^{-1/2} . \end{align*}$$

Using (3.6), (3.7), (3.8), (3.16), and the Cauchy–Schwarz inequality, we get

(3.20) $$ \begin{align} N_{\mathcal{A}, \mathcal{B}} (\lambda) - \frac{|\mathcal{A}| |\mathcal{B}| \varphi (q)}{q^2} \ll (t^{} M^{-1/2})^{1/4} \cdot |\mathcal{A}|^{3/4} \sqrt{|\mathcal{B}| q} + (t M^{-1})^{1/2} \cdot \sqrt{|\mathcal{A}| |\mathcal{B}|} q . \end{align} $$

We have $\varphi (q) \gg q/\log t,$ and hence after some calculations, we see that $N_{\mathcal {A}, \mathcal {B}} (\lambda )> 0$ provided $M\gg t^{2} \beta ^{-6} \log ^8 t$ . As in Theorem 2.3, one has $Q_1 \leqslant M^t$ , and thus

$$\begin{align*}d \ll \exp ( t \log M ) = \exp (O(t \log t - \log \beta) ) . \end{align*}$$

In the case of prime $q,$ the argument is even simpler because one do not need the regularization, the second term in (3.19) plus the quantity r is negligible, see estimate (3.16). Finally, let $\mathcal {A} = \mathcal {B}$ and if $\lambda \notin {\mathbb {Z}}^*_q$ , then write $\lambda = q' \lambda '$ , where $q' |q$ and $\lambda '\in {\mathbb {Z}}^*_{q_*/q'}$ . Using the Dirichlet principle, choose a subset of $\mathcal {A}' \subseteq \mathcal {A}$ of density at least $\alpha $ such that $|\pi _{q'} (\mathcal {A}')|=1$ . Then the required inclusion (3.4) can be rewritten as

$$\begin{align*}\lambda' \in \{ (a_1-b_1) (a_2 - b_2) ~:~ (a_1,a_2), (b_1,b_2) \in \mathcal{A} \}, \end{align*}$$

and we can apply the arguments above replacing $q_*$ to $q_*/q'$ . This completes the proof.

Proof The argument differs from the proof of Theorem 3.2 in some unimportant details only, so we use the notation from the former result. Indeed, for $a = (a_1,a_2)$ and $b=(b_1,b_2),$ we write $\tilde {I}(a,b) = 1$ if the pair $a,b$ satisfies (3.21) and $\tilde {I}(a,b) = 0,$ otherwise. Calculating $\tilde {I}^2 (a,a')$ , we arrive to the equation

(3.25) $$ \begin{align} a_1^2 - (a^{\prime}_1)^2 + 2(a^{\prime}_1 - a_1) x - a_2^2 + (a^{\prime}_2)^2 + 2(a_2 - a^{\prime}_2) y = 0, \end{align} $$

and hence, we can find x via y or y via x, provided $a\neq a' \pmod q$ . Assuming that $a^{\prime }_2 \neq a_2$ , say, we derive

$$\begin{align*}y= \frac{(a^{\prime}_1)^2-a_1^2 +a_2^2 - (a^{\prime}_2)^2}{2(a_2 - a^{\prime}_2)} + \frac{a_1-a^{\prime}_1}{a_2 - a^{\prime}_2} \cdot x = s + t x , \end{align*}$$

and hence substituting the last expression into (3.21) and computing the discriminant $\tilde {D} (a,a')$ (without loss of the generality, we put $\lambda =1$ ), one obtains

$$\begin{align*}\tilde{D}(a,a') = (t (a_2-s)-a_1)^2 + (1-t)^2 (1+(a_2-s)^2 - a_1^2) \end{align*}$$

(3.26) $$ \begin{align} \quad\qquad= 2t (t-1) (a_2-s)^2 - 2a_1 t(a_2-s) + (1-t)^2 (1-a_1^2) + (a_2-s)^2 + a_1^2 .\!\!\!\!\! \end{align} $$

As in the proof of Theorem 3.2, we consider $\mathcal {E} (a,a')$ , take good primes and so on. The first eigenvalue $\mu _1$ equals the number of the solutions to the equation $x^2-y^2 \equiv 1 \pmod q$ , that is, $\varphi (q)$ again. Also, $\tilde {I}^{2} (a,a) = \mu _1$ and for $a\neq a'$ the quantity $\tilde {I}^{2} (a,a')$ expressed exactly as in (3.10) (with another discriminant $\tilde {D}$ , of course), and thus, one can check that $\mathcal {E} u_1$ vanishes making calculations as in (3.12)—(3.14). Further, as in Theorem 3.2, we apply the standard Weil bound to estimate the sum of characters. For any good prime $p,$ it gives us a nontrivial bound of the form $O(p^{3/2}) = O(p^2/\sqrt {M}),$ and hence, we obtain (3.22) and thus (3.23) by the same argument as at the end of Theorem 3.2 (one can check or see below that all obtained varieties are non–degenerated). Finally, to get (3.24), we need to estimate

$$\begin{align*}\sum_{a,a' \in \mathcal{A}} \sum_{x,y} \chi_{q} (\tilde{D}((x,y),(a_1,a_2))) \chi_{q} (\tilde{D}((x,y),(a^{\prime}_1,a^{\prime}_2))), \end{align*}$$

and by the Weil estimate, it is at most $20 q^{3/2}$ , say, excluding the case $\tilde {D}((x,y),(a_1,a_2))$ is proportional to $\tilde {D}((x,y),(a^{\prime }_1,a^{\prime }_2))$ . In particular, it means that the coefficients of these polynomials are proportional ones and using (3.26) and comparing the coefficients before the highest degrees in x, say, we get $\frac {a_2-2a_1-y}{(y-a_2)^4} = \frac {a^{\prime }_2-2a^{\prime }_1-y}{(y-a^{\prime }_2)^4}$ . Again, thanks to $a \neq a',$ we see that this equation is nontrivial one, and hence, it has at most four solutions. It follows that our sum is at most $4q$ in this case. Thus, as in (3.19) and (3.20), we have

$$\begin{align*}M_{\mathcal{A}, \mathcal{B}} (\lambda) - \frac{|\mathcal{A}| |\mathcal{B}| \varphi (q)}{q^2} \leqslant 3 (q^{3/2} |\mathcal{A}| )^ {1/4} \sqrt{|\mathcal{A}| |\mathcal{B}|} \leqslant 3 q^{7/8} \sqrt{|\mathcal{A}| |\mathcal{B}|} . \end{align*}$$

This completes the proof.

Proof Let $q=p^{\rho _1}_1 \dots p^{\rho _t}_t$ , where $p_j$ are different odd primes and $\rho _j$ are positive integers. By our assumption $p_j \geqslant M$ for all $j\in [t]$ . Without loosing of the generality, one can take $\lambda = -1$ in formula (3.2). Recall that $\mathrm {SL}_2({\mathbb {Z}}_q)$ acts on ${\mathbb {Z}}_q$ via Möbius transformations: $x\to gx = \frac {ax+b}{cx+d}$ , where $g=\left (\begin {array}{cc} a & b \\ c & d \end {array}\right )$ (for composite $q,$ the equivalence is taken over ${\mathbb {Z}}^*_q$ , of course). Since $\mathcal {B} = A\times B,$ we can rewrite our equation (3.2) as

(4.2) $$ \begin{align} a=gb \,, \quad \quad a\in A\,, b\in B\,, g\in G , \end{align} $$

where $G \subset \mathrm {SL}_2 ({\mathbb {Z}}_q)$ is the set of matrices of the form

$$\begin{align*}g= \left( {\begin{array}{cc} -\alpha & \alpha \beta+1 \\ -1 & \beta \\ \end{array} } \right) \,, \quad \quad (\alpha,\beta) \in \mathcal{A} , \end{align*}$$

see [Reference Shkredov17, Section 5] or just make a direct calculation. Clearly, $|G| = |\mathcal {A}|$ . Further by [Reference Shkredov17, Lemma 15], the multiplicative energy $\mathsf {E}(G)$ of the set G, that is,

$$\begin{align*}\mathsf{E}(G) = |\{ (g_1,g_2,g_3,g_4) \in G\times G \times G \times G ~:~ g_1 g_2^{-1} = g_3 g_4^{-1} \}| \end{align*}$$

coincides with the number of the solutions to the system

$$\begin{align*}&\beta_1 - \beta_2 = \beta_3 - \beta_4 := s \,, \quad \quad s(\alpha_1 - \alpha_3) = s(\alpha_2 - \alpha_4) = 0 \,, \\& \alpha_1 - \alpha_2 - \alpha_1 \alpha_2 s = \alpha_3 - \alpha_4 - \alpha_3 \alpha_4 s , \end{align*}$$

where $(\alpha _i,\beta _i) \in \mathcal {A}$ , $i\in [4]$ . Let $s = d s'$ , where d is a divisor of q and $s'$ is coprime to q. Taking $(\alpha _1,\beta _1), (\alpha _4,\beta _4) \in \mathcal {A}$ , we find $\beta _2$ , $\beta _3$ from the first equation and $\alpha _2,\alpha _3$ modulo $q/d$ from the second one. Also, using $\alpha _3$ we can reconstruct $\alpha _2$ from the third equation, provided $d>1$ . In other words, for fixed $d,$ there are $q/d$ possibilities for $s'$ and d possibilities for $\alpha _3$ . Finally, if $d=1$ , then we have at most $q|G|^2$ solutions. Thus, we obtain the bound

(4.3) $$ \begin{align} \mathsf{E}(G) \leqslant |G|^2 \sum_{d|q} \frac{q}{d} \cdot d \leqslant \tau(q) q |G|^2 . \end{align} $$

Now, let us say a few words about representations of the group $\mathrm {SL}_2 ({\mathbb {Z}}_q)$ (see [Reference Bourgain and Gamburd3, Sections 7 and 8]). First of all, for any irreducible representation $\rho _q$ of $\mathrm {SL}_2 ({\mathbb {Z}}_q),$ we have $\rho = \rho _q = \rho _{p^{\rho _1}_1} \otimes \dots \otimes \rho _{p^{\rho _t}_t}$ , and hence, it is sufficient to understand the representation theory for $\mathrm {SL}_2 ({\mathbb {Z}}_{p^n})$ , where p is a prime number and n is a positive integer. Now, by [Reference Bourgain and Gamburd3, Lemma 7.1], we know that for any odd prime, the dimension of any faithful irreducible representation of $\mathrm {SL}_2 ({\mathbb {Z}}_{p^n})$ is at least $2^{-1} p^{n-2} (p-1)(p+1)$ . For an arbitrary $r\leqslant n,$ we can consider the natural projection $\pi _r : \mathrm {SL}_2 ({\mathbb {Z}}_{p^n}) \to \mathrm {SL}_2 ({\mathbb {Z}}_{p^r}),$ and let $H_r = \mathrm {Ker\,} \pi _r$ . One can show that the set $\{ H_r \}_{r\leqslant n}$ gives all normal subgroups of $\mathrm {SL}_2 ({\mathbb {Z}}_{p^n}),$ and hence, any nonfaithful irreducible representation arises as a faithful irreducible representation of $\mathrm {SL}_2 ({\mathbb {Z}}_{p^r})$ for a certain $r<n$ . Anyway, we see that the multiplicity (dimension) $d_\rho $ of any nontrivial irreducible representation $\rho $ of $\mathrm {SL}_2 ({\mathbb {Z}}_{p^n})$ is at least $p/3 \geqslant M/3$ .

Applying estimate (4.3), using the formula for $\mathsf {E}(G)$ via the representations and taking into account, the obtained lower bound for the multiplicities of the representations, we get

$$\begin{align*}\frac{M\| \widehat{G}\|^4_{op}}{3|\mathrm{SL}_2 ({\mathbb{Z}}_q)|} \leqslant \frac{1}{|\mathrm{SL}_2 ({\mathbb{Z}}_q)|} \sum_{\rho} d_\rho \| \widehat{G} (\rho) \widehat{G}^* (\rho) \|_{}^{2} = \mathsf{E}(G) \leqslant \tau(q) q |G|^2 , \end{align*}$$

and hence

(4.4) $$ \begin{align} \| \widehat{G}\|_{op} \leqslant |G| \cdot \left( \frac{3\tau(q)}{M\delta^2} \right)^{1/4} := \frac{|G|}{K} , \end{align} $$

where by $\| \widehat {G}\|_{op}$ , we have denoted the maximum of the operator norm of matrices $\widehat {G} (\rho )$ for all nontrivial representations $\rho $ and $\| \cdot \|$ is the usual Hilbert–Schmidt norm. Thanks to our choice of $M,$ one can see that bound (4.4) is nontrivial, that is, $K>1$ . Returning to (4.2) and using the standard scheme (see, e.g., [Reference Shkredov17, Lemma 13 and Sections 5 and 6]), we obtain

$$\begin{align*}N_{\mathcal{A}, \mathcal{B}} (\lambda) - \frac{|A||B||G| q}{J_2(q)} \leqslant \sqrt{|A||B|} |G| q^{-1/k} , \end{align*}$$

where $k \sim \log q/\log K$ and $|\mathrm {SL}_2 ({\mathbb {Z}}_q)| = q J_2 (q) = q^3 \prod _{p|q} (1-p^{-2})$ . Hence $N_{\mathcal {A}, \mathcal {B}} (\lambda )> 0$ , provided $K \gg (\sqrt {\alpha \beta })^{-O(1)}$ . The last condition is equivalent to $M\gg \tau (q) \delta ^{-2} (\sqrt {\alpha \beta })^{-O(1)}$ . This completes the proof.

Proof Let $S+X = {\mathbb {Z}}_q$ and $|X| = \mathrm {cov}^{+} (S) := k$ . For any $g\in {\mathbb {Z}}_q$ , consider $jg$ , where $j=0,1,\dots , k$ . By the pigeonhole principle, there are different $j_1 \neq j_2$ such that ${j_1 g \in S+x}$ and $j_2 g \in S+x$ with the same $x\in X$ . It implies that $(j_1-j_2)g \in S-S,$ and hence $g\in (j_1-j_2)^{-1} (S-S)$ , provided $(j_1-j_2)^{-1} \in \mathcal {R}^*$ . It remains to notice that $[-k,k]^{-1} \cdot (S-S) = [k]^{-1} \cdot (S-S)$ . This completes the proof.

Proof Let $p_1$ be the least prime factor of q. By our assumption, we know that ${p_1 \geqslant 2 \alpha ^{-1}+3}$ . Write $p_1=2k+1$ and take $\Lambda = \{0,1,\dots , k_*\}$ , where $\lceil \alpha ^{-1} - 1 \rceil + 1 = k_* \leqslant k$ . Then one has $Y:= (\Lambda - \Lambda )\setminus \{0\} \subseteq {\mathbb {Z}}^*_q$ . First of all, consider $n\in {\mathbb {Z}}_q^*$ and form the set $n\cdot \Lambda + A$ . Since $|\Lambda ||A| = (k_* +1) \alpha q> q$ , it follows that there are different $\lambda _1,\lambda _2 \in \Lambda $ such that

$$\begin{align*}n\lambda_1 + a_1 \equiv n\lambda_2 + a_2\quad \pmod q , \end{align*}$$

where $a_1, a_2 \in A$ and $a_1 \neq a_2$ . Hence $n\in Y^{-1} (A-A)$ and thus ${\mathbb {Z}}_q^* \subseteq Y^{-1} (A-A)$ . Also, notice that as in Proposition 5.2, one has $Y^{-1} (A-A) = [k_*]^{-1} \cdot (A-A)$ .

Now, let $n=n' q_1$ , where $q_1|q$ and $n'$ is coprime to q. By the pigeonhole principle, there is $B \subseteq {\mathbb {Z}}_{q/q_1}$ and $s\in {\mathbb {Z}}_q$ such that $q_1 B+s \subseteq A$ and the density of B in ${\mathbb {Z}}_{q/q_1}$ is at least $\alpha $ . In particular, we have $q_1 (B-B) \subseteq A-A$ . By the same argument as above, one has $n' \equiv y^{-1} (b_1-b_2) \pmod {q/q_1}$ , where $y\in Y$ and $b_1,b_2 \in B$ . It follows that ${n \equiv y^{-1} (a_1-a_2) \pmod q}$ as required. Thus, we have proved that $[k_*]^{-1} (A-A) = {\mathbb {Z}}_q,$ and hence $\mathrm {cov}^\times (A-A) \leqslant k_* \leqslant \alpha ^{-1}+1$ . This completes the proof.

Proof Put $A_{\vec {s}} = A_1 \cap (A_2-s_1) \cap \dots (A_k-s_{k-1})$ , where $\vec {s} = (s_1,\dots , s_{k-1}) \in {\mathbb {Z}}^{k-1}_q$ . We have $\sum _{\vec {s}} |A_{\vec {s}}| = |A_1| \dots |A_k|$ , and hence, there is $\vec {s}_*$ such that $|A_{\vec {s}_*}| \geqslant \alpha _1, \dots , \alpha _k q$ . Clearly, for any $\vec {s}$ , one has

$$\begin{align*}A_{\vec{s}} - A_{\vec{s}} \subseteq \bigcap_{i=1}^k (A_i - A_i) . \end{align*}$$

Applying Theorem 5.4 with $A = A_{\vec {s}_*}$ , we obtain bound (5.4). This completes the proof.

Proof Applying Theorem 5.4 with $A=B$ , we find a set $X\subseteq {\mathbb {Z}}_q$ , $n:=|X| \leqslant \beta ^{-1} +1$ such that $X(B-B) = {\mathbb {Z}}_q$ . Let $X = \{ x_1,\dots ,x_n\}$ and $\vec {x} = (x_1,\dots ,x_n) \in {\mathbb {Z}}^n_q$ . Considering the collection of the sets $A^n + j \cdot \vec {x} \subseteq {\mathbb {Z}}^n_q$ , $j\geqslant 1$ , we see that there is $0<d \leqslant \alpha ^{-n}$ with $d\cdot X \subseteq A-A$ . Hence

$$\begin{align*}(A-A)(B-B) \supseteq d\cdot X (B-B) \supseteq d \cdot {\mathbb{Z}}_q \end{align*}$$

as required. It remains to notice that

$$\begin{align*}d \leqslant \alpha^{-n} \leqslant \alpha^{-\beta^{-1} -1} . \end{align*}$$

This completes the proof.

Proof Take $S=S_1=[k]\times [k]$ or $S=S_2 = \{ (2j,2j) ~:~ j\in [k]\}$ for a certain positive integer k. Applying Theorem 6.1 with $n=|S|$ and $A=\mathcal {A}$ , we see that for some $\alpha $ , $\beta \neq 0$ the following holds $\alpha +\beta \cdot S \subseteq \mathcal {A}$ and hence to solve (3.1) with $d=1$ it is sufficiently to find for any $\lambda \in {\mathbb {Z}}^*_q$ some elements $a\in \beta ^{-1} (A-\alpha )$ , $b\in \beta ^{-1} (B-\alpha )$ and $(t_1,t_2) \in S$ such that

$$\begin{align*}(t_1 - a) (t_2-b) \equiv \lambda \pmod q . \end{align*}$$

If for a certain absolute constant $C>0$ , one has $k \gg \min ^{-C} \{\alpha _* ,\beta _*,\delta \}$ , then for ${S=S_2}$ , the last equation has a solution thanks to the famous Bourgain–Gamburd machine [Reference Bourgain and Gamburd4] (see details in [Reference Shkredov18], say) and for $S=S_1$ (actually, for any dense subset of $S_1$ ), the latter fact was obtained in [Reference Shkredov18, Theorem 3]. This completes the proof.