# Inverse semigroup from metrics on doubles III. Commutativity and
(in)finiteness of idempotents

V. Manuilov  Moscow Center for Fundamental and Applied Mathematics and Moscow
State University, Leninskie Gory 1, Moscow, 119991, Russia
<EMAIL_ADDRESS>
###### Abstract.

We have shown recently that, given a metric space $X$, the coarse equivalence
classes of metrics on the two copies of $X$ form an inverse semigroup $M(X)$.
Here we study the property of idempotents in $M(X)$ of being finite or
infinite, which is similar to this property for projections in
$C^{*}$-algebras. We show that if $X$ is a free group then the unit of $M(X)$
is infinite, while if $X$ is a free abelian group then it is finite. As a by-
product, we show that the inverse semigroup $M(X)$ is not a quasi-isometry
invariant. More examples of finite and infinite idempotents are provided. We
also give a geometric description of spaces, for which their inverse semigroup
$M(X)$ is commutative.

###  1\. Introduction

Given metric spaces $(X,d_{X})$ and $(Y,d_{Y})$, a metric $d$ on $X\sqcup Y$
that extends the metrics $d_{X}$ on $X$ and $d_{Y}$ on $Y$, depends only on
the values $d(x,y)$, $x\in X$, $y\in Y$, and it may be not easy to check which
functions $d:X\times Y\to(0,\infty)$ determine a metric on $X\sqcup Y$. The
problem of description of all such metrics is difficult due to the lack of a
nice algebraic structure on the set of metrics, but, passing to coarse
equivalence of metrics, we get an algebraic structure, namely, that of an
inverse semigroup [4]. Recall that two metrics, $b,d$, on a space $Z$ are
coarsely equivalent if there exist monotone functions
$\varphi,\psi:[0,\infty)\to[0,\infty)$ such that

$\lim\nolimits_{t\to\infty}\varphi(t)=\lim\nolimits_{t\to\infty}\psi(t)=\infty$

and

$\varphi(d(z_{1},z_{2}))\leq b(z_{1},z_{2})\leq\psi(d(z_{1},z_{2}))$

for any $z_{1},z_{2}\in Z$. A coarse equivalence class of a metric $d$ we
denote by $[d]$.

Let $\mathcal{M}(X,Y)$ denote the set of all metrics $d$ on $X\sqcup Y$ such
that

  * •

the restriction of $d$ onto $X$ and $Y$ are $d_{X}$ and $d_{Y}$ respectively;

  * •

$\inf_{x\in X,y\in Y}d(x,y)>0$.

Coarse equivalence classes of metrics in $\mathcal{M}(X,Y)$ can be considered
as morphisms from $X$ to $Y$ [3], where the composition $\rho d$ of a metric
$d$ on $X\sqcup Y$ and a metric $\rho$ on $Y\sqcup Z$ is given by the metric
determined by

$(\rho\circ d)(x,z)=\inf\nolimits_{y\in Y}[d(x,y)+\rho(y,z)],\quad x\in X,\
z\in Z.$

When $Y=X$, we call $X\sqcup X$ the double of $X$. In what follows we identify
$X\sqcup X$ with $X\times\\{0,1\\}$, and write $X$ for $X\times\\{0\\}$
(resp., $x$ for $(x,0)$) and $X^{\prime}$ for $X\times\\{1\\}$ (resp.,
$x^{\prime}$ for $(x,1)$).

The main result of [4] is that the semigroup $M(X)$ (with respect to this
composition) of coarse equivalence classes of metrics on the double of $X$ is
an inverse semigroup with the unit element ${\mathbf{1}}$ and the zero element
${\mathbf{0}}$, and the unique pseudo-inverse for $[d]\in M(X)$ is the coarse
equivalence class of th metric $d^{*}$ given by
$d^{*}(x,y^{\prime})=d(x^{\prime},y)$, $x,y\in X$.

Recall that a semigroup $S$ is an inverse semigroup if for any $s\in S$ there
exists a unique $t\in S$ (denoted by $s^{*}$ and called a pseudo-inverse) such
that $s=sts$ and $t=tst$ [2]. Philosophically, inverse semigroups describe
local symmetries in a similar way as groups describe global symmetries, and
technically, the construction of the (reduced) group $C^{*}$-algebra of a
group generalizes to that of the (reduced) inverse semigroup $C^{*}$-algebra
[6]. It is known that any two idempotents in an inverse semigroup $S$ commute,
and that there is a partial order on $S$ defined by $s\leq t$ if $s=ss^{*}t$.
Our standard reference for inverse semigroups is [2].

Close relation between inverse semigroups and $C^{*}$-algebras allows to use
classification of projections in $C^{*}$-algebras for idempotents in inverse
semigroups. Namely, as in $C^{*}$-algebra theory, we call two idempotents,
$e,f\in E(S)$ von Neumann equivalent (and write $e\sim f$) if there exists
$s\in S$ such that $s^{*}s=e$, $ss^{*}=f$. An idempotent $e\in E(S)$ is called
infinite if there exists $f\in E(S)$ such that $f\preceq e$, $f\neq e$, and
$f\sim e$. Otherwise $e$ is finite. An inverse semigroup is finite if every
idempotent is finite, and is weakly finite if it is unital and the unit is
finite. A commutative inverse semigroup is patently finite.

In [5] we gave a geometric description of idempotents in the inverse semigroup
$M(X)$ (there are two types of idempotents, named type I and type II) and
showed in Lemma 3.3 that the type is invariant under the von Neumann
equivalence. In the first part of this paper, we study the property of weak
finiteness for $M(X)$ (i.e. finiteness of the unit element) and discuss its
relation to geometric properties of $X$.

We start with several examples of finite or infinite idempotents, and then
show that if $X$ is a free group then $M(X)$ is not weakly finite, while if
$X$ is a free abelian group then it is weakly finite. We also show that the
inverse semigroup $M(X)$ is not a quasi-isometry invariant. The property of
being weakly finite is also not a coarse invariant. We don’t know if it is a
quasi-isometry invariant.

In the second part of this paper, we give a geometric description of spaces,
for which the inverse semigroup $M(X)$ is commutative.

##  Part I Weak finiteness of $M(X)$

###  2\. Some examples

The following example shows that in $M(X)$, for an appropriate $X$, we can
imitate examples of partial isometries and projections in a Hilbert space.

######  Example 2.1.

Let $l^{1}(\mathbb{N})$ be the space of infinite $l^{1}$ sequences, with the
metric given by the $l^{1}$-norm, and let

$X_{n}=\\{(0,\ldots,0,t,0,\ldots):t\in[0,\infty)\\}$

with $t$ at the $n$-th place, $n\in\mathbb{N}$. Set
$X=\cup_{n\in\mathbb{N}}X_{n}\subset l^{1}(\mathbb{N})$.

Let $x=(0,\ldots,0,t,0,\ldots)\in X_{n}$, $y=(0,\ldots,0,s,0,\ldots)\in
X_{m}$. Define metrics $d$, $e$, $f$ on $X\sqcup X^{\prime}$ by

