# Almost Bijective Parametrization of
$3\times 3$ Copositive Matrices

Hoon Hong and Ezra Nance

###### Abstract

In this work we take a deep dive into the cone of copositive $3\times 3$
matrices. In doing so we visualize the cone, make geometric observations about
it, and prove them. We then use these observations to parametrize the set. In
the process we run into issues with surjectivity, and overcome them by
resolving singularities and slightly shifting our original approach. We do all
of this to ultimately arrive at a novel parametrization of the $3\times 3$
copositive matrix cone which is surjective and almost injective, which we call
almost bijective.

##  1 Introduction

For many years positive semi-definite matrices have been studied, that is,
matrices whose associated quadratic form is always non-negative. These objects
have been interesting and fruitful to look into. They have applications in not
only matrix theory, but also in optimization [11] and differential equations
[9]. Furthermore, they can be used to answer the quadratic case of the famous
Hilbert’s 17th problem. It might seem amazing that these matrices have proven
to be so useful, but this really shouldn’t come as a surprise. The property of
being non-negative for all inputs is a very natural one. After all, we live in
a world where negative values don’t make much sense for many physical
quantities such as mass or time. So in the spirit of avoiding negative
quantities, copositive matrices were introduced.

######  Definition 1 (Copositive Matrix).

An $n\times n$ symmetric matrix $A$ is _copositive_ if $x^{\intercal}Ax\geq 0$
for all $x\geq 0$.

Notice that the non-negativity condition has now been extended to the input of
the quadratic form, not only the output. Copositive matrices were first
introduced by Motzkin [8], and their applications are quite similar to those
of positive semi-definite matrices for many of the same reasons [6]. While
copositive matrices have been studied much less than positive semi-definite
ones, quite a bit of research has been done on the implicitization problem
[10]. That is, given a symmetric matrix how can one decide if it is copositive
or not? While we will use some of these results, our goal instead is
parametrization. In other words, how do we generate all of the copositive
matrices?

######  Definition 2 (Cone of Copositive Matrices).

Let $\mathcal{CF}_{n}\subset\mathbb{R}^{\frac{n(n+1)}{2}}$ be the set of
$n\times n$ copositive matrices.

Most of the results in this area are focused on parametrizing special subsets
of the copositive cone, see [4], [7], and [1]. There are more general results
involving the parametrization of a general semialgebraic set like [5].
However, these results would be difficult for us to implement. Furthermore,
these generalized results are based off the Cylindrical Algebraic
Decomposition (CAD), which yield piecewise results. In this work we wish to
avoid piecewise parametrizations as much as possible.

Similar to the positive semi-definite matrices the set of copositive matrices
of a particular size form a closed, convex cone. There is a classic result [3]
which states that for $n<5$,

$\mathcal{CF}_{n}=\left\\{A+B:A\text{ is positive semi-definite and }B\text{
has non-negative entries}\right\\}.$

This is a good parametrization of the set, however, we will demand a bit more.
Ideally, we would like to parametrize the set injectively, and we can see that
using this method we will have $n(n+1)$ parameters for an
$\frac{n(n+1)}{2}$-dimensional set. Therefore, we have no hope of this being
injective. This is where we will make progress.

As is often the case in mathematics we will begin by considering a small case.
When $n=2$ it doesn’t take much work to see that

$\mathcal{CF}_{2}=\left\\{\begin{bmatrix}t_{1}^{2}&-t_{1}t_{2}+\lambda\\\
-t_{1}t_{2}+\lambda&t_{2}^{2}\end{bmatrix}:t_{1},t_{2},\lambda\geq
0\right\\}.$

Furthermore, this parametrization is injective. This sets the standard for
what we want as $n$ goes up. Naturally, we wish to parametrize
$\mathcal{CF}_{3}$ next which brings us to the main problem in the paper.

######  Problem 3.

Find a parametrization map $\Phi:U\to\mathcal{CF}_{3}$ such that

  1. 1.

The domain $U$ is an easily described.

  2. 2.

The map $\Phi$ is surjective.

  3. 3.

The map $\Phi$ is (almost) injective.

We will address this problem by using the geometry of $\mathcal{CF}_{3}$ to
inform our intuition and progress from there.

##  2 Visualizing $\mathcal{CF}_{3}$

In order the visualize $\mathcal{CF}_{3}\subset\mathbb{R}^{6}$, we will need
to take a 3-dimensional slice. However, we would like for this slice to be
“generic” in some sense. When studying copositive matrices it is quite common
to scale the diagonal elements of the matrix to be 1 since

$\begin{bmatrix}a_{11}&a_{12}&a_{13}\\\ a_{12}&a_{22}&a_{23}\\\
a_{13}&a_{23}&a_{33}\end{bmatrix}\in\mathcal{CF}_{3}\iff\begin{bmatrix}1&\frac{a_{12}}{\sqrt{a_{11}a_{22}}}&\frac{a_{13}}{\sqrt{a_{11}a_{33}}}\\\
\frac{a_{12}}{\sqrt{a_{11}a_{22}}}&1&\frac{a_{23}}{\sqrt{a_{22}a_{33}}}\\\
\frac{a_{13}}{\sqrt{a_{11}a_{33}}}&\frac{a_{23}}{\sqrt{a_{22}a_{33}}}&1\end{bmatrix}\in\mathcal{CF}_{3}.$

This works as long as no $a_{ii}=0$. In other words, this almost always works.
With this property in mind we now will define a particular slice of
$\mathcal{CF}_{3}$.

######  Definition 4.

Let $\widehat{\mathcal{CF}}_{3}$ be the subset of $\mathcal{CF}_{3}$
consisting of matrices whose diagonal elements equal 1, that is,

$\widehat{\mathcal{CF}}_{3}=\left\\{A\in\mathcal{CF}_{3}:A=\begin{bmatrix}1&a_{12}&a_{13}\\\
a_{12}&1&a_{23}\\\ a_{13}&a_{23}&1\end{bmatrix}\right\\}.$

Note that $\widehat{\mathcal{CF}}_{3}$ is a 3-dimensional, closed, convex
cone. Thus, we can visualize it. In Figure 1 we can see the result of sampling
the set.

Figure 1: Sampled Points from $\widehat{\mathcal{CF}}_{3}$

From visual inspection we can pick out a few notable features:

  1. 1.

The boundary of $\widehat{\mathcal{CF}}_{3}$ seems to be comprised of 4
discrete pieces: 3 flat pieces and 1 curved piece.

  2. 2.

The set appears to be bounded by the cone formed by the inequalities
$a_{ij}\geq-1$ for all $i\neq j$.

  3. 3.

The curved side looks like it is bounded by the boundary of a 2-dimensional
simplex.

These observations are much clearer in Figure 2 where we have color coded the
parts of the boundary. The red, blue, and green portions are the flat pieces,
and the gray portion is the curved 2-dimensional simplex. It should be noted
that the gaps between these pieces are not really there. They are a result of
using software to plot the boundary. We can confirm observation 2 in the
following lemma.

Figure 2: Pieces of the boundary of $\widehat{\mathcal{CF}}_{3}$

######  Lemma 5.

Let $A\in\widehat{\mathcal{CF}}_{3}$. Then $a_{12},a_{13},a_{23}\geq-1$.

###### Proof.

Let $A\in\widehat{\mathcal{CF}}_{3}$. By way of contradiction assume that
$a_{12}<-1$. Thus, $a_{12}=-1-\varepsilon$ for some $\varepsilon>0$. Then the
associated quadratic form is

$\displaystyle
x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+2a_{12}x_{1}x_{2}+2a_{13}x_{1}x_{3}+2a_{23}x_{2}x_{3}$
$\displaystyle=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+-2(1+\varepsilon)x_{1}x_{2}+2a_{13}x_{1}x_{3}+2a_{23}x_{2}x_{3}$
$\displaystyle=(x_{1}-x_{2})^{2}+x_{3}^{2}-2\varepsilon
x_{1}x_{2}+2a_{13}x_{1}x_{3}+2a_{23}x_{2}x_{3}.$

Evaluating this polynomial at $x=\left(1,1,0\right)$ gives us
$-2\varepsilon<0$. Therefore, $A\notin\widehat{\mathcal{CF}}_{3}$, which is a
contradiction. By symmetry we also have that $a_{13}\geq-1$ and
$a_{23}\geq-1$. ∎

Lemma 5 as well as looking at a picture like Figure 2 suggests a method for
parametrizing this set. We can take a portion of $\widehat{\mathcal{CF}}_{3}$
and project it out from the point $(-1,-1,-1)$. From visual inspection it
appears that if we take the curved portion of the boundary and project it out,
we should be able to recover all of $\widehat{\mathcal{CF}}_{3}$, see Figure
3.

Figure 3: Projection of the curved boundary of $\widehat{\mathcal{CF}}_{3}$

Thus, we have our plan of action. First we will parametrize this curved
portion of the boundary of $\widehat{\mathcal{CF}}_{3}$. Next we will project
it out from the point $(-1,-1,-1)$ to get the entirety of
$\widehat{\mathcal{CF}}_{3}$. Finally we will scale the diagonal elements to
“glue” the slices together and form $\mathcal{CF}_{3}$.

##  3 Parametrizing the Curved Boundary of $\widehat{\mathcal{CF}}_{3}$

Note that for a matrix to be on the boundary of $\widehat{\mathcal{CF}}_{3}$,
its quadratic form must evaluate to 0 on some non-negative vector. With that
in mind, we will begin by trying to figure out what the defining property is
for being in this curved boundary. Looking at this set we can pull out a
couple of examples.

$A=\begin{bmatrix}1&-1&-1\\\ -1&1&1\\\ -1&1&1\end{bmatrix}\hskip
20.00003ptB=\begin{bmatrix}1&-1/2&-1/2\\\ -1/2&1&-1/2\\\
-1/2&-1/2&1\end{bmatrix}$

We will contrast these with a matrix which is on the boundary but not the
curved portion.

$C=\begin{bmatrix}1&-1&1\\\ -1&1&1\\\ 1&1&1\end{bmatrix}$

One can check that all three of these matrices are on the boundary of
$\widehat{\mathcal{CF}}_{3}$, but one difference is that $|A|=|B|=0$, whereas
$|C|\neq 0$. However, being copositive and singular isn’t quite enough. Note
that the matrix

$\begin{bmatrix}1&1/2&1/2\\\ 1/2&1&1/2\\\ 1/2&1/2&1\end{bmatrix}$

is singular and copositive but is in the interior of
$\widehat{\mathcal{CF}}_{3}$. Analyzing these matrices a little more we can
see that not only are $A$ and $B$ singular, but they have a null vector which
has non-negative components. This gives us the following lemma.

######  Lemma 6.

Let $A\in\partial\widehat{\mathcal{CF}}_{3}$ with
$a_{12}+a_{13}+a_{23}\leq-1$. Then $A$ is singular and has a null vector with
non-negative components.

###### Proof.

Since $A\in\partial\widehat{\mathcal{CF}}_{3}$, we have $y^{\intercal}Ay=0$
for some $y\in\mathbb{R}_{\geq 0}\setminus\\{0\\}$. First we will consider
what happens when a component of $y$ is zero. So without loss of generality
assume that $y_{1}=0$. Then we have

$\displaystyle y^{\intercal}Ay$
$\displaystyle=y_{2}^{2}+2a_{23}y_{2}y_{3}+y_{3}^{2}$
$\displaystyle=(y_{2}-y_{3})^{2}+2(a_{23}+1)y_{2}y_{3}.$

Note that if $y_{2}$ or $y_{3}$ is zero, then we get a contradiction with
$y=0$. Thus, $y_{2}$ and $y_{3}$ are both non-zero, and we can solve for
$a_{23}$.

$a_{23}=-\frac{(y_{2}-y_{3})^{2}}{2y_{2}y_{3}}-1$

From this we can see that $a_{23}\leq-1$, but from Lemma 5 we see that
$a_{23}\geq-1$. Hence, $a_{23}$ must equal $-1$. To achieve this we must have
have $y_{2}=y_{3}=t>0$. Furthermore, the condition
$a_{12}+a_{13}+a_{23}\leq-1$ becomes the condition $a_{12}+a_{13}\leq 0$. With
these in mind we arrive at

$Ay=\begin{bmatrix}a_{12}y_{2}+a_{13}y_{3}\\\ y_{2}-y_{3}\\\
-y_{2}+y_{3}\end{bmatrix}=t\begin{bmatrix}a_{12}+a_{13}\\\ 0\\\
0\end{bmatrix}.$

