Mathematics of Computation · 2006 · 142 citations · 38 references
We introduce a Fourier-based harmonic analysis for a class of discrete dynamical systems which arise from Iterated Function Systems. Our starting point is the following pair of special features of these systems. (1) We assume that a measurable space <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X"> <mml:semantics> <mml:mi>X</mml:mi> <mml:annotation encoding="application/x-tex">X</mml:annotation> </mml:semantics> </mml:math> </inline-formula> comes with a finite-to-one endomorphism <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r colon upper X right-arrow upper X"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>:</mml:mo> <mml:mi>X</mml:mi> <mml:mo stretchy="false">→</mml:mo> <mml:mi>X</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">r\colon X\rightarrow X</mml:annotation> </mml:semantics> </mml:math> </inline-formula> which is onto but not one-to-one. (2) In the case of affine Iterated Function Systems (IFSs) in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper R Superscript d"> <mml:semantics> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> <mml:annotation encoding="application/x-tex">\mathbb {R}^d</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, this harmonic analysis arises naturally as a spectral duality defined from a given pair of finite subsets <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper B comma upper L"> <mml:semantics> <mml:mrow> <mml:mi>B</mml:mi> <mml:mo>,</mml:mo> <mml:mi>L</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">B, L</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper R Superscript d"> <mml:semantics> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> <mml:annotation encoding="application/x-tex">\mathbb {R}^d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of the same cardinality which generate complex Hadamard matrices. Our harmonic analysis for these iterated function systems (IFS) <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis upper X comma mu right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>X</mml:mi> <mml:mo>,</mml:mo> <mml:mi>μ</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(X, \mu )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is based on a Markov process on certain paths. The probabilities are determined by a weight function <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper W"> <mml:semantics> <mml:mi>W</mml:mi> <mml:annotation encoding="application/x-tex">W</mml:annotation> </mml:semantics> </mml:math> </inline-formula> on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X"> <mml:semantics> <mml:mi>X</mml:mi> <mml:annotation encoding="application/x-tex">X</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. From <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper W"> <mml:semantics> <mml:mi>W</mml:mi> <mml:annotation encoding="application/x-tex">W</mml:annotation> </mml:semantics> </mml:math> </inline-formula> we define a transition operator <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper R Subscript upper W"> <mml:semantics> <mml:msub> <mml:mi>R</mml:mi> <mml:mi>W</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">R_W</mml:annotation> </mml:semantics> </mml:math> </inline-formula> acting on functions on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X"> <mml:semantics> <mml:mi>X</mml:mi> <mml:annotation encoding="application/x-tex">X</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, and a corresponding class <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H"> <mml:semantics> <mml:mi>H</mml:mi> <mml:annotation encoding="application/x-tex">H</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of continuous <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper R Subscript upper W"> <mml:semantics> <mml:msub> <mml:mi>R</mml:mi> <mml:mi>W</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">R_W</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-harmonic functions. The properties of the functions in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H"> <mml:semantics> <mml:mi>H</mml:mi> <mml:annotation encoding="application/x-tex">H</mml:annotation> </mml:semantics> </mml:math> </inline-formula> are analyzed, and they determine the spectral theory of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L squared left-parenthesis mu right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msup> <mml:mi>L</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo stretchy="false">(</mml:mo> <mml:mi>μ</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">L^2(\mu )</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. For affine IFSs we establish orthogonal bases in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L squared left-parenthesis mu right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msup> <mml:mi>L</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo stretchy="false">(</mml:mo> <mml:mi>μ</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">L^2(\mu )</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. These bases are generated by paths with infinite repetition of finite words. We use this in the last section to analyze tiles in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper R Superscript d"> <mml:semantics> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> <mml:annotation encoding="application/x-tex">\mathbb {R}^d</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.
38