Fundamental group of tiles associated to quadratic canonical number systems

If A is a 2 × 2 expanding matrix with integral coefficients, and ⊂ ℤ² a complete set of coset representatives of ℤ²/Aℤ² with |det(A)| elements, then the set ℐ defined by Aℐ = ℐ + is a self-affine plane tile of ℝ², provided that its two-dimensional Lebesgue measure is positive. It was shown by Luo and Thuswaldner that the fundamental group of such a tile is either trivial or uncountable. To a quadratic polynomial x ² + Ax + B, A, B ∈ ℤ such that B ≥ 2 and −1 ≤ A ≤ B, one can attach a tile ℐ. Akiyama and Thuswaldner proved the triviality of the fundamental group of this tile for 2A < B + 3, by showing that a tile of this class is homeomorphic to a closed disk. The case 2A ≥ B + 3 is treated here by using the criterion given by Luo and Thuswaldner. This research was supported by the Austrian Science Fundation (FWF), projects S9610 and S9612, that are part of the Austrian National Research Network “Analytic Combinatorics and Probabilistic Number theory”.     

When is the union of two unit intervals a self-similar set satisfying the open set condition?

Let U _λ be the union of two unit intervals with gap λ. We show that U _λ is a self-similar set satisfying the open set condition if and only if U _λ can tile an interval by finitely many of its affine copies (admitting different dilations). Furthermore, each such λ can be characterized as the spectrum of an irreducible double word which represents a tiling pattern. Some further considerations of the set of all such λ’s, as well as the corresponding tiling patterns, are given. The first author was partially supported by the RGC grant and the direct grant in CUHK, Fok Ying Tong Education Foundation and NSFC (10571100). The second author was partially supported by NSFC (70371074) and NFSC (10571104).     

On the Structure of Multiple Translational Tilings by Polygonal Regions

We consider polygons with the following ``pairing property': for each edge of the polygon there is precisely one other edge parallel to it. We study the problem of when such a polygon K tiles multiply the plane when translated at the locations Λ , where Λ is a multiset in the plane. The pairing property of K makes this question particularly amenable to Fourier analysis. As a first application of our approach we establish a necessary and sufficient condition for K to tile with a given lattice Λ . (This was first found by Bolle for the case of convex polygons—notice that all convex polygons that tile, necessarily have the pairing property and, therefore, our theorems apply to them.) Our main result is a proof that a large class of such polygons tile multiply only quasi-periodically, which for us means that Λ must be a finite union of translated two-dimensional lattices in the plane. For the particular case of convex polygons we show that all convex polygons which are not parallelograms tile multiply only quasi-periodically, if at all. Received February 24, 1999, and in revised form August 26, 1999, and October 9, 1999.     

Procreating tiles of double commutative-step digraphs

Double commutative-step digraph generalizes the double-loop digraph. A double commutative-step digraph can be represented by an L-shaped tile, which periodically tessellates the plane. Given an initial tile L（l, h, x, y）, Aguil5 et al. define a discrete iteration L（p） = L（l ＋ 2p, h ＋ 2p, x ＋ p, y ＋ p）, p = 0, 1, 2,..., over L-shapes （equivalently over double commutative-step digraphs）, and obtain an orbit generated by L（l, h, x,y）, which is said to be a procreating k-tight tile if L（p）（p = 0, 1, 2, ~ ~ ~ ） are all k-tight tiles. They classify the set of L-shaped tiles by its behavior under the above-mentioned discrete dynamics and obtain some procreating tiles of double commutative-step digraphs. In this work, with an approach proposed by Li and Xu et al., we define some new discrete iteration over L-shapes and classify the set of tiles by the procreating condition. We also propose some approaches to find infinite families of realizable k-tight tiles starting from any realizable k-tight L-shaped tile L（l, h, x, y）, 0 ≤ y - x ≤ 2k ＋ 2. As an example, we present an infinite family of 3-tight optimal double-loop networks to illustrate our approaches.     

Construction of wavelet sets with certain self-similarity properties

A measurable set Q ⊂ R ⁿ is a wavelet set for an expansive matrix A if F ⁻¹ _(ΧQ) is an A-dilation wavelet. Dai, Larson, and Speegle [7] discovered the existence of wavelet sets in R _n associated with any real n ×n expansive matrix. In this work, we construct a class of compact wavelet sets which do not contain the origin and which are, up to a certain linear transformation, finite unions of integer translates of an integral selfaffine tile associated with the matrix B = A ^t. Some of these wavelet sets may have good potential for applications because of their tractable geometric shapes.     

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.     

