Integral representation of even positive-definite functions of two variables

We obtain an integral representation of even functions of two variables for which the kernel [k ₁(x + y) + k ₂(x − y)], x, y ∈ R ², is positive definite.     

Partitioning Posets

Given a poset P = (X, ≺ ), a partition X ₁, ..., X _k of X is called an ordered partition of P if, whenever x ∈ X _i and y ∈ X _j with x ≺ y, then i ≤ j. In this paper, we show that for every poset P = (X, ≺ ) and every integer k ≥ 2, there exists an ordered partition of P into k parts such that the total number of comparable pairs within the parts is at most (m − 1)/k, where m ≥ 1 is the total number of edges in the comparability graph of P. We show that this bound is best possible for k = 2, but we give an improved bound, , for k ≥ 3, where c(k) is a constant depending only on k. We also show that, given a poset P = (X, ≺ ) and an integer 2 ≤ k ≤ |X|, we can find an ordered partition of P into k parts that minimises the total number of comparable pairs within parts in time polynomial in the size of P. We prove more general, weighted versions of these results. Supported by an EPSRC doctoral training grant.     

Accelerated hybrid conjugate gradient algorithm with modified secant condition for unconstrained optimization

An accelerated hybrid conjugate gradient algorithm represents the subject of this paper. The parameter β _k is computed as a convex combination of b_k^HS\beta_k^{HS} (Hestenes and Stiefel, J Res Nat Bur Stand 49:409–436, 1952) and b_k^DY\beta_k^{DY} (Dai and Yuan, SIAM J Optim 10:177–182, 1999), i.e. b_k^C = (1-q_k)b_k^HS + q_k b_k^DY\beta_k^C =\left({1-\theta_k}\right)\beta_k^{HS} + \theta_k \beta_k^{DY}. The parameter θ _k in the convex combinaztion is computed in such a way the direction corresponding to the conjugate gradient algorithm is the best direction we know, i.e. the Newton direction, while the pair (s _k , y _k ) satisfies the modified secant condition given by Li et al. (J Comput Appl Math 202:523–539, 2007) B _k + 1 s _k  = z _k , where z_k = y_k +(h_k / || s_k ||² )s_kz_k =y_k +\left({{\eta_k} / {\left\| {s_k} \right\|^2}} \right)s_k, h_k = 2( f_k -f_k+1 )+( g_k +g_k+1 )^Ts_k\eta_k =2\left( {f_k -f_{k+1}} \right)+\left( {g_k +g_{k+1}} \right)^Ts_k, s _k  = x _k + 1 − x _k and y _k  = g _k + 1 − g _k . It is shown that both for uniformly convex functions and for general nonlinear functions the algorithm with strong Wolfe line search is globally convergent. The algorithm uses an acceleration scheme modifying the steplength α _k for improving the reduction of the function values along the iterations. Numerical comparisons with conjugate gradient algorithms show that this hybrid computational scheme outperforms a variant of the hybrid conjugate gradient algorithm given by Andrei (Numer Algorithms 47:143–156, 2008), in which the pair (s _k , y _k ) satisfies the classical secant condition B _k + 1 s _k  = y _k , as well as some other conjugate gradient algorithms including Hestenes-Stiefel, Dai-Yuan, Polack-Ribière-Polyak, Liu-Storey, hybrid Dai-Yuan, Gilbert-Nocedal etc. A set of 75 unconstrained optimization problems with 10 different dimensions is being used (Andrei, Adv Model Optim 10:147–161, 2008).     

