# Robustness and complexity of directed and weighted metabolic hypergraphs

Pietro Traversa  Institute for Biocomputation and Physics of Complex Systems
(BIFI), University of Zaragoza, 50018 Zaragoza, Spain  Department of
Theoretical Physics, University of Zaragoza, 50018 Zaragoza, Spain  CENTAI
Institute, Turin, Italy  Guilherme Ferraz de Arruda  CENTAI Institute, Turin,
Italy  Alexei Vazquez  Nodes & Links Ltd, Salisbury House, Station Road,
Cambridge, CB1 2LA, UK  Yamir Moreno  Institute for Biocomputation and Physics
of Complex Systems (BIFI), University of Zaragoza, 50018 Zaragoza, Spain
Department of Theoretical Physics, University of Zaragoza, 50018 Zaragoza,
Spain  CENTAI Institute, Turin, Italy

###### Abstract

Metabolic networks are probably among the most challenging and important
biological networks. Their study provides insight into how biological pathways
work and how robust a specific organism is against an environment or therapy.
Here we propose a directed hypergraph with edge-dependent vertex weight as a
novel framework to represent metabolic networks. This hypergraph-based
representation captures higher-order interactions among metabolites and
reactions, as well as the directionalities of reactions and stoichiometric
weights, preserving all essential information. Within this framework, we
propose the communicability and the search information as metrics to quantify
the robustness and complexity of directed hypergraphs. We explore the
implications of network directionality on these measures and illustrate a
practical example by applying them to the small-scale e_coli_core model.
Additionally, we compare the robustness and the complexity of 30 different
models of metabolism, connecting structural and biological properties. Our
findings show that antibiotic resistance is associated with high structural
robustness, while the complexity can distinguish between eukaryotic and
prokaryotic organisms.

##  I Introduction

A metabolic network [1, 2, 3, 4, 5] is a highly organized system of chemical
reactions that occur in living organisms to sustain life and regulate cellular
processes. Metabolic networks are incredibly complex because of the large
number of reactions and the intricate web of interactions between molecules.
Chemical reactions take some metabolites, usually called reactants or
substrates, and turn them into products, which can be used by other reactions.
This complexity allows organisms to perform various functions and respond to
various challenges, but it makes understanding them much more challenging. The
key functions of metabolism are the production of energy, the conversion of
food into building blocks of proteins, lipids, nucleic acids, and
carbohydrates, and the elimination of metabolic wastes.

Given the network structure of metabolism, many researchers have attempted to
characterize and understand it through network theory. It has been shown that
graphs whose nodes are metabolites and are connected by chemical reactions
have a scale-free distribution [3] and have been described as “among the most
challenging biological networks and, arguably, the ones with most potential
for immediate applicability” [6]. Other attempts have tried to give more
concrete answers by focusing on graphs with reactions as nodes or bipartite
graphs but missing a fundamental aspect of chemical reactions. To take place,
they require a collective interaction of reactants to create multiple
products. Hence, these are high-order interactions that the graphs cannot
fully capture. As network theory has advanced, new structures have been
devised that can capture high-order interactions. These structures called
hypergraphs have been very successful in fields such as social sciences [7, 8,
9, 10, 11, 12, 13, 14, 15, 16, 17], epidemiology [18, 12, 15, 19, 20, 21],
biology [22, 23, 24, 25, 26, 27, 28], etc. Recently, Mulas et al. [29, 30]
applied hypergraphs to chemical networks trying to capture the high-order
nature of chemical reactions. In this paper, we take the concept of chemical
hypergraphs and apply it to metabolic networks. In addition, we take it a step
further by showing how including weights in the treatment allows no biological
or structural information to be lost. Therefore, we argue that metabolic
hypergraphs are the right framework to address and understand metabolism,
allowing a bridge between biology and network theory.

This article aims to lay the foundation for a theory of metabolic networks
based on hypergraphs. We describe the method by which each metabolic network
can be represented as a hypergraph and introduce two applicable measures,
namely, communicability and search information.

The work is organized as follows. In section II we give the mathematical
definitions regarding metabolic hypergraphs. We also comment on previous
studies in the field of metabolic networks and on how they can be viewed as a
simplification of the metabolic hypergraph we propose here. In section III we
propose a generalization of the communicability and search information to
hypergraphs. We keep this section general enough so that these measures can be
easily applied to any hypergraph, directed or undirected, weighted or not. We
use metabolic hypergraphs as an example and we report the results in section
IV. We conclude by commenting on the possibility that this framework offers to
motivate further research in this area.

##  II Metabolic networks as hypergraph

In this section, we give a formal definition of metabolic hypergraphs and
introduce the notation that is used to characterize them.

###  II.1 Hypergraphs definition

A hypergraph $H=\left\\{V,E\right\\}$ is a set of vertices or nodes $v\in V$
and hyperedges $e\in E$. Each hyperedge is a subset of $V$ such that different
nodes interact with each other if and only if they belong to the same
hyperedge. Thus, unlike traditional graphs, where edges connect pairs of
nodes, hyperedges represent interactions involving multiple nodes. If the
dimension $|e|$ of the hyperedges is $2$, then the hypergraph is equivalent to
a conventional graph. The total number of vertices is denoted as $N=|V|$ and
the number of hyperedges as $M=|E|$.

To interpret metabolic networks as hypergraphs, we first need to define a
special type of hypergraph introduced by Chitra et al. [31]. A hypergraph with
edge-dependent vertex weights (EDVW) $H=\left\\{V,E,W,\Gamma\right\\}$ is a
set of vertices or nodes $v\in V$, hyperedges $e\in E$, edge weights $w(e)$
and edge-dependent vertex weight $\gamma_{e}(v)$. If
$\gamma_{e}(v)=\gamma(v)\;\forall\,e\in E$, then the hypergraph is said to
have edge-independent vertex weight. All the weights are assumed to be
positive. These types of weights are a unique property of some higher-order
systems and are crucial to encode in the hypergraph all the information
contained in metabolic networks.

In this paper, we deal with directed hypergraphs, which are an extension of
directed graphs. In a directed hypergraph, each hyperedge is associated with a
direction similar to the direction of an arrow connecting two vertices in a
directed graph. In this context, a hyperedge $e_{j}$ is divided into a head
set $H(e_{j})$ and a tail set $T(e_{j})$. Similarly to the arrow, the
direction goes from the tail to the head set, with the difference that the
directed hyperedge is connecting multiple vertices. A vertex can belong solely
to either the head or the tail of a hyperedge, but not both. Unless explicitly
stated otherwise, any hypergraph in this paper is considered to be directed.

Additionally, we define $k_{v}^{out}$, the out-degree of a vertex $v\in V$, as
the number of hyperedge-tails that include $v$. Similarly, $k_{v}^{in}$
denotes the in-degree of a vertex $v\in V$, the number of hyperedge-heads in
which $v$ is contained. We also use $|H(e)|$ and $|T(e)|$ to represent the
number of vertices belonging to $H(e)$ and $T(e)$ respectively.

Given a directed hypergraph H = $\left\\{V,E\right\\}$ of $N$ vertices and $M$
hyperedges, the incidence matrix is the matrix
$\mathcal{I}\in\mathbb{R}^{N\times M}$ such that:

$\mathcal{I}_{ij}=\begin{cases}1&\text{ if $v_{i}\in H(e_{j})$}\\\ -1&\text{
if $v_{i}\in T(e_{j})$}\\\ 0&\text{ if $v_{i}\not\in e_{j}$}\end{cases},$ (1)

where $H(e_{j})$ and $T(e_{j})$ are, respectively, the head and the tail of
the hyperedges $e_{j}$. We can rewrite the incidence matrix as

$\mathcal{I}=\mathcal{I}_{H}-\mathcal{I}_{T},$ (2)

where we separated the contributions coming from the head and the tail of the
hyperedges in order to work with positive signed matrices.

###  II.2 Metabolic hypergraphs

