Introduction
The GV bound for concatenated codes
The Gilbert–Varshamov (GV) bound gives a classical lower bound on the best relative minimum distance attainable by binary codes at a given rate [10 , 19 ] . Its distance function is δ G V ( R ) = h 2 − 1 ( 1 − R ) \delta_{\mathrm{GV}}(R)=h_2^{-1}(1-R) δ GV ( R ) = h 2 − 1 ( 1 − R ) , where h 2 ( x ) : = − x log 2 x − ( 1 − x ) log 2 ( 1 − x ) h_2(x):=-x\log_2 x-(1-x)\log_2(1-x) h 2 ( x ) := − x log 2 x − ( 1 − x ) log 2 ( 1 − x ) is the binary entropy function (with 0 log 2 0 : = 0 0\log_2 0:=0 0 log 2 0 := 0 ), and h 2 − 1 : [ 0 , 1 ] → [ 0 , 1 / 2 ] h_2^{-1}:[0,1]\to[0,1/2] h 2 − 1 : [ 0 , 1 ] → [ 0 , 1/2 ] is the inverse of the restriction h 2 ∣ [ 0 , 1 / 2 ] h_2|_{[0,1/2]} h 2 ∣ [ 0 , 1/2 ] . A central problem in coding theory is to approach this bound with codes that admit efficient encoding and decoding.
Code concatenation is a classical approach to this problem. In a binary concatenated code [7 ] , each symbol of an outer code over a larger finite field is encoded as a word of a binary inner code. The classical analysis based on the product of the inner and outer minimum distances gives the Zyablov bound [20 ] . Thommesen showed that a Reed–Solomon outer code concatenated with independently chosen random binary inner maps, one per outer coordinate, can attain the GV bound [17 ] . Against this background, Doron, Mosheiff, and Wootters [6 ] expressed high moments of the bias of concatenated codewords in terms of the dual of the outer code. When both constituent codes are random linear codes of rate ε \varepsilon ε and the outer alphabet is sufficiently large, they obtain relative minimum distance at least 1 / 2 − O ( ε ) 1/2 - O(\varepsilon) 1/2 − O ( ε ) at binary rate ε 2 \varepsilon^2 ε 2 with high probability [6 Theorem 3] . Their existence proof, however, leaves open how to construct such outer codes explicitly. With this goal in mind, they asked what conditions on a fixed outer code would suffice to ensure that, with high probability, its concatenation with a single random binary linear inner code approaches the GV bound at low rates [6 Question 1] .
We address this question by extending their moment analysis to random subcodes of a prescribed linear code after coordinate scaling. The paper has two principal contributions.
We bound the probability of small minimum distance by two terms. The first depends on the bias moments of the inner code. The second arises from restricting the outer code to a scaled copy of the prescribed code A A A . Averaging over the scalings expresses this term through the weight distribution of A ⊥ A^\perp A ⊥ . A lower bound on the dual distance then suffices to control it.
For algebraic geometry (AG) codes on the Garcia–Stichtenoth (GS) tower [9 ] , the Riemann–Roch bound on dual distance makes the additional term exponentially small. We fix one inner encoding map throughout the tower at each target rate. The resulting distance lower bound holds with failure probability exponentially small in the block length. Its coefficient of R \sqrt{R} R agrees with that in the low-rate GV expansion
δ G V ( R ) = 1 2 − ln 2 2 R + O ( R 3 / 2 ) ( R → 0 ) . \delta_{\mathrm{GV}}(R) = \frac{1}{2} - \sqrt{\frac{\ln2}{2}}\sqrt{R} + O(R^{3/2}) \qquad(R \to0). δ GV ( R ) = 2 1 − 2 ln 2 R + O ( R 3/2 ) ( R → 0 ) .
For each fixed target rate, the AG encoder and decoder also give polynomial-time encoding and unique decoding up to the designed radius.
Main results
The codes considered in this paper. We study concatenated codes whose outer code is a random subcode of a scaled copy of a prescribed linear code and whose inner encoding map is the same at every coordinate. Let Q = 2 k 0 Q = 2^{k_0} Q = 2 k 0 , fix a binary [ n 0 , k 0 ] [n_0,k_0] [ n 0 , k 0 ] linear code C i n C_{\mathrm{in}} C in , and fix an F 2 \mathbb{F}_2 F 2 -linear isomorphism ϕ : F Q → C i n \phi: \mathbb{F}_Q \to C_{\mathrm{in}} ϕ : F Q → C in . Let A ≤ F Q K A \le\mathbb{F}_Q^K A ≤ F Q K be a prescribed K K K -dimensional linear code, called the base code , and fix an F Q \mathbb{F}_Q F Q -linear encoding isomorphism E A : F Q K → A E_A : \mathbb{F}_Q^K \to A E A : F Q K → A . We select a k k k -dimensional subcode, where 1 ≤ k ≤ K 1 \le k \le K 1 ≤ k ≤ K .
Choose a random k k k -dimensional subspace U ≤ F Q K U \le\mathbb{F}_Q^K U ≤ F Q K and, independently, choose α \alpha α uniformly from ( F Q × ) n (\mathbb{F}_Q^\times)^n ( F Q × ) n . Let diag ( α ) \operatorname{diag}(\alpha) diag ( α ) denote the diagonal matrix with entries α 1 , … , α n \alpha_1,\ldots,\alpha_n α 1 , … , α n . We call A α : = diag ( α ) A A_\alpha:= \operatorname{diag}(\alpha)A A α := diag ( α ) A the scaled base code and define
C o u t ( α , U ) : = diag ( α ) E A ( U ) ⊆ A α , C ( α , U ) : = C o u t ( α , U ) ∘ ϕ C i n ; C_{\mathrm{out}}(\alpha,U) := \operatorname{diag}(\alpha)E_A(U) \subseteq A_\alpha,\qquad C(\alpha,U) := C_{\mathrm{out}}(\alpha,U) \circ_\phi C_{\mathrm{in}}; C out ( α , U ) := diag ( α ) E A ( U ) ⊆ A α , C ( α , U ) := C out ( α , U ) ∘ ϕ C in ;
see § 3.1 for the precise definition of the concatenated codes. Thus C ( α , U ) C(\alpha,U) C ( α , U ) has block length N = n n 0 N = nn_0 N = n n 0 and binary dimension k k 0 kk_0 k k 0 . We choose the distribution of U U U so that
Pr U [ ℓ ∣ U = 0 ] ≤ Q − k \Pr_U[\ell|_U = 0] \le Q^{-k} U Pr [ ℓ ∣ U = 0 ] ≤ Q − k
for every nonzero F Q \mathbb{F}_Q F Q -linear functional ℓ : F Q K → F Q \ell: \mathbb{F}_Q^K \to\mathbb{F}_Q ℓ : F Q K → F Q . (1.1)
The uniform distribution on k k k -dimensional subspaces satisfies (1.1). § 4.1 gives further examples using graphs of linear maps. In the moment expansion below, condition (1.1) makes the average contribution from vectors outside A α ⊥ A_\alpha^\perp A α ⊥ nonpositive. Averaging over the coordinate scalings expresses the contribution from nonzero vectors in A α ⊥ A_\alpha^\perp A α ⊥ in terms of the weight distribution of A ⊥ A^\perp A ⊥ (Remark 3.7 ). These two steps are explained in § 3.3 and § 4.3.1 . Moreover, the inclusion C o u t ( α , U ) ⊆ A α C_{\mathrm{out}}(\alpha,U) \subseteq A_\alpha C out ( α , U ) ⊆ A α allows us to use the decoding algorithms available for A A A (§ 6.3 ).
A general bound on the probability of small minimum distance. Write Tr : = Tr F Q / F 2 \operatorname{Tr}:=\operatorname{Tr}_{\mathbb{F}_Q/\mathbb{F}_2} Tr := Tr F Q / F 2 and let ω j ∈ F Q \omega_j\in\mathbb{F}_Q ω j ∈ F Q be the unique element such that
ϕ ( a ) j = Tr ( ω j a ) ( a ∈ F Q , 1 ≤ j ≤ n 0 ) . \phi(a)_j=\operatorname{Tr}(\omega_j a)\qquad(a\in\mathbb{F}_Q,\ 1\le j\le n_0). ϕ ( a ) j = Tr ( ω j a ) ( a ∈ F Q , 1 ≤ j ≤ n 0 ) .
For an integer r ≥ 1 r\ge1 r ≥ 1 , choose an ordered tuple V = ( ( i 1 , j 1 ) , … , ( i r , j r ) ) V=((i_1,j_1),\ldots,(i_r,j_r)) V = (( i 1 , j 1 ) , … , ( i r , j r )) uniformly from V r : = ( { 1 , … , n } × { 1 , … , n 0 } ) r \mathcal{V}_r:=\left(\{1,\ldots,n\}\times\{1,\ldots,n_0\}\right)^r V r := ( { 1 , … , n } × { 1 , … , n 0 } ) r , independently of α \alpha α . Associate to V V V the vector g V ∈ F Q n g_V\in\mathbb{F}_Q^n g V ∈ F Q n given by
( g V ) i : = ∑ ℓ : i ℓ = i ω j ℓ ( 1 ≤ i ≤ n ) . (g_V)_i:=\sum_{\ell:i_\ell=i}\omega_{j_\ell}\qquad(1\le i\le n). ( g V ) i := ℓ : i ℓ = i ∑ ω j ℓ ( 1 ≤ i ≤ n ) .
For 0 < β < 1 0<\beta<1 0 < β < 1 and an even integer r ≥ 2 r\ge2 r ≥ 2 , define
T 0 : = Q k ( β N ) r # { V ∈ V r : g V = 0 } , T_0:=\frac{Q^k}{(\beta N)^r}\#\{V\in\mathcal{V}_r:g_V=0\}, T 0 := ( β N ) r Q k # { V ∈ V r : g V = 0 } ,
T A : = Q k ( β N ) r E α # { V ∈ V r : 0 ≠ g V ∈ A α ⊥ } . (1) T_A:=\frac{Q^k}{(\beta N)^r}\mathbb{E}_{\alpha}\#\{V\in\mathcal{V}_r:0\ne g_V\in A_\alpha^\perp\}. \tag*{(1)} T A := ( β N ) r Q k E α # { V ∈ V r : 0 = g V ∈ A α ⊥ } . (1)
We first prove the following bound.
Theorem 1.1 (General probability bound). For the construction above, suppose that the distribution of U U U satisfies (1.1). For every 0 < β < 1 0<\beta<1 0 < β < 1 and every even integer r ≥ 2 r\ge2 r ≥ 2 ,
Pr α , U [ δ ( C ( α , U ) ) < 1 − β 2 ] ≤ T 0 + T A . (2) \Pr_{\alpha,U}\left[\delta(C(\alpha,U))<\frac{1-\beta}{2}\right]\le T_0+T_A. \tag*{(2)} α , U Pr [ δ ( C ( α , U )) < 2 1 − β ] ≤ T 0 + T A . (2)
A binary linear code C ≤ F 2 N C\le\mathbb{F}_2^N C ≤ F 2 N is called β \beta β -balanced if every nonzero x ∈ C x\in C x ∈ C satisfies ∣ wt ( x ) / N − 1 / 2 ∣ ≤ β / 2 \left|\operatorname{wt}(x)/N-1/2\right|\le\beta/2 ∣ wt ( x ) / N − 1/2 ∣ ≤ β /2 , where wt ( x ) \operatorname{wt}(x) wt ( x ) is its Hamming weight. We will prove the following stronger estimate under the assumptions of Theorem 1.1:
Pr α , U [ C ( α , U ) is not β -balanced ] ≤ T 0 + T A . (3) \Pr_{\alpha,U}[C(\alpha,U)\text{ is not }\beta\text{-balanced}]\le T_0+T_A. \tag*{(3)} α , U Pr [ C ( α , U ) is not β -balanced ] ≤ T 0 + T A . (3)
When A = F Q n A=\mathbb{F}_Q^n A = F Q n and U U U is a uniformly random k k k -dimensional subspace, coordinate scaling preserves this distribution and A ⊥ = { 0 } A^\perp=\{0\} A ⊥ = { 0 } . Thus T A = 0 T_A=0 T A = 0 and only the tuples with g V = 0 g_V=0 g V = 0 enter the upper bound, as in the random outer code argument of Doron, Mosheiff, and Wootters [6 Section 1.2] . With both constituent rates equal to ε \varepsilon ε and log 2 Q = Ω ( ε − 3 ) \log_2 Q=\Omega(\varepsilon^{-3}) log 2 Q = Ω ( ε − 3 ) , this specialization recovers the 1 / 2 − O ( ε ) 1/2-O(\varepsilon) 1/2 − O ( ε ) lower bound on relative distance at binary rate ε 2 \varepsilon^2 ε 2 in their Theorem 3 (see § 7.1 ). For a proper base code, Theorem 1.1 allows any subspace distribution satisfying (1.1), and the nonzero vectors in A α ⊥ A_\alpha^\perp A α ⊥ contribute the additional term T A T_A T A .
The moment identity and the proof are given in § 3.2 and § 3.3 . In § 4 , we construct distributions satisfying (1.1) and derive sufficient conditions for both terms to decay exponentially.
Choice of parameters. To obtain a useful distance guarantee, we choose the inner code and the base code so that both terms are small. The first term, T 0 T_0 T 0 , is independent of A A A and of the choice of the inner encoding map. We choose an inner code satisfying the τ \tau τ -nice condition in Definition 3.3, and choose its rate and block length so that the bias of a uniformly random inner codeword has a sufficiently small moment generating function. The estimates in Section 3.2 then make T 0 T_0 T 0 decay exponentially.
Our main technical contribution is an estimate for T A T_A T A , which arises from the restriction of the outer code to the scaled base code A α A_\alpha A α . In § 4.3.1 , we bound this additional term using the weight distribution of A ⊥ A^\perp A ⊥ , and in particular its minimum distance:
T A ≤ Q k β r ( Q − 1 ) 1 − d ( A ⊥ ) ( A ⊥ ≠ { 0 } ) . T_A\le\frac{Q^k}{\beta^r}(Q-1)^{1-d(A^\perp)}\qquad(A^\perp\ne\{0\}). T A ≤ β r Q k ( Q − 1 ) 1 − d ( A ⊥ ) ( A ⊥ = { 0 }) .
Thus, we choose A A A with sufficiently large dual distance to make T A T_A T A decay exponentially as well. The resulting conditions are stated in Corollary 3.9 .
A construction from AG codes. Let A = C L ( D , G ) A=C_L(D,G) A = C L ( D , G ) be an AG code on a curve of genus g g g ; see § 5.2 for the definition. The Riemann–Roch theorem gives d ( A ⊥ ) ≥ deg G − 2 g + 2 d(A^\perp)\ge\deg G-2g+2 d ( A ⊥ ) ≥ deg G − 2 g + 2 . On the GS tower, we can choose deg G \deg G deg G so that this lower bound meets the requirement for T A T_A T A , while A A A has dimension large enough to contain the desired subcode. Together with the choice of the inner code described above, this gives a concrete family to which Theorem 1.1 applies. The precise construction is given in § 5.1 and § 5.3 and yields the following result.
Theorem 1.2 (GV asymptotics at low rates from AG codes (informal)). For every sufficiently small ε > 0 \varepsilon>0 ε > 0 , there is an explicit randomized construction of binary concatenated codes ( C m ) m (C_m)_m ( C m ) m , with block lengths N m N_m N m and rates R m R_m R m , whose outer codes are subcodes of scaled AG codes. For fixed ε \varepsilon ε , the construction uses one inner encoding map, independent of m m m , and the rates satisfy lim m → ∞ R m = ε 2 \lim_{m\to\infty}R_m=\varepsilon^2 lim m → ∞ R m = ε 2 . Moreover, there is a constant c > 0 c>0 c > 0 , independent of ε \varepsilon ε and m m m , such that, for all sufficiently large m m m ,
Pr α m , U m [ δ ( C m ) ≥ h 2 − 1 ( 1 − ε 2 − ε 4 ) ] ≥ 1 − 2 − c ε 4 N m . \Pr_{\alpha_m,U_m}\left[\delta(C_m)\ge h_2^{-1}\left(1-\varepsilon^2-\varepsilon^4\right)\right]\ge1-2^{-c\varepsilon^4N_m}. α m , U m Pr [ δ ( C m ) ≥ h 2 − 1 ( 1 − ε 2 − ε 4 ) ] ≥ 1 − 2 − c ε 4 N m . At the limiting rate R = lim m → ∞ R m = ε 2 R=\lim_{m\to\infty}R_m=\varepsilon^2 R = lim m → ∞ R m = ε 2 , the distance target is δ G V ( R + R 2 ) \delta_{\mathrm{GV}}(R+R^2) δ GV ( R + R 2 ) , which differs from δ G V ( R ) \delta_{\mathrm{GV}}(R) δ GV ( R ) by O ( R 3 / 2 ) O(R^{3/2}) O ( R 3/2 ) as R → 0 R\to0 R → 0 . The full statement and parameter choices are given in Theorem 4.3 and Table 1 . For each fixed ε \varepsilon ε , we choose the inner code once by exhaustive search and fix its encoding map. The probability in Theorem 1.2 is over the choice of the message subspace and the coordinate scalings. With either subspace construction in Example 3.2, the outer seed has description length O ( ε N m ) O(\varepsilon N_m) O ( ε N m ) and the expected running time of the construction is polynomial in N m N_m N m .
Table 1: Parameters for the GS construction. The bar on ρ ˉ i n \bar{\rho}_{\mathrm{in}} ρ ˉ in denotes the target before rounding; the outer dimension uses the actual inner rate.
Table 1.
By Corollary 4.4, for each sufficiently small ε > 0 \varepsilon>0 ε > 0 and all sufficiently large m m m , there exists a subcode of a scaled GS code whose concatenation with a uniformly random injective F 2 \mathbb{F}_2 F 2 -linear inner map meets the distance target of Theorem 1.2 with probability tending to one as ε → 0 \varepsilon\to0 ε → 0 . This answers the fixed-outer-code question of Doron, Mosheiff, and Wootters [6 Question 1] for this family in the low-rate regime.
Related work
Guruswami and Indyk gave polynomial-time decoding algorithms for low-rate concatenated codes that meet the GV bound using independently chosen inner maps [12 ] . Independent random inner encoding maps at all n n n outer coordinates require separate random choices for each coordinate; specifying n n n arbitrary binary linear [ n 0 , k 0 ] [n_0,k_0] [ n 0 , k 0 ] inner maps directly requires O ( n n 0 k 0 ) O(nn_0k_0) O ( n n 0 k 0 ) bits, compared with O ( n 0 k 0 ) O(n_0k_0) O ( n 0 k 0 ) bits for a single reused map.
Barg, Justesen, and Thommesen studied concatenations of a fixed inner code with a random linear outer code using the weight distribution and cumulants of the inner code [1 ] . In particular, their Proposition 3 relates the agreement of the resulting expansion at low rates with the GV expansion to the dual distance of the inner code. Thus agreement with the leading GV coefficient in the setting of a random linear outer code is already known. Their expansion keeps the inner code fixed as the total rate tends to zero. In our GS family, the inner code is fixed along the tower at each target rate, but its length grows as the target rate tends to zero.
Umeda, Sakakibara, and Kasahara used the average binary weight enumerator to show that most binary images in their family of generalized AG codes meet the GV bound [18 ] . In a binary expansion, each symbol of F Q \mathbb{F}_Q F Q is represented by k 0 = log 2 Q k_0=\log_2 Q k 0 = log 2 Q bits. In our construction, each symbol is encoded by a word of length n 0 > k 0 n_0>k_0 n 0 > k 0 in a fixed τ \tau τ -nice inner code. Ben-Aroya and Ta-Shma obtained explicit balanced binary codes by concatenating Hermitian codes with the Hadamard code, whose nonzero words all have the same weight [2 Sections 3.2 and 3.3] .
Other recent approaches obtain capacity for list decoding by randomly deleting coordinates from AG codes over a fixed alphabet [3 ] , or take traces of AG codes to obtain binary codes [5 ] .
Here list decoding allows the decoder to return several candidate codewords; deleting coordinates is called puncturing.
Organization of the paper
Section 2 introduces the construction and the moment identity, and proves Theorem 1.1 . Section 3 gives distributions satisfying (1.1) and estimates the two terms in the bound. Section 4 derives the parameters, constructs AG base codes, and proves the distance theorem. Section 5 treats randomness, encoding, and decoding. Section 6 compares the construction with random linear outer codes, explains the rate allocation, and discusses open problems. Appendix A gives complementary bounds obtained by Poissonization.
Construction framework and a general probability bound
We recall the notation and the moment identity of Doron, Mosheiff, and Wootters, then use condition (1.1) to prove Theorem 1.1 .
Notation for codes and concatenation
For a positive integer t t t , let [ t ] : = { 1 , … , t } [t] := \{1, \ldots, t\} [ t ] := { 1 , … , t } . We write ln \ln ln for the natural logarithm and log b \log_b log b for the logarithm to base b b b ; an unsubscripted log \log log also denotes the natural logarithm. We use O O O and o o o with respect to the indicated limit. In an inequality f ≤ g + O ( h ) f \le g + O(h) f ≤ g + O ( h ) , with h ≥ 0 h \ge0 h ≥ 0 , the notation means that f ≤ g + C h f \le g + Ch f ≤ g + C h for some constant C > 0 C > 0 C > 0 in the stated asymptotic regime.
A linear [ ℓ , j ] [\ell, j] [ ℓ , j ] code over a field F F F is a subspace C ≤ F ℓ C \le F^\ell C ≤ F ℓ of dimension j j j . Its rate is j / ℓ j/\ell j / ℓ . The support of a word c c c is supp ( c ) : = { i : c i ≠ 0 } \operatorname{supp}(c) := \{i : c_i \ne0\} supp ( c ) := { i : c i = 0 } , and its Hamming weight is wt ( c ) : = ∣ supp ( c ) ∣ \operatorname{wt}(c) := |\operatorname{supp}(c)| wt ( c ) := ∣ supp ( c ) ∣ . The dual code is C ⊥ : = { y ∈ F ℓ : ∑ i c i y i = 0 for all c ∈ C } C^\perp:= \{y \in F^\ell: \sum_i c_i y_i = 0 \text{ for all } c \in C\} C ⊥ := { y ∈ F ℓ : ∑ i c i y i = 0 for all c ∈ C } . The weight enumerator of C C C is W C ( x , y ) : = ∑ c ∈ C x ℓ − wt ( c ) y wt ( c ) W_C(x,y) := \sum_{c \in C} x^{\ell-\operatorname{wt}(c)} y^{\operatorname{wt}(c)} W C ( x , y ) := ∑ c ∈ C x ℓ − wt ( c ) y wt ( c ) . The Hamming distance between two words of the same length is d H ( x , y ) : = wt ( x − y ) d_H(x,y) := \operatorname{wt}(x-y) d H ( x , y ) := wt ( x − y ) . The minimum Hamming distance is d ( C ) : = min { wt ( c ) : 0 ≠ c ∈ C } d(C) := \min\{\operatorname{wt}(c) : 0 \ne c \in C\} d ( C ) := min { wt ( c ) : 0 = c ∈ C } , with the convention d ( { 0 } ) = ∞ d(\{0\}) = \infty d ({ 0 }) = ∞ . The relative minimum distance is δ ( C ) : = d ( C ) / ℓ \delta(C) := d(C)/\ell δ ( C ) := d ( C ) / ℓ . We use the shorter term “distance” when the meaning is clear.
For a concatenated code, let n n n be the outer block length, n 0 n_0 n 0 the binary inner block length, and N : = n n 0 N := nn_0 N := n n 0 the block length of the resulting binary code. Let C i n ≤ F 2 n 0 C_{\mathrm{in}} \le\mathbb{F}_2^{n_0} C in ≤ F 2 n 0 be the inner code of dimension k 0 k_0 k 0 , and let k k k be the dimension of the outer code. Write A ≤ F Q n A \le\mathbb{F}_Q^n A ≤ F Q n for the base code from which subcodes are selected, and let K ≥ k K \ge k K ≥ k be its dimension. Set ρ i n : = k 0 / n 0 \rho_{\mathrm{in}} := k_0/n_0 ρ in := k 0 / n 0 , ρ o u t : = k / n \rho_{\mathrm{out}} := k/n ρ out := k / n , R : = k k 0 / N = ρ i n ρ o u t R := kk_0/N = \rho_{\mathrm{in}}\rho_{\mathrm{out}} R := k k 0 / N = ρ in ρ out , and Q = 2 k 0 Q = 2^{k_0} Q = 2 k 0 . Dimensions of codes over F Q \mathbb{F}_Q F Q and of binary codes are taken over F Q \mathbb{F}_Q F Q and F 2 \mathbb{F}_2 F 2 , respectively. For S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] , write F Q S : = { z ∈ F Q n : supp ( z ) ⊆ S } \mathbb{F}_Q^S := \{z \in\mathbb{F}_Q^n : \operatorname{supp}(z) \subseteq S\} F Q S := { z ∈ F Q n : supp ( z ) ⊆ S } . The dual distance of A A A is d ( A ⊥ ) d(A^\perp) d ( A ⊥ ) .
Write Tr : = Tr F Q / F 2 \operatorname{Tr} := \operatorname{Tr}_{\mathbb{F}_Q/\mathbb{F}_2} Tr := Tr F Q / F 2 . Fix a basis of F Q \mathbb{F}_Q F Q over F 2 \mathbb{F}_2 F 2 . For C ≤ F Q n C \le\mathbb{F}_Q^n C ≤ F Q n and a fixed F 2 \mathbb{F}_2 F 2 -linear isomorphism ϕ : F Q → C i n \phi: \mathbb{F}_Q \to C_{\mathrm{in}} ϕ : F Q → C in , denote the binary concatenation by
C ∘ ϕ C i n : = { ( ϕ ( c 1 ) , … , ϕ ( c n ) ) : c = ( c 1 , … , c n ) ∈ C } ≤ F 2 N . C \mathbin{\circ_\phi} C_{\mathrm{in}} := \{(\phi(c_1), \ldots, \phi(c_n)) : c = (c_1, \ldots, c_n) \in C\} \le\mathbb{F}_2^N. C ∘ ϕ C in := {( ϕ ( c 1 ) , … , ϕ ( c n )) : c = ( c 1 , … , c n ) ∈ C } ≤ F 2 N .
As the concatenated code depends on the choice of ϕ \phi ϕ , we indicate this dependence explicitly. For a predicate P, let 1 [ P ] \mathbf{1}[P] 1 [ P ] denote its indicator.
Definition 2.1. For any positive integer ℓ \ell ℓ and x ∈ F 2 ℓ x \in\mathbb{F}_2^\ell x ∈ F 2 ℓ , define its unnormalized bias by bias ( x ) : = ∑ j = 1 ℓ ( − 1 ) x j = ℓ − 2 wt ( x ) \operatorname{bias}(x) := \sum_{j=1}^{\ell}(-1)^{x_j} = \ell- 2\operatorname{wt}(x) bias ( x ) := ∑ j = 1 ℓ ( − 1 ) x j = ℓ − 2 wt ( x ) . For x ( 1 ) , … , x ( n ) ∈ F 2 n 0 x^{(1)}, \ldots, x^{(n)} \in\mathbb{F}_2^{n_0} x ( 1 ) , … , x ( n ) ∈ F 2 n 0 , set
bias ( x ( 1 ) , … , x ( n ) ) : = ∑ i = 1 n bias ( x ( i ) ) . \operatorname{bias}(x^{(1)}, \ldots, x^{(n)}) := \sum_{i=1}^{n}\operatorname{bias}(x^{(i)}). bias ( x ( 1 ) , … , x ( n ) ) := i = 1 ∑ n bias ( x ( i ) ) . This is the bias quantity used in [6 Section 1.2] , expressed in terms of a concatenated word. For a concatenated word of length N N N and 0 < β < 1 0 < \beta< 1 0 < β < 1 , the inequalities bias ( x ) > β N \operatorname{bias}(x) > \beta N bias ( x ) > β N
and wt ( x ) / N < ( 1 − β ) / 2 \operatorname{wt}(x)/N < (1-\beta)/2 wt ( x ) / N < ( 1 − β ) /2 are equivalent. This equivalence converts moment estimates into distance estimates. A binary linear code C ≤ F 2 N C \leq\mathbb{F}_2^N C ≤ F 2 N is called β \beta β -balanced if, for every 0 ≠ x ∈ C 0 \ne x \in C 0 = x ∈ C , ∣ bias ( x ) ∣ ≤ β N |\operatorname{bias}(x)| \leq\beta N ∣ bias ( x ) ∣ ≤ β N , or equivalently ( 1 − β ) / 2 ≤ wt ( x ) / N ≤ ( 1 + β ) / 2 (1-\beta)/2 \leq\operatorname{wt}(x)/N \leq(1+\beta)/2 ( 1 − β ) /2 ≤ wt ( x ) / N ≤ ( 1 + β ) /2 .
Our construction of concatenated codes. Now let A ≤ F Q n A \leq\mathbb{F}_Q^n A ≤ F Q n be the base code of dimension K ≥ k K \geq k K ≥ k , and fix an F Q \mathbb{F}_Q F Q -linear encoding isomorphism E A : F Q K → A E_A:\mathbb{F}_Q^K \to A E A : F Q K → A . For U U U sampled from a distribution U \mathcal{U} U satisfying condition (1.1) and α ∈ ( F Q × ) n \alpha\in(\mathbb{F}_Q^\times)^n α ∈ ( F Q × ) n , define
C o u t ( α , U ) : = diag ( α ) E A ( U ) ⊆ A α : = diag ( α ) A . (4) C_{\mathrm{out}}(\alpha,U) := \operatorname{diag}(\alpha)E_A(U) \subseteq A_\alpha:= \operatorname{diag}(\alpha)A. \tag*{(4)} C out ( α , U ) := diag ( α ) E A ( U ) ⊆ A α := diag ( α ) A . (4)
See also Figure 1 for the construction. The dimension of C o u t ( α , U ) C_{\mathrm{out}}(\alpha,U) C out ( α , U ) is exactly k k k , and A α A_\alpha A α is its scaled base code. When Z Z Z denotes a random seed specifying the subspace, we write U = U Z U=U_Z U = U Z and abbreviate C o u t ( α , U Z ) C_{\mathrm{out}}(\alpha,U_Z) C out ( α , U Z ) as C o u t ( α , Z ) C_{\mathrm{out}}(\alpha,Z) C out ( α , Z ) .
Figure 1. A random subspace U U U determines E A ( U ) ⊆ A E_A(U) \subseteq A E A ( U ) ⊆ A in the fixed base code. Independent coordinate scaling gives the outer code inside the scaled base code A α A_\alpha A α . The map ϕ × n \phi^{\times n} ϕ × n applies the same inner encoding map to every coordinate.
A moment identity
To analyze the distance of the concatenated code, we expand moments of the biases of its nonzero codewords. The following identity holds for any fixed outer code, without assuming a probability distribution on that code. Recall the trace representation ϕ ( a ) j = Tr ( ω j a ) \phi(a)_j=\operatorname{Tr}(\omega_j a) ϕ ( a ) j = Tr ( ω j a ) used in § 1.2 . It exists because coordinate j j j of ϕ \phi ϕ is an F 2 \mathbb{F}_2 F 2 -linear functional on F Q \mathbb{F}_Q F Q ; the nondegeneracy of the trace pairing gives the uniqueness of ω j \omega_j ω j .
For an integer r ≥ 0 r \geq0 r ≥ 0 , let V r : = ( [ n ] × [ n 0 ] ) r \mathcal{V}_r := ([n] \times[n_0])^r V r := ([ n ] × [ n 0 ] ) r , with V 0 \mathcal{V}_0 V 0 consisting only of the empty tuple. For V = ( ( i 1 , j 1 ) , … , ( i r , j r ) ) ∈ V r V=((i_1,j_1),\ldots,(i_r,j_r)) \in\mathcal{V}_r V = (( i 1 , j 1 ) , … , ( i r , j r )) ∈ V r , define
( g V ) i : = ∑ ℓ : i ℓ = i ω j ℓ ∈ F Q ( i ∈ [ n ] ) . (g_V)_i := \sum_{\ell:i_\ell=i}\omega_{j_\ell} \in\mathbb{F}_Q \qquad(i \in[n]). ( g V ) i := ℓ : i ℓ = i ∑ ω j ℓ ∈ F Q ( i ∈ [ n ]) .
We have ∣ V r ∣ = N r |\mathcal{V}_r|=N^r ∣ V r ∣ = N r . Permuting the outer coordinates induces a bijection on the tuples and the same permutation on the coordinates of g V g_V g V . Define
Z r : = { V ∈ V r : g V = 0 } , p r ( 0 ) : = ∣ Z r ∣ N r = Pr V ∈ V r [ g V = 0 ] , \mathcal{Z}_r := \{V \in\mathcal{V}_r:g_V=0\}, \qquad p_r^{(0)} := \frac{|\mathcal{Z}_r|}{N^r} = \Pr_{V\in\mathcal{V}_r}[g_V=0], Z r := { V ∈ V r : g V = 0 } , p r ( 0 ) := N r ∣ Z r ∣ = V ∈ V r Pr [ g V = 0 ] ,
where V V V is uniform on V r \mathcal{V}_r V r . In particular, p 0 ( 0 ) = 1 p_0^{(0)}=1 p 0 ( 0 ) = 1 .
Let C ≤ F Q n C \leq\mathbb{F}_Q^n C ≤ F Q n be a k k k -dimensional outer code, and fix an F Q \mathbb{F}_Q F Q -linear encoding isomorphism u ↦ c ( u ) u \mapsto c(u) u ↦ c ( u ) from F Q k \mathbb{F}_Q^k F Q k to C C C . Set X u : = bias ( ϕ ( c ( u ) 1 ) , … , ϕ ( c ( u ) n ) ) X_u:=\operatorname{bias}(\phi(c(u)_1),\ldots,\phi(c(u)_n)) X u := bias ( ϕ ( c ( u ) 1 ) , … , ϕ ( c ( u ) n )) . In what follows, E u ≠ 0 \mathbb{E}_{u\ne0} E u = 0 denotes the uniform average over u ∈ F Q k ∖ { 0 } u \in\mathbb{F}_Q^k \setminus\{0\} u ∈ F Q k ∖ { 0 } .
Lemma 2.2 (Moment identity; cf. [6 Section 1.2] ). For every integer r ≥ 1 r \geq1 r ≥ 1 , the following identity holds:
E u ≠ 0 X u r = 1 Q k − 1 ∑ V ∈ V r ( Q k 1 [ g V ∈ C ⊥ ] − 1 ) . (5) \mathbb{E}_{u\ne0}X_u^r = \frac{1}{Q^k-1}\sum_{V\in\mathcal{V}_r}\left(Q^k\mathbf{1}[g_V\in C^\perp]-1\right). \tag*{(5)} E u = 0 X u r = Q k − 1 1 V ∈ V r ∑ ( Q k 1 [ g V ∈ C ⊥ ] − 1 ) . (5)
Proof. Expanding X u r X_u^r X u r over V ∈ V r V \in\mathcal{V}_r V ∈ V r and using the trace representation of ϕ \phi ϕ gives X u r = ∑ V ∈ V r ( − 1 ) Tr ( c ( u ) ⋅ g V ) X_u^r = \sum_{V \in\mathcal{V}_r}(-1)^{\operatorname{Tr}(c(u)\cdot g_V)} X u r = ∑ V ∈ V r ( − 1 ) Tr ( c ( u ) ⋅ g V ) . For each V V V , character orthogonality gives Q k 1 [ g V ∈ C ⊥ ] Q^k1[g_V \in C^\perp] Q k 1 [ g V ∈ C ⊥ ] for the sum over all messages. Removing the u = 0 u=0 u = 0 term, dividing by Q k − 1 Q^k-1 Q k − 1 , and summing over V V V gives (2.2).
Proof and consequences of the general bound
For uniformly random α ∈ ( F Q × ) n \alpha\in(\mathbb{F}_Q^\times)^n α ∈ ( F Q × ) n , set A α : = diag ( α ) A A_\alpha:= \operatorname{diag}(\alpha)A A α := diag ( α ) A . To normalize the second count in (1.2), define, for r ≥ 1 r \ge1 r ≥ 1 ,
L r ( A , C i n ) : = 1 N r E α # { V ∈ V r : g V ≠ 0 , g V ∈ A α ⊥ } . \mathcal{L}_r(A,C_{\mathrm{in}}) := \frac{1}{N^r}\mathbb{E}_\alpha\#\{V \in\mathcal{V}_r : g_V \ne0,\ g_V \in A_\alpha^\perp\}. L r ( A , C in ) := N r 1 E α # { V ∈ V r : g V = 0 , g V ∈ A α ⊥ } .
Although g V g_V g V is defined using ϕ \phi ϕ , this average is independent of ϕ \phi ϕ . Set L 0 ( A , C i n ) : = 0 \mathcal{L}_0(A,C_{\mathrm{in}}):=0 L 0 ( A , C in ) := 0 . Both p r ( 0 ) p_r^{(0)} p r ( 0 ) and L r ( A , C i n ) \mathcal{L}_r(A,C_{\mathrm{in}}) L r ( A , C in ) are normalized by the number N r N^r N r of ordered tuples. Since their defining events are disjoint, we have
p r ( 0 ) + L r ( A , C i n ) = Pr α , V [ g V ∈ A α ⊥ ] , p_r^{(0)}+\mathcal{L}_r(A,C_{\mathrm{in}})=\Pr_{\alpha,V}[g_V\in A_\alpha^\perp], p r ( 0 ) + L r ( A , C in ) = α , V Pr [ g V ∈ A α ⊥ ] ,
where V V V is uniform on V r \mathcal{V}_r V r and independent of α \alpha α .
Write C : = C o u t ( α , U ) ∘ ϕ C i n C:=C_{\mathrm{out}}(\alpha,U)\circ_\phi C_{\mathrm{in}} C := C out ( α , U ) ∘ ϕ C in . The distance bound (1.3) takes the form
Pr α , U [ δ ( C ) < 1 − β 2 ] ≤ Q k β r ( p r ( 0 ) + L r ( A , C i n ) ) = T 0 + T A (6) \Pr_{\alpha,U}\left[\delta(C)<\frac{1-\beta}{2}\right]\le\frac{Q^k}{\beta^r}\left(p_r^{(0)}+\mathcal{L}_r(A,C_{\mathrm{in}})\right)=T_0+T_A \tag*{(6)} α , U Pr [ δ ( C ) < 2 1 − β ] ≤ β r Q k ( p r ( 0 ) + L r ( A , C in ) ) = T 0 + T A (6)
for 0 < β < 1 0<\beta<1 0 < β < 1 and even r ≥ 2 r\ge2 r ≥ 2 . Below, we prove the stronger estimate (1.4).
Proof of Theorem 1.1. For each nonzero message u ∈ F Q k u\in\mathbb{F}_Q^k u ∈ F Q k of the outer code, let X u X_u X u denote the unnormalized bias of the corresponding binary codeword, and set N b a d : = # { u ∈ F Q k ∖ { 0 } : ∣ X u ∣ > β N } N_{\mathrm{bad}}:=\#\{u\in\mathbb{F}_Q^k\setminus\{0\}: |X_u|>\beta N\} N bad := # { u ∈ F Q k ∖ { 0 } : ∣ X u ∣ > β N } . Since r r r is even, 1 [ ∣ X u ∣ > β N ] ≤ X u r / ( β N ) r 1[|X_u|>\beta N]\le X_u^r/(\beta N)^r 1 [ ∣ X u ∣ > β N ] ≤ X u r / ( β N ) r , and hence
N b a d ≤ Q k − 1 ( β N ) r E u ≠ 0 X u r . (7) N_{\mathrm{bad}}\le\frac{Q^k-1}{(\beta N)^r}\mathbb{E}_{u\ne0}X_u^r. \tag*{(7)} N bad ≤ ( β N ) r Q k − 1 E u = 0 X u r . (7)
Substituting (2.2) in (2.4) cancels the factor Q k − 1 Q^k-1 Q k − 1 and gives
( β N ) r N b a d ≤ ∑ V ∈ V r ( Q k 1 [ g V ∈ C o u t ( α , U ) ⊥ ] − 1 ) . (\beta N)^rN_{\mathrm{bad}}\le\sum_{V\in\mathcal{V}_r}\left(Q^k1[g_V\in C_{\mathrm{out}}(\alpha,U)^\perp]-1\right). ( β N ) r N bad ≤ V ∈ V r ∑ ( Q k 1 [ g V ∈ C out ( α , U ) ⊥ ] − 1 ) .
For a fixed tuple V ∈ V r V\in\mathcal{V}_r V ∈ V r and scaling α \alpha α , define ℓ V , α ( x ) : = ∑ i = 1 n ( g V ) i α i ( E A ( x ) ) i \ell_{V,\alpha}(x):=\sum_{i=1}^n(g_V)_i\alpha_i(E_A(x))_i ℓ V , α ( x ) := ∑ i = 1 n ( g V ) i α i ( E A ( x ) ) i . By the definition of C o u t ( α , U ) C_{\mathrm{out}}(\alpha,U) C out ( α , U ) , the conditions g V ∈ C o u t ( α , U ) ⊥ g_V\in C_{\mathrm{out}}(\alpha,U)^\perp g V ∈ C out ( α , U ) ⊥ and ℓ V , α ∣ U = 0 \ell_{V,\alpha}|_U=0 ℓ V , α ∣ U = 0 are equivalent.
We classify the tuples according to g V g_V g V . First, if g V = 0 g_V=0 g V = 0 , then g V ∈ C o u t ( α , U ) ⊥ g_V\in C_{\mathrm{out}}(\alpha,U)^\perp g V ∈ C out ( α , U ) ⊥ for every α , U \alpha,U α , U , since every linear code contains the zero vector. These tuples therefore contribute ( Q k − 1 ) ∣ Z r ∣ (Q^k-1)|\mathcal{Z}_r| ( Q k − 1 ) ∣ Z r ∣ to the sum above.
Next, suppose g V ≠ 0 g_V\ne0 g V = 0 . If g V ∉ A α ⊥ g_V\notin A_\alpha^\perp g V ∈ / A α ⊥ , then ℓ V , α \ell_{V,\alpha} ℓ V , α is a nonzero linear functional. Condition (1.1) gives Pr U [ ℓ V , α ∣ U = 0 ] ≤ Q − k \Pr_U[\ell_{V,\alpha}|_U=0]\le Q^{-k} Pr U [ ℓ V , α ∣ U = 0 ] ≤ Q − k , and thus E U [ Q k 1 [ g V ∈ C o u t ( α , U ) ⊥ ] − 1 ] ≤ 0 \mathbb{E}_U[Q^k1[g_V\in C_{\mathrm{out}}(\alpha,U)^\perp]-1]\le0 E U [ Q k 1 [ g V ∈ C out ( α , U ) ⊥ ] − 1 ] ≤ 0 . Consequently, these tuples make no positive contribution after averaging over U U U .
It remains to consider g V ≠ 0 g_V\ne0 g V = 0 with g V ∈ A α ⊥ g_V\in A_\alpha^\perp g V ∈ A α ⊥ . In this case, ℓ V , α = 0 \ell_{V,\alpha}=0 ℓ V , α = 0 , so g V ∈ C o u t ( α , U ) ⊥ g_V\in C_{\mathrm{out}}(\alpha,U)^\perp g V ∈ C out ( α , U ) ⊥ for every U U U . Averaging first over U U U and then over α \alpha α , the positive contribution from tuples with g V ≠ 0 g_V\ne0 g V = 0 is at most Q k ∑ V : g V ≠ 0 Pr α [ g V ∈ A α ⊥ ] Q^k\sum_{V:g_V\ne0}\Pr_\alpha[g_V\in A_\alpha^\perp] Q k ∑ V : g V = 0 Pr α [ g V ∈ A α ⊥ ] .
Combining these observations with (2.4) gives
E α , U N b a d ≤ Q k β r ( p r ( 0 ) + L r ( A , C i n ) ) . (8) \mathbb{E}_{\alpha,U}N_{\mathrm{bad}}\le\frac{Q^k}{\beta^r}\left(p_r^{(0)}+\mathcal{L}_r(A,C_{\mathrm{in}})\right). \tag*{(8)} E α , U N bad ≤ β r Q k ( p r ( 0 ) + L r ( A , C in ) ) . (8)
The code C C C fails to be β \beta β -balanced if and only if N b a d ≥ 1 N_{\mathrm{bad}}\ge1 N bad ≥ 1 . Markov’s inequality Pr [ N b a d ≥ 1 ] ≤ E N b a d \Pr[N_{\mathrm{bad}}\ge1]\le\mathbb{E}N_{\mathrm{bad}} Pr [ N bad ≥ 1 ] ≤ E N bad and (2.5) give the stronger estimate (1.4). Since δ ( C ) < ( 1 − β ) / 2 \delta(C)<(1-\beta)/2 δ ( C ) < ( 1 − β ) /2 implies that C C C is not β \beta β -balanced, this also proves (2.3) and (1.3).
The moment identity follows the character orthogonality approach of Doron, Mosheiff, and Wootters [6 Section 1.2] . The additional step is to separate the vectors in the dual of the scaled base code from those for which (1.1) gives a nonpositive average contribution.
Sufficient conditions for exponential decay
To apply Theorem 1.1, the distribution of U U U must satisfy condition (1.1). We construct such distributions in Section 3.1, then estimate T 0 T_0 T 0 and T A T_A T A in Sections 3.2 and 3.3, respectively. Exponential decay of both terms gives the desired bound on the failure probability.
Distributions on subspaces
For 1 ≤ k ≤ K 1 \le k \le K 1 ≤ k ≤ K , write Gr Q ( k , K ) \operatorname{Gr}_{Q}(k,K) Gr Q ( k , K ) for the set of all k k k -dimensional F Q \mathbb{F}_{Q} F Q -subspaces of F Q K \mathbb{F}_{Q}^{K} F Q K . We first give a standard distribution satisfying (1.1), then construct distributions that use fewer random elements.
The uniform distribution on Gr Q ( k , K ) \operatorname{Gr}_{Q}(k,K) Gr Q ( k , K ) satisfies condition (1.1). Indeed, counting the k k k -dimensional subspaces contained in the kernel of a nonzero linear functional ℓ \ell ℓ gives
Pr U ∼ Gr Q ( k , K ) [ ℓ ∣ U = 0 ] = Q K − k − 1 Q K − 1 < Q − k . \Pr_{U \sim\operatorname{Gr}_{Q}(k,K)}[\ell|_{U}=0] = \frac{Q^{K-k}-1}{Q^{K}-1} < Q^{-k}. U ∼ Gr Q ( k , K ) Pr [ ℓ ∣ U = 0 ] = Q K − 1 Q K − k − 1 < Q − k .
Condition (1.1) allows us to choose a restricted family of subspaces. We use graphs of linear maps and give two constructions: one using Toeplitz matrices and one using multiplication in an extension field. Set s 0 : = K − k s_0 := K-k s 0 := K − k and identify F Q K \mathbb{F}_{Q}^{K} F Q K with F Q k ⊕ F Q s 0 \mathbb{F}_{Q}^{k} \oplus\mathbb{F}_{Q}^{s_0} F Q k ⊕ F Q s 0 . An arbitrary linear map from F Q s 0 \mathbb{F}_{Q}^{s_0} F Q s 0 to F Q k \mathbb{F}_{Q}^{k} F Q k requires k s 0 ks_0 k s 0 field elements to specify. For s 0 > 0 s_0 > 0 s 0 > 0 , a Toeplitz matrix uses only k + s 0 − 1 = K − 1 k+s_0-1=K-1 k + s 0 − 1 = K − 1 field elements. The required property is that the image of each fixed nonzero input be uniform on F Q k \mathbb{F}_{Q}^{k} F Q k . As the next lemma shows, this property is sufficient for the distribution on the associated graphs to satisfy (1.1). Let Z Z Z be a random seed and let H Z : F Q s 0 → F Q k H_Z:\mathbb{F}_{Q}^{s_0}\to\mathbb{F}_{Q}^{k} H Z : F Q s 0 → F Q k be a random linear map such that
Pr Z [ H Z ( b ) = a ] = Q − k for every 0 ≠ b ∈ F Q s 0 and every a ∈ F Q k . (9) \Pr_Z[H_Z(b)=a]=Q^{-k}\quad\text{for every }0\ne b\in\mathbb{F}_{Q}^{s_0}\text{ and every }a\in\mathbb{F}_{Q}^{k}. \tag*{(9)} Z Pr [ H Z ( b ) = a ] = Q − k for every 0 = b ∈ F Q s 0 and every a ∈ F Q k . (9)
This is the uniformity property used in [4 Definition 11] . Define the graph of H Z T H_Z^{\mathsf{T}} H Z T by
U Z : = { ( u , H Z T u ) : u ∈ F Q k } ≤ F Q k ⊕ F Q s 0 , U_Z:=\{(u,H_Z^{\mathsf{T}}u):u\in\mathbb{F}_{Q}^{k}\}\le\mathbb{F}_{Q}^{k}\oplus\mathbb{F}_{Q}^{s_0}, U Z := {( u , H Z T u ) : u ∈ F Q k } ≤ F Q k ⊕ F Q s 0 ,
where u u u is a column vector.
Lemma 3.1. If ( H Z ) Z (H_Z)_Z ( H Z ) Z satisfies (3.1), then the distribution of U Z U_Z U Z satisfies condition (1.1). More precisely, writing any nonzero linear map ℓ : F Q k ⊕ F Q s 0 → F Q \ell:\mathbb{F}_{Q}^{k}\oplus\mathbb{F}_{Q}^{s_0}\to\mathbb{F}_{Q} ℓ : F Q k ⊕ F Q s 0 → F Q as ℓ ( u , v ) = a ⋅ u + b ⋅ v \ell(u,v)=a\cdot u+b\cdot v ℓ ( u , v ) = a ⋅ u + b ⋅ v , we have
Pr Z [ ℓ ∣ U Z = 0 ] = { 0 , b = 0 , Q − k , b ≠ 0. \Pr_Z[\ell|_{U_Z}=0]=
\begin{cases}
0, & b=0,\\
Q^{-k}, & b\ne0.
\end{cases} Z Pr [ ℓ ∣ U Z = 0 ] = { 0 , Q − k , b = 0 , b = 0.
Proof. On the graph, ℓ ( u , H Z T u ) = ( a + H Z ( b ) ) ⋅ u \ell(u,H_Z^{\mathsf{T}}u)=(a+H_Z(b))\cdot u ℓ ( u , H Z T u ) = ( a + H Z ( b )) ⋅ u . The restriction vanishes identically if and only if H Z ( b ) = − a H_Z(b)=-a H Z ( b ) = − a . If b = 0 b=0 b = 0 , then ℓ ≠ 0 \ell\ne0 ℓ = 0 implies a ≠ 0 a\ne0 a = 0 , so this event cannot occur. If b ≠ 0 b\ne0 b = 0 , (3.1) gives probability Q − k Q^{-k} Q − k .
Example 3.2. When s 0 = 0 s_0=0 s 0 = 0 , set U Z = F Q k U_Z=\mathbb{F}_{Q}^{k} U Z = F Q k ; no randomness is needed to specify the subspace U Z U_Z U Z . In the following constructions, assume s 0 > 0 s_0>0 s 0 > 0 .
Construction using Toeplitz matrices. Choose a uniformly random Toeplitz matrix T ∈ F Q s 0 × k T\in\mathbb{F}_{Q}^{s_0\times k} T ∈ F Q s 0 × k , and set H Z ( b ) = T T b H_Z(b)=T^{\mathsf{T}}b H Z ( b ) = T T b . Write T i , j = z j − i T_{i,j}=z_{j-i} T i , j = z j − i , and let i 0 i_0 i 0 be the largest index for which b i 0 ≠ 0 b_{i_0}\ne0 b i 0 = 0 . Fix all diagonal variables except z 1 − i 0 , … , z k − i 0 z_{1-i_0},\ldots,z_{k-i_0} z 1 − i 0 , … , z k − i 0 . The output $(T^{\mathsf{T}}b)_j
contains z j − i 0 z_{j-i_0} z j − i 0 with coefficient b i 0 b_{i_0} b i 0 , and every diagonal index appearing in the remaining terms is larger than j − i 0 j-i_0 j − i 0 . Thus, the linear part of the affine map from the remaining k k k variables to T T b T^{\mathsf{T}}b T T b is represented by a triangular matrix whose diagonal entries are all b i 0 b_{i_0} b i 0 and is therefore invertible. Consequently, T T b T^{\mathsf{T}}b T T b is uniform on F Q k \mathbb{F}_Q^k F Q k . Toeplitz matrices give a standard example satisfying (3.1); see, for example, [4 ] .
Construction using multiplication in an extension field. Let m 0 = max { s 0 , k } m_0=\max\{s_0,k\} m 0 = max { s 0 , k } and K = F Q m 0 \mathbb{K}=\mathbb{F}_{Q^{m_0}} K = F Q m 0 . Fix an F Q \mathbb{F}_Q F Q -linear injection ι : F Q s 0 ↪ K \iota:\mathbb{F}_Q^{s_0}\hookrightarrow\mathbb{K} ι : F Q s 0 ↪ K and an F Q \mathbb{F}_Q F Q -linear surjection P : K ↠ F Q k P:\mathbb{K}\twoheadrightarrow\mathbb{F}_Q^k P : K ↠ F Q k . For uniformly random z ∈ K z\in\mathbb{K} z ∈ K , define H z ( b ) = P ( z ι ( b ) ) H_z(b)=P(z\iota(b)) H z ( b ) = P ( z ι ( b )) . If b ≠ 0 b\ne0 b = 0 , multiplication by ι ( b ) \iota(b) ι ( b ) is a bijection of K \mathbb{K} K , so H z ( b ) H_z(b) H z ( b ) is uniform.
Controlling the first term
To bound the first term T 0 T_0 T 0 in Theorem 1.1, we impose the following condition on the weight distribution of the dual of the inner code.
Definition 3.3 ([6 Definition 2.2] ). Let 0 < τ < ρ i n < 1 0<\tau<\rho_{\mathrm{in}}<1 0 < τ < ρ in < 1 . A binary [ n 0 , k 0 ] [n_0,k_0] [ n 0 , k 0 ] code C i n ≤ F 2 n 0 C_{\mathrm{in}}\le\mathbb{F}_2^{n_0} C in ≤ F 2 n 0 of rate ρ i n = k 0 / n 0 \rho_{\mathrm{in}}=k_0/n_0 ρ in = k 0 / n 0 is τ \tau τ -nice if
c i : = # { x ∈ C i n ⊥ : wt ( x ) = i } ≤ ( n 0 i ) 2 − n 0 ( ρ i n − τ ) (10) c_i:=\#\{x\in C_{\mathrm{in}}^\perp:\operatorname{wt}(x)=i\}\le\binom{n_0}{i}2^{-n_0(\rho_{\mathrm{in}}-\tau)} \tag*{(10)} c i := # { x ∈ C in ⊥ : wt ( x ) = i } ≤ ( i n 0 ) 2 − n 0 ( ρ in − τ ) (10) for every 1 ≤ i ≤ n 0 1\le i\le n_0 1 ≤ i ≤ n 0 .
A uniformly random binary [ n 0 , k 0 ] [n_0,k_0] [ n 0 , k 0 ] linear code is τ \tau τ -nice with probability at least 1 − n 0 2 − τ n 0 1-n_0 2^{-\tau n_0} 1 − n 0 2 − τ n 0 . Indeed, for every nonzero x ∈ F 2 n 0 x\in\mathbb{F}_2^{n_0} x ∈ F 2 n 0 ,
Pr [ x ∈ C i n ⊥ ] = 2 n 0 − k 0 − 1 2 n 0 − 1 ≤ 2 − k 0 . \Pr[x\in C_{\mathrm{in}}^\perp]=\frac{2^{n_0-k_0}-1}{2^{n_0}-1}\le2^{-k_0}. Pr [ x ∈ C in ⊥ ] = 2 n 0 − 1 2 n 0 − k 0 − 1 ≤ 2 − k 0 .
Hence E [ c i ] ≤ ( n 0 i ) 2 − k 0 \mathbb{E}[c_i]\le\binom{n_0}{i}2^{-k_0} E [ c i ] ≤ ( i n 0 ) 2 − k 0 for 1 ≤ i ≤ n 0 1\le i\le n_0 1 ≤ i ≤ n 0 . Markov’s inequality bounds the probability of violating (3.2) at any fixed weight by 2 − τ n 0 2^{-\tau n_0} 2 − τ n 0 ; a union bound gives the assertion.
Neither the moment identity nor the general probability bound requires (3.2). Condition (3.2) is used only when bounding the term arising from the inner code, starting with Proposition 3.5.
Bounding T 0 T_0 T 0 reduces to estimating the number ∣ Z r ∣ |Z_r| ∣ Z r ∣ of tuples satisfying g V = 0 g_V=0 g V = 0 . We estimate this number using the moment generating function (MGF) of the bias of a uniformly random word of C i n C_{\mathrm{in}} C in .
Let U U U be uniform on F Q \mathbb{F}_Q F Q , and set Y : = bias ( ϕ ( U ) ) Y:=\operatorname{bias}(\phi(U)) Y := bias ( ϕ ( U )) . Its moment generating function is
M C i n ( s ) : = E [ e s Y ] = 1 Q ∑ a ∈ F Q exp ( s bias ( ϕ ( a ) ) ) . (11) M_{C_{\mathrm{in}}}(s):=\mathbb{E}[e^{sY}]=\frac{1}{Q}\sum_{a\in\mathbb{F}_Q}\exp\bigl(s\operatorname{bias}(\phi(a))\bigr). \tag*{(11)} M C in ( s ) := E [ e s Y ] = Q 1 a ∈ F Q ∑ exp ( s bias ( ϕ ( a )) ) . (11)
The function ln M C i n \ln M_{C_{\mathrm{in}}} ln M C in is the cumulant generating function used in the analysis of a fixed inner code and a random outer code by Barg, Justesen, and Thommesen [1 ] , expressed in terms of the bias variable.
Let U 1 , … , U n U_1,\ldots,U_n U 1 , … , U n be independent uniform F Q \mathbb{F}_Q F Q -valued random variables, and set Y i : = bias ( ϕ ( U i ) ) Y_i:=\operatorname{bias}(\phi(U_i)) Y i := bias ( ϕ ( U i )) and S n : = ∑ i = 1 n Y i S_n:=\sum_{i=1}^nY_i S n := ∑ i = 1 n Y i .
Lemma 3.4. For every integer r ≥ 1 r\ge1 r ≥ 1 , we have ∣ Z r ∣ = E [ S n r ] |Z_r|=\mathbb{E}[S_n^r] ∣ Z r ∣ = E [ S n r ] . Consequently, for every even r ≥ 2 r\ge2 r ≥ 2 and every s > 0 s>0 s > 0 ,
∣ Z r ∣ ≤ r ! 2 s r ( M C i n ( s ) n + M C i n ( − s ) n ) . (12) |Z_r|\le\frac{r!}{2s^r}\left(M_{C_{\mathrm{in}}}(s)^n+M_{C_{\mathrm{in}}}(-s)^n\right). \tag*{(12)} ∣ Z r ∣ ≤ 2 s r r ! ( M C in ( s ) n + M C in ( − s ) n ) . (12)
Proof. Using
bias ( ϕ ( U i ) ) = ∑ j = 1 n 0 ( − 1 ) Tr ( ω j U i ) , \operatorname{bias}(\phi(U_i))=\sum_{j=1}^{n_0}(-1)^{\operatorname{Tr}(\omega_jU_i)}, bias ( ϕ ( U i )) = j = 1 ∑ n 0 ( − 1 ) Tr ( ω j U i ) ,
we expand S n r S_n^r S n r over the ordered tuples V = ( ( i 1 , j 1 ) , … , ( i r , j r ) ) ∈ V r V=((i_1,j_1),\ldots,(i_r,j_r))\in\mathcal{V}_r V = (( i 1 , j 1 ) , … , ( i r , j r )) ∈ V r . Independence gives
E [ S n r ] = ∑ V ∈ V r ∏ i = 1 n E U i [ ( − 1 ) Tr ( U i ( g V ) i ) ] . \mathbb{E}[S_n^r]=\sum_{V\in\mathcal{V}_r}\prod_{i=1}^{n}\mathbb{E}_{U_i}\left[(-1)^{\operatorname{Tr}(U_i(g_V)_i)}\right]. E [ S n r ] = V ∈ V r ∑ i = 1 ∏ n E U i [ ( − 1 ) Tr ( U i ( g V ) i ) ] .
By character orthogonality, the product equals one when g V = 0 g_V=0 g V = 0 and zero otherwise. Hence ∣ Z r ∣ = E [ S n r ] |\mathcal{Z}_r|=\mathbb{E}[S_n^r] ∣ Z r ∣ = E [ S n r ] . If r r r is even, then cosh ( s x ) ≥ ( s x ) r / r ! \cosh(sx)\ge(sx)^r/r! cosh ( s x ) ≥ ( s x ) r / r ! for every real x x x , so
E [ S n r ] ≤ r ! s r E [ cosh ( s S n ) ] = r ! 2 s r ( M C i n ( s ) n + M C i n ( − s ) n ) . \mathbb{E}[S_n^r]\le\frac{r!}{s^r}\mathbb{E}[\cosh(sS_n)]=\frac{r!}{2s^r}\left(M_{C_{\mathrm{in}}}(s)^n+M_{C_{\mathrm{in}}}(-s)^n\right). E [ S n r ] ≤ s r r ! E [ cosh ( s S n )] = 2 s r r ! ( M C in ( s ) n + M C in ( − s ) n ) .
Set Δ : = ρ i n − τ > 0 \Delta:=\rho_{\mathrm{in}}-\tau>0 Δ := ρ in − τ > 0 , and for s ≥ 0 s\ge0 s ≥ 0 define
Γ Δ , n 0 ( s ) : = 1 + 2 − n 0 Δ ( ( 1 + tanh s ) n 0 − 1 ) . \Gamma_{\Delta,n_0}(s):=1+2^{-n_0\Delta}\left((1+\tanh s)^{n_0}-1\right). Γ Δ , n 0 ( s ) := 1 + 2 − n 0 Δ ( ( 1 + tanh s ) n 0 − 1 ) .
Proposition 3.5. Suppose that C i n C_{\mathrm{in}} C in has rate ρ i n \rho_{\mathrm{in}} ρ in and is τ \tau τ -nice. For every even r ≥ 2 r\ge2 r ≥ 2 and every s > 0 s>0 s > 0 ,
∣ Z r ∣ ≤ r ! s r ( cosh s ) N Γ Δ , n 0 ( s ) N / n 0 . (13) |\mathcal{Z}_r|\le\frac{r!}{s^r}(\cosh s)^N\Gamma_{\Delta,n_0}(s)^{N/n_0}. \tag*{(13)} ∣ Z r ∣ ≤ s r r ! ( cosh s ) N Γ Δ , n 0 ( s ) N / n 0 . (13)
Proof. We first bound the moment generating function M C i n M_{C_{\mathrm{in}}} M C in in (11) . For s ≥ 0 s\ge0 s ≥ 0 , the binary MacWilliams identity [14 Chapter 5] gives
M C i n ( s ) = ( cosh s ) n 0 ∑ z ∈ C i n ⊥ ( tanh s ) wt ( z ) . (14) M_{C_{\mathrm{in}}}(s)=(\cosh s)^{n_0}\sum_{z\in C_{\mathrm{in}}^\perp}(\tanh s)^{\operatorname{wt}(z)}. \tag*{(14)} M C in ( s ) = ( cosh s ) n 0 z ∈ C in ⊥ ∑ ( tanh s ) wt ( z ) . (14)
Since C i n C_{\mathrm{in}} C in is τ \tau τ -nice, for every j ≥ 1 j\ge1 j ≥ 1 ,
c j = # { z ∈ C i n ⊥ : wt ( z ) = j } ≤ 2 − n 0 Δ ( n 0 j ) . c_j=\#\{z\in C_{\mathrm{in}}^\perp:\operatorname{wt}(z)=j\}\le2^{-n_0\Delta}\binom{n_0}{j}. c j = # { z ∈ C in ⊥ : wt ( z ) = j } ≤ 2 − n 0 Δ ( j n 0 ) .
The binomial theorem therefore yields
∑ z ∈ C i n ⊥ ( tanh s ) wt ( z ) ≤ 1 + 2 − n 0 Δ ( ( 1 + tanh s ) n 0 − 1 ) = Γ Δ , n 0 ( s ) . \sum_{z\in C_{\mathrm{in}}^\perp}(\tanh s)^{\operatorname{wt}(z)}
\le1+2^{-n_0\Delta}\left((1+\tanh s)^{n_0}-1\right)=\Gamma_{\Delta,n_0}(s). z ∈ C in ⊥ ∑ ( tanh s ) wt ( z ) ≤ 1 + 2 − n 0 Δ ( ( 1 + tanh s ) n 0 − 1 ) = Γ Δ , n 0 ( s ) .
For − s -s − s , the expansion contains terms of alternating signs; taking their absolute values gives the same upper bound. Thus M C i n ( ± s ) ≤ ( cosh s ) n 0 Γ Δ , n 0 ( s ) M_{C_{\mathrm{in}}}(\pm s)\le(\cosh s)^{n_0}\Gamma_{\Delta,n_0}(s) M C in ( ± s ) ≤ ( cosh s ) n 0 Γ Δ , n 0 ( s ) . Substitution into Lemma 3.4 gives
∣ Z r ∣ ≤ r ! s r ( cosh s ) N Γ Δ , n 0 ( s ) N / n 0 . |\mathcal{Z}_r|\le\frac{r!}{s^r}(\cosh s)^N\Gamma_{\Delta,n_0}(s)^{N/n_0}. ∣ Z r ∣ ≤ s r r ! ( cosh s ) N Γ Δ , n 0 ( s ) N / n 0 .
We will use the following elementary estimate:
Γ Δ , n 0 ( s ) ≤ 1 + 2 − n 0 Δ ( 1 + tanh s ) n 0 = 1 + exp [ − n 0 ( Δ ln 2 − ln ( 1 + tanh s ) ) ] . (15) \Gamma_{\Delta,n_0}(s)\le1+2^{-n_0\Delta}(1+\tanh s)^{n_0}
=1+\exp\left[-n_0\left(\Delta\ln2-\ln(1+\tanh s)\right)\right]. \tag*{(15)} Γ Δ , n 0 ( s ) ≤ 1 + 2 − n 0 Δ ( 1 + tanh s ) n 0 = 1 + exp [ − n 0 ( Δ ln 2 − ln ( 1 + tanh s ) ) ] . (15)
Writing κ ( s ) : = Δ ln 2 − ln ( 1 + tanh s ) \kappa(s):=\Delta\ln2-\ln(1+\tanh s) κ ( s ) := Δ ln 2 − ln ( 1 + tanh s ) , we have 0 ≤ Γ Δ , n 0 ( s ) − 1 ≤ e − n 0 κ ( s ) 0\le\Gamma_{\Delta,n_0}(s)-1\le e^{-n_0\kappa(s)} 0 ≤ Γ Δ , n 0 ( s ) − 1 ≤ e − n 0 κ ( s ) . Thus, even when the parameters vary, n 0 κ ( s ) → ∞ n_0\kappa(s)\to\infty n 0 κ ( s ) → ∞ implies Γ Δ , n 0 ( s ) → 1 \Gamma_{\Delta,n_0}(s)\to1 Γ Δ , n 0 ( s ) → 1 . If, in addition, κ ( s ) ≥ κ 0 > 0 \kappa(s)\ge\kappa_0>0 κ ( s ) ≥ κ 0 > 0 holds uniformly, then Γ Δ , n 0 ( s ) − 1 \Gamma_{\Delta,n_0}(s)-1 Γ Δ , n 0 ( s ) − 1 is exponentially small in n 0 n_0 n 0 . In the applications at low rates below, we estimate n 0 − 1 ln Γ Δ , n 0 ( s ) n_0^{-1}\ln\Gamma_{\Delta,n_0}(s) n 0 − 1 ln Γ Δ , n 0 ( s ) directly to the required precision.
Since p r ( 0 ) = ∣ Z r ∣ / N r p_r^{(0)} = |Z_r|/N^r p r ( 0 ) = ∣ Z r ∣/ N r , Proposition 3.5 gives the following bound whenever C i n C_{\mathrm{in}} C in is τ \tau τ -nice, s > 0 s > 0 s > 0 , and r ≥ 2 r \ge2 r ≥ 2 is even:
T 0 = Q k β r p r ( 0 ) ≤ T ‾ 0 : = Q k r ! ( β s N ) r ( cosh s ) N Γ Δ , n 0 ( s ) N / n 0 . T_0 = \frac{Q^k}{\beta^r}p_r^{(0)} \le\overline{T}_0 := \frac{Q^k r!}{(\beta sN)^r}(\cosh s)^N\Gamma_{\Delta,n_0}(s)^{N/n_0}. T 0 = β r Q k p r ( 0 ) ≤ T 0 := ( β s N ) r Q k r ! ( cosh s ) N Γ Δ , n 0 ( s ) N / n 0 .
Fix s > 0 s > 0 s > 0 and 0 < β < 1 0 < \beta< 1 0 < β < 1 . For even r r r with r / N → λ > 0 r/N \to\lambda> 0 r / N → λ > 0 , Stirling’s formula gives
1 N ln r ! ( β s N ) r = λ ln λ β s − λ + o N ( 1 ) . \frac{1}{N}\ln\frac{r!}{(\beta sN)^r} = \lambda\ln\frac{\lambda}{\beta s} - \lambda+ o_N(1). N 1 ln ( β s N ) r r ! = λ ln β s λ − λ + o N ( 1 ) .
The limiting expression is minimized at λ = β s \lambda= \beta s λ = β s . The factorial ratio and ( cosh s ) N (\cosh s)^N ( cosh s ) N then contribute ln cosh s − β s \ln\cosh s-\beta s ln cosh s − β s to the limiting exponent. The derivative of this expression is tanh s − β \tanh s-\beta tanh s − β , so we choose
s β : = arctanh ( β ) , λ β : = β s β . (16) s_\beta:= \operatorname{arctanh}(\beta), \qquad\lambda_\beta:= \beta s_\beta. \tag*{(16)} s β := arctanh ( β ) , λ β := β s β . (16)
Define
I ( β ) : = β s β − ln cosh ( s β ) = ln 2 ( 1 − h 2 ( 1 − β 2 ) ) . (17) I(\beta) := \beta s_\beta-\ln\cosh(s_\beta)=\ln2\left(1-h_2\left(\frac{1-\beta}{2}\right)\right). \tag*{(17)} I ( β ) := β s β − ln cosh ( s β ) = ln 2 ( 1 − h 2 ( 2 1 − β ) ) . (17)
This is the rate function for large deviations of a uniform { − 1 , 1 } \{-1,1\} { − 1 , 1 } -valued random variable, and it yields the exponent associated with the GV bound in the analysis at low rates below. Since tanh ( s β ) = β \tanh(s_\beta)=\beta tanh ( s β ) = β , we also have
Γ Δ , n 0 ( s β ) ≤ 1 + exp [ − n 0 ( Δ ln 2 − ln ( 1 + β ) ) ] . (18) \Gamma_{\Delta,n_0}(s_\beta)\le1+\exp\left[-n_0\left(\Delta\ln2-\ln(1+\beta)\right)\right]. \tag*{(18)} Γ Δ , n 0 ( s β ) ≤ 1 + exp [ − n 0 ( Δ ln 2 − ln ( 1 + β ) ) ] . (18)
Thus, at s = s β s=s_\beta s = s β , the factor Γ Δ , n 0 ( s β ) \Gamma_{\Delta,n_0}(s_\beta) Γ Δ , n 0 ( s β ) is determined by the size of n 0 ( Δ ln 2 − ln ( 1 + β ) ) n_0(\Delta\ln2-\ln(1+\beta)) n 0 ( Δ ln 2 − ln ( 1 + β )) . Taking even r = r N r=r_N r = r N with r / N → λ β r/N\to\lambda_\beta r / N → λ β gives
1 N ln T 0 ≤ 1 N ln T ‾ 0 = R ln 2 − I ( β ) + 1 n 0 ln Γ Δ , n 0 ( s β ) + o N ( 1 ) . (19) \frac{1}{N}\ln T_0\le\frac{1}{N}\ln\overline{T}_0=R\ln2-I(\beta)+\frac{1}{n_0}\ln\Gamma_{\Delta,n_0}(s_\beta)+o_N(1). \tag*{(19)} N 1 ln T 0 ≤ N 1 ln T 0 = R ln 2 − I ( β ) + n 0 1 ln Γ Δ , n 0 ( s β ) + o N ( 1 ) . (19)
In particular, T 0 T_0 T 0 decays exponentially in N N N if there is a constant a 0 > 0 a_0>0 a 0 > 0 , independent of N N N , such that
I ( β ) − R ln 2 − 1 n 0 ln Γ Δ , n 0 ( s β ) ≥ a 0 (20) I(\beta)-R\ln2-\frac{1}{n_0}\ln\Gamma_{\Delta,n_0}(s_\beta)\ge a_0 \tag*{(20)} I ( β ) − R ln 2 − n 0 1 ln Γ Δ , n 0 ( s β ) ≥ a 0 (20)
for all sufficiently large N N N .
Controlling the second term
Controlling T A T_A T A
To bound T A T_A T A , fix a tuple V V V with g V ≠ 0 g_V\ne0 g V = 0 . The event g V ∈ A α ⊥ g_V\in A_\alpha^\perp g V ∈ A α ⊥ is equivalent to diag ( α ) g V ∈ A ⊥ \operatorname{diag}(\alpha)g_V\in A^\perp diag ( α ) g V ∈ A ⊥ . Independent scaling makes diag ( α ) g V \operatorname{diag}(\alpha)g_V diag ( α ) g V uniform among vectors with the same support as g V g_V g V . Its probability of belonging to A ⊥ A^\perp A ⊥ is therefore determined by the number of dual codewords with that support.
For a fixed moment order r ≥ 1 r\ge1 r ≥ 1 and a nonempty set S ⊆ [ n ] S\subseteq[n] S ⊆ [ n ] , let
N A ⊥ ( S ) : = # { z ∈ A ⊥ : supp ( z ) = S } , M S : = # { V ∈ V r : supp ( g V ) = S } . N_A^\perp(S):=\#\{z\in A^\perp:\operatorname{supp}(z)=S\},\qquad M_S:=\#\{V\in\mathcal{V}_r:\operatorname{supp}(g_V)=S\}. N A ⊥ ( S ) := # { z ∈ A ⊥ : supp ( z ) = S } , M S := # { V ∈ V r : supp ( g V ) = S } .
For 1 ≤ w ≤ n 1\le w\le n 1 ≤ w ≤ n , define π r ( w ) : = N − r # { V ∈ V r : wt ( g V ) = w } \pi_r(w):=N^{-r}\#\{V\in\mathcal{V}_r:\operatorname{wt}(g_V)=w\} π r ( w ) := N − r # { V ∈ V r : wt ( g V ) = w } and
θ w ( A ) : = 1 ( n w ) ∑ S ⊆ [ n ] ∣ S ∣ = w N A ⊥ ( S ) ( Q − 1 ) w . \theta_w(A):=\frac{1}{\binom{n}{w}}\sum_{\substack{S\subseteq[n]\\|S|=w}}\frac{N_A^\perp(S)}{(Q-1)^w}. θ w ( A ) := ( w n ) 1 S ⊆ [ n ] ∣ S ∣ = w ∑ ( Q − 1 ) w N A ⊥ ( S ) .
The quantity π r ( w ) \pi_r(w) π r ( w ) is the proportion of tuples for which wt ( g V ) = w \operatorname{wt}(g_V)=w wt ( g V ) = w . The quantity θ w ( A ) \theta_w(A) θ w ( A ) is the probability that a uniformly random vector of weight w w w , obtained by first choosing its support uniformly and then choosing each nonzero entry uniformly, belongs to A ⊥ A^\perp A ⊥ .
Set Θ A ( Q ) : = max 1 ≤ w ≤ n θ w ( A ) \Theta_A(Q) := \max_{1 \le w \le n} \theta_w(A) Θ A ( Q ) := max 1 ≤ w ≤ n θ w ( A ) . Writing B w ⊥ : = # { z ∈ A ⊥ : wt ( z ) = w } B_w^\perp:= \#\{z \in A^\perp: \operatorname{wt}(z) = w\} B w ⊥ := # { z ∈ A ⊥ : wt ( z ) = w } and partitioning by support gives
θ w ( A ) = B w ⊥ ( n w ) ( Q − 1 ) w . \theta_w(A) = \frac{B_w^\perp}{\binom{n}{w}(Q-1)^w}. θ w ( A ) = ( w n ) ( Q − 1 ) w B w ⊥ .
Thus, Θ A ( Q ) \Theta_A(Q) Θ A ( Q ) is the maximum over w w w of the proportion θ w ( A ) \theta_w(A) θ w ( A ) of vectors of weight w w w that belong to A ⊥ A^\perp A ⊥ , and is determined by the ordinary weight enumerator. We use the numbers of codewords with prescribed supports to estimate this proportion.
Theorem 3.6. For every integer r ≥ 1 r \ge1 r ≥ 1 ,
L r ( A , C i n ) = ∑ w = 1 n π r ( w ) θ w ( A ) ≤ Θ A ( Q ) . \mathcal{L}_r(A,C_{\mathrm{in}}) = \sum_{w=1}^{n} \pi_r(w)\theta_w(A) \le\Theta_A(Q). L r ( A , C in ) = w = 1 ∑ n π r ( w ) θ w ( A ) ≤ Θ A ( Q ) .
Proof. Fix 0 ≠ g ∈ F Q n 0 \ne g \in\mathbb{F}_Q^n 0 = g ∈ F Q n , and let S = supp ( g ) S = \operatorname{supp}(g) S = supp ( g ) be its support and w = ∣ S ∣ w = |S| w = ∣ S ∣ its weight. For uniformly random α ∈ ( F Q × ) n \alpha\in(\mathbb{F}_Q^\times)^n α ∈ ( F Q × ) n , the vector diag ( α ) g \operatorname{diag}(\alpha)g diag ( α ) g is uniform over the ( Q − 1 ) w (Q-1)^w ( Q − 1 ) w vectors with support exactly S S S . Since diag ( α ) g ∈ A ⊥ \operatorname{diag}(\alpha)g \in A^\perp diag ( α ) g ∈ A ⊥ is equivalent to g ∈ A α ⊥ g \in A_\alpha^\perp g ∈ A α ⊥ , we have
Pr α [ g ∈ A α ⊥ ] = N A ⊥ ( S ) ( Q − 1 ) w . \Pr_\alpha[g \in A_\alpha^\perp] = \frac{N_A^\perp(S)}{(Q-1)^w}. α Pr [ g ∈ A α ⊥ ] = ( Q − 1 ) w N A ⊥ ( S ) .
Summing this identity over V V V gives
E α # { V ∈ V r : g V ≠ 0 , g V ∈ A α ⊥ } = ∑ ∅ ≠ S ⊆ [ n ] M S N A ⊥ ( S ) ( Q − 1 ) ∣ S ∣ . \mathbb{E}_\alpha\#\{V \in\mathcal{V}_r : g_V \ne0,\ g_V \in A_\alpha^\perp\}
=
\sum_{\varnothing\ne S \subseteq[n]} M_S \frac{N_A^\perp(S)}{(Q-1)^{|S|}}. E α # { V ∈ V r : g V = 0 , g V ∈ A α ⊥ } = ∅ = S ⊆ [ n ] ∑ M S ( Q − 1 ) ∣ S ∣ N A ⊥ ( S ) .
For a permutation σ \sigma σ of [ n ] [n] [ n ] and V = ( ( i 1 , j 1 ) , … , ( i r , j r ) ) ∈ V r V = ((i_1,j_1),\ldots,(i_r,j_r)) \in\mathcal{V}_r V = (( i 1 , j 1 ) , … , ( i r , j r )) ∈ V r , define
σ V : = ( ( σ ( i 1 ) , j 1 ) , … , ( σ ( i r ) , j r ) ) . \sigma V := ((\sigma(i_1),j_1),\ldots,(\sigma(i_r),j_r)). σ V := (( σ ( i 1 ) , j 1 ) , … , ( σ ( i r ) , j r )) .
The map V ↦ σ V V \mapsto\sigma V V ↦ σ V is a bijection of V r \mathcal{V}_r V r , and the definition of g V g_V g V gives
( g σ V ) σ ( i ) = ( g V ) i ( i ∈ [ n ] ) , supp ( g σ V ) = σ ( supp ( g V ) ) . (g_{\sigma V})_{\sigma(i)} = (g_V)_i \quad(i \in[n]), \qquad\operatorname{supp}(g_{\sigma V}) = \sigma(\operatorname{supp}(g_V)). ( g σ V ) σ ( i ) = ( g V ) i ( i ∈ [ n ]) , supp ( g σ V ) = σ ( supp ( g V )) .
Thus, the uniform distribution on V r \mathcal{V}_r V r is invariant under permutations of the outer coordinates, and M S M_S M S depends only on ∣ S ∣ |S| ∣ S ∣ . Denote the corresponding value by M w M_w M w . Grouping by w = ∣ S ∣ w = |S| w = ∣ S ∣ yields
L r ( A , C i n ) = 1 N r ∑ w = 1 n M w ∑ S ⊆ [ n ] ∣ S ∣ = w N A ⊥ ( S ) ( Q − 1 ) w . (21) \mathcal{L}_r(A,C_{\mathrm{in}}) = \frac{1}{N^r} \sum_{w=1}^{n} M_w \sum_{\substack{S \subseteq[n]\\ |S|=w}} \frac{N_A^\perp(S)}{(Q-1)^w}. \tag*{(21)} L r ( A , C in ) = N r 1 w = 1 ∑ n M w S ⊆ [ n ] ∣ S ∣ = w ∑ ( Q − 1 ) w N A ⊥ ( S ) . (21)
On the other hand, the definition of π r ( w ) \pi_r(w) π r ( w ) gives
π r ( w ) = 1 N r ∑ S ⊆ [ n ] ∣ S ∣ = w M S = ( n w ) M w N r . \pi_r(w) = \frac{1}{N^r} \sum_{\substack{S \subseteq[n]\\ |S|=w}} M_S = \binom{n}{w}\frac{M_w}{N^r}. π r ( w ) = N r 1 S ⊆ [ n ] ∣ S ∣ = w ∑ M S = ( w n ) N r M w .
Substituting this into (3.13) yields L r ( A , C i n ) = ∑ w = 1 n π r ( w ) θ w ( A ) \mathcal{L}_r(A,C_{\mathrm{in}}) = \sum_{w=1}^{n} \pi_r(w)\theta_w(A) L r ( A , C in ) = ∑ w = 1 n π r ( w ) θ w ( A ) . Since ∑ w = 1 n π r ( w ) \sum_{w=1}^{n} \pi_r(w) ∑ w = 1 n π r ( w ) is the proportion of tuples for which g V ≠ 0 g_V \ne0 g V = 0 , we have ∑ w = 1 n π r ( w ) = 1 − ∣ Z r ∣ / N r ≤ 1 \sum_{w=1}^{n} \pi_r(w) = 1 - |\mathcal{Z}_r|/N^r \le1 ∑ w = 1 n π r ( w ) = 1 − ∣ Z r ∣/ N r ≤ 1 . The final inequality follows from θ w ( A ) ≤ Θ A ( Q ) \theta_w(A) \le\Theta_A(Q) θ w ( A ) ≤ Θ A ( Q ) for every w w w . □ \square □
By nondegeneracy of the trace pairing, ( g V ) i = 0 (g_V)_i = 0 ( g V ) i = 0 if and only if ∑ ℓ : i ℓ = i x j ℓ = 0 \sum_{\ell:i_\ell=i} x_{j_\ell} = 0 ∑ ℓ : i ℓ = i x j ℓ = 0 for every x ∈ C i n x \in C_{\mathrm{in}} x ∈ C in . Thus supp ( g V ) \operatorname{supp}(g_V) supp ( g V ) , and hence both ∣ Z r ∣ |\mathcal{Z}_r| ∣ Z r ∣ and L r ( A , C i n ) \mathcal{L}_r(A,C_{\mathrm{in}}) L r ( A , C in ) by the formula above, are independent of ϕ \phi ϕ .
Proof. The case w < d ⊥ w<d^\perp w < d ⊥ follows from the definition of minimum distance. For w ≥ d ⊥ w\ge d^\perp w ≥ d ⊥ , remove any d ⊥ − 1 d^\perp-1 d ⊥ − 1 coordinates from S S S and let T T T be the remaining set of coordinates. If two dual codewords with support exactly S S S agree on T T T , their difference is supported on at most d ⊥ − 1 d^\perp-1 d ⊥ − 1 coordinates. This difference also belongs to A ⊥ A^\perp A ⊥ , so it is zero by the definition of minimum distance. Projection onto T T T is therefore injective. Each codeword is nonzero in every coordinate of T T T , so there are at most ( Q − 1 ) ∣ T ∣ = ( Q − 1 ) w − d ⊥ + 1 (Q-1)^{|T|}=(Q-1)^{w-d^\perp+1} ( Q − 1 ) ∣ T ∣ = ( Q − 1 ) w − d ⊥ + 1 dual codewords with support S S S . Dividing by ( Q − 1 ) w (Q-1)^w ( Q − 1 ) w and averaging over supports gives θ w ( A ) ≤ ( Q − 1 ) 1 − d ⊥ \theta_w(A)\le(Q-1)^{1-d^\perp} θ w ( A ) ≤ ( Q − 1 ) 1 − d ⊥ . The conclusion follows from the definition of Θ A ( Q ) \Theta_A(Q) Θ A ( Q ) and Theorem 3.6 . □
The bound in Lemma 3.8 is attained by any linear [ n , K ] [n,K] [ n , K ] maximum distance separable (MDS) code A A A with 1 ≤ K < n 1\le K<n 1 ≤ K < n . Such a code satisfies d ( A ) = n − K + 1 d(A)=n-K+1 d ( A ) = n − K + 1 , and A ⊥ A^\perp A ⊥ is MDS with d ( A ⊥ ) = K + 1 d(A^\perp)=K+1 d ( A ⊥ ) = K + 1 . For every S S S of size K + 1 K+1 K + 1 , the shortened dual code A ⊥ ∩ F Q S A^\perp\cap\mathbb{F}_Q^S A ⊥ ∩ F Q S has dimension one, and every nonzero word in it has support S S S . Thus N A ⊥ ( S ) = Q − 1 N_A^\perp(S)=Q-1 N A ⊥ ( S ) = Q − 1 and θ K + 1 ( A ) = ( Q − 1 ) − K \theta_{K+1}(A)=(Q-1)^{-K} θ K + 1 ( A ) = ( Q − 1 ) − K , which gives Θ A ( Q ) = ( Q − 1 ) − K \Theta_A(Q)=(Q-1)^{-K} Θ A ( Q ) = ( Q − 1 ) − K . If K = n K=n K = n , then A ⊥ = { 0 } A^\perp=\{0\} A ⊥ = { 0 } and Θ A ( Q ) = 0 \Theta_A(Q)=0 Θ A ( Q ) = 0 .
We now combine the estimates for the two terms. If A ⊥ ≠ { 0 } A^\perp\ne\{0\} A ⊥ = { 0 } , Lemma 3.8 gives
1 N log 2 T A ≤ R + r N log 2 1 β − ρ i n d ( A ⊥ ) − 1 n log Q ( Q − 1 ) , (22) \frac{1}{N}\log_2 T_A\le R+\frac{r}{N}\log_2\frac{1}{\beta}-\rho_{\mathrm{in}}\frac{d(A^\perp)-1}{n}\log_Q(Q-1), \tag*{(22)} N 1 log 2 T A ≤ R + N r log 2 β 1 − ρ in n d ( A ⊥ ) − 1 log Q ( Q − 1 ) , (22)
with the convention log 2 0 = − ∞ \log_2 0=-\infty log 2 0 = − ∞ .
Under the assumptions of Theorem 1.1 and Proposition 3.5, fix 0 < β < 1 0<\beta<1 0 < β < 1 and choose even integers r = r N r=r_N r = r N with r / N = λ β + o ( 1 ) r/N=\lambda_\beta+o(1) r / N = λ β + o ( 1 ) .
Corollary 3.9 (A sufficient condition using the dual distance). For these choices, suppose that, for constants a 0 , a A > 0 a_0, a_A > 0 a 0 , a A > 0 independent of N N N ,
I ( β ) − R ln 2 − 1 n 0 ln Γ Δ , n 0 ( s β ) ≥ a 0 , I(\beta)-R\ln2-\frac{1}{n_0}\ln\Gamma_{\Delta,n_0}(s\beta)\ge a_0, I ( β ) − R ln 2 − n 0 1 ln Γ Δ , n 0 ( s β ) ≥ a 0 , ρ i n d ( A ⊥ ) − 1 n log Q ( Q − 1 ) − R − r N log 2 1 β ≥ a A (23) \rho_{\mathrm{in}}\frac{d(A^\perp)-1}{n}\log_Q(Q-1)-R-\frac{r}{N}\log_2\frac{1}{\beta}\ge a_A \tag*{(23)} ρ in n d ( A ⊥ ) − 1 log Q ( Q − 1 ) − R − N r log 2 β 1 ≥ a A (23) for all sufficiently large N N N . The second condition is unnecessary when A ⊥ = { 0 } A^\perp=\{0\} A ⊥ = { 0 } . Then there is c > 0 c>0 c > 0 , independent of N N N , such that
Pr α , U [ C ( α , U ) is not β -balanced ] ≤ e − c N \Pr_{\alpha,U}[C(\alpha,U)\text{ is not }\beta\text{-balanced}]\le e^{-cN} α , U Pr [ C ( α , U ) is not β -balanced ] ≤ e − c N for all sufficiently large N N N .
Proof. Equations (19) and (22) make both exponents negative by constants independent of N N N . Apply (3) , absorbing the sum of the two exponential bounds into a smaller exponent constant.
These conditions guide the parameter choices in the next section. The exact weighted sum in Theorem 3.6 may replace the estimate using the dual distance when more information about A ⊥ A^\perp A ⊥ is available. Appendix A gives further bounds obtained by Poissonization. The effect of the allocation of the inner and outer rates is discussed in § 7.2 .
Construction using AG codes
We apply the general bound to AG codes on the GS tower. We first derive the parameter choices from the two exponent conditions. We then construct the AG base codes A A A , scale their coordinates to obtain A α A_\alpha A α , and choose random subcodes of A α A_\alpha A α as the outer codes.
Choice of the inner code and the required dual distance
Fix constants
c 0 > 2 , c A > 2 ( ln 2 ) 3 / 2 . (24) c_0>2,\qquad c_A>\sqrt{2}(\ln2)^{3/2}. \tag*{(24)} c 0 > 2 , c A > 2 ( ln 2 ) 3/2 . (24)
For sufficiently small ε > 0 \varepsilon>0 ε > 0 , our target rate is ε 2 \varepsilon^2 ε 2 and our distance target is
δ ε : = h 2 − 1 ( 1 − ε 2 − ε 4 ) , β ε : = 1 − 2 δ ε . (25) \delta_\varepsilon:=h_2^{-1}(1-\varepsilon^2-\varepsilon^4),\qquad\beta_\varepsilon:=1-2\delta_\varepsilon. \tag*{(25)} δ ε := h 2 − 1 ( 1 − ε 2 − ε 4 ) , β ε := 1 − 2 δ ε . (25)
Thus I ( β ε ) = ( ε 2 + ε 4 ) ln 2 I(\beta_\varepsilon)=(\varepsilon^2+\varepsilon^4)\ln2 I ( β ε ) = ( ε 2 + ε 4 ) ln 2 . The margin above the target rate in the first exponent is ε 4 ln 2 \varepsilon^4\ln2 ε 4 ln 2 . We first let m → ∞ m\to\infty m → ∞ with ε \varepsilon ε fixed, and then let ε → 0 \varepsilon\to0 ε → 0 . The notation o m ( 1 ) o_m(1) o m ( 1 ) and o ε ( 1 ) o_\varepsilon(1) o ε ( 1 ) refers to these respective limits.
To control T 0 T_0 T 0 , choose the target inner rate slightly above log 2 ( 1 + β ε ) + τ \log_2(1+\beta_\varepsilon)+\tau log 2 ( 1 + β ε ) + τ , as suggested by (18) . Here τ \tau τ is the tolerance in the condition on the dual weight distribution in (10) . Taking τ = o ( ε ) \tau=o(\varepsilon) τ = o ( ε ) preserves the leading coefficient of the inner rate, since log 2 ( 1 + β ε ) = Θ ( ε ) \log_2(1+\beta_\varepsilon)=\Theta(\varepsilon) log 2 ( 1 + β ε ) = Θ ( ε ) . For a fixed inner rate, a smaller τ \tau τ strengthens the moment bound, but requires a larger inner block length to make n 0 2 − τ n 0 n_0 2^{-\tau n_0} n 0 2 − τ n 0 small. To see how these requirements fit together, temporarily leave τ \tau τ unspecified and set ρ ˉ i n = log 2 ( 1 + β ε ) + 2 τ \bar{\rho}_{\mathrm{in}}=\log_2(1+\beta_\varepsilon)+2\tau ρ ˉ in = log 2 ( 1 + β ε ) + 2 τ and n 0 = ⌈ c 0 τ − 1 log 2 ( 1 / ε ) ⌉ n_0=\lceil c_0\tau^{-1}\log_2(1/\varepsilon)\rceil n 0 = ⌈ c 0 τ − 1 log 2 ( 1/ ε )⌉ . With the rounding of k 0 k_0 k 0 described below, the sampling estimate and (18) give
n 0 2 − τ n 0 = O ( ε c 0 log ( 1 / ε ) τ ) , 1 n 0 ln Γ ρ i n − τ , n 0 ( s β ε ) = O ( τ ε c 0 log ( 1 / ε ) ) . n_0 2^{-\tau n_0}=O\left(\frac{\varepsilon^{c_0}\log(1/\varepsilon)}{\tau}\right),\qquad
\frac{1}{n_0}\ln\Gamma_{\rho_{\mathrm{in}}-\tau,n_0}(s\beta_\varepsilon)=O\left(\frac{\tau\varepsilon^{c_0}}{\log(1/\varepsilon)}\right). n 0 2 − τ n 0 = O ( τ ε c 0 log ( 1/ ε ) ) , n 0 1 ln Γ ρ in − τ , n 0 ( s β ε ) = O ( log ( 1/ ε ) τ ε c 0 ) .
Making the first quantity tend to zero ensures that a randomly chosen inner code is τ \tau τ -nice with probability tending to one. We require the second to be o ( ε 4 ) o(\varepsilon^4) o ( ε 4 ) to preserve the margin in the exponent of T 0 T_0 T 0 . The choice τ = ε 2 \tau= \varepsilon^2 τ = ε 2 satisfies both requirements for every c 0 > 2 c_0 > 2 c 0 > 2 and also gives τ = o ( ε ) \tau= o(\varepsilon) τ = o ( ε ) . We therefore take
τ : = ε 2 , n 0 : = ⌈ c 0 ε − 2 log 2 ( 1 / ε ) ⌉ , ρ ˉ i n : = log 2 ( 1 + β ε ) + 2 ε 2 . (26) \tau:= \varepsilon^2,\qquad n_0 := \left\lceil c_0\varepsilon^{-2}\log_2(1/\varepsilon)\right\rceil,\qquad\bar{\rho}_{\mathrm{in}} := \log_2(1+\beta_\varepsilon)+2\varepsilon^2. \tag*{(26)} τ := ε 2 , n 0 := ⌈ c 0 ε − 2 log 2 ( 1/ ε ) ⌉ , ρ ˉ in := log 2 ( 1 + β ε ) + 2 ε 2 . (26)
Choose an even integer k 0 k_0 k 0 with ∣ k 0 − ρ ˉ i n n 0 ∣ ≤ 2 \lvert k_0-\bar{\rho}_{\mathrm{in}}n_0\rvert\le2 ∣ k 0 − ρ ˉ in n 0 ∣ ≤ 2 , and set ρ i n : = k 0 / n 0 \rho_{\mathrm{in}} := k_0/n_0 ρ in := k 0 / n 0 and Q : = 2 k 0 Q := 2^{k_0} Q := 2 k 0 . For sufficiently small ε \varepsilon ε , we have 1 ≤ k 0 < n 0 1\le k_0<n_0 1 ≤ k 0 < n 0 . The parity condition makes Q Q Q a square, as required for the GS tower. The factor log 2 ( 1 / ε ) \log_2(1/\varepsilon) log 2 ( 1/ ε ) in n 0 n_0 n 0 makes the probability of failing the τ \tau τ -nice condition tend to zero:
n 0 2 − τ n 0 = O ( ε c 0 − 2 log ( 1 / ε ) ) = o ε ( 1 ) . (27) n_0 2^{-\tau n_0}=O\left(\varepsilon^{c_0-2}\log(1/\varepsilon)\right)=o_\varepsilon(1). \tag*{(27)} n 0 2 − τ n 0 = O ( ε c 0 − 2 log ( 1/ ε ) ) = o ε ( 1 ) . (27)
Hence a τ \tau τ -nice inner code exists for every sufficiently small ε \varepsilon ε . Fix any such code C i n C_{\mathrm{in}} C in and any F 2 \mathbb{F}_2 F 2 -linear isomorphism ϕ : F Q → C i n \phi:\mathbb{F}_Q\to C_{\mathrm{in}} ϕ : F Q → C in .
We will choose the outer dimension using the actual rate ρ i n \rho_{\mathrm{in}} ρ in so that the binary rate never exceeds ε 2 \varepsilon^2 ε 2 . This avoids a positive error from rounding k 0 k_0 k 0 in the rate term of (19) . The remaining correction n 0 − 1 ln Γ n_0^{-1}\ln\Gamma n 0 − 1 ln Γ is O ( ε c 0 + 2 / log ( 1 / ε ) ) = o ε ( ε 4 ) O(\varepsilon^{c_0+2}/\log(1/\varepsilon))=o_\varepsilon(\varepsilon^4) O ( ε c 0 + 2 / log ( 1/ ε )) = o ε ( ε 4 ) , as proved in Lemma 4.2.
For the second term, take r / N = λ β ε + o N ( 1 ) r/N=\lambda\beta_\varepsilon+o_N(1) r / N = λ β ε + o N ( 1 ) . The entropy expansion and (26) give
β ε = 2 ln 2 ε + O ( ε 3 ) , ρ i n = 2 ln 2 ε + O ( ε 2 ) , λ β ε = 2 ln 2 ε 2 + O ( ε 4 ) . \beta_\varepsilon=\sqrt{2\ln2}\,\varepsilon+O(\varepsilon^3),\qquad\rho_{\mathrm{in}}=\sqrt{\frac{2}{\ln2}}\,\varepsilon+O(\varepsilon^2),\qquad\lambda\beta_\varepsilon=2\ln2\,\varepsilon^2+O(\varepsilon^4). β ε = 2 ln 2 ε + O ( ε 3 ) , ρ in = ln 2 2 ε + O ( ε 2 ) , λ β ε = 2 ln 2 ε 2 + O ( ε 4 ) .
The positive contribution ( r / N ) log 2 ( 1 / β ε ) (r/N)\log_2(1/\beta_\varepsilon) ( r / N ) log 2 ( 1/ β ε ) in (22) therefore has order ε 2 log 2 ( 1 / ε ) \varepsilon^2\log_2(1/\varepsilon) ε 2 log 2 ( 1/ ε ) . Since ρ i n \rho_{\mathrm{in}} ρ in has order ε \varepsilon ε , a relative dual distance of order ε log 2 ( 1 / ε ) \varepsilon\log_2(1/\varepsilon) ε log 2 ( 1/ ε ) can offset this contribution. We will realize it with AG base codes whose limiting rate is
R A : = c A ε log 2 ( 1 / ε ) . (28) R_A:=c_A\varepsilon\log_2(1/\varepsilon). \tag*{(28)} R A := c A ε log 2 ( 1/ ε ) . (28)
The condition on c A c_A c A in (24) makes 2 ln 2 − c A 2 / ln 2 2\ln2-c_A\sqrt{2/\ln2} 2 ln 2 − c A 2/ ln 2 negative. The genus term in the dual distance will be negligible for our choice of Q Q Q .
AG evaluation codes and the GS tower
Definition 4.1 ([16 Chapter 2, Sections 2 and 4] ). Let X / F Q X/\mathbb{F}_Q X / F Q be a smooth projective geometrically irreducible curve of genus g g g . Let D = P 1 + ⋯ + P n D=P_1+\cdots+P_n D = P 1 + ⋯ + P n be a sum of distinct F Q \mathbb{F}_Q F Q -rational points, and let G G G be an F Q \mathbb{F}_Q F Q -rational divisor whose support is disjoint from that of D D D , with deg G = μ < n \deg G=\mu<n deg G = μ < n . Set
L ( G ) : = { f ∈ F Q ( X ) : div ( f ) + G ≥ 0 } ∪ { 0 } . L(G):=\{f\in\mathbb{F}_Q(X):\operatorname{div}(f)+G\ge0\}\cup\{0\}. L ( G ) := { f ∈ F Q ( X ) : div ( f ) + G ≥ 0 } ∪ { 0 } . The associated AG evaluation code is defined by
C L ( D , G ) : = { ( f ( P 1 ) , … , f ( P n ) ) : f ∈ L ( G ) } . C_L(D,G):=\{(f(P_1),\ldots,f(P_n)):f\in L(G)\}. C L ( D , G ) := {( f ( P 1 ) , … , f ( P n )) : f ∈ L ( G )} .
Write A : = C L ( D , G ) A:=C_L(D,G) A := C L ( D , G ) for the base code/ The resulting code satisfies d ( A ) ≥ n − μ d(A)\ge n-\mu d ( A ) ≥ n − μ . If μ ≥ 2 g − 1 \mu\ge2g-1 μ ≥ 2 g − 1 , the Riemann–Roch theorem gives K = dim A = μ + 1 − g K=\dim A=\mu+1-g K = dim A = μ + 1 − g [16 Section 1.5] . For 2 g − 1 ≤ μ < n 2g-1\le\mu<n 2 g − 1 ≤ μ < n , the standard dual distance bound for AG codes gives d ( A ⊥ ) ≥ d 0 : = μ − 2 g + 2 d(A^\perp)\ge d_0:=\mu-2g+2 d ( A ⊥ ) ≥ d 0 := μ − 2 g + 2 [16 Chapter 2] . By Lemma 3.8 and Theorem 3.6, it follows that
L r ( A , C i n ) ≤ Θ A ( Q ) ≤ ( Q − 1 ) 1 − d 0 , T A ≤ Q k β r ( Q − 1 ) 1 − d 0 . L_r(A,C_{\mathrm{in}})\le\Theta_A(Q)\le(Q-1)^{1-d_0},\qquad T_A\le\frac{Q^k}{\beta^r}(Q-1)^{1-d_0}. L r ( A , C in ) ≤ Θ A ( Q ) ≤ ( Q − 1 ) 1 − d 0 , T A ≤ β r Q k ( Q − 1 ) 1 − d 0 .
Thus the degree of G G G and the genus of the curve directly control T A T_A T A .
The GS tower. Let Q = q 2 Q=q^2 Q = q 2 be a square prime power. We use the second GS tower [9 ] , whose function fields are defined by
F 1 = F Q ( x 1 ) , F m + 1 = F m ( x m + 1 ) , x m + 1 q + x m + 1 = x m q x m q − 1 + 1 . F_1=\mathbb{F}_Q(x_1),\qquad F_{m+1}=F_m(x_{m+1}),\qquad x_{m+1}^q+x_{m+1}=\frac{x_m^q}{x_m^{q-1}+1}. F 1 = F Q ( x 1 ) , F m + 1 = F m ( x m + 1 ) , x m + 1 q + x m + 1 = x m q − 1 + 1 x m q .
Let X m \mathcal{X}_m X m be the smooth projective curve with function field F m F_m F m and genus g m g_m g m . We identify its closed points with the places of F m F_m F m . Write P ∞ , m P_{\infty,m} P ∞ , m for the unique point above the pole of x 1 x_1 x 1 . Shum et al. used this tower to compute bases of Riemann–Roch spaces [15 ] . For every a ∈ F Q a \in\mathbb{F}_Q a ∈ F Q with a q + a ≠ 0 a^q+a \ne0 a q + a = 0 , the rational place x 1 = a x_1=a x 1 = a of F 1 F_1 F 1 splits completely in F m F_m F m . We take all the points above these q 2 − q q^2-q q 2 − q places as evaluation points P 1 , m , … , P n m , m P_{1,m},\ldots,P_{n_m,m} P 1 , m , … , P n m , m , so n m = ( q 2 − q ) q m − 1 n_m=(q^2-q)q^{m-1} n m = ( q 2 − q ) q m − 1 . These evaluation points yield the optimal asymptotic ratio [9 , 15 ] :
g m n m = γ Q + o m ( 1 ) , γ Q : = 1 Q − 1 . \frac{g_m}{n_m}=\gamma_Q+o_m(1),\qquad\gamma_Q:=\frac{1}{\sqrt{Q}-1}. n m g m = γ Q + o m ( 1 ) , γ Q := Q − 1 1 .
For a target rate R A R_A R A of the AG base code satisfying γ Q < R A < 1 − γ Q \gamma_Q<R_A<1-\gamma_Q γ Q < R A < 1 − γ Q , set μ m : = ⌊ R A n m + g m − 1 ⌋ \mu_m:=\lfloor R_A n_m+g_m-1\rfloor μ m := ⌊ R A n m + g m − 1 ⌋ , G m : = μ m P ∞ , m G_m:=\mu_mP_{\infty,m} G m := μ m P ∞ , m , D m : = P 1 , m + ⋯ + P n m , m D_m:=P_{1,m}+\cdots+P_{n_m,m} D m := P 1 , m + ⋯ + P n m , m , and A m : = C L ( D m , G m ) A_m:=C_L(D_m,G_m) A m := C L ( D m , G m ) . Also let K m : = dim F Q A m K_m:=\dim_{\mathbb{F}_Q}A_m K m := dim F Q A m and d 0 , m : = μ m − 2 g m + 2 d_{0,m}:=\mu_m-2g_m+2 d 0 , m := μ m − 2 g m + 2 . In the notation of Theorem 1.1 , we take A = A m A=A_m A = A m . For all sufficiently large m m m , we have 2 g m − 1 ≤ μ m < n m 2g_m-1\le\mu_m<n_m 2 g m − 1 ≤ μ m < n m , and the Riemann–Roch theorem together with g m / n m = γ Q + o m ( 1 ) g_m/n_m=\gamma_Q+o_m(1) g m / n m = γ Q + o m ( 1 ) gives
K m n m = R A + o m ( 1 ) , d 0 , m n m = R A − γ Q + o m ( 1 ) . (29) \frac{K_m}{n_m}=R_A+o_m(1),\qquad\frac{d_{0,m}}{n_m}=R_A-\gamma_Q+o_m(1). \tag*{(29)} n m K m = R A + o m ( 1 ) , n m d 0 , m = R A − γ Q + o m ( 1 ) . (29)
In this range, g m ∈ Z g_m\in\mathbb{Z} g m ∈ Z implies μ m = ⌊ R A n m ⌋ + g m − 1 \mu_m=\lfloor R_A n_m\rfloor+g_m-1 μ m = ⌊ R A n m ⌋ + g m − 1 , and the equality K m = μ m + 1 − g m = ⌊ R A n m ⌋ K_m=\mu_m+1-g_m=\lfloor R_A n_m\rfloor K m = μ m + 1 − g m = ⌊ R A n m ⌋ holds exactly. Thus, R A R_A R A is the limiting rate of the AG code A m A_m A m .
For each m m m , fix an F Q \mathbb{F}_Q F Q -linear isomorphism E A m : F Q K m → A m E_{A_m}:\mathbb{F}_Q^{K_m}\to A_m E A m : F Q K m → A m for encoding. Specifically, construct a basis of L ( μ m P ∞ , m ) L(\mu_mP_{\infty,m}) L ( μ m P ∞ , m ) using the method of [15 ] , and use its evaluation vectors at the points specified above as the rows of a generator matrix. For fixed Q Q Q , this isomorphism E A m E_{A_m} E A m can be computed from the defining equations of the tower in polynomial time.
The outer subcode and the distance theorem
Use the GS base code A m A_m A m with R A R_A R A given by (28) . Here k 0 = Θ ( ε − 1 log ( 1 / ε ) ) k_0=\Theta(\varepsilon^{-1}\log(1/\varepsilon)) k 0 = Θ ( ε − 1 log ( 1/ ε )) , so γ Q = o ε ( R A ) \gamma_Q=o_\varepsilon(R_A) γ Q = o ε ( R A ) and γ Q < R A < 1 − γ Q \gamma_Q<R_A<1-\gamma_Q γ Q < R A < 1 − γ Q for sufficiently small ε \varepsilon ε . To obtain binary rate tending to ε 2 \varepsilon^2 ε 2 , set
k m : = ⌊ ε 2 n m ρ i n ⌋ , N m : = n m n 0 . (30) k_m:=\left\lfloor\frac{\varepsilon^2n_m}{\rho_{\mathrm{in}}}\right\rfloor,\qquad N_m:=n_mn_0. \tag*{(30)} k m := ⌊ ρ in ε 2 n m ⌋ , N m := n m n 0 . (30)
Since ε 2 / ρ i n = Θ ( ε ) \varepsilon^2/\rho_{\mathrm{in}}=\Theta(\varepsilon) ε 2 / ρ in = Θ ( ε ) and R A / ( ε 2 / ρ i n ) → ∞ R_A/(\varepsilon^2/\rho_{\mathrm{in}})\to\infty R A / ( ε 2 / ρ in ) → ∞ as ε → 0 \varepsilon\to0 ε → 0 , we have 1 ≤ k m ≤ K m 1\le k_m\le K_m 1 ≤ k m ≤ K m for each sufficiently small ε \varepsilon ε and all sufficiently large m m m . The binary rate satisfies the exact bound
R m : = ρ i n k m n m , 0 ≤ ε 2 − R m < ρ i n n m = k 0 N m . (31) R_m:=\rho_{\mathrm{in}}\frac{k_m}{n_m},\qquad0\le\varepsilon^2-R_m<\frac{\rho_{\mathrm{in}}}{n_m}=\frac{k_0}{N_m}. \tag*{(31)} R m := ρ in n m k m , 0 ≤ ε 2 − R m < n m ρ in = N m k 0 . (31)
In particular, R m → ε 2 R_m\to\varepsilon^2 R m → ε 2 as m → ∞ m\to\infty m → ∞ for fixed ε \varepsilon ε . Let r m ≥ 2 r_m\ge2 r m ≥ 2 be an even integer nearest to λ β ε N m \lambda_{\beta_\varepsilon}N_m λ β ε N m .
Choose a random k m k_m k m -dimensional subspace U m ≤ F Q K m U_m\le\mathbb{F}_Q^{K_m} U m ≤ F Q K m from any distribution satisfying (1.1), and independently choose α m \alpha_m α m uniformly from ( F Q × ) n m (\mathbb{F}_Q^\times)^{n_m} ( F Q × ) n m . Define
A m , α m : = diag ( α m ) A m , A_{m,\alpha_m}:=\operatorname{diag}(\alpha_m)A_m, A m , α m := diag ( α m ) A m ,
C o u t , m ( α m , U m ) : = diag ( α m ) E A m ( U m ) ⊆ A m , α m , C_{\mathrm{out},m}(\alpha_m,U_m):=\operatorname{diag}(\alpha_m)E_{A_m}(U_m)\subseteq A_{m,\alpha_m}, C out , m ( α m , U m ) := diag ( α m ) E A m ( U m ) ⊆ A m , α m ,
C m ( α m , U m ) : = C o u t , m ( α m , U m ) ∘ ϕ C i n . (32) C_m(\alpha_m,U_m):=C_{\mathrm{out},m}(\alpha_m,U_m)\circ\phi\ C_{\mathrm{in}}. \tag*{(32)} C m ( α m , U m ) := C out , m ( α m , U m ) ∘ ϕ C in . (32)
Thus A m A_m A m is the fixed base code, A m , α m A_{m,\alpha_m} A m , α m is the scaled base code, and C o u t , m ( α m , U m ) C_{\mathrm{out},m}(\alpha_m,U_m) C out , m ( α m , U m ) is the selected outer code. The distance analysis requires only (1.1). The constructions in Example 3.2 also give short descriptions and efficient encoding, as discussed in Section 5.
The constants and remainder bounds are uniform over the admissible inner codes and encoding maps. The limit in m m m is taken with ε \varepsilon ε fixed.
Lemma 4.2. For the preceding parameter choices,
1 N m ln T 0 ≤ − ε 4 ln 2 + O ( ε c 0 + 2 log ( 1 / ε ) ) + o m ( 1 ) , (33) \frac{1}{N_m}\ln T_0\le-\varepsilon^4\ln2+O\left(\frac{\varepsilon^{c_0+2}}{\log(1/\varepsilon)}\right)+o_m(1), \tag*{(33)} N m 1 ln T 0 ≤ − ε 4 ln 2 + O ( log ( 1/ ε ) ε c 0 + 2 ) + o m ( 1 ) , (33) 1 N m log 2 T A ≤ ε 2 log 2 ( 1 / ε ) [ 2 ln 2 − c A 2 ln 2 + o ε ( 1 ) ] + O ( ε 2 ) + o m ( 1 ) . (34) \frac{1}{N_m}\log_2 T_A\le\varepsilon^2\log_2(1/\varepsilon)\left[2\ln2-c_A\sqrt{\frac{2}{\ln2}}+o_\varepsilon(1)\right]+O(\varepsilon^2)+o_m(1). \tag*{(34)} N m 1 log 2 T A ≤ ε 2 log 2 ( 1/ ε ) [ 2 ln 2 − c A ln 2 2 + o ε ( 1 ) ] + O ( ε 2 ) + o m ( 1 ) . (34)
Proof. Write e ε : = ρ i n − ρ ˉ i n e_\varepsilon:=\rho_{\mathrm{in}}-\bar{\rho}_{\mathrm{in}} e ε := ρ in − ρ ˉ in , so ∣ e ε ∣ ≤ 2 / n 0 |e_\varepsilon|\le2/n_0 ∣ e ε ∣ ≤ 2/ n 0 . The inner parameters give
( ρ i n − τ ) ln 2 − ln ( 1 + β ε ) = ( ε 2 + e ε ) ln 2 , (\rho_{\mathrm{in}}-\tau)\ln2-\ln(1+\beta_\varepsilon)=(\varepsilon^2+e_\varepsilon)\ln2, ( ρ in − τ ) ln 2 − ln ( 1 + β ε ) = ( ε 2 + e ε ) ln 2 ,
n 0 ( ε 2 + e ε ) ln 2 ≥ c 0 ln ( 1 / ε ) − 2 ln 2. n_0(\varepsilon^2+e_\varepsilon)\ln2\ge c_0\ln(1/\varepsilon)-2\ln2. n 0 ( ε 2 + e ε ) ln 2 ≥ c 0 ln ( 1/ ε ) − 2 ln 2.
Hence (18) implies
Γ ρ i n − τ , n 0 ( s β ε ) − 1 ≤ 4 ε c 0 , 1 n 0 ln Γ ρ i n − τ , n 0 ( s β ε ) = O ( ε c 0 + 2 log ( 1 / ε ) ) . (35) \Gamma_{\rho_{\mathrm{in}}-\tau,n_0}(s_{\beta_\varepsilon})-1\le4\varepsilon^{c_0},
\qquad
\frac{1}{n_0}\ln\Gamma_{\rho_{\mathrm{in}}-\tau,n_0}(s_{\beta_\varepsilon})=O\left(\frac{\varepsilon^{c_0+2}}{\log(1/\varepsilon)}\right). \tag*{(35)} Γ ρ in − τ , n 0 ( s β ε ) − 1 ≤ 4 ε c 0 , n 0 1 ln Γ ρ in − τ , n 0 ( s β ε ) = O ( log ( 1/ ε ) ε c 0 + 2 ) . (35)
Since R m ≤ ε 2 R_m\le\varepsilon^2 R m ≤ ε 2 and I ( β ε ) = ( ε 2 + ε 4 ) ln 2 I(\beta_\varepsilon)=(\varepsilon^2+\varepsilon^4)\ln2 I ( β ε ) = ( ε 2 + ε 4 ) ln 2 , substitution into (19) proves (33) . The error from rounding r m r_m r m and from Stirling’s formula tends to zero as m → ∞ m\to\infty m → ∞ .
For the second term, (22) and (29) give
1 N m log 2 T A ≤ R m + r m N m log 2 1 β ε − ρ i n ( R A − γ Q + o m ( 1 ) ) log Q ( Q − 1 ) . \frac{1}{N_m}\log_2 T_A\le R_m+\frac{r_m}{N_m}\log_2\frac{1}{\beta_\varepsilon}-\rho_{\mathrm{in}}(R_A-\gamma_Q+o_m(1))\log_Q(Q-1). N m 1 log 2 T A ≤ R m + N m r m log 2 β ε 1 − ρ in ( R A − γ Q + o m ( 1 )) log Q ( Q − 1 ) .
We have
β ε = 2 ln 2 ε + O ( ε 3 ) , \beta_\varepsilon=\sqrt{2\ln2}\,\varepsilon+O(\varepsilon^3), β ε = 2 ln 2 ε + O ( ε 3 ) ,
ρ i n = 2 ln 2 ε + O ( ε 2 ) , \rho_{\mathrm{in}}=\sqrt{\frac{2}{\ln2}}\,\varepsilon+O(\varepsilon^2), ρ in = ln 2 2 ε + O ( ε 2 ) ,
r m N m = 2 ln 2 ε 2 + O ( ε 4 ) + o m ( 1 ) . \frac{r_m}{N_m}=2\ln2\,\varepsilon^2+O(\varepsilon^4)+o_m(1). N m r m = 2 ln 2 ε 2 + O ( ε 4 ) + o m ( 1 ) .
Also, γ Q = o ε ( R A ) \gamma_Q=o_\varepsilon(R_A) γ Q = o ε ( R A ) and log Q ( Q − 1 ) = 1 − o ε ( 1 ) \log_Q(Q-1)=1-o_\varepsilon(1) log Q ( Q − 1 ) = 1 − o ε ( 1 ) . Substitute these estimates and R A = c A ε log 2 ( 1 / ε ) R_A=c_A\varepsilon\log_2(1/\varepsilon) R A = c A ε log 2 ( 1/ ε ) to obtain (34) . The bounds use the inner code only through its parameters and the τ \tau τ -nice condition. □ \square □
For the following theorem, use the parameters and construction in Sections 4.1 and 4.3, with c 0 , c A c_0,c_A c 0 , c A satisfying (24) . For each sufficiently small ε > 0 \varepsilon>0 ε > 0 , fix any τ \tau τ -nice inner code and any associated encoding isomorphism. The probability is over ( α m , U m ) (\alpha_m,U_m) ( α m , U m ) .
Theorem 4.3 (Distance guarantee for the GS construction). There are constants ε 0 , c > 0 \varepsilon_0,c>0 ε 0 , c > 0 , independent of ε \varepsilon ε , m m m , and the chosen inner code and encoding map, such that the following holds. For every 0 < ε < ε 0 0<\varepsilon<\varepsilon_0 0 < ε < ε 0 and all sufficiently large m m m , depending on ε \varepsilon ε , the binary rate satisfies (31) , and
Pr α m , U m [ C m is β ε -balanced ] ≥ 1 − 2 − c ε 4 N m . (36) \Pr_{\alpha_m,U_m}[C_m\text{ is }\beta_\varepsilon\text{-balanced}]\ge1-2^{-c\varepsilon^4N_m}. \tag*{(36)} α m , U m Pr [ C m is β ε -balanced ] ≥ 1 − 2 − c ε 4 N m . (36)
Proof. The choice of c A c_A c A makes the leading coefficient in (34) strictly negative. Thus, for some c 1 > 0 c_1>0 c 1 > 0 and sufficiently small ε \varepsilon ε and large m m m ,
T A ≤ 2 − c 1 ε 2 log 2 ( 1 / ε ) N m . T_A \le2^{-c_1\varepsilon^2\log_2(1/\varepsilon)N_m}. T A ≤ 2 − c 1 ε 2 l o g 2 ( 1/ ε ) N m .
Since c 0 > 2 c_0>2 c 0 > 2 , the error in (33) is o ε ( ε 4 ) o_\varepsilon(\varepsilon^4) o ε ( ε 4 ) . Taking m m m sufficiently large after fixing ε \varepsilon ε gives T 0 ≤ 2 − c 2 ε 4 N m T_0\le2^{-c_2\varepsilon^4N_m} T 0 ≤ 2 − c 2 ε 4 N m for some c 2 > 0 c_2>0 c 2 > 0 . Apply (3) and decrease the exponent constant to absorb the sum of the two terms. Thus C m C_m C m is β ε \beta_\varepsilon β ε -balanced with the stated probability. □
For the explicit distance bound, use
1 − h 2 ( ( 1 − β ) / 2 ) ≥ β 2 2 ln 2 ( 0 ≤ β < 1 ) . 1-h_2((1-\beta)/2)\ge\frac{\beta^2}{2\ln2}\qquad(0\le\beta<1). 1 − h 2 (( 1 − β ) /2 ) ≥ 2 ln 2 β 2 ( 0 ≤ β < 1 ) .
The function on the left has value and derivative zero at β = 0 \beta=0 β = 0 , and its second derivative is 1 / ( ( 1 − β 2 ) ln 2 ) ≥ 1 / ln 2 1/((1-\beta^2)\ln2)\ge1/\ln2 1/ (( 1 − β 2 ) ln 2 ) ≥ 1/ ln 2 . Together with (25) , this gives
β ε 2 ≤ ln 2 2 ε 1 + ε 2 ≤ ln 2 2 ( ε + ε 3 2 ) . \frac{\beta_\varepsilon}{2}\le\sqrt{\frac{\ln2}{2}}\varepsilon\sqrt{1+\varepsilon^2}\le\sqrt{\frac{\ln2}{2}}\left(\varepsilon+\frac{\varepsilon^3}{2}\right). 2 β ε ≤ 2 ln 2 ε 1 + ε 2 ≤ 2 ln 2 ( ε + 2 ε 3 ) .
Hence, the distance target also gives the explicit lower bound
δ ( C m ) ≥ δ ε ≥ 1 2 − ln 2 2 ( ε + ε 3 2 ) (37) \delta(C_m)\ge\delta_\varepsilon\ge\frac{1}{2}-\sqrt{\frac{\ln2}{2}}\left(\varepsilon+\frac{\varepsilon^3}{2}\right) \tag*{(37)} δ ( C m ) ≥ δ ε ≥ 2 1 − 2 ln 2 ( ε + 2 ε 3 ) (37)
on the event in (36) . If the inner code is also sampled independently, the total failure probability is at most n 0 2 − τ n 0 + 2 − c ε 4 N m n_0 2^{-\tau n_0}+2^{-c\varepsilon^4N_m} n 0 2 − τ n 0 + 2 − c ε 4 N m . The first term tends to zero as ε → 0 \varepsilon\to0 ε → 0 ; the exponential estimate in N m N_m N m applies after fixing a τ \tau τ -nice inner code. Equation (31) and the distance bound prove Theorem 1.2.
A simultaneous guarantee for the inner encoding maps
The constant in Theorem 4.3 is independent of the chosen inner code and encoding map. Since n 0 n_0 n 0 and k 0 k_0 k 0 remain fixed as m → ∞ m\to\infty m → ∞ , a finite union bound gives an outer code that works for all maps with τ \tau τ -nice images.
Under the assumptions of Theorem 4.3, let F ε \mathcal{F}_\varepsilon F ε be the set of injective F 2 \mathbb{F}_2 F 2 -linear maps φ : F Q → F 2 n 0 \varphi:\mathbb{F}_Q\to\mathbb{F}_2^{n_0} φ : F Q → F 2 n 0 with τ \tau τ -nice images. Write
C m φ ( α m , U m ) : = C o u t , m ( α m , U m ) ∘ φ ( F Q ) . C_m^\varphi(\alpha_m,U_m):=C_{\mathrm{out},m}(\alpha_m,U_m)\circ\varphi(\mathbb{F}_Q). C m φ ( α m , U m ) := C out , m ( α m , U m ) ∘ φ ( F Q ) .
Corollary 4.4. For all sufficiently large m m m ,
Pr α m , U m [ ∃ φ ∈ F ε : C m φ ( α m , U m ) is not β ε -balanced ] ≤ 2 n 0 k 0 − c ε 4 N m . (38) \Pr_{\alpha_m,U_m}\left[\exists\varphi\in\mathcal{F}_\varepsilon:C_m^\varphi(\alpha_m,U_m)\text{ is not }\beta_\varepsilon\text{-balanced}\right]\le2^{n_0k_0-c\varepsilon^4N_m}. \tag*{(38)} α m , U m Pr [ ∃ φ ∈ F ε : C m φ ( α m , U m ) is not β ε -balanced ] ≤ 2 n 0 k 0 − c ε 4 N m . (38)
Consequently, for each sufficiently large m m m one can fix a seed ( α m ∗ , U m ∗ ) (\alpha_m^*,U_m^*) ( α m ∗ , U m ∗ ) , depending on ε \varepsilon ε and m m m , for which C m φ ( α m ∗ , U m ∗ ) C_m^\varphi(\alpha_m^*,U_m^*) C m φ ( α m ∗ , U m ∗ ) is β ε \beta_\varepsilon β ε -balanced for every φ ∈ F ε \varphi\in\mathcal{F}_\varepsilon φ ∈ F ε . For this fixed outer code, a uniformly random injective F 2 \mathbb{F}_2 F 2 -linear map φ : F Q → F 2 n 0 \varphi:\mathbb{F}_Q\to\mathbb{F}_2^{n_0} φ : F Q → F 2 n 0 satisfies
Pr φ [ δ ( C m φ ( α m ∗ , U m ∗ ) ) < δ ε ] ≤ n 0 2 − τ n 0 . \Pr_\varphi\left[\delta(C_m^\varphi(\alpha_m^*,U_m^*))<\delta_\varepsilon\right]\le n_0 2^{-\tau n_0}. φ Pr [ δ ( C m φ ( α m ∗ , U m ∗ )) < δ ε ] ≤ n 0 2 − τ n 0 .
This upper bound tends to zero as ε → 0 \varepsilon\to0 ε → 0 .
Proof. There are at most 2 n 0 k 0 2^{n_0k_0} 2 n 0 k 0 binary linear maps from F Q \mathbb{F}_Q F Q to F 2 n 0 \mathbb{F}_2^{n_0} F 2 n 0 . Apply (36) to each φ ∈ F ε \varphi\in\mathcal{F}_\varepsilon φ ∈ F ε and take a union bound. For fixed ε \varepsilon ε , the resulting upper bound tends to zero as m → ∞ m\to\infty m → ∞ , proving the existence assertion. The image of a uniformly random injective map is a uniformly random binary [ n 0 , k 0 ] [n_0,k_0] [ n 0 , k 0 ] code. Its probability of failing to be τ \tau τ -nice is at most n 0 2 − τ n 0 n_0 2^{-\tau n_0} n 0 2 − τ n 0 by (27) . Every map whose image is τ \tau τ -nice succeeds for the chosen outer code, which proves the last assertion. □
Algorithmic properties of the construction
We estimate the randomness required by the construction in § 5 and describe its encoding and decoding algorithms. The distance theorem allows any distribution satisfying (1.1); the complexity statements below use the constructions in Example 3.2, or more generally subspaces with bases that can be computed in polynomial time.
Randomness
In the construction using Toeplitz matrices, the seed consists of the matrix defining U Z U_Z U Z and the coordinate scalings α ∈ ( F Q × ) n \boldsymbol{\alpha} \in(\mathbb{F}_Q^{\times})^n α ∈ ( F Q × ) n . Let S s e e d S_{\mathrm{seed}} S seed denote its Shannon entropy in bits. If s 0 : = K − k > 0 s_0 := K-k>0 s 0 := K − k > 0 , the matrix is determined by K − 1 K-1 K − 1 independent uniform elements of F Q \mathbb{F}_Q F Q ; if s 0 = 0 s_0=0 s 0 = 0 , the subspace is deterministic. Thus,
S s e e d N = ρ i n ( log Q ( Q − 1 ) + 1 [ s 0 > 0 ] K − 1 n ) . (39) \frac{S_{\mathrm{seed}}}{N}=\rho_{\mathrm{in}}\left(\log_Q(Q-1)+\mathbb{1}[s_0>0]\frac{K-1}{n}\right). \tag*{(39)} N S seed = ρ in ( log Q ( Q − 1 ) + 1 [ s 0 > 0 ] n K − 1 ) . (39)
Representing each field element by k 0 k_0 k 0 bits gives a seed description of length
B d e s c ≤ ( n + 1 [ s 0 > 0 ] ( K − 1 ) ) k 0 ≤ 2 ρ i n N . B_{\mathrm{desc}}\leq\left(n+\mathbb{1}[s_0>0](K-1)\right)k_0\leq2\rho_{\mathrm{in}}N. B desc ≤ ( n + 1 [ s 0 > 0 ] ( K − 1 ) ) k 0 ≤ 2 ρ in N .
These quantities exclude the descriptions of the fixed base code A A A , its encoding isomorphism E A E_A E A , and the inner encoding map ϕ \phi ϕ .
For the parameters of Theorem 4.3 , we have ρ i n = Θ ( ε ) \rho_{\mathrm{in}}=\Theta(\varepsilon) ρ in = Θ ( ε ) and K / n = O ( ε log 2 ( 1 / ε ) ) K/n=O(\varepsilon\log_2(1/\varepsilon)) K / n = O ( ε log 2 ( 1/ ε )) . Hence both the entropy and the description length are O ( ε N ) O(\varepsilon N) O ( εN ) , with the choice of U Z U_Z U Z contributing O ( ε 2 log 2 ( 1 / ε ) ) O(\varepsilon^2\log_2(1/\varepsilon)) O ( ε 2 log 2 ( 1/ ε )) bits per binary coordinate. The construction using multiplication in an extension field satisfies the same bounds. An exactly uniform seed can be sampled using O ( ε N ) O(\varepsilon N) O ( εN ) unbiased random bits in expectation by rejecting zero when choosing each α i \alpha_i α i .
Encoding
Let G A ∈ F Q K × n G_A\in\mathbb{F}_Q^{K\times n} G A ∈ F Q K × n represent E A E_A E A with messages written as row vectors. The outer encoder in the Toeplitz construction is
u ⟼ u [ I k ∣ T T ] G A diag ( α ) , u ∈ F Q k . u\longmapsto u[I_k\mid T^{\mathsf{T}}]G_A\operatorname{diag}(\alpha),\qquad u\in\mathbb{F}_Q^k. u ⟼ u [ I k ∣ T T ] G A diag ( α ) , u ∈ F Q k .
For the construction using multiplication in an extension field, replace T T T^{\mathsf{T}} T T by a matrix representing H Z H_Z H Z . Applying ϕ : F Q → C i n \phi:\mathbb{F}_Q\to C_{\mathrm{in}} ϕ : F Q → C in to each outer coordinate gives the binary encoder. Thus, if A A A can be encoded in polynomial time, so can the concatenated code. For the GS codes, the required encoding maps are computed as described in § 5.2 .
Decoding inherited from the base code
Suppose that A A A has a decoder that corrects e e e errors and s s s erasures whenever 2 e + s < D A d e c 2e+s<D_A^{\mathrm{dec}} 2 e + s < D A dec , where 0 < D A d e c ≤ d ( A ) 0<D_A^{\mathrm{dec}}\leq d(A) 0 < D A dec ≤ d ( A ) . To decode C o u t ( α , Z ) ⊆ A α C_{\mathrm{out}}(\alpha,Z)\subseteq A_\alpha C out ( α , Z ) ⊆ A α , multiply each unerased received coordinate by α i − 1 \alpha_i^{-1} α i − 1 and apply the decoder for A A A . If the result a a a belongs to E A ( U Z ) E_A(U_Z) E A ( U Z ) , return diag ( α ) a \operatorname{diag}(\alpha)a diag ( α ) a ; otherwise, declare failure. Nonzero scaling preserves the error and erasure locations, so this decoder has the same correction guarantee. The required generator matrix and membership tests are obtained by linear algebra from the seed and G A G_A G A .
Let d i n : = d ( C i n ) d_{\mathrm{in}}:=d(C_{\mathrm{in}}) d in := d ( C in ) . Forney’s generalized minimum distance (GMD) decoding therefore corrects any t t t binary errors in C o u t ( α , Z ) ∘ ϕ C i n C_{\mathrm{out}}(\alpha,Z)\mathbin{\circ_\phi} C_{\mathrm{in}} C out ( α , Z ) ∘ ϕ C in whenever
t < d i n D A d e c 2 . (40) t<\frac{d_{\mathrm{in}}D_A^{\mathrm{dec}}}{2}. \tag*{(40)} t < 2 d in D A dec . (40)
for every α \alpha α , Z Z Z [8 , 12 ] . GMD decoding finds a nearest codeword in each inner block, orders the blocks by reliability, and tries at most n + 1 n+1 n + 1 erasure patterns, retaining only those with s < D A d e c s < D_A^{\mathrm{dec}} s < D A dec . Each candidate is reencoded and checked against the received binary word within the radius in (40) . There is at most one such candidate, since the concatenated code has minimum distance at least d i n D A d e c d_{\mathrm{in}}D_A^{\mathrm{dec}} d in D A dec . Given the generator matrix, membership testing, reencoding, and distance verification take polynomial time. For a fixed inner code and encoding map, exhaustive decoding of one inner block takes O ( Q n 0 ) O(Qn_0) O ( Q n 0 ) time, which is independent of N N N . Thus the concatenated decoder runs in polynomial time if the decoder for A A A , including the preprocessing for each erasure pattern, does so.
For A = C L ( D , G ) A=C_L(D,G) A = C L ( D , G ) , suppose that the curve has an F Q \mathbb{F}_Q F Q -rational point P P P outside the support of D D D . With auxiliary point P P P , the decoder of Lee, Bras-Amorós, and O’Sullivan corrects e e e errors whenever 2 e < n − deg G 2e<n-\deg G 2 e < n − deg G [13 Propositions 13 and 15] . For s s s erasures, apply this algorithm to C L ( D ′ , G ) C_L(D',G) C L ( D ′ , G ) , where D ′ D' D ′ is the sum of the n − s n-s n − s remaining evaluation points. If 2 e + s < n − deg G 2e+s<n-\deg G 2 e + s < n − deg G , then n − s > deg G n-s>\deg G n − s > deg G , so evaluation on these points is injective. The recovered function can therefore be evaluated at all original points to recover the transmitted word. Hence we may take D A d e c = n − deg G D_A^{\mathrm{dec}}=n-\deg G D A dec = n − deg G .
For the GS codes, the required preprocessing also takes polynomial time. Put P = P ∞ , m P=P_{\infty,m} P = P ∞ , m , g = g m g=g_m g = g m , and n ′ = deg D ′ n'=\deg D' n ′ = deg D ′ . Choose a function x x x whose only pole is at P P P , of least positive order h ≤ g + 1 h\leq g+1 h ≤ g + 1 . The standard bases over F Q [ x ] \mathbb{F}_Q[x] F Q [ x ] for R = ⋃ b ≥ 0 L ( b P ) \mathcal{R}=\bigcup_{b\geq0}L(bP) R = ⋃ b ≥ 0 L ( b P ) and its ideal of functions vanishing on D ′ D' D ′ are obtained by choosing functions of least pole order in each residue class modulo h h h [13 Section II] . Riemann–Roch bounds these pole orders by 2 g + h − 1 2g+h-1 2 g + h − 1 and n ′ + 2 g + h − 1 n'+2g+h-1 n ′ + 2 g + h − 1 , respectively. Interpolation functions are obtained from the surjective evaluation map L ( ( n ′ + 2 g ) P ) → F Q n ′ L((n'+2g)P)\to\mathbb{F}_Q^{n'} L (( n ′ + 2 g ) P ) → F Q n ′ and the vanishing conditions are imposed by taking kernels of evaluation maps. Since g = O ( n m ) g=O(n_m) g = O ( n m ) , the basis functions and their products lie in Riemann–Roch spaces whose divisor degrees are O ( n m ) O(n_m) O ( n m ) . The explicit function representations and basis computations on the tower [15 ] , followed by linear algebra, give a polynomial bound for fixed Q Q Q , uniformly over the erasure patterns. Together with the bounds on the remaining operations in [13 Section III.C] , this includes the preprocessing in the running time of each decoding trial.
For the construction in Theorem 4.3 , with either distribution from Example 3.2, we obtain the following result.
Corollary 5.1 (A decoding guarantee for finite GS codes). For every sufficiently small fixed ε > 0 \varepsilon>0 ε > 0 , there exists a τ \tau τ -nice inner code C i n C_{\mathrm{in}} C in satisfying
d ( C i n ) n 0 ≥ 1 2 − ρ i n . \frac{d(C_{\mathrm{in}})}{n_0}\geq\frac{1}{2}-\sqrt{\rho_{\mathrm{in}}}. n 0 d ( C in ) ≥ 2 1 − ρ in . For any such code and any isomorphism ϕ : F Q → C i n \phi:\mathbb{F}_Q\to C_{\mathrm{in}} ϕ : F Q → C in , for all sufficiently large m m m and every outer seed ( α m , Z m ) (\alpha_m,Z_m) ( α m , Z m ) , the concatenated code can uniquely correct any t t t binary errors satisfying
t N m < ϑ ε , m : = 1 2 ( 1 2 − ρ i n ) ( 1 − μ m n m ) (41) \frac{t}{N_m}<\vartheta_{\varepsilon,m}:=\frac{1}{2}\left(\frac{1}{2}-\sqrt{\rho_{\mathrm{in}}}\right)\left(1-\frac{\mu_m}{n_m}\right) \tag*{(41)} N m t < ϑ ε , m := 2 1 ( 2 1 − ρ in ) ( 1 − n m μ m ) (41) in time polynomial in N m N_m N m .
Proof. For a uniformly random binary [ n 0 , k 0 ] [n_0,k_0] [ n 0 , k 0 ] linear code, the probability of violating (3.2) is at most n 0 2 − τ n 0 n_0 2^{-\tau n_0} n 0 2 − τ n 0 . For sufficiently small ε \varepsilon ε , the entropy inequality used in the proof of Theorem 4.3 gives 1 − h 2 ( 1 / 2 − ρ i n ) ≥ 2 ρ i n / ln 2 1-h_2(1/2-\sqrt{\rho_{\mathrm{in}}})\geq2\rho_{\mathrm{in}}/\ln2 1 − h 2 ( 1/2 − ρ in ) ≥ 2 ρ in / ln 2 . A union bound over nonzero words of weight below n 0 ( 1 / 2 − ρ i n ) n_0(1/2-\sqrt{\rho_{\mathrm{in}}}) n 0 ( 1/2 − ρ in ) therefore gives
Pr [ d ( C i n ) / n 0 < 1 / 2 − ρ i n ] ≤ 2 − ( 2 / ln 2 − 1 ) k 0 . \Pr[d(C_{\mathrm{in}})/n_0<1/2-\sqrt{\rho_{\mathrm{in}}}]\leq2^{-(2/\ln2-1)k_0}. Pr [ d ( C in ) / n 0 < 1/2 − ρ in ] ≤ 2 − ( 2/ l n 2 − 1 ) k 0 .
The sum of these two failure bounds is o ε ( 1 ) o_\varepsilon(1) o ε ( 1 ) , so an inner code satisfying both conditions exists for sufficiently small ε \varepsilon ε .
For A m A_m A m , we may take D A m d e c = n m − μ m D^{\mathrm{dec}}_{A_m}=n_m-\mu_m D A m dec = n m − μ m . Thus (40) gives
d ( C i n ) D A m d e c 2 N m = 1 2 d ( C i n ) n 0 ( 1 − μ m n m ) ≥ ϑ ε , m . \frac{d(C_{\mathrm{in}})D^{\mathrm{dec}}_{A_m}}{2N_m}=\frac{1}{2}\frac{d(C_{\mathrm{in}})}{n_0}\left(1-\frac{\mu_m}{n_m}\right)\geq\vartheta_{\varepsilon,m}. 2 N m d ( C in ) D A m dec = 2 1 n 0 d ( C in ) ( 1 − n m μ m ) ≥ ϑ ε , m .
The polynomial running time follows from the preceding GMD and preprocessing bounds, since fixed ε \varepsilon ε allows us to fix C i n C_{\mathrm{in}} C in and ϕ \phi ϕ independently of m m m .
Since μ m / n m → R A + γ Q \mu_m/n_m\to R_A+\gamma_Q μ m / n m → R A + γ Q for fixed ε \varepsilon ε , the parameter estimates in § 5 give
lim m → ∞ ϑ ε , m = 1 2 ( 1 2 − ρ i n ) ( 1 − R A − γ Q ) = 1 4 − O ( ε ) ( ε → 0 ) . \lim_{m\to\infty}\vartheta_{\varepsilon,m}=\frac{1}{2}\left(\frac{1}{2}-\sqrt{\rho_{\mathrm{in}}}\right)(1-R_A-\gamma_Q)=\frac{1}{4}-O(\sqrt{\varepsilon})\qquad(\varepsilon\to0). m → ∞ lim ϑ ε , m = 2 1 ( 2 1 − ρ in ) ( 1 − R A − γ Q ) = 4 1 − O ( ε ) ( ε → 0 ) .
On the event in (36) , the lower bound on δ ( C m ) / 2 \delta(C_m)/2 δ ( C m ) /2 has the form 1 / 4 − O ( ε ) 1/4-O(\varepsilon) 1/4 − O ( ε ) . The larger deficit in the guaranteed GMD radius comes from the term ρ i n \sqrt{\rho_{\mathrm{in}}} ρ in in (41) .
Discussion
We compare the construction with unrestricted random outer codes, explain the allocation of the inner and outer rates, and discuss the remaining questions.
Comparison with random linear outer codes
Taking A = F Q n A=\mathbb{F}_Q^n A = F Q n removes the restriction to a proper base code. Since A ⊥ = { 0 } A^\perp=\{0\} A ⊥ = { 0 } , the second term vanishes. For U U U chosen uniformly from Gr Q ( k , n ) \operatorname{Gr}_Q(k,n) Gr Q ( k , n ) , condition (1.1) holds, and each map U ↦ diag ( α ) E A ( U ) U\mapsto\operatorname{diag}(\alpha)E_A(U) U ↦ diag ( α ) E A ( U ) preserves the uniform distribution. Thus, for every 0 < β < 1 0<\beta<1 0 < β < 1 and every even r ≥ 2 r\geq2 r ≥ 2 , (3) gives
Pr U [ U ∘ ϕ C i n is not β -balanced ] ≤ T 0 . (42) \Pr_U[U\circ_\phi C_{\mathrm{in}}\text{ is not }\beta\text{-balanced}]\leq T_0. \tag*{(42)} U Pr [ U ∘ ϕ C in is not β -balanced ] ≤ T 0 . (42)
To recover the distance guarantee of [6 Theorem 3] , take both constituent rates equal to ε \varepsilon ε and log 2 Q = Ω ( ε − 3 ) \log_2 Q=\Omega(\varepsilon^{-3}) log 2 Q = Ω ( ε − 3 ) . Then n 0 = ( log 2 Q ) / ε n_0=(\log_2 Q)/\varepsilon n 0 = ( log 2 Q ) / ε , so τ = n 0 − 1 / 2 = o ( ε ) \tau=n_0^{-1/2}=o(\varepsilon) τ = n 0 − 1/2 = o ( ε ) and n 0 ε 2 → ∞ n_0\varepsilon^2\to\infty n 0 ε 2 → ∞ as ε → 0 \varepsilon\to0 ε → 0 . For a τ \tau τ -nice inner code take β = 2 ε \beta=2\varepsilon β = 2 ε , s = ε / 2 s=\varepsilon/2 s = ε /2 , and r r r to be the nearest even integer to ε 2 N \varepsilon^2N ε 2 N . With a = 1 a=1 a = 1 , b = 2 b=2 b = 2 , and z = 1 / 2 < ln 2 z=1/2<\ln2 z = 1/2 < ln 2 , (6.2) below gives N − 1 ln T 0 = ε 2 ( ln 2 − 7 / 8 + o ( 1 ) ) N^{-1}\ln T_0=\varepsilon^2(\ln2-7/8+o(1)) N − 1 ln T 0 = ε 2 ( ln 2 − 7/8 + o ( 1 )) . The coefficient ln 2 − 7 / 8 \ln2-7/8 ln 2 − 7/8 is negative, and a uniformly random inner code fails (3.2) with probability at most n 0 2 − n 0 n_0 2^{-\sqrt{n_0}} n 0 2 − n 0 . The resulting binary code has rate ε 2 \varepsilon^2 ε 2 . By (6.1), the probability over the two independent codes that its relative distance is below 1 / 2 − ε 1/2-\varepsilon 1/2 − ε is at most n 0 2 − n 0 + e − c ε 2 N n_0 2^{-\sqrt{n_0}}+e^{-c\varepsilon^2N} n 0 2 − n 0 + e − c ε 2 N for some c > 0 c>0 c > 0 and all sufficiently small ε \varepsilon ε .
For the inner parameters in (4.3), fix a τ \tau τ -nice inner code and an encoding isomorphism ϕ : F Q → C i n \phi:\mathbb{F}_Q\to C_{\mathrm{in}} ϕ : F Q → C in as in § 5.1 , and take k = ⌊ ε 2 n / ρ i n ⌋ k=\lfloor\varepsilon^2n/\rho_{\mathrm{in}}\rfloor k = ⌊ ε 2 n / ρ in ⌋ . Then the binary rate tends to ε 2 \varepsilon^2 ε 2 as n → ∞ n\to\infty n → ∞ , and the estimate of T 0 T_0 T 0 in Lemma 4.2 gives the distance target h 2 − 1 ( 1 − ε 2 − ε 4 ) h_2^{-1}(1-\varepsilon^2-\varepsilon^4) h 2 − 1 ( 1 − ε 2 − ε 4 ) with failure probability at most 2 − c ε 4 n n 0 2^{-c\varepsilon^4nn_0} 2 − c ε 4 n n 0 for sufficiently large n n n .
Allocation of the inner and outer rates
We explain how the inner rate affects the explicit upper bound T ‾ 0 \overline{T}_0 T 0 used in Section 3.2. Doron, Mosheiff, and Wootters take both constituent rates to be ε \varepsilon ε in their analysis of random linear outer codes [6 Theorem 3] . The earlier analysis of Barg, Justesen, and Thommesen treats the inner rate and the total rate as separate parameters [1 Section I] . Thus equal rates are one relevant choice, rather than a common assumption of previous work.
For the comparison below, consider a family of τ \tau τ -nice inner codes with 0 < τ < ρ i n < 1 0<\tau<\rho_{\mathrm{in}}<1 0 < τ < ρ in < 1 , R = ε 2 R=\varepsilon^2 R = ε 2 , ρ i n = a ε + o ( ε ) \rho_{\mathrm{in}}=a\varepsilon+o(\varepsilon) ρ in = a ε + o ( ε ) , and τ = o ( ε ) \tau=o(\varepsilon) τ = o ( ε ) , where a > 0 a>0 a > 0 is fixed. Assume that n 0 ε 2 → ∞ n_0\varepsilon^2\to\infty n 0 ε 2 → ∞ . Take β = b ε + o ( ε ) \beta=b\varepsilon+o(\varepsilon) β = b ε + o ( ε ) with fixed b > 0 b>0 b > 0 , s = z ε + o ( ε ) s=z\varepsilon+o(\varepsilon) s = z ε + o ( ε ) with fixed 0 < z < a ln 2 0<z<a\ln2 0 < z < a ln 2 , and even r r r such that r / N = β s + o ( ε 2 ) r/N=\beta s+o(\varepsilon^2) r / N = β s + o ( ε 2 ) . Let b c r i t ( a ) b_{\mathrm{crit}}(a) b crit ( a ) be the infimum of the b > 0 b>0 b > 0 for which ln 2 − b z + z 2 / 2 < 0 \ln2-bz+z^2/2<0 ln 2 − b z + z 2 /2 < 0 for some 0 < z < a ln 2 0<z<a\ln2 0 < z < a ln 2 . Put a ∗ : = 2 / ln 2 a_*:=\sqrt{2/\ln2} a ∗ := 2/ ln 2 and b G V : = 2 ln 2 b_{\mathrm{GV}}:=\sqrt{2\ln2} b GV := 2 ln 2
Proposition 6.1. Under these assumptions,
1 N ln T ‾ 0 = ε 2 ( ln 2 − b z + z 2 2 ) + o ( ε 2 ) . (43) \frac{1}{N}\ln\overline{T}_0=\varepsilon^2\left(\ln2-bz+\frac{z^2}{2}\right)+o(\varepsilon^2). \tag*{(43)} N 1 ln T 0 = ε 2 ( ln 2 − b z + 2 z 2 ) + o ( ε 2 ) . (43) Moreover,
b c r i t ( a ) = { 1 a + a ln 2 2 , a < 2 / ln 2 , 2 ln 2 , a ≥ 2 / ln 2 . b_{\mathrm{crit}}(a)=
\begin{cases}
\frac{1}{a}+\frac{a\ln2}{2}, & a<\sqrt{2/\ln2},\\
\sqrt{2\ln2}, & a\ge\sqrt{2/\ln2}.
\end{cases} b crit ( a ) = { a 1 + 2 a l n 2 , 2 ln 2 , a < 2/ ln 2 , a ≥ 2/ ln 2 .
Proof. The zero word gives n 0 − 1 ln M C i n ( s ) ≥ s − ρ i n ln 2 n_0^{-1}\ln M_{\mathrm{C}_{\mathrm{in}}}(s)\ge s-\rho_{\mathrm{in}}\ln2 n 0 − 1 ln M C in ( s ) ≥ s − ρ in ln 2 , which motivates the restriction z < a ln 2 z<a\ln2 z < a ln 2 . In this range,
( ρ i n − τ ) ln 2 − ln ( 1 + tanh s ) = ( a ln 2 − z ) ε + o ( ε ) > 0. (\rho_{\mathrm{in}}-\tau)\ln2-\ln(1+\tanh s)=(a\ln2-z)\varepsilon+o(\varepsilon)>0. ( ρ in − τ ) ln 2 − ln ( 1 + tanh s ) = ( a ln 2 − z ) ε + o ( ε ) > 0.
Equation (15) and n 0 ε 2 → ∞ n_0\varepsilon^2\to\infty n 0 ε 2 → ∞ imply n 0 − 1 ln Γ = o ( ε 2 ) n_0^{-1}\ln\Gamma=o(\varepsilon^2) n 0 − 1 ln Γ = o ( ε 2 ) . Since r ≍ N ε 2 → ∞ r\asymp N\varepsilon^2\to\infty r ≍ N ε 2 → ∞ , Stirling’s formula gives
1 N ln r ! ( β s N ) r = − β s + o ( ε 2 ) . \frac{1}{N}\ln\frac{r!}{(\beta sN)^r}=-\beta s+o(\varepsilon^2). N 1 ln ( β s N ) r r ! = − β s + o ( ε 2 ) .
Together with ln cosh s = z 2 ε 2 / 2 + o ( ε 2 ) \ln\cosh s=z^2\varepsilon^2/2+o(\varepsilon^2) ln cosh s = z 2 ε 2 /2 + o ( ε 2 ) , this proves (43) .
The supremum of b z − z 2 / 2 bz-z^2/2 b z − z 2 /2 over 0 < z < a ln 2 0<z<a\ln2 0 < z < a ln 2 is b 2 / 2 b^2/2 b 2 /2 if b ≤ a ln 2 b\le a\ln2 b ≤ a ln 2 , and a b ln 2 − a 2 ( ln 2 ) 2 / 2 ab\ln2-a^2(\ln2)^2/2 ab ln 2 − a 2 ( ln 2 ) 2 /2 otherwise. Equating this supremum to ln 2 \ln2 ln 2 gives b c r i t ( a ) b_{\mathrm{crit}}(a) b crit ( a ) . If a < a ∗ a<a_* a < a ∗ , every admissible z z z satisfies
ln 2 − b G V z + z 2 2 = ( b G V − z ) 2 2 ≥ ( b G V − a ln 2 ) 2 2 > 0. \ln2-b_{\mathrm{GV}}z+\frac{z^2}{2}=\frac{(b_{\mathrm{GV}}-z)^2}{2}\ge\frac{(b_{\mathrm{GV}}-a\ln2)^2}{2}>0. ln 2 − b GV z + 2 z 2 = 2 ( b GV − z ) 2 ≥ 2 ( b GV − a ln 2 ) 2 > 0.
Thus the upper bound diverges when β = ( b G V + o ( 1 ) ) ε \beta=(b_{\mathrm{GV}}+o(1))\varepsilon β = ( b GV + o ( 1 )) ε , because N ε 2 → ∞ N\varepsilon^2\to\infty N ε 2 → ∞ .
If a > a ∗ a>a_* a > a ∗ , take s = ( b G V + ν ε ) ε s=(b_{\mathrm{GV}}+\nu_\varepsilon)\varepsilon s = ( b GV + ν ε ) ε and let r r r be the nearest even integer to β s N \beta sN β s N , where β = ( b G V + ν ε ) ε \beta=(b_{\mathrm{GV}}+\nu_\varepsilon)\varepsilon β = ( b GV + ν ε ) ε . Choose ν ε → 0 \nu_\varepsilon\to0 ν ε → 0 slowly enough that N ε 2 ν ε → ∞ N\varepsilon^2\nu_\varepsilon\to\infty N ε 2 ν ε → ∞ and the remainders in the exponent are o ( ε 2 ν ε ) o(\varepsilon^2\nu_\varepsilon) o ( ε 2 ν ε ) . The normalized exponent is then − ε 2 ( b G V ν ε + ν ε 2 / 2 ) + o ( ε 2 ν ε ) -\varepsilon^2(b_{\mathrm{GV}}\nu_\varepsilon+\nu_\varepsilon^2/2)+o(\varepsilon^2\nu_\varepsilon) − ε 2 ( b GV ν ε + ν ε 2 /2 ) + o ( ε 2 ν ε ) , so T ‾ 0 → 0 \overline{T}_0\to0 T 0 → 0 . At a = a ∗ a=a_* a = a ∗ , the optimum is on the excluded boundary z = a ln 2 z=a\ln2 z = a ln 2 , which explains the final qualification. □
In particular, if a < a ∗ a<a_* a < a ∗ , the stated range of s , r s,r s , r cannot make T ‾ 0 → 0 \overline{T}_0\to0 T 0 → 0 when β = ( b G V + o ( 1 ) ) ε \beta=(b_{\mathrm{GV}}+o(1))\varepsilon β = ( b GV + o ( 1 )) ε . If a > a ∗ a>a_* a > a ∗ , there is a sequence ν ε > 0 \nu_\varepsilon>0 ν ε > 0 tending to zero and admissible s , r s,r s , r for which β = ( b G V + ν ε ) ε \beta=(b_{\mathrm{GV}}+\nu_\varepsilon)\varepsilon β = ( b GV + ν ε ) ε and T ‾ 0 → 0 \overline{T}_0\to0 T 0 → 0 .
For equal constituent rates, a = 1 a=1 a = 1 , the threshold for the distance deficit given by this estimate is b c r i t ( 1 ) / 2 = ( 1 + ln 2 / 2 ) / 2 = 0.673286 … b_{\mathrm{crit}}(1)/2=(1+\ln2/2)/2=0.673286\ldots b crit ( 1 ) /2 = ( 1 + ln 2/2 ) /2 = 0.673286 … , whereas the GV coefficient is ln 2 / 2 = 0.588705 … \sqrt{\ln2}/2=0.588705\ldots ln 2 /2 = 0.588705 … . This comparison concerns the bound, not the best distance attainable by such codes. Our construction has ρ i n ∼ a ∗ ε \rho_{\mathrm{in}}\sim a_*\varepsilon ρ in ∼ a ∗ ε and lim m k m / n m ∼ ε / a ∗ \lim_m k_m/n_m\sim\varepsilon/a_* lim m k m / n m ∼ ε / a ∗ as ε → 0 \varepsilon\to0 ε → 0 . The estimates in Lemma 4.2 control the smaller terms needed when the leading coefficient of the inner rate approaches a ∗ a_* a ∗ .
Open problems
The construction gives the leading GV coefficient while retaining a prescribed AG base code for encoding and decoding.
First, the selection of the outer subcode and the coordinate scalings is random. The simultaneous guarantee in Corollary 4.4 proves the existence of an outer code that works for every inner map with a τ \tau τ -nice image, at each sufficiently large block length. It remains to find such a choice deterministically, or to certify efficiently that a given choice satisfies the distance bound.
Second, the alphabet is fixed as the block length grows, but increases as the target rate tends to zero: Q = 2 Θ ( ε − 1 log ( 1 / ε ) ) Q=2^{\Theta(\varepsilon^{-1}\log(1/\varepsilon))} Q = 2 Θ ( ε − 1 l o g ( 1/ ε )) . Reducing this dependence while preserving the distance guarantee, the O ( ε N ) O(\varepsilon N) O ( εN ) description length, and the decoding guarantee would improve the cost of exhaustive decoding of the inner code.
Third, GMD decoding guarantees correction of a fraction 1 / 4 − O ( ε ) 1/4-O(\sqrt{\varepsilon}) 1/4 − O ( ε ) of errors, whereas half the distance lower bound is 1 / 4 − O ( ε ) 1/4-O(\varepsilon) 1/4 − O ( ε ) . Methods using multiple candidates for the inner code and more information than its minimum distance have been studied for concatenated codes [11 ] . One may seek to combine them with list recovery for AG codes, which asks for codewords agreeing with prescribed small lists on sufficiently many coordinates, while requiring the outer word to belong to E A ( U Z ) E_A(U_Z) E A ( U Z ) after undoing the scalings. The present complexity guarantee is polynomial in the block length for fixed ε \varepsilon ε and does not give a bound polynomial in 1 / ε 1/\varepsilon 1/ ε .
Finally, the estimate using the dual distance discards part of the weight distribution of A ⊥ A^\perp A ⊥ . For finite block lengths, the exact sum in Theorem 3.6 or the bounds in Appendix § 8 may give a sharper distance guarantee.
Additional bounds obtained by Poissonization
This appendix develops another approach to bounding the additional term L r ( A , C i n ) \mathcal{L}_r(A,C_{\mathrm{in}}) L r ( A , C in ) arising from A A A . Although it is not needed for our GS construction, the approach explains how our estimate relates to the Poissonization argument of Doron, Mosheiff, and Wootters and gives an additional bound through an evaluation of the weight enumerator.
For a fixed tuple length r r r , Theorem 3.6 gives
L r ( A , C i n ) = ∑ w = 1 n π r ( w ) θ w ( A ) . \mathcal{L}_r(A,C_{\mathrm{in}})=\sum_{w=1}^{n}\pi_r(w)\theta_w(A). L r ( A , C in ) = w = 1 ∑ n π r ( w ) θ w ( A ) .
Following [6 Section 1.2] , we replace the fixed tuple length by a Poisson random variable (Poissonization) to obtain another representation in terms of weight enumerators.
For t ≥ 0 t\ge0 t ≥ 0 , define
p 0 ( t ) : = 1 Q W C i n ( 1 , e − 2 t ) , ξ ( t ) : = Q p 0 ( t ) − 1 Q − 1 , p_0(t):=\frac{1}{Q}W_{C_{\mathrm{in}}}(1,e^{-2t}),\qquad\xi(t):=\frac{Qp_0(t)-1}{Q-1}, p 0 ( t ) := Q 1 W C in ( 1 , e − 2 t ) , ξ ( t ) := Q − 1 Q p 0 ( t ) − 1 ,
and
Φ A , C i n ( t ) : = Q − K W A ( 1 , ξ ( t ) ) − p 0 ( t ) n . \Phi_{A,C_{\mathrm{in}}}(t):=Q^{-K}W_A(1,\xi(t))-p_0(t)^n. Φ A , C in ( t ) := Q − K W A ( 1 , ξ ( t )) − p 0 ( t ) n .
Lemma A.1. Let J ∼ Poi ( N t ) J\sim\operatorname{Poi}(Nt) J ∼ Poi ( N t ) . Conditional on J = j J=j J = j , choose V V V uniformly from V j \mathcal{V}_j V j , and choose α ∈ ( F Q X ) n \alpha\in(\mathbb{F}_Q^X)^n α ∈ ( F Q X ) n independently and uniformly. Then
Pr J , V , α [ g V ≠ 0 , g V ∈ A α ⊥ ] = Φ A , C i n ( t ) . (44) \Pr_{J,V,\alpha}\left[g_V\ne0,\ g_V\in A_\alpha^\perp\right]=\Phi_{A,C_{\mathrm{in}}}(t). \tag*{(44)} J , V , α Pr [ g V = 0 , g V ∈ A α ⊥ ] = Φ A , C in ( t ) . (44) Moreover, for every integer r ≥ 1 r\ge1 r ≥ 1 ,
L r ( A , C i n ) ≤ 3 r Φ A , C i n ( r / N ) . (45) \mathcal{L}_r(A,C_{\mathrm{in}})\le3\sqrt{r}\,\Phi_{A,C_{\mathrm{in}}}(r/N). \tag*{(45)} L r ( A , C in ) ≤ 3 r Φ A , C in ( r / N ) . (45)
Proof. By the splitting property of the Poisson distribution, the counts at positions ( i , j ) ∈ [ n ] × [ n 0 ] (i,j)\in[n]\times[n_0] ( i , j ) ∈ [ n ] × [ n 0 ] are independent Poi ( t ) \operatorname{Poi}(t) Poi ( t ) random variables. Their parities are therefore independent Bernoulli random variables with parameter ( 1 − e − 2 t ) / 2 (1-e^{-2t})/2 ( 1 − e − 2 t ) /2 .
For one outer coordinate, let
G t : = ∑ j = 1 n 0 ζ j ω j , Pr [ ζ j = 1 ] = 1 − e − 2 t 2 . G_t:=\sum_{j=1}^{n_0}\zeta_j\omega_j,\qquad\Pr[\zeta_j=1]=\frac{1-e^{-2t}}{2}. G t := j = 1 ∑ n 0 ζ j ω j , Pr [ ζ j = 1 ] = 2 1 − e − 2 t .
For a ∈ F Q a\in\mathbb{F}_Q a ∈ F Q , set χ a ( y ) : = ( − 1 ) Tr ( a y ) \chi_a(y):=(-1)^{\operatorname{Tr}(ay)} χ a ( y ) := ( − 1 ) Tr ( a y ) . Independence of the variables ζ j \zeta_j ζ j gives E [ χ a ( G t ) ] = e − 2 t wt ( ϕ ( a ) ) \mathbb{E}[\chi_a(G_t)]=e^{-2t\operatorname{wt}(\phi(a))} E [ χ a ( G t )] = e − 2 t wt ( ϕ ( a )) . Fourier inversion therefore yields
Pr [ G t = 0 ] = 1 Q ∑ a ∈ F Q e − 2 t wt ( ϕ ( a ) ) = 1 Q W C i n ( 1 , e − 2 t ) = p 0 ( t ) . (46) \Pr[G_t=0]=\frac{1}{Q}\sum_{a\in\mathbb{F}_Q}e^{-2t\operatorname{wt}(\phi(a))}=\frac{1}{Q}W_{C_{\mathrm{in}}}(1,e^{-2t})=p_0(t). \tag*{(46)} Pr [ G t = 0 ] = Q 1 a ∈ F Q ∑ e − 2 t wt ( ϕ ( a )) = Q 1 W C in ( 1 , e − 2 t ) = p 0 ( t ) . (46)
Thus, p 0 ( t ) p_0(t) p 0 ( t ) is a probability, and the term a = 0 a=0 a = 0 also gives p 0 ( t ) ≥ Q − 1 p_0(t) \ge Q^{-1} p 0 ( t ) ≥ Q − 1 . Hence, 0 ≤ ξ ( t ) ≤ 1 0 \le\xi(t) \le1 0 ≤ ξ ( t ) ≤ 1 .
The n n n outer coordinates are independent. After multiplication by independent uniform elements of F Q \mathbb{F}_Q F Q , each coordinate equals 0 0 0 with probability p 0 ( t ) p_0(t) p 0 ( t ) and takes each nonzero value with probability ( 1 − p 0 ( t ) ) / ( Q − 1 ) (1-p_0(t))/(Q-1) ( 1 − p 0 ( t )) / ( Q − 1 ) . Moreover, g V ∈ A α ⊥ g_V \in A^\perp_\alpha g V ∈ A α ⊥ is equivalent to diag ( α ) g V ∈ A ⊥ \operatorname{diag}(\alpha)g_V \in A^\perp diag ( α ) g V ∈ A ⊥ . Summing over A ⊥ ∖ { 0 } A^\perp\setminus\{0\} A ⊥ ∖ { 0 } therefore gives
Pr [ g V ≠ 0 , g V ∈ A α ⊥ ] = W A ⊥ ( p 0 ( t ) , 1 − p 0 ( t ) Q − 1 ) − p 0 ( t ) n . \Pr[g_V \ne0,\, g_V \in A^\perp_\alpha] = W_{A^\perp}\left(p_0(t),\frac{1-p_0(t)}{Q-1}\right)-p_0(t)^n. Pr [ g V = 0 , g V ∈ A α ⊥ ] = W A ⊥ ( p 0 ( t ) , Q − 1 1 − p 0 ( t ) ) − p 0 ( t ) n .
Since p 0 ( t ) + ( Q − 1 ) ( 1 − p 0 ( t ) ) / ( Q − 1 ) = 1 p_0(t)+(Q-1)(1-p_0(t))/(Q-1)=1 p 0 ( t ) + ( Q − 1 ) ( 1 − p 0 ( t )) / ( Q − 1 ) = 1 and p 0 ( t ) − ( 1 − p 0 ( t ) ) / ( Q − 1 ) = ξ ( t ) p_0(t)-(1-p_0(t))/(Q-1)=\xi(t) p 0 ( t ) − ( 1 − p 0 ( t )) / ( Q − 1 ) = ξ ( t ) , the MacWilliams identity [14 Chapter 5] yields (A.1).
On the other hand, conditioning on J = j J=j J = j gives
Φ A , C i n ( t ) = e − N t ∑ j = 0 ∞ ( N t ) j j ! L j ( A , C i n ) . \Phi_{A,C_{\mathrm{in}}}(t)=e^{-Nt}\sum_{j=0}^{\infty}\frac{(Nt)^j}{j!}\mathcal{L}_j(A,C_{\mathrm{in}}). Φ A , C in ( t ) = e − N t j = 0 ∑ ∞ j ! ( N t ) j L j ( A , C in ) .
Setting t = r / N t=r/N t = r / N and retaining only the term j = r j=r j = r , we obtain
Φ A , C i n ( r / N ) ≥ Pr [ Poi ( r ) = r ] L r ( A , C i n ) . \Phi_{A,C_{\mathrm{in}}}(r/N)\ge\Pr[\operatorname{Poi}(r)=r]\mathcal{L}_r(A,C_{\mathrm{in}}). Φ A , C in ( r / N ) ≥ Pr [ Poi ( r ) = r ] L r ( A , C in ) .
Stirling’s formula gives
Pr [ Poi ( r ) = r ] − 1 ≤ 2 π r e 1 / ( 12 r ) < 3 r , \Pr[\operatorname{Poi}(r)=r]^{-1}\le\sqrt{2\pi r}e^{1/(12r)}<3\sqrt{r}, Pr [ Poi ( r ) = r ] − 1 ≤ 2 π r e 1/ ( 12 r ) < 3 r ,
which proves (A.2).
Combining Theorem 3.6 and Lemma A.1 gives, for every even r ≥ 2 r\ge2 r ≥ 2 ,
L r ( A , C i n ) ≤ min { Θ A ( Q ) , 3 r Φ A , C i n ( r / N ) } . \mathcal{L}_r(A,C_{\mathrm{in}})\le\min\{\Theta_A(Q),\,3\sqrt{r}\,\Phi_{A,C_{\mathrm{in}}}(r/N)\}. L r ( A , C in ) ≤ min { Θ A ( Q ) , 3 r Φ A , C in ( r / N )} .
The quantity Θ A ( Q ) \Theta_A(Q) Θ A ( Q ) is the maximum, over w w w , of the fraction θ w ( A ) \theta_w(A) θ w ( A ) of all vectors of weight w w w that belong to the dual code, and is determined by the ordinary dual weight enumerator. Poissonization, on the other hand, makes the contributions from different coordinates independent and evaluates the weight enumerator at a specified point. The two approaches differ in how they weight and bound the contributions, rather than in the type of information they use about the outer code.