#  Quantum Key Distribution Routing Protocol in Quantum Networks: Overview and
Challenges

Pankaj Kumar  Student Member, IEEE Neel Kanth Kundu  Member, IEEE and Binayak
Kar  Member, IEEE P. Kumar and B. Kar are with Department of Computer Science
and Information Engineering, National Taiwan University of Science and
Technology, Taiwan (e-mail<EMAIL_ADDRESS>bkar@mail.ntust.edu.tw).
Neel Kanth Kundu is with the Centre for Applied Research in Electronics (CARE)
and Bharti School of Telecommunication Technology and Management (BSTTM),
Indian Institute of Technology (IIT) Delhi, New Delhi-110016, India (e-mail:
<EMAIL_ADDRESS>
###### Abstract

The use of quantum cryptography in everyday applications has gained attention
in both industrial and academic fields. Due to advancements in quantum
electronics, practical quantum devices are already available in the market,
and ready for wider use. Quantum Key Distribution (QKD) is a crucial aspect of
quantum cryptography, which involves generating and distributing symmetric
cryptographic keys between geographically separated users using principles of
quantum physics. Many successful QKD networks have been established to test
different solutions. The objective of this paper is to delve into the
potential of utilizing established routing design techniques in the context of
quantum key distribution, a field distinguished by its unique properties
rooted in the principles of quantum mechanics. However, the implementation of
these techniques poses substantial challenges, including quantum memory
decoherence, key rate generation, latency delays, inherent noise in quantum
systems, limited communication ranges, and the necessity for highly
specialized hardware. This paper conducts an in-depth examination of essential
research pertaining to the design methodologies for quantum key distribution.
It also explores the fundamental aspects of quantum routing and the associated
properties inherent to quantum QKD. This paper elucidates the necessary steps
for constructing efficient and resilient QKD networks. In summarizing the
techniques relevant to QKD networking and routing, including their underlying
principles, protocols, and challenges, this paper sheds light on potential
applications and delineates future research directions in this burgeoning
field.

##  I introduction

Creating secure cryptographic keys over untrusted networks is crucial [1].
While public key infrastructure, based on complex mathematical problems and
assumptions about the computational capability of eavesdroppers, is widely
used, it falls into the category of theoretically vulnerable computational
security solutions. With the continual advancement of computational power and
the emergence of quantum computing algorithms capable of solving complex
mathematical problems in polynomial time, such as Shor’s factoring algorithm
[2], new challenges and opportunities are on the horizon. Quantum Key
Distribution (QKD) operates on the principles of quantum information theory
and allows for the creation of information-theoretic secure cryptographic keys
[3].

To ensure the integrity and security of data packets traversing through the
QKD network, it is imperative to encrypt them using quantum secure keys. This
study emphasizes the significance of extending this security paradigm to the
routing packets themselves, highlighting the critical need to safeguard
routing data with quantum secure keys. In essence, QKD networks distinguish
themselves by their heavy reliance on quantum secure keys as a fundamental
element in their communication architecture [4]. Traditional routing
protocols, designed without the consideration of this unique feature of QKD
networks, pose a substantial challenge when directly applied within QKD
infrastructures. Such a direct application invariably results in the
suboptimal utilization of quantum secure keys. This underutilization is a
highly undesirable outcome, given the intrinsic value and scarcity of quantum
secure keys within the QKD network ecosystem. Consequently, the development
and implementation of a specialized routing protocol capable of achieving
efficient and high utilization of quantum secure keys emerge as critical
prerequisites for the practical deployment and success of QKD networks [5].

QKD networks exhibit substantial distinctions in comparison to conventional
telecommunication networks, primarily stemming from the unique characteristics
of QKD links and the intricacies of network organization. QKD encounters
several technical limitations. Such as low-key generation rates and
communication distance due to factors like photon detection efficiency,
transmission losses, and noise levels. The absence of practical quantum
repeaters poses a significant hurdle, as they are essential for extending
QKD’s range beyond its current limitations. QKD systems necessitate precise
routing strategies due to the coexistence of classical and quantum channels
within quantum links. Consequently, contemporary network architectures employ
a hop-by-hop approach for secure key distribution to navigate these
complexities effectively [6]. QKD Networks comprise several quantum repeaters
and trusted nodes that facilitate communication between Alice and Bob. These
components play a crucial role in enabling significantly extended
communication distances by reducing signal loss through shorter hops between
nodes. Additionally, trusted nodes perform measurements between parties,
enhancing security. Another advantage of QKD networks is the existence of
multiple paths between Alice and Bob, leading to increased key generation
rates as key bits are distilled on each connecting path in an additive manner
[7].

This paper focuses on the networking aspects of QKD with an emphasis on QKD
network organization, routing and signaling protocols, and software-defined
QKD networks. This paper aims to provide the readers with an insight into QKD
routing design from an engineering perspective. It is important to incorporate
the interdependence of conventional cryptography and QKD for the successful
design of QKD routing [8]. However, this interdependence remains poorly
understood despite its fundamental importance, leading to significant open
issues in QKD network design. The primary objective of this article is to
provide an understanding of strategies for designing QKD routing techniques in
quantum networks, empowering readers to:

  * •

Identify effective QKD routing protocol design methods within a quantum
network in order to comprehend the information flow within the network.

  * •

Analyze quantum networks from an engineering standpoint and gain proficiency
in understanding their operational modes, implementation approaches, currently
available solutions, and techniques for simulating quantum cryptographic
networks.

  * •

Provide a high-level perspective on the design of QKD networks with a focus on
applied quantum cryptography techniques for future communication networks.

Figure 1: QKD network architecture

The rest of the paper is structured as follows: In Section I, we provide an
overview of the QKD network. Section II presents QKD network architecture and
elements. The QKD routing design techniques are discussed in Section III and
future research direction in Section IV. Lastly, we summarize our findings and
conclusions in Section V.

##  II QKD NETWORK ARCHITECTURE AND ELEMENTS

###  II-A QKD Networks Architecture:

The QKD network cannot exist independently of the classical network, as it
necessitates an authenticated classical network and various secure
cryptographic functions within the classical network. The architecture of
networks can vary significantly, characterized by differing numbers of layers
based on their unique definitions and intended applications. The ITU-T Y.3800
recommendation [9] provides comprehensive insights into the conceptual
structures of both QKD networks and user networks. In the context of network
architectures that facilitate QKD, a comprehensive three-layer design has been
developed from a holistic perspective. This design draws inspiration from the
established six-layer network architecture. As illustrated in Figure 1, this
network architecture comprises three distinct logical layers.

_Infrastructure Layer:_ In Figure 1, the infrastructure layer of the QKD
network comprises a range of essential physical components necessary for QKD
networking. These components are strategically situated within secure and
dependable nodes, referred to as QKD nodes, with the primary objective of
safeguarding against potential physical attacks. QKD nodes have the capability
to establish connections in pairs through either optical fiber or free-space
links, facilitating the generation of secret keys in the form of symmetric
random bit sequences. Notably, these secret keys, being classical bit
sequences, are securely stored within the QKD nodes. Furthermore, each QKD
node diligently maintains comprehensive secret-key parameters, including
identifiers, sizes, transmission rates, key types, as well as physical device
identification, and timestamp records, which are utilized for both the
generation and storage of secret keys [6]. Additionally, QKD nodes retain
pertinent information concerning the link parameters, encompassing details
such as link length, type, and the error rate associated with quantum
channels.

_Control and Management Layer:_ In Figure 1, the higher-level layer consists
of the QKD network controller and manager, as described in [9]. The QKD
network controller is tasked with the responsibilities of activating,
deactivating, and calibrating all QKD nodes within the network. On the other
hand, the role of the QKD network manager involves the comprehensive oversight
and maintenance of the entire QKD network. This includes the continuous
monitoring of the status of all QKD nodes and links, along with real-time data
acquisition of secret-key parameters and link parameters from these nodes.
Additionally, the QKD network manager is responsible for supervising the
operations of the QKD network controller. Statistical information obtained
through monitoring and management is regularly collected, recorded, and
updated within a designated database to facilitate data analysis and
historical tracking. It’s important to highlight that the actual secret keys
stored within the QKD nodes are securely maintained in physically isolated
locations. This design ensures that the secret keys remain inaccessible to
both the QKD network controller and the network manager. This robust security
measure safeguards the secrecy of the keys, even with the introduction of the
control and management layer [10].

_Application Layer:_ The highest layer depicted in Figure 1 is the QKD
application layer, which encompasses cryptographic applications that are
integral to users of the QKD network. This process involves cryptographic
applications communicating their security requirements, such as specific
secret key specifications, to the QKD network manager. Subsequently, the
manager undertakes the task of verifying the availability of the requested
secret keys. If the requisite keys are indeed available, the manager proceeds
to instruct the QKD network controller to furnish these keys to the
applications for the purpose of data encryption. Upon receiving the supplied
secret keys, each application assumes responsibility for its management and
usage. It’s important to note that the capacity of a QKD network to
accommodate users is contingent upon the availability of resources and the
particular requirements of the users themselves [11].

###  II-B QKD Network Elements:

Considering the architecture of QKD networks, the corresponding QKD network
components can be delineated as follows:

_QKD Nodes:_ QKD nodes are essential components within a Quantum Key
Distribution network. These nodes play a crucial role in the establishment of
secure cryptographic keys based on the principles of quantum mechanics. QKD
nodes are responsible for generating cryptographic keys, often referred to as
quantum keys. These keys are created using the unique properties of quantum
mechanics, such as superposition and entanglement of photons, in order to
ensure their security against eavesdropping. These nodes are designed to be
physically secure to protect against tampering and attacks. Once quantum keys
are generated, QKD nodes are responsible for securely distributing these keys
to users or applications that require them for encryption and decryption
processes [1].

_QKD Network Controller:_ The QKD network controller shown in Figure 1 is a
centralized server responsible for managing QKD nodes within a QKD network
infrastructure. Its functions include activating, deactivating, and
calibrating QKD nodes. The QKD network controller assumes critical
responsibilities in network management. These encompass essential network
control functions such as QKD connection management, which includes tasks like
node access and authentication. The controller also manages routing control,
enabling secret-key relay and facilitating failure recovery within the
network. Additionally, it plays a pivotal role in Quality of Service (QoS)
control, encompassing aspects like customization and ensuring end-to-end QoS
assurance.

_Cryptographic Application:_ The top layer in Figure 1 represents a
cryptographic application, which is essentially a user with particular
security requirements. These requirements typically involve requests for
cryptographic keys, specifying details like key size, rate, and key refresh
rate. Importantly, a cryptographic application is usually co-located in the
same physical location as a QKD node to receive the secret keys. This
proximity is essential for the secure exchange of keys.

Figure 2: SDN-based QKD

##  III Routing Design Techniques for QKD Networks

Over the recent years, substantial strides have been taken to tackle the
technical hurdles associated with practical QKD networking. This section
delves into an extensive examination of the design methodologies introduced
for QKD networks, encompassing Software-Defined Networking (SDN), routing
strategies, overlay solutions, and switch-centric QKD approaches.

####  III-1 SDN-based QKD

The QKD scheme proposed in [12] aims to make QKD systems compatible with SDN
principles. This involves creating a model for QKD systems that aligns them
with traditional network elements like routers and switches. This model
necessitates careful consideration of which QKD capabilities and parameters
are relevant from a network management perspective. For instance, the
intricate nature of QKD systems, with multiple complex hardware and software
components, needs to be abstracted to simplify interaction with the SDN
controller. Additionally, sensitive data like internal information and actual
key material must be kept confidential to ensure the security of the QKD
network. This model serves several purposes: it promotes the adoption of
standard interfaces, reducing time-to-market for solutions that previously
relied on custom ad-hoc implementations. It leverages SDN technologies for
optical networks to improve quantum channel spectrum allocation. Furthermore,
centralizing QKD network management enhances the optimization of key
generation and utilization while maintaining a centralized database of active
links and consumer applications.

The network involves aggregating and abstracting QKD systems within the same
secure area as logical network elements. This is represented in the node
architecture, where various QKD systems are controlled within the Software-
Defined QKD (SD-QKD) node shown in Figure 2. The SD-QKD node model comprises
four essential components:

  1. (a)

Interfaces: These encompass all the QKD systems that are consolidated within
an SD-QKD node. These interfaces facilitate the interaction between the node
and the QKD systems.

  2. (b)

Applications: Applications can be either internal or external entities that
make use of keys obtained from the node’s Key Management System (KMS). These
keys are crucial for secure communications and are accessed by various
applications.

  3. (c)

Links: These are akin to key connections between two SD-QKD nodes. These links
can take on two forms: physical connections via a quantum channel or virtual
connections established through trusted relay mechanisms. They play a pivotal
role in securing the communication between nodes.

  4. (d)

Capabilities and additional information: This component encompasses
supplementary data, including identifiers and geographical locations. It also
provides support for various operations required for the effective functioning
of the SDQKD node. These capabilities and additional information are crucial
for managing and optimizing the quantum key distribution network.

These physical QKD systems create quantum channels and generate quantum secure
keys, which are managed by KMS. Finally, an SDN agent plays a crucial role in
gathering data from the QKD node, establishing communication with the SDN
controller, and implementing configuration updates as requested by the QKD
controller. This requires the agent to coordinate with other elements within
the node, such as the KMS and the QKD systems.

Figure 3: Routing and key pool-based QKD

####  III-2 Routing and key pool-based QKD

A graph theoretic-based QKD network routing model was described in [11]. In
this paper, it is assumed that the QKD network comprises many independent
point-to-point (P2P) QKD systems and each P2P QKD system continuously
generates a secret key for two adjacent end nodes. In the QKD network, all
nodes are interconnected in the classical networking perspective, however,
quantum channels are only present between specific nodes. Additionally, each
node has the capability to establish a neighbor relationship solely with nodes
directly linked by quantum channels. Figure 3 shows a topology of the QKD
network.

Every node within the network possesses two distinct communication channels: a
classical channel and a quantum channel. The classical channel functions as a
virtual connection within the classical network and is represented by a dotted
line in Figure 3. Its primary purpose is to facilitate the transmission of
essential network control information, encrypted data, and similar content. On
the other hand, the quantum channel is formed through the optical fibers
linking two neighboring nodes, depicted as a solid line in Figure 3. The
primary role of the quantum channel is to facilitate the creation of secret
keys for each QKD system. The key generated by the P2P QKD system is the local
key. In the QKD network, each P2P QKD system operates autonomously and in a
continuous manner to generate local keys for the two nodes at either end of
the communication link. These local keys are subsequently stored in dedicated
secret key pools, referred to as local key pools. The concept of a local key
serves as the fundamental building block for establishing secure keys for
users within a network. These locally usable keys are securely stored in what
we term a residual local key pool. In specific scenarios [13], where a quantum
channel is unavailable, the generation of a local key between two distant end
nodes becomes challenging. In such circumstances, these two end nodes have no
choice but to establish shared keys through a relay process with the
assistance of multiple intermediate nodes. The keys generated through this
relaying process, which we refer to as global keys, necessitate the
utilization of a specific quantity of local key resources for their creation
and maintenance. This approach ensures that secure communication is maintained
even when faced with the absence of a direct quantum channel, allowing for the
establishment of shared keys through a collaborative network effort. This
global key serves as the actual secret key employed for secure communication
among users, encompassing activities like voice calls, video chats, and file
transfers. Consequently, the global key can be established between nodes that
are either far apart or adjacent to each other. To ensure secure
communication, when two neighboring nodes require a global key, they can
directly utilize the local keys they share as the global key. In cases where
nodes are not adjacent and still require a global key, they must acquire it
through a process involving multiple intermediary nodes facilitating the relay
of keys. The procedure by which nodes acquire a global key is commonly
referred to as key exchange. During the exchange of the global key from its
source to its intended destination, it often traverses multiple intermediate
QKD links. This intermediate QKD link collection is collectively called the
relaying path.

Figure 4: Trusted repeater-based QKD

####  III-3 Trusted repeater-based QKD

Point-to-point QKD encounters limitations arising from various physical-layer
impediments. These include issues like scattering and the attenuation of
quantum signals during their passage through quantum channels. Additionally,
it is worth noting that quantum states of light cannot be amplified. This is
due to the fundamental requirement of measuring and cloning a quantum state of
light, which, as outlined in the quantum no-cloning theorem [14], is
inherently impossible. Consequently, the establishment of long-distance end-
to-end QKD connections necessitates the integration of repeater technologies.
Quantum repeaters, defined as devices capable of forwarding qubits without
engaging in measurement or cloning processes, continue to pose challenges in
practical QKD network implementations. The trusted repeater technique has
emerged as a pragmatic solution to address this challenge, commonly employed
in real-world QKD networks. This approach leverages intermediate nodes
equipped with trusted repeaters, facilitating the gradual transmission of
secret keys along the QKD path, originating from the source node and
culminating at the destination node. In this process, secret keys undergo
decryption and subsequent re-encryption. This operation is executed using an
information-theoretically secure One-Time Pad (OTP) cryptographic algorithm
[2] at each intermediate node.

Figure 4 shows long-distance end-to-end QKD based on trusted repeaters. We’ve
strategically positioned two intermediate nodes equipped with trusted
repeaters for the source and destination nodes. This setup facilitates secure
communication within a QKD framework [11]. The QKD sender is linked to the QKD
receiver through a combination of Quantum channels and public channels. The
key objective here is to establish three distinct secret keys, each serving
specific communication segments: the source node to the intermediate node 1,
intermediate node 1 to intermediate node 2, and intermediate node 2 to the
destination node. It’s important to note that all three secret keys share
identical key sizes, ensuring uniform cryptographic strength across the
communication path. The process unfolds in a series of meticulously
orchestrated steps:

  1. (a)

Source node to Intermediate node 1: In the first step, a secret key is
generated securely between the source node and intermediate node 1. This step
is vital as it forms the foundation for secure communication between the
source and the initial intermediate node.

  2. (b)

Intermediate node 1 to Intermediate node 2: The second step involves the
creation of a secret key, establishing a secure link between Intermediate Node
1 and Intermediate Node 2. This intermediary key bridges the gap between the
two consecutive nodes, ensuring the confidentiality and integrity of the data
in transit.

  3. (c)

Intermediate Node 2 to Destination node: Finally, in the third step, a secret
key is generated to establish secure communication between intermediate node 2
and the destination node. This last link in the chain ensures the end-to-end
security of the communication, safeguarding data as it reaches its intended
destination.

This meticulous three-step process, enabled by the strategic placement of
intermediate nodes with trusted repeaters, allows for the generation of three
distinct secret keys, each with uniform key sizes, to secure the communication
channels between the source node and the destination node. This approach
ensures the confidentiality and integrity of data throughout its paths.

Figure 5: Overlay-based QKD

####  III-4 Overlay-based QKD

The previously discussed QKD network types deal with the arrangement of
quantum channels, whereas the QKD overlay network type is focused on the
realization of public channels. The primary objective of the overlay network
is to establish a higher-level network structure to enhance QoS and make
efficient use of resources from lower-level networks. In pursuing this goal,
the overlay network seeks to operate independently of predefined paths set by
Internet Service Providers (ISPs). Key characteristics of the overlay network
approach include the ability to discover alternative routes that offer
superior service quality and rapid rerouting in case of interruptions, as well
as the utilization of multipath communications [15]. Employing multipath
connections is a frequently recommended solution for enhancing network
performance, encompassing safeguards against network failures, distribution of
network loads, implementation of high bandwidth capabilities, and selection of
low-delay pathways [10].

The use of external routing protocols like the Border Gateway Protocol (BGP)
for routing between network domains is acknowledged to result in sluggish
response times and delayed recovery from network disruptions. This is
primarily due to the time it takes to gather information about network link
interruptions or congestion, as well as the typically configured minimum route
advertisement interval timer in BGP, which often operates on a timescale of
minutes. Consequently, the process of achieving a consistent network view
following a link outage can extend to tens of minutes, a substantial timeframe
that poses challenges for network applications. Moreover, BGP’s propagation of
only a single route makes it challenging for network nodes to detect
alternative routes in various scenarios [15].

To address these challenges, the overlay network adopts a peer-to-peer
approach, facilitating connections between nodes in diverse domains and
enabling the utilization of alternative pathways through traffic encapsulation
within the lower network. As a packet traverses the path, intermediate nodes
receive it, unbox the packet, scrutinize the recipient’s IP address, re-
encapsulate the packet, and then transmit it onward to potential network nodes
in other domains. Essentially, it operates as a step-by-step process commonly
implemented in QKD networking shown in Figure 5. Leveraging the encapsulation
principle, overlay nodes autonomously gauge link conditions and can promptly
respond to congestion by diverting traffic towards less congested routes.
Overlay networks introduce novel capabilities that are challenging to achieve
within lower-level networks. The appeal of the overlay QKD approach lies in
its ability to bypass ”untrusted” nodes and swiftly reconfigure routes when
trust in certain nodes becomes compromised or when multipath communication is
essential [8].

##  IV Future Research Directions

_1) Quantum repeaters:_ Quantum repeaters are essential for extending the
reach of QKD networks beyond their current limitations. One of the primary
limitations of traditional QKD is the distance over which quantum keys can be
reliably transmitted. Quantum signals are susceptible to attenuation and loss
over long distances. Quantum repeaters address this limitation by effectively
”renewing” and forwarding quantum information, allowing secure communication
over much greater distances. In a QKD network, quantum signals can degrade
significantly as they pass through optical fibers or other communication
channels. Quantum repeaters mitigate this loss by actively enhancing and
amplifying the quantum signals while preserving their quantum properties. This
ensures that the quantum keys remain secure and usable over extended
distances. Future work should focus on the development of efficient and
practical quantum repeater protocols and technologies, which can enable secure
communication over longer distances.

