On arithmetical algorithms over finite fields

Standard methods for calculating over GF(pⁿ), the finite field of pⁿ elements, require an irreducible polynomial of degree n with coefficients in GF(p). Such a polynomial is usually obtained by choosing it randomly and then verifying that it is irreducible, using a probabilistic algorithm. If it is not, the procedure is repeated. Here we given an explicit basis, with multiplication table, for the fields GF(p^pk), for k = 0, 1, 2,…, and their union. This leads to efficient computational methods, not requiring the preliminary calculation of irreducible polynomials over finite fields and, at the same time, yields a simple recursive formula for irreducible polynomials which generate the fields. The fast Fourier transform (FFT) is a method for efficiently evaluating (or interpolating) a polynomial of degree < n at all of the nth roots of unity, i.e., on the finite multiplicate subgroups of F, in O(nlogn) operations in the underlying field. We give an analogue of the fast Fourier transform which efficiently evaluates a polynomial on some of the additive subgroups ofF. This yields new “fast” algorithms for polynomial computation.     

An analysis of the solution set to a homotopy equation between polynomials with real coefficients

We investigate the structure of the solution setS to a homotopy equationH(Z,t)=0 between two polynomialsF andG with real coefficients in one complex variableZ. The mapH is represented asH(x+iy, t)=h ₁(x, y, t)+ih ₂(x, y, t), whereh ₁ andh ₂ are polynomials from ℝ² × [0,1] into ℝ and i is the imaginary unit. Since all the coefficients ofF andG are real, there is a polynomialh ₃ such thath ₂(x, y, t)=yh₃(x, y, t). Then the solution setS is divided into two sets {(x, t)∶h ₁(x, 0, t)=0} and {(x+iy, t)∶h ₁(x, y, t)=0,h ₃(x, y, t)=0}. Using this division, we make the structure ofS clear. Finally we briefly explain the structure of the solution set to a homotopy equation between polynomial systems with real coefficients in several variables.     

Existence of subgraph with orthogonal (g,f)-factorization

Simple graphs are considered. Let G be a graph andg(x) andf(x) integer-valued functions defined on V(G) withg(x)⩽f(x) for everyxɛV(G). For a subgraphH ofG and a factorizationF=|F ₁,F ₂,⃛,F ₁| ofG, if |E(H)∩E(F ₁)|=1,1⩽i⩽j, then we say thatF orthogonal toH. It is proved that for an (mg(x)+k,mf(x) -k)-graphG, there exists a subgraphR ofG such that for any subgraphH ofG with |E(H)|=k,R has a (g,f)-factorization orthogonal toH, where 1⩽k<m andg(x)⩾1 orf(x)⩾5 for everyxɛV(G). Project supported by the Chitia Postdoctoral Science Foundation and Chuang Xin Foundation of the Chinese Academy of Sciences.     

Some Algebraic Methods for Calculating the Number of Colorings of a Graph

With an arbitrary graph G having n vertices and m edges, and with an arbitrary natural number p, we associate in a natural way a polynomial R(x ₁,...,x _n) with integer coefficients such that the number of colorings of the vertices of the graph G in p colors is equal to p ^m-n R(0,...,0). Also with an arbitrary maximal planar graph G, we associate several polynomials with integer coefficients such that the number of colorings of the edges of the graph G in 3 colors can be calculated in several ways via the coefficients of each of these polynomials. Bibliography: 2 titles.     

Polynomials on graphs

Let G be a simple graph with adjacency matrix A, and p(x) a polynomial with rational coefficients. If p(A) is the adjacency matrix of a graph, we denote that graph by p(G). We consider the question: Given a graph G, which polynomials p(x) give rise to a graph p(G) and what are those graphs? We give a complete answer if G is a distance-regular graph. We then derive some general relations between the polynomials p(x), the spectrum of A, and the automorphism group of G.     

A polynomial dual of partitions

Let P(x) = Σ_i=0ⁿa_ixⁱ be a nonnegative integral polynomial. The polynomial P(x) is m-graphical, and a multi-graph G a realization of P(x), provided there exists a multi-graph G containing exactly P(1) points where a_i of these points have degree i for 0≤i≤n. For multigraphs G, H having polynomials P(x), Q(x) and number-theoretic partitions (degree sequences) π, ?, the usual product P(x)Q(x) is shown to be the polynomial of the Cartesian product G × H, thus inducing a natural product π? which extends that of juxtaposing integral multiple copies of ?. Skeletal results are given on synthesizing a multi-graph G via a natural Cartesian product G₁ × … × G_k having the same polynomial (partition) as G. Other results include an elementary sufficient condition for arbitrary nonnegative integral polynomials to be graphical.     

Estimation of the parameters for unstable AR models

