# A Polynomial-Time Algorithm for Special Cases of the Unbounded Subset-Sum
Problem

Majid Salimi<EMAIL_ADDRESS>Hamid Mala<EMAIL_ADDRESS>Faculty of
Computer Engineering, University of Isfahan, Isfahan, Iran

###### Abstract

The Unbounded Subset-Sum Problem (USSP) is defined as: given sum $s$ and a set
of integers $W\leftarrow\\{p_{1},\dots,p_{n}\\}$ output a set of non-negative
integers $\\{y_{1},\dots,y_{n}\\}$ such that $p_{1}y_{1}+\dots+p_{n}y_{n}=s$.
The USSP is an NP-complete problem that does not have any known polynomial-
time solution. There is a pseudo-polynomial algorithm for the USSP problem
with $O((p_{1})^{2}+n)$ time complexity and $O(p_{1})$ memory complexity,
where $p_{1}$ is the smallest element of $W$ [7]. This algorithm is polynomial
in term of the number of inputs, but exponential in the size of $p_{1}$.
Therefore, this solution is impractical for the large-scale problems.
In this paper, first we propose an efficient polynomial-time algorithm with
$O(n)$ computational complexity for solving the specific case of the USSP
where $s>\sum_{i=1}^{k-1}q_{i}q_{i+1}-q_{i}-q_{i+1}$, $q_{i}$’s are the
elements of a small subset of $W$ in which $gcd$ of its elements divides $s$
and $2\leq k\leq n$. Second, we present another algorithm for smaller values
of $s$ with $O(n^{2})$ computational complexity that finds the answer for some
inputs with a probability between $0.5$ to $1$. Its success probability is
directly related to the number of subsets of $W$ in which $gcd$ of their
elements divides $s$. This algorithm can solve the USSP problem with large
inputs in the polynomial-time, no matter how big inputs are, but, in some
special cases where $s$ is small, it cannot find the answer.

###### keywords:

Subset-Sum Problem, NP-complete, Pseudo-polynomial algorithm.

††journal: Discrete Applied Mathematics

##  1 Introduction

The Subset-Sum Problem (SSP) is a well-known NP-complete problem which is
defined as: given a set of positive integers
$W\leftarrow\\{p_{1},\dots,p_{n}\\}$ and a positive integer $s$ compute the
set of boolean numbers $\\{y_{1},\dots,y_{n}\\}$ such that
$p_{1}y_{1}+\dots+p_{n}y_{n}=s$.

######  Definition 1.1

(Subset-Sum Problem (SSP)). Let $W\leftarrow\\{p_{1},p_{2},\dots,p_{n}\\}$ be
a set of $n$ positive random integers. The SSP is the problem of finding a
subset of $W$, where the sum of its members is equal to a given value $s$.

Until now there exists no polynomial-time solution for the SSP, but there
exist some pseudo-polynomial algorithms which can solve special instances of
the SSP with small inputs. The complexity of the best possible solutions of
the SSP are equal to $O(2^{n/2})$ [8], $O(s\sqrt{n})$ [9] and $O(nc)$ [13],
where $c$ is the size of the largest element of $W$. In 2014, Cygan et al.
showed that the SSP cannot be computed in time $s^{\epsilon}poly(n)$ under the
Set Cover Hypothesis, where $\epsilon<1$ [4]. A variant of the SSP is the
unbounded subset sum problem which is defined in Definition 1.2.

######  Definition 1.2

(Unbounded Subset-Sum Problem (USSP)). Consider a set
$W\leftarrow\\{p_{1},p_{2},\dots,p_{n}\\}$ of $n$ random positive integers.
Given a non-negative integer $s$, the USSP is the problem of finding the set
of non-negative integers $\\{y_{1},\dots,y_{n}\\}$ such that
$s=\sum_{i=1}^{n}y_{i}p_{i}$, where $p_{1}<p_{2}<\dots<p_{n}$. Note that there
is no condition on non-negative integers $y_{i}$’s (i.e. they can be zero or
any positive integer). We use the notation $n-$USSP to explicitly indicate
that the size of $W$ is $n$.

The USSP is an NP-complete problem and the best known solution for it is a
pseudo-polynomial-time algorithm with time complexity $O((p_{1})^{2}+n)$ and
memory complexity $O(p_{1})$, where $p_{1}$ is the smallest element of $W$
[7]. This solution is exponential in term of the magnitude of the input and
polynomial in the size of the input. There is a reduction from the USSP to
SSP, and the SSP problem is itself reducible to the partitioning problem [10],
which is partitioning a given set of positive integers $W$ into two subsets
$W_{1}$ and $W_{2}$ such that the sum of the elements of $W_{1}$ equals the
sum of the elements in $W_{2}$. The reduction of USSP to SSP of [10] is not
correct since by transforming an instance of the SSP problem to an instance of
the USSP problem the set of possible answers dramatically increases. Note that
most of the answers of the transformed USSP problem do not work for the source
SSP problem. If we want to compute the answer of the USSP problem which works
for SSP too, we need to add some constraints. These constraints make the USSP
problem the constraint satisfaction problem, which is NP-complete.
The USSP can be considered as a special case of Unbounded Knapsack Problem
(UKP), where the weight and the value of elements is equal. The only
difference is that in USSP the amount of $\sum_{i=1}^{n}y_{i}p_{i}$ must be
exactly equal to $s$, but in the UKP it can be equal to or less than $s$.
Kellerer et al. described the UKP problem in Chapter Eight of Knapsack
Problems [UKP].

###  1.1 Our Contribution

In this paper, we propose two versions of an algorithm for solving the USSP
problem with various conditions on $s$. By using these two algorithms, we can
solve many instances of USSP with large values of $n$ and $s$.

  * 1.

Algorithm 3 solves the USSP for $s>\sum_{i=1}^{k-1}q_{i}q_{i+1}-q_{i}-q_{i+1}$
with $O(n)$ computational complexity, where $q_{i}$’s are the elements of a
small subset of $W$ that the $gcd$ of its elements divides $s$.

  * 2.

Algorithm 4 is a deterministic algorithm which can compute the answer of the
USSP with probability between $0.5$ to $1$ for $p_{1}\leq
s\leq\sum_{i=1}^{k-1}q_{i}q_{i+1}-q_{i}-q_{i+1}$. Its success probability is
directly related to the number of subsets of $W$, in which $gcd$ of its
elements divides $s$ (i.e. If the set $W$ contains a large number of prime
integers, this probability will be close to one). Anyway, the USSP with small
$n$ and $s$ does not have large space and can be solved by brute force
algorithms.

Table 1: Brief Review of the Proposed Algorithms

Algorithm |  Complexity |  $s$ |  Probability
---|---|---|---
Algorithm 3 |  $O(n)$ |  $s>z_{1}$ ∗ |  1
Algorithm 4 |  $O(n^{2})$ |  $s\leq z_{1}$ |  $1-x$ ∗∗

∗ $z_{1}\leftarrow\sum_{i=1}^{k-1}q_{i}q_{i+1}-q_{i}-q_{i+1}$, where $q_{i}$’s
are the elements of a small subset of $W$ in which $gcd$ of its elements
divides $s$.

∗∗ $x\leftarrow\prod_{i=1}^{i=f}(1-(\frac{z_{1}}{2z_{i}}))$, where $1\leq f<n$
is the number of subsets of $W$ in which $gcd$ of their elements divides $s$
and Algorithm 4 can find them.

###  1.2 Paper Organization

The rest of this paper is organized as follows. In Section 2, the related work
are discussed. In Section 3, $2$-USSP problem is examined. An algorithm for
the USSP with large values of $s$ is presented in Section 4. In Section 5, an
algorithm for handling small values of $s$ is proposed. Finally, the paper is
concluded in Section 6.

##  2 Related Work