In this article, we focus on metabolic networks. A metabolic network [2] is a
set of biological processes that determines the properties of the cell.
Several reactions are involved in metabolism, grouped into various metabolic
pathways. A metabolic pathway is an ordered chain of reactions in which
metabolites are converted into other metabolites or energy. For example, the
glycolysis pathway is the set of reactions involved in the transformation of
one molecule of glucose into two molecules of pyruvate, producing energy.
Metabolic networks are among the most challenging and highest potential
biological networks [6, 3]. The way to represent a metabolic network on a
graph is not unique, and several approaches have been tried. One possible way
is to consider metabolites (or reactions) as nodes and connect them if and
only if they share a reaction (or metabolite). The resulting graph is
undirected, and this may change the structural properties of the network in an
undesirable way. In [32], the authors analyze the same dataset that we analyze
for E.Coli and propose a directed graph with reactions as nodes that take into
account the directionality of the reactions, highlighting the difference with
the undirected counterparts.

Figure 1: An example of a metabolic network mapped into a hypergraph with
edge-dependent vertex weight. In a), we present a small network composed of
three reactions and five metabolites. The first reaction $r_{1}$ is reversible
and is represented with the double arrow. In b), we show the corresponding
stoichiometry matrix. Reactants are negative and products are positive. Note
that we need to split the reversible reaction into two irreversible reactions
$r_{1}^{+}$ and $r_{1}^{-}$ to write it in matrix form. This stoichiometry
matrix is the weighted incidence matrix of the hypergraph with edge-dependent
vertex weights shown in c). For the sake of visualization, only the hyperedge
$r_{1}^{+}$ is shown. The hyperedge $r_{1}^{-}$ is just the same but with the
opposite sign. Note that weights are both positive and negative, meaning that
the hypergraph is directed. Indeed, we separate the head and tail of each
hyperedge with a dashed line.

However, reactions are intrinsically higher-order interactions since they can
occur only when all reactants are present. In Fig. 1, we illustrate the way to
map a chemical reaction network into a hypergraph. The resulting hypergraph is
a directed hypergraph with edge-dependent vertex weight, which we will refer
to as metabolic hypergraph for brevity. More formally, we define a metabolic
hypergraph as a 3-tuple $H=\left\\{V,E,\mathcal{S}\right\\}$, where
$V=\\{v_{1},v_{2},\dots v_{N}\\}$ is a set of N metabolites (vertices), and E
is a set of oriented reactions (hyperedges). Each $e\in E$ is a pair
$(T(e),H(e))$, the tail and the head of the hyperedge which corresponds
respectively to the inputs and outputs of the reaction. Note that $T(e)$ or
$H(e)$ can also be empty sets. This is the case for external reactions that
introduce inside the cell the ingested metabolites (the tail is an empty set),
and external reactions that secrete metabolites (the head is an empty set). We
also call the former source reactions and the latter sink reactions, and their
effect on the measurements is discussed in more detail in section III.
$\mathcal{S}$ is the stoichiometry matrix associated with the chemical network
and it represents the EDVW of the hypergraph. Indeed, one can notice that $S$
can be rewritten using the EDVW matrix $\Gamma$ as
$\mathcal{S}=\Gamma\circ\mathcal{I}$, where $\mathcal{I}$ is the directed
incidence matrix and “$\circ$” is the element-wise matrix product.

###  II.3 Literature background

There are different techniques to study metabolic networks. One popular method
is using stochastic chemical kinetics [33], but this requires the notion of
the kinetic rates constant, the rates at which metabolites are consumed per
reaction, which are usually not available [34]. What instead is generally
known are the reactions, the stoichiometry coefficient, and the structure of
the metabolic network. Thus, several graph representations of metabolic
networks have been tried. The most common one is the reaction adjacency matrix
(RAG) defined as $A^{RAG}=\hat{\mathcal{S}}^{T}\hat{\mathcal{S}}$ [32], where
$\hat{\mathcal{S}}$ is the boolean version of the stoichiometry matrix. The
biggest limitation of this model is that is undirected, while we know that the
direction of reactions is chemically really important. A big improvement was
proposed in [32] where the authors proposed a flux-dependent graph model, that
accounts suitably for the directness of the reactions. However, graph
representations of these systems are still missing a crucial point, which is
the fact that reactions are higher-order object, that involves the
interactions of all input metabolites to produce output metabolites.
Therefore, hyperedges are the natural mathematical object to encode reactions.
Mulas et al. [30] already took a step in this direction by defining a Laplace
operator for chemical hypergraphs. The last step we make is to incorporate
into the hypergraph model the weights associated with metabolites and
reactions, using a similar framework to the EDVW defined in [31]. This last
modification to the model is crucial to include biological and chemical
constraints into the model.

The great advantage of the metabolic hypergraph framework we propose is that
it captures all the physical properties that a metabolic network displays: the
directness of reactions, the higher-order interactions, and the chemical
properties like mass conservation, thanks to the inclusion of weights. This
framework represents a link between network theory and biology.

We remark that the previous graph representation of metabolic networks can be
seen as a pairwise projection of a metabolic hypergraph. For example, the RAG
is an undirected projection of the hypergraph as in [35] and the flux-
dependent graph [32] is similar to the normalized adjacency matrix defined in
[36] but extended to directed and weighted hypergraphs. Projections are a
pairwise simplification and can perform well depending on the task, but they
don’t contain all the information.

###  II.4 Dataset

In our experiments, the metabolic hypergraphs are taken from the BiGG Database
[37]. We analyze 30 different models, with an increasing number of nodes
describing different organisms (see Table 1 in the Appendix for the exact
number of nodes and reactions of each BiGG model). We chose the metabolic
networks in order to have a reasonable variety of organisms, and we avoided
very large networks because of the computational costs. The majority of the
data is composed of bacteria that can be divided into classes like antibiotic-
resistant, aerobic or anaerobic, Gram-positive or Gram-negative. The other
organisms are Eukaryotes and one in the Archaea domain. All data are publicly
available on the BiGG models web page [38] in different formats. In this
analysis, the _.json_ format is used. The data contain information on
metabolites, reactions, and genes. Metabolites are identified by a Bigg id,
consisting of an abbreviation defining their type, for example, “h” for
hydrogen and “ATP” for the adenosine triphosphate, and a subscript indicating
the compartment to which they belong. Regarding the reactions, in addition to
their IDs, the metabolites belonging to them are given, with their respective
stoichiometric coefficients. We work in the convention in which a metabolite
with a positive stoichiometric coefficient is a product, otherwise, it is a
reactant. In the BiGG dataset, the direction of the reactions is also
determined by the parameters “lower_bound” and “upper_bound.” These parameters
are associated with each reaction and correspond to the maximal flux of
metabolites that can flow through. A value of lower_bound $=0$ and upper_bound
$>0$ means that the reaction is annotated correctly, following the convention.
On the contrary, if lower_bound $<0$ and upper_bound $=0$, the reactions are
written with inverted orientations. These two parameters combined also
determine if a reaction is reversible or not. If a reaction is reversible,
both the direct and inverse reactions are present and will be characterized by
a lower_bound $<0$ and upper_bound $>0$. We recall that we treat reversible
reactions as two distinct hyperedges, see Fig. 1 for a visual example. It is
important to notice that few reactions have lower_bound $=0$ and upper_bound
$=0$. In practice, this implies that no flux of metabolites can flow through,
so those reactions are discarded.

Lastly, we highlight that some hyperedges may have an empty tail or head.
These hyperedges correspond to reactions involved in the transportation of
metabolites from the outside of the cell to the inside or vice-versa. For this
reason, sometimes they may represent sinks and sources in the hypergraph. By
source, we mean a node or hyperedge from which you can start and leave but
never go back, while a sink is a trapping node or hyperedge that if it is
reached, it is impossible to leave.

##  III Measurements

In this section, we define two measures of the chemical hypergraph based on
the notion of paths or walks on hypergraphs. A _walk_ of length $l$ from node
$v_{0}$ to node $v_{l}$ is defined as a sequence of alternating nodes and
hyperedges $\left(v_{0},e_{1},v_{1},e_{2},v_{2},...e_{l},v_{l}\right)$. We
also define the _dual walk_ form hyperedge $e_{0}$ to hyperedge $e_{l}$ of
length $l$ as the alternating sequence of alternating nodes and hyperedges
$\left(e_{0},v_{1},e_{1},v_{2},e_{2},...v_{l},e_{l}\right)$. We are interested
in both metabolites and reactions, which is why it is useful also to consider
the dual walk.

