Differentiable Eigenvalues of Perturbed Quadratic Matrix Functions

Let T(λ, ε ) = λ² + λC + λεD + K be a perturbed quadratic matrix polynomial, where C, D, and K are n × n hermitian matrices. Let λ₀ be an eigenvalue of the unperturbed matrix polynomial T(λ, 0). With the falling part of the Newton diagram of det T(λ, ε), we find the number of differentiable eigenvalues. Some results are extended to the general case L(λ, ε) = λ² + λD(ε) + K, where D(ε) is an analytic hermitian matrix function. We show that if K is negative definite on Ker L(λ₀, 0), then every eigenvalue λ(ε) of L(λ, ε) near λ₀ is analytic.     

Estimating the distance to a monotone function

In standard property testing, the task is to distinguish between objects that have a property 𝒫 and those that are ε‐far from 𝒫, for some ε > 0. In this setting, it is perfectly acceptable for the tester to provide a negative answer for every input object that does not satisfy 𝒫. This implies that property testing in and of itself cannot be expected to yield any information whatsoever about the distance from the object to the property. We address this problem in this paper, restricting our attention to monotonicity testing. A function f : {1,…,n} ↦ R is at distance ε_f from being monotone if it can (and must) be modified at ε_fn places to become monotone. For any fixed δ > 0, we compute, with probability at least 2/3, an interval [(1/2 − δ)ε,ε] that encloses ε_f. The running time of our algorithm is O(ε_f⁻¹ log log ε_f^{− 1} log n), which is optimal within a factor of loglog ε_f⁻¹ and represents a substantial improvement over previous work. We give a second algorithm with an expected running time of O(ε_f⁻¹ log nlog log log n). Finally, we extend our results to multivariate functions. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Modulated waves in a semiclassical continuum limit of an integrable NLS chain

A one‐dimensional integrable lattice system of ODEs for complex functions Q_n(τ) that exhibits dispersive phenomena in the phase is studied. We consider wave solutions of the local form Q_n(τ) ∼ qexp(i(kn + ωτ + c)), in which q, k, and ω modulate on long time and long space scales t = ετ and x = εn. Such solutions arise from initial data of the form Q_n(0) = q(nε) exp(iϕ(nε)/ε), the phase derivative ϕ′ 0 giving the local value of the phase difference k. Formal asymptotic analysis as ε → 0 yields a first‐order system of PDEs for q and ϕ′ as functions of x and t. A certain finite subchain of the discrete system is solvable by an inverse spectral transform. We propose formulae for the asymptotic spectral data and use them to study the limiting behavior of the solution in the case of initial data |Q_n| < 1, which yield hyperbolic PDEs in the formal limit. We show that the hyperbolic case is amenable to Lax‐Levermore theory. The associated maximization problem in the spectral domain is solved by means of a scalar Riemann‐Hilbert problem for a special class of data for all times before breaking of the formal PDEs. Under certain assumptions on asymptotic behaviors, the phase and amplitude modulation of the discrete systems is shown to be governed by the formal PDEs. Modulation equations after breaking time are not studied. Full details of the WKB theory and numerical results are left to a future exposition. © 2000 John Wiley & Sons, Inc.     

The scaling window of the 2‐SAT transition

