Intersection problem for the class of quaternary reed-muller codes
Except where reference is made to the work of others, the work described in this
dissertation is my own or was done in collaboration with my advisory committee. This
dissertation does not include proprietary or classi ed information.
Abel Ahbid Ahmed Delgado Ortiz
Certi cate of Approval:
Douglas A. Leonard
Professor
Mathematics and Statistics
Kevin T. Phelps, Chair
Professor
Mathematics and Statistics
Geraldo S. De Souza
Professor
Mathematics and Statistics
George T. Flowers
Dean
Graduate School
Intersection problem for the class of quaternary reed-muller codes
Abel Ahbid Ahmed Delgado Ortiz
A Dissertation
Submitted to
the Graduate Faculty of
Auburn University
in Partial Ful llment of the
Requirements for the
Degree of
Doctor of Philosophy
Auburn, Alabama
August 10, 2009
Intersection problem for the class of quaternary reed-muller codes
Abel Ahbid Ahmed Delgado Ortiz
Permission is granted to Auburn University to make copies of this dissertation at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Dissertation Abstract
Intersection problem for the class of quaternary reed-muller codes
Abel Ahbid Ahmed Delgado Ortiz
Doctor of Philosophy, August 10, 2009
(M.S., University of Puerto Rico, February 16, 2003)
(B.S., Universidad Nacional San Antonio Abad, December 17, 1996)
58 Typed Pages
Directed by Kevin T. Phelps
Given two codesC1 andC2 over an alphabet F, we denote the size of their intersection
by  (C1;C2), and call this the intersection number of C1 and C2.
In general the intersection problem can be stated as follows: given a family or class of
families of codes,  nd the spectrum of intersection numbers. The general strategy to attack
this kind of problem begins by  nding necessary conditions for the intersection. This leads
to lower and upper bounds or a set of possible intersection numbers. Secondly,  nding the
su cient conditions implies giving speci c constructions of codes in such a way that the
cardinality of their intersection  ts those values between these bounds.
In this dissertation is presented a complete solution of the intersection problem for
QRM(r;m). This includes the well-known quaternary Kerdock code, the Kerdock-like
code and Preparata-like code.
iv
Style manual or journal used Journal of Approximation Theory (together with the style
known as \aums"). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (speci cally LATEX)
together with the departmental style- le aums.sty.
v
Table of Contents
1 Introduction 1
2 Binary Reed-Muller codes and Quaternary Reed-Muller codes 6
2.1 Binary Reed-Muller Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 The Quaternary Reed-Muller Codes . . . . . . . . . . . . . . . . . . . . . . 11
2.3 The Class of Quaternary Reed-Muller Codes . . . . . . . . . . . . . . . . . 14
3 Intersection 17
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Intersection problem for q-ary linear codes . . . . . . . . . . . . . . . . . . . 17
3.3 Intersection problem for perfect codes . . . . . . . . . . . . . . . . . . . . . 20
3.4 Intersection problem for Hadamard Codes . . . . . . . . . . . . . . . . . . . 22
3.5 Intersection problem for Quaternary linear codes . . . . . . . . . . . . . . . 25
4 Intersection Problem for The Class of Quaternary Reed-Muller
Codes 27
4.1 Application to QRM(r;m) . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5 Concluding Remarks 47
Bibliography 51
vi
Chapter 1
Introduction
Let Zn2 denote the vector space of dimension n over Z2. A linear subspace of dimension
k will be called a binary-[n;k]-linear code over Z2, [n;k]-code for short. An element of a
code C is called a codeword. A k n matrix G, whose rows form a basis for an [n;k]-code
is called a generator matrix of the code. An information set for C is any set of k linearly
independent columns of G. The remaining r = n k columns are called a redundant set and
r is the redundancy of C. G is called systematic if it has the form [IjA], where I is a k k
identity matrix and A is a k (n k) matrix. A code C has a systematic generator matrix
if and only if the  rst k columns of any generator matrix of C are linearly independent. In
this case the information set is taken to be the set of the  rst k columns of the matrix.
The inner product of two vectors x = (x1;:::;xn), and y = (y1;:::;yn) in Zn2 is
x y =
nX
i=1
xiyi (mod 2): (1.1)
Given a [n;k]-code C, the dual code or orthogonal code of C is de ned by
C? =fx2Zn2jx c = 0;8c2Cg: (1.2)
C? is a [n;n k]-code. A code C is self-orthogonal provided that C C? and self-dual
provided that C = C?:
An (n k) n matrix H is called a parity-check matrix for the [n;k]-code C if the
columns of H form a basis for the dual code C. If G = [IkjA] is a generator matrix for the
[n;k]-code C, then H = [ ATjIn k] is a parity-check matrix for C.
1
The Hamming distance d(x;y) between two vectors x, y2Zn2 is the number of positions
in which x and y di er. The minimum (Hamming) distance d of a code C is the smallest
distance between distinct codewords. The (Hamming) weight wt(x) of a vector x 2Zn2 is
the number of nonzero coordinates in x. If C is a linear code, the minimum distance d
coincides with the minimum weight of the nonzero codewords of C. If the minimum weight
d of an [n;k]-code is known, then we refer to the code as an [n;k;d]-code.
Let Ci be an [n;ki;di]-code for i2f1;2g, both over Z2. The (uju + v) construction
produces the [2n;k1 +k2;minf2d1;d2g] code
C =f(u;u + v)ju2C1;v2C2g: (1.3)
If Ci has a generator matrix Gi and parity-check matrix Hi, then generator and parity-check
matrices for C are
0
B@ G1 G2
0 G2
1
CA and
0
B@ H1 0
 H2 H2
1
CA: (1.4)
Let [n] be the set f1;2;:::;ng. Sn denotes the symmetric group of [n]. Two [n;k]
codes C1, C2, are permutation equivalent if there exists a permutation  2Sn such that
C1 =  (C2).
Let Zn4 be the set of all n-tuples over Z4. If C is an additive subgroup of Zn4 then it is
called a quaternary linear code of length n. C can be expressed as a direct sum of  cyclic
subgroups of order 4 of Zn4 and  cyclic subgroups of order 2 of Zn4, and we say that the
type of C is 4 2 . Notice that C has 2m elements, where 2  +  = m. Alternatively, we
can say that C is code of type (n; ; ) or that C is an (n; ; )-code.
We call G a generator matrix of C if its rows generate C.
Every quaternary linear codeC of type 4 2 is permutation equivalent to a quaternary
linear code with generator matrix of the form
2
0
B@ I A B
0 2I 2C
1
CA; (1.5)
where I and I denote the identity matrices, of order  and  , respectively, A, C, are Z2-
matrices, B is a Z4- matrix and 0 is the    zero matrix.
The inner product of two vectors x = (x1;:::;xn), y = (y1;:::;yn) in Zn4 is
x y =
nX
i=1
xiyi (mod 4): (1.6)
Let C be a quaternary linear code of length n. De ne the dual code of C as
C? =fx2Zn4jx c = 0;8c2Cg: (1.7)
Notice that C? is a quaternary linear code. If the generator matrix of C is given by
(1.5), then the generator matrix of C? is given by
0
B@  BT CTAT CT In    
2AT 2I 0
1
CA (1.8)
The Lee weights of 0, 1, 2, 32Z4 are 0, 1, 2, 1, respectively. For i2Z4, the Lee weight
of i is denoted by wL(i). The Lee weight wL(x) of x = (x1:::xn)2Zn4 is de ned to be the
integral sum of the Lee weights of its components,
wL(x) =
nX
i=1
wL(xi): (1.9)
This weight function de nes a distance function dL(x;y) = wL(x y) on Zn4, which is
called the Lee distance.
3
The map  : Z4 !Z24, de ned by  (0) = 00;  (1) = 01;  (2) = 11, and  (3) = 10, is
called the Gray map. This map can be extended componentwise to a map, also denoted by
 , from Zn4 to Z2n2 : In general, given a quaternary linear code C, its binary image  (C) will
be nonlinear. A binary code C is called Z4-linear if, after a permutation of coordinates, it
is the binary image of a quaternary linear code.
An important property of the Gray map is that it is a distance preserving map from Zn4
(with the Lee distance) to Z2n2 (with the Hamming distance). Moreover ifC i s a quaternary
linear code then  (C) is distance invariant.
A decomposition of a permutation  2Sn into nonintersecting cycles of length greater
than 1, will be called canonical, and it is denoted as follows:
 =
 ( )Y
j=2
(
 jY
i=1
(vji;1   vji;j)); (1.10)
where  j denotes the number of j-cycles in the decomposition of  . The number of cycles
will be denoted by  ( ) = P?j=2 j. For a cycle  = (v?p;1v?p;1:::v?p;?) of length ? in  , ?
will be denoted by  ( ). The sum of all lengths of the cycles in  will be denoted by  ( ).
( ( ) = P ( )j=2 j  j):
Associated with  , there is a matrix P of order n, called a permutation matrix in
which P (i;j) = 1; if  (i) = j and 0 otherwise.
The diagonal matrix diag(a1;a2;:::an) of order n is the matrix D de ned by D(i;j) := 0
if i6= j and D(i;i) := ai where ai are real entries.
Any matrix that can be written as the product of a permutation matrix and a diagonal
matrix is called a monomial matrix.
Since we are interested in quaternary linear codes, we are going to use monomial
matrices that have the matrix diag(a1;a2;:::an) with entries ai equal -1 or 1. De ne the
diagonal matrix Di as diag(a1;a2;:::an), where aj = 1 if i = j, and aj = 1, otherwise.
Associated with Di there is a map  i : Zn4 !Zn4 that multiplies the ith-coordinate of
each vector of Zn4 by  1. For i = 0;:::;n,  i is called the inversion of the ith-coordinate,
4
where Id =  0. In general, we will write  to denote an inversion of coordinates and  s,
when we want to emphasize the set S of coordinates. Let  2Sn and  an inversion of
coordinates, the map  ( ) is called a monomial map. If P is the matrix associated to  , and
D, the matrix associated to  , then the matrix PD is the matrix associated to the monomial
map  ( ). Here D is the diagonal matrix that has -1 in those positions determined by  .
From now on by monomial map or monomial matrix, we mean just what we say in this
paragraph.
We say that C1 and C2 are monomially equivalent, provided there is a monomial map
 ( ) such that  ( (C1)) = C2. Two quaternary linear codes that are equivalent are of the
same type.
Given a vector x = (x1::: xn) and a subset I =fi1;:::;ikg [n], k<n, the projection
of x onto I is the vector xjI = (xi1;:::;xik) where ij < ij+1, 1  j k 1. For a given
permutation  =
 1 2:::n
i1i2:::in
 
, xj = xjI.
In chapter 2 and 3 of this dissertation we set up the reference frame for chapter 4.
Speci cally, chapter 2 contains the de nitions and background information required to
understand the main result and chapter 3 reviews the intersection problem from an historical
point of view.
Chapter 4 presents the two main results: Theorem 4.7 which gives the intersection num-
ber for quaternary t IR codes and Theorem 4.9 which determines the algebraic structure
of those intersections, moreover shows explicit constructions of their generator matrices.
We end this chapter by applying these results to the class of quaternary Reed-Muller codes.
Chapter 5 refers to the conclusions of this dissertation, as well as open problems and
future directions for research.
5
Chapter 2
Binary Reed-Muller codes and
Quaternary Reed-Muller codes
Since the codes that are the focus of this dissertation are characterized in terms of
binary Reed Muller codes, in this chapter we are going to review their principal properties.
In the literature, there are several constructions of these codes, but they were  rst treated
by D.E Muller (1954) and I.S Reed (1954). The mathematical interest of Reed-Muller codes
is that they are related to a ne and projective geometries.
Kumar etal. [1], presented a construction of the quaternary Kerdock codeK(m) as well
as a construction of the quaternary Preparata code P(m), which is the Z4-dual of K(m).
The Gray map image of the quaternary Kerdock codeK(m) is a nonlinear binary code K(m)
that is permutation equivalent to the original de nition given by Kerdock. The quaternary
Preparata code is de ned asP(m) =K(m)?. The binary Gray map image ofP(m) gives a
nonlinear code, P, that has the same parameters of the original code de ned by Preparata,
but there is an essential di erence between P(m) and P. The  rst one is contained in a
nonlinear code with the same weight distribution as the extended binary Hamming code of
the same length (see Theorem 9.10 of [2]). The second one, is a subcode of the extended
binary Hamming code of the same length (Proposition 9.14 of [2]). It is known that there are
several codes with the same parameters as the quaternary Preparata code. They are named
quaternary Preparata-like codes and their Z4 dual are codes with the same parameters as the
Kerdock codes . In [1], they also established the quaternary Reed Muller codeQRM(r;m),
as a Z4-version of the binary Reed Muller code, which includes quaternary Kerdock codes
and Preparata codes as special cases and have the property that their images through  
(mod 2) map are the binary Reed-Muller codes. Considering arbitrary Preparata-like codes
it was observed in [3] that it is possible to construct a family of quaternary codes similar to
6
that constructed in [1], whose binary image through the  (mod 2) map is a Reed Muller
code that contains the Kerdock-like codes and the Preparata-like codes as a special cases.
In [6], [5] a superclass that contains the QRM(r;m) was de ned. Also various prop-
erties including the kernel and rank of the Gray map of codes in this superclass were
established in [3].
2.1 Binary Reed-Muller Codes
Let r;m2Z such that 0 r m. Consider, the set of all binary vectors of length m
ordered lexicographically. Any function f : Zm2  !Z2 is called a Boolean function, de ned
on m variables. If we evaluate f on its domain, the corresponding 2m entries de ne a unique
binary vector f of length n = 2m. Conversely, given any binary vector of length n, we can
associate a unique Boolean function de ned on m variables whose domain is Zm2 . Thus,
there is a bijection between Boolean functions f and the corresponding vectors f. Since f
has 2m entries and each one can be 0 or 1, we have 22m vectors and therefore the same
number of Boolean functions.
For example, the binary vector f = 11010010 of length 8, corresponds to the Boolean
function on three variables f, de ned by its truth table:
x1 x2 x3 f
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
7
For 1 j m, denote by xj the Boolean function de ned by the correspondence rule
f(x1;:::;xm) = xj. The corresponding vector xj of length 2m has a 1 in the coordinate i
if and only if 2m j occurs in the binary expansion of i 1.
For example, let m = 3, j = 2. 23 2 occurs in the binary expansion of 2,3,6,7, therefore,
x2 has 1 in the coordinates 3,4,7,8, thus x2 = (0;0;1;1;0;0;1;1):
Also, the constant Boolean functions, denoted by 0 and 1 are associated with the all
zeros vector 0 and the all ones vector 1. Given two Boolean functions f and g, the sum f+g,
and the product fg correspond to the logical operators ^ and _. The function f = 1 f,
correspond to the operator NOT.
The set B of all Boolean functions de ned on m-variables, which is equal to the set of
all binary functions de ned on Z2, is a linear space over Z2. Thus, B with the standard
addition and scalar multiplication of functions, is a linear space over Z2. Moreover, due to
the standard product of functions,B is a commutative linear algebra. Notice, that we have
the following relations:
xi xi = xi; and xi xj = xj xi : (2.1)
We relate the Boolean functions to their corresponding binary vectors by de ning the
componentwise product of the vectors a = (a1;:::;an) and b = (b1;:::;bn) over Z2 as
ab = (a1b1;:::;anbn) (2.2)
Thus, binary vectors related to (2.1) are given by
xixi = xi; and xixj = xjxi : (2.3)
Using, the product and the functions xj, we get 2m 1 terms with di erent forms
xi1   xik; with k m and i1 <i2 <   <ik (2.4)
8
The linear combination of the function 1 with the terms in (2.4) are linearly independent
[7] and therefore the corresponding binary vectors
1;x1;x2;:::;xm;x1x2;x1x3;:::;x1x2x3   xm; (2.5)
are also linearly independent and generate Zn2: The next table is an example of the 16
Boolean functions that generate the space of all the Boolean functions from Z42 to Z2, and
the corresponding binary vectors of length 16 that generate Z162 :
Booleanfunction Vector
1 1 = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
x1 x1 = 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
x2 x2 = 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x3 x3 = 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
x4 x4 = 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
x1x2 x1x2 = 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1
x1x3 x1x3 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
x1x4 x1x4 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
x2x3 x2x3 = 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1
x2x4 x2x4 = 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0
x1x2x3 x1x2x3 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
x1x2x4 x1x2x4 = 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
x1x3x4 x1x3x4 = 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
x2x3x4 x1x2x4 = 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
x1x2x3x4 x1x2x3x4 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
9
Let 0 r m. The rth order Reed-Muller code R(r;m) of length n = 2m is the set of
codewords generated by the matrix G(r,m):
G(r;m) =
0
BB
BB
BB
BB
BB
@
G0
G1
G2
...
Gr
1
CC
CC
CC
CC
CC
A
:
where G0 is the 1 2m matrix equals to the all-one vector of length 2n, G1 is the  m1  2m
matrix whose rows are the binary vectors x1;:::;xn given in (2.4), and for 1 <r m, Gr,
is the  mr  2m matrix whose rows are the binary vectors obtained by the componentwise
multiplication of a choice of r rows of G1:
There are two trivial codes: R(0;m), called the repetition code with generator matrix
G(0;m) and R(m;m) which is the all space Zn2. As an example of a nontrivial code, we have
the second order Reed-Muller code of length 16, RM(2;4), given by the following generator
matrix :
G =
0
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
B@
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0
1
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CA
:
Alternatively, these codes can be constructed using the (uju+v) construction(1.3)
10
Theorem 2.1. Let r;m be integers such that 0 r m. The rth order Reed-Muller code
RM(r;m) is constructed in the following way:
1. The 0th order Reed-Muller code RM(0;m) is the repetition code f0;1g, and the mth-
order Reed-Muller code RM(m;m) is Z2m2
2. RM(r;m) =f(u;u + v)ju2RM(r;m 1);v2RM(r 1;m 1)g, 0 <r<m
For 0 < r < m, let G(r;m) be a generator matrix of the Reed-Muller code, then
according to (1.4)
G(r;m) =
0
B@ G(r;m 1) G(r;m 1)
0 G(r 1;m 1)
:
1
CA
For r = 0, G(r;m) = (1) and for r = m,
G(m;m) =
0
B@ G(m 1;m)
ei
1
CA:
where ei = (0;::;1;::;n). The number 1 appears at the ith-position.
The following theorem shows the principal properties of Reed-Muller codes.
Theorem 2.2. Let r;m be integers such that 0 r m. Then the following hold:
1. R(i;m) R(j;m), if 0 i j m.
2. The dimension of R(r;m) equals k = 1 + m1 + m2 +:::+ mr .
3. The minimum weight of R(r;m) equals 2m r.
4. R(m;m)? =f0g and if 0 r<m, then R(r;m)? = RM(m r 1;m):
2.2 The Quaternary Reed-Muller Codes
The purpose of this section is to introduceQRM(r;m) codes, which were de ned in [1]
to be quaternary Reed-Muller codes of length 22m. In order to proceed, some terminology
and notation is needed. We follow closely the book Quaternary codes (see [2])
11
In chapter 1 we saw that the Gray map relates codes of length n over Z4 with binary
codes of length 2n. But also, we can relate codes of length n over Z4 with binary codes of the
same length. A natural way is to extend componentwise the additive group homomorphism
 : Z4!Z2, de ned by  (0) =  (2) = 0,  (1) =  (3) = 1 to a map  : Zn4 !Zn2. Thus, if
x = (x1;:::;xn), then  (x) = ( (x1);:::; (xn)).
Let Z4[X] be the polynomial ring with coe cients in Z4. The map  can be naturally
extended to a map from Z4[X] to Z2[X] as follows
Z4[X]!Z2[X]
a0 +a1X +   +anXn! (a0) + (a1)X +   + (an)Xn
Let h(X) be a monic polynomial of degree m 1 in Z4[X]. If  (h(X)) is irreducible
over Z2, then h(X) is called a basic irreducible polynomial of degree m in Z4[X]. If h(X) is
primitive of degree m over Z2 then h(X) is called a basic primitive polynomial of degree m
in Z4[X].
Let 2 m2Z and n = 2m 1. Let  be a root of a basic primitive polynomial h(x)
of degree m dividing Xn 1. Since  is a basic primitive root of unity,  ; 2;:::; n = 1, are
n distinct root of h(x). Consider the (m+ 1) 2m matrix
0
B@ 1 1 1 1 : : : 1
0 1   2 : : :  n 1
1
CA; (2.6)
whose rows are are numbered by 0;1;:::;m and columns by1;0;1:::;n 1, where  j should
be replaced by t(b1j;:::;bmj) if  j = b1j +   + bmj m 1 (j = 1;0;1:::;n 1) and we
agree that  1 = 0. Denote the ith row of the matrix by ui, then the quaternary rth order
Reed-Muller code QRM(r;m) of length 2m is the code generated by the 2m tuples of the
form
ui1ui2;:::;uis; 1 i1 <i2;:::;<is m; 0 s r;where ui1ui2;:::;uis = 12m (2.7)
when s=0.
12
It can be proved that these vectors, form a basis over the free Z4 module Z2m4 . Basic
properties of QRM(r;m) codes are enlisted in the following Theorem
Theorem 2.3. [1]Let r;m integers such that 0 r m. Let QRM(r;m) be a quaternary
Reed-Muller code of length 2m
1. QRM(r;m) is of type 4k where k = 1 + m1 + m2 +   + mr :
2. QRM(r;m) QRM(r + 1;m), 8r<m.
3.  (QRM(r;m)) = RM(r;m):
When r = 1,QRM(1;m), is known as the quaternary linear Kerdock code and will be
denoted byK(m). If m 2 and 0 r m 1, thenQRM(r;m)? =QRM(m r 1;m).
Another well-known code is obtained whenr = m 2, named the quaternary linear Preparata
code, denoted byP(m). The quaternary Kerdock code and the quaternary Preparata code
were  rst de ned in [1].
Since QRM(m 2;m) =QRM(1;m)? =K(m)? =P(m), the quaternary Preparata
codes are duals of Kerdock codes and therefore, P(m) is of type 4k1, where, k1 = 2m k,
with k =k = 1 + m1 .
The Gray map image ofQRM(r;m) is a Z4-linear code which is denoted byQRM(r;m).
Notice that this code is a nonlinear binary code.
We illustrate the previous discussion with an example. Let h(x) = x4+3x3+2x2+1 be
a basic irreducible polynomial over Z4. Let  be a root of h(x) in the Galois ring GR(44).
Then,  = (0;1;0;0),  2 = (0;0;1;0),  3 = (0;0;0;1), and  j for j  4 is getting using
 4 =  3 + 2 2 + 3: Using (3:2:1) we get the generator matrix of K(4):
0
BB
BB
BB
BB
BB
@
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 0 0 3 3 1 3 2 1 0 3 1 2 0
0 1 1 0 0 0 3 3 1 3 2 1 0 3 1 2
0 1 0 1 0 2 2 1 1 1 1 2 3 2 3 1
0 1 0 0 1 1 3 1 2 3 0 1 3 2 0 3
1
CC
CC
CC
CC
CC
A
=
0
BB
BB
BB
BB
BB
@
u0
u1
u2
u3
u4
1
CC
CC
CC
CC
CC
A
:
13
The quaternary Preparata code, P(4) =QRM(2;4), is generated by
0
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
B@
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 0 0 3 3 1 3 2 1 0 3 1 2 0
0 1 1 0 0 0 3 3 1 3 2 1 0 3 1 2
0 1 0 1 0 2 2 1 1 1 1 2 3 2 3 1
0 1 0 0 1 1 3 1 2 3 0 1 3 2 0 3
0 1 0 0 1 0 1 3 3 2 2 0 0 3 2 0
0 1 0 0 0 2 2 1 3 2 1 0 1 2 2 0
0 1 0 0 0 3 1 1 2 2 0 0 1 2 0 0
0 1 0 0 0 0 2 3 1 3 2 2 0 2 3 1
0 1 0 0 0 0 1 3 2 1 0 1 0 2 0 2
0 1 0 0 0 2 2 1 2 3 0 2 1 0 0 3
1
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CA
=
0
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
B@
u0
u1
u2
u3
u4
uiu2
u1u3
u1u4
u2u3
u2u4
u3u4
1
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CA
:
2.3 The Class of Quaternary Reed-Muller Codes
The class QRM(r;m) of quaternary Reed-Muller codes is a generalization of QRM
codes. We describe brie y those aspects that are relevant to the purpose of this dissertation.
The material used in this section can be found in the paper [6] and chapter six of [5].
De nition 2.3.1. Let r;m2Z and 0 r m. C2QRM(r;m) if and only if :
1. The quaternary length of the code C is 2m.
2. C is of type 4k, where k = 1 + m1 + m2 +   + mr 
3.  (C) = RM(r;m):
The related binary class is de ned as QRM(r;m) =fCjC =  (C)2QRM(r;m)g
By Theorem 2.3QRM(r;m) codes satis es de nition 2.3.1 above. Thus,QRM(r;m)2
QRM(r;m). In order to give another example, let  be the map from Z2 to Z4, which
is the usual inclusion from the additive structure in Z2 to Z4 :  (0) = 0,  (1) = 2. This
map can be extended to the map ( ;Id) : Zn2 7! Zn4 , which will also be denoted by  ,
14
(see [8]). That way, using this inclusion map, the binary vectors de ned in (1.4) can be
considered as a quaternary vectors. This is the case in the next example, which is denoted
bySRM(r;m) and de ned as the quaternary code which is generated by the generators of
the binary Reed-Muller code RM(r;m)[6].
The (uju + v)-construction de ned in (1.3) allows one to construct other codes in
QRM(r;m) apart from QRM(r;m) and SRM(r;m):
Theorem 2.4. Let C2QRM(r;m) and D2QRM(r;m). Then, the code C de ned as
f(u;u + v)ju2C;v2D belongs to the class QRM(r + 1;m+ 1):
Theorem 2.5. Let C2QRM(r;m), with 1 r m then
C?2QRM(m r 1;m)
It is useful to characterize codes in theQRM(r;m) class in terms of generator matrices.
If G is a quaternary matrix with row vectors x1;x2:::;xk, then  (G) is de ned as
0
BB
BB
BB
B@
 (x1)
 (x2)
...
 (xk)
1
CC
CC
CC
CA
:
Lemma 2.3.1. [5] Let C2QRM(r;m) and let G be its generator matrix. Then  (C) is a
generator matrix of RM(r;m):
Theorem 2.6. [5] LetCbe a quaternary code of length 2m. Cbelongs to the classQRM(r;m)
if and only if there exist a binary (Pri=0 mi ) 2m matrix N, such that the generator ma-
trix of C is G(r;m) + 2N, where G(r;m) is the generator matrix of RM(r;m) de ned in
Theorem 2.1 above.
Corollary 2.3.1. If C2QRM, then (C=2RM(r;m);+) (RM;+).
15
Any quaternary code with the same parameters as the quaternary Preparata code is
named Preparata-like and its Z4-dual is called Kerdock-like. The following theorem shows
that these codes are members of QRM(r;m):
Theorem 2.7. Let P(2m) be a Z4-linear Preparata-like code, and K(2m) a Z4-linear
Kerdock-like code of length n+ 1 = 22m. P(2m)2QRM and K(2m)2QRM:
16
Chapter 3
Intersection
3.1 Introduction
In this chapter we consider the intersection problem for coding theory  rst introduced
by Etzion and Vardy [13] in the setting of binary perfect codes. Since then, this problem
has been considered for other families of codes such as Hadamard codes and q-ary cyclic
codes whose alphabets are  nite  elds [14], [10], [11] or for families of codes whose alphabet
is the ring of integer modulo 4 [15], [23].
Given two codesC1 andC2 over an alphabet F, we denote the size of their intersection
by  (C1;C2), and call this the intersection number of C1 and C2.
In general the intersection problem can be stated as follows: given a family or class of
families of codes,  nd the spectrum of intersection numbers.
The general strategy to attack this kind of problem begins by  nding necessary con-
ditions for the intersection. This leads to lower and upper bounds or a set of possible
intersection numbers. Secondly,  nding the su cient conditions implies giving speci c con-
structions of codes in such a way that the cardinality of their intersection  ts those values
between these bounds. In this chapter, the alphabet F is the  nite  eld GF(q) of q elements.
3.2 Intersection problem for q-ary linear codes
Let C1 be an [n;k1]-code. Since it is a linear subspace of Fn, it is the kernel of
some linear transformation. Let H1 be the parity-check-matrix of order (n k1)  n.
Similarly, let C2 be an [n;k2]-code, with parity-check-matrix H2 of order (n k2) n. The
intersection C = C1\C2 is also linear, therefore, there is a matrix H =
0
B@ H1
H2
1
CA such
17
that C1\C2 = fx2FnqjHxT = 0g. Notice that, rank(H)  2n (k1 + k2). Now, since
n = dim(C)+rank(H), (k1+k2) n dim(C) and the intersection C1\C2 = qdim(C1\C2) 
q(k1+k2) n. Thus the intersection problem can be stated as follows: Determine the values
v between maxf0;(k1 +k2) ng and minfk1;k2g, such that qv are intersection numbers of
C1 and C2.
A particular case of this problem arises when C2 =  (C1), where  2Sn. In this case
their dimensions are the same, k1 = k2 = k: Therefore both are of the same size and we
look at the values v between 2k n and k.
The intersection problem for this particular case (when the codes are permutation
equivalent) was solved by Bar-Yahalom and Etzion [10] for q-ary cyclic codes. The approach
they used was based on a partition of the columns of the generator matrix of the code into
two sets I(C) and R(C), called the information set and the redundant set, respectively.
R(C) consists of (n k) columns, among which at most t are linearly independent. A code
whose generator matrix presents a partition in which t gets its maximum value is called a
t-redundancy or t-IR, and an independent redundancy or (IR) if t = r. Now if C is an
[n;k] t-IR code for which t k, then the set of t linearly independent columns in R(C) can
be extended by k t columns from I(C) to obtain a set of k linearly independent columns.
This set of k linearly independent columns is called a free set.
The following theorems give an enumeration method for the intersection of linear codes
with the partition of the generated matrix, explained above.
Theorem 3.1. [10] If C is an [n;k] t-IR code, then for each  , 0   t 1, there exists
a permutation   , for which jC\  (C)j= qk  :
Theorem 3.2. [10] Let C be an [n;k] code over F. If 12C then  (C; (C)) 2:
Theorem 3.3. [10] Let C be an [n;k] code over F. There exists  2 Sn, such that
 (C; (C)) = qk1 if and only if there exists  12Sn, such that  (C?; 1(C?)) = qn 2k+k1:
18
Theorem 3.4. [10] Let C be an (n;k) code over F, k n k. If all the codewords have
generalized parity 0, (that is, if the sum of the entries of the codeword is 0) then q2k n is
not an intersection number of C:
Example 3.2.1. Let?s see this enumeration method for the case of the binary Reed-Muller
RM(r;m) code. For 0  r < m, let k = Pmi=0  mi be dimension of this code. Denote by
r = n k the redundancy number associated to the generator matrix of RM(r;m) which
has k linearly independent rows and then k linearly independent columns. Here we have two
cases. The  rst one corresponds to r d(m+ 1)=2e and then k r . Since k of the other
n k columns are linearly independent, then we have a partition where t gets its maximum
value with t = k. The second case corresponds to r>d(m+ 1)=2e, we have that k>n k.
So the maximum partition is obtained with t = r .
If RM(r;m) is an k-IR code, by Theorem 3.1, for each  , in 0    k 1, 2k  is
an intersection number and since 1 2RM(r;m) by Theorem 3.2, 1 is not an intersection
number ( = k). But if RM(r;m) is an (n k)-IR code, for each  in 0   n k 1,
2k  is an intersection number, and since the codewords of any binary Reed-Muller code are
of even weight, the generalized parity is 0 and, by Theorem 3.4, 22k n is not an intersection
number, ( = n k). The permutation that we choose for each  , can be the cycle (1;::; +
1)of length  + 1.
Table 3:1 shows the variation of the interval for  and Table 3:2, is an example that
shows the cycles that act over RM(1;5) in order to get its corresponding isomorphic codes
and then the cardinalities of their intersections.
One interesting family of q-ary linear codes are the so called q-ary Hamming codes.
Given a  nite  eld F, the q-ary Hamming code Hq;r of length n = (qr 1)=(q 1), where
r 2, is de ned by the parity-check matrix whose columns are the points (in some order)
of the projective geometry PG(q 1;r). (A projective geometry PG(q 1;r) is the set
whose elements are the 1-dimensional subspaces of Fr). De ne a q-ary Hamming code by a
parity-check matrix constructed in the following way: From each element in PG(q 1;r),
choose the representatives whose leading nonzero entry is 1. There are 2r 1 points in which
19
R(r;m) k n k t 0   t 1
0;5 1 31 1 a
1;5 6 26 6 0   5
2;5 16 16 16 0   15
3;5 26 6 6 0   5
4;5 31 1 1 a
5;5 32 0 0 a
Table 3.1: RM(r;5)
(1;:: + 1) (1) (1;2) (1;2;3) (1;2;3;4) (1;2;3;4;5) (1;2;3;4;5;6)
26  64 32 16 8 4 2
Table 3.2: jRM(1;5)\ (RM(1;5))j
all its components are 0 and 1. They are the numbers 1;2;3;:::;2r 1 written in binary,
then, place these columns in increasing order from 1 to 2r 1. The rest of the columns can
be placed in any order.
The intersection problem for binary Hamming codes was solved in [22] and for q-ary
Hamming codes, in [11].
Theorem 3.5. [11] For each m 3, there exist two linear q-ary Hamming codes H1, H2
of length N = qm 1q 1 , such that  (H1;H2) = qN l, for l = m+ 1;m+ 2;:::;2m.
3.3 Intersection problem for perfect codes
Let x2F, the sphere of radius r centered at x is de ned by Sr(x) =fy2Fnjd(x;y) 
rg. Given a set S2Fn, the hull of S, denoted by K(S), is de ned by Sx2SSr(x). If in
addition the spheres are disjoint, we say that S perfectly covers K(S) or that S is an r-
error-correcting code. Given a set S which is an r-error correcting code, we say that it is an
r-perfect code provided K(S) = F. In [7] it is shown that the only parameters for nontrivial
perfect codes are the two Golay codes and the q-ary 1-perfect codes where q is a prime or
prime power. So, from now on, q-ary 1-perfect codes will be refereed as q-ary perfect codes.
20
Let C be a Hamming code of length n and x2Fn, then the coset C + x is a perfect
code, but not linear. In 1962, [18] Vasil?ev constructed nonlinear binary perfect codes that
are not cosets of Hamming codes.
For x 2Fn2 , let p(x) = wt(x) (mod 2). Let Cn be a perfect binary code of length
n = 2m 1. Let f : Cn!f0;1g be an arbitrary mapping.
Theorem 3.6. [18] The code C(2n+1;f) =f(xjx+cjp(v)+f(c) : x2Fn2 ;c2Cngis perfect.
If f 0, then C(2n+1;f) is the Hamming code, but if f(0) = 0 and f(c1)+f(c2)6= f(c1+c2)
for some c1;c2;c1 + c2, then C(2n+1;f) is not linear.
As in the case of cosets of Hamming codes, any binary perfect code C of length n
generates a partition of Fn2 into translates Ci = C + xi, where xi is a vector of weight 1,
andjCj=jCijfor all i = 1;2;:::;n. This partition is known as the trivial partition. There
are non-trivial partitions into perfect codes of Fn2 , see for example ([19], [21]).
The following construction of perfect codes of length 2n+1 from perfect codes of length
n is due to Phelps [19] and Solov?eva [20]. Etzion and Vardy [22] refer to their  nding as
construction A and describes it in the next theorem.
Theorem 3.7. CONSTRUCTION A Let En2 denote the set of all the even-weight vectors
in Fn2 . Let C0;C1:::;Cn and C 0, C 1 :::;C n be partitions of Fn2 and En+12 ; into a perfect
code and its translates, respectively, into an extended perfect code and its translates. Let  
be a permutation on the set f0;1;:::;ng. Then the code
CA =f(xjy) : x2Ci; y2C  (i), for some i = 0;:::;ng, where ( j ), denotes concate-
nation, is a perfect code of length 2m+1 1:
Let us discuss the intersection problem for two binary perfect codes C1 and C2 of the
same length n = 2m 1. If c 2C1\C2, then its complement is also in the intersection.
Thus the intersection must have even cardinality, and  (C1;C2) 2. Etzion and Vardy [13],
determined an upper bound for that intersection, which is  (C1;C2)  2n m 2v, where
v = (n 1)=2. Moreover, they constructed two perfect codes C1 and C2 whose intersection
number shows that this upper bound is attainable for all n. The idea of the construction of
21
these codes is as follows. Let Hn a Hamming code of length n = 2v + 1 = 2m 1. Assume
that the columns of its generator matrix, H, h1;h2;:::;hn; are arranged such that for some
 xed column vector z = hn, h1 + hi+v = z for all i = 1;2:::;v. The code C1 is the coset
of Hn such that the syndrome s(c) = Hct is z for all c 2C1. Next, they obtained C2 by
modifying C1 in the following way C2 = (C1nB)[A, where A=fxjxjp(x) : x2Fv2g and
B=A+ e2v+1. Notice, that according TheoremAis a Hamming code of length n given by
Vasil?ev construction. Now,  (C1;C2) = 2n m 2v.
In [22], Etzion and Vardy, using a combination of construction A and the construction
of Vasil?ev, obtained two perfect codes with intersection number equal 2. Thus the spectrum
of intersection numbers, for any two binary perfect codes of the same length, is given by
the following interval
0  (C1;C2) 2n m 2v (3.1)
The following two theorems give intersection numbers in the interval (3.1), but the
results do not cover the entire possible spectrum.
Theorem 3.8. [9] For any two integers k1 and k2 satisfying 1  ki  2(n+1)=2 log(n+1),
i = 1;2, there exist perfect codes C1 and C2 both of length n = 2m 1, m  4, with
intersection number  (C1;C2) = 2k1k2.
Theorem 3.9. [9] For any even integer q in the interval 0  q 2(n+1)=2 log(n+1), there
are two perfect codes C1 and C2 both of length n = 2m 1, m 4, such that  (C1;C2) = q.
3.4 Intersection problem for Hadamard Codes
A Hadamard matrix H of order n is an n n matrix of +1?s and  1?s such that
HH? = nI, where I is the n n identity matrix. It is known that if a Hadamard matrix of
order n exist, then n is 1,2, or a multiple of 4 [7]. Two Hadamard matrices are equivalent if
one can be obtained from the other by permuting rows and/or columns and multiplying rows
22
and columns by 1. The equivalent normalized matrix H0 is gotten from H by multiplying
each row and column by  1, to make the entries of the  rst row and column all +1. The
binary matrix c(H0) is obtained from H0 by replacing each entry equal to 1 with 0 and each
entry equal to -1 with 1. We can consider the rows of this matrix as binary vectors of length
n. The binary (n;2n;n=2)-code consisting of the rows of c(H0) and their complements is
called a (binary) Hadamard code.
In order to get new Hadamard matrices it is useful to introduce the Kronecker product:
If A is a matrix of order m n and B is a matrix of order r s, then A B denotes the
nr ms matrix
0
BB
BB
BB
B@
a11B a12B ::: a1nB
a21B a22B ::: a2nB
... ... ... ...
an1B an2B ::: anmB
1
CC
CC
CC
CA
:
If H1 and H2 are Hadamard matrices of orders n1, n2 respectively, it easy to check that
H1 H2 is a Hadamard matrix. In particular taking the Hadamard matrix S =
0
B@ 1 1
1  1
1
CA,
and starting from a Hadamard Matrix S0 = (1), we obtain by successive Kronecker products
St = St 1 S, a Hadamard matrix of order 2t for any t 0. St is called a Sylvester type
Hadamard matrix. It is known that the binary code obtained from St is the dual of the
extended Hamming code.
The next four matrices are examples of Hadamard matrices of order 1, 2, 4 and 8,
respectively. Each one of the matrices with order 1, 2 and 4 leads to an unique binary
Hadamard code. The matrix of order 8 leads to an unique Hadamard code up to equiva-
lence.
23
[1],
0
B@ 1 1
 1 1
1
CA,
0
BB
BB
BB
B@
1 1 1 1
1 1  1  1
1  1 1  1
1  1  1 1
1
CC
CC
CC
CA
,
0
BB
BB
BB
BB
BB
BB
BB
BB
BB
BB
B@
1 1 1 1 1 1 1 1
1 1  1  1 1 1  1  1
1  1 1  1 1  1 1  1
1 1  1  1 1 1  1  1
1 1 1 1  1  1  1  1
1 1  1  1  1  1 1 1
1  1 1  1  1 1  1 1
1  1  1 1  1 1 1  1
1
CC
CC
CC
CC
CC
CC
CC
CC
CC
CC
CA
:
The spectrum for the intersection numbers is with respect to the length of a Hadamard
code. Due to the fact that a Hadamard code contains each codeword and its complement,
the numbers in the spectrum are even. Thus, for length 8, the only Hadamard code is the
linear code and the intersection problem is settled for this length. The intersection numbers
are I(8) = f0;2;4;8;16g. Nonlinear binary Hadamard codes appears beginning at length
n 16.
Using Hadamard codes from matrices constructed by the product SN[B01;B02] =0
B@ B01 B01
B02  B02
1
CA or its transpose, the next theorem settled the problem for the length 2t
Theorem 3.10. [14] For all t 3 there exist Hadamard codes of length 2t with intersection
number i if and only if i2I(2t) =f0;2;4;:::;2t+1 12;2t+1 8;2t+1g:
the next theorem gives a partial answer to the general case, that is, when a Hadamard
matrix of lenth 4s, where s is an odd number, exists.
Theorem 3.11. [9] For all t 4, if there exists a Hadamard matrix of order 4s, there exists
Hadamard codes of length 2t+2s with intersection number 2i for all 2i2f0;2;4;:::;2t+3s 
12;2t+3s 8;2t+3g= I(2t+2s):
24
3.5 Intersection problem for Quaternary linear codes
The intersection problem for quaternary linear codes has been solved for quaternary
extended linear perfect codes [15] and for quaternary linear Hadamard codes [23].
The characterization of the extended 1-perfect Z4-linear codes, up to equivalence, is
given in [16], so we know that for each length, n = 2t, there are exactlybt+ 1=2cnonequiv-
alent extended 1-perfect Z4 linear codes. Each one of these codes can be given by a parity-
check matrix consisting of all column vectors of the form Z 2  f1 2 Z4g Z  14 , where
t + 1 =  + 2 and Z2 means f0;2g Z4. This parity-check matrix can be seen as the
generator matrix for the corresponding Z4-linear Hadamard code
Theorem 3.12. [16, 17] For each  2f1;:::;b(t + 1)=2cg there exists a unique (up to
isomorphism) extended perfect Z4-linear code C0 of binary length n+ 1 = 2t 16, such that
the Z4-dual code of C0 is of type (0; ; ; ), where  = 2t 1 and  = t+ 1 2 .
In view of this Theorem, we can create the following table:
t  ( ; ; ; )
2 1 (0;2;1;1)
3 1,2 (0;4;2;1), (0;4;0;2)
4 1,2 (0;8;3;1), (0;8;1;2)
5 1,2,3 (0;16;4;1), (0;16;2;2), (0;16;0;3)
6 1,2,3 (0;32;5;1), (0;32;3;2), (0;32;1;3)
... ... ...
Example 3.5.1. In the case of length n+ 1 = 32, there are three non-isomorphic extended
perfect Z4-linear codes, since we have three possible parameters:  = 1,  = 2 and  = 3.
The following matrix is the parity-check matrix of the code C0 =   1(C0) for  = 2 (also
notice that  = 16 and  = 2):
0
BB
BB
B@
0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2
0 0 0 0 2 2 2 2 0 0 0 0 2 2 2 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
1
CC
CC
CA:
25
Theorem 3.13. For any t 3 and any quaternary linear perfect codes C1 and C2 of length
 = 2t 1, not necessary such that their quaternary dual codes contain the all-ones vector,
it is true that
22  2t 1  (C1;C2) 22  t 1:
Moreover, there exist such codes for any possible intersection number between these bounds.
Theorem 3.14. For any t 3 and any two quaternary linear Hadamard codes C1 and C2
of length  = 2t 1, it is true that 2  (C1;C2) 2t+1:
Theorem 3.15. For any t 3 there are two quaternary linear Hadamard codes C1 and C2
of length  = 2t 1, such that  (C1;C2) = 2l, where l is any value from 1 to t+ 1.
The quaternary linear codes have been generalized to the Z2Z4-additive codes. The
intersection problem for these kind of codes is given in [15] and [23].
26
Chapter 4
Intersection Problem for The Class of Quaternary Reed-Muller Codes
This chapter presents results that lead to the solution of the intersection problem for
QRM(r;m). Remember that this class contains the most important families of quaternary
codes such as the quaternary Kerdock-like codes as well the Preparata- like codes. As a
consequence, the solution of the intersection problem for binary codes in QRM(r;m) is
obtained. This class contains the original Kerdock code which is a nonlinear binary code,
but it is the Gray map image of a quaternary linear code (a Kerdock-like code).
Our results generalize those given in [10]. This allows to us to attack the intersection
problem with the same approach used in [10]. As mentioned in Chapter 3, that approach
was based on a partition of the columns of the generator matrix of a [n;k]-code over a  nite
 eld, into two sets, one of them is a set of k linearly independent columns and the other
is a set of n k columns from which t columns are linearly independent. This partition
is given in such a way that t gets its maximum value. In this case, the code is called a
t-independence redundance (t-IR) code, and independent redundancy (IR) code if t = r:
Remember,  is the (mod 2) map. Now, we introduce another map,  :f0;2g!Z2,
which is de ned by  (0) = 0, and  (2) = 1.  is an isomorphism of groups and the extension
 :f0;2gn!Zn2 is also an isomorphism of groups.
Theorem 4.1. [1] LetC be a quaternary linear code of type 4 2 and length n, with generator
matrix G given by (1.5). Then, the binary residue code,  (C) = f (c)jc 2Cg is a binary
linear [n; ]-code with generator matrix
 
I A  (B)
 
;
and the Torsion code, Tor(C) = f (c)jc 2C; (c) = 0g is a binary linear [n; +  ]-code
with generator matrix
27
0
B@ I A  (B)
0 I C
1
CA:
Any quaternary linear code is equivalent to a code whose generator matrix is of form
(1.5), with the additional condition that a partition of the columns into two sets, leads to
the corresponding generator matrix of the binary residue code and presents a partition of
its columns as speci ed in [10].
Let C be a quaternary linear code of type 4 2 and length n, with generator matrix G
given by (1.5). Let  (C) = C, and denote by I(C) the set of columns of G whose positions
correspond to the columns of  (G) which are in I(C). Similarly, denote by R(C), the set of
columns of G, whose positions correspond to the columns of  (G) which are in R(C). We
say that C is called a t-redundancy t-IR code, or redundancy (IR) code, respectively, if C
is. In the same way, a set of columns of G is a free set if this set leads to a free set in the
columns of  (G).
Theorem 4.2. [10] If C is an [n;k]-code and T is a set of linearly independent columns in
its generator matrix, jTj= t, then in C each t-tuple appears in the columns of T exactly in
jCj=2t codewords.
Theorem 4.2 is de ned for linear codes over  nite  elds. The next theorem shows a
similar result for codes de ned over the ring Z4, which is not a  eld. This result allows us
to adopt the approach from [10].
Theorem 4.3. Let C be a quaternary linear code of type 4 2 . Let G be a generator matrix
ofC and denote by  (G) the generator matrix of  (C). If T is a set of t linearly independent
columns of  (G), then each t-tuple in the corresponding columns of G appears exactly in jCj4t
codewords of C
Proof. Let C be a quaternary linear code of type 4 2 . By Theorem 4.1  (C) is a binary-
[n; ]-code with generator matrix  (G), where G is of the form given by (1.5). In addition,
since  : C !  (C) is a surjective homomorphism, then CKer( )   (C). Notice that
28
2C Ker( )  C and 2C is of type 402 and Ker( ) of type 402 + . Moreover, given a
codeword c 2C, then 2C+ c  Ker( ) + c, each class Ker( ) + c can be divided by 2 
classes of C2C each having the same cardinality.
Let J =fi1;i2;:::;itg [n] be a set of indices that label a set of t linearly independent
columns of  (G). Let c = (c1;c2;:::;cn) be a codeword inC, and cjJ = (ci1;ci2;:::;cit) be
the projection of the codeword c on the set J. Since  (c) =  c = (  c1;  c2;:::;  cn)2 (C),  (c)
is associated to a unique class Ker( ) + c. By Theorem 4.2 (  ci1;  ci2;:::;  cit) appears in
exactly 2 2t codewords of  (C). Denote these codewords by di where i = 1;:::; 2 2t , and they
are such that their projection to J is dijJ = (  ci1;  ci2;:::;  cit). For some i, di =  (c).
Now, notice that (i1;:::;it) label t linearly independent columns of the generator ma-
trix of Tor(C). So if h2Tor(C), then by Theorem 4.2 hjJ = (hi1;hi2;:::;hit) will appear
in 2 + 2t codewords of Tor(C). Since Tor(C) = Ker( ) and  is an isomorphism, the t-tuple
(2hi1;2hi2;:::;2hit) will appear in 2 + 2t codewords of Ker( ). But Ker( ) is the union of
2 classes of C2C that means, given any of such classes it contains 2 2t codewords whose pro-
jection is the t-tuple (2hi1;2hi2;:::;2hit). In particular this is true for the vector all zeros,
0 = (0;. . .;0), since 022C Ker( ). That way, Ker( ) + c will have 2 classes each one
having 2 2t codewords with the same vector projection cjJ. Now repeat the same argument
for the remaining 2 2t  1 di codeword of C. They give the same number of codewords with
projection cjJ that was obtained by di. That way, the total number is 2 2t 2 2 2t and this
proves the theorem.
Let x = (x1;:::;xn)2Zn4 and J =fi1;:::;ijg [n]. Let  be a permutation de ned
onJ and s be an inversion of coordinates with associated subsetS J, and s a monomial
map. De ne the function ? s : Zn4 !Zn4 as ? s (h) = h  s( (h)). Notice that ? is an
homomorphism of groups. When C Zn4 is a quaternary linear code, ?  will be helpful
in determining those codewords that are in the intersection of C and  s( (C)): So, in the
following de nition we give a special name to the set ? s (Zn4); which re ects this fact.
29
De nition 4.0.1. Let  s be a monomial map. The index of  s is the set X s = fx2
Zn4 :9h2Zn4 : ? s (h) = xg. If x2X  , then x is called the index of h, with respect   ,
and we will write x = h  , and we say that h is attached to the index x.
Remark 4.0.1. Let h = (h1;h2;:::;hn)2Zn4. Let?s examine the index of h projected on the
coordinates determinated by a cycle  of the permutation  , and the inversion of coordinates
 . Without loss of generality, we can assume that  = (1;2:::;?):
The projection of h to the coordinates labeled by  is given by hj = (h1;:::;h?), and
 (hj ) = ( h1;:::; h?), where we choose ( ) if  multiplies the corresponding coordinate
by  1. In other words, by doing a selection of signs in the components of hj , we are deter-
mining implicitly the set S associated to  s. Thus, we have  ( (hj )) = ( h2;:::; h?; h1)
and xj = hj   ( (hj )) = (x1;:::;x?) where:
x2 = h1 h2
x3 = h2 h3
... = ... ... ... (4.1)
x? = h? 1 h?
x1 = h? h1:
Theorem 4.4. Let  s a monomial map as in the remark, then x2X s if and only if
1. For every cycle (1;:::;?) in  , the vector xj = (x1;:::;x?), satis es P?i=1xi = 0
(mod 2)
2. For every s2[n] which is not a label of a coordinate of xj , xs = 0:
Proof. 1. If x 2 X  , then there exists h 2 Zn4 such that h   (h) = x. Let  =
(v?p;1; v?p;2:::v?p;?) be a cycle of  . Then, all possible cases for  with respect to hj =
(h1; h2; :::;hj; :::;h?), are given, by (4.1) and the projection xj satis es the following
30
relation
?X
i=1
xi =
? 1X
i=1
(hi hi+1) +h? h1 =
?X
i=1
hi 
?X
i=1
hi = 0 (mod 2)
2. This follows directly by de nition 4.0.1.
Conversely, assume that there exist a vector x 2Zn4 that satis es 1) and 2): We are
going to show that there is a vector h2Zn4 such that x = h ( ). Following [10], the values
of hs for s satisfying condition 2) may be chosen arbitrarily. For a cycle  = (1;2;:::;?),
in  , select an arbitrary value for h1. Notice that if  multiply by  1 the  rst coordinate,
then we had chosen h1. As we did before, we are going to use the notation h1 to express
this fact. Now, proceed by the formula
8j; 2 j ?;  hj = hj 1 xj:
Since, P?i=1xi = 0 (mod 2), it follows that  h1 = h? x?:
From these formulae we have that for all i, 1 i n, xi = hi h  (i), or by de nition
of index set, x = h  (i):
Lemma 4.0.1. 1. Let h2Zn4. If  is an inversion of an odd number of coordinates in
a cycle  of  , then the initial choice of h1 in hj is restricted to two elements in the
set f0;1;2;3g:
2. If  is an inversion of an even number of coordinates in a cycle  of  , then initial
choice of h1 in hj can be made in four ways from the set f0;1;2;3g:
Proof. Let h = (h1;h2;:::;hn) be a word in Zn4,  2Sn and  = (1;:::;?), a cycle of length
? in the decomposition of  , and take a subset S =fi1;:::;ikgof [?] where k ?: Consider
xj = hj   ( (hj )), where  =  s. By Theorem 4.4,
?X
i=1
xi = 0 (mod 2). Assume that
x = h ( ) = 0, then P?i=1xi = 0 (mod 4). From the system (4.1), we get:
31
?X
i=1
xi =
X
i2[?]nS
xi +
X
i2S
xi = 2hi1 +   + 2hik =  2h1 +    2h1 = 0 . Now it is easy to
see that if k is odd, h12f0;2g and if k is even, h12f0;1;2;3g. Moreover, if k is odd and
h1 = 0 then, hj = ( 0;:::;0| {z }
?times
), but if h1 = 2, then hj = ( 2;:::;2| {z }
?times
): If k is even and either
h1 = 0 or 2, hj is exactly as in the previous case. Now if h1 = 1, then hj = ( 1;3;:::;3;1| {z }
?times
)
but if h1 = 3, then hj = ( 3;1;:::;1;3| {z }
?times
)
Since ? s is a surjective homomorphism from Zn4 to ? s (Zn4), it is true that Zn4Ker(? 
s )
 