###  III.1 Hypergraph communicability

We are usually interested in understanding how paths are distributed because
that is how information and interactions spread. In social systems, for
example, the more the paths connecting two nodes, the easier is for
information to spread from one another. Also, if one path of connection fails,
the information can still be spread through other paths, even if they are
longer than the path that failed. For this reason, the notion of paths and
communication between nodes can also be related to the robustness of the
network. However, having a robust network is not always positive. The same
reasoning about the spreading of information applies to the spreading of
viruses. If a network is robust, is way more difficult to design containment
strategies for the virus, since shutting down a connection might not be enough
because of the presence of alternative paths. A way to measure how nodes
communicate within a network is called communicability and we extend this
definition to hypergraphs.

The communicability [39, 40] between two pairs of node $p$ and $q$ is defined
as the weighted sum of all walks starting from node $p$ and ending at node
$q$, as in

$G_{pq}=\sum_{k=0}^{\infty}c_{k}n_{pq}^{k},$ (3)

where $n_{pq}^{k}$ is the number of walks from $p$ to $q$ and $c_{k}$ is the
penalization for long paths. The most common choice is $c_{k}=\frac{1}{k!}$ so
that you recover an exponential expansion. For a graph, $n_{pq}^{k}$ can be
easily found by taking the k-power of the adjacency matrix, $(A^{k})_{pq}$.
Hypergraphs don’t have a unique definition of adjacency matrix, we thus have
to use the definition of walk given above. The vertex-to-vertex
communicability for a hypergraph with incidence matrix $\mathcal{I}$ is
defined as

$G_{pq}^{V}=\sum_{k=0}^{\infty}\frac{\left((\mathcal{I}_{T}\mathcal{I}_{H}^{t})^{k}\right)_{pq}}{k!},$
(4)

or in matrix form

$G^{V}=e^{\mathcal{I}_{T}\mathcal{I}_{H}^{t}},$ (5)

where $t$ indicates the transpose of the matrix. In metabolic hypergraphs, we
are also interested in how reactions communicate with each other. For this
reason, we define the hyperedge-to-hyperedge communicability based on the
notion of dual path,

$G_{pq}^{E}=\sum_{k=0}^{\infty}\frac{\left((\mathcal{I}_{H}^{t}\mathcal{I}_{T})^{k}\right)_{pq}}{k!},$
(6)

or in matrix form

$G^{E}=e^{\mathcal{I}_{H}^{t}\mathcal{I}_{T}}.$ (7)

The Estrada index [39, 41] of a hypergraph $H$ is generalized as

$\begin{split}EE^{V}(H)=\text{Trace}\left(G^{V}\right),\\\
EE^{E}(H)=\text{Trace}\left(G^{E}\right).\end{split}$ (8)

One can notice that the matrices $\mathcal{I}_{T}\mathcal{I}_{H}^{t}$ and
$\mathcal{I}_{H}^{t}\mathcal{I}_{T}$ have the same spectrum except for the
number of zero eigenvalues because of the difference in size. This means that
for $M>N$ for example (which is usually the case in metabolic hypergraphs),
then the Estrada index defined on nodes and the one defined on the hyperedges
are related by $EE^{E}(H)=EE^{V}(H)+(M-N)$. We use the Estrada index defined
on the nodes to measure the hypergraph robustness, also known as natural
connectivity, as

$\bar{\lambda}^{V}=\log{\left(\frac{EE(H)^{V}}{N}\right)}.$ (9)

The same definition holds for $\bar{\lambda}^{E}$ with the proper
normalization.

Since computing the exponential of very large matrices might be a difficult
numerical task, we use an approximation for the calculation of the robustness
based on eigenvalue decomposition. For simplicity, let us call
$A^{V}=\mathcal{I}_{T}\mathcal{I}_{H}^{t}$ (the same reasoning holds for
$A^{E}=\mathcal{I}_{H}^{t}\mathcal{I}_{T}^{t}$) and order the spectrum of
$A^{V}$ in such a way that
$\lambda_{1}>\lambda_{2}>\lambda_{3}>...\lambda_{N}$. Then the natural
connectivity or robustness of the hypergraph becomes

$\displaystyle\bar{\lambda}^{V}$
$\displaystyle=\log\left(\sum_{i=1}^{N}e^{\lambda_{i}}\right)-\log(N)=$
$\displaystyle=\log\left[e^{\lambda_{1}}\left(1+\sum_{i=2}^{N}e^{\lambda_{i}-\lambda_{1}}\right)\right]-\log(N)=$
$\displaystyle=\lambda_{1}+\log\left(1+\sum_{i=2}^{N}e^{\lambda_{i}-\lambda_{1}}\right)-\log(N)=$
$\displaystyle=\lambda_{1}-\log(N)+\mathcal{O}\left(e^{-(\lambda_{1}-\lambda_{2})}\right).$

Thus if the spectral gap is large enough, the natural connectivity is
dominated by the largest eigenvalue. Since the correction is exponential, this
approximation is usually quite good. As a consequence of the common spectrum
of $\mathcal{I}_{H}^{t}\mathcal{I}_{T}$ and
$\mathcal{I}_{T}\mathcal{I}_{H}^{t}$, the difference in robustness is
approximately $\bar{\lambda}^{V}-\bar{\lambda}^{E}\approx\log(\frac{M}{N})$,
which is usually quite small.

This generalization of communicability applies also to undirected hypergraphs
by substituting $I_{H}$ and $I_{T}$ with the undirected incidence matrix $I$.

###  III.2 Hypergraph search information

_Rosvall et al._ [42, 43] introduced the concept of search information, as a
measure of complexity in urban graphs. The idea is to measure the number of
binary questions one has to make in order to locate the shortest path
connecting a node $s$ to a node $t$. As a consequence, this measure is based
on walks like the communicability, but with the crucial difference that it
considers only the shortest paths. This allows us to link the search
information with the notion of complexity. While alternative pathways tend to
make the network more robust, they also make the probability of finding the
shortest path decrease and the complexity increases. This trade-off is the
reason that motivated us to consider communicability and search information
together.

In [42], the search information is defined as a matrix $S$ with entries

$S(i,j)^{V}=-\log_{2}\left(\sum_{\left\\{p(i,j)\right\\}}P\left(p(i,j)\right)\right),$
(10)

where $\left\\{p(v_{i},v_{j})\right\\}$ is the set of all shortest paths from
node $v_{i}$ to node $v_{j}$.

The original definition was made for undirected and unweighted ordinary
graphs, so a very different structure from directed hypergraphs with edge-
dependent vertex weight but the meaning remains the same. What changes, is the
probability of following the shortest path. The probability of making a step
is proportional to the stoichiometric coefficients of the starting and
arriving node, similar to what has been done in the normalized flow graph in
[32]. The probability of taking a step in a directed hypergraph with EDVW is

$\begin{split}P(v\xrightarrow{}e)=\frac{\gamma_{e}(v)}{\sum_{h}\gamma_{h}(v)},\\\
P(e\xrightarrow{}v)=\frac{\gamma_{e}(v)}{\sum_{n}\gamma_{e}(n)}.\end{split}$
(11)

The probability of following a path is derived by multiplication of the
single-step probability,

$P(v_{0},v_{l})=P(v_{0}\xrightarrow{}e_{1})P(e_{1}\xrightarrow{}v_{1})\dots
P(e_{l}\xrightarrow{}v_{l}).$ (12)

It is important to note that the search information might be ill-defined if
the hypergraph has sources or sinks. For example, by definition, there are no
paths from a sink node $v_{\text{sink}}$ to any other nodes $v$, making the
definition of $S(v_{\text{sink}},v)$ unclear in this case. What we do to solve
the problem is to set $S(v_{\text{sink}},v)=0$ and then not count sink and
source nodes when computing the average. With this convention, the access,
hide, and average search information are defined as

$\begin{split}&A^{V}(s)=\frac{1}{N-N_{\text{sources}}}\sum_{t}S^{V}(s,t)\\\
&H^{V}(t)=\frac{1}{N-N_{\text{sinks}}}\sum_{s}S^{V}(s,t)\\\
&\bar{S}^{V}=\frac{1}{(N-N_{\text{sinks})}(N-N_{\text{sources}})}\sum_{s,t}S^{V}(s,t).\\\
\end{split}$ (13)

