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>}}$

     

About some problems of spectral synthesis

For a given pair $\text{(A,b)∈}\text{R}{}^{\mathrm{n\times n}}\text{×}\text{R}{}^{\mathrm{n\times 1}}$ such that A is cyclic and b is a cyclic generator (with respect to A) of $\text{R}{}^{\mathrm{n\times 1}}$, it is shown that for every nonnegative integer m we can find a nonnegative integer t and a sequence $\text{{f}{}_{\mathrm{j\}}}{}^{\mathrm{t}}{}_{\mathrm{j=0}}\text{,f}{}_{\mathrm{j}}\text{∈}\text{R}{}^{\mathrm{1\times n}}$,so that a the zeros of the rational function det P(z), where $\text{P(z) = zI ? A ? ∑}{}^{\mathrm{t}}{}_{\mathrm{j=0}}\text{z}{}^{\mathrm{-(m+j)}}\text{b?}$_f, lie in the open unit disc in the complex plane. The result is directly applicable to a stabilizability problem for linear systems with a time delay in control action.     

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}$

     

Binomial self-inverse sequences and tangent coefficients

This paper treats the class of sequences {a_n} that satisfy the recurrence relation

$\text{a}{}_{\mathrm{2n+1}}\text{=∑}{}_{\mathrm{<mtext>k=0</mtext>}}{}^{\mathrm{<mtext>n</mtext>}}\text{(?1)}{}^{\mathrm{<mtext>k</mtext>}}\text{(}\text{n}\text{k}\text{a}{}_{\mathrm{k}}\text{d}{}^{\mathrm{n?k}}$

between the odd and even terms of {a_n} that involves the coefficients of tan(t), namely

$\text{a}{}_{\mathrm{2n+1}}\text{=∑}{}_{\mathrm{<mtext>k=0</mtext>}}{}^{\mathrm{<mtext>n</mtext>}}\text{(?1)}{}^{\mathrm{<mtext>k</mtext>}}\text{(}\text{2}\text{n}\text{+1}\text{2}\text{k}\text{+1}\text{)}\text{T}{}_{\mathrm{k}}\text{(d/2)}{}^{\mathrm{2k+1}}\text{a}{}_{\mathrm{2n?2k}}$

A combinatorial setting is then provided to elucidate the appearance of the tangent coefficients in this equation.     

On the enumeration of self-complementary m-placed relations

A formula for the number a_m(2n) of self-complementary m-placed relations is given. Then we obtain from this formula asymptotic results, e.g.$\text{a}{}_{\mathrm{m}}\text{(2n) ～ (2(}{}^{\mathrm{2n}}\text{)}{}^{\mathrm{<mtext>m</mtext><mtext>2?n</mtext>}}\text{)/n}$     

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}$

     

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.     

Derivations of Witt vectors with application to K2 of truncated polynomial rings and Laurent series

The absolute Kähler module $\text{Ω}{}_{\mathrm{w}}{}_{\mathrm{n}}{}^{\mathrm{(k)}}$ of the truncated generalized Witt vectors of a field k of positive characteristic is zero if and only if k is perfect. This recovers known information on $\text{K}{}_2\text{(}\text{k[t]}\text{(t}{}^{\mathrm{n}}\text{)}\text{)}$ with which the structure of K₂(k((t))) can be studied.     

Capacitance and the conformal module of quadrilaterals

Let ? be defined on T^r and have an absolutely convergent Fourier series

. Set $\text{∥?∥ = ∑ ¦?}{}_{\mathrm{k}}\text{¦}$. In this paper the problem of determining the limit of $\text{∥?}{}^{\mathrm{n}}\text{∥}$, as n → ∞, is studied.     

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 Lp estimates for the wave equation

New and more elementary proofs are given of two results due to W. Littman: (1) Let $\text{n ? 2, p ?}\text{2n}\text{(n ? 1)}$. The estimate $\text{∫∫ (¦▽u¦}{}^{\mathrm{p}}\text{+ ¦u}{}_{\mathrm{t}}\text{¦}{}^{\mathrm{p}}\text{) dx dt ? C ∫∫ ¦□u¦}{}^{\mathrm{p}}\text{dx dt}$ cannot hold for all u?C₀^∞(Q), Q a cube in $\text{R}{}^{\mathrm{<mi\; mathvariant="italic"\; is="true">n</mi>}}\text{× R}$, some constant C. (2) Let n ? 2, p ≠ 2. The estimate $\text{∫ (¦▽(t)¦}{}^{\mathrm{p}}\text{+ ¦u}{}_{\mathrm{t}}\text{(t)¦}{}^{\mathrm{p}}\text{) dx ? C(t) ∫ (¦▽u(0)¦}{}^{\mathrm{p}}\text{+ ¦u}{}_{\mathrm{t}}\text{(0)¦}{}^{\mathrm{p}}\text{) dx}$ cannot hold for all C^∞ solutions of the wave equation □u = 0 in $\text{R}{}^{\mathrm{n}}\text{x R}$; all t ?$\text{R}$; some function C: $\text{R}$ → $\text{R}$.     

