Isometric approximation property in euclidean spaces

We give a necessary and sufficient quantitative geometric condition for a compact setA⊂R ⁿ to have the following property with a givenc≥1: For everyɛ>0 and for every mapf: A→R ⁿ such that there is an isometryS: A→R ⁿ such that |Sx−fx|≤cɛ for allx∈A.     

Growth and Hölder conditions for the sample paths of Feller processes

Let (A,D(A)) be the infinitesimal generator of a Feller semigroup such that C _c ^∞(ℝ ⁿ )⊂D(A) and A|C _c ^∞(ℝ ⁿ ) is a pseudo-differential operator with symbol −p(x,ξ) satisfying |p(•,ξ)|_∞≤c(1+|ξ|²) and |Imp(x,ξ)|≤c ₀Rep(x,ξ). We show that the associated Feller process {X _t } _{t ≥0} on ℝ ⁿ is a semimartingale, even a homogeneous diffusion with jumps (in the sense of [21]), and characterize the limiting behaviour of its trajectories as t→0 and ∞. To this end, we introduce various indices, e.g., β_∞ ^x :={λ>0:lim _{|ξ|→∞ | x − y |≤2/|ξ|}|p(y,ξ)|/|ξ|^λ=0} or δ_∞ ^x :={λ>0:liminf _{|ξ|→∞ | x − y |≤2/|ξ| |ε|≤1}|p(y,|ξ|ε)|/|ξ|^λ=0}, and obtain a.s. (ℙ ^x ) that lim _{t →0} t ^−1/λ _{s ≤ t} |X _s −x|=0 or ∞ according to λ>β_∞ ^x or λ<δ_∞ ^x . Similar statements hold for the limit inferior and superior, and also for t→∞. Our results extend the constant-coefficient (i.e., Lévy) case considered by W. Pruitt [27]. Received: 21 July 1997 / Revised version: 26 January 1998     

Optimal properties of contraction semigroups in banach spaces

Suppose that(T _t )_t>0 is aC ₀ semi-group of contractions on a Banach spaceX, such that there exists a vectorx∈X, ‖x‖=1 verifyingJ ⁻¹(Jx)={x}, whereJ is the duality mapping fromX toP(X ^*). If |<T _t x,f>|→1, whent→+∞ for somef∈X ^*, ‖f‖≤1 thenx is an eigenvector of the generatorA, associated with a purcly imaginary eigenvalue. Because of Lin's example [L], the hypothesis onx∈X is the best possible. If the hypothesisJ ⁻¹(Jx)={x} is not verified, we can prove that ifJx is a singleton and ifJ ⁻¹(Jx) is weakly compact, then if |<T _t x, f>|→1, whent→+∞ for somef∈X ^*, ‖f‖≤1, there existsy∈J ⁻¹(Jx) such thaty is an eigenvector of the generatorA, associated with a purely imaginary eigenvalue. We give also a counter-example in the case whereX is one of the spaces ℓ₁ orL ₁.     

Lower bound on the profile of degree pairs in cross-intersecting set systems

We raise the following problem. For natural numbers m, n ≥ 2, determine pairs d′, d″ (both depending on m and n only) with the property that in every pair of set systems A, B with |A| ≤ m, |B| ≤ n, and A ∩ B ≠ 0 for all A ∈ A, B ∈ B, there exists an element contained in at least d′ |A| members of A and d″ |B| members of B. Generalizing a previous result of Kyureghyan, we prove that all the extremal pairs of (d′, d″) lie on or above the line (n − 1) x + (m − 1) y = 1. Constructions show that the pair (1 + ɛ / 2n − 2, 1 + ɛ / 2m − 2) is infeasible in general, for all m, n ≥ 2 and all ɛ > 0. Moreover, for m = 2, the pair (d′, d″) = (1 / n, 1 / 2) is feasible if and only if 2 ≤ n ≤ 4. The problem originates from Razborov and Vereshchagin’s work on decision tree complexity. Research supported in part by the Hungarian Research Fund under grant OTKA T-032969.     