We consider the random 2‐satisfiability (2‐SAT) problem, in which each instance is a formula that is the conjunction of m clauses of the form x∨y, chosen uniformly at random from among all 2‐clauses on n Boolean variables and their negations. As m and n tend to infinity in the ratio m/n→α, the problem is known to have a phase transition at α_c=1, below which the probability that the formula is satisfiable tends to one and above which it tends to zero. We determine the finite‐size scaling about this transition, namely the scaling of the maximal window W(n, δ)=(α_?(n,δ), α₊(n,δ)) such that the probability of satisfiability is greater than 1?δ for α<α_? and is less than δ for α>α₊. We show that W(n,δ)=(1?Θ(n^?1/3), 1+Θ(n^?1/3)), where the constants implicit in Θ depend on δ. We also determine the rates at which the probability of satisfiability approaches one and zero at the boundaries of the window. Namely, for m=(1+ε)n, where ε may depend on n as long as |ε| is sufficiently small and |ε|n^1/3 is sufficiently large, we show that the probability of satisfiability decays like exp(?Θ(nε³)) above the window, and goes to one like 1?Θ(n^?1|ε|^?3 below the window. We prove these results by defining an order parameter for the transition and establishing its scaling behavior in n both inside and outside the window. Using this order parameter, we prove that the 2‐SAT phase transition is continuous with an order parameter critical exponent of 1. We also determine the values of two other critical exponents, showing that the exponents of 2‐SAT are identical to those of the random graph. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 201–256 2001     

Uniform approximation by some Hermite interpolating splines

In this paper some upper bound for the error ∥ s-f ∥_∞ is given, where f ε C¹[a,b], but s is a so-called Hermite spline interpolant (HSI) of degree 2q ?1 such that f(x_i) = s(x_i), f′(rmx_i) = s′(x_i), s^(j) (x_i) = 0 (i = 0, 1, …, n; j = 2, 3, …, q ?1; n > 0, q > 0) and the knots x_i are such that a = x₀ < x₁ < … < x_n = b. Necessary and sufficient conditions for the existence of convex HSI are given and upper error bound for approximation of the function fε C¹[a, b] by convex HSI is also given.     

On the homogenization of some linear problems in domains weakly connected by a system of traps

The aim of the paper is to study the asymptotic behaviour of solutions of second‐order elliptic and parabolic equations, arising in modelling of flow in cavernous porous media, in a domain Ω^ε weakly connected by a system of traps ??^ε, where ε is the parameter that characterizes the scale of the microstructure. Namely, we consider a strongly perforated domain Ω^ε ?Ω a bounded open set of ?³ such that Ω^ε =Ω₁^ε ∪Ω₂^ε ∪??^ε ∪ W^ε, where Ω₁^ε, Ω₂^ε are non‐intersecting subdomains strongly connected with respect to Ω, ??^ε is a system of traps and meas W^ε → 0 as ε → 0. Without any periodicity assumption, for a large range of perforated media and by means of variational homogenization, we find the homogenized models. The effective coefficients are described in terms of local energy characteristics of the domain Ω^ε associated with the problem under consideration. The resulting homogenized problem in the parabolic case is a vector model with memory terms. An example is presented to illustrate the methodology. Copyright © 2007 John Wiley & Sons, Ltd.     

Multidimensional Oscillations for Non-linear Hyperbolic Mixed Problem: The Justified Non-linear Geometric Optics Method

The mixed-Neumann problem for the non-linear wave equation □u−a(u)(∣∂_tu)∣²−∣∇u∣² = f_ε(z) is studied. The function f_ε(z) = ∑_k∈Kf_k(z,ε⁻¹ϕ_k(z),ε), ε∈[0,1], K is finite, f_k(z,θ_k,ε) are 2π-periodic with respect to θ_k. The existence of solution u_ε on a domain z = (t,x,y)∈[0,T]×ℝ₊×ℝ^d, d = 1 or 2, is proved when ε is sufficiently small; T does not depend on ε. By the non-linear geometric optics method the asymptotic (with respect to ε→0) solution ũ _ε is constructed. The estimation for the rest ε²r_ε = u_ε−ũ_ε is derived and the limit r_ε, ε→0, is studied.     

Embedding Subspaces of Lp into 𝓁Np, 0 < p < 1

It is shown that if X is an n – dimensional subspace of L_p, 0 < p < 1, then there exists a subspace Y of 𝓁^N_p such that d(X, Y) ≤ 1 + ε and N ≤ C(ε, p)n(log n)³.     

The critical behavior of random digraphs

We study the critical behavior of the random digraph D(n,p) for np = 1 + ε, where ε = ε(n) = o(1). We show that if ε³n →—∞, then a.a.s. D(n,p) consists of components which are either isolated vertices or directed cycles, each of size O_p(|ε|^?1). On the other hand, if ε³n →∞, then a.a.s. the structure of D(n,p) is dominated by the unique complex component of size (4 + o(1))ε²n, whereas all other components are of size O_p(ε^?1). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On the Paper "Asymptotics for the Moments of Singular Distributions"

In their 1993 paper, W. Goh and J. Wimp derive interesting asymptotics for the moments c_n(α) ≡ c_n = ∫¹₀tⁿdα(t), N = 0, 1, 2, ..., of some singular distributions α (with support [0, 1]), which contain oscillatory terms. They suspect, that this is a general feature of singular distributions and that this behavior provides a striking contrast with what happens for absolutely continuous distributions. In the present note, however, we give an example of an absolutely continuous measure with asymptotics of moments containing oscillatory terms, and an example of a singular measure having very regular asymptotic behavior of its moments. Finally, we give a short proof of the fact that the drop-off rate of the moments is exactly the local measure dimension about 1 (if it exists).     

On the value of a random minimum spanning tree problem

Suppose we are given a complete graph on n vertices in which the lenghts of the edges are independent identically distributed non-negative random variables. Suppose that their common distribution function F is differentiable at zero and D = F′ (0) > 0 and each edge length has a finite mean and variance. Let L_n be the random variable whose value is the length of the minimum spanning tree in such a graph. Then we will prove the following: lim_{n → ∞}E(L_n) = ζ(3)/D where ζ(3) = Σ_{k = 1}^∞ 1/k³ = 1.202… and for any ε > 0 lim_{n → ∞} Pr(|L_n^?ζ(3)/D|) > ε) = 0.     