From here we will rule out the possibility of $a_{12}+a_{13}<0$. To see this
we will consider the quadratic form on a general $x$ and get

$x_{1}^{2}+(x_{2}-x_{3})^{2}+2a_{12}x_{1}x_{2}+2a_{13}x_{1}x_{3}.$

Evaluating this on
$x=\left(1,-\frac{1}{a_{12}+a_{13}},-\frac{1}{a_{12}+a_{13}}\right)$ we get
the value $1-2=-1<0$. This contradicts $A$ being copositive, and we finish the
first case. When $y_{1}=0$, $A$ is singular with a null vector of
$(0,t,t)\in\mathbb{R}_{\geq 0}\setminus\\{0\\}$. We will have symmetric
arguments if a different component of $y$ is zero.

For the next case assume that $y\in\mathbb{R}_{>0}$. Here we will show that
$y^{\intercal}Ay=0$ implies that $Ay=0$. To proceed we will assume that
$y^{\intercal}Ay=0$ and $Ay\neq 0$, and we will arrive at a contradiction.
Since $Ay\neq 0$ there exists some $i\in\\{1,2,3\\}$ such that the $i$th
component of the vector $(Ay)$ is non-zero. Here we have to split into two
cases.

Assume that $(Ay)_{i}>0$. Let $\varepsilon\in\mathbb{R}$ be such that
$0<\varepsilon<\min\\{2(Ay)_{i},y_{i}\\}$. With this setup we have two
valuable properties. We have $\varepsilon-2(Ay)_{i}<0$, which implies
$\varepsilon^{2}-2\varepsilon(Ay)_{i}<0$. Also, we have $y-\varepsilon
e_{i}\in\mathbb{R}_{>0}$. With these in mind we have

$\displaystyle(y-\varepsilon e_{i})^{\intercal}A(y-\varepsilon e_{i})$
$\displaystyle=y^{\intercal}Ay-\varepsilon e_{i}^{\intercal}Ay-\varepsilon
y^{\intercal}Ae_{i}+\varepsilon^{2}e_{i}^{\intercal}Ae_{i}$
$\displaystyle=-\varepsilon(Ay)_{i}-\varepsilon(Ay)_{i}+\varepsilon^{2}$
$\displaystyle<0.$

This contradicts $A$ being copositive.

For the last case assume that $(Ay)_{i}<0$. Let $\varepsilon\in\mathbb{R}$ be
such that $0<\varepsilon<\min\\{-2(Ay)_{i},y_{i}\\}$. Similar to the last case
now we have $\varepsilon^{2}+2\varepsilon(Ay)_{i}<0$ and $y+\varepsilon
e_{i}\in\mathbb{R}_{>0}$. Now we calculate the quadratic form

$\displaystyle(y+\varepsilon e_{i})^{\intercal}A(y+\varepsilon e_{i})$
$\displaystyle=y^{\intercal}Ay+\varepsilon e_{i}^{\intercal}Ay+\varepsilon
y^{\intercal}Ae_{i}+\varepsilon^{2}e_{i}^{\intercal}Ae_{i}$
$\displaystyle=\varepsilon(Ay)_{i}+\varepsilon(Ay)_{i}+\varepsilon^{2}$
$\displaystyle<0,$

and we arrive at our contradiction. ∎

This leads us to an idea. Since all of the matrices on this curved surface
have a non-negative null vector, we can use the coordinates of that null
vector as our parameters. If we assume that $p\geq 0$ is a null vector, then
we have the following system.

$\begin{bmatrix}1&a_{12}&a_{13}\\\ a_{12}&1&a_{23}\\\
a_{13}&a_{23}&1\end{bmatrix}\begin{bmatrix}p_{1}\\\ p_{2}\\\
p_{3}\end{bmatrix}=\begin{bmatrix}0\\\ 0\\\ 0\end{bmatrix}$

Luckily, we can uniquely solve this system for $a_{ij}$ as long as $p>0$. This
leads to the following lemma.

######  Lemma 7.

Let $p\in\mathbb{R}^{3}_{>0}$ and $A$ be a $3\times 3$ real symmetric matrix
with 1’s along the diagonal. Then $Ap=0$ if and only if

$a_{12}=\frac{p_{3}^{2}-(p_{1}^{2}+p_{2}^{2})}{2p_{1}p_{2}},\hskip
20.00003pta_{13}=\frac{p_{2}^{2}-(p_{1}^{2}+p_{3}^{2})}{2p_{1}p_{3}},\hskip
20.00003pta_{23}=\frac{p_{1}^{2}-(p_{2}^{2}+p_{3}^{2})}{2p_{2}p_{3}}.$

###### Proof.

We have

$A=\begin{bmatrix}1&a_{12}&a_{13}\\\ a_{12}&1&a_{23}\\\
a_{13}&a_{23}&1\end{bmatrix}.$

Note that $Ap=0$ if and only if

$Ap=\begin{bmatrix}p_{1}+a_{12}p_{2}+a_{13}p_{3}\\\
a_{12}p_{1}+p_{2}+a_{23}p_{3}\\\
a_{13}p_{1}+a_{23}p_{2}+p_{3}\end{bmatrix}=\begin{bmatrix}0\\\ 0\\\
0\end{bmatrix}.$

Thus, we have the system

$\begin{bmatrix}p_{2}&p_{3}&0\\\ p_{1}&0&p_{3}\\\
0&p_{1}&p_{2}\end{bmatrix}\begin{bmatrix}a_{12}\\\ a_{13}\\\
a_{23}\end{bmatrix}=-\begin{bmatrix}p_{1}\\\ p_{2}\\\ p_{3}\end{bmatrix}.$

Since $p\in\mathbb{R}^{3}_{>0}$ the system has a unique solution, which is

$a_{12}=\frac{p_{3}^{2}-(p_{1}^{2}+p_{2}^{2})}{2p_{1}p_{2}},\hskip
20.00003pta_{13}=\frac{p_{2}^{2}-(p_{1}^{2}+p_{3}^{2})}{2p_{1}p_{3}},\hskip
20.00003pta_{23}=\frac{p_{1}^{2}-(p_{2}^{2}+p_{3}^{2})}{2p_{2}p_{3}}.$

∎

Given Lemma 7 we have a parametrization for $3\times 3$ real symmetric
matrices with 1’s along the diagonal with a positive null vector:

$\begin{bmatrix}1&\frac{p_{3}^{2}-(p_{1}^{2}+p_{2}^{2})}{2p_{1}p_{2}}&\frac{p_{2}^{2}-(p_{1}^{2}+p_{3}^{2})}{2p_{1}p_{3}}\\\
\frac{p_{3}^{2}-(p_{1}^{2}+p_{2}^{2})}{2p_{1}p_{2}}&1&\frac{p_{1}^{2}-(p_{2}^{2}+p_{3}^{2})}{2p_{2}p_{3}}\\\
\frac{p_{2}^{2}-(p_{1}^{2}+p_{3}^{2})}{2p_{1}p_{3}}&\frac{p_{1}^{2}-(p_{2}^{2}+p_{3}^{2})}{2p_{2}p_{3}}&1\end{bmatrix}.$

However, it’s possible that not all of these matrices are copositive. In order
to check this, we need a sufficient condition for copositivity. Luckily, we
don’t need a sufficient condition for a general $3\times 3$ to be copositive,
but we only have to worry about singular matrices with a positive null vector.
Under these constraints we have a nice way to check copositivity.

######  Lemma 8.

Let $A$ be a real symmetric matrix such that $Ap=0$ for some
$p\in\mathbb{R}^{n}_{>0}$. Then $A\in\mathcal{CF}_{n}$ if and only if $A$ is
positive semi-definite.

###### Proof.

If $A$ is positive semi-definite, then $x^{\intercal}Ax\geq 0$. Thus,
$A\in\mathcal{CF}_{n}$. For the other direction assume that $A$ is not
positive semi-definite. Then there exists some $q\in\mathbb{R}^{3}$ such that
$q^{\intercal}Aq<0$. Note that there exists some $\varepsilon>0$ such that
$p+\varepsilon q\in\mathbb{R}^{3}_{>0}$. Then we have

$\displaystyle(p+\varepsilon q)^{\intercal}A(p+\varepsilon q)$
$\displaystyle=p^{\intercal}Ap+\varepsilon p^{\intercal}Aq+\varepsilon
q^{\intercal}Ap+\varepsilon^{2}q^{\intercal}Aq$
$\displaystyle=\varepsilon^{2}q^{\intercal}Aq$ $\displaystyle<0.$

Hence $A$ is not copositive. ∎

So in this special case checking copositivity is the same as checking if the
matrix is positive semi-definite. Thus, we can check all of the principal
minors. Note that by construction the determinant of the whole matrix is 0,
and all of the $1\times 1$ principal minors are 1. Therefore, we really only
need to check the $2\times 2$ principal minors. Doing so gives us the
following.

$\displaystyle\begin{vmatrix}1&\frac{p_{3}^{2}-(p_{1}^{2}+p_{2}^{2})}{2p_{1}p_{2}}\\\
\frac{p_{3}^{2}-(p_{1}^{2}+p_{2}^{2})}{2p_{1}p_{2}}&1\end{vmatrix}$
$\displaystyle=-\frac{1}{4p_{1}^{2}p_{2}^{2}}(p_{1}+p_{2}+p_{3})(p_{1}-p_{2}+p_{3})(p_{1}+p_{2}-p_{3})(p_{1}-p_{2}-p_{3})$
$\displaystyle\begin{vmatrix}1&\frac{p_{2}^{2}-(p_{1}^{2}+p_{3}^{2})}{2p_{1}p_{3}}\\\
\frac{p_{2}^{2}-(p_{1}^{2}+p_{3}^{2})}{2p_{1}p_{3}}&1\end{vmatrix}$
$\displaystyle=-\frac{1}{4p_{1}^{2}p_{3}^{2}}(p_{1}+p_{2}+p_{3})(p_{1}-p_{2}+p_{3})(p_{1}+p_{2}-p_{3})(p_{1}-p_{2}-p_{3})$
$\displaystyle\begin{vmatrix}1&\frac{p_{1}^{2}-(p_{2}^{2}+p_{3}^{2})}{2p_{2}p_{3}}\\\
\frac{p_{1}^{2}-(p_{2}^{2}+p_{3}^{2})}{2p_{2}p_{3}}&1\end{vmatrix}$
$\displaystyle=-\frac{1}{4p_{2}^{2}p_{3}^{2}}(p_{1}+p_{2}+p_{3})(p_{1}-p_{2}+p_{3})(p_{1}+p_{2}-p_{3})(p_{1}-p_{2}-p_{3})$

The sign of each of these minors is determined by signs of the factors
$(p_{1}+p_{2}+p_{3}),$ $(p_{1}-p_{2}+p_{3}),$ $(p_{1}+p_{2}-p_{3}),$ and
$(p_{1}-p_{2}-p_{3})$. Note that $(p_{1}+p_{2}+p_{3})>0$ for all $p>0$. So we
arrive at a result. Namely, the singular matrices we have parametrized are
copositive if and only if
$(p_{1}-p_{2}+p_{3})(p_{1}+p_{2}-p_{3})(p_{1}-p_{2}-p_{3})\leq 0$. This is
what we must answer now, which leads into the next lemma.

######  Lemma 9.

Let $A$ be a $3\times 3$ real symmetric matrix with 1’s along the diagonal,
and let $p$ be a positive null vector of $A$. Then
$A\in\widehat{\mathcal{CF}}_{3}$ if and only if

$p\in\operatorname{cone}\left\\{e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\right\\}\setminus\left(\operatorname{span}\\{e_{1}+e_{2}\\}\cup\operatorname{span}\\{e_{1}+e_{3}\\}\cup\operatorname{span}\\{e_{2}+e_{3}\\}\right).$

###### Proof.

From the discussion above we know that $A\in\widehat{\mathcal{CF}}_{3}$ if and
only if

$(p_{1}-p_{2}+p_{3})(p_{1}+p_{2}-p_{3})(p_{1}-p_{2}-p_{3})\leq 0.$

So we must consider the signs of the following expressions.

$\displaystyle(p_{1}-p_{2}-p_{3})$ (1) $\displaystyle(p_{1}-p_{2}+p_{3})$ (2)
$\displaystyle(p_{1}+p_{2}-p_{3})$ (3)