$\displaystyle d(x,y^{\prime})$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{cl}|s-t|+1,&\mbox{if\ }m=n+1;\\\
s+t+1,&\mbox{if\ }m\neq n+1,\end{array}\right.$ $\displaystyle
e(x,y^{\prime})$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{cl}|s-t|+1,&\mbox{if\ }m=n;\\\
s+t+1,&\mbox{if\ }m\neq n,\end{array}\right.$ $\displaystyle f(x,y^{\prime})$
$\displaystyle=$ $\displaystyle\left\\{\begin{array}[]{cl}|s-t|+1,&\mbox{if\
}m=n\geq 2;\\\ s+t+1,&\mbox{if\ }m\neq n\mbox{\ or\ }m=n=1.\end{array}\right.$

It is easy to see that $d$, $e$, $f$ are metrics on $X\sqcup X^{\prime}$, and
that $d^{*}d=e$, $dd^{*}=f$ are idempotents, and that $e={\mathbf{1}}\neq f$.
In particular, ${\mathbf{1}}$ is infinite. Although $d$ seems similar to a
one-sided shift in a Hilbert space, it behaves differently: $f$ is
orthogonally complemented, i.e. there exists $h$ such that $f\lor
h={\mathbf{1}}$, $f\land h={\mathbf{0}}$, but the complement is not a minimal
idempotent, i.e. there exists a lot of idempotents $j\in E(M(X))$ such that
$j\leq h$, $j\neq h$.

On the other hand, if $X\subset[0,\infty)$ with the standard metric then the
inverse semigroup $M(X)$ is commutative (Prop. 7.1 in [4]), hence any
idempotent can be equivalent only to itself, hence is finite. In Part 2, we
shall give a geometric description of all metric spaces with commutative
$M(X)$, which is patently finite.

The next example shows that the picture may be more complicated.

######  Theorem 2.2.

There exists an amenable space $X$ of bounded geometry and $s\in M(X)$ such
that $s^{*}s=\mathbf{1}$, but $ss^{*}\neq\mathbf{1}$.

###### Proof.

Let

$x_{n}=(\log 2,\log 3,\ldots,\log n,\log(n+1),0,0,\ldots),$
$x^{\prime}_{n}=(\log 2,\log 2,\log 3,\log 3,\ldots,\log n,\log
n,\log(n+1),\log(n+1),0,0,\ldots),$

and let

$X=\\{x_{n}:n\in\mathbb{N}\\},\quad
X^{\prime}=\\{x^{\prime}_{n}:n\in\mathbb{N}\\},$

$X,X^{\prime}\subset l^{\infty}(\mathbb{N})$ with the metric

$d(x,y)=\sup\nolimits_{k}|x_{k}-y_{k}|,\quad x=(x_{1},x_{2},\ldots),\quad
y=(y_{1},y_{2},\ldots).$

Take $m>n$, then $d(x_{n},x_{m})=\log m=d(x^{\prime}_{n},x^{\prime}_{m})$,
hence the restriction of $d$ onto the two copies of $X$ coincide (thus
determining the metric $d_{X}$ on $X$), and $d\in\mathcal{M}(X)$.

We have, for $n$ even, $n=2k$,

$\displaystyle d(x_{n},X^{\prime})$ $\displaystyle=$
$\displaystyle\inf\nolimits_{m\in\mathbb{N}}d(x_{2k},x^{\prime}_{m})=d(x_{2k},x^{\prime}_{k})$
$\displaystyle=$ $\displaystyle\max\nolimits_{i\leq k}(|\log(i+1)-\log(2i+1)|\
\leq\ \log 2,$

and for $n$ odd, $n=2k-1$,

$d(x_{2k-1},x^{\prime}_{m})\geq\log(k+1)$

for any $m\in\mathbb{N}$, hence

$d(x_{n},X^{\prime})=\inf\nolimits_{m\in\mathbb{N}}d(x_{2k-1},x^{\prime}_{m})=d(x_{2k-1},x^{\prime}_{k})=\log(k+1),$

i.e.

$\lim_{k\to\infty}d(x_{2k-1},X^{\prime})=\infty.$

On the other hand,

$\displaystyle d(x^{\prime}_{n},X)$ $\displaystyle=$
$\displaystyle\inf\nolimits_{m\in\mathbb{N}}d(x^{\prime}_{n},x_{m})\leq
d(x^{\prime}_{n},x_{2n})$ $\displaystyle=$ $\displaystyle\log(2n+1)-\log(n+1)\
\leq\ \log 2.$

Let $X_{+}=\\{x_{2k}:k\in\mathbb{N}\\}$,
$X_{-}=\\{x_{2k-1}:k\in\mathbb{N}\\}$. Then

$\displaystyle d^{*}d(x,x^{\prime})$ $\displaystyle=$
$\displaystyle\inf\nolimits_{y\in
X}[d(x,y^{\prime})+d^{*}(y,x^{\prime})]=\inf\nolimits_{y\in
X}[d(x,y^{\prime})+d(x,y^{\prime})]$ $\displaystyle=$ $\displaystyle
2d(x,X^{\prime})\ \leq\ \log 2$

for any $x\in X_{+}$ and

$\lim_{x\in X_{-};\ x\to\infty}d^{*}d(x,x^{\prime})=\lim_{x\in X_{-};\
x\to\infty}2d(x,X^{\prime})=\infty,$

while

$dd^{*}(x,x^{\prime})=2d(x^{\prime},X)\leq\log 2$

for any $x\in X$.

Let $d_{+},d_{-}\in\mathcal{M}(X)$ be the idempotent selfadjoint metrics
defined by

$d_{\pm}(x,y^{\prime})=\inf\nolimits_{u\in X_{\pm}}[d_{X}(x,u)+1+d_{X}(u,y)].$

Then $[d^{*}d]=[d_{+}]$, $[dd^{*}]=\mathbf{1}$, and $[d_{+}]$ is strictly
smaller than $\mathbf{1}$, hence $M(X)$ is not finite.

Note that $X$ is amenable. Set $F_{n}=\\{x_{1},\ldots,x_{n}\\}\subset X$. Let
$N_{r}(A)$ denote the $r$-neighborhood of the set $A$. Then
$N_{r}(F_{n})\setminus F_{n}$ is empty when $\log(n+1)>r$, hence
$\\{F_{n}\\}_{n\in\mathbb{N}}$ is a Følner sequence. For $r=\log m$, the ball
$B_{r}(x_{n})$ of radius $r$ centered at $x_{n}$ contains either no other
points besides $x_{n}$ (if $n\geq m+1$), or it consists of the points
$x_{1},\ldots,x_{m}$ (if $n\leq m$), hence the metric on $X$ is of bounded
geometry. In fact, this space is of asymptotic dimension zero.

∎

###  3\. Case of free groups

Let $X=\Gamma$ be a finitely generated group with the word length metric
$d_{X}$. Consider the following property (I):

  * (i1)

$X=Y\sqcup Z$, and for any $D>0$ there exists $z\in Z$ such that
$d_{X}(z,Y)>D$;

  * (i2)

there exist $g,h\in\Gamma$ such that $gY\subset Y$, $hZ\subset Y$ and $gY\cap
hZ=\emptyset$;

  * (i3)

there exists $C>0$ such that $|d_{X}(gy,hz)-d_{X}(y,z)|<C$ for any $y\in Y$,
$z\in Z$.

The property (I) is neither stronger nor weaker than non-amenability. If we
require additionally that $Y\sim Z$ then it would imply non-amenability.

######  Lemma 3.1.

The free group $\mathbb{F}_{2}$ on two generators satisfies the property (I).

###### Proof.

Let $a$ and $b$ be the generating elements of $\mathbb{F}_{2}$, and let
$Y\subset X$ be the set of all reduced words in $a$, $a^{-1}$, $b$ and
$b^{-1}$ that begin with $a$ or $a^{-1}$, $Z=X\setminus Y$. Let $g=ab$,
$h=a^{2}$. Clearly, $gY\subset Y$ and $hZ\subset Y$.

If $z$ begins with $a^{n}$, $n>D$, then $d_{X}(z,Y)\geq n$.

If $y\in Y$, $z\in Z$ then

$d_{X}(aby,a^{2}z)=|y^{-1}b^{-1}a^{-1}a^{2}z|=|y^{-1}b^{-1}az|=|y^{-1}z|+2=d_{X}(y,z)+2,$

as the word $y^{-1}b^{-1}az$ cannot be reduced any further ($y^{-1}$ ends with
$a^{\pm}$, and $z$ either begins with $b^{\pm}$, or is an empty word).

∎

######  Theorem 3.2.

Let $X=\Gamma$ be a group with the property (I). Then $X$ is not weakly
finite.

###### Proof.

We shall prove that there exists $d\in\mathcal{M}(X)$ such that
$[d^{*}d]=\mathbf{1}$ and $[dd^{*}]\neq\mathbf{1}$.

Let $X=Y\sqcup Z$, $g,h\in\Gamma$ satisfy the conditions of the property (I).
Define a map $f:X\to X$ by setting

$f(x)=\left\\{\begin{array}[]{cl}gx,&\mbox{if\ }x\in Y;\\\ hx,&\mbox{if\ }x\in
Z.\end{array}\right.$

The maps $f|_{Y}$ and $f|_{Z}$ are left multiplications by $g$ and $h$,
respectively, hence are isometries. If $y\in Y$, $z\in Z$ then (i3) holds for
some $C>0$, hence $|d_{X}(f(x),f(y))-d_{X}(x,y)|<C$ holds for any $x,y\in X$.

Set

$d(x,y^{\prime})=\inf\nolimits_{u\in X}[d_{X}(x,u)+C+d_{X}(f(u),y)].$

It is easy to check that $d$ satisfies all triangle inequalities, hence $d$ is
a metric, $d\in\mathcal{M}(X)$. Then

$d^{*}d(x,x^{\prime})=2d_{X}(x,X^{\prime})=2\inf\nolimits_{u,y\in
X}[d_{X}(x,u)+C+d_{X}(f(u),y)]=2C$

for any $x\in X$, and

$\displaystyle dd^{*}(x,x^{\prime})$ $\displaystyle=$ $\displaystyle
2d_{X}(x^{\prime},X)=\inf\nolimits_{z,u\in X}[d_{X}(z,u)+C+D_{X}(f(u),x)]$
$\displaystyle=$ $\displaystyle 2(C+d_{X}(f(X),x))\ \geq\ 2C+2d_{X}(Y,x)$

is not bounded. Thus, $[d^{*}d]=\mathbf{1}$, while $[dd^{*}]\neq\mathbf{1}$.

∎

###  4\. Case of abelian groups

A positive result is given by the following Theorem.

######  Theorem 4.1.

Let $X=\mathbb{R}^{n}$, with a norm $\|\cdot\|$, and let the metric $d_{X}$ be
determined by the norm $\|\cdot\|$. If $s\in M(X)$, $s^{*}s=\mathbf{1}$ then
$ss^{*}=\mathbf{1}$.

###### Proof.

Let $d\in\mathcal{M}(X)$, $[d]=s$. As $[d^{*}d]=\mathbf{1}$, there exists
$C>0$ such that $2d(x,X^{\prime})<C$ for any $x\in X$. It suffices to show
that there exists $D>0$ such that $2d(x^{\prime},X)<D$ for any $x\in X$.
Suppose the contrary: for any $n\in\mathbb{N}$ there exists $x_{n}\in X$ such
that $d(x^{\prime}_{n},X)>2n$. Then $d(y^{\prime},X)>n$ for any $y\in X$ such
that $d_{X}(y,x_{n})\leq n$.

As $2d(x,X^{\prime})<C$ for any $x\in X$, there is a (not continuous) map
$f:X\to X$ such that $d_{X}(x,f(x)^{\prime})<C/2$ for any $x\in X$. This map
satisfies

$|d_{X}(f(x),f(y))-d_{X}(x,y)|<C\quad\mbox{for\ any\ }x,y\in X.$

Then there exists a continuous map $g:X\to X$ such that $d_{X}(f(x),g(x))<C$
for any $x\in X$. This map satisfies

$|d_{X}(g(x),g(y))-d_{X}(x,y)|<2C\quad\mbox{for\ any\ }x,y\in X,$

and $d(x,g(x)^{\prime})<3C/2$ for any $x\in X$.

Let $x_{0}=0$ denote the origin of $X$, and let $S_{R}$ be the sphere of
radius $R$ centered at the origin,

$S_{R}=\\{x\in X:d_{X}(x_{0},x)=R\\}.$

Set $x^{\prime}_{0}=f(x_{0})^{\prime}\in X^{\prime}$. For $x\in S_{R}$, we
have

$|d_{X}(x_{0},g(x))|=|d_{X}(x^{\prime}_{0},g(x)^{\prime})-R|\leq 2C.$

For $R>3C$, set $h_{R}(x)=\frac{g(x)}{\|g(x)\|}$. Then $h_{R}$ is a coninuous
map from $S_{R}$ to $S_{R}$ for any $R>3C$, and we have

$|d_{X}(h_{R}(x),h_{R}(y))-d_{X}(x,y)|<3C\quad\mbox{for\ any\ }x,y\in S_{R},$

and $d(x,h_{R}(x)^{\prime})<5C$ for any $x\in X$.

Let $R_{n}=d_{X}(x^{\prime}_{0},x^{\prime}_{n})$. Then $x_{n}\in S_{R_{n}}$.
If $d_{X}(y,x_{n})\leq n$ then $d(y^{\prime},X)>n$, hence $y\notin
h_{R_{n}}(S_{R_{n}})$, so the map $h_{R_{n}}$ is not surjective. Then, by the
Borsuk–Ulam Theorem, there exists a pair of antipodal points $y_{1},y_{2}\in
S_{R_{n}}$ such that $h_{R_{n}}(y_{1})=h_{R_{n}}(y_{2})=z$. As
$d(y_{i},z^{\prime})<5C$, $i=1,2$, and $d_{X}(y_{1},y_{2})=2R_{n}$, the
triangle inequality (for the trianlge with the vertices $y_{1}$, $y_{2}$,
$z^{\prime}$) is violated when $2R_{n}>10C$. This contradiction proves the
claim.

∎

######  Corollary 4.2.

Let $X=\mathbb{Z}^{n}$ with an $l_{p}$-metric, $1\leq p\leq\infty$, and let
$s\in M(X)$. Then $s^{*}s=\mathbf{1}$ implies $ss^{*}=\mathbf{1}$.

###### Proof.

By Proposition 9.2 of [4], $M(\mathbb{Z}^{n})=M(\mathbb{R}^{n})$.

∎

###  5\. $M(X)$ doesn’t respect equivalences

######  Proposition 5.1.

The inverse semigroup $M(X)$ is not a coarse invariant.

###### Proof.

The space $X$ from Theorem 2.2 is coarsely equivalent to the space
$Y=\\{n^{2}:n\in\mathbb{N}\\}$ with the standard metric, which we denote by
$b_{X}$. Indeed, for $n<m$, we have $b_{X}(x_{n},x_{m})=m^{2}-n^{2}$ and
$d_{X}(x_{n},x_{m})=\log(m+1)$. As $m^{2}-(m-1)^{2}=2m-1>\log(m+1)$ for $m>1$,
we have $d_{X}(x,y)\leq b_{X}(x,y)$ for any $x,y\in X$, and taking
$f(t)=2e^{t}$, we have $b_{X}(x,y)\leq f(d_{X}(x,y))$ for any $x,y\in X$.

For the metric $d_{X}$ from Theorem 2.2, the inverse semigroup $M(X,d_{X})$ is
not commutative ($[d^{*}d]\neq[dd^{*}]$), while the inverse semigroup
$M(X,b_{X})$ is commutative by Prop. 7.1 of [5].

∎

######  Theorem 5.2.

The inverse semigroup $M(X)$ is not a quasi-isometry invariant.

###### Proof.

Let $X=\mathbb{N}$ be endowed with the metric $b_{X}$ given by
$b_{X}(n,m)=|2^{n}-2^{m}|$, $n,m\in\mathbb{N}$, and let
$y_{n}=s(n)4^{[\frac{n}{2}]}$, where $s(n)=(-1)^{[\frac{n-1}{2}]}$ and $[t]$
is the greatest integer not exceeding $t$. Let $d_{X}$ be the metric on $X$
given by $d_{X}(n,m)=|y_{n}-y_{m}|$, $n,m\in\mathbb{N}$. The two metrics are
quasi-isometric. Indeed, suppose that $n>m$. If $s(n)=-s(m)$ then

$d_{X}(n,m)=4^{[\frac{n}{2}]}+4^{[\frac{m}{2}]}\leq
4^{\frac{n}{2}+1}+4^{\frac{m}{2}+1}=4(\cdot 2^{n}+2^{m})\leq 12b_{X}(n,m);$
$d_{X}(n,m)=4^{[\frac{n}{2}]}+4^{[\frac{m}{2}]}\geq
4^{\frac{n}{2}}+4^{\frac{m}{2}}\geq 2^{n}-2^{m}=b_{X}(n,m).$

We use here that $\frac{2^{r}+1}{2^{r}-1}\leq 3$ for any $r=n-m\in\mathbb{N}$.
If $s(n)=s(m)$ then

$d_{X}(n,m)=4^{[\frac{n}{2}]}-4^{[\frac{m}{2}]}\leq
4^{\frac{n}{2}+1}-4^{\frac{m}{2}}=4\cdot 2^{n}-2^{m}\leq 7b_{X}(n,m).$

We use here that $\frac{4\cdot 2^{r}-1}{2^{r}-1}\leq 7$ for any
$r=n-m\in\mathbb{N}$. To obtain an estimate in other direction, note that
$s(n)=s(m)$ implies that $[n/2]\geq[m/2]+1$, and that $n-m\neq 2$. If $n=m+1$
then

$d_{X}(m+1,m)=3\cdot 4^{[m/2]}\geq\frac{3}{2}\cdot 2^{m}=\frac{3}{2}\
b_{X}(m+1,m),$

If $n\geq m+3$ then

$d_{X}(n,m)=4^{[\frac{n}{2}]}-4^{[\frac{m}{2}]}\geq
4^{\frac{n}{2}}-4^{\frac{m}{2}+1}=2^{n}-4\cdot 2^{m}\geq\frac{4}{7}\
b_{X}(n,m).$

We use here that $\frac{2^{r}-4}{2^{r}-1}\geq\frac{4}{7}$ for any $r=n-m\geq
3$. Thus,

$\frac{3}{7}\ b_{X}(n,m)\leq d_{X}(n,m)\leq 12\cdot b_{X}(n,m)$

for any $n,m\in\mathbb{N}$, so the two metrics are quasi-isometric.

We already know that $M(X,b_{X})$ is commutative, so it remains to expose two
non-commuting elements in $M(X,d_{X})$.

Let

$X=\\{(y_{n},0):n\in\mathbb{N}\\},\quad
X^{\prime}=\\{(-y_{n},1):n\in\mathbb{N}\\},$

and let $d$ be the metric on $X\sqcup X^{\prime}$ induced from the standard
metric on the plane $\mathbb{R}^{2}$, $s=[d]$. Note that $-y_{n}=y_{n-1}$ if
$y_{n}>0$ and $n>1$, and $-y_{n}=y_{n+1}$ if $y_{n}<0$. Hence, $d^{*}=d$ and
$s^{2}=\mathbf{1}$.

Let

$A_{+}=\\{y_{n}:n\in\mathbb{N};y_{n}>0\\},\quad
A_{-}=\\{y_{n}:n\in\mathbb{N};y_{n}<0\\},$

$X=A_{+}\sqcup A_{-}$, and let the metrics $d_{+}$ and $d_{-}$ on $X\sqcup
X^{\prime}$ be given by

$d_{\pm}(n,m^{\prime})=\inf\nolimits_{k\in A_{\pm}}[d_{X}(n,k)+1+d_{X}(k,m)],$

$e=[d_{+}]$, $f=[d_{-}]$. Then $es=\mathbf{0}$, while $se=f$, i.e. $e$ and $s$
do not commute.

∎

##  Part II When $M(X)$ is commutative

###  6\. R-spaces

######  Definition 6.1.

A metric space $X$ is an R-space (R for rigid) if, for any $C>0$ and any two
sequences $\\{x_{n}\\}_{n\in\mathbb{N}}$, $\\{y_{n}\\}_{n\in\mathbb{N}}$ of
points in $X$ satisfying

$|d_{X}(x_{n},x_{m})-d_{X}(y_{n},y_{m})|<C\quad\mbox{for\ any\
}n,m\in\mathbb{N}$ (6.1)

there exists $D>0$ such that $d_{X}(x_{n},y_{n})<D$ for any $n\in\mathbb{N}$.

######  Example 6.2.

As $M(X)$ is commutative for any $X\subset[0,\infty)$, it would follow from
Theorem 7.2 below that such $X$ is an R-space. A less trivial example is a
planar spiral $X$ given by $r=e^{\varphi}$ in polar coordinates with the
metric induced from the standard metric on the plane. Indeed, take any two
sequences $\\{x_{n}\\}_{n\in\mathbb{N}}$, $\\{y_{n}\\}_{n\in\mathbb{N}}$, in
$X$. Without loss of generality we may assume that $x_{1}=y_{1}=0$ is the
origin. If these sequences satisfy (6.1) then

$|d_{X}(0,x_{n})-d_{X}(0,y_{n})|<C$

for some fixed $C>0$ (we take $m=1$). If $x_{n}=(r_{n},\varphi_{n})$,
$y_{n}=(s_{n},\psi_{n})$ then $d_{X}(0,x_{n})=r_{n}$, $d_{X}(0,y_{n})=s_{n}$,
and we have $|r_{n}-s_{n}|<C$. Then $x_{n}$ and $y_{n}$ lie in a ring of width
$C$, say $R\leq r\leq R+C$. If $R$ is sufficiently great then

$d_{X}(x_{n},y_{n})\leq(\log(R+C)-\log R)(R+C),$

which is bounded as a function of $R$.

Recall that two maps $f,g:X\to X$ are equivalent if there exists $C>0$ such
that $d_{X}(f(x),g(x))<C$ for any $x\in X$. A map $f:X\to X$ is an almost
isometry if there exists $C>0$ such that

$|d_{X}(f(x),f(y))-d_{X}(x,y)|<C$

for any $x,y\in X$ and if for any $y\in X$ there exists $x\in X$ such that
$d_{X}(f(x),y)<C$ (the latter condition provides existence of an ‘inverse’ map
$g:X\to X$ such that $f\circ g$ and $g\circ f$ are equivalent to the identity
map). The set $AI(X)$ of all equivalence classes of almost isometries of $X$
is a group with respect to the composition. A metric space $X$ is called AI-
rigid [1] if the group $AI(X)$ is trivial.

######  Proposition 6.3.

A countable R-space $X$ is AI-rigid.

###### Proof.

Let $\\{x_{n}\\}_{n\in\mathbb{N}}$ be a sequence of all points of $X$, and let
$f:X\to X$ be an almost isometry. Set $y_{n}=f(x_{n})$. Then there exists
$C>0$ such that

$|d_{X}(f(x_{n}),f(x_{m}))-d_{X}(x_{n},x_{m})|<C$

for any $n,m\in\mathbb{N}$, hence there exists $D>0$ such that

$d_{X}(x_{n},f(x_{n}))=d_{X}(x_{n},y_{n})<D$

for any $n\in\mathbb{N}$, i.e. $f$ is equivalent to the identity map, hence
$X$ is AI-rigid.

∎

######  Example 6.4.

Euclidean spaces $\mathbb{R}^{n}$, $n\geq 1$, are not R-spaces, as they have a
non-trivial symmetry. The Archimedean spiral $r=\varphi$ is not an R-space, as
it is $\pi$-dense in $\mathbb{R}^{2}$.

###  7\. Criterion of commutativity

Let $a,b:T\to[0,\infty)$ be two functions on a set $T$. We say that $a\preceq
b$ if there exists a monotonely increasing function
$\varphi:[0,\infty)\to[0,\infty)$ with $\lim_{s\to\infty}\varphi(s)=\infty$
(we call such functions reparametrizations) such that $a(t)\leq\varphi(b(t))$
for any $t\in T$.

The following Lemma should be known, but we could not find a reference.

######  Lemma 7.1.

Let $a,b:T\to[0,\infty)$ be two functions. If $a\preceq b$ is not true then
there exists $C>0$ and a sequence $(t_{n})_{n\in\mathbb{N}}$ of points in $T$
such that $b(t_{n})<C$ for any $n\in\mathbb{N}$ and
$\lim_{n\to\infty}a(t_{n})=\infty$.

###### Proof.

If $a\preceq b$ is not true then for any reparametrization $\varphi$ there
exists $t\in T$ such that $a(t)>\varphi(b(t))$. Suppose that for any $C>0$,
the value $\max\\{a(t):b(t)\leq C\\}$ is finite. Then set

$f(C)=\max(\max\\{a(t):b(t)\leq C\\},C).$

This gives a reparametrization $f$. If $b(t)=C$ then $a(t)\leq f(C)=f(b(t))$ —
a contradiction. Thus, there exists $C>0$ such that $\max\\{a(t):b(t)\leq
C\\}=\infty$. It remains to choose a sequence $(t_{n})_{n\in\mathbb{N}}$ in
the set $\\{t\in T:b(t)\leq C\\}$ such that $a(t_{n})>n$.

∎

######  Theorem 7.2.

$X$ is an R-space if and only if $M(X)$ is commutative.

###### Proof.

Let $X$ be an R-space. We shall show that any $s\in M(X)$ is a projection. It
would follow that $M(X)$ is commutative. First, we shall show that any $s\in
M(X)$ is selfadjoint. Let $d\in\mathcal{M}(X)$, $[d]=s$. Suppose that
$[d^{*}]\neq[d]$. This means that either $d^{*}\preceq d$ or $d\preceq d^{*}$
is not true, where $d$ and $d^{*}$ are considered as functions on $T=X\times
X^{\prime}$. Without loss of generality we may assume that $d^{*}\preceq d$ is
not true. Then there exist sequences $(x_{n})_{n\in\mathbb{N}}$ in $X$ and
$(y^{\prime})_{n\in\mathbb{N}}$ in $X^{\prime}$ and $L>0$ such that
$d(x_{n},y^{\prime}_{n})<L$ for any $n\in\mathbb{N}$ and
$\lim_{n\to\infty}d(y_{n},x^{\prime}_{n})=\infty$ (recall that
$d^{*}(x,y^{\prime}):=d(y,x^{\prime})$).

Take $n,m\in\mathbb{N}$. Since $d(x_{n},y^{\prime}_{n})<L$,
$d(x_{m},y^{\prime}_{m})<L$, we have

$|d_{X}(x_{n},x_{m})-d_{X}(y_{n},y_{m})|=|d_{X}(x_{n},x_{m})-d_{X}(y^{\prime}_{n},y^{\prime}_{m})|<2L,$

and, since $X$ is an R-space, there exists $D>0$ such that
$d_{X}(x_{n},y_{n})<D$ for any $n\in\mathbb{N}$.

Then, using the triangle inequality for the quadrangle
$x_{n}y_{n}x^{\prime}_{n}y^{\prime}_{n}$, we get

$\displaystyle d(y_{n},x^{\prime}_{n})$ $\displaystyle\leq$ $\displaystyle
d_{X}(y_{n},x_{n})+d(x_{n},y^{\prime}_{n})+d_{X}(y^{\prime}_{n},x^{\prime}_{n})$
$\displaystyle=$ $\displaystyle
d_{X}(y_{n},x_{n})+d(x_{n},y^{\prime}_{n})+d_{X}(y_{n},x_{n})$
$\displaystyle<$ $\displaystyle D+L+D,$

which contradicts the condition
$\lim_{n\to\infty}d(y_{n},x^{\prime}_{n})=\infty$.

Now, let us show that $[d]\in M(X)$ is idempotent if $X$ is an R-space. Let
$a(x)=d(x,X^{\prime})$, $b(x)=d(x,x^{\prime})$. It was shown in [4] (Theorem
3.1 and remark at the end of Section 11) that if $[d]$ is selfadjoint then it
is idempotent if and only if $b\preceq a$. Suppose that the latter is not
true. Then there exists $L>0$ and a sequence $\\{x_{n}\\}_{n\in\mathbb{N}}$ of
points in $X$ such that $d(x_{n},X^{\prime})<L$ for any $n\in\mathbb{N}$ and
$\lim_{n\to\infty}d(x_{n},x^{\prime}_{n})=\infty$. In particular, this means
that there exists a sequence $\\{y_{n}\\}_{n\in\mathbb{N}}$ of points in $X$
such that $d(x_{n},y^{\prime}_{n})<L$ for any $n\in\mathbb{N}$. Since $[d]$ is
selfadjoint, for any $L>0$ there exists $R>0$ such that if $d(x,y^{\prime})<L$
then $d(x^{\prime},y)<R$.

It follows from the triangle inequality for the quadrangle
$x_{n}x_{m}y^{\prime}_{n}y^{\prime}_{m}$ that

$\displaystyle|d_{X}(x_{n},x_{m})-d_{X}(y_{n},y_{m})|$ $\displaystyle=$
$\displaystyle|d_{X}(x_{n},x_{m})-d_{X}(y^{\prime}_{n},y^{\prime}_{m})|$
$\displaystyle\leq$ $\displaystyle
d(x_{n},y^{\prime}_{n})+d(x_{m},y^{\prime}_{m})\ <\ 2L$

for any $n,m\in\mathbb{N}$, hence, the property of being an R-space implies
that there exists $D>0$ such that $d_{X}(x_{n},y_{n})<D$ for any
$n\in\mathbb{N}$. Therefore,

$d(x_{n},x^{\prime}_{n})\leq d_{X}(x_{n},y_{n})+d(y_{n},x^{\prime}_{n})<D+R$

for any $n\in\mathbb{N}$ — a contradiction with
$\lim_{n\to\infty}d(x_{n},x^{\prime}_{n})=\infty$.

In the opposite direction, suppose that $X$ is not an R-space. i.e. that there
exists $C>0$ and sequences $\\{x_{n}\\}_{n\in\mathbb{N}}$,
$\\{y_{n}\\}_{n\in\mathbb{N}}$ of points in $X$ such that (6.1) holds and
$\lim_{n\to\infty}d_{X}(x_{n},y_{n})=\infty$.

Note that these sequences cannot be bounded. Indeed, if there exists $R>0$
such that $d_{X}(x_{1},x_{n})<R$ for any $n\in\mathbb{N}$ then

$d_{X}(y_{1},y_{n})\leq d_{X}(x_{1},x_{n})+C=R+C$

for any $n\in\mathbb{N}$, but then

$d_{X}(x_{n},y_{n})\leq
d_{X}(x_{n},x_{1})+d_{X}(x_{1},y_{1})+d_{X}(y_{1},y_{n})<R+d_{X}(x_{1},y_{1})+R+C,$

which contradicts $\lim_{n\to\infty}d_{X}(x_{n},y_{n})=\infty$. Passing to a
subsequence, we may assume that

$d_{X}(x_{k},x_{n})>k,\ d_{X}(x_{k},y_{n})>k,\ d_{X}(y_{k},x_{n})>k,\
d_{X}(y_{k},y_{n})>k$

for any $n<k$, and $d_{X}(x_{k},y_{k})>k$ for any $k\in\mathbb{N}$. In
particular, this means that

$d_{X}(x_{k},y_{n})>k\quad\mbox{for\ any\ }k,n\in\mathbb{N}.$ (7.1)

Let us define two metrics on $X$ and show that they don’t commute. For $x,y\in
X$ set

$d_{1}(x,y^{\prime})=\min\nolimits_{n\in\mathbb{N}}[d_{X}(x,x_{n})+C+d_{X}(y_{n},y)];$
$d_{2}(x,y^{\prime})=\min\nolimits_{n\in\mathbb{N}}[d_{X}(x,y_{n})+C+d_{X}(x_{n},y)]$

(it is clear that the minimum is attained on some $n\in\mathbb{N}$ as
$x_{n},y_{n}\to\infty$). Let us show that $d_{1}$ is a metric on $X\sqcup
X^{\prime}$ (the case of $d_{2}$ is similar).

Due to symmetry, it suffices to check the two triangle inequalities for the
triangle $xzy^{\prime}$, $z\in X$:

$\displaystyle d_{1}(x,y^{\prime})+d_{1}(z,y^{\prime})$ $\displaystyle=$
$\displaystyle\min\nolimits_{n\in\mathbb{N}}[d_{X}(x,x_{n})+C+d_{X}(y_{n},y)]$
$\displaystyle+\
\min\nolimits_{m\in\mathbb{N}}[d_{X}(z,x_{m})+C+d_{X}(y_{m},y)]$
$\displaystyle=$ $\displaystyle
d_{X}(x,x_{n_{x}})+d_{X}(y_{n_{x}},y)+d_{X}(y,y_{n_{z}})+d_{X}(z,x_{n_{z}})+2C$
$\displaystyle\geq$ $\displaystyle
d_{X}(x,x_{n_{x}})+d_{X}(y_{n_{x}},y_{n_{z}})+d_{X}(z,x_{n_{z}})+2C$
$\displaystyle\geq$ $\displaystyle
d_{X}(x,x_{n_{x}})+(d_{X}(x_{n_{x}},x_{n_{z}})-C)+d_{X}(z,x_{n_{z}})+2C$
$\displaystyle=$ $\displaystyle
d_{X}(x,x_{n_{x}})+d_{X}(x_{n_{x}},x_{n_{z}}+d_{X}(z,x_{n_{z}})+C$
$\displaystyle\geq$ $\displaystyle d_{X}(x,z)+C\ \geq\ d_{X}(x,z).$

and

$\displaystyle d_{1}(x,y^{\prime})$ $\displaystyle=$
$\displaystyle\min\nolimits_{n\in\mathbb{N}}[d_{X}(x,x_{n})+C+d_{X}(y_{n},y)]$
$\displaystyle\leq$ $\displaystyle d_{X}(x,x_{n_{z}})+d_{X}(y_{n_{z}},y)+C$
$\displaystyle\leq$ $\displaystyle
d_{X}(x,z)+d_{X}(z,x_{n_{z}})+d_{X}(y_{n_{z}},y)+C$ $\displaystyle=$
$\displaystyle d_{X}(x,z)+d_{1}(z,y^{\prime}).$

Let us evaluate $(d_{2}\circ d_{1})(x_{k},x^{\prime}_{k})$ and $(d_{1}\circ
d_{2})(x_{k},x^{\prime}_{k})$.

Taking fixed values $n=m=k$, $u=y_{k}$, we get

$\displaystyle(d_{2}\circ d_{1})(x_{k},x^{\prime}_{k})$ $\displaystyle=$
$\displaystyle\inf\nolimits_{u\in
X}\\{\min\nolimits_{n\in\mathbb{N}}[d_{X}(x_{k},x_{n})+C+d_{X}(y_{n},u)]$
$\displaystyle+\
\min\nolimits_{m\in\mathbb{N}}[d_{X}(u,y_{m})+C+d_{X}(x_{m},x_{k})]\\}$
$\displaystyle\leq$ $\displaystyle\inf\nolimits_{u\in
X}\\{[d_{X}(x_{k},x_{k})+C+d_{X}(y_{k},u)]$ $\displaystyle+\
[d_{X}(u,y_{k})+C+d_{X}(x_{k},x_{k})]\\}$ $\displaystyle=$
$\displaystyle[d_{X}(x_{k},x_{k})+C]+[C+d_{X}(x_{k},x_{k})]\ =\ 2C.$

Using the triangle inequality for the triangle $x_{n}x_{m}u$ and (7.1), we get

$\displaystyle(d_{1}\circ d_{2})(x_{k},x^{\prime}_{k})$ $\displaystyle=$
$\displaystyle\inf\nolimits_{u\in
X}\\{\min\nolimits_{n\in\mathbb{N}}[d_{X}(x_{k},y_{n})+C+d_{X}(x_{n},u)]$
$\displaystyle+\
\min\nolimits_{m\in\mathbb{N}}[d_{X}(u,x_{m})+C+d_{X}(y_{m},x_{k})]\\}$
$\displaystyle\geq$ $\displaystyle\inf\nolimits_{u\in
X}\\{\min\nolimits_{n\in\mathbb{N}}[d_{X}(x_{k},y_{n})+d_{X}(x_{n},u)]$
$\displaystyle+\
\min\nolimits_{m\in\mathbb{N}}[d_{X}(u,x_{m})+d_{X}(y_{m},x_{k})]\\}$
$\displaystyle\geq$
$\displaystyle\min\nolimits_{n,m\in\mathbb{N}}[d_{X}(x_{k},y_{n})+d_{X}(x_{n},x_{m})+d_{X}(y_{m},x_{k})]$
$\displaystyle>$ $\displaystyle k+d_{X}(x_{n},x_{m})+k\ >\ 2k.$

Thus, for the sequence $\\{x_{k}\\}_{k\in\mathbb{N}}$ of points in $X$, the
distances $(d_{2}\circ d_{1})(x_{k},x^{\prime}_{k})$ are uniformly bounded,
while $\lim_{k\to\infty}(d_{1}\circ d_{2})(x_{k},x^{\prime}_{k})=\infty$,
hence the metrics $(d_{2}\circ d_{1})$ and $d_{1}\circ d_{2}$ are not
equivalent, i.e. $[d_{2}][d_{1}]\neq[d_{1}][d_{2}]$.

∎

### References

  * [1] A. Kar, J.-F. Lafont, B. Schmidt. Rigidity of Almost-Isometric Universal Covers. Indiana Univ. Math. J. 65 (2016), 585–613.
  * [2] M. V. Lawson. Inverse Semigroups: The Theory of Partial Symmetries. World Scientific, 1998.
  * [3] V. Manuilov. Roe bimodules as morphisms of discrete metric spaces. Russian J. Math. Phys., 26 (2019), 470–478.
  * [4] V. Manuilov. Metrics on doubles as an inverse semigroup. J. Geom. Anal., to appear.
  * [5] V. Manuilov. Metrics on doubles as an inverse semigroup II. J. Math. Anal. Appl., to appear.
  * [6] A. L. T. Paterson. Groupoids, Inverse Semigroups, and their Operator Algebras. Springer, 1998.


Towards Compliant Data Management Systems for Healthcare ML
Towards Compliant Data Management Systems

Goutham RamakrishnanThe work was performed during an internship at Microsoft Research, Cambridge, UK1 Aditya Nori2 Hannah Murfet2 Pashmina Cameron2

Ramakrishnan et al.

University of Wisconsin–Madison Microsoft Research Cambridge

The increasing popularity of machine learning approaches and the rising awareness of data protection and data privacy presents an opportunity to build truly secure and trustworthy healthcare systems. Regulations such as GDPR and HIPAA present broad guidelines and frameworks, but the implementation can present technical challenges.
Compliant data management systems require enforcement of a number of technical and administrative safeguards. While policies can be set for both safeguards there is limited availability to understand compliance in real time.
Increasingly, machine learning practitioners are becoming aware of the importance of keeping track of sensitive data.
With sensitivity over personally identifiable, health or commercially sensitive information there would be value in understanding assessment of the flow of data in a more dynamic fashion.
We review how data flows within machine learning projects in healthcare from source to storage to use in training algorithms and beyond. Based on this, we design engineering specifications and solutions for versioning of data. Our objective is to design tools to detect and track sensitive data across machines and users across the life cycle of a project, prioritizing efficiency, consistency and ease of use. We build a prototype of the solution that demonstrates the difficulties in this domain. Together, these represent first efforts towards building a compliant data management system for healthcare machine learning projects.

compliance, data tracking, data discovery, data versioning

§ INTRODUCTION

Data-driven machine learning approaches have grown in prominence over the last decade, including in cross-disciplinary research areas such as healthcare.
In the healthcare domain, the data is often of a sensitive and confidential nature, thus requiring careful data protection and privacy practices by the data users.
For example, images of MRI scans obtained from hospitals, which are used to train machine learning models for cancer diagnosis (see Figure <ref>), often contain personally identifiable information (PII) or Protected Health Information (PHI) at source.
The use of such sensitive data necessitates extreme care to ensure compliance with local data protection laws and
any contractual obligations. Failure to do so may have damaging consequences for the patients, for example one scenario could be a situation where a group of individual's health records leaked, identity information stolen, and consequently they become a target of phishing attacks. Organizations who act as data controllers may face consequences such as loss of trust and reputation, loss of business, hefty fines<cit.> or even lawsuits <cit.>. Contractual obligations often take the form of a data sharing agreement between the data sharer and the research institution. Often these  data sharing agreements require constraints <cit.> including how the data will be used, for what purposes, for use by specific individuals, require deletion after a given retention period, to not attempt to re-identify individuals and prohibit further disclosure.

The data-flow across the stages of a machine learning pipeline for healthcare

With the increasing prevalence of data-driven approaches, regulatory bodies across the world have already or are in the process of enacting strict data protection and privacy laws.
General Data Protection Regulation (GDPR)<cit.> is a prominent example of such a law, which provides safeguards for citizens of the European Union. HIPAA <cit.> is an example of data privacy and security regulation from the United States.
GDPR enforces strict regulations on the collectors and processors of data and imposes heavy penalties upon their violation.
Organizations usually appoint a Data Protection Officer (DPO), who can help monitor internal data access and advise on matters relating to data protection, for ensuring accountability.
From our review, there are limited software tools which are specifically designed to help and improve the work efficiency of DPOs and privacy officers that support the full data lifecycle.

Tracking the flow (and copies) of data in real time, before a project starts, during the project and after the project has concluded can be challenging, and currently there are few tools to support data tracking over the entire project life cycle. Version control tools for source code are well understood, but the tools required for data versioning are still in the nascent stage. Compliance in healthcare requires a good data versioning system as a minimum, but has needs that beyond this. Data flow within healthcare needs to be tracked not only across different versions, but also across different permission levels and different data classifications (e.g. anonymous vs. pseudonymous).
The challenges associated with developing such tools stem from the inherent complexity of modern project workflows.

* Each project may have multiple researchers working on it, each researcher may have multiple machines on which they work.

* Each machine may also be used by more than one researcher.

* Each project may have multiple data sets and each data set may contain multiple sensitive data elements.

* A project or a study may conclude, which may lead to a need to delete all copies of the data used for such a study

* The permission to use certain data sets may be time-limited, leading to a need to track and delete all copies of the data set including derivatives

Keeping these in mind, our objective is to design tools to detect and track sensitive data across machines and users across the life cycle of a project, prioritizing efficiency, consistency and ease of use. Specifically, at various stages of a project, the permissions to access, modify and delete data may vary, so we need tools to periodically (at some pre-specified frequency) assess the compliance of data storage and usage to the relevant regulations.

We aim to build tools to enforce compliance while keeping the overhead minimal. More often than not, there is a deep desire to comply to data protection rules, but these rules can be quite complex and may change over time. Integrating the data protection rules within the machine learning workflows for healthcare makes using automated tools for tracking data movements makes it easier for researchers to build trustworthy systems.
Healthcare ML practitioners are the primary data feeders to the tool and the DPO or privacy officer is the primary consumer of the tool in order to monitor data compliance. As adoption of the tool grows, more stringent compliance requirements can be monitored and adhered to within the tool.

Complete and provably correct enforcement of data compliance is a very difficult task, and as yet an unsolved problem. There have been some attempts to solve a part of the problem <cit.> using formal policy language, but such tools largely use static policies (they only inspect the source code) to perform verification; compliance with data protection rules requires software validation as well. Each project has different requirements, each machine learning system has different vulnerabilities and each region and type of data has different levels of sensitivity associated with it.
Discovering and mitigating vulnerabilities and data leakage (or model leakage) within machine learning <cit.> (or indeed even a given software system and hardware platform <cit.>) is a very active area of research.
Even if all three of these aspects were fully understood, any system that imposes full `surveillance' upon those working with the data would indeed feel over burdensome to a researcher new to working in this area.
Recently, there has been an increased focus on privacy regulations, and it will take some time for users to fully appreciate and accustom themselves with the changing landscape.
Thus, in order to encourage uptake of a new tool, changes made to existing systems have to be gradual and incremental, always keeping in mind the human factor.
Without formal verification guarantees, we have no way of automatically ensuring the compliance of the outputs generated by the scripts used to process the data.

We envision a data management system that is built specifically with the aim of enforcing and demonstrating compliance to data protection regulations.
The design and implementation of such a system must facilitate ease of use and prove useful across different roles in an organization.
While it must help individual researchers and developers keep track of their data, it must also function in a broader scope to enable managers and DPOs/ privacy officers to track compliance across projects and teams at the organizational level.

The data management tool must comply with the following high-level specifications, in order to ensure data protection (privacy and security):

Data discovery: Find all data with potentially sensitive data across all storage mechanisms, all relevant file formats, and machines for all users. Determine the level of sensitivity of the data. Scan the storage systems at a user-specified frequency to facilitate automated monitoring of data.

Data versioning: Detect all file changes since last scan, including changes to contents, metadata or location of the file. Detect if any files have been deleted or created. Use hashing to compare contents of a file. Log this information using a globally unique identifier such that each file, the machine on which the files resides and the user of the data can be identified uniquely.

Storage and review: Store the information gathered from the scans in a database. The database schema must be such that an intuitive interface for reviewing the stored logs can be implemented efficiently. Ensure recentness and consistency of logs. Allow a concept of staleness in the database to indicate out-of-date information in case the scans fail for some reason.

As a first step towards building such a tool, we have built a prototype system with the following fine-grained software specification:

* Each sensitive file should be tracked by the system. Each file is uniquely identified by it's filepath and SHA-256 hash.

* When a file is moved or copied, a new file is considered to have been created due to changes to it's filepath.

* When the contents of a file are changed, a file is considered to be modified due to changes to it's SHA-256 hash.

* Researchers handling the data specify the root folders of all locations (including all machines) where sensitive data is stored. The completeness of the scans done by the compliance tool relies on researchers taking care to provide a complete list of root folders. Subfolders and compressed folders are checked automatically.

* File formats such as DICOM contain image pixel data and patient information as metadata in a single bundle. It may be important to track modifications in the pixel data and metadata independently (using hash values).

* Metadata such as `Last Scanned' and `Last Modified' are useful to check if the logged information is up-to-date.

* If sensitive data is read and processed by a program, and some derivative data is created, the derivative data is assumed to be sensitive in the absence of any further information provided by the researchers. In a future version, researchers may be able to whitelist certain programs that they know do not produce any sensitive derived data. Additionally, formal verification tools such as <cit.> may be used to automatically determine whether certain programs conform to their original software specification (and thus provide guarantees on the sensitivity of the derived data), but this is beyond the scope of this work.

§ WHY DATA VERSIONING IS NOT ENOUGH

Version control for source code is a well-studied problem in the domain of software engineering and several implementations are available for use, with git<cit.> being one of the most preferred tools used by developers.
Machine learning research requires version control for data in addition to source code.
With the increasing emphasis on reproducible research in machine learning over the last few years, several tools which provide the facility of data versioning have emerged.

Git-LFS<cit.> provides storage functionality for large data files along with seamless integration with git. It replaces large files with text pointers inside git, while the data itself is stored on a remote server. However a major shortcoming is that the files are stored as blobs and thus the data files cannot be diffed.
Pachyderm<cit.> offers a comprehensive data versioning system, with repositories for data, flexible data pipelines and support for cloud-based computing. However it is a heavyweight software, and the data needs to be copied in and out of the Pachyderm cluster to use it.
Quilt<cit.> offers a simple model that represents data as python packages. However, it may not scale well to large data inputs and its usage-APIs are implemented only in python and R.
DVC<cit.> provides the functionality of data dependency tracking along with git integration. It is an open-source tool, easy to learn and run.
MissingLink<cit.> offers an end-to-end management of machine learning projects, with version control for data being a key feature. This requires users to upload data on to missinglink.ai servers. Some commercial solutions that are not tailored to a machine learning workflow do exist <cit.>, but these ordinarily don't cater to machine learning workflows where high-throughput data access for training, fine-tuning and debugging models is required. In some cases, the contractual restrictions may also require the data to be hosted within certain institutional boundaries, which may mean that such a tool cannot be used if the data is not stored on premise.

However, the use of the above tools on sensitive data in the healthcare domain presents several challenges from the compliance perspective. Sensitive data cannot be uploaded to third-party servers, first because the data may leak, or be tampered with, and second because the servers may well be in a different geographic region from the data, both of which may not be acceptable from a compliance point of view. File formats such as DICOM and NIFTII constitute a bundle of patient information along with pixel data, it may be important to individually keep track of changes in both. Moreover, the sensitive data files which may be created over the course of the project cycle need to be automatically detected and tracked. The unique constraints imposed by the sensitivity of the data and the inadequacy of the existing tools for adherence to compliance (as opposed to mere enforcement) motivates the design and implementation of a new data management system for compliance.

§ METHODOLOGY

Sensitive data files may be used/created across the various stages of a typical machine learning pipeline.
In the data pre-processing stage, the raw data is cleaned, transformed and converted for consumption by the model.
Often, it becomes necessary for researchers to download the raw/transformed training data for debugging purposes.
The training, debugging and testing phases of the project may also lead to creation of sensitive data files.
The complexity of data flows of an actual machine learning project are shown in the flowchart in Figure <ref>.
A compliant data management system should give users the ability to track and monitor sensitive data across machines across the project cycle, thus making it easy for them to be compliant.
We visualize such a system to have three key components: data discovery, data versioning and data review.

§.§ Data Discovery

A key prerequisite for any system that tracks data compliance is the ability to find all files containing sensitive data. Asking the user to specify which files are sensitive rather puts the onus on to the ML researcher. The specific files that contain sensitive data may also change over the course of the project. Often sensitive data can be isolated to one or more specialized file formats for a particular project (for example, a project using MRI scan images may restrict itself to just DICOM files).
However, a simple directory-walk or search based on file extensions is not adequate for finding all sensitive files.
For completeness of the file discovery, in addition to searching for specified file extensions, it is necessary to account for the following:

* Files may be present in a compressed format (e.g. as a `gz' or inside a `zip')

* Files may be present inside temporary folders (and therefore not have the same file extension)

* Files may be present under a different extension as a result of bugs in code generating them or deliberate attempt to fool file discovery. In such cases, it becomes necessary to check the file signature (usually by reading the initial few bytes of the file) to determine the file format. It may also be useful to gather additional information about the files. For example, DICOM files may not have the `.dcm' extension, may or may not have a well-formed preamble and may be stored in little or big endian.

* There may also be files in a system that present themselves as one of our specified formats, but are in fact just text or image files. The system must be able to deal with these files accordingly. For example, a `.dcm' file may be renamed as `.jpg', a `.jpg' may be renamed as a `.dcm'. When configured to look for `.dcm' file, all files that are truly `.dcm', whatever the extension must be identified and tracked by our compliance checker.

Depending on the properties of any particular file format, additional steps may be necessary to ensure the exhaustiveness of the file discovery.

§.§ Data Versioning

Across the life-cycle of a machine learning project, new data files may be created and old data files may be modified, moved or deleted.
From a compliance perspective, it is imperative that we are able to track such events.
We propose a file versioning system built according to the following guidelines:

* Each sensitive file is tracked by considering its filepath to be invariant. When it is moved or copied, a new file is considered to have been created.

* Changes in the file (and therefore new versions) are detected by comparing with the SHA-256 hash values of the file contents.

* File formats such as DICOM contain image pixel data and patient information as metadata in a single bundle. It may be important to track modifications in the pixel data and metadata independently (using hash values).

* Metadata such as `Last Scanned' and `Last Modified' are useful to check if the logged information is up-to-date.

The information gathered from the `Compliance Checker Scan' (i.e. data discovery followed by data versioning) must be stored in the back end.

§.§ Data Review Interface

The information logged by the data discovery and versioning stages must be easily available for review, in an intuitive interface.

* The interface must automatically retrieve the latest information from the backend.

* It must allow the DPO or privacy officer to filter and view information pertaining to specific fields (such as machine, user, scan time, file format, etc.)

* It must allow the DPO or privacy officer to check for the recentness of the information in the logs.

* A utility that allows the DPO or privacy officer to email the user of a given machine in order to remind them to run the scan would be very useful as well.

Depending on the nature of the sensitive data and the requirements of the DPO or privacy officer, the review interface may require further functionalities.

§ IMPLEMENTATION

We describe our implementation of a software prototype for the tool, the `Compliance Checker', which uses Python3.7, Azure SQL and PowerBI.

§.§ CompliCheck: A python package

The Compliance Checker software is developed as a python package, the key features of which are described below:

* The code structured using the principles of object oriented programming, and is thus easy to understand and build upon.

* The file discovery component of the package has custom file discoverers for DICOM and NIFTII file formats. The modular structure of the code allows one to add more custom file discoverers easily. It also searches inside compressed files and folders.

* The file versioning component of the package primarily acts as an interface of communication with the Azure SQL database, where the results of the compliance scans are logged.

* The package can be easily installed using the `setup.py' script.

Database Schema used by the Compliance Checker

§.§ Database Design

The schema of the Azure SQL database used is shown in Figure <ref>.
The database is structured as two tables, File_Log and MAC_log, which are described below:

* MAC_Log:
This table contains one row per user (identified by `Username') per machine (identified by MAC address). Each entry specifies the sensitive file formats to scan for, and the filepaths in which to run the scan. It is important to verify the recentness/freshness of the scans, thus we maintain the `Stale' field. The `Scan Frequency' specifies the ideal frequency of the compliance scan, and the `Last Scanned' stores the datetime corresponding to the last time the scan was run. An entry is considered `Stale' if a time greater than the `Scan Frequency' has elapsed since `Last Scanned'. Note that storing this information allows us to update the values of the `Stale' column in a self-sufficient manner, without needing information from the File_Log.

* File_Log:
This table contains the file versioning information for every file scanned on every machine. Note that we do not store the `Username' field in this table, to avoid duplicate records in case of shared folders on machines. The `Version' is an integer, and the `Status' specifies whether an entry is `Latest Version', `Old Version' or `Deleted'. The `Last Modified' field stores the scan datetime of the scan when the version (i.e. change in file) was detected. The other fields in the table are self-evident, and have been justified in Section <ref>.

§.§ Running the Compliance Checker

When running the compliance checker for the first time for a new machine-user combination, an entry must be created in the MAC_Log table first.
When the `Run' operation is called, the paths and formats to be scanned are retrieved from the MAC_Log.
The compliance scan begins and the results are stored in the File_Log table.
Note that the compliance scan is an atomic operation, i.e. the scan either succeeds or fails in its entirety.
The changes to the backend database are only committed at the end of the scan, thus ensuring consistency.
A `Paths', `Formats' and `Scan Frequency' of a pre-existing entry in the MAC_Log can be modified if necessary.
To ensure recentness/freshness of the `Stale' column in the MAC_Log, all entries are updated at the end of a compliance scan on any machine.
All of the above operations can be achieved through running the program with appropriate arguments.

Note that our implementation of data versioning is `storage-free'. Therefore, it only detects new versions of files and does not offer the ability to revert to old versions. Development of this feature is left for future work.

PowerBI Report for Compliance Review. The deviations from previous versions of the data can be reviewed by the DPO or privacy officer using this interface.

§.§ Deployment and Automation

The development of the software as a python package enables us to deploy the tool across machines easily.
In addition, to ensure regularity of scanning, it is important to automate the running of the tool on machines.
On Linux machines, this can be implemented as a cron job.
On Windows machines, automation can be achieved by scheduling a task to run periodically.
Automatic scans are especially useful and important when working with virtual machines/cloud computing.
To this end, we have developed batch/bash scripts for use by system administrators to install the software and setup the automation on machines.

§.§ PowerBI Interface

As a review interface, we have created a PowerBI report for viewing the results of the compliance checker program (as shown in Figure <ref>).
The interface allows the DPO or privacy officer to view the results of the compliance scans across machines, filtered by format, scan-time, version and staleness.
It is directly linked to the Azure SQL database to retrieve the latest data. This is a viewing tool only, at the moment. In future, a more comprehensive user interface could provide additional functionality such as adding file formats to be checked or sending reminders to users to run the compliance checker tool on a particular machine if stale data is detected.

§ CONCLUSION

Compliance with data privacy and protection laws are a priority for modern organizations, thus motivating the need for a data management system built specifically for the purpose of facilitating adherence to compliance regulations. Even when entities have the best intentions, proving compliant behaviour is extremely hard. Therefore, at some level, collaborations in healthcare (or other spaces that includes handling sensitive or personal data) are based on trust. However, with recent high-profile cases have proven that implicit promise of trust is no longer sufficient and we need to put system level checks in place to ensure and verify good behaviour.
In this paper, we have reported on ongoing work towards the design of tools to that end and present a prototype implementation of the software.

Future work will explore (a) a more nuanced methodology for discovering sensitive data, for example, discovering PII data, anonymised vs non-anonymised data, etc.; (b) building a fully-fledged data version control system with compliance in mind rather than trying to add compliance as an after-thought; (c) building a dedicated software front-end for review that also allows the DPO or privacy officer to send reminders to project team members. In a future version, one could also envisage a customizable definition of data versioning for each application. The changes that constitute a new version may not be the same for each application and it would be desirable to track the attributes that matter most for each use case.


$\mathfrak{Q}$ is CS (as we may extend the field $\mathbb{k}$; see Section
missing 4). Let $Q\subset S$ be the standardization of $P\subset R$. Since
ideal extension $QW\subset W$ has the same multigraded Hilbert function as
$\mathfrak{Q}\subset W$, it follows that $QW$ is CS, and so [CDNG_CS_IDEALS,
Proposition 2.7] implies that $Q\subset S$ is also CS. Finally, $P\subset R$
is CS by §missing 7.1. ∎

The theorem below lists some important basic properties of CS ideals in $R$.

######  Theorem 7.3.

Assume Section missing 7. Let $I\subset R$ be an $R$-homogeneous CS ideal.
Then the following statements hold:

  1. (i)

${\text{in}}_{>}(I)$ is radical and CS for any monomial order $>$ on $R$; in
particular, $I$ is radical.

  2. (ii)

The $\mathbb{N}$-graded Castelnuovo-Mumford regularity $\text{reg}(I)$ is
bounded from above by $p$.

  3. (iii)

$I$ is a multiplicity-free ideal.

  4. (iv)

If $P\subset R$ is a minimal prime of $I$, then $P$ is CS.

  5. (v)

All reduced Gröbner bases of $I$ consist of elements of multidegree
$\leq(1,\ldots,1)\in\mathbb{N}^{p}$. In particular, $I$ has a universal
Gröbner basis of elements of multidegree $\leq(1,\ldots,1)\in\mathbb{N}^{p}$.

###### Proof.

(i) It follows from Theorem 7.1(v) and [conca2022radical, Proposition 3.4(2)].

(ii) It is a consequence of Theorem 7.1(ii) and [conca2022radical, Proposition
3.4(3)].

(iii) It follows from Theorem 7.1(iii) and [conca2022radical, Proposition
3.6(1)].

(iv) Since $I$ is multiplicity-free, we conclude that $P$ also is. We then
obtain the result from §missing 7.1.

(v) It follows from Theorem 7.1(v) and [conca2022radical, Proposition 3.4(6)].
∎

Finally, we point out some interesting consequences of our work, that signal
very rigid properties of certain multigraded Hilbert functions. To that end,
we use the multigraded Hilbert scheme of Haiman and Sturmfels
[HAIMAN_STURMFELS]. For a given function
$h:\mathbb{N}^{p}\rightarrow\mathbb{N}$, the multigraded Hilbert scheme
${\text{HS}}_{R/\mathbb{k}}^{h}$ parametrizes all $R$-homogeneous ideals
$I\subset R$ such that
$\dim_{\mathbb{k}}\left(\left[R/I\right]_{\nu}\right)=h(\nu)$ for all
$\nu\in\mathbb{N}^{p}$. We have the following rigidity result that extends
[CS_PAPER, Theorem 2.1 and Corollary 2.6].

######  Corollary .

Assume Section missing 7. Let $h:\mathbb{N}^{p}\rightarrow\mathbb{N}$ be a
function and consider the corresponding multigraded Hilbert scheme
${\text{HS}}_{R/\mathbb{k}}^{h}$. If ${\text{HS}}_{R/\mathbb{k}}^{h}$ contains
a $\mathbb{k}$-point that corresponds to a CS ideal and a $\mathbb{k}$-point
that corresponds to a prime ideal, then any $\mathbb{k}$-point in
${\text{HS}}_{R/\mathbb{k}}^{h}$ corresponds to an ideal that is Cohen-
Macaulay and CS.

###### Proof.

Let $[P],[H]\in{\text{HS}}_{R/\mathbb{k}}^{h}$ be $\mathbb{k}$-points in
${\text{HS}}_{R/\mathbb{k}}^{h}$ such that $P\subset R$ is a prime ideal and
$H\subset R$ is a CS ideal. Let $I\subset R$ be an $R$-homogeneous ideal such
that $[I]\in{\text{HS}}_{R/\mathbb{k}}^{h}$. From the definition, it follows
that $I$ and $P$ are both CS. We may assume that $\mathbb{k}$ is a infinite
field and keep the primeness of $P$ (see Section missing 4). Let $J\subset S$
and $Q\subset S$ be the standardizations of $I$ and $P$, respectively. Since
$J$ and $Q$ are CS, both ${\text{gin}}(J)$ and ${\text{gin}}(Q)$ are radical,
and actually are equal. Then ${\text{gin}}(J)={\text{gin}}(Q)$ is Cohen-
Macaulay by Section missing 7. Finally, $J\subset S$ is Cohen-Macaulay and
Theorem 7.1(iv) implies that $I\subset R$ is also Cohen-Macaulay; which
concludes the proof. ∎

##  8\. Examples of determinantal ideals with a fine grading

The goal of this section is to present examples of multigraded ideals in non-
standard positive multigraded polynomial rings that have a multiplicity-free
multidegree. The examples we selected are determinantal ideals.

We start with generic determinantal ideals with the finest multidegree
structure. Let $\mathbb{k}$ be a field and set
$R=\mathbb{k}[x_{i,j}\mid(i,j)\in[m]\times[n]]$ with $m\leq n$. We give $R$ a
multigraded structure by setting
$\deg(x_{i,j})={\mathbf{e}}_{i}\oplus\mathbf{f}_{j}\in\mathbb{N}^{m}\oplus\mathbb{N}^{n}$
where ${\mathbf{e}}_{1},\dots,{\mathbf{e}}_{m}$ and
$\mathbf{f}_{1},\dots,\mathbf{f}_{n}$ are the canonical bases of
$\mathbb{N}^{m}$ and $\mathbb{N}^{n}$, respectively. The determinantal ideal
$I_{r}$ of the $r$-minors of the $m\times n$ generic matrix $X=(x_{i,j})$ is
then $R$-homogeneous. We have:

######  Theorem 8.1.

The $\mathbb{k}$-algebra $R/I_{m}$ has a multiplicity-free multidegree with
respect to the $\mathbb{N}^{m}\oplus\mathbb{N}^{n}$-grading.

A combinatorial formula for the multidegree of $R/I_{r}$ is described in
[miller2005combinatorial, Chap.15 and 16] (up to certain sign changes).
Indeed, by [miller2005combinatorial, Theorem 15.40 and Corollary 16.30], the
multidegree of a larger family of determinantal ideals, the Schubert
determinantal ideals, is given in terms of pipe-dreams (i.e., special tiling
of the rectangles by crosses and elbow joints). So one could derive Theorem
8.1 from the results in [miller2005combinatorial]. Nevertheless, we present
below a self-contained proof of Theorem 8.1. To simplify the notation, we set

$\mathcal{K}_{m,n}=\mathcal{K}(R/I_{m};t_{1},\dots,t_{m},s_{1},\dots,s_{n})\quad\text{
and
}\quad\mathcal{C}_{m,n}=\mathcal{C}(R/I_{m};t_{1},\dots,t_{m},s_{1},\dots,s_{n}).$

Indeed, we prove the following formula from which Theorem 8.1 follows
immediately.

######  Theorem 8.2.

$\mathcal{C}_{m,n}\,=\,\sum_{(\mathbf{a},\mathbf{b})\in
T}{\mathbf{t}}^{\mathbf{a}}{\mathbf{s}}^{\mathbf{b}}$

with
$T=\big{\\{}(\mathbf{a},\mathbf{b})\in\mathbb{N}^{m}\times\\{0,1\\}^{n}\,\mid\,|\mathbf{a}|+|\mathbf{b}|=n-m+1\big{\\}}$.

For the proof Theorem 8.2 we denote by $H_{m,n}$ the right hand side of the
equality, i.e.

$H_{m,n}\,=\,\sum_{(\mathbf{a},\mathbf{b})\in
T}{\mathbf{t}}^{\mathbf{a}}{\mathbf{s}}^{\mathbf{b}}$

with
$T=\big{\\{}(\mathbf{a},\mathbf{b})\in\mathbb{N}^{m}\times\\{0,1\\}^{n}\,\mid\,|\mathbf{a}|+|\mathbf{b}|=n-m+1\big{\\}}$.
Firstly we observe that $H_{m,n}$ satisfies the following recursion:

######  Lemma .

For all $n>m>1$, one has $H_{m,n}=s_{n}H_{m,n-1}+t_{m}H_{m,n-1}+H_{m-1,n-1}$.

###### Proof.

The first addend corresponds to the sum of all the monomials in $H_{m,n}$ that
contain $s_{n}$. The second corresponds to the sum of all the monomials in
$H_{m,n}$ that do not contain $s_{n}$ and contain $t_{m}$. Finally the third
addend corresponds to the sum of all the monomials in $H_{m,n}$ that do not
contain $s_{n}$ and $t_{m}$. Here it is important to observe that
$n-m+1=(n-1)-(m-1)+1$. ∎

Secondly we observe that also $\mathcal{C}_{m,n}$ satisfies the same recursion
of Section missing 8.

######  Lemma .

For all $n>m>1$, one has
$\mathcal{C}_{m,n}=s_{n}\mathcal{C}_{m,n-1}+t_{m}\mathcal{C}_{m,n-1}+\mathcal{C}_{m-1,n-1}$.

###### Proof.

The $m$-minors of $X$ form a Gröbner basis of $I_{m}$ with respect to the
diagonal term order. Let $J_{m,n}={\text{in}}(I_{m})$ be the monomial ideal
generated by the main diagonals of the $m$-minors of $X$. Then

$\mathcal{K}_{m,n}=\mathcal{K}(R/J_{m,n};t_{1},\dots,t_{m},s_{1},\dots,s_{n})$

and similarly for $\mathcal{C}_{m,n}$. We have a decomposition
$J_{m,n}=x_{m,n}J_{m-1,n-1}+J_{m,n-1}$ from which it follows that
$J_{m,n}+(x_{m,n})=J_{m,n-1}+(x_{m,n})$ and $J_{m,n}:(x_{m,n})=J_{m-1,n-1}$.
Therefore we have an induced short exact sequence

$0\to R/J_{m-1,n-1}\left(-\deg(x_{m,n})\right)\to R/J_{m,n}\to
R/\left(J_{m,n-1}+(x_{m,n})\right)\to 0$

and hence

(3)
$\mathcal{K}_{m,n}=(1-t_{m}s_{n})\mathcal{K}_{m,n-1}+t_{m}s_{n}\mathcal{K}_{m-1,n-1}.$

Replacing ${\mathbf{t}}$ with $\mathbf{1}-{\mathbf{t}}$ and ${\mathbf{s}}$
with $\mathbf{1}-{\mathbf{s}}$ and extracting the homogeneous component of
degree $n-m+1$ we obtain

$\mathcal{C}_{m,n}=(t_{m}+s_{n})\mathcal{C}_{m,n-1}+\mathcal{C}_{m-1,n-1},$

which concludes the proof. ∎

Now we are ready to prove Theorem 8.2.

###### Proof of Theorem 8.2.

By Section missing 8 and Section missing 8 the polynomials $H_{m,n}$ and
$\mathcal{C}_{m,n}$ satisfy the same recursive relation. Hence it suffices to
check that they agree when $m=1$ and when $m=n$. When $m=1$ the ideal $I_{m}$
is generated by a regular sequence of elements of degree
${\mathbf{e}}_{1}+\mathbf{f}_{j}$ with $j=1,\dots,m$. In this case,
$\mathcal{C}_{1,n}=\prod_{j=1}^{n}(t_{1}+s_{j})$ which clearly coincides with
$H_{1,n}$. When $m=n$ then $I_{m}$ is generated by single element of degree
$\sum_{i=1}^{m}{\mathbf{e}}_{i}+\sum_{j=1}^{m}\mathbf{f}_{j}$, and hence
$\mathcal{C}_{m,m}=\sum_{i=1}^{m}t_{i}+\sum_{j=1}^{m}s_{j}$ which coincides
with $H_{m,m}$. This concludes the proof of the theorem. ∎

######  Remark .

As a consequence of Theorem 8.1 and §missing 7.1, it follows that
$I_{m}\subset R$ is a CS ideal.

######  Remark .

By inspecting the Eagon-Northcott resolution of $I_{m}$, we may compute that
the $\mathbb{N}$-graded Castelnuovo-Mumford regularity $I_{m}$ is given by
$\text{reg}(I_{m})=m+n$. Indeed, by coarsening the
$\mathbb{N}^{m}\oplus\mathbb{N}^{n}$-grading of $R$ into an
$\mathbb{N}$-grading, we obtain that each variable $x_{i,j}$ has degree $2$
and that the ideal $I_{m}$ is generated in degree $2m$. Since the Eagon-
Northcott complex has linear maps in the $x_{i,j}$’s and length $n-m$, it
follows that $\text{reg}(I_{m})=n+m$. This shows that the upper bound of
Theorem 7.3(ii) is sharp.

######  Remark .

From the recursion of $\mathcal{K}$-polynomials stated in (missing) 3, we may
compute the following formula for the $\mathcal{K}$-polynomial of $I_{m}$:

$\mathcal{K}(R/I_{m};{\mathbf{t}},{\mathbf{s}})\;=\;1-t_{1}t_{2}\cdots
t_{m}\sum_{j=0}^{n-m}(-1)^{j}h_{j}({\mathbf{t}})e_{m+j}({\mathbf{s}})$

where $h_{j}({\mathbf{t}})$ is the complete symmetric polynomial of degree $j$
in $t_{1},\ldots,t_{m}$ (sum of all monomials of degree $j$) and
$e_{j}({\mathbf{s}})$ is the elementary symmetric polynomial of degree $j$ in
$s_{1},\ldots,s_{n}$ (sum of all squarefree monomials of degree $j$). Also,
the formula for $\mathcal{K}(R/I_{m};{\mathbf{t}},{\mathbf{s}})$ may be
obtained from the Eagon-Northcott resolution of $I_{m}$.

Finally, we point out that most determinantal varieties do not have a
multiplicity-free multidegree with respect to the
$\mathbb{N}^{m}\oplus\mathbb{N}^{n}$-grading.

######  Remark .

For $1<r<m$, the $\mathbb{k}$-algebra $R/I_{r}$ does not have a multiplicity-
free multidegree with respect to the
$\mathbb{N}^{m}\oplus\mathbb{N}^{n}$-grading. For $2<r<m$, this happens
already with respect to the $\mathbb{N}^{m}$ (row) grading and the
$\mathbb{N}^{n}$ (column) grading individually, see [conca2022radical]. We
have a significantly different behavior when $r=2$: $R/I_{2}$ has a
multiplicity free multidegree with respect to the row or column grading, but
one can check by utilizing [miller2005combinatorial] or by direct computations
that for $m,n>2$ the multidegree polynomial has coefficients $>1$ with respect
to the $\mathbb{N}^{m}\oplus\mathbb{N}^{n}$-grading. For example, when $m=n=3$
and $r=2$ the multidegree polynomial is

$\displaystyle\mathcal{C}(R/I_{2},t_{1},t_{2},t_{3},s_{1},s_{2},s_{3})\;=\;$
$\displaystyle t_{1}^{2}t_{2}^{2}+t_{1}^{2}t_{2}t_{3}+t_{1}^{2}t_{2}s_{1}+{\bf
2}t_{1}t_{2}t_{3}s_{1}+t_{1}t_{2}s_{1}^{2}+t_{1}^{2}s_{1}s_{2}+{\bf
2}t_{1}t_{2}s_{1}s_{2}+$ $\displaystyle{\bf
2}t_{1}s_{1}s_{2}s_{3}+t_{1}s_{1}^{2}s_{2}+s_{1}^{2}s_{2}s_{3}+s_{1}^{2}s_{2}^{2}+\cdots\mbox{
symmetric terms}.$

## Acknowledgments

Caminata and Conca were partially supported by PRIN 2020355B8Y “Squarefree
Gröbner degenerations, special varieties and related topics” and by GNSAGA-
INdAM. Caminata was supported by the GNSAGA-INdAM grant “New theoretical
perspectives via Gröbner bases” and by the European Union within the program
NextGenerationEU. Cid-Ruiz was partially supported by an FWO Postdoctoral
Fellowship (1220122N). This work was supported by the “National Group for
Algebraic and Geometric Structures, and their Applications” (GNSAGA – INdAM).
Cid-Ruiz is very appreciative of the hospitality offered by the mathematics
department of the University of Genova, where part of this work was done. We
thank the reviewers for carefully reading our paper and for their comments and
corrections.

## References