Noncommutative convexity arises from linear matrix inequalities

This paper concerns polynomials in g noncommutative variables x=(x₁,…,xg), inverses of such polynomials, and more generally noncommutative “rational expressions” with real coefficients which are formally symmetric and “analytic near 0.” The focus is on rational expressions r=r(x) which are “matrix convex” near 0; i.e., those rational expressions r for which there is an ?>0 such that if X=(X₁,…,Xg) is a g-tuple of n×n symmetric matrices satisfying

     

On a class of equilibrium problems in the real axis

In a series of seminal papers, Thomas J. Stieltjes (1856-1894) gave an elegant electrostatic interpretation for the zeros of classical families of orthogonal polynomials, such as Jacobi, Hermite and Laguerre polynomials. More generally, he extended this approach to the zeros of polynomial solutions of certain second-order linear differential equations (Lamé equations), the so-called Heine-Stieltjes polynomials.In this paper, a class of electrostatic equilibrium problems in R, where the free unit charges x₁,…,x_n∈R are in presence of a finite family of “attractors” (i.e., negative charges) z₁,…,z_m∈C?R, is considered and its connection with certain class of Lamé-type equations is shown. In addition, we study the situation when both n→∞ and m→∞, by analyzing the corresponding (continuous) equilibrium problem in presence of a certain class of external fields.     

On explicit factors of cyclotomic polynomials over finite fields

We study the explicit factorization of 2 ⁿ r-th cyclotomic polynomials over finite field \mathbbF_q{\mathbb{F}_q} where q, r are odd with (r, q) = 1. We show that all irreducible factors of 2 ⁿ r-th cyclotomic polynomials can be obtained easily from irreducible factors of cyclotomic polynomials of small orders. In particular, we obtain the explicit factorization of 2 ⁿ 5-th cyclotomic polynomials over finite fields and construct several classes of irreducible polynomials of degree 2 ^n–2 with fewer than 5 terms.     

Periodic solutions of the Lyness max equation

We investigate the periodic nature of solutions of a “max-type” difference equation sometimes referred to as the “Lyness max” equation. The equation we consider is x_n+1=max{x_n,A}/x_n−1, n=0,1,…, where A is a positive real parameter and the initial conditions are arbitrary positive numbers. We also present related results for a similar equation sometimes referred to as the “period 7 max” equation.     

On finite decomposition complexity of Thompson group

Finite decomposition complexity (FDC) is a large scale property of a metric space. It generalizes finite asymptotic dimension and applies to a wide class of groups. To make the property quantitative, a countable ordinal “the complexity” can be defined for a metric space with FDC. In this paper we prove that the subgroup Z?Z of Thompson?s group F belongs to Dω exactly, where ω is the smallest infinite ordinal number and show that F equipped with the word-metric with respect to the infinite generating set {x₀,x₁,…,xn,…} does not have finite decomposition complexity.     

类对称函数的Schur凸性和不等式

对x = (x₁, x₂,···, x_n) ∈ (0,1)ⁿ 和 r ∈ {1, 2,···, n} 定义对称函数 F_n(x, r) = F_n(x₁, x₂,···, x_n; r) =∏_{1≤i1∑j=1^r(1+xi3/1- xi3)^1/r, 其中i1, i2, ···, ir 是整数. 该文证明了Fn(x, r) 是(0,1)ⁿ 上的Schur凸、Schur乘性凸和Schur调和凸函数. 作为应用,利用控制理论建立了若干不等式.}     

Incomplete Character Sums and Polynomial Interpolation of the Discrete Logarithm

In the first part of the paper, certain incomplete character sums over a finite field F_p^r are considered which in the case of finite prime fields F_p are of the form ∑^A+N−1_n=Aχ(g(n))ψ(f(n)), where A and N are integers with 1≤N<p, g and f are polynomials over F_p, and χ denotes a multiplicative and ψ an additive character of F_p. Excluding trivial cases, it is shown that the above sums are at most of the order of magnitude N^1/2p^r/4. Recently, Shparlinski showed that a polynomial f over the integers which coincides with the discrete logarithm of the finite prime field F_p for N consecutive elements of F_p must have a degree at least of the order of magnitude Np^−1/2. In this paper this result is extended to arbitrary F_p^r. The proof is based on the above new bound for incomplete hybrid character sums.     

