Dense Packings from Algebraic Number Fields and Codes1

arXiv:1506.00419v3 [math.NT] 11 Jan 2017

Shantian Cheng
Risk Management Institute,
National University of Singapore,
21 Heng Mui Keng Terrace,
119613 Singapore
rmicst@nus.edu.sg
Abstract
We introduce a new method from number fields and codes to construct dense packings
in the Euclidean spaces. Via the canonical Q-embedding of arbitrary number field K into
R[K:Q] , both the prime ideal p and its residue field κ can be embedded as discrete subsets
in R[K:Q] . Thus we can concatenate the embedding image of the Cartesian product of n
copies of p together with the image of a length n code over κ. This concatenation leads to
a packing in the Euclidean space Rn[K:Q] . Moreover, we extend the single concatenation to
multiple concatenation to obtain dense packings and asymptotically good packing families.
For instance, with the help of Magma, we construct a 256-dimensional packing denser than
the Barnes-Wall lattice BW256 .
Keywords: Dense packings, Number fields, Minkowski lattice, Codes
MSC: 11H31, 52C17, 11H71, 11H06, 11R04

1

Introduction

The classical problem of packing non-overlapping equal spheres densely in an n-dimensional Euclidean space
has attracted the interest of numerous mathematicians for centuries. Many methods and results from different
disciplines, such as discrete geometry, combinatorics, number theory and coding theory, etc. have been
involved in this problem, while some explicit fascinating dense constructions and asymptotically good packing
families have been found. For a detailed survey on the development in this field, the reader may refer to the
books of Cassels [6], Conway and Sloane [8], Zong [20]. If the centers of the packed spheres form a discrete
additive subgroup of Rn (lattice), we call it a lattice packing.
Sphere packings are continuous analogues of error-correcting codes in the Hamming space [9]. The basic
problem of error-correcting codes is to seek the maximum size of a code given length, alphabet size and
minimal Hamming distance, in other words, dense packing of points in Hamming space such that each pair
of distinct points is separated at least by the minimum Hamming distance. In the digital world, errorcorrecting codes are widely employed in information storage and transmission, for example, the blue ray
storage format and the communication between space stations and the Earth. Based on the similarities
between sphere packings and error-correcting codes, the results in sphere packings can potentially contribute
to the development of error-correcting codes.
Meanwhile, some constructions of dense lattice or non-lattice packings are inspired by constructions in
coding theory. For example, similar to concatenated codes, Leech and Sloane’s “Construction A” method
concatenated certain binary codes together with 2 · Zn to construct new lattice packings (see details in
[8, Chapter 5]). Bachoc [2] generalized the method to construct modular lattices using codes over finite
involution algebras. In Construction C [20, Chapter 5], the binary expansion of the coordinates in Zn is
considered. A point is a packing center if and only if its first ℓ coordinate arrays are codewords in certain ℓ
binary codes respectively.
√
Let ω = −1+2 −3 . Xing [19] further investigated the concatenating method. Instead of packings in Zn , he
√
n
considered the packings in OK
, where OK = Z [ω] denotes the ring of integers in the number field Q( −3).
That is, for a non-zero prime ideal P of OK , Pn can be embedded as a lattice L in R2n via the canonical
1 This

research began when the author was a PhD candidate at Nanyang Technological University.

1

√
Q-embedding of the special number field Q( −3) into R2 . Hence any subset P of Pn can be regarded
as a packing in R2n . Then he replaced the binary expansion in Construction C by the P-adic expansion,
and concatenated the lattice L with some special codes over OK /P. This method produces several dense
packings in low dimensions attaining the best-known densities and also obtains an unconditional bound on
the asymptotic density exponent λ > −1.265 (see [19]). Cheng [7] applied this concatenation to multiplicative
lattices and improved the asymptotic density of packing families derived from multiplicative lattices. One
natural
question is whether we can use arbitrary number field instead of the special quadratic number field
√
Q( −3) to generalize the constructing method.
In this paper, we extend Xing’s method to a general level, i.e. we employ the ideals in OK instead of
Z[ω], where OK denotes the ring of integers in an arbitrary number field K. Suppose the extension degree
of K over Q is m. Minkowski interpreted the elements in K as points in the m-dimensional Euclidean space
Rm . The interpretation is called “Minkowski Theory” in algebraic number theory (see [14, Section I.5] or
[18, Section 5.3]).
By Minkowski’s interpretation, we can use the canonical Q-embedding to construct lattices in Rm from
ideals in OK . In this way, for a non-zero prime ideal p of OK , the Cartesian product of n copies of p can be
embedded as a lattice in Rmn . Meanwhile, the codes defined over OK /p with length n can also be embedded
as finite subsets of Rmn . Then we can proceed with the concatenating method as Construction A on these
two kinds of subsets of Rmn to construct dense packings. For instance, we construct a 256-dimensional
packing with center density δ satisfying log2 δ > 208.09, which is larger than 192 of the Barnes-Wall lattice
BW256 (see the table of dense packings in [8, Table 1.3]). Furthermore, for different choices of number fields
and prime ideals, we also provide several asymptotically good packing families.
In section 2, we recall the formal definitions and necessary properties of sphere packing densities, algebraic
number fields and codes. They play important roles in the main results. In section 3, we describe our
generalized concatenating method in detail. Several examples of dense packings and asymptotically good
packing families for different choices of number fields and prime ideals are provided. The detailed numerical
results are provided in Tables 1 - 4. In Section 4, we conclude our main contribution.

2
2.1

Preliminaries
Sphere Packing

Let P be the set of centers of packed spheres and BN (R) be the set