How Close to Regular Must a Semicomplete Multipartite Digraph Be to Secure Hamiltonicity?

 Let D be a semicomplete multipartite digraph, with partite sets V ₁, V ₂,…, V _c, such that |V ₁|≤|V ₂|≤…≤|V _c|. Define f(D)=|V(D)|−3|V _c|+1 and . We define the irregularity i(D) of D to be max|d ⁺(x)−d ⁻(y)| over all vertices x and y of D (possibly x=y). We define the local irregularity i _l(D) of D to be max|d ⁺(x)−d ⁻(x)| over all vertices x of D and we define the global irregularity of D to be i _g(D)=max{d ⁺(x),d ⁻(x) : x∈V(D)}−min{d ⁺(y),d ⁻(y) : y∈V(D)}. In this paper we show that if i _g(D)≤g(D) or if i _l(D)≤min{f(D), g(D)} then D is Hamiltonian. We furthermore show how this implies a theorem which generalizes two results by Volkmann and solves a stated problem and a conjecture from [6]. Our result also gives support to the conjecture from [6] that all diregular c-partite tournaments (c≥4) are pancyclic, and it is used in [9], which proves this conjecture for all c≥5. Finally we show that our result in some sense is best possible, by giving an infinite class of non-Hamiltonian semicomplete multipartite digraphs, D, with i _g(D)=i(D)=i _l(D)=g(D)+?≤f(D)+1. Revised: September 17, 1998     

Superstability of the generalized orthogonality equation on restricted domains

Chmielinski has proved in the paper [4] the superstability of the generalized orthogonality equation |〈f(x), f(y)〉| = |〈x,y〉|. In this paper, we will extend the result of Chmielinski by proving a theorem: LetD _n be a suitable subset of ℝⁿ. If a function f:D _n → ℝⁿ satisfies the inequality ∥〈f(x), f(y)〉| |〈x,y〉∥ ≤ φ(x,y) for an appropriate control function φ(x, y) and for allx, y ∈ D _n, thenf satisfies the generalized orthogonality equation for anyx, y ∈ D _n.     

L p − Lq estimates for convolution operators with n-Dimensional singular measures

Let S ⊂ ℜⁿ⁺¹ be the graph of the function ϕ :[−1, 1] ⁿ → ℜ defined by ϕ (x ₁ , …, x_n) = ∑ _j=1 ⁿ |x_j|^αj, with1<α ₁ ≤ … ≤ α_n, let σ the Euclidean area measure on S. In this article we study the L^p − L^q boundedness of convolution operators with the singular Borel measure on Rⁿ⁺¹ given by μ (E)=σ (E ∩ S)     

Asymptotic behavior of solutions for a class of retarded difference equations

Consider the retarded difference equationx _n −x _n−1 =F(−f(x _n )+g(x _n−k )), wherek is a positive integer,F,f,g:R→R are continuous,F andf are increasing onR, anduF(u)>0 for allu≠0. We show that whenf(y)≥g(y) (resp. f(y)≤g(y)) fory∈R, every solution of (*) tends to either a constant or −∞ (resp. ∞) asn→∞. Furthermore, iff(y)≡g(y) fory∈R, then every solution of (*) tends to a constant asn→∞. Project supported by NNSF (19601016) of China and NSF (97-37-42) of Hunan     

On homomorphisms from the Hamming cube to Z

WriteF for the set of homomorphisms from {0, 1} ^d toZ which send0 to 0 (think of members ofF as labellings of {0, 1} ^d in which adjacent strings get labels differing by exactly 1), andF ₁ for those which take on exactlyi values. We give asymptotic formulae for |F| and |F|. In particular, we show that the probability that a uniformly chosen memberf ofF takes more than five values tends to 0 asd→∞. This settles a conjecture of J. Kahn. Previously, Kahn had shown that there is a constantb such thatf a.s. takes at mostb values. This in turn verified a conjecture of I. Benjaminiet al., that for eacht>0,f a.s. takes at mosttd values. Determining |F| is equivalent both to counting the number of rank functions on the Boolean lattice 2^[d] (functionsf: 2^[d]→N satisfyingf( ) andf(A)≤f(A∪x)≤f(A)+1 for allA∈2^[d] andx∈[d]) and to counting the number of proper 3-colourings of the discrete cube (i.e., the number of homomorphisms from {0, 1} ^d toK ₃, the complete graph on 3 vertices). Our proof uses the main lemma from Kahn’s proof of constant range, together with some combinatorial approximation techniques introduced by A. Sapozhenko. Research supported by a Graduate School Fellowship from Rutgers University.     

