#  Network-based community detection of comorbidities and their association
with SARS-CoV-2 virus during COVID-19 pathogenesis

S. Chatterjee<EMAIL_ADDRESS>B.S. Sanjeev<EMAIL_ADDRESS>
(May 31, 2022)

###### Abstract

Recent studies emphasized the necessity to identify key (human) biological
processes and pathways targeted by the Coronaviridae family of viruses,
especially SARS-CoV-2. COVID-19 caused up to 33-55% death rates in COVID-19
patients with malignant neoplasms and Alzheimer’s disease. Given this
scenario, we identified biological processes and pathways which are most
likely affected by COVID-19. The associations between various diseases and
human genes known to interact with viruses from Coronaviridae family were
obtained from the IntAct COVID-19 data set annotated with DisGeNET data. We
constructed the disease-gene network to identify genes that are involved in
various comorbid diseased states. Communities from the disease-gene network
through Louvain method were identified and functional enrichment through over-
representation analysis methodology was used to discover significant
biological processes and pathways shared between COVID-19 and other diseases.
The IntAct COVID-19 data set comprised of 828 human genes and 10,473 diseases
that together constituted nodes in the disease-gene network. Each of the
70,210 edges connects a human gene with an associated disease. The top 10
genes linked to most number of diseases were VEGFA, BCL2, CTNNB1, ALB, COX2,
AGT, HLA-A, HMOX1, FGT2 and COMT. The most vulnerable group of patients thus
discovered had comorbid conditions such as carcinomas, malignant neoplasms and
Alzheimer’s disease. Finally, we identified 37 potentially useful biological
processes and pathways for improved therapies.

Department of Applied Sciences

Indian Institute of Information Technology

Allahabad 211012, India

###### Contents

  1. 1 Introduction
  2. 2 Materials and Methods
    1. 2.1 Disease-gene Network Construction
    2. 2.2 Network Analysis
    3. 2.3 Network Modularity
    4. 2.4 Community Detection
    5. 2.5 Functional Pathway Enrichment Analysis
  3. 3 Results and Discussion
    1. 3.1 Analysis of Disease-Gene Network
    2. 3.2 Network Topology Community Detection
    3. 3.3 Functional Enrichment Analysis
    4. 3.4 Validation
  4. 4 Conclusion

##  1 Introduction

Genes and proteins perform a variety of functions within an organism.
Interactions between them are indispensable to fundamental cellular processes.
Graph-theoretic tools enable processing network topological information to
identify and analyze functional dependencies between disease-gene dynamics
[1]. Many network-based strategies have been widely adopted to investigate
such relationships [2]. The current pandemic, COVID-19, is caused by SARS-
CoV-2 virus. This virus is a member of Coronaviridae family that is also
responsible for other life threatening diseases such as SARS-CoV and MERS [3].
Insights from disease-gene networks have been useful to decipher the
underlying molecular interactions with context-specific studies, including
COVID-19 [4]. Evidence from multiple studies has shown that the severity of
COVID-19 is enhanced by comorbid and life-threatening diseases, and patients
with comorbidities have been affected disproportionately [5, 6]. Such patients
are more susceptible to organ failure and mortality [6]. Patients with
comorbidities such as carcinomas and malignant neoplasms have a higher risk of
developing multiple organ failure leading to death [7]. According to a recent
study on COVID-19 patients, the mortality rate was as high as 33% if afflicted
with malignant neoplasms [8]. At 54.5%, the mortality rate associated with
Alzheimer’s disease was even higher [9]. The molecular interplay involving
overlapping relationships between COVID-19 and other diseases such as
carcinomas, neoplasms and Alzheimer’s disease is not yet fully understood
[10]. Given the global spread of COVID-19, it is vital to investigate
biological processes and pathways that are common between COVID-19 and other
diseases and comorbid conditions. Such advances would ultimately contribute
towards better therapeutic outcomes.

Protein-protein interactions (PPIs) are generally modeled using network
centrality approaches. Such approaches have been used to understand various
disease mechanisms and comorbidities of SARS-CoV-2 in HIV and other immuno-
compromised diseases [11]. In the current study, we constructed a disease-gene
network which maps (human) genes associated with diseases as well as viral
proteins of the Coronaviridae family.

The aim of the current study is to perform an integrated network analysis
between diseases and genes to discover biological processes and pathways
shared between COVID-19 and various diseases.

##  2 Materials and Methods

The methodology followed in this study uses network analysis tools for
community detection. We constructed a disease-gene network for analysis to
identify crucial genes followed by Louvain method based community detection to
identify biological process and pathways affected by SARS-CoV-2 infection.

###  2.1 Disease-gene Network Construction

DisGeNET is a comprehensive database comprising of genes and variants
associated with human diseases [12]. It integrates data from expert-curated
repositories, GWAS databases, animal models and the scientific literature. The
IntAct Coronavirus data set includes interaction data from the high-throughput
multi-level proteomics studies on SARS-CoV-2, SARS and other members of the
Coronaviridae family. It contains molecular interactions involving human and
viral proteins from the Coronaviridae family, along with a certain proportion
of other model organisms.

The disease-gene network upon which the analysis was performed was constructed
using IntAct Coronavirus data set that is annotated through DisGeNET [12]. The
IntAct Coronavirus data set was derived from the IntAct Molecular Interaction
database which is a curated database for molecular interaction data [13]. For
annotation through DisGeNET, only human proteins which interact with members
of the Coronaviridae family were taken into account. The disease-gene network
was constructed [14] as an undirected biparted graph $G$ ($V_{G}$, $E_{G}$),
where the 11,301 nodes ($V_{G}$) represented 828 genes and 10,473 diseases,
and the 70,210 edges ($E_{G}$) represented disease-gene interactions. The
network is a biparted graph as all edges connect the set of diseases with the
set of human genes, with each edge representing an association from the IntAct
Coronavirus data set.

###  2.2 Network Analysis

The degree of a node is defined as the number of edges connected to it. It is
one of the measures of network connectivity and network centrality measures
used in protein-protein interactions [15]. Nodes with high degree represent
hubs. Figure 1 shows the number of nodes and their respective degrees.
Functional gene enrichment analysis was performed to reveal critical pathways
that could be targeted for clinical purposes.

Figure 1: Very high degrees for only a fraction of nodes shows that only a
smaller set of genes and diseases have high interactions with other nodes. For
instance, VEGFA is known to be involved in 1899 diseases, while malignant
neoplasms are associated with 459 genes. All the genes, taken from IntAct
Coronavirus data set [12], are known to be associated with SARS-CoV-2 too.

###  2.3 Network Modularity

Modularity is defined as the fraction of edges that fall within the given
groups minus the expected fraction if edges were distributed at random [16].
The modularity for undirected graphs lies in the range of
${\displaystyle(-1/2,1)}$. A positive modularity indicates that the number of
edges within a community exceeds the expected value by random chance.
Modularity (Louvain method) of the disease-gene network was 0.28 among all the
22 classes signifying a positive modular structured network (see Figure 2).

Figure 2: The network modularity of the disease-gene network constructed was
0.28 signifying a positive modular structured network. Shown here are sizes
(number of nodes) of the 22 modularity classes obtained.

###  2.4 Community Detection

