Extensions of homogeneous polynomials on c 0(l 2 i )

We show that a 2-homogeneous polynomial on the complex Banach space c ₀ l ₂ ⁱ ) is norm attaining if and only if it is finite (i.e, depends only on finite coordinates). As the consequence, we show that there exists a unique norm-preserving extension for norm-attaining 2-homogeneous polynomials on c ₀(l ₂ ⁱ ). The second author was supported by FAPESP, Brazil, Research Grant 01/04220-8.     

A Superconsistent Chebyshev Collocation Method for Second-Order Differential Operators

A standard way to approximate the model problem –u =f, with u(±1)=0, is to collocate the differential equation at the zeros of T _n : x _i , i=1,...,n–1, having denoted by T _n the nth Chebyshev polynomial. We introduce an alternative set of collocation nodes z _i , i=1,...,n–1, which will provide better numerical performances. The approximated solution is still computed at the nodes {x _i }, but the equation is required to be satisfied at the new nodes {z _i }, which are determined by asking an extra degree of consistency in the discretization of the differential operator.     

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.     

Automorphisms for Skew PBW Extensions and Skew Quantum Polynomial Rings

In this work, I study the automorphisms of skew PBW extensions and skew quantum polynomials. I use Artamonov's works as reference for getting the principal results about automorphisms for generic skew PBW extensions and generic skew quantum polynomials. In general, if I have an endomorphism on a generic skew PBW extension and there are some x _i , x _j , x _u such that the endomorphism is not zero on these elements and the principal coefficients are invertible, then endomorphisms act over x _i as a _i x _i for some a _i in the ring of coefficients. Of course, this is valid for quantum polynomial rings, with r = 0, as such Artamonov shows in his work. We use this result for giving some more general results for skew PBW extensions, using filtred-graded techniques. Finally, I use localization to characterize some class the endomorphisms and automorphisms for skew PBW extensions and skew quantum polynomials over Ore domains.     

An Isolated Umbilical Point of the Graph of a Homogeneous Polynomial

Suppose that the origin o of R ³ is an isolated umbilical point of the graph of a homogeneous polynomial in two real variables of degree k3. Then we see that the index of o is an element of the set 1–k/2+i ^[k/2] _i=0. Moreover, we see that each element of 1–k/2+i ^[k/2] _i=0 may be the index of o on the graph of a suitable homogeneous polynomial of degree k.     

On the existence of the best discrete approximation in norm by reciprocals of real polynomials

For the given data (w_i,x_i,y_i), i=1,…,M, we consider the problem of existence of the best discrete approximation in l_p norm (1≤p<∞) by reciprocals of real polynomials. For this problem, the existence of best approximations is not always guaranteed. In this paper, we give a condition on data which is necessary and sufficient for the existence of the best approximation in l_p norm. This condition is theoretical in nature. We apply it to obtain several other existence theorems very useful in practice. Some illustrative examples are also included.     

On linearly related sequences of derivatives of orthogonal polynomials

We discuss an inverse problem in the theory of (standard) orthogonal polynomials involving two orthogonal polynomial families (P_n)_n and (Q_n)_n whose derivatives of higher orders m and k (resp.) are connected by a linear algebraic structure relation such as

for all n=0,1,2,…, where M and N are fixed nonnegative integer numbers, and r_i,n and s_i,n are given complex parameters satisfying some natural conditions. Let u and v be the moment regular functionals associated with (P_n)_n and (Q_n)_n (resp.). Assuming 0mk, we prove the existence of four polynomials Φ_M+m+i and Ψ_N+k+i, of degrees M+m+i and N+k+i (resp.), such that

the (k−m)th-derivative, as well as the left-product of a functional by a polynomial, being defined in the usual sense of the theory of distributions. If k=m, then u and v are connected by a rational modification. If k=m+1, then both u and v are semiclassical linear functionals, which are also connected by a rational modification. When k>m, the Stieltjes transform associated with u satisfies a non-homogeneous linear ordinary differential equation of order k−m with polynomial coefficients.     

Selection in Monotone Matrices and Computingkth Nearest Neighbors

Anm×nmatrix =(a_{i, j}), 1≤i≤mand 1≤j≤n, is called atotally monotonematrix if for alli₁, i₂, j₁, j₂, satisfying 1≤i₁<i₂≤m, 1≤j₁<j₂≤n.[formula]We present an[formula]time algorithm to select thekth smallest item from anm×ntotally monotone matrix for anyk≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a setS={p₁,…, p_n} ofnpoints in convex position and a vectork={k₁,…, k_n}, we also present anO(n^4/3log^c n) algorithm to compute thek_ith nearest neighbor ofp_ifor everyi≤n; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points ofSare arbitrary, then thek_ith nearest neighbor ofp_i, for alli≤n, can be computed in timeO(n^7/5 log^c n), which also improves upon the previously best-known result.     

Nonlinear functional equations satisfied by orthogonal polynomials