? s (Zn4). Thus, to each index we can associate a unique equivalence class in Zn4Ker(? 
s )
.
Notice that Ker(? s ) is the set of vectors attached to the index zero. Now, assume that
x = h  6= 0, then its associated class is Ker(? s ) + h. For all u 2 Ker(? s ) + h,
consider the following two cases, if  s inverts an odd number of coordinates, then uj =
(h1;h2;:::;h?) or uj = (h1 + 2;h2 + 2;:::;h? + 2). For the set of vectors attached to the
index x = h ( ), the initial choice of h1 can be done only in two ways. Now, assume that
 s performs an even number of coordinates. In this case, if h1 = 0 or h1 = 2, uj is like the
previous case. If h1 = 1, then uj = (h1 + 1;h2 + 3;:::;h? 1 + 1;h? + 3), but if h1 = 3 then
uj = (h1 + 3;h2 + 1;:::;h? 1 + 3;h? + 1). Thus, in this case, also we can choose h1 in four
ways.
Lemma 4.0.2. If C is quaternary linear code of type 4 2 , and   is a monomial map,
then  ( (h))2C\ ( (C)) if and only if h  2C:
Proof. h  ( (h))2C if and only if  ( (h))2C if and only if  ( (h))2C\ ( (C))
Lemma 4.0.3. Let C be a quaternary linear code of type 4 2 , and D be an equivalent code
to C. If   is a monomial map, then  (C; ( (C))) =  (D; ( (D))) and both intersections
are of the same type.
Proof. Since C and D are equivalent, they are isomorphic as abelian groups. Then, they
are of the same type. Since, C\ ( (C)) and D\ ( (D)) are subgroups of C, and D,
32
respectively, the image of restriction of the isomorphism to C\ ( (C)) is D\ ( (D)).
Thus, the conclusion of the lemma follows.
Lemma 4.0.4. Let C be a quaternary linear code of type 4 2 ,
1. Let   be a monomial map,  > 0, 12C, then  (C; ( (C))) 2
2. Let  be a permutation,  = 0,  > 0, 22C,  (C; ( (C))) 2.
Proof. 1. If 1 2C, then 1 2 (C) and the intersection has at least 4 elements. Now,
 ( (C)) leave invariant codewords of order 2. So the intersection at least is 2.
