#  On the equivalence of quasirandomness
and exchangeable representations
independent from lower-order variables

Leonardo N. Coregliano  Henry P. Towsner

###### Abstract

It is often convenient to represent a process for randomly generating a graph
as a graphon. (More precisely, these give _vertex exchangeable_
processes—those processes in which each vertex is treated the same way.) Other
structures can be treated by generalizations like hypergraphons, permutatons,
and, for a very general class, theons. These representations are not unique:
different representations can lead to the same probability distribution on
graphs. This naturally leads to questions (going back at least to Hoover’s
proof of the Aldous–Hoover Theorem on the existence of such representations)
that ask when quasirandomness properties on the distribution guarantee the
existence of particularly simple representations.

We extend the usual theon representation by adding an additional datum of a
random permutation to each tuple, which we call a $\ast$-representation. We
show that if a process satisfies the _unique coupling_ property
$\texttt{UCouple}[\ell]$, which says roughly that all $\ell$-tuples of
vertices “look the same”, then the process is $\ast$-$\ell$-independent: there
is a $\ast$-representation that does not make use of any random information
about $\ell$-tuples (including tuples of length $<\ell$). Simple examples show
that the use of $\ast$-representations is necessary.

This resolves a question of Coregliano and Razborov, since it easily follows
that $\texttt{UCouple}[\ell]$ implies $\texttt{Independence}[\ell^{\prime}]$
(the existence of an $\ell^{\prime}$-independent ordinary representation) for
$\ell^{\prime}<\ell$.

##  1 Introduction

Consider a rule for randomly generating a graph on a set of vertices $V$:

  * •

for each vertex $v\in V$ we pick a random value $\bm{\omega}_{v}\in[0,1]$
uniformly and independently,

  * •

for each pair of vertices $\\{v,w\\}\in\binom{V}{2}$ we pick a random value
$\bm{\omega}_{v,w}\in[0,1]$, also uniformly and independently,

  * •

we have a measurable set ${\mathcal{N}}_{E}\subseteq[0,1]^{3}$, and we place
an edge111Our notation here foreshadows the general situation, where we might
be considering structures with multiple edge relations simultaneously. In that
setting, we will need a different set ${\mathcal{N}}_{E}$ for each edge
relation $E$. between the pair $\\{v,w\\}$ if
$(\bm{\omega}_{v},\bm{\omega}_{w},\bm{\omega}_{v,w})\in{\mathcal{N}}_{E}$.

Such a construction is sometimes called a _$2$ -hypergraphon_222A _graphon_ is
a closely related object: specifically, given ${\mathcal{N}}_{E}$, we may
define a graphon $f_{E}\colon[0,1]^{2}\to[0,1]$ by
$f_{E}(\omega_{v},\omega_{w})\stackrel{{\scriptstyle\text{def}}}{{=}}\lambda(\\{\omega_{v,w}\mid(\omega_{v},\omega_{w},\omega_{v,w})\in{\mathcal{N}}_{E}\\})$,
where $\lambda$ is the Lebesgue measure.. These arise, for instance, as a way
to represent the limit of a suitably convergent sequence of graphs, and they
have been studied under using several essentially equivalent
formalisms—exchangeable relations [Aus08, DJ08], graph limits and graphons and
their generalizations [LS06, Lov12, ES12, CR20], flag algebras [Raz07] and
ultraproducts [ES12, NOdM12, AC14, NOdM20]. The Aldous–Hoover Theorem [Hoo79,
Ald81, Ald85] (see also [Kal05, Chapter 7]) says that _any_ method for
randomly generating a graph that treats the vertices symmetrically (that is,
which is _exchangeable_) can be represented as a distribution over
$2$-hypergraphons.

###### Example 1.1 (The Quasirandom Graph).

A fundamental example is the case where
${\mathcal{N}}^{\operatorname{qr}}_{E}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{(\omega_{v},\omega_{w},\omega_{v,w})\mid\omega_{v,w}<1/2\\}$.
This is essentially the process where we flip a coin for each pair $\\{v,w\\}$
and place an edge if the coin comes up heads.

The representation given by a $2$-hypergraphon is not unique: there are other
$2$-hypergraphons that are essentially the same. For instance, any measure-
preserving permutation of $[0,1]$ gives us essentially the same
rule—${\mathcal{N}}^{\operatorname{qr}^{\prime}}_{E}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{(\omega_{v},\omega_{w},\omega_{v,w})\mid\omega_{v,w}<1/4\text{
or }\omega_{v,w}\geq 3/4\\}$ is not meaningfully different from
${\mathcal{N}}^{\operatorname{qr}}_{E}$.

The more fundamental object is the probability distribution that
${\mathcal{N}}$ induces on a set of vertices. That is, if we fix a finite
vertex set $V$ and let ${\mathcal{K}}_{V}$ be the set of graphs on $V$ (with
vertices labeled by the elements of $V$), ${\mathcal{N}}$ induces a
probability distribution $\mu^{\mathcal{N}}_{V}$ on ${\mathcal{K}}_{V}$ where
the probability of $K\in{\mathcal{K}}_{V}$ is precisely the probability that
generating a graph using ${\mathcal{N}}$ by the method described above
produces the graph $K$. (This idea also makes sense, with slightly more care
about measurability, when $V$ is infinite.) For example, when $V$ is finite,
$\mu^{{\mathcal{N}}^{\operatorname{qr}}}_{V}$ is the uniform distribution on
(labeled) graphs on $V$.

We can then say that ${\mathcal{N}}$ and ${\mathcal{N}}^{\prime}$ are
equivalent if $\mu^{\mathcal{N}}_{V}$ and $\mu^{{\mathcal{N}}^{\prime}}_{V}$
are the same for all finite sets $V$.

The example ${\mathcal{N}}^{\operatorname{qr}}$ has a distinctive property:
the variables $\omega_{v}$ and $\omega_{w}$ are not actually used, that is,
${\mathcal{N}}^{\operatorname{qr}}_{E}=[0,1]^{2}\times{\mathcal{H}}^{\operatorname{qr}}_{E}$
for a set ${\mathcal{H}}^{\operatorname{qr}}_{E}$. We call this property _$1$
-independence_, because the $2$-hypergraphon is independent of the unary
variables $\omega_{v},\omega_{w}$.

Complicating matters, a $1$-independent $2$-hypergraphon may be equivalent to
one that is not $1$-independent.

###### Example 1.2.

Consider the rule where
${\mathcal{N}}^{\operatorname{twist}}_{E}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{(\omega_{v},\omega_{w},\omega_{v,w})\mid(\omega_{v}+\omega_{w}+\omega_{v,w})\bmod
1<1/2\\}$.

It is not difficult to check that
$\mu^{{\mathcal{N}}^{\operatorname{twist}}}_{V}$ is the same as
$\mu^{{\mathcal{N}}^{\operatorname{qr}}}_{V}$ for every finite set $V$.

To get a property of the underlying object, instead of just the
representation, we can say that ${\mathcal{N}}$ has $\texttt{Independence}[1]$
if it is equivalent to some $1$-independent set. For graphs, there is not much
to say: any $2$-hypergraphon with $\texttt{Independence}[1]$ is equivalent to
$\\{(\omega_{v},\omega_{w},\omega_{v,w})\mid\omega_{v,w}<p\\}$ for some
$p\in[0,1]$. However we will see that the situation is more complicated when
we consider directed graphs and hypergraphs.

The main topic of this paper is understanding how the quasirandomness
properties of the measures $(\mu^{\mathcal{N}}_{V})_{V}$ relate to whether
$\mu^{\mathcal{N}}_{V}$ has a $1$-independent—or, more generally,
$\ell$-independent—representation. This question was already raised in
Hoover’s original paper [Hoo79], where he asks when ${\mathcal{N}}$ has a
representation omitting some variables. Nevertheless, our result here is the
first general result showing how to take a suitably quasirandom
$(\mu^{\mathcal{N}}_{V})_{V}$ and produce a representation omitting some of
the variables.

To explain our motivation for doing this, we need to consider what happens
when we try generalize the notion of quasirandomness beyond graphs. For the
purposes of the introduction, it will suffice to consider $3$-hypergraphs. We
will let $H$, rather than $E$, be the name of our hypergraph relation. A
$3$-hypergraphon is given by a measurable set
${\mathcal{N}}_{H}\subseteq[0,1]^{7}$. The seven here is the number of non-
empty subsets of a set of three elements333In our general notation below,
where we will consider relations on $d$-tuples, we will write
${\mathcal{N}}_{H}\subseteq{\mathcal{E}}_{k(H)}$. Here $k(H)$ is the arity of
$H$, in this case $3$, and ${\mathcal{E}}_{k(H)}$ will be defined to be
$[0,1]^{r(k(H))}$, where $r(k(H))$ is the set of non-empty subsets of
$[k(H)]\stackrel{{\scriptstyle\text{def}}}{{=}}\\{1,\ldots,k(H)\\}$.. To
generate a $3$-hypergraph on $V$, we select random variables
$(\bm{\omega}_{v})_{v\in V}$,
$(\bm{\omega}_{v,w})_{\\{v,w\\}\in\binom{V}{2}}$, and
$(\bm{\omega}_{v,w,x})_{\\{v,w,x\\}\in\binom{V}{3}}$ uniformly and
independently in $[0,1]$—that is, we choose random variables for each vertex,
each unordered pair of vertices, and each unordered triple of vertices—and we
place a $3$-edge on the triple $\\{v,w,x\\}$ if

$\displaystyle(\bm{\omega}_{v},\bm{\omega}_{w},\bm{\omega}_{x},\bm{\omega}_{v,w},\bm{\omega}_{v,x},\bm{\omega}_{w,x},\bm{\omega}_{v,w,x})$
$\displaystyle\in{\mathcal{N}}_{H}.$

We abbreviate the long tuple by $(\bm{\omega}_{s})_{s\in r(\\{v,w,x\\})}$ to
emphasize that we are indexing the variables by non-empty subsets of the index
set $\\{v,w,x\\}$, where we write $r(V)$ for the set of non-empty subsets of
$V$.

There are a number of ways we might generalize the properties of
${\mathcal{N}}^{\operatorname{qr}}$ to a $3$-hypergraph [LM15b, Tow17,
AHCH+18]. Let us focus just on those ways that ${\mathcal{N}}_{H}$ might be
quasirandom relative to the unary data
$\\{\omega_{v},\omega_{w},\omega_{x}\\}$.

Before stating these, it is helpful to generalize the $\mu^{\mathcal{N}}_{V}$
notation to allow the possibility that some of our random variables have
already been chosen. Given a finite set $V$ and a set $S\subseteq r(V)$, let
us write $\mu^{\mathcal{N}}_{V}[(\omega_{s})_{s\in S}]$ for the distribution
on ${\mathcal{K}}_{V}$ given by taking the given values $(\omega_{s})_{s\in
S}$, randomly choosing all those $\bm{\omega}_{s}$ with $s\in r(V)\setminus S$
and placing $(v,w,x)\in H$ exactly when $((\omega_{s})_{s\in
S},(\bm{\omega}_{s})_{s\in r(V)\setminus S})\in{\mathcal{N}}_{H}$.

Then saying that ${\mathcal{N}}_{H}$ is quasirandom could mean:

  1. (1)

$\mu^{\mathcal{N}}_{\\{v,w,x\\}}[(\omega_{v},\omega_{w},\omega_{x})]$ is
independent of the choice of $\omega_{v},\omega_{w},\omega_{x}$ (except on a
set of measure $0$). This property is called $\texttt{Disc}[1]$, standing for
“discrepancy”, and has been extensively studied [CGW89, KRS02, KNRS10, LM15a,
LM15b, LM17, Tow17, AHCH+18].

  2. (2)

For every finite set $V$, $\mu^{\mathcal{N}}_{V}[(\omega_{v})_{v\in V}]$ is
independent of the choice of $(\omega_{v})_{v\in V}$ (except on a set of
measure $0$). This property was introduced in [CR23] under the name
$\texttt{UCouple}[1]$. (This stands for “unique coupling”, a formulation of
this property introduced in that paper and proven equivalent.)

  3. (3)

There is a representation equivalent to ${\mathcal{N}}$ of the form
$[0,1]^{3}\times{\mathcal{M}}_{H}$. This property is called
$\texttt{Independence}[1]$, and is also introduced in [CR23].

The first two properties can be shown to be representation independent. It is
not hard to see that these are ordered from weakest to strongest. For
$2$-hypergraphons, these are all equivalent444This follows as an easy exercise
from the equivalence $P_{1}(t)\iff P_{1}(4)\iff P_{4}$ of the seminal paper on
graph quasirandomness [CGW89].. For $3$-hypergraphs, however, these notions
are all distinct.

To see that the $\texttt{UCouple}[1]$ is stronger than $\texttt{Disc}[1]$,
consider the following example, slightly modified from one in [CR23, Theorem
3.15].

###### Example 1.3.

Let ${\mathcal{N}}^{\operatorname{disc}}_{H}$ be the set of
$(\omega_{v},\omega_{w},\omega_{x},\omega_{v,w},\omega_{v,x},\omega_{w,x},\omega_{v,w,x})$
such that either:

  * •

$\min\\{\omega_{v},\omega_{w},\omega_{x}\\}<1/2$ and $\omega_{v,w,x}<1/2$, or

  * •

$\min\\{\omega_{v},\omega_{w},\omega_{x}\\}\geq 1/2$ and an odd number of the
values $\omega_{v,w},\omega_{v,x},\omega_{w,x}$ are $<1/2$.

Observe that
$\mu^{{\mathcal{N}}^{\operatorname{disc}}}_{\\{v,w,x\\}}[(\omega_{v},\omega_{w},\omega_{x})]$
always places measure $1/2$ on the case where the $3$-edge appears. However on
a set of four vertices $V=\\{v_{1},v_{2},v_{3},v_{4}\\}$, the distribution is
no longer independent of the $\omega_{v}$. For instance, if $\omega_{v}<1/2$
for all $v\in V$ then
$\mu^{{\mathcal{N}}^{\operatorname{disc}}}_{V}[(\omega_{v})_{v\in V}]$ is the
uniform distribution on ${\mathcal{K}}_{V}$, while if $\omega_{v}\geq 1/2$ for
all $v\in V$ then
$\mu^{{\mathcal{N}}^{\operatorname{disc}}}_{V}[(\omega_{v})_{v\in V}]$ assigns
probability $0$ to any $3$-hypergraph on $V$ with an odd number of edges.

To see that $\texttt{Independence}[1]$ is stronger than $\texttt{UCouple}[1]$,
it helps to first consider the random tournament.

###### Example 1.4.

${\mathcal{N}}^{\operatorname{qrT}}_{\rightarrow}\subseteq[0,1]^{3}$ is the
set of triples $(\omega_{v},\omega_{w},\omega_{v,w})$ such that exactly one of
$\omega_{v}<\omega_{w}$ and $\omega_{v,w}<1/2$ is true.

We write $\rightarrow$ rather than $E$ for the name of our relation because it
is asymmetric: $\mu^{{\mathcal{N}}^{\operatorname{qrT}}}_{V}$ concentrates on
structures where, for any pair $\\{v,w\\}$ of distinct vertices, exactly one
of the edges $(v,w)$ or $(w,v)$ is present—that is, a tournament. In fact, it
is the uniform distribution on tournaments, and further,
$\mu^{{\mathcal{N}}^{\operatorname{qrT}}}_{V}((\omega_{v})_{v\in V})$ is still
the uniform distribution, no matter what the values $(\omega_{v})_{v\in V}$
are, so this has $\texttt{UCouple}[1]$.

On the other hand, any representation of the form
$[0,1]^{2}\times{\mathcal{H}}$ must concentrate on symmetric structures, so
${\mathcal{N}}^{\operatorname{qrT}}$ cannot have $\texttt{Independence}[1]$.
This can be extended to an example on $3$-hypergraphs that similarly has
$\texttt{UCouple}[1]$ but not $\texttt{Independence}[1]$, as is done in [CR23,
Theorem 3.8]: for instance, take ${\mathcal{N}}^{\operatorname{cycle}}_{H}$ to
be the $3$-hypergraphon consisting of triples on which
${\mathcal{N}}^{\operatorname{qrT}}_{\rightarrow}$ would induce a cycle.

The first author and Razborov [CR23] introduced $\texttt{UCouple}[1]$ and
$\texttt{Independence}[1]$, as well as higher-arity generalizations, and
settled most questions about which combinations are possible, leaving only the
question of whether $\texttt{UCouple}[\ell]$ implies
$\texttt{Independence}[\ell^{\prime}]$ when $\ell^{\prime}<\ell$. Our original
motivation was settling this implication: given ${\mathcal{N}}_{H}$ satisfying
$\texttt{UCouple}[\ell]$, we show how to construct an equivalent
representation satisfying $\texttt{Independence}[\ell^{\prime}]$—that is, a
representation that does not use any of the variables $\omega_{s}$ with
$\lvert s\rvert\leq\ell^{\prime}$.

Our approach begins by looking at the proof that the quasirandom tournament
does not have $\texttt{Independence}[1]$. That argument turned on a quirk of
the representation: the binary data in a $2$-hypergraphon is intrinsically
symmetric, forcing us to use the unary data to encode the asymmetry of the
quasirandom tournament. However, like the quasirandom graph, the quasirandom
tournament seems like an essentially binary object, the representation just
has no way to express that.

Facing a similar issue, Crane and the second author proposed [CT18] a modified
representation that adds in an antisymmetric datum at each level. For binary
relations, our modified representation takes ${\mathcal{N}}_{E}$ to be a
subset of $[0,1]^{3}\times{\mathcal{O}}_{\\{v,w\\}}$, where
${\mathcal{O}}_{\\{v,w\\}}$ is just the set of orders of $\\{v,w\\}$ with the
uniform distribution. For example, in this modified representation, we can
take ${\mathcal{N}}^{\operatorname{qrT}}_{\rightarrow}$ to be
$\\{(\omega_{v},\omega_{w},\omega_{v,w},<_{v,w})\mid v<_{v,w}w\\}$. We should
view $(\omega_{v},\omega_{w})$ as the unary data and $(\omega_{v,w},<_{v,w})$
as the binary data, so this gives a representation of the quasirandom
tournament that is independent of the unary data, but only using our modified
representation. We will call this a $\ast$-$1$-independent representation. (We
could, in fact, add the requirement that ${\mathcal{N}}_{E}$ satisfy a
suitable symmetry property in the $\omega_{s}$ variables, essentially
requiring that _all_ the asymmetry be expressed by the $<_{v,w}$ variables,
but since we do not need this restriction, we do not impose it here.)

The bulk of this paper is devoted to showing, as part of Theorem 2.2, that
$\texttt{UCouple}[\ell]$ is _equivalent_ to the existence of a
$\ast$-$\ell$-independent representation. This shows that the quasirandom
tournament is the essential difference between $\texttt{UCouple}[1]$ and
$\texttt{Independence}[1]$, and similarly a “quasirandom orientation”
describes the gap between $\texttt{UCouple}[\ell]$ and
$\texttt{Independence}[\ell]$. We also show, in Corollary 3.8, that we can
easily convert a $\ast$-$\ell$-independent representation into an
$\ell^{\prime}$-independent representation for any $\ell^{\prime}<\ell$
(because we can use any lower arity data, not just the unary data, to simulate
the asymmetry).

Our construction begins with the following observation. When we have a
representation ${\mathcal{N}}_{H}$ and choose a value $\omega_{v}$ for some
vertex $v$, we determine, in some probabilistic sense, how $v$ will behave in
the broader structure—for instance $\omega_{v}$ determines the degree of $v$
(with high probability, up to a small error). However different values of
$\omega_{v}$ might determine the same behavior for $v$; for instance, in
${\mathcal{N}}^{\operatorname{qr}}$, $\omega_{v}$ is entirely ignored—there is
only one “type” of point. In the twisted representation, the same thing is
true: even though the value $\omega_{v}$ appears in the definition of
${\mathcal{N}}^{\operatorname{twist}}_{E}$, it does not ultimately affect the
behavior of $v$: every vertex “looks the same”, no matter what $\omega_{v}$
was. On the other hand, there are exactly two “types” of pairs—the types with
an edge and the types without.

We construct a new representation in which we randomly choose, for each tuple,
the type that tuple should have. To say this slightly more formally, the shape
of our construction will be as follows:

  * •

for each $\ell$, we will define a space $\Lambda_{\ell}$ of types of
$\ell$-tuples,

  * •

for each finite set $A$, we will define a function
$\mathbbm{p}^{\mathcal{N}}_{A}\colon[0,1]^{r(\ell)}\to\Lambda_{\lvert
A\rvert}$ mapping the random data $(\omega_{s})_{s\in r(A)}$ to the type in
$\Lambda_{\lvert A\rvert}$ that ${\mathcal{N}}$ determines on the data
$(\omega_{s})_{s\in r(A)}$.