Let c be a linear functional defined by its moments c(xⁱ)=c_i for i=0,1,…. We proved that the nonlinear functional equations P(t)=c(P(x)P(αx+t)) and P(t)=c(P(x)P(xt)) admit polynomial solutions which are the polynomials belonging to the family of formal orthogonal polynomials with respect to a linear functional related to c. This equation relates the polynomials of the family with those of the scaled and shifted family. Other types of nonlinear functional equations whose solutions are formal orthogonal polynomials are also presented. Applications to Legendre and Chebyshev polynomials are given. Then, orthogonality with respect to a definite inner product is studied. When c is an integral functional with respect to a weight function, the preceding functional equations are nonlinear integral equations, and these results lead to new characterizations of orthogonal polynomials on the real line, on the unit circle, and, more generally, on an algebraic curve.     

Sparse direct factorizations through unassembled hyper-matrices

We set out to efficiently compute the solution of a sequence of linear systems A_ix_i = b_i, where the matrix A_i is tightly related to matrix A_{i –1}. In the setting of an hp -adaptive Finite Element Method, the sequence of matrices A_i results from successive local refinements of the problem domain. At any step i > 1, a factorization already exists and it is the updated linear system relative to the refined mesh for which a factorization must be computed in the least amount of time. This observation holds the promise of a tremendous reduction in the cost of an individual refinement step. We argue that traditional matrix storage schemes, whether dense or sparse, are a bottleneck, limiting the potential efficiency of the solvers. We propose a new hierarchical data structure, the Unassembled Hyper-Matrix (UHM), which allows the matrix to be stored as a tree of unassembled element matrices, hierarchically ordered to mirror the refinement history of the physical domain. The factorization of such an UHM proceeds in terms of element matrices, only assembling nodes when they need to be eliminated. Efficiency comes in terms of both performance and space requirements. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Distance matrices for points on a line,on a circle,and at the vertices of ann-dimensional cube

Forn pointsA _i ,i=1, 2, ...,n, in Euclidean space ℝ ^m , the distance matrix is defined as a matrix of the form D=(D _i ,j) _i ,j=1,...,n, where theD _i ,j are the distances between the pointsA _i andA _j . Two configurations of pointsA _i ,i=1, 2,...,n, are considered. These are the configurations of points all lying on a circle or on a line and of points at the vertices of anm-dimensional cube. In the first case, the inverse matrix is obtained in explicit form. In the second case, it is shown that the complete set of eigenvectors is composed of the columns of the Hadamard matrix of appropriate order. Using the fact that distance matrices in Euclidean space are nondegenerate, several inequalities are derived for solving the system of linear equations whose matrix is a given distance matrix. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 127–138, July, 1995.     

Proof of Two Conjectures of Brenti and Simion on Kazhdan-Lusztig Polynomials

We find an explicit formula for the Kazhdan-Lusztig polynomials P _ui,a,v _i of the symmetric group (n) where, for a, i, n such that 1 a i n, we denote by u _i,a = s _a s _a+1 ··· s _i–1 and by v _i the element of (n) obtained by inserting n in position i in any permutation of (n – 1) allowed to rise only in the first and in the last place. Our result implies, in particular, the validity of two conjectures of Brenti and Simion [4, Conjectures 4.2 and 4.3], and includes as a special case a result of Shapiro, Shapiro and Vainshtein [13, Theorem 1]. All the proofs are purely combinatorial and make no use of the geometry of the corresponding Schubert varieties.     

Constructing set systems with prescribed intersection sizes

Let f be an n-variable polynomial with positive integer coefficients, and let be a set system on the n-element universe. We define a set system and prove that f(H_i1∩H_i2∩∩H_ik)=|G_i1∩G_i2∩∩G_ik|, for any 1km, where f(H_i1∩H_i2∩∩H_ik) denotes the value of f on the characteristic vector of H_i1∩H_i2∩∩H_ik. The construction of is a straightforward polynomial-time algorithm from the set system and the polynomial f. In this paper we use this algorithm for constructing set systems with prescribed intersection sizes modulo an integer. As a by-product of our method, some upper bounds on the number of sets in set systems with prescribed intersection sizes are extended.     

Divisibility among power GCD matrices and among power LCM matrices on three coprime divisor chains

Let h be a positive integer and S?=?{x ₁,?…?,?x _h } be a set of h distinct positive integers. We say that the set S is a divisor chain if x _σ(1) ∣?…?∣ x _σ(h) for a permutation σ of {1,?…?,?h}. If the set S can be partitioned as S?=?S ₁?∪?S ₂?∪?S ₃, where S ₁, S ₂ and S ₃ are divisor chains and each element of S _i is coprime to each element of S _j for all 1?≤?i?<?j?≤?3, then we say that the set S consists of three coprime divisor chains. The matrix having the ath power (x _i , x _j ) ^a of the greatest common divisor of x _i and x _j as its i, j-entry is called the ath power greatest common divison (GCD) matrix on S, denoted by (S ^?a ). The ath power least common multiple (LCM) matrix [S ^?a ] can be defined similarly. In this article, let a and b be positive integers and let S consist of three coprime divisor chains with 1?∈?S. We show that if a?∣?b, then the ath power GCD matrix (S ^?a ) (resp., the ath power LCM matrix [S ^?a ]) divides the bth power GCD matrix (S ^?b ) (resp., the bth power LCM matrix [S ^?b ]) in the ring M _h (Z) of h?×?h matrices over integers. We also show that the ath power GCD matrix (S ^?a ) divides the bth power LCM matrix [S ^?b ] in the ring M _h (Z) if a?∣?b. However, if a???b, then such factorizations are not true. Our results extend Hong's and Tan's theorems and also provide further evidences to the conjectures of Hong raised in 2008.     

