2-Adic Valuations of Quadratic Sequences

Will Boultinghouse Kentucky Wesleyan College

Division of Natural Sciences and Mathematics 3000 Frederica Street Owensboro, KY 42301

USA

Jane Long

Stephen F. Austin State University Department of Mathematics and Statistics

Nacogdoches, TX 75962-3040 USA

Olena Kozhushkina

Ursinus College

Department of Mathematics and Computer Science

Collegeville, PA 19426 USA

Justin Trulen^{1} Kentucky Wesleyan College

Division of Natural Sciences and Mathematics 3000 Frederica Street Owensboro, KY 42301

USA

jtrulen@kwc.edu

Abstract

We determine properties of the 2-adic valuation sequences for general quadratic polynomials with integer coefficients directly from the coefficients. These properties include boundedness or unboundedness, periodicity, and valuations at terminating nodes.

1Corresponding author.

We completely describe the periodic sequences in the bounded case. Throughout, we frame results in terms of trees and sequences.

1 Introduction

For p prime and n ∈ ℕ = {0, 1, 2, 3, …}, the exponent of the highest power of p that divides n is called the p-adic valuation of n, which we denote ν_{p}(n). The valuation of 0 is defined to be +∞. Formally, the valuation of a positive integer n of the form n = p^{k}d, where k ∈ ℕ and d is an integer not divisible by p, is ν_{p}(n) = k. We can find p-adic valuations of sequences by finding the valuation of each successive term. The present work considers 2-adic valuations of sequences generated from the natural numbers by evaluating quadratic functions of the form f(n) = an^{2} + bn + c where a, b, c ∈ ℤ and a ≠ 0.

Information about sequences of valuations can be viewed in two different ways: in terms of sequences and in terms of trees. We let (ν_{2}(f(n)))_{n≥0} denote the sequence of 2-adic valuations for the quadratic function f(n). Since every positive natural number n can be written in the form n = 2^{k}d, where d is not divisible by 2, in many cases, we can determine the valuations of outputs of the quadratic function f(n) using characteristics of the coefficients a, b, and c. The main results are given in Theorems 1 and 2; one would anticipate these results can be extended to odd primes with some modifications, which will be addressed in future work.

Theorem 1. Let f(n) = an^{2} + bn + c where a, b, c ∈ ℤ with a ≠ 0 and, without loss of generality, a, b, c are not all even. Then

1. If a and b are even and c is odd, then ν_{2}(f(n)) = 0 for all n ∈ ℕ.

2. If a is even and b is odd, then (ν_{2}(f(n)))_{n≥0} is an unbounded sequence.

3. If a is odd and b is even, then

(a) if b^{2} − 4ac = 0, then (ν_{2}(f(n)))_{n≥0} is an unbounded sequence;

(b) if b^{2} − 4ac = 4^{ℓ}Δ for ℓ ∈ ℤ^{+} as large as possible and Δ ≡ 1 (mod 8), then (ν_{2}(f(n)))_{n≥0} is an unbounded sequence;

(c) if b^{2} − 4ac = 4^{ℓ}Δ for ℓ ∈ ℤ^{+} as large as possible, Δ ≡ m (mod 8), and m ∈ {2, 3, 5, 6, 7}, then the sequence (ν_{2}(f(n)))_{n≥0} is bounded and its minimal period length equals 2^{ℓ}.

4. If a and b are odd and c is even, then (ν_{2}(f(n)))_{n≥0} is an unbounded sequence.

5. If a, b, and c are odd, then ν_{2}(f(n)) = 0 for all n ∈ ℕ.

Theorem 1 is proved in Section 3. Henceforward, we will refer to the minimal period length simply as the period. In Case 3, we use the discriminant to determine whether roots to f(n) = 0 lie in the 2-adic numbers ℚ_{2} or the ring of 2-adic integers ℤ_{2}. Corollary 10 takes care of Case 3(a). Even though the statement of this theorem only classifies these sequences as unbounded, the proofs of Cases 2 and 4 reveal more information about the 2adic valuations. Theorem 1 represents a complete answer to when ν_{2}(f(n))_{n≥0} is bounded or unbounded using only the coefficients of the quadratic polynomial. Furthermore, Theorem 1 gives an explicit period length for the bounded sequences which can be determined by the coefficients of the quadratic polynomial. In the unbounded cases we are able to describe what possible valuations will be for certain subsequences. Such statements are easier to frame in the sense of trees, which are discussed in Section 2. Theorem 2, proved in Sections 4 and 5, completely determines all valuations in the non-trivial bounded case (3(c) of Theorem 1).

Theorem 2. Let f(n) = an^{2}+bn+c where a, b, c ∈ ℤ. If a is odd and b is even and b^{2}−4ac = 4^{ℓ}Δ for ℓ ∈ ℤ^{+} as large as possible with ℓ ≥ 2, Δ ≡ m (mod 8), and m ∈ {2, 3, 5, 6, 7}, then the sequence (ν_{2}(f(n)))_{n≥0} is bounded with period equal to 2^{ℓ}. Furthermore, we have the following 2-adic valuations:

ν_{2}(f(n)) = \begin{cases}0, & if n ≡ a^{−1} (1 − \frac{b}{2}) (mod 2); \\ 2(i − 1), & if n ≡ a^{−1} (2^{i−1} − \frac{b}{2}) (mod 2^{i}) with 2 ≤ i < ℓ; \\ 2(ℓ − 1), & if n ≡ a^{−1} (2^{ℓ−1} − \frac{b}{2}) (mod 2^{ℓ}) and m = 6, 2; \\ 2ℓ − 1, & if n ≡ a^{−1} (2^{ℓ−1} − \frac{b}{2}) (mod 2^{ℓ}) and m = 7, 3; \\ 2ℓ, & if n ≡ a^{−1} (2^{ℓ−1} − \frac{b}{2}) (mod 2^{ℓ}) and m = 5; \\ 2ℓ − 1, & if n ≡ a^{−1} (2^{ℓ} − \frac{b}{2}) (mod 2^{ℓ}) and m = 6, 2; \\ 2(ℓ − 1), & if n ≡ a^{−1} (2^{ℓ} − \frac{b}{2}) (mod 2^{ℓ}) and m = 7, 5, 3; \end{cases}

where a^{−1} is the inverse of a (mod 2^{ℓ}).

The case ℓ = 1 is covered by Lemma 13. In this case, the sequence is periodic with period equal to 2. Theorem 2 is proved in Proposition 12 and Corollary 24. Both of these results are an extension of the work by Byrnes et al. [3], which only considered quadratics of the form f(n) = an^{2} + c. The work of Medina et al. [6] details conditions under which these sequences are bounded or unbounded for general primes but we extend these results for p = 2 by providing the exact conditions on the coefficients of quadratic equations. Furthermore, we provide a closed form giving the exact valuation for the bounded sequences relying only on the coefficients of the quadratic function. Boundedness of p-adic valuations of polynomial sequences is also discussed in Bell’s work [2].

2 Parity and trees

