Admissibility of kneading sequences and structure of Hubbard trees for quadratic polynomials

Hubbard trees are invariant trees connecting the points of thecritical orbits of post-critically finite polynomials. Douadyand Hubbard showed in the Orsay Notes that they encode all combinatorialproperties of the Julia sets. For quadratic polynomials, onecan describe the dynamics as a subshift on two symbols, anditinerary of the critical value is called the kneading sequence.Whereas every (pre)periodic sequence is realized by an abstractHubbard tree (see the authors’ preprint from 2007), notevery such tree is realized by a quadratic polynomial. In thispaper, we give an Admissibility Condition that describes preciselywhich sequences correspond to quadratic polynomials. We identifythe occurrence of the so-called ‘evil branch points’as the sole obstruction to being realizable. We also show howto derive the properties of periodic (branch) points in thetree (their periods, relative positions, number of arms andwhether they are evil or not) from the kneading sequence.     

On a Two-Variable Class of Bernstein–Szegő Measures

The one-variable Bernstein–Szegő theory for orthogonal polynomials on the real line is extended to a class of two-variable measures. The polynomials orthonormal in the total degree ordering and the lexicographical ordering are constructed and their recurrence coefficients discussed.      

On standard bases in rings of differential polynomials

We consider Ollivier’s standard bases (also known as differential Gröbner bases) in an ordinary ring of differential polynomials in one indeterminate. We establish a link between these bases and Levi’s reduction process. We prove that the ideal [x ^p ] has a finite standard basis (w.r.t. the so-called β-orderings) that contains only one element. Various properties of admissible orderings on differential monomials are studied. We bring up the question of whether there is a finitely generated differential ideal that does not admit a finite standard basis w.r.t. any ordering.     

Invariant Differential Operators on Certain Nilpotent Homogeneous Spaces

 Let be a nilpotent connected and simply connected Lie group, and an analytic subgroup of G. Let , be a unitary character of H and let . Suppose that the multiplicities of all the irreducible components of τ are finite. Corwin and Greenleaf conjectured that the algebra of the differential operators on the Schwartz-space of τ which commute with τ is isomorphic to the algebra of H-invariant polynomials on the affine space . We prove in this paper this conjecture under the condition that there exists a subalgebra which polarizes all generic elements in . We prove also that if is an ideal of , then the finite multiplicities of τ is equivalent to the fact that the algebra is commutative.     

On the Zero-Divergence of Equidistant Lagrange Interpolation

 In 1942, P. Szász published the surprising result that if a function f is of bounded variation on [−1, 1] and continuous at 0 then the sequence of the equidistant Lagrange interpolation polynomials converges at 0 to . In the present note we give a construction of a function continuous on [−1, 1] whose Lagrange polynomials diverge at 0. Moreover, we show that the rate of divergence attains almost the maximal possible rate.     

The vanishing ideal of a finite set of closed points in affine space

Given a finite set of closed rational points of affine space over a field, we give a Gröbner basis for the lexicographic ordering of the ideal of polynomials which vanish at all given points. Our method is an alternative to the Buchberger-Möller algorithm, but in contrast to that, we determine the set of leading terms of the ideal without solving any linear equation but by induction over the dimension of affine space. The elements of the Gröbner basis are also computed by induction over the dimension, using one-dimensional interpolation of coefficients of certain polynomials.     

On the Zero-Divergence of Equidistant Lagrange Interpolation

 In 1942, P. Szász published the surprising result that if a function f is of bounded variation on [−1, 1] and continuous at 0 then the sequence of the equidistant Lagrange interpolation polynomials converges at 0 to . In the present note we give a construction of a function continuous on [−1, 1] whose Lagrange polynomials diverge at 0. Moreover, we show that the rate of divergence attains almost the maximal possible rate. (Received 2 February 2000)     

Invariant Differential Operators on Certain Nilpotent Homogeneous Spaces

 Let be a nilpotent connected and simply connected Lie group, and an analytic subgroup of G. Let , be a unitary character of H and let . Suppose that the multiplicities of all the irreducible components of τ are finite. Corwin and Greenleaf conjectured that the algebra of the differential operators on the Schwartz-space of τ which commute with τ is isomorphic to the algebra of H-invariant polynomials on the affine space . We prove in this paper this conjecture under the condition that there exists a subalgebra which polarizes all generic elements in . We prove also that if is an ideal of , then the finite multiplicities of τ is equivalent to the fact that the algebra is commutative. (Received 15 November 2000)     

