Atomic surfaces, tilings and coincidence I. irreducible case

An irreducible Pisot substitution defines a graph-directed iterated function system. The invariant sets of this iterated function system are called the atomic surfaces. In this paper, a new tiling of atomic surfaces, which contains Thurston’sβ-tiling as a subclass, is constructed. Related tiling and dynamical properties are studied. Based on the coincidence condition defined by Dekking [Dek], we introduce thesuper-coincidence condition. It is shown that the super-coincidence condition governs the tiling and dynamical properties of atomic surfaces. We conjecture that every Pisot substitution satisfies the super-coincidence condition. The second author is supported by a JSPS Postdoc Fellowship.     

Substitution tilings and separated nets with similarities to the integer lattice

We show that any primitive substitution tiling of ℝ² creates a separated net which is biLipschitz to ℤ². Then we show that if H is a primitive Pisot substitution in ℝ ^d , for every separated net Y, that corresponds to some tiling τ ∈ X _H , there exists a bijection Φ between Y and the integer lattice such that sup _y∈Y ∥Φ(y) − y∥ < ∞. As a corollary, we get that we have such a Φ for any separated net that corresponds to a Penrose Tiling. The proofs rely on results of Laczkovich, and Burago and Kleiner.     

On the product of twists of rank two and a conjecture of Larsen

In this note we present examples of elliptic curves and infinite parametric families of pairs of integers (d,d′) such that, if we assume the parity conjecture, we can show that E ^d ,E ^d′ and E ^dd′ are all of positive even rank over ℚ. As an application, we show examples where a conjecture of M. Larsen holds.      

Algorithm for determining pure pointedness of self-affine tilings

Overlap coincidence in a self-affine tiling in Rd is equivalent to pure point dynamical spectrum of the tiling dynamical system. We interpret the overlap coincidence in the setting of substitution Delone set in Rd and find an efficient algorithm to check the pure point dynamical spectrum. This algorithm is easy to implement into a computer program. We give the program and apply it to several examples. In the course of the proof of the algorithm, we show a variant of the conjecture of Urbański (Solomyak (2006) [40]) on the Hausdorff dimension of the boundaries of fractal tiles.     

The Remak height for units

We investigate the values of the Remak height, which is a weighted product of the conjugates of an algebraic number. We prove that the ratio of logarithms of the Remak height and of the Mahler measure for units αof degree d is everywhere dense in the maximal interval [d/2(d-1),1] allowed for this ratio. To do this, a “large” set of totally positive Pisot units is constructed. We also give a lower bound on the Remak height for non-cyclotomic algebraic numbers in terms of their degrees. In passing, we prove some results about some algebraic numbers which are a product of two conjugates of a reciprocal algebraic number. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the Characterization of Expansion Maps for Self-Affine Tilings

We consider self-affine tilings in ℝ ⁿ with expansion matrix φ and address the question which matrices φ can arise this way. In one dimension, λ is an expansion factor of a self-affine tiling if and only if |λ| is a Perron number, by a result of Lind. In two dimensions, when φ is a similarity, we can speak of a complex expansion factor, and there is an analogous necessary condition, due to Thurston: if a complex λ is an expansion factor of a self-similar tiling, then it is a complex Perron number. We establish a necessary condition for φ to be an expansion matrix for any n, assuming only that φ is diagonalizable over ℂ. We conjecture that this condition on φ is also sufficient for the existence of a self-affine tiling.     

Central sets and substitutive dynamical systems

In this paper we establish a new connection between central sets and the strong coincidence conjecture   for fixed points of irreducible primitive substitutions of Pisot type. Central sets, first introduced by Furstenberg using notions from topological dynamics, constitute a special class of subsets of N$\mathbb{N}$ possessing strong combinatorial properties: Each central set contains arbitrarily long arithmetic progressions, and solutions to all partition regular systems of homogeneous linear equations. We give an equivalent reformulation of the strong coincidence condition in terms of central sets and minimal idempotent ultrafilters in the Stone–?ech compactification βN$\beta \mathbb{N}$. This provides a new arithmetical approach to an outstanding conjecture in tiling theory, the Pisot substitution conjecture  . The results in this paper rely on interactions between different areas of mathematics, some of which had not previously been directly linked: They include the general theory of combinatorics on words, abstract numeration systems, tilings, topological dynamics and the algebraic/topological properties of Stone–?ech compactification of N$\mathbb{N}$.     

Tiling Groupoids and Bratteli Diagrams II: Structure of the Orbit Equivalence Relation

