On the existence of partitionable skew Room frames

Partitionable skew Room frames of type hⁿ have played an important role in the constructions of 4-frames, (K₄-e)-frames and super-simple (4,2)-frames. In this paper, we investigate the existence of partitionable skew Room frames of type hⁿ. The necessary conditions for the existence of such a design are that and h?5. It is proved that these necessary conditions are also sufficient with a few possible exceptions. As a byproduct, the known results on the existence of skew Room frames and uniform 4-frames are both improved.     

Completely reducible super-simple designs with block size four and related super-simple packings

A design is said to be super-simple if the intersection of any two blocks has at most two elements. A super-simple design \({\mathcal{D}}\) with point set X, block set \({\mathcal{B}}\) and index λ is called completely reducible super-simple (CRSS), if its block set \({\mathcal{B}}\) can be written as \({\mathcal{B}=\bigcup_{i=1}^{\lambda} \mathcal{B}_i}\), such that \({\mathcal{B}_i}\) forms the block set of a design with index unity but having the same parameters as \({\mathcal{D}}\) for each 1 ≤ i ≤ λ. It is easy to see, the existence of CRSS designs with index λ implies that of CRSS designs with index i for 1 ≤ i ≤ λ. CRSS designs are closely related to q-ary constant weight codes (CWCs). A (v, 4, q)-CRSS design is just an optimal (v, 6, 4)_q+1 code. On the other hand, CRSS group divisible designs (CRSSGDDs) can be used to construct q-ary group divisible codes (GDCs), which have been proved useful in the constructions of q-ary CWCs. In this paper, we mainly investigate the existence of CRSS designs. Three neat results are obtained as follows. Firstly, we determine completely the spectrum for a (v, 4, 3)-CRSS design. As a consequence, a class of new optimal (v, 6, 4)₄ codes is obtained. Secondly, we give a general construction for (4, 4)-CRSSGDDs with skew Room frames, and prove that the necessary conditions for the existence of a (4, 2)-CRSSGDD of type g ^u are also sufficient except definitely for \({(g,u)\in \{(2,4),(3,4),(6,4)\}}\). Finally, we consider the related optimal super-simple (v, 4, 2)-packings and show that such designs exist for all v ≥ 4 except definitely for \({v\in \{4,5,6,9\}}\).     

Super-simple, pan-orientable and pan-decomposable GDDs with block size 4

In this paper we study (4,2μ)-GDDs of type gⁿ possessing both the pan-decomposable property introduced by Granville, Moisiadis, Rees, On complementary decompositions of the complete graph, Graphs and Combinatorics 5 (1989) 57-61 and the pan-orientable property introduced by Grüttmüller, Hartmann, Pan-orientable block designs, Australas. J. Combin. 40 (2008) 57-68. We show that the necessary condition for a (4,2μ)-GDD satisfying both of these properties, namely (1) n≥4, μg(n−1)≡0 (mod 3), and (2) g−1,n are not both even if μ is odd are sufficient. When λ=2, our designs are super-simple.We also determine the spectrum of (4,2)-GDDs which are super-simple and possess some of the decomposable/orientable conditions, but are not pan-decomposable or pan-orientable. In particular, we show that the necessary conditions for a super-simple directable (4,2)-GDD of type gⁿ are sufficient.     

Super-simple balanced incomplete block designs with block size 4 and index 5

In statistical planning of experiments, super-simple designs are the ones providing samples with maximum intersection as small as possible. Super-simple designs are also useful in other constructions, such as superimposed codes and perfect hash families etc. The existence of super-simple (v,4,λ)-BIBDs have been determined for λ=2,3,4 and 6. When λ=5, the necessary conditions of such a design are that and v≥13. In this paper, we show that there exists a super-simple (v,4,5)-BIBD for each and v≥13.     

The Sperner Capacity of Linear and Nonlinear Codes for the Cyclic Triangle

Shannon introduced the concept of zero-error capacity of a discrete memoryless channel. The channel determines an undirected graph on the symbol alphabet, where adjacency means that symbols cannot be confused at the receiver. The zero-error or Shannon capacity is an invariant of this graph. Gargano, Körner, and Vaccaro have recently extended the concept of Shannon capacity to directed graphs. Their generalization of Shannon capacity is called Sperner capacity. We resolve a problem posed by these authors by giving the first example (the two orientations of the triangle) of a graph where the Sperner capacity depends on the orientations of the edges. Sperner capacity seems to be achieved by nonlinear codes, whereas Shannon capacity seems to be attainable by linear codes. In particular, linear codes do not achieve Sperner capacity for the cyclic triangle. We use Fourier analysis or linear programming to obtain the best upper bounds for linear codes. The bounds for unrestricted codes are obtained from rank arguments, eigenvalue interlacing inequalities and polynomial algebra. The statement of the cyclic q-gon problem is very simple: what is the maximum size N _q(n) of a subset S _n of {0, 1, \(\ldots\) , q?1} ⁿ with the property that for every pair of distinct vectors x = (x _i), y = (y _i) \(\in \) S _n, we have x _j ?y _j ≡ 1(mod q) for some j? For q = 3 (the cyclic triangle), we show N ₃(n)?2 ⁿ . If however S _n is a subgroup, then we give a simple proof that \(\left| {S_n } \right| \leqslant \sqrt 3 ^n \) .     

