On the integrality of nth roots of generating functions

Motivated by the discovery that the eighth root of the theta series of the E₈ lattice and the 24th root of the theta series of the Leech lattice both have integer coefficients, we investigate the question of when an arbitrary element f∈R (where R=1+xZ?x?) can be written as f=gn for g∈R, n?2. Let Pn:={gn|g∈R} and let . We show among other things that (i) for f∈R, f∈Pn⇔f (mod μn)∈Pn, and (ii) if f∈Pn, there is a unique g∈Pn with coefficients mod μn/n such that f≡gn (mod μn). In particular, if f≡1 (mod μn) then f∈Pn. The latter assertion implies that the theta series of any extremal even unimodular lattice in Rn (e.g. E₈ in R⁸) is in Pn if n is of the form i²j³k⁵ (i?3). There do not seem to be any exact analogues for codes, although we show that the weight enumerator of the rth order Reed-Muller code of length m² is in Pr² (and similarly that the theta series of the Barnes-Wall lattice BWm² is in Pm²). We give a number of other results and conjectures, and establish a conjecture of Paul D. Hanna that there is a unique element f∈Pn (n?2) with coefficients restricted to the set {1,2,…,n}.     

Linear Codes over \mathbb{F}_{q}[u]/(u^s) with Respect to the Rosenbloom–Tsfasman Metric

We investigate the structure of codes over rings with respect to the Rosenbloom-Tsfasman (RT) metric. We define a standard form generator matrix and show how we can determine the minimum distance of a code by taking advantage of its standard form. We define MDR (maximum distance rank) codes with respect to this metric and give the weights of the codewords of an MDR code. We explore the structure of cyclic codes over and show that all cyclic codes over rings are MDR. We propose a decoding algorithm for linear codes over these rings with respect to the RT metric. AMS Classification: 94B05, 94B60     

The polynomial degree of the Grassmannian G(1,n,q) of lines in finite projective space PG(n, q)

Let G: = G(1,n,q) denote the Grassmannian of lines in PG(n,q), embedded as a point-set in PG(N, q) with For n = 2 or 3 the characteristic function of the complement of G is contained in the linear code generated by characteristic functions of complements of n-flats in PG(N, q). In this paper we prove this to be true for all cases (n, q) with q = 2 and we conjecture this to be true for all remaining cases (n, q). We show that the exact polynomial degree of is for δ: = δ(n, q) = 0 or 1, and that the possibility δ = 1 is ruled out if the above conjecture is true. The result deg( for the binary cases (n,2) can be used to construct quantum codes by intersecting G with subspaces of dimension at least      

On the length of the tail of a vector space partition

A vector space partition of a finite dimensional vector space V=V(n,q) of dimension n over a finite field with q elements, is a collection of subspaces U₁,U₂,…,U_t with the property that every non zero vector of V is contained in exactly one of these subspaces. The tail of consists of the subspaces of least dimension d₁ in , and the length n₁ of the tail is the number of subspaces in the tail. Let d₂ denote the second least dimension in .Two cases are considered: the integer q^d₂−d₁ does not divide respective divides n₁. In the first case it is proved that if 2d₁>d₂ then n₁≥q^d₁+1 and if 2d₁≤d₂ then either n₁=(q^d₂−1)/(q^d₁−1) or n₁>2q^d₂−d₁. These lower bounds are shown to be tight and the elements in the subspaces in tails of minimal length will constitute a subspace of V of dimension 2d₁ respectively d₂.In case q^d₂−d₁ divides n₁ it is shown that if d₂<2d₁ then n₁≥q^d₂−q^d₁+q^d₂−d₁ and if 2d₁≤d₂ then n₁≥q^d₂. The last bound is also shown to be tight.The results considerably improve earlier found lower bounds on the length of the tail.     

Johnson type bounds on constant dimension codes

Very recently, an operator channel was defined by Koetter and Kschischang when they studied random network coding. They also introduced constant dimension codes and demonstrated that these codes can be employed to correct errors and/or erasures over the operator channel. Constant dimension codes are equivalent to the so-called linear authentication codes introduced by Wang, Xing and Safavi-Naini when constructing distributed authentication systems in 2003. In this paper, we study constant dimension codes. It is shown that Steiner structures are optimal constant dimension codes achieving the Wang-Xing-Safavi-Naini bound. Furthermore, we show that constant dimension codes achieve the Wang-Xing-Safavi-Naini bound if and only if they are certain Steiner structures. Then, we derive two Johnson type upper bounds, say I and II, on constant dimension codes. The Johnson type bound II slightly improves on the Wang-Xing-Safavi-Naini bound. Finally, we point out that a family of known Steiner structures is actually a family of optimal constant dimension codes achieving both the Johnson type bounds I and II.      

Optimal conflict-avoiding codes of length <Emphasis Type="Italic">n</Emphasis> ≡ 0 (mod 16) and weight 3

A conflict-avoiding code of length n and weight k is defined as a set of binary vectors, called codewords, all of Hamming weight k such that the distance of arbitrary cyclic shifts of two distinct codewords in C is at least 2k−2. In this paper, we obtain direct constructions for optimal conflict-avoiding codes of length n = 16m and weight 3 for any m by utilizing Skolem type sequences. We also show that for the case n = 16m + 8 Skolem type sequences can give more concise constructions than the ones obtained earlier by Jimbo et al.      

Strong difference families,difference covers,and their applications for relative difference families

In (M. Buratti, J Combin Des 7:406–425, 1999), Buratti pointed out the lack of systematic treatments of constructions for relative difference families. The concept of strong difference families was introduced to cover such a problem. However, unfortunately, only a few papers consciously using the useful concept have appeared in the literature in the past 10 years. In this paper, strong difference families, difference covers and their connections with relative difference families and optical orthogonal codes are discussed.      

2-(31,15,7), 2-(35,17,8) and 2-(36,15,6) designs with automorphisms of odd prime order,and their related Hadamard matrices and codes

We present the full classification of Hadamard 2-(31,15,7), Hadamard 2-(35, 17,8) and Menon 2-(36,15,6) designs with automorphisms of odd prime order. We also give partial classifications of such designs with automorphisms of order 2. These classifications lead to related Hadamard matrices and self-dual codes. We found 76166 Hadamard matrices of order 32 and 38332 Hadamard matrices of order 36, arising from the classified designs. Remarkably, all constructed Hadamard matrices of order 36 are Hadamard equivalent to a regular Hadamard matrix. From our constructed designs, we obtained 37352 doubly-even [72,36,12] codes, which are the best known self-dual codes of this length until now.      

On circulant self-dual codes over small fields

We construct self-dual codes over small fields with q = 3, 4, 5, 7, 8, 9 of moderate length with long cycles in the automorphism group. With few exceptions, the codes achieve or improve the known lower bounds on the minimum distance of self-dual codes.      

Linear Programming Bounds for Codes via a Covering Argument

We recover the first linear programming bound of McEliece, Rodemich, Rumsey, and Welch for binary error-correcting codes and designs via a covering argument. It is possible to show, interpreting the following notions appropriately, that if a code has a large distance, then its dual has a small covering radius and, therefore, is large. This implies the original code to be small. We also point out that this bound is a natural isoperimetric constant of the Hamming cube, related to its Faber–Krahn minima. While our approach belongs to the general framework of Delsarte’s linear programming method, its main technical ingredient is Fourier duality for the Hamming cube. In particular, we do not deal directly with Delsarte’s linear program or orthogonal polynomial theory. This research was partially supported by ISF grant 039-7682.