# Single Molecule Structure of Partially Digested Kinetoplast DNA Networks

Saminathan Ramakrishnan  School of Physics and Astronomy, University of
Edinburgh  Zihao Chen  School of Biological Sciences, Ashworth laboratories,
Institute for Immunology and Infection Research, University of Edinburgh  Yair
Augusto Gutierrez Fosado  School of Physics and Astronomy, University of
Edinburgh  Luca Tubiana  Physics Department, University of Trento  Willem
Vanderlinden  School of Physics and Astronomy, University of Edinburgh
Nicholas Jon Savill  School of Biological Sciences, Ashworth laboratories,
Institute for Immunology and Infection Research, University of Edinburgh
Achim Schnaufer  School of Biological Sciences, Ashworth laboratories,
Institute for Immunology and Infection Research, University of Edinburgh
Davide Michieletto  School of Physics and Astronomy, University of Edinburgh
MRC Human Genetics Unit, Institute of Genetics and Cancer, University of
Edinburgh

# Topological Digestion of Kinetoplast DNA Networks Yield Perturbed
Morphologies

Saminathan Ramakrishnan  School of Physics and Astronomy, University of
Edinburgh  Zihao Chen  School of Biological Sciences, Ashworth laboratories,
Institute for Immunology and Infection Research, University of Edinburgh  Yair
Augusto Gutierrez Fosado  School of Physics and Astronomy, University of
Edinburgh  Luca Tubiana  Physics Department, University of Trento  Willem
Vanderlinden  School of Physics and Astronomy, University of Edinburgh
Nicholas Jon Savill  School of Biological Sciences, Ashworth laboratories,
Institute for Immunology and Infection Research, University of Edinburgh
Achim Schnaufer  School of Biological Sciences, Ashworth laboratories,
Institute for Immunology and Infection Research, University of Edinburgh
Davide Michieletto  School of Physics and Astronomy, University of Edinburgh
MRC Human Genetics Unit, Institute of Genetics and Cancer, University of
Edinburgh

# Single-Molecule Morphology of Topologically Digested Olympic Networks

Saminathan Ramakrishnan  School of Physics and Astronomy, University of
Edinburgh  Zihao Chen  School of Biological Sciences, Ashworth laboratories,
Institute for Immunology and Infection Research, University of Edinburgh  Yair
Augusto Gutierrez Fosado  School of Physics and Astronomy, University of
Edinburgh  Luca Tubiana  Physics Department, University of Trento  Willem
Vanderlinden  School of Physics and Astronomy, University of Edinburgh
Nicholas Jon Savill  School of Biological Sciences, Ashworth laboratories,
Institute for Immunology and Infection Research, University of Edinburgh
Achim Schnaufer  School of Biological Sciences, Ashworth laboratories,
Institute for Immunology and Infection Research, University of Edinburgh
Davide Michieletto  School of Physics and Astronomy, University of Edinburgh
MRC Human Genetics Unit, Institute of Genetics and Cancer, University of
Edinburgh

###### Abstract

The kinetoplast DNA (kDNA) is the archetype of a two-dimensional Olympic
network, composed of thousands of DNA minicircles and found in the
mitochondrion of certain parasites. The evolution, replication and self-
assembly of this structure are fascinating open questions in biology that can
also inform us how to realise synthetic Olympic networks in vitro. To obtain a
deeper understanding of the structure and assembly of kDNA networks, we
sequenced the Crithidia fasciculata kDNA genome and performed high-resolution
Atomic Force Microscopy (AFM) and analysis of kDNA networks that had been
partially digested by selected restriction enzymes. We discovered that these
topological perturbations lead to networks with significantly different
geometrical features and morphologies with respect to the unperturbed kDNA,
and that these changes are strongly dependent on the class of DNA circles
targeted by the restriction enzymes. Specifically, cleaving maxicircles leads
to a dramatic reduction in network size once adsorbed onto the surface, whilst
cleaving both maxicircles and a minor class of minicircles yields non-circular
and deformed structures. We argue that our results are a consequence of a
precise positioning of the maxicircles at the boundary of the network, and we
discuss our findings in the context of kDNA biogenesis, design of artificial
Olympic networks and detection of in vivo perturbations.
Keywords: kinetoplast DNA, atomic force microscopy, topology, Olympic
networks.

The mitochondrial genome of Kinetoplastid parasites displays one of the most
unique and complex topologies in nature Simpson (1967); Laurent and Steinert
(1970); Shlomai and Zadok (1983); Pérez-Morga and Englund (1993); Shlomai
(1994); Morris  _et al._ (2001); Lukes  _et al._ (2002). The so-called
“kinetoplast DNA” (i.e. associated with the cellular body, or “plastos”, near
the parasite flagellum that give it its movement, or “kinetikos”) is a unique
genome with a complex topology. In the organism C. fasciculata, it is formed
by around 5000 interlinked DNA minicircles (2.5 kb), and around 30 larger DNA
maxicircles (30 kb). The DNA rings are assembled and replicated into a two-
dimensional (2D) network and contained in a membraneless DNA-dense region of
$1\mu$m $\times$ $0.4\mu$m within the mitochondrion. The maxicircles mostly
encode rRNAs and mRNAs for oxidative phosphorylation and mitoribosomes, while
the minicircles encode guide RNA genes required for post-transcriptional
editing of the mRNAs Simpson (1967); Simpson  _et al._ (2000); Hajduk and
Ochsenreiter (2010). Kinetoplast DNA replication and biogenesis are not
understood and are topics of intense debate in the parasitology community
Pérez-Morga and Englund (1993); Liu  _et al._ (2005); Klingbeil  _et al._
(2001); Hoffmann  _et al._ (2018); Schnaufer (2010); Kalichava and
Ochsenreiter (2021); Amodeo  _et al._ (2021, 2022).

There are several open questions in the field of Trypanosome and Kinetoplastid
biology; for instance, it is unclear (i) how kDNA was evolutionarily preferred
over other simpler forms of genomes (for instance longer DNA rings, as in
human mitochondria) and (ii) whether each genetic class of rings (e.g.
maxicircles and minicircles) occupy specific and distinct positions within the
kDNA structure or whether they are uniformly and randomly dispersed Lukes  _et
al._ (2005). Interestingly, a strain of Trypanosome Brucei can be evolved –
under certain conditions – to survive and replicate without kDNA Schnaufer
_et al._ (2002); Schnaufer (2010). Overall, there are a number of unanswered
questions about the evolutionary advantage of this structure and whether it is
limited to a specific life stage of the parasite.

Recently, the bio- and polymer physics community used C. fasciculata kDNA as
archetype of a 2D polymer, which is otherwise challenging to realise
synthetically Soh  _et al._ (2020); Soh and Doyle (2021); Klotz  _et al._
(2020); Yadav  _et al._ (2023). In general, the polymer physics of networks of
interlinked rings, be it 1D, 2D or 3D, have not been studied thoroughly mainly
because of experimental challenges Grosberg (2020); Tubiana  _et al._ (2022).
Thus, it remains rather overlooked how the topology of so-called “Olympic”
networks affects their material properties, although preliminary works suggest
that they may display unique features, such as strong non-linear stress
response Vilgis and Otto (1997); Wu  _et al._ (2017), weaker swelling Fischer
_et al._ (2015); Lang  _et al._ (2014), percolation Igram  _et al._ (2016);
Diao  _et al._ (2012); Michieletto  _et al._ (2014) and active elastic tuning
Kim  _et al._ (2013); Krajina  _et al._ (2018). Linking this back to the
biogenesis of kDNA in Kinetoplastids, it remains to be determined which – if
any – of these properties are required for the biological functions of kDNA in
the cell.

Simulations of polymer rings with tunable linking degree suggest that a mean
linking degree, or valence, of 3 – similar to that found in kDNA structures
Chen  _et al._ (1995); Ibrahim  _et al._ (2019); He  _et al._ (2023) – may
reflect the fact that these networks are poised at the percolation point,
where a random graph starts displaying a system-spanning component Michieletto
_et al._ (2014); Diao  _et al._ (2012); Ubertini and Rosa (2023). In fact, a
random graph with valence 3 is optimally connected, i.e. it displays
percolation but without redundant links between circles, thus ensuring
integrity of the structure whilst optimising the rate of replication, which in
C. fasciculata occurs through decatenation of minicircles from the network
Michieletto  _et al._ (2014); Pérez-Morga and Englund (1993). At the same
time, whilst the material and elastic properties of kDNA networks are still
largely unknown, recent work has estimated the bending stiffness to be in the
range of $\kappa\simeq 10^{-21}-10^{-19}J$ He  _et al._ (2023); Klotz  _et
al._ (2020) and in-plane Young modulus $Y\simeq 0.1$ pN/$\mu$m He  _et al._
(2023). Since the elasticity of an Olympic network correlates with the mean
linking number Vilgis and Otto (1997); Ubertini and Rosa (2023); Palombo  _et
al._ (2023), we expect that the kDNA elasticity will strongly depend on its
underlying topology.

To achieve a better understanding of the connection between material
properties and underlying topology, precise single-molecule measurements of
experimental Olympic structures are needed. To date, the only synthetic
Olympic structures were 1D polycatenanes Wu  _et al._ (2017); Datta  _et al._
(2020); Peil  _et al._ (2020), and bulk 3D Olympic gels Kim  _et al._ (2013);
Krajina  _et al._ (2018) – the latter made from DNA plasmids and type 2
topoisomerase. Despite these recent advances in the synthesis of catenated
structures, there is no experimental method that can precisely quantify the
topology of an Olympic network (especially 3D ones). Qualitative single
molecule characterisation of kDNA networks have been performed using electron
microscopy Laurent and Steinert (1970); Barker (1980); Ferguson  _et al._
(1994) and more recently atomic force microscopy (AFM) Cavalcanti  _et al._
(2011); Yaffe  _et al._ (2021).

In our most recent AFM study He  _et al._ (2023) we performed quantitative
image analysis and discovered that AFM, coupled to molecular dynamics
simulations, can provide insights into the topology of Olympic networks at
single molecule resolution. In this work, we use AFM, quantitative image
analysis and polymer theory to understand more about the structure of kDNA and
Olympic networks in general. Specifically, by exploiting the fact that
catenated DNA circles can be cleaved by sequence-specific restriction enzymes,
we perturb the topology of the network and measure the changes in network
morphology. Whilst topological perturbations to kDNA have been explored in the
literature (see Refs. Chen  _et al._ (1995); Yadav  _et al._ (2023); Ragotskie
_et al._ (2023)), existing works have not quantitatively measured changes in
network morphologies. More specifically, (i) Cozzarelli and co-authors were
able to correctly determine the average valence of _C. fasciculata_ kDNA by
progressively linearising some of its minicircles with XhoI restriction enzyme
Chen  _et al._ (1995); (ii) Yadav and co-authors measured the shape auto-
correlation, and hence the relaxation properties, of networks that had been
treated with different restriction enzymes via imaging and discovered that
more digested structures had a longer relaxation time, in line with a
reduction in network connectivity Yadav  _et al._ (2023); (iii) Ragotskie and
co-authors caused light-induced nonspecific damage to C. fasciculata kDNA and
observed the persistence of a 1D edge-loop, consistent with the estimation
that the kDNA border is at least 4-fold redundantly linked with respect to the
inner minicircles Ragotskie  _et al._ (2023). In our work we wanted to
complement these studies and provide a single-molecule view of kDNA networks
that underwent specific topological perturbations.

To achieve accurate and specific topological perturbations, we first deep
sequenced C. fasciculata kDNA and discovered that it contains 18 classes of
minicircles, the most abundant of these covering 85% of the network. Through
the sequencing, we were able to identify specific restriction endonucleases
(REs) that digest different parts of the kDNA structure. We then employed some
of these REs to partially digest kDNA and discovered that, for instance,
cleaving maxicircles unexpectedly yields significantly shrunk networks. On the
contrary, cleaving both the minor class ($\sim$ 10% of total) and maxicircles
yields significantly larger and non-circular structures. We qualitatively
explain these findings with a scaling theory, as kDNA networks with less mass
ought to display weaker adsorption to the surface whilst less connected
networks are expected to display a weaker bulk modulus and to extend more
along the surface. Finally, by cleaving all, and only, minicircles we
discovered that most of the maxicircles in the kDNA are interlinked with each
other. We argue that our results shed some light on this fascinating and
unique structure and potentially inform assembly strategies to synthetically
design 2D Olympic networks.

Figure 1:  a Minicircles relative copy number from C. fasciculata kDNA
sequencing and assembly (see methods). b Table with examples of restriction
enzymes that can partially digest (+) or not (-) kDNA components (see SI for a
full table with 243 enzymes). $\pm$ denotes digest of some of the “other”
classes. c Protocol for preparation of clean samples of partially digested
kDNA: we load partially digested samples in wells and run gel electrophoresis
in a 1.5% agarose gel at 10V/cm for 20 minutes. The intact and partially
digested kDNA structures are too big to travel through the gel and remain
stuck in the wells. We flush the wells and recover the partially intact kDNA,
which are now cleaned from linearised products and enzymes. d Gel
electrophoresis showing partially digested kDNA samples. Linearised maxi
circles (MC) run at about 30 kbp, while minicircles (mc) run at 2.5 kbp. e
From left to right: images of undigested, BssHII-, PstI- and EcoRI-treated
samples. The height color scale is the same throughout the paper. At the
bottom, we show colorcoded sketches of the networks: blue, maxicircle; orange,
major minicircle class; green, 1st minor minicircle class; red and grey, 2nd
and other minicircle classes.

##  I Results

###  I.1 Deep Sequencing of C. fasciculata kDNA reveals 18 classes of
minicircles

