LINEAR RECURRENCE SEQUENCES IN DIOPHANTINE ANALYSIS by ELISA BELLAH A DISSERTATION Presented to the Department of Mathematics and the Division of Graduate Studies of the University of Oregon in partial fulfillment of the requirements for the degree of Doctor of Philosophy June 2022 DISSERTATION APPROVAL PAGE Student: Elisa Bellah Title: Linear Recurrence Sequences in Diophantine Analysis This dissertation has been accepted and approved in partial fulfillment of the requirements for the Doctor of Philosophy degree in the Department of Mathematics by: Shabnam Akhtari Chair Daniel Dugger Core Member Christopher Sinclair Core Member Benjamin Young Core Member Brittany Erickson Institutional Representative and Krista Chronister Vice Provost for Graduate Studies Original approval signatures are on file with the University of Oregon Division of Graduate Studies. Degree awarded June 2022 ii ©c 2022 Elisa Bellah iii DISSERTATION ABSTRACT Elisa Bellah Doctor of Philosophy Department of Mathematics June 2022 Title: Linear Recurrence Sequences in Diophantine Analysis Diophantine analysis is an area of number theory concerned with finding integral solutions to polynomial equations defined over the rationals, or more generally over a number field. In some cases, it is possible to associate a well- behaved recurrence sequence to the solution set of a Diophantine equation, which can be useful in generating explicit results. It is known that the solution set to any norm form equation is naturally associated to a family of linear recurrence sequences. As these sequences have been widely studied, Diophantine problems involving norm forms are well-suited to be studied through their associated sequences. In this dissertation, we use this method to study two such problems. iv CURRICULUM VITAE NAME OF AUTHOR: Elisa Bellah GRADUATE AND UNDERGRADUATE SCHOOLS ATTENDED: University of Oregon, Eugene, OR Portland State University, Portland, OR DEGREES AWARDED: Doctor of Philosophy, Mathematics, 2022, University of Oregon Master of Science, Mathematics, 2017, University of Oregon Bachelor of Science, Mathematics, 2015, Portland State University AREAS OF SPECIAL INTEREST: Number Theory Diophantine Analysis PROFESSIONAL EXPERIENCE: Graduate Employee, University of Oregon, 2015-2022 GRANTS, AWARDS AND HONORS: Anderson Distinguished Graduate Teaching Award, Department of Mathematics, University of Oregon, 2020 PUBLICATIONS: Bellah, E. (2021). Norm Form Equations and Linear Divisibility Sequences. International Journal of Number Theory. v ACKNOWLEDGEMENTS First and foremost, I would like to thank my advisor, Shabnam Akhtari, for all of her support and guidance over the years. I would also like to thank my WiN group leaders, Elena Fuchs and Damaris Schindler, for their advice and support, and for coming up with a fun project to keep me motivated through the last stages of my program. Many thanks as well to my friends and fellow graduate students who supported me throughout the program, and to the community at AYE for keeping me sane through this process and reminding me what’s important. Finally a special thank you to my sister, to whom I owe everything. vi TABLE OF CONTENTS Chapter Page I. INTRODUCTION AND BACKGROUND . . . . . . . . . . . . . . . . 1 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Background on Norm Form Equations . . . . . . . . . . . . . . 3 1.3. Background on Linear Recurrence Sequences . . . . . . . . . . 8 1.4. Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 II. NORM FORM EQUATIONS AND LDS . . . . . . . . . . . . . . . . . 14 2.1. Coordinate Sequences . . . . . . . . . . . . . . . . . . . . . . . 16 2.2. Norm Form Equations over Real Quadratic Fields . . . . . . . 22 2.3. Norm Form Equations over Quartic Fields . . . . . . . . . . . 24 2.4. Powers of Algebraic Integers . . . . . . . . . . . . . . . . . . . 37 III. INDEX FORM EQUATIONS OVER BIQUADRATIC FIELDS . . . . 43 3.1. Background on Index Form Equations . . . . . . . . . . . . . . 44 3.2. Reduction to Simultaneous Norm Form Equations . . . . . . . 50 3.3. Near Squares in Linear Recurrence Sequences . . . . . . . . . . 55 REFERENCES CITED . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 vii CHAPTER I INTRODUCTION AND BACKGROUND 1.1. Motivation Diophantine analysis is an area of number theory concerned with finding integral solutions to Diophantine equations; that is, equations of the form F (x1, . . . , xn) = 0, where F is a polynomial defined over the rationals, or more generally over a number field. Given such a Diophantine equation, typical problems include (1) determining the existence of solutions, (2) studying their distribution, and (3) giving explicit descriptions of the solution set and its arithmetic properties. Possibly the most famous Diophantine problem is on the existence of solutions to the Fermat equation xn + yn = zn (1.1.1) where n is some fixed positive integer. Conjectured by Fermat in the 17th century, and then only recently proven in the 1990s, it is now known that there are no positive integer solutions to (1.1.1) when n ≥ 3. The solution set in the remaining nontrivial case, when n = 2, make up the Pythagorean triples. It is classically known that there are infinitely many Pythagorean triples, opening up further Diophantine problems. Explicit problems on the distribution of Pythagorean triples (as in [3] and [21]) and their arithmetic properties (as in [25] and [31]) have been widely studied. It is often the case that explicit Diophantine results such as 1 these lead to applications in cryptography and information security (see [18] for applications of Pythagorean triples in cryptography, for example). In some cases, it is possible to associate a well behaved recurrence sequence to the solution set of a Diophantine equation. This strategy can be useful in generating explicit Diophantine results. One example of this is the use of Elliptic Divisibility Sequences, defined below, to study integer points on elliptic curves defined over Q; for example, integer solutions to the cubic equation y2 = x3 + ax+ b. (1.1.2) By Siegel’s theorem, we know that there are only finitely many integer solutions to (1.1.2) (see Chapter 9 of [27], for example). However little is known about the structure of the solution set. In [34], Ward showed that rational points on elliptic curves are associated to the terms of the nonlinear recurrence sequence {hn} satisfying hm+nh 2 m−n = hm+1hm−1hn − h h h2n+1 n−1 n. (1.1.3) More precisely, Ward showed that for any rational point P on an elliptic curve (1.1.2), we have an x(nP ) = , h2n for some integer sequence {an} and x(nP ) denoting the x-coordinate of the point obtained from adding P to itself n times using the usual group law on elliptic curves. The sequence {hn} is called an Elliptic Divisibility Sequence (EDS) and has several nice arithmetic properties as outlined in [34]. In particular, {hn} satisfies the divisibility property given in Definition 1.3.3 of Section 1.3. This association has led to several Diophantine results. For example, Hindry and Silverman studied 2 bounds on the number of integral multiples of points on elliptic curves in [16]. More recently, work has been done to bound the size of the largest n so that nP is integral. In [17] Ingram found a uniform bound on n by studying the sequence of valuations of an EDS, which was later improved by Stange in [30]. In this dissertation, we focus on Diophantine problems coming from norm form equations, which we discuss in detail in the next section. It is known that all rational reducible forms are integrally equivalent to a constant multiple of a product of norm forms (see Theorem 2 in Section 2.1 of [7], for example). Furthermore, as we’ll see in Chapter II, the solution set to any norm form equation is naturally associated to a family of linear recurrence sequences. As these sequences have been widely studied, Diophantine problems involving norm forms are well-suited to be studied through their associated linear recurrence sequences. In this dissertation, we use this method to study two such problems. In the following sections, we provide the background on norm form equations and linear recurrence sequences used throughout this manuscript, and conclude the chapter with an outline of this dissertation. 1.2. Background on Norm Form Equations Let K be a number field, and W = {w1, . . . , wn} a Q-linearly independent subset of K. The norm form associated to the set W is given by FW (X1, . . . , Xn) := NK(X1w1 + · · ·+Xnwn). (1.2.4) 3 Note that FW is in fact a rational form. To see this, let σ1, . . . , σn denote the embeddings σi : K ↪→ C fixing Q. By definition, ∏n FW (X1, . . . , Xn) = (X1σi(w1) + · · ·+Xnσi(wn)). i=1 So FW is homogeneous of degree n. Now, let σ̃j be an element in Gal(K̃/Q) extending σj, where K̃ denotes the Galois closure of K. If we act on FW by any σ̃j, we have ∏n σ̃jFW (X1, . . . , Xn) = (X1σ̃jσi(w1) + · · ·+Xnσ̃jσi(wn)), i=1 which only reindexes our product. So, σ̃jFW = FW for each j, implying our coefficients must be rational. Given a norm form FW , it then is a classical Diophantine problem to ask for integer solutions to equations of the form FW (X1, . . . , Xn) = c, (1.2.5) where c is a fixed nonzero integer. We consider two simple examples. √ Example. Let D be a nonsquare integer. If we let W = {1, D}, then the √ corresponding norm form defined over Q( D) is FW (X, Y ) = X2 − DY 2. In this case, we see that (1.2.5) is a Pell-type equation. Example. If W is an integral basis for a number field K, the set of solutions to (1.2.5) with c = ±1 gives a complete list of units in K. So, the problem of finding units in a number field can be interpreted as such a Diophantine problem. 4 Given a Q-linearly independent set W , let M be the Z-module in K generated by W . Observe that if T is another basis for M , the norm forms FW and FT , which are defined in (1.2.4), are integrally equivalent. That is, there exist (aij) ∈ GLn(Z) so that if ∑n Yi = aijXj, j=1 then we have FW (X1, . . . , Xn) = FT (Y1, . . . , Yn). So, integer solutions to (1.2.5) can be found by instead studying the elements in the associated module M of fixed norm c. The characterization of solutions to (1.2.5) depends on whether or not the associated module M is full in K (that is, whether rankM = [K : Q]). Characterization in the case that M is full. Let OM := {α ∈ K | αM ⊆M} denote the coefficient ring of the module M . It is known that when M is full in K, the coefficient ring OM is an order in K (see Theorem 3 in Section 2.2 of [7], for example), and furthermore that M contains only a finite number of nonassociate elements of fixed norm c (see the Corollary to Theorem 5 in Section 2.2 of [7], for example). So, the set of elements in M of fixed norm c can be written as a disjoint union of finitely many families α1 U+M , . . . , α U + ` M , where U+M := {ε ∈ OM | NK(ε) = 1} (1.2.6) denotes the positive unit group of M . 5 Characterization in the case that M is not full. While the characterization in the full case is well-known, the characterization in the nonfull case was more recently provided by Schmidt in [23] and [24]. We give an overview of these results below. For each subfield L of K, let ML := {α ∈M | ∀λ ∈ L, ∃z ∈ Z6=0 so that zλα ∈M}, and observe that ML is a submodule of M . As above, we let OML denote the coefficient ring of ML, and U+L the units in OML of positive norm. In [23],M Schmidt showed that OML is an order in L, and furthermore that the solutions to (1.2.5) are contained in finitely many families of the form µU+L ,M for some µ ∈ K and subfields L ⊂ K. The methods in [23] do not give an explicit method to construct all such families, but the following Lemma tells us when these families are finite. Lemma 1.2.1 (Section 5 of [23]). ML is nonzero if and only if ML contains a submodule of the form αN , where N is full in L and α ∈ K. We call M nondegenerate when ML = {0} for every subfield L of K that is not rational or imaginary quadratic. By Lemma 1.2.1 and Dirichlet’s unit theorem, there are only finitely many solutions to (1.2.5) in the nondegenerate case. In [24], Schmidt provided explicit upper bounds on the number of these solutions. We state this result below. 6 Theorem 1.2.2 (Theorem 1 of [24]). Suppose that FW is a norm form with associated module M that is nondegenerate. Then, the number of solutions to (1.2.5) is upper bounded by 30n min(r2 , rc2(n)), n+4 where c2(n) = (2n) n2 and r = [K : Q]. The results of Chapter II will focus on studying the arithmetic of the solutions to (1.2.5) obtained from families of the form αU+M where U+M is the positive unit group of an order in a number field not equal to the rationals or an imaginary quadratic, as in the full and degenerate cases. By Dirichlet’s unit theorem, U+M is a finitely generated abelian group with positive rank. So, for any nontorsion element ε of U+M , we can generate an infinite sequence of elements in M of fixed norm c given by α(k) = βεk, where k ∈ Z≥0. So, if we write α(k) = x1(k)w1 + · · ·+ xn(k)wn, (1.2.7) then we obtain infinitely many solutions (x1(k), . . . , xn(k)) to (1.2.5). Furthermore, the characterization above implies that all infinite families of solutions to (1.2.5) are obtained in this way. In Chapter II we study the arithmetic of the sequences {xi(k) : k ∈ Z≥0}, which are known to satisfy a linear recurrence relation. 7 1.3. Background on Linear Recurrence Sequences An integer sequence {b(k) : k ∈ Z≥0} is said to be a linear recurrence sequence (LRS) if it satisfies a homogeneous linear recurrence b(k + d) = s1b(k + d− 1) + · · ·+ sdb(k), (1.3.8) for si ∈ Z and d ∈ Z≥0. We say that b(k) has order d if (1.3.8) is minimal. The characteristic polynomial of b(k) is given by f(X) = Xd − s Xd−11 − · · · − sd, and the roots of f are the characteristic roots of b(k). When b(k) has order d, f(X) is called the minimal polynomial of b(k). For a linear recurrence sequence b(k) of order d, we call b(0), . . . , b(d − 1) its initial conditions. The following result tells us how to construct explicit formulas for linear recurrence sequences. Proposition 1.3.1 (Chapter 1 of [9], for example). Let b(k) be a LRS of order d with characteristic roots α1, . . . , αm and write the minimal polynomial of b(k) as ∏m f(X) = (X − α )nii . i=1 Then, there exists polynomials Ai(X) ∈ Q[X] of degree ni − 1 so that ∑m b(k) = A (k)αki i . i=1 As suggested in Proposition 1.3.1, linear recurrence sequences are known to grow exponentially. Since we will only consider sequences that are nondegenerate 8 with distinct characteristic roots we state the result on growth of these special families below. Note that similar results hold for more general families of linear recurrence sequences. Proposition 1.3.2 (Theorem 2.3 of [9]). Let b(k) be a LRS with distinct characteristic roots αi so that αi/αj is not a root of unity for any i 6= j. Suppose that α1 has maximal absolute value. Then, there is a constant A ∈ R and for all ε > 0 there is a constant k0 = k0(ε) so that |α|(1−ε)k ≤ |b(k)| ≤ A|α|k, for all k ≥ k0. While it is challenging to obtain arithmetic results on linear recurrence sequences in general (see Section 6.1 of [9] for a survey of such results), it has been found to be more tractable to study the arithmetic of sequences with the following divisibility property. Definition 1.3.3. A linear recurrence sequence b(k) is a linear divisibility sequence (LDS) if b(k) has the following property: for all n,m ∈ Z>0, n | m⇒ b(n) | b(m). For example, the fact that Lucas sequences, which we discuss below, are divisibility sequences was used in [6] to study their primitive divisors, and in [29] to study their index divisibility sets, as well as in many other results throughout the literature. Elliptic Divisibility Sequences, discussed in Section 1.1, are examples of 9 nonlinear divisibility sequences. Similar results for these sequences have also been found, such as in [28] and [32]. The characterization in Proposition 1.3.7 below shows that Lucas sequences are fundamental in studying linear divisibility sequence. We first give some background on these sequences. Let P,Q be nonzero coprime integers. The Lucas sequence with integer parameters (P,Q) is defined to be the order 2 linear recurrence sequence uk = uk(P,Q) with initial values u0 = 0, u1 = 1, and recurrence uk+2 = Puk+1 −Quk. For example, the Fibonacci sequence is the Lucas sequence with integer parameters (1,−1). Let θ, θ̄ be roots of the polynomial X2 − PX + Q. Using Proposition 1.3.1 and the initial conditions of un we can write θk − θ̄k uk = . θ − θ̄ Note that Lucas sequences are sometimes defined by the parameters (θ, θ̄), rather than the integer parameters (P,Q). Lemma 1.3.4. Every Lucas sequence is a LDS. Proof. Let P,Q be nonzero coprime integers, and consider the matrix  P −QA =  . 1 0 10 Observe that for any positive integer k, we have  uk k+1 −Quk A =  , uk −Quk−1 where uk is the Lucas sequence with integer parameters (P,Q). Now, take any positive integers m,n. Then we have  n   u −Qu ∗ ∗ Amn  m+1 m  ≡  =  (modum). um −Qum−1 0 ∗ On the other hand, we have   u −Qu mn  mn+1 mnA =  . umn −Qumn−1 Comparing the lower left hand entries, we see that um | umn for every m,n ∈ Z>0. So, uk is a LDS. Characterization of Linear Divisibility Sequences. Determining precisely which linear recurrence sequences are linear divisibility sequences is an open problem. We give a survey of some of the current characterizations below. Note that an order one linear recurrence sequence b(k) with initial condition b(0) = c takes the form b(k) = cak. So, every nonzero order one linear recurrence sequence is a linear divisibility sequence. In order two, we have the following. Proposition 1.3.5 (Theorem 1 of [15]). Let b(k) be an order two linear recurrence sequence. Then b(k) is a linear divisibility sequence if and only if b(0) = 0. 11 Using Proposition 1.3.1, we obtain that the only linear divisibility sequences in order two are of the form c · uk or c · kαk−1, where uk is a Lucas sequence, and α, c ∈ Z6=0. The order three case was studied by Hall in [14]. The main result of this paper is as follows. Proposition 1.3.6 (Theorem 4 of [14]). Let b(k) be a linear recurrence sequence of order three with b(0) = 0 and characteristic polynomial f(X) = X3 − s1X2 − s2X − s3. If f(X) is an irreducible cubic with gcd(s2, s3) = 1, then b(k) is not a linear divisibility sequence. It is conjectured that the only order three linear recurrence sequences b(k) with b(0) = 0 that are linear divisibility sequences are of the form c · k2αk−1, c · kuk, or c · u2k, where uk is a Lucas sequence, and c, α ∈ Z6=0 (see Section 3.4 of [5], for example). For higher order sequences, little explicit information is known. The best known result in this direction tells us that the terms of a linear divisibility sequence must at least divide a product which generalizes the the conjectured order three characterization. Proposition 1.3.7 (Section 1.3 of [5]). Let b(k) be a linear divisibility sequence with b(0) = 0. Then, there exists αi, βi ∈ C and nonzero integers c, ` so that if we 12 write ∏( )k k a(k) := c · ` αi − βk i αi − βi i then we have b(k) | a(k) for all k ∈ Z≥0. 1.4. Organization This dissertation is organized as follows. In Chapter II we show that for certain families of quartic norm form equations, there exists integrally equivalent forms making any one of coordinate sequences defined in (1.2.7) a linear divisibility sequence. The results in this chapter provide new families of order 4 linear divisibility sequences, as well as some further arithmetic structure to the solution set of certain quartic norm form equations. In Chapter III we discuss how to translate the question of monogeniety of a number field to a Diophantine problem through the use of index forms. We then discuss ongoing work to use the methods from a paper of Gaál, Pethö and Pohst to obtain explicit information about monogenizers in certain families of biquadratic fields by studying near squares in an associated order two linear recurrence sequence. 13 CHAPTER II NORM FORM EQUATIONS AND LINEAR DIVISIBILITY SEQUENCES In this chapter, we show that for certain families of norm form equations defined over quartic fields, we can find an integrally equivalent forms so that one of the sequences {xi(k) : k ∈ Z≥0} defined in (1.2.7) is a linear divisibility sequence. The families we consider are motivated by the following theorem of Kubota. Proposition 2.0.1 (Theorem 1 of [19]). Let K be a real biquadratic field with quadratic subfields Li, and let εi be a fundamental unit of Li. Then, K has a system of fundamental units of one of the following forms, up to relabeling: (i) ε1, ε2, ε3 √ (ii) ε1, ε2, ε3 √ √ (iii) ε1, ε2, ε3 √ (iv) ε1ε2, ε3, ε3 √ √ (v) ε1ε2, ε3, ε2 √ √ √ (vi) ε1ε2, ε2ε3, ε3ε1 √ (vii) ε1ε2ε3, ε2, ε3 √ (viii) ε1ε2ε3, ε2, ε3, with NK (εi) = −1 for i = 1, 2, 3,i √ where ε denotes any element η ∈ K with η2 = ε, and the εi in cases (i) to (vii) appearing under a radical have NL (εi) = 1. Furthermore, there are infinitely manyi K of each type. 14 Proposition 2.0.1 tells us that to study solutions to a norm form equation FW (X1, X2, X3, X4) = c defined over a real biquadratic field, it suffices to understand the coordinates of the sequences α(k) = βηk where η is of one of the following three types: (a) η is a unit in quadratic subfield of K, (b) η2 is a unit in a quadratic subfield of K, or (c) η is a product of units of types (a) and (b) Our main results concern the sequences α(k) = βηk where η is type (b). In fact, our results hold for quartic fields containing a unit of type (b) more generally. We will show the following. Theorem 2.0.2. Let K be a quartic field with a real quadratic subfield L containing a quartic unit η of positive norm, so that η2 is a unit in L. Fix a nonzero element β ∈ K, and write α(k) = βηk. Then, there is a choice of basis W = {w1, w ′2, w3, w4} for the module M = β Z[η], which we construct explicitly, so that if we write α(k) = x1(k)w1 + · · ·+ x4(k)w4 then {x1(k) : k ∈ Z≥0} is a LDS. √ √ Theorem 2.0.3. Let M = Z[ m, m+ 1], where m and m + 1 are non-square √ √ integers. Then, η = m + m+ 1 is a unit in the positive unit group U+M with η2 a unit in a quadratic subfield of K = Q(η), and there is a choice of basis W = 15 {w1, w2, w3, w4} for the module M , which we construct explicitly, so that if we write ηk = x1(k)w1 + · · ·+ x4(k)w4, then {x1(k) : k ∈ Z≥0} is a LDS. Remark 2.0.4. Note that Theorems 2.0.2 and 2.0.3 hold for the sequence {xi(k) : k ∈ Z≥0} for any fixed i ∈ {1, 2, 3, 4}, just by changing the basis to reindex our coordinates. However, we show in Sections 2.2 and 2.3 that there does not exist a choice of basis for the modules M ′ and M in Theorems 2.0.2 and 2.0.3 so that the coordinate sequences x1(k), x2(k), x3(k), x4(k) defined in (1.2.7) are LDS simultaneously. This chapter is organized as follows. In Section 2.1, we show that the sequences {xi(k) : k ∈ Z≥0} defined in (1.2.7) are linear recurrence sequences, each with characteristic polynomial equal to the minimal polynomial of our unit ε. In Section 2.2, we discuss how to use Lucas sequences to study norm forms defined over real quadratic fields. In Section 2.3, we prove Theorems 2.0.2 and 2.0.3. In Section 2.4, we discuss a related sequence proposed by Silverman in [26], and provide examples where Conjecture 9 of this paper holds. 2.1. Coordinate Sequences Let M be a full module in a number field K, and ε a nontorsion element in the positive unit group U+M defined in (1.2.6). For β ∈ M with NK(β) = c, set 16 α(k) = βεk. If we choose a basis W = {w1, . . . , wn} for M , and write α(k) = x1(k)w1 + · · ·+ xn(k)wn, (2.1.1) then we obtain tuples of solutions (x1(k), . . . , xn(k)) to the corresponding norm form equation FW (X1, . . . , Xn) = c. Definition 2.1.1. We call the integer sequences {xi(k) : k ∈ Z≥0}, where xi(k) is defined in (2.1.1), the coordinate sequences of α(k) with respect to our choice of basis W . In this section, we show that the coordinate sequences {xi(k) : k ∈ Z≥0} have characteristic polynomial equal to the minimal polynomial of ε. We also provide sufficient conditions so that the minimal polynomial of the coordinate sequence {xi(k) : k ∈ Z≥0} is equal to the minimal polynomial of ε. Proposition 2.1.2. Let K be a number field, and take γ ∈ K and θ ∈ OK . Consider the sequence x(k) = Tr kK/Q(γθ ). (a) The sequence x(k) satisfies a linear recurrence with characteristic polynomial equal to the minimal polynomial of θ. (b) Let L = Q(θ). If TrK/L(γ) =6 0, then the minimal polynomial of the sequence x(k) is equal to the minimal polynomial of θ. Remark 2.1.3. Suppose that θ has minimal polynomial f(X) = Xd − s1Xd−1 − · · · − sd, 17 for si ∈ Z. Then, Proposition 2.1.2(a) implies that the sequence x(k) = Tr (γθkK/Q ) satisfies the recurrence x(k + d) = s1x(k + d− 1) + · · ·+ sdx(k). However, it is possible that this recurrence is not minimal. For example, take √ √ √ K = Q( 2, 3, 5), √ √ √ θ = 2 + 3 and γ = 5. Then, Proposition 2.1.2 (a) implies that x(k) satisfies an order 4 recurrence, but we can check that x(k) = 0 for k = 0, 1, 2, 3. So, x(k) is a constant sequence, while deg θ = 4. There does not appear to be a complete characterization for when the sequence x(k) is exactly of order deg θ in the current literature, so Proposition 2.1.2 (b) gives a new result in this direction. We note that Proposition 2.1.2 (a) follows from known results on generalized power sums (see Chapter 1 of [9], for example), but we provide a more elementary proof below. Proof of Proposition 2.1.2. Let n = [K : Q] and σi : K ↪→ C be the n distinct embeddings fixing Q. Set γi := σi(γ) and θi := σi(θ), for i ∈ {1, . . . , n}. Then, we can write ∑n x(k) = Tr k kK/Q(γθ ) = γiθi . (2.1.2) i=1 Let f(X) = Xd − s Xd−11 − · · · − sd 18 be the minimal polynomial of θ over Q. Since θ ∈ OK we have si ∈ Z. Then, ∑d ∑d ∑n s x(k + d− j) = s γ θk+d−jj j i i by (2.1.2) j=1 ∑j=1 i=1n ∑d = γ θk s θd−ji i j i ∑i=1 j=1n = γ k diθi θi , i=1 where the final equality follows beca∑use each θi is a root of f(X). So, our sequence satisfies the recurrence x(k + d) = dj=1 sjx(k + d − j), which has characteristic polynomial equal to f(X), which proves part (a). Next, suppose that x(k) satisfies an order m recurrence for 0 < m ≤ d, say ∑m x(k +m) = rjx(k +m− j), j=1 where rj ∈ Z. Then, we have ∑m Tr (γθk+m) = r Tr (γθk+m−jK/Q j K/Q ), j=1 and by linearity of the trace, we get Tr kK/Q(Cθ · γ) = 0, where ∑m C = θm − r θm−ii . i=1 Order the embeddings so that σ1(θ) = θ1, . . . , σd(θ) = θd are distinct, and σi(θ) = σdm+i(θ) 19 for m = 1, 2, . . . , `. Then, Tr kK/Q(Cθ · γ) = σ1(Cθk) (σ1(γ) + σd+1(γ) + · · ·+ σ`d+1(γ)) + σ (Cθk2 ) (σ2(γ) + σd+2(γ) + · · ·+ σ`d+2(γ)) ... ( ) + σd(Cθ k) σd(γ) + σ2d(γ) + · · ·+ σ(`+1)d(γ) where n = (`+ 1)d. For i = 1, . . . , d. Set Si = σi(γ) + σd+i(γ) + · · ·+ σ`d+i(γ). Then, we can write      σ1(Cθ 0) · · · σd(Cθ0)   . . . .. . . ..  S1   0  ...   = ... , (2.1.3) σ (Cθd−1) · · · σ (Cθd−11 d ) Sd 0 Without loss of generality, suppose that σ1(θ) = θ. Then, S1 = TrK/L(γ), where L = Q(θ). If C 6= 0 then the set {C,Cθ, . . . , Cθd−1} would be Q-linearly independent, and we would have    σ1(Cθ 0) · · · σ (Cθ0n )   . det . . . .. .  = disc(C,Cθ, . . . , Cθd−1 1/2. . ) 6= 0. σ (Cθd−1) · · · σ (Cθd−11 d ) 20 But this contradicts (2.1.3), since S1 6= 0 by assumption. So, we must have C = 0, and so θ is a root of ∑m Xm − r m−iiX ∈ Z[X] i=1 But since θ is degree d, and m ≤ d we get m = d. Hence, the recurrence ∑d x(k + d) = sjx(k + d− j) j=1 is minimal, and so f(X) is the minimal polynomial of the sequence x(k). We have the following Corollary to Proposition 2.1.2. Corollary 2.1.4. Let K be a number field and M a full module in K. Suppose that ε is a nontorsion element in U+M . For a fixed nonzero β ∈M , let α(k) = βεk and {xi(k) : k ∈ Z≥0} be a coordinate sequence of α(k) with respect to some basis, as defined in (2.1.1). Then, {xi(k) : k ∈ Z≥0} is a linear recurrence sequence with characteristic polynomial equal to the minimal polynomial of ε. Furthermore, if deg ε = [K : Q] then the minimal polynomial of this sequence is equal to the minimal polynomial of ε. Proof. Let W = {w1, . . . , wn} be any basis for M , and write α(k) = x1(k)w1 + · · ·+ xn(k)wn. Since M is a full module, W is a Q-basis for K. So, there exists a dual basis W ∗ = {w∗1, . . . , w∗n} to W with respect to the trace pairing. That is, W ∗ is a basis for K, 21 and we have Tr ∗K/Q(wiwj) = δij for all i, j, where 1 if i = j δij = 0 if i 6= j. Let γ = w∗i β. Then we have xi(k) = Tr k K/Q(γε ). Note that if deg ε = [K : Q] then Q(ε) = K. So TrKQ(ε)(γ) = γ 6= 0. Hence, the result follows from Proposition 2.1.2 (b). 2.2. Norm Form Equations over Real Quadratic Fields Suppose that K is a real quadratic field, and let M be a full module in K. For any β ∈M and ε a nontorsion element in U+M , let α(k) = βεk as before. Since ε is degree 2 over Q, Corollary 2.1.4 implies that the coordinate sequences of α(k) are order 2 linear recurrence sequences. Such sequences have been well-studied, and so Corollary 2.1.4 implies some immediate consequences. Proposition 2.2.1. Let K be a real quadratic field and M a full module in K. Fix a nonzero element β ∈ M and write α(k) = βεk. Then, there is a choice of basis 22 W = {w1, w2} for M , which we construct explicitly, so that if we write α(k) = x1(k)w1 + x2(k)w2 then the sequence x1(k) is a LDS. Recall from Proposition 1.3.5 of Chapter I that order two linear divisibility sequences must initialize at zero. So, given α(k) as in Proposition 2.2.1, it is not possible to find a basis for M so that x1(k) and x2(k) are LDS simultaneously. Proof of Proposition 2.2.1. By Proposition 1.3.5, it suffices to find a basis {w1, w2} for M so that x1(0) = 0. Let {t1, t2} be any basis for M , and B be the matrix given by     β  = Bt1 . βε t2 Note that ∃C ∈ GL2(Z) so that BC is lower triangular. So, we can define a new basis {v1, v2} from {t1, t2} by change of basis matrix C−1. Then,      β  a11 0 v1=    , (2.2.4) βε a21 a22 v2 for some aij ∈ Z. Now, let W = {w1, w2} be the basis defined by     w1 1 1v1=    . w2 1 0 v2 23 We claim that we can take W as our desired basis. To see this, observe that       0 a11 w1 a11 0 v1=  . a22 a21 − a22 w2 a21 a22 v2 So, if we write α(k) = x1(k)w1 + x2(k)w2 then by (2.2.4) x1(k) has initial conditions x1(0) = 0 and x1(1) = a22. So, x1(k) = a22uk, where uk is the Lucas sequence with parameters (ε, ε̄). By Corollay 2.1.4 we know that x1(k) is an order 2 recurrence sequence, and so we must have a22 6= 0. Hence, x1(k) is a LDS. 2.3. Norm Form Equations over Quartic Fields Let K be a quartic field, and M a full module in K. Choose an element β in M , and suppose there exists a unit η ∈ U+M of degree 4 over Q. By Corollary 2.1.4, the coordinate sequences of α(k) = βηk are order 4 linear recurrence sequences. Unlike in the order 2 case, much less is known about higher-order linear recurrence sequences, and so it is generally quite challenging to determine when an arbitrary order 4 linear recurrence sequence is a LDS. Suppose that η is a quartic unit with η2 =: ε a unit in a quadratic subfield of Q(η). Recall, by Proposition 2.0.1, this is one of the three cases needed to understand solutions to norm forms over real biquadratic fields. Let K̃ be the Galois closure of K. Observe that for σ ∈ Gal(K̃/Q) we have σ(ε) = σ(η)2. So, the conjugates of η are of the form √ √ ± ε,± ε̄, (2.3.5) 24 where ε̄ denotes the conjugate of ε. Since η is of degree 4 over Q, it has minimal polynomial f(X) = X4 − (ε+ ε̄)X2 + 1. (2.3.6) So, Corollary 2.1.4 implies that the coordinate sequences x(k) of α(k) are order 4 linear recurrence sequences satisfying x(k + 4) = Tx(k + 2)− x(k), (2.3.7) where T = ε + ε̄. The following Proposition gives sufficient initial conditions for x(k) to be a LDS, and will be used to prove our main results. Proposition 2.3.1. Let x(k) be an order 4 linear recurrence sequence with initial conditions x(0) = 0, x(1) = x(2) = a, x(3) = a(T + 1), and recurrence x(k + 4) = Tx(k + 2)− x(k), where a and T are nonzero integers. Then, x(k) is a LDS. Proof. Note that it suffices prove our claim for a = 1. Let uk denote the Lucas sequence with integer parameters (T, 1). Since we assumed that x(0) = 0 and x(2) = 1, we have x(2n) = un for every n ∈ Z≥0. Consider the matrix    T −1 A =  . 1 0 25 Recall from the proof of Lemma 1.3.4 that we have the identity n   un+1 −un   A =  , (2.3.8) un −un−1 and so we have  x(2n+ 2) −x(2n)n A =  , (2.3.9) x(2n) −x(2n− 2) for every n ∈ Z>0. Using the recurrence for x(k), we observe that    x(3)An  = x(2n+ 3) . (2.3.10) x(1) x(2n+ 1) Combining (2.3.9) and (2.3.10) yields    x(2n+ 3) x(3)x(2n+ 2)− x(1)x(2n)=  . x(2n+ 1) x(3)x(2n)− x(1)x(2n− 2) That is, we have x(2n+ 1) = x(3)x(2n)− x(1)x(2(n− 1)) for any positive integer n. Recalling that x(1) = 1, x(3) = T + 1 and x(2n) = un, we obtain x(2n+ 1) = (T + 1)un − un−1 = un+1 + un, where the final equality follows by using the recurrence for uk. So, we have  x(k) = un, if k = 2n (2.3.11)un+1 + un, if k = 2n+ 1, 26 for any k ∈ Z≥0. Note that we need to show x(k) | x(k`) for every k, ` ∈ Z≥0. Suppose that k = 2n. Then, x(k) = un and x(k`) = un`. So, by Lemma 1.3.4 we have x(k) | x(k`). Next, suppose that k = 2n + 1 and ` = 2m. Noting that A2n = (An)2, and using identity (2.3.8) we have    2u2n+1 −u2n  un+1 −un =  . u2n −u2n−1 un −un−1 After squaring the matrix on the right, we compare the upper left-hand entries to get the identity u 2 22n+1 = un+1 − un. So, we have x(2k) x(2(2n+ 1)) = x(k) x(2n+ 1) u2n+1 = un+1 + un = un+1 − un ∈ Z. Hence, x(k) | x(2k), and by the previous case we have x(2k) | x(2km)⇒ x(k) | x(k`). Now, suppose that k = 2n + 1 and ` = 2m + 1. Let ε, ε̄ denote the roots of X2 − TX + 1. Recall from Section 1.3 we can write εk − ε̄k uk = , ε− ε̄ 27 for every k ∈ Z≥0. So, we have x(2n+ 1) = un+1 + un εn+1 − ε̄n+1 εn − ε̄n = + ε− ε̄ ε− ε̄ εn(ε+ 1)− ε̄n(ε̄+ 1) = ε− ε̄ 1 εn(ε+ 1)− (1 + ε) = ε n+1 ε− ε̄ ε+ 1 2n+1 = · ε − 1 . ε− ε̄ εn+1 This gives x((2n+ 1)(2m+ 1)) x(2(2nm+ n+m) + 1) = x(2n+ 1) x(2n+ 1) ε2(2nm+n+m)+1 − 1 εn+1 = · ε2nm+n+m+1 ε2n+1 − 1 ε(2n+1)(2m+1) − 1 = · 1 . ε2n+1 − 1 εm(2n+1) To see this value is in Z, let α = ε2n+1. Then, from above we obtain x((2n+ 1)(2m+ 1)) α2m+1 − 1 = · 1 x(2n+ 1) α− 1 αm α2m + α2m−1 + · · ·+ α + 1 = αm = (αm + α−m) + · · ·+ (α + α−1) + 1. Since α = ε2n+1 and NK(ε) = 1, then α and α −1 are quadratic conjugates. So, we have αt + α−t ∈ Z for every t = 1, . . . ,m. Hence, x(2n+ 1) | x((2n+ 1)(2m+ 1)), 28 and so x(k) is a LDS. Theorem 2.0.2 will now follow from Proposition 2.1.2. Recall that K is a quartic number field containing a quartic unit η of positive norm so that η2 is a unit in a quadratic subfield of K. Proof of Theorem 2.0.2. Note that the module M ′ = βZ[η] has basis {β, βη, βη2, βη3}. Define the set W = {w1, w2, w3, w4} by      0 0 1 0  w1 1 0 0 1 w   β  βη2 = ,  1 0 0 0w3  2βη ︸ T + 1 ︷︷1 0 0 ︸ w4 βη3 A where T = ε + ε̄. Note that A ∈ GL4(Z), and so W is a basis for M . Since η has minimal polynomial f(X) = X4 − TX2 + 1, then by Corollary 2.1.4 we know that the sequence x1(k) is an order 4 linear recurrence sequence satisfying (2.3.7). Moreover, if we write α(k) = βεk in terms of the basis W , then x1(0) = 0, x1(1) = x1(2) = 1, and x1(3) = T + 1. So, by Proposition 2.3.1, x1(k) is a LDS. 29 In the following Corollary, we provide explicit formulas for the coordinate sequences of α(k), with respect to the basis constructed in Theorem 2.0.2, in terms of Lucas sequences. Corollary 2.3.2. Let W = {w1, w2, w3, w4} be the basis for the module βZ[η] constructed in Theorem 2.0.2, and α(k) = βηk be as above. If we write α(k) = x1(k)w1 + · · ·+ x4(k)w4, then for any integer k ≥ 3 we have u if k = 2n  n 0 if k = 2nx1(k) =  x2(k) = un+1 + u n if k = 2n+ 1, un if k = 2n+ 1,   −un−1 if k = 2n 0 if k = 2nx3(k) =  x4(k) = 0 if k = 2n+ 1, −un−1 if k = 2n+ 1, where un is the Lucas sequence with parameters (ε, ε̄), defined in Section 2.1. Proof. Recall, by Corollary 2.1.4 we know that all of the coordinate sequences xi(k) of α(k) satisfy the order 4 recurrence xi(k + 4) = Txi(k + 2)− xi(k), (2.3.12) where T = ε + ε̄, and by construction of our basis W these sequences have initial conditions 30 k x1(k) x2(k) x3(k) x4(k) 0 0 0 1 0 1 1 0 0 1 2 1 0 0 0 3 T + 1 1 0 0 From (2.3.11) in the proof of Proposition 2.3.1 we see that x1(k) satisfies the desired formula. Next, let yi(n) = xi(2n + 1) for i = 2, 4 and y3(n) = x3(2n). By (2.3.12) we have that yi(n) satisfies the order 2 recurrence yi(n+ 2) = Tyi(n+ 1)− yi(n). Since y2(0) = 0 and y2(1) = 1 we get x2(2n+ 1) = y2(n) = un for all n ≥ 0, where un is the Lucas sequence with integer parameters (T, 1). Since y3(1) = 0 and y3(2) = −1 we have x3(2n) = y3(n) = −un−1 for all n ≥ 1. Similarly, since y4(1) = 0 and y4(2) = −1 we have x4(2n+ 1) = y4(n) = −un−1 for all n ≥ 1. 31 Remark 2.3.3. Let M be an arbitrary full module in our quartic field K and let α(k) = βηk as above. Note that M ′ = βZ[η] is a finite index submodule of M containing α(k) for every k ∈ Z≥0. So, we can always write the coordinate sequences for α(k) in terms of the basis constructed in Theorem 2.0.2. It turns out to be more challenging to apply Proposition 2.3.1 to find a basis for the entire module M . The following Proposition provides sufficient conditions for when this can be done. First, we set some notation. For a basis {t1, t2, t3, t4} of M , write     β  t1    βη t 2= B . (2.3.13) 2  βη t3 βη3 t4 Writing B in Smith normal form, we know that there exists X, Y ∈ GL4(Z) so that XBY = diag(δ1, . . . , δ4) (2.3.14) with δ1 | · · · | δ4. Let X = (xij). Then, we have the following. Proposition 2.3.4. If there exists a matrix X ∈ GL4(Z) satisfying (2.3.14) and ( ) δ4 gcd χ4, = 1, δ1 where χi = xi2 + xi3 + (T + 1)xi4, and T = ε + ε̄, then there is a choice of basis W for the module M so that the coordinate sequence x1(k) of α(k) with respect to the basis W satisfies the initial conditions of Proposition 2.3.1. 32 Proof. Suppose that we have a basis W = {w1, w2, w3, w4} for M as above. Set ( )> ( )> w~ = w1 · · · w4 and ~t = t1 · · · t4 . Then, Aw~ = B~t, where B is defined in (2.3.13) and A is a matrix with first column ( )> 0 a a a(T + 1) . Let X be any matrix satisfying (2.3.14), which we know exists by writing B is Smith normal form. Write D = diag(δ1, . . . , δ4). Observe that gcd(χ1, . . . , χ4) = 1, since if there were a prime p dividing every χi, then we would have          q1 p · ...    = 0 · x11 .. .    + x12    x13 x14  . . .. + .. + (T + 1)    . ..  , q4 x41 x42 x43 x44 where qi ∈ Z. But then the columns of X would be (Z/p)-linearly dependent, which contradicts the fact that X ∈ GL4(Z). Now, let ( )> ~c1 = δ4χ δ4χ δ41 2 χ3 χδ δ δ 4 . 1 2 3 It is known that any lattice element can be extended to a basis precisely when it is primitive (see Chapter 1 of [8], for example). Since δ1 | · · · | δ4, and we’ve assumed that gcd(χ4, δ4/δ1) = 1, then we have ( ) δ4 δ4 δ3 gcd χ1, χ2, χ3, χ4 = 1. δ1 δ2 δ2 33 So, there is a matrix C ∈ GL4(Z) with first column equal to ~c1. Next, let A = X−1DC. Then, A has first column ( )> ~a1 = 0 δ4 δ4 δ4(T + 1) . Furthermore, D−1XA = C ∈ GL4(Z). Let Z = Y D−1XA ∈ GL4(Z), and define a new basis W = {w1, w2, w3, w4} from {t1, t2, t3, t4} by change of basis matrix Z−1. Since Z = B−1A, we have    w1 .    β .  A .. =  ..  . w4 βη 3 So, if we write α(k) = x1(k)w1 + · · · + x4(k)w4, then x1(k) satisfies the initial conditions x1(0) = 0, x1(1) = x1(2) = δ4, x1(3) = δ4(T + 1). Theorem 2.0.3 provides a family of modules satisfying the conditions of Proposition 2.3.4. An interesting future direction could be to provide a characterization of all such modules. √ √ √ √ Proof of Theorem 2.0.3. Recall that M = Z[ √ √m, m+ 1], and η = m + m+ 1.√ √ Observe tha√t η = ε, where ε = 2m+ 1 + 2 m(m+ 1). Let K = Q( m, m+ 1), and L = Q( m(m+ 1)). A short computation shows that NL(ε) = 1 and η ∈ U+M . Next, observe that      1 1 0 0 0 1          √ η  0 1 1 0 m  =η2 2m+ 1 0 0 2   √  . √ m+ 1  η3 ︸ 0 4m+︷︷3 4m+ 1 0 ︸ m(m+ 1) B 34 We can compute XBY = diag(1, 1,−2, 2) where     1 0 0 0 1 0 0 00 1 0 0    0 1 −1 0 X =   , and Y =   . 0 −4m− 3 0 1 0 0 1 0 −2m− 1 0 1 0 0 0 0 1 Hence, χ4 = 1 and so Proposition 2.3.4 applies. That is, there is a basis W so that the coordinate sequence x1(k) of α(k) with respect to the basis W satisfies the initial conditions of Proposition 2.3.1. So, x1(k) is a LDS. Remark 2.3.5. Note that the proof of Proposition 2.3.4 provides an algorithm for computing our desired basis in Theorem 2.0.3 explicitly. We demonstrate this computation. Note that TrL/Q(ε) = 4m+ 2. Recall that we need to find a matrix C = D−1XA in GL4(Z) with first column being a primitive vector and A ∈Mat4(Z) with first column ( )> ~a = 0 a a a(4m+ 3) . We compute the first column of C to be ( )> ~c1 = 0 a 0 a/2 . 35 So, we choose a = 2 and the rest of the entries of C so that C ∈ GL4(Z). For example, we can take   0 1 0 0 2 0 1 0   C = . 0 0 0 1 1 0 0 0 Then, we compute A = X−1DC, where D = diag(1, 1,−2, 2), to get    0 1 0 0  2 0 1 0  A =   . 2 2m+ 1 0 0  8m+ 6 0 4m+ 3 −2 So, setting Z = √B−1A, and using Z−1 as our change of basis matrix from√ √ {1, m, m+ 1, m(m+ 1)} we obtain basis W = {w1, w2, w3, w4} for M given by √ √ √ w1 = m, w2 = 2 + m+ 1− m(m+ 1), √ w3 = m(m+ 1), w4 = 1. So, if we write ηk = x1(k)w1 + · · · + x4(k)w4, we can check that x1(k) satisfies the initial conditions x1(0) = 0, x1(1) = x1(2) = 2, x1(3) = 2(4m + 3), and so by Proposition 2.3.1 we have that x1(k) is a LDS. Remark 2.3.6. If α(k) is as in Theorems 2.0.2 and 2.0.3, the coordinate sequences {xi(k) : k ∈ Z≥0} contain order two subsequences {xi(2k) : k ∈ Z≥0}. By Proposition 1.3.5 in Chapter I, an order two linear recurrence sequence must 36 initialize at zero. So, it is not possible to find a basis for the corresponding module that makes x1(k), x2(k), x3(k), x4(k) LDS simultaneously. 2.4. Powers of Algebraic Integers We conclude this chapter by discussing a related sequence studied by Silverman in [26], and show how methods from the previous sections might be used in its analysis. Given α ∈ Z̄, define the sequence dk(α) = max{d ∈ Z | αk ≡ 1(mod d)}. (2.4.15) where the congruence αk ≡ 1(mod d) means that there is an element β ∈ Z̄ with αk = 1 + dβ. In [26], Silverman proved that dk(α) is a divisibility sequence, and showed that, except for some exceptional cases, this sequence grows slower than exponentially. We record this Theorem below. Theorem 2.4.1 (Theorem 1 of [26]). Let α ∈ Z̄. Then, log dn(α) lim = 0 n→∞ n unless α` ∈ Z for some ` ∈ Z, or α` is a unit in a quadratic extension of Q. √ In the exceptional case where α is an element of Z[ D] for a nonsquare integer D ≥ 2, and NK(α) = 1, it is shown in Theorem 7 of [26] that dk := dk(α) 37 satisfies the order 4 linear recurrence dk+4 = Tdk+2 − dk, (2.4.16) where T = α + ᾱ. Let η be an algebraic number of degree 4 with η2 quadratic. Choose an integral basis {w1, w2, w3, w4} for L = Q(η), and write ηk = x1(k)w1 + · · ·+ x4(k)w4. (2.4.17) Then, by Corollary 2.1.4 we have that the xi(k) also satisfy the order 4 linear recurrence xi(k + 4) = Txi(k + 2)− xi(k). (2.4.18) We have the following observation. √ Proposition 2.4.2. Let α be a nontorsion unit of positive norm in Z[ D] for a nonsquare integer D ≥ 2, and let η be any algebraic integer satisfying η2 = α. Let L = Q(η). If OL = Z[η], then there exists a choice of basis for OL so that dk(α) if d 1 (α) = 1 x1(k) = dk(α)/d1(α) if d1(α) 6= 1, where dk(α) and x1(k) are defined as in (2.4.15) and (2.4.17), respectively. Proof. By (2.4.16) and (2.4.18), we know that x1(k) and dk(α) both satisfy the same recurrence. So, it suffices to find a basis for OL so that the initial conditions 38 of x1(k) match those of dk(α). Let ( )> ~a = d0 d1 d2 d3 . If d1(α) = 1, then ~a is a primitive lattice element in Z4 and so there exists A ∈ GL4(Z) with first column ~a. Let {w1, w2, w3, w4} be the basis obtained from √ √ { 2 √ 3 1, α, α , α } by change of basis matrix A−1. Then x1(k) has the desired initial conditions. If d1(α) 6= 1, then we replace the sequence dk(α) by dk(α)/d1(α) in the argument above. Remark 2.4.3. Since the coordinate sequence {xi(k) : k ∈ Z } of βk≥0 for any β ∈ Z̄ defined in (2.4.17) are linear recurrence sequences with distinct characteristic roots, then by Proposition 1.3.2 they grow exponentially. So Theorem 2.4.1 implies that if xi(k) = dk(α) for some α ∈ Z̄ and fixed index i, then α must be in one of the exceptional cases. That is, we must have a power of α either in Z or a quadratic unit. It would be interesting to know when a result like Proposition 2.4.2 holds in the other exceptional cases. We finish this section by discussing how the recurrence for the coordinate sequences {xi(k) : k ∈ Z≥0} of αk, for some α ∈ Z̄, could be used to study the sequence dk(α) defined in (2.4.15). By definition, we have that dk(α) is the largest positive integer satisfying αk − 1 ∈ dk(α)OK . (2.4.19) Let {1, w2, . . . , wn} be an integral basis for K. If we write αk = x1(k) + x2(k)w2 + · · ·+ xn(k)wn. 39 Then we have dk(α) = gcd(x1(k)− 1, x2(k), . . . , xn(k)). (2.4.20) Furthermore, by Corollary 2.1.4 each of the sequences xi(k) has characteristic polynomial equal to the minimal polynomial of α. As in the previous sections, we can change the initial conditions of xi(k) by changing the basis of OK . We use these observations to study the following conjecture. Conjecture 2.4.4 (Conjecture 9 of [26]). For α ∈ Z̄, suppose one of the following holds: (a) [Q(αr) : Q] ≥ 3 for all r ≥ 1, or (b) [Q(αr) : Q] ≥ 2 for all r ≥ 1 and NK(α) 6= ±1. Then, the set {k ≥ 1 | dk(α) = d1(α)} is infinite. The following proposition can be used to construct examples where Conjecture 2.4.4 holds. Proposition 2.4.5. Let α ∈ Z̄ have minimal polynomial f(X) = Xn − s Xn−11 − · · · − sn, and set K = Q(α). If there exists a positive divisor t > 1 of n so that si = 0 ∀i ∈6 tZ, then we have dk(α) ≤ |OK/Z[α]| for all k ∈ 1 + tZ. In particular, if OK = Z[α], then dk(α) = d1(α) = 1 for all k ∈ 1 + tZ. Proof. Let ∆ = |OK/Z[α]|, and d̃k denote the largest integer with αk − ∈ d̃k1 Z[α]. ∆ 40 Since O ⊂ 1K Z[α], then by (2.4.19) we have∆ αk − ∈ O ⊂ dk1 dk K Z[α]. ∆ So, dk ≤ d̃k. Next, write αk = y1(k) + y2(k)α + · · ·+ yn(k)αn−1. Then, similar to (2.4.20) we observe that d̃k = ∆ gcd(y1(k)− 1, y2(k), . . . , yn(k)). If si = 0 ∀i 6∈ tZ, then by Corollary 2.1.4 we have y1(k + n) = sty1(k + n− t) + · · ·+ s`tyi(k + n− `t). Since y1(k) has initial conditions y1(0) = 1, y1(1) = · · · = y1(n− 1) = 0, we see that y1(1 + `t) = 0 for any ` ∈ Z≥0. So, dk ≤ d̃k = ∆. We give an example to demonstrate how to use Proposition 2.4.5 to generate examples where Conjecture 2.4.4 holds. Example 2.4.6. Let α be an algebraic number of degree 4 so that β := α2 is quadratic. Observe that the minimal polynomial of α is of the form f(X) = X4 − Tr 2L/Q(β)X +NL/Q(β), 41 where L = Q(β), and so by Proposition 2.4.5 we have that dk(α) ≤ |OK/Z[α]| whenever k is odd. So, Conjecture 2.4.4 holds whenever OK = Z[α] where K = Q(α). (2.4.21) Number fields K satisfying (2.4.21) are called monogenic, and elements α satisfying (2.4.21) are called monogenizers of K. We searched for elements α as in Example 2.4.6 that are monogenizers of K = Q(α). Using Sage to check whether OK = Z[α], we searched the first five real quadratic fields (ordered by discriminant), and found the following list of examples: √ √ √ √ √ √ √ √ √ √ 2 + 2, 1 + 3, 1(5 + 5), 1 + 6, 1 + 7. 2 It would be interesting to provide a characterization of all monogenic quartic fields with generator of the form α where α2 is contained in a quadratic subfield, as this would provide a family of examples where Conjecture 2.4.4 holds for the sequence dk(α) and could improve the results of Section 2.3. In the following chapter, we study the monogenizers of certain biquadratic fields through their associated index forms. 42 CHAPTER III INDEX FORM EQUATIONS OVER BIQUADRATIC FIELDS Let K be a number field and O an order in K. That is, O is a Z-module in K of rank [K : Q] that is also a ring with unity. We call O monogenic if there exists an element α ∈ O with O = Z[α]. In this case we call α a monogenizer of O. Note that if α is a monogenizer of O, so is α ± c for any integer c. We define the equivalence α ∼ β ⇔ α± β ∈ Z (3.0.1) and call each equivalence class a monogenization of O. It is well-known that every order is contained in the ring of integers OK of K, and so we will say that K is monogenic whenever OK is, and that α is a monogenizer of K when α is a monogenizer of OK . In Remark 2.3.3 and Example 2.4.6, we saw that the results of Chapter II could be improved when our quartic field K has monogenizer α with α2 contained in a quadratic subfield of K. √ √ A biquadratic field is a quartic field of the form Q( m, n) where m and n are distinct nonsquare integers. In [11], Gaál, Pethö and Pohst give a method to algorithmically search for monogenizers of certain biquadratic fields, which we expect will lead to further theoretical results. In this chapter, we give an exposition of the methods outlined in [11]. Our main contribution is a rewriting of this algorithmic paper in order to motivate further theoretical results. This chapter is organized as follows. In Section 3.1 we give some background on index form equations, which translate the question of monogeneity of a number field K to a Diophantine problem. In Section 3.2 we use the results of [11] to 43 reduce this Diophantine problem to solving a system of norm form equations. In Section 3.3 we outline how the authors of [11] associate the monogenizers of a biquadratic field to near squares of an associated linear recurrence sequence. We then discuss ongoing work to use this result to obtain bounds on the height of monogenizers in biquadratic fields. 3.1. Background on Index Form Equations Let K be a number field and α an element of OK . Note that Z[α] is finite index in OK when degα = [K : Q], and that α is a monogenizer precisely when the index is equal to 1. We use this observation to translate the problem of finding monogenizers of K to a Diophantine problem. Let σi be the distinct embeddings of K ↪→ C fixing Q. For any m-tuple of elements α1, . . . , αm in K, the discriminant of α1, . . . , αm is defined to be the quantity DK(α1, . . . , αm) := det(σi(αj)) 2. For an element α ∈ K of degree m, the discriminant of α is given by DK(α) := DK(1, α, . . . , α m−1). Let {1, w1, . . . , wn} be an integral basis for K so that [K : Q] = n + 1. For an element α ∈ OK of degree [K : Q] write α = x0 + x1w1 + · · ·+ xnwn, (3.1.2) 44 with xi ∈ Z. Let σ0, . . . , σn be the distinct embeddings K ↪→ C fixing Q, and suppose that σ0 is the identity embedding. We have  21 α · · · α n    1 σ1(α) · · · σ1(α)n DK(α) = det .. .. . . ...  . . . .  1 σn(α) · · · σn(α)n This is a Vandermonde determinant, and so we get ∏ DK(α) = (σi(α)− σj(α))2. 0≤i