Equationally complete (m,n) rings

It is shown that every super-simple (m, n) ring is equationally complete. The atomic varieties of (m, 2) rings and the atomic varieties of (2,n) rings are completely determined.     

On maximum length convolutional codes under a trellis complexity constraint

We look at convolutional codes with maximum possible code length for prescribed redundancy, conditioned on constraints on the free distance and on the bit-oriented trellis state complexity. Rate (n−1)/n codes have been studied to some extent in the literature, but more general rates have not been studied much. In this work we consider convolutional codes of rate (n−r)/n, r⩾1. Explicit construction techniques for free distance d_free=3 and 4 codes are described. For codes with r=2, an efficient exhaustive search algorithm is outlined. For the more general case with r⩾2, a heuristic approach is suggested. Several new codes were found for r=1 and in particular for r=2 and 3. Compared to previously known codes of similar free distance and complexity constraints, the new codes have either strictly higher rate, or the same rate but smaller low distance multiplicities.     

Some constructions of linearly optimal group codes

We continue here the research on (quasi)group codes over (quasi)group rings. We give some constructions of [n,n-3,3]_q-codes over F_q for n=2q and n=3q. These codes are linearly optimal, i.e. have maximal dimension among linear codes having a given length and distance. Although codes with such parameters are known, our main results state that we can construct such codes as (left) group codes. In the paper we use a construction of Reed-Solomon codes as ideals of the group ring F_qG where G is an elementary abelian group of order q.     

Super-simple Steiner pentagon systems

A Steiner pentagon system of order v(SPS(v)) is said to be super-simple if its underlying (v,5,2)-BIBD is super-simple; that is, any two blocks of the BIBD intersect in at most two points. In this paper, it is shown that the necessary condition for the existence of a super-simple SPS(v); namely, v?5 and v≡1 or is sufficient, except for v=5, 15 and possibly for v=25. In the process, we also improve an earlier result for the spectrum of super-simple (v,5,2)-BIBDs, removing all the possible exceptions. We also give some new examples of Steiner pentagon packing and covering designs (SPPDs and SPCDs).     

Latin hypercubes and MDS codes

Maximum distance separable (MDS) codes have special properties that give them excellent error correcting capabilities. Counting the number of q-ary MDS codes of length n and distance d, denoted by D_q(n,d)_MDS, is a very hard problem. This paper shows that for d=2, it amounts to counting the number of (n-1)-dimensional Latin hypercubes of order q. Thus, D_q(3,2)_MDS is the number of Latin squares of order q, which is known only for a few values of q. This paper proves constructively that D₃(n,2)_MDS=6·2^n-2.     

Optimum super-simple mixed covering arrays of type <Emphasis Type="Italic">a</Emphasis><Superscript>1</Superscript><Emphasis Type="Italic">b</Emphasis><Superscript><Emphasis Type="Italic">k</Emphasis>−1</Superscript>

A mixed covering array (MCA) of type (_v 1, v ₂,..., v _k ), denoted by MCA_λ (N; t, k, (v ₁, v ₂,..., v _k )), is an N × k array with entries in the i-th column from a set _{V i} of v _i symbols and has the property that each N × t sub-array covers all the t-tuples at least λ times, where 1 ≤ i ≤ k. An MCA _λ (N; t, k, (_v 1, v ₂,..., v _k )) is said to be super-simple, if each of its N × (t + 1) sub-arrays contains each (t + 1)-tuple at most once. Recently, it was proved by Tang, Yin and the author that an optimum super-simple MCA of type (a, b, b,..., b) is equivalent to a mixed detecting array (DTA) of type (a, b, b,..., b) with optimum size. Such DTAs can be used to generate test suites to identify and determine the interaction faults between the factors in a component-based system. In this paper, some combinatorial constructions of optimum super-simple MCAs of type (a, b, b,..., b) are provided. By employing these constructions, some optimum super-simple MCAs are then obtained. In particular, the spectrum across which optimum super-simple MCA₂(2b ²; 2, 4, (a, b, b, b))′s exist, is completely determined, where 2 ≤ a ≤ b.     

