# FedAUXfdp: Differentially Private One-Shot Federated Distillation

Haley Hoech  Roman Rischke  Karsten Müller&Wojciech Samek
Department of Artificial Intelligence, Fraunhofer Heinrich Hertz Institute
$\\{$haley.hoech, roman.rischke, karsten.mueller,
<EMAIL_ADDRESS>
###### Abstract

Federated learning suffers in the case of “non-iid” local datasets, i.e., when
the distributions of the clients’ data are heterogeneous. One promising
approach to this challenge is the recently proposed method FedAUX, an
augmentation of federated distillation with robust results on even highly
heterogeneous client data. FedAUX is a partially
$(\epsilon,\delta)$-differentially private method, insofar as the clients’
private data is protected in only part of the training it takes part in. This
work contributes a fully differentially private modification, termed
FedAUXfdp. We further contribute an upper bound on the $l_{2}$-sensitivity of
regularized multinomial logistic regression. In experiments with deep networks
on large-scale image datasets, FedAUXfdp with strong differential privacy
guarantees performs significantly better than other equally privatized SOTA
baselines on non-iid client data in just a single communication round. Full
privatization of the modified method results in a negligible reduction in
accuracy at all levels of data heterogeneity.

##  1 Introduction

Federated learning (FL)††International Workshop on Trustworthy Federated
Learning in conjunction with IJCAI 2022 (FL-IJCAI’22), Vienna, Austria. is a
form of decentralized machine learning, in which a global model is formed by
an orchestration server aggregating the outcome of training on a number of
local client models without any sharing of their private training data McMahan
et al. (2017). Interest in federated learning has increased recently for its
privacy and communication-efficiency advantages over centralized learning on
mobile and edge devices Li et al. (2019); Sattler et al. (2021c). A classical
mechanism for model aggregation in FL is federated averaging (FedAVG), where
the locally trained models are weighted proportionally to the size of the
local dataset. In each communication round of federated averaging, weight
updates of the clients’ local models are sent to the orchestration server,
averaged by the server, and the average is sent back to the federation of
clients to initialize the next round of training McMahan et al. (2017).

Federated ensemble distillation (FedD), an often even more communication-
efficient and accurate alternative to FedAVG, uses knowledge distillation to
transfer knowledge from clients to server Itahara et al. (2020); Lin et al.
(2020); Chen and Chao (2020); Sattler et al. (2021b). In FedD, clients and
server share a public dataset auxiliary to the clients’ private data. The
clients communicate the output of their privately trained models on the public
distillation dataset to the server, which uses the average of these outputs as
supervision for the distillation data in training the global model. In
comparison to federated averaging, federated ensemble distillation offers
additional privacy, as direct white box attacks are not possible for example,
and allows combining different model architectures, making it appealing in an
Internet-of-Things ecosystem Li et al. (2020); Chang et al. (2019); Li et al.
(2021).

FedAUX is an augmentation of federated distillation, which derives its success
from taking full advantage of the AUXiliary data. FedAUX uses this auxiliary
data for model pretraining and relevance weighting. To perform the weighting,
the clients’ output on each data point of the distillation dataset is
individually weighted by a measure of similarity between that distillation
datapoint and the client’s local data, called a ‘certainty score’. Weighting
the outputs by the scores prioritizes votes from clients whose local data is
more similar to the auxiliary/distillation data.

A major challenge of federated learning is performance when the distributions
of the clients’ data are heterogeneous, i.e. performance on “non-iid” data, as
is often the circumstance in real-world applications of FL Kairouz et al.
(2021). FedAUX overcomes that challenge, performing remarkably more
efficiently on non-iid data than other state-of-the-art federated learning
methods, federated averaging, federated proximal learning, Bayesian federated
learning, and federated ensemble distillation. For example on MobilenetV2,
FedAUX achieves 64.8% server accuracy, while even the second-best method only
achieves 46.7% Sattler et al. (2021a).

Despite its privacy benefits, federated distillation still presents a privacy
risk to clients participating Papernot et al. (2017). Data-level differential
privacy protects the clients’ data by limiting the impact of any individual
datapoint on the model and quantifies the privacy loss associated to
participating in training with parameters $(\epsilon,\delta)$. Both
governments and private institutions are increasingly interested in securing
their data using differential privacy.

Each client in the FedAUX method trains two models on their local dataset.
Sattler et al. (2021a) privatize only the scoring model, leaving the
classification model exposed. The clients’ data is accordingly only protected
with differential privacy in part of the training it participates in. In this
work, we add a local, data-level $(\epsilon,\delta)$-differentially private
mechanism for this second model and appropriately modify the FedAUX method to
apply said mechanism. We thereby contribute a ‘fully’ privatized version of
FedAUX. Full differential privacy here is used as a way of describing our
contribution of privacy over the original FedAUX method. We additionally give
an upper bound on the $l_{2}$-sensitivity of regularized multinomial logistic
regression. See Section 4.2 for background on differential privacy.

In results with deep neural networks on large scale image datasets at an
($\epsilon=0.6,\delta=2*10^{-5}$) level of differential privacy we compare
fully differentially private FedAUXfdp with two privatized baselines,
federated ensemble distillation and federated averaging in a single
communication round. FedAUXfdp outperforms these baselines dramatically on the
heterogeneous client data. Our method modifications achieve better results
than FedAUX in a single communication round and we see a negligible reduction
in accuracy of applying this strong amount of differential privacy to the
modified FedAUX method.

In Section 3 we outline the original FedAUX, in Section 4 we explain our
modification, including our privacy mechanism as well as background on
differential privacy, and in Section 5 we detail the experimental set-up and
highlight important results.

##  2 Related Work

Our method modifies Sattler et al. (2021a), who contributed a semi-
differentially private FedAUX method. For a discussion of works related to the
non-privacy aspects of FedAUX, we refer to their paper.

Cynthia Dwork introduced differential privacy Dwork and Roth (2014) and
Kasiviswanathan et al. (2008) local differential privacy. Differential privacy
bounds were greatly improved with the introduction of the moments accountant
in Abadi et al. (2016).

In addition to quantifying privacy loss, differential privacy protects
provably against membership inference attacks Shokri et al. (2017); Choquette-
Choo et al. (2021), in which an adversary can determine if a data point
participated in the training of a model. This can pose a privacy threat, for
example, if participation in model training could imply a client has a
particular disease or other risk factor. Alternatives for privatization in
general include secure multi-party computation or homomorphic encryption,
though neither protect against membership inference attacks Shokri et al.
(2017). Others have combined local differential privacy and federated
learning, notably Geyer et al. (2018); McMahan et al. (2018). While Sun and
Lyu (2021) combined federated model distillation with differential privacy,
they only attain robust results on non-iid data when the client and
distillation data contains the same classes.

Our one-shot federated distillation approach uses model distillation to
transfer the learning outcome in form of softlabels for a public distillation
dataset. Zhou et al. (2021) use dataset distillation Wang et al. (2018) to
design a communication-efficient and privacy-preserving one-shot FL mechanism.

##  3 FedAUX

###  3.1 Method

In FedAUX, there are two actors, the clients and the orchestration server.
Each client, $i=1,\ldots,n$, has its own private, local, labeled dataset
$D_{i}$. Auxiliary to the client data, is a public, unlabeled dataset
$D_{aux}$. The auxiliary data is further split into the negative data $D^{-}$,
used in training the certainty score models, and the distillation data
$D_{distill}$, used for knowledge distillation.

There are three types of models, the clients’ scoring models, the clients’
classification models, and the server’s global model, which can all be
decomposed into a feature extractor $h$ and linear or logistic regression
classification head. Whether the full model or just the classification head is
trained varies by model and we outline this next. In FedAUX four kinds of
training are conducted (see Figure 1):

Figure 1: Overview of FedAUX and FedAUXfdp training. Models secured with
differential privacy indicated with black locks.

  1. 1.

Feature extractor. Unsupervised pretraining with the public auxiliary data
$D_{aux}$ on the server to obtain the feature extractor, $h_{0}$, which is
sent to the clients and initialized in all their models as well as the
server’s.

  2. 2.

Scoring model heads. Supervised training of the scoring model classification
heads $s_{i}$ of all clients, in combination with the frozen feature extractor
$h_{0}$ to generate scoring models $f_{i}=s_{i}\circ h_{0}$. Each training is
a binary logistic regression on the extracted features of their private local
data and the public negative data $h_{0}(D_{i}\cup D^{-})$.

  3. 3.

Classification models. Supervised training of the clients’ full classification
models $g_{i}=c_{i}\circ h_{i}$, consisting of a feature extractor $h_{i}$
(initialized with $h_{0}$ from the pretraining) and linear classification head
$c_{i}$, on their local datasets $D_{i}$.

  4. 4.

Server model. Supervised training of the server’s full model $S$, consisting
of a feature extractor $h$ (initialized with $h_{0}$ from the pretraining) and
linear classification head. The server calculates an initial weight update of
the clients’ average class model weight updates from their training round. For
the server’s training, the input data $X$ is the unlabeled $D_{distill}$ and
the supervision $Y$ a $(|D_{distill}|\times n_{classes})$-dimensional matrix
of the softlabel output of the class model $g_{i}(D_{distill})$, weighted by a
certainty score for each distillation datapoint. The certainty scores are the
output of the $(\epsilon,\delta)$-differentially privatized scoring model on
the distillation data $f_{i}(D_{distill})$, measures of similarity between
each distillation data point and the client’s local data. Each entry in $Y$
is:

$\frac{\sum_{i}f_{i}(x)\cdot g_{i}(x)}{\sum_{i}f_{i}(x)},\text{for }x\in
D_{distill}.$ (1)

###  3.2 Privacy

Participating in the training of the scoring classification heads and
classification models presents a privacy risk to the private data of the
clients. In FedAUX, the scoring heads are sanitized using an
$(\epsilon,\delta)$-differentially private sanitization mechanism. FedAUX’s
mechanism for privatizing the scoring model is based on freezing the feature
extractor and using a logistic classification head. As the feature extractor
was trained on public data, only sanitizing this head is required to yield a
differentially private model. Further, using the L-BFGS optimizer in sci-kit
learn’s logistic regression guarantees finding optimal weights for the
logistic regression heads. In FedAUXfdp we privatize the classification models
in a similar fashion. This thereby makes the server models learned in
FedAUXfdp fully differentially private, as discussed in Section 4, with the
specific privacy mechanism outlined in Section 4.2.

##  4 FedAUXfdp

In the fully differentially private version of FedAUX, we adapt the training
of the classification and server models as follows. Rather than training the
full client models, we freeze the feature extractors and train only the
classification heads using a multinomial logistic regression on extracted
features of the client’s local dataset $D_{i}$. As communicating model updates
to the server poses a privacy threat, we no longer initialize the server with
the averaged weight update of the clients. Accordingly, step three in the
process is changed as follows:

  1. 3.

Classification model. Supervised training of the classification model heads
$c_{i}$ of the clients, combined with the frozen feature extractor $h_{0}$, to
generate class models $g_{i}=c_{i}\circ h_{0}$. Each is a multinomial logistic
regression on the extracted features of their private local data
$h_{0}(D_{i})$. See Figure 1.

As with the scoring models in the original FedAUX, freezing the feature
extractors, which have been trained on public data, allows us to make the
models differentially private by simply sanitizing the classification heads.
Again, we opt for logistic classification heads because the L-BFGS optimizer
in sci-kit learn’s logistic regression guarantees convergence to globally
optimal weights of the logistic regression.

We formulate the training of these classifiers as regularized empirical risk
minimization problems.

###  4.1 Regularized Empirical Risk Minimization

Let
$\boldsymbol{\beta}:=(\boldsymbol{\beta}^{T}_{1},\ldots,\boldsymbol{\beta}^{T}_{C})^{T}\in\mathbb{R}^{C(p+1)}$
with
$\boldsymbol{\beta}_{k}:=(\beta_{k,0},\ldots,\beta_{k,p})^{T}\in\mathbb{R}^{p+1}$
be the vector of trainable parameters of the regularized multinomial logistic
regression problem with $C$ classes

$\min_{\boldsymbol{\beta}}J(\boldsymbol{\beta},h,D)=\frac{1}{|D|}\sum_{i=1}^{|D|}-\log(p_{y_{i}}(h(\textbf{x}_{i})))+\frac{\lambda}{2}\|\boldsymbol{\beta}\|_{2}^{2}$
(2)

with softmax function

$p_{y_{i}}(\boldsymbol{\beta},h(\textbf{x}_{i}))=\frac{\exp(\boldsymbol{\beta}_{y_{i}}^{T}h(\textbf{x}_{i}))}{\sum_{k=1}^{C}\exp(\boldsymbol{\beta}_{k}^{T}h(\textbf{x}_{i}))}$

for a labeled data point $(\textbf{x}_{i},y_{i})$ from a dataset $D$.

Thereby, $h(\textbf{x}_{i})\in\mathbb{R}^{p+1}$ is an extracted feature vector
with the first coordinate being a constant for the bias term $\beta_{k,0}$,
and $y_{i}\in\\{1,\ldots,C\\}$ the corresponding class label. We assume
w.l.o.g. that

$\|h(\textbf{x})\|_{2}\leq 1.$ (3)

To fulfill this assumption, we normalize the input features for the logistic
regression problem as follows

$\tilde{h}(\textbf{x}):=h(\textbf{x})\Big{(}\operatorname*{max}_{\textbf{x}\in
D}\|h(\textbf{x})\|_{2}\Big{)}^{-1}.$ (4)

###  4.2 Privacy

We privatize the classification models using $(\epsilon,\delta)$-differential
privacy. Informally, differential privacy anonymizes the client data in this
context, insofar as with very high likelihood the results of the model would
be very similar regardless whether or not a particular data point participates
in training Dwork and Roth (2014).

####  4.2.1 Definitions

######  Definition 1.

A randomized mechanism $\mathcal{M}:\mathcal{D}\rightarrow\mathcal{R}$
satisfies $(\epsilon,\delta)$-differential privacy, if for any two adjacent
inputs $D_{1}$ and $D_{2}$ that only differ in one element and for any subset
of outputs $S\subseteq\mathcal{R},$

$P[D_{1}\in S]\leq\exp(\epsilon)P[\mathcal{M}(D_{2})\in S]+\delta.$

We use the Gaussian mechanism, in which a specific amount of Gaussian noise is
added relative to the $l^{2}$-sensitivity Dwork and Roth (2014) and according
to pre-selected $\epsilon$ and $\delta$ values.

######  Definition 2.

For $\epsilon\in(0,1)$, $c^{2}>2\ln(1.25/\delta)$, the Gaussian Mechanism with
parameter $\sigma\geq c\Delta_{2}(\mathcal{M})/\epsilon$ is
$(\epsilon,\delta)$-differentially private.

######  Definition 3.

For two datasets, $D_{1},D_{2}$ differing in one datapoint, the
$l_{2}$-sensitivity is

$\Delta(\mathcal{M})=\operatorname*{max}_{D_{1},D_{2}\in\mathcal{D}}\|\mathcal{M}(D_{1})-\mathcal{M}(D_{2})\|_{2}$

####  4.2.2 Sensitivity of the Classification Models

We contribute the following theorem for the $l_{2}$-sensitivity of regularized
multinomial logistic regression (2), which generalizes a corollary from
Chaudhuri et al. (2011).

######  Theorem 1.

The $l_{2}$-sensitivity of regularized multinomial logistic regression, as
defined in (2), is at most $\frac{2\sqrt{C}}{\lambda|D|}$.

###### Proof.

W.l.o.g. we set $h(\textbf{x})=\textbf{x}$ in this proof and omit the argument
$h$ in the definition of $J$ for ease of exposition. Let
$D=\\{(\textbf{x}_{1},y_{1}),\ldots,(\textbf{x}_{N},y_{N})\\}$ and
$D^{\prime}=(D\setminus\\{(\textbf{x}_{N},y_{N})\\})\cup\\{(\textbf{x}^{\prime}_{N},y^{\prime}_{N})\\}$.
That is, $D$ and $D^{\prime}$ differ in exactly one data point. Furthermore,
let

$\displaystyle\boldsymbol{\beta}_{1}^{*}$ $\displaystyle=$
$\displaystyle\operatorname*{arg\,min}_{\boldsymbol{\beta}}J(\boldsymbol{\beta},D)$
(5) $\displaystyle\boldsymbol{\beta}_{2}^{*}$ $\displaystyle=$
$\displaystyle\operatorname*{arg\,min}_{\boldsymbol{\beta}}J(\boldsymbol{\beta},D^{\prime}).$
(6)

The goal is to show that
$\|\boldsymbol{\beta}_{1}^{*}-\boldsymbol{\beta}_{2}^{*}\|_{2}\leq\frac{2\sqrt{C}}{\lambda
N}$. We define

$\displaystyle d(\boldsymbol{\beta})$ $\displaystyle:=$ $\displaystyle
J(\boldsymbol{\beta},D^{\prime})-J(\boldsymbol{\beta},D)$ $\displaystyle=$
$\displaystyle\frac{1}{N}\left(l(\boldsymbol{\beta},\textbf{x}^{\prime}_{N})-l(\boldsymbol{\beta},\textbf{x}_{N})\right),$

with the log-softmax loss function

$\displaystyle
l(\boldsymbol{\beta},\textbf{x}):=-\log(p_{y}(\boldsymbol{\beta},\textbf{x}))$
(8)

for an arbitrary data point $(\textbf{x},y)$.

With

$\displaystyle\nabla_{\boldsymbol{\beta}}\ l(\boldsymbol{\beta},\textbf{x})$
$\displaystyle=$ $\displaystyle-\frac{\nabla_{\boldsymbol{\beta}}\
p_{y}(\boldsymbol{\beta},\textbf{x})}{p_{y}(\boldsymbol{\beta},\textbf{x})}$
(9)

we obtain

$\displaystyle\frac{\partial\ p_{k}(\boldsymbol{\beta},\textbf{x})}{\partial\
\boldsymbol{\beta}_{k}}$ $\displaystyle=$
$\displaystyle\frac{\exp(\boldsymbol{\beta}_{k}^{T}\textbf{x})\cdot\sum_{j\neq
k}\exp(\boldsymbol{\beta}_{j}^{T}\textbf{x})}{(\sum_{j}\exp(\boldsymbol{\beta}_{j}^{T}\textbf{x}))^{2}}\textbf{x}$
(10) $\displaystyle\frac{\partial\
p_{k}(\boldsymbol{\beta},\textbf{x})}{\partial\ \boldsymbol{\beta}_{\ell\neq
k}}$ $\displaystyle=$
$\displaystyle-\frac{\exp(\boldsymbol{\beta}_{k}^{T}\textbf{x})\cdot\exp(\boldsymbol{\beta}_{\ell}^{T}\textbf{x})}{(\sum_{j}\exp(\boldsymbol{\beta}_{j}^{T}\textbf{x}))^{2}}\textbf{x}$
(11) $\displaystyle\frac{\partial\ l(\boldsymbol{\beta},\textbf{x})}{\partial\
\boldsymbol{\beta}_{k=y}}$ $\displaystyle=$ $\displaystyle\frac{\sum_{j\neq
k}\exp(\boldsymbol{\beta}_{j}^{T}\textbf{x})}{\sum_{j}\exp(\boldsymbol{\beta}_{j}^{T}\textbf{x})}\textbf{x}$
(12) $\displaystyle\frac{\partial\ l(\boldsymbol{\beta},\textbf{x})}{\partial\
\boldsymbol{\beta}_{\ell\neq y}}$ $\displaystyle=$
$\displaystyle-\frac{\exp(\boldsymbol{\beta}_{\ell}^{T}\textbf{x})}{\sum_{j}\exp(\boldsymbol{\beta}_{j}^{T}\textbf{x})}\textbf{x}.$
(13)

Note, that the factors on the rhs of (12) and (13) have absolute values of at
most 1. Hence, we can bound

$\displaystyle\|\nabla_{\boldsymbol{\beta}}\ d(\boldsymbol{\beta})\|_{2}$
$\displaystyle=$ $\displaystyle\frac{1}{N}\|\nabla_{\boldsymbol{\beta}}\
l(\boldsymbol{\beta},\textbf{x}^{\prime}_{N})-\nabla_{\boldsymbol{\beta}}\
l(\boldsymbol{\beta},\textbf{x}_{N})\|_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{N}\left(\|\nabla_{\boldsymbol{\beta}}\
l(\boldsymbol{\beta},\textbf{x}^{\prime}_{N})\|_{2}+\|\nabla_{\boldsymbol{\beta}}\
l(\boldsymbol{\beta},\textbf{x}_{N})\|_{2}\right)$ $\displaystyle\leq$
$\displaystyle\frac{1}{N}\left(\sqrt{C}\|\textbf{x}^{\prime}_{N}\|_{2}+\sqrt{C}\|\textbf{x}_{N}\|_{2}\right)$
$\displaystyle\leq$ $\displaystyle\frac{2\sqrt{C}}{N},$

where the last inequality follows from assumption (3) that
$\|\textbf{x}\|_{2}\leq 1$.

We observe that due to the convexity of $l(\boldsymbol{\beta},\textbf{x})$ in
$\boldsymbol{\beta}$ and the 1-strong convexity of the $l_{2}$-regularization
term in (2), $J(\boldsymbol{\beta},D)$ is $\lambda$-strongly convex. Hence, we
obtain by Shalev-Shwartz inequality Shalev-Shwartz (2007)

$\displaystyle\left(\nabla_{\boldsymbol{\beta}}\
J(\boldsymbol{\beta_{1}^{*}},D)-\nabla_{\boldsymbol{\beta}}\
J(\boldsymbol{\beta_{2}^{*}},D)\right)^{T}\left(\boldsymbol{\beta_{1}^{*}}-\boldsymbol{\beta_{2}^{*}}\right)\geq$
$\displaystyle\lambda\|\boldsymbol{\beta_{1}^{*}}-\boldsymbol{\beta_{2}^{*}}\|_{2}^{2}.$
(15)

Moreover, by construction of $d(\boldsymbol{\beta}),$

$J(\boldsymbol{\beta_{2}^{*}},D)+d(\boldsymbol{\beta_{2}^{*}})=J(\boldsymbol{\beta_{2}^{*}},D^{\prime}).$
(16)

By optimality of $\boldsymbol{\beta_{1}^{*}}$ and
$\boldsymbol{\beta_{2}^{*}}$, it holds

$\displaystyle\textbf{0}=\nabla_{\boldsymbol{\beta}}\
J(\boldsymbol{\beta_{1}^{*}},D)$ $\displaystyle=$
$\displaystyle\nabla_{\boldsymbol{\beta}}\
J(\boldsymbol{\beta_{2}^{*}},D^{\prime})$ $\displaystyle=$
$\displaystyle\nabla_{\boldsymbol{\beta}}\
J(\boldsymbol{\beta_{2}^{*}},D)+\nabla_{\boldsymbol{\beta}}\
d(\boldsymbol{\beta_{2}^{*}}).$

Applying the Cauchy-Schwartz inequality finally leads to

$\displaystyle\|\boldsymbol{\beta_{1}^{*}}-\boldsymbol{\beta_{2}^{*}}\|_{2}\cdot\|\nabla_{\boldsymbol{\beta}}\
d(\boldsymbol{\beta_{2}^{*}})\|_{2}\geq\left(\boldsymbol{\beta_{1}^{*}}-\boldsymbol{\beta_{2}^{*}}\right)^{T}\nabla_{\boldsymbol{\beta}}\
d(\boldsymbol{\beta_{2}^{*}})$ (18) $\displaystyle=$
$\displaystyle\left(\boldsymbol{\beta_{1}^{*}}-\boldsymbol{\beta_{2}^{*}}\right)^{T}\left(\nabla_{\boldsymbol{\beta}}\
J(\boldsymbol{\beta_{1}^{*}},D)-\nabla_{\boldsymbol{\beta}}\
J(\boldsymbol{\beta_{2}^{*}},D)\right)$ $\displaystyle\geq$
$\displaystyle\lambda\|\boldsymbol{\beta_{1}^{*}}-\boldsymbol{\beta_{2}^{*}}\|_{2}^{2},$

which concludes the proof, since

$\|\boldsymbol{\beta_{1}^{*}}-\boldsymbol{\beta_{2}^{*}}\|_{2}\leq\frac{\|\nabla_{\boldsymbol{\beta}}\
d(\boldsymbol{\beta_{2}^{*}})\|_{2}}{\lambda}\leq\frac{2\sqrt{C}}{\lambda N}.$
(19)

∎

We remark that in the binary case ($C=2$) one regression head parameterized by
$\boldsymbol{\beta}\in\mathbb{R}^{(p+1)}$ suffices, resulting in an
$l_{2}$-sensitivity of at most $\frac{2}{\lambda|D|}$.

####  4.2.3 Private Mechanism

Using Theorem 1 and the Gaussian mechanism, we get our
$(\epsilon,\delta)$-differentially private mechanism for sanitizing the
multinomial classification models as follows:

$\mathcal{M}_{priv}(D)=\mathcal{M}(D)+\mathcal{N}(0,I\sigma^{2}),\text{ where
}$ $\sigma^{2}=\frac{8Cln(1.25\delta^{-1})}{\epsilon^{2}\lambda^{2}|D|^{2}}$

This leads to the overall training procedure for the classification models
described in Algorithm 1.

Algorithm 1 Classification model training and privatization

for each client do

$\boldsymbol{\beta}^{*}\rightarrow\operatorname*{argmin}_{\boldsymbol{\beta}}J(\boldsymbol{\beta},h,D)$

$\sigma^{2}\rightarrow\frac{8C\ln(1.25\delta^{-1})}{\epsilon^{2}\lambda^{2}(|D|)^{2}}$

$\boldsymbol{\beta}^{*}\rightarrow\boldsymbol{\beta}^{*}+\mathcal{N}(0,I\sigma^{2})$

end for

###  4.3 Cumulative Privacy Loss

By the composability and post-processing properties of differentially private
mechanisms Dwork and Roth (2014), the cumulative privacy loss for an
individual client’s dataset in training of the server’s model is equal to the
sum of the loss of the scoring and classification models. The server model is
$(\epsilon,\delta)$-differentially private, where

$\epsilon=\epsilon_{scores}+\epsilon_{classes}$
$\delta=\delta_{scores}+\delta_{classes}$

##  5 Experiments

We ran experiments on large-scale convolutional, ShuffleNet- Zhang et al.
(2018), MobileNet- Sandler et al. (2018), and ResNet-style He et al. (2016)
networks, using CIFAR-10 as local client data and both STL-10 and CIFAR-100 as
auxiliary data. Of the auxiliary data, 80% is used for distillation and 20%
for unsupervised pretraining. The pretraining is done by contrastive
representation learning using the Adam optimizer with a learning rate of
$10^{-3}.$

The number of clients is $n=20$ and there is full participation in one round
of communication. The training data is split among the clients using a
Dirichlet distribution with parameter $\alpha$ as done first in Hsu et al.
(2019) and later in Lin et al. (2020); Chen and Chao (2020). With the lowest
$\alpha=0.01$, clients see almost entirely one class of images. With the
highest $\alpha=10.24$, each client sees a substantial number of images from
every class. See Table 1. We follow Sattler et al. (2021a) in their selection
of highlighted Dirichlet parameters $\alpha$, who chose
$\alpha=2^{n}*10^{-2},$ for $n\in\\{0,2,4,10\\}$.

Class |  $\alpha$ = 0.01 |  $\alpha$ = 0.04 |  $\alpha$ = 0.16 |  $\alpha$ = 10.24
---|---|---|---|---
First | 94.5% | 75.3% | 56.8% | 15.1%
Second | 5.2% | 16.6% | 22.3% | 13.6%
Third | 0.3% | 5.6% | 10.1% | 12.0%
Table 1: Ranked percentage of data coming from the three largest classes for
each level of data heterogeneity

We find the optimal weights of the class model logistic regressions using
scikit-learn’s LogisticRegression with the L-BFGS Liu and Nocedal (1989)
optimizer. For baselines, we chose Federated Ensemble Distillation (FedD) and
Federated Averaging (FedAVG), which we pretrain (+P) in the same fashion as
FedAUXfdp. We also compare FedAUXfdp to FedAUX, but with a frozen feature
extractor (+F) for consistency. In FedAUX+F, the clients’ local models (linear
classification heads) are trained for 40 local epochs. For FedAUX+F,
FedAUXfdp, and FedD+P, the full sever model is trained for 10 distillation
epochs using the Adam optimizer with a learning rate of $5\cdot 10^{-5}$ and a
batch size of 128. For FedAVG+P, the average of the weights of the clients’
logistic regressions is used as a classification head on top of the frozen
feature extractor on the server.

For privacy, we chose $(\epsilon=0.1,\delta=10^{-5})$ for the scores and
unless otherwise mentioned $(\epsilon=0.5,\delta=10^{-5})$ for the classes. We
choose regularization parameter $\lambda=0.01$ for both the certainty score
and class models unless otherwise mentioned.

| ShuffleNet |  | MobileNetv2
---|---|---|---
Method | $\alpha=0.01$ | $\alpha=0.04$ | $\alpha=0.16$ | $\alpha=10.24$ |  | $\alpha=0.01$ | $\alpha=0.04$ | $\alpha=0.16$ | $\alpha=10.24$
FedAVG+P | 46.0$\pm$ 0.4 | 56.7$\pm$ 6.6 | 67.5$\pm$ 3.5 | 74.1 $\pm$ 1.4 |  | 47.2$\pm$ 2.6 | 54.2$\pm$ 5.5 | 65.6$\pm$ 0.9 | 72.0 $\pm$ 0.6
FedD+P | 41.8 $\pm$ 4.4 | 54.7 $\pm$ 5.0 | 68.8 $\pm$ 2.1 | 72.3 $\pm$ 1.6 |  | 43.7 $\pm$ 1.8 | 52.2 $\pm$ 4.6 | 67.0 $\pm$ 1.7 | 70.8 $\pm$ 0.2
FedAUXfdp | 75.2 $\pm$ 1.1 | 74.6 $\pm$ 1.1 | 72.3 $\pm$ 0.6 | 71.7 $\pm$ 1.3 |  | 72.8 $\pm$ 0.4 | 72.0 $\pm$ 1.2 | 70.8 $\pm$ 0.2 | 69.4 $\pm$ 0.8

Table 2: Server model inference accuracy of FedAUXfdp as compared to FL
baselines with pretraining. All methods cumulative privacy loss
($\epsilon=0.6,\delta=2e-05$).

As shown in Table 2, on both ShuffleNet and MobileNetv2 architectures
FedAUXfdp significantly outperforms baselines in the most heterogeneous
settings ($\alpha=0.01,0.04).$ While the baselines undergo a steady reduction
in accuracy as client data heterogeneity increases, FedAUXfdp is even
improving. As data heterogeneity increases fewer classes per client result in
the addition of less noise, see Theorem 1.

|  | ShuffleNet |  | MobileNetv2
---|---|---|---|---
Method | Class DP | $\alpha=0.01$ | $\alpha=0.04$ | $\alpha=0.16$ | $\alpha=10.24$ |  | $\alpha=0.01$ | $\alpha=0.04$ | $\alpha=0.16$ | $\alpha=10.24$
FedAUX+F | None | 64.8 $\pm$ 1.1 | 64.9 $\pm$ 0.5 | 67.7 $\pm$ 0.8 | 73.4 $\pm$ 0.1 |  | 60.1 $\pm$ 1.2 | 61.2 $\pm$ 1.8 | 63.7 $\pm$ 0.8 | 67.5 $\pm$ 0.0
FedAUXfdp | None | 76.1 $\pm$ 0.3 | 75.6 $\pm$ 0.4 | 75.2 $\pm$ 0.5 | 75.4 $\pm$ 0.1 |  | 73.0 $\pm$ 0.5 | 73.3 $\pm$ 0.6 | 73.2 $\pm$ 0.2 | 73.0 $\pm$ 0.1
FedAUXfdp | (1.0, 1e-05) | 75.7 $\pm$ 0.7 | 75.1 $\pm$ 0.7 | 74.6 $\pm$ 0.5 | 74.9 $\pm$ 0.2 |  | 73.0 $\pm$ 0.4 | 72.7 $\pm$ 1.0 | 72.7 $\pm$ 0.3 | 72.4 $\pm$ 0.0
FedAUXfdp | (0.5, 1e-05) | 75.2 $\pm$ 1.1 | 74.6 $\pm$ 1.1 | 72.3 $\pm$ 0.6 | 71.7 $\pm$ 1.3 |  | 72.8 $\pm$ 0.4 | 72.0 $\pm$ 1.2 | 70.8 $\pm$ 0.2 | 69.4 $\pm$ 0.8
FedAUXfdp | (0.1, 1e-05) | 60.8 $\pm$ 2.4 | 59.4 $\pm$ 5.8 | 33.9 $\pm$ 5.4 | 34.6 $\pm$ 3.0 |  | 66.4 $\pm$ 3.3 | 53.1 $\pm$ 12.9 | 38.9 $\pm$ 4.4 | 34.9 $\pm$ 3.3
FedAUXfdp | (0.01, 1e-05) | 36.3 $\pm$ 5.1 | 39.8 $\pm$ 7.5 | 12.6 $\pm$ 5.1 | 11.7 $\pm$ 3.5 |  | 44.4 $\pm$ 6.8 | 28.7 $\pm$ 5.1 | 16.6 $\pm$ 5.8 | 11.5 $\pm$ 0.8

Table 3: FedAUXfdp server model inference accuracy at various levels of class
differential privacy $(\epsilon,\delta)$ and comparison to FedAUX+F server
model inference accuracy. Scoring model privacy for all methods
($\epsilon=0.1,\delta=1e-05$).

Table 3 shows the impact on the server model accuracy from the method
modifications and from different levels of privacy in FedAUXfdp. The method
modifications (FedAUXfdp without the class differential privacy) are an all-
around improvement in accuracy over FedAUX+F, especially on non-iid client
data. The logistic classification heads outperform the linear ones in a single
communication round. For FedAUXfdp with no class differential privacy the
results are nearly constant as opposed to FedAUX+F, where one sees the usual
improvement as iid-ness increases.

Privatizing FedAUXfdp at additional epsilon-delta values of $(0.5,10^{-5})$
results in nearly no reduction in accuracy over FedAUXfdp with no class model
privacy. Only at $\epsilon=0.1$ we see a drop in accuracy. With equal
regularization, the additional differential privacy impacts the models trained
on the non-iid data distributions less than those trained on homogeneous data,
again due to the class size term $C$ in the $l_{2}$-sensitivity from Theorem
1.

Figure 2: Accuracy vs. regularization. Server model inference accuracy of FedAUXfdp on ShuffleNet with and without $(\epsilon=0.01,\delta=1e-05)$ class model differential privacy at various levels of class model regularization $\lambda$.  Distill Data | $\alpha=0.01$ | $\alpha=0.04$ | $\alpha=0.16$ | $\alpha=10.24$
---|---|---|---|---
STL-10 | 77.2 $\pm$ 0.5 | 75.4 $\pm$ 1.0 | 74.7 $\pm$ 0.9 | 74.4 $\pm$ 0.8
CIFAR-100 | 70.4 $\pm$ 0.7 | 68.9 $\pm$ 1.8 | 67.6 $\pm$ 1.6 | 68.5 $\pm$ 1.9
Table 4: FedAUXfdp server model inference accuracy on ResNet8 with
distillation data sharing 9/10 classes (STL-10) versus entirely different
distillation data classes (CIFAR-100).

The drop in accuracy of adding class differential privacy can be partially
compensated for by increasing the regularization parameter $\lambda$ of the
client models’ logistic regressions. Regularization reduces model variance and
therefore the impact an individual datapoint has on the model. It thus affects
the sensitivity of a differentially private mechanism as in the corollary from
Chaudhuri et al. (2011), which our sensitivity theorem generalizes. As shown
in Figure 2, on the ShuffleNet model architecture, increasing the
regularization from $\lambda=0.01$ to $\lambda=1$ nearly eliminates the gap
between the accuracy with and without $(\epsilon=0.01,\delta=10^{-5})$ class
model differential privacy at all levels of data heterogeneity $\alpha$. The
additional regularization does, however, reduce the accuracy of the model
without the class differential privacy, moreso the more homogeneous the client
data.

Table 4 shows results on ResNet with both STL-10 and CIFAR-100 as distillation
data. STL-10 and CIFAR10 share 9/10 of the same classes, while CIFAR-100 has
completely different classes. Even with distillation classes unmatching client
classes, we still see robust results.

##  6 Conclusion

In this work, we have modified the FedAUX method, an augmentation of federated
distillation, and made it fully differentially private. We have contributed a
mechanism that privatizes respectably with little loss in model accuracy,
particularly on non-iid client data. We additionally contributed a theorem for
the sensitivity of $l_{2}$ regularized multinomial logistic regression. On
large scale image datasets we have examined the impact of different amounts of
differential privacy and regularization. Measuring the impact of federated
averaging, distillation, and differential privacy on the attackability of the
global server model would be an interesting investigation direction.

## References

  * Abadi et al. [2016] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 308–318, 2016.
  * Chang et al. [2019] Hongyan Chang, Virat Shejwalkar, Reza Shokri, and Amir Houmansadr.  Cronus: Robust and heterogeneous collaborative learning with black-box knowledge transfer.  arXiv preprint arXiv:1912.11279, 2019.
  * Chaudhuri et al. [2011] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate.  Differentially private empirical risk minimization.  J. Mach. Learn. Res., 12:1069–1109, 2011.
  * Chen and Chao [2020] Hong-You Chen and Wei-Lun Chao.  FedDistill: Making bayesian model ensemble applicable to federated learning.  arXiv preprint arXiv:2009.01974, 2020.
  * Choquette-Choo et al. [2021] Christopher A. Choquette-Choo, Florian Tramer, Nicholas Carlini, and Nicolas Papernot.  Label-only membership inference attacks.  In Proceedings of the 38th International Conference on Machine Learning, PMLR, volume 139, pages 1964–1974, 2021.
  * Dwork and Roth [2014] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014.
  * Geyer et al. [2018] Robin C. Geyer, Tassilo Klein, and Moin Nabi.  Differentially private federated learning: A client level perspective.  arXiv preprint arXiv:1712.07557v2, 2018.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778, 2016.
  * Hsu et al. [2019] Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown.  Measuring the effects of non-identical data distribution for federated visual classification.  arXiv preprint arXiv:1909.06335, 2019.
  * Itahara et al. [2020] Sohei Itahara, Takayuki Nishio, Yusuke Koda, Masahiro Morikura, and Koji Yamamoto.  Distillation-based semi-supervised federated learning for communication-efficient collaborative training with non-iid private data.  arXiv preprint arXiv:2008.06180, 2020.
  * Kairouz et al. [2021] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurèlien Bellet, and Mehdi Bennis.  Advances and open problems in federated learning.  In Foundations and Trends in Machine Learning, volume 14, pages 1–210, 2021.
  * Kasiviswanathan et al. [2008] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  What can we learn privately?  In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 531–540, 2008.
  * Li et al. [2019] Qinbin Li, Zeyi Wen, and Bingsheng He.  Federated learning systems: Vision, hype and reality for data privacy and protection.  arXiv preprint arXiv:1907.09693, 2019.
  * Li et al. [2020] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang.  On the convergence of FedAvg on non-iid data.  In Proceedings of 8th International Conference on Learning Representations (ICLR). OpenReview.net, 2020.
  * Li et al. [2021] Yiying Li, Wei Zhou, Huaimin Wang, Haibo Mi, and Timothy M Hospedales.  Fedh2l: Federated learning with model and statistical heterogeneity.  arXiv preprint arXiv:2101.11296, 2021.
  * Lin et al. [2020] Tao Lin, Lingjing Kong, Sebastian U. Stich, and Martin Jaggi.  Ensemble distillation for robust model fusion in federated learning.  In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
  * Liu and Nocedal [1989] Dong C. Liu and Jorge Nocedal.  On the limited memory BFGS method for large scale optimization.  Math. Program., 45(1-3):503–528, 1989.
  * McMahan et al. [2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1273–1282, 2017.
  * McMahan et al. [2018] Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang.  Learning differentially private recurrent language models.  In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2018.
  * Papernot et al. [2017] Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, Ian Goodfellow, and Kunal Talwar.  Semi-supervized knowledge transfer for deep learning from private training data.  In Proceedings of the 5th International Conference on Learning Representations (ICLR). OpenReview.net, 2017.
  * Sandler et al. [2018] Mark Sandler, Andrew G. Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  MobileNetV2: Inverted residuals and linear bottlenecks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 4510–4520, 2018.
  * Sattler et al. [2021a] Felix Sattler, Tim Korjakow, Roman Rischke, and Wojciech Samek.  Fedaux: Leveraging unlabeled auxiliary data in federated learning.  In IEEE Transactions on Neural Networks and Learning Systems, 2021\.
  * Sattler et al. [2021b] Felix Sattler, Arturo Marban, Roman Rischke, and Wojciech Samek.  Cfd: Communication-efficient federated distillation via soft-label quantization and delta coding.  IEEE Trans. Netw. Sci. Eng., 2021.
  * Sattler et al. [2021c] Felix Sattler, Klaus-Robert Müller, and Wojciech Samek.  Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints.  IEEE Transactions on Neural Networks and Learning Systems, 32(8):3710–3722, 2021.
  * Shalev-Shwartz [2007] Shai Shalev-Shwartz.  Online Learning: Theory, Algorithms, and Applications.  PhD thesis, Hebrew University, 2007.
  * Shokri et al. [2017] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov.  Membership inference attacks against machine learning models.  In IEEE Symposium on Security and Privacy, pages 3–18, 2017.
  * Sun and Lyu [2021] Lichao Sun and Lingjuan Lyu.  Federated model distillation with noise-free differential privacy.  In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21), 2021.
  * Wang et al. [2018] Tongzhou Wang, Jun-Yan Zhu, Antonio Torralba, and Alexei A. Efros.  Dataset distillation.  arXiv preprint arXiv:1811.10959, 2018.
  * Zhang et al. [2018] Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun.  ShuffleNet: An extremely efficient convolutional neural network for mobile devices.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 6848–6856, 2018.
  * Zhou et al. [2021] Yanlin Zhou, George Pu, Xiyao Ma, Xiaolin Li, and Dapeng Wu.  Distilled one-shot federated learning.  arXiv preprint arXiv:2009.07999, 2021.


# Modular Arithmetic Study on Ascending and Descending Operations Related with
Collatz Conjecture and Origin of the Operation

Kyo Jin Ihn

###### Abstract

Sequence of numbers generated by the recurrence relation based on the Collatz
conjecture is investigated. An arithmetic operation on the Collatz conjecture
is called descending operation, and ascending operation is carried out
reversely to the descending operation. Study on the $3x+1$ problem against
every integer is relevant to that of descending operation against every odd.
Any odds can be generated by ascending operations against odds not multiple of
3, and vise versa. Ascending operations against an odd not multiple of 3 can
generate infinite number of odds in the next generation. The odds multiple of
3 are terminal numbers of sequences that no further ascending operations are
possible. Descending operations against the odds 1,5,21,
$\cdots\left(=\sum_{j=0}^{m}4^{j}\right)$ reach 1, and otherwise reach the
odds greater than or equal to 5. No two odds except 1 in each sequence are the
same, and the each descending sequence is unique. Every descending sequence
can start from terminal numbers, and reaches ultimately the origin of 1 as
indicated by the Collatz conjecture. Sequences of odds in the same pattern
ignoring the sizes of the odds are generated by ascending operations in the
same number of doubling operations against the odds in modular arithmetic.

###### keywords:

Collatz conjecture, Modular arithmetic, 3x+1 problem, Sequence of numbers,
Recurrence relation, Fractal

††journal: Indagationes Mathematicae

organization=Department of Chemical Engineering, Kangwon National
University,city=Chunchon, postcode=24341, country=Korea (South)

##  1 Introduction

The Collatz conjecture introduced in 1937 by Lothar Collatz examines whether
repeating arithmetic operations will transform every positive integer into
1.[1] It is known as 3x+1 problem.[1] The 3x+1 problem involves the operations
generating a sequence of numbers as follows: $3x+1$ operation if it is odd,
and halving operation if it is even. The conjecture is that the sequences
generated by the consecutive operations against any positive integers reach
always 1.[1]

By the Collatz conjecture, halving operations until to reach an odd followed
by $3x+1$ operation against a positive odd $x$ is called descending operation
in this study. If we let $x_{k-1}$ be a positive odd generated by a descending
operation against a positive odd $x_{k}$, number of halving operations is
determined by p-adic valuation such that
$m_{k-1}=\nu_{2}\left(3x_{k}+1\right)$, .

The descending operation includes two operations such that $3x_{k}+1$
operation against an odd $x_{k}$ and halving operations against the even
$3x_{k}+1$ until to reach an odd $x_{k-1}$. If an even generates an odd
$x_{k}$ by halving operations, it belongs to the evens generated in the
process of descending operation against an odd $x_{k+1}$. Every odd is
generated by the halving operation against every even. Consequently, in
proving the Collatz conjecture, the study on the 3x+1 problem against every
positive integer is relevant to the study using the recurrence relation of the
descending operation against every positive odd.

Consecutive descending operations using the recurrence relation
$x_{k-1}=\left(3x_{k}+1\right)/2^{m_{k-1}}$ generate a sequence of odds.
N-terms of descending sequence can be expressed as $x_{n}\rightarrow
x_{n-1}\rightarrow\cdots\rightarrow x_{k}\rightarrow\cdots\rightarrow
x_{1}\rightarrow x_{0}$. The $x_{0}$ is not always the origin of 1 unless it
is defined. The odds $x_{n-1}$ to $x_{0}$ in the sequence are not multiples of
3, since the odds multiples of 3 cannot be generated by the descending
operation.

Each sequence of odds generated by consecutive descending operations is
unique, because numbers of halving operations are fixed. Descending sequences
can be thus expressed by the odds and the numbers of halving operations
instead of showing whole evens for simplicity. Collatz conjecture states that
every descending sequence reaches ultimately the origin of 1.[1]

The reverse operation against the descending operation such that
$\left(2^{m}x-1\right)/3$ operation against a positive odd $x$ not multiple of
3 is called ascending operation, where $m$ is number of doubling operations to
show $2^{m}x\equiv 1\left(mod\>3\right)$. The odds generated by the ascending
operations from an odd correspond to the first generation odds. Ascending
operations against an odd not multiple of 3 can generate infinite number of
odds in the first generation, since multiple doubling operations are possible.

##  2 Types of ascending operations

###  2.1 First generation odds

Odds $x_{k}$ are generated by the recurrence relation
$x_{k}=\left(2^{m_{k-1}}x_{k-1}-1\right)/3$ of ascending operation with
$m_{k-1}$ times of doubling operations against a positive odd $x_{k-1}$ not
multiple of 3. Doubling operations against every odd can generate every even.
Since $2^{2}\equiv 1\left(mod\>3\right)$, $2^{2m}\equiv 1\left(mod\>3\right)$
and $2^{2m-1}\equiv-1\left(mod\>3\right)$, where $m$ is positive integer.
$2^{2m}x_{0}\equiv 1\left(mod\>3\right)$ and
$2^{2m-1}x_{0}\equiv-1\left(mod\>3\right)$ by the odds $x_{0}\equiv
1\left(mod\>3\right)$, and $2^{2m-1}x_{0}\equiv 1\left(mod\>3\right)$ and
$2^{2m}x_{0}\equiv-1\left(mod\>3\right)$ by
$x_{0}\equiv-1\left(mod\>3\right)$. Thus, ascending operations are performed
by every two doubling operations. This proves Theorem 1.

###### Theorem 1

$2^{2m}x\equiv 1\left(mod\>3\right)$ by positive odd $x\equiv
1\left(mod\>3\right)$ and $2^{2m-1}x\equiv 1\left(mod\>3\right)$ by
$x\equiv-1\left(mod\>3\right)$, where m is positive integer.

Tables 1 and 2 are the examples of first generation odds generated by
ascending operations concerning up to 12 times of doubling operations against
$x_{0}=1$ and 5. Ascending operations against $x_{0}=1$ using the recurrence
relation $x_{1}=\left(2^{m}x_{0}-1\right)/3$ generate the odds
$x_{1}=\sum_{j=0}^{(m-2)/2}4^{j}$ for even $m$ by Theorem 1. Ascending
operations against $x_{0}=5$ generate the odds
$x_{1}=2^{m}+\sum_{j=0}^{(m-1)/2}4^{j}$ for odd $m$.

Table 1: Examples of first generation odds $x_{1}=\sum_{j=0}^{(m-2)/2}4^{j}$ for even $m$ generated by the recurrence relation $x_{1}=\left(2^{m}x_{0}-1\right)/3$ of ascending operation against $x_{0}=1$ $x_{0}$ | $m$ | $2^{m}x_{0}$ | $x_{1}$ | $x_{1}\;(mod\;3)$ | $2^{m}x_{0}\;(mod\;3)$
---|---|---|---|---|---
1 | 1 | $2$ |  |  |
1 | 2 | $2^{2}$ | 1 | 1 | 1
1 | 3 | $2^{3}$ |  |  |
1 | 4 | $2^{4}$ | 5 | -1 | 1
1 | 5 | $2^{5}$ |  |  |
1 | 6 | $2^{6}$ | 21 | 0 | 1
1 | 7 | $2^{7}$ |  |  |
1 | 8 | $2^{8}$ | 85 | 1 | 1
1 | 9 | $2^{9}$ |  |  |
1 | 10 | $2^{10}$ | 341 | -1 | 1
1 | 11 | $2^{11}$ |  |  |
1 | 12 | $2^{12}$ | 1365 | 0 | 1
Table 2: Examples of first generation odds $x_{1}=2^{m}+\sum_{j=0}^{(m-1)/2}4^{j}$ for odd $m$ generated by the recurrence relation $x_{1}=\left(2^{m}x_{0}-1\right)/3$ of ascending operation against $x_{0}=5$ $x_{0}$ | $m$ | $2^{m}x_{0}$ | $x_{1}$ | $x_{1}\;(mod\;3)$ | $2^{m}x_{0}\;(mod\;3)$
---|---|---|---|---|---
5 | 1 | $5\times 2$ | 3 | 0 | 1
5 | 2 | $5\times 2^{2}$ |  |  |
5 | 3 | $5\times 2^{3}$ | 13 | 1 | 1
5 | 4 | $5\times 2^{4}$ |  |  |
5 | 5 | $5\times 2^{5}$ | 53 | -1 | 1
5 | 6 | $5\times 2^{6}$ |  |  |
5 | 7 | $5\times 2^{7}$ | 213 | 0 | 1
5 | 8 | $5\times 2^{8}$ |  |  |
5 | 9 | $5\times 2^{9}$ | 853 | 1 | 1
5 | 10 | $5\times 2^{10}$ |  |  |
5 | 11 | $5\times 2^{11}$ | 3413 | -1 | 1
5 | 12 | $5\times 2^{12}$ |  |  |

If we assume that ascending operations against two odds $x_{k-1}$ and
$x_{k-1}+a$ with even $a$ generate the same odd $x_{k}$, we can let the
recurrence relations as $x_{k}=\left(2^{n}x_{k-1}-1\right)/3$ and
$x_{k}=\left(2^{m}\left(x_{k-1}+a\right)-1\right)/3$ with $n>m$. The resulting
formula $\left(2^{n-m}-1\right)x_{k-1}=a$ is not correct, since left side is
an odd. This indicates that no two odds $x_{k}$ are the same, if the odds in
the previous generation are different. This proves Lemma 2.

###### Lemma 2

Let $x_{k}$ be the odds generated by
$x_{k}=\left(2^{m_{k-1}}x_{k-1}-1\right)/3$ operation against odds $x_{k-1}$
not multiple of 3, then no two odds $x_{k}$ in the $k$-th generateion are the
same, if the odds $x_{k-1}$ in the previous generation are different.

Every odd not multiple of 3 is defined by $x_{k-1}=6n+1$ and $x_{k-1}=6n+5$,
where $n$ is nonnegative integer. In the recurrence relation
$x_{k}=\left(2^{m_{k-1}}x_{k-1}-1\right)/3$ of ascending operation, if
$x_{k-1}=6n+1$, $m_{k-1}$ is even by Theorem 1. If we let $m_{k-1}=2m$,
$x_{k}=2^{2m+1}n+\sum_{j=0}^{m-1}4^{j}$ , where $m$ is positive integer. Since
$m_{k-1}$ is odd for $x_{k-1}=6n+5$, if we let $m_{k-1}=2m-1$,
$x_{k}=2^{2m-1}(2n+1)+\sum_{j=0}^{m-1}4^{j}$ . Each formula for the first
generation odds generated from an odd includes the term
$\sum_{j=0}^{m-1}4^{j}$.

The $x_{k-1}$ concerns every odd excluding multiple of 3 ready for ascending
operation $x_{k}=\left(2^{m_{k-1}}x_{k-1}-1\right)/3$, and the $x_{k}$
concerns every odd ready for descending operation
$x_{k-1}=\left(3x_{k}+1\right)/2^{m_{k-1}}$. Thus, descending operation
against any odds can generate the odds not multiple of 3, and vice versa.
Descending operations against the odds 1,5,21,
$\cdots\left(=\sum_{j=0}^{m}4^{j}\right)$ reach the origin $x_{0}=1$, and
otherwise the odds greater than or equal to 5. This proves Theorem 3.

###### Theorem 3

Let $x_{k}=2^{2m+1}n+\sum_{j=0}^{m-1}4^{j}$ be the odds generated by
$x_{k}=\left(2^{2m}x_{k-1}-1\right)/3$ operation against odds $x_{k-1}=6n+1$
and $x_{k}=2^{2m-1}(2n+1)+\sum_{j=0}^{m-1}4^{j}$ be the odds generated by
$x_{k}=\left(2^{2m-1}x_{k-1}-1\right)/3$ operation against odds
$x_{k-1}=6n+5$, then $x_{k-1}$ concern every odd excluding multiple of 3 and
$x_{k}$ every odd, where $n$ is nonnegative integer.

###  2.2 Ascending operation against 1

If we let $x_{k-1}=x_{k}$ in the recurrence relation
$x_{k}=\left(2^{m}x_{k-1}-1\right)/3$, $(2^{m}-3)x_{k-1}=1$. Solution of the
formula is $x_{k-1}=1$ and $m=2$. This is the trivial cycle. Steiner proved
that there is no 1-cycle other than the trivial (1; 2).[2] Since the trivial
cycle is unique, no pairs of $x_{k-1}$ and $x_{k}$ are the same except
$x_{k-1}=x_{k}=1.$

An ascending sequence of $x_{0}=x_{1}=x_{2}=\cdots=1$ is generated by the
recurrence relation $x_{k}=\left(2^{2}x_{k-1}-1\right)/3$ of ascending
operation against $x_{0}=1$. Every $x_{k-1}=1$ in each generation generates
the odds $x_{k}=\sum_{j=0}^{(m-2)/2}4^{j}$ in the next generation. Every odd
$x_{k}$ in the sequence generated from $x_{k-1}=1$ goes to the origin
$x_{0}=1$ by descending operations. The odd $x_{k-1}=1$ for $k\geq 2$ can be
thus considered exceptionally.

###  2.3 Ascending operation against odds

Since $2^{3}\equiv-1\left(mod\;3^{2}\right)$ and $2^{6}\equiv
1\left(mod\;3^{2}\right)$, $2^{6n}\equiv 1\left(mod\;3^{2}\right)$, where $n$
is positive integer. Let $x_{0}$ be a positive odd not multiple of 3, then
$2^{6n+m_{0}}x_{0}\equiv 2^{m_{0}}x_{0}\left(mod\;2\times 3^{2}\right)$ by the
properties of modular arithmetic regarding compatibility with scaling, where
$m_{0}$ is nonnegative integer less than 6.

Let $x_{1}=\left(2^{m_{0}}x_{0}-1\right)/3$ and
$y_{1}=\left(2^{m}x_{0}-1\right)/3$ be odds with $m\equiv
m_{0}\left(mod\;6\right)$, then $y_{1}\equiv x_{1}\left(mod\;6\right)$. This
means that the first generation odds in ascending operation are congruent
modulo 6, if numbers of doubling operations are congruent modulo 6, as
illustrated in Tables 1 and 2. This proves Theorem 4.

###### Theorem 4

Let $x_{0}$ be positive odds not multiple of 3, and let
$x_{1}=\left(2^{m_{0}}x_{0}-1\right)/3$ and
$y_{1}=\left(2^{m}x_{0}-1\right)/3$ be odds with $m\equiv
m_{0}\left(mod\;6\right)$, then $y_{1}\equiv x_{1}\left(mod\;6\right)$, where
$m_{0}$ is nonnegative integer less than 6.

An ascending sequence of odds from $x_{0}$ to $x_{n}$ generated by the
recurrence relation $x_{k}=\left(2^{m}x_{k-1}-1\right)/3$ of ascending
operation can be expressed as $x_{0}\Rightarrow
x_{1}\Rightarrow\cdots\Rightarrow x_{k}\Rightarrow\cdots\Rightarrow x_{n}$. If
$3\mid x_{n}$, the $x_{n}$ is a terminal number of ascending sequence because
no further ascending operation is possible. The odds $x_{0}$ to $x_{n-1}$ are
not multiples of 3.

Let an odd $x_{1}=\left(2^{m_{0}}x_{0}-1\right)/3$ such that $x_{1}\equiv
1\left(mod\;3\right)$, then
$\left(2^{m_{0}+2}x_{0}-1\right)/3\equiv-1\left(mod\;3\right)$ and
$\left(2^{m_{0}+4}x_{0}-1\right)/3\equiv 0\left(mod\;3\right)$. Let
$y_{1}=\left(2^{m}x_{0}-1\right)/3$, then $y_{1}\equiv 1\left(mod\;3\right)$
for $m\equiv m_{0}\left(mod\;6\right)$, $y_{1}\equiv-1\left(mod\;3\right)$ for
$m\equiv m_{0}+2\left(mod\;6\right)$ and $y_{1}\equiv 0\left(mod\;3\right)$
for $m\equiv m_{0}+4\left(mod\;6\right)$ by Theorem 4. The odds multiple of 3
are generated by every 6 doubling operations of ascending operation. Since the
first generation odds are generated by every two doubling operations, ratio of
the odds multiple of 3 against the odds in the first generation is 1/3.

Infinite number of odds multiple of 3 are generated by one step of ascending
operation against any positive odds not multiple of 3. And reversely, odds not
multiple of 3 are generated by one step of descending operation against any
positive odds multiple of 3. Every positive odd not multiple of 3 is thus
generated by the descending operation against every positive odd multiple of
3, and _vice versa_. Therefore, every descending sequence can start from
terminal numbers.

###  2.4 Odds in the branches

Number of odds $x_{1}$ in the branch of first generation originated from an
odd $x_{0}$ is infinite. The odds $x_{k}$ in the branches of $k$-th generation
are infinitely generated by ascending operations against each odd $x_{k-1}$
excluding multiples of 3 in the branches of previous generation. The sequence
of branches can be thus generated infinitely by consecutive ascending
operations.

If we let $M$ be number of odds excluding multiples of 3 in each branch of
every generation, number of odds excluding multiples of 3 in the branches of
$k$-th generation is $M^{k}$, because number of odds ready for ascending
operation in the branches of previous generation is $M^{k-1}$. Total number of
odds excluding multiples of 3 up to branches of $n$-th generation from an odd
is $1+M+M^{2}+\cdots+M^{n}$. If we let $1\ll M$, since $M^{n-1}\ll M^{n}$,
$1+M+M^{2}+\cdots+M^{n}\approx M^{n}$. If the odds in in every branch are not
limited, $M$ and $n$ go to infinite.

##  3 Generalization for patterns of ascending operation

###  3.1 Modular arithmetic properties of doubling operation

Let $p$ be an odd prime number, then $\left(p\pm
1\right)^{p^{n}}=\sum_{k=0}^{p^{n}}\left(\begin{array}[]{c}p^{n}\\\
k\end{array}\right)\left(\pm 1\right)^{k}p^{p^{n}-k}$, where $n$ is
nonnegative integer. Since p-adic valuation for the binomial coefficient is
$\nu_{p}\left(\left(\begin{array}[]{c}p^{n}\\\
k\end{array}\right)\right)=n-\nu_{p}(k)$,
$\nu_{p}\left(\left(\begin{array}[]{c}p^{n}\\\
k\end{array}\right)p^{p^{n}-k}\right)=n-\nu_{p}(k)+p^{n}-k$. Since
$k+\nu_{p}(k)<p^{n}$ if $0\leq k\leq p^{n}-1$ and $n-\nu_{p}(k)+p^{n}-k=0$ if
$k=p^{n}$, $p^{n+1}\mid\left(\begin{array}[]{c}p^{n}\\\
k\end{array}\right)p^{p^{n}-k}$ for $0\leq k\leq p^{n}-1$. Thus, $\left(p\pm
1\right)^{p^{n}}\equiv\pm 1\left(mod\;p^{n+1}\right)$. This proves Theorem 5.
The prime number 2 satisfies also the formula $\left(p+1\right)^{p^{n}}\equiv
1\left(mod\;p^{n+1}\right)$, thus $3^{2^{n}}\equiv
1\left(mod\;2^{n+1}\right)$.

###### Theorem 5

Let $p$ be an odd prime number, then $\left(p\pm 1\right)^{p^{n}}\equiv\pm
1\left(mod\;p^{n+1}\right)$, where $n$ is nonnegative integer.

If we let $p=3$, $4^{3^{n}}=2^{2\times 3^{n}}\equiv
1\left(mod\;3^{n+1}\right)$ and $2^{3^{n}}\equiv-1\left(mod\;3^{n+1}\right)$
by Theorem 5. Since the odds $2^{3^{n}}-1$ and $2^{3^{n}}+1$ in $2^{2\times
3^{n}}-1=\left(2^{3^{n}}-1\right)\left(2^{3^{n}}+1\right)$ are neighboring,
$3^{n+1}\mid 2^{3^{n}}+1$ and $3\nmid 2^{3^{n}}-1$. Mersenne numbers show
$3^{n+1}\mid 2^{2\times 3^{n}}-1$ and $3\nmid 2^{3^{n}}-1$, and Wagstaff
numbers show $3^{n}\mid\left(2^{3^{n}}+1\right)/3$. This proves Theorems 6 and
7.

###### Theorem 6

Mersenne numbers show $3^{n+1}\mid 2^{2\times 3^{n}}-1$ and $3\nmid
2^{3^{n}}-1$, where $n$ is nonnegative integer.

###### Theorem 7

Wagstaff numbers show $3^{n}\mid\left(2^{3^{n}}+1\right)/3$, where $n$ is
nonnegative integer.

Since $3^{n+1}\mid 2^{3^{n}}+1$ and $3\nmid 2^{3^{n}}-1$ for $2^{2\times
3^{n}}-1=\left(2^{3^{n}}-1\right)\left(2^{3^{n}}+1\right)$,
$3^{n}\mid\sum_{j=0}^{3^{n}-1}4^{j}$, $3\nmid\sum_{j=0}^{3^{n}-1}2^{j}$,
$3^{n}\mid\sum_{j=0}^{3^{n}-1}\left(-2\right)^{j}$ and
$\sum_{j=0}^{3^{n}-1}4^{j}=\sum_{j=0}^{3^{n}-1}2^{j}\times\sum_{j=0}^{3^{n}-1}\left(-2\right)^{j}$.
Generally, since $x^{2m}-1=\left(x^{m}-1\right)\left(x^{m}+1\right)$ for
positive number $x$ and odd $m$,
$\sum_{j=0}^{m-1}x^{2j}=\sum_{j=0}^{m-1}x^{j}\times\sum_{j=0}^{m-1}\left(-x\right)^{j}$.

Since
$x^{2^{a}m}-1=\left(x^{m}-1\right)\prod_{k=0}^{a-1}\left(x^{2^{k}m}+1\right)$
and $x^{2^{a}}-1=\left(x-1\right)\prod_{k=0}^{a-1}\left(x^{2^{k}}+1\right)$,
$\sum_{j=0}^{2^{a}-1}x^{j}=\prod_{k=0}^{a-1}\left(x^{2^{k}}+1\right)$ and
$\sum_{j=0}^{m-1}x^{2^{a}j}=\sum_{j=0}^{m-1}x^{j}\times\prod_{k=0}^{a-1}\sum_{j=0}^{m-1}\left(-x^{2^{k}}\right)^{j}$.
If we let x be even, $x^{2^{k}}+1$ with $k\geq 1$ are generalized Fermat
numbers, This proves Theorem 8.

###### Theorem 8

$\sum_{j=0}^{2^{a}-1}x^{j}=\prod_{k=0}^{a-1}\left(x^{2^{k}}+1\right)$ and
$\sum_{j=0}^{m-1}x^{2^{a}j}=\sum_{j=0}^{m-1}x^{j}\times\prod_{k=0}^{a-1}\sum_{j=0}^{m-1}\left(-x^{2^{k}}\right)^{j}$
for positive number $x$ and odd $m$.

Theorem 6 states $2^{2\times 3^{n}}\equiv 1\left(mod\;3^{n+1}\right)$, where
$n$ is nonnegative integer. Then, an positive odd $x_{0}$ not multiple of 3
shows $2^{m_{0}+2\times 3^{n}}x_{0}\equiv 2^{m_{0}}x_{0}\left(mod\;2\times
3^{n+1}\right)$ by the properties of modular arithmetic regarding
compatibility with scaling, where $m_{0}$ is nonnegative integer less than
$2\times 3^{n}$. If we let $x_{1}=\left(2^{m_{0}}x_{0}-1\right)/3$ and
$y_{1}=\left(2^{m}x_{0}-1\right)/3$ be odds with relation of $m\equiv
m_{0}\left(mod\;2\times 3^{n}\right)$, $y_{1}\equiv x_{1}\left(mod\;2\times
3^{n}\right)$, where $x_{0}$ are odds not multiple of 3. Thus, the first
generation odds generated by ascending operations are congruent modulo
$2\times 3^{n}$, if the numbers of doubling operations are congruent modulo
$2\times 3^{n}$. This proves Theorem 9. Theorem 9 is a generalized Theorem 4.

###### Theorem 9

Let $x_{0}$ be a positive odd not multiple of 3 and let
$y_{1}=\left(2^{m}x_{0}-1\right)/3$ and
$x_{1}=\left(2^{m_{0}}x_{0}-1\right)/3$ with $m\equiv m_{0}\left(mod\;2\times
3^{n}\right)$ be odds, then $y_{1}\equiv x_{1}\left(mod\;2\times
3^{n}\right)$, where $m_{0}$ is nonnegative integer less than $2\times 3^{n}$
and $n$ is positive integer.

###  3.2 Pattern of ascending operations

Let $x_{0}-\left(m_{0}\right)-x_{1}-\left(m_{1}\right)-x_{2}-(m_{2})-\cdots-
x_{k-1}-\left(m_{k-1}\right)-x_{k}-\cdots-\left(m_{n-1}\right)-x_{n}$ be a
sequence of odds generated by the recurrence relation
$x_{k}=\left(2^{m_{k-1}}x_{k-1}-1\right)/3$ of ascending operation. Each
number in the parenthesis is number of doubling operations. The ascending
sequence can be expressed as $x_{0}\Rightarrow
x_{1}\Rightarrow\cdots\Rightarrow x_{k-1}\Rightarrow
x_{k}\Rightarrow\cdots\Rightarrow x_{n}$. Pattern of a sequence is identified
by the numbers of doubling operations in the sequence ignoring the sizes of
odds.

Let $b_{k}=\sum_{h=0}^{k-1}m_{h}$ be the total number of doubling operations
in a sequence from $x_{0}$ to $x_{k}$. If we let $y_{0}=x_{0}+2\times 3^{n}j$,
odds in the ascending sequence $y_{1}=x_{1}+2^{m_{0}+1}3^{n-1}j$,
$y_{2}=x_{2}+2^{m_{0}+m_{1}+1}3^{n-2}j$, $y_{k}=x_{k}+2^{b_{k}+1}3^{n-k}j$ and
$y_{n}=x_{n}+2^{b_{n}+1}j$ are generated by the recurrence relation
$y_{k}=\left(2^{m_{k-1}}y_{k-1}-1\right)/3$ of ascending operation, where $j$
is nonnegative integer. The ascending sequences $y_{0}\Rightarrow
y_{1}\Rightarrow y_{2}\Rightarrow\cdots\Rightarrow
y_{k}\Rightarrow\cdots\Rightarrow y_{n}$ with different $j$ are generated by
the same numbers of doubling operations as the sequence from $x_{0}$ to
$x_{n}$ in the same pattern. The sequences in the same pattern show
$y_{0}\equiv x_{0}\left(mod\;2\times 3^{n}\right)$, $y_{1}\equiv
x_{1}\left(mod\;2^{m_{0}+1}3^{n-1}\right)$, $y_{k}\equiv
x_{k}\left(mod\;2^{b_{k+1}}3^{n-k}\right)$, and $y_{n}\equiv
x_{n}\left(mod\;2^{b_{n}+1}\right)$. Number of sequences in the same pattern
is infinite. This proves Lemma 10.

Each descending sequence started from each odd is unique. Thus
$y_{0}=x_{0}+2\times 3^{n}j$ is the solution for the recurrence relation
$x_{k-1}=\left(3x_{k}+1\right)/2^{m_{k-1}}$ of descending operation against
$y_{n}=x_{n}+2^{b_{n}+1}j$. The descending sequences from $y_{n}$ to $y_{0}$
with different $j$ belong to the same pattern.

###### Lemma 10

Let $x_{0}\Rightarrow x_{1}\Rightarrow x_{2}\cdots\Rightarrow
x_{k}\Rightarrow\cdots\Rightarrow x_{n}$ be a sequence generated by the
recurrence relation $x_{k}=\left(2^{m_{k-1}}x_{k-1}-1\right)/3$ of ascending
operation with $b_{k}=\sum_{h=0}^{k-1}m_{h}$, if and only if $y_{0}\equiv
x_{0}\left(mod\;2\times 3^{n}\right)$, then the sequences of odds
$y_{0}\Rightarrow y_{1}\Rightarrow y_{2}\Rightarrow\cdots\Rightarrow
y_{k}\Rightarrow\cdots\Rightarrow y_{n}$ with $y_{k}\equiv
x_{k}\left(mod\;2^{b_{k+1}}3^{n-k}\right)$ are infinitely generated by the
recurrence relation $y_{k}=\left(2^{m_{k-1}}y_{k-1}-1\right)/3$ with the same
numbers of doubling operations $m_{k}$.

###  3.3 Primitive sequence

Theorem 9 states that let $x_{0}$ be positive odds not multiple of 3, then the
first generation odds $y_{1}=\left(2^{m}x_{0}-1\right)/3$ and
$x_{1}=\left(2^{m_{0}}x_{0}-1\right)/3$ with $m\equiv m_{0}\left(mod\;2\times
3^{n}\right)$ show $y_{1}\equiv x_{1}\left(mod\;2\times 3^{n}\right)$, where
$m_{0}$ is nonnegative integer less than $2\times 3^{n}$ and $n$ is positive
integer. Then, $n$ terms of ascending sequences started from each $y_{1}$
belong to the same pattern by Lemma 10

Let a group such that $G_{n}=\left\\{x_{1}\mid 1\leq x_{1}<2\times
3^{n},\left(2^{m}x_{0}-1\right)/3\equiv x_{1}\left(mod\;2\times
3^{n}\right),2^{m}x_{0}\equiv 1\left(mod\;3\right),m\equiv
m_{0}\left(mod\;2\times 3^{n}\right),0\leq m_{0}<2\times
3^{n},m_{0}\in\mathbb{N},n\in\mathbb{N}\right\\}$. Order of the group is
$|G_{n}|=3^{n}$, since $2^{m}x_{0}\equiv 1\left(mod\;3\right)$ by every two
doubling operations. Since
$\left(2^{m}x_{0}-1\right)/3\equiv\left(2^{m_{0}}x_{0}-1\right)/3\left(mod\;2\times
3^{n}\right)$ by Theorem 9, $G_{n}=\left\\{x_{1}\mid 1\leq x_{1}<2\times
3^{n},\left(2^{m_{0}}x_{0}-1\right)/3\equiv x_{1}\left(mod\;2\times
3^{n}\right),2^{m_{0}}x_{0}\equiv 1\left(mod\;3\right),0\leq m_{0}<2\times
3^{n},m_{0}\in\mathbb{N},n\in\mathbb{N}\right\\}$. Since $G_{n}$ includes
every positive odd less than $2\times 3^{n}$, $G_{n}=\left\\{x\mid
x=2m-1,1\leq m\leq 3^{n},m\in\mathbb{N},n\in\mathbb{N}\right\\}$.

For example, $G_{2}=\left\\{x_{1}\mid 1\leq x_{1}<2\times
3^{n},\left(2^{m+2\times 3^{2}j}-1\right)/3\equiv x_{1}\;\left(mod\;2\times
3^{2}\right),2^{m+2\times 3^{2}j}\equiv 0\;\left(mod\;3\right),0\leq m<2\times
3^{2},m_{0}\in\mathbb{N},n\in\mathbb{N}\right\\}$. Since $\left(2^{m+2\times
3^{2}j}-1\right)/3\equiv\;\left(2^{m}-1\right)/3\;\left(mod\;2\times
3^{2}\right)$ by Theorem 9, $G_{2}=\left\\{x_{1}\mid 1\leq x_{1}<2\times
3^{n},\left(2^{m}-1\right)/3\equiv x_{1}\left(mod\;2\times
3^{n}\right),2^{m}\equiv 1\left(mod\;3\right),0\leq m<2\times
3^{n},m\in\mathbb{N}\right\\}=\left\\{1,5,3,13,17,15,7,11,9\right\\}$. The
elements of the group are remainders of $y_{1}\equiv x_{1}\left(mod\;2\times
3^{n}\right)$. Thus, $G_{2}=\left\\{x\mid x=2m-1,1\leq m\leq
3^{n},m\in\mathbb{N}\right\\}$.

The $n$ terms of ascending sequences started from each $y_{1}$ with relation
of $y_{1}\equiv x_{1}\left(mod\;2\times 3^{n}\right)$ show the same pattern as
the sequence started from $x_{1}$. If $x_{1}\in G_{n}$, the ascending sequence
started from $x_{1}$ is named as a primitive sequence, which is generated by
the smallest odds among the sequences in the same pattern. Thus, each set of
ascending sequences in the same pattern includes each primitive sequence that
starts from an odd between 1 and $2\times 3^{n}$. The sequences in the same
patterns are infinitely regenerated throughout the consecutive generations
like a fractal.

##  4 Specific consecutive descending operations

###  4.1 Descending operations with one halving operation

An odd $x_{k-1}$ generated by the recurrence relation
$x_{k-1}=\left(3x_{k}+1\right)/2^{m_{k-1}}$ of descending operation is smaller
than the odd $x_{k}$ if $m_{k-1}\geq 2$. If average numbers of halving
operations in a sequence is $\overline{m_{k-1}}\approx\log_{2}3\approx 1.59$,
the sequence will keep the similar values. If $m_{k-1}=1$, $x_{k-1}>x_{k}$.

Let $x_{n}-[1]-x_{n-1}-[1]-x_{n-2}-[1]-\cdots x_{k}-\cdots-[1]-x_{0}$ be a
sequence generated by the recurrence relation
$x_{k-1}=\left(3x_{k}+1\right)/2$ of descending operation with one halving
operation. Numbers of halving operations are listed in the brackets. Total
number of halving operations is $b_{n}=n$. Sizes of the odds in the descending
sequence increase continuously.

Odd 3 is generated by the ascending operation $3=\left(2\times 5-1\right)/3$
against 5. Then, ascending operations with one doubling operation against the
odds $x_{0}=-1+2\times 3j$ generate the odds $x_{1}=-1+4j$ by Lemma 10, where
j is posiive integer. Two terms of sequences with $m_{0}=m_{1}=1$ are
$x_{2}=-1+2^{3}j$, $x_{1}=-1+2^{2}3j$ and $x_{0}=-1+2\times 3^{2}j$. Three
terms of sequences with $m_{0}=m_{1}=m_{2}=1$ are $x_{3}=-1+2^{4}j$,
$x_{2}=-1+2^{3}3j$, $x_{1}=-1+2^{2}3^{2}j$ and $x_{0}=-1+2\times 3^{3}j$.
Thus, the odds $x_{k}=-1+2^{k+1}3^{n-k}j$ belong to the $n$ terms of
descending sequences from $x_{n}=-1+2^{n+1}j$ to $x_{0}=-1+2\times 3^{n}j$.
The descending sequences of different $j$ show the same pattern.

Since $x_{0}/x_{n}\approx(3/2)^{n}$, sizes of the odds increase exponentially
to the number of descending operations. The ratio $x_{0}/x_{n}$ becomes more
close to $(3/2)^{n}$ by larger $x_{n}$.

Let $x_{n+1}-[1]-x_{n}-[1]-x_{n-1}-[1]-\cdots-x_{2}-[1]-x_{1}-[m_{0}]-1$ be a
descending sequence, where $x_{1}$ is a first generation odd originated from
$x_{0}=1$. The odds $x_{n+1}$ to $x_{1}$ increase geometrically with common
ratio of $x_{k-1}/x_{k}\approx 3/2$.

Theorem 7 states $3^{n+1}\mid 2^{3^{n}}+1$, where $n$ is nonnegative integer.
Since $3^{n+1}\mid 2^{3^{n}(2h-1)}+1$,
$\left(2^{3^{n}(2h-1)+1}-1\right)/3\equiv-1\left(mod\;2\times 3^{n}\right)$,
where $h$ is positive integer. If we let
$x_{1}=\left(2^{3^{n}(2h-1)+1}-1\right)/3$, since
$x_{1}=\sum_{j=0}^{m_{0}-1}4^{j}$ with
$m_{0}=\left(3^{n}\left(2h-1\right)+1\right)/2$, the $x_{1}$ belong to the
first generation odds generated from the origin $x_{0}=1$ as shown in Theorem
3. Since $x_{1}\equiv-1\left(mod\;2\times 3^{n}\right)$, $n$ terms of
ascending sequences $x_{1}-(1)-x_{2}-(1)-\cdots-x_{n}-(1)-x_{n+1}$ in the same
pattern are generated by Lemma 10. If we let $x_{1}=-1+2\times 3^{n}j$, the
sequence of odds from $x_{1}$ to $x_{n+1}=-1+2^{n+1}j$ with
$x_{k}=-1+2^{k}3^{n-k+1}j$ are generated by the recurrence relation
$x_{k}=\left(2x_{k-1}-1\right)/3$, where $j$ is positive integer.

Number of halving operations to reach the origin $x_{0}=1$ is
$m_{0}=3^{n}\left(2h-1\right)+1$. Infinitely large $x_{1}$ can be generated by
consecutive descending operations with one halving operation. One step of
descending operation against the $x_{1}$ reaches the origin $x_{0}=1$
irrespective of size of $x_{1}$. If we let $h=1$, $m_{0}=3^{n}+1$, such as 4,
10, 28, $\cdots$.

Examples of descending sequences of odds with $h=1$ are $3-[1]-5-[4]-1$ for
$n=1$, Then, $3\equiv-1\;\left(mod\;2^{2}\right)$ and
$5\equiv-1\;\left(mod\;2\times 3\right)$. If $n=2$,
$151-[1]-227-[1]-341-[10]-1$, Then, $151\equiv-1\;\left(mod\;2^{3}\right)$,
$227\equiv-1\;\left(mod\;2^{2}3\right)$ and $341\equiv-1\;\left(mod\;2\times
3^{2}\right)$. If $n=3$,
$26512143-[1]-39768215-[1]-59652323-[1]-89478485-[28]-1$. Then,
$26512143\equiv-1\;\left(mod\;2^{4}\right)$,
$39768215\equiv-1\;\left(mod\;2^{3}3\right)$,
$59652323\equiv-1\;\left(mod\;2^{2}3^{2}\right)$ and
$89478485\equiv-1\;\left(mod\;2\times 3^{3}\right)$.

###  4.2 Descending operations with two halving operations

Let $x_{n}-[2]-x_{n-1}-[2]-x_{n-2}-[2]-\cdots-x_{1}-[2]-x_{0}$ be a sequence
generated by the recurrence relation $x_{k-1}=\left(3x_{k}+1\right)/2^{2}$ of
descending operation with two halving operations. Total number of halving
operations is $b_{n}=2n$. Sizes of the odds in the descending sequence
decrease continuously.

Odd 1 is generated by the ascending operation $1=\left(2^{2}\times
1-1\right)/3$ against 1. Then, ascending operations against the odds
$x_{0}=1+2\times 3j$ generate the odds $x_{1}=1+2^{3}j$ by Lemma 10, where j
is nonnegative integer. Two terms of sequences with $m_{0}=m_{1}=2$ are
$x_{2}=1+2^{5}j$, $x_{1}=1+2^{3}3j$ and $x_{0}=1+2\times 3^{2}j$. Three terms
of sequences with $m_{0}=m_{1}=m_{2}=2$ are $x_{3}=1+2^{7}j$,
$x_{2}=1+2^{5}3j$, $x_{1}=1+2^{3}3^{2}j$ and $x_{0}=1+2\times 3^{3}j$. The
odds $x_{k}=1+2^{2k+1}3^{n-k}j$ belong to the $n$ terms of descending
sequences from $x_{n}=1+2^{2n+1}j$ to $x_{0}=1+2\times 3^{n}j$. The descending
sequences of different $j$ show the same pattern.

Since $x_{0}/x_{n}\approx\left(3/4\right)^{n}$, sizes of the odds decrease
exponentially to the number of descending operations with two halving
operations. If we let $x_{n}=1$, $1-[2]-1-[2]-\cdots-1$, which is the $n$
terms of descending sequence concerning the trivial cycle.

Let $x_{n+1}-[2]-x_{n}-[2]-x_{n-1}-[2]-\cdots-x_{2}-[2]-x_{1}-[m_{0}]-1$ be a
descending sequence, where $x_{1}$ is a first generation odd originated from
$x_{0}=1$. The odds $x_{n+1}$ to $x_{1}$ decrease geometrically with common
ratio of $x_{k-1}/x_{k}\approx 3/4$.

Theorem 6 states $3^{n+1}\mid 2^{2\times 3^{n}}-1$, where $n$ is nonnegative
integer. Since $2^{2\times 3^{n}h}\equiv 1\left(mod\;3^{n+1}\right)$ ),
$\left(2^{2\left(3^{n}h+1\right)}-1\right)/3\equiv 1\left(mod\;2\times
3^{n}\right)$, where $h$ is positive integer. If we let
$x_{1}=\left(2^{2\left(3^{n}h+1\right)}-1\right)/3$, since
$x_{1}=\sum_{j=0}^{3^{n}h}4^{j}$, $x_{1}$ belong to the first generation odds
generated from the origin $x_{0}=1$ as shown in Theorem 3. Since $x_{1}\equiv
1\left(mod\;2\times 3^{n}\right)$, $n$ terms of sequences
$x_{1}-(2)-x_{2}-(2)-\cdots-(2)-x_{n+1}$ in the same pattern are generated by
Lemma 10. If we let $x_{1}=1+2\times 3^{n}j$, sequences of odds from $x_{1}$
to $x_{n+1}=1+2^{2n+1}j$ with $x_{k}=1+2^{2k-1}3^{n-k+1}j$ are generated by
the recurrence relation $x_{k}=\left(2^{2}x_{k-1}-1\right)/3$, where $j$ is
positive integer. Number of halving operations against the odd $x_{1}$ to
reach the origin $x_{0}=1$ is $m_{0}=2\left(3^{n}h+1\right)$. If we let $h=1$,
$m_{0}=2\left(3^{n}+1\right)$, such as 2, 8, 20,56, $\cdots$.