q
v = (a1 , · · · , aN ) ∈ RN : kvk = a21 + · · · + a2N 6 R ,
where kvk denotes the Euclidean length of vector v. As a sphere packing construction is determined by the
arrangement of the sphere centers, we just use P to denote the corresponding packing.
For a packing P, the radius of the equal packed spheres is r = dE (P)/2, where dE (P) is the minimum
Euclidean distance between two distinct points in P. Then the density ∆(P) of packing P is defined as
∆(P) = lim sup
R→∞

|P ∩ BN (R)| · rN · VN
,
vol(BN (R + r))

where VN is the volume of the unit sphere in RN , that is


π N/2


,
if N is even;
VN = (N/2)!
N (N −1)/2

((N − 1) /2)!

2 π
, if N is odd.
N!
2

The sphere packing problem is to construct packings obtaining large density ∆(P). Moreover, the center
density δ(P) and density exponent λ(P) are defined respectively as
δ(P) =

∆(P)
,
VN

λ(P) =

1
log2 ∆(P).
N

If P = L forms a lattice, the density of lattice packing L can be simplified as
∆(L) =

(dE (L)/2)N VN
,
det(L)

where det(L) is the determinant of L. Note that from Minkowski’s Convex Body Theorem (see [13, Theorem
1.4] or [15, Theorem 4]), for any rank N lattice L, the minimum Euclidean distance of L satisfies
√
(1)
dE (L) 6 N det(L)1/N .
 (N )
When we explore the asymptotic behavior of a packing family F = P
as the dimension N of packing
P (N ) tends to ∞, we consider the asymptotic density exponent of the family


1
(2)
λ(F ) = lim sup log2 ∆ P (N ) .
N →∞ N
Note that by Stirling formula, as N → ∞, we have
log2 VN = −

N
1
N
log2
− log2 (N π) − ǫ,
2
2πe 2

(3)

where 0 < ǫ < (log2 e)/(6N ).
For the asymptotic aspect, Minkowski gave a nonconstructive bound that asserts that there exists some
packing family F such that the asymptotic density exponent λ(F ) satisfies λ(F ) > −1 (see [6, p.184]). It
is of interest to construct families with λ(F ) > −∞ explicitly (such families are called asymptotically good).
Known constructive bounds for families with polynomial or exponential construction complexity in terms of
dimension N are listed in the book of Litsyn and Tsfasman [18, p.628]. Rush [17] proved that Minkowski’s
bound on asymptotic density λ > −1 can be attained by lattice packings constructed from codes. More
recently, Gaborit and Zémor [10] improved the density by a linear factor to the quantity of the form cn2−n
for constant c.

2.2

Algebraic Number Fields

Let K be an algebraic number field of degree m over Q, and let OK be its ring of integers. Suppose K has
s real embeddings
ρ1 , · · · , ρs : K ֒→ R,
and t pairs of complex conjugate embeddings
σ1 , σ 1 , · · · , σt , σ t : K ֒→ C.
Thus m = s + 2t. We consider the canonical embedding τ : K ֒→ Rs+2t , that is, for any α ∈ K, τ (α) is the
following vector


√
√
√
√
ρ1 (α), · · · , ρs (α), 2ℜσ1 (α), 2ℑσ1 (α), · · · , 2ℜσt (α), 2ℑσt (α) ,
(4)

where ℜ denotes the real part and ℑ denotes the imaginary part of a complex number. τ can be directly
extended to K n ֒→ Rmn , which is also denoted by τ in this paper without causing any confusion.
Note that in the software Magma V2.21-4 [4, 5], the embedding τ defined above is called the Minkowski
map and it is employed to compute the “minimum norm” (square of minimum Euclidean distance) of a
3

Minkowski lattice. In Subsection 3.4, we will use the software to compute the density of some explicit
examples from our construction.
Set Tr = TraceK/Q and N = NormK/Q . By the Minkowski Theory [14, Section I.5], the embedding
τ maps the non-zero ideals of OK to some special lattices in Rm . The following lemma characterizes the
determinant of such lattices.
Lemma 2.1 ([14, Section I.5]). For any non-zero ideal I ⊆ OK , LI := τ (I) is a lattice of rank m. The
determinant of LI is
p
det LI = N (I) |DK |,
where DK is the discriminant of K and N (I) = [OK : I] is the absolute norm of I.

Generally it remains hard to compute the minimum Euclidean distance of lattices. However, we can
estimate a lower bound on the Euclidean length of non-zero points in the lattice LI . The proof is sketched
here and a similar discussion on general ideal lattices can be found in [3]. Note that in [3], the distance
between two points is defined using some special quadratic forms, while in this paper, we only focus on the
standard Euclidean distance, which refers to the original meaning of packing in the Euclidean space and
brings convenience in computation (Magma uses standard Euclidean distance as built-in measure).
Lemma 2.2. Let I ⊆ OK be a non-zero ideal. For any 0 6= α ∈ I, the Euclidean length of the vector
τ (α) ∈ LI satisfies
kτ (α)k >

In other words, dE (LI ) >

√

√
m · N (I)1/m .

m · |N(α)|

1/m

>

√
m · N (I)1/m .

Proof. The Euclidean length of the vector τ (α) satisfies
kτ (α)k

2

=

s
X

ρi (α)2 + 2


(s + 2t) 

s
Y

i=1

=

σj (α)σ̄j (α)

j=1

i=1

>

t
X

ρi (α)2 ·

t
Y

j=1

σj (α)σ j (α) ·

h
i1/m
2
m (N(α))
> m · N (I)2/m .

t
Y

j=1

1
 s+2t

σj (α)σ j (α)

