HOW TO OBTAIN LATTICES FROM (f, σ, δ)-CODES VIA A
GENERALIZATION OF CONSTRUCTION A

arXiv:1607.03787v2 [cs.IT] 30 Sep 2017

S. PUMPLÜN
Abstract. We show how cyclic (f, σ, δ)-codes over finite rings canonically induce
a Z-lattice in RN by using certain quotients of orders in nonassociative division
algebras defined using the skew polynomial f . This construction generalizes the
one using certain σ-constacyclic codes by Ducoat and Oggier, which used quotients
of orders in non-commutative associative division algebras defined by f , and can
be viewed as a generalization of the classical Construction A for lattices from
linear codes. It has the potential to be applied to coset coding, in particular to
wire-tap coding. Previous results by Ducoat and Oggier are obtained as special
cases.

Introduction
In the classical Construction A, a lattice is obtained by lifting a linear code over
some finite ring [19]. This idea was recently generalized to the non-commutative setting by considering natural orders in cyclic algebras over number fields: by taking the
quotient of the natural order by a suitable ideal, a ring is obtained which is isomorphic to the quotient of a twisted polynomial ring by some polynomial [21, 43]. This
established a connection between twisted polynomials and certain σ-constacyclic
codes.
We generalize Construction A using skew polynomial rings S[t; σ, δ] and construct
lattices by lifting cyclic (f, σ, δ)-codes, i.e. much more general linear codes than
considered in [21, 43], to lattices in nonassociative algebras. The multiplicative
structure of the algebra is not necessary to build a lattice, so we do not limit our
considerations to associative algebras as has been done so far.
As recently several classes of cyclic (f, σ, δ)-codes were constructed with a better
minimal distance for certain lengths than previously known codes (e.g., see [6], [7],
[8], [9], [10], [12], [11] [16], [22], [29], [38], [62]), (f, σ, δ)-codes become increasingly
important. These codes employ skew polynomial rings S[t; σ, δ] where S is a unital
ring, σ an injective endomorphism of S and δ a left σ-derivation of S, and are built
by choosing a monic polynomial f ∈ S[t; σ, δ] of degree m, and some monic right
2010 Mathematics Subject Classification. Primary: 17A35; Secondary: 11T71, 94B40, 94B05.
Key words and phrases. Space-time block code, linear (f, σ, δ)-code, nonassociative algebra, coset
coding, wiretap coding, Construction A, order, skew polynomial ring.
1

2

S. PUMPLÜN

divisor g of f [14]. Every cyclic (f, σ, δ)-code is associated with a principal left ideal
of a unital nonassociative algebra Sf defined by f , which is generated by some monic
right divisor g of f .
The nonassociative algebra Sf = S[t; σ, δ]/S[t; σ, δ]f is defined on the additive
subgroup {h ∈ S[t; σ, δ] | deg(h) < m} of S[t; σ, δ] by using right division by f to
define the algebra multiplication g ◦h = gh modr f [54]. This can be seen as a canonical generalization of associative quotient algebras S[t; σ, δ]/(f ), where we factor out
a two-sided ideal generated by f , which occurs when Rf is a two-sided ideal. If S
is a division algebra, the associative quotient algebras S[t; σ, δ]/(f ) as well as the
right nuclei of the nonassociative algebras Sf were used when constructing central
simple algebras for instance in [1], [2], [30], [31, Sections 1.5, 1.8, 1.9], [45]. Due
to their large nuclei, the algebras Sf were also successfully employed to systematically build fast-decodable fully diverse space-time block codes in [51, 57, 39], see
[52], which are used for reliable high rate transmission over wireless digital channels
with multiple antennas transmitting and receiving the data. Skew-polynomial rings
and their ideals have been already used in other applications and when generalizing
other classical notions like Gröbner bases [3] to a non-commutative setting, e.g. see
[15, 17, 36, 37, 33, 34, 47, 48, 61], where they appear as examples of solvable polynomial rings, operator theory [28], and other codes, in particular (cyclic) convolutional
codes and MDS codes cf. [23, 24, 26, 27, 40, 41, 42].
We choose suitable monic irreducible skew polynomials f ∈ K[t, σ, δ] with K/F
a finite field extension of number fields, or f ∈ D[t, σ, δ] with D a cyclic division
algebra over a number field, and define natural orders Λ in Sf . We then use the
quotient of Λ by certain two-sided ideals to canonically construct a lattice L in RN ,
i.e. a Z-module L of rank N , from a cyclic (f, σ, δ)-code over a finite ring.
The non-commutative setup treated in [21, 43] is obtained as the special case
where K/F is a cyclic field extension of degree n and f (t) = tn − c ∈ OF [t; σ] is
(right-)invariant, i.e. satisfy f R ⊂ Rf , which makes Rf a two-sided ideal, and Sf
non-commutative, but still associative.
The advantage of using nonassociative algebras as we do is the fact that this does
not limit our choices of skew polynomials f to those which create two-sided ideals
Rf . This means that we have a much larger choice of lattices we can build. Lattices
now can be obtained by lifting any cyclic (f, σ, δ)-code, moreover, we can also lift σconstacyclic codes to lattices (now sitting inside nonassociative algebras). Sometimes
there exist easy conditions for nonassociative cyclic algebras to be division algebras
which is an additional bonus.
Our construction A can be used to encode space-time block codes, for coset coding,
and in particular for wiretap coding.

HOW TO OBTAIN LATTICES FROM (f, σ, δ)-CODES

3

The paper is organized as follows: After collecting the results we need in Section
1, for monic and irreducible f ∈ K[t; σ, δ] we define a natural order in Sf , and
investigate the quotients of a natural order by some ideals in Section 2. These
results are then generalized in Section 4 to monic irreducible f ∈ D[t; σ, δ], where
D = (K/F, ρ, c) is a cyclic division algebra. In Sections 3 and 5, we describe a
lattice encoding of certain cyclic (f, σ, δ)-codes over the finite rings OK /pOK , where
p is a maximal ideal in some suitable subring of OK , and how it can be applied to
space-time block codes.
Throughout the paper we will put a special emphasis on the nonassociative cyclic
algebras (K/F, σ, c) employed in [58], and on the generalized nonassociative cyclic
algebras (D, σ, d), since these are used for iterated space-time block codes [51], [52].
1. Preliminaries
1.1. Nonassociative algebras. Let R be a unital commutative ring and let A
be an R-module. We call A an algebra over R if there exists an R-bilinear map
A × A → A, (x, y) 7→ x · y, denoted simply by juxtaposition xy, the multiplication
of A. An algebra A is called unital if there is an element in A, denoted by 1, such
that 1x = x1 = x for all x ∈ A. We will only consider unital algebras.
For an R-algebra A, the left nucleus of A is defined as Nucl (A) = {x ∈ A | [x, A, A] =
0} where [x, y, z] = (xy)z − x(yz) for x, y, z ∈ A, the middle nucleus as Nucm (A) =
{x ∈ A | [A, x, A] = 0} and the right nucleus as Nucr (A) = {x ∈ A | [A, A, x] = 0}.
Their intersection Nuc(A) = {x ∈ A | [x, A, A] = [A, x, A] = [A, A, x] = 0} is the nucleus of A. The center of A is C(A) = {x ∈ A | x ∈ Nuc(A) and xy = yx for all y ∈
A} [56].
Let R be a Noetherian integral domain with quotient field F and A a finitedimensional unital F -algebra. Then an R-lattice in A is an R-submodule Γ of
A which is finitely generated and contains an F -basis of A. An R-order in A is
a multiplicatively closed R-lattice containing 1A (the multiplication may be not
associative). An R-order will be called maximal if Γ′ ⊂ Γ implies Γ′ = Γ for every
R-order Γ′ in A.
An algebra A 6= 0 over a field F is called a division algebra, if for any a ∈ A,
a 6= 0, the right multiplication with a, La (x) = ax, and the right multiplication with
a, Ra (x) = xa, are bijective. Any division algebra is simple, that means has only
trivial two-sided ideals. A finite-dimensional algebra A is a division algebra over F
if and only if A has no zero divisors.
1.2. Skew polynomial rings. Let S be a unital (not necessarily commutative)
ring, σ an injective ring homomorphism of S and δ : S → S a left σ-derivation,
i.e. an additive map such that δ(ab) = σ(a)δ(b) + δ(a)b for all a, b ∈ S, implying
δ(1) = 0. Let Const(δ) = {a ∈ S | δ(a) = 0} and Fix(σ) = {a ∈ S | σ(a) = a}.