Examples of descending sequences for $h=1$ are: $1-[2]-1$ for $n=0$.
$113-[2]-85-[8]-1$ if $n=1$. Then, $113\equiv 1\;\left(mod\;2^{3}\right)$ and
$85\equiv 1\;\left(mod\;2\times 3\right)$. If $n=2$,
$621377-[2]-466033-[2]-349525-[20]-1$. Then, $621377\equiv
1\;\left(mod\;2^{5}\right)$, $466033\equiv 1\;\left(mod\;2^{3}3\right)$ and
$349525\equiv 1\;\left(mod\;2\times 3^{2}\right)$.

##  5 Sequence of odds repeating cyclically

###  5.1 Sequence including cyclic odds

Let $\cdots-x_{a}-\left[m_{a-1}\right]-x_{a-1}-[m_{a-2}]-x_{a-2}-\cdots-
x_{b+1}-[m_{b}]-x_{b}-\left[m_{b-1}\right]-\cdots$ be a descending sequence of
odds that are not multiples of 3. Formula for the odds concerning $a-b$ times
of descending operations is
$x_{b}=\left(3\cdots\left(3\left(3\left(3x_{a}+1\right)/2^{m_{a-1}}+1\right)/2^{m_{a-2}}+1\right)/2^{m_{a-3}}\cdots+1\right)/2^{m_{b}}$.

