# The Second Joint Workshop on Cross Reality

Nanjia Wang
University of Calgary
Calgary, Canada
<EMAIL_ADDRESS>
Yue Li
Xi’an Jiaotong Liverpool University
Suzhou, China
<EMAIL_ADDRESS>
Francesco Chiossi
LMU Munich
Munich, Germany
<EMAIL_ADDRESS>
Fabian Pointecker
University of Applied Sciences Upper Austria
Wels, Austria
<EMAIL_ADDRESS>
Lixiang Zhao
Xi’an Jiaotong-Liverpool University
Suzhou, China
<EMAIL_ADDRESS>
Daniel Zielasko
Trier University
Trier, Germany
<EMAIL_ADDRESS>
Use footnote for providing further information about author (webpage,
alternative address)— _not_ for acknowledging funding agencies.

###### Abstract

The 2nd Joint Workshop on Cross Reality (JWCR’24), organized as part of ISMAR
2024, seeks to explore the burgeoning field of Cross Reality (CR), which
encompasses the seamless integration and transition between various points on
the reality-virtuality continuum (RVC) such as Virtual Reality (VR), Augmented
Virtuality (AV), and Augmented Reality (AR). This hybrid workshop aims to
build upon the foundation laid by the inaugural JWCR at ISMAR 2023, which
successfully unified diverse CR research communities. The workshop will
address key themes including CR visualization, interaction, user behavior,
design, development, engineering, and collaboration. CR Visualization focuses
on creating and displaying spatial data across the RVC, enabling users to
navigate and interpret information fluidly. CR Interaction delves into natural
user engagements using gestures, voice commands, and other advanced techniques
to enhance immersion. The study of CR User Behavior and Experience
investigates how users perceive and interact within these hybrid environments.
Furthermore, CR Design and Development emphasizes creating effective CR
applications using innovative processes and tools, while CR Collaboration
examines methods for fostering teamwork in mixed reality settings.

_Keywords_ Cross-Reality $\cdot$ Mixed Reality $\cdot$ Virtual Reality $\cdot$
Augmented Reality $\cdot$ Augmented Virtuality $\cdot$ Spatial Computing

##  1 Introduction

Cross Reality (CR) Auda et al. (2023) is an emerging technology that focuses
on the concurrent usage of or the transition between multiple systems at
different points on the reality-virtuality continuum (RVC), including Virtual
Reality (VR), Augmented Virtuality (AV), and Augmented Reality (AR). CR has
gained significant attention in recent years due to its potential for
revolutionizing various research and industry areas where users need to
comprehend and explore spatial data and its relevant information in different
forms Chiossi et al. (2022). It is expected that in the near future, more CR
applications will arise to allow users to transition along the individual
stages of the RVC or to collaborate in-between these stages to use their
distinct advantages and mitigate their potential problems.

###  1.1 Themes and Topics of Interest

Last year, the 1st Joint Workshop on Cross Reality Liang et al. (2023) held in
conjunction with the IEEE ISMAR 2023 brought together the community of CR
researchers from five separate workshops on individual CR topics. The workshop
drew a lot of attention where participants established the research area
further. There were over 50 participants joined the 1st JWCR in person with
over 20 participants joined online. This is a follow up workshop to explore
the new challenges, solutions, and opportunities in the field of CR and
provide a comprehensive overview of the related research on the design of
interactive techniques for effective CR visualization, interaction,
collaboration, user experience, behavior and engineering. We are particularly
interested in blurring the lines between and merging the virtual and physical
worlds to support users in understanding data in different forms. The workshop
provides a forum for researchers from VR/AV/AR/MR, visualization, HCI, and
related fields to present their technical and systems papers that introduce
new approaches, ideas, discussions, and applications.

## Topics of Interest

The field of Cross Reality (CR) is a rapidly evolving area of research that
encompasses various aspects of technology and human interaction. CR integrates
and transitions between multiple systems on the reality-virtuality continuum,
including Virtual Reality (VR), Augmented Reality (AR), and Augmented
Virtuality (AV). This convergence of real and virtual worlds opens up numerous
possibilities for innovation in how we perceive, interact with, and utilize
digital information in our daily lives and professional activities.

CR research covers a broad spectrum of topics, aiming to enhance user
experiences and functionalities across different reality-virtuality
interfaces. The integration of virtual and physical environments presents
unique challenges and opportunities in design, interaction, and application
development. Researchers and practitioners are exploring new methodologies and
technologies to create more immersive, interactive, and effective CR systems.

Key areas of interest include, but are not limited to, the following:

  * •

Cross Reality environment design: virtuality and reality

  * •

Computational and Adaptive Cross Reality Systems

  * •

Visual representations in cross-reality systems

  * •

Cross Reality transitions across multiple interfaces

  * •

Cross Reality interaction

  * •

Multimodal interaction, perception, and cognition

  * •

Real-world tool use and tangibles as input to CR systems

  * •

Collaborative Cross Reality immersive analytics

  * •

Collaboration across the reality-virtuality continuum

  * •

Cross Reality user experience

  * •

Cross Reality user behavior

  * •

Cross Reality tools, frameworks, and APIs

  * •

Testing Cross Reality systems

  * •

Design guidelines for Cross Reality applications

  * •

Evaluation of Cross Reality experiences and systems

Researchers in these areas are encouraged to contribute their insights and
findings to advance the state of CR technology and its applications. By
addressing these topics, we aim to foster a deeper understanding of CR and its
potential to transform various domains, including education, healthcare,
industry, and entertainment.

####  1.1.1 CR Visualization

CR Visualization refers to the ability to create and display abstract or
inherently spatial data along the RVC. The visual representations of a Cross-
Reality system offer different degrees of virtuality to users and enable users
to seamlessly move back and forth across the reality-virtuality continuum.

####  1.1.2 CR Interaction

CR Interaction allows users to naturally and intuitively engage with real and
virtual objects and environments. CR enables various forms of interaction,
including hand gestures, voice commands, haptic feedback, and eye-tracking.
Advanced interaction techniques for object manipulation, locomotion, and
spatial interaction enhance the level of immersion and interactivity in CR
experiences, enabling users to seamlessly perform complex tasks and
interactions.

####  1.1.3 CR User Behavior and Experience

CR User Behavior and Experience are concerned with how users perceive, process
andrespond to visual information in CR environments. CR technology enables
users to immerse themselves in virtual or augmented reality spaces, allowing
them to interact with and seamlessly transition between virtual and physical
environments and objects.

####  1.1.4 CR Design, Development, and Engineering

CR Design, Development, and Engineering are concerned with processes, methods,
frameworks, and tools that increase the effectiveness and efficiency of design
and development teams tasked with creating CR applications and systems.
Testing and evaluation are a substantial part of these processes.
Additionally, there are still many open challenges in enabling end users, such
as developers, domain experts, and users with minimal programming experience,
to craft, program, and tailor CR applications and experiences according to
their goals, interests, needs, and abilities. There is a growing interest in
utilizing authoring tools powered by Generative AI for prototyping CR
applications.

####  1.1.5 CR Collaboration

CR Collaboration is an area of growing interest, as it allows users to work
together in real and virtual environments using different interaction
techniques and interfaces with different degrees of virtuality. Collaborative
CR experiences have the potential to enhance local, remote, and hybrid
communication, foster creativity, and improve decision-making in various
domains such as design, training, and education.

####  1.1.6 CR Applications

CR Applications have the potential to enhance the effectiveness and efficiency
of real-life tasks in diverse industries. However, there needs to be more
empirical evidence to support claims made about the advantages of serious CR;
namely, more CR applications need to demonstrate their benefit in solving
real-life tasks and be evaluated by empirical studies with the respective user
group.

###  1.2 Workshop Format

This will be a half-day to a full-day workshop with a mixture of invited
keynote speeches, presentations of short position papers, and panel discussion
on topics derived from the position papers. Position papers will each be
presented for ten minutes, while thirty to sixty minutes will be allocated for
the group discussion activity. It will be a hybrid event supporting both face-
to-face and online participation. A discord channel will be created, enabling
people to discuss the workshop topic both before and after the ISMAR event.

###  1.3 Workshop Contributions

We welcome position paper submissions from 2-4 pages long, excluding
references. All paper submissions must be in English. Paper quality versus
length will be assessed according to a contribution-per-page judgment. All
submissions will be accepted or rejected as workshop papers. All accepted
papers will be archived in the IEEE Xplore digital library. Detailed
submission and review guidelines are available on the workshop website:
https://cross-realities.org/2024/

###  1.4 Audience

Based on the statistics of the 1st JWCR at ISMAR 2023, we are expecting 15 to
20 submissions with paper presentations at the workshop. An additional 20 to
30 participants will join the panel discussion with presenters.

###  1.5 Important Dates

We encourage all interested researchers and practitioners to note the
following important dates for the 2nd Joint Workshop on Cross Reality
(JWCR’24):

  * •

July 26, 2024: Papers submission deadline

  * •

August 9, 2024: Notification of acceptance

  * •

August 26, 2024: Camera-ready submission deadline

  * •

October 25, 2024: Workshop date

###  1.6 Call for Participation

We are pleased to invite you to the 2nd Joint Workshop on Cross Reality
(JWCR’24), held in conjunction with ISMAR 2024. Cross Reality (CR) is an
emerging technology that enables concurrent usage and transitions between
multiple systems across the reality-virtuality continuum (RVC), including
Virtual Reality (VR), Augmented Virtuality (AV), and Augmented Reality (AR).
This technology has garnered significant attention for its potential to
revolutionize research and industry by allowing users to explore and
comprehend spatial data in diverse forms.

Following the success of the inaugural JWCR at ISMAR 2023, which united the CR
research community from five separate workshops, this year’s workshop aims to
further explore new challenges, solutions, and opportunities in the field. We
seek to provide a comprehensive overview of research on interactive techniques
for effective CR visualization, interaction, collaboration, user experience,
behavior, and engineering. Our goal is to blur the lines between the virtual
and physical worlds, enhancing users’ ability to understand and manipulate
data across different forms.

###  1.7 Organizers

##### Nanjia Wang