Community detection algorithms aim to identify the modules and, possibly,
their hierarchical organization, based only on the information encoded in the
graph topology [17]. The algorithms assign nodes to communities based on the
hierarchical organization of the structure of the network [18]. Community
detection was successfully applied in protein function annotation,
identification of disease modules, disease gene prediction and studies on
drug-targeted therapies [19, 20].

Community Detection Application and Service framework (CDAPS) is a framework
that integrates identification, annotation, visualization and analysis of
large-scale multi-scale network communities [19]. Genes underlying the same
phenotype tend to interact with each other and form network communities [21].
Hierarchical community Decoding Framework (HiDeF) is one of the frameworks
that proved its utility in identifying robust structures in omics data [22].
It is capable of analyzing the multiscale organization of diverse biological
systems. Hence, we used HiDeF (through CDAPS) to gain insights into the
hierarchical communities present in the disease-gene network.

Community detection was performed using the Louvain algorithm (in HiDeF
framework) with a maximum resolution parameter of less than 50 and p-values
representing the significance [23]. p-value is defined as the probability of
discovering at least n genes with the annotation (GO:BP), in a community
module with n genes.

The community persistence threshold was kept at 5 to remove the unstable
clusters. This resulted in a hierarchical network with communities as nodes
and their hierarchical relationships as edges. We identified significant
communities to study network connectedness and the number of hierarchical
modules of the overall network. For functional enrichment, the communities
were based on the significance of overlap with gene sets from curated gene
ontology databases. The Louvain method based on network modularity (Q) is
defined as [24]:

$\displaystyle{\displaystyle
Q={\frac{1}{2m}}\sum\limits_{ij}{\bigg{[}}A_{ij}-{\frac{k_{i}k_{j}}{2m}}{\bigg{]}}\delta(c_{i},c_{j})}$
(1)

where ${\displaystyle A_{ij}}$ represents the edge weight between nodes
${\displaystyle i}$ and ${\displaystyle j}$; ${\displaystyle k_{i}}$ and
${\displaystyle k_{j}}$ are the sum of the weights of the edges attached to
nodes ${\displaystyle i}$ and ${\displaystyle j}$ respectively;
${\displaystyle m}$ is the sum of all of the edge weights in the graph;
${\displaystyle c_{i}}$ and ${\displaystyle c_{j}}$ are the communities of the
nodes; and ${\displaystyle\delta}$ is Kronecker delta function
$({\displaystyle\delta(x,y)=1}$ if ${\displaystyle x=y}$, ${\displaystyle 0}$
otherwise).

G the initial network

repeat

Put each node of G in its own community;

while  _some nodes are moved_ do

for  _all node n of G_ do

place n in its neighboring community

including its own which maximizes

the gain in modularity

endfor

endwhile

if  _the new modularity is greater than the initial_ then

G = the network between communities of G;

else

Terminate

end if

endif

until  __;

Algorithm 1 Louvain Algorithm for Community Detection

###  2.5 Functional Pathway Enrichment Analysis

g:Profiler is a widely used tool to detect statistically significant gene
ontology terms that highlight biological processes enriched in gene lists with
known functional information [25]. Using g:Profiler, genes were mapped to
known functional annotations to detect statistically significant enriched
pathways for functional enrichment (see Table 2 ). This process allows over-
representation analysis that highlights statistically significant pathways.

We selected all nodes with minimum Jaccard index value [26] for overlap
greater than 0.05 and the range of p-value [27] upto a maximum of 0.00001. The
information for functional enrichment is fetched from widely known databases
such as KEGG database [28], WikiPathways [29], Reactome pathway database [30]
and other widely known databases for gene ontology.