Sublinear perturbations of the differential equation y(n) = 0 and of the analogous difference equation

According to a result of A. Ghizzetti, for any solution y(t) of the differential equation where $\text{y}{}^{\mathrm{(n)}}\text{(t)+}\text{∑}\text{i=0}\text{n?1}\text{g}{}_{\mathrm{i}}\text{(t) y}{}^{\mathrm{i}}\text{(t)=0}\text{(t ? 1)}$, $\text{∝}{}_1{}^{\mathrm{\infty }}\text{¦g}{}_{\mathrm{i}}\text{(x)¦x}{}^{\mathrm{n?I?1}}\text{dx < ∞}$ (0 ?i ? n ?1, either y(t) = 0 for t ? 1 or there is an integer r with 0 ? r ? n ? 1 such that $\text{lim}\text{t → ∞}\text{y(t)}\text{t}{}^{\mathrm{r}}$ exists and ≠0. Related results are obtained for difference and differential inequalities. A special case of the former has interesting applications in the study of orthogonal polynomials.     

Product formulas for semigroups with elliptic generators

Real constant coefficient nth order elliptic operators, Q, which generate strongly continuous semigroups on L²($\text{R}$^k) are analyzed in terms of the elementary generator,

$\text{A = (?n)}{}^{\mathrm{<mtext>(</mtext><mtext>n</mtext><mtext>2</mtext><mtext>\; ?\; 1</mtext>}}\text{)(n!)}{}^{\mathrm{?1}}\text{∑}\text{k}\text{j = 1}\text{?}{}^{\mathrm{n}}\text{?x}{}_{\mathrm{j}}{}^{\mathrm{n}}$

, for n even. Integral operators are defined using the fundamental solutions p_n(x, t) to u_t = Au and using real polynomials q_l,…, q_k on $\text{R}$^m by the formula, for q = (q_l,…, q_k),

$\text{(F(t)?)(x) = ∫}$

_$\text{R}$m

$\text{?(x + q(z)) P}{}_{\mathrm{n}}\text{(z, t)dz}$

. It is determined when, strongly on L²($\text{R}$^k),

$\text{e}{}^{\mathrm{tQ}}\text{=}\text{lim}\text{j → ∞}\text{F}\text{t}\text{j}{}^{\mathrm{j}}$

. If n = 2 or k = 1, this can always be done. Otherwise the symbol of Q must have a special form.     

Factorization of fredholm operators on analytic functions

Let Ω be a simply connected domain in the complex plane, and $\text{A(Ω}{}^{\mathrm{n}}\text{)}$, the space of functions which are defined and analytic on $\text{Ω}{}^{\mathrm{n}}$, if K is the operator on elements $\text{u(t, a}{}_1\text{, …, a}{}_{\mathrm{n}}\text{)}\text{of}\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ defined in terms of the kernels k_i(t, s, a₁, …, a_n) in $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$ by is the identity operator on $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$, then the operator I ? K may be factored in the form (I ? K)(M ? W) = (I ? ΠK)(M ? ΠW). Here, W is an operator on $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ defined in terms of a kernel w(t, s, a₁, …, a_n) in $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$ by Wu = ∝_an^tw(t, s, a₁, …, a_n) u(s, a₁, …, a_n) ds. ΠW is the operator; ΠWu = ∝_{an ? 1}w(t, s, a₁, …, a_n) u(s, a₁, …, a_n) ds. ΠK is the operator; ΠKu = ∑_{i = 1}^{n ? 1} ∝_ai^tk_i(t, s, a₁, …, a_n) ds + ∝_{an ? 1}^tk_n(t, s, a₁, …, a_n) u(s, a₁, …, a_n) ds. The operator M is of the form m(t, a₁, …, a_n)I, where $\text{m ? A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ and maps elements of $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ into itself by multiplication. The function m is uniquely derived from K in the following manner. The operator K defines an operator $\text{K}{}^1$ on functions u in $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$, by . A determinant $\text{δ(I ? K}{}^1\text{)}$ of the operator $\text{I ? K}{}^1$ is defined as an element $\text{m}{}^1\text{(t, a}{}_1\text{, …, a}{}_{\mathrm{n\; +\; 1}}\text{)}$ of $\text{A(Ω}{}^{\mathrm{n\; +\; 2}}\text{)}$. This is mapped into $\text{A(Ω}{}^{\mathrm{n\; +\; 1}}\text{)}$ by setting a_{n + 1} = t to give m(t, a₁, …, a_n). The operator I ? ΠK may be factored in similar fashion, giving rise to a chain factorization of I ? K. In some cases all the matrix kernels k_i defining K are separable in the sense that k_i(t, s, a₁, …, a_n) = P_i(t, a₁, …, a_n) Q_i(s, a₁, …, a_n), where P_i is a 1 × p_i matrix and Q_i is a p_i × 1 matrix, each with elements in $\text{A(Ω}{}_{\mathrm{n\; +\; 1}}\text{)}$, explicit formulas are given for the kernels of the factors W. The various results are stated in a form allowing immediate extension to the vector-matrix case.     

Sobolev inequalities with remainder terms

The usual Sobolev inequality in $\text{R}$ⁿ, n ? 3, asserts that , with S_n being the sharp constant. This paper is concerned, instead, with functions restricted to bounded domains Ω ? $\text{R}$ⁿ. Two kinds of inequalities are established: (i) If ? = 0 on ?Ω, then with $\text{p =}\text{2}{}^1\text{2}$ and with $\text{q =}\text{n}\text{(n ? 1)}$. (ii) If ? ≠ 0 on ?Ω, then with $\text{q =}\text{2(n ? 1)}\text{(n ? 2)}$. Some further results and open problems in this area are also presented.     

Laws of iterated logarithm of multiparameter wiener processes

Let {$\text{X(}\text{t}\text{) :}\text{t}\text{∈ R}{}_{\mathrm{+}}{}^{\mathrm{N}}$} denote the N-parameter Wiener process on $\text{R}{}_{\mathrm{+}}{}^{\mathrm{N}}\text{= [0, ∞)}{}^{\mathrm{n}}$. For multiple sequences of certain independent random variables the authors find lower bounds for the distributions of maximum of partial sums of these random variables, and as a consequence a useful upper bound for the yet unknown function , c ≥ 0, is obtained where D_N = Π_{k = 1}^N [0, T_k]. The latter bound is used to give three different varieties of N-parameter generalization of the classical law of iterated logarithm for the standard Brownian motion process.     

Generalized Schur complements

Let A be an n×n complex matrix. For a suitable subspace $\text{M}$ of Cⁿ the Schur compression A _$\text{M}$ and the (generalized) Schur complement A_/$\text{M}$ are defined. If A is written in the form

$\text{A=}\text{B}\text{C}\text{S}\text{T}$

according to the decomposition $\text{C}{}^{\mathrm{n}}\text{=}\text{M}\text{⊕}\text{M}{}^{\mathrm{\perp }}$ and if B is invertible, then

$\text{A}{}_{\mathrm{<mtext>M</mtext>}}\text{=}\text{B}\text{C}\text{S}\text{SB}{}^{\mathrm{?1}}\text{C}$

and

$\text{A}{}_{\mathrm{<mtext>/</mtext><mtext>M</mtext>}}\text{=}\text{0}\text{0}\text{0}\text{T?SB}{}^{\mathrm{?1}}\text{C}\text{·}$

The commutativity rule for Schur complements is proved:

$\text{(A}{}_{\mathrm{<mtext>/</mtext><mtext>M</mtext>}}\text{)}{}_{\mathrm{<mtext>/</mtext><mtext>N</mtext>}}\text{=(A)}{}_{\mathrm{<mtext>/</mtext><mtext>N</mtext>}}\text{)}{}_{\mathrm{<mtext>/</mtext><mtext>M</mtext>}}\text{·}$

This unifies Crabtree and Haynsworth's quotient formula for (classical) Schur complements and Anderson's commutativity rule for shorted operators. Further, the absorption rule for Schur compressions is proved:

$\text{(A}{}_{\mathrm{<mtext>/</mtext><mtext>M</mtext>}}\text{)}{}_{\mathrm{<mtext>N</mtext>}}\text{=(A}{}_{\mathrm{<mtext>N</mtext>}}\text{)}{}_{\mathrm{<mtext>M</mtext>}}\text{=A}{}_{\mathrm{<mtext>M</mtext>}}\text{whenever}\text{M}\text{?}\text{N}$

.     

Sharp Sobolev type inequalities for higher fractional derivativesInégalités optimales de type Sobolev pour les dérivées fractionelles d'ordre supérieur

On $\text{R}{}^{\mathrm{n}}$, n?1 and n≠2, we prove the existence of a sharp constant for Sobolev inequalities with higher fractional derivatives. Let s be a positive real number. For n>2s and $\text{q=}\text{2n}\text{n?2s}$ any function $\text{f∈}\text{H}{}^{\mathrm{s}}\text{(}\text{R}{}^{\mathrm{n}}\text{)}$ satisfies

$\text{6f6}{}^2{}_{\mathrm{q}}\text{?S}{}_{\mathrm{n,s}}\text{(?Δ)}{}^{\mathrm{s/2}}\text{f}{}^2{}_2\text{,}$

where the operator (?Δ)^s in Fourier spaces is defined by $\text{(?Δ)}{}^{\mathrm{s}}\text{f}\text{(k):=(2π|k|)}{}^{\mathrm{2s}}\text{f}\text{(k)}$. To cite this article: A. Cotsiolis, N.C. Tavoularis, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 801–804.     

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.