# Using Posters to Recommend Anime and Mangas in a Cold-Start Scenario

Jill-Jênn Vie  Mangaki
RIKEN Center for AIP
Tokyo, Japan
<EMAIL_ADDRESS>Florian Yger  LAMSADE
Université Paris-Dauphine
Paris, France
<EMAIL_ADDRESS>Ryan Lahfa, Basile Clement,
Kévin Cocchi, Thomas Chalumeau  Mangaki
Mitry-Mory, France
{ryan, basile, kevin<EMAIL_ADDRESS>Hisashi Kashima  Kyoto University
RIKEN Center for AIP
Kyoto, Japan
<EMAIL_ADDRESS>
###### Abstract

Item cold-start is a classical issue in recommender systems that affects anime
and manga recommendations as well. This problem can be framed as follows: how
to predict whether a user will like a manga that received few ratings from the
community? Content-based techniques can alleviate this issue but require extra
information, that is usually expensive to gather. In this paper, we use a deep
learning technique, Illustration2Vec, to easily extract tag information from
the manga and anime posters (e.g., sword, or ponytail). We propose BALSE
(Blended Alternate Least Squares with Explanation), a new model for
collaborative filtering, that benefits from this extra information to
recommend mangas. We show, using real data from an online manga recommender
system called Mangaki, that our model improves substantially the quality of
recommendations, especially for less-known manga, and is able to provide an
interpretation of the taste of the users.

###### Index Terms:

recommender system, cold-start, collaborative filtering, LASSO, tag prediction

##  I Introduction

Recommender systems are useful to help users decide what to enjoy next. In the
case of anime and mangas, users, easily overwhelmed by the ever-growing amount
of works, end up barely scratching the surface of what Japanese animation has
to offer. Collaborative filtering is a popular technique that relies on
existing rating data from users on items in order to predict unseen ratings
[1]. However, it is still hard to recommend items for which little information
is available, e.g., items for which few or no ratings have been provided by
the community. This problem has been referred to as the _item cold-start
problem_.

In order to alleviate this problem, it is possible to rely on extra
information about the items, such as metadata (e.g., for movies: directors,
composers, release date). However, such information is not always available:
new anime projects may only have a poster or a trailer, and a title. Such a
poster is usually the first contact that a user has with an item and plays a
large role in the user’s decision to watch it or not. Especially in the manga
and anime industry, posters contain a lot of information about the characters,
in order to maximize the visual appeal for the consumers. Hence, it is natural
to consider posters as a source for additional metadata. In recent years,
convolutional neural networks (CNNs) have established themselves as the _de-
facto_ method for extracting semantic information from image content in a wide
variety of tasks. We propose using a CNN for extracting meaningful tags
directly from the item’s poster. Such extracted tags can help draw links
between items, which can be useful when few ratings are available. In this
paper, we present BALSE111http://knowyourmeme.com/memes/events/balse (Blended
Alternate Least Squares with Explanation), a new method leveraging tag
information extracted from the posters for tackling the item cold-start
problem and improving the recommendation performance for little-known items.
We show using real data that our method provides better rating predictions
than existing techniques, and gives interpretable insight about the user’s
taste.

To the best of our knowledge, this is the first research work that uses tag
prediction on item posters in order to improve the accuracy of a recommender
system and explain to users why they are recommended little-known items.

This paper is organized as follows. We first present existing work related to
this research. Then, we expose the context of collaborative filtering and item
cold-start, together with a few common assumptions. We then describe our
model, BALSE, and present some experimental results on a real dataset. We
finish by discussing the results and future work.

##  II Related Work

Using side information in order to improve recommendations has been the core
of existing research [14] and several approaches have been developed to take
into account extra data about users or items, whether coming from text
alexandridis2017parvecmffang2011matrix, social networks [7], images or other
types of data nedelec2017specializingkim2014scalablexu2013speedup. More
recently, deep learning techniques have been used for this purpose. YouTube is
extracting features from the videos browsed within a user history in order to
improve their recommendations [6]. Researchers have also analyzed music
content as extra information [23]. They managed to recover explainable latent
features, corresponding to certain types of music, without any human
annotation. Such side information is particularly useful in order to mitigate
the cold-start problem
wei2017collaborativekula2015metadatabiswas2017combatingbobadilla2012collaborative.
In the exact context of movies, [29] extract latent features from the posters
using CNNs and improve the recommendations using those latent features.
However, those extracted features do not have semantic meaning, therefore they
cannot be used to explain to the user why extra works are recommended to them.

Several approaches have tried to bridge the gap between content-based
approaches and collaborative filtering [5]. The main idea behind those so-
called hybrid methods is to combine different recommendation models in order
to overcome their limitations and build more robust models with higher
predictive power. Existing techniques can take on several names: blending or
stacking roda2011optimaljahrer2010combining, or the general ensemble methods
for machine learning estimators. These techniques use the output of different
models as features for a higher-level model. This higher-level model is
usually a linear model [20]. Such blended methods have played an important
role in achieving top performance in challenges such as the Netflix Prize
sill2009featurekoren2009bellkor. The approach described in this paper builds
upon these ideas, as we are presenting a blended model, but the combination we
present is nonlinear. We complement a classical collaborative filtering
recommender system with a fallback model that will compensate the prediction
error on hard-to-predict data points, i.e. items with few ratings.

##  III Context

We assume the typical setting for collaborative filtering: we have access to a
$n\times m$ rating matrix $R$ containing the ratings of $n$ users on $m$ items
that can be either manga or anime: $r_{ij}$ represents the rating that user
$i$ gave to item $j$. In practice, since users only rate the few items that
they have interacted with, the rating matrix $R$ tend to be very sparse: in
the dataset considered in this paper, less than 1% of the entries are known;
other popular datasets in the field aggarwal2016recommenderwang2016learning
report similar levels of sparsity. Therefore, it is challenging to infer the
missing entries of $R$.

Another assumption is that the whole rating matrix can be explained by few
latent profiles, i.e. each user rating vector can be decomposed as a
combination of few latent vectors. Therefore, matrix completion is usually
performed using matrix factorization: we try to devise a factorization
$R\approx UV^{T}$ where a $n\times r$ matrix $U$ represents the user feature
vectors and a $m\times r$ matrix $V$ represents the item feature vectors. Once
this model is trained, that is, when the available entries of $R$ match their
counterparts in $UV^{T}$, computing a missing entry $(i,j)$ of the rating
matrix $R$ is simply performed by looking at the corresponding $(i,j)$ entry
of $UV^{T}$, or, equivalently, computing the dot product $U_{i}^{T}V_{j}$
where $U_{i}$ in the $i$-th row of $U$ and $V_{j}$ is the $j$-th row of $V$.

Finally, we also assume that we have access to the posters of some of the
items. This is all the content we have.

##  IV Our Model: BALSE

Figure 1: The BALSE architecture.

We now describe BALSE (Blended Alternate Least Squares with Explanation), our
model for recommending anime and mangas. The main idea is to rely on the
rating matrix when possible, and on the posters when rating information barely
exists. We expect a nonlinear blending of two models considering these sources
of information to achieve higher performance than any of the models. BALSE is
composed of several blocks:

  * •

an Illustration2Vec block, which is a convolutional neural network that takes
a poster as input and outputs tag predictions;

  * •

an ALS222ALS stands for Alternate Least Squares. block, that performs a matrix
factorization of the rating matrix for collaborative filtering using alternate
least squares with $\lambda$-weighted regularization;

  * •

a LASSO333LASSO stands for Least Absolute Shrinkage and Selection Operator.
block, that performs a regularized linear regression of each row of the rating
matrix, using tag predictions, in order to infer explainable user preferences;

  * •

a Steins gate, that performs a blending of the outputs of ALS and LASSO
models, in order to overcome their limitations and provide a final rating
value.

The main architecture of our model is presented in Figure 1. Both posters and
ratings are used for the predictions.

###  IV-A Illustration2Vec

Figure 2: Example of tag prediction on a manga illustration. ©Solène
Pichereau, http://sedeto.fr.