4

S. PUMPLÜN

The skew polynomial ring R = S[t; σ, δ](defined first by Ore [46]) is the set of skew
polynomials a0 + a1 t + · · · + an tn with ai ∈ S, where addition is defined term-wise
and multiplication by ta = σ(a)t + δ(a) for all a ∈ S (for properties see [18, 25, 28]).
The ring S[t; σ] = S[t; σ, 0] is called a twisted polynomial ring and S[t; δ] = S[t; id, δ]
a differential polynomial ring.
For f = a0 + a1 t + · · · + an tn with an 6= 0 define deg(f ) = n and deg(0) = −∞.
Then deg(f g) ≤ deg(f ) + deg(g) with equality if
• f has an invertible leading coefficient,
• g has an invertible leading coefficient,
• S is a domain.
An element f ∈ R is irreducible in R if it is not a unit and it has no proper factors,
i.e if there do not exist g, h ∈ R with deg(g), deg(h) < deg(f ) such that f = gh.

1.3. How to obtain nonassociative algebras from skew polynomial rings.
From now on, let R = S[t; σ, δ] and σ injective. We do not assume S to be a
division ring. We can still perform a right division by a polynomial f ∈ R which has
invertible leading coefficient dm : for all g(t) ∈ R of degree l > m, there exist uniquely
determined r(t), q(t) ∈ R with deg(r) < deg(f ), such that g(t) = q(t)f (t) + r(t). Let
modr f denote the remainder of right division by such an f [54, Proposition 1].
Pm
i
Suppose f (t) =
i=0 di t ∈ R = S[t; σ, δ] has an invertible leading coefficient
dm . Let Rm = {g ∈ R | deg(g) < m}. Then Rm together with the multiplication
g ◦ h = gh modr f becomes a unital nonassociative ring Sf = (Rm , ◦) also denoted
by R/Rf [54].
This construction was introduced by Petit [49, 50] for unital division rings S. Sf is
a unital nonassociative algebra over S0 = {a ∈ S | ah = ha for all h ∈ Sf } which is a
commutative subring of S. We call Sf a Petit algebra. The algebra Sf is associative
if and only if Rf is a two-sided ideal in R ([54, Theorem 4 (ii)], or [49, (1)] if S is
a division ring). For all invertible a ∈ S we have Sf ∼
= Saf , so that without loss of
generality it suffices to only consider monic polynomials in the construction.
If Sf is not associative then S ⊂ Nucl (Sf ) and S ⊂ Nucm (Sf ), Nucr (Sf ) = {g ∈
Rm | f g ∈ Rf } and S0 is the center of Sf [54]. It is easy to see that C(S) ∩ Fix(σ) ∩
Const(δ) ⊂ S0 .
If S is a division algebra and Sf is a finite-dimensional vector space over S0 , then
Sf is a division algebra if and only if f (t) is irreducible in R [49, (9)].
P
i
For f (t) = m
i=0 di t ∈ S[t; σ], t is left-invertible in Sf if and only if d0 is invertible
by a simple degree argument. Thus if f is irreducible (hence d0 6= 0) and S a division
ring then t is always left-invertible in Sf and S0 = Fix(σ) ∩ C(S) is the center of Sf
[54, Theorem 8 (ii)].

HOW TO OBTAIN LATTICES FROM (f, σ, δ)-CODES

5

The S-basis 1, t, t2 , . . . , tn−1 is the canonical basis for the left S-module Sf . Since
S ⊂ Nucm (Sf ) and S ⊂ Nucl (Sf ), the right multiplication with 0 6= a ∈ Sf in Sf ,
Rh : Sf −→ Sf , p 7→ pa, is an S-module endomorphism, and after expressing Ra in
matrix form with respect to the canonical basis of Sf , the map
γ : Sf → EndK (Sf ), a 7→ Ra
induces an injective S-linear map
γ : Sf → Matm (S), a 7→ Ra 7→ M (a).
This fact is exploited when designing space-time block codes which employ one of
the following two special cases of algebras:
Definition 1. (i) Let S/S0 be an extension of commutative unital rings and G = hσi
a finite cyclic group of order m acting on S such that S0 = Fix(σ). For any c ∈ S,
Sf = S[t; σ]/S[t; σ](tm − c)
is called a nonassociative cyclic algebra (S/S0 , σ, c) of degree m.
(ii) Let D be a finite-dimensional central division algebra over F = C(D) of degree
n, σ ∈ Aut(D) such that σ|F has finite order m and f (t) = tm − d ∈ D[t; σ]. Let
F0 = F ∩ Fix(σ). The F0 -algebra Sf = D[t; σ]/D[t; σ]f (t) is called a (generalized)
nonassociative cyclic algebra of degree m. We denote this algebra by (D, σ, d) and
call 1, e, . . . , en , t, et . . . , en−1 t, . . . en tm−1 its canonical basis as a left K-vector space.
Remark 1. If c ∈ S \ S0 , then (S/S0 , σ, c) has nucleus S and center S0 . These
algebras first appeared over finite fields in [55], over general fields they were studied
in [59], and over number fields, in [58]. If c ∈ S0× , S[t; σ]/S[t; σ](tm − c) is a classical
associative cyclic algebra, cf. [21], [43]. If c = 0, S[t; σ]/S[t; σ](tm ) is a commutative
associative algebra, the direct product of m copies of S. If S/S0 is a cyclic Galois field
extension of degree m with Galois group hσi and c ∈ S \S0 , then Nuc((S/S0 , σ, c)) =
K. If m is prime then (S/S0 , σ, c) is a division algebra. For non-prime m, a division
algebra for all choices of c such that 1, c, . . . , cm−1 are linearly independent [59].
Example 2. Let F and L be fields, F0 = F ∩ L, and let K be a cyclic field extension
of both F and L such that Gal(K/F ) = hρi and [K : F ] = n, Gal(K/L) = hσi and
[K : L] = m, such that ρ and σ commute. Let D = (K/F, ρ, c) be an associative
cyclic division algebra over F of degree n with canonical basis 1, e, . . . , en−1 (where
en = c, el = ρ(l)e for every l in K), and c ∈ F0 . For x = x0 + x1 e + x2 e2 + · · · +
xn−1 en−1 ∈ D, extend σ to an automorphism σ ∈ AutL (D) of order m via
σ(x) = σ(x0 ) + σ(x1 )e + σ(x2 )e2 + · · · + σ(xn−1 )en−1 .

6

S. PUMPLÜN

For all d ∈ D × , Sf = D[t; σ]/D[t; σ](tm − d) is the generalized nonassociative cyclic
algebra (D, σ, d) of dimension m2 n2 over F0 . For all d ∈ F × , we have
Sf = D[t; σ]/D[t; σ](tm − d) = (L/F0 , ρ, c) ⊗F0 (F/F0 , σ, d) = (D, σ, d)
(D, σ, d) is associative if and only if d ∈ F0 . For f ∈ F0 [t], (D, σ, d) is a generalized
cyclic algebra of degree n [31, Section 1.4].
1.4. Space-time block coding. An (s × t) space-time block code (STBC) is a set
C of complex s × t matrices. C is called linear if X, X ′ ∈ C implies X ± X ′ ∈ C. A
linear code is called fully diverse, if detX 6= 0 for all 0 6= X ∈ C.
Let K/F be a Galois field extension of degree n and K an imaginary number field.
Nonassociative cyclic division algebras A = (K/F, σ, c) of degree n can be used to
build linear n × n STBCs with entries in K, since the right multiplication in A
induces the injective K-linear map γ : A ֒→ EndK (A) ֒→ Mat( K), a 7→ Ra 7→ M (a)
(cf. Section 1.3). The set of matrices γ(A) is a linear STBC that is fully diverse
since A is a division algebra.
Let A = (D, σ, d) be a generalized nonassociative cyclic division algebra, with
D = (K/F, σ, c) an associative cyclic algebra of degree n. Again, A can be used to
build a fully diverse linear mn × mn STBC with entries in K: we know γ : A ֒→
EndD (A), a 7→ Ra is an injective D-linear map, and K ⊂ D. Using the canonical
K-basis of A, we obtain an mn × mn-matrix M (a) representing Ra for every a ∈ A.
Thus we have γ : A ֒→ EndD (A) ֒→ Matmn (K), a 7→ Ra 7→ M (a) and γ(A) is a
fully diverse linear STBC.
When d ∈ L× or d ∈ F × , γ(A) is used for the codes in [53], [52], [57]. For m = 2,
γ(A) is used in the iterated codes constructed in [39]. In particular, for d ∈ F × the
algebra in Example 2 is employed for the space-time block codes in [57], see also
[51].
1.5. Cyclic (f, σ, δ)-codes. Let f ∈ S[t; σ, δ] be monic of degree m and σ injective.
P
i
We associate to an element a(t) = m−1
i=0 ai t in Sf the vector (a0 , . . . , am−1 ). A
linear code of length m over S is a submodule of the S-module S m . Conversely,
for any linear code C of length m we denote by C(t) the set of skew polynomials
P
i
a(t) = m−1
i=0 ai t ∈ Sf associated to the codewords (a0 , . . . , am−1 ) ∈ C.
A cyclic (f, σ, δ)-code C ⊂ S m is a set consisting of the vectors (a0 , . . . , am−1 )
Pm−1 i
obtained from elements h =
i=0 ai t in a left principal ideal Sf g where Sf =
S[t; σ, δ]g/S[t; σ, δ]f , and g is a monic right divisor of f . A code C over S is called
σ-constacyclic if there is a non-zero c ∈ S such that
(a0 , . . . , am−1 ) ∈ C ⇒ (σ(am−1 )c, σ(a0 ), . . . , σ(am−2 )) ∈ C.
Lemma 3. (cf. [54, Proposition 7]) Let f ∈ R = S[t; σ, δ] be monic of degree m.
(a) Let σ be injective. Then:

HOW TO OBTAIN LATTICES FROM (f, σ, δ)-CODES

7

• Every right divisor g of f of degree < m with an invertible leading coefficient
generates a principal left ideal in Sf .
• All left ideals in Sf which contain a non-zero polynomial g of minimal degree
with invertible leading coefficient are principal left ideals, and g is a right
divisor of f in R.
• ([14, Theorem 1]) Each principal left ideal generated by a monic right divisor
of f is an S-module which is isomorphic to a submodule of S m and forms a
code of length m and dimension m − deg(g).
(b) Let S be a division ring. Then all left ideals in Sf are generated by some monic
right divisor g of f in R.
Proof. (a) Let g(t) be such a right divisor of f (t), then the ideal Rf is contained in
Rg and it is easy to check that Rg/Rf = {h ∈ Rm | h = sg for some s ∈ Rm } is a
left ideal in Sf .
The proof of the second assertion is similar to the one of [13, Lemma 1]: Suppose
that I is a left ideal in Sf which contains a non-zero polynomial g of minimal degree
with invertible leading coefficient. For any p ∈ I ⊂ Rm , a right division by g yields
unique r, q ∈ R with deg(r) < deg(g) such that p = qg + r and hence r = p − qg ∈ I.
Since we chose g ∈ I to have minimal degree, we conclude that r = 0, implying
p = qg and so I = Rg is a principal left ideal, and g is a right divisor of f in R.
(b) Let I be a left ideal of Sf . If I = {0} then I = (0). So suppose I 6= (0) and
choose a monic non-zero polynomial g in I ⊂ Rm of minimal degree. As in the proof
of (i), for any p ∈ I, a right division by g yields unique r, q ∈ R with deg(r) < deg(g)
such that p = qg + r and hence r = p − qg ∈ I. Since g ∈ I has minimal degree,
r = 0, and so I = Rg.

Let f, g, h, h′ ∈ S[t; σ, δ] be monic polynomials such that f = gh = h′ g. Let C be
P
i
the cyclic (f, σ, δ)-code corresponding to g and c(t) = m−1
i=0 ci t ∈ S[t; σ, δ]. Then
(c0 , . . . , cm−1 ) ∈ C is equivalent to c(t)h(t) = 0 in Sf [14, Theorem 2], i.e. h is a
parity check polynomial for C.
The codes C of length m we consider consist of all elements (a0 , . . . , am−1 ) obtained
P
i
from polynomials a(t) = m−1
i=0 ai t in a left principal ideal Sf g of Sf , with g a monic
right divisor of f ; σ-constacyclic codes are obtained when f (t) = tm − c ∈ S[t; σ].
For a field K, every skew polynomial ring K[t; σ, δ] can be made into either a
twisted or a differential polynomial ring by a linear change of variables [31, 1.1.21].
When constructing linear codes, however, we will consider general skew polynomial rings. They might produce better distance bounds than cyclic (f, σ, δ)-codes
constructed only with an automorphism, where δ = 0, see [9] for examples of this
phenomenon.

8

S. PUMPLÜN

2. Natural orders in Sf and their quotients by a prime ideal, I
In the following, we use the notation from [21, Section 2]. Let K/F be a Galois
extension of number fields of degree n with OF and OK the rings of integers of F ,
respectively K.
2.1. Let p be a maximal ideal of OF , p the prime lying below p and OF /p = Fpj ,
where j is the inertial degree of p above p. Let π : OK −→ OK /pOK be the canonical
projection. Let σ ∈ G = Gal(K/F ). We have σ(pOK ) ⊂ pOK since σ|F = id. Thus
σ induces a ring homomorphism
σ : OK /pOK −→ OK /pOK ,

a + pOK 7→ σ(a) + pOK

with π ◦ σ|OK = σ ◦ π and Fix(σ) = Fpj . Suppose that δ is an F -linear left σderivation on K such that δ(OK ) ⊂ OK . Then δ induces a left σ-derivation δ :
OK /pOK −→ OK /pOK . Since OK is a Dedekind domain we have
e

pOK = pe11 pe22 . . . pgg
for suitable prime (maximal) ideals pi of OK , ei ≥ 0. The ideals pet t are pair-wise
comaximal. By the Chinese Remainder Theorem, we have thus the following direct
sum of rings:
e
eg
OK /pOK = OK /pe11 · · · pgg OK ∼
= OK /pe11 OK × · · · × OK /pg OK .

G acts trivially on each of these pt , therefore there is an induced action of G on
each OK /pet t OK and the above is an isomorphism of G-modules (cf. [43, (9)]). That
means on each ring OK /pet t OK there is a canonical induced automorphism σ and a
canonical left σ-derivation δ induced by δ.
In particular, if p is inert in K/F , pOK is a prime ideal in OK and thus OK /pOK =
Fpnj a finite field, and σ ∈ Gal(Fpnj /Fpj ) (cf. [21, Section 2] if δ = 0 and K/F is
cyclic).
P
i
2.2. Suppose f (t) = m
i=0 di t ∈ OK [t; σ, δ] is monic and irreducible in K[t; σ, δ].
Consider the nonassociative division algebra
Sf = K[t; σ, δ]/K[t; σ, δ]f
over F . Then the nonassociative OF -algebra
Λ = OK [t; σ, δ]/OK [t; σ, δ]f
is an OF -order in Sf called the natural order and Λ = OK ⊕ OK t ⊕ · · · ⊕ OK tm−1
as left OK -module. Since f is irreducible in K[t; σ, δ], Λ does not have any zero
divisors. The center of Λ contains OF . Hence for every maximal ideal p in OF , pΛ
is a two-sided ideal of Λ.

HOW TO OBTAIN LATTICES FROM (f, σ, δ)-CODES

9

Λ is usually not maximal, but it is uniquely determined whenever Rf is not
a two-sided ideal, since in that case K is the left and middle nucleus of Sf and
uniquely determines OK and in turn Λ. (For examples of classes of maximal orders
in nonassociative cyclic algebras of degree two, cf. [32, 35], the results there can be
generalized to nonassociative algebras of any degree n.)
Remark 4. Sf is associative if and only if Rf is a two-sided ideal [54, Theorem
4 (ii)]. Therefore our definition generalizes the non-commutative natural orders in
[21] which were only defined for two-sided ideals Rf and δ = 0.
Pm−1 i
P
i
For any g(t) = m−1
i=0 ai t ∈ (OK /pOK )[t; σ, δ]
i=0 ai t ∈ OK [t; σ, δ] define g(t) =
Pm
i
with ai = ai + pOK . Let f (t) = i=0 di t ∈ (OK /pOK )[t; σ, δ] with di = di + pOK .
Lemma 5. (i) The surjective homomorphism of nonassociative rings
Ψ : Λ −→ Sf ,