_2) High-rate QKD:_ Traditional QKD systems have been limited by relatively
low-key generation rates. These systems could not match the data transfer
rates commonly used in modern networks and applications. This limitation made
QKD less practical for high-speed data transmission needs, such as those in
data centers, financial institutions, and critical infrastructure sectors.
Low-key generation rates have been primarily attributed to the nature of
quantum signals and the stringent security requirements of QKD. Quantum
signals, typically carried by individual photons, have inherently low signal-
to-noise ratios, leading to slow key generation processes. Moreover, the
security of QKD relies on the need for extremely long and random keys, further
impeding the rate at which keys can be produced.

_3) Quantum network topologies:_ The choice of quantum network topology is a
critical decision that can significantly impact the performance, security, and
scalability of a Quantum Key Distribution network. A well-designed topology
considers the unique properties of quantum communication while aligning with
the network’s goals and applications [14]. It plays a central role in ensuring
the reliable and secure exchange of quantum keys across distributed nodes and
users.

_4) Quantum cryptography protocol:_ A Quantum network protocol in QKD networks
is a set of rules and procedures governing the exchange of quantum
information, primarily quantum keys, among multiple network nodes in a secure
and efficient manner. These protocols are designed to harness the principles
of quantum mechanics to establish cryptographic keys with provable security
properties, such as resistance to eavesdropping attacks. Quantum network
protocols dictate how quantum states, often in the form of entangled particles
or qubits, are generated, transmitted, and measured between different nodes
within the network [11]. They also include procedures for error correction,
privacy amplification, and key distillation to ensure the final keys are both
secure and reliable.