We now have cases.

  1. 1.

Assuming that expression (1), (2), or (3) is equal to zero gives us
$p_{1}=p_{2}+p_{3}$, $p_{2}=p_{1}+p_{3}$, or $p_{3}=p_{1}+p_{2}$ respectively.
In all three of these cases

$p\in\operatorname{cone}\left\\{e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\right\\}\setminus\left(\operatorname{span}\\{e_{1}+e_{2}\\}\cup\operatorname{span}\\{e_{1}+e_{3}\\}\cup\operatorname{span}\\{e_{2}+e_{3}\\}\right).$

  2. 2.

Assume that expressions (1), (2), and (3) are all less than zero. Then adding
the inequalities formed by (2) and (3) gives us $2p_{1}<0$, which is a
contradiction.

  3. 3.

Assume that expression (3) is less than zero while expressions (1) and (2) are
greater than zero. Then negating inequality (2) and adding it to (3) gives us
$2p_{2}<0$, a contradiction.

  4. 4.

Assume that expression (2) is less than zero while expressions (1) and (3) are
greater than zero. Then negating inequality (1) and adding it to (2) gives us
$2p_{3}<0$, a contradiction.

  5. 5.

Assume that expression (1) is less than zero while expressions (2) and (3) are
greater than zero. These inequalities imply that
$p\in\operatorname{cone}\\{e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\\}$. However,
$p$ being strictly positive implies that
$p\notin\operatorname{span}\\{e_{1}+e_{2}\\}\cup\operatorname{span}\\{e_{1}+e_{3}\\}\cup\operatorname{span}\\{e_{2}+e_{3}\\}.$

∎

With Lemma 9 in hand we can cut down our domain to come from the specified to
domain to arrive at a parametrization of the curved boundary. Furthermore,
since each expression for $a_{ij}$ is homogeneous and quadratic in the
numerator and denominator, the length of the positive null vector chosen has
no effect on the copositive matrix generated. Thus, we can assume that the
null vector is from a simplex to simplify our domain even further.

Figure 4: Possible null vectors for $\widehat{\mathcal{CF}}_{3}$

Since our domain now is a portion of a simplex. We will do a change of
variables so that it is just a simplex. We will do the change of variables:

$p_{1}=t_{2}+t_{3},\hskip 10.00002ptp_{2}=t_{1}+t_{3},\hskip
10.00002ptp_{3}=t_{1}+t_{2},$

and now our domain is the standard simplex, $\Delta_{3}$, without its corners.
Following this change of variables through gives us matrices of the following
form.

$\begin{bmatrix}1&\frac{p_{3}^{2}-(p_{1}^{2}+p_{2}^{2})}{2p_{1}p_{2}}&\frac{p_{2}^{2}-(p_{1}^{2}+p_{3}^{2})}{2p_{1}p_{3}}\\\
\frac{p_{3}^{2}-(p_{1}^{2}+p_{2}^{2})}{2p_{1}p_{2}}&1&\frac{p_{1}^{2}-(p_{2}^{2}+p_{3}^{2})}{2p_{2}p_{3}}\\\
\frac{p_{2}^{2}-(p_{1}^{2}+p_{3}^{2})}{2p_{1}p_{3}}&\frac{p_{1}^{2}-(p_{2}^{2}+p_{3}^{2})}{2p_{2}p_{3}}&1\end{bmatrix}\mapsto\begin{bmatrix}1&\frac{2t_{1}t_{2}}{(1-t_{1})(1-t_{2})}-1&\frac{2t_{1}t_{3}}{(1-t_{1})(1-t_{3})}-1\\\
\frac{2t_{1}t_{2}}{(1-t_{1})(1-t_{2})}-1&1&\frac{2t_{2}t_{3}}{(1-t_{2})(1-t_{3})}-1\\\
\frac{2t_{1}t_{3}}{(1-t_{1})(1-t_{3})}-1&\frac{2t_{2}t_{3}}{(1-t_{2})(1-t_{3})}-1&1\end{bmatrix}$

We can formalize this in the following theorem.

######  Theorem 10.

The map
$\Psi:\operatorname{int}(\Delta_{3})\to\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}<-1\\}$
defined by

$(t_{1},t_{2},t_{3})\mapsto\begin{bmatrix}1&\frac{2t_{1}t_{2}}{(1-t_{1})(1-t_{2})}-1&\frac{2t_{1}t_{3}}{(1-t_{1})(1-t_{3})}-1\\\
\frac{2t_{1}t_{2}}{(1-t_{1})(1-t_{2})}-1&1&\frac{2t_{2}t_{3}}{(1-t_{2})(1-t_{3})}-1\\\
\frac{2t_{1}t_{3}}{(1-t_{1})(1-t_{3})}-1&\frac{2t_{2}t_{3}}{(1-t_{2})(1-t_{3})}-1&1\end{bmatrix}$

is $\Psi$ bijective.

###### Proof.

As discussed above, $\Psi$ is a composition. Namely, $\Psi=f\circ g$, where

$g:\operatorname{int}(\Delta_{3})\to\operatorname{int}\left(\operatorname{conv}\\{e_{1}+e_{2},e_{1}+e_{2},e_{2}+e_{3}\\}\right)$

is defined by $g(t_{1},t_{2},t_{3})=(t_{2}+t_{3},t_{1}+t_{3},t_{1}+t_{2})$,
and

$f:\operatorname{int}\left(\operatorname{conv}\\{e_{1}+e_{2},e_{1}+e_{2},e_{2}+e_{3}\\}\right)\to\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}<-1\\}$

is defined by

$f(p_{1},p_{2},p_{3})=\begin{bmatrix}1&\frac{p_{3}^{2}-(p_{1}^{2}+p_{2}^{2})}{2p_{1}p_{2}}&\frac{p_{2}^{2}-(p_{1}^{2}+p_{3}^{2})}{2p_{1}p_{3}}\\\
\frac{p_{3}^{2}-(p_{1}^{2}+p_{2}^{2})}{2p_{1}p_{2}}&1&\frac{p_{1}^{2}-(p_{2}^{2}+p_{3}^{2})}{2p_{2}p_{3}}\\\
\frac{p_{2}^{2}-(p_{1}^{2}+p_{3}^{2})}{2p_{1}p_{3}}&\frac{p_{1}^{2}-(p_{2}^{2}+p_{3}^{2})}{2p_{2}p_{3}}&1\end{bmatrix}.$

It can be easily checked that the linear map $g$ is bijective. Now we will
check that $f$ is bijective, completing the proof. Note that $f$ is bijective
if all matrices in
$\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}<-1\\}$ can be
uniquely determined by a single null vector. We will begin by checking the
rank of matrices in the image of $f$. This map $f$ was specifically chosen so
that $|f(p)|=0$. So clearly the rank of $f(p)$ is either 1 or 2. For now let
us assume that the rank is 1. Then by following the discussion in the proof of
Lemma 9 we see that at least one of the following equations must be true to
force the $2\times 2$ minors to be 0.

$\displaystyle p_{1}-p_{2}-p_{3}$ $\displaystyle=0$ $\displaystyle
p_{1}-p_{2}+p_{3}$ $\displaystyle=0$ $\displaystyle p_{1}+p_{2}-p_{3}$
$\displaystyle=0$

This implies $p_{1}=p_{2}+p_{3}$, $p_{2}=p_{1}+p_{3}$, or $p_{3}=p_{1}+p_{2}$.
All of these conditions occur on the boundary of
$\operatorname{conv}\\{e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\\}$, which is not
in the domain of $f$. Hence, $f(p)$ is rank 2 for all $p$ in the domain.

This is actually all we need. If $f(p)=f(p^{\prime})$ with $p\neq p^{\prime}$.
Then because of our choice of domain, $p$ and $p^{\prime}$ are linearly
independent. Hence, $f(p)$ has at least a 2 dimensional null space, but this
contradicts $f(p)$ being rank 2. Thus, $f$ is injective. Based on Lemma 9 we
know that if the domain of $f$ is expanded to be
$\operatorname{conv}\\{e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\\}\setminus\\{e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\\}$,
then its image would be a superset of
$\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}<-1\\}$. So to
check surjectivity we will show that all of the points left out of the domain
of $f$ do not map to points in the codomain. From symmetry we only need to see
where $f$ maps points which satisfy $p_{1}=p_{2}+p_{3}$. If we make this
substitution we see that

$f(p_{2}+p_{3},p_{2},p_{3})=\begin{bmatrix}1&-1&-1\\\ -1&1&1\\\
-1&1&1\end{bmatrix},$

which does not satisfy the condition that $a_{12}+a_{13}+a_{23}<-1$. Thus, $f$
is surjective.

∎

##  4 Resolving Singularities in the Boundary Parametrization

The parametrization in Theorem 10 works for almost all points on this curved
boundary. Unfortunately, we miss out on most of its limit points. For
instance, we cannot obtain the matrix

$\begin{bmatrix}1&-1&0\\\ -1&1&0\\\ 0&0&1\end{bmatrix}.$

Furthermore, the domain in Theorem 10 is slightly awkward. In this section we
will fix both of these issues. We will change our map so that it is defined
everywhere on $\Delta_{3}$, and in doing so we will pick up the desired limit
points so that we will be parametrizing the closed set
$\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}\leq-1\\}$. To
do this we will dive a little deeper into the limit points of our
parametrization

$\phi:\operatorname{conv}\\{e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\\}\setminus\\{e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\\}\to\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}\leq-1\\}$
$(p_{1},p_{2},p_{3})\mapsto\begin{bmatrix}1&\frac{p_{3}^{2}-(p_{1}^{2}+p_{2}^{2})}{2p_{1}p_{2}}&\frac{p_{2}^{2}-(p_{1}^{2}+p_{3}^{2})}{2p_{1}p_{3}}\\\
\frac{p_{3}^{2}-(p_{1}^{2}+p_{2}^{2})}{2p_{1}p_{2}}&1&\frac{p_{1}^{2}-(p_{2}^{2}+p_{3}^{2})}{2p_{2}p_{3}}\\\
\frac{p_{2}^{2}-(p_{1}^{2}+p_{3}^{2})}{2p_{1}p_{3}}&\frac{p_{1}^{2}-(p_{2}^{2}+p_{3}^{2})}{2p_{2}p_{3}}&1\end{bmatrix}.$

As we saw in Theorem 10, this map is nicely behaved when we restrict the
domain to be just the interior of
$\operatorname{conv}\\{e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\\}$, that is, when
the matrix has a null vector with strictly positive components. So now let us
consider matrices in $\widehat{\mathcal{CF}}_{3}$ with null vectors which have
0 components. So we will assume $A\in\widehat{\mathcal{CF}}_{3}$ and that
$Ap=0$ for some $p\in\mathbb{R}^{3}_{\geq 0}\setminus\\{0\\}$. Note that $p$
cannot have two components being 0. So we will arbitrarily choose $p_{1}$ to
be 0 and see the results. In order for $p$ to be a null vector we have

$\begin{bmatrix}1&a_{12}&a_{13}\\\ a_{12}&1&a_{23}\\\
a_{13}&a_{23}&1\end{bmatrix}\begin{bmatrix}0\\\ p_{2}\\\
p_{3}\end{bmatrix}=\begin{bmatrix}a_{12}p_{2}+a_{13}p_{3}\\\
p_{2}+a_{23}p_{3}\\\ a_{23}p_{2}+p_{3}\end{bmatrix}=\begin{bmatrix}0\\\ 0\\\
0\end{bmatrix}.$

From the last two equations we have that $a_{23}=-1$ and $p_{2}=p_{3}=1$. Now
from the first equation we get $a_{12}+a_{13}=0$. Also, from Lemma 5 we know
that $a_{12},a_{13}\geq-1$. Putting this all together we now have

$A=\begin{bmatrix}1&t&-t\\\ t&1&-1\\\ -t&-1&1\end{bmatrix}$

for some $-1\leq t\leq 1$. In other words, requiring the null vector to be
$(0,1,1)$ doesn’t give us just one matrix in
$\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}\leq-1\\}$.
Instead, we obtain a 1-dimensional set. This is the important idea. Here we
see a single point “splitting” into infinitely many points. And by symmetry we
get similar results if we require a different component of the null vector to
be 0. These results are summarized in Figure 5.

Figure 5: Null vector (left) and corresponding matrices in
$\widehat{\mathcal{CF}}_{3}$ (right)