Consider a quadratic function of the form f(n) = an^{2} + bn + c, where a, b and c are integers and a is nonzero. To prove the results stated in Theorems 1 and 2, we consider the eight possible cases based on the parity of the coefficients a, b, and c. In the case where a, b, and c are all even, there exists an i ∈ ℕ such that 2^{i} divides a, b, and c but 2^{i+1} does not. Then

ν_{2}(f(n)) ν_{2}(f(2q + 1)) \begin{matrix}ν_{2}(f(4q + 3)) \\ ν_{2}(f(4q + 1)) \end{matrix} ν_{2}(f(2q)) \begin{matrix}ν_{2}(f(4q + 2)) \\ ν_{2}(f(4q)) \end{matrix} 2q + 1 2q 4q + 3 4q + 1 4q + 2 4q

Figure 1: Levels 0, 1, and 2 of a tree.

f(n) = 2^{i}(a_{0}n^{2} + b_{0}n + c_{0}) and it follows that ν_{2}(f(n)) = i + ν_{2}(a_{0}n^{2} + b_{0}n + c_{0}). Hence, this case can be reduced to one of the other seven cases. So we assume, unless stated otherwise, that a, b, and c are not all even.

Two more cases of Theorem 1 are trivial (Case 1 where a, b are even, and Case 5, where a, b, and c are odd), since ν_{2}(f(n)) = 0 for all n ∈ ℕ. For the remaining five cases, we classify the behavior using trees. In the case that a is odd and b is even we show, with the help of the discriminant, that f(n) = 0 has a root in ℚ_{2}. We must take some care since some quadratics may not have a zero in ℚ_{2}.

As discussed in Section 1, we can present information about the sequence of valuations using a tree. We begin the construction of the tree with the top node representing the valuation of the quadratic f(n) evaluated at any natural number n. If the 2-adic valuation is constant for every n in this node, then we stop the construction, as ν_{2}(n) is completely determined for the sequence. If ν_{2}(n) is not constant, this node splits into two branches, where one branch represents all numbers of the form n = 2q and the other branch represents all numbers of the form n = 2q + 1, where in both cases q ∈ ℕ. We then repeat this step as necessary to create the tree. The nodes correspond to the sets {2^{i}q + r_{i−1}|q ∈ ℕ} where

r_{i−1} = ∑_{k=0}^{i−1} α_{k}2^{k},  (1)

for fixed coefficients α_{k} ∈ {0, 1}. This process does not always terminate. If it terminates, we say that the tree is finite; otherwise, the tree is infinite. We say a node is non-terminating if (ν_{2}(f(n)))_{n≥0} is non-constant for every n in that equivalence class. We say a node is terminating if (ν_{2}(f(n)))_{n≥0} is constant for every n in that equivalence class. In practice, we label the node with this constant valuation.

4

For each of the remaining five nontrivial cases on the parity of the coefficients a, b and c, either (ν_{2}(f(n)))_{n≥0} produces a finite tree or an infinite tree. We say a finite tree has ℓ levels if there exists ℓ ∈ ℤ^{+} such that for all r_{ℓ−1} ∈ {0, 1, 2, …, 2^{ℓ}−1} we have (ν_{2}(f(2^{ℓ}q+r_{ℓ−1})))_{q≥0} constant for all q ∈ ℕ, and ℓ is the smallest possible value. Every node at level ℓ in a finite tree has a constant valuation, which depends on r_{ℓ−1}.

Each node of a tree represents a subsequence of the sequence of 2-adic valuations. A finite tree of ℓ levels represents a sequence with period equal to 2^{ℓ}.

In the literature, these finite trees are also called finite automata. The sequences generated via the 2-adic valuation are called 2-automatic sequences and, in particular, the sequences f(2^{i}q + r) are known as the 2-kernel sequences. See Allouche and Shallit’s book [1] and Bell’s paper [2] for more details.

2.1 2-adic numbers and selected lemmas

First, we state several well-known lemmas. The first is a well-established fact about the p-adic valuation, which can also be defined on the set ℚ and extends to ℚ_{2}; see Lemma 3.3.2 in [5].

Lemma 3. Let x, y ∈ ℚ, then ν_{p}(xy) = ν_{p}(x) + ν_{p}(y).

An element n in ℚ_{2} can be represented in the form

n = ∑_{i=k}^{∞} α_{i}2^{i}  (2)

where k = −ν_{2}(n) and α_{i} ∈ {0, 1} for all i; it is well-known that this representation is unique.

Lemma 3 and the construction of ℚ_{2} are well-known [5]. Medina et al. [6] provide a useful characterization of the sequence of 2-adic valuations of a polynomial. Before we state the result, we recall the following characterization of the ring of 2-adic integers

ℤ_{2} = {n ∈ ℚ_{2} : n = ∑_{i=0}^{∞} α_{i}2^{i} where α_{i} ∈ {0, 1}} .

Lemma 4. ([6], Theorem 2.1) Let f(n) ∈ ℤ[n] be a polynomial that is irreducible over ℤ. Then (ν_{2}(f(n)))_{n≥0} is either periodic or unbounded. Moreover, (ν_{2}(f(n)))_{n≥0} is periodic if and only if f(n) has no zeros in ℤ_{2}. In the periodic case, the minimal period length is a power of 2.

We assume that the quadratic f(n) is irreducible because, if not, by Lemma 3,

ν_{p}(f(n)) = ν_{p}(g(n) · h(n)) = ν_{p}(g(n)) + ν_{p}(h(n)),

where g(n) and h(n) are irreducible.

Therefore, to determine whether (ν_{2}(f(n)))_{n≥0} is periodic or unbounded, it suffices to determine if f(n) has zeros in ℚ_{2} and then determine whether the zeros are also in ℤ_{2}. The following lemmas will be used in Section 3 to identify when the square root of a number is in ℤ_{2}. The version of Hensel’s lemma stated below determines when a polynomial in ℤ_{2}[x] has zeros in ℤ_{2}. Lemma 6, which follows from Lemma 5, specifically determines whether the polynomial f(x) = x^{2} − a has zeros in ℤ_{2}.

Lemma 5. (Hensel’s lemma, [7, Sec. 6.4]) Assume that P ∈ ℤ_{2}[x] and x_{0} ∈ ℤ_{2} satisfies

P (x_{0}) ≡ 0 (mod 2^{n})

If ϕ = ν_{2}(P′(x_{0})) < n/2, then there exists a unique zero ξ of P in ℤ_{2} such that

ξ ≡ x_{0} (mod p^{n−ϕ}) and ν_{2}(P′(ξ)) = ν_{2}(P′(x_{0}))

Lemma 6. ([7, Sec. 6.6]) The function f(x) = x^{2} − a has a zero in ℤ_{2}^{×}, the set of invertible elements of ℤ_{2}, if and only if a ≡ 1 (mod 8).

3 Proof of Theorem 1: unbounded cases and infinite trees

We now prove Theorem 1. The main idea is to describe the roots to f(n) = 0 in ℚ_{2} simply using the quadratic formula, the parity of the coefficients, and the lemmas presented in Section 2.1. Moreover, according to Lemma 4, if a zero exists in ℤ_{2}, it manifests as an infinite branch in the tree. We begin with Cases 2 and 4.