Figure 3: Network representation of the most significant biological processes and pathways. Community detection (Louvain method) was executed using Hierarchical community Decoding Framework. The associations of functional enrichment are represented as a hierarchical network for community detection using over-represented analysis wherein the size of a node represents its significance in the Disease-Gene Network. (a) High degree genes | (b) High degree diseases
---|---
| Rank | Gene | Degree
---|---|---
1 | VEGFA | 1899
2 | BCL2 | 1456
3 | CTNNB1 | 1368
4 | ALB | 1198
5 | COX2 | 875
6 | AGT | 765
7 | HLA-A | 672
8 | HMOX1 | 666
9 | FGF2 | 635
10 | COMT | 622
11 | MET | 594
12 | PLG | 586
13 | PCNA | 581
14 | PARP1 | 565
15 | AIMP2 | 555
16 | FBN1 | 552
17 | HSPA4 | 550
18 | GNAS | 536
19 | STAT1 | 531
20 | AHSA1 | 526
21 | TGFBR2 | 502
22 | HSPA1B | 502
23 | DNMT1 | 496
24 | HSPA1A | 458
25 | DPP4 | 451
| Rank | Disease Name | Degree
---|---|---
1 | Neoplasms (unclassified) | 535
2 | Malignant Neoplasms | 459
3 | Primary Malignant Neoplasms | 444
4 | Malignant Neoplasm of breast | 372
5 | Tumor cell Invasion | 368
6 | Breast Carcinoma | 363
7 | Liver Carcinoma | 352
8 | Carcinogenesis | 347
9 | Neoplasm metastasis | 344
10 | Colorectal carcinoma | 309
11 | Malignant neoplasm of prostrate | 284
12 | Prostrate carcinoma | 276
13 | Malignant neoplasm of lung | 263
14 | Carcinoma of lung | 262
15 | Primary malignant neoplasm of lung | 257
16 | Non-small cell Lung carcinoma | 241
17 | Tumor progression | 235
18 | Alzheimer’s Disease | 226
19 | Malignant neoplasm of stomach | 221
20 | Stomach carcinoma | 209
21 | Malignant neoplasm of colon | 208
22 | Glioblastoma | 198
23 | Glioblastoma Multiforme | 195
24 | Glioma | 193
25 | Melanoma | 188
Table 1: List of high-degree nodes in the Disease-Gene network. Rank | Gene Ontology / Biological process | P-value | -log(P-value) | Reference
---|---|---|---|---
1 | Mitochondrial respiratory chain complex I assembly | 8.71E-12 | 11.05998 | GO:0032981
2 | Ubiquitin E3 ligase | 1.63E-10 | 9.787812 | CORUM:622
3 | Activin receptor complex | 2.82E-10 | 9.549751 | GO:0048179
4 | Arylamine N-acetyltransferase activity | 1.49E-09 | 8.826814 | GO:0004060
5 | Complex I biogenesis | 1.49E-08 | 7.826814 | REAC:R-HSA-6799198
6 | FK506 binding | 3.23E-08 | 7.490797 | GO:0005528
7 | HDL assembly | 5.21E-08 | 7.283162 | REAC:R-HSA-8963896
8 | Integrated Cancer Pathway | 3.76E-07 | 6.424812 | WP:WP1971
9 | ACE Inhibitor Pathway | 5.50E-07 | 6.258848 | WP:WP554
10 | Hypothesized Pathways in Pathogenesis of CVD | 5.72E-07 | 6.242604 | WP:WP3668
11 | 40S ribosomal subunit, cytoplasmic | 7.42E-07 | 6.129596 | CORUM:305
12 | TIM complex, mitochondrial | 8.17E-07 | 6.087778 | CORUM:623
13 | EIF3 complex | 8.17E-07 | 6.087778 | CORUM:4399
14 | VCB complex | 8.25E-07 | 6.083546 | GO:0030891
15 | Acetylation | 1.09E-06 | 5.962574 | REAC:R-HSA-156582
16 | SARS-CoV-2 mitochondrial interactions | 1.23E-06 | 5.910095 | WP:WP5038
17 | snRNA binding | 1.30E-06 | 5.886057 | GO:0017069
18 | Complex I biogenesis | 1.42E-06 | 5.847712 | REAC:R-HSA-6799198
19 | ribosomal small subunit assembly | 1.50E-06 | 5.823909 | GO:0000028
20 | PLOD2-FKBP10 complex | 1.65E-06 | 5.782516 | CORUM:7000
21 | negative regulation of extrinsic apoptotic signaling pathway | 1.73E-06 | 5.761954 | GO:1902042
22 | CRD-mediated mRNA stability complex | 2.06E-06 | 5.686133 | GO:0070937
23 | TIM complex, mitochondrial | 2.06E-06 | 5.686133 | CORUM:623
24 | ncRNA catabolic process | 2.47E-06 | 5.607303 | GO:0034661
25 | Acetylation | 2.89E-06 | 5.539102 | REAC:R-HSA-156582
26 | angiotensin-mediated drinking behavior | 3.28E-06 | 5.484126 | GO:0003051
27 | positive regulation of phospholipase C activity | 4.44E-06 | 5.352617 | GO:0010863
28 | DCS complex | 4.90E-06 | 5.309804 | CORUM:1288
29 | snRNA binding | 6.58E-06 | 5.181774 | GO:0017069
30 | Ubiquinone and other terpenoid-quinone biosynthesis | 6.71E-06 | 5.173277 | KEGG:00130
31 | metanephric glomerular capillary formation | 7.31E-06 | 5.136083 | GO:0072277
32 | CCT complex | 7.62E-06 | 5.118045 | CORUM:126
33 | heat acclimation | 8.01E-06 | 5.096367 | GO:0010286
34 | Striated Muscle Contraction | 8.70E-06 | 5.060481 | REAC:R-HSA-390522
35 | protein N-linked glycosylation via asparagine | 9.63E-06 | 5.016374 | GO:0018279
36 | medium-chain-acyl-CoA dehydrogenase activity | 9.84E-06 | 5.007005 | GO:0070991
37 | Interferon-stimulated gene factor 3 transcription complex | 9.90E-06 | 5.004365 | CORUM:60
Table 2: List of significantly enriched biological processes and pathways along with their community size. The number of genes involved are less than 7 and the corresponding p-value threshold is less than 9.9E-06. Rank | Gene Ontology / Biological process | Gc | FDR
---|---|---|---
1 | Mitochondrial respiratory chain complex I assembly | 7 | 9.60E-14
2 | Ubiquitin E3 ligase | 3 | -
3 | Activin receptor complex | 4 | 5.84E-11
4 | Arylamine N-acetyltransferase activity | 3 | -
5 | Complex I biogenesis | 4 | 1.62E-07
6 | FK506 binding | 3 | 0.0007
7 | HDL assembly | 3 | 0.0211
8 | Integrated Cancer Pathway | 4 | 2.16E-08
9 | ACE Inhibitor Pathway | 3 | 6.19E-07
10 | Hypothesized Pathways in Pathogenesis of CVD | 3 | 1.78E-06
11 | 40S ribosomal subunit, cytoplasmic | 3 | 1.56E-05
12 | TIM complex, mitochondrial | 2 | 0.00034
13 | EIF3 complex | 2 | 0.0012
14 | VCB complex | 2 | 0.00019
15 | Acetylation | 2 | 6.81E-05
16 | SARS-CoV-2 mitochondrial interactions | 3 | 3.55E-06
17 | snRNA binding | 3 | 4.20E-05
18 | Complex I biogenesis | 3 | 5.37E-05
19 | ribosomal small subunit assembly | 3 | 1.37E-05
20 | PLOD2-FKBP10 complex | 2 | -
21 | Negative regulation of extrinsic apoptotic signaling | 3 | 0.00012
22 | CRD-mediated mRNA stability complex | 2 | 0.00025
23 | TIM complex, mitochondrial | 2 | 0.00034
24 | ncRNA catabolic process | 3 | 6.73E-05
25 | Acetylation | 2 | 6.81E-05
26 | angiotensin-mediated drinking behavior | 2 | 0.00040
27 | positive regulation of phospholipase C activity | 3 | 0.00019
28 | DCS complex | 2 | -
29 | snRNA binding | 3 | 4.20E-05
30 | Ubiquinone and other terpenoid-quinone biosynthesis | 2 | 0.00014
31 | metanephric glomerular capillary formation | 2 | 0.00067
32 | CCT complex | 2 | 0.00059
33 | heat acclimation | 2 | -
34 | Striated Muscle Contraction | 3 | 1.47E-05
35 | protein N-linked glycosylation via asparagine | 3 | 5.61E-05
36 | medium-chain-acyl-CoA dehydrogenase activity | 2 | 0.00017
37 | Interferon-stimulated gene factor 3 complex | 2 | -
Table 3: Functionally enriched biological processes validated using STRING
along with the number of genes involved (Gc) in the community and the False
Discovery Rates (FDR) of each GO:BP node. Figure 4: List of significantly
enriched biological pathways based on -log(p-value).

##  3 Results and Discussion

Treating patients with life threatening diseases during COVID-19 pandemic has
been quite challenging. There is an urgent need for treatment strategies that
utilize therapies involving immunosuppression. Therapeutic clinical
applications used in various immunotherapies have led to the worsening of
COVID-19 outcomes among patients suffering from cancer [31]. Acute respiratory
distress syndrome (ARDS), pulmonary embolism, acute myocardial infarction and
septic shock were the leading causes of death among cancer patients [32]. In
developing adverse COVID-19 outcomes, cancer patients are at higher risk [33].
The clinical manifestations of neurological disorders, carcinomas and COVID-19
infected patients are to a certain extent interrelated with the modulation of
immune system involving cytokine storm and immunosuppression [34]. It has been
hypothesized that patients suffering from the above stated conditions being
more vulnerable to viral infections due to compromised immune responses [35].
Therefore, it becomes critical to investigate as to why patients suffering
from immunocompromised disorders are at higher risk, and to determine how
SARS-CoV-2 infection affects the overall functionality of patients with
comorbidities. We present the insights obtained from network analysis and
functional enrichment studies on the disease-gene network.

###  3.1 Analysis of Disease-Gene Network

The disease-gene network was constructed as described in Section 2.1. This
network is a biparted graph with edges connecting diseases to functionally
connected (human) genes affected by COVID-19. The network comprised of 11,301
nodes (828 human genes and 10,473 diseases) and 70,210 edges.

As shown in Tables 1 (a-b) , the top 25 diseases ranked by degree were either
neoplasms or carcinomas. The lone exception to this list was Alzheimer’s
disease, a neurodegenerative disease that affects a large population.

The top 10 genes that were involved with most diseases were identified as
VEGFA, BCL2, CTNNB1, ALB, COX2, AGT, HLA-A, HMOX1, FGT2 and COMT. The degrees
were in the range 622 (COMT) to 1,899 (VEGFA). These results reflect the
significance of hubs in the overall disease-gene network.

