New perturbation analyses for the Cholesky factorization

We present new perturbation analyses for the Cholesky factorizationA = R^T R of a symmetric positive definite matrix A. The analysesmore accurately reflect the sensitivity of the problem thanprevious normwise results. The condition numbers here are alteredby any symmetric pivoting used in PAP^T = R^TR, and both numericalresults and an analysis show that the standard method of pivotingis optimal in that it usually leads to a condition number veryclose to its lower limit for any given A. It follows that thecomputed R will probably have greatest accuracy when we usethe standard symmetric pivoting strategy. Initially we give a thorogh analysis to obtain both first-orderand strict normwise perturbation bounds which are as tight aspossible, leading to a definition of an optimal condition numberfor the problem. Then we use this approach to obtain reasonablyclear first-order and strict componentwise perturbation bounds. We complete the work by giving a much simpler normwise analysiswhich provides a somewhat weaker bound, but which allows usto estimate the condition of the problem quite well with anefficient computation. This simpler analysis also shows whythe factorization is often less sensitive than we previouslythought, and adds further insight into why pivoting usuallygives such good results. We derive a useful upper bound on thecondition of the problem when we use pivoting. This research was supported by the Natural Sciences and EngineeringResearch Ciuncil of Canada Grant OGP0009236. This research was supported in part by the US National ScienceFoundation under grant CCR 95503126.     

On Aronson's Upper Bounds for Heat Kernels

Let L be a uniformly elliptic operator in divergence form onR^d, and let p(t,x,y) be the fundamental solution to the heatequation for L. A new proof is given of Aronson's upper bound: 2000 Mathematics Subject Classification35J15, 60J60.     

Polynomial systems supported on circuits and dessins d'enfants

We study polynomial systems in which equations have as commonsupport a set of n + 2 points in ⁿ called a circuit. We finda bound on the number of real solutions to such systems whichdepends on n, the dimension of the affine span of the minimalaffinely dependent subset of , and the rank modulo 2 of . Weprove that this bound is sharp by drawing the so-called dessinsd’enfants on the Riemann sphere. We also obtain that themaximal number of solutions with positive coordinates to systemssupported on circuits in ⁿ is n + 1, which is very small comparedto the bound given by the Khovanskii fewnomial theorem.     

An isoperimetric function for Bestvina-Brady groups

Given a right-angled Artin group A, the associated Bestvina–Bradygroup is defined to be the kernel of the homomorphism A thatmaps each generator in the standard presentation of A to a fixedgenerator of . We prove that the Dehn function of an arbitraryfinitely presented Bestvina–Brady group is bounded aboveby n⁴. This is the best possible universal upper bound.     

On the number of homotopy types of fibres of a definable map

In this paper we prove a single exponential upper bound on thenumber of possible homotopy types of the fibres of a Pfaffianmap in terms of the format of its graph. In particular, we showthat if a semi-algebraic set SR^m+n, where R is a real closedfield, is defined by a Boolean formula with s polynomials ofdegree less than d, and : R^m+nRⁿ is the projection on a subspace,then the number of different homotopy types of fibres of doesnot exceed s^2(m+1)n(2^m nd)^O(nm). As applications of our mainresults we prove single exponential bounds on the number ofhomotopy types of semi-algebraic sets defined by fewnomials,and by polynomials with bounded additive complexity. We alsoprove single exponential upper bounds on the radii of ballsguaranteeing local contractibility for semi-algebraic sets definedby polynomials with integer coefficients.     

ON THE LEAST n WITH {chi}(n) != 1

Suppose that a > 1. By using a method of Linnik employinghis Large Sieve one may derive the following result. The numberof primitive Dirichlet characters with conductor Q such that(n) = 1 for all n (log Q)^a is O(Q^2/a+). We improve the exponent2/a for a > 2 by using a refined version by Heath-Brown ofthe Halasz–Montgomery ‘Large Values method’.     

Heat Kernel Estimates and LP Spectral Independence of Elliptic Operators

Let be an open subset of R^d, and let T_p for p[1, ) be consistentC₀-semigroups given by kernels that satisfy an upper heat kernelestimate. Denoting their generators by A_p, we show that thespectrum (A_p) is independent of p[1, ). We also treat the caseof weighted L^p-spaces for weights that satisfy a subexponentialgrowth condition. An example shows that independence of thespectrum may fail for an exponential weight. 1991 MathematicsSubject Classification 47D06, 47A10, 35P05.     

A note on the design of hp-version interior penalty discontinuous Galerkin finite element methods for degenerate problems