g 7→ g

has kernel pΛ.
(ii) Ψ induces an Fpj -algebra isomorphism given by
Ψ : Λ/pΛ −→ Sf ,

g + pΛ 7→ g.

Proof. (i) Λ is nonassociative OF -algebra and Ψ is a well-defined surjective hoPm−1 i
momorphism with kernel pΛ: For all g =
i=0 bi t ∈ pΛ it follows that g =
Pm−1 i
i=0 bi t = 0 in (OK /pOK )[t; σ, δ], so that pΛ ⊂ ker(Ψ).
Suppose conversely there is a nonzero g ∈ Λ such that Ψ(g) = g = 0, then
g = hf + r in OK [t; σ, δ] with a nonzero r ∈ OK [t; σ, δ], and so g = h f + r with r = 0
P
i
in (OK /pOK )[t; σ, δ]. We have pΛ = {al | a ∈ p, l ∈ Λ} = { m−1
i=0 ai t | ai ∈ pOK }.
This implies that r ∈ pOK [t; σ, δ] = pΛ.
(ii) follows from (i).

Example 6. Let Gal(K/F ) = < σ > and f (t) = tn − d ∈ OK [t; σ] irreducible in
K[t; σ]. A = (K/F, σ, d) is a nonassociative cyclic division algebra of degree n over

F and Sf = (OK /pOK )/Fpj , σ, d with f (t) = tn − d ∈ (OK /pOK )[t; σ]. If d ∈ OF
is non-zero, A is associative and Λ depends on the choice of the maximal subfield K
in A. Then Sf is an associative (generalized) cyclic algebra as in [21, 43] and f (t)
is reducible whenever OK /pOK is a field.
If d ∈ OK \ OF , A is not associative and the natural order
Λ = OK [t; σ]/OK [t; σ]f = OK ⊕ OK t ⊕ · · · ⊕ OK tn−1
of A is uniquely determined. If n is prime then f is irreducible and A a division
algebra for every d ∈ OK \ OF . If n is not prime and 1, d, . . . , dn−1 are linearly
independent then f is irreducible and A a division algebra (Remark 1). Furthermore,
Λ/pΛ ∼
= ((OK /pOK )/Fpj , σ, d) = Sf .

10

S. PUMPLÜN

Remark 7. Suppose that K/F is cyclic of degree n and inertial with respect to p,
P
then OK /pOK = Fpjn and Gal(Fpjn /Fpj ) = hσi. Let f (t) = ni=0 di ti ∈ OK [t; σ, δ]
be such that f (t) = tn − d0 .
(i) In [21], only polynomials f (t) = tn −d0 with d0 ∈ OF are considered which makes
the ideal (OK /pOK )[t; σ]f two-sided and the resulting Fpj -algebra associative. In
this case, f (t) = tn − d0 is always reducible in Fpjn [t; σ].
(ii) By Lemma 3, if f is irreducible, then Sf has no non-trivial left ideals. For
instance, if n is prime and d0 6∈ OF then for all d0 6= 0,
Λ/pΛ ∼
= (Fpjn /Fpj , σ, d0 )
is always a division algebra, i.e. f (t) = tn − d0 is irreducible, and so there are no
non-trivial left ideals by Lemma 3 (b).
3. Lattice encoding of cyclic (f, σ, δ)-codes over OK /pOK , I
We keep the assumptions and notation from Section 2. Let I = Λg(t) be a
principal left ideal of Λ generated by a monic polynomial g(t) such that p ⊂ I ∩ OF .
Then I/pΛ is a principal left ideal of Λ/pΛ and Ψ(I/pΛ) is a principal left ideal
of ((OK /pOK )/Fpj , σ, c) generated by the monic polynomial Ψ(g + pΛ) = g. That
means, Ψ(I/pΛ) corresponds to an (f , σ, δ)-code C over Fq . In particular, if we
choose f (t) such that f (t) = tm − c with c non-zero, then Ψ(I/pΛ) corresponds to
a σ-constacyclic code over Fq .
If f is irreducible and OK /pOK a field, then Sf has no nontrivial principal left
ideals which contain a non-zero polynomial of minimal degree with invertible leading
coefficient and so C has length n and dimension n, or is zero, whereas when f is
reducible and OK /pOK a field, an (f , σ, δ)-code C corresponds to a right divisor g
of f and has dimension n − deg(g). So we will look for irreducible f where f is
reducible.
3.1. Construction A. Let
ρ : Λ −→ Λ/pΛ −→ Ψ(Λ/pΛ)
be the canonical projection Λ −→ Λ/pΛ composed with Ψ. We know that OK is a
free Z-module of rank n[F : Q]. Then
L = ρ−1 (C) = I
is a Z-module of dimension N = nm[F : Q]. The embedding of this lattice into
RN is canonically determined by considering A ⊗Q R. Now all works exactly as
as explained in [21, Section 3.3]. The construction of L can be seen as a noncommutative variation of the classical Construction A in [19].

HOW TO OBTAIN LATTICES FROM (f, σ, δ)-CODES

11

This way we can construct a lattice L in RN from the linear code C over the finite
ring S = OK /pOK . The non-commutative variation of Construction A in [21] is the
special case that f (t) = tn − c ∈ OF [t] ⊂ K[t; σ], where Sf is associative.
Example 8. Let K[t; σ] = Q(i)[t; σ] with σ the complex conjugation, so that F = Q,
OF = Z and OK = Z[i]. Let f (t) = t2 − t + (i− 3) ∈ Z[i][t, σ], then f (t) is irreducible
in Q(i)[t; σ], since σ(z)z − z 6= i − 3 for all z ∈ Q(i) [49, (17)]. Let p = 3. Then
Z[i]/3Z[i] = F9 and using the natural order Λ = Z[i] ⊕ Z[i]t in Sf , we obtain the
nonassociative algebra Λ/3Λ ∼
= Sf over F3 with f (t) = t2 − (α + α3 − 1)t + α − 3 ∈
F9 [t; σ] where σ(α) = α3 , if α is a primitive root of F9 over F3 , that is α2 + 1 = 0.
Since
f (t) = (t − 2 + α)(t + 1 + α),
f is reducible in F9 [t; σ]. The left ideal generated by (t + 1 + α) in Sf yields a cyclic
(f, σ, 0)-code of length 2 and dimension one. Taking the pre-image of it under Ψ it
corresponds to a principal left ideal I/3Λ in Λ/3Λ.
3.2. Examples involving nonassociative quaternion algebras. Let K = Q(i),
F = Q, so that OF = Z and OK = Z[i]. The examples given in [21] are special cases
of our construction using cyclic algebras. We now consider some algebras which are
not associative.
Let f (t) = t2 − bt − c ∈ Z[i][t, σ] be irreducible in Q(i)[t; σ]. This is equivalent to
σ(z)z − bz − c 6= 0 for all z ∈ Q(i) [49, (17)]. In particular, if b, c ∈ Z then f (t) is
irreducible if b2 + 4c < 0 (alternatively, if f is an irreducible polynomial in R) by
[5, Corollary 2.6]. Suppose that f (t) = t2 − c ∈ (Z[i]/pZ[i])[t; σ] for some maximal
ideal p in OF .
For the natural order Λ = Z[i] ⊕ Z[i]t, we obtain the (perhaps nonassociative)
quaternion algebra
Λ/pΛ ∼
= ((Z[i]/pZ[i])/Fpj , σ, c) = Sf .
In particular, Λ/pΛ = (Z[i]/pZ[i]) ⊕ (OK /pOK )t as (Z[i]/pZ[i])-module.
For any choice of c ∈ Z such that c 6∈ pZ[i], f (t) = t2 − c ∈ OK [t, σ] is reducible.
For b = 0 and any choice of c ∈ Z[i] \ Z, f (t) = t2 − c ∈ Z[i][t, σ] is irreducible in
Q(i)[t; σ] and therefore
A = Sf = (Q(i)/Q, σ, c)
a nonassociative quaternion division algebra (for instance, ct = (t2 )t 6= t(t2 ) = σ(c)t
in A.) We can also write A as the Cayley-Dickson doubling Cay(Q(i), c), defined in
the obvious way.
Example 9. Let f (t) = t2 − c ∈ Z[i][t; σ], c ∈ Z[i] \ Z. Choose any p which remains
inert in Q(i), then OK /pOK = Fp2j , where j is the inertial degree of p above p, and
Λ/pΛ ∼
= (Fp2j /Fpj , σ, c).