Escaping immune system mechanism is a prerequisite for tumor development in
carcinomas. Angiogenic entities such as VEGFA play a significant role [36] in
the development of immunosuppressive micro environment [37]. Consequently,
strategies involving treatment with anti-VEGF drugs such as bevacizumab
besides VEGFR-mediated signaling therapies may deliver favorable outcomes.
Studies have already shown that such treatments improve anti-inflammatory
responses and oxygen perfusion, culminating in the alleviation of clinical
symptoms in severe COVID-19 patients [38].

###  3.2 Network Topology Community Detection

We performed community detection on the disease-gene network using Louvain
algorithm [24] to obtain 1,052 significant communities. The p-value was kept
as 0.00001.

###  3.3 Functional Enrichment Analysis

Our main focus was to highlight the critical processes affected by COVID-19
disease. Figure 3 shows the network representation of top-ranked biological
processes and pathways obtained through the analysis. To identify
significantly enriched biological processes and pathways, the corresponding
p-value threshold was kept less than 9.9E-06. As listed in Table 2, we
identified 37 such key biological processes and critical pathways affected by
Coronaviridae family in the overall disease gene network with p-values ranging
between 8.71E-12 to 9.90E-6.

As shown in Table 3 , the maximum number of genes involved in all the
identified communities was less than 7. The top 10 biological
processes/critical pathways were associated with the mitochondrial respiratory
chain I complex assembly, Ubiquitin E3 ligase, Activin receptor complex,
Arylamine N-acetyltransferase activity, Complex I biogenesis, FK506 binding,
HDL assembly, Integrated Cancer Pathway and ACE Inhibitor Pathway and
Hypothesized Pathways in Pathogenesis of Cardiovascular Diseases (as shown in
Figure. 4) .

###  3.4 Validation

For validation, we correlated our findings with STRING database which is a
comprehensively covers human proteins in the form of manually curated function
protein interaction network [39]. As shown in Table 3 , 31 out of all the 37
significant communities (84%) detected were validated (supplementary table
attached) with least False Discovery Rate (FDR), demonstrating that the
majority of highlighted GO:BP terms are clinically significant.

##  4 Conclusion

In the current study, we analyzed the disease-gene network linked to SARS-
CoV-2 and other members of the Coronaviridae family. Our study strongly
suggests that the patients with comorbid conditions, especially various
carcinomas, neoplasms and Alzheimer’s disease, are the most vulnerable among
all the disease classes infected by SARS-CoV-2.

Using network topology and community detection algorithm followed by
functional enrichment, the top 10 potential genes that were involved with
multiple diseases involving various carcinomas and neoplasms were identified
as VEGFA, BCL2, CTNNB1, ALB, COX2, AGT, HLA-A, HMOX1, FGT2 and COMT. We report
37 key biological processes and disease pathways affected by Coronavirus
infection in the disease gene network. As an outcome of our study, we make
case for clinical investigations towards anti-VEGF therapies in patients
suffering from various carcinomas and neoplasms infected with COVID-19.