Let’s continue to see what happens if we consider other points on the boundary
of the domain. So now we will assume that the null vector, $p$, has components
$(1,t,1-t)$ for $0<t<1$. In other words $p$ is strictly in between the points
$(1,1,0)$ and $(1,0,1)$. Here we get

$\begin{bmatrix}1&a_{12}&a_{13}\\\ a_{12}&1&a_{23}\\\
a_{13}&a_{23}&1\end{bmatrix}\begin{bmatrix}1\\\ t\\\
1-t\end{bmatrix}=\begin{bmatrix}(1+a_{13})+(a_{12}-a_{13})t\\\
(a_{12}+a_{23})+(1-a_{23})t\\\
(1+a_{13})-(1-a_{23})t\end{bmatrix}=\begin{bmatrix}0\\\ 0\\\ 0\end{bmatrix}.$

Since $t$ is not 0 or 1, we only get a single solution for this system,
namely, $(a_{12},a_{13},a_{23})=(-1,-1,1)$. So here we kind of have the
opposite behavior of what we saw before. Now we have infinitely many points
“collapsing” to a single point. Again, by symmetry we have similar behavior
for a permutation of the null vector. We can summarize this in Figure 6.

Figure 6: Null vector (left) and corresponding matrix in
$\widehat{\mathcal{CF}}_{3}$ (right)

Now that we see the issues we can require our change of coordinates to address
them. Not only do we want to do a change of coordinates so that our domain is
$\Delta_{3}$, but we also want this change of coordinates to have
singularities which will “counter act” the behaviors we see in our
parametrization. So now we have the problem. Find a map
$\psi:\Delta_{3}\to\operatorname{conv}\\{e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\\}$
such that $\psi$ applied to a corner point is singular, and $\psi$ applied to
an edge gives us a corner point.

This required some searching, but eventually we found the map
$\psi:\Delta_{3}\setminus\\{e_{1},e_{2},e_{3}\\}\to\operatorname{conv}\\{e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\\}$
defined by

$\psi(t)=\left(\frac{t_{3}(1-t_{1}t_{2})}{(1-t_{1})(1-t_{2})},\frac{t_{2}(1-t_{1}t_{3})}{(1-t_{1})(1-t_{3})},\frac{t_{1}(1-t_{2}t_{3})}{(1-t_{2})(1-t_{3})}\right).$

This map has all of the desired properties. However, we don’t have a good
explanation of how to construct this map. We simply looked for one which has
the outlined properties. This of course leads to questions like, is this the
best way to change our coordinates to cancel out the singularities? Is this
the only way to change coordinates to achieve this? We don’t have the answers
to these questions.

With the ultimate goal of having a bijective or almost bijective map in the
end we will now check this in the following lemma.

######  Lemma 11.

The map
$\psi:\operatorname{int}(\Delta_{3})\to\operatorname{int}(\operatorname{conv}\\{e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\\})$
defined by

$\psi(t)=\left(\frac{t_{3}(1-t_{1}t_{2})}{(1-t_{1})(1-t_{2})},\frac{t_{2}(1-t_{1}t_{3})}{(1-t_{1})(1-t_{3})},\frac{t_{1}(1-t_{2}t_{3})}{(1-t_{2})(1-t_{3})}\right)$

is bijective.

###### Proof.

We will start with injectivity. Assume $\psi(t)=\psi(r)$ for
$t,r\in\operatorname{int}(\Delta_{3})$. Writing out this condition gives us

$\displaystyle\frac{t_{3}(1-t_{1}t_{2})}{(1-t_{1})(1-t_{2})}-\frac{r_{3}(1-r_{1}r_{2})}{(1-r_{1})(1-r_{2})}$
$\displaystyle=0$
$\displaystyle\frac{t_{2}(1-t_{1}t_{3})}{(1-t_{1})(1-t_{3})}-\frac{r_{2}(1-r_{1}r_{3})}{(1-r_{1})(1-r_{3})}$
$\displaystyle=0$
$\displaystyle\frac{t_{1}(1-t_{2}t_{3})}{(1-t_{2})(1-t_{3})}-\frac{r_{1}(1-r_{2}r_{3})}{(1-r_{2})(1-r_{3})}$
$\displaystyle=0.$

Now if we combine these fractions, set the numerators equal to zero, and
reduce the equations using the conditions that $t_{1}+t_{2}+t_{3}-1=0$ and
$r_{1}+r_{2}+r_{3}-1=0$, we get the incredibly long equations

$\displaystyle
r_{2}^{2}r_{3}t_{2}^{2}+r_{2}^{2}r_{3}t_{2}t_{3}-r_{2}^{2}t_{2}^{2}t_{3}-r_{2}^{2}t_{2}t_{3}^{2}+r_{2}r_{3}^{2}t_{2}^{2}+r_{2}r_{3}^{2}t_{2}t_{3}-r_{2}r_{3}t_{2}^{2}t_{3}-r_{2}r_{3}t_{2}t_{3}^{2}-$
$\displaystyle
r_{2}^{2}r_{3}t_{2}-r_{2}^{2}r_{3}t_{3}+r_{2}^{2}t_{2}t_{3}-r_{2}r_{3}^{2}t_{2}-r_{2}r_{3}^{2}t_{3}-r_{2}r_{3}t_{2}^{2}+r_{2}t_{2}^{2}t_{3}+r_{2}t_{2}t_{3}^{2}+r_{3}t_{2}^{2}t_{3}+$
$\displaystyle
r_{3}t_{2}t_{3}^{2}-r_{2}^{2}t_{3}+r_{2}r_{3}t_{2}-r_{2}t_{2}t_{3}+r_{3}t_{2}^{2}+r_{2}t_{3}-r_{3}t_{2}$
$\displaystyle=0$ $\displaystyle
r_{2}^{2}r_{3}t_{2}t_{3}+r_{2}^{2}r_{3}t_{3}^{2}+r_{2}r_{3}^{2}t_{2}t_{3}+r_{2}r_{3}^{2}t_{3}^{2}-r_{2}r_{3}t_{2}^{2}t_{3}-r_{2}r_{3}t_{2}t_{3}^{2}-r_{3}^{2}t_{2}^{2}t_{3}-r_{3}^{2}t_{2}t_{3}^{2}-$
$\displaystyle
r_{2}^{2}r_{3}t_{2}-r_{2}^{2}r_{3}t_{3}-r_{2}r_{3}^{2}t_{2}-r_{2}r_{3}^{2}t_{3}-r_{2}r_{3}t_{3}^{2}+r_{2}t_{2}^{2}t_{3}+r_{2}t_{2}t_{3}^{2}+r_{3}^{2}t_{2}t_{3}+r_{3}t_{2}^{2}t_{3}+$
$\displaystyle
r_{3}t_{2}t_{3}^{2}+r_{2}r_{3}t_{3}+r_{2}t_{3}^{2}-r_{3}^{2}t_{2}-r_{3}t_{2}t_{3}-r_{2}t_{3}+r_{3}t_{2}$
$\displaystyle=0$ $\displaystyle
r_{2}^{2}r_{3}t_{2}t_{3}-r_{2}r_{3}^{2}t_{2}t_{3}+r_{2}r_{3}t_{2}^{2}t_{3}+r_{2}r_{3}t_{2}t_{3}^{2}+r_{2}^{2}r_{3}t_{2}+r_{2}^{2}r_{3}t_{3}+r_{2}r_{3}^{2}t_{2}+r_{2}r_{3}^{2}t_{3}-$
$\displaystyle
r_{2}t_{2}^{2}t_{3}-r_{2}t_{2}t_{3}^{2}-r_{3}t_{2}^{2}t_{3}-r_{3}t_{2}t_{3}^{2}-r_{2}^{2}r_{3}-r_{2}r_{3}^{2}-$
$\displaystyle
2r_{2}r_{3}t_{2}-2r_{2}r_{3}t_{3}+2r_{2}t_{2}t_{3}+2r_{3}t_{2}t_{3}+t_{2}^{2}t_{3}+t_{2}t_{3}^{2}+2r_{2}r_{3}-2t_{2}t_{3}$
$\displaystyle=0.$

Using a computer algebra system we get that the solutions to this system are
either $(t_{1},t_{2},t_{3})=(r_{1},r_{2},r_{3})$ or $t_{1}$ is free and
$t_{2}$ is a root of

$\displaystyle\Big{(}r_{2}^{4}r_{3}^{2}+2r_{2}^{3}r_{3}^{3}+r_{2}^{2}r_{3}^{4}-r_{2}^{4}r_{3}-3r_{2}^{3}r_{3}^{2}-2r_{2}^{2}r_{3}^{3}+r_{2}^{3}+2r_{2}^{2}r_{3}+r_{2}r_{3}^{2}-r_{2}^{2}-2r_{2}r_{3}-r_{3}^{2}+r_{2}+r_{3}\Big{)}z^{3}+$
$\displaystyle\Big{(}-r_{2}^{4}r_{3}^{2}-2r_{2}^{3}r_{3}^{3}-r_{2}^{2}r_{3}^{4}+r_{2}^{4}r_{3}+3r_{2}^{3}r_{3}^{2}+2r_{2}^{2}r_{3}^{3}-3r_{2}^{3}r_{3}-3r_{2}^{2}r_{3}^{2}-2r_{2}r_{3}^{2}+2r_{2}^{2}+5r_{2}r_{3}+3r_{3}^{2}-r_{2}-3r_{3}\Big{)}z^{2}+$
$\displaystyle\Big{(}-r_{2}^{4}r_{3}^{2}-2r_{2}^{3}r_{3}^{3}-r_{2}^{2}r_{3}^{4}-r_{2}^{4}r_{3}+r_{2}^{3}r_{3}^{2}+2r_{2}^{2}r_{3}^{3}+3r_{2}^{3}r_{3}+r_{2}^{2}r_{3}^{2}-r_{2}^{2}r_{3}+r_{2}r_{3}^{2}+r_{2}^{2}-r_{2}r_{3}-2r_{2}\Big{)}z+$
$\displaystyle\Big{(}r_{2}^{4}r_{3}^{2}+2r_{2}^{3}r_{3}^{3}+r_{2}^{2}r_{3}^{4}+r_{2}^{4}r_{3}-r_{2}^{3}r_{3}^{2}-2r_{2}^{2}r_{3}^{3}-2r_{2}^{3}r_{3}+r_{2}^{3}+r_{2}^{2}r_{3}-2r_{2}^{2}\Big{)}.$

Again, using a computer algebra system tells us that when $r\in\Delta_{3}$,
the only root that can happen on the interval $[0,1]$ is a root precisely at
zero. This tells us if $t_{1}$ is free, then $t_{2}=0$. But this implies $t$
is on the boundary of $\Delta_{3}$. Hence, $\psi$ is injective.

Now for surjectivity. Let
$r\in\operatorname{int}(\operatorname{conv}\\{e_{1}+e_{2},e_{1}+e_{3},e_{2}+e_{3}\\})$.
Then $r=s_{1}(e_{2}+e_{3})+s_{2}(e_{1}+e_{3})+s_{3}(e_{1}+e_{2})$ for some
$s\in\operatorname{int}(\Delta_{3})$. Now we must find
$t\in\operatorname{int}(\Delta_{3})$ such that $\psi(t)=r$. So we get the
following system.

$\displaystyle\frac{t_{3}(1-t_{1}t_{2})}{(1-t_{1})(1-t_{2})}$
$\displaystyle=s_{1}+s_{2}$
$\displaystyle\frac{t_{2}(1-t_{1}t_{3})}{(1-t_{1})(1-t_{3})}$
$\displaystyle=s_{1}+s_{3}$
$\displaystyle\frac{t_{1}(1-t_{2}t_{3})}{(1-t_{2})(1-t_{3})}$
$\displaystyle=s_{2}+s_{3}.$

∎

Figure 7: Standard simplex (left) and $\psi$ evaluated on those curves (right)

We can visualize this change of coordinates in Figure 7. Now if we compose
this change of coordinates map with our parametrization map, we get the
following map
$\Psi:\Delta_{3}\to\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}\leq-1\\}$,
which leads to the following theorem.

######  Theorem 12.

The map
$\Psi:\Delta_{3}\to\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}\leq-1\\}$
defined by