Existence of a low rank or ℋ︁‐matrix approximant to the solution of a Sylvester equation

We consider the Sylvester equation AX?XB+C=0 where the matrix C∈?^n×m is of low rank and the spectra of A∈?^n×n and B∈?^m×m are separated by a line. We prove that the singular values of the solution X decay exponentially, that means for any ε∈(0,1) there exists a matrix X? of rank k=O(log(1/ε)) such that ∥X?X?∥₂?ε∥X∥₂. As a generalization we prove that if A,B,C are hierarchical matrices then the solution X can be approximated by the hierarchical matrix format described in Hackbusch (Computing 2000; 62 : 89–108). The blockwise rank of the approximation is again proportional to log(1/ε). Copyright © 2004 John Wiley & Sons, Ltd.     

A recurrence relation for the square root

The behavior of the sequence x_{n + 1} = x_n(3N − x_n²)/2N is studied for N > 0 and varying real x₀. When 0 < x₀ < (3N)^1/2 the sequence converges quadratically to N^1/2. When x₀ > (5N)^1/2 the sequence oscillates infinitely. There is an increasing sequence β_r, with β₋₁ = (3N)^1/2 which converges to (5N)^1/2 and is such that when β_r < x₀ < β_{r + 1} the sequence {x_n} converges to (−1)^rN^1/2. For x₀ = 0, β₋₁, β₀,… the sequence converges to 0. For x₀ = (5N)^1/2 the sequence oscillates: x_n = (−1)ⁿ(5N)^1/2. The behavior for negative x₀ is obtained by symmetry.     

On the L convergence of Lagrange interpolating entire functions of exponential type

Let f: be a continuous, 2π-periodic function and for each n ε let t_n(f; ·) denote the trigonometric polynomial of degree n interpolating f in the points 2kπ/(2n + 1) (k = 0, ±1, …, ±n). It was shown by J. Marcinkiewicz that lim_{n → ∞} ∝₀^2π¦f(θ) − t_n(f θ)¦^p dθ = 0 for every p > 0. We consider Lagrange interpolation of non-periodic functions by entire functions of exponential type τ > 0 in the points kπ/τ (k = 0, ± 1, ± 2, …) and obtain a result analogous to that of Marcinkiewicz.     

Decrease rate of the probabilities ofε-deviations for the means of stationary processes

The asymptotic behavior asn → ∞ of the normed sumsσn =n ^?1 Σ _k ^=0n?1 Xk for a stationary processX = (X _n ,n ∈ ?) is studied. For a fixedε > 0, upper estimates for P(sup _k≥n ¦σ _k ¦ ≥ε) asn → ∞ are obtained.     

On the Existence of Multiple Periodic Solutions for the Vector <Emphasis Type="Italic">p</Emphasis>-Laplacian via Critical Point Theory

We study the vector p-Laplacian

On the Maximum Number of Cycles in Outerplanar and Series–Parallel Graphs

Let c(n) be the maximum number of cycles in an outerplanar graph with n vertices. We show that lim c(n)^1/n exists and equals β = 1.502837 . . ., where β is a constant related to the recurrence x_n+1 = 1 + x_n²,  x₀=1{x_{n+1} = 1 + x_n^2, \, x_0=1}. The same result holds for the larger class of series–parallel graphs.     

Asymptotic expansions of the distributions of some test statistics for Gaussian ARMA processes

Let {X_t} be a Gaussian ARMA process with spectral density f_θ(λ), where θ is an unknown parameter. The problem considered is that of testing a simple hypothesis H:θ = θ₀ against the alternative A:θ ≠ θ₀. For this problem we propose a class of tests , which contains the likelihood ratio (LR), Wald (W), modified Wald (MW) and Rao (R) tests as special cases. Then we derive the χ² type asymptotic expansion of the distribution of T up to order n⁻¹, where n is the sample size. Also we derive the χ² type asymptotic expansion of the distribution of T under the sequence of alternatives A_n: θ = θ₀ + /√n, ε > 0. Then we compare the local powers of the LR, W, MW, and R tests on the basis of their asymptotic expansions.     

A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.