## References

  * [1] Xingyi Li, Wenkai Li, Min Zeng, Ruiqing Zheng, and Min Li.  Network-based methods for predicting essential genes or proteins: a survey.  Briefings in bioinformatics, 21(2):566–583, 2020.
  * [2] Xiujuan Wang, Natali Gulbahce, and Haiyuan Yu.  Network-based methods for human disease gene prediction.  Briefings in functional genomics, 10(5):280–293, 2011.
  * [3] Zeinab Abdelrahman, Mengyuan Li, and Xiaosheng Wang.  Comparative review of sars-cov-2, sars-cov, mers-cov, and influenza a respiratory viruses.  Frontiers in immunology, page 2309, 2020.
  * [4] Xu Li, Jinchao Yu, Zhiming Zhang, Jing Ren, Alex E Peluffo, Wen Zhang, Yujie Zhao, Jiawei Wu, Kaijing Yan, Daniel Cohen, et al.  Network bioinformatics analysis provides insight into drug repurposing for covid-19.  Medicine in Drug Discovery, 10:100090, 2021.
  * [5] Zhi Zong, Yujun Wei, Jiang Ren, Long Zhang, and Fangfang Zhou.  The intersection of covid-19 and cancer: signaling pathways and treatment implications.  Molecular Cancer, 20(1):1–19, 2021.
  * [6] Adekunle Sanyaolu, Chuku Okorie, Aleksandra Marinkovic, Risha Patidar, Kokab Younis, Priyank Desai, Zaheeda Hosein, Inderbir Padda, Jasmine Mangat, and Mohsin Altaf.  Comorbidity and its impact on patients with covid-19.  SN comprehensive clinical medicine, 2(8):1069–1076, 2020.
  * [7] Puja Mehta, Daniel F McAuley, Michael Brown, Emilie Sanchez, Rachel S Tattersall, and Jessica J Manson.  Covid-19: consider cytokine storm syndromes and immunosuppression.  The lancet, 395(10229):1033–1034, 2020.
  * [8] Mariana Chavez-MacGregor, Xiudong Lei, Hui Zhao, Paul Scheet, and Sharon H Giordano.  Evaluation of covid-19 mortality and adverse outcomes in us patients with or without cancer.  JAMA oncology, 8(1):69–78, 2022.
  * [9] Jordi A Matias-Guiu, Vanesa Pytel, and Jorge Matías-Guiu.  Death rate due to covid-19 in alzheimer’s disease and frontotemporal dementia.  Journal of Alzheimer’s Disease, 78(2):537–541, 2020.
  * [10] Osama M Al-Quteimat and Amer Mustafa Amer.  The impact of the covid-19 pandemic on cancer patients.  American journal of clinical oncology, 2020.
  * [11] Juan Ambrosioni, José Luis Blanco, Juliana M Reyes-Urueña, Mary-Ann Davies, Omar Sued, Maria Angeles Marcos, Esteban Martínez, Silvia Bertagnolio, Jose Alcamí, Jose M Miro, et al.  Overview of sars-cov-2 infection in adults living with hiv.  The lancet HIV, 8(5):e294–e305, 2021.
  * [12] Janet Piñero, Juan Manuel Ramírez-Anguita, Josep Saüch-Pitarch, Francesco Ronzano, Emilio Centeno, Ferran Sanz, and Laura I Furlong.  The disgenet knowledge platform for disease genomics: 2019 update.  Nucleic acids research, 48(D1):D845–D855, 2021.
  * [13] Henning Hermjakob, Luisa Montecchi-Palazzi, Chris Lewington, Sugath Mudali, Samuel Kerrien, Sandra Orchard, Martin Vingron, Bernd Roechert, Peter Roepstorff, Alfonso Valencia, et al.  Intact: an open source molecular interaction database.  Nucleic acids research, 32(suppl_1):D452–D455, 2004.
  * [14] Paul Shannon, Andrew Markiel, Owen Ozier, Nitin S Baliga, Jonathan T Wang, Daniel Ramage, Nada Amin, Benno Schwikowski, and Trey Ideker.  Cytoscape: a software environment for integrated models of biomolecular interaction networks.  Genome research, 13(11):2498–2504, 2003.
  * [15] Hawoong Jeong, Sean P Mason, A-L Barabási, and Zoltan N Oltvai.  Lethality and centrality in protein networks.  Nature, 411(6833):41–42, 2001.
  * [16] Gaertler Marco Gorke Robert Hoefer Martin Nikoloski Zoran Brandes Ulrik, Delling Daniel and Wagner Dorothea.  On modularity clustering.  IEEE Transactions on Knowledge and Data Engineering, 20(2):172–188, 2008.
  * [17] Santo Fortunato.  Community detection in graphs.  Physics reports, 486(3-5):75–174, 2010.
  * [18] Arian Ashourvan, Qawi K Telesford, Timothy Verstynen, Jean M Vettel, and Danielle S Bassett.  Multi-scale detection of hierarchical community architecture in structural and functional brain networks.  PLoS One, 14(5):e0215520, 2019.
  * [19] Akshat Singhal, Song Cao, Christopher Churas, Dexter Pratt, Santo Fortunato, Fan Zheng, and Trey Ideker.  Multiscale community detection in cytoscape.  PLoS computational biology, 16(10):e1008239, 2020.
  * [20] Natali Gulbahce and Sune Lehmann.  The art of community detection.  BioEssays, 30(10):934–938, 2008.
  * [21] Lenore Cowen, Trey Ideker, Benjamin J Raphael, and Roded Sharan.  Network propagation: a universal amplifier of genetic associations.  Nature Reviews Genetics, 18(9):551–562, 2017.
  * [22] Fan Zheng, She Zhang, Christopher Churas, Dexter Pratt, Ivet Bahar, and Trey Ideker.  Hidef: identifying persistent structures in multiscale ‘omics data.  Genome biology, 22(1):1–15, 2021.
  * [23] Pak C Sham and Shaun M Purcell.  Statistical power and significance testing in large-scale genetic studies.  Nature Reviews Genetics, 15(5):335–346, 2014.
  * [24] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre.  Fast unfolding of communities in large networks.  Journal of statistical mechanics: theory and experiment, 2008(10):P10008, 2008.
  * [25] Uku Raudvere, Liis Kolberg, Ivan Kuzmin, Tambet Arak, Priit Adler, Hedi Peterson, and Jaak Vilo.  g: Profiler: a web server for functional enrichment analysis and conversions of gene lists (2019 update).  Nucleic acids research, 47(W1):W191–W198, 2019.
  * [26] Paul Jaccard.  The distribution of the flora in the alpine zone. 1.  New phytologist, 11(2):37–50, 1912.
  * [27] John D Storey and Robert Tibshirani.  Statistical significance for genomewide studies.  Proceedings of the National Academy of Sciences, 100(16):9440–9445, 2003.
  * [28] Minoru Kanehisa and Susumu Goto.  Kegg: kyoto encyclopedia of genes and genomes.  Nucleic acids research, 28(1):27–30, 2000.
  * [29] Alexander R Pico, Thomas Kelder, Martijn P Van Iersel, Kristina Hanspers, Bruce R Conklin, and Chris Evelo.  Wikipathways: pathway editing for the people.  PLoS biology, 6(7):e184, 2008.
  * [30] G Joshi-Tope, Marc Gillespie, Imre Vastrik, Peter D’Eustachio, Esther Schmidt, Bernard de Bono, Bijay Jassal, GR Gopinath, GR Wu, Lisa Matthews, et al.  Reactome: a knowledgebase of biological pathways.  Nucleic acids research, 33(suppl_1):D428–D432, 2005.
  * [31] Lisa Derosa, Cléa Melenotte, Franck Griscelli, Bertrand Gachot, Aurélien Marabelle, Guido Kroemer, and Laurence Zitvogel.  The immuno-oncological challenge of covid-19.  Nature Cancer, 1(10):946–964, 2020.
  * [32] A Addeo and A Friedlaender.  Cancer and covid-19: Unmasking their ties.  Cancer treatment reviews, 88:102041, 2020.
  * [33] Casmir Turnquist, Bríd M Ryan, Izumi Horikawa, Brent T Harris, and Curtis C Harris.  Cytokine storms in cancer and covid-19.  Cancer Cell, 38(5):598–601, 2020.
  * [34] Ziad Bakouny, Jessica E Hawley, Toni K Choueiri, Solange Peters, Brian I Rini, Jeremy L Warner, and Corrie A Painter.  Covid-19 and cancer: current challenges and perspectives.  Cancer Cell, 2020.
  * [35] Luigi Ferini-Strambi and Maria Salsone.  Covid-19 and neurological disorders: are neurodegenerative or neuroimmunological diseases more vulnerable?  Journal of neurology, 268(2):409–419, 2021.
  * [36] Robert D Schreiber, Lloyd J Old, and Mark J Smyth.  Cancer immunoediting: integrating immunity’s roles in cancer suppression and promotion.  Science, 331(6024):1565–1570, 2011.
  * [37] Thibault Voron, Orianne Colussi, Elie Marcheteau, Simon Pernot, Mevyn Nizard, Anne-Laure Pointet, Sabrina Latreche, Sonia Bergaya, Nadine Benhamouda, Corinne Tanchot, et al.  Vegf-a modulates expression of inhibitory checkpoints on cd8+ t cells in tumors.  Journal of Experimental Medicine, 212(2):139–148, 2015.
  * [38] Jiaojiao Pang, Feng Xu, Gianmarco Aondio, Yu Li, Alberto Fumagalli, Ming Lu, Giuseppe Valmadre, Jie Wei, Yuan Bian, Margherita Canesi, et al.  Efficacy and tolerability of bevacizumab in patients with severe covid-19.  Nature communications, 12(1):1–10, 2021.
  * [39] Damian Szklarczyk, Annika L Gable, Katerina C Nastou, David Lyon, Rebecca Kirsch, Sampo Pyysalo, Nadezhda T Doncheva, Marc Legeay, Tao Fang, Peer Bork, et al.  The string database in 2021: customizable protein–protein networks, and functional characterization of user-uploaded gene/measurement sets.  Nucleic acids research, 49(D1):D605–D612, 2021.
  * [40] Christopher Paluch, Ana Mafalda Santos, Consuelo Anzilotti, Richard J Cornall, and Simon J Davis.  Immune checkpoints as therapeutic targets in autoimmunity.  Frontiers in immunology, page 2306, 2018.
  * [41] Jörg Menche, Amitabh Sharma, Maksim Kitsak, Susan Dina Ghiassian, Marc Vidal, Joseph Loscalzo, and Albert-László Barabási.  Uncovering disease-disease relationships through the incomplete interactome.  Science, 347(6224):1257601, 2015.
  * [42] Thomas F Schulz.  Cancer and viral infections in immunocompromised individuals.  International journal of cancer, 125(8):1755–1763, 2009.
  * [43] Mini Kamboj and Kent A Sepkowitz.  Nosocomial infections in patients with cancer.  The Lancet Oncology, 10(6):589–597, 2009.
  * [44] Amir Hossein Mansourabadi, Mona Sadeghalvad, Hamid-Reza Mohammadi-Motlagh, and Nima Rezaei.  The immune system as a target for therapy of sars-cov-2: a systematic review of the current immunotherapies for covid-19.  Life sciences, page 118185, 2020.
  * [45] Livia Onofrio, Michele Caraglia, Gaetano Facchini, Vincenzo Margherita, Sabino De Placido, and Carlo Buonerba.  Toll-like receptors and covid-19: a two-faced story with an exciting ending.  Future science OA, 6(8):FSO605, 2020.
  * [46] Sara Rahiminejad, Mano R Maurya, and Shankar Subramaniam.  Topological and functional comparison of community detection algorithms in biological networks.  BMC bioinformatics, 20(1):1–25, 2019.