Upper Bound on the Packing Density of Regular Tetrahedra and Octahedra

Aristotle contended that (regular) tetrahedra tile space, an opinion that remained widespread until it was observed that non-overlapping tetrahedra cannot subtend a solid angle of 4π around a point if this point lies on a tetrahedron edge. From this 15th century argument, we can deduce that tetrahedra do not tile space but, more than 500 years later, we are unaware of any known non-trivial upper bound to the packing density of tetrahedra. In this article, we calculate such a bound. To this end, we show the existence, in any packing of regular tetrahedra, of a set of disjoint spheres centered on tetrahedron edges, so that each sphere is not fully covered by the packing. The bound on the amount of space that is not covered in each sphere is obtained in a recursive way by building on the solid angle argument. The argument can be readily modified to apply to other polyhedra. The resulting lower bound on the fraction of empty space in a packing of regular tetrahedra is 2.6…×10⁻²⁵ and reaches 1.4…×10⁻¹² for regular octahedra.     

Rigidity of planar tilings

Summary Aperturbation of a tiling of a region inR ⁿ is a set of isometries, one applied to each tile, so that the images of the tiles tile the same region.We show that a locally finite tiling of an open region inR ² with tiles which are closures of their interiors isrigid in the following sense: any sufficiently small perturbation of the tiling must have only earthquake-type discontinuities, that is, the discontinuity set consists of straight lines and arcs of circles, and the perturbation near such a curve shifts points along the direction of that curve.We give an example to show that this type of rigidity does not hold inR ⁿ , forn>2.Using rigidity in the plane we show that any tiling problem with a finite number of tile shapes (which are topological disks) is equivalent to a polygonal tiling problem, i.e. there is a set of polygonal shapes with equivalent tiling combinatorics.Oblatum 19-III-1991     

Triangulations (tilings) and certain block triangular matrices

For a convex polygonP withn sides, a ‘partitioning’ ofP inton−2 nonoverlapping triangles each of whose vertices is a vertex ofP is called a triangulation or tiling, and each triangle is a tile. Each tile has a given cost associated with it which may differ one from another. This paper considers the problem of finding a tiling ofP such that the sum of the costs of the tiles used is a minimum, and explores the curiosity that (an abstract formulation of) it can be cast as a linear program. Further the special structure of the linear program permits a recursive O(n ³) algorithm. Research and reproduction of this report were partially supported by the National Science Foundation Grants MCS-8119774, MCS-7926009 and ECS-8012974; Department of Energy Contract DE-AM03-76SF00326, PA# DE-AT03-76ER72018; Office of Naval Research Contract N00014-75-C-0267. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and donot necessarily reflect the views of the above sponsors.     

Tiling groups: New applications in the triangular lattice

We first give a new presentation of an algorithm, from W. Thurston, to tile polygons with ``calissons' (i.e., lozenges formed from two cells of the triangular lattice Λ ). Afterward, we use a similar method to get a linear algorithm to tile polygons with m -leaning bars (parallelograms of length m formed from 2m cells of Λ ) and equilateral triangles (whose sides have length m ) and we produce a quadratic algorithm to tile polygons with m -leaning bars. <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>20n2p189.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>no <sectionname> </lsiheader> Received July 3, 1996, and in revised form May 14, 1997.     

Self-Affine Sets and Graph-Directed Systems

   Abstract. A self-affine set in R ⁿ is a compact set T with A(T)= ∪ _{d∈ D} (T+d) where A is an expanding n× n matrix with integer entries and D ={d ₁ , d ₂ ,···, d _N } ⊂ Z ⁿ is an N -digit set. For the case N = | det(A)| the set T has been studied in great detail in the context of self-affine tiles. Our main interest in this paper is to consider the case N > | det(A)| , but the theorems and proofs apply to all the N . The self-affine sets arise naturally in fractal geometry and, moreover, they are the support of the scaling functions in wavelet theory. The main difficulty in studying such sets is that the pieces T+d, d∈ D, overlap and it is harder to trace the iteration. For this we construct a new graph-directed system to determine whether such a set T will have a nonvoid interior, and to use the system to calculate the dimension of T or its boundary (if T ^o ≠  ). By using this setup we also show that the Lebesgue measure of such T is a rational number, in contrast to the case where, for a self-affine tile, it is an integer.     

Aperiodic Tilings with One Prototile and Low Complexity Atlas Matching Rules

We give a constructive method that can decrease the number of prototiles needed to tile a space. We achieve this by exchanging edge-to-edge matching rules for a small atlas of permitted patches. This method is illustrated with Wang tiles, and we apply our method to present via these rules a single prototile that can only tile ℝ³ aperiodically, and a pair of square tiles that can only tile ℝ² aperiodically.     