12

S. PUMPLÜN

If c 6= 0 this is a division algebra because f (t) = t2 − c is irreducible. Given any
principal left ideal I of Λ containing p, Ψ(I/pΛ) is thus either trivial or all of
Sf = Fp2j [t; σ]/Fp2j [t; σ]f .
If c = 0, i.e. when c ∈ pOK then f (t) = t2 and Sf is a commutative associative
algebra. There are no σ-constacyclic codes since here c = 0. Thus this algebra
cannot be used for lattice encoding of σ-constacyclic codes.
E.g., take p = 3. If c = i then Λ/3Λ ∼
= (F9 /F3 , σ, i) is a nonassociative quaternion
division algebra over F3 where σ(α) = α3 , if α is a primitive root of F9 over F3 , that
is α2 + 1 = 0. I = (1+ i)Λ satisfies 3 ∈ I ∩ OF (since 1− 2i ∈ Z[i], so (1+ i)(1− 2i) =
3 ∈ I). Hence I/3Λ is a left principal ideal of Λ/3Λ ∼
= (F9 /F3 , σ, i), generated by
∼
Ψ((1 + i) + 3Λ), implying I/3Λ = (F9 /F3 , σ, i). Since here f is irreducible, the
only available (and trivial) σ-constacyclic code here is the one corresponding to the
algebra (F9 /F3 , σ, i).
If c = 3i, then f (t) = t2 and Λ/3Λ ∼
= (F9 /F3 , σ, 0) is a commutative associative
algebra over F3 . There are no σ-constacyclic codes since c = 0, hence this example
cannot be used for lattice encoding of σ-constacyclic codes.
Example 10. Let f (t) = t2 − c ∈ Z[i][t; σ], c ∈ Z[i] \ Z.
(i) Choose any p which splits in Q(i), e.g. p = 5. Then (5) = (1 + 2i)(1 − 2i) means
that Z[i]/5Z[i] ∼
= Z[i]/(1 − 2i) × Z[i]/(1 + 2i) ∼
= F5 × F5 and
Λ/5Λ = (F5 × F5 ) ⊕ (F5 × F5 )e
is a nonassociative quaternion algebra over F5 with
Λ/5Λ ∼
= ((F5 × F5 )/F5 , σ, c) = Sf with f (t) = t2 − c ∈ (F5 × F5 )[t; σ].
Here, σ(a, b) = (b, a) fixes the elements (a, a), a ∈ F5 . The algebra Λ/5Λ is a split
nonassociative quaternion algebra [60], however for all c 6= 0, f is irreducible in
(F5 × F5 )[t; σ], since c 6∈ F5 . In this case, there are no non-trivial divisors of f and
hence no non-trivial codes to lift. If c = 0 then f (t) = t2 and Λ/5Λ a commutative
associative algebra. There are no σ-constacyclic codes since c = 0.
(ii) Choose p = 2 which ramifies in Q(i). Then Z[i]/2Z[i] ∼
= F2 +F2 v = {0, 1, v, v +1}
2
with v = 0. I.e., F2 + F2 v is the finite chain ring of characteristic 2, nilpotency
index 2 and residue field F2 . Here σ = id,
Λ/2Λ = (F2 + F2 v) ⊕ (F2 + F2 v)e
and we have the following F2 -algebra isomorphism:
Λ/2Λ ∼
= ((F2 + F2 v)/F2 , id, c) = Sf
with f (t) = t2 − c ∈ (F2 + F2 v)[t], c ∈ Z[i] \ Z. For both c = v and c = v + 1, it
is easy to show that f is irreducible, and if c = 0 again f = t2 . We conclude that
p = 2 does not yield an algebra which can be employed for lattice encoding.

HOW TO OBTAIN LATTICES FROM (f, σ, δ)-CODES

13

3.3. For a nonassocative cyclic algebra A = (K/F, σ, c) of prime degree n, A is a
division algebra if and only if c ∈ K \ F . Examples 9 and 10 demonstrate that this
poses a problem when trying to find irreducible f (t) = tn − c such that f (t) = tn − c
is reducible and 0 6= c, since f (t) is either irreducible, or c = 0. This is not the case
when n is not prime:
Example 11. Let f (t) = t4 − c. Let ω15 be a primitive 15th root of unity, K =
−1
Q(i, ω15 + ω15
), and F = Q(i). Choose c ∈ OK \ OF such that 1, c, c2 , c3 are
−1
F -linearly independent. Then D = (Q(i, ω15 + ω15
)/Q(i), σ, c) is a nonassociative
cyclic division algebra of degree 4 and
−1
−1
−1 2
−1 3
Λ = Z[i, ω15 + ω15
] ⊕ Z[i, ω15 + ω15
]t ⊕ Z[i, ω15 + ω15
]t ⊕ Z[i, ω15 + ω15
]t

is the natural order in D.
−1
Let p = (1 + i). Then p is unramified in Q(i, ω15 + ω15
), Z[i]/(1 + i) ∼
= F2 , and
Λ/pΛ ∼
= (F16 /F2 , σ, c)
is a nonassociative cyclic algebra of degree 4 over F2 which for c 6= 0 is never
a division algebra, since 1, c, c2 , c3 are always linearly dependent over F2 . Hence
f (t) = t4 −c is reducible. If c = 1 then given any principal left ideal I of Λ containing
(1 + i) that is generated by a monic polynomial, Ψ(I/(1 + i)Λ) corresponds to a
σ-constacyclic code over F16 .
4. Natural orders in Sf and their quotients by a prime ideal, II
4.1. Let K/F be a cyclic Galois extension of number fields of degree n and let
D = (K/F, ρ, c) be a cyclic division algebra over F such that c ∈ OF× . Let D =
(OK /OF , ρ, c) be the generalized associative cyclic algebra over OF of degree n such
that D ⊗OF F = (K/F, ρ, c) = D. Then D = OK ⊕ OK e ⊕ · · · ⊕ OK en−1 is a natural
OF -order of D, cf. 2.2 or [21].
Let σ ∈ Aut(D) and δ be a σ-derivation on D, satisfying the following criteria:
• F0 = F ∩ Fix(σ) ∩ Const(δ) is a number field.
• σ(D) ⊂ D and δ(D) ⊂ D.
• S0 = OF ∩ Fix(σ) ∩ Const(δ) is the ring of integers of F0 where here σ and
δ denote the restrictions of σ and δ to D.
P
i
Suppose f (t) = m
i=0 di t ∈ D[t; σ, δ] is monic and irreducible in D[t; σ, δ]. Consider the division algebra
Sf = D[t; σ, δ]/D[t; σ, δ]f
over F0 . Then the S0 -algebra
Λ = D[t; σ, δ]/D[t; σ, δ]f

14

S. PUMPLÜN

is an S0 -order in Sf which we call the natural order (this is again usually not
maximal). Λ is not uniquely determined even when Rf is not a two-sided ideal. It
depends on the choice of the maximal subfield in D which we will assume to be K.
Since f is irreducible in D[t; σ, δ], Λ does not have zero divisors. If 1, e, . . . , en−1
is the canonical basis of D then
Λ = OK ⊕ OK e ⊕ · · · ⊕ OK en−1 ⊕ OK t ⊕ OK et ⊕ · · · ⊕ OK en−1 t ⊕ · · · ⊕ OK en−1 tm−1
as left OK -module.
Let p be a prime ideal in S0 such that pOF is maximal. Since S0 lies in the centers
of both D and Λ, pD is a two-sided ideal of D and pΛ is a two-sided ideal of Λ. Let
π : D −→ D/pD be the canonical projection. We have σ(pD) ⊂ pD since p ⊂ Fix(σ)
and σ(D) ⊂ D by assumption. Thus σ induces a ring homomorphism
σ : D/pD −→ D/pD
with Fix(σ) = Fix(σ)/pFix(σ) and π ◦ σ = σ ◦ π. We also have δ(pD) ⊂ pD by
assumption, so that δ induces a left σ-derivation δ : D/pD −→ D/pD with field of
constants Const(δ) = Const(δ)/p. Let
S0 = Fix(σ) ∩ Const(δ) ∩ F
with F = OF /pOF = Fpj , where j is the inertial degree of p above p. For any g(t) =
Pm−1 i
Pm−1 i
i=0 ai t ∈ D[t; σ, δ] define g(t) =
i=0 ai t ∈ (D/pD)[t; σ, δ] with ai = ai + pD.
Pm
i
Let f (t) = i=0 di t ∈ (D/pD)[t; σ, δ] with di = di + pD, then
Sf = (D/pD)[t; σ, δ]/(D/pD)[t; σ, δ]f .
Since S0 = S0 /p ∼
= Fix(σ) ∩ Const(δ) ∩ F , Sf is an algebra over a subfield of Fpj .
Lemma 12. (i) The surjective homomorphism of additive groups
Ψ : Λ −→ (D/pD)[t; σ, δ]/(D/pD)[t; σ, δ]f ,

