On some results of Korobov and Larcher and Zaremba's conjecture

1. Problem Statement and Context

Zaremba's Conjecture:
The central problem addressed is Zaremba's conjecture (1971), which posits the existence of an absolute constant $M$ such that for any integer $q > 1$, there exists an integer $a$ coprime to $q$ where the partial quotients $c_j$ in the continued fraction expansion of $a/q = [0; c_1, \dots, c_s]$ are all bounded by $M$ (i.e., $M(a) = \max c_j \le M$).

• Historical Context: Zaremba conjectured $M=5$. Hensley later suggested $M=2$ for large primes.
• Previous Bounds:
  • Korobov (1960): Proved $M(a) \ll \log q$ for prime $q$.
  • Bourgain & Kontorovich: Proved the conjecture for "almost all" $q$ using the Bourgain-Gamburd machine.
  • Shkredov (Previous Work [40]): Improved Korobov's bound to $M = O(\log q / \log \log q)$ for specific sets of denominators using a mix of additive combinatorics and the affine sieve.

Motivation:
The problem is deeply connected to numerical integration and the discrepancy of sequences. The discrepancy of the sequence $X(a, q) = \{(j/q, aj/q)\}_{j=1}^q$ is bounded by the sum of partial quotients $S(a) = \sum c_j$ and the maximum partial quotient $M(a)$. Lower bounds on these quantities lead to better quasi-Monte Carlo integration methods.

2. Methodology

The paper employs a sophisticated combination of Analytic Number Theory, Additive Combinatorics, and Fractal Geometry.

A. The Bourgain-Gamburd Machine and Affine Sieve

The author utilizes the expansion results in $SL_2(\mathbb{Z}/q\mathbb{Z})$ (Helfgott's expansion) and the Bourgain-Gamburd machine to establish uniform distribution properties of sets of inverses. Specifically, the paper relies on the fact that for a set $A \subset \mathbb{Z}/q\mathbb{Z}$ constructed from continued fractions, the intersection $A \cap A^{-1}$ is large and well-distributed.

B. Ahlfors-David Sets and Cantor Structures

The set of rationals with bounded partial quotients, denoted $Z_M(t)$, is shown to possess a Cantor-type structure. The author proves that $Z_M(t)$ is an Ahlfors-David set (a fractal set with specific measure properties) of Hausdorff dimension $w_M \approx 1 - \frac{6}{\pi^2 M}$.

• This structure allows the author to treat the set of numerators $a$ as a collection of disjoint intervals indexed by continuants.
• The dimension $w_M$ is crucial for estimating the cardinality of the set of valid numerators.

C. Critical Denominators and Independence

A novel technical contribution is the analysis of critical denominators $x(a)$ (denominators of convergents to $a/q$).

• Independence: The author proves that for elements within a small interval of the Cantor set, their critical denominators are "independent" in a Diophantine sense. Specifically, linear combinations $\alpha x_1 + \beta x_2 + \gamma x_3 \equiv 0 \pmod q$ with small coefficients imply trivial solutions.
• Repulsion: This independence leads to "repulsion" inequalities, preventing critical denominators from clustering too closely to $\sqrt{q}$, which would otherwise violate the bounded partial quotient condition.

D. Diophantine Approximation

The proof involves eliminating "bad" numerators where partial quotients become large. This is done by showing that if too many numerators had large partial quotients, one could construct a linear Diophantine approximation that contradicts the repulsion properties derived from the independence of critical denominators.

3. Key Contributions and Results

The paper presents three main theorems (Theorems 6, 7, and 8) that improve upon previous bounds by Korobov and Larcher. The results apply to a set of denominators $\mathcal{Z}$ which includes all sufficiently large primes and square-free numbers with large prime factors.

Theorem 6: Improved Bound on the Sum of Partial Quotients

• Result: For $q \in \mathcal{Z}$, there are at least $q^{2w_M - 1 - o(1)}$ integers $a$ coprime to $q$ such that the sum of partial quotients $S(a) \ll \sqrt{\log \log q} \cdot \log q$.
• Significance: This improves Larcher's bound on the sum of partial quotients. It provides a lower bound on the number of such numerators, showing they are abundant, not just existent.

Theorem 7: Improved Bound on the Maximum Partial Quotient

• Result: For $q \in \mathcal{Z}$ and $M \ge C\sqrt{\log q}$, there are at least $q^{2w_M - 1 - o(1)}$ integers $a$ such that $M(a) \le M + 2$.
• Significance: This improves the previous bound of $O(\log q / \log \log q)$ to $O(\sqrt{\log q})$. It establishes that for a large set of numerators, the partial quotients are significantly smaller than previously known.

Theorem 8: Resolution for Fixed $M$ (Zaremba's Conjecture for Primes)

• Result: There exist absolute constants $M, \bar{M}$ such that for any sufficiently large prime $q$, there are at least $q^{1 - O(1/M)}$ integers $a$ coprime to $q$ with $M(a) \le \bar{M}$.
• Significance: This is the strongest result. It proves Zaremba's conjecture (existence of bounded partial quotients) for all sufficiently large prime denominators. While the constant $\bar{M}$ is large (and computable), it is absolute and independent of $q$.
• Note: The lower bound $q^{1 - O(1/M)}$ is weaker than the $q^{2w_M - 1}$ bound in Theorems 6 and 7, but it guarantees the existence of solutions for a fixed $M$.

4. Technical Highlights and Mechanisms

1. Transition from "Almost All" to "All": Unlike Bourgain and Kontorovich, who proved the conjecture for almost all $q$, Shkredov's method (using the specific structure of $Z_M(t)$ and critical denominators) allows the result to hold for every sufficiently large prime $q$.
2. The "Middle Interval" Phenomenon: The paper identifies a regime where $M = \Omega(\sqrt{\log q})$. In this regime, if partial quotients are bounded everywhere except a "middle interval" of the continued fraction, the set of such numerators has the same asymptotic size as the full set of Zaremba numerators. This suggests a specific structural rigidity in the continued fractions of these numbers.
3. Optimality of the Method: The author notes that the bound $M \sim \sqrt{\log q}$ in Theorem 7 is likely close to the limit of the current method. The "loss" comes from the expansion rate in the modular group (the Bourgain-Gamburd machine), specifically the requirement for uniform distribution in sets of size $q^{1/9}$.

5. Significance and Applications

• Number Theory: The paper provides the first proof of Zaremba's conjecture for all large primes, a major step toward the general conjecture.
• Numerical Integration: The results yield sequences with extremely low discrepancy, improving the efficiency of quasi-Monte Carlo methods for high-dimensional integration.
• Combinatorics: The techniques have applications in counting spanning trees in graphs and linear extensions of posets, as noted in the introduction.
• Fractal Geometry: The rigorous application of Ahlfors-David set theory to the distribution of continued fractions offers a new geometric perspective on Diophantine problems.

Conclusion

I.D. Shkredov's paper represents a significant advancement in the theory of continued fractions. By synthesizing the Bourgain-Gamburd expansion machinery with the fractal geometry of Cantor sets and novel Diophantine independence arguments, the author proves Zaremba's conjecture for all large primes and provides tight lower bounds on the number of such numerators. The work bridges the gap between "almost all" results and "all" results, offering deep insights into the structure of rational numbers with bounded partial quotients.