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.     

Best Approximation in an Asymmetrically Weighted L1 Measure

Let f(x) be a given, real-valued, continuous function definedon an interval [a,b]of the real line. Given a set of m real-valued,continuous functions _j(x) defined on [a,b], a linear approximatingfunction can be formed with any real setA = {a₁, a₂,..., a_m}. We present results for determining A sothat F(A, x) is a best approximation to(x) when the measureof goodness of approximation is a weighted sum of |F(A, x)–f(x)|,the weights being positive constants, w, when F(A, x) f(x)and w2 otherwise (when w, = w2 = 1, the measure is the L₁, norm).The results are derived from a linear programming formulationof the problem. In particular, we give a theorem which shows when such bestapproximations interpolate the function at fixed ordinates whichare independent of f(x). We show how the fixed points can becalculated and we present numerical results to indicate thatthe theorem is quite robust.     

Un Theoreme De Littlewood Pour Les Nombres Premiers De Beurling

En 1914, Littlewood a montré, contre l'opinion couranteà l'époque, qu'il existe des valeurs de x pourlesquelles le nombre de nombres premiers inférieurs àx, (x), dépasse le logarithme intégral de x, lix. Plus précisément, il a établi que, pourun K > 0 convenable, il existe une infinité de valeursde x pour lesquelles etaussi [1] une infinité de valeurs de x pour lesquelles En 1937, Beurling a instauréune nouvelle manière de considérer les problèmessur les nombres premiers, en introduisant les ‘nombrespremiers généralisés’ [2]. L'idéeest de partir d'une fonction croissante P(x) (x 0), nulle sur[0, 1], qui joue le rôle de (x). On lui associe la fonctiondzeta et la fonction croissante N(x) (qui joue le rôlede la partie entière de x) selon la formule l'hypothèse est toujours queles intégrales ci-dessus existent lorque > 1 (s = + it). Le but de Beurling est, partant de propriétésconvenables de la fonction N(x), d'obtenir pour P(x) le ‘théorèmedes nombres premiers’, P(x) li x (x ). Nous allons,au contraire, partir d'une hypothèse simple sur P(x)(par exemple, P(x) < li x) et en tirer des conséquencespour la fonction (x), en laissant de côté la fonctionN(x). Bien entendu, nous verrons en passant que l'hypothèseP(x) < li x est incompatible avec le fait que (s) soit lafonction dzeta de Riemann. Il sera commode d'associer à la fonction (s) la fonction elle aussi définiepour > 1. Ainsi Nousnous servirons seulement des deux faits suivants. 1991 MathematicsSubject Classification 11M41, 11N80.     

Essentially infinite colourings of hypergraphs

We consider edge colourings of the complete r-uniform hypergraphK_n^(r)on n vertices. How many colours may such a colouring haveif we restrict the number of colours locally? The local restrictionis formulated as follows: for a fixed hypergraph H and an integerk we call a colouring (H, k)-local if every copy of H in thecomplete hypergraph K_n^(r) receives at most k different colours. We investigate the threshold for k that guarantees that every(H, k)-local colouring of K_n^(r) must have a globally boundednumber of colours as n , and we establish this threshold exactly.The following phenomenon is also observed: for many H (at leastin the case of graphs), if k is a little over this threshold,the unbounded (H, k)-local colourings exhibit their colourfulnessin a ‘sparse way’; more precisely, a bounded numberof colours are dominant while all other colours are rare. Hencewe study the threshold k₀ for k that guarantees that every (H,k)-local colouring n of K_n^(r) with k k₀ must have a globallybounded number of colours after the deletion of up to n^r edgesfor any fixed > 0 (the bound on the number of colours isallowed to depend on H and only); we think of such colouringsn as ‘essentially finite’. As it turns out, everyessentially infinite colouring is closely related to a non-monochromaticcanonical Ramsey colouring of Erdös and Rado. This secondthreshold is determined up to an additive error of 1 for everyhypergraph H. Our results extend earlier work for graphs byClapsadle and Schelp [‘Local edge colorings that are global’,J. Graph Theory 18 (1994) 389–399] and by the first twoauthors and Schelp [‘Essentially infinite colourings ofgraphs’, J. London Math. Soc. (2) 61 (2000) 658–670].We also consider a related question for colourings of the integersand arithmetic progressions.

---

2000 Mathematics Subject Classification 05D10 (primary), 05C35(secondary). The first author was partially supported by NSF grants CCR 0225610and DMS 0505550. The second author was partially supported byFAPESP and CNPq through a Temático–ProNEx project(Proc. FAPESP 2003/09925–5) and by CNPq (Proc. 306334/2004–6and 479882/2004–5). The third author was partially supportedby NSF grant DMS 0300529. The fourth author was partly supportedby the DFG within the European graduate program ‘Combinatorics,Geometry, and Computation’ (No. GRK 588/2) and by DFGgrant SCHA 1263/1–1. This work was supported in part bya CAPES/DAAD collaboration grant.     

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.     