$\Psi(t)=\begin{bmatrix}1&\frac{2t_{3}^{2}(1+t_{1})(1+t_{2})}{(1-t_{1}t_{3})(1-t_{2}t_{3})}-1&\frac{2t_{2}^{2}(1+t_{1})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{2}t_{3})}-1\\\
\frac{2t_{3}^{2}(1+t_{1})(1+t_{2})}{(1-t_{1}t_{3})(1-t_{2}t_{3})}-1&1&\frac{2t_{1}^{2}(1+t_{2})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{1}t_{3})}-1\\\
\frac{2t_{2}^{2}(1+t_{1})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{2}t_{3})}-1&\frac{2t_{1}^{2}(1+t_{2})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{1}t_{3})}-1&1\end{bmatrix}.$

is bijective.

###### Proof.

Based on Theorem 10 and Lemma 11 we already have that $\Psi$ restricted to the
interior of $\Delta_{3}$ is injective. Furthermore, the image of this
restricted map is the interior of the codomain. Thus, this restriction of
$\Psi$ is bijective. Now we must see where the boundaries of the domain get
mapped. To see this let us consider an edge of the domain where $t=(s,1-s,0)$.
Then we get

$\Psi(t)=\begin{bmatrix}1&-1&\frac{(2s-1)(s^{2}-s-1)}{s^{2}-s+1}\\\
-1&1&-\frac{(2s-1)(s^{2}-s-1)}{s^{2}-s+1}\\\
\frac{(2s-1)(s^{2}-s-1)}{s^{2}-s+1}&-\frac{(2s-1)(s^{2}-s-1)}{s^{2}-s+1}&1\end{bmatrix}.$

Note that in this case $a_{12}+a_{13}+a_{23}=-1$. Furthermore, this expression

$\frac{(2s-1)(s^{2}-s-1)}{s^{2}-s+1}$

bijectively maps the interval $[0,1]$ to the interval $[-1,1]$. So we have
bijectively mapped one edge of the domain to one edge of the codomain. Now by
symmetry we can argue that the others behave the same. ∎

##  5 Projecting to Parametrize $\widehat{\mathcal{CF}}_{3}$

Now that we have a nice parametrization for the set
$\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}\leq-1\\}$, we
can extend this set to recover all of $\widehat{\mathcal{CF}}_{3}$. As we
described before we will do this by projecting the curved boundary from the
point $(a_{12},a_{13},a_{23})=(-1,-1,-1)$. We can see a 2-dimensional version
of this idea in Figure 8. This leads to the following lemma.

Figure 8: Projecting the boundary to the whole set

######  Lemma 13.

The map $\phi:\mathbb{R}_{\geq
0}\times\left\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}\leq-1\right\\}\to\widehat{\mathcal{CF}}_{3}$
defined by

$\phi(\lambda,A)=A+\lambda\left(A-\begin{bmatrix}1&-1&-1\\\ -1&1&-1\\\
-1&-1&1\end{bmatrix}\right)=\begin{bmatrix}1&(1+\lambda)a_{12}+\lambda&(1+\lambda)a_{13}+\lambda\\\
(1+\lambda)a_{12}+\lambda&1&(1+\lambda)a_{23}+\lambda\\\
(1+\lambda)a_{13}+\lambda&(1+\lambda)a_{23}+\lambda&1\end{bmatrix}$

is a bijection.

###### Proof.

Note that $\phi$ is injective since there is no way for two distinct rays from
$(a_{12},a_{13},a_{23})=(-1,-1,-1)$ to intersect
$\left\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}\leq-1\right\\}$
in two different points and eventually meet up. Also, $\phi$ is surjective
since every point in $\widehat{\mathcal{CF}}_{3}$ can be traced back to a
point in
$\left\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}\leq-1\right\\}$
when following a line back towards $(-1,-1,-1)$. ∎

##  6 Scaling to Parametrize $\mathcal{CF}_{3}$

Now that we have a good parametrization for $\widehat{\mathcal{CF}}_{3}$, we
can scale the diagonal to obtain all of $\mathcal{CF}_{3}$. In other words we
can extend our chosen slice of $\mathcal{CF}_{3}$ to almost the whole set with
the following method. Let $A\in\widehat{\mathcal{CF}}_{3}$, then we can scale
$A$ to have whatever diagonal we wish via the map

$\left(\begin{bmatrix}s_{1}\\\ s_{2}\\\
s_{3}\end{bmatrix},\begin{bmatrix}1&a_{12}&a_{13}\\\ a_{12}&1&a_{23}\\\
a_{13}&a_{23}&1\end{bmatrix}\right)\mapsto\begin{bmatrix}s_{1}^{2}&s_{1}s_{2}a_{12}&s_{1}s_{3}a_{13}\\\
s_{1}s_{2}a_{12}&s_{2}^{2}&s_{2}s_{3}a_{23}\\\
s_{1}s_{3}a_{13}&s_{2}s_{3}a_{23}&s_{3}^{2}\end{bmatrix},$

where $s\in\mathbb{R}^{3}_{\geq 0}$. This will work for all but a measure zero
set in $\mathcal{CF}_{3}$. So if we wanted to we could stop here. However, we
will try to dive a little deeper to examine the problem and see if we can fix
it.

Just like some of our other issues while developing this parametrization, we
run into difficulties when zeros occur, but this time we are concerned with
zeros in the diagonal. To highlight the problem let’s look at the matrices

$A=\begin{bmatrix}0&1&1\\\ 1&1&1\\\ 1&1&1\end{bmatrix}\hskip
20.00003pt\text{and}\hskip 20.00003ptB=\begin{bmatrix}0&0&0\\\ 0&1&1\\\
0&1&1\end{bmatrix}.$

Clearly both $A$ and $B$ are copositive, but with the current method of
scaling the diagonal we can only obtain $B$. This is happening because when we
scale a diagonal element, we have to scale an entire row and column as well.
This is an issue.

On the road to fixing this problem let’s try to reverse the order of scaling
and extending. In other words, right now we are parametrizing a portion of the
boundary of $\widehat{\mathcal{CF}}_{3}$, extending that to all of
$\widehat{\mathcal{CF}}_{3}$, and then scaling the diagonal to get
$\mathcal{CF}_{3}.$ Instead let’s try to take the curved portion of the
boundary of $\widehat{\mathcal{CF}}_{3}$, scale the diagonal, and then extend
the set to get $\mathcal{CF}_{3}$. Algebraically nothing changes when we do
this, we still end up with the map $\Phi:\mathbb{R}^{4}_{\geq
0}\times\left\\{A\in\partial\widehat{\mathcal{CF}}_{3}:a_{12}+a_{13}+a_{23}\leq-1\right\\}\to\mathcal{CF}_{3}$

$(s_{1},s_{2},s_{3},\lambda,A)\mapsto\begin{bmatrix}s_{1}^{2}&s_{1}s_{2}(1+\lambda)a_{12}+s_{1}s_{2}\lambda&s_{1}s_{3}(1+\lambda)a_{13}+s_{1}s_{3}\lambda\\\
s_{1}s_{2}(1+\lambda)a_{12}+s_{1}s_{2}\lambda&s_{2}^{2}&s_{2}s_{3}(1+\lambda)a_{23}+s_{2}s_{3}\lambda\\\
s_{1}s_{3}(1+\lambda)a_{13}+s_{1}s_{3}\lambda&s_{2}s_{3}(1+\lambda)a_{23}+s_{2}s_{3}\lambda&s_{3}^{2}\end{bmatrix}.$

However, thinking about the process in this order will help us fix some of the
issues. Namely, the issue that this map is not surjective.

|  |
---|---|---
|  |
Figure 9: The off-diagonal elements as a diagonal element changes from 1 to 0

To try to visualize the problem, we will set $s_{2}=s_{3}=1$, but we will
allow $s_{1}$ to decrease from 1 to 0. See Figure 9. There are two big issues
here. One is that when $s[1]=0$ this boundary collapses into a 1-dimensional
object, and so we lose injectivity. Unfortunately, we can’t do much about this
issue. The second problem is that the point we need to project from,
$(-s_{1}s_{2},-s_{1}s_{3},-s_{2}s_{3})$, lies directly under this vertical
line when $s_{1}=0$. So projecting will only give us a vertical line, when the
copositive set here is everything in a non-negative direction from this line.
This issue we can address, and we will do so by projecting a ray _towards_ a
non-negative direction instead of _from_ a point.

To achieve this we will take the curved simplex that we already have which has
vertices at $(s_{1}s_{2},-s_{1}s_{3},-s_{2}s_{3})$,
$(-s_{1}s_{2},s_{1}s_{3},-s_{2}s_{3})$, and
$(-s_{1}s_{2},-s_{1}s_{3},s_{2}s_{3})$, and we will project towards one with
vertices at $(s_{1}s_{2}+1,-s_{1}s_{3},-s_{2}s_{3})$,
$(-s_{1}s_{2},s_{1}s_{3}+1,-s_{2}s_{3})$,
$(-s_{1}s_{2},-s_{1}s_{3},s_{2}s_{3}+1)$. We can do this without introducing
any new parameters since this surface we are projecting towards solely depends
on the boundary that we’ve already parametrized. This surface is given by

$\displaystyle a_{12}$
$\displaystyle=(2s_{1}s_{2}+1)\frac{t_{3}^{2}(1+t_{1})(1+t_{2})}{(1-t_{1}t_{3})(1-t_{2}t_{3})}-s_{1}s_{2}$
$\displaystyle a_{13}$
$\displaystyle=(2s_{1}s_{3}+1)\frac{t_{2}^{2}(1+t_{1})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{2}t_{3})}-s_{1}s_{3}$
$\displaystyle a_{23}$
$\displaystyle=(2s_{2}s_{3}+1)\frac{t_{1}^{2}(1+t_{2})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{1}t_{3})}-s_{2}s_{3}.$

Projecting towards this surface gives us our final version of the
parametrization: $\Phi:\mathbb{R}^{4}_{\geq
0}\times\Delta_{3}\to\mathcal{CF}_{3}$, where
$(s_{1},s_{2},s_{3},\lambda,t_{1},t_{2},t_{3})$ gets mapped to the matrix

$\begin{bmatrix}s_{1}^{2}&(2s_{1}s_{2}+\lambda)\frac{t_{3}^{2}(1+t_{1})(1+t_{2})}{(1-t_{1}t_{3})(1-t_{2}t_{3})}-s_{1}s_{2}&(2s_{1}s_{3}+\lambda)\frac{t_{2}^{2}(1+t_{1})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{2}t_{3})}-s_{1}s_{3}\\\
(2s_{1}s_{2}+\lambda)\frac{t_{3}^{2}(1+t_{1})(1+t_{2})}{(1-t_{1}t_{3})(1-t_{2}t_{3})}-s_{1}s_{2}&s_{2}^{2}&(2s_{2}s_{3}+\lambda)\frac{t_{1}^{2}(1+t_{2})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{1}t_{3})}-s_{2}s_{3}\\\
(2s_{1}s_{3}+\lambda)\frac{t_{2}^{2}(1+t_{1})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{2}t_{3})}-s_{1}s_{3}&(2s_{2}s_{3}+\lambda)\frac{t_{1}^{2}(1+t_{2})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{1}t_{3})}-s_{2}s_{3}&s_{3}^{2}\end{bmatrix}.$

######  Theorem 14.

This map $\Phi:\mathbb{R}^{4}_{\geq 0}\times\Delta_{3}\to\mathcal{CF}_{3}$ is
surjective and almost injective.

###### Proof.

Let $A\in\mathcal{CF}_{3}$. The diagonal of $A$ uniquely determines $s_{1}$,
$s_{2}$, and $s_{3}$. Let’s first consider the case where all $s_{i}>0$. In
this case the problem simplifies to considering the map
$\widehat{\Phi}:\mathbb{R}_{\geq
0}\times\Delta_{3}\to\widehat{\mathcal{CF}}_{3}$, where
$(\lambda,t_{1},t_{2},t_{3})$ maps to

$\begin{bmatrix}1&(2+\frac{\lambda}{s_{1}s_{2}})\frac{t_{3}^{2}(1+t_{1})(1+t_{2})}{(1-t_{1}t_{3})(1-t_{2}t_{3})}-1&(2+\frac{\lambda}{s_{1}s_{3}})\frac{t_{2}^{2}(1+t_{1})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{2}t_{3})}-1\\\
(2+\frac{\lambda}{s_{1}s_{2}})\frac{t_{3}^{2}(1+t_{1})(1+t_{2})}{(1-t_{1}t_{3})(1-t_{2}t_{3})}-1&1&(2+\frac{\lambda}{s_{2}s_{3}})\frac{t_{1}^{2}(1+t_{2})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{1}t_{3})}-1\\\
(2+\frac{\lambda}{s_{1}s_{3}})\frac{t_{2}^{2}(1+t_{1})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{2}t_{3})}-1&(2+\frac{\lambda}{s_{2}s_{3}})\frac{t_{1}^{2}(1+t_{2})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{1}t_{3})}-1&1\end{bmatrix}.$

