Divisibility of polynomials over finite fields and combinatorial applications

Consider a maximum-length shift-register sequence generated by a primitive polynomial f over a finite field. The set of its subintervals is a linear code whose dual code is formed by all polynomials divisible by f. Since the minimum weight of dual codes is directly related to the strength of the corresponding orthogonal arrays, we can produce orthogonal arrays by studying divisibility of polynomials. Munemasa (Finite Fields Appl 4(3):252–260, 1998) uses trinomials over \mathbbF₂{\mathbb{F}_2} to construct orthogonal arrays of guaranteed strength 2 (and almost strength 3). That result was extended by Dewar et al. (Des Codes Cryptogr 45:1–17, 2007) to construct orthogonal arrays of guaranteed strength 3 by considering divisibility of trinomials by pentanomials over \mathbbF₂{\mathbb{F}_2} . Here we first simplify the requirement in Munemasa’s approach that the characteristic polynomial of the sequence must be primitive: we show that the method applies even to the much broader class of polynomials with no repeated roots. Then we give characterizations of divisibility for binomials and trinomials over \mathbbF₃{\mathbb{F}_3} . Some of our results apply to any finite field \mathbbF_q{\mathbb{F}_q} with q elements.     

Sudoku-like arrays,codes and orthogonality

This paper is concerned with constructions and orthogonality of generalized Sudoku arrays of various forms. We characterize these arrays based on their constraints; for example Sudoku squares are characterized by having strip and sub-square constraints. First, we generalize Sudoku squares to be multi-dimensional arrays with strip and sub-cube constraints and construct mutually orthogonal sets of these arrays using linear polynomials. We add additional constraints motivated by elementary intervals for low discrepancy sequences and again give a construction of these arrays using linear polynomials in detail for 3 dimensional and a general construction method for arbitrary dimension. Then we give a different construction of these hypercubes due to MDS codes. We also analyze the orthogonality of all of the Sudoku-like hypercubes we consider in this paper.     

Construction of nested orthogonal arrays

A (symmetric) nested orthogonal array is a symmetric orthogonal array OA(N,k,s,g) which contains an OA(M,k,r,g) as a subarray, where M<N and r<s. In this communication, some methods of construction of nested symmetric orthogonal arrays are given. Asymmetric nested orthogonal arrays are defined and a few methods of their construction are described.     

Linear hash families and forbidden configurations

The classical orthogonal arrays over the finite field underlie a powerful construction of perfect hash families. By forbidding certain sets of configurations from arising in these orthogonal arrays, this construction yields previously unknown perfect, separating, and distributing hash families. When the strength s of the orthogonal array, the strength t of the hash family, and the number of its rows are all specified, the forbidden sets of configurations can be determined explicitly. Each forbidden set leads to a set of equations that must simultaneously hold. Hence computational techniques can be used to determine sufficient conditions for a perfect, separating, and distributing hash family to exist. In this paper the forbidden configurations, resulting equations, and existence results are determined when (s, t) ∈ {(2, 5), (2, 6), (3, 4), (4, 3)}. Applications to the existence of covering arrays of strength at most six are presented.      

On linear programming bounds for nets

It is well known that there are close connections between low-discrepancy point sets and sequences on the one hand, and certain combinatorial and algebraic structures on the other hand. E. g., Niederreiter [1] showed the equivalence between (t, t + 2, s)-nets and orthogonal arrays of strength 2. Some years later this was generalized and made precise in the work of Lawrence [2] as well as Mullen and Schmid [3] by introducing ordered orthogonal arrays. This large class of combinatorial structures yields both new constructions and bounds for the existence of nets and sequences. The linear programming bound for ordered orthogonal arrays was first derived by Martin and Stinson [4]. As in the case of error-correcting codes and orthogonal arrays, it yields a very strong bound for ordered orthogonal arrays, and consequently for nets and sequences. Solving linear programming problems in exact arithmetics is very time-consuming. Using different approaches to reduce the computing time, we have calculated the linear programming bound for a wide parameter range. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Self-Orthogonal and Self-Dual Codes Constructed via Combinatorial Designs and Diophantine Equations