In 1996, Alfonsin proposed another variation of the SSP called Subset-sum with
Repetitions Problem (SRP): given positive integers $s$, $r_{1},\dots,r_{n}$
and an increasing set of coprime integers $W\leftarrow\\{p_{1},\dots,p_{n}\\}$
there exist positive integers $y_{i}$, $y_{i}\leq r_{i}$ such that
$y_{1}p_{1}+\dots+y_{n}p_{n}=s$ [1]. He stated that the SRP problem is NP-
complete even if $W$ is a super-increasing set and $r_{i}\leftarrow 0,1$ for
all $i$. He also found a polynomial algorithm for the special case where the
set $W\leftarrow\\{p_{1},\dots,p_{n}\\}$ is a chain sequence. It means that
$p_{i}|p_{i+1}$. Anyway their approach was not universal [1].
In 1996, Hansen and Ryan proposed an algorithm with time complexity
$O((p_{1})^{2}+n)$ and memory complexity $O(p_{1})$ for the USSP problem [7],
where $W\leftarrow\\{p_{1},\dots,p_{n}\\}$ are coprime integers. In 2009,
Muntean and Oltean proposed an optical solution to the problem of whether an
instance of the USSP has an answer or not [11]. In 2017, Bringmann showed that
the USSP problem can be solved in $O(s\log s)$ [3]. In 2018, Wojtczak showed
that the unbounded subset-sum problem with rational numbers is strongly NP-
complete. In other words, no pseudo-polynomial algorithm can exist for solving
USSP with rational numbers unless P=NP [15].
Another variant of this problem is to decide whether an instance of the USSP
has a solution or not. This is a YES/NO problem and it is also an NP-complete
problem [11]. More than one hundred years ago, Ferdinand Georg Frobenius
introduced the Frobenius number as defined in Definition 2.1.

######  Definition 2.1

(Frobenius number). Let $W\leftarrow\\{p_{1},\dots,p_{n}\\}$ be a set of
coprime positive integers, where $p_{1}<p_{2}<\dots<p_{n}$. The greatest
integer which cannot be expressed as a linear combination (with nonnegative
integer coefficients) of elements of $W$ is called the Frobenius number
$f(p_{1},\dots,p_{n})$.

Computing the Frobenius number for $n=2$ is an easy problem and it is equal to
$f(p_{1},p_{2})=p_{1}p_{2}-p_{1}-p_{2}$ [14], [6]. Furthermore, Sylvester
showed that half of integers $0,1\dots,p_{1}p_{2}-p_{1}-p_{2}$ are not
representable by any linear combination of $p_{1}$ and $p_{2}$ [14]. In 1994,
Davison proposed a quadratic-time algorithm for computing the Frobenius number
for $n=3$ [5]. The problem of finding the Frobenius number for $n>2$ is an NP-
hard problem and the time complexity of the best solution for it is equal to
$O(p_{1}\sqrt{n})$ [2]. The upper bound of Frobenius number for $n>2$ is equal
to $f(p_{1},\dots,p_{n})\leq p_{1}(p_{n}-1)-p_{n}$ [2].

##  3 Preliminaries

First we focus on the 2-USSP, which denotes the USSP with $n=2$ and
$W\leftarrow\\{p_{1},p_{2}\\}$. In Theorem 3.1 we obtain the answers of the
USSP equation $y_{1}p_{1}+y_{2}p_{2}=s$ for any adequately large random
integer $s$.

######  Theorem 3.1

Let $p_{1}$ and $p_{2}$ be non-negative integers, where $p_{1}<p_{2}$ and
$gcd(p_{1},p_{2})=1$, then the equation $y_{1}p_{1}+y_{2}p_{2}=s$ has
$l\leftarrow\big{\lfloor}\frac{s-p_{1}(sp_{1}^{-1}\bmod
p_{2})}{p_{1}p_{2}}\big{\rfloor}+1$ answers $(y_{1},y_{2})$. Moreover, if
$s>p_{1}(p_{2}-1)-p_{2}$, then the equation $y_{1}p_{1}+y_{2}p_{2}=s$ has at
least one answer $(y_{1},y_{2})$.

###### Proof.

Let we rewrite the equation $y_{1}p_{1}+y_{2}p_{2}=s$ in modulo $p_{2}$. We
have $p_{1}y_{1}\bmod p_{2}=s\bmod p_{2}$. Hence, we can compute an answer for
$y_{1}$ as $y_{1}^{*}=sp_{1}^{-1}\bmod p_{2}$ (the largest possible value for
$y_{1}^{*}$ is $p_{2}-1$). With this value for $y_{1}$ and any other integer
value for $y_{2}$, the USSP equation $y_{1}p_{1}+y_{2}p_{2}=s$ is satisfied
modulo $p_{2}$. The value $y_{2}^{*}=\frac{s-p_{1}y_{1}^{*}}{p_{2}}$ omits the
modulo if it is a non-negative integer. So, with this values for $y_{1}$ and
$y_{2}$ the equation $y_{1}p_{1}+y_{2}p_{2}=s$ is satisfied (without modulo
$p_{2}$). In fact if the equation $y_{1}p_{1}+y_{2}p_{2}=s$ has at least one
answer, then $y_{2}^{*}=\frac{s-p_{1}y_{1}^{*}}{p_{2}}$ is an integer.
Consequently, the only condition that must be held is that $y_{2}^{*}$ should
be non-negative. The largest possible value of $y_{1}$ is equal to $p_{2}-1$,
so the Frobenius number that is the possible largest value of $s$ for which
the equation $y_{1}p_{1}+y_{2}p_{2}=s$ has no answer, is computed by
considering $y_{2}^{*}=-1$ as below.

$\displaystyle\frac{s-p_{1}y_{1}^{*}}{p_{2}}$ $\displaystyle=-1$
$\displaystyle\Rightarrow s$ $\displaystyle=p_{1}y_{1}^{*}-p_{2}$ (1)

As the maximum possible value for $y_{1}^{*}$ is $p_{2}-1$, the maximum
possible value for $s$ is obtained as below.

$s=p_{1}(p_{2}-1)-p_{2}$ (2)

So the lower bound of $s$ is $p_{1}p_{2}-p_{1}-p_{2}$ in the sense that for
any integer $s>p_{1}p_{2}-p_{1}-p_{2}$, the equation $p_{1}y_{1}+p_{2}y_{2}=s$
has at least one non-negative answer. If $s\leq p_{1}p_{2}-p_{1}-p_{2}$, then
there may be no valid positive value for $y_{2}$ and the value of $y_{2}$ may
be negative.

Now suppose $(y^{*}_{1},y^{*}_{2})$ is an answer for the USSP equation
$y_{1}p_{1}+y_{2}p_{2}=s$. Then one can easily check that
$(y^{*}_{1}+p_{2},y^{*}_{2}-p_{1})$ is also an answer for this equation if
$y^{*}_{2}-p_{1}$ is still non-negative. This condition is equivalent to
$s\geq(y^{*}_{1}+p_{2})p_{1}$. As the extension we can say
$(y_{1}^{*}+(l-1)p_{2},y_{2}^{*}-(l-1)p_{1})$ is also an answer to the USSP
equation if $y^{*}_{2}-(l-1)p_{1}\geq 0$. Now suppose $y_{2}^{*}-lp_{1}<0$.
Then, the value of $(y^{*}_{1},y^{*}_{2})$, as a seed, defines a coset of $l$
valid values for $y_{1}$ and $y_{2}$ as

$\displaystyle\\{(y_{1}^{*},y_{2}^{*}),(y_{1}^{*}+p_{2},y_{2}^{*}-p_{1}),\dots,(y_{1}^{*}+(l-1)p_{2},y_{2}^{*}-(l-1)p_{1})\\}$
(3)

The value of $y_{2}$ must be non-negative, so the value of $l$ is obtained as
below.

$\displaystyle y^{*}_{2}-(l-1)p_{1}\geq 0$ (4) $\displaystyle\Rightarrow
l-1=\bigg{\lfloor}\frac{y^{*}_{2}}{p_{1}}\bigg{\rfloor}=\bigg{\lfloor}\frac{s-p_{1}y_{1}^{*}}{p_{1}p_{2}}\bigg{\rfloor}$
(5) $\displaystyle\Rightarrow
l=\bigg{\lfloor}\frac{s-p_{1}y_{1}^{*}}{p_{1}p_{2}}\bigg{\rfloor}+1$ (6)