Zero sets of holomorphic functions in the unit ball with slow growth

We study the zero-varieties of holomorphic functions in the unit ball satisfying the growth condition log |f(z)|≤c _fλ(|z|), where λ:(0,1)→ℝ⁺ is a positive increasing function. We obtain some sufficient conditions on an analytic variety to be defined by such a function. Some results for the particular case λ(r)=log(e/(1−r)), corresponding to the classA ^−∞, generalize those of B. Korenblum in one variable. Both authors supported by DGICYT grant PB92-0804-C02-02.     

Strikte Konvexität für Variationsprobleme auf demn-dimensionalen Torus

We consider a variational problem with an integrandF:R ⁿ ×R×R ⁿ →R that isZ-periodic in the firstn+1 variables and satisfies certain growth-conditions. By a recent result of Moser, there exist for every α∈R ⁿ minimal solutionsu:R ⁿ →R minimising ƒF(x, u(x), u _x (x)) dx with respect to compactly supported variations ofu and such that sup |u(x)-αx|<∞. Given such a minimal solutionu we define the average action (whereB _r is ther-ball around 0∈R ⁿ ) and show thatM(α) is indeed independent of the minimal solutionu satisfying sup |u(x)-αx|<∞. We prove that this average actionM(α) is strictly convex in α.      

Algebraic methods in sum-product phenomena

We classify the polynomials f(x, y) ∈ ℝ[x, y] such that, given any finite set A ⊂ ℝ, if |A + A| is small, then |f(A,A)| is large. In particular, the following bound holds: |A + A‖f(A,A)| ≳ |A|^5/2. The Bezout theorem and a theorem by Y. Stein play an important role in our proof.     

Generating primitive positive clones

Suppose is a set of operations on a finite set A. Define PPC() to be the smallest primitive positive clone on A containing . For any finite algebra A, let PPC#(A) be the smallest number n for which PPC(CloA) = PPC(Clo _n A). S. Burris and R. Willard [2] conjectured that PPC#(A) ≤|A| when CloA is a primitive positive clone and |A| > 2. In this paper, we look at how large PPC#(A) can be when special conditions are placed on the finite algebra A. We show that PPC#(A) ≤|A| holds when the variety generated by A is congruence distributive, Abelian, or decidable. We also show that PPC#(A) ≤|A| + 2 if A generates a congruence permutable variety and every subalgebra of A is the product of a congruence neutral algebra and an Abelian algebra. Furthermore, we give an example in which PPC#(A) ≥|A| - 1)² so that these results are not vacuous. Received August 30, 1999; accepted in final form April 4, 2000.     

Negative result in pointwise 3-convex polynomial approximation

Let Δ³ be the set of functions three times continuously differentiable on [−1, 1] and such that f″′(x) ≥ 0, x ∈ [−1, 1]. We prove that, for any n ∈ ℕ and r ≥ 5, there exists a function f ∈ C ^r [−1, 1] ⋂ Δ³ [−1, 1] such that ∥f ^(r)∥ _{C[−1, 1]} ≤ 1 and, for an arbitrary algebraic polynomial P ∈ Δ³ [−1, 1], there exists x such that

Asymptotic behavior of the solution to the two-dimensional stationary problem of flow past a body far from it

In the exterior domain Ω⊂ℝ² we consider the two-dimensional Navier-stokes system Δu-▽p=(u,▽)u, div u=0 whose solution possesses a finite Dirichlet integral and satisfies the condition lim_|x|→∞ u(x)=(1, 0). For this solution, we establish the estimate |u(x)−(1, 0)|≤c|x| ^−α, where α>1/4. This estimate implies an asymptotic expression for the solution indicating the presence of a track behind the body. Translated fromMatematicheskie Zametki, Vol. 65, No. 2, pp. 246–253, February, 1999.     

A large-deviation result for the range of random walk and for the Wiener sausage