This block extracts tag information from the posters, such as “1girl” or
“weapon”. Such tags are associated with confidence weights that represent how
likely a certain tag appears in a certain poster. Formally, from the poster
database, we want to extract a $m\times t$ matrix $T$ where $m$ is the number
of items and $t$ is the number of possible tags, such that $t_{jk}\in[0,1]$
represents how likely a tag $k$ appears in the poster of item $j$. $T$ is
computed using Illustration2Vec [19], a VGG-16 neural network [21] that
predicts a variety of tags based on illustrations, pre-trained on ImageNet and
trained on manga illustrations labeled with tags from the community website
Danbooru. We use the implementation provided by the authors, which is freely
available. The output of the network is for each poster $j$, a vector
$T_{j}=(t_{j1},\ldots,t_{jt})$ where for tag $k=1,\ldots,t$, component
$t_{jk}\in[0,1]$ represents how likely tag $k$ describes the poster of item
$j$. In other words, the output of Illustration2Vec is a row of matrix $T$. We
will call such a vector a tag prediction. See Fig. 2 for an example of an
output of the Illustration2Vec model.

###  IV-B LASSO

The LASSO block approximates the rating matrix $R$ with a regularized linear
regression model called LASSO [22], using the tag predictions as features for
the items. We train a LASSO model for every user in the train set.

$R\approx PT^{T}$

where:

  * •

$P$ contains the parameters to learn, a $n\times t$ matrix of user
preferences, of which the $i$-th row is denoted as $P_{i}$ (likewise, $R_{i}$
denotes the $i$-th row of $R$);

  * •

$T$ is the given $m\times t$ matrix of tag predictions for each item.

LASSO comes with an $\alpha$ parameter which induces a L1 regularization term
to prevent overfitting, and to provide explanation of user preferences as we
will show later. Therefore, for every user $i$ of the train set, we estimate
the parameters $P_{i}$ that minimize:

$\frac{1}{2\mathcal{N}_{i}}\lVert R_{i}-P_{i}T^{T}\rVert_{2}^{2}+\alpha\lVert
P_{i}\rVert_{1}$

where $\mathcal{N}_{i}$ is the number of items rated by user $i$.

The output of the LASSO block is a rating prediction for each pair $(i,j)$:

$\hat{r}_{ij}^{LASSO}=\tau(P_{i}^{T}T_{j}).$

where $\tau:x\mapsto\max(\min(x,2),-2)$ is a function that shrinks its input
to values between -2 and 2. Such a function prevents the regressor from
providing invalid predictions that are outside the range of rating values.

###  IV-C ALS

The ALS block performs matrix factorization of the $n\times m$ sparse rating
matrix $R$, in order to provide an estimate $\hat{r}_{ij}^{ALS}$ for the
missing entries $(i,j)$. Thus, we learn the parameters of the following
factorization:

$R\approx UV^{T}$

where:

  * •

$U$ is the $n\times r$ matrix of user latent vectors;

  * •

$V$ is the $m\times r$ matrix of item latent vectors.

In order to avoid overfitting, we regularize the parameters to estimate.
Therefore, as we want to minimize the squared error, the loss function to
minimize has the following form:

$\sum_{i,j|r_{ij}\neq 0}(r_{ij}-U_{i}^{T}V_{j})^{2}+\lambda\left(\lVert
U_{i}\rVert_{2}^{2}+\lVert V_{j}\rVert^{2}_{2}\right)$

where $U_{i}$ for every $i=1,\ldots,n$ are the rows of $U$ and $V_{j}$ for
every $j=1,\ldots,m$ are the rows of $V$, and $\lambda$ is a regularization
parameter. This estimation is made by using alternate least squares with
weighted $\lambda$-regularization (ALS-WR) [30].

Once the parameters have been learned, the prediction for rating of user $i$
on item $j$ is:

$\hat{r}_{ij}^{ALS}=U_{i}^{T}V_{j}.$

###  IV-D Steins Gate

At this step, we have predictions from two different blocks: ALS trained on
the ratings and LASSO trained on the tag predictions of the posters. We want
to improve the predictive power of the overall model, thus we learn a rule
that would automatically choose the best model according to the number of
ratings of the item considered. Formally, we want to learn parameters $\beta$
and $\gamma$ such that:

$\displaystyle\hat{r}_{ij}^{BALSE}$
$\displaystyle=\sigma(\beta(\mathcal{R}_{j}-\gamma))\hat{r}_{ij}^{ALS}$
$\displaystyle\quad+\left(1-\sigma(\beta(\mathcal{R}_{j}-\gamma))\right)\hat{r}_{ij}^{LASSO}$

where:

  * •

$\mathcal{R}_{j}$ is the number of ratings of the item $j$;

  * •

$\hat{r}_{ij}^{ALS}$ is the rating prediction of ALS model for user $i$ on
item $j$;

  * •

$\hat{r}_{ij}^{LASSO}$ is the rating prediction of LASSO model for user $i$ on
item $j$;

  * •

$\sigma:x\mapsto 1/(1+e^{-x})$ is the sigmoid function.

The intuition behind this formula is the following: we want to find a
threshold $\gamma$ such that when the number of ratings of item $j$ verifies
$R_{j}\gg\gamma$, BALSE mimics ALS, e.g.,
$\hat{r}_{ij}^{BALSE}\approx\hat{r}_{ij}^{ALS}$, while when $R_{j}\ll\gamma$,
i.e. in a cold-start setting, BALSE mimics LASSO, e.g.,
$\hat{r}_{ij}^{BALSE}\approx\hat{r}_{ij}^{LASSO}$. $\beta$ is just a scaling
parameter that indicates how sharp the passage from LASSO to ALS will be.
Formally, we want to estimate the parameters $\beta$ and $\gamma$ that
minimize:

$\sum_{i,j|r_{ij}\neq 0}\left(\hat{r}_{ij}^{BALSE}-r_{ij}\right)^{2}.$

This formula is differentiable with respect to $\gamma$, thus it makes its
optimization easier. It can be seen as a soft switch between the two possible
predictions (ALS and LASSO), according to the number of ratings of the item.
The parameters $\beta$ and $\gamma$ are learned using gradient descent.

##  V Experiments and Results

###  V-A Mangaki dataset

Mangaki444https://mangaki.fr [24] is a website where people can rate items
that represent either manga or anime, and receive recommendations based on
their ratings. Mangaki can be seen as an open source version of Movielens [9]
for manga and anime. The Mangaki dataset is a $2079\times 9979$ anonymized
matrix of 334390 ratings from 2079 users on 9979 items. 80% of the items have
a poster.

Users can either rate an item with {favorite, like, neutral, dislike} if they
watched it, or {willsee, wontsee} if they did not watch it, i.e. testify
whether they want to watch it or not, based on the content presented: poster,
possibly synopsis, or some statistics.

###  V-B Models

The models considered in this benchmark are:

  * •

ALS: alternate least squares with weighted $\lambda$-regularization from [30],
that ignores posters;

  * •

LASSO: regularized linear regression using ratings and the tag predictions
from Illustration2Vec, that is content-based;

  * •

BALSE: the proposed method.

In practice, we use $\lambda=0.1$ and rank $r=20$ for every ALS model trained
and $\alpha=0.01$ for every LASSO model trained. Ratings are mapped into
custom values: (favorite, like, neutral, dislike) = (4, 2, 0.1, -2) and
(willsee, wontsee) = (0.5, -0.5). The Steins gate is optimized using gradient
descent with exponential decay implemented in TensorFlow. The learning rate
starts at $0.9$ and decays every 20 steps with a base of $0.997$. All the code
is available on our GitHub repository555https://github.com/mangaki/balse.

###  V-C 5-fold cross validation

We perform a 5-fold cross validation over the triplets $(i,j,r_{ij})$ of the
database, keeping 30% of the train set as a validation set. Therefore, our
data is split into a train set (56%), a validation set (24%) and a test set
(20%).