Kinetoplast DNA from C. fasciculata was purchased from Inspiralis at 100
ng/$\mu$l in TE buffer (10 mM Tris-HCl pH7.5, 1 mM EDTA). A sample of kDNA was
sent for deep sequencing at NovoGene. We then performed de novo DNA assembly
of 4.7 million pair-end reads (150 bp) using KOMICS Geerts  _et al._ (2021).
We performed several quality checks, including searching for the universally
conserved minicircle sequence CSB3 (GGGGTTGGTGT) and comparing our contigs
with known sequences of CfC1 Sugisaki and Ray (1987), T. congolense and T.
brucei Cooper  _et al._ (2019) (see Methods). Overall, the final assembly
incorporated over 96% of all the 4.7 million reads and displayed complete
coverage. We detected 18 distinct classes of minicircles with less than 75%
sequence identity, and their relative abundance was estimated from mean read
depth calculated by samtools Li  _et al._ (2009). The major class composes
85.2% of the kDNA, a first minor class 10.9%, a second minor class 1.8% and
the other classes make up about 2.1% of the kDNA (Fig. 1a). Assuming that the
kDNA network contained 5000 minicircles, we estimated 9 to 10 maxicircles per
network Chen  _et al._ (1995).

C. fasciculata maxicircle genes boundaries were predicted with Leishmania
major maxicircle annotation to extract unedited genes. We used published
transcriptomic data of C. fasciculata from in vitro culture and mosquito
hindguts to validate unedited maxicircle gene annotations and predict edited
encrypted genes Filosa  _et al._ (2019). T-masked mapping using T-aligner
Gerasimov  _et al._ (2018) suggested that CfC1 capable of editing four cryptic
genes: ATPase subunit 6 (A6), ribosomal protein S12 (RPS12 or uS12m), NADH
dehydrogenase subunit 7 (ND7), and cytochrome oxidase subunit 2 (COXII). Guide
RNAs were identified on 13 out of 18 minicircle classes, which captured the
same gRNAs on contigs containing the annotated minicircle fragments in
previous study Gerasimov  _et al._ (2018). However, no gRNA was found on the
major and the 1st minor minicircle classes.

Finally, RE cutting sites on C. fasciculata minicircles and maxicircle were
predicted for enzymes available from New England Biolabs (see Fig. 1b and SI
for a full table). Specifically, we chose BssHII as negative control, PstI as
cutting maxicircles and a small $<4\%$ fraction of minicircles, EcoRI cutting
maxicircles and around 13% of the minicircles and finally BmrI, cutting all,
and only, minicircles. Through these enzymes, we specifically implement
topological perturbations to the kDNA structure with the aim of quantifying
specific changes in their morphology via Atomic Force Microscopy.

Figure 2:  a-b Example AFM images of control and EcoRI treated samples. Scale
bar is 2 $\mu$m. c Boxplot showing the circularity $\Gamma$. Smaller
$\Gamma=4\pi(\textrm{area}/\textrm{perimeter}^{2})$ indicate that the
perimeter is longer than the one of a perfect circle and it quantifies
irregular kDNA borders. d Boxplot showing aspect ratio $\Delta=M/m$ between
major and minor axes. Lower aspect ratios indicate shapes with more similar
major and minor axes. EcoRI digested structures display more irregular borders
but the overall shape is less ellipsoidal and more circular.

###  I.2 Preparation of partially digested kDNA for AFM

For restriction digestion with EcoRI, PstI and BssHII, 1 $\mu$L of enzyme (10
Units) was used to digest 1 $\mu$g of kDNA in 1X rCutsmart buffer, overnight
at 37∘C. The BssHII-treated sample was also incubated at 50∘C for 2 hours
prior to overnight incubation at 37∘C, as per NEB recommendation. We found
that during the AFM sample preparation, the mica surface was quickly covered
by recombinant albumin in rCutSmart buffer and restriction digested mini and
maxicircles, particularly at high magnesium concentration. Thus, enzyme-
treated partially digested kDNA structures were poorly adsorbed on the mica
surface. To solve this issue, we developed a methodology to remove linearised
mini and maxicircles, enzymes and albumin for AFM sample preparation as
follows (see also Fig. 1c): the kDNA sample was first prestained with diluted
SybrGold and ran in 1.5% agarose gel at about 10 V/cm for 20 minutes (see Fig.
1c,d). The gel tray was then removed from the tank and placed on a UV
transilluminator. 1X TE buffer in the well was gently pipetted out and
replaced with 80 $\mu$L of adsorption buffer (10 mM Tris-HCl pH 7.9, 10 mM
MgCl2, 1 mM EDTA). This step was repeated twice and 50 $\mu$L of adsorption
buffer was left in the well after the second wash. Under UV light, a
fluorescent layer was visible on the wall of the well; this is because the
kDNA structure contains thousands of DNA rings that can individually travel
through the gel, but remain stuck in the well when linked with each other in
the (partially) intact kDNA (Fig. 1d). More specifically, we found that the
kDNA becomes weakly adsorbed on the wall of the well and is easily removable
by washing. The kDNA was either gently flushed using a pipette with 10-20
$\mu$L of adsorption buffer or gently touched with a pipette tip to resuspend
the kDNA back into the buffer. We took utmost care to avoid disrupting kDNA
integrity at this stage. After resuspension, a 50 $\mu$L of sample was
recovered and adsorbed on freshly cleaved mica for 10 minutes. The sample was
dip washed in ultra-pure water for 1 minute and gently air-dried in ultrapure
nitrogen stream (see Fig. 1e and SI for example images).

Figure 3:  a-b Examples of AFM images of control and PstI treated samples
(scale bar is 2 $\mu$m). c Boxplot of the diameter $d=\sqrt{\textrm{area}}$ of
kDNAs. d Schematics sketching weak (top) and strong (bottom) adsorption of
kDNA to the mica. e Boxplot of the average median height of the kDNA
structures for control and PstI-treated samples (see SI for details).

###  I.3 Partially digested structures display irregular borders

First, we noticed that EcoRI-treated networks (missing all maxicircles and
around 13% of minicircles) appeared structurally disrupted, while the others
were, in first approximation, largely unperturbed (Fig. 1e). To quantify this
change in morphology we measured the circularity $\Gamma$ and aspect ratio
$\Delta$ (see Fig. 2). To obtain these two quantities, we manually traced the
closed contour of the kDNA structures in ImageJ, and computed the circularity
as $\Gamma=4\pi(A/p^{2})$, where $A$ is the area of the closed curve and $p$
its perimeter, while the aspect ratio as $\Delta=M/m$ where $M$ and $m$ are
the major and minor axes of a fitted ellipse. A value of $\Gamma=1$ indicates
that the perimeter is that of a perfect circle, whilst $\Gamma<1$ indicates
longer, typically irregular, perimeters. At the same time, $\Delta$ refers to
the shape of the overall object, with $\Delta=1$ indicating an object with
near circular symmetry, while $\Delta\simeq 0$ indicating a rod.

As shown in Fig. 2c, we observe a significant (p-value $<0.001$) decrease in
circularity in both PstI and EcoRI treated samples, but no significant change
of $\Gamma$ in our BssHII control. The value of $\Gamma$ drops from near 1 for
the control to below 0.9 for EcoRI treated samples, reflecting the appearance
of irregular kDNA borders, almost “blebbing”, visually evident in the AFM
images (Fig. 2a-b). Additionally, we find a decrease, albeit more modest, in
the aspect ratio $\Delta$ reflecting more symmetric structures, with a smaller
difference between major and minor axes (Fig. 2d). This confirms that the
control samples are somewhat ellipsoidal with a well defined major axis
roughly 20% longer than the minor axis.

Interestingly, the fact that PstI-treated samples show a minor change in
circularity $\Gamma$ suggest that they contribute to the structural integrity
of the network, especially of the border. It is also interesting to note at
this stage that the mass contribution of maxicircles is about 2.3%, i.e.
around 200 $10^{3}$ kg/mol within a total of 8.5 $10^{6}$ kg/mol for the whole
kDNA. Fig. 2c then suggests that cleaving both maxicircles and the minor class
of minicircles (in total about 15% of the kDNA mass) has a compound effect in
the network morphology likely due to a decrease in network connectivity Chen
_et al._ (1995); Yadav  _et al._ (2023).

###  I.4 Cleaving maxicircles yields significantly shrunk networks

To understand the specific structural role of maxicircles, we decided to focus
on PstI-treated kDNA structures, which lack maxicircles and a small ($<4\%$)
fraction of minicircles. First, we validated in our agarose gel that a small
number of minicircles are cleaved along with maxicircles in PstI-treated
samples (Fig. 1d). Second, and more importantly, we observe that PstI
treatment causes a dramatic reduction in kDNA area $A$, or diameter
$d=\sqrt{A}$, from around $d=8$ $\mu$m to around $d=5.5$ $\mu$m, i.e. a
1.5-fold shrinkage with respect to the control and BssHII-treated samples
(Fig. 3). Curiously, and unexpectedly, EcoRI-treated samples appear to recover
a larger size compared with PstI-treated kDNAs (Fig. 3c).

We can try to rationalise this puzzling observation with a simple scaling
argument: the free energy of adsorption of a soft polymeric cylinder on a
surface can be written as Gennes (1979)

$\mathcal{F}=k_{B}T\kappa\dfrac{D_{0}^{2}}{D^{2}}-k_{B}T\delta f_{b}N$ (1)

where $D$ is the average extension of the polymers away from the surface,
$\kappa$ is an effective stiffness that is proportional to the in-plane Young
modulus, $\delta$ is an effective interaction between the monomers and the
surface and $N$ is the total length of the polymers in the cylinder (see Fig.
3d for a schematics). Assuming that the whole kDNA mass is confined within a
layer $D$ from the surface, the fraction of mass adsorbed is approximately
$f_{b}\simeq a/D$, where $a$ is the extent of the attractive layer from the
surface. We can substitute this into Eq. (1),

$\mathcal{F}=k_{B}T\kappa\dfrac{D_{0}^{2}}{D^{2}}-k_{B}T\delta\dfrac{a}{D}N$
(2)

and minimise it with respect to $D$, i.e. $\partial\mathcal{F}/\partial D=0$,
to obtain

$\dfrac{D}{D_{0}}=2\dfrac{D_{0}}{a}\dfrac{\kappa}{\delta N}\sim\kappa(\delta
N)^{-1}\,.$ (3)

This equation implies that the average height of kDNA away from the adsorbing
surface is inversely proportional to the effective adsorption strength $\delta
N$, and directly proportional to the stiffness $\kappa$, respectively.
Assuming that the whole kDNA is contained within a constant cylindrical volume
$V=\pi R_{0}^{2}D_{0}=\pi R^{2}D$ we obtain a relationship between the average
kDNA extension $R$ and the total adsorption energy $\delta N$ scaling as

$\dfrac{R}{R_{0}}\sim\left(\dfrac{\delta N}{\kappa}\right)^{1/2}\,,$ (4)

implying that the more the kDNA mass, i.e. the larger $N$, the stronger the
adsorption strength and the larger the planar extension $R$ of the kDNA
network. This scaling argument entails that the lack of maxicircles decreases
the overall mass of kDNA, in turn decreasing the net adsorption strength of
the kDNA structure. At the same time, as expected, the larger the kDNA in-
plane stiffness $\kappa$ the smaller the lateral extension or spreading along
the surface.

This simple scaling argument is in line with our observations: removing
maxicircles, i.e. decreasing $\delta N$, reduces $R$, as seen in Fig. 3c and
increases the average height, as seen in Fig. 3e, where we compute the median
kDNA height from the mica (see SI for details). On the other hand, we note
that the mass lost due to PstI treatment amounts to about 2% of the total mass
(see above). Because of this, we expect a relatively small change in kDNA
extension, in marked contrast with the significant (1.5-fold) reduction in
kDNA diameter seen in experiments (Fig. 3c). Additionally, according to Eq.
(4), we should expect a similar shrinking in networks where the minor class of
minicircles, accounting for about 10% of kDNA mass, has been cleaved. On the
contrary, we did not observe such shrinkage in EcoRI-treated networks, which
in fact displayed more extended structures (Fig. 3c). These contrasting
results may be reconciled by arguing that while the removal of maxicircles
leads to a shrinkage of the network due to smaller adsorption strength
($\delta N$), the additional cleavage of a considerable $\sim 10\%$ fraction
of minicircles reduces the topological connectivity and the in-plane stiffness
($\kappa$) of the network, in turn allowing easier spreading on the surface.

Figure 4: a-d Example AFM images (zoomed in at the borders) of control,
BssHII, PstI and EcoRI samples. The scale bar is 500 nm. e Boxplot showing the
height of the hubs for the different samples.

###  I.5 EcoRI-treated networks display significantly disrupted hubs

After having quantified global changes to kDNA morphology, we then turned our
focus to smaller scale sub-structures. More specifically, from the AFM images
we realised that the hubs, or rosette, structures that characterise intact
kDNA are affected by partial digestion. In Fig. 4a-d we show representative
zoomed in sections of kDNAs, showing a series of hubs at the periphery of
partially digested kDNAs. To quantify their state, we extract the height of
the tallest pixel across several tens of hubs around each kDNA: while BssHII
and PstI treated hubs are not significantly affected, EcoRI treatment causes a
significant disruption, with the hubs’ height reducing from $3.3\pm 0.7$ nm to
$2.6\pm 0.5$ nm (p-value $<0.001$, Fig. 4e). We note that even for the control
case, the average height is smaller than the one expected for several
(possibly tens) of DNA strands overlapping each other at the hub Ragotskie
_et al._ – each around $2$ nm thick in the hydrated DNA structure – due to (i)
imaging dehydrated DNA and (ii) the compression of the DNA by the AFM tip He
_et al._ (2023). Nevertheless, the qualitative and quantitative disruption in
the EcoRI treated samples is clear and points to the fact that hubs are mostly
made by essential crossings between minicircles rather than maxicircles. At
the same time, we note that PstI treated samples do not display significantly
disrupted hubs, but do display fewer connections between the hubs (Fig. 4c)
and also more irregular borders (Fig. 2c).

###  I.6 Maxicircles form an Olympic sub-network and weave through hubs at the
periphery