2. If 22C, then 22 (C) and the intersection has at least 2 elements.
Theorem 4.5. Let C a quaternary linear code of type 4 2 . Assume that C = C1LC2,
where C1 is of type 4 20, C2 is of type 402 and L represents the direct sum. Assume
that C\ ( (C)) is of type 4 12 1, where 1   1 <  , 1   1 <  , and   is a monomial
map. Then, C1\ ( (C1)) is of type 4 120, C2\ ( (C2)) is of type 402 1 and C\ ( (C)) =
C1\ ( (C1))LC2\ ( (C2)):
For a vector x = (x1;:::;xn) 2 Zn4, the generalized parity of x, gp(x), is de ned as
gp(x) = Pni=1xi (mod 2): Let C be a a quaternary linear code of type 4 2 . Let G be a
generator matrix given by 1.5. Let  a permutation of columns of a free set of G, and let S
be a set of labels of columns of a free set of G, then,  ( ) is called a free monomial map.
Theorem 4.6. Let C be a t-IR quaternary linear code of type 4 2 .
1. Let  be a free permutation with respect to C. Then, every word is attached to one
index only, and every index x2C\X has exactly 2 4   ( )+ ( ) codewords attached
to it and  (C; (C)) =jC\X j2 4   ( )+ ( ):
2. Let   a free monomial map with respect to C. Then, every word is attached to one
index only, and each index in C\X  has exactly 2 ( )o 4 ( )e 4   ( ) codewords
attached to it and  (C; ( (C))) =jC\X  j2 ( )o 4 ( )e 4   ( )
33
Proof. 1. Let x 2X \C. Then there exists h 2C such that h  (h) = x. Let  be
a cyclic in  . For any choice of h1, the vector projection hj is uniquely determined.
Since h12f0;1;2;3g, we have four di erent hj vectors. Since  was taken arbitrarily
in  , it follows that the number of di erent vectors hj each one of length  ( ) is 4 ( ),
By Theorem 4.3, there are 2 4 4 ( ) codeword inC, for each hj . So there are attached to
x, 4 ( ) 2 4 4 ( ) = 4 + ( )  ( ) codewords. Since any index in X has exactly the same
number of attached codewords, it follows that  (C; (C)) =jC\X j2 4   ( )+ ( ):
2. Let  be a cycle of length ? in the decomposition of the free permutation  . Consider
the vector h and its projection hj . Let  be a map which produce an inversion on
an odd number of coordinates of hj . Assume that h is attached to the index 0. By
lemma 4.0.1, for each initial choice of h1, hj is uniquely determined, but we have
only two choices possible: 0 and 2. Thus there exist only two di erent vectors hj .
Let  ( )o be the number of cycles which corresponding projections present an odd
number of coordinates with inversions. So, we have 2 ( )o distinct projections of h on
those cycles. Moreover, if  had cycles with an even number of inversions (including
cycles without inversions), by lemma 4.0.1 we will have 4 ( )e di erent projections of
h on those cycles, where  ( )e denotes the number of cycles of  in which is realized
an even number of inversions. In this way we have 2 ( )o4 ( )e di erent codewords
each one with  ( ) coordinates. Since  is a free permutation, it follows that for each
hj , there are 2 4 4 ( ) codewords. Thus, the index 0 has 2 ( )o4 ( )e 4   ( )codewords
attached to it. Since any index in X  has exactly the same number of attached words,
it follows that  (C; ( (C))) =jC\X  j2 ( )o 4 ( )e 2  4   ( ):
Theorem 4.7. Let C be a quaternary linear t-IR code of type 4 20 . There exists a subset
A f0;1;2;:::;t 1g f0;1;2;:::;tg such that for all (?;j)2A there is a permutation  
34
and a set Sj associated to a monomial map  sj such that
 (C; sj( (C))) =
