A vector exchange property of submodular systems

Generalizing the multiple basis exchange property for matroids, the following theorem is proved: If x and y are vectors of a submodular system in $\text{R}{}^{\mathrm{E}}$ and $\text{x}{}_1\text{,x}{}_2\text{?}\text{R}{}^{\mathrm{E}}$ such that x = x₁ + x₂, then there are $\text{y}{}_1\text{,y}{}_2\text{?}\text{R}{}^{\mathrm{E}}$ such that y = y₁ + y₂ and both x₁ + y₁ and x₂ + y₂ belong to the submodular system.An integral analogue holds for the integral submodular systems and a non-negative analogue for polymatroids.     

Starting in maximum-polynomial-degree Nordsieck-Gear methods

The intent of this paper is to show that the Nordsieck-Gear methods with maximum polynomial degree k+1, first described in [1], admit of matched starting methods which are exact for all polynomials of degree ?k+1. In general, it is shown that these starting methods yield starting errors of the required order, O(h^k+2), for all initial-value problems

$\text{y}{}^{\mathrm{(P)}}\text{(x)=f(x,y,y}{}^{\mathrm{(1)}}\text{,y}{}^{\mathrm{(2)}}\text{,…,y}{}^{\mathrm{(p?1)}}\text{),}$

$\text{y(0)=y}{}_0\text{, y}{}^{\mathrm{i}}\text{(0)=y}{}_0{}^{\mathrm{(i)}}\text{, i=1,2,…,p?1,}$

where f is k+1 times continuously differentiable in a neighborhood of the graph of the exact solution (x,?(x)), x?[0,X]. Two theorems are proved. The first is the constructive existence of an algorithm which requires (k-p+1)(k-p+2)/2 evaluations of the function f to obtain approximations of the method's required higher-order scaled derivatives at the origin:

$\text{h}{}^{\mathrm{p+1}}\text{y}\text{?}{}^{\mathrm{(p+1)}}\text{(0)}\text{(p+1)!}\text{,…,}\text{h}{}^{\mathrm{k}}\text{y}\text{?}{}^{\mathrm{(k)}}\text{(0)}\text{k!}\text{,}$

each of which is accurate to O(h^k+2). The second, less general theorem, shows that when f is a polynomial in x, y, and its higher order derivatives y⁽¹⁾,y⁽²⁾,…,y(^p?1), an algorithm can be constructed for obtaining the higher-order scaled derivatives exactly. These results lay to rest once and for all any heuristic arguments against varying corrector minus predictor coefficients for preserving maximal order (polynomial degree) because starting values are inexact. Furthermore, and perhaps most importantly, the maximum-polynomial-degree Nordsieck-Gear methods are shown to have a unique property of zero starting error for an important class of ordinary differential equations.     

Generalizations of two inequalities involving hermitian forms