Irreducible Width 2 Posets of Linear Discrepancy 3

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x) − h _L (y)| ≤ k, where h _L (x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width 2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique linear extension that witnesses linear discrepancy 2. The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290.     

Strict Betweennesses Induced by Posets as well as by Graphs

For a finite poset P = (V, ≤ ), let _s(P){\cal B}_s(P) consist of all triples (x,y,z) ∈ V ³ such that either x < y < z or z < y < x. Similarly, for every finite, simple, and undirected graph G = (V,E), let B_s(G){\cal B}_s(G) consist of all triples (x,y,z) ∈ V ³ such that y is an internal vertex on an induced path in G between x and z. The ternary relations B_s(P){\cal B}_s(P) and B_s(G){\cal B}_s(G) are well-known examples of so-called strict betweennesses. We characterize the pairs (P,G) of posets P and graphs G on the same ground set V which induce the same strict betweenness relation B_s(P)=B_s(G){\cal B}_s(P)={\cal B}_s(G).     

Variable target value relaxed alternating projection method

In this paper we propose a modification of the von Neumann method of alternating projection x _k+1=P _A P _B x _k where A,B are closed and convex subsets of a real Hilbert space ℋ. If Fix P _A P _B ≠∅ then any sequence generated by the classical method converges weakly to a fixed point of the operator T=P _A P _B . If the distance δ=inf  _x∈A,y∈B ‖ x−y ‖ is known then one can efficiently apply a modification of the von Neumann method, which has the form x _k+1=P _A (x _k +λ _k (P _A P _B x _k −x _k )) for λ _k >0 depending on x _k (for details see: Cegielski and Suchocka, SIAM J. Optim. 19:1093–1106, 2008). Our paper contains a generalization of this modification, where we do not suppose that we know the value δ. Instead of δ we apply its approximation which is updated in each iteration.     

The Lambert W-functions and some of their integrals: a case study of high-precision computation

The real-valued Lambert W-functions considered here are w ₀(y) and w _− 1(y), solutions of we ^w  = y, − 1/e < y < 0, with values respectively in ( − 1,0) and ( − ∞ , − 1). A study is made of the numerical evaluation to high precision of these functions and of the integrals ò₁^￥ [-w₀(-xe^-x)]^a x^-bx\int_1^\infty [-w_0(-xe^{-x})]^\alpha x^{-\beta}\d x, α > 0, β ∈ ℝ, and ò₀¹ [-w_-1(-x e^-x)]^a x^-bx\int_0^1 [-w_{-1}(-x e^{-x})]^\alpha x^{-\beta}\d x, α > − 1, β < 1. For the latter we use known integral representations and their evaluation by nonstandard Gaussian quadrature, if α ≠ β, and explicit formulae involving the trigamma function, if α = β.     

An extension of almost sure central limit theorem for order statistics

Let {X _n ,n ≥ 1} be a sequence of i.i.d. random variables. Let M _n and m _n denote the first and the second largest maxima. Assume that there are normalizing sequences a _n  > 0, b _n and a nondegenerate limit distribution G, such that . Assume also that {d _k ,k ≥ 1} are positive weights obeying some mild conditions. Then for x > y we have

Dependent percolation in two dimensions

For a natural number k, define an oriented site percolation on ℤ² as follows. Let x _i , y _j be independent random variables with values uniformly distributed in {1, …, k}. Declare a site (i, j) ∈ℤ² closed if x _i = y _j , and open otherwise. Peter Winkler conjectured some years ago that if k≥ 4 then with positive probability there is an infinite oriented path starting at the origin, all of whose sites are open. I.e., there is an infinite path P = (i ₀, j ₀)(i ₁, j ₁) · · · such that 0 = i ₀≤i ₁≤· · ·, 0 = j ₀≤j ₁≤· · ·, and each site (i _n , j _n ) is open. Rather surprisingly, this conjecture is still open: in fact, it is not known whether the conjecture holds for any value of k. In this note, we shall prove the weaker result that the corresponding assertion holds in the unoriented case: if k≤ 4 then the probability that there is an infinite path that starts at the origin and consists only of open sites is positive. Furthermore, we shall show that our method can be applied to a wide variety of distributions of (x _i ) and (y _j ). Independently, Peter Winkler [14] has recently proved a variety of similar assertions by different methods. Received: 4 March 1999 / Revised version: 27 September 1999 / Published online: 21 June 2000     

On some characterization of probability distributions in Hilbert spaces

Summary The aim of this paper is to prove the following theorem about characterization of probability distributions in Hilbert spaces:Theorem. — Let x₁, x₂, …, x_n be n (n≥3) independent random variables in the Hilbert spaceH, having their characteristic functionals f_k(t) = E[e^i(t,x _k)], (k=1, 2, …, n): let y₁=x₁ + x_n, y₂=x₂ + x_n, …, y_n−1=x_n−1 + x_n. If the characteristic functional f(t₁, t₂, …, t_n−1) of the random variables (y₁, y₂, …, y_n−1) does not vanish, then the joint distribution of (y₁, y₂, …, y_n−1) determines all the distributions of x₁, x₂, …, x_n up to change of location.     

The primes contain arbitrarily long polynomial progressions

We establish the existence of infinitely many polynomial progressions in the primes; more precisely, given any integer-valued polynomials P ₁, …, P _k  ∈ Z[m] in one unknown m with P ₁(0) = … = P _k (0) = 0, and given any ε > 0, we show that there are infinitely many integers x and m, with 1 \leqslant m \leqslant x^e1 \leqslant m \leqslant x^\varepsilon, such that x + P ₁(m), …, x + P _k (m) are simultaneously prime. The arguments are based on those in [18], which treated the linear case P _j  = (j − 1)m and ε = 1; the main new features are a localization of the shift parameters (and the attendant Gowers norm objects) to both coarse and fine scales, the use of PET induction to linearize the polynomial averaging, and some elementary estimates for the number of points over finite fields in certain algebraic varieties.     

Construction of multivariate compactly supported orthonormal wavelets

We propose a constructive method to find compactly supported orthonormal wavelets for any given compactly supported scaling function φ in the multivariate setting. For simplicity, we start with a standard dilation matrix 2I_2×2 in the bivariate setting and show how to construct compactly supported functions ψ₁,. . .,ψ_n with n>3 such that {2^kψ_j(2^kx−ℓ,2^ky−m), k,ℓ,m∈Z, j=1,. . .,n} is an orthonormal basis for L₂(ℝ²). Here, n is dependent on the size of the support of φ. With parallel processes in modern computer, it is possible to use these orthonormal wavelets for applications. Furthermore, the constructive method can be extended to construct compactly supported multi-wavelets for any given compactly supported orthonormal multi-scaling vector. Finally, we mention that the constructions can be generalized to the multivariate setting. Dedicated to Professor Charles A. Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 42C15, 42C30.     

A generalized mixed type of quartic–cubic–quadratic–additive functional equations

We determine the general solution of the functional equation f(x + ky) + f(x-ky) = g(x + y) + g(x-y) + h(x) + h(y) for fixed integers with k ≠ 0; ±1 without assuming any regularity conditions for the unknown functions f, g, h, and0020[(h)\tilde] \tilde{h} . The method used for solving these functional equations is elementary but it exploits an important result due to Hosszú. The solution of this functional equation can also be obtained in groups of certain type by using two important results due to Székelyhidi.     

Center conditions III: Parametric and model center problems

We consider an Abel equation (*)y’=p(x)y ² +q(x)y ³ withp(x), q(x) polynomials inx. A center condition for (*) (closely related to the classical center condition for polynomial vector fields on the plane) is thaty ₀=y(0)≡y(1) for any solutiony(x) of (*). Folowing [7], we consider a parametric version of this condition: an equation (**)y’=p(x)y ² +εq(x)y ³ p, q as above, ε ∈ ℂ, is said to have a parametric center, if for any ɛ and for any solutiony(ɛ,x) of (**)y(ɛ, 0)≡y(ɛ, 1).. We give another proof of the fact, shown in [6], that the parametric center condition implies vanishing of all the momentsm _k (1), wherem _k (x)=∫ ₀ ^{x pk} (t)q(t)(dt),P(x)=∫ ₀ ^x p(t)dt. We investigate the structure of zeroes ofm _k (x) and generalize a “canonical representation” ofm _k (x) given in [7]. On this base we prove in some additional cases a composition conjecture, stated in [6, 7] for a parametric center problem. The research of the first and the third author was supported by the Israel Science Foundation, Grant No. 101/95-1 and by the Minerva Foundation.     

A bound for the representability of large numbers by ternary quadratic forms and nonhomogeneous waring equations

The solvability of the equation n = x ² + y ² + 6pz ² (p is a fixed large prime) is proved under some natural congruential conditions and the assumption nm ¹² > p ²¹. As an implication, the solvability of the equation n = x ² + y ² + u ³ + v ³ + z ⁴ + w ¹⁶ + t ^4k+1 for all sufficiently large n is established. Bibliography: 13 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 357, 2008, pp. 5–21.     

Asymptotics of random sums of negatively dependent random variables in the presence of dominatedly varying tails

Let X ₁ , X ₂ , . . . be a sequence of negatively dependent and identically distributed random variables, and let N be a counting random variable independent of X _i ’s. In this paper, we study the asymptotics for the tail probability of the random sum S_N = ?_{k = 1}^N X_k {S_N} = \sum\nolimits_{k = 1}^N {{X_k}} in the presence of heavy tails. We consider the following three cases: (i) P(N > x) = o(P(X ₁  > x)), and the distribution function (d.f.) of X ₁ is dominatedly varying; (ii) P(X ₁  > x) = o(P(N > x)), and the d.f. of N is dominatedly varying; (iii) the tails of X ₁ and N are asymptotically comparable and dominatedly varying.     

On the boundedness of one recurrent sequence in a banach space

We establish necessary and sufficient conditions under which a sequence x ₀ = y ₀ , x _n+1 = Ax _n  + y _n+1 , n ≥ 0, is bounded for each bounded sequence { y_n :n \geqslant 0 } ì { x ? è_{n = 1}^￥ D( Aⁿ ) |sup_{n \geqslant 0} || Aⁿ x || < ￥ }\left\{ {y_n :n \geqslant 0} \right\} \subset \left\{ {\left. {x \in \bigcup\nolimits_{n = 1}^\infty {D\left( {A^n } \right)} } \right|\sup _{n \geqslant 0} \left\| {A^n x} \right\| < \infty } \right\}, where A is a closed operator in a complex Banach space with domain of definition D(A) .     

Center conditions II: Parametric and model center problems

We consider an Abel equation (*)y’=p(x)y ² +q(x)y ³ withp(x), q(x) polynomials inx. A center condition for (*) (closely related to the classical center condition for polynomial vector fields on the plane) is thaty ₀=y(0)≡y(1) for any solutiony(x) of (*). We introduce a parametric version of this condition: an equation (**)y’=p(x)y ² +εq(x)y ³ p, q as above, ℂ, is said to have a parametric center, if for any ε and for any solutiony(ε,x) of (**),y(ε,0)≡y(ε,1). We show that the parametric center condition implies vanishing of all the momentsm _k (1), wherem _k (x)=∫ ₀ ^{x pk} (t)q(t)(dt),P(x)=∫ ₀ ^x p(t)dt. We investigate the structure of zeroes ofm _k (x) and on this base prove in some special cases a composition conjecture, stated in [10], for a parametric center problem. The research of the first and the third author was supported by the Israel Science Foundation, Grant No. 101/95-1 and by the Minerva Foundation.     

Piecewise Convex Maximization Problems: Piece Adding Technique

In this article, we provide a global search algorithm for maximizing a piecewise convex function F over a compact D. We propose to iteratively refine the function F at local solution y by a virtual cutting function p _y (⋅) and to solve max {min {F(x)−F(y),p _y (x)}∣x∈D} instead. We call this function either a patch, when it avoids returning back to the same local solutions, or a pseudo patch, when it possibly yields a better point. It is virtual in the sense that the role of cutting constraints is played by additional convex pieces in the objective function. We report some computational results, that represent an improvement on previous linearization based techniques.     

Diagnostic tests for local coalescences of variables in Boolean functions

The article studies diagnostic tests for local k -fold coalescences of variables in Boolean functions f( [(x)\tilde]ⁿ )( 1 ￡ k ￡ n,  1 ￡ t ￡ 2^2k ) f\left( {{{\tilde{x}}^n}} \right)\left( {1 \leq k \leq n,\;1 \leq t \leq {2^{{2^k}}}} \right) . Upper and lower bounds are proved for the Shannon function of the length of the diagnostic test for local k -fold coalescences generated by the system of functions F_t^k \Phi_t^k . The Shannon function of the length of a complete diagnostic test for local k -fold coalescences behaves asymptotically as 2 ^k (n − k + 1) for n → ∞, k → ∞.