In this second paper, we study the case of substitution tilings of \mathbb R^d{{\mathbb R}^d} . The substitution on tiles induces substitutions on the faces of the tiles of all dimensions j = 0, . . . , d − 1. We reconstruct the tiling’s equivalence relation in a purely combinatorial way using the AF-relations given by the lower dimensional substitutions. We define a Bratteli multi-diagram B{{\mathcal B}} which is made of the Bratteli diagrams B^j, j=0, ?d{{\mathcal B}^j, j=0, \ldots d} , of all those substitutions. The set of infinite paths in B^d{{\mathcal B}^d} is identified with the canonical transversal Ξ of the tiling. Any such path has a “border”, which is a set of tails in B^j{{\mathcal B}^j} for some j ≤ d, and this corresponds to a natural notion of border for its associated tiling. We define an étale equivalence relation R_B{{\mathcal R}_{\mathcal B}} on B{{\mathcal B}} by saying that two infinite paths are equivalent if they have borders which are tail equivalent in B^j{{\mathcal B}^j} for some j ≤ d. We show that R_B{{\mathcal R}_{\mathcal B}} is homeomorphic to the tiling’s equivalence relation R_X{{\mathcal R}_\Xi} .     

On <Emphasis Type="Italic">γ</Emphasis>-Vectors Satisfying the Kruskal–Katona Inequalities

We present examples of flag homology spheres whose γ-vectors satisfy the Kruskal–Katona inequalities. This includes several families of well-studied simplicial complexes, including Coxeter complexes and the simplicial complexes dual to the associahedron and to the cyclohedron. In these cases, we construct explicit flag simplicial complexes whose f-vectors are the γ-vectors in question, and so a result of Frohmader shows that the γ-vectors satisfy not only the Kruskal–Katona inequalities but also the stronger Frankl–Füredi–Kalai inequalities. In another direction, we show that if a flag (d−1)-sphere has at most 2d+3 vertices its γ-vector satisfies the Frankl–Füredi–Kalai inequalities. We conjecture that if Δ is a flag homology sphere then γ(Δ) satisfies the Kruskal–Katona, and further, the Frankl–Füredi–Kalai inequalities. This conjecture is a significant refinement of Gal’s conjecture, which asserts that such γ-vectors are nonnegative.     

Approximations and Lower Bounds for the Length of Minimal Euclidean Steiner Trees

We give a new lower bound on the length of the minimal Steiner tree with a given topology joining given terminals in Euclidean space, in terms of toroidal images. The lower bound is equal to the length when the topology is full. We use the lower bound to prove bounds on the “error” e in the length of an approximate Steiner tree, in terms of the maximum deviation d of an interior angle of the tree from 120°. Such bounds are useful for validating algorithms computing minimal Steiner trees. In addition we give a number of examples illustrating features of the relationship between e and d, and make a conjecture which, if true, would somewhat strengthen our bounds on the error. J. H. Rubinstein, J. Weng: Research supported by the Australian Research Council N. Wormald: Research supported by the Australian Research Council and the Canada Research Chairs Program. Research partly carried out while the author was in the Department of Mathematics and Statistics, University of Melbourne     

Geometry of the common dynamics of flipped Pisot substitutions

In this article we study the common dynamics of two different Pisot substitutions σ ₁ and σ ₂ having the same incidence matrix. This common dynamics arises in the study of the adic systems associated with the substitutions σ ₁ and σ ₂. Since the adic systems considered here have geometric realizations given by solutions to graph-directed iterated function systems, we actually study topological and measure-theoretic properties of the solution of those iterated function systems which describe the common dynamics. We also consider generalizations of these results to the nonunimodular case, the case of more than two substitutions and the case of two substitutions with different incidence matrices.     

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.     

Regular path decompositions of odd regular graphs

Kotzig asked in 1979 what are necessary and sufficient conditions for a d‐regular simple graph to admit a decomposition into paths of length d for odd d>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable to a decomposition of the graph into paths of length 3 where the middle edges of the paths coincide with the 1‐factor. We conjecture that existence of a 1‐factor is indeed a sufficient condition for Kotzig's problem. For general odd regular graphs, most 1‐factors appear to be extendable and we show that for the family of simple 5‐regular graphs with no cycles of length 4, all 1‐factors are extendable. However, for d>3 we found infinite families of d‐regular simple graphs with non‐extendable 1‐factors. Few authors have studied the decompositions of general regular graphs. We present examples and open problems; in particular, we conjecture that in planar 5‐regular graphs all 1‐factors are extendable. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 114–128, 2010     

