ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.284970 J. Algebra Comb. Discrete Appl. 4(2) • 207–217 Received: 12 June 2015 Accepted: 8 June 2016 Journal of Algebra Combinatorics Discrete Structures and Applications The extension problem for Lee and Euclidean weights Research Article Philippe Langevin, Jay A. Wood Abstract: The extension problem is solved for the Lee and Euclidean weights over three families of rings of the form Z/NZ: N = 2`+1, N = 3`+1, or N = p = 2q + 1 with p and q prime. The extension problem is solved for the Euclidean PSK weight over Z/NZ for all N. 2010 MSC: 94B05 Keywords: Extension problem, Lee weight, Euclidean weight, Egalitarian weight 1. Introduction One of the themes of the Mini-cours at the Lens conference was the extension theorem of MacWilliams. In its original form, this theorem says that any linear isomorphism between linear codes defined over a finite field that preserves the Hamming weight must extend to a monomial transformation. This result has been generalized in several directions, including: for linear codes defined over finite Frobe- nius rings with respect to the Hamming weight [12] or the homogeneous weight [7]; for linear codes defined over finite Frobenius rings with respect to symmetrized weight compositions [11] (with an improved proof in [2]); for linear codes defined over finite commutative chain rings with respect to any weight function satisfying certain conditions [13, 14]; for linear codes equipped with a weight function having maximal symmetry and satisfying certain conditions, defined over products of finite chain rings [6] or over a finite principal ideal ring [5]. Despite all this progress, there are glaring gaps in our knowledge: does the extension theorem hold for linear codes defined over Z/NZ with respect to the Lee weight or the Euclidean weight? In general, we do not know. The purpose of this paper is to describe what we do know. In [15, Examples 3.7 and 3.9], it was claimed that the extension theorem holds for the Lee and Euclidean weights over the rings Z/2kZ, Z/3kZ, Philippe Langevin; Laboratoire IMATH, Université de Toulon, 83957 La Garde Cedex, France (email: langevin@univ-tln.fr). Jay A. Wood (Corresponding Author); Department of Mathematics, Western Michigan University, 1903 W. Michigan Ave., Kalamazoo, MI 49008–5248 USA (email: jay.wood@wmich.edu). 207 P. Langevin, J. A. Wood / J. Algebra Comb. Discrete Appl. 4(2) (2017) 207–217 and Z/pZ for a prime p of the form p = 2q + 1 with q prime. Proofs of those claims will constitute the bulk of this paper. Barra [1] has proved that the extension theorem holds for the Lee weight over Z/pZ for a prime p of the form p = 4q + 1 with q prime. In [15, Example 3.8], it was claimed that the extension theorem holds for Euclidean PSK weight over the rings Z/3kZ and Z/pZ for a prime p of the form p = 2q + 1 with q prime. For this weight, we give a simple proof that works for all Z/NZ. This proof is similar to the proof in [2, Theorem 6.6] for the homogeneous weight over any finite Frobenius ring. 2. Background Let R = Z/NZ be the ring of integers modulo N. Every element x of R is represented uniquely by an integer a satisfying −N/2 < a ≤ N/2 with x ≡ a mod N. The Lee weight wL(x) (resp., Euclidean weight wE(x)) of x ∈ R is the ordinary absolute value |a| (resp., the square |a|2) of the representative a. Alternatively, if one represents x ∈ R by a unique integer representative b satisfying 0 ≤ b < N with x ≡ b mod N, then the Lee weight and the Euclidean weight have the form wL(x) = { b, 0 ≤ b ≤ N/2, N − b, N/2 ≤ b < N; wE(x) = { b2, 0 ≤ b ≤ N/2, (N − b)2, N/2 ≤ b < N. There is another Euclidean weight, the Euclidean PSK weight wPSK, which is used in phase-shift key modulation. It is defined using the squared Euclidean distance in the complex numbers; for x ∈ R, wPSK(x) = |exp(2πix/N) − 1|2 = 2 − 2 cos(2πx/N). Note that all three weights satisfy w(−x) = w(x), for x ∈ R. The Lee and the Euclidean weights can be extended to real-valued functions (still denoted by wL, wE, and wPSK) on the product Rn: wL(x) = n∑ i=1 wL(xi), wE(x) = n∑ i=1 wE(xi), wPSK(x) = n∑ i=1 wPSK(xi), for x = (x1,x2, . . . ,xn) ∈ Rn. A monomial transformation T on Rn is an R-module isomorphism T : Rn → Rn of the form T(x1,x2, . . . ,xn) = (u1xσ(1),u2xσ(2), . . . ,unxσ(n)), for (x1,x2, . . . ,xn) ∈ Rn, where u1,u2, . . . ,un are units of R and σ is a permutation of the set {1, 2, . . . ,n}. If G is a subgroup of the group of units of R and each ui ∈ G, we say that T is a G-monomial transfor- mation. In the case where G = {±1}, i.e., each ui = ±1, we say that T is a signed permutation. The following proposition is now immediate. Proposition 2.1. Suppose T : Rn → Rn is a signed permutation. Then T preserves the Lee and Euclidean weights. That is, for every x ∈ Rn, wL(T(x)) = wL(x), wE(T(x)) = wE(x), and wPSK(T(x)) = wPSK(x). 208 P. Langevin, J. A. Wood / J. Algebra Comb. Discrete Appl. 4(2) (2017) 207–217 Conversely, the signed permutations are precisely the linear isometries of Rn with respect to any of the three weights. Proposition 2.2. Let w be one of the weights wL,wE,wPSK, and suppose f : Rn → Rn is an R-module homomorphism that preserves w: w(f(x)) = w(x), for all x ∈ Rn. Then f is a signed permutation. Proof. Observe that f is injective. Indeed, only the zero vector has weight zero, so if f(x) = 0, then 0 = w(f(x)) = w(x) implies x = 0. Because Rn is a finite set, f is also surjective, hence an R-module isomorphism. Let ei = (0, . . . , 0, 1, 0, . . . , 0), with the 1 in position i, 1 ≤ i ≤ n. Then w(1) = w(ei) = w(f(ei)). But w(1) = w(−1) is the smallest positive value of w on R, so it follows that f(ei) = ±ej for some j, 1 ≤ j ≤ n. Because f is known to be an isomorphism, it follows that f is a signed permutation. Again, let w be one of the weights wL,wE,wPSK. We say that R = Z/NZ has the extension property with respect to w if the following property is satisfied for every R-submodule C ⊆ Rn and every R- module homomorphism f : C → Rn: if f preserves w, w(f(x)) = w(x), x ∈ C, then f extends to a signed permutation. That is, there exists a signed permutation T defined on all of Rn such that T(x) = f(x) for x ∈ C. Another way to view the extension property is that every linear w-isometry on C extends to a linear w-isometry on Rn. The main results of this paper are the following theorems. Theorem 2.3. The rings in the following list have the extension property with respect to the Lee weight wL and the Euclidean weight wE: 1. R = Z/2`+1Z, l ≥ 0; 2. R = Z/3`+1Z, l ≥ 0; 3. R = Z/pZ, with prime p of the form p = 2q + 1, q prime. Remark 2.4. Barra proved that R = Z/pZ, with prime p of the form p = 4q + 1, q prime, has the extension property with respect to the Lee weight wL [1]. Remark 2.5. (Added in proof.) After the submission of this paper, the authors, together with Serhii Dyshko, have extended Theorem 2.3, first to the cases R = Z/pZ for all primes p [3], and then to the cases R = Z/p`+1Z for all primes p and ` ≥ 0 [P. Langevin, J. A. Wood, The extension theorem for the Lee and Euclidean weights over Z/pkZ, in preparation, 2016]. The methods used for the new results are very different from those of Sections 4 and 5 of this paper. Theorem 2.6. For any positive integer N, the ring R = Z/NZ has the extension property with respect to the Euclidean PSK weight wPSK. After an explanation of the method of attack in Section 3 and an analysis of cases in Section 4, the proof of Theorem 2.3 appears in Section 5. The proof of Theorem 2.6 appears in Section 6. 3. Method of attack for Theorem 2.3 In this section we will describe how the proof of Theorem 2.3 reduces to showing that certain Fourier coefficients are nonzero. In both this section and the next, we will use some basic facts from number theory, such as the structure of the group of units for Z/NZ and the form of cyclotomic polynomials, which may be found in textbooks such as [10]. There is an extension theorem for general weight functions over a finite Frobenius ring, [13, The- orem 3.1]. The theorem below is the form that this theorem takes in the context of the Lee or the Euclidean weights on the Frobenius ring R = Z/NZ. 209 P. Langevin, J. A. Wood / J. Algebra Comb. Discrete Appl. 4(2) (2017) 207–217 To establish notation, let R = Z/NZ and let w be one of wL, wE, or wPSK on R. Let m = bN/2c be the largest integer less than or equal to N/2. Form an m×m real matrix Aw as follows. The entry of Aw in position (i,j), 1 ≤ i,j ≤ m, equals w(ij), the value of the weight function on the product of i and j in the ring R. Theorem 3.1 ([13, Theorem 3.1]). If the matrix Aw is nonsingular over C, then R has the extension property with respect to w. Remark 3.2. In fact, Theorem 3.1 applies to any complex-valued weight w on R that satisfies two properties: w(0) = 0 and Sym(w) = {±1}. Here, Sym(w) denotes the symmetry group of the weight w: Sym(w) = {u ∈ R : u is a unit, and w(ux) = w(x) for all x ∈ R}. Example 3.3. For R = Z/9Z, the determinants of the matrices for wL and wE are detAL = det   1 2 3 4 2 4 3 1 3 3 0 3 4 1 3 2   = 189, detAE = det   1 4 9 16 4 16 9 1 9 9 0 9 16 1 9 4   = 45 927. Remark 3.4. Maple has been used to verify that R = Z/NZ has the extension property for wL and wE for N ≤ 2048. The smallest singular values of the matrices AL and AE were calculated and seen to be nonzero. Barra has verified the extension property for wL over R = Z/pZ for the first 2012 primes p [1, p. 44]. Now assume that R = Z/NZ is a local ring, so that N equals a prime power; R is then a finite commutative chain ring. We continue to assume that w is one of wL,wE,wPSK. In this chain ring context, the determinant detAw can be factored into linear expressions that are Fourier transforms of values of the weight function w, [14, Theorem 7]. We explain this next. Suppose R = Z/p`+1Z, with p prime. Let U be the group of units of R. Then |U| = φ(p`+1) = p`(p− 1), where φ is Euler’s totient function. The group U is cyclic when p is an odd prime. For powers of 2, U is cyclic for Z/2Z and Z/4Z; for Z/2`+1Z, l ≥ 2, U is isomorphic to the product of a cyclic group of order 2 times a cyclic group of order 2`−1, with generators for the two cyclic factors being the residue classes of −1 and 5, respectively. The group U acts on the ring R by ring multiplication. The orbits have the form Oi = {upi : u ∈U}, i = 0, 1, . . . ,` + 1. The orbit Oi equals the set-theoretic difference of ideals (pi)\(pi+1), where (a) = Ra denotes the principal ideal generated by a ∈ R. Because U is abelian, the stabilizer subgroup of a point in an orbit Oi, i = 0, 1, . . . ,`+ 1, is independent of the point chosen; the stabilizer subgroup depends only on the orbit. Denote the stabilizer subgroup of a point of Oi by Ui. Then Ui = {u ∈ U : upi = pi}, and Oi can be identified with the coset space U/Ui. The ideal (pi) has order |(pi)| = p`+1−i, i = 0, 1, . . .` + 1, so that |Oi| = p`+1−i −p`−i = p`−i(p− 1) and |Ui| = pi. The group of complex characters (group homomorphisms from U to the multiplicative group of nonzero complex numbers) of the group U will be denoted Û. A pair (π,Oi) consisting of a character π ∈ Û and a U-orbit Oi is admissible if Ui ⊆ ker π. For π ∈ Û, let iπ be the largest integer j ≤ ` such that (π,Oj) is admissible. Because U0 = {1}, every pair (π,O0) is admissible, so that iπ ≥ 0 for all π ∈ Û. Given a subgroup H ⊆ U, the annihilator (Û : H) of H in Û is defined by (Û : H) = {π ∈ Û : π(H) = 1}. Let U = {±1} ⊆ U. Suppose a character π satisfies (1) π ∈ (Û : U) and (2) (π,Oi) is admissible. For w equal to wL,wE,wPSK, we define w̌(π,i) = ∑ u∈U/UUi w(upi)π(u). (1) 210 P. Langevin, J. A. Wood / J. Algebra Comb. Discrete Appl. 4(2) (2017) 207–217 Observe that this character sum is well-defined. Here is the factorization of detAw, for w equal to wL,wE,wPSK. Theorem 3.5 ([14, Theorem 7]). Let R = Z/p`+1Z and U = {±1}⊆U. For w equal to wL,wE,wPSK, there exists a nonzero integer constant C such that detAw = C ∏ π∈(Û:U) w̌(π,iπ) 1+iπ. Remark 3.6. Theorem 3.5 also holds for any weight w satisfying the conditions in Remark 3.2. Theo- rem 3.5 can be viewed as a generalization of the factorization of the group determinant given by Dedekind and Frobenius in 1896 [4]. Example 3.7. For R = Z/9Z, the factorizations have the form detAw = 3w(3)2[w(1) + w(2)ζ + w(4)ζ2][w(1) + w(2)ζ2 + w(4)ζ] = 3w(3)2[w(1)2 −w(1)w(2) −w(1)w(4) + w(2)2 −w(2)w(4) + w(4)2], where ζ is a primitive third root of unity in C. Using wL,wE, we recover the values of detAw in Example 3.3. For additional details of this computation, see [14, Example 12]. Remark 3.8. In order to prove Theorem 2.3, we will show that w̌(π,iπ) 6= 0 for all π ∈ (Û : U) and then appeal to Theorems 3.1 and 3.5. To illustrate the type of argument that will be used in the next two sections, consider the factorization of detAw in Example 3.7. Under what conditions could one of the factors vanish? In the example, there are three factors. One possibility is w(3) = 0. For the other two factors, make use of the minimal polynomial for ζ over Q, i.e., ζ2 + ζ + 1 = 0. Then w(1) + w(2)ζ + w(4)ζ2 = (w(1) −w(4)) + (w(2) −w(4))ζ, w(1) + w(4)ζ + w(2)ζ2 = (w(1) −w(2)) + (w(4) −w(2))ζ. Both these factors would vanish when w(1) = w(2) = w(4), and, if the values of w are rational numbers, this is the only way in which these factors could vanish. For wL and wE, it is easy to see that the factors do not vanish. 4. Analysis of cases In this section we will analyze the structure of the orbits Oi and the stabilizer subgroups Ui that occur in the character sum (1). The case where N = 2`+1 Let R = Z/2`+1Z. When R = Z/2Z or R = Z/4Z, the extension property for wL or wE follows easily from Theorem 3.1 (also, see Remark 3.4). For the rest of the discussion, we assume ` ≥ 2. Then the group of units U of R is isomorphic to the product of a cyclic group B of order 2 and a cyclic group C of order 2`−1, with B and C generated by the residue classes of −1 and 5, respectively. In particular, B = U = {±1}. In Theorem 3.5, it is the characters π ∈ (Û : U), i.e., characters such that π(−1) = 1, that contribute to the factorization of detAw. Since (Û : U) ∼= (U/U)̂ and U ∼= U ×C, we see that U/U ∼= C is a cyclic group of order 2`−1, and (Û : U) ∼= Ĉ. 211 P. Langevin, J. A. Wood / J. Algebra Comb. Discrete Appl. 4(2) (2017) 207–217 The orbits of U on R have the form Oi = {u2i : u ∈U}, i = 0, 1, . . . ,` + 1, and the stabilizer subgroup of the point 2i ∈Oi is Ui = {1 + m2`+1−i : 0 ≤ m < 2i}, i = 0, 1, . . . ,`. When i = ` + 1, U`+1 = U. The stabilizer subgroups satisfy {1} = U0 ⊂U1 ⊂ ···⊂Ul = U`+1 = U, and |Ui| = 2i (for 0 ≤ i ≤ `). Observe that −1 ∈Ui only for i = ` or ` + 1. Thus, for i < `, the image of Ui under the projection U ∼= U ×C → C ∼= U/U is the unique subgroup in C of order 2i. In particular, Ui is cyclic, for i < `. Proposition 4.1. Let R = Z/2`+1Z, ` ≥ 2, and U = {±1}. If π ∈ (Û : U), then ker π = UUiπ. Proof. Take any π ∈ (Û : U). Under the isomorphism (Û : U) ∼= Ĉ, we can view π as a character on C. From that perspective, ker π is a subgroup E of C of order 2k, for some k ≤ ` − 1 (since C is a group of order 2`−1). Note that E is the image of Uk under the projection U → C. When we view π as a character on U, we see that Uk ⊂ ker π, that ker π ∼= U ×E (since π ∈ (Û : U)), and that ker π = UUk. If k < `− 1, we claim that k = iπ, i.e., that k is the largest integer j such that Uj ⊂ ker π. On the one hand, ker π ∼= U ×E has order 2k+1 but is not cyclic. If Uk+1 ⊂ ker π, then Uk+1 = ker π, because both groups have order 2k+1. But Uk+1 is cyclic, forcing ker π to be cyclic as well; contradiction. Thus, if k < `− 1, we have iπ = k and ker π = UUiπ. If k = `− 1, then ker π ∼= U ×E has order 2`, so that ker π = U and π is the trivial character. In that case, iπ = `, so that ker π = U = U` = UU`. The case where N = 3`+1 We first assume that N = p`+1, with p an odd prime. We will specialize to p = 3 later. Set R = Z/p`+1Z, and let U be its group of units. The group U is cyclic of order p`(p− 1). Let U = {±1}; then U/U is cyclic of order p`(p− 1)/2. The orbits of U on R have the form Oi = {upi : u ∈U}, i = 0, 1, . . . ,` + 1, and the stabilizer subgroup of the point pi ∈Oi is Ui = {1 + mp`+1−i : 0 ≤ m < pi}, i = 0, 1, . . . ,`. When i = ` + 1, U`+1 = U. The stabilizer subgroups satisfy {1} = U0 ⊂U1 ⊂ ···⊂U` ⊂U`+1 = U, and |Ui| = pi (for 0 ≤ i ≤ `). Observe that −1 ∈Ui only for i = ` + 1. Proposition 4.2. Let R = Z/3`+1Z and U = {±1}. If π ∈ (Û : U), then ker π = UUiπ. Proof. Take any π ∈ (Û : U). Viewing π as a character on U/U, ker π is a subgroup of the cyclic group U/U, which, for a general odd prime p, has order p`(p − 1)/2. For a general odd prime p, there is not much control on the order of ker π. But this proposition assumes that p = 3, so that the cyclic group U/U has order 3`. Thus ker π is the unique subgroup of order 3k for some k ≤ l. Under the projection U → U/U, Ui projects to a subgroup of order 3i (for i ≤ `) because −1 6∈ Ui. Thus, when we view π as a character on U, we see that Uk ⊂ ker π, and ker π = UUk has order 2 · 3k. Note that Uk+1 6⊆ ker π by size considerations, so that iπ = k and ker π = UUiπ. For i = ` + 1, ker π = U, so that iπ = ` and ker π = UUiπ. 212 P. Langevin, J. A. Wood / J. Algebra Comb. Discrete Appl. 4(2) (2017) 207–217 The case where N = p = 2q + 1, p, q prime Let R = Z/pZ, where p is prime and p = 2q + 1, with q prime. Then the group of units U is cyclic of order p− 1 = 2q. Set U = {±1}; then U/U is cyclic with prime order q. Because R is a field, the orbit structure of U acting on R is very simple. There are only two orbits: O0 = U = R \ (0) and O1 = (0). The stabilizer subgroups of a point are U0 = {1} and U1 = U, respectively. Proposition 4.3. Let R = Z/pZ, with prime p satisfying p = 2q + 1, q prime. Set U = {±1}. If π ∈ (Û : U), then ker π = UUiπ. Proof. Take any π ∈ (Û : U). Because U/U has prime order, ker π (viewed as a subgroup of U/U) is either trivial or all of U/U. When viewing π as a character on U, ker π = U or ker π = U. In the first case, iπ = 0, so that ker π = U = UU0; in the second case, iπ = 1, and ker π = U = UU1. A common corollary Propositions 4.1, 4.2, and 4.3 all lead to a common corollary. Corollary 4.4. Let R = Z/NZ, with, respectively, N = 2`+1, N = 3`+1, or N = p = 2q + 1, with p and q prime. Let U = {±1}. Let w be wL or wE on R. For any π ∈ (Û : U), • the quotient groups U/UUj are cyclic groups of prime power order; • the character π, viewed as a homomorphism π : U/UUiπ → C, is injective; and • the function f : U/UUiπ → Q, f(u) = w(upiπ ), is well-defined and injective. (Here, p is 2, 3, or p, respectively.) Proof. The group U/UUj is a quotient of the group U/U, which is cyclic of prime power order (under the hypotheses on N). By Propositions 4.1, 4.2, and 4.3, ker π = UUiπ, so that the character π viewed as π : U/UUiπ → C is injective. That the function f is well-defined and injective follows from the definition of Uiπ and the ±-symmetry of w (i.e., w(−x) = w(x), for x ∈ R). 5. Proof of Theorem 2.3 The proof of Theorem 2.3 will depend upon understanding the Fourier transform of a function defined on a cyclic group of prime power order. In this section we isolate the necessary lemma that will be used and then prove Theorem 2.3. Let p be a prime, and suppose G is a cyclic group of order pk. Let γ ∈ G be a generator of G. Given any function f : G → C, the Fourier transform of f is a function f̂ : Ĝ → C, given by f̂(π) = ∑ g∈G π(g)f(g), π ∈ Ĝ. Lemma 5.1. Assume G is a cyclic group of order pk, p prime. If π ∈ Ĝ is injective as a function π : G → C and f : G → Q is any injective function with rational values, then f̂(π) 6= 0. Proof. The image ξ = π(γ) under π of the generator γ of G is a pkth root of unity. Because π is assumed to be injective, ξ is a primitive pkth root of unity. As g = γj varies over G, the images π(g) = ξj 213 P. Langevin, J. A. Wood / J. Algebra Comb. Discrete Appl. 4(2) (2017) 207–217 vary over all the pkth roots of unity. The Fourier transform of f has the form f̂(π) = pk−1∑ j=0 f(γj)ξj. (2) The summation in (2), with 0 ≤ j < pk, can be written as a double summation by making use of the residue class m of j mod pk−1. Write j = ipk−1 + m, with 0 ≤ i < p and 0 ≤ m < pk−1. As a double summation, the Fourier transform is f̂(π) = p−1∑ i=0 pk−1−1∑ m=0 f(γip k−1+m)ξip k−1+m. (3) To simplify (3), we make use of the minimal polynomial of ξ over Q. The minimal polynomial of ξ over Q has degree φ(pk) = pk−1(p− 1), and the minimal polynomial itself is the cyclotomic polynomial Φpk(x) = x (p−1)pk−1 + x(p−2)p k−1 + · · · + xp k−1 + 1. (4) In (3), those terms where i = p − 1 will be replaced by the following expression derived from the minimal polynomial (4): ξ(p−1)p k−1+m = − p−2∑ i=0 ξip k−1+m. (5) After substituting the expressions from (5) into (3), the form of f̂(π) becomes f̂(π) = p−2∑ i=0 pk−1−1∑ m=0 {f(γip k−1+m) −f(γ(p−1)p k−1+m)}ξip k−1+m. (6) Observe from (6) that f̂(π), as a polynomial in ξ, has degree < (p − 1)pk−1, the latter being the degree of the minimal polynomial of ξ over Q. If f̂(π) = 0, then all the (rational) coefficients of the powers of ξ must vanish. This contradicts f being injective. Proof of Theorem 2.3. When N = 2`+1, N = 3`+1, or N = p = 2q + 1, p, q prime, Corollary 4.4 shows that the groups U/UUj are cyclic of prime power order. It also shows that a character π ∈ (Û : U) is injective on U/UUj when j = iπ. Set G = U/UUiπ, and define f : G → Q by f(u) = w(upiπ ), where w is wL or wE. This is a well-defined injective function on G. Under the assumptions above, Lemma 5.1 implies that w̌(π,iπ) = ∑ u∈U/UUiπ w(upiπ )π(u) 6= 0 (see (1)). Because the w̌(π,iπ) are the factors of detAw in Theorem 3.5, we conclude that detAw 6= 0. By Theorem 3.1, the extension property holds in the cases claimed in the statement of the theorem. The same arguments show that Theorem 2.3 holds for any rational-valued weight satisfying the conditions of Remark 3.2 such that w(x) = w(y) implies y = ±x. Rational weights yield rational coefficients in (6), which are needed to apply the minimal polynomial argument. 214 P. Langevin, J. A. Wood / J. Algebra Comb. Discrete Appl. 4(2) (2017) 207–217 Remark 5.2. Consider the case where R = Z/pZ, with p = 4q + 1 and p,q prime, as in Remark 2.4. The group U/U is cyclic of order 2q. For any π ∈ (Û : U), ker π (viewed as a subgroup of U/U) will be cyclic of order 1, 2, q, or 2q. Barra provides separate arguments for each of the four cases. Refer to [1, Theorem 5.28] for the details. For other values of N, the type of analysis given above quickly becomes very complicated. The group U/U need not be cyclic, and even in cases (such as N prime) where U/U is cyclic, it need not have prime power order. The degree and form of the cyclotomic polynomial becomes complicated, and the number of different cases to consider quickly gets out of hand. 6. An egalitarian weight and the proof of Theorem 2.6 Theorem 2.6 will be a special case of a general result valid over any finite module with a cyclic socle, in particular, over any finite Frobenius ring. The treatment here generalizes that for Frobenius bimodules in [18, Section 2.3] and will be rather brisk. Readers wanting more background information are also referred to [16]. We work in the following context. Let R be a finite ring with 1, and let A be a finite unitary left R-module. Suppose χ is an generating character for A, i.e., χ : A → C× is a homomorphism from the additive group of A to the multiplicative group of nonzero complex numbers that has the property that ker χ contains no nonzero left R-submodules. Such a generating character exists if and only if the socle of A is cyclic [17, Proposition 14] (and in the case where A = R, a generating character exists if and only if the ring R is Frobenius [12, Theorem 3.10]). It follows that any character π on A is a right scalar multiple of χ; i.e., π = χr, for some r ∈ R, where χr(a) = χ(ra) for a ∈ A. Let G be a subgroup of the automorphism group GLR(A). We will write elements g ∈ GLR(A) as acting on the right of A, so that the preservation of scalar multiplication takes the form (rx)g = r(xg), for r ∈ R, x ∈ A, and g ∈ GLR(A). Define a weight wG : A → C on A by wG(x) = 1 − 1 |G| ∑ g∈G χ(xg), x ∈ A. A weight w on A is egalitarian if there exists a nonzero constant γ such that ∑ x∈B w(b) = γ|B| for any nonzero left R-submodule B ⊆ A. Proposition 6.1. The weight wG has the following properties. 1. The value wG(0) = 0. 2. The weight wG is right G-invariant; i.e., wG(xg) = wG(x), for all x ∈ A and g ∈ G. 3. The weight wG is egalitarian with γ = 1. Moreover, wG is egalitarian on cosets with γ = 1; i.e.,∑ b∈B wG(x0 + b) = |B| for any nonzero left R-submodule B ⊆ A and element x0 ∈ A. Proof. Because χ(0) = 1, the first result is immediate. The right invariance follows immediately by a re-indexing argument. To prove that wG is egalitarian on cosets, let x0 ∈ A and B ⊆ A be a nonzero submodule. We calculate: ∑ b∈B wG(x0 + b) = ∑ b∈B  1 − 1 |G| ∑ g∈G χ((x0 + b)g)   = |B|− 1 |G| ∑ g∈G χ(x0g) ∑ b∈B χ(bg) = |B|, 215 P. Langevin, J. A. Wood / J. Algebra Comb. Discrete Appl. 4(2) (2017) 207–217 where we have used the fact that ∑ b∈B χ(bg) = 0 for any nonzero left submodule B. Indeed, because ker χ contains no nonzero left submodules, there exists some b0 ∈ B with χ(b0g) 6= 1. By re-indexing (b = b0 + c), we see that ∑ b∈B χ(bg) = χ(b0g) ∑ c∈B χ(cg). Thus, ∑ b∈B χ(bg) = 0. Remark 6.2. When A = R and G = U(R), the group of units of R, the resulting weight wU(R) is the homogeneous weight on R [9]. The egalitarian property for the homogeneous weight was proved in [8, Theorem 2]. The proof of the next theorem generalizes that for the homogeneous weight found in [2, Theorem 6.6]. Theorem 6.3. The weight wG has the extension property. That is, if C ⊆ An is a left R-linear code in An and f : C → An is an injective homomorphism of R-modules that preserves wG, wG(xf) = wG(x) for all x ∈ C, then f extends to a G-monomial transformation of An. Proof. Write the components of f as f = (f1,f2, . . . ,fn); each fi : C → A is a homomorphism of left R-modules. Inputs to fi are written on the left. Weight preservation and the definition of wG yield, for all x ∈ C, n∑ i=1  1 − 1 |G| ∑ g∈G χ((xfi)g)   = n∑ i=1  1 − 1 |G| ∑ g∈G χ(xig)   . This simplifies to n∑ i=1 ∑ g∈G χ((xfi)g) = n∑ i=1 ∑ g∈G χ(xig), x ∈ C. (7) This is an equation of functions on C, specifically, linear combinations of characters on C. Because characters are linearly independent over the complex numbers, if we set i = 1 and g = idG on the left side of (7), there exist i = σ(1) and g1 ∈ G on the right side so that χ(xf1) = χ(xσ(1)g1) for all x ∈ C. This implies that the image of the module homomorphism C → A, x 7→ xf1 − xσ(1)g1, is contained in ker χ. But ker χ contains no nonzero left submodules, so xf1 = xσ(1)g1 for all x ∈ C. It now follows, by re-indexing, that∑ g∈G χ(xf1g) = ∑ g∈G χ(xσ(1)g1g) = ∑ g∈G χ(xσ(1)g) for all x ∈ C. This allows us to reduce by one the size of the outer summation in (7) and to proceed by induction to produce a permutation σ of {1, 2, . . . ,n} and elements gi ∈ G with xfi = xσ(i)gi for all x ∈ C and i = 1, 2, . . . ,n. Proof of Theorem 2.6. Let R = Z/NZ, A = R, and G = {±1}. A generating character for Z/NZ is χ(x) = exp(2πix/N), x ∈ Z/NZ, where exp is the usual complex exponential function. Then χ(x) + χ(−x) = 2 cos(2πx/N), so that wG(x) = 1 − cos(2πx/N), x ∈ Z/NZ. Up to a factor of 2, wG(x) equals wPSK. Acknowledgment: We thank Aleams Barra for renewing our interest in this problem. The second author thanks the Université de Toulon for its support for research visits in 2000 and 2015, when the ideas of this paper were developed and finalized. 216 P. Langevin, J. A. Wood / J. Algebra Comb. Discrete Appl. 4(2) (2017) 207–217 References [1] A. Barra, Equivalence Theorems and the Local-Global Property, ProQuest LLC, PhD thesis Univer- sity of Kentucky, Ann Arbor, MI, USA, 2012. [2] A. Barra, H. Gluesing–Luerssen, MacWilliams extension theorems and the local–global property for codes over Frobenius rings, J. Pure Appl. Algebra 219(4) (2015) 703–728. [3] S. Dyshko, P. Langevin, J. A. Wood, Deux analogues au déterminant de Maillet, C. R. Math. Acad. Sci. Paris 354(7) (2016) 649–652. [4] F. G. Frobenius, Gesammelte Abhandlungen, Springer–Verlag, Berlin, 1968. [5] M. Greferath, T. Honold, C. Mc Fadden, J. A. Wood, J. Zumbrägel, MacWilliams’ extension theorem for bi-invariant weights over finite principal ideal rings, J. Combin. Theory Ser. A 125 (2014) 177–193. [6] M. Greferath, C. Mc Fadden, J. Zumbrägel, Characteristics of invariant weights related to code equivalence over rings, Des. Codes Cryptogr. 66(1) (2013) 145–156. [7] M. Greferath, S. E. Schmidt, Finite–ring combinatorics and MacWilliams’ equivalence theorem, J. Combin. Theory Ser. A 92(1) (2000) 17–28. [8] W. Heise, T. Honold, Homogeneous and egalitarian weights on finite rings, Proceedings of the Seventh International Workshop on Algebraic and Combinatorial Coding Theory (ACCT-2000), Bansko, Bulgaria, 183–188, 2000. [9] T. Honold, Characterization of finite Frobenius rings, Arch. Math. 76(6) (2001) 406–415. [10] K. Ireland, M. Rosen, A Classical Introduction to Modern Number Theory, second ed., Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York, 1990. [11] J. A. Wood, Extension theorems for linear codes over finite rings, Applied algebra, algebraic al- gorithms and error–correcting codes (Toulouse, 1997), Lecture Notes in Comput. Sci. 1255 (1997) 329–340. [12] J. A. Wood, Duality for modules over finite rings and applications to coding theory, Amer. J. Math. 121(3) (1999) 555–575. [13] J. A. Wood, Weight functions and the extension theorem for linear codes over finite rings, Finite fields: theory, applications, and algorithms (Waterloo, ON, 1997), Contemp. Math. 225 (1999) 231– 243. [14] J. A. Wood, Factoring the semigroup determinant of a finite chain ring, Coding Theory, Cryptography and Related Areas (2000) 249–264. [15] J. A. Wood, The structure of linear codes of constant weight, Trans. Amer. Math. Soc. 354(3) (2002) 1007–1026. [16] J. A. Wood, Foundations of linear codes defined over finite modules: the extension theorem and the MacWilliams identities. Codes over rings, 124–190, Ser. Coding Theory Cryptol., 6, World Sci. Publ., Hackensack, NJ, 2009. [17] J. A. Wood, Applications of finite Frobenius rings to the foundations of algebraic coding theory. Proceedings of the 44th Symposium on Ring Theory and Representation Theory, 223–245, Symp. Ring Theory Represent. Theory Organ. Comm., Nagoya, 2012. [18] J. A. Wood, Relative one-weight linear codes, Des. Codes Cryptogr. 72(2) (2014) 331–344. 217 http://dx.doi.org/10.1016/j.jpaa.2014.04.026 http://dx.doi.org/10.1016/j.jpaa.2014.04.026 http://dx.doi.org/10.1016/j.crma.2016.05.004 http://dx.doi.org/10.1016/j.crma.2016.05.004 http://dx.doi.org/10.1016/j.jcta.2014.03.005 http://dx.doi.org/10.1016/j.jcta.2014.03.005 http://dx.doi.org/10.1007/s10623-012-9671-9 http://dx.doi.org/10.1007/s10623-012-9671-9 http://dx.doi.org/10.1006/jcta.1999.3033 http://dx.doi.org/10.1006/jcta.1999.3033 http://dx.doi.org/10.1007/PL00000451 http://dx.doi.org/10.1007/3-540-63163-1_26 http://dx.doi.org/10.1007/3-540-63163-1_26 http://dx.doi.org/10.1007/3-540-63163-1_26 http://www.ams.org/mathscinet-getitem?mr=1738408 http://www.ams.org/mathscinet-getitem?mr=1738408 http://www.ams.org/mathscinet-getitem?mr=1650644 http://www.ams.org/mathscinet-getitem?mr=1650644 http://www.ams.org/mathscinet-getitem?mr=1650644 http://dx.doi.org/10.1007/978-3-642-57189-3_23 http://dx.doi.org/10.1007/978-3-642-57189-3_23 http://dx.doi.org/10.1090/S0002-9947-01-02905-1 http://dx.doi.org/10.1090/S0002-9947-01-02905-1 http://www.ams.org/mathscinet-getitem?mr=2850303 http://www.ams.org/mathscinet-getitem?mr=2850303 http://www.ams.org/mathscinet-getitem?mr=2850303 http://www.ams.org/mathscinet-getitem?mr=2975625 http://www.ams.org/mathscinet-getitem?mr=2975625 http://www.ams.org/mathscinet-getitem?mr=2975625 http://dx.doi.org/10.1007/s10623-012-9769-0 Introduction Background Method of attack for Theorem ?? Analysis of cases Proof of Theorem ?? An egalitarian weight and the proof of Theorem ?? References