Lemma 2 states no two odds $x_{k}$ in a generation are the same, if the odds
$x_{k-1}$ in the previous generation are different. If we let $x_{a}=x_{b}$ in
a sequence, since the descending sequence started from an odd is unique,
$x_{a-1}=x_{b-1}$, $x_{a-2}=x_{b-2}$, $x_{a-3}=x_{b-3}$, $\cdots$ and
$m_{a}=m_{b}$, $m_{a-1}=m_{b-1}$, $m_{a-2}=m_{b-2}$, $\cdots$. The sequence is
consisted with the cyclic odds from $x_{a}$ to $x_{b+1}$.

The cyclic descending operations continue sequentially until the descending
sequence reaches an origin of $x_{0}$. All of the odds $x_{a}$ to $x_{b+1}$ in
the sequence have the chance to be the origin of the sequence. If the origin
of the descending sequence is unique, the odds in the cyclic sequence will
show $x_{a}=x_{a-1}=x_{a-2}=\cdots=x_{b+1}=\cdots=x_{0}$. Since no pairs of
$x_{k-1}$ and $x_{k}$ are the same except $x_{k-1}=x_{k}=1$, it is expected
that the odds in the cyclic sequence are equally 1.

###  5.2 Cycle with one odd

The cyclic sequence with one odd is $\cdots-
x_{a}-\left[m_{a-1}\right]-x_{a-1}\left(=x_{a}\right)-\left[m_{a-1}\right]-\cdots-
x_{0}\left(=x_{a}\right)$. Recurrence relation for one descending operation
with $x_{a}=x_{a-1}$ repeating in a cycle is
$x_{a}=\left(3x_{a}+1\right)/2^{m_{a-1}}$. Solution is $x_{a}=1$ and
$m_{a-1}=2$, and the repeating sequence is named as trivial cycle,
$1-[2]-1$.[2]