Our findings suggest that (i) hubs are mostly made by links between
minicircles (Fig. 4) and (ii) maxicircles contribute to provide structural
integrity to the kDNA border (Fig. 2). While it is well known that during kDNA
replication the minicircles are polymerized and reattached at the periphery of
the parent kDNA by enzymes Pérez-Morga and Englund (1993), the fate of
maxicircles and their position within the kDNA after cell division are
unknown. Still, we note that during cell division, the maxicircles form the
so-called “nabelschnur”, a DNA bridge connecting newly replicated kDNAs in the
daughter cells Gluenz  _et al._ (2011), suggesting that they may assume a more
peripheral position compared to minicircles. In light of this, and motivated
by the dramatic structural and morphological change in PstI treated samples,
we hypothesised that at least some maxicircles may be weaved along the kDNA
periphery and provide direct support to the border. To qualitatively test this
hypothesis, we first visually inspected AFM images of non-digested samples,
and observed clear signatures of maxicircles joining hubs and threading
minicircles along the periphery of intact kDNAs (see white arrow in Fig. 5a,b)
and we also identified cases in which maxicircles were clearly linked near the
border of the network and spreading outside it (Fig. 5c-e). To further
understand whether the maxicircles are themselves forming a sub-network, we
treated kDNAs with BmrI, a restriction enzyme that cuts all minicircles but
leaves maxicircles intact. Intriguingly, BmrI-treated samples displayed a
consistent DNA band that did not travel into the gel (Fig. 5f). This suggests
that maxicircles in C. fasciculata are linked with each other, as found in
Trypanosoma equiperdum Shapiro (1993). To further prove this finding, we
extracted the DNA mass in the well as before and visualised it under AFM;
indeed, we could observe catenated structures of several (but likely not all
10) maxicircles (Fig. 5g-h). Thus, in light of these results we argue that at
least some maxicircles are thread and weave along the periphery of the kDNA
providing structural integrity and that they form a percolating sub-network
within the kDNA.

Figure 5:  a-e AFM images and zoomed in regions displaying examples of
maxicircles weaved at the periphery (white arrows) and threading through
minicircles and hubs (white circle). Scale bar in a and c is 2 $\mu$m. f Gel
elctrophoresis comparing kDNA, PstI-treated kDNA and BmrI-treated kDNA. The
latter enzyme cuts all minicircles but leaves maxicircles intact. The presence
of DNA mass in the well (orange arrow) suggests that the maxicircles are
linked together. (Lin MC = linearised maxicircles, mc = minicircles). g-h AFM
images of maxicircles purified from BmrI-treated samples and displaying
linking. Scale bar is 500 nm. i Sketch of kDNA model with some of the
maxicircles forming a sub-linked network and weaving around the periphery.

##  II Discussion

The kinetoplast DNA remains one of the most mysterious and fascinating
structures in nature. Its biogenesis, self-assembly and replication are
puzzling and still not fully understood. To address some of the open questions
in this field we performed atomic force microscopy (AFM) on C. fasciculata
kDNA samples that had been partially digested by restriction enzymes. We
specifically identified restriction enzymes that cut different fractions of
the kDNA structure via deep sequencing and DNA assembly. More specifically, we
chose BssHII having no targets, PstI targeting maxicircles and $<4\%$ of
minicircles (in total around $6\%$ of kDNA mass), EcoRI targeting maxicircles
and around $13\%$ of minicircles (in total around $15\%$ of kDNA mass) and
BmrI cutting all, and only, minicircles in C. fasciculata kDNA (Fig. 1a-b, d).

First, we proposed a new method to obtain kDNAs that are suitable for AFM: it
employs gel electrophoresis to clean samples from enzymes, BSA and other small
kDNA fragments. We argue that it could be used in the future as a simple way
to purify kDNA and other samples containing catenated structures such as some
DNA origami for AFM (Fig. 1c). We then measured the change in shape and size
of these structures and observed that both EcoRI and PstI treated structures
displayed a significant reduction in circularity, with the border of PstI and
EcoRI treated samples appearing more irregular and “blebbing” than control
samples. These results suggested that both maxicircles and minicircles play an
important role in kDNA border integrity (Fig. 2).

We then reported a marked change in size of PstI treated kDNA samples, with a
diameter reduced 1.5-fold when adsorbed on mica with respect to the control
sample (Fig. 3). Intriguingly, this size change was not observed in confocal
microscopy in the bulk Yadav  _et al._ (2023). On the contrary, we did not
observe any significant shrinking in EcoRI treated samples. We rationalised
this finding via a simple scaling argument (see Eq. (4)), which predicts that
less polymer mass in the kDNA network reduces the effective adsorption
strength but that cleaving minicircles may decrease the network stiffness.
These two parameters, kDNA mass and network stiffness, balance each other and
both affect the average network extension in opposite ways.

We note that similar kDNA structures have been recently prepared and analysed
via confocal microscopy in a bulk solution by Yadav et al. Yadav  _et al._
(2023). They reported that the digested kDNAs did not appear to assume a
different size or shape, yet they displayed a different dynamical relaxation
timescale, which they measured by computing correlations of the anisotropy
vector. The increasing internal relaxation timescale was attributed to a
smaller internal kDNA connectivity, which rendered the networks floppier and
hence slower to relax. In contrast with their findings, we do instead observe
a dramatic change in size (1.5-fold reduction) of PstI-treated samples
(lacking mainly maxicircles) and a significant reduction of circularity in
PstI and EcoRI treated samples (lacking both maxicircles and 13% of
minicircles). Yet, in line with their findings, our results suggest that the
EcoRI-treated networks are floppier than the control ones and can stretch more
on the mica.

Further, we found that the hubs’ height is significantly reduced after EcoRI
treatment, suggesting that minicircles are the main component of those
structures. At the same time, we found a significant change in border shape
after PstI. We thus argue that maxicircles may assume a specific spatial
distribution within the network and find visual, qualitative evidence that at
least some of them may thread and weave along the border, contributing to the
structural scaffolding of the hubs (Fig. 5a-e). Finally, by treating kDNAs
with BmrI we found evidence that maxicircles form a percolated interlinked
sub-network (Fig. 5f).

Overall, our single molecule AFM quantitative characterisation of partially
digested kDNA offer some insight into kDNA’s unique structure. Despite this,
more work is needed to exactly pinpoint the spatial distribution of
maxicircles and different classes of minicircles, and to dissect how each
component contributes to the kDNA material properties. In the future, we plan
to analyse and quantitatively compare the kDNA from different parasites; for
instance, there are forms of trypanosomes that no longer depend on kDNA
function and have lost maxicircles but not minicircles; thus, it would be
natural to look at kDNA structures extracted from these strains Schnaufer  _et
al._ (2002). We hope that ultimately, our results will complement others, to
achieve a full understanding of the biogenesis and self-assembly of this
fascinating and mysterious structure.

## Acknowledgements

DM thanks the Royal Society for support through a University Research
Fellowship. This project has received funding from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation
program (grant agreement No 947918, TAP). The authors also acknowledge the
contribution of the COST Action Eutopia, CA17139. The minicircle assembly is
deposited on GenBank OR687467-OR687484.

##  III Methods

### kDNA sequencing and bioinformatic analysis

####  III.0.1 DNA Assembly

Kinetoplast DNA from C. fasciculata was purchased from Inspiralis at 100
ng/$\mu$l in TE buffer (10 mM Tris-HCl pH7.5, 1 mM EDTA).

kDNA sample was sequenced at NovoGene. After Microbial Whole Genome Library
Preparation (350bp), libraries were pooled and sequenced on Illumina
sequencer. Pair-end reads (150 bp) were generated and about 4.7 million reads
passed the quality filter.

To optimize the minicircle detection and construction, de novo assembly was
performed in KOMICS with increase kmer sizes Van den Broeck  _et al._ (2020).
Contigs that contained the CSB3 (GGGGTTGGTGT) or its reverse complement, with
one allowed mismatch to capture sequence variations, were tested for
circularity. Fragments of the published minicircle sequence was detected and
was annealed manually for circularization and comparison with the known
sequence of major minicircle type in CfC1 Sugisaki and Ray (1987). The
circularized contigs were orientated to the same strand and aligned at their
anchor region. The published annotated minicircle fragments were detected in
the de novo assembled complete minicircles Yasuhira and Simpson (1995). After
assembly with small kmers, contigs homologous to L. braziliensis maxicircle
were extracted for manual examination by global mapping that allowed one
mismatch, to select for the longest homologous contig with complete read
coverage.

####  III.0.2 Relative abundance estimation

After minicircles of three T. congolense strains were assembled, the conserved
regions was identified by visually examining aligned minicircles. Motifs
homologous to T. brucei CSB1, 2, and 3 were recognized in both conserved area
Cooper  _et al._ (2019). Illumina reads were mapped to the assemblies using
Bowtie 2 with `--very-sensitive` option Langmead and Salzberg (2012).
Subsequent IGV visualization revealed no region with low or no coverage
Robinson  _et al._ (2011). The minicircle assemblies incorporated over 96% of
kDNA reads. The completeness was confirmed by $>$98% mapped CSB3-containing
reads and $>$97% CSB3-containing reads mapped with quality $\geq 10$. More
specifically, we obtained 4701610 total reads, mapped 4516344 (96%) and a
total of 494007 CSB3-containing reads, and mapped 489034 (98%). The relative
abundance of 18 unique minicircles was estimated from mean read depth
calculated by samtools Li  _et al._ (2009).

####  III.0.3 Minicircle Annotation

C. fasciculata maxicircle was aligned to annotated L. major maxicircle and
subsequently to unedited L. major maxicircle genes for annotation. The
annotation was confirmed by aligning transcriptomic data from in vitro
adherent and swimming form of C. fasciculata and infected mosquito hindguts
Filosa  _et al._ (2019). Using the unedited C. fasciculata maxicircle genes as
a reference, T-aligner performed T-masked mapping to detect consistently
edited encrypted genes that were used in subsequent edited gene prediction and
minicircle annotation Gerasimov  _et al._ (2018). The published A6 and uS12m
edited mRNAs Yasuhira and Simpson (1995) as well as predicted edited ND7 and
COXII mRNAs Filosa  _et al._ (2019) were validated by alignment of the
transcriptomic data with Bowtie2 Langmead and Salzberg (2012). Guide RNA
prediction was achieved using a custom version of the kDNA annotation package
Cooper  _et al._ (2019). Restriction enzyme cutting sites on C. fasciculata
minicircles and maxicircle were predicted for enzymes available from New
England Biolabs (NEB) using a custom python script to facilitate enzyme
choice.

### kDNA digestion

For restriction digestion with EcoRI, PstI, BssHII (all from NEB), 1$\mu$L of
enzyme (10 Units) was used to digest 1 $\mu$g of kDNA in 1X rCutsmart buffer,
overnight at 37∘C. The BssHII restriction digestion sample was incubated at
50∘C for 2 hours prior to overnight incubation at 37∘C. The samples were then
ran on a gel and recovered from the wells, as described in the text. After
recovery, the samples were adsorbed on freshly cleaved mica, dip washed in
ultra-pure water for 1 minute and gently air-dried in ultrapure nitrogen
stream.

### AFM images acquisition and analysis

The AFM images were recorded in Bruker JPK NanoWizard 4XP using SNL-10 probes.
To maintain uniformity in comparing the structural changes, we traced only the
circular kDNA structures and recorded the topographs at high resolution (2000
pixels X 2000 pixels). The AFM topographs were post-processed in the JPK data
processing software and converted into TIF files. We then used ImageJ to
manually compute the area of each kDNA, distance between hubs and pore size
using morphological segmentation via MorphoLibJ Legland  _et al._ (2016) as
previously described (Ref. He  _et al._ (2023)). The heights of the hubs in
Figure 4e were quantified using Gwyddion software. For each AFM image,
individual height profiles were generated for a minimum of 50 hubs, and the
peak maxima for each hub were recorded to calculate the average height in nm.

To obtain the average height of the whole kDNA, we performed an analysis using
MountainsSPIP software. First, the AFM images were pre-processed using the
least square plane (LSPL) subtraction function to flatten any long-range slope
in the AFM images. Subsequently, a line-by-line levelling process was applied
by subtracting the least square polynomial and mean values to ensure
straightness and align each scan line onto a uniform flat surface within the
image. The resulting flat images and data points were then used to generate a
histogram of the pixel height distribution (see SI). Within the histogram, two
prominent peaks corresponding to the mica surface and kDNA structures
(adsorbed DNA) were identified. We then calculated the average height of the
kDNA structures by taking the difference between the two maxima of the two
peaks.

### Agarose gel electrophoresis

We prepared 0.5 $\mu$g of kDNA with 0.5$\mu$L of restriction enzymes (BssHII,
Pst1, EcoRI) in 1X rCutsmart buffer and incubated overnight at 37∘C. The
BssHII sample was incubated at 50∘C for 2 hours before the overnight
incubation, as per NEB recommendations. A 0.8% agarose gel was cast in 1X TAE
buffer and 25 $\mu$L of restriction digested kDNA samples (plus a control
sample) were prepared in 1X loading dye and run for 5 hours at 50V (about
5V/cm). The gel was stained with SYBR gold and imaged in a geldoc imaging
system.

