🔢 mathematics

Lifting all elements in $\mathrm{SL}_n(\mathbb{Z}/q\mathbb{Z})$

This paper establishes that every element in $\mathrm{SL}_n(\mathbb{Z}/q\mathbb{Z})$ can be lifted to $\mathrm{SL}_n(\mathbb{Z})$ with a norm bounded by $Cq^2\log q$ , while proving the existence of elements requiring lifts of norm at least $q^{2+o(1)}$ , a result derived from a new finding regarding small elements in $(\mathbb{Z}/q\mathbb{Z})^\times$ possessing large $n$ -th roots.

Original authors: Amitay Kamber, Péter P. Varjú

Published 2026-03-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Amitay Kamber, Péter P. Varjú

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, infinite library of integer matrices (grids of whole numbers) called $SL_n(\mathbb{Z})$ . Now, imagine you have a small, finite "shadow" version of this library called $SL_n(\mathbb{Z}/q\mathbb{Z})$ . This shadow library is created by taking every number in the big library and squinting at it through a filter that only shows the remainder when divided by a number $q$ .

The big question this paper asks is: If you pick a specific picture in the small shadow library, how big does the original picture in the big library have to be to cast that shadow?

In mathematical terms, this is called "lifting." You want to find the "smallest" possible original matrix that creates a specific shadow.

Here is the breakdown of what the authors discovered, using some everyday analogies:

1. The "Average" vs. The "Worst Case"

Think of the shadow library as a room full of lockers.

The Average Case: If you walk into the room and pick a locker at random, you can usually find a key (a lift) that isn't too heavy. Recent research showed that for almost all lockers, the key weighs about $q^{1 + 1/n}$ . It's a manageable weight.
The Worst Case: The authors asked, "Is there a 'bad' locker where the key is incredibly heavy?"
- The Discovery: Yes! They proved that for every $q$ , there is at least one "evil" locker that requires a key weighing at least $q^2$ (roughly).
- The Analogy: Imagine trying to open a safe. For 99% of safes, a standard key works. But there is one specific safe where you need a key the size of a skyscraper. The authors found that specific safe and proved it exists.

2. The Upper Limit: "We Can Always Find a Key"

While one locker might need a skyscraper-sized key, the authors also proved that no locker ever needs a key bigger than $q^2 \times \log(q)$ .

The Analogy: Even for that "evil" locker, you don't need a key the size of the universe. You just need a key the size of a skyscraper. They found a method to construct a key for every single locker that stays within this limit.

3. The Secret Ingredient: The "Magic Root"

How did they prove the "evil locker" exists? They used a clever trick involving roots.

Imagine you have a number $q$ . You are looking for a "root" (a number that, when multiplied by itself $n$ times) that is very small, but when you multiply that root by $n$ , it becomes huge.
The Analogy: It's like finding a tiny seed that, when you water it with a specific amount of liquid ( $n$ ), suddenly grows into a giant tree.
They used tools from Additive Combinatorics (specifically "Bohr sets," which are like complex, multi-dimensional grids) to prove that these "magic seeds" always exist. This was a major breakthrough in its own right.

4. The Construction: Building the Key

To prove they could lift every element (Theorem 1.3), they used a two-step construction process:

The Foundation: They first built the first $n-1$ rows of the matrix. They showed you can do this with relatively small numbers (like $q \log q$ ).
The Roof: The last row is the tricky part. To make the whole matrix work (determinant = 1), the last row has to be huge (around $q^2$ ).

The Analogy: Imagine building a house. You can build the walls and the first floor with standard bricks. But to put the roof on and make the house stable, you need a massive, heavy beam. You can't avoid using that heavy beam for the roof, but you don't need to use heavy bricks for the walls.

5. Why Does This Matter?

This isn't just about abstract math; it connects to cryptography and network design.