###  5.3 Cycle with two odds

The cyclic sequence with two odds is
$\cdots-[m_{a}]-x_{a}-\left[m_{a-1}\right]-x_{a-1}-\left[m_{a}\right]-x_{a-2}(=x_{a})-\left[m_{a-1}\right]-x_{a-3}\left(=x_{a-1}\right)-\left[m_{a}\right]-\cdots$.
Formula for the odds concerning two times of descending operations repeating
in a cycle for $x_{a}=x_{a-2}$ is
$\left(2^{m_{a}+m_{a-1}}-3^{2}\right)x_{a}=2^{m_{a-1}}+3$, and
$\left(2^{m_{a}+m_{a-1}}-3^{2}\right)x_{a-1}=2^{m_{a}}+3$ for
$x_{a-1}=x_{a-3}$. Since $2^{m_{a}+m_{a-1}}>3^{2}$, $m_{a}+m_{a-1}\geq 4$.

Since $x_{a-1}=\left(3x_{a}+1\right)/2^{m_{a-1}}$ and
$x_{a}=\left(3x_{a-1}+1\right)/2^{m_{a}}$ are the recurrence relations of the
cycle, $\left(3+1/x_{a}\right)\left(3+1/x_{a-1}\right)=2^{m_{a}+m_{a-1}}$. The
solution is $x_{a}=x_{a-1}=1$ and $m_{a}=m_{a-1}=2$. Thus, there is no cycle
composed of two odds, but $1-[2]-1-[2]-1$.

