Relatively prime polynomials and nonsingular Hankel matrices over finite fields

The probability for two monic polynomials of a positive degree n with coefficients in the finite field Fq to be relatively prime turns out to be identical with the probability for an n×n Hankel matrix over Fq to be nonsingular. Motivated by this, we give an explicit map from pairs of coprime polynomials to nonsingular Hankel matrices that explains this connection. A basic tool used here is the classical notion of Bezoutian of two polynomials. Moreover, we give simpler and direct proofs of the general formulae for the number of m-tuples of relatively prime polynomials over Fq of given degrees and for the number of n×n Hankel matrices over Fq of a given rank.     

Necklaces,symmetries and self-reciprocal polynomials

The connection between a certain class of necklaces and self-reciprocal polynomials over finite fields is shown. For n?2, self-reciprocal polynomials of degree 2n arising from monic irreducible polynomials of degree n are shown to be either irreducible or the product or two irreducible factors which are necessarily reciprocal polynomials. Using DeBruijn's method we count the number of necklaces in this class and hence obtain a formula for the number of irreducible self-reciprocal polynomials showing that they exist for every even degree. Thus every extension of a finite field of even degree can be obtained by adjoining a root of an irreducible self-reciprocal polynomial.     

A Poisson * Negative Binomial Convolution Law for Random Polynomials over Finite Fields

Let F _q[X] denote a polynomial ring over a finite field F _q with q elements. Let 𝒫_n be the set of monic polynomials over F _q of degree n. Assuming that each of the qⁿ possible monic polynomials in 𝒫_n is equally likely, we give a complete characterization of the limiting behavior of P(Ω_n=m) as n→∞ by a uniform asymptotic formula valid for m≥1 and n−m→∞, where Ω_n represents the number (multiplicities counted) of irreducible factors in the factorization of a random polynomial in 𝒫_n. The distribution of Ω_n is essentially the convolution of a Poisson distribution with mean log n and a negative binomial distribution with parameters q and q⁻¹. Such a convolution law exhibits three modes of asymptotic behaviors: when m is small, it behaves like a Poisson distribution; when m becomes large, its behavior is dominated by a negative binomial distribution, the transitional behavior being essentially a parabolic cylinder function (or some linear combinations of the standard normal law and its iterated integrals). As applications of this uniform asymptotic formula, we derive most known results concerning P(Ω_n=m) and present many new ones like the unimodality of the distribution. The methods used are widely applicable to other problems on multiset constructions. An extension to Rényi's problem, concerning the distribution of the difference of the (total) number of irreducibles and the number of distinct irreducibles, is also presented. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 17–47, 1998     

Continuous symmetrized Sobolev inner products of order N (I)

Given a symmetrized Sobolev inner product of order N, the corresponding sequence of monic orthogonal polynomials {Qn} satisfies that Q2n(x)=Pn(x²), Q2n+1(x)=xRn(x²) for certain sequences of monic polynomials {Pn} and {Rn}. In this paper, we deduce the integral representation of the inner products such that {Pn} and {Rn} are the corresponding sequences of orthogonal polynomials. Moreover, we state a relation between both inner products which extends the classical result for symmetric linear functionals.     

Self-conjugate-reciprocal irreducible monic factors of xn − 1 over finite fields and their applications

Self-reciprocal and self-conjugate-reciprocal polynomials over finite fields have been of interest due to their rich algebraic structures and wide applications. Self-reciprocal irreducible monic factors of $x^n-1$ over finite fields and their applications have been quite well studied. In this paper, self-conjugate-reciprocal irreducible monic (SCRIM) factors of $x^n-1$ over finite fields of square order are focused on. The characterization of such factors is given together with the enumeration formula. In many cases, recursive formulas for the number of SCRIM factors of $x^n-1$ are given as well. As applications, Hermitian complementary dual cyclic codes over finite fields and Hermitian self-dual cyclic codes over finite chain rings of prime characteristic are discussed.     