On subword decomposition and balanced polynomials

Let H(x) be a monic polynomial over a finite field F=GF(q). Denote by Na(n) the number of coefficients in Hn which are equal to an element a∈F, and by G the set of elements a∈F^× such that Na(n)>0 for some n. We study the relationship between the numbers (Na(n))_a∈G and the patterns in the base q representation of n. This enables us to prove that for “most” n's we have Na(n)≈Nb(n), a,b∈G. Considering the case H=x+1, we provide new results on Pascal's triangle modulo a prime. We also provide analogous results for the triangle of Stirling numbers of the first kind.     

Sharp upper bounds on the number of the scattering poles

We study the scattering poles of a compactly supported “black box” perturbations of the Laplacian in Rⁿ, n odd. We prove a sharp upper bound of the counting function N(r) modulo o(rⁿ) in terms of the counting function of the reference operator in the smallest ball around the black box. In the most interesting cases, we prove a bound of the type N(r)?A_nrⁿ+o(rⁿ) with an explicit A_n. We prove that this bound is sharp in a few special spherically symmetric cases where the bound turns into an asymptotic formula.     

Random matrix products and applications to cellular automata

Let λ be the upper Lyapunov exponent corresponding to a product of i.i.d. randomm×m matrices (X _i) _i ^0/∞ over ℂ. Assume that theX _i's are chosen from a finite set {D ₀,D ₁...,D _t-1(ℂ), withP(X _i=D_j)>0, and that the monoid generated byD ₀, D₁,…, D_q−1 contains a matrix of rank 1. We obtain an explicit formula for λ as a sum of a convergent series. We also consider the case where theX _i's are chosen according to a Markov process and thus generalize a result of Lima and Rahibe [22]. Our results on λ enable us to provide an approximation for the numberN _≠0(F(x)ⁿ,r) of nonzero coefficients inF(x) ⁿ.(modr), whereF(x) ∈ ℤ[x] andr≥2. We prove the existence of and supply a formula for a constant α (<1) such thatN _≠0(F(x)ⁿ,r) ≈n ^α for “almost” everyn. Supported in part by FWF Project P16004-N05     

Enumeration of inequivalent irreducible Goppa codes

We consider irreducible Goppa codes over F_q of length qⁿ defined by polynomials of degree r, where q is a prime power and n,r are arbitrary positive integers. We obtain an upper bound on the number of such codes.     

A dynamic adaptive local search algorithm for the circular packing problem

This paper studies the circular packing problem (CPP) which consists of packing n non-identical circles C_i of known radius r_i, i ∈ N = {1, … , n}, into the smallest containing circle C. The objective is to determine the coordinates (x_i, y_i) of the center of C_i, i ∈ N, as well as the radius r and center (x, y) of C. This problem, which is a variant of the two-dimensional open dimension problem, is solved using a two-step, dynamic, adaptive, local search algorithm. At each iteration, the algorithm identifies the set of potential “best local positions” of a circle C_i, i ∈ N, given the positions of the previously packed circles, and determines for each of these positions the coordinates and radius of the smallest containing circle. The “best local position” minimizes the radius of the current containing circle. That is, every time an additional circle is packed, both the center and the radius of the containing circle are dynamically updated, and the smallest containing circle is known. The experimental results reflect the good performance of the algorithm.     

Gaussian decompositions in function spaces

We introduce Gausslets , where P(x) are distinguished polynomials in ?ⁿ. Combined with dilations x?2 ^v x, where v∈N₀, and translations x?x+m, where m ∈ ?ⁿ, one obtains frames in the function spaces B _pq ^s (? ⁿ ) and F _pq ^s (? ⁿ ) for all possible parameters ^{s, p}, and ^q.     

The Proof of a Conjecture of Additive Number Theory