The last > becomes an equality if and only if the ideal I is a principal ideal generated by α.
The following lemma is a basic fact in algebraic number theory (see [14, Section I.2]).
Lemma 2.3. For any non-zero element β ∈ OK , we have |N(β)| > 1.
of non-zero elements in LOK satisfies dE (LOK ) >
√ From the above lemmas, the minimum Euclidean length
√
m. Indeed, as the vector τ (1) has Euclidean length m, we have
√
(5)
dE (LOK ) = m.

4

2.3

Coding Theory

We recall some notations and results in coding theory.
For a q-ary code C, let n(C), M (C) and dH (C) denote the length, the size, and the minimum Hamming
distance of C, respectively. Such a code is usually referred to as an (n(C), M (C), dH (C))-code. Moreover,
the relative minimum distance ̺(C) and the rate R(C) are defined respectively as

̺(C) =

dH (C)
,
n(C)

R(C) =

logq M (C)
.
n(C)

In particular, if a code C forms a linear space over Fq , then the code C is called an [n(C), k(C), dH (C)]linear code over Fq , where k(C) := logq M (C) is called the dimension of C. In this case, the rate R(C) =
k(C)
.
n(C)
Let Uq be the set of the ordered pair (̺, R) ∈ R2 , for which there exists a family {Ci }∞
i=0 of q-ary codes
such that n(Ci ) increasingly goes to ∞ as i tends to ∞ and
̺ = lim ̺(Ci ),
i→∞

and R = lim R(Ci ).
i→∞

Here is a result on Uq :
Proposition 2.4 ([18, Section 1.3.1] or [19, Proposition 3.1]). There exists a continuous function Rq (̺),
̺ ∈ [0, 1], such that

Uq = (̺, R) ∈ R2 : 0 6 R 6 Rq (̺), 0 6 ̺ 6 1 .
Moreover, Rq (0) = 1, Rq (̺) = 0 for ̺ ∈ [(q − 1)/q, 1], and Rq (̺) decreases on the interval [0, (q − 1)/q].
For 0 < ̺ < 1, the q-ary entropy function is given as
Hq (̺) = ̺ logq (q − 1) − ̺ logq ̺ − (1 − ̺) logq (1 − ̺).
The asymptotic Gilbert-Varshamov (GV) bound indicates that
Rq (̺) > RGV (q, ̺) := 1 − Hq (̺),

for all ̺ ∈



q−1
0,
q



.

(6)

Moreover, for any given rate R, there exists a family of linear codes which meets the GV bound (see [12,
Section 17.7]).

3

Main Results

In this section, we introduce our new construction of dense sphere packings. In particular, several explicit
constructions and asymptotically good packing families are provided at the end of this section. Our idea is
to apply special concatenating methods on LI defined in Lemma 2.1.
Let [K : Q] = m and let p be a prime ideal of OK . Assume that the residue field Fp = OK /p of p is
isomorphic to the finite field Fq . Let τ be the canonical embedding defined in Eq. (4).
For i ∈ N, let Lnpi denote the Cartesian product of n identical copies of lattice Lpi = τ (pi ). Then Lnpi is
a lattice of rank mn by Lemma 2.1. Moreover, the determinant satisfies
n
det Lnpi = det Lpi ,
which is straightforward from the definition of lattice determinant. In addition, by the definition of Lnpi , the
minimum Euclidean distance satisfies
dE (Lnpi ) = dE (Lpi ).
5

For simplicity, in this section we write Li = Lpi for short.
As OK is a Dedekind domain (see [14, Section I.3] or [1, Chapter 9]), let κ = OK /p, then we have
i
i+1
dim
= 1 for o
all i ∈ N. We know κ ∼
= Fq . Thus for i ∈ N, we can choose the sets Si :=
n κ p /p
(i)

(i)

(i)

α1 = 0, α2 , · · · , αq

⊆ pi such that
(i)

i+1
α1 mod pi+1 , · · · , α(i)
q mod p

(7)

represent the q distinct elements in pi /pi+1 .

3.1

Concatenation with One Code

We fix one index i0 ∈ N>1 in the discussion here and generalize the result to a family of indices in the next
subsection. Let P be a subset of Lni0 , which can be regarded as a packing in Rmn .
Given a q-ary code C with length n, in order to perform our concatenation, we take the code alphabet set
n
of C to be Si0 −1 ⊆ pi0 −1 (see Eq. (7)). In this way, C can be regarded as a finite subset of OK
. The advantage
of using Si0 −1 as the alphabet set is that it can help us bound the packing radius of our construction. The
details are included in the proof of Proposition 3.2.
n
We define τ (c) for each codeword c = (c1 , · · · , cn ) ∈ C ⊆ OK
as
τ (c) := (τ (c1 ), · · · , τ (cn )) ∈ Rmn ,
and take τ (C) := {τ (c) : c ∈ C}. We consider the concatenation
τ (C) + P := {a + p ∈ Rmn : a ∈ τ (C), p ∈ P} ,
which corresponds to a packing in Rmn . We will analyze the density of such a packing in this subsection.
The following lemma characterizes the minimum Euclidean distance of the concatenation τ (C)+P, which
will play an important role in later discussions.
Lemma 3.1. Let p be a non-zero prime ideal in OK with absolute norm N (p) = q (i.e., the residue field
Fp ∼
= Fq ). For i0 ∈ N>1 , let
(i) P be a subset of Lni0 ,
(ii) C be a q-ary (n, M, dC )-code over the alphabet set Si0 −1 . In addition, C contains the zero codeword.
Then the minimum Euclidean distance of the packing τ (C) + P satisfies
n
o
p
dE (τ (C) + P) > min dE (Li0 −1 ) dC , dE (P) .
√
In particular, if dE (Li0 −1 ) dC > dE (P), we have exactly