_5) Practical implementations and cost reduction:_ Practical implementations
and cost reduction are pivotal considerations in the development of QKD
networks. To make quantum communication technology feasible for real-world
applications, researchers and engineers are focused on creating more compact,
robust, and affordable QKD hardware and infrastructure. Practical
implementations involve designing QKD systems that are easy to install and
maintain, even in resource-constrained environments. Furthermore, cost
reduction efforts seek to bring down the expenses associated with QKD
networks, including the cost of specialized quantum components, integration
into existing networks, and overall operational costs. Achieving practicality
and cost-effectiveness is critical to making QKD accessible to a broader range
of users and industries, ultimately driving the adoption of quantum-secure
communication solutions in sectors such as finance, healthcare, and
telecommunications.

##  V Conclusion

QKD networks offer the promise of long-term data security and robust
protection for a wide array of applications. However, they are not without
their share of unresolved challenges and open questions. This paper aims to
provide a comprehensive overview, delving into past accomplishments while
offering insights into the future of QKD networks. This work categorizes
various options for implementing QKD networks and reviews their development,
encompassing trusted repeaters, SDN architectures, and routing-based key pools
within QKD networks [16]. Furthermore, the paper presents a detailed
examination of the general architecture of QKD networks, highlighting the
constituent elements, interfaces, and protocols involved. This paper outlines
a promising set of research directions that point toward the initial steps in
shaping the quantum internet. Achieving comprehensive progress in QKD network
development will necessitate collaborative efforts across multiple domains,
including physics, computer science, security, and communications.