The vanilla models ALS and LASSO are trained on both the train set and the
validation set. For BALSE, the ALS and LASSO blocks are first trained using
the train set only, and the Steins gate parameters $\beta$ and $\gamma$ are
trained using the validation set666Please also note that in Steins gate, the
number of ratings $R_{j}$ of item $j$ is computed over the train set., in
order to prevent overfitting. For the final predictions of BALSE, blending is
performed using the learned $\beta$ and $\gamma$ parameters, and the vanilla
ALS and LASSO models. Finally, the root mean squared error (RMSE) is computed
over the test set.

We distinguish the performance of all three models on three sets: the whole
test set, a set of little-known items that received less than 3 ratings in the
train and validation set (that represents 1000 ratings, therefore 3% of the
test set), and cold-start items, i.e. items that were never seen in the train
and validation sets.

###  V-D Results

BALSE achieves a comparable performance than ALS overall, but substantially
improves the recommendations on little-known items, see Table I.

TABLE I: Results of RMSE on various subsets of the test set. RMSE | Whole test set | Little-known items (3% least rated) | Cold-start items (0 rating)
---|---|---|---
ALS | 1.15681 $\pm$ 0.004 | 1.29269 $\pm$ 0.029 | 1.50047 $\pm$ 0.03500
LASSO | 1.44444 $\pm$ 0.002 | 1.31331 $\pm$ 0.036 | 1.37909 $\pm$ 0.05600
BALSE | 1.14954 $\pm$ 0.004 | 1.22714 $\pm$ 0.036 | 1.34533 $\pm$ 0.04500
Figure 3: This is Steins gate’s choice: $\gamma=0.79040$. For items having at
least one rating, it is better to rely more on the ratings predicted by ALS
than by LASSO.

The learned parameter $\gamma$ of the Steins gate was less than 1, see Figure
3, which means that items having at least 1 rating can start to rely on ALS
(their ratings) more than LASSO (their poster) for the predictions. However,
BALSE provides better predictions than ALS for cold-start items, because ALS
was not trained on them in the train set, therefore it outputs constant
predictions.

ALS converges after 10 iterations. Steins gate takes 15k iterations to
converge. LASSO is the bottleneck of the proposed approach because one LASSO
model should be trained per user that appears in the train set.

###  V-E Explanation of user taste

Using the tags, it is possible to provide an explanation of the taste of any
user $i$ using the preference matrix $P$ learned by LASSO, because the columns
of $P_{i}$ are labeled with tags.

LASSO has been appreciated for its explainability [22]: the row preferences of
each user are sparse, allowing to capture the tags that explain best the
ratings of every user.

As an example, for a certain user among the authors, LASSO or BALSE report
that his six most preferred tags are: _kneehighs_ , _cat_ , _serafuku_ 777
_Serafuku_ means “Japanese school uniform”., _twin braids_ , _japanese
clothes_ and _angry_ whereas his six most disliked tags are: _pleated skirt_ ,
_standing_ , _silver hair_ , _window_ , _torn clothes_ and _skirt_. Using this
information, LASSO or BALSE can explain a recommendation: “We recommend to you
the anime _Chivalry of a Failed Knight_ , because there is a girl with _twin
braids_ , _serafuku_ and _japanese clothes_ ” or a warning: “You might not
like the anime _The Asterisk War: The Academy City on the Water_ because there
is a girl with a _pleated skirt_ , even though there are _kneehighs_ and
_serafuku_.”

##  VI Conclusion and Future Work

We proposed BALSE, a model for recommending anime and manga that makes use of
information that is automatically extracted from posters. We showed that our
model performs better than the baseline models, especially in the item cold-
start scenario.

This paper is a proof a concept and the obtained results are very encouraging.
Indeed, the blending Steins gate is such that any improvement made on any
block would improve the overall performance of the approach. As future work,
we plan to replace blocks in our architecture with more complex models:
Illustration2Vec could be replaced with residual networks [10], ALS could be
replaced with factorization machines [17] or co-factorization [8], LASSO could
be replaced with Localized Lasso [28], a variant that works well for few
samples, many features. We also to integrate more side information, for
instance the drawing style of the image, or tags coming from open databases
such as AniDB888http://anidb.net or AniList999https://anilist.co, in order to
improve the explanation of the users’ preferences.

For the sake of simplicity, we mapped the categorical ratings like, dislike,
etc. to ad-hoc values, but we could instead use ordinal regression methods
[16]. However, they require more computation to be trained properly. Ensemble
methods that blend more than two models could be considered [20], or that rely
not also on the number of ratings provided for a certain item, but on the
number of ratings provided by a certain user, or the number of works that
contain a certain tag.

Here, we mitigated the problem of item cold-start recommendation through the
use of extra information on the item side. Obviously, similar results could be
obtained for the user cold-start problem, provided enough data is available to
describe the users.

Using BALSE, recommender systems can automatically replenish their database,
where new items go through the tag prediction track and the explainable model
in order to justify the recommendations for their first users, and
automatically go to the main track when sufficient ratings have been
collected.

## Acknowledgments

This work was carried out while Florian Yger was a visiting researcher at
RIKEN Center for AIP, and Kévin Cocchi and Thomas Chalumeau were interns at
Mangaki. We would like to thank Nicolas Hug and Étienne Simon for their
helpful comments and Solène Pichereau for kindly providing the example
illustration of Figure 2.