g 7→ g

has kernel pΛ.
(ii) Ψ induces an S0 -algebra isomorphism
Ψ : Λ/pΛ ∼
= (D/pD)[t; σ, δ]/(D/pD)[t; σ, δ]f , g + pΛ 7→ g
P
Pm−1 i
i
Proof. (i) For all g = m−1
i=0 bi t ∈ pΛ we have g =
i=0 bi t = 0 in (D/pD)[t; σ, δ],
so that pΛ ⊂ ker(Ψ).
Suppose conversely there is a nonzero g ∈ Λ such that Ψ(g) = g = 0, then
g = hf + r in D[t; σ, δ] with a nonzero r ∈ D[t; σ, δ], and so g = h f + r with r = 0
P
i
in (D/pD)[t; σ, δ]. We have pΛ = {al | a ∈ p, l ∈ Λ} = { m−1
i=0 ai t | ai ∈ pD}. This
implies that r ∈ pD[t; σ, δ] = pΛ.
(ii) follows from (i).


HOW TO OBTAIN LATTICES FROM (f, σ, δ)-CODES

15

4.2. A special case. Let Sf = (D, σ, d) be the F0 -algebra constructed in Example
2 where now F , L and K be number fields. Suppose that c ∈ OF0 and that d ∈ OL×
or d ∈ OF× . Then D = (OK /OF , ρ, c) is an associative cyclic algebra over OF of
degree n such that D ⊗OF F = (K/F, ρ, c) = D is a division algebra over F . For
x = x0 + x1 e + x2 e2 + · · · + xn−1 en−1 ∈ D, define
σ(x) = σ(x0 ) + σ(x1 )e + σ(x2 )e2 + · · · + σ(xn−1 )en−1 .
Since c ∈ OF0 , σ ∈ AutL (D) has order m and restricts to σ ∈ AutOL (D).
Let p be a prime ideal in OF0 such that pOF is maximal. Then
Λ/pΛ ∼
= (D/pD)[t; σ]/(D/pD)[t; σ]f ∼
= (D, σ, d)
is an algebra over F0 = OF0 /p, with D = D/pD a generalized associative cyclic
algebra over Fpj = Fix(ρ).
Example 13. Let ω denote the primitive third root of unity, ω7 a primitive 7th root
of unity and θ = ω7 + ω7−1 = 2 cos( 2π
7 ). Put F = Q(θ). Let K = F (ω) = Q(ω, θ) and
consider the quaternion division algebra D = (K/F, σ, −1). Note that σ(ω) = ω 2 .
Let L = Q(ω), so that K/L is a cubic cyclic field extension whose Galois group is
generated by the automorphism τ : ω7 + ω7−1 7→ ω72 + ω7−2 . Note that ω ∈ OL = Z[ω].
The multiplication of the division algebra A = (D, τ, ω) is behind the fully diverse
codes employed in [57] (cf. [51]). Here,
Λ = Z[ω3 , ω7 + ω7−1 ] ⊕ Z[ω3 , ω7 + ω7−1 ]e ⊕ Z[ω3 , ω7 + ω7−1 ]e2 ⊕ . . .
is a natural order in A.
Let p = 2, then p is a prime ideal in OF = Z[ω3 ] which remains prime in OK =
Z[ω3 , ω7 + ω7−1 ] and Z[i]/p ∼
= F4 . p is inert in K = Q(ω3 , ω7 + ω7−1 ). Now
D/pD = (F64 /F8 , σ, −1) ∼
= Mat2 (F8 )
is a split quaternion algebra over F8 . Thus
Λ/pΛ ∼
= (Mat2 (F8 ), τ , ω)
where ω ∈ Z[ω]/2Z[ω].
5. Lattice encoding of cyclic (f, σ, δ)-codes over OK /pOK , II
We continue to assume the setup from Section 4.1.
5.1. A second generalization of Construction A. Let I be a principal left
ideal of Λ generated by a monic polynomial g(t), such that p ⊂ I ∩ S0 . Then
I/pΛ is a non-zero principal left ideal of Λ/pΛ and Ψ(I/pΛ) is a principal left ideal
of Sf generated by the monic polynomial Ψ(g + pΛ) = g. That means Ψ(I/pΛ)
corresponds to an (f , σ, δ)-code C over OK /pOK .

16

S. PUMPLÜN

In particular, if we choose δ = 0 and f (t) such that f (t) = tm − c ∈ D/pD with c
non-zero, then Ψ(I/pΛ) is a σ-constacyclic code over OK /pOK .
If f is irreducible and D/pD is a division algebra, then the algebra Sf is simple.
Then any non-zero code C must have length m and dimension m (and correspond
to the whole algebra), whereas whenever f is reducible, C respectively Ψ(I/pΛ)
corresponds to a right divisor g of f and has dimension m − deg(g). Let
ρ : Λ −→ Λ/pΛ −→ Ψ(Λ/pΛ)
be the canonical projection Λ −→ Λ/pΛ composed with Ψ. We know that OK is a
free Z-module of rank n[F : Q]. Therefore
L = ρ−1 (C) = I
is a Z-module of dimension N = n2 m[F : Q]. The embedding of this lattice into
RN is canonically determined by considering Sf ⊗Q R. Again all works exactly as
explained in [21, Section 3.3] (since associativity is not relevant for the argument).
The construction of L can again be seen as a second (nonassociative) variation of
the non-commutative Construction A in [19].
In this way we can construct a lattice L in RN from the linear (f , σ, δ)-code C
over a finite ring.
Note that even if R = D[t; σ, δ] is isomorphic to D[t; σ] or D[t; δ], like when σ or δ
are inner, we conjecture that the codes/lattices we obtain from using different ways
to write R can be substantially different in performance, similarly as the examples
obtained in [9], where some of the codes obtained by working with the general skew
polynomial ring Fq [t; σ, δ] have a better distance bound than the ones obtained with
δ = 0.
5.2. Space-time block codes. We now apply the above considerations to spacetime block coding (cf. 1.4).
Example 14. Let A = (K/F, σ, c), c ∈ OK non-zero, be a nonassociative cyclic
division algebra over F of degree m with c ∈ OK . Take the natural order Λ =
OK [t; σ]/OK [t; σ]f , and let a = a0 + a1 t + · · · + am−1 tm−1 , b = b0 + b1 t + · · · +
bm−1 tm−1 ∈ Λ. If we identify a with the vector (a0 , a1 , . . . , am−1 ), we can express
Ra ∈ EndOK (Λ) as an m × m-matrix M (a) with entries in OK :


(1)




M (a) = 




a0
a1
a2
..
.
am−1

cσ(am−1 ) cσ 2 (am−2 )
σ(a0 )
cσ 2 (am−1 )
σ(a1 )
σ 2 (a0 )
..
..
.
.
2
σ(am−2 ) σ (am−3 )

···
···
···
..
.

cσ m−1 (a1 )
cσ m−1 (a2 )
cσ m−1 (a3 )
..
.

···

σ m−1 (a0 )

T




 .




HOW TO OBTAIN LATTICES FROM (f, σ, δ)-CODES

17

