Determination of a Convex Body from Minkowski Sums of its Projections

For a convex body K in R^d and 1 K d – 1, let P_K (K)be the Minkowski sum (average) of all orthogonal projectionsof K onto k-dimensional subspaces of R^d. It is Known that theoperator P_k is injective if kd/2, k=3 for all d, and if k =2, d 14. It is shown that P_2k (K) determines a convex body K among allcentrally symmetric convex bodies and P_2k+1(K) determines aconvex body K among all bodies of constant width. Correspondingstability results are also given. Furthermore, it is shown thatany convex body K is determined by the two sets P_k (K) and P_k'(K) if 1 < k < k'. Concerning the range of P_k , 1 k d–2, it is shown that its closure (in the Hausdorff-metric)does not contain any polytopes other than singletons.     

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.     

Algebraic decay and variable speeds in wavefront solutions of a scalar reaction-diffusion equation

Wavefront solutions of scalar reaction-diffusion equations havebeen intensively studied for many years. There are two basiccases, typified by quadratic and cubic kinetics. An intermediatecase is considered in this paper, namely, u_l = u_xx + u²(1 –u). It is shown that there is a unique travelling-wave solution,with a speed 1/2, for which the decay to zero ahead of the waveis exponential with x. Moreover, numerical evidence is presentedwhich suggests that initial conditions with such exponentialdecay evolve to this travelling-wave solution, independentlyof the half-life of the initial decay. It is then shown thatfor all speeds greater than 1/2 there is also a travelling-wavesolution, but that these faster waves decay to zero algebraically,in proportion to 1/x. The numerical evidence suggests that initialconditions with such a decay rate evolve to one of these fasterwaves; the particular speed depends in a simple way on the detailsof the initial condition. Finally, initial conditions decayingalgebraically for a power law other than 1/x are considered.It is shown numerically that such initial conditions evolveeither to an algebraically decaying travelling wave, or in somecases to a wavefront whose shape and speed vary as a functionof time. This variation is monotonic and can be quite pronounced,and the speed is a function of u as well as of time. Using asimple linearization argument, an approximate formula is derivedfor the wave speed which compares extremely well with the numericalresults. Finally, the extension of the results to the more generalcase of u_l = u_xx + u^m(1 – u), with m > 1, is discussed.     

Mixed multiplicities for arbitrary ideals and generalized Buchsbaum-Rim multiplicities

We introduce first the notion of mixed multiplicities for arbitraryideals in a local d-dimensional Noetherian ring (A,m) which,in some sense, generalizes the concept of mixed multiplicitiesfor m-primary ideals. We also generalize Teissier's productformula for a set of arbitrary ideals and extend the notionof the Buchsbaum-Rim multiplicity (BR-multiplicity) of a submoduleof a free module to the case where the submodule no longer hasfinite colength. For a submodule M of A^p, we introduce a sequenceof multiplicities e^k_BR (M), k = 0, . . . , d + p – 1 whichin the case of an ideal (p = 1) coincides with the multiplicitysequence c0(I,A), . . . , c_d(I,A) defined for an arbitrary idealI of A by Achilles and Manaresi. In the case where M has finitecolength in Ap and is totally decomposable, we prove that ourBR-multiplicity sequence essentially falls into the standardBR-multiplicity of M.     

ON THE INTEGRAL GALOIS MODULE STRUCTURE OF CYCLIC EXTENSIONS OF p-ADIC FIELDS

We strengthen results of Miyata on the integral Galois modulestructure of totally ramified cyclic Kummer extensions K ofdegree pⁿ of a p-adic field k. Let c₁(K/k) be the first ramificationnumber of K/k, and let c(K/k) be the least non-negative residueof c₁(K/k) modulo pⁿ. Suppose that K is of the form k() with^pn k and val _K(–1)>0, (val _K(–1), p)= 1. Thenthe valuation ring of K is free over its associated order ifc(K/k) divides p^m–1 for some m with 1mn; the converseholds if n= 2; and is a Hopf order (or a Gorenstein order)if and only if c(K/k) = pⁿ–1.     

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.     

Mixed hp-DGFEM for incompressible flows II: Geometric edge meshes

We consider the Stokes problem of incompressible fluid flowin three-dimensional polyhedral domains discretized on hexahedralmeshes with hp-discontinuous Galerkin finite elements of typeQ_k for the velocity and Q_k–1 for the pressure. We provethat these elements are inf-sup stable on geometric edge meshesthat are refined anisotropically and non-quasiuniformly towardsedges and corners. The discrete inf-sup constant is shown tobe independent of the aspect ratio of the anisotropic elementsand is of O(k^–3/2) in the polynomial degree k, as in thecase of conforming Q_k–Q_k–2 approximations on thesame meshes.     

Asymptotics for the Heat Content of a Planar Region with a Fractal Polygonal Boundary

Let k 3 be an integer. For 0<s<1, let D_s R² be the setthat is constructed iteratively as follows. Take a regular openk-gon with sides of unit length, attach regular open k-gonswith sides of length s to the middles of the edges, and so on.At each stage of the iteration the k-gons that are added area factor s smaller than the previous generation and are attachedto the outer edges of the family grown so far. The set D_s isdefined to be the interior of the closure of the union of allthe k-gons. It is easy to see that there must exist some s_k> 0 such that no k-gons overlap if and only if 0 < s s_k. We derive an explicit formula for s_k. The set D_s is open, bounded, connected and has a fractal polygonalboundary. Let denote the heat content of D_s at time t when D_s initially has temperature 0and D_s is kept at temperature 1. We derive the complete short-timeexpansion of up to terms that are exponentially small in 1/t. It turns out that there arethree regimes, corresponding to 0<s<1/(k–1), s=1/(k–1),and 1/(k–1)<s s_k. For s 1/(k–1) the expansionhas the form where p_s is a log (1/s²)-periodic function, d_s=log (k–1)/log(1/s) is a similarity dimension, A_s and B are constants relatedto the edges and vertices, respectively, of D_s, and r_s is anerror exponent. For s=1/(k–1), the t^1/2-term carries anadditional log t. 1991 Mathematics Subject Classification: 11D25,11G05, 14G05.     

