as Del Zanna & Bucciantini (2002) used the more accurate CENO3-scheme, while
our result is based on the 2nd order in space LF method. However, this
drawback can be overcome by using a finer mesh (not shown).

####  C.3.2 Uncertainty for simulations of turbulent and cooling flows

The exactness of the simulation presented in this paper is harder to estimate.
The flows are turbulent and cooling introduces more instabilities, waves, and
interfaces. The turbulent region of the cocoon has no fixed boundary but is
embedded by shocks and material interfaces into the environment. Interior
turbulent fluctuations will impact the shape of the interfaces and, inversely,
the dynamics of the interfaces will act on the interior turbulence. From these
arguments, one cannot expect to find a converged solution in the sense
demonstrated in Fig. 19. One has to trust the general correctness of the
scheme and has to give some reasons why the presented solutions are close to
correct. A rigorous error analysis based on statistical analysis of many
simulations that differ slightly in their initial conditions would be
desirable, but is sophisticated, complex, and computationally expensive – and
thus out of reach for the present study. A step in this direction is,
nevertheless, presented in Fig. 21. We list in the following some points that
allow the shed some light on the uncertainties.

Figure 21: Simulation of the fiducial case of CygX1 on a mesh 2 times finer
than the simulation presented in Fig. 3. Shown is the simulation at $6000$ s,
corresponding to the middle panel of Fig. 3.

##### 1\. Turbulence:

Reynolds numbers are too high to resolve the turbulent cascade with any
numerical scheme. Moreover, ideal hydrodynamics does not treat diffusion
explicitly. But a numerical scheme implicitly introduces a certain diffusion
(Hirsch 2006; LeVeque et al. 2002), which is in astrophysical rarefied flows
much larger than the physical diffusion. However, as pointed out by Boris et
al. (1992) and further explored by Porter et al. (1992) and Porter & Woodward
(1994), finite volume methods as the one used here cut the turbulent cascade
in a way not leading to an energy pile-up or -sink at the numerical diffusion
scale, thus cutting the cascade correctly, at least to first order. Such an
approach is termed MILES (monotone integrated large-eddy simulation). A more
rigorous study to the MILES approach is given e.g. in Garnier et al. (1999)
and summary of the idea and more references can be found in Folini & Walder
(2006). These studies show that turbulent flows are relatively well captured
by finite volume methods, without introducing large errors.

##### 2\. Cooling:

Radiative shocks are prone to an overstability, whenever the slope of the
cooling law is sufficiently shallow or negative. For a radiative cooling
parametrized as a function of density and temperature
$\dot{\tau}(\rho,T)=\rho^{2}\Lambda(T)$ with
$\Lambda(T)=\Lambda_{0}T^{\beta}$, which applies for free-free and line
cooling, Chevalier & Imamura (1982) and Bertschinger (1986) have shown that
the overstability is present whenever $\beta\;\hbox to0.0pt{\lower
2.5pt\hbox{$\sim$}\hss}\raise 1.5pt\hbox{$<$}\;0.4$ (fundamental mode), and,
respectively, $\beta\;\hbox to0.0pt{\lower 2.5pt\hbox{$\sim$}\hss}\raise
1.5pt\hbox{$<$}\;0.8$ (first overtone mode). We have shown (Walder & Folini
1996) that presence and amplitude of the overstable modes in a numerical study
critically depend on the numerical resolution as smeared out interfaces
radiate more than better resolved ones. The resolution we chose for the
simulations are sufficient to resolve the overstability (not shown). It is,
however, worth to add two remarks. Firstly, the used numerical model does not
include mass- and, particularly, heat-diffusion which physically determines
the smearing of the interface. It is thus not clear whether we under- or over-
estimate this particular effect. Secondly, radiative multi-dimensional shocks
can generate and drive turbulence (Walder & Folini 1998) and turbulent thin-
shells (Folini & Walder 2006; Folini et al. 2014).

##### 3\. Resolution comparison:

The fiducial case of CygX1 has been simulated on a mesh 2 times finer than the
generic mesh up to about 10’000 s. The snapshot at 6000 s is shown in Fig. 21.
This can be compared to the snapshot of the generic case shown in the middle
panel of Fig. 3. The comparison shows that the instability sets in at about
the same time in both of the simulations. However, in the simulation on the
finer mesh, the jets propagates about 10 percent faster than in the simulation
on the generic mesh. We also observe similar effects, of the same order, in 1D
test simulations. This is expected on the basis of the arguments given in the
point above. Better resolving the contact interface at the head of the jet
will reduce cooling there, leaving slightly more energy to push the bow shock
to a larger distance. Note that an error of 10 percent is for most large-scale
fluid-dynamical simulations already a quite good result. We stress again that
the correct jet speed depends on on the physical diffusion.

To even improve the confidence in the solutions presented in this paper, we
have run a 2D resolution study, using the generic and the finer mesh in the 3D
case. This study covers also the turbulent phase. Again we find that the
essential features of the jet (number and location of the cross shocks, cocoon
shape, time when the instability and the turbulence sets in) are independent
of the resolution. Note, however, that the 2D simulations cannot directly be
compared to the 3D simulations as the character of the turbulence is different
in 2D and 3D.

###  C.4 The necessity of relativistic simulations

Given that the computational costs are considerably higher for a relativistic
simulation, one may ask whether it is necessary to perform relativistic
simulations to obtain correct solutions for the mildly relativistic problems
presented in this paper, with $\gamma_{b}\approx 1.06$ for CygX1 and
$\gamma_{b}\approx 1.51$ for CygX3. However, even these small Lorentz factors
lead to a significant difference in the jet propagation between a relativistic
and a Newtonian simulation. This is illustrated in Fig. 22 which shows 1D
simulations at (observer) time $t=6500$ s of the jet propagation of CygX3,
including all cooling terms. The jet head is located in the thin high-density
shell. In the Newtonian case this shell is located, in the observers frame, at
about $x=45\cdot 10^{12}$ cm. The shell in the relativistic case is located at
$x=71\cdot 10^{12}$ cm. Both simulations used 12800 cells. Thus, the
relativistic jet head propagates about 1/3 faster than the Newtonian one. This
can be explained on the basis of Eq. 5: the ratio between $\eta^{*}$ and
$\eta$ for CygX3 (see Table 8) is about $2.3$, resulting in a difference in
the jet-propagation speed of about 45%. There is less difference for CygX1,
but still about 5%. Note that in 1D the shocked beam will cool down, in
contrast to the multi-D simulations where the beam is regularly re-heated by
the cross-shocks.

Figure 22: Comparison in density profiles of 1D simulations for parameters
similar to the fiducial cases. Shown is, in the observer frame, the comparison
between a Newtonian and a relativistic simulation for CygX1 at 30’000 s (blue)
and for CygX3 for 6500 s (red). The simulations include all cooling terms. The
pattern with forward and reverse shock and a thin layer of cooled gas to the
left of the contact interface between beam and environment material is similar
for all simulations. The mesh consists of 12800 cells, about as much as the
mesh covering the beam in the 3D simulations presented in the paper.

###  C.5 Numerical approximation of Bessel K functions

Eqn. 16 and therefore Eqns. 20 and 23 use the modified Bessel function of the
second kind (also called Bessel K function or Macdonald function), especially
the ratio $K_{3}/K_{2}$. A Fortran 90 implementation of this function by
Moreau (2005) was ported to A-MaZe, but as both functions tends to zero at low
temperature, a simple division of $K_{3}(\Theta^{-1})$ by $K_{2}(\Theta^{-1})$
caused underflows during calculations, pushing us to modify the method to
derive the ratio directly. Fig. 23 compares our Fortran method with the built-
in Bessel K functions from the SciPy package and shows the stability of our
method over the whole temperature range compared to a simple division.

Figure 23: Comparison of our Fortran method for the ratio $K_{3}/K_{2}$ with
the simple division of both terms using the functions defined in Python
package SciPy. Our Fortran method avoids underflows for large values of
$\Theta^{-1}$ with a relative error never exceeding $10^{-8}$

##  Appendix D Simulations setups

Tables 5 and 7 show the input parameters for each run in CGS units, while
Tables 6 and 8 show the same inputs in terms of the adimensional parameters
introduced Sect. 3.1.