Multi-degree reduction of tensor product Bézier surfaces with general boundary constraints

We propose an efficient approach to the problem of multi-degree reduction of rectangular Bézier patches, with prescribed boundary control points. We observe that the solution can be given in terms of constrained bivariate dual Bernstein polynomials. The complexity of the method is O(mn₁n₂) with m ? min(m₁, m₂), where (n₁, n₂) and (m₁, m₂) is the degree of the input and output Bézier surface, respectively. If the approximation—with appropriate boundary constraints—is performed for each patch of several smoothly joined rectangular Bézier surfaces, the result is a composite surface of global C^r continuity with a prescribed r ? 0. In the detailed discussion, we restrict ourselves to r ∈ {0, 1}, which is the most important case in practical application. Some illustrative examples are given.     

Connection coefficients for Laguerre-Sobolev orthogonal polynomials

Laguerre-Sobolev polynomials are orthogonal with respect to an inner product of the form , where α>−1, λ?0, and , the linear space of polynomials with real coefficients. If dμ(x)=xαe−xdx, the corresponding sequence of monic orthogonal polynomials {Q_n^(α,λ)(x)} has been studied by Marcellán et al. (J. Comput. Appl. Math. 71 (1996) 245-265), while if dμ(x)=δ(x)dx the sequence of monic orthogonal polynomials {L_n^(α)(x;λ)} was introduced by Koekoek and Meijer (SIAM J. Math. Anal. 24 (1993) 768-782). For each of these two families of Laguerre-Sobolev polynomials, here we give the explicit expression of the connection coefficients in their expansion as a series of standard Laguerre polynomials. The inverse connection problem of expanding Laguerre polynomials in series of Laguerre-Sobolev polynomials, and the connection problem relating two families of Laguerre-Sobolev polynomials with different parameters, are also considered.     

Roots and polynomials as Homeomorphic spaces

We provide a unified, elementary, topological approach to the classical results stating the continuity of the complex roots of a polynomial with respect to its coefficients, and the continuity of the coefficients with respect to the roots. In fact, endowing the space of monic polynomials of a fixed degree n and the space of n roots with suitable topologies, we are able to formulate the classical theorems in the form of a homeomorphism. Related topological facts are also considered.     

Maximal minors of a matrix with linear form entries

Let P be a matrix whose entries are homogeneous polynomials in n variables of degree one over an algebraically closed field. We show that the maximal minors, say m-minors, of P generate the linear space of homogeneous polynomials of degree m if P has the maximal rank m at every point of the affine n-space except the origin.     

An algorithm for the divisors of monic polynomials over a commutative ring

Gilmer and Heinzer proved that given a reduced ring R, a polynomial f divides a monic polynomial in R[X] if and only if there exists a direct sum decomposition of R = R₀ ⊕ … ⊕ R_m (m ≤ deg f), associated to a fundamental system of idempotents e₀, … , e_m, such that the component of f in each R_i[X] has degree coefficient which is a unit of R_i. We propose to give an algorithm to explicitly find such a decomposition. Moreover, we extend this result to divisors of doubly monic Laurent polynomials.     

Elementary symmetric polynomials in Shamir's scheme

The concept of k-admissible tracks in Shamir's secret sharing scheme over a finite field was introduced by Schinzel et al. (2009) [10]. Using some estimates for the elementary symmetric polynomials, we show that the track (1,…,n) over Fp is practically always k-admissible; i.e., the scheme allows to place the secret as an arbitrary coefficient of its generic polynomial even for relatively small p. Here k is the threshold and n the number of shareholders.     

The parity of the number of irreducible factors for some pentanomials

