Linear Codes over Finite Chain Rings

Thomas Honold Zentrum Mathematik Technische Universität München D-80290 München, Germany

                 honold@ma.tum.de

Ivan Landjev Institute of Mathematics and Informatics Bulgarian Academy of Sciences 8 Acad. G. Bonchev str. 1113 Sofia, Bulgaria

               ivan@moi.math.bas.bg

Submitted: December 20, 1998; Accepted: December 18, 1999

AMS Subject Classification: Primary 94B27; Secondary 94B05, 51E22, 20K01.

Abstract

The aim of this paper is to develop a theory of linear codes over finite chain rings from a geometric viewpoint. Generalizing a well-known result for linear codes over fields, we prove that there exists a one-to-one correspondence between so-called fat linear codes over chain rings and multisets of points in projective Hjelmslev geometries, in the sense that semilinearly isomorphic codes correspond to equivalent multisets and vice versa. Using a selected class of multisets we show that certain MacDonald codes are linearly representable over nontrivial chain rings.

1 Introduction

In the past decade, a substantial research has been done on linear codes over finite rings. Traditionally authors used to focus their research on codes over integer residue rings, especially ℤ_{4}. Nowadays quite a few papers are concerned with linear codes over other classes of rings (cf. e. g. [2, 7, 11, 12, 16, 17, 21, 24, 42, 43, 44, 50]).

The aim of this paper is to develop the fundamentals of the theory of linear codes over the class of finite chain rings. There are several reasons for choosing this class of rings. First of all, it contains rings, whose properties lie closest to the properties of finite fields. Hence a theory of linear codes over finite chain rings is expected to resemble the theory of linear codes over finite fields. Secondly, the class of finite chain rings contains important representatives like integer residue rings of prime power order and Galois rings. Codes over such rings appeared in various contexts in recent coding theory research. In third place, nontrivial linear codes over finite chain rings can be considered as multisets of points in finite projective Hjelmslev geometries thus extending the familiar interpretation of linear codes over finite fields as multisets of points in classical projective geometries PG(k, q) [10]. However, there are some differences between linear codes over finite fields and linear codes over finite chain rings. For instance, as a consequence of the existence of noncommutative finite chain rings, one is forced to distinguish between left and right linear codes, between the left and right orthogonal of a given code etc.

In Sect. 2 we give some basic results on finite modules over chain rings. In Sect. 3, we define the notion of a linear code over a finite chain ring R, along with some basic concepts like orthogonal code, code automorphism etc. We introduce regular partitions of R^{n} and prove MacWilliams-type identities for the spectra of linear codes w. r. t. such partitions. Section 4 contains a brief introduction to projective Hjelmslev geometries. In Sect. 5, we prove that there is a one-to-one correspondence between equivalence classes of so-called fat left linear codes over a chain ring and equivalence classes of multisets of points in right projective Hjelmslev geometries over the same ring. In Sect. 6, we investigate codes which belong to a selected class of multisets. We obtain chain ring analogues of the Simplex and Hamming codes and—as q-ary images with respect to a generalized Gray map—codes with the same parameters as the MacDonald codes.

An outline of some of the results of this paper appeared in [20].

2 Basic Facts on Finite Modules over Chain Rings

A ring^{1} is called a left (right) chain ring if its lattice of left (right) ideals forms a chain. The following result describes some properties of finite left chain rings (see e. g. [8, 38, 40]).

Theorem 2.1. For a finite ring R with radical N ≠ 0 the following conditions are equivalent:

(i) R is a left chain ring;

(ii) the principal left ideals of R form a chain; (iii) R is a local ring, and N = Rθ for any θ ∈ N \ N^{2};

1By the term ‘ring’ we always mean an associative ring with identity 1 ≠ 0; ring homomorphisms are assumed to preserve the identity.

(iv) R is a right chain ring.

Moreover, if R satisfies the above conditions, then every proper left (right) ideal of R has the form N^{i} = Rθ^{i} = θ^{i}R for some positive integer i.

In the sequel, we shall use the term chain ring to denote a finite left (and thus right) chain ring. We shall always assume that for a chain ring R the letters N, θ have the same meaning as in Th. 2.1. In addition we denote by q = p^{r} the cardinality of the finite field R/N (thus R/N ≅ 𝔽_{q}) and by m the index of nilpotency of N. Since for 0 ≤ i ≤ m − 1 the module N^{i}/N^{i+1} is a vector space of dimension 1 over R/N, we have |N^{i}/N^{i+1}| = q for 0 ≤ i ≤ m − 1, and in particular |R| = q^{m}.

The structure of chain rings can be very complicated, but the following two special cases are worth to note: (i) If R has characteristic p then R ≅ 𝔽_{q}[X; σ]/(X^{m}) for some σ ∈ Aut 𝔽_{q}, i. e. R is a truncated skew polynomial ring, and (ii) if R has (maximal) characteristic p^{m} then R ≅ GR(q^{m}, p^{m}) is a Galois ring; cf. [25, 38, 45]. Thus the smallest noncommutative chain ring has cardinality 16. It may be represented as R = 𝔽_{4}⊕𝔽_{4} with operations (a, b)+(c, d) = (a+c, b+d), (a, b)·(c, d) = (ac, ad+bc^{2}).^{2}

The upper Loewy series of a left R-module _{R}M is the chain

M = θ^{0}M ⊇ θ^{1}M ⊇ ⋯ ⊇ θ^{m−1}M ⊇ θ^{m}M = 0  (1)

of submodules θ^{i}M = N^{i}M ≤ _{R}M. Every quotient θ^{i−1}M/θ^{i}M (i ≥ 1) is a vector space over the field R/N ≅ 𝔽_{q}. Similarly, the lower Loewy series of _{R}M is the chain

M = M[θ^{m}] ⊇ ⋯ ⊇ M[θ^{2}] ⊇ M[θ] ⊇ M[1] = 0  (2)

of submodules M[θ^{i}] = {x ∈ M | θ^{i}x = 0}. Again every quotient M[θ^{i}]/M[θ^{i−1}] is a vector space over R/N ≅ 𝔽_{q}. We say that θ^{i} is the period of x ∈ M if i is the smallest nonnegative integer such that θ^{i}x = 0, and we write M^{∗} = {x ∈ M | x has period θ^{m}}. Similarly, the height of x is the largest integer i ≤ m such that x ∈ θ^{i}M. If x has height i we write θ^{i} ∥ x.

For i ∈ ℕ let μ_{i} = dim_{R/N}(θ^{i−1}M/θ^{i}M). Multiplication by θ (i. e. the map M → M, x → θx) induces additive isomorphisms

θ^{i−1}M/(M[θ] + θ^{i}M) ≅ θ^{i}M/θ^{i+1}M.  (3)

Thus we have log_{q}|M| = μ_{1} + μ_{2} + ⋯ + μ_{m} with μ_{i} ≥ μ_{i+1}, i. e. μ = (μ_{1}, μ_{2}, …) is a partition of log_{q}|M| (into at most m parts) which we abbreviate as μ ⊢ log_{q}|M|. In the sequel we shall write μ = (μ_{1}, …, μ_{r}) if μ_{i} = 0 for i > r and sometimes μ = 1^{s_{1}}2^{s_{2}}3^{s_{3}} ⋯ if exactly s_{j} parts of μ are equal to j.

2This example is due to Kleinfeld [26].

The following theorem generalizes the structure theorem for finite ℤ/p^{m}ℤ-modules or equivalently, finite Abelian p-groups of exponent not exceeding p^{m}, to the case of an arbitrary finite chain ring R.^{3}

Theorem 2.2. Every finite module _{R}M over a chain ring R is a direct sum of cyclic R-modules. The partition λ = (λ_{1}, …, λ_{r}) ⊢ log_{q}|M| satisfying

RM ≅ R/N^{λ_{1}} ⊕ ⋯ ⊕ R/N^{λ_{r}}  (4)

is uniquely determined by _{R}M. More precisely, λ = μ′ is conjugate to the partition μ = (μ_{1}, μ_{2}, …) ⊢ log_{q}|M| defined by μ_{i} = dim θ^{i−1}M/θ^{i}M.

Definition 2.1. The partitions λ, μ defined in Th. 2.2 are called the shape resp. conjugate shape of _{R}M. The integer λ′_{1} = μ_{1} = dim_{R/N}(M/θM) = dim_{R/N} M[θ] is called the rank of _{R}M and denoted by rk M.

Theorem 2.2 implies that any finite module _{R}M and its dual Hom(_{R}M,_{R}R)_{R} have the same shape.