dE (τ (C) + P) = dE (P).
Proof. Let τ (c) + p be a non-zero element in τ (C) + P, where c ∈ C and p ∈ P. If c = 0, then
kτ (c) + pk = kpk > dE (P).
If c 6= 0, without loss of generality, we assume c = (c1 , · · · , ce , 0), where e is the Hamming weight of c
and ci 6= 0 for 1 6 i 6 e. As P ⊆ Lni0 , we can further assume p = (τ (ρ1 ), · · · , τ (ρn )), where ρj ∈ pi0 for
1 6 j 6 n. Thus
τ (c) + p = (τ (c1 + ρ1 ), · · · , τ (ce + ρe ), τ (ρe+1 ), · · · , τ (ρn )) .
6

As c1 , · · · , ce are non-zero elements in Si0 −1 , i.e., for 1 6 i 6 e, ci ∈ pi0 −1 \ pi0 , we have that ci + ρi are
non-zero elements in pi0 −1 for 1 6 i 6 e. Thus
2

kτ (c) + pk >

e
X
i=1

2

kτ (ci + ρi )k > e · d2E (Li0 −1 ) > dC · d2E (Li0 −1 ).

In summary, the minimum Euclidean distance of the packing τ (C) + P satisfies
n
o
p
dE (τ (C) + P) > min dE (Li0 −1 ) dC , dE (P) .

(8)

√
In particular, if dE (Li0 −1 ) dC > dE (P), then from Eq. (8) above, we have the minimum distance
dE (τ (C) + P) > dE (P). Meanwhile, as C contains the zero codeword, P is a subset of τ (C) + P, thus
dE (P) > dE (τ (C) + P). Finally we have exactly
dE (τ (C) + P) = dE (P).
√
The following proposition generalizes Proposition 2.3 of [19], where only the special case K = Q( −3)
is discussed.
Proposition 3.2. Under the same assumption on P and C as in Lemma 3.1,
√
(i) if dE (Li0 −1 ) dC > dE (P), then the density of τ (C) + P as a packing in Rmn is at least M · ∆ (P),
where ∆ (P) is the density of the packing P as a packing in Rmn , and M is the size of the code C;
(ii) if P is a lattice and C satisfies that for any u, v ∈ C, the sum τ (u) + τ (v) is equal to τ (w) + p for some
w ∈ C and p ∈ P, then τ (C) + P is also a lattice.
Proof. (i) We denote the volume of the unit sphere in RN by VN and the sphere of radius b by BN (b). Let
s = max{kτ (c)k : c ∈ C}. For any c ∈ C and p ∈ P ∩ Bmn (b), we have τ (c) + p ∈ (τ (c) + P) ∩ Bmn (b + s).
This implies that
|(τ (c) + P) ∩ Bmn (b + s)| > |P ∩ Bmn (b)| .
Moreover, as the elements in the alphabet set Si0 −1 of C represent the q distinct elements in pi0 −1 /pi0 and
P ⊆ Lni0 , we have if ci 6= cj then
(τ (ci ) + P) ∩ (τ (cj ) + P) = ∅.
We write d = dE (τ (C) + P) for short and from Lemma 3.1 we have d = dE (P). Finally we obtain

=
=
>
=