Note that if $gcd(p_{1},p_{2})=e$, then the equation $y_{1}p_{1}+y_{2}p_{2}=s$
has answer if $e|s$. If $gcd(p_{1},p_{2})=e\neq 1$ and $e|s$ then
$p_{1}^{-1}\bmod p_{2}$ does not exist, so the value $sp_{1}^{-1}\bmod p_{2}$
cannot be computed. In such cases we can easily replace $p_{1},p_{2}$ and $s$
by $\frac{p_{1}}{e},\frac{p_{2}}{e}$ and $\frac{s}{e}$ in the
$sp_{1}^{-1}\bmod p_{2}$. The answers will satisfy the original instance of
the USSP. Note that if $gcd(p_{1},p_{2})=e\neq 1$ and $e\not|s$ then the
equation does not have answer at all. ∎

In 1884, Sylvester showed that half on integers $0\leq s\leq
p_{1}p_{2}-p_{1}-p_{2}$ cannot be expressed by linear combination of $p_{1}$
and $p_{2}$ by non-negative coefficients.

######  Theorem 3.2

(Sylvester Theorem.) Let $z=p_{1}p_{2}-p_{1}-p_{2}$. Exactly half of the
integer values $s$ in the interval $0\leq s\leq z$ can be represented by
linear combination of $p_{1}$ and $p_{2}$ with non-negative coefficients. The
following set include these numbers [14].

$\displaystyle\\{$ $\displaystyle
0p_{2}+0p_{1},0p_{2}+p_{1},\dots,0p_{2}+\lfloor\frac{z}{p_{1}}\rfloor p_{1},$
$\displaystyle
p_{2}+0p_{1},p_{2}+p_{1},\dots,p_{2}+\lfloor\frac{z-p_{2}}{p_{1}}\rfloor
p_{1},$ $\displaystyle\lfloor\frac{z}{p_{2}}\rfloor p_{2}+0p_{1}\\}$ (7)

In other words, any non-negative integer $z-ip_{1}-jp_{2}$ for
$i\in\\{1,\dots,p_{2}-1\\}$ and $j\in\\{1,\dots,i\\}$ is not representable by
linear combination of $p_{1}$ and $p_{2}$ with non-negative coefficients.

In Theorem 3.3, we show that exactly
$\lceil\frac{s}{p_{1}}\rceil+\sum_{i=0}^{k}\lfloor\frac{s-ip_{1}}{p_{2}}\rfloor$
of integers between $0\leq r\leq s$, $s\leq p1p2-p1-p2$ can be expressed by
linear combination of $p_{1}$ and $p_{2}$ with non-negative coefficients.

######  Theorem 3.3

Let $z=p_{1}p_{2}-p_{1}-p_{2}$, then for any integer $s$ smaller than $z$, the
$\lceil\frac{s}{p_{1}}\rceil+\sum_{i=0}^{k}\lfloor\frac{s-ip_{1}}{p_{2}}\rfloor$
integers in the interval $0\leq r\leq s$ can be expressed by linear
combination of $p_{1}$ and $p_{2}$ with non-negative coefficients.

###### Proof.

Let’s partition $\\{0,\dots,z\\}$ into $k=\lceil\frac{z}{p_{1}}\rceil$ sets
$\\{ip_{1},\dots,(i+1)p_{1}-1\\}$, for $i\in\\{0,\dots,k\\}$, (Ignore the lack
of the last set.). One can easily check that the integers $r_{1}=ip_{1}$ and
$r_{2}=jp_{2}$ will be in $ip_{1}\leq r_{1}<(i+1)p_{1}$ and $xp_{1}\leq
r_{2}<(x+1)p_{1}$ respectively, for $j\in\\{0,\dots,\lfloor
z/p_{2}\rfloor\\}$, where $x=\lfloor\frac{jp_{2}}{p_{1}}\rfloor$. Let
$e=jp_{2}\bmod p_{1}$, then $e$’th element of any interval $\acute{i}\geq x+i$
can be expressed by $jp_{2}+ip_{1}$, for $i\in\\{0,\dots,k\\}$. As a result,
for integers $ip_{1}\leq r<(i+1)p_{1}$, the integer $ip_{1}$ plus another
$\lfloor\frac{(i+1)p_{1}-1}{p_{2}}\rfloor$ integers can be expressed by
$p_{1}$ and $p_{2}$. Let $s\in\\{0,\dots,z\\}$ then
$\lceil\frac{s}{p_{1}}\rceil+\sum_{i=0}^{k}\lfloor\frac{s-ip_{1}}{p_{2}}\rfloor$
integers $0\leq r\leq s$ can be represented by linear combination of $p_{1}$
and $p_{2}$.
As observed, the number of integers which can be expressed by linear
combination of $p_{1}$ and $p_{2}$ grows linearly with approaching $s$ to $z$.
So, the percentage of $2-$USSP instances $y_{1}p_{1}+y_{2}p_{2}=r$, for
$r=\\{0,1,2,\dots,s\\}$, $s\leq z$ is approximated by $\frac{s}{2z}$. ∎

Based on Theorem 3.1, we define $A2(s,p_{1},p_{2})=y_{1}$ as an algorithm
which computes the 2-USSP with time and memory complexity $O(1)$. The
$A2(s,p_{1},p_{2})=y_{1}^{*}$ works as shown in Algorithm A2.

Input: $s,W=\\{p_{1},p_{2}\\}$

Output: $y_{1}^{*}$

$e=gcd(p_{1},p_{2})$

if  _$gcd(p_{1},p_{2})\not|s$_ then

Return($\bot$)

else

$s\leftarrow s/e$

$p_{1}\leftarrow p_{1}/e$

$p_{2}\leftarrow p_{2}/e$

$y_{1}^{*}=sp_{1}^{-1}\bmod p_{2}$

Return$(y_{1}^{*})$

end if

Algorithm 1 The algorithm $A2(s,p_{1},p_{2}$)

##  4 Unbounded Subset-Sum Problem

Assume $W=\\{p_{1},\dots,p_{n}\\}$ such that for $j=\\{1,\dots,n-1\\}$ we have
$p_{j+1}>p_{j}$, that is, $W$ is sorted in ascending order. The USSP can be
solved just by invoking the $A2(s,p_{1},p_{2})$ algorithm as follows:

$\displaystyle s_{1}$ $\displaystyle=s$ (8) $\displaystyle y_{1}$
$\displaystyle=A2(s_{1},p_{1},p_{2})$ (9) $\displaystyle s_{2}$
$\displaystyle=s_{1}-y_{1}p_{1}$ (10) $\displaystyle y_{2}$
$\displaystyle=A2(s_{2},p_{2},p_{3})$ (11) $\displaystyle y_{n-1}$
$\displaystyle=A2(s_{n-1},p_{n-1},p_{n})$ (12) $\displaystyle s_{n}$
$\displaystyle=s_{n-1}-y_{n-1}p_{n-1}$ (13) $\displaystyle y_{n}$
$\displaystyle=s_{n}/p_{n}$ (14)

Some one may says there is no need for equations (11)-(14); it can stop at
$s_{2}$ because $p_{2}|s_{2}$, so we have a solution as long as $s_{2}>0$. But
its not true, because a correct solution is the one that picks from all
elements of $W$ not just two of them. The algorithm $A2(s,p_{1},p_{2})$ works
only if $gcd(p_{1},p_{2}$)$|s$ and $s>p_{1}(sp_{1}^{-1}\bmod p_{2})$. These
conditions must be met just for the first pair ($p_{1},p_{2}$). Because, if
$gcd(p_{1},p_{2})|s$, then we have $gcd(p_{2},p_{3})|p_{2}|s_{2}$ and as an
extension we can say that $gcd(p_{i},p_{i+1})|s_{i}$. We have $n-1$ equations

$\displaystyle s$ $\displaystyle=s_{2}+y_{1}p_{1}$ (15) $\displaystyle s_{2}$
$\displaystyle=s_{3}+y_{2}p_{2}$ (16) $\displaystyle s_{n-1}$
$\displaystyle=y_{n}p_{n}+y_{n-1}p_{n-1}$ (17)