Uniformly distributed functions inGF[q,x] andGF{q,x}

Summary Let A, B, C, ... denote polynomials over the finite field GF(q). It is shown that the sequence {B_i} is uniformly distributed modulo M if the sequence {B_i+k - B_i} is uniformly distributed modulo M for all integers k>0. A similar result holds for sequences defined by functional values. Also, a result of Weyl concerning uniform distribution modulo 1 is extended to polynomials over finite fields. Entrata in Redazione il 25 febbraio 1972.     

Recursive Three-Term Recurrence Relations for?the?Jacobi Polynomials on a Triangle

Given a suitable weight on ℝ ^d , there exist many (recursive) three-term recurrence relations for the corresponding multivariate orthogonal polynomials. In principle, these can be obtained by calculating pseudoinverses of a sequence of matrices. Here we give an explicit recursive three-term recurrence for the multivariate Jacobi polynomials on a simplex. This formula was obtained by seeking the best possible three-term recurrence. It defines corresponding linear maps, which have the same symmetries as the spaces of Jacobi polynomials on which they are defined. The key idea behind this formula is that some Jacobi polynomials on a simplex can be viewed as univariate Jacobi polynomials, and for these the recurrence reduces to the univariate three-term recurrence.     

Computing Syzygies by Faug��re��s F5 algorithm

In this paper, we introduce a new algorithm for computing a set of generators for the syzygies on a sequence of polynomials. For this, we extend a given sequence of polynomials to a Gr?bner basis using Faugère??s F₅ algorithm (A new efficient algorithm for computing Gr?bner bases without reduction to zero (F ₅). ISSAC, ACM Press, pp 75?C83, 2002). We show then that if we keep all the reductions to zero during this computation, then at termination (by adding principal syzygies) we obtain a basis for the module of syzygies on the input polynomials. We have implemented our algorithm in the computer algebra system Magma, and we evaluate its performance via some examples.     

Hermite matrix polynomials and second order matrix differential equations

In this paper we introduce the class of Hermite’s matrix polynomials which appear as finite series solutions of second order matrix differential equations Y″−xAY′+BY=0. An explicit expression for the Hermite matrix polynomials, the orthogonality property and a Rodrigues’ formula are given.     

An approach to solving multiparameter algebraic problems

An approach to solving the following multiparameter algebraic problems is suggested: (1) spectral problems for singular matrices polynomially dependent on q≥2 spectral parameters, namely: the separation of the regular and singular parts of the spectrum, the computation of the discrete spectrum, and the construction of a basis that is free of a finite regular spectrum of the null-space of polynomial solutions of a multiparameter polynomial matrix; (2) the execution of certain operations over scalar and matrix multiparameter polynomials, including the computation of the GCD of a sequence of polynomials, the division of polynomials by their common divisor, and the computation of relative factorizations of polynomials; (3) the solution of systems of linear algebraic equations with multiparameter polynomial matrices and the construction of inverse and pseudoinverse matrices. This approach is based on the so-called ΔW-q factorizations of polynomial q-parameter matrices and extends the method for solving problems for one- and two-parameter polynomial matrices considered in [1–3] to an arbitrary q≥2. Bibliography: 12 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 229, 1995, pp. 191–246. Translated by V. N. Kublanovskaya.     

Divisibility of polynomials over finite fields and combinatorial applications

Consider a maximum-length shift-register sequence generated by a primitive polynomial f over a finite field. The set of its subintervals is a linear code whose dual code is formed by all polynomials divisible by f. Since the minimum weight of dual codes is directly related to the strength of the corresponding orthogonal arrays, we can produce orthogonal arrays by studying divisibility of polynomials. Munemasa (Finite Fields Appl 4(3):252–260, 1998) uses trinomials over \mathbbF₂{\mathbb{F}_2} to construct orthogonal arrays of guaranteed strength 2 (and almost strength 3). That result was extended by Dewar et al. (Des Codes Cryptogr 45:1–17, 2007) to construct orthogonal arrays of guaranteed strength 3 by considering divisibility of trinomials by pentanomials over \mathbbF₂{\mathbb{F}_2} . Here we first simplify the requirement in Munemasa’s approach that the characteristic polynomial of the sequence must be primitive: we show that the method applies even to the much broader class of polynomials with no repeated roots. Then we give characterizations of divisibility for binomials and trinomials over \mathbbF₃{\mathbb{F}_3} . Some of our results apply to any finite field \mathbbF_q{\mathbb{F}_q} with q elements.     