## References

  * [1] U. M. Maurer, “Secret key agreement by public discussion from common information,” _IEEE transactions on information theory_ , vol. 39, no. 3, pp. 733–742, 1993.
  * [2] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in _Proceedings 35th annual symposium on foundations of computer science_. Ieee, 1994, pp. 124–134.
  * [3] P. W. Shor and J. Preskill, “Simple proof of security of the BB84 quantum key distribution protocol,” _Physical review letters_ , vol. 85, no. 2, p. 441, 2000.
  * [4] H. Nejatollahi, N. Dutt, S. Ray, F. Regazzoni, I. Banerjee, and R. Cammarota, “Post-quantum lattice-based cryptography implementations: A survey,” _ACM Computing Surveys (CSUR)_ , vol. 51, no. 6, pp. 1–41, 2019.
  * [5] X. Zou, X. Yu, Y. Zhao, A. Nag, and J. Zhang, “Collaborative routing in partially-trusted relay based quantum key distribution optical networks,” in _2020 Optical Fiber Communications Conference and Exhibition (OFC)_. IEEE, 2020, pp. 1–3.
  * [6] Q. Wang, X. Yu, Q. Zhu, Y. Zhao, and J. Zhang, “Quantum key pool construction and key distribution scheme in multi-domain qkd optical networks (qkd-on),” in _4th Optics Young Scientist Summit (OYSS 2020)_ , vol. 11781. SPIE, 2021, pp. 509–512.
  * [7] Y. Cao, Y. Zhao, Q. Wang, J. Zhang, S. X. Ng, and L. Hanzo, “The evolution of quantum key distribution networks: On the road to the qinternet,” _IEEE Communications Surveys & Tutorials_, vol. 24, no. 2, pp. 839–894, 2022.
  * [8] E. Schoute, L. Mancinska, T. Islam, I. Kerenidis, and S. Wehner, “Shortcuts to quantum network routing,” _arXiv preprint arXiv:1610.05238_ , 2016.
  * [9] I. Recommendation, “Y. 3800: Overview on networks supporting quantum key distribution,” _International Telecommunication Union: Geneva, Switzerland_ , 2019.
  * [10] O. Amer, W. O. Krawec, and B. Wang, “Efficient routing for quantum key distribution networks,” in _2020 IEEE International Conference on Quantum Computing and Engineering (QCE)_. IEEE, 2020, pp. 137–147.
  * [11] C. Yang, H. Zhang, and J. Su, “Quantum key distribution network: Optimal secret-key-aware routing method for trust relaying,” _China Communications_ , vol. 15, no. 2, pp. 33–45, 2018.
  * [12] A. Aguado, V. Lopez, D. Lopez, M. Peev, A. Poppe, A. Pastor, J. Folgueira, and V. Martin, “The engineering of software-defined quantum key distribution networks,” _IEEE Communications Magazine_ , vol. 57, no. 7, pp. 20–26, 2019\.
  * [13] S. DiAdamo, B. Qi, G. Miller, R. Kompella, and A. Shabani, “Packet switching in quantum networks: A path to the quantum internet,” _Physical Review Research_ , vol. 4, no. 4, p. 043064, 2022.
  * [14] M. Mehic, M. Niemiec, S. Rass, J. Ma, M. Peev, A. Aguado, V. Martin, S. Schauer, A. Poppe, C. Pacher _et al._ , “Quantum key distribution: a networking perspective,” _ACM Computing Surveys (CSUR)_ , vol. 53, no. 5, pp. 1–41, 2020.
  * [15] B. Kar and P. Kumar, “Routing protocols for quantum networks: Overview and challenges,” _arXiv preprint arXiv:2305.00708_ , 2023.
  * [16] B. M. Waxman, “Routing of multipoint connections,” _IEEE journal on selected areas in communications_ , vol. 6, no. 9, pp. 1617–1622, 1988.

Pankaj Kumar earned his M.Tech. degree in computer science and engineering
from the Indian Institute of Technology (ISM) in Dhanbad, India. He is
currently pursuing a Ph.D. degree in computer science and information
engineering (CSIE) at National Taiwan University of Science and Technology
(NTUST), Taiwan. His research focuses on network design, quantum algorithms,
quantum information theory, quantum communications, and QKD networks.
---
Neel Kanth Kundu is an Assistant Professor at the Centre for Applied Research
in Electronics (CARE) and Bharti School of Telecommunication Technology and
Management, Indian Institute of Technology Delhi. He received his Ph.D. degree
in electronic and computer engineering with a concentration in scientific
computation from The Hong Kong University of Science and Technology, Clear
Water Bay, Hong Kong in 2022. He was a postdoctoral research fellow with the
Department of Electronic and Electrical Engineering at the University of
Melbourne, Australia from February 2023 to October 2023. His research
interests include signal processing for 6G wireless communications, quantum
communications, and quantum information processing.
---
Binayak Kar is an Assistant Professor of computer science and information
engineering at National Taiwan University of Science and Technology (NTUST),
Taiwan. He received his Ph.D. degree in computer science and information
engineering from the National Central University (NCU), Taiwan, in 2018. He
was a post-doctoral research fellow in computer science at National Chiao Tung
University (NCTU), Taiwan, from 2018 to 2019. His research interests include
network softwarization, cloud/edge/fog computing, optimization, queueing
theory, machine learning, cyber security, and quantum computing.
---


# The automorphism group of the random poset does not admit a generic pair

Aleksandra Kwiatkowska  Institut für Mathematische Logik und
Grundlagenforschung, Westfalische Wilhelms-Universität Münster, Einsteinstr.
62, 48149 Münster, Germany And Instytut Matematyczny, Uniwersytet Wrocławski,
pl. Grunwaldzki 2/4, 50-384 Wrocław, Poland<EMAIL_ADDRESS>and
Aristotelis Panagiotopoulos  Institut für Mathematische Logik und
Grundlagenforschung, Westfalische Wilhelms-Universität Münster, Einsteinstr.
62, 48149 Münster, Germany And JG<EMAIL_ADDRESS>
###### Abstract.

We show that the conjugacy class of every pair of automoprhisms of the random
poset is meager. This answers a question of Truss; see also Kuske-Truss.

###### Key words and phrases:

Random poset, universal poset, ample generics, mutual genericity, small index
property, ultrahomogeneous structure, automorphism group

###### 2000 Mathematics Subject Classification:

20B27, 06A99

We would like to thank A.S. Kechris for his feedback on an earlier draft of
this paper.

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation) under Germany’s Excellence Strategy EXC 2044–390685587,
Mathematics Münster: Dynamics–Geometry–Structure and by CRC 1442 Geometry:
Deformations and Rigidity.

A.K. additionally was supported by Narodowe Centrum Nauki grant
2016/23/D/ST1/01097.

##  1\. Introduction

Some of the most well-studied properties of Polish groups concern the
interactions between the topological and algebraic structure of such groups.
Indeed, properties such as the _small index property_ , the _automatic
continuity_ , and the _Bergman property_ are often used to evaluate how much
of the topology and the dynamical properties of a Polish group $G$ can be
recovered from its pure algebraic structure. While most of these properties
rarely occur in the realm of locally compact Polish groups, they tend to be a
typical feature of automorphism groups $\mathrm{Aut}(M)$ of classical
ultrahomogeneous structures $M$, such as the _random graph_ and the linear
ordering $(\mathbb{Q},<)$.

That being said, there are still two structures among these classical examples
for which it remains open whether their automorphism groups satisfy any of the
above properties—namely, the _random poset_ $(P,<)$ and the _random
tournament_ $(T,\rightarrow)$. The main obstacle here is that the only known
techniques we have for establishing such properties for an automorphism group
$\mathrm{Aut}(M)$ use either the existence of elements $g\in\mathrm{Aut}(M)$
with “small” _support_ $\mathrm{supp}(g):=\\{a\in M\mid g(a)\neq a\\}$, see
[1, 8]; or require $\mathrm{Aut}(M)$ to satisfy a relatively stronger property
known as _ample generics_ [4]. However, both $\mathrm{Aut}(P,<)$ and
$\mathrm{Aut}(T,\rightarrow)$ fail to have elements with “small” support (see
[2, Lemma 3.1] and [7, Lemma 2.9]) and for both structures it has been a long-
standing open question whether their automorphism groups have ample generics
(for $\mathrm{Aut}(P,<)$, see [5, 10]; for $\mathrm{Aut}(T,\rightarrow)$, see
[3] and [9, Proposition 6.3.1]). In this paper we settle the later question
for $(P,<)$ in the negative. As a consequence, any potential proof that
$\mathrm{Aut}(P,<)$ has, say, the automatic continuity property, would truly
have to involve novel techniques.