Under these definitions, ${\mathcal{N}}$ determines a probability measure on
$\Lambda_{1}$, ${\mathcal{N}}$ together with a pair
$(p,p^{\prime})\in\Lambda_{1}^{2}$ determines a probability measure on
$\Lambda_{2}$, and so on. We can identify these with $[0,1]$ by choosing
measure-preserving functions $u\colon[0,1]\to\Lambda_{1}$,
$u_{p,p^{\prime}}\colon[0,1]\to\Lambda_{2}$, and so on. Then our new
representation is given by taking $p_{v}=u(\omega_{v})$,
$p_{v,w}=u_{u(\omega_{v}),u(\omega_{w})}(\omega_{v,w})$, and similarly at
higher arity. We need the data from $<_{u,v}$ to break symmetry: if
$p_{v},p_{w}$ are the same then $\omega_{v,w}$ can determine something about
the unordered set $\\{v,w\\}$, but if it specifies something asymmetric—say,
that exactly one of the two edges $(v,w)$ and $(w,v)$ is present—then our
representation needs the asymmetric datum $<_{v,w}$ to choose among the ways
to resolve the asymmetry.

It would be trivial to just take $\Lambda_{\ell}=[0,1]^{r(\ell)}$ with
$\mathbbm{p}^{\mathcal{N}}_{\ell}$ as the identity. However, since we want to
extract a $\ast$-$\ell$-independent representation from this, we want to show
that $\texttt{UCouple}[\ell]$ implies that there is only one type of
$\ell$-tuple. This will force us to choose a definition in which the type does
not contain unused information—points which behave the same way really should
get the same type.

On the other hand, our notion of type has to contain enough information to
reconstruct $\mu^{\mathcal{N}}_{V}$. Certainly this means that
$\mathbbm{p}^{\mathcal{N}}_{k(H)}({\mathcal{N}}_{H})$ has to be disjoint from
$\mathbbm{p}^{\mathcal{N}}_{k(H)}([0,1]^{r(k(H))}\setminus{\mathcal{N}}_{H})$—that
is, a $k(H)$-tuple that is an edge needs to have a different type from one
that does not have an edge. Slightly more generally, points that lead to
different distributions need to have different types: that is, if
$\mu^{\mathcal{N}}_{V}[(\omega_{s})_{s\in
r(A)}]\neq\mu^{\mathcal{N}}_{V}[(\omega^{\prime}_{s})_{s\in r(A)}]$ for some
finite set $V$ containing $A$, then we need to have
$\mathbbm{p}^{\mathcal{N}}_{A}((\omega_{s})_{s\in
r(A)})\neq\mathbbm{p}^{\mathcal{N}}_{A}((\omega^{\prime}_{s})_{s\in r(A)})$.

This gives our first real candidate for the definition of a type, which we
will call a _weak type_ : we could take
$\mathbbm{p}^{\operatorname{weak},{\mathcal{N}}}_{A}((\omega_{s})_{s\in
r(A)})$ to be $(\mu^{\mathcal{N}}_{A\cup B}[(\omega_{s})_{s\in
r(A)}])_{B\text{ a finite set}}$. That is, two tuples have the same weak type
if, whenever we have a finite set containing that tuple, the distributions of
structures on that set are the same555The reader familiarized with flag
algebras should note that this is almost a flag algebra homomorphism
extension. More specifically, if $\phi$ is the flag algebra homomorphism
corresponding to ${\mathcal{N}}$, then the flag algebra extension
$\bm{\phi^{\sigma}}$ corresponds to the _distribution of the weak type_
$\mathbbm{p}^{\operatorname{weak},{\mathcal{N}}}_{A}((\bm{\omega}_{s})_{s\in
r(A)})$ when $(\bm{\omega}_{s})_{s\in r(A)}$ is picked uniformly at random
conditioned to $\mu^{{\mathcal{N}}_{H}}_{A}[(\bm{\omega}_{s})_{s\in r(A)}]$
being concentrated on $\sigma$..

A standard example shows that this is insufficient.

###### Example 1.5 (Complete Bipartite Graph).

Let ${\mathcal{N}}^{\operatorname{bp}}_{E}$ be the set of
$(\omega_{v},\omega_{w},\omega_{v,w})$ such that exactly one of $\omega_{v}$
and $\omega_{w}$ is $<1/2$.

The random structure generated by
$\mu^{{\mathcal{N}}^{\operatorname{bp}}}_{V}$ is a complete bipartite graph,
with each vertex having equal chance to belong to each of the parts. Since the
parts are unlabeled, there is only one possible value of
$\mu^{{\mathcal{N}}^{\operatorname{bp}}}_{\\{v\\}\cup B}[\omega_{v}]$. However
there is no way to replicate ${\mathcal{N}}^{\operatorname{bp}}_{E}$ with only
one type of point: our construction should have two types of points,
corresponding to the two parts of the bipartition.

Formally, what goes wrong is a failure of _amalgamation_. If we know the types
of $v$ and $w$, they should determine a distribution on the possible types of
the pair $\\{v,w\\}$. That means that if we have two different pairs,
$\omega_{v},\omega_{w}$ and $\omega^{\prime}_{v},\omega^{\prime}_{w}$ that
lead to the same pair of types—that is,
$\mathbbm{p}^{\operatorname{weak},{\mathcal{N}}}_{\\{v\\}}(\omega_{v})=\mathbbm{p}^{\operatorname{weak},{\mathcal{N}}}_{\\{v\\}}(\omega^{\prime}_{v})$
and
$\mathbbm{p}^{\operatorname{weak},{\mathcal{N}}}_{\\{w\\}}(\omega_{w})=\mathbbm{p}^{\operatorname{weak},{\mathcal{N}}}_{\\{w\\}}(\omega^{\prime}_{w})$—then
we need the distribution on types of pairs extending $\omega_{v},\omega_{w}$
to be the same as the distribution on types of pairs extending
$\omega^{\prime}_{v},\omega^{\prime}_{w}$.

With weak types for ${\mathcal{N}}^{\operatorname{bp}}_{E}$, this fails: we
have
$\mathbbm{p}^{\operatorname{weak},{\mathcal{N}}^{\operatorname{bp}}}_{\\{v\\}}(1/4)=\mathbbm{p}^{\operatorname{weak},{\mathcal{N}}^{\operatorname{bp}}}_{\\{v\\}}(3/4)$,
but the pair $(1/4,1/4)$ needs to place measure $1$ on the $2$-type that is
not an edge, while the pair $(1/4,3/4)$ needs to place measure $1$ on the
$2$-type that is an edge.

Our types need more information than weak types. To do this, we want to
replace the distribution $\mu^{\mathcal{N}}_{A\cup B}[(\omega_{s})_{s\in
r(A)}]$ with some pointwise information. We define the _dissociated type_
$\mathbbm{p}^{\operatorname{dsct},{\mathcal{N}}}_{A}((\omega_{s})_{s\in
r(A)})$ to be the family of functions

$\displaystyle(\omega_{s})_{s\in r(B)}\mapsto\mu^{\mathcal{N}}_{A\cup
B}[(\omega_{s})_{s\in r(A)\cup r(B)}],$

where $B$ ranges over finite sets. That is, in order to have the same type,
two sets of values $\\{\omega_{s}\\}_{s\in r(A)}$,
$\\{\omega^{\prime}_{s}\\}_{s\in r(A)}$ not only need to lead to the same
distribution on ${\mathcal{K}}_{A\cup B}$, they need to lead to the same
distribution for each fixed set of data on $B$. (We call these dissociated
types because we look at data on $A$ and $B$ separately, but not at any data
on sets overlapping $A$ and $B$.)666There is a very close analogy to the
situation in model theory: types over a set are not well-behaved. Our solution
is analogous to considering only types over _models_ : allowing data from
additional sets $B$ amounts to letting us name additional fixed elements which
we use, for example, to distinguish the equivalence classes. In the model
theoretic setting, a great deal of work has gone into replacing types over
models with notions of strong types, which add only enough information to
resolve these obstacles. Hrushovski has asked whether there is a way to
transfer the model theoretic approach [Hru22].

This will turn out to be the correct definition for $1$-types, and we can
prove that amalgamation holds going from $1$-types to $2$-types: if
$\mathbbm{p}^{\operatorname{dsct},{\mathcal{N}}}_{\\{v\\}}(\omega_{v})=\mathbbm{p}^{\operatorname{dsct},{\mathcal{N}}}_{\\{v\\}}(\omega^{\prime}_{v})$
and
$\mathbbm{p}^{\operatorname{dsct},{\mathcal{N}}}_{\\{w\\}}(\omega_{w})=\mathbbm{p}^{\operatorname{dsct},{\mathcal{N}}}_{\\{w\\}}(\omega^{\prime}_{w})$
then
$\mathbbm{p}^{\operatorname{dsct},{\mathcal{N}}_{H}}_{\\{v,w\\}}(\omega_{v},\omega_{w},\bm{\omega}_{v,w})$
and
$\mathbbm{p}^{\operatorname{dsct},{\mathcal{N}}_{H}}_{\\{v,w\\}}(\omega^{\prime}_{v},\omega^{\prime}_{w},\bm{\omega}_{v,w})$
have the same distribution when $\bm{\omega}_{v,w}$ is picked uniformly at
random in $[0,1]$.

Unfortunately, the next step of amalgamation fails, as the following example
illustrates.

###### Example 1.6.

Let ${\mathcal{N}}^{\operatorname{odd}}_{H}$ consist of those
$(\omega_{s})_{s\in r(3)}$ such that an odd number of the values
$\omega_{1,2},\omega_{1,3},\omega_{2,3}$ are $<1/2$.

This has a unique dissociated $2$-type777This representation is
$1$-independent, so we will ignore the unary data. We need to show that
$\mathbbm{p}^{\operatorname{dsct},{\mathcal{N}}^{\operatorname{odd}}}_{\\{v,w\\}}(\omega_{v,w})=\mathbbm{p}^{\operatorname{dsct},{\mathcal{N}}^{\operatorname{odd}}}_{\\{v,w\\}}(\omega^{\prime}_{v,w})$
for any $\omega_{v,w},\omega^{\prime}_{v,w}$. Obviously the interesting case
is when, without loss of generality, $\omega_{v,w}<1/2$ while
$\omega^{\prime}_{v,w}\geq 1/2$. In this case, observe that, for any finite
set $B$ and data $\\{\omega_{s}\\}_{s\in r(\\{v,w\\}\cup B)}$, replacing
$\omega_{v,w}$ with $\omega^{\prime}_{v,w}$ and also replacing each
$\omega_{s}$ with $s\cap\\{v,w\\}=\\{v\\}$ with $1/2-\omega_{s}$ will generate
the same structure. This is a measure-preserving transformation on
$\\{\omega_{s}\\}_{s\in r(\\{v,w\\}\cup B)\setminus(r(\\{v,w\\})\cup r(B))}$,
so in particular shows that $\mu^{\mathcal{N}}_{\\{v,w\\}\cup
B}[(\omega_{v,w},(\omega_{s})_{s\in r(B)})]=\mu^{\mathcal{N}}_{\\{v,w\\}\cup
B}[(\omega^{\prime}_{v,w},(\omega_{s})_{s\in r(B)})]$.. However, the $3$-type
is completely determined by the information at the $2$-ary level: for
instance, the values $(1/4,1/4,3/4)$ and $(1/4,3/4,3/4)$ for
$(\omega_{1,2},\omega_{1,3},\omega_{2,3})$ lead to different distributions on
$3$-types.

We conclude that dissociated types still do not contain enough information
when the arity is greater than $1$. Examining the proof that $1$-types can
amalgamate to $2$-types suggested the following strengthening, which we call
_overlapping_ types.
$\mathbbm{p}^{\operatorname{ovlp},{\mathcal{N}}}_{A}((\omega_{s})_{s\in
r(A)})$ to be the family of functions

$\displaystyle(\omega_{s})_{s\in r(A\cup B),A\not\subseteq s\not\subseteq
A}\mapsto\mu^{\mathcal{N}}_{A\cup B}[(\omega_{s})_{s\in r(A\cup
B),A\not\subseteq A},\omega_{A}],$

where $B$ ranges over finite sets. That is, we now consider more pointwise
information, namely all the data which overlaps some _but not all_ of $A$.
(Including any $\omega_{s}$ with $A\subseteq s$ would certainly be too much
information, because it would amount to keeping all the data of the original
representation regarding $A$, leading to failure of uniqueness of $\ell$-types
for $\texttt{UCouple}[\ell]$.) This gives the same definition of a $1$-type,
but adds in more information at higher arity.

This definition works for ${\mathcal{N}}^{\operatorname{odd}}$—there are now
two overlapping $2$-types, as there should be, depending on whether
$\omega_{v,w}$ is $<1/2$ or $\geq 1/2$. We also get some progress towards
amalgamation: overlapping types amalgamate to dissociated types, in any arity.
That is, if we have two $k$-tuples $(\omega_{s})_{s\in
r(k)\setminus\\{[k]\\}}$ missing only the top variable and such that, for each
$(k-1)$-tuple, the overlapping types are the same, then the distribution on
dissociated $k$-types obtained by choosing $\bm{\omega}_{[k]}$ uniformly at
random in $[0,1]$ is the same.

However the overlapping type has too much information. For example,
${\mathcal{N}}^{\operatorname{twist}}$ has many overlapping $2$-types; indeed,
if $(\omega_{v},\omega_{w},\omega_{v,w})$ and
$(\omega^{\prime}_{v},\omega^{\prime}_{w},\omega^{\prime}_{v,w})$ have the
same overlapping $2$-type in ${\mathcal{N}}^{\operatorname{twist}}$ then not
only does $\omega_{v}+\omega_{w}+\omega_{v,w}<1/2$ if and only if
$\omega^{\prime}_{v}+\omega^{\prime}_{w}+\omega^{\prime}_{v,w}<1/2$, but
$\omega_{v}=\omega^{\prime}_{v}$ and $\omega_{w}=\omega^{\prime}_{w}$ as
well888This is because the overlapping $2$-type of $(\omega_{v},\omega_{w})$
knows for each $(\omega_{u},\omega_{v,u},\omega_{w,u})$ whether
$(\omega_{v},\omega_{u},\omega_{v,u})$ and
$(\omega_{w},\omega_{u},\omega_{w,u})$ are edges, so it can subtract out
$\omega_{u}+\omega_{v,u}$ and $\omega_{u}+\omega_{w,u}$ modulo $1$ to
determine $\omega_{v}$ and $\omega_{w}$, respectively.: the overlapping
$2$-type has completely learned the pointwise $1$-ary data, which is
information about the individual points $v$ and $w$ that wasn’t present in the
overlapping $1$-types. To see why this is a failure of amalgamation, note that
since ${\mathcal{N}}^{\operatorname{twist}}$ has a unique overlapping $1$-type
(recall that overlapping and dissociated $1$-types are the same) and since the
overlapping $2$-type knows full pointwise $1$-ary information, changing
$1$-ary point data changes the overlapping $2$-type distribution without
changing the overlapping $1$-types.

One of our guiding principles is that the right definition ought to properly
stratify information: all unary information should show up in the $1$-types,
all binary information in the $2$-types, and so on. But this example shows
that overlapping $2$-types can contain new unary information that wasn’t
already present in the $1$-types.

Our final notion, which we call an _amalgamating type_ , is in between a
dissociated type and an overlapping type. Essentially, we want it to be a
dissociated type together with all the information from the overlapping type
which isn’t really lower arity data. Informally, it is essentially a pair
consisting of the dissociated type together with a function taking any
$(\omega^{\prime}_{s})_{s\in r(A)\setminus\\{A\\}}$ consistent with the
dissociated type to an overlapping type consistent with
$(\omega^{\prime}_{s})_{s\in r(A)\setminus\\{A\\}}$.

That is, the amalgamating type does not know what the overlapping type is,
because that would be too much information. But it knows everything about the
overlapping type that isn’t too much information, because once you tell it the
extra information, it can recover the overlapping type.

In the case of $2$-types, this works roughly as follows. Given
$\omega_{v},\omega_{w},\omega_{v,w}$, we will choose a dissociated $2$-type,
which includes a choice of dissociated $1$-types. We then also want to
remember as much as we can about the overlapping $2$-type while still
forgetting the specific values $\omega_{v},\omega_{w}$. Therefore, we will
remember a recipe that says “for any $\omega^{\prime}_{v},\omega^{\prime}_{w}$
consistent with my $1$-types, I know which overlapping $2$-type I would have
had if my unary data had been $\omega^{\prime}_{v},\omega^{\prime}_{w}$”.

It is not immediately obvious that such a function makes sense, but its
existence almost falls out of the fact that we have amalgamation. Consider any
$\omega^{\prime}_{v},\omega^{\prime}_{w}$ with the same dissociated $1$-types
as $\omega_{v},\omega_{w}$. Amalgamation tells us that the distribution of
dissociated $2$-types is the same. That is, there is a measure-preserving
function999This is not quite correct, but for simplicity, we will assume this
in the introduction only.
$f_{\omega_{v},\omega_{w},\omega^{\prime}_{v},\omega^{\prime}_{w}}\colon[0,1]\to[0,1]$
so that

$\displaystyle\mathbbm{p}^{\operatorname{dsct},{\mathcal{N}}}_{\\{v,w\\}}(\omega_{v},\omega_{w},\omega_{v,w})=\mathbbm{p}^{\operatorname{dsct},{\mathcal{N}}}_{\\{v,w\\}}(\omega^{\prime}_{v},\omega^{\prime}_{w},f_{\omega_{v},\omega_{w},\omega^{\prime}_{v},\omega^{\prime}_{w}}(\omega_{v,w})).$

Therefore we would like to take the amalgamating $2$-type of
$(\omega_{v},\omega_{w},\omega_{v,w})$ to be the function

$\displaystyle(\omega^{\prime}_{v},\omega^{\prime}_{w})\mapsto\mathbbm{p}^{\operatorname{ovlp},{\mathcal{N}}}_{\\{v,w\\}}(\omega^{\prime}_{v},\omega^{\prime}_{w},f_{\omega_{v},\omega_{w},\omega^{\prime}_{v},\omega^{\prime}_{w}}(\omega_{v,w}))$

defined on those $\omega^{\prime}_{v},\omega^{\prime}_{w}$ with the correct
dissociated $1$-types.

There are some additional measure-theoretic formalities to make this work
correctly. For example, we need the functions
$f_{\omega_{v},\omega_{w},\omega^{\prime}_{v},\omega^{\prime}_{w}}$ to satisfy
a cocycle condition
$f_{\omega^{\prime}_{v},\omega^{\prime}_{w},\omega^{\prime\prime}_{v},\omega^{\prime\prime}_{w}}\circ
f_{\omega_{v},\omega_{w},\omega^{\prime}_{v},\omega^{\prime}_{w}}=f_{\omega_{v},\omega_{w},\omega^{\prime\prime}_{v},\omega^{\prime\prime}_{w}}$.
Therefore it is more natural to identify some target space $\Lambda$, obtain
almost everywhere bijective functions
$f_{\omega_{v},\omega_{w}}\colon[0,1]\to\Lambda$, and then set
$f_{\omega_{v},\omega_{w},\omega^{\prime}_{v},\omega^{\prime}_{w}}=f^{-1}_{\omega^{\prime}_{v},\omega^{\prime}_{w}}\circ
f_{\omega_{v},\omega_{w}}$. Some work is needed to identify the target space
in a way that depends measurably on $\omega_{v},\omega_{w}$.

Nevertheless, after solving the measure-theoretic issues, this definition
suffices: amalgamating $(k-1)$-types do determine the distribution of
amalgamating $k$-types (Lemma 9.5(iii)) and $\texttt{UCouple}[\ell]$ implies
that there is only one amalgamating $\ell$-type (Remark 9.3). (Actually, we
are not quite able to prove the second: we need the additional assumption that
the representation is $(\ell-1)$-independent; however this weaker result is
sufficient because we can iterate the construction.)

###  1.1 Organization

In Section 2, we setup basic notation and definitions and formally state our
main theorems formally.

Section 3 is devoted to the concept of $d$-realizations, which allows us to
transform a representation that uses order variables into one that does not
use order variables at the expense of at most one level of independence
(Corollary 3.8).

Section 4 is devoted to extending the characterization of when two
representations are equivalent to cover order variables (Theorem 4.2). As a
consequence, we will derive that if ${\mathcal{N}}$ is
$\ast$-$\ell$-independent, then it must satisfy $\texttt{UCouple}[\ell]$
(Proposition 4.4).

In Section 5, we begin our journey to prove the converse direction, by
formalizing the notions of dissociated and overlapping types and proving
fundamental properties about them, culminating in the proof of uniqueness of
overlapping $\ell$-types in $(\ell-1)$-independent representations
(Proposition 5.8); this uniqueness will be inherited by amalgamating
$\ell$-types later.

In Section 6, we address measurability within the space of
dissociated/overlapping types by constructing a Polish topology over these
spaces, so that equipping the space with the Borel $\sigma$-algebra turns it
into a standard Borel space (Proposition 6.6). This allows us to make sense of
a “random type”.

Section 7 is devoted to proving the aforementioned “defective amalgamation”
(Proposition 7.4), that is, that overlapping types amalgamate to dissociated
types; this will serve as a building block for the final construction of
amalgamating types in Section 9.