| Jet parameters | Star parameters
---|---|---
setup name | $L_{j}\text{ (erg s}^{-1})$ | $\rho_{j}\text{ (g cm}^{-3})$ | $v_{j}\text{ (cm s}^{-1})$ | $r_{0}\text{ (cm)}$ | $T_{j}\text{ (K)}$ | $B_{j}\text{ (G)}$ | $\dot{M}^{\star}$ | $v_{\infty}\text{ (km s}^{-1})$ | $T^{\star}\text{ (K)}$ | $B^{\star}\text{ (G)}$
CygX1 | $5.1\cdot 10^{36}$ | $1.3\cdot 10^{-15}$ | $1\cdot 10^{10}$ | $5\cdot 10^{10}$ | $10^{8}$ | $10.$ | $3\cdot 10^{-6}$ | $1000$ | $3\cdot 10^{4}$ | $10.$
CygX1_noLoss | $5.1\cdot 10^{36}$ | $1.3\cdot 10^{-15}$ | $1\cdot 10^{10}$ | $5\cdot 10^{10}$ | $10^{8}$ | $0.$ | $3\cdot 10^{-6}$ | $1000$ | $3\cdot 10^{4}$ | $0.$
CygX1_wind | $5.1\cdot 10^{36}$ | $1.3\cdot 10^{-15}$ | $1\cdot 10^{10}$ | $5\cdot 10^{10}$ | $10^{8}$ | $10.$ | $3\cdot 10^{-6}$ | $1500$ | $3\cdot 10^{4}$ | $10.$
CygX1_mP | $5.1\cdot 10^{35}$ | $1.3\cdot 10^{-16}$ | $1\cdot 10^{10}$ | $5\cdot 10^{10}$ | $10^{8}$ | $10.$ | $3\cdot 10^{-6}$ | $1000$ | $3\cdot 10^{4}$ | $10.$
CygX1_T7 | $5.1\cdot 10^{36}$ | $1.3\cdot 10^{-15}$ | $1\cdot 10^{10}$ | $5\cdot 10^{10}$ | $10^{7}$ | $10.$ | $3\cdot 10^{-6}$ | $1000$ | $3\cdot 10^{4}$ | $10.$
CygX1_T9 | $5.1\cdot 10^{36}$ | $1.3\cdot 10^{-15}$ | $1\cdot 10^{10}$ | $5\cdot 10^{10}$ | $10^{9}$ | $10.$ | $3\cdot 10^{-6}$ | $1000$ | $3\cdot 10^{4}$ | $10.$
Table 5: Simulation parameters of runs based on Cygnus X-1. Massloss rate $\dot{M}^{\star}$ is in units $M_{\odot}$ yr-1 setup name | $\beta_{j}$ | $M_{j}$ | $\mathcal{M}_{j}$ | $\eta$ | $\eta^{*}$ | $K$
---|---|---|---|---|---|---
CygX1 | $0.334$ | $67$ | $71$ | $0.077$ | $0.087$ | $258$
CygX1_noLoss | $0.334$ | $67$ | $71$ | $0.077$ | $0.087$ | $258$
CygX1_wind | $0.334$ | $67$ | $71$ | $0.116$ | $0.130$ | $387$
CygX1_mP | $0.334$ | $67$ | $71$ | $0.008$ | $0.009$ | $26$
CygX1_T7 | $0.334$ | $211$ | $224$ | $0.077$ | $0.087$ | $26$
CygX1_T9 | $0.334$ | $21$ | $22$ | $0.077$ | $0.087$ | $2577$
Table 6: Dimensionless parameters of Cygnus X-1 runs. | Jet parameters | Star parameters
---|---|---
setup name | $L_{j}\text{ (erg s}^{-1})$ | $\rho_{j}\text{ (g cm}^{-3})$ | $v_{j}\text{ (cm s}^{-1})$ | $r_{0}\text{ (cm)}$ | $T_{j}\text{ (K)}$ | $B_{j}\text{ (G)}$ | $\dot{M}^{\star}$ | $v_{\infty}\text{ (km s}^{-1})$ | $T^{\star}\text{ (K)}$ | $B^{\star}\text{ (G)}$
CygX3 | $10^{38}$ | $1.4\cdot 10^{-14}$ | $2.25\cdot 10^{10}$ | $2\cdot 10^{10}$ | $10^{8}$ | $10$ | $10^{-5}$ | $1500$ | $8\cdot 10^{4}$ | $100$
CygX3_noLoss | $10^{38}$ | $1.4\cdot 10^{-14}$ | $2.25\cdot 10^{10}$ | $2\cdot 10^{10}$ | $10^{8}$ | $10$ | $10^{-5}$ | $1500$ | $8\cdot 10^{4}$ | $100$
CygX3_mW | $10^{38}$ | $1.4\cdot 10^{-14}$ | $2.25\cdot 10^{10}$ | $2\cdot 10^{10}$ | $10^{8}$ | $10$ | $7.5\cdot 10^{-6}$ | $1000$ | $8\cdot 10^{4}$ | $100$
CygX3_mP | $5.0\cdot 10^{37}$ | $7\cdot 10^{-15}$ | $2.25\cdot 10^{10}$ | $2\cdot 10^{10}$ | $10^{8}$ | $10$ | $10^{-5}$ | $1500$ | $8\cdot 10^{4}$ | $100$
CygX3_mPmW | $5.0\cdot 10^{37}$ | $7\cdot 10^{-15}$ | $2.25\cdot 10^{10}$ | $2\cdot 10^{10}$ | $10^{8}$ | $10$ | $7.5\cdot 10^{-6}$ | $1000$ | $8\cdot 10^{4}$ | $100$
CygX3_mPmmW | $5.0\cdot 10^{37}$ | $7\cdot 10^{-15}$ | $2.25\cdot 10^{10}$ | $2\cdot 10^{10}$ | $10^{8}$ | $10$ | $7.5\cdot 10^{-6}$ | $750$ | $8\cdot 10^{4}$ | $100$
Table 7: Simulation parameters of runs based on Cygnus X-3. Massloss rate $\dot{M}^{\star}$ is in units $M_{\odot}$ yr-1 setup name | $\beta_{j}$ | $M_{j}$ | $\mathcal{M}_{j}$ | $\eta$ | $\eta^{*}$ | $K$
---|---|---|---|---|---|---
CygX3 | $0.75$ | $150$ | $228$ | $0.0028$ | $0.0065$ | $3.5$
CygX3_noLoss | $0.75$ | $150$ | $228$ | $0.0028$ | $0.0065$ | $3.5$
CygX3_mW | $0.75$ | $150$ | $228$ | $0.0025$ | $0.0058$ | $3.1$
CygX3_mP | $0.75$ | $150$ | $228$ | $0.0014$ | $0.0032$ | $1.8$
CygX3_mPmW | $0.75$ | $150$ | $228$ | $0.0013$ | $0.0029$ | $1.6$
CygX3_mPmmW | $0.75$ | $150$ | $228$ | $0.0009$ | $0.0022$ | $1.2$
Table 8: Dimensionless parameters of Cygnus X-3 runs,

##  Appendix E Instability growth phase

Figs. 24 and 25 show pressure slices of runs CygX1 and CygX3 runs
respectively, highlighting the internal structure of the beam with alternating
over- and under-pressured regions compared to the fluid in the surrounding
cocoon.

Figure 24: Pressure slices during instability growth phase of fiducial Cygnus
X-1 run CygX1. Color scale is fixed from 1 (blue) to 1000 Ba (red) to better
highlight the beam structure. The beam shows an alternance of over- and
underpressured zones whose number has risen at the 5000 s mark. The inner
cocoon shows ripple-like structures alternating on both sides of the beam with
increasing intensity as the jet evolves. Figure 25: Pressure slices during
instability growth phase of fiducial Cygnus X-3 run CygX3. Color scale is
fixed from $10^{3}$ (blue) to $10^{5}$ Ba (red) to better highlight the beam
structure.


# Interconnecting Fog Robots with Secure Global Addressability