## References

  * [1] Charu C Aggarwal  “Recommender systems”  Springer, 2016
  * [2] Georgios Alexandridis, Georgios Siolas and Andreas Stafylopatis  “ParVecMF: A Paragraph Vector-based Matrix Factorization Recommender System”  In _arXiv preprint arXiv:1706.07513_ , 2017
  * [3] Sampoorna Biswas, Laks VS Lakshmanan and Senjuti Basu Ray  “Combating the Cold Start User Problem in Model Based Collaborative Filtering”  In _arXiv preprint arXiv:1703.00397_ , 2017
  * [4] JesúS Bobadilla, Fernando Ortega, Antonio Hernando and JesúS Bernal  “A collaborative filtering approach to mitigate the new user cold start problem”  In _Knowledge-Based Systems_ 26 Elsevier, 2012, pp. 225–238
  * [5] Robin Burke  “Hybrid recommender systems: Survey and experiments”  In _User modeling and user-adapted interaction_ 12.4 Springer, 2002, pp. 331–370
  * [6] Paul Covington, Jay Adams and Emre Sargin  “Deep neural networks for youtube recommendations”  In _Proceedings of the 10th ACM Conference on Recommender Systems_ , 2016, pp. 191–198  ACM
  * [7] Julien Delporte, Alexandros Karatzoglou, Tomasz Matuszczyk and Stéphane Canu  “Socially enabled preference learning from implicit feedback data”  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , 2013, pp. 145–160  Springer Berlin Heidelberg
  * [8] Yi Fang and Luo Si  “Matrix co-factorization for recommendation with rich side information and implicit feedback”  In _Proceedings of the 2nd International Workshop on Information Heterogeneity and Fusion in Recommender Systems_ , 2011, pp. 65–69  ACM
  * [9] F. Harper and Joseph A. Konstan  “The MovieLens Datasets: History and Context”  In _ACM Trans. Interact. Intell. Syst._ 5.4 New York, NY, USA: ACM, 2015, pp. 19:1–19:19  DOI: 10.1145/2827872
  * [10] 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_ , 2016, pp. 770–778
  * [11] Michael Jahrer, Andreas Töscher and Robert Legenstein  “Combining predictions for accurate recommender systems”  In _Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2010, pp. 693–702  ACM
  * [12] Yong-Deok Kim and Seungjin Choi  “Scalable variational bayesian matrix factorization with side information”  In _Artificial Intelligence and Statistics_ , 2014, pp. 493–502
  * [13] Yehuda Koren  “The bellkor solution to the netflix grand prize”  In _Netflix prize documentation_ 81, 2009, pp. 1–10
  * [14] Maciej Kula  “Metadata embeddings for user and item cold-start recommendations”  In _arXiv preprint arXiv:1507.08439_ , 2015
  * [15] Thomas Nedelec, Elena Smirnova and Flavian Vasile  “Specializing Joint Representations for the task of Product Recommendation”  In _arXiv preprint arXiv:1706.07625_ , 2017
  * [16] Fabian Pedregosa, Francis Bach and Alexandre Gramfort  “On the consistency of ordinal regression methods”  In _Journal of Machine Learning Research_ 18.55, 2017, pp. 1–35
  * [17] Steffen Rendle  “Factorization machines”  In _Data Mining (ICDM), 2010 IEEE 10th International Conference on_ , 2010, pp. 995–1000  IEEE
  * [18] Fabio Roda, Alberto Costa and Leo Liberti  “Optimal recommender systems blending”  In _Proceedings of the International Conference on Web Intelligence, Mining and Semantics_ , 2011, pp. 60  ACM
  * [19] Masaki Saito and Yusuke Matsui  “Illustration2Vec: A Semantic Vector Representation of Illustrations”  In _SIGGRAPH Asia Technical Briefs_ , 2015
  * [20] Joseph Sill, Gábor Takács, Lester Mackey and David Lin  “Feature-weighted linear stacking”  In _arXiv preprint arXiv:0911.0460_ , 2009
  * [21] Karen Simonyan and Andrew Zisserman  “Very deep convolutional networks for large-scale image recognition”  In _arXiv preprint arXiv:1409.1556_ , 2014
  * [22] Robert Tibshirani  “Regression shrinkage and selection via the lasso”  In _Journal of the Royal Statistical Society. Series B (Methodological)_ JSTOR, 1996, pp. 267–288
  * [23] Aaron Van den Oord, Sander Dieleman and Benjamin Schrauwen  “Deep content-based music recommendation”  In _Advances in Neural Information Processing Systems_ , 2013, pp. 2643–2651
  * [24] Jill-Jênn Vie, Camille Laïly and Solène Pichereau  “Mangaki: an Anime/Manga Recommender System with Fast Preference Elicitation”  In _Technical Report_ , 2015
  * [25] Huazheng Wang, Qingyun Wu and Hongning Wang  “Learning Hidden Features for Contextual Bandits”  In _Proceedings of the 25th ACM International on Conference on Information and Knowledge Management_ , 2016, pp. 1633–1642  ACM
  * [26] Jian Wei, Jianhua He, Kai Chen, Yi Zhou and Zuoyin Tang  “Collaborative filtering and deep learning based recommendation system for cold start items”  In _Expert Systems with Applications_ 69 Elsevier, 2017, pp. 29–39
  * [27] Miao Xu, Rong Jin and Zhi-Hua Zhou  “Speedup matrix completion with side information: Application to multi-label learning”  In _Advances in Neural Information Processing Systems_ , 2013, pp. 2301–2309
  * [28] Makoto Yamada, Koh Takeuchi, Tomoharu Iwata, John Shawe-Taylor and Samuel Kaski  “Localized Lasso for High-Dimensional Regression”  In _arXiv preprint arXiv:1603.06743_ , 2016
  * [29] Lili Zhao, Zhongqi Lu, Sinno Jialin Plan and Qiang Yang  “Matrix factorization+ for movie recommendation”  In _Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence_ , 2016, pp. 3945–3951  AAAI Press
  * [30] Yunhong Zhou, Dennis Wilkinson, Robert Schreiber and Rong Pan  “Large-scale parallel collaborative filtering for the netflix prize”  In _Lecture Notes in Computer Science_ 5034 Springer, 2008, pp. 337–348


# A recursive function coding number theoretic functions

Vesa Halava, Tero Harju, Teemu Pirttimäki
Department of Mathematics and Statistics
University of Turku, Finland
Supported by emmy.network foundation under the aegis of the Fondation de
Luxembourg.

###### Abstract

We show that there exists a fixed recursive function $e$ such that for all
functions $h\colon\mathbb{N}\to\mathbb{N}$, there exists an injective function
$c_{h}\colon\mathbb{N}\to\mathbb{N}$ such that $c_{h}(h(n))=e(c_{h}(n))$,
i.e., $h=c_{h}^{-1}ec_{h}$.

##  1 Introduction

This article is motivated by the Woodin theorem on computability [5] and its
entertaining implication stating that “every function is computable”, where
functions are considered to be on natural numbers, and “computable” refers to
Turing computability in the models of Peano arithmetic. To a computer
scientist or a mathematician coming from formal languages this strikes quite
strange. Non-computable function should not be computable!

The actual Woodin theorem on computability considers computations of Turing
machines in nonstandard models of arithmetic. Indeed, the Woodin theorem
states a much stronger model theoretical result of computability in non-
standard models and the existence of end-extensions models. We do not state
the Woodin theorem in full, because it is quite involved and lies outside the
scope of our treatment.

We shall show that there exists a recursive $e$ that “computes” all functions
$h\colon\mathbb{N}\to\mathbb{N}$ after we encode the inputs and outputs by an
injective coding $c_{h}$, i.e.,

$h(n)=c_{h}^{-1}ec_{h}(n)\text{ for all }n\in\mathbb{N}\,.$

The universality questions for _real_ functions go back to Sierpiński [4]; see
Larson et al. [2]. Rado [3] considered the problem in a more general setting.
Sierpiński showed that under the assumption of the Continuum Hypothesis there
exists a fixed 2-place real Borel function $B$ such that for every 2-place
real function $h$, there exists a function $\varphi$ satisfying
$h(x,y)=B(\varphi(x),\varphi(y))$. Larson et al. [2] show that without the
Continuum Hypothesis, we may not have universal functions on the reals.

In the treatment below, we consider only number theoretic functions
$h\colon\mathbb{N}\to\mathbb{N}$ for single argument values. Our approach does
not involve logical models as needed in the Woodin theorem.

##  2 Trees of functions

In the proofs we use directed graphs induced by the functions on $\mathbb{N}$.
Let $h\colon\mathbb{N}\to\mathbb{N}$ be a function and $B\subseteq\mathbb{N}$.
The image of $B$ under $h$ is the set

$h(B)=\\{h(n)\mid n\in B\\}.$

We consider the directed (possibly infinite) graph
$G_{(h,B)}=(V_{(h,B)},E_{(h,B)})$ allowing loops where the set of _vertices_
is $V_{(h,B)}=B\cup h(B)$, and the set of _edges_ is
$E_{(h,B)}=\\{(n,h(n))\mid n\in B\\}\subseteq V_{(h,B)}\times V_{(h,B)}$. The
edges are directed, and we also denote $(n,h(n))$ by $n\rightarrow h(n)$. Such
graphs induced by a functions $h$ on some subset $B\subseteq\mathbb{N}$ are
called _function graphs_.

Denote by $G_{h}=G_{(h,\mathbb{N})}=(\mathbb{N},H)$ the _full graph of_ $h$,
where $H=\\{(n,h(n))\mid n\in\mathbb{N}\\}$.

######  Lemma 1.

In any function graph, all vertices have a unique outgoing edge. There are
countably, possibly infinitely, many incoming edges to each vertex.

###### Proof.

Follows from the fact that $h$ is a function. ∎

Let $G=(V,E)$ be the graph of a function $h$. A vertex $h(n)$ is the
_successor of_ $n\in V$ in $G$ for $h$. We let

$\displaystyle h^{+}(n)$ $\displaystyle=\\{v\mid v=h^{k}(n)\text{ for some
}k\geq 1\\},$ $\displaystyle h^{-}({n})$ $\displaystyle=\\{v\mid
n=h^{k}(v)\text{ for some }k\geq 1\\}$

denote the sets of the _descendants_ and _predecessors_ of $n$, respectively.

Note that the set of _immediate predecessors_ $h^{-1}(n)$ can be infinite. It
also can be empty.

A _cycle_ in function graph $G$ is a _closed path_ , that is, it is of the
form $h(n),h^{2}(n),\dots,h^{k}(n)=n$ for some $k\geq 1$, where the vertices
are all different. In the case $k=1$, $h(n)=n$ denotes a loop, an edge of the
form $(n,n)$. The number $k$ is called the _length_ of the cycle.