## References

  * Simpson (1967) L. P. Simpson, Atlas de Symposia sobre a Biota Amazonica (Pathologia) 6, 231 (1967).
  * Laurent and Steinert (1970) M. Laurent and M. Steinert, Proc. Natl. Acad. Sci. USA 66, 419 (1970).
  * Shlomai and Zadok (1983) J. Shlomai and A. Zadok, Nucleic Acids Res. 11, 4019 (1983).
  * Pérez-Morga and Englund (1993) D. L. Pérez-Morga and P. T. Englund, Cell 74, 703 (1993).
  * Shlomai (1994) J. Shlomai, Parasitology today (Personal ed.) 10, 341 (1994).
  * Morris  _et al._ (2001) J. C. Morris, M. E. Drew, M. M. Klingbeil, S. A. Motyka, T. T. Saxowsky, Z. Wang, and P. T. Englund, International journal for parasitology 31, 453 (2001).
  * Lukes  _et al._ (2002) J. Lukes, D. Guilbride, and J. Votýpka, Eukaryot. Cell 1, 495 (2002).
  * Simpson  _et al._ (2000) L. Simpson, O. H. Thiemann, N. J. Savill, J. D. Alfonzo, and D. A. Maslov, Proc. Natl. Acad. Sci. USA 97, 6986 (2000).
  * Hajduk and Ochsenreiter (2010) S. Hajduk and T. Ochsenreiter, RNA Biology 7, 229 (2010).
  * Liu  _et al._ (2005) B. Liu, Y. Liu, S. a. Motyka, E. E. C. Agbo, and P. T. Englund, Trends in parasitology 21, 363 (2005).
  * Klingbeil  _et al._ (2001) M. M. Klingbeil, M. E. Drew, Y. Liu, J. C. Morris, S. A. Motyka, T. T. Saxowsky, Z. Wang, and P. T. Englund, Protist 152, 255 (2001).
  * Hoffmann  _et al._ (2018) A. Hoffmann, S. Käser, M. Jakob, S. Amodeo, C. Peitsch, J. Týc, S. Vaughan, B. Zuber, A. Schneider, and T. Ochsenreiter, Proceedings of the National Academy of Sciences of the United States of America 115, E1809 (2018).
  * Schnaufer (2010) A. Schnaufer, Trends Parasitol. 26, 557 (2010).
  * Kalichava and Ochsenreiter (2021) A. Kalichava and T. Ochsenreiter, Open Biology 11, 14 (2021).
  * Amodeo  _et al._ (2021) S. Amodeo, A. Kalichava, A. Fradera-Sola, E. Bertiaux-Lequoy, P. Guichard, F. Butter, and T. Ochsenreiter, Journal of Cell Science 134 (2021), 10.1242/jcs.254300.
  * Amodeo  _et al._ (2022) S. Amodeo, I. Bregy, and T. Ochsenreiter, FEMS Microbiology Reviews , 1 (2022).
  * Lukes  _et al._ (2005) J. Lukes, H. Hashimi, and A. Zíková, Curr. Genet. 48, 277 (2005).
  * Schnaufer  _et al._ (2002) A. Schnaufer, G. J. Domingo, and K. Stuart, International Journal for Parasitology 32, 1071 (2002).
  * Soh  _et al._ (2020) B. W. Soh, A. Khorshid, D. Al Sulaiman, and P. S. Doyle, Macromolecules 53, 8502 (2020).
  * Soh and Doyle (2021) B. W. Soh and P. S. Doyle, ACS Macro Letters 10, 880 (2021).
  * Klotz  _et al._ (2020) A. R. Klotz, B. W. Soh, and P. S. Doyle, Proceedings of the National Academy of Sciences of the United States of America 117, 121 (2020).
  * Yadav  _et al._ (2023) I. Yadav, D. Al Sulaiman, and P. S. Doyle, Physical Review Research 5, 1 (2023).
  * Grosberg (2020) A. Y. Grosberg, Proceedings of the National Academy of Sciences of the United States of America 117, 18 (2020).
  * Tubiana  _et al._ (2022) L. Tubiana, F. Ferrari, and E. Orlandini, Phys. Rev. Lett. 129, 227801 (2022).
  * Vilgis and Otto (1997) T. A. Vilgis and M. Otto, Phys. Rev. E 56, R1314 (1997).
  * Wu  _et al._ (2017) Q. Wu, P. M. Rauscher, X. Lang, R. J. Wojtecki, J. J. De Pablo, M. J. Hore, and S. J. Rowan, Science 358, 1434 (2017).
  * Fischer  _et al._ (2015) J. Fischer, M. Lang, and J. U. Sommer, Journal of Chemical Physics 143 (2015), 10.1063/1.4933228.
  * Lang  _et al._ (2014) M. Lang, J. Fischer, M. Werner, and J. U. Sommer, Physical Review Letters 112, 1 (2014).
  * Igram  _et al._ (2016) S. Igram, K. C. Millett, and E. Panagiotou, Journal of Knot Theory and its Ramifications 25 (2016), 10.1142/S0218216516500814.
  * Diao  _et al._ (2012) Y. Diao, K. Hinson, R. Kaplan, M. Vazquez, and J. Arsuaga, J. Math. Biol. 64, 1087 (2012).
  * Michieletto  _et al._ (2014) D. Michieletto, D. Marenduzzo, E. Orlandini, G. Alexander, and M. Turner, Soft Matter 10, 5936 (2014).
  * Kim  _et al._ (2013) Y. S. Kim, B. Kundukad, A. Allahverdi, L. Nordensköld, P. S. Doyle, and J. R. Van Der Maarel, Soft Matter 9, 1656 (2013).
  * Krajina  _et al._ (2018) B. A. Krajina, A. Zhu, S. C. Heilshorn, and A. J. Spakowitz, Physical Review Letters 121, 148001 (2018).
  * Chen  _et al._ (1995) J. Chen, C. A. Rauch, J. H. White, P. T. Englund, and N. Cozzarelli, Cell 80, 61 (1995).
  * Ibrahim  _et al._ (2019) L. Ibrahim, P. Liu, M. Klingbeil, Y. Diao, and J. Arsuaga, Journal of Physics A: Mathematical and Theoretical 52 (2019).
  * He  _et al._ (2023) P. He, A. J. Katan, L. Tubiana, C. Dekker, and D. Michieletto, Physical Review X 13, 21010 (2023), arXiv:2209.01293 .
  * Ubertini and Rosa (2023) M. A. Ubertini and A. Rosa, Macromolecules 56, 3354 (2023).
  * Palombo  _et al._ (2023) G. Palombo, S. Weir, D. Michieletto, and Y. A. G. Fosado, arXiv:2308.09689v1 (2023).
  * Datta  _et al._ (2020) S. Datta, Y. Kato, S. Higashiharaguchi, K. Aratsu, A. Isobe, T. Saito, D. D. Prabhu, Y. Kitamoto, M. J. Hollamby, A. J. Smith, R. Dagleish, N. Mahmoudi, L. Pesce, C. Perego, G. M. Pavan, and S. Yagai, Nature 583, 400 (2020).
  * Peil  _et al._ (2020) A. Peil, P. Zhan, and N. Liu, Small 16, 1 (2020).
  * Barker (1980) D. C. Barker, Micron (1969) 11, 21 (1980).
  * Ferguson  _et al._ (1994) M. L. Ferguson, A. F. Torri, D. Pérez-Morga, D. C. Ward, and P. T. Englund, Journal of Cell Biology 126, 631 (1994).
  * Cavalcanti  _et al._ (2011) D. P. Cavalcanti, D. L. Gonçalves, L. T. Costa, and W. de Souza, Micron 42, 553 (2011).
  * Yaffe  _et al._ (2021) N. Yaffe, D. Rotem, A. Soni, D. Porath, and J. Shlomai, Scientific Reports 11, 1 (2021).
  * Ragotskie  _et al._ (2023) J. Ragotskie, N. Morrison, C. Stackhouse, R. C. Blair, and A. R. Klotz, Journal of Polymer Science n/a, 1 (2023).
  * Geerts  _et al._ (2021) M. Geerts, A. Schnaufer, and F. Van den Broeck, BMC Bioinformatics 22, 1 (2021).
  * Sugisaki and Ray (1987) H. Sugisaki and D. S. Ray, Molecular and biochemical parasitology 23, 253 (1987).
  * Cooper  _et al._ (2019) S. Cooper, E. S. Wadsworth, T. Ochsenreiter, A. Ivens, N. J. Savill, and A. Schnaufer, Nucleic acids research 47, 11304 (2019).
  * Li  _et al._ (2009) H. Li, B. Handsaker, A. Wysoker, T. Fennell, J. Ruan, N. Homer, G. Marth, G. Abecasis, and R. Durbin, Bioinformatics (Oxford, England) 25, 2078 (2009).
  * Filosa  _et al._ (2019) J. N. Filosa, C. T. Berry, G. Ruthel, S. M. Beverley, W. C. Warren, C. Tomlinson, P. J. Myler, E. A. Dudkin, M. L. Povelones, and M. Povelones, PLoS Neglected Tropical Diseases 13, 1 (2019).
  * Gerasimov  _et al._ (2018) E. S. Gerasimov, A. A. Gasparyan, I. Kaurov, B. Tichý, M. D. Logacheva, A. A. Kolesnikov, J. Lukeš, V. Yurchenko, S. L. Zimmer, and P. Flegontov, Nucleic acids research 46, 765 (2018).
  * Gennes (1979) P.-G. d. Gennes,  _Scaling concepts in polymer physics_ (Cornell University Press, 1979).
  * (53) J. Ragotskie, N. Morrison, C. Stackhouse, R. C. Blair, and A. R. Klotz, Journal of Polymer Science n/a.
  * Gluenz  _et al._ (2011) E. Gluenz, M. L. Povelones, P. T. Englund, and K. Gull, Molecular and Cellular Biology 31, 1012 (2011).
  * Shapiro (1993) T. A. Shapiro, Proceedings of the National Academy of Sciences of the United States of America 90, 7809 (1993).
  * Van den Broeck  _et al._ (2020) F. Van den Broeck, N. J. Savill, H. Imamura, M. Sanders, I. Maes, S. Cooper, D. Mateus, M. Jara, V. Adaui, J. Arevalo, A. Llanos-Cuentas, L. Garcia, E. Cupolillo, M. Miles, M. Berriman, A. Schnaufer, J. A. Cotton, and J. C. Dujardin, Proceedings of the National Academy of Sciences of the United States of America 117, 25159 (2020).
  * Yasuhira and Simpson (1995) S. Yasuhira and L. Simpson, RNA (New York, N.Y.) 1, 634 (1995).
  * Langmead and Salzberg (2012) B. Langmead and S. L. Salzberg, Nature Methods 9, 357 (2012).
  * Robinson  _et al._ (2011) J. T. Robinson, H. Thorvaldsdóttir, W. Winckler, M. Guttman, E. S. Lander, G. Getz, and J. P. Mesirov, Nature Biotechnology 29, 24 (2011).
  * Legland  _et al._ (2016) D. Legland, I. Arganda-Carreras, and P. Andrey, Bioinformatics 32, 3532 (2016).


# The $p$-Adic Valuation Trees for Quadratic Polynomials for Odd Primes

Will Boultinghouse
Kentucky Wesleyan College
Division of Natural Sciences and Mathematics
3000 Frederica Street
Owensboro  KY 42301
USA  Emily Hammett
Rowan University
Department of Mathematics
201 Mullica Hill Road
Glassboro  NJ 08028
USA  Stephen Hu
Rutgers University
Department of Mathematics
Hill Center for the Mathematical Sciences
110 Frelinghuysen Road
Piscataway  NJ 08854
USA  Olena Kozhushkina111Corresponding author.
Ursinus College
Department of Mathematics and Computer Science
Pfahler Hall 101
Collegeville  PA 19426
USA
<EMAIL_ADDRESS>
Rachel Snyder
Western Washington University
Department of Mathematics
516 High Street
Bellingham  WA 98225
USA  Justin Trulen
Kentucky Wesleyan College
Division of Natural Sciences and Mathematics
3000 Frederica Street
Owensboro  KY 42301
USA

###### Abstract

We examine the behavior of the sequences of $p$-adic valuations of quadratic
polynomials with integer coefficients for an odd prime $p$ through tree
representations. Under this representation, a finite tree corresponds to a
periodic sequence, and an infinite tree corresponds to an unbounded sequence.
We use the polynomial coefficients to determine whether the $p$-adic valuation
trees are finite or infinite, the number of infinite branches, the number of
levels, the valuations at terminating nodes, and their relationship to the
corresponding sequences.

Keywords: valuations, polynomials, $p$-adic integers, valuation trees,
Hensel’s lemma.

##  1 Introduction

Let $p$ be an odd prime. The $p$-adic valuation of a natural number $n$ is
defined as the highest power of $p$ that divides $n$. If we write $n=p^{k}d$,
where $k\in\mathbb{N}=\left\\{0,1,2,\ldots\right\\}$ and $d$ is an integer not
divisible by $p$, then the $p$-adic valuation is defined as $\nu_{p}(n):=k$. A
natural question to investigate is to classify the behavior of the sequence
$(\nu_{p}(x_{n}))$, given some prime $p$ and an integer sequence $(x_{n})$.
For instance, Legendre’s formula [7] gives a closed form for the sequence
$(\nu_{p}(n!))$:

$\nu_{p}(n!)=\frac{n-s_{p}(n)}{p-1},$

where $s_{p}(n)$ denotes the sum of the base-$p$ digits of $n$. Medina et al.
[8] considered sequences of $p$-adic valuations generated by polynomials; Bell
[3] investigated sequences generated by polynomials with rational coefficients
to study $p$-regular sequences; Byrnes et al. [4] considered sequences of
$p$-adic valuations for polynomials of the form $f(n)=an^{2}+c$; Boultinghouse
et al. [5] examined the sequences of 2-adic valuations generated by quadratic
polynomials with integer coefficients. In this paper, we study the $p$-adic
valuation of sequences generated by quadratic polynomials of the form
$f(n)=an^{2}+bn+c$, where $a,b,c\in\mathbb{Z}$ and $a\neq 0$, for an odd prime
$p$. If $p\mid\gcd(a,b,c)$, then define
$k=\min\\{\nu_{p}(a),\nu_{p}(b),\nu_{p}(c)\\}$. It suffices to consider the
corresponding function $f(n)p^{-k}$ since the valuations for $f(n)$ are those
for $f(n)p^{-k}$ increased by the value of $k$. Therefore, unless otherwise
specified, we assume $p\nmid\gcd(a,b,c)$ throughout.

