# Primitive Indexes, Zsigmondy Numbers, and Primoverization

Tejas R. Rao

(September 22, 2018)

Abstract. We define a _primitive index_ of an integer in a sequence to be the
index of the term with the integer as a primitive divisor. For the sequences
$k^{u}+h^{u}$ and $k^{u}-h^{u}$, we discern a formula to find the primitive
indexes of any composite number given the primitive indexes of its prime
factors. We show how this formula reduces to a formula relating the
multiplicative order of $k$ modulo $N$ to that of its prime factors. We then
introduce immediate consequences of the formula: certain sequences which yield
the same primitive indexes for numbers with the same unique prime factors, an
expansion of the lifting the exponent lemma for $\nu_{2}(k^{n}+h^{n})$, a
simple formula to find any Zsigmondy number, a note on a certain class of
pseudoprimes titled overpseudoprime, and a proof that numbers such as Wagstaff
numbers are either overpseudoprime or prime.

##  1 The Formula

A _primitive index_ of a number is the index of the term in a sequence that
has that number as a primitive divisor. Let $k$ and $h$ be positive integers
for the duration of this paper. We denote the primitive index of $N$ in
$k^{u}-h^{u}$ as $P_{N}(k,h)$. For $k^{u}+h^{u}$, it is denoted $P^{N}(k,h)$.
Note that $P_{N}(k,1)=O_{N}(k)$, where $O_{N}(k)$ refers to the multiplicative
order of $k$ modulo $N$. Both are defined as the first positive integer $m$
such that $k^{m}\equiv 1\mod N$. Throughout this paper, $p$ will refer to
primes.

###  1.1 Primitive Indexes in $k^{u}-h^{u}$

Proposition 1. _$N|k^{u}-h^{u}$ iff $P_{N}(k,h)|u$._
Since

$k^{P_{N}(k,h)}-h^{P_{N}(k,h)}\equiv 0\mod N\Longleftrightarrow
k^{P_{N}(k,h)}\equiv h^{P_{N}(k,h)}\mod N$,

raising both $k$ and $h$ to a multiple of $P_{N}(k,h)$ will maintain the
divisibility. In the other direction, since $N\nmid k^{u}-h^{u}$, where
$u<P_{N}(k,h)$, then $k^{u}\not\equiv h^{u}\mod N$, and, for any positive
integer $m$,

$k^{P_{N}(k,h)m+u}=k^{P_{N}(k,h)m}k^{u}\not\equiv
h^{P_{N}(k,h)m}h^{u}=h^{P_{N}(k,h)m+u}\mod N$.

This proposition also shows that $N_{1}|N_{2}$ iff
$P_{N_{1}}(k,h)|P_{N_{2}}(k,h)$ for all $k$ and $h$, providing the primitive
indexes exist.
Proposition 2. _If $gcd(N,k)=gcd(N,h)=1$, $P_{N}(k,h)|lcm(O_{N}(k),O_{N}(h))$
and $P_{N}(k,h)|\lambda(N)$._
Since $k^{\lambda(N)}\equiv h^{\lambda(N)}\equiv 1\mod N$ and
$k^{lcm(O_{N}(k),O_{N}(h))}\equiv h^{lcm(O_{N}(k),O_{N}(h))}\equiv 1\mod N$,
the result follows from the previous proposition. Additionally,
$P_{N}(k,h)\neq O_{N}(k)$ and $P_{N}(k,h)\neq O_{N}(h)$ if $O_{N}(k)\neq
O_{N}(h)$. It would be impossible for $k^{P_{N}(k,h)}\equiv h^{P_{N}(k,h)}\mod
N$ if this were true.
We will now present a modified version of a lifting the exponent [3] proof to
fit primitive indexes.

######  Theorem 1.

For $gcd(p,h)=1$, and for $k-h\neq 2(odd)$ and/or $p\neq 2$,

(1)

where $a-1\geq\nu_{p}(k^{u}-h^{u})$, where $\nu_{p}(k^{u}-h^{u})$ is the
largest $i$ such that $u=P_{p^{i}}(k,h)=P_{p}(k,h)$.
For $gcd(p,h)=1$, and for $k-h=2(odd)$ and $p=2$,

(2)

where $a-1\geq\nu_{2}(k^{2}-h^{2})$, where $\nu_{2}(k^{2}-h^{2})$ is the
largest $i$ such that $2^{i}|k^{2}-h^{2}$.

Take a prime $p$. If $p^{a}|k^{u}-h^{u}$, then for some positive integer $m$,
$k^{u}-h^{u}=p^{a}m\Longrightarrow k^{u}=p^{a}m+h^{u},$ where $p\nmid m$ and
$a$ is the largest power of $p$ that divides $k^{u}-h^{u}$. Since
$P_{p^{a}}(k,h)|P_{p^{a+1}}(k,h)$ by Proposition 1, $P_{p^{a+1}}(k,h)$ is a
multiple of $P_{p^{a}}(k,h)$. To search for this we do the following. For some
integer $f\leq p$, we take the binomial expansion of
$k^{uf}-h^{uf}=(p^{a}m+h^{u})^{f}-h^{u}$:

$(\binom{f}{0}(p^{a}m)^{f}+\binom{f}{1}(p^{a}m)^{f-1}h^{u}+...+\binom{f}{f-2}(p^{a}m)^{2}h^{u(f-2)}+\binom{f}{f-1}(p^{a}m)^{1}h^{u(f-1)}+h^{uf})-h^{uf}$.

Then we cancel $h^{uf}$ and $-h^{uf}$ and factor out $p^{a}$:

$p^{a}(\binom{f}{0}p^{a(f-1)}m^{f}+\binom{f}{1}p^{a(f-2)}m^{f-1}h^{u}+...+\binom{f}{f-2}p^{a}m^{2}h^{u(f-2)}+\binom{f}{f-1}mh^{u(f-1)}).$

If $\binom{f}{f-1}$ does not have a factor of $p$, then the expansion equals
$pM+mh^{u(f-1)}\binom{f}{f-1}$ for some positive integer M. Recall that
$p\nmid m$, and thus $p\nmid pM+mh^{u(f-1)}\binom{f}{f-1}$, as long as
$gcd(p,h)\neq 1$. We thus specify $gcd(p,h)\neq 1$. This means that the only
time when another factor of $p$ emerges is when the final term has a factor of
$p$. For $f\leq p$, this only occurs when $f=p$:

$\binom{p}{p-1}mh^{u(f-1)}=\dfrac{p!}{(p-(p-1))!(p-1)!}mh^{u(f-1)}=pmh^{u(f-1)}.$

_Case 1_ ($a>1,$ $p$ odd): We can thus factor out exactly one more factor of
$p$ for the first time at $k^{up}-h^{up}$, making
$P_{p^{a+1}}(k,h)=up=pP_{p^{a}}(k)$, since the first time $p|k^{u}-h^{u}$ is
$u=P_{p^{a}}(k,h)$.
_Case 2_ ($a=1$, $p$ odd): In only this case for odd numbers, the second last
term is $\binom{p}{p-2}m^{2}h^{u(f-2)}$ after $p^{2}$ is factored out. But
since $\binom{p}{p-2}m^{2}h^{u(f-2)}=\frac{p-1}{2}(p)(m^{2})h^{u(f-2)}$, the
second term still has a factor of $p$ and thus still yields $pM+mh^{u(f-1)}$
for the binomial as a whole, meaning there are no more factors of $p$.
_Case 3_ ($p=2$, $a=1$): After factoring out $2^{2}$ from
$(2m+h^{u})^{2}-h^{2u}$, we get:

$(2^{2})(m^{2}+h^{u}m)=(2^{2})(m(m+h^{u})).$

Since $2\nmid m$ or$h^{u}$, $m$ and $h^{u}$ are odd and thus $m+h^{u}$ is even
and has at least one more factor of $2$. This means that, if there is
_exactly_ one factor of $2$ in $P_{2}(k,h)$, then
$P_{2^{x}}(k,h)=2(P_{2}(k,h))$, where $x\geq 3$. This case is unique because
$a=1$ as in Case $2$, and yet $2$ is even, meaning $2\nmid p-1=2-1$.
_Case 4_ ($p=2$, $a>1$):
After factoring out $2^{a+1}$, the final two terms of the binomial expansion
are
$\frac{2^{a+1}-2^{a}}{2}m^{2}h^{u(f-2)}+m=(2^{a}-2^{a-1})m^{2}h^{u(f-2)}+mh^{u(f-1)}=odd$,
since neither $m$ nor $h$ can be even. It therefore cannot be divisible by
$2$. This means that there are no more factors of $2$.
Equation (1) arises from the fact that either $k-h$ is odd and $2$ does not
divide any term in the sequence, or $k-h$ is even such that $k-h\neq 2(odd)$,
meaning $k-h=2(even)$, and thus the first term, $k-h$, is divided by at least
$2^{2}$, and every power of $2$ greater than $1$ behaves normally. For
equation (2), when $k-h=2(odd)$, it has exactly one factor of two, meaning
that $k^{2}-h^{2}$ is divided by _at least_ $2^{3}$ by Case 3. Thus, the
powers of $2$ will behave normally for sure only after the greatest power of
$2$ that divides $k^{2}-h^{2}$.
Corollary. _For $gcd(p,h)=1$,_

$P_{p^{a}}(k,h)=p^{a-\gamma_{p}(k,h)}P_{p}(k,h)$,

where

$\gamma_{p}(k,h)=\begin{cases}\nu_{p}(k^{u}-h^{u})&\text{if $k-h\neq 2(odd)$
and/or $p\neq 2$ and where $u=P_{p}(k,h)$;}\\\ \nu_{2}(k^{2}-h^{2})&\text{if
$k-h=2(odd)$ and $p=2$.}\\\ \end{cases}$

Corollary. __

$P_{nf^{a+1}}(k,h)=fP_{n}(k)$_,_

_if $gcd(f,h)=1$ and the maximum power of $f$ that divides
$k^{P_{n}(k,h)}-h^{P_{n}(k,h)}$ is $a$._
Corollary. _For $gcd(n,h_{1})=gcd(n,h_{2})=1$, iff
$\gamma_{n}(k_{1},h_{1})=\gamma_{n}(k_{2},h_{2})$ and
$P_{n}(k_{1},h_{1})=P_{n}(k_{2},h_{2})$, then
$P_{n^{a}}(k_{1},h_{1})=P_{n^{a}}(k_{2},h_{2})$ for all positive integers
$a$._
Proposition 3. _For $N=n_{1}n_{2}...$, where $gcd(N,h)=1$ and
$gcd[n_{i}]_{i}=1$,_

$P_{N}(k,h)=lcm[P_{n_{i}}(k,h)]_{i}$.

From Proposition 1, $n_{i}|k^{u}-h^{u}$ iff $P_{n_{i}}(k,h)|u$. All factors of
coprime $n_{i}$ thus divide $k^{u}-h^{u}$ for the first time when
$u=lcm[P_{n_{i}}(k,h)]$.

######  Theorem 2.

For $N=p_{1}^{p_{1}}p_{2}^{p_{2}}...$, $p_{i}$ prime, and $gcd(N,h)=1$,

$P_{N}(k,h)=(\displaystyle\prod_{i}{n_{i}^{a_{i}-\gamma_{n_{i}}(k,h)})}lcm[P_{n_{i}}(k,h)]_{i}$.

We combine the previous properties to achieve this. If we let each
$n_{i}=p_{i}$, $p_{i}$ prime, then $gcd[p_{i}]_{i}=1$, and we can find the
order of any composite number coprime with the base $h$.
This reduces to

$O_{N}(k)=(\displaystyle\prod_{i}{n_{i}^{a_{i}-\gamma_{n_{i}}(k)})}lcm[O_{n_{i}}(k)]_{i}$,

for multiplicative order.
We will now inspect certain sequences that yield the same primitive indexes
for all numbers with specified prime factors.

######  Theorem 3.

For any prime $p$,

$O_{p^{a}}(k+p^{\gamma_{p}(k)+1}m)=O_{p^{a}}(k),$

where $m\in\mathbb{N},m\neq 0$.

For positive integers,

$\displaystyle i^{s}-j^{s}$
$\displaystyle=(i-j)(i^{s-1}-i^{s-2}j+i^{s-3}j^{2}-...+i^{2}j^{s-3}-ij^{s-2}+j^{s-1}).$

This means, for any positive integer $m$, $k^{n}\equiv(k+pm)^{n}\mod p$
because $(k+pm)^{n}=k^{n}+((k+pm)^{n}-k^{n})$, and $(k+pm)^{n}-k^{n}$ is
divisible by $(k+pm)-k=pm$, as shown above. This means we are adding $0$
modulo $p$. It is therefore clear to see that $p$ will divide both
$k^{O_{p}(k)}-1$ and $(k+pm)^{O_{p}(k)}-1$, and no exponents less than that.
So $O_{p}(k)=O_{p}(k+pm)$. This holds true for all $p^{a}$ at $k+p^{a}m$.
Additionally, $k+p^{a}m=k+p^{b}(p^{a-b}m^{\prime})$.Therefore, at
$p^{a}=p^{\gamma_{p}(k)+1}$,

$O_{p}(k+p^{\gamma_{p}(k)+1}m)=O_{p^{2}}(k+p^{\gamma_{p}(k)+1}m)=...=O_{p^{\gamma_{p}(k)}}(k+p^{\gamma_{p}(k)+1}m)=O_{p}(k),$

and

$O_{p^{\gamma_{p}(k)+1}}(k+p^{\gamma_{p}(k)+1}m)=O_{p^{\gamma_{p}(k)+1}}(k)$,

by the definition of $\gamma$. Since those two identities hold, we have proven
that
$O_{p^{\gamma_{p}(k)+1}}(k+p^{\gamma_{p}(k)+1}m)=pO_{p^{\gamma_{p}(k)+1}}(k)$
and all previous powers have the same order to that base, meaning

$\gamma_{p}(k+p^{\gamma_{p}(k)+1}m)=\gamma_{p}(k),$

and $O_{p}(k+p^{\gamma_{p}(k)+1}m)=O_{p}(k)$. These two facts together are
sufficient to prove the orders of $k$ modulo $p^{a}$ and
$k+p^{\gamma_{p}(k)+1}m$ modulo $p^{a}$ are the same by the corollaries to
Theorem 1.
Let us denote the set of all positive integers made up solely of powers of
$p_{i}$, for all chosen $i$, $i\in\mathbb{N}$, as follows:

$\eta[p_{i}]=\\{p_{1}^{a_{1}}p_{2}^{a_{2}}...|a_{i}\in\mathbb{N}_{0},p_{i}$
prime$\\}$.

A number is said to be ”in $\eta$” if it is one number made up of certain
powers of some or all of the primes listed in the brackets. The period of any
number, $N$, in $\eta$, base $k$ is defined as follows:

$\Lambda_{N}(k)=\Lambda_{\eta[p_{i}]}(k)=\displaystyle\prod_{i}{p_{i}^{\gamma_{p_{i}}(k)+1}}$.

