Contents
1 Introduction 3
1.1 Small-set local testability and independent checks 3
1.2 Techniques 6
1.3 Concluding remarks 10
2 The Lin–Hsieh construction preserves full rank 10
2.1 The balanced product 10
2.2 Rank inheritance 12
3 A full-rank modification of HLMRZ 12
3.1 The HLMRZ construction 13
3.2 Equivariant maps and rank detection 14
3.3 The orbit matrix of the line product 15
3.4 The full-rank modification 16
4 LPS Ramanujan graphs on 2-groups 17
4.1 The graphs 18
4.2 The cubical complexes 22
5 Full-rank lossless graphs and the quantum code construction 23
5.1 Lossless graphs with a free 2-group action 24
5.2 Full-rank lossless expanders 25
5.3 The quantum codes 25
A Arithmetic background 29
A.1 Integral quaternions and the product structure 29
A.2 The LPS group and the tree 30
A.3 The Ramanujan property of congruence quotients 31
Introduction
Hong, Guo, and Lucas [6 ] showed that quantum information can remain protected for long times at low positive temperature even when the free-energy density is analytic at every positive temperature. Their construction brings together two properties of quantum LDPC codes: small-set confinement and independence of the specified sparse checks. Confinement supplies an energy penalty for errors, while independence makes the partition function exactly computable. Their work thus separates the dynamical protection of quantum information from the presence of a thermodynamic phase transition.
Their quantum examples have positive rate, but their distance and confinement range are of order N \sqrt{N} N , where N N N is the number of physical qubits, and their analysis guarantees a stretched-exponential memory timescale. They leave open whether the same combination can be achieved with asymptotically good quantum codes and confinement on a linear range. We answer this coding-theoretic question by constructing an explicit family of asymptotically good binary CSS quantum LDPC codes whose specified X X X - and Z Z Z -check matrices have full row rank and satisfy confinement on a linear range. The requirement is simultaneous: independence and confinement hold for the same sparse checks.
The physical consequences follow by applying the analysis of [6 ] with our improved code parameters, within their framework and under their dynamical assumptions. This gives a guaranteed memory lifetime of exp ( Ω ( N ) ) \exp(\Omega(N)) exp ( Ω ( N )) at sufficiently low fixed positive temperature, while preserving thermodynamic analyticity. We refer to [6 ] for the physical interpretation and dynamical analysis. We now explain the coding problem and the challenges in obtaining both properties simultaneously.
Small-set local testability and independent checks
The classical case. A binary linear code is specified by a parity-check matrix
H : F 2 n ⟶ F 2 m , C = ker H . H : \mathbb{F}_2^n \longrightarrow\mathbb{F}_2^m,\qquad C = \ker H. H : F 2 n ⟶ F 2 m , C = ker H .
The code is low-density parity-check (LDPC) when the row and column weights of H H H are bounded by constants: each check reads constantly many bits, and each bit participates in constantly many checks. Full row rank means that the specified checks are linearly independent, in which case dim C = n − m \dim C = n-m dim C = n − m .
Suitable random biregular Tanner graphs give asymptotically good classical LDPC codes. Let d d d be the degree of a bit vertex and d ′ > d d^{\prime} > d d ′ > d the degree of a check vertex, so that m = ( d / d ′ ) n m = (d/d^{\prime})n m = ( d / d ′ ) n . For suitable fixed degrees, the random graph has, with high probability, lossless expansion on a linear range: there are constants α > 0 \alpha> 0 α > 0 and ε < 1 / 2 \varepsilon< 1/2 ε < 1/2 such that
∣ Γ ( S ) ∣ ≥ ( 1 − ε ) d ∣ S ∣ for every S ⊆ [ n ] with ∣ S ∣ ≤ α n . |\Gamma(S)| \ge(1-\varepsilon)d|S| \qquad\text{for every } S \subseteq[n] \text{ with } |S| \le\alpha n. ∣Γ ( S ) ∣ ≥ ( 1 − ε ) d ∣ S ∣ for every S ⊆ [ n ] with ∣ S ∣ ≤ α n .
At least ( 1 − 2 ε ) d ∣ S ∣ (1-2\varepsilon)d|S| ( 1 − 2 ε ) d ∣ S ∣ check vertices then have exactly one neighbor in S S S . Each such check is violated by the error supported on S S S . Consequently,
∣ H e ∣ ≥ γ ∣ e ∣ whenever ∣ e ∣ ≤ α n , γ = ( 1 − 2 ε ) d . (1) |He| \ge\gamma|e| \qquad\text{whenever } |e| \le\alpha n,\qquad\gamma= (1-2\varepsilon)d. \tag*{(1)} ∣ H e ∣ ≥ γ ∣ e ∣ whenever ∣ e ∣ ≤ α n , γ = ( 1 − 2 ε ) d . (1)
In particular, every nonzero codeword has weight greater than α n \alpha n α n .
This also gives small-set local testability. If dist ( y , C ) ≤ α n \operatorname{dist}(y,C) \le\alpha n dist ( y , C ) ≤ α n , choose a nearest codeword c ∈ C c \in C c ∈ C and apply (1) to e = y + c e = y + c e = y + c . Since H e = H y He = Hy H e = H y , we obtain
∣ H y ∣ ≥ γ dist ( y , C ) . |Hy| \ge\gamma\operatorname{dist}(y,C). ∣ H y ∣ ≥ γ dist ( y , C ) .
As m = Θ ( n ) m = \Theta(n) m = Θ ( n ) , a uniformly sampled check rejects y y y with probability at least a constant times its relative distance from C C C , throughout this small-set range.
When d d d is odd, suitable random biregular ensembles also give full-row-rank matrices with high probability; see Appendix A of the preprint of [6 ] . Oddness avoids an immediate dependency: if every column has even weight, the sum of all rows is zero. Thus asymptotically good classical LDPC codes can simultaneously have independent sparse checks and small-set local testability.
Testing over the full range. To obtain an LTC tester from the specified matrix H H H , one requires a constant κ > 0 \kappa> 0 κ > 0 , independent of n n n , such that
∣ H y ∣ ≥ κ dist ( y , C ) for every y ∈ F 2 n . |Hy| \ge\kappa\operatorname{dist}(y,C) \qquad\text{for every } y \in\mathbb{F}_2^n. ∣ H y ∣ ≥ κ dist ( y , C ) for every y ∈ F 2 n .
For asymptotically good codes, such a constant-query tester must use linearly many redundant checks beyond a basis of the dual code, as shown by Ben-Sasson, Guruswami, Kaufman, Sudan, and Viderman [3 ] .
For the full-rank lossless matrices above, the obstruction can be seen directly. Choose the parameters so that γ > 1 \gamma> 1 γ > 1 . Surjectivity of H H H gives a word y y y whose syndrome has weight one. By (1) , every vector with this syndrome has weight greater than α n \alpha n α n . Adding a codeword preserves the syndrome, so
dist ( y , C ) > α n , ∣ H y ∣ = 1. \operatorname{dist}(y,C) > \alpha n, \qquad|Hy| = 1. dist ( y , C ) > α n , ∣ H y ∣ = 1.
Hence the specified checks cannot provide a constant-soundness test over the full range. This obstruction concerns the matrix H H H ; it does not rule out a different tester using redundant checks for the same code.
The quantum problem. We seek the same combination for quantum codes: positive rate, linear distance, small-set soundness on a linear range, and independent sparse checks. A binary CSS code is specified by two matrices
H X ∈ F 2 m X × N , H Z ∈ F 2 m Z × N , H X H Z T = 0. H_X \in\mathbb{F}_2^{m_X \times N}, \qquad H_Z \in\mathbb{F}_2^{m_Z \times N}, \qquad H_X H_Z^{T} = 0. H X ∈ F 2 m X × N , H Z ∈ F 2 m Z × N , H X H Z T = 0.
Their rows specify commuting X X X - and Z Z Z -type checks, respectively, and their columns correspond to qubits. Commutation couples the two matrices, so the classical random construction cannot simply be applied independently to the two types of checks.
There is a further distinction: a nonzero error can be a stabilizer and therefore act trivially on the code. Error size must consequently be measured after reduction modulo stabilizers. For pure X X X - and Z Z Z -errors, represented by x , z ∈ F 2 N x,z \in\mathbb{F}_2^N x , z ∈ F 2 N , define
r X ( x ) = min a ∈ F 2 m X ∣ x + H X T a ∣ , r Z ( z ) = min b ∈ F 2 m Z ∣ z + H Z T b ∣ . (2) r_X(x) = \min_{a \in\mathbb{F}_2^{m_X}} |x + H_X^{T}a|, \qquad r_Z(z) = \min_{b \in\mathbb{F}_2^{m_Z}} |z + H_Z^{T}b|. \tag*{(2)} r X ( x ) = a ∈ F 2 m X min ∣ x + H X T a ∣ , r Z ( z ) = b ∈ F 2 m Z min ∣ z + H Z T b ∣. (2)
We require constants α , γ > 0 \alpha,\gamma> 0 α , γ > 0 such that
∣ H Z x ∣ ≥ γ r X ( x ) whenever r X ( x ) ≤ α N , ∣ H X z ∣ ≥ γ r Z ( z ) whenever r Z ( z ) ≤ α N . (3) \lvert H_Zx\rvert\ge\gamma r_X(x) \qquad\text{whenever } r_X(x) \le\alpha N, \\
\lvert H_Xz\rvert\ge\gamma r_Z(z) \qquad\text{whenever } r_Z(z) \le\alpha N. \tag*{(3)} ∣ H Z x ∣ ≥ γ r X ( x ) whenever r X ( x ) ≤ α N , ∣ H X z ∣ ≥ γ r Z ( z ) whenever r Z ( z ) ≤ α N . (3)
We call these the small-set soundness inequalities , with soundness coefficient γ \gamma γ on the range α N \alpha N α N . They give the small-set quantum local testability guarantee used here. In the physics literature this property is called confinement [6 ] . The reductions in (2) are modulo stabilizers, not modulo the entire syndrome kernels. A nontrivial logical operator has zero syndrome but positive reduced weight, so (3) also implies quantum minimum distance greater than α N \alpha N α N .
The additional requirement is
rank H X = m X , rank H Z = m Z . \operatorname{rank} H_X = m_X,\qquad\operatorname{rank} H_Z = m_Z. rank H X = m X , rank H Z = m Z .
As in the classical case, independence and soundness must hold for the same specified sparse checks. Deleting dependent checks preserves the code and sparsity, but can substantially decrease syndrome weights. Selecting a basis of the check rows therefore does not by itself establish the desired combination.
Previous quantum constructions. The hypergraph-product examples studied by Hong, Guo, and Lucas [6 ] already combine positive constant rate, independent sparse checks, and small-set soundness. Their soundness guarantee, however, holds only up to reduced weight c N c\sqrt{N} c N , for a constant c > 0 c > 0 c > 0 , and their distance is O ( N ) O(\sqrt{N}) O ( N ) . The problem is to achieve linear distance and small-set soundness on a linear range while retaining independence of the specified checks.
Our results. Our first result is a family of explicit lossless expanders with full-rank adjacency matrices. A ( Δ L , Δ R ) (\Delta_L,\Delta_R) ( Δ L , Δ R ) -biregular bipartite graph on L ⊔ R L \sqcup R L ⊔ R is two-sided ( c , ε ) (c,\varepsilon) ( c , ε ) -lossless if every set S S S of at most c ∣ L ∣ c\lvert L\rvert c ∣ L ∣ left vertices has at least ( 1 − ε ) Δ L ∣ S ∣ (1-\varepsilon)\Delta_L\lvert S\rvert ( 1 − ε ) Δ L ∣ S ∣ neighbors, and symmetrically for sets of right vertices.
Theorem 1.1 (Full-rank lossless expanders). For every integer t ≥ 1 t \ge1 t ≥ 1 , every ε > 0 \varepsilon> 0 ε > 0 , and every a min ≥ 1 a_{\min} \ge1 a m i n ≥ 1 , there are a positive integer a ≥ a min a \ge a_{\min} a ≥ a m i n , a constant c > 0 c > 0 c > 0 , and an explicit infinite family of ( a , t a ) (a,ta) ( a , t a ) -biregular bipartite graphs on L ⊔ R L \sqcup R L ⊔ R with ∣ L ∣ = t ∣ R ∣ \lvert L\rvert= t\lvert R\rvert ∣ L ∣ = t ∣ R ∣ , such that:
each graph is two-sided ( c , ε ) (c,\varepsilon) ( c , ε ) -lossless;
its binary adjacency map F 2 L → F 2 R \mathbb{F}_2^L \to\mathbb{F}_2^R F 2 L → F 2 R has full row rank, and is invertible when t = 1 t=1 t = 1 ;
it admits a free action of a finite 2 2 2 -group with a bounded number of orbits.
The neighbors of every vertex can be computed in time polynomial in the logarithm of the number of vertices.
Plugging two such graphs into the Lin–Hsieh balanced product gives quantum LDPC codes with the combination described above. The rate can be made arbitrarily close to one, and the soundness coefficient can be prescribed in advance.
Theorem 1.2 (Independent checks and small-set quantum local testability). Let t 1 , t 2 ≥ 2 t_1, t_2 \ge2 t 1 , t 2 ≥ 2 be integers and let γ 0 > 0 \gamma_0 > 0 γ 0 > 0 . There are constants α > 0 \alpha> 0 α > 0 and w ∈ Z > 0 w \in\mathbb{Z}_{>0} w ∈ Z > 0 , and an explicit infinite family of binary CSS codes with blocklengths N → ∞ N \to\infty N → ∞ , whose specified parity-check matrices H X , H Z H_X, H_Z H X , H Z satisfy the following properties:
H X H Z T = 0 H_X H_Z^{T} = 0 H X H Z T = 0 , both matrices have full row rank, and every row and column of either matrix has weight at most w w w . Each qubit participates in at most 2 w 2w 2 w checks in total.
The number K K K of encoded qubits satisfies
K N = ( t 1 − 1 ) ( t 2 − 1 ) t 1 t 2 + 1 . \frac{K}{N} = \frac{(t_1-1)(t_2-1)}{t_1t_2+1}. N K = t 1 t 2 + 1 ( t 1 − 1 ) ( t 2 − 1 ) . The small-set soundness inequalities (3) hold with γ = γ 0 \gamma= \gamma_0 γ = γ 0 . In particular, the quantum minimum distance is greater than α N \alpha N α N .
Every row and column of H X , H Z H_X, H_Z H X , H Z can be enumerated in time polynomial in log N \log N log N , after finite precomputation depending only on t 1 , t 2 , γ 0 t_1, t_2, \gamma_0 t 1 , t 2 , γ 0 .
Taking t 1 = t 2 = 4 t_1 = t_2 = 4 t 1 = t 2 = 4 gives rate 9 / 17 9/17 9/17 , while taking both integers large makes the rate approach one. The constants α \alpha α and w w w may depend on the chosen rate and soundness coefficient. The theorem establishes small-set quantum local testability on a linear range; it does not assert quantum local testability over the full range.
Techniques
The construction has two rank reductions. First, we reduce independence of the quantum checks to rank conditions on the input graphs of the Lin–Hsieh balanced product. Second, we show that, in a suitable variant of the HLMRZ construction, these conditions reduce to a rank test on a fixed finite gadget. The second reduction requires a free action of a finite 2 2 2 -group. To supply this symmetry together with the required expansion, we construct LPS Ramanujan cubical complexes on a common family of finite 2 2 2 -groups.
Rank inheritance in the Lin–Hsieh construction. Lin and Hsieh use the balanced product to construct a two-dimensional cubical object from two bipartite graphs with a common free group action [1 , 9 ] . Directional losslessness is inherited from the input graphs, and their small-set estimate gives small-set soundness for a suitable choice of parameters (see also [4 ] for a higher-dimensional version). Our observation is that appropriate rank conditions are inherited as well.
Write the two input adjacency maps as
A : F 2 A 0 ⟶ F 2 A 1 , B : F 2 B 0 ⟶ F 2 B 1 . A : \mathbb{F}_2^{A_0} \longrightarrow\mathbb{F}_2^{A_1}, \qquad B : \mathbb{F}_2^{B_0} \longrightarrow\mathbb{F}_2^{B_1}. A : F 2 A 0 ⟶ F 2 A 1 , B : F 2 B 0 ⟶ F 2 B 1 .
Their balanced product has vertex blocks
V i j = ( A i × B j ) / G , i , j ∈ { 0 , 1 } . V_{ij} = (A_i \times B_j)/G, \qquad i,j \in\{0,1\}. V ij = ( A i × B j ) / G , i , j ∈ { 0 , 1 } .
and the three-term complex
F 2 V 2 0 → δ 0 F 2 V 1 0 ⊕ F 2 V 1 1 → δ 1 F 2 V 1 1 . \mathbb{F}_2^{V_2^0} \xrightarrow{\delta_0} \mathbb{F}_2^{V_1^0} \oplus\mathbb{F}_2^{V_1^1} \xrightarrow{\delta_1} \mathbb{F}_2^{V_1^1}. F 2 V 2 0 δ 0 F 2 V 1 0 ⊕ F 2 V 1 1 δ 1 F 2 V 1 1 .
The associated CSS code has check matrices
H X = δ 0 T , H Z = δ 1 . H_X = \delta_0^T,\qquad H_Z = \delta_1. H X = δ 0 T , H Z = δ 1 .
Freeness of the group action makes each directional map a direct sum of copies of the corresponding input map. Consequently, injectivity of A A A implies injectivity of δ 0 \delta_0 δ 0 , and surjectivity of B B B implies surjectivity of δ 1 \delta_1 δ 1 . These are precisely the conditions that make H X H_X H X and H Z H_Z H Z have full row rank. Section 2 gives the argument. The remaining task is therefore to construct two-sided lossless bipartite graphs of suitable opposite imbalances, with full-rank adjacency maps and a common free group action.
Detecting rank on vertex orbits. The construction of Hsieh, Lubotzky, Mohanty, Reiner, and Zhang [HLM+25], which we call HLMRZ, builds two-sided lossless graphs from cubical incidence graphs and a fixed finite gadget. Their construction retains a free group action, but does not supply the rank guarantee needed here. Our modification uses a special feature of finite 2 2 2 -groups acting in characteristic two.
If a finite 2 2 2 -group acts linearly on a nonzero binary vector space, it fixes a nonzero vector. Indeed, the number of nonzero vectors is odd, whereas every orbit has power-of-two size, so at least one orbit must be a singleton. Applying this observation to the kernel of an equivariant adjacency map shows that every nonzero kernel contains a nonzero vector constant on each vertex orbit. Thus injectivity is detected by the restriction to orbit-constant vectors.
We call the matrix of this restriction the orbit matrix . Since the action is free, the orbit matrix of the transpose is the transpose of the orbit matrix. Applying the same kernel argument to the transpose therefore detects surjectivity as well. In our construction, the numbers of vertex orbits are fixed while the graphs grow, so this reduces the rank problem to a matrix of fixed size.
Changing the gadget at one middle type. In the HLMRZ line product, the vertex orbits on each side are indexed by cube signatures. Let H H H be the set of middle types, with h = ∣ H ∣ h = |H| h = ∣ H ∣ even, and let C x C_x C x be the gadget matrix used at middle vertices of type x ∈ H x \in H x ∈ H . Our choice of input complexes ensures that a left cube and a right cube share at most one middle vertex. This distinct-witness property lets us count the edge contributions from the different middle types separately: the orbit matrix of the line product is
∑ x ∈ H C x . \sum_{x \in H} C_x. x ∈ H ∑ C x .
In the unmodified construction, the same gadget C C C is used at every type, so this matrix is h C = 0 hC = 0 h C = 0 . We break this cancellation by changing the gadget at one middle type.
Suppose the left signature set is t t t times as large as the right one, for an integer t ≥ 1 t \ge1 t ≥ 1 . For the noncomplete biregular gadget used here, a matching argument gives a matrix F F F , supported on gadget nonedges, with column weight one and row weight t t t . Its rows have disjoint nonempty supports, so F F F has full row rank. We replace C C C by C + F C+F C + F at every middle vertex of type 0, leaving the other types unchanged. The orbit matrix becomes
and the 2-group rank criterion gives full row rank of the entire adjacency matrix. Reversing the bipartition supplies the injective map needed for the other input.
The modification preserves the group action because it depends only on the middle type. The nonedge support of F F F , together with the distinct-witness property, ensures that all inserted edges are new. If the original line product has degrees ( a 0 , t a 0 ) (a_0,ta_0) ( a 0 , t a 0 ) , the modified degrees are
( a 0 + 1 , t ( a 0 + 1 ) ) . (a_0+1,t(a_0+1)). ( a 0 + 1 , t ( a 0 + 1 )) .
Since edges are only added, every original neighborhood is preserved. Thus the same lossless range remains valid, and an original loss ε 0 \varepsilon_0 ε 0 increases to at most
ε + = ε 0 a 0 + 1 a 0 + 1 = ε 0 + 1 − ε 0 a 0 + 1 . \varepsilon_+ = \frac{\varepsilon_0a_0+1}{a_0+1}=\varepsilon_0+\frac{1-\varepsilon_0}{a_0+1}. ε + = a 0 + 1 ε 0 a 0 + 1 = ε 0 + a 0 + 1 1 − ε 0 .
Section 3 proves the modification and this loss bound.
LPS Ramanujan graphs on 2-groups. The remaining issue is to construct a cubical complex that can serve as the input to the HLMRZ construction and that admits a free action of a finite 2-group with a bounded number of orbits. In the HLMRZ construction the underlying group is P S L 2 ( F q ) \mathrm{PSL}_2(\mathbb{F}_q) PSL 2 ( F q ) . It comes from the graphs in the directions of the complex, which are the LPS Ramanujan graphs [10 ] . Thus, a natural approach is to carry out an analogue of the LPS construction of Ramanujan graphs in which the underlying group is a 2-group. This is the program we carry out in § 4 .
At first glance, constructing bounded-degree expanders from finite p p p -groups might seem to contradict known non-expansion results. In particular, Lubotzky and Weiss [LW93] proved that finite solvable groups of bounded derived length cannot yield bounded-degree expanders. Since finite p p p -groups are nilpotent, and thus solvable, one might suspect that they cannot expand. However, the obstruction of [LW93] applies only when the derived length is uniformly bounded. In our setting the derived length tends to infinity, and expansion is entirely possible. In fact, Lubotzky and Weiss themselves demonstrated this with an infinite family of expanders on finite p p p -groups. We briefly review their example, as it clarifies some steps in our approach.
Let Γ = S L n ( Z ) \Gamma=\mathrm{SL}_n(\mathbb{Z}) Γ = SL n ( Z ) , and let Γ ( N ) \Gamma(N) Γ ( N ) be the principal congruence subgroup of level N N N , namely the kernel of reduction modulo N N N . Fix a prime p p p . For j ≥ 1 j\ge1 j ≥ 1 we have Γ ( p j + 1 ) ⊴ Γ ( p j ) \Gamma(p^{j+1})\trianglelefteq\Gamma(p^j) Γ ( p j + 1 ) ⊴ Γ ( p j ) , and Γ ( p j ) / Γ ( p j + 1 ) \Gamma(p^j)/\Gamma(p^{j+1}) Γ ( p j ) /Γ ( p j + 1 ) is an abelian p p p -group of order p n 2 − 1 p^{n^2-1} p n 2 − 1 . This follows by a direct computation or, more conceptually, from the isomorphism onto the additive group of the Lie algebra
Γ ( p j ) / Γ ( p j + 1 ) ≅ s l n ( F p ) , I + p j X ⟼ X ( m o d p ) . \Gamma(p^j)/\Gamma(p^{j+1})\cong\mathfrak{sl}_n(\mathbb{F}_p),\qquad I+p^jX\longmapsto X\pmod p. Γ ( p j ) /Γ ( p j + 1 ) ≅ sl n ( F p ) , I + p j X ⟼ X ( mod p ) .
Thus Γ ( p ) / Γ ( p m ) \Gamma(p)/\Gamma(p^m) Γ ( p ) /Γ ( p m ) is a finite p p p -group, of order
∣ Γ ( p ) / Γ ( p m ) ∣ = ∏ j = 1 m − 1 ∣ Γ ( p j ) / Γ ( p j + 1 ) ∣ = p ( m − 1 ) ( n 2 − 1 ) . \left|\Gamma(p)/\Gamma(p^m)\right|=\prod_{j=1}^{m-1}\left|\Gamma(p^j)/\Gamma(p^{j+1})\right|=p^{(m-1)(n^2-1)}. ∣ Γ ( p ) /Γ ( p m ) ∣ = j = 1 ∏ m − 1 Γ ( p j ) /Γ ( p j + 1 ) = p ( m − 1 ) ( n 2 − 1 ) .
These quotients form expanders with respect to suitable bounded-size generating sets. For instance, for n ≥ 3 n \ge3 n ≥ 3 this follows from Margulis’ argument [Mar73], since Γ \Gamma Γ has property (T) and Γ ( p ) \Gamma(p) Γ ( p ) is a finite-index subgroup.
Now back to our setting. One can verify by similar reasoning that if Γ \Gamma Γ is an arithmetic subgroup of an algebraic group G G G that is smooth at p p p , then Γ ( p ) / Γ ( p m ) \Gamma(p)/\Gamma(p^{m}) Γ ( p ) /Γ ( p m ) is a p p p -group of order at most p ( m − 1 ) dim G p^{(m-1)\dim G} p ( m − 1 ) d i m G , with equality when Γ \Gamma Γ is dense in G ( Z p ) G(\mathbb{Z}_p) G ( Z p ) .
Thus, to carry out an analogue of the LPS Ramanujan graphs, we recall that their construction uses the group Γ = G ′ ( Z [ 1 / p ] ) \Gamma= G'(\mathbb{Z}[1/p]) Γ = G ′ ( Z [ 1/ p ]) for a prime p ≡ 1 ( m o d 4 ) p \equiv1 \pmod{4} p ≡ 1 ( mod 4 ) , where G ′ = D × / Z ( D × ) G' = D^\times/Z(D^\times) G ′ = D × / Z ( D × ) and D = ( − 1 , − 1 Q ) D = \left(\frac{-1,-1}{\mathbb{Q}}\right) D = ( Q − 1 , − 1 ) is the algebra of Hamilton quaternions over Q \mathbb{Q} Q . The integral structure is given by the Lipschitz quaternions: Γ \Gamma Γ is the group of units of L ( Z [ 1 / p ] ) \mathcal{L}(\mathbb{Z}[1/p]) L ( Z [ 1/ p ]) , namely the quaternions whose norm is a power of p p p , modulo the scalars ± p z \pm p^z ± p z . There are 8 ( p + 1 ) 8(p+1) 8 ( p + 1 ) quaternions in L ( Z ) \mathcal{L}(\mathbb{Z}) L ( Z ) of norm p p p . Each of them has exactly one associate under the units ± 1 , ± i , ± j , ± k \pm1,\pm i,\pm j,\pm k ± 1 , ± i , ± j , ± k with positive odd real part, and these p + 1 p+1 p + 1 representatives are denoted S p S_p S p . They generate the principal congruence subgroup Γ ( 2 ) \Gamma(2) Γ ( 2 ) , which is a free group on ( p + 1 ) / 2 (p+1)/2 ( p + 1 ) /2 generators. This group acts simply transitively on the vertices of the ( p + 1 ) (p+1) ( p + 1 ) -regular tree T p + 1 T_{p+1} T p + 1 , inducing an isomorphism:
T p + 1 ≅ Cay ( Γ ( 2 ) , S p ) . T_{p+1} \cong\operatorname{Cay}(\Gamma(2),S_p). T p + 1 ≅ Cay ( Γ ( 2 ) , S p ) .
In the LPS setting one now takes the quotient modulo an odd prime q ≠ p q \ne p q = p , namely by Γ ( 2 q ) ⊴ Γ ( 2 ) \Gamma(2q) \trianglelefteq\Gamma(2) Γ ( 2 q ) ⊴ Γ ( 2 ) , to obtain a finite Cayley graph on Γ ( 2 ) / Γ ( 2 q ) \Gamma(2)/\Gamma(2q) Γ ( 2 ) /Γ ( 2 q ) . LPS identify this group with PSL 2 ( F q ) \operatorname{PSL}_2(\mathbb{F}_q) PSL 2 ( F q ) or PGL 2 ( F q ) \operatorname{PGL}_2(\mathbb{F}_q) PGL 2 ( F q ) , according to whether p p p is a quadratic residue modulo q q q . The Ramanujan property relies on a deep input, which is Deligne’s proof of the Ramanujan–Petersson conjecture. In the form of [Lub94, Theorem 7.3.1], it gives the Ramanujan bound for Γ ( N ) \ T p + 1 \Gamma(N)\backslash T_{p+1} Γ ( N ) \ T p + 1 at every level N N N prime to p p p .
Our setting requires the groups to be 2-groups, and the discussion above suggests a natural way to achieve this. Since Γ ( 2 m ) ⊴ Γ ( 2 ) \Gamma(2^m) \trianglelefteq\Gamma(2) Γ ( 2 m ) ⊴ Γ ( 2 ) , one can take the LPS generators and reduce them modulo 2 m 2^m 2 m . By the reasoning above, Γ ( 2 ) / Γ ( 2 m ) \Gamma(2)/\Gamma(2^m) Γ ( 2 ) /Γ ( 2 m ) is a 2-group; it embeds in a 2-group of order 2 ( m − 1 ) dim G ′ = 2 3 ( m − 1 ) 2^{(m-1)\dim G'} = 2^{3(m-1)} 2 ( m − 1 ) d i m G ′ = 2 3 ( m − 1 ) . Since 2 m 2^m 2 m is prime to p p p , the LPS machinery gives the Ramanujan bound for the resulting Cayley graphs.
As in the LPS dichotomy between PSL 2 \operatorname{PSL}_2 PSL 2 and PGL 2 \operatorname{PGL}_2 PGL 2 , the quotient depends on whether p p p is a square modulo 2 m 2^m 2 m , which happens exactly when p ≡ 1 ( m o d 8 ) p \equiv1 \pmod{8} p ≡ 1 ( mod 8 ) . For such p p p , strong approximation shows that Γ ( 2 ) / Γ ( 2 m ) \Gamma(2)/\Gamma(2^m) Γ ( 2 ) /Γ ( 2 m ) is an index-two subgroup G m G_m G m of order 2 3 m − 4 2^{3m-4} 2 3 m − 4 , which does not depend on p p p . Hence the LPS graphs of several primes p 1 , … , p ℓ ≡ 1 ( m o d 8 ) p_1,\ldots,p_\ell\equiv1 \pmod{8} p 1 , … , p ℓ ≡ 1 ( mod 8 ) live on the same 2-group G m G_m G m . The cubical structure needed for the HLMRZ construction then follows as in their original construction, from the unique factorization of odd integral quaternions due to Dickson [5 ] .
We point out that, fortunately, the LPS construction is very well adapted to the 2-group setting we need. The LPS generators already lie in Γ ( 2 ) \Gamma(2) Γ ( 2 ) , the top of the tower Γ ( 2 ) ⊇ Γ ( 4 ) ⊇ ⋯ ⊇ Γ ( 2 m ) \Gamma(2) \supseteq\Gamma(4) \supseteq\cdots\supseteq\Gamma(2^m) Γ ( 2 ) ⊇ Γ ( 4 ) ⊇ ⋯ ⊇ Γ ( 2 m ) , so their reductions modulo 2 m 2^m 2 m generate 2-groups. This is not the case for an odd prime q ≠ p q \ne p q = p . The quotients Γ ( 2 ) / Γ ( 2 q m ) \Gamma(2)/\Gamma(2q^m) Γ ( 2 ) /Γ ( 2 q m ) are not q q q -groups, since they map onto Γ ( 2 ) / Γ ( 2 q ) \Gamma(2)/\Gamma(2q) Γ ( 2 ) /Γ ( 2 q ) , which is PSL 2 ( F q ) \operatorname{PSL}_2(\mathbb{F}_q) PSL 2 ( F q ) or PGL 2 ( F q ) \operatorname{PGL}_2(\mathbb{F}_q) PGL 2 ( F q ) , as the case m = 1 m=1 m = 1 above already shows.
Concluding remarks
Our construction supplies asymptotically good quantum LDPC codes with independent sparse checks and small-set soundness on a linear range. Applying the analysis of Hong, Guo, and Lucas [6 ] , within their framework and under their dynamical assumptions, improves the guaranteed memory lifetime from a stretched-exponential timescale to exp ( Ω ( N ) ) \exp(\Omega(N)) exp ( Ω ( N )) at sufficiently low fixed positive temperature. The free-energy density remains analytic at every positive temperature.
The proof reduces independence of the quantum checks to rank conditions on two lossless graphs, and then reduces these conditions to a rank test on a fixed finite gadget. The second reduction relies on the acting group being a finite 2 2 2 -group. The original HLMRZ construction [HLM+25] uses the groups PSL 2 ( F q ) \operatorname{PSL}_2(\mathbb{F}_q) PSL 2 ( F q ) , so our rank-detection criterion does not apply. We wonder whether a different argument can enforce the required rank conditions through a modification of a fixed finite gadget, while retaining the original group family and lossless expansion.
The Lin–Hsieh construction preserves full rank
Lin and Hsieh use the balanced product to build a two-dimensional cubical complex from two bipartite graphs. A key feature of their construction is that directional lossless expansion of the resulting two-dimensional complex is inherited from the lossless expansion of the two input graphs. In this section, we observe that the same inheritance principle holds for rank: suitable full-rank properties of the adjacency matrices of the two input graphs imply the corresponding full-rank properties of the boundary maps, and hence of the parity-check matrices, of the resulting complex. We now give the details.
The balanced product
Let
Γ A = ( A 0 , A 1 , E A ) and Γ B = ( B 0 , B 1 , E B ) \Gamma_A=(A_0,A_1,E_A) \qquad\text{and} \qquad\Gamma_B=(B_0,B_1,E_B) Γ A = ( A 0 , A 1 , E A ) and Γ B = ( B 0 , B 1 , E B )
be two bipartite graphs, and denote their adjacency matrices by A A A and B B B . Suppose that the two graphs admit a common free G G G -action. Their balanced product has four blocks of vertices
V i j = ( A i × B j ) / G , i , j ∈ { 0 , 1 } , V_{ij}=(A_i\times B_j)/G,\qquad i,j\in\{0,1\}, V ij = ( A i × B j ) / G , i , j ∈ { 0 , 1 } ,
where the quotient is with respect to the diagonal G G G -action
( v , w ) ∼ ( g v , g w ) , g ∈ G . (v,w)\sim(gv,gw),\qquad g\in G. ( v , w ) ∼ ( g v , g w ) , g ∈ G .
The edges are quotiented by the same action:
( ( v , w ) , ( v ′ , w ′ ) ) ∼ ( ( g v , g w ) , ( g v ′ , g w ′ ) ) , g ∈ G . ((v,w),(v',w'))\sim((gv,gw),(gv',gw')), \qquad g\in G. (( v , w ) , ( v ′ , w ′ )) ∼ (( g v , g w ) , ( g v ′ , g w ′ )) , g ∈ G .
Denote by
S j : F 2 V 0 j ⟶ F 2 V 1 j , T i : F 2 V i 0 ⟶ F 2 V i 1 S_j:\mathbb{F}_2^{V_{0j}}\longrightarrow\mathbb{F}_2^{V_{1j}},\qquad T_i:\mathbb{F}_2^{V_{i0}}\longrightarrow\mathbb{F}_2^{V_{i1}} S j : F 2 V 0 j ⟶ F 2 V 1 j , T i : F 2 V i 0 ⟶ F 2 V i 1
the two families of directional adjacency maps. They form the diagram
F 2 V 00 → S 0 F 2 V 10 T 0 ↓ ↓ T 1 F 2 V 01 → S 1 F 2 V 11 \begin{CD}
\mathbb{F}_2^{V_{00}} @>S_0>> \mathbb{F}_2^{V_{10}} \\
@V T_0 VV @VV T_1 V \\
\mathbb{F}_2^{V_{01}} @>S_1>> \mathbb{F}_2^{V_{11}}
\end{CD} F 2 V 00 T 0 ↓ ⏐ F 2 V 01 S 0 S 1 F 2 V 10 ↓ ⏐ T 1 F 2 V 11
The following directional-copy property is the basic structural fact that we need.
Lemma 2.1 ([9 Lemma 26] ). The subgraph between V 00 V_{00} V 00 and V 10 V_{10} V 10 defined by S 0 S_0 S 0 is a disjoint union of ∣ B 0 / G ∣ |B_0/G| ∣ B 0 / G ∣ copies of Γ A \Gamma_A Γ A . Equivalently, after suitable orderings of the bases,
S 0 ≅ ⨁ B 0 / G A . S_0 \cong\bigoplus_{B_0/G} A. S 0 ≅ B 0 / G ⨁ A . The analogous statement holds for the other three directional maps: S 1 S_1 S 1 is a direct sum of copies of A A A , while T 0 T_0 T 0 and T 1 T_1 T 1 are direct sums of copies of B B B .
Proof. Fix a G G G -orbit O ⊆ B 0 O \subseteq B_0 O ⊆ B 0 and a representative b ∈ O b \in O b ∈ O . Since the G G G -action on B 0 B_0 B 0 is free, every orbit in ( A i × O ) / G (A_i \times O)/G ( A i × O ) / G has a unique representative of the form [ a , b ] [a,b] [ a , b ] . Thus
a ⟼ [ a , b ] a \longmapsto[a,b] a ⟼ [ a , b ]
identifies the subgraph induced on ( A 0 × O ) / G (A_0 \times O)/G ( A 0 × O ) / G and ( A 1 × O ) / G (A_1 \times O)/G ( A 1 × O ) / G with Γ A \Gamma_A Γ A . Different G G G -orbits in B 0 B_0 B 0 give disjoint components. Hence the graph defined by S 0 S_0 S 0 is the disjoint union of ∣ B 0 / G ∣ |B_0/G| ∣ B 0 / G ∣ copies of Γ A \Gamma_A Γ A , and consequently
S 0 ≅ ⨁ B 0 / G A . S_0 \cong\bigoplus_{B_0/G} A. S 0 ≅ B 0 / G ⨁ A .
The other three statements follow identically by fixing an orbit in the unused coordinate. □
The balanced-product squares imply
T 1 S 0 = S 1 T 0 . T_1S_0 = S_1T_0. T 1 S 0 = S 1 T 0 .
Indeed, taking one step in each of the two graph directions is independent of the order of the two steps. Consequently the balanced product defines the three-term complex
C 0 = F 2 V 00 → δ 0 C 1 = F 2 V 10 ⊕ F 2 V 01 → δ 1 C 2 = F 2 V 11 , (4) C^0 = \mathbb{F}_2^{V_{00}} \xrightarrow{\delta_0} C^1 = \mathbb{F}_2^{V_{10}} \oplus\mathbb{F}_2^{V_{01}} \xrightarrow{\delta_1} C^2 = \mathbb{F}_2^{V_{11}}, \tag*{(4)} C 0 = F 2 V 00 δ 0 C 1 = F 2 V 10 ⊕ F 2 V 01 δ 1 C 2 = F 2 V 11 , (4)
where
δ 0 = ( S 0 T 0 ) , δ 1 = ( T 1 S 1 ) . (5) \delta_0 =
\begin{pmatrix}
S_0\\
T_0
\end{pmatrix},
\qquad
\delta_1 = \begin{pmatrix} T_1 & S_1 \end{pmatrix}. \tag*{(5)} δ 0 = ( S 0 T 0 ) , δ 1 = ( T 1 S 1 ) . (5)
The identity T 1 S 0 = S 1 T 0 T_1S_0 = S_1T_0 T 1 S 0 = S 1 T 0 gives
δ 1 δ 0 = 0 \delta_1\delta_0 = 0 δ 1 δ 0 = 0
over F 2 \mathbb{F}_2 F 2 .
The associated CSS code places the qubits on V 10 ⊔ V 01 V_{10} \sqcup V_{01} V 10 ⊔ V 01 , the X X X -checks on V 00 V_{00} V 00 , and the Z Z Z -checks on V 11 V_{11} V 11 . Its parity-check matrices are
H X = δ 0 T = ( S 0 T T 0 T ) , H Z = δ 1 = ( T 1 S 1 ) . (6) H_X = \delta_0^T = \begin{pmatrix} S_0^T & T_0^T \end{pmatrix},
\qquad
H_Z = \delta_1 = \begin{pmatrix} T_1 & S_1 \end{pmatrix}. \tag*{(6)} H X = δ 0 T = ( S 0 T T 0 T ) , H Z = δ 1 = ( T 1 S 1 ) . (6)
Rank inheritance
We now show that the rank properties of the two input graphs are inherited by the two parity-check matrices of the balanced product. The two ends of the chain complex require opposite rank conditions: independence of the X X X -checks amounts to injectivity of δ 0 \delta_0 δ 0 , whereas independence of the Z Z Z -checks amounts to surjectivity of δ 1 \delta_1 δ 1 . Accordingly, we require the adjacency map of the first input graph to be injective and that of the second to be surjective.
Theorem 2.2 (Rank inheritance). Let
Γ A = ( A 0 , A 1 , E A ) and Γ B = ( B 0 , B 1 , E B ) \Gamma_A=(A_0,A_1,E_A) \qquad\text{and} \qquad\Gamma_B=(B_0,B_1,E_B) Γ A = ( A 0 , A 1 , E A ) and Γ B = ( B 0 , B 1 , E B ) be two bipartite graphs with a common free G G G -action, and let
A : F 2 A 0 ⟶ F 2 A 1 , B : F 2 B 0 ⟶ F 2 B 1 A:\mathbb{F}_2^{A_0}\longrightarrow\mathbb{F}_2^{A_1}, \qquad B:\mathbb{F}_2^{B_0}\longrightarrow\mathbb{F}_2^{B_1} A : F 2 A 0 ⟶ F 2 A 1 , B : F 2 B 0 ⟶ F 2 B 1 be their adjacency maps. If A A A is injective and B B B is surjective, then the two parity-check matrices H X H_X H X and H Z H_Z H Z of the Lin–Hsieh balanced-product code [9 ] have full row rank.
Proof. Suppose first that a ∈ F 2 V 00 a\in\mathbb{F}_2^{V_{00}} a ∈ F 2 V 00 is a dependency among the rows of H X H_X H X . By (6) ,
0 = H X T a = δ 0 a = ( S 0 a T 0 a ) 0=H_X^{T}a=\delta_0a=\begin{pmatrix}S_0a\\T_0a\end{pmatrix} 0 = H X T a = δ 0 a = ( S 0 a T 0 a ) and hence S 0 a = 0 S_0a=0 S 0 a = 0 . By Lemma 2.1, S 0 S_0 S 0 is a direct sum of copies of A A A . Since A A A is injective, so is S 0 S_0 S 0 , and therefore a = 0 a=0 a = 0 . Thus H X H_X H X has full row rank.
Similarly, suppose that b ∈ F 2 V 11 b\in\mathbb{F}_2^{V_{11}} b ∈ F 2 V 11 is a dependency among the rows of H Z H_Z H Z . Then
0 = H Z T b = δ 1 T b = ( T 1 T b S 1 T b ) 0=H_Z^{T}b=\delta_1^{T}b=\begin{pmatrix}T_1^{T}b\\S_1^{T}b\end{pmatrix} 0 = H Z T b = δ 1 T b = ( T 1 T b S 1 T b ) and hence T 1 T b = 0 T_1^{T}b=0 T 1 T b = 0 . By Lemma 2.1, T 1 T_1 T 1 is a direct sum of copies of B B B . Since B B B is surjective, B T B^{T} B T is injective, and therefore T 1 T T_1^{T} T 1 T is injective. Hence b = 0 b=0 b = 0 , and H Z H_Z H Z has full row rank. □ \square □
A full-rank modification of HLMRZ
HLMRZ construct two-sided lossless graphs as line products of two cubical incidence graphs, recalled in § 3.1 . Their graphs admit a free action of the underlying group ([HLM+25, Proposition A.3]). For our constructions, we need the binary adjacency matrix to have full row rank as well. We show that, when the acting group is a finite 2 2 2 -group, this additional requirement can be enforced by adding a sparse complementary factor at one middle type. The modification preserves the vertex sets, the free action, and the lossless range, with a controlled increase in loss. The key is that injectivity and surjectivity of an equivariant binary map can then be detected on a fixed-size matrix indexed by vertex orbits.
Assumption 3.1 (Free 2 2 2 -group action). The acting group G G G is a finite 2 2 2 -group. Its actions on L L L and R R R are free and preserve the two vertex classes. In a family, the numbers of vertex orbits and all local parameters are fixed before ∣ G ∣ |G| ∣ G ∣ grows.
This is an additional algebraic requirement, not an expansion assumption. The groups PSL 2 ( F q ) \operatorname{PSL}_2(\mathbb{F}_q) PSL 2 ( F q ) of the original HLMRZ construction do not satisfy it. The required family will be supplied by the 2 2 2 -groups of § 4 , through Theorem 5.1 . Here we prove the modification theorem assuming this symmetry.
The HLMRZ construction
We recall the definitions from HLMRZ that we need, in the notation of this paper.
Definition 3.2. A ( Δ L , Δ R ) (\Delta_L,\Delta_R) ( Δ L , Δ R ) -biregular bipartite graph on L ⊔ R L \sqcup R L ⊔ R is two-sided ( α , ε ) (\alpha,\varepsilon) ( α , ε ) -lossless if
∣ N ( S ) ∣ ≥ ( 1 − ε ) Δ L ∣ S ∣ ( S ⊆ L , ∣ S ∣ ≤ α ∣ L ∣ ) , |N(S)| \ge(1-\varepsilon)\Delta_L|S| \qquad(S \subseteq L,\ |S| \le\alpha|L|), ∣ N ( S ) ∣ ≥ ( 1 − ε ) Δ L ∣ S ∣ ( S ⊆ L , ∣ S ∣ ≤ α ∣ L ∣ ) , ∣ N ( T ) ∣ ≥ ( 1 − ε ) Δ R ∣ T ∣ ( T ⊆ R , ∣ T ∣ ≤ α ∣ R ∣ ) . |N(T)| \ge(1-\varepsilon)\Delta_R|T| \qquad(T \subseteq R,\ |T| \le\alpha|R|). ∣ N ( T ) ∣ ≥ ( 1 − ε ) Δ R ∣ T ∣ ( T ⊆ R , ∣ T ∣ ≤ α ∣ R ∣ ) .
Cubes and signatures. Let G G G be a finite group. Inverse-closed subsets A 1 , … , A h ⊆ G A_1,\ldots,A_h \subseteq G A 1 , … , A h ⊆ G are cubical generating sets if
A i A j = A j A i ( i ≠ j ) , ∣ A 1 ⋯ A h ∣ = ∏ i = 1 h ∣ A i ∣ . A_iA_j=A_jA_i \quad(i\ne j), \qquad|A_1\cdots A_h|=\prod_{i=1}^{h}|A_i|. A i A j = A j A i ( i = j ) , ∣ A 1 ⋯ A h ∣ = i = 1 ∏ h ∣ A i ∣.
They define the decorated Cayley cubical complex Y = Cay ( G ; A 1 , … , A h ) Y=\operatorname{Cay}(G;A_1,\ldots,A_h) Y = Cay ( G ; A 1 , … , A h ) on the vertex set G × F 2 h G\times\mathbb{F}_2^h G × F 2 h . Its cubes are the collections f = { ( f x , x ) : x ∈ F 2 h } f=\{(f_x,x):x\in\mathbb{F}_2^h\} f = {( f x , x ) : x ∈ F 2 h } with f x − 1 f x + e i ∈ A i f_x^{-1}f_{x+e_i}\in A_i f x − 1 f x + e i ∈ A i for all x ∈ F 2 h x\in\mathbb{F}_2^h x ∈ F 2 h and i ∈ [ h ] i\in[h] i ∈ [ h ] . The signature of f f f is the labeling
( x , i ) ⟼ f x − 1 f x + e i ∈ A i (x,i)\longmapsto f_x^{-1}f_{x+e_i}\in A_i ( x , i ) ⟼ f x − 1 f x + e i ∈ A i
of the directed edges of the cube. Left translation ( g f ) x = g f x (gf)_x=gf_x ( g f ) x = g f x preserves signatures. For a signature σ \sigma σ , put ϕ σ ( x ) = f 0 − 1 f x \phi_\sigma(x)=f_0^{-1}f_x ϕ σ ( x ) = f 0 − 1 f x , where f f f is any cube of signature σ \sigma σ . This is the product of the labels along any path from 0 0 0 to x x x , so it depends only on σ \sigma σ . Thus ϕ σ \phi_\sigma ϕ σ is the unique cube of signature σ \sigma σ with ϕ σ ( 0 ) = 1 \phi_\sigma(0)=1 ϕ σ ( 0 ) = 1 , and every cube of signature σ \sigma σ is g ϕ σ g\phi_\sigma g ϕ σ for a unique g ∈ G g\in G g ∈ G . We write this cube as ( g , σ ) (g,\sigma) ( g , σ ) .
Incidence graphs. Let h h h be a power of two, and let H ⊆ F 2 h H\subseteq\mathbb{F}_2^h H ⊆ F 2 h be the Hadamard code. It consists of h h h vertex types, contains 0 0 0 , and any two distinct types have Hamming distance h / 2 h/2 h /2 . For a nonempty set S S S of signatures, the incidence graph I ( Y , S ) I(Y,S) I ( Y , S ) is the bipartite graph between the cubes G × S G\times S G × S and the middle vertices M = G × H M=G\times H M = G × H , in which a cube is adjacent to its vertices of types in H H H . This is the coded cubical incidence graph of HLMRZ, restricted to the signatures in S S S . Thus the cube ( g , σ ) (g,\sigma) ( g , σ ) is adjacent to ( g ϕ σ ( x ) , x ) (g\phi_\sigma(x),x) ( g ϕ σ ( x ) , x ) for x ∈ H x\in H x ∈ H . A middle vertex u = ( g , x ) u=(g,x) u = ( g , x ) has exactly one neighbor of each signature σ ∈ S \sigma\in S σ ∈ S , namely
Nbr u ( σ ) = ( g ϕ σ ( x ) − 1 , σ ) . (7) \operatorname{Nbr}_u(\sigma)=\left(g\phi_\sigma(x)^{-1},\sigma\right). \tag*{(7)} Nbr u ( σ ) = ( g ϕ σ ( x ) − 1 , σ ) . (7)
Left translation by G G G acts freely on both sides, and Nbr k u ( σ ) = k Nbr u ( σ ) \operatorname{Nbr}_{ku}(\sigma)=k\operatorname{Nbr}_u(\sigma) Nbr k u ( σ ) = k Nbr u ( σ ) for k ∈ G k\in G k ∈ G .
The line product. Let Y L Y_L Y L and Y R Y_R Y R be two such complexes of the same dimension h h h on the same group G G G , and let S L , S R S_L,S_R S L , S R be nonempty sets of signatures of Y L , Y R Y_L,Y_R Y L , Y R , of sizes D L , D R D_L,D_R D L , D R . The incidence graphs I L = I ( Y L , S L ) I_L=I(Y_L,S_L) I L = I ( Y L , S L ) and I R = I ( Y R , S R ) I_R=I(Y_R,S_R) I R = I ( Y R , S R ) have the vertex sets
L = G × S L , R = G × S R , M = G × H . L=G\times S_L,\qquad R=G\times S_R,\qquad M=G\times H. L = G × S L , R = G × S R , M = G × H .
Write LNbr u \operatorname{LNbr}_u LNbr u and RNbr u \operatorname{RNbr}_u RNbr u for their neighbor maps (7) , defined with the normalized cubes ϕ σ L \phi^L_\sigma ϕ σ L and ϕ τ R \phi^R_\tau ϕ τ R . A gadget is a simple ( d L , d R ) (d_L,d_R) ( d L , d R ) -biregular bipartite graph on S L ⊔ S R S_L\sqcup S_R S L ⊔ S R . Let $C\in\mathbb{F}_2^{S_R\times S_L} be its adjacency matrix. The line product Z 0 = Z ( L L , R R ; C ) Z_0 = Z(L_L, R_R; C) Z 0 = Z ( L L , R R ; C ) is the bipartite graph on L ⊔ R L \sqcup R L ⊔ R with an edge
L N b r u u ( σ ) ∼ R N b r u u ( τ ) \mathrm{LNbru}_u(\sigma) \sim\mathrm{RNbru}_u(\tau) LNbru u ( σ ) ∼ RNbru u ( τ )
for every u ∈ M u \in M u ∈ M and every gadget edge ( σ , τ ) (\sigma,\tau) ( σ , τ ) . We call u u u a witness of this edge. Every cube has one middle neighbor of each type, and receives d L d_L d L or d R d_R d R gadget edges at each of them. The neighbor maps are equivariant, so left translation by G G G acts freely on Z 0 Z_0 Z 0 . The line product is a form of the derandomized squaring of Rozenman and Vadhan [RV05]. It keeps only the two-step paths from L L L through M M M to R R R whose two labels form a gadget edge. We will require the distinct-witness condition
∣ N I L ( ℓ ) ∩ N I R ( r ) ∣ ≤ 1 ( ℓ ∈ L , r ∈ R ) . (8) \lvert N_{I_L}(\ell) \cap N_{I_R}(r) \rvert\le1 \qquad(\ell\in L,\ r \in R). \tag*{(8)} ∣ N I L ( ℓ ) ∩ N I R ( r )∣ ≤ 1 ( ℓ ∈ L , r ∈ R ) . (8)
It says that a left cube and a right cube share at most one middle vertex. Under (8) , every edge of Z 0 Z_0 Z 0 has a unique witness. Since the gadget is simple, Z 0 Z_0 Z 0 is then simple and ( h d L , h d R ) (hd_L,hd_R) ( h d L , h d R ) -biregular. HLMRZ do not impose this condition, since their losslessness argument does not need it. We use it to make Z 0 Z_0 Z 0 simple and to compute its orbit matrix (Lemma 3.5 ). The main theorem of HLMRZ shows that suitable line products of this form are lossless.
Theorem 3.3 ([HLM+25, Theorem 2.2]). For every ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) and β ∈ ( 0 , 1 ] \beta\in(0,1] β ∈ ( 0 , 1 ] there are a power of two h h h and an integer d 0 d_0 d 0 such that the following holds for all integers d L , d R ≥ d 0 d_L,d_R \ge d_0 d L , d R ≥ d 0 with β ≤ d L / d R ≤ β + ε \beta\le d_L/d_R \le\beta+\varepsilon β ≤ d L / d R ≤ β + ε . There is c > 0 c > 0 c > 0 such that, for infinitely many primes q q q , there are two cubical complexes of dimension h h h on PSL 2 ( F q ) \operatorname{PSL}_2(\mathbb{F}_q) PSL 2 ( F q ) , signature sets, and a gadget of degrees ( d L , d R ) (d_L,d_R) ( d L , d R ) whose line product Z 0 Z_0 Z 0 is two-sided ( c , ε ) (c,\varepsilon) ( c , ε ) -lossless.
Equivariant maps and rank detection
Let Γ \Gamma Γ be a bipartite graph on L ⊔ R L \sqcup R L ⊔ R on which G G G acts freely, and let A : V → W A: V \to W A : V → W be its adjacency map, where V = F 2 L V = \mathbb{F}_2^L V = F 2 L and W = F 2 R W = \mathbb{F}_2^R W = F 2 R . The action permutes coordinates, and since it preserves edges, A A A is equivariant : A ( g v ) = g A ( v ) A(gv) = gA(v) A ( g v ) = g A ( v ) for g ∈ G g \in G g ∈ G and v ∈ V v \in V v ∈ V . In particular, A A A maps the subspace V G V^G V G of G G G -invariant vectors into W G W^G W G . A vector is invariant exactly when it is constant on each orbit, so V G V^G V G is identified with F 2 L / G \mathbb{F}_2^{L/G} F 2 L / G , and W G W^G W G with F 2 R / G \mathbb{F}_2^{R/G} F 2 R / G .
Let [ A ] : F 2 L / G → F 2 R / G [A]: \mathbb{F}_2^{L/G} \to\mathbb{F}_2^{R/G} [ A ] : F 2 L / G → F 2 R / G be the adjacency map of the quotient graph Γ / G \Gamma/G Γ/ G , whose vertices are the vertex orbits and whose edges are the edge orbits. We call [ A ] [A] [ A ] the orbit matrix of A A A . Since G G G acts freely, Γ → Γ / G \Gamma\to\Gamma/G Γ → Γ/ G is a covering map. Indeed, every edge of Γ / G \Gamma/G Γ/ G at the orbit of a vertex r r r lifts to an edge at r r r , and freeness guarantees that distinct edges at r r r lie in distinct edge orbits. Hence [ A ] [A] [ A ] is identified with the restriction of A A A to V G V^G V G . The same argument applies to the graph read from R R R to L L L , whose quotient has adjacency map [ A T ] = [ A ] T [A^T] = [A]^T [ A T ] = [ A ] T .
Altogether,
[ A ] = A ∣ V G , [ A T ] = [ A ] T = A T ∣ W G . (9) [A] = A|_{V^G}, \qquad[A^T] = [A]^T = A^T|_{W^G}. \tag*{(9)} [ A ] = A ∣ V G , [ A T ] = [ A ] T = A T ∣ W G . (9)
Note that the size of [ A ] [A] [ A ] is fixed in a family satisfying Assumption 3.1, although the dimensions of A A A grow with ∣ G ∣ \lvert G\rvert ∣ G ∣ .
The next lemma shows that injectivity and surjectivity of A A A are equivalent to those properties of [ A ] [A] [ A ] . It is the only place where we use that G G G is a 2-group, through the standard fact that a finite p p p -group acting linearly on a nonzero finite-dimensional vector space over F p \mathbb{F}_p F p fixes a nonzero vector.
Lemma 3.4. Under Assumption 3.1, A A A is injective if and only if [ A ] [A] [ A ] is injective, and A A A is surjective if and only if [ A ] [A] [ A ] is surjective.
Proof. Since ker [ A ] = ( ker A ) G \ker[A]=(\ker A)^G ker [ A ] = ( ker A ) G , if A A A is injective so is [ A ] [A] [ A ] . Conversely, suppose that ker A ≠ 0 \ker A\ne0 ker A = 0 . Then G G G acts on the 2 dim ker A − 1 2^{\dim\ker A}-1 2 d i m k e r A − 1 nonzero vectors of ker A \ker A ker A . Each orbit has power-of-two size and their total is odd, so some orbit has size 1. This gives a nonzero vector in ( ker A ) G = ker [ A ] (\ker A)^G=\ker[A] ( ker A ) G = ker [ A ] . Hence A A A is injective if and only if [ A ] [A] [ A ] is.
For surjectivity, recall that a linear map of finite-dimensional spaces is surjective if and only if its transpose is injective. The map A T A^T A T is the adjacency map of Γ \Gamma Γ read from R R R to L L L , on which G G G still acts freely. So the injectivity part applies to it, and its orbit matrix is [ A ] T [A]^T [ A ] T by (9) . Thus
A is surjective ⟺ A T is injective ⟺ [ A ] T is injective ⟺ [ A ] is surjective . A\text{ is surjective}\Longleftrightarrow A^T\text{ is injective}\Longleftrightarrow[A]^T\text{ is injective}\Longleftrightarrow[A]\text{ is surjective}. A is surjective ⟺ A T is injective ⟺ [ A ] T is injective ⟺ [ A ] is surjective .
The orbit matrix of the line product
Keep the notation of § 3.1 , and assume the distinct-witness condition (8) . We now allow the gadget to depend on the middle type. For each x ∈ H x\in H x ∈ H , choose a binary matrix C x ∈ F 2 S R × S L C_x\in\mathbb{F}_2^{S_R\times S_L} C x ∈ F 2 S R × S L , and use it at every middle vertex of type x x x . Let A C : F 2 L → F 2 R A_C:\mathbb{F}_2^L\to\mathbb{F}_2^R A C : F 2 L → F 2 R be the adjacency map of the resulting line product, where C = ( C x ) x ∈ H C=(C_x)_{x\in H} C = ( C x ) x ∈ H . When all C x C_x C x equal C C C , this is the original line product Z 0 Z_0 Z 0 , and we write A 0 A_0 A 0 for its adjacency map.
Left translation preserves the middle types, and the neighbor maps are equivariant. Hence G G G still acts freely on the line product. Its vertex orbits are the sets G × { σ } G\times\{\sigma\} G × { σ } for σ ∈ S L \sigma\in S_L σ ∈ S L and G × { τ } G\times\{\tau\} G × { τ } for τ ∈ S R \tau\in S_R τ ∈ S R . We index them by the signatures, so that the orbit matrix is a map
[ A C ] : F 2 S L ⟶ F 2 S R . [A_C]:\mathbb{F}_2^{S_L}\longrightarrow\mathbb{F}_2^{S_R}. [ A C ] : F 2 S L ⟶ F 2 S R .
Its size does not depend on ∣ G ∣ |G| ∣ G ∣ . The next lemma computes it.
Lemma 3.5. Under the distinct-witness condition (8) ,
[ A C ] = ∑ x ∈ H C x . [A_C]=\sum_{x\in H} C_x. [ A C ] = x ∈ H ∑ C x . More precisely, the edges witnessed at middle vertices of type x x x have orbit matrix C x C_x C x .
Proof. By § 3.2 , [ A C ] [A_C] [ A C ] is the adjacency map of the quotient graph over F 2 \mathbb{F}_2 F 2 . Thus its ( τ , σ ) (\tau,\sigma) ( τ , σ ) entry is the number of edge orbits between G × { σ } G\times\{\sigma\} G × { σ } and G × { τ } G\times\{\tau\} G × { τ } , modulo 2. We count these orbits.
Every edge of the line product has the form LNbr u ( σ ) ∼ RNbr u ( τ ) \operatorname{LNbr}_u(\sigma)\sim\operatorname{RNbr}_u(\tau) LNbr u ( σ ) ∼ RNbr u ( τ ) , where u u u is a middle vertex of some type x x x and ( σ , τ ) (\sigma,\tau) ( σ , τ ) is an edge of the gadget C x C_x C x . Here σ \sigma σ and τ \tau τ are the signatures of the two endpoints, and u u u is the witness of the edge, which is unique by the distinct-witness condition. Hence the edges correspond one-to-one to the pairs ( u , ( σ , τ ) ) (u,(\sigma,\tau)) ( u , ( σ , τ )) of this form.
By equivariance of the neighbor maps, translation by g ∈ G g\in G g ∈ G maps the edge of ( u , ( σ , τ ) ) (u,(\sigma,\tau)) ( u , ( σ , τ )) to the edge of ( g u , ( σ , τ ) ) (gu,(\sigma,\tau)) ( g u , ( σ , τ )) . Since G G G acts simply transitively on the middle vertices of each type, the edge orbits correspond one-to-one to the pairs consisting of a type x x x and a gadget edge ( σ , τ ) (\sigma,\tau) ( σ , τ ) of C x C_x C x . The orbit of such a pair joins G × { σ } G \times\{\sigma\} G × { σ } to G × { τ } G \times\{\tau\} G × { τ } . Hence the number of edge orbits between these two vertex orbits is the number of types x x x with ( C x ) τ , σ = 1 (C_x)_{\tau,\sigma}=1 ( C x ) τ , σ = 1 . Modulo 2, this number is ∑ x ( C x ) τ , σ \sum_x(C_x)_{\tau,\sigma} ∑ x ( C x ) τ , σ . Counting only the edges witnessed at type x x x gives C x C_x C x .
In particular, when h h h is even and the same gadget is used at every middle type, [ A 0 ] = h C = 0 [A_0]=hC=0 [ A 0 ] = h C = 0 , which is not surjective. By Lemma 3.4 , A 0 A_0 A 0 is not surjective either, so the original line product does not have full row rank.
To obtain full rank, we must therefore break the cancellation among the h h h identical gadget contributions. We will do this by modifying the gadget at a single middle type. The next subsection constructs the small additional gadget that will be used for this modification.
The full-rank modification
By Lemma 3.5 , the orbit matrix of Z 0 Z_0 Z 0 is h C hC h C , which vanishes since h h h is even. We break this cancellation by adding, at the middle vertices of type 0 only, a matrix F ∈ F 2 S R × S L F \in\mathbb{F}_2^{S_R \times S_L} F ∈ F 2 S R × S L supported on the nonedges of the gadget. The orbit matrix then becomes h C + F = F hC+F=F h C + F = F , so full row rank of F F F gives full row rank of the whole adjacency map, by Lemma 3.4 . The support condition ensures that no gadget edge is created twice. To keep the graph biregular, with the smallest possible increase in degree, we ask F F F to have column weight one and row weight t t t , where D L = t D R D_L=tD_R D L = t D R . Its rows then have nonempty, pairwise disjoint supports, so F F F has full row rank automatically. Such a matrix exists whenever the gadget is not complete.
Lemma 3.6. Let C ∈ F 2 S R × S L C \in\mathbb{F}_2^{S_R \times S_L} C ∈ F 2 S R × S L be the adjacency matrix of a simple ( d L , d R ) (d_L,d_R) ( d L , d R ) -biregular gadget, where D L = t D R D_L=tD_R D L = t D R for an integer t ≥ 1 t \ge1 t ≥ 1 and d L < D R d_L<D_R d L < D R . Then there is a matrix F ∈ F 2 S R × S L F \in\mathbb{F}_2^{S_R \times S_L} F ∈ F 2 S R × S L , supported on the zero entries of C C C , with column weight one and row weight t t t . In particular, F F F has full row rank.
Proof. Biregularity gives d R = t d L d_R=td_L d R = t d L . Replace each vertex of S R S_R S R by t t t copies with the same neighbors, and consider the bipartite complement of the gadget. It is biregular, with D L D_L D L vertices on each side and left degree t ( D R − d L ) > 0 t(D_R-d_L)>0 t ( D R − d L ) > 0 , hence regular. A regular bipartite graph of positive degree has a perfect matching. Merging the copies in such a matching gives F F F (Figure 1 ).
Figure 1. The proof of Lemma 3.6 for t = 2 t=2 t = 2 . (a) A gadget with ∣ S L ∣ = 6 |S_L|=6 ∣ S L ∣ = 6 , ∣ S R ∣ = 3 |S_R|=3 ∣ S R ∣ = 3 , and degrees ( 1 , 2 ) (1,2) ( 1 , 2 ) . (b) Each right vertex is replaced by t t t copies (boxed). The dashed lines are the complement of the gadget, and the red edges are a perfect matching in it. (c) Merging the copies gives F F F (red), next to the gadget (gray). Every left vertex has one red edge, and every right vertex has t t t .
Let Z + Z^{+} Z + be the line product with the gadget matrices
C 0 + = C + F , C x + = C ( x ≠ 0 ) , C^{+}_{0}=C+F,\qquad C^{+}_{x}=C\quad(x\ne0), C 0 + = C + F , C x + = C ( x = 0 ) ,
and let A + : F 2 L → F 2 R A^{+}\colon\mathbb{F}_{2}^{L}\to\mathbb{F}_{2}^{R} A + : F 2 L → F 2 R be its adjacency map.
Lemma 3.7 (Full-rank modification of the line product). Assume Assumption 3.1 and the distinct-witness condition (3.2), that h h h is even, and that the gadget and F F F are as in Lemma 3.6 . If Z 0 Z_{0} Z 0 is two-sided ( α , ε 0 ) (\alpha,\varepsilon_{0}) ( α , ε 0 ) -lossless, then:
(i) Z + Z^{+} Z + is simple, G G G -invariant, and has degrees ( h d L + 1 , t ( h d L + 1 ) ) (hd_{L}+1,t(hd_{L}+1)) ( h d L + 1 , t ( h d L + 1 )) .
(ii) A + A^{+} A + has full row rank.
(iii) Z + Z^{+} Z + is two-sided ( α , ε + ) (\alpha,\varepsilon_{+}) ( α , ε + ) -lossless, where
ε + = ε 0 h d L + 1 h d L + 1 = ε 0 + 1 − ε 0 h d L + 1 . \varepsilon_{+}=\frac{\varepsilon_{0}hd_{L}+1}{hd_{L}+1}=\varepsilon_{0}+\frac{1-\varepsilon_{0}}{hd_{L}+1}. ε + = h d L + 1 ε 0 h d L + 1 = ε 0 + h d L + 1 1 − ε 0 .
Proof. For (i), note that 0 ∈ H 0\in H 0 ∈ H and ϕ σ ( 0 ) = 1 \phi_{\sigma}(0)=1 ϕ σ ( 0 ) = 1 . Hence the edges added at type 0 are ( g , σ ) ∼ ( g , τ ) (g,\sigma)\sim(g,\tau) ( g , σ ) ∼ ( g , τ ) for g ∈ G g\in G g ∈ G and F τ , σ = 1 F_{\tau,\sigma}=1 F τ , σ = 1 . They form a G G G -invariant set. Since F F F has column weight one and row weight t t t , every left vertex gains one edge and every right vertex gains t t t . With d R = t d L d_{R}=td_{L} d R = t d L , this gives the stated degrees. An added edge is not a gadget edge at its own witness, since F F F is supported on the nonedges of C C C . By the distinct-witness condition, it is not witnessed anywhere else either. So Z + Z^{+} Z + is simple.
For (ii), Lemma 3.5 gives [ A + ] = h C + F = F [A^{+}]=hC+F=F [ A + ] = h C + F = F . This has full row rank, so A + A^{+} A + is surjective by Lemma 3.4 .
For (iii), Z + Z^{+} Z + is obtained from Z 0 Z_{0} Z 0 by adding edges, so neighborhoods only grow. For S ⊆ L S\subseteq L S ⊆ L with ∣ S ∣ ≤ α ∣ L ∣ |S|\le\alpha|L| ∣ S ∣ ≤ α ∣ L ∣ ,
∣ N Z + ( S ) ∣ ≥ ∣ N Z 0 ( S ) ∣ ≥ ( 1 − ε 0 ) h d L ∣ S ∣ = ( 1 − ε + ) ( h d L + 1 ) ∣ S ∣ . |N_{Z^{+}}(S)|\ge|N_{Z_{0}}(S)|\ge(1-\varepsilon_{0})hd_{L}|S|=(1-\varepsilon_{+})(hd_{L}+1)|S|. ∣ N Z + ( S ) ∣ ≥ ∣ N Z 0 ( S ) ∣ ≥ ( 1 − ε 0 ) h d L ∣ S ∣ = ( 1 − ε + ) ( h d L + 1 ) ∣ S ∣.
The same computation from R R R , with the degrees h d R hd_{R} h d R and h d R + t = t ( h d L + 1 ) hd_{R}+t=t(hd_{L}+1) h d R + t = t ( h d L + 1 ) , gives the bound for T ⊆ R T\subseteq R T ⊆ R .
Thus it remains to construct lossless line products with distinct witnesses whose group satisfies Assumption 3.1. We turn to this in § 4 .
LPS Ramanujan graphs on 2-groups
The full-rank modification of § 3 applies to the HLMRZ line product once its underlying group is a finite 2-group acting freely with a bounded number of orbits (Assumption 3.1). In HLMRZ, the underlying group is PSL 2 ( F q ) \operatorname{PSL}_{2}(\mathbb{F}_{q}) PSL 2 ( F q ) . This group comes from the directional graphs of their cubical complexes, which are the Ramanujan graphs of Lubotzky, Phillips, and Sarnak [10 ] . The rest of their construction uses these graphs only through the Ramanujan bound and through the arithmetic of the integral quaternions that generate them: unique factorization, and injectivity of reduction on quaternions of small norm. Neither depends on the vertex group being PSL 2 ( F q ) \operatorname{PSL}_2(\mathbb{F}_q) PSL 2 ( F q ) . The main task is therefore to construct analogues of the LPS graphs whose vertex groups are 2 2 2 -groups. As explained in § 1.2 , the LPS generators lie in the congruence subgroup of level 2 2 2 , so reducing them modulo 2 m 2^m 2 m , instead of modulo an odd prime q q q , produces 2 2 2 -groups.
The section has two parts. § 4.1 constructs the graphs: for every prime p ≡ 1 ( m o d 4 ) p \equiv1 \pmod{4} p ≡ 1 ( mod 4 ) , the LPS generators of norm p p p , reduced modulo 2 m 2^m 2 m , form a Ramanujan Cayley graph on a 2 2 2 -group (Theorem 4.2 ). For p ≡ 1 ( m o d 8 ) p \equiv1 \pmod{8} p ≡ 1 ( mod 8 ) the graph is non-bipartite, and its vertex group is a group G m G_m G m of order 2 3 m − 4 2^{3m-4} 2 3 m − 4 , the same for all such p p p . For p ≡ 5 ( m o d 8 ) p \equiv5 \pmod{8} p ≡ 5 ( mod 8 ) it is bipartite, on a group G ^ m \widehat{G}_m G m containing G m G_m G m with index two. § 4.2 combines several primes into a cubical complex on G m G_m G m , as HLMRZ do with the original LPS graphs (Theorem 4.6). It also shows that two such complexes with disjoint prime lists satisfy the distinct-witness condition of the line product (Lemma 4.7 ). § 5.1 then feeds these complexes into the HLMRZ construction. The arithmetic inputs, namely the action of the LPS group on the tree and the Ramanujan property of congruence quotients, are used as black boxes, and we collect them in Appendix § 8 .
The graphs
The LPS generators. For a commutative ring R R R , write
L ( R ) = R + R i + R j + R k , i 2 = j 2 = k 2 = i j k = − 1 , \mathcal{L}(R) = R + R i + R j + R k,\qquad i^2 = j^2 = k^2 = i j k = -1, L ( R ) = R + R i + R j + R k , i 2 = j 2 = k 2 = ij k = − 1 ,
and L = L ( Z ) \mathcal{L} = \mathcal{L}(\mathbb{Z}) L = L ( Z ) . For a = a 0 + a 1 i + a 2 j + a 3 k a = a_0+a_1i+a_2j+a_3k a = a 0 + a 1 i + a 2 j + a 3 k , the conjugate and norm are a ‾ = a 0 − a 1 i − a 2 j − a 3 k \overline{a} = a_0-a_1i-a_2j-a_3k a = a 0 − a 1 i − a 2 j − a 3 k and N ( a ) = a a ‾ = a 0 2 + a 1 2 + a 2 2 + a 3 2 N(a) = a\overline{a} = a_0^2+a_1^2+a_2^2+a_3^2 N ( a ) = a a = a 0 2 + a 1 2 + a 2 2 + a 3 2 . Congruences are coefficientwise. For a positive integer n ≡ 1 ( m o d 4 ) n \equiv1 \pmod{4} n ≡ 1 ( mod 4 ) , put
A ( n ) = { a ∈ L : N ( a ) = n , a 0 odd } / { ± 1 } . A(n) = \{a \in\mathcal{L} : N(a) = n,\ a_0\ \text{odd}\}/\{\pm1\}. A ( n ) = { a ∈ L : N ( a ) = n , a 0 odd } / { ± 1 } .
Since squares are 0 or 1 modulo 4, a quaternion of norm n n n has exactly one odd coordinate. Hence every a ∈ A ( n ) a \in A(n) a ∈ A ( n ) has even pure coordinates, that is, a ≡ 1 ( m o d 2 ) a \equiv1 \pmod{2} a ≡ 1 ( mod 2 ) . For a prime p ≡ 1 ( m o d 4 ) p \equiv1 \pmod{4} p ≡ 1 ( mod 4 ) , the set A ( p ) A(p) A ( p ) has p + 1 p+1 p + 1 elements, and their representatives with a 0 > 0 a_0 > 0 a 0 > 0 are the LPS generators (Lemma A.1). LPS reduce them modulo an odd prime q q q , whereas we reduce them modulo 2 m 2^m 2 m .
The groups G m G_m G m . Fix m ≥ 3 m \ge3 m ≥ 3 and put R m = Z / 2 m Z R_m = \mathbb{Z}/2^m\mathbb{Z} R m = Z / 2 m Z . The set U m = 1 + 2 L ( R m ) U_m = 1 + 2\mathcal{L}(R_m) U m = 1 + 2 L ( R m ) of quaternions with odd real part and even pure part is a group: the two-sided ideal 2 L ( R m ) 2\mathcal{L}(R_m) 2 L ( R m ) is nilpotent, so 1 + 2 y 1 + 2y 1 + 2 y is inverted by a finite geometric series. The scalar units R m × R_m^\times R m × form a central subgroup.
Definition 4.1 (The groups G m G_m G m and G ^ m \widehat{G}_m G m ).
G ^ m = U m / R m × , G m = { [ x ] ∈ G ^ m : N ( x ) ≡ 1 ( m o d 8 ) } . \widehat{G}_m = U_m/R_m^\times,\qquad G_m = \{[x] \in\widehat{G}_m : N(x) \equiv1 \pmod{8}\}. G m = U m / R m × , G m = {[ x ] ∈ G m : N ( x ) ≡ 1 ( mod 8 )} . The norm condition is well defined because c 2 ≡ 1 ( m o d 8 ) c^2 \equiv1 \pmod{8} c 2 ≡ 1 ( mod 8 ) for odd c c c , and it defines a subgroup because the norm is multiplicative. Dividing by the real part, every class in G ^ m \widehat{G}_m G m has a unique representative
1 + 2 u , u = u 1 i + u 2 j + u 3 k , u t ∈ Z / 2 m − 1 Z , 1 + 2u,\qquad u = u_1i + u_2j + u_3k,\qquad u_t \in\mathbb{Z}/2^{m-1}\mathbb{Z}, 1 + 2 u , u = u 1 i + u 2 j + u 3 k , u t ∈ Z / 2 m − 1 Z ,
so ∣ G ^ m ∣ = 2 3 ( m − 1 ) |\widehat{G}_m| = 2^{3(m-1)} ∣ G m ∣ = 2 3 ( m − 1 ) . We call these representatives normal forms . Every integer satisfies x 2 ≡ x ( m o d 2 ) x^2 \equiv x \pmod{2} x 2 ≡ x ( mod 2 ) , hence 4 x 2 ≡ 4 x ( m o d 8 ) 4x^2 \equiv4x \pmod{8} 4 x 2 ≡ 4 x ( mod 8 ) , and therefore N ( 1 + 2 u ) ≡ 1 + 4 ( u 1 + u 2 + u 3 ) ( m o d 8 ) N(1+2u) \equiv1+4(u_1+u_2+u_3) \pmod{8} N ( 1 + 2 u ) ≡ 1 + 4 ( u 1 + u 2 + u 3 ) ( mod 8 ) . Thus [ 1 + 2 u ] ∈ G m [1+2u] \in G_m [ 1 + 2 u ] ∈ G m exactly when u 1 + u 2 + u 3 u_1+u_2+u_3 u 1 + u 2 + u 3 is even, which holds for half of the normal forms:
[ G ^ m : G m ] = 2 , ∣ G m ∣ = 2 3 m − 4 . (10) [\widehat{G}_m:G_m]=2,\qquad|G_m|=2^{3m-4}. \tag*{(10)} [ G m : G m ] = 2 , ∣ G m ∣ = 2 3 m − 4 . (10)
In normal forms, the group law is
( 1 + 2 u ) ( 1 + 2 v ) = ( 1 − 4 u ⋅ v ) + 2 ( u + v + 2 u × v ) , (11) (1+2u)(1+2v)=(1-4u\cdot v)+2(u+v+2u\times v), \tag*{(11)} ( 1 + 2 u ) ( 1 + 2 v ) = ( 1 − 4 u ⋅ v ) + 2 ( u + v + 2 u × v ) , (11)
where u ⋅ v u\cdot v u ⋅ v and u × v u\times v u × v are the usual dot and cross products of the coefficient vectors ( u 1 , u 2 , u 3 ) (u_1,u_2,u_3) ( u 1 , u 2 , u 3 ) and ( v 1 , v 2 , v 3 ) (v_1,v_2,v_3) ( v 1 , v 2 , v 3 ) . This follows from the identity u v = − u ⋅ v + u × v uv=-u\cdot v+u\times v uv = − u ⋅ v + u × v for pure quaternions, and dividing by the odd real part gives the normal form of the product. Inverses are [ 1 + 2 u ] − 1 = [ 1 − 2 u ] [1+2u]^{-1}=[1-2u] [ 1 + 2 u ] − 1 = [ 1 − 2 u ] .
Reduction modulo 2 m 2^m 2 m . Let Z 2 \mathbb{Z}_2 Z 2 be the ring of 2-adic integers. Every x ∈ 1 + 2 L ( Z 2 ) x\in1+2\mathcal{L}(\mathbb{Z}_2) x ∈ 1 + 2 L ( Z 2 ) is invertible, with inverse N ( x ) − 1 x ˉ N(x)^{-1}\bar{x} N ( x ) − 1 x ˉ , since N ( x ) ≡ 1 ( m o d 4 ) N(x)\equiv1\pmod{4} N ( x ) ≡ 1 ( mod 4 ) is a unit. Reduction modulo 2 m 2^m 2 m followed by the quotient by scalars is a surjective homomorphism
π m : 1 + 2 L ( Z 2 ) ⟶ G ^ m . \pi_m:1+2\mathcal{L}(\mathbb{Z}_2)\longrightarrow\widehat{G}_m. π m : 1 + 2 L ( Z 2 ) ⟶ G m .
It kills the scalars Z 2 × \mathbb{Z}_2^\times Z 2 × . Hence π m ( a ˉ ) = π m ( a ) − 1 \pi_m(\bar{a})=\pi_m(a)^{-1} π m ( a ˉ ) = π m ( a ) − 1 , as a a ˉ = N ( a ) a\bar{a}=N(a) a a ˉ = N ( a ) is a scalar, and π m ( a ) ∈ G m \pi_m(a)\in G_m π m ( a ) ∈ G m if and only if N ( a ) ≡ 1 ( m o d 8 ) N(a)\equiv1\pmod{8} N ( a ) ≡ 1 ( mod 8 ) . For an odd prime p p p we have Z [ 1 / p ] ⊂ Z 2 \mathbb{Z}[1/p]\subset\mathbb{Z}_2 Z [ 1/ p ] ⊂ Z 2 , so π m \pi_m π m applies to every quaternion over Z [ 1 / p ] \mathbb{Z}[1/p] Z [ 1/ p ] congruent to 1 1 1 modulo 2 2 2 , and in particular to A ( n ) A(n) A ( n ) . Moreover, π m \pi_m π m is continuous for the 2-adic topology on L ( Z 2 ) ≅ Z 2 4 \mathcal{L}(\mathbb{Z}_2)\cong\mathbb{Z}_2^4 L ( Z 2 ) ≅ Z 2 4 and the discrete topology on G ^ m \widehat{G}_m G m , since it is locally constant: π m ( x ) \pi_m(x) π m ( x ) depends only on x x x modulo 2 m 2^m 2 m , so π m \pi_m π m is constant on the open neighborhood x + 2 m L ( Z 2 ) x+2^m\mathcal{L}(\mathbb{Z}_2) x + 2 m L ( Z 2 ) of each x x x . For a prime p ≡ 1 ( m o d 4 ) p\equiv1\pmod{4} p ≡ 1 ( mod 4 ) , put
A p ( m ) = π m ( A ( p ) ) . A_p^{(m)}=\pi_m(A(p)). A p ( m ) = π m ( A ( p )) .
If p ≡ 1 ( m o d 8 ) p\equiv1\pmod{8} p ≡ 1 ( mod 8 ) , then A p ( m ) ⊆ G m A_p^{(m)}\subseteq G_m A p ( m ) ⊆ G m .
The theorem. Recall that a connected k k k -regular graph is Ramanujan if every adjacency eigenvalue λ ≠ ± k \lambda\ne\pm k λ = ± k satisfies ∣ λ ∣ ≤ 2 k − 1 |\lambda|\le2\sqrt{k-1} ∣ λ ∣ ≤ 2 k − 1 . We prove the following theorem:
Theorem 4.2 (LPS Ramanujan graphs on 2-groups). Let p ≡ 1 ( m o d 4 ) p\equiv1\pmod{4} p ≡ 1 ( mod 4 ) be prime and let m ≥ 3 m\ge3 m ≥ 3 satisfy 2 m > 2 p 2^m>2\sqrt{p} 2 m > 2 p . Then A p ( m ) A_p^{(m)} A p ( m ) consists of p + 1 p+1 p + 1 distinct nonidentity elements, and Cay ( ⟨ A p ( m ) ⟩ ; A p ( m ) ) \operatorname{Cay}(\langle A_p^{(m)}\rangle;A_p^{(m)}) Cay (⟨ A p ( m ) ⟩ ; A p ( m ) ) is a simple, connected, ( p + 1 ) (p+1) ( p + 1 ) -regular Ramanujan graph. Moreover:
(i) If p ≡ 1 ( m o d 8 ) p\equiv1\pmod{8} p ≡ 1 ( mod 8 ) , then ⟨ A p ( m ) ⟩ = G m \langle A_p^{(m)}\rangle=G_m ⟨ A p ( m ) ⟩ = G m , the graph is non-bipartite, and its girth is at least 2 3 log p ∣ G m ∣ \frac{2}{3}\log_p|G_m| 3 2 log p ∣ G m ∣ .
(ii) If p ≡ 5 ( m o d 8 ) p\equiv5\pmod{8} p ≡ 5 ( mod 8 ) , then ⟨ A p ( m ) ⟩ = G ^ m \langle A_p^{(m)}\rangle=\widehat{G}_m ⟨ A p ( m ) ⟩ = G m , the graph is bipartite with parts G m G_m G m and G ^ m ∖ G m \widehat{G}_m\setminus G_m G m ∖ G m , and its girth is at least 4 3 log p ∣ G ^ m ∣ \frac{4}{3}\log_p|\widehat{G}_m| 3 4 log p ∣ G m ∣ .
This is the analogue of the LPS theorem [10 ] : the pair G m ⊆ G ^ m G_m\subseteq\widehat{G}_m G m ⊆ G m plays the role of PSL 2 ( F q ) ⊆ PGL 2 ( F q ) \operatorname{PSL}_2(\mathbb{F}_q)\subseteq\operatorname{PGL}_2(\mathbb{F}_q) PSL 2 ( F q ) ⊆ PGL 2 ( F q ) , and the condition p ≡ 1 ( m o d 8 ) p\equiv1\pmod{8} p ≡ 1 ( mod 8 ) replaces the condition that p p p is a square modulo q q q . Indeed, for m ≥ 3 m\ge3 m ≥ 3 an odd integer is a square modulo 2 m 2^m 2 m exactly when it is 1 1 1 modulo 8 8 8 . Odd squares are 1 1 1 modulo $8, and conversely every 2-adic unit that is 1 1 1 modulo 8 8 8 is a 2-adic square [Ser73, Chapter II, §3.3, Theorem 4].
Strategy of the proof. Two ingredients of the LPS construction carry over unchanged to the level 2 m 2^m 2 m , and we use them as black boxes. First, the LPS group is free and acts simply transitively on the ( p + 1 ) (p+1) ( p + 1 ) -regular tree, so every congruence quotient of the tree is a Cayley graph (Theorem A.2 ). Second, every congruence quotient of level prime to p p p is Ramanujan (Theorem A.3 ). This is the deep input, resting on Deligne’s proof of the Ramanujan–Petersson conjecture. What requires a new argument is the identification of the vertex group. At an odd prime q q q the quaternion algebra splits, so reduction modulo q q q takes values in a matrix group over F q \mathbb{F}_q F q , and LPS identify the image with PSL 2 ( F q ) \operatorname{PSL}_2(\mathbb{F}_q) PSL 2 ( F q ) or PGL 2 ( F q ) \operatorname{PGL}_2(\mathbb{F}_q) PGL 2 ( F q ) . At 2 2 2 the algebra is ramified, and no such matrix description is available. We use strong approximation, as in the LPS setting, to pass to a 2 2 2 -adic group, and then compute its image modulo 2 m 2^m 2 m directly (Proposition 4.4 ). Finally, an elementary size argument shows that the p + 1 p+1 p + 1 generators remain distinct and nontrivial after reduction (Lemma 4.3 ).
The following lemma is stated for general n n n , since it is also applied to products of several primes in § 4.2 .
Lemma 4.3 (Non-degeneracy). Let n ≡ 1 ( m o d 4 ) n \equiv1 \pmod{4} n ≡ 1 ( mod 4 ) be a positive integer that is not a square, and let m ≥ 3 m \ge3 m ≥ 3 satisfy 2 m > 2 n 2^m > 2\sqrt{n} 2 m > 2 n . Then π m \pi_m π m is injective on A ( n ) A(n) A ( n ) , and 1 ∉ π m ( A ( n ) ) 1 \notin\pi_m(A(n)) 1 ∈ / π m ( A ( n )) .
Proof. Let a , b ∈ L a,b \in\mathcal{L} a , b ∈ L represent elements of A ( n ) A(n) A ( n ) . Their real parts are odd, hence nonzero, so their pure coordinates are smaller than n < 2 m − 1 \sqrt{n}<2^{m-1} n < 2 m − 1 in absolute value. Suppose that π m ( a ) = π m ( b ) \pi_m(a)=\pi_m(b) π m ( a ) = π m ( b ) , so a ≡ c b ( m o d 2 m ) a \equiv cb \pmod{2^m} a ≡ c b ( mod 2 m ) for an odd integer c c c . Taking norms gives c 2 ≡ 1 ( m o d 2 m ) c^2 \equiv1 \pmod{2^m} c 2 ≡ 1 ( mod 2 m ) , since n n n is odd. One of the consecutive even numbers c − 1 , c + 1 c-1,c+1 c − 1 , c + 1 is 2 2 2 modulo 4 4 4 , so the other is divisible by 2 m − 1 2^{m-1} 2 m − 1 , that is, c ≡ ± 1 ( m o d 2 m − 1 ) c \equiv\pm1 \pmod{2^{m-1}} c ≡ ± 1 ( mod 2 m − 1 ) . Replacing b b b by − b -b − b , we may assume c ≡ 1 ( m o d 2 m − 1 ) c \equiv1 \pmod{2^{m-1}} c ≡ 1 ( mod 2 m − 1 ) , and write c = 1 + 2 m − 1 k c=1+2^{m-1}k c = 1 + 2 m − 1 k . Since the pure coordinates b t b_t b t are even, c b t ≡ b t ( m o d 2 m ) cb_t \equiv b_t \pmod{2^m} c b t ≡ b t ( mod 2 m ) , so a t ≡ c b t ≡ b t ( m o d 2 m ) a_t \equiv cb_t \equiv b_t \pmod{2^m} a t ≡ c b t ≡ b t ( mod 2 m ) for t = 1 , 2 , 3 t=1,2,3 t = 1 , 2 , 3 . As ∣ a t ∣ , ∣ b t ∣ < 2 m − 1 |a_t|,|b_t|<2^{m-1} ∣ a t ∣ , ∣ b t ∣ < 2 m − 1 , this gives a t = b t a_t=b_t a t = b t . Since N ( a ) = N ( b ) N(a)=N(b) N ( a ) = N ( b ) , it follows that a 0 = ± b 0 a_0=\pm b_0 a 0 = ± b 0 . For the real coordinates, a ≡ c b a\equiv cb a ≡ c b gives a 0 ≡ c b 0 ( m o d 2 m ) a_0\equiv cb_0 \pmod{2^m} a 0 ≡ c b 0 ( mod 2 m ) , and c ≡ 1 ( m o d 2 m − 1 ) c\equiv1\pmod{2^{m-1}} c ≡ 1 ( mod 2 m − 1 ) then gives a 0 ≡ b 0 ( m o d 2 m − 1 ) a_0\equiv b_0\pmod{2^{m-1}} a 0 ≡ b 0 ( mod 2 m − 1 ) . If a 0 = − b 0 a_0=-b_0 a 0 = − b 0 , this says 2 b 0 ≡ 0 ( m o d 2 m − 1 ) 2b_0\equiv0\pmod{2^{m-1}} 2 b 0 ≡ 0 ( mod 2 m − 1 ) , so b 0 b_0 b 0 is even since m ≥ 3 m\ge3 m ≥ 3 , a contradiction. Hence a = b a=b a = b .
If π m ( a ) = 1 \pi_m(a)=1 π m ( a ) = 1 , the pure coordinates of a a a are divisible by 2 m 2^m 2 m , so they vanish, and n = a 0 2 n=a_0^2 n = a 0 2 , a contradiction.
:::
The tree quotient. Fix a prime p ≡ 1 ( m o d 4 ) p\equiv1\pmod{4} p ≡ 1 ( mod 4 ) . Let Λ p \Lambda_p Λ p be the subgroup of the projective group L ( Z [ 1 / p ] ) × / Z [ 1 / p ] × \mathcal{L}(\mathbb{Z}[1/p])^\times/\mathbb{Z}[1/p]^\times L ( Z [ 1/ p ] ) × / Z [ 1/ p ] × generated by the classes of A ( p ) A(p) A ( p ) , where Z [ 1 / p ] × = { ± p z : z ∈ Z } \mathbb{Z}[1/p]^\times=\{\pm p^z:z\in\mathbb{Z}\} Z [ 1/ p ] × = { ± p z : z ∈ Z } . By Theorem A.2 , Λ p \Lambda_p Λ p is free on ( p + 1 ) / 2 (p+1)/2 ( p + 1 ) /2 generators, with A ( p ) A(p) A ( p ) as symmetric generating set, and
T p + 1 ≅ Cay ( Λ p ; A ( p ) ) T_{p+1}\cong\operatorname{Cay}(\Lambda_p;A(p)) T p + 1 ≅ Cay ( Λ p ; A ( p ))
is the ( p + 1 ) (p+1) ( p + 1 ) -regular tree. Let Λ p + \Lambda_p^+ Λ p + be the index-two subgroup of words of even length. The representatives of classes in Λ p \Lambda_p Λ p are congruent to 1 1 1 modulo 2 2 2 (Theorem A.2 (i)) and differ by scalars, so π m \pi_m π m induces a homomorphism π m : Λ p → G ^ m \pi_m:\Lambda_p\to\widehat{G}_m π m : Λ p → G m . Its image is ⟨ A p ( m ) ⟩ \langle A_p^{(m)}\rangle ⟨ A p ( m ) ⟩ , and its kernel is the congruence subgroup Γ p ( 2 m ) \Gamma_p(2^m) Γ p ( 2 m ) of ((A.2)). Dividing the tree by this normal subgroup gives, as in ((A.3)),
X p , 2 m : = Γ p ( 2 m ) \ T p + 1 ≅ Cay ( π m ( Λ p ) ; A p ( m ) ) . (12) X^{p,2^m}:=\Gamma_p(2^m)\backslash T_{p+1}\cong\operatorname{Cay}\bigl(\pi_m(\Lambda_p);A_p^{(m)}\bigr). \tag*{(12)} X p , 2 m := Γ p ( 2 m ) \ T p + 1 ≅ Cay ( π m ( Λ p ) ; A p ( m ) ) . (12)
This graph is Ramanujan by Theorem A.3 . It remains to identify the group π m ( Λ p ) \pi_m(\Lambda_p) π m ( Λ p ) .
The vertex group. For a commutative ring R R R , let L 1 ( R ) \mathcal{L}^{1}(R) L 1 ( R ) be the group of norm-one elements of L ( R ) \mathcal{L}(R) L ( R ) , and let L 1 ( R ; 2 ) \mathcal{L}^{1}(R;2) L 1 ( R ; 2 ) be its subgroup of elements congruent to 1 1 1 modulo 2 2 2 .
Proposition 4.4 (Common image). For every prime p ≡ 1 ( m o d 4 ) p \equiv1 \pmod{4} p ≡ 1 ( mod 4 ) and every m ≥ 3 m \ge3 m ≥ 3 ,
π m ( Λ p + ) = G m . \pi_m(\Lambda_p^+) = G_m. π m ( Λ p + ) = G m .
Proof. We prove the three equalities in
π m ( Λ p + ) = π m ( L 1 ( Z [ 1 / p ] ; 2 ) ) = π m ( L 1 ( Z 2 ; 2 ) ) = G m . (13) \pi_m(\Lambda_p^+) = \pi_m\left(\mathcal{L}^{1}(\mathbb{Z}[1/p];2)\right) = \pi_m\left(\mathcal{L}^{1}(\mathbb{Z}_2;2)\right) = G_m. \tag*{(13)} π m ( Λ p + ) = π m ( L 1 ( Z [ 1/ p ] ; 2 ) ) = π m ( L 1 ( Z 2 ; 2 ) ) = G m . (13)
The first passes from Λ p + \Lambda_p^+ Λ p + to norm-one quaternions, the second uses strong approximation to pass to the 2 2 2 -adic group, and the third computes the image of that group directly.
The first equality. A word w w w of length 2 k 2k 2 k in integral representatives of A ( p ) A(p) A ( p ) has norm p 2 k p^{2k} p 2 k , so p − k w ∈ L 1 ( Z [ 1 / p ] ; 2 ) p^{-k}w \in\mathcal{L}^{1}(\mathbb{Z}[1/p];2) p − k w ∈ L 1 ( Z [ 1/ p ] ; 2 ) represents the same class. Conversely, let x ∈ L 1 ( Z [ 1 / p ] ; 2 ) x \in\mathcal{L}^{1}(\mathbb{Z}[1/p];2) x ∈ L 1 ( Z [ 1/ p ] ; 2 ) . By Theorem A.2 (i), [ x ] ∈ Λ p [x] \in\Lambda_p [ x ] ∈ Λ p , so x = ± p z a 1 ⋯ a k x = \pm p^{z}a_1 \cdots a_k x = ± p z a 1 ⋯ a k with integral representatives a i a_i a i of elements of A ( p ) A(p) A ( p ) . Taking norms gives 1 = p 2 z + k 1 = p^{2z+k} 1 = p 2 z + k , so k k k is even and [ x ] ∈ Λ p + [x] \in\Lambda_p^+ [ x ] ∈ Λ p + . Here the parity of the word length is well defined, since Λ p \Lambda_p Λ p is free on A ( p ) A(p) A ( p ) up to inverses (Theorem A.2 (ii)). Since π m \pi_m π m kills scalars, the two images agree.
The second equality. The inclusion ⊆ \subseteq ⊆ is clear. For the reverse inclusion, we use the strong approximation theorem [8 ] , [PR94, Theorem 7.12], in the form given in [11 ] . If G G G is a connected, simply connected, Q \mathbb{Q} Q -simple algebraic group over Q \mathbb{Q} Q and G ( Z [ 1 / p ] ) G(\mathbb{Z}[1/p]) G ( Z [ 1/ p ]) is infinite, then G ( Z [ 1 / p ] ) G(\mathbb{Z}[1/p]) G ( Z [ 1/ p ]) is dense in ∏ ℓ ≠ p G ( Z ℓ ) \prod_{\ell\ne p}G(\mathbb{Z}_{\ell}) ∏ ℓ = p G ( Z ℓ ) . We apply this to the norm-one group G = SL 1 ( D ) G = \operatorname{SL}_1(D) G = SL 1 ( D ) of the Hamilton quaternion algebra D D D , with the integral structure given by the Lipschitz order, so that G ( Z [ 1 / p ] ) = L 1 ( Z [ 1 / p ] ) G(\mathbb{Z}[1/p]) = \mathcal{L}^{1}(\mathbb{Z}[1/p]) G ( Z [ 1/ p ]) = L 1 ( Z [ 1/ p ]) and G ( Z 2 ) = L 1 ( Z 2 ) G(\mathbb{Z}_2) = \mathcal{L}^{1}(\mathbb{Z}_2) G ( Z 2 ) = L 1 ( Z 2 ) . Over an algebraic closure, G G G becomes SL 2 \operatorname{SL}_2 SL 2 , so it is connected, simply connected, and Q \mathbb{Q} Q -simple. The group L 1 ( Z [ 1 / p ] ) \mathcal{L}^{1}(\mathbb{Z}[1/p]) L 1 ( Z [ 1/ p ]) is infinite, since by the proof of the first equality its subgroup L 1 ( Z [ 1 / p ] ; 2 ) \mathcal{L}^{1}(\mathbb{Z}[1/p];2) L 1 ( Z [ 1/ p ] ; 2 ) maps onto the infinite group Λ p + \Lambda_p^+ Λ p + . Projecting to the factor ℓ = 2 \ell= 2 ℓ = 2 , we find that L 1 ( Z [ 1 / p ] ) \mathcal{L}^{1}(\mathbb{Z}[1/p]) L 1 ( Z [ 1/ p ]) is dense in L 1 ( Z 2 ) \mathcal{L}^{1}(\mathbb{Z}_2) L 1 ( Z 2 ) . As L 1 ( Z 2 ; 2 ) \mathcal{L}^{1}(\mathbb{Z}_2;2) L 1 ( Z 2 ; 2 ) is an open subgroup, L 1 ( Z [ 1 / p ] ; 2 ) \mathcal{L}^{1}(\mathbb{Z}[1/p];2) L 1 ( Z [ 1/ p ] ; 2 ) is dense in it. Since π m \pi_m π m is continuous and G m G_m G m is finite, every nonempty fiber of π m \pi_m π m on L 1 ( Z 2 ; 2 ) \mathcal{L}^{1}(\mathbb{Z}_2;2) L 1 ( Z 2 ; 2 ) is open, and hence meets this dense subgroup.
The third equality. Norm-one elements map into G m G_m G m . Conversely, let [ x ] ∈ G m [x] \in G_m [ x ] ∈ G m , and lift x x x to x ~ ∈ 1 + 2 L ( Z 2 ) \widetilde{x} \in1+2\mathcal{L}(\mathbb{Z}_2) x ∈ 1 + 2 L ( Z 2 ) . Then N ( x ~ ) ≡ 1 ( m o d 8 ) N(\widetilde{x}) \equiv1 \pmod{8} N ( x ) ≡ 1 ( mod 8 ) , so N ( x ~ ) = c 2 N(\widetilde{x}) = c^2 N ( x ) = c 2 for some c ∈ Z 2 × c \in\mathbb{Z}_2^{\times} c ∈ Z 2 × [Ser73, Chapter II, §3.3, Theorem 4]. Since c c c is odd, x ~ / c ∈ L 1 ( Z 2 ; 2 ) \widetilde{x}/c \in\mathcal{L}^{1}(\mathbb{Z}_2;2) x / c ∈ L 1 ( Z 2 ; 2 ) , and π m ( x ~ / c ) = π m ( x ~ ) = [ x ] \pi_m(\widetilde{x}/c) = \pi_m(\widetilde{x}) = [x] π m ( x / c ) = π m ( x ) = [ x ] . □
We are now in a position to prove Theorem 4.2 , by combining the above claims with the Ramanujan property of congruence quotients, in the form of Theorem A.3 .
Proof of Theorem 4.2 . By Lemma 4.3 with n = p n = p n = p , the set A p ( m ) A_p^{(m)} A p ( m ) consists of p + 1 p+1 p + 1 distinct nonidentity elements. It is inverse-closed, since π m ( a ‾ ) = π m ( a ) − 1 \pi_m(\overline{a}) = \pi_m(a)^{-1} π m ( a ) = π m ( a ) − 1 . Thus the Cayley graph is simple and ( p + 1 ) (p+1) ( p + 1 ) -regular, and by (12) it is X p , 2 m X^{p,2^m} X p , 2 m .
By Proposition 4.4 , the vertex group π m ( Λ p ) \pi_m(\Lambda_p) π m ( Λ p ) contains G m G_m G m , which has index two in G ^ m \widehat{G}_m G m . If p ≡ 1 ( m o d 8 ) p \equiv1 \pmod{8} p ≡ 1 ( mod 8 ) , the generators lie in G m G_m G m , so π m ( Λ p ) = G m \pi_m(\Lambda_p) = G_m π m ( Λ p ) = G m . If p ≡ 5 ( m o d 8 ) p \equiv5 \pmod{8} p ≡ 5 ( mod 8 ) , they lie in the other coset, so π m ( Λ p ) = G ^ m \pi_m(\Lambda_p) = \widehat{G}_m π m ( Λ p ) = G m and every edge joins the two cosets.
Finally, Theorem A.3 , applied with N = 2 m N = 2^m N = 2 m , shows that X p , 2 m X^{p,2^m} X p , 2 m is Ramanujan. Its two cases depend on whether p p p is a square modulo 2 m 2^m 2 m , which holds exactly when p ≡ 1 ( m o d 8 ) p \equiv1 \pmod{8} p ≡ 1 ( mod 8 ) , as noted after the statement of the theorem. Hence the graph is non-bipartite in case (i) and bipartite in case (ii), and the girth bounds follow from the same theorem, using (10) . □
The cubical complexes
Since the group G m G_m G m does not depend on p p p , the graphs of several primes p ≡ 1 ( m o d 8 ) p \equiv1 \pmod{8} p ≡ 1 ( mod 8 ) live on the same group, and we can combine them into a cubical complex exactly as HLMRZ do [HLM+25, Section 4]. The mechanism is the following. Reduction modulo 2 m 2^m 2 m is injective on the integral quaternions involved, which have bounded norm. Therefore the multiplicative structure that unique factorization gives the integral generators survives in G m G_m G m : the generating sets of different primes commute, and their ordered products are all distinct. Consequently, the operator of a mixed direction factors into one-direction operators, and the Ramanujan bounds multiply. Compared with HLMRZ, the same integral generators are reduced modulo 2 m 2^m 2 m instead of an odd prime q q q , and the separation condition (14) below replaces their condition q > 2 ∏ i p i q > 2\sqrt{\prod_i p_i} q > 2 ∏ i p i . Their quadratic-residue condition becomes p ≡ 1 ( m o d 8 ) p \equiv1 \pmod{8} p ≡ 1 ( mod 8 ) . Once the primes are fixed, increasing m m m gives an infinite family.
Let A 1 , … , A ℓ A_1,\ldots,A_\ell A 1 , … , A ℓ be cubical generating sets of a finite group G G G (Section 3.1). For ∅ ≠ I ⊆ [ ℓ ] \varnothing\ne I \subseteq[\ell] ∅ = I ⊆ [ ℓ ] , write A I = ∏ i ∈ I A i A_I = \prod_{i\in I} A_i A I = ∏ i ∈ I A i and d I = ∏ i ∈ I ∣ A i ∣ d_I = \prod_{i\in I} |A_i| d I = ∏ i ∈ I ∣ A i ∣ , and let 1 I ∈ F 2 ℓ \mathbf{1}_I \in\mathbb{F}_2^\ell 1 I ∈ F 2 ℓ be the indicator vector of I I I . Since the A i A_i A i commute, A I A_I A I does not depend on the order of the factors. The bipartite graph between types y y y and y + 1 I y+\mathbf{1}_I y + 1 I has edges
( g , y ) ∼ ( g a , y + 1 I ) , a ∈ A I . (g,y) \sim(ga,y+\mathbf{1}_I), \qquad a \in A_I. ( g , y ) ∼ ( g a , y + 1 I ) , a ∈ A I .
The complex is α \alpha α -expanding if, for every nonempty I I I and every y y y , the second largest eigenvalue of the adjacency matrix of this graph is at most α d I \alpha\sqrt{d_I} α d I . Let ( T I f ) ( g ) = ∑ a ∈ A I f ( g a ) (T_I f)(g) = \sum_{a\in A_I} f(ga) ( T I f ) ( g ) = ∑ a ∈ A I f ( g a ) on ℓ 2 ( G ) \ell^2(G) ℓ 2 ( G ) . The adjacency eigenvalues of this bipartite graph are ± \pm ± the singular values of T I T_I T I . So the complex is α \alpha α -expanding exactly when, for every nonempty I I I , the operator T I T_I T I has norm at most α d I \alpha\sqrt{d_I} α d I on the orthogonal complement 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ of the constant functions.
From now on, let ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 , let p 1 , … , p ℓ p_1,\ldots,p_\ell p 1 , … , p ℓ be distinct primes with p i ≡ 1 ( m o d 8 ) p_i \equiv1 \pmod{8} p i ≡ 1 ( mod 8 ) , and let m ≥ 3 m \ge3 m ≥ 3 satisfy
2 m > 2 p 1 p 2 ⋯ p ℓ . (14) 2^m > 2\sqrt{p_1p_2\cdots p_\ell}. \tag*{(14)} 2 m > 2 p 1 p 2 ⋯ p ℓ . (14)
The next lemma transfers the unique factorization of integral quaternions to G m G_m G m . For I ⊆ [ ℓ ] I \subseteq[\ell] I ⊆ [ ℓ ] , put
n I = ∏ i ∈ I p i , A I ( m ) = ∏ i ∈ I A p i ( m ) . n_I = \prod_{i\in I} p_i, \qquad A_I^{(m)} = \prod_{i\in I} A_{p_i}^{(m)}. n I = i ∈ I ∏ p i , A I ( m ) = i ∈ I ∏ A p i ( m ) .
Lemma 4.5. For every nonempty I ⊆ [ ℓ ] I \subseteq[\ell] I ⊆ [ ℓ ] and every ordering of I I I , multiplication followed by reduction is a bijection
∏ i ∈ I A ( p i ) → ∼ A I ( m ) = π m ( A ( n I ) ) . \prod_{i\in I} A(p_i) \xrightarrow{\sim} A_I^{(m)} = \pi_m\bigl(A(n_I)\bigr). i ∈ I ∏ A ( p i ) ∼ A I ( m ) = π m ( A ( n I ) ) . In particular, A I ( m ) A_I^{(m)} A I ( m ) does not depend on the ordering, and ∣ A I ( m ) ∣ = ∏ i ∈ I ( p i + 1 ) |A_I^{(m)}| = \prod_{i\in I}(p_i+1) ∣ A I ( m ) ∣ = ∏ i ∈ I ( p i + 1 ) .
Proof. For every ordering, multiplication is a bijection from ∏ i ∈ I A ( p i ) \prod_{i\in I} A(p_i) ∏ i ∈ I A ( p i ) onto A ( n I ) A(n_I) A ( n I ) , by unique factorization of integral quaternions (Lemma A.1). The integer n I > 1 n_I > 1 n I > 1 is squarefree, hence not a square, and (14) gives 2 m > 2 n I 2^m > 2\sqrt{n_I} 2 m > 2 n I . By Lemma 4.3 , π m \pi_m π m is injective on A ( n I ) A(n_I) A ( n I ) .
We prove the following theorem.
Theorem 4.6 (Ramanujan cubical complexes on 2-groups). Assume (14) . Then the sets A p 1 ( m ) , … , A p ℓ ( m ) A_{p_1}^{(m)},\ldots,A_{p_\ell}^{(m)} A p 1 ( m ) , … , A p ℓ ( m ) are cubical generating sets of G m G_m G m , with ∣ A p i ( m ) ∣ = p i + 1 \lvert A_{p_i}^{(m)}\rvert=p_i+1 ∣ A p i ( m ) ∣ = p i + 1 , and the decorated cubical complex
Y m = Cay ( G m ; A p 1 ( m ) , … , A p ℓ ( m ) ) Y_m=\operatorname{Cay}(G_m;A_{p_1}^{(m)},\ldots,A_{p_\ell}^{(m)}) Y m = Cay ( G m ; A p 1 ( m ) , … , A p ℓ ( m ) ) is 2 ℓ 2^\ell 2 ℓ -expanding.
Proof. We follow the argument of HLMRZ. By (14) , 2 m > 2 p i 2^m>2\sqrt{p_i} 2 m > 2 p i for every i i i . So by Theorem 4.2, each A p i ( m ) A_{p_i}^{(m)} A p i ( m ) is inverse-closed, lies in G m G_m G m , and has p i + 1 p_i+1 p i + 1 elements. By Lemma 4.5,
A p i ( m ) A p j ( m ) = π m ( A ( p i p j ) ) = A p j ( m ) A p i ( m ) ( i ≠ j ) , A_{p_i}^{(m)}A_{p_j}^{(m)}=\pi_m\left(A(p_ip_j)\right)=A_{p_j}^{(m)}A_{p_i}^{(m)}\qquad(i\ne j), A p i ( m ) A p j ( m ) = π m ( A ( p i p j ) ) = A p j ( m ) A p i ( m ) ( i = j ) ,
and ∣ A p 1 ( m ) ⋯ A p ℓ ( m ) ∣ = ∏ i ( p i + 1 ) = ∏ i ∣ A p i ( m ) ∣ \lvert A_{p_1}^{(m)}\cdots A_{p_\ell}^{(m)}\rvert=\prod_i(p_i+1)=\prod_i\lvert A_{p_i}^{(m)}\rvert ∣ A p 1 ( m ) ⋯ A p ℓ ( m ) ∣ = ∏ i ( p i + 1 ) = ∏ i ∣ A p i ( m ) ∣ . Thus these are cubical generating sets.
For expansion, fix one of the primes p = p i p=p_i p = p i , and let T p , m T_{p,m} T p , m be the adjacency operator of Cay ( G m ; A p i ( m ) ) \operatorname{Cay}(G_m;A_{p_i}^{(m)}) Cay ( G m ; A p i ( m ) ) . It is self-adjoint, since A p i ( m ) A_{p_i}^{(m)} A p i ( m ) is inverse-closed. The graph is connected, non-bipartite, and Ramanujan (Theorem 4.2(i)). Hence ± ( p + 1 ) \pm(p+1) ± ( p + 1 ) are not eigenvalues of T p , m T_{p,m} T p , m on 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ , and all its eigenvalues there have absolute value at most 2 p 2\sqrt{p} 2 p . Now let I = { i 1 < ⋯ < i k } I=\{i_1<\cdots<i_k\} I = { i 1 < ⋯ < i k } be nonempty. By Lemma 4.5, every element of A I ( m ) A_I^{(m)} A I ( m ) is a product a 1 ⋯ a k a_1\cdots a_k a 1 ⋯ a k with a j ∈ A p i j ( m ) a_j\in A_{p_{i_j}}^{(m)} a j ∈ A p i j ( m ) in exactly one way. Hence T I = T p i 1 , m ⋯ T p i k , m T_I=T_{p_{i_1},m}\cdots T_{p_{i_k},m} T I = T p i 1 , m ⋯ T p i k , m . Every factor preserves 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ , so
∥ T I ∣ 1 ⊥ ∥ ≤ ∏ i ∈ I 2 p i ≤ 2 ∣ I ∣ d I ≤ 2 ℓ d I . \left\|T_I\big|_{\mathbf{1}^{\perp}}\right\|\leq\prod_{i\in I}2\sqrt{p_i}\leq2^{\lvert I\rvert}\sqrt{d_I}\leq2^\ell\sqrt{d_I}. T I 1 ⊥ ≤ i ∈ I ∏ 2 p i ≤ 2 ∣ I ∣ d I ≤ 2 ℓ d I .
The tripartite line product uses two such complexes on the same group (§ 3.1 ). Let P L P^L P L and P R P^R P R be disjoint lists of h h h primes congruent to 1 modulo 8, and let m m m satisfy (14) for the union of the 2 h 2h 2 h primes. Theorem 4.6 gives two 2 h 2^h 2 h -expanding complexes Y L , Y R Y_L,Y_R Y L , Y R on G m G_m G m , with the common vertex set G m × F 2 h G_m\times\mathbb{F}_2^h G m × F 2 h . A superscript ∙ ∈ { L , R } \bullet\in\{L,R\} ∙ ∈ { L , R } distinguishes their products of generating sets A I ( m ) , ∙ A_I^{(m),\bullet} A I ( m ) , ∙ .
Lemma 4.7. In this setting, a cube of Y L Y_L Y L and a cube of Y R Y_R Y R share at most one vertex. In particular, the distinct-witness condition (8) holds for all signature sets.
Proof. Suppose that a cube f f f of Y L Y_L Y L and a cube f ′ f' f ′ of Y R Y_R Y R share two vertices. A cube has exactly one vertex of each type, so these are ( f x , x ) = ( f x ′ , x ) (f_x,x)=(f'_x,x) ( f x , x ) = ( f x ′ , x ) and ( f y , y ) = ( f y ′ , y ) (f_y,y)=(f'_y,y) ( f y , y ) = ( f y ′ , y ) for two distinct types x , y x,y x , y . The element f x − 1 f y f_x^{-1}f_y f x − 1 f y is the product of the edge labels of f f f along a path from x x x to $y that changes each coordinate in I = supp ( x + y ) I=\operatorname{supp}(x+y) I = supp ( x + y ) once, so it lies in A I ( m ) , L A_I^{(m),L} A I ( m ) , L . In the same way, f y ′ − 1 f x ′ f_y'^{-1}f_x' f y ′ − 1 f x ′ lies in A I ( m ) , R A_I^{(m),R} A I ( m ) , R . Hence A I ( m ) , L ∩ A I ( m ) , R A_I^{(m),L}\cap A_I^{(m),R} A I ( m ) , L ∩ A I ( m ) , R is nonempty. By Lemma 4.5, there are a ∈ A ( n ) a\in A^{(n)} a ∈ A ( n ) and b ∈ A ( n ′ ) b\in A^{(n')} b ∈ A ( n ′ ) with π m ( a ) = π m ( b ) \pi_m(a)=\pi_m(b) π m ( a ) = π m ( b ) , where n , n ′ > 1 n,n'>1 n , n ′ > 1 are coprime squarefree products of left and right primes, respectively. Then π m ( a b ˉ ) = π m ( a ) π m ( b ) − 1 = 1 \pi_m(a\bar b)=\pi_m(a)\pi_m(b)^{-1}=1 π m ( a b ˉ ) = π m ( a ) π m ( b ) − 1 = 1 , and a b ˉ a\bar b a b ˉ represents an element of A ( n n ′ ) A^{(nn')} A ( n n ′ ) . But $nn'i s n o t a s q u a r e , a n d $ 2 m > 2 n n ′ is not a square, and \$2^m>2\sqrt{nn'} i s n o t a s q u a r e , an d $ 2 m > 2 n n ′ by the separation condition for the union. This contradicts Lemma 4.3.
Full-rank lossless graphs and the quantum code construction
We now complete the construction. First we feed the cubical complexes of § 4 into the HLMRZ construction (Theorem 5.1). The modification of Lemma 3.7 then gives full-rank lossless graphs with a free action of G m G_m G m , which proves Theorem 1.1 . Finally, we plug two such graphs into the Lin–Hsieh balanced product and prove Theorem 1.2 . All ranks in this section are over F 2 \mathbb{F}_2 F 2 .
Lossless graphs with a free 2-group action
HLMRZ prove their main theorem (Theorem 3.3) from two ingredients. The first is a pair of structured base graphs, namely incidence graphs I L , I R I_L, I_R I L , I R as in § 3.1 with three combinatorial properties ([HLM+25, Lemma 2.8]). The second is a random gadget with local expansion and spreading properties ([HLM+25, Lemma 2.9]). The argument of [HLM+25, Section 2.2] uses the base graphs only through these three properties. Their proof in [HLM+25, Sections 3.1 and 3.2] uses the two cubical complexes only through the conclusions of the HLMRZ theorem on Ramanujan cubical complexes over PSL 2 ( F q ) \operatorname{PSL}_2(\mathbb{F}_q) PSL 2 ( F q ) ([HLM+25, Theorem 3.5]). Namely, the two complexes live on the same group, their generating sets are cubical of sizes p i + 1 p_i+1 p i + 1 for primes p i p_i p i in an interval [ x , 2 x ] [x,2x] [ x , 2 x ] , and both complexes are 2 h 2^h 2 h -expanding. Theorem 4.6 gives the same conclusions on G m G_m G m , for primes congruent to 1 modulo 8. The construction therefore applies verbatim, with PSL 2 ( F q ) \operatorname{PSL}_2(\mathbb{F}_q) PSL 2 ( F q ) replaced by G m G_m G m and the condition q > 2 ∏ i p i q > 2\sqrt{\prod_i p_i} q > 2 ∏ i p i replaced by (14) .
Theorem 5.1 (Lossless line products with a free 2-group action). Let t ≥ 1 t \ge1 t ≥ 1 be an integer and let ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . There is d 0 d_0 d 0 such that for every integer d ≥ d 0 d \ge d_0 d ≥ d 0 there are a power of two h ≥ 2 h \ge2 h ≥ 2 , two disjoint lists P L , P R P^L, P^R P L , P R of h h h primes congruent to 1 modulo 8, an integer D R > d D_R > d D R > d , a constant c > 0 c > 0 c > 0 , and an integer m 0 m_0 m 0 with the following property. For m ≥ m 0 m \ge m_0 m ≥ m 0 , let Y L , Y R Y_L,Y_R Y L , Y R be the complexes of Theorem 4.6 on G m G_m G m for P L P^L P L and P R P^R P R . There are signature sets S L , S R S_L,S_R S L , S R with ∣ S L ∣ = t D R |S_L| = tD_R ∣ S L ∣ = t D R and ∣ S R ∣ = D R |S_R| = D_R ∣ S R ∣ = D R , and a gadget C C C of degrees ( d , t d ) (d,td) ( d , t d ) , such that Z 0 = Z ( I ( Y L , S L ) , I ( Y R , S R ) ; C ) Z_0 = Z(I(Y_L,S_L), I(Y_R,S_R); C) Z 0 = Z ( I ( Y L , S L ) , I ( Y R , S R ) ; C ) satisfies the following:
(i) Z 0 Z_0 Z 0 is simple, ( h d , h t d ) (hd,htd) ( h d , h t d ) -biregular, and two-sided ( c , ε ) (c,\varepsilon) ( c , ε ) -lossless.
(ii) Z 0 Z_0 Z 0 satisfies the distinct-witness condition (8) .
(iii) Left translation is a free action of the 2-group G m G_m G m , with ∣ S L ∣ |S_L| ∣ S L ∣ , ∣ S R ∣ |S_R| ∣ S R ∣ , and h h h orbits on L L L , R R R , and M M M .
(iv) The sets S L S_L S L , S R S_R S R , the gadget C C C , and the neighbors of a vertex of Z 0 Z_0 Z 0 are computable in time polynomial in m m m .
Proof. For (i), we run the proof of the HLMRZ main theorem ([HLM+25, Theorem 2.2], stated as Theorem 3.3) verbatim on the complexes of Theorem 4.6 , with ratio β = 1 / t \beta= 1/t β = 1/ t and degrees ( d , t d ) (d,td) ( d , t d ) . Primes congruent to 1 modulo 8 in [ x , 2 x ] [x,2x] [ x , 2 x ] exist for every large x x x [2 ] , and m 0 m_0 m 0 is the least m ≥ 3 m \ge3 m ≥ 3 satisfying (14) for the union of P L P^L P L and P R P^R P R . The proof takes D L = t D R D_L = tD_R D L = t D R , and its degrees satisfy t d ≤ D 3 / 8 td \le D^{3/8} t d ≤ D 3/8 with D = ( t + 1 ) D R D = (t+1)D_R D = ( t + 1 ) D R , so D R > d D_R > d D R > d for large d d d . The density c c c depends only on the degrees and the loss. Simplicity and (ii) follow from Lemma 4.7 , and (iii) holds since G m G_m G m is a 2-group acting freely by left translation, with orbits indexed by S L S_L S L , S R S_R S R , and H H H .
For (iv), the signatures are the square-consistent labelings of the cube by the generating sets. Finding them, the normalized cubes ϕ σ \phi_\sigma ϕ σ , and the choices of S L S_L S L , S R S_R S R , and C C C is a finite search whose size depends only on the primes and the degrees. Each step is a fixed number of operations in G m G_m G m , each polynomial in m m m by (11) . The neighbors of ( g , σ ) (g,\sigma) ( g , σ ) are ( g φ σ L ( x ) φ τ R ( x ) − 1 , τ ) (g\varphi_{\sigma}^{L}(x)\varphi_{\tau}^{R}(x)^{-1},\tau) ( g φ σ L ( x ) φ τ R ( x ) − 1 , τ ) for x ∈ H x \in H x ∈ H and gadget edges ( σ , τ ) (\sigma,\tau) ( σ , τ ) , and the right neighbors are similar.
Full-rank lossless expanders
Theorem 5.2 (Full-rank lossless expanders, precise form of Theorem 1.1 ). For every integer t ≥ 1 t \ge1 t ≥ 1 , every ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , and every positive integer a min a_{\min} a m i n , there are positive integers u , a u,a u , a , a constant c > 0 c > 0 c > 0 , and an integer m 0 m_0 m 0 , with a ≥ a min a \ge a_{\min} a ≥ a m i n , such that for every m ≥ m 0 m \ge m_0 m ≥ m 0 there is a simple bipartite graph
Z m = ( G m × [ t u ] , G m × [ u ] , E m ) Z_m = (G_m \times[tu], G_m \times[u], E_m) Z m = ( G m × [ t u ] , G m × [ u ] , E m ) with degrees ( a , t a ) (a,ta) ( a , t a ) , two-sided ( c , ε ) (c,\varepsilon) ( c , ε ) -losslessness, and a full-row-rank binary adjacency map
F 2 G m × [ t u ] ⟶ F 2 G m × [ u ] . \mathbb{F}_2^{G_m \times[tu]} \longrightarrow\mathbb{F}_2^{G_m \times[u]}. F 2 G m × [ t u ] ⟶ F 2 G m × [ u ] . Left translation is a free G m G_m G m -action. Neighbors on either side can be enumerated in time polynomial in m = O ( log ∣ G m ∣ ) m = O(\log|G_m|) m = O ( log ∣ G m ∣ ) .
Proof. Apply Theorem 5.1 with t t t , loss ε / 2 \varepsilon/2 ε /2 , and an integer d d d with d ≥ d 0 d \ge d_0 d ≥ d 0 , d ≥ a min d \ge a_{\min} d ≥ a m i n , and d ≥ 2 / ε d \ge2/\varepsilon d ≥ 2/ ε . It gives a power of two h ≥ 2 h \ge2 h ≥ 2 , an integer D R > d D_R > d D R > d , a constant c > 0 c > 0 c > 0 , and an integer m 0 m_0 m 0 . Put u = D R u = D_R u = D R and a = h d + 1 a = hd + 1 a = h d + 1 .
Let m ≥ m 0 m \ge m_0 m ≥ m 0 , and let S L , S R S_L,S_R S L , S R and C C C be as in Theorem 5.1 . Identify S L S_L S L with [ t u ] [tu] [ t u ] and S R S_R S R with [ u ] [u] [ u ] . By Theorem 5.1 , the line product Z 0 Z_0 Z 0 is simple and two-sided ( c , ε / 2 ) (c,\varepsilon/2) ( c , ε /2 ) -lossless, satisfies the distinct-witness condition (8) , and satisfies Assumption 3.1. Since h h h is even and the gadget is simple with ∣ S L ∣ = t ∣ S R ∣ |S_L| = t|S_R| ∣ S L ∣ = t ∣ S R ∣ and d < ∣ S R ∣ d < |S_R| d < ∣ S R ∣ , the hypotheses of Lemma 3.7 hold. Let Z m Z_m Z m be the modified graph Z + Z^+ Z + . By that lemma, Z m Z_m Z m is simple with degrees ( h d + 1 , t ( h d + 1 ) ) = ( a , t a ) (hd + 1,t(hd + 1)) = (a,ta) ( h d + 1 , t ( h d + 1 )) = ( a , t a ) , its adjacency map has full row rank, and left translation by G m G_m G m acts freely. It is two-sided lossless with the same density c c c and with loss
ε + = ε 2 + 1 − ε / 2 a ≤ ε 2 + 1 a ≤ ε , \varepsilon_+ = \frac{\varepsilon}{2} + \frac{1-\varepsilon/2}{a} \le\frac{\varepsilon}{2} + \frac{1}{a} \le\varepsilon, ε + = 2 ε + a 1 − ε /2 ≤ 2 ε + a 1 ≤ ε ,
since a > d ≥ 2 / ε a > d \ge2/\varepsilon a > d ≥ 2/ ε . Moreover a > d ≥ a min a > d \ge a_{\min} a > d ≥ a m i n .
Neighbors in Z 0 Z_0 Z 0 are computable in time polynomial in m m m by Theorem 5.1 (iv). By the proof of Lemma 3.7 , the added edges are ( g , σ ) ∼ ( g , τ ) (g,\sigma) \sim(g,\tau) ( g , σ ) ∼ ( g , τ ) with F τ , σ = 1 F_{\tau,\sigma} = 1 F τ , σ = 1 . The matrix F F F of Lemma 3.6 is found from C C C by a finite matching computation, whose size depends only on u u u , t t t , and d d d .
Theorem 1.1 follows. The graphs Z m Z_m Z m have ( t + 1 ) u ∣ G m ∣ (t+1)u|G_m| ( t + 1 ) u ∣ G m ∣ vertices and ( t + 1 ) u (t+1)u ( t + 1 ) u orbits under the free action of G m G_m G m , so m = O ( log ∣ G m ∣ ) m = O(\log|G_m|) m = O ( log ∣ G m ∣ ) is logarithmic in the number of vertices.
The quantum codes
Lin and Hsieh construct good quantum LDPC codes from two-sided lossless expanders with a free group action, assuming such expanders exist ([9 ] , Conjecture 10 and Theorem 9). Theorem 5.2 provides them, with full rank in addition. We prove Theorem 1.2 by running their construction with these graphs. Full rank of the input graphs gives independent checks by Theorem 2.2, and the small-set estimate of Lin and Hsieh gives small-set soundness.
The small-set estimate. Let Γ A = ( A 0 , A 1 , E A ) \Gamma_A=(A_0,A_1,E_A) Γ A = ( A 0 , A 1 , E A ) and Γ B = ( B 0 , B 1 , E B ) \Gamma_B=(B_0,B_1,E_B) Γ B = ( B 0 , B 1 , E B ) be two-sided ( c 1 , ε 1 ) (c_1,\varepsilon_1) ( c 1 , ε 1 ) - and ( c 2 , ε 2 ) (c_2,\varepsilon_2) ( c 2 , ε 2 ) -lossless bipartite graphs with a common free G G G -action. Let Γ A \Gamma_A Γ A have degrees D 1 D_1 D 1 on A 0 A_0 A 0 and D 1 ′ D'_1 D 1 ′ on A 1 A_1 A 1 , and let Γ B \Gamma_B Γ B have degrees D 2 D_2 D 2 on B 0 B_0 B 0 and D 2 ′ D'_2 D 2 ′ on B 1 B_1 B 1 . In the code of § 2 , the qubits are V 10 ⊔ V 01 V_{10}\sqcup V_{01} V 10 ⊔ V 01 . For y = ( y 10 , y 01 ) ∈ F 2 V 10 ⊕ F 2 V 01 y=(y_{10},y_{01})\in\mathbb{F}_2^{V_{10}}\oplus\mathbb{F}_2^{V_{01}} y = ( y 10 , y 01 ) ∈ F 2 V 10 ⊕ F 2 V 01 , put
∣ y ∣ w = ∣ y 10 ∣ D 1 + ∣ y 01 ∣ D 2 , |y|_w=\frac{|y_{10}|}{D_1}+\frac{|y_{01}|}{D_2}, ∣ y ∣ w = D 1 ∣ y 10 ∣ + D 2 ∣ y 01 ∣ ,
and call y y y locally minimal if adding a row of H X H_X H X to y y y does not decrease ∣ y ∣ w |y|_w ∣ y ∣ w . Suppose that ε 1 ≤ ε \varepsilon_1\leq\varepsilon ε 1 ≤ ε , ε 1 D 1 ≤ D 1 ′ \varepsilon_1D_1\leq D'_1 ε 1 D 1 ≤ D 1 ′ , and ε 2 D 1 ≤ ε \varepsilon_2D_1\leq\varepsilon ε 2 D 1 ≤ ε . Then every locally minimal y y y with ∣ y 10 ∣ , ∣ y 01 ∣ < κ ∣ G ∣ |y_{10}|,|y_{01}|<\kappa|G| ∣ y 10 ∣ , ∣ y 01 ∣ < κ ∣ G ∣ satisfies
∣ H Z y ∣ ≥ ( 1 2 − 6 ε ) D 1 D 2 ∣ y ∣ w , (15) |H_Zy|\geq\left(\frac{1}{2}-6\varepsilon\right)D_1D_2|y|_w, \tag*{(15)} ∣ H Z y ∣ ≥ ( 2 1 − 6 ε ) D 1 D 2 ∣ y ∣ w , (15)
where κ > 0 \kappa>0 κ > 0 depends only on the degrees, the densities c 1 , c 2 c_1,c_2 c 1 , c 2 , and the orbit counts [9 Lemma 12] . Reversing both bipartitions exchanges H X H_X H X with H Z H_Z H Z and D i D_i D i with D i ′ D'_i D i ′ .
Proof of Theorem 1.2 . Put ε = 1 / 24 \varepsilon=1/24 ε = 1/24 and a min = ⌈ 4 γ 0 ⌉ a_{\min}=\lceil4\gamma_0\rceil a m i n = ⌈ 4 γ 0 ⌉ .
The two graphs. As in the proof of [9 Theorem 11] , we choose the graphs in order, since the loss of the second graph must be small compared with the degrees of the first. Apply Theorem 5.2 with t 1 t_1 t 1 , loss ε 1 = ε / t 1 \varepsilon_1=\varepsilon/t_1 ε 1 = ε / t 1 , and a min a_{\min} a m i n . It gives u 1 u_1 u 1 , a density c 1 c_1 c 1 , and a graph of degrees ( a , t 1 a ) (a,t_1a) ( a , t 1 a ) with a ≥ a min a\geq a_{\min} a ≥ a m i n . Reversing its bipartition gives a graph Γ A \Gamma_A Γ A with
A 0 = G m × [ u 1 ] , A 1 = G m × [ t 1 u 1 ] , ( D 1 , D 1 ′ ) = ( t 1 a , a ) . A_0=G_m\times[u_1],\qquad A_1=G_m\times[t_1u_1],\qquad(D_1,D'_1)=(t_1a,a). A 0 = G m × [ u 1 ] , A 1 = G m × [ t 1 u 1 ] , ( D 1 , D 1 ′ ) = ( t 1 a , a ) .
Its adjacency map is injective, being the transpose of a full-row-rank map. Now apply Theorem 5.2 with t 2 t_2 t 2 , loss ε 2 = ε / ( t 1 a ) \varepsilon_2=\varepsilon/(t_1a) ε 2 = ε / ( t 1 a ) , and a min a_{\min} a m i n . It gives u 2 u_2 u 2 , a density c 2 c_2 c 2 , and a graph Γ B \Gamma_B Γ B with
B 0 = G m × [ t 2 u 2 ] , B 1 = G m × [ u 2 ] , ( D 2 , D 2 ′ ) = ( b , t 2 b ) , B_0=G_m\times[t_2u_2],\qquad B_1=G_m\times[u_2],\qquad(D_2,D'_2)=(b,t_2b), B 0 = G m × [ t 2 u 2 ] , B 1 = G m × [ u 2 ] , ( D 2 , D 2 ′ ) = ( b , t 2 b ) ,
where b ≥ a min b\geq a_{\min} b ≥ a m i n . Its adjacency map is surjective. For every m m m above both thresholds m 0 m_0 m 0 , the group G m G_m G m acts freely on both graphs. Since max { D 1 , D 1 ′ } = t 1 a \max\{D_1,D'_1\}=t_1a max { D 1 , D 1 ′ } = t 1 a , with ε 1 t 1 a = ε a \varepsilon_1t_1a=\varepsilon a ε 1 t 1 a = ε a and ε 2 t 1 a = ε \varepsilon_2t_1a=\varepsilon ε 2 t 1 a = ε , the hypotheses of (5.1) hold in both orientations.
Rank and rate. We have H X H Z T = ( δ 1 δ 0 ) T = 0 H_XH_Z^T=(\delta_1\delta_0)^T=0 H X H Z T = ( δ 1 δ 0 ) T = 0 , and both check matrices have full row rank by Theorem 2.2 . Freeness gives ∣ V i j ∣ = ∣ A i ∣ ∣ B j ∣ / ∣ G m ∣ |V_{ij}|=|A_i||B_j|/|G_m| ∣ V ij ∣ = ∣ A i ∣∣ B j ∣/∣ G m ∣ . With M = u 1 u 2 ∣ G m ∣ M=u_1u_2|G_m| M = u 1 u 2 ∣ G m ∣ , the blocks V 00 , V 10 , V 01 , V 11 V_{00},V_{10},V_{01},V_{11} V 00 , V 10 , V 01 , V 11 have sizes
t 2 M , t 1 t 2 M , M , t 1 M . t_2M,\qquad t_1t_2M,\qquad M,\qquad t_1M. t 2 M , t 1 t 2 M , M , t 1 M .
The qubits are V 10 ⊔ V 01 V_{10}\sqcup V_{01} V 10 ⊔ V 01 , and the ranks of H X , H Z H_X,H_Z H X , H Z are ∣ V 00 ∣ , ∣ V 11 ∣ |V_{00}|,|V_{11}| ∣ V 00 ∣ , ∣ V 11 ∣ . Hence
N = ( t 1 t 2 + 1 ) M , K = N − t 2 M − t 1 M = ( t 1 − 1 ) ( t 2 − 1 ) M . N=(t_1t_2+1)M,\qquad K=N-t_2M-t_1M=(t_1-1)(t_2-1)M. N = ( t 1 t 2 + 1 ) M , K = N − t 2 M − t 1 M = ( t 1 − 1 ) ( t 2 − 1 ) M .
Small-set soundness and distance. Let x x x be an X X X -error, and let y y y minimize ∣ ⋅ ∣ w \lvert\cdot\rvert_w ∣ ⋅ ∣ w over x + im H X T x+\operatorname{im} H_X^T x + im H X T . Then y y y is locally minimal. Put d = min { D 1 , D 2 } d=\min\{D_1,D_2\} d = min { D 1 , D 2 } and D = max { D 1 , D 2 } D=\max\{D_1,D_2\} D = max { D 1 , D 2 } . The coset contains an element x ′ x' x ′ with ∣ x ′ ∣ = r X ( x ) \lvert x'\rvert=r_X(x) ∣ x ′ ∣ = r X ( x ) , so minimality gives ∣ y ∣ w ≤ ∣ x ′ ∣ w ≤ ∣ x ′ ∣ / d = r X ( x ) / d \lvert y\rvert_w\leq\lvert x'\rvert_w\leq\lvert x'\rvert/d=r_X(x)/d ∣ y ∣ w ≤ ∣ x ′ ∣ w ≤ ∣ x ′ ∣ / d = r X ( x ) / d , and hence ∣ y 10 ∣ , ∣ y 01 ∣ ≤ D ∣ y ∣ w ≤ ( D / d ) r X ( x ) \lvert y_{10}\rvert,\lvert y_{01}\rvert\leq D\lvert y\rvert_w\leq(D/d)r_X(x) ∣ y 10 ∣ , ∣ y 01 ∣ ≤ D ∣ y ∣ w ≤ ( D / d ) r X ( x ) . Recall that N = ( t 1 t 2 + 1 ) u 1 u 2 ∣ G m ∣ N=(t_1t_2+1)u_1u_2\lvert G_m\rvert N = ( t 1 t 2 + 1 ) u 1 u 2 ∣ G m ∣ . Choose α > 0 \alpha>0 α > 0 below κ d / ( D ( t 1 t 2 + 1 ) u 1 u 2 ) \kappa d/(D(t_1t_2+1)u_1u_2) κ d / ( D ( t 1 t 2 + 1 ) u 1 u 2 ) and below the analogous bound for the reversed bipartitions. Neither bound depends on m m m . If r X ( x ) ≤ α N r_X(x)\leq\alpha N r X ( x ) ≤ α N , then ∣ y 10 ∣ , ∣ y 01 ∣ ≤ ( D / d ) α N < κ ∣ G m ∣ \lvert y_{10}\rvert,\lvert y_{01}\rvert\leq(D/d)\alpha N<\kappa\lvert G_m\rvert ∣ y 10 ∣ , ∣ y 01 ∣ ≤ ( D / d ) α N < κ ∣ G m ∣ , so (15) applies to y y y and
∣ H Z x ∣ = ∣ H Z y ∣ ≥ 1 4 D 1 D 2 ∣ y ∣ w = 1 4 ( D 2 ∣ y 10 ∣ + D 1 ∣ y 01 ∣ ) ≥ d 4 ∣ y ∣ ≥ d 4 r X ( x ) . \lvert H_Zx\rvert=\lvert H_Zy\rvert\geq\frac{1}{4}D_1D_2\lvert y\rvert_w=\frac{1}{4}\left(D_2\lvert y_{10}\rvert+D_1\lvert y_{01}\rvert\right)\geq\frac{d}{4}\lvert y\rvert\geq\frac{d}{4}r_X(x). ∣ H Z x ∣ = ∣ H Z y ∣ ≥ 4 1 D 1 D 2 ∣ y ∣ w = 4 1 ( D 2 ∣ y 10 ∣ + D 1 ∣ y 01 ∣ ) ≥ 4 d ∣ y ∣ ≥ 4 d r X ( x ) .
Since D 1 = t 1 a D_1=t_1a D 1 = t 1 a , D 2 = b D_2=b D 2 = b , and a , b ≥ a min a,b\geq a_{\min} a , b ≥ a m i n , we have d ≥ a min ≥ 4 γ 0 d\geq a_{\min}\geq4\gamma_0 d ≥ a m i n ≥ 4 γ 0 , so ∣ H Z x ∣ ≥ γ 0 r X ( x ) \lvert H_Zx\rvert\geq\gamma_0r_X(x) ∣ H Z x ∣ ≥ γ 0 r X ( x ) . Reversing both bipartitions gives ∣ H X z ∣ ≥ γ 0 r Z ( z ) \lvert H_Xz\rvert\geq\gamma_0r_Z(z) ∣ H X z ∣ ≥ γ 0 r Z ( z ) in the same way, since also min { D 1 ′ , D 2 ′ } ≥ a min \min\{D'_1,D'_2\}\geq a_{\min} min { D 1 ′ , D 2 ′ } ≥ a m i n . This proves small-set soundness with soundness coefficient γ 0 \gamma_0 γ 0 . A nontrivial logical operator has a nontrivial X X X - or Z Z Z -part, say x x x , with H Z x = 0 H_Zx=0 H Z x = 0 and r X ( x ) > 0 r_X(x)>0 r X ( x ) > 0 . The inequality forces r X ( x ) > α N r_X(x)>\alpha N r X ( x ) > α N , so the quantum minimum distance is greater than α N \alpha N α N .
Sparsity and explicitness. As in [9 proof of Theorem 9] , the X X X - and Z Z Z -checks have weights D 1 + D 2 D_1+D_2 D 1 + D 2 and D 1 ′ + D 2 ′ D'_1+D'_2 D 1 ′ + D 2 ′ , and the qubits in V 10 V_{10} V 10 and V 01 V_{01} V 01 lie in D 1 ′ + D 2 D'_1+D_2 D 1 ′ + D 2 and D 1 + D 2 ′ D_1+D'_2 D 1 + D 2 ′ checks. All of these are at most w = t 1 a + t 2 b w=t_1a+t_2b w = t 1 a + t 2 b .
All orbit counts, degrees, and primes are fixed before m m m grows. A vertex of the balanced product has coordinates
[ ( g , i ) , ( h , j ) ] ⟷ ( i , g − 1 h , j ) , [(g,i),(h,j)]\longleftrightarrow(i,g^{-1}h,j), [( g , i ) , ( h , j )] ⟷ ( i , g − 1 h , j ) ,
so its neighbors are enumerated using the neighbor algorithms of the two graphs and a fixed number of group operations in G m G_m G m . This takes time polynomial in m = O ( log N ) m=O(\log N) m = O ( log N ) , for both rows and columns of H X H_X H X and H Z H_Z H Z .
Acknowledgments
We are grateful to the Israeli Interdisciplinary Center for the Theory of Quantum Computing, at whose conference we first learned of this problem. We also want to thank Dorit Aharonov, Alex Lubotzky, Shai Evra and Nadav Drechsler for many interesting conversations.
AI methodology
We used ChatGPT (OpenAI) and Claude (Anthropic) extensively in this work. ChatGPT assisted with the development of the main ideas and proofs. This includes the strategy of using free actions of finite 2-groups to reduce the rank conditions to a problem on a fixed finite gadget, and help with the rank arguments and the full-rank gadget modification, and parts of the arithmetic construction. Both tools were used to examine proofs for gaps, to derive soundness estimates and parameter choices, for exploratory computations, and to draft and revise the manuscript. Claude was used in particular to check and simplify proofs and to restructure the presentation. The authors verified the correctness and originality of all content, including references.
Arithmetic background
This appendix collects the standard arithmetic inputs used in § 4 . They concern the integral LPS generator sets, the action of the LPS group on the Bruhat–Tits tree, and the Ramanujan property of congruence quotients.
Integral quaternions and the product structure
We use the notation of § 4.1 . Let D = L ( Q ) D = \mathcal{L}(\mathbb{Q}) D = L ( Q ) be the Hamilton quaternion algebra over Q \mathbb{Q} Q , with the Lipschitz order L = L ( Z ) \mathcal{L} = \mathcal{L}(\mathbb{Z}) L = L ( Z ) . The algebra is definite at the real place, ramified at 2 2 2 , and split at every odd prime. Since every a ∈ A ( n ) a \in A(n) a ∈ A ( n ) satisfies a ≡ 1 ( m o d 2 ) a \equiv1 \pmod{2} a ≡ 1 ( mod 2 ) , products of elements of the sets A ( n ) A(n) A ( n ) again have odd real part. Each A ( n ) A(n) A ( n ) is closed under conjugation. For a prime p ≡ 1 ( m o d 4 ) p \equiv1 \pmod{4} p ≡ 1 ( mod 4 ) , the representatives with a 0 > 0 a_0 > 0 a 0 > 0 give the usual LPS generator list [Lub94, Section 2.1].
Lemma A.1 ([HLM+25, Lemma 4.8]). Let the primes p 1 , … , p k p_1,\ldots,p_k p 1 , … , p k be distinct and congruent to 1 1 1 modulo 4 4 4 , and put n = p 1 ⋯ p k n = p_1 \cdots p_k n = p 1 ⋯ p k . Then
∣ A ( n ) ∣ = ∏ i = 1 k ( p i + 1 ) , |A(n)| = \prod_{i=1}^{k}(p_i + 1), ∣ A ( n ) ∣ = i = 1 ∏ k ( p i + 1 ) , and, for every prescribed ordering, multiplication induces a bijection
A ( p 1 ) × ⋯ × A ( p k ) ⟶ ∼ A ( n ) . (16) A(p_1) \times\cdots\times A(p_k) \overset{\sim}{\longrightarrow} A(n). \tag*{(16)} A ( p 1 ) × ⋯ × A ( p k ) ⟶ ∼ A ( n ) . (16) In particular, ∣ A ( p ) ∣ = p + 1 |A(p)| = p + 1 ∣ A ( p ) ∣ = p + 1 and A ( p i ) A ( p j ) = A ( p i p j ) = A ( p j ) A ( p i ) A(p_i)A(p_j) = A(p_ip_j) = A(p_j)A(p_i) A ( p i ) A ( p j ) = A ( p i p j ) = A ( p j ) A ( p i ) for i ≠ j i \ne j i = j .
Proof. We recall the argument. Its factorization input is Dickson’s factorization theorem for odd quaternions [5 Theorem 8] .
Counting. For odd squarefree n n n , Jacobi’s four-square formula gives
∣ { a ∈ L : N ( a ) = n } ∣ = 8 ∑ d ∣ n d = 8 ∏ i = 1 k ( p i + 1 ) . \left|\{a \in\mathcal{L}: N(a)=n\}\right| = 8\sum_{d\mid n}d = 8\prod_{i=1}^{k}(p_i+1). ∣ { a ∈ L : N ( a ) = n } ∣ = 8 d ∣ n ∑ d = 8 i = 1 ∏ k ( p i + 1 ) .
Coordinate permutations show that exactly one quarter of these solutions have their unique odd coordinate in the real position. Quotienting that set by the fixed-point-free involution a ↦ − a a \mapsto-a a ↦ − a divides its size by two. This proves the displayed formula for ∣ A ( n ) ∣ |A(n)| ∣ A ( n ) ∣ .
Factorization and normalization. Let γ ∈ L \gamma\in\mathcal{L} γ ∈ L represent an element of A ( n ) A(n) A ( n ) . Since n n n is squarefree, γ \gamma γ is primitive. For a fixed ordering of p 1 , … , p k p_1,\ldots,p_k p 1 , … , p k , the cited factorization theorem gives
γ = α 1 ⋯ α k , N ( α i ) = p i , \gamma=\alpha_1\cdots\alpha_k,\qquad N(\alpha_i)=p_i, γ = α 1 ⋯ α k , N ( α i ) = p i ,
uniquely up to unit migration. The units are { ± 1 , ± i , ± j , ± k } \{\pm1,\pm\mathbf{i},\pm\mathbf{j},\pm\mathbf{k}\} { ± 1 , ± i , ± j , ± k } , and the migration has the form
α i ⟼ u i − 1 − 1 α i u i , u 0 = u k = 1. \alpha_i \longmapsto u_{i-1}^{-1}\alpha_i u_i,\qquad u_0=u_k=1. α i ⟼ u i − 1 − 1 α i u i , u 0 = u k = 1.
Right multiplication by i , j , k \mathbf{i},\mathbf{j},\mathbf{k} i , j , k moves the unique odd coordinate to the other three positions. Choose u 1 , … , u k − 1 u_1,\ldots,u_{k-1} u 1 , … , u k − 1 successively so that the first k − 1 k-1 k − 1 factors have odd real part. Each choice is unique up to sign. Those factors are all congruent to 1 1 1 modulo 2 2 2 , and so is γ \gamma γ . Therefore the last factor is also congruent to 1 1 1 modulo 2 2 2 . This gives a factorization by elements of the prescribed A ( p i ) A(p_i) A ( p i ) , unique modulo the signs already quotiented out. It proves (A.1). □ \square □
The LPS group and the tree
Fix a prime p ≡ 1 ( m o d 4 ) p \equiv1 \pmod4 p ≡ 1 ( mod 4 ) . For a commutative ring R R R , write
G ′ ( R ) = L ( R ) × / R × G'(R)=\mathcal{L}(R)^\times/R^\times G ′ ( R ) = L ( R ) × / R ×
for the group of units of L ( R ) \mathcal{L}(R) L ( R ) modulo scalar units. The units of L ( Z [ 1 / p ] ) \mathcal{L}(\mathbb{Z}[1/p]) L ( Z [ 1/ p ]) are the elements whose norm is a power of p p p , and the scalar units are ± p Z \pm p^{\mathbb{Z}} ± p Z . For the Hamilton quaternions, G ′ ( Z [ 1 / p ] ) G'(\mathbb{Z}[1/p]) G ′ ( Z [ 1/ p ]) is the group denoted Γ \Gamma Γ in [Lub94, Section 7.0]. For a positive integer N N N prime to p p p , its principal congruence subgroup of level N N N is
Γ p ( N ) = ker ( G ′ ( Z [ 1 / p ] ) ⟶ G ′ ( Z [ 1 / p ] / N Z [ 1 / p ] ) ) , (17) \Gamma_p(N)=\ker\left(G'(\mathbb{Z}[1/p])\longrightarrow G'(\mathbb{Z}[1/p]/N\mathbb{Z}[1/p])\right), \tag*{(17)} Γ p ( N ) = ker ( G ′ ( Z [ 1/ p ]) ⟶ G ′ ( Z [ 1/ p ] / N Z [ 1/ p ]) ) , (17)
where Z [ 1 / p ] / N Z [ 1 / p ] ≅ Z / N Z \mathbb{Z}[1/p]/N\mathbb{Z}[1/p]\cong\mathbb{Z}/N\mathbb{Z} Z [ 1/ p ] / N Z [ 1/ p ] ≅ Z / N Z . Thus Γ p ( N ) \Gamma_p(N) Γ p ( N ) consists of the classes [ a ] [a] [ a ] with a ≡ c ( m o d N ) a\equiv c\pmod N a ≡ c ( mod N ) for some scalar c c c invertible modulo N N N . Being a kernel, it is normal and has finite index.
Let
Λ p = ⟨ [ a ] : a ∈ A ( p ) ⟩ ⊆ G ′ ( Z [ 1 / p ] ) . \Lambda_p=\langle[a]:a\in A(p)\rangle\subseteq G'(\mathbb{Z}[1/p]). Λ p = ⟨[ a ] : a ∈ A ( p )⟩ ⊆ G ′ ( Z [ 1/ p ]) .
Since a a ˉ = p a\bar a=p a a ˉ = p for a ∈ A ( p ) a\in A(p) a ∈ A ( p ) , one has [ a ˉ ] = [ a ] − 1 [\bar a]=[a]^{-1} [ a ˉ ] = [ a ] − 1 . Choose a splitting D ⊗ Q p ≅ M 2 ( Q p ) D\otimes\mathbb{Q}_p\cong M_2(\mathbb{Q}_p) D ⊗ Q p ≅ M 2 ( Q p ) . Let T p + 1 T_{p+1} T p + 1 be the ( p + 1 ) (p+1) ( p + 1 ) -regular Bruhat–Tits tree, whose vertex set is
PGL 2 ( Q p ) / PGL 2 ( Z p ) . \operatorname{PGL}_2(\mathbb{Q}_p)/\operatorname{PGL}_2(\mathbb{Z}_p). PGL 2 ( Q p ) / PGL 2 ( Z p ) .
The splitting gives G ′ ( Z [ 1 / p ] ) G'(\mathbb{Z}[1/p]) G ′ ( Z [ 1/ p ]) an action on T p + 1 T_{p+1} T p + 1 .
Theorem A.2 (LPS tree realization). The following standard properties hold [10 ] , [Lub94, Corollary 2.1.11, Lemma 7.4.1, and p. 95].
(i) Λ p = Γ p ( 2 ) \Lambda_p = \Gamma_p(2) Λ p = Γ p ( 2 ) . Equivalently, Λ p \Lambda_p Λ p consists exactly of the classes having a representative a ∈ L ( Z [ 1 / p ] ) a \in\mathcal{L}(\mathbb{Z}[1/p]) a ∈ L ( Z [ 1/ p ]) with a ≡ 1 ( m o d 2 ) a \equiv1 \pmod{2} a ≡ 1 ( mod 2 ) and N ( a ) N(a) N ( a ) a power of p p p .
(ii) Λ p \Lambda_p Λ p is free on ( p + 1 ) / 2 (p+1)/2 ( p + 1 ) /2 generators. The full symmetric generating set is A ( p ) A(p) A ( p ) , with conjugate pairs representing inverse generators.
(iii) Λ p \Lambda_p Λ p acts simply transitively on the vertices of T p + 1 T_{p+1} T p + 1 , and
T p + 1 ≅ Cay ( Λ p ; A ( p ) ) . T_{p+1} \cong\operatorname{Cay}(\Lambda_p; A(p)). T p + 1 ≅ Cay ( Λ p ; A ( p )) .
Now let N N N be even and prime to p p p . Then Γ p ( N ) ⊆ Γ p ( 2 ) = Λ p \Gamma_p(N) \subseteq\Gamma_p(2) = \Lambda_p Γ p ( N ) ⊆ Γ p ( 2 ) = Λ p , and Γ p ( N ) \Gamma_p(N) Γ p ( N ) is the kernel of the restriction to Λ p \Lambda_p Λ p of projective reduction modulo N N N . Write this restriction as π N : Λ p → G ′ ( Z / N Z ) \pi_N : \Lambda_p \to G'(\mathbb{Z}/N\mathbb{Z}) π N : Λ p → G ′ ( Z / N Z ) . For N = 2 m N = 2^m N = 2 m , it is the map π m \pi_m π m of § 4 , whose image lies in G ^ m ⊆ G ′ ( Z / 2 m Z ) \widehat{G}_m \subseteq G'(\mathbb{Z}/2^m\mathbb{Z}) G m ⊆ G ′ ( Z / 2 m Z ) . Quotienting the Cayley graph of Theorem A.2 (iii) by the normal subgroup Γ p ( N ) \Gamma_p(N) Γ p ( N ) gives the Cayley graph of the quotient group:
Γ p ( N ) \ T p + 1 ≅ Cay ( π N ( Λ p ) ; π N ( A ( p ) ) ) . (18) \Gamma_p(N)\backslash T_{p+1} \cong\operatorname{Cay}\left(\pi_N(\Lambda_p); \pi_N(A(p))\right). \tag*{(18)} Γ p ( N ) \ T p + 1 ≅ Cay ( π N ( Λ p ) ; π N ( A ( p )) ) . (18)
At this stage the generating list is counted with multiplicity: collisions or identity images have not yet been excluded. In § 4 , Lemma 4.3 excludes them at the levels used there.
The parity of word length defines an index-two subgroup Λ p + ⊆ Λ p \Lambda_p^+ \subseteq\Lambda_p Λ p + ⊆ Λ p . This is well defined either from freeness or from the bipartition of T p + 1 T_{p+1} T p + 1 .
The Ramanujan property of congruence quotients
We use the following theorem from [Lub94, Chapter 7]. It extends the Ramanujan property of the LPS graphs to the congruence quotients of every level prime to p p p , without identifying their vertex groups. We state it for the Hamilton quaternions and the group G ′ ( Z [ 1 / p ] ) G'(\mathbb{Z[1/p]}) G ′ ( Z [ 1/ p ] ) above.
Theorem A.3 ([Lub94, Theorems 7.3.1 and 7.3.12]). Let p ≡ 1 ( m o d 4 ) p \equiv1 \pmod{4} p ≡ 1 ( mod 4 ) be prime and let N N N be a positive integer prime to p p p . Then
X p , N = Γ p ( N ) \ T p + 1 X^{p,N} = \Gamma_p(N)\backslash T_{p+1} X p , N = Γ p ( N ) \ T p + 1 is a finite ( p + 1 ) (p+1) ( p + 1 ) -regular Ramanujan graph: every adjacency eigenvalue λ \lambda λ satisfies
λ = ± ( p + 1 ) or ∣ λ ∣ ≤ 2 p . (19) \lambda= \pm(p+1) \qquad\text{or} \qquad|\lambda| \le2\sqrt{p}. \tag*{(19)} λ = ± ( p + 1 ) or ∣ λ ∣ ≤ 2 p . (19) Moreover:
(i) If p p p is a quadratic residue modulo N N N , then X p , N X^{p,N} X p , N is non-bipartite and has girth at least 2 log p N − 2 log p 2 2\log_p N - 2\log_p 2 2 log p N − 2 log p 2 .
(ii) If p p p is not a quadratic residue modulo N N N , then X p , N X^{p,N} X p , N is bipartite and has girth at least 4 log p N − 4 log p 2 4\log_p N - 4\log_p 2 4 log p N − 4 log p 2 .
Parts (i) and (ii) are Parts II and I of [Lub94, Theorem 7.3.12], respectively. The deep spectral input is Deligne’s theorem [Lub94, Theorem 6.1.2], the Ramanujan–Petersson conjecture in representation-theoretic form. It is transferred to the quaternion algebra by the Jacquet–Langlands correspondence [Lub94, Section 6.2, Theorem 6.2.1 and Corollary 6.2.2], and [Lub94, Theorem 7.1.1] records the resulting statement for the congruence subgroups. We use the theorem as a black box, and no automorphic argument is repeated here.