We construct tree diagrams for each sequence to visualize these sequences. The
top node of the tree represents the valuation of $f(n)$ for any
$n\in\mathbb{N}$. If $\nu_{p}(f(n))$ does not depend on $n$, we stop the
construction and label the node with its $p$-adic valuation: the sequence
$(\nu_{p}(f(n)))$ is constant. Otherwise, the top node splits into $p$
branches, each branch corresponding to a subsequence
$pq,pq+1,pq+2,\ldots,pq+p-1$ for some $q\in\mathbb{N}$. We then repeat the
evaluation process for each node to construct the tree, splitting when
necessary. See Figure 1 for example.

$q$$3q$$\nu_{3}\geq
1$$9q$$\boxed{\nu_{3}=3}$$9q+3$$\boxed{\nu_{3}=2}$$9q+6$$\boxed{\nu_{3}=2}$$3q+1$$\boxed{\nu_{3}=0}$$3q+2$$\boxed{\nu_{3}=0}$
Figure 1: a $3$-adic valuation tree of $f(n)=n^{2}+27$

We call any node with no variation terminating since it does not split.
Otherwise, we call the node non-terminating.

As mentioned above, we represent the terms of the subsequence as nodes. For
each $m\in\mathbb{N}$, if $n=p^{m}q+r$ is a non-terminating node, then the
successive branches are $p^{m}(pq)+r,p^{m}(pq+1)+r,\ldots,p^{m}(pq+p-1)+r$,
and they are arranged from left to right in the order presented.

Define the $m^{th}$ level of a tree as the nodes that can be written in the
form $n=p^{m}q+r$, where $r\in\left\\{0,1,2,\ldots,p^{m}-1\right\\}$. We call
a tree finite if there exists a level that contains only terminating nodes.
Otherwise, we refer to such a tree as infinite. In the case of a finite tree,
we define the number of levels as the smallest $m$ such that the valuation of
$f(p^{m}q+r)$ is constant for all $r$ with respect to $q\in\mathbb{N}$. For
example, the tree in Figure 1 is a finite tree with two levels.

Finite trees can also be viewed as $p$-automatic sequences (see Definition 1.1
in [1]). The set of subsequences $(\nu_{p}\circ f(p^{m}q+r))$, where $m\geq 0$
and $0\leq r<p^{m}$, is called the $p$-kernel of the sequence $(\nu_{p}\circ
f(n))$. We refer the reader to Allouche and Shallit’s book [2] and Bell’s
paper [3] for more information.

In infinite trees, an infinite branch refers to a path that travels through
non-terminating nodes and branches. An infinite tree contains at least one
infinite branch. See Figures 2 and 3 in the Appendix for examples of infinite
trees.

An infinite branch in the tree provides some key insight into the zeros of the
polynomial $f$: any infinite branch in the tree associated to the polynomial
$f$ corresponds to a root of $f(x)=0$ in the $p$-adic ring of integers
$\mathbb{Z}_{p}$. This result can be attributed to Byrnes et al. [4]. We
should point out that the case of a tree being finite corresponds to the
sequence of $p$-adic valuations being both bounded and periodic. If a tree
contains at least one infinite branch, then the sequence of $p$-adic
valuations is unbounded. Lastly, we discuss the shape of the trees – this
pertains to the tree structure: which branches terminate, at what level they
terminate, at what level the branches split, and the valuations at the
terminating nodes.

The following theorem provides the main results of the paper.

######  Theorem 1.1.

Let $p$ be an odd prime and let $f(n)=an^{2}+bn+c\in\mathbb{Z}[n]$ such that
$p\nmid\gcd(a,b,c)$.

  1. 1.

If $a\equiv 0\pmod{p}$ and $b\equiv 0\pmod{p}$, then the tree has one node
with valuation $\nu_{p}(f(n))=0$.

  2. 2.

If $a\equiv 0\pmod{p}$ and $b\not\equiv 0\pmod{p}$, then the tree has one
infinite branch.

  3. 3.

If $a\not\equiv 0\pmod{p}$, then we consider the discriminant $D=b^{2}-4ac$.

    1. (a)

If $D=0$, then the tree has one infinite branch.

    2. (b)

If $D=p^{\nu_{p}(D)}\Delta$ where $\nu_{p}(D)$ is even and $\Delta$ is a
quadratic residue modulo $p$, then the tree has two infinite branches.

    3. (c)

If $D=p^{\nu_{p}(D)}\Delta$ where $\nu_{p}(D)$ is odd or $\Delta$ is a
quadratic non-residue modulo $p$, then the tree is finite with
$\ell=\lceil\nu_{p}(D)/2\rceil$ levels.

The result above will be proven by extending the ideas from Boultinghouse et
al. [5] by using Hensel’s lemma and the theory of quadratic residues.

The following theorem describes the exact structure of all finite trees from
part 3(c) of Theorem 1.1 regarding the valuations at each terminating node.

######  Theorem 1.2.

Let $p$ be an odd prime and let $f(n)=an^{2}+bn+c\in\mathbb{Z}[n]$ such that
$\nu_{p}(a)=0$. Let $D=b^{2}-4ac\neq 0$ denote the discriminant. Suppose the
discriminant can be expressed as $D=p^{\nu_{p}(D)}\Delta$ so that
$p\nmid\Delta$, and the valuation $\nu_{p}(D)$ is odd or $\Delta$ is a
quadratic non-residue modulo $p$. Set $\ell=\lceil\nu_{p}(D)/2\rceil$. Then
there exists a natural number $S_{\ell}$ with the property

$\nu_{p}\left(\frac{b}{2a}-S_{\ell}\right)\geq\ell,$

such that

$\nu_{p}(f(n))=\begin{cases}2(m-1),&\ \text{if}\ n\equiv(p^{m-1}r-S_{\ell})\
\mbox{\rm(mod}\ p^{m}\mbox{\rm)}\ \text{for}\ m=1,2,\ldots,\ell;\\\
\nu_{p}(D),&\ \text{if}\ n\equiv-S_{\ell}\ \mbox{\rm(mod}\
p^{\ell}\mbox{\rm)},\\\ \end{cases}$

where $r\in\left\\{1,2,\ldots,p-1\right\\}$.

The theorem above will be proven using the translation arguments for the
structures of finite trees developed in Boultinghouse et al. [5].

Note that this theorem can be stated in the context of the tree associated
with the function $f(n)$. Consider the assumptions of Theorem 1.2. Let
$r\in\left\\{1,2,\ldots,p-1\right\\}$. At a given level $m$, where $1\leq
m<\ell$, the tree has $p-1$ terminating nodes at the nodes
$n\equiv(p^{m-1}r-S_{\ell})\ \mbox{\rm(mod}\ p^{m}\mbox{\rm)}$ with valuation
$\nu_{p}(f(n))=2(m-1)$. At the $\ell^{th}$ level, the nodes are terminating.
Additionally, each node of the form $n\equiv(p^{\ell-1}r-S_{\ell})\
\mbox{\rm(mod}\ p^{\ell}\mbox{\rm)}$ has a valuation of
$\nu_{p}(f(n))=2(\ell-1)$ and the node of the form $n\equiv-S_{\ell}\
\mbox{\rm(mod}\ p^{m}\mbox{\rm)}$ has a valuation $\nu_{p}(f(n))=\nu_{p}(D)$.
See Figure 4 in the Appendix for such an example.

##  2 The $p$-adic numbers and other preliminaries

The $p$-adic numbers $\mathbb{Q}_{p}$ are all elements expressible as
$x=\sum_{i=m}^{\infty}a_{i}p^{i}$ where $m\in\mathbb{Z}\cup\\{\infty\\}$,
$a_{i}\in\\{0,1,\ldots,p-1\\}$, and $a_{m}\neq 0$.

With the $p$-adic expansion of $x$ we have the equivalent definition of the
$p$-adic valuation as

$\nu_{p}(x)=\nu_{p}\left(\sum_{i=m}^{\infty}a_{i}p^{i}\right)=m.$

By definition we let $\nu_{p}(0)=\infty$. Additionally, for
$x,y\in\mathbb{Q}_{p}$ we have the identity

$\nu_{p}(xy)=\nu_{p}(x)+\nu_{p}(y).$

A space of interest will be the ring of $p$-adic integers, denoted as
$\mathbb{Z}_{p}$:

$\mathbb{Z}_{p}=\left\\{x\in\mathbb{Q}_{p}:x=\sum_{i=0}^{\infty}a_{i}p^{i}\right\\}.$

The next result is a well-known lemma that could be used to determine the
existence of zeros in $\mathbb{Z}_{p}$ for polynomials with integer
coefficients. We cite the lemma without proof here, as stated in Section 6.4
in the work by Robert [9].

######  Lemma 2.1 (Hensel’s lemma).

Let $f(x)\in\mathbb{Z}_{p}[x]$ and suppose there is some
$x_{0}\in\mathbb{Z}_{p}$ that satisfies

$f(x_{0})\equiv 0\ \mbox{\rm(mod}\ p^{n}\mbox{\rm)}.$

If $\phi=\nu_{p}(f^{\prime}(x_{0}))<\frac{n}{2}$, then there exists a unique
zero $\xi$ of $f(x)$ in $\mathbb{Z}_{p}$ such that

$\xi\equiv x_{0}\ \mbox{\rm(mod}\
p^{n-\phi}\mbox{\rm)}\qquad\text{and}\qquad\nu_{p}(f^{\prime}(\xi))=\nu_{p}(f^{\prime}(x_{0}))=\phi.$

The conditions on $\xi$ imply that only one zero can exist with those
particular conditions. However, observe that there can exist more than one
zero in general.

######  Lemma 2.2 (Theorem 2.6 Byrnes et al. [4]).

Any infinite branch in the tree associated to the polynomial $f(n)$
corresponds to a root of $f(x)=0$ in the $p$-adic field $\mathbb{Q}_{p}$.

######  Lemma 2.3 (Theorem 2.1 Medina et al. [8]).

Let $p$ be a prime number and $f\in\mathbb{Z}[x]$. Then $(\nu_{p}(f(n)))$ is
either periodic or unbounded. Moreover, $(\nu_{p}(f(n)))$ is periodic if and
only if $f(n)$ has no zeros in $\mathbb{Z}_{p}$. In the periodic case, the
minimal period length is a power of $p$.

From the proof of Theorem 4.1 by Medina et al. [8], we have the following
result regarding the existence of square roots in $\mathbb{Z}_{p}$.

######  Proposition 2.4.

Let $p$ be an odd prime, and let $a\in\mathbb{Z}$. For nonzero $a$, let $d$ be
the unique integer which satisfies $a=p^{\nu_{p}(a)}\cdot d$. Then there
exists a square root of $a$ in $\mathbb{Z}_{p}$ if and only if $\nu_{p}(a)$ is
even and $d$ is a quadratic residue modulo $p$.

Determining whether a tree associated with the quadratic function is finite or
infinite is tied to the zeros of that quadratic function being in
$\mathbb{Z}_{p}$. The zeros of the quadratic depend on the square root of the
discriminant being in $\mathbb{Z}_{p}$. Hence, there is a need to work with
quadratic residues. Next, we present the definition and some basic facts.

######  Definition 2.5.

A number $r\in\mathbb{Z}$ is a quadratic residue modulo $p$ if there exists
$x\in\mathbb{Z}$ such that $x^{2}\equiv r\pmod{p}$.

Next, we prove some simple ideas involving quadratic residues that will be
useful later in the paper.

######  Lemma 2.6.

Let $a\in\mathbb{Q}_{p}$. If there exists $x\in\mathbb{Q}_{p}$ such that
$x^{2}=a$, then $\nu_{p}(a)=2k$ for some $k\in\mathbb{Z}$.

###### Proof.

Let $a\in\mathbb{Q}_{p}$ and suppose there exists $x\in\mathbb{Q}_{p}$ such
that $x^{2}=a$. Then $\nu_{p}(x^{2})=2\nu_{p}(x)=\nu_{p}(a)$. Since $p$-adic
valuations must be integers, then $\nu_{p}(a)=2k$ for some $k\in\mathbb{Z}$. ∎

######  Lemma 2.7.

Let $a\in\mathbb{Z}_{p}$. If there exists $x\in\mathbb{Q}_{p}$ such that
$x^{2}=a$, then $x\in\mathbb{Z}_{p}$.

###### Proof.

Let $a\in\mathbb{Z}_{p}$. Suppose there exists $x\in\mathbb{Q}_{p}$ such that
$x^{2}=a$. From Lemma 2.6, we have $2\nu_{p}(x)=\nu_{p}(a)$. Since
$\nu_{p}(a)\geq 0$, it follows that $\nu_{p}(x)\geq 0$ and thus
$x\in\mathbb{Z}_{p}$. ∎

In conjunction with quadratic residues, we will later make use of the Legendre
symbol. We define the Legendre symbol, denoted by $\left(\frac{a}{p}\right)$,
as a function of an integer $a$ and an odd prime $p$ such that

$\left(\frac{a}{p}\right)=\begin{cases}1,&\ \text{if}\ a\,\text{is a quadratic
residue modulo}\ p\ \text{and}\ a\not\equiv 0\ \mbox{\rm(mod}\
p\mbox{\rm)};\\\ -1,&\ \text{if}\ a\,\text{is not a quadratic residue modulo}\
p;\\\ 0,&\ \text{if}\ a\equiv 0\ \mbox{\rm(mod}\ p\mbox{\rm)}.\end{cases}$

Note the Legendre symbol can be calculated by

$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\ \mbox{\rm(mod}\
p\mbox{\rm)}\ \text{and}\ \left(\frac{a}{p}\right)\in\left\\{-1,0,1\right\\}.$

In the following lemma, we state several other properties of the Legendre
symbol.

######  Lemma 2.8.

Let $p$ be an odd prime and $a$, $b$ be any integers. Then:

  1. 1.

If $a\equiv b\ \mbox{\rm(mod}\ p\mbox{\rm)}$, then
$\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$.

  2. 2.

The Legendre symbol has the multiplicative property. That is,
$\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right)$.

To determine the valuations, we frequently use properties of primes and
polynomials. To simplify calculations, we mention a property of considering
polynomials modulo a power of a prime $p$, extending the property introduced
by Byrnes et al. [4] when the power of $p$ is $1$.