_If $p\nmid k^{u}-1$, then we define $\gamma_{p}(k)=0$ and if $k=1$, then
$\Lambda_{N}(1)=0$._ Note that $\Lambda_{N}(k)$ is the same for every
composite or prime number with the same unique prime factors, as they are all
in $\eta$. The period of $\eta[p_{i}]$ base $k$ is defined as that of any and
all $N$ in said $\eta$. _Any_ composite number or prime number $N$ in $\eta$
will behave the same in at least every base given as follows:

######  Theorem 4.

For any number $N$ in $\eta[p_{i}]$,

$O_{\eta[p_{i}]}(k+{\Lambda_{\eta[p_{i}]}(k)}m)=O_{\eta[p_{i}]}(k).$

Since $O_{p^{a}}(k+p^{\gamma_{p}(k)+1}m)=O_{p^{a}}(k)$ from Theorem 3, we know
that $p_{1}^{\gamma_{p_{1}}(k)+1}m_{1}=p_{2}^{\gamma_{p_{2}}(k)+1}m_{2}=...$
will yield the above equality. This is the definition of $\Lambda$.

######  Theorem 5.

For $gcd(N,h)=1$ ,

$P_{\eta[p_{i}]}(k+\Lambda_{\eta[p_{i}]}(k)m,h+\Lambda_{\eta[p_{i}]}(h)m)=P_{\eta[p_{i}]}(k,h)$.

$(j+\Lambda_{\eta[p_{i}]}(j)m)^{u}\equiv j^{u}\mod N$ by Theorem 4. This means
that the residues for all exponents are the same for bases $k$ and
$k+\Lambda_{\eta[p_{i}]}(k)m$ and $h$ and $h+\Lambda_{\eta[p_{i}]}(h)m$. The
result follows after taking into account that when $p\nmid k^{u}-1$,
$\gamma_{p}(k)=0$ and if $k=1$, then $\Lambda_{N}(1)=0$.
Remark. Note that, for $gcd(k,h)=1$, no number $gcd(n,h)\neq 1$ and
$gcd(n,k)\neq 1$ will divide $k^{u}-h^{u}$, and thus every number that does
divide $k^{u}-h^{u}$ will obey Theorem 1 and Proposition 2.

###  1.2 Primitive Indexes in $k^{u}+h^{u}$

We operate under the condition that neither $k^{u}+h^{u}$ nor $k^{u}-h^{u}$
are equal to $0$ for all $u$.

######  Theorem 6.

For $N>2$, $N|k^{u}+h^{u}$ iff $P^{N}(k,h)|u$ and

$\dfrac{u}{P^{N}(k,h)}$,

is odd.

When $N|k^{P^{N}(k,h)}+h^{P^{N}(k,h)}$, we have

$k^{P^{N}(k,h)}+h^{P^{N}(k,h)}\equiv 0\mod N\Longleftrightarrow
k^{P^{N}(k,h)}\equiv-h^{P^{N}(k,h)}\mod N$.

Raising both $k$ and $h$ to the same odd multiple of $P^{N}(k,h)$ will
preserve this congruence, even multiples will not. In the other direction, for
all $y<P^{N}(k,h)$, we have $k^{y}\not\equiv h^{y}\mod N$. This is proven as
follows: we see that for all $N$ that divide some $k^{u}+h^{u}$,

$k^{P^{N}(k,h)}\equiv-h^{P^{N}(k,h)}\mod N\Longrightarrow
k^{2P^{N}(k,h)}\equiv h^{2P^{N}(k,h)}\mod N,$

and by Proposition 1, $P_{N}(k,h)|2P^{N}(k,h)$. But since $P_{N}(k,h)\nmid
P^{N}(k,h)$ for all $N>2$ by Proposition 1, for all such $N$ we know
$P_{N}(k,h)=2P^{N}(k,h)$ or $P_{N}(k,h)=2$. But if $P_{N}(k,h)=2$, then
because $k^{2}-h^{2}=(k-h)(k+h)$ and $N\nmid k-h$, $N|k+h$ and by definition
$P^{N}(k,h)=1$. In this case, it is still true that $2=2P^{N}(k,h)$. Thus, for
all $y<P^{N}(k,h)<P_{N}(k,h)$, we have

$k^{P^{N}(k,h)m+y}=k^{P^{N}(k,h)m}k^{y}\not\equiv-h^{P^{N}(k,h)m}h^{y}=-h^{P^{N}(k,h)m+y}\mod
N$,

for any positive integer $m$. For $N=2$, $N$ either divides every term or no
term.

######  Theorem 7.

$2P^{N}(k,h)=P_{N}(k,h)$, where $N=p^{a}$ and $p$ has an even primitive index
in $k^{u}-h^{u}$ and/or where $N>2$ divides some term in $k^{u}+h^{u}$.

We proved that for all $N$ which divide some $k^{u}+h^{u}$, the equality holds
in the theorem above in Theorem 6. In the other direction, for an _odd_ prime
power $p^{a}$ with an even primitive index in $k^{u}+h^{u}$,

$\displaystyle k^{P_{p^{a}}(k,h)}-h^{P_{p^{a}}(k,h)}$
$\displaystyle=(k^{\frac{P_{p^{a}}(k,h)}{2}}-h^{\frac{P_{p^{a}}(k,h)}{2}})(k^{\frac{P_{p^{a}}(k,h)}{2}}+h^{\frac{P_{p^{a}}(k,h)}{2}})$
$\displaystyle\equiv 0\mod p^{a},$

implies that
$p^{a}|(k^{\frac{P_{p^{a}}(k,h)}{2}}+h^{\frac{P_{p^{a}}(k,h)}{2}})$ since
$p\nmid(k^{\frac{P_{p^{a}}(k,h)}{2}}-h^{\frac{P_{p^{a}}(k,h)}{2}})$ by Theorem
1 and Proposition 1. This is because any odd $p^{a}$ with an even primitive
index we will have
$y=\frac{P_{p^{a}}(k,h)}{2}=p^{a-\gamma_{p^{a}}(k,h)}\frac{P_{p}(k,h)}{2}$ and
thus $P_{p}(k,h)\nmid y$. Additionally, no smaller exponent $u$ will allow
$k^{u}\equiv-h^{u}\mod{p^{a}}$ because then $p^{a}|k^{2u}-h^{2u}$ for
$2u<P_{p^{a}}(k)$ by the forward direction of this theorem proven in Theorem
6, contradicting Proposition 1. For all odd primes, $P_{p}(k,h)$ and
$P_{p^{a}}(k,h)$ are both either odd or even. Therefore, $P_{p}(k,h)$ being
even implies $P^{p^{a}}(k,h)=\frac{1}{2}P_{p^{a}}(k,h)$.

######  Theorem 8.

For odd $N=p_{1}^{a_{1}}p_{2}^{a_{2}}...$, iff each $P^{p_{i}^{a_{i}}}(k,h)$
is odd or the smallest primitive index in the $lcm$ is even and every other
primitive index in the $lcm$ is an odd multiple of it,

$P^{N}(k,h)=lcm[P^{p_{i}^{a_{i}}}(k,h)]$.

By Theorem 6 and the logic from Proposition 3, the result follows when
$P^{p_{i}^{a_{i}}}(k,h)$ is odd and/or for odd multiples of the smallest
primitive index. _For any other primitive indexes, there can never be a
multiple of them such that dividing by any one of them always yields an odd,
meaning $N\nmid k^{u}+h^{u}$ for any $u$ if the conditions specified in the
theorem are not met._
For odd $p$, $P^{p^{a}}(k,h)$ may be calculated as in Theorem 1, as shown by
Theorem 6.
We can finalize the discussion of lifting the exponent in [3] by deriving a
formula for $\nu_{2}(k^{n}+h^{n})$, as I have not found it discussed
elsewhere. Recall that $\nu_{2}(k^{n}+h^{n})$ refers to the highest power of
$2$ that divides $k^{n}+h^{n}$. Also note that $P_{2}(k,h)=P^{2}(k,h)=1$ if it
exists, and $2$ either divides every term in $k^{u}+h^{u}$ and $k^{u}-h^{u}$
or none.

######  Theorem 9.

Iff $2|k+h$,

$\nu_{2}(k^{n}+h^{n})=\begin{cases}\nu_{2}(k+h)&\text{if $n$ is odd;}\\\
1&\text{if $n$ is even.}\\\ \end{cases}$

If $2\nmid k+h$, then clearly $2$ divides no $k^{n}+h^{n}$. For
$\nu_{2}(k+h)=a$, we know $2^{a-x}\nmid k^{n}+h^{n}$ for even $n$ and $a-x>1$
by Theorem 6. Since if $2|k+h$, $2|k^{n}+h^{n}$, it must be true that
$\nu_{2}(k^{n}+h^{n})=1$ for even $n$. For odd $n$, we have that
$2^{a}|k^{n}+h^{n}$ by Theorem 6. If $2^{a+x}|k^{n}+h^{n}$, then the first
index it does this at yields
$P_{2^{a+x}}(k,h)=2P^{2^{a+x}}(k,h)=2(odd),odd\neq 1$ again by Theorem 7. But
since for any $y$, $P_{2^{y}}(k,h)$ is a power of $2$ by Theorem 1, this is a
contradiction.
By combining Theorem 8 and Theorem 9, one can easily see whether any even
number $N$ has a primitive index in $k^{u}+h^{u}$ and furthermore calculate
the primitive index if it does.

##  2 Connection to Primitive Roots

We know that the multiplicative group of integers modulo $n=2,4,p^{a},$ or
$2p^{a}$, $(\mathbb{Z}/n\mathbb{Z})^{\times}$, has
$|(\mathbb{Z}/n\mathbb{Z})^{\times}|=\phi(n)$. Its generators can be expressed
as ${k}$, where $O_{n}(k)=\phi(n)$. This means that

$\\{k^{0},k^{1},...,k^{\phi(n)-1}\\}$,

represents a reduced residue system modulo $n$. At least one $k$ yields this
iff $n=2,4,p^{a},$ or $2p^{a}$. This information is from [1].
Proposition 4. _For $0\leq u<\phi(n)$, $k^{u}\equiv h^{u}\mod n$ exactly $t$
times, where $P_{n}(k,h)t=\phi(n)$._
By Proposition 1, for $u<\phi(n)$, $k^{u}\equiv h^{u}\mod n$ exactly at
$u=0,P_{n}(k,h),2P_{n}(k,h),...,(t-1)P_{n}(k,h)$. The next equivalence is not
less than $\phi(n)$.
This proposition says that $P_{n}(k,h)=\phi(n)$ means both

$\\{k^{0},k^{1},...,k^{\phi(n)-1}\\}$,

and

$\\{h^{0},h^{1},...,h^{\phi(n)-1}\\}$,

are reduced residue systems modulo $N$ and furthermore that $k^{0}\equiv
h^{0}\mod n$ and every other equivalent power of $k$ and $h$ in the reduced
residue system are distinct modulo $n$.
Proposition 5. _If $k(h)^{\phi(n)-P_{n}(k,h)}$ is a generator of the reduced
residue system of $n$, then so are $k$, $h$, and $h(k)^{\phi(n)-P_{n}(k,h)}$._
First note that, by Proposition 4, $O_{n}(k)=O_{n}(h)=\phi(n)$, and both $h$
and $k$ are also generators of the reduced residue system. This means the
inverse of $a^{b}\mod n$ is $a^{\phi(n)-b}\mod n$. Therefore,

$k^{P_{n}(k,h)}-h^{P_{n}(k,h)}\equiv 0\mod n\Longleftrightarrow
h^{P_{n}(k,h)}(k^{P_{n}(k,h)})^{\phi(n)-P_{n}(k,h)}\equiv
k^{P_{n}(k,h)}(h^{P_{n}(k,h)})^{\phi(n)-P_{n}(k,h)}\equiv 1\mod n$.

Additionally, no exponent $u<P_{n}(k,h)$ will yield either equivalence. This
means that
$P_{n}(k,h)=O_{n}(k(h)^{\phi(n)-P_{n}(k,h)})=O_{n}(h(k)^{\phi(n)-P_{n}(k,h)})$.
Therefore, if $P_{n}(k,h)=\phi(n)$, then so do those two orders.

##  3 Cyclotomic Polynomials, Zsigmondy Numbers, and Primoverization

A homogenized cyclotomic polynomial is defined as follows:

$\Phi_{n}(k,h)=\dfrac{k^{n}-h^{n}}{\displaystyle\prod_{d|n}{\Phi_{d}(k,h)}}$.

Straightforwardly, the highest power of all nonprimitive factors of
$k^{n}-h^{n}$ that divide some $k^{d}-h^{d}$ for $d|n$ are divided out via
this definition.
Definition: Zsigmondy Numbers. A Zsigmondy number,

$\mathcal{Z}(n,k,h)$,

is the product of the primitive prime divisors of the term $k^{n}-h^{n}$. We
shall denote

$\zeta(n,k,h)$,

to be the product of the primitive prime divisors of the term $k^{n}+h^{n}$.
These are also termed Zsigmondy numbers.
One can see how Zsigmondy numbers and primitive indexes are closely related.
Without so much as invoking the properties of cyclotomic polynomials, we can
find Zsigmondy numbers explicitly.

######  Theorem 10.

For $n\neq 2$ and $gcd(k,h)=1$ and $z\in\mathbb{N},z\neq 0$,

$\mathcal{Z}(n,k,h)=\begin{cases}\Phi_{n}(k,h)&\text{if $n\neq
p^{z}(P_{p}(k,h))$;}\\\ \dfrac{\Phi_{n}(k,h)}{p}&\text{if
$n=p^{z}(P_{p}(k,h))$.}\\\ \end{cases}$

As noted above, the highest power of all nonprimitive factors of $k^{n}-h^{n}$
which divide some $k^{d}-h^{d}$ for $d|n$ are divided out via the definition
of $\Phi_{n}(k,h)$. This means the only nonprimitive prime factors of
$\Phi_{n}(k,h)$ are new multiplicities of previous prime factors introduced in
$k^{n}-h^{n}$. From Theorem 2, the new multiplicities of $N$ can only be
present at $n=N^{z}q$, where $N|k^{q}-h^{q}$. Additionally from the theorem,
the highest power of $N|\Phi_{n}(k,h)$, where $N$ is not primitive and $n>2$,
is $1$.
Lemma. _If $q\neq P_{N}(k,h)$, then $N\nmid\Phi_{n}(k,h)$._
Assume $q\neq P_{N}(k,h)$. By Proposition 1, $P_{N}(k,h)|q$. By Theorem 2, we
can see $P_{N^{a}}(k,h)=N^{a-\gamma_{N}(k,h)}P_{N}(k,h)|N^{z}q$. This would be
divided out.
Lemma. _If $N$ is composite, then $N\nmid\Phi_{n}(k,h)$._
Assume $N$ is composite. Since this must be a new multiplicity of $N$, we know
$P_{N}(k,h)<n$. By Property 1, we see that
$P_{N^{a}(f_{i})}(k,h)|P_{N^{a+1}}(k,h)=n$ for every proper factor $f_{i}$ of
$N$ and for $a+1$ the largest power of the chosen $f_{i}$ that divides
$k^{n}-h^{n}$. By Theorem 2 and because $n>2$, we have that
$P_{N^{a}(f_{i})}(k,h)<P_{N^{a+1}}(k,h)$, and thus $f_{i}\nmid\Phi_{n}(k,h)$.
All factors $f_{i}$ of $N$ would be divided out.
It is clear that $n=p^{z}P_{p}(k,h)$ if it possible that $p|\Phi_{n}(k,h)$ and
$p$ is not primitive ($p$ prime). By Theorem 2, the maximum power of $p$ that
divides $\Phi_{n}(k,h)$ is $1$. In the other direction, if
$n=p^{z}(P_{p}(k,h))$, then $n=P_{p^{a}}(k,h)$, where
$a=\nu_{p}(k^{n}-h^{n})$, by Theorem 2, and thus there must be exactly one
factor of $p$ that divides $\Phi_{p^{z}P_{p}(k,h)}(k,h)$ and is not primitive.
This reduces to