Then we have

$\displaystyle s+s_{2}+\dots+s_{n-1}$
$\displaystyle=y_{1}p_{1}+\dots+y_{n}p_{n}+s_{2}+\dots+s_{n-1}$
$\displaystyle\Rightarrow s$ $\displaystyle=y_{1}p_{1}+\dots+y_{n}p_{n}$ (18)

As observed just by using A2 algorithm the USSP problem can be solved only if
the greatest common divisor of the two smallest elements of $W$ divides $s$.
To overcome this limitation, we propose an efficient algorithm denoted by
Algorithm 3 with $O(n)$ computational complexity. This algorithm just needs
$gcd(p_{1},\dots,p_{n})|s$. Let $W_{1}$ be a small subset of $W$, where $gcd$
of its elements divides $s$, then, in the first step, the Algorithm 2 finds
$W_{1}$, and second, Algorithm 3 solves the USSP problem for $W_{1}$ and $s$,
and in the final step, it solves the USSP problem for other elements of $W$.
The Algorithm 2 and 3 works as follows.

Input: $s,W=\\{p_{1},\dots,p_{n}\\}$

Output:  A small subgroup of $W$, where $gcd$ of its elements divides $s$, or
$\bot$

if  _$gcd(p_{1},\dots,p_{n})\not|s$_ then

Return$(\bot)$

end if

$q_{1},\dots,q_{n}=0$

$k=0$

for  _$i=n\ to\ 1$_ do

if  _$gcd(q_{1},\dots,q_{k},W-\\{p_{i}\\})\not|s$_ then

$k\leftarrow k+1$

$q_{k}=p_{i}$ % Element of $W_{1}$.

end if

$W\leftarrow W-\\{p_{i}\\}$ % Delete $p_{i}$ from $W$.

if  _$gcd(q_{1},\dots,q_{k})|s$_ then

$break$

end if

end for

Return $(W_{1}=\\{q_{k},\dots,q_{1}\\})$

Algorithm 2 Finding a small subset of $W$, where $gcd$ of its elements divides
$s$.

The idea of Algorithm 3 is that we choose $y_{i}$ such that
$gcd(q_{2},\dots,q_{k})$ divides $s-y_{i}p_{i}$, where $p_{i}=q_{1}$. As a
result, the size of $W_{1}$ can be reduced to 2, and then, by running
$A2(s,q_{k-1},q_{k})$ the USSP can be solved. As observed, the Algorithm 3
works for any integer bigger than
$q_{k-1}q_{k}-q_{k}-q_{k-1}+\sum_{i=1}^{k-1}q_{i}x_{i}-q_{i}-x_{i}$, where
$x_{i}=gcd(q_{i},\dots,q_{k})$. In the worst case, $x_{i}=q_{i+1}$, so, in the
worst case, the Algorithm 3 works for any integer bigger that
$z_{1}=\sum_{i=1}^{k-1}q_{i}q_{i+1}-q_{i}-q_{i+1}$.

Input: $s,W=\\{p_{1},\dots,p_{n}\\}$

Output: $(y_{1},\dots,y_{n})$ such that $p_{1}y_{1}+\dots+p_{n}y_{n}=s$ or
$\bot$

$W_{1}$=$\\{q_{1},\dots,q_{k}\\}$=Algorithm2($s,W=\\{p_{1},\dots,p_{n}\\}$)

$y_{1},\dots,y_{n}=-1$

for  _$i=1\ to\ k-1$_ do

for  _$j=1\ to\ n$_ do

if  _$p_{j}=q_{i}$_ then

$break$ % Find $q_{i}$ in $W$.

end if

end for

if  _$i <k-1$_ then

$x=gcd(q_{i+1},\dots,q_{k})$

else

$x=q_{k}$

end if

if  _$s <p_{j}(sp_{j}^{-1}\bmod x)$_ then

Return($\bot$) % $s$ is too small

end if

$y_{j}=A2(s,p_{j},x)$ % Solving the USSP for elements of $W_{1}$.

$s\leftarrow s-p_{j}y_{j}$ % Now $gcd$ of $W_{1}-\\{q_{i}\\}$ divides $s$

end for

% Now $q_{k}$ divides $s$.

for  _$j=1\ to\ n$_ do

if  _$p_{j}=q_{k}$_ then

$break$ % Find $q_{k}$ in $W$.

end if

end for

for  _$i=j+1\ to\ n$_ do

if  _$s\geq p_{j}(sp_{j}^{-1}\bmod p_{i})$_ then

$y_{j}=A2(s,p_{j},p_{i})$

$s\leftarrow s-p_{j}y_{j}$ % Solving the problem for the rest of elements of
$W$.

$j=i$

else

end if

$y_{i}=0$

end for

% Now $s$ is a multiple of $p_{j}$, where $j\leq n$.

for  _$i=1\ to\ j-1$_ do

if  _$y_{i}=-1$_ then

if  _$s\geq p_{j}p_{i}$_ then

$y_{i}=p_{j}$

$s\leftarrow s-p_{i}y_{i}$ % $s$ still is a multiple of $p_{j}$

else

$y_{i}=0$

end if

end if

end for

if  _$s=0$_ then

$y_{j}=0$

else

$y_{j}=s/p_{j}$

end if

Return$(y_{1},\dots,y_{n})$

Algorithm 3 The proposed algorithm for solving the USSP

##  5  An Algorithm for the USSP with Small $s$

Let elements of $W$ be independent random integers uniformly chosen from
$\\{2,3,\dots,s\\}$ and
$s\in\\{p_{1},p_{1}+1,\dots,\sum_{i=1}^{k-1}q_{i}q_{i+1}-q_{i}-q_{i+1}\\}$ be
a uniform random integer, then the USSP problem can be solved with probability
more than $0.5$ by Algorithm 3, if there is a subgroup
$W_{1}=\\{q_{1},\dots,q_{k}\\}$, in which the $gcd$ of its elements divides
$s$. The Algorithm 4 can improve the success probability by calling Algorithm
3 with another subset $W_{2}$ (if there exists any), in which $gcd$ of its
elements divides $s$. The success probability of running Algorithm 3 with two
different subsets can be increased up to $0.5+0.5*0.5=0.75$. As observed, the
success probability increases logarithmically, from $0.5$ to less than one,
with increasing the number of subgroups of $W$ in which $gcd$ of their
elements divides $s$. The Algorithm 4 succeeds with high probability if the
input is given at random and $n$ is a large integer (i.e. it does not work for
all inputs).
Note that, if the elements of $W$ are not independent then the number of
subsets, in which $gcd$ of its elements divides $s$, decreases. As a result,
the success probability of this algorithm decreases too, but it never falls
less than $0.5$.

Input: $s,W=\\{p_{1},\dots,p_{n}\\}$

Output: $(y_{1},\dots,y_{n})$ or $\bot$

for  _$i=1\ to\ n$_ do

$W_{1}=q_{1},\dots,q_{k}$=Algorithm2($s,W=\\{p_{1},\dots,p_{n}\\}$)

if  _Algorithm3( $s,W_{1}=\\{q_{1},\dots,q_{k}\\}$)=$\bot$_ then

for  _$j=1\ to\ n$_ do

if  _$p_{j}=q_{1}$_ then

$break$ % Find $q_{1}$ in $W$.

end if

end for

$W\leftarrow W-\\{p_{j}\\}$

else

$x_{1},\dots,x_{k}$=Algorithm3($s,W_{1}=\\{q_{1},\dots,q_{k}\\}$)

$i=1$

for  _$j=1\ to\ n$_ do

if  _$q_{i}=p_{j}$_ then

$y_{j}=x_{i}$

$i=i+1$

else

$y_{j}=0$

end if

end for

Return$(y_{1},\dots,y_{n})$

end if

end for

Return($(\bot)$)

Algorithm 4 The proposed algorithm for solving USSP with small values of $s$

