Constrained Minkowski Sums: A Geometric Framework for Solving Interval Problems in Computational Biology Efficiently

In this paper, we introduce the notion of a constrained Minkowski sum: for two (finite) point-sets P,Q⊆ℝ² and a set of k inequalities Ax≥b, it is defined as the point-set (P ⊕ Q) _Ax≥b ={x=p+q∣p∈P,q∈Q,Ax≥b}. We show that typical interval problems from computational biology can be solved by computing a set containing the vertices of the convex hull of an appropriately constrained Minkowski sum. We provide an algorithm for computing such a set with running time O(Nlog N), where N=|P|+|Q| if k is fixed. For the special case where P and Q consist of points with integer x ₁-coordinates whose absolute values are bounded by O(N), we even achieve a linear running time O(N). We thereby obtain a linear running time for many interval problems from the literature and improve upon the best known running times for some of them. The main advantage of the presented approach is that it provides a general framework within which a broad variety of interval problems can be modeled and solved. T. Bernholt gratefully acknowledges the Deutsche Forschungsgemeinschaft for the financial support (SFB 475, “Reduction of complexity in multivariate data structures”).     

Kernels of Toeplitz operators,smooth functions,and Bernstein type inequalities

Let ϕ be a unimodular function on the unit circle and let K_p(ϕ) denote the kernel of the Toeplitz operator T_ϕ in the Hardy space H^p, p≥1; . Suppose K_p(ϕ)≠{0}. The problem is to find out how the smoothness of the symbol ϕ influences the boundary smoothness of functions in K_p(ϕ). One of the main results is as follows. Theorem 1 Let 1<p, q<+∞, 1<r≤+∞, q⁻¹=p⁻¹+r⁻¹. Suppose |ϕ|≡1 on and ϕ∈W _r ¹ (i.e., ). Then K_p(ϕ)⊂W _q ¹ . Moreover, for any f∈K_p(ϕ) we have ‖f′‖_q≤c(p, r)‖ϕ′‖_r ‖f‖. Bibliography: 19 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 201, 1992, pp. 5–21. Translated by K. M. D'yakonov.     

Averaging distances in real quasihypermetric Banach spaces of finite dimension

The average distance theorem of Gross implies that for each realN-dimensional Banach space (N≥2) there is a unique positive real numberr(E) with the following property: For each positive integern and for all (not necessarily distinct)x ₁,x ₂, …,x _n inE with ‖x ₁‖=‖x ₂‖=…=‖x _n‖=1, there exists anx inE with ‖x‖=1 such that The main result of this paper shows, thatr(E)≤2−1/N for each realN-dimensional Banach spaceE (N≥2) with the so-called quasihypermetric property (which is equivalent toE isL ¹-embeddable). Moreover, equality holds if and only ifE is isometrically isomorphic to ℝ ^N equipped with the usual 1-norm.     

Sopra una curva gobba luogo di certi punti parabolici di una rete di superficie,generale, dell’ordinen

Abstract   we prove that the operator maps into itself for where and k(x,y)=ϕ(x,y) e^ig(x,y), ϕ(x,y) satisfies (5), (e.g. ϕ(x,y)=|x–y|^iτ,τ real) and the phase g(x,y)=x^a⋅ y^b +Φ_**(x^a,y^b). We obtain L^p estimates for operators with more general phases than in [5] and for these operators we require that b₁ b₂>1, and and a_l≥ b_l≥ 1, which remained open from [4]. Keywords Oscillatory integrals, L^p mappings Mathematics Subject Classification (2000) Primary 42B20, Secondary 46B70, 47G10     

Sharp estimates for maximal operators associated to the wave equation

The wave equation, ∂ _tt u=Δu, in ℝ ⁿ⁺¹, considered with initial data u(x,0)=f∈H ^s (ℝ ⁿ ) and u’(x,0)=0, has a solution which we denote by . We give almost sharp conditions under which and are bounded from H ^s (ℝ ⁿ ) to L ^q (ℝ ⁿ ).     

Large sample theory for distributions on the hypersphere with rotational symmetries

Summary A distribution on the unit sphere inℝ ^q with a densityf(‖x _v ‖) is considered where is ans(<q) dimensional subspace andx _v is the part ofx in . For a large sample the estimation of , a test that and a test for rotational symmetry within is given. For several samples with possibly different subspaces but the samef, a test that is given. For all tests power functions for contiguous alternatives are given. For the special density proportional to expk‖x _v ‖ ², additional results are given. Research supported in part by a Contract with the Office of Naval Research N00014-81-K-0146 awarded to Princeton University, Princeton, New Jersey 08544.     

On the Dimension of Coinvariants of Permutation Representations

