Detecting Combinatorial Hierarchy in Tilings Using Derived Voronoi Tessellations

   Abstract. Tilings of R ² can display hierarchy similar to that seen in the limit sequences of substitutions. Self-similarity for tilings has been used as the standard generalization, but this viewpoint is limited because such tilings are analogous to limit points of constant-length substitutions. To generalize limit points of non-constant-length substitutions, we define hierarchy for infinite, labelled graphs, then extend this definition to tilings via their dual graphs. Examples of combinatorially substitutive tilings that are not self-similar are given. We then find a sufficient condition for detecting combinatorial hierarchy that is motivated by the characterization by Durand of substitutive sequences. That characterization relies upon the construction of the ``derived sequence'—a recoding in terms of reappearances of an initial block. Following this, we define the ``derived Vorono? tiling'—a retiling in terms of reappearances of an initial patch of tiles. Using derived Vorono? tilings, we obtain a sufficient condition for a tiling to be combinatorially substitutive.     

Two finiteness theorems for periodic tilings of d-dimensional euclidean space

Consider the d -dimensional euclidean space E ^d . Two main results are presented: First, for any N∈ N, the number of types of periodic equivariant tilings that have precisely N orbits of (2,4,6, . . . ) -flags with respect to the symmetry group Γ , is finite. Second, for any N∈ N, the number of types of convex, periodic equivariant tilings that have precisely N orbits of tiles with respect to the symmetry group Γ , is finite. The former result (and some generalizations) is proved combinatorially, using Delaney symbols, whereas the proof of the latter result is based on both geometric arguments and Delaney symbols. <lsiheader> <onlinepub>7 August, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>20n2p143.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>no <sectionname> </lsiheader> Received September 5, 1996, and in revised form January 6, 1997.     

Detecting Combinatorial Hierarchy in Tilings Using Derived Voronoi Tessellations

Abstract. Tilings of R ² can display hierarchy similar to that seen in the limit sequences of substitutions. Self-similarity for tilings has been used as the standard generalization, but this viewpoint is limited because such tilings are analogous to limit points of constant-length substitutions. To generalize limit points of non-constant-length substitutions, we define hierarchy for infinite, labelled graphs, then extend this definition to tilings via their dual graphs. Examples of combinatorially substitutive tilings that are not self-similar are given. We then find a sufficient condition for detecting combinatorial hierarchy that is motivated by the characterization by Durand of substitutive sequences. That characterization relies upon the construction of the ``derived sequence'—a recoding in terms of reappearances of an initial block. Following this, we define the ``derived Vorono? tiling'—a retiling in terms of reappearances of an initial patch of tiles. Using derived Vorono? tilings, we obtain a sufficient condition for a tiling to be combinatorially substitutive.     

Rectangling a rectangle