As observed, Algorithm 4 can find at most $n-1$ subsets of $W$ (if exists.),
in which $gcd$ of their elements divides $s$. The success probability can be
at most $1-{\frac{1}{2}}^{n-1}$, but the size of these subsets are different
and therefore they have also different thresholds in Algorithm 3. So, to
compute the success probability of Algorithm 4, we have to estimate the
percentage of the integers $0\leq s\leq z_{1}$ which can be expressed by
linear combination of elements of other $n-2$ subgroups.
Let $W_{2}$ be another small subgroup of $W$ in which $gcd$ of its elements
divides $s$, then, $50\%$ of integers $0\leq s\leq z_{2}$ can be represented
by linear combination of elements of $W_{2}$, and based on Theorem 3.3, about
$\frac{z_{1}}{2z_{2}}$ of integers $\\{0,\dots,z_{1}\\}$ can be expressed by
linear combination of elements of $W_{2}$. Let $1\leq f<n$ be the number of
subsets of $W$, in which $gcd$ of their elements divides $s$, then, we can
estimate the number of integers $0\leq s\leq z_{1}$ which cannot be expressed
by the linear combination of elements of $W$ as below.

$\displaystyle P_{Fail}=\prod_{i=1}^{i=f}(1-(\frac{z_{1}}{2z_{i}}))$ (19)

We can say that the Algorithm 4 works for any integer $0\leq s\leq z_{1}$ with
probability equal to

$\displaystyle P_{Success}$
$\displaystyle=1-\prod_{i=1}^{i=f}(1-(\frac{z_{1}}{2z_{i}}))$ (20)

Note that, no matter how much the value of $n$ goes up, for the integers
$0<s<p_{1}$ the USSP instance does not have answer. So, it is notable to
consider $P_{Success}$ as the probability that the integers $p_{1}\leq s\leq
z_{1}$ has an answer in USSP problem.

######  Example 5.1

Let $W=\\{11,13,15,19,21\\}$. So $p_{1}=11$ and $z_{1,2}=119$, then the
Algorithm 4 can solve $85$ percent of USSP problem, where $p_{1}\leq s\leq
z_{1}$, and almost all of this $15$ percentage lies in $p_{1}\leq
s\leq\frac{z_{1}}{2}$. We show that our estimation is equal to $80$ percent.

$\displaystyle\frac{z_{1}}{2z_{1}}=\frac{119}{238}=0.5$
$\displaystyle\frac{z_{1}}{2z_{2}}=\frac{119}{334}=0.35$
$\displaystyle\frac{z_{1}}{2z_{3}}=\frac{119}{418}=0.28$
$\displaystyle\frac{z_{1}}{2z_{4}}=\frac{119}{718}=0.16$ $\displaystyle
P_{Success}=1-\prod_{i=1}^{i=f}(1-(\frac{z_{i}}{2z_{1}}))$
$\displaystyle=1-(1-0.5)\times(1-0.35)\times(1-0.28)\times(1-0.16)$
$\displaystyle\cong 0.80$ (21)

##  6 Conclusion

The unbounded subset-sum problem is a well-known and well-studied NP-complete
problem and there is a formal reduction from USSP to SSP. The USSP problem
does not have any known polynomial solution. In this paper, we proposed two
efficient polynomial-time algorithms for solving the special cases of the USSP
problem with different conditions on $s$. The Algorithm 3 solves the USSP for
$s>\sum_{i=1}^{k-1}q_{i}q_{i+1}-q_{i}-q_{i+1}$ with $O(n)$ computational
complexity, where $q_{i}$’s are the elements of small subset of $W$ in which
$gcd$ of its elements divides $s$. Algorithm 4 is dedicated for smaller values
of $s$, where only several exceptions happen for some values of $s$ in the
interval $p_{1}\leq s\leq\sum_{i=1}^{k-1}q_{i}q_{i+1}-q_{i}-q_{i+1}$ in the
sense that the USSP instance may have an answer but our algorithm fails to
find it. We estimated the probability of this failure and noticed it decreases
to zero by a small increase of $n$. The complexity of our algorithm is
$O(n^{2})$.

## References

  * [1] R. Alfonsin. On variations of the subset sum problem. Discrete Applied Mathematics, 81, pp. 1-7, 1998.
  * [2] D. Beihoffer, J. Hendry, A. Nijenhuis and S. Wagon. Faster Algorithms for Frobenius Numbers. journal of combinatorics 12\. pp. 1-38. 2005.
  * [3] K. Bringmann. A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. pp.1-12. 2017.
  * [4] M. Cygan, H. Dell, D. Lokshtanov, D. Marx and J. Nederlofk et al.“On problems as hard as CNF-SAT. In Transactions on Algorithms, 12(3), Article 41. 2016.
  * [5] J. L. Davison. On the linear diophantine problem of Frobenius, J. Number Theory, 48\. pp. 353-363. 1994.
  * [6] R. Guy. Unsolved Problems in Number Theory, Springer-Verlag New York. ISBN: 978-0-387-20860-2. pp. 172. 2004.
  * [7] P. Hansen and J. Ryan. Testing integer knapsacks for feasibility. European Journal of Operational Research, 88, pp. 578-582. 1996.
  * [8] K. Koiliaris and C. Xu. ”A Faster Pseudopolynomial Time Algorithm for Subset Sum”. Preprint available at arxiv.org/abs/1507.02318. 2017.
  * [9] J. Kleinberg and V. Tardos. Algorithm Design (2nd ed.). p. 491. ISBN 0-321-37291-3. 2006.
  * [10] J. Kleinberg and É Tardos. Algorithm Design (2nd ed.). Addison-Wesley. ISBN 0-321-37291-3. 2006.
  * [11] O. Muntean. Optical solutions for the unbounded subset-sum problem. International Journal of Innovative Computing, Information and Control (IJICIC). 8(8). 2009. pp.2159-2167.
  * [12] D. Pisinger. ”Linear Time Algorithms for Knapsack Problems with Bounded Weights”. Journal of Algorithms, Volume 33(1), pp. 114, 1999.
  * [13] H. Kellerer, U. Pferschy, D. Pisinger. ”Knapsack Problems”. Springer, ISBN: 978-3-540-24777-7, 2004.
  * [14] J. Sylvester. Mathematical questions, with their solutions. Educational Times 41. pp. 21. 1884.
  * [15] D. Wojtczak. On Strong NP-Completeness of Rational Problems. In Computer Science – Theory and Applications. 2018.


$\displaystyle\leq\frac{\mathrm{polylog}\left(n\right)}{n}$

which finishes the proof for (177).

###  F.3 Proof of Claim 3

The independence follows directly from Assumption 6 and the null hypothesis
(18).

##### Proof of (185):

by independence, we have

$\displaystyle\mathbb{E}(X-\mu)\otimes\left(T_{Q^{*}}^{Q}-I_{d}\right)$
$\displaystyle=\left[\mathbb{E}(X-\mu)\right]\otimes\left[\mathbb{E}\left(T_{Q^{*}}^{Q}-I_{d}\right)\right]$
$\displaystyle=0$

##### Proof of (186):

The optimality condition of $Q^{*}(x)$ gives that

$\displaystyle\mathbb{E}s(x,X)\left(T_{Q^{*}(x)}^{Q}-I_{d}\right)=0$

By independence, one then has

$\displaystyle\mathbb{E}\left(T_{Q^{*}(x)}^{Q}-I_{d}\right)$
$\displaystyle\overset{(i)}{=}\left[\mathbb{E}s(x,X)\right]\cdot\left[\mathbb{E}s(x,X)\left(T_{Q^{*}(x)}^{Q}-I_{d}\right)\right]$
$\displaystyle=\mathbb{E}s(x,X)\left(T_{Q^{*}(x)}^{Q}-I_{d}\right)$
$\displaystyle=0$

Here (i) follows from the fact that $\mathbb{E}s(x,X)\equiv 1$.

##  Appendix G Proof of Proposition 13

Note that under the null (18), it holds that $Q^{*}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu)=Q^{*}$. Then Theorem 6
implies that with probability at least $1-O(n^{-100})$,

$\displaystyle\left\|\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)-Q^{*}\right\|_{\mathrm{F}}\leq\frac{\mathrm{polylog}\left(n\right)}{\sqrt{n}}$