Let be a univariate, separable polynomial of degree n with roots x ₁,…,x _n in some algebraic closure of the ground field . It is a classical problem of Galois theory to find all the relations between the roots. It is known that the ideal of all such relations is generated by polynomials arising from G-invariant polynomials, where G is the Galois group of f(Z). Namely: The action of G on the ordered set of roots induces an action on by permutation of the coordinates and each defines a relation P − P(x ₁,…,x _n ) called a G-invariant relation. These generate the ideal of all relations. In this note we show that the ideal of relations admits an H-basis of G-invariant relations if and only if the algebra of coinvariants has dimension ‖G‖ over . To complete the picture we then show that the coinvariant algebra of a transitive permutation representation of a finite group G has dimension ‖G‖ if and only if G = Σ _n acting via the tautological permutation representation.     

Codimension-<Emphasis Type="Italic">p</Emphasis> Paley–Wiener theorems

We obtain the generalized codimension-p Cauchy–Kovalevsky extension of the exponential function in R ^m =R ^p ⊕R ^q , where p>1, , and prove the corresponding codimension-p Paley–Wiener theorems.     

Toeplitz operators related to strongly singular Calderón-Zygmund operators

In this paper, the boundedness of Toeplitz operator T _b(f) related to strongly singular Calderón-Zygmund operators and Lipschitz function b ε (ℝⁿ) is discussed from L ^p(ℝⁿ) to L ^q(ℝⁿ), , and from L ^p(ℝⁿ) to Triebel-Lizorkin space . We also obtain the boundedness of generalized Toeplitz operator Θ _α0 ^b from L ^p(ℝⁿ) to L ^q(ℝⁿ), . All the above results include the corresponding boundedness of commutators. Moreover, the boundedness of Toeplitz operator T _b(f) related to strongly singular Calderón-Zygmund operators and BMO function b is discussed on L ^p(ℝⁿ), 1 < p < ∞.     

Integral kašin splittings

Forx ∈ ℝ ⁿ andp≥1 put ‖x‖ _p :=(n ⁻¹Σ|x _i| ^p )^1/p . An orthogonal direct sum decomposition ℝ^2k =E⊕E ^⊥ where dimE=k and ‖x‖₂/‖x‖₁≤C is called here a (k, C)-splitting. By a theorem of Kašin there existsC>0 such that (k, C)-splittings exist for allk, and by the volume ratio method of Szarek one can takeC=32eπ. All proofs of existence of (k, C)-splittings heretofore given are nonconstructive. Here we investigate the representation of (k, C)-splittings by matrices with integral entries. For everyC>8e _1/2 π _−1/2 and positive integerk we specify a positive integerN(k, C) such that in the set ofk by 2k matrices with integral entries of absolute value not exceedingN(k, C) there exists a matrix with row span a summand in a (k, C)-splitting. We haveN(k, C)≤2^18k fork large enough depending onC. We explain in detail how to test a matrix for the property of representing a (k, C)-splitting. Taken together our results yield an explicit (if impractical) construction of (k, C)-splittings.     

N-widths of Ω r ′ in L p

Let Ω _ϕ ^r ={f:f ^(r-1) abs. cont. on [0,1], ‖q_r(D)f‖_p≤1, f^(2K+σ) (0)=f^(2K+σ)=0, (k)=0,...,l-1}. where , and I is an identical operator. Denote Kolmogorov, linear, Geelfand and Bernstein n-widths of Ω _ϕ ^r in L^p byd _n (Ω _ϕ ^r ;L ^p ),δ _n (Ω _ϕ ^r ;L ^p ),d ⁿ (Ω _p ^r ;L ^p ) andb _n (Ω _p ^r ;L ^p ), respectively. In this paper, we find a method to get an exact estimation of these n-widths. Related optimal subspaces and an optimal linear operator are given. For another subset , similar results are also derrived.     

Minimization of the Tikhonov functional in Banach spaces smooth and convex of power type by steepest descent in the dual

For Tikhonov functionals of the form Ψ(x)=‖Ax−y‖ _Y ^r +α‖x‖ _X ^q we investigate a steepest descent method in the dual of the Banach space X. We show convergence rates for the proposed method and present numerical tests.     

Onp-absolutely summing constants of banach spaces

Given 1≦p<∞ and a real Banach spaceX, we define thep-absolutely summing constantμ _p(X) as inf{Σ _i ^=1/m |x*(x _i)|^p p Σ _i ^=1/m ‖x _i‖^p p]¹ p}, where the supremum ranges over {x*∈X*; ‖x*‖≤1} and the infimum is taken over all sets {x ₁,x ₂, …,x _m} ⊂X such that Σ _i ^=1/m ‖x _i‖>0. It follows immediately from [2] thatμ _p(X)>0 if and only ifX is finite dimensional. In this paper we find the exact values ofμ _p(X) for various spaces, and obtain some asymptotic estimates ofμ _p(X) for general finite dimensional Banach spaces. This is a part of the author’s Ph.D. Thesis prepared at the Hebrew University of Jerusalem, under the supervision of Prof. A. Dvoretzky and Prof. J. Lindenstrauss.     