######  Proposition 2.9.

Let $f(n)$ be a polynomial with integer coefficients, and let $p$ be a prime.
Then for $q,r\in\mathbb{Z}$ with $i\geq 1$, we have $f(p^{i}q+r)\equiv f(r)\
\mbox{\rm(mod}\ p^{i}\mbox{\rm)}$.

###### Proof.

Let $f(n)=a_{m}n^{m}+\cdots+a_{1}n+a_{0}\in\mathbb{Z}[n]$. Then applying the
binomial theorem gives

$\begin{split}f(p^{i}q+r)&=a_{m}(p^{i}q+r)^{m}+a_{m-1}(p^{i}q+r)^{m-1}+\cdots+a_{0}\\\
&=a_{m}\sum_{k=0}^{m}\binom{m}{k}(p^{i}q)^{k}r^{m-k}+a_{m-1}\sum_{k=0}^{m-1}\binom{m-1}{k}(p^{i}q)^{k}r^{m-1-k}+\cdots+a_{0}\\\
&\equiv a_{m}r^{m}+a_{m-1}r^{m-1}\cdots+a_{0}\ \mbox{\rm(mod}\
p^{i}\mbox{\rm)}\\\ &\equiv f(r)\ \mbox{\rm(mod}\
p^{i}\mbox{\rm)}.\end{split}$

In other words, when considering a polynomial $f(n)\in\mathbb{Z}[n]$ modulo
$p^{i}$, the input can be reduced modulo $p^{i}$ before proceeding with the
evaluation of the polynomial. ∎

##  3 The case for $a\equiv 0\ \mbox{\rm(mod}\ p\mbox{\rm)}$

In this section, we will prove parts (1) and (2) from Theorem 1.1. We need the
following lemma to prove part (1) of Theorem 1.1.

######  Lemma 3.1.

Let $p$ be a prime and let $f(n)=an^{2}+bn+c\in\mathbb{Z}[n]$. Then
$\nu_{p}(f(n))=0$ if and only if $f(r)\not\equiv 0\pmod{p}$ holds for all
$r\in\\{0,1,\ldots,p-1\\}$.

###### Proof.

Let $p$ be a prime and let $f(n)=an^{2}+bn+c\in\mathbb{Z}[n]$. Then
$\nu_{p}(f(n))=0$ if and only if $\nu_{p}(f(pq+r))=0$ for all
$r\in\\{0,1,\ldots,p-1\\}$. From Proposition 2.9, we see that $f(pq+r)\equiv
f(r)\pmod{p}$. Therefore, $\nu_{p}(f(n))=0$ if and only if $f(r)\not\equiv
0\pmod{p}$ holds for all $r\in\\{0,1,\ldots,p-1\\}$. ∎

######  Proposition 3.2.

Let $p$ be an odd prime and let $f(n)=an^{2}+bn+c\in\mathbb{Z}[n]$. If
$a\equiv 0\pmod{p}$, $b\equiv 0\pmod{p}$, and $c\not\equiv 0\pmod{p}$, then
the corresponding tree is a single node with valuation zero.

###### Proof.

Let $p$ be an odd prime. Let $f(n)=an^{2}+bn+c\in\mathbb{Z}[n]$ such that
$a\equiv 0\pmod{p}$, $b\equiv 0\pmod{p}$, and $c\not\equiv 0\pmod{p}$. This
implies that $a=p\alpha$ and $b=p\beta$ for some integers $\alpha$ and
$\beta$. Therefore for all $r\in\\{0,1,\ldots,p-1\\}$, we have that
$f(r)=p\alpha r^{2}+p\beta r+c$. Since $c\not\equiv 0\pmod{p}$, then
$f(r)=p\alpha r^{2}+p\beta r+c\not\equiv 0\pmod{p}$. Therefore by Lemma 3.1,
the tree of $f(n)$ is a dot tree with a valuation of 0. ∎

The trees described in the above proposition are the simplest types of trees
one can have, and we will refer to them as dot trees. The dot trees in
Proposition 3.2 have only the valuation of zero. However, dot trees may have
valuations other than zero. This case occurs when the quadratic coefficients
are all divisible by $p$ to some power. We can state this formally as the
following corollary.

######  Corollary 3.3.

Let $p$ be a prime and let $f(n)=an^{2}+bn+c$. Then the corresponding tree has
a single valuation of $k\geq 0$ if and only if there exists a $k\in\mathbb{N}$
such that $p^{k}$ divides $a$, $b$, and $c$, but $p^{k+1}$ divides $a$ and $b$
but not $c$.

Next, we prove part (2) of Theorem 1.1. Again, we first need a lemma. As noted
above, the tree associated with a quadratic is infinite if a zero of the
quadratic is in $\mathbb{Z}_{p}$. The nature of these zeros is tied to the
discriminant of the quadratic. Furthermore, we see that the $p$-adic valuation
of the discriminant plays a role in determining when the tree associated to a
quadratic is finite or infinite. The next lemma is used to simplify a
calculation.

######  Lemma 3.4.

Let $p$ be a prime and let $D=b^{2}-4ac$ where $a\equiv a_{0}\ \mbox{\rm(mod}\
p\mbox{\rm)}$, $b\equiv b_{0}\ \mbox{\rm(mod}\ p\mbox{\rm)}$, and $c\equiv
c_{0}\ \mbox{\rm(mod}\ p\mbox{\rm)}$ with
$a_{0},b_{0},c_{0}\in\\{0,1,\ldots,p-1\\}$. Then $\nu_{p}(D)=0$ if and only if
$\nu_{p}(b_{0}^{2}-4a_{0}c_{0})=0$.

###### Proof.

Suppose $\nu_{p}(D)=0$. Notice that from a straightforward calculation, $D$ is
of the form $D=pt+b_{0}^{2}-4a_{0}c_{0}$, where $t\in\mathbb{Z}$. Then $D$ is
not divisible by $p$ if and only if $b_{0}^{2}-4a_{0}c_{0}$ is not divisible
by $p$. ∎

######  Proposition 3.5.

Let $p$ be an odd prime and let $f(n)=an^{2}+bn+c\in\mathbb{Z}[n]$. If
$a\equiv 0\ \mbox{\rm(mod}\ p\mbox{\rm)}$ and $b\not\equiv 0\ \mbox{\rm(mod}\
p\mbox{\rm)}$, then the corresponding tree is infinite with exactly one
infinite branch.

###### Proof.

We first show that the corresponding tree has at least one infinite branch,
and then we show that it has at most one infinite branch to reach the desired
result of exactly one infinite branch.

To determine that there is at least one infinite branch, we apply Hensel’s
lemma (Lemma 2.1). Let $f(x)=ax^{2}+bx+c$. Taking the derivative gives
$f^{\prime}(x)=2ax+b$. We want to find some $x_{0}\in\mathbb{Z}_{p}$ so that
$f(x_{0})\equiv 0\pmod{p^{n}}$ and $\nu_{p}(f^{\prime}(x_{0}))<\frac{n}{2}$.

Let $x_{0}=-cb^{p-2}\in\mathbb{Z}$. Recalling $a\equiv 0\pmod{p}$ and applying
Fermat’s Little Theorem, we have

$f(x_{0})=a(-cb^{p-2})^{2}+b(-cb^{p-2})+c\equiv-cb^{p-1}+c\equiv 0\pmod{p},$

so that $n\geq 1$. Then

$f^{\prime}(x_{0})=2a(-cb^{p-2})+b\equiv b\pmod{p},$

which implies $\phi=\nu_{p}(f^{\prime}(x_{0}))=0$. Since $\phi<\frac{n}{2}$,
Hensel’s lemma guarantees the existence of a zero. Therefore the tree has at
least one infinite branch.

We apply Lemma 3.4 to determine that there is exactly one infinite branch and
exactly one zero of $f(n)$ is in $\mathbb{Q}_{p}$ and is not in
$\mathbb{Z}_{p}$. That is, we determine that exactly one zero has a negative
$p$-adic valuation. Consider the zeros $n_{1,2}=\frac{-b\pm\sqrt{D}}{2a}$,
where $D=b^{2}-4ac=p^{\nu_{p}(D)}\Delta$. By hypothesis we have $a=p\alpha$,
$b=p\beta+b_{0}$, and $c=p\gamma+c_{0}$ with $b_{0}\in\\{1,2,\ldots,p-1\\}$,
and $c_{0}\in\\{0,1,\ldots,p-1\\}$. Then it follows from Lemma 3.4 that
$\nu_{p}(D)=0$, since $\nu_{p}(b_{0}^{2})=0$. Furthermore,

$D=p(p(\beta^{2}-4\alpha\gamma)-2(2\alpha c_{0}-\beta b_{0}))+b_{0}^{2}\equiv
b_{0}^{2}\pmod{p}.$

It follows that $D=\Delta\equiv b_{0}^{2}\pmod{p}$ is a quadratic residue.
Since the valuation of the discriminant is even and $\Delta$ is a quadratic
residue, we have $\sqrt{D}\in\mathbb{Z}_{p}$ by Proposition 2.4. Furthermore,
neither $b$ nor $\sqrt{D}$ is congruent to zero modulo $p$. Since
$\sqrt{D}\not\equiv 0\pmod{p}$, it follows that $2\sqrt{D}\not\equiv
0\pmod{p}$ and therefore $\sqrt{D}\not\equiv-\sqrt{D}\pmod{p}$.

Furthermore, at least one $-b-\sqrt{D}$ or $-b+\sqrt{D}$ cannot be congruent
to zero modulo $p$. If both were congruent to zero mod $p$, we could combine
the two statements of $-b-\sqrt{D}\equiv 0\pmod{p}$ and $-b+\sqrt{D}\equiv
0\pmod{p}$ to get $\sqrt{D}\equiv-\sqrt{D}\pmod{p}$, which is a contradiction.
Without loss of generality, suppose $-b-\sqrt{D}\not\equiv 0\pmod{p}$. This
implies $\nu_{p}\left(-b-\sqrt{D}\right)=0$. Recalling $\nu_{p}(a)\geq 1$, we
have

$\nu_{p}(n_{1})=\nu_{p}\left(\frac{-b-\sqrt{D}}{2a}\right)=\nu_{p}\left(-b-\sqrt{D}\right)-\nu_{p}(2a)=0-\nu_{p}(a)<0,$

and thus $n_{1}\in\mathbb{Q}_{p}\setminus\mathbb{Z}_{p}$. It follows that at
least one zero is not in $\mathbb{Z}_{p}$, and thus the tree has at most one
infinite branch. ∎

With a little more work, we can have the following corollary.

######  Corollary 3.6.

If $a\equiv 0\ \mbox{\rm(mod}\ p\mbox{\rm)}$ and $b\not\equiv 0\
\mbox{\rm(mod}\ p\mbox{\rm)}$, then on the $m^{th}$ level, there is only one
non-terminal node with a valuation greater than or equal to $m$. The other
$p-1$ nodes are terminal with valuation equal to $m-1$.

###### Proof.

From Proposition 3.5 there must exist at least one non-terminating node at
$n=pq+r_{0}$, where $r_{0}\in\left\\{0,1,\ldots,p-1\right\\}$, such that
$p\mid f(pq+r_{0})$. Furthermore, a calculation yields

$a(pq+r_{0})^{2}+b(pq+r_{0})+c=p(apq^{2}+bq+2aqr_{0}+r_{0}^{2}a/p)+br_{0}+c,$

thus $p\mid(br_{0}+c)$. That is,

$br_{0}+c=pk_{1}\ \text{for}\ k_{1}\in\mathbb{Z}.$

Thus, the valuation at this node is greater than or equal to $1$.

Additionally, suppose there exists a second non-terminating node at
$n=pq+r_{0}^{\prime}$, where
$r_{0}^{\prime}\in\left\\{0,1,\ldots,p-1\right\\}\setminus\left\\{r_{0}\right\\}$,
such that $p\mid f(pq+r_{0}^{\prime})$. A similar calculation shows that
$p\mid(br_{0}^{\prime}+c)$ as well. That is,

$br_{0}^{\prime}+c=pk_{2}\ \text{for}\ k_{2}\in\mathbb{Z}.$

Taking the difference of $br_{0}+c=pk_{1}$ and $br_{0}^{\prime}+c=pk_{2}$, we
get

$b(r_{0}-r_{0}^{\prime})=p(k_{1}-k_{2}).$

Since $r_{0},r_{0}^{\prime}\in\left\\{0,1,\ldots,p-1\right\\}$, it follows
that $p\nmid(k_{1}-k_{2})$. But then $p\mid b$, which is a contradiction. Thus
there exists exactly one non-terminating node. Furthermore, since

$a(pq+r_{0}^{\prime})^{2}+b(pq+r_{0}^{\prime})+c=p(apq^{2}+bq+2aqr_{0}^{\prime}+r_{0}^{\prime
2}a/p)+br_{0}^{\prime}+c,$

for all
$r_{0}^{\prime}\in\left\\{0,1,\ldots,p-1\right\\}\setminus\left\\{r_{0}\right\\}$,
the valuations at all terminating nodes must be zero.

Suppose by induction for all levels $i$ up to $m-1$ with $m\geq 2$ the
terminating nodes have a valuation equal to $i-2$ and there is only one non-
terminating node, with a valuation greater than or equal to $i-1$.

Now suppose the only non-terminating node is at $n=p^{m-1}q+r_{0}$, and so
$p^{m-1}\mid f(p^{m-1}q+r_{0})$. This node splits into the nodes of the form
$n=p^{m}q+p^{m-1}r+r_{0}$, where $r\in\left\\{0,1,\ldots,p-1\right\\}$. Then

$\displaystyle f(p^{m}q+p^{m-1}r+r_{0})=a(p^{m}q+r_{0})^{2}$
$\displaystyle+b(p^{m}q+r_{0})+c$
$\displaystyle+2ap^{m-1}rr_{0}+2ap^{2m-1}qr+ap^{2(m-1)}r^{2}+bp^{m-1}r.$