Therefore, one has with probability at least $1-O(n^{-100})$,

$\displaystyle\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu)\in{\cal
S}_{d}((2c_{1})^{-1},2c_{1})$ (196)

for $n$ large enough. Here we recall that $c_{1}\geq 1$ is a constant defined
in Assumption 2.

One can apply the triangle inequality to see that

$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}\left(T^{Q_{i}}_{\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)}-I_{d}\right)\otimes\left(T^{Q_{i}}_{\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)}-I_{d}\right)-\mathbb{E}\left(T^{Q}_{Q^{*}}-I_{d}\right)\otimes\left(T^{Q}_{Q^{*}}-I_{d}\right)\right\|_{\mathrm{F}}$
$\displaystyle\leq$
$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}\left(T^{Q_{i}}_{\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)}-I_{d}\right)\otimes\left(T^{Q_{i}}_{\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)}-I_{d}\right)-\mathbb{E}\left(T^{Q}_{\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)}-I_{d}\right)\otimes\left(T^{Q}_{\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)}-I_{d}\right)\right\|_{\mathrm{F}}$
$\displaystyle+\left\|\mathbb{E}\left(T^{Q}_{\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)}-I_{d}\right)\otimes\left(T^{Q}_{\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)}-I_{d}\right)-\mathbb{E}\left(T^{Q}_{Q^{*}}-I_{d}\right)\otimes\left(T^{Q}_{Q^{*}}-I_{d}\right)\right\|_{\mathrm{F}}$
$\displaystyle\overset{(i)}{\leq}$ $\displaystyle\underbrace{\sup_{S\in{\cal
S}_{d}((2c_{1})^{-1},2c_{1})}\left\|\frac{1}{n}\sum_{i=1}^{n}\left(T^{Q_{i}}_{S}-I_{d}\right)\otimes\left(T^{Q_{i}}_{S}-I_{d}\right)-\mathbb{E}\left(T^{Q}_{S}-I_{d}\right)\otimes\left(T^{Q}_{S}-I_{d}\right)\right\|_{\mathrm{F}}}_{\zeta_{1}}$
$\displaystyle+\underbrace{\sup_{S:\left\|S-Q^{*}\right\|_{\mathrm{F}}\leq\mathrm{polylog}\left(n\right)/\sqrt{n}}\left\|\mathbb{E}\left(T^{Q}_{S}-I_{d}\right)\otimes\left(T^{Q}_{S}-I_{d}\right)-\mathbb{E}\left(T^{Q}_{Q^{*}}-I_{d}\right)\otimes\left(T^{Q}_{Q^{*}}-I_{d}\right)\right\|_{\mathrm{F}}}_{\zeta_{2}}$
(197)

Here (i) follows from (196).

Upper bounds for $\zeta_{1},\zeta_{2}$ in (197) are summarized in the lemma
below whose proof is deferred to Appendix G.1. Note that Lemma 39 do not
assume the null hypothesis so that it can be reused later for the proof of the
power (Theorem 14).

######  Lemma 39.

Suppose Assumption 1-6 hold. Then with probability at least $1-O(n^{-100})$,

$\displaystyle\zeta_{1}$
$\displaystyle\leq\frac{\mathrm{polylog}\left(n\right)}{\sqrt{n}}$ (198)
$\displaystyle\zeta_{2}$
$\displaystyle\leq\frac{\mathrm{polylog}\left(n\right)}{\sqrt{n}}$ (199)

Lemma 39 combined with (197) then implies

$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}\left(T^{Q_{i}}_{\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)}-I_{d}\right)\otimes\left(T^{Q_{i}}_{\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)}-I_{d}\right)-\mathbb{E}\left(T^{Q}_{Q^{*}}-I_{d}\right)\otimes\left(T^{Q}_{Q^{*}}-I_{d}\right)\right\|_{\mathrm{F}}\leq\frac{\mathrm{polylog}\left(n\right)}{\sqrt{n}}$
(200)

As a result, if $\left(\lambda_{i}\right)_{i\in[d^{2}]}$ are sorted in order,
then one has $\widehat{\lambda}_{i}\to\lambda_{i}$ uniformly for $i\in[d^{2}]$
in probability which further implies that

$\sum_{i=1}^{d^{2}}\widehat{\lambda}_{i}w_{i}\overset{p}{\rightarrow}\sum_{i=1}^{d^{2}}\lambda_{i}w_{i}$

Then the continuous mapping theorem implies that $\widehat{q}_{1-\alpha}\to
q_{1-\alpha}$ in probability. Then one can obtain

$\displaystyle\mathbb{P}\left(\widehat{{\cal
T}}_{n}>\widehat{q}_{1-\alpha}\right)\leq\mathbb{P}\left(\widehat{{\cal
T}}_{n}>q_{1-\alpha}-\epsilon\right)+\mathbb{P}\left(\left|\widehat{q}_{1-\alpha}-q_{1-\alpha}\right|>\epsilon\right)$

Taking the limit as $n\to\infty$, followed by letting $\epsilon\to 0$ to get
that

$\limsup_{n\to\infty}\mathbb{P}\left(\widehat{{\cal
T}}_{n}>\widehat{q}_{1-\alpha}\right)\leq\alpha$ (201)

A similar lower bound shows

$\liminf_{n\to\infty}\mathbb{P}\left(\widehat{{\cal
T}}_{n}>\widehat{q}_{\alpha}\right)\geq\alpha$ (202)

Finally, combining (201) and (202) completes the proof.

###  G.1 Proof of Lemma 39

##### Proof of (198):

the proof is similar to Lemma 33, and is hence omitted for brevity.

##### Proof of (199):

First, recall differential properties (Lemma 17) that

$\displaystyle\left\|T^{Q}_{S}\right\|_{\mathrm{op}}$
$\displaystyle\leq\lambda_{\max}\left(Q\right)\cdot\lambda_{\min}\left(Q\right)^{-1/2}\cdot\lambda_{\min}\left(S\right)^{-1/2}$
(203)
$\displaystyle\left|\\!\left|\\!\left|dT^{Q}_{S}\right|\\!\right|\\!\right|$
$\displaystyle\leq\frac{1}{2}\lambda_{\max}\left(Q\right)^{1/2}\cdot\lambda_{\min}\left(S\right)^{-2}\cdot\lambda_{\max}\left(S\right)^{1/2}$

Also, denote
$\phi(Q,S):=\left(T^{Q}_{S}-I_{d}\right)\otimes\left(T^{Q}_{S}-I_{d}\right)$.

With these results in place, one can obtain

$\displaystyle\left\|\phi(Q,S)-\phi(Q,Q^{*})\right\|_{\mathrm{F}}$
$\displaystyle\leq\left\|\left(T^{Q}_{S}-I_{d}\right)\otimes\left(T^{Q}_{S}-T^{Q}_{Q^{*}}\right)\right\|_{\mathrm{F}}+\left\|\left(T^{Q}_{S}-T^{Q}_{Q^{*}}\right)\otimes\left(T^{Q}_{Q^{*}}-I_{d}\right)\right\|_{\mathrm{F}}$
$\displaystyle\leq\left\|T^{Q}_{S}-I_{d}\right\|_{\mathrm{F}}\cdot\left\|T^{Q}_{S}-T^{Q}_{Q^{*}}\right\|_{\mathrm{F}}+\left\|T^{Q}_{S}-T^{Q}_{Q^{*}}\right\|_{\mathrm{F}}\cdot\left\|T^{Q}_{Q^{*}}-I_{d}\right\|_{\mathrm{F}}$
$\displaystyle\leq\left\|T^{Q}_{S}-I_{d}\right\|_{\mathrm{F}}\cdot\left|\\!\left|\\!\left|dT^{Q}_{S^{\prime}}\right|\\!\right|\\!\right|\cdot\left\|S-Q^{*}\right\|_{\mathrm{F}}+\left\|T^{Q}_{Q^{*}}-I_{d}\right\|_{\mathrm{F}}\cdot\left|\\!\left|\\!\left|dT^{Q}_{S^{\prime}}\right|\\!\right|\\!\right|\cdot\left\|S-Q^{*}\right\|_{\mathrm{F}}$