$\mathcal{Z}(n,k,1)=\begin{cases}\Phi_{n}(k)&\text{if $n\neq
p^{z}(O_{p}(k))$;}\\\ \dfrac{\Phi_{n}(k)}{p}&\text{if $n=p^{z}(O_{p}(k))$.}\\\
\end{cases}$

This definition is preferred because it allows one to classify certain classes
of numbers as Zsigmondy numbers without even calculating $\Phi_{n}(k,h)$.
Proposition 6. _For $n=2$,_

$\mathcal{Z}(2,k,h)=\dfrac{\Phi_{2}(k,h)}{2^{\nu_{2}(k^{2}-h^{2})}}$_._

This follows directly from Theorem 1 and the reasoning expressed in Theorem
10.
We have not only proved the forward condition that $n=p^{z}q$, but
additionally that $q=P_{p}(k,h)$ and the biconditionality of the statement. We
will now explore how this affects Shevelev’s exploration of overpseudoprimes.
From Shevelev [2, (2.4)], we see that all primes satisfy

$p=r_{k}(p)O_{p}(k)$,

for any base $k$, where $r_{k}(p)$ is the number of distinct cyclotomic cosets
of $k$ modulo $p$. A composite number is termed _overpseudoprime_ base $k$ if
$n=r_{k}(n)O_{n}(k)$.
Definition: Primover. A number $n$ is said to be primover base $k$ if it is
either a composite overpseudoprime base $k$ or prime.
From Shevelev [2, Th. 12], a necessary and sufficient condition for $n$ to be
primover is as follows:
Lemma. _If $gcd(n,b)=1$, then $n$ is primover iff $O_{n}(k)=O_{d}(k)$ for each
divisor $d>1$ of $n$._
In his paper [2, Th. 16, Th. 17], he details how every composite
overpseudoprime base $k$ is a strong pseudoprime and superpseudoprime to the
same base. We strengthen and expand upon some of the theorems found in [2],
making them biconditional and removing the condition ”if $p$ does not divide
$\Phi_{n}(k)$” (if $gcd(p,\Phi_{n}(k))=1$). We also introduce new examples of
primover numbers evident from Theorem 10. Note that all Zsigmondy numbers in
the sequence $k^{u}-1$ are primover due to the above lemma.
Proposition 7. _Generalized repunits,_

$\mathcal{Z}(n,k,1)=\dfrac{k^{n}-1}{k-1}$_,_

_are primover base $2$ iff $n$ is prime._
Proposition 8. _Numbers of the form_

$\mathcal{Z}(pq,k,1)=\dfrac{(k-1)(k^{pq}-1)}{(k^{p}-1)(k^{q}-1)},$__

_are primover base $k$. This identity holds iff both $p$ and $q$ are distinct
primes, where $p\neq O_{q}(k)$ and $q\neq O_{p}(k)$._
Proposition 9. _Numbers of the form_

$\mathcal{Z}(pO_{p}(k),k,1)=\dfrac{(k-1)(k^{pO_{p}(k)}-1)}{p(k^{p}-1)(k^{O_{p}(k)}-1)}$__

_are primover base $k$ iff $p$ is prime and $O_{p}(k)$ is prime._
Proposition 10. _Numbers of the form_

$\mathcal{Z}(n^{a},k,1)=\dfrac{k^{n^{a}}-1}{k^{n^{a-1}}-1}$_,_

_are primover base $k$ iff $n$ is prime._
We further the study of Zsigmondy by inspecting $k^{u}+h^{u}$. We introduce an
important theorem regarding the relationship between $k^{u}+h^{u}$ and
$k^{u}-h^{u}$.

######  Theorem 11.

For $n>1$ and/or $k+h$ odd,

$\zeta({n},k,h)=\mathcal{Z}({2n},k,h)$.

From Theorem 7, if an odd $p$ divides some $k^{u}+h^{u}$, then
$P_{p^{a}}(k,h)=2P^{p^{a}}(k,h)$. If an odd $p$ has an even primitive index in
$k^{u}-h^{u}$, then by Theorem 7, $P_{p^{a}}(k,h)=2P^{p^{a}}(k,h)$. By the
definition of primitive prime divisors, the result follows when $n>1$, since
$P_{2}(k,h)=P^{2}(k,h)=1$. If $k+h$ is odd then so will every term be, and
$\zeta(1,k,h)=\mathcal{Z}(1,k,h)$. If not, then since
$P_{2}(k,h)=P^{2}(k,h)=1$, $2^{a-b}\zeta(1,k,h)=\mathcal{Z}(1,k,h)$, where $a$
is the highest power of $2$ that divides $k-h$ and $b$ is the highest power of
$2$ that divides $k+h$. Thus, all $\zeta(n,k,1)$ are primover base $k$ for
$n>1$ and/or $k+h$ odd. For $n=1$ and $k+1$ even, $\zeta(1,k,1)$ is primover
iff $a>b$.
Corollary. _The only odd $N$ that divide some $k^{u}+h^{u}$ are those that are
made up entirely of primes with even primitive indexes in $k^{u}-h^{u}$ and
that satisfy the conditions specified in Theorem 8._
Corollary. _For $k+u$ even, the only even $2^{a}N$, $N$ odd, that divide some
$k^{u}+h^{u}$ are those where $N$ obeys the above corollary and
$a=\nu_{2}(k+h)$ if $P^{N}(k,h)$ is odd and $a=1$ if $P^{N}(k,h)$ is even._
This is proven via Theorem 9.
Proposition 11. _All Wagstaff numbers with prime exponents,_

$\zeta(p,2,1)=\dfrac{2^{p}+1}{3}$_,_

_are primover base $2$._

## References

  * [1] Byrkit, D. R., Pettofrezzo, A. J. (1970). _Elements of Number Theory_ , Englewood Cliffs: Prentice Hall, LCCN 71081766.
  * [2] Castillo, J. H., García-Pulgarín, G., Shevelev, V., Velásquez-Soto, J. M. (2012, June 4). _Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers_. Retrieved from arXiv:1206.0606 [math.NT].
  * [3] Parvardi, A. H. (2011, February 28). _Lifting The Exponent Lemma (LTE)._ Retrieved from https://artofproblemsolving.com/.


11institutetext: TNO, 2597 AK The Hague, The Netherlands

# Affordance Perception by a Knowledge-Guided Vision-Language Model with
Efficient Error Correction††thanks: Supported by TNO ERP APPL.AI program.

G.J. Burghouts  M. Schaaphok  M. van Bekkum  W. Meijer  F. Hillerström  J. van
Mil

###### Abstract

Mobile robot platforms will increasingly be tasked with activities that
involve grasping and manipulating objects in open world environments.
Affordance understanding provides a robot with means to realise its goals and
execute its tasks, e.g. to achieve autonomous navigation in unknown buildings
where it has to find doors and ways to open these. In order to get actionable
suggestions, robots need to be able to distinguish subtle differences between
objects, as they may result in different action sequences: doorknobs require
grasp and twist, while handlebars require grasp and push. In this paper, we
improve affordance perception for a robot in an open-world setting. Our
contribution is threefold: (1) We provide an affordance representation with
precise, actionable affordances; (2) We connect this knowledge base to a
foundational vision-language models (VLM) and prompt the VLM for a wider
variety of new and unseen objects; (3) We apply a human-in-the-loop for
corrections on the output of the VLM. The mix of affordance representation,
image detection and a human-in-the-loop is effective for a robot to search for
objects to achieve its goals. We have demonstrated this in a scenario of
finding various doors and the many different ways to open them.

###### Keywords:

Open World Robotics Perception Affordance Vision-language model Knowledge.

##  1 Introduction

Mobile robot platforms will increasingly be tasked with activities that
involve grasping and manipulating objects in open world environments in order
to reach a goal [35]. Interacting in such an open world poses challenges for a
robot. In order to pursue its goal, the robot needs to take advantage of the
actionable possibilities of objects that it encounters, e.g. lift it to get it
out of the way, open it to see what is inside, etc. In contrast to a closed
world or rigidly structured environment, in an open world the robot needs to
be able to adapt to unforeseen events and interact with unknown objects [4].
Effective interaction with objects is based on the perception of their
affordances [10, 3], what the object offers or provides to an user [11]. A
button on a door affords pushing, while a handle may also afford pushing [26].
Understanding of affordance allows reasoning about object uses: what
possibilities for interaction does the object offer and how can an object be
handled and put to use? Understanding affordance comes from the combination of
perception and prior knowledge of the world [11]. Perception provides clues
about possible affordances: what object does the robot see, what properties
does it have and what does the object seemingly allow? Combined with prior
knowledge this leads to affordance understanding. Potential actions can then
be deduced from models that describe how a robot may make use of some property
(take action) based on those perceived affordances [3, 4]. However, such
models do not scale well, because a lot of manual engineering is required to
extend them with new object classes and with new contexts for existing object
classes.

In order to generate actionable suggestions, the robot needs to distinguish
subtle differences between objects, as they may result in different action
sequences: doorknobs require grasp and turn, while door handles require grasp
and push. Sources that provide this knowledge about actions may include
explicitly structured (semantic) knowledge bases [31] or e.g. foundational
language models like ChatGPT [28]. Approaches that rely on explicit semantic
affordance-action models are precise [3, 4]: when one determines an
affordance, one can deduce an associated action. This makes for actionable
affordances, i.e. affordances with perceivable action possibilities. Similar
to explicit knowledge models for perception however, this requires manual
engineering and does not scale well. On the other hand, foundational language
models scale well and embed a wealth of fine-grained knowledge. They can
provide precise information on object affordances, as is demonstrated by
ChatGPT when prompted with “Give me a visual description of a door handle and
a door knob and give a step-by-step action list on how to open a door”. The
ChatGPT-generated text clearly outlined their visual properties and the steps
for using both: “grasp and push or pull” for door handles and “grasp and
twist” for door knobs [27].

Surprisingly, we discover in this paper that foundational vision-language
models (VLMs) do not exhibit the same fine-grained distinctions as the
language models. VLMs such as GLIP [19, 37] are very flexible and are
therefore promising also for affordance perception. They embed knowledge about
a wide variety of objects and allow open vocabulary object prompting, which
makes their use scalable for new objects and new contexts. However, we find
that VLMs models lack the necessary fine-grained semantic differences between
objects, such as a doorknob vs. a handlebar, where each requires a different
action. This lack of discrimination, makes it difficult to deduce the right
action for the robot. To enable the required fine-grained perception, the VLM
needs to be fine-tuned. This should require little additional annotations and
retraining, because the robot needs to be deployed again quickly to continue
its task. We propose a solution by correcting the VLM efficiently for confused
objects by a human-in-the-loop.

In this paper, we bring together knowledge representation and foundation
models, to achieve a best of both worlds, complemented with a human-in-the-
loop that refines missing knowledge. We improve affordance understanding in an
open-world setting for a robot whose training and world model includes some,
but does not have complete world knowledge. Our contribution is threefold: (1)
We provide an affordance representation in a knowledge base that represents
precise, actionable affordances for a limited set of relevant objects; (2) We
connect this knowledge base to a VLM and prompt it for a wider variety of new
and unseen objects similar to those in the knowledge base; (3) We apply a
human-in-the-loop to correct the VLM where its finegrained discrimination is
lacking.

##  2 Related Work

###  2.1 Affordance modelling

There are multiple proposed formalisations of affordances for robotics [38]
[22] [9], all relating to some extent objects, actions and effects to an agent
and its action capability. Functional representation of affordances should
have the ability for recognition, cognitive and conceptual understanding, how
to use and operate an object, invention of new objects/tools for a function
[16]. Features/characteristics of objects can be taken into account when
detecting affordances, but background knowledge is required [24], while
affordances may be hidden from current perspective [24]. The most common used
formalization of affordances is that a potential action exists that could
generate the effect, if applied to a specific object in the environment. A
single interaction will then produce an instance of this triplet (object,
action, effect). The surveys by [2], [36], [3], [24] provide overviews of the
work on affordances for robotics. Affordances can be used for different
purposes, such as planning when one knows the desired effects and the objects
and one needs to predict the action or for effect prediction when one knows
both the object and the action [12]. A practical approach for affordances in
robotics focuses on affordance templating[15], [14] for more complex
manipulation tasks, but this can only handle situation envisioned at design
time. Other approaches include deep learning [8], reinforcement learning and
value functions [1] [12].

###  2.2 Affordance Perception

Most of the affordance perception research, focuses on task-driven object
detection [20, 30, 32], i.e., finding objects that can cut the tape around a
closed box. A context-based Gated Graph Neural Network uses the detected
objects in an image and selects the ones that are suitable for a task, given
the appearance of an object and the global context of all objects in the scene
[30]. The category-based approach TOIST extracts the objects from a language
description of the task [20]. The methods in [20, 30] leveraged only a limited
amount of external knowledge. Therefore, a recent trend is to use large
language models (LLMs) to extend the knowledge by a huge amount. In [34] a
joint language and vision model was used for object detection. They modeled
the detection via language embeddings from Wiktionary object descriptions. The
state-of-the-art for affordance perception is the end-to-end learning approach
presented in [32]. The approach uses a LLM with chain of thought (CoT) for
extracting knowledge about which objects and properties can afford to solve a
task. The extracted objects and properties are used to fine-tune an object
detection model. This knowledge-conditioned model learns to both detect
objects and to recognize visual attributes that provide affordances, e.g., a
sharp object can cut. Instead of a comprehensive learning scheme during
preparation, our goal is to be flexible in an open world, with new tasks that
involve new objects. Therefore, instead of pre-learning for affordance
perception, we focus on efficient learning on the job.

###  2.3 Open-Vocabulary Object Detection