A sequence x_{1}, …, x_{r} of elements of _{R}M is said to be independent (resp., linearly independent) if a_{1}x_{1} + ⋯ + a_{r}x_{r} = 0 with a_{j} ∈ R implies a_{j}x_{j} = 0 (resp., a_{j} = 0) for every j. A basis of _{R}M is an independent set of generators which does not contain 0. By Th. 2.2 the cardinality of any basis of _{R}M is equal to k = rk M, and the periods of its elements are θ^{λ_{1}}, …, θ^{λ_{k}} in some order. Note that _{R}M is a free module if and only if _{R}M has shape m^{k}.

Recall that a module_{R}M is projective (resp., injective) if_{R}M is a direct summand of a free module (resp., a direct summand of every module containing _{R}M).

Theorem 2.3. For a finite module _{R}M over a chain ring R the following properties are equivalent:

(i) _{R}M is free;

(ii) _{R}M is projective;

(iii) _{R}M is injective;

(iv) There exists i ∈ {1, 2, …, m − 1} such that M[θ^{i}] = θ^{m−i}M.

Proof. Since R is local, (i) and (ii) are equivalent. The equivalence of (ii) and (iii) is due to the fact that R is a quasi-Frobenius ring; cf. [9, §58]. Clearly (i) implies M[θ^{i}] = θ^{m−i}M for 0 ≤ i ≤ m and thus in particular (iv). Conversely, suppose that (iv) holds. The R-module M[θ^{i}] has conjugate shape (λ′_{1}, …, λ′_{i}) while θ^{m−i}M has conjugate shape (λ′_{m−i+1}, …, λ′_{m}). Since both modules are equal and m − i ≥ 1, we have λ′_{s} = λ′_{m−i+s} ≤ λ′_{s+1} for 1 ≤ s ≤ i − 1 and hence λ′_{1} = λ′_{2} = ⋯ = λ′_{i} = λ′_{m}.

3The proof in [35, Ch. 15, § 2] is easily adapted to the present situation. Theorem 2.2 holds, more generally, for matrix rings over finite chain rings—one only has to replace _{R}R by its unique indecomposable direct summand; cf. [1, 15, 28].

For partitions λ, μ with μ ≤ λ define

α_{λ}(μ; x) = ∏_{j≥1} x^{μ′_{j+1}(λ′_{j}−μ′_{j})} · \left[{λ′_{j} − μ′_{j+1} \atop μ′_{j} − μ′_{j+1}}\right]_{x}  (5)

where \left[{n \atop k}\right]_{x} = ∏_{s=1}^{k} \frac{x^{n−s+1}−1}{x^{s}−1} denotes a Gaussian polynomial.

Theorem 2.4. Let R be a finite chain ring with residue field of order q, and let _{R}M be a finite R-module of shape λ. For every partition μ satisfying μ ⊆ λ the module RM has exactly α_{λ}(μ; q) submodules of shape μ. In particular, the number of free rank 1 submodules of _{R}M equals

q^{λ′_{1}−1+λ′_{2}−1+···+λ′_{m−1}−1} · \left[{λ′_{m} \atop 1}\right]_{q}.  (6)

Proof. The theorem is well-known in the special case R = ℤ_{p^{m}}, cf. e. g. [6]. The general case follows from the results in [36, Ch. II] which remain valid for arbitrary (even noncommutative) chain rings.

Theorem 2.5. Let _{R}H be a free module of rank n over the chain ring R, and let RM be a submodule of _{R}H of shape λ and rank λ′_{1} = k.

(i) For every basis x_{1}, …, x_{k} of M there exists a basis y_{1}, …, y_{n} of H such that x_{j} ∈ Ry_{j} for 1 ≤ j ≤ k.

(ii) The quotient module H/M has shape (m − λ_{n}, m − λ_{n−1}, …, m − λ_{1}) and conjugate shape (n − λ′_{m}, n − λ′_{m−1}, …, n − λ′_{1}). In particular, M is free if and only if H/M is free if and only if rk(H/M) = n − k.

(iii) If M^{∗} ≠ ∅ (e. g. λ_{1} = m) then M is the sum of its free rank 1 submodules.

(iv) Dually, if (H/M)^{∗} ≠ ∅ (e. g. k < n) then M is the intersection of the free rank n − 1 submodules of _{R}H containing M.

Proof. Let {x_{1}, …, x_{k}} be a basis of M. We may assume the ordering is such that x_{j} has period θ^{λ_{j}}. Since H[θ^{i}] = θ^{m−i}H (0 ≤ i ≤ m), there exist y_{1}, …, y_{k} ∈ H^{∗} such that x_{j} = θ^{m−λ_{j}}y_{j} (1 ≤ j ≤ k). The sequence y_{1}, …, y_{k} is linearly independent. By Th. 2.3, it can be extended to a (free) basis y_{1}, …, y_{n} of H proving (i). The isomorphism H/M ≅ ⨁_{j=1}^{n} R/N^{m−λ_{j}} then gives (ii). If z ∈ M^{∗} and x_{j} ∉ M^{∗} then z + x_{j} ∈ M^{∗} and x_{j} = (z + x_{j}) − z, whence (iii) holds. Finally, if z ∉ M but z ∈ Ry_{1} + ⋯ + Ry_{n−1} we have z = r_{1}y_{1} + ⋯ + r_{n−1}y_{n−1} with r_{j} not divisible by θ^{m−λ_{j}}, say. Let y′_{j} = y_{j} + θ^{λ_{j}}y_{n}, y′_{t} = y_{t} if t ≠ j. The free rank n − 1 module H′ = Ry′_{1} + ⋯ + ry′_{n−1} contains M since θ^{m−λ_{j}}y′_{j} = θ^{m−λ_{j}}y_{j} = x_{j}. But z = r_{1}y′_{1} + ⋯ + r_{n−1}y′_{n−1} − r_{j}θ^{λ_{j}}y_{n} ∉ M, proving (iv).