However, before that, Section 8 proves a technical measure-theoretic lemma
(Lemma 8.3) that will provide all the measurability and measure-preserving
properties required for the formalization of amalgamating types.

In Section 9, we finally define amalgamating types (Definition 9.2) and prove
that every $\texttt{UCouple}[\ell]$ object has a $\ast$-$\ell$-independent
representation (Proposition 9.7).

In Section 10, we show that every $\texttt{UCouple}[\ell]$ object is the
reduct of an independent coupling of an $\texttt{Independence}[\ell]$ object
with a quasirandom $(\ell+1)$-orientation (Proposition 10.1). This is the
formalization of the statement that “the gap between $\texttt{UCouple}[\ell]$
and $\texttt{Independence}[\ell]$ is a quasirandom orientation”.

We conclude the paper with some final remarks and open problems in Section 11.

More details on the location of the proofs of our main theorems can be found
in Table 1 near the end of Section 2.

##  2 Notation, basic definitions and main theorems

In this section, we establish basic notation and provide all basic definitions
required to formally state our main results.

We denote the set of non-negative integers by $\mathbb{N}$ and the set of
positive integers by $\mathbb{N}_{+}$. For $k\in\mathbb{N}$, we let
$[k]\stackrel{{\scriptstyle\text{def}}}{{=}}\\{1,\ldots,k\\}$. The set of
injective functions from $A$ to $B$ is denoted $(B)_{A}$ and we use the
shorthand $(B)_{k}\stackrel{{\scriptstyle\text{def}}}{{=}}(B)_{[k]}$ when
$k\in\mathbb{N}$. The symmetric group on a set $B$ is denoted $S_{B}$ and we
also use the shorthand $S_{k}\stackrel{{\scriptstyle\text{def}}}{{=}}S_{[k]}$
for $k\in\mathbb{N}$ (we also identify $S_{k}=([k])_{k}$). For sets
$A\subseteq B$, we let $\iota_{A,B}\colon A\to B$ be the inclusion map.

For an injection $\alpha\colon A\to B$, we let $\overline{\alpha}\colon
A\to\operatorname{im}(\alpha)$ be the bijection obtained by restricting the
codomain of $\alpha$ to its image $\operatorname{im}(\alpha)$. As usual, if
$U\subseteq A$, we denote the restriction of $\alpha$ to $U$ by
$\alpha\mathord{|}_{U}\colon U\to B$, but we will also use the notation
$\alpha\mathord{\downarrow}_{U}\colon U\to\alpha(U)$ for the bijection
obtained from $\alpha$ by restricting its domain to $U$ and its codomain to
$\alpha(U)$ (i.e.,
$\alpha\mathord{\downarrow}_{U}\stackrel{{\scriptstyle\text{def}}}{{=}}\overline{\alpha\mathord{|}_{U}}$).
Furthermore, if $A$ and $B$ are both disjoint from a set $V$, we let
$\alpha\mathord{\uparrow}_{V}\colon A\cup V\to B\cup V$ be the extension of
$\alpha$ that acts identically on $V$.

For $\ell\in\mathbb{N}$ and a set $V$, we let
$\binom{V}{\ell}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{A\subseteq
V\mid\lvert A\rvert=\ell\\}$ be the set of subsets of $V$ of size $\ell$, we
let $\binom{V}{>\ell}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{A\subseteq
V\mid\lvert A\rvert>\ell\\}$, we let
$r(V,\ell)\stackrel{{\scriptstyle\text{def}}}{{=}}\bigcup_{1\leq
k\leq\ell}\binom{V}{k}$ and we let
$r(V)\stackrel{{\scriptstyle\text{def}}}{{=}}\bigcup_{\ell\in\mathbb{N}_{+}}\binom{V}{\ell}$
be the set of _finite_ non-empty subsets of $V$.

By Borel space, we mean a standard Borel space, that is, a measurable space
$(X,{\mathcal{B}})$, where $X$ can be equipped with a Polish space structure
such that ${\mathcal{B}}$ is the Borel $\sigma$-algebra of the corresponding
topology; however, we will typically omit ${\mathcal{B}}$ from the notation.
The set of probability measures on a Borel space $X$ is denoted by
${\mathcal{P}}(X)$. By standard probability space, we mean a probability space
whose underlying measurable space is a (standard) Borel space. (Finite or)
countable products of Borel spaces will always be equipped with the product
(Borel) $\sigma$-algebra. Random variables will always be typeset in bold
font. We will denote the Lebesgue measure by $\lambda$ (with a small abuse of
notation, we will use $\lambda$ for the Lebesgue measure in any number of
dimensions and even for a countable product of one-dimensional Lebesgue
measures).

For a relational language ${\mathcal{L}}$ and a predicate symbol
$P\in{\mathcal{L}}$, we denote the _arity_ of $P$ by $k(P)\in\mathbb{N}_{+}$.
A structure $M$ in ${\mathcal{L}}$ is _canonical_ if
$P^{M}\subseteq(V(M))_{k(P)}$ for every $P\in{\mathcal{L}}$, that is, if all
its predicates can only hold in injective tuples. A universal theory is
_canonical_ if all of its models are canonical. Since every universal theory
is isomorphic (via a quantifier-free definition) to a canonical universal
theory (see [CR20, Theorem 2.3], where quantifier-free definitions are called
open interpretations), _all of our structures will be assumed to be canonical
unless explicitly stated otherwise_. We denote the set of (canonical)
structures in ${\mathcal{L}}$ over a set $V$ by
${\mathcal{K}}_{V}[{\mathcal{L}}]$ and for a canonical theory $T$, the set of
models of $T$ over a set $V$ is denoted ${\mathcal{K}}_{V}[T]$; we will omit
${\mathcal{L}}$ and $T$ from the notation when these are clear from the
context. The _pure canonical theory_ in ${\mathcal{L}}$ is the universal
theory $T_{\mathcal{L}}$ whose models are all canonical structures in
${\mathcal{L}}$ (i.e.,
${\mathcal{K}}_{V}[T_{\mathcal{L}}]={\mathcal{K}}_{V}[{\mathcal{L}}]$). When
$V$ is (finite or) countable, we equip ${\mathcal{K}}_{V}$ with the
$\sigma$-algebra generated by cylinder sets, that is, sets of the form

$\displaystyle C(U,K)$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{M\in{\mathcal{K}}_{V}\mid
M\mathord{|}_{U}=K\\}$ (2.1)

for some finite set $U\subseteq V$ and some $N\in{\mathcal{K}}_{U}$; this
makes ${\mathcal{K}}_{V}$ a Borel space.

###  2.1 Contra-variance and equivariance

Throughout this article, we will define several classes of objects $X_{A}$
indexed by countable sets $A$ and most of the time, whenever $\alpha\colon
A\to B$ is an injection, there will a contra-variantly defined map
$\alpha^{*}\colon X_{B}\to X_{A}$ in the sense that
$\operatorname{id}_{A}^{*}$ is the identity map on $X_{A}$ and
$(\beta\mathbin{\circ}\alpha)^{*}=\alpha^{*}\mathbin{\circ}\beta^{*}$ whenever
$\alpha\colon A\to B$ and $\beta\colon B\to C$ are injective.

Formally, what is going on here is that there is a subcategory ${\mathcal{X}}$
of Set whose objects are precisely the $X_{A}$ and there is a contra-variant
functor $F_{{\mathcal{X}}}\colon\textsc{Inj}\to{\mathcal{X}}$ given by
$F_{{\mathcal{X}}}(\alpha)\stackrel{{\scriptstyle\text{def}}}{{=}}\alpha^{*}$,
where Inj is the subcategory of Set whose objects are the countable sets and
whose morphisms are the injective functions. However, since what will be
important is the functor $F_{{\mathcal{X}}}$ rather than the precise morphisms
of ${\mathcal{X}}$, we will abbreviate this abstract non-sense by simply
saying that every $\alpha\colon A\to B$ _contra-variantly_ defines the map
$\alpha^{*}\colon X_{B}\to X_{A}$. Technically, we should add ${\mathcal{X}}$
to the notation $\alpha^{*}$, but since ${\mathcal{X}}$ will be indicated by
the domain and co-domain of the function, we opt for the simpler notation.

A few important examples are the following:

  1. I.

If $Z$ is a set, then every injection $\alpha\colon A\to B$ between countable
sets contra-variantly induces a map $\alpha^{*}\colon Z^{B}\to Z^{A}$ given by

$\displaystyle\alpha^{*}(z)_{t}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}z_{\alpha(t)}\qquad(z\in
Z^{B},t\in A).$

Recalling that $\overline{\alpha}\colon A\to\operatorname{im}(\alpha)$ is the
restriction of the codomain of $\alpha$ to its image and that
$\iota_{\operatorname{im}(\alpha),B}\colon\operatorname{im}(\alpha)\to B$ is
the inclusion map, note that
$\alpha^{*}=\overline{\alpha}^{*}\mathbin{\circ}\iota_{\operatorname{im}(\alpha),B}^{*}$
due to
$\alpha=\iota_{\operatorname{im}(\alpha),B}\mathbin{\circ}\overline{\alpha}$
and contra-variance.

  2. II.

If $Z$ is a set and for each countable set $A$, we have a collection
$c(A)\subseteq 2^{A}$ of subsets of $A$ such that $\alpha(c(A))\subseteq c(B)$
whenever $\alpha\colon A\to B$ is an injection, then there is a contra-
variantly defined $\alpha^{*}\colon Z^{c(B)}\to Z^{c(A)}$ given by

$\displaystyle\alpha^{*}(z)_{C}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}z_{\alpha(C)}\qquad(z\in
Z^{c(B)},C\in c(A)).$

Examples of $c(A)$ with the required property include $r(A)$, $r(A,\ell)$ for
some fixed $\ell$, $\binom{A}{>\ell}$ for some fixed $\ell$, etc.

  3. III.

If $Z$ is a Borel space, then every injection $\alpha\colon A\to B$ between
countable sets contra-variantly induces a map
$\alpha^{*}\colon{\mathcal{P}}(Z^{B})\to{\mathcal{P}}(Z^{A})$, where for
$\mu\in{\mathcal{P}}(Z^{B})$, $\alpha^{*}(\mu)$ is the pushforward measure
under the map $\alpha^{*}\colon Z^{B}\to Z^{A}$ of item (I) above:

$\displaystyle\alpha^{*}(\mu)(U)$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\mu((\alpha^{*})^{-1}(U))=\mu(\\{z\in
Z^{B}\mid\alpha^{*}(z)\in U\\}).$

(Typically, the pushforward construction is co-variant, but since this is the
pushforward of the contra-variant $\alpha^{*}$ of item (I), the composed
functor is contra-variant.)

  4. IV.

For a fixed finite relational language ${\mathcal{L}}$, every injection
$\alpha\colon A\to B$ between countable sets contra-variantly induces a map
$\alpha^{*}\colon{\mathcal{K}}_{B}\to{\mathcal{K}}_{A}$ given by

$\displaystyle P^{\alpha^{*}(M)}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\beta\in
A^{k(P)}\mid\alpha\mathbin{\circ}\beta\in P^{M}\\}\qquad(P\in{\mathcal{L}}),$

where $k(P)\in\mathbb{N}_{+}$ is the arity of $P\in{\mathcal{L}}$, that is,
$\alpha^{*}(M)$ is the unique structure in ${\mathcal{K}}_{A}$ such that
$\alpha$ is an embedding of $M$ in $\alpha^{*}(M)$.

  5. V.

Building on items (III) and (IV), for a finite relational language
${\mathcal{L}}$, an injection $\alpha\colon A\to B$ between countable sets
contra-variantly induces a map
$\alpha^{*}\colon{\mathcal{P}}({\mathcal{K}}_{B})\to{\mathcal{P}}({\mathcal{K}}_{A})$
defined by letting $\alpha^{*}(\mu)$ be the distribution of
$\alpha^{*}(\bm{M})$ for the
$\alpha^{*}\colon{\mathcal{K}}_{B}\to{\mathcal{K}}_{A}$ of item (IV), where
$\bm{M}$ is sampled in ${\mathcal{K}}_{B}$ according to $\mu$. Note that in
this language, an exchangeable distribution is simply a
$\mu\in{\mathcal{P}}({\mathcal{K}}_{A})$ such that $\sigma^{*}(\mu)=\mu$ for
every $\sigma\in S_{A}$.

  6. VI.

In a similar fashion to item (II), suppose we already have contra-variantly
defined $\alpha^{*}\colon X_{B}\to X_{A}$ for every injection $\alpha\colon
A\to B$ and suppose for each countable set $A$, we have a collection
$c(A)\subseteq 2^{A}$ of subsets of $A$ such that $\alpha(c(A))\subseteq c(B)$
whenever $\alpha\colon A\to B$ is an injection.

Then we have a further contra-variantly defined

$\displaystyle\alpha^{*}\colon\prod_{C\in c(B)}X_{C}\to\prod_{C\in c(A)}X_{C}$

given by

$\displaystyle\alpha^{*}(x)_{C}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\alpha\mathord{\downarrow}_{C}^{*}(x_{C})\qquad\left(x\in\prod_{D\in
c(B)}X_{D},C\in c(A)\right).$

(Recall that $\alpha\mathord{\downarrow}_{C}\colon C\to\alpha(C)$ is the
bijective restriction of $\alpha$ to $U$.)

We will also perform several constructions $G_{A}\colon X_{A}\to
X^{\prime}_{A}$, where $X_{A}$ is an object of ${\mathcal{X}}$ and
$X^{\prime}_{A}$ is an object of ${\mathcal{X}}^{\prime}$ and most of the
time, these constructions will be _equivariant_ in the sense that the diagram

${X_{B}}$${X^{\prime}_{B}}$${X_{A}}$${X^{\prime}_{A}}$$\scriptstyle{G_{B}}$$\scriptstyle{\alpha^{*}}$$\scriptstyle{\alpha^{*}}$$\scriptstyle{G_{A}}$

is commutative for every injection $\alpha\colon A\to B$. Formally, what is
going on here is that the collection of maps $(G_{A})_{A}$ is a natural
transformation between the contra-variant functors $F_{{\mathcal{X}}}\to
F_{{\mathcal{X}}^{\prime}}$, but we will abbreviate this abstract non-sense by
simply saying that the construction $G_{A}$ is _equivariant_.

One example of equivariance already appeared in the introduction: for a
$k$-hypergraphon ${\mathcal{N}}\subseteq[0,1]^{r(k)}$ and a countable set $A$,
we implicitly defined a function
$M_{A}^{\mathcal{N}}\colon[0,1]^{r(A)}\to{\mathcal{K}}_{A}$ that constructed a
$k$-hypergraph $M_{A}^{\mathcal{N}}(x)$ with vertex set $A$ from
$x\in[0,1]^{r(A)}$ and ${\mathcal{N}}$ by declaring $e\in\binom{A}{k}$ to be
an edge exactly when $\alpha^{*}(x)\in{\mathcal{N}}$ for
$\alpha^{*}\colon[0,1]^{r(A)}\to[0,1]^{r(k)}$ given by item (II) for any
enumeration $\alpha\in A^{k}$ of $e$. It is straightforward to check that the
construction $M_{A}^{\mathcal{N}}$ is equivariant, that is, the diagram

${{[0,1]}^{r(B)}}$${{\mathcal{K}}_{B}}$${{[0,1]}^{r(A)}}$${{\mathcal{K}}_{A}}$$\scriptstyle{M_{B}^{\mathcal{N}}}$$\scriptstyle{\alpha^{*}}$$\scriptstyle{\alpha^{*}}$$\scriptstyle{M_{A}^{\mathcal{N}}}$

is commutative.

###  2.2 $d$-peons, $d$-Euclidean structures and $d$-theons

For a (finite or) countable set $V$, we let ${\mathcal{O}}_{V}$ be the set of
linear orders on $V$ and if $V$ is finite, we equip ${\mathcal{O}}_{V}$ with
the uniform probability measure, which we denote by $\nu_{V}$. Note that every
injection $\alpha\colon U\to V$ contra-variantly defines
$\alpha^{*}\colon{\mathcal{O}}_{V}\to{\mathcal{O}}_{U}$ by

$\displaystyle u_{1}\mathbin{\alpha^{*}(\lhd)}u_{2}$
$\displaystyle\iff\alpha(u_{1})\lhd\alpha(u_{2})\qquad(u_{1},u_{2}\in U).$

Given further an atomless probability space $\Omega=(X,\mu)$, a countable set
$V$ and $d,\ell\in\mathbb{N}$, we let

$\displaystyle{\mathcal{E}}_{V}^{(d)}(\Omega)$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\prod_{A\in
r(V)}(X\times{\mathcal{O}}_{A}^{d}),$
$\displaystyle{\mathcal{E}}_{V,\ell}^{(d)}(\Omega)$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\prod_{A\in
r(V,\ell)}(X\times{\mathcal{O}}_{A}^{d}),$

be equipped with the product (Borel) $\sigma$-algebra and with the product
measures

$\displaystyle\bigotimes_{A\in
r(V)}\left(\mu\otimes\bigotimes_{i=1}^{d}\nu_{A}\right),$
$\displaystyle\bigotimes_{A\in
r(V,\ell)}\left(\mu\otimes\bigotimes_{i=1}^{d}\nu_{A}\right),$

respectively, which we denote both by $\mu^{(d)}$ by abuse of notation. We
will omit $\Omega$ from the notation when it is clear from context and we will
omit $(d)$ from the notation when $d=0$ (the same convention will be used in
terms defined later that use $\Omega$ and $d$). We will also use the
shorthands ${\mathcal{O}}_{k}$, ${\mathcal{E}}_{k}^{(d)}$ and
${\mathcal{E}}_{k,\ell}^{(d)}$ when $V=[k]$ for $k\in\mathbb{N}$. Finally, we
will naturally identify ${\mathcal{E}}_{V}^{(d)}$ and
${\mathcal{E}}_{V,\ell}^{(d)}$ with the spaces

$\displaystyle\left(\prod_{A\in r(V)}X\right)\times\prod_{A\in
r(V)}{\mathcal{O}}_{A}^{d},$ $\displaystyle\left(\prod_{A\in
r(V,\ell)}X\right)\times\prod_{A\in r(V,\ell)}{\mathcal{O}}_{A}^{d},$

respectively.

Note that every injection $\alpha\colon U\to V$ contra-variantly defines
$\alpha^{*}\colon{\mathcal{E}}_{V}^{(d)}\to{\mathcal{E}}_{U}^{(d)}$ by

$\displaystyle\alpha^{*}(x,{\lhd})$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}(y,{\ll})\qquad\left(x\in{\mathcal{E}}_{V},{\lhd}\in\prod_{A\in
r(V)}{\mathcal{O}}_{A}^{d}\right),$

where

$\displaystyle y_{A}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\alpha^{*}(x)_{A}=x_{\alpha(A)}\qquad(A\in
r(V)),$ $\displaystyle{\ll^{i}_{A}}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\alpha\mathord{\downarrow}_{A}^{*}({\lhd^{i}_{\operatorname{im}(\alpha)}})\qquad(i\in[d],A\in
r(V)).$

An analogous formula yields a contra-variantly defined
$\alpha^{*}\colon{\mathcal{E}}_{V,\ell}^{(d)}\to{\mathcal{E}}_{U,\ell}^{(d)}$.

For $d_{1},d_{2}\in\mathbb{N}$ and two atomless standard probability spaces
$\Omega_{1}$ and $\Omega_{2}$, we will naturally identify the spaces
${\mathcal{E}}_{V}^{(d_{1}+d_{2})}(\Omega_{1}\times\Omega_{2})$ and
${\mathcal{E}}_{V}^{(d_{1})}(\Omega_{1})\times{\mathcal{E}}_{V}^{(d_{2})}(\Omega_{2})$
via the natural bijection that maps
$x\in{\mathcal{E}}_{V}^{(d_{1}+d_{2})}(\Omega_{1}\times\Omega_{2})$ to
$(y,z)\in{\mathcal{E}}_{V}^{(d_{1})}(\Omega_{1})\times{\mathcal{E}}_{V}^{(d_{2})}(\Omega_{2})$,
where for every $A\in r(V)$, $y_{A}$ is the projection of $x_{A}$ to
$\Omega_{1}$ along with the first $d_{1}$ orders and $z_{A}$ is the projection
of $x_{A}$ to $\Omega_{2}$ along with the last $d_{2}$ orders.

The remainder of the section is devoted to generalizing the notions of theons
of [CR20] and the associated quasirandomness notions of [CR23] to include the
extra order variables of [CT18].

Let $\Omega=(X,\mu)$ be an atomless probability space, let
$d,\ell\in\mathbb{N}$, let ${\mathcal{L}}$ be a relational language and
$P\in{\mathcal{L}}$.