An extremal property of Hermite polynomials

Let H_n be the nth Hermite polynomial, i.e., the nth orthogonal on polynomial with respect to the weight w(x)=exp(−x²). We prove the following: If f is an arbitrary polynomial of degree at most n, such that |f||H_n| at the zeros of H_n+1, then for k=1,…,n we have f^(k)H_n^(k), where · is the norm. This result can be viewed as an inequality of the Duffin and Schaeffer type. As corollaries, we obtain a Markov-type inequality in the norm, and estimates for the expansion coefficients in the basis of Hermite polynomials.     

Gersgorin variations II: On themes of Fan and Gudkov

Assume F={f₁,. . .,f_n} is a family of nonnegative functions of n−1 nonnegative variables such that, for every matrix A of order n, |a_ii|>f_i (moduli of off-diagonal entries in row i of A) for all i implies A nonsingular. We show that there is a positive vector x, depending only on F, such that for all A=(a_ij), and all i, f_i≥∑_j|a_ij|{x_j}/x_i. This improves a theorem of Ky Fan, and yields a generalization of a nonsingularity criterion of Gudkov. Dedicated to Charles A. Micchelli, in celebration of his 60th birthday and our 30 years of friendship     

Matrices associated with arithmetical functions

Let f be an arithmetical function and S={x ₁,x ₂,…,x_n } a set of distinct positive integers. Denote by [f(x_i ,x_j }] the n×n matrix having f evaluated at the greatest common divisor (x_i ,x_j ) of x_i , and x_j as its i j-entry. We will determine conditions on f that will guarantee the matrix [f(x_i ,x_j )] is positive definite and, in fact, has properties similar to the greatest common divisor (GCD) matrix

[(x_i ,x_j )] where f is the identity function. The set S is gcd-closed if (x_i ,x_j )∈S for 1≤ i j ≤ n. If S is gcd-closed, we calculate the determinant and (if it is invertible) the inverse of the matrix [f(x_i ,x_j )]. Among the examples of determinants of this kind are H. J. S. Smith's determinant det[(i,j)].     

An asymptotic property of gap series. II

An upper bound estimate in the law of the iterated logarithm for Σf(n _k ω) where n_k+1∫n_k≧ 1 + ck ^-α (α≧0) is investigated. In the case α<1/2, an upper bound had been given by Takahashi [15], and the sharpness of the bound was proved in our previous paper [8]. In this paper it is proved that the upper bound is still valid in case α≧1/2 if some additional condition on {n _k} is assumed. As an application, the law of the iterated logarithm is proved when {n _k} is the arrangement in increasing order of the set B(τ)={₁ ⁱ ₁...q_τ ⁱ _τ|i₁,...,i_τ∈N ₀}, where τ≧ 2, N ₀=NU{0}, and q ₁,...,q _τ are integers greater than 1 and relatively prime to each others. This revised version was published online in June 2006 with corrections to the Cover Date.     

Relative asymptotics and Fourier series of orthogonal polynomials with a discrete Sobolev inner product

Let μ be a finite positive Borel measure supported in [−1,1] and introduce the discrete Sobolev-type inner product

where the mass points a_k belong to [−1,1], M_k,i0, i=0,…,N_k−1, and M_k,Nk>0. In this paper, we study the asymptotics of the Sobolev orthogonal polynomials by comparison with the orthogonal polynomials with respect to the measure μ and we prove that they have the same asymptotic behaviour. We also study the pointwise convergence of the Fourier series associated to this inner product provided that μ is the Jacobi measure. We generalize the work done by F. Marcellán and W. Van Assche where they studied the asymptotics for only one mass point in [−1,1]. The same problem with a finite number of mass points off [−1,1] was solved by G. López, F. Marcellán and W. Van Assche in a more general setting: they consider the constants M_k,i to be complex numbers. As regards the Fourier series, we continue the results achieved by F. Marcellán, B. Osilenker and I.A. Rocha for the Jacobi measure and mass points in .     

Breakdown and near-breakdown control in the CGS algorithm using stochastic arithmetic

In the Conjugate-Gradient-Squared method, a sequence of residualsr _k defined byr _k=P _k ² (A)r₀ is computed. Coefficients of the polynomialsP _k may be computed as a ratio of scalar products from the theory of formal orthogonal polynomials. When a scalar product in a denominator is zero or very affected by round-off errors, situations of breakdown or near-breakdown appear. Using floating point arithmetic on computers, such situations are detected with the use of _i in some ordering relations like |x _i . The user has to choose the _i himself and these choices condition entirely the efficient detection of breakdown or near-breakdown. The subject of this paper is to show how stochastic arithmetic eliminates the problem of the _i with the estimation of the accuracy of some intermediate results.