To this end, note that in Case 2, we can write a = 2r and b = 2k + 1 for some r, k ∈ ℤ. Then an^{2} + bn + c = 0 has roots of the form

x = \frac{−2k − 1 ± \sqrt{1 − 8(rc − β)}}{4r},  (3)

where β = (k^{2} + k)/2. Set j = rc − β.

Also, in Case 4, we can write a = 2r + 1, b = 2k + 1, and c = 2p. Then an^{2} + bn + c = 0 has roots of the form

x = \frac{−2k − 1 ± \sqrt{1 − 8((2r + 1)p − β)}}{2(2r + 1)},  (4)

where β = (k^{2} + k)/2. Set j = (2r + 1)p − β. Observe that in either case the roots contain \sqrt{1 − 8j} where j ∈ ℤ. Since \sqrt{1 − 8j} is a zero of the function g(x) = x^{2} − (1 − 8j), by Lemma 6 the zero is in ℤ_{2}.

Notice that both roots (3) and (4) have an even denominator. We still need to check if these roots are in ℚ_{2} or ℤ_{2}. Therefore, in light of Lemma 4, Case 2 (Proposition 7) and Case 4 (Proposition 8) are proved by an inductive argument on the behavior of the tree. It turns out that, in Case 2, f(n) has exactly one zero in ℤ_{2} and in Case 4, f(n) has two zeros in ℤ_{2}. See Figure 3 in the Appendix for an example of a tree with one infinite branch and Figure 4 for an example of a tree with two infinite branches.

Proposition 7. If a is even and b is odd, then the 2-adic valuation tree of f(n) = an^{2}+bn+c has exactly one infinite branch. Furthermore, the valuation of the terminating node at the i^{th} level is i − 1.

Proof. Note that this Proposition corresponds to Case 2 of Theorem 1. Substituting a = 2r and b = 2k + 1 for some r, k ∈ ℤ, we get an^{2} + bn + c = 2(rn^{2} + kn) + n + c. Now suppose that c is even. If n is even, then 2(rn^{2} + kn) + n + c is divisible by 2 and so ν_{2}(f(2n)) ≥ 1. If n is odd, then 2(rn^{2} + kn) + n + c is not divisible by 2 and so ν_{2}(f(2n + 1)) = 0. An analogous argument shows that, for c odd, ν_{2}(f(2n)) = 0 and ν_{2}(f(2n + 1)) ≥ 1. Therefore, the conclusion of the proposition is valid at the initial step.

Now, arguing inductively, suppose that n = 2^{i}q + r_{i−1} is the non-terminating node, that is ν_{2}(f(n)) ≥ i. So f(n) ≡ 0 (mod 2^{i}) or a(2^{i}q + r_{i−1})^{2} + b(2^{i}q + r_{i−1}) + c = 2^{i}β where β ∈ ℤ. Consider f(n) evaluated at the next level:

a(2^{i+1}q + r_{i−1})^{2} + b(2^{i+1}q + r_{i−1}) + c ≡ ar_{i−1}^{2} + br_{i−1} + c ≡ 2^{i}β (mod 2^{i+1}),

and

a(2^{i+1}q + 2^{i} + r_{i−1})^{2} + b(2^{i+1}q + 2^{i} + r_{i−1}) + c ≡ ar_{i−1}^{2} + 2^{i}b + br_{i−1} + c
≡ 2^{i}β + 2^{i}b ≡ 2^{i}(β + b) (mod 2^{i+1}).

Since b is odd it follows that the valuation of one node is i and the other is greater than i depending on if β is odd or even. Therefore one node terminates and the other is nonterminating.

Proposition 8. If a and b are odd, and c is even, then the 2-adic valuation tree of f(n) = an^{2} + bn + c has two infinite branches. Furthermore, the valuation of the terminating node at the i^{th} level is i.

Proof. This proposition addresses Case 4 of Theorem 1. Write a = 2r + 1, b = 2k + 1, and c = 2p for some integers r, k, and p. First note that both a(2q)^{2} + b(2q) + c and a(2q + 1)^{2} + b(2q + 1) + c are congruent to 0 (mod 2). We now verify that the proposition holds at the initial step.

In the 2q case, we check 4q and 4q + 2. Note that

a(4q)^{2} + b(4q) + c ≡ c (mod 4)

and

a(4q + 2)^{2} + b(4q + 2) + c ≡ 2b + c (mod 4).

If c ≡ 0 (mod 4), then 2b + c ≢ 0 (mod 4). If c ≢ 0 (mod 4) then c = 2p with p odd and 2b + c = 2(b + p) ≡ 0 (mod 4). That is, either

ν_{2}(f(4q)) ≥ 2 and ν_{2}(f(4q + 2)) = 1, or

ν_{2}(f(4q)) = 1 and ν_{2}(f(4q + 2)) ≥ 2.

For the 2q + 1 case, we check 4q + 1 and 4q + 3. Note that

a(4q + 1)^{2} + b(4q + 1) + c ≡ a + b + c (mod 4)

and

a(4q + 3)^{2} + b(4q + 3) + c ≡ a + 3b + c (mod 4).

By hypothesis, a + b + c = 2(r + k + p) and a + 3b + c = 2(r + 3k + p + 2). But note that r + 3k + p + 2 = (r + k + p + 1) + (2k + 1). Now it is clear that r + 3k + p + 2 is even (odd) if and only if r + k + p + 1 is odd (even). Again, either

ν_{2}(f(4q + 1)) ≥ 2 and ν_{2}(f(4q + 3)) = 1, or
ν_{2}(f(4q + 1)) = 1 and ν_{2}(f(4q + 3)) ≥ 2.

For the inductive step, now suppose that n = 2^{i}q + r_{i−1} and n = 2^{i}q + r_{i−1}^{∗} are the nonterminating nodes where r_{i−1} = ∑_{k=1}^{i−1} α_{k}2^{k} + 1 (the odd side branch) and r_{i−1}^{∗} = ∑_{k=1}^{i−1} α_{k}2^{k} (the even side branch) where α_{k} ∈ {0, 1}. The fact that these branches are non-terminating follows from the same argument as in the proof of Proposition 7.

We now consider Case 3(b) of Theorem 1.

Proposition 9. Let a be odd, b be even and b^{2} − 4ac = 4^{ℓ}Δ for some ℓ ∈ ℤ^{+} as large as possible and Δ ≡ 1 (mod 8), then the 2-adic valuation tree of f(n) = an^{2} + bn + c has two infinite branches.

Proof. Let a be odd and b = 2k for some k ∈ ℤ. Fix ℓ ∈ ℤ^{+}. Then an^{2} + bn + c = 0 has roots of the form x = \frac{−k±\sqrt{k^{2}−ac}}{a}. By the hypothesis 4k^{2} − ac = 2^{2ℓ}Δ where Δ ≡ 1 (mod 8).