∆ (τ (C) + P)
|(τ (C) + P) ∩ Bmn (b + s)| (d/2)mn Vmn
lim sup
vol(Bmn (b + s + d/2)
b→∞

P
mn
Vmn
c∈C |(τ (c) + P) ∩ Bmn (b + s)| (d/2)
lim sup
vol(B
(b
+
s
+
d/2)
mn
b→∞
mn
|C| · |P ∩ Bmn (b)| (dE (P)/2) Vmn
lim sup
vol (Bmn (b + s + d/2))
b→∞
|C| · ∆ (P) = M · ∆(P).

(ii) By the definition of a lattice, this part is true.
7

3.2

Concatenation with a Family of Codes

For a family of q-ary codes {Ci }ℓ−1
i=0 , where ℓ ∈ N>1 , we can take the code alphabet set of Ci to be Si (see
Eq. (7)). Note that the choice of the alphabet set of the codes is only used in the proof. For the computation,
we only care about the length, size and minimum Hamming distance of the codes.
Similar to Subsection 3.1, for any subset P of Lnℓ , and a family of q-ary codes C = {Ci }ℓ−1
i=0 with length
n, we consider the concatenation
)
( ℓ−1
ℓ−1
X
X
mn
ai + p ∈ R
: ai ∈ τ (Ci ), p ∈ P .
(9)
τ (Ci ) + P =
τ (C) + P :=
i=0

i=0

Note that for each 0 6 i 6 ℓ − 1, as the code alphabet set of Ci is Si , the set τ (Ci ) is a finite subset of Lni .
Meanwhile P is a subset of Lnℓ . As for any 0 6 i 6 ℓ, the lattice Lni is a sublattice of LnOK , the concatenation
Eq. (9) makes sense within LnOK .
Proposition 3.3. Let p be a non-zero prime ideal in OK with absolute norm N (p) = q. For ℓ ∈ N>1 , let
(i) P be a subset of Lnℓ ,
ℓ−1

(ii) C = {Ci }i=0
a family
of q-ary codes, where Ci is an (n, Mi , dCi )-code, the alphabet set of Ci is Si ,
 be

d2E (P)
and dCi > 2
. In addition, for each 0 6 i 6 ℓ − 1, Ci contains the zero codeword.
dE (Li )
Qℓ−1
Then the density of τ (C) + P as a packing in Rmn is at least ∆(P) · i=0 Mi .

Proof. Let Pℓ := P ⊆ Lnℓ . For i from ℓ − 1 to 0, we can recursively define
Pi := τ (Ci ) + Pi+1 ⊆ Lni .
Note that P0 = τ (C) + P.
We claim that for 0 6 i 6 ℓ − 1,
dE (Pi ) = dE (Pi+1 )

and ∆(Pi ) > Mi · ∆(Pi+1 ).

(10)

We use induction on k = ℓ − i to prove the claim. When k = 1, i = ℓ − 1, as the minimum Hamming
distance of Cℓ−1 satisfies dCℓ−1 d2E (Lℓ−1 ) > d2E (P) = d2E (Pℓ ), by Lemma 3.1 and Proposition 3.2 (i), we have
dE (Pℓ−1 ) = dE (τ (Cℓ−1 ) + Pℓ ) = dE (Pℓ )

and ∆(Pℓ−1 ) > Mℓ−1 · ∆(Pℓ ).

Suppose for all k in the range 1 6 k < k0 + 1 6 ℓ, the statement Eq. (10) is true, i.e., i = ℓ − k,
dE (Pℓ−k ) = dE (Pℓ−k+1 )

and ∆(Pℓ−k ) > Mℓ−k · ∆(Pℓ−k+1 )

is true. By induction, we need to prove
dE (Pℓ−k0 −1 ) = dE (Pℓ−k0 )

and ∆(Pℓ−k0 −1 ) > Mℓ−k0 −1 · ∆(Pℓ−k0 ).

From Eq. (11), we have
dE (Pℓ−k0 ) = dE (Pℓ−k0 +1 ) = · · · = dE (Pℓ−1 ) = dE (Pℓ ) = dE (P).
Besides, the minimum Hamming distance of Cℓ−k0 −1 satisfies
dCℓ−k0 −1 d2E (Lℓ−k0 −1 ) > d2E (P) = d2E (Pℓ−k0 ).
8

(11)

Then by Lemma 3.1 and Proposition 3.2 (i), as Pℓ−k0 −1 = τ (Cℓ−k0 −1 ) + Pℓ−k0 , we get
dE (Pℓ−k0 −1 ) = dE (Pℓ−k0 )

and ∆(Pℓ−k0 −1 ) > Mℓ−k0 −1 · ∆(Pℓ−k0 ).

Thus we have proved the claim Eq. (10). From the claim, we easily obtain ∆(P0 ) > ∆(P) ·

Qℓ−1
i=0

Mi .

Remark 3.4. From the above proposition, given a dense packing P from the canonical embedding Eq. (4)
on some prime ideal in a certain algebraic number field, we can concatenate several codes satisfying the
requirements in Proposition 3.3 to P to obtain some new denser packings. The density increases by a ratio
larger than the product of the sizes of these codes.
Note that generally it is hard to determine the minimum Euclidean distance of P ⊆ Lnℓ ⊆ Rmn . However,
we can consider special choices of P with some algebraic structure. The following corollary, which plays a
crucial role in Subsection 3.4 for Examples 3.8 - 3.11, considers the case P = Lnℓ . The advantage is that
for all i ∈ N, we have dE (Lni ) = dE (Li ). Instead of searching for the minimum Euclidean distance of Lni in
Rmn , we can search for the minimum Euclidean distance of Li in Rm . In our examples, m is small such that
Magma can be used to compute the minimum Euclidean distance.
Corollary 3.5. Let p be a non-zero prime ideal in OK with absolute norm N (p) = q. For ℓ ∈ N>1 , let
ℓ−1
C = {Ci }i=0 bea family of q-ary codes, where Ci is an (n, Mi , dCi )-code, the alphabet set of Ci is Si , and
d2 (Lℓ )
dCi > E
. In addition, for each 0 6 i 6 ℓ − 1, the code Ci contains the zero codeword.
d2E (Li )
Then the density of τ (C) + Lnℓ as a packing in Rmn satisfies
∆(τ (C) + Lnℓ ) >

ℓ−1
mn
(dE (Lℓ )/2) Vmn Y
 p
n
Mi ,
·
q ℓ |DK |
i=0

where DK is the discriminant of K and Vmn is the volume of the unit sphere in Rmn . Moreover, the center
density δ = δ(τ (C) + Lnℓ ) satisfies
ℓ−1

X
n
log2 Mi .
log2 δ > mn log2 dE (Lℓ ) − mn − nℓ log2 q − log2 |DK | +
2
i=0
In particular, if for all 0 6 i 6 ℓ − 1, the code Ci is a linear code of dimension ki = logq Mi , then
ℓ−1

log2 δ > mn log2 dE (Lℓ ) − mn − nℓ log2 q −

X
n
ki .
log2 |DK | + log2 q ·
2
i=0

Proof. Note that N (pℓ ) = q ℓ and then by Lemma 2.1

 p
n
n
det Lnℓ = (det Lℓ ) = q ℓ |DK | .

Remark 3.6. For concatenation with finite codes, we care more about the dimension of the packing as we
need to compare the new construction with the known good packings in the Euclidean space with the same
dimension. Hence we fix the length n of the codes first. As for 
0 6 i 6 ℓ− 1, the lattice Li is a sublattice of


d2 (Lℓ )
> q 2ℓ/m by Eq. (5) and Lemma
L0 , we have dE (Li ) > dE (L0 ). Thus the length n satisfies n > 2E
jm
k dE (L0 )
2.2. Therefore, we can concatenate at most ℓ =
logq n codes to Lnℓ . This bound will be used in the
2
computation of Subsection 3.4.
9

3.3

Asymptotic Properties

In this subsection, we show that our construction will lead to asymptotically good packing families, which
means we can obtain several constructive bounds on the asymptotic density exponent Eq. (2).
We will employ families of linear codes that meet the GV bound. As there exist only exponential time
algorithms or randomized polynomial algorithms to construct such families (see [12, Section 17.7]), our
corresponding asymptotic density exponent bounds are exponential constructive bounds.
From Eq. (1) and Lemma 2.2, for 0 6 i 6 ℓ − 1, we know
d2E (Lℓ )
6 q 2(ℓ−i)/m |DK |1/m .
d2E (Li )

(12)

Different from the finite concatenation in Subsection 3.2, for asymptotic results, we first fix ℓ and construct
the packing for each ℓ ∈ N>1 . The length nℓ of the codes is set depending
ℓ.
 2 on 
 2ℓ/m

dE (Lℓ )
1/m
We uniformly set nℓ = q
|DK |
. Then by Eq. (12), nℓ >
for all 0 6 i 6 ℓ − 1. Based
d2E (Li )
on the GV bound Eq. (6), for 0 6 i 6 ℓ − 1, we can choose q-ary

 2

dE (Lℓ )
(nℓ )
nℓ , ki , 2
dE (Li )
(nℓ )

linear code Ci

such that the rate is
(n )

ki ℓ
(n )
(n )
> RGV (q, ̺i ℓ ) = 1 − Hq (̺i ℓ ),
nℓ
where the relative minimum distance satisfies

(nℓ )

̺i

=




d2E (Lℓ )
d2E (Li )
.
nℓ

oℓ−1
n
(n )
Let C (nℓ ) := Ci ℓ
. For each nℓ , define a packing
i=0

P (nℓ ) := τ (C (nℓ ) ) + Lnℓ ℓ

as in Eq. (9).
Next we take ℓ increasingly
to ∞. The following proposition describes
the asymptotic density exponent


of the packing family F = P (nℓ ) ℓ→∞ , where nℓ = q 2ℓ/m |DK |1/m tends to ∞ as ℓ goes to ∞.
Proposition 3.7. The asymptotic density exponent of the family F satisfies
λ(F )

>

−1 −

1
1
m
log2 |DK | − log2
2m
2
2πe

!
ℓ−1
log2 q X ′  (nℓ ) 
1
,
H ̺
+ lim sup log2 dE (Lℓ ) − log2 nℓ −
2
m i=0 q i
ℓ→∞
where Hq′ (̺) = Hq (̺) for 0 < ̺ <

q−1
q−1
and Hq′ (̺) = 1 for
6 ̺ 6 1.
q
q

10

(13)

Proof. By Corollary 3.5,
λ(F ) > lim sup
ℓ→∞

= −1 −





ℓ−1
Y

mnℓ

1
(dE (Lℓ )/2)
Vmn
(n )
nℓ ℓ ·
Mi ℓ 
log2   p
mnℓ
ℓ
q |DK |
i=0

1
log2 |DK | +
2m

ℓ−1

(nℓ )

X log q · k
1
ℓ
2
i
log2 Vmnℓ +
log2 q +
+ lim sup log2 dE (Lℓ ) −
m
mnℓ
mn
ℓ
ℓ→∞
i=0

!

.

By Eq. (3),
ℓ−1

lim sup
ℓ→∞

=

>

=

=

(nℓ )

X log q · k
1
2
i
log2 Vmnℓ +
mnℓ
mn
ℓ
i=0

!

ℓ−1 (n )
log2 q X ki ℓ
mnℓ
1
1
log2 mnℓ π +
−
lim sup − log2
2
2πe
2mnℓ
m i=0 nℓ
ℓ→∞

!

ℓ−1


1
m
1
log2 q X
(n )
− log2
RGV q, ̺i ℓ
+ lim sup − log2 nℓ +
2
2πe
2
m i=0
ℓ→∞

!

ℓ−1


m
1
log2 q X 
1
(n )
1 − Hq′ ̺i ℓ
+ lim sup − log2 nℓ +
− log2
2
2πe
2
m i=0
ℓ→∞

1
m
− log2
+ lim sup
2
2πe
ℓ→∞

!

!
ℓ−1
1
log2 q X ′  (nℓ ) 
ℓ
.
H ̺
log2 q − log2 nℓ −
m
2
m i=0 q i

In summary, we get Eq. (13).

3.4

Examples

We use some explicit examples to illustrate our new construction. Here Magma V2.21-4 [5, 4] will be employed
to obtain the numerical results.
For the finite concatenation, we use the linear codes from [11] which have an explicit construction. For
the asymptotic result, we set sufficiently large ℓ to approximate the limit.
Example 3.8. Consider the number field K = Q[α], where α is a root of the irreducible polynomial
f (x) = x4 − x3 − x2 + x + 1 ∈ Q[x].
K/Q is a totally complex number field with extension degree [K : Q] = 4 and absolute discriminant |DK | =
117. The absolute discriminant is the smallest one of all totally complex number fields with degree 4 (see
[16]).
(i) We consider a prime ideal p lying over 3 ∈ Z. The Magma code of this example is listed in Appendix
A, while for other examples, the Magma code can be modified from this template.
The key outputs of Appendix A are listed here:
The degree of K=Q[x]/(x^4 - x^3 - x^2 + x + 1) is m=4;
The absolute value of the discriminant of K is |d|=117;
11

P is a Prime Ideal of O
Two element generators:
[3, 0, 0, 0]
[2, 1, 1, 0] lying over 3 with norm q=9;

The above statement means p = (3, 2 + α + α2 ).
Finite Concatenation:
We can concatenate at most 3 linear codes to the lattice
constructed by 64 copies of L_{P^3},
whose Hamming weights are required respectively at least
27;9;3;

Referring to [11], as the norm of p is 9, we can use the existing 9-ary linear codes C0 , C1 , C2 with
parameters
[64, 25, 27] , [64, 49, 9] , [64, 61, 3]
respectively. The sum of the dimensions is 135. Considering the concatenation in Corollary 3.5, we
obtain a packing with dimension 4 × 64 = 256, whose center density δ satisfies
Our packing is in dimension 256 with Log_2(center density)
at least 208.088204168043224246772217517

Note that our packing is denser than the Barnes-Wall lattice BW256 , whose density is listed in the table
of dense sphere packings [8, Table 1.3].
Using this ideal to construct a packing family as in Proposition 3.7, we get the following result.
Asymptotic result:
The asymptotic density exponent of the packing family is
at least -1.442426720

Note that the above result means our packing family is asymptotically good.
(ii) For this field, we similarly analyze other prime ideals and list part of our numerical results in Table 1,
where δ is the center density and λ is the asymptotic density of the corresponding packing family.
Example 3.9. Consider the number field K = Q[α], where α is a root of the irreducible polynomial
f (x) = x3 + x2 − 2x − 1 ∈ Q[x].
K/Q is a totally real number field with extension degree [K : Q] = 3 and absolute discriminant |DK | = 49.
The absolute discriminant is the smallest one of all totally real cubic number fields (see [16]). The numerical
results on our examples are partially listed in Table 2.
12

Table 1: Examples constructed from Q[x]/ x4 − x3 − x2 + x + 1
p
q dimension log2 δ at least λ at least
180
108.52
(3, 2 + α + α2 ) 9
256
208.091
−1.442
512
590.52
256
190.63
(7, 4 + α)
7
−1.453
400
410.15
1



The packing can be explicitly constructed with log2 δ larger than 192
given by the Barnes-Wall lattice BW256 .

Table 2: Examples constructed from Q[x]/ x3 + x2 − 2x − 1
p
(2)

q
8

(7, 5 + α)

7

dimension
255
192
255

log2 δ at least
134.46
83.68
157.63

λ at least
−1.628



−1.585

Example 3.10. Consider the number field K = Q[α], where α is a root of the irreducible polynomial
f (x) = x3 + x2 − 1 ∈ Q[x].
K/Q is a number field with extension degree [K : Q] = 3 and absolute discriminant |DK | = 23. The absolute
discriminant is the smallest one of all cubic number fields (see [16]). The numerical results on our examples
are partially listed in Table 3.
Table 3: Examples constructed from Q[x]/ x3 + x2 − 1
p

q

(2)

8

(5, 2 + α)

5

(7, 11 + α)

7

dimension
96
192
150
180
255

log2 δ at least
24.70
115.40
69.47
101.01
187.32



λ at least
−1.429
−1.445
−1.430

Example 3.11. Consider the number field K = Q[α], where α is a root of the irreducible polynomial
f (x) = x6 + x3 + 1 ∈ Q[x].
K/Q is a number field with extension degree [K : Q] = 6 and absolute discriminant |DK | = 19683. The
polynomial f (x) = x6 + x3 + 1 is the 9th cyclotomic polynomial over Q. The numerical results on our
examples are partially listed in Table 4.

4

Conclusion

This paper provides a new method to construct dense packings using canonical Q-embedding of algebraic
number fields, and special codes over the residue field of some prime ideals. With the help of Magma V2.21-4,
13


Table 4: Examples constructed from Q[x]/ x6 + x3 + 1
p
q dimension log2 δ at least λ at least
180
109.71
(3, 2 + α) 3
−1.868
192
122.72
several explicit constructions were provided in Examples 3.8 - 3.11. Especially, in R256 , a packing denser
than the Barnes-Wall lattice BW256 was obtained. Moreover, this method can be utilized to construct
asymptotically good packing families. For each number field and prime ideal in Tables 1 - 4, a lower bound
on the asymptotic density exponent of the corresponding packing family was provided.

Acknowledgements
Financially, the accomplishment of the first version had been partially supported by Nanyang Technological
University under NTU Research Scholarship, when the author was a PhD candidate, and partially supported
by Yujie Nan when the author was unemployed till he joined RMI, NUS.
The author sincerely thanks his PhD supervisors, San Ling and Chaoping Xing, for introducing him
to this topic, especially for the invaluable suggestions and comments from Chaoping Xing which make the
author’s initial idea become mature.

A

Magma Code for Example 3.8

R:=RealField(10); Q:=RationalField();
W<x>:=PolynomialRing(Q); f:=x^4-x^3-x^2+x+1;
/*Input a polynomial over rational number field Q*/
if IsIrreducible(f) then
/* Test whether f is irreducible*/
K<a>:=NumberField([f]); O:=MaximalOrder(K); m:=AbsoluteDegree(K);
printf"The degree of K=Q[x]/(%o) is m=%o;\n",f,m;
d:=AbsoluteDiscriminant(K);
printf"The absolute value of the discriminant of K \
is |d|=%o;\n",d;
p:=3;
/*Choose p=3 as a base prime number*/
J:=Decomposition(O,p); P:=J[1,1]; q:=Norm(P);
printf"P is a %o lying over %o with norm q=%o;\n",P,p,q;
printf"\nFinite Concatenation:\n";
n:=64; l:=Floor(m/2*Log(n)/Log(q));
/*Set the length of the codes*/
L:=MinkowskiLattice(P^l); b:=Minimum(L);
printf"We can concatenate at most %o linear codes to \
the lattice constructed by %o copies of L_{P^%o},\n \
whose Hamming weights are required respectively at least \
\n",l,n,l;
for t in [0..l-1] do
Z:=MinkowskiLattice(P^t); h:=Ceiling(Minimum(L)/Minimum(Z));
printf"%o;",h;
end for;
printf"\n";

14

printf"Refer to the Codetable.de to get the largest dimension \
of the corresponding linear codes with length %o; \n",n;
fromtable:=135;
printf"Here the sum of dimensions T=%o;\n",fromtable;
/*For this example, the sum of the dimensions is 135*/
c:=(m*n*Log(b^0.5)-n*l*Log(q)-0.5*n*Log(d))/Log(2)-m*n;
printf"Our packing is in dimension %o with \
Log_2(center density) at least\n %o\n",n*m,\
c+Log(q)/Log(2)*fromtable;
printf"\nAsymptotic result:\n";
l:=1000; n:=Ceiling(q^(2*l/m)*d^(1/m));
/*Set l sufficiently large to approximate the limit*/
L:=MinkowskiLattice(P^l);b:=Minimum(L);
Sum:=0;
for t in [l-1..0 by -1] do
Z:=MinkowskiLattice(P^t);
g:=Ceiling(Minimum(L)/Minimum(Z));
varrho:=g/n;
if varrho le (q-1)/q then
Sum:=Sum+(varrho*Log(q-1)-varrho*Log(varrho)\
-(1-varrho)*Log(1-varrho))/Log(q);
else Sum:=Sum+1;
end if;
end for;
Lambda:=-1-1/(2*m)*Log(d)/Log(2)-0.5*Log(m/(2*Pi(R)*Exp(1))) \
/Log(2)+Log(b^0.5)/Log(2)-0.5*Log(n)/Log(2) \
-1/m*Log(q)/Log(2)*Sum;
printf"The asymptotic density exponent of the packing family is \
\n at least %o",Lambda;
else
printf"The polynomial %o is not irreducible over Q.\n",f;
end if;

References
[1] M.F. Atiyah and I.G. MacDonald. Introduction to Commutative Algebra. Addison-Wesley Series in
Mathematics, Westview Press, 1994.
[2] C. Bachoc. Applications of Coding Theory to the Construction of Modular Lattices . Journal of Combinatorial Theory, Series A, 1997, 78, no. 1: 92 – 119.
[3] E. Bayer-Fluckiger. Ideal Lattices. A Panorama of Number Theory Or The View from Baker’s Garden,
Cambridge University Press, 2002, pp. 168–184.
[4] W. Bosma, J.J. Cannon, C. Fieker, and A. Steel (eds.). Handbook of Magma Functions, v2.21 ed., online
http://magma.maths.usyd.edu.au/magma/handbook/, 2015.

15

[5] W. Bosma, J.J. Cannon, and C. Playoust. The Magma Algebra System. I. The User Language. J.
Symbolic Comput, 1997, 24, no. 3-4, 235–265, Computational algebra and number theory (London,
1993).
[6] J.W.S. Cassels. An Introduction to the Geometry of Numbers. Springer-Verlag, New York, 1997.
[7] S. Cheng. Improvement on Asymptotic Density of Packing Families Derived from Multiplicative Lattices.
Finite Fields and Their Applications, 2015, 36: 133–150
[8] J.H. Conway and N.J.A. Sloane. Sphere Packings, Lattices and Groups, 3rd ed., Springer-Verlag, New
York, 1999.
[9] N.D. Elkies. Lattices, Linear Codes, and Invariants, Part II. Notices of the AMS 47(11), 1382–1391
(2000)
[10] P. Gaborit and G. Zémor. On the Construction of Dense Lattices with A Given Automorphisms Group.
Annales de l’institut Fourier, 2007, 57, no. 4: 1051-1062
[11] M. Grassl. Bounds on the Minimum Distance of Linear Codes and Quantum Codes, Online available at
http://www.codetables.de, 2007, Accessed on 2016-06-25.
[12] F.J. MacWilliams and N.J.A. Sloane. The Theory of Error-correcting Codes, North-Holland Mathematical Library, North-Holland Publishing Company, 1977.
[13] D. Micciancio and S. Goldwasser. Complexity of Lattice Problems: A Cryptographic Perspective, The
Kluwer International Series in Engineering and Computer Science, vol. 671, Kluwer Academic Publishers, Boston, Massachusetts, March 2002.
[14] J. Neukirch. Algebraic Number Theory, Grundlehren der mathematischen Wissenschaften : a series of
comprehensive studies in mathematics, vol. 322, Springer-Verlag Berlin Heidelberg, 1999.
[15] P.Q. Nguyen. Hermite’s Constant and Lattice Algorithms, The LLL Algorithm - Survey and Applications
(P.Q. Nguyen and B. Vallée, eds.), Information Security and Cryptography, Springer, 2010, pp. 19–69.
[16] A. M. Odlyzko. Bounds for Discriminants and Related Estimates for Class Numbers, Regulators and
Zeros of Zeta Functions : A Survey of Recent Results, Journal de théorie des nombres de Bordeaux,
1990, 2, no. 1: 119–141.
[17] J.A. Rush. A Lower Bound on Packing Density. Inventiones mathematicae, 1989, 98, no. 3: 499-509.
[18] M.A. Tsfasman and S.G. Vlăduş. Algebraic-Geometric Codes, Kluwer Academic, 1991.
[19] C. Xing. Dense Packings from Quadratic Fields and Codes. Journal of Combinatorial Theory, Series A,
2008, 115, no. 6: 1021–1035.
[20] C. Zong. Sphere Packings, Universitext (1979), Springer-Verlag New York, 1999.

16