Kaiyuan Chen1, Jiachen Yuan1, Nikhil Jha1, Jeffrey Ichnowski1,
John Kubiatowicz1, and Ken Goldberg1,2 1Department of Electrical Engineering
and Computer Science2Department of Industrial Engineering and Operations
Research1,2University of California, Berkeley, CA, USA {kych, jcyuan_johnson,
nikhiljha, jeffi, kubitron<EMAIL_ADDRESS>
# FogROS G: Enabling Secure, Connected and Mobile Fog Robotics with Global
Addressability

Kaiyuan Chen1, Jiachen Yuan1, Nikhil Jha1, Jeffrey Ichnowski1,
John Kubiatowicz1, and Ken Goldberg1,2 1Department of Electrical Engineering
and Computer Science2Department of Industrial Engineering and Operations
Research1,2University of California, Berkeley, CA, USA {kych, jcyuan_johnson,
nikhiljha, jeffi, kubitron<EMAIL_ADDRESS>
###### Abstract

Fog Robotics renders networked robots with greater mobility, on-demand compute
capabilities and better energy efficiency by offloading heavy robotics
workloads to nearby Edge and distant Cloud data centers. However, as the de-
facto standard for implementing fog robotics applications, Robot Operating
System (ROS) and its successor ROS2 fail to provide fog robots with a mobile-
friendly and secure communication infrastructure.

In this work, we present FogROS G, a secure routing framework that connects
robotics software components from different physical locations, networks, Data
Distribution Service (DDS) and ROS distributions. FogROS G indexes networked
robots with globally unique 256-bit names that remains constant even if the
robot roams between multiple administrative network domains. FogROS G
leverages Global Data Plane, a global and secure peer-to-peer routing
infrastructure between the names, guaranteeing that only authenticated party
can send to or receive from the robot. FogROS G adopts a proxy-based design
that connect nodes from ROS1 and ROS2 with mainstream DDS vendors; this can be
done without any changes to the application code. The code is publicly
available at https://github.com/KeplerC/gdp-for-ros.

##  I Introduction

As robot onboard resources fail to keep up with heavier robotics computations,
leveraging external computational resources on demand becomes more desirable.
Fog robotics [1, 2] has been proposed for the continuum of Cloud Computing
that offers immense on-demand computational resources and Edge Computing that
exploits the resources close to the robot with lower access latency [3, 4]. In
this paper, we propose FogROS G, a framework that enables secure and location-
independent routing for Robot Operating System (ROS)111For the rest of the
paper, we use ROS for both ROS1 and ROS2.. It allows networked robots to roam
freely with no requirement of a static network address (i.e. IP), network
administrative domain or physical location. With minimal effort, robotic
application developers can publish their compute services globally and only
authenticated robots can use the services; they can also establish secure
communication channel with robots even if the robots do not have a publicly
accessible network address.

Figure 1: FogROS G connects fog robotics drone with cloud compute resources.
When the drone flies from an enterprise network to a university network,
FogROS G persists its ROS connection over topic /images and /commands, despite
(1) its IP address has changed and (2) both IP addresses are behind firewall
and not publicly accessible (2) the nodes on the cloud are implemented in ROS1
but drone uses ROS2. This is accomplished by assigning every ROS topic a
globally-unique and location-independent name([75e...0fc] and [af0...889]) and
by securely routing the messages through GDP infrastructure.

ROS is the de-facto standard for implementing fog robotics applications. It
modularizes the robotics application into nodes, and connects the nodes into a
graph. Nodes communicate with each other through a publish-subscribe (pub/sub)
system that node publishes messages with respect to topics, and subscribes to
the topics published by other nodes.

Although it presents a convenient interface to robotics application
developers, the current ROS 2 implementation cannot meet the following
requirements of the fog robotics applications:

#### Edge-Cloud Continuum

ROS computational graph may span across multiple network administrative
domains with the recent advances of the edge computing and multi-cloud
computing [5, 6, 7, 8]. For example, in FogROS 2[9], a ROS node on the robot
can connect to both Google Cloud Platform (GCP) and Amazon Web Services (AWS).
However, some of the IP addresses are visible only within the same network
domain, and external accesses are blocked by firewall. ROS is unable to
discover the nodes out of the domain and those without a publicly accessible
address.

#### Mobility

ROS uses static IP address to discover and peer with ROS nodes on other
machines. However, because an IP address is usually bound to a physical
location. The mobile robots, such as Unmanned Aerial Vehicle, cannot have a
static IP address. Existing approaches such as mobile IP, are known to have
security and reliability issues [10].

#### Security

ROS is notorious for the lack of the security mechanisms [11, 12]. For
example, due to the lack of authentication scheme in the ROS implementation,
anyone can join an existing ROS network, publish to and subscribe from the
robots. Attackers can freely listen to the existing communication and remotely
control the robot [13] .

#### Compatibility

ROS2 fails in both backward-compatibility with ROS1 and unification with
different DDS vendors [14, 15]. While most of the existing research prototypes
are implemented with ROS1, ROS2 nodes cannot directly communicate with running
ROS1 nodes. In addition, network configuration with ROS2 is DDS vendor-
specific: different vendors use different configuration languages and offer
different features. Most of the existing multiple machine implementations with
ROS2 only work with one of the DDS, such as FogROS [16] and Zenoh [17].

Fog Robotics challenges the traditional wisdom to retrains robots behind
firewalls, which hinders the mobility of the robots and limits the ability to
leverage external computational resources. Thus, FogROS G argues a paradigm
shift to make ROS nodes location-independent. Every ROS node is indexed with a
globally visible and unique name, which is independent from the location of
the robot and the network that it connects to. The fog robots can roam freely:
as long as there is a globally connected path in FogROS G, they can stay
connected with their edge or cloud services. We adopt a security-first design
that only the authenticated party can connect to the node and establish a
secure communication with it.

In FogROS G, every ROS topic is indexed with 256-bit name derived from the
meta information (such as the name, author, functionality) of node. The
attacker is unable to guess the name, because there are $2^{256}$ possible
names and modifying one bit of the meta information changes the 256-bit name
entirely (i.e. avalanche effect). The names are mapped to Global Data Plane
(GDP) [18], a federated peer-to-peer network that can securely route the
messages across different network administrative domains. We design a GDP-ROS
proxy that converts between ROS messages and GDP packets, and
cryptographically harden the packets with confidentiality, integrity and
authenticity. The proxy-based designs also allow to connect ROS nodes with
different network middleware vendors and ROS distributions.

In this paper, we implement GDP routing infrastructure in Rust, a memory-safe
and type-safe language. The switches are implemented on kernel-bypass DPDK for
minimal routing overhead. We implement a proxy between GDP and ROS similar to
FogROS [16], but the packets are sent in layer 2 with GDP headers.

FogROS G aims the following design goals:

  1. 1.

Security FogROS G assumes the attackers may tap into any network links between
robots and cloud servers, and they can eavesdrop and tamper the ongoing
communication. FogROS G prevents them from learning any of the plaintext data
(such as topic name, ROS messages), and detect any unauthenticated messages
sent to the ROS nodes.

  2. 2.

Location Independent A node with FogROS G stays connected with its ROS graph
as long as it can connect to one of the other nodes enabled with FogROS G
(even if they do not belong to the same ROS graph). Other ROS nodes are able
to connect to the node with the same interface and 256-bit name.

  3. 3.

User-Friendly FogROS G does not require any modifications to the original ROS
2 application code. Application developers only need to specify the nodes
intended to be global in a separate configuration file. This is helpful for
separating security policy with actual implementation.

  4. 4.

Compatibility FogROS G does not rely on any of the DDS-specific configuration,
and can be ported to both ROS1 and ROS2. It also allows ROS nodes with
different DDS vendors and ROS distributions connected with the same FogROS G
network.

##  II Design

Figure 2: An overview of the proposed FogROS G architecture. (Orange) shows
the procedure of generating and publishing a 256-bit name [75e...0fc] globally
to GDP Routing Information Base (RIB). (Magenta) shows the subscriber can
derive the same name [75e...0fc] with the meta-information of the topic and
send the subscription query. (Black) The GDP infrastructure populates the
switches with associated routing information, and forward the actual encrypted
data.

Figure 2 shows an overview of the proposed architecture. FogROS G has three
main components: (1) an address manager that converts and registers ROS node
metadata to 256 bit globally unique name (2) GDP routing infrastructure (3) a
proxy module that converts between ROS messages and GDP packets.

To make a ROS topic globally visible, the user specifies the meta-information
(such as author, functionality) about the topics. The meta-information is
converted to a 256-bit globally unique name by SHA-256 hash, and publishes the
topic information to GDP Routing information Base (RIB). FogROS G adopts a
proxy-based approach that serializes the ROS messages with vendor-independent
encoding and converts them to GDP packets. The GDP packets are
cryptographically hardened with confidentiality and integrity, and they are
routed to the target FogROS G proxy. After the GDP packets are decrypted and
verified their authenticity. they are converted back to ROS messages and sent
to the destination ROS node.

###  II-A Global Addressable ROS

FogROS G uses ROS topic as the minimal granularity of the global name, because
a robot can run many ROS nodes, and a ROS node can host many ROS topics. ROS
topic exposes a standardized interface with fixed message format. It can be
easily extended to other ROS features, such as services. User can restrict the
exposure of ROS nodes by allowing only part of the interfaces to public.
Partitioning public and private interfaces also enhance the privacy and
isolation of the ROS nodes. If one uses ROS Master in ROS1 or VPN in
FogROS[16], all nodes have to join the same pub/sub network. A node may
accidentally subscribe to a topic with the same name on another machine, which
greatly introduces unwanted message exchanges and additional communication
overhead.

The global name is designed to be unique, static and location independent,
with the goal that anyone can derive and identify the topic even if he or she
does not know the 256-bit name. The name is derived from the metadata of the
ROS topic, such as the ROS node’s name, author, maintainer, interface,
description etc. It can also contain a human-memorable random number [19] to
prevent multiple identical ROS nodes running at the same time. Optionally, one
can include the public portion of the security credential to facilitate the
verification of the name advertisement.

The metadata is serialized and converted into 256-bit string using SHA-256
hash. There are several reasons why hashed string is suitable for using as the
globally unique name: (1) deterministic The hash is deterministic so that
every party holding the same metadata can derive the same hash value and thus
the same global name for the ROS node (2) One-way SHA-256 is a one way
function that the attacker cannot reverse the original meta-data from the 256
bit name and thus does not leak the original metadata. (3) Avalanche effect A
small change to the original metadata leads to new hash value that appear
unrelated to the original hash value (4) Large name space There are $2^{256}$
possible names and it is proved to be computationally infeasible to find two
messages with the same hash.

###  II-B GDP-ROS proxy

The GDP-ROS proxy converts between ROS messages and GDP packets. After user
initializes the proxy with the metadata of the topics, the proxy subscribes to
the events of the topic. For example, if there is a new local publisher ROS
node joins the network, it publishes the topic globally. Using proxy-based
design has several advantages:

#### Vendor-Agnostic

Existing efforts[9] on connecting multiple ROS nodes across multiple machines
require vendor-specific configurations, and every vendor requires different
configuration format [20, 21]. As a result, most of the existing solutions
only work for one DDS (for example, FogROS 2 and Zenoh [17] only support
CycloneDDS [14]). However, FogROS G’s proxy presents an abstraction of a
virtual node that is agnostic to the heterogeneous implementations of the ROS
nodes. Due to the same reason, it works for both ROS1 and ROS2.

#### Efficient and Adaptive

The proxy does not introduce additional overhead if all the ROS nodes are on
the same machine, as they still use the original ROS to manage the graph and
inter-node communication. It does not exposes the topics to public unless
specified by the user.

#### User-Friendly

The proxy presents a virtual node abstraction to other nodes so that other
nodes can communicate with the node in the same way as they communicate with a
local ROS node. As a result, it allows ROS node to be transparent about the
underlying routing infrastructure and users can interact with remote nodes
without modifying the original application code.

###  II-C FogROS G Data Security

Figure 3: An illustration of the fields of GDP packets. ROS messages are
serialized into JSON formatted string. The string is encrypted, hashed and
signed for confidentiality and integrity.

All FogROS G communication is exchanged in GDP packets that guarantee the
confidentiality, integrity and authenticity of the ROS messages. Figure 3
shows how a GDP packet is generated with ROS. The ROS message is serialized
into a string that contains ROS message type, topic and the original message.
The string is encrypted with AES encryption [22] so that only the parties with
the same symmetric key is able to decrypt the the ciphertext to the plaintext.
The encrypted data is hashed with SHA-256 [23] to protect the integrity of the
data, that modifying one bit of the payload changes the resultant hash
entirely. The hash is signed with the private portion of the writer key with
Elliptic Curve Digital Signature Algorithm(ECDSA) [24], so that anyone holding
the public portion of the writer key is able to verify that the content is
produced by the authentic writer. The resultant payload is used as the GDP
payload sent through the GDP routing infrastructure.

###  II-D Location-Independent Routing with GDP

Figure 4: An illustration of the routing architecture of the GDP network with
two Trust Domains (School and Cloud). There is a higher tier RIB that connect
both domains and facilitate the query of the name.

Global Data Plane (GDP) is a peer-to-peer routing infrastructure that enables
secure routing on federated network infrastructure that there is no central
authority for assigning names. GDP assigns all the entities (network hardware,
data, message senders and receivers) with flat and location-independent names.
These names do not involve any physical identifiers (such as IP addresses),
allowing the resources to be placed, moved and replicated to different
locations. The location-independent name also allows the abstraction that one
can directly communicate with services, data instead of an end host.

GDP enables flat and location-independent routing with a routing fabric of
switches and Routing Information Bases (RIB). GDP organizes the routing fabric
as a number of network administrative domains named Trust Domains (TDs) and
restrict the routing only through trusted TDs. TD guarantees every domain can
independently maintain verifiable routing state. GDP use a hierarchical
structure of TDs to ensure the routing scalability and locality.

Figure 4 illustrates a GDP network with two TDs. The robot drone publishes a
GDP name [75e...0fc] to its local RIB, and the routing information is flooded
to higher tier RIB through the border switches B1 and B2. The RIBs verify the
advertisement message by validating the hash generation and the cryptographic
credentials of the name advertiser. After verification, RIB updates the
256-bit name and its corresponding switch to its in-memory key-value store.
The remote subscriber from the cloud TD sends a name query, and the name query
is propagated to its local RIB and the higher tier RIB. The GDP RIB (Tier 1)
responds the query with B1’s routing information, and B3 subscribes to the
topic by peering with B1. Finally ROS messages are published through the
switches along the path with shortest path routing algorithm to the cloud
subscriber.

##  III Preliminary Evaluation

###  III-A Implementation

We implement GDP routing infrastructure with 23,378 Lines of Code in Rust.
Rust is a type-safe language with strong memory and type safety at compile
time. We use Capsule, Comcast’s implementation of NetBricks [25], to implement
the switching and RIB. Capsule wraps around Intel’s Data Plane Development Kit
(DPDK) to bypass the kernel and provide fast userspace packet processing
ability.

We implement the proxy with 2,000 LoC in Python. The proxy interfaces the
corresponding ROS version and serializes the ROS messages to JSON format. The
proxy interfaces the GDP infrastructure by sending raw bytecode packets
through sendp through layer 2 (versus regular layer 3 send used by DDS).
Because Layer 2 packets are required to have fixed length of payload
(typically 1500 bytes), the proxy also implements packet re-ordering and
assembly mechanism.

###  III-B Evaluation Setup

We use five Intel NUC edge servers with an Intel® Pentium® Silver J5005 CPU @
1.50 GHz with 2 cores enabled to emulate the robot and 4 cores enabled to
emulate the edge servers. They are connected in a ring that one server is only
connected to two other neighbor servers. We conduct preliminary evaluation on
the networking performance with ROS 2 and CycloneDDS with three real robotics
applications.

FogROS G is evaluated with the following ROS applications: (1) Visual SLAM
Simultaneous Localization and Mapping (vSLAM) with ORB-SLAM2 [26], and we use
fr2/loop from TUM Dataset[11]; (2) Grasp Planning with Dex-Net [27], and (3)
Motion Planning with Motion Planning Templates (MPT) [28], and we use Home
dataset from Open Motion Planning Library OMPL[29]. We refer readers to
FogROS1 [16] and FogROS2 [9] for more details.

| Robot | ROS2 | FogROS G
---|---|---|---
Scenario | Only | Network | Total | Network | Total
vSLAM | 0.68 | 0.010 | 1.4 | 0.024 | 1.4
MotionPlanning | 161.8 | 0.008 | 4.3 | 0.023 | 4.3
GraspPlanning | 14.0 | 0.065 | 0.6 | 0.089 | 0.6
TABLE I: Network and end-to-end total latency benchmark of FogROS G on edge.
We measure the network and total time in seconds using unsecured ROS2 with
CycloneDDS on the edge, FogROS G with the cloud and edge servers. Total time
is the sum of network and compute time. We assume both cloud server and robot
run behind firewall similar to Figure 4.  Figure 5: Network Latency Comparison
between Off-the-shelf ROS2 and FogROS G. The experiment is conducted through
three intermediate routing nodes.

Figure 5 compares the network latency between off-the-shelf ROS2 and FogROS G.
FogROS G introduces an additional 0.014 second overhead on average compared to
the off-the-shelf ROS2 with CycloneDDS. The additional latency is caused by
the proxy and the cost of cryptographic operations. Due to our current
implementation limitations, the numbers for FogROS G show the one-way latency
instead of the end-to-end latency. The actual latency will be slightly larger
and they will be reflected in the final published version.

The key insight from Table I is that FogROS G introduces very little overhead
compared to the the original unsecured ROS2 - despite FogROS G is safer and
more connected. The overhead is negligible to the actual compute intensive
application.

##  IV Discussion and Future Work

In this paper, we enable secure and location independent fog robotics
applications by giving every ROS node a globally identifiable name and using
GDP to securely route to the name. Besides completing the evaluation section
and deploying our design with real robots, we deem the following research
directions as the future work of this project: (1) ROS message persistence and
replay. We hope to leverage the persistence aspect of the GDP routing. As the
ROS messages can be securely routed to persistent storage server and replayed
later. (2) Service-centric Anycast Routing. In this paper, we explored
indexing a ROS node with globally unique name. However, we can name services
(such as grasp planning as a service) with the same 256-bit name. The robot
can query in an anycast style to reach out to the service closest to the
robot.

## References

  * [1] A. K. Tanwani, R. Anand, J. E. Gonzalez, and K. Goldberg, “RILaaS: Robot inference and learning as a service,” _IEEE Robotics & Automation Letters_, vol. 5, no. 3, pp. 4423–4430, 2020.
  * [2] N. Tian, A. K. Tanwani, J. Chen, M. Ma, R. Zhang, B. Huang, K. Goldberg, and S. Sojoudi, “A fog robotic system for dynamic visual servoing,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 1982–1988.
  * [3] B. Kehoe, S. Patil, P. Abbeel, and K. Goldberg, “A survey of research on cloud robotics and automation,” _IEEE Trans. Automation Science and Engineering_ , vol. 12, no. 2, pp. 398–409, 2015.
  * [4] B. Kehoe, A. Matsukawa, S. Candido, J. Kuffner, and K. Goldberg, “Cloud-based robot grasping with the google object recognition engine,” in _Proc. IEEE Int. Conf. Robotics and Automation (ICRA)_ , 2013, pp. 4263–4270.
  * [5] M.-L. Lam and K.-Y. Lam, “Path planning as a service PPaaS: Cloud-based robotic path planning,” in _Proc. IEEE Int. Conf. on Robotics and Biomimetics (ROBIO)_ , 2014, pp. 1839–1844.
  * [6] G. Mohanarajah, V. Usenko, M. Singh, R. D’Andrea, and M. Waibel, “Cloud-based collaborative 3d mapping in real-time with low-cost robots,” _IEEE Trans. Automation Science and Engineering_ , vol. 12, no. 2, pp. 423–431, 2015\.
  * [7] C. Mouradian, S. Yangui, and R. H. Glitho, “Robots as-a-service in cloud computing: Search and rescue in large-scale disasters case study,” in _IEEE Consumer Communications & Networking Conference (CCNC)_, 2018, pp. 1–7.
  * [8] J. Rosa and R. P. Rocha, “Exportation to the cloud of distributed robotic tasks implemented in ros,” in _Proceedings of the Symposium on Applied Computing_ , 2017, pp. 235–240.
  * [9] J. Ichnowski, K. Chen, K. Dharmarajan, S. Adebola, M. Danielczuk, V. Mayoral-Vilches, H. Zhan, D. Xu, R. Ghassemi, J. Kubiatowicz, _et al._ , “Fogros 2: An adaptive and extensible platform for cloud and fog robotics using ros 2,” _arXiv preprint arXiv:2205.09778_ , 2022.
  * [10] J. Chandrasekaran, “Mobile ip: Issues, challenges and solutions,” _Newark: Rutgers University_ , 2009.
  * [11] J. Sturm, N. Engelhard, F. Endres, W. Burgard, and D. Cremers, “A benchmark for the evaluation of rgb-d slam systems,” in _Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS)_ , Oct. 2012.
  * [12] V. Mayoral-Vilches, R. White, G. Caiazza, and M. Arguedas, “Sros2: Usable cyber security tools for ros 2,” _arXiv e-prints_ , pp. arXiv–2208, 2022\.
  * [13] “Hacking ROS 2 ethically,” https://cybersecurityrobotics.net/hacking-ros-2/, accessed: 2021-02-15.
  * [14] E. Boasson, A. Corsaro, and H. van t Hag, “Eclipse Cyclone DDS,” https://projects.eclipse.org/projects/iot.cyclonedds.
  * [15] eProsima, “Fast DDS,” https://www.eprosima.com/index.php/products-all/eprosima-fast-dds.
  * [16] K. E. Chen, Y. Liang, N. Jha, J. Ichnowski, M. Danielczuk, J. Gonzalez, J. Kubiatowicz, and K. Goldberg, “FogROS: An adaptive framework for automating fog robotics deployment,” in _2021 IEEE 17th International Conference on Automation Science and Engineering (CASE)_. IEEE, 2021, pp. 2035–2042.
  * [17] “Integrating ROS2 with Eclipse zenoh,” https://zenoh.io/blog/2021-04-28-ros2-integration/, accessed: 2021-02-15.
  * [18] N. Mor, R. Pratt, E. Allman, K. Lutz, and J. Kubiatowicz, “Global data plane: A federated vision for secure data in edge computing,” in _2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)_. IEEE, 2019, pp. 1652–1663.
  * [19] J. Katz, R. Ostrovsky, and M. Yung, “Efficient password-authenticated key exchange using human-memorable passwords,” in _International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 2001, pp. 475–494.
  * [20] “CycloneDDS Peer with multiple remote machines,” https://github.com/eclipse-cyclonedds/cyclonedds/blob/master/docs/manual/options.md#cycloneddsdomaindiscovery, accessed: 2021-02-15.
  * [21] “FastDDS Peer with multiple remote machines,” https://fast-dds.docs.eprosima.com/en/latest/fastdds/use˙cases/wifi/initial˙peers.html, accessed: 2021-02-15.
  * [22] S. Heron, “Advanced encryption standard (aes),” _Network Security_ , vol. 2009, no. 12, pp. 8–12, 2009.
  * [23] A. W. Appel, “Verification of a cryptographic primitive: Sha-256,” _ACM Transactions on Programming Languages and Systems (TOPLAS)_ , vol. 37, no. 2, pp. 1–31, 2015.
  * [24] D. Johnson, A. Menezes, and S. Vanstone, “The elliptic curve digital signature algorithm (ecdsa),” _International journal of information security_ , vol. 1, no. 1, pp. 36–63, 2001.
  * [25] A. Panda, S. Han, K. Jang, M. Walls, S. Ratnasamy, and S. Shenker, “$\\{$NetBricks$\\}$: Taking the v out of $\\{$NFV$\\}$,” in _12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)_ , 2016, pp. 203–216.
  * [26] R. Mur-Artal and J. D. Tardós, “ORB-SLAM2: An open-source slam system for monocular, stereo, and RGB-D cameras,” _IEEE Trans. Robotics_ , vol. 33, no. 5, pp. 1255–1262, 2017.
  * [27] J. Mahler, J. Liang, S. Niyaz, M. Laskey, R. Doan, X. Liu, J. A. Ojea, and K. Goldberg, “Dex-Net 2.0: Deep learning to plan robust grasps with synthetic point clouds and analytic grasp metrics,” in _Proc. Robotics: Science and Systems (RSS)_ , 2017.
  * [28] J. Ichnowski and R. Alterovitz, “Motion planning templates: A motion planning framework for robots with low-power CPUs,” in _Proc. IEEE Int. Conf. Robotics and Automation (ICRA)_ , 2019.
  * [29] I. A. Şucan, M. Moll, and L. E. Kavraki, “The Open Motion Planning Library,” _IEEE Robotics & Automation Magazine_, vol. 19, no. 4, pp. 72–82, Dec. 2012. [Online]. Available: http://ompl.kavrakilab.org