Expanders: These matrices are used to build "expander graphs," which are super-efficient networks (like the internet or social networks) where you can get from any point to any other point very quickly.
The "Big Holes": The authors found that while the network is usually very efficient (short paths), there are specific "holes" or bottlenecks where the path is much longer than expected. Understanding these worst-case scenarios helps engineers design more robust systems that don't get stuck.

Summary

The Problem: How big is the original number needed to create a specific remainder?
The Average: Usually small ( $q^{1.3}$ for $n=2$ ).
The Worst Case: Can be huge ( $q^2$ ).
The Guarantee: You never need more than $q^2 \log q$ .
The Method: They found a "magic seed" (a small number with a large root) to prove the worst case exists, and used a "foundation and roof" strategy to prove you can always find a solution.

In short, the authors mapped the entire landscape of these numbers, showing us exactly where the "mountains" (hard cases) are and proving that no mountain is higher than a specific limit.

1. Problem Statement

The paper addresses the optimal lifting problem for the special linear group $SL_n(\mathbb{Z})$ . Specifically, it investigates the operator norm $\|\gamma\|$ of matrices $\gamma \in SL_n(\mathbb{Z})$ that map to a given element $x \in SL_n(\mathbb{Z}/q\mathbb{Z})$ under the reduction modulo $q$ map $\pi_q$ .

The central question is to determine the minimal $T$ such that every element in the finite group $SL_n(\mathbb{Z}/q\mathbb{Z})$ can be lifted to an element in $SL_n(\mathbb{Z})$ with norm $\|\gamma\| \le T$ .

Average Case (Almost-diameter): Previous work (Theorem 1.1) established that for square-free $q$ , almost all elements can be lifted with norm $O(q^{1+1/n+\epsilon})$ .
Worst Case (Diameter): The paper seeks to determine the bound required to lift every element, not just almost all.

2. Key Contributions and Main Results

The authors provide a near-complete solution to the worst-case lifting problem, establishing a sharp gap between the average case and the worst case.

Theorem 1.2 (Lower Bound / Worst Case)

There exists an element $x \in SL_n(\mathbb{Z}/q\mathbb{Z})$ such that every lift $\gamma \in SL_n(\mathbb{Z})$ satisfies:
$\|\gamma\| \ge C_{n,\epsilon} q^{2-\epsilon}$
This confirms a conjecture by Sarnak (previously known only for $n=2$ and specific $q$ ) and extends it to all $n \ge 2$ .

Theorem 1.3 (Upper Bound / Existence)

There exists a constant $C_n$ such that every element $x \in SL_n(\mathbb{Z}/q\mathbb{Z})$ has a lift $\gamma \in SL_n(\mathbb{Z})$ satisfying:
$\|\gamma\| \le C_n q^2 \log q$

Significance of the Gap

Ratio of Exponents: The ratio between the worst-case exponent ($2$) and the average-case exponent ( $1 + 1/n$ $1 + 1/ n$ ) is $\frac{2n}{n+1}$ $\frac{2 n}{n + 1}$ .
- For $n=2$ , the ratio is $4/3$ .
- As $n \to \infty$ , the ratio approaches $2$.
"Big Holes": This result demonstrates that the "diameter" of the Cayley graph (worst-case distance) is significantly larger than the "almost-diameter" (average distance), a phenomenon Sarnak termed "big holes."

3. Methodology and Proof Techniques

The proof is divided into two distinct parts corresponding to the lower and upper bounds.

A. Proving the Lower Bound (Theorem 1.2)

The authors construct a specific "hard" element in $SL_n(\mathbb{Z}/q\mathbb{Z})$ that forces any lift to have large entries.