For open world robotics, it is key to have open-vocabulary perception models.
In computer vision, such methods have rapidly advanced since CLIP [29]. Here
it was shown that contrastive pretraining on a massive number of noisy image-
text pairs can result in models with impressive zero-shot generalization
capabilities. CLIP is able to classify images, where we are interested in
localizing objects in images, a task known as object detection. For object
detection, ViLD [13] and OWL-ViT [25] extended CLIP with localization
capabilities. GLIP [19] and GLIPv2 [37] followed a different strategy and
proposed an architecture and pretraining strategy specifically designed for
object detection. Recently GLIPv2 set a new state of the art performance on
MS-COCO [21] for zero-shot tasks, i.e. unseen objects. GLIPv2 performs well at
detecting almost any everyday object, therefore we take GLIP as a starting
point. To search for the right objects that can provide specific affordances
to solve the task at hand (e.g. opening a door via a push bar), we leverage a
knowledge base that captures information about affordances and objects. Such
knowledge feeds into the model via task-specific textual prompts. Inspired by
[7, 6], we improve the discrimination by validating known spatial relations
between the objects in a scene. One problem with GLIPv2 and similar recent
models is their struggle with fine-grained or less common objects or
viewpoints [5]. We improve the model’s ability to distinguish fine-grained
objects by efficient learning on the job.

##  3 Method

###  3.1 Architecture

We propose a modular system as shown in 1, consisting of (a) a knowledge base
in TypeDB [33] for affordance representation, (b) a neuro-symbolic program in
Scallop [17] for logical constraints, (c) a GLIP module for localizing objects
and (d) a human-in-the-loop for label refinement.

The knowledge base provides labels for relevant object classes to the object
detection module, the neuro-symbolic program provides (spatial) constraints on
localization of objects and the human-in-the-loop will provide label
refinement and correction on identified objects. The output of the object
detection is a set of actionable object labels.

Figure 1: Affordance detection architecture

###  3.2 Affordance representation

To find objects that offer the desired affordance to reach the specified goal,
a proper representation of affordances is required. We present a
representation of affordances using three relations: the effect relation, the
affordance relation and the action relation. The effect relation connects a
property to an object. The affordance relation connects an action to an effect
and the action relation relates to a direct object. Figure 2 shows an example
of this representation, where the effect is a relation between the object
‘door’ and the property ‘accessibility’, the affordance is the relation
between the action ‘push down’ and the effect and the action relation ‘push
down’ is related to the direct object ‘handle’.

Figure 2: Basic affordance representation using three relations, effect
relation, affordance relation and action relation

We designed this representation to provide more flexibility in modelling
complex affordances and to achieve more flexible, actionable instructions. The
representation allows us to (1) explicitly model whether action and effect are
on the same or on different objects, (2) represent more detailed and complex
affordance structures, including indirect object and other agents (see Figure
3). The model structure also allows for (3) different affordances leading to
the same effect, which supports quick identification of different affordances,
(4) one action to have multiple effects, where it can distinguish between (a)
both effects happening jointly or (b) one of the effects taking place.
Finally, we can model (5) effects as a verb (e.g. the effect is that person A
“holds” a cup), (6) probabilities of an effect taking place, (7) chains of
actions to obtain the desired effect (where the “action” relation is replaced
by an “action chain” relation). The affordance representations are modelled in
a TypeDB knowledge graph. Manually engineering these graphs would be too
labour-intensive and inefficient. We can however create baseline versions of
these graphs by semi-automated generation (and then manual curation) based on
common-sense knowledge available in LLMs ([18]). In order to avoid scalability
problems and inference perfomance issues, we envision creating domain- and/or
use-case-specific models (e.g. office environment, industrial site, etc.).

Figure 3: Affordance representation, where the robot SPOT gives a cup to
another person, with the effect that this person holds the cup.

###  3.3 Localizing Objects with Affordances

The goal is to find objects that offer the desired affordance. For instance,
if the robot is tasked to open a door, to localize a push bar or handle in an
image. There can be multiple means to open doors, e.g. a push bar, a handle, a
knob, a button. The set of relevant objects $\\{\,l_{0},l_{1},...,l_{n}\,\\}$
is taken from a knowledge base, as proposed in [7]. To localize these objects
in image, we prompt the GLIP model [19] in the string format as proposed in
[19, 37]:

$\texttt{<}l_{0}\texttt{>. }\texttt{<}l_{1}\texttt{>.
}\cdots\texttt{<}l_{n}\texttt{>}$ (1)

In accordance with [5], the model is not able to distinguish between fine-
grained object labels. In Figure 4, results are shown for three different
scenes with various door and openers. for example, the door handle is
mislabeled as a knob. For a robot, this mistake is crucial, because it will
select the wrong action to open it. A knob should be turned, whereas the
handle should be pushed downwards. There are many false positives too,
respectively the handrail is mistaken for a push bar, the window on the side
is mistaken for a knob, and the window frame in the background is mistaken for
a door handle.

Figure 4: Standard GLIP is incapable of fine-grained discrimination of various
door openers.

###  3.4 Finegrained Discrimination by Sparse Human Feedback

When using an open-vocabulary detection model, our objective is to increase
the model’s discrimination between fine-grained objects. Given that most of
the relevant objects can be detected (see Figure 4), the recall is promising
already. The problem is mostly in the classification of the objects, i.e. the
labels assigned to them (e.g. a handle that is labeled as a knob). To improve
the label assignment, our proposal is to involve a human in the process, to
reassign labels in an efficient manner. In our scenario, the robot is tasked
to navigate through an unknown building. During a first run, it is able to
find the relevant objects (recall), but with wrong labels assigned to them.
Detected objects are visualized and grouped on a 2D canvas to create an
overview, where the human can quickly identify the classes of objects and
label a few characteristic instances of each class. In our approach, each
object is represented by a feature vector by a visual encoder, we have used
CLIP [29]. The objects can now be distributed on the 2D canvas by a
dimensionality reduction, we have used t-SNE [23]. This canvas enables the
human to quickly assign labels to the encountered object classes.

Figure 5: In the overview of all detected objects, the main classes can be
identified quickly, as shown by the new labels that were assigned to them by a
user.

Being provided with a few labels, a task-specific model can now be deployed
for the task and environment at hand. For simplicity we leverage a nearest
neighbor model, on top of the VLM, to relabel the outputs of the VLM. More
specifically, only the labels and confidences are changed by this second
model; the boxes remain unchanged. The relabelling model is constructed as
follows. The $N$ labels are defined as $D=\\{(x_{i},y_{i})\\}_{i\in 1..N}$,
where $x_{i}$ denotes the feature vector of object $i$ and $y_{i}$ is the
provided label for object $i$. An object seen during testing is encoded by
feature vector $x_{j}^{test}$. It gets a label assigned, $y_{j}^{test}$, with
a confidence value $c_{j}^{test}$. The confidence value $c$ is important for
the robot’s planning, because it can go to the most confident object first.
The assignment of label $y$ and confidence $c$ is inferred the minimal cosine
distance to labeled objects:

$c(x_{j}^{test},x_{i})=\frac{x_{j}^{test}\cdot x_{i}}{\lVert
x_{j}^{test}\rVert\cdot\lVert x_{i}\rVert}$ (2)

$y_{j}^{test}=\operatorname*{arg\,max}_{y_{i}}\,c(x_{j}^{test},x_{i}),\,\,\,(x_{i},y_{i})\in
D$ (3)

###  3.5 Refining Objects by Spatial Reasoning

As can be seen from Figure 4, there are many false positives when using GLIP.
The precision of affordance objects can be enhanced by verifying known spatial
relations. For instance, the opener of a door is typically nearby the door. We
follow the approach from [7]. A neuro-symbolic program [17] takes the often
uncertain objects and their labels and confidences
$\\{(y_{j}^{test},c_{j}^{test})\\}_{j\in 1..M}$ and verifies spatial relations
that are predefined by the user before the robot starts the mission. The
neuro-symbolic program takes the spatial relations in the form of first-order
logic:

$\begin{split}\exists\,\,d,o:&\,\,object(d,door)\land
object(o,opener)\,\,\land\\\
&\,\,correct\texttt{-}range\texttt{-}hor(d,o)\,\,\land\\\
&\,\,correct\texttt{-}range\texttt{-}vert(d,o)\end{split}$ (4)

This specifies that a door opener $o$ is expected to be close to the
horizontal side of the door $d$ and vertically close to the middle of the door
$d$:

$correct\texttt{-}range\texttt{-}hor(d,o)=max(1-\frac{hor\texttt{-}dist\texttt{-}from\texttt{-}side(o,d)}{width(d)},\,0)$
(5)

$correct\texttt{-}range\texttt{-}vert(d,o)=max(1-\frac{vert\texttt{-}dist\texttt{-}from\texttt{-}middle(o,d)}{height(d)},\,0)$
(6)

The spatial reasoning approach can be a solution for classes of object
affordances if the specification expressed in first-order logic can be a
fairly accurate representation of real world conditions. In case there is a
higher degree of uncertainty in spatial relations, the approach may be less
effective and other formalisms (e.g. possibilistic logic) may yield better
results.

##  4 Experiment

###  4.1 Setup and Dataset

For experimentation, we consider the scenario where a robot navigates through
an office building, and the robot needs to localize the openers such that it
can open doors to move through them. In order to test the validity of our
approach, we have conducted a limited experiment in a single environment.
Videos of three different scenes with various doors and openers were collected
for training, comprising 1553 frames. Only 3 frames were labeled by a human
user. These frames result from the human feedback as shown in Figure 5. This
resulted in 3 labeled doors, 2 labeled door handles, 1 labeled push bar and 1
labeled button. For testing, another video was recorded with similar doors and
openers, but under different circumstances such as changed viewpoint and
camera distance. This yielded 1370 test frames.

###  4.2 Visualization

We already established that GLIP’s object predictions are not actionable due
to many wrong labels and false positives (see Figure 4). With our relabeling
method from Section 3.4, the predictions improve significantly. Figure 6 shows
the improved results. In the top row, it shows that the handle was initially
labeled as a knob, but it is corrected, and now labeled as a handle. This
enables a robot to select the correct action (push down) instead of the wrong
action (rotate). In the bottom row, a similar improvement is observed, for
relabeling a knob (error) to a handle (correct). In the middle row, the button
was corrected from knob to button, and the false positive (push bar) is
removed. Most improvement is due to the relabeling method, whereas the spatial
reasoning adds minor improvements. For instance, in the middle row, a false
positive (handle) is removed, because its spatial relation to the door is not
conforming to the expectation (Equation 4). A demo clip of our method’s
predictions on the full test recordings can be found online.

Figure 6: Our relabeling method yields actionable labels.

###  4.3 Performance Evaluation

A quantitative analysis shows that the performance is indeed improved
significantly. The metric for object detection is mAP which measures both the
localization and classification accuracy. For the localization, a predicted
object should have an overlap with the ground truth of at least IoU $\geq$
0.5, where IoU is the intersection over union. From the 1370 test frames, 11
images were labeled for validation. The predictions of GLIP are not
actionable, as can be observed in Figure 7 from the low scores for the green
bars (left bar in each group), for the door openers, i.e. the handle (almost
zero), push bar and button. All scores are below 0.15, which means that less
than 1 out of 7 predicted objects is correct. For application in robotics,
this is insufficient because the robot would make mostly mistakes while it
operates. The performance of our relabeling method is indicated in blue
(middle bar in each group). The scores are much higher, showing its
effectiveness for finding objects that are related to the affordances of
interest. The spatial reasoner is effective for the push bar (orange bar). For
this class, GLIP produced many false positives in the background, as there are
many elongated shapes that have some resemblance with a push bar. These false
positives do not conform to expected spatial relations, i.e. being close to
the door. For the other door openers, the spatial reasoning does not impact
the predictions much.

Figure 7: For the localization and classification of affordance objects, the
performance of GLIP (green bars) is increased significantly by our method
(blue and orange bars).

##  5 Conclusion

We have investigated the possibility of affordance analysis by a robot without
closed-world assumptions: its training and world model does not include
complete world knowledge. Affordances, objects and actions can be precisely
modeled in a relational model. A future option could be to automatically
extract those from a knowledge base or LLM. Objects from these relations can
be visually localized with a VLM. Label assignment quality varies but is
overall semantically imprecise (false positives include mix-ups of handrails
and push bars) and not actionable (e.g. knob is identified as a handle).
Furthermore, detection provides a good starting point for determination of
relevant objects in terms of affordances: the recall is good but precision
needs improvement. An effective way to determine actionable labels and improve
the model, is involvement of sparse feedback from a human who labels
characteristic objects from a 2D plot. This drastically improves the mAP
(combination of precision and recall for localization and labels) with only a
few labels. Our current, limited experiment is a first step towards a more
elaborate investigation of our approach in a diverse set of environments and a
more open-world setting.

