\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\usepackage[normalem]{ulem}
\usepackage{mathrsfs}
\usepackage{pgf,tikz,pgfplots}
\usepackage{verbatim}
\pgfplotsset{compat=1.15}
\usetikzlibrary{arrows}
\usepackage{enumerate}
\usepackage{multicol}
\def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}}
%\usepackage[skip=0pt]{caption}
%\DeclareCaptionLabelSeparator*{spaced}{\\[2ex]}
%\captionsetup[figure]{labelsep=period, labelfont=it, justification=justified, singlelinecheck=false, font=singlespacing, skip=0pt}
%\setlength\intextsep{0pt}
\usepackage{booktabs}
\usepackage{multirow}
\usepackage{ragged2e}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
2-Adic Valuations of Quadratic Sequences
}
\vskip 1cm
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\footnote{Corresponding author.}\\
Kentucky Wesleyan College\\
Division of Natural Sciences and Mathematics\\
3000 Frederica Street\\
Owensboro, KY 42301 \\
USA\\
\href{mailto:jtrulen@kwc.edu}{\tt jtrulen@kwc.edu} \\
\end{center}
\vskip .2 in
\begin{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. We completely describe the periodic sequences in the bounded case. Throughout, we frame results in terms of trees and sequences.
\end{abstract}
\section{Introduction}\label{SecIntro}
For $p$ prime and $n\in\mathbb{N}=\{0,1,2,3,\ldots\}$, the exponent of the highest power of $p$ that divides $n$ is called the \textit{$p$-adic valuation of $n$}, which we denote $\nu_{p}(n)$. The valuation of $0$ is defined to be $+\infty$. Formally, the valuation of a positive integer $n$ of the form $n=p^{k}d$, where $k\in\mathbb{N}$ and $d$ is an integer not divisible by $p$, is $\nu_{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\in\mathbb{Z}$ and $a\neq0$.
Information about sequences of valuations can be viewed in two different ways: in terms of sequences and in terms of trees. We let $(\nu_2(f(n)))_{n\geq 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~\ref{MainThm1} and~\ref{MainThm2}; one would anticipate these results can be extended to odd primes with some modifications, which will be addressed in future work.
\begin{theorem}\label{MainThm1} Let $f(n)=an^{2}+bn+c$ where $a,b,c\in\mathbb{Z}$ with $a\neq 0$ and, without loss of generality, $a,b,c$ are not all even. Then
\begin{enumerate}
\item If $a$ and $b$ are even and $c$ is odd, then $\nu_{2}(f(n))=0$ for all $n\in\mathbb{N}$.
\item If $a$ is even and $b$ is odd, then $(\nu_{2}(f(n)))_{n\geq 0}$ is an unbounded sequence.
\item If $a$ is odd and $b$ is even, then
\begin{enumerate}
\item if $b^{2}-4ac=0$, then $(\nu_{2}(f(n)))_{n\geq 0}$ is an unbounded sequence;
\item if $b^{2}-4ac=4^{\ell}\Delta$ for $\ell\in\mathbb{Z}^{+}$ as large as possible and $\Delta\equiv\modd{1} {8}$, then $(\nu_{2}(f(n)))_{n\geq 0}$ is an unbounded sequence;
\item if $b^{2}-4ac=4^{\ell}\Delta$ for $\ell\in\mathbb{Z}^{+}$ as large as possible,
$\Delta\equiv\modd{m} {8}$, and $m\in\left\{2,3,5,6,7\right\}$, then the sequence $(\nu_{2}(f(n)))_{n\geq 0}$ is bounded and its minimal period length equals $2^{\ell}$.
\end{enumerate}
\item If $a$ and $b$ are odd and $c$ is even, then $(\nu_{2}(f(n)))_{n\geq 0}$ is an unbounded sequence.
\item If $a$, $b$, and $c$ are odd, then $\nu_{2}(f(n))=0$ for all $n\in\mathbb{N}$.
\end{enumerate}
\end{theorem}
Theorem~\ref{MainThm1} is proved in Section~\ref{SecInf}. Henceforward, we will refer to the \textit{minimal period length} simply as the \textit{period}. In Case 3, we use the discriminant to determine whether roots to $f(n)=0$ lie in the 2-adic numbers $\mathbb{Q}_2$ or the ring of 2-adic integers $\mathbb{Z}_2$. Corollary~\ref{InfSpecCor} 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 2-adic valuations. Theorem~\ref{MainThm1} represents a complete answer to when $\nu_{2}(f(n))_{n\geq0}$ is bounded or unbounded using only the coefficients of the quadratic polynomial. Furthermore, Theorem~\ref{MainThm1} 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~\ref{SecParityandTrees}. Theorem~\ref{MainThm2}, proved in Sections~\ref{BoundedSection} and~\ref{SecStrucTree}, completely determines all valuations in the non-trivial bounded case (3(c) of Theorem~\ref{MainThm1}).
\begin{theorem}\label{MainThm2}
Let $f(n)=an^{2}+bn+c$ where $a,b,c\in\mathbb{Z}$. If $a$ is odd and $b$ is even and $b^{2}-4ac=4^{\ell}\Delta$ for $\ell\in\mathbb{Z}^{+}$ as large as possible with $\ell\geq2$, $\Delta\equiv\modd{m} {8}$, and $m\in\left\{2,3,5,6,7\right\}$, then the sequence $(\nu_{2}(f(n)))_{n\geq 0}$ is bounded with period equal to $2^{\ell}$. Furthermore, we have the following 2-adic valuations:
\begin{displaymath}
\nu_{2}(f(n))=\begin{cases}
0,&\ \text{if}\ n\equiv\modd{ a^{-1}\left(1-\frac{b}{2}\right)} {2};\\
2(i-1),&\ \text{if}\ n\equiv\modd{ a^{-1}\left(2^{i-1}-\frac{b}{2}\right)} {2^{i}}\ \text{with}\ 2\leq i<\ell;\\
2(\ell-1),&\ \text{if}\ n\equiv\modd{ a^{-1}\left(2^{\ell-1}-\frac{b}{2}\right)} {2^{\ell}}\ \text{and}\ m=6,2;\\
2\ell-1,&\ \text{if}\ n\equiv\modd{ a^{-1}\left(2^{\ell-1}-\frac{b}{2}\right)} {2^{\ell}}\ \text{and}\ m=7,3;\\
2\ell,&\ \text{if}\ n\equiv\modd{ a^{-1}\left(2^{\ell-1}-\frac{b}{2}\right)} {2^{\ell}}\ \text{and}\ m=5;\\
2\ell-1,&\ \text{if}\ n\equiv\modd{ a^{-1}\left(2^{\ell}-\frac{b}{2}\right)} {2^{\ell}}\ \text{and}\ m=6,2;\\
2(\ell-1),&\ \text{if}\ n\equiv\modd{ a^{-1}\left(2^{\ell}-\frac{b}{2}\right)} {2^{\ell}}\ \text{and}\ m=7,5,3;\\
\end{cases}
\end{displaymath}
where $a^{-1}$ is the inverse of $\modd{a} {2^{\ell}}$.
\end{theorem}
The case $\ell=1$ is covered by Lemma~\ref{FinLem1}. In this case, the sequence is periodic with period equal to 2. Theorem~\ref{MainThm2} is proved in Proposition~\ref{FinThm} and Corollary~\ref{FinCor}. Both of these results are an extension of the work by Byrnes et al.~\cite{Byrnes}, which only considered quadratics of the form $f(n)=an^{2}+c$. The work of Medina et al.~\cite{Medina} 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 \cite{Bell}.
\section{Parity and trees}\label{SecParityandTrees}
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~\ref{MainThm1} and~\ref{MainThm2}, 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\in\mathbb{N}$ such that $2^{i}$ divides $a,b$, and $c$ but $2^{i+1}$ does not. Then $f(n)=2^{i}(a_{0}n^{2}+b_{0}n+c_{0})$ and
it follows that $\nu_{2}(f(n))=i+\nu_{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~\ref{MainThm1} are trivial (Case 1 where $a,b$ are even, and Case 5, where $a,b,$ and $c$ are odd), since $\nu_{2}(f(n))=0$ for all $n\in\mathbb{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 $\mathbb{Q}_2$. We must take some care since some quadratics may not have a zero in $\mathbb{Q}_2$.
As discussed in Section~\ref{SecIntro}, 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 $\nu_2(n)$ is completely determined for the sequence. If $\nu_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\in\mathbb{N}$. We then repeat this step as necessary to create the tree. The nodes correspond to the sets $\{2^{i}q+r_{i-1}|q\in\mathbb{N}\}$ where
\begin{equation}\label{2adicRemainder}
r_{i-1}=\sum_{k=0}^{i-1}\alpha_{k}2^{k},
\end{equation}
for fixed coefficients $\alpha_{k}\in\{0,1\}$. This process does not always terminate. If it terminates, we say that the tree is \textit{finite}; otherwise, the tree is \textit{infinite}. We say a node is \textit{non-terminating} if $(\nu_{2}(f(n)))_{n\geq0}$ is non-constant for every $n$ in that equivalence class. We say a node is \textit{terminating} if $(\nu_{2}(f(n)))_{n\geq 0}$ is constant for every $n$ in that equivalence class. In practice, we label the node with this constant valuation.
\begin{figure}
\begin{center}
\begin{tikzpicture}[level 1/.style={sibling distance=4cm},
level 2/.style={sibling distance=6cm}]
\node at ([shift={(0cm,0cm)}]current page.north)[draw](x){$\nu_{2}(f(n))$}
child{node[draw] (a){$\nu_{2}(f(2q+1))$}
child[grow=south,level distance=4cm] {node[draw] (c){$\nu_{2}(f(4q+3))$}}
child[grow=south west,level distance=4cm] {node[draw] (d){$\nu_{2}(f(4q+1))$}}}
child {node[draw] (b){$\nu_{2}(f(2q))$}
child[grow=south,level distance=4cm] {node[draw] (e){$\nu_{2}(f(4q+2))$}}
child[grow=south east,level distance=4cm] {node[draw] (f){$\nu_{2}(f(4q))$}}}
;
\path (x) edge node[fill=white] [draw=none, midway] {$2q+1$} (a);
\path (x) edge node[fill=white][draw=none, midway]{$2q$} (b);
\path (a) edge node[fill=white] [draw=none, midway] {$4q+3$} (c);
\path (a) edge node[fill=white][draw=none, midway]{$4q+1$} (d);
\path (b) edge node[fill=white] [draw=none, midway] {$4q+2$} (e);
\path (b) edge node[fill=white][draw=none, midway]{$4q$} (f);
\end{tikzpicture}
\end{center}
\caption{Levels 0, 1, and 2 of a tree.}
\end{figure}
For each of the remaining five nontrivial cases on the parity of the coefficients $a$, $b$ and $c$, either $(\nu_{2}(f(n)))_{n\geq0}$ produces a finite tree or an infinite tree. We say a finite tree has \textit{$\ell$ levels} if there exists $\ell\in\mathbb{Z}^{+}$ such that for all $r_{\ell-1}\in\{0,1,2,\ldots,2^{\ell}-1\}$ we have $(\nu_{2}(f(2^{\ell}q+r_{\ell-1})))_{q\geq 0}$ constant for all $q\in\mathbb{N}$, and $\ell$ is the smallest possible value. Every node at level $\ell$ in a finite tree has a constant valuation, which depends on $r_{\ell-1}$.
Each node of a tree represents a subsequence of the sequence of 2-adic valuations. A finite tree of $\ell$ levels represents a sequence with period equal to $2^{\ell}$.
In the literature, these finite trees are also called \textit{finite automata.} The sequences generated via the 2-adic valuation are called \textit{2-automatic sequences} and, in particular, the sequences $f(2^{i}q+r)$ are known as the \textit{2-kernel sequences.} See Allouche and Shallit's book~\cite{AlloucheShallit} and Bell's paper~\cite{Bell} for more details.
\subsection{2-adic numbers and selected lemmas}\label{SecLemmas}
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 $\mathbb{Q}$ and extends to $\mathbb{Q}_2$; see Lemma 3.3.2 in~\cite{Gouvea}.
\begin{lemma}\label{SuppLemm1}
Let $x,y\in\mathbb{Q}$, then $\nu_{p}(xy)=\nu_{p}(x)+\nu_{p}(y)$.
\end{lemma}
An element $n$ in $\mathbb{Q}_2$ can be represented in the form
\begin{equation}\label{SuppLemma3.5}
n=\sum_{i=k}^{\infty}\alpha_{i}2^{i}
\end{equation}
where $k=-\nu_{2}(n)$ and $\alpha_{i}\in\left\{0,1\right\}$ for all $i$; it is well-known that this representation is unique.
Lemma~\ref{SuppLemm1} and the construction of $\mathbb{Q}_{2}$ are well-known~\cite{Gouvea}. Medina et al.~\cite{Medina} 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
\begin{equation*}
\mathbb{Z}_{2}=\left\{n\in\mathbb{Q}_{2}:n=\sum_{i=0}^{\infty}\alpha_{i}2^{i}\ \text{where}\ \alpha_{i}\in\left\{0,1\right\}\right\}.
\end{equation*}
\begin{lemma}\label{SuppLemm6}
(\cite{Medina}, Theorem 2.1) Let $f(n)\in\mathbb{Z}[n]$ be a polynomial that is irreducible over $\mathbb{Z}$. Then $(\nu_{2}(f(n)))_{n\geq0}$ is either periodic or unbounded. Moreover, $(\nu_{2}(f(n)))_{n\geq0}$ is periodic if and only if $f(n)$ has no zeros in $\mathbb{Z}_{2}$. In the periodic case, the minimal period length is a power of $2$.
\end{lemma}
We assume that the quadratic $f(n)$ is irreducible because, if not, by Lemma~\ref{SuppLemm1}, $$\nu_p(f(n))=\nu_p(g(n)\cdot h(n))=\nu_p(g(n))+\nu_p(h(n)),$$ where $g(n)$ and $h(n)$ are irreducible.
Therefore, to determine whether $(\nu_{2}(f(n)))_{n\geq0}$ is periodic or unbounded, it suffices to determine if $f(n)$ has zeros in $\mathbb{Q}_2$ and then determine whether the zeros are also in $\mathbb{Z}_{2}$.
The following lemmas will be used in Section~\ref{SecInf} to identify when the square root of a number is in $\mathbb{Z}_{2}$. The version of Hensel's lemma stated below determines when a polynomial in $\mathbb{Z}_{2}[x]$ has zeros in $\mathbb{Z}_{2}$. Lemma~\ref{roots}, which follows from Lemma~\ref{Hensel}, specifically determines whether the polynomial $f(x)=x^{2}-a$ has zeros in $\mathbb{Z}_{2}$.
\begin{lemma}\label{Hensel}
(Hensel's lemma,~\cite[Sec.~6.4]{Robert}) Assume that $P\in\mathbb{Z}_{2}[x]$ and $x_{0}\in\mathbb{Z}_{2}$ satisfies \begin{equation*}
P(x_{0})\equiv\modd{0} {2^{n}}
\end{equation*}
If $\phi=\nu_{2}(P'(x_{0}))0$, then we can write $\Delta=1+8j=1-8(-j)$ where $j\in\mathbb{N}$.
Thus in either case $\Delta=1-8j$ where $j\in\mathbb{Z}$. Then
it follows that $\sqrt{4k^{2}-4ac}=2^{\ell}\sqrt{1-8j}$. By Lemma~\ref{roots}, $\sqrt{1-8j}$ is in $\mathbb{Z}_{2}$. Furthermore, since the denominator of $x$ is odd this also guarantees that $x\in\mathbb{Z}_{2}$. Therefore, there are two infinite branches, one corresponding to each root.
\end{proof}
\begin{corollary}\label{InfSpecCor}
Under the conditions of Proposition~\ref{InfSpecThm}, if $b^{2}-4ac=0$, the tree has one infinite branch.
\end{corollary}
\begin{proof}
In this case (3(a) of Theorem~\ref{MainThm1}) roots take the form $x=-\frac{b}{2a}$. Since $b=2k$, then $x=-\frac{k}{a}$ which has 2-adic form $x=\sum_{i=0}^{\infty}\alpha_{i}2^{i}$ where $\alpha_{i}$ is either 0 or 1. This guarantees that the one branch is infinite.
\end{proof}
\begin{remark}
Note the connection between subsequences of $(\nu_2(f(n)))_{n\geq 0}$ and the infinite branches of a tree.
Proposition~\ref{InfCase1} asserts that for all $i\in\mathbb{Z}^{+}$ there exists exactly one subsequence of the form $n=2^{i}q+r_{i-1}$ such that $\nu_{2}(f(n))\geq i$ and exactly one subsequence of the form
$n=2^{i}q+r_{i-1}^{*}$ with $\nu_{2}(f(n))=i-1$. Similarly, Proposition~\ref{InfCase2} asserts that for all $i\in\mathbb{Z}^{+}$ there are exactly two subsequences corresponding to $n=2^{i}q+r_{i-1}$ such that $\nu_{2}(f(n))\geq i+1$ and exactly two subsequences of the form $n=2^{i}q+r_{i-1}^{*}$ with $\nu_{2}(f(n))=i$. For $r_{i-1}$ and $r_{i-1}^{*}$, the representations presented in equation (\ref{2adicRemainder}) of Section~\ref{SecParityandTrees} equate the coefficients $\alpha_{k}$ and $\alpha_{k}^{*}$ for all $0\leq k\leq i-2$, and
meanwhile $\alpha_{i-1}^{*} \equiv \modd{\alpha_{i-1}+1} {2}$.
As for the cases of Proposition~\ref{InfSpecThm} and Corollary~\ref{InfSpecCor}, we can apply Lemma~\ref{SuppLemm6} to conclude that these sequences are unbounded. Much like Propositions~\ref{InfCase1} and~\ref{InfCase2}, we can say that the results of Proposition~\ref{InfSpecThm} yield that for all $i\in\mathbb{N}$ there are exactly two subsequences of the form $n=2^{i}q+r_{i-1}$, where $(\nu_{2}(f(n)))_{n\geq 0}$ is not constant, while Corollary~\ref{InfSpecCor} asserts there is exactly one such subsequence.
\end{remark}
\section{Bounded cases and finite trees}\label{BoundedSection}
In this section, we prove Case 3(c) of Theorem~\ref{MainThm1} and the first part of Theorem~\ref{MainThm2}. The coefficients of these quadratics satisfy the following: $a$ is odd and $b$ is even, and $b^{2}-4ac=4^{\ell}\Delta$, where $\ell\in\mathbb{Z}^+$ is as large as possible, $\Delta\equiv\modd{m} {8}$, and $m\in\{2,3,5,6,7\}$. Their trees are finite with $\ell$ levels. We can again apply the reasoning of the proof of Proposition \ref{InfSpecThm}.
If $\Delta<0$ we can naturally write $\Delta=m-8j$ where $j\in\mathbb{N}$ and if $\Delta>0$ then we write $\Delta=m+8j=m-8(-j)$ where $j\in\mathbb{N}$ or $j=0$. Henceforth, we will write $\Delta=m-8j$ where $j\in\mathbb{Z}$. Again, by Lemma~\ref{roots} functions of the form $g(x)=x^{2}-(m-8j)$ do not have a zero in $\mathbb{Z}_{2}$. By Lemma~\ref{SuppLemm6}, the corresponding valuation sequences are periodic. Figures~\ref{fig:Ex5} and~\ref{fig:Ex6} 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~\ref{MainThm1}, where $a$ is odd and $b$ is even, we have the condition that $\ell$ is as large as possible. This corresponds to factoring out as many powers of 4 as possible, ruling out the possibilities $m\in\{0,4\}$. Now if $m=1$ (Case 3(b), covered in
Section~\ref{SecInf}), an infinite tree is created. This leaves the cases $m\in\{2,3,5,6,7\}$. As discussed above, the zeros of these quadratic functions are not elements of $\mathbb{Q}_{2}$; therefore, their trees must be finite. The proofs of the next two propositions follow the proofs of Propositions~\ref{InfCase1} and~\ref{InfCase2}.
\begin{proposition}\label{FinThm}
If $a$ is odd and $b$ is even, and $b^{2}-4ac=4^{\ell}\Delta$ where $\ell\in\mathbb{Z}^+$ is as large as possible, $\Delta\equiv\modd{m} {8}$, and $m\in\{2,3,5,6,7\}$, then the 2-adic valuation tree of $f(n)$ is finite with $\ell$ levels.
\end{proposition}
The proof of this proposition is broken down into Lemmas~\ref{FinLem1},~\ref{FinLem2}, and~\ref{FinLem3}. Unless stated otherwise, let $b=2k$ for some $k\in\mathbb{Z}$. Lemma~\ref{FinLem1} covers the case $\ell=1$, in which the 2-adic valuation tree has exactly one level. Lemmas~\ref{FinLem2} and~\ref{FinLem3} describe valuations for finite trees with more than one level; Lemma~\ref{FinLem3} describes the valuation at the final level and Lemma~\ref{FinLem2} describes the other levels. Under the assumptions of Proposition~\ref{FinThm}, with $a$ odd and $b$ even, we complete the square and use properties of the $p$-adic valuation to obtain $\nu_{2}(an^{2}+bn+c)=\nu_{2}((an+k)^{2}-k^{2}+ac)$.
\begin{lemma}\label{FinLem1}
Let $\ell=1$, i.e., $b^{2}-4ac=4\Delta$, $\Delta\equiv\modd{m} {8}$, and $m\in\{2,3,5,6,7\}$. If $m\in\{2,7\}$ and $b\equiv\modd{0} {4}$ or if $m\in\{3,6\}$ and $b\equiv\modd{2} {4}$, then
\begin{displaymath}
\nu_{2}(an^{2}+bn+c)=\begin{cases}
0,&\ \text{if}\ n\ \text{even};\\
1,&\ \text{if}\ n\ \text{odd}.
\end{cases}
\end{displaymath}
If $m\in\left\{3,6\right\}$ and $b\equiv\modd{0} {4}$ or if $m\in\left\{2,7\right\}$ and $b\equiv\modd{2} {4}$, then
\begin{displaymath}
\nu_{2}(an^{2}+bn+c)=\begin{cases}
1,&\ \text{if}\ n\ \text{even};\\
0,&\ \text{if}\ n\ \text{odd}.
\end{cases}
\end{displaymath}
If $m=5$ and $b\equiv\modd{0} {4}$, then
\begin{displaymath}
\nu_{2}(an^{2}+bn+c)=\begin{cases}
0,&\ \text{if}\ n\ \text{even};\\
2,&\ \text{if}\ n\ \text{odd}.
\end{cases}
\end{displaymath}
If $m=5$ and $b\equiv\modd{2} {4}$, then
\begin{displaymath}
\nu_{2}(an^{2}+bn+c)=\begin{cases}
2,&\ \text{if}\ n\ \text{even};\\
0,&\ \text{if}\ n\ \text{odd}.
\end{cases}
\end{displaymath}
\end{lemma}
\begin{proof}
Using the convention that $\Delta=m-8j$ where $j\in\mathbb{Z}$ and $m\in\left\{2,3,5,6,7\right\}$, consider the case where $m=7$ and $b\equiv\modd{2} {4}$. Then, since $b=2k$, we have $k$ odd. If $n$ is even, then $(an+k)^2\equiv\modd{ k^{2}} {2}$ and so it follows that
$$((an+k)^{2}-k^{2}+ac) \equiv k^2-7 \equiv -6 \equiv \modd{0} {2},$$
but
$$((an+k)^{2}-k^{2}+ac)\equiv k^2-7 \equiv -6 \equiv \modd{2} {4}.$$
Therefore $\nu_{2}(an^{2}+bn+c)=1$ when $n$ is even. Similarly, when $m=7$ and $b\equiv\modd{2} {4}$ if $n$ is odd, then $(an+k)^{2}$ is even.
Therefore,
$(an+k)^{2}-k^{2}+ac \equiv -7 \equiv \modd{1} {2}$.
Thus $\nu_{2}(an^{2}+bn+c)=0$ when $n$ is odd.
Now consider the case where $m=7$ and $b\equiv\modd{0}
{4}$. We have $b=2k$ with $k$ even. Thus, if $n$ is odd we have
$$(an+k)^{2}-k^{2}+ac \equiv -6\equiv \modd{0} {2} $$
and
$$(an+k)^{2}-k^{2}+ac \equiv k^2-7 \equiv -6 \equiv \modd{2} {4}.$$
Thus $\nu_{2}(an^{2}+bn+c)=1$ when
$n$ is odd. When $n$ is even we have $(an+k)^{2}-k^{2}+ac
\equiv -7 \equiv \modd{1} {2}$. Thus $\nu_{2}(an^{2}+bn+c)=0$ when $n$
is even.
The cases of $m\in\{2,3,6\}$ when $b\equiv\modd{0} {4}$ or $b\equiv\modd{2} {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\in\mathbb{Z}$. 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, $\nu_{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\equiv\modd{1} {4}$, and this implies
$$
(an+k)^2-5+8j \equiv 1-5+8j \equiv -4+8j \equiv\modd{0} {4}.
$$
Thus, $\nu_{2}(an^{2}+bn+c)\geq 2$. \\
Since $(an+k)$ is odd, let $an+k=2d+1$, for some $d\in \mathbb{Z}$. Then,
\begin{align*}
(an+k)^2-5+8j &= (2d+1)^2-5+8j\\
&\equiv\modd{4(d^2+d-1)} {8}.
\end{align*}
Observe that $d^2+d-1$ is odd, regardless of whether $d$ is even or odd. Thus, $\nu_{2}(an^{2}+bn+c)<3$. Therefore,
$\nu_{2}(an^{2}+bn+c)=2$.
\end{proof}
\begin{lemma}\label{FinLem2}
Under the assumptions of Proposition~\ref{FinThm} (Case 3(c) of Theorem~\ref{MainThm1}) let $\ell\geq 2$ and suppose $0*=triangle 45,x=1cm,y=1cm]
\draw [line width=0.8pt] (0,7)-- (-1,6);
\draw [line width=0.8pt] (0,7)-- (1,6);
\draw [fill=black] (0,7) circle (1pt);
\draw [fill=black] (-1,6) circle (1pt);
\draw [fill=black] (1,6) circle (1pt);
\draw [line width=0.8pt] (-1,6)-- (-2,5);
\draw [line width=0.8pt] (-1,6)-- (0,5);
\draw [fill=black] (0,5) circle (1pt);
\draw [fill=black] (-2,5) circle (1pt);
\draw [line width=0.8pt] (-2,5)-- (-3,4);
\draw [line width=0.8pt] (-2,5)-- (-1,4);
\draw [fill=black] (-3,4) circle (1pt);
\draw [fill=black] (-1,4) circle (1pt);
\draw [line width=0.8pt,dotted] (-3,4)-- (-5,2);
\draw [line width=0.8pt] (-5,2)-- (-6,1);
\draw [line width=0.8pt] (-5,2)-- (-4,1);
\draw [fill=black] (-5,2) circle (1pt);
\draw [fill=black] (-6,1) circle (1pt);
\draw [fill=black] (-4,1) circle (1pt);
\end{tikzpicture}
\end{equation*}
\caption{The form of trees of type $(\ell,1)$.}
\label{fig:ell_1_tree}
\end{figure}
\vspace{0.2in}
Here, we suppose that $\ell\geq2$ because $\ell=1$ creates a tree with one level, see Lemma~\ref{FinLem1}, and the directional behavior we seek to classify is not defined. The conditions $4a^2-4ac=4^{\ell}\Delta$ for $\ell\in\mathbb{Z}^+$ as large as possible, $\Delta\equiv\modd{m} {8}$, and $m\in\{2,3,5,6,7\}$ imply $c$ must be odd.
\begin{proposition}\label{FinPropStruc3}
Under the assumptions of Proposition~\ref{FinThm}, if $c$ is odd and $\ell\geq2$ is an integer, then a quadratic of the form $f(n)=an^{2}+2an+c$ creates a tree that is of type $(\ell,1)$. Furthermore, we have
\begin{displaymath}
\nu_{2}(f(n))=\begin{cases}
0,&\ \text{if}\ n\equiv\modd{0} {2};\\
2(i-1),&\ \text{if}\ n\equiv\modd{\sum_{k=0}^{i-2}2^{k}} {2^{i}}\ \text{with}\ 2\leq i<\ell;\\
2(\ell-1),&\ \text{if}\ n\equiv\modd{\sum_{k=0}^{\ell-2}2^{k}} {2^{\ell}}\ \text{and}\ m=6,2;\\
2\ell-1,&\ \text{if}\ n\equiv\modd{\sum_{k=0}^{\ell-2}2^{k}} {2^{\ell}}\ \text{and}\ m=7,3;\\
2\ell,&\ \text{if}\ n\equiv\modd{\sum_{k=0}^{\ell-2}2^{k}} {2^{\ell}}\ \text{and}\ m=5;\\
2\ell-1,&\ \text{if}\ n\equiv\modd{\sum_{k=0}^{\ell-1}2^{k}} {2^{\ell}}\ \text{and}\ m=6,2;\\
2(\ell-1),&\ \text{if}\ n\equiv\modd{\sum_{k=0}^{\ell-1}2^{k}} {2^{\ell}}\ \text{and}\ m=7,5,3.
\end{cases}
\end{displaymath}
\end{proposition}
\begin{proof}
In light of Lemma~\ref{FinLem2}, 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 $\ell^{th}$ level) or one node is non-terminating and the other is terminating. So in order to show that the tree is of type $(\ell,1)$, we only need to confirm that nodes corresponding to $n=2^{i}q+2^{i-1}+\cdots+2^{1}+2^{0}$, where $1\leq i\leq\ell$, are always non-terminating. Since $a$ is odd, completing the square and using the convention that $4a^{2}-4ac=4^{\ell}\Delta$ where $\Delta=m-8j$ where $j\in\mathbb{Z}$ gives
\begin{align*}
\nu_{2}(f(n))&=\nu_{2}(an^{2}+2an+c)=\nu_{2}(a(n+1)^{2}-a+c)\\
&=\nu_{2}(a^{2}(n+1)^{2}-a^{2}+ac)=\nu_{2}(a^{2}(n+1)^{2}-4^{\ell-1}(m-8j))\\
&=\nu_{2}(a^{2}(2^{i}q+2^{i-1}+2^{i-2}+\cdots+2+1+1)^{2}-4^{\ell-1}(m-8j))\\
&=\nu_{2}(a^{2}(2^{i}q+2^{i})^{2}-4^{\ell-1}(m-8j))\\
&=\nu_{2}(a^{2}4^{i}(q+1)^{2}-4^{\ell-1}(m-8j)).
\end{align*}
If $q$ is odd, then $n=2^{i}q+2^{i-1}+\cdots+2^{1}+2^{0}$ is the non-terminating node, provided $i<\ell$, and produces two nodes one of which does not terminate. If $i=\ell$, then both nodes terminate by Proposition~\ref{FinThm}.
The nodes that terminate are of the form $n=2^{i}q+2^{i-2}+\cdots+2^{1}+2^{0}$ when $1\leq i<\ell$. The case when $n=2q$ is handled by the proof of Lemma~\ref{FinLemStruc2}. For the case $1*