As a consequence, the access information of a sink and the hide information of
a source will be set to zero. Following [42], we introduce an additional
normalization factor $\ln_{2}M$ to take into account size effects. We denote
the normalized average search information as
$\sigma^{V}=\frac{\bar{S}^{V}}{\log_{2}N}$. The interpretation of these
measures is very intuitive. The access information measures how easy it is to
reach the other nodes in the network, while the hide information estimates how
hidden a node is. Consequently, very central and connected nodes in the
hypergraph have low hide information because there are a lot of paths leading
to them but have relatively high access information because there are also
many paths departing from such nodes.

Figure 2: Access vs. hide information for reactions a) and metabolites b).
Reactions are colored differently according to the pathway they belong to. Not
that the $y$ axis is cut for visualization purposes. Metabolites are divided
into compartments, $c$ stands for cytosol compartment, and $e$ for
extracellular space.

##  IV Results and Discussion

In this section, we apply the previously defined metrics to a range of
metabolic hypergraphs. As illustrated in Fig. 1, these hypergraphs were
constructed by starting with metabolic networks obtained from the BiGG Dataset
[37]. The metabolic networks were selected to have a reasonable variety of
organisms. The primary goal of this section is to demonstrate the practical
application of our framework and the defined measurements.

###  IV.1 Exploring the E. coli Core Model: A Practical Example

To provide a tangible illustration of our methodology, we focus on the BiGG
model known as e_coli_core [44]. This model represents a small-scale version
of Escherichia coli str. K-12 substr. MG1655, making it an ideal candidate for
demonstrating the performance of our metrics and understanding their
limitations. Additionally, an Escher map for this model is available online
[45].

In Fig. 2, we show the access vs. hide information for reactions and
metabolites. Regarding the reactions (Fig. 2 a), the measure correctly
identifies the Biomass reaction as a central hub. Reactions are plotted with
different colors based on the biological pathway they belong to. We can
clearly see the behavior of sinks and sources in the reactions belonging to
the extracellular exchange pathway. The pathways don’t tend to separate into
clusters, indicating that they all have a similar complexity. This could be an
effect of the simplicity of this model or could be a property shared by all
organisms. We didn’t investigate further since the scope of this section was
just to provide a practical example, but it could be worth it to explore it in
future work.

Figure 3: Reactions average communicability for the e_coli_core model. A
simplified Escher map is used as a background to help with the visualization.
For a more accurate version of the map, visit [45].

We also comment on the reactions that are ranked the highest by the average
communicability. The average communicability is defined as
$\bar{G}_{e}=\frac{1}{M}\sum_{h\in E}G^{E}_{he}$ and is shown in Fig. 3.
Notably, the Biomass reaction (1-st highest average communicability) and ATP
synthase (2-st highest average communicability) are correctly identified as
central reactions within the metabolism. The Biomass reaction is responsible
for cell growth, while ATP synthase plays a crucial role in ATP synthesis, the
primary energy source for the organism. The production of ATP is mainly due to
the consumption of oxygen that occurs through the reaction CYTBD (cytochrome
oxidase bd – 6-th highest average communicability). When oxygen is
unavailable, Escherichia coli can still survive thanks to the activation of
the anaerobic pathway, which derives energy from the reaction THD2 (NAD(P)
transhydrogenase –3-rd highest average communicability).

Regarding the metabolites (Fig. 2 b), we observe a clear distinction between
those belonging to the cytosol compartment and those located in the
extracellular compartment. As expected, extracellular metabolites tend to
have, on average, higher hide information. It is important to clarify that
metabolites with zero hide information are source nodes and remain initialized
to zero because they are unreachable. However, an instructive observation
could be made on o2_c. As commented in section III, a node with low but non-
zero hide information is expected to be a central hub, but in reality, it has
a very low degree. The explanation for this helps to understand the
implications of network directionality. The node o2_c is only connected to the
core metabolism via the irreversible CYTBD reaction as a substrate.
Consequently, there cannot be any directed path from the core metabolism to
o2_c, only the opposite. We conclude that the node o2_c does not belong to the
largest strongly connected component. In practice, it behaves very similarly
to a source node. Nonetheless, the hide information is not zero because a
pathway originates from the transport of external oxygen to the cytosol. In
contrast, in cyanobacteria, algae, and plants (not investigated here) O2 is
produced via oxygenic photosynthesis. In those organisms, O2 should be part of
the strongly connected component.

###  IV.2 Robustness and complexity across organisms

Our study assesses the robustness and complexity of 30 distinct metabolic
hypergraphs derived from various eukaryotic and prokaryotic organisms.

Figure 4: The robustness measured as the natural connectivity
$\bar{\lambda}^{V}$ of 30 different BiGG models. The organisms resistant to
antibiotics are shown in different colors. The models are ordered in
increasing robustness.

In Fig. 4, we present the computed robustness values for several organisms
arranged in ascending order. The BiGG model associated with the organisms
_Staphylococcus aureus subsp aureus_ [46, 47], _Mycobacterium tuberculosis_
[48, 49], _Acinetobacter baumannii AYE_ [50], and _Salmonella enterica_ [51]
are represented in different color because they are bacteria that have evolved
resistance to antibiotics. Except for the first _Staphylococcus aureus subsp
aureus_ model, antibiotic-resistant bacteria tend to exhibit relatively high
robustness compared to other organisms. We measured the Spearman’s rank
correlation between robustness and antibiotic resistance obtaining a value of
$0.424$, revealing a moderate correlation. Here, the definition of robustness
is based on the network’s resilience to random or targeted node removal. The
concept of natural connectivity quantifies this resilience by counting the
number of closed loops in the network. If there are many alternative paths, it
is less probable that a node removal will disconnect the network. In the
context of biology, antibiotics operate by targeting and inhibiting some
specific reactions, without which the cell dies [1]. Therefore, having a
structurally robust metabolism is advantageous as it allows the organism to
circumvent antibiotic inhibition by utilizing alternative reactions or
pathways. However, this is not the whole picture since many other factors play
a role. For example, bacteria are naturally subjected to random mutations that
may strengthen their response to antibiotics, and this may not necessarily be
reflected in a high structural hypergraph robustness. Conversely, a very
robust metabolic hypergraph, with many alternative paths, may have a few but
very important reactions that are easy to target with antibiotics. Hence, high
structural hypergraph robustness does not guarantee antibiotic resistance.

Figure 5: The complexity measured as the average search information
$\sigma^{V}=\frac{S^{V}}{\log_{2}N}$ of 30 different BiGG models. The models
are ordered in increasing complexity, and the y-axis is zoomed in for
visualization purposes.

The complexity of metabolic networks is expected to be quite similar across
organisms since they share many common reactions and metabolic pathways.
Nevertheless, some differences are expected in the metabolism of aerobic and
anaerobic organisms, as well as between eukaryotes and prokaryotes. Aerobic
and anaerobic organisms should have a different metabolism because of the
different ways they produce energy, while eukaryotes and prokaryotes have
significantly different cell structures. With this in mind, we measure the
average search information of the 30 different metabolic hypergraphs and
report the results in Fig. 5. We notice a clear separation between eukaryotes
and some aerobic organisms, showing a high complexity, and prokaryotes, which
have a lower complexity. A few outliers exist, including _Staphylococcus
aureus subsp aureus N315_ , which exhibits high complexity, potentially due to
unusually large weights associated with certain reactions compared to other
organisms. Setting all the weights to $1$ would indeed lead to a much lower
complexity, ranked slightly below the average, indicating a possible bias. In
addition, one can also notice that the other model for _Staphylococcus_ has a
low complexity. Another outlier is the first model we analyzed for _Homo
sapiens - erythrocytes_ [52] that may be expected to be complex. However, it
is important to note that this model refers just to the erythrocyte metabolism
(blood cells) rather than the entire human metabolisms. Erythrocytes lack
mitochondria and produce ATP through anaerobic glycolysis, so their metabolism
could be closer to that of anaerobic organisms. Conversely, the low complexity
of the aerobic organisms _Acinetobacter baumannii AYE_ , _Pseudomonas putida_
, and _Helicobacter pylori_ is curious, and we don’t have a clear motivation.
Note that a generic human (Homo sapiens) cell has a similar complexity as a
yeast cell (Saccharomyces cerevisiae). That is expected. Eukaryote cells have
similar metabolic pathways. The additional complexity in human metabolism is
due to the multi-cellularity, which is not accounted for in this study.

