#### Title

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

#### Date Thesis Awarded

5-2009

#### Document Type

Honors Thesis

#### Degree Name

Bachelors of Science (BS)

#### Department

Mathematics

#### Advisor

Sarah Day

#### Committee Member

Chi-Kwong Li

#### Committee Member

David Phillips

#### Committee Member

Weizhen Mao

#### Abstract

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.

#### Recommended Citation

Paljug, Brian, "Investigating Computational Aspects of the Coincidence Condition for Substitutions of Pisot Type" (2009). *Undergraduate Honors Theses.* Paper 312.

http://publish.wm.edu/honorstheses/312

#### Creative Commons License

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

## Comments

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