Correction to: Good polynomials for optimal LRC of low locality

Designs, Codes and Cryptography -     

Uniqueness of optimal mod 3 polynomials for parity

Text

In this paper, we completely characterize the quadratic polynomials modulo 3 with the largest (hence “optimal”) correlation with parity. This result is obtained by analysis of the exponential sum

     

Chebyshev polynomials are not always optimal

We are concerned with the problem of finding the polynomial with minimal uniform norm on among all polynomials of degree at most n and normalized to be 1 at c. Here, is a given ellipse with both foci on the real axis and c is a given real point not contained in . Problems of this type arise in certain iterative matrix computations, and, in this context, it is generally believed and widely referenced that suitably normalized Chebyshev polynomials are optimal for such constrained approximation problems. In this work, we show that this is not true in general. Moreover, we derive sufficient conditions which guarantee that Chebyshev polynomials are optimal. Also, some numerical examples are presented.     

An alternative class of irreducible polynomials for optimal extension fields

Optimal extension fields (OEF) are a class of finite fields used to achieve efficient field arithmetic, especially required by elliptic curve cryptosystems (ECC). In software environment, OEFs are preferable to other methods in performance and memory requirement. However, the irreducible binomials required by OEFs are quite rare. Sometimes irreducible trinomials are alternative choices when irreducible binomials do not exist. Unfortunately, trinomials require more operations for field multiplication and thereby affect the efficiency of OEF. To solve this problem, we propose a new type of irreducible polynomials that are more abundant and still efficient for field multiplication. The proposed polynomial takes the advantage of polynomial residue arithmetic to achieve high performance for field multiplication which costs O(m ^3/2) operations in \mathbbF_p{\mathbb{F}_p} . Extensive simulation results demonstrate that the proposed polynomials roughly outperform irreducible binomials by 20% in some finite fields of medium prime characteristic. So this work presents an interesting alternative for OEFs.     

Jensen's Inequality for polynomials with concentration at low degrees

Summary We give a generalization of Jensen's Inequality, valid for polynomials having some concentration at low degrees. We investigate the constants involved, both from a theoretical and a numerical point of view.     

The Atkin orthogonal polynomials for congruence subgroups of low levels

The aim of this paper is to give the explicit formulae for the orthogonal functions of the Atkin inner product for the noncompact arithmetic triangular groups and to relate these functions to the supersingular elliptic curves. Also, we state the Atkin orthogonal polynomials for the classical well known group Γ(2). The author was partially supported by the Grant-in-Aid for Young Scientists (B) (No. 14740015) Japan Society for the Promotion of Science.     

Generalized faber polynomials and an optimal error recovery algorithm

This paper deals with the problem of approximate evaluation of a certain class of analytic functions. The choice of this class is motivated by the problem of the summation of moment sequences. By assuming that the information about the function is given by its Taylor coefficients, we are able to establish a lower bound on the error of an arbitrary algorithm. We present also an algorithm whose error is asymptotically at most twice the lower bound, thereby showing that our estimate is asymptotically sharp.     

Design of optimal observers with specified eigenvalues via shifted Legendre polynomials

The quadratic performance measure of estimation errors in approximated by using the Legendre polynomial approach for the design of optimal observers with specified distinct and multiple eigenvalues. This method is simple as compared with other design techniques of optimal observers. One example is illustrated, and only a small number (m=6) of shifted Legendre series are needed to produce a much better result than that obtained by the convenient block-pulse function.     

Computation of the canonical polynomials and applications to some optimal control problems

The Tau method is a numerical technique that consists in constructing polynomial approximate solutions for ordinary differential equations. This method has two approaches: operational and recursive. The former converts the differential problem to a matrix problem and produces approximations in terms of a prescribed orthogonal polynomials basis. In the recursive approach, we construct approximate solutions in terms of a special set of polynomials {Q _k (t); k?=?0, 1, 2...} called canonical polynomials basis. In some cases, the Q _k ??s can be obtained explicitly through a recursive formula. But no analogous formulae are reported in the literature for the general cases. In this paper, utilizing the operational Tau method, we develop an algorithm that allows to generate those canonical polynomials iteratively and explicitly. In addition, we demonstrate the capability of the operational Tau method in treating quadratic optimal control problems governed by ordinary differential equations.     

On the roots of polynomials with concentration at low degrees

We investigate the roots of polynomials with concentration at low degrees, and prove that there is an open disk, the radius of which depends only on d and k, such that any polynomial with concentration d at degree k has at most k roots in this disk. We also give numerical estimates for this radius.     

Coding for locality in reconstructing permutations

The problem of storing permutations in a distributed manner arises in several common scenarios, such as efficient updates of a large, encrypted, or compressed data set. This problem may be addressed in either a combinatorial or a coding approach. The former approach boils down to presenting large sets of permutations with locality, that is, any symbol of the permutation can be computed from a small set of other symbols. In the latter approach, a permutation may be coded in order to achieve locality. Both approaches must present low query complexity to allow the user to find an element efficiently. We discuss both approaches, and give a particular focus to the combinatorial one. In the combinatorial approach, we provide upper and lower bounds for the maximal size of a set of permutations with locality, and provide several simple constructions which attain the upper bound. In cases where the upper bound is not attained, we provide alternative constructions using a variety of tools, such as Reed-Solomon codes, permutation polynomials, and multi-permutations. In addition, several low-rate constructions of particular interest are discussed. In the coding approach we discuss an alternative representation of permutations, present a paradigm for supporting arbitrary powers of the stored permutation, and conclude with a proof of concept that permutations may be stored more efficiently than ordinary strings over the same alphabet.     

Infinite sums for Fibonacci polynomials and Lucas polynomials

The Ramanujan Journal - In this paper we establish certain infinite sums involving many arithmetical functions and the Fibonacci polynomials or the Lucas polynomials. Several of the sums are given...     

Combinatorial formula for Macdonald polynomials and generic Macdonald polynomials

We give a direct proof of the combinatorial formula for interpolation Macdonald polynomials by introducing certain polynomials, which we call generic Macdonald polynomials, and which depend on d additional parameters and specialize to all Macdonald polynomials of degree d. The form of these generic polynomials is that of a Bethe eigenfunction and they imitate, on a more elementary level, the R-matrix construction of quantum immanants.     

Analysis of an algorithm for generating locally optimal meshes for approximation by discontinuous piecewise polynomials

This paper discusses the problem of constructing a locally optimal mesh for the best approximation of a given function by discontinuous piecewise polynomials. In the one-dimensional case, it is shown that, under certain assumptions on the approximated function, Baines' algorithm [M.J. Baines, Math. Comp., 62 (1994), pp. 645-669] for piecewise linear or piecewise constant polynomials produces a mesh sequence which converges to an optimal mesh. The rate of convergence is investigated. A two-dimensional modification of this algorithm is proposed in which both the nodes and the connection between the nodes are self-adjusting. Numerical results in one and two dimensions are presented.