Combinatorial designs have been widely used, in the construction of self-dual codes. Recently, new methods of constructing self-dual codes are established using orthogonal designs (ODs), generalized orthogonal designs (GODs), a set of four sequences and Diophantine equations over GF(p). These methods had led to the construction of many new self-dual codes over small finite fields and rings. In this paper, we used some methods to construct self-orthogonal and self dual codes over GF(p), for some primes p. The construction is achieved by using some special kinds of combinatorial designs like orthogonal designs and GODs. Moreover, we combine eight circulant matrices, a system of Diophantine equations over GF(p), and a recently discovered array to obtain a new construction method. Using this method new self-dual and self-orthogonal codes are obtained. Specifically, we obtain new self-dual codes [32,16,12] over GF(11) and GF(13) which improve the previously known distances.     

On t-Covering Arrays

This paper concerns construction methods for t-covering arrays. Firstly, a construction method using perfect hash families is discussed by combining with recursion techniques and error-correcting codes. In particular, by using algebraic-geometric codes for this method we obtain infinite families of t-covering arrays which are proved to be better than currently known probabilistic bounds for covering arrays. Secondly, inspired from a result of Roux [16] and also from a recent result of Chateauneuf and Kreher [6] for 3-covering arrays, we present several explicit constructions for t-covering arrays, which can be viewed as generalizations of their results for t-covering arrays.     

Counting and constructing orthogonal circulants

If F is an arbitrary finite field and T is an n × n orthogonal matrix with entries in F then one may ask how to find all the orthogonal matrices belonging to the algebra F[T] and one may want to know the cardinality of this group. We present here a means of constructing this group of orthogonal matrices given the complete factorization of the minimal polynomial of T over F. As a corollary of this construction scheme we give an explicit formula for the number of n × n orthogonal circulant matrices over GF(p^l) and a similar formula for symmetric circulants. These generalize results of MacWilliams, J. Combinatorial Theory10 (1971), 1–17.     

Incomplete orthogonal arrays and idempotent orthogonal arrays

First, we shall define idempotent orthogonal arrays and notice that idempotent orthogonal array of strength two are idempotent mutually orthogonal quasi-groups. Then, we shall state some properties of idempotent orthogonal arrays.Next, we shall prove that, starting from an incomplete orthogonal arrayT _EF based onE andF E, from an orthogonal arrayT _G based onG = E – F and from an idempotent orthogonal arrayT _H based onH, we are able to construct an incomplete orthogonal arrayT _(F(G×H))F based onF(G × H) andF. Finally, we shall show the relationship between the construction which lead us to this result and the singular direct product of mutually orthogonal quasi-groups given by Sade [5].     

New results on the Bochner condition about classical orthogonal polynomials

The classical polynomials (Hermite, Laguerre, Bessel and Jacobi) are the only orthogonal polynomial sequences (OPS) whose elements are eigenfunctions of the Bochner second-order differential operator F (Bochner, 1929 [3]). In Loureiro, Maroni and da Rocha (2006) [18] these polynomials were described as eigenfunctions of an even order differential operator Fk with polynomial coefficients defined by a recursive relation. Here, an explicit expression of Fk for any positive integer k is given. The main aim of this work is to explicitly establish sums relating any power of F with Fk, k?1, in other words, to bring a pair of inverse relations between these two operators. This goal is accomplished with the introduction of a new sequence of numbers: the so-called A-modified Stirling numbers, which could be also called as Bessel or Jacobi-Stirling numbers, depending on the context and the values of the complex parameter A.     

Spreads, arcs, and multiple wavelength codes

We present several new families of multiple wavelength (2-dimensional) optical orthogonal codes (2D-OOCs) with ideal auto-correlation λ_a=0 (codes with at most one pulse per wavelength). We also provide a construction which yields multiple weight codes. All of our constructions produce codes that are either optimal with respect to the Johnson bound (J-optimal), or are asymptotically optimal and maximal. The constructions are based on certain pointsets in finite projective spaces of dimension k over GF(q) denoted PG(k,q).     

Rational power series, sequential codes and periodicity of sequences

