Date Thesis Awarded


Document Type

Honors Thesis

Degree Name

Bachelors of Science (BS)




Sarah Day

Committee Member

Chi-Kwong Li

Committee Member

David Phillips

Committee Member

Weizhen Mao


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.

Creative Commons License

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.


Thesis is part of Honors ETD pilot project, 2008-2013. Migrated from Dspace in 2016.