A _(Borel) $d$-$P$-on_ over $\Omega$ is a measurable subset ${\mathcal{N}}$ of
${\mathcal{E}}_{k(P)}^{(d)}(\Omega)$. We say that ${\mathcal{N}}$ is _$\ell$
-independent_ if
${\mathcal{N}}={\mathcal{E}}_{k(P),\ell}^{(d)}\times{\mathcal{H}}$ for some
${\mathcal{H}}\subseteq\prod_{A\in\binom{[k(P)]}{>\ell}}(X\times{\mathcal{O}}_{A}^{d})$.
Dually, the _rank_ of ${\mathcal{N}}$ (denoted
$\operatorname{rk}({\mathcal{N}})$) is the minimum $\ell\in\mathbb{N}$ such
that
${\mathcal{N}}={\mathcal{H}}\times\prod_{A\in\binom{[k(P)]}{>\ell}}(X\times{\mathcal{O}}_{A}^{d})$
for some ${\mathcal{H}}\subseteq{\mathcal{E}}_{k(P),\ell}^{(d)}$.

A _(Borel) $d$-Euclidean structure_ in ${\mathcal{L}}$ over $\Omega$ is a
function ${\mathcal{N}}$ that maps each $P\in{\mathcal{L}}$ to a $d$-$P$-on
${\mathcal{N}}_{P}\subseteq{\mathcal{E}}_{k(P)}^{(d)}(\Omega)$. We say that
${\mathcal{N}}$ is _$\ell$ -independent_ if all of its $d$-peons
${\mathcal{N}}_{P}$ are $\ell$-independent. Dually, the _rank_ of
${\mathcal{N}}$ is
$\operatorname{rk}({\mathcal{N}})\stackrel{{\scriptstyle\text{def}}}{{=}}\max\\{\operatorname{rk}({\mathcal{N}}_{P})\mid
P\in{\mathcal{L}}\\}\cup\\{0\\}$.

For a $d$-Euclidean structure in ${\mathcal{L}}$ over $\Omega$ and a countable
set $V$, we let
$M^{\mathcal{N}}_{V}\colon{\mathcal{E}}_{V}^{(d)}\to{\mathcal{K}}_{V}$ be the
(Borel) measurable function given by

$\displaystyle P^{M^{\mathcal{N}}_{V}(x)}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\alpha\in(V)_{k(P)}\mid\alpha^{*}(x)\in{\mathcal{N}}_{P}\\}\qquad(x\in{\mathcal{E}}_{V}^{(d)},P\in{\mathcal{L}}),$

that is, the predicate $P$ holds on an injective tuple $\alpha$ in
$M^{\mathcal{N}}_{V}(x)$ exactly when the point
$\alpha^{*}(x)\in{\mathcal{E}}_{k(P)}^{(d)}$ is an element of
${\mathcal{N}}_{P}$. It is straightforward to check that $M^{\mathcal{N}}_{V}$
is equivariant in the sense of Section 2.1.

We also let
$\mu^{\mathcal{N}}_{V}\stackrel{{\scriptstyle\text{def}}}{{=}}(M^{\mathcal{N}}_{V})_{*}(\mu^{(d)})$
be the pushforward probability measure of $\mu^{(d)}$ by
$M^{\mathcal{N}}_{V}$, that is, if $\bm{x}\sim\mu^{(d)}$ is picked in
${\mathcal{E}}_{V}^{(d)}$ according to $\mu^{(d)}$, then
$\mu^{\mathcal{N}}_{V}$ is the distribution of $M^{\mathcal{N}}_{V}(\bm{x})$.
The fact that the distribution of $\bm{x}$ is $S_{V}$-invariant and
$M^{\mathcal{N}}_{V}$ is equivariant implies that the distribution
$\mu^{\mathcal{N}}_{V}$ is $S_{V}$-invariant (i.e., _exchangeable_). Obviously
$\mu^{\mathcal{N}}_{V}$ is also _local_ , that is, for $A,B\subseteq V$
disjoint, $M^{\mathcal{N}}_{V}(\bm{x})\mathord{|}_{A}$ is independent from
$M^{\mathcal{N}}_{V}(\bm{x})\mathord{|}_{B}$.

For a finite (canonical) ${\mathcal{L}}$-structure $K$, we let

$\displaystyle T_{\operatorname{ind}}(K,{\mathcal{N}})$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}(M^{\mathcal{N}}_{V(K)})^{-1}(K)\stackrel{{\scriptstyle\text{def}}}{{=}}\\{x\in{\mathcal{E}}_{V(K)}^{(d)}\mid
M^{\mathcal{N}}_{V(K)}(x)=K\\},$ $\displaystyle
t_{\operatorname{ind}}(K,{\mathcal{N}})$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\mu^{(d)}(T_{\operatorname{ind}}(K,{\mathcal{N}}))=\mu^{\mathcal{N}}_{V(K)}(\\{K\\}),$
$\displaystyle\phi_{\mathcal{N}}(K)$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{\lvert
K\rvert!}{\lvert\operatorname{Aut}(K)\rvert}t_{\operatorname{ind}}(K,{\mathcal{N}})=\mu^{\mathcal{N}}_{V(K)}(\\{K^{\prime}\in{\mathcal{K}}_{V(K)}\mid
K^{\prime}\cong K\\}).$

Exchangeability implies that $t_{\operatorname{ind}}(K,{\mathcal{N}})$ and
$\phi_{\mathcal{N}}(K)$ depends only on the isomorphism-type of $K$.

For a canonical theory $T$, a _(Borel) $d$-$T$-on_ is a $d$-Euclidean
structure ${\mathcal{N}}$ such that
$t_{\operatorname{ind}}(K,{\mathcal{N}})=0$ whenever $K$ is _not_ a model of
$T$. Let ${\mathcal{N}}_{1}$ and ${\mathcal{N}}_{2}$ be a $d_{1}$-Euclidean
structure over $\Omega_{1}$ and a $d_{2}$-Euclidean structure over
$\Omega_{2}$, respectively, both in ${\mathcal{L}}$. We say that
${\mathcal{N}}_{1}$ is _equivalent_ to ${\mathcal{N}}_{2}$ if
$\mu^{{\mathcal{N}}_{1}}_{V}=\mu^{{\mathcal{N}}_{2}}_{V}$ for every countable
set $V$ (this is easily summarized as
$\phi_{{\mathcal{N}}_{1}}=\phi_{{\mathcal{N}}_{2}}$).

The set of functions

$\displaystyle\operatorname{Hom}^{+}({\mathcal{A}}[T],\mathbb{R})$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\phi_{\mathcal{N}}\mid{\mathcal{N}}\text{
is a $0$-$T$-on}\land d\in\mathbb{N}\\}$

was completely characterized in the theory of flag algebras [Raz07] (see also
[CR20] for the connection to theons). Since the precise characterization will
not be important for us, the unfamiliarized reader can think of this as a set
of representatives of each equivalence class of $0$-$T$-ons. Furthermore,
since elements $\operatorname{Hom}^{+}({\mathcal{A}}[T],\mathbb{R})$ encode
limits of convergent sequences of finite models of $T$, we will refer to them
as _limits_ of $T$ or as limits in ${\mathcal{L}}$ when we do not want to
specify $T$. As one might expect, every $d$-$T$-on ${\mathcal{N}}$ is
equivalent to some $0$-$T$-on ${\mathcal{N}}^{\prime}$, but it will be
important to produce ${\mathcal{N}}^{\prime}$ from ${\mathcal{N}}$ preserving
as much independence as possible.

We say that two $d$-Euclidean structures ${\mathcal{N}}^{1}$ and
${\mathcal{N}}^{2}$ in the same language ${\mathcal{L}}$ over the same space
$\Omega=(X,\mu)$ are _almost everywhere (a.e.) equal_ if
$\mu^{(d)}({\mathcal{N}}^{1}_{P}\mathbin{\triangle}{\mathcal{N}}^{2}_{P})=0$
for every $P\in{\mathcal{L}}$; in particular, this implies that they represent
the same limit: $\phi_{{\mathcal{N}}^{1}}=\phi_{{\mathcal{N}}^{2}}$.

We say that a limit $\phi$ is $\ell$-independent if there exists a
$0$-Euclidean structure ${\mathcal{N}}$ such that $\phi_{\mathcal{N}}=\phi$;
this property is also denoted $\texttt{Independence}[\ell]$. We say that a
limit $\phi$ is $\ast$-$\ell$-independent if there exist $d\in\mathbb{N}$ and
a $d$-Euclidean structure ${\mathcal{N}}$ such that $\phi_{\mathcal{N}}=\phi$.
These are not equivalent: our main result Theorem 2.2 says that
$\ast$-$\ell$-independence is equivalent to the property
$\texttt{UCouple}[\ell]$ defined below, which is strictly weaker than
$\texttt{Independence}[\ell]$ (see [CR23]).

Dually, the _rank_ of a limit $\phi$ is the minimum rank of a $0$-$T$-on
${\mathcal{N}}$ such that $\phi=\phi_{\mathcal{N}}$. We could define the
$\ast$-rank by allowing $d$-$T$-ons, but as we will see in Corollary 3.9, such
a definition would be equivalent to the usual rank.

Recall that a _quantifier-free definition_ (or _open interpretation_) from a
canonical theory $T_{1}$ in ${\mathcal{L}}_{1}$ to a canonical theory $T_{2}$
in ${\mathcal{L}}_{2}$ is a function $I$ that maps predicate symbols
$P\in{\mathcal{L}}_{1}$ to quantifier-free formulas
$I(P)(x_{1},\ldots,x_{k(P)})$ in ${\mathcal{L}}_{2}$ so that axioms of $T_{1}$
are mapped to theorems of $T_{2}$ when we declare $I$ to commute with logical
connectives; such a quantifier-free definition is denoted as $I\colon
T_{1}\leadsto T_{2}$. For a set $V$, a quantifier-free definition naturally
defines a map
$I^{*}_{V}\colon{\mathcal{K}}_{V}[T_{2}]\to{\mathcal{K}}_{V}[T_{1}]$ given
by101010The $\ast$ in $I^{*}_{V}$ is to denote a different kind of contra-
variance. Namely, this is a contra-variant functor from the category Int of
quantifier-free definitions to Set, see [CR20]. The next two defined maps,
which will be denoted by $I^{*}$ also have similar contra-variances as
functors from Int.

$\displaystyle P^{I^{*}_{V}(M)}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}I(P)(M)\stackrel{{\scriptstyle\text{def}}}{{=}}\\{\alpha\in(V)_{k(P)}\mid
M\vDash I(P)(\alpha)\\}\qquad(P\in{\mathcal{L}}),$

that is, the predicate $P\in{\mathcal{L}}_{1}$ holds on a tuple $\alpha$ in
$I^{*}_{V}(M)$ exactly when the formula $I(P)$ holds on $\alpha$ in $M$. It is
straightforward to check that $I^{*}_{V}$ is equivariant in the sense of
Section 2.1. Similarly, $I\colon T_{1}\leadsto T_{2}$ also naturally defines a
map
$I^{*}\colon\operatorname{Hom}^{+}({\mathcal{A}}[T_{2}],\mathbb{R})\to\operatorname{Hom}^{+}({\mathcal{A}}[T_{1}],\mathbb{R})$
given by

$\displaystyle I^{*}(\phi)(M)$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\sum\\{\phi(N)\mid
N\in{\mathcal{M}}_{V(M)}[T_{2}]\land I^{*}_{V(M)}(N)\cong M\\},$

for every finite ${\mathcal{L}}_{1}$-structure $M$, where
${\mathcal{M}}_{V(M)}[T_{2}]$ is the set of models of $T_{2}$ over $V(M)$ _up
to isomorphism_ (in [Raz07, CR20] $I^{*}(\phi)$ is denoted as $\phi^{I}$).
From a probabilistic view, we have
$I^{*}(\phi_{\mathcal{N}})=\phi_{\mathcal{H}}$ exactly when for every
countable set $V$, if $\bm{M}$ is sampled at random according to
$\mu^{\mathcal{N}}_{V}$, then $I^{*}_{V}(\bm{M})\sim\mu^{\mathcal{H}}_{V}$.

In turn, there is also a naturally induced map over $d$-Euclidean structures
${\mathcal{N}}$ over $\Omega=(X,\mu)$ defined as follows. First, for a
quantifier-free formula $F(x_{1},\ldots,x_{n})$, we define the _truth set_
$T(F,{\mathcal{N}})\subseteq{\mathcal{E}}_{n}^{(d)}(\Omega)$ as follows:

  * •

if $F$ is $P(x_{i_{1}},\ldots,x_{i_{k}})$ and $i_{1},\ldots,i_{k}$ are not
pairwise distinct or $F$ is $x_{i}=x_{j}$ for $i\neq j$, then
$T(F,{\mathcal{N}})\stackrel{{\scriptstyle\text{def}}}{{=}}\varnothing$.

  * •

$T(x_{i}=x_{i})\stackrel{{\scriptstyle\text{def}}}{{=}}{\mathcal{E}}_{n}^{(d)}(\Omega)$.

  * •

if $F$ is $P(x_{i_{1}},\ldots,x_{i_{k}})$ and $i_{1},\ldots,i_{k}$ are
pairwise distinct, then
$T(F,{\mathcal{N}})\stackrel{{\scriptstyle\text{def}}}{{=}}(i^{*})^{-1}({\mathcal{N}}_{P})$,
where we view $i$ as an injection $[k]\to[n]$.

  * •

$T(\mathord{-},{\mathcal{N}})$ commutes with propositional connectives (e.g.,
we have $T(F_{1}\lor
F_{2},{\mathcal{N}})\stackrel{{\scriptstyle\text{def}}}{{=}}T(F_{1},{\mathcal{N}})\cup
T(F_{2},{\mathcal{N}})$ and $T(\neg
F,{\mathcal{N}})\stackrel{{\scriptstyle\text{def}}}{{=}}{\mathcal{E}}_{n}^{(d)}(\Omega)\setminus
T(F,{\mathcal{N}})$).

Then for a $d$-Euclidean structure ${\mathcal{N}}$ over $\Omega=(X,\mu)$, we
define the $d$-Euclidean structure $I^{*}({\mathcal{N}})$ over
$\Omega=(X,\mu)$ by

$\displaystyle I^{*}({\mathcal{N}})_{P}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}T(I(P),{\mathcal{N}})\qquad(P\in{\mathcal{L}}_{1}).$
(2.2)

(In [CR20, Remark 6], this was defined only for the $d=0$ case and used the
notation $I({\mathcal{N}})$ instead.) These maps are connected to each other
in the sense that $\phi_{I^{*}({\mathcal{N}})}=I^{*}(\phi_{\mathcal{N}})$
(this is easily checked by noting that if $\bm{M}$ is sampled at random
according to $\mu^{\mathcal{N}}_{V}$, then
$I^{*}_{V}(\bm{M})\sim\mu^{I^{*}({\mathcal{N}})}_{V}$).

A particularly important case of quantifier-free definitions are _reducts_
111111In [CR20, CR23], these were called structure-erasing interpretations.,
i.e., quantifier-free definitions of the form $I\colon
T_{{\mathcal{L}}^{\prime}}\leadsto T_{\mathcal{L}}$ in which
${\mathcal{L}}^{\prime}\subseteq{\mathcal{L}}$ and $I$ acts identically on
predicate symbols of ${\mathcal{L}}^{\prime}$. In this case,
$I^{*}_{V}\colon{\mathcal{K}}_{V}[{\mathcal{L}}]\to{\mathcal{K}}_{V}[{\mathcal{L}}^{\prime}]$
is simply the reduct map
$M\mathord{|}_{{\mathcal{L}}^{\prime}}\stackrel{{\scriptstyle\text{def}}}{{=}}I^{*}_{V}(M)$
and we also abbreviate
$\phi\mathord{|}_{{\mathcal{L}}^{\prime}}\stackrel{{\scriptstyle\text{def}}}{{=}}I^{*}(\phi)$.
It is straightforward to check that if ${\mathcal{N}}$ is a $d$-Euclidean
structure in ${\mathcal{L}}$, then
$\phi_{\mathcal{N}}\mathord{|}_{{\mathcal{L}}^{\prime}}=\phi_{{\mathcal{N}}\mathord{|}_{{\mathcal{L}}^{\prime}}}$,
where ${\mathcal{N}}\mathord{|}_{{\mathcal{L}}^{\prime}}$ is the $d$-Euclidean
structure in ${\mathcal{L}}^{\prime}$ obtained from ${\mathcal{N}}$ by simply
restricting it to ${\mathcal{L}}^{\prime}$ (which is a.e. equal to
$I^{*}({\mathcal{N}})$).

Given two theories $T_{1}$ and $T_{2}$ in ${\mathcal{L}}_{1}$ and
${\mathcal{L}}_{2}$, respectively, the _disjoint union theory_ is the theory
$T_{1}\cup T_{2}$ in the disjoint union language
${\mathcal{L}}_{1}\mathbin{\stackrel{{\scriptstyle\cdot}}{{\cup}}}{\mathcal{L}}_{2}$
that contains both axioms of $T_{1}$ and $T_{2}$ (i.e., its models are models
of $T_{1}$ and $T_{2}$ on the same vertex set). With a small abuse of
notation, for $i\in[2]$, we also call the quantifier-free definitions of the
form $I\colon T_{i}\leadsto T_{1}\cup T_{2}$ that act identically on predicate
symbols of ${\mathcal{L}}_{i}$ _reducts_ and use the notation
$\phi\mathord{|}_{T_{i}}$ for $\phi\mathord{|}_{{\mathcal{L}}_{i}}$ when
$\phi\in\operatorname{Hom}^{+}({\mathcal{A}}[T_{1}\cup T_{2}],\mathbb{R})$.

A _coupling_ of two limits $\phi_{1}$ and $\phi_{2}$ in ${\mathcal{L}}_{1}$
and ${\mathcal{L}}_{2}$, respectively, is a limit $\psi$ in the disjoint union
language
${\mathcal{L}}_{1}\mathbin{\stackrel{{\scriptstyle\cdot}}{{\cup}}}{\mathcal{L}}_{2}$
such that $\psi\mathord{|}_{{\mathcal{L}}_{1}}=\phi_{1}$ and
$\psi\mathord{|}_{{\mathcal{L}}_{2}}=\phi_{2}$. For example, if
${\mathcal{N}}^{1}$ and ${\mathcal{N}}^{2}$ are $d$-Euclidean structures in
${\mathcal{L}}_{1}$ and ${\mathcal{L}}_{2}$, respectively, over the same
$\Omega$ with $\phi_{{\mathcal{N}}^{1}}=\phi_{1}$ and
$\phi_{{\mathcal{N}}^{2}}=\phi_{2}$, then the (disjoint) union function
${\mathcal{N}}^{1}\mathbin{\stackrel{{\scriptstyle\cdot}}{{\cup}}}{\mathcal{N}}^{2}$
is a $d$-Euclidean structure in
${\mathcal{L}}_{1}\mathbin{\stackrel{{\scriptstyle\cdot}}{{\cup}}}{\mathcal{L}}_{2}$
over $\Omega$ such that
$\phi_{{\mathcal{N}}^{1}\mathbin{\stackrel{{\scriptstyle\cdot}}{{\cup}}}{\mathcal{N}}^{2}}$
is a coupling of $\phi_{1}$ and $\phi_{2}$.

The _independent coupling_ of two limits $\phi_{1}$ and $\phi_{2}$ in
${\mathcal{L}}_{1}$ and ${\mathcal{L}}_{2}$, respectively is the limit
$\phi_{1}\otimes\phi_{2}$ in
${\mathcal{L}}_{1}\mathbin{\stackrel{{\scriptstyle\cdot}}{{\cup}}}{\mathcal{L}}_{2}$
given by

$\displaystyle(\phi_{1}\otimes\phi_{2})(M)$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{\lvert\operatorname{Aut}(M\mathord{|}_{{\mathcal{L}}_{1}})\rvert\cdot\lvert\operatorname{Aut}(M\mathord{|}_{{\mathcal{L}}_{2}})\rvert}{\lvert\operatorname{Aut}(M)\rvert\cdot\lvert
M\rvert!}\cdot\phi_{1}(M\mathord{|}_{{\mathcal{L}}_{1}})\cdot\phi_{2}(M\mathord{|}_{{\mathcal{L}}_{2}}).$

A more geometric description of the independent coupling is as follows: let
${\mathcal{N}}^{1}$ be a $d_{1}$-Euclidean structure in ${\mathcal{L}}_{1}$
over $\Omega_{1}$ and ${\mathcal{N}}^{2}$ be a $d_{2}$-Euclidean structure in
${\mathcal{L}}_{2}$ over $\Omega_{2}$. The _independent coupling_ of
${\mathcal{N}}^{1}$ and ${\mathcal{N}}^{2}$ is the $(d_{1}+d_{2})$-Euclidean
structure in
${\mathcal{L}}_{1}\mathbin{\stackrel{{\scriptstyle\cdot}}{{\cup}}}{\mathcal{L}}_{2}$
over $\Omega_{1}\times\Omega_{2}$ given by

$\displaystyle({\mathcal{N}}^{1}\otimes{\mathcal{N}}^{2})_{P}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{(x^{1},x^{2})\in{\mathcal{E}}_{k(P)}^{(d_{1})}(\Omega_{1})\times{\mathcal{E}}_{k(P)}^{(d_{2})}(\Omega_{2})\mid
x^{i}\in{\mathcal{N}}^{i}_{P}\\}\qquad(P\in{\mathcal{L}}_{i},i\in[2]).$

