Date of Degree
Melvyn B. Nathanson
Discrete Mathematics and Combinatorics | Number Theory
order type, combinatorics on words, Sidon sets, Mian-Chowla, greedy algorithm
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.
Cheng, Yin Choi, "On the Order-Type Complexity of Words, and Greedy Sidon Sets for Linear Forms" (2023). CUNY Academic Works.
This work is embargoed and will be available for download on Saturday, September 30, 2023
Graduate Center users:
To read this work, log in to your GC ILL account and place a thesis request.
See the GC’s lending policies to learn more.