Dissertations, Theses, and Capstone Projects

Date of Degree

9-2023

Document Type

Dissertation

Degree Name

Ph.D.

Program

Mathematics

Advisor

Kevin O'Bryant

Committee Members

Melvyn B. Nathanson

Cormac O’Sullivan

Subject Categories

Discrete Mathematics and Combinatorics | Number Theory

Keywords

order type, combinatorics on words, Sidon sets, Mian-Chowla, greedy algorithm

Abstract

This work consists of two parts. In the first part, we study the order-type complexity of right-infinite words over a finite alphabet, which is defined to be the order types of the set of shifts of said words in lexicographical order. The set of shifts of any aperiodic morphic words whose first letter in the purely-morphic pre-image occurs at least twice in the pre-image has the same order type as Q ∩ (0, 1), Q ∩ (0, 1], or Q ∩ [0, 1). This includes all aperiodic purely-morphic binary words. The order types of uniform-morphic ternary words were also studied, and the properties of their corresponding morphisms when the order type is an ordinal are examined. The set of shifts of the characteristic word of slope α for an irrational α has the same order type as Q ∩ (0, 1), independent of α. We also show how to decide the order between two distinct shifts of a characteristic word of irrational slope by examining the α-Ostrowski expansions of the indices of the shifts.

In the second part, we consider a generalization of the greedy Sidon set, also known as the Mian-Chowla sequence. The greedy Sidon set is the lexicographically first set in N that does not contain x1, x2, y1, y2 with x1 + x2 = y1 + y2. Its growth and structure have remained enigmatic for 80 years. We generalize the form x1 + x2 to arbitrary linear forms c1x1 + · · · + chxh; these are called Sidon sets for linear forms. We explicitly describe the elements of the greedy Sidon sets for linear forms when ci = n i−1 for some n ≥ 2, and also when h = 2, c1 = 2, c2 ≥ 4, the “structured” domain. We also contrast the “enigmatic” domain when h = 2, c1 = 2, c2 = 3 with the “structured” domain, and give upper bounds on the growth rates in both cases. Finally, we study the case when h = 2, c1 = m, c2 > 2m for m ≥ 3 and examine another boundary between the “structured” and “enigmatic” domains.

Download

Share

COinS