| Sbornik: Mathematics |
|
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper) Some applications of growth in M. V. Lyamkin Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia
Russian version:
Matematicheskii Sbornik, 2022, Volume 213, Number 10, DOI: https://doi.org/10.4213/sm9707 
Bibliographic databases:
    § 1. IntroductionRecall Zaremba’s conjecture, which is the subject of our study. Any rational number $r$ can uniquely be represented as a continued fraction of the form
$$
\begin{equation*}
r=b_0+\cfrac{1}{b_1+\cfrac{1}{b_2+\dots+\cfrac{1}{b_k}}},
\end{equation*}
\notag
$$
where $b_0$ is an integer and $b_1, \dots, b_k$ are positive integers. The numbers $b_0, b_1, \dots, b_k$ are called the partial quotients of $r$. Zaremba stated the following conjecture. Conjecture 1. For every positive integer $q$ there exists $a \in \mathbb{N}$, $a < q$, $(a, q)=1$, such that all partial quotients of the continued fraction $a/q$ are bounded by an absolute constant $M$. There are various versions of this conjecture. It was originally formulated for $M=5$. Let $\mathcal{Q}_M$ denote the set of positive integers $q$ such that for some positive integer $a$ coprime to $q$ all partial fractions of $a/q$ are bounded by $M$. In these terms Zaremba’s conjecture states that $\mathbb{N}=\mathcal{Q}_5$. Hensley suggested (see [7] and [8]) that for sufficiently large $q$ the partial quotients can be bounded by $2$. In the same paper [7] he proved the version of Zaremba’s conjecture that we formulate now in a simplified form. Theorem 1. The pairs of remainders modulo any prime number $p$ of the numerators and denominators of fractions $a/q$, $q \leqslant Q$, for which the partial quotients of continued fractions are bounded by some $M$ are asymptotically uniformly distributed over $\mathbb{F}_p^2$ as $Q \to \infty$. Thus, for every prime $p$ and any integer $u\,{\in}\, \{0, 1, 2, \dots, p-1 \}$ there exists $q \in \mathcal{Q}_M\colon q \equiv u\pmod{p}$. In this paper we prove that, under the same restrictions, we can additionally have $q=O_\varepsilon(p^{2+\varepsilon})$. Another result which is closely related to Zaremba’s conjecture was proved by Bourgain and Kontorovich [1]. They established that asymptotically almost surely all positive integers lie in $\mathcal{Q}_M$ for some $M$; more exactly, the following theorem holds. Another approach to a series of similar problems is connected with the use of the affine sieve, which is generalized to the case of semigroups. For the latest results in this area, see [15]. For the sieve method in general, see the survey [13]. In 2020 Shkredov [20] proved the following bound for $q$ in terms of $p$ in the case when $u=0$, improving the exponent from 30 (as in [17]) to $1+\varepsilon$. Theorem 3. Let $\varepsilon > 0$ and let $p$ be a prime number. Then there exist $q=O(p^{1+\varepsilon})$, $q \equiv 0\pmod{p}$, and $a < q$, $(a, q)=1$, such that all partial quotients of the continued fraction for $a/q$ are bounded by a constant $M$ depending only on $\varepsilon$. Developing the approach from [20] we prove the following result. Theorem 4. For every $\varepsilon > 0$ there exists a constant $M=M(\varepsilon)$ such that for every prime number $p$ and any $u \in \{ 0, 1, \dots, p-1 \}$ there exist $q=O_\varepsilon( p^{2+\varepsilon})$, $q \equiv u \ (\operatorname{mod}p)$, and $a \in \mathbb{N}$ such that $(a, q)=1$ and all partial quotients of the continued fraction $a/q$ are bounded above by $M$. Moreover, if the numbers $u=u(p)$ and $ v=v(p)$ grow sufficiently slowly with $p$, then it is possible to find $a/q$ with the same bound for $q$ such that $a \equiv v\pmod{p}$ and $q \equiv -u \pmod{p}$. Theorem 5. Fix $\varepsilon > 0$. Then there exist $\varepsilon_1 > 0$ and $ M > 0$ depending only on $\varepsilon$ such that for all $u$ and $v$, there exist $a, q \in \mathbb{N}\colon q=O_\varepsilon(p^{2+\varepsilon})$, such that $q \equiv -u \pmod{p}$, $a \equiv v \pmod{p}$, $(a, q)=1$, and all partial quotients of the continued fraction $a/q$ are bounded above by $M$. Before we prove Theorems 4 and 5, we illustrate our methods by a simple well-known example (see, for instance, [17], Theorem 2). Namely, we fix $M=2$ and look for a bound for $q \in \mathcal{Q}$, $q \equiv u \pmod{p}$. Theorem 6. There exists an absolute positive constant $C$ such that for any prime number $p$ and any $u \in \{ 0, 1, \dots, p-1 \}$ there exist $q=O(p^C)$, $q \equiv u \pmod{p}$, and $a \in \mathbb{N}$ such that $(a, q)=1$ and all partial quotients of the continued fraction for $a/q$ are bounded by 2. We give a new proof of this theorem by using the following fact, which holds for subsets of $\mathrm{SL}_2(\mathbb{F}_p)$ of arbitrary form, instead of working with particular generating sets. Here an observation concerning the growth in the subgroup $\mathcal{B}\,{\subset}\, \mathrm{SL}_2(\mathbb{F}_p)$ of the matrices of the form $\begin{pmatrix} \lambda &u \\ 0 &\lambda^{-1}\end{pmatrix}$ is of importance (see Lemma 7). Theorem 7. Let $c \in \mathbb{F}_p$ be arbitrary and let $A \subset \mathrm{SL}_2(\mathbb{F}_p)$ be such that $A \nsubseteq \mathcal{B}$ and $|A| \gg p^{1+\delta}$. Then the following assertion holds for all $n \gg 1/\delta$: 1.1. The necessary definitionsFirst recall the standard terminology from additive combinatorics. Let $G$ be a group and let $A, B \subset G$ be finite nonempty subsets. $\bullet$ We denote the characteristic function $A \colon G \to \{ 0, 1 \}$ of a set $A$ by the same symbol. $\bullet$ The Minkowski product is $AB=\{ x \in G\mid \exists\, a\in A,\ \exists\, b \in B\colon x=ab \}$. Multiple products are defined similarly: for example, $A^3=AAA$. Moreover, $A^{-1}=\{ a' \in G\mid \exists\, a\in A\colon a'=a^{-1} \}$. $\bullet$ For $n \in \mathbb{N}$ and $x \in \mathbb{Z}_n$ we set $e_n(x)=\exp(2\pi i x/n)$. $\bullet$ For every prime number $p$ we take some primitive root $\xi$. Then for every $x \in \mathbb{F}_p^*$ there exists a unique number $\operatorname{ind}x\in \{ 0, 1, \dots p-2 \}$ such that $x=\xi^{ \operatorname{ind}x}$; it is called the index of $x$. For any complex matrices $X, Y \in \operatorname{Mat}_{n \times n}(\mathbb{C})$ we use the following notation: $\bullet$ $\langle X, Y \rangle=\operatorname{tr}(XY^*)$ is the Hilbert-Schmidt inner product; $\bullet$ $\|X\|=\sqrt{\langle X, X\rangle}$; $\bullet$ $\|X\|_{\mathrm{op}}=\max_{v \neq 0}(|Xv|/|v|)$ is the operator norm (here $|\cdot|$ denotes the Euclidean norm). For an arbitrary finite group $G$ we introduce the following notation from representation theory and Fourier analysis on groups (see [18]). $\bullet$ $\widehat G$ is some maximal set of pairwise nonisomorphic irreducible unitary representations of $G$; $1 \in \widehat G$ is the identity representation. Given $\rho \in \widehat G $, we denote the dimension of $\rho$ by $ d_\rho$. $\bullet$ For $ f, h \in L_2(G)$ and $ g \in G$, $ (f * h)(g) =\sum_{t \in G}f(t)h(t^{-1}g)$ is the convolution. $\bullet$ $\widehat f(\rho)=\sum_{g \in G}f(g)\rho(g)$, where $f \in L_2(G)$ and $\rho \in \widehat G$ is the Fourier transform. $\bullet$ $\|A\|_{\mathrm{op}}=\max_{\rho \neq 1}\|\widehat A(\rho)\|_{\mathrm{op}}$ is the maximum operator norm of the Fourier coefficients of the subset $A$ of some group. $\bullet$ $d_{\min}=d_{\min}(G)$ is the minimum dimension of a nontrivial irreducible representation of $G$. By Frobenius’s theorem (see, for example, [18], Ch. 1, § 5),
$$
\begin{equation}
d_{\min}(\mathrm{SL}_2(\mathbb{F}_p))=\frac{p-1}{2}.
\end{equation}
\tag{1.1}
$$
We recall the classical inequalities
$$
\begin{equation}
\| XY\| \leqslant \|X\|_{\mathrm{op}} \,\|Y\|\quad\text{and} \quad \|X\|_{\mathrm{op}} \leqslant \|X\|
\end{equation}
\tag{1.2}
$$
(see [11]). Moreover, the Hilbert-Schmidt norm also satisfies the Cauchy-Bunyakovsky-Schwarz inequality We focus on the group $\mathrm{SL}_2(\mathbb{F}_p)$ and define some subsets of it: $\bullet$ $\mathcal{B}=\mathcal{B}(p)=\biggl\{ \begin{pmatrix}a & b \\ 0 & d\end{pmatrix} \in \mathrm{SL}_2(\mathbb{F}_p) \Bigm| a, b, d \in \mathbb{F}_p \biggr\}$ is the Borel subgroup; $\bullet$ $\mathcal{U}=\mathcal{U}(p)=\biggl\{ \begin{pmatrix}1 & b \\ 0 & 1\end{pmatrix} \in \mathrm{SL}_2(\mathbb{F}_p)\Bigm| b \in \mathbb{F}_p \biggr\}$ is the unipotent subgroup; $\bullet$ for every $p$ we fix some quadratic nonresidue $\varepsilon \in \mathbb{F}_p$ and set $K_\varepsilon=K_\varepsilon (p)=\biggl\{ \begin{pmatrix}x & \varepsilon y \\ y & x\end{pmatrix}\in \mathrm{SL}_2(\mathbb{F}_p)\Bigm| x^2-\varepsilon y^2=1 \pmod{p} \biggr\}$, which is a cyclic subgroup; $\bullet$ $\Omega_c=\biggl\{ \begin{pmatrix}a & b \\ c & d\end{pmatrix} \in \mathrm{SL}_2(\mathbb{F}_p) \Bigm| a, b, d \in \mathbb{F}_p \biggr\}$ is the set of matrices of the form $\begin{pmatrix}* & * \\ c & *\end{pmatrix}$ in $\mathrm{SL}_2(\mathbb{F}_p)$; $\bullet$ $\Omega^a_c=\biggl\{ \begin{pmatrix}a & b \\ c & d\end{pmatrix} \in \mathrm{SL}_2(\mathbb{F}_p) \Bigm| b, d \in \mathbb{F}_p \biggr\}$ is the set of matrices of the form $\begin{pmatrix}a & * \\ c & *\end{pmatrix}$ in $\mathrm{SL}_2(\mathbb{F}_p)$; $\bullet$ $E=\begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}$ is the identity matrix. Finally, we recall some notation for continued fractions (see [10]). $\bullet$ For $b_0 \in \mathbb{Z}$ and $b_1, \dots, b_k \in \mathbb{N}$,
$$
\begin{equation*}
[b_0; b_1, \dots, b_k]=b_0+\cfrac{1}{b_1+\cfrac{1}{b_2+\dots+ \cfrac{1}{b_k}}}.
\end{equation*}
\notag
$$
$\bullet$ Let $r \in \mathbb{Q}$. Then there exist unique $k=k(r)$, $b_0=b_0(r)$ and $b_1=b_1(r), \dots, b_k=b_k(r) > 1$ such that $r= [b_0; b_1, \dots,b_k]$. Moreover, we denote the numerators and denominators of convergents by $p_t=p_t(r)$ and $q_t=q_t(r)$, $t=0, \dots, k$. Thus, ${p_t}/{q_t}=[b_0; b_1, \dots, b_t]$. $\bullet$ For $Q, M \in \mathbb{N}$ we denote by $F_M=\{ r \in \mathbb{Q} \cap (0, 1)\mid\forall\, i\ b_i(r) \leqslant M \}$ the set of fractions with partial quotients bounded by $M$. We also set
$$
\begin{equation*}
F_M(Q)=\biggl\{ \frac{p}{q} \in F_M\Bigm| (p, q)=1, \ q < Q \biggr\}
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
\mathcal{Q}_M=\biggl\{ q \in \mathbb{N} \Bigm| \exists\, p\colon (p, q)=1, \ \frac{p}{q} \in F_M\biggr \}.
\end{equation*}
\notag
$$
Thus, Zaremba’s conjecture states that $\mathcal{Q}_M=\mathbb{N}$ for some $M$. Recall the formulae connecting the numerators and denominators of convergents (see [10], Theorems 1, 2 and 6). The first is the key formula for us, because it expresses the determinant of the matrix $\begin{pmatrix} p_{t-1} & p_t \\ q_{t-1}& q_t \end{pmatrix}$ formed by the numerators and denominators of convergents: The law governing the formation of convergents is as follows:
$$
\begin{equation}
p_t=b_t p_{t-1}+p_{t-2},\qquad q_t=b_t q_{t-1}+q_{t-2}.
\end{equation}
\tag{1.5}
$$
The following relations hold for the ratios of the numerators and ratios of the denominators of convergents:
$$
\begin{equation}
\frac{q_t}{q_{t-1}}=[b_t; b_{t-1}, \dots, b_1]\quad\text{and}\quad \frac{p_t}{p_{t-1}} =[b_t; b_{t-1}, \dots, b_2].
\end{equation}
\tag{1.6}
$$
We use the standard Vinogradov symbols $\ll$ and $\gg$, as well as the Landau notation $O$ and $o$. We write $f \asymp g$ if $f \ll g$ and $ g \ll f$. Moreover, the notation $\ll_l$, $\gg_l$, and $\asymp_l$ means that the inequalities hold up to multiplicative constants which only depend on $l$. 1.2. Growth in $\mathrm{SL}_2( {\mathbb{F}}_p)$ and Fourier analysisWe present basic formulae for Fourier analysis on finite non-Abelian groups (see, for example, [18]). Let $f, g\in L_2(G)$ be functions on a group and let $|G| < \infty$. Then the following formulae hold:
$$
\begin{equation}
\langle f, f \rangle=\sum_{x \in G}|f(x)|^2 =\frac{1}{|G|}\sum_{\rho \in \widehat G} d_\rho \|\widehat f(\rho)\|^2,
\end{equation}
\tag{1.7}
$$
$$
\begin{equation}
\langle f, g \rangle=\sum_{x \in G}f(x) \overline{g(x)} =\frac{1}{|G|}\sum_{\rho \in \widehat G} d_\rho \langle \widehat f(\rho), \widehat g(\rho) \rangle,
\end{equation}
\tag{1.8}
$$
$$
\begin{equation}
\forall\, g \in G\quad f(g) =\frac{1}{|G|}\sum_{\rho \in \widehat G} d_\rho \langle \widehat f(\rho), \rho(g^{-1}) \rangle.
\end{equation}
\tag{1.9}
$$
Formula (1.7) is known as Parseval’s equality, (1.8) as Plancherel’s formula, and (1.9) as the inversion formula. We note another important equality: If $f$ and $g$ are the characteristic functions of sets $A$ and $B$, then $(f*g)(x)$ is equal to the number of representations $x=ab$, where $a \in A$ and $b \in B$. Thus, the support of a convolution coincides with the Minkowski product of the sets. This property underlines the important role that methods of Fourier analysis play in additive combinatorics. Let us prove a classical lemma of Fourier analysis on finite groups. Lemma 1. Let $G$ be a finite group, let $X \subset G$, and let $\rho$ be an irreducible unitary representation of $G$ of dimension $d$. Then $\|\widehat X(\rho)\|_{\mathrm{op}} \leqslant \|\widehat X(\rho)\| \leqslant \sqrt{|X|\,|G|/d}$. Proof. Let us choose some complete system of pairwise nonisomorphic irreducible unitary representations $\widehat G$ such that $\rho \in \widehat G$. According to Parseval’s equality (1.7), Transferring the coefficients and extracting the square root we obtain the assertion claimed. This completes the proof of the lemma. It is known that using analytic methods one can obtain nontrivial results only for sufficiently large subsets of a group. We present a simple proof from [17] of the following theorem, which gives a sufficient condition for the product of three sets to exhaust the whole group for sufficiently large cardinalities of the sets. This is a special case of a result due to Gowers (see [5], Theorem 3.3). Theorem 8. If $X, Y, Z \subset \mathrm{SL}_2(\mathbb{F}_p)$ are such that then $XYZ=\mathrm{SL}_2(\mathbb{F}_p)$. Proof. It suffices to prove for an arbitrary $g \in \mathrm{SL}_2(\mathbb{F}_p)$ that $(X*Y*Z)(g) \neq 0$. We apply inversion formula (1.9):
$$
\begin{equation*}
\begin{aligned} \, |G|(X*Y*Z)(g) &= \sum_{\rho \in \widehat G}d_U\langle \widehat{(X*Y*Z)}(\rho), \rho(g^{-1})\rangle \\ & =\bigl|X|\,|Y|\,|Z\bigr|+\sum_{\rho \in \widehat G \setminus \{ 1 \}}d_\rho\bigl\langle \widehat X(\rho) \widehat Y(\rho) \widehat Z(\rho), \rho(g^{-1})\bigr\rangle. \end{aligned}
\end{equation*}
\notag
$$
We estimate the modulus of the sum using inequalities (1.2) and (1.3) and the equality $\|\rho(g)\|_{\mathrm{op}}=1$:
$$
\begin{equation*}
\biggl|\sum_{\rho \in \widehat G \setminus \{ 1 \}}d_\rho\bigl\langle \widehat X(\rho) \widehat Y(\rho) \widehat Z(\rho), \rho(g^{-1})\bigr\rangle \biggr|\leqslant \|X\|_{\mathrm{op}} \sum_{\rho \in \widehat G \setminus \{ 1 \}}d_\rho \|Y(\rho)\|\,\|Z(\rho)\|.
\end{equation*}
\notag
$$
Let us apply the Cauchy-Bunyakovsky inequality, Parseval’s equality, and the bound from Lemma 1:
$$
\begin{equation*}
\begin{aligned} \, & \|X\|_{\mathrm{op}} \sum_{\rho \in \widehat G \setminus \{ 1 \}}d_\rho \|Y(\rho)\|\,\|Z(\rho)\| \leqslant \sqrt{\frac{|X| \,|G|}{d_{\min}}} \biggl(\sum_{\rho \neq 1}d_\rho \|Y(\rho)\|^2 \sum_{\rho \neq 1}d_\rho \|Z(\rho)\|^2\biggr)^{1/2} \\ &\qquad < \sqrt{\frac{|X| \,|Y|\, |Z|\, |G|^3}{d_{\min}}}. \end{aligned}
\end{equation*}
\notag
$$
It can readily be seen that $\sqrt{\|X| \,|Y|\, |Z|\, |G|/d_{\min}} \leqslant |X| \,|Y|\, |Z|$ for $|X|\,|Y|\,|Z| \geqslant 2q^3(q+1)^3(p-1)^2$. Hence $(X*Y*Z)(g) \neq 0 $, as required. The following fact is proved similarly (see [17], Lemma 4). Theorem 9. Let $X_1, X_2, \dots, X_n \subset \mathrm{SL}_2(\mathbb{F}_p)$ satisfy $|X_1|\, |X_2| \dotsb |X_n| \gg_n p^{2n+2}$. Then $X_1 X_2 \dotsb X_n=\mathrm{SL}_2(\mathbb{F}_p)$. 1.3. Continued fractions with bounded partial quotientsWe will extensively use the known estimates for $|F_M(Q)|$ in terms of the Hausdorff dimension $\omega_M$ of the set $F_M$. Let us formulate a result from [9]. Lemma 2. In the above notation $|F_M(Q)|\asymp_M Q^{2\omega_M}$ and $\omega_M \to 1$ as $ M \to \infty$. We also need an approximate value of $\omega_2$ as calculated in [12]: Now we associate continued fractions with the group $\mathrm{SL}_2(\mathbb{F}_p)$, as in [1], [20] and [17], for instance. Fix a prime number $p$ and $Q < p$ as parameters. We represent every $r \in F_M(Q)$ as a convergent $r={p_k}/{q_k}= [0; b_1, \dots, b_k]$ and consider the matrix $g(r)=\begin{pmatrix} p_{k-1} &p_k\\ q_{k-1} &q_k\end{pmatrix} \in \mathrm{GL_2}(\mathbb{F}_p)$. It can readily be seen that
$$
\begin{equation}
g(r)=\begin{pmatrix} 0 & 1 \\ 1 & b_1\end{pmatrix}\begin{pmatrix}0 & 1 \\ 1& b_2\end{pmatrix} \dotsb \begin{pmatrix}0 & 1 \\ 1 & b_k\end{pmatrix}.
\end{equation}
\tag{1.12}
$$
Since $Q < p$, it follows that the map $g$ is injective. By (1.4), $g(r) \in \mathrm{SL}_2(\mathbb{F}_p)$ $\Leftrightarrow$ $2 \mid k$. We discard all $r$ such that $k(r)$ is odd and work with the remaining quantities without reducing the size of the set too heavily. Indeed, if we set
$$
\begin{equation*}
F_M^{\mathrm{even}}(Q)=\biggl\{ \frac{p}{q} \in F_M\colon (p, q)=1, \ q \leqslant Q, \ k\biggl(\frac{p}{q}\biggr) \ \vdots \ 2 \biggr\} \subset F_M(Q),
\end{equation*}
\notag
$$
then we obtain $|F_M^{\mathrm{even}}(Q)| \geqslant |1/(M+1)F_M(Q)|$, since, if $p_{2k+1}/(q_{2k+1}) \notin F_M^{\mathrm{even}}(Q)$, then it can be recovered from the previous convergent in $F_M^{\mathrm{even}}$ and the last partial quotient, which can take $M$ values because $g\biggl(\dfrac{p_{2k+1}}{q_{2k+1}}\biggr)=g\biggl(\dfrac{p_{2k}}{q_{2k}}\biggr)\begin{pmatrix}0 & 1 \\ 1 & b\end{pmatrix}$ for some $b \in \{ 1, 2, \dots, M \}$. Thus (see Lemma 2), Accordingly, we consider
$$
\begin{equation}
A=A_M(Q)=g(F_M^{\mathrm{even}}(Q)) \subset \mathrm{SL}_2(\mathbb{F}_p),
\end{equation}
\tag{1.14}
$$
and we work with this set in what follows. Finally, note that if the product of sets $A_M(Q_1),A_M(Q_2),\dots,A_M(Q_n)$ intersects some subset $\Omega \subset \mathrm{SL}_2(\mathbb{F}_p)$, then the matrix $\begin{pmatrix} p_{s-1} &p_s\\ q_{s-1} &q_s\end{pmatrix}$ of numerators and denominators of convergents of the rational number ${p_s}/{q_s}$ whose partial quotients are bounded by $M$, where $q_s$ can be estimated in terms of $Q_1, Q_2, \dots, Q_n$, can be shown to belong to $\Omega$ modulo $p$. This is the subject of the following lemma. Lemma 3. Given $g\!=\!\begin{pmatrix} \alpha& \beta \\ \gamma &\delta\end{pmatrix} \!\in\! \mathrm{SL}_2(\mathbb{F}_p)$ and sets $A_M(Q_1), A_M(Q_2)$, …, $A_M(Q_n)$, let $g \in A_M(Q_1)A_M(Q_2)\dotsb A_M(Q_n)$. Then there exists a pair of integers $a, q \in \mathbb{N}$ such that and the partial quotients of the continued fraction for $a/q$ are bounded by $M$. A similar assertion holds if the conditions $p=\alpha \pmod{p}$ and $q= \gamma\pmod{p}$ are replaced by $a=\beta \pmod{p}$ and $q=\delta\pmod{p}$. Proof. Let the matrices ${\begin{pmatrix}p_{k_i-1} &p_{k_i} \\ q_{k_i-1} &q_{k_i}\end{pmatrix}}{\in}\, A_M(Q_i)$, $i\,{\in}\, \{ 1, 2, \dots, n \}$, satisfy where $p_{k_i}/q_{k_i}=[0; b_1^i, \dots, b_{k_i}^i]$ (here we write indices as superscripts). Now consider the product of the above matrices as matrices in $\mathrm{SL}_2(\mathbb{Z})$:
Simple inequalities for matrix elements enable us to prove that Moreover, (1.15) implies that
$$
\begin{equation*}
p_s \equiv \beta \pmod {p}, \qquad q_s \equiv \delta \pmod{p},
\end{equation*}
\notag
$$
and also
$$
\begin{equation*}
\frac{p_s}{q_s}=[0; b_1^1, \dots, b_{k_1}^1, b_1^2, \dots, b_{k_2}^2, \dots, b_1^n, \dots, b_{k_n}^n ];
\end{equation*}
\notag
$$
thus, ${p_s}/{q_s} \in F_M$ since all the $b_i^j$ are bounded by $M$.
Thus, the pair $a=p_s$, $q=q_s$ satisfies the conditions and the second assertion of the lemma is proved. The first part is proved similarly. This completes the proof.1.4. Solutions of linear equations in $A$The fact that an element of $\mathrm{SL}_2(\mathbb{F}_p)$ belongs to a certain subgroup of $\mathrm{SL}_2(\mathbb{F}_p)$ is expressed by a linear homogeneous equation in $\mathbb{F}_p$ for the matrix elements. For example,
$$
\begin{equation*}
g=\begin{pmatrix}a & b \\ c & d\end{pmatrix} \in \mathcal{B} \quad\Longleftrightarrow \quad c=0.
\end{equation*}
\notag
$$
In particular, an upper bound for the number of solutions of linear equations with respect to $p_{s-1}$, $q_{s-1}$, $p_s$ and $q_s$ will help us to estimate the cardinality of the intersection of $A$ with some subgroups. We need the following assertion. Lemma 4. Let $24Q^4 < p$ and $A=A_M(Q)$, and let $f$ be a nontrivial linear function defined by the formula Then $|\{ g \in A\colon f(g)=0 \}| \leqslant M Q^{1+o(1)}$ as $p \to \infty$. Proof. We estimate the number of solutions of the equation
$$
\begin{equation}
\alpha p_{s-1}+\beta p_s+\gamma q_{s-1}+\delta q_s=0 \pmod{p}
\end{equation}
\tag{1.16}
$$
for $\begin{pmatrix}p_{s-1}&p_s \\ q_{s-1} &q_s\end{pmatrix}{\in}\, A$. We show that, if the hyperplane (1.16) contains at least three elements of $A$, then treating the coefficients $\alpha, \beta, \gamma, \delta\,{\in}\, \mathbb{Z} / p\mathbb{Z}$ as integers we can assume that $\alpha, \beta, \gamma, \delta\,{\in}\, (-3Q^3, 3Q^3)$. Indeed, if there exist three such matrices $\begin{pmatrix}p_{s_i-1}^i &p_{s_i}^i \\ q_{s_i-1}^i &q_{s_i}^i\end{pmatrix}{\in}\, A$, $i\,{\in}\, \{ 1, 2, 3 \}$, satisfying (1.16), then for any matrix $g=\begin{pmatrix}x &y \\ z &w\end{pmatrix}$ in $\mathrm{SL}_2(\mathbb{F}_p)$ such that $ f(g)=0$ we have
$$
\begin{equation}
\begin{vmatrix} p_{s_1-1}^1 & p_{s_1}^1 & q_{s_1-1}^1 & q_{s_1}^1 \\ p_{s_2-1}^2 & p_{s_2}^2 & q_{s_2-1}^2 & q_{s_2}^2 \\ p_{s_3-1}^3 & p_{s_3}^3 & q_{s_3-1}^3 & q_{s_3}^3 \\ x & y & z & w \end{vmatrix}=0.
\end{equation}
\tag{1.17}
$$
Setting
$$
\begin{equation*}
\begin{gathered} \, \alpha'=-\begin{vmatrix} p_{s_1}^1 & q_{s_1-1}^1 & q_{s_1}^1 \\ p_{s_2}^2 & q_{s_2-1}^2 & q_{s_2}^2 \\ p_{s_3}^3 & q_{s_3-1}^3 & q_{s_3}^3 \end{vmatrix}, \qquad \beta'=\begin{vmatrix} p_{s_1-1}^1 & q_{s_1-1}^1 & q_{s_1}^1 \\ p_{s_2-1}^2 & q_{s_2-1}^2 & q_{s_2}^2 \\ p_{s_3-1}^3 & q_{s_3-1}^3 & q_{s_3}^3 \end{vmatrix}, \\ \gamma'=-\begin{vmatrix} p_{s_1-1}^1 & p_{s_1}^1 & q_{s_1}^1 \\ p_{s_2-1}^2 & p_{s_2}^2 & q_{s_2}^2 \\ p_{s_3-1}^3 & p_{s_3}^3 & q_{s_3}^3 \end{vmatrix}, \qquad \delta'=\begin{vmatrix} p_{s_1-1}^1 & p_{s_1}^1 & q_{s_1-1}^1 \\ p_{s_2-1}^2 & p_{s_2}^2 & q_{s_2-1}^2 \\ p_{s_3-1}^3 & p_{s_3}^3 & q_{s_3-1}^3 \end{vmatrix}, \end{gathered}
\end{equation*}
\notag
$$
we obtain a new description of this hyperplane in the form (1.16), and we can readily derive the following bounds from the explicit formula for determinants: since $0 < p_{s-1}, p_s, q_{s-1}, q_s < Q$ for $\begin{pmatrix}p_{s-1}&p_s \\ q_{s-1} &q_s\end{pmatrix} \in A$.
Now note that if (1.16) holds for $\begin{pmatrix}p_{s-1} &p_s \\ q_{s-1} &q_s\end{pmatrix} \in A$ in $\mathbb{F}_p$, then the same equation also holds in $\mathbb{Z}$ by the inequality $24Q^4 < p$ and by (1.18). Since $f$ is a nontrivial linear function, one of the coefficients is nonzero. We assume that $\alpha' \neq 0$; otherwise the reasoning is similar. Then we can express $p_{s-1}$ as $p_{s-1}=(1+p_sq_{s-1})/{q_s}$, and substitute this into (1.16). Further, adding and subtracting the term ${\beta' \gamma'}/{\alpha'}$ we collect like terms:
$$
\begin{equation}
(\beta' q_s+\alpha 'q_{s-1})(\gamma' q_s+\alpha ' p_s) =-\alpha'^2+(\beta' \gamma'- \alpha' \delta') q_s^2.
\end{equation}
\tag{1.19}
$$
We fix $q_s$ and show how we can recover the full continued fraction using the resulting equality (1.19). If the right-hand side of (1.19) is not zero, then we can represent it as a product of two integers $N K$, where $N=\beta' q_s+\alpha 'q_{s-1}$ and $K=\gamma' q_s+\alpha ' p_s$, in at most $Q^{o(1)}$ ways; this follows from the well-known bound on the number-of-divisors function. In turn, $p_s$ can readily be recovered from $K$: $p_s=(K-\gamma' q_s)/\alpha$. Thus, at most $Q^{1+o(1)}$ elements of the set $A$ satisfy (1.16) since $q_s \in [0, Q-1]$.
Finally, if the right-hand side of (1.19) is zero, then either $q_{s-1}=-({\beta'}/{\alpha'})q_s$ or $p_s=({\gamma'}/{\alpha'}) q_s$, and from either of the pairs $(q_{s-1}, q_s)$ and $ (p_{s-1}, p_s)$ we can uniquely recover the continued fraction by (1.6). Thus, in this case at most $2Q$ elements of $A$ satisfy (1.16), which completes the proof of the lemma. A few words about the remaining cases. If, for instance, $\delta'$ is the only nonzero coefficient among $\alpha'$, $\beta'$, $\gamma'$, $\delta'$, then after similar calculations we will need to recover the continued fraction from $p_{s-1}$ and $q_{s-1}$, which, in view of (1.5), can be done in at most $M$ ways. This is why the coefficient $M$ occurs in the conclusion of the lemma. The proof of the lemma is complete. We can get rid of the constraint $24Q^4 < p$ and obtain a weaker estimate for the number of solutions of equation $(1.16)$. Corollary 1. For $Q < p$ let $A=A_M(Q)$, and let $f$ be a nontrivial linear function on $\mathrm{SL}_2(\mathbb{F}_p)$ given by Proof. Set
$$
\begin{equation*}
A_{1/4}=A_M\biggl(\frac{1}{3}Q^{1/4}\biggr)\quad\text{and} \quad A_{3/4}=A_M(12 M^2 Q^{3/4}).
\end{equation*}
\notag
$$
Then $ A=A_M(Q) \subset A_{1/4} A_{3/4}$. Note that for any matrix $r \in \mathrm{SL}_2(\mathbb{F}_p)$ the function $f_r(g)=f(rg)$ is also linear and nontrivial. Thus, we can use Lemma 4 and write the following bounds:
$$
\begin{equation*}
\begin{aligned} \, |\{ g \in A\colon f(g)=0 \}| &\leqslant |\{ (g, r) \in A_{1/4} \times A_{3/4}\colon f_{r^{-1}}(g)=0 \}| \\ & \leqslant |A_{3/4}| Q^{(1+o(1))/{4}} \asymp_M |A| Q^{(1-2\omega_M+o(1))/{4}}, \end{aligned}
\end{equation*}
\notag
$$
where, to estimate the cardinality of $|A_{3/4}|$, we have used asymptotic formula (1.13) in combination with (1.14), which imply that Thus, we have proved relation (1.20). To obtain (1.21) from it, we use (1.13) and (1.14) again:
$$
\begin{equation*}
|A| Q^{(1-2\omega_M+o(1))/{4}} \asymp_M |A|^{1-(2 \omega_M-1)/(8 \omega_M)}.
\end{equation*}
\notag
$$
It remains to note that for $\omega_M \in (0.53, 1)$ (see Lemma 2 and relation (1.11)) we have $(2 \omega_M-1)/(8 \omega_M)>0.06/{8} > 0.005$, and thus we can set $c_1=0.005$, although more precise inequalities enable us to establish the inequality $(2 \omega_M-1)/(8 \omega_M) > 0.01$. This completes the proof of the corollary. We should mention here general results on the solution of linear equations in generating sets. In [6] Helfgott linked the growth of a symmetric generating subset $C \subset \mathrm{SL}_2(\mathbb{F}_p)$ with the cardinality of the set $|\operatorname{tr}(C)|$ (see [6], § 4). Thus, a further investigation of solutions of linear equations in generating sets could help one to understand growth in $\mathrm{SL}_2(\mathbb{F}_p)$ better. 1.5. The intersections of $A$ with subgroups of $\mathrm{SL}_2( {\mathbb{F}}_p)$The objective of this section is to prove a nontrivial bound for $\|A_M(Q)\|_{\mathrm{op}}$ for all numbers $Q$ such that $p^c < Q < p$. We need some facts concerning subgroups of $\mathrm{SL}_2(\mathbb{F}_p)$. We recall Dickson’s classical theorem (see [3] and [4]). Theorem 10. Let $H$ be a proper subgroup of $\mathrm{SL}_2(\mathbb{F}_p)$ which is maximal by inclusion. Then $H$ is isomorphic to one of the following subgroups: a) the Borel group of upper triangular matrices $\mathcal{B}(p)$; b) the dihedral group $D_{p \pm 1}$; c) the dicyclic group $\mathrm{Dic}_n$, where $n \in \{ p-1, p, p+1 \}$; d) some finite subgroup of order at most 120. Here isomorphism is established by conjugation. We note that both the dihedral and dicyclic subgroups are unions of two cosets by cyclic subgroups, and therefore it is appropriate to introduce maximal cyclic subgroups, such as $K_\varepsilon$, into consideration. Such subgroups, as well as Borel subgroups, can be reduced to a more convenient form by conjugation by elements of $\mathrm{SL}_2(\mathbb{F}_p)$. For instance, this is what the following lemma claims (see [16], Theorem 12 and Lemma 13). Lemma 5. Let $H$ be an inclusion-maximal cyclic subgroup of $\mathrm{SL}_2(\mathbb{F}_p)$. Then one of the following holds: 1) $H \subset B$, where $B$ is a Borel subgroup of $\mathrm{SL}_2(\mathbb{F}_p)$; 2) $H=g K_\varepsilon g^{-1}$ for some $g \in \mathrm{SL}_2(\mathbb{F}_p)$. Moreover, if $B$ is a Borel subgroup of $\mathrm{SL}_2(\mathbb{F}_p)$, then it is conjugate to the standard Borel subgroup $\mathcal{B}$ by some element of $\mathrm{SL}_2(\mathbb{F}_p)$. A finite group $G$ is said to be $d$-quasirandom if $d_{\min}(G) \geqslant d$. Gamburd and Bourgain [2] showed that, if the growth $|X^3|\,{\gg}\min(|G|, |X|^{1+c})$ holds for some positive constant $c$ for all generating subsets $X$ of a quasirandom group and if a subset $A$ has a nontrivial upper bound of the form $|A|^{1-\delta}$ for its intersections with arbitrary cosets, then $A$ is uniform, that is, $\|A\|_{\mathrm{op}} \ll |A|^{1-\varepsilon (\delta)}$. We formulate this fact in a form convenient for us (see [21], Theorem 49, and also Theorem 13 and equation (1.1)). Theorem 11. Let $A \subset \mathrm{SL}_2(\mathbb{F}_p)$ be a nonempty set such that for some $\delta > 0$ for every proper subgroup $H < \mathrm{SL}_2(\mathbb{F}_p)$ and every $h \in \mathrm{SL}_2(\mathbb{F}_p)$. Then $\|A\|_{\mathrm{op}} \ll |A|^{1-\varepsilon (\delta)}$ for some $\varepsilon (\delta) > 0$. Thus, to establish a bound for $\|A_M(Q)\|_{\mathrm{op}}$, it suffices to prove (1.22), We do this in the following lemma. Lemma 6. Let $H$ be an arbitrary proper subgroup of $\mathrm{SL}_2(\mathbb{F}_p)$, let $h \in \mathrm{SL}_2(\mathbb{F}_p)$, and let $c > 0$. Then for some constant $\varepsilon=\varepsilon (c)$ the bound (1.22) holds for $A=A_M(Q)$, where $Q \gg p^c$. Proof. By Theorem 10 and Lemma 5, it suffices to estimate $|A \cap g\mathcal{B}h|$ and $|A \cap g K_\varepsilon h|$ for arbitrary matrices $g, h \in \mathrm{SL}_2(\mathbb{F}_p)$. Indeed, all Borel subgroups of $\mathrm{SL}_2(\mathbb{F}_p)$ have the form $h^{-1}\mathcal{B}h$, and the obvious substitution $g h^{-1}$ $\longleftrightarrow$ $g$ shows that $g\mathcal{B}h$ is the general form of cosets of Borel subgroups. Arguing similarly for the dihedral and dicyclic subgroups and recalling that each of them is a union of two cosets by a cyclic subgroup, we see that it suffices to estimate $|A \cap g K_\varepsilon h|$.
We begin with the Borel subgroup $\mathcal{B}$. Let $g^{-1}\,{=}\begin{pmatrix}a & b \\ c & d\end{pmatrix}$ and $h^{-1}\,{=}\begin{pmatrix}\alpha & \beta \\ \gamma & \delta\end{pmatrix}$. Then the intersection $|A_M(Q) \cap g\mathcal{B}h|$ has cardinality equal to the number of solutions of the equation for $\begin{pmatrix}p_{s-1} &p_s \\ q_{s-1} &q_s\end{pmatrix}\in\, A_M(Q)$, or, equivalently, for $\begin{pmatrix}a & b \\ c & d\end{pmatrix} \begin{pmatrix}p_{s-1} &p_s \\ q_{s-1} &q_s\end{pmatrix} \begin{pmatrix}\alpha & \beta \\ \gamma & \delta\end{pmatrix} \in\,\mathcal{B}$. We recall that we have defined $\mathcal{B}$ to be the subgroup of upper triangular matrices. Thus, we are interested in the cardinality of the intersection of $A$ with the hyperplane given by Since the matrices $g$ and $ h$ are nonsingular, not all the coefficients of the linear equation (1.23) vanish, and we obtain (1.22) from (1.20) in Corollary 1.We turn to the case of the subgroup $K_\varepsilon$. We could estimate $|A \cap g K_\varepsilon h|$ by a constant using methods from [16]; however, a weaker estimate is sufficient for us: we use only the fact that in $K_\varepsilon$ the upper left and lower right matrix entries are equal. Simple calculations show that this condition,
$$
\begin{equation*}
\biggl( g^{-1}\begin{pmatrix}p_{s-1} &p_s \\ q_{s-1} &q_s\end{pmatrix}h^{-1}\biggr)_{11} =\biggl( g^{-1}\begin{pmatrix}p_{s-1} &p_s \\ q_{s-1} &q_s\end{pmatrix}h^{-1}\biggr)_{22},
\end{equation*}
\notag
$$
where $(X)_{ij}$ is the entry of the matrix $X$ with indices $i$ and $j$, is equivalent to
$$
\begin{equation*}
(\alpha a-\beta c)p_{s-1}+(\alpha b-\beta d) q_{s-1}+(\gamma a-\delta c) p_s +(\gamma b-\delta d) q_s=0.
\end{equation*}
\notag
$$
The coefficients of this equation are entries of the nonsingular matrix $\begin{pmatrix}\alpha &-\beta \\ \gamma &-\delta\end{pmatrix}\begin{pmatrix}a & b \\ c & d\end{pmatrix}$, and thus we can apply Corollary 1 again and complete the proof of the lemma. Combining Theorem 11 and Lemma 6 we obtain the following assertion. Corollary 2. Let $Q \gg p^c$ for some $c > 0$. Then $\|A_M(Q)\|_{\mathrm{op}} \ll_M |A_M(Q)|^{1-\varepsilon}$, where $\varepsilon$ depends only on $c$. § 2. Applications to Zaremba’s conjectureIn this section we obtain our main applications to Zaremba’s conjecture. We begin with a technically simpler result, Theorem 6. Then we go over to Theorem 4 on the existence of a continued fraction in $F_M$ whose denominator is of order $p^{2+\varepsilon}$ and has a prescribed remainder modulo $p$. Here we need Corollary 2 and some information about the growth of our set $A$ under multiplication by $\Omega_u$ and $\mathcal{U}$: see Lemmas 8 and 9. Finally, we establish Theorem 5, where we complement the method of the proof of Theorem 4 by using the idea that two coprime positive integers can be interpreted as successive denominators of convergents of some continued fraction. 2.1. Proof of Theorems 7 and 6We use the classification of representations of $\mathcal{B}$. We will use the notation from Theorem 12 in what follows. Theorem 12. There exists a complete system of irreducible unitary pairwise nonisomorphic representations of the group $\mathcal{B}$, namely, the $\chi_a$, $a \in \mathbb{F}_p^*$, and $\pi_1, \dots, \pi_4$. Here, for $g=\begin{pmatrix}\lambda &u \\ 0 &\lambda^{-1}\end{pmatrix}\in \mathcal{B}$, $\chi_a(g)=e_{p-1}(a \ \operatorname{ind} (\lambda))$, and the representations $\pi_i$, $i=1,2,3,4$, have dimension $(p-1)/{2}$. Let us use results on the growth of symmetric generating sets in $\mathrm{SL}_2(\mathbb{F}_p)$ that were originally established by Helfgott [6], then improved by Kowalski [14] and improved further by Rudnev and Shkredov [19]. In [19], Theorem 2, the authors got rid of the condition that the set must be symmetric. Theorem 13. Let $X \subset \mathrm{SL}_2(\mathbb{F}_p)$, $|X| \ll p^{2+{2}/{15}}$, and let $X$ generate $\mathrm{SL}_2(\mathbb{F}_p)$. Then $|X^3| \gg |X|^{1+{1}/{24}}$. Note that if we do not care about exact numerical values, then it is sufficient to have the bound $|X^3| \gg |X|^{1+c}$ for some $c > 0$. Nonetheless, we have formulated the precise result for clarity. Lemma 7. Let $X \subset \mathcal{B}$ satisfy $|X| \geqslant 4 p^{1+{2}/{n}}$. Then for any $u \in \mathbb{F}_p$ there exist $\lambda \in \mathbb{F}_p^*$ such that $\begin{pmatrix}\lambda &u \\ 0 &\lambda^{-1}\end{pmatrix}\in X^n$. Proof. We write
$$
\begin{equation*}
\Gamma=\biggl\{\begin{pmatrix}\lambda &u \\ 0 &\lambda^{-1}\end{pmatrix} \Bigm|\lambda \in \mathbb{F}_p \biggr\}.
\end{equation*}
\notag
$$
Then it is necessary and sufficient for us to show that $X^n \cap \Gamma \neq \varnothing$. In terms of the inner product of functions on a group, this condition can be written in the form
$$
\begin{equation}
\langle \underbrace {X*X*\dots *X}_n, \Gamma \rangle \neq 0.
\end{equation}
\tag{2.1}
$$
For all nontrivial one-dimensional representations $\chi_a$, $a\in\mathbb{F}_p^* \setminus \{ 0 \}$ (see Lemma 12), since the element $a \lambda$ ranges over $\mathbb{F}_p^*$, we have Using Plancherel’s identity (1.8) and (2.2) we obtain
$$
\begin{equation*}
\langle \underbrace {X*X*\dots *X}_n, \Gamma \rangle=\frac{1}{|\mathcal{B}|}\biggl( (p-1)|X|^n +\sum_{i=1}^4\frac{p-1}{2}\langle (\widehat X (\pi_i))^n, \Gamma(\pi_i)\rangle \biggr),
\end{equation*}
\notag
$$
where we have singled out the leading term corresponding to $\rho=1$. Now it remains to estimate the right-hand side of the above equality so as to show that the full sum is nonzero. Applying formulae (1.2) and (1.3) and the estimate from Lemma 1 repeatedly we see that
$$
\begin{equation*}
\begin{aligned} \, & \frac{p-1}{2}\biggl|\sum_{i=1}^4\langle (\widehat X (\pi_i))^n, \Gamma(\pi_i)\rangle \biggr| \leqslant 4 \frac{p-1}{2}\biggl(\frac{2|X|\,|\mathcal{B}|}{p-1}\biggr)^{n/2} \sqrt{\frac{2|\Gamma|\,|\mathcal{B}|}{p-1}} \\ &\qquad =2^{(n+1)/{2}+1}(p-1)^{{3}/{2}}p^{(n+1)/{2}} |X|^{{n}/{2}}. \end{aligned}
\end{equation*}
\notag
$$
It remains to use the inequality $|X| \geqslant 4 p^{1+{2}/{n}}$, which implies now that
$$
\begin{equation*}
\frac{p-1}{2}\biggl| \sum_{i=1}^4\langle (\widehat X (\pi_i))^n, \Gamma(\pi_i)\rangle \biggr| < (p-1)|X|^n.
\end{equation*}
\notag
$$
This yields (2.1) and completes the proof of the lemma. Now we prove Theorem 7. Proof of Theorem 7. We fix some $u_0 \in \mathbb{F}_p$ and prove that for $n \gg {1}/{\delta}$ the set $A^n$ contains an element of the form $\begin{pmatrix}* &* \\ -u_0 &*\end{pmatrix}$, that is, $A^n \cap \Omega_{-u_0} \neq \varnothing$. We set $\Omega:=\Omega_{-u_0}$. By Theorem 10 we can consider two cases.
Case 1. The set $A$ does not generate the whole of $\mathrm{SL}_2(\mathbb{F}_p)$ and $A \subset \mathcal{B}_g:=g^{-1}\mathcal{B}g$ for some $g \in \mathrm{SL}_2(\mathbb{F}_p)$. Since $A \nsubseteq \mathcal{B}$, we have $g \notin \mathcal{B}$, and $g$ factorizes as
$$
\begin{equation*}
g=b \omega \begin{pmatrix}1 &v \\ 0 &1\end{pmatrix}, \qquad b \in \mathcal{B}, \qquad \omega=\begin{pmatrix}0 &1\\ -1 &0\end{pmatrix}.
\end{equation*}
\notag
$$
It can readily be seen that such a representation exists for all $g \notin \mathcal{B}$ and, moreover, it is unique. Thus, any element of $\mathcal{B}_g$ is uniquely represented as a product
$$
\begin{equation*}
\begin{aligned} \, &\begin{pmatrix}-v &-1 \\ 1 &0\end{pmatrix} \begin{pmatrix}\lambda &u \\ 0 &\lambda^{-1}\end{pmatrix} \begin{pmatrix}0 &1 \\ -1 &-v\end{pmatrix} \\ &\qquad=\begin{pmatrix}\lambda^{-1}+uv &-\lambda v+v^2 u+\lambda^{-1}v \\ -u &\lambda-uv\end{pmatrix}, \qquad \lambda \in \mathbb{F}_p^*, \quad u \in \mathbb{F}_p. \end{aligned}
\end{equation*}
\notag
$$
In other words,
$$
\begin{equation*}
\mathcal{B}_g=\biggl\{ \begin{pmatrix}\lambda^{-1}+uv &-\lambda v+v^2 u+\lambda^{-1}v \\ -u &\lambda-uv\end{pmatrix} \Bigm| \lambda \in \mathbb{F}_p^*, u \in \mathbb{F}_p \biggr\}.
\end{equation*}
\notag
$$
Thus,
$$
\begin{equation*}
\Gamma:=\Omega \cap \mathcal{B}_g =\biggl\{ \begin{pmatrix}\lambda^{-1}+u_0v &-\lambda v+v^2 u_0+\lambda^{-1}v \\ -u_0 &\lambda-u_0v\end{pmatrix} \Bigm| \lambda \in \mathbb{F}_p^* \biggr\}.
\end{equation*}
\notag
$$
We apply the automorphism $\psi\colon g \mapsto \begin{pmatrix}0 &1 \\ -1 &-v\end{pmatrix} g \begin{pmatrix}-v &-1 \\ 1 &0\end{pmatrix}$. Then $\psi(A) \subset \mathcal{B}$ and
$$
\begin{equation*}
\Gamma':=\psi(\Gamma)=\biggl\{\begin{pmatrix}\lambda &u_0 \\ 0 &\lambda^{-1}\end{pmatrix} \Bigm| \lambda \in \mathbb{F}_p^* \biggr\}.
\end{equation*}
\notag
$$
Now we can use Lemma 7 for $n=2/\delta$, and thus the discussion of the first case is complete, Note that our reasoning means the following: the intersection $\mathcal{B}$ c $\Omega_{-u_0}$ coincides with $\Gamma'$ up to some inner automorphism of $\mathcal{B}$.
Case 2. It remains to consider a set $A$ that generates the whole of $\mathrm{SL}_2(\mathbb{F}_p)$. Here it suffices to have an estimate of $n$ by a constant that does not depend on $\delta$. Indeed, since $|A| \gg p$, it follows that, by Theorem 13, cubing the set $A$ increases the cardinality $Cp^{{1}/{24}}$ times (where $C$ is an absolute constant), and then for the power $A^{3^k}$, where $k$ is some absolute constant, we can claim that $|A^{3^k}| \gg p^{2+{1}/{15}}$. Hence $A^{30\cdot 3^k}=\mathrm{SL}_2(\mathbb{F}_p)$ by Theorem 9. In particular, $A^n \cap \Omega_{-u_0} \neq \varnothing$. This completes the proof of the theorem. We make several remarks concerning the theorem just proved. It is clear that a set $A$ satisfying the conditions of Theorem 7 also contains an element of the form $\begin{pmatrix}* &b \\ * &*\end{pmatrix}$ for each $b$ (provided that $A$ does not entirely consist of lower triangular matrices). This follows, for example, from the fact that the map $\begin{pmatrix}a & b \\ c & d\end{pmatrix} \mapsto \begin{pmatrix}d &-c\\ -b &a\end{pmatrix}$ is an inner automorphism of $\mathrm{SL}_2(\mathbb{F}_p)$ under the conjugation by ${\omega=\begin{pmatrix}0 &1 \\ -1 &0\end{pmatrix}}$. Also note that in the general case it is impossible to overcome the $p^2$ barrier if we are looking, for example, for an element of $A^n$ of the form $\begin{pmatrix}-1 &*\\ * &*\end{pmatrix}$. Indeed, assume that the equation $x^2=-1 \pmod{p}$ has no solutions in $\mathbb{F}_p$. Then the subgroup
$$
\begin{equation*}
\biggl\{\begin{pmatrix}\lambda^2 &u \\ 0 &\lambda^{-2}\end{pmatrix} \biggm|\lambda \in \mathbb{F}_p^*, \ u \in \mathbb{F}_p \biggr\}
\end{equation*}
\notag
$$
has size ${p(p-1)}/{2}$ and does not contain elements of the considered form. Now we can readily prove Theorem 6. Proof of Theorem 6. We write $Q=p$. Then $A=A_2(p)$ has cardinality $|A| \gg_M p^{1.06}$ by (1.11) and (1.13). By Theorem 7 there exists $C$ such that $ A^C \cap \Omega_c \neq \varnothing$. It remains to apply Lemma 3. This completes the proof of the theorem. We note that we can set $C=30 \cdot 3^{17}$ in Theorem 6 proved above, because
$$
\begin{equation*}
\omega_2 \biggl(\frac{25}{24}\biggr)^{17}>2+\frac{1}{15}.
\end{equation*}
\notag
$$
This constant can readily be improved. 2.2. Proof of Theorem 4To prove Theorem 4 we must use some specific features of the set $A$. To do this we prove several lemmas. Proof. Consider the product
$$
\begin{equation*}
\begin{pmatrix}p_{k-1} &p_{k} \\ q_{k-1} &q_{k}\end{pmatrix} \begin{pmatrix} 1 &u\\ 0 &1\end{pmatrix} =\begin{pmatrix}p_{k-1} &up_{k-1}+p_k \\ q_{k-1} &uq_{k-1} +q_k\end{pmatrix}=\begin{pmatrix}x &y\\ z &t\end{pmatrix}.
\end{equation*}
\notag
$$
From $x$, $y$, $z$ and $t$ we can recover $p_{k-1}$ and $q_{k-1}$ and, from these, in turn, recover the elements $p_k$ and $q_k$ in at most $M$ ways by (1.6). Finally, using these data we can recover $u=(y-p_k) / p_{k-1}$. We note that $Q < p$, and thus all numerators and denominators of convergents are distinct from zero. Thus, the matrices $\begin{pmatrix}p_{k-1} &p_{k} \\ q_{k-1} &q_{k}\end{pmatrix} \in A$ and $\begin{pmatrix} 1 &u\\ 0 &1\end{pmatrix} \in \mathcal{U}$ are recovered from $\begin{pmatrix}x &y\\ z &t\end{pmatrix}$ in at most $M$ ways, and we have proved the first part of the lemma.
The other part can be established similarly: we write
$$
\begin{equation*}
\begin{pmatrix} 1 &u\\ 0 &1\end{pmatrix} \begin{pmatrix}p_{k-1} &p_{k} \\ q_{k-1} &q_{k}\end{pmatrix} = \begin{pmatrix}p_{k-1}+uq_{k-1} &p_k+uq_k \\ q_{k-1} &q_k\end{pmatrix}=\begin{pmatrix}x &y\\ z &t\end{pmatrix}.
\end{equation*}
\notag
$$
From $x$, $y$, $z$ and $ t$ we recover $q_{k-1}$ and $q_k$ and, from these, in turn, the elements $p_{k-1}$ and $p_k$ using relation (1.6), which defines $u$ uniquely. This completes the proof of the lemma. Proof. We prove the first inequality only, since the other is established in a similar way. Let $\begin{pmatrix}p_{t-1} &p_t \\ q_{t-1} &q_t\end{pmatrix} \begin{pmatrix}a & b \\ c & d\end{pmatrix}= \begin{pmatrix}x &y \\ z &w\end{pmatrix}$. It suffices to show that there exist at most $QM$ ways to recover $p_k$ and $q_k$ from the right-hand side. If we write out the product of matrices, then the equality of the entries in the left-hand columns yields
$$
\begin{equation*}
\begin{cases} ap_{t-1}+cp_t=x, \\ aq_{t-1}+cq_t=z. \end{cases}
\end{equation*}
\notag
$$
We multiply these two equalities by $q_{t-1}$ and $p_{t-1}$, respectively, and consider the difference:
$$
\begin{equation*}
\begin{aligned} \, &ap_{t-1}q_{t-1}+cp_tq_{t-1}-aq_{t-1}p_{t-1}-cq_tp_{t-1}=xq_{t-1}-zp_{t-1} \\ &\qquad \Longleftrightarrow\quad -c=xq_{t-1}-zp_{t-1}. \end{aligned}
\end{equation*}
\notag
$$
We note that both integers $x$ and $z$ cannot vanish simultaneously, and therefore, if we assume without loss of generality that $x \neq 0$, then there exist at most $Q$ values for $p_{t-1}$, from each of which one can calculate $q_{t-1}=(-c+zp_{t-1})/x$ and, from $p_{t-1}$ and $q_{t-1}$, can recover the elements $p_t$ and $q_t$ in at most $M$ ways by (1.6). The matrix $\begin{pmatrix}a & b \\ c & d\end{pmatrix} \in \Omega_c$ is now determined uniquely. This completes the proof of the lemma. Now we are ready to prove Theorem 4. Proof of Theorem 4. We can assume that $p \gg_\varepsilon 1$, because simpler arguments work for small $p=O_\varepsilon(1)$: using Theorems 9 and 13 we can write $A_M(p)^k=\mathrm{SL}_2(\mathbb{F}_p)$ for $k=O(1)$, and thus we have
Now, we set where we choose the number $M$ below. We note that, if $AA_\varepsilon A \cap \Omega_u \neq \varnothing$, then by Lemma 3 there exists a fraction $a/q \in F_M$ with the required properties
$$
\begin{equation*}
q \equiv u\pmod{p}, \qquad (a, q)=1\quad\text{and} \quad q \leqslant 4 p^2 p^\varepsilon=O(p^{2+\varepsilon}).
\end{equation*}
\notag
$$
Thus, it suffices to prove that $AA_\varepsilon A \cap \Omega_u \neq \varnothing$. Since $\Omega_u\mathcal{U}=\Omega_u$, we can write this relation in the form
$$
\begin{equation}
E=\begin{pmatrix}1 &0 \\ 0 &1\end{pmatrix} \in \Omega_{-u} AA_\varepsilon A \mathcal{U}.
\end{equation}
\tag{2.5}
$$
Consider the function $f=(\Omega_{-u} A) * A_\varepsilon * (A \mathcal{U})$. Then (2.5) is equivalent to $f(E) \neq 0$. Let us write the inversion formula, where we single out the leading term and use formula (1.10):
$$
\begin{equation}
|G|f(E)=|\Omega_{-u} A| \,|A_\varepsilon|\, |A \mathcal{U}| +\sum_{\rho \neq 1} d_\rho \bigl\langle \widehat{ (\Omega_{-u} A)}(\rho) * \widehat{A_\varepsilon}(\rho) * \widehat{(A \mathcal{U})} (\rho), \rho(E) \bigr\rangle.
\end{equation}
\tag{2.6}
$$
Now we estimate the sum of the remaining terms. We note that $\rho (E)$ is the identity matrix. We use (1.2) and the Cauchy-Bunyakovsky-Schwarz inequality to extract the factor $\|A_\varepsilon\|_{\mathrm{op}}$. We have
$$
\begin{equation*}
\sum_{\rho \neq 1} d_\rho \bigl\langle \widehat{ (\Omega_{-u} A)}(\rho) * \widehat{A_\varepsilon}(\rho) * \widehat{(A \mathcal{U})} (\rho), \rho(E) \bigr\rangle \leqslant \|A_\varepsilon\|_{\mathrm{op}}\sum_{\rho}d_\rho\| \widehat{\Omega_{-u} A}\| \,\|\widehat{A \mathcal{U}}\|.
\end{equation*}
\notag
$$
Using the Cauchy-Bunyakovsky-Schwarz inequality again and then using Parseval’s equality (1.7) we obtain
$$
\begin{equation*}
\begin{aligned} \, &\sum_{\rho}d_\rho\| \widehat{\Omega_{-u} A}\| \,\|\widehat{A \mathcal{U}}\| \leqslant \biggl( \sum_{\rho}d_\rho\| \widehat{\Omega_{-u} A}\|^2\biggr)^{1/2} \biggl( \sum_{\rho}d_\rho \|\widehat{A \mathcal{U}}\|^2\biggr)^{1/2} \\ &\qquad\leqslant \sqrt{|G|\,|\Omega_{-u} A|}\sqrt{|G|\,|A \mathcal{U}|}, \end{aligned}
\end{equation*}
\notag
$$
that is,
$$
\begin{equation}
\sum_{\rho}d_\rho\| \widehat{\Omega_{-u} A}\| \,\|\widehat{A \mathcal{U}}\| \leqslant \sqrt{|G|\,|\Omega_{-u} A|}\sqrt{|G|\,|A \mathcal{U}|}.
\end{equation}
\tag{2.7}
$$
By Corollary 2 there exists $\varepsilon'=\varepsilon'(\varepsilon)$ such that $\| A_\varepsilon \|_{\mathrm{op}} \ll |A_\varepsilon|^{1-\varepsilon'}$.
Now it is sufficient to prove that
$$
\begin{equation*}
|A_\varepsilon|^{2\varepsilon'}\,|\Omega_{-u} A| \,|A \mathcal{U}| \geqslant p^6 > |G|^2,
\end{equation*}
\notag
$$
since in this case it follows from (2.6) and (2.7) that $f(E) \neq 0$. It can readily be seen that $|\Omega_{-u}| \geqslant p(p-1) \geqslant{p^2}/{2}$. By Lemmas 8 and 9
$$
\begin{equation*}
|\Omega_{-u} A| \,|A \mathcal{U}| \geqslant \frac{p^2}{2M}|A|^2.
\end{equation*}
\notag
$$
Now, using Lemma 2 we choose $M$ so that
$$
\begin{equation*}
\omega_M(1+\varepsilon \varepsilon ') > 1+\frac{\varepsilon \varepsilon'}{2}.
\end{equation*}
\notag
$$
Then for some constant $C_\varepsilon$ we have
$$
\begin{equation*}
|A_\varepsilon|^{\varepsilon'}\,|A| \geqslant C_\varepsilon p^{2+\varepsilon \varepsilon'}.
\end{equation*}
\notag
$$
Combining the above we obtain
$$
\begin{equation*}
|A_\varepsilon|^{2\varepsilon'}\,|\Omega_{-u} A|\, |A \mathcal{U}| \geqslant C_\varepsilon p^{6+2\varepsilon \varepsilon'} \geqslant p^6,
\end{equation*}
\notag
$$
since, as we said before, the prime number $p$ can be assumed to be sufficiently large. This completes the proof of Theorem 4. 2.3. Proof of Theorem 5To prove Theorem 5 we need another lemma (cf. Lemma 9). Lemma 10. Let $u, v \in \mathbb{Z}$ be integers such that $0 < u < v$, $2vQ < p$ and $(u, v)=1$. Then $|( \Omega_{-u}^v)^{-1}A_M(Q)|=p|A_M(Q)|$. Proof. Recall that
$$
\begin{equation*}
\Omega_{-u}^v=\biggl\{\begin{pmatrix}v &* \\ -u &*\end{pmatrix} \in \mathrm{SL}_2(\mathbb{F}_p) \biggr\}\quad\text{and}\quad ( \Omega_{-u}^v)^{-1}=\biggl\{\begin{pmatrix}* & *\\ u & v\end{pmatrix} \in \mathrm{SL}_2(\mathbb{F}_p) \biggr\}.
\end{equation*}
\notag
$$
We claim that the map $\psi\colon A_M(Q) \to \mathbb{F}_p^2$ defined by
$$
\begin{equation}
\psi\colon \begin{pmatrix}p_{k-1} &p_{k} \\ q_{k-1} &q_{k}\end{pmatrix} \mapsto \begin{pmatrix}u p_{t-1}+vq_{t-1} &up_t+vq_t\end{pmatrix}=\begin{pmatrix}u & v \end{pmatrix} \begin{pmatrix}p_{k-1} &p_{k} \\ q_{k-1} &q_{k}\end{pmatrix}
\end{equation}
\tag{2.8}
$$
is injective. Using (1.6) we choose a rational number $r \in (0, 1)$ such that its convergents ${n_{t-1}}/{m_{t-1}}$, ${n_t}/{m_t}$ have the following properties: We write the numbers under consideration as continued fractions,
$$
\begin{equation}
\frac{n_t}{m_t}=[0; a_1, \dots, a_t], \qquad \frac{p_k}{q_k}=[0; b_1, \dots, b_k], \qquad \frac{n_{t+k}}{m_{t+k}}=[0; a_1, \dots, a_t, b_1, \dots, b_k].
\end{equation}
\tag{2.9}
$$
(In the last case we combined two records of our continued fractions, which gave us the number ${n_{t+k}}/{m_{t+k}}$.) Let us show that if
$$
\begin{equation*}
\psi\biggl(\begin{pmatrix}p_{k-1} &p_{k} \\ q_{k-1} &q_{k}\end{pmatrix}\biggr) =\begin{pmatrix}x &y\end{pmatrix},
\end{equation*}
\notag
$$
then the matrix $\begin{pmatrix}p_{k-1} &p_{k} \\ q_{k-1} &q_{k}\end{pmatrix} \in A_M(Q)$ is uniquely recovered from the pair $x$, $y$. Since $u p_{t-1}+vq_{t-1} \leqslant 2aQ < p$, it follows that $u p_{t-1}+vq_{t-1}=x$ in $\mathbb{Z}$ and, similarly, $up_t+vq_t=y$. By the construction of the continued fraction for ${n_{t+k}}/{m_{t+k}}$, it follows from (2.9) and the definition (2.8) of the function $\psi$ that
$$
\begin{equation*}
\begin{aligned} \, & \begin{pmatrix}n_{t+k-1} &n_{t+k} \\ m_{t+k-1} &m_{t+k}\end{pmatrix} =\begin{pmatrix}n_{t-1} &n_t \\ m_{t-1} &m_t\end{pmatrix}\begin{pmatrix}p_{k-1} &p_{k} \\ q_{k-1} &q_{k}\end{pmatrix} \\ &\qquad = \begin{pmatrix}n_{t-1} &n_t \\ u &v\end{pmatrix}\begin{pmatrix}p_{k-1} &p_{k} \\ q_{k-1} &q_{k}\end{pmatrix} =\begin{pmatrix}* & *\\ x & y\end{pmatrix}. \end{aligned}
\end{equation*}
\notag
$$
Hence $m_{t+k-1}=x$ and $ m_{t+k}=y$. Thus, given $x$ and $y$, we can recover all partial quotients $a_1, \dots, a_t, b_1, \dots, b_k$, and therefore also the preimage $\begin{pmatrix}p_{k-1} &p_{k} \\ q_{k-1} &q_{k}\end{pmatrix}$ of the pair $x$, $y$. That is, $\psi$ is an injection.
Now note that the set $( \Omega_{-u}^v)^{-1}$ is invariant under multiplication by $\mathcal{U}$ from the left: Then Thus, it is necessary and sufficient to prove that $\begin{pmatrix}v^{-1} & 0\\ u &v\end{pmatrix}A_M(Q)$ intersects each coset $\mathcal{U}g, g \in \mathrm{SL}_2(\mathbb{F}_p)$ in at most one element. Since $\mathcal{U}\begin{pmatrix}x &y\\ z &t\end{pmatrix}=\biggl\{ \begin{pmatrix}* & *\\ z &t\end{pmatrix} \in \mathrm{SL}_2(\mathbb{F}_p) \biggr\}$ is determined uniquely by the two bottom entries, and the pairs of such entries are distinct due to the injectivity of $\psi$, it follows that the lemma is proved.Finally, let us prove the last theorem, Theorem 5. The method of the proof is very similar to the one we have just used, so we omit some details. Proof of Theorem 5. We set
$$
\begin{equation*}
A=A_M(Q), \qquad A_\varepsilon=A_M(p^\varepsilon)\quad\text{and} \quad Q=p^{1-\varepsilon_1};
\end{equation*}
\notag
$$
we choose the parameters $\varepsilon_1$ and $M$ below. We must show that
$$
\begin{equation*}
AA_\varepsilon A \cap \Omega_{-u}^v \neq \varnothing.
\end{equation*}
\notag
$$
Since $\Omega_{-u}^v\mathcal{U}=\Omega_{-u}^v$, we can rewrite this relation in the form
$$
\begin{equation}
E \in ( \Omega_{-u}^v )^{-1} AA_\varepsilon A \mathcal{U}.
\end{equation}
\tag{2.10}
$$
Consider the function $f=(( \Omega_{-u}^v )^{-1} A) * A_\varepsilon * (A \mathcal{U})$. Then (2.10) is equivalent to $f(E) \neq 0$. By Corollary 2 there exists
$$
\begin{equation*}
\varepsilon'=\varepsilon'(\varepsilon)\colon \quad \| A_\varepsilon \|_{\mathrm{op}} \ll |A_\varepsilon|^{1-\varepsilon'}.
\end{equation*}
\notag
$$
Set $\varepsilon_1={\varepsilon \varepsilon'}/{2}$. Since we can use the same reasoning as in Theorem 4, it suffices to establish the bound
$$
\begin{equation*}
|A_\varepsilon|^{2\varepsilon'}\,|( \Omega_{-u}^v )^{-1} A|\, |A \mathcal{U}| \geqslant p^6 > |G|^2.
\end{equation*}
\notag
$$
By Lemmas 8 and 10 we have
$$
\begin{equation*}
|( \Omega_{-u}^v )^{-1} A|\, |A \mathcal{U}| \geqslant \frac{p^2}{M}|A|^2.
\end{equation*}
\notag
$$
Now, using Lemma 2 we choose the parameter $M$ so that
$$
\begin{equation*}
\omega_M\biggl(1+\frac{\varepsilon \varepsilon'}{2}\biggr) > 1+ \frac{\varepsilon \varepsilon'}{4}.
\end{equation*}
\notag
$$
Then for some constant $C_\varepsilon$ we have Combining these inequalities we obtain since $p$ can be assumed to be sufficiently large. Thus, the theorem is proved. We note that we take $\varepsilon_1$ depending on $\varepsilon$. Unfortunately, our method does not enable us to replace $\varepsilon_1$ by an absolute constant, for example, $1/2$. The point is that in such a case we would have to take $v \asymp p^{1/2}$ and $Q\asymp p^{1/2}$ in Lemma 10, and then we would obtain $|(\Omega_{-u}^v)^{-1}A_M(Q)|=p|A_M(Q)| \ll p^2$, which is too small a cardinality of a subset of the group to use Fourier analysis. By Theorem 5 we can claim that for any sufficiently large prime number $p$ there exist coprime positive integers $a$ and $q$ such that the partial quotients of the continued fraction for $a/q$ are bounded by an absolute constant and, moreover, Vinogradov’s conjecture on the least quadratic residue reads as follows. Conjecture 2. For every $\varepsilon > 0$ and for a sufficiently large prime number $p$ there exists a quadratic residue $a$ such that $({a}/{p})=1$ and $a < p^\varepsilon$. If Vinogradov’s conjecture holds, then we can also find a pair of numbers $a, q$ such that
$$
\begin{equation*}
(a, q)=1, \qquad \biggl( \frac{a}{p} \biggr)=1, \qquad q=1-a \pmod{p}\quad\text{and} \quad \frac{a}{q} \in F_M.
\end{equation*}
\notag
$$
Citation in format AMSBIB
\Bibitem{Lya22} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|