On the Algorithmic Complexity of Minkowski's Reconstruction Theorem

In 1903 Minkowski showed that, given pairwise different unitvectors µ₁, ..., µ_m in Euclidean n-space Rⁿ whichspan Rⁿ, and positive reals µ₁, ..., µ_m such that^m_i=1µ_iµ_i = 0, there exists a polytope P in Rⁿ, uniqueup to translation, with outer unit facet normals µ₁, ...,µ_m and corresponding facet volumes µ₁, ..., µ_m.This paper deals with the computational complexity of the underlyingreconstruction problem, to determine a presentation of P asthe intersection of its facet halfspaces. After a natural reformulationthat reflects the fact that the binary Turing-machine modelof computation is employed, it is shown that this reconstructionproblem can be solved in polynomial time when the dimensionis fixed but is #P-hard when the dimension is part of the input. The problem of ‘Minkowski reconstruction’ has variousapplications in image processing, and the underlying data structureis relevant for other algorithmic questions in computationalconvexity.     

A WKB analysis of the buckling condition for a cylindrical shell of arbitrary thickness subjected to an external pressure

We consider the plane-strain buckling of a cylindrical shellof arbitrary thickness which is made of a Varga material andis subjected to an external hydrostatic pressure on its outersurface. The WKB method is used to solve the eigenvalue problemthat results from the linear bifurcation analysis. We show thatthe circular cross-section buckles into a non-circular shapeat a value of µ₁ which depends on A₁/A₂ and a mode number,where A₁ and A₂ are the undeformed inner and outer radii, andµ₁ is the ratio of the deformed inner radius to A₁. Inthe large mode number limit, we find that the dependence ofµ₁ on A₁/A₂ has a boundary layer structure: it is constantover almost the entire region of 0 < A₁/A₂ < 1 and decreasessharply from this constant value to unity as A₁/A₂ tends tounity. Our asymptotic results for A₁ – 1 = O(1) and A₁– 1 = O(1/n) are shown to agree with the numerical resultsobtained by using the compound matrix method.     

Small Deviations of Riemann-Liouville Processes In lq Spaces With Respect To Fractal Measures

We investigate Riemann–Liouville processes R_H, with H> 0, and fractional Brownian motions B_H, for 0 < H <1, and study their small deviation properties in the spacesL_q([0, 1], µ). Of special interest here are thin (fractal)measures µ, that is, those that are singular with respectto the Lebesgue measure. We describe the behavior of small deviationprobabilities by numerical quantities of µ, called mixedentropy numbers, characterizing size and regularity of the underlyingmeasure. For the particularly interesting case of self-similarmeasures, the asymptotic behavior of the mixed entropy is evaluatedexplicitly. We also provide two-sided estimates for this quantityin the case of random measures generated by subordinators. While the upper asymptotic bound for the small deviation probabilityis proved by purely probabilistic methods, the lower bound isverified by analytic tools concerning entropy and Kolmogorovnumbers of Riemann–Liouville operators. 2000 MathematicsSubject Classification 60G15 (primary), 47B06, 47G10, 28A80(secondary).     

Beardon's Diophantine Equations and Non-Free Mobius Groups

Let µ be a real number. The Möbius group G_µis the matrix group generated by It is known that G_µ is free if |µ| 2 (see [1])or if µ is transcendental (see [3, 8]). Moreover, thereis a set of irrational algebraic numbers µ which is densein (–2, 2) and for which G_µ is non-free [2, p. 528].We may assume that µ > 0, and in this paper we considerrational µ in (0, 2). The following problem is difficult. Let G^nf denote the set of all rational numbers µ in (0,2) for which G_µ is non-free. In 1969 Lyndon and Ullman[8] proved that G^nf contains the elements of the forms p/(p²+ 1) and 1/(p + 1), where p = 1, 2, ..., and that if µ₀ G^nf, then µ₀/p G^nf for p = 1, 2, .... In 1993 Beardon[2] studied problem (P) by means of the words of the form A^rB^s A^t and A^r B^s A^t B^u A^v, and he obtained a sufficient conditionfor solvability of (P), included implicitly in [2, pp. 530–531],by means of the following Diophantine equations: 1991 Mathematics SubjectClassification 20E05, 20H20, 11D09.     

Recurrence and asymptotics for orthonormal rational functions on an interval

^{Let µ be a positive bounded Borel measure on a subsetI of the real line and = {₁, ..., _n} a sequence of arbitrary ‘complex’poles outside I. Suppose {₁, ..., _n} is the sequence of rationalfunctions with poles in orthonormal on I with respect to µ. First, we are concernedwith reducing the number of different coefficients in the three-termrecurrence relation satisfied by these orthonormal rationalfunctions. Next, we consider the case in which I = [–1, 1] and µ satisfies the Erdos–Turán conditionµ' > 0 a.e. on I (where µ' is the Radon–Nikodymderivative of the measure µ with respect to the Lebesguemeasure) to discuss the convergence of _n+1(x)/_n(x) as n tendsto infinity and to derive asymptotic formulas for the recurrencecoefficients in the three-term recurrence relation. Finally,we give a strong convergence result for _n(x) under the morerestrictive condition that µ satisfies the Szeg condition(1 – x2)–1/2 log µ'(x) L1([– 1, 1]).}     