##  V Conclusion

Metabolic networks are very large and complex systems. For this reason, it is
important to build a framework able to unite biology and network theory. Many
successful studies have represented metabolic networks as graphs with
metabolites as nodes, reactions as nodes, or both. Taking a step further, with
the employment of hypergraphs, we are able to capture what all of these
previous graph representations were missing, the higher-order interactions of
reactions. In this paper, we show how metabolic networks are naturally mapped
into hypergraphs. In particular, the stoichiometry matrix can be viewed as a
weighted incidence matrix of a directed hypergraph with edge-dependent vertex
weight. No information is lost representing metabolic networks as hypergraphs:
the higher-order interactions between metabolites, the directionalities of
reactions, and the stoichiometric weights are all included.

Within this novel framework, we propose two measurements to characterize the
hypergraph’s robustness and complexity. We apply them to directed hypergraphs
with EDVW, but the generalization to undirected and unweighted hypergraphs is
straightforward. This approach allows analysis at the local scale, with the
communicability and the access and hide information, and at the global scale,
with the natural connectivity as a measure of robustness and the average
search information as a measure of complexity. We comment on the complications
introduced by directionality and how they can be reflected in the measures. To
illustrate the practical application of our framework and metrics, we present
an example using the e_coli_core model. This small-scale metabolism
demonstrates how our metrics operate locally and offers valuable insights into
the behavior of metabolic hypergraphs. At the global scale, we compare 30
different BiGG models in robustness and complexity, leading to some
interesting results. We show that the metabolism of organisms that have
evolved resistance to antibiotics is associated with hypergraphs that display
high robustness. Furthermore, we observe that eukaryotic and prokaryotic
organisms have different complexity values.

A possibility for future works could be modifying the definition of the
average search information and the probability of taking a step in the
hypergraph. Here, we consider a walk biased by the stoichiometric weights, but
more options could be explored. One possibility is to define the probabilities
based on the communicability measure or on the rates obtained by flux balance
analysis [53, 32]. Also, we didn’t consider the information regarding genes
that are contained in the BiGG models. Genomics plays a crucial, especially in
resistance to antibiotics, and for this reason, it could be interesting to
integrate it into this framework. Another possibility is to apply our measures
to other contexts, like social or technological hypergraphs.

We believe that this framework represents a promising approach to bridge
network theory and biology. We hope that it may serve as a starting point,
potentially reaching experts in the field who could further refine and utilize
these findings to get more biological insights.

Data availability
All data are publicly available on the BiGG models [38] web page in different
formats. In this analysis, the _.json_ format is used.

Code availability
Custom code that supports the findings of this study is available from the
corresponding author upon request.

###### Acknowledgements.

P.T., G.F.A, and Y.M. acknowledge the financial support of Soremartec S.A. and
Soremartec Italia, Ferrero Group. Y.M. acknowledges partial support from the
Government of Aragon and FEDER funds, Spain through grant E36-20R (FENOL), and
by the EU program Horizon 2020/H2020-SCI-FA-DTS-2020-1 (KATY project, contract
number 101017453). We acknowledge the use of the computational resources of
COSNET Lab at Institute BIFI, funded by Banco Santander (grant Santander‐UZ
2020/0274) and by the Government of Aragón (grant UZ-164255). The funders had
no role in study design, data collection, and analysis, decision to publish,
or preparation of the manuscript.

