On the van der Waerden conjecture and zeros of polynomials

Let

$\text{F(x) =}\text{∑}\text{k=o}\text{n}\text{n}\text{k}\text{A}{}_{\mathrm{k}}\text{x}{}^{\mathrm{k}}$

$\text{A}{}_{\mathrm{n}}\text{≠ 0,}$

and

$\text{G(x) =}\text{∑}\text{k=o}\text{n}\text{n}\text{k}\text{B}{}_{\mathrm{k}}\text{x}{}^{\mathrm{k}}$

$\text{B}{}_{\mathrm{n}}\text{≠ 0,}$

be polynomials with real zeros satisfying A_n?1 = B_n?1 = 0, and let

$\text{H(x) =}\text{∑}\text{k=o}\text{n-2}\text{n}\text{k}\text{A}{}_{\mathrm{k}}\text{B}{}_{\mathrm{k}}\text{x}{}^{\mathrm{k}}\text{.}$

Using the recently proved validity of the van der Waerden conjecture on permanents, some results on the real zeros of H(x) are obtained. These results are related to classical results on composite polynomials.     

An inequality involving permanents of certain direct products

Let A denote a decomposable symmetric complex valued n-linear function on C^m. We prove

$\text{6A·A6}{}^2\text{?2}{}^{\mathrm{n}}\text{2n}\text{n}{}^{\mathrm{?1}}\text{6A?A6}{}^2$

, where · denotes the symmetric product and ? the tensor product. As a consequence we have per

$\text{M}\text{M}\text{M}\text{M}\text{?2}{}^{\mathrm{n}}\text{[per(M)]}{}^2$

, where M is a positive semidefinite Hermitian matrix and per denotes the permanent function. A sufficient condition for equality in the matrix inequality is that M is a nonnegative diagonal matrix.     

Pairs of additive equations II. Large odd degree

Let k be an odd positive integer. Davenport and Lewis have shown that the equations

$\text{a}{}_1\text{x}{}_1{}^{\mathrm{k}}\text{+…+a}{}_{\mathrm{n}}\text{x}{}_{\mathrm{n}}{}^{\mathrm{k}}\text{=0}$

with integer coefficients, have a nontrivial solution in integers x₁,…, x_N provided that

$\text{N?[36klog6k]}$

Here it is shown that for any ? > 0 and k > k₀(?) the equations have a nontrivial solution provided that

$\text{N?}\text{8}\text{log 2}\text{+?}\text{k log k.}$

     

Canonical forms for linear systems

This paper considers canonical forms for the similarity action of Gl(n) on $\text{∑}{}_{\mathrm{n,m}}\text{={(A,B)∈}\text{C}{}^{\mathrm{n}}\text{·}{}^{\mathrm{n}}\text{×}\text{C}{}^{\mathrm{n}}\text{·}{}^{\mathrm{m}}\text{}}$:

$\text{Gl(n×∑}{}_{\mathrm{n,m}}\text{→∑}{}_{\mathrm{n,m}}$

,

$\text{(H,(A,B))?(HAH}{}^{-1}\text{,HB)}$

Those canonical forms are obtained as an application of a more general method to select canonical elements M_c in the orbits $\text{O}{}_{\mathrm{M}}$ of a matrix group G acting on a set of matrices $\text{M}\text{?}\text{C}{}^{\mathrm{l}}\text{·}{}^{\mathrm{p}}$. We define a total order (?) on $\text{C}{}^{\mathrm{l}}\text{·}{}^{\mathrm{p}}$, different from the lexicographic order ^l? [0^l?x ? x <0, but $\text{0?x≠0 for x∈}\text{R}\text{]}$ and consider normalized $\text{O}{}_{\mathrm{M}}$-elements with a minimal number of parameters:

$\text{min{}\text{M}\text{?}\text{∈}\text{O}{}_{\mathrm{M}}\text{:}\text{M}\text{?}\text{normalized}}$

It is shown that the row and column echelon forms, the Jordan canonical form, and “nice” control canonical forms for reachable (A,B)-pairs have a homogeneous interpretation as such (?)-minimal orbit elements. Moreover new canonical forms for the general action (?) are determined via this method.     

On the number of zeros of diagonal cubic forms

Let M_s, be the number of solutions of the equation

$\text{X}{}_1{}^3\text{+ X}{}_2{}^3\text{+ … + X}{}_{\mathrm{s}}{}^3\text{=0}$

in the finite field GF(p). For a prime p ≡ 1(mod 3),

$\text{∑}\text{s=1}\text{∞}\text{M}{}_{\mathrm{s}}\text{X}{}^{\mathrm{s}}\text{=}\text{x}\text{1 ? px}\text{+}\text{x}{}^2\text{(p ? 1)(2 + dx)}\text{1 ? 3px}{}^2\text{? pdx}{}^3$

,

$\text{M}{}_3\text{= p}{}^2\text{+ d(p ? 1)}$

, and

$\text{M}{}_4\text{= p}{}^2\text{+ 6(p}{}^2\text{? p)}$

. Here d is uniquely determined by

$\text{4}{}_{\mathrm{p}}\text{= d}{}^2\text{+ 27b}{}^2\text{and}\text{d ≡ 1(}\text{mod}\text{3)}$

.     

Concavity of certain maps on positive definite matrices and applications to Hadamard products

If f is a positive function on (0, ∞) which is monotone of order n for every n in the sense of Löwner and if Φ₁ and Φ₂ are concave maps among positive definite matrices, then the following map involving tensor products:

$\text{(A,B)?f[Φ}{}_1\text{(A)}{}^{\mathrm{?1}}\text{?Φ}{}_2\text{(B)]·(Φ}{}_1\text{(A)?I)}$

is proved to be concave. If Φ₁ is affine, it is proved without use of positivity that the map

$\text{(A,B)?f[Φ}{}_1\text{(A)?Φ}{}_2\text{(B)}{}^{\mathrm{?1}}\text{]·(Φ}{}_1\text{(A)?I)}$

is convex. These yield the concavity of the map

$\text{(A,B)?A}{}^{\mathrm{1?p}}\text{?B}{}^{\mathrm{p}}$

(0<p?1) (Lieb's theorem) and the convexity of the map

$\text{(A,B)?A}{}^{\mathrm{1+p}}\text{?B}{}^{\mathrm{?p}}$

(0<p?1), as well as the convexity of the map

$\text{(A,B)?(A·log[A])?I?A?log[B]}$

.These concavity and convexity theorems are then applied to obtain unusual estimates, from above and below, for Hadamard products of positive definite matrices.     

Deterministic version of Wigner's semicircle law for the distribution of matrix eigenvalues

It is proved that Wigner's semicircle law for the distribution of eigenvalues of random matrices, which is important in the statistical theory of energy levels of heavy nuclei, possesses the following completely deterministic version. Let A_n=(a_ij), 1?i, ?n, be the nth section of an infinite Hermitian matrix, {λ⁽ⁿ⁾}_1?k?n its eigenvalues, and {u_k⁽ⁿ⁾}_1?k?n the corresponding (orthonormalized column) eigenvectors. Let $\text{v}{}^1{}_{\mathrm{n}}\text{=(a}{}_{\mathrm{n1}}\text{,a}{}_{\mathrm{n2}}\text{,?,a}{}_{\mathrm{n,n?1}}\text{)}$, put

$\text{X}{}_{\mathrm{n}}\text{(t)=[n(n-1)]}{}^{\mathrm{<mtext>-1</mtext><mtext>2</mtext>}}\text{∑}\text{k=1}\text{[(n-1)t]}\text{|v}{}_{\mathrm{n}}{}^1\text{u}{}_{\mathrm{f}}{}^{\mathrm{(n-1)}}\text{|}{}^2\text{,}\text{0?t?1}$

(bookeeping function for the length of the projections of the new row v¹_n of A_n onto the eigenvectors of the preceding matrix A_n?1), and let finally

$\text{F}{}_{\mathrm{n}}\text{(x)=n}{}^{-1}\text{(}\text{number of}\text{λ}{}_{\mathrm{k}}{}^{\mathrm{(n)}}\text{?x}\text{n}\text{,1?k?n)}$

(empirical distribution function of the eigenvalues of $\text{A}{}_{\mathrm{n}}\text{n}$. Suppose (i) $\text{lim}{}_{\mathrm{n}}\text{a}{}_{\mathrm{nn}}\text{n}\text{=0}$, (ii) lim_nX_n(t)=Ct(0<C<∞,0?t?1). Then

$\text{F}{}_{\mathrm{n}}\text{?W(·,C)}\text{(n→∞)}$

,where W is absolutely continuous with (semicircle) density

$\text{w(x,C)=}\text{(2Cπ)}{}^{-1}\text{(4C-x}{}^2{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{for}\text{|x|?2}\text{C}\text{0}\text{for}\text{|x|?2}\text{C}$

     

On a conjecture by D. Ž. D̄okovic

It is shown that if $\text{A?Ω}{}_{\mathrm{n}}\text{?{J}{}_{\mathrm{n}}\text{}}$ satisfies

$\text{nkσ}{}_{\mathrm{k}}\text{(A)?(n?k+1)}{}^2\text{σ}{}_{\mathrm{k?1}}\text{(A)}$

$\text{(k=1,2,…,n)}$

, where σ_k(A) denotes the sum of all kth order subpermanent of A, then Per[λJ_n+(1?λ)A] is strictly decreasing in the interval 0<λ<1.     

Kolmogorov-Landau inequalities for monotone functions

Presented in this report are two further applications of very elementary formulae of approximate differentiation. The first is a new derivation in a somewhat sharper form of the following theorem of V. M. Olovyani?nikov: LetN_n (n ? 2) be the class of functionsg(x) such thatg(x), g′(x),…, g⁽ⁿ⁾(x) are ? 0, bounded, and nondecreasing on the half-line ?∞ < x ? 0. A special element ofN_nis

$\text{g}{}_1\text{(x) = 0}\text{if}\text{?∞ < x < ?1, g}{}_1\text{(x) = (1 + x)}{}^{\mathrm{n}}\text{if}\text{?1 ? x ? 0}$

. Ifg(x) ∈ N_nis such that

$\text{g(0) ? g}{}_1\text{(0) = 1, g}{}^{\mathrm{(n)}}\text{(0) ? g}{}_1{}^{\mathrm{(n)}}\text{(0) = n!}$

, then

$\text{g}{}^{\mathrm{(v)}}\text{(0) ? g}{}_1{}^{\mathrm{(v)}}\text{(0)}$

for

1$\text{v = 1,…, n ? 1}$

. Moreover, if we have equality in (1) for some value of v, then we have there equality for all v, and this happens only if $\text{g(x) = g}{}_1\text{(x)}$ in (?∞, 0].The second application gives sufficient conditions for the differentiability of asymptotic expansions (Theorem 4).     

Common solutions to the Lyapunov equations

Let A be an n×n matrix with complex entries. A necessary and sufficient condition is established for the existence of a Hermitian solution H to the equations

$\text{AH+HA}{}^1\text{=HA+A}{}^1\text{H=I}$

.     

On the asymptotic number of tournament score sequences

An n-tournament is a complete labelled digraph on n vertices without loops or multiple arcs. A tournament's score sequence is the sequence of the out-degrees of its vertices arranged in nondecreasing order. The number S_n of distinct score sequences arising from all possible n-tournaments, as well as certain generalizations are investigated. A lower bound of the form

$\text{S}{}_{\mathrm{n}}\text{>}\text{C}{}_1\text{4}{}^{\mathrm{n}}\text{n}{}^{\mathrm{<mtext>5</mtext><mtext>2</mtext>}}$

(C₁ a constant) and an upper bound of the form $\text{S}{}_{\mathrm{n}}\text{<}\text{C}{}_2\text{4}{}^{\mathrm{n}}\text{n}{}^2$ are proved. A q-extension of the Catalan numbers

$\text{c}{}_1\text{(q)=1}\text{and}\text{c}{}_{\mathrm{n}}\text{(q)=}\text{∑}\text{i?1}\text{n?1}\text{c}{}_{\mathrm{i}}\text{(q)c}{}_{\mathrm{n?1}}\text{(q)q}{}^{\mathrm{i(n?i?1)}}$

is defined. It is conjectured that all coefficients in the polynomial C_n(q) are at most $\text{O(}\text{4}{}^{\mathrm{n}}\text{n}{}^3\text{)}$. It is shown that if this conjecture is true, then

$\text{S}{}_{\mathrm{n}}\text{<}\text{C}{}_3\text{4}{}^{\mathrm{n}}\text{n}{}^{\mathrm{<mtext>5</mtext><mtext>2</mtext>}}$

     

Strong approximation theorems for density dependent Markov chains

A variety of continuous parameter Markov chains arising in applied probability (e.g. epidemic and chemical reaction models) can be obtained as solutions of equations of the form

$\text{X}{}_{\mathrm{N}}\text{(t)=x}{}_0\text{+∑}\text{1}\text{N}\text{lY}{}_1\text{N ∫}{}^{\mathrm{t}}{}_0\text{f}{}_1\text{(X}{}_{\mathrm{N}}\text{(s))ds}$

where $\text{l∈}\text{Z}{}^{\mathrm{t}}$, the Y₁ are independent Poisson processes, and N is a parameter with a natural interpretation (e.g. total population size or volume of a reacting solution).The corresponding deterministic model, satisfies

$\text{X(t)=x}{}_0\text{+ ∫}{}^{\mathrm{t}}{}_0\text{∑ lf}{}_1\text{(X(s))ds}$

Under very general conditions lim_N→∞X_N(t)=X(t) a.s. The process X_N(t) is compared to the diffusion processes given by

$\text{Z}{}_{\mathrm{N}}\text{(t)=x}{}_0\text{+∑}\text{1}\text{N}\text{lB}{}_1\text{N∫}{}^{\mathrm{t}}{}_0\text{ft(Z}{}_{\mathrm{N}}\text{(s))ds}$

and

$\text{V(t)=∑ l∫}{}^{\mathrm{t}}{}_0\text{f}{}_1\text{(X(s))}\text{d}\text{W}\text{?}{}_1\text{+∫}{}^{\mathrm{t}}{}_0\text{?F(X(s))·V(s)}\text{ds.}$

Under conditions satisfied by most of the applied probability models, it is shown that X_N,Z_N and V can be constructed on the same sample space in such a way that

$\text{X}{}_{\mathrm{N}}\text{(t)=Z}{}_{\mathrm{N}}\text{(t)+O}\text{logN}\text{N}$

and

$\text{N}\text{(X}{}_{\mathrm{N}}\text{(t)?X(t))=V(t)+O}\text{log N}\text{N}$

     

Lower bounds for the norm of the symmetric product

Suppose each of m, n, and k is a positive integer, k ? n, A is a (real-valued) symmetric n-linear function on E_m, and B is a k-linear symmetric function on E_m. The tensor and symmetric products of A and B are denoted, respectively, by A ?B and A?B. The identity

$\text{6A · B6}{}^2\text{=}\text{∑}\text{q=0}\text{n}\text{(}\text{n}\text{k}\text{)}\text{(}\text{n+k}\text{k}\text{)}\text{6A?}{}_{\mathrm{q}}\text{B6}{}^2$

is proven by Neuberger in [1]. An immediate consequence of this identity is the inequality

$\text{6A · B 6}{}^2\text{?}\text{n+k}\text{n}{}^{\mathrm{?1}}\text{6A · B 6}{}^2$

In this paper a necessary and sufficient condition for

$\text{6A · B 6}{}^2\text{=}\text{n+k}\text{n}{}^{\mathrm{?}}\text{6A · B 6}{}^2$

is given. It is also shown that under certain conditions the inequality can be considerably improved. This improvement results from an analysis of the terms 6A?_qB6, 1?q?n, appearing in the identity.     

Stability of a chain of linear differential equations

The behavior of an infinite sequence of ordinary differential equations of the form:

$\text{dXn}\text{dt}\text{=}\text{∑}\text{i=?M}\text{N}\text{L}{}_{\mathrm{i}}\text{X}{}_{\mathrm{i+n}}\text{, 0 ? n, 0 < N, M < ∞}$

,

$\text{X}{}_{\mathrm{n}}\text{(0) = C}{}_{\mathrm{n}}\text{, (1) X}{}_{\mathrm{n}}\text{≡ 0, n < 0}$

, where X_n(t) is a vector valued function of R⁺, is studied in spaces of infinite sequences of vectors. In particular, sufficient conditions for asymptotic stability of this sequence of linear equations are established and applied to the stability analysis of a string of vehicles with a simple form of automatic control.     

Eigenvalues of p-summing and lp-type operators in Banach spaces

This paper is a study of the distribution of eigenvalues of various classes of operators. In Section 1 we prove that the eigenvalues (λ_n(T)) of a p-absolutely summing operator, p ? 2, satisfy

$\text{∑}\text{n∈N}\text{|λ}{}_{\mathrm{n}}\text{(T)|}{}^{\mathrm{p}}{}^{\mathrm{<mtext>1</mtext><mtext>p</mtext>}}\text{?π}{}_{\mathrm{p}}\text{(T).}$

This solves a problem of A. Pietsch. We give applications of this to integral operators in L_p-spaces, weakly singular operators, and matrix inequalities.In Section 2 we introduce the quasinormed ideal Π₂⁽ⁿ⁾, P = (p₁, …, p_n) and show that for T ∈ Π₂⁽ⁿ⁾, 2 = (2, …, 2) ∈ Nⁿ, the eigenvalues of T satisfy

$\text{∑}\text{i∈N}\text{|λ}{}_{\mathrm{i}}\text{(T)|}{}^{\mathrm{<mtext>2</mtext><mtext>n</mtext>}}{}^{\mathrm{<mtext>n</mtext><mtext>2</mtext>}}\text{?π}{}^{\mathrm{n}}{}_2\text{(T).}$

More generally, we show that for T ∈ Π_p⁽ⁿ⁾, P = (p₁, …, p_n), pi ? 2, the eigenvalues are absolutely p-summable,

$\text{1}\text{p}\text{=}\text{∑}\text{i=1}\text{n}\text{1}\text{p}{}_{\mathrm{i}}\text{and}\text{∑}\text{n∈N}\text{|λ}{}_{\mathrm{n}}\text{(T)|}{}^{\mathrm{p}}{}^{\mathrm{<mtext>1</mtext><mtext>p</mtext>}}\text{?C}{}_{\mathrm{p}}\text{π}{}^{\mathrm{n}}{}_{\mathrm{P}}\text{(T).}$

We also consider the distribution of eigenvalues of p-nuclear operators on L_r-spaces.In Section 3 we prove the Banach space analog of the classical Weyl inequality, namely

$\text{∑}\text{n∈N}\text{|λ}{}_{\mathrm{n}}\text{(T)|}{}^{\mathrm{p}}\text{? C}{}_{\mathrm{p}}\text{∑}\text{n∈N}\text{α}{}_{\mathrm{n}}\text{(T)}{}^{\mathrm{p}}$

, 0 < p < ∞, where α_n denotes the Kolmogoroff, Gelfand of approximation numbers of the operator T. This solves a problem of Markus-Macaev.Finally we prove that Hilbert space is (isomorphically) the only Banach space X with the property that nuclear operators on X have absolutely summable eigenvalues. Using this result we show that if the nuclear operators on X are of type l₁ then X must be a Hilbert space.     

Asymptotic results for partitions (II) and a conjecture of Bateman and Erdös

Asymptotic results are obtained for p_A^(k)(n), the kth difference of the function p_A(n) which is the number of partitions of n into integers from A. Under certain restrictions on A it is shown that

$\text{P}{}_{\mathrm{A}}{}^{\mathrm{(k+1)}}\text{(n)}\text{P}{}_{\mathrm{A}}{}^{\mathrm{(k)}}\text{(n)}\text{= O(n}{}^{\mathrm{?1/2}}\text{) (n→ ∫)}$

thereby verifying for these A a conjecture of Bateman and Erdös.     

The nonorientable genus of the symmetric quadripartite graph

The nonorientable genus of K_4(n) is shown to satisfy:

$\text{γ}\text{(K}{}_{\mathrm{4(n)}}\text{)=2(n?1)}{}^2\text{for n ? 3}$

,

$\text{γ}\text{(K}{}_{\mathrm{4(2)}}\text{)=3,}\text{γ}\text{(K}{}_4\text{(1))=1}$

.     

Sur la compatibilité des extensions ponctuelles d'un matroïde

A natural sufficient condition for a finite family of single element extensions of a matroid to be compatible is given. Characterizations of all the finite extensions N of a matroid M(E) are given for which the rank function satisfies

$\text{ρ}{}_{\mathrm{N}}\text{(X)=}\text{Min}\text{Z?E}\text{{ρ}{}_{\mathrm{M}}\text{(Z)+|X?}\text{Z}{}^{\mathrm{N}}\text{|}}$

or equivalently the closure operator satisfies $\text{X}{}^{\mathrm{N}}\text{=}\text{X}{}^{\mathrm{N}}\text{? E}{}^{\mathrm{N}}\text{? X}$. The single element extensions and the principal extensions are examples of such matroids. The notion of a sheaf of flats of M. Las Vergnas is used in the proof of a new necessary and sufficient condition for two single element extensions of a matroid to be compatible. An initial announcement of part of these results appeared in R. Cordovil (C. R. Acad. Sci. Paris. A284 (1977), 1249–1252).