It is straightforward to check that for every finite
${\mathcal{L}}_{1}\mathbin{\stackrel{{\scriptstyle\cdot}}{{\cup}}}{\mathcal{L}}_{2}$-structure
$M$, we have

$\displaystyle
t_{\operatorname{ind}}(M,{\mathcal{N}}^{1}\otimes{\mathcal{N}}^{2})$
$\displaystyle=t_{\operatorname{ind}}(M\mathord{|}_{{\mathcal{L}}_{1}},{\mathcal{N}}^{1})\cdot
t_{\operatorname{ind}}(M\mathord{|}_{{\mathcal{L}}_{2}},{\mathcal{N}}^{2}),$

from which one gets
$\phi_{{\mathcal{N}}^{1}\otimes{\mathcal{N}}^{2}}=\phi_{{\mathcal{N}}^{1}}\otimes\phi_{{\mathcal{N}}^{2}}$.

A more probabilistic view of couplings and independent couplings is as
follows: $\phi_{\mathcal{H}}$ is a coupling of $\phi_{{\mathcal{N}}^{1}}$ and
$\phi_{{\mathcal{N}}^{2}}$ if for every countable set $V$, if $\bm{N}$ is
sampled according to $\mu^{\mathcal{H}}_{V}$, then
$\bm{N}\mathord{|}_{{\mathcal{L}}_{1}}\sim\mu^{{\mathcal{N}}^{1}}_{V}$ and
$\bm{N}\mathord{|}_{{\mathcal{L}}_{2}}\sim\mu^{{\mathcal{N}}^{2}}_{V}$; if
further $\bm{N}\mathord{|}_{{\mathcal{L}}_{1}}\sim\mu^{{\mathcal{N}}^{1}}_{V}$
and $\bm{N}\mathord{|}_{{\mathcal{L}}_{2}}\sim\mu^{{\mathcal{N}}^{2}}_{V}$ are
independent, then $\phi_{\mathcal{H}}$ is the independent coupling of
$\phi_{{\mathcal{N}}^{1}}$ and $\phi_{{\mathcal{N}}^{2}}$.

Two limits $\phi_{1}$ and $\phi_{2}$ are _uniquely coupleable_ if there exists
exactly one coupling of $\phi_{1}$ and $\phi_{2}$ (which must be the
independent coupling $\phi_{1}\otimes\phi_{2}$).

We say that a limit $\phi$ is _uniquely $\ell$-coupleable_ if for every limit
$\psi$ with $\operatorname{rk}(\psi)\leq\ell$, $\phi$ and $\psi$ are uniquely
coupleable; this property is also denoted $\texttt{UCouple}[\ell]$. It was
shown in [CR23, Theorem 3.10] that $\phi\in\texttt{UCouple}[\ell]$ is
equivalent to the property that for some (equivalently, every) $0$-Euclidean
structure ${\mathcal{N}}$ over $\Omega=(X,\mu)$ with
$\phi_{\mathcal{N}}=\phi$, if $V$ is a countable set and $\bm{x}$ is picked at
random in ${\mathcal{E}}_{V}$ according to $\mu$, then
$M^{\mathcal{N}}_{V}(\bm{x})$ is independent (as a random variable) from
$(\bm{x}_{A}\mid A\in r(V,\ell))$. As we will see in Proposition 4.4, the same
characterization holds if we let ${\mathcal{N}}$ be a $d$-Euclidean structure
with $\phi_{\mathcal{N}}=\phi$ for $d\in\mathbb{N}$. From this
characterization, it is obvious that
$\texttt{Independence}[\ell]\implies\texttt{UCouple}[\ell]$ (see [CR23,
Theorem 3.2])

Furthermore, it was shown in [CR23, Theorem 3.3] that both
$\texttt{Independence}[\ell]$ and $\texttt{UCouple}[\ell]$ are natural
properties in the sense that if
$\phi\in\operatorname{Hom}^{+}({\mathcal{A}}[T],\mathbb{R})$ satisfies the
property and $I\colon T^{\prime}\leadsto T$ is a quantifier-free definition,
then $I^{*}(\phi)$ also satisfies the property. Moreover, these properties are
also preserved under independent couplings [CR23, Theorem 3.4] in the sense
that if $\phi_{1}$ and $\phi_{2}$ both have the property then
$\phi_{1}\otimes\phi_{2}$ also has the property.

We end this section with a high-arity generalization of the quasirandom
tournament of Example 1.4.

###### Definition 2.1.

For $k\in\mathbb{N}_{+}$, the _theory of $k$-orientations_ is the theory
$T_{k\operatorname{-Orientation}}$ in a language ${\mathcal{L}}$ containing a
single predicate symbol $P$, whose arity is
$k(P)\stackrel{{\scriptstyle\text{def}}}{{=}}k$, and with axioms

$\displaystyle\forall x_{1},\ldots,x_{k},(P(x_{1},\ldots,x_{k})\to\neg
P(x_{\sigma(1)},\ldots,x_{\sigma(k)}))\qquad(\sigma\in
S_{k}\setminus\\{\operatorname{id}_{k}\\}),$ $\displaystyle\forall
x_{1},\ldots,x_{k},\left(\bigwedge_{i\neq j}x_{i}\neq
x_{j}\to\bigvee_{\sigma\in S_{k}}P(x_{\sigma(1),\ldots,\sigma(k)})\right),$

that is, for each $k$-set $A$ of vertices, the predicate $P$ holds in exactly
one of the (injective) $k$-tuples $\alpha$ with $\operatorname{im}(\alpha)=A$.

The _quasirandom $k$-orientation_ is the limit
$\phi^{k\operatorname{-qrO}}\in\operatorname{Hom}^{+}({\mathcal{A}}[T_{k\operatorname{-Orientation}}],\mathbb{R})$
is the limit encoded by the ($(k-1)$-independent)
$1$-$T_{k\operatorname{-Orientation}}$-on
${\mathcal{N}}^{k\operatorname{-qrO}}$ over any space $\Omega=(X,\mu)$ given
by

$\displaystyle{\mathcal{N}}^{k\operatorname{-qrO}}_{P}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{(x,{\lhd})\in{\mathcal{E}}_{k}^{(1)}(\Omega)\mid{\lhd}_{[k]}={\leq}\\},$
(2.3)

where ${\leq}\in{\mathcal{O}}_{k}$ is the usual order on $[k]$. Note that
$\mu^{\mathcal{N}}_{V}$ consists of the distribution in which each $k$-set is
given a uniformly at random orientation independently.

Alternatively, we will see in Remark 3.7 that
$\phi^{k\operatorname{-qrO}}=\phi_{{\mathcal{H}}^{k\operatorname{-qrO}}}$ for
the $0$-$T_{k\operatorname{-Orientation}}$-on
${\mathcal{H}}^{k\operatorname{-qrO}}$ over $\Omega=([0,1),\lambda)$ given by

$\displaystyle{\mathcal{H}}^{k\operatorname{-qrO}}_{P}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{x\in{\mathcal{E}}_{k}^{(0)}(\Omega)\mid\sigma_{x}=\gamma_{\lfloor
x_{[k]}\cdot k!\rfloor+1}\\},$ (2.4)

where $\sigma_{x}\in S_{k}$ is defined when $x$ has distinct coordinates as
the unique permutation such that

$\displaystyle
x_{[k]\setminus\\{\sigma^{-1}_{x}(1)\\}}<x_{[k]\setminus\\{\sigma^{-1}_{x}(2)\\}}<\cdots<x_{[k]\setminus\\{\sigma^{-1}_{x}(k)\\}},$

and defined arbitrarily (but measurably) when $x$ has repeated coordinates and
$\gamma_{1},\ldots,\gamma_{k!}$ is some fixed enumeration of $S_{k}$.

This latter representation shows that $\phi^{k\operatorname{-qrO}}$ satisfies
$\texttt{Independence}[k-2]$.

It is straightforward to check that the quasirandom $k$-orientation
$\phi^{k\operatorname{-qrO}}$ can be obtained as a quantifier-free definition
of the $(\Theta,p)$-quasirandom homomorphisms in $S_{k}$-action theories
defined in [CR23, Definition 2.9], which in particular implies that it
satisfies $\texttt{UCouple}[k-1]$ (by [CR23, Proposition 9.1]). However, we
will see that $\phi^{k\operatorname{-qrO}}\in\texttt{UCouple}[k-1]$ follows
from the more conceptual fact that it is represented by the
$(k-1)$-independent $1$-$T_{k\operatorname{-Orientation}}$-on
${\mathcal{N}}^{k\operatorname{-qrO}}$ (see Corollary 4.5).

###  2.3 Main theorems

Our main theorem provides some more characterizations of
$\texttt{UCouple}[\ell]$ complementing the ones of [CR23, Theorem 3.10].

###### Theorem 2.2.

The following are equivalent for a limit
$\phi\in\operatorname{Hom}^{+}({\mathcal{A}}[T],\mathbb{R})$ and
$\ell\in\mathbb{N}$.

  1. i.

$\phi\in\texttt{UCouple}[\ell]$.

  2. ii.

$\phi$ is $\ast$-$\ell$-independent.

  3. iii.

There exists an $\ell$-independent $1$-Euclidean structure ${\mathcal{N}}$
such that $\phi=\phi_{\mathcal{N}}$.

  4. iv.

There exist a canonical theory $T^{\prime}$, an $\ell$-independent limit
$\psi\in\operatorname{Hom}^{+}({\mathcal{A}}[T^{\prime}],\mathbb{R})$ and a
quantifier-free definition $I\colon T\leadsto T^{\prime}\cup
T_{(\ell+1)\operatorname{-Orientation}}$ such that
$\phi=I^{*}(\psi\otimes\phi^{(\ell+1)\operatorname{-qrO}})$.

The implication (iii)$\implies$(ii) follows trivially from definitions.

As it was shown in [CR23, Theorems 3.6 and 3.8] (see also Example 1.4),
$\texttt{Independence}[\ell]$ (i.e., existence of an $\ell$-independent
$0$-Euclidean structure ${\mathcal{N}}$ with $\phi=\phi_{\mathcal{N}}$) is
strictly stronger than $\texttt{UCouple}[\ell]$ (see Example 1.4). The theorem
above says that not only is $\texttt{UCouple}[\ell]$ (item (i)) equivalent to
$\ast$-$\ell$-independence (item (ii)), but even adding extra order variables
does not increase the strength of quasirandomness: existence of an
$\ell$-independent $1$-Euclidean structure representation (item (iii)) is
still equivalent to $\texttt{UCouple}[\ell]$. Finally, the fact that item (iv)
is also equivalent to $\texttt{UCouple}[\ell]$ can be seen as a classification
of all $\texttt{UCouple}[\ell]$ limits as those that essentially consist of an
$\texttt{Independence}[\ell]$ part independently coupled with a quasirandom
$(\ell+1)$-orientation; in other words, the only difference between
$\texttt{UCouple}[\ell]$ and $\texttt{Independence}[\ell]$ is the potential
presence of a hidden quasirandom $(\ell+1)$-orientation.

As a consequence of Theorem 2.2 above, we settle the final missing
implications between the quasirandomness properties of [CR23]:

###### Theorem 2.3.

For every $\ell,\ell^{\prime}\in\mathbb{N}$ with $\ell^{\prime}<\ell$, we have
$\texttt{UCouple}[\ell]\implies\texttt{Independence}[\ell^{\prime}]$.

Since by [CR23, Theorems 3.3 and 3.4] independent couplings and quantifier-
free definitions preserve both $\texttt{Independence}[\ell]$ and
$\texttt{UCouple}[\ell]$, one can easily see how Theorem 2.2(i)$\implies$(iv)
implies Theorem 2.3 as the representation
$\phi^{(\ell+1)\operatorname{-qrO}}=\phi_{{\mathcal{H}}^{(\ell+1)\operatorname{-qrO}}}$
shows $\phi^{(\ell+1)\operatorname{-qrO}}\in\texttt{Independence}[\ell-1]$.
However, as it turns out, it will be easier to prove that every
$\ast$-$\ell$-independent limit satisfies $\texttt{Independence}[\ell-1]$
(Corollary 3.8), (so Theorem 2.3 will follow from the implication Theorem
2.2(i)$\implies$(ii) instead, see Corollary 9.8).

Table 1 contains the location of the proofs of the implications of Theorem 2.2
and the proof of Theorem 2.3.

Result | Proof location
---|---
Theorem 2.2 |  (iii)$\implies$(ii) | Trivial from definitions
(ii)$\implies$(i) | Proposition 4.4
(iv)$\implies$(i) | Corollary 4.6
(i)$\implies$(iii) | Proposition 9.7
(iii)$\implies$(iv) | Proposition 10.1
Theorem 2.3 |  | Corollaries 3.8 and 9.8
Table 1: Proof locations for main theorems.

##  3 $d$-Realizations

This section is dedicated to proving in Corollary 3.8 that every
$\ast$-$\ell$-independent limit is $(\ell-1)$-independent, which in particular
means that Theorem 2.3 is a direct corollary of Theorem 2.2 (this will be put
together in Corollary 9.8). We start by recalling a few concepts and basic
results from exchangeability theory.

###### Definition 3.1.

Let $\Omega_{1}=(X_{1},\mu_{1})$ and $\Omega_{2}=(X_{2},\mu_{2})$ be atomless
probability spaces, let $d_{1},d_{2},n\in\mathbb{N}$ and let
$f\colon{\mathcal{E}}_{n}^{(d_{1})}(\Omega_{1})\to\Omega_{2}\times{\mathcal{O}}_{n}^{d_{2}}$
be a function.

We say that $f$ is _symmetric_ if it is a.e. $S_{n}$-invariant in the first
component and a.e. $S_{n}$-equivariant in the order components in the sense
that

$\displaystyle f(\sigma^{*}(x))$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}(f_{0}(x),\sigma^{*}(f_{1}(x)),\sigma^{*}(f_{2}(x)),\ldots,\sigma^{*}(f_{d_{2}}(x)))$

for $\mu_{1}^{(d_{1})}$-almost every
$x\in{\mathcal{E}}_{n}^{(d_{1})}(\Omega_{1})$ and every $\sigma\in S_{n}$,
where $f_{0}\colon{\mathcal{E}}_{n}^{(d_{1})}(\Omega_{1})\to\Omega_{2}$ and
$f_{i}\colon{\mathcal{E}}_{n}^{(d_{1})}(\Omega_{1})\to{\mathcal{O}}_{n}$
($i\in[d_{2}]$) denote the components of $f$.

We say that $f$ is _measure-preserving on highest order argument_ (h.o.a.) if
it is measurable and for almost every $x\in{\mathcal{E}}_{n,n-1}^{(d_{1})}$,
the function

$\displaystyle
f(x,\mathord{-})\colon\Omega_{1}\times{\mathcal{O}}_{n}^{d_{1}}\to\Omega_{2}\times{\mathcal{O}}_{n}^{d_{2}}$

is measure-preserving (with respect to $\mu_{1}^{(d_{1})}$ and
$\mu_{2}^{(d_{2})}$).

Given a family $f=(f_{i})_{i\in\mathbb{N}_{+}}$ of symmetric functions
$f_{i}\colon{\mathcal{E}}_{i}^{(d_{1})}(\Omega_{1})\to\Omega_{2}\times{\mathcal{O}}_{i}^{d_{2}}$
and a countable set $V$, we define the function
$\widehat{f}_{V}\colon{\mathcal{E}}_{V}^{(d_{1})}(\Omega_{1})\to{\mathcal{E}}_{V}^{(d_{2})}(\Omega_{2})$
by

$\displaystyle\widehat{f}_{V}(x)_{A}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}(\overline{\alpha}_{A}^{-1})^{*}(f_{\lvert
A\rvert}(\alpha_{A}^{*}(x)))\qquad(A\in r(V)),$

where $\alpha_{A}\colon[\lvert A\rvert]\to V$ is any injection with
$\operatorname{im}(\alpha_{A})=A$ (recall that
$\overline{\alpha}_{A}\colon[\lvert A\rvert]\to A$ is the restriction of the
codomain of $\alpha_{A}$). Since the $f_{i}$ are symmetric, this a.e. does not
depend on the particular choice of $\alpha_{A}$.

Given further a $d_{2}$-Euclidean structure ${\mathcal{N}}$ in ${\mathcal{L}}$
over $\Omega_{2}$, we define the $d_{1}$-Euclidean structure
$f^{*}({\mathcal{N}})$ in ${\mathcal{L}}$ over $\Omega_{1}$ by

$\displaystyle f^{*}({\mathcal{N}})_{P}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\widehat{f}_{k(P)}^{-1}({\mathcal{N}}_{P})\qquad(P\in{\mathcal{L}}).$

The following lemma is an extension of a standard fact from exchangeability
theory to account for order variables.

###### Lemma 3.2.

Let $\Omega_{1}=(X_{1},\mu_{1})$ and $\Omega_{2}=(X_{2},\mu_{2})$ be atomless
probability spaces, let $d_{1},d_{2},n\in\mathbb{N}$ and let
$f=(f_{i})_{i\in\mathbb{N}_{+}}$ of symmetric functions
$f_{i}\colon{\mathcal{E}}_{i}^{(d_{1})}(\Omega_{1})\to\Omega_{2}\times{\mathcal{O}}_{i}^{d_{2}}$.
Then the following hold.

  1. i.

If each $f_{i}$ is measure-preserving on h.o.a. and $V$ is a countable set,
then $\widehat{f}_{V}$ is measure-preserving.

  2. ii.

$\widehat{f}_{V}$ is a.e. equivariant, that is, if $\beta\colon U\to V$ is an
injection between countable sets, then
$\beta^{*}\mathbin{\circ}\widehat{f}_{V}=\widehat{f}_{U}\mathbin{\circ}\beta^{*}$
holds $\mu_{1}^{(d_{1})}$-almost everywhere.

###### Proof.

Item (i) is equivalent to proving that if $\bm{x}$ is picked at random in
${\mathcal{E}}_{V}^{(d_{1})}(\Omega_{1})$ according to $\mu_{1}^{(d_{1})}$,
then $\bm{y}\stackrel{{\scriptstyle\text{def}}}{{=}}\widehat{f}_{V}(\bm{x})$
is distributed according to the measure $\mu_{2}^{(d_{2})}$ of
${\mathcal{E}}_{V}^{(d_{2})}(\Omega_{2})$. The definition of $\widehat{f}_{V}$
implies that each coordinate $\bm{y}_{A}$ is measurable with respect to the
$\sigma$-algebra generated by $(\bm{x}_{B}\mid B\in r(A))$ and since all
$f_{i}$ are measure-preserving on h.o.a., the conditional distribution of the
coordinate $\bm{y}_{A}$ given $(\bm{x}_{B}\mid B\subsetneq A)$ is
$\mu_{2}^{(d)}$, hence a simple induction and the fact that the coordinates of
$\bm{x}$ are mutually independent yields item (i).

For item (ii), note that for $\mu_{1}^{(d_{1})}$-almost every
$x\in{\mathcal{E}}_{V}^{(d_{1})}(\Omega_{1})$ and every $A\in r(U)$, we have

$\displaystyle\\!\\!\\!\\!\\!\\!(\beta^{*}\mathbin{\circ}\widehat{f}_{V})(x)_{A}$
$\displaystyle=\Biggl{(}f_{\lvert\beta(A)\rvert,0}(\alpha_{\beta(A)}^{*}(x)),$
$\displaystyle\hphantom{{}={}}\beta\mathord{\downarrow}_{A}^{*}\biggl{(}(\overline{\alpha}_{\beta(A)}^{-1})^{*}\Bigl{(}f_{\lvert\beta(A)\rvert,1}\bigl{(}\alpha_{\beta(A)}^{*}(x)\bigr{)}\Bigr{)}\biggr{)},\ldots,\beta\mathord{\downarrow}_{A}^{*}\biggl{(}(\overline{\alpha}_{\beta(A)}^{-1})^{*}\Bigl{(}f_{\lvert\beta(A)\rvert,d_{2}}\bigl{(}\alpha_{\beta(A)}^{*}(x)\bigr{)}\Bigr{)}\biggr{)}\Biggr{)},$

where $f_{i,0}\colon{\mathcal{E}}_{i}^{(d_{1})}(\Omega_{1})\to\Omega_{2}$ and
$f_{i,j}\colon{\mathcal{E}}_{i}^{(d_{1})}(\Omega_{1})\to{\mathcal{O}}_{i}$
($j\in[d_{2}]$) denote the components of $f_{i}$ ($i\in\mathbb{N}_{+}$).

Note that the composition
$\beta\mathord{\downarrow}_{A}^{-1}\mathbin{\circ}\overline{\alpha}_{\beta(A)}$
is a bijection $[\lvert A\rvert]\to A$. Let $\gamma_{A}\colon[\lvert
A\rvert]\to U$ be obtained from
$\beta\mathord{\downarrow}_{A}^{-1}\mathbin{\circ}\overline{\alpha}_{\beta(A)}$
by changing its codomain to $U$ (i.e., we have
$\gamma_{A}\stackrel{{\scriptstyle\text{def}}}{{=}}\iota_{A,V}\mathbin{\circ}\beta\mathord{\downarrow}_{A}^{-1}\mathbin{\circ}\overline{\alpha}_{\beta(A)}$).
By construction, $\gamma_{A}$ is an injection with
$\operatorname{im}(\gamma_{A})=A$ and
$\alpha_{\beta(A)}=\beta\mathbin{\circ}\gamma_{A}$, so we get