## References

  * Campbell et al. [2018] N. A. Campbell, L. A. Urry, M. L. Cain, S. A. Wasserman, P. V. Minorsky, and J. B. Reece, _Biology: a global approach_ (Pearson, New York, 2018), eleventh edition, global edition ed., ISBN 9781292170435.
  * Dräger and Planatscher [2013] A. Dräger and H. Planatscher, in _Encyclopedia of Systems Biology_ , edited by W. Dubitzky, O. Wolkenhauer, K.-H. Cho, and H. Yokota (Springer New York, New York, NY, 2013), pp. 1249–1251, ISBN 9781441998620 9781441998637.
  * Ma and Zeng [2003] H. Ma and A.-P. Zeng, Bioinformatics 19, 270 (2003), ISSN 1367-4803.
  * Stitt et al. [2010] M. Stitt, R. Sulpice, and J. Keurentjes, Plant Physiology 152, 428 (2010), ISSN 1532-2548.
  * Renz et al. [2021] A. Renz, R. Mostolizadeh, and A. Dräger, in _Systems Medicine_ , edited by O. Wolkenhauer (Academic Press, Oxford, 2021), pp. 362–371, ISBN 978-0-12-816078-7.
  * Guimerà and Nunes Amaral [2005] R. Guimerà and L. A. Nunes Amaral, Nature 433, 895 (2005), ISSN 0028-0836, 1476-4687.
  * Niu et al. [2017] X. Niu, C. Doyle, G. Korniss, and B. K. Szymanski, Scientific Reports 7, 41750 (2017).
  * Centola et al. [2018] D. Centola, J. Becker, D. Brackbill, and A. Baronchelli, Science 360, 1116 (2018), ISSN 0036-8075.
  * Baronchelli [2018] A. Baronchelli, Royal Society Open Science 5, 172189 (2018).
  * Benson et al. [2018] A. R. Benson, R. Abebe, M. T. Schaub, A. Jadbabaie, and J. Kleinberg, Proceedings of the National Academy of Sciences (2018), ISSN 0027-8424.
  * Iacopini et al. [2019] I. Iacopini, G. Petri, A. Barrat, and V. Latora, Nature Communications 10, 1 (2019).
  * de Arruda et al. [2020] G. F. de Arruda, G. Petri, and Y. Moreno, Physical Review Research 2, 023032 (2020).
  * Landry and Restrepo [2020] N. W. Landry and J. G. Restrepo, Chaos 30, 103117 (2020).
  * Barrat et al. [2021] A. Barrat, G. F. de Arruda, I. Iacopini, and Y. Moreno, _Social contagion on higher-order structures_ (2021), eprint 2103.03709.
  * Ferraz de Arruda et al. [2021] G. Ferraz de Arruda, M. Tizzani, and Y. Moreno, Communications Physics 4, 24 (2021), ISSN 2399-3650.
  * Alvarez-Rodriguez et al. [2021] U. Alvarez-Rodriguez, F. Battiston, G. F. de Arruda, Y. Moreno, M. Perc, and V. Latora, Nature Human Behaviour 5, 586 (2021).
  * Neuhäuser et al. [2020] L. Neuhäuser, A. Mellor, and R. Lambiotte, Phys. Rev. E 101, 032310 (2020).
  * Bodó et al. [2016] Á. Bodó, G. Y. Katona, and P. L. Simon, Bulletin of Mathematical Biology 78, 713 (2016).
  * Ferraz De Arruda et al. [2023] G. Ferraz De Arruda, G. Petri, P. M. Rodriguez, and Y. Moreno, Nature Communications 14, 1375 (2023), ISSN 2041-1723.
  * Higham and de Kergorlay [2021a] D. J. Higham and H.-L. de Kergorlay, _Mean field analysis of hypergraph contagion model_ (2021a), eprint 2108.05451.
  * Higham and de Kergorlay [2021b] D. J. Higham and H.-L. de Kergorlay, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 477, 20210232 (2021b).
  * Stewart et al. [2003] I. Stewart, M. Golubitsky, and M. Pivato, SIAM Journal on Applied Dynamical Systems 2, 609 (2003).
  * Golubitsky et al. [2005] M. Golubitsky, I. Stewart, and A. Török, SIAM Journal on Applied Dynamical Systems 4, 78 (2005).
  * Golubitsky and Stewart [2006] M. Golubitsky and I. Stewart, Bull. Amer. Math. Soc 43, 305 (2006).
  * Yu et al. [2011] S. Yu, H. Yang, H. Nakahara, G. S. Santos, D. Nikolić, and D. Plenz, Journal of Neuroscience 31, 17514 (2011), ISSN 0270-6474.
  * Bairey et al. [2016] E. Bairey, E. D. Kelsic, and R. Kishony, Nature communications 7, 12285 (2016), ISSN 2041-1723.
  * Battiston et al. [2021] F. Battiston, E. Amico, A. Barrat, G. Bianconi, G. Ferraz de Arruda, B. Franceschiello, I. Iacopini, S. Kéfi, V. Latora, Y. Moreno, et al., Nature Physics 17, 1093 (2021).
  * Cervantes-Loreto et al. [2021] A. Cervantes-Loreto, C. A. Ayers, E. K. Dobbs, B. J. Brosi, and D. B. Stouffer, Ecology Letters 24, 1443 (2021).
  * Mulas and Zhang [2021] R. Mulas and D. Zhang, Discrete Mathematics 344, 112372 (2021), ISSN 0012-365X.
  * Jost and Mulas [2019] J. Jost and R. Mulas, Advances in Mathematics 351, 870 (2019), ISSN 0001-8708.
  * Chitra and Raphael [2019] U. Chitra and B. Raphael, in _Proceedings of the 36th International Conference on Machine Learning_ , edited by K. Chaudhuri and R. Salakhutdinov (PMLR, 2019), vol. 97 of _Proceedings of Machine Learning Research_ , pp. 1172–1181.
  * Beguerisse-Díaz et al. [2018] M. Beguerisse-Díaz, G. Bosque, D. Oyarzún, J. Picó, and M. Barahona, npj Systems Biology and Applications 4, 1 (2018), ISSN 2056-7189.
  * Gillespie [1977] D. T. Gillespie, The journal of physical chemistry 81, 2340 (1977).
  * Srinivasan et al. [2015] S. Srinivasan, W. R. Cluett, and R. Mahadevan, Biotechnology journal 10, 1345 (2015).
  * Traversa et al. [2023] P. Traversa, G. F. de Arruda, and Y. Moreno, _From unbiased to maximal entropy random walks on hypergraphs_ (2023), eprint 2306.09499.
  * Banerjee [2021] A. Banerjee, Linear Algebra and its Applications 614, 82 (2021), ISSN 0024-3795, special Issue ILAS 2019.
  * King et al. [2015] Z. A. King, J. Lu, A. Dräger, P. Miller, S. Federowicz, J. A. Lerman, A. Ebrahim, B. Ø. Palsson, and N. E. Lewis, Nucleic Acids Research 44, D515 (2015), ISSN 0305-1048.
  * [38] _Bigg models_ , http://bigg.ucsd.edu/models, accessed: 2022-06-20.
  * Estrada et al. [2012] E. Estrada, N. Hatano, and M. Benzi, Physics Reports 514, 89 (2012), ISSN 0370-1573.
  * Estrada and Hatano [2008] E. Estrada and N. Hatano, Phys. Rev. E 77, 036111 (2008).
  * Estrada [2022] E. Estrada, SeMA Journal 79, 57 (2022).
  * Rosvall et al. [2005] M. Rosvall, A. Trusina, P. Minnhagen, and K. Sneppen, Physical Review Letters 94, 028701 (2005).
  * Sneppen et al. [2005] K. Sneppen, A. Trusina, and M. Rosvall, Europhysics Letters 69, 853 (2005).
  * Orth et al. [2010a] J. D. Orth, R. M. Fleming, and B. Ø. Palsson, EcoSal plus 4, 10 (2010a).
  * [45] _e. coli core fba escher map_ , https://sbrg.github.io/escher-fba/, accessed: 2023-09-21.
  * Becker and Palsson [2005] S. A. Becker and B. Ø. Palsson, BMC Microbiology 5, 8 (2005), ISSN 1471-2180.
  * Seif et al. [2019] Y. Seif, J. M. Monk, N. Mih, H. Tsunemoto, S. Poudel, C. Zuniga, J. Broddrick, K. Zengler, and B. Ø. Palsson, PLOS Computational Biology 15, e1006644 (2019), ISSN 1553-7358.
  * Jamshidi and Palsson [2007] N. Jamshidi and B. Ø. Palsson, BMC Systems Biology 1, 26 (2007), ISSN 1752-0509.
  * Kavvas et al. [2018] E. S. Kavvas, Y. Seif, J. T. Yurkovich, C. Norsigian, S. Poudel, W. W. Greenwald, S. Ghatak, B. Ø. Palsson, and J. M. Monk, BMC Systems Biology 12, 25 (2018), ISSN 1752-0509.
  * Norsigian et al. [2018] C. J. Norsigian, E. Kavvas, Y. Seif, B. Ø. Palsson, and J. M. Monk, Frontiers in Genetics 9, 121 (2018), ISSN 1664-8021.
  * Thiele et al. [2011] I. Thiele, D. R. Hyduke, B. Steeb, G. Fankam, D. K. Allen, S. Bazzani, P. Charusanti, F.-C. Chen, R. M. Fleming, C. A. Hsiung, et al., BMC Systems Biology 5, 8 (2011), ISSN 1752-0509.
  * Bordbar et al. [2011] A. Bordbar, N. Jamshidi, and B. Ø. Palsson, BMC systems biology 5, 1 (2011).
  * Orth et al. [2010b] J. D. Orth, I. Thiele, and B. Ø. Palsson, Nature biotechnology 28, 245 (2010b), ISSN 1087-0156.

##  Appendix A BiGG models

In Table 1, we provide the number of nodes, reactions, and hyperedges for each
analyzed hypergraph. We also report the associated BiGG model ID to facilitate
its identification, reproduction, and further studies. For more information,
see the BiGG models webpage [38].

Organism | BiGG models | Metabolites | Reactions | Hyperedges
---|---|---|---|---
Saccharomyces cerevisiae S288C | iND750 | 1059 | 1266 | 1702
Pseudomonas putida KT2440 | iJN746 | 907 | 1054 | 1415
Plasmodium cynomolgi strain B | iAM_Pc455 | 907 | 1074 | 1563
e_coli_core | e_coli_core | 72 | 95 | 141
Staphylococcus aureus subsp. aureus USA300_TCH1516 | iYS854 | 1335 | 1453 | 1872
Mycobacterium tuberculosis H37Rv-1 | iNJ661 | 825 | 1022 | 1293
Mycobacterium tuberculosis H37Rv-2 | iEK1008 | 998 | 1224 | 1500
Clostridium ljungdahlii DSM 13528 | iHN637 | 698 | 773 | 988
Yersinia pestis CO92 | iPC815 | 1552 | 1960 | 2507
Shigella dysenteriae Sd197 | iSDY_1059 | 1888 | 2529 | 3172
Escherichia coli str. K-12 substr. MG1655 | iJR904 | 761 | 1075 | 1329
Lactococcus lactis subsp. cremoris MG1363 | iNF517 | 650 | 730 | 979
Helicobacter pylori 26695 | iIT341 | 485 | 554 | 737
Homo sapiens | iAB_RBC_283 | 342 | 469 | 645
Homo sapiens2 | iAT_PLT_636 | 738 | 1008 | 1455
Plasmodium falciparum 3D7 | iAM_Pf480 | 909 | 1083 | 1576
Escherichia coli BL21(DE3) | iEC1356_Bl21DE3 | 1918 | 2730 | 3376
Synechococcus elongatus PCC 7942 | iJB785 | 768 | 843 | 1064
Plasmodium berghei | iAM_Pb448 | 903 | 1067 | 1554
Trypanosoma cruzi Dm28c | iIS312 | 606 | 519 | 806
Staphylococcus aureus subsp aureus N315 | iSB619 | 655 | 729 | 945
Thermotoga maritima MSB8 | iLJ478 | 570 | 652 | 852
Methanosarcina barkeri str. Fusaro | iAF692 | 628 | 690 | 900
Clostridioides difficile 630 | iCN900 | 885 | 1222 | 1455
Plasmodium vivax Sal-1 | iAM_Pv461 | 909 | 1078 | 1570
Bacillus subtilis | iYO844 | 990 | 1250 | 1589
Synechocystis sp. PCC 6803 | iJN678 | 795 | 862 | 1086
Geobacter metallireducens GS-15 | iAF987 | 1109 | 1281 | 1642
Acinetobacter baumannii AYE | iCN718 | 888 | 1013 | 1436
Salmonella enterica | STM_v1_0 | 1802 | 2528 | 3133
Table 1: BiGG models and their number of metabolites and reactions. The
directed hypergraph constructed from the model has a number of nodes equal to
the number of metabolites and the number of hyperedges bigger than the number
of reactions because of the presence of reversible reactions.