If we identify b with (b0 , b1 , . . . , bm−1 ), the right multiplication with a in Λ is given by
the matrix multiplication b · a = bM (a). The family of matrices {M (a) | 0 6= a ∈ A}
is a fully diverse linear space-time block code C.
Let p ⊂ OF be a maximal ideal. Then ρ : Λ −→ Λ/pΛ −→ Ψ(Λ/pΛ) =
((OK /pOK )/Fpf , σ, c). Hence L = ρ−1 (C) = I is a fully diverse space-time block
code over OK which is a Z-lattice whose embedding into Rm is canonically determined by A ⊗Q R.
Nonassociative cyclic division algebras as above can be employed to obtain fully
diverse multiple-input double-output codes [58]. The algebras A = (D, σ −1 , d) we
consider next are used for the systematic space-time block code constructions of the
fast-decodable iterated codes in [39], [52], [53], [57].
Example 15. Let A = (D, σ, d) be a division algebra of degree n and d ∈ OL or
d ∈ OF .
For x = x0 + x1 t + x2 t2 + · · · + xm−1 tm−1 , y = y0 + y1 t + y2 t2 + · · · + ym−1 tm−1 ∈
Λ, xi , yi ∈ D, represent x as (x0 , x1 , . . . , xm−1 ) and y as (y0 , y1 , . . . , ym−1 ). Then
Rx ∈ EndD (Λ) is given by the m × m-matrix

T
x0
dσ(xm−1 ) dσ 2 (xm−2 ) · · · dσ m−1 (x1 )
 x
σ(x0 )
dσ 2 (xm−1 ) · · · dσ m−1 (x2 ) 


1

2 (x )
m−1 (x ) 

x
σ(x
)
σ
·
·
·
dσ
2
1
0
3 
M (x) = 

..
..
..
 ..

..
.
 .

.
.
.
2
m−1
xm−1 σ(xm−2 ) σ (xm−3 ) · · · σ
(x0 )
with entries in D. We can write the multiplication in Λ as y · x = yM (x). Now
substitute the right regular representation γ(d) in D for d in M (x) and the right
regular representation γ(xi ) in D for each entry xi in M (x). This way we obtain a
block matrix
T

γ(x0 )
γ(d)σ(γ(xm−1 )) · · · γ(d)σ m−1 (γ(x1 ))


σ(γ(x0 ))
· · · γ(d)σ m−1 (γ(x2 )) 
 γ(x1 )


γ(M (x)) := 
..
..
..
..

.
.
.
.


γ(xm−1 )
σ(γ(xm−2 ))
···
σ m−1 (γ(x0 ))
where σ(γ(xi )) means we apply σ to each entry of the n×-matrix γ(xi ). Products
are the usual matrix products. This is an mn × mn matrix with entries in OK . It
represents right multiplication in Λ. Writing elements in Λ = OK ⊕ OK e ⊕ · · · ⊕
OK en−1 tm−1 as row vectors of length mn with entries in OK , we obtain y · x =
y γ(M (x)).
The family of matrices {γ(M (x))} is a fully diverse linear space-time block code
C. In particular, if d ∈ OF , then det(γ(M (x))) ∈ OF ([39], [52, Remark 5]) and if

18

S. PUMPLÜN

d ∈ OL , then
dσ(γ(xn−1 )) dσ 2 (γ(xn−2 ))

σ(γ(x0 ))
dσ 2 (γ(xn−1 ))


σ(γ(x1 ))
σ 2 (γ(x0 ))
γ(M (x)) = 

.
..

..

.
2
γ(xn−1 ) σ(γ(xn−2 )) σ (γ(xn−3 ))


γ(x0 )
γ(x1 )
γ(x2 )
..
.

···
···
···
..
.
···

T
dσ m−1 (γ(x1 ))
dσ m−1 (γ(x2 ))


m−1
dσ
(γ(x3 ))

..


.
m−1
σ
(γ(x0 ))

and det(γ(M (x))) ∈ L ∩ OK = OL ([57], [52, Lemma 19]).
Let p ⊂ OF0 be a prime ideal such that pOF is maximal. Then
ρ : Λ −→ Λ/pΛ −→ Ψ(Λ/pΛ) = (D, σ, d).
Here, L = ρ−1 (C) = I induces a fully diverse STBC over OK which is a Z-lattice
whose embedding into RN , N = mn2 , is canonically determined by A ⊗Q R.
Remark 16. The explanations in [21, Section 5.2, 5.3] hold analogously for our
generalization of Construction A in Section 3.1 and the examples here, and show
the potential of the construction for coset coding used in space-time block coding, in
particular for wiretap space-time block coding, but also for linear codes over finite
rings. Moreover, the matrix generating a cyclic (f, σ, δ)-code C ⊂ S m represents the
right multiplication Rg in Sf and is a control matrix of C [54].
6. Conclusion
We presented a method how to construct a lattice from a suitable (f, σ, δ)-code
defined over a finite ring which can be seen as a generalization of the classical
construction A. This can be summarized as follows: Let D be a cyclic division
algebra over F which is already defined over OF , or a Galois field extension and
f defined over its ring of integers. Take the additional assumptions on σ and δ as
given in the corresponding previous sections.
• Choose some monic skew polynomial f ∈ D[t; σ, δ] (resp., f ∈ OK [t; σ, δ] in
the field case) which is irreducible in D[t; σ, δ].
• Take a natural order Λ of Sf .
• Choose a prime ideal p in S0 . This yields the finite ring OK /pOK you
consider the code C to be defined over. f must be reducible in (D/pD)[t; σ, δ].
• Choose a principal left ideal I of Λ generated by a monic polynomial, such
that p ⊂ I ∩ S0 .
• Ψ(I/pΛ) corresponds to an (f , σ, δ)-code C over OK /pOK , and L = ρ−1 (C) =
I is a Z-lattice whose embedding into RN is canonically determined by Sf ⊗Q
R.
If we want to apply this construction to space time block coding instead, we
substitute the last step with:

HOW TO OBTAIN LATTICES FROM (f, σ, δ)-CODES

19

• Take the matrix representing right multiplication in Λ and let C be the
associated space-time block code. Then ρ−1 (C) = I is a fully diverse spacetime block code which is a Z-lattice.
If desired, this method can be extended to work for any Noetherian integral
domain and central simple algebra over its quotient field. It can be applied for coset
coding and wiretap coding analogously as described in [21, Sections 5.2, 5.3].
It would be interesting to investigate which properties of C carry over to the lattice
STBC L and find examples of well performing coset codes.

References
[1] A. S. Amitsur, Differential polynomials and division algebras. Annals of Mathematics, Vol. 59
(2) (1954) 245-278.
[2] A. S. Amitsur, Non-commutative cyclic fields. Duke Math. J. 21 (1954), 87105.
[3] J. Apel, Gröbnerbasen in Nichtkommutativen Algebren und ihre Anwendung. Dissertation,
Leipzig (1988)
[4] M. Artin, Noncommutative rings. http://math.mit.edu/∼etingof/artinnotes.pdf, last accessed
24.4.2017
[5] J. Bergen, M. Giesbrecht, P. N. Shivakumar, Y. Zhang, Factorizations for difference operators.
Adv. Difference Equ. 2015, 2015:57, 6 pp.
[6] M. Bhaintwal, Skew quasi-cyclic codes over Galois rings. Des. Codes Cryptogr. 62 (1) (2012),
85-101.
[7] A. Batoul, K. Guenda, T. A. Gulliver, On self-dual cyclic codes over finite chain rings. Des.
Codes Cryptogr. 70 (3) (2014), 347-358.
[8] D. Boucher, P. Solè, F. Ulmer, Skew-constacyclic codes over Galois rings. Adv. Math. Comm. 2
(3) (2008), 273-292.
[9] D. Boucher, F. Ulmer, Linear codes using skew polynomials with automorphisms and derivations,
Des. Codes Cryptogr. 70 (3) (2014), 405-431.
[10] D. Boucher, F. Ulmer, Self-dual skew codes and factorization of skew polynomials, J. Symbolic
Comput. 60 (2014), 47-61.
[11] D. Boucher, F. Ulmer, Coding with skew polynomial rings, J. Symbolic Comput. 44 (12) (2009),
1644-1656.
[12] D. Boucher, F. Ulmer, Codes as modules over skew polynomial rings. Cryptography and coding,
Lecture Notes in Comput. Sci., 5921, Springer, Berlin, 2009, 38-55.
[13] D. Boucher, W. Geiselmann, F. Ulmer, Skew-cyclic codes. AAECC 18 (2007), 370-389.
[14] M. Boulagouaz, A. Leroy, (σ, δ)-codes. Adv. Math. Comm. 7 (4) (2013), 463-474.
[15] J. Bueso, J. Gomez-Torrecillas, and A. Verschoren. “Methods in Non-Commutative Algebra.”
(2003). Kluwer Academic Press.
[16] Y. Cao, On constacyclic codes over finite chain rings. Finite Fields Appl. 24 (2013), 124-135
[17] M. Ceria, T. Mora, BuchbergerZacharias Theory of multivariate Ore extensions. Journal of
Pure and Applied Algebra 221 (12) (2017), 2974-3026.
[18] P. M. Cohn, “Skew fields.” Theory of general division rings. Encyclopedia of Mathematics and
its Applications, 57. Cambridge University Press, Cambridge, 1995.
[19] J. H. Conway, N. J. Sloane, Sphere packings, Lattices and groups. Springer Verlag 1999.