$\displaystyle f_{\lvert\beta(A)\rvert,0}(\alpha_{\beta(A)}^{*}(x))$
$\displaystyle=f_{\lvert A\rvert,0}(\gamma_{A}^{*}(\beta^{*}(x))).$

On the other hand, note that
$\overline{\gamma}_{A}=\beta\mathord{\downarrow}_{A}^{-1}\mathbin{\circ}\overline{\alpha}_{\beta(A)}$,
hence
$\overline{\gamma}_{A}^{-1}=\overline{\alpha}_{\beta(A)}^{-1}\mathbin{\circ}\beta\mathord{\downarrow}_{A}$,
so for every $j\in[d_{2}]$, we get

$\displaystyle\beta\mathord{\downarrow}_{A}^{*}\bigl{(}(\overline{\alpha}_{\beta(A)}^{-1})^{*}(f_{\lvert\beta(A)\rvert,j}(\alpha_{\beta(A)}^{*}(x)))\bigr{)}$
$\displaystyle=(\overline{\gamma}_{A}^{-1})^{*}(f_{\lvert
A\rvert,j}(\gamma_{A}^{*}(\beta^{*}(x))).$

Since $\operatorname{im}(\gamma_{A})=A$, we conclude that

$\displaystyle(\beta^{*}\mathbin{\circ}\widehat{f}_{V})(x)_{A}$
$\displaystyle=(\widehat{f}_{U}\mathbin{\circ}\beta^{*})(x)_{A}$

for $\mu_{1}^{(d_{1})}$-almost every
$x\in{\mathcal{E}}_{V}^{(d_{1})}(\Omega_{1})$ and every $A\in r(U)$. ∎

In order to prove Theorem 2.3, we need to find a way of simulating the order
variables of a $d$-Euclidean structure by the ordinary variables of a
$0$-Euclidean structures in a way that preserves as much independence as
possible. This will be done by $d$-realizations defined below, which are
heavily inspired by the different representations
${\mathcal{N}}^{k\operatorname{-qrO}}$ and
${\mathcal{H}}^{k\operatorname{-qrO}}$ of the quasirandom $k$-orientation (see
Definition 2.1).

###### Definition 3.3.

Let $\Omega_{1}=(X_{1},\mu_{1})$ and $\Omega_{2}=(X_{2},\mu_{2})$ be atomless
probability spaces and let $d\in\mathbb{N}$.

A _$d$ -realization_ from $\Omega_{1}$ to $\Omega_{2}$ is a family
$f=(f_{i})_{i\in\mathbb{N}_{+}}$ of symmetric measure-preserving on h.o.a.
functions
$f_{i}\colon{\mathcal{E}}_{i}(\Omega_{1})\to\Omega_{2}\times{\mathcal{O}}_{i}^{d}$
satisfying the following properties:

  1. i.

For every $i\in\mathbb{N}_{+}$, if the coordinate functions of $f_{i}$ are
$f_{i,0}\colon{\mathcal{E}}_{i}(\Omega_{1})\to\Omega_{2}$ and
$f_{i,j}\colon{\mathcal{E}}_{i}(\Omega_{1})\to{\mathcal{O}}_{i}$ ($j\in[d]$),
then, except for a zero $\mu_{1}$-measure set, $f_{i,0}$ depends only on the
top coordinate (indexed by $[i]$) and for every $j\in[d]$, except for a zero
$\mu_{1}$-measure set, $f_{i,j}$ depends only on the coordinates indexed by
sets in $\binom{[i]}{>i-2}$.

  2. ii.

There exists a family $g=(g_{i})_{i\in\mathbb{N}_{+}}$ of symmetric measure-
preserving on h.o.a. functions
$g_{i}\colon{\mathcal{E}}_{i}^{(d)}(\Omega_{2}\times\Omega_{2})\to\Omega_{1}$
such that

$\displaystyle\widehat{f}_{i}(\widehat{g}_{i}(x,y,{\lhd}))$
$\displaystyle=(x,{\lhd})$ (3.1)

for every $i\in\mathbb{N}_{+}$ and $(\mu_{2}\otimes\mu_{2})^{(d)}$-almost
every $(x,y,{\lhd})\in{\mathcal{E}}_{i}^{(d)}(\Omega_{2}\times\Omega_{2})$.

Any family of functions $g$ as in item (ii) above is called an _almost inverse
family_ of $f$.

###### Remark 3.4.

Since both the $f_{i}$ and $g_{i}$ are symmetric, by Lemma 3.2(ii), equation
(3.1) implies

$\displaystyle\widehat{f}_{V}(\widehat{g}_{V}(x,y,{\lhd}))$
$\displaystyle=(x,{\lhd})$

for every countable $V$ and $(\mu_{2}\otimes\mu_{2})^{(d)}$-almost every
$(x,y,{\lhd})\in{\mathcal{E}}_{V}^{(d)}(\Omega_{2})$.

Our first order of business is to show that $d$-realizations exist.

###### Lemma 3.5.

For all $d\in\mathbb{N}$ and all atomless standard probability spaces
$\Omega_{1}=(X_{1},\mu_{1})$ and $\Omega_{2}=(X_{2},\mu_{2})$, there exists a
$d$-realization from $\Omega_{1}$ to $\Omega_{2}$.

###### Proof.

First we claim that it is enough to show the result for only one fixed pair of
spaces $(\Omega_{1},\Omega_{2})$. Indeed, if $f=(f_{i})_{i\in\mathbb{N}_{+}}$
is a $d$-realization from $\Lambda_{1}$ to $\Lambda_{2}$,
$g=(g_{i})_{i\in\mathbb{N}_{+}}$ is an almost inverse family of $f$ and
$\Omega_{1}$ and $\Omega_{2}$ are standard probability spaces, then we can let
$F_{1}\colon\Omega_{1}\to\Lambda_{1}$ and
$F_{2}\colon\Omega_{2}\to\Lambda_{2}$ be measure-isomorphisms modulo $0$ and
for every $i\in\mathbb{N}_{+}$, define
$f^{\prime}_{i}\colon{\mathcal{E}}_{i}(\Omega_{1})\to\Omega_{2}\times{\mathcal{O}}_{i}^{d}$
and
$g^{\prime}_{i}\colon{\mathcal{E}}_{i}^{(d)}(\Omega_{2}\times\Omega_{2})\to\Omega_{1}$
by

$\displaystyle f^{\prime}_{i}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}(F_{2}^{-1}\otimes\operatorname{id}_{{\mathcal{O}}_{i}^{d}})\mathbin{\circ}f_{i}\mathbin{\circ}\bigotimes_{A\in
r(i)}F_{1},$ $\displaystyle g^{\prime}_{i}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}F_{1}^{-1}\mathbin{\circ}g_{i}\mathbin{\circ}\bigotimes_{A\in
r(i)}(F_{2}\otimes F_{2}\otimes\operatorname{id}_{{\mathcal{O}}_{A}^{d}}).$

(Note that the above only gives an almost everywhere definition as
$F_{1}^{-1}$ and $F_{2}^{-1}$ are only defined in a full measure set, but we
can simply extend the definition arbitrarily but measurably.)

It is straightforward to check that
$f^{\prime}=(f^{\prime}_{i})_{i\in\mathbb{N}_{+}}$ is a $d$-realization from
$\Omega_{1}$ to $\Omega_{2}$ and
$g^{\prime}=(g^{\prime}_{i})_{i\in\mathbb{N}_{+}}$ is an almost inverse family
of $f^{\prime}$.

We now note that the case $d=0$ is trivial: by taking $\Omega_{1}=\Omega_{2}$,
we can simply let $f_{i}(x)\stackrel{{\scriptstyle\text{def}}}{{=}}x_{[i]}$
for every $i\in\mathbb{N}_{+}$ and every $x\in{\mathcal{E}}_{i}(\Omega_{1})$.
An almost inverse family of $f$ is then obtained by taking
$g_{i}(x,y)\stackrel{{\scriptstyle\text{def}}}{{=}}x_{[i]}$ for every
$i\in\mathbb{N}_{+}$ and every
$(x,y)\in{\mathcal{E}}_{i}(\Omega_{2}\times\Omega_{2})$.

We now claim that the case $d\in\mathbb{N}_{+}$ follows from the case $d=1$.
Indeed, if $f=(f_{i})_{i\in\mathbb{N}_{+}}$ is a $1$-realization from
$\Omega_{1}$ to $\Omega_{2}$ and $g=(g_{i})_{i\in\mathbb{N}_{+}}$ is an almost
inverse family of $f$, then letting

$\displaystyle f^{\prime}_{i}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\bigotimes_{i=1}^{d}f_{i},$
$\displaystyle g^{\prime}_{i}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\bigotimes_{i=1}^{d}g^{\prime}_{i}$

for every $i\in\mathbb{N}_{+}$, it is straightforward to check that
$f^{\prime}=(f^{\prime}_{i})_{i\in\mathbb{N}_{+}}$ is a $d$-realization from
$\Omega_{1}^{d}$ to $\Omega_{2}^{d}$ and
$g^{\prime}=(g^{\prime}_{i})_{i\in\mathbb{N}_{+}}$ is an almost inverse family
of $f^{\prime}$.

Let us then prove the case $d=1$ when $\Omega_{1}=([0,1)^{2},\lambda)$ and
$\Omega_{2}=([0,1),\lambda)$.

First, for every $i\in\mathbb{N}_{+}$, let

$\displaystyle D_{i}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{(x,y)\in{\mathcal{E}}_{i}(\Omega_{1})\mid\exists
A,B\in r(i),(A\neq B\land y_{A}=y_{B})\\}.$

(Recall that we naturally identify ${\mathcal{E}}_{i}(\Omega_{1})$ with
${\mathcal{E}}_{i}(\Omega_{2})\times{\mathcal{E}}_{i}(\Omega_{2})$.) Note that
$D_{i}$ is a Borel set with $\lambda$-measure zero, so it is sufficient to
define $f_{i}$ only outside of $D_{i}$.

For each $i\in\mathbb{N}_{+}$, let $\theta_{i}$ be the uniform probability
measure on $S_{i}$ and let $\tau_{i}\colon[0,1)\to S_{i}$ be defined as
follows. We fix an enumeration $\gamma^{i}_{1},\ldots,\gamma^{i}_{i!}$ of
$S_{i}$ and let

$\displaystyle\tau_{i}(x)$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\gamma^{i}_{\lfloor
x\cdot i!\rfloor+1}.$ (3.2)

Note that $\tau_{i}$ is a measure-preserving with respect to $\lambda$ and
$\theta_{i}$.

Define the function
$f_{i}\colon{\mathcal{E}}_{i}(\Omega_{1})\to\Omega_{2}\times{\mathcal{O}}_{i}$
by

$\displaystyle f_{i}(x,y)$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}(x_{[i]},(\tau_{i}(y_{[i]})\mathbin{\circ}\sigma_{y})^{*}({\leq}))$

for every $(x,y)\in{\mathcal{E}}_{i}(\Omega_{1})\setminus D_{i}$, where $\leq$
is the usual order on $[i]$ and $\sigma_{y}\in S_{i}$ is the unique
permutation such that

$\displaystyle
y_{[i]\setminus\\{\sigma_{y}^{-1}(1)\\}}<y_{[i]\setminus\\{\sigma_{y}^{-1}(2)\\}}<\cdots<y_{[i]\setminus\\{\sigma_{y}^{-1}(i)\\}}.$
(3.3)

We also define $f_{i}$ arbitrarily but measurably in $D_{i}$.

Clearly, item (i) of Definition 3.3 holds for
$f=(f_{i})_{i\in\mathbb{N}_{+}}$.

Let us now show that $f$ is symmetric. Let $i\in\mathbb{N}_{+}$, let
$(x,y)\in{\mathcal{E}}_{i}(\Omega)\setminus D_{i}$, let $\pi\in S_{i}$ and
note that

$\displaystyle(f_{i}\mathbin{\circ}\pi^{*})(x,y)$
$\displaystyle=\bigl{(}x_{[i]},(\tau_{i}(y_{[i]})\mathbin{\circ}\sigma_{\pi^{*}(y)})^{*}({\leq})\bigr{)}$
$\displaystyle\bigl{(}(\operatorname{id}_{\Omega_{2}}\otimes\pi^{*})\mathbin{\circ}f_{i}\bigr{)}(x,y)$
$\displaystyle=\Bigl{(}x_{[i]},\pi^{*}\bigl{(}(\tau_{i}(y_{[i]})\mathbin{\circ}\sigma_{y})^{*}({\leq})\bigr{)}\Bigr{)}=\bigl{(}x_{[i]},(\tau_{i}(y_{[i]})\mathbin{\circ}\sigma_{y}\mathbin{\circ}\pi)^{*}({\leq})\bigr{)},$

so it suffices to show that
$\sigma_{y}\mathbin{\circ}\pi=\sigma_{\pi^{*}(y)}$.

But indeed, we know that $\sigma_{\pi^{*}(y)}$ is the unique element of
$S_{i}$ such that

$\displaystyle\pi^{*}(y)_{[i]\setminus\\{\sigma_{\pi^{*}(y)}^{-1}(1)\\}}<\pi^{*}(y)_{[i]\setminus\\{\sigma_{\pi^{*}(y)}^{-1}(2)\\}}<\cdots<\pi^{*}(y)_{[i]\setminus\\{\sigma_{\pi^{*}(y)}^{-1}(i)\\}}$

and since for every $j\in[i]$, we have

$\displaystyle\pi^{*}(y)_{[i]\setminus\\{\sigma_{\pi^{*}(y)}^{-1}(j)\\}}$
$\displaystyle=y_{[i]\setminus\\{(\pi\mathbin{\circ}\sigma_{\pi^{*}(y)}^{-1})(j)\\}}=y_{[i]\setminus\\{(\sigma_{\pi^{*}(y)}\mathbin{\circ}\pi^{-1})^{-1}(j)\\}},$

it follows that $\sigma_{y}=\sigma_{\pi^{*}(y)}\mathbin{\circ}\pi^{-1}$, hence
$\sigma_{y}\mathbin{\circ}\pi=\sigma_{\pi^{*}(y)}$ as desired. Therefore
$f_{i}$ is symmetric.

Let us now show that $f_{i}$ is measure-preserving on h.o.a. Fix
$(x,y)\in{\mathcal{E}}_{i,i-1}(\Omega_{1})$ and note that showing that the
function
$f_{i}(x,y,\mathord{-})\colon\Omega_{1}\to\Omega_{2}\times{\mathcal{O}}_{i}$
is measure-preserving is equivalent to showing that if $\bm{w}$ and $\bm{z}$
are picked i.i.d. uniformly at random in $[0,1)$, then
$(\bm{u},{\bm{\lhd}})\stackrel{{\scriptstyle\text{def}}}{{=}}f_{i}((x,\bm{w}),(y,\bm{z}))$
is uniformly distributed in $[0,1)\times{\mathcal{O}}_{i}$.

The definition of $f_{i}$ gives $\bm{u}=\bm{w}$ and $\bm{\lhd}$ is
$\bm{z}$-measurable with

$\displaystyle\bm{\lhd}$
$\displaystyle=(\tau_{i}(\bm{z})\mathbin{\circ}\sigma_{y,\bm{z}})^{*}({\leq}),$

but note that $\sigma_{y,\bm{z}}$ does not depend on $\bm{z}$ at all and
$\tau_{i}(\bm{z})$ is uniformly distributed in $S_{i}$, hence $\bm{\lhd}$ is
uniformly distributed in ${\mathcal{O}}_{i}$ and is independent from $\bm{u}$.
Therefore $(\bm{u},\bm{\lhd})$ is uniformly distributed in
$[0,1)\times{\mathcal{O}}_{i}$.

It remains to show that there exists an almost inverse family of $f$. For each
$i\in\mathbb{N}_{+}$, let

$\displaystyle D^{\prime}_{i}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{(y,{\lhd})\in{\mathcal{E}}_{i}^{(1)}(\Omega_{2})\mid\exists
A,B\in r(i),(A\neq B\land y_{A}=y_{B})\\}.$

Clearly $D^{\prime}_{i}$ is an $S_{i}$-invariant Borel set with zero
$\lambda$-measure.

We now define $S_{i}$-invariant functions

$\displaystyle h_{i}\colon$
$\displaystyle{\mathcal{E}}_{i}^{(1)}(\Omega_{2})\setminus
D^{\prime}_{i}\to[0,1),$ $\displaystyle k_{i}\colon$
$\displaystyle{\mathcal{E}}_{i}^{(1)}(\Omega_{2})\setminus
D^{\prime}_{i}\to[i!]$

inductively in $i\in\mathbb{N}_{+}$ as follows. (We will later use $h_{i}$ in
(3.8) to define the almost inverse family $g$ of $f$.)

To start the induction, we define $h_{0}$ as the constant $0$ function. Given
$h_{i-1}$, for $(y,{\lhd})\in{\mathcal{E}}_{i}^{(1)}(\Omega_{2})\setminus
D^{\prime}_{i}$, we let $k_{i}(y,{\lhd})\in[i!]$ be the unique element such
that

$\displaystyle(\gamma^{i}_{k_{i}(y,{\lhd})}\mathbin{\circ}\widetilde{\sigma}_{y,{\lhd}})^{*}({\leq})$
$\displaystyle={\lhd_{[i]}},$ (3.4)

where $\leq$ is the usual order on $[i]$, $\widetilde{\sigma}_{y,{\lhd}}\in
S_{i}$ is the unique permutation such that

$\displaystyle[i]\ni a$ $\displaystyle\longmapsto
h_{i-1}(\alpha_{[i]\setminus\\{\widetilde{\sigma}_{y,{\lhd}}^{-1}(a)\\},i}^{*}(y,{\lhd}))\in[0,1)$
(3.5)

is increasing and for each $A\subseteq[i]$, $\alpha_{A,i}\colon[\lvert
A\rvert]\to[i]$ is any injection with $\operatorname{im}(\alpha_{A,i})=A$.
Note that since $h_{i-1}$ is inductively assumed to be $S_{i-1}$-invariant,
the above does not depend on the choice of $\alpha_{A,i}$.

We then define

$\displaystyle h_{i}(y,{\lhd})$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{y_{[i]}+k_{i}(y,{\lhd})-1}{i!}.$

Clearly, if $k_{i}$ is $S_{i}$-invariant, so is $h_{i}$.

Let us then show that $k_{i}$ is $S_{i}$-invariant. Let
$(y,{\lhd})\in{\mathcal{E}}_{i}^{(1)}(\Omega_{2})\setminus D^{\prime}_{i}$,
let $\pi\in S_{i}$. Since

$\displaystyle(\gamma^{i}_{k_{i}(\pi^{*}(y,{\lhd}))}\mathbin{\circ}\widetilde{\sigma}_{\pi^{*}(y,{\lhd})})^{*}({\leq})$
$\displaystyle=\pi^{*}({\lhd_{[i]}}),$

we get

$\displaystyle(\gamma^{i}_{k_{i}(\pi^{*}(y,{\lhd}))}\mathbin{\circ}\widetilde{\sigma}_{\pi^{*}(y,{\lhd})}\mathbin{\circ}\pi^{-1})^{*}({\leq})$
$\displaystyle={\lhd_{[i]}},$

so it suffices to show that

$\displaystyle\widetilde{\sigma}_{\pi^{*}(y,{\lhd})}\mathbin{\circ}\pi^{-1}=\widetilde{\sigma}_{y,{\lhd}}.$
(3.6)

To do so, note first that since for every $a\in[i]$, we have

$\displaystyle
h_{i-1}(\alpha_{[i]\setminus\\{\widetilde{\sigma}_{\pi^{*}(y,{\lhd})}^{-1}(a)\\},i}^{*}(\pi^{*}(y,{\lhd})))$
$\displaystyle=h_{i-1}(\pi\mathbin{\circ}\alpha_{[i]\setminus\\{\widetilde{\sigma}_{\pi^{*}(y,{\lhd})}^{-1}(a)\\},i})^{*}(y,{\lhd}))$
(3.7)
$\displaystyle=h_{i-1}(\alpha_{[i]\setminus\\{(\widetilde{\sigma}_{\pi^{*}(y,{\lhd})}\mathbin{\circ}\pi^{-1})^{-1}(a)\\},i})^{*}(y,{\lhd}),$

where the second equality follows since $h_{i-1}$ is inductively assumed to be
$S_{i-1}$-invariant and