If Δ < 0 then we can naturally write Δ = 1 − 8j where j ∈ {1, 2, 3, …}.

If Δ > 0, then we can write Δ = 1 + 8j = 1 − 8(−j) where j ∈ ℕ.

Thus in either case Δ = 1−8j where j ∈ ℤ. Then it follows that \sqrt{4k^{2} − 4ac} = 2^{ℓ}\sqrt{1 − 8j}. By Lemma 6, \sqrt{1 − 8j} is in ℤ_{2}. Furthermore, since the denominator of x is odd this also guarantees that x ∈ ℤ_{2}. Therefore, there are two infinite branches, one corresponding to each root.

Corollary 10. Under the conditions of Proposition 9, if b^{2} − 4ac = 0, the tree has one infinite branch.

Proof. In this case (3(a) of Theorem 1) roots take the form x = −\frac{b}{2a}. Since b = 2k, then x = −\frac{k}{a} which has 2-adic form x = ∑_{i=0}^{∞} α_{i}2^{i} where α_{i} is either 0 or 1. This guarantees that the one branch is infinite.

Remark 11. Note the connection between subsequences of (ν_{2}(f(n)))_{n≥0} and the infinite branches of a tree. Proposition 7 asserts that for all i ∈ ℤ^{+} there exists exactly one subsequence of the form n = 2^{i}q + r_{i−1} such that ν_{2}(f(n)) ≥ i and exactly one subsequence of the form n = 2^{i}q + r_{i−1}^{∗} with ν_{2}(f(n)) = i − 1. Similarly, Proposition 8 asserts that for all i ∈ ℤ^{+} there are exactly two subsequences corresponding to n = 2^{i}q+r_{i−1} such that ν_{2}(f(n)) ≥ i+1 and exactly two subsequences of the form n = 2^{i}q + r_{i−1}^{∗} with ν_{2}(f(n)) = i. For r_{i−1} and r_{i−1}^{∗}, the representations presented in equation (1) of Section 2 equate the coefficients α_{k} and α_{k}^{∗} for all 0 ≤ k ≤ i − 2, and meanwhile α_{i−1}^{∗} ≡ α_{i−1} + 1 (mod 2).

As for the cases of Proposition 9 and Corollary 10, we can apply Lemma 4 to conclude that these sequences are unbounded. Much like Propositions 7 and 8, we can say that the results of Proposition 9 yield that for all i ∈ ℕ there are exactly two subsequences of the form n = 2^{i}q + r_{i−1}, where (ν_{2}(f(n)))_{n≥0} is not constant, while Corollary 10 asserts there is exactly one such subsequence.

4 Bounded cases and finite trees

In this section, we prove Case 3(c) of Theorem 1 and the first part of Theorem 2. The coefficients of these quadratics satisfy the following: a is odd and b is even, and b^{2}−4ac = 4^{ℓ}Δ, where ℓ ∈ ℤ^{+} is as large as possible, Δ ≡ m (mod 8), and m ∈ {2, 3, 5, 6, 7}. Their trees are finite with ℓ levels. We can again apply the reasoning of the proof of Proposition 9.

If Δ < 0 we can naturally write Δ = m − 8j where j ∈ ℕ and if Δ > 0 then we write Δ = m + 8j = m − 8(−j) where j ∈ ℕ or j = 0. Henceforth, we will write Δ = m − 8j where j ∈ ℤ. Again, by Lemma 6 functions of the form g(x) = x^{2} − (m − 8j) do not have a zero in ℤ_{2}. By Lemma 4, the corresponding valuation sequences are periodic. Figures 5 and 6 in the Appendix illustrate examples of finite trees arising from functions f_{3}(n) = 15n^{2} + 1142n + 25559 and f_{4}(n) = 5n^{2} + 106n + 1125.

We should take a moment to note why we only need to consider these five values of m. First note that in Cases 3(b) and 3(c) of Theorem 1, where a is odd and b is even, we have the condition that ℓ is as large as possible. This corresponds to factoring out as many powers of 4 as possible, ruling out the possibilities m ∈ {0, 4}. Now if m = 1 (Case 3(b), covered in Section 3), an infinite tree is created. This leaves the cases m ∈ {2, 3, 5, 6, 7}. As discussed above, the zeros of these quadratic functions are not elements of ℚ_{2}; therefore, their trees must be finite. The proofs of the next two propositions follow the proofs of Propositions 7 and 8.

Proposition 12. If a is odd and b is even, and b^{2} − 4ac = 4^{ℓ}Δ where ℓ ∈ ℤ^{+} is as large as possible, Δ ≡ m (mod 8), and m ∈ {2, 3, 5, 6, 7}, then the 2-adic valuation tree of f(n) is finite with ℓ levels.

The proof of this proposition is broken down into Lemmas 13, 14, and 16. Unless stated otherwise, let b = 2k for some k ∈ ℤ. Lemma 13 covers the case ℓ = 1, in which the 2-adic valuation tree has exactly one level. Lemmas 14 and 16 describe valuations for finite trees with more than one level; Lemma 16 describes the valuation at the final level and Lemma 14 describes the other levels. Under the assumptions of Proposition 12, with a odd and b even, we complete the square and use properties of the p-adic valuation to obtain ν_{2}(an^{2} + bn + c) = ν_{2}((an + k)^{2} − k^{2} + ac).

Lemma 13. Let ℓ = 1, i.e., b^{2} − 4ac = 4Δ, Δ ≡ m (mod 8), and m ∈ {2, 3, 5, 6, 7}. If m ∈ {2, 7} and b ≡ 0 (mod 4) or if m ∈ {3, 6} and b ≡ 2 (mod 4), then

ν_{2}(an^{2} + bn + c) = \begin{cases}0, & if n even; \\ 1, & if n odd. \end{cases}

If m ∈ {3, 6} and b ≡ 0 (mod 4) or if m ∈ {2, 7} and b ≡ 2 (mod 4), then

ν_{2}(an^{2} + bn + c) = \begin{cases}1, & if n even; \\ 0, & if n odd. \end{cases}

If m = 5 and b ≡ 0 (mod 4), then

ν_{2}(an^{2} + bn + c) = \begin{cases}0, & if n even; \\ 2, & if n odd. \end{cases}

If m = 5 and b ≡ 2 (mod 4), then

ν_{2}(an^{2} + bn + c) = \begin{cases}2, & if n even; \\ 0, & if n odd. \end{cases}

Proof. Using the convention that Δ = m − 8j where j ∈ ℤ and m ∈ {2, 3, 5, 6, 7}, consider the case where m = 7 and b ≡ 2 (mod 4). Then, since b = 2k, we have k odd. If n is even, then (an + k)^{2} ≡ k^{2} (mod 2) and so it follows that

((an + k)^{2} − k^{2} + ac) ≡ k^{2} − 7 ≡ −6 ≡ 0 (mod 2),

but

((an + k)^{2} − k^{2} + ac) ≡ k^{2} − 7 ≡ −6 ≡ 2 (mod 4).