# On the Euler function of linearly recurrence sequences

Florian Luca111School of Maths, Wits University, Johannesburg, South Africa
and Centro de Ciencias Matemáticas UNAM, Morelia, Mexico email:
<EMAIL_ADDRESS>Makoko Campbell Manape222School of Maths, Wits
University, Johannesburg, South Africa

###### Abstract

In this paper, we show that if $(U_{n})_{n\geq 1}$ is any nondegenerate
linearly recurrent sequence of integers whose general term is up to sign not a
polynomial in $n$, then the inequality $\phi(|U_{n}|)\geq|U_{\phi(n)}|$ holds
for almost all positive integers $n$, where $\phi$ is the Euler function.

AMS Subject Classification: 11B39.

Keywords: Linear recurrence sequences, Euler function

##  1 Introduction

Let $(U_{n})_{n\geq 1}$ be a linearly recurrent sequence of integers. Such a
sequence satisfies a recurrence of the form

$U_{n+k}=a_{1}U_{n+k-1}+\cdots+a_{k}U_{n}\qquad{\text{\rm for~{}all}}\qquad
n\geq 0$

with integers $a_{1},\ldots,a_{k}$, where $U_{0},\ldots,U_{k-1}$ are integers.
Assuming $k$ is minimal, $U_{n}$ can be represented as

$U_{n}=\sum_{i=1}^{s}P_{i}(n)\alpha_{i}^{n},$

where

$f(X)=X^{k}-a_{1}X^{k-1}-\cdots-
a_{k}=\prod_{i=1}^{s}(X-\alpha_{i})^{\sigma_{i}}$

is the characteristic polynomial of $(U_{n})_{n\geq 1}$,
$\alpha_{1},\ldots,\alpha_{s}$ are the distinct roots of $f(X)$ with
multiplicities $\sigma_{1},\ldots,\sigma_{s}$, respectively, and $P_{i}(X)$ is
a polynomial of degree $\sigma_{i}-1$ with coefficients in
${\mathbb{Q}}[\alpha_{i}]$. The sequence is nondegenerate if
$\alpha_{i}/\alpha_{j}$ is not a root of $1$ for any $i\neq j$ in
$\\{1,\ldots,s\\}$. A classical example is the Fibonacci sequence
$(F_{n})_{n\geq 0}$ which has $k=2$, $f(X)=X^{2}-X-1$ and initial terms
$F_{0}=0,~{}F_{1}=1$. Let $\phi(m)$ and $\sigma(m)$ be the Euler function and
sum of divisors function of the positive integer $m$. In [3], the first author
proved that the inequalities

$\phi(F_{n})\geq F_{\phi(n)}\qquad{\text{\rm and}}\qquad\sigma(F_{n})\leq
F_{\sigma(n)}$

hold for all positive integers $n$. It was also remarked that if instead of
considering $(F_{n})_{n\geq 0}$ one considers a Lucas sequence with complex
conjugated roots; that is, a nondegenerate binary recurrent sequence
$(U_{n})_{n\geq 0}$ with $U_{0}=0,~{}U_{1}=1$ and $f(X)$ a quadratic
polynomial with complex conjugated roots, then the inequality

$\phi(|U_{n}|)\geq|U_{\phi(n)}|$

fails infinitely often. In fact, it fails for a positive proportion of prime
numbers $n$. Such questions were recently revisited by other authors (see [2]
and [4], for example).

In this paper, we prove the following theorem.

######  Theorem 1.

Let $(U_{n})_{n\geq 0}$ be a nondegenerate binary recurrent sequence such that
$|U_{n}|$ is not a polynomial in $n$ for all large $n$ and let $x$ be a large
real number. Then the inequality

$\phi(|U_{n}|)\geq|U_{\phi(n)}|$ (1)

fails on a set of positive integers $n\leq x$ of cardinality $O(x/\log x)$. A
similar statement holds for the positive integers $n\leq x$ for which the
inequality

$\sigma(|U_{n}|)\leq|U_{\sigma(n)}|$

fails.

The theorem doesn’t hold for sequences for which $U_{n}$ is either $P(n)$ or
$(-1)^{n}P(n)$, with some polynomial $P(X)\in{\mathbb{Z}}[X]$, whose
characteristic equation is one of $(X-1)^{d}=0$ or $(X+1)^{d}=0$, where $d$ is
the degree of $P(X)$. For example, with $P(X)=X^{2}+1$, we have that if $n$ is
odd then $U_{n}=n^{2}+1$ is even therefore

$\phi(U_{n})\leq\frac{n^{2}+1}{2}.$

On the other hand, for a positive proportion of odd $n$, we have
$\phi(n)>n/{\sqrt{2}}$. For such $n$,

$U_{\phi(n)}=\phi(n)^{2}+1>\frac{n^{2}}{2}+1>\phi(U_{n}).$

As we said above, the bound $O(x/\log x)$ from the statement of Theorem 1 is
close to the truth in some cases like when $(U_{n})_{n\geq 0}$ is a Lucas
sequence with complex conjugated roots. Even more, it is easy to construct
binary recurrent sequences $(U_{n})_{n\geq 1}$ with real roots for which
inequality (1) fails for a number of positive integers $n\leq x$ which is $\gg
x/(\log x)$. For example, let $q_{1}<\cdots<q_{k}$ be odd primes such that

$\sum_{i=1}^{k}\frac{1}{q_{i}}>1.$

Let $a>2$ be a positive integer such that $a\equiv 2\pmod{q_{i}}$ for
$i=1,\ldots,k$. Then $2^{p}-a$ is a multiple of $q_{i}$ for all $i=1,\ldots,k$
whenever $p$ is a prime such that $p\equiv 1\pmod{q_{i}-1}$ for all
$i=1,\ldots,k$. For such primes $p$ which are sufficiently large we have

$\displaystyle\phi(2^{p}-a)$ $\displaystyle=$
$\displaystyle(2^{p}-a)\prod_{q\mid
2^{p}-a}\left(1-\frac{1}{q}\right)\leq(2^{p}-1)\prod_{i=1}^{k}\left(1-\frac{1}{q_{i}}\right)$
$\displaystyle<$
$\displaystyle(2^{p}-a)\exp\left(-\sum_{i=1}^{k}\frac{1}{q_{i}}\right)<\frac{2^{p}-a}{e}$
$\displaystyle<$ $\displaystyle 2^{p-1}-a=2^{\phi(p)}-a.$

Thus, $\phi(U_{n})<U_{\phi(n)}$ for $n=p$ a large prime in the progression
$1\pmod{{\text{\rm lcm}}[q_{1}-1,\ldots,q_{k}-1]}$ and $U_{n}:=2^{n}-a$ which
is the $n$th term of a binary recurrent sequence of characteristic polynomial
$f(X)=X^{2}-3X+2$.

##  2 The proof

Let $p(n)$ be the smallest prime factor of $n$. Let

${\mathcal{A}}_{1}(x)=\\{n\leq x:p(n)>x^{c_{1}}\\}$

where $c_{1}\in(0,1/3)$ is a constant to be determined later. We show first
that ${\mathcal{A}}_{1}(x)$ contains $O(x/\log x)$ positive integers $n\leq x$
as $x\to\infty$. Indeed, putting $y:=x^{c_{1}}$, the set
${\mathcal{A}}_{1}(x)$ coincides with the $n\leq x$ which are coprime to all
the primes $p\leq y$. The number of such is, by the sieve,

$\ll x\prod_{p\leq y}\left(1-\frac{1}{p}\right)\ll\frac{x}{\log
y}\ll\frac{x}{\log x}.$

From now on, let $n\leq x$ not in ${\mathcal{A}}_{1}(x)$. We also assume that
$n\geq x^{1-c_{2}}$, with $c_{2}=c_{1}/2$, since there are only
$O(x^{1-c_{2}})=o(x/\log x)$ as $x\to\infty$ positive integers failing this
last inequality.