###  5.4 Cycle with three odds

The cyclic sequence with three odds is
$\cdots-[m_{a}]-x_{a}-\left[m_{a-1}\right]-x_{a-1}-\left[m_{a-2}\right]-x_{a-2}-\left[m_{a}\right]-x_{a-3}(=x_{a})-\left[m_{a-1}\right]-x_{a-4}\left(=x_{a-1}\right)-\left[m_{a-2}\right]-x_{a-5}\left(=x_{a-2}\right)-\left[m_{a}\right]-\cdots$.
Formula for the odds concerning three times of descending operations repeating
in a cycle for $x_{a}=x_{a-3}$ is
$\left(2^{m_{a}+m_{a-1}+m_{a-2}}-3^{3}\right)x_{a}=2^{m_{a-1}+m_{a-2}}+2^{m_{a-1}}3+3^{2}$.
Since left side of the formula is positive, $m_{a}+m_{a-1}+m_{a-2}\geq 5$.

Recurrence relations for the descending operations of the cycle are
$x_{a-1}=\left(3x_{a}+1\right)/2^{m_{a-1}}$,
$x_{a-2}=\left(3x_{a-1}+1\right)/2^{m_{a-2}}$ and
$x_{a}=\left(3x_{a-2}+1\right)/2^{m_{a}}$. Multiplication of the three
formulae results
$\left(3+1/x_{a}\right)\left(3+1/x_{a-1}\right)\left(3+1/x_{a-2}\right)=2^{m_{a}+m_{a-1}+m_{a-2}}$.
The solution is $x_{a}=x_{a-1}=x_{a-2}=1$ and $m_{a}=m_{a-1}=m_{a-2}=2$. There
is no cycle composed of three odds, but $1-[2]-1-[2]-1-[2]-1$.

