ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.34390 J. Algebra Comb. Discrete Appl. 4(1) • 37–47 Received: 25 November 2015 Accepted: 16 May 2016 Journal of Algebra Combinatorics Discrete Structures and Applications Refined analysis of RGHWs of code pairs coming from Garcia-Stichtenoth’s second tower∗ Research Article Olav Geil, Stefano Martin, Umberto Martínez-Peñas, Diego Ruano Abstract: Asymptotically good sequences of ramp secret sharing schemes were given in [5] by using one-point algebraic geometric codes defined from asymptotically good towers of function fields. Their security is given by the relative generalized Hamming weights of the corresponding codes. In this paper we demonstrate how to obtain refined information on the RGHWs when the codimension of the codes is small. For general codimension, we give an improved estimate for the highest RGHW. 2010 MSC: 94A62, 94B27, 94B65 Keywords: Algebraic geometric codes, Asymptotically good ramp secret sharing schemes, Generalized Hamming weights, Relative generalized Hamming weights, Secret sharing 1. Introduction Relative generalized Hamming weights (RGHWs) of two linear codes are fundamental for evaluating the security of ramp secret sharing schemes and wire-tap channels of type II [6, 7, 9, 12]. Until few years ago only the RGHWs of MDS codes and a few other examples of codes were known [8], but recently new results were discovered for one-point algebraic geometric codes [6], q-ary Reed-Muller codes [4] and cyclic codes [13]. In [5] it was discussed how to obtain asymptotically good sequences of ramp secret sharing schemes by using one-point algebraic geometric codes defined from asymptotically good towers of function fields. The tools used in [5] were the Goppa bound and the Feng-Rao bounds. In the present paper we focus on secret sharing schemes coming from the Garcia-Stichtenoth’s second tower [3]. We give a method for obtaining new information on the RGHWs when the used codes have small codimension. For general codimension we give an improved estimate on the highest RGHW. The new results are obtained ∗ Supported by the Danish Council for Independent Research, grant DFF-4002-00367 and the Spanish Ministry of Economy, grant MTM2015-65764-C3-2-P. Olav Geil, Stefano Martin, Umberto Martínez-Peñas, Diego Ruano (Corresponding Author); Department of Mathematical Sciences, Aalborg University, Fredrik Bajers Vej 7G, 9220-Aalborg Øst, Denmark (email: olav@math.aau.dk, stefano.martin87@gmail.com, umberto@math.aau.dk, diego@math.aau.dk). 37 O. Geil et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 37–47 by studying in detail the sequence of Weierstrass semigroups related to the sequence of rational places [10]. We recall the definition of RGHWs and briefly mention their use in connection with secret sharing schemes. Definition 1.1. Let C2 ( C1 ⊆ Fnq be two linear codes. For m = 1, . . . ,` = dimC1 − dimC2 the m-th relative generalized Hamming weight of C1 with respect to C2 is Mm(C1,C2) = min{#SuppD | D ⊆ C1 is a linear space, dimD = m,D ∩C2 = {~0}}. Here SuppD = #{i ∈ N | exists (c1, . . . ,cn) ∈ D with ci 6= 0}. Note that for m = 1, . . . ,dimC1, the m-th generalized Hamming weight (GHW) of C1 dm(C1) is Mm(C1,{~0}). Given C2 ( C1 linear codes, by definition, we have that the m-th generalized Hamming weight is a lower bound for the m-th relative generalized Hamming weight of C1 with respect to C2, i.e. Mm(C1,C2) ≥ dm(C1). In [2], a general construction of a linear secret sharing scheme with n par- ticipants is defined from two linear codes C2 ( C1 of length n. It was proved in [6, 7] that it has rm = n−M`−m+1(C1,C2) + 1 reconstruction and tm = Mm(C⊥2 ,C⊥1 )−1 privacy for m = 1, . . . ,`. Here, rm and tm are the unique numbers such that the following holds: It is not possible to recover m q-bits of information about the secret with only tm shares, but it is possible with some tm + 1 shares. With any rm shares it is possible to recover m q-bits of information about the secret, but it is not possible to recover m q-bits of information with some rm −1 shares. We shall focus on one-point algebraic geometric codes CL(D,G) where D = P1 + . . . + Pn, G = µQ, and P1, . . . ,Pn,Q are pairwise different rational places over a function field. By writing νQ for the valuation at Q, the Weiestrass semigroup corresponding to Q is H(Q) = −νQ ( ∞⋃ µ=0 L(µQ) ) = {µ ∈ N0 | L(µQ) 6= L((µ−1)Q)}. We denote by g the genus of the function field and by c the conductor of the Weierstrass semigroup. We consider C1 = CL(D,µ1Q) and C2 = CL(D,µ2Q), with −1 ≤ µ2 < µ1. Observe that for ` = dim(C1)−dim(C2) and µ = µ1 −µ2 we have that ` ≤ µ, with equality if 2g−1 ≤ µ2 < µ1 ≤ n−1 holds. From [6, Theorem 19] we have the following bound: Theorem 1.2. For m = 1, . . . ,` we have that: Mm(C1,C2) ≥ n−µ1 + Z(H(Q),µ,m), where Z(H(Q),µ,m) = min{#{α ∈∪m−1s=1 (is + H(Q)) | α /∈ H(Q)} | −(µ−1) ≤ i1 < i2 < ... < im−1 ≤−1}. For m > g, one has that dm(C) = n−k + m, that is the Singleton bound is reached [11, Corollary 4.2]. For other values of m, using Theorem 1.2, the following result was found [5, Proposition 14]. Proposition 1.3. Let CL(D,µQ) be a one-point algebraic geometric code of length n and dimension k. If −1 ≤ µ < n and 1 ≤ m ≤ min{k,g}, then: dm(CL(D,µQ)) ≥ n−k + 2m− c + hc−m ≥ n−k + 2m− c where hc−m = #(H(Q)∩ (0,c−m]). 38 O. Geil et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 37–47 Moreover, in the proof of [5, Proposition 14], one has that dm(CL(D,µQ)) ≥ n−µ + g −1 + 2m− c + hc−m, which may allow us to improve the bound in Proposition 1.3 for µ ≤ 2g−2, since in this case k ≥ µ+1−g. Furthermore, we can apply it to bound the RGHWs of a pair of codes. Proposition 1.4. Let CL(D,µ2Q) ⊆ CL(D,µ1Q) be two one-point algebraic geometric codes of length n and dimension k1 and k2, respectively. If −1 ≤ µ2 < µ1 < n and 1 ≤ m ≤ min{k1,g} then dm(CL(D,µ1Q)) ≥ n−µ1 + g −1 + 2m− c + hc−m where hc−m = #(H(Q)∩ (0,c−m]). Moreover, if 1 ≤ m ≤ min{k1 −k2,g} then Mm(CL(D,µ1Q),CL(D,µ2Q)) ≥ n−µ1 + g −1 + 2m− c + hc−m. From Garcia-Stichtenoth’s second tower [3] one obtains codes over any field Fq where q is an even power of a prime. Garcia and Stichtenoth analyzed the asymptotic behaviour of the number of rational places and the genus, from which one has that the codes beat the Gilbert-Varshamov bound for q ≥ 49. This allows us to create sequences of asymptotically good codes. The Garcia-Stichtenoth’s tower (F1,F2,F3, . . .) in [3] over Fq, for q an even power of a prime, is given by: • F1 = Fq(x1), • for ν > 1, Fν = Fν−1(xν) with xν satisfying x √ q ν + xν = x √ q ν−1 x √ q−1 ν−1 +1 . The number of rational points of Fν is Nq(Fν) ≥ q ν−1 2 (q− √ q) and its genus is gν = g(Fν) = (q 1 2bν+12 c− 1)(q 1 2dν+12 e−1). For every function field Fν the following complete description of the Weierstrass semigroups cor- responding to a sequence of rational places was given in [10]. Let Qν be the rational point that is the unique pole in x1. The Weierstrass semigroups H(Qν) at Qν in Fν are given recursively by: H(Q1) = N0, H(Qν) = √ q ·H(Qν−1)∪{i ∈ N0 : i ≥ cν}, where cν = q ν 2 −q 1 2bν+12 c is the conductor of H(Qν). An alternative way to obtain these Weiestrass semigroups was described in [1]. Definition 1.5. First we define H(Q1) = N0. For ν positive integer and j = 2 ⌊ ν 2 ⌋ , we define: cν = q ν 2 −q 1 2 (ν−j 2 ), H(Qν) = S 0 ν ∪S 1 ν ∪S 2 ν ∪ . . .∪S j 2 ν ∪S∞ν , where: • S0ν = {xν,1} = {0}, • For 1 ≤ i ≤ j 2 , Siν = {x ν,q i−1 2 +1 ,x ν,q i−1 2 +2 ,x ν,q i−1 2 +3 , . . . ,x ν,q i 2 } where for 1 ≤ k ≤ q i 2 − q i−1 2 we have that x ν,q i−1 2 +k = q j 2 −q ν−i+1 2 + kq ν−2i+1 2 , • S∞ν = [cν + 1,∞). 39 O. Geil et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 37–47 Using the previous description of the Weierstrass semigroup H(Qν), we can see that it has the following properties: Lemma 1.6. With the same notation as before, one has that: 1. For any i1, i2 ∈{0,1,2, . . . , j2 −1, j 2 ,∞}, i1 6= i2, we have that Si1ν ∩Si2ν = ∅. 2. For i ∈{1, . . . , j 2 } we have that #Siν = q i 2 −q i−1 2 and # ( ∪ir=0Srν ) = q i 2 . 3. For i ∈ {1, . . . , j 2 } and for any two consecutive elements x,y ∈ Siν, with x > y, we have that x−y = q ν−2i+1 2 . 4. For i ∈ {1, . . . , j 2 }. Let x be the first element of Siν and y the last element of Si−1ν , we have that x−y = q ν−2i+1 2 . 5. For i ∈{1, . . . , j 2 }, and for any x,y ∈∪ir=0Srν, x > y we have that x−y ≥ q ν−2i+1 2 . Proof. 1. By Theorem 1 in [1]. 2. Let i ∈ {1, . . . , j 2 }, the cardinality of Siν follows by its definition. For the second part, by (1), we have that: # ( ∪ir=0S r ν ) = #S0ν + i∑ r=1 #Srν = 1 + i∑ r=1 (q r 2 −q r−1 2 ) = 1 + q i 2 −1 = q i 2 . 3. Consider two consecutive elements x,y ∈ Siν, x > y. There exists a k ∈{1, . . . ,q i 2 −q i−1 2 −1} such that x = q j 2 −q ν−i+1 2 +kq ν−2i+1 2 and y = q j 2 −q ν−i+1 2 +(k+1)q ν−2i+1 2 . It follows that x−y = q ν−2i+1 2 . 4. Let y be the last element of Si−1ν , i.e. y = q j 2 − q ν−i+1 2 , and x be the first element of Siν, i.e. x = q j 2 −q ν−i+1 2 + q ν−2i+1 2 . We have that x−y = q ν−2i+1 2 . 5. For i ∈{1, . . . , j 2 }, consider x,y ∈∪ir=0Srν with x > y. This mean that there exists i1, i2 ∈{1, . . . , i}, i1 ≥ i2 such that x ∈ Si1ν , y ∈ Si2ν . Let x2 be the element that precedes x in H(Qν), then we have that x−y = (x−x2) + (x2 −y) = q ν−2i1+1 2 + (x2 −y) ≥ q ν−2i1+1 2 ≥ q ν−2i+1 2 . The second inequality follows by (3) and (4), the third one since x2 ≥ y and the last one since i1 ≤ i. Applying Proposition 1.3 to code pairs coming from Garcia-Stichtenoth’s second tower [3], an asymp- totic result was given in [5, Theorem 23], which combined with Proposition 1.4 allows us to obtain the following result. Corollary 1.7. Let (Fi)∞i=1 be Garcia-Stichtenoth’s second tower of function fields over Fq, where q is an even power of a prime. Let (Ci)∞i=1 be a sequence of one-point algebraic geometric codes constructed from (Fi)∞i=1. Consider R̃,R,ρ with 0 ≤ R ≤ 1 − 1√ q−1, 0 ≤ R̃ < 1 and 0 ≤ ρ ≤ min{R, 1√ q−1}, and assume that dim(Ci)/ni → R and µi/ni → R̃. For all sequences of positive integers (mi)∞i=1 with mi/ni → ρ, it holds that δ = lim infi→∞dmi(Ci)/ni satisfies δ ≥ 1−R + 2ρ− 1 √ q −1 . (1) δ ≥ 1− R̃ + 2ρ. (2) Note that the bound (2) is sharper than (1) for 1√ q−1 ≤ R ≤ 1− 1√ q−1. 40 O. Geil et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 37–47 2. Small codimension In this section we give a refined bound on the RGHWs of two nested one-point algebraic geometric codes coming from Garcia-Stichtenoth’s towers when the codimension is small. Before giving such bound, we illustrate the main idea with an example. Example 2.1. Consider q = 9 and let F6 be the 6-th function field defined by the Garcia-Stichtenoth’s tower over Fq. The Weierstrass semigroup H(Q6) at Q6 in F6 is H(Q6) = {0,243,486,513,540,567,594,621,648}∪ ∪{3n | n ∈ N and 3n ∈ [654,702]}∪{n ∈ N | n > 702}. We denote these three sets as A0, B0 and C0 respectively. For computing Z(H(Q6),µ,m) one should find i1, . . . , im−1 such that −(µ − 1) ≤ i1 < i2 < · · · < im−1 ≤ −1 and minimize #{α ∈ ∪m−1s=1 (is + H(Q6)) | α /∈ H(Q6)}. In this example we fix i1 = −20, thus: i1 + H(Q6) = {−20,223,466,493,520,547,574,601,628}∪ ∪{3n−20 | n ∈ N and 3n ∈ [654,702]}∪{n ∈ N | n > 682} = = (i1 + A 0)f ∪ (i1 + B0)∪ (i1 + C0). Note that i1 + A0 and H(Q6) are disjoint since −i1 = 20 < 27 and |x−y| ≥ 27 for any x,y ∈ A0 x 6= y. For the same reason for any −20 < i2 < · · · < im−1 ≤−1, we have that im−1 + A0, im−2 + A0, . . . , i2 + A0, i1+A 0 and H(Q6) are disjoint. It follows that ∪m−1v=1 (iv+A 0) ⊆{α ∈∪m−1v=1 (iv+H(Q6)) | α /∈ H(Q6)} and #∪m−1v=1 (iv + A 0) = ∑m−1 v=1 #(iv + A 0) = (m−1)#A0 = 9(m−1). The same argument does not hold for i + B0 (or i + C0) because there exists x,y ∈ B0 (or C0) such that |x−y| = 3 and −i1 > 3 thus it is possible that (iv + B0)∩B0 6= ∅ (or (iv + C0)∩C0 6= ∅) for some v = 1, . . . ,m−1. Note that #((i1 +C0)\C0) = i1 = 20, but (i1 +C0)\C0 may intersect A0∪B0. Therefore we consider (i1 + C 0)\ √ qN, in this way (i1 + C0)\(C0 ∪ √ qN) and H(Q6) are disjoint. It follows that if i1 = −20, then Z(H(Q6),µ,m) ≥ #∪m−1v=1 (iv + A 0) + #((i1 + C 0)\(C0 ∪ √ qN)) = (m−1) ·9 + ⌊ 202 3 ⌋ . As we can see from previous example, we do not consider the sets B0, i1 +B0, . . ., im−1 +B0 because of their intersections with other sets. In general, we will also consider all the possible values −i1 in the range [m−1,µ−1] to obtain the following bound. Theorem 2.2. Let ν be an even positive integer and q an even power of a prime. Consider two one- point algebraic geometric codes C2 = CL(D,µ2Q) ( C1 = CL(D,µ1Q) of length n built on the ν-th Garcia-Stichtenoth’s function field over Fq and µ = µ1 − µ2. For µ < q ν+1 2 , m = 1, . . . ,µ, consider u∗ = 2 3 ( 1 + ν 4 + logq ( m−1 2( √ q−1) )) and β = min{2q− ν+1 4 ( √ q − 1)(µ− 1) 3 2 + 1, 1 4 q ν−5 2 ( √ q − 1)−2 + 1}, we have that: Mm(C1,C2) ≥ n−µ1 + g(m) where g(m) =   min { (m−1)q ν 4 −u 2 + qu− 1 2 (1−q− 1 2 )−1 : if m > β, u ∈{logq(m−1)− 1 2 , logq(µ−1) + 3 2 } } (m−1)q ν 4 −u ∗ 2 + qu ∗−1 2 (1−q− 1 2 )−1 if m ≤ β,m 6= 1, 0 if m = 1. 41 O. Geil et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 37–47 Proof. By Theorem 1.2 we have that Mm(C1,C2) ≥ n − µ1 + Z(H(Qν),µ,m) thus we will estimate Z(H(Qν),µ,m). If m = 1, Z(H(Qν),µ,1) = 0, otherwise we denote the conductor of H(Qν) by c. Set −(µ − 1) ≤ i1 < · · · < im−1 ≤ −1, we define u(i1) = ⌊ logq(−i1) + 1 2 ⌋ , then qu(i1)− 1 2 ≤ −i1 < qu(i1)+ 1 2 . For the sake of simplicity we write u instead of u(i1). To estimate Z(H(Qν),µ,m) we consider the following two sets: A(i1, i2, . . . , iv) = {α ∈ ∪m−1v=1 (iv + A0(u)) | α /∈ H(Qν)} where A0(u) = ⋃ν 2 −u i=0 S i ν and C(i1) = (i1 + C 0)\H(Qν) where C0 = {α ∈ N | α > c}. Again, to simplify the notation we write A = A(i1, i2, . . . , iv), A0 = A0(u) and C = C(i1). By construction A ∪ C ⊆ {α ∈ ∪m−1s=1 (is + H(Qν)) | α /∈ H(Qν)} and A ∩ C = ∅. Thus we have that Z(H(Qν),µ,m) ≥ #A + #C. We start by computing the cardinality of A. By definition of A0 for any x,y ∈ A0, x 6= y there exist ix, iy ∈ {0, . . . , ν2 − u} such that x ∈ S ix ν and y ∈ S iy ν . We can assume without loss of generality that ix ≥ ij and x > y, then we obtain by (6) in Lemma 1.6 that x − y ≥ q ν−2ix+1 2 . Since µ < q ν+1 2 , then ix ≤ ν2 −u ≤ 0 and |x−y| ≥ q ν−2ix+1 2 ≥ q ν−2( ν 2 −u)+1 2 = qu+ 1 2 . Thus for x,y ∈ A0, x > y, we have that x−y ≥ qu+ 1 2 . Since −i1 < qu+ 1 2 , it follows that (j1 + A0)∩(j2 + A0) = ∅ for any j1,j2 ∈ [i1,0]. Therefore we have that #A = # ⋃m−1 v=1 (iv+A 0) = (m−1)#A0. By (2) in Lemma 1.6, we have #A0 = #( ⋃ν 2 −u i=0 S i ν) = q ν 4 −u 2 . Thus #A = (m−1)q ν 4 −u 2 . Furthermore, #C = #((i1 + C0)\H(Qν)) = #([c + i1,c)\H(Qν)) ≥ #([c + i1,c)\ √ qN) =⌊ −i1(1−q− 1 2 ) ⌋ where the inequality follows since H(Qν)∩ [0,c) ⊂ √ qN. Hence, Mm(C1,C2) ≥ n−µ1 + Z(H(Qν),µ,m) ≥ n−µ1 + min i1∈{−(µ−1),...,−(m−1)} (#A + #C) ≥ n−µ1 + min { (m−1)q ν 4 −u 2 + ⌊ −i1 ( 1−q− 1 2 )⌋ | | i1 ∈{−(µ−1), . . . ,−(m−1)} } . One could try to minimize the previous expression bounding u by logq(−i1) + 1 2 . However, the obtained bound is too loose. Hence, we consider the minimum among all possible values of u instead of i1: Mm(C1,C2) ≥ n−µ1 + min { (m−1)q ν 4 −u 2 + ⌊ qu− 1 2 ( 1−q− 1 2 )⌋ | | u ∈ {⌊ logq(m−1) + 1 2 ⌋ , ⌊ logq(m) + 1 2 ⌋ , . . . , ⌊ logq(µ−1) + 1 2 ⌋}} ≥ n−µ1 + min { (m−1)q ν 4 −u 2 + qu− 1 2 ( 1−q− 1 2 ) −1 | | u ∈ {⌊ logq(m−1) + 1 2 ⌋ , ⌊ logq(m) + 1 2 ⌋ , . . . , ⌊ logq(µ−1) + 1 2 ⌋}} ≥ n−µ1 + min { (m−1)q ν 4 −u 2 + qu− 1 2 ( 1−q− 1 2 ) −1 | | logq(m−1)− 1 2 ≤ u ≤ logq(µ−1) + 1 2 } , where the second to last inequality is obtained since −i1 ≥ qu− 1 2 . We define f(u) = (m − 1)q ν 4 −u 2 + qu− 1 2 ( 1−q− 1 2 ) −1. In this way our bound becomes: Mm(C1,C2) ≥ n−µ1 + min { f(u) | logq(m−1)− 1 2 ≤ u ≤ logq(µ−1) + 1 2 } . 42 O. Geil et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 37–47 By looking the derivative of f(u), one can see that f(u) only has a minimum at u∗ = 2 3 ( 1 + ν 4 + logq ( m−1 2( √ q−1) )) . However, it does not always hold that logq(m − 1) − 1/2 ≤ u∗ ≤ logq(µ − 1) + 1/2. This happens when either u∗ < logq(m − 1) − 1 2 or u∗ > logq(µ − 1) + 1 2 . The first case is equivalent to m > 1 4 q ν−5 2 ( √ q−1)−2 + 1, the second one to m > 2q− ν+1 4 ( √ q−1)(µ−1) 1 2 + 1. Thus if m > β = min{2q− ν+1 4 ( √ q−1)(µ−1) 3 2 + 1, 1 4 q ν−5 2 ( √ q−1)−2 + 1}, then the minimum is reached in logq(m−1)− 1 2 or logq(µ−1) + 1 2 . The previous result has an asymptotic implication as well. Corollary 2.3. Let q be an even power of a prime, 0 ≤ R̃2 ≤ R̃1 < 1, and R̃ = R̃1 − R̃2 < 1√q−1. There exists a sequence of pairs of one-point AG codes C2,i = CL(Di,µ2,iQ) ( C1,i = CL(Di,µ1,iQ), such that: ni = n(C2,i) = n(C1,i) →∞, µj,i/ni → R̃j when i →∞, for j = 1,2. For a given ρ let mi be such that mi/ni → ρ when i →∞ and let M = lim inf Mmi(C1,i,C2,i)/ni. It holds that: M ≥ 1− R̃1 + g(ρ), where g(ρ) =   minw∈{ρ,R̃} { ρ(w(q − √ q))− 1 2 + w q (q − √ q) } if ρ > β,( 2ρ2 q )1 3 + 1√ q ( ρ 2 )2 3 if ρ ≤ β,ρ 6= 0, 0 if ρ = 0, and β = min { 1 4 q− 5 2 ( √ q −1)−3,2q− 1 4 (R √ q −R) 3 2 } . Proof. Consider the Garcia-Stichtenoth’s tower (F1,F2, . . .) over Fq described at the end of section 1, and 0 ≤ µ2,i < µ1,i ≤ ni − 1 with µj,i/ni → R̃j for j = 1,2. Now consider Cj,i = CL(Di,µj,iQ) for j = 1,2, where Di is a divisor of degree ni − 1 and with ni − 1 distinct places not containing Qi, which is the unique pole of x1 ∈ Fi. By taking the limit of the bound obtained in Theorem 2.2, the corollary holds. Note that if we assume that C2,i is the zero code for all i, then lim inf Mmi(C1,i,{~0}) is the asymptotic value of the mi-th general Hamming weight of Ci,1. For R̃ < 14(q−√q), the bound in Corollary 2.3 is sharper than the one obtained in [5, Theorem 23]. In Figure 1 we compare the bound from Corollary 1.7 (the dashed curve) with the bound from Corollary 2.3 (the solid curve). The first axis represents ρ = limmi/ni, and the second axis represents δ = lim inf Mmi(C1,i,{~0}). 3. The highest RGHW As we illustrated at the beginning of section 1, for any n − M`(C1,C2) + 1 obtained shares an eavesdropper may recover at least one q-bit of the secret. In this section, for 2g − 1 ≤ µ2 < µ1 ≤ n− 1, we obtain a refined bound for the highest RGHW of two one-point algebraic geometric codes obtained from Garcia-Stichtenoth’s towers, i.e. M`(C1,C2). Proposition 3.1. Let ν be an even positive integer and 2g−1 ≤ µ2 < µ1 ≤ n−1. Consider two one-point algebraic geometric codes C2 = CL(D,µ2Q) ( C1 = CL(D,µ1Q) built on the ν-th Garcia-Stichtenoth’s tower. We have that µ = µ1 −µ2 = dim(C1)−dim(C2) = ` and Mµ(C1,C2) ≥ n−dimC2 if µ ≥ q ν−1 2 , 43 O. Geil et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 37–47 Figure 1. Mµ(C1,C2) ≥ n−dimC2 − ( q ν−1 2 bν+1 2 −logq(µ)c−1∑ i=1 (q1− i 2 −q− i 2 )+ +(q ν+1 2 −bν+1 2 −logq(µ)c −µ)q bν+1 2 −logq(µ)c 2 ) if µ < q ν−1 2 . Proof. Since 2g − 1 ≤ µ2 < µ1 ≤ n − 1, then µ = µ1 − µ2 = ` [5, Lemma 12]. By Theorem 1.2, we have that Mµ(C1,C2) ≥ n−µ1 + Z(H(Q),µ,µ), where Z(H(Q),µ,µ) = #{α ∈∪µ−1v=1(−v + H(Q)) | α /∈ H(Q)}. For any x,y ∈ H(Q), we have that |x − y| ≤ q ν−1 2 , thus if µ ≥ q ν−1 2 then (∪µ−1v=0 − v + H(Q)) = N0 ∪{−1, . . . ,−(µ−1)}. It follows that Z(H(Q),µ,µ) = (N0\H(Qν))∪{−1, . . . ,−(µ−1)}) = g +µ−1. Thus Mµ(C1,C2) ≥ n−µ1 + g + µ− 1. Moreover since µ2 ≥ 2g − 1, then µ2 −g + 1 = dimC2 and the first part of the proposition holds. For ` ≤ q ν−1 2 we claim that: Z(H(Q),µ,µ) = µ + g −1− (q ν−1 2 u1(µ)−1∑ i=1 (q1− i 2 + q− i 2 ) + u2(µ)q u1(µ) 2 ), where u1(µ) = ⌊ ν+1 2 − logq(µ) ⌋ and u2(µ) = q ν−2u1(µ)+1 2 −µ. This means that µ = q ν+1 2 −u1(µ) −u2(µ). We prove it by decreasing induction on µ, for q ν−1 2 ≥ µ ≥ 1. For the basis step we have µ = q ν−1 2 , thus u1(µ) = 1 and u2(µ) = 0. According to our claim, Z(H(Q),µ,µ) is equal to µ + g − 1, which has been already proven in the first part of this proposition. For the inductive step, we now assume that our claim is true for Z(H(Q),µ,µ) and we want to prove it for Z(H(Q),µ−1,µ−1). We note that: Z(H(Q),µ,µ) = #{α ∈∪µ−2v=1(−v + H(Q)) | α /∈ H(Q)}+ #{α ∈−(µ−1) + H(Q)) | α /∈∪µ−2v=0(−v + H(Q))} = Z(H(Q),µ−1,µ−1) + #T(µ), where T(µ) = {α ∈ −(µ − 1) + H(Q) | α /∈ ∪µ−2v=0(−v + H(Q))}. Thus Z(H(Q),µ − 1,µ − 1) = Z(H(Q),µ,µ) − #T(µ). We consider two cases: µ such that q ν−2u1(µ−1)−1 2 < µ− 1 < q ν−2u1(µ−1)+1 2 and µ−1 = q ν−2u1(µ−1)+1 2 −1. 44 O. Geil et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 37–47 Let us consider the first case, µ such that q ν−2u1(µ−1)−1 2 < µ−1 < q ν−2u1(µ−1)+1 2 , then u1(µ−1) = u1(µ) and u2(µ−1) = u2(µ) + 1. By induction we have that Z(H(Q),µ,µ) = µ + g−1−(q ν−1 2 ∑u1(µ)−1 i=1 (q 1− i 2 −q− i 2 ) + u2(µ)q u1(µ) 2 ). We claim that #T(µ) = q u1(µ) 2 . By (5) in Lemma 1.6, for any x,y ∈ ∪u1(µ−1)i=0 S i ν, x > y we have that x−y ≥ q ν−2u1(µ−1)+1 2 , moreover µ−1 < q ν−2u1(µ−1)+1 2 . Therefore, one has that (−(µ−1) +∪u1(µ−1)i=0 S i ν)∩ (∪µ−2v=0 − v + H(Q)) = ∅. Then −(µ − 1) + ∪ u1(µ−1) i=0 S i ν ⊆ T(µ). Actually, the previous inclusion is an equality. We shall prove it by contradiction: we assume that there exists an element x ∈ T(µ) but not in −(µ−1) +∪u1(µ−1)i=0 S i ν. By definition of T(µ), we have that x ∈−(µ−1) + (S∞ν ∪ (∪ j/2 i=u1(µ−1)+1 Siν)) where j = 2bν/2c. Consider y < x to be the previous element of x in −(µ−1) + H(Q). By (3) and (4) in Lemma 1.6, we have that x−y ≤ q ν−2u1(µ−1)−1 2 < µ−1. Thus, −(µ−2) ≤−(µ−1) + (x−y) ≤ 0 and x ∈−(µ−1) + (x−y) + H(Q) ⊆∪µ−2v=0(−v + H(Q)). This means x /∈ T(µ), which is a contradiction. It follows that #T(µ) = # ( −(µ−1)+∪u1(µ−1)i=0 S i ν ) = # ( ∪u1(µ−1)i=0 S i ν ) = q u1(µ−1) 2 = q u1(µ) 2 . We consider now the second case, µ−1 = q ν−2u1(µ−1)+1 2 −1, then u1(µ−1) = u1(µ)+1 and u2(µ−1) = 0. By using the same argument as in the first case, one may also prove that #T(µ) = q u1(µ) 2 . Corollary 3.2. By using the same notation of the previous proposition, for 2g ≤ µ2 < µ1 < n− 1 and ` ≥ q ν−1 2 we have that M`(C1,C2) = n−dimC2. Proof. By 3.1, M`(C1,C2) ≥ n− dimC2. And M`(C1,C2) ≤ n− dimC2, by the Singleton bound for one-point algebraic geometric codes and the result holds. This means that for ` ≥ q ν−1 2 the Singleton bound is reached. Note that for ` < q ν−1 2 , the bound in Proposition 3.1 allows us to get a refined bound since we could consider hc−m. As before, this result has an asymptotically implication: Corollary 3.3. Let q be an even power of a prime, 2√ q−1 ≤ R̃2 ≤ R̃1 < 1, and R̃ = R̃1 − R̃2. There exists a sequence of one-point algebraic geometric codes C2,i = CL(Di,µ2,iQ) ( C1,i = CL(Di,µ1,iQ), µi = µ1,i − µ2,i, such that: ni = n(C2,i) = n(C1,i) → ∞, µj,i/ni → R̃j when i → ∞, for j = 1,2. Let `i = dimC1,i −dimC2,i, M = lim inf M`i(C1,i,C2,i)/ni, Rj = lim dim Ci,j ni for j = 1,2, and R = R1 −R2, we have that: M = 1−R2 if R ≥ 1 q − √ q and M ≥ 1−R2 − ( 1 q − √ q (−blogq(R(1− 1√q ))c−1∑ i=1 (q1− i 2 −q− i 2 )+ +q 1+ 1 2 blogq(R(1− 1√ q ))c ) + Rq −1 2 blogq(R(1− 1√ q ))c ) if R < 1 q − √ q . 45 O. Geil et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 37–47 Proof. Let (F1,F2, . . .) be the tower of function fields defined in section 1, and 0 ≤ µ2,i < µ1,i ≤ ni−1 with µj,i/ni → R̃j for j = 1,2, where ni is the length of rational places of Fi. Now consider Cj,i = CL(Di,µj,iQ) for j = 1,2, where Di is a divisor of degree ni−1, with ni−1 distinct places not containing Q, which is the unique pole of x1 ∈Fi. Since we assume that 2√q−1 ≤ R̃2 ≤ R̃1 < 1 then Rj = R̃j − 1√q−1, for j = 1,2 and R = R̃. By taking the limit of the result obtained in Proposition 3.1 and Corollary 3.2 the result holds. Note that if blogq(R(1− 1√ q ))c = logq(R(1− 1√ q )) then the formulas in Corollary 3.3 become: M = 1−R1 if R ≥ 1 q − √ q and M ≥ 1−R1 − 1 q − √ q − logq(R(1− 1√ q ))−1∑ i=1 ( q1− i 2 −q− i 2 ) if R < 1 q − √ q . Corollary 1.7 can be used for ρ ≤ min{R, 1√ q−1}. If C2,i = {0} for all i, then the value M of Corollary 3.3 represents the asymptotic value of the highest GHW of Ci,1. Note that Corollary 3.3 can be used for any value of R, but 1.7 cannot. References [1] M. Bras–Amorós, M. O’Sullivan, The order bound on the minimum distance of the one–point codes associated to the Garcia–Stichtenoth tower, IEEE Trans. Inform. Theory 53(11) (2007) 4241–4245. [2] H. Chen, R. Cramer, S. Goldwasser, R. de Haan, V. Vaikuntanathan, Secure computation from random error correcting codes, In Advances in cryptology—EUROCRYPT 2007, Lecture Notes in Comput. Sci. 4515 (2007) 291–310. [3] A. Garcia, H. Stichtenoth, On the asymptotic behaviour of some towers of function fields over finite fields, J. Number Theory 61(2) (1996) 248–273. [4] O. Geil, S. Martin, Relative generalized Hamming weights of q−ary Reed–Muller codes, to appear in Adv. Appl. Commun. [5] O. Geil, S. Martin, U. Martínez-Peñas, R. Matsumoto, D. Ruano, Asymptotically good ramp secret sharing schemes, arXiv preprint arXiv:1502.05507, 2015. [6] O. Geil, S. Martin, R. Matsumoto, D. Ruano, Y. Luo, Relative generalized Hamming weights of one–point algebraic geometric codes, IEEE Trans. Inform. Theory 60(10) (2014) 5938–5949. [7] J. Kurihara, T. Uyematsu, R. Matsumoto, Secret sharing schemes based on linear codes can be precisely characterized by the relative generalized Hamming weight, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E95–A(11) (2012) 2067–2075. [8] Z. Liu, W. Chen, Y. Luo, The relative generalized Hamming weight of linear q−ary codes and their subcodes, Des. Codes Cryptogr. 48(2) (2008) 111–123. [9] Y. Luo, C. Mitrpant, A. J. Han Vinck, K. Chen, Some new characters on the wire–tap channel of type II, IEEE Trans. Inform. Theory 51(3) (2005) 1222–1229. [10] R. Pellikaan, H. Stichtenoth, F. Torres, Weierstrass semigroups in an asymptotically good tower of function fields, Finite Fields Appl. 4(4) (1998) 381–392. [11] M. A. Tsfasman, S. G. Vlăduţ, Geometric approach to higher weights, IEEE Trans. Inform. Theory 41(6, part 1) (1995) 1564–1588. [12] V. K. Wei, Generalized Hamming weights for linear codes, IEEE Trans. Inform. Theory 37(5) (1991) 1412–1418. 46 http://dx.doi.org/10.1109/TIT.2007.907522 http://dx.doi.org/10.1109/TIT.2007.907522 http://link.springer.com/chapter/10.1007%2F978-3-540-72540-4_17 http://link.springer.com/chapter/10.1007%2F978-3-540-72540-4_17 http://link.springer.com/chapter/10.1007%2F978-3-540-72540-4_17 http://dx.doi.org/10.1006/jnth.1996.0147 http://dx.doi.org/10.1006/jnth.1996.0147 https://arxiv.org/abs/1407.6185 https://arxiv.org/abs/1407.6185 http://dx.doi.org/10.1109/TIT.2014.2345375 http://dx.doi.org/10.1109/TIT.2014.2345375 http://doi.org/10.1587/transfun.E95.A.2067 http://doi.org/10.1587/transfun.E95.A.2067 http://doi.org/10.1587/transfun.E95.A.2067 http://dx.doi.org/10.1007/s10623-008-9170-1 http://dx.doi.org/10.1007/s10623-008-9170-1 http://dx.doi.org/10.1109/TIT.2004.842763 http://dx.doi.org/10.1109/TIT.2004.842763 http://dx.doi.org/10.1006/ffta.1998.0217 http://dx.doi.org/10.1006/ffta.1998.0217 http://dx.doi.org/10.1109/18.476213 http://dx.doi.org/10.1109/18.476213 http://dx.doi.org/10.1109/18.133259 http://dx.doi.org/10.1109/18.133259 O. Geil et al. / J. Algebra Comb. Discrete Appl. 4(1) (2017) 37–47 [13] J. Zhang K. Feng, Relative generalized Hamming weights of cyclic codes, arXiv preprint arXiv:1505.07277, 2015. 47 Introduction Small codimension The highest RGHW References