Therefore ν_{2}(an^{2} + bn + c) = 1 when n is even. Similarly, when m = 7 and b ≡ 2 (mod 4) if n is odd, then (an + k)^{2} is even. Therefore, (an + k)^{2} − k^{2} + ac ≡ −7 ≡ 1 (mod 2). Thus ν_{2}(an^{2} + bn + c) = 0 when n is odd.

Now consider the case where m = 7 and b ≡ 0 (mod 4). We have b = 2k with k even. Thus, if n is odd we have

(an + k)^{2} − k^{2} + ac ≡ −6 ≡ 0 (mod 2)

and

(an + k)^{2} − k^{2} + ac ≡ k^{2} − 7 ≡ −6 ≡ 2 (mod 4).

Thus ν_{2}(an^{2} + bn + c) = 1 when n is odd. When n is even we have (an + k)^{2} − k^{2} + ac ≡ −7 ≡ 1 (mod 2). Thus ν_{2}(an^{2} + bn + c) = 0 when n is even.

The cases of m ∈ {2, 3, 6} when b ≡ 0 (mod 4) or b ≡ 2 (mod 4) can be handled in the same fashion. For m = 5, the valuations are slightly different.

Consider the case where m = 5. Recall that b = 2k for some k ∈ ℤ. Note that

b^{2} − 4ac = 4(5 − 8j),

and hence k^{2} − ac = 5 − 8j. Thus,

(an + k)^{2} − k^{2} + ac = (an + k)^{2} − 5 + 8j.

If (an + k) is even, which is the case when both n and k are even or both n and k are odd, then (an + k)^{2} − 5 + 8j is odd. Thus, ν_{2}(an^{2} + bn + c) = 0.

Now suppose that (an+k) is odd, which is true when n and k have different parity. Then (an + k)^{2} ≡ 1 (mod 4), and this implies

(an + k)^{2} − 5 + 8j ≡ 1 − 5 + 8j ≡ −4 + 8j ≡ 0 (mod 4).

Thus, ν_{2}(an^{2} + bn + c) ≥ 2. Since (an + k) is odd, let an + k = 2d + 1, for some d ∈ ℤ. Then,

(an + k)^{2} − 5 + 8j = (2d + 1)^{2} − 5 + 8j
≡ 4(d^{2} + d − 1) (mod 8).

Observe that d^{2}+d−1 is odd, regardless of whether d is even or odd. Thus, ν_{2}(an^{2}+bn+c) < 3. Therefore, ν_{2}(an^{2} + bn + c) = 2.

Lemma 14. Under the assumptions of Proposition 12 (Case 3(c) of Theorem 1) let ℓ ≥ 2 and suppose 0 < i < ℓ. At the i^{th} level there is one terminal and one non-terminal node. Furthermore, the terminal node has valuation 2(i − 1) and the non-terminal node has valuation at least 2i.

First we need:

Claim 15. Let a, k ∈ ℤ with a odd. Let g(n) = an + k, then (ν_{2}(g(n)))_{n≥0} creates an unbounded sequence.

Proof. First note that the root of ax+k = 0 is x = −\frac{k}{a}. Also note that ν_{2}(x) = ν_{2}(−k)−ν_{2}(a). Since a is odd, ν_{2}(a) = 0. Therefore ν_{2}(x) = ν_{2}(−k) ≥ 0. By equation (2), x ∈ ℤ_{2}, so Lemma 4 implies that (ν_{2}(g(n)))_{n≥0} is an unbounded sequence.

Proof. To prove Lemma 14, we proceed by an inductive argument on i. Again, using the convention that Δ = m−8j where j ∈ ℤ, for the base case i = 1, note that b^{2}−4ac ≡ 4^{ℓ}(m− 8j) ≡ 0 (mod 4). Recall that b = 2k. First, assume that k is even. If n is even, then an+k is even and so (an+k)^{2}−k^{2}+ac ≡ 0 (mod 4). Thus ν_{2}(an^{2}+bn+c) = ν_{2}((an+k)^{2}−k^{2}+ac) ≥ 2 by Claim 15. If n is odd, then (an+k)^{2} −k^{2} +ac ≡ 1 (mod 2), and again using the technique of completing the square, ν_{2}(an^{2} + bn + c) = 0. If k is odd, a similar argument shows that ν_{2}(an^{2} + bn + c) ≥ 2 when n is odd. Observe also that Claim 15 can be used to show that (ν_{2}((an+k)^{2}))_{n≥0} forms an unbounded sequence therefore ν_{2}((an+k)^{2} −k^{2} +ac) ≥ 2. Thus, the claim is true for i = 1.

For the inductive step, notice that since i < ℓ, it follows that

b^{2} − 4ac ≡ 4^{ℓ}(m − 8j) ≡ 0 (mod 2^{2i}).

Suppose there exists an i − 1 ≥ 0 such that n = 2^{i−1}q + r_{i−2} splits into two nodes: one node terminating with valuation 2(i−1) and the other node having valuation of at least 2i. We let n = 2^{i}q + r_{i−1} denote the non-terminating node, where r_{i−1} = ∑_{h=0}^{i−1} α_{h}2^{h} with α_{h} ∈ {0, 1}, for all 0 ≤ h ≤ i − 2, and q ∈ ℤ. Then we have

(an + k)^{2} − k^{2} + ac ≡ (a(2^{i}q + r_{i−1}) + k)^{2} ≡ 0 (mod 2^{2i}),

so ν_{2}(an^{2} + bn + c) ≥ 2i. This also implies that a(2^{i}q + r_{i−1}) + k ≡ 0 (mod 2^{i}). Thus ar_{i−1} + k = 2^{i}β where β ∈ ℤ. Now suppose that k is even. (The proof for k odd can be handled in the same fashion, and thus is omitted.) Since k is even, then r_{i−1} must be even.

Consider the (i + 1)^{st} level where i + 1 < ℓ. Here again we have

b^{2} − 4ac = 4^{ℓ}(m − 8j) (mod 2^{2(i+1)}) ≡ 0.

Moving to the next level, in the case n = 2^{i+1}q + r_{i−1} we have

ν_{2}((an + k)^{2} − 4^{ℓ−1}(m − 8j)) = ν_{2}((a(2^{i+1}q + r_{i−1}) + k)^{2} − 4^{ℓ−1}(m − 8j))
= ν_{2}((2^{i+1}aq + ar_{i−1} + k)^{2} − 4^{ℓ−1}(m − 8j))
= ν_{2}((2^{i+1}aq + 2^{i}β)^{2} − 4^{ℓ−1}(m − 8j))
= ν_{2}(2^{2i}(2aq + β)^{2} − 2^{2(ℓ−1)}(m − 8j)),

and in the case n = 2^{i+1}q + 2^{i} + r_{i−1} we have

ν_{2}((an + k)^{2} − 4^{ℓ−1}(m − 8j))
= ν_{2}((a(2^{i+1}q + 2^{i} + r_{i−1}) + k)^{2} − 4^{ℓ−1}(m − 8j))
= ν_{2}((2^{i+1}aq + 2^{i}a + ar_{i−1} + k)^{2} − 4^{ℓ−1}(m − 8j))
= ν_{2}((2^{i+1}aq + 2^{i}a + 2^{i}β)^{2} − 4^{ℓ−1}(m − 8j))
= ν_{2}(2^{2i}(2aq + a + β)^{2} − 2^{2(ℓ−1)}(m − 8j)).