8>
>>>>
>>>>
><
>>>>
>>>>
>>:
4  ?; if 1 ? t 1, j = 0;
214  ? 1; if 1 ? t 1, j = 1;
2j ? 14  (j 1); if ? is odd, ?+ 1 <j t;
2j ?4  j; if ? is even, ?+ 1 <j t;
2j4  j; if ? = 0, j2f0;1;:::;tg.
Proof. Let C be a quaternary linear t-IR code of length n, and type 4 20. Let G be a
generator matrix with the columns of R(C) placed  rst, followed by the  columns of the
information set I(C). Let 1 <? t 1. In order to de ne the permutation  and the set S
associated to  s, we distinguish two cases a) 0 j ?+ 1 and b) ?+ 1 <j t 1. Let?s
us discuss each case separately.
a) 0 j ?+ 1: De ne  = (1;2:::;?+ 1) a permutation consisting of one cycle, and for
j = 0, de ne S0 = f0g , and  so = Id. So  ( ) = 1,  ( ) = ? + 1 and by Theorem 4.6,
 (C; (C)) = 4  ?.
For j = 1, de ne S1 = f1g, then  ( )o = 1,  ( )e = 0;  ( ) = ? + 1. Thus,
 (C; s1( (C))) = 214  ? 1. Notice that the  rst new intersection number appears at j = 1