ＥＳＴＩＭＡＴＩＯＮＯＦＴＨＥＰＡＲＡＭＥＴＥＲＳＦＯＲＵＮＳＴＡＢＬＥＡＲＭＯＤＥＬＳＡＮＨｏＮＧＺＨＩ（安鸿志）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ,ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅ,Ｂｅｉｊｉｎｇ１０...     

On finite Moufang polygons

We show that a finite generalized polygon Γ is Moufang with respect to a groupG if and only if for every flag {x, y} of Γ, the subgroupG ₁(x, y) ofG fixing every element incident with one ofx, y acts transitively on the set of apartments containing the elementsu, x, y, w, whereu≠y (resp.w≠x) is an arbitrary element incident withx (resp.y). Research Associate at the National Fund of Scientific Research of Belgium. Research partially supported by NSF Grant DMS-8901904.     

Center conditions III: Parametric and model center problems

We consider an Abel equation (*)y’=p(x)y ² +q(x)y ³ withp(x), q(x) polynomials inx. A center condition for (*) (closely related to the classical center condition for polynomial vector fields on the plane) is thaty ₀=y(0)≡y(1) for any solutiony(x) of (*). Folowing [7], we consider a parametric version of this condition: an equation (**)y’=p(x)y ² +εq(x)y ³ p, q as above, ε ∈ ℂ, is said to have a parametric center, if for any ɛ and for any solutiony(ɛ,x) of (**)y(ɛ, 0)≡y(ɛ, 1).. We give another proof of the fact, shown in [6], that the parametric center condition implies vanishing of all the momentsm _k (1), wherem _k (x)=∫ ₀ ^{x pk} (t)q(t)(dt),P(x)=∫ ₀ ^x p(t)dt. We investigate the structure of zeroes ofm _k (x) and generalize a “canonical representation” ofm _k (x) given in [7]. On this base we prove in some additional cases a composition conjecture, stated in [6, 7] for a parametric center problem. The research of the first and the third author was supported by the Israel Science Foundation, Grant No. 101/95-1 and by the Minerva Foundation.     

Extended iterative methods for the solution of operator equations