R-trees and laminations for free groups III: currents and dual R-tree metrics

We study the map which associates to a current its support (whichis a lamination). We show that this map is Out(F_N)-equivariant,not injective, not surjective and not continuous. However itis semi-continuous and almost surjective in a suitable sense.Given an -tree T (with dense orbits) in the boundary of outerspace and a current µ carried by the dual lamination ofT, we define a dual pseudo-distance d_µ on T. When thetree and the current come from a measured geodesic laminationon a surface with boundary, the dual distance is the originaldistance of the tree T. In general, such a good correspondencedoes not occur. We prove that when the tree T is the attractivefixed point of a non-geometric irreducible, with irreduciblepowers, outer automorphism, the dual lamination of T is uniquelyergodic and the dual distance d_µ is either zero or infinitethroughout T.     

POLYNOMIAL NUMERICAL INDEX FOR SOME COMPLEX VECTOR-VALUED FUNCTION SPACES

We study the relation between the polynomial numerical indicesof a complex vector-valued function space and the ones of itsrange space. It is proved that the spaces C(K, X) and L(µ,X) have the same polynomial numerical index as the complex Banachspace X for every compact Hausdorff space K and every -finitemeasure µ, which does not hold any more in the real case.We give an example of a complex Banach space X such that, forevery k 2, the polynomial numerical index of order k of X isthe greatest possible, namely 1, while the one of X** is theleast possible, namely k^k/(1–k). We also give new examplesof Banach spaces with the polynomial Daugavet property, namelyL(µ, X) when µ is atomless, and C_w(K, X), C_w*(K,X*) when K is perfect.     

Necessary and Sufficient Conditions for Exponential Stability and Ultimate Boundedness of Systems Governed by Stochastic Partial Differential Equations

Consider the following infinite dimensional stochastic evolutionequation over some Hilbert space H with norm |·|: It is proved that under certain mild assumptions, the strongsolution X_t(x₀)VHV*, t 0, is mean square exponentially stableif and only if there exists a Lyapunov functional (·,·):HxR₊R¹ which satisfies the following conditions: (i)c₁|x|²–k₁e^–µ₁t(x,t)c₂|x|²+k₂+k₂e^–µ₂t; (ii) L(x,t)–c₃(x,t)+k₃e^–µ₃t, xV, t0; where L is the infinitesimal generator of the Markov processX_t and c_i, k_i, µ_i, i = 1, 2, 3, are positive constants.As a by-product, the characterization of exponential ultimateboundedness of the strong solution is established as the nulldecay rates (that is, µ_i = 0) are considered.     

A Large Deviation Principle for Polynomial Hypergroups

Let S_n, n 1, be a random walk on a polynomial hypergroup (N₀,*), that is, a Markov chain on the nonnegative integers withstationary transition probabilities P_ij = _i* µ({j}), whereµ is a fixed probability measureon N₀. Under certain conditionson this measure, the principle of large deviations is shownfor the distributions of S_n/n. This result comprises the largedeviation principle for birth and death random walks associatedwith the polynomials generating the polynomial hypergroup.     

Uniqueness of solutions to weak parabolic equations for measures

We study uniqueness of solutions of parabolic equations formeasures µ(dt dx) = µ_t(dx)dt of the type L*µ = 0, satisfying µ_t as t 0, where each µ_tis a probability measure on ^d, L = _t + a^ij(t, x)_xixj + bⁱ(t,x)_xj is a differential operator on (0, T) x ^d and is a giveninitial measure. One main result is that uniqueness holds underuniform ellipticity and Lipschitz conditions on a^ij but forbⁱ merely local integrability and coercivity conditions aresufficient.     

A Numerical Method for the Solution of the Double Eigenvalue Problem

A generalization of the Rayleigh quotient iterative method,called the Minimum Residual Quotient Iteration (MRQI), is derivedfor the numerical solution of the 2-parameter eigenvalue problem;i.e. to find scalars µ and a corresponding vector x satisfyingthe following equations, Ax = B₁x + µB₂x, ||x|| = 1, f(x) = 0, where A and B are nxn real matrices, ||.|| denotes the l₂ normand f is a real functional. The method is applied to doubleeigenvalue problems for ordinary differential equations andcomputational results are presented.     

Complex Dynamics of Convergence Acceleration