lemmathmlemma corthmcor propthmprop dfthmdf remthmrem exthmex

# On a theorem of Lafforgue

Matthew Baker  Matthew Baker, School of Mathematics, Georgia Institute of
Technology, Atlanta, USA<EMAIL_ADDRESS>and  Oliver Lorscheid  Oliver
Lorscheid, University of Groningen, the Netherlands, and IMPA, Rio de Janeiro,
Brazil<EMAIL_ADDRESS>
###### Abstract.

We give a new proof, along with some generalizations, of a folklore theorem
(attributed to Laurent Lafforgue) that a rigid matroid (i.e., a matroid with
indecomposable basis polytope) has only finitely many projective equivalence
classes of representations over any given field.

The authors thank David Speyer, Alex Fink, and Rudi Pendavingh for helpful
discussions. We also thank BIRS for their hospitality hosting the workshop
23w5149: "Algebraic Aspects of Matroid Theory", during which the arguments in
this paper emerged. Thanks also to Justin Chen, Eric Katz, and Bernd Sturmfels
for their feedback on an earlier version of the paper. The first author was
supported by NSF grant DMS-2154224 and a Simons Fellowship in Mathematics. The
second author was supported by Marie Skłodowska Curie Fellowship MSCA-
IF-101022339.

##  1\. Introduction

A matroid $M$ is called rigid if its base polytope $P_{M}$ has no non-trivial
regular matroid polytope subdivisions. Such matroids are interesting for a
number of reasons; for example, a theorem of Bollen–Draisma–Pendavingh [8]
asserts that for each prime number $p$, a rigid matroid is algebraically
representable in characteristic $p$ if and only if it is linearly
representable in characteristic $p$. A folklore theorem, attributed to L.
Lafforgue, asserts that a rigid matroid has at most finitely many
representations over any field, up to projective equivalence. This is
mentioned without proof in a few places throughout the literature, for example
in Alex Fink’s Ph.D. thesis [12, p. 10], where he writes:

> Matroid subdivisions have made prominent appearances in algebraic geometry.
> […] Lafforgue’s work implies, for instance, that a matroid whose polytope
> has no subdivisions is representable in at most finitely many ways, up to
> the actions of the obvious groups.

We have been unable to find a proof of this result in the papers of Lafforgue
cited by Fink [15, 16], though a proof sketch appears in [13, Theorem 7.8]. In
this paper, we provide a rigorous and efficient proof of Lafforgue’s theorem,
along with some new generalizations.

What is arguably most interesting about our approach to Lafforgue’s theorem is
that we deduce it from a purely algebraic statement which has nothing to do
with matroids. The only input from matroid theory needed is the fact that the
rescaling class functor ${\mathcal{X}}_{M}$ from pastures to sets is
representable (see Section 2 below for further details). We believe this to be
a nice illustration of the power, and elegance, of the algebraic theory
developed by the authors in [3] and [4].