where $S^{\prime}$ lies between $Q^{*}$ and $S$. Note that Assumption 2 and
the condition
$\left\|S-Q^{*}\right\|_{\mathrm{F}}\leq\mathrm{polylog}\left(n\right)/\sqrt{n}$
implies that

$\displaystyle S,Q^{*}\in{\cal S}_{d}((2c_{1})^{-1},2c_{1})$

Then for any $S\in{\cal S}_{d}((2c_{1})^{-1},2c_{1})$, one has

$\displaystyle\mathbb{E}\left\|T^{Q}_{S}-I_{d}\right\|_{\mathrm{F}}\cdot\left|\\!\left|\\!\left|dT^{Q}_{S^{\prime}}\right|\\!\right|\\!\right|$
$\displaystyle\overset{(i)}{\lesssim}\mathbb{E}\left(\left\|X-\mu\right\|^{3C_{1}/2}+1\right)\cdot\left\|X-\mu\right\|^{C_{1}/2}$
$\displaystyle\overset{(ii)}{\lesssim}1$

Here $C_{1}$ is defined in Assumption 2, (i) follows from (203) and (ii) is a
result of the sub-Gaussianity of $X$. Similarly, one has

$\mathbb{E}\left\|T^{Q}_{Q^{*}}-I_{d}\right\|_{\mathrm{F}}\cdot\left|\\!\left|\\!\left|dT^{Q}_{S^{\prime}}\right|\\!\right|\\!\right|\lesssim
1$

Combining results above, one can obtain

$\displaystyle\zeta_{2}$
$\displaystyle\leq\sup_{S:\left\|S-Q^{*}\right\|_{\mathrm{F}}\leq\mathrm{polylog}\left(n\right)/\sqrt{n}}\mathbb{E}_{Q}\left\|\phi(Q,S)-\phi(Q,Q^{*})\right\|_{\mathrm{F}}$
$\displaystyle\lesssim\sup_{S:\left\|S-Q^{*}\right\|_{\mathrm{F}}\leq\mathrm{polylog}\left(n\right)/\sqrt{n}}1\cdot\left\|S-Q^{*}\right\|_{\mathrm{F}}$
$\displaystyle\leq\frac{\mathrm{polylog}\left(n\right)}{\sqrt{n}}$

The proof is then complete.

##  Appendix H Proof of Theorem 14

As argued at the beginning of Appendix C.2, one can assume without loss of
generality that $\left\|X-\mu\right\|\leq L$ almost surely with
$L=C_{L}\sqrt{\log n}$ for some constant $C_{L}$ large enough as in (79).
Recall the notation that $M_{L}:=\gamma_{1}(L)$.

##### Power under Frobenius norm:

First we demonstrate concentration of various quantities of interest and
derive their consequences in Lemma 40 below. The proof is in Appendix H.1.

######  Lemma 40.

Instate the notations and assumptions in Theorem 14. Assume in addition that
$\left\|X-\mu\right\|\leq L$ almost surely. Then there exists an event $E_{n}$
that satisfies $\mathbb{P}(E_{n})\geq 1-O(n^{-100})$ for any
$\mathbb{P}\in\mathfrak{P}$, under which the following inequalities

$\displaystyle\left\|X_{i}-\mu\right\|\leq L,$ $\displaystyle\quad
Q_{i}\in{\cal S}_{d}(M_{L}^{-1},M_{L})\qquad\text{for}\quad i\in[n]$ (204)
$\displaystyle\sup_{x\in
B_{\mu}(L)}\left\|\widehat{Q}_{n}(x)-Q^{*}(x)\right\|_{\mathrm{F}}$
$\displaystyle\leq\frac{\mathrm{polylog}\left(n\right)}{\sqrt{n}}$ (205)
$\displaystyle\left\\{\widehat{Q}_{n}(x):x\in B_{\mu}(L)\right\\}$
$\displaystyle\subset{\cal
S}_{d}\left(\left(2^{1/6}M_{L}\right)^{-1},2^{1/6}M_{L}\right)$ (206)
$\displaystyle\sum_{i=1}^{n}\left\|Q^{*}(X_{i})-Q^{*}(\mu)\right\|_{\mathrm{F}}^{2}$
$\displaystyle\geq\frac{na_{n}^{2}}{2}$ (207)
$\displaystyle\left\|\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)-Q^{*}(\mu)\right\|_{\mathrm{F}}^{2}$
$\displaystyle\leq\frac{\mathrm{polylog}\left(n\right)}{\sqrt{n}}$ (208)
$\displaystyle\left|\widehat{\lambda}_{i}\right|$ $\displaystyle\leq
2\lambda_{1},\qquad i\in\left[d^{2}\right]$ (209)

hold for $n$ large enough.

Next, note that (31) in Lemma 17 implies that for any $Q,S\in{\cal
S}_{d}\left(\left(2^{1/6}M_{L}\right)^{-1},2^{1/6}M_{L}\right)$ (here
$2^{1/6}$ is chosen only for technical computation), one has

$\frac{1}{2\sqrt{2}M_{L}^{3}}\leq\lambda_{\min}\left(-dT^{Q}_{S}\right)\leq\lambda_{\max}\left(-dT^{Q}_{S}\right)\leq\frac{\sqrt{2}}{2}M_{L}^{3}$

which then implies that under $E_{n}$, the following holds.

$\displaystyle\lambda_{\min}\left(\widehat{H}\right)\geq\frac{1}{n}\sum_{i=1}^{n}\lambda_{\min}\left(-dT^{Q_{i}}_{\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)}\right)\geq\frac{1}{2\sqrt{2}M_{L}^{3}}$

Therefore, under $E_{n}$, one has

$\displaystyle\widehat{{\cal
T}}_{n}\geq\frac{1}{8M_{L}^{6}}\sum_{i=1}^{n}\left\|\widehat{Q}_{n}(X_{i})-\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)\right\|_{\mathrm{F}}^{2}$ (210)

Then from the following decomposition

$\widehat{Q}_{n}(X_{i})-\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)=Q^{*}(X_{i})-Q^{*}(\mu)+\underbrace{\widehat{Q}_{n}(X_{i})-Q^{*}(X_{i})+Q^{*}(\mu)-\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu)}_{\Delta_{i}}$

one can obtain

$\displaystyle\sum_{i=1}^{n}\left\|\widehat{Q}_{n}(X_{i})-\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)\right\|_{\mathrm{F}}^{2}$ $\displaystyle\overset{(i)}{=}$
$\displaystyle\sum_{i=1}^{n}\left\|Q^{*}(X_{i})-Q^{*}(\mu)\right\|_{\mathrm{F}}^{2}+2\sum_{i=1}^{n}\left\langle
Q^{*}(X_{i})-Q^{*}(\mu),\Delta_{i}\right\rangle+\sum_{i=1}^{n}\left\|\Delta_{i}\right\|_{\mathrm{F}}^{2}$
$\displaystyle\overset{(ii)}{\geq}$
$\displaystyle\sum_{i=1}^{n}\left\|Q^{*}(X_{i})-Q^{*}(\mu)\right\|_{\mathrm{F}}^{2}-2\left(\sum_{i=1}^{n}\left\|Q^{*}(X_{i})-Q^{*}(\mu)\right\|_{\mathrm{F}}^{2}\right)^{1/2}\cdot\left(\sum_{i=1}^{n}\left\|\Delta_{i}\right\|_{\mathrm{F}}^{2}\right)^{1/2}+\sum_{i=1}^{n}\left\|\Delta_{i}\right\|_{\mathrm{F}}^{2}$
$\displaystyle\geq$
$\displaystyle\left(\sum_{i=1}^{n}\left\|Q^{*}(X_{i})-Q^{*}(\mu)\right\|_{\mathrm{F}}^{2}\right)\cdot\left(1-2\left(\frac{\sum_{i=1}^{n}\left\|\Delta_{i}\right\|_{\mathrm{F}}^{2}}{\sum_{i=1}^{n}\left\|Q^{*}(X_{i})-Q^{*}(\mu)\right\|_{\mathrm{F}}^{2}}\right)^{1/2}\right)$
(211)