Since β ∈ ℤ either 2aq+β or 2aq+a+β is odd and the other is even. As long as i+1 < ℓ then in the odd case the valuation is 2i and in the even case the valuation is at least 2(i + 1).

Lemma 16. If a is odd and b is even with b = 2k for k ∈ ℤ, and b^{2} − 4ac = 4^{ℓ}Δ where ℓ ∈ ℤ^{+} is as large as possible, Δ ≡ m (mod 8), and m ∈ {2, 3, 5, 6, 7}, then at the ℓ^{th} level the nodes of the 2-adic valuation tree terminate with valuations of 2(ℓ − 1), 2ℓ − 1 or 2ℓ.

Suppose that n = 2^{ℓ}q + r_{ℓ−2}. If an + k ≡ 0 (mod 2^{ℓ}), then

ν_{2}(f(n)) = \begin{cases}2(ℓ − 1), & if m = 7, 5, 3; \\ 2ℓ − 1, & if m = 6, 2; \end{cases}

and if an + k ≢ 0 (mod 2^{ℓ}), then

ν_{2}(f(n)) = \begin{cases}2(ℓ − 1), & if m = 6, 2; \\ 2ℓ − 1, & if m = 7, 3; \\ 2ℓ, & if m = 5. \end{cases}

Suppose that n = 2^{ℓ}q + 2^{ℓ−1} + r_{ℓ−2}. If an + k ≡ 0 (mod 2^{ℓ}), then

ν_{2}(f(n)) = \begin{cases}2(ℓ − 1), & if m = 6, 2; \\ 2ℓ − 1, & if m = 7, 3; \\ 2ℓ, & if m = 5; \end{cases}

and if an + k ≢ 0 (mod 2^{ℓ}), then

ν_{2}(f(n)) = \begin{cases}2(ℓ − 1), & if m = 7, 5, 3; \\ 2ℓ − 1, & if m = 6, 2. \end{cases}

Proof. By Lemma 14 there exists a non-terminating node n = 2^{ℓ−1}q + r_{ℓ−2} with q ∈ ℤ and

ν_{2}((an + k)^{2} − k^{2} + ac) ≥ 2(ℓ − 1).

Consider n = 2^{ℓ}q + r_{ℓ−2} with q ∈ ℤ. By the same argument as in Lemma 14 and using the convention that Δ = m − 8j where j ∈ ℤ, we have

(an + k)^{2} − k^{2} + ac = (2^{ℓ}aq + 2^{ℓ−1}β)^{2} − 2^{2(ℓ−1)}(m − 8j) = 2^{2(ℓ−1)}((2aq + β)^{2} + 8j − m),

where β ∈ ℤ. Recall that a is odd. Then depending on whether β is even or odd, simple calculations show the first two results.

In the case when n = 2^{ℓ}q + 2^{ℓ−1} + r_{ℓ−2} with q ∈ ℤ we have

(an + k)^{2} − k^{2} + ac = 2^{2(ℓ−1)}((2aq + a + β)^{2} + 8j − m),

where β ∈ ℤ. Then again depending on whether β is odd or even, it is straightforward to show the last two results.

5 Structure of finite trees

The section describes the overall structure of finite trees, continuing the discussion of Case 3(c) of Theorem 1, in which a is odd, b is even, b^{2} − 4ac = 4^{ℓ}Δ where Δ ≡ m (mod 8), and m ∈ {2, 3, 5, 6, 7}. Throughout this section, we make use of several operators. The operators allow us to track changes from very easily described trees, which we call type (ℓ, 1), to more complicated trees.

Definition 17 (Translation operator, [4]). For quadratics of the form f(n) = an^{2} + bn + c we define τ^{s}(f)(n) = f(n − s) for s ∈ ℝ, namely τ^{s}(f)(n) = a(n − s)^{2} + b(n − s) + c = an^{2} + (b − 2as)n + (c + as^{2} − bs).

Proposition 18. Let the assumptions of Proposition 12 hold for the function f(n) = an^{2} + bn + c and suppose s ∈ ℤ. Then we have the following relationship

ν_{2}(f(2^{i}q + r_{i−1})) = ν_{2}(τ^{s}f(2^{i}q + (r_{i−1} + s) mod 2^{i})).

That is the valuations ν_{2}(f(n)) at the node of the form n = 2^{i}q + r_{i−1} are moved to the node of the form n = 2^{i}q + (r_{i−1} + s) (mod 2^{i}) under the operation τ^{s}.

Proof. Note that finite trees with ℓ levels correspond to periodic sequences with a period equal to 2^{ℓ}. Since τ^{s} is a translation operator, every element in the sequence (ν_{2}(f(n)))_{n≥0} is moved over s spaces.

Definition 19 (S-operator). Let a be a positive, odd integer. For quadratics of the form f(n) = n^{2} + bn + ac we define S^{a}(f)(n) = an^{2} + bn + c. Likewise, for quadratics of the form f(n) = an^{2} + bn + c define S^{a^{−1}}(f)(n) = n^{2} + bn + ac.

In general, the S-operator need not output a quadratic function with an integer constant term. However, the present work only applies S^{a} to functions whose output has integer coefficients.

Definition 20 (Dilation operator, [4]). For quadratics of the form f(n) = an^{2} + bn + c we define δ^{s}(f)(n) = f(sn) for s ∈ ℝ, namely δ^{s}(f)(n) = a(sn)^{2} + b(sn) + c.

Lemma 21. Under the assumptions of Proposition 12 the trees created by f(n) = n^{2}+bn+ac and S^{a}(f)(n) where a ∈ ℤ have the same number of levels. Similarly, the trees created by g(n) = an^{2} + bn + c and τ^{s}(g)(n) where s ∈ ℤ have the same number of levels.

Proof. The assumptions of Proposition 12 represent Cases 3(b) and 3(c) of Theorem 1. Simple calculations show that the discriminants of f(n) and S^{a}(f)(n) are the same, and that the discriminants of g(n) and τ^{s}(g)(n) are the same. The conclusions then follow directly from Proposition 12.

Proposition 22. Let the assumptions of Proposition 12 hold and suppose f(n) = n^{2}+bn+ac. Then we have the following relationship

ν_{2}(f(2^{i}q + r_{i−1})) = ν_{2}(S^{a}(f(2^{i}q + a^{−1} · r_{i−1}))).

That is the valuation ν_{2}(f(n)) at the node the form n = 2^{i}q + r_{i−1} is moved to the node of the form of n = 2^{i}q + (a^{−1} · r_{i−1}) (mod 2^{i}) under the operation S^{a}. In this context a^{−1} is the inverse of a (mod 2^{i}).

Proof. Since a is odd, note that