# Convexity and Aigner’s Conjectures

Greg McShane  Institut Fourier 100 rue des maths, BP 74, 38402 St Martin
d’Hères cedex, France  mcshane at ujf-grenoble.fr

###### Abstract.

Markov numbers are integers that appear in triples which are solutions of a
Diophantine equation, the so-called Markov cubic

$x^{2}+y^{2}+z^{2}-3xyz=0.$

A classical topic in number theory, these numbers are related to many areas of
mathematics such as combinatorics, hyperbolic geometry, approximation theory
and cluster algebras.

One can associate to each a positive rational number a Markov number in a
natural way. We give a new unified proof of certain conjectures from Martin
Aigner’s book, Markov’s Theorem and 100 Years of the Uniqueness Conjecture.
Our proof relies on a relationship between Markov numbers and the lengths of
closed simple geodesics on the punctured torus discovered by H. Cohn.

##  1\. Introduction

The Markov numbers are the positive integer solutions of the Diophantine
equation

$x^{2}+y^{2}+z^{2}-3xyz=0$

Markov in the late 1800s showed that all these solutions could be given the
structure of a binary tree. It became customary (and useful) to index the
Markov numbers by the rationals in the interval $[0,1]$ which stand at the
same place in the Stern–Brocot binary tree (see Figures 2 and 3). Frobenius’
conjecture asserts that each Markov number appears at most once in this tree.
If this conjecture is true, then the obvious order of Markov numbers gives
rise to a new strict order on the rationals.

###  1.1. Aigner’s Monotonicity Conjectures

Aigner [1] proposed three conjectures to better understand this order.

  1. (1)

(The fixed numerator conjecture) Let $p,q$ and $i$ be positive integers such
that $i>0,p<q$ and $gcd(p,q)=1,gcd(p,q+i)=1$ then

$m_{p/q}<m_{p/(q+i)}.$

  2. (2)

(The fixed denominator conjecture) Let $p,q$ and $i$ be positive integers such
that $i>0,p<q$ and $gcd(p,q)=1,gcd(p+i,q)=1$ then

$m_{p/q}<m_{(p+i)/q}.$

  3. (3)

(The fixed sum conjecture) Let $p,q$ and $i$ be positive integers such that
$i>0,p<q$ and $gcd(p,q)=1,gcd(p-i,q+i)=1$ then

$m_{p/q}<m_{(p-i)/(q+i)}.$

The fixed numerator conjecture was proved in [8] using ideas from cluster
algebra theory and snake graphs. Their proof relies on a connection between
Christoffel paths and Markov numbers (see [2] for a discussion) which provides
a formulation of Markov numbers as continuant polynomials. The proof is rather
technical and introduces several interesting tools for studying paths in the
Cayley graph of the monoid $\mathbb{N}^{2}$ with the usual generators. In [9],
the authors prove the fixed numerator conjecture by using ”transformations” on
paths in the Cayley graph. We will show how these results can be deduced by
considerations of convexity established in [7]. Our proof is represented
visually in Figure 4.

###  1.2. Geometry of the Markov numbers

The question of counting for Markov triples, that is for $R>0$ estimating the
size of the set of Markov triples $(x,y,z)$ for which the sup norm is less
than $R$, was first investigated by Gurwood in his thesis. He established an
asymptotic formula using a correspondence between Markov and Farey trees.
Somewhat later Zagier [10] obtained an improved error term. At the time of
writing the best result is due to a Rivin and the author [7]:

$M(R)=C(\log R)^{2}+O(\log R\log\log R),$

for a numerical constant which has a geometric interpretation.

The method introduced in [7] differs from that of Gurwood and Zagier in that
it relies on ideas of H. Cohn to interpret the question in terms of geometry
of hyperbolic surfaces. In [4] Cohn shows that the Markov triple $(1,1,1)$ is,
up to multiplication by 3, the image under the character map $\chi$ of the
modular torus. Recall that the modular torus is the quotient of the upper half
$\mathbb{H}$ plane by $\Gamma$, the commutator subgroup of
$\text{PSL}(2,\mathbb{Z})$, acting by Mobius transformations. Secondly, he
shows that the permutations and the Vieta flips used to construct Markov’s
binary tree are induced by automorphisms of the fundamental group of the torus
and concludes that $\text{Aut}(\mathbb{Z}*\mathbb{Z})$ acts transitively on
Markov triples. It is well known that if
$\rho:\mathbb{Z}*\mathbb{Z}\rightarrow\text{PSL}(2,\mathbb{R})$ is a discrete
faithful representation and $\gamma$ a closed curve homotopic on the surface
$X=\mathbb{H}/\rho(\mathbb{Z}*\mathbb{Z})$, then $\ell_{X}(\gamma)$, the
length of the closed geodesic homotopic to $\gamma$ on the surface $X$, can be
computed from the trace using the relation

$2\cosh\ell_{X}(\gamma)/2=|\text{tr\,}\rho(\gamma)|.$

We note that the absolute value of the trace of an element of
$\text{PSL}(2,\mathbb{R})$ is well defined. Now identifying
$\mathbb{Z}*\mathbb{Z}$ with the fundamental group of the modular torus Cohn
shows that if $x$ is a Markov number then there exists a simple loop $\gamma$
such that

$x=\frac{1}{3}|\text{tr\,}\rho(\gamma)|.$

so there is an explicit relation between Markov numbers and lengths of simple
geodesics on the modular torus. In [7] the simple closed curves are embedded
as a subset of primitive elements in the integer lattice
$\mathbb{Z}^{2}\subset\mathbb{R}^{2}$ and the length function
$\gamma\mapsto\ell_{X}(\gamma)$ is shown, using a simple geometric argument,
to extend to a proper convex function
$\ell:\mathbb{R}^{2}\mapsto\mathbb{R}_{+}$. Thus the counting problem for
Markov numbers can be settled by counting integer points in the set

$\ell^{-1}([0,R])=R\ell^{-1}([0,1])\subset\mathbb{R}^{2}$

It is easy to visualize this set using a very short computer program see for
example Figure 1.

In summary, given a fraction $p/q$ one obtains a primitive lattice point
$(q,p)\in\mathbb{Z}^{2}$ and so a closed simple geodesic $\gamma_{p/q}\subset
X$ such that

$M_{p/q}=\frac{2}{3}\cosh\left(\frac{\ell_{X}(\gamma_{p/q}))}{2}\right)=\frac{2}{3}\cosh(\|(q,p)\|_{s}),$

where $\|.\|_{s}$ is the norm induced by the function
$\frac{1}{2}\ell:\mathbb{R}^{2}\mapsto\mathbb{R}_{+}$.

Figure 1. A level set $S$ for the the length function $\ell$.

###  1.3. Restatement of Conjectures

Thus the fixed numerator conjecture is equivalent to : Let $p,q$ and $i$ be
positive integers such that $i>0,p<q$ and $p$ is coprime with both $q,q+i$
then

$\|(q,p)\|_{s}<\|(q+i,p)\|_{s}.$

It is natural now to ask oneself whether we need to restrict to integers. In
fact, using quite simple geometric arguments one can prove a result, in a non
discrete setting, which yields Aigner’s conjectures as a corollary:

######  Theorem 1.1.

Let $p,q$ be real non negative numbers and $i>0$ then

(1) $\|(q,p)\|_{s}<\|(q+i,p)\|_{s}$