$\displaystyle\operatorname{im}(\pi\mathbin{\circ}\alpha_{[i]\setminus\\{\widetilde{\sigma}_{\pi^{*}(y,{\lhd})}^{-1}(a)})$
$\displaystyle=\pi([i]\setminus\\{\widetilde{\sigma}_{\pi^{*}(y,{\lhd})}^{-1}(a)\\})$
$\displaystyle=[i]\setminus\\{(\pi\mathbin{\circ}\widetilde{\sigma}_{\pi^{*}(y,{\lhd})}^{-1})(a)\\}=\operatorname{im}(\alpha_{[i]\setminus\\{(\widetilde{\sigma}_{\pi^{*}(y,{\lhd})}\mathbin{\circ}\pi^{-1})^{-1}(a)}).$

Since $\widetilde{\sigma}_{y,{\lhd}}$ and
$\widetilde{\sigma}_{\pi^{*}(y,{\lhd})}$ are the unique elements of $S_{i}$
such that

$\displaystyle[i]\ni a$ $\displaystyle\longmapsto
h_{i-1}(\alpha_{[i]\setminus\\{\widetilde{\sigma}_{y,{\lhd}}^{-1}(a)\\}}^{*}(y,{\lhd}))\in[0,1)$
$\displaystyle[i]\ni a$ $\displaystyle\longmapsto
h_{i-1}(\alpha_{[i]\setminus\\{\widetilde{\sigma}_{\pi^{*}(y,{\lhd})}^{-1}(a)\\}}^{*}(\pi^{*}(y,{\lhd})))\in[0,1)$

are increasing, (3.6) follows from (3.7). Therefore $k_{i}$ is
$S_{i}$-invariant.

We now claim that $h_{i}$ is measure-preserving on h.o.a. (or more precisely,
any measurable extension of $h_{i}$ to ${\mathcal{E}}_{i}^{(1)}(\Omega_{2})$
is measure-preserving on h.o.a.). This is equivalent to saying that for
$\lambda^{(1)}$-almost every
$(y,{\lhd})\in{\mathcal{E}}_{i,i-1}^{(1)}(\Omega_{2})$ such that $y_{A}\neq
y_{B}$ whenever $A\neq B$, if $\bm{z}$ and $\bm{\ll}$ are sampled
independently and uniformly in $[0,1)$ and ${\mathcal{O}}_{i}$, respectively,
then
$\bm{w}\stackrel{{\scriptstyle\text{def}}}{{=}}h_{i}((y,\bm{z}),({\lhd},\bm{\ll}))$
is uniformly distributed in $[0,1)$.

In turn, from the definition of $h_{i}$, the above is equivalent to showing
that
$\bm{j}\stackrel{{\scriptstyle\text{def}}}{{=}}k_{i}((y,\bm{z}),({\lhd},\bm{\ll}))$
is uniformly distributed in $[i!]$. But this follows since

$\displaystyle(\gamma^{i}_{\bm{j}}\mathbin{\circ}\widetilde{\sigma}_{(y,\bm{z}),({\lhd},\bm{\ll})})^{*}({\leq})$
$\displaystyle={\bm{\ll}},$

since $\widetilde{\sigma}_{(y,\bm{z}),({\lhd},\bm{\ll})}$ does not depend on
$\bm{z}$ or $\bm{\ll}$ and since $\bm{\ll}$ is uniformly distributed on
${\mathcal{O}}_{i}$.

We now finally define
$g_{i}\colon{\mathcal{E}}_{i}^{(1)}(\Omega_{2}\times\Omega_{2})\to\Omega_{1}$
($i\in\mathbb{N}_{+}$) as

$\displaystyle g_{i}(x,y,{\lhd})$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}(x_{[i]},h_{i}(y,{\lhd})),$
(3.8)

(using an arbitrary measurable extension of $h_{i}$).

It is straightforward to check that the fact that $h_{i}$ is $S_{i}$-invariant
implies that $g_{i}$ is symmetric and the fact that $h_{i}$ is measure-
preserving on h.o.a. implies that $g_{i}$ is measure preserving on h.o.a.

We now claim that $g=(g_{i})_{i\in\mathbb{N}_{+}}$ is an almost inverse family
of $f$. For this, we have to show that for every $i\in\mathbb{N}_{+}$ and
$\lambda^{(1)}$-almost every
$(x,y,{\lhd})\in{\mathcal{E}}_{i}^{(1)}(\Omega_{2}\times\Omega_{2})$, we have

$\displaystyle\widehat{f}_{i}(\widehat{g}_{i}(x,y,{\lhd}))$
$\displaystyle=(x,{\lhd}).$ (3.9)

Since $D^{\prime}_{i}$ has zero measure, we may suppose that $(y,{\lhd})\notin
D^{\prime}_{i}$. Note that for $A\in r(i)$, we have

$\displaystyle\widehat{f}_{i}(\widehat{g}_{i}(x,y,{\lhd}))_{A}$
$\displaystyle=(\overline{\alpha}_{A,i}^{-1})^{*}\biggl{(}f_{\lvert
A\rvert}\Bigl{(}\alpha_{A,i}^{*}\bigl{(}\widehat{g}_{i}(x,y,{\lhd})\bigr{)}\Bigr{)}\biggr{)}=(\overline{\alpha}_{A,i}^{-1})^{*}\biggl{(}f_{\lvert
A\rvert}\Bigl{(}\bigl{(}\widehat{g}_{\lvert
A\rvert}(\alpha_{A,i}^{*}(x,y,{\lhd}))\bigr{)}\Bigr{)}\biggr{)},$

almost everywhere, where the second equality follows from Lemma 3.2(ii).

For every $B\in r(\lvert A\rvert)$, let

$\displaystyle z_{B}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\alpha_{B,\lvert
A\rvert}^{*}\bigl{(}\alpha_{A,i}^{*}(x)\bigr{)}_{[\lvert
B\rvert]}=\alpha_{A,i}^{*}(x)_{B}=x_{\alpha_{A,i}(B)},$ $\displaystyle w_{B}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}h_{\lvert
B\rvert}\Bigl{(}\alpha_{B,\lvert
A\rvert}^{*}\bigl{(}\alpha_{A,i}^{*}(y,{\lhd})\bigr{)}\Bigr{)}=\frac{y_{\alpha_{A,i}(B)}+k_{\lvert
B\rvert}\bigl{(}(\alpha_{A,i}\mathbin{\circ}\alpha_{B,\lvert
A\rvert})^{*}(y,{\lhd})\bigr{)}-1}{\lvert B\rvert!},$ (3.10)

so that $\widehat{g}_{\lvert A\rvert}(\alpha_{A,i}^{*}(x,y,{\lhd}))=(z,w)$.

We claim that

$\displaystyle\sigma_{w}$
$\displaystyle=\widetilde{\sigma}_{\alpha_{A,i}^{*}(y,{\lhd})}.$ (3.11)

To see this, note first that for every $a\in[\lvert A\rvert]$, we have

$\displaystyle w_{[\lvert A\rvert]\setminus\\{\sigma_{w}^{-1}(a)\\}}$
$\displaystyle=h_{\lvert A\rvert-1}\Bigl{(}\alpha_{[\lvert
A\rvert]\setminus\\{\sigma_{w}^{-1}(a)\\},\lvert
A\rvert}^{*}\bigl{(}\alpha_{A,i}^{*}(y,{\lhd})\bigr{)}\Bigr{)}.$ (3.12)

The definition of $\sigma_{w}$ in (3.3) is as the unique permutation in
$S_{\lvert A\rvert}$ such that mapping $a\in[\lvert A\rvert]$ to the left-hand
side of (3.12) yields an increasing function. On the other hand, the
definition of $\widetilde{\sigma}_{\alpha_{A,i}^{*}(y,{\lhd})}$ in (3.5) is as
the unique permutation in $S_{\lvert A\rvert}$ such that mapping $a\in[\lvert
A\rvert]$ to

$\displaystyle h_{\lvert A\rvert-1}\Bigl{(}\alpha_{[\lvert
A\rvert]\setminus\\{\widetilde{\sigma}_{\alpha_{A,i}^{*}(y,{\lhd})}(a)\\}}^{*}\bigl{(}\alpha_{A,i}^{*}(y,{\lhd})\bigr{)}\Bigr{)}$

yields an increasing function; comparing this to the right-hand side of
(3.12), we conclude that
$\sigma_{w}=\widetilde{\sigma}_{\alpha_{A,i}^{*}(y,{\lhd})}$ (i.e., (3.11)
holds).

Note now that the definitions of $\tau_{\lvert A\rvert}$ and $w$ (in (3.2) and
(3.10), respectively) imply that

$\displaystyle\tau_{\lvert A\rvert}(w_{[\lvert A\rvert]})$
$\displaystyle=\gamma^{\lvert A\rvert}_{\lfloor w_{[\lvert
A\rvert]}\cdot\lvert A\rvert!\rfloor+1}=\gamma^{\lvert A\rvert}_{k_{\lvert
A\rvert}(\alpha_{A,i}^{*}(y,{\lhd}))}$ (3.13)

almost everywhere simply because $y_{A}\in[0,1)$.

Thus, almost everywhere we have

$\displaystyle\widehat{f}_{i}(\widehat{g}_{i}(x,y,{\lhd}))_{A}$
$\displaystyle=(\overline{\alpha}_{A,i}^{-1})^{*}\bigl{(}f_{\lvert
A\rvert}(z,w)\bigr{)}$ $\displaystyle=\Bigl{(}z_{[\lvert
A\rvert]},(\overline{\alpha}_{A,i}^{-1})^{*}\bigl{(}(\tau_{\lvert
A\rvert}(w_{[\lvert
A\rvert]})\mathbin{\circ}\sigma_{w})^{*}({\leq})\bigr{)}\Bigr{)}$
$\displaystyle=\Bigl{(}x_{A},(\overline{\alpha}_{A,i}^{-1})^{*}\bigl{(}(\gamma^{\lvert
A\rvert}_{k_{\lvert
A\rvert}(\alpha_{A,i}^{*}(y,{\lhd}))}\mathbin{\circ}\widetilde{\sigma}_{\alpha_{A,i}^{*}(x,y,{\lhd})})^{*}({\leq})\bigr{)}\Bigr{)}$
$\displaystyle=\Bigl{(}x_{A},(\overline{\alpha}_{A,i}^{-1})^{*}\bigl{(}\alpha_{A,i}\mathord{\downarrow}_{[\lvert
A\rvert]}^{*}({\lhd_{A}})\bigr{)}\Bigr{)}$ $\displaystyle=(x_{A},{\lhd_{A}}),$

where the third equality follows from (3.11) and (3.13), the fourth equality
follows from (3.4) and the fifth equality follows since
$\alpha_{A,i}\mathord{\downarrow}_{[\lvert A\rvert]}=\overline{\alpha}_{A,i}$.
Thus (3.9) holds almost everywhere, so $g$ is an almost inverse family of $f$.
∎

The next lemma shows how to use families of symmetric measure-preserving on
h.o.a. functions, and in particular $d$-realizations to change representations
of limits.

###### Lemma 3.6.

Let $\Omega_{1}=(X_{1},\mu_{1})$ and $\Omega_{2}=(X_{2},\mu_{2})$ be atomless
standard probability spaces, let $f=(f_{i})_{i\in\mathbb{N}_{+}}$ be a family
of symmetric measure-preserving on h.o.a. functions
$f_{i}\colon{\mathcal{E}}_{i}^{(d_{1})}(\Omega_{1})\to\Omega_{2}\times{\mathcal{O}}_{i}^{d_{2}}$
and let ${\mathcal{N}}$ be a $d_{2}$-Euclidean structure in ${\mathcal{L}}$
over $\Omega_{2}$. Then the following hold.

  1. i.

$\operatorname{rk}(f^{*}({\mathcal{N}}))\leq\operatorname{rk}({\mathcal{N}})$.

  2. ii.

$\phi_{f^{*}({\mathcal{N}})}=\phi_{\mathcal{N}}$.

  3. iii.

If $d_{1}=0$, $f$ is a $d_{2}$-realization and ${\mathcal{N}}$ is
$\ell$-independent, then $f^{*}({\mathcal{N}})$ is a.e. equal to an
$(\ell-1)$-independent $0$-Euclidean structure.

  4. iv.

If $d_{1}=0$, $f$ is a $d_{2}$-realization and ${\mathcal{N}}$ is
$\ell$-independent and does not depend on any coordinate in
${\mathcal{O}}_{A}$ with $\lvert A\rvert=\ell+1$, then $f^{*}({\mathcal{N}})$
is a.e. equal to an $\ell$-independent $0$-Euclidean structure.

###### Proof.

Item (i) follows directly from definitions.

For item (ii), note that for every finite set $V$, for almost every
$x\in{\mathcal{E}}_{V}^{(d_{1})}(\Omega_{1})$, every $P\in{\mathcal{L}}$ and
every $\alpha\in(V)_{k(P)}$, we have

$\displaystyle(M^{f^{*}({\mathcal{N}})}_{V}(x)\vDash P(\alpha))$
$\displaystyle\iff\alpha^{*}(x)\in
f^{*}({\mathcal{N}})_{P}\iff\alpha^{*}(x)\in\widehat{f}_{k(P)}^{-1}({\mathcal{N}}_{P})\iff(\widehat{f}_{k(P)}\mathbin{\circ}\alpha^{*})(x)\in{\mathcal{N}}_{P}$
$\displaystyle\iff\alpha^{*}(\widehat{f}_{V}(x))\in{\mathcal{N}}_{P}\iff(M^{\mathcal{N}}_{V}(\widehat{f}_{V}(x))\vDash
P(\alpha)),$

where the third equivalence follows from Lemma 3.2(ii).

Since $\widehat{f}_{V}$ is measure-preserving by Lemma 3.2(i), we get that for
$K\in{\mathcal{K}}_{V}$, we have

$\displaystyle t_{\operatorname{ind}}\bigl{(}K,f^{*}({\mathcal{N}})\bigr{)}$
$\displaystyle=\mu^{(d_{1})}\Bigl{(}T_{\operatorname{ind}}\bigl{(}K,f^{*}({\mathcal{N}})\bigr{)}\Bigr{)}=\mu^{(d_{1})}\bigl{(}(M_{V}^{f^{*}({\mathcal{N}})})^{-1}(\\{K\\})\bigr{)}=\mu^{(d_{1})}\Bigl{(}\widehat{f}_{V}^{-1}\bigr{(}(M_{V}^{\mathcal{N}})^{-1}(\\{K\\})\bigr{)}\Bigr{)}$
$\displaystyle=\mu^{(d_{2})}\bigl{(}(M_{V}^{\mathcal{N}})^{-1}(\\{K\\})\bigr{)}=\mu^{(d_{2})}\bigl{(}T_{\operatorname{ind}}(K,{\mathcal{N}})\bigr{)}=t_{\operatorname{ind}}(K,{\mathcal{N}}).$

Therefore $\phi_{f^{*}({\mathcal{N}})}=\phi_{\mathcal{N}}$.

For item (iii), since each $d_{2}$-$P$-on ${\mathcal{N}}_{P}$ is
$\ell$-independent and item (i) of Definition 3.3 says that, except for a zero
$\mu_{1}$-measure set, $f_{i}$ depends only on coordinates indexed by sets in
$\binom{[i]}{>i-2}$, it follows that, except for a zero $\mu_{1}$-measure set,
each $P$-on $f^{*}({\mathcal{N}}_{P})$ depends only on coordinates indexed by
sets in $\binom{[k(P)]}{>\ell-1}$.

Item (iv) follows with the same logic as item (iii), except that since
${\mathcal{N}}$ also does not depend on coordinates in ${\mathcal{O}}_{A}$
with $\lvert A\rvert=\ell+1$, it follows that, except for a zero
$\mu_{1}$-measure set, each $P$-on $f^{*}({\mathcal{N}}_{P})$ depends only on
coordinates indexed by sets in $\binom{[k(P)]}{>\ell}$ as the order
coordinates of size $\ell+1$ are now irrelevant. ∎

###### Remark 3.7.

The alternative representation ${\mathcal{H}}^{k\operatorname{-qrO}}$ in (2.4)
of the quasirandom $k$-orientation is obtained from the standard
representation ${\mathcal{N}}^{k\operatorname{-qrO}}$ as
${\mathcal{H}}^{k\operatorname{-qrO}}=f^{*}({\mathcal{N}}^{k\operatorname{-qrO}})$
(up to zero-measure) for the $d$-realization constructed in Lemma 3.5 (when
$\Omega=([0,1),\lambda)$).

As a direct corollary, we conclude that $\ast$-$\ell$-independence implies
$\texttt{Independence}[\ell^{\prime}]$ for every $\ell^{\prime}<\ell$:

###### Corollary 3.8.

If $\ell^{\prime},\ell\in\mathbb{N}$ are such that $\ell^{\prime}<\ell$, then
every $\ast$-$\ell$-independent limit $\phi$ satisfies
$\texttt{Independence}[\ell^{\prime}]$.

###### Proof.

It suffices to show the case $\ell^{\prime}=\ell-1$. If $\phi$ is
$\ast$-$\ell$-independent, then there exist $d\in\mathbb{N}$ and an
$\ell$-independent $d$-Euclidean structure ${\mathcal{N}}$ over some space
$\Omega=(X,\mu)$ such that $\phi=\phi_{\mathcal{N}}$. By Lemma 3.5, there
exists a $d$-realization $f$ from $\Omega$ to $\Omega$ and by Lemma 3.6, items
(ii) and (iii), we have $\phi=\phi_{f^{*}({\mathcal{N}})}$ and
$f^{*}({\mathcal{N}})$ is a $0$-Euclidean structure that is a.e. equal to some
$(\ell-1)$-independent $0$-Euclidean structure ${\mathcal{H}}$. In particular,
this implies that for the $(\ell-1)$-independent $0$-Euclidean structure
${\mathcal{H}}$, we have $\phi=\phi_{\mathcal{H}}$, so $\phi$ satisfies
$\texttt{Independence}[\ell-1]$. ∎

Another direct corollary is that the rank of a limit can be alternatively
defined as the minimum rank of any $d$-Euclidean structure representing it
(instead taking the minimum over only $0$-Euclidean structures representing
it):

###### Corollary 3.9.

For every limit $\phi$, we have

$\displaystyle\operatorname{rk}(\phi)$
$\displaystyle=\min_{\mathcal{N}}\operatorname{rk}({\mathcal{N}}),$

where the minimum is over all $d$-Euclidean structures ${\mathcal{N}}$ over
some space $\Omega$ and for some $d\in\mathbb{N}$ such that
$\phi=\phi_{\mathcal{N}}$.

###### Proof.

Let $m$ be the minimum on the right-hand side. From the definition of rank, it
is clear that $\operatorname{rk}(\phi)\geq m$. On the other hand, if
${\mathcal{N}}$ is a $d$-Euclidean structure over some space $\Omega$ with
$\phi=\phi_{\mathcal{N}}$ and $\operatorname{rk}({\mathcal{N}})=m$, then by
Lemma 3.5, there exists a $d$-realization $f$ from $\Omega$ to $\Omega$ and by
Lemma 3.6, items (ii) and (i), we have $\phi=\phi_{f^{*}({\mathcal{N}})}$ and
$\operatorname{rk}(\phi)\leq\operatorname{rk}(f^{*}({\mathcal{N}}))\leq\operatorname{rk}({\mathcal{N}})=m$
(as $f^{*}({\mathcal{N}})$ is a $0$-Euclidean structure). ∎

##  4 Uniqueness for $d$-theons

This section is devoted to proving the two easiest non-trivial implications of
Theorem 2.2, namely, the implications (ii)$\implies$(i), which says that any
$\ast$-$\ell$-independent limit satisfies $\texttt{UCouple}[\ell]$
(Proposition 4.4) and the implication (iv)$\implies$(i), which says that any
limit obtained as a quantifier-free definition of an independent coupling of
an $(\ell+1)$-quasirandom orientation with an $\ell$-independent limit
satisfies $\texttt{UCouple}[\ell]$ (Corollary 4.6).

The proof idea is the same as the proof that
$\texttt{Independence}[\ell]\implies\texttt{UCouple}[\ell]$ from [CR23,
Theorem 3.2]: we first show that if $\operatorname{rk}(\psi)\leq\ell$, then
every $d$-Euclidean structure ${\mathcal{N}}$ representing $\psi$ must be a.e.
equal to a $d$-Euclidean structure of rank at most $\ell$ (Lemma 4.3). This
means that for a coupling $\xi$ of a $\ast$-$\ell$-independent limit $\phi$
with $\psi$, we can represent $\xi$ by some $d$-Euclidean structure
${\mathcal{H}}$ such that the $\phi$ part is $\ell$-independent and the $\psi$
part has “almost everywhere” rank at most $\ell$; thus
$t_{\operatorname{ind}}(\mathord{-},{\mathcal{H}})$ behaves multiplicatively
so $\xi$ must be the independent coupling $\phi\otimes\psi$.

The main ingredient for such a proof is $d$-theon uniqueness that
characterizes when two $d$-theons represent the same limit. We start by
stating the $0$-theon uniqueness proved in [CR20]121212Let us note that the
statement in [CR20] is slightly different from the below in two aspects:
First, the measurability is with respect to the completion of the spaces
${\mathcal{E}}_{k}(\Omega)$ on the domains of the functions (i.e., the
analogue of Lebesgue measurability as opposed to Borel measurability);
however, one can get Borel measurability by simply changing the functions on a
zero measure set. Second, the notions of symmetric and measure-preserving are
not a.e. but everywhere notions in [CR20], but this is clearly not an issue
(see Lemma 3.6(ii))..