Summary Given an iterative methodM ₀, characterized byx ^(k+1=G ₀(x( ^k )) (k0) (x(⁰) prescribed) for the solution of the operator equationF(x)=0, whereF:XX is a given operator andX is a Banach space, it is shown how to obtain a family of methodsM _p characterized byx ^(k+1=G _p (x( ^k )) (k0) (x(⁰) prescribed) with order of convergence higher than that ofM _o. The infinite dimensional multipoint methods of Bosarge and Falb [2] are a special case, in whichM ₀ is Newton's method.Analogues of Theorems 2.3 and 2.36 of [2] are proved for the methodsM _p, which are referred to as extensions ofM ₀. A number of methods with order of convergence greater than two are discussed and existence-convergence theorems for some of them are proved.Finally some computational results are presented which illustrate the behaviour of the methods and their extensions when used to solve systems of nonlinear algebraic equations, and some applications currently being investigated are mentioned.     

Equidistribution of sparse sequences on nilmanifolds

We study equidistribution properties of nil-orbits (b ⁿ x) _n∈ℕ when the parameter n is restricted to the range of some sparse sequence that is not necessarily polynomial. For example, we show that if X = G/Γ is a nilmanifold, b ∈ G is an ergodic nilrotation, and c ∈ ℝ \ ℤ is positive, then the sequence $ (b^{[n^c ]} x)_{n \in \mathbb{N}} $ (b^{[n^c ]} x)_{n \in \mathbb{N}} is equidistributed in X for every x ∈ X. This is also the case when n ^c is replaced with a(n), where a(t) is a function that belongs to some Hardy field, has polynomial growth, and stays logarithmically away from polynomials, and when it is replaced with a random sequence of integers with sub-exponential growth. Similar results have been established by Boshernitzan when X is the circle.     

Admissible wavelets on the Siegel domain of type one

LetSp(n, R) be the sympletic group, and letK _n * be its maximal compact subgroup. ThenG=Sp(n,R)/K _n * can be realized as the Siegel domain of type one. The square-integrable representation ofG gives the admissible wavelets AW and wavelet transform. The characterization of admissibility condition in terms of the Fourier transform is given. The Bergman kernel follows from the viewpoint of coherent state. With the Laguerre polynomials, Hermite polynomials and Jacobi polynomials, two kinds of orthogonal bases for AW are given, and they then give orthogonal decompositions ofL ²-space on the Siegel domain of type one ℒ(ℋ _n , |y| *dxdy). Project supported in part by the National Natural Science Foundation of China (Grant No. 19631080).     

A counterexample in copositive approximation

The present paper gives a converse result by showing that there exists a functionf ∈C _[−1,1], which satisfies that sgn(x)f(x) ≥ 0 forx ∈ [−1, 1], such that {fx75-1} whereE _n ⁽⁰⁾ (f, 1) is the best approximation of degreen tof by polynomials which are copositive with it, that is, polynomialsP withP(x(f(x) ≥ 0 for allx ∈ [−1, 1],E _n(f) is the ordinary best polynomial approximation off of degreen.     

Center conditions II: Parametric and model center problems

We consider an Abel equation (*)y’=p(x)y ² +q(x)y ³ withp(x), q(x) polynomials inx. A center condition for (*) (closely related to the classical center condition for polynomial vector fields on the plane) is thaty ₀=y(0)≡y(1) for any solutiony(x) of (*). We introduce a parametric version of this condition: an equation (**)y’=p(x)y ² +εq(x)y ³ p, q as above, ℂ, is said to have a parametric center, if for any ε and for any solutiony(ε,x) of (**),y(ε,0)≡y(ε,1). We show that the parametric center condition implies vanishing of all the momentsm _k (1), wherem _k (x)=∫ ₀ ^{x pk} (t)q(t)(dt),P(x)=∫ ₀ ^x p(t)dt. We investigate the structure of zeroes ofm _k (x) and on this base prove in some special cases a composition conjecture, stated in [10], for a parametric center problem. The research of the first and the third author was supported by the Israel Science Foundation, Grant No. 101/95-1 and by the Minerva Foundation.     

Simple algorithms for approximating all roots of a polynomial with real roots

We present a simple algorithm for approximating all roots of a polynomial p(x) when it has only real roots. The algorithm is based on some interesting properties of the polynomials appearing in the Extended Euclidean Scheme for p(x) and p′(x). For example, it turns out that these polynomials are orthogonal; as a consequence, we are able to limit the precision required by our algorithm in intermediate steps. A parallel implementation of this algorithm yields a P-uniform NC₂ circuit, and the bit complexity of its sequential implementation is within a polylog factor of the bit complexity of the best known algorithm for the problem.     

Approximate solution of differential equations with the use of asymptotic polynomials

We consider an approximate solution of differential equations with initial and boundary conditions. To find a solution, we use asymptotic polynomials Q _n ^f (x) of the first kind based on Chebyshev polynomials T _n (x) of the first kind and asymptotic polynomials G _n ^f (x) of the second kind based on Chebyshev polynomials U _n (x) of the second kind. We suggest most efficient algorithms for each of these solutions. We find classes of functions for which the approximate solution converges to the exact one. The remainder is represented as an expansion in linear functionals {L _n ^f } in the first case and {M _n ^f } in the second case, whose decay rate depends on the properties of functions describing the differential equation.     

On a problem of (0,2)-interpolation

The object in this paper is to consider the problem of existence, uniqueness, explicit representation of (0,2)-interpolation on the zeros of (1−x²)P_n−1(x)/x when n is odd, where P_n−1 denotes Legendre polynomial of degreen−1, and the problem of convergence of interpolatory polynomials.     

Classification of all noncommutative polynomials whose Hessian has negative signature one and a noncommutative second fundamental form

Every symmetric polynomial p = p(x) = p(x ₁,..., x _g ) (with real coefficients) in g noncommuting variables x ₁,..., x _g can be written as a sum and difference of squares of noncommutative polynomials:

Differential operators associated with zonal polynomials. II

Summary LetC _κ(S) be the zonal polynomial of the symmetricm×m matrixS=(s_ij), corresponding to the partition κ of the non-negative integerk. If ∂/∂S is them×m matrix of differential operators with (i, j)th entry ((1+δ_ij)∂/∂s_ij)/2, δ being Kronecker's delta, we show that C_k(∂/∂S)C_λ(S)=k!δ_λkC_k(I), where λ is a partition ofk. This is used to obtain new orthogonality relations for the zonal polynomials, and to derive expressions for the coefficients in the zonal polynomial expansion of homogenous symmetric polynomials.     

Where does the sup norm of a weighted polynomial live?

A characterization is given of the sets supporting the uniform norms of weighted polynomials [w(x)] ⁿ P _n (x), whereP _n is any polynomial of degree at mostn. The (closed) support ∑ ofw(x) may be bounded or unbounded; of special interest is the case whenw(x) has a nonempty zero setZ. The treatment of weighted polynomials consists of associating each admissible weight with a certain functional defined on subsets of ∑ —Z. One main result of this paper states that there is a unique compact set (independent ofn andP _n ) maximizing this functional that contains the points where the norms of weighted polynomials are attained. The distribution of the zeros of Chebyshev polynomials corresponding to the weights [w(x)] ⁿ is also studied. The main theorems give a unified method of investigating many particular examples. Applications to weighted approximation on the real line with respect to a fixed weight are included.