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], kd(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 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 ? 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 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
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 :
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