Without loss of generality, let the non-terminating node be at
$n=p^{m}q+r_{0}$, that is $r=0$. Since $n=p^{m}q+r_{0}$ is the non-terminating
node, and we know the valuations are bigger than or equal to $m-1$, the above
implies

$\displaystyle f(p^{m}q+r_{0})$
$\displaystyle=a(p^{m}q+r_{0})^{2}+b(p^{m}q+r_{0})+c$
$\displaystyle=p^{m-1}(ap^{m+1}q^{2}+2apqr_{0}+bpq)+ar_{0}^{2}+br_{0}+c$
$\displaystyle=p^{m-1}k_{3}\ \text{for}\ k_{3}\in\mathbb{Z}\ \text{depending
on}\ q.$

Additionally, since $n=p^{m}q+r_{0}$ is the non-terminating node and
$p^{m-1}\mid f(p^{m-1}q+r_{0})$, this implies
$p^{m-1}\mid(ar_{0}^{2}+br_{0}+c)$. But if $p^{m}\nmid(ar_{0}^{2}+br_{0}+c)$,
then the node $n=p^{m}q+r_{0}$ would have constant valuation equal to $m-1$,
which contradicts the fact that this node is non-terminating. Thus we must
have $p^{m}\mid f(p^{m-1}q+r_{0})$, which implies that $p\mid k_{3}$.

This fact, and the equation above, then imply

$\displaystyle f(p^{m}q+p^{m-1}r+r_{0})$
$\displaystyle=p^{m-1}k_{3}+2ap^{m-1}rr_{0}+2ap^{2m-1}qr+ap^{2(m-1)}r^{2}+bp^{m-1}r$
$\displaystyle=p^{m-1}(k_{3}+2arr_{0}+2ap^{m}qr+ap^{m-1}r^{2}+br),$

for all other $r\in\left\\{1,\ldots,p-1\right\\}$. Since $b$ and $r$ are not
divisible by $p$, then $br$ is not divisible by $p$. Thus all other nodes are
terminal with valuation $m-1$ on the $m^{th}$ level. This then completes the
proof. ∎

##  4 The case for $a\not\equiv 0\ \mbox{\rm(mod}\ p\mbox{\rm)}$

In this section, we first prove the case (3) from Theorem 1.1 and then we
prove Theorem 1.2. The following proposition comes in three parts. The first
two parts prove cases (3a) and (3b) of Theorem 1.1. The third part proves case
(3c). Then, with the help of Corollary 4.4, we prove Theorem 1.2.

######  Proposition 4.1.

Let $p$ be an odd prime and let $f(n)=an^{2}+bn+c\in\mathbb{Z}[n]$ such that
$\nu_{p}(a)=0$. Let $D=b^{2}-4ac$ denote the discriminant and express
$D=p^{\nu_{p}(D)}\Delta$ so that $p\nmid\Delta$.

  1. 1.

If $D=0$, then the tree has exactly one infinite branch corresponding to the
zero $n_{1}=-\frac{b}{2a}$.

  2. 2.

For $D\neq 0$, if $\nu_{p}(D)$ is even and $\Delta$ is a quadratic residue
modulo $p$, then the tree has exactly two infinite branches corresponding to
the zeros $n_{1,2}=\frac{-b\pm\sqrt{D}}{2a}$.

  3. 3.

For $D\neq 0$, if $\nu_{p}(D)$ is odd or $\Delta$ is a quadratic non-residue
modulo $p$, then the tree is finite with $\ell=\lceil\nu_{p}(D)/2\rceil$
levels. Additionally, there exists a number $S_{\ell}\in\mathbb{Z}$ such that
the tree associated to $f(n-S_{\ell})$ has the following properties:

    1. (a)

The number of levels is equal to $\ell=\lceil\nu_{p}(D)/2\rceil$.

    2. (b)

Other than the last level, the node of the form $n=p^{j}q$ where $1\leq
j\leq\ell-1$ is the only non-terminating node.

    3. (c)

The valuation of the terminating nodes is equal to $2(m-1)$ where $m$ is the
level. The only exception is the node $n=p^{\ell}q$ on the last level.

    4. (d)

The node $n=p^{\ell}q$ on the last level has valuation $\nu_{p}(D)$. This is
the maximum valuation of the tree.

###### Proof.

Part (1) is trivial with $D=0$.

For part (2), consider $D=p^{\nu_{p}(D)}\Delta$ with $\nu_{p}(D)$ even and
$\Delta$ a quadratic residue modulo $p$. By Proposition 2.4, $\sqrt{D}$ is a
$p$-adic integer. Since $\nu_{p}(2a)=0$, then
$n_{1,2}=\frac{-b\pm\sqrt{D}}{2a}$ are $p$-adic integers as well.

For part (3), define $S$ to equal in its $p$-adic expansion to

$S=\frac{b}{2a}=\sum_{i=0}^{\infty}s_{i}p^{i},$

where $s_{i}\in\left\\{0,1,2,\ldots,p-1\right\\}$.

Define $S_{\ell}$ as

$S_{\ell}=\sum_{i=0}^{\ell-1}s_{i}p^{i},$

which is the truncation of $S$. Note that by definitions of $S$ and $S_{\ell}$
from above we have

$\displaystyle\nu_{p}\left(\frac{b}{2a}-S_{\ell}\right)$
$\displaystyle=\nu_{p}(b-2aS_{\ell})$ $\displaystyle\geq\ell.$

Then

$b-2aS_{\ell}=p^{\ell}k_{1},$

where $k_{1}\in\mathbb{Z}$. A simple calculation gets us

$\displaystyle f(n-S_{\ell})$
$\displaystyle=a(n-S_{\ell})^{2}+b(n-S_{\ell})+c$
$\displaystyle=an^{2}+(b-2aS_{\ell})n+aS_{\ell}^{2}-bS_{\ell}+c$
$\displaystyle=an^{2}+p^{\ell}k_{1}n+aS_{\ell}^{2}-bS_{\ell}+c$
$\displaystyle=an^{2}+p^{\ell}k_{1}n+f(-S_{\ell}).$

The discriminant of $f(n)$ is equal to the discriminant of $f(n-\tau)$, where
$\tau\in\mathbb{Z}$. Thus we have

$p^{2\ell}k_{1}^{2}-4af(-S_{\ell})=p^{\nu_{p}(D)}\Delta.$

Since $\ell=\lceil\nu_{p}(D)/2\rceil$, then $2\ell\geq\nu_{p}(D)$ (that is,
either $2\ell=\nu_{p}(D)$ or $2\ell=\nu_{p}(D)+1$). It follows that
$p^{\nu_{p}(D)}$ divides $f(-S_{\ell})$ since $4a$ and $\Delta$ are not
divisible by $p$. Then we have

$f(-S_{\ell})=p^{\nu_{p}(D)}k_{2},$

where $k_{2}\in\mathbb{Z}$ is not divisible by $p$. Now we have

$f(n-S_{\ell})=an^{2}+p^{\ell}k_{1}n+p^{\nu_{p}(D)}k_{2}.$

At the $m^{th}$ level the nodes are of the form $n=p^{m}j+p^{m-1}r$, where
$1\leq m\leq\ell$ and $r\in\left\\{0,1,2,\ldots,p-1\right\\}$. Then

$\displaystyle f(n-S_{\ell})$ $\displaystyle=f(p^{m}j+p^{m-1}r-S_{\ell})$
$\displaystyle=a(p^{m}j+p^{m-1}r)^{2}+p^{\ell}k_{1}(p^{m}j+p^{m-1}r)+p^{\nu_{p}(D)}k_{2}$
$\displaystyle=ap^{2m}j^{2}+2ap^{2m-1}rj+ap^{2m-2}r^{2}+p^{\ell+m}k_{1}j+p^{\ell+m-1}k_{1}r+p^{\nu_{p}(D)}k_{2},$

when $r\neq 0$ and

$f(n-S_{\ell})=ap^{2m}j^{2}+p^{\ell+m}k_{1}j+p^{\nu_{p}(D)}k_{2},$

when $r=0$.

At a given level $m<\ell$, if $r\neq 0$, then notice that $2m-2$ is the
smallest exponent on $p$. We get

$f(n-S_{\ell})=p^{2m-2}(ap^{2}j^{2}+2aprj+ar^{2}+p^{\ell-m+2}k_{1}j+p^{\ell-m+1}k_{1}r+p^{\nu_{p}(D)-2m+2}k_{2}).$

But notice that $ar^{2}$ is not divisible by $p$. Thus we have

$\nu_{p}(f(n-S_{\ell}))=2m-2.$

If $r=0$, then $2m$ is the smallest exponent on $p$. We get

$f(n-S_{\ell})=p^{2m}(aj^{2}+p^{\ell-m}k_{1}j+p^{\nu_{p}(D)-2m}k_{2}).$

Since $j$ is a natural number, then

$\nu_{p}(f(n-S_{\ell}))\geq 2m.$

In other words, at every level $m<\ell$, there is only one non-terminal node
which is of the form $n=p^{m}j$, and all other nodes are terminating with
$p$-adic valuation equal to $2m-2$.

At the $\ell$th level, our equations will now take the form

$f(n-S_{\ell})=ap^{2\ell}j^{2}+2ap^{2\ell-1}rj+ap^{2\ell-2}r^{2}+p^{2\ell}k_{1}j+p^{2\ell-1}k_{1}r+p^{\nu_{p}(D)}k_{2},$

when $r\neq 0$, and

$f(n-S_{\ell})=ap^{2\ell}j^{2}+p^{2\ell}k_{1}j+p^{\nu_{p}(D)}k_{2},$

when $r=0$.

When $r\neq 0$, then $2\ell-2$ is the smallest exponent on $p$. We get

$f(n-S_{\ell})=p^{2\ell-2}(ap^{2}j^{2}+2aprj+ar^{2}+p^{2}k_{1}j+pk_{1}r+p^{\nu_{p}(D)-2\ell+2}k_{2}).$

Since $ar^{2}$ is not divisible by $p$, we have

$\nu_{p}(f(n-S_{\ell}))=2\ell-2.$

When $r=0$, consider two cases: either $\nu_{p}(D)$ is odd or $\nu_{p}(D)$ is
even. If $\nu_{p}(D)$ is odd, then $2\ell>\nu_{p}(D)$. Thus, we have

$f(n-S_{\ell})=p^{\nu_{p}(D)}(apj^{2}+pk_{1}j+k_{2}).$

Recall that $k_{2}$ is not divisible by $p$, and so we have

$\nu_{p}(f(n-S_{\ell}))=\nu_{p}(D).$

If $\nu_{p}(D)$ is even, then $2\ell=\nu_{p}(D)$. Then we have

$f(n-S_{\ell})=p^{\nu_{p}(D)}(aj^{2}+k_{1}j+k_{2}).$

Recall that $\nu_{p}(a)=\nu_{p}(k_{2})=0$ and $\nu_{p}(k_{1})\geq 0$. Then we
have

$\displaystyle\nu_{p}(aj^{2}+k_{1}j+k_{2})$
$\displaystyle=\nu_{p}(4a^{2}j^{2}+4ak_{1}j+4ak_{2})$
$\displaystyle=\nu_{p}((2aj+k_{1})^{2}-k_{1}^{2}+4ak_{2})$
$\displaystyle=\nu_{p}((2aj+k_{1})^{2}-\Delta).$

Assume there exists an $r\in\left\\{0,1,\ldots,p-1\right\\}$ such that when
$j=pk+r$, then

$\nu_{p}((2a(pk+r)+k_{1})^{2}-\Delta)\geq 1,$

which implies

$(2a(pk+r)+k_{1})^{2}-\Delta=p\kappa,$

where $\kappa\in\mathbb{Z}$. Then it follows that

$(2a(pk+r)+k_{1})^{2}-\Delta\equiv(2ar+k_{1})^{2}-\Delta\pmod{p}\equiv
0\pmod{p}.$

Thus

$(2ar+k_{1})^{2}\equiv\Delta\pmod{p}.$

This implies that $\Delta$ is a quadratic residue, which contradicts the
assumption that $\Delta$ is not a quadratic residue in the case of
$\nu_{p}(D)$ even. Therefore,

$\nu_{p}(aj^{2}+k_{1}j+k_{2})=0$

for all $j\in\mathbb{N}$ and this completes the proof. ∎

######  Remark 4.2.

With the above assumption, if we have an infinite tree, then we must have that
$\nu_{p}(D)$ is even and $\Delta$ is a quadratic residue modulo $p$. To see
this, consider the case when either $\nu_{p}(D)$ is odd or $\Delta$ is not a
quadratic residue modulo $p$. Then $\sqrt{D}$ does not exist in
$\mathbb{Z}_{p}$, hence neither of $n_{1,2}$ are $p$-adic integers. Therefore,
the corresponding tree is finite.

######  Lemma 4.3 (Translation).

Let $p$ be an odd prime and let $f(n)\in\mathbb{Z}[n]$. Suppose
$s\in\mathbb{Z}$, and set $g(n)=f(n-s)$. Given $m\in\mathbb{N}$ and
$r\in\mathbb{Z}$ such that $0\leq r<p^{m}$, it follows that

$\nu_{p}(f(p^{m}q+r))=\nu_{p}(g(p^{m}q+(r+s)\ \mbox{\rm(mod}\
p^{m}\mbox{\rm)})).$

###### Proof.

If the node $n=p^{k}q+d$ terminates, the valuation $\nu_{p}(f(n))$ at the node
of the form $n=p^{k}q+r$ is moved to the node of the form $n=p^{k}q+(r+s)\
\mbox{\rm(mod}\ p^{k}\mbox{\rm)}$ under translating an equation from $f(n)$ to
$f(n-s)=g(n)$. Similarly, if the node $n=p^{k}q+d$ continues under $f(n)$, the
node of the form $n=p^{k}q+(r+s)\ \mbox{\rm(mod}\ p^{k}\mbox{\rm)}$ continues
under translating an equation from $f(n)$ to $f(n-s)=g(n)$. ∎

######  Corollary 4.4.