Super-Simple Twofold Steiner Pentagon Systems

A twofold pentagon system of order v is a decomposition of the complete undirected 2-multigraph 2K _v into pentagons. A twofold Steiner pentagon system of order v [TSPS(v)] is a twofold pentagon system such that every pair of distinct vertices is joined by a path of length two in exactly two pentagons of the system. A TSPS(v) is said to be super-simple if its underlying (v, 5, 4)-BIBD is super-simple; that is, if any two blocks of the BIBD intersect in at most two points. In this paper, it is shown that the necessary conditions for the existence of a super-simple TSPS(v); namely, v ≥ 15 and v ≡ 0 or 1 (mod 5) are sufficient. For these specified orders, the main result of this paper also guarantees the existence of a very special and interesting class of twofold and fourfold Steiner pentagon systems of order v with the additional property that, for any two vertices, the two or four paths of length two joining them are distinct.     

The lengths of Hermitian self-dual extended duadic codes

Duadic codes are a class of cyclic codes that generalize quadratic residue codes from prime to composite lengths. For every prime power q, we characterize integers n such that there is a duadic code of length n over F_q² with a Hermitian self-dual parity-check extension. We derive asymptotic estimates for the number of such n as well as for the number of lengths for which duadic codes exist.     

The nonexistence of ternary [105,6,68] and [230,6,152] codes

Let [n,k,d]_q-codes be linear codes of length n, dimension k and minimum Hamming distance d over GF(q). In this paper, the nonexistence of [105,6,68]₃ and [230,6,152]₃ codes is proved.     

Ternary self-orthogonal codes of dual distance three and ternary quantum codes of distance three

Ternary self-orthogonal codes with dual distance three and ternary quantum codes of distance three constructed from ternary self-orthogonal codes are discussed in this paper. Firstly, for given code length n ≥ 8, a ternary [n, k]₃ self-orthogonal code with minimal dimension k and dual distance three is constructed. Secondly, for each n ≥ 8, two nested ternary self-orthogonal codes with dual distance two and three are constructed, and consequently ternary quantum code of length n and distance three is constructed via Steane construction. Almost all of these quantum codes constructed via Steane construction are optimal or near optimal, and some of these quantum codes are better than those known before.     

Combinatorial families enumerated by quasi-polynomials

We say that the sequence (an) is quasi-polynomial in n if there exist polynomials P₀,…,Ps−1 and an integer n₀ such that, for all n?n₀, an=Pi(n) where . We present several families of combinatorial objects with the following properties: Each family of objects depends on two or more parameters, and the number of isomorphism types of objects is quasi-polynomial in one of the parameters whenever the values of the remaining parameters are fixed to arbitrary constants. For each family we are able to translate the problem of counting isomorphism types of objects into the problem of counting integer points in a union of parametrized rational polytopes. The families of objects to which this approach is applicable include combinatorial designs, linear and unrestricted codes, and dissections of regular polygons.     

Euclidean and Hermitian LCD MDS codes

Linear codes with complementary duals (abbreviated LCD) are linear codes whose intersection with their dual is trivial. When they are binary, they play an important role in armoring implementations against side-channel attacks and fault injection attacks. Non-binary LCD codes in characteristic 2 can be transformed into binary LCD codes by expansion. On the other hand, being optimal codes, maximum distance separable codes (abbreviated MDS) are of much interest from many viewpoints due to their theoretical and practical properties. However, little work has been done on LCD MDS codes. In particular, determining the existence of q-ary [n, k] LCD MDS codes for various lengths n and dimensions k is a basic and interesting problem. In this paper, we firstly study the problem of the existence of q-ary [n, k] LCD MDS codes and solve it for the Euclidean case. More specifically, we show that for \(q>3\) there exists a q-ary [n, k] Euclidean LCD MDS code, where \(0\le k \le n\le q+1\), or, \(q=2^{m}\), \(n=q+2\) and \(k= 3 \text { or } q-1\). Secondly, we investigate several constructions of new Euclidean and Hermitian LCD MDS codes. Our main techniques in constructing Euclidean and Hermitian LCD MDS codes use some linear codes with small dimension or codimension, self-orthogonal codes and generalized Reed-Solomon codes.     

New linear codes over GF(8)

Let [n, k, d; q]-codes be linear codes of length n, dimension k and minimum Hamming distance d over GF(q). Let d₈(n, k) be the maximum possible minimum Hamming distance of a linear [n, k, d; 8]-code for given values of n and k. In this paper, eighteen new linear codes over GF(8) are constructed which improve the table of d₈(n, k) by Brouwer.