Some New Optimal Ternary Linear Codes

Let d₃(n,k) be the maximum possible minimum Hamming distance of a ternary [ n,k,d;3]-code for given values of n and k. It is proved that d₃(44,6)=27, d₃(76,6)=48,d₃(94,6)=60 , d₃(124,6)=81,d₃(130,6)=84 , d₃(134,6)=87,d₃(138,6)=90 , d₃(148,6)=96,d₃(152,6)=99 , d₃(156,6)=102,d₃(164,6)=108 , d₃(170,6)=111,d₃(179,6)=117 , d₃(188,6)=123,d₃(206,6)=135 , d₃(211,6)=138,d₃(224,6)=147 , d₃(228,6)=150,d₃(236,6)=156 , d₃(31,7)=17 and d₃(33,7)=18 . These results are obtained by a descent method for designing good linear codes.     

Optimal ternary linear codes

Let n _q (k, d) denote the smallest value of n for which there exists a linear [n, k, d]-code over GF(q). An [n, k, d]-code whose length is equal to n _q (k, d) is called optimal. The problem of finding n _q (k, d)has received much attention for the case q = 2. We generalize several results to the case of an arbitrary prime power q as well as introducing new results and a detailed methodology to enable the problem to be tackled over any finite field.In particular, we study the problem with q = 3 and determine n ₃(k, d) for all d when k 4, and n ₃(5, d) for all but 30 values of d.     

The Nonexistence of Ternary [50,5,32] Codes

It is unknown (cf. Hill and Newton [8] or Hamada [3]) whether or not there exists a ternary [50,5,32] code meeting the Griesmer bound. The purpose of this paper is to prove the nonexistence of ternary [50,5,32] codes. Since there exists a ternary [51,5,32] code, this implies that n3(5,32) = 51, where n3(k,d) denotes the smallest value of n for which there exists a ternary [n,k,d] code.     

Optimal holey packings OHP4(2, 4, n ,3)'s

An optimal holey packing OHP_d(2, k, n, g) is equivalent to a maximal (g + 1)‐ary (n, k, d) constant weight code. In this paper, we provide some recursive constructions for OHP_d(2, k, n, g)'s and use them to investigate the existence of an OHP₄(2, 4, n, 3) for n ≡ 2, 3 (mod 4). Combining this with Wu's result ( 18 ), we prove that the necessary condition for the existence of an OHP₄(2, 4, n, 3), namely, n ≥ 5 is also sufficient, except for n ∈ {6, 7} and except possibly for n = 26. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 111–123, 2006     

A family of Bernstein quasi-interpolants on [0,1]

Suppose that we want to approximate f∈C[0,1] by polynomials inP, using only its values on X_n={i/n, 0≤i≤n}. This can be done by the Lagrange interpolant L_n f or the classical Bernstein polynomial B_n f. But, when n tends to infinity, L_n f does not converge to f in general and the convergence of B_n f to f is very slow. We define a family of operators B _n ^(k) , n≥k, which are intermediate ones between B _n ⁽⁰⁾ =B _n ⁽¹⁾ =B_n and B _n ⁽ⁿ⁾ =L_n, and we study some of their properties. In particular, we prove a Voronovskaja-type theorem which asserts that B _n ^(k) f−f=O(n^−[(k+2)/2]) for f sufficiently regular. Moreover, B _n ^(k) f uses only values of B_n f and its derivaties and can be computed by De Casteljau or subdivision algorithms.     

The Smallest Parallelepiped of n Random Points and Peeling

Let n random points be given with uniform distribution in the d-dimensional unit cube [0,1]^d. The smallest parallelepiped A which includes all the n random points is dealt with. We investigate the asymptotic behavior of the volume of A as n tends to . Using a point process approach, we derive also the asymptotic behavior of the volumes of the k-th smallest parallelepipeds A _n ^(k) which are defined by iteration. Let A _n = A _n ⁽¹⁾ . Given A _n ^(k,-,1) delete the random points X _i which are on the boundary A _n ^(k,-,1) , and construct the smallest parallelepiped which includes the inner points of A _n ^(k,-,1) , this defines A _n ^(k) . This procedure is known as peeling of the parallelepiped A_n.     