is a Ph.D. student at the SEER lab (https://seriousxr.ca/) under the
supervision of Dr. Frank Maurer. His work focuses on single-user cross-reality
(CR) applications Wang and Maurer (2022). His research goal is to exploit the
potential benefits of single-user CR applications, including the ability to
transition between spaces on the Milgram’s Reality Virtuality Continuum (RVC)
that are most suitable for specific tasks Aigner et al. (2023); Wang et al.
(2020). Nanjia is a member of the 1st Joint Workshop on Cross Reality program
committee.

##### Yue Li

received her PhD degree from the University of Nottingham in 2020 with the
Postgraduate Award. She is an Assistant Professor at Xi’an Jiaotong-Liverpool
University (https://imyueli.github.io/). Her research interest is in the field
of HCI, with particular emphasis on Cross Reality technologies and their use
in cultural heritage and education Ch’Ng et al. (2020); Xu et al. (2024); He
et al. (2024).

##### Francesco Chiossi

(www.francesco-chiossi-hci.com is a PhD researcher at LMU Munich with a
background in applied cognitive science. He focuses on implicit measures of
user behavior and context, such as electrodermal activity Chiossi et al.
(2023a) and EEG Chiossi et al. (2023b), as an implicit input to design and
evaluate physiologically adaptive systems across the reality-virtuality
continuum Chiossi et al. (2024).

##### Fabian Pointecker

received his Master’s degree in Human-Centered Computing from the University
of Applied Sciences Upper Austria and is a member of the program committee of
the 1st Joint Workshop on Cross Reality. His research interests are
visualization and transition techniques in the area of CR (https://hive.fh-
hagenberg.at/). He is currently focusing on visual transition techniques that
allow the user to seamlessly move along Milgrams’s Reality Virtuality
Continuum.

##### Lixiang Zhao

is a Ph.D. student at VACT lab in Xi’an Jiaotong Liverpool University
(https://lixiangzhao98.github.io/), supervised by Dr. Lingyun Yu. His research
focuses on Scientific Visualization (SciVis) and HCI. His work is dedicated to
design and evaluate the spatial interaction techniques Zhao et al. (2023) and
visualization techniques Li et al. (2023) within CR and VR environments,
tailored to specific scientific domains including astronomy and biomedicine.

##### Daniel Zielasko

is currently a postdoctoral researcher at the HCI Group at the University of
Trier. He received his Ph.D. in 2020 at the Virtual Reality and Immersive
Visualization group at RWTH Aachen University for studying desk-based Virtual
Reality. He received his Master’s degree in Computer Science in 2013 at RWTH
Aachen University.

He focuses on the integration of VR technologies into existing professional
workflows and collaborates with neuroscientists, archaeologists, and
psychologists in various interdisciplinary projects such as the EU Flagship
Project, "The Human Brain Project (HBP)," and the SMHB (Supercomputing and
Modeling for the Human Brain). His special interest is the prevention of
cybersickness Zielasko et al. (2024) and the development of convincing and
innovative 3D user interfaces Wang et al. (2024); Zielasko et al. (2017).

## References

  * Auda et al. [2023] Jonas Auda, Uwe Gruenefeld, Sarah Faltaous, Sven Mayer, and Stefan Schneegass.  A scoping survey on cross-reality systems.  _ACM Comput. Surv._ , 56(4), oct 2023.  ISSN 0360-0300.  doi:10.1145/3616536.  URL https://doi.org/10.1145/3616536.
  * Chiossi et al. [2022] Francesco Chiossi, Johannes Zagermann, Jakob Karolus, Nils Rodrigues, Priscilla Balestrucci, Daniel Weiskopf, Benedikt Ehinger, Tiare Feuchtner, Harald Reiterer, Lewis L. Chuang, Marc Ernst, Andreas Bulling, Sven Mayer, and Albrecht Schmidt.  Adapting visualizations and interfaces to the user.  _it - Information Technology_ , 2022.  doi:10.1515/itit-2022-0035.
  * Liang et al. [2023] Hai-Ning Liang, Hans-Christian Jetter, Frank Maurer, Uwe Gruenefeld, Mark Billinghurst, and Christoph Anthes.  1st joint workshop on cross reality.  In _IEEE ISMAR 2023_. IEEE, October 2023.  doi:10.13140/RG.2.2.21577.52322.
  * Wang and Maurer [2022] Nanjia Wang and Frank Maurer.  A design space for single-user cross-reality applications.  In _Proceedings of the 2022 international conference on advanced visual interfaces_ , pages 1–5, 2022.
  * Aigner et al. [2023] David Aigner, Nanjia Wang, David Kielmayer, Jürgen Steiner, Julian Hochpöchler, Christoph Heinzl, Daniel Roth, Frank Maurer, and Christoph Anthes.  Cardiac visualisation along the rv-continuum-a high-fidelity pilot study.  In _2023 IEEE International Symposium on Mixed and Augmented Reality Adjunct (ISMAR-Adjunct)_ , pages 675–680. IEEE, 2023.
  * Wang et al. [2020] Nanjia Wang, Amir Aminbeidokhti, and Frank Maurer.  Individual and collaborative cross-reality immersive analytics-initial ideas.  In _XR@ ISS_ , 2020.
  * Ch’Ng et al. [2020] Eugene Ch’Ng, Yue Li, Shengdan Cai, and Fui-Theng Leow.  The effects of vr environments on the acceptance, experience, and expectations of cultural heritage learning.  _Journal on computing and cultural heritage (JOCCH)_ , 13(1):1–21, 2020.
  * Xu et al. [2024] Ningning Xu, Yue Li, Xingbo Wei, Letian Xie, Lingyun Yu, and Hai-Ning Liang.  Cubemuseum ar: A tangible augmented reality interface for cultural heritage learning and museum gifting.  _International Journal of Human–Computer Interaction_ , 40(6):1409–1437, 2024.
  * He et al. [2024] Shuqi He, Haonan Yao, Luyan Jiang, Kaiwen Li, Nan Xiang, Yue Li, Hai-Ning Liang, and Lingyun Yu.  Data cubes in hand: A design space of tangible cubes for visualizing 3d spatio-temporal data in mixed reality.  In _Proceedings of the CHI Conference on Human Factors in Computing Systems_ , pages 1–21, 2024.
  * Chiossi et al. [2023a] Francesco Chiossi, Yagiz Turgut, Robin Welsch, and Sven Mayer.  Adapting visual complexity based on electrodermal activity improves working memory performance in virtual reality.  _Proceedings of the ACM on Human-Computer Interaction_ , 7(MHCI):1–26, 2023a.
  * Chiossi et al. [2023b] Francesco Chiossi, Changkun Ou, Carolina Gerhardt, Felix Putze, and Sven Mayer.  Designing and evaluating an adaptive virtual reality system using eeg frequencies to balance internal and external attention states.  _arXiv preprint arXiv:2311.10447_ , 2023b.
  * Chiossi et al. [2024] Francesco Chiossi, Uwe Gruenefeld, Baosheng James Hou, Joshua Newn, Changkun Ou, Rulu Liao, Robin Welsch, and Sven Mayer.  Understanding the impact of the reality-virtuality continuum on visual search using fixation-related potentials and eye tracking features.  In _Proceedings of MobileHCI 2024_. ACM, 2024.  doi:10.1145/3676528.
  * Zhao et al. [2023] Lixiang Zhao, Tobias Isenberg, Fuqi Xie, Hai-Ning Liang, and Lingyun Yu.  Metacast: Target-and context-aware spatial selection in vr.  _IEEE Transactions on Visualization and Computer Graphics_ , 2023.
  * Li et al. [2023] Jiayin Li, Lixiang Zhao, Hai-Ning Liang, and Lingyun Yu.  Immerview: Adaptive multi-view layout for immersive situated visualizations.  In _2023 IEEE International Symposium on Mixed and Augmented Reality Adjunct (ISMAR-Adjunct)_ , pages 108–112. IEEE, 2023.
  * Zielasko et al. [2024] Daniel Zielasko, Ben Rehling, and Gregor Domes.  The progression of cybersickness after exposure.  2024\.
  * Wang et al. [2024] Nanjia Wang, Daniel Zielasko, and Frank Maurer.  User preferences for interactive 3d object transitions in cross reality-an elicitation study.  In _Proceedings of the 2024 International Conference on Advanced Visual Interfaces_ , pages 1–9, 2024.
  * Zielasko et al. [2017] Daniel Zielasko, Benjamin Weyers, Martin Bellgardt, Sebastian Pick, Alexander Meibner, Tom Vierjahn, and Torsten W Kuhlen.  Remain seated: towards fully-immersive desktop vr.  In _2017 IEEE 3rd workshop on everyday virtual reality (WEVR)_ , pages 1–6. IEEE, 2017.


Bbbk

# Pushing Alias Resolution to the Limit

Taha Albakour  TU Berlin ,  Oliver Gasser  Max Planck Institute for
Informatics and  Georgios Smaragdakis  Delft University of Technology

(2023)

###### Abstract.

In this paper, we show that utilizing multiple protocols offers a unique
opportunity to improve IP alias resolution and dual-stack inference
substantially. Our key observation is that prevalent protocols, e.g., SSH and
BGP, reply to unsolicited requests with a set of values that can be combined
to form a unique device identifier. More importantly, this is possible by just
completing the TCP handshake. Our empirical study shows that utilizing readily
available scans and our active measurements can double the discovered IPv4
alias sets and more than 30$\times$ the dual-stack sets compared to the state-
of-the-art techniques. We provide insights into our method’s accuracy and
performance compared to popular techniques.

Alias Resolution, Protocol Dual-Stack, Network Measurement.

††journalyear: 2023††copyright: rightsretained††conference: Proceedings of the
2023 ACM Internet Measurement Conference; October 24–26, 2023; Montreal, QC,
Canada††booktitle: Proceedings of the 2023 ACM Internet Measurement Conference
(IMC ’23), October 24–26, 2023, Montreal, QC, Canada††doi:
10.1145/3618257.3624840††isbn: 979-8-4007-0382-9/23/10††ccs: Networks Network
protocols††ccs: Networks Network management††ccs: Security and privacy Network
security

##  1\. Introduction

Uncovering the Internet’s topology is crucial for Internet measurement and
analysis. Common topology mapping tools, such as Traceroute, only provide
partial information by revealing interface-level links. Alias resolution, the
process of mapping IP addresses to the underlying hardware, enhances the
accuracy and completeness of the observed topology (Gunes and Sarac, 2007).
Moreover, it can aid researchers in the development of novel measurement
techniques (Vermeulen et al., 2022). The identification of dual-stack hosts,
i.e, IPv4 and IPv6 enabled host, presents a conceptually similar challenge to
alias resolution. Due to its large address space, however, measuring IPv6
networks remains a challenging task. Nevertheless, identifying dual-stack
hosts is an important step in understanding network performance
(Chandrasekaran et al., 2015), policy (claffy, 2011), and security posture
(Czyz et al., 2016).

Prior work introduced many techniques to resolve aliases with the common
source address (CAIDA, 2023) as the earliest approach. This technique operates
by sending a packet to a closed port on a router, which triggers an ICMP port
unreachable message. If the source address of the ICMP message differs from
the probed address (the interface where the packet is received), the IP pairs
are inferred as aliases. However, detecting aliases using this method becomes
challenging as many routers always respond from the probed address or may not
respond at all, rendering the technique impractical.

Other techniques utilize the IPID field in the IP header. IPID-based
techniques are predicated on the fact that many routers maintain a monotonic
IPID counter that increments with each generated packet, and shared across
interfaces. IPID-based tools attempt to sample the IPID value of candidate IPs
over a short timeframe and perform a monotonic bounds test on the IPID
sequences. If an IP pair share the same sequence, then they are likely to be
aliases. RadarGun (Bender et al., 2008), Rocketfuel (Spring et al., 2002), and
MIDAR (Keys et al., 2013) are few examples of tools utilizing this technique
for IPv4 addresses, and Speedtrap (Luckie et al., 2013) for IPv6 addresses,
respectively. If a router utilizes a non-monotonically incremental IPID
counter, such technique fails to identify potential aliases. Additionally,
these techniques require sending large number of packets, rendering them less
optimal for large scale measurements.

Recent work took a protocol-centric approach and exploited a unique identifier
in the response to an unsolicited SNMPv3 request (Albakour et al., 2021). This
approach can infer aliases by grouping addresses that shares the same unique
identifier. One drawback to this approach is that it requires the target IP to
respond to a specific service, i.e., SNMPv3. Firewalls and access control
lists can limit the number of identifiable aliases for a given host if the
service is configured to respond only on selected addresses.

The mentioned techniques mainly addresses the alias resolution problem,
however, the protocol-centric approach also solve the dual-stack
identification. Further, researchers have developed a use-case specific
solutions for dual-stack identification (Albakour et al., 2021; Pujol et al.,
2017; Padmanabhan et al., 2022; Berger et al., 2013) with generic techniques
utilizing DNS PTR records (Luckie et al., 2019; Czyz et al., 2016)

In this paper, we take a protocol-centric approach and introduce a technique
that improves both IP alias and dual-stack resolution. Our main contributions
can be summarized as follows:

  * •

We introduce a new alias resolution technique, for both IPv4 and IPv6, by
collecting and analyzing application layer headers for different protocols,
namely, BGP and SSH.

  * •

Our alias resolution technique improves dual-stack discovery as more IPv4 and
IPv6 addresses are associated with unique identifiers.

  * •

We apply our methodology on our own active measurements data as well as data
obtained from Censys. We complement previous protocol-centric technique and
demonstrate that it is possible to more than double the number of identifiable
non-singleton IPv4 alias sets.

  * •

Our results show that we can identify more than 650 thousand dual-stack alias
sets. Which is, by a large margin, the largest set reported to date.

  * •

We make the datasets we collected and our analysis publicly available at:
https://routerfingerprinting.github.io/

##  2\. Methodology

Scanning for active services is a widely used technique in Internet
measurement and security analysis (Durumeric et al., 2013; Czyz et al., 2016).
In this paper, we show that utilizing service scanning results for two popular
protocols, namely, SSH and BGP, enables large-scale alias and dual-stack
inference. By analyzing these protocols and their specifications (Lonvick and
Ylonen, 2006; Rekhter et al., 2006), we identify unique host identifiers that
can be used to group IP addresses belonging to the same host in both IPv4 and
IPv6.

###  2.1. Service Scan Data

We perform active service scans for SSH and BGP in two phases:

  1. (1)

An Internet-wide TCP scan sending a single SYN packet on port 22 and 179 using
ZMap (Durumeric et al., 2013).

  2. (2)

A service scan using ZGrab2 (GitHub, 2023) targeting IPs, which are responsive
to the Internet-wide ZMap scan.

In the service scan, specifically for SSH, we complete the TCP handshake and
subsequently send a protocol-specific payload to solicit banner information
from the target IP. For BGP, the target IP sends an open message after we
complete the TCP handshake without the need for any additional data exchange.

To complement our view of active services, we leverage the Censys dataset
(Durumeric et al., 2015), in addition to our own active measurements. Censys
perform service scan on the 65k ports. However, we only consider hosts that
are running SSH and BGP on the default ports, i.e., TCP/22 for SSH and TCP/179
for BGP.

SSH Protocol Protocol: SSH-2.0- SSH Version 2 ... Key Exchange
(method:curve25519-sha256) Message Code: Key Exchange Init (20) Algorithms ...
kex_algorithms string: curve25519-sha256,.. server_host_key_algorithms length:
57 server_host_key_algorithms string:...
encryption_algorithms_server_to_client length: 108
encryption_algorithms_server_to_client string: ... ...
mac_algorithms_server_to_client length: 213 mac_algorithms_server_to_client
string: ... ... compression_algorithms_server_to_client length: 21
compression_algorithms_server_to_client string:... Key Exchange
(method:curve25519-sha256) Message Code: Elliptic Curve Diffie-Hellman Key
Exchange Reply(31) KEX host key (type: ssh-ed25519) ... EdDSA public key
length: 32 EdDSA public key:409fa737033d6a79a1130aff96ee5ee2c39a9... ...

Figure 1. Snippet of a Dissected SSH Connection Setup

###  2.2. SSH Identifier

The Secure Shell (SSH) protocol, initially introduced in RFC 4253 (Lonvick and
Ylonen, 2006), provides a mechanism to establish a secure network connection.
We utilize ZGrab2’s SSH module, which handle the SSH handshake, to perform our
service scan. Upon completion of the TCP handshake, the server and the client
send their respective service string banner and then proceed to exchange a
series of plain text message before transitioning to an encrypted session.
During this exchange, both the server and client communicate their respective
capabilities regarding encryption, authentication, and compression algorithms.
This exchange enables both endpoints to convey to the other the algorithms
they support. RFC 4253 (Lonvick and Ylonen, 2006) states that each supported
algorithm MUST be listed in order of preference, from most to least. This
requirement results in a signature that can be used to identify the client and
the server implementation (Willie Bythwood, Andrew Kien, and Iman Vakilinia,
2023; Dulaunoy et al., 2022). We use this information, and the service banner
as the first part of our SSH host identifier.

SSH server requires a pair of host keys. These keys are typically generate
during the service setup. The client and server exchange the public key
components during the connection setup phase. We use the server public key as
the second part of our SSH identifier. While the SSH public key itself is
likely to be unique per host, our active scan shows that 0.4% of non-singleton
hosts communicate different algorithmic capabilities. Therefore, combining the
key with the host’s algorithmic capabilities can enhance the uniqueness of the
SSH identifier. We highlight (in blue) the various parts of our SSH identifier
in a snippet of SSH connection setup in Figure 1.

###  2.3. BGP Identifier

Border Gateway Protocol - OPEN Message Marker:
ffffffffffffffffffffffffffffffff Length:37 Type: OPEN Message (1) Version: 4
My AS: 23456 Hold Time: 90 BGP Identifier: 148.170.0.33 Optional Parameters
Length: 8 Optional Parameter: Capability Parameter Type: Capability (2)
Parameter Length: 2 Capability: Route refresh capability (Cisco) Type: Route
refresh capability (Cisco) (128) Length: 0 Optional Parameter: Capability
Parameter Type: Capability (2) Parameter Length: 2 Capability: Route refresh
capability Type: Route refresh capability (2) Length: 0 Border Gateway
Protocol - NOTIFICATION Message Marker: ffffffffffffffffffffffffffffffff
Length: 21 Type: NOTIFICATION Message (3) Major error Code: Cease (6) Minor
error Code (Cease): Connection Rejected (5)

Figure 2. A Dissected BGP OPEN Message

The BGP protocol is used to facilitate the exchange of routing information
between BGP-speaking routers. To that end, BGP speakers establish and maintain
a TCP session, typically over port 179. When scanning for host running BGP, we
complete the TCP handshake and wait for data. We simply close the connection
after 2 seconds timeout, or after receiving any data. We find that more than
5.8M BGP speakers close the connection immediately after completing the TCP
handshake. However, 364k IPs close the connection after sending an OPEN and a
Notification message stating that the connection is rejected. Figure 2 shows
an example of a dissected BGP OPEN message from our service scan.

The OPEN message of a BGP speaker contains multiple fields that, when
combined, can serve as a globally unique identifier. The first notable field
is the BGP identifier. The BGP identifier is used as part of a loop and
collision prevention mechanism and defined in RFC 4271 (Rekhter et al., 2006)
as 4-octet unsigned integer that uniquely identifies the BGP speakers within
an Autonomous System (AS). Moreover, it should have the same value for every
local interface. The OPEN message also contains the Autonomous System Number
(ASN) of a BGP speaker’s network. The ASN is a globally unique number that is
associated with a single AS (Hawkinson and Bates, 1996). Some OPEN messages
may contain optional parameters field that indicate the supported capabilities
(Chandra and Scudder, 2009). The additional fields within the OPEN message
such as Length, Version, and Hold Time are host-wide, and shared across all
interfaces. Combining the values of those fields results in a unique
identifier that we use to group alias and dual stack addresses. We highlight
(in blue) the relevant parts of the identifier in a dissected BGP message in
Figure 2.

###  2.4. Alias and Dual-Stack Inference

For every IP that is responsive to the BGP and SSH service scan, we extract
the respective identifier. We group IP addresses that shares the same
identifier into SSH and BGP alias sets, respectively. We group IPv4 and IPv6
addresses that share the same identifier into dual-stack sets.

###  2.5. Datasets

We leverage two different types of datasets. First, we use active measurement
data in the IPv4 and IPv6 Internet. In IPv4, we perform Internet-wide scans
for the SSH and BGP protocols using ZMap (Durumeric et al., 2013) and ZGrab2
(GitHub, 2023). In IPv6, we use an IPv6 Hitlist (Gasser et al., 2018; Zirngibl
et al., 2022) to identify potentially active addresses in the vast IPv6
address space. The active measurement data was collected on April 18, 2023,
utilizing a single vantage point located in a data center in Germany. Our
dataset, including our analysis, are publicly available (Albakour et al.,
2023). Second, we use data obtained from Censys (Durumeric et al., 2015) to
identify additional responsive hosts to SSH or BGP. We selected a Censys
snapshot that closely matches the date of our active measurement, March 28,
2023.

In Table 1 we show an overview of these two datasets as well as the union,
where applicable, of both sources. In IPv4, we find that both Censys as well
as our active scans cover a similar number of ASes for both SSH and BGP.
Censys does, however, find around 6M more IPs for SSH and 35k more IPs for
BGP. This might be linked with Censys performing distributed measurements,
which reduces the likelihood of triggering rate-limiting or intrusion
detection system filters (Wan et al., 2020). Further, censys also finds an
additional 5.6M IPs running SSH on 60,806 different ports. We do not consider
non-standard ports from Censys since our active scan only covers port 22. The
union of both IPv4 data sources provides additional coverage compared to just
a single source, both with respect to the number of covered IPs as well as
ASes. Therefore, unless explicitly stated otherwise, we use the union of both
data sources in the remainder of the paper for our IPv4 analysis.

In IPv6, our active scans find more than 1M SSH IPs and 67k BGP IPs. In
contrast, Censys reports only 944 SSH IPs and no IPs for BGP. Further, the SSH
IPs are running the service on a non-standard port, namely 80 and 443. We
believe that the variation attribute to the IPv6 hitlists used. Due to its
limited coverage, we exclude Censys IPv6 data from our analysis. However, as
of August 15, 2023, Censys IPv6 snapshot reports more than 415k IPv6 addresses
running SSH on port 22. We expect this number to increase overtime as Censys
scans for IPv6 more rigorously.

In addition to SSH and BGP services, we conduct an SNMPv3 scan for both IPv4
and IPv6. We utilizing an already established methodology (Albakour et al.,
2021) to identify alias and dual-stack sets. We then use the results for
validation purposes and as a supplement to our results. The SNMPv3 data also
serve as baseline for comparison. We note that Censys data primarily reports
SNMPv2 hosts and does not seem to include any information on SNMPv3.
Consequently, we do not include it as an additional source.

Table 1. Service Scanning Dataset Overview

| Active measurements | Censys | Union
---|---|---|---
Protocol | # IPs | # ASN | # IPs | # ASN | # IPs | # ASN
SSH | 15.9M | 46.1k | 21.7M | 47.6k | 24.4M | 48.9k
BGP | 364k | 6.5k | 391k | 7k | 409k | 7.5k
SNMPv3 | 20.8M | 50.2k | n.a | n.a | n.a | n.a
Union | 36.7M | 59.6k | 22.1M | 48.5k | 24.7M | 49.7k
SSH (IPv6) | 1.01M | 10.8k | n.a | n.a | n.a | n.a
BGP (IPv6) | 67k | 3.1k | n.a | n.a | n.a | n.a
SNMPv3 (IPv6) | 337k | 10.8k | n.a | n.a | n.a | n.a
Union | 1.3M | 14.4k |  |  |  |

###  2.6. Validation

We take a cross-protocol validation approach and compare sets derived from IP
addresses responsive to different protocol pairs. We also utilize MIDAR (Keys
et al., 2013) as an additional source for validation. Specifically, we test a
random sample of 61k alias sets using MIDAR and check whether the resulting
sets perfectly match the ones we identify with SSH. We ensure that each sample
set contains at most ten IPv4 addresses to ensure completing the MIDAR run in
a close time frame to the SSH service scan. We provide a summary of our
validation results in Table 2 where we report the test sample size, the number
of sets that exactly match, and the number of sets with mismatching IPs.

In cross-protocol validation, we initially compare the alias sets obtained
from SSH and BGP. Our active scan data contains a total of 7.8k responsive
addresses, common to both protocols. We identify 1.34k alias sets using SSH
and 1.35k alias sets using BGP. The validation between SSH and BGP protocols
shows that 96% of the SSH sets have a perfect match with the BGP sets.

Next, we examine the results of SSH and SNMPv3 pairs. Our active scan data
contains a total of 63k responsive addresses to both protocols, resulting in
13.6k alias sets using SSH and 14.5k alias sets using SNMPv3. The validation
between SSH and SNMPv3 protocols shows a 97% agreement.

Finally, we compare the BGP and SNMPv3 pairs with 37k responsive addresses to
both protocols. We identify 1.84k alias sets using BGP and 1.9k alias sets
using SNMPv3. The validation between BGP and SNMPv3 shows a 95% agreement.

When comparing our results with MIDAR, we focus solely on SSH-based alias sets
due to the time required to run MIDAR against all alias sets. We find that
only 13% of the sampled sets can be verified with MIDAR. This low coverage can
be attributed to two reasons: (a) the majority of these addresses do not
utilize an incremental IPID counter, or (b) targets with large traffic volume
resulting in a high velocity IPID counter. MIDAR is able to verify 8.5k alias
sets with a 96% agreement with our SSH results. The remaining 4% alias sets
are split into two or three alias sets by MIDAR, while SSH groups them into a
single set. We suspect that the disagreement can be attributed to IP churn
given that the MIDAR run took three weeks to complete. It is also possible
that some of these sets share the same host key.

In summary, the validation results confirm that our technique has at least a
95% agreement with state-of-the-art.

Table 2. Alias Sets Validation

| Sample size | Agree | Disagree |
---|---|---|---|---
SSH-BGP | 1.34k | 1.29k | 53 |
SSH-SNMPv3 | 13.6k | 13.2k | 398 |
BGP-SNMPv3 | 1.84k | 1.76k | 87 |
SSH-MIDAR | 8.5k | 8.1k | 366 |

###  2.7. Limitations

Our methodology provides the largest sets of alias and dual-stack addresses to
date. However, we do note a few limitations:

  * •

First, our methodology relies on application-level data. As such, it is only
applicable to IPs responsive to SSH and BGP. Firewalls and access control may
block or restrict access to the these services which can limit the alias
inference.

  * •

Second, in the case of BGP, BGP speakers can have a non-unique BGP identifier
due to mis-configuration which can lead to incorrect inferences.

  * •

Third, our defined SSH identifier, might not be unique in all cases. It is in
fact possible for multiple host to share the same identifier, e.g., SSH
servers can be shipped with factory-default keys (Gasser et al., 2014;
Heninger et al., 2012). It is unlikely for two different hosts to generate the
exact same host key, however, unless an administrator chose to use the same
key pair across multiple hosts.

  * •

Lastly, our validation is limited by the relatively small number of
overlapping sets with other techniques, the responsiveness of a service on all
IPs in a given set, and the possibility of IP churn.

##  3\. Ethical Considerations

For our active experiments we do our best to minimize additional load or harm
on the destination devices. BGP, SSH, and SNMPv3 load is very low (only a few
packets per destination). Moreover, we randomly distribute our measurements
over the address space for our experiment, ensuring that at most one packet
reaches a target IP each second. Furthermore, we coordinate with local network
administrators to ensure that our scanning efforts do not harm the local or
upstream network. For the active scanning we use best current practices
(Durumeric et al., 2013; Partridge and Allman, 2016; Dittrich et al., 2012) to
ensure that our prober IP address has a meaningful DNS PTR record.
Additionally, we show information about our measurements and opt-out
possibilities on a website of our scanning servers. During our active
experiments, we did not receive any complaints or opt-out requests.

##  4\. Analysis

In this section we present our results, consisting of alias resolution and
dual-stack statistics as well as AS-level analyses.

###  4.1. Alias Resolution

To identify alias sets, we group IP addresses with identical unique
identifiers for SSH and BGP. We also supplement our findings with SNMPv3 as
described in (Albakour et al., 2021). In Table 3 we report the number of non-
singleton alias sets and the contribution of each individual protocol, data
source, and the union of all. In IPv4, the SSH active scan results in 505k
alias sets, which cover over 3.2M unique IPv4 addresses. Similarly, the Censys
dataset results in 699k alias sets, covering more than 4.6M IPv4 addresses.
Censys data provide a notable increase of 70% and 80% in the number of IPv4
addresses and resulting alias sets compared to the active measurement alone.

With BGP, both Censys and the active scan produce similar results, with 12k
alias sets covering 175k IPv4 addresses. In contrast, our SNMPv3 scan results
in 557k alias sets covering 6.1M IPv4 addresses. By consolidating these
findings, we can effectively cover more than 11.8M IPv4 addresses.

Interestingly, a substantial majority of 97% of these addresses only respond
to a single service, while only 3% are responsive to two or three services.
Consequently, this stark difference increases the resulting alias sets,
exceeding 1.4M, of which 40% can only be identified with SNMPv3 and 60% (which
is more than double what can be achieved by SNMPv3 alone) with SSH or BGP. We
note however, that the majority of these sets comes from SSH. In Figure 3 we
show the distribution of IPv4 addresses per alias set. We find that the
majority of the sets contain less than 100 addresses. Additionally, more that
60% of SSH alias sets contain only two addresses compared to less than 30% for
BGP and SNMPv3. BGP sets are also more likely to contain more addresses
compared to sets derived from SSH and SNMPv3. We also note a similar set size
regardless of the data source.

For IPv6, the active SSH scan results in 47k alias sets that cover 266k unique
IPv6 addresses. Moreover, we find 8.3k and 16.7k alias sets, covering 48k and
71k IPv6 addresses with BGP and SNMPv3, respectively. Merging these results we
obtain over 66k IPv6 alias sets, with a coverage of more than 340k unique IPv6
addresses. Similar to our IPv4 results, a majority of 94% of these addresses
are only responsive to a single service, while 6% are responsive to two or
three services. This results in 25% of the IPv6 alias sets being identifiable
only with SNMPv3, while 75% can be identified with SSH and BGP. In Figure 4 we
show the distribution of IPv6 addresses per alias set. Similar to IPv4, the
majority of sets contain less that 100 addresses. Additionally, SSH sets are
more likely to contain fewer IPv6 addresses compared to BGP and SNMPv3. We
also note a similar set size for BGP and SNMPv3.

Table 3. Alias Sets Overview

Source | Active (IPs) | Censys (IPs) | Union (IPs) |
---|---|---|---|---
{4*[IPv4] | SSH | 505k (3.2M) | 699k (4.6M) | 926k (5.7M) |
| BGP | 12k (175k) | 12k (175k) | 12k (175k) |
| SNMPv3 | 557k (6.1M) | n.a | 557k (6.1M) |
| Union | 1.04M | 708k | 1.4M (11.8M) |
{4*[IPv6] | SSH | 47k (266k) | n.a | n.a |
| BGP | 8.3k (48k) | n.a | n.a |
| SNMPv3 | 16.7k (71k) | n.a | n.a |
| Union | 66k |  |  |

Figure 3. IPv4 addresses per alias sets Figure 4. IPv6 addresses per alias
sets

###  4.2. Dual-Stack Inference

Next, we shift our attention to the results of dual-stack identification, as
summarized in Table 4. We merge alias sets from IPv4 and IPv6, if they use the
same unique identifier. The SSH active scan results in more than 634k dual-
stack alias sets, which cover 1.05M IPv4 addresses and 771k IPv6 addresses.
With BGP, we identify 4.2k dual-stack sets, covering 78k IPv4 addresses and
16.3k IPv6 addresses. Additionally, SNMPv3 discovers 21k dual-stack alias sets
that cover 1.1M IPv4 addresses and 45k IPv6 addresses. Consolidating these
findings results in a total of 650k dual-stack alias sets, of which 3% can
only be identified with SNMPv3, while 97% (30$\times$ compared to SNMPv3
alone) can only be identified with SSH or BGP. Further, these sets cover a
total of 2.2M IPv4 addresses and 830k IPv6 addresses. Notably, more than 88%
of the dual-stack sets contains a single IPv4 and a single IPv6 addresses, 7%
set with 2-10 addresses, and only 2% with more than 10 addresses. It is worth
noting that our IPv6 sample size is relatively small compared to IPv4.
Nonetheless, these results indicate that a substantial portion of known IPv6
addresses are exclusively IPv6-enabled, with just 64% of the IPv6 addresses
having an IPv4 counterpart. However, it is also possible that some host are
only responsive over IPv6 due to policy as shown by previous work (Czyz et
al., 2016).

Table 4. Dual-Stack Sets

| IPv4 addr | IPv6 addr | Dual Stack Sets
---|---|---|---
SSH | 1.05M | 771k | 634k
BGP | 78k | 16.3k | 4.2k
SNMPv3 | 1.1M | 45k | 21k
Union | 2.2M | 830k | 650k

###  4.3. AS-Level Analysis

Figure 5 shows the distribution of Autonomous System Numbers (ASNs) per IPv4
alias set. We find that less than 10% of SSH and SNMPv3 sets contain addresses
associated with two or more ASes. In contrast, over 35% of BGP sets contain
addresses associated with multiple ASes. This outcome aligns with
expectations, as BGP typically consist of border routers that connect
different ASes.

Figure 5. ASN per IPv4 Alias Set

In Figure 6, we show the distribution of the number of alias and dual-stack
sets per AS. We find that over 37k ASes contain at least one set. The majority
of ASes have fewer than 100 sets, and only 3% of ASes have more than 100 alias
sets.

Figure 6. Distribution of the number of alias sets per AS. Table 5. Top 10
ASes for IPv4 alias sets for each protocol separately and for the union. Each
cell shows the ASN as well as the number of alias sets in parenthesis.

Rank | SSH | BGP | SNMPv3 | Union
---|---|---|---|---
1 | 14061 (68k) | 21859 (311) | 3269 (19k) | 14061 (68k)
2 | 22927 (61k) | 701 (288) | 30722 (12k) | 22927 (61k)
3 | 16509 (46k) | 42689 (211) | 3320 (10k) | 16509 (46k)
4 | 16276 (28k) | 19429 (182) | 12874 (10k) | 16276 (29k)
5 | 24940 (24k) | 24940 (162) | 4134 (8k) | 4134 (25k)
6 | 14618 (23k) | 3269 (159) | 8881 (8k) | 24940 (24k)
7 | 45102 (19k) | 20473 (144) | 5089 (7.5k) | 3269 (23k)
8 | 4134 (17k) | 12389 (144) | 3301 (7k) | 14618 (23k)
9 | 396982 (17k) | 852 (101) | 7018 (7k) | 3320 (20k)
10 | 46606 (15k) | 17511 (96) | 7029 (6.6k) | 45102 (19k)

To better understand the main contributors of alias sets, we now focus on the
top 10 ASes. In Table 5, we report the largest AS based on different protocols
as well as the union of all three protocols for IPv4. We expect SSH to be
predominantly prevalent in cloud provider networks, whereas BGP and SNMPv3 to
be more prevalent in ISP networks. Indeed, among the top 10 ASes for SSH, 8
are cloud service providers, including DigitalOcean (rank 1, AS14061), Amazon
(rank 3, AS16509; rank 6, AS14618), and OVH (rank 4, AS16276). Surprisingly,
however, we also observe two major ISPs: Telefonica de Argentina (rank 2,
AS22927) and China Telecom (rank 8, AS4134). Shifting our focus to the top 10
ASes in the BGP and SNMPv3 data, we find that 8 of them are ISPs, while the
remaining 2 are cloud service providers. The top three ASes for BGP are
Zenlayer (AS21859), Verizon (AS701), and Glide (AS42689); the top three for
SNMPv3 are Telecom Italia (AS3269), Vodafone Italy (AS30722), and Deutsche
Telekom (AS3320). Lastly, we consider the union of all data sources. We find
this to be dominated by similar ASes as in the SSH data set, with a split of 6
cloud service providers and 4 ISPs.

Table 6. Top 10 ASes for IPv6 alias and dual-stack sets. Each cell shows the ASN as well as the number of alias sets in parenthesis. Rank | IPv6 | Dual-stack
---|---|---
1 | 7684 (4k) | 14061 (215k)
2 | 63949 (3.2k) | 63949 (112k)
3 | 4837 (1.8k) | 16276 (34k)
4 | 4134 (1.4k) | 12876 (13k)
5 | 6939 (1.1k) | 197695 (13k)
6 | 26347 (943) | 8972 (8.7k)
7 | 9808 (731) | 20473 (8.5k)
8 | 197540 (713) | 8560 (8.5k)
9 | 7922 (707) | 7506 (7.7k)
10 | 20857 (685) | 51167 (7.6k)

We conclude our analysis by considering the largest 10 ASes with IPv6 alias
sets and dual-stack alias sets. Table 6 shows the union results of all three
protocols for IPv6 and IPv4-IPv6 dual-stack alias sets. The IPv6 alias sets
spread over 7k ASes in total. The top 10 are split between 7 ISPs (e.g.,
Hurricane Electric, AS6939; China Unicom, AS4837; Chinanet, AS4134) and 3
cloud service providers (e.g., Akamai, AS63949; Dreamhost, AS26347). Finally,
our dual-stack alias sets cover more than 9.5k ASes. Note that this includes
sets with at least a single IPv4 and a single IPv6 address. We find that the
top 3 ASes are cloud service provides (DigitalOcean, ASAS14061; Linode,
AS63949; OVH, AS16276) and cover more than 54% of the total dual-stack sets.
The remaining 7 are ISPs and cover only 10% of all dual-stack alias sets.

##  5\. Conclusion

In this paper we introduced a multi-protocol approach to improve IP alias
resolution and dual-stack identification. Our key observation is that a unique
identifier for each protocol can be used to group different subsets of alias
sets. We evaluated our method with two popular protocols, namely, SSH and BGP,
and we showed that our technique substantially increases both the number of
alias as well as dual-stack sets, compared to similar protocol-centric
technique such as SNMPv3. Our results showed that we can supplement previous
work and identify up to 1.4 million non-singleton IPv4 alias sets, i.e.,
double compared to what can be achieved with previously known technique. Our
results also showed that we can identify more than 650 thousand dual-stack
alias sets. By a large margin (30$\times$), this is the largest set reported
to date.

As part of our future research agenda, we plan to investigate if other popular
protocols are associated with unique identifiers that will further increase
the IP coverage of alias and dual-stack sets. We also plan to inspect SSH
identifiers more in-depth, specifically in terms of consistency and stability.
Moreover, we plan to use updated IPv6 hit-list as we were limited to these
publicly available in this paper. Our initial results are very encouraging,
and we plan to perform additional measurements from multiple vantage points
(VPs) to understand the effect of geographical VP location.

## Acknowledgements

We would like to thank our shepherd, Liz Izhikevich, and the anonymous
reviewers for their valuable comments. This work was supported in part by the
European Research Council (ERC) under Starting Grant ResolutioNet (ERC-
StG-679158).

## References

  * (1)
  * Albakour et al. (2021) Taha Albakour, Oliver Gasser, Robert Beverly, and Georgios Smaragdakis. 2021.  Third Time’s Not a Charm: Exploiting SNMPv3 for Router Fingerprinting. In _ACM IMC_.
  * Albakour et al. (2023) Taha Albakour, Oliver Gasser, and Georgios Smaragdakis. 2023\.  Pushing Alias Resolution to the Limit (artifacts).  https://routerfingerprinting.github.io/.
  * Bender et al. (2008) Adam Bender, Rob Sherwood, and Neil Spring. 2008\.  Fixing Ally’s Growing Pains with Velocity Modeling. In _ACM IMC_.
  * Berger et al. (2013) Arthur Berger, Nicholas Weaver, Robert Beverly, and Larry Campbell. 2013.  Internet Nameserver IPv4 and IPv6 Address Relationships. In _ACM IMC_.
  * CAIDA (2023) CAIDA. 2023.  iffinder.  https://catalog.caida.org/software/iffinder.
  * Chandra and Scudder (2009) Ravi Chandra and John Scudder. 2009.  Capabilities Advertisement with BGP-4.  IETF RFC 5492.
  * Chandrasekaran et al. (2015) Balakrishnan Chandrasekaran, Georgios Smaragdakis, Arthur Berger, Matthew Luckie, and Keung-Chi Ng. 2015\.  A Server-to-Server View of the Internet. In _ACM CoNEXT_.
  * claffy (2011) kc claffy. 2011\.  Tracking IPv6 Evolution: Data We Have and Data We Need.  _ACM Computer Communication Review_ 3 (2011).  Issue 41.
  * Czyz et al. (2016) Jakub Czyz, Matthew Luckie, Mark Allman, and Michael Bailey. 2016.  Don’t Forget to Lock the Back Door! A Characterization of IPv6 Network Security Policy. In _NDSS_.
  * Dittrich et al. (2012) David Dittrich, Erin Kenneally, et al. 2012\.  The Menlo Report: Ethical Principles Guiding Information and Communication Technology Research.  _U.S. Department of Homeland Security_ (2012).
  * Dulaunoy et al. (2022) Alexandre Dulaunoy, Jean-Louis Huynen, and Aurelien Thirion. 2022.  Active and Passive Collection of SSH Key Material for Cyber Threat Intelligence.  _Digital Threats_ (2022).
  * Durumeric et al. (2015) Zakir Durumeric, David Adrian, Ariana Mirian, Michael Bailey, and J. Alex Halderman. 2015.  A Search Engine Backed by Internet-Wide Scanning. In _ACM CCS_.
  * Durumeric et al. (2013) Zakir Durumeric, Eric Wustrow, and J. Alex Halderman. 2013\.  ZMap: Fast Internet-Wide Scanning and its Security Applications. In _USENIX Security Symposium_.
  * Gasser et al. (2014) Oliver Gasser, Ralph Holz, and Georg Carle. 2014.  A Deeper Understanding of SSH: Results from Internet-wide scans. In _IEEE/IFIP Network Operations and Management Symposium_.
  * Gasser et al. (2018) Oliver Gasser, Quirin Scheitle, Pawel Foremski, Qasim Lone, Maciej Korczyński, Stephen D. Strowes, Luuk Hendriks, and Georg Carle. 2018.  Clusters in the Expanse: Understanding and Unbiasing IPv6 Hitlists. In _ACM IMC_.
  * GitHub (2023) ZGrab 2.0 GitHub. 2023\.  Fast Go Application Scanner.  urlhttps://github.com/zmap/zgrab2.
  * Gunes and Sarac (2007) Mehmet Hadi Gunes and Kamil Sarac. 2007.  Importance of IP Alias Resolution in Sampling Internet Topologies. In _IEEE Global Internet Symposium_.
  * Hawkinson and Bates (1996) John A. Hawkinson and Tony J. Bates. 1996.  Guidelines for creation, selection, and registration of an Autonomous System (AS).  https://www.rfc-editor.org/info/rfc1930
  * Heninger et al. (2012) Nadia Heninger, Zakir Durumeric, Eric Wustrow, and J. Alex Halderman. 2012.  Mining your Ps and Qs: Detection of widespreadweak keys in network devices. In _USENIX Security Symposium_.
  * Keys et al. (2013) Ken Keys, Young Hyun, Matthew Luckie, and Kim Claffy. 2013\.  Internet-Scale IPv4 Alias Resolution with MIDAR.  _IEEE/ACM Trans. Networking_ 21 (2013).  Issue 2.
  * Lonvick and Ylonen (2006) Chris M. Lonvick and Tatu Ylonen. 2006.  The Secure Shell (SSH) Transport Layer Protocol.  https://www.rfc-editor.org/info/rfc4253
  * Luckie et al. (2013) Matthew Luckie, Robert Beverly, William Brinkmeyer, and kc claffy. 2013.  Speedtrap: Internet-Scale IPv6 Alias Resolution. In _ACM IMC_.
  * Luckie et al. (2019) Matthew Luckie, Bradley Huffaker, and k claffy. 2019\.  Learning Regexes to Extract Router Names from Hostnames. In _ACM IMC_.
  * Padmanabhan et al. (2022) Ramakrishna Padmanabhan, John P. Rula, Philipp Richter, Stephen D. Strowes, and Alberto Dainotti. 2022.  DynamIPs: Analyzing address assignment practices in IPv4 and IPv6. In _ACM CoNEXT_.
  * Partridge and Allman (2016) Craig Partridge and Mark Allman. 2016.  Ethical Considerations in Network Measurement Papers.  _Comm. of the ACM_ 59, 10 (2016).
  * Pujol et al. (2017) Enric Pujol, Philipp Richter, and Anja” Feldmann. 2017\.  Understanding the Share of IPv6 Traffic in a Dual-stack ISP. In _PAM_.
  * Rekhter et al. (2006) Yakov Rekhter, Susan Hares, and Tony Li. 2006.  A Border Gateway Protocol 4 (BGP-4).  IEFT RFC 4271.
  * Spring et al. (2002) Neil Spring, Ratul Mahajan, and David Wetherall. 2002\.  Measuring ISP topologies with Rocketfuel. In _ACM SIGCOMM_.
  * Vermeulen et al. (2022) Kevin Vermeulen, Ege Gurmericliler, Italo Cunha, David Choffnes, and Ethan Katz-Bassett. 2022\.  Internet Scale Reverse Traceroute. In _ACM IMC_.
  * Wan et al. (2020) Gerry Wan, Liz Izhikevich, David Adrian, Katsunari Yoshioka, Ralph Holz, Christian Rossow, and Zakir Durumeric. 2020.  On the Origin of Scanning: The Impact of Location on Internet-Wide Scans. In _ACM IMC_.
  * Willie Bythwood, Andrew Kien, and Iman Vakilinia (2023) Willie Bythwood, Andrew Kien, and Iman Vakilinia. 2023.  Fingerprinting Bots in a Hybrid Honeypot. In _SoutheastCon 2023_. 76–80.
  * Zirngibl et al. (2022) Johannes Zirngibl, Lion Steger, Patrick Sattler, Oliver Gasser, and Georg Carle. 2022.  Rusty Clusters? Dusting an IPv6 Research Foundation. In _ACM IMC_.


h A`j_2``\eta (A+1)]

\efig
\]

which exists because \( \eta \) is taut. It is just
\( \Delta [\eta] (A) \).

The multiplication comes from the chain rule
transformation. It is

\[
(T^2 A, \Delta [T](TA) \times \Delta [T] (A) \times B)
\to^{(\mu A, m A \times B)}
(TA, \Delta [T] (A) \times B)
\]

where \( m A \) is the composite

\[
\Delta [T] (TA) \times \Delta [T] (A) \to/ >->/<200>^\gamma
\Delta [T^2] (A) \to^{\Delta[\mu](A)}
\Delta [T] (A) \rlap{\ .}
\]

The \( B \) looks just tacked on with nothing to do
with \( T \) or \( A \), but they are intertwined via
the associativity law for the monad
\( D (T, \eta, \mu) \). We won't look at this directly,
but it is apparent when we consider Eilenberg-Moore
algebras for it. An algebra is

\[
(\alpha, \beta) \colon (TA, \Delta [T] (A) \times B) \to (A, B)
\]

such that \( (A, \alpha) \) is a \( T \)-algebra and
\( \beta \) makes the following diagrams commute

\[
\bfig
\qtriangle/>`>`>/<800,450>[1 \times B`\Delta {[}T{]} (A) \times B`B;
h \times B`\cong`\beta]

\efig
\]

\[
\bfig
\square/>``>`>/<1600,1000>[\Delta {[}T{]} (TA) \times \Delta {[}T{]} (A) \times B
`\Delta {[}T{]}(A) \times B`\Delta {[}T{]} (A) \times B`B\rlap{\ .};
\Delta {[}T{]} (\alpha) \times B``\beta`\beta]

\morphism(0,1000)/>/<0,-500>[\Delta {[}T{]} (TA) \times \Delta {[}T{]} (A) \times B`
\Delta {[}T^2{]}(A) \times B;\gamma \times B]

\morphism(0,500)/>/<0,-500>[\Delta {[}T^2{]}(A) \times B`
\Delta {[}T{]} (A) \times B;\Delta {[}\mu{]} \times B]

\efig
\]

We see the \( \alpha \) appearing in the top row  in
the equations for \( \beta \).

§.§ Dirichlet functors

The analysis of $ {\mathbb P} $ easily generalizes to
the covariant exponentials $ L^X $.

Let $ L $ be a sup-lattice, then

\Delta [L^X] \cong L_* \times L^X

where $ L_* = \{l \in L\ |\ l \neq \bot\} $.

An element of $ L^{(X+1)} $ is a function
$ X + 1 \to^{[\phi, l]} L $ where $ \phi \colon X \to L $
and $ l \in L $. If $ f \colon X \to Y $ and
$ L^f [\phi, l] = [\psi, m] \colon Y+1 \to L $,
then $ \psi (y) = \bigvee_{f x = y} \phi(x) $ and
$ m $ is the sup over all pre-images of $ * $,
i.e. $ \{*\} $, so $ m = l $, i.e. $ L^{(X+1)} \cong
L^X \times L $, as functors.

$ L^j (\phi) = [\phi, \bot] \colon X + 1 \to L $ where
$ \phi \colon X \to L $ and $ \bot $ is the bottom
element of $ L $, i.e. the sup of the empty set,
$ j^{-1} \{*\} $. This gives the result.

Recall that for $ l \in L $, a sup lattice, $ D(l) $
denotes the down-set of $ l $, $ \{l'\in L\ |\ l' \leq l\} $,
which is a sub sup lattice of $ L $.

Let $ C_l = \{l' \in L \ |\ l \vee l' = \top \mbox{\ and\ }
l' \neq \bot\} $. Then

\Delta [L^{[X]}] \cong \sum_{l \in L} C_l \cdot
D(l)^{[X]} \rlap{\ .}

The proof is similar to that of the previous proposition.
An element of $ \Delta [L^{[X]}] $ is a function
$ [\phi, l'] \colon X+1 \to L $ for $ l' \neq \bot $ and
$ \bigvee_{x \in X} \phi (x) \vee l' = \top $. If we let
$ l = \bigvee_{x \in X} \phi (x) $ then
$ \phi \in D(l)^{[X]} $. And there's one such $ \phi $
for each $ l' \neq \bot $ and $ l \vee l' = \top $.

$ \Delta $ of a Dirichlet functor is a Dirichlet functor.

(1) If $ \top $ is join-irreducible then

\Delta [L^{[X]}] = L_* \cdot L^{[X]} +
\sum_{l \neq \top} D(l)^{[X]}\rlap{\ .}

(2) $ \Delta [{\bf n}^{[X]}] = (n - 1) \cdot
{\bf n}^{[X]} + ({\bf n - 1})^{[X]} +
({\bf n - 2})^{[X]} + \dots +
{\bf 2}^{[X]} + {\bf 1}^{[X]} \rlap{\ .} $

(3) $ \Delta [p_*^{[X]}] = \pi (p) \cdot
p_*^{[X]} + \sum q_*^{[X]} + 1 $, the coproduct
taken over all primes $ < p $.

(1) $ \top $ join-irreducible means $ l \vee l' =
\top \Rightarrow l = \top $ or $ l' = \top $, so

$$ C_\top = L_* = \{l'\ |\ l' \neq \bot \}  \mbox{\ \ and if\ \ }
l \neq \top

then $ C_l = \{ \top\} \cong 1 $.

(2) The top element of $ {\bf n} $ is
join-irreducible, so this is a special case of (1).

(3) This is a special case of (2), given
the definition of $ p_* $.

$ \Delta $ of a sequential Dirichlet functor is
again one.

By Corollary <ref> (3) we know
that for a prime $ p $, $ \Delta p_*^{[X]} $ is
a sequential Dirichlet functor. For a composite
$ n $, $ n_* $ is a cartesian product
of $ p_* $'s so by Proposition <ref>,
$ \Delta n_*^{[X]} $ is also a
sequential Dirichlet functor. Finally, $ \Delta $
of a sequential Dirichlet functor is a coproduct
of $ \Delta n_*^{[X]} $'s so is
again one.

§ A NEWTON SUMMATION FORMULA

For a function $ f \colon {\mathbb R} \to {\mathbb R} $, the
difference operator $ \Delta $

\Delta [f] (x) = f (x + 1) - f (x)

can be iterated giving discrete versions of  higher
derivatives. Thus

\Delta^2 [f] (x) = f(x + 2) - 2 f(x + 1) + f(x)

\Delta^3 [f] (x) = f (x + 3) - 3 f (x + 2) + 3 f(x + 1) - f (x)

and so on.

The Newton series is a discrete analog of Taylor series,
trying to recover $ f $ or some reasonable approximation
of $ f $, from specific values $ \Delta^k [f] (a) $. It takes
the form

\begin{eqnarray}
g (x) &  = & \sum^\infty_{n = 0} {{\Delta^n [f](a)}\over {n!}} (x - a)^{\downarrow n}\\
& = & \sum^\infty_{n = 0} \binom{x - a}{n}
\Delta^n [f](a)
\end{eqnarray}

where $ (x - a)^{\downarrow n} $ is the falling power

(x - a) (x - a - 1) (x - a - 2) \dots (x - a - n + 1)

and $ \binom{x - a}{n} $ is the “binomial coefficient”

{(x - a) (x - a - 1) \dots (x - a - n + 1)}\rlap{\ \ .}\over

The formulas (1) and (2) look sufficiently combinatorial
to suggest that there may be a similar formula for
taut endofunctors of $ {\bf Set} $, and indeed there is.
That is what we develop in this section.

This section has significant overlap with <cit.>
but it is hard to isolate what precisely. Their objective was
completely different from ours, concentrating on monads,
theories, and operads. But crucial points here appear at
various points in their work. They clearly recognized the
importance of the category $ {\bf Surj} $ of finite cardinals
and surjections (there called $ {\mathbb S} $) and its
relation to soft analytic functors (called semi-analytic).
Their Theorem 2.2 is basically Part I of our main
theorem below. In particular the $ A [n] $ of their
Lemma 2.5 is $ \Delta^n [F] (0) $ by our
Corollary <ref>.

Neither of the formulas (1) or (2) generalize directly
to functors, even for $ a = 0 $. We need more structure
on the higher differences $ \Delta^n [F] $, and to
study this we need a better understanding of them.

The suggestive notation $ \Delta [F] (X) = F (X + 1) \setminus
F(X) $ is too suggestive here. Blindly applying the
difference twice would give

\begin{eqnarray}
\Delta^2 [F] (X) & = & (F(X+2)\setminus F(X+1))\setminus
(F(X+1) \setminus F(X))\nonumber\\
& = & F(X+2) \setminus F(X+1)\nonumber
\end{eqnarray}

which is definitely wrong, as can easily be seen by
taking $ F (X) = X^2 $. We must be mindful of which
injection we are complementing.

To track the injections, let's take two different one-point
sets $ 1_a = \{a\} $ as $ 1_b = \{b\} $ with corresponding
difference operators

\begin{eqnarray}
\Delta_a [F] (X) & = & F(X + 1_a) \setminus F(X)\nonumber\\
\Delta_b [F] (X) & = & F (X + 1_b) \setminus F(X)\nonumber\rlap{\ .}
\end{eqnarray}

Thus we have

\begin{eqnarray}
\Delta_a [\Delta_b [F]] (X) & = & \Delta_b [F] (X+1_a) \setminus \Delta_b[F] (X)\nonumber\\
& = & \Bigl(F(X+1_a +1_b)\setminus F(X+1_a)\Bigr) \setminus \Bigl(F(X+1_b)\setminus F(X)\Bigr) \nonumber\\
& = & F (X+1_a +1_b) \setminus \Bigl(F(X+1_a) \cup F (X+1_b)\Bigr)\nonumber
\end{eqnarray}

as $ F (X) \subseteq F (X + 1_a) $.

This leads to the following. Let $ S_A \colon {\bf Set} \to {\bf Set} $
be the translation functor $ S_A (X) = X + A $, which is obviously
taut. For any taut functor $ F \colon {\bf Set} \to {\bf Set} $ and
any set $ X $, let $ D_A [F] (X) $ be the subset of $ F(X+A) $
consisting of those $ a \in F(X+A) $ not in the image of
$ F(X+A_0) \to/ >->/<200> F (X+A) $ for any proper subset
$ A_0 \subsetneq A $. As there will be much talk of proper
subsets in what follows, we will use an arrow with a double tail
$ A_0 \to/ >>->/<200> A $ to indicate a monomorphism which
is not an isomorphism.

$ D_A [F] $ is a taut subfunctor of $ FS_A $.

First we show it's a subfunctor. Let $ f \colon X \to Y $
and $ a \in FS_A (X) = F (X + A) $. Then $ F (f+A) (a)
\in F(Y+A) $. Let $ A_0 \to/ >>->/<200> A $ be a proper
subset of $ A $. Then as

\bfig
\square/ >->`>`>` >->/<550,500>[X+A_0`X+A`Y+A_0`Y+A;

\efig

is a pullback and as $ F $ is taut

\bfig
\square/ >->`>`>` >->/<700,500>[F(X+A_0)`F(X+A)`F(Y+A_0)`F(Y+A);
`F(f + A_0)`F(f+A)`]

\efig

is also a pullback. Thus if $ F(f+A)(a) $ were in
$ F(Y+A_0) $, $ a $ would be in $ F(X+A_0) $. So
if $ a \in D_A [F](X) $, $ F(f+A)(a) $ is in
$ D_A[F](Y) $, i.e. $ D_A [F] $ is a subfunctor of
$ FS_A $.

$ D_A [F](X) $ is defined to be the complement of

\bigcup F (X+A_0) \subseteq F (X+A) \rlap{ ,}

the union taken over all proper subsets
$ A \to/ >>->/<200> A $. Thus $ D_A [F] $ is a
complemented subfunctor of $ F S_A $ and
by Proposition <ref> is taut.

$ D_A [D_B [F]] \cong D_{A+B} [F] \rlap{ .} $

An element $ a \in D_A [D_B[F]] (X) $ is an
element $ a \in D_B[F] (X+A) $ which is not in
any $ D_B [F] (X+A_0) $ for a proper subset
$ A_0 \subsetneq A $. The first condition means
that $ a \in F(X+A+B) $ but not in any
$ F(X+A+B_0) $ for a proper subset $ B_0 \subseteq B $.
The second condition ($ (a \notin D_B [F] (X+A_0) $)
means that $ a $ is not in $ F(X+A_0+B) $ or there
exists a proper subset $ B_0 \subsetneq B $ with
$ a \in F (A+A_0+B_0) $. But this last condition is
impossible, for if $ a $ were in $ F(X+A_0+B_0) $
it would be in $ F(X+A+B_0) $ which it is not. The
conclusion is that $ a \in D_A[D_B [F] (X) $ if and
only if $ a \in F(X+A+B) $ but $ a \notin F(X+A+B_0) $
and $ a \notin F (X+A_0+B) $. This is equivalent to
$ a \in F(X+A+B) $ and $ a \notin F(X+C) $ for any
proper subset $ C \subsetneq A+B $ because such
a $ C $ would be contained in either a $ A_0 +B $
or a $ A + B_0 $. The result follows.

For any finite cardinal $ n $

\Delta^n [F] = D_n [F]

\Delta^n [F] (X) = \{a \in F(X+n) | a \notin F(X+n_0)
\mbox{\ \ for any\ \ } n_0 \to/ >>->/<200> n \} .

$ \Delta^0 [F] = F = D_0 [F] $ and $ \Delta^1 [F]
= \Delta F = D_1 [F] $ by definition. The result now
follows from the previous proposition by induction.

We are hoping to recover $ F $ from the sequence
$ \Delta^n [F](0) $ via some version of the Newton
series, at least for polynomial functors. From the
above description of $ \Delta^n [F] (0) $, it is clear
that $ S_k $ acts on $ \Delta^n[F](0) $ so we get a
symmetric sequence (species) and a corresponding
analytic functor

\sum^\infty_{n = 0} X^n \otimes_{S_n} \Delta^n [F](0) .

This looks promising but it doesn't give $ F $ even
for polynomials. For example $ F (X) = X^n $ is
connected but the above analytic functor is not.
It's defined as a sum of (non trivial) functors. We
need something a bit tighter. In fact, not only do
bijections act on the $ \Delta^n [F](a) $ but
epimorphisms do too, in the appropriate sense of

Let $ {\bf Surj} $ be the category of finite cardinals
with surjections as morphisms.

Although it will not be used below, it may be of
interest to note that \( {\bf Surj} \) is the free
symmetric monoidal category generated by a
commutative semigroup.

For any taut functor $ F \colon {\bf Set} \to {\bf Set} $
and set $ A $, the family $ \langle \Delta^n [F](A)\rangle_n $
is the object part of a functor

{\bf Surj} \to {\bf Set} .

Let $ f \colon m \to/->>/<200> n $ be a surjection and
$ a \in \Delta^m [F](A) $, so $ a \in F (A+m) $ but
$ a \notin F(A+m_0) $ for any $ m_0 \to/ >>->/<200> m $.
Then $ F(A+f) (a) \in F (A+n) $ and we have to show
that it's not in any $ F(A+n_0) $ for $ n_0 \to/ >>->/<200> n $.
Suppose it were. Take the pullback

\bfig
\square/ >>->`>`->>` >>->/[m_0\ `n`n_0\ `m\rlap{ .};

\place(250,250)[\framebox{\scriptsize Pb}]

\efig

As usual $ m_0 \to/ >->/<200> m $ is monic, but it
is also proper because $ f $ is surjective. $ F $
being taut produces a pullback

\bfig
\square/ >->`>`>` >->/<700,500>[F(A+m_0)`F(A+m)`F(A+n_0)`F(A+n);

\place(350,250)[\framebox{\scriptsize Pb}]

\efig

so if $ F (A+f) (a) $ were in $ F (A+n_0) $, $ a $ would be
in $ F(A+m_0) $ contrary to the definition of $ a $.

Furthermore, the construction $ F \leadsto \langle \Delta^n [F]
(A) \rangle_n $ is itself functorial. If $ {\bf Taut} $ is the category
of taut endofunctors of $ {\bf Set} $ with taut natural
transformations as morphisms, then we have the following.

For any set $ A $, taking iterated differences produces
a functor

\Delta^*_A \colon {\bf Taut} \to {\bf Set}^{\bf Surj} \rlap{ .}

For $ F \colon {\bf Set} \to {\bf Set} $ a taut functor,
let $ \Delta^*_A (F) $ be given by

\Delta^*_A (F) (n) = \Delta^n [F] (A)

the functor of the previous proposition. Let
$ t \colon F \to G $ be a taut transformation. By applying
Proposition <ref> iteratively we see
that $ t S^n \colon FS^n \to GS^n $ restricts to a taut

\bfig
\square/ >->`>`>` >->/[\Delta^n{[}F{]}`FS^n`\Delta^n{[}G{]}`GS^n\rlap{ .};
`\Delta^n {[}t{]}`tS^n`]

\efig

This gives the formula for $ \Delta^*_A (t) $, namely
$ \Delta^*_A (t) (A) = t(A+n) $. So naturality of
$ \Delta^*_A (F) (m) $ in $ n $ is simply

\bfig
\square<800,500>[F(A+m)`F(A+n)`G(A+m)`G(A+n);

\efig

for any surjection $ f \colon m \to/->>/<200> n $,
which is just naturality of $ t $ itself.

Functoriality of $ \Delta^*_A  [t] $ in $ t $ follows
from the fact that it is a restriction of $ t S^n $.

Below we will be only concerned with \( \Delta^*_A \)
for \( A = 0 \) and write \( \Delta^* \) for \( \Delta^*_0 \).

Let us call a functor $ G \colon {\bf Surj} \to {\bf Set} $
a soft species (“soft” because the structures
can be compressed). A soft species produces a
soft analytic functor, the Newton sum
of $ G $.

\widetilde{G} (X) = \int^{n \in {\bf Surj}} X^n \times G (n) ,

i.e. , left Kan extension of $ G $ along the inclusion $ J $
of $ {\bf Surj} $ into $ {\bf Set} $

\bfig
\Vtriangle/ >->`>`>/<400,500>[{\bf Surj}`{\bf Set}`{\bf Set};
J`G`{\scriptsize {\rm Lan}}_J G = \widetilde{G}]

\morphism(320,300)/=>/<150,0>[`;]

\place(800,0)[.]

\efig

This is similar to the definition of analytic functor which is
the Kan extension along the inclusion of $ {\bf Bij} $ into
$ {\bf Set} $. For a species $ F \colon {\bf Bij}  \to {\bf Set} $
we can take the Kan extension of $ F $ in steps

\bfig
\Vtriangle/`>`>/<600,700>[{\bf Bij}`{\bf Set}`{\bf Set};
`F`{\scriptsize {\rm Lan}}_{JI} F]

\morphism(0,700)/ >->/<600,0>[{\bf Bij}`{\bf Surj};I]

\morphism(600,700)/ >->/<600,0>[{\bf Surj}`{\bf Set};J]

\morphism(600,700)|r|/>/<0,-700>[{\bf Surj}`{\bf Set};{\scriptsize {\rm Lan}}_I F]

\efig

so that every analytic functor is soft analytic: every
species can be softened.

It may be of interest to note that the soft species
associated to $ F $, $ \mbox{Lan}_I F $ is given by

({\rm Lan}_I F) (n) = \sum_{m \to/->>/<120> n} F(m) /_\sim

where the sum is taken over all surjections
$ f \colon m \to/->>/<200> n $, and the equivalence
relation is the quotient of $ F (m) $ by the subgroup
of $ S_m $ consisting of all elements preserving
$ f $

\bfig
\Vtriangle/>`->>`->>/<350,450>[m`m`n;\sigma`f`f]

\place(500,0)[.]

\efig

We can analyze the definition of $ \widetilde{G} $
further to connect it to analytic functors and
underline the similarity with formulas (1) and (2)
for Newton series. From the definition, $ \widetilde{G} (X) $
consists of equivalence classes $ [a \in G(n), f \colon n \to X] $
of triples $ (n, a, f) $ where the equivalence relation
is generated by the relation $ (n, a, f) \sim (m, b, g) $
if there exists a surjection $ \sigma \colon n \to/->>/<200> m $
such that $ f = g \sigma $ and $ b = G(\sigma)(a) $

\bfig
\place(0,0)[b]

\place(150,0)[\in]

\place(350,0)[G(m)]

\place(0,400)[a]

\place(150,400)[\in]

\place(350,400)[G(n)]

\morphism(0,400)/|->/<0,-300>[`;]

\morphism(350,350)|r|/>/<0,-280>[`;G(\sigma)]

\square(800,0)|arrb|/>`->>`=`>/<400,400>[n`X`m`X\rlap{ .};f`\sigma``g]

\efig

So the equivalence relation is expressed in terms of
a zigzag path of surjections and elements of $ G $
satisfying conditions as above. We will see presently
that we can assume that the $ f \colon n \to X $ is
monic, $ \sigma $ a bijection and the zigzag paths have
length one, i.e. no zigzag at all. Everything we need
can be expressed in these terms.

(1) Every equivalence class in $ \widetilde{G} (X) $ contains
a representation in which $ f $ is monic.

(2) Two elements $ (n, a, f) $ and $ (m, b, g) $ with $ f $
and $ g $ monic are equivalent if and only if $ m = n $ and
there is a bijection $ \sigma \colon n \to m $ with $ f = g \sigma $
and $ b = G(\sigma)(a) $.

(3) For a morphism $ \phi \colon X \to Y $,
$ \widetilde{G} (\phi) [n, a, f] = [m, b, g] $ where $ g $ is the
image of $ \phi f $ and $ b $ comes from $ a $ as  in

\bfig
\place(0,0)[b]

\place(150,0)[\in]

\place(350,0)[G(m)]

\place(0,400)[a]

\place(150,400)[\in]

\place(350,400)[G(n)]

\morphism(0,400)/|->/<0,-300>[`;]

\morphism(350,350)|r|/>/<0,-280>[`;G(e)]

\square(800,0)|arrb|/ >->`->>`>` >->/<400,400>[n`X`m`Y\rlap{ .};f`e`\phi`g]

\efig

(4) If $ \phi \colon X \to/ >->/<200> Y $ is monic, then so is
$ \widetilde{G} (\phi) $ and an element $ [b, m, g] $ in $ \widetilde{G}(Y) $
is in the image of $ \widetilde{G} (\phi) $ if and only if $ g $ factors
through $ \phi $

\bfig
\dtriangle/<--` >->`>/[X`m`Y\rlap{ .};`\phi`g]

\efig

(1) For any equivalence class $ [n, a, f] $ take the image
factorization of $ f $, and since the quotient of a finite
cardinal is again one, we get

\bfig
\place(-150,0)[\ov{a} = G(e)(a)]

\place(150,0)[\in]

\place(350,0)[G(\ov{n})]

\place(0,400)[a]

\place(150,400)[\in]

\place(350,400)[G(n)]

\morphism(0,400)/|->/<0,-300>[`;]

\morphism(350,350)|r|/>/<0,-280>[`;G(e)]

\square(800,0)|arrb|/>`->>`=` >->/<400,400>[n`X`\ov{n}`X;f`e``\ov{f}]

\efig

so that $ [n, a, f] = [\ov{n}, \ov{a}, \ov{f}] $.

(2) Suppose elements $ (n, a, f) $ and $ (m, b, g) $ of
the same equivalence class are related by a single
epimorphism $ \sigma \colon n \to/->>/<200> m $

\bfig
\place(0,0)[b]

\place(150,0)[\in]

\place(350,0)[G(m)]

\place(0,400)[a]

\place(150,400)[\in]

\place(350,400)[G(n)]

\morphism(0,400)/|->/<0,-300>[`;]

\morphism(350,350)|r|/>/<0,-280>[`;G(\sigma)]

\square(800,0)|arrb|/>`->>`=`>/<400,400>[n`X`m`X\rlap{ .};f`\sigma``g]

\efig

Factor $ f $ and $ g $, giving

\bfig
\square/`->>`=`/<1000,500>[n`X`m`X;`\sigma``]

\morphism(0,0)|b|/->>/<500,0>[m`\ov{m};e']

\morphism(500,0)|b|/ >->/<500,0>[\ov{m}`X\rlap{ .};\ov{g}]

\morphism(0,500)|a|/->>/<500,0>[n`\ov{n};e]

\morphism(500,500)|a|/ >->/<500,0>[\ov{n}`X;\ov{f}]

\morphism(500,500)|r|/>/<0,-500>[\ov{n}`\ov{m};\ov{\sigma}]

\efig

We see that $ \ov{\sigma} $ is both one-one and onto,
so a bijection.  Let $ \ov{a} = G(e)(a) $ and $ \ov{b} =
G(e')(b) $. Then $ G(\ov{\sigma})(\ov{a}) = \ov{b} $. So
any zigzag path relating $ (n, a, f) $ to $ (m, b, g) $

\bfig
\node a(0,0)[b]
\node b(150,0)[\in]
\node c(350,0)[G(m)]
\node d(0,300)[]
\node e(0,380)[\vdots]
\node f(350,300)[]
\node g(0,800)[a_2]
\node h(150,800)[\in]
\node i(350,800)[G(n_2)]
\node j(0,1200)[a_1]
\node k(150,1200)[\in]
\node l(350,1200)[G(n_1)]
\node m(0,1600)[a]
\node n(150,1600)[\in]
\node o(350,1600)[G(n)]
\node p(350,380)[\vdots]

\node a'(800,0)[m]
\node b'(1300,0)[X]
\node c'(800,800)[n_2]
\node d'(1300,800)[X]
\node d''(800,300)[]
\node f''(1300,300)[]
\node e'(800,1200)[n_1]
\node f'(1300,1200)[X]
\node g'(800,1600)[n]
\node h'(1300,1600)[X]
\node i'(800,380)[\vdots]
\node j'(1300,380)[\vdots]

\arrow/|->/[a`d;]
\arrow/>/[c`f;]
\arrow/|->/[g`e;]
\arrow/|->/[g`j;]
\arrow/>/[i`l;]
\arrow/|->/[m`j;]
\arrow/>/[o`l;]
\arrow/->>/[a'`d'';]
\arrow/=/[b'`f'';]
\arrow/->>/[c'`i';]
\arrow/=/[d'`j';]
\arrow|l|/->>/[c'`e';\sigma_2]
\arrow/=/[d'`f';]
\arrow/->>/[g'`e';\sigma_1]
\arrow/=/[h'`f';]

\arrow|b|/ >->/[a'`b';g]
\arrow|a|/>/[c'`d';f_2]
\arrow|a|/>/[e'`f';f_1]
\arrow|a|/ >->/[g'`h';f]
\arrow/>/[i`p;]

\efig

can be replaced with one in which all the $ f_i $
are monic and all the $ \sigma_i $ bijections.
Replacing the backward $ \sigma $'s by their
inverses gives a path of length $ 1 $.

(3) For a morphism $ \phi \colon X \to Y $,
$ \widetilde{G} (\phi) $ is given by composition,
$ \widetilde{G} (\phi) [n, a, f] = [n, a, \phi f] $ and
if we want to express this with a monic $ g $ we
factor $ \phi f $,

\bfig
\node a(0,0)[b]
\node b(150,0)[\in]
\node c(350,0)[G(m)]
\node d(700,0)[m]
\node e(1200,0)[Y]
\node f(0,400)[a]
\node g(150,400)[\in]
\node h(350,400)[(n)]
\node i(700,400)[n]
\node j(1200,400)[X]

\arrow/|->/[f`a;]
\arrow|r|/>/[h`c;G(e)]
\arrow|r|/->>/[i`d;e]
\arrow|r|/>/[j`e;\phi]
\arrow|b|/ >->/[d`e;g]
\arrow|a|/ >->/[i`j;f]

\efig

and $ [n, a, \phi f] = [m, b, g] $.

(4) A monomorphism in $ {\bf Set} $, $ \phi \colon X \to/ >->/<200> Y $
is split, unless $ X = \emptyset \neq Y $, and will be automatically
preserved. In case $ X = \emptyset $, an element of
$ \widetilde{G} (\emptyset) $ is of the form
$ [a~\in~G(\emptyset), \emptyset \to/ >->/<200> \ \emptyset] $ and
$ \widetilde{G} (\phi) $ will take it to $ [a \in G(\emptyset),
\emptyset \to/ >->/<200> Y] $.
This is also monic because the equivalence relation is

For the second part of the statement, the “if” is
trivial. So suppose we have an element $ [m, b, g] $,
with $ g $ monic, in the image of $ \widetilde{G} (\phi) $
so that there is $ [n, a, f] $, with $ f $ monic, in
$ \widetilde{G} (\phi) $ with $ [m, b, g] = [n, a, \phi f] $.
Then by (2) there is a bijection $ \sigma $ such that

\bfig
\node a(0,0)[b]
\node b(150,0)[\in]
\node c(350,0)[G(m)]
\node d(700,0)[m]
\node e(1300,0)[Y]
\node f(0,400)[a]
\node g(150,400)[\in]
\node h(350,400)[G(n)]
\node i(700,400)[n]
\node j(1000,400)[X]
\node k(1300,400)[Y]

\arrow/|->/[a`f;]
\arrow/>/[c`h;]
\arrow|r|/>/[d`i;\sigma]
\arrow/=/[e`k;]
\arrow|b|/ >->/[d`e;g]
\arrow|a|/ >->/[i`j;f]
\arrow|a|/ >->/[j`k;\phi]

\efig

and there is our factorization.

So we see that $ \widetilde{G} $ on objects is given

\widetilde{G} (X) = \sum^\infty_{n = 0} G(n) \times {\rm Mono}
(n, X)/S_n

which, if we take $ G = \Delta^* [F] $, looks a lot like
formula (2) for the Newton sum. It also looks like the
formula for an analytic functor. But $ \widetilde{G} $ is
not the coproduct of functors that this might suggest.
First of all $ {\rm Mono} (n, X) $ is not functorial in $ X $,
and secondly $ \widetilde{G} $ is a coend over $ {\bf Surj} $,
so surjections have to be accounted for. The point is that
the extra structure that $ G $ has compensates for
the shortfalls of $ {\rm Mono} (n, X) $.

Power series functors

\sum^\infty_{n = 0} C_n X^n

are analytic so soft analytic too but we can calculate
directly what the corresponding soft species is. We can
view such a polynomial functor as a left Kan extension

\bfig
\Vtriangle/>`>`>/<350,450>[{\mathbb N}`{\bf Set}`{\bf Set};
K`C_{(\ )}`\sum C_n X^n]

\morphism(300,300)/=>/<150,0>[`;]

\efig

where $ {\mathbb N} $ is the discrete category whose
objects are natural numbers, and $ K $ takes the number
$ n $ and sends it to the set of cardinality $ n $

K (n) = \{1, 2, \dots, n\} .

The corresponding soft species $ G $ is given by

G (n) = \sum_{m \to/->>/ n} C_m \rlap{ ,}

one summand for each surjection $ m \to/->>/ n $.

(1) For a soft species $ G $, the corresponding
soft analytic functor $ \widetilde{G} $ is taut.

(2) For a morphism of soft species $ t \colon G \to H $,
i.e. a natural transformation, the corresponding
$ \tilde{t} \colon \widetilde{G} \to \widetilde{H} $ is taut.

(3) $ \tilde{(\ )} $ defines a functor $ {\bf SoftSp} \to
{\bf Taut} $, from the category of soft species $ {\bf Set}^{\bf Surj} $
to the category of taut endofunctors of $ {\bf Set} $ and taut
natural transformations.

(1) Let

\bfig
\square/ >->`>`>` >->/[X_0`X`Y_0`Y;

\place(250,250)[\framebox{\scriptsize Pb}]

\efig

be an inverse image diagram. We want to show that

\bfig
\square/ >->`>`>` >->/[\widetilde{G}(X_0)`\widetilde{G}(X)

\efig

is a pullback. Take $ [a \in G(a), n \to/ >->/^f X] $ in
$ \widetilde{G}(X) $.

\begin{align*}
\widetilde{G}(\phi) [a, n, f] & = [a \in G(n), n \to/ >->/ X \to^f Y]\\
& = [G(e)(a) \in G(m), m \to/ >->/^g Y]
\end{align*}

where $ n \to/->>/^e m \to/ >->/^g Y $ is the image
factorization of $ \phi f $. Suppose there is
$ [b \in G(p), p \to/ >->/^h Y_0] $ in $ \widetilde{G}(Y_0) $
such that

[b \in G(p), p \to/ >->/^h Y_0 \to/ >->/ Y] =
[G(e)(a) \in G(m), m \to/ >->/^g Y] .

Then by <ref> (2), there exists a bijection
$ \sigma \colon m \to p $ such that

\bfig
\node a(0,0)[b]
\node b(150,0)[\in]
\node c(350,0)[G(p)]
\node d(700,0)[p]
\node e(1000,0)[Y_0]
\node f(1300,0)[Y]
\node g(0,400)[G(e)(a)\quad]
\node h(150,400)[\in]
\node i(350,400)[G(m)]
\node j(700,400)[m]
\node k(1300,400)[Y]

\arrow/|->/[g`a;]
\arrow|r|/>/[i`c;G(\sigma)]
\arrow|l|/>/[j`d;\sigma]
\arrow/=/[k`f;]
\arrow|b|/ >->/[d`e;h]
\arrow|b|/ >->/[e`f;j]
\arrow|a|/ >->/[j`k;g]

\efig

i.e. $ b = G(\sigma) G(e)(a) $. Consider the diagram

\bfig
\node a(300,0)[Y_0]
\node b(800,0)[Y\rlap{ .}]
\node c(0,250)[p]
\node d(300,500)[X_0]
\node e(800,500)[X]
\node f(0,500)[m]
\node g(0,800)[n]

\arrow|a|/{@{ >->}@/^1.2em/}/[g`e;f]
\arrow|r|/-->/[g`d;k]
\arrow|a|/ >->/[d`e;i]
\arrow|b|/ >->/[c`a;h]
\arrow|b|/ >->/[a`b;j]
\arrow|l|/->>/[g`f;e]
\arrow|l|/>/[f`c;\sigma]
\arrow|l|/>/[d`a;\phi_0]
\arrow|r|/>/[e`b;\phi]

\place(550,250)[\framebox{\scriptsize Pb}]

\efig

$ j h \sigma e = g e = \phi f $ so there exists  $ k $
as above, and $ [n, a, f] $ is in $ \widetilde{G}(X_0) $.
So $ \widetilde{G} $ is taut.

(2) Let $ t \colon G \to H $ be a natural transformation.
Then $ \tilde{t} \colon \widetilde{G} \to \widetilde{H} $
is defined as follows

\tilde{t} (X) \colon \widetilde{G} (X) \to \widetilde{H} (X)

[a \in G(n), n \to/ >->/ X] \longmapsto [t(n)(a) \in
H(n), n \to/ >->/ X] .

We have several things to prove:

(i) Well-defined: If $ [a \in G(n), n \to/ >->/ X] =
[a' \in G(n'), n' \to/ >->/ X] $ then there is a bijection
$ \sigma \colon n \to n' $ such that

\bfig
\node a(0,0)[a']
\node b(150,0)[\in]
\node c(350,0)[G(n')]
\node d(700,0)[n']
\node e(1200,0)[X]
\node f(0,400)[a]
\node g(150,400)[\in]
\node h(350,400)[G(n)]
\node i(700,400)[n]
\node j(1200,400)[X]

\arrow/|->/[f`a;]
\arrow|r|/>/[h`c;G(\sigma)]
\arrow|r|/>/[i`d;\sigma]
\arrow|r|/=/[j`e;]
\arrow|b|/ >->/[d`e;]
\arrow|a|/ >->/[i`j;]

\place(560,400)[,]
\place(560,0)[,]

\efig

i.e. $ a' = G(\sigma)a $. So $ H(\sigma) t(n)(a) =
t(n')G(\sigma)a = t(n')a' $.

(ii) Natural:

\bfig
\square<600,500>[\widetilde{G}(X)`\widetilde{H}(X)`\widetilde{G}(Y)`\widetilde{H}(Y);
\tilde{t}(x)`\widetilde{G}(\phi)`\widetilde{H}(\phi)`\tilde{t}(Y)]

\place(300,250)[?]

\morphism(1000,500)|r|/>/<0,-500>[X`Y;\phi]

\efig

Choose an element $ [a \in G(n), \alpha \colon n \to/ >->/ X] $ of
$ \widetilde{G}(X) $ and chase it around the diagram

\bfig
\square/|->`|->`|->`|->/<800,500>[{[}a, \alpha{]}`{[}t(n) (a), \alpha{]}
`{[}a, \phi \alpha{]}`{[}t(n)(a), \phi \alpha{]}\rlap{ .};```]

\efig

$ \tilde{t} $ is indeed natural.

(iii) Taut: Let

\bfig
\square/ >->`>`>` >->/[X_0`X`Y_0`Y;`\phi_0`\phi`]

\place(250,250)[\framebox{\scriptsize Pb}]

\efig

be an inverse image diagram and consider

\begin{equation}\tag{*}
\bfig
\square/ >->`>`>` >->/[\widetilde{G} X_0`\widetilde{G} X
`\widetilde{G} Y_0`\widetilde{G} Y\rlap{ .};
`\widetilde{G} (\phi_0)`\widetilde{G} \phi`]

\efig
\end{equation}

If $ \widetilde{G} (\phi) [a \in G(n), n \to/ >->/ X] \in
\widetilde{G} Y_0 $, then it is $ [G(e)(a) \in G(m),
m \to/ >->/^g Y] $
where $ n \to^e m \to/ >->/^g Y $ is the image
factorization of $ \phi f $. By <ref> (4),
$ \widetilde{G} (\phi) [a, n] $ is in $ \widetilde{G} Y_0 $
iff $ g \colon m \to/ >->/ Y $ factors through $ Y_0 $

\bfig
\Vtriangle/ >->` >->`<-< /<300,400>[m`Y`Y_0\rlap{ .};g`g_0`]

\efig

In the diagram

\bfig
\node a(300,0)[Y_0]
\node b(800,0)[Y\rlap{ .}]
\node d(300,500)[X_0]
\node e(800,500)[X]
\node f(0,400)[m]
\node g(0,900)[n]

\arrow|l|/ >->/[f`a;g_0]
\arrow|r|/-->/[g`d;f_0]
\arrow|a|/>/[g`f;e]
\arrow/ >->/[d`e;]
\arrow/ >->/[a`b;]
\arrow|l|/>/[d`a;\phi_0]
\arrow|r|/>/[e`b;\phi]
\arrow|a|/>/[g`e;f]

\place(550,250)[\framebox{\scriptsize Pb}]

\efig

the outside commutes, so there exists
$ f_0 \colon n \to X_0 $, as above, i.e. $ f $
factors through $ X_0 $, and so
$ [a \in G(n), m \to/ >->/ X] \in \widetilde{G} (X_0) $.
Therefore $ (*) $ is a pullback, and $ \tilde{t} $ is

(3) $ \widetilde{(\  )} $ is automatically functorial
$ {\bf Set}^{\bf Surj} \to {\bf Set}^{\bf Set} $ because
it is Kan extension. The only question is whether
it takes its values in $ {\bf Taut} $, and that's what
was proved in (1) and (2).

We are now ready for our main theorem which
might be dubbed “The Fundamental Theorem of
Functorial Difference Calculus”. Part I says
“Summing a soft species and then taking differences
gives the original soft species” and Part II says
“Taking differences of a taut functor and then summing
produces a best approximation by a soft analytic

I. For a soft species $ G \colon {\bf Surj} \to {\bf Set} $
we have a natural isomorphism

G \to^\cong \Delta^* [\widetilde{G}]  .

II.  $ \widetilde{(\  )}  \colon {\bf SoftSp} \to {\bf Taut} $ is
left adjoint to $ \Delta^* \colon {\bf Taut} \to {\bf SoftSp} $.

I. Using Proposition <ref> (1) and
Corollary <ref>, we see that an element
of $ \Delta^n [\widetilde{G}] (0) $ is an equivalence

[a \in G(k), k \to/ >->/ n]_k

which is not equal to any

[b \in G(k_0), k_0 \to/ >->/ n_0 \to/ >>->/ n]_{k_0}

for a proper mono $ n_0 \to/ >>->/ n $. If $ k \to/ >->/ n $
were a proper mono, we would have

\bfig
\node a(0,0)[a]
\node b(150,0)[\in]
\node c(350,0)[G(k)]
\node d(700,0)[k]
\node e(820,0)[=]
\node f(1200,0)[k \to/ >>->/ n\rlap{ ,}\quad\quad]
\node g(0,400)[a]
\node h(150,400)[\in]
\node i(350,400)[G(k)]
\node j(700,400)[k]
\node k(1200,400)[n]
\arrow/|->/[g`a;]
\arrow|r|/>/[i`c;]
\arrow|r|/=/[d`j;]
\arrow/=/[f`k;]
\arrow/ >->/[j`k;]

\efig

so $ [a \in G(n), k \to/ >->/ n] $ would not be in
$ \Delta^n [\widetilde{G}] (0) $. It follows that the
elements of $ \Delta^n [\widetilde{G}] (0) $ are of
the form

[a \in G(n), \sigma \colon n \to n]

for $ \sigma $ a bijection. Each such class has a
canonical representative with $ \sigma = \id $,
and for these the equivalence relation is
equality, i.e. $ \Delta^n [\widetilde{G}] (0) $ is
in bijection with $ G(n) $ itself.

The natural transformation which gives this
bijection is

\begin{array}{rcl}
\eta (n) \colon G(n)  & \to/>/<250> & \Delta^n [\widetilde{G}](0)\\
a   & \to/|->/<250>  & [a \in G(n), \id \colon n \to n] \rlap{ .}
\end{array}

II. Let $ G \colon {\bf Surj} \to {\bf Set} $ be a
soft species and $ F \colon {\bf Set} \to {\bf Set} $
be a taut functor. As $ \widetilde{G} $ is the left
Kan extension of $ G $ along the inclusion
$ J \colon {\bf Surj} \to {\bf Set} $, we already have
a natural bijection of natural transformations

\widetilde{G} \to^t F \over G \to_u FJ \rlap{ .}

Note that $ \Delta^* [F] $ is a subfunctor of $ FJ $.
We will show that in the above bijection $ t $ is
taut if and only if $ u $ factors through
$ \Delta^* (F) \to/ >->/ FJ $.

First assume $ t $ is taut. By Kan extension theory,
the $ u $ corresponding to $ t $ is given by

u (n) \colon G(n) \to F(n)

u (n) (a) = t (n) [a \in G(n), \id \colon n \to/ >->/ n] \rlap{ .}

We want to show that $ u (n) (a) $ is in fact an
element of $ \Delta^n [F] (0) $, i.e. $ u (n) (a) $ is not
in any $ F (n_0) \to/ >->/ F (n) $ for a proper mono
$ f \colon n_0 \to/ >>->/ n $. Suppose it were, so that
we would have $ x \in F (n_0) $ such that
$ F(f) (x) = u (n) (a) $. As $ t $ is taut, we have the

\bfig
\square/ >->`>`>` >->/<600,500>[\widetilde{G}(n_0)`\widetilde{G}(n)
\widetilde{G}(f)`t(n_0)`t(n)`F(f)]

\place(300,250)[\framebox{\scriptsize Pb}]

\efig

and so there is an element $ [b \in G(m),
m \to/ >->/ n_0] $ in $ \widetilde{G}(n_0) $
such that $ t(n_0) $ of which is $ x $
and $ \widetilde{G}(f) [b \in G(m), m \to/ >->/ n_0] =
[a \in G(n), \id \colon n \to/ >->/ n] $. This last
equation means that there is a bijection
$ \sigma \colon n \to m $ with

\bfig
\node a(0,0)[b]
\node b(150,0)[\in]
\node c(350,0)[G(m)]
\node d(0,450)[a]
\node e(150,450)[\in]
\node f(350,450)[G(n)]

\arrow/|->/[d`a;]
\arrow|r|/>/[f`c;G(\sigma)]

\square(700,0)|arlb|/>`>`=`/<800,450>[n`n`m`n;\id`\sigma``]
\morphism(700,0)/ >->/<400,0>[m`n_0;]
\morphism(1100,0)/ >->/<400,0>[n_0`n;]

\efig

which implies that $ n_0 \to/ >->/ n $ is an iso,
i.e. is not proper. This contradicts our choice of $ n_0 $,
so $ u (n) (a) $ is indeed an element of
$ \Delta^n [F](0) $, and $ u $ factors through
$ \Delta^* [F] \to/ >->/ F J $.

Now, let $ u \colon G \to F J $ factor through
$ \Delta^* [F] $. The corresponding $ t \colon
\widetilde{G} \to F $ is given by

t (X) \colon \widetilde{G} (X) \to F (X)

[a \in G(n), n \to/ >->/^f X] \longmapsto
F (f) u (n) (a)

and we want to show that it's taut. To this end,
let $ \phi \colon Y \to/ >->/ X $ be a monomorphism.
We will show that

\bfig
\square/ >->`>`>` >->/<550,500>[\widetilde{G} (Y)`\widetilde{G}(X)`FY`FX;

\efig

is a pullback. Take $ [b \in G(n), g \colon n \to/ >->/ X] $
in $ \widetilde{G} (X) $ such that there is $ y \in FY $ with

\begin{align*}
F(\phi)(y) & = t (X) [n, b, g]\nonumber\\
& = F(g) u (n)(a)\rlap{ .} \tag{*}
\end{align*}

We want to show that $ g $ factors through $ \phi $. Take
the pullback

\bfig
\square/ >->` >->` >->` >->/[m`n`Y`X;\psi`f`g`\phi]

\place(250,250)[\framebox{\scriptsize Pb}]

\efig

and, as $ F $ is taut, we get another pullback

\bfig
\square/ >->` >->` >->` >->/[F(m)`F(n)`F(Y)`F(X)\rlap{ .};

\place(250,250)[\framebox{\scriptsize Pb}]

\efig

Because of $ (*) $, there is $ x \in F(m) $ such that
$ F(f) (x) = y $ and $ F(\psi) (x) = u (n) (a) $. Since
$ u (n) (a) $ is in $ \Delta^n [F] (0) $, $ \psi $ cannot
be proper so that $ g $ will factor through $ \phi $ and
$ [b \in G(n), s \colon n \to/ >->/ X] $ is in
$ \widetilde{G} (Y) $.

If $ F \colon {\bf Set} \to {\bf Set} $ is soft analytic, e.g. power
series or analytic, then its Newton series converges to it

F(X) \cong \int^{n \, \in\, {\rm Surj}} X^n \times \Delta^n [F](0)\rlap{ .}

Note that what we are calling power series are
functors of the form

F(X) = \sum^\infty_{n\,=\, 0} C_n X^n

and only involve finite powers of $ X $. For
polynomial functors as in Definition <ref>
involving arbitrary powers of $ X $, the corollary
doesn't hold. We merely get a comparison. For
example, for an infinite set $ A $, the Newton series
of $ F (X) = X^A $ converges to the functor

G(X) =\{ f \colon A \to X\  | \mbox{\  the image of $ f $ is finite}\}.