The aim of this paper is to show that for any n∈N, n>3, there exist a, b∈N* such that n=a+b, the “lengths” of a and b having the same parity (see the text for the definition of the “length” of a natural number). Also we will show that for any n∈N, n>2, n≠5, 10, there exist a, b∈N* such that n=a+b, the “lengths” of a and b having different parities. We will prove also that for any prime p≡7(mod 8) there exist a, b∈N* such that p=a²+b, the “length” of b being an even number.     

A generalized Cayley-Hamilton theorem for polynomials with matrix coefficients

A family F of square matrices of the same order is called a quasi-commuting family if (AB-BA)C=C(AB-BA) for all A,B,C∈F where A,B,C need not be distinct. Let f_k(x₁,x₂,…,x_p),(k=1,2,…,r), be polynomials in the indeterminates x₁,x₂,…,x_p with coefficients in the complex field C, and let M₁,M₂,…,M_r be n×n matrices over C which are not necessarily distinct. Let and let δ_F(x₁,x₂,…,x_p)=detF(x₁,x₂,…,x_p). In this paper, we prove that, for n×n matrices A₁,A₂,…,A_p over C, if {A₁,A₂,…,A_p,M₁,M₂,…,M_r} is a quasi-commuting family, then F(A₁,A₂,…,A_p)=O implies that δ_F(A₁,A₂,…,A_p)=O.     

Green’s matrices

Our goal is to identify and understand matrices A that share essential properties of the unitary Hessenberg matrices M that are fundamental for Szegö’s orthogonal polynomials. Those properties include: (i) Recurrence relations connect characteristic polynomials {r_k(x)} of principal minors of A. (ii) A is determined by generators (parameters generalizing reflection coefficients of unitary Hessenberg theory). (iii) Polynomials {r_k(x)} correspond not only to A but also to a certain “CMV-like” five-diagonal matrix. (iv) The five-diagonal matrix factors into a product BC of block diagonal matrices with 2 × 2 blocks. (v) Submatrices above and below the main diagonal of A have rank 1. (vi) A is a multiplication operator in the appropriate basis of Laurent polynomials. (vii) Eigenvectors of A can be expressed in terms of those polynomials.Conditions (v) connects our analysis to the study of quasi-separable matrices. But the factorization requirement (iv) narrows it to the subclass of “Green’s matrices” that share Properties (i)-(vii).The key tool is “twist transformations” that provide 2ⁿ matrices all sharing characteristic polynomials of principal minors with A. One such twist transformation connects unitary Hessenberg to CMV. Another twist transformation explains findings of Fiedler who noticed that companion matrices give examples outside the unitary Hessenberg framework. We mention briefly the further example of a Daubechies wavelet matrix. Infinite matrices are included.     

The centralizer of a semi-linear transformation

Let V be a finite-dimensional vector space over a division ring D, where D is finite-dimensional over its center F. Suppose T is a semi-linear transformation on V with associated automorphism σ of D. The centralizer of T is the ring C(T) of all linear transformations on V which commute with T. If σ^r is the identity on D for some r ? 1 and no smaller positive power of σ is an inner automorphism, then the center of C(T) is computed to be polynomials in T^r with coefficients from F₀, where F₀ is the subfield of F left elementwise fixed by σ. A matrix version of this theorem is also given.     

Rational approximation with varying weights I

We investigate two problems concerning uniform approximation by weighted rationals {w ⁿr_n～ _∞ ⁿ⁼¹ }, wherer _n=p_n Namely, forw(x):=e ^x we prove that uniform convergence to 1 ofw ⁿr_n is not possible on any interval [0,a] witha>2π. Forw(x):=x ^?, ?>1, we show that uniform convergence to 1 ofw ⁿr_n is not possible on any interval [b, 1] withb<tan ⁴(π(??1)/4?). (The latter result can be interpreted as a rational analogue of results concerning “incomplete polynomials.”) More generally, for α≥0, β≥0, α+β>0, we investigate forw(x)=e ^x andw(x)=x ^?, the possibility of approximation byw ⁿ p_n/q_n～ _∞ ⁿ⁼¹ , where depp _n≤αn, degq _n≤βn. The analysis utilizes potential theoretic methods. These are essentially sharp results though this will not be established in this paper.