Note that $\lambda$ separates the image of $\widehat{\Phi}$ into distinct
layers. Thus, $\lambda$ is uniquely determined by $A$ as well. For each
$\lambda$ we have a map which is essentially the same as the bijective map in
Theorem 12. The only difference is that it is a curved simplex with corner
points at $(1+\frac{\lambda}{s_{1}s_{1}},-1,-1)$,
$(-1,1+\frac{\lambda}{s_{1}s_{3}},-1)$, and
$(-1,-1,1+\frac{\lambda}{s_{2}s_{3}})$ instead of at $(1,-1,-1)$, $(-1,1,-1)$,
and $(-1,-1,1)$. Hence, each layer is a bijection, and we have achieved
surjectivity. Also, this means that our original map $\Phi$ is injective as
long as we avoid the measure-zero set of $s_{1}=0$, $s_{2}=0$, or $s_{3}=0$.

Now we will consider the case when $s_{1}=0$. This leads to $A$ having the
form

$\begin{bmatrix}0&\lambda\frac{t_{3}^{2}(1+t_{1})(1+t_{2})}{(1-t_{1}t_{3})(1-t_{2}t_{3})}&\lambda\frac{t_{2}^{2}(1+t_{1})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{2}t_{3})}\\\
\lambda\frac{t_{3}^{2}(1+t_{1})(1+t_{2})}{(1-t_{1}t_{3})(1-t_{2}t_{3})}&s_{2}^{2}&(2s_{2}s_{3}+\lambda)\frac{t_{1}^{2}(1+t_{2})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{1}t_{3})}-s_{2}s_{3}\\\
\lambda\frac{t_{2}^{2}(1+t_{1})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{2}t_{3})}&(2s_{2}s_{3}+\lambda)\frac{t_{1}^{2}(1+t_{2})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{1}t_{3})}-s_{2}s_{3}&s_{3}^{2}\end{bmatrix}.$

Here we lose injectivity. Since $\lambda=0$ causes the first row and columns
to be zero regardless of what $(t_{1},t_{2},t_{3})$ is. However, this map
still surjects onto matrices in $\mathcal{CF}_{3}$ with their top-right entry
being 0. Notice that the $2\times 2$ bottom-right corner is

$\begin{bmatrix}s_{2}^{2}&(2s_{2}s_{3}+\lambda)\frac{t_{1}^{2}(1+t_{2})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{1}t_{3})}-s_{2}s_{3}\\\
(2s_{2}s_{3}+\lambda)\frac{t_{1}^{2}(1+t_{2})(1+t_{3})}{(1-t_{1}t_{2})(1-t_{1}t_{3})}-s_{2}s_{3}&s_{3}^{2}\end{bmatrix}=\begin{bmatrix}s_{2}^{2}&-s_{2}s_{3}+\gamma\\\
-s_{2}s_{3}+\gamma&s_{3}^{2}\end{bmatrix},$

where $\gamma\in[0,\infty)$. This matches our description of matrices in
$\mathcal{CF}_{2}$. Now for the $(1,2)$ and $(1,3)$ entries, they can be any
non-negative numbers. And note, that’s exactly what we have here. We can think
of $t$ as choosing a non-negative direction, and $\lambda$ extends that
direction to achieve any non-negative numbers we wish. By symmetry we can
extend this argument, and we have surjectivity in this case. ∎

##  7 Conclusion

After all of this work we arrived at a parametrization of $\mathcal{CF}_{3}$
which is quite nice in a lot of ways. Not only is it almost injective, but we
can see a lot of the symmetries that exist within $\mathcal{CF}_{3}$. Of
course the goal is to keep going, and to parametrize $\mathcal{CF}_{4}$ and so
on. But we very quickly run into a problem. If we were to try to directly
apply the same method to the $n=4$ case, we would get stuck. There is no
equivalent result for Lemma 7. In fact, we were only able to get Lemma 7
because the number of non-diagonal elements, $\binom{n}{2}$, happens to match
to the size of the matrix when $n=3$. This brings us to the following
question.

######  Question 15.

For $n>3$ how do we parametrize the set

$\left\\{A\in\widehat{\mathcal{CF}}_{n}:\underset{p\geq
0}{\exists}Ap=0\right\\}$

in an injective or almost injective way?

We believe answering this question will make great progress towards the
parametrization of all copositive matrices. Another possible direction to go
is consider higher degree homogeneous polynomials and try to parametrize the
more general _copositive forms_. These are being considered in physics
applications [2]. Regardless, there we believe that this is a rich area of
study which still has many unknowns. With this paper our goal was to start the
ball rolling on parametrizing copositive forms with the smallest non-trivial
case, and hopefully we developed ideas which can be utilized for further
parametrization.

## References

  * [1] Andrey Afonin, Roland Hildebrand, and Peter JC Dickinson.  The extreme rays of the 6$\times$ 6 copositive cone.  Journal of Global Optimization, 79(1):153–190, 2021.
  * [2] Haibin Chen, Zheng-Hai Huang, and Liqun Qi.  Copositive tensor detection and its applications in physics and hypergraphs.  Computational Optimization and Applications, 69(1):133–158, 2018\.
  * [3] Palahenedi Hewage Diananda.  On non-negative forms in real variables some or all of which are non-negative.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 58, pages 17–25. Cambridge University Press, 1962.
  * [4] Peter JC Dickinson, Mirjam Dür, Luuk Gijben, and Roland Hildebrand.  Irreducible elements of the copositive cone.  Linear Algebra and its Applications, 439(6):1605–1626, 2013.
  * [5] MJ González-López, T Recio, and F Santos.  Parametrization of semialgebraic sets.  Mathematics and Computers in Simulation, 42(4-6):353–362, 1996\.
  * [6] Karl-Peter Hadeler.  On copositive matrices.  Linear Algebra and its Applications, 49:79–89, 1983.
  * [7] Roland Hildebrand.  The extreme rays of the 5$\times$ 5 copositive cone.  Linear Algebra and its Applications, 437(7):1538–1547, 2012.
  * [8] TS Motzkin.  Copositive quadratic forms.  National Bureau of Standards Report, 1818:11–12, 1952.
  * [9] James E Potter.  Matrix quadratic solutions.  SIAM Journal on Applied Mathematics, 14(3):496–501, 1966.
  * [10] Hannu Väliaho.  Criteria for copositive matrices.  Linear Algebra and its applications, 81:19–34, 1986.
  * [11] Lieven Vandenberghe and Stephen Boyd.  Semidefinite programming.  SIAM review, 38(1):49–95, 1996.


is a W3C-proposed language for expressing structural
constraints on RDF graphs. The recommendation only specifies
semantics for non-recursive ; recently, some efforts
have been made to allow recursive schemas.
In this paper, we argue that for defining and studying semantics of recursive , lessons can be learned from years of research in non-monotonic reasoning.
We show that from a schema, a three-valued semantic operator can directly be obtained.
Building on Approximation Fixpoint Theory (AFT), this operator immediately induces a wide variety of semantics, including a supported, stable, and well-founded semantics, related in the expected ways.
By building on AFT, a rich body of theoretical results becomes directly available for .
As such, the main contribution of this short paper is providing theoretical foundations for the study of recursive , which can later enable an informed decision for an extension of the W3C recommendation.

§ INTRODUCTION

The Semantic Web SemanticWeb extends the World-Wide Web with machine-interpretable data.
The de facto standard of this web is that data is stored and published in the
Resource Description Framework <cit.>,
i.e., as a set of triples, referred to as a graph,
often extended with semantic information expressed in OWL <cit.>.
While in principle the Semantic Web is open and every agent can represent their data however they want, from the perspective of applications, or when consuming RDF data in some other way, it can often be useful to know which structural properties an RDF graph in question satisfies. In other words, there is a need for a declarative language for describing integrity constraints on RDF graphs.

Several proposals have emerged to fill this need, the most prominent of them being ShEx <cit.>
and <cit.>.
Both approaches start from the notion of a shape: a structural property that a node in an RDF graph can satisfy, e.g., the shape of “things that have a name” will be satisfied for those nodes that appear as the subject in a triple with predicate .
On top of a language for defining such shapes, the two proposals also have a mechanism for targeting: for specifying which nodes should satisfy which shapes, e.g., to declare that “All persons should satisfy the has-a-name shape”.

In our paper, we will build on a formalization of <cit.>, which has revealed a striking similarity between
shapes and concepts descriptions, as known from description logics
we recently deepened this connection further <cit.>.
Following this line of research, we formalize a schema as a tuple $(\defin,\theory)$, where $\defin$ is a set of rules of
the form

s \lrule \concept

and $\theory$ is a set of concept inclusions of the form

\concept \subseteq s

with  $  \concept$ a shape (i.e., a concept description) and $s$ a shape name.
$\defin$ defines the shapes in terms of relations in the RDF graph and contains the so-called targeting constraints.

The W3C recommendation for only specifies the semantics when $\defin$ is non-recursive, i.e., if no shape is defined in terms of itself, but recently, some efforts have been made to lift this restriction, i.e., to define a supported and a stable semantics for recursive <cit.>.

In this paper, we put forward another principled way to define semantics of recursive , building on Approximation Fixpoint Theory (AFT), an abstract lattice-theoretic framework originally designed to unify semantics of non-monotonic logics AFT with applications, among others, in (extensions of) logic programming, autoepistemic logic, default logic, abstract argumentation, and active integrity constraints  <cit.>.

There are several advantages to defining semantics of in this way:

* It is simple and straightforward:
the power of AFT, comes largely from the fact that all that is required to apply it, is to define a (three-valued) semantic operator (similar to Fitting's immediate consequence operator for logic programs <cit.>).
In many domains (including ), there is a natural choice for such an operator; AFT then immediately induces all major classes of semantics.

* It provides confidence: AFT guarantees that the developed semantics follow well-established principles in nonmonotonic reasoning.

Even in case semantics are already defined, applying AFT can be a sanity check. A striking example of this is the fact that applications of AFT uncovered some issues in the semantics of (weighted and non-weighted) Abstract Dialectic Frameworks <cit.>.

* It provides access to a large body of theoretical results, including theorems on stratification <cit.>, predicate introduction <cit.>, and strong equivalence <cit.>, thereby eliminating the need to  “reinvent the wheel” by rediscovering these results in each of the separate domains.

In a nutshell, our main contribution is establishing formal
foundations for the study of recursive .

§ FORMALIZATION OF

In actual ,  semantics is defined in terms of RDF graphs, but we recently showed how to reduce this to the logical setting <cit.>.
As such, for the purpose of the current paper, we focus on the logical setting and take abstraction of RDF graphs.
Throughout this paper, we (implicitly) fix a vocabulary, i.e., a set of node names (denoted $N$), property names (denoted $P$), and shape names (denoted $S$).

A node name $c$ is also referred to as a constant, a property name $p$ as a binary predicate symbol and a shape name $s$ as a unary predicate symbol.

Path expressions $E$ and shapes $\phi$  are defined as follows:

\begin{align*}
E & ::=  p \mid p^- \mid E \cup E \mid E \circ E \mid E^* \mid E?\\
\concept &::= \top \mid s \mid \{c\} \mid \concept \land \concept \mid
\concept \lor \concept \mid \neg \concept \mid \forall E.\concept \mid
{}\geqn{n}{E}{\concept} \mid  \eq(E,E)\mid \disj(E,E)\mid \closed(Q)
\end{align*}

where $p$, $c$, and $s$ represent property names, node names, and shape names respectively,
and $n$ stands for non-zero natural numbers.
When developing our semantics, we will treat $\phi_1\lor\phi_2$ as an abbreviation of $\lnot(\lnot \phi_1\land\lnot \phi_2)$ and $\forall E.\phi$ as an abbreviation for $\lnot \geqn{1}{E}{\lnot \phi}$. The reason for having them in the syntax is to enable the comparison with existing semantics in <ref>.

As usual, an interpretation $I$ consists of

* a set $\dom^I$, called the domain of

* for each constant $c $, an element $\semi c \in
\dom^I$;

* for each shape name $s$, a set $\semi s\subseteq \dom^I$; and

* for each property name $p$, a binary relation $\semi
p$ on $\dom^I$.

When we say a graph-interpretation, we mean an interpretation that only consists of a domain and an interpretation for node and property names (not shape names). Intuitively, such an interpretation corresponds to an RDF graph.
A path expression $E$ evaluates in $I$ to a binary relation $\semi E$ on $\dom^I$,
and a shape $\phi$ to a subset $\semi \phi$ of
$\dom^I$, as defined in Tables <ref> and <ref>.

$E$     $\iexpr{E}{I}$

$p^-$     $\{(a,b) \mid (b,a) \in \iexpr{p}{I}\}$

$\iexpr{E_1 \cup E_2}{I}$     $\iexpr{E_1}{I} \cup \iexpr{E_2}{I}$

$\iexpr{E_1 \circ E_2}{I}$     $\{(a,b) \mid \exists c: (a,c) \in \iexpr{E_1}{I} $
$ \land (c,b) \in \iexpr{E_2}{I} \}$

$\iexpr{E^*}{I}$    the reflexive-transitive
closure of

$\iexpr{E?}{I}$      $\iexpr{E}{I} \cup \{(a,a)\mid a\in\dom^I\}$

Semantics of a path expression $E$ in an interpretation $I$.

$\concept$     $\iexpr{\concept}{I}$

$  \top$     $ \dom^I$

$\{c\}$     $\{c^I\}$

$\concept_1 \land \concept_2$     $\iexpr{\concept_1}{I} \cap \iexpr{\concept_2}{I}$

$\neg \concept_1$     $\dom^I \setminus \iexpr{\concept_1}{I}$

$\geqn{n}{E}{\concept_1} $     $\{a \in \dom^I \mid \sharp (\semi\phi_1 \cap \iexpr{E}{I}(a)) \geq n\} $

$\eq(E_1,E_2) $     $\{a \in \dom^I \mid
\semi{E_1}(a) = \semi{E_2}(a)\}$

$\disj(E_1,E_2) $     $\{a \in \dom^I \mid
\semi{E_1}(a) \cap \semi{E_2}(a) = \emptyset\}$

$\closed(Q) $     $\{a \mid \semi{p}(a)=\emptyset \text{  for every } p\in P\setminus Q\} $

Semantics of a shape $\concept$ in an interpretation $I$.
We use $\sharp X$ to denote the cardinality of $X$. For a binary
relation $R$ and an element $a$, we use $R(a)$ to denote  $\{b \mid (a,b) \in R\}$.

A schema is a tuple $(\defin,\theory)$ with

* $\defin$ a set of rules of the form $s\lrule \concept$ with $s$ a shape name (referred to as the head of the rule) and $\concept$ a shape (the body of the rule), such that
each $s\in S$ appears exactly once in the head of a rule, and

* a set of (concept) inclusions of the form $\concept \subseteq s$, with $\concept$ a shape that does not mention any shape names[The condition that $\phi$ does not mention any shape names will entail that the target query can be evaluated on the underlying graph, without knowledge of the shape definitions. In actual SHACL, the condition is even more limited; there only very specific queries are allowed as targets.], and $s$ a shape name.

A shape name $s_1$ depends on shape name $s_2$ in if there is a rule $s_1\lrule \concept$ in , and $s_2$ or some shape name that depends on $s_2$ occurs in $\concept$. A  schema is non-recursive if no shape name depends on itself.

If $(\defin,\theory)$ is  a non-recursive schema, and $I$ a graph-interpretation, then  $I$ can be uniquely extended to an interpretation $I'$ such that for each $s\in S$, $\iexpr{s}{I'} = \iexpr{\concept}{I'}$ if $s\lrule\concept\in\defin$.
In that case, we say that $I$ validates with respect to $(\defin,\theory)$ if $\iexpr{\phi}{I'}\subseteq \iexpr{s}{I'}$ for each inclusion $\phi\subseteq s$ in $\theory$.
For the recursive case, the situation is less obvious; in <ref>, we use approximation fixpoint theory to study the different semantic options that arise, but before doing so, we recall  preliminaries on AFT.

§ APPROXIMATION FIXPOINT THEORY

A complete lattice $\langle L,\leq\rangle$ is a set $L$ equipped with a partial order $\leq$, such that every
set $S\subseteq L$ has a  least upper bound and a greatest lower bound.
A complete lattice has a least element $\bot$ and a greatest element $\top$.
An operator $O:L\to L$ is monotone if $x\leq y$ implies that $O(x)\leq O(y)$. An element $x\in L$ is  a fixpoint of $O$ if $O(x)=x$.
Every monotone operator $O$ in a
complete lattice has a least fixpoint, denoted $\lfp(O)$.

Given a lattice $L$, AFT uses a bilattice
$L^2$.  We define projections for pairs as usual:
$(x,y)_1=x$ and $(x,y)_2=y$.  Pairs $(x,y)\in L^2$ are used to
approximate elements in the interval $[x,y] = \{z\mid x\leq
z\wedge z\leq y\}$. We call $(x,y)\in L^2$ consistent if $x\leq
y$, that is, if $[x,y]$ is non-empty. We use $L^c$ to denote the set
of consistent elements.

The precision
order on $L^2$ is defined as $(x,y) \leqp (u,v)$ if $x\leq u$
and $v\leq y$. If $(u,v)$ is consistent, this means that $(x,y)$
approximates all elements approximated by $(u,v)$.

In its original form, AFT makes use of approximators, which are operators on $L^2$, but <cit.> showed that all the consistent fixpoints studied in AFT are uniquely determined by an approximator's restriction to $L^c$ and developed a theory of consistent approximators.

An operator $A: L^c\to L^c$ is a consistent approximator of $O$ if it is -monotone and coincides with $O$ on $L$ (meaning $A(x,x) = (O(x),O(x))$ for all $x\in L$).

AFT studies fixpoints of $O$ using fixpoints of $A$.

* The $A$-Kripke-Kleene fixpoint is the $\leqp$-least fixpoint of $A$; it approximates all fixpoints of $O$.

* A partial $A$-stable fixpoint is a pair  $(x,y)$ such that $x=\lfp(A(\cdot,y)_1)$ and $y=\lfp(A(x,\cdot)_2)$, where $A(\cdot,y)_1:L\to L$ maps $z$ to $A(z,y)_1$ and similarly for $A(x,\cdot)_2$.

* The $A$-well-founded fixpoint is the least precise ($\leqp$-least) partial $A$-stable fixpoint.

* An $A$-stable fixpoint of $O$ is a fixpoint $x$ of $O$ such that $(x,x)$ is a partial $A$-stable fixpoint.

These definitions allow reconstructing all major
logic programming semantics by taking for $O$ Van Emden and Kowalski's immediate consequence operator $T_P$ LP and for $A$ Fitting's three- (or four-) valued extension $\Psi_P$ <cit.>.

§ FIXPOINT SEMANTICS FOR RECURSIVE

For the rest of this paper, we fix a  schema $(\defin,\theory)$ and a graph-interpretation $I$.

We already mentioned that if is non-recursive, it uniquely induces a  complete interpretation $I'$ in which all constraints in are to be verified.
When is recursive, however, the situation becomes more complex.
On the one hand, there is a range of possible semantics dealing with recursion.

On the other hand, some of the semantics yield not a single interpretation $I'$, but either a set of them, or a three-valued interpretation.
This will give us a choice between brave and cautious validation; the focus of this paper is on the treatment of negation, but we briefly discuss brave and cautious validation below.

To apply AFT, the first step to take is to determine a suitable lattice.
In our case, the obvious candidate is the lattice  $L_I$ (from now on, denoted  $L$) of all interpretations $I'$ with domain $\dom^I$ that agree with $I$ on $N\cup P$, or in other words, the set of interpretations that expand $I$. This set is equipped with the standard truth order, $I_1 \leqt I_2$ if $\iexpr{s}{I_1}\subseteq \iexpr{s}{I_2}$ for all $s\in S$.

The role of the semantic operator is to update the value of the interpretation of the shapes. In analogy with logic programming, its definition is straightforward: it maps the interpretation $I'$ to $\oper(I')$ such that for each shape name $s$ with defining rule $s\lrule \concept$, we define
$\oper(I')(s) = \iexpr{\concept}{I'}$.

With the lattice $\langle L, \leqt\rangle$, elements of $L^c$ are pairs $\pinter=(\pinter_1,\pinter_2)$ of two interpretations with $\pinter_1\leqt \pinter_2$; such pairs correspond one-to-one to three-valued interpretations that assign each $s\in S $ a function $\dom\to\{\ltrue,\lfalse,\lunkn\}$, mapping $a$ to if $a$ in $\iexpr{s}{\pinter_1}$, to $\lfalse$ if $a\not\in \iexpr{s}{\pinter_2}$ and to $\lunkn$ otherwise (in other words,  $\pinter_1$ represents what is certainly true and $\pinter_2$ what is possibly true). From now on, we  simply refer to elements of $L^c$ as three-valued interpretations.

We can evaluate a shape $\concept$ in a three-valued interpretation $\pinter$ with a straightforward extension of Kleene's truth tables, as also used in previous studies of recursive SHACL <cit.>; for completeness, this is included in <ref>. This table makes use of the truth order $\leqt$ on truth values defined as $\lfalse\leqt\lunkn\leqt\ltrue$, and the  negation on truth values defined as usual: $\lnot\ltrue=\lfalse; \lnot \lfalse = \ltrue; \lnot \lunkn=\lunkn$.

$\concept$     $\tiexpr{\concept}{\pinter}(a)$

$\top$     $\ltrue$

$\{c\}$     $\ltrue$ if $a=c$; $\lfalse$ otherwise

$s$     $\tiexpr{s}{\pinter}(a)$

$\neg \phi_1$     $\neg \tiexpr{\phi_1}{\pinter}(a)$

$\phi_1 \land \phi_2$     $\min_{\leqt} (\tiexpr{\phi_1}{\pinter}(a),  \tiexpr{\phi_2}{\pinter}(a))$

$\geqn{n}{E}{\phi_1} $     $
\begin{cases}
\ltrue & \text{if}\; \sharp\{b\in \iexpr{E}{\pinter}(a) \mid
\tiexpr{\phi_1}{\pinter}(b) = \ltrue \} \geq n, \\
\lfalse & \text{if}\;  \sharp\{b\in \iexpr{E}{\pinter}(a) \mid
\tiexpr{\phi_1}{\pinter}(b) \leqt \lunkn \} < n , \\
\lunkn  & \text{otherwise}
\end{cases}$

$\eq(E_1,E_2) $     if $a\in \iexpr{\eq(E_1,E_2)}{\pinter}$; $\lfalse$ otherwise

$\disj(E_1,E_2) $     if $a\in \iexpr{\disj(E_1,E_2)}{\pinter}$; $\lfalse$ otherwise

$\closed(Q)$     if $\iexpr{p}{\pinter}(a)=\emptyset$ for all $p\in P\setminus Q$; $\lfalse$ otherwise

Three-valued semantics of shapes.

grnode=[draw,circle,fill=white,minimum size=4pt,
inner sep=0pt]
(0,0) node [grnode] (a) [label=left:$a$] ;
(1,1) node [grnode] (c) [label=above:$c$] ;
(2,0) node [grnode] (b) [label=right:$b$] ;

(0,2.5) node [grnode] (e) [label=left:$e$] ;
(1,3.5) node [grnode] (d) [label=above:$d$] ;
(2,2.5) node [grnode] (f) [label=right:$f$] ;
(3.5,1) node [grnode] (Pfizer) [label=above:$\mathit{Pfizer}$] ;
(3.5,3.5) node [grnode] (Cough) [label=above:$\mathit{Cough}$] ;
[Latex[length=3mm]-Latex[length=3mm]] (a) – (c) node [sloped,midway,above ] $\mathit{closeTo}$;
[Latex[length=3mm]-Latex[length=3mm]] (c) – (b) node [sloped,midway,above ] $\mathit{closeTo}$;
[Latex[length=3mm]-Latex[length=3mm]] (a) – (b) node [sloped,midway,below] $\mathit{closeTo}$;

[Latex[length=3mm]-Latex[length=3mm]] (f) – (e) node [sloped,midway,below ] $\mathit{closeTo}$;
[Latex[length=3mm]-Latex[length=3mm]] (e) – (d) node [sloped,midway,above ] $\mathit{closeTo}$;
[Latex[length=3mm]-Latex[length=3mm]] (d) – (f) node [sloped,midway,above] $\mathit{closeTo}$;