### Defintions and notation

A poset (partially ordered set) is a structure $(N,<_{N})$ so that for all
$a,b,c\in N$ we have that: $(a<_{N}b)\wedge(b<_{N}c)$ implies $a<_{N}c$; and
$a\not<_{N}a$. We write $a\perp b$ whenever $a\neq b$ and both $a\not<_{N}b$,
$b\not<_{N}a$ hold. An embedding of posets $f\colon(A,<_{A})\to(B,<_{B})$ is
any injective function $f\colon A\to B$ so that
$(a<_{A}a^{\prime})\iff(f(a)<_{B}f(a^{\prime}))$. The random poset
$\mathcal{P}$ is the unique up to isomorphism countable poset $(P,<_{P})$ so
that:

  1. (1)

every finite poset embeds in $\mathcal{P}$;

  2. (2)

if $f,g\colon(A,<_{A})\to\mathcal{P}$ are two embeddings and $A$ is finite,
then $\varphi\circ f=g$ for some automorphism
$\varphi\in\mathrm{Aut}(\mathcal{P})$ of $\mathcal{P}$.

Below we view the automorphism group $\mathrm{Aut}(\mathcal{P})$ of
$\mathcal{P}$ as a Polish group endowed with the pointwise convergence
topology. Let $G$ be a Polish group. We say that $f\in G$ is generic if the
conjugacy class $\\{gfg^{-1}\colon g\in G\\}$ of $f$ is comeager. Furthermore,
$(f_{1},f_{2})\in G^{2}$ is a generic pair if the conjugacy class
$\\{(gf_{1}g^{-1},gf_{2}g^{-1})\colon g\in G\\}$ of $(f_{1},f_{2})$ is
comeager in $G^{2}$. More generally, we say that $G$ has ample generics if for
every $n\geq 1$ there exists $(f_{1},\ldots,f_{n})$ whose diagonal conjugacy
class $\\{(gf_{1}g^{-1},\ldots,gf_{n}g^{-1})\colon g\in G\\}$ is comeager in
$G^{n}$.

Kuske-Truss [5] showed that $\mathrm{Aut}(\mathcal{P})$ has a generic
automorphism. In Section 3 of the same paper they remark that the next
principal goal should be to establish that ${\rm Aut}(\mathcal{P})$ has ample
generics and to use this as a mean to prove that ${\rm Aut}(\mathcal{P})$ has
the small index property. They also point out that merely the existence of a
generic pair in ${\rm Aut}(\mathcal{P})$ could be used to streamline the proof
of the fact that ${\rm Aut}(\mathcal{P})$ is simple, see [2]. The question of
whether ${\rm Aut}(P)$ has a generic pair reappears in [5, Question 3]. The
following is the main result of this article.

######  Theorem 1.

The automorphism group $\mathrm{Aut}(\mathcal{P})$ of the random poset
$\mathcal{P}$ does not have a generic pair. In fact, for every
$(f_{1},f_{2})\in\mathrm{Aut}(\mathcal{P})^{2}$ the diagonal conjugacy class
$\\{(gf_{1}g^{-1},gf_{2}g^{-1})\colon g\in\mathrm{Aut}(\mathcal{P})\\}$ of
$(f_{1},f_{2})$ is meager in $\mathrm{Aut}(\mathcal{P})^{2}$.

##  2\. Proof of Theorem 1

We start by reformulating the statement of Theorem 1 in combinatorial terms.
For this we will make use of results from [4].

A partial automorphism is a triple $(A,<_{A},f_{A})$, where $(A,<_{A})$ is a
finite poset and $f_{A}\colon A\rightharpoonup A$ is a partial map, which
induces an isomorphism between $\mathrm{dom}(f_{A})$ and
$\mathrm{rng}(f_{A})$. In what follows we will identify such $f_{A}$ with its
graph, i.e., $f_{A}\subseteq A^{2}$. By an embedding
$\alpha\colon(A,<_{A},f_{A})\to(B,<_{B},f_{B})$ of partial automorphisms we
mean any embedding $\alpha\colon(A,<_{A})\to(B,<_{B})$ of posets so that
$\mathrm{rng}(\alpha\upharpoonright\mathrm{dom}(f_{A}))\subseteq\mathrm{dom}(f_{B})$
and $f_{B}\circ\alpha=\alpha\circ f_{A}$, for every $a\in\mathrm{dom}(f_{A})$.
A pair of partial automorphisms is a quadruple $(A,<,f_{A},g_{A})$, so that
both $(A,<_{A},f_{A})$ and $(A,<_{A},g_{A})$ are partial automorphisms. By an
embedding $\alpha\colon(A,<_{A},f_{A},g_{A})\to(B,<_{B},f_{B},g_{B})$ of pairs
of partial automorphisms we mean any map $\alpha\colon A\to B$ which induces
embeddings $\alpha\colon(A,<_{A},f_{A})\to(B,<_{B},f_{B})$ and
$\alpha\colon(A,<_{A},g_{A})\to(B,<_{B},g_{B})$ of partial automorphisms. We
say that $(B,<_{B},f_{B},g_{B})$ extends $(A,<_{A},f_{A},g_{A})$ and write

$(A,<_{A},f_{A},g_{A})\preceq(B,<_{B},f_{B},g_{B}),$

if the inclusion $A\subseteq B$ induces an embedding of pairs of partial
automorphisms. Similarly we will define the extension
$(A,<_{A})\preceq(B,<_{B})$ between posets and the extension
$(A,<_{A},f_{A})\preceq(B,<_{B},f_{B})$ between partial automorphisms—notice
that posets and partial automorphisms can be viewed as special types of pairs
of partial automorphisms $(A,<_{A},f_{A},g_{A})$ where either both
$f_{A},g_{A}$ or only $g_{A}$ are equal to the empty partial map $\emptyset$.

Let $\mathcal{A}$ be the category of embeddings between pairs of partial
automorphisms. By [4, Theorem 2.11], the action of ${\rm Aut}(\mathcal{P})$ on
$\big{(}{\rm Aut}(\mathcal{P})\big{)}^{2}$ by conjugation
$g\cdot(f_{1},f_{2})\mapsto(gf_{1}g^{-1},gf_{2}g^{-1})$ has a dense orbit if
and only if $\mathcal{A}$ has the _joint embedding property_ and by [4,
Theorem 6.2] ${\rm Aut}(\mathcal{P})$ has a generic pair if and only if the
category $\mathcal{A}$ has both the _joint embedding property_ and the _weak
amalgamation property_. Recall that a category $\mathcal{C}$ has the Joint
Embedding Property (JEP) if for any two objects $A,B\in\mathcal{C}$ there
exists $C\in\mathcal{C}$ which embeds both $A$ and $B$. A category
$\mathcal{C}$ has the Weak Amalgamation Property (WAP) if for every object
$A\in\mathcal{C}$ there is $\alpha\colon A\to\widetilde{A}$ in $\mathcal{C}$
so that for all $\beta\colon\widetilde{A}\to B$ and
$\gamma\colon\widetilde{A}\to C$ in $\mathcal{C}$ there are
$\beta^{\prime}\colon B\to D$ and $\gamma^{\prime}\colon C\to D$ in
$\mathcal{C}$, so that
$\beta^{\prime}\circ\beta\circ\alpha=\gamma^{\prime}\circ\gamma\circ\alpha.$

Notice that the continuous action of a Polish group with a dense orbit does
not contain any orbits which are neither meager nor comeager. Hence, by the
previous paragraph, Theorem 1 follows from the following result.

######  Theorem 2.

The category $\mathcal{A}$ has JEP but does not have WAP.