ν_{2}(S^{a}(f)(n)) = ν_{2}((an^{2} + bn + c)) = ν_{2}((an)^{2} + b(an) + ac) = ν_{2}(δ^{a}(f)(n)),

where δ^{a}(f)(n) = f(an) is the dilation operator. Thus, the valuation of f(n) for n = 2^{i}q+r_{i−1} is the same as the valuation of n′ = 2^{i}(a^{−1}q) + a^{−1} · r_{i−1} after the S^{a}-operator is applied.

Suppose that f(n) = an^{2} + bn + c creates a finite tree. We say that this tree is type (ℓ, 1), for ℓ ≥ 2, if at every level the non-terminating node is of the form n = 2q or n = 2^{i}q + 2^{i−2} + ⋯ + 2^{1} + 2^{0} for i < ℓ and the tree has ℓ levels. We also say that a quadratic function is type (ℓ, 1) if it creates an (ℓ, 1) tree. That is, f(n) creates a finite tree of the following form:

Figure 2: The form of trees of type (ℓ, 1).

Here, we suppose that ℓ ≥ 2 because ℓ = 1 creates a tree with one level, see Lemma 13, and the directional behavior we seek to classify is not defined. The conditions 4a^{2}−4ac = 4^{ℓ}Δ for ℓ ∈ ℤ^{+} as large as possible, Δ ≡ m (mod 8), and m ∈ {2, 3, 5, 6, 7} imply c must be odd.

Proposition 23. Under the assumptions of Proposition 12, if c is odd and ℓ ≥ 2 is an integer, then a quadratic of the form f(n) = an^{2} + 2an + c creates a tree that is of type (ℓ, 1). Furthermore, we have

ν_{2}(f(n)) = \begin{cases}0, & if n ≡ 0 (mod 2); \\ 2(i − 1), & if n ≡ ∑_{k=0}^{i−2} 2^{k} (mod 2^{i}) with 2 ≤ i < ℓ; \\ 2(ℓ − 1), & if n ≡ ∑_{k=0}^{ℓ−2} 2^{k} (mod 2^{ℓ}) and m = 6, 2; \\ 2ℓ − 1, & if n ≡ ∑_{k=0}^{ℓ−2} 2^{k} (mod 2^{ℓ}) and m = 7, 3; \\ 2ℓ, & if n ≡ ∑_{k=0}^{ℓ−2} 2^{k} (mod 2^{ℓ}) and m = 5; \\ 2ℓ − 1, & if n ≡ ∑_{k=0}^{ℓ−1} 2^{k} (mod 2^{ℓ}) and m = 6, 2; \\ 2(ℓ − 1), & if n ≡ ∑_{k=0}^{ℓ−1} 2^{k} (mod 2^{ℓ}) and m = 7, 5, 3. \end{cases}

Proof. In light of Lemma 14, we know that if a node is non-terminating, then it produces two nodes that either both terminate (i.e., these nodes are at the ℓ^{th} level) or one node is non-terminating and the other is terminating. So in order to show that the tree is of type (ℓ, 1), we only need to confirm that nodes corresponding to n = 2^{i}q + 2^{i−1} + ⋯ + 2^{1} + 2^{0}, where 1 ≤ i ≤ ℓ, are always non-terminating. Since a is odd, completing the square and using the convention that 4a^{2} − 4ac = 4^{ℓ}Δ where Δ = m − 8j where j ∈ ℤ gives

ν_{2}(f(n)) = ν_{2}(an^{2} + 2an + c) = ν_{2}(a(n + 1)^{2} − a + c)
= ν_{2}(a^{2}(n + 1)^{2} − a^{2} + ac) = ν_{2}(a^{2}(n + 1)^{2} − 4^{ℓ−1}(m − 8j))
= ν_{2}(a^{2}(2^{i}q + 2^{i−1} + 2^{i−2} + ⋯ + 2 + 1 + 1)^{2} − 4^{ℓ−1}(m − 8j))
= ν_{2}(a^{2}(2^{i}q + 2^{i})^{2} − 4^{ℓ−1}(m − 8j))
= ν_{2}(a^{2}4^{i}(q + 1)^{2} − 4^{ℓ−1}(m − 8j)).

If q is odd, then n = 2^{i}q+2^{i−1} +⋯+2^{1} +2^{0} is the non-terminating node, provided i < ℓ, and produces two nodes one of which does not terminate. If i = ℓ, then both nodes terminate by Proposition 12.

The nodes that terminate are of the form n = 2^{i}q + 2^{i−2} + ⋯ + 2^{1} + 2^{0} when 1 ≤ i < ℓ. The case when n = 2q is handled by the proof of Lemma 21. For the case 1 < i < ℓ, by the same calculation as above we have

ν_{2}(f(n)) = ν_{2}(a^{2}2^{2(i−1)}(2q + 1)^{2} − 4^{ℓ−1}(m − 8j))

Since 2q + 1 is odd and i < ℓ the valuation must be 2(i − 1).

In the case when n = 2^{ℓ}q + 2^{ℓ−2} + ⋯ + 2^{1} + 2^{0} we have

ν_{2}(f(n)) = ν_{2}(a^{2}2^{2(ℓ−1)}(2q + 1)^{2} − 4^{ℓ−1}(m − 8j))

Thus the valuation must be 2(ℓ − 1) if m = 6, 2, or 2ℓ − 1 if m = 7, 3 or 2ℓ if m = 5.

Finally if n = 2^{ℓ}q+2^{ℓ−2}+⋯+2^{1}+2^{0} we have ν_{2}(f(n)) = ν_{2}(a^{2}2^{2ℓ}(q+1)^{2}−4^{ℓ−1}(m−8j)). Thus the valuation must be 2(ℓ − 1) if m = 7, 5, 3 or 2ℓ − 1 if m = 6, 2.

If the function f(n) = an^{2} + bn + c meets the assumptions of Proposition 12 (Case 3(c) of Theorem 1) note if we define the function g(n) = n^{2} + 2n − (1 − \frac{b}{2})^{2} + 2 (1 − \frac{b}{2}) + ac, then it follows that S^{a}(τ^{1− \frac{b}{2}} (g))(n) = f(n). Therefore, by Propositions 18, 22, and 23 we immediately have the following corollary.

Corollary 24. If f(n) = an^{2} + bn + c meets the assumptions of Proposition 12 (Case 3(c)) with ℓ ≥ 2, then

ν_{2}(f(n)) = \begin{cases}0, & if n ≡ a^{−1} (1 − \frac{b}{2}) (mod 2); \\ 2(i − 1), & if n ≡ a^{−1} (2^{i−1} − \frac{b}{2}) (mod 2^{i}) with 2 ≤ i < ℓ; \\ 2(ℓ − 1), & if n ≡ a^{−1} (2^{ℓ−1} − \frac{b}{2}) (mod 2^{ℓ})and m = 6, 2; \\ 2ℓ − 1, & if n ≡ a^{−1} (2^{ℓ−1} − \frac{b}{2}) (mod 2^{ℓ}) and m = 7, 3; \\ 2ℓ, & if n ≡ a^{−1} (2^{ℓ−1} − \frac{b}{2}) (mod 2^{ℓ}) and m = 5; \\ 2ℓ − 1, & if n ≡ a^{−1} (2^{ℓ} − \frac{b}{2}) (mod 2^{ℓ}) and m = 6, 2; \\ 2(ℓ − 1), & if n ≡ a^{−1} (2^{ℓ} − \frac{b}{2}) (mod 2^{ℓ}) and m = 7, 5, 3; \end{cases}

