Weighted simultaneous Chebyshev approximation

In this paper we discuss the problem of weighted simultaneous Chebyshev approximation to functions f₁,…f_m ε C(X) (1 m ∞), i.e., we wish to minimize the expression {∑^m_{j = 1} λ_j¦f_j − q¦^p}^1/p∞, where λ_j > 0, ∑^m_{j = 1} λ_j = 1, p 1. For this problem we establish the main theorems of the Chebyshev theory, which include the theorems of existence, alternation, de La Vallée Poussin, uniqueness, strong uniqueness, as well as that of continuity of the best approximation operator, etc.     

Equations on the semidirect product of a finite semilattice by a finite commutative monoid

LetCom _t,q denote the variety of finite monoids that satisfy the equationsxy=yx andx ^t =x ^t+q . The varietyCom _1,1 is the variety of finite semilattices also denoted byJ ₁. In this paper, we consider the product varietyJ ₁*Com _t,q generated by all semidirect products of the formM*N withM∈J ₁ andN∈Com _t,q . We give a complete sequence of equations forJ ₁*Com _t,q implying complete sequences of equations forJ ₁*(Com∩A),J ₁*(Com∩G) andJ ₁*Com, whereCom denotes the variety of finite commutative monoids,A the variety of finite aperiodic monoids andG the variety of finite groups. This material is based upon work supported by the National Science Foundation under Grants No. CCR-9101800 and CCR-9300738. Many thanks to the referee for his valuable comments and suggestions.     

A Chromatic Symmetric Function in Noncommuting Variables

Stanley (Advances in Math. 111, 1995, 166–194) associated with a graph G a symmetric function X _G which reduces to G's chromatic polynomial under a certain specialization of variables. He then proved various theorems generalizing results about , as well as new ones that cannot be interpreted on the level of the chromatic polynomial. Unfortunately, X _G does not satisfy a Deletion-Contraction Law which makes it difficult to apply the useful technique of induction. We introduce a symmetric function Y _G in noncommuting variables which does have such a law and specializes to X _G when the variables are allowed to commute. This permits us to further generalize some of Stanley's theorems and prove them in a uniform and straightforward manner. Furthermore, we make some progress on the (3 + 1)-free Conjecture of Stanley and Stembridge (J. Combin Theory (A) J. 62, 1993, 261–279).     

Stability of the C *-Algebra Associated with Twisted CCR

The universal enveloping C ^*-algebra A of twisted canonical commutation relations is considered. It is shown that, for any (–1,1), the C ^*-algebra A is isomorphic to the C ^*-algebra A ₀ generated by partial isometries t _i ,t _i ^*,i=1,¨,d satisfying the relations t _i ^* t _j = _ij (1– _k<i t _k t _k ^*), t _j t _i =0, ij and it is proved that the Fock representation of A is faithful.     

L∞-upper bound of L2-projections onto splines at a geometric mesh