Recall that a mapping ϕ: _{R}M → _{R}M′ is semilinear if there exists a ring homomorphism σ: R → R such that ϕ(x + y) = ϕ(x) + ϕ(y) and ϕ(rx) = σ(r)ϕ(x) for x, y ∈ M, r ∈ R. If ϕ is an isomorphism (i. e. The set of all semilinear isomorphisms (i. e. bijective semilinear mappings) ϕ: _{R}M → _{R}M is denoted by ΓL(_{R}M).

By Th. 2.3 the injective envelope of a finite module _{R}M (cf. [9, §17]) can be characterized as a minimal free module _{R}H containing _{R}M. To be precise, we require the existence of an R-linear embedding (injective map) ι: _{R}M → _{R}H such that no proper free submodule of _{R}H contains ι(M). The minimality of _{R}H is equivalent to rk H = rk M.

Theorem 2.6. Let _{R}M be a finite module with M^{∗} ≠ ∅ and _{R}H a minimal free module containg _{R}M.

(i) Any semilinear embedding of _{R}M into a free module _{R}F can be extended to a semilinear embedding of _{R}H into _{R}F.

(ii) If ϕ: _{R}M → _{R}M′ is a semilinear isomorphism and _{R}H′ a minimal free module containing _{R}M′, then there exists a semilinear isomorphism ϕ̃: _{R}H → _{R}H′ which extends ϕ.

Proof. Given an R-semilinear map ϕ: _{R}M → _{R}F with associated ring homomorphism σ, define a new operation of R on F by rx := σ(r)x, and denote the resulting module by _{R}F^{σ}. Then ϕ: _{R}M → _{R}F^{σ} is linear. Since M^{∗} ≠ ∅ and ϕ is an embedding, we have σ ∈ Aut R. Hence _{R}F^{σ} is free, and (i) reduces to a well-known property of the injective envelope of an R-module. Assertion (ii) follows from (i).

3 Linear Codes over Finite Chain Rings

In this section, we introduce the basic notions of the theory of linear codes over finite chain rings. With respect to component-wise addition and left/right multiplication, the set R^{n} all n-tuples over R has the structure of an (R, R)-bimodule.

Definition 3.1. A code C of length n over R is a nonempty subset of R^{n}. The vectors of C are called codewords. The code C is left (resp., right) linear if it is an R-submodule of _{R}R^{n} (resp., of R_{R}^{n}). A linear code is one which is either left or right linear.

In places where this sounds ambiguous we make it precise by writing e. g. C ≤ _{R}R^{n} if C is left linear. We formulate our results with a bias towards left modules, omitting obvious right module counterparts.

By Th. 2.1 the periods of x = (x_{1}, …, x_{n}) ∈ R^{n} in _{R}R^{n} and R_{R}^{n} coincide, whence the sets C[θ^{i}] in the lower Loewy series (2) of a linear code C are defined unambiguously even for bicodes, i. e. bimodules C ≤ _{R}R^{n}_{R}. The same holds a forteriori for the shape of C.

For two vectors u = (u_{1}, …, u_{n}) ∈ R^{n} and v = (v_{1}, …, v_{n}) ∈ R^{n} we define their inner product u · v by

u · v := u_{1}v_{1} + u_{2}v_{2} + ⋯ + u_{n}v_{n}.  (7)

Sending each v ∈ R^{n} to the R-linear mapping Φ_{r}(v): _{R}R^{n} → _{R}R, u → u · v defines an R-isomorphism R_{R}^{n} ≅ Hom(_{R}R^{n},_{R}R)_{R}.

For a code C ⊆ _{R}R^{n} we define

C^{⊥} = {y ∈ R^{n} | x · y = 0 for every x ∈ C}
⊥C = {y ∈ R^{n} | y · x = 0 for every x ∈ C}.

(8)

The linear code C^{⊥} ≤ R_{R}^{n} (resp., ^{⊥}C ≤ _{R}R^{n}) is called the right (resp., left) orthogonal code of C.

Theorem 3.1. Let C, C′ ≤ _{R}R^{n} be left linear codes over R. Further, let C be of shape λ = (λ_{1}, …, λ_{n}) and rank λ′_{1} = k. Then

(i) C^{⊥} has shape (m − λ_{n}, m − λ_{n−1}, …, m − λ_{1}) and conjugate shape (n − λ′_{m}, n − λ′_{m−1}, …, n − λ′_{1}). In particular, C is free as an R-module if and only if C^{⊥} is free if and only if rk(C^{⊥}) = n − k.

(ii) ^{⊥}(C^{⊥}) = C;

(iii) the map Φ_{r} induces an isomorphism R_{R}^{n}/C^{⊥} ≅ Hom(_{R}C,_{R}R)_{R};

(iv) (C ∩ C′)^{⊥} = C^{⊥} + C′^{⊥}, (C + C′)^{⊥} = C^{⊥} ∩ C′^{⊥}.

Proof. We prove (iii) first. Restricting Φ_{r}(y) to the code C induces an isomorphism from R_{R}^{n}/C^{⊥} onto a submodule W of Hom(_{R}C,_{R}R)_{R}. Since _{R}R is injective, every ϕ ∈ Hom(_{R}C,_{R}R) can be extended to ϕ̃ ∈ Hom(_{R}R^{n},_{R}R), whence ϕ̃ = Φ_{r}(y) for some y ∈ R^{n}. This implies W = Hom(_{R}C,_{R}R) proving (iii).

Since Hom(_{R}C,_{R}R)_{R} has shape equal to that of _{R}C, assertion (i) follows from the isomorphism in (iii) and Th. 2.5.(ii). Assertions (ii) and (iv) hold for any quasi-Frobenius ring; cf. [9, §58], [18].

Theorem 3.1 shows in particular that C ↦ C^{⊥} defines an antiisomorphism between the lattices of left resp., right linear codes of length n over R.

Definition 3.2 (cf. [34]). A family S = (S_{i} | i ∈ I) of nonempty subsets of R^{n} is called a regular partition of R^{n} if the following conditions are satisfied:

(i) R^{n} = ⋃_{i∈I} S_{j};

(ii) S_{i} ∩ S_{j} = ∅ for all pairs i ≠ j; (iii) for any two elements i, j ∈ I and any α ∈ R there exist constants λ_{ij}^{α}, ρ_{ij}^{α} such

that for each x ∈ S_{i} there are exactly λ_{ij}^{α} elements y ∈ S_{j} with x · y = α, and for each y ∈ S_{j} exactly ρ_{ij}^{α} elements x ∈ S_{i} with x · y = α.

If x ∈ S_{i} we say that x has S-type i. We call a permutation ϕ ∈ Sym(R^{n}) an S-automorphism of R^{n} if x − y ∈ S_{i} implies ϕ(x) − ϕ(y) ∈ S_{i} (i ∈ I).

Regular partitions of R^{n} can be obtained as the set of orbits from certain subgroups G of ΓL(_{R}R^{n}). Note that for every ϕ ∈ ΓL(_{R}R^{n}) there exist a uniquely determined ring automorphism σ ∈ Aut R and an invertible matrix A ∈ GL(n, R) such that

ϕ(x) = σ(x) · A (x ∈ R^{n}).  (9)

In Sections 5 and 6 the following special case will be important: The orbits of the group of all left semimonomial transformations of R^{n}, i. e. all maps ϕ ∈ ΓL(_{R}R^{n}) whose associated matrix A in (9) is monomial, form a regular partition. They are in one-to-one correspondence with the elements of the set I of m + 1-tuples w = (w_{0}, w_{1}, …, w_{m}) of nonnegative integers satisfying ∑_{i=0}^{m} w_{i} = n. For x = (x_{1}, …, x_{n}) ∈ R^{n} and 0 ≤ i ≤ m let

a_{i}(x) = |{j | 1 ≤ j ≤ n and θ^{i} ∥ x_{j}}|  (10)

and define

S_{w} = {x ∈ R^{n} | a_{i}(x) = w_{i} for 0 ≤ i ≤ m} (w ∈ I).  (11)

For brevity we omit the letter ‘S’ when referring to the special regular partition S = (S_{w})_{w∈I} defined in (11). Thus the sequence (a_{0}(x), …, a_{m}(x)) is simply the type of the word x, and a (code) automorphism of R^{n} is a permutation ϕ ∈ Sym(R^{n}) satisfying a_{i}(x − y) = a_{i}(ϕ(x) − ϕ(y)) for x, y ∈ R^{n}, 0 ≤ i ≤ m.

Definition 3.3. Two codes C_{1}, C_{2} ⊆ R^{n} are said to be isomorphic (resp., semilinearly isomorphic) if there exists a code automorphism (resp., semilinear code automorphism) ϕ of R^{n} with ϕ(C_{1}) = C_{2}.

Thus two linear codes C_{1}, C_{2} ≤ _{R}R^{n} are semilinearly isomorphic if and only if there exists a left semimonomial transformation ϕ of R^{n} with ϕ(C_{1}) = C_{2}.

In the sense of [50] the type of x is essentially the symmetrized weight composition of x with respect to the full group of units of R. A result in [48] implies that every semilinear permutation ϕ: C → C of a linear code C ≤ _{R}R^{n} which preserves the type of codewords x ∈ C extends to a left semimonomial transformation of R^{n}. Extensions of this result to general weight functions on finite rings—with particular emphasis on the case of commutative chain rings—have been investigated in [51].

Given a code C ⊆ R^{n} and a regular partition S = (S_{i} | i ∈ I) of R^{n} we define integers A_{i} (i ∈ I) by A_{i} = |C ∩ S_{i}|. The family (A_{i})_{i∈I} is called the S-spectrum of C. We write (B_{i}^{(s)})_{i∈I} for the S-spectra of the codes

C_{(s)}^{⊥} = {y ∈ R^{n} | x · y ∈ N^{s} for every x ∈ C} (0 ≤ s ≤ m)

and abbreviate B_{i}^{(m)} = |C^{⊥} ∩ S_{i}| as B_{i}.

The S-spectra of a linear code C ≤ _{R}R^{n} and its dual codes C_{(s)}^{⊥} are related by identities which are similar to the MacWilliams identities (cf. [19] or [37]). In order to formulate this result, we define functions ω_{s}: R → ℝ, 0 ≤ s ≤ m, by

ω_{s}(x) = \begin{cases}1 & if x ∈ N^{s}, \\ −1/(q − 1) & if x ∈ N^{s−1} \ N^{s}, \\ 0 & if x ∉ N^{s−1}. \end{cases}  (12)

These functions satisfy the following “orthogonality relations” for ideals A of R:

\frac{1}{|A|} · ∑_{x∈A} ω_{s}(x) = \begin{cases}1 & if A ≤ N^{s}, \\ 0 & if A ≰ N^{s}. \end{cases}  (13)

Theorem 3.2 (MacWilliams identities). Let S = (S_{i} | i ∈ I) be a regular partition of R^{n}, and let C ≤ _{R}R^{n} be a linear code. The S-spectrum of the orthogonal codes C_{(s)}^{⊥} is obtained from the S-spectrum of C by

B_{j}^{(s)} = \frac{1}{|C|} · ∑_{i∈I} A_{i} · (∑_{α∈R} λ_{ij}^{α} · ω_{s}(α)).  (14)

Proof. Using (13) we have

∑_{x∈C} ω_{s}(x · y) = \begin{cases}|C| & if y ∈ C_{(s)}^{⊥}, \\ 0 & if y ∈ R^{n} \ C_{(s)}^{⊥}, \end{cases}  (15)

since the set {x · y | x ∈ C} is a left ideal of R which is contained in N^{s} if and only if y ∈ C_{(s)}^{⊥}. Thus

B_{j}^{(s)} = |C_{(s)}^{⊥} ∩ S_{j}|

= \frac{1}{|C|} · ∑_{y∈S_{j}} ∑_{x∈C} ω_{s}(x · y)

= \frac{1}{|C|} · ∑_{i∈I} ∑_{x∈C∩S_{i}} ∑_{y∈S_{j}} ω_{s}(x · y)

= \frac{1}{|C|} · ∑_{i∈I}|C ∩ S_{i}| · (∑_{α∈R} λ_{ij}^{α} · ω_{s}(α))

= \frac{1}{|C|} · ∑_{i∈I} A_{i} · (∑_{α∈R} λ_{ij}^{α} · ω_{s}(α)).

(16)

Regular partitions of R^{n} are Fourier-invariant partitions (F-partitions) of the abelian group (R^{n}, +) in the sense of [13, 14]. The link is provided by an additive character ψ: R → ℂ satisfying N^{m−1} ⊈ ker ψ. The pairing R^{n} × R^{n} → ℂ, (x, y) ↦ ψ(x · y) can be used to define a suitable Fourier transform F: ℂR^{n} → ℂR^{n}.

For the special case R = 𝔽_{q} of Th. 3.2 see [34]. MacWilliams identities for Fpartitions are proved in [14]. Other types of MacWilliams identities for codes over finite rings can be found e. g. in [23, 27, 41, 50].

4 The projective Hjelmslev geometries PHG(R_{R}^{k})

In this section, we introduce the projective Hjelmslev geometries PHG(R_{R}^{k}) and give some results on their basic structure. For a rigorous approach to projective Hjelmslev spaces the reader is referred to [29, 30, 31, 47]. Consider a finite free right module H_{R} where R is a chain ring. The elements of P = P(H_{R}) = {xR | x ∈ H^{∗}} are called points of H_{R}, those of L = L(H_{R}) = {xR + yR | x, y linearly independent} are called lines of H_{R}. The incidence relation I ⊆ P × L is defined in a natural way by set-theoretical inclusion. As usual we identify lines with subsets of P.^{4} Note that any two different points are joined by at least one line.

Definition 4.1. The incidence structure Π = (P, L, I) together with the neighbour relation ⌢ ⌣, defined by

(N1) the points X, Y are neighbours (notation X ⌢ ⌣Y) if and only if there exist different lines s, t ∈ L with X, Y ∈ s ∩ t; (N2) the lines s, t ∈ L are neighbours if and only if for every point X ∈ s there is a point Y ∈ t with X ⌢ ⌣Y and, conversely, for every Y ∈ t there is an X ∈ s with

Y ⌢ ⌣X;

is called a projective Hjelmslev space and denoted by PHG(H_{R}).^{5}

The relation ⌢ ⌣ induces an equivalence relation on P as well as on L. The class [X] of all points which are neighbours to the point X = xR consists of all free rank 1 submodules contained in xR + Hθ. Similarly, the class [s] of all lines which are neighbours to s = xR + yR, consists of all free rank 2 submodules contained in xR + yR + Hθ.

The point set T ⊆ P is called a Hjelmslev subspace of Π if for every two points X, Y ∈ T , there exists a line s ⊆ T with X, Y ∈ s. We write X ⌢ ⌣T if there exists a

point Y ∈ T with X ⌢ ⌣Y. Every Hjelmslev subspace is a projective Hjelmslev space and consists of the points contained in some free submodule of H_{R}.^{6} For every X ⊆ P we define the closure \overline{X} as the intersection of all Hjelmslev subspaces containing X. The set X ⊆ P is said to be independent if for any X ∈ X we have X ⌢̸ ⌣\overline{X \ \{X\}}, and a basis of Π if X is independent and \overline{X} = P. The dimension of Π is defined as dim Π = |B| − 1 where B is any basis of Π. Equivalently, dim Π = rk(H_{R}) − 1.

4A line s ∈ L is uniquely determined by {X ∈ P | XIs}.

5If R is noncommutative, PHG(H_{R}) and PHG(_{R}H) are in general not isomorphic. Working with right instead of left modules will be justified in Section 5.

An isomorphism between two projective Hjelmslev spaces Π = PHG(H_{R}) and Π′ = PHG(H′_{R}) is a bijection β: P → P′ which satisfies β(L) = L′. The spaces Π and Π′ are isomorphic if and only if rk(H_{R}) = rk(H′_{R}). Every semilinear isomorphism ϕ: H_{R} → H′_{R} induces such an isomorphism since it maps xR ∈ P onto ϕ(xR) = ϕ(x)R ∈ P′. The following theorems can be found in [30, 32]:

Theorem 4.1. If rk(H_{R}) = rk(H′_{R}) ≥ 3 then for any isomorphism β: Π → Π′ there exists a semilinear isomorphism ϕ: H_{R} → H′_{R} inducing β.

Theorem 4.2. Let {P_{1}, P_{2}, …, P_{k+1}} ⊆ P and {Q_{1}, Q_{2}, …, Q_{k+1}} ⊆ P′ be subsets (“frames”) such that any k of the points in each of the sets form a basis of Π resp., Π′. Then there exists exactly one isomorphism β: Π → Π′ with β(P_{i}) = Q_{i}, 1 ≤ i ≤ k+1.

Projective Hjelmslev spaces can be defined axiomatically as incidence structures π = (P, L, I) with a neighbour relation ⌢ ⌣ on P and on L which satisfy certain conditions. Without going into details we mention the following

Theorem 4.3 ([30, 33]). For every projective Hjelmslev space Π of dimension at least 3, having on each line at least 5 points no two of which are neighbours, there exists a free module H_{R} over a chain ring R such that PHG(H_{R}) is isomorphic to Π.

Remark 4.1. The incidence structure (P, L, I) and Def. 4.1 make sense for an arbitrary finite module M_{R} which is not a priori a submodule of some finite free module. We can embed M_{R} into a finite free module H_{R} of rank rk(H_{R}) ≥ rk(M_{R}) and view (P, L, I) as a substructure of the geometry PHG(H_{R}). By Th. 2.5.(iii) a submodule M_{R} ≤ H_{R} is determined by its set of points, and if rk(H_{R}) > rk(M_{R}) then M is closed by Th. 2.5.(iv). According to Theorems 2.3, 2.6 and 4.1 two finite modules RM and _{R}M′ of rank at least 3 are semilinearly isomorphic if and only if they are isomorphic as substructures of PHG(H_{R}) and PHG(H′_{R}), respectively, assuming of course that rk(H_{R}) = rk(H′_{R}). Thus both viewpoints are essentially equivalent.

For simplicity we take H_{R} = R_{R}^{k} in the sequel. The incidence structure PHG(R_{R}^{k}) is called the (right) k − 1-dimensional projective Hjelmslev geometry over R.

We shall need the following refinement of the neighbour relation:

Definition 4.2. Let Δ_{1}, Δ_{2} be Hjelmslev subspaces of PHG(R_{R}^{k}) and 0 ≤ i ≤ m. We say that Δ_{1} is an i-neighbour to Δ_{2}, and write Δ_{1} ⌢ ⌣_{i}Δ_{2} in this case, if Δ_{1} ⊆ Δ_{2}+R^{k}θ^{i}.

6Needless to say, we identify Hjelmslev subspaces of PHG(H_{R}) with the corresponding free submodules of H_{R}.

Denoting by π^{(i)} : R^{k} → R^{k}/R^{k}θ^{i} the natural projection, we have Δ_{1} ⌢ ⌣_{i}Δ_{2} if

and only if π^{(i)}(Δ_{1}) ⊆ π^{(i)}(Δ_{2}). The relation ⌢ ⌣_{i} induces an equivalence relation on Hjelmslev subspaces of equal dimension. The i-neighbour class of Δ is [Δ]_{i} = {Δ′ | dim Δ′ = dim Δ and Δ′ ⌢ ⌣_{i}Δ}.

For points X = xR, Y = yR we have X ⌢ ⌣_{i}Y but X ⌢̸ ⌣_{i+1}Y if and only if |X ∩ Y | = q^{i} if and only if xR + yR has shape (m, m − i). The neighbour class [X]_{i} coincides with the set of all free rank 1 submodules of xR + R^{k}θ^{i}. Similarly, for a line s = xR + yR the neighbour class [s]_{i} coincides with the set of all free rank 2 submodules of xR + yR + R^{k}θ^{i}. Furthermore, lines s and t are i-neighbours if and only if for every X ∈ s there is a point Y ∈ t with X ⌢ ⌣_{i}Y and, conversely, for every

Y ∈ t there is an X ∈ s with Y ⌢ ⌣_{i}X. Clearly ⌢ ⌣_{1} coincides on points and on lines

with the neighbour relation ⌢ ⌣ introduced at the beginning of this section.

Let P^{(i)} (resp. L^{(i)}) be the set of all i-neighbour classes of points (resp. of lines) in (P, L, I).

Theorem 4.4. The incidence structure Π^{(i)} = (P^{(i)}, L^{(i)}, I^{(i)}) with I^{(i)} defined by

[X]_{i} I^{(i)} [s]_{i} ⟺ ∃X′ ∈ [X]_{i}, ∃s′ ∈ [s]_{i} : X′ I s′  (17)

is isomorphic to PHG ((R^{k}/θ^{i}R^{k})_{R/N^{i}}) for all i ∈ {1, …, m}. In particular, Π^{(1)} is isomorphic to the projective geometry PG(k − 1, q).

Proof. The image under π^{(i)} of every free submodule of R_{R}^{k} is a free module over R/N^{i} of the same rank. Hence, if we define [X]_{i}I′[s]_{i} by π^{(i)}(X) ⊆ π^{(i)}(s) then (P^{(i)}, L^{(i)}, I′) is isomorphic to PHG ((R^{k}/θ^{i}R^{k})_{R/N^{i}}). Let X = xR ∈ P, s = yR + zR ∈ L with π^{(i)}(X) ⊆ π^{(i)}(s), i. e. xR ⊆ yR + zR + R^{k}θ^{i}. Since xR is free and hence a direct summand of yR + zR + R^{k}θ^{i}, it is contained in some free rank 2 submodule of yR + zR + R^{k}θ^{i}. This gives I′ = I^{(i)} as desired.

5 Multisets in Projective Hjelmslev Geometries and Linear Codes over Chain Rings

Let Π = PHG(H_{R}) = (P, L, I) be a finite dimensional projective Hjelmslev geometry over the chain ring R.

Definition 5.1. A multiset in Π is a mapping 𝔨: T → ℕ_{0} where T ⊆ P.^{7}

Often we tacitly assume T = P, defining 𝔨(P) = 0 for P ∈ P \ T .

7A multiset 𝔨: T → ℕ_{0} is called a set if 𝔨(P) ∈ {0, 1} for any P ∈ T .

The mapping 𝔨 is extended to the power set of P by

𝔨(Q) = ∑_{P ∈Q} 𝔨(P) for Q ⊆ P.  (18)

The integer 𝔨(P) is called the multiplicity of the point P. The integer 𝔨(P) = ∑_{P ∈T} 𝔨(P) is called the cardinality or length of the multiset 𝔨 and is denoted by |𝔨|. The support of 𝔨 is defined as Supp 𝔨 = {P ∈ T |𝔨(P) > 0} and the hull of 𝔨 as the module

⟨𝔨⟩ = ∑_{xR∈Supp 𝔨}xR ≤ H_{R}.  (19)

The shape of 𝔨 is the shape of its hull ⟨𝔨⟩_{R}.

Definition 5.2. Two multisets 𝔨 in Π and 𝔨′ in Π′ are said to be equivalent if there exists a bijective R-semilinear mapping ψ: ⟨𝔨⟩ → ⟨𝔨′⟩ such that 𝔨(P) = 𝔨′(ψ(P)) for every point P = xR ≤ ⟨𝔨⟩.

If dim Π ≤ dim Π′, say, then in view of Remark 4.1 the multisets 𝔨, 𝔨′ are equivalent if and only if there exists an embedding β: Π → Π′ such that 𝔨 and 𝔨′β coincide on the points of Π.

Definition 5.3. A linear code C ≤ _{R}R^{n} is said to be fat if for every i ∈ {1, …, n} there exists a codeword c = (c_{1}, c_{2}, …, c_{n}) ∈ C with c_{i} ∈ R^{∗}.

Thus C ≤ _{R}R^{n} is fat if and only if the restriction to C of every projection map Φ_{r}(e_{j}): _{R}R^{n} → _{R}R, x ↦ x · e_{j} = x_{j} is onto.

Let C ≤ _{R}R^{n} be a fat linear code. We intend to associate with C a certain multiset of points in a projective Hjelmslev geometry over R which generalizes the familiar correspondence between full-length linear [n, k]-codes over 𝔽_{q} and multisets of points in PG(k−1, q) of cardinality n obtained as columns of a generator matrix of the [n, k]- code. Since the dual Hom(_{R}C,_{R}R)_{R} of _{R}C need not be a free R-module, some extra work is necessary. Let S = (c_{1}, …, c_{k}) be a sequence of (not necessarily independent) generators for _{R}C and G ∈ M_{k,n}(R) be the k × n-matrix with rows c_{1}, …, c_{k}. Denote the columns of G by g_{1}, …, g_{n}, i. e. g_{j} = (Φ_{r}(e_{j})(c_{1}), …, Φ_{r}(e_{j})(c_{k})). Note that g_{j} has period θ^{m} since Φ(e_{j}) is onto and c_{1}, …, c_{k} generate _{R}C, and thus defines a point in the projective (right) Hjelmslev geometry (P, L, I) = PHG(R_{R}^{k}). We define the multiset 𝔨_{S} induced by the generating sequence S of C as

𝔨_{S}: \{ \begin{matrix}P & → ℕ_{0} \\ P & ↦ |\{j | P = g_{j}R\}|. \end{matrix}  (20)

We say that the multiset 𝔨_{S} and the code C = ∑_{c∈S} Rc are associated. By definition of 𝔨_{S} we have |𝔨_{S}| = n. The following theorem is a generalization of a similar result by Dodunekov and Simonis [10] about linear codes over finite fields.

Theorem 5.1. For every multiset 𝔨 of length n in PHG(R_{R}^{k}) there exists a fat linear code C ≤ _{R}R^{n} and a generating sequence S = (c_{1}, ⋯, c_{k}) of _{R}C which induces 𝔨. Two multisets 𝔨_{1} in PHG(R_{R}^{k_{1}}) and 𝔨_{2} in PHG(R_{R}^{k_{2}}) associated with fat (left) linear codes C_{1} and C_{2} over R, respectively, are equivalent if and only if the codes C_{1} and C_{2} are semilinearly isomorphic.

Proof. To prove the first assertion, choose a list (g_{1}, …, g_{n}) of vectors g_{j} ∈ R^{k} such that for every point P of P HG(R_{R}^{k})

𝔨(P) = |{j | 1 ≤ j ≤ n and P = g_{j}R}|.  (21)

Define C ≤ _{R}R^{n} to be the code generated by the rows of the k×n-matrix G ∈ M_{k,n}(R) with columns g_{1}, …, g_{n}. Every column of G contains at least one entry r ∈ R^{∗}. Hence the code C is fat. Clearly, the sequence S = (c_{1}, …, c_{k}) of rows of G induces 𝔨 in the sense of (20), i. e. 𝔨_{S} = 𝔨.

To prove the second assertion, assume first that two semilinearly isomorphic codes C_{1}, C_{2} ≤ _{R}R^{n} are associated with multisets 𝔨_{1} in PHG(R_{R}^{k_{1}}) and 𝔨_{2} in PHG(R_{R}^{k_{2}}), respectively. Let G_{1} ∈ M_{k_{1},n}(R) and G_{2} ∈ M_{k_{2},n}(R) be matrices whose sequences S_{1} and S_{2} of rows generate C_{1} (resp., C_{2}) and induce 𝔨_{1} (resp., 𝔨_{2}), i. e. 𝔨_{S_{i}} = 𝔨_{i} for i = 1, 2. Let ϕ: R^{n} → R^{n} be a semilinear code automorphism of _{R}R^{n} with ϕ(C_{1}) = C_{2}. The sequence S′_{2} = ϕ(S_{1}) also generates C_{2}. Let G′_{2} ∈ M_{k_{1},n}(R) be the matrix associated with S′_{2} and 𝔨′_{2} the multiset in PHG(R_{R}^{k_{1}}) induced by S′_{2}. There exist U ∈ M_{k_{1},k_{2}}(R), V ∈ M_{k_{2},k_{1}}(R) with G′_{2} = UG_{2}, G_{2} = VG′_{2}. Let ψ_{U} : R_{R}^{k_{2}} → R_{R}^{k_{1}}, g → Ug and ψ_{V} : R_{R}^{k_{1}} → R_{R}^{k_{2}}, g → Vg be the corresponding R-linear mappings. Then 𝔨_{2} = 𝔨′_{2}ψ_{U} and 𝔨′_{2} = 𝔨_{2}ψ_{V}. From G′_{2} = UVG′_{2}, G_{2} = VUG_{2} we conclude that ψ_{U}ψ_{V} fixes 𝔨′_{2} and ψ_{V}ψ_{U} fixes 𝔨_{2}, whence the restrictions of ψ_{U} and ψ_{V} to ⟨𝔨_{2}⟩ and ⟨𝔨′_{2}⟩, respectively, are mutually inverse R-isomorphisms. Thus 𝔨_{2} and 𝔨′_{2} are equivalent. Moreover, there exists a monomial matrix M and a ring automorphism σ such that ϕ(x) = σ(x)M for x ∈ R^{n}. This shows G′_{2} = σ(G_{1})M. The columns of G′_{2} and σ(G_{1}) represent the multisets 𝔨′_{2} and 𝔨_{1}σ^{−1}, respectively. Since M is monomial we have 𝔨′_{2} = 𝔨_{1}σ^{−1} and thus 𝔨_{1} = 𝔨′_{2}σ proving the equivalence of 𝔨_{1} and 𝔨_{2}.

Conversely, suppose that 𝔨_{1} and 𝔨_{2} are equivalent and associated with C_{1} and C_{2}. Let G_{1}, G_{2} have the same meaning as above, and let ψ: ⟨𝔨_{1}⟩ → ⟨𝔨_{2}⟩ be a bijective semilinear mapping with 𝔨_{1} = 𝔨_{2}ψ. Let H_{1} ≤ R_{R}^{k_{1}} and H_{2} ≤ R_{R}^{k_{2}} be minimal free R-modules containing ⟨𝔨_{1}⟩ and ⟨𝔨_{2}⟩, respectively. By Th. 2.6 ψ can be extended to a bijective semilinear mapping ψ̃: H_{1} → H_{2}. Since H_{1} and H_{2} are direct summands of R_{R}^{k_{1}} and R_{R}^{k_{2}}, respectively, we can extend ψ̃ to a mapping from R_{R}^{k_{1}} into R_{R}^{k_{2}} and ψ̃^{−1} to a mapping from R_{R}^{k_{2}} into R_{R}^{k_{1}}, i. e. there exist matrices U ∈ M_{k_{1},k_{2}}(R), V ∈ M_{k_{2},k_{1}}(R) and a ring automorphism σ of R such that ψ(g) = σ(Vg) for every g ∈ ⟨𝔨_{1}⟩ and ψ^{−1}(h) = Uσ^{−1}(h) for every h ∈ ⟨𝔨_{2}⟩. The matrix G′_{1} = VG_{1} ∈ M_{k_{2},n}(R) generates C_{1} since UG′_{1} = G_{1}, and for every point P of PHG(R_{R}^{k_{1}}) it contains exactly 𝔨_{1}(P) = 𝔨_{2}(ψ(P)) columns h ∈ R^{k_{2}} with σ(h)R = ψ(P). Thus the columns of σ(G′_{1}) and G_{2} represent the same points of PHG(R_{R}^{k_{2}}) when counted with their multiplicities. This clearly implies the existence of a monomial matrix M with G_{2} = σ(G′_{1})M which in turn yields that C_{1} and C_{2} are semilinearly isomorphic.

Remark 5.1. If one defines PHG(R_{R}^{k}) as a point-line incidence structure as we did in Section 4, the restriction to fat linear codes in Th. 5.1 is a natural consequence. Non-fat linear codes, however, do appear in some situations, for example in the classification of ℤ_{4}-linear codes of constant Lee or Euclidean weight [49]. It is possible to circumvent the restriction to fat linear codes by viewing PHG(R_{R}^{k}) as a projective lattice geometry [4] having additional non-free points. Theorem 5.1 can be proved in this more general setting.

Definition 5.4. Let 𝔨: P → ℕ_{0} be a multiset in Π = PHG(R_{R}^{k}). A hyperplane Δ in Π is said to have the 𝔨-type (a_{0}, a_{1}, …, a_{m}), where a_{i} = ∑_{P : P ⌢ ⌣_{i}Δ, P⌢̸ ⌣_{i+1}Δ} 𝔨(P),

for i = 0, 1, …, m.

We shall often say ‘type’ instead of ‘𝔨-type’, if there is no doubt about the multiset 𝔨 we are referring to. By duality (Th. 3.1) every hyperplane Δ in PHG(R_{R}^{k}) can be considered as the set of points, whose homogeneous coordinates (x_{1}, …, x_{k}) satisfy a linear equation

r_{1}x_{1} + r_{2}x_{2} + … + r_{k}x_{k} = 0,

where at least one of the r_{i}’s is a unit in R. Let C be a fat linear code associated with 𝔨, and let G_{S} be a k×n-matrix whose sequence S of rows generates C and satisfies 𝔨_{S} = 𝔨. All codewords of C which belong to the cyclic submodule R(r_{1}, …, r_{k})G_{S} ≤ _{R}C are called codewords associated with the hyperplane Δ (relative to the choice of the generating sequence S). For different generating sequences S, S′ of C with 𝔨_{S} = 𝔨_{S′} the matrices G_{S} and G_{S′} can differ only by the ordering and scaling of their columns. Thus as far as the number and type (10) of codewords associated with a hyperplane is concerned, we may safely omit from now on any reference to the generating sequence. There is a connection between the type of a hyperplane in Π and the number of codewords of a given type in C associated with that hyperplane.

Theorem 5.2. Let 𝔨 be a multiset in PHG(R_{R}^{k}) and C a fat linear code over R associated with 𝔨. For each hyperplane Δ of 𝔨-type

(0, …, 0, a_{j}, a_{j+1}, …, a_{m}) with a_{j} ≠ 0 (0 ≤ j ≤ m)

there exist exactly q^{m−s} − q^{m−s−1} codewords in C of type

(\underbrace{0, …, 0}_{s}, a_{j}, …, a_{m+j−s−1}, ∑_{i=m+j−s}^{m} a_{i})  (j ≤ s ≤ m − 1)  (22)

which are associated with Δ.

Proof. Fix a generating sequence S of C and let G = G_{S} be as above. Let Δ = (Rr)^{⊥} with r = (r_{1}, …, r_{k}) ∈ _{R}R^{k}. The codeword c = (r_{1} … r_{k})G has exactly the same type (0, …, 0, a_{j}, a_{j+1}, …, a_{m}) as the hyperplane Δ. Since c has period θ^{m−j}, we have |Rc| = q^{m−j}. The words in Rc with type as in (22) are exactly those which generate the cyclic submodule Rc[θ^{m−s}] ≤ Rc of order q^{m−s}. Their number is therefore q^{m−s} − q^{m−s−1} as asserted.

Theorem 5.3. A multiset 𝔨 in PHG(R_{R}^{k}) and its associated code have the same shape. In particular, |⟨𝔨⟩| = |C|.

Proof. Choose a k × n-matrix G whose sequence S of rows generate R_{C} and whose columns g_{1}, …, g_{n} represent the points P as in (21). Since S generates _{R}C, the linear map Hom(_{R}C,_{R}R)_{R} → ⟨𝔨⟩_{R} which sends the restriction Φ_{r}(e_{j})|_{C} to g_{j} is an isomorphism. Thus ⟨𝔨⟩_{R}, Hom(_{R}C,_{R}R)_{R} and _{R}C all have the same shape; cf. the remark following Def. 2.1.

6 Linear Codes from Selected Multisets in PHG(R_{R}^{k})

In this section we discuss some classes of linear codes over chain rings which arise from certain multisets of points in projective Hjelmslev geometries.

6.1 Simplex and Hamming Codes over Chain Rings

In [3] Blake introduced a generalization of the class of Hamming codes to the ring of integers modulo q = p^{r}, where p is prime. Below we suggest another definition, which reflects the geometric nature of the usual Hamming codes.

Consider the Hjelmslev geometry Π = (P, L, I) = PHG(R_{R}^{k}). The linear code C associated with the multiset 𝔨 defined by 𝔨(P) = 1 for all P ∈ P, is called the k-dimensional simplex code over R and is denoted by Sim(k, R). By Th. 2.4 the code Sim(k, R) has length q^{(k−1)(m−1)}\left[{k \atop 1}\right]_{q}, and by Th. 5.3 it has shape m^{k}, in particular |Sim(k, R)| = q^{km}. All hyperplanes Δ in Π have the same 𝔨-type (a_{0}, a_{1}, …, a_{m}), where

\begin{aligned}a_{0} & = q^{(k−1)(m−1)} (\left[{k \atop 1}\right]_{q} − \left[{k − 1 \atop 1}\right]_{q}) = q^{(k−1)m}, \\ a_{j} & = q^{(k−2)(m−1)}\left[{k − 1 \atop 1}\right]_{q} (q^{m−j} − q^{m−j−1}) , j = 1, …, m − 1, \\ a_{m} & = q^{(k−2)(m−1)}\left[{k − 1 \atop 1}\right]_{q}. \end{aligned}  (23)

These numbers are obtained e. g. by observing that ∑_{s≥j} a_{s} is the number of free rank 1 submodules contained in Δ + θ^{j}R^{k} which has shape m^{k−1}(m − j)^{1}. Thus

∑_{s≥j} a_{s} = α_{m^{k−1}(m−j)^{1}}(m^{1}; q) = \begin{cases}q^{(k−1)(m−1)}\left[{k \atop 1}\right]_{q} & if j = 0, \\ q^{(k−1)(m−1)}\left[{k−1 \atop 1}\right]_{q} · q^{1−j} & if 1 ≤ j ≤ m.^{8} \end{cases}

The dual code Sim(k, R)^{⊥} is called the k-th order Hamming code over R and is denoted by Ham(k, R). It is free of rank q^{(k−1)(m−1)}\left[{k \atop 1}\right]_{q} −k, in particular |Ham(k, R)| =

q^{mq^{(k−1)(m−1)}\left[{k \atop 1}\right]_{q}−mk}. For example, Ham(k, ℤ_{4}) has parameters (n, M, w_{Lee}) = (2^{2k−1} − 2^{k−1}, 2^{2^{2k}−2^{k}−2k}, 3).

6.2 The Linearity of the MacDonald Codes

Let us fix a Hjelmslev subspace Σ of Π with rk Σ = u, 1 ≤ u ≤ k − 1. Let C be associated with 𝔨: P → ℕ_{0} defined by

𝔨(P) = \{ \begin{matrix}1 & if P ⌢ ⌣_{i}Σ, \\ 0 & otherwise, \end{matrix}  (24)

where i ≥ 1 is fixed. Since 𝔨 is the set of points of the R-module Σ+R^{k}θ^{i} of conjugate shape k^{m−i}u^{i}, we have by Th. 2.4 and Th. 5.3

𝔨(P) = q^{(k−1)(m−i)+(u−1)(i−1)} · \left[{u \atop 1}\right]_{q},  |C| = q^{k(m−i)+ui}.  (25)

Consider the mapping ψ: R → 𝔽_{q}^{m} (cf. [22, Section 3]) defined by the matrix

G = G^{(m)} = [\begin{matrix}1 & 1 & … & 1 \\ a_{1} & a_{2} & … & a_{q^{m−1}} \end{matrix}] ,  (26)

where a_{1}, a_{2}, …, a_{q^{m−1}} are the elements of 𝔽_{q}^{m−1} taken in some order. By [17, Th. 1.1] or [24, Prop. 11],

w_{Ham}(ψ(x) − ψ(y)) = \begin{cases}0 & if x = y, \\ q^{m−1} & if x − y ∈ N^{m−1} \ \{0\}, \\ q^{m−1} − q^{m−2} & if x − y ∉ N^{m−1}. \end{cases}

Thus the q-ary image ψ(C) is a (possibly nonlinear) distance invariant code with parameters N = q^{m−1}𝔨(P) = q^{(k−u)(m−i)+u(m−1)}\left[{u \atop 1}\right]_{q}, M = |C| = q^{(k−u)(m−i)+um}.

The hyperplanes of Π can be divided into i + 1 disjoint nonempty classes, which we denote by (A_{j}), 0 ≤ j ≤ i:

8Note that α_{λ}(m^{1}; q) is already determined by λ′_{m} and |λ| = ∑ λ_{i}.

(A_{j}) hyperplanes Δ with Σ⌢ ⌣_{j}Δ, and Σ ⌢̸ ⌣_{j+1}Δ, 0 ≤ j < i;

(A_{i}) hyperplanes Δ with Σ⌢ ⌣_{i}Δ.

Denote by λ^{(t)} (resp., μ^{(t)}) the shape (resp., conjugate shape) of the module (Δ + R^{k}θ^{t}) ∩ (Σ + R^{k}θ^{i}), 0 ≤ t ≤ m. The nonzero Hamming weights of ψ(C) are

∑_{s=0}^{t−2} a_{s}(q^{m−1} − q^{m−2}) + a_{t−1}q^{m−1} =

= α_{λ^{(0)}}(m^{1}, q)(q^{m−1} − q^{m−2}) − α_{λ^{(t)}}(m^{1}, q)q^{m−1} + α_{λ^{(t−1)}}(m^{1}, q)q^{m−2},

where (a_{0}, …, a_{m}) is one of the possible 𝔨-types of hyperplanes of Π and j+1 ≤ t ≤ m if Δ is of class (A_{j}), 0 ≤ j ≤ i. If Δ is of class (A_{i}) then

μ^{(t)} = \begin{cases}k^{m−i}u^{i} = μ^{(0)} & if 0 ≤ t ≤ i, \\ k^{m−t}(k − 1)^{t−i}u^{i} & if i ≤ t ≤ m. \end{cases}  (27)

Hence α_{λ^{(t)}}(m^{1}, q) = α_{λ^{(t−1)}}(m^{1}, q)/q if i + 1 ≤ t ≤ m, and Δ produces codewords of single nonzero weight

α_{λ^{(0)}}(m^{1}, q)(q^{m−1} − q^{m−2}) = q^{(k−u)(m−i)+u(m−1)−1}(q^{u} − 1).  (28)

If Δ is of class (A_{j}), 0 ≤ j ≤ i − 1, then

μ^{(t)} = \begin{cases}k^{m−i}u^{i} & if 0 ≤ t ≤ j, \\ k^{m−i}u^{i−t+j}(u − 1)^{t−j} & if j ≤ t ≤ i, \\ k^{m−t}(k − 1)^{t−i}u^{j}(u − 1)^{i−j} & if i ≤ t ≤ m. \end{cases}  (29)

Equation (29) is derived e. g. using the formula |U ∩ V | = |U||V |/|U + V | with U = Δ + R^{k}θ^{t}, V = Σ + R^{k}θ^{i}, and observing that Δ + Σ has shape m^{k−1}(m − j)^{1}. Hence we have α_{λ^{(t)}}(m^{1}, q) = α_{λ^{(t−1)}}(m^{1}, q)/q if j + 2 ≤ t ≤ m, and thus Δ produces nonzero codewords of weights (28) and

\begin{matrix}α_{λ^{(0)}}(m^{1}, q)(q^{m−1} − q^{m−2}) − α_{λ^{(j+1)}}(m^{1}, q)q^{m−1} + α_{λ^{(j)}}(m^{1}, q)q^{m−2} = \\ = (α_{λ^{(0)}}(m^{1}, q) − α_{λ^{(j+1)}}(m^{1}, q))q^{m−1} \\ = q^{(k−u)(m−i)+u(m−1)+u−1}. \end{matrix}  (30)

Let K = (k − u)(m − i) + um, U = (k − u)(m − i) + u(m − 1) (whence K − U = u). The code ψ(C) is a two-weight code over a q-ary alphabet of length N, minimum distance D, and with weights W_{1} and W_{2}, where

N = \frac{q^{K} − q^{U}}{q − 1} , |ψ(C)| = q^{K}, D = W_{1} = q^{K−1} − q^{U−1}, W_{2} = q^{K−1}.  (31)

Now we assume that R is one of the chain rings 𝔽_{q}[X; σ]/(X^{m}) of characteristic p. By Th. 5 from [22], the code ψ(C) is linear over 𝔽_{q}, and it has the parameters (31) of a MacDonald code. Since MacDonald codes are uniquely determined by their parameters (cf. [10, 46]), we get that ψ(C) is semilinearly isomorphic to a MacDonald code. Choosing k, u, i appropriately, we can get all MacDonald codes with parameters U ≥ K(1 − 1/m). Hence we have the following theorem (cf. [22] for the special case m = 2):

Theorem 6.1. A q-ary MacDonald code whose parameters K, U satisfy the condition U ≥ K(1 − 1/m) is linearly representable over any of the chain rings 𝔽_{q}[X; σ]/(X^{m}).

Acknowledgements. The authors wish to thank S. Dodunekov, W. Heise, A. Kreuzer, A. Nechaev, J. Simonis, J. Wood, and V. Zinoviev for comments/references. They are indebted to the referee for valuable suggestions which helped to improve the paper. The research of the second author was financially supported by the Alexander-von-Humboldt Stiftung.

References

[1] K. Asano. Über verallgemeinerte Abelsche Gruppen mit hyperkomplexem Operatorenring und ihre Anwendungen. Japanese Journal of Mathematics, 15:231– 253, 1938/39.

[2] C. Bachoc. Applications of coding theory to the construction of modular lattices. Journal of Combinatorial Theory, Series A, 78:92–119, 1997.

[3] I. F. Blake. Codes over integer residue rings. Information and Control, 29:295– 300, 1975.

[4] U. Brehm, M. Greferath, and S. E. Schmidt. Projective geometry on modular lattices. In Buekenhout [5], chapter 21, pages 1115–1142.

[5] F. Buekenhout, editor. Handbook of Incidence Geometry—Buildings and Foundations. Elsevier Science Publishers, 1995.

[6] L. M. Butler. Subgroup Lattices and Symmetric Functions. Number 539 in Memoirs of the American Mathematical Society. American Mathematical Society, 1994.

[7] A. R. Calderbank and N. J. A. Sloane. Modular and p-adic cyclic codes. Designs, Codes and Cryptography, 6:21–35, 1995.

[8] W. E. Clark and D. A. Drake. Finite chain rings. Abhandlungen aus dem mathematischen Seminar der Universität Hamburg, 39:147–153, 1974.

[9] C. W. Curtis and I. Reiner. Representation Theory of Finite Groups and Associative Algebras. John Wiley & Sons, Wiley Classics Library edition, 1988.

[10] S. Dodunekov and J. Simonis. Codes and projective multisets. Electronic Journal of Combinatorics, 5(#R37), 1998.

[11] S. T. Dougherty, P. Gaborit, M. Harada, A. Munemasa, and P. Solé. Type IV self-dual codes over rings. IEEE Transactions on Information Theory, 45(7):2345–2360, Nov. 1999.

[12] S. T. Dougherty, P. Gaborit, M. Harada, and P. Solé. Type II codes over 𝔽_{2}+u𝔽_{2}. IEEE Transactions on Information Theory, 45(1):32–45, Jan. 1999.

[13] T. Ericson, J. Simonis, H. Tarnanen, and V. A. Zinoviev. F -partitions of cyclic groups. AAECC, 8:387–393, 1997.

[14] T. Ericson and V. A. Zinoviev. On Fourier-invariant partitions of finite abelian groups and the MacWilliams identity for group codes. Problems of Information Transmission, 32(1):117–122, 1996.

[15] C. Faith. On Köthe rings. Mathematische Annalen, 164:207–212, 1966.

[16] P. Gaborit. Mass formulas for self-dual codes over ℤ_{4} and 𝔽_{q} + u𝔽_{q}-rings. IEEE Transactions on Information Theory, 42:1222–1228, 1996.

[17] M. Greferath and S. E. Schmidt. Gray isometries for finite chain rings. IEEE Transactions on Information Theory, 45(7):2522–2524, Nov. 1999.

[18] M. Hall, Jr. A type of algebraic closure. Annals of Mathematics, 40:360–369, 1939.

[19] W. Heise and P. Quattrocchi. Informations- und Codierungstheorie. Springer-Verlag, Berlin, 3rd edition, 1995.

[20] T. Honold and I. Landjev. Linear codes over finite chain rings. In Optimal Codes and Related Topics, pages 116–126, Sozopol, Bulgaria, 1998.

[21] T. Honold and I. Landjev. All Reed-Muller codes are linearly representable over the ring of dual numbers over ℤ_{2}. IEEE Transactions on Information Theory, 45(2):700–701, Mar. 1999.

[22] T. Honold and I. Landjev. Linearly representable codes over chain rings. Abhandlungen aus dem mathematischen Seminar der Universität Hamburg, 69:187–203, 1999.

[23] T. Honold and I. Landjev. MacWilliams identities for linear codes over finite Frobenius rings. Submitted for publication, Oct. 1999.

[24] T. Honold and A. A. Nechaev. Weighted modules and representations of codes. Problems of Information Transmission, 35(3):205–223, 1999.

[25] S. K. Jain, J. Luh, and B. Zimmermann-Huisgen. Finite uniserial rings of prime characteristic. Communications in Algebra, 16(10):2133–2135, 1988.

[26] E. Kleinfeld. Finite Hjelmslev planes. Illinois Journal of Mathematics, 3:403– 407, 1959.

[27] M. Klemm. Über die Identität von MacWilliams für die Gewichtsfunktion von Codes. Archiv der Mathematik, 49:400–406, 1987.

[28] G. Köthe. Verallgemeinerte Abelsche Gruppen mit hyperkomplexem Operatorenring. Mathematische Zeitschrift, 39:31–44, 1935.

[29] A. Kreuzer. Hjelmslev-Räume. Resultate der Mathematik, 12:148–156, 1987.

[30] A. Kreuzer. Projektive Hjelmslev-Räume. Dissertation, Technische Universität München, 1988.

[31] A. Kreuzer. Hjelmslevsche Inzidenzgeometrie - Ein Bericht. Bericht TUM-M9001, Technische Universität München, Jan. 1990. Beiträge zur Geometrie und Algebra Nr. 17.

[32] A. Kreuzer. Fundamental theorem of projective Hjelmslev spaces. Mitteilungen der Mathematischen Gesellschaft in Hamburg, 12(3):809–817, 1991.

[33] A. Kreuzer. A system of axioms for projective hjelmslev spaces. Journal of Geometry, 40:125–147, 1991.

[34] I. Landjev. A note on the MacWilliams identities. Compt. Rend. Bulg. Acad. Sci., 52, 1999.

[35] S. Lang. Algebra. Addison-Wesley Publishing Company, 2nd edition, 1984.

[36] I. G. MacDonald. Symmetric Functions and Hall Polynomials. Oxford University Press, 2nd edition, 1995.

[37] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland Publishing Company, Amsterdam, 1977.

[38] B. R. McDonald. Finite Rings with Identity. Marcel Dekker, New York, 1974.

[39] T. Mora and H. F. Mattson, Jr., editors. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC) 12, number 1255 in Lecture Notes in Computer Science. Springer-Verlag, 1997.

[40] A. A. Nechaev. Finite principal ideal rings. Russian Academy of Sciences. Sbornik. Mathematics, 20:364–382, 1973.

[41] A. A. Nechaev. Linear codes over modules and over spaces. MacWilliams’ identity. In Proceedings of the 1996 IEEE Int. Symp. Inf. Theory and Appl., pages 35–38, Victoria B.C., Canada, 1996.

[42] A. A. Nechaev and A. S. Kuzmin. Linearly presentable codes. In Proceedings of the 1996 IEEE Int. Symp. Inf. Theory and Appl., pages 31–34, Victoria B.C., Canada, 1996.

[43] A. A. Nechaev and A. S. Kuzmin. Formal duality of linear presentable codes over a Galois field.

[44] A. A. Nechaev, A. S. Kuzmin, and V. T. Markov. Linear codes over finite rings and modules. Preprint N 1995-6-1, Center of New Information Technologies, Moscow State University, 1995.

[45] R. Raghavendran. Finite associative rings. Compositio Mathematica, 21:195– 229, 1969.

[46] F. Tamari. On linear codes which attain the Solomon-Stiffler bound. Discrete Mathematics, 49:179–191, 1984.

[47] F. D. Veldkamp. Geometry over rings. In Buekenhout [5], chapter 19, pages 1033–1084.

[48] J. A. Wood. Extension theorems for linear codes over finite rings. In Mora and Mattson [39], pages 329–340.

[49] J. A. Wood. Codes of constant Lee or Euclidean weight. Extended Abstract for the Workshop on Coding and Cryptography (WCC 99), Paris 1999.

[50] J. A. Wood. Duality for modules over finite rings and applications to coding theory. American Journal of Mathematics, 121(3):555–575, 1999.

[51] J. A. Wood. Weight functions and the extension theorem for linear codes over finite rings. In G. L. M. Ronald C. Mullin, editor, Finite Fields: Theory, Applications, and Algorithms, volume 225 of Contemporary Mathematics, pages 231–243. American Mathematical Society, 1999.