##  2\. Reformulation and generalizations of Lafforgue’s theorem

It is well-known to experts that a matroid $M$ is rigid if and only if every
valuated matroid ${\mathbb{M}}$ whose underlying matroid is $M$ is rescaling
equivalent to the trivially valuated matroid. Since we could not find a
reference for this result, we provide a proof in Appendix B.

Recall from [3] (see also Appendix A) that there is a category of algebraic
objects called pastures, which generalize not only fields but also partial
fields and hyperfields. According to [1], there is a robust notion of (weak)
matroids over a pasture111Technically speaking, [1] deals with tracts, not
pastures, but the difference between the two is immaterial when considering
weak matroids. For the sake of brevity, we do not define tracts in this paper,
nor do we consider idylls or ordered blueprints (both of which play a
prominent role in [4]). $P$ such that (to mention just a few examples):

  * $\bullet$

Matroids over the Krasner hyperfield ${\mathbb{K}}$ are the same thing as
matroids in the usual sense.

  * $\bullet$

Matroids over the tropical hyperfield ${\mathbb{T}}$ are the same thing as
valuated matroids.

  * $\bullet$

Matroids over a field $K$ are the same thing as $K$-representable matroids,
together with a choice of a matrix representation (up to the equivalence
relation where two matrices are equivalent if they have the same row space).

For every matroid $M$ there is a functor ${\mathcal{X}}_{M}$ from pastures to
sets taking a pasture $P$ to the set of rescaling equivalence classes of
(weak) $P$-representations of $M$. A matroid $M$ is rigid if and only if
${\mathcal{X}}_{M}({\mathbb{T}})$ consists of a single point. For a field $K$,
${\mathcal{X}}_{M}(K)$ coincides with the set of projective equivalence
classes of representations of $M$ over $K$. Thus Lafforgue’s theorem is
equivalent to the assertion that if ${\mathcal{X}}_{M}({\mathbb{T}})$ is a
singleton, then ${\mathcal{X}}_{M}(K)$ is finite for every field $K$.

Recall from [3] that for every matroid $M$, the functor ${\mathcal{X}}_{M}$ is
representable by a pasture $F_{M}$ canonically associated to $M$, called the
foundation of $M$. Concretely, this means that
$\operatorname{Hom}(F_{M},P)={\mathcal{X}}_{M}(P)$ for every pasture $P$,
functorially in $P$.

From this point of view, Lafforgue’s theorem is equivalent to the assertion
that if $\operatorname{Hom}(F_{M},{\mathbb{T}})=\\{0\\}$, then
$\operatorname{Hom}(F_{M},K)$ is finite for every field $K$. This is the
statement of Lafforgue’s theorem that we actually prove in this paper. The
advantage of this formulation is that it turns out to be a special case of a
result which can be formulated purely in the language of pastures, without any
mention of matroids! In fact, the algebraic incarnation of this result holds
more generally with pastures (which generalize fields) replaced by bands
(which generalize rings).

See Appendix A for an overview of bands, including a definition, some
examples, and the key facts needed for the present paper.

###  2.1. An algebraic generalization of Lafforgue’s theorem

In order to state the algebraic result about bands which implies Lafforgue’s
theorem, we mention (see Section 4 below) that given a band $B$ and a field
$K$, there is a canonically associated $K$-algebra $\myrho_{K}(B)$ with the
universal property that $\operatorname{Hom}_{\rm
Band}(B,S)=\operatorname{Hom}_{K-{\rm alg}}(\myrho_{K}(B),S)$ for every
$K$-algebra $S$. Moreover, if $B$ is finitely generated (which is the case,
for example, when $B=F_{M}$ for some matroid $M$), then so is $\myrho_{K}(B)$.

If $B$ is finitely presented, the set $\operatorname{Hom}(B,{\mathbb{T}})$ has
the structure of a finite polyhedral complex $\Sigma_{B}$; cf. Section 4.
Moreover, if $K$ is a field, the set $\operatorname{Hom}_{\rm Band}(B,K)$ is
equal to $\operatorname{Hom}_{K-{\rm alg}}(\myrho_{K}(B),K)$, which is in turn
equal to the set $X_{B,K}(K)$ of $K$-points of the finite type affine
$K$-scheme $X_{B,K}:=\operatorname{Spec}(\myrho_{K}(B))$. (When $B=F_{M}$ for
a matroid $M$, we call $X_{B,K}$ the reduced realization space of $M$ over
$K$.)

Our first generalization of Lafforgue’s theorem is as follows:

######  Theorem 2.1.

For every finitely generated band $B$ and every field $K$, we have the
inequality $\dim X_{B,K}\leqslant\dim\Sigma_{B}$. In particular, if
$\operatorname{Hom}(B,{\mathbb{T}})=\\{0\\}$, then $\dim\Sigma_{B}=0$ and thus
$X_{B,K}(K)=\operatorname{Hom}(B,K)$ is finite for every field $K$.

Applying Theorem 2.1 to $B=F_{M}$ immediately gives:

######  Corollary  (Lafforgue).

If $M$ is a rigid matroid, then ${\mathcal{X}}_{M}(K)$ is finite for every
field $K$.

In the terminology of Appendix B, Theorem 2.1 in the case $B=F_{M}$ says
precisely that for any field $K$, the dimension of the reduced realization
space of $M$ over $K$ is bounded above by the dimension of the reduced
Dressian of $M$.

###  2.2. A relative version of Lafforgue’s theorem

Rudi Pendavingh (private communication) asked if there might be a relative
version of Lafforgue’s theorem with respect to minors of $M$. More precisely,
Pendavingh asked the following question: Suppose $N$ is an (embedded) minor of
$M$ with the property that a valuated matroid structure on $M$ is determined,
up to rescaling equivalence, by its restriction to $N$. Is it then true that,
for every field $K$, there are (up to projective equivalence) at most finitely
many extensions of each $K$-representation of $N$ to a $K$-representation of
$M$?

We answer Pendavingh’s question in the affirmative, proving the following
algebraic generalization of Section 2.1:

######  Theorem 2.2.

Let $K$ be an algebraically closed valued field, and let $v:K\to{\mathbb{T}}$
be a non-trivial valuation. If $f:B_{1}\to B_{2}$ is a homomorphism of
finitely generated bands, then the fiber dimension of
$f_{K}:\operatorname{Hom}(B_{2},K)\to\operatorname{Hom}(B_{1},K)$ is bounded
above by the fiber dimension of
$f_{{\mathbb{T}}}:\operatorname{Hom}(B_{2},{\mathbb{T}})\to\operatorname{Hom}(B_{1},{\mathbb{T}})$,
i.e., if $x\in\operatorname{Hom}(B_{1},K)$ and $x^{\prime}$ is the image of
$x$ in $\operatorname{Hom}(B_{1},{\mathbb{T}})$, then $\dim
f_{K}^{-1}(x)\leqslant\dim f_{{\mathbb{T}}}^{-1}(x^{\prime})$.

In particular, setting $B_{1}=F_{N}$ and $B_{2}=F_{M}$ when $N$ is an embedded
minor of a matroid $M$, we find that if the induced map
${\mathcal{X}}_{N}({\mathbb{T}})\to{\mathcal{X}}_{M}({\mathbb{T}})$ has finite
fibers (i.e., a valuated matroid structure on $N$ has at most finitely many
extensions to $M$, up to rescaling equivalence) then, for every field $k$, the
natural map ${\mathcal{X}}_{N}(k)\to{\mathcal{X}}_{M}(k)$ has finite fibers,
i.e., every $k$-representation of $N$ has at most finitely many extensions to
$M$, up to projective equivalence.

Note that Lafforgue’s theorem (Section 2.1) follows from the special case of
Theorem 2.2 where $N$ is the trivial (empty) matroid and
$f_{{\mathbb{T}}}:\operatorname{Hom}(B_{2},{\mathbb{T}})\to\operatorname{Hom}(B_{1},{\mathbb{T}})$
has finite fibers.

##  3\. Some examples

In this section we present examples of both rigid and non-rigid matroids (see
Appendix A for some details on our notation).

######  Example  (Dress–Wenzel).

In [11, Theorem 5.11], Dress and Wenzel showed that if the inner Tutte group
$F_{M}^{\times}$ of the matroid $M$ is finite, then $M$ is rigid. From our
point of view, this is clear, since the inner Tutte group is the
multiplicative group of the foundation (cf. [4, Corollary 7.13]) and a non-
trivial homomorphism $F_{M}\to{\mathbb{T}}$ of pastures would give, in
particular, a nonzero group homomorphism $F_{M}^{\times}\to({\mathbb{R}},+)$;
however the only torsion element of $({\mathbb{R}},+)$ is 0.

For example:

  1. (1)

The foundation of the Fano matroid $F_{7}$ is ${\mathbb{F}}_{2}$, so $F_{7}$
is rigid. More generally, any binary matroid has foundation equal to either
${\mathbb{F}}_{1}^{\pm}$ or ${\mathbb{F}}_{2}$ [4, Corollary 7.32] and so it
is rigid.

  2. (2)

The foundation of the ternary spike $T_{8}$ is ${\mathbb{F}}_{3}$ (see [5,
Proposition 8.9]), so $T_{8}$ is also rigid.

  3. (3)

Dress and Wenzel prove in [11, Corollary 3.8] that the inner Tutte group of
any finite projective space of dimension at least 2 is finite, which provides
a wealth of additional examples of rigid matroids.

  4. (4)

Since the automorphism group of the ternary affine plane $M={\rm AG}(2,3)$
acts transitively, all single-element deletions are isomorphic to each other.
Let $M^{\prime}$ be any of these deletions. By [5, Proposition 6.2], the
foundation of $M^{\prime}$ is equal to the hexagonal (or sixth-root-of-unity)
partial field ${\mathbb{H}}\ =\
{{\mathbb{F}}_{1}^{\pm}}(T)\\!\sslash\\!\langle\\!\\!\langle
T^{3}+1,T-T^{2}-1\rangle\\!\\!\rangle$, whose multiplicative group is the
group of sixth roots of unity in ${\mathbb{C}}$. Therefore $M^{\prime}$ is
rigid.

It is not true that a matroid $M$ is rigid if and only if its inner Tutte
group (or, equivalently, its foundation) is finite. For example:

######  Example  (suggested by Rudi Pendavingh).

Let $M$ be the Betsy Ross matroid (cf. [23, Figure 3.3], where $M$ is also
called $B_{11}$). Using the Macaulay2 software described in [10], we have
checked that $F_{M}$ is the (infinite) golden ratio partial field
${\mathbb{G}}\ =\ {{\mathbb{F}}_{1}^{\pm}}(T)\\!\sslash\\!\langle\\!\\!\langle
T^{2}-T-1\rangle\\!\\!\rangle$. One checks easily that ${\rm
Hom}({\mathbb{G}},{\mathbb{T}})$ is trivial, so $M$ is rigid; in particular,
the converse of the statement “$F_{M}$ finite implies $M$ rigid” is not true.
It is also easy to see directly that ${\mathbb{G}}$ admits only finitely many
homomorphisms to any field.

