On 2-dimensional insertion-deletion Reed-Solomon codes with optimal asymptotic error-correcting capability

Reed-Solomon codes have gained a lot of interest due to its encoding simplicity, well structuredness and list-decoding capability [6] in the classical setting. This interest also translates to other metric setting, including the insertion and deletion (insdel for short) setting which is used to model synchronization errors caused by positional information loss in communication systems. Such interest is supported by the construction of a deletion correcting algorithm of insdel Reed-Solomon code in [22] which is based on the Guruswami-Sudan decoding algorithm [6]. Nevertheless, there have been few studies [3] on the insdel error-correcting capability of Reed-Solomon codes.In this paper, we discuss a criterion for a 2-dimensional insdel Reed-Solomon codes to have optimal asymptotic error-correcting capabilities, which are up to their respective lengths. Then we provide explicit constructions of 2-dimensional insdel Reed-Solomon codes that satisfy the established criteria. The family of such constructed codes can then be shown to extend the family of codes with asymptotic error-correcting capability reaching their respective lengths provided in [3, Theorem 2] which provide larger error-correcting capability compared to those defined in [25].     

一类新的渐近稳定多项式

[1]对[2]中提出的求多项式根的渐近因子分离法进行了详细的讨论,国外对此法(称为Sebastiao e Silva算法)也进行了大量的研究,例如[3]—[9].此算法有不少令人注目的特点.本文将讨论一类新的渐近稳定多项式,它们也具有许多与 Sebastiao e Silva算法相类似的性质.     

Incomplete sums,DC-constrained codes,and codes that maintain synchronization

The codes formed by vectors of values of characters of polynomials with argument running over (a subset of) points of a finite field are a frequent object of investigation since one can estimate their parametes via the classical inequalities for the values of exponential sums. In [2] it was observed that applying estimates of incomplete sums, one can prove that some codes of this type have small running digital sum compared to the block length. In the present paper, we derive an extension of the results of [2] to nonprime fields and to the nonbinary case, which leads to new families of error-correcting dc-constrained codes. We show also that constructed codes are comma-free and detect synchronization errors even for a high rate of additive errors.The results of this paper were presented in part at the French-Soviet Workshop on Algebraic Coding, Paris, July 22–24, 1991, and published in Springer Lect. Notes Comput. Sci., 573, 1992, pp. 16–22.     

Skew codes of prescribed distance or rank

In this paper we generalize the notion of cyclic code and construct codes as ideals in finite quotients of non-commutative polynomial rings, so called skew polynomial rings of automorphism type. We propose a method to construct block codes of prescribed rank and a method to construct block codes of prescribed distance. Since there is no unique factorization in skew polynomial rings, there are much more ideals and therefore much more codes than in the commutative case. In particular we obtain a [40, 23, 10]₄ code by imposing a distance and a [42,14,21]₈ code by imposing a rank, which both improve by one the minimum distance of the previously best known linear codes of equal length and dimension over those fields. There is a strong connection with linear difference operators and with linearized polynomials (or q-polynomials) reviewed in the first section.      

Higher order recurrences for analytical functions of Tchebysheff type

Relation of hyperbolons of volume one to generalized Clifford algebras is described in [1b] and there some applications are listed. In this note which is an extension of [8] we use the one parameter subgroups of the group of hyperbolons of volume one in order to define and investigate generalization of Tchebysheff polynomial system. Parallely functions of roots of polynomials of any degree are studied as possible generalization of symmetric functions considered by Eduard Lucas. It is found how functions of roots of polynomial of any degree are related to this generalization of Tchebysheff polynomials. The relation is explicit. In a primary sense the considered generalization is in passing fromZ ₂ toZ _n group decomposition of the exponential. We end up with an application of the discovered generalization to quite large class of dynamical systems with iteration.     

多项式稳定性判据对代数方程求根的应用及其数值试验