For vertices $u$ and $v$ of a function graph, we say that $v$ is _connected
to_ $u$ if there is a path from $v$ to $u$, i.e., if $u$ is a descendant of
$v$.

######  Lemma 2.

Consider a graph of a function $h$. If $u$ and $v$ belong to a common finite
or infinite path, then one of them is a descendant of the other: either
$h^{k}(u)=v$ or $h^{k}(v)=u$ for some $k\in\mathbb{N}$.

###### Proof.

This is clear from the definition of a function graph. ∎

A _connected component of_ a vertex $n\in\mathbb{N}$ of the full function
graph $G_{h}=(\mathbb{N},H)$ is the subgraph $G_{h}^{n}=G_{(h,V)}$ such that
$n\in V$ and for all $m\in\mathbb{N}$, $m\in V$ if and if only if $n$ and $m$
have a common descendant.

######  Lemma 3.

A connected component of $G_{h}$ can have at most one cycle.

###### Proof.

Follows from the fact that $h$ is a function. Indeed, if a connected component
has a cycle, it is unique as all vertices have a unique outgoing edge. This
means that the connected component of $G_{h}$ ’ends’ in the cycle. ∎

All vertices $n$ in the full function graph $G_{h}$ start an infinite sequence
$(h^{k}(n))_{k=0}^{\infty}$. This sequence may be ultimately periodic, which
means that the iteration of $h$ startin from $n$ leads to a cycle. Otherwise,
the sequence is an infinite path.

######  Lemma 4.

The connected component $G_{h}^{n}$ of $G_{h}$ either

  1. 1.

has a unique cycle and for all vertices $m$ in $G_{h}^{n}$, the sequence
$(h^{k}(m))_{k=0}^{\infty}$ is ultimately periodic and leads to the unique
cycle,

  2. 2.

has no cycles and for all vertices $m$ in $G_{h}^{n}$, the sequence
$(h^{k}(m))_{k=0}^{\infty}$ is not ultimately periodic.

For all vertices $m$ in the component $G_{h}^{n}$, there exist $k_{1}$ and
$k_{2}$ such that

$h^{k_{1}+i}(n)=h^{k_{2}+i}(m)$

for all $i\in\mathbb{N}$.

###### Proof.

This follows from the fact that all vertices of the $G_{h}^{n}$ are a common
descendant with $n$. Hence, for all vertices $m$, $(h^{k}(m))_{k=0}^{\infty}$
is ultimately periodic iff $(h^{k}(n))_{k=0}^{\infty}$ ultimately periodic.

Also if $m$ and $n$ have a common descendant, they are both connect to a
vertex $w=h^{k_{1}}(n)=h^{k_{2}}(m)$. ∎

In order to chacterise the connected components of a function graph we need
function trees. A subgraph $G=(V,E)$ of a function graph is an _function tree_
if there is a unique _root_ $u\in V$ such that all vertices in $V$ are
connected to $u$ (except $u$). Naturally it needs to be a tree and it can be
infinite. The _depth_ of a rooted tree is the length of a longest path in it.
Clearly all finite trees have finite depth.

Let $n\in\mathbb{N}$ be a vertex of $G_{h}$ for a function $h$ and let
$C_{n}^{h}$ be the set of the vertices in the cycle of $G_{h}$ containing $n$.
Hence, if $n$ does not belong to a cycle then $C_{n}^{h}=\emptyset$. Denote by

$\stackrel{{\scriptstyle\leftarrow}}{{n}}=\\{v\mid\exists k\geq 1\colon
h^{k}(v)=n\text{ and }h^{k-1}(v)\notin C_{n}^{h}\\},$

the set of all predecessors of $n$ that are connected to $n$ by a path not
visiting the cycle of $n$ (if $n$ belongs to one). It can be that $n$ has only
one immediate predecessor and it is from $C_{n}^{h}$, then
$\stackrel{{\scriptstyle\leftarrow}}{{n}}=\emptyset$. Note also that for a
vertex $n$ not in a cycle $\stackrel{{\scriptstyle\leftarrow}}{{n}}=h^{-}(n)$.
Let then

$O_{h}^{n}=G_{(h,\stackrel{{\scriptstyle\leftarrow}}{{n}})}.$

######  Lemma 5.

Subgraph $O_{h}^{n}$ is a function tree with $n$ as a root.

###### Proof.

By the definition of the sets $\stackrel{{\scriptstyle\leftarrow}}{{n}}$,
$O_{h}^{n}=G_{(h,\stackrel{{\scriptstyle\leftarrow}}{{n}})}=(V,E)$ where
$V=\stackrel{{\scriptstyle\leftarrow}}{{n}}\cup
h(\stackrel{{\scriptstyle\leftarrow}}{{n}})=\stackrel{{\scriptstyle\leftarrow}}{{n}}\cup\\{n\\}$,
since $n$ is the only image of $h$ on set
$\stackrel{{\scriptstyle\leftarrow}}{{n}}$ not in
$\stackrel{{\scriptstyle\leftarrow}}{{n}}$. Clearly, $O_{h}^{n}$ is a function
tree. ∎

######  Lemma 6.

In the full function graph $G_{h}=G_{(h,\mathbb{N})}$ with a vertex $n$, the
connected components $G_{h}^{n}$ are either

  1. 1.

a cycle $C_{m}^{h}$ together with the all function trees $O_{h}^{u}$ with
$u\in C_{h}^{m}$, or

  2. 2.

the function tree $O_{h}^{n}$ together with the function trees $O_{h}^{m}$ for
the (infinitely many) descendants $m$ of $n$.

###### Proof.

By Lemma 4 we have two cases:

1) If a connected component contains a cycle, then it is of the first form.
Indeed, if a vertex of the component is outside of the unique cycle, it
belongs to a function tree of the vertex through which it iteratively connects
to the cycle.

2) On the other hand, if the connected component does not contain any cycle,
then it is an ordered tree such that from all of its vertices there begins an
infinite path. By definition, the predecessors of $n$ are in $O_{h}^{n}$
rooted in $n$. The other vertices in the component have a common descendant
with $n$, that is, they belong to a function tree $O_{h}^{m}$ for some
$m\in\stackrel{{\scriptstyle\rightarrow}}{{n}}$. This proves the claim. ∎

##  3 Universal recursive function $e$

There are countably many non-isomorphic connected function trees and these are
partitioned into four different types according whether they contain a cycle
and whether they have infinite paths. Moreover, for each type there are non-
isomorphic connected function trees, but they can all be embedded in a cycle
(of some length) and a finite number of function rooted trees.

The basic idea in the construction of the special function $e$ is to pack its
function graph with infinitely many times each of the above possibilities.

The construction of $e$ can be best explained by considering its image
sequence $\sigma=e(1),e(2),\dots$. In the sequence $\sigma$ all natural
numbers appear infinitely many times. It can be separated to two cases: (1)
First, for the powers $n=2^{k}$, the iterative sequence
$(e^{i}(n))_{i=0}^{\infty}$ is defined so that it is not ultimately periodic
for odd $k$. (2) Secondly, all natural numbers are roots of a function tree
with infinite depth. For any ultimately periodic sequence of natural numbers,
the images of $e$ contains infinitely many cycles of all lengths.

We shall now give a construction of the sequence $\sigma$.

  1. (i)

For all inputs of the form $n=2^{k}$ for $k\geq 1$, let $e(n)=2^{2k}$.

  2. (ii)

We use three counters $k,n$ and $i$, where

     * •

$k$ is for the length of the cycle,

     * •

$n$ is for the maximal number of determined argument $e(n)$, and

     * •

$i$ is for indexing the current number in the sequence.

The initial values are $k=1=n$ and $i=0$. On every round, the procedure does
the following:

    1. (a)

assign one cycle of all lengths $\leq k$, and update $i:=i+1$ on each of these
steps. Set $n$ to the last $i$ for which $e(i)$ is determined. Set $k:=k+1$.

    2. (b)

