2.2. Constructions
+1
A trivial construction allows to construct an equitable partition of H(n+1,q) with intersection array S+(q-1)Id from an equitable partition of H(n,q) with i.array S. In particular, given the intersection array, the existence of a c.r. code in H(n,q) implies the existence in H(N,q) for all N≥n.
*t:
If we have a perfect coloring F (of H(n,q)) with quotient matrix S, then the coloring G(X1,X2,...,Xt)=F(X1+X2+...+Xt) of H(tn,q) is perfect with quotient matrix tS.
[b;c]t
If we have a c.r. code with array [b;c] (in any graph), then its t'th Cartesian power (in the Cartesian power of the graph) is a c.r. code with array [tb, (t-1)b ,..., b; c, 2c, ..., tc] (an arithmetic c.r. code, see [KLM]). However, it is an open question if the nonexistence of a [b;c] c.r. code in H(n,2) necessarily implies the nonexistence of a [tb,(k-1)b,...,b;c,2c,...,tc] c.r. code in H(tn,2). Note: for the case where the original c.r. code is a Hamming code, see the earlier reference [Sole90] (for t=2, [BZZ74]).
Golay family
The binary Golay G[23,12,7] code, the extended binary Golay G[24,12,8] code, different shortened Golay codes.
[23,22,21;1,2,3] Golay code G[23,12,7], see [BCN,11.3E]
[22,21,20;1,2,6] {0,1} shortened G[23,12,7], see [BCN,11.3F]
[21,20,16;1,2,12] {00,01,10,11} shortened G[23,12,7], see [BCN,11.3G]
[24,23,22,21;1,2,3,24] extended Golay code G[24,12,8], see [BCN,11.3D]
[21,20,16,6,2,1;1,2,6,16,20,21] {00,11} shortened G[23,12,7], see [BCN,11.3H]
[21,20,16,9,2,1;1,2,3,16,20,21] {000,111} shortened G[24,12,8], see [BCN,11.3H]
[22,21,20,3,2,1;1,2,3,20,21,22] {0} shortened G[23,12,7], see [BCN,11.3H]
[22,21,20,16,6,2,1;1,2,6,16,20,21,22] {00,11} shortened G[24,12,8], see [BRZ08]
[23,22,21,20,3,2,1;1,2,3,20,21,22,23] {0} shortened G[24,12,8], see [BRZ08]
The arrays [23,22,21,20,3,2,1;1,2,3,20,21,22,23] and [22,21,20,16,6,2,1;1,2,6,16,20,21,22] where known as the intersection arrays of the bipartite doubles of the graphs of cosets of G[23,12,7] and shortened G[23,12,7], respectively, see [BCN,11.3E,11,3F]. These graphs are clearly Cayley graphs of F212; however, the fact that there are completely regular codes with these intersection arrays was unnoticed for several years. Discovering this fact in [BRZ08] disproved (well, refined) the known Neumaier conjecture about the c.r. codes with code distance at least 8.
Three other intersection arrays mentioned in [BCN,11.3E,11,3F] are [253,210,3;1,30,231], [276,231;1,36], [231,160,6;1,48,210]. The corresponding linear c.r. codes also exist by Theorem 11.1.10 [BCN] and can be related to the Golay family of c.r. codes.
Preparata family
Two notable infinite classes of c.r. codes with code distance more than 4 are the classes of nonlinear codes with parameters of Preparata P[22m-1, 22m-2m,5] and P[22m, 22m-2m,6] codes [SZZ71, Th.4, Th.5]. Using translations of the Preparata codes, we can construct a wide family of c.r. codes with code distance 3 and 4.
The binary code P[16,8,6] (also known as the Nordstrom-Robinson code) has intersection array [16, 15, 14, 1; 1, 2, 15, 16]. The code is not linear; however, there is a partition of the extended Hamming H[16,11,4] code into 8 translations of P[16,8,6], see [SZ69] (alternatively, we can partition the Z4-linear H[16,11,4] into Z4-cosets of the Z4-linear representation of P[16,8,6]). The union of T mutually disjoint translations of P[16,8,6] that are subsets of the same H[16,11,4] code gives a c.r. code with array [16,15,16-2T,1;1,2T,15,16]. Puncturing ({0,1}-shortening) gives [15, 16-2T, 1; 1, 2T, 15]. In general, from Preparata P[22m, 22m-2m,6] codes we get [22m-1, 22m-2T, 1; 1, 2T, 22m-1] and [22m, 22m-1, 22m-2T, 1; 1, 2T, 22m-1, 22m] c.r. codes (we can use translations of the original Preparata codes in the extended Hamming code, or Z4-linear Preparata-like and Hamming-like codes).
Splitting construction
The original construction suggested by D. G. Fon-Der-Flaass [FDF] allows to construct [2b+c;c] c.r. codes from [b;c] c.r. codes. Note that, for given b and c satisfying the necessary condition (b+c)/gcd(b,c)=2i (for some i) one can construct [b;c] c.r. codes in H(n,2) for n≥ b+c-gcd(b,c), using rather simple construction (union of cosets of the Hamming code, *t, +1). The splitting construction, in some cases, allows to construct codes for smaller n. We first describe two variants of the original construction (for perfect 2-colorings or, equivalently, for c.r. codes with covering radius 1), then modifications for constructing c.r. codes with covering radius 2.
Simple variant
We start from an equitable partition (C,B) of H(n,2) with quotient matrix
a
c
b
d
where a≤c.
1. By doubling *2 construction, we construct the partition (D,E) of H(2n,2), where D={(x,y) : x+y ∈ C}. The corresponding quotient matrix is
2a
2c
2b
2d
2. Now we split D into two cells D' and D'' accordingly to the parity of the x-part of the word (x,y). Then, (D',D'',E) is an equitable partition with the quotient matrix
3. From (D',D'',E), construct a new partition (D'0∪D''1, D'1∪D''0, E0∪E1) of the hypercube of the next dimension; it is equitable with the quotient matrix
Repeating this step t=c-a times (if t=0, then step 3 is omitted) gives 4. Now we can unify the last two cells (for an equitable partition in general, we can unify two cells, i and j, if the corresponding rows of the quotient matrix coincide in all positions except i and j) to obtain a partition with quotient matrix
a
c
2b+c
2b+a
Advanced variant
If 0<a<c, then we can reduce the diagonal elements of the resulting quotient matrix, together with the dimension of the hypercube, by 1. Using the fact that by König's theorem C can be partitioned into edges, one can modify step 2 to get the array (the idea is, when counting the parity of x, to include also one y-bit, which corresponds to the direction of the edge containing x+y). Then, after step 3 with t=c-a-1 and unifying two cells, we have
a-1
c
2b+c
2b+a-1
Simple splitting construction: covering radius 2
First of all, we note that if a=0, then after step 2 we have two c.r. codes D' and D'' with i.array [2b,c;c,2b]. Also, we can see that iterating steps 1 and 2 gives the array, for example (3 iterations; for our purposes, it is sufficient to split only the first cell in every iteration) Unifying different groups of cells, we can get c.r. codes with i.arrays [8b,7c;c,8b], [8b,6c;2c,8b], [8b,5c;3c,8b], [8b,4c;4c,8b], [8b,3c;5c,8b], [8b,2c;6c,8b], [8b,c;7c,8b]. A special case (b=c=1) of this construction gives the array [2i,2i-t;t,2i]; a c.r. code with this i.array can be obtained as the union of t cosets of the extended Hamming code H[2i,2i-i-1,4].
Advanced splitting construction: covering radius 2
It is possible to modify step 2 to obtain If a=1, then D' and D'' are CR codes with i.array [2b,c;c,2b].
Again, iterating construction can give [2ib,(2i-j)c; jc, 2ib]. Let us describe this with the example of [[a,b],[c,d]]=[[1,5],[3,3]], i=3. The first step is *8: coloring x=(x0,x1,x2,x3,x4,x5,x6,x7) with the color of y=x0+x1+x2+x3+x4+x5+x6+x7, we obtain an equitable partition (D,E) with quotient matrix
8
24
40
24
Next, want to split D to 8 subcells. We can do this in accordance to the parities of (x0+x1+x2+x3), (x0+x1+x4+x5), and (x0+x2+x4+x6). In this case we get
To get zeros in some matrix elements, we modify the parity check functions: we subdivide D according to the parities of (x'0+x'1+x'2+x'3), (x'0+x'1+x'4+x'5), and (x'0+x'2+x'4+x'6), where x'i is obtained from xi by removing the symbol in the position k defined at the unique (because a=1) direction in which y=x0+x1+x2+x3+x4+x5+x6+x7 sees another vertex of D. The new subpartition is equitable with quotient matrix
Next, we can group the first 8 cells into 2 cells (both c.r. codes) in an arbitrary way, realizing each of the intersection arrays [40,3(8-j); 3j, 40], j=1,2,3,4.
It is not known if it is possible to split when a≥2 in non-trivial cases (the cases when a=2 of more after "+1" construction are considered as trivial; they do not result in new parameters).
Cayley graphs and linear c.r. codes
Assume that we have some generating set M of the vector space Fqn over the finite field Fq of order q. We assume that M consists of pairwise independent vectors (however, M can be a redundant generating set as linear dependences involving three or more vectors are allowed), which means `nonzero and distinct' in the binary case. Consider the Cayley graph M(Fqn) on Fqn, where two vectors are adjacent iff their difference belongs to aM for some nonzero a∈Fq. Let AM be a matrix having M as the column set (we fix some basis in Fqn to represent the vectors as columns). It is straightforward that if f is a perfect coloring of M(Fqn), then F(x)=f(AMx) is a perfect coloring of H(|M|,q) with the same quotient matrix. In particular, if B is a c.r. code in M(Fqn), then AMB ={AMx : x∈B} is a c.r. code in H(|M|,q) with the same intersection array. In particular, if B is a linear c.r. code, then AMB is a linear c.r. code too. In particular, if M(Fqn) is a distance regular graph, then the code C(M)={x: AMx=0} is a linear completely regular code with the same intersection array [BCN, 11.1.C]; the code distance is at least 3. The inverse is also true: if C is a linear c.r. code with distance is at least 3 and M is the column set of its check matrix, then the corresponding Cayley graph is distance regular with the same intersection array. So, there is a one-to-one (in some sense) correspondence between the Cayley graphs (of considered type) of vector spaces over Fq and the linear q-ary completely regular codes with distance at least 3. Note that the linear c.r. codes with smaller distance are reduced to the linear c.r. codes with distance ≥3 [Vas08].
There are many different constructions of linear c.r. codes in Hamming graphs, a survey for the case of covering radius 2 can be found in [CK86], see the remarks in the next section. Examples of distance-regular Cayley graphs of large radius are the halved hypercubes and the folded halved hypercubes (the corresponding c.r. codes were considered in [RZ09,RZ14]), the bilinear form graphs (the corresponding c.r. codes were considered in [RZ10]), and the other graphs described in Sections 9.5-9.6 of [BCN]. An important fact is that H(n,qs) is a Cayley graph on Fqns. So, any c.r. code (linear or nonlinear) in H(n,qs) corresponds to a (linear or nonlinear, respectively) c.r. code in H(n(qs-1)/(q-1),q) with the same quotient matrix.
Linear c.r. codes with covering radius 2
Let C be a linear code with distance 3, let C⊥ be its dual, and let M be the column set of the check matrix of C (generator matrix of C⊥). The following assertions are equivalent:
(1) C is a completely regular code with covering radius at most 2.
(2) C⊥ is a projective two-weight code ("projective" means that no two coordinates are linearly dependent).
(3) F*qM is a (λ1,λ2) difference set for some integers λ1, λ2 (that is, for every element v from F*qM it holds λ1=|{(x,y): x-y=v; x,y∈F*qM}| and for every nonzero v∉F*qM it holds λ2=|{(x,y): x-y=v; x,y∈F*qM}| ).
(4) the Cayley graph with generator set M is strongly regular (i.e., distance regular of radius 2; this graph can also be considered at the graph of cosets of C).
A survey of different constructions can be found in [CK86].
References
[BCN] A.E.Brouwer, A.M.Cohen, A.Neumaier. Distance-Regular Graphs. Springer-Verlag, 1989. DOI 10.1007/978-3-642-74341-2
[BZZ74] L.A. Bassalygo, G.V. Zaitsev, V.A. Zinoviev. Uniformly packed codes. Problems Inform. Transmiss. 10(1) 1974, 9-14.
[BRZ08] J. Borges, J. Rifà, V. Zinoviev. On non-antipodal binary completely regular codes. Discrete Math. 308(16) 2008, 3508-3525. DOI 10.1016/j.disc.2007.07.008
[BRZ14] J. Borges, J. Rifà, V. Zinoviev. New families of completely regular codes and their corresponding distance regular coset graphs. Des. Codes Cryptogr. 70(1-2) 2014, 139-148. DOI 10.1007/s10623-012-9713-3
[CK86] A. R. Calderbank, W. M. Kantor. The geometry of two-weight codes. Bull. London Math. Soc. 18(2) 1986, 97-122. DOI 10.1112/blms/18.2.97
[FDF07a] D. G. Fon-Der-Flaass. Perfect 2-colorings of a hypercube. Sib. Math. J. 48(4) 2007, 740–745. DOI 10.1007/s11202-007-0075-4. Translated from Sib. Mat. Zh. 48(4) 2007, 923-930.
[FDF07b] D. G. Fon-Der-Flaass. A bound on correlation immunity. Siberian Electronic Mathematical Reports 4, 2007, 133-135. PDF
[FDF07c] D. G. Fon-Der-Flaass. Perfect colorings of the 12-cube that attain the bound on correlation immunity. Siberian Electronic Mathematical Reports 4, 2007, 292-295 [Russian]. English translation: arXiv:1403.8091
[KLM] J. H. Koolen, W. S. Lee, W. J. Martin. Arithmetic completely regular codes. To appear in ???. http://arxiv.org/abs/0911.1826
[SZZ71] N. V. Semakov, V. A. Zinoviev, G. V. Zaitsev. Uniformly packed codes. Probl. Inf. Transm. 7(1) 1971, 30-39 (translated from Probl. Peredachi Inf. 7(1) 1971, 38-50).
[SZ69] N. V. Semakov, V. A. Zinoviev. Perfect and quasi-perfect equal-weight codes. Probl. Inf. Transm. 5(2) 1969, 11-13 (translated from Probl. Peredachi Inf. 5(2) 1969, 14-18).
[Sole90] P. Sole. Completely regular codes and completely transitive codes. Discrete Math. 81(2) 1990, 193-201. DOI 10.1016/0012-365X(90)90152-8
[Vas08] A. Yu. Vasil'eva. Linear binary completely regular codes with distance 2. Computational Technologies in Electrical and Electronics Engineering, 2008. SIBIRCON 2008. IEEE Region 8 International Conference on. 12-15. DOI 10.1109/SIBIRCON.2008.4602615
[RZ10] J. Rifà, V. Zinoviev. New completely regular q-ary codes based on Kronecker products. IEEE Tranf. Inform. Theory 56(1) 2010, 266-272. DOI 10.1109/TIT.2009.2034812
[RZ09] J. Rifà, V. Zinoviev. On a class of binary linear completely transitive codes with arbitrary covering radius. Discrete Math. 309(16) 2009, 5011-5016. DOI 10.1016/j.disc.2009.03.004
[RZ14] J. Rifà, V. Zinoviev. On a family of binary completely transitive codes with growing covering radius. Discrete Math. 309(16) 2014, 48-52. DOI 10.1016/j.disc.2013.11.009