Diagonal Construction: They choose a diagonal matrix $x = \text{diag}(\beta\alpha^{-1}, \beta, \dots, \beta)$ .
Linear Constraints: They analyze the tangent space of $SL_n$ at $x$ . Lifting $x$ to $SL_n(\mathbb{Z}/q^2\mathbb{Z})$ imposes a linear congruence on the diagonal entries of the lift $\gamma$ :
$\alpha a_1 + a_2 + \dots + a_n \equiv n\beta \pmod{q^2}$
To force a large norm, they need a $\beta$ such that $n\beta$ is large (close to $q^2$ ) while $\beta^n$ is small (so $x$ is small).
Additive Combinatorics (The Core Innovation): The existence of such a $\beta$ $β$ is guaranteed by Theorem 1.5, which states that for any $q$ $q$ , there exists a small element $\alpha$ $α$ with a large $n$ $n$ -th root $\beta$ $β$ (specifically, $|\beta^n|$ $∣ β^{n} ∣$ is small, but $|n\beta|$ $∣ n β ∣$ is large).
- Bohr Sets: The proof of Theorem 1.5 utilizes Bohr sets from additive combinatorics. They construct a set of frequencies generated by $n$ -th roots of small primes.
- Contradiction Argument: They assume the contrary (that no such large root exists), implying that $n$ lies in a small Bohr set. This Bohr set is approximated by a Generalized Arithmetic Progression (GAP) of bounded rank $r \le k$ .
- Matrix Commutativity: The structure of the frequencies induces a linear action on the GAP, represented by commuting integer matrices $B_j$ . The condition that $\beta^n$ is small implies $B_j^n$ are scalar matrices.
- Pigeonhole Principle: With sufficiently many generators, two matrices $B_{s_1}$ and $B_{s_2}$ must be scalar multiples of each other. This leads to a contradiction because the ratio of their eigenvalues would be an irrational $n$ -th root, yet the matrices are integer matrices.

B. Proving the Upper Bound (Theorem 1.3)

The proof generalizes Sarnak's approach for $n=2$ using a two-step lifting strategy:

Lifting the First $n-1$ Rows:
- The goal is to lift the first $n-1$ rows of $x$ to integers such that they can be completed to a matrix in $SL_n(\mathbb{Z})$ .
- This requires the rows to be linearly independent modulo every prime $p$ .
- Using probabilistic arguments and bounds on the number of "bad" lifts (where rows become dependent modulo $p$ ), they show that a lift with entries bounded by $O(q \log q)$ exists.
Lifting the Last Row:
- Once the first $n-1$ rows are fixed, the last row is determined by the determinant condition and the requirement to match $x \pmod q$ .
- This step involves solving a linear Diophantine equation. The authors show that the last row can be chosen with entries bounded by $O(q^2 \log q)$ .
- Lemma 1.6: They prove that the number of matrices with the first $n-1$ rows bounded by $T$ and the last row by $T^2$ is roughly $T^{n^2-1}$ , suggesting that the $q^2$ bound for the last row is essentially optimal if the first rows are kept small.

4. Additional Results and Context

Projective and Affine Spaces: The paper extends the analysis to the action of $SL_n(\mathbb{Z})$ $S L_{n} (Z)$ on the affine space $A_q$ $A_{q}$ and projective space $P_q$ $P_{q}$ .
- They define "diameter" and "almost-diameter" for these spaces.
- Proposition 5.3: They determine that the diameter of the projective space $P_q$ is exactly $1$ (in the exponent of $q$ ), meaning there exist pairs of points at distance $\approx \log q$ , even though the "almost-diameter" is conjectured to be $1/n$ .
Relation to Ramanujan Graphs: The results are compared to the diameter of LPS Ramanujan graphs. The factor $4/3$ (for $n=2$ ) appearing in the ratio of worst-case to average-case lifting is the same factor conjectured for the diameter of certain Ramanujan graphs.

5. Conclusion

This paper resolves the worst-case lifting problem for $SL_n(\mathbb{Z}/q\mathbb{Z})$ , showing that while "most" elements lift efficiently ( $q^{1+1/n}$ ), the "worst" elements require a significantly larger lift ( $q^2$ ). The proof introduces a novel application of additive combinatorics (Bohr sets and GAPs) to number theory problems involving matrix groups, specifically to construct elements with specific root properties. This establishes a definitive "big hole" phenomenon in the geometry of arithmetic groups.