[-Latex[length=3mm]] (c) – (Pfizer) node [sloped,midway,above] $\mathit{vaccinated}$;
[-Latex[length=3mm]] (d) – (Cough) node [sloped,midway,above] $\mathit{hasSymptoms}$;

figureVisual representation of the example interpretation.

Once a three-valued evaluation of shapes is defined, an approximator is obtained directly: like the operator, the approximator updates the value of each shape symbol according to its defining rule: it maps to $\app(\pinter)$ where for each shape $s\in S$ defined by the rule $s\lrule \concept$, $\app(\pinter)(s) = \iexpr{\concept}{\pinter}$.

is a consistent approximator of $\oper$.

At this point, AFT dictates what the supported models (fixpoints of ), (partial) stable models (-stable fixpoints), well-founded model (-well-founded fixpoint), and Kripke-Kleene model (-KK fixpoint) of are.
It is worth stressing that to arrive to this point, we made two choices. The first was our choice of order on the lattice. We opted here for the truth order, but its inverse would also have been a possible choice.
Several of the semantics induced by AFT aim to minimize models in the chosen order for reasons of groundedness <cit.>, e.g., if $s$ has $s\lrule s$ as defining rule, in stable and well-founded semantics, our chosen order would result in no nodes satisfying $s$.
The second choice we made is which three-valued truth evaluation to use; we opted for the most obvious choice: a direct extension of Kleene's three-valued truth tables, which was used in other studies of recursive SHACL as well <cit.>.
Given these choices, models of the different types (stable, well-founded, ... ) are defined by AFT, and hence semantics for brave and cautious validation under of each semantics are established.

Let $\sigma\in\{\mathit{KK},\mathit{WF}\}$ and let $\pinter$ be the $\sigma$-model. We say that
$I$ cautiously (resp.  bravely) $\sigma$-validates with respect to $(\defin,\theory)$ if $\iexpr{\concept\land\lnot s}{\pinter}=\lfalse$ (resp.  $\iexpr{\concept\land\lnot s}{\pinter}\leqt\lunkn$) for every $\concept\subseteq s$ in $\theory$.

Let $\sigma\in\{\mathit{St},\mathit{Sup}\}$ and let $M$ be the set of $\sigma$-models. We say that
$I$ cautiously (resp.  bravely) $\sigma$-validates with respect to $(\defin,\theory)$ if
$\iexpr{\concept\land\lnot s}{I'}=\lfalse$ for all (resp. for some) $I'\in M$ for every $\concept\subseteq s$ in $\theory$.

Let us illustrate the differences between the various types of models on a small example.

Consider binary predicates $\mathit{closeTo}$, $\mathit{hasSymptoms}$, and $\mathit{vaccinated}$ and an interpretation $I$ with domain $\{a,b,c,d,e,f,\mathit{Pfizer},\mathit{Cough}\}$, where $a,\dots,f$ represent people (divided in two cliques of three “close” friends); one person ($c$) is vaccinated and one person ($d$) shows Covid symptoms. This interpretation is visually  depicted in <ref>.

We define two shapes: the shape of people at risk (those who
* are not vaccinated and
* have symptoms or are close to someone at risk) and the shape of people who can go to office (those who are not at risk), as formalized below:

\begin{align*}
\small
\mathit{atRisk} &\gets \lnot \geqn{1}{\mathit{vaccinated}}{\top} \land % \\&
(\geqn{1}{ \mathit{hasSymptoms}}{\top} \lor \exists \mathit{closeTo}.\mathit{atRisk}) \\
\mathit{canWork} &\gets \neg \mathit{atRisk}
\end{align*}

For this set of shape definitions, the unique stable model equals the well-founded model and states that $d$, $e$, and $f$ are at risk, while $a$, $b$, and $c$ can work.
In the Kripke-Kleene model, $d$, $e$, and $f$ are again at risk, $c$ is not at risk (and hence can work), but for $a$ and $b$ it is unknown whether they are at risk.
There are two supported models: the  stable model and one in which everyone except for $c$ is at risk.

Let $G$ be the graph consisting of three nodes:
$\{\mathit{Tom}, \mathit{Ann}, \mathit{Bob}\}$ and which forms a
clique through the $\mathit{closeTo}$ property. Furthermore, we add the tuple $(\mathit{Tom}, \mathit{yes})$ to the extension of $\mathit{hasSymptoms}$. The graph is depicted in Figure <ref>.

Example graph

Consider the following shapes:

\begin{align*}
\small
\mathit{NeedsTest} & \gets \exists \mathit{hasSymptoms}.\mathit{yes} \lor \exists \mathit{closeTo}.\mathit{NeedsTest} \\
\mathit{Healthy} & \gets \neg \mathit{NeedsTest}
\end{align*}

There is one supported model $I=\{\mathit{NeedsTest}(\mathit{Tom}),$ $\mathit{NeedsTest}(\mathit{Ann}),$ $\mathit{NeedsTest}(\mathit{Bob})\}$. Next, consider the following shape:

\begin{align*}
\small
\mathit{Safe} & \gets \exists \mathit{vaccinated}.\mathit{yes} \lor {}\leq_1 \mathit{closeTo}.\neg \mathit{Safe}
\end{align*}

Written in normal-form we obtain the set of shape definitions:

\begin{align*}
\small
\mathit{Safe} & \gets \exists \mathit{vaccinated}.\mathit{yes} \\
\mathit{Safe} & \gets \neg s_1 \\
s_1 & \gets {}\geqn{2}{\mathit{closeTo}}{s_2} \\
s_2 & \gets \neg\mathit{Safe}
\end{align*}

There are two possible 2-valued supported models: $\emptyset$ and
$\{\mathit{Safe}(\mathit{Tom}),$ $\mathit{Safe}(\mathit{Ann}),$
$\mathit{Safe}(\mathit{Bob})\}$. We refer to the latter model by
$I$. There exists a proper level mapping for $I$. For all
$b\in \{\mathit{Tom}, \mathit{Ann}, \mathit{Bob}\}$:
$\lvl(\top, b) = 0$, $\lvl(\neg s_1, b) = 0$ and
$\lvl(\mathit{Safe}, b) = 1$. Therefore, all nodes in $G$ are
considered safe under $\lvl$-stable model semantics.

However, this is not the case under $\twop{\defin, G}$-stable model
semantics. $\twop{\defin, G}(\emptyset, I)_1 = \emptyset$, therefore
$I$ is not an $\twop{\defin, G}$-stable model.

FIVE INDIVIDUALS: CLIQUE OF THREE; VACCINATED GUY IN CONTACT WITH EVERYONE; Fifth person only in contact with the vaccinated guy.

HERE WE SAY: “safe is: vaccinated or all friends are safe”
This works well...

ALSO include something to verify. E.G. all citizens are safe.

Maxime, can you write out this example, mabye with a tikz visualization of the input interpretation? ?

§ COMPARISON WITH EXISTING SEMANTICS

Corman et al. <cit.> already defined a supported semantics and Andreşel et al. <cit.> a stable semantics for . For clarity, we refer to the existing semantics as CRS-supported and ACORSS-stable semantics, and to the semantics induced by AFT, e.g., as AFT-stable. Both of them focus on brave validation, but Andreşel et al. also mention the possibility of cautious validation.  The main results on correspondence between the semantics are summarized here.

In fact,
Corman et al. <cit.> already defined the three-valued immediate consequence operator (there denoted $\mathbf{T}$). While the focus of that work was on supported semantics,
we now showed that in fact, by defining the approximator , they had everything at hand to define the full.
Since Corman et al. also characterized supported models as fixpoints of (in their Definition 17), our semantics and theirs coincide.

$I$ CRS-validates $(\defin,\theory)$ if and only if $I$ bravely $\mathit{Sup}$-validates $(\defin,\theory)$.

The situation is somewhat different for stable semantics, which Andreşel et al. <cit.> defined in terms of level mappings.

Let $I'$ be an interpretation.
A level assignment for $I'$ is a function that maps tuples in $\{(\phi,a)\mid \iexpr{\phi}{I'}(a)=\ltrue\}$ to integers and satisfies

* $\level(\phi_1\land\phi_2,a)= \mathrm{max}\{\level(\phi_1,a),\level(\phi_2,a)\}$,

* $\level(\phi_1\lor\phi_2,a)= \mathrm{min}\{\level(\phi_i,a)\mid i\in \{1,2\}\land  \iexpr{\phi_i}{I'}(a)=\ltrue\}$,

* $\level(\geqn{n}{E}{\concept})$ is the smallest $k\geq 0$ for which there are $n$ elements $b_1,\dots b_n \in\dom^{I'}$ such that $\level(\concept,b_i)\leq k$, $(a,b_i) \in\iexpr{E}{I'}$, and $\iexpr{\concept}{I'}(b_i)=\ltrue$, and
* $\level(\forall E. \concept, a) = \max(\{\level(\concept,b) \mid (a,b) \in \iexpr{E}{I'} \land \iexpr{\concept}{I'}{(b)}= \ltrue\}$.

A supported model $I'$ is an ARCOSS-stable model if there exists a level assignment for $I'$ such that $\level(s,a)>\level(\concept_s,a)$ for each rule $s\lrule\phi_s$ in $\defin$ and each $a$ with $\iexpr{s}{I'}(a) = \ltrue$.

For  the correspondence in case of stable semantics, we recall a normal form of Andreşel et al. <cit.>:

$\defin$ is in shape normal form if all
rules in $\defin$ have one of the
following forms:

$s\gets \top$     $s\gets \{c\}$     $s\gets \neg s'$
$s\gets s' \land s''$     $s\gets s' \lor s''$
$s\gets \geqn{n}{E}{s'}$
$s\gets \forall E.s'$     $s\gets \eq(E, E')$     $s\gets \disj(E, E')$

If $I'$ is an AFT-stable model of , then it is also an ACORSS-stable model.
If is in shape normal form, the converse also holds.

The difference between our stable semantics and the ACORSS-stable semantics is a semantic (in terms of the standard three-valued truth evaluation) versus a syntactic (the level mappings are defined in terms of the syntactic structure of the shapes) treatment of negation and is illustrated in the next example.

[Example <ref> continued]
Suppose that in our same interpretation, we wish to define a shape that identifies possible superspreaders. To do this, we say that a person is “safe” if they are vaccinated, or in contact with at most $1$ non-safe person.
This can be formalized as:

\begin{align*}
\small
\mathit{Safe} & \gets \exists \mathit{vaccinated}.\top \lor {}\leq_1 \mathit{closeTo}.\neg \mathit{Safe},
\end{align*}

Where  $\leq_1$ is an abbreviation for $\lnot \geq_2$.
With the interpretation of <ref>, there is a single AFT-stable model in which $a$, $b$, and $c$ are safe, but $d$, $e$, and $f$ are not.

However, there are two ACROSS-stable models: the one mentioned above, and one in which everyone is safe, including the three-clique of non-vaccinated people.

§ CONCLUSION

When Corman et al. <cit.> defined the supported model semantics for , they showed how to translate actual expressions (as specified by the W3C recommendation) into logical expressions in a language akin to description logics. For studying recursive expressions, they even already defined the operator $\app$.
Hence, the only work left to obtain a rich family of semantics, was  observing that this operator is indeed an approximators and applying AFT.
As such, we believe this paper establishes strong and formal foundations for the study of recursive .

Indeed, AFT does not just dictate how the semantics are to be defined, but immediately provides guarantees such as stratification and predicate introduction results that can be instrumental when developing concrete validators for recursive : we immediately obtain results about which transformations can safely be applied to our theories.

Our results have been presented without taking a stance on the choice of semantics.

It is important to realize though, that if one wants to view as an (inductive) definition of the shapes, it has been argued repeatedly that the well-founded semantics correctly formalizes this <cit.>.
Under the well-founded semantics, integrates first-order constraints (of a restricted form)  with inductive definitions and aggregates, and hence can be seen as a fragment of the language $\mathrm{FO}(\mathrm{ID},\mathrm{Agg})$, the formal foundation of the language IDP.
It is a topic for future work to investigate whether this can be exploited for either extending , or for developing alternative validation mechanisms, building on  .

This research was supported by the Flemish Government in the “Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen” programme and by FWO Flanders project G0B2221N.