A Remarkable q,t-Catalan Sequence and q-Lagrange Inversion

We introduce a rational function C _n(q, t) and conjecture that it always evaluates to a polynomial in q, t with non-negative integer coefficients summing to the familiar Catalan number . We give supporting evidence by computing the specializations and C _n (q) = C _n(q,1) = C _n(1,q). We show that, in fact, D _n(q) q-counts Dyck words by the major index and C _n(q) q-counts Dyck paths by area. We also show that C _n(q, t) is the coefficient of the elementary symmetric function e _nin a symmetric polynomial DH_n(x; q, t) which is the conjectured Frobenius characteristic of the module of diagonal harmonic polynomials. On the validity of certain conjectures this yields that C _n(q, t) is the Hilbert series of the diagonal harmonic alternants. It develops that the specialization DH_n(x; q, 1) yields a novel and combinatorial way of expressing the solution of the q-Lagrange inversion problem studied by Andrews [2], Garsia [5] and Gessel [11]. Our proofs involve manipulations with the Macdonald basis {P (x; q, t)} which are best dealt with in -ring notation. In particular we derive here the -ring version of several symmetric function identities.Work carried out under NSF grant support.     

TheT-ideal generated by the standard identitys 3[x 1,x 2,x 3]

LetK = T_o(s₃), {c_n} its codimensions, {l_n} its colengths and {Χ_n} its sequence of co-characters. For 9≦n, c_n =2n - 1 or c_n =n(n + l)/2- 1, 3≦l_n ≦4 and χ_n =[n] + 2[n-1,1] + α[n-2,2] + β[2²,1^n?4] where α + β≦l.     

Ternary codes of steiner triple systems

The code over a finite field F^q of a design ?? is the space spanned by the incidence vectors of the blocks. It is shown here that if ?? is a Steiner triple system on v points, and if the integer d is such that 3^d ≤ v < 3^d+1, then the ternary code C of ?? contains a subcode that can be shortened to the ternary generalized Reed-Muller code ?_F3(2(d ? 1),d) of length 3^d. If v = 3^d and d ≥ 2, then C_? ? ?_F3(1,d)? ? _F3(2(d ? 1),d) ? C. © 1994 John Wiley & Sons, Inc.     

ADDITIVE FAMILIES OF INVARIANTS OF SKEWSYMMETRIC TENSORS

Abstract

Let d be a positive integer and F be a field of characteristic 0. Suppose that for each positive integer n, I _n is a polynomial invariant of the usual action of GL_n (F) on Λ^d(Fⁿ), such that for t ? Λ^d(F ^k) and s ? Λ^d(F ^l), I _{k + l} (t l s) = I _k(t)I _t (s), where t ⊥ s is defined in §1.4. Then we say that {I_n} is an additive family of invariants of the skewsymmetric tensors of degree d, or, briefly, an additive family of invariants. If not all the I_n are constant we say that the family is non-trivial. We show that in each even degree d there is a non-trivial additive family of invariants, but that this is not so for any odd d. These results are analogous to those in our paper [3] for symmetric tensors. Our proofs rely on the symbolic method for representing invariants of skewsymmetric tensors. To keep this paper self-contained we expound some of that theory, but for the proofs we refer to the book [2] of Grosshans, Rota and Stein.     

Optimal ternary quasi-cyclic codes

