On the Connectedness of Self-Affine Tiles

Let T be a self-affine tile in Rⁿ defined by an integral expandingmatrix A and a digit set D. The paper gives a necessary andsufficient condition for the connectedness of T. The conditioncan be checked algebraically via the characteristic polynomialof A. Through the use of this, it is shown that in R², for anyintegral expanding matrix A, there exists a digit set D suchthat the corresponding tile T is connected. This answers a questionof Bandt and Gelbrich. Some partial results for the higher-dimensionalcases are also given.     

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.     

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

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     

Integral Self-Affine Tiles in {\Bbb R}^n Part II: Lattice Tilings

Let A be an expanding n × n integer matrix with |det (A)| = m. A standard digit set ${\cal D}Let A be an expanding n×n integer matrix with |det(A)|=m. Astandard digit set D for A is any complete set of coset representatives for? ⁿ /A(? ⁿ ). Associated to a given D is a setT (A, D), which is the attractor of an affine iterated function system, satisfyingT=∪ _d∈D (T+d). It is known thatT (A, D) tiles? ⁿ by some subset of? ⁿ . This paper proves that every standard digit set D gives a setT (A, D) that tiles? ⁿ with a lattice tiling.     

Integral self-affine tiles in ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> part II: Lattice tilings

Let A be an expanding n×n integer matrix with |det(A)|=m. Astandard digit set D for A is any complete set of coset representatives forℤ ⁿ /A(ℤ ⁿ ). Associated to a given D is a setT (A, D), which is the attractor of an affine iterated function system, satisfyingT=∪ _d∈D (T+d). It is known thatT (A, D) tilesℝ ⁿ by some subset ofℤ ⁿ . This paper proves that every standard digit set D gives a setT (A, D) that tilesℝ ⁿ with a lattice tiling.     

On number system constructions

We investigate various number system constructions. After summarizing earlier results we prove that for a given lattice Λ and expansive matrix M: Λ → Λ if ρ(M ⁻¹) < 1/2 then there always exists a suitable digit set D for which (Λ, M, D) is a number system. Here ρ means the spectral radius of M ⁻¹. We shall prove further that if the polynomial f(x) = c ₀ + c ₁ x + ··· + c _k x ^k ∈ Z[x], c _k = 1 satisfies the condition |c ₀| > 2 Σ _i=1 ^k |c _i | then there is a suitable digit set D for which (Z ^k , M, D) is a number system, where M is the companion matrix of f(x). The research was supported by OTKA-T043657 and Bolyai Fellowship Committee.     

Hamilton cycles,avoiding prescribed arcs,in close-to-regular tournaments

The local irregularity of a digraph D is defined as i_l(D) = max {|d⁺ (x) − d⁻ (x)| : x ϵ V(D)}. Let T be a tournament, let Γ = {V₁, V₂, …, V_c} be a partition of V(T) such that |V₁| ≥ |V₂| ≥ … ≥ |V_c|, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in Γ. We prove that, if |V(T)| ≥ max{2i_l(T) + 2|V₁| + 2|V₂| − 2, i_l(T) + 3|V₁| − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., i_l(T) = 0), then we state slightly better lower bounds for |V(T)| such that we still can guarantee that D is Hamiltonian. Finally, we show that our results are best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 123–136, 1999     

Algebraic methods in sum-product phenomena

We classify the polynomials f(x, y) ∈ ℝ[x, y] such that, given any finite set A ⊂ ℝ, if |A + A| is small, then |f(A,A)| is large. In particular, the following bound holds: |A + A‖f(A,A)| ≳ |A|^5/2. The Bezout theorem and a theorem by Y. Stein play an important role in our proof.     

Integral distance graphs

Suppose D is a subset of all positive integers. The distance graph G(Z, D) with distance set D is the graph with vertex set Z, and two vertices x and y are adjacent if and only if |x − y| ≡ D. This paper studies the chromatic number χ(Z, D) of G(Z, D). In particular, we prove that χ(Z, D) ≤ |D| + 1 when |D| is finite. Exact values of χ(G, D) are also determined for some D with |D| = 3. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 287–294, 1997     

Maximum Hitting of a Set by Compressed Intersecting Families

For a family A{\mathcal{A}} and a set Z, denote {A ? A \colon A ?Z 1 ?}{\{A \in \mathcal{A} \colon A \cap Z \neq \emptyset\}} by A(Z){\mathcal{A}(Z)}. For positive integers n and r, let S_n,r{\mathcal{S}_{n,r}} be the trivial compressed intersecting family {A ? (c[n]r ) \colon 1 ? A}{\{A \in \big(\begin{subarray}{c}[n]\\r \end{subarray}\big) \colon 1 \in A\}}, where [n] : = {1, ?, n}{[n] := \{1, \ldots, n\}} and (c[n]r ) : = {A ì [n] \colon |A| = r}{\big(\begin{subarray}{c}[n]\\r \end{subarray}\big) := \{A \subset [n] \colon |A| = r\}}. The following problem is considered: For r ≤ n/2, which sets Z í [n]{Z \subseteq [n]} have the property that |A(Z)| ￡ |S_n,r(Z)|{|\mathcal{A}(Z)| \leq |\mathcal{S}_{n,r}(Z)|} for any compressed intersecting family A ì (c[n]r ){\mathcal{A}\subset \big(\begin{subarray}{c}[n]\\r \end{subarray}\big)}? (The answer for the case 1 ? Z{1 \in Z} is given by the Erdős–Ko–Rado Theorem.) We give a complete answer for the case |Z| ≥ r and a partial answer for the much harder case |Z| < r. This paper is motivated by the observation that certain interesting results in extremal set theory can be proved by answering the question above for particular sets Z. Using our result for the special case when Z is the r-segment {2, ?, r+1}{\{2, \ldots, r+1\}}, we obtain new short proofs of two well-known Hilton–Milner theorems. At the other extreme end, by establishing that |A(Z)| ￡ |S_n,r(Z)|{|\mathcal{A}(Z)| \leq |\mathcal{S}_{n,r}(Z)|} when Z is a final segment, we provide a new short proof of a Holroyd–Talbot extension of the Erdős-Ko-Rado Theorem.     