Regularities of the Distribution of β-adic van der Corput Sequences

For Pisot numbers β with irreducible β-polynomial, we prove that the discrepancy function D(N, [0,y)) of the β-adic van der Corput sequence is bounded if and only if the β-expansion of y is finite or its tail is the same as that of the expansion of 1. If β is a Parry number, then we can show that the discrepancy function is unbounded for all intervals of length y ? \Bbb Q(b) y \notin {\Bbb Q}(\beta) . We give explicit formulae for the discrepancy function in terms of lengths of iterates of a reverse β-substitution.     

Non-periodic Tilings of ? n by Crosses

An n-dimensional cross consists of 2n+1 unit cubes: the “central” cube and reflections in all its faces. A tiling by crosses is called a Z-tiling if each cross is centered at a point with integer coordinates. Periodic tilings of ℝ ⁿ by crosses have been constructed by several authors for all n∈N. No non-periodic tiling of ℝ ⁿ by crosses has been found so far. We prove that if 2n+1 is not a prime, then the total number of non-periodic Z-tilings of ℝ ⁿ by crosses is 2^à₀2^{\aleph _{0}} while the total number of periodic Z-tilings is only ℵ₀. In a sharp contrast to this result we show that any two tilings of ℝ ⁿ ,n=2,3, by crosses are congruent. We conjecture that this is the case not only for n=2,3, but for all n where 2n+1 is a prime.     

Near optimal bounds for the Erdős distinct distances problem in high dimensions

We show that the number of distinct distances in a set of n points in ℝ ^d is Ω(n ^{2/d − 2 / d(d + 2)}), d ≥ 3. Erdős’ conjecture is Ω(n ^2/d ).     

Uniform Boundedness of Torsion Subgroups of Linear Groups

The torsion conjecture says： for any abelian variety A defined over a number field k, the order of the torsion subgroup of A（k） is bounded by a constant C（k,d） which depends only on the number field k and the dimension d of the abelian variety. The torsion conjecture remains open in general. However, in this paper, a short argument shows that the conjecture is true for more general fields if we consider linear groups instead of abelian varieties. If G is a connected linear algebraic group defined over a field k which is finitely generated over Q,Г is a torsion subgroup of G（k）. Then the order of Г is bounded by a constant C＇（k, d） which depends only on k and the dimension d of G.     

Counterexamples of the Conjecture on Roots of Ehrhart Polynomials

On roots of Ehrhart polynomials, Beck et al. conjecture that all roots α of the Ehrhart polynomial of an integral convex polytope of dimension d satisfy −d≤ℜ(α)≤d−1. In this paper, we provide counterexamples for this conjecture.     

The d-Step Conjecture and Gaussian Elimination

The d-step conjecture is one of the fundamental open problems concerning the structure of convex polytopes. Let Δ (d,n) denote the maximum diameter of a graph of a d-polytope that has n facets. The d-step conjecture Δ (d,2d) = d is proved equivalent to the following statement: For each ``general position' real matrix M there are two matrices drawn from a finite group matrices isomorphic to the symmetric group on d letters, such that has the Gaussian elimination factorization L ^-1 U in which L and U are lower triangular and upper triangular matrices, respectively, that have positive nontriangular elements. If #(M) is the number of pairs giving a positive L ^-1 U factorization, then #(M) equals the number of d-step paths between two vertices of an associated Dantzig figure. One consequence is that #(M)≤ d!. Numerical experiments all satisfied #(M) ≥ 2 ^d-1 , including examples attaining equality for 3 ≤ d ≤ 15. The inequality #(M) ≥ 2 ^d-1 is proved for d=3. For d≥ 4, examples with #(M) =2 ^d-1 exhibit a large variety of combinatorial types of associated Dantzig figures. These experiments and other evidence suggest that the d-step conjecture may be true in all dimensions, in the strong form #(M) ≥ 2 ^d-1 . Received April 10, 1995, and in revised form August 23, 1995.     

Regularities of the Distribution of β-adic van der Corput Sequences

For Pisot numbers β with irreducible β-polynomial, we prove that the discrepancy function D(N, [0,y)) of the β-adic van der Corput sequence is bounded if and only if the β-expansion of y is finite or its tail is the same as that of the expansion of 1. If β is a Parry number, then we can show that the discrepancy function is unbounded for all intervals of length . We give explicit formulae for the discrepancy function in terms of lengths of iterates of a reverse β-substitution.