The fact that $\mathcal{A}$ has JEP is straightforward. Indeed, let
$(A,<_{A},f_{A},g_{A})\in\mathcal{A}$ and
$(B,<_{B},f_{B},g_{B})\in\mathcal{A}$ and assume without loss of generality
that $A\cap B=\emptyset$. Then both pairs of partial automorphisms embed to
the partial automorphism $(C,<_{C},f_{C},g_{C})$, where $C:=A\cup B$, $<_{C}$
is the partial order $<_{A}\cup\;\\{(a,b)\mid a\in A,b\in B\\}\;\cup<_{B}$,
$f_{C}:=f_{A}\cup f_{B}$, and $g_{C}:=g_{A}\cup g_{B}$.

The rest of this paper is devoted to showing that $\mathcal{A}$ does not have
WAP. We start with some definitions. Let $(A,<_{A})\preceq(B,<_{B})$ be an
extension of posets and let $b\in B$. The quantifier free type of $b$ over $A$
in $(B,<)$, denoted by $\mathrm{qft}\big{(}b,A,(B,<_{B})\big{)}$, is the
collection of all formulas $\varphi(x)$ in some fixed variable $x$ of the
form:

$\varphi(x)\equiv(x<a)\;\;\text{ or }\;\;\varphi(x)\equiv(x>a)\;\;\text{ or
}\;\;\varphi(x)\equiv(x=a),$

where $a\in A$ and $\varphi(b)$ holds in $(B,<_{B})$. A quantifier free type
$p(x)$ over $A$ is any collection of the form
$\mathrm{qft}\big{(}c,A,(C,<_{C})\big{)}$, where $(A,<_{A})\preceq(C,<_{C})$
and $c\in C$.

If $p(x)$ is a quantifier free type over some poset $(A,<_{A})$ and
$\alpha\colon(A,<_{A})\to(B,<_{B})$ is an isomorphism, then we denote by
$p[\alpha](x)$ the push forward of $p$ by $\alpha$. This is the new quantifier
free type over $(B,<_{B})$ attained by setting for each $b\in B$:

$\displaystyle(x<b)\in p[\alpha](x)\iff(x<\alpha^{-1}(b))\in p(x)$
$\displaystyle(x>b)\in p[\alpha](x)\iff(x>\alpha^{-1}(b))\in p(x)$
$\displaystyle(x=b)\in p[\alpha](x)\iff(x=\alpha^{-1}(b))\in p(x)$

We record the following simple fact which we are going to use extensively
below.

######  Fact 1.

Let $(C,<_{C},g)$ be a partial automorphism and let $c,d\in C$. If
$p[g](x)=q[x]$, where
$p(x):=\mathrm{qft}\big{(}c,\mathrm{dom}(g),(C,<_{C})\big{)}$ and
$q(x):=\mathrm{qft}\big{(}d,\mathrm{rng}(g),(C,<_{C})\big{)}$, then the map
$g^{\prime}:=g\cup\\{(c,d)\\}$ induces a new partial automorphism
$(C,<_{C},g^{\prime})$.

Let $(B,<_{B},f_{B})$ be a partial automorphism and let $a,b\in B$ with
$a<_{B}b$. We say that $f_{B}$ is free in $(a,b)$, if whenever
$(B,<_{B})\preceq(C,<_{C})$ and $c_{1},\ldots,c_{\ell}\in C$, with
$a<_{C}c_{1}<_{C}\cdots<_{C}c_{\ell}<_{C}b$, then $(C,<_{C},f_{C})$ is a
partial automorphism, where

$f_{C}:=f_{B}\cup\\{(a,c_{1}),(c_{1},c_{2}),\ldots,(c_{\ell-1},c_{\ell})\\}.$

######  Lemma 1.

Let $(A,<_{A},f_{A})$ be a partial automorphism and let $s\in A$ with
$s<_{A}f_{A}(s)$. Then, there is an extension
$(A,<_{A},f_{A})\preceq(B,<_{B},f_{B})$, some $n\in\mathbb{N}$, and $a,b\in B$
with $a<_{B}b$, so that $f_{B}^{n}(s)=a$ and $f_{B}$ is free in $(a,b)$.

###### Proof.

Let $\\{a_{1},\ldots,a_{k}\\}$ be an enumeration of $A$ and set
$(A_{0},<_{0},f_{0}):=(A,<_{A},f_{A})$. Assume that for some $i<k$ we have
defined partial automorphisms

$(A_{0},<_{0},f_{0})\preceq(A_{1},<_{1},f_{1})\preceq\cdots\preceq(A_{i},<_{i},f_{i}),$

so that for some $n_{i}\in\mathbb{N}$ we have that

$f_{i}=f_{A}\cup\\{(s,f_{i}(s)),(f_{i}(s),f^{2}_{i}(s)),\ldots,(f^{n_{i}-1}_{i}(s),f_{i}^{n_{i}}(s))\\}.$

We define a further extension
$(A_{i},<_{i},f_{i})\preceq(A_{i+1},<_{i+1},f_{i+1})$ as follows:

Case 1. If there is a partial automorphism $(D,<_{D},f_{D})$ which extends
$(A_{i},<_{i},f_{i})$, and some $m\geq n_{i}$ so that $f_{D}^{m}(s)$ is
defined and $a_{i}<_{D}f_{D}^{m}(s)$, then let $(A_{i+1},<_{i+1},f_{i+1})$ be
the unique partial automorphism with:

$(A_{i},<_{i},f_{i})\preceq(A_{i+1},<_{i+1},f_{i+1})\preceq(D,<_{D},f_{D}),\text{
so that }$

$A_{i+i}=A_{i}\cup\\{f^{j}_{D}(s))\mid 0\leq j\leq m\\}$ and
$f_{i+1}=f_{i}\cup\\{(s,f_{D}(s)),\ldots,(f^{m-1}_{D}(s),f^{m}_{D}(s))\\}$,
and set $n_{i+1}:=m$.

Case 2. If Case 1 does not hold, but there is a partial automorphism
$(D,<_{D},f_{D})$ which extends $(A_{i},<_{i},f_{i})$, and some $m\geq n_{i}$
so that $f_{D}^{m}(s)$ is defined and $f_{D}^{m}(s)\perp a_{i}$, then let
$(A_{i+1},<_{i+1},f_{i+1})$ be the unique partial automorphism with

$(A_{i},<_{i},f_{i})\preceq(A_{i+1},<_{i+1},f_{i+1})\preceq(D,<_{D},f_{D}),\text{
so that }$

$A_{i+i}=A_{i}\cup\\{f^{j}_{D}(s))\mid 0\leq j\leq m\\}$ and
$f_{i+1}=f_{i}\cup\\{(s,f_{D}(s)),\ldots,(f^{m-1}_{D}(s),f^{m}_{D}(s))\\}$,
and set $n_{i+1}:=m$.

Case 3. If neither Case 1 nor Case 2 hold, then set
$(A_{i+1},<_{i+1},f_{i+1}):=(A_{i},<_{i},f_{i})$ and $n_{i+1}:=n_{i}$

Given the resulting partial automorphism $(A_{k},<_{k},f_{k})$, set
$n:=n_{k}+1$, and let $(E,<_{E},f_{E})$ be any $\preceq$-minimal extension of
$(A_{k},<_{k},f_{k})$ which adds $f^{n_{k}}_{k}(s)$ into the domain of
$f_{E}$. By minimality, $E=A_{k}\cup\\{a\\}$ for some new point $a$ and
$f_{E}=f_{k}\cup\\{(f^{n_{k}}_{k}(s),a)\\}$. Indeed, notice that if $a$ was
not a new point, then it would have to come from $A$. But then, $a=a_{j}$ for
some $j\leq k$, and any further extension $(F,<_{F},f_{F})$ of
$(E,<_{E},f_{E})$ which would include $a$ in the domain of $f_{F}$, would
activate Case 1 at the $j$-th stage of the above construction. As a
consequence, by the end of the construction, we would have
$a<_{k}f_{k}^{n_{k}}(s)$, and since the orbit of $s$ under any extension of
$f_{A}$ is increasing that would contradict that $f^{n}_{E}(s)=a$.

We may finally extend $(E,<_{E},f_{E})\preceq(B,<_{B},f_{B})$ to the desired
partial automorphism $(B,<_{B},f_{B})$ which is defined by: $B:=E\cup\\{b\\}$
where $b\not\in E$; $a<_{B}b$ and
$\mathrm{qft}\big{(}b,E\setminus\\{a\\},(B,<_{B})\big{)}=\mathrm{qft}\big{(}a,E\setminus\\{a\\},(B,<_{B})\big{)}$;
and $f_{B}:=f_{E}$. It is easy to check that $(B,<_{B})$ is a poset and
therefore $(B,<_{B},f_{B})$ is a partial automorphism extending
$(A,<_{A},f_{A})$ and $f_{B}^{n}(s)=a<_{B}b$.