For an integer k 1 and a geometric mesh (qⁱ)_−∞^∞ with q ε (0, ∞), let M_i,k(x): = k[q^{i + k}](· − x)₊^{k − 1}, N_i,k(x): = (q^{i + k} − qⁱM_i,k(x)/k, and let A_k(q) be the Gram matrix (∝M_i,kN_j,k)_i,jεz. It is known that A_k(q)⁻¹_∞ is bounded independently of q. In this paper it is shown that A_k(q)⁻¹_∞ is strictly decreasing for q in [1, ∞). In particular, the sharp upper bound and lower bound for A_k (q)⁻¹ are obtained: for all q ε (0, ∞).     

On the multiplicity of the eigenvalues of a graph

Given a graph G with characteristic polynomial ϕ(t), we consider the ML-decomposition ϕ(t) = q ₁(t)q ₂(t)² ... q _m (t)^m, where each q _i (t) is an integral polynomial and the roots of ϕ(t) with multiplicity j are exactly the roots of q _j (t). We give an algorithm to construct the polynomials q _i (t) and describe some relations of their coefficients with other combinatorial invariants of G. In particular, we get new bounds for the energy E(G) = |λ_i| of G, where λ₁, λ₂, ..., λ_n are the eigenvalues of G (with multiplicity). Most of the results are proved for the more general situation of a Hermitian matrix whose characteristic polynomial has integral coefficients. This work was done during a visit of the second named author to UNAM.     

Uniform estimates for polynomial approximation in domains with corners

Let be a domain with a Jordan boundary ∂G, consisting of l smooth curves Γ_j, such that {z_j}Γ_j-1∩Γ_j≠, j=1,…,l, where Γ₀Γ_l. Denote by α_jπ, 0<α_j2, the angles at z_j's between the curves Γ_j-1 and Γ_j, exterior with respect to G. Let Φ be a conformal mapping of the exterior of onto the exterior of the unit disk, normed by Φ^′(∞)>0. We assume that there is a neighborhood U of , such that , where

z≠z_j if α_j1. Set g_Gsup{|g(z)|:zG}. Then we prove Theorem. Let and 0βr. If a function f is analytic in G and f^(r)β_G<+∞, then for each nlr there is an algebraic polynomial P_n of degree <n, such that

     

Itération de pliages de quadrilatères

Iteration of quadrilateral foldings. Starting with a quadrilateral q₀=(A₁,A₂,A₃,A₄) of ², one constructs a sequence of quadrilaterals q_n=(A_4n+1,...,A_4n+4) by iteration of foldings: q_n=₄°₃°₂°₁(q_n-1) where the folding _j replaces the vertex number j by its symmetric with respect to the opposite diagonal (see Fig. 1).We study the dynamical behavior of this sequence. In particular, we prove that:– The drift exists.– When none of the q_n is isometric to q₀, then the drift v is zero if and only if one has maxa_j+mina_j1/2a_j where a₁,...,a₄ are the sidelengths of q₀.– For Lebesgue almost all q₀ the sequence (q_n-nv)_n1 is dense on a bounded analytic curve with a center or an axis of symmetry. However, for Baire generic q₀, the sequence (q_n-nv)_n1 is unbounded (see Figs. 2 to 7).      

A constructive method of solving the Liapounov equation for complex matrices

Summary This paper describes a method of solving the Liapounov equation (1)HM+M ^* H=2D, M in upper Hessenberg form,D diagonal. Initialising the first row of the matrixA arbitrarily, one can find (by solving equations with one unknown) the unknown elements ofA such that (2)AM+M ^* A ^* =2F, whereA differs from a Hermitian matrix only in that its diagonal elements need not be real.F is a diagonal matrix which is uniquely determined by the first row ofA. By solving Eq. (2) for several initial values one may generate several matricesA andF (in the most unfavourable case 2n–1A's andF's are needed) and superpose them to getn linearly independent Hermitian matricesH _j andD _j respectively for whichH _j M+M ^* H _j =2D _j is valid. Then one can solve the real system to obtain the solution of Eq. (1).This work was performed under the terms of the agreement on association between the Max-Planck-Institut für Plasmaphysik and Euratom.     

A Limit Function for Equidistant Fourier Interpolation

Denote by s_n the nth order Fourier polynomial of the odd function f of period 2π equal to 1 on ]0, π[. The Gibbs phenomenon is caused by the well-known fact that [formula] An analogous Gibbs phenomenon is caused by a similar limiting behaviour of s*_n, the nth order trigonometric polynomial interpolating f at jπ/n (1 ≤ j ≤ 2n).     

A note on "More Operator Versions of the Schwarz Inequality"

It is shown that for any (n + 1)-positive (possibly non-linear) map and any bounded linear operators A _i ,i = 1,¨,n we have [(A _i ^* A _j )] _{i,j = 1} ^*[(A _i )^*(A _j )] _{i,j = 1} ^*, and that the statement is false if "(n + 1)-positive" is replaced by "n-positive". This resolves an issue raised by Bhatia and Davis in relation to a Schwartz inequality which can be regarded as a non-commutative variance-covariance inequality [2]     

On the sequence of powers of a stochastic matrix with large exponent

We consider the class of primitive stochastic n×n matrices A, whose exponent is at least (n²−2n+2)/2+2. It is known that for such an A, the associated directed graph has cycles of just two different lengths, say k and j with k>j, and that there is an α between 0 and 1 such that the characteristic polynomial of A is λⁿ−αλ^n−j−(1−α)λ^n−k. In this paper, we prove that for any mn, if α1/2, then A^m+k−A^m_∞A^m−1w^T_∞, where 1 is the all-ones vector and w^T is the left-Perron vector for A, normalized so that w^T1=1. We also prove that if jn/2, n31 and , then A^m+j−A^m_∞A^m−1w^T_∞ for all sufficiently large m. Both of these results lead to lower bounds on the rate of convergence of the sequence A^m.     

Dual canonical bases,quantum shuffles and <Emphasis Type="Italic">q</Emphasis>-characters

Rosso and Green have shown how to embed the positive part U_q() of a quantum enveloping algebra U_q() in a quantum shuffle algebra. In this paper we study some properties of the image of the dual canonical basis B^* of U_q() under this embedding . This is motivated by the fact that when is of type A_r, the elements of (B^*) are q-analogues of irreducible characters of the affine Iwahori-Hecke algebras attached to the groups GL(m) over a p-adic field.     

On the spectrum of the two-dimensional periodic Dirac operator

We prove the absolute continuity of the Dirac operator spectrum inR ² with the scalar potential V and the vector potential A=(A₁, A₂) being periodic functions (with a common period lattice) such that V, A_j≠L _loc ^q (R ²), q>2. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 118, No. 1, pp. 3–14, January, 1999.     

Conservative loads on shells

Generalized load vectorsp and edge load vectorsF are denned in terms of the body force and surface on a shell. Necessary and sufficient conditions are derived forp andF, and therefore the body force and the surface force, to be conservative. It is shown for example thatp must satisfyp _i=P _ijk q _j,1 q _k,2+Q _ij ¹ q _j,2–Q _ij ² q _j,1+R _i whereq is the generalized position vector andP _ijk, Q_i,j ¹ and Q_ij ² are skew tensors.The case of hydrostatic pressure is examined in detail.This work was supported in part by NSF grant MSM 8618657.     

The Faber Operator and its Boundedness

Let G be a domain bounded by a Jordan curve Γ, and let A(G) be the Banach space of functions continuous on G and holomorphic in G. The Faber operator T is a linear mapping from A( ) to A(G) mapping wⁿ onto the nth Faber polynomial F_n(z) (n=0, 1, 2, …). We show that T<∞ if Γ is piecewise Dini-smooth, and give an example of a quasicircle Γ for which T=∞.     

Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids

The chromatic polynomial P_G(q) of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals (−∞,0), (0,1) and (1,32/27]. Analogous theorems hold for the flow polynomial of bridgeless graphs and for the characteristic polynomial of loopless matroids. Here we exhibit all these results as special cases of more general theorems on real zero-free regions of the multivariate Tutte polynomial Z_G(q,v). The proofs are quite simple, and employ deletion–contraction together with parallel and series reduction. In particular, they shed light on the origin of the curious number 32/27.     

Continuity in G

For a discrete group G, we consider βG, the Stone– ech compactification of G, as a right topological semigroup, and G^*=βGG as a subsemigroup of βG. We study the mappings λ_p^* :G^*→G^*and μ^* :G^*→G^*, the restrictions to G^* of the mappings λ_p :βG→βG and μ :βG→βG, defined by the rules λ_p(q)=pq, μ(q)=qq. Under some assumptions, we prove that the continuity of λ_p^* or μ^* at some point of G^* implies the existence of a P-point in ω^*.     

The equivalence of theories that characterize ALogTime

A number of theories have been developed to characterize ALogTime (or uniform NC ¹, or just NC ¹), the class of languages accepted by alternating logtime Turing machines, in the same way that Buss’s theory characterizes polytime functions. Among these, ALV′ (by Clote) is particularly interesting because it is developed based on Barrington’s theorem that the word problem for the permutation group S ₅ is complete for ALogTime. On the other hand, ALV (by Clote), T ⁰ NC ⁰ (by Clote and Takeuti) as well as Arai’s theory and its two-sorted version VNC ¹ (by Cook and Morioka) are based on the circuit characterization of ALogTime. While the last three theories have been known to be equivalent, their relationship to ALV′ has been an open problem. Here we show that ALV′ is indeed equivalent to the other theories.      

Decomposable graphs and definitions with no quantifier alternation

Let D(G) be the minimum quantifier depth of a first order sentence Φ that defines a graph G up to isomorphism. Let D₀(G) be the version of D(G) where we do not allow quantifier alternations in Φ. Define q₀(n) to be the minimum of D₀(G) over all graphs G of order n.We prove that for all n we have

log^*n−log^*log^*n−2≤q₀(n)≤log^*n+22,