###  5.5 Cycle with n odds

The cyclic sequence with $a-b\;\left(=n\right)$ odds is
$\cdots-[m_{b}]-x_{a}\left(=x_{b}\right)-\left[m_{a-1}\right]-x_{a-1}-\left[m_{a-2}\right]-x_{a-2}-\cdots-
x_{b+1}-\left[m_{b}\right]-x_{b}\left(=x_{a}\right)-\left[m_{a-1}\right]-\cdots$.
Formula for the cyclic sequence with $x_{a}=x_{b}$ is
$\left(2^{m_{a-1}+m_{a-2}+\cdots+m_{b}}-3^{a-b}\right)x_{a}=2^{m_{a-1}+m_{a-2}+\cdots+m_{b+1}}+2^{m_{a-1}+m_{a-2}+\cdots+m_{b+2}}3+\cdots+2^{m_{a-1}}3^{a-b-2}+3^{a-b-1}$.

Recurrence relations for the descending operations of the cycle are
$x_{a-1}=\left(3x_{a}+1\right)/2^{m_{a-1}}$,
$x_{a-2}=\left(3x_{a-1}+1\right)/2^{m_{a-2}}$,
$x_{a-3}=\left(3x_{a-2}+1\right)/2^{m_{a-3}}$,$\cdots$ ,
$x_{a}=\left(3x_{b+1}+1\right)/2^{m_{b}}$. Multiplication of the the formulae
results
$\left(3+1/x_{a}\right)\left(3+1/x_{a-1}\right)\cdots\left(3+1/x_{b+1}\right)=2^{m_{a-1}+m_{a-2}+\cdots+m_{b}}$.
The solution is $x_{a}=x_{a-1}=\cdots=x_{b+1}=1$ and
$m_{a-1}=m_{a-2}=\cdots=m_{b}=2$. There is no cycle composed of n odds, but
$1-[2]-1-[2]-\cdots-1$ with $n$ terms..

