{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/34298"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/34298","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Beatty ratios, algorithms related to Sturmian sequences and uniform distribution theory","abstract":"This dissertation is divided into three main sections. The main result of Section 1 is that, for $a,b>1$, irrational, the quantity $\\log (a/b)$ is ``not too far'' from the series of fractional parts $$ \\sum_{n=1}^{\\infty}\\frac{a \\{a^{-1} (n+1)\\}-b\\{b^{-1}(n+1)\\}}{n(n+1)} \\text{,}$$ i.e, the absolute value of the difference of these two quantities is less than one plus a ``small'' constant $k(a,b)$. In order to prove this result, we first study properties of ratios of elements of Beatty sequences and their connection with Sturmian sequences. If we write $a_n=\\lfloor n a \\rfloor$ for $a$ a real number and $n \\in \\N$, then we are concerned with ratios of the form $$r_{a}(n,k):=\\frac{ a_{n+k}}{a_n} $$ \\noindent as well as their reciprocals. These types of quotients have various properties. For example, the $i^{th}$ element of a Sturmian sequence with slope $s:=s(a,b)$ can be defined by a difference of ratios $R(i):=r_{a}(i,1)-r_{b}(i,1)$ for some irrational numbers $a$, $b$, i.e, $R(i)$ is positive or negative depending on whether or not $i$ is an integer in the Sturmian sequence with slope $s$. We also study partial sums of the form \\begin{equation} \\label{thabs1} \\sum_{n\\leq x} \\frac{ a_{n+k}}{a_n} \\end{equation} and find asymptotics for them. Next, we consider the series \\begin{equation*} \\sum_{n=1}^{\\infty} \\left(\\frac{ a_{n+k}}{a_n}-\\frac{ b_{n+k}}{b_n}\\right) \\end{equation*} \\noindent and show that it satisfies an identity involving $\\log a$ and $\\log b$ for the case when $a$ and $b$ are irrationals. This identity bears a superficial resemblance to a discrete analogue of Frullani's integral. The main result of the section is deduced as a corollary from this identity. The identity is proved by using Sturmian sequences to write the sum \\eqref{thabs1} over the positive integers, finding asymptotics for partial sums of elements of the Beatty sequences, and using summation by parts techniques together with some combinatorial arguments. In the second portion of this thesis we present a Minimum Excluded with Skipping (MES) algorithm that generalizes minimum excluded type algorithms. This algorithm has one sequence as input and another sequence as output. We study this algorithm in connection with Beatty, nonhomogeneous Sturmian, and other (not necessarily quasilinear) types of sequences. A complete characterization of this algorithm is presented in the case of an Beatty sequence. The proofs of these theorems use Diophantine approximation, continued fractions and various number theoretic and combinatorial arguments. The third portion of this thesis deals with a topic related to a theorem that begun as a conjecture of Steinhaus. This well known Three Gap Theorem states that there are at most three gap sizes in the sequence of fractional parts $\\{\\alpha n\\}_{n \\sumn=1\\infty\\frac{a \\{a-1 (n+1)\\}-b\\{b-1(n+1)\\}}{n(n+1)} \\text{,}$ i.e, the absolute value of the difference of these two quantities is less than one plus a ``small'' constant $k(a,b)$. In order to prove this result, we first study properties of ratios of elements of Beatty sequences and their connection with Sturmian sequences. If we write $a_n=\\lfloor n a \\rfloor$ for $a$ a real number and $n \\in \\N$, then we are concerned with ratios of the form $ra(n,k):=\\frac{ an+k}{an} $ \\noindent as well as their reciprocals. These types of quotients have various properties. For example, the $i^{th}$ element of a Sturmian sequence with slope $s:=s(a,b)$ can be defined by a difference of ratios $R(i):=r_{a}(i,1)-r_{b}(i,1)$ for some irrational numbers $a$, $b$, i.e, $R(i)$ is positive or negative depending on whether or not $i$ is an integer in the Sturmian sequence with slope $s. We also study partial sums of the form \\begin{equation} \\label{thabs1} \\sumn\\leq x \\frac{ an+k}{an} \\end{equation} and find asymptotics for them. Next, we consider the series \\begin{equation*} \\sumn=1\\infty \\left(\\frac{ an+k}{an}-\\frac{ bn+k}{bn}\\right) \\end{equation*} \\noindent and show that it satisfies an identity involving \\log a$ and $\\log b$ for the case when $a$ and $b$ are irrationals. This identity bears a superficial resemblance to a discrete analogue of Frullani's integral. The main result of the section is deduced as a corollary from this identity. The identity is proved by using Sturmian sequences to write the sum \\eqref{thabs1} over the positive integers, finding asymptotics for partial sums of elements of the Beatty sequences, and using summation by parts techniques together with some combinatorial arguments. In the second portion of this thesis we present a Minimum Excluded with Skipping (MES) algorithm that generalizes minimum excluded type algorithms. This algorithm has one sequence as input and another sequence as output. We study this algorithm in connection with Beatty, nonhomogeneous Sturmian, and other (not necessarily quasilinear) types of sequences. A complete characterization of this algorithm is presented in the case of an Beatty sequence. The proofs of these theorems use Diophantine approximation, continued fractions and various number theoretic and combinatorial arguments. The third portion of this thesis deals with a topic related to a theorem that begun as a conjecture of Steinhaus. This well known Three Gap Theorem states that there are at most three gap sizes in the sequence of fractional parts $\\{\\alpha n\\}_{n<N}$. The main discovery of this section is that if we average over a short interval $[\\gamma,\\gamma+\\eta]$, the distribution becomes continuous. Moreover, this continuous distribution is universal in the sense that it is the same for any $\\gamma$ and any interval around $\\gamma$. Under these circumstances one would expect that the above averaging process would introduce enough randomness in the sequence so that the limiting distribution would be Poissonian. However, we will prove that, surprisingly, this is not the case.","abstract_has_math":true,"creators":["Polanco Encarnacion, Geremias"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Stolarsky, Kenneth B.","Berndt, Bruce C.","Hildebrand, A.J.","Zaharescu, Alexandru"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012-09-18T21:10:08Z","date_published":"2012-09-18T21:10:08Z","updated_at":"2026-07-22T22:25:31Z","subjects":["Beatty Sequence","Sturmian Sequence","characteristic Sequence","Frullani's integral","Steinhaus Theorem","Three Gap Theorem","Kloosterman Sums","Farey Fractions"],"languages":["en"],"rights":["Copyright 2012 Geremias Polanco Encarnacion"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/34298","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Stolarsky, Kenneth B.","Berndt, Bruce C.","Hildebrand, A.J.","Zaharescu, Alexandru"]},{"key":"dc:creator","label":"Author","values":["Polanco Encarnacion, Geremias"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2012-09-18T21:10:08Z","2012-08"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Beatty Sequence","Sturmian Sequence","characteristic Sequence","Frullani's integral","Steinhaus Theorem","Three Gap Theorem","Kloosterman Sums","Farey Fractions"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2012 Geremias Polanco Encarnacion"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/34298"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This dissertation is divided into three main sections. The main result of Section 1 is that, for $a,b>1$, irrational, the quantity $\\log (a/b)$ is ``not too far'' from the series of fractional parts $$ \\sum_{n=1}^{\\infty}\\frac{a \\{a^{-1} (n+1)\\}-b\\{b^{-1}(n+1)\\}}{n(n+1)} \\text{,}$$ i.e, the absolute value of the difference of these two quantities is less than one plus a ``small'' constant $k(a,b)$. In order to prove this result, we first study properties of ratios of elements of Beatty sequences and their connection with Sturmian sequences. If we write $a_n=\\lfloor n a \\rfloor$ for $a$ a real number and $n \\in \\N$, then we are concerned with ratios of the form $$r_{a}(n,k):=\\frac{ a_{n+k}}{a_n} $$ \\noindent as well as their reciprocals. These types of quotients have various properties. For example, the $i^{th}$ element of a Sturmian sequence with slope $s:=s(a,b)$ can be defined by a difference of ratios $R(i):=r_{a}(i,1)-r_{b}(i,1)$ for some irrational numbers $a$, $b$, i.e, $R(i)$ is positive or negative depending on whether or not $i$ is an integer in the Sturmian sequence with slope $s$. We also study partial sums of the form \\begin{equation} \\label{thabs1} \\sum_{n\\leq x} \\frac{ a_{n+k}}{a_n} \\end{equation} and find asymptotics for them. Next, we consider the series \\begin{equation*} \\sum_{n=1}^{\\infty} \\left(\\frac{ a_{n+k}}{a_n}-\\frac{ b_{n+k}}{b_n}\\right) \\end{equation*} \\noindent and show that it satisfies an identity involving $\\log a$ and $\\log b$ for the case when $a$ and $b$ are irrationals. This identity bears a superficial resemblance to a discrete analogue of Frullani's integral. The main result of the section is deduced as a corollary from this identity. The identity is proved by using Sturmian sequences to write the sum \\eqref{thabs1} over the positive integers, finding asymptotics for partial sums of elements of the Beatty sequences, and using summation by parts techniques together with some combinatorial arguments. In the second portion of this thesis we present a Minimum Excluded with Skipping (MES) algorithm that generalizes minimum excluded type algorithms. This algorithm has one sequence as input and another sequence as output. We study this algorithm in connection with Beatty, nonhomogeneous Sturmian, and other (not necessarily quasilinear) types of sequences. A complete characterization of this algorithm is presented in the case of an Beatty sequence. The proofs of these theorems use Diophantine approximation, continued fractions and various number theoretic and combinatorial arguments. The third portion of this thesis deals with a topic related to a theorem that begun as a conjecture of Steinhaus. This well known Three Gap Theorem states that there are at most three gap sizes in the sequence of fractional parts $\\{\\alpha n\\}_{n1$, irrational, the quantity $\\log (a/b)$ is ``not too far'' from the series of fractional parts $$ \\sum_{n=1}^{\\infty}\\frac{a \\{a^{-1} (n+1)\\}-b\\{b^{-1}(n+1)\\}}{n(n+1)} \\text{,}$$ i.e, the absolute value of the difference of these two quantities is less than one plus a ``small'' constant $k(a,b)$. In order to prove this result, we first study properties of ratios of elements of Beatty sequences and their connection with Sturmian sequences. If we write $a_n=\\lfloor n a \\rfloor$ for $a$ a real number and $n \\in \\N$, then we are concerned with ratios of the form $$r_{a}(n,k):=\\frac{ a_{n+k}}{a_n} $$ \\noindent as well as their reciprocals. These types of quotients have various properties. For example, the $i^{th}$ element of a Sturmian sequence with slope $s:=s(a,b)$ can be defined by a difference of ratios $R(i):=r_{a}(i,1)-r_{b}(i,1)$ for some irrational numbers $a$, $b$, i.e, $R(i)$ is positive or negative depending on whether or not $i$ is an integer in the Sturmian sequence with slope $s$. We also study partial sums of the form \\begin{equation} \\label{thabs1} \\sum_{n\\leq x} \\frac{ a_{n+k}}{a_n} \\end{equation} and find asymptotics for them. Next, we consider the series \\begin{equation*} \\sum_{n=1}^{\\infty} \\left(\\frac{ a_{n+k}}{a_n}-\\frac{ b_{n+k}}{b_n}\\right) \\end{equation*} \\noindent and show that it satisfies an identity involving $\\log a$ and $\\log b$ for the case when $a$ and $b$ are irrationals. This identity bears a superficial resemblance to a discrete analogue of Frullani's integral. The main result of the section is deduced as a corollary from this identity. The identity is proved by using Sturmian sequences to write the sum \\eqref{thabs1} over the positive integers, finding asymptotics for partial sums of elements of the Beatty sequences, and using summation by parts techniques together with some combinatorial arguments. In the second portion of this thesis we present a Minimum Excluded with Skipping (MES) algorithm that generalizes minimum excluded type algorithms. This algorithm has one sequence as input and another sequence as output. We study this algorithm in connection with Beatty, nonhomogeneous Sturmian, and other (not necessarily quasilinear) types of sequences. A complete characterization of this algorithm is presented in the case of an Beatty sequence. The proofs of these theorems use Diophantine approximation, continued fractions and various number theoretic and combinatorial arguments. The third portion of this thesis deals with a topic related to a theorem that begun as a conjecture of Steinhaus. This well known Three Gap Theorem states that there are at most three gap sizes in the sequence of fractional parts $\\{\\alpha n\\}_{n