On the Local and Superlinear Convergence of Quasi-Newton Methods

This paper presents a local convergence analysis for severalwell-known quasi-Newton methods when used, without line searches,in an iteration of the form to solve for x^* such that Fx^* = 0. The basic idea behind theproofs is that under certain reasonable conditions on x_o, Fand x_o, the errors in the sequence of approximations {H_k} toF'(x^*)^–1 can be shown to be of bounded deterioration inthat these errors, while not ensured to decrease, can increaseonly in a controlled way. Despite the fact that H_k is not shownto approach F'(x^*)^–1, the methods considered, includingthose based on the single-rank Broyden and double-rank Davidon-Fletcher-Powellformulae, generate locally Q-superlinearly convergent sequences{x_k}.     

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.     

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.     

Some Remarks on p-Adic Analytic Groups

A theorem of Maranda [1, Section 30] states that if F is a finitegroup, p is a prime and p^e exactly divides |F|, then a Z_pF-latticeM is determined up to isomorphism by its finite quotient M/p^e+1M.If M is a free Z_p-module of rank d, this is equivalent to sayingthat representations of F in GL_d(Z_p) are determined up to equivalenceby their images modulo p^e+1. 1991 Mathematics Subject Classification20E18, 22E20.     

Long-Time Behavior of Solutions of the Fast Diffusion Equations with Critical Absorption Terms

This paper is devoted to the long-time behavior of solutionsto the Cauchy problem of the porous medium equation u_t = (u^m)– u^p in Rⁿ x (0,) with (1 – 2/n)₊ < m < 1and the critical exponent p = m + 2/n. For the strictly positiveinitial data u(x,0) = O(1 + |x|)^–k with n + mn(2 –n + nm)/(2[2 – m + mn(1 – m)]) k < 2/(1 –m), we prove that the solution of the above Cauchy problem convergesto a fundamental solution of u_t = (u^m) with an additional logarithmicanomalous decay exponent in time as t .     

Decentralized dynamic pole assignment with low-order compensators

N. Karcanias Control Engineering Centre, School of Engineering and Mathematical Sciences, City University, Northampton Square London EC1V OHB, UK Email: n.karcanias{at}city.ac.uk Received on June 14, 2006; Accepted on October 2, 2006 The problem of arbitrary pole placement via dynamic decentralizedoutput feedback is studied for minimal systems described bya proper transfer function matrix P(s) R^{m x p}(s) (m = m_i andp = p_i), with McMillan degree n. The family of controllersto be used includes those decentralized controllers with channelswhose ith channel has maximum observability index at most d_i.The method presented here is based on asymptotic linearizationaround a decentralized degenerate compensator of the pole placementmap related to the problem. It is shown that the method worksgenerically when m⁺p > n, where m⁺ = min{d_i(p_i + m_i –1) + m_i}, i = 1, ..., , and the smallest d_i of the compensatorof the ith channel is the integral part of (n – pm_i)/p(p_i+ m_i – 1).     

Arbitrary rank jumps for A-hypergeometric systems through Laurent polynomials

We investigate the solution space of hypergeometric systemsof differential equations in the sense of Gel’fand, Graev,Kapranov and Zelevinski. For any integer d 2, we constructa matrix A_(d) ^{d x 2d} and a parameter vector ß_(d)such that the holonomic rank of the A-hypergeometric systemH_A(d)(ß_(d)) exceeds the simplicial volume vol(A_(d))by at least d – 1. The largest previously known gap betweenrank and volume was 2. Our construction gives evidence to the general observation thatrank jumps seem to go hand in hand with the existence of multipleLaurent (or Puiseux) polynomial solutions.     

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.     

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.     

On time regularity and related conditions for power-bounded operators

Let T be a bounded linear operator in a complex Banach space.Our main result gives various characterizations of the condition:T is power-bounded and an estimate ||(I – T)Tⁿ || cn^–1/2 holds for all positive integers n. In particular, this conditionholds if and only if T = β S + (1 – β)I, forsome β (0, 1) and some power-bounded operator S; or ifand only if T is power-bounded and the discrete semigroup (Tⁿ)is dominated by the continuous semigroup (e^{– t(I –T)})_{t 0} in a natural sense. As a consequence of our main results,for 1/2 < 1 we characterize the condition that T is power-boundedand ||(I – T)Tⁿ || c n^– for all n, in terms ofestimates on the semigroup e^{–t(I – T)}.     

Animals, Trees and Renewal Sequences: Corrigendum

IN SECTION 3 of the above we omitted to mention aperiodicity.The period p of the pseudo renewal sequence {a_n: n > 0} isgiven by p = g.c.d. {n > 1: a_n > 0}. We are only concernedwith aperiodic renewal sequences (i.e. where p = 1). As it standsTheorem 3.1 is incorrect and should be restated as: THEOREM 3.1 If a = (a_n: n = 0,1,...) is an aperiodic pseudo-renewalsequence its limit a satisfies g_na^–n > 1 where a^–1 is to be interpreted as; if a = 0.     

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.