###  5.6 Cycle with infinite odds

Formula for $x_{a}=1$ concerning $n$ times of operation with $m_{k}=2$ is
$2^{2}-2^{2}\left(3/2^{2}\right)^{n}=1+3/2^{2}+\left(3/2^{2}\right)^{2}+\cdots+\left(3/2^{2}\right)^{n-1}$.
If n goes to infinite,
$4=1+3/2^{2}+\left(3/2^{2}\right)^{2}+\left(3/2^{2}\right)^{3}+\cdots$.

It is concluded that no odd but 1 is the number in the cyclic sequence. Thus,
no two odds except 1 are the same in descending sequences. This proves Lemma
11.

###### Lemma 11

Let a sequence of positive odds $x_{n}\rightarrow
x_{n-1}\rightarrow\cdots\rightarrow x_{k}\rightarrow
x_{k-1}\rightarrow\cdots\rightarrow x_{1}\rightarrow x_{0}$ generated by the
recurrence relation $x_{k-1}=\left(3x_{k}+1\right)/2^{m_{k-1}}$ of descending
operation with $m_{k-1}=\nu_{2}\left(3x_{k}+1\right)$, then no two odds except
1 in the sequence are the same.

##  6 Estimation of odds in descending operations

Approximation for the ratio of neighboring odds $x_{k-1}/x_{k}\approx
3/2^{m_{k-1}}$ is derived from the recurrence relation
$x_{k-1}=\left(3x_{k}+1\right)/2^{m_{k-1}}$. Since the chain relation shows
$\left(x_{n-1}/x_{n}\right)\left(x_{n-2}/x_{n-1}\right)\cdots\left(x_{0}/x_{1}\right)\approx
3^{n}/2^{b_{n}}$ with $b_{n}=\sum_{j=0}^{n-1}m_{j}$, $x_{0}\approx
3^{n}x_{n}/2^{b_{n}}$. If we let $x_{0}=1$ in a descending sequence of odds,
total number of halving operations for n times of descending operations
against an odd $x_{n}$ to reach the origin of 1 is
$b_{n}\approx\log_{2}{3^{n}x_{n}}$.

