| Digital Archive


Search the Digital Archive

Investigating Computational Aspects of the Coincidence Condition for Substitutions of Pisot Type

Show full item record

Author: Paljug, Brian
Advisor: Day, Sarah, 1975-
Committee Members: Li, Chi-Kwong; Phillips, David; Mao, Weizhen
Issued Date: 2009-05-15
URI: http://hdl.handle.net/10288/1234
Description: We call mappings from an alphabet $\cA=\{a_1,a_2,...,a_d\}$ to the set $\cA^*=\{W=w_1w_2...w_r|r\in\nats,w_i\in\cA\}$ of all finite ordered sequences comprised of letters in $\cA$, \emph{substitutions} over $\cA$. By definition, a substitution $\varphi$ maps $\cA\to\cA^*$, but it can be extended to map $\cA^*\to\cA^*$ by $\varphi(w_1w_2...w_r)=\varphi(w_1)\varphi(w_2)...\varphi(w_r)$. Substitutions have many interesting qualities, and arise in the mathematical fields of geometry, combinatorics, and dynamics, and also in various fields of physical sciences (notably, the study of quasicrystals). There is a still-unproven conjecture in the study of substitutions, known as the \emph{Coincidence Conjecture}. The Coincidence Conjecture states that every substitution that fulfills the criteria for being of \emph{Pisot type} (see Definition \ref{def:pisot} achieves the following combinatorial condition: for every distinct $i,j\in\cA$, there exist integers $k,n$ such that $\varphi^n(i)$ and $\varphi^n(j)$ have the same $k$th letter, and the prefixes of length $k-1$ of $\varphi^n(i)$ and $\varphi^n(j)$ are the same up to the reordering of the letters. This coincidence condition has important implications for the properties of the substitution, and so the Coincidence Conjecture is of particular significance in the study of substitutions. The Coincidence Conjecture has been proven for substitutions defined on two-letter alphabets, but is still open for alphabets of higher order. This paper attempts to do several things. First, it provides a thorough survey of the background of the study of substitutions, providing a good starting reference for further study of literature in this area. It also expands on the background, providing several new results. Finally, it explores several computational aspects of the Coincidence Conjecture that have not been previously investigated, resulting in some interesting new observations.
Degree: Bachelors of Science in Mathematics

Files in this item

Files Size Format View
PaljugBrian2009.pdf 325.7Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record