For such $n$, the interval $[1,n]$ contains $n/p(n)$ numbers which are not
coprime to $n$, namely all the positive integers which are multiples of
$p(n)$. Thus,

$\phi(n)\leq n-\frac{n}{p(n)}\leq n-\frac{n}{x^{c_{1}}}.$

Let

$U_{n}=\sum_{i=1}^{s}P_{i}(n)\alpha_{i}^{n}.$

We assume that $|\alpha_{1}|\geq|\alpha_{2}|\geq\cdots\geq|\alpha_{s}|$. Let
$D$ be an upper bound for the degrees of the polynomials $P_{i}(X)$ for
$i=1,\ldots,s$. From the theory of ${\mathcal{S}}$-unit equations, we know
that

$|\alpha_{1}|^{n/2}\leq|U_{n}|\ll|\alpha_{1}|^{n}n^{D}$

holds for all $n\geq n_{0}$. Indeed, the upper bound above holds for all $n$
whereas the lower bound holds for all but finitely many $n$. Thus, for $n\geq
n_{0}$, we have that

$\log\log|U_{n}|=\log n+O(1).$

Since $\phi(m)\gg m/\log\log m$ holds for all integers $m\geq 2$, we have that
for $n>n_{0}$, the inequality

$\phi(|U_{n}|)\gg\frac{|U_{n}|}{\log\log|U_{n}|}=\frac{|U_{n}|}{\log n+O(1)}$

holds. Assume now that

$\phi(|U_{n}|)\leq|U_{\phi(n)}|.$

We then get

$\frac{|U_{n}|}{\log
n+O(1)}\ll\phi(|U_{n}|)\leq|U_{\phi(n)}|\leq|\alpha_{1}|^{\phi(n)}\phi(n)^{D}\ll|\alpha_{1}|^{n-n/x^{c_{1}}}n^{D}.$

This gives

$|U_{n}|\ll|\alpha_{1}|^{n-n/x^{c_{1}}}n^{D}(\log n+O(1)).$

In particular, since $n\geq x^{1-c_{2}}$, it follows that for large $x$ the
inequality

$|U_{n}|\ll|\alpha_{1}|^{n-0.5n/x^{c_{1}}}$

holds. This inequality can be rewritten as

$\left|\sum_{i=1}^{s}P_{i}(n)(\alpha_{i}/\alpha_{1})^{n}\right|\leq|\alpha_{1}|^{-0.5n/x^{c_{1}}}.$
(2)

We may assume that $s\geq 2$, otherwise the above inequality fails for all $x$
sufficiently large when $s=1$ and $n\geq x^{1-c_{2}}$ as $|\alpha_{1}|>1$
(here we used the fact that $|U_{n}|$ is not a polynomial in $n$ which
corresponds to the case $s=1$ and $\alpha_{1}\in\\{\pm 1\\}$). Let
${\mathbb{K}}$ be the splitting field of the characteristic polynomial of
$(U_{n})_{n\geq 1}$. We let

${\bf
x}:=(x_{1},\ldots,x_{s})=(P_{1}(n),P_{2}(n)(\alpha_{2}/\alpha_{1})^{n},\ldots,P_{s}(n)(\alpha_{s}/\alpha_{1})^{n}).$

Let ${\mathcal{S}}$ be the set of valuations of ${\mathbb{K}}$ consisting of
all the infinite ones together with the finite ones $v$ such that
$|\alpha_{i}/\alpha_{1}|_{v}\neq 1$ for some $i=2,\ldots,s$. A classical
application of the subspace theorem shows that inequality (2) can be rewritten
as

$\prod_{i=1}^{s}\prod_{v\in{\mathcal{S}}}|L_{i,v}({\bf x})|_{v}\ll
n^{sD}|\alpha_{1}|^{-c_{3}n/x^{c_{1}}}.$ (3)

In the above, $L_{i,v}({\bf x})$ are linear forms in ${\bf x}$ given by
$L_{i,v}({\bf x})=x_{i}$ for all $(i,v)\in\\{1,\ldots,s\\}\times{\mathcal{S}}$
except for the pair of indices say $(i,s)=(1,\infty)$, where $\infty$ is the
infinite valuation corresponding to the embedding of ${\mathbb{K}}$ in
${\mathbb{C}}$, for which we take $L_{1,\infty}({\bf x})=\sum_{i=1}^{s}x_{i}$.
Here, $c_{3}:=0.5/d$ or $1/d$, where $d$ is the degree of ${\mathbb{K}}$
according to whether ${\mathbb{K}}$ is real or not. Indeed, by the product
formula we have

$\prod_{v\in{\mathcal{S}}}|L_{i,v}({\bf
x})|_{v}=\prod_{v\in{\mathcal{S}}}|P_{i}(n)(\alpha_{i}/\alpha_{1})^{n}|_{v}\ll|P_{i}(n)|\ll
n^{D}$

for $i\in\\{2,3,\ldots,s\\}$, while

$\displaystyle\prod_{v\in{\mathcal{S}}}|L_{1,v}({\bf x})|_{v}$
$\displaystyle=$
$\displaystyle|\sum_{i=1}^{s}P_{i}(n)(\alpha_{i}/\alpha_{1})^{n}|_{\infty}\prod_{v\in{\mathcal{S}}\backslash\\{\infty\\}}|x_{1}|_{v}$
$\displaystyle\ll$
$\displaystyle|\alpha_{1}|^{-c_{3}n/x^{c_{1}}}|P_{1}(n)|_{\infty}\ll|\alpha_{1}|^{-c_{3}n/x^{c_{1}}}n^{D}.$

Inequality (3) together with the fact that $H({\bf
x})\gg|\alpha_{1}|^{c_{4}n}$ for some positive constant $c_{4}$ shows that
there exists a positive constant $c_{5}$ such that inequality

$\prod_{i=1}^{s}\prod_{v\in{\mathcal{S}}}\frac{|L_{i,v}({\bf x})|_{v}}{|{\bf
x}|_{v}}\leq H({\bf x})^{-c_{5}/x^{c_{1}}}$

holds. Let $\delta:=c_{5}/x^{c_{1}}$. By the Subspace theorem, the vector
${\bf x}$ is contained in finitely many proper linear subspaces of
${\mathbb{K}}$. The number of such subspaces can be bounded in terms of
$\delta$. For example, the main theorem in [1] shows that the number of these
subspaces is at most

$(2^{60s^{2}}\delta^{-7s})^{r}\log d\log\log d,$

where $r$ is the cardinality of ${\mathcal{S}}$ and $d$ is the degree of
${\mathbb{K}}$. Choosing the constant $c_{1}:=1/(14rs)$, we get that the
number of subspaces is $O({\sqrt{x}})$ and the constant implied by the above
$O$ depends on the sequence. Each one of these subspaces leads to an equation
of the form

$\sum_{i=1}^{s}C_{i}P_{i}(n)\alpha_{i}^{n}=0,$

where $(C_{1},\ldots,C_{s})$ is a vector with components in ${\mathbb{K}}$ not
all zero. But each of such equations represents the number of zeros of a
certain nondegenerate linearly recurrent sequence having the same
characteristic polynomial as $(U_{n})_{n\geq 0}$ and the number of such zeros
is bounded in terms of $s$ only. Putting everything together we get the
conclusion of the theorem. The case of the $\sigma$ function is analogous as
$\sigma(n)\geq n+n/p(n)\geq n+n/x^{c_{1}}$ when
$n\not\in{\mathcal{A}}_{1}(x)$.

## References

  * [1] J.–H. Evertse, “An improvement of the quantitative subspace theorem”, Compositio Math. 101 (1996), 225–311.
  * [2] M. Jaidee and P. Pongsriiam, “Arithmetic functions of Fibonacci and Lucas numbers”, Fibonacci Quart. 57 (2019), 246–254.
  * [3] F. Luca, “Arithmetic functions of Fibonacci numbers”, Fibonacci Quart. 37 (1999), 265–268.
  * [4] A. K. Pandey and B. K. Sharma, “On inequalities related to a generalized Euler totient function and Lucas sequences”, J. Integer Seq. 26 (2023), Art. 23.8.6.