Lemma 10 states that the descending sequences from $y_{n}=x_{n}+2^{b_{n}+1}j$
to $y_{0}=x_{0}+2\times 3^{n}j$ generated by the recurrence relation
$y_{k-1}=\left(3y_{k}+1\right)/2^{m_{k-1}}$ show the same pattern as the
sequence from $x_{n}$ to $x_{0}$, where $j$ is nonnegative integer.The ratio
$y_{n}/y_{0}\approx 2^{b_{n}}/3^{n}$ of the sequences in the same pattern is
approximately constant, since the sequences from $y_{n}$ to $y_{0}$ have the
same $b_{n}$. The ratio of $y_{n}/y_{0}$ by larger odds becomes more close to
$2^{b_{n}}/3^{n}$. This proves Lemma 12.

###### Lemma 12

Let $b_{n}=\sum_{k=0}^{n-1}m_{k}$ be the total number of doubling operations
in the sequence of odds $x_{n}\rightarrow x_{n-1}\rightarrow\cdots\rightarrow
x_{k}\rightarrow\cdots\rightarrow x_{0}$ generated by the recurrence relation
of descending operation $x_{k-1}=\left(3x_{k}+1\right)/2^{m_{k-1}}$ with
$m_{k-1}=\nu_{2}\left(3x_{k}+1\right)$,if $y_{n}\equiv
x_{n}\left(mod\;2^{b_{n}+1}\right)$, then each sequence of odds
$y_{n}\rightarrow y_{n-1}\rightarrow\cdots\rightarrow
y_{k}\rightarrow\cdots\rightarrow y_{0}$ generated by
$y_{k-1}=\left(3y_{k}+1\right)/2^{m_{k-1}}$ shows $y_{0}\approx
3^{n}y_{n}/2^{b_{n}}$.

An example of descending sequence of odds with one halving operation reaching
$x_{0}=1$ is $26512143-[1]-39768215-[1]-59652323-[1]-89478485-[28]-1$ with
$b_{n}=31$ for $n=4$. The expected value is $x_{4}\approx
2^{31}/3^{4}=26512143.8$ for $x_{0}=1$.

General formula for the odds in descending sequence with one halving operation
is $y_{k}=-1+2^{k+1}3^{n-k}j$. If $n=3$, $y_{3}/y_{0}\approx 3^{3}/2^{3}$ by
Lemma 12. The primitive descending sequence of $j=1$ is
$15-[1]-23-[1]-35-[1]-53$. The sequences from $x_{4}$ to $x_{1}$ and from
$y_{3}$ to $y_{0}$ belong to the same pattern. Since $x_{4}$ is larger than
$y_{3}$ of $j=1$, the ratio of $x_{4}/x_{1}$ is more close to $3^{3}/2^{3}$
than $y_{3}/y_{0}$.

##  7 Origin of sequences

The first generation odds $x_{k}$ are infinitely generated by the recurrence
relation $x_{k}=\left(2^{m_{k-1}}x_{k-1}-1\right)/3$ of ascending operation
with $m_{k-1}$ times of doubling operations against a positive odd $x_{k-1}$
not multiple of 3. The first generation odds show sequentially $x_{k}\equiv
h\;(mod\;3)$ with $h=1,-1,0$ by every two doubling operations $m_{k-1}$.
Consecutive ascending operations can be performed infinitely against the odds
not multiples of 3 in the previous generation. Ascending operations are
terminated by the odds multiple of 3.

Each descending sequence is unique, and can start from terminal numbers. A
descending operation against any odds can generate odds not multiple of 3, and
vice versa. Descending operations against the odds of
1,5,21,85,$\cdots\;\left(=\sum_{j=0}^{m}4^{j}\right)$ reach 1, and otherwise
reach the odds greater than or equal to 5. Since no odds in each descending
sequence except 1 are the same, every descending sequence started from
terminal numbers continues until to reach the origin of 1. This proves the
Collatz conjecture.

## Funding

This research did not receive any specific grant from funding agencies in the
public, commercial, or not-for-profit sectors.

## References

  * [1] O’Connor, J.J.; Robertson, E.F. (2006). ”Lothar Collatz”. St Andrews University School of Mathematics and Statistics, Scotland.
  * [2] Steiner, R. P. (1977). ”A theorem on the syracuse problem”. Proceedings of the 7th Manitoba Conference on Numerical Mathematics. pp. 553–9. MR 0535032.