assign the numbers $1,\dots,n$ to $e(i)$ while increasing $i:=i+1$ at each of
these steps.

    3. (c)

In these cases, skip the numbers $2^{k}$. By skipping we mean that in every
step, $i$ is tested, and if the $i=2^{k}$, we set $i=i+1$.

  3. (iii)

The assignment of a cycle of length $k$ for all $i$ is as follows: if there
are no powers of two in $\\{i,\dots,i+(k-1)\\}$, then the cycle of length $k$
will be

$e(i)=i+(k-1),e(i+(k-1))=i+(k-1)-1,\dots,e(i+1))=i.$ (1)

If the number of powers of two in $\\{i,\dots,i+(k-1)\\}$ is $t$, then let
$e(i)=i+(k-1)+t$ and skip the powers of two from both from the image and
domain when coming down to $i$ with the images in (1).

Actually, it is an easy number theoretical exercise to show that $t\leq 1$ in
$e$.

First 56 elements of $\sigma$ are

$\begin{split}&\stackrel{{\scriptstyle(1)}}{{\underline{1}}},\stackrel{{\scriptstyle(2)}}{{2^{2}}},\stackrel{{\scriptstyle(3)}}{{1}},\stackrel{{\scriptstyle(4)}}{{2^{2\cdot
2}}},{\stackrel{{\scriptstyle(5)}}{{\underline{5}}}},\underline{\stackrel{{\scriptstyle(6)}}{{7}},\stackrel{{\scriptstyle(7)}}{{{6}}}},\stackrel{{\scriptstyle(8)}}{{2^{2\cdot
3}}},\stackrel{{\scriptstyle(9)}}{{1}},\stackrel{{\scriptstyle(10)}}{{2}},\stackrel{{\scriptstyle(11)}}{{3}},\stackrel{{\scriptstyle(12)}}{{4}},\stackrel{{\scriptstyle(13)}}{{5}},\stackrel{{\scriptstyle(14)}}{{6}},\stackrel{{\scriptstyle(15)}}{{7}},\stackrel{{\scriptstyle(16)}}{{2^{2\cdot
4}}},\\\
&\underline{\stackrel{{\scriptstyle(17)}}{{17}}},\underline{\stackrel{{\scriptstyle(18)}}{{19}},\stackrel{{\scriptstyle(19)}}{{18}}},\underline{\stackrel{{\scriptstyle(20)}}{{22}},\stackrel{{\scriptstyle(21)}}{{20}},\stackrel{{\scriptstyle(22)}}{{21}}},\stackrel{{\scriptstyle(23)}}{{1}},\dots,\stackrel{{\scriptstyle(31)}}{{10}},\stackrel{{\scriptstyle(32)}}{{2^{2\cdot
5}}},\stackrel{{\scriptstyle(33)}}{{11}},\dots,\stackrel{{\scriptstyle(45)}}{{22}},\underline{\stackrel{{\scriptstyle(46)}}{{46}}},\\\
&\underline{\stackrel{{\scriptstyle(47)}}{{48}},\stackrel{{\scriptstyle(48)}}{{47}}},\underline{\stackrel{{\scriptstyle(49)}}{{51}},\stackrel{{\scriptstyle(50)}}{{49}},\stackrel{{\scriptstyle(51)}}{{50}}},\underline{\stackrel{{\scriptstyle(52)}}{{55}},\stackrel{{\scriptstyle(53)}}{{52}},\stackrel{{\scriptstyle(54)}}{{53}},\stackrel{{\scriptstyle(55)}}{{54}}},\stackrel{{\scriptstyle(56)}}{{1}},\dots\end{split}$

where $(i)$ refer to the position in the sequence, and $e(i)$ is written below
$(i)$. Underlining denotes what is a called a cycle. For example,
$e(20)=22,e(22)=21,e(21)=20$ making a cycle of length three.

######  Theorem 1.

The function $e$ is recursive.

###### Proof.

This is clear from the above algorithm for sequence $\sigma$. Indeed, for an
input $i$, the value $e(i)$ is computed by the sequence $\sigma$ up to and
including $i$ by simply adding a new counter. ∎

The function $e$ has the following properties:

  1. 1.

All numbers appear as an image of $e$ infinitely many times.

  2. 2.

There is a partitioning $\mathbb{N}=P\cup C\cup T$, where $P=\\{2^{k}\mid
k\geq 1\\}$, $C=\\{n\mid n\text{ appears in a cycle in }G_{e}\\}$, and
$T=\mathbb{N}\setminus(P\cup C)$. These sets are all infinite and pairwisely
disjoint.

  3. 3.

The set $T=\bigcup_{n\in P\cup C}T_{n}$ is a partition of $T$, where for each
$i\in T_{n}$, $k$ is the least power for which $n=e^{k}(i)\in P\cup C$.

  4. 4.

For all $n\notin P\cup C$, we have $e(n)<n$.

  5. 5.

For each $k$, there are infinitely many cycles of length $k$ in $G_{e}$.

  6. 6.

There are infinitely many disjoint, not ultimately periodic, subsequences in
$e$, i.e. paths in $G_{e}$. Indeed, such subsequences have arise from
$n=2^{m}$ with odd $m$. Note also that all numbers of the form $2^{2k}$ with
even powers belong to a unique not ultimately periodic subsequence in $e$
characterized by the largest odd factor of $k$.

  7. 7.

For any $n\in P\cup C$ and $T_{n}$, $G_{(e,T_{n})}$ forms a function tree
rooted at $n$ and each vertex in it has infinitely many incoming edges.

  8. 8.

For $n\in C$, $O_{e}^{n}=G_{(e,T_{n})}$. This follows from the fact that
$\stackrel{{\scriptstyle\leftarrow}}{{n}}=T_{n}$.

  9. 9.

For $n\in P$ we have two cases for function trees for it:

    1. (a)

if $n=2^{k}$ with odd $k$, then $O_{e}^{n}=G_{(e,T_{n})}$. This follows from
the fact that $\stackrel{{\scriptstyle\leftarrow}}{{n}}=T_{n}$.

    2. (b)

if $n=2^{k}$ with even $k$, then
$\stackrel{{\scriptstyle\leftarrow}}{{n}}=T_{n}\cup\\{2^{\frac{k}{2}}\\}\cup\stackrel{{\scriptstyle\leftarrow}}{{2^{\frac{k}{2}}}}$,
and $O_{e}^{n}=G_{(e,T_{n})}\cup G_{(e,U_{n})}$, where
$U_{n}=\\{2^{\frac{k}{2}}\\}\cup\stackrel{{\scriptstyle\leftarrow}}{{2^{\frac{k}{2}}}}$.
Note that $G_{(e,U_{n})}$ consists of $O_{e}^{2^{\frac{k}{2}}}$ together with
the edge $(2^{\frac{k}{2}},n)$.

  10. 10.

Combining cases 6 and 9(a), we get that there are countably infinitely many
connected subgraphs in $G_{e}$ with two-way infinite paths. Indeed, for all
$n=2k$ with odd $k$, $O_{e}^{n}$ is a function tree of infinite depth rooted
in $n$, and, for all vertices is $v$ in it, the sequence
$(h(v)^{k})_{k=0}^{\infty}$ is not ultimately periodic.

We define further, for all vertices $n\in P\cup C$,

$V_{n}=T_{n}\cup\\{n\\}\text{ and }G_{(e,T_{n})}=(V_{n},E_{n}).$

In the following, an _enumeration function_ $\epsilon$ of a set $S$ is an
injective mapping from $\mathbb{N}$ to $S$ such $\epsilon(n)$ is defined for
all $1\leq n\leq|S|$. In other words, there is a one-to-one correspondence
between the sets $\\{1,2,\dots,|S|\\}$ and $S$. Note that $|S|$ may be
infinite.