On regularity of a quasiconformal mapping at a point of maximal stretching

Local behaviour of a K-quasiconformal mapping f at a point z₀of maximal stretching is studied. A sufficient condition forthe existence of the finite limit lim(f(z) – f(z₀))/(z– z₀)|z – z₀|^1/K–1 as z z₀, and a criterionfor z₀ to be a point of maximal stretching are given.     

Courbes De Genre 5 Munies D'une Involution Sans Point Fixe

We study genus 5 curves C with a fixed point free involution.We give a geometrical (embedded) characterisation of these curvesamong all genus 5 curves: the points of the Prym variety associatedto the involution give embeddings of the curve C in P₃ so thatC has infinitely many quadrisecant lines. Conversely, any genus5 curve having such an embedding is endowed with a fixed pointfree involution and the embedding is given by a point of thePrym variety.     

Congruences De Sommes De Chiffres De Valeurs Polynomiales

Let m, g, q N with q 2 and (m, q – 1) = 1. For n N,denote by s_n(n) the sum of digits of n in the q-ary digitalexpansion. Given a polynomial f with integer coefficients, degreed 1, and such that f(N) N, it is shown that there exists C= C(f, m, q) > 0 such that for any g Z, and all large N, In the special case m = q = 2 and f(n)= n², the value C = 1/20 is admissible. 2000 Mathematics SubjectClassification 11B85 (primary), 11N37, 11N69 (secondary).     

Stability in the Sense of Bounded Average Power

An R^m-valued sequence (x_k): = (x_k : k = 1, 2, ...), e.g. generatedrecursively by x_k = f_k (x_k–_k, U_k), is called ‘averagepth power bounded’ if (1/K) is bounded uniformly in K= 1, 2,.... (The case p = 2 may correspond to ‘power’in the physical sense.) This is a notion of stability. Givenestimates of the form: f_k (x, u) < a x + ¶ _k conditionsare obtained on the coefficient sequence (a_k) and the inputestimates e_k:=¶_k (u_k) which ensure this form of stabilityfor the output (x_k). In particular, a condition (utilized inan application to adaptive control) is obtained which imposes(i) a bound b on (a_k) and a ‘sparsity measure’ m(K) on #{kK: a_k>} as K ( >1) (ii) average pth power boundednesson (e_k), and (iii) a growth condition on (e_k) related to b andm (•). This condition is sharp.     

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.     

Complex Monodromy and Changing Real Pictures

The purpose of this note is to generalise, and give a more illuminatingproof, of a theorem of [13] (Theorem 1.1 below). Before statingit, we provide some introductory information. Consider the followingtwo sequences of pictures: in each we see a 1-parameter familyX_R,t of real algebraic hypersurfaces, which undergoes a bifurcationwhen the parameter t is equal to 0. Note that in Figure 1, both(i) (a) and (i) (b), and in (ii) (b), the surface X_R,t has apurely 1-dimensional part, which we have indicated with a dottedline, and that in (i) (b) we have drawn a curve vertically alongthe middle of the surface to make clearer the way it passesthrough itself. The reader will observe that in (a) the surfaceX_R,t is homotopically a 2-sphere when t>0 and a 0-spherewhen t<0, while in (b) X_R,t is a homotopy 1-sphere both fort<0 and t>0. Such sequences are typical in singularity theory; each is infact the family of algebraic closures of images of a versaldeformation of a codimension 1 singularity of mapping. Now suppose that the complexification X_C,t is a homotopy n-sphere.In [13] the second author pointed out that it follows that X_R,tis a homotopy sphere for t0 (allowing the empty set as a –1-sphere).Indeed, in the local situation, or globally in the weightedhomogeneous case, there are well-defined integers k₊ and k_–between –1 and n such that X_R,tS^k+ for t>0 and X_R,tS^k–for t<0. We describe X_R,t for tR–0 as ‘good’ if thehomotopy dimension of X_R,t is equal to n. In this case the inclusionX_R,tX_t is a homotopy equivalence [13, 1.1].     

A non-conforming finite element method with anisotropic mesh grading for the Stokes problem in domains with edges

The solution of the Stokes problem in three-dimensional domainswith edges has anisotropic singular behaviour which is treatednumerically by using anisotropic finite element meshes. Thevelocity is approximated by Crouzeix–Raviart (nonconformingP₁ ) elements and the pressure by piecewise constants. Thismethod is stable for general meshes (without minimal or maximalangle condition). Denoting by N_e the number of elements in themesh, the interpolation and consistency errors are of the optimalorder h N_e^–1/3 which is proved for tensor product meshes.As a by-product, we analyse also nonconforming prismatic elementswith P₁ [oplus ] span {x₃²} as the local space for the velocitywhere x₃ is the direction of the edge.     

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.     