######  Example .

The matroid $U_{2,4}$ is not rigid, since its foundation is the near-regular
partial field ${\mathbb{U}}\ =\
{{\mathbb{F}}_{1}^{\pm}}(T_{1},T_{2})\\!\sslash\\!\langle\\!\\!\langle
T_{1}+T_{2}-1\rangle\\!\\!\rangle$, which admits infinitely many different
homomorphisms to ${\mathbb{T}}$ (map $T_{1}$ to 1 and $T_{2}$ to any element
less than or equal to 1, or vice-versa). And for any field $K$, the reduced
realization space ${\mathcal{X}}_{M}(K)$ is equal to $K\backslash\\{0,1\\}$,
so in particular it is infinite whenever $K$ is. The base polytope of
$U_{2,4}$ is an octahedron, which admits a regular matroid decomposition into
two tetrahedra (see [18, p. 189] for a nice visualization).

######  Example .

The non-Fano matroid $M=F_{7}^{-}$ is not rigid, and it provides an example
for which the dimension of the reduced realization spaces
${\mathcal{X}}_{M}(K)$ and ${\mathcal{X}}_{M}({\mathbb{T}})$ jumps. The
foundation of $M$ is the dyadic partial field
${\mathbb{D}}={{\mathbb{F}}_{1}^{\pm}}(T)\\!\sslash\\!\langle\\!\\!\langle
T+T-1\rangle\\!\\!\rangle$ by [5, Prop. 8.4], and there is at most one
homomorphism $F_{M}={\mathbb{D}}\to K$ into any field $K$, sending $T$ to the
multiplicative inverse of $2$ (if it exists, i.e., if $\textup{char}\;K\neq
2$). In contrast, there are infinitely many homomorphisms
${\mathbb{D}}\to{\mathbb{T}}$ (parametrized by the image of
$f(T)\in{\mathbb{T}}$). So
$\dim{\mathcal{X}}_{M}(K)=0<1=\dim{\mathcal{X}}({\mathbb{T}})$.

##  4\. Proof of the main theorems

The key fact needed for the proof of Theorem 2.1 is the following theorem of
Bieri and Groves [7, Theorem A], which is a cornerstone of tropical geometry.
For the statement, recall that a semi-valuation from a ring $R$ to
$\overline{\mathbb{R}}={\mathbb{R}}\cup\\{+\infty\\}$ is a map
$v:R\to\overline{\mathbb{R}}$ such that $v(0)=+\infty$, $v(xy)=v(x)+v(y)$, and
$v(x+y)\geqslant\textup{min}\\{v(x),v(y)\\}$ for all $x,y\in R$. (The map $v$
is called a valuation if, in addition, $v(x)=+\infty$ implies that $x=0$.) If
$R$ is a $K$-algebra, where $K$ is a valued field (i.e., a field endowed with
a valuation $v:K\to\overline{\mathbb{R}}$), a $K$-semi-valuation is a semi-
valuation which restricts to the given valuation on $K$.

######  Theorem 4.1 (Bieri–Groves).

Let $K$ be a field endowed with a real valuation $v$, and suppose $R$ is a
finitely generated $K$-algebra with Krull dimension equal to $n$, having
generators $T_{1},\ldots,T_{n}$. Let $X={\rm Spec}(R)$ be the corresponding
affine $K$-scheme. Then the set

${\rm
Trop}(X):=\\{(v(T_{1}),\ldots,v(T_{n}))\;|\;v:R\to\overline{\mathbb{R}}\textrm{
is a $K$-semi-valuation}\\}$

is a polyhedral complex of dimension $\dim({\rm Trop}(X))=\dim X$.

######  Remark .

Bieri and Groves assume that $X$ is irreducible and show, more precisely, that
${\rm Trop}(X)$ has pure dimension $n$. Our formulation of the Bieri–Groves
theorem (which does not include the purity statement) follows immediately from
theirs by decomposing $X$ into irreducible components.

######  Remark .

More or less by definition, a semi-valuation on a ring $R$ is precisely the
same thing as a homomorphism from $R$ to ${\mathbb{T}}$ in the category of
bands, and if $K$ is a valued field then a $K$-semi-valuation on $R$ is the
same thing as a homomorphism from $R$ to ${\mathbb{T}}$ which restricts to the
given homomorphism $v:K\to{\mathbb{T}}$ on $K$.

Let $K$ be a field, and let $\operatorname{{Alg}}_{K}$ denote the category of
$K$-algebras, i.e. ring extensions $R$ of $K$ together with $K$-linear ring
homomorphisms. We write $\operatorname{Hom}_{K}(R,S)$ for the set of
$K$-algebra homomorphisms between two $K$-algebras $R$ and $S$. Given a band
$B$, we define the _associated $K$-algebra_ as

$\myrho_{K}(B)\ =\ K[B]\,/\,\langle N_{B}\rangle,$

where $K[B]$ is the monoid algebra over $K$ and the elements of the nullset
$N_{B}$ are interpreted as elements of $K[B]$ (cf. Appendix A). It comes with
a band homomorphism $\myalpha_{B}:B\to\myrho_{K}(B)$, which maps $a$ to $[a]$.

The other main ingredient needed for the proof of Theorem 2.1 is the following
technical but important result:

######  Proposition .

Let $K$ a field, $B$ be a band and $R=\myrho_{K}(B)$ the associated
$K$-algebra.

  1. (1)

The homomorphism $\myalpha_{B}:B\to\myrho_{K}(B)$ is initial for all
homomorphisms from $B$ to a $K$-algebra, i.e., for every $K$-algebra $S$ the
natural map

$\operatorname{Hom}_{K}(R,S)\
\stackrel{{\scriptstyle\myalpha_{B}^{\ast}}}{{\longrightarrow}}\
\operatorname{Hom}(B,S)$

is a bijection.

  2. (2)

Assume we are given a valuation $v_{K}:K\to{\mathbb{T}}$, and that $B$ is
finitely generated by $a_{1},\dotsc,a_{n}$. Let $T_{i}=\myalpha_{B}(a_{i})$
for $i=1,\dotsc,n$, and let $X=\operatorname{Spec}R$. Let
$\exp^{n}:\overline{\mathbb{R}}^{n}\to{\mathbb{T}}^{n}$ be the coordinate-wise
exponential map. Then the $T_{i}$ generate $R$ as a $K$-algebra, and

$\exp^{n}\Big{(}\operatorname{Trop}(X)\Big{)}\ \subset\
\operatorname{Hom}(B,{\mathbb{T}})$

as subsets of ${\mathbb{T}}^{n}$.

###### Proof.

We begin with (1). The map $\myalpha_{B}^{\ast}$ is injective since $R$ is
generated by the subset $\myalpha_{B}(B)$, and therefore every homomorphism
$f:R\to S$ is determined by the composition $f\circ\myalpha_{B}:B\to S$. In
order to show that $\myalpha_{B}^{\ast}$ is surjective, consider a band
homomorphism $f:B\to S$, which is, in particular a multiplicative map.
Therefore it extends (uniquely) to a $K$-linear homomorphism $\hat{f}:K[B]\to
S$ from the monoid algebra $K[B]$ to $S$. For every $\sum a_{i}\in N_{B}$, we
have $\sum f(a_{i})\in N_{S}$ by the definition of a band homomorphism. By the
definition of $N_{S}$, this means that $\sum f(a_{i})=0$ in $S$. Thus
$\hat{f}$ factorizes through $\bar{f}:R=K[B]/\langle N_{B}\rangle\to S$, and,
by construction, we have
$f=\bar{f}\circ\myalpha_{B}=\myalpha_{B}^{\ast}(\bar{f})$. This establishes
(1).

We continue with (2). Since $B$ is generated by $a_{1},\dotsc,a_{n}$ as a
pointed monoid and $\myalpha_{B}(B)$ generates $R$ as a $K$-algebra, $R$ is
generated as a $K$-algebra by $T_{1},\dotsc,T_{n}$. In order to verify that
$\exp^{n}(\operatorname{Trop}(X))\subset\operatorname{Hom}(B,{\mathbb{T}})$,
consider a point $(v(T_{1}),\dotsc,v(T_{n}))\in\operatorname{Trop}(X)$, where
$v:R\to\overline{\mathbb{R}}$ is a $K$-semi-valuation. Post-composing $v$ with
$\exp$ yields a seminorm $v^{\prime}:R\to{\mathbb{T}}$, which is,
equivalently, a band homomorphism. Pre-composing $v^{\prime}$ with
$\myalpha_{B}$ yields a band homomorphism $v^{\prime\prime}:B\to{\mathbb{T}}$,
which is an element of $\operatorname{Hom}(B,{\mathbb{T}})$. By construction,
$\exp^{n}(v(T_{1}),\dotsc,v(T_{n}))=v^{\prime\prime}$, which establishes the
last assertion. ∎

######  Remark .

  1. (1)

Under the assumptions of Section 4.(2), $\operatorname{Hom}(B,{\mathbb{T}})$
embeds as a subspace of ${\mathbb{T}}^{n}$, which has a well-defined
(Lebesgue) covering dimension in the sense of [21, Chapter 3]. As discussed in
[17], the subspace topology of
$\operatorname{Hom}(B,{\mathbb{T}})\subset{\mathbb{T}}^{n}$ is equal to the
compact-open topology for $\operatorname{Hom}(B,{\mathbb{T}})$ with respect to
the discrete topology for $B$ and the natural order topology for
${\mathbb{T}}$, which shows that the dimension of
$\operatorname{Hom}(B,{\mathbb{T}})$ does not depend on the embedding into
${\mathbb{T}}^{n}$.

  2. (2)

With the topologies just described, $\exp^{n}$ defines a continuous injection
from $\operatorname{Trop}(X)$ to $\operatorname{Hom}(B,{\mathbb{T}})$ which
identifies the former with a closed subspace of the latter. In particular,
[21, Prop. 3.1.5] shows that
$\dim\operatorname{Trop}(X)\leqslant\dim\operatorname{Hom}(B,{\mathbb{T}})$.

  3. (3)

If in addition to the assumptions of (2), $N_{B}$ is finitely generated as an
ideal of $B^{+}$, then $\operatorname{Hom}(B,{\mathbb{T}})$ is a tropical pre-
variety in ${\mathbb{T}}^{n}$ and is therefore the underlying set of a finite
polyhedral complex. The dimension of $\operatorname{Hom}(B,{\mathbb{T}})$ as a
polyhedral complex is equal to its covering dimension [21, Theorem 2.7 and
Section 3.7].

###### Proof of Theorem 2.1.

Let $v:K\to{\mathbb{T}}$ be a valuation (which we can take to be the trivial
valuation if we like). Let $\myalpha_{B}:B\to R$ be the canonical homomorphism
to the associated $K$-algebra $R=\myrho_{K}(B)$, cf. Section 4. Let
$a_{1},\dotsc,a_{n}\in B$ be a set of generators for $B$, and for
$i=1,\dotsc,n$ let $T_{i}=\myalpha_{B}(a_{i})$. By Section 4, the $T_{i}$
generate $R$ as a $K$-algebra, i.e., $R=K[T_{1},\dotsc,T_{n}]/I$ for some
ideal $I$.

