Natural Tiling, Lattice Tiling and Lebesgue Measure of Integral Self-Affine Tiles

In the existing theory of self-affine tiles, one knows thatthe Lebesgue measure of any integral self-affine tile correspondingto a standard digit set must be a positive integer and everyintegral self-affine tile admits some lattice Zⁿ as a translationtiling set of Rⁿ. In this paper, we give algorithms to evaluatethe Lebesgue measure of any such integral self-affine tile Kand to determine all of the lattice tilings of Rⁿ by K. Moreover,we also propose and determine algorithmically another type oftranslation tiling of Rⁿ by K, which we call natural tiling.We also provide an algorithm to decide whether or not Lebesguemeasure of the set K (K+j), j–Zⁿ, is strictly positive.     

Differentiable Peak-Interpolation on Bounded Domains with Smooth Boundary

Let D be a bounded domain in Cⁿ with C² boundary, and, for 1 k , let A^k(D) be the algebra of functions holomorphic on Dand C^k on a neighbourhood of . It is shown that each peak-interpolation set for A^k(D) is afinite set.     

Boundary Accessibility of a Domain Quasiconformally Equivalent to a Ball

A boundary point of a domain D in Rⁿ is said to be broadly accessibleif it ‘almost lies’ on the boundary of a round ballcontained in D. If f is a quasiconformal mapping of the unitball Bⁿ onto D, then it is shown that broadly accessible boundarypoints on D correspond under f to a set of full measure on Bⁿ.2000 Mathematics Subject Classification 30C65.     

Classification of Integral Expanding Matrices and Self-Affine Tiles

   Abstract. Let T be a self-affine tile that is generated by an expanding integral matrix A and a digit set D . It is known that many properties of T are invariant under the Z -similarity of the matrix A . In [LW1] Lagarias and Wang showed that if A is a 2 × 2 expanding matrix with |det(A)| = 2 , then the Z -similar class is uniquely determined by the characteristic polynomial of A . This is not true if |det(A)| > 2. In this paper we give complete classifications of the Z -similar classes for the cases |det(A)| =3, 4, 5 . We then make use of the classification for |det(A)| =3 to consider the digit set D of the tile and show that μ(T) >0 if and only if D is a standard digit set. This reinforces the conjecture in [LW3] on this.     

Squared Givens Rotation

Given a matrix A, let U be the upper triangular matrix thatresults from the application of Gaussian elimination to A^TA.We develop a fast and square-root-free Givens rotation admittingthe direct calculation of U from A.     

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.     

A new methodology for the stability analysis of pairwise triangularizable and related switching systems

We consider the asymptotic stability of the time-varying dynamicsystem : = A(t)x, A(t) R^{n x n}, A(t) A= {A₁, ..., A_m}, where A_i is Hurwitz and where a set of non-singularmatrices T_{i j} exist such that any pair of matrices {T_{i j} A_iT_{i j}^–1, T_{i j} A_j T_{i j}^–1}, i, j {1, ..., m}, areupper triangular. Switching systems of this form are referredto as pairwise triangularizable switching systems. It can beestablished that (a) pairwise triangularizability is not sufficientto guarantee the existence of a common quadratic Lyapunov functionfor the linear time-invariant dynamic systems A_i : = A_i x; (b) additional conditions can be specified which guaranteeasymptotic stability of the switching system . In this paperwe also show that pairwise triangularizability is not even sufficientto guarantee asymptotic stability of the switching system .We also show that the method of proof of stability in (b), whichdoes not assume the existence of a common quadratic Lyapunovfunction, can be used to prove the asymptotic stability of moregeneral switching systems (systems that are not pairwise triangularizable).Finally, we show that our results can be used as the basis forthe design of practical control systems; namely, for the designof an automobile speed switched controller with guaranteed stabilityproperties.     

On Closed Sets with Convex Projections

A shadow of a subset A of Rⁿ is the image of A under a projectiononto a hyperplane. Let C be a closed nonconvex set in Rⁿ suchthat the closures of all its shadows are convex. If, moreover,there are n independent directions such that the closures ofthe shadows of C in those directions are proper subsets of therespective hyperplanes then it is shown that C contains a copyof R^n–2. Also for every closed convex set B ‘minimalimitations’ C of B are constructed, that is, closed subsetsC of B that have the same shadows as B and that are minimalwith respect to dimension.     