20

S. PUMPLÜN

[20] J. Ducoat, F. Oggier, Lattice encoding of cyclic codes from skew polynomial rings. Proc. of the
4th International Castle Meeting on Coding Theory and Applications, Palmela, 2014.
[21] J. Ducoat, F. Oggier, On skew polynomial codes and lattices from quotients of cyclic division
algebras. Adv. Math. Comm. 10 (1) 2016, 79-94.
[22] N. Fogarty, H. Gluesing-Luerssen, A Circulant Approach to Skew-Constacyclic Codes. Finite
Fields Appl. 35 (2015), 92114.
[23] J. Gómez-Torrecillas, F. J. Lobillo, G. Navarro, A new perspective of cyclicity in convolutional
codes. IEEE Trans. Inform. Theory 62 (5) (2016), 2702-2706.
[24] J. Gómez-Torrecillas, F. J. Lobillo, G. Navarro, Convolutional codes with a matrix-algebra
word-ambient. Adv. Math. Commun. 10 (1) (2016), 29-43.
[25] J. Gómez-Torrecillas, F. J. Lobillo, G. Navarro, An isomorphism test for modules over a noncommutative PID. Applications to similarity of Ore polynomials. J. Symbolic Comput. 75 (2016),
149-170.
[26] J. Gómez-Torrecillas, F. J. Lobillo, G. Navarro, Separable automorphisms on matrix algebras
over finite field extensions: applications to ideal codes. ISSAC’15 - Proceedings of the 2015 ACM
International Symposium on Symbolic and Algebraic Computation, 189195, ACM, New York,
2015.
[27] J. Gómez-Torrecillas, F. J. Lobillo, G. Navarro, Information-bit error rate and false positives
in an MDS code. Adv. Math. Commun. 9 (2) (2015), 149-168.
[28] J. Gómez-Torrecillas, Basic module theory over non-commutative rings with computational aspects of operator algebras. With an appendix by V. Levandovskyy. Lecture Notes in Comput. Sci.
8372, Algebraic and algorithmic aspects of differential and integral operators, 23-82, Springer,
Heidelberg, 2014.
[29] J. Gao, Kong, Qiong 1-generator quasi-cyclic codes over Fpm + uFpm + · · · + us−1 Fpm . J.
Franklin Inst. 350 (10) (2013), 3260-3276.
[30] Hoechsmann, Klaus, Simple algebras and derivations. Trans. Amer. Math. Soc. 108 (1963),
1-12.
[31] N. Jacobson, “Finite-dimensional division algebras over fields,” Springer Verlag, BerlinHeidelberg-New York, 1996.
[32] J. S. Kauta, Maximal orders and valuation rings in nonassociative quaternion algebras. Proceedings of the 39th Symposium on Ring Theory and Representation Theory, 65-74, Symp. Ring
Theory Represent. Theory Organ. Comm., Yamaguchi, 2007.
[33] A. Kandri-Rody, W. Weispfenning, Non-commutative Gröbner bases in algebras of solvable
type. J. Symb. Comp. 9 (1990), 1-26
[34] H. Kredel, Solvable polynomial rings. Shaker Verlag 1993.
[35] H. J. Lee, W. C. Waterhouse, Maximal orders in nonassociative quaternion algebras. J. Algebra
146 (2) (1992), 441-453.
[36] V. Levandovskyy,
Non-commutative computer algebra for polynomial algebras:
Gröbner bases, applications and implementation. Dissertation, Kaiserslautern (2005),
http://kluedo.ub.uni-kl.de/volltexte/2005/1883/
[37] V. Levandovskyy, PBW bases, non-degeneracy conditions and applications. In: Buchweitz, R.O., Lenzing, H. (Eds.), Representation of Algebras and Related Topics. Proceedings of the ICRA
X Conference, 45 (2005), 229-246.
[38] X. Liu, H. Liu, LCD codes over finite chain rings. Finite Fields Appl. 34 (2015), 1-19.
[39] N. Markin, F. Oggier, Iterated space-time code constructions from cyclic algebras. IEEE Transactions on Information Theory, 59 (9), September 2013.

HOW TO OBTAIN LATTICES FROM (f, σ, δ)-CODES

21

[40] G. Nebe, A. Schaefer, A nilpotent non abelian group code. Algebra and Discrete Mathematics
18 (2014) 268-273.
[41] G. Nebe, W. Willems, On self-dual MRD codes. Adv. Math. of Comm. 10 (2016) 633-642.
[42] G. Nebe, D. Liebhold and A. Vazquez Castro, Network coding with flags. To appear in Designs,
Codes and Cryptography.
[43] F. Oggier, B. A. Sethuraman, Quotients of orders in cyclic algebras and space-time codes. Adv.
Math. Commun. 7 (4) (2013), 441-461.
[44] F. Oggier, J.-C. Belfiore, Enabling multiplication in lattice codes via Construction A. IEEE Int.
Workshop Inf. Theory 2013, 1-5.
[45] O. Ore, Formale Theorie der linearen Differentialgleichungen. (Zweiter Teil). (German) J.
Reine Angew. Math. 168 (1932), 233-252.
[46] O. Ore, Theory of noncommutative polynomials. Annals of Math. (1933), 480-508.
[47] M. Pesch, Gröbner Bases in skew polynomial rings. Shaker Verlag 1998.
[48] M. Pesch, Two-sided Gröbner bases in iterated Ore extensions. Progress in Computer Science
and Applied Logic (15) (1991), 225-243, Birkhäuser.
[49] J.-C. Petit, Sur certains quasi-corps généralisant un type d’anneau-quotient, Séminaire Dubriel.
Algèbre et théorie des nombres 20 (1966-67), 1-18.
[50] J.-C. Petit, Sur les quasi-corps distributifes à base momogène, C. R. Acad. Sc. Paris 266 (1968),
Série A, 402-404.
[51] S. Pumplün, A. Steele, Fast-decodable MIDO codes from nonassociative algebras. Int. J. of
Information and Coding Theory (IJICOT) 3 (1) 2015, 15-38.
[52] S. Pumplün, A. Steele, The nonassociative algebras used to build fast-decodable space-time block
codes. Adv. Math. Comm. 9 (4) (2015), 449-469.
[53] S. Pumplün, How to obtain division algebras used for fast decodable space-time block codes.
Adv. Math. Comm. 8 (3) (2014), 323 - 342.
[54] S. Pumplün, Finite nonassociative algebras obtained from skew polynomials and possible applications to (f, σ, δ)-codes. Adv. Math. Comm. 11 (3) (2017), 615-634. doi:10.3934/amc.2017046
[55] R. Sandler, Autotopism groups of some finite non-associative algebras. American Journal of
Mathematics 84 (1962), 239-264.
[56] R.D. Schafer, “An introduction to nonassociative algebras,” Dover Publ., Inc., New York, 1995.
[57] K. P. Srinath, B. S. Rajan, Fast-decodable MIDO codes with large coding gain. IEEE Transactions on Information Theory (2) 60 2014, 992-1007.
[58] A. Steele, S. Pumplün, F. Oggier, MIDO space-time codes from associative and non-associative
cyclic algebras. Information Theory Workshop (ITW) 2012 IEEE (2012), 192-196.
[59] A. Steele, Nonassociative cyclic algebras. Israel J. Math. 200 (1) (2014), 361-387.
[60] W. C. Waterhouse, Nonassociative quaternion algebras. Algebras, Groups and Geometries 4
(1987), 365-378.
[61] V. Weispfenning, Finite Gröbner bases in non-noetherian skew polynomial rings. Proc. ISSAC’92 (1992), 320-332, A.C.M.
[62] M. Wu, Free cyclic codes as invariant submodules over finite chain rings. Int. Math. Forum 8
(37-40) (2013), 1835-1838.
E-mail address: susanne.pumpluen@nottingham.ac.uk
School of Mathematical Sciences, University of Nottingham, University Park, Nottingham NG7 2RD, United Kingdom