De Paepe's Disc has Nontrivial Polynomial Hull

The topological disc (De Paepe's) isshown here to have non-trivial polynomially convex hull. Infact, the authors show that this holds for all discs of theform , where f is holomorphicon |z|r, and f(z=z²+a₃z³+..., with all coefficients a_n real,and at least one a_2n+1 0. 2000 Mathematics Subject Classification32E20.     

Shapiro's Cyclic Sum

Shapiro's cyclic sum is defined by , If K is the cone in Rⁿ of points withnon-negative coordinates, it is shown that the minimum of Ein K is a fixed point of T², where T is the non-linear operatordefined by (Tx)_i = x_n–i+1/(x_n–i+2 + x_n–i+3)²for i = 1,2,...,n. It is conjectured that Tx = S^kx, where Sis the shift operator in Rⁿ, and a proof is given under someadditional hypotheses. One of the consequences is a simple proofthat at the minimum point, a_i(x) = a_n–i+1–k(x) fori = 1,2,...,n.     

Quantum Markov Processes with a Christensen-Evans Generator in a Von Neumann Algebra

Let A be a unital von Neumann algebra of operators on a complexseparable Hilbert space H₀, and let {T_t, t 0} be a uniformlycontinuous quantum dynamical semigroup of completely positiveunital maps on A. The infinitesimal generator L of {T_t} is abounded linear operator on the Banach space A. For any Hilbertspace K, denote by B(K) the von Neumann algebra of all boundedoperators on K. Christensen and Evans [3] have shown that Lhas the form [formula] where is a representation of A in B(K) for some Hilbert spaceK, R: H₀ K is a bounded operator satisfying the ‘minimality’condition that the set {(RX–(X)R)u, uH₀, XA} is totalin K, and K₀ is a fixed element of A. The unitality of {T_t}implies that L(1) = 0, and consequently K₀=iH–R^*R, whereH is a hermitian element of A. Thus (1.1) can be expressed as [formula] We say that the quadruple (K, , R, H) constitutes the set ofChristensen–Evans (CE) parameters which determine theCE generator L of the semigroup {T_t}. It is quite possible thatanother set (K', ', R', H') of CE parameters may determine thesame generator L. In such a case, we say that these two setsof CE parameters are equivalent. In Section 2 we study thisequivalence relation in some detail. 1991 Mathematics SubjectClassification 81S25, 60J25.     

A fully discrete stabilized finite-element method for the time-dependent Navier-Stokes problem

A fully discrete stabilized finite-element method is presentedfor the two-dimensional time-dependent Navier–Stokes problem.The spatial discretization is based on a finite-element spacepair (X_h, M_h) for the approximation of the velocity and thepressure, constructed by using the Q₁ – P₀ quadrilateralelement or the P₁ – P₀ triangular element; the time discretizationis based on the Euler semi-implicit scheme. It is shown thatthe proposed fully discrete stabilized finite-element methodresults in the optimal order error bounds for the velocity andthe pressure.     

Reduced-order filtering with energy-to-peak performance for discrete-time Markovian jumping systems

In this paper, the l₂–l (energy-to-peak) performanceof the discrete-time Markovian jump linear system is investigated.The jump parameters are modelled by a discrete-time Markov process.Furthermore, we study the l₂–l reduced-order filteringproblem for the Markovian jump linear system. A reduced-orderfilter with the same randomly jumping parameters is proposedwhich can make the error systems with Markovian jump parametersstochastically stable with a prescribed l₂–lperformance.Sufficient conditions in terms of linear matrix inequalities(LMIs) and a coupling non-convex rank constraint are derivedfor the existence of a solution to the reduced-order filteringproblems. A numerical example is given to illustrate the designprocedures.     

Block-size determination in fractured porous media

A flow-reversal method involving the injection and retrievalof fluid from a fractured, porous medium at a different temperatureto that of the system in its undisturbed state is describedand assessed as a potential technique for measuring the thermaltransients of blocks of fractured porous media. Formulae areobtained for the zeroth- and first-order time moments of thethermal history of the fluid when it is well mixed in the injection-retrievalhole, injected at a temperature T₁ (different to the uniformtemperature T₀ of the undisturbed system) at a fixed rate Q,for a time t₁ and then withdrawn through the same drill holeat the same fixed rate Q. These formulae have a potential fordetermining some geometric parameters of the block structure,including the block surface-to-volume ratio and the mean actiontime for conductive heating.     

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).