. For j > 1, the intersection numbers are alternating between 214  ? 1 and 4  ?:
b) ? + 1 < j  t. If ? is odd, new intersection numbers appears when j  ? + 3, so we
require ?+3 n  . Consider the permutation  j = (1;2;:::;?+1)(?+2) js=?+3(s), where
Sj = f1;:::;jg is the set associated to the monomial map  sj. Thus,  ( j)o = j ? 1,
 ( j)e = 1 ,  ( j) = j. Thus,  (C; sj( (C))) =jC\X s jj2j 14  j 1:
If ? is even, the new intersection numbers appears when j ?+2, so we require ?+2 <
n  . Consider the permutation  j = (1;2;:::;?+ 1) js=?+2(s), where Sj = f1;:::;jg is
the set associated to the monomial map  sj. Thus,  ( j)o = j ? 1+1 = j ?,  ( j)e = 0,
 ( j) = j. Thus,  (C; sj( (C))) =jC\X s jj4  j2j ?:
Now, considering each element in the set Sj = f1;:::;jg, 1  j t 1, as a permu-
tation consisting of a cycle of length 1, one can write  = (1):::;(j). Thus, there are, j
35
cycles of length 1. This implies  ( )o = j,  ( )e = 0,  ( ) = j. Thus, by Theorem 4.6
 (C; sj( (C))) =jC\X sj j2j4  j:
Now we are going to prove that for each one of these cases, C\X  =f0g. That is,
the vector of all zeros is the unique codeword that is also an index. Let c2C\X  which in
terms of its components can be written as c = (b1;:::;bn   1;a1;:::;a ), where bi denotes
the parity-check symbols or the labels of the columns of R(C), and ai are the information
symbols or the labels of the columns of I(C). Also, ai = bn  +1, i2f1;:::; g. By de nition
of the index set, a1 = ::: = a = 0 . Since bi =
 X
j=1
cijaj, aj 2Z4, it follows that bi = 0 ,
for all i2f1;:::;n  g: Thus c = 0:
Example 4.0.2. Let C a quaternary linear code of type 4620 whose generator matrix is
given by
G =
0
BB
BB
BB
BB
BB
BB
BB
@
1 0 0 0 0 0 2 1 3 2 0 0
0 1 0 0 0 0 1 2 3 1 1 1
0 0 1 0 0 0 0 3 0 3 3 0
0 0 0 1 0 0 0 1 0 1 1 3
0 0 0 0 1 0 0 2 3 2 0 0
0 0 0 0 0 1 3 3 1 1 2 0
1
CC
CC
CC
CC
CC
CC
CC
A
Since the dimension of  (G)  = 6, I(C) is the set of columns 1,2,3,4,5,6. R(C) is the set
of columns 7,8,9,10,11,12. Notice that in this set, all the columns are linearly independent.
Thus t =  = 6. Now A is subset of f0;1;:::;5g f0;1;:::;6g. In order to get the
monomial maps, we proceed as in the theorem, placing the columns of R(C)  rst, and second
the columns of I(C).
a 1 ? 5, 0 j ?+ 1. If j = 0, we have the following table:
36
(?;j) (1;:::;?+ 1) Sj 46 ?
(1;0) (1;2) f0g 45
(2;0) (1;2;3) f0g 44
(3;0) (1;2;3;4) f0;g 43
(4;0) (1;2;3;4;5) f0g 42
(5;0) (1;2;3;4;5;6) f0g 41
If j = 1, we have the following table
(?;j) (1;:::;?+ 1) S1 2146 ? 1
(1;1) (1;2) f1g 2144
(2;1) (1;2;3) f1g 2143
(3;1) (1;2;3;4) f1g 2142
(4;1) (1;2;3;4;5) f1g 241
(5;1) (1;2;3;4;5;6) f1g 2140
b 1 ? 5, ? odd, ? + 1 j 6. New intersection numbers appears when j ? + 3.
Also, we require that ?+3 6. Thus ?2f1;3g. This implies that if ? = 1, then j2f4;5;6g,
but if ? = 3, then j2f6g,
(?;j)  j = (1;2;:::;?+ 1)(?+ 2) js=?+3(s) Sj 2j ? 146 (j 1)
(1;4)  4 = (1;2)(3)(4) f1;2;3;4g 2243
(1;5)  5 = (1;2)(3)(4)(5) f1;2;3;4;5g 2342
(1;6)  6 = (1;2)(3)(4)(5)(6) f1;2;3;4;5;6g 2441
(?;j) (1;:::;?+ 1) S6 2j ? 1)46 (? 1)
(3;6) (1;2;3;4)(5)(6) f1;2;3;4;5;6g 2241
If ? is even, ? + 1  j  6. New intersection numbers appears when j  ? + 2. Also, we
require that ?+ 2 6. Thus ?2f2;4g. This implies that if ? = 2, then j2f4;5;6g, but if
? = 4, then j2f6g,
37
(?;j)  j = (1;2:::;?+ 1) js=?+2(s) Sj 2j ?46 (  j)
(1;4)  4 = (1;2)(3)(4) f1;2;3;4g 2242
(1;5)  5 = (1;2)(3)(4)(5) f1;2;3;4;5g 2341
(1;6)  6 = (1;2)(3)(4)(5)(6) f1;2;3;4;5;6g 2440
(?;j) (1;:::;?+ 1) S6 2j ?)46 (  j)
(3;6) (1;2;3;4)(5)(6) f1;2;3;4;5;6g 2240
(c) ? = 0 and j2f0;1;:::;tg
(?;j) (1;:::;?+ 1) Sj 2j4  j
(0;0) (1) f0g 4620
(0;1) (1) f0;1g 4521
(0;2) (1) f0;1;2g 4422
(0;3) (1) f0;1;2;3g 4323
(0;4) (1) f0;1;2;3;4g 4224
(0;5) (1) f0;1;2;3;4;5g 4125
(0;6) (1) f0;1;2;3;4;5;6g 4026
Theorem 4.8. Let C be a t-IR quaternary linear code of type 4 2 . Then, 2t ?4  t, where
? is odd and 1 ?<t 1,is an intersection number.
Proof. By the previous Theorem, it is easy to see that for ? odd, 2t ?4  t is a number
which does not come by the conclusion of the theorem. Let (1;2;:::;? + 1) be cycle of
length ? + 1. Let S = f2;:::;tg and consider  s. That is, this is an inversion of all
coordinates determined by the cycle, except the  rst one plus the inversion of the following
t (?+ 1) coordinates. Since the cycle has now an odd number of inversions, it follows that
 ( )o = 1 + t ? 1 = t ?,  ( )e = 0,  ( ) = t. Since all these coordinates, correspond