Let $X=\operatorname{Spec}R$, so that $X(K)=\operatorname{Hom}_{K}(R,K)$.
Section 4 yields a commutative diagram

${X(K)=\operatorname{Hom}_{K}(R,K)}$${\operatorname{Hom}(B,K)}$${\operatorname{Trop}(X)}$${\operatorname{Hom}(B,{\mathbb{T}})}$$\scriptstyle{\simeq}$$\scriptstyle{\exp^{n}}$

where the right-hand vertical map is obtained by composing with
$v:K\to{\mathbb{T}}$ and the left-hand vertical map is induced by composing
the embedding of $X(K)=\operatorname{Hom}_{K}(R,K)$ into $K^{n}$ via
$\myphi\mapsto(\myphi(T_{i}))_{i=1}^{n}$ with the coordinate-wise absolute
value $v_{K}^{n}:K^{n}\to{\mathbb{T}}^{n}$.

By the Bieri–Groves theorem (Theorem 4.1), the dimension of the affine variety
$X$ is equal to the dimension of $\operatorname{Trop}(X)$, as defined in
Section 4. Using Section 4(2) and Section 4(2), we conclude that

$\dim\Big{(}X\Big{)}\ =\ \dim\Big{(}\operatorname{Trop}(X)\Big{)}\ \leqslant\
\dim\Big{(}\operatorname{Hom}(B,{\mathbb{T}})\Big{)},$

as desired. ∎

###### Proof of Theorem 2.2.

Suppose $f:B_{1}\to B_{2}$ is a band homomorphism. Choose generators
$x_{1},\ldots,x_{m}$ for $B_{1}$. Completing $f(x_{1}),\ldots,f(x_{m})$ to a
set of generators for $B_{2}$ if necessary, we find a generating set
$y_{1},\ldots,y_{n}$ for $B_{2}$ with $m\leqslant n$ such that
$f(x_{i})=y_{i}$ for $i=1,\ldots,m$. Setting
$X=\operatorname{Spec}(\myrho_{K}(B_{1}))$ and
$Y=\operatorname{Spec}(\myrho_{K}(B_{2}))$, and letting
$\operatorname{Trop}(X)$ (resp. $\operatorname{Trop}(Y)$) be the
tropicalization of $X$ with respect to
$\myalpha_{B_{1}}(x_{1}),\ldots,\myalpha_{B_{1}}(x_{m})$ (resp.
$\myalpha_{B_{2}}(y_{1}),\ldots,\myalpha_{B_{2}}(y_{n})$), we obtain a
commutative diagram

${Y(K)}$${X(K)}$${\operatorname{Trop}(Y)}$${\operatorname{Trop}(X)}$${\operatorname{Hom}(B_{2},{\mathbb{T}})}$${\operatorname{Hom}(B_{1},{\mathbb{T}})}$$\scriptstyle{f_{K}}$$\scriptstyle{f_{{\mathbb{T}}}}$

Since $\operatorname{Trop}(Y)$ is a closed subspace of
$\operatorname{Hom}(B_{2},{\mathbb{T}})$ (resp. $\operatorname{Trop}(X)$ is a
closed subspace of $\operatorname{Hom}(B_{1},{\mathbb{T}})$), it suffices to
prove that if $x\in X(K)$ and
$x^{\prime}=\operatorname{Trop}(x)\in\operatorname{Trop}(X)$, then $\dim
f_{K}^{-1}(x)\leqslant\dim f_{{\mathbb{T}}}^{-1}(x^{\prime})$.

To see this, write $f_{K}^{-1}(x)=Z(K)$ with $Z$ an affine subscheme of $Y$.
If we pull back the functions
$\myalpha_{B_{2}}(y_{1}),\ldots,\myalpha_{B_{2}}(y_{n})$ to a set of
generators for the affine coordinate ring of $Z$, we obtain a commutative
diagram

${Z(K)}$${Y(K)}$${X(K)}$${\operatorname{Trop}(Z)}$${\operatorname{Trop}(Y)}$${\operatorname{Trop}(X)}$

Applying the Bieri–Groves theorem to $Z$, we find that the image of $Z(K)$
under ${\rm Trop}$ has dimension equal to $\dim f_{K}^{-1}(x)$. In addition,
the natural map $\operatorname{Trop}(Z)\to\operatorname{Trop}(Y)$ identifies
$\operatorname{Trop}(Z)$ with a closed subspace of $\operatorname{Trop}(Y)$,
since $\operatorname{Trop}(Z)$ (resp. $\operatorname{Trop}(Y)$) is the
topological closure of $Z(K)$ (resp. $Y(K)$) in ${\mathbb{T}}^{n}$ (cf. [20,
Proposition 2.2]). By construction, $\operatorname{Trop}(Z)$ is in fact a
closed subspace of $\dim f_{{\mathbb{T}}}^{-1}(x^{\prime})$. This means that
$\dim f_{K}^{-1}(x)=\dim\operatorname{Trop}(Z)\leqslant\dim
f_{{\mathbb{T}}}^{-1}(x^{\prime})$ as desired. ∎

##  Appendix A Pastures and Bands

More details pertaining to the following overview of bands and pastures can be
found in [2].

In this text, a _pointed monoid_ is a (multiplicatively written) commutative
semigroup $A$ with identity $1$, together with a distinguished element $0$
that satisfies $0\cdot a=0$ for all $a\in A$. The _ambient semiring of $A$_ is
the semiring $A^{+}={\mathbb{N}}[A]/\langle 0\rangle$, which consists of all
finite formal sums $\sum a_{i}$ of nonzero elements $a_{i}\in A$. Note that
$A$ is embedded as a submonoid in $A^{+}$, where $0$ is identified with the
empty sum. An _ideal of $A^{+}$_ is a subset $I$ that contains $0$ and is
closed under both addition and multiplication by elements of $A^{+}$.

######  Definition .

A _band_ is a pointed monoid $B$ together with an ideal $N_{B}$ of $B^{+}$
(called the _nullset_) such that for every $a\in A$, there is a unique $b\in
A$ with $a+b\in N_{B}$. We call this $b$ the _additive inverse of $a$_, and we
denote it by $-a$. A _band homomorphism_ is a multiplicative map $f:B\to C$
preserving $0$ and $1$ such that $\sum a_{i}\in N_{B}$ implies $\sum
f(a_{i})\in N_{C}$. This defines the category $\operatorname{{Bands}}$.