It is well known that the Stickelberger–Swan theorem is very important for determining the reducibility of polynomials over a binary field. Using this theorem the parity of the number of irreducible factors for some kinds of polynomials over a binary field, for instance, trinomials, tetranomials, self-reciprocal polynomials and so on was determined. We discuss this problem for Type II pentanomials, namely x^m+xⁿ⁺²+xⁿ⁺¹+xⁿ+1F₂[x] for even m. Such pentanomials can be used for the efficient implementation of multiplication in finite fields of characteristic two. Based on the computation of the discriminant of these pentanomials with integer coefficients, we will characterize the parity of the number of irreducible factors over F₂ and establish necessary conditions for the existence of this kind of irreducible pentanomials.Our results have been obtained in an experimental way by computing a significant number of values with Mathematica and extracting the relevant properties.     

The zeros of linear combinations of orthogonal polynomials

Let {p_n} be a sequence of monic polynomials with p_n of degree n, that are orthogonal with respect to a suitable Borel measure on the real line. Stieltjes showed that if m<n and x₁,…,x_n are the zeros of p_n with x₁<<x_n then there are m distinct intervals f the form (x_j,x_j+1) each containing one zero of p_m. Our main theorem proves a similar result with p_m replaced by some linear combinations of p₁,…,p_m. The interlacing of the zeros of linear combinations of two and three adjacent orthogonal polynomials is also discussed.     

On the Krall-type discrete polynomials

In this paper we present a unified theory for studying the so-called Krall-type discrete orthogonal polynomials. In particular, the three-term recurrence relation, lowering and raising operators as well as the second order linear difference equation that the sequences of monic orthogonal polynomials satisfy are established. Some relevant examples of q-Krall polynomials are considered in detail.     

Eigenvalue problems to compute almost optimal points for rational interpolation with prescribed poles

Explicit formulas exist for the (n,m) rational function with monic numerator and prescribed poles that has the smallest possible Chebyshev norm. In this paper we derive two different eigenvalue problems to obtain the zeros of this extremal function. The first one is an ordinary tridiagonal eigenvalue problem based on a representation in terms of Chebyshev polynomials. The second is a generalised tridiagonal eigenvalue problem which we derive using a connection with orthogonal rational functions. In the polynomial case (m = 0) both problems reduce to the tridiagonal eigenvalue problem associated with the Chebyshev polynomials of the first kind. Postdoctoral researcher FWO-Flanders.     

On the linear functionals associated to linearly related sequences of orthogonal polynomials

An inverse problem is solved, by stating that the regular linear functionals u and v associated to linearly related sequences of monic orthogonal polynomials n(Pn) and n(Qn), respectively, in the sense

     

Limit relations for the complex zeros of Laguerre and q-Laguerre polynomials

For each the nth Laguerre polynomial has an m-fold zero at the origin when α=−m. As the real variable α→−m, it has m simple complex zeros which approach 0 in a symmetric way. This symmetry leads to a finite value for the limit of the sum of the reciprocals of these zeros. There is a similar property for the zeros of the q-Laguerre polynomials and of the Jacobi polynomials and similar results hold for sums of other negative integer powers.     

Non-Unique Factorization of Polynomials Over Residue Class Rings of the Integers

We investigate non-unique factorization of polynomials in ? _{p ⁿ} [x] into irreducibles. As a Noetherian ring whose zero-divisors are contained in the Jacobson radical, ? _{p ⁿ} [x] is atomic. We reduce the question of factoring arbitrary nonzero polynomials into irreducibles to the problem of factoring monic polynomials into monic irreducibles. The multiplicative monoid of monic polynomials of ? _{p ⁿ} [x] is a direct sum of monoids corresponding to irreducible polynomials in ? _p [x], and we show that each of these monoids has infinite elasticity. Moreover, for every m ∈ ?, there exists in each of these monoids a product of 2 irreducibles that can also be represented as a product of m irreducibles.     

A quantitative Khintchine-Groshev type theorem over a field of formal series

An asymptotic formula which holds almost everywhere is obtained for the number of solutions to theDiophantine inequalities ‖qA − p‖ < Ψ(‖g‖), where A is an n x m matrix (m > 1) over the field of formal Laurent series with coefficients from a finite field, and p and q are vectors of polynomials over the same finite field.