^** Email: emmanuil.georgoulis{at}mcs.le.ac.uk^*** Email: al{at}maths.strath.ac.uk We consider a variant of the hp-version interior penalty discontinuousGalerkin finite element method (IP-DGFEM) for second-order problemsof degenerate type. We do not assume uniform ellipticity ofthe diffusion tensor. Moreover, diffusion tensors of arbitraryform are covered in the theory presented. A new, refined recipefor the choice of the discontinuity-penalization parameter (thatis present in the formulation of the IP-DGFEM) is given. Makinguse of the recently introduced augmented Sobolev space framework,we prove an hp-optimal error bound in the energy norm and anh-optimal and slightly p-suboptimal (by only half an order ofp) bound in the L² norm (the latter, for the symmetric versionof the IP-DGFEM), provided that the solution belongs to an augmentedSobolev space.     

Mixed Newton numbers and isolated complete intersection singularities

Let f:(ⁿ, 0) (^p, 0) be a complete intersection with an isolatedsingularity at the origin. We give a lower bound for the Milnornumber of f in terms of the mixed multiplicities of a set ofmonomial ideals attached to the Newton polyhedra of the componentfunctions of f. The Milnor number of f equals the bound thatwe give when f satisfies a condition that we define and thatextends the notion of Newton non-degenerate function studiedby Kouchnirenko. Our techniques are based on the notion of integralclosure of submodules and its relation with Buchsbaum–Rimmultiplicity and mixed multiplicities of a set of ideals.     

Bounds on the solution of the time-varying linear matrix differential equation P(t) = AH(t) P(t) + P(t) A(t) + Q(t)

^** Email: pagilla{at}ceat.okstate.edu We derive upper and lower bounds for the trace of the solutionof the time-varying linear matrix differential equation (t)= A^H(t) P(t) + P(t) A(t) + Q(t). A practical numerical exampleis given to verify the bounds. The bounds obtained are usefulsince the considered equation is encountered in a number ofapplications in systems and control theory.     

On the Discrepancy for Cartesian Products

Let B₂ denote the family of all circular discs in the plane.It is proved that the discrepancy for the family {B₁ x B₂ :B₁, B₂ B₂} in R⁴ is O(n^1/4+) for an arbitrarily small constant > 0, that is, it is essentially the same as that for thefamily B₂ itself. The result is established for the combinatorialdiscrepancy, and consequently it holds for the discrepancy withrespect to the Lebesgue measure as well. This answers a questionof Beck and Chen. More generally, we prove an upper bound forthe discrepancy for a family {^k_i=1A_i:A_iA_i, i = 1, 2, ..., k},where each A_i is a family in R^d_i, each of whose sets is describedby a bounded number of polynomial inequalities of bounded degree.The resulting discrepancy bound is determined by the ‘worst’of the families A_i, and it depends on the existence of certaindecompositions into constant-complexity cells for arrangementsof surfaces bounding the sets of A_i. The proof uses Beck's partialcoloring method and decomposition techniques developed for therange-searching problem in computational geometry.     

Some power of an element in a Garside group is conjugate to a periodically geodesic element

We show that for each element g of a Garside group, there existsa positive integer m such that g^m is conjugate to a periodicallygeodesic element h, an element with |hⁿ| = |n| · |h|for all integers n, where |g| denotes the shortest word lengthof g with respect to the set of simple elements. We also showthat there is a finite-time algorithm that computes, given anelement of a Garside group, its stable super summit set.     

Error estimates for stochastic differential games: the adverse stopping case

^** Email: frederic.bonnans{at}inria.fr^*** Email: stefania.maroso{at}inria.fr^**** Email: zidani{at}ensta.fr We obtain error bounds for monotone approximation schemes ofa particular Isaacs equation. This is an extension of the theoryfor estimating errors for the Hamilton–Jacobi–Bellmanequation. To obtain the upper error bound, we consider the ‘Krylovregularization’ of the Isaacs equation to build an approximatesub-solution of the scheme. To get the lower error bound, weextend the method of Barles & Jakobsen (2005, SIAM J. Numer.Anal.) which consists in introducing a switching system whosesolutions are local super-solutions of the Isaacs equation.     

On the Centred Hausdorff Measure

Let v be a measure on a separable metric space. For t, q R,the centred Hausdorff measures µ^h with the gauge functionh(x, r) = r^t(vB(x, r))^q is studied. The dimension defined bythese measures plays an important role in the study of multifractals.It is shown that if v is a doubling measure, then µ^h isequivalent to the usual spherical measure, and thus they definethe same dimension. Moreover, it is shown that this is trueeven without the doubling condition, if q 1 and t 0 or ifq 0. An example in R² is also given to show the surprisingfact that the above assertion is not necessarily true if 0 <q < 1. Another interesting question, which has been askedseveral times about the centred Hausdorff measure, is whetherit is Borel regular. A positive answer is given, using the aboveequivalence for all gauge functions mentioned above.     

Intertwining Maps from Certain Group Algebras