and

(2) $\|(q,p)\|_{s}<\|(q,p+i)\|_{s}$

If in addition $p<q$ then

(3) $\|(q,p)\|_{s}<\|(q+i,p-i)\|_{s}$

###  1.4. Organisation, Remarks

We give a brief account of the geometry and topology of the once punctured
torus in Sections 2 and 3. This is followed in Section 4 by the proof of the
convexity of the length function $\ell$ which appeared in [7]. We conclude
with the proof of Theorem 1.1 in Section 5.

One could of course state many more theorems using these ideas but our purpose
here is simply to show why Aigner’s conjectures are manifestations of the
convexity of the length function.

Finally we note that it is unlikely that purely geometric methods would yield
a proof of Frobenius’ conjecture as a natural variation of it is false [6].

###  1.5. Thanks

I thank Vlad Segesciu and Louis Funar for many useful conversations over the
years concerning this subject. I am grateful too to Xu Binbin for comments on
the preliminary versions of the text.

##  2\. Hyperbolic structures and representations

The rank two free group $\mathbb{Z}*\mathbb{Z}$ arises as the fundamental
group of exactly two non-homeomorphic orientable surfaces: the three-holed
sphere $\Sigma_{0,3}$, the one-holed torus $\Sigma_{1,1}$, Furthermore
$\Sigma_{1,1}$ enjoys the remarkable property that every automorphism of its
fundamental group is geometric ie induced by a homeomorphism. Equivalently,
every homotopy-equivalence $\Sigma_{1,1}\rightarrow\Sigma_{1,1}$ is homotopic
to a homeomorphism. Much time and energy has been devoted to the geometric and
topological properties of the one holed torus see for example [3].

###  2.1. Fricke theory

It has been known since the time of Fricke that, as a consequence of Riemann’s
Uniformization Theorem, the moduli space of hyperbolic structures on the three
holed sphere and the one holed torus can be identified with semi algebraic
subsets of $\mathbb{R}^{3}$. More precisely, one obtains a hyperbolic
structure $X$ on $\Sigma$ from a discrete faithful representation $\rho$ of
$\pi_{1}(\Sigma)$ into $\mathrm{isom}(\mathbb{H})$ such that
$\mathbb{H}/\rho(\pi_{1}(\Sigma))$ is homeomorphic to $\Sigma$. One can lift
any such $\rho$ from a representation into $\mathrm{isom}(\mathbb{H})^{+}$,
which is isomorphic to $\text{P}\mathrm{SL}(2,\mathbb{R})$, to a
representation

$\tilde{\rho}:\pi_{1}(\Sigma)\rightarrow\text{SL}(2,\mathbb{R}).$

Doing this allows one to consider the trace
$\text{tr\,}\tilde{\rho}(\gamma)\in\mathbb{R}$ for any element $\gamma$ of the
free group so that many problems can be reduced to questions of linear
algebra. In particular one defines a character map

$\chi:X\mapsto(\text{tr\,}\tilde{\rho}(\alpha),\text{tr\,}\tilde{\rho}(\beta),\text{tr\,}\tilde{\rho}(\alpha\beta)),$

which provides an embedding of the moduli space of hyperbolic structures on
$\Sigma$. Goldman [5] studied the dynamical system defined by the action of
the group of outer automorphisms of
$\pi_{1}(\Sigma)\simeq\mathbb{Z}*\mathbb{Z}$ on the moduli space. If $\phi$ is
an automorphism then it acts on the representations

$\tilde{\rho}\mapsto\tilde{\rho}\circ\phi^{-1}$

and evidently this induces an action on the points in the image of the
embedding above. It turns out that, by applying Cayley-Hamilton theorem to
$\mathrm{SL}(2,\mathbb{R})$, it is easy to show that this action is the
restriction of polynomial diffeomorphisms of $\mathbb{R}^{3}$.

###  2.2. Markov triples

An important aspect of the theory of the action of the group of outer
automorphisms is that it admits an invariant function. In the case of the pair
of orientable surfaces this is

$\kappa:(x,y,z)\mapsto x^{2}+y^{2}+z^{2}-xyz.$

The level set $\kappa^{-1}(0)$ has five connected components - the singleton
$(0,0,0)$ and four codimension one manifolds homeomorphic to $\mathbb{R}^{2}$.
The non trivial components can be identified with the Teichmueller space of a
once punctured torus. It is well known that there are integer points in
$\kappa^{-1}(0)\cap\mathbb{R}_{+}^{3}$, for example $(3,3,3)$, and that they
form a single orbit for the action of the outer automorphisms. From such a
point one obtains a Markov triple, that is a solution in positive integers of
the Markov cubic

$x^{2}+y^{2}+z^{2}-3xyz=0$

simply by dividing through by $3$. This map is natural in that it is a
conjugation of automorphisms of the level set $\kappa^{-1}(0)$ with the
automorphisms of the Markov cubic. So, since we will not be interested in
arithemetic properties of these solutions, we will also refer in what follows
to elements of $\kappa^{-1}(0)\cap\mathbb{N}^{3}$ as Markov numbers. An
integer which appears in a Markov triple is called a Markov number.

####  2.2.1. Reduction theory

The fact that the Markov triples form a single orbit is a corollary of a
classical result of Markov in reduction theory which we now explain briefly.
We start by giving the Markov triples an ordering, in the obvious way, using
the sup norm on $\mathbb{R}^{3}$ and proceed to show that any solution can be
obtained from $(1,1,1)$ by repeatedly applying generators of the group of
automorphisms of the cubic. This automorphism group can be shown to be
generated by:

  1. (1)

sign change automorphisms $(x,y,z)\mapsto(x,-y,-z)$.

  2. (2)

coordinate permutations eg $(x,y,z)\mapsto(y,x,z)$.

  3. (3)

a Vieta flip $(x,y,z)\mapsto(x,y,3xy-z)$.

Since Markov triples are solutions in positive integers we will use just the
Markov morphisms that is the group generated by permutations and the Vieta
flip. Given a Markov triple $(x,y,z)\neq(1,1,1)$ we may apply a permutation so
that $x\leq y<z$ which one can try to “reduce” using the Vieta flip, that is
replacing the it by the triple $(x,y,3xy-z)$. We obtain a smaller solution
provided $3xy<2z$ and this inequality holds for every Markov triple except
$(1,1,1)$. The reduction process gives rise to the structure of a rooted
binary tree, the Markov tree, on the Markov triples with $(1,1,1)$ as the root
triple.

##  3\. Automorphisms of $\mathbb{Z}*\mathbb{Z}$

Let $\mathbb{Z}*\mathbb{Z}$ denote the free group on 2 generators which we
will denote $\alpha$ and $\beta$. We think of $\alpha$ and $\beta$ as simple
loops meeting in a single point in a holed torus.

###  3.1. Primitive elements

An element $\gamma\in\mathbb{Z}*\mathbb{Z}$ is called primitive, if there
exists an automorphism $\phi$, such that $\gamma=\phi(\alpha)$. If
$\phi(\delta)=\beta$, then $\gamma$ and $\delta$ are called associated
primitives.