The set $e^{-1}(u)$ is naturally countably infinite for all $u\in\mathbb{N}$;
see the fact 1 of $e$. Assume now that $n\in P\cup C$. We define the
enumeration functions $\beta_{u}$ for all $u\in V_{n}$. First, let $\beta_{n}$
be the enumeration of the set $e^{-1}(n)\cap T_{n}$. We need to intersect
$e^{-1}(n)$ with $T_{n}$, since for $n\in C$, $e^{-1}(n)$ contains also the
unique predecessor $m$ of $n$ in the cycle and $m\notin T_{n}$, and, similarly
in the case where $n=2^{k}\in P$ with even $k$, $2^{\frac{k}{2}}\in
e^{-1}(n)\setminus T_{n}$ (see case 9(b) of properties of $e$).

For each $v\in V_{n}$, an enumeration $\beta_{v}$ of the set $e^{-1}(v)$ (and
$e^{-1}(v)\cap T_{n}$ if $v=n$) is given by the sequence $\sigma$ of $e$:
$\beta_{v}(i)=x_{i}$ equals the $i$’th number $x_{i}>v+1$ such that
$e(x_{i})=v$. Note that the condition $x_{i}>v+1$ is for $v=n\in C$ or
$v=n=2^{k}\in P$ with even $k$: If $n\in C$, then the unique predecessor of
$n$ in the cycle of length $t$ is either $n+1$ or $n-(t-1)\leq n$ (see case
(iii) of the definition of $e$). And for $n=2^{k}$ with even $k$, the
predecessor $2^{\frac{k}{2}}$ of $n$ not in $T_{n}$ is clearly less than $n$.

In other words, $\beta_{v}(i)=x_{i}$ for all $v$, and

$e^{-1}(v)\cap T_{n}=\\{x_{i}\mid i\in\mathbb{N}\colon e(x_{i})=v,\text{ and
}v+1<x_{i}<x_{i+1}\\}.$

In the next lemma we show that any function tree, i.e., a subgraph of $G_{h}$
for some $h\colon\mathbb{N}\to\mathbb{N}$, can be injectively mapped to (a
subgraph) of $G_{(e,T_{n})}$. Note that, instead of $G_{(e,T_{n})}$, we could
also show the result for any function tree rooted in $m\in T_{n}$ in $G_{e}$,
but that is unnecessary for what follows.

######  Lemma 7.

Let $h\colon\mathbb{N}\to\mathbb{N}$ be a function and $O=(V,E)$ be a tree
which is a subgraph of $G_{h}$ rooted at $r$. Then, for all $n\in P\cup C$,
there is an injective function $c_{O}\colon V\to V_{n}$ such that
$c_{O}(h(m))=e(c_{O}(m))$ for all $m\in V\setminus\\{r\\}$, and $c_{O}(r)=n$.

###### Proof.

Let $\pi$ be an enumeration function of the vertex set $V$ of the tree $O$. We
may assume that $\pi(1)=r$, for the root $r$. Also, let $\alpha_{u}$ be an
enumeration function of the set $h^{-1}(u)\cap V$ for each vertex $u\in V$.

We define $c_{O}$ by an ascending sequence of subsets $\Delta_{i}\subseteq
V\times V_{n}$. In every steps we add pairs $(a,b)$ to $\Delta_{i}$ such that
$a\in h^{-1}(u)$ and $b\in e^{-1}(v)$ for some $(u,v)\in\Delta_{i}$.
Therefore, $h(a)=u$, $e(b)=v$ and $c_{O}(h(a))=c_{O}(u)=v=e(b)=e(c_{O}(a))$.
In what follows, $\Delta_{j}\subseteq c_{O}$ for all $j=0,1,\dots$.

To begin with, let

$\Delta_{0}=\\{(r,n)\\}\cup\\{(\alpha_{r}(i),\beta_{n}(i))\mid
i=1,\dots,|h^{-1}(r)\cap V|\\},$

where $\beta_{n}$ is the enumeration function of the set $e^{-1}(n)\cap
T_{n}$. Now, for any pair $(\alpha_{r}(i),\beta_{n}(i))\in\Delta_{0}$, we have
$h(\alpha_{r}(i))=r$ and $e(\beta_{n}(i))=n$, and
$c_{O}(h(\alpha_{r}(i)))=c_{O}(r)=n=e(\beta_{n}(i))=e(c_{O}(\alpha_{r}(i)))$.

The sets $\Delta_{j}$, for $j\geq 1$, are defined inductively: For the vertex
$\pi(j)$, if $(\pi(j),v)\in\Delta_{j-1}$ for some $v\in V_{n}$, then we have
two cases:

  1. 1.

if for all $u\in h^{-1}(\pi(j))$, there is a pair
$(u,v^{\prime})\in\Delta_{j-1}$, then set $\Delta_{j}=\Delta_{j-1}$. This
corresponds to the case where $\pi(j)$ and all its predecessors already have a
pair in $\Delta_{j-1}$. Note that our construction works so that either all
predecessors of vertex in $V$ have a pair in $\Delta_{j-1}$ or none of the
predecessors has.

  2. 2.

otherwise, set
$\Delta_{j}=\Delta_{j-1}\cup\\{(\alpha_{\pi(j)}(i),\beta_{v}(i))\mid
i=1,\dots,|h^{-1}(\pi(j))\cap V|\\}$.

In the case, when there is no $v\in V_{n}$ such that
$(\pi(j),v)\in\Delta_{j-1}$, there exists a (finite and unique) shortest path
in $O$ such that $\pi(j)=p_{0},p_{1},p_{2},\dots,p_{k}$ such that
$(p_{k},v)\in\Delta_{j-1}$ for some $v\in V_{n}$. In other words, in iteration
sequence $h^{k}(\pi(j))$, for some $k\geq 1$
$(h^{k}(\pi(j)),v)\in\Delta_{j-1}$ as the root of $O$ has a pair, and let
$p_{i}=h^{i}(\pi(j))$ for $i=0,\dots,k$.

Then let $v_{k}=v$ and construct a set $\Sigma_{t}$, downwards for
$t=k,k-1,\dots,0$, by

$\Sigma_{t}=\\{(\alpha_{p_{t}}(i),\beta_{v_{t}}(i))\mid
i=1,\dots,|h^{-1}(p_{t})\cap V|\\},$

and $v_{t-1}=v^{\prime}$ for $t=k,\dots,1$ such that
$(p_{t-1},v^{\prime})\in\Sigma_{t}$.

Let $\Sigma=\cup_{t=0}^{k}\Sigma_{t}$ and $\Delta_{j}=\Delta_{j-1}\cup\Sigma$.
Now we note two things:

1) For the path $\pi(j)=p_{0},p_{1},p_{2},\dots,p_{k}$ in $O$ such that
$h^{i}(\pi(j))=p_{i}$ there are pairs $(p_{t},v_{t})\in\Sigma$ for
$t=0,\dots,k$ such that $v=v_{k},\dots,v_{0}$
$e(v_{0})=v_{1},e(v_{1})=v_{2},\dots,e(v_{k-1})=v_{k}=v$,
$and(p_{k},v_{k}\in\Delta_{j-1}$. Therefore, $h(p_{i})=p_{i+1}$, and
$e_{(}v_{i})=v_{i+1}$ for $i=0,\dots,k-1$, and
$(p_{i},v_{i})\in\Delta_{j}\subseteq c_{O}$. Therefore,
$c_{O}(h(p_{i}))=v_{i+1}=e(v_{i})=e(c_{O}(p_{i}))$.

2) For all pairs
$(\alpha_{p_{t}}(i),\beta_{v_{t}}(i))\in\Sigma\setminus\\{(p_{t},v_{t})\mid
t=0,1,\dots,k\\}$, we have $h(\alpha_{p_{t}}(i))=p_{t}$ and
$e(\beta_{v_{t}}(i))=v_{t}$, and $(p_{t},v_{t})\in\Sigma$. Therefore,
$c_{O}(h(\alpha_{p_{t}}(i)))=c_{O}(p_{t})=v_{t}=e(\beta_{v_{t}}(i))=e(c_{O}(\alpha_{p_{t}}(i)))$.