SomeL-functions of a polynomial ring over a finite field

An L-function involved in the enumeration of certain families of irreducible polynomials over a finite field is studied. For a number of cases, we confirm the hypothesis on zeros of that function, which is an analog of the hypothesis of Riemann and Weyl postulated for algebraic varieties over finite fields. Translated fromAlgebra i Logika, Vol. 35, No. 4, pp. 476–495, July–August, 1996.     

Computing border bases using mutant strategies

Border bases, a generalization of Gröbner bases, have actively been addressed during recent years due to their applicability to industrial problems. In cryptography and coding theory a useful application of border based is to solve zero-dimensional systems of polynomial equations over finite fields, which motivates us for developing optimizations of the algorithms that compute border bases. In 2006, Kehrein and Kreuzer formulated the Border Basis Algorithm (BBA), an algorithm which allows the computation of border bases that relate to a degree compatible term ordering. In 2007, J. Ding et al. introduced mutant strategies bases on finding special lower degree polynomials in the ideal. The mutant strategies aim to distinguish special lower degree polynomials (mutants) from the other polynomials and give them priority in the process of generating new polynomials in the ideal. In this paper we develop hybrid algorithms that use the ideas of J. Ding et al. involving the concept of mutants to optimize the Border Basis Algorithm for solving systems of polynomial equations over finite fields. In particular, we recall a version of the Border Basis Algorithm which is actually called the Improved Border Basis Algorithm and propose two hybrid algorithms, called MBBA and IMBBA. The new mutants variants provide us space efficiency as well as time efficiency. The efficiency of these newly developed hybrid algorithms is discussed using standard cryptographic examples.     

Chebycheff and Belyi Polynomials, Dessins d’Enfants, Beauville Surfaces and Group Theory

We start discussing the group of automorphisms of the field of complex numbers, and describe, in the special case of polynomials with only two critical values, Grothendieck’s program of ‘Dessins d’ enfants’, aiming at giving representations of the absolute Galois group. We describe Chebycheff and Belyi polynomials, and other explicit examples. As an illustration, we briefly treat difference and Schur polynomials. Then we concentrate on a higher dimensional analogue of the triangle curves, namely, Beauville surfaces and varieties isogenous to a product. We describe their moduli spaces, and show how the study of these varieties leads to new interesting questions in the theory of finite (simple) groups. We would like to thank Fabio Tonoli for helping us with the pictures.     

Bounded and unbounded polynomials and multilinear forms: Characterizing continuity

In this paper we prove a characterization of continuity for polynomials on a normed space. Namely, we prove that a polynomial is continuous if and only if it maps compact sets into compact sets. We also provide a partial answer to the question as to whether a polynomial is continuous if and only if it transforms connected sets into connected sets. These results motivate the natural question as to how many non-continuous polynomials there are on an infinite dimensional normed space. A problem on the lineability of the sets of non-continuous polynomials and multilinear mappings on infinite dimensional normed spaces is answered.     

Generalized weighted Sobolev spaces and applications to Sobolev orthogonal polynomials II

We present a definition of general Sobolev spaces with respect to arbitrary measures, Wh,p (Ω,μ) for 1 ≤p≤∞. In [RARP] we proved that these spaces are complete under very light conditions. Now we prove that if we consider certain general types of measures, then Cc∞ (R) is dense in thee spaces. As an application to Sobolev orthogonal polynomials, we study the boundedness of the multiplication operator. This gives an estimation of the zeroes of Sobolev orthogonal polynomials.     

The inverses of an H-space

 A multiplication on an H-space X has a left inverse λ and a right inverse ρ. They are mutual inverses and λ = ρ if and only if . In this paper we investigate the order of λ. We give an example of a multiplication with , and prove that for any finite H-complex X there are finitely many left inverses of finite order. Conditions are given for there to be infinitely many multiplications on X with the same left inverse. We then give conditions for a left inverse to have infinite order. We apply these results to specific Lie groups. Received: 15 June 2001