where a^{−1} is the inverse of a (mod 2^{ℓ}).

Proof. Simply note that g is type (ℓ, 1) and recall the ways in which the operators affect the function g. Each terminating node, under the operators, moves from n = 2^{i}q + r_{i−2} to n = 2^{i}q + a^{−1} (r_{i−2} + 1 − \frac{b}{2}) (mod 2^{i}). In the case of type (ℓ, 1) we have r_{i−2} = ∑_{k=0}^{i−2} 2^{k}. Thus r_{i−2} + 1 = 2^{i−1} in each case.

6 Acknowledgments

The authors would like to thank Dr. Victor Moll for suggesting this topic. We would also like to thank following institutions for providing support to collaborate: ICERM, AIM, Kentucky Wesleyan College, Ursinus College, and Stephen F. Austin State University. We are grateful to our other colleagues for their ongoing support: Dr. Maila Brucal-Hallare, Dr. Jean-Claude Pedjeu, and Dr. Bianca Thompson. And, finally, we are very grateful to the reviewer who provided many very helpful and insightful comments.

Appendix: figures illustrating trees and tables of values for 2-adic valuation sequences of some quadratic functions

In the following tree representations, a closed circle indicates a terminating node and an open circle indicates a non-terminating node.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ f_{1}(n) & −25 & −8 & 17 & 50 & 91 & 140 & 197 & 262 & 335 & 416 & 505 & 602 \\ ν_{2}(f_{1}2(n)) & 0 & 3 & 0 & 1 & 0 & 2 & 0 & 1 & 0 & 5 & 0 & 1 \end{matrix}

\begin{matrix}n & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \\ f_{1}(n) & 707 & 820 & 941 & 1070 & 1207 & 1352 & 1505 & 1666 & 1835 & 2012 \\ ν_{2}(f_{1}(n)) & 0 & 2 & 0 & 1 & 0 & 3 & 0 & 1 & 0 & 2 \end{matrix}

Figure 3: The 2-adic valuation tree for f_{1}(n) = 4n^{2} + 13n − 25. Theorem 1 predicts that (ν_{2}(f_{1}(n)))_{n≥0} is an unbounded sequence, as it satisfies Case 2.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ f_{2}(n) & −28 & −3 & 48 & 125 & 228 & 357 & 512 & 693 & 900 & 1133 & 1392 \\ ν_{2}(f_{2}(n)) & 2 & 0 & 4 & 0 & 2 & 0 & 9 & 0 & 2 & 0 & 4 \end{matrix}

\begin{matrix}n & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\ f_{2}(n) & 1677 & 1988 & 2325 & 2688 & 3077 & 3492 & 3933 & 4400 & 4893 \\ ν_{2}(f_{2}(n)) & 0 & 2 & 0 & 7 & 0 & 2 & 0 & 4 & 0 \end{matrix}

Figure 4: The 2-adic valuation tree and data for f_{2}(n) = 13n^{2} + 12n − 28. Notice that Theorem 1 predicts that (ν_{2}(f_{2}(n)))_{n≥0} is an unbounded sequence, as it satisfies Case 3(a) since 12^{2} − 4 · 13(−28) = 4^{3}(1 − 8(−3)).

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ f_{3}(n) & 25559 & 26716 & 27903 & 29120 & 30367 & 31644 & 32951 & 34288 \\ ν_{2}(f_{3}(n)) & 0 & 2 & 0 & 6 & 0 & 2 & 0 & 4 \end{matrix}

\begin{matrix}n & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ f_{3}(n) & 35655 & 37052 & 38479 & 39936 & 41423 & 42940 & 44487 & 46064 \\ ν_{2}(f_{3}(n)) & 0 & 2 & 0 & 10 & 0 & 2 & 0 & 4 \end{matrix}

Figure 5: The 2-adic valuation tree and data for f_{3}(n) = 15n^{2} + 1142n + 25559. Notice that Theorem 1 predicts that (ν_{2}(f_{3}(n))_{n≥0} is a bounded sequence, as it satisfies Case 3(c) since 1142^{2} − 4 · 15 · 25559 = 4^{7}(2 − 8 · 2).

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ f_{4}(n) & 1125 & 1236 & 1357 & 1488 & 1629 & 1780 & 1941 & 2112 & 2293 & 2484 \\ ν_{2}(f_{4}(n)) & 0 & 2 & 0 & 4 & 0 & 2 & 0 & 6 & 0 & 2 \end{matrix}

\begin{matrix}n & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\ f_{4}(n) & 2685 & 2896 & 3117 & 3348 & 3589 & 3840 & 4101 & 4372 & 4653 & 4944 \\ ν_{2}(f_{4}(n)) & 0 & 4 & 0 & 2 & 0 & 8 & 0 & 2 & 0 & 4 \end{matrix}

Figure 6: The 2-adic valuation tree and data for f_{4}(n) = 5n^{2} + 106n + 1125. Notice that Theorem 1 predicts that (ν_{2}(f_{4}(n))_{n≥0} is a bounded sequence, as it satisfies Case 3(c) since 106^{2} − 4 · 5 · 1125 = 4^{5}(5 − 8 · 2).

References

[1] J.-P. Allouche and J. Shallit, Automatic Sequences, Theory, Applications, Generalizations, Cambridge University Press, 2003.

[2] J. P. Bell, p-adic valuations and k-regular sequences, Discrete Math. 307 (2007), 3070– 3075.

[3] A. N. Byrnes, J. Fink, G. Lavigne, I. Nogues, S. Rajasekaran, A. Yuan, L. Almodovar, X. Guan, A. Kesarwani, L. A. Medina, E. Rowland, and V. H. Moll, A closed-form solution might be given by a tree. Valuations of quadratic polynomials, Sci. Ser. A Math. Sci. 29 (2019), 11–28.

[4] L. Grafakos, Classical Fourier Analysis, Second Edition, Springer, 2008.

[5] F. Gouvêa, p-Adic Numbers: An Introduction, Springer-Verlag, 1997.

[6] L. A. Medina, V. H. Moll, and E. Rowland, Periodicity in the p-adic valuation of a polynomial, J. Number Theory 180 (2017), 139–153.

[7] A. M. Robert, A Course in p-adic Analysis, Springer, 2000.

2010 Mathematics Subject Classification: Primary 11B50; Secondary 11S05. Keywords: p-adic valuation, polynomial sequences, p-adic tree.

Received June 15 2020; revised versions received June 30 2020; March 12 2021; May 5 2021; May 14 2021. Published in Journal of Integer Sequences, May 17 2021.

Return to Journal of Integer Sequences home page.