We are left to show that $f_{B}$ is free in $(a,b)$. Let
$(B,<_{B})\preceq(C,<_{C})$ with $a<_{C}c_{1}<_{C}\cdots<_{C}c_{\ell}<_{C}b$
for some $c_{1},\ldots,c_{\ell}\in C$. The fact that $(C,<_{C},f_{C})$, with

$f_{C}:=f_{B}\cup\\{(a,c_{1}),(c_{1},c_{2}),\ldots,(c_{\ell-1},c_{\ell})\\}.$

is a partial automorphism follows by a straightforward induction based on Fact
1 and the following claim.

######  Claim.

Let $c\in C$ with $a<_{C}c<_{C}b$. Then we have that:

  1. (1)

$\mathrm{qft}\big{(}c,B\setminus\\{a\\},(C,<_{C})\big{)}\big{)}=\mathrm{qft}\big{(}a,B\setminus\\{a\\},(C,<_{C})\big{)}\big{)}$;

  2. (2)

if $p(x):=\mathrm{qft}\big{(}c,\mathrm{dom}(f_{B}),(C,<_{C})\big{)}$ and
$q(x):=\mathrm{qft}\big{(}c,\mathrm{rng}(f_{B}),(C,<_{C})\big{)}$, then

$q(x)=p[f_{B}](x).$

###### Proof of Claim.

For simplicity we will denote $<_{C}$ by $<$ throughout this proof.

(1) follows from transitivity of $<$, since $a<c<b$ and
$\mathrm{qft}\big{(}b,E\setminus\\{a\\},(B,<_{B})\big{)}=\mathrm{qft}\big{(}a,E\setminus\\{a\\},(B,<_{B})\big{)}$.

For (2), we need to show that for every $w\in\mathrm{dom}(f_{B})$ we have
that:

  1. (i)

$c=f_{B}(w)$ if and only if $c=w$;

  2. (ii)

$c<f_{B}(w)$ if and only if $c<w$;

  3. (iii)

$c>f_{B}(w)$ if and only if $c>w$.

By part (1) of the claim, and since $\mathrm{dom}(f_{B})\subseteq
B\setminus\\{a\\}$, it is enough to show that for every
$w\in\mathrm{dom}(f_{B})\subseteq B\setminus\\{a\\}$ we have that:

  1. (i)′

$c=f_{B}(w)$ if and only if $a=w$;

  2. (ii)′

$c<f_{B}(w)$ if and only if $a<w$;

  3. (iii)′

$c>f_{B}(w)$ if and only if $a>w$.

Notice that (i)′ is trivially true since $c\not\in\mathrm{rng}(f_{B})$.
Moreover, for $w=f^{-1}_{B}(a)=f^{n-1}_{B}(s)$, both (ii)′ and (iii)′ are
satisfied since $w<f_{B}(w)<c$. If now
$w\in\mathrm{dom}(f_{B})\setminus\\{f^{-1}_{B}(a)\\}$, then $f_{B}(w)\in
B\setminus\\{a\\}$. Hence, by a second application of part (1) of the claim we
are left to show that for all
$w\in\mathrm{dom}(f_{B})\setminus\\{f^{-1}_{B}(a)\\}$ we have that:

  1. (ii)′′

$a<f_{B}(w)$ if and only if $a<w$;

  2. (iii)′′

$a>f_{B}(w)$ if and only if $a>w$.

This statement is clear if $w=f_{B}^{l}(s)$ for some $l<n-1$, since $f_{B}$ is
increasing in the $f_{B}$-orbit of $s$ and therefore
$w<f_{B}(w)<a=f_{B}^{n}(s)$. We may therefore assume that both $w\in A$ and
$f_{B}(w)\in A$. Hence, $w=a_{i}$ and $f_{B}(w)=a_{j}$ for some $i,j\leq k$.
We consider the following three cases:

$\bullet$ If $w>a$, then $w>a>f_{B}^{-1}(a)$, and hence $f_{B}(w)>a$.

$\bullet$ If $w<a$, then any extension $g$ of $f_{B}$ with
$a\in\mathrm{dom}(g)$ satisfies $g(w)<g(a)$, i.e.,

$a_{j}=f_{B}(w)=g(w)<g(a)=g(f^{n}_{B}(s)).$

But any such extension $g$ is, in particular, an extension of $f_{j-1}$ in the
construction above. Hence, by Case 1 at the $j$-th step of the construction we
already have that $a_{j}<f_{j}^{n_{j}}(s)$. But then,
$f_{B}(w)=a_{j}<f_{j}^{n_{j}}(s)<a$.

$\bullet$ If $w\perp a$, then by Case 2 at the $i$-th step of the above
construction we have that $w\perp f_{B}^{n_{i}}(s)$. Since
$f^{n_{i}}_{B}(s)\leq f^{-1}_{B}(a)<a$ we have that $w\perp f^{-1}_{B}(a)$.
Hence, $f_{B}(w)\perp a$. ∎

Let $p_{0}(x):=\mathrm{qft}\big{(}a,\mathrm{dom}(f_{B}),(C,<_{C})\big{)}$ and
$q_{1}(x):=\mathrm{qft}\big{(}c_{1},\mathrm{rng}(f_{B}),(C,<_{C})\big{)}$.
Using both (1),(2) of the last claim we have that $q_{1}(x)=p_{0}[f_{B}](x)$.
By Fact 1 we have that $(C,<_{C},f_{B}\cup\\{(a,c_{1})\\})$ is a partial
automorphism. By induction we show that $(C,<_{C},f_{C})$ is a partial
automorphism. The inductive step is as follows. Take $t$ with $0<t\leq\ell$.
By (1) and (2) of the last claim we have that
$q^{\prime}_{t}(x)=p^{\prime}_{t-1}[f_{B}](x)$, where

$q^{\prime}_{t}(x)=\mathrm{qft}\big{(}c_{t},\mathrm{rng}(f_{B}),(C,<_{C})\big{)}\;\text{
and
}\;p^{\prime}_{t-1}(x)=\mathrm{qft}\big{(}c_{t-1},\mathrm{dom}(f_{B}),(C,<_{C})\big{)}.$

Since $a<_{C}c_{1}<_{C}\cdots<_{C}c_{t-1}<_{C}c_{t}$, we also have that the
quantifier-free type

$\mathrm{qft}\big{(}c_{t},\\{c_{1},\ldots,c_{t-1}\\},(C,<_{C})\big{)}$

is the push-forward of the the quantifier-free type

$\mathrm{qft}\big{(}c_{t-1},\\{a,c_{1},\ldots,c_{t-2}\\},(C,<_{C})\big{)},$

under the partial automorphism
$\\{(a,c_{1}),(c_{1},c_{2}),\ldots,(c_{t-2},c_{t-1})\\}$. Combining these two
facts, we have that the quantifier-free type

$q_{t}(x):=\mathrm{qft}\big{(}c_{t},\mathrm{rng}(f_{B})\cup\\{c_{1},\ldots,c_{t-1}\\},(C,<_{C})\big{)}$

is the push forward of the quantifier-free type

$p_{t-1}(x):=\mathrm{qft}\big{(}c_{t-1},\mathrm{dom}(f_{B})\cup\\{a,c_{1},\ldots,c_{t-2}\\},(C,<_{C})\big{)}$

under the map
$f_{B}\cup\\{(a,c_{1}),(c_{1},c_{2}),\ldots,(c_{t-2},c_{t-1})\\}$. By Fact 1,
if the latter is a partial automorphism, then so is
$f_{B}\cup\\{(a,c_{1}),(c_{1},c_{2}),\ldots,(c_{t-2},c_{t-1}),(c_{t-1},c_{t})\\}$.

Hence, $(C,<_{C},f_{C})$ is indeed a partial automorphism.

∎

We can now conclude with the proof of Theorem 2 which implies Theorem 1.

###### Proof of Theorem 2.

Consider the pair $(A,<_{A},f_{A},g_{A})$ of partial automorphisms with:

  1. (1)