Let R be a commutative ring. A power series f∈R[[x]] with (eventually) periodic coefficients is rational. We show that the converse holds if and only if R is an integral extension over Z_m for some positive integer m. Let F be a field. We prove the equivalence between two versions of rationality in F[[x₁,…,x_n]]. We extend Kronecker’s criterion for rationality in F[[x]] to F[[x₁,…,x_n]]. We introduce the notion of sequential code which is a natural generalization of cyclic and even constacyclic codes over a (not necessarily finite) field. A truncation of a cyclic code over F is both left and right sequential (bisequential). We prove that the converse holds if and only if F is algebraic over F_p for some prime p. Finally, we show that all sequential codes are obtained by a simple and explicit construction.     

On incomplete orthogonal arrays

First we prove that, if an incomplete orthogonal array (1, r, s, k, t) does exist, then s ?(r ? t + 1)k. Next, we establish a relation between the existence of incomplete orthogonal arrays and the existence of orthogonal arrays. From this relation, we may bring out the upper bounds of the maximum number of contraints.     

Balanced sets and circuits in a transversal space

The study of fully dependent sets (unions of circuits) has played a part in characterizing transversal spaces. In fact, the fully dependent sets satisfy |Δ(F)| = ?(F) in any deltoid representation, and it is with a consideration of this property that we begin the present paper. We study “balanced” sets and from our results draw conclusions about fully dependent sets and circuits in a transversal space. These include upper bounds for the number of circuits, and the result that a non-trivial transversal space can be neither a hereditary circuit space nor the dual of a geometric hereditary circuit space. The paper is reasonably self-contained; all unusual terms are defined as they are encountered.     

Affine blocking sets, three-dimensional codes and the Griesmer bound

We construct families of three-dimensional linear codes that attain the Griesmer bound and give a non-explicit construction of linear codes that are one away from the Griesmer bound. All these codes contain the all-1 codeword and are constructed from small multiple blocking sets in AG(2,q).     

Partial Convexity

We study OC-convexity, which is defined by the intersection of conic semispaces of partial convexity. We investigate an optimization problem for OC-convex sets and prove a Krein--Milman type theorem for OC-convexity. The relationship between OC-convex and functionally convex sets is studied. Topological and numerical aspects, as well as separability properties are described. An upper estimate for the Carathéodory number for OC-convexity is found. On the other hand, it happens that the Helly and the Radon number for OC-convexity are infinite. We prove that the OC-convex hull of any finite set of points is the union of finitely many polyhedra.     

On the maximal number of pairwise orthogonal Steiner triple systems

For some time it has been known that for prime powers p^k = 1 + 3 · 2^st there exists a pair of orthogonal Steiner triple systems of order p^k. In fact, such a pair can be constructed using the method of Mullin and Nemeth for constructing strong starters. We use a generalization of the construction of Mullin and Nemeth to construct sets of mutually orthogonal Steiner triple systems for many of these prime powers. By using other techniques we show that a set of mutually orthogonal Steiner triple systems of any given size can be constructed for all but a finite number of such prime powers.     

Pairwise “Orthogonal generalized room squares” and equidistant permutation arrays

A generalized Room square S(r, λ; v) is an r × r array such that every cell in the array contains a subset of a v-set V. This subset could of course be the empty set. The array has the property that every element of V is contained precisely once in every row and column and that any two distinct elements of V are contained in precisely λ common cells. In this paper we define pairwise orthogonal generalized Room squares and give a construction for these using finite projective geometries. This is another generalization of the concept of pairwise orthogonal latin squares. We use these orthogonal arrays to construct permutations having a constant Hamming distance.     

Coding‐theoretic constructions for (t,m,s)‐nets and ordered orthogonal arrays

(t,m,s)‐nets are point sets in Euclidean s‐space satisfying certain uniformity conditions, for use in numerical integration. They can be equivalently described in terms of ordered orthogonal arrays, a class of finite geometrical structures generalizing orthogonal arrays. This establishes a link between quasi‐Monte Carlo methods and coding theory. The ambient space is a metric space generalizing the Hamming space of coding theory. We denote it by NRT space (named after Niederreiter, Rosenbloom and Tsfasman). Our main results are generalizations of coding‐theoretic constructions from Hamming space to NRT space. These comprise a version of the Gilbert‐Varshamov bound, the (u,u+υ)‐construction and concatenation. We present a table of the best known parameters of q‐ary (t,m,s)‐nets for qε{2,3,4,5} and dimension m≤50. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 403–418, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10015