Plane with A{infty}-Weighted Metric not Bilipschitz Embeddable to Rn

A planar set G R² is constructed that is bilipschitz equivalentto (G,d^z), where (G, d) is not bilipschitz embeddable to anyuniformly convex Banach space. Here, Z (0, 1) and d^z denotesthe zth power of the metric d. This proves the existence ofa strong A weight in R², such that the corresponding deformedgeometry admits no bilipschitz mappings to any uniformly convexBanach space. Such a weight cannot be comparable to the Jacobianof a quasiconformal self-mapping of R². 2000 Mathematics SubjectClassification 54E40 (primary); 30C62, 30C65, 28A80 (secondary).     

Mixed block elimination for linear systems with wider borders

The paper is about the stable solution of possibly ill-conditionedbordered linear systems. Given stable solvers for matrix A andfor A^T, we prove that the Govaerts Mixed Block Elimination (BEM)method constitutes a stable solver for the matrix consistingof A or A^T with a border of width 1, and hence by recursionfor a border of any width. We express the algorithm in an efficient,iterative, form. We analyse its operation count, and verifythe theory by extensive numerical experiments. ^*Senior Research Associate of the Belgian National Fund of ScientificResearch NFWO.     

On the Volume Ratio of Two Convex Bodies

Let K and L be two convex bodies in Rⁿ. The volume ratio vr(K,L) of K and L is defined by vr(K, L = inf(|K|/|T(L)|)^1/n, wherethe infimum is over all affine transformations T of Rⁿ for whichT(L) K. It is shown in this paper that vr(K, L) , where c > 0 is an absolute constant. This isoptimal up to the logarithmic term. 2000 Mathematics SubjectClassification 52A40, 46B07 (primary); 52A21, 52A20 (secondary).     

On the Structure of the Moving Finite-element Equations

Address from 1st April 1985, School of Mathematics, Universityof Bristol, University Walk, Bristol BS8 1TW. The morning finite-element method for evolutionary partial differentialequations leads to a coupled non-linear system of ordinary differentialequations in time, with a coefficien matrix A, say, for thetime derivaties, We show for linear elements in any number ofdimensions, A can be written in the form M^TCM, where the matrixC depends solely on the mesh geometry and the matrix M on thegradient of the section, As a simple consequence we show thatA is singular only in the cases (i) element degeneracy () and (ii) collinearity of nodes (M not out of fullrank). We give constructions for the inversion of A in all cases. In one dimension, if A is non-singular, it has a simple explicitinverse. If A is singular we replace it by reduced matrix A^*.It can be shown that every case the spectral radius of the Jacobiiteration matrix ia ?and that A or A^* can be efficiently invertedby conjugate gradient methods. Finally, we discuss the applicability of these arguments tosystem of equations in any number of dimensions.     

Linear Independence of Hecke Operators in the Homology of X0(N)

In Merel's recent proof [7] of the uniform boundedness conjecturefor the torsion of elliptic curves over number fields, a keystep is to show that for sufficiently large primes N, the Heckeoperators T₁, T₂, ..., T_D are linearly independent in theiractions on the cycle e from 0 to i in H₁(X₀(N) (C), Q). In particular,he shows independence when max(D⁸, 400D⁴) < N/(log N)⁴. Inthis paper we use analytic techniques to show that one can chooseD considerably larger than this, provided that N is large.     

Algebras Generated by Holomorphic and Harmonic Functions on the Disc

Let E be a subset of the boundary of the open unit disc D, andlet A be the algebra of bounded holomorphic functions on D thatextend continuously to D E. It is shown that if f is a boundedharmonic function on D that extends continuously to D E andis not holomorphic, then the uniformly closed algebra A[f] generatedby A and f contains . This result contains as special cases a result on the disc algebradue to irka and a result on H(D due to Axler and Shields. Astronger form of the result, in which f is allowed to have discontinuitieson a small subset of E, is also established. 2000 MathematicsSubject Classification 46J10, 46J15, 30H05.     

Non-Regular Tangential Behaviour of a Monotone Measure

A Radon measure µ on Rⁿ is said to be k-monotone if is a non-decreasing function on (0,) for every x Rⁿ. (If µ is the k-dimensional Hausdorffmeasure restricted to a k-dimensional minimal surface then thisimportant property is expressed by the monotonicity formula.)We give an example of a 1-monotone measure µ in R² withnon-unique and non-conical tangent measures at a point. Furthermore,we show that µ can be the one-dimensional Hausdorff measurerestricted to a closed set A R². 2000 Mathematics Subject Classification49Q05, 49Q20 (primary), 28A75, 53A10 (secondary).     

Generalized Ramsey Theory for Graphs V. the Ramsey Number of a Digraph

Continuing this series of papers on generalized Ramsey theoryfor graphs, we define the Ramsey number r(D_l, D₂) of two digraphsD₁ and D₂ as the minimum p such that every 2-colouring of thearcs (directed lines) of DK_P (the complete symmetric digraphof order p) contains a monochromatic D₁ or D₂. It is shown(Theorem1) that this number exists if and only if D₁ or D₂ is acyclic.Then r(D), the diagonal Ramsey number of a given acyclic digraphD, is defined as r(D, D). Notation: D' is the converse of D,GD is the underlying graph of D, DG is the symmetric digraphof G, and T_p is the transitive tournament of order p. Let r(m,n) be the traditional Ramsey number of the two complete graphsK_m and K_n. Finally, let S_n be the star with n arcs from onepoint u to n points v_i. Assuming the Ramsey numbers under discussionexist, we prove the following results: THEOREM 2. r(D₁, D₂) = r(D₁' D₂'). THEOREM 3. r(D₁, D₂) r(GD₁, GD₂). THEOREM 4. r(D₁, D₂) r(T_P1, T_P2) if both D₁ and D₂ (with p₁and p₂ points respectively) are acyclic. THEOREM 5. r(T_m, T_n) = r(m, n). THEOREM 6. r(m, ri) r(T_m, DK_n) r(2^m–1, n). THEOREM 7. r(S_m, S_n) = r(S_m, S_n') = m+n. Finally, we establish all Ramsey numbers r(D₁, D₂) for digraphswithout isolates and with less than four points, and all diagonalRamsey numbers r(D) of acyclic digraphs without isolates withless than five points.     

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.     

On the connectedness of self-affine attractors

Let T = T(A, D) be a self-affine attractor in defined by an integral expanding matrix A and a digit set D. In the first part of this paper, in connection with canonical number systems, we study connectedness of T when D corresponds to the set of consecutive integers . It is shown that in and , for any integral expanding matrix A, T(A, D) is connected. In the second part, we study connectedness of Pisot dual tiles, which play an important role in the study of -expansions, substitutions and symbolic dynamical systems. It is shown that each tile of the dual tiling generated by a Pisot unit of degree 3 is arcwise connected. This is naturally expected since the digit set consists of consecutive integers as above. However surprisingly, we found families of disconnected Pisot dual tiles of degree 4. We even give a simple necessary and sufficient condition of connectedness of the Pisot dual tiles of degree 4. Detailed proofs will be given in [4]. Received: 2 March 2003     

An Euler-Type Version of the Local Steiner Formula for Convex Bodies

The purpose of this note is to establish a new version of thelocal Steiner formula and to give an application to convex bodiesof constant width. This variant of the Steiner formula generalizesresults of Hann [3] and Hug [6], who use much less elementarytechniques than the methods of this paper. In fact, Hann askedfor a simpler proof of these results [4, Problem 2, p. 900].We remark that our formula can be considered as a Euclideananalogue of a spherical result proved in [2, p. 46], and thatour method can also be applied in hyperbolic space. For some remarks on related formulas in certain two-dimensionalMinkowski spaces, see Hann [5, p. 363]. For further information about the notions used below, we referto Schneider's book [9]. Let Kⁿ be the set of all convex bodiesin Euclidean space Rⁿ, that is, the set of all compact, convex,non-empty subsets of Rⁿ. Let S^n–1 be the unit sphere.For KKⁿ, let NorK be the set of all support elements of K, thatis, the pairs (x, u)RⁿxS^n–1 such that x is a boundarypoint of K and u is an outer unit normal vector of K at thepoint x. The support measures (or generalized curvature measures)of K, denoted by ₀(K.), ..., _n–1(K.), are the unique Borelmeasures on RⁿxS^n–1 that are concentrated on NorK andsatisfy [formula] for all integrable functions f:RⁿR; here denotes the Lebesguemeasure on Rⁿ. Equation (1), which is a consequence and a slightgeneralization of Theorem 4.2.1 in Schneider [9], is calledthe local Steiner formula. Our main result is the following.1991 Mathematics Subject Classification 52A20, 52A38, 52A55.