Let λ₁ and λ_N be, respectively, the greatest and smallest eigenvalues of an N×N hermitian matrix H=(h_ij), and x=(x₁,x₂,…,x_N) with (x,x)=1. Then, it is known that (1) λ₁?(x,Hx)?λ_N and (2) if, in addition, H is positive definite, $\text{(λ}{}_1\text{+λ}{}_{\mathrm{N}}\text{)}{}^2\text{4λ}{}_1\text{λ}{}_{\mathrm{N}}\text{?(x,Hx)(x,H}{}^{\mathrm{?1}}\text{x)?1}$. Assuming that y=(y₁,y₂,…, y_N) and |y_i|?1, i=1,2,…,N, it is shown in this paper that these inequalities remain true if H and H^?1 are, respectively, replaced by the Hadamard products $\text{M(y)1H}$ and $\text{M(y)1H}{}^{\mathrm{?1}}$, where M(y) is a matrix defined by $\text{M(y)=(δ}{}_{\mathrm{ij}}\text{+(1?δ}{}_{\mathrm{ij}}\text{)}\text{y}{}_{\mathrm{i}}\text{y}{}_{\mathrm{j}}$. Subsequently, these results are extended to improve the spectral bounds of $\text{M(y)1H}$.     

Arnold's canonical matrices and the asymptotic simplification of ordinary differential equations

Let A(x,ε) be an n×n matrix function holomorphic for |x|?x₀, 0<ε?ε₀, and possessing, uniformly in x, an asymptotic expansion $\text{A(x,ε)?Σ}{}^{\mathrm{\infty }}{}_{\mathrm{r=0}}\text{A}{}_{\mathrm{r}}\text{(x) ε}{}^{\mathrm{r}}$, as ε→0⁺. An invertible, holomorphic matrix function P(x,ε) with an asymptotic expansion $\text{P(x,ε)?Σ}{}^{\mathrm{\infty }}{}_{\mathrm{r=0}}\text{P}{}_{\mathrm{r}}\text{(x)ε}{}^{\mathrm{r}}$, as ε→0⁺, is constructed, such that the transformation y = P(x,ε)z takes the differential equation $\text{ε}{}^{\mathrm{h}}\text{dy}\text{dx}\text{= A(x,ε)y,h}$ a positive integer, into $\text{ε}{}^{\mathrm{h}}\text{dz}\text{dx}\text{= B(x,ε)z}$, where B(x,ε) is asymptotically equal, to all orders, to a matrix in a canonical form for holomorphic matrices due to V.I. Arnold.     

Diophantine inequalities with mixed powers

It is shown that λ₁, λ₂,…, λ₆, μ are not all of the same sign and at least one ratio $\text{λ}{}_{\mathrm{i}}\text{λ}{}_{\mathrm{j}}$ is irrational then the values taken by $\text{λ}{}_1\text{x}{}_1{}^3\text{+ ? + λ}{}_6\text{x}{}_6{}^3\text{+ μy}{}^3$ for integer values of x₁ ,…, x₆, y are everywhere dense on the real line. A similar result holds for expressions of the form $\text{λ}{}_1\text{x}{}_1{}^3\text{+ ? + λ}{}_4\text{x}{}_4{}^3\text{+ μ}{}_1\text{y}{}_1{}^2\text{+ μ}{}_2\text{y}{}_2{}^3$.     

Some aspects of the finite moment problem

The approximate solution of the finite moment problem $\text{μ}{}_{\mathrm{k}}\text{= ∫}{}_0{}^1\text{x}{}^{\mathrm{k?1}}\text{?(x)}\text{d}\text{x}$, k = 1, 2, 3, …, is considered. This problem is related to the problem of finding a best polynomial least squares approximation to a given function $\text{?(x)}$ in [0,1]. The connection with Laplace transform inversion is emphasized, and a set of special square matrices with integral elements is introduced, which has an intimate relation to the above two problems. These matrices are the well-known inverses of finite segments of the infinite Hilbert matrix.     

On the normal form of a system of differential equations with nilpotent linear part

We consider prenormal forms associated to generic perturbations of the system $\text{x}\text{?}\text{=2y,}\text{y}\text{?}\text{=3x}{}^2$. It is known that they have a formal normal form $\text{x}\text{?}\text{=2y+2x}\text{Δ}{}^1\text{,}\text{y}\text{?}\text{=3x}{}^2\text{+3y}\text{Δ}{}^1$, where $\text{Δ}{}^1\text{=x+A}{}_0\text{(y}{}^2\text{?x}{}^3\text{)}$ [Differential Equations 158 (1) (1999) 152–173]. We show that the series A₀ and the normalizing transformations are divergent, but 1-summable. To cite this article: M. Canalis-Durand, R. Schäfke, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Infinite-variate wide-sense Markov processes and functional analysis for bounded operator-forming vectors

Let p, q be arbitrary parameter sets, and let $\text{H}$ be a Hilbert space. We say that x = (xⁱ)_i?q, xⁱ ? $\text{H}$, is a bounded operator-forming vector (?$\text{H}$_F^q) if the Gram matrix 〈x, x〉 = [(xⁱ, x^j)]_i?q,j?q is the matrix of a bounded (necessarily ≥ 0) operator on $\text{l}{}_{\mathrm{q}}{}^2$, the Hilbert space of square-summable complex-valued functions on q. Let A be p × q, i.e., let A be a linear operator from $\text{l}{}_{\mathrm{q}}{}^2$ to $\text{l}{}_{\mathrm{p}}{}^2$. Then exists a linear operator ǎ from (the Banach space) $\text{H}$_F^q to $\text{H}$_F^p on $\text{D}$(A) = {x:x ? $\text{H}$_F^q, $\text{A〈x, x〉}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ is p × q bounded on $\text{l}{}_{\mathrm{q}}{}^2$} such that y = ǎx satisfies y^j?σ(x) = {space spanned by the xⁱ}, 〈y, x〉 = A〈x, x〉 and $\text{〈y, y〉 = A〈x, x〉}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{(A〈x, x〉}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}{}^1$. This is a generalization of our earlier [J. Multivariate Anal.4 (1974), 166–209; 6 (1976), 538–571] results for the case of a spectral measure concentrated on one point. We apply these tools to investigate q-variate wide-sense Markov processes.     

Temporal exponential decay for the Stark effect in atoms

Let $\text{H}{}_1\text{= ?∑}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{N}}\text{(Δ}{}_{\mathrm{i}}\text{+ V(}\text{x}{}_{\mathrm{i}}\text{)) + ∑}{}_{\mathrm{1\; ?\; i\; <j\; ?\; N}}\text{¦}\text{x}{}_{\mathrm{i}}\text{?}\text{x}{}_{\mathrm{j}}\text{¦}{}^{\mathrm{?1}}\text{, V(}\text{x}{}_{\mathrm{i}}\text{) = N ∝ ¦}\text{x}\text{?}\text{y}\text{¦}{}^{\mathrm{?1}}\text{?(}\text{y}\text{)d}\text{y}$, with ? a normalized Gaussian. Suppose $\text{E}$ ≠ 0 and that $\text{H = H}{}_1\text{+}\text{E}\text{· (∑}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{N}}\text{x}{}_{\mathrm{i}}\text{)}$ has no eigenfunctions in L²($\text{R}$^3N. If H₁ψ = μψ with μ < infσ_ess(H₁), then (ψ, e^?itHψ) decays exponentially at a rate governed by the positions of the resonances of H.     

Identities for sums of Dedekind type

Sums of Dedekind type are defined by the formula $\text{f(h, k) =}\text{Σ}{}_{\mathrm{<mtext>\mu (</mtext><mtext>mod</mtext><mtext>\; k)</mtext>}}\text{A(}\text{μ}\text{k}\text{) B(}\text{hμ}\text{k}\text{)}$, where each of A(x) and B(x) satisfies a multiplication formula of the form $\text{Σ}{}_{\mathrm{<mtext>b(</mtext><mtext>mod</mtext><mtext>\; q)</mtext>}}\text{F(x +}\text{b}\text{q}\text{) = q}{}^{\mathrm{\nu (F)}}\text{F(qx)}$. Properties of these sums are obtained, including an extension of M. I. Knopp's identity for the classical Dedekind sums s(h, k).     

The existence,uniqueness, and instability of spherically symmetric solutions of a system of reaction—Diffusion equations

The system $\text{?x}\text{?t}\text{= Δx + F(x,y),}\text{?y}\text{?t}\text{= G(x,y)}$ is investigated, where x and y are scalar functions of time (t ? 0), and n space variables $\text{(ξ}{}_1\text{,…, ξ}{}_{\mathrm{n}}\text{), Δx ≡ ∑}{}_{\mathrm{i\; =\; 1}}{}^{\mathrm{n}}\text{?}{}^2\text{x}\text{?ξ}{}_{\mathrm{i}}{}^2$, and F and G are nonlinear functions. Under certain hypotheses on F and G it is proved that there exists a unique spherically symmetric solution $\text{(x(r),y(r)),}\text{where}\text{r = (ξ}{}_1{}^2\text{+ … + ξ}{}_{\mathrm{n}}{}^2\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, which is bounded for r ? 0 and satisfies x(0) >x₀, y(0) > y₀, x′(0) = 0, y′(0) = 0, and x′ < 0, y′ > 0, ?r > 0. Thus, (x(r), y(r)) represents a time independent equilibrium solution of the system. Further, the linearization of the system restricted to spherically symmetric solutions, around (x(r), y(r)), has a unique positive eigenvalue. This is in contrast to the case n = 1 (i.e., one space dimension) in which zero is an eigenvalue. The uniqueness of the positive eigenvalue is used in the proof that the spherically symmetric solution described is unique.     

Numerical approximation of product integrals

A technique for the numerical approximation of matrix-valued Riemann product integrals is developed. For a ? x < y ? b, I_m(x, y) denotes

$\text{∫}\text{χ}\text{y}\text{∫}\text{χ}\text{v}{}_2\text{?}\text{∫}\text{χ}\text{v}{}_2\text{∏}\text{i=1}\text{m}\text{F(ν}{}_{\mathrm{i}}\text{)dν}{}_1\text{dν}{}_2\text{?dν}{}_{\mathrm{m}}$

, and A_m(x, y) denotes an approximation of I_m(x, y) of the form

$\text{(y?x)}{}^{\mathrm{m}}\text{∑}\text{k=1}\text{n}\text{a}{}_{\mathrm{k}}\text{∏}\text{i=1}\text{m}\text{F(χ}{}_{\mathrm{ik}}\text{)}$

, where a_k and y_ik are fixed numbers for i = 1, 2,…, m and k = 1, 2,…, N and x_ik = x + (y ? x)y_ik. The following result is established. If p is a positive integer, F is a function from the real numbers to the set of w × w matrices with real elements and F⁽¹⁾ exists and is continuous on [a, b], then there exists a bounded interval function H such that, if n, r, and s are positive integers, $\text{(b ? a)}\text{n}\text{= h < 1, x}{}_{\mathrm{i}}\text{= a + hi}\text{for}\text{i = 0, 1,…, n}\text{and}\text{0 < r ? s ? n}$, then

$\text{∏}\text{χ}{}_{\mathrm{r?}}\text{χ}{}_{\mathrm{s}}\text{(I+F dχ)?}\text{∏}\text{i=r}\text{s}\text{I+}\text{∑}\text{j=1}\text{p}\text{I}{}_{\mathrm{j}}\text{(χ}{}_{\mathrm{i?1}}\text{,χ}{}_{\mathrm{i}}\text{)}$

$\text{=h}{}^{\mathrm{p}}\text{H(χ}{}_{\mathrm{r?1}}\text{,χ}{}_{\mathrm{s}}\text{)+O(h}{}^{\mathrm{p+1}}\text{)}$

Further, if F^(j) exists and is continuous on [a, b] for j = 1, 2,…, p + 1 and A is exact for polynomials of degree less than p + 1 ? j for j = 1, 2,…, p, then the preceding result remains valid when A_j is substituted for I_j.     

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

     

Wr,p(R)-splines

In [3] Golomb describes, for 1 < p < ∞, the H^r,p(R)-extremal extension $\text{F}{}_1$ of a function $\text{?:E → R}$ (i.e., the H^r,p-spline with knots in E) and studies the cone $\text{H}{}_{1E}{}^{\mathrm{r,p}}$ of all such splines. We study the problem of determining when $\text{F}{}_1$ is in W^r,p ≡ H^r,p ∩ L^p. If $\text{F}{}_1\text{? W}{}^{\mathrm{r,p}}$, then $\text{F}{}_1$ is called a W^r,p-spline, and we denote by $\text{W}{}_{1E}{}^{\mathrm{r,p}}$ the cone of all such splines. If E is quasiuniform, then $\text{F}{}_1\text{? W}{}^{\mathrm{r,p}}$ if and only if . The cone $\text{W}{}_{1E}{}^{\mathrm{r,p}}$ with E quasiuniform is shown to be homeomorphic to l^p. Similarly, $\text{H}{}_{1E}{}^{\mathrm{r,p}}$ is homeomorphic to h^r,p. Approximation properties of the W^r,p-splines are studied and error bounds in terms of the mesh size $\text{¦ E ¦}$ are calculated. Restricting ourselves to the case p = 2 and to quasiuniform partitions E, the second integral relation is proved and better error bounds in terms of $\text{¦ E ¦}$ are derived.     

A note on Ramsey numbers

Upper bounds are found for the Ramsey function. We prove $\text{R(3, x) <}\text{cx}{}^2\text{ln}\text{x}$ and, for each k ? 3, $\text{R(k, x) <}\text{c}{}_{\mathrm{k}}\text{x}{}^{\mathrm{k\; ?\; 1}}\text{(}\text{ln}\text{x)}{}^{\mathrm{k\; ?\; 2}}$ asymptotically in x.     

On the probability that given polynomials have a specified highest common factor

The polynomial functions f₁, f₂,…, f_m are found to have highest common factor h for a set of values of the variables x₁, x₂,…,x_m whose asymptotic density is

$\text{1}\text{h}{}^{\mathrm{n}}\text{∑}\text{d∣h}\text{μ(d)Π}{}^{\mathrm{m}}{}_{\mathrm{l\; =\; 1}}\text{?(f}{}_1\text{, dh)}\text{d}{}^{\mathrm{m}}\text{Π}\text{p∣h}\text{1?}\text{Π}{}^{\mathrm{m}}{}_{\mathrm{l\; =\; 1}}\text{?(f}{}_1\text{, p)}\text{p}{}^{\mathrm{m}}$

For the special case f₁(x) = f₂(x) = … = f_m(x) = x and h = 1 the above formula reduces to $\text{Π}{}_{\mathrm{?}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{m}}\text{) =}\text{1}\text{ζ}\text{(m)}$, the density if m-tuples with highest common factor 1. Necessary and sufficient conditions on the polynomials f₁, f₂,…, f_m for the asymptotic density to be zero are found. In particular it is shown that either the polynomials may never have highest common factor h or else h is the highest common factor infinitely often and in fact with positive density.     

On the Cauchy problem for the generalized Benjamin–Ono equation with small initial data

We prove global well-posedness results for small initial data in $\text{H}{}^{\mathrm{s}}\text{(}\text{R}\text{),}\text{s>s}{}_{\mathrm{k}}$, and in , s_k=1/2?1/k, for the generalized Benjamin–Ono equation $\text{?}{}_{\mathrm{t}}\text{u+}\text{H}\text{?}{}^2{}_{\mathrm{x}}\text{u+?}{}_{\mathrm{x}}\text{(u}{}^{\mathrm{k+1}}\text{)=0,}\text{k?4}$. We also consider the cases k=2,3. To cite this article: L. Molinet, F. Ribaud, C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

A theory for optimal regularization in the finite dimensional case

Consider the matrix problem $\text{Ax = y + ε =}\text{y}\text{?}$ in the case where A is known precisely, the problem is ill conditioned, and ε is a random noise vector. Compute regularized “ridge” estimates,$\text{x}\text{?}{}_{\mathrm{\lambda }}\text{= (A}{}^1\text{A + λI)}{}^{-1}\text{A}{}^1\text{y}\text{?}$,where ¹ denotes matrix transpose. Of great concern is the determination of the value of λ for which x?_λ “best” approximates $\text{x}{}_{\mathrm{<mtext>0</mtext>}}\text{= A}{}^{\mathrm{+}}\text{y}$. Let $\text{Q = 6}\text{x}\text{?}{}_{\mathrm{\lambda }}\text{? x}{}_{\mathrm{<mtext>0</mtext>}}\text{6}{}^2$,and define λ₀ to be the value of λ for which Q is a minimum. We look for λ₀ among solutions of dQ/dλ = 0. Though Q is not computable (since ε is unknown), we can use this approach to study the behavior of λ₀ as a function of y and ε. Theorems involving “noise to signal ratios” determine when λ₀ exists and define the cases λ₀ > 0 and λ₀ = ∞. Estimates for λ₀ and the minimum square error Q₀ = Q(λ₀) are derived.     

Existence and uniqueness of statistical measures for solution processes for linear-stochastic differential equations

Structure is developed on the set of real-valued stochastic processes in terms of the authors recently defined statistical measures making explicit an $\text{L}{}_{\mathrm{p}}{}^{\mathrm{n}}\text{(Ω, T)}$-calculus over the structure. This proves that the stochastic-differential equation $\text{L}$y=x, where x is a stochastic process and $\text{L}$ is an nth order linear-stochastic differential operator with up to n ? 1 stochastic-process coefficients, is solved by Adomian's series, and finally, establishes the existence and uniqueness of the statistical measures of the solution process.     

Isospectral matrices and classical polynomials

The matrices of order n defined, in terms of the n arbitrary numbers x_j, by the formulae $\text{X=}\text{diag}\text{(x}{}_{\mathrm{j}}\text{)}\text{and}\text{Z}{}_{\mathrm{jk}}\text{=δ}{}_{\mathrm{jk}}\text{∑′}\text{l=1}\text{n}\text{(x}{}_{\mathrm{j}}\text{?x}{}_{\mathrm{l}}\text{)}{}^{\mathrm{?1}}\text{+(1?δ}{}_{\mathrm{jk}}\text{(x}{}_{\mathrm{j}}\text{?x}{}_{\mathrm{k}}\text{)}{}^{\mathrm{?1}}$, are representations of the multiplicative operator ξ and of the differential operator d/dξ in a space spanned by the polynomials in ξ of degree less than n. This elementary fact implies a number of remarkable formulae involving these matrices, including novel representations of the classical polynomials.