Following [7] let $\phi:\mathbb{Z}*\mathbb{Z}\rightarrow\mathbb{Z}^{2}$ be the
canonical abelianizing homomorphism. The kernel of $\phi$ is a characteristic
subgroup, that is it is $\text{Aut}(\mathbb{Z}*\mathbb{Z})$-invariant, so
there is a homorphism from $\text{Aut}(\mathbb{Z}*\mathbb{Z})$ to the
automorphisms of $\mathbb{Z}^{2}$ namely $\mathrm{GL}(2,\mathbb{Z})$. In fact
this homomorphism is surjective and faithful. Moreover,

  1. (1)

If $\gamma$ is primitive then $\phi(\gamma)$ is a primitive element of
$\mathbb{Z}^{2}$.

  2. (2)

$\text{Aut}(\mathbb{Z}*\mathbb{Z})$ acts transitively on primitive elements of
$\mathbb{Z}*\mathbb{Z}$

  3. (3)

$\mathrm{GL}(2,\mathbb{Z})$ acts transitively on primitive elements of
$\mathbb{Z}^{2}$.

###  3.2. Topological realizations of automorphisms of $\mathbb{Z}*\mathbb{Z}$

It is useful, and this is essentially Cohn’s point of view [4], to identify
$\mathbb{Z}*\mathbb{Z}$ with the fundamental group of the holed torus and
think of $\mathrm{Out}(\mathbb{Z}*\mathbb{Z})$, the outer automorphism group
of $\mathbb{Z}*\mathbb{Z}$, as being the mapping class group of the holed
torus. The outer automorphism group is generated by the so-called Nielsen
transformations, which either permute the basis $\alpha,\beta$, or transform
it into $\alpha\beta,\beta$, or $\alpha\beta^{-1},\beta$. Both these latter
transformations can be realized topologically as Dehn twists on the holed
torus. We identify $\mathbb{Z}^{2}$ with the first homology of the holed torus
$\Sigma$ and will call the cover $\tilde{\Sigma}\rightarrow\Sigma$
corresponding to $\ker\phi$ the homology cover or maximal abelian cover of
$\Sigma$.

##  4\. Convexity of the length function

Let $\gamma\in\mathbb{Z}*\mathbb{Z}$ be some closed curve and
$\ell_{X}(\gamma)$ the minimum over the lengths wrt the hyperbolic structure
$X$ of all closed curves in the homotopy class of $\gamma$. In fact the
minimum is attained and is lthe length of the unique (oriented) closed
geodesic in the homotopy class.

######  Theorem 4.1.

The length function is convex on $H_{1}(X,\mathbb{Q})$ and so extends
continuously (as a convex function) to $H_{1}(X,\mathbb{R})$.

Since the proof is short and instructive we shall reproduce it now.

Let $X$ be a holed torus equipped with a hyperbolic structure. If $h$ is a
primitive homology class (that is, not a multiple of another class), then the
shortest multicurve representing a non-trivial homology class $h$ is a simple
closed geodesic and a multiple of such a geodesic otherwise. Further, the
shortest multicurve representing $h$ is unique.

Begin by defining a valuation $\ell$ on the first homology with integral
coefficients, where $\ell(h)$ is just the length of the shortest multicurve
representing h. The valuation of the trivial homology class is defined to be
0. By the previous paragraph $\ell$ statisfies

$\ell(nh)=n\ell(h),\forall n\in\mathbb{N}.$

Moreover if $h,g$ are not commensurable then $\ell$ satisfies the strict
triangle inequality

$\ell(h+g)<\ell(h)+\ell(g).$

This is because the union of the shortest multicurves representing $h$ and $g$
is not embedded, that is there is a transverse intersection somewhere. Hence,
the shortest multicurve representing $h+g$ is strictly shorter than the union
of the minimisers for $h,g$.

##  5\. Proof of Theorem 1.1.

Figure 2. Triples in a subtree of Markov’s tree. Figure 3. Corresponding
rationals in the Farey tree.

The correspondence between rationals and Markov numbers is determined by the
values at $0/1,1/2,1/1$ and, following [8] (see Figures 2 and 3), these are by
convention $(1,5,2)$. Now, passing from these fractions to primitive lattice
points we have the values of the norm at $(1,0),(2,1),(1,1)$ We can easily
find the value at $(0,1)$ using Vieta flipping and we see that it is $1$ ie
the same value as for $(1,0)$. In fact one can go a step further and show that
the three vectors $(1,0),(0,1),(-1,1)$ correspond to the fundamental triple of
Markov numbers $(1,1,1)$. The unit ball of the associated stable norm looks
just like the convex set depicted in Figure 1.

Now let $p,q$ be non negative real numbers as in the statement of Theorem 1.1.
For any $i$ the point $(q+i,p)$ lies on the line $y=p$. Since
$\ell:\mathbb{R}^{2}\mapsto\mathbb{R}_{+}$ is a proper convex function this
line meets the set

$S=\\{(x,y)\in\mathbb{R}^{2},\,\ell(x,y)=\ell(q,p)\\}$

in exactly two points one of which is $(q,p)$ and the other has a negative $x$
coordinate. It follows that for $i>0$ the point $(q+i,p)$ is outside of the
norm ball

$B=\\{(x,y)\in\mathbb{R}^{2},\,\ell(x,y)\leq\ell(q,p)\\}$

and the first part of the theorem follows.

A similar argument using a vertical line instead of a horizontal one yields a
proof of the second part of the Theorem 1.1.

Finally for the third part one must consider the line $(q,p)+i(-1,1)$. It is
easy to check that it meets $S$ in $(q,p)$ and $(p,q)$ and so for $i>0$ we
have the required inequality.

Figure 4. A portion of the set $B$ with the point $(q,p)$ on its boundary $S$
and the three lines (horizontal, vertical and diagonal) that appear in our
proof of the conjectures.

## References

  * [1] M. Aigner, Markov’s theorem and 100 years of the uniqueness conjecture. A mathematical journey from irrational numbers to perfect matchings. Springer, Cham, 2013.
  * [2] J. Berstel, A.Lauve, C. Reutenauer, F. Saliola. Combinatorics on Words: Christoffel Words and Repetitions in Words, CRM Monograph Series Volume: 27; 2008
  * [3] Buser, Peter, and K -D. Semmler. The geometry and spectrum of the one holed torus. Commentarii Mathematici Helvetici 63.1 (1988): 259-274.
  * [4] Harvey Cohn Approach to Markov’s Minimal Forms Through Modular Functions Annals of Mathematics Second Series, Vol. 61, No. 1 1955
  * [5] William M Goldman The modular group action on real SL(2)–characters of a one-holed torus Geom. Topol. Volume 7, Number 1 (2003), 443-486.
  * [6] Greg McShane, Hugo Parlier, Multiplicities of simple closed geodesics and hypersurfaces in Teichmüller space, Geom. Topol. Volume 12, Number 4 (2008), 1883-1919.
  * [7] Greg McShane, Igor Rivin A norm on homology of surfaces and counting simple geodesics International Mathematics Research Notices, Volume 1995, Issue 2, 1995
  * [8] M. Rabideaua, R. Schiffler, Continued fractions and orderings on the Markov numbers, Advances in Mathematics Vol 370, 2020.
  * [9] C Lagisquet and E. Pelantová and S. Tavenas and L. Vuillon, On the Markov numbers: fixed numerator, denominator, and sum conjectures. https://arxiv.org/abs/2010.10335
  * [10] Zagier, Don B. (1982). On the Number of Markov Numbers Below a Given Bound. Mathematics of Computation. 160 (160): 709–723