Here (i) follows by developing the square, (ii) is a consequence of the
Cauchy-Schwarz inequality.

Lemma 40 implies that under $E_{n}$, one has

$\displaystyle\left\|\Delta_{i}\right\|_{\mathrm{F}}$
$\displaystyle\leq\left\|\widehat{Q}_{n}(X_{i})-Q^{*}(X_{i})\right\|_{\mathrm{F}}+\left\|Q^{*}(\mu)-\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern 1.5mu)\right\|_{\mathrm{F}}$
$\displaystyle\lesssim\frac{\mathrm{polylog}\left(n\right)}{\sqrt{n}}$ (212)

Therefore, (211) and (212) together imply the following inequality for $n$
large enough.

$\displaystyle\sum_{i=1}^{n}\left\|\widehat{Q}_{n}(X_{i})-\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)\right\|_{\mathrm{F}}^{2}\overset{(I)}{\geq}\frac{na_{n}^{2}}{2}\cdot\frac{3}{4}$
(213)

Here (I) arises due to Lemma 40, (212) as well as the fact that
$\mathrm{polylog}\left(n\right)=o\left(na_{n}^{2}\right)$.

Combining (210) and (213) then gives that under $E_{n}$, one has

$\displaystyle\widehat{{\cal T}}_{n}$
$\displaystyle\geq\frac{3na_{n}^{2}}{64M_{L}^{6}}$
$\displaystyle\geq\sqrt{na_{n}^{2}}$ (214)

for $n$ large enough.

Denote $\widetilde{q}_{1-\alpha}$ the $1-\alpha$ quantile of
$\sum_{i=1}^{d^{2}}2\lambda_{1}w_{i}$, which is a fixed constant. Then as a
consequence of Lemma 40, $\sum_{i=1}^{d^{2}}\widehat{\lambda}_{i}w_{i}$ is
stochastically dominated by $\sum_{i=1}^{d^{2}}2\lambda_{1}w_{i}$ under
$E_{n}$, which then implies that

$\widehat{q}_{1-\alpha}<\widetilde{q}_{1-\alpha},\qquad\text{under }E_{n}$

Therefore, for any $\mathbb{P}\in\mathfrak{P}$, one can obtain

$\displaystyle\mathbb{P}\left(\widehat{{\cal
T}}_{n}>\widehat{q}_{1-\alpha}\right)$
$\displaystyle\geq\mathbb{P}\left(\left\\{\widehat{{\cal
T}}_{n}>\widetilde{q}_{1-\alpha}\right\\}\cap\left\\{\widetilde{q}_{1-\alpha}>\widehat{q}_{1-\alpha}\right\\}\right)$
$\displaystyle\geq\mathbb{P}\left(\left\\{\widehat{{\cal
T}}_{n}>\widetilde{q}_{1-\alpha}\right\\}\cap E_{n}\right)$
$\displaystyle\overset{(i)}{\geq}\mathbb{P}\left(\left\\{\sqrt{na_{n}^{2}}>\widetilde{q}_{1-\alpha}\right\\}\cap
E_{n}\right)$

for $n$ large enough. Here (i) follows from (214).

Finally, one can take $n\to\infty$ to see that

$\displaystyle\liminf_{n\to\infty}\inf_{\mathbb{P}\in\mathfrak{P}}\mathbb{P}\left(\widehat{{\cal
T}}_{n}>\widehat{q}_{1-\alpha}\right)$
$\displaystyle\geq\liminf_{n\to\infty}\inf_{\mathbb{P}\in\mathfrak{P}}\mathbb{P}\left(\left\\{\sqrt{na_{n}^{2}}>\widetilde{q}_{1-\alpha}\right\\}\cap
E_{n}\right)$ $\displaystyle\geq 1$

which implies

$\lim_{n\to\infty}\inf_{\mathbb{P}\in\mathfrak{P}}\mathbb{P}\left(\widehat{{\cal
T}}_{n}>\widehat{q}_{1-\alpha}\right)=1$

The proof is then complete.

##### Power under Wasserstein distance:

by Lemma 17 and the boundedness assumption, one has

$\displaystyle\mathbb{E}\left\|Q^{*}(X)-Q^{*}(\mu)\right\|_{\mathrm{F}}^{2}\geq\frac{1}{\mathrm{polylog}\left(n\right)}\mathbb{E}W^{2}\left(Q^{*}(X),Q^{*}(\mu)\right)$

Therefore, the 1st part of the proof (Frobenius norm) can be applied.

###  H.1 Proof of Lemma 40

(204)-(206) are shown in the proof of Theorem 6 and (208) is due to Lemma 27.

##### Proof of (207):

With these in place, we have almost surely that

$\displaystyle\left\|Q^{*}(X)-Q^{*}(\mu)\right\|_{\mathrm{F}}^{2}$
$\displaystyle\leq d\left\|Q^{*}(X)-Q^{*}(\mu)\right\|_{\mathrm{op}}^{2}$
$\displaystyle\leq dM_{L}^{2}=:M_{F}\asymp\mathrm{polylog}\left(n\right)$
(215)

Define random variable $Y_{i}$ as follows.

$\displaystyle Y_{i}$
$\displaystyle:=\left\|Q^{*}(X_{i})-Q^{*}(\mu)\right\|_{\mathrm{F}}^{2}-\mathbb{E}\left\|Q^{*}(X)-Q^{*}(\mu)\right\|_{\mathrm{F}}^{2}$

With (215) in place, one then has $Y_{i}\in[-M_{F},M_{F}]$,
$\mathbb{E}Y_{i}=0$ and

$\displaystyle\operatorname{{\rm Var}}{Y_{i}}$
$\displaystyle=\mathbb{E}Y_{i}^{2}$
$\displaystyle\leq\mathbb{E}\left|Y_{i}\right|M_{F}$ $\displaystyle\leq
2\mathbb{E}\left\|Q^{*}(X_{i})-Q^{*}(\mu)\right\|_{\mathrm{F}}^{2}\cdot M_{F}$
$\displaystyle=2a_{n}^{2}\cdot M_{F}$

To prove (207), it suffices to show that ,

$\displaystyle\left|\sum_{i}^{n}Y_{i}\right|\leq\frac{na_{n}^{2}}{2}\quad\text{with
probability at least }1-O(n^{-100})$ (216)

To this end, note that by Bernstein’s inequality (Vershynin,, 2018, Theorem
2.8.4), one has with probability at least $1-O(n^{-100})$,

$\displaystyle\left|\sum_{i}^{n}Y_{i}\right|$ $\displaystyle\lesssim M_{F}\log
n+\sqrt{n\operatorname{{\rm Var}}{Y_{i}}}\cdot\sqrt{\log n}$
$\displaystyle\lesssim M_{F}\log n+\sqrt{na_{n}^{2}M_{F}}\cdot\sqrt{\log n}$
$\displaystyle\overset{(i)}{\leq}\mathrm{polylog}\left(n\right)\cdot\left(1+\sqrt{na_{n}^{2}}\right)$
(217)

Then (217) implies (216) for $n$ large enough due to the assumption that
$na_{n}^{2}\gtrsim n^{2\alpha_{2}}$ for some constant $\alpha_{2}>0$. The
proof is then complete.

##### Proof of (209):

Note that the proof of Lemma 39 does not assume the null hypothesis.
Therefore, with (208) in place, one can exactly follow (196)-(200) as in the
proof of Lemma 39 to get

$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}\left(T^{Q_{i}}_{\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)}-I_{d}\right)\otimes\left(T^{Q_{i}}_{\widehat{Q}_{n}(\mkern
1.5mu\overline{\mkern-1.5muX\mkern-1.5mu}\mkern
1.5mu)}-I_{d}\right)-\mathbb{E}\left(T^{Q}_{Q^{*}}-I_{d}\right)\otimes\left(T^{Q}_{Q^{*}}-I_{d}\right)\right\|_{\mathrm{F}}\leq\frac{\mathrm{polylog}\left(n\right)}{\sqrt{n}}$

which implies (209).