一、引言 已有许多方法可以求多项式的根,其中多数属于迭代法.这类方法的缺点是收敛性依赖于初始近似的选择(求复根还没有大范围收敛的迭代法).另一类方法是先求根的模或实部,然后再设法求同模或等实部的根,如根平方——结式法,按分布理论求根等就属于这一类.这类方法不存在收敛性问题,但也有其不足之处.如根平方——结点法的缺点除了有可能将良态多项式变为病态多项式之外,求结式也增加了计算的复杂性.采用单精度运算的数值试验结果表明,这个方法求解的精度比某些迭代法低.     

关于路与圈的匹配多项式的一个注记（英文）

The spectra of matching polynomials which are useful in the computations of resonance energy and grand canonical partition functions of molecular's. It also present other properties for certain classes of graphs and lattices. In [1] Balasubramanian calculates several matching polynomials and matching roots of several molecular graphs. He found that the matching polynomial of C_6, C_(10), C_(14), C_(18) and C_(22) are divided by x~2-2. In this note,we prove that x~2-2 divides MC_(4k+2)(x), k = 1, 2,..., n and obtain some other properties of matching polynomials of paths and cycles.     

On chromatic and flow polynomial unique graphs

It is known that the chromatic polynomial and flow polynomial of a graph are two important evaluations of its Tutte polynomial, both of which contain much information of the graph. Much research is done on graphs determined entirely by their chromatic polynomials and Tutte polynomials, respectively. Oxley asked which classes of graphs or matroids are determined by their chromatic and flow polynomials together. In this paper, we found several classes of graphs with this property. We first study which graphic parameters are determined by the flow polynomials. Then we study flow-unique graphs. Finally, we show that several classes of graphs, ladders, Möbius ladders and squares of n-cycle are determined by their chromatic polynomials and flow polynomials together. A direct consequence of our theorem is a result of de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomial, Graphs Comb. 20 (2004) 105-119] that these classes of graphs are Tutte polynomial unique.     

Pointwise error estimates for interpolation

Pointwise error estimates are obtained for polynomial interpolants in the roots and extrema of the Chebyshev polynomials of the first kind. These estimates are analogous to those derived by Henrici [2] for trigonometric polynomial interpolants.     

A series solution for nonlinear differential equations using delta operators

In this paper, we shall generalize our previous results [1] to the case of series expansion in powers of several polynomials. For this, we shall extend the ideas of delta operators and their basic polynomial sequences, introduced in conjunction with the algebra (over a field of characteristic zero) of all polynomials in one variable [2] to the algebra (over a field of characteristic zero) of all polynomials in n indeterminates. We apply this technique to derive the formal power series expansion of the input-output map describing a nonlinear system with polynomial inputs.     

Explicit subspace designs

A subspace design is a collection {H ₁, H ₂, ...,H _M } of subspaces of \(\mathbb{F}_q^m\) with the property that no low-dimensional subspace W of \(\mathbb{F}_q^m\) intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal rate list-decodable codes over constant-sized large alphabets and sub-logarithmic (and even smaller) list size. Subspace designs are the only non-explicit part of their construction. In this paper, we give explicit constructions of subspace designs with parameters close to the probabilistic construction, and this implies the first deterministic polynomial time construction of list-decodable codes achieving the above parameters.Our constructions of subspace designs are natural and easily described, and are based on univariate polynomials over finite fields. Curiously, the constructions are very closely related to certain good list-decodable codes (folded RS codes and univariate multiplicity codes). The proof of the subspace design property uses the polynomial method (with multiplicities): Given a target low-dimensional subspace W, we construct a nonzero low-degree polynomial P _W that has several roots for each H _i that non-trivially intersects W. The construction of P _W is based on the classical Wronskian determinant and the folded Wronskian determinant, the latter being a recently studied notion that we make explicit in this paper. Our analysis reveals some new phenomena about the zeroes of univariate polynomials, namely that polynomials with many structured roots or many high multiplicity roots tend to be linearly independent.     

Nonbinary quantum error-correcting codes from algebraic curves

We give a new exposition and proof of a generalized CSS construction for nonbinary quantum error-correcting codes. Using this we construct nonbinary quantum stabilizer codes with various lengths, dimensions, and minimum distances from algebraic curves. We also give asymptotically good nonbinary quantum codes from a Garcia–Stichtenoth tower of function fields which are constructible in polynomial time.     