Now, $\Delta_{j}\subseteq\Delta_{j+1}$ for all $j$. Set
$\Delta=\cup_{j}^{\infty}\Delta_{j}$. Finally, define $c_{O}\colon V\to V_{n}$
by $c_{O}(u)=v$ if and only if $(u,v)\in\Delta$.

That $c_{O}$ is injective is clear from its definition. ∎

We shall now prove that any connected subgraph of $G_{h}$ can be mapped into
$G_{e}$. For the set $C$ of cyclic numbers in $e$ as defined in the above,
define the subsets

$C_{k}=\\{n\mid n\text{ is the smallest number occurring in a }k\text{-cycle
of }G_{e}\\}.$

We begin with subgraphs having a cycle.

######  Lemma 8.

Let $h\colon\mathbb{N}\to\mathbb{N}$ be a function and let $G=(V,E)$ be a
connected subgraph of $G_{h}^{n}$ of case 1 of Lemma 6 with a cycle of length
$k$. Then for all numbers $i\in C_{k}$ with $G_{e}^{i}=(W,F)$, there exists an
injective function $c_{i}\colon V\to W$ such that $c_{i}(h(j))=e(c_{i}(j))$
for all $j\in V$

###### Proof.

Assume that the cycle in $G_{h}^{n}$ is $C_{m_{1}}^{h}$:
$h(m_{1})=m_{2},\dots,h(m_{k})=m_{1}$, and let $O_{h}^{m_{j}}$ be the function
trees rooted at $m_{j}$ for $j=0,1,\dots,k$.

Let $i\in C_{k}$, and denote $C_{e}^{i}=\\{t_{1},\dots,t_{k}\\}$ where
$e(t_{j})=t_{j+1}$ for $j=1,\dots,k_{1}$ and $e(t_{k})=t_{1}$. We may assume
$i=t_{1}$.

We define $c_{i}$ again as a subset of $V\times W$ as follows: first

$I=\\{(m_{j},t_{j})\mid j=1,\dots,k\\}.$

Then for each function tree $O_{h}^{m_{j}}$ in $G$, let $c_{O_{h}^{m_{j}}}$ be
the mapping given in Lemma 7 from $O_{h}^{m_{j}}$ to $G_{(e,T_{t_{j}})}$.
Finally, set

$c_{i}=I\cup_{j=1}^{k}c_{O_{h}^{m_{j}}}$

Now each $c_{O_{h}^{m_{j}}}$ maps correctly by Lemma 7, and for $m_{j}\in
C_{m_{1}}^{h}$, if $j=1,\dots,k-1$, then
$c_{i}(h(m_{j}))=c_{i}(m_{j+1})=t_{j+1}=e(t_{j})=e(c_{i}(t_{j}))$, and for
$m_{k}$, we have
$c_{i}(h(m_{k}))=c_{i}(m_{1})=t_{1}=e(t_{k})=e(c_{i}(t_{k}))$.

This proves the claim. ∎

######  Lemma 9.

Let $h\colon\mathbb{N}\to\mathbb{N}$ be a function and $G_{h}^{n}=(V,E)$ as in
the case 2 of Lemma 6. Then for all numbers $i=2^{m}$ for odd $m$ with
$G_{e}^{i}=(W,F)$, there exists an injective function $c_{i}\colon V\to W$
such that $c_{i}(h(j))=e(c_{i}(j))$ for all $j\in V$.

###### Proof.

Now, the sequence $(h^{k}(n))_{k=0}^{\infty}$ is not ultimately periodic. We
define the mapping $c_{i}$ again as a subset of $V\times W$, by defining sets
$I_{k}$ such that $c_{i}=\cup_{k=0}^{\infty}I_{k}$.

First, let

$I_{0}=\\{(h^{k}(n),2^{2^{k}m})\mid k=0,1,\ldots\\}\cup c_{O_{n}^{h}}$

where $c_{O_{n}^{h}}$ is the mapping of Lemma 7 from $O_{n}^{h}$ into
$G_{(e,T_{i})}$. In other words, $I_{0}$ defines $c_{i}$ for the predecessors
of $n$ (i.e., for all vertices in $h^{-}(n)$), for $n$ and for all descendants
of $n$. Indeed, $I_{0}$ maps the predecessors and descendant of $n$ correctly
by Lemma 7 and the fact that
$I_{0}(h^{k}(n))=2^{2^{k}m}=e(2^{2^{k-1}m})=e(I_{0}(h^{k-1}(n))$ for all
$k=1,2,\ldots$.

What are left are the function trees sequences of the descendants $u=h^{k}(n)$
of $n$. Assume $u=h^{k}(n)$ with $k\geq 1$. Let

$Y_{u}=h^{-}(u)\setminus\left(\\{h^{k-1}(n)\\}\cup h^{-}(h^{k-1}(n))\right).$

So $Y_{n}$ consist of all predecessors of $u=h^{k}(n)$ except the vertex
$h^{k-1}(n)$ and its predecessors.

We define $I_{k}$, for $k=1,\dots$, so that $\cup_{j=0}^{k-1}I_{j}$ already
defines images for vertices in
$h^{-}(h^{k-1}(n))\cup\\{h^{k-1}(n)\\}=h^{-}(u)\setminus Y_{u}$, and $I_{k}$
defines the images for $Y_{u}$.

Indeed, let $u=h^{k}(n)$. Using the property 9(b) of $e$, we set $I_{k}$ to be
the mapping $c_{G_{(h,Y_{u})}}$ of Lemma 7 from function tree $G_{(h,Y_{u})}$
into $G_{(e,T_{2^{2^{k}m}})}$.

Let $c_{i}=\cup_{k=0}^{\infty}I_{k}$. As all $v\in V$ are either in
$O_{n}^{h}$ or in $Y_{u}$ for some $u$ or $v=h^{k}(n)$, and by Lemma 7,
$c_{i}$ maps correctly in $O_{n}^{h}$ and in the sets $Y_{u}$, we have an
injective mapping fulfilling the claim. ∎

We are ready to prove our main theorem.

######  Theorem 2.

Let $h\colon\mathbb{N}\to\mathbb{N}$ be a function. There exists an injective
function $c_{h}\colon\mathbb{N}\to\mathbb{N}$ such that
$c_{h}(h(n))=e(c_{h}(n))$.

###### Proof.

Let $G_{h}=(\mathbb{N},E)$ be the graph of $h$. In $G_{h}$, there are
enumerably many connected subgraphs. Let $\pi$ a enumeration function of these
subgraphs. Now, all $i=1,2,\dots$, if $\pi(i)$ is

  1. 1.

a subgraph of type 1 in Lemma 7 with a cycle of length $k$, let $I_{i}$ be the
mapping $c_{t}$ given in Lemma 8 to the $i$th cycle of length of length $k$
(in other words, $t$ is the $i$’th number in $C_{k}$), or

  2. 2.

a subgraph of type 2 in Lemma 7, let $I_{i}$ be the mapping $c_{t}$ given in
Lemma 9, where $t=2^{m}$ and $m$ this the $i$th odd number (so $m=2i-1$).

Set $c_{h}=\cup_{i=1}^{\infty}I_{k}$. The claim now follows from Lemmata 8 and
9.

∎

### Acknowledgements.

The authors are grateful to Joseph Almog for his help and discussions on the
topic. Most grateful we are to the referees of the preliminary version of this
paper who helped us to realize (together with Almog) what we actually had
proved.

## References

  * [1]
  * [2] Paul B. Larson, Arnold W. Miller, Juris Steprāns, and William A. R. Weiss, Universal functions, Fundam. Math., 227: 3 (2014), 197–245.
  * [3] R. Rado: Universal graphs and universal functions, Acta Arith. 9 (1964), 331–340.
  * [4] W. Sierpiński: Sur une function universelle de deux variables reelles, Bull Acad Sci Cracovie A (1936), 8–12.
  * [5] W. H. Woodin: _A Potential Subtlety Concerning the Distinction between Determinism and Nondeterminism_ , Infinity: New Research Frontiers (M. Heller, W. H. Woodin, editors), Cambridge University Press, New York, 2011, pp. 119–129.