Quasi-cyclic codes have provided a rich source of good linear codes. Previous constructions of quasi-cyclic codes have been confined mainly to codes whose length is a multiple of the dimension. In this paper it is shown how searches may be extended to codes whose length is a multiple of some integer which is greater than the dimension. The particular case of 5-dimensional codes over GF(3) is considered and a number of optimal codes (i.e., [n, k, d]-codes having largest possible minimum distance d for given length n and dimension k) are constructed. These include ternary codes with parameters [45, 5, 28], [36, 5, 22], [42, 5, 26], [48, 5, 30] and [72, 5, 46], all of which improve on the previously best known bounds.This research has been supported by the British SERC.     

On the Positive Definiteness of Certain Functions

For a coinmutative senugoup (S, +, *) with involution and a function f : S → [0, ∞), the set S(f) of those p ≥ 0 such that f^P is a positive definite function on S is a closed subsemigroup of [0, ∞) containing 0. For S = (IR, +, x* = -x) it may happen that S(f) = { kd : k ∈ N₀ } for some d > 0, and it may happen that S(f) = {0} ? [d, ∞) for some d > O. If α > 2 and if S = (?, +, n* = -n) and f(n) = e^?[n]α or S = (IN₀, +, n* = n) and f(n) = e^nα, then S(f) ∪ (0, c) = ? and [d, ∞) ? S(f) for some d ≥; c > 0. Although (with c maximal and d minimal) we have not been able to show c = d in all cases, this equality does hold if S = ? and α ≥ 3.4. In the last section we give sinipler proofs of previously known results concerning the positive definiteness of x → e^?||x||α on normed spaces.     

Constructing Maximal Commutative Subalgebras of Matrix Rings in Small Dimensions