We show that the following are equivalent: (i) A rectangle of eccentricityv can be tiled using rectangles of eccentricityu. (ii) There is a rational function with rational coefficients,Q(z), such thatv =Q(u) andQ maps each of the half-planes {z | Re(z) < 0} and {z | Re(z) > 0 into itself, (iii) There is an odd rational function with rational coefficients,Q(z), such thatv = Q(u) and all roots ofv = Q(z) have a positive real part. All rectangles in this article have sides parallel to the coordinate axes and all tilings are finite. We letR(x, y) denote a rectangle with basex and heighty. In 1903 Dehn [1 ] proved his famous result thatR(x, y) can be tiled by squares if and only ify/x is a rational number. Dehn actually proved the following result. (See [4] for a generalization to tilings using triangles.) The first and third authors were partially supported by NSF.     

Perfect Packings of Squares Using the Stack-Pack Strategy

Abstract. We consider the problem of packing an infinite set of square tiles into a finite number of rectangular boxes. We introduce a simple packing strategy that we call stack-pack. Using this strategy, we prove that if 1/2 < t < 2/3, then the squares of side n ^-t , for positive integers n , can be packed into some finite collection of square boxes of the same area ζ(2t) as the total area of the tiles.     

Perfect Packings of Squares Using the Stack-Pack Strategy

   Abstract. We consider the problem of packing an infinite set of square tiles into a finite number of rectangular boxes. We introduce a simple packing strategy that we call stack-pack. Using this strategy, we prove that if 1/2 < t < 2/3, then the squares of side n ^-t , for positive integers n , can be packed into some finite collection of square boxes of the same area ζ(2t) as the total area of the tiles.     

Fractional Poisson equations and ergodic theorems for fractional coboundaries

For a given contractionT in a Banach spaceX and 0<α<1, we define the contractionT _α=Σ _j=1 ^∞ a _j T ^j , where {a _j } are the coefficients in the power series expansion (1-t)^α=1-Σ _j=1 ^∞ a _j t ^j in the open unit disk, which satisfya _j >0 anda _j >0 and Σ _j=1 ^∞ a _j =1. The operator calculus justifies the notation(I−T) ^α :=I−T _α (e.g., (I−T _1/2)²=I−T). A vectory∈X is called an, α-fractional coboundary for T if there is anx∈X such that(I−T) ^α x=y, i.e.,y is a coboundary forT _α . The fractional Poisson equation forT is the Poisson equation forT _α . We show that if(I−T)X is not closed, then(I−T) ^α X strictly contains(I−T)X (but has the same closure). ForT mean ergodic, we obtain a series solution (converging in norm) to the fractional Poisson equation. We prove thaty∈X is an α-fractional coboundary if and only if Σ _k=1 ^∞ T ^k y/k ^1-α converges in norm, and conclude that lim _n ‖(1/n ^1-α)Σ _k=1 ⁿ T ^k y‖=0 for suchy. For a Dunford-Schwartz operatorT onL ₁ of a probability space, we consider also a.e. convergence. We prove that iff∈(I−T) ^α L ₁ for some 0<α<1, then the one-sided Hilbert transform Σ _k=1 ^∞ T ^k f/k converges a.e. For 1<p<∞, we prove that iff∈(I−T) ^α L _p with α>1−1/p=1/q, then Σ _k=1 ^∞ T ^k f/k ^1/p converges a.e., and thus (1/n ^1/p ) Σ _k=1 ⁿ T ^k f converges a.e. to zero. Whenf∈(I−T) ^1/q L _p (the case α=1/q), we prove that (1/n ^1/p (logn)^1/q )Σ _k=1 ⁿ T ^k f converges a.e. to zero.     

Fractal tiles associated with shift radix systems

Shift radix systems form a collection of dynamical systems depending on a parameter r which varies in the d-dimensional real vector space. They generalize well-known numeration systems such as beta-expansions, expansions with respect to rational bases, and canonical number systems. Beta-numeration and canonical number systems are known to be intimately related to fractal shapes, such as the classical Rauzy fractal and the twin dragon. These fractals turned out to be important for studying properties of expansions in several settings.In the present paper we associate a collection of fractal tiles with shift radix systems. We show that for certain classes of parameters r these tiles coincide with affine copies of the well-known tiles associated with beta-expansions and canonical number systems. On the other hand, these tiles provide natural families of tiles for beta-expansions with (non-unit) Pisot numbers as well as canonical number systems with (non-monic) expanding polynomials.We also prove basic properties for tiles associated with shift radix systems. Indeed, we prove that under some algebraic conditions on the parameter r of the shift radix system, these tiles provide multiple tilings and even tilings of the d-dimensional real vector space. These tilings turn out to have a more complicated structure than the tilings arising from the known number systems mentioned above. Such a tiling may consist of tiles having infinitely many different shapes. Moreover, the tiles need not be self-affine (or graph directed self-affine).     

Lattice triangulations of $\mathbb{E}^3 $ and of the 3-torus

This paper gives answers to a few questions concerning tilings of Euclidean spaces where the tiles are topological simplices with curvilinear edges. We investigate lattice triangulations of Euclidean 3-space in the sense that the vertices form a lattice of rank 3 and such that the triangulation is invariant under all translations of that lattice. This is the dual concept of a primitive lattice tiling where the tiles are not assumed to be Euclidean polyhedra but only topological polyhedra. In 3-space there is a unique standard lattice triangulation by Euclidean tetrahedra (and with straight edges) but there are infinitely many non-standard lattice triangulations where the tetrahedra necessarily have certain curvilinear edges. From the view-point of Discrete Differential Geometry this tells us that there are such triangulations of 3-space which do not carry any flat discrete metric which is equivariant under the lattice. Furthermore, we investigate lattice triangulations of the 3-dimensional torus as quotients by a sublattice. The standard triangulation admits such quotients with any number n ≥ 15 of vertices. The unique one with 15 vertices is neighborly, i.e., any two vertices are joined by an edge. It turns out that for any odd n ≥ 17 there is an n-vertex neighborly triangulation of the 3-torus as a quotient of a certain non-standard lattice triangulation. Combinatorially, one can obtain these neighborly 3-tori as slight modifications of the boundary complexes of the cyclic 4-polytopes. As a kind of combinatorial surgery, this is an interesting construction by itself.     

Fractal Penrose tilings I. Construction and matching rules

Summary Quasiperiodic tilings of kite-and-dart type, widely used as models for quasicrystals with decagonal symmetry, are constructed by means of somewhat artificial matching rules for the tiles. The proof of aperiodicity uses a self-similarity property, or inflation procedure, which requires drawing auxiliary lines. We introduce a modification of the kite-and-dart tilings which comes very naturally with both properties: the tiles are strictly self-similar, and their fractal boundaries provide perfect matching rules.     

Covering properties which,under weak diamond principles,constrain the extents of separable spaces

We show that separable, locally compact spaces with property (a) necessarily have countable extent — i.e., have no uncountable closed, discrete subspaces — if the effective weak diamond principle ⋄(ω,ω,<) holds. If the stronger, non-effective, diamond principle Φ(ω,ω,<) holds then separable, countably paracompact spaces also have countable extent. We also give a short proof that the latter principle implies there are no small dominating families in ^ω ₁ ω.     

On Dehn Functions of Infinite Presentations of Groups

We introduce two new types of Dehn functions of group presentations which seem more suitable (than the standard Dehn function) for infinite group presentations and prove the fundamental equivalence between the solvability of the word problem for a group presentation defined by a decidable set of defining words and the property of being computable for one of the newly introduced functions (this equivalence fails for the standard Dehn function). Elaborating on this equivalence and making use of this function, we obtain a characterization of finitely generated groups for which the word problem can be solved in nondeterministic polynomial time. We also give upper bounds for these functions, as well as for the standard Dehn function, for two well-known periodic groups. In particular, we prove that the (standard) Dehn function of a 2-group Γ of intermediate growth, defined by a system of defining relators due to Lysenok, is bounded from above by C₁x² log₂ x, where C₁ > 1 is a constant. We also show that the (standard) Dehn function of a free m-generator Burnside group B(m, n) of exponent n ≥ 2⁴⁸, where n is either odd or divisible by 2⁹, defined by a minimal system of defining relators, is bounded from above by the subquadratic function x^19/12. Received: September 2007, Revision: March 2008, Accepted: March 2008     

Hitting, returning and the short correlation function

We consider a stochastic process with the weakest mixing condition: the so called α. For any fixed n-string we prove the following results. (1) The hitting time has approximately exponential law. (2) The return time has approximately a convex combination between a Dirac measure at the origin and an exponential law. In both cases the parameter of the exponential law is λ(A)ℙ(A) where ℙ(A) is the measure of the string and λ(A) is a certain autocorrelation function of the string. We show also that the weight of the convex combination is approximately λ(A). We describe the behavior of this autocorrelation function. Our results hold when the rate of mixing decays polinomially fast with power larger than the golden number.     

Polytopes that fill ℝn and scissors congruenceand scissors congruence

Suppose thatP is a (not necessarily convex) polytope in ℝ ⁿ that can fill ℝ ⁿ with congruent copies of itself. Then, except for its volume, all its classical Dehn invariants for Euclidean scissors congruence must be zero. In particular, in dimensions up to 4, any suchP is Euclidean scissors congruent to ann-cube. An analogous result holds in all dimensions for translation scissors congruence.     

Tilings of Polygons with Similar Triangles, II

Let A be a polygon, and let s (A) denote the number of distinct nonsimilar triangles Δ such that A can be dissected into finitely many triangles similar to Δ . If A can be decomposed into finitely many similar symmetric trapezoids, then s(A)=∞ . This implies that if A is a regular polygon, then s(A)=∞ . In the other direction, we show that if s(A)=∞ , then A can be decomposed into finitely many symmetric trapezoids with the same angles. We introduce the following classification of tilings: a tiling is regular if Δ has two angles, α and β , such that at each vertex of the tiling the number of angles α is the same as that of β . Otherwise the tiling is irregular. We prove that for every polygon A the number of triangles that tile A irregularly is at most c ⋅ n ⁶ , where n is the number of vertices of A. If A has a regular tiling, then A can be decomposed into finitely many symmetric trapezoids with the same angles. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p411.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received February 17, 1997, and in revised form June 16, 1997.     

Block band Toeplitz preconditioners derived from generating function approximations: analysis and applications

We are concerned with the study and the design of optimal preconditioners for ill-conditioned Toeplitz systems that arise from a priori known real-valued nonnegative generating functions f(x,y) having roots of even multiplicities. Our preconditioned matrix is constructed by using a trigonometric polynomial θ(x,y) obtained from Fourier/kernel approximations or from the use of a proper interpolation scheme. Both of the above techniques produce a trigonometric polynomial θ(x,y) which approximates the generating function f(x,y), and hence the preconditioned matrix is forced to have clustered spectrum. As θ(x,y) is chosen to be a trigonometric polynomial, the preconditioner is a block band Toeplitz matrix with Toeplitz blocks, and therefore its inversion does not increase the total complexity of the PCG method. Preconditioning by block Toeplitz matrices has been treated in the literature in several papers. We compare our method with their results and we show the efficiency of our proposal through various numerical experiments.This research was co-funded by the European Union in the framework of the program “Pythagoras I” of the “Operational Program for Education and Initial Vocational Training” of the 3rd Community Support Framework of the Hellenic Ministry of Education, funded by national sources (25%) and by the European Social Fund - ESF (75%). The work of the second and of the third author was partially supported by MIUR (Italian Ministry of University and Research), grant number 2004015437.     

Operads,configuration spaces and quantization

We review several well-known operads of compactified configuration spaces and construct several new such operads, [`(C)]\bar C, in the category of smooth manifolds with corners whose complexes of fundamental chains give us (i) the 2-coloured operad of A <sub>∞</sub>-algebras and their homotopy morphisms, (ii) the 2-coloured operad of L <sub>∞</sub>-algebras and their homotopy morphisms, and (iii) the 4-coloured operad of openclosed homotopy algebras and their homotopy morphisms. Two gadgets — a (coloured) operad of Feynman graphs and a de Rham field theory on [`(C)]\bar C — are introduced and used to construct quantized representations of the (fundamental) chain operad of [`(C)]\bar C which are given by Feynman type sums over graphs and depend on choices of propagators.     

The Discrepancy of Boxes in Higher Dimension

We prove that the red—blue discrepancy of the set system formed by n points and n axis-parallel boxes in <bo>R</bo> ^d can be as high as n ^Ω(1) in any dimension d= Ω(log n) . This contrasts with the fixed-dimensional case d=O(1) , where the discrepancy is always polylogarithmic. More generally we show that in any dimension 1<d= O(log n) the maximum discrepancy is 2 ^Ω(d) . Our result also leads to a new lower bound on the complexity of off-line orthogonal range searching. This is the problem of summing up weights in boxes, given n weighted points and n boxes in <bo>R</bo> ^d . We prove that the number of arithmetic operations is at least Ω(nd+ nlog log n) in any dimension d=O(log n) . Received June 30, 2000, and in revised form November 9, 2000. Online publication April 6, 2001.     

On the duals of Lp spaces with 0<p<1

Given a measure space < Ω,m,μ >, a locally bounded, Hausdorff topological linear space < X, τ > and a real number 0<p<1, one can define the space L_p(Ω,m,μ,X), which is, under certain assumptions, a Fréchet space if endowed with a suitable topology. M.M. Day [1] has given a necessary and sufficient condition, in terms of the properties of the measure space < Ω,m,μ >, for the dual of L_p(Ω,m,μ,C) to be trivial. In this paper a different proof along with a slight generalization is given for this result, using standard and elementary measure theoretic arguments. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Framework for the Construction of Self-replicating Tilings

Dekking (Adv. Math. 44:78–104, 1982; J. Comb. Theory Ser. A 32:315–320, 1982) provided an important method to compute the boundaries of lattice rep-tiles as a ‘recurrent set’ on a free group of a finite alphabet. That is, those tilings are generated by lattice translations of a single tile, and there is an expanding linear map that carries tiles to unions of tiles. The boundary of the tile is identified with a sequence of words in the alphabet obtained from an expanding endomorphism (substitution) on the alphabet. In this paper, Dekking’s construction is generalized to address tilings with more than one tile, and to have the elements of the tilings be generated by both translation and rotations. Examples that fall within the scope of our main result include self-replicating multi-tiles, self-replicating tiles for crystallographic tilings and aperiodic tilings.