$A=\\{x,y,z\\}$ with $x<_{A}y<_{A}z$;

  2. (2)

$f_{A}=\\{(x,y),(z,z)\\}$ and $g_{A}=\\{(x,z)\\}$.

Let $(\widetilde{A},<_{\widetilde{A}},f_{\widetilde{A}},g_{\widetilde{A}})$ be
any extension of $(A,<_{A},f_{A},g_{A})$. We will define two further
extensions $(A_{1},<_{1},f_{1},g_{1})$ and $(A_{2},<_{2},f_{2},g_{2})$ of
$(\widetilde{A},<_{\widetilde{A}},f_{\widetilde{A}},g_{\widetilde{A}})$ which
do not amalgamate over $(A,<_{A},f_{A},g_{A})$. We start by defining some
initial extension $(A_{0},<_{0},f_{0},g_{0})$ of
$(\widetilde{A},<_{\widetilde{A}},f_{\widetilde{A}},g_{\widetilde{A}})$ which
will be contained in both $(A_{1},<_{1},f_{1},g_{1})$ and
$(A_{2},<_{2},f_{2},g_{2})$.

Apply Lemma 1 to $(\widetilde{A},<_{\widetilde{A}},f_{\widetilde{A}})$ for
$s:=x$ to get some extension $(B,<_{B},f_{B})$, some $n\in\mathbb{N}$, and
some $a_{f},b_{f}\in B$ with $a_{f}<_{B}b_{f}$, so that $(f_{B})^{n}(x)=a_{f}$
and $f_{B}$ is free in $(a_{f},b_{f})$. By extending further $(B,<_{B})$ if
necessary we can assume without loss of generality that there is some $c\in B$
with $a_{f}<_{B}c<_{B}b_{f}$. Notice that since $f_{A}(z)=z$ and $x<_{B}z$ we
have that $f^{n}_{B}(x)<_{B}z$ for all $n\in\mathbb{N}$. Since by the
construction in the proof of Lemma 1 we have that

$\mathrm{qft}\big{(}a_{f},B\setminus\\{a_{f},b_{f}\\},(B,<_{B})\big{)}=\mathrm{qft}\big{(}b_{f},B\setminus\\{a_{f},b_{f}\\},(B,<_{B})\big{)},$

it follows that $b_{f}<_{B}z$. Since $x<_{B}c<_{B}z$ and $g_{A}(x)=z$, any
extension $(E,<_{E},g)$ of $(B,<_{B},g_{A})$ with $c\in\mathrm{dom}(g)$
satisfies $c<_{E}g(c)$. Hence, by Lemma 1 applied to an arbitrarily chosen
such extension $(E,<_{E},g)$ with $s:=c$ we get a further extension
$(B,<_{B},g_{A})\preceq(C,<_{C},g_{C})$, some $m\in\mathbb{N}$, and
$a_{g},b_{g}\in C$ with $a_{g}<_{C}b_{g}$, so that $g_{C}^{m}(c)=a_{g}$ and
$g_{C}$ is free in $(a_{g},b_{g})$.

Set $c_{0}:=c,c_{1}:=g_{C}(c),\cdots,c_{m}:=g_{C}^{m}(c)$. By extending $C$
further if necessary, we may assume without loss of generality that for every
$i$ with $0\leq i\leq m$ there is a point $d_{i}\in C$ with
$d_{i}\not\in\mathrm{dom}(g_{C})$ and $c_{i}<_{C}d_{i}$, and so that:

$\mathrm{qft}\big{(}d_{i},C\setminus\\{c_{i},d_{i}\\},(C,<_{C})\big{)}=\mathrm{qft}\big{(}c_{i},C\setminus\\{c_{i},d_{i}\\},(C,<_{C})\big{)}.$

Set $(A_{0},<_{0}):=(C,<_{C})$. By a simple induction using Fact 1 we have
that $(A_{0},<_{0},g_{0})$ with
$g_{0}:=g_{C}\cup\\{(d,d_{1}),(d_{1},d_{2}),\ldots,(d_{m-1},d_{m})\\}$, is a
partial automorphism. Since $f_{B}$ is free in $(a_{f},b_{f})$ and
$a_{f}<_{0}c<_{0}d<_{0}b_{f}$, we similarly have that $(A_{0},<_{0},f_{0})$
with $f_{0}:=f^{\prime}\cup\\{(a_{f},c),(c,d)\\}$ is also a partial
automorphism. We therefore have a pair $(A_{0},<_{0},f_{0},g_{0})$ of partial
automorphisms.

We may now define two further extensions of $(A_{0},<_{0},f_{0},g_{0})$ which
do not amalgamate over $(A,<_{A},f_{A},g_{A})$ as follows:
$(A_{1},<_{1},f_{1},g_{1})$ is defined by setting
$A_{1}:=A_{0},f_{1}:=f_{0},g_{1}:=g_{0}\cup\\{(g^{m}_{0}(c),d_{m})\\}$; and
$(A_{2},<_{2},f_{2},g_{2})$ is defined by
$A_{2}:=A_{0}\cup\\{e\\},f_{2}:=f_{0},g_{2}:=g_{0}\cup\\{(g^{m}_{0}(c),e),(e,d_{m})\\}$,
where $e$ is a new point with $g^{m}_{0}(c)<_{2}e<_{2}d_{m}$. Since
$a_{g}<_{2}g^{m}_{0}(c)<_{2}e<_{2}d_{m}<_{2}b_{g}$ and $g_{0}$ is free in
$(a_{g},b_{g})$, we have that both $(A_{1},<_{1},g_{1})$ and
$(A_{2},<_{2},g_{2})$ are partial automorphisms.

Finally, to see that $(A_{1},<_{1},f_{1},g_{1})$ and
$(A_{2},<_{2},f_{2},g_{2})$ cannot be amalgamated over
$(A,<_{A},f_{A},g_{A})$, notice that in any such amalgam, the copy of $x$ in
$A_{1}$ has to be identified with the copy of $x$ in $A_{2}$. As a
consequence, in such amalgam, the point $g_{1}^{t}\circ f_{1}^{s}(x)$ from
$A_{1}$ has to be identified with the point $g_{2}^{t}\circ f_{2}^{s}(x)$ from
$A_{2}$, for all $s,t\in\mathbb{N}$ for which both $g_{1}^{t}\circ
f_{1}^{s}(x)$ and $g_{2}^{t}\circ f_{2}^{s}(x)$ are defined. However, by the
above construction we have that $(g_{1}^{m+1}\circ
f_{1}^{n+1})(x)=(g_{1}^{m}\circ f_{1}^{n+2})(x)$ in $A_{1}$ and
$(g_{2}^{m+1}\circ f_{2}^{n+1})(x)<_{2}(g_{2}^{m}\circ f_{2}^{n+2})(x)$. ∎

## References

  * [1] G.M. Bergman, Generating Infinite Symmetric Groups Bull. Lond. Math. Soc. 38 (2006), 429–440.
  * [2] A.M.W. Glass, S.H. McCleary, M. Rubin, Automorphism groups of countable highly homogeneous partially ordered sets, Math Z 214 (1993), 55–66.
  * [3] B. Herwig, D. Lascar, Extending Partial Automorphisms and the Profinite Topology on Free Groups, Trans. Amer. Math Soc (5) 352 (2000),1985–2021.
  * [4] A.S. Kechris, C. Rosendal, Turbulence, amalgamation, and generic automorphisms of homogeneous structures, Proc. Lond. Math. Soc. (3) 94 (2007), no. 2, 302–350.
  * [5] D. Kuske, J.K. Truss, Generic automorphisms of the universal partial order, Proc. Amer. Math. Soc. 129 (2001), no. 7, 1939–1948.
  * [6] D. Macpherson, A survey of homogeneous structures, Discrete Math. 311 (2011), no. 15, 1599–1634.
  * [7] D. Macpherson, K. Tent, Simplicity of some automorphism groups, J. Algebra (1) 342 (2011), 40–52.
  * [8] C. Rosendal, S. Solecki, Automatic continuity of homomorphisms and fixed points on metric compacta, Isr. J. Math. 162 (2007), 349–371.
  * [9] D. Siniora, Automorphism groups of homogeneous structures, PhD thesis, University of Leeds.
  * [10] J.K. Truss, On notions of genericity and mutual genericity J. Symbolic Logic 72 (2007), no. 3, 755–766.