Parameter choices on Guruswami–Sudan algorithm for polynomial reconstruction

Guruswami–Sudan algorithm for polynomial reconstruction problem plays an important role in the study of error-correcting codes. In this paper, we study new better parameter choices in Guruswami–Sudan algorithm for the polynomial reconstruction problem. As a consequence, our result gives a better upper bound for the number of solutions for the polynomial reconstruction problem comparing with the original algorithm.     

On the Key Equation Over a Commutative Ring

We define alternant codes over a commutative ring R and a corresponding key equation. We show that when the ring is a domain, e.g. the p-adic integers, the error-locator polynomial is the unique monic minimal polynomial (equivalently, the unique shortest linear recurrence) of the finite sequence of syndromes and that it can be obtained by Algorithm MR of Norton.WhenR is a local ring, we show that the syndrome sequence may have more than one (monic) minimal polynomial, but that all the minimal polynomials coincide modulo the maximal ideal ofR . We characterise the set of minimal polynomials when R is a Hensel ring. We also apply these results to decoding alternant codes over a local ring R: it is enough to find any monic minimal polynomial over R and to find its roots in the residue field. This gives a decoding algorithm for alternant codes over a finite chain ring, which generalizes and improves a method of Interlando et. al. for BCH and Reed-Solomon codes over a Galois ring.     

Algebras Generated by Linearly Dependent Elements with Prescribed Spectra

We consider associative algebras presented by a finite set of generators and relations of special form: each generator is annihilated by some polynomial, and the sum of generators is zero. The growth of this algebra in dependence on the degrees of the polynomials annihilating the generators is studied. The tuples of degrees for which the algebras are finite-dimensional, have polynomial growth, or have exponential growth are indicated. To the tuple of degrees, we assign a graph, and the above-mentioned cases correspond to Dynkin diagrams, extended Dynkin diagrams, and the other graphs, respectively. For extended Dynkin diagrams, we indicate the hyperplane in the space of parameters (roots of the polynomials) on which the corresponding algebras satisfy polynomial identities.     

A deformation of commutative polynomial algebras in even numbers of variables

We introduce and study a deformation of commutative polynomial algebras in even numbers of variables. We also discuss some connections and applications of this deformation to the generalized Laguerre orthogonal polynomials and the interchanges of right and left total symbols of differential operators of polynomial algebras. Furthermore, a more conceptual re-formulation for the image conjecture [18] is also given in terms of the deformed algebras. Consequently, the well-known Jacobian conjecture [8] is reduced to an open problem on this deformation of polynomial algebras.     

On Reed-Solomon Codes

The complexity of decoding the standard Reed-Solomon code is a well-known open problem in coding theory. The main problem is to compute the error distance of a received word. Using the Weil bound for character sum estimate, Li and Wan showed that the error distance can be determined when the degree of the received word as a polynomial is small. In the first part, the result of Li and Wan is improved. On the other hand, one of the important parameters of an error-correcting code is the dimension. In most cases, one can only get bounds for the dimension. In the second part, a formula for the dimension of the generalized trace Reed-Solomon codes in some cases is obtained.     

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.     

渐近因子分离法及其在多项式求根中的应用

[1]提出了一种渐近分离多项式因子的方法,并考虑了在求根中的应用,但尚有许多问题没有解决,也没有给出实用的算法。其实Sebastiao,Silva早就提出过类似的方法。[1]和[2]都只考虑了f(x)没有重根的特殊情形,本文把渐近因子分离过程推广到任意f(x)的情形,并且给出了几种有实用价值的算法和两个实例。     

On the positivity of symmetric polynomial functions. Part III: Extremal polynomials of degree 4

In this paper, which is a continuation of [V. Timofte, On the positivity of symmetric polynomial functions. Part I: General results, J. Math. Anal. Appl. 284 (2003) 174-190] and [V. Timofte, On the positivity of symmetric polynomial functions. Part II: Lattice general results and positivity criteria for degrees 4 and 5, J. Math. Anal. Appl., in press], we study properties of extremal polynomials of degree 4, and we give the construction of some of them. The main results are Theorems 9, 13, 15, 16, and 18.