Let k denote an algebraically closed field of arbitrary characteristic. Let C denote the set of all commutative, finite dimensional, local k-algebras of the form (B, m, k) with i(m) ?2. Here i(m) denotes the index of nilpotency of the maximal ideal m. A Akalgebra (R, J,k)∈L is called a (c₁-construction if there exists (B, m, k)∈ £ ? {(k, (0), k)} and a finitely generated, faithful B-module N such that R,?B?(the idealization of N). (R.J.k) is called a (c_2::-construction if there exist a (B,m k)∈ L, a positive integer p $ge;2 and a nonzero z £ S_B(the socle of B) such that R?B[x]/(mX, X^p- z). Let M_n×n(K) denote the set of all n x n matrices, over k with n≥2. Let .M_n(k) denote the set of all maximal, commutative A;-subalgebras of M_n×n(k). In this paper, we show any (R J, k) ∈£?M_n;(k) with n>5 is a C₁ or C₂ -construction except for one isomorphism class. The one exception occurs when n = 5.     

Construction of Some Optimal Ternary Linear Codes and the Uniqueness of [294, 6, 195; 3]-Codes Meeting the Griesmer Bound

Let n_q(k, d) denote the smallest value of n for which there exists an [n, k, d; q]-code. It is known (cf. (J. Combin. Inform. Syst. Sci.18, 1993, 161–191)) that (1) n₃(6, 195) {294, 295}, n₃(6, 194) {293, 294}, n₃(6, 193) {292, 293}, n₃(6, 192) {290, 291}, n₃(6, 191) {289, 290}, n₃(6, 165) {250, 251} and (2) there is a one-to-one correspondence between the set of all nonequivalent [294, 6, 195; 3]-codes meeting the Griesmer bound and the set of all {v₂ + 2v₃ + v₄, v₁ + 2v₂ + v₃; 5, 3}-minihypers, where v_i = (3ⁱ − 1)/(3 − 1) for any integer i ≥ 0. The purpose of this paper is to show that (1) n₃(6, 195) = 294, n₃(6, 194) = 293, n₃(6, 193) = 292, n₃(6, 192) = 290, n₃(6, 191) = 289, n₃(6, 165) = 250 and (2) a [294, 6, 195; 3]-code is unique up to equivalence using a characterization of the corresponding {v₂ + 2v₃ + v₄, v₁ + 2v₂ + v₃; 5, 3}-minihypers.     

Weight Hierarchies of Linear Codes Satisfying the Chain Condition

The weight hierarchy of a linear [n,k;q] code C over GF(q) is the sequence (d₁,d₂,...,d_k) where d_r is the smallest support of an r–dimensional subcode of C. By explicit construction, it is shown that if a sequence (a₁,a₂,...,a_k) satisfies certain conditions, then it is the weight hierarchy of a code satisfying the chain condition.     

Separable polynomials over finite dimensional algebras

In [5] it was shown that for a polynomial P of precise degree n with coefficients in an arbitrary m-ary algebra of dimension d as a vector space over an algebraically closed fields, the zeros of P together with the homogeneous zeros of the dominant part of P form a set of cardinality n^d or the cardinality of the base field. We investigate polynomials with coefficients in a d dimensional algebra A without assuming the base field k to be algebraically closed. Separable polynomials are defined to be those which have exactly n^d distinct zeros in [Ktilde] ?_k A [Ktilde] where [Ktilde] denotes an algebraic closure of k. The main result states that given a separable polynomial of degree n, the field extension L of minimal degree over k for which L ?_k A contains all nd zeros is finite Galois over k. It is shown that there is a non empty Zariski open subset in the affine space of all d-dimensional k algebras whose elements A have the following property: In the affine space of polynomials of precise degree n with coefficients in A there is a non empty Zariski open subset consisting of separable polynomials; in other polynomials with coefficients in a finite dimensional algebra are “generically” separable.     

On the minimum length of ternary linear codes

From the geometrical point of view, we prove that [g ₃(6, d) + 1, 6, d]₃ codes exist for d = 118–123, 283–297 and that [g ₃(6, d), 6, d]₃ codes for d = 100, 341, 342 and [g ₃(6, d) + 1, 6, d]₃ codes for d = 130, 131, 132 do not exist, where ${g_3(k,\,d)=\sum_{i=0}^{k-1}\left\lceil d/3^i \right\rceil}$ . These determine the exact value of n ₃(6, d) for d = 100, 118–123, 130, 131, 132, 283–297, 341, 342, where n _q (k, d) is the minimum length n for which an [n, k, d] _q code exists.     

The second and the third smallest distances on the sphere

Let s₁ (n) denote the largest possible minimal distance amongn distinct points on the unit sphere . In general, let s_k(n) denote the supremum of thek-th minimal distance. In this paper we prove and disprove the following conjecture of A. Bezdek and K. Bezdek: s₂(n) = s₁([n/3]). This equality holds forn > n₀ however s₂(12) > s₁(4).We set up a conjecture for s_k(n), that one can always reduce the problem of thek-th minimum distance to the function s₁. We prove this conjecture in the casek=3 as well, obtaining that s₃(n) = s₁([n/5]) for sufficiently largen.The optimal construction for the largest second distance is obtained from a point set of size [n/3] with the largest possible minimal distance by replacing each point by three vertices of an equilateral triangle of the same size . If 0, then s₂ tends to s₁([n/3]). In the case of the third minimal distance, we start with a point set of size [n/5] and replace each point by a regular pentagon.     

A Necessary and Sufficient Condition for the Existence of Some Ternary [n, k, d] Codes Meeting the Greismer Bound

Let k and d be any integers such that k 4 and . Then there exist two integers and in {0,1,2} such that . The purpose of this paper is to prove that (1) in the case k 5 and (,) = (0,1), there exists a ternary code meeting the Griesmer bound if and only if and (2) in the case k 4 and (,) = (0,2) or (1,1), there is no ternary code meeting the Griesmer bound for any integers k and d and (3) in the case k 5 and , there is no projective ternary code for any integers k and such that 1k-3, where and for any integer i 0. In the special case k=6, it follows from (1) that there is no ternary linear code with parameters [233,6,154] , [234,6,155] or [237,6,157] which are new results.     

The fractional dimensional theory in Lüroth expansion

It is well known that every x ∈ (0, 1] can be expanded to an infinite Lüroth series in the form of