(

For a subset $S$ of $B^{+}$, we denote by $\langle\\!\\!\langle
S\rangle\\!\\!\rangle$ the smallest ideal of $B^{+}$ that contains $S$ and is
closed under the _fusion axiom_ (cf. [6])

  1. (F)

if $c+\sum a_{i}$ and $-c+\sum b_{j}$ are in $\langle\\!\\!\langle
S\rangle\\!\\!\rangle$, then $\sum a_{i}+\sum b_{j}$ is in
$\langle\\!\\!\langle S\rangle\\!\\!\rangle$.

######  Definition .

A band $B$ is _finitely generated_ if it is finitely generated as a monoid. It
is a _finitely presented fusion band_ , which we abbreviate by simply saying
that $B$ is _finitely presented_ , if it is finitely generated and
$N_{B}=\langle\\!\\!\langle S\rangle\\!\\!\rangle$ for a finite subset $S$ of
$N_{B}$.

The _unit group of $B$_ is the submonoid $B^{\times}=\\{a\in B\mid ab=1\text{
for some }b\in B\\}$ of $B$, which is indeed a group.

######  Definition .

A _pasture_ is a band $P$ with $P^{\times}=P-\\{0\\}$ and

$N_{P}\ =\ \Big{\langle}\\!\\!\Big{\langle}\,a+b+c\in P^{+}\;\Big{|}\;a+b+c\in
N_{P}\,\Big{\rangle}\\!\\!\Big{\rangle}.$

######  Example .

Every ring $R$ is a band, with nullset $N_{R}=\\{\sum a_{i}\mid\sum
a_{i}=0\text{ in }R\\}$. In fact, this defines a fully faithful embedding
$\operatorname{{Rings}}\to\operatorname{{Bands}}$. Every field is a pasture.

The following examples of interest are bands which are not rings (we write
$a-b$ for $a+(-b)$):

  * $\bullet$

The _regular partial field_ is the pasture
${{\mathbb{F}}_{1}^{\pm}}=\\{0,1,-1\\}$ with nullset

$N_{{\mathbb{F}}_{1}^{\pm}}\ =\ \Big{\\{}n.1+n.(-1)\,\Big{|}\,n\geqslant
0\Big{\\}}\ =\ \langle\\!\\!\langle 1-1\rangle\\!\\!\rangle.$

  * $\bullet$

The _Krasner hyperfield_ is the pasture ${\mathbb{K}}=\\{0,1\\}$ with nullset

$N_{\mathbb{K}}\ =\ {\mathbb{N}}-\\{1\\}\ =\ \langle\\!\\!\langle 1+1,\
1+1+1\rangle\\!\\!\rangle.$

  * $\bullet$

The _tropical hyperfield_ is the pasture ${\mathbb{T}}={\mathbb{R}}_{\geqslant
0}$ with nullset

$\textstyle N_{\mathbb{T}}\ =\ \\{0\\}\ \cup\ \Big{\\{}\sum
a_{i}\;\Big{|}\;a_{1},\dotsc,a_{n}\text{ assumes its maximum at least
twice}\Big{\\}}.$

Examples of band homomorphisms are the inclusion
${\mathbb{K}}\hookrightarrow{\mathbb{T}}$ and the surjection
${\mathbb{T}}\to{\mathbb{K}}$ that sends every nonzero element to $1$. A band
homomorphism $R\to{\mathbb{T}}$ from a ring $R$ into ${\mathbb{T}}$ is the
same thing as a non-archimedean seminorm. In particular, the trivial absolute
value on a field $K$ is the unique band homomorphism $K\to{\mathbb{T}}$ that
factors through ${\mathbb{K}}$.

The pasture ${{\mathbb{F}}_{1}^{\pm}}$ is an initial object in
$\operatorname{{Bands}}$, i.e., every band $B$ comes with a unique
homomorphism ${{\mathbb{F}}_{1}^{\pm}}\to B$. This leads to a description
$B={{\mathbb{F}}_{1}^{\pm}}[T_{i}\mid i\in I]\\!\sslash\\!\langle S\rangle$ of
$B$ in terms of generators $\\{T_{i}\mid i\in I\\}$ and relations $S\subset
B^{+}$, in the sense that $\\{T_{i}\\}\cup\\{0,-1\\}$ generates $B$ as a
monoid, $S$ generates the ideal $N_{B}$, and $S$ contains a complete set of
binary relations between the signed products $x=\pm T_{i_{1}}\dotsb T_{i_{r}}$
of the $T_{i}$, i.e., if $x-y\in S$ then $x=y$ as elements of $B$.

Similarly, we write $P={{\mathbb{F}}_{1}^{\pm}}(T_{i}\mid i\in
I)\\!\sslash\\!\langle\\!\\!\langle S\rangle\\!\\!\rangle$ for a pasture $P$
if $P^{\times}$ is generated as a group by $\\{T_{i}\mid i\in I\\}$ and $-1$,
if $N_{P}=\langle\\!\\!\langle S\rangle\\!\\!\rangle$, and if $S$ contains a
complete set of binary relations between the signed products of the $T_{i}$.
For example,

${\mathbb{K}}\ =\ {{\mathbb{F}}_{1}^{\pm}}\\!\sslash\\!\langle\\!\\!\langle
1+1,\ 1+1+1\rangle\\!\\!\rangle,\quad\text{and}\quad{\mathbb{F}}_{5}\ =\
{{\mathbb{F}}_{1}^{\pm}}(T)\\!\sslash\\!\langle\\!\\!\langle T^{2}+1,\
T-1-1\rangle\\!\\!\rangle.$

##  Appendix B Valuated matroids and subdivisions of the basis polytope

In this section, we show that a matroid is rigid if and only if it has a
unique rescaling class over ${\mathbb{T}}$. We begin with some observations
and recall some results from the literature.

For a pasture $F$, we can identify isomorphism classes of a (weak) Grassmann-
Plücker function $\Delta$ with the corresponding Plücker vector
$(\Delta(I))_{I\in\binom{E}{r}}\in{\mathbb{P}}^{\binom{E}{r}}(F)$. We call
this Plücker vector a representation of $M$, and by abuse of terminology we
use the terms “Grassmann-Plücker function” and “Plücker vector”
interchangeably.

Every matroid $M$ can be (uniquely) represented over ${\mathbb{K}}$ by the
Grassmann-Plücker function $\Delta_{M}:\binom{E}{r}\to{\mathbb{K}}$ which
sends an $r$-subset $I$ of $E$ to $1$ if it a basis of $M$ and to $0$
otherwise. Post-composing $\Delta_{M}$ with the inclusion
${\mathbb{K}}\hookrightarrow{\mathbb{T}}$ defines the _trivial representation
of $M$_, which shows that $M$ has at least one rescaling class over
${\mathbb{T}}$.

Recall that the basis polytope $P_{M}$ of $M$ is the convex hull of the points
$e_{I}=\sum_{i\in I}e_{i}\in{\mathbb{R}}^{n}$ for which $I$ is a basis of $M$.
Let $\Delta:\binom{E}{r}\to{\mathbb{T}}$ be a Plücker vector for $M$, i.e.,
$\operatorname{supp\,}(\Delta)=\operatorname{supp\,}(\Delta_{M})$.

Let ${\mathcal{S}}_{\Delta}=\\{e_{I}\mid\Delta(I)\neq 0\\}$ be the support of
$\Delta$, considered as a subset of ${\mathbb{R}}^{n}$. Post-composing with
$\log$ yields a function
$\tilde{\Delta}:{\mathcal{S}}_{\Delta}\to{\mathbb{R}}$ whose graph $\Gamma$ is
a subset of ${\mathbb{R}}^{n}\times{\mathbb{R}}$. The convex closure of
$\Gamma$ has a unique coarsest structure as a polyhedral complex. The lower
faces of this polyhedral complex are those faces for which the last coordinate
of the outward normal vector is negative. Omitting this last coordinate
projects these faces onto $P_{M}$ and defines a polyhedral subdivision of
$P_{M}$ called the regular subdivision associated to $\Delta$, see e.g. [18,
Definition 2.3.8].

By a theorem of Speyer (cf. [22, Prop. 2.2]), this subdivision of $P_{M}$ is a
matroid subdivision, i.e., all faces of the subdivision are themselves matroid
polytopes, and conversely every regular matroid subdivision of $P_{M}$ comes
from a ${\mathbb{T}}$-representation of $M$ (see also [18, Lemma 4.4.6] and
[14, Thm. 10.35]).

######  Proposition .

A matroid $M$ is rigid if and only if $M$ has a unique rescaling class over
${\mathbb{T}}$.

###### Proof.

Let $r$ be the rank and $E=\\{1,\dotsc,n\\}$ the ground set of $M$. Let
$\Delta:\binom{E}{r}\to{\mathbb{T}}$ be a tropical Plücker vector for $M$, and
let ${\mathcal{S}}_{\Delta}$ be as above.

By definition, $M$ is rigid if and only if $P_{M}$ admits only the trivial
regular matroid subdivision. Since none of the points of
${\mathcal{S}}_{\Delta}$ lies in the convex closure of the other points,
$\Delta:\binom{E}{r}\to{\mathbb{T}}$ induces the trivial matroid subdivision
if and only if the subset $\Big{\\{}(e_{I},\tilde{\Delta}(I))\mid
I\in{\mathcal{S}}_{\Delta}\Big{\\}}$ of ${\mathbb{R}}^{n}\times{\mathbb{R}}$
is contained in an affine hyperplane $H$.

In this case, let $x_{i}e_{i}$ be the unique intersection point of $H$ with
the coordinate axis generated by $e_{i}$ (in the case of a loop $i$ of $M$
there is no such intersection point, and we can formally put $x_{i}=+\infty$).
Then $\tilde{\Delta}(I)=\sum_{k=1}^{r}x_{i_{k}}e_{i_{k}}$ for
$I\in{\mathcal{S}}_{\Delta}$. Rescaling $\Delta$ by $t=(\exp(-x_{i})\mid
i=1,\dotsc,n)$ yields a Plücker vector
$\Delta_{0}=t.\Delta:\binom{E}{r}\to{\mathbb{T}}$ for which

$\tilde{\Delta}_{0}(I)\ =\ \tilde{\Delta}(I)-\sum_{k=1}^{r}x_{i_{k}}e_{i_{k}}\
=\ 0$

for every $I\in{\mathcal{S}}_{\Delta}$. Thus $\tilde{\Delta}_{0}$ is the
trivial representation of $M$. Conversely, rescaling $\Delta_{0}$ yields a
Plücker vector $\Delta$ for which $\Big{\\{}(e_{I},\tilde{\Delta}(I))\mid
I\in{\mathcal{S}}_{\Delta}\Big{\\}}$ is contained in an affine hyperplane,
which concludes the proof. ∎

######  Remark .

The (local) Dressian of a matroid $M$ (cf. [19]) is a polyhedral complex
$\Delta_{M}$ whose underlying set consists of all
${\mathbb{T}}$-representations of $M$; the polyhedral structure is defined by
the 3-term tropical Plücker relations. One can show using [19, Cor. 18] that
the lineality space of $\Delta_{M}$ is precisely the set of valuations on $M$
which are projectively equivalent to the trivial valuation. The topological
space ${\rm Hom}(F_{M},{\mathbb{T}})$ considered in the body of this paper can
then be naturally identified with $\Delta_{M}$ modulo its lineality space,
which we call the reduced Dressian $\overline{\Delta}_{M}$. (We omit the
details, as it would take us too far afield into a somewhat lengthy discussion
of various topologies and polyhedral structures.) See [9, Section 3] for an
algorithm for computing the Dressian and/or reduced Dressian of a matroid $M$,
and also (in Section 5) some interesting counterexamples to plausible-sounding
assertions.

## References

  * [1] Matthew Baker and Nathan Bowler.  Matroids over partial hyperstructures.  Adv. Math., 343:821–863, 2019.
  * [2] Matthew Baker, Tong Jin, and Oliver Lorscheid.  Band schemes.  In preparation.
  * [3] Matthew Baker and Oliver Lorscheid.  Foundations of matroids. Part 1: Matroids without large uniform minors.  Preprint, arXiv:2008.00014. To appear in Memoirs of the AMS.
  * [4] Matthew Baker and Oliver Lorscheid.  The moduli space of matroids.  Adv. Math., 390:Paper No. 107883, 118, 2021.
  * [5] Matthew Baker, Oliver Lorscheid, and Tianyi Zhang.  Foundations of matroids, Part 2: Further theory, examples, and computational methods.  In preparation.
  * [6] Matthew Baker and Tianyi Zhang.  Fusion rules for pastures and tracts.  European J. Combin., 108:Paper No. 103628, 15, 2023.
  * [7] Robert Bieri and J. R. J. Groves.  The geometry of the set of characters induced by valuations.  J. Reine Angew. Math., 347:168–195, 1984.
  * [8] Guus P. Bollen, Jan Draisma, and Rudi Pendavingh.  Algebraic matroids and Frobenius flocks.  Adv. Math., 323:688–719, 2018.
  * [9] Madeline Brandt and David E. Speyer.  Computation of Dressians by dimensional reduction.  Adv. Geom., 22(3):409–420, 2022.
  * [10] Justin Chen and Tianyi Zhang.  Representing matroids via pasture morphisms.  Preprint, arXiv:2307.14275, 2023.
  * [11] Andreas W. M. Dress and Walter Wenzel.  Valuated matroids.  Adv. Math., 93(2):214–250, 1992.
  * [12] Alex Fink.  Matroid polytope subdivisions and valuations.  PhD thesis, University of California Berkeley, 2010.
  * [13] Alex Fink.  Polymatroid subdivision.  Preprint available at https://webspace.maths.qmul.ac.uk/a.fink/matroid_subdivisions_Edmonds2015.pdf, 2015\.
  * [14] Michael Joswig.  Essentials of tropical combinatorics, volume 219 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2021.
  * [15] Laurent Lafforgue.  Pavages des simplexes, schémas de graphes recollés et compactification des ${\rm PGL}^{n+1}_{r}/{\rm PGL}_{r}$.  Invent. Math., 136(1):233–271, 1999.
  * [16] Laurent Lafforgue.  Chirurgie des grassmanniennes, volume 19 of CRM Monograph Series.  American Mathematical Society, Providence, RI, 2003.
  * [17] Oliver Lorscheid.  Tropical geometry over the tropical hyperfield.  Rocky Mountain J. Math., 52(1):189–222, 2022.
  * [18] Diane Maclagan and Bernd Sturmfels.  Introduction to tropical geometry, volume 161 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2015.
  * [19] Jorge Alberto Olarte, Marta Panizzut, and Benjamin Schröter.  On local Dressians of matroids.  In Algebraic and geometric combinatorics on lattice polytopes, pages 309–329. World Sci. Publ., Hackensack, NJ, 2019.
  * [20] Sam Payne.  Analytification is the limit of all tropicalizations.  Math. Res. Lett., 16(3):543–556, 2009.
  * [21] A. R. Pears.  Dimension theory of general spaces.  Cambridge University Press, Cambridge, England-New York-Melbourne, 1975\.
  * [22] David E. Speyer.  Tropical linear spaces.  SIAM J. Discrete Math., 22(4):1527–1558, 2008.
  * [23] Stefan H. M. van Zwam.  Partial fields in matroid theory.  PhD thesis, Eindhoven, 2009. Available online at www.math.lsu.edu/~svanzwam/pdf/thesis-online.pdf.