###### Theorem 4.1 (Theon Uniqueness [CR20, Theorems 3.9 and 3.11, Proposition
7.7]).

The following are equivalent for $T$-ons ${\mathcal{N}}^{1}$ and
${\mathcal{N}}^{2}$ over spaces $\Omega_{1}$ and $\Omega_{2}$, respectively.

  1. i.

We have $\phi_{{\mathcal{N}}^{1}}=\phi_{{\mathcal{N}}^{2}}$ (i.e.,
${\mathcal{N}}^{1}$ and ${\mathcal{N}}^{2}$ represent the same limit).

  2. ii.

For some (equivalently, every) atomless standard probability space $\Omega$,
there exist families $f=(f_{i})_{i\in\mathbb{N}_{+}}$ and
$g=(g_{i})_{i\in\mathbb{N}_{+}}$ of symmetric measure-preserving on h.o.a.
functions $f_{i}\colon{\mathcal{E}}_{i}(\Omega)\to\Omega_{1}$ and
$g_{i}\colon{\mathcal{E}}_{i}(\Omega)\to\Omega_{2}$ such that
$f^{*}({\mathcal{N}}^{1})$ is a.e. equal to $g^{*}({\mathcal{N}}^{2})$.

  3. iii.

There exists a family $h=(h_{i})_{i\in\mathbb{N}_{+}}$ of symmetric measure-
preserving on h.o.a. functions
($h_{i}\colon{\mathcal{E}}_{i}(\Omega_{1}\times\Omega_{1})\to\Omega_{2}$) such
that $h^{*}({\mathcal{N}}^{2})$ is a.e. equal to the the $T$-on
${\mathcal{H}}$ over $\Omega_{1}\times\Omega_{1}$ given by

$\displaystyle{\mathcal{H}}_{P}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{(x,y)\in{\mathcal{E}}_{k(P)}(\Omega\times\Omega)\mid
x\in{\mathcal{N}}^{1}_{P}\\}\qquad(P\in{\mathcal{L}}),$

where ${\mathcal{L}}$ is the language of $T$.

The avid reader might have noticed that we did not use almost inverse families
of $d$-realizations in any of the applications in Section 3; this is where
they will become useful: we will reduce $d$-theon uniqueness to theon
uniqueness via $d$-realizations and their almost inverse families.

###### Theorem 4.2 ($d$-Theon Uniqueness).

The following are equivalent for a $d_{1}$-$T$-on ${\mathcal{N}}^{1}$ over
$\Omega_{1}$ and a $d_{2}$-$T$-on ${\mathcal{N}}^{2}$ over $\Omega_{2}$.

  1. i.

We have $\phi_{{\mathcal{N}}^{1}}=\phi_{{\mathcal{N}}^{2}}$ (i.e.,
${\mathcal{N}}^{1}$ and ${\mathcal{N}}^{2}$ represent the same limit).

  2. ii.

For every $d\in\mathbb{N}$ and every atomless standard probability space
$\Omega$, there exist families $f=(f_{i})_{i\in\mathbb{N}_{+}}$ and
$g=(g_{i})_{i\in\mathbb{N}_{+}}$ of symmetric measure-preserving on h.o.a.
functions
$f_{i}\colon{\mathcal{E}}_{i}^{(d)}(\Omega)\to\Omega_{1}\times{\mathcal{O}}_{i}^{d_{1}}$
and
$g_{i}\colon{\mathcal{E}}_{i}^{(d)}(\Omega)\to\Omega_{2}\times{\mathcal{O}}_{i}^{d_{2}}$
such that $f^{*}({\mathcal{N}}^{1})$ is a.e. equal to
$g^{*}({\mathcal{N}}^{2})$.

  3. iii.

Item (iii) holds for some $d$ and $\Omega$.

  4. iv.

There exists a family $h=(h_{i})_{i\in\mathbb{N}_{+}}$ of symmetric measure-
preserving on h.o.a. functions
($h_{i}\colon{\mathcal{E}}_{i}^{(d_{1})}(\Omega_{1}\times\Omega_{1})\to\Omega_{2}\times{\mathcal{O}}_{i}^{d_{2}}$)
such that $h^{*}({\mathcal{N}}^{2})$ is a.e. equal to the $d_{1}$-$T$-on
${\mathcal{H}}$ over $\Omega_{1}\times\Omega_{1}$ given by

$\displaystyle{\mathcal{H}}_{P}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{(x,y,{\lhd})\in{\mathcal{E}}_{k(P)}^{(d_{1})}(\Omega\times\Omega)\mid(x,{\lhd})\in{\mathcal{N}}^{1}_{P}\\}\qquad(P\in{\mathcal{L}}),$

where ${\mathcal{L}}$ is the language of $T$.

###### Proof.

The implication (ii)$\implies$(iii) is trivial.

The implications (iii)$\implies$(i) and (iv)$\implies$(i) follow from Lemma
3.6(ii).

Let us now show the implication (i)$\implies$(ii).

By Lemma 3.5, for $j\in[2]$, there exists a $d_{j}$-realization $F_{j}$ from
$\Omega_{j}$ to $\Omega_{j}$. Since by Lemma 3.6(ii) we have

$\displaystyle\phi_{F_{1}^{*}({\mathcal{N}}^{1})}$
$\displaystyle=\phi_{{\mathcal{N}}^{1}}=\phi_{{\mathcal{N}}^{2}}=\phi_{F_{2}^{*}({\mathcal{N}}^{2})}$

for the $0$-$T$-ons $F_{1}^{*}({\mathcal{N}}^{1})$ and
$F_{2}^{*}({\mathcal{N}}^{2})$, by Theorem 4.1, there exist families
$f^{\prime}=(f^{\prime}_{i})_{i\in\mathbb{N}_{+}}$ and
$g^{\prime}=(g^{\prime}_{i})_{i\in\mathbb{N}_{+}}$ of symmetric measure-
preserving on h.o.a. functions
$f^{\prime}_{i}\colon{\mathcal{E}}_{i}(\Omega)\to\Omega_{1}$ and
$g^{\prime}_{i}\colon{\mathcal{E}}_{i}(\Omega)\to\Omega_{2}$ such that
$(f^{\prime})^{*}(F_{1}^{*}({\mathcal{N}}^{1}))$ is a.e. equal to
$(g^{\prime})^{*}(F_{2}^{*}({\mathcal{N}}^{2}))$.

Define
$f_{i}\colon{\mathcal{E}}_{i}^{(d)}(\Omega)\to\Omega_{1}\times{\mathcal{O}}_{i}^{d_{1}}$
and
$g_{i}\colon{\mathcal{E}}_{i}^{(d)}(\Omega)\to\Omega_{2}\times{\mathcal{O}}^{d_{2}}$
by

$\displaystyle f_{i}(x,{\leq})$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}((F_{1})_{i}\mathbin{\circ}\widehat{f^{\prime}}_{i})(x),$
$\displaystyle g_{i}(x,{\leq})$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}((F_{2})_{i}\mathbin{\circ}\widehat{g^{\prime}}_{i})(x).$

(Note that both $f_{i}$ and $g_{i}$ completely ignore the order variables.) It
is straightforward to check that $f_{i}$ and $g_{i}$ are symmetric and
measure-preserving on h.o.a. and that $f^{*}({\mathcal{N}}^{1})$ is a.e. equal
to $g^{*}({\mathcal{N}}^{2})$.

It remains to show the implication (i)$\implies$(iv).

Let $F_{1}$ be a $d_{1}$-realization from $\Omega_{1}$ to $\Omega_{1}$ and let
$G_{1}$ be an almost inverse family of $F$. Let also $F_{2}$ be a
$d_{2}$-realization from $\Omega_{2}$ to $\Omega_{2}$. Since by Lemma 3.6(ii)
we have

$\displaystyle\phi_{F_{1}^{*}({\mathcal{N}}^{1})}$
$\displaystyle=\phi_{{\mathcal{N}}^{1}}=\phi_{{\mathcal{N}}^{2}}=\phi_{F_{2}^{*}({\mathcal{N}}^{2})}$

for the $0$-$T$-ons $F_{1}^{*}({\mathcal{N}}^{1})$ and
$F_{2}^{*}({\mathcal{N}}^{2})$, by Theorem 4.2, there exists a family
$h^{\prime}=(h^{\prime}_{i})_{i\in\mathbb{N}_{+}}$ of symmetric measure-
preserving on h.o.a. functions
$h^{\prime}_{i}\colon{\mathcal{E}}_{i}(\Omega_{1}\times\Omega_{1})\to\Omega_{2}$
such that $(h^{\prime})^{*}(F_{2}^{*}({\mathcal{N}}^{2}))$ is a.e. equal to
the $T$-on ${\mathcal{H}}^{\prime}$ over $\Omega_{1}\times\Omega_{1}$ given by

$\displaystyle{\mathcal{H}}^{\prime}_{P}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{(x,y)\in{\mathcal{E}}_{k(P)}(\Omega_{1}\times\Omega_{1})\mid
x\in F_{1}^{*}({\mathcal{N}}^{1})_{P}\\}\qquad(P\in{\mathcal{L}}).$

Let now $H\colon\Omega_{1}\to\Omega_{1}\times\Omega_{1}$ be a measure-
isomorphism modulo $0$ and let $H^{1},H^{2}\colon\Omega_{1}\to\Omega_{1}$ be
its coordinate functions (which are measure-preserving) and define functions
$\widetilde{H}^{1}_{i},\widetilde{H}^{2}_{i}\colon{\mathcal{E}}_{i}(\Omega_{1})\to{\mathcal{E}}_{i}(\Omega_{1})$
by

$\displaystyle\widetilde{H}^{j}_{i}(y)_{A}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}H^{j}(y_{A})\qquad(j\in[2],y\in{\mathcal{E}}_{i}(\Omega_{1}),A\in
r(i)).$

Clearly $\widetilde{H}^{j}_{i}$ is measure-preserving.

Finally, define
$h_{i}\colon{\mathcal{E}}_{i}^{(d)}(\Omega_{1}\times\Omega_{1})\to\Omega_{2}\times{\mathcal{O}}_{i}^{d_{2}}$
by

$\displaystyle h_{i}(x,y,{\leq})$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}(F_{2})_{i}\Bigl{(}\widehat{h^{\prime}}_{i}\bigl{(}\widehat{(G_{1})}_{i}(x,\widetilde{H}^{1}_{i}(y),{\leq}),\widetilde{H}^{2}_{i}(y)\bigr{)}\Bigr{)}.$

It is straightforward to check that $h_{i}$ is symmetric and measure-
preserving on h.o.a.

Let us now show that $h^{*}({\mathcal{N}}^{2})$ is a.e. equal to the
$d_{1}$-$T$-on ${\mathcal{H}}$ over $\Omega_{1}\times\Omega_{1}$ given by

$\displaystyle{\mathcal{H}}_{P}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\\{(x,y,{\lhd})\in{\mathcal{E}}_{k(P)}^{(d_{1})}(\Omega\times\Omega)\mid(x,{\lhd})\in{\mathcal{N}}^{1}_{P}\\}\qquad(P\in{\mathcal{L}}).$

Fix $P\in{\mathcal{L}}$ and note that for
$(\mu_{1}\otimes\mu_{1})^{(d_{1})}$-almost every
$(x,y,{\leq})\in{\mathcal{E}}_{k(P)}^{(d_{1})}(\Omega_{1}\times\Omega_{1})$,
we have

$\displaystyle\\!\\!\\!\\!\\!\\!(x,y,{\leq})\in{\mathcal{H}}_{P}$
$\displaystyle\iff(x,{\leq})\in{\mathcal{N}}^{1}_{P}$
$\displaystyle\iff\widehat{(F_{1})}_{k(P)}\Bigl{(}\widehat{(G_{1})}_{k(P)}\bigl{(}x,\widetilde{H}_{k(P)}^{1}(y),{\leq}\bigr{)}\Bigr{)}\in{\mathcal{N}}^{1}_{P}$
$\displaystyle\iff\widehat{(G_{1})}_{k(P)}\bigl{(}x,\widetilde{H}_{k(P)}^{1}(y),{\leq}\bigr{)}\in
F_{1}^{*}({\mathcal{N}}^{1})_{P}$
$\displaystyle\iff\Bigl{(}\widehat{(G_{1})}_{k(P)}\bigl{(}x,\widetilde{H}_{k(P)}^{1}(y),{\leq}\bigr{)},\widetilde{H}^{2}_{k(P)}(y)\Bigr{)}\in{\mathcal{H}}^{\prime}_{P}$
$\displaystyle\iff\Bigl{(}\widehat{(G_{1})}_{k(P)}\bigl{(}x,\widetilde{H}_{k(P)}^{1}(y),{\leq}\bigr{)},\widetilde{H}^{2}_{k(P)}(y)\Bigr{)}\in(h^{\prime})^{*}(F_{2}^{*}({\mathcal{N}}^{2}))_{P}$
$\displaystyle\iff(\widehat{F_{2}})_{k(P)}\Biggl{(}\biggl{(}\widehat{h^{\prime}}_{k(P)}\Bigl{(}\widehat{(G_{1})}_{k(P)}\bigl{(}x,\widetilde{H}_{k(P)}^{1}(y),{\leq}\bigr{)},\widetilde{H}^{2}_{k(P)}(y)\Bigr{)}\biggr{)}\Biggr{)}\in{\mathcal{N}}^{2}_{P}$
$\displaystyle\iff\widehat{h}_{k(P)}(x,y,{\leq})\in{\mathcal{N}}^{2}_{P}$
$\displaystyle\iff(x,y,{\leq})\in h^{*}({\mathcal{N}}^{2})_{P},$

as desired, where the second equivalence follows since $G$ is an almost
inverse family to $F$ and $\widetilde{H}^{1}_{k(P)}$ is measure-preserving,
the fourth equivalence follows by the definition of ${\mathcal{H}}^{\prime}$,
the fifth equivalence follows since ${\mathcal{H}}^{\prime}$ is a.e. equal to
$(h^{\prime})^{*}(F_{2}^{*}({\mathcal{N}}^{2}))$ and the seventh equivalence
follows by the definition of $h$. ∎

The next lemma shows that except for zero measure changes, the notion of rank
does not depend on the representation.

###### Lemma 4.3.

If ${\mathcal{N}}$ is a $d$-Euclidean structure over $\Omega$, then it is a.e.
equal to a $d$-Euclidean structure ${\mathcal{N}}^{\prime}$ over $\Omega$ with
$\operatorname{rk}({\mathcal{N}}^{\prime})=\operatorname{rk}(\phi_{\mathcal{N}})$.
Moreover, if ${\mathcal{N}}$ is $\ell$-independent from some $\ell$, then
${\mathcal{N}}^{\prime}$ can be taken to also be $\ell$-independent.

###### Proof.

Write $\Omega=(X,\mu)$ and let
$r\stackrel{{\scriptstyle\text{def}}}{{=}}\operatorname{rk}(\phi_{\mathcal{N}})$.
Note that it suffices to prove the case when ${\mathcal{L}}$ has a single
predicate symbol $P$.

Let $k\stackrel{{\scriptstyle\text{def}}}{{=}}k(P)$ and define
$W\colon{\mathcal{E}}_{k,r}^{(d)}(\Omega)\to[0,1]$ by

$\displaystyle W(x)$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}\mu^{(d)}\left(\left\\{y\in\prod_{A\in\binom{[k]}{>r}}(X\times{\mathcal{O}}_{A}^{d})\;\middle|\;(x,y)\in{\mathcal{N}}_{P}\right\\}\right)$

and let

$\displaystyle{\mathcal{H}}_{P}$
$\displaystyle\stackrel{{\scriptstyle\text{def}}}{{=}}W^{-1}(1)\times\prod_{A\in\binom{[k]}{>r}}(X\times{\mathcal{O}}_{A}^{d}).$

Clearly $\operatorname{rk}({\mathcal{H}})\leq r$. Also note that if
${\mathcal{N}}$ is $\ell$-independent, then so is ${\mathcal{H}}$.

Thus, it suffices to show that ${\mathcal{N}}$ is a.e. equal to
${\mathcal{H}}$. In turn, this is equivalent to showing that $W$ is
$\\{0,1\\}$-valued $\mu^{(d)}$-a.e.

Since $\operatorname{rk}(\phi_{\mathcal{N}})\leq r$, we know that there exists
a $0$-Euclidean structure ${\mathcal{G}}$ over some space
$\Omega^{\prime}=(X^{\prime},\mu^{\prime})$ such that
$\phi_{\mathcal{G}}=\phi_{\mathcal{N}}$ and
$\operatorname{rk}({\mathcal{G}})=r$. By Theorem 4.2, there exist families
$f=(f_{i})_{i\in\mathbb{N}_{+}}$ and $g=(g_{i})_{i\in\mathbb{N}_{+}}$ of
symmetric measure-preserving on h.o.a. functions
$f_{i}\colon{\mathcal{E}}_{i}(\Omega)\to\Omega\times{\mathcal{O}}_{i}^{(d)}$
and $g_{i}\colon{\mathcal{E}}_{i}(\Omega)\to\Omega^{\prime}$ such that
$f^{*}({\mathcal{N}})$ is a.e. equal to $g^{*}({\mathcal{G}})$.

From the structure of the functions $\widehat{f}_{k}$ and $\widehat{g}_{k}$,
we can decompose them as

$\displaystyle\widehat{f}_{k}(x,y)$ $\displaystyle=(F_{1}(x),F_{2}(x,y)),$
$\displaystyle\widehat{g}_{k}(x,y)$ $\displaystyle=(G_{1}(x),G_{2}(x,y)),$

where $x\in{\mathcal{E}}_{k,r}(\Omega)$, $y\in X^{\binom{[k]}{>r}}$ and

$\displaystyle F_{1}\colon$
$\displaystyle{\mathcal{E}}_{k,r}(\Omega)\to{\mathcal{E}}_{k,r}^{(d)}(\Omega),$
$\displaystyle F_{2}\colon$
$\displaystyle{\mathcal{E}}_{k}(\Omega)\to\prod_{A\in\binom{[k]}{>r}}(X\times{\mathcal{O}}_{A}^{d}),$
$\displaystyle G_{1}\colon$
$\displaystyle{\mathcal{E}}_{k,r}(\Omega)\to{\mathcal{E}}_{k,r}(\Omega^{\prime}),$
$\displaystyle G_{2}\colon$ $\displaystyle{\mathcal{E}}_{k}(\Omega)\to
X^{\binom{[k]}{>r}}.$

The fact that the $f_{i}$ and $g_{i}$ are measure-preserving on h.o.a. implies
that $F_{1}$ and $G_{1}$ are measure-preserving and that for almost every
$x\in{\mathcal{E}}_{k,r}(\Omega)$, the restrictions $F_{2}(x,\mathord{-})$ and
$G_{2}(x,\mathord{-})$ are also measure-preserving.

Since $f^{*}({\mathcal{N}})$ is a.e. equal to $g^{*}({\mathcal{G}})$, by
Fubini’s Theorem, we get

$\displaystyle W(F_{1}(x))$ $\displaystyle=\mu\left(\left\\{y\in
X^{\binom{[k]}{>r}}\;\middle|\;(G_{1}(x),G_{2}(x,y))\in{\mathcal{G}}_{P}\right\\}\right)$

for $\mu$-almost every $x\in{\mathcal{E}}_{k,r}(\Omega)$. Since
$\operatorname{rk}({\mathcal{G}})=r$, the measure above can only be $0$ or $1$
(as $G_{2}(x,y)$ only contains coordinates indexed by sets in
$\binom{[k]}{>r}$). Using again that $F_{1}$ is measure-preserving, we
conclude that $W(z)\in\\{0,1\\}$ for $\mu^{(d)}$-almost every
$z\in{\mathcal{E}}_{k,r}^{(d)}(\Omega)$, as desired. ∎

We can finally prove the implication (ii)$\implies$(i) of Theorem 2.2 in the
proposition below.

###### Proposition 4.4 (Theorem 2.2(ii)$\implies$(i)).

If $\phi\in\operatorname{Hom}^{+}({\mathcal{A}}[T],\mathbb{R})$ is
$\ast$-$\ell$-independent, then $\phi$ satisfies $\texttt{UCouple}[\ell]$.

###### Proof.

Let ${\mathcal{L}}$ be the language of $T$. Since $\phi$ is
$\ast$-$\ell$-independent, there exist $d\in\mathbb{N}$ and an
$\ell$-independent $d$-$T$-on over some space $\Omega$ such that
$\phi=\phi_{\mathcal{N}}$.

Let now $\psi$ be any limit in some language ${\mathcal{L}}^{\prime}$ with
$\operatorname{rk}(\psi)\leq\ell$, let $\xi$ be a coupling of $\phi$ and
$\psi$ and let ${\mathcal{G}}$ be any $0$-Euclidean structure in