Minimum boundary touching tilings of polyominoes

We study the problem of tiling a polyomino P with as few squares as possible such that every square in the tiling has a non‐empty intersection with the boundary of P . Our main result is an algorithm which given a simply connected polyomino P computes such a tiling of P . We indicate how one can improve the running time of this algorithm for the more restricted row‐column‐convex polyominoes. Finally we show that a related decision problem is in NP for rectangular polyominoes. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Imbedding posets in the integers

An imbedding of a poset P in the integers is a one-to-one order presevring map from P into the integers. Such a map always exists when P is finite and, moreover, certain imbeddings of subsets of finite P can be extended to imbeddings of the whole of P. D. E. Daykin has asked when an imbedding in the integers of a finite subset of a countable poset can be extended to the whole poset. This paper answers Daykin's question and some related questions.     

On the existence of Weierstrass points whose first non-gaps are five

LetH be a numerical semigroup, i.e., a subsemigroup of the additive semigroup N of non-negative integers whose complement N/H in N is finite. Leta be the least positive integer inH. Then we show that ifa=5, then there exists a pointed complete non-singular irreducible algebraic curve (C, P) such thatH is the set of integers which are pole orders atP of regular functions onC/{P}.     

Tilings of the integers can have superpolynomial periods

Let A be a finite set of integers. We say that A tiles the integers if there is a set T ⊆ ℤ such that {t+A: t∈T{ forms a disjoint partition of the integers. It has long been known that such a set T must be periodic. The question is to determine how long the period of T can become as a function of the diameter of the set A. The previous best lower bound, due to Kolountzakis [7], shows that the period of T can grow as fast as the square of the diameter of A. In this paper we improve Kolountzakis’ lower bound by showing that the period of T can in fact grow faster than any power of the diameter of A.     

Zero divisors in quaternion algebras

Let F be a finite field or an algebraic number field. In previous papers we have shown how to find the basic building blocks (the radical and the simple components) of a finite dimensional algebra over F in polynomial time (deterministically in characteristic zero and Las Vegas in the finite case). A finite-dimensional simple algebra A is a full matrix algebra over some not necessarily commutative extension field G of F. The problem remains to find G and an isomorphism between A and a matrix algebra over G. This, too, can be done in polynomial time for finite F. We indicate in the present paper that the problem for F = Q might be substantially more difficult. We link the problem to hard number theoretic problems such as quadratic residuosity modulo a composite number. We show that assuming the generalized Riemann hypothesis, there exists a randomized polynomial time reduction from quadratic residuosity to determining whether or not a given 4-dimensional algebra over Q has zero divisors. It will follow that finding a pair of zero divisors is at least as hard as factoring squarefree integers.     

Tilings of Convex Polygons with Congruent Triangles

By the spectrum of a polygon A we mean the set of triples (??,??,??) such that A can be dissected into congruent triangles of angles ??,??,??. We propose a technique for finding the spectrum of every convex polygon. Our method is based on the following classification. A tiling is called regular if there are two angles of the triangles, ?? and ?? such that at every vertex of the tiling the number of triangles having angle ?? equals the number of triangles having angle ??. Otherwise the tiling is irregular. We list all pairs (A,T) such that A is a convex polygon and T is a triangle that tiles A regularly. The list of triangles tiling A irregularly is always finite, and can be obtained, at least in principle, by considering the system of equations satisfied by the angles, examining the conjugate tilings, and comparing the sides and the area of the triangles to those of A. Using this method we characterize the convex polygons with infinite spectrum, and determine the spectrum of the regular triangle, the square, all rectangles, and the regular N-gons with N large enough.     

Invariant measures for non-primitive tiling substitutions

We consider self-affine tiling substitutions in Euclidean space and the corresponding tiling dynamical systems. It is well known that in the primitive case, the dynamical system is uniquely ergodic. We investigate invariant measures when the substitution is not primitive and the tiling dynamical system is non-minimal. We prove that all ergodic invariant probability measures are supported on minimal components, but there are other natural ergodic invariant measures, which are infinite. Under some mild assumptions, we completely characterize σ-finite invariant measures which are positive and finite on a cylinder set. A key step is to establish recognizability of non-periodic tilings in our setting. Examples include the “integer Sierpiński gasket and carpet” tilings. For such tilings, the only invariant probability measure is supported on trivial periodic tilings, but there is a fully supported σ-finite invariant measure that is locally finite and unique up to scaling.     

The entropies of renewal systems

Renewal systems are symbolic dynamical systems originally introduced by Adler. IfW is a finite set of words over a finite alphabetA, then the renewal system generated byW is the subshiftX _W ⊂A ^Z formed by bi-infinite concatenations of words fromW. Motivated by Adler’s question of whether every irreducible shift of finite type is conjugate to a renewal system, we prove that for every shift of finite type there is a renewal system having the same entropy. We also show that every shift of finite type can be approximated from above by renewal systems, and that by placing finite-type constraints on possible concatenations, we obtain all sofic systems. The authors were supported in part by NFS grants DMS-8706284, DMS-8814159 and DMS-8820716.     

Constraints on the angular distribution of the zeros of a polynomial of low complexity

LetP(z) be a polynomial of degreen with complex coefficients. Theorem.There exists a constant C such that if P has at most k terms then the number of zeros of P in any open sector of aperture π/n at the origin is no more than C ^k2. The main point of this bound is that it is independent both ofn and the coefficients ofP. The proof is a simple application of Khovanskii's real Bezout theorem to the system of real equations ReP=ImP=0. We also describe a measure of additive complexity for sets of integers and use it to estimate the angular distribution more finely.     

Degree sets for digraphs

The degree setD _D of a digraphD is the set of outdegrees of the vertices ofD. For a finite, nonempty setS of nonnegative integers, it is shown that there exists an asymmetric digraph (oriented graph)D such thatD _D =S. Furthermore, the minimum order of such a digraphD is determined. Also, given two finite sequences of nonnegative integers, a necessary and sufficient condition is provided for which these sequences are the outdegree sequences of the two sets of an asymmetric bipartite digraph.     

Classification of disordered tilings

A tilingT is a disordered realization of a periodic tilingP with symmetry group Γ if we can map the complement of a compact set ofT onto the quotientP/Γ in such a way that this map respects the features of the tilingT andP. We show that the global type of a 2-dimensional tilingT is determined by the periodic tilingP it is a disordered realization of, a conjugacy class of Γ which can be associated toT and a winding number. In some cases, we need in addition some kind of orientation. For higher-dimensional tilings of spaces which are simply connected at infinity, e.g. ℝ ⁿ withn≥3, the associated periodic tiling alone is sufficient.     

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).     

Exhaustive weakly wandering sequences

A sequence of integers {n_i : i = 0, 1…} is an exhaustive weakly wandering sequence for a transformation T if for some measurable set W, X=^∞_i=0TⁿⁱW(disj. We introduce a hereditary Property (H) for a sequence of integers associated with an infinite ergodic transformation T, and show that it is a sufficient condition for the sequence to be an exhaustive weakly wandering sequence for T. We then show that every infinite ergodic transformation admits sequences that possess Property (H), and observe that Property (H) is inherited by all subsequences of a sequence that possess it. As a corollary, we obtain an application to tiling the set of integers with infinite subsets.     

Random graph orders

Let P _n be the order determined by taking a random graph G on {1, 2,..., n}, directing the edges from the lesser vertex to the greater (as integers), and then taking the transitive closure of this relation. We call such and ordered set a random graph order. We show that there exist constants c, and °, such that the expected height and set up number of P _n are sharply concentrated around cn and °n respectively. We obtain the estimates: .565<c<.610, and .034<°<.289. We also discuss the width, dimension, and first-order properties of P _n.     

Arithmetical characterization of class groups of the form ℤ/<Emphasis Type="Italic">n</Emphasis>ℤ<Emphasis Type="Italic">⊕</Emphasis>ℤ/<Emphasis Type="Italic">n</Emphasis>ℤ via the system of sets of lengths

Let H be a Krull monoid with finite class group such that each class contains a prime divisor (e.g., the multiplicative monoid of the ring of algebraic integers of some number field). It is shown that it can be determined whether the class group is of the form ℤ/nℤ⊕ℤ/nℤ, for n≥3, just by considering the system of sets of lengths of H. Supported by the Austrian Science Fund FWF (Project P18779-N13).     

Characterization of Planar Pseudo-Self-Similar Tilings

A pseudo-self-similar tiling is a hierarchical tiling of Euclidean space which obeys a nonexact substitution rule: the substitution for a tile is not geometrically similar to itself. An example is the Penrose tiling drawn with rhombi. We prove that a nonperiodic repetitive tiling of the plane is pseudo-self-similar if and only if it has a finite number of derived Vorono\"{\i} tilings up to similarity. To establish this characterization, we settle (in the planar case) a conjecture of E. A. Robinson by providing an algorithm which converts any pseudo-self-similar tiling of R ² into a self-similar tiling of R ² in such a way that the translation dynamics associated to the two tilings are topologically conjugate. Received June 20, 2000, and in revised form January 25, 2001. Online publication July 25, 2001.     

A pentagonal crystal, the golden section, alcove packing and aperiodic tilings

A Lie theoretic interpretation is given to a pattern with five-fold symmetry occurring in aperiodic Penrose tiling based on isosceles triangles with length ratios equal to the Golden Section. Specifically a B(∞) crystal based on that of Kashiwara is constructed exhibiting this five-fold symmetry. It is shown that it can be represented as a Kashiwara B(∞) crystal in type A₄. Similar crystals with (2n + 1)-fold symmetry are represented as Kashiwara crystals in type A_2n . The weight diagrams of the latter inspire higher aperiodic tiling. In another approach alcove packing is seen to give aperiodic tiling in type A₄. Finally 2m-fold symmetry is related to type B _m . Work supported in part by Minerva grant, no. 8596/1.     

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     

Factoring wavelet transforms into lifting steps

This article is essentially tutorial in nature. We show how any discrete wavelet transform or two band subband filtering with finite filters can be decomposed into a finite sequence of simple filtering steps, which we call lifting steps but that are also known as ladder structures. This decomposition corresponds to a factorization of the polyphase matrix of the wavelet or subband filters into elementary matrices. That such a factorization is possible is well-known to algebraists (and expressed by the formulaSL(n;R[z, z⁻¹])=E(n;R[z, z⁻¹])); it is also used in linear systems theory in the electrical engineering community. We present here a self-contained derivation, building the decomposition from basic principles such as the Euclidean algorithm, with a focus on applying it to wavelet filtering. This factorization provides an alternative for the lattice factorization, with the advantage that it can also be used in the biorthogonal, i.e., non-unitary case. Like the lattice factorization, the decomposition presented here asymptotically reduces the computational complexity of the transform by a factor two. It has other applications, such as the possibility of defining a wavelet-like transform that maps integers to integers. Research Tutorial Acknowledgements and Notes. Page 264.