On finite groups whose derived subgroup has bounded rank

Let G be a finite group with derived subgroup of rank r. We prove that |G: Z ₂(G)| ≤ |G′|^2r . Motivated by the results of I. M. Isaacs in [5] we show that if G is capable then |G: Z(G)| ≤ |G′|^4r . This answers a question of L. Pyber. We prove that if G is a capable p-group then the rank of G/Z(G) is bounded above in terms of the rank of G′.     

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.     

Zero divisors and prime elements of bounded semirings

A semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse. A bounded semiring is a semiring equipped with a compatible bounded partial order. In this paper, properties of zero divisors and prime elements of a bounded semiring are studied. In particular, it is proved that under some mild assumption, the set Z（A） of nonzero zero divisors of A is A ／ {0, 1}, and each prime element of A is a maximal element. For a bounded semiring A with Z（A） = A ／ {0, 1}, it is proved that A has finitely many maximal elements if ACC holds either for elements of A or for principal annihilating ideals of A. As an application of prime elements, we show that the structure of a bounded semiring A is completely determined by the structure of integral bounded semirings if either ｜Z（A）｜ = 1 or ｜Z（A）｜ -- 2 and Z（A）2 ≠ 0. Applications to the ideal structure of commutative rings are also considered. In particular, when R has a finite number of ideals, it is shown that the chain complex of the poset I（R） is pure and shellable, where I（R） consists of all ideals of R.     

Determinantal Inequalities for Accretive-Dissipative Matrices

A matrix is said to be accretive-dissipative if, in its Hermitian decomposition , both matrices B and C are positive definite. Further, if B= I _n, then A is called a Buckley matrix. The following extension of the classical Fischer inequality for Hermitian positive-definite matrices is proved. Let be an accretive-dissipative matrix, k and l be the orders of A ₁₁ and A ₂₂, respectively, and let m = min{k,l}. Then For Buckley matrices, the stronger bound is obtained. Bibliography: 5 titles.     

Parseval Frame Wavelet Multipliers in L2（Rd）

Let A be a d × d real expansive matrix. An A-dilation Parseval frame wavelet is a function ?? ?? L ²(? ^d ), such that the set $ \left\{ {\left| {\det A} \right|^{\frac{n} {2}} \psi \left( {A^n t - \ell } \right):n \in \mathbb{Z},\ell \in \mathbb{Z}^d } \right\} $ forms a Parseval frame for L ²(? ^d ). A measurable function f is called an A-dilation Parseval frame wavelet multiplier if the inverse Fourier transform of d??? is an A-dilation Parseval frame wavelet whenever ?? is an A-dilation Parseval frame wavelet, where ??? denotes the Fourier transform of ??. In this paper, the authors completely characterize all A-dilation Parseval frame wavelet multipliers for any integral expansive matrix A with |det(A)| = 2. As an application, the path-connectivity of the set of all A-dilation Parseval frame wavelets with a frame MRA in L ²(? ^d ) is discussed.     

An Exceptional Set in the Ergodic Theory of Expanding Maps on Manifolds

Under a general hypothesis an expanding map T of a Riemannian manifold M is known to preserve a measure equivalent to the Liouville measure on that manifold. As a consequence of this and Birkhoff’s pointwise ergodic theorem, the orbits of almost all points on the manifold are asymptotically distributed with regard to this Liouville measure. Let T be Lipschitz of class τ for some τ in (0,1], let Ω(x) denote the forward orbit closure of x and for a positive real number δ and let E(x₀, δ) denote the set of points x in M such that the distance from x₀ to Ω is at least δ. Let dim A denote the Hausdorff dimension of the set A. In this paper we prove a result which implies that there is a constant C(T) > 0 such that dimE(x₀,d) 3 dimM - \fracC(T)|logd| \dim E(x_0,\delta) \ge \dim M - \frac{C(T)}{\vert\!\log \delta \vert} if τ = 1 and dimE(x₀,d) 3 dimM - \fracC(T)log|logd|\dim E(x_0,\delta) \ge \dim M - \frac{C(T)}{\log \vert \log \delta \vert} if τ < 1. This gives a quantitative converse to the above asymptotic distribution phenomenon. The result we prove is of sufficient generality that a similar result for expanding hyperbolic rational maps of degree not less than two follows as a special case.     

A weak-type inequality for uniformly bounded trigonometric polynomials

This paper is devoted to refining the Bernstein inequality. Let D be the differentiation operator. The action of the operator Λ = D/n on the set of trigonometric polynomials T _n is studied: the best constant is sought in the inequality between the measures of the sets {x ∈ T: |Λt(x)| > 1} and {x ∈ T: |t(x)| > 1}. We obtain an upper estimate that is order sharp on the set of uniformly bounded trigonometric polynomials T _n ^C = {t ∈ T _n : ‖t‖ ≤ C}.     

Distribution of large values of the argument of the Riemann zeta function on short intervals

An upper bound for the measure of the set of values t ∈ (T,T + H] for H = T ^27/82+ɛ for which |S(t)| ≥ λ is obtained.