An identity for normal-like operators

Forλεσ(A) (A a bounded linear operator on a Hilbert space) withλ a boundary point of the numerical range, the ‘spectral theory’ forλ is ‘just as ifA were normal’. IfA isnormal-like (the smallest disk containingσ(A) has radiusr=inf _z ‖A − z‖), then also sup {‖Ax‖² − |〈x.Ax〉|²:‖x‖=1}=r ². This research was partially supported by Air Force Contract AF-AFOSR-62-414.     

Shape preserving widths of Sobolev-type classes ofs-monotone functions on a finite interval

LetI be a finite interval andr ∈ ℕ. Denote by △ ₊ ^s L _q the subset of all functionsy ∈L _q such that thes-difference △ _T ^s y(·) is nonnegative onI, ∀τ>0. Further, denote by △ ₊ ^s W _p ^r the class of functionsx onI with the seminorm ‖x ^(r) ‖L _p ≤1, such that △ _T ^s x≥0, τ > 0, τ>0. Fors=3,…,r+1, we obtain two-sided estimates of the shape preserving widths , whereM ⁿ is the set of all linear manifoldsM ⁿ inL _q , dimM ⁿ ≤n, such thatM ⁿ ⋂△ ₊ ^s L _q ≠ 0. Part of this work was done while the first author visited Tel Aviv University in 2001 and part of it while the second author was a member of the Industrial Mathematics Institute (IMI), University of South Carolina.     

On a problem of the Goldbach-waring type

LetE(X)=‖{N≤X;N≠p ₁ ² +p ₂ ³ +p ₃ ⁴ +p ₄ ⁵ for any primesp _i}‖. It is proved in this paper that there exists a positive constant δ>0 such that

On the ratio of the expected maximum of a martingale and theL p-norm of its last term

For eachp>1, the supremum,S, of the absolute value of a martingale terminating at a random variableX inL _p, satisfiesES≦(Γ(q))^1/q‖X‖_p (q=p(p-1)^-1).The maximum,M, of a mean-zero martingale which starts at zero and terminates atX, satisfiesES≦(Γ(q))^1/q‖X‖_p (q=p(p-1)^-1), whereσ _q is the unique solution of the equationt = ‖Z −t ‖ _q for an exponentially distributed random variableZ with mean 1.σ _p has other characterizations and satisfies lim _p‖ q ^{− 1} σ _q =c withc determined byce ^c+1 = 1. Equalities in (1) and (2) are attainable by appropriate martingales which can be realized as stopped segments of Brownian motion. A presumably new property of the exponential distribution is obtained en route to inequality (2).     

INJECTIVE MAPS ON PRIMITIVE SEQUENCES OVER Z/（p^e）

Let Z/(pe) be the integer residue ring modulo pe with p an odd prime and integer e ≥ 3. For a sequence (a) over Z/(pe), there is a unique p-adic decomposition (a) = (a)0 (a)1·p … (a)e-1 ·pe-1, where each (a)i can be regarded as a sequence over Z/(p), 0 ≤ i ≤ e - 1. Let f(x) be a primitive polynomial over Z/(pe) and G' (f(x), pe) the set of all primitive sequences generated by f(x) over Z/(pe). For μ(x) ∈ Z/(p)[x] with deg(μ(x)) ≥ 2 and gcd(1 deg(μ(x)),p- 1) = 1,set ψe-1 (x0, x1,…, xe-1) = xe-1·[ μ(xe-2) ηe-3 (x0, x1,…, xe-3)] ηe-2 (x0, x1,…, xe-2),which is a function of e variables over Z/(p). Then the compressing map ψe-1: G'(f(x),pe) → (Z/(p))∞,(a) (→)ψe-1((a)0, (a)1,… ,(a)e-1) is injective. That is, for (a), (b) ∈ G' (f(x), pe), (a) = (b) if and only if ψe - 1 ((a)0, (a)1,… , (a)e - 1) =ψe - 1 ((b)0,(b)1,… ,(b)e-1). As for the case of e = 2, similar result is also given. Furthermore, if functions ψe-1 and ψe-1 over Z/(p) are both of the above form and satisfy ψe-1((a)0,(a)1,… ,(a)e-1) = ψe-1((b)0,(b)1,… ,(b)e-1) for (a),(b) ∈ G'(f(x),pe), the relations between (a) and (b), ψe-1 and ψe-1 are discussed.     

Convergence of solutions of stochastic differential equations to the Arratia flow

We consider the solution x _ε of the equation