Skip to main content

Some results on Pell equations and sequence autocorrelations

Resource type
Thesis type
(Thesis) Ph.D.
Date created
Pell equations are Diophantine equations of the form x² − Dy² = 1. For fixed D, all positive solutions are generated by powers of a single solution, known as the fundamental solution. In the first chapter, we introduce the concept of the "gap order" of any integer polynomial f, which concerns the finiteness of ordered tuples (s₀, s₁, · · · , sₙ) with f(sᵢ) | f(sᵢ₊₁) and sₙ/s₀ bounded. We determine the gap order for all integer polynomials, answering a conjecture by Chan-Choi-Lam. The proof of this result partially relies upon bounds for solutions to systems of Pell equations, and the existence of solutions to Pell equations that satisfy certain congruence conditions. In Chapter 2, we explore the multiplicative order g(D) of solutions (x, y) = (s, t) of the Pell equation x² −Dy² = 1, viewed as elements s+t√D of Z[√D]/⟨D⟩. Our main results for this chapter are establishing a method of constructing the solution set for x² − D²ⁿ⁺¹y² = 1 from the fundamental solution of x² − Dy² = 1 for any n ∈ N, and using this to find g(D²ⁿ⁺¹) for sufficiently large n. Afterwards, we focus on Rudin-Shapiro (R-S) sequences and their autocorrelations. Our main result for this chapter is an alternative proof of the order of the maximal aperiodic autocorrelation of R-S sequences originally proven by Allouche, Choi, Denise, Erdélyi, and Saffari, and we extend this to periodic autocorrelations. We also discuss the connection between our main result and the burgeoning field of joint spectral radius theory. In Chapter 4, we present an extension of the main result of the previous chapter and a result on the sum of squares of R-S sequence autocorrelations, proven implicitly by Littlewood and explicitly by Høholdt-Jensen-Justesen. We also establish bounds on the sum of magnitudes of R-S sequence autocorrelations. Finally, we present a conjecture on which autocorrelation is maximal, and we provide evidence for this by proving an analogous result for a function we construct from the autocorrelations.
113 pages.
Copyright statement
Copyright is held by the author(s).
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Choi, Stephen
Member of collection
Download file Size
etd22696.pdf 821.91 KB

Views & downloads - as of June 2023

Views: 11
Downloads: 3