## References

  * [1] Ahn, M., Brohan, A., Brown, N., Chebotar, Y., Cortes, O., David, B., Finn, C., Gopalakrishnan, K., Hausman, K., Herzog, A., Ho, D., Hsu, J., Ibarz, J., Ichter, B., Irpan, A., Jang, E., Ruano, R., Jeffrey, K., Jesmonth, S., Yan, M.: Do as i can, not as i say: Grounding language in robotic affordances. Conference on Robotic Learning (04 2022)
  * [2] Ardon, P., Pairet, E., Lohan, K.S., Ramamoorthy, S., Petrick, R.: Affordances in robotic tasks – a survey. arXiv:2004.07400 [cs] (2022)
  * [3] Ardon, P., Pairet, E., Lohan, K.S., Ramamoorthy, S., Petrick, R.P.: Building affordance relations for robotic agents - a review. Proceedings of the Thirtieth Joint Conference on Artificial Intelligence IJCAI-21 - Survey track (2021)
  * [4] Beßler, D., Porzel, R., Pomarlan, M., Beetz, M., Malaka, R., Bateman, J.: A formal model of affordances for flexible robotic task execution. Frontiers in Artificial Intelligence and Applications 325, 2425–2432 (2020). https://doi.org/10.3233/FAIA200374
  * [5] Bugliarello, E., Sartran, L., Agrawal, A., Hendricks, L.A., Nematzadeh, A.: Measuring progress in fine-grained vision-and-language understanding (2023)
  * [6] Burghouts, G.J., Hillerström, F., Walraven, E., van Bekkum, M., Ruis, F., Sijs, J.: Anomaly detection in an open world by a neuro-symbolic program on zero-shot symbols. In: IROS 2022 Workshop Probabilistic Robotics in the Age of Deep Learning (2022)
  * [7] Burghouts, G.J., Meijer, W., Hillerström, F., van Mil, J., van Bekkum, M., Schaaphok, M., Ruis, F.: Improved zero-shot object localization using contextualized prompts and objects in context. In: ICRA2023 Workshop on Pretraining for Robotics (PT4R) (2023)
  * [8] Chen, D., Kong, D., Li, J., Wang, S., Yin, B.: A survey of visual affordance recognition based on deep learning. IEEE Transactions on Big Data 9(6), 1458–1476 (2023). https://doi.org/10.1109/TBDATA.2023.3291558
  * [9] Francisco Cruz, Sven Magg, C.W., Wermter., S.: Training agents with interactive reinforcement learning and contextual affordances. IEEE Transactions on Cognitive and Developmental Systems 8, 271–284 (2016)
  * [10] Gaver, W.W.: Technology affordances. Conference on Human Factors in Computing Systems - Proceedings pp. 79–84 (1991). https://doi.org/10.1145/108844.108856
  * [11] Gibson, J.J.: The Ecological Approach to Visual Perception. Psychology Press Classic Editions (1979)
  * [12] Graves, D., Günther, J., Luo, J.: Affordance as general value function: a computational model. Adaptive Behavior 4, 307–327 (2022)
  * [13] Gu, X., Lin, T.Y., Kuo, W., Cui, Y.: Open-vocabulary detection via vision and language knowledge distillation. arXiv preprint arXiv:2104.13921 (2021)
  * [14] Hart, S., Quispe, A.H., Lanighan, M.W., Gee, S.: Generalized affordance templates for mobile manipulation. 2022 International Conference on Robotics and Automation (ICRA) pp. 6240–6246 (2022)
  * [15] Hart, S., Dinh, P., Hambuchen, K.: The affordance template ros package for robot task programming. In: 2015 IEEE International Conference on Robotics and Automation (ICRA). pp. 6227–6234 (2015). https://doi.org/10.1109/ICRA.2015.7140073
  * [16] Ho, S.B.: A general framework for the representation of function and affordance: A cognitive, causal, and grounded approach, and a step toward agi (2022)
  * [17] Huang, J., Li, Z., Chen, B., Samel, K., Naik, M., Song, L., Si, X.: Scallop: From probabilistic deductive databases to scalable differentiable reasoning. In: Advances in Neural Information Processing Systems. vol. 34, pp. 25134–25145 (2021)
  * [18] Kommineni, V.K., König-Ries, B., Samuel, S.: From human experts to machines: An llm supported approach to ontology and knowledge graph construction (2024)
  * [19] Li*, L.H., Zhang*, P., Zhang*, H., Yang, J., Li, C., Zhong, Y., Wang, L., Yuan, L., Zhang, L., Hwang, J.N., Chang, K.W., Gao, J.: Grounded language-image pre-training. In: CVPR (2022)
  * [20] Li, P., Tian, B., Shi, Y., Chen, X., Zhao, H., Zhou, G., Zhang, Y.Q.: Toist: Task oriented instance segmentation transformer with noun-pronoun distillation. Advances in Neural Information Processing Systems 35, 17597–17611 (2022)
  * [21] Lin, T.Y., Maire, M., Belongie, S., Hays, J., Perona, P., Ramanan, D., Dollár, P., Zitnick, C.L.: Microsoft coco: Common objects in context. In: Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13. pp. 740–755. Springer (2014)
  * [22] Luis Montesano, Manuel Lopes, A.B., Santos-Victor., J.: Modeling affordances using bayesian networks. IEEE/RSJ International Conference on Intelligent Robots and Systems pp. 4102–4107 (2007)
  * [23] Van der Maaten, L., Hinton, G.: Visualizing data using t-sne. Journal of machine learning research 9(11) (2008)
  * [24] Min, H., Yi, C., Luo, R., Zhu, J., Bi, S.: Affordance research in developmental robotics: A survey. IEEE Transactions on Cognitive and Developmental Systems 8(4), 237–255 (2016). https://doi.org/10.1109/TCDS.2016.2614992
  * [25] Minderer, M., Gritsenko, A., Stone, A., Neumann, M., Weissenborn, D., Dosovitskiy, A., Mahendran, A., Arnab, A., Dehghani, M., Shen, Z., Wang, X., Zhai, X., Kipf, T., Houlsby, N.: Simple open-vocabulary object detection with vision transformers. arXiv preprint arXiv:2205.06230 (2022)
  * [26] Norman, D.A.: The Design of Everyday Things. Basic Books, New York, 2 edn. (2013)
  * [27] OpenAI: ChatGPT (2023), accessed: 2023-04-21
  * [28] OpenAI: Gpt-4 technical report (2023)
  * [29] Radford, A., Kim, J.W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., Krueger, G., Sutskever, I.: Learning transferable visual models from natural language supervision. In: ICML (2021)
  * [30] Sawatzky, J., Souri, Y., Grund, C., Gall, J.: What object should i use?-task driven object detection. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 7605–7614 (2019)
  * [31] Speer, R., Havasi, C.: Representing general relational knowledge in concept net 5. Proceedings of the 8th International Conference on Language Resources and Evaluation, LREC 2012 pp. 3679–3686 (2012)
  * [32] Tang, J., Zheng, G., Yu, J., Yang, S.: Cotdet: Affordance knowledge prompting for task driven object detection. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 3068–3078 (2023)
  * [33] Vaticle: The polymorphic database powered by types (2023), https://typedb.com/
  * [34] Vo, D.M., Chen, H., Sugimoto, A., Nakayama, H.: Noc-rek: novel object captioning with retrieved vocabulary from external knowledge. In: 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). pp. 17979–17987. IEEE (2022)
  * [35] Yamanobe, N., Wan, W., Ramirez-Alpizar, I.G., Petit, D., Tsuji, T., Akizuki, S., Hashimoto, M., Nagata, K., Harada, K.: A brief review of affordance in robotic manipulation research. Advanced Robotics 31(19-20), 1086–1101 (2017). https://doi.org/10.1080/01691864.2017.1394912
  * [36] Zech, P., Haller, S., Lakani, S.R., Ridge, B., Ugur, E., Piater, J.: Computational models of affordance in robotics: a taxonomy and systematic classification. Adaptive Behavior 25(5), 235–271 (2017). https://doi.org/10.1177/1059712317726357, https://doi.org/10.1177/1059712317726357
  * [37] Zhang, H., Zhang, P., Hu, X., Chen, Y.C., Li, L.H., Dai, X., Wang, L., Yuan, L., Hwang, J.N., Gao, J.: Glipv2: Unifying localization and vision-language understanding (2022)
  * [38] Şahin, E., Çakmak, M., Doğar, M.R., Uğur, E., Üçoluk, G.: To afford or not to afford: A new formalization of affordances toward affordance-based robot control. Adaptive Behavior (2007). https://doi.org/10.1177/1059712307084689


logic, but these two approaches have developed through very different pathways
on the road to being incorporated in modern-day programming languages. In this
work, we have developed a core calculus that captures many of the key concepts
for ownership tracking in a graded setting, connecting these fine-grained
substructural notions with prior work on simpler systems such as linear and
uniqueness types which sit closer to the theory. This has allowed us to not
only better understand the relationship between these disparate approaches to
resourceful reasoning but also to examine how they interact.

By developing a framework through which both ownership properties and precise
grades for reasoning about data can be tracked within the setting of the
Granule language, we demonstrate that careful management of both resource and
memory usage are not only compatible but complementary in a functional
context. This paper represents a piece of two larger puzzles—one aiming to
develop an in-depth theoretical understanding of Rust’s comprehensive approach
to memory management, and one aiming to expand the range of properties about
programs that can be represented explicitly through graded types—and we look
forward to seeing more ideas being shared (or, indeed, borrowed) across the
boundary between these two closely related worlds in the future.