Let {S _n } be a random walk on ℤ ^d and let R _n be the number of different points among 0, S ₁,…, S _{n −1}. We prove here that if d≥ 2, then ψ(x) := lim _{n →∞}(−:1/n) logP{R _n ≥nx} exists for x≥ 0 and establish some convexity and monotonicity properties of ψ(x). The one-dimensional case will be treated in a separate paper. We also prove a similar result for the Wiener sausage (with drift). Let B(t) be a d-dimensional Brownian motion with constant drift, and for a bounded set A⊂ℝ ^d let Λ _t = Λ _t (A) be the d-dimensional Lebesgue measure of the `sausage' ∪_{0≤ s ≤ t} (B(s) + A). Then φ(x) := lim _t→∞: (−1/t) log P{Λ _t ≥tx exists for x≥ 0 and has similar properties as ψ. Received: 20 April 2000 / Revised version: 1 September 2000 / Published online: 26 April 2001     

Near-interpolation

Summary.  A parametric curve fL ₂ ^(m) ([a,b]ℝ ^d ) is a ``near-interpolant' to prescribed data z <sub>ij</sub> ℝ <sup>d</sup> at data sites t <sub>i</sub> [a,b] within tolerances 0<ɛ <sub>ij</sub> ≤∞ if |f <sup>(j−1)</sup> (t <sub>i</sub> )−z <sub>ij</sub> |≤ɛ <sub>ij</sub> for i=1:n and j=1:m, and a ``best near-interpolant' if it also minimizes ∫ _a ^b |f ^(m) |². In this paper optimality conditions are derived for these best near-interpolants. Based on these conditions it is shown that the near-interpolants are actually smoothing splines with weights that appear as Lagrange multipliers corresponding to the constraints. The optimality conditions are applied to the computation of near-interpolants in the last sections of the paper. Received September 4, 2001 / Revised version received July 22, 2002 / Published online October 29, 2002 Mathematics Subject Classification (1991): 41A05, 41A15, 41A29     

Diophantine approximation generalized

In this paper we study the set of x ∈ [0, 1] for which the inequality |x − x _n | < z _n holds for infinitely many n = 1, 2, .... Here x _n ∈ [0, 1) and z _n s> 0, z _n → 0, are sequences. In the first part of the paper we summarize known results. In the second part, using the theory of distribution functions of sequences, we find the asymptotic density of n for which |x − x _n | < z _n , where x is a discontinuity point of some distribution function of x _n . Generally, we also prove, for an arbitrary sequence x _n , that there exists z _n such that the density of n = 1, 2, ..., x _n → x, is the same as the density of n = 1, 2, ..., |x − x _n | < z _n , for x ∈ [0, 1]. Finally we prove, using the longest gap d _n in the finite sequence x ₁, x ₂, ..., x _n , that if d _n ≤ z _n for all n, z _n → 0, and z _n is non-increasing, then |x − x _n | < z _n holds for infinitely many n and for almost all x ∈ [0, 1].     

Pointwise characterization of Sobolev classes

We prove that a function f is in the Sobolev class W _loc ^m,p (ℝ ⁿ ) or W ^m,p (Q) for some cube Q ⊂ ℝ ⁿ if and only if the formal (m − 1)-Taylor remainder R ^m−1 f(x,y) of f satisfies the pointwise inequality |R ^m−1 f(x,y)| ≤ |x − y| ^m [a(x) + a(y)] for some a ε L ^p (Q) outside a set N ⊂ Q of null Lebesgue measure. This is analogous to H. Whitney’s Taylor remainder condition characterizing the traces of smooth functions on closed subsets of ℝ ⁿ . Dedicated to S.M. Nikol’skiĭ on the occasion of his 100th birthday The main results and ideas of this paper were presented in the plenary lecture of the author at the International Conference and Workshop Function Spaces, Approximation Theory and Nonlinear Analysis dedicated to the centennial of Sergei Mikhailovich Nikol’skii, Moscow, May 24–28, 2005.     

On Maps Preserving Zero Jordan Products

Let R be a ring, A = M _n (R) and θ: A → A a surjective additive map preserving zero Jordan products, i.e. if x,y ∈ A are such that xy + yx = 0, then θ(x)θ(y) + θ(y)θ(x) = 0. In this paper, we show that if R contains \frac12\frac{1}{2} and n ≥ 4, then θ = λϕ, where λ = θ(1) is a central element of A and ϕ: A → A is a Jordan homomorphism.