Wild tiles in ℝ<Superscript>3</Superscript> with spherical boundaries

Wildly embedded tiles in ℝ³ with spherical boundary are discussed. The construction of the topologically complicated, crumpled cube tiles is reviewed. We construct an infinite family of wildly embedded, cellular tiles with Fox-Artin-type wild points. Finally, a condition on the set of wild points on a cellular tile is given to show that certain wild cells cannot be tiles. Several observations are recorded for further investigations. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 11, No. 4, pp. 203–211, 2005.     

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.     

Error diffusion on simplices: The structure of bounded invariant tiles

This is a companion paper to Adleret al. (in press, 2015). There, we proved the existence of an absorbing invariant tile for the Error Diffusion dynamics on an acute simplex when the input is constant and “ergodic” and we discuss the geometry of this tile. Under the same assumptions we prove here that said invariant tile (a fundamental set of the lattice generated by the vertices of the simplex) which is a finite union of polytopes have the property that any union of the intersections of the tile with the Voronoï regions of the vertices is a tile for a different, explicitly defined lattice.     

一类自相似tile成为框架集的充分必要条件

本文研究了数字集具有严格乘积形式的自相似tile成为框架集的问题.利用Zak变换,证明了自相似tile是框架集的充要条件是其数字集D={0,1,2…,N-1}.     

On Fuglede's Conjecture and the Existence of Universal Spectra

Recent methods developed by Tao [18], Kolountzakis and Matolcsi [7] have led to counterexamples to Fugelde’s Spectral Set Conjecture in both directions. Namely, in Tao produced a spectral set which is not a tile, while Kolountzakis and Matolcsi showed an example of a nonspectral tile. In search of lower dimensional nonspectral tiles we were led to investigate the Universal Spectrum Conjecture (USC) of Lagarias and Wang [14]. In particular, we prove here that the USC and the "tile → spectral" direction of Fuglede’s conjecture are equivalent in any dimensions. Also, we show by an example that the sufficient condition of Lagarias and Szabó [13] for the existence of universal spectra is not necessary. This fact causes considerable difficulties in producing lower dimensional examples of tiles which have no spectra. We overcome these difficulties by invoking some ideas of Révész and Farkas [2], and obtain nonspectral tiles in . Fuglede’s conjecture and the Universal Spectrum Conjecture remains open in 1 and 2 dimensions. The one-dimensional case is closely related to a number theoretical conjecture on tilings by Coven and Meyerowitz [1].     

Topological Structure of Non-wandering Set of a Graph Map

Let G be a graph （i.e., a finite one-dimensional polyhedron） and f ： G → G be a continuous map. In this paper, we show that every isolated recurrent point of f is an isolated non-wandering point; every accumulation point of the set of non-wandering points of f with infinite orbit is a two-order accumulation point of the set of recurrent points of f; the derived set of an ω-limit set of f is equal to the derived set of an the set of recurrent points of f; and the two-order derived set of non-wandering set of f is equal to the two-order derived set of the set of recurrent points of f.     

On weight distributions of perfect colorings and completely regular codes

A vertex coloring of a graph is called “perfect” if for any two colors a and b, the number of the color-b neighbors of a color-a vertex x does not depend on the choice of x, that is, depends only on a and b (the corresponding partition of the vertex set is known as “equitable”). A set of vertices is called “completely regular” if the coloring according to the distance from this set is perfect. By the “weight distribution” of some coloring with respect to some set we mean the information about the number of vertices of every color at every distance from the set. We study the weight distribution of a perfect coloring (equitable partition) of a graph with respect to a completely regular set (in particular, with respect to a vertex if the graph is distance-regular). We show how to compute this distribution by the knowledge of the color composition over the set. For some partial cases of completely regular sets, we derive explicit formulas of weight distributions. Since any (other) completely regular set itself generates a perfect coloring, this gives universal formulas for calculating the weight distribution of any completely regular set from its parameters. In the case of Hamming graphs, we prove a very simple formula for the weight enumerator of an arbitrary perfect coloring.     

Block separation in solvable groups

If π is a set of primes, a finite group G is block π-separated if for every two distinct irreducible complex characters α, β ∈ Irr(G) there exists a prime p ∈ π such that α and β lie in different Brauer p-blocks. A group G is block separated if it is separated by the set of prime divisors of |G|. Given a set π with n different primes, we construct an example of a solvable π-group G which is block separated but it is not separated by every proper subset of π. Received: 22 December 2004