Let $p$ be an odd prime and let $f(n)=an^{2}+bn+c\in\mathbb{Z}[n]$ such that
$\nu_{p}(a)=0$. Let $D=b^{2}-4ac\neq 0$ denote the discriminant. Suppose the
discriminant can be expressed as $D=p^{\nu_{p}(D)}\Delta$ so that
$p\nmid\Delta$, and the valuation $\nu_{p}(D)$ is odd or $\Delta$ is a
quadratic non-residue modulo $p$. Set $\ell=\lceil\nu_{p}(D)/2\rceil$. Define
a natural number $S_{\ell}$ as in the proof of Proposition 4.1. Then

$\nu_{p}(f(n))=\begin{cases}2(m-1),&\ \text{if}\ n\equiv(p^{m-1}r-S_{\ell})\
\mbox{\rm(mod}\ p^{m}\mbox{\rm)}\ \text{for}\ m=1,2,\ldots,\ell;\\\
\nu_{p}(D),&\ \text{if}\ n\equiv-S_{\ell}\ \mbox{\rm(mod}\
p^{\ell}\mbox{\rm)}.\\\ \end{cases}$

###### Proof.

This follows immediately from applying Lemma 4.3 to Proposition 4.1. ∎

Additionally, with a little more work we can get the following corollary from
Proposition 4.1 part 1.

######  Corollary 4.5.

If $a\not\equiv 0\ \mbox{\rm(mod}\ p\mbox{\rm)}$ and $D=b^{2}-4ac=0$, then on
the $m^{th}$ level, the terminal nodes have valuations equal to $2(m-1)$ and
the non-terminal nodes have valuation greater than or equal to $2m$.

###### Proof.

First, note that

$\displaystyle\nu_{p}(an^{2}+bn+c)$
$\displaystyle=\nu_{p}(4a^{2}n^{2}+4abn+4ac)$
$\displaystyle=\nu_{p}(4a^{2}n^{2}+4abn+b^{2}-b^{2}+4ac)$
$\displaystyle=\nu_{p}((2an+b)^{2}-b^{2}+4ac)$
$\displaystyle=\nu_{p}((2an+b)^{2})$ $\displaystyle=2\nu_{p}((2an+b)).$

By Proposition 4.1 part 1, there must exist at least one non-terminal node at
$n=pq+r_{0}$, where $r_{0}\in\left\\{0,1,\ldots,p-1\right\\}$, such that
$p\mid(2a(pq+r_{0})+b)$. Thus the valuation at this node is greater than or
equal to two by the last line of the above equality. Now suppose there exists
a second non-terminating node
$r_{0}^{\prime}\in\left\\{0,1,\ldots,p-1\right\\}\backslash\left\\{0\right\\}$.
Thus $p\mid(2a(pq+r_{0}^{\prime})+b)$. From these two statements, we have

$2a(pq+r_{0})+b=pk_{1}\ \text{and}\ 2a(pq+r_{0}^{\prime})+b=pk_{2},$

for some $k_{1},k_{2}\in\mathbb{Z}$ which depend on $q$. Taking the
difference, we have

$2a(r_{0}-r_{0}^{\prime})=p(k_{1}-k_{2}).$

Since $p\nmid(r_{0}-r_{0}^{\prime})$, we have $p\mid a$, which is a
contradiction to the hypothesis. Thus all other nodes must be terminating with
a valuation equal to zero.

Suppose by induction for all levels $i$ up to $m-1$ with $m\geq 2$ the
terminating nodes have a valuation equal to $2(i-2)$. Furthermore, suppose
there is only one non-terminating node. This node has valuation greater than
or equal to $2(i-1)$.

Suppose the only non-terminating node is at $n=p^{m-1}q+r_{0}$, and so
$p^{m-1}\mid(2a(p^{m-1}q+r_{0})+b)$. This node then splits into nodes of the
form $n=p^{m}q+p^{m-1}r+r_{0}$, where $r\in\left\\{0,1,2,\ldots,p-1\right\\}$.
Without loss of generality, suppose the non-terminating node is at
$n=p^{m}q+r_{0}$, that is, $r=0$. Then a calculation yields

$2a(p^{m}q+p^{m-1}r+r_{0})+b=2ap^{m}q+2ap^{m-1}r+2ar_{0}+b.$

Since $n=p^{m}q+r_{0}$ is the non-terminating node, and we know the valuations
of $2a(p^{m}q+p^{m-1}r+r_{0})+b$ are bigger than or equal to $m-1$, the above
implies

$2a(p^{m}q+r_{0})+b=p^{m-1}k_{3},$

for $k_{3}\in\mathbb{Z}$ depending on $q$. Suppose that
$p^{m}\nmid(2a(p^{m}q+r_{0})+b)$. Then this non-terminating node
$n=p^{m}q+r_{0}$ would have valuation $\nu_{p}(2a(p^{m}q+r_{0})+b)=2(m-1)$,
which contradicts the fact it is non-terminating. Therefore,
$p^{m}\mid(2a(p^{m}q+r_{0})+b)$ and this node must have a valuation greater
than or equal to $2m$. But furthermore, we must have $p\mid k_{3}$. This and
the above equation imply that

$\displaystyle 2a(p^{m}q+p^{m-1}r+r_{0})+b$
$\displaystyle=2ap^{m}q+2ap^{m-1}r+2ar_{0}+b$
$\displaystyle=2ap^{m-1}r+p^{m-1}k_{3}$ $\displaystyle=p^{m-1}(2ar+k_{3}).$

Since $p\mid k_{3}$ and $p\nmid ar$, all other nodes on the $m^{th}$ level
must be terminating with valuation $2(m-1)$. This completes the proof. ∎

##  5 Acknowledgments

The authors would like to thank the National Science Foundation for funding
the REU program at Ursinus College through grant 1851948.

## Appendix: examples

This section includes several examples of the $p$-adic valuation trees for
quadratic polynomials.

### A tree with one infinite branch

The figure below shows a $3$-adic valuation tree for the polynomial
$f(n)=12n^{2}+16n+7$. According to case 2 of Theorem 1.1, the tree has one
infinite branch.

$q$$3q$$\boxed{0}$$3q+1$$\boxed{0}$$3q+2$$\nu_{3}\geq
1$$9q+2$$\boxed{1}$$9q+5$$\nu_{3}\geq
2$$27q+5$$\boxed{2}$$27q+14$$\boxed{2}$$27q+23$$\nu_{3}\geq
3$$81q+23$$\nu_{3}\geq
4$$81q+50$$\boxed{3}$$81q+77$$\boxed{3}$$9q+8$$\boxed{1}$

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|---
$f(n)$ | $7$ | $35$ | 87 | 163 | 263 | 387 | 535 | 707 | 903 | 1123 | 1367 |
$\nu_{3}(f(n))$ | 0 | 0 | 1 | 0 | 0 | 2 | 0 | 0 | 1 | 0 | 0 |

$n$ | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19
---|---|---|---|---|---|---|---|---|---
$f(n)$ | 1635 | 1927 | 2243 | 2583 | 2947 | 3335 | 3747 | 4183 | 4643
$\nu_{3}(f(n))$ | 1 | 0 | 0 | 2 | 0 | 0 | 1 | 0 | 0

Figure 2: A $3$-adic valuation tree for the polynomial $f(n)=12n^{2}+16n+7$,
followed by the table containing the first twenty terms of the sequence of the
$3$-adic valuations generated by $f(n)$.

### A tree with two infinite branches

For the next example, consider $f(n)=n^{2}+1$ and $p=5$. Since $D=-5^{0}\cdot
4$, the $5$-adic valuation of $D$ is even, and $-4$ is a quadratic residue
modulo $5$. By case 3(b) of Theorem 1.1, the valuation tree of $f(n)$ is
infinite with two branches.

$q$$5q$$\boxed{0}$$5q+1$$\boxed{0}$$5q+2$$\nu_{5}\geq
1$$25q+2$$\boxed{1}$$25q+7$$\nu_{5}\geq
2$$5^{3}q+7$$\boxed{2}$$5^{3}q+32$$\boxed{2}$$5^{3}q+57$$\nu_{5}\geq
3$$5^{4}q+57$$\boxed{3}$$5^{4}q+182$$\boxed{3}$$5^{4}q+307$$\boxed{3}$$5^{4}q+432$$\nu_{5}\geq
4$$5^{4}q+557$$\boxed{3}$$5^{3}q+82$$\boxed{1}$$5^{3}q+107$$\boxed{1}$$25q+12$$\boxed{1}$$\boxed{1}$$25q+22$$\boxed{1}$$5q+3$$\nu_{5}\geq
1$$25q+3$$\boxed{1}$$\boxed{1}$$25q+13$$\boxed{1}$$25q+18$$\nu_{5}\geq
2$$5^{3}q+18$$\boxed{2}$$5^{3}q+43$$\boxed{2}$$5^{3}q+68$$\nu_{5}\geq
3$$5^{4}q+68$$\boxed{3}$$5^{4}q+193$$\nu_{5}\geq
4$$5^{4}q+319$$\boxed{3}$$5^{4}q+443$$\boxed{3}$$5^{4}q+568$$\boxed{3}$$5^{3}q+93$$\boxed{2}$$5^{3}q+118$$\boxed{2}$$25q+23$$\boxed{1}$$5q+4$$\boxed{0}$

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|---
$f(n)$ | $1$ | $2$ | 5 | 10 | 17 | 26 | 37 | 50 | 65 | 82 | 101 |
$\nu_{5}(f(n))$ | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 2 | 1 | 0 | 0 |

$n$ | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19
---|---|---|---|---|---|---|---|---|---
$f(n)$ | 0 | 1 | 0 | 197 | 226 | 257 | 290 | 325 | 362
$\nu_{5}(f(n))$ | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 2 | 0

Figure 3: A $5$-adic valuation tree for the polynomial $f(n)=n^{2}+1$,
followed by the table containing the first twenty terms of the sequence of the
$5$-adic valuations generated by $f(n)$.

### A finite tree

The figures below illustrate two $3$-adic valuation trees from case 3(c) of
Theorem 1.1. Consider $f(n)=4n^{2}+160n-587$. Since $D=160^{2}+16\cdot
587=3^{7}\cdot 16$, it follows that $\nu_{3}(D)=7$ is odd. By case 3(c) of
Theorem 1.1, the tree is finite with $\ell=\lceil 7/2\rceil=4$ levels. The
second figure is the translated tree $f(n-S_{\ell})$, where
$S_{\ell}=\frac{b}{2a}=20$.

$q$$3q$$\boxed{0}$$3q+1$$\nu_{3}\geq
2$$9q+1$$\boxed{2}$$9q+4$$\boxed{2}$$9q+7$$\nu_{3}\geq 4$$27q+7$$\nu_{3}\geq
6$$81q+7$$\boxed{7}$$81q+34$$\boxed{6}$$81q+61$$\boxed{6}$$27q+16$$\boxed{4}$$27q+25$$\boxed{4}$$3q+2$$\boxed{0}$
Figure 4: A $3$-adic valuation tree for the polynomial $f(n)=4n^{2}+160n-587$.
$q$$3q$$\nu_{3}\geq 2$$9q$$\nu_{3}\geq 4$$27q$$\nu_{3}\geq
6$$81q$$\boxed{7}$$81q+27$$\boxed{6}$$81q+54$$\boxed{6}$$27q+9$$\boxed{4}$$27q+18$$\boxed{4}$$9q+3$$\boxed{2}$$9q+6$$\boxed{2}$$3q+1$$\boxed{0}$$3q+2$$\boxed{0}$
Figure 5: The translated tree: a $3$-adic valuation tree for the polynomial
$f(n-20)=4n^{2}-2187$, used to determine the tree in Figure 4.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|---
$f(n)$ | $-587$ | $-423$ | $-251$ | $-71$ | 117 | 313 | 517 | 729 | 949 | 1177 | 1413 |
$\nu_{3}(f(n))$ | 0 | 2 | 0 | 0 | 2 | 0 | 0 | 6 | 0 | 0 | 2 |

$n$ | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19
---|---|---|---|---|---|---|---|---|---
$f(n)$ | 1657 | 1909 | 2169 | 2437 | 2713 | 2997 | 3289 | 3589 | 3897
$\nu_{3}(f(n))$ | 0 | 0 | 2 | 0 | 0 | 4 | 0 | 0 | 2

Table 1: The first twenty terms of $(\nu_{3}(f(n)))$, generated by
$f(n)=4n^{2}+160n-587$.

## References

  * [1] J.-P. Allouche and J. Shallit, The ring of $k$-regular sequences. Theoret. Comput. Sci. 98 (1992), no. 2, 163–197.
  * [2] J.-P. Allouche and J. Shallit, Automatic Sequences, Theory, Applications, Generalizations, Cambridge University Press, 2003\.
  * [3] J. P. Bell, $p$-adic valuations and $k$-regular sequences, Discrete Math. 307 (2007), 3070–3075.
  * [4] L. Almodovar, A. N. Byrnes, J. Fink, X. Guan, A. Kesarwani, G. Lavigne, L. A. Medina, V. H. Moll, I. Nogues, S. Rajasekaran, E. Rowland, and A. Yuan, A closed-form solution might be given by a tree. Valuations of quadratic polynomials, Sci. Ser. A Math. Sci. 29 (2019), 11–28.
  * [5] W. Boultinghouse, J. Long, O. Kozhushkina, and J. Trulen. 2-Adic valuations of quadratic sequences. Journal of Integer Sequences 24 (2021), Article 21.6.1.
  * [6] F. Gouvêa, p-Adic Numbers: An Introduction, Springer-Verlag, 1997.
  * [7] A. M. Legendre.  Theorie des Nombres.  Firmin Didot Freres, Paris, 1830.
  * [8] L. A. Medina, V. H. Moll, and E. Rowland. Periodicity in the $p$-adic valuation of a polynomial. Journal of Number Theory 180 (2017), 139–153.
  * [9] A. M. Robert, A Course in p-adic Analysis, Springer, 2000.