Generalized Steffensen methods are nonderivative algorithmsfor the computation of fixed points of a function f. They replacethe functional iteration Z_m+1=f(Z_m) with Z_m+1=F_n(Z_m, where F_nis explicitly provided for every n 1 as a quotient of two Hankeldeterminants. In this paper we derive rules pertaining to thelocal behaviour of these methods. Specifically, and subjectto analyticity, given that is a bounded fixed point of f, thenit is also a fixed point of F_n. Moreover, unless f'() vanishesor is a root of unity, becomes a superattractive fixed pointof F_n of degree n; if f'() is a root of unity of minimal degreeq2, then is (as a fixed point of F_n) superattractive of degreemin {q-1, n}; if f'()=1, then is attractive for F_n; and, finally,if is superattractive of degree s (as a fixed point of f),then it becomes superattractive of degree (s + 1)^n–1(ns+ s + 1)–1. Attractivity rules change at infinity (providedthat f()=). Broadly speaking, infinity becomes less attractivefor F_n, Since one is interested in convergence to finite fixedpoints, this further enhances the appeal of generalized Steffensenmethods.     

The Expected order of a Random Permutation

Let µ_n be the expected order of a random permutation,that is, the arithmetic mean of the orders of the elements inthe symmetric group S_n. We prove that log µ_n ñc(n/logn) as n , where .     

Decomposition of weighted Triebel-Lizorkin and Besov spaces on the ball

Weighted Triebel–Lizorkin and Besov spaces on the unitball B^d in ^d with weights w_µ(x)=(1–|x|²)^µ–1/2,µ0, are introduced and explored. A decomposition schemeis developed in terms of almost exponentially localized polynomialelements (needlets) {}, {} and it is shown that the membershipof a distribution to the weighted Triebel–Lizorkin orBesov spaces can be determined by the size of the needlet coefficients{f, } in appropriate sequence spaces.     

Smoothness of the Lq-Spectrum of Self-Similar Measures with Overlaps

Let µ be the self-similar measure for a linear functionsystem S_jx=x+b_j (j=1,2,...,m) on the real line with the probabilityweight . Under the condition that satisfies the finite type condition, the L^q-spectrum (q) of µ is shown to bedifferentiable on (0,); as an application, µ is exactdimensional and satisfies the multifractal formalism.     

Irregularities of Point Distribution Relative to Convex Polygons III

Suppose that P is a distribution of N points in the unit squareU=[0, 1]². For every x=(x₁, x₂)U, let B(x)=[0, x₁]x[0, x₂] denotethe aligned rectangle containing all points y=(y₁, y₂)U satisfying0y₁x₁ and 0y₂x₂. Denote by Z[P; B(x)] the number of points ofP that lie in B(x), and consider the discrepancy function D[P; B(x)]=Z[P; B(x)]–Nµ(B(x)), where µ denotes the usual area measure.     

Existence of Solutions To Weak Parabolic Equations For Measures

Let A = (a^ij) be a Borel mapping on [0, 1] x R^d with valuesin the space of non-negative operators on R^d and let b = (bⁱ)be a Borel mapping on [0, 1] x R^d with values in R^d. Let Under broad assumptions on A and b, we construct a family µ= (µ_t)_t [0, 1] of probability measures µ_t on R^dwhich solvesthe Cauchy problem L* µ = 0 with initial conditionµ₀ = , where \nu is a probability measure on R^d, in thefollowing weak sense: and Such an equation is satisfied by transition probabilities ofa diffusion process associated with A and b provided such aprocess exists. However, we do not assume the existence of aprocess and allow quite singular coefficients, in particular,b may be locally unbounded or A may be degenerate. An infinite-dimensionalanalogue is discussed as well. Main methods are L^p-analysiswith respect to suitably chosen measures and reduction to theelliptic case (studied previously) by piecewise constant approximationsin time. 2000 Mathematics Subject Classification 35K10, 35K12,60J35, 60J60, 47D07.     

Simultaneous determination of the source terms in a linear hyperbolic problem from the final overdetermination: weak solution approach

The problem of determining the pair w:={F(x, t);f(t)} of sourceterms in the hyperbolic equation u_tt = (k(x)u_x)_x + F(x, t) andin the Neumann boundary condition k(0)u_x(0, t) = f(t) from themeasured data µ(x):=u(x, T) and/or (x):=u_t(x, t) at thefinal time t = T is formulated. It is proved that both componentsof the Fréchet gradient of the cost functionals J₁(w)= ||u(x, t;w) – µ(x)||₀² and J₂(w) = ||u_t(x, T;w)– (x)||₀² can be found via the solutions of correspondingadjoint hyperbolic problems. Lipschitz continuity of the gradientis derived. Unicity of the solution and ill-conditionednessof the inverse problem are analysed. The obtained results permitone to construct a monotone iteration process, as well as toprove the existence of a quasi-solution.     

OPTIMAL INTEGRABILITY CONDITION FOR THE LOG-SOBOLEV INEQUALITY

Let M denote a connected complete Riemannian manifold (possiblywith a convex boundary), the Riemannian distance function froma fixed point and V C² (M) such that dµ_V e^V d xis a probability measure. For any K 0, we prove that K/2 isthe infimum over all > 0 such that Ric_M – Hess_V –Kand imply the log-Sobolevinequality for the Dirichlet form µ_V(| f |²).     

Annular Functions and Gap Series

If f(z) = c_kz^nk, where n_k+1/n_k q > 1, and f(z) is analyticin |z| < 1, the f(z) is an annular function if and only ifsup |c_k| = . This answers a question posed by L. R. Sons andD.M. Campbell simplifies the proofs of many known examples ofannular functions. Present address: Dept. of Mathematical Sciences, McMaster University,Hamilton, Ontario, Canada L8S4K1