In [17, 18, 19], we began to investigate the continuity propertiesof homomorphisms from (non-abelian) group algebras. Alreadyin [19], we worked with general intertwining maps [3, 12]. Thesemaps not only provide a unified approach to both homomorphismsand derivations, but also have some significance in their ownright in connection with the cohomology comparison problem [4]. The present paper is a continuation of [17, 18, 19]; this timewe focus on groups which are connected or factorizable in thesense of [26]. In [26], G. A. Willis showed that if G is a connectedor factorizable, locally compact group, then every derivationfrom L¹(G) into a Banach L¹(G)-module is automatically continuous.For general intertwining maps from L¹(G), this conclusion isfalse: if G is connected and, for some nN, has an infinite numberof inequivalent, n-dimensional, irreducible unitary representations,then there is a discontinuous homomorphism from L¹(G into aBanach algebra by [18, Theorem 2.2] (provided that the continuumhypothesis is assumed). Hence, for an arbitrary intertwiningmap from L¹(G), the best we can reasonably hope for is a resultasserting the continuity of on a ‘large’, preferablydense subspace of L¹(G). Even if the target space of is a Banachmodule (which implies that the continuity ideal I() of is closed),it is not a priori evident that is automatically continuous:the proofs of the automatic continuity theorems in [26] relyon the fact that we can always confine ourselves to restrictionsto L¹(G) of derivations from M(G) [25, Lemmas 3.1 and 3.4].It is not clear if this strategy still works for an arbitraryintertwining map from L¹(G) into a Banach L¹(G)-module.     

A Paley-Wiener theorem for Bergman spaces with application to invariant subspaces

An analogue of the Paley–Wiener theorem is developed forweighted Bergman spaces of analytic functions in the upper half-plane.The result is applied to show that the invariant subspaces ofthe shift operator on the standard Bergman space of the unitdisk can be identified with those of a convolution Volterraoperator on the space L²(⁺, (1/t)dt).     

On Certain Exponential Sums and the Distribution of Diffie-Hellman Triples

Let g be a primitive root modulo a prime p. It is proved thatthe triples (g^x, g^y, g^xy), x, y = 1, ..., p–1, are uniformlydistributed modulo p in the sense of H. Weyl. This result isbased on the following upper bound for double exponential sums.Let >0 be fixed. Then uniformly for any integers a, b, c with gcd(a, b, c, p) = 1.Incomplete sums are estimated as well. The question is motivated by the assumption, often made in cryptography,that the triples (g^x, g^y, g^xy) cannot be distinguished fromtotally random triples in feasible computation time. The resultsimply that this is in any case true for a constant fractionof the most significant bits, and for a constant fraction ofthe least significant bits.     

Upwind difference approximations for degenerate parabolic convection-diffusion equations with a discontinuous coefficient

We analyse approximate solutions generated by an upwind differencescheme (of Engquist–Osher type) for nonlinear degenerateparabolic convection–diffusion equations where the nonlinearconvective flux function has a discontinuous coefficient (x)and the diffusion function A(u) is allowed to be strongly degenerate(the pure hyperbolic case is included in our setup). The mainproblem is obtaining a uniform bound on the total variationof the difference approximation u, which is a manifestationof resonance. To circumvent this analytical problem, we constructa singular mapping (, ·) such that the total variationof the transformed variable z = (, u) can be bounded uniformlyin . This establishes strong L¹ compactness of z and, since(, ·) is invertible, also u. Our singular mapping isnovel in that it incorporates a contribution from the diffusionfunction A(u). We then show that the limit of a converging sequenceof difference approximations is a weak solution as well as satisfyinga Krukov-type entropy inequality. We prove that the diffusionfunction A(u) is Hölder continuous, implying that the constructedweak solution u is continuous in those regions where the diffusionis nondegenerate. Finally, some numerical experiments are presentedand discussed.     

Repartition des points rationnels sur la cubique de Segre

We study the distribution of rational points on Segre's cubicdefined as the locus of points x ⁵ such that In particular, we verify Manin'sconjecture concerning the asymptotic behaviour of the numberof non-trivial rational points of height at most B.     

The largest prime factor of X3+2

The largest prime factor of X³+2 was investigated in 1978 byHooley, who gave a conditional proo that it is infinitely oftenat least as large as X¹+, with a certain positive constant .It is trivial to obtain such a result with =0. One may thinkof Hooley's result as an approximation to the conjecture thatX³+2 is infinitely often prime. The condition required by Hooley,his R^* conjecture, gives a non-trivial bound for short Ramanujan–Kloostermansums. The present paper gives an unconditional proof that thelargest prime factor of X³+2 is infinitely often at least aslarge as X¹⁺, though with a much smaller constant than thatobtained by Hooley. In order to do this we prove a non-trivialbound for short Ramanujan–Kloosterman sums with smoothmodulus. It is also necessary to modify the Chebychev method,as used by Hooley, so as to ensure that the sums that occurdo indeed have a sufficiently smooth modulus. 2000 MathematicsSubject Classification: 11N32.