to columns of a free set, it follows that the number of codewords attached to any index is
2t ?4  t= and  (C; ( (C)) =jC\X s j2t ?4  t. Since coordinates from t+1 to n belong to
columns of I(C) and are zeros from any vector in X s , it follows that the unique codeword
in this set is the codeword all zeros. Now the conclusion follows.
38
Example 4.0.3. We continue with the code given in the previous example. That code
satis es the hypothesis of the theorem. ? 2 f1;3g, t = 6 =  . So, 4025 and 4023 are
new intersection numbers. The permutation for the  rst number is  = (1;2)(3)(4)(5) and
S = S6nf1g is the set of  s. For the second number,  = (1;2;3)(4)(5)(6) and the set S is
like the  rst intersection number.
Theorem 4.9. Let C be t-IR quaternary linear code of type 4 . The expression of the
intersection numbers computed in theorem 4.7, gives also the type, of the intersection.
Proof. Case 1:  (C; sj( (C))) = 4  ?, if, 1 ? t 1, j = 0.
CLAIM. The quaternary linear codeC\ s( (C)) constructed in the proof of Theorem
4.7 can be expressed as a direct sum of   ? cyclic subgroups of order 4.
In this case S0 =f0gand  0 = Id, this means that there is no inversion of coordinates
of the code C. Thus, the permutation is the cycle  = (1;:::;? + 1), and we are going to
write  instead of  s . We prove the claim by showing that does not exist in the intersection
a codeword of order 2 which is not the sum of one codeword in the intersection of order
4 with itself. By Theorem 4.7 we know that C\X = f 0g. Thus the index zero has
attached 4  ? codewords. By lemma 4.4 these are all the codewords in the intersection.
In other words, h 2 C\ (C) if and only if h = 0. The projection hj satis es the
system (4.1) and by lemma 4.0.1 for each choice of h1 we have 4 possibilities, 0, 1, 2 and
3. Thus, if h2C\ (C), either hj = ( 0;:::;0| {z }
?+1
) or hj = ( 1;:::;1| {z }
?+1
) or hj = ( 2;:::;2| {z }
?+1
) or
hj = ( 3;:::;3| {z }
?+1
). In this way, C\ (C) can be expressed as the union of four disjoint sets
(another way to see that the four sets above are disjoint consists of noticing that the relation
de ned in the intersection, h1  h2 if and only if h1j = h2j is the equivalence). Denote
these sets by [( 0;:::;0| {z }
?+1
)], [( 1;:::;1| {z }
?+1
)], [( 2;:::;2| {z }
?+1
)] and [( 3;:::;3| {z }
?+1
)]. It is clear that these sets
are de ned by [(a;:::;a| {z }
?+1
)] =fh2C\ (C) : hj = (a;:::;a| {z }
?+1
)g. Observe that [( 0;:::;0| {z }
?+1
)] is
a subgroup of C\ (C) and the other are its cosets. Since the intersection is a  nite group,
each coset has the same cardinality. Notice, that the cosets that contain a codeword of
39
order two are [( 2;:::;2| {z }
?+1
)] and [( 0;:::;0| {z }
?+1
)] whereas the cosets that contain only codewords
of order four are [( 1;:::;1| {z }
?+1
)] and [( 3;:::;3| {z }
?+1
)]. Moreover, using the fact that C\ (C) is
an additive group fh + h : h 2 [( 1;:::;1| {z }
?+1
)]g = fh + h : h 2 [( 3;:::;3| {z }
?+1
)]g = [( 2;:::;2| {z }
?+1
)];
fh1 + h2 : h12[( 1;:::;1| {z }
?+1
)];h22[( 3;:::;3| {z }
?+1
)]g= [( 0;:::;0| {z }
?+1
)]:
That means, that any element of order two, is obtained by adding a codeword of order
four by itself or is obtained by adding to di erent codeword the order 4 in the intersection.
Thus, the type of the intersection is 4  ?.
Now, let us consider is the generator matrix of this intersection. Take h2[( 1;:::;1| {z }
?+1
)].
Then 2h2[( 2;:::;2| {z }
?+1
)] and 3h2[( 3;:::;3| {z }
?+1
)]. Thus, the intersection can be obtained as a
direct sum of the subgroup generated by h and the coset [( 0;:::;0| {z }
?+1
)]. Since the the type
of the intersection is 4  ?, the type of [( 0;:::;0| {z }
?+1
)] should be 4  ? 1, otherwise we will have
a contradiction with the Fundamental Theorem of Abelian groups. Now, choose   ? 1
codewords of [( 0;:::;0| {z }
?+1
)] of the form c?+1+i = ( 0;:::;0| {z }
?+1
0;:::;1;0:::;0| {z }
t ?+1
;ct+1:::;cn), where
1  i   ? 1, and ? + 1 + i indicates the position in which is placed the number 1.
Now the generator matrix is obtained in the following way, place the codeword h, as the
 rst row of the matrix and then, place the   ? 1 codewords c?+i as the last rows of the
matrix.
Case 2:  (C; sj( (C))) = 214  ? 1 if 1 ? t 1, j = 1.
CLAIM: The quaternary linear code C\ s1 (C), constructed in the proof of Theorem
4.7 can be expressed as a direct sum of   ? 1 cyclic subgroups of order 4 and 1 cyclic
subgroup of order 2.
If in the generator matrix constructed in case 1, we multiply by -1, the  rst coordinate
of each row, we see that  1, change the  rst coordinate of the codeword h, which is in the
 rst row. The last   ? 1 rows are invariant since their  rst coordinate is 0. < h > is
a cyclic subgroup of order 4 generated by h, and <  1(h) > is a cyclic subgroup of order
4 generated by  1(h), and < h >\<  1(h) >= f0;2hg: This means that in the cyclic
40
subgroup generated by h, the codewords of order two are invariant. Thus, the generator
matrix for C\ s1 (C) is obtained by the generator matrix of C\ (C) by multiplying the
 rst row by 2.
Case 3:  (C; sj( (C))) = 2j ?4  j if ? is even ?+ 1 j t, j = 1.
CLAIM: The quaternary linear codeC\ sj( j(C)), constructed in the proof of Theorem
4.7 can be expressed as a direct sum of   j cyclic subgroups of order 4 and j ? cyclic
subgroups of order 2.
For S?+1, with ? even,C\ s?+1( (C)) is of type 214  ? 1 and the generator matrix has in
the  rst row 2h, where h2[( 1;:::;1| {z }
?+1
)], and the last   ? 1 are occupied for codewords
in [( 0;:::;0| {z }
?+1
)] Now, consider S?+2 and the permutation  ?+2 = (1;2:::;? + 1)(? + 2).
Notice that in the generator matrix of C\ s?+1( (C)), the second row is given by c?+2 =
( 0;:::;0| {z }
?+1
1;:::;0;0:::;0| {z }
t ?+1
;ct+1:::;cn), but the other rows have 0 in that component, as a
result, the new generator matrix is obtained by only multiplying by 2, the codeword c?+2.
Assume j = ? + 1 + i and consider the permutation  ?+1+i = (1;2:::;? + 1) ?+1+is=?+2(s).
The generator matrix ofC\ s?+i 1( ?+i 1(C)) has the  rst row is occupied by 2h, the next
?+i 1 rows by 2c?+i 1 and the last   (?+i) by codewords of order four that belong to
[( 0;:::;0| {z }
?+1
)] . In this matrix, the row c?+i = c?+2 = ( 0;:::;0| {z }
?+i
1;:::;0;0:::;0| {z }
t ?+1
;ct+1:::;cn)
is the unique codeword that has 1 in the coordinate ? + i. So, after the application of the
monomial map, the new generator matrix is obtained by multiplying this codeword by 2.
Thus, we have i + 1 codewords of order two and   (? + i + 1) codewords of order four.
Since j = ?+ 1 +i, then j ? = 1 +i and the conclusion of the claim follows.
Case 4:  (C; sj( (C))) = 2j ? 14  (j 1), if ? is odd, ?+ 1 <j t 1
CLAIM: The quaternary linear codeC\ sj( (C)), constructed in the proof of Theorem
4.7 can be expressed as a direct sum of   (j 1) cyclic subgroups of order 4 and j ? 1
cyclic subgroups of order 2.
We omit the proof of this case since is similar to the previous case.
Case 5:  (C; sj( (C))) = 2j4  j if ? = 0, j2f0;1;:::;tg.
41
CLAIM: The quaternary linear codeC\ sj( (C)), constructed in the proof of Theorem
4.7 can be expressed as a direct sum of   j cyclic subgroups of order 4 and j cyclic
subgroups of order 2.
In this case Sj = f1;:::;tg and since ? = 0 there is no permutation, so we just write
 sj(C) instead of a  sj( (C)). Put the generator matrix ofC in the form G = (I jA). Denote
by G0 the generator matrix of  sj(C). G0 di ers fromG, in the j  rst rows, and coincide in
the last   j rows. Since each row of G is a codeword of order 4, these   j rows of G0 are
of order 4. Notice that, for 1 i j,  sj, multiplies by  1, the i-th coordinate of the i-th
row of G. Seeing the code as a  nite direct sum of cyclic subgroups, the rows of G are the
generators of cyclic groups of order 4 in that direct sum  sj, changes the j-th coordinate in
each of the 4 codewords that correspond to the cyclic subgroup generated by the j-th row.
But in this subgroup we know that only two codewords in the j-th coordinate, have 0 or
2, which mean these codewords remains after the inversion of that coordinate. As a result
we have thatC\ sj( (C)) is expressed as a direct sum of 4  j subgroups of order 4 and 2j
subgroups of order 2:
Theorem 4.10. [15] Let C1, C2, be two quaternary linear codes. Then,
hC?1 ;C?2i = (C1\C2)? (4.2)
Theorem 4.10 allows one to see the parity-check matrix of the intersection of two
quaternary linear codes C1, C2, similar to the case of linear codes de ned over  nite  elds.
That is, if H1 and H2 are the respective parity-check matrices, then,
H =
0
B@ H1
H2
1
CA: (4.3)
is the parity matrix of the intersection.
42
Suppose that the type of C1\C2 is 4 2 , by Theorem 4.10 and 1.8, H will have n k1
rows that  rows that are vectors of order 4 plus  rows that are vectors of order 2, where
k1 is the number of rows in the generator matrix of C1\C2.
Theorem 4.11. LetC be a quaternary linear code of type 4 20 then k1 is the Pseudodimen-
sion of C\ s( (C)), if and only if n 2 +k1 is the Pseudodimension of C?\ s( (C?))
Proof. Let G be a generator matrix of C, given by (1.5). Let H and  s( (H)) be parity-
check matrices of both,C and  s (C) . Let H1 = (Hk s( (H))), the parity-check matrix of
C\ s( (C)). The Pseudo-dimension of this matrix is n k1 then n k1 = k2 +2(n   k2)
and hence k2 = n 2 + k1. Similarly, if k2 = n 2 + k1 is the Pseudodimension of
C?\ s( (C?)), then n 2(n k) +k2 = k1:
Corollary 4.0.1. Let C be a quaternary linear t-IR code of type 4 20,   n  , gp(x) = 0,
for all x2C, then 2  n is not pseudo-dimension of the intersection.
Proof. By contradiction, suppose that the pseudo-dimension of the intersection is 2  n,
then by Theorem 4.11 the only possible intersection of C? with any of its equivalent codes
is 1. Since the vector 1 2C?, Theorem 4.0.4 say that the intersection should be at least
2.
Theorem 4.12. Let C be an (n;k) t-IR code and G its generator matrix, where I(C) =
fn k+ 1;n k+ 2;:::;ng, columns 1;2;:::;t;n k+ 1 are linearly independent, the  rst
row of G doesn?t have generalized parity 0, and the last k 1 entries in this row are zeroes.
Then there exists a permutation  such that  (C; (C)) = 2k t:
Due to the fact that  :f0;2gn!Zn2 is an isomorphism, any quaternary linear code of
type 2 can be identi ed as an binary code of dimension  . Thus, the theorem 4.12 above,
can be applied if we want to compute intersection numbers of codes of that type.
When the quaternary code is of type 4 , a slightly modi cation of the statement in
Theorem 4.12 gives the following result
43
Theorem 4.13. Let C be an (n; ) t-IR code and G its generator matrix, where I(C) =
fn  + 1;n  + 2;:::;ng, columns in  (G) 1;2;:::;t;n  + 1 are linearly independent,
the  rst row of G doesn?t have generalized parity 0 or 2 and the last   1 entries in this
row are zeroes. Then there exists a permutation  such that  (C; (C)) = 4  t:
4.1 Application to QRM(r;m)
In this section we are going to apply the results of the previous section to the class
QRM(r;m). First of all, we need to establish the possible spectrum of the intersection of
two codes in this class.
Let r 1, Let C1 2QRM(r;m) of type (0; 1;n), then C2 =  ( (C1)) 2QRM(r;m)
and has the same type same type (0; 1;n) then by proposition 3:6:2hC1;C2iis a quaternary
linear code of type code of type ( ; ;n) where
 2 f 1;:::;min(2 1;n)g (4.4)
and
max( ; 1)   +  min(2 1;n) (4.5)
By 3.6.1
 (C1;C2) = jC1\C2j= 4
2  1
jhC1;C2ij (4.6)
If we choose 2 1 < n, in (4:0:1) then  2f 1;:::;2 1g, and  1   +   2 1 If we select
 = 0 and  = 2 1, we obtain the maximum lower bound  (C1;C2) 1 .
If 2 1 > n, then  2f 1;:::;ng, and  1   +   n. Again, if we select  = 0 and
 = n,we obtain the maximum lower bound for this intersection,  (C1;C2) 42  1 n . Thus,
we have the following proposition.
44
Theorem 4.14. Let r  1,C1, C2 2QRM(r;m) both of type (0; 1;n = 2m), Then If
2 1 <n
1  (C1;C2) 4 1
If, 2 1 >n
42  1 n  (C1;C2) 4 1:
Now, we need to see that given a code C 2QRM(r;m), it is an t-(IR) code. By
Theorem 2.6, we know that the generator matrix ofC can be written as G = G(r;m) + 2N,
where G(r;m) is the generator matrix of the Reed-Muller code with parameters [n; ], which
we know, (see example 3.2.1) is a t-(IR) code and thereforeC. As in the binary case, when
r d(m+ 1)=2e,we have that   r , where r = n  and t =  . According to 4.7, there
exists a subset A f0;1;2;:::;  1g f0;1;2;:::; g such that for all (?;j) 2A, there
is a permutation  ? and a set Sj associated to the map such that  (C; sj( (C))) satis es
the values given by Theorem 4.7. By construction we know that A can be expressed as
follows: A = F5i=1Ai, where, A1 =f(?;0);1 ?   1g, A2 = f(?;1);1  ?    1g,
A3 =f(?;j);? is odd; 1 ?   1; ?+ 1 <j   1g,
A4 =f(?;j);? is even; 1 ?   1; ?+ 1 <j   1g, A5 =f(0;j);0 j  g.
The minimum intersection number obtained by Theorem 4.7 is 2 and is given by the
ordered pair (  1;1) which belong to the subset A2. Since 1 is a lower bound of the
possible spectrum for these codes we still need to see if it is an intersection number. Notice
that 12C, then by Theorem 4.0.4, 1 is not an intersection number.
Similarly, if r d(m+ 1)=2e,we have that   r , where r = n  and t = n  . A
is a subset of f0;1;2;:::;n   1g f0;1;2;:::;n  g. As in the previous case, this set
is the union of the following  ve sets:
A1 =f(?;0);1 ?   1g, A2 =f(?;1);1 ? n   1g,
A3 =f(?;j);? is odd; 1 ? n   1; ?+ 1 <j n   1g,
A4 =f(?;j);? is even; 1 ? n   1; ?+ 1 <j   1g, A5 =f(0;j);0 j n  g.
45
Again, the minimum intersection number obtained by Theorem 4.7, is 4  121. We still
need to see if 42  n is and intersection number. Since for all x2C, gp(x) = 0 by corollary
4.0.1 42  n is not an intersection number.
Considering both cases, we can say that the minimum intersection number for the class
of quaternary Reed-Muller codes is given by maxf42  n;2g.
Additional intersection number are obtained by Theorem 4.8 in the following way. For
t =  , consider ? odd in the interval 1 ?<  1, with S =f2;:::; g, and for t = n  ,
consider ? odd 1 ?<n   1, with S =f2;:::;n  g.
Now, we discuss particular cases. IfC =QRM(1;m), then it is a quaternary Kerdock
code. Since n    , the minimum intersection is 2. IfC =QRM(m 2;m) then, it is the
quaternary linear Preparata code, then n    , and the minimum intersection number is
4  121 if n  > :
46
Chapter 5
Concluding Remarks
In this dissertation we solved the intersection problem for the class of quaternary Reed-
Muller codes, that is, we have found all the intersection numbers by considering intersections
of monomial equivalent codes. In addition, we determined the abelian structure of that
intersections and their respective generator matrices. The class of quaternary Red-Muller
codes contains two important families, the Kerdock-like codes, and Preparata-like codes.
Note that since nonlinear binary Kerdock-like codes and Preparata-like codes are Z4-linear
codes, the spectrum for these codes are also determined. It should be noted that trying
to solve the intersection problem for these codes in the realm of Z2 would be much more
laborious. For example, solving the intersection problem for the quaternary Kerdock code
K is less involved than solving it for nonlinear binary Kerdock-codes.
One problem that is remaining is the intersection problem for binary non-linear codes
that have the same parameters as Kerdock-like codes, and Preparta-like codes, but are not
Z4-linear codes, that is, they are not binary Gray map images of quaternary linear codes.
So, the intersection problem for these codes can not be solved by using the linear structure
provided by Z4.
We have developed enough theory that allows to us to solve the intersection problem for
other families of codes apart of those already examined, that is, Goethals codes, Delsarte-
Goethals codes, ZRM codes and quaternary cyclic codes. Let?s see brie y, how we can apply
the results of chapter 4 to quaternary cyclic codes of length n.
According to their types, quaternary cyclic codes can be classi ed into three classes of
types 204 , 2 4 and 2 40. If the cyclic code is of type 204 , its residue binary cyclic code
is an [n; ]-code. The  rst  columns of its generator matrix are linearly independent and
the last  columns are also linearly independent. So, this binary cyclic code is a t-IR code
47
for t = minf ;rg. Thus the quaternary cyclic code is also a t-IR code for t = minf ;rg. So
all the values speci ed by Theorem 4.7 are intersection numbers.
Cyclic codes of type 2 40 behave as a binary cyclic codes. That way, they are t-IR
codes for t = minf ;n  g. Also the concepts of monomial equivalence and permutation
equivalence, coincide. By Theorem 4.7 for each ?, 0 ? t 1, there is a permutation  ?,
for which  (C; (C)) = 2  ?. Notice that in this case, maxf1;n 2(n  ) + 1g t n  :
The case of cyclic codes of type 2 4 is treated using Theorem 4.5. That is, this case
is the union of the two previous cases.
In the  rst case, it remains to discuss whether maxf1;204n 2(n  )gis also an intersec-
tion number and, in the second case, whether maxf1;2n 2(n  )40g is also an intersection
number. This question can be solved by considering whether the vector 1 is a codeword or
not, for codes of type 2 4 with  > 0; and whether the vector 2 is a codeword or not, for
codes of type 2 4 with  = 0 and  > 0. As matter of example, we consider only the case
when 1 is in the code, (respectively when 2 is in the code).
Denote the code by C and by g its generator polynomial. 1 2C implies that  (1) 2
 (C). Thus,  (g)(1) = 1, where  (g) is the polynomial generator of  (C). Therefore,
either g(1) = 1 or g(1) = 3, which mean that the  rst row of the generator matrix of
C of the generator matrix doesn?t have generalized parity 0 or 2. If the code is of type
4 20, then for  > n  , (t = n  ) the conditions of theorem 4.13 are satis es and
therefore 4  t = 4n 2(n  ) is an intersection number; for   n  , (t =  ) we have
1 = maxf1;4n 2(n  )g and by Lemma 4.0.4, one is not an intersection number. If 2 is in
the code which is of type 402 , then for  >n  (t = n  ) the conditions of theorem 4.12
are satis es and therefore 2  t = 2n 2(n  ) is an intersection number; for   n  , we
have 1 = maxf1;2n 2(n  )g and by Lemma 4.0.4 one is not an intersection number. Using
Theorem 4.5, the general case, can be obtained by combining the two previous cases.
The intersection problem for perfect codes is still unsolved. In the binary case, part of
the spectrum is known. It is interesting to note that in each admissible length, this spectrum
does not have holes in the interval [0;a(n)], where 0 a(n) 2n m 2v. Considering that
48
those intersections numbers were found using essentially the construction of Vasil?ev, we
can consider the possibility that each integer even number z, such that 0 z 2n m 2v
is actually an intersection number by trying to construct pairs of perfect binary codes,
using for example, Phelps construction, or Phelps-Soloveva?s construction among others or
combining them in a more or less ingenious way.
Recently,  Osterg ard, and Pottonin,[24] obtained a complete classi cation of all non
inequivalent perfect binary codes of length 15. By computer search this number is 5983.
Thus, for the case of length 15, we will know the spectrum of the intersection by computer
search. If the spectrum covers all the interval speci ed above, then one can try to prove this
result for all admissible length. On the contrary, if the spectrum has holes then probably
this is true for all admissible lengths.
The intersection problem for q-ary perfect codes is considered in [12]. It is interesting
to notice that there are some di erences with respect to the binary perfect codes. In the
binary case, the minimum intersection number is 2, instead [12] provides one example of
two ternary perfect codes with intersection number equal to 1, which in turn implies that
the intersection number for q-ary perfect codes, where q> 2, is not necessarily even. Also,
[12] gives the spectrum of intersection numbers of non-linear perfect codes by the switchings
of simple components.
Essentially we can classify the known constructions under two groups, those based on
the approach of switching constructions and those base on the approach of concatenation
constructions. It would be interesting determine the spectrum of intersection numbers of
intersection of non-linear q-ary perfect codes using this last approach.
The intersection problem can be seen from another point of view; for example, in the
case of perfect codes, the kernel is their biggest linear sub-code. An obvious question is how
is the spectrum of the intersection of two kernels of the same dimension. It is known that
there are many constructions of perfect codes and we can  nd two perfect codes having
kernels with the same dimension but coming from di erent constructions. It would be
interesting to compare the intersections of kernels of perfect codes obtained by the same
49
construction with the intersection of those coming from di erent constructions. The same
question can be formulated for the rank of a perfect code, which is its smallest linear super-
space.
50
Bibliography
[1] A. Jamos, P.V. Kumar, A.R. Calderbank, N.J.A Sloane, and P. Sole, "The Z4 Linearity
of kerdock, preparata, Goethals, and related codes", IEEE Trans. Inform. Theory, vol.
40, pp. 301-319, 1994.
[2] Z.-X.Wan, "Quaternary Codes", World Scienti c, Singapore, 1997,
[3] J.Borges-K.T. Phelps,J. Rif a, "Kerdok-Like, and preparata-like", IEEE Trans. Inform.
Theory, vol. 49, pp. 2834-2843, 2003.
[4] J. Borges and J. Rif a, \A characterization of 1-additive perfect codes", IEEE Trans.
Inform. Theory, vol. 45, no. 5, pp. 1688{1697, 1999.
[5] C. Fernandez, "On Reed-Muller and related quaternary codes",Universitat Autnoma
de Barcelona Universitat Autnoma de Barcelona, Barcelona, ISBN:84-689-7933-3, Oc-
tober, 2005.
[6] Borges, C. Fernandez, and K.T Phelps, "Quaternary Reed-Muller Codes", IEEE Trans.
Inform. Theory, vol. 51, no. 5, pp. 2686{2691, 2005.
[7] F. I. MacWilliams and N. J. Sloane, The theory of Error-Correcting codes, North-
Holland, New York, 1977.
[8] J. Borges, C. Fern andez, J. Pujol, J. Rif a and M. Villanueva, \add-linear codes:
generator matrices and duality", submitted to Designs, Codes and Cryptography,
arXiv:0710.1149, 2008.
[9] S. V. Avgustinovich, O. Heden, F. I. Solov?eva, \On intersection problem for perfect
binary codes", Designs. Codes and Cryptography., vol. 39, pp. 317{322, 2006.
[10] E. Bar-Yahalom, T. Etzion, \Intersection of isomorphic linear codes", Journal of Comb.
Theory, Series A 80, pp. 247-256, 1997.
[11] F. I. Solov?eva and A. V. Los?, \On intersections of q-ary perfect codes", Proc. Tenth
Int. Workshop \Algebraic and Combinatorial Coding Theory". Zvenigorod, Russia.
September, pp. 244-247, 2006.
[12] F. I. Solov?eva and A. V. Los?, \Intersections of q-ary perfect codes", Siberian Math.
Journal, vol. 49, no. 2, pp. 464-474, 2008.
[13] T. Etzion, and A. Vardy, "On Perfect Binary Codes: Constructions, Properties, and
Enumeration", IEEE Trans. Inform. Theory, vol. 40, no. 3, pp.754-763, 1994
51
[14] K. T. Phelps and M. Villanueva, \Intersection of Hadamard codes", IEEE Trans.
Inform. Theory, vol. 53, no. 5, pp. 1924{1928, 2007.
[15] J. Rif a, F. I. Solov?eva and M. Villanueva, \On the intersection of add-additive perfect
codes", IEEE Trans. Inform. Theory, vol. 54, no. 3, pp. 1346{1356, 2008.
[16] D. S. Krotov, \Z4-linear perfect codes", Discrete Analysis and Operation Research,
Novosibirsk, Institute of Math. SB RAS, vol. 7, N. 4, pp. 78{90, 2000 (in Russian).
(translation available at http://arxiv.org//abs/0710.0198).
[17] D. S. Krotov, D. S. Krotov, \Z4-linear Hadamard and extended perfect codes", Proc.
of the International Workshop on Coding and Cryptography, Paris (France), Jan. 8-12,
pp. 329{334, 2001.
[18] J. L.Vasilev, On nongroup close-packed codes, Probl. Kibernet, vol. 8, pp. 375378. 1962.
[19] K.T. Phelps, A combinatorial construction of perfect Codes, SIAM J. Alg. Meth. In-
form, vol. 4, pp. 398-403. 1983.
[20] F.I. Solove?va, On binary nongroup codes, Methodi Diskr. Analiza, vol. 37, pp. 65-76.
1981.
[21] J. Rif a, Well-Ordered steiner triple system and 1-perfect partitions of the N-cube,
SIAM J. Discrete Math, vol. 12, pp. 35-47. 1999.
[22] T. Etzion, and A. Vardy, On Perfect Codes and tilings: Problems and solutions,SIAM
J. Discrete Math, vol. 11, pp. 205-223. 1998.
[23] J. Rif a, F. I. Solov?eva and M. Villanueva, \On the intersection of Z2Z4-additive
Hadamard codes", IEEE Trans. Inform. Theory, vol. 55, no. 4, pp. 1766{1774, 2009.
[24] Patrick R.J Ostergad, and Olli Pottonin, The Perfect Binary One-Error-Correcting
Codes of Length 15: Part I-Classi cation, arXiv:0806.2513v2,22 jun 2009.
52