## References

  * (1)
  * Abel and Bernardy (2020) Andreas Abel and Jean-Philippe Bernardy. 2020.  A Unified View of Modalities in Type Systems.  _Proc. ACM Program. Lang._ 4, ICFP (2020), 90:1–90:28.  https://doi.org/10.1145/3408972
  * Almeida (1997) Paulo Sérgio Almeida. 1997.  Balloon Types: Controlling Sharing of State in Data Types. In _ECOOP’97—Object-Oriented Programming: 11th European Conference Jyväskylä, Finland, June 9–13, 1997 Proceedings 11_. Springer, 32–59.
  * Atkey (2018) Robert Atkey. 2018.  Syntax and Semantics of Quantitative Type Theory. In _Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science_. 56–65.
  * Balabonski et al. (2016) Thibaut Balabonski, François Pottier, and Jonathan Protzenko. 2016.  The Design and Formalization of Mezzo, a Permission-Based Programming Language.  _ACM Trans. Program. Lang. Syst._ 38, 4, Article 14 (aug 2016), 94 pages.  https://doi.org/10.1145/2837022
  * Barendsen and Smetsers (1996) Erik Barendsen and Sjaak Smetsers. 1996.  Uniqueness Typing for Functional Languages with Graph Rewriting Semantics.  _Mathematical Structures in Computer Science_ 6, 6 (1996), 579–612.
  * Benton (1995) P Nick Benton. 1995.  A Mixed Linear and Non-Linear Logic: Proofs, Terms and Models. In _Computer Science Logic: 8th Workshop, CSL’94 Kazimierz, Poland, September 25–30, 1994 Selected Papers 8_. Springer, 121–135.
  * Bernardy et al. (2017) Jean-Philippe Bernardy, Mathieu Boespflug, Ryan R Newton, Simon Peyton Jones, and Arnaud Spiwack. 2017.  Linear Haskell: Practical Linearity in a Higher-Order Polymorphic Language.  _Proceedings of the ACM on Programming Languages_ 2, POPL (2017), 1–29.
  * Bianchini et al. (2023) Riccardo Bianchini, Francesco Dagnino, Paola Giannini, and Elena Zucca. 2023.  Multi-Graded Featherweight Java. In _37th European Conference on Object-Oriented Programming, ECOOP 2023, July 17-21, 2023, Seattle, Washington, United States_ _(LIPIcs, Vol. 263)_ , Karim Ali and Guido Salvaneschi (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 3:1–3:27.  https://doi.org/10.4230/LIPIcs.ECOOP.2023.3
  * Bianchini et al. (2022) Riccardo Bianchini, Francesco Dagnino, Paola Giannini, Elena Zucca, and Marco Servetto. 2022.  Coeffects for Sharing and Mutation.  _Proc. ACM Program. Lang._ 6, OOPSLA2, Article 156 (oct 2022), 29 pages.  https://doi.org/10.1145/3563319
  * Bornat et al. (2005) Richard Bornat, Cristiano Calcagno, Peter O’Hearn, and Matthew Parkinson. 2005.  Permission Accounting in Separation Logic. In _Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages_ (Long Beach, California, USA) _(POPL ’05)_. Association for Computing Machinery, New York, NY, USA, 259–270.  https://doi.org/10.1145/1040305.1040327
  * Boyland (2003) John Boyland. 2003.  Checking Interference with Fractional Permissions. In _Static Analysis: 10th International Symposium, SAS 2003 San Diego, CA, USA, June 11–13, 2003 Proceedings_. Springer, 55–72.
  * Brady (2021) Edwin C. Brady. 2021.  Idris 2: Quantitative Type Theory in Practice.  , 9:1–9:26 pages.  https://doi.org/10.4230/LIPIcs.ECOOP.2021.9
  * Brunel et al. (2014) Aloïs Brunel, Marco Gaboardi, Damiano Mazza, and Steve Zdancewic. 2014.  A Core Quantitative Coeffect Calculus. In _ESOP_ , Vol. 8410. Springer, 351–370.
  * Choudhury et al. (2021) Pritam Choudhury, Harley Eades III, Richard A Eisenberg, and Stephanie Weirich. 2021.  A Graded Dependent Type System with a Usage-Aware Semantics.  _Proceedings of the ACM on Programming Languages_ 5, POPL (2021), 1–32.
  * Clarke and Wrigstad (2003) Dave Clarke and Tobias Wrigstad. 2003.  External Uniqueness is Unique Enough. In _ECOOP 2003–Object-Oriented Programming: 17th European Conference, Darmstadt, Germany, July 21-25, 2003. Proceedings 17_. Springer, 176–200.
  * Clarke et al. (1998) David G. Clarke, John M. Potter, and James Noble. 1998.  Ownership Types for Flexible Alias Protection. In _Proceedings of the 13th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications_ (Vancouver, British Columbia, Canada) _(OOPSLA ’98)_. Association for Computing Machinery, New York, NY, USA, 48–64.  https://doi.org/10.1145/286936.286947
  * de Vries (2013) Edsko de Vries. 2013.  Modelling Unique and Affine Typing Using Polymorphism. In _Essays Dedicated to Rinus Plasmeijer on the Occasion of His 61st Birthday on The Beauty of Functional Code - Volume 8106_. Springer-Verlag, Berlin, Heidelberg, 181–192.  https://doi.org/10.1007/978-3-642-40355-2{_}13
  * de Vries et al. (2009) Edsko de Vries, Adrian Francalanza, and Matthew Hennessy. 2009.  Uniqueness Typing for Resource Management in Message-Passing Concurrency. In _Proceedings First International Workshop on Linearity, LINEARITY 2009, Coimbra, Portugal, 12th September 2009_ _(EPTCS, Vol. 22)_ , Mário Florido and Ian Mackie (Eds.). 26–37.  https://doi.org/10.4204/EPTCS.22.3
  * de Vries et al. (2008) Edsko de Vries, Rinus Plasmeijer, and David M. Abrahamson. 2008.  Uniqueness Typing Simplified. In _Implementation and Application of Functional Languages_ , Olaf Chitil, Zoltán Horváth, and Viktória Zsók (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 201–218.
  * Eades III and Orchard (2020) Harley Eades III and Dominic Orchard. 2020.  Grading Adjoint Logic.  _arXiv preprint arXiv:2006.08854_ (2020).
  * Fluet et al. (2006) Matthew Fluet, Greg Morrisett, and Amal Ahmed. 2006.  Linear Regions Are All You Need. In _Programming Languages and Systems_ , Peter Sestoft (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 7–21.
  * Gaboardi et al. (2016) Marco Gaboardi, Shin-ya Katsumata, Dominic Orchard, Flavien Breuvart, and Tarmo Uustalu. 2016.  Combining Effects and Coeffects via Grading. In _Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming_ (Nara, Japan) _(ICFP 2016)_. Association for Computing Machinery, New York, NY, USA, 476–489.  https://doi.org/10.1145/2951913.2951939
  * Ghica and Smith (2014) Dan R. Ghica and Alex I. Smith. 2014.  Bounded Linear Types in a Resource Semiring. In _Proceedings of the 23rd European Symposium on Programming Languages and Systems - Volume 8410_. Springer-Verlag, Berlin, Heidelberg, 331–350.  https://doi.org/10.1007/978-3-642-54833-8_18
  * Girard (1987) Jean-Yves Girard. 1987.  Linear Logic.  _Theoretical Computer Science_ 50, 1 (1987), 1–101.
  * Girard et al. (1992) Jean-Yves Girard, Andre Scedrov, and Philip J Scott. 1992.  Bounded Linear Logic: A Modular Approach to Polynomial-Time Computability.  _Theoretical Computer Science_ 97, 1 (1992), 1–66.
  * Harrington (2006) Dana Harrington. 2006.  Uniqueness Logic.  _Theoretical Computer Science_ 354, 1 (2006), 24–41.
  * Hicks et al. (2004) Michael Hicks, Greg Morrisett, Dan Grossman, and Trevor Jim. 2004.  Experience with Safe Manual Memory-Management in Cyclone. In _Proceedings of the 4th International Symposium on Memory Management_ (Vancouver, BC, Canada) _(ISMM ’04)_. Association for Computing Machinery, New York, NY, USA, 73–84.  https://doi.org/10.1145/1029873.1029883
  * Hogg (1991) John Hogg. 1991.  Islands: Aliasing Protection in Object-Oriented Languages.  _SIGPLAN Not._ 26, 11 (nov 1991), 271–285.  https://doi.org/10.1145/118014.117975
  * Hughes et al. (2021a) Jack Hughes, Daniel Marshall, James Wood, and Dominic Orchard. 2021a.  Linear Exponentials as Graded Modal Types. In _5th International Workshop on Trends in Linear Logic and Applications (TLLA 2021)_.
  * Hughes et al. (2021b) Jack Hughes, Michael Vollmer, and Dominic Orchard. 2021b.  Deriving Distributive Laws for Graded Linear Types.  _Electronic Proceedings in Theoretical Computer Science_ 353 (dec 2021), 109–131.  https://doi.org/10.4204/eptcs.353.6
  * Jouvelot and Gifford (1991) Pierre Jouvelot and David Gifford. 1991.  Algebraic Reconstruction of Types and Effects. In _Proceedings of the 18th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages_ (Orlando, Florida, USA) _(POPL ’91)_. Association for Computing Machinery, New York, NY, USA, 303–310.  https://doi.org/10.1145/99583.99623
  * Jung et al. (2019) Ralf Jung, Hoang-Hai Dang, Jeehoon Kang, and Derek Dreyer. 2019.  Stacked Borrows: An Aliasing Model for Rust.  _Proceedings of the ACM on Programming Languages_ 4, POPL (2019), 1–32.
  * Jung et al. (2017) Ralf Jung, Jacques-Henri Jourdan, Robbert Krebbers, and Derek Dreyer. 2017.  RustBelt: Securing the Foundations of the Rust Programming Language.  _Proceedings of the ACM on Programming Languages_ 2, POPL (2017), 1–34.
  * Lorenzen et al. (2023) Anton Lorenzen, Daan Leijen, and Wouter Swierstra. 2023.  FP2: Fully in-Place Functional Programming. In _ICFP’23_. ACM SIGPLAN.  https://www.microsoft.com/en-us/research/publication/fp2-fully-in-place-functional-programming-2/ preprint.
  * Lucassen and Gifford (1988) J. M. Lucassen and D. K. Gifford. 1988.  Polymorphic Effect Systems. In _Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages_ (San Diego, California, USA) _(POPL ’88)_. Association for Computing Machinery, New York, NY, USA, 47–57.  https://doi.org/10.1145/73560.73564
  * Makwana and Krishnaswami (2019) Dhruv C Makwana and Neel Krishnaswami. 2019.  NumLin: Linear Types for Linear Algebra.  (2019).
  * Marshall and Orchard (2022a) Daniel Marshall and Dominic Orchard. 2022a.  Graded Modal Types for Integrity and Confidentiality. In _17th Workshop on Programming Languages and Analysis for Security (PLAS 2022)_.
  * Marshall and Orchard (2022b) Daniel Marshall and Dominic Orchard. 2022b.  Replicate, Reuse, Repeat: Capturing Non-Linear Communication via Session Types and Graded Modal Types.  _arXiv preprint arXiv:2203.12875_ (2022).
  * Marshall and Orchard (2022c) Daniel Marshall and Dominic A Orchard. 2022c.  How to Take the Inverse of a Type. In _Proceedings of 36th European Conference on Object-Oriented Programming (ECOOP 2022)_.
  * Marshall et al. (2022) Daniel Marshall, Michael Vollmer, and Dominic Orchard. 2022.  Linearity and Uniqueness: An Entente Cordiale. In _Programming Languages and Systems: 31st European Symposium on Programming, ESOP 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Munich, Germany, April 2–7, 2022, Proceedings_. Springer International Publishing Cham, 346–375.
  * McBride (2001) Conor McBride. 2001.  The Derivative of a Regular Type is its Type of One-Hole Contexts.  _Unpublished manuscript_ (2001), 74–88.
  * McBride (2016) Conor McBride. 2016.  I Got Plenty o’ Nuttin’.  _A List of Successes That Can Change the World: Essays Dedicated to Philip Wadler on the Occasion of His 60th Birthday_ (2016), 207–233.
  * Moon et al. (2021) Benjamin Moon, Harley Eades III, and Dominic Orchard. 2021.  Graded Modal Dependent Type Theory.  _Programming Languages and Systems_ 12648 (2021), 462.
  * Mycroft and Voigt (2013) Alan Mycroft and Janina Voigt. 2013.  Notions of Aliasing and Ownership.  In _Aliasing in Object-Oriented Programming. Types, Analysis and Verification_ , Dave Clarke, James Noble, and Tobias Wrigstad (Eds.). Lecture Notes in Computer Science, Vol. 7850. Springer, 59–83.  https://doi.org/10.1007/978-3-642-36946-9_4
  * O’Connor et al. (2021) Liam O’Connor, Zilin Chen, Christine Rizkallah, Vincent Jackson, Sidney Amani, Gerwin Klein, Toby Murray, Thomas Sewell, and Gabriele Keller. 2021.  Cogent: Uniqueness Types and Certified Compilation.  _J. Funct. Program._ (2021).
  * Orchard et al. (2019) Dominic Orchard, Vilem-Benjamin Liepelt, and Harley Eades III. 2019.  Quantitative Program Reasoning with Graded Modal Types.  _Proceedings of the ACM on Programming Languages_ 3, ICFP (2019), 1–30.
  * Pearce (2021) David J Pearce. 2021.  A Lightweight Formalism for Reference Lifetimes and Borrowing in Rust.  _ACM Transactions on Programming Languages and Systems (TOPLAS)_ 43, 1 (2021), 1–73.
  * Petricek et al. (2014) Tomas Petricek, Dominic Orchard, and Alan Mycroft. 2014.  Coeffects: A Calculus of Context-Dependent Computation. In _Proceedings of the 19th ACM SIGPLAN International Conference on Functional Programming_ (Gothenburg, Sweden) _(ICFP ’14)_. Association for Computing Machinery, New York, NY, USA, 123–135.  https://doi.org/10.1145/2628136.2628160
  * Radanne et al. (2020) Gabriel Radanne, Hannes Saffrich, and Peter Thiemann. 2020.  Kindly Bent to Free Us.  _Proc. ACM Program. Lang._ 4, ICFP, Article 103 (Aug. 2020), 29 pages.  https://doi.org/10.1145/3408985
  * Sammler et al. (2021) Michael Sammler, Rodolphe Lepigre, Robbert Krebbers, Kayvan Memarian, Derek Dreyer, and Deepak Garg. 2021.  RefinedC: Automating the Foundational Verification of C Code with Refined Ownership Types. In _Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation_. 158–174.
  * Smetsers et al. (1994) Sjaak Smetsers, Erik Barendsen, Marko van Eekelen, and Rinus Plasmeijer. 1994.  Guaranteeing Safe Destructive Updates Through a Type System with Uniqueness Information for Graphs. In _Graph Transformations in Computer Science_ , Hans Jürgen Schneider and Hartmut Ehrig (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 358–379.  https://doi.org/10.1007/3-540-57787-4_23
  * Somogyi et al. (1996) Zoltan Somogyi, Fergus Henderson, and Thomas Conway. 1996.  The Execution Algorithm of Mercury, an Efficient Purely Declarative Logic Programming Language.  _The Journal of Logic Programming_ 29, 1 (1996), 17–64.  https://doi.org/10.1016/S0743-1066(96)00068-4 High-Performance Implementations of Logic Programming Systems.
  * Spiwack et al. (2022) Arnaud Spiwack, Csongor Kiss, Jean-Philippe Bernardy, Nicolas Wu, and Richard A. Eisenberg. 2022.  Linearly Qualified Types: Generic Inference for Capabilities and Uniqueness.  _Proc. ACM Program. Lang._ 6, ICFP, Article 95 (aug 2022), 28 pages.  https://doi.org/10.1145/3547626
  * Tofte et al. (2004) Mads Tofte, Lars Birkedal, Martin Elsman, and Niels Hallenberg. 2004.  A Retrospective on Region-Based Memory Management.  _Higher-Order and Symbolic Computation_ 17, 3 (Sept. 2004), 245–265.  https://doi.org/10.1023/B:LISP.0000029446.78563.a4
  * Tov and Pucella (2011) Jesse A. Tov and Riccardo Pucella. 2011.  Practical Affine Types.  _SIGPLAN Not._ 46, 1 (Jan. 2011), 447–458.  https://doi.org/10.1145/1925844.1926436
  * Wadler (1990) Philip Wadler. 1990.  Linear Types can Change the World!. In _Programming Concepts and Methods_ , Vol. 3. Citeseer, 5.
  * Wadler (1993) Philip Wadler. 1993.  A Syntax for Linear Logic. In _Mathematical Foundations of Programming Semantics, 9th International Conference, New Orleans, LA, USA, April 7-10, 1993, Proceedings_. 513–529.  https://doi.org/10.1007/3-540-58027-1_24
  * Walker et al. (2000) David Walker, Karl Crary, and Greg Morrisett. 2000.  Typed Memory Management via Static Capabilities.  _ACM Trans. Program. Lang. Syst._ 22, 4 (jul 2000), 701–771.  https://doi.org/10.1145/363911.363923
  * Weiss et al. (2019) Aaron Weiss, Olek Gierczak, Daniel Patterson, and Amal Ahmed. 2019.  Oxide: The Essence of Rust.  _arXiv preprint arXiv:1903.00982_ (2019).
  * Wood and Atkey (2022) James Wood and Robert Atkey. 2022.  A Framework for Substructural Type Systems. In _Programming Languages and Systems - 31st European Symposium on Programming, ESOP 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Munich, Germany, April 2-7, 2022, Proceedings_ _(Lecture Notes in Computer Science, Vol. 13240)_ , Ilya Sergey (Ed.). Springer, 376–402.  https://doi.org/10.1007/978-3-030-99336-8_14
  * Zhu and Xi (2005) Dengping Zhu and Hongwei Xi. 2005.  Safe Programming with Pointers Through Stateful Views. In _Practical Aspects of Declarative Languages_ , Manuel V. Hermenegildo and Daniel Cabeza (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 83–97.

```

`

``

``

`

`

`

`

`

`

`


in $V^{2}_{S}$, the argument also applies when $u_{i}$ is at high modulation.
∎

######  Lemma 7.7 (HighxHigh-Low-interaction).

Let $N_{1}\sim N_{2}\gg 1$, and $N\ll N_{1}$. Then, we find (77) to hold with
$C(\underline{N},\underline{M})=N_{1}^{\frac{1}{2}+}M_{\min}^{\frac{1}{2}}$.

###### Proof.

If $N=1$, we carry out an additional homogeneous dyadic decomposition in $N\in
2^{\mathbb{Z}}$. Let $N\leq N_{1}^{-4}$. In this case we simply use two
$L^{4}$-Strichartz estimates to find

$\begin{split}\big{|}\iint
P_{N,M}v\partial_{x}(P_{N_{1},M_{1}}u_{1}P_{N_{2},M_{2}}u_{2})\big{|}&\lesssim
NT^{\frac{1}{2}}\|P_{N_{1},M_{1}}u_{1}\|_{L^{4}}\|P_{N_{2},M_{2}}u_{2}\|_{L^{4}}\\\
&\lesssim
NT^{\frac{1}{2}}(N_{1}N)^{\frac{1}{2}}\|P_{N_{1},M_{1}}u_{1}\|_{U^{2}_{S}}\|P_{N_{2},M_{2}}u_{2}\|_{U^{2}_{S}}.\end{split}$

In the following let $N\geq N_{1}^{-4}$. We begin with the resonant case when
all functions have modulation $\ll N_{1}^{4}N$. This allows us to use a
bilinear Strichartz estimate

$\begin{split}&\quad\big{|}\iint Q_{\ll N_{1}^{4}N}P_{N,M}v\partial_{x}(Q_{\ll
N_{1}^{4}N}P_{N_{1},M_{1}}u_{1}Q_{\ll
N_{1}^{4}N}P_{N_{2},M_{2}}u_{2})\big{|}\\\ &\lesssim N\|Q_{\ll
N_{1}^{4}N}(Q_{\ll N_{1}^{4}N}P_{N_{1},M_{1}}u_{1}Q_{\ll
N_{1}^{4}N}P_{N,M}v)\|_{L_{t}^{1}L_{x}^{2}}\\\ &\lesssim
NT^{\frac{1}{2}}\big{(}\frac{N}{N_{1}^{2}}\big{)}^{\frac{1}{2}}M_{\min}^{\frac{1}{2}}\|P_{N_{1},M_{1}}u_{1}\|_{U^{2}_{S}}\|P_{N_{2},M_{2}}v\|_{U^{2}_{S}}\|P_{N_{2},M_{2}}u_{2}\|_{U^{2}_{S}}.\end{split}$

But we have to estimate $v$ in $V^{2}_{S}$. For this purpose we interpolate
(cf. [7, Proposition 2.20]) with the Strichartz estimate

$\|P_{N_{1},M_{1}}u_{1}P_{N,M}v\|_{L^{2}}\lesssim
N^{\frac{3}{4}}N_{1}^{\frac{1}{4}}\|P_{N_{1},M_{1}}u_{1}\|_{U^{4}_{S}}\|P_{N_{2},M_{2}}v\|_{U^{4}_{S}}.$

Hence, we obtain

$\lesssim
T^{\frac{1}{2}}\big{(}\frac{N}{N_{1}^{2}}\big{)}^{\frac{1}{2}}N\log(N^{\frac{1}{4}}N_{1}^{\frac{5}{4}})\|P_{N_{1},M_{1}}u_{1}\|_{V^{2}_{S}}\|P_{N_{2},M_{2}}u_{2}\|_{V^{2}_{S}}\|P_{N,M}v\|_{V^{2}_{S}}.$

In the non-resonant case we have one modulation comparable to $N_{1}^{4}N$. We
obtain

$\begin{split}\big{|}\iint Q_{\gtrsim
N_{1}^{4}N}P_{N,M}v\partial_{x}(P_{N_{1},M_{1}}u_{1}P_{N_{2},M_{2}}u_{2})\big{|}&\lesssim\|Q_{\gtrsim
N_{1}^{4}N}\partial_{x}P_{N,M}v\|_{L^{2}}\|P_{N_{1},M_{1}}u_{1}\|_{L^{4}}\|P_{N_{2},M_{2}}u_{2}\|_{L^{4}}\\\
&\lesssim
N(N_{1}^{4}N)^{-\frac{1}{2}}(N_{1}N_{2})^{\frac{1}{2}}\|P_{N_{1},M_{1}}u_{1}\|_{V^{2}_{S}}\|P_{N_{2},M_{2}}u_{2}\|_{V^{2}_{S}}.\end{split}$

An interpolation argument like above yields an additional factor of
$T^{\alpha}$. The estimates with $u_{i}$ at high modulation are better behaved
because of improved $L^{4}$-Strichartz estimates at low frequencies (applied
to $P_{N,M}v$). ∎

######  Lemma 7.8 (LowxLow-interaction).

Let $N,N_{1},N_{2}\lesssim 1$. Then, we find (77) to hold with
$C(\underline{N},\underline{M})=1$.

###### Proof.

By two $L^{4}$-Strichartz estimates we find

$\sup_{\|v\|_{V^{2}_{S}}=1}\big{|}\iint
P_{N,M}v\partial_{x}(P_{N_{1},M_{1}}u_{1}P_{N_{2},M_{2}}u_{2})\big{|}\lesssim
T^{\frac{1}{2}}\|P_{N_{1},M_{1}}u_{1}\|_{L^{4}}\|P_{N_{2},M_{2}}u_{2}\|_{L^{4}}\lesssim
T^{\frac{1}{2}}\prod_{i=1}^{2}\|u_{i}\|_{U^{2}_{S}},$

which is good enough. ∎

##  Appendix A Anisotropic Leibniz rule on mixed domains

This section is devoted to the proof of Proposition 6.4. We use the following
fractional Leibniz rule, which is based on the well-known Kato-Ponce estimate
(cf. [4, 5]) for $\alpha\geq 0$,
$\frac{1}{2}=\frac{1}{p_{1}}+\frac{1}{q_{1}}=\frac{1}{p_{2}}+\frac{1}{q_{2}}$
for $1<p_{1},p_{2},q_{1},q_{2}\leq\infty$:

$\|\langle\partial\rangle^{\alpha}(fg)\|_{L^{2}(\mathbb{R}^{d})}\lesssim\|\langle\partial\rangle^{\alpha}f\|_{L^{p_{1}}(\mathbb{R}^{d})}\|g\|_{L^{q_{1}}(\mathbb{R}^{d})}+\|f\|_{L^{p_{2}}(\mathbb{R}^{d})}\|\langle\partial\rangle^{\alpha}g\|_{L^{q_{2}}(\mathbb{R}^{d})}.$
(81)

We also need the above on $\mathbb{R}^{d_{1}}\times\mathbb{T}^{d_{2}}$. It
turns out we can transfer the above estimate for $1<p_{1},q_{2}<\infty$ in a
straightforward manner by an extension operator. Let $\varphi\in
C^{\infty}_{c}(\mathbb{R}^{d};\mathbb{R}_{\geq 0})$ denote a radially
decreasing function with $\varphi(x)=1$ for $|x|\leq 10$ and $\varphi(x)=0$
for $|x|\geq 15$. We denote the extension $\tilde{f}=f\varphi\in
L^{2}(\mathbb{R}^{d})$ of $f\in L^{2}(\mathbb{T}^{d})$. We have for
$k\in\mathbb{N}$ clearly

$\|\langle\partial\rangle^{k}f\|_{L^{2}(\mathbb{T}^{d})}\lesssim\|\langle\partial\rangle^{k}\tilde{f}\|_{L^{2}(\mathbb{R}^{d})}\lesssim\|\langle\partial\rangle^{k}f\|_{L^{2}(\mathbb{T}^{d})}.$

By interpolation, the equivalence also holds for $\langle\partial\rangle^{s}$,
and by obvious modification of the extension operator also holds on
$\mathbb{R}^{d_{1}}\times\mathbb{T}^{d_{2}}$. So, let
$f,g:\mathbb{T}^{d}\to\mathbb{C}$, and let $\tilde{f}$,
$\tilde{g}:\mathbb{R}^{d}\to\mathbb{C}$ denote their extensions. Then we
obtain

$\|\langle\partial\rangle^{\alpha}(fg)\|_{L^{2}(\mathbb{T}^{d})}\lesssim\|\langle\partial\rangle^{\alpha}(\tilde{f}\tilde{g})\|_{L^{2}(\mathbb{R}^{d})}\lesssim\|\langle\partial\rangle^{\alpha}\tilde{f}\|_{L^{p_{1}}(\mathbb{R}^{d})}\|\tilde{g}\|_{L^{p_{2}}(\mathbb{R}^{d})}+\|\tilde{f}\|_{L^{q_{1}}(\mathbb{R}^{d})}\|\langle\partial\rangle^{\alpha}\tilde{g}\|_{L^{q_{2}}(\mathbb{R}^{d})}.$

Clearly,

$\|\tilde{g}\|_{L^{p_{2}}(\mathbb{R}^{d})}\lesssim\|g\|_{L^{p_{2}}(\mathbb{T}^{d})},\quad\|\tilde{f}\|_{L^{q_{1}}(\mathbb{R}^{d})}\lesssim\|f\|_{L^{q_{1}}(\mathbb{T}^{d})}.$

To argue that

$\|\langle\partial\rangle^{\alpha}\tilde{f}\|_{L^{p}(\mathbb{R}^{d})}\lesssim\|\langle\partial\rangle^{\alpha}f\|_{L^{p}(\mathbb{T}^{d})}$
(82)

for $1<p<\infty$, we again use interpolation such that it suffices to show
(82) for $\alpha=k\in\mathbb{N}$. We use the characterization of $L^{p}$-based
Sobolev spaces

$\|\langle\partial\rangle^{k}\tilde{f}\|_{L^{p}(\mathbb{R}^{d})}\simeq\|\tilde{f}\|_{L^{p}(\mathbb{R}^{d})}+\sum_{|\alpha|=k}\|\partial^{\alpha}\tilde{f}\|_{L^{p}(\mathbb{R}^{d})}$

from which (82) is immediate by the product rule. We have proved the
following:

######  Proposition A.1 (Fractional Leibniz rule on cylinders).

Let $d_{1},d_{2}\in\mathbb{N}_{0}$ with $d_{1}+d_{2}\geq 1$, $\alpha\geq 0$,
$\frac{1}{2}=\frac{1}{p_{1}}+\frac{1}{q_{1}}=\frac{1}{p_{2}}+\frac{1}{q_{2}}$
for $1<p_{1},p_{2},q_{1},q_{2}\leq\infty$ and $1<p_{1},q_{2}<\infty$:

$\|\langle\partial\rangle^{\alpha}(fg)\|_{L^{2}(\mathbb{R}^{d_{1}}\times\mathbb{T}^{d_{2}})}\lesssim\|\langle\partial\rangle^{\alpha}f\|_{L^{p_{1}}(\mathbb{R}^{d_{1}}\times\mathbb{T}^{d_{2}})}\|g\|_{L^{q_{1}}(\mathbb{R}^{d_{1}}\times\mathbb{T}^{d_{2}})}+\|f\|_{L^{p_{2}}(\mathbb{R}^{d_{1}}\times\mathbb{T}^{d_{2}})}\|\langle\partial\rangle^{\alpha}g\|_{L^{q_{2}}(\mathbb{R}^{d_{1}}\times\mathbb{T}^{d_{2}})}.$
(83)

From the above we derive the following anisotropic version. Let
$\mathbb{D}=\mathbb{K}_{1}\times\mathbb{K}_{2}\times\mathbb{K}_{3}$ and write
$(x,y)\in\mathbb{K}_{1}\times(\mathbb{K}_{2}\times\mathbb{K}_{3})=\mathbb{D}$.
Dual variables will be denoted by $\xi$ and $\eta$. We define Fourier
multipliers $\langle\partial_{x}\rangle^{\alpha}$ and
$\langle\partial_{y}\rangle^{\beta}$ on $\mathbb{D}$ by

$(\langle\partial_{x}\rangle^{\alpha}f)\widehat{(}\xi,\eta)=\langle\xi\rangle^{\alpha}\hat{f}(\xi),\quad(\langle\partial_{y}\rangle^{\beta}f)\widehat{(}\xi,\eta)=\langle\eta\rangle^{\beta}\hat{f}(\xi,\eta).$

We are ready for the proof of Proposition A.2, whose statement is repeated for
convenience:

######  Proposition A.2.

Let $\mathbb{D}=\mathbb{K}_{1}\times\mathbb{K}_{2}\times\mathbb{K}_{3}$ with
$\mathbb{K}_{i}\in\\{\mathbb{R};\mathbb{T}\\}$, $\alpha,\beta\geq 0$,
$\delta>0$, and $\frac{1}{2}=\frac{1}{p}+\frac{1}{q}$. Then the following
estimate holds:

$\|\langle\partial_{x}\rangle^{\alpha}\langle\partial_{y}\rangle^{\beta}(u^{2})\|_{L^{2}_{xy}(\mathbb{D})}\lesssim\|\langle\partial_{x}\rangle^{\alpha}\langle\partial_{y}\rangle^{\beta}u\|_{L^{2}_{xy}(\mathbb{D})}\|u\|_{L^{\infty}_{xy}(\mathbb{D})}+\|\langle\partial_{x}\rangle^{\alpha+\delta}u\|_{L^{2}_{x}L_{y}^{p}(\mathbb{D})}\|\langle\partial_{y}\rangle^{\beta}u\|_{L^{\infty}_{x}L_{y}^{q}(\mathbb{D})}.$
(84)

###### Proof.

We use a paraproduct decomposition for the $x$ frequencies. Let $P_{N}$ denote
dyadic Littlewood-Paley projections in the $x$-frequencies. First note that by
the usual fractional Leibniz rule (81) we find for the low frequencies:

$\|\langle\partial_{x}\rangle^{\alpha}\langle\partial_{y}\rangle^{\beta}P_{\lesssim
1}(u^{2})\|_{L^{2}_{xy}}\lesssim\|\langle\partial_{y}\rangle^{\beta}(u^{2})\|_{L^{2}_{xy}}\lesssim\|\langle\partial_{y}\rangle^{\beta}u\|_{L^{2}_{x}L^{2}_{y}}\|u\|_{L^{\infty}_{xy}}.$

By Littlewood-Paley theory, we write

$\|P_{\gtrsim 1}u\|^{2}_{L^{2}_{xy}}=\sum_{N\in
2^{\mathbb{N}_{0}}}\|P_{N}u\|_{L^{2}_{xy}}^{2}.$

For $N\in 2^{\mathbb{N}_{0}}$ we estimate the High-Low interaction as follows:

$\begin{split}\|\langle\partial_{x}\rangle^{\alpha}\langle\partial_{y}\rangle^{\beta}P_{N}(P_{N}uP_{\ll
N}u)\|_{L^{2}_{xy}}&\sim
N^{\alpha}\big{\|}\|\langle\partial_{y}\rangle^{\beta}(P_{\sim N}uP_{\ll
N}u)\|_{L^{2}_{y}}\big{\|}_{L^{2}_{x}}\\\ &\lesssim
N^{\alpha}\big{\|}\|\langle\partial_{y}\rangle^{\beta}P_{\sim
N}u\|_{L^{2}_{y}}\|P_{\ll N}u\|_{L^{\infty}_{y}}+\|P_{\sim
N}u\|_{L_{y}^{p}}\|\langle\partial_{y}\rangle^{\beta}P_{\ll
N}u\|_{L_{y}^{q}}\big{\|}_{L^{2}_{x}}\\\
&\lesssim\|\langle\partial_{x}\rangle^{\alpha}\langle\partial_{y}\rangle^{\beta}P_{N}u\|_{L^{2}_{xy}}\|P_{\ll
N}u\|_{L^{\infty}_{xy}}\\\
&\quad+N^{-\delta}\|\langle\partial_{x}\rangle^{\alpha+\delta}P_{N}u\|_{L_{x}^{2}L^{p}_{y}}\|P_{\ll
N}\langle\partial_{y}\rangle^{\beta}u\|_{L_{x}^{\infty}L_{y}^{q}}.\end{split}$

The claim follows from square summation. The High-High-Low interaction can be
estimated likewise. ∎

######  Remark A.3.

The $\delta$-derivative loss can likely be removed by modifying the arguments
from [4] to the anisotropic setting, but we do not need this in the following.

##  Appendix B Semilinear ill-posedness issues

In this section, we prove that the Cauchy problem for (KP-I) is semilinearly
ill-posed for initial data in $H^{s_{1},s_{2}}(\mathbb{R}^{3})$ for any
$(s_{1},s_{2})\in\mathbb{R}^{2}$ and $\alpha<\frac{15}{7}$, namely we prove
that the flow-map for (KP-I) cannot be $C^{2}$-differentiable at the origin.
For similar results for the two-dimensional equation on $\mathbb{R}^{2}$, we
refer to [15, 13, 18].

######  Theorem B.1.

Let $\alpha<\frac{15}{7}$, $\bar{s}\in\mathbb{R}^{2}$ and
$\mathbb{D}=\mathbb{R}^{3}$. Then there exists no $T>0$ such that (KP-I)
admits a unique local solution defined on the interval $[-T,T]$ such that the
flow-map for (KP-I)

$\Gamma:u_{0}\mapsto u,$

is $C^{2}$-differentiable at zero from $H^{\bar{s}}(\mathbb{R}^{3})$ to
$C([-T,T],H^{\bar{s}}(\mathbb{R}^{3}))$.

###### Proof.

We consider the following Cauchy problem for $\gamma\in\mathbb{R}$:

$\left\\{\begin{array}[]{cl}\partial_{t}u-D_{x}^{\alpha}\partial_{x}u-\partial_{x}^{-1}\Delta_{y}u&=\partial_{x}(u^{2}),\quad(x,y,t)\in\mathbb{R}\times\mathbb{R}^{2}\times\mathbb{R},\\\
u(0)&=\gamma\phi\in H^{s_{1},s_{2}}(\mathbb{R}^{3}).\end{array}\right.$ (85)

Suppose that $u(\gamma,x,y,t)$ solves (85). Fix $T>0$ such that the map
$\Gamma$ is $C^{2}$ and let $t\in(0,T)$. Then,

$u(\gamma,x,y,t)=\gamma
S_{\alpha}(t)\phi(x,y)+\int_{0}^{t}S_{\alpha}(t-t^{\prime})u(\gamma,x,y,t^{\prime})u_{x}(\gamma,x,y,t^{\prime})dt^{\prime}.$
(86)

Then

$\begin{split}\frac{\partial
u}{\partial\gamma}(0,x,y,t)&=S_{\alpha}(t)\phi(x,y)=:u_{1}(x,y,t)\\\
\frac{\partial^{2}u}{\partial\gamma^{2}}(0,x,y,t)&=2\int_{0}^{t}S_{\alpha}(t-t^{\prime})u_{1}(x,y,t^{\prime})\partial_{x}u_{1}(x,y,t^{\prime})=:u_{2}(x,y,t).\end{split}$
(87)

The $C^{2}$ assumption enables us to write

$u(\gamma,x,y,t)=\gamma
u_{1}(x,y,t)+\frac{\gamma^{2}}{2!}u_{2}(x,y,t)+o(\gamma^{2}),$

and

$\|u_{2}(\cdot,\cdot,t)\|_{H^{\bar{s}}(\mathbb{R}^{3})}\lesssim\|\phi\|_{H^{\bar{s}}(\mathbb{R}^{3})}^{2}.$
(88)

We show that there exists initial data $\phi$ such that (88) fails. For
$\xi\in\mathbb{R},\eta\in\mathbb{R}^{2}$, define $\phi$ by its Fourier
transform as follows:

$\hat{\phi}(\xi,\eta)=|D_{1}|^{-\frac{1}{2}}\mathbf{1}_{D_{1}}(\xi,\eta)+|D_{2}|^{-\frac{1}{2}}N^{-s_{1}-(1+\frac{\alpha}{2})s_{2}}\mathbf{1}_{D_{2}}(\xi,\eta),$
(89)

where $D_{1}$ and $D_{2}$ are defined as follows and $|D_{i}|$ denotes the
measure of the sets $D_{i},i=1,2$:

$\begin{split}D_{1}&:=[\beta/2,\beta]\times[-\sqrt{\alpha+1}\beta^{2},\sqrt{\alpha+1}\beta^{2}]\times[-\beta^{\frac{1}{2}+2\delta},\beta^{\frac{1}{2}+2\delta}],\\\
D_{2}&:=[N,N+\beta]\times[\sqrt{\alpha+1}N^{2},\sqrt{\alpha+1}N^{2}+\beta^{2}]\times[-N^{\frac{1}{2}-\delta},N^{\frac{1}{2}-\delta}].\end{split}$
(90)

Here $N,\beta,\delta>0$ are real numbers such that $N\gg 1,\beta,\delta\ll 1$
and will be chosen later. A simple computation gives that
$\|\phi\|_{H^{\bar{s}}(\mathbb{R}^{3})}\sim 1$. Using [16, Lemma 4], we can
write $u_{2}$ as follows:

$u_{2}(x,y,t)=c\int_{\mathbb{R}^{4}}e^{i(x\xi+y.\eta+t(\xi|\xi|^{\alpha}+|\eta|^{2}/\xi))}\frac{\xi
e^{it(\tau-\xi|\xi|^{\alpha}-\frac{|\eta|^{2}}{\xi})}}{\tau-\xi|\xi|^{\alpha}-\frac{|\eta|^{2}}{\xi}}\widehat{u_{1}}\ast\widehat{u_{1}}(\xi,\eta,\tau)d\xi
d\eta d\tau.$ (91)

Using the definition of $u_{1}$, the expression for
$\widehat{u_{1}}\ast\widehat{u_{1}}$ is given by

$\widehat{u_{1}}\ast\widehat{u_{1}}(\xi,\eta,\tau)=\int_{\mathbb{R}^{3}}\delta\Big{(}\tau-\xi_{1}|\xi_{1}|^{\alpha}-\frac{|\eta_{1}|^{2}}{\xi_{1}}-\xi_{2}|\xi_{2}|^{\alpha}-\frac{|\eta_{2}|^{2}}{\xi_{2}}\Big{)}\hat{\phi}(\xi_{1},\eta_{1})\hat{\phi}(\xi_{2},\eta_{2})d\xi_{1}d\eta_{1}.$
(92)

Set

$\Phi(x,y,t,\xi_{1},\eta_{1},\xi_{2},\eta_{2}):=\xi
e^{i(x\xi+y\cdot\eta+t(\xi|\xi|^{\alpha}+|\eta|^{2}/\xi))}\frac{e^{-it\Omega_{\alpha}(\xi_{1},\eta_{1},\xi_{2},\eta_{2})}-1}{\Omega_{\alpha}(\xi_{1},\eta_{1},\xi_{2},\eta_{2})}.$

We split $u_{2}$ into three parts:

$u_{2}(x,y,t)=c(f_{1}(x,y,t)+f_{2}(x,y,t)+f_{3}(x,y,t)),$

where

$\begin{split}f_{1}(x,y,t)&=\frac{c}{|D_{1}|}\int_{\begin{subarray}{c}{(\xi_{1},\eta_{1})\in
D_{1}}\\\ {(\xi_{2},\eta_{2})\in
D_{1}}\end{subarray}}\Phi(x,y,t,\xi_{1},\eta_{1},\xi_{2},\eta_{2})d\xi_{1}d\eta_{1}d\xi_{2}d\eta_{2},\\\
f_{2}(x,y,t)&=\frac{c}{|D_{2}|N^{2(s_{1}+(1+\frac{\alpha}{2})s_{2})}}\int_{\begin{subarray}{c}{(\xi_{1},\eta_{1})\in
D_{2}}\\\ {(\xi_{2},\eta_{2})\in
D_{2}}\end{subarray}}\Phi(x,y,t,\xi_{1},\eta_{1},\xi_{2},\eta_{2})d\xi_{1}d\eta_{1}d\xi_{2}d\eta_{2},\\\
f_{3}(x,y,t)&=\frac{c}{|D_{1}|^{\frac{1}{2}}|D_{2}|^{\frac{1}{2}}N^{s_{1}+(1+\frac{\alpha}{2})s_{2}}}\Big{(}\int_{\begin{subarray}{c}{(\xi_{1},\eta_{1})\in
D_{1}}\\\ {(\xi_{2},\eta_{2})\in
D_{2}}\end{subarray}}+\int_{\begin{subarray}{c}{(\xi_{1},\eta_{1})\in
D_{2}}\\\ {(\xi_{2},\eta_{2})\in
D_{1}}\end{subarray}}\Big{)}\Phi(x,y,t,\xi_{1},\eta_{1},\xi_{2},\eta_{2})d\xi_{1}d\eta_{1}d\xi_{2}d\eta_{2}.\end{split}$

We focus on the high-low interaction viz. $f_{3}$. The spatial Fourier
transform of the same is given by

$\widehat{f_{3}}(\xi,\eta,t)=\frac{c\xi
e^{it(\xi|\xi|^{\alpha}+|\eta|^{2}/\xi)}}{|D_{1}|^{\frac{1}{2}}|D_{2}|^{\frac{1}{2}}N^{s_{1}+(1+\frac{\alpha}{2})s_{2}}}\Big{(}\int_{\begin{subarray}{c}{(\xi_{1},\eta_{1})\in
D_{1}}\\\ {(\xi_{2},\eta_{2})\in
D_{2}}\end{subarray}}+\int_{\begin{subarray}{c}{(\xi_{1},\eta_{1})\in
D_{2}}\\\ {(\xi_{2},\eta_{2})\in
D_{1}}\end{subarray}}\Big{)}\frac{e^{-it\Omega_{\alpha}(\xi_{1},\eta_{1},\xi_{2},\eta_{2})}-1}{\Omega_{\alpha}(\xi_{1},\eta_{1},\xi_{2},\eta_{2})}d\xi_{1}d\eta_{1}.$

Employing [16, Lemma 5], we have the following bound on the size of the
resonance function.

######  Lemma B.2 (Size of the resonance function).

Let $(\xi_{1},\eta_{1})\in D_{1},(\xi_{2},\eta_{2})\in D_{2}$ or
$(\xi_{1},\eta_{1})\in D_{1},(\xi_{2},\eta_{2})\in D_{2}$, then

$|\Omega_{\alpha}(\xi_{1},\eta_{1},\xi_{2}\,\eta_{2})|\lesssim
N^{\alpha-1}\beta^{2}.$

###### Proof.

We first note that we can relate the resonance functions in the two and three-
dimensional cases as follows:

$\Omega_{\alpha}^{3d}(\xi_{1},\eta_{1},\mu_{1},\xi_{2},\eta_{2},\mu_{2})=\Omega_{\alpha}^{2d}(\xi_{1},\eta_{1},\xi_{2},\eta_{2})-\frac{(\xi_{1}\mu_{2}-\xi_{2}\mu_{1})^{2}}{\xi_{1}\xi_{2}(\xi_{1}+\xi_{2})},$
(93)

where the notation is self explanatory. Consequently,

$|\Omega_{\alpha}^{3d}(\xi_{1},\eta_{1},\mu_{1},\xi_{2},\eta_{2},\mu_{2})|\lesssim\max\Big{(}|\Omega_{\alpha}^{2d}(\xi_{1},\eta_{1},\xi_{2},\eta_{2})|,\frac{(\xi_{1}\eta_{2}-\xi_{2}\eta_{1})^{2}}{|\xi_{1}\xi_{2}(\xi_{1}+\xi_{2})|}\Big{)}.$

From [18, Theorem 1.2], we have the following bound:

$|\Omega^{2d}_{\alpha}(\xi_{1},\eta_{1},\xi_{2},\eta_{2})|\lesssim
N^{\alpha-1}\beta^{2}.$

We bound the second term on the right-hand side of (93) as follows:

$\frac{(\xi_{1}\eta_{2}-\xi_{2}\eta_{1})^{2}}{|\xi_{1}\xi_{2}(\xi_{1}+\xi_{2}|}\lesssim\max\Big{(}\frac{|\xi_{1}\eta_{2}|^{2}}{|\xi_{1}\xi_{2}(\xi_{1}+\xi_{2})|},\frac{|\xi_{2}\eta_{1}|^{2}}{|\xi_{1}\xi_{2}(\xi_{1}+\xi_{2})|}\Big{)}\lesssim\max(\beta
N^{-1-2\delta},\beta^{4\delta}).$

We choose $\delta\ll 1$ so that

$|\Omega_{\alpha}^{3d}|\lesssim N^{\alpha-1}\beta^{2}.$ (94)

∎

We continue with the proof of Theorem B.1 and denote $\Omega_{\alpha}^{3d}$ by
$\Omega_{\alpha}$ as there is no confusion.

_Proof (ctd.)_ We choose $N,\beta,\delta$ such that $N^{\alpha-1}\beta^{2}\sim
N^{-\theta},$ i.e., $\beta\sim
N^{\frac{1}{2}-\frac{\alpha}{2}-\frac{\theta}{2}}$ and
$\delta=\frac{\theta}{2}$ for $0<\theta\ll 1$. Then,

$\Big{|}\frac{e^{it\Omega_{\alpha}(\xi_{1},\eta_{1},\xi_{1},\eta_{2})}-1}{\Omega_{\alpha}(\xi_{1},\eta_{1},\xi_{2},\eta_{2})}\Big{|}=|t|+O(N^{-\epsilon}).$

We calculate the $H^{\bar{s}}(\mathbb{R}^{3})$ norm of $f_{3}(t)$:

$\|f_{3}(\cdot,\cdot,t)\|_{H^{\bar{s}}(\mathbb{R}^{3})}\gtrsim
N\frac{|D_{1}|^{\frac{1}{2}}}{|D_{2}|^{\frac{1}{2}}}\beta^{\frac{3}{2}}N^{\frac{1}{4}-\frac{\delta}{2}}=N|D_{1}|^{\frac{1}{2}}.$
(95)

From (88), we have

$1\sim\|\phi\|_{H^{\bar{s}}(\mathbb{R}^{3})}^{2}\gtrsim
N\beta^{\frac{7}{4}+\delta}=N^{(\frac{15}{8}-\frac{7\alpha}{8})-},$

which is true only if $\alpha\geqslant\frac{15}{7}$. ∎

### Acknowledgment

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation) – Project-ID 317210226 – SFB 1283 (S.H.) and Project-ID –
258734477 – SFB 1173 (R.S.).

## References

  * [1] J. Bourgain.  Fourier transform restriction phenomena for certain lattice subsets and applications to nonlinear evolution equations. I. Schrödinger equations.  Geom. Funct. Anal., 3(2):107–156, 1993.
  * [2] D. Chiron and F. Rousset.  The KdV/KP-I limit of the nonlinear Schrödinger equation.  SIAM J. Math. Anal., 42(1):64–96, 2010.
  * [3] V. S. Dryuma.  Analytic solution of the two-dimensional Korteweg-de Vries (KdV) equation.  Sov. Phys. JETP Lett., 19:387, June 1974.
  * [4] L. Grafakos.  Multilinear operators in harmonic analysis and partial differential equations.  In Harmonic analysis and nonlinear partial differential equations, RIMS Kôkyûroku Bessatsu, B33, pages 11–27. Res. Inst. Math. Sci. (RIMS), Kyoto, 2012.
  * [5] L. Grafakos and R. H. Torres.  Multilinear Calderón-Zygmund theory.  Adv. Math., 165(1):124–164, 2002.
  * [6] Z. Guo and T. Oh.  Non-existence of solutions for the periodic cubic NLS below $L^{2}$.  Int. Math. Res. Not., 2018(6):1656–1729, 2018.
  * [7] M. Hadac, S. Herr, and H. Koch.  Well-posedness and scattering for the KP-II equation in a critical space.  Ann. Inst. H. Poincaré C Anal. Non Linéaire, 26(3):917–941, 2009.
  * [8] M. Hadac, S. Herr, and H. Koch.  Erratum to “Well-posedness and scattering for the KP-II equation in a critical space” [Ann. I. H. Poincaré—AN 26 (3) (2009) 917–941] [mr2526409].  Ann. Inst. H. Poincaré C Anal. Non Linéaire, 27(3):971–972, 2010.
  * [9] M. Ifrim and D. Tataru.  Local well-posedness for quasilinear problems: a primer.  arXiv e-prints, page arXiv:2008.05684, Aug. 2020.
  * [10] A. D. Ionescu, C. E. Kenig, and D. Tataru.  Global well-posedness of the KP-I initial-value problem in the energy space.  Invent. Math., 173(2):265–304, 2008.
  * [11] B. B. Kadomtsev and V. I. Petviashvili.  On the stability of solitary waves in weakly dispersing media.  Sov. Phys., Dokl., 15:539–541, 1970.
  * [12] C. Klein and J.-C. Saut.  Numerical study of blow up and stability of solutions of generalized Kadomtsev-Petviashvili equations.  J. Nonlinear Sci., 22(5):763–811, 2012.
  * [13] F. Linares, D. Pilod, and J.-C. Saut.  Dispersive perturbations of Burgers and hyperbolic equations I: Local theory.  SIAM J. Math. Anal., 46(2):1505–1537, 2014.
  * [14] J.-L. Lions.  Quelques méthodes de résolution des problèmes aux limites non linéaires.  Dunod, Paris; Gauthier-Villars, Paris, 1969.
  * [15] L. Molinet, J. C. Saut, and N. Tzvetkov.  Global well-posedness for the KP-I equation.  Math. Ann., 324(2):255–275, 2002.
  * [16] L. Molinet, J.-C. Saut, and N. Tzvetkov.  Well-posedness and ill-posedness results for the Kadomtsev-Petviashvili-I equation.  Duke Math. J., 115(2):353–384, 2002.
  * [17] L. Molinet, J. C. Saut, and N. Tzvetkov.  Global well-posedness for the KP-I equation on the background of a non-localized solution.  Comm. Math. Phys., 272(3):775–810, 2007.
  * [18] A. Sanwal and R. Schippa.  Low regularity well-posedness for KP-I equations: the dispersion generalised case.  Preprint, arXiv:2205.02037v2, 2022.
  * [19] R. Schippa.  Short-time Fourier transform restriction phenomena and applications to nonlinear dispersive equations.  2019\.
  * [20] H. Takaoka and N. Tzvetkov.  On 2D nonlinear Schrödinger equations with data on ${\mathbb{R}}\times\mathbb{T}$.  J. Funct. Anal., 182(2):427–442, 2001.
  * [21] T. Tao.  Global regularity of wave maps. II. Small energy in two dimensions.  Comm. Math. Phys., 224(2):443–544, 2001.
  * [22] T. Tao.  Nonlinear dispersive equations, volume 106 of CBMS Regional Conference Series in Mathematics.  Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2006.  Local and global analysis.