# Properties of the cone of polynomials of fixed degree that preserve
nonnegative matrices

Jared J. L. Brannan  Benjamin J. Clark

(February 2024)

###### Abstract

As was detailed by Lowey and London in [7], the cone of polynomials that
preserve the nonnegativity of matrices may play an important role in the
solution to the nonnegative inverse eigenvalue problem. In this paper, we
start by showing the cone generated by polynomials of degree greater than or
equal to $2n$ that preserve nonnegative matrices of order $n$ is non-
polyhedral. Then it is shown that a polynomial that preserves nonnegative
matrices of order $n$ can have all the center terms be negative and they can
have the largest term, in absolute value, be arbitrarily negative with the
remaining coefficients being one. We explore properties of the measure of the
cone when restricted to the unit sphere and prove some initial bounds of that
volume.

##  1 Introduction

Motivated by the nonnegative inverse eigenvalue problem (NIEP), Lowey and
London in [7] posed the problem of characterizing the polynomials that
preserve nonnegative matrices of a fixed order. Finding a characterization has
been shown to provide additional necessary conditions for the NIEP. See [5]
for a survey on the NIEP and [6] for more information on how characterizing
the polynomials that preserve nonnegative matrices gives necessary conditions
for the NIEP.

We denote $\mathcal{P}_{n}$ to be the set of polynomials that preserve
nonnegative matrices of order $n$. Clark and Paparella in [2] gave general
results for the coefficients of polynomials in $\mathcal{P}_{n}$ and in [3]
gave a characterization for $\mathcal{P}_{2}$. Bharali and Holtz in [1]
considered a larger class of entire functions that preserve nonnegative
matrices of a fixed order. Lowey in [6] gave a proof of a conjecture of Clark
and Paparella that $\mathcal{P}_{n+1}$ is a strict subset of $\mathcal{P}_{n}$
and showed that if we restrict the degree of polynomials in $\mathcal{P}_{n}$
to some $m\in\mathbb{Z}^{+}$, denoted $\mathcal{P}_{n,m}$, then
$\mathcal{P}_{2,m}$ is non-polyhedral for $m\geq 4$. We extend this result to
show that $\mathcal{P}_{n,m}$ is non-polyhedral for all $n\geq 2$ and $m\geq
2n$.

Next, we give two new sets of polynomials in $\mathcal{P}_{n}$. The first is
given an arbitrary length of polynomial if the first and last $n$ terms are
nonnegative then we show the rest can be made negative. The second is we show
that given enough terms in a polynomial the center term can be made
arbitrarily negative.

We conclude by considering the volume the cone $\mathcal{P}_{n,m}$ takes when
restricted to the unit sphere. We conjecture that as $m$ goes to infinity the
volume of the cone goes to $0$. Some inequalities are given for how the volume
changes as we vary $m$ and $n$ for $\mathcal{P}_{n,m}$.

##  2 Background and notation

The set $\mathsf{M}_{n}^{\geq 0}$ ($\mathsf{M}_{n}^{+})$ will be used to
denote the $n$ by $n$ nonnegative (positive) matrices.

For a given $n\in\mathbb{Z}^{+}$, then $\langle n\rangle=\\{1,2,\dots,n\\}$
and $\langle n\rangle_{0}=\\{0,1,2,\dots,n\\}$.

The set $\mathcal{P}_{n}=\\{p\in\mathbb{R}[x]:p(A)\geq 0,\forall
A\in\mathsf{M}_{n}^{\geq 0}\\}$ is the main object of study. It is shown in
[2, Lemma 6] that $\mathcal{P}_{n}$ is equivalent to
$\\{p\in\mathbb{R}[x]:p(A)\geq 0,\forall A\in\mathsf{M}_{n}^{+}\\}$, that is
we need only consider positive matrices. When we restrict the degree of
polynomials in $\mathcal{P}_{n}$ we will use the notation of [6], which is
$\mathcal{P}_{n,m}=\\{p\in\mathcal{P}_{n}:\text{deg}(p)\leq m\\}$.

For the convex analysis dealing with the cone behaviors of $\mathcal{P}_{n}$
and $\mathcal{P}_{n,m}$ we will be following the notation of [9]. Let $S$ be a
set of values where scalar multiplication is defined, then $\mathcal{C}(S)$
denotes the cone generated by the set $S$.

Let $p\in\mathbb{R}[x]$, then denote
$\mathcal{Z}_{i,j}(p)\subset\mathsf{M}_{n}^{+}$ such that $(p(A))_{i,j}=0$ for
all $A\in\mathcal{Z}_{i,j}(p)$. Also define $\mathcal{Z}(p)$ to be the union
of $\mathcal{Z}_{i,j}(p)$ for all $i,j\in\langle n\rangle$.

######  Lemma 2.1.

Let $S_{n}$ be the set of positive stochastic $n$ by $n$ matrices and
$p\in\mathbb{R}[t]$, then $p\in\mathcal{P}_{n}$ if and only if $p(\rho A)\geq
0$ for all $A\in S_{n}$ and $\rho\in\mathbb{R}^{+}$.

###### Proof.

This follows directly from [2, Lemma 1], [2, Lemma 6], and noting that all
positive matrices can be turned into a row stochastic matrix by a diagonal
similarity. ∎

We are following the definition and construction of Hausdorff measure from
Evans [4, Definition 2.1].

######  Definition 2.2.

Let $A\subseteq\mathbb{R}^{n}$, then $\mathcal{H}^{s}$ denotes the
$s$-dimensional Hausdorff measure on $\mathbb{R}^{n}$ and $\mathcal{H}^{s}(A)$
denotes the $s$-dimensional Hausdorff measure of the set $A$.

We will use $\overline{B}_{k}(0,1)$ to be the closed $k$ dimensional unit
sphere centered at $0$.

##  3 Cone of polynomials is non polyhedral for sufficient degree

######  Definition 3.1.

Let $p,q\in\mathbb{R}[x]$ and $t\in[0,1]$, then define
$g_{p,q,t}(x):=(1-t)p(x)+tq(x)$ to be the polynomial made from the convex
combination of $p$ and $q$.

######  Lemma 3.2.

Let $X=\\{x,x^{2},\dots,x^{n}\\}$ and
$P=\\{p_{i}\\}_{i=1}^{m}\subset\mathcal{P}_{n,2n}$ where

$p_{i}(x)=\sum_{\begin{subarray}{c}k=0\\\
k\not=n\end{subarray}}^{2n}a_{i,k}x^{k}-x^{n}.$

Then $g_{p,q,t}$ is not extremal in $\mathcal{P}_{n,2n}$ for any $t\in(0,1)$,
$p\in P$, and for any $q\in X$.

###### Proof.

Let $p\in P$ and $q\in X$, then following $\mathcal{Z}(q)=\emptyset$ we get
for any $t\in(0,1)$, $\mathcal{Z}(g_{p,q,t})=\emptyset$. For a specific
$t\in(0,1)$ we can find an $\epsilon>0$ such that $g_{p,q,t}(A)-\epsilon
A^{n}\geq 0$ for all $A\in\mathsf{M}_{n}^{\geq 0}$ following $x^{n}$ is
continuous over matrices. Thus $g_{p,q,t}$ is not extremal for any
$t\in(0,1)$. ∎

######  Lemma 3.3.

Let $X=\\{x,x^{2},\dots,x^{n}\\}$ and $P=\\{p_{i}\\}_{i=1}^{m}$ where

$p_{i}(x)=\sum_{\begin{subarray}{c}k=0\\\
k\not=n\end{subarray}}^{2n}a_{i,k}x^{k}-x^{n}.$

Then $g_{p,q,t}$ forms a face of $\mathcal{C}(X\cup P)$ for some $p\in P$ and
$q\in X$.

###### Proof.

The cone $\mathcal{C}(X\cup P)$ is finitely generated and hence polyhedral.
Note, from construction, that $\mathcal{C}(X\cup P)$ is not a subset of either
$\mathcal{C}(X)$ or a subset of $\mathcal{C}(P)$. For polyhedral cones, convex
combinations of extremal generators form the faces of the cone. The result
follows from $g_{p,q,t}$ being a convex combination of extremal generators
from the cone $P$ to the cone $X$. ∎

######  Theorem 3.4.

Let $n\in\mathbb{Z}^{+}$, then $\mathcal{P}_{n,2n}$ is not a polyhedral cone.

###### Proof.

Assume for contradiction that $\mathcal{P}_{n,2n}$ is a polyhedral cone, then
$\mathcal{P}_{n,2n}$ is finitely generated. We know $\mathcal{P}_{n,2n}$ is a
superset of the nonnegative orthant which has a convex basis of
$\\{1,x,x^{2},\dots,x^{2n}\\}$. Clark and Paparella, in [2, Corollary 4.2 and
Theorem 4.11], showed that the first and last $n$ terms of the polynomial must
be nonnegative. However, Loewy showed in [6, Corollary 2.2] that the $x^{n}$
term can be negative. Without loss of generality we can assume that the $n$th
coefficient is equal to $1$. Thus the remaining finite conical basis element
of $\mathcal{P}_{n,2n}$ are $P=\\{p_{i}\\}_{i=1}^{m}$ where

$p_{i}(x)=\sum_{\begin{subarray}{c}k=0\\\
k\not=n\end{subarray}}^{2n}a_{i,k}x^{k}-x^{n}$

and with $a_{i,k}\geq 0$. Note that not all the $a_{i,k}$ need to be positive
in the extremal case.

If $p\in P$ and $q\in X=\\{x,x^{2},\dots,x^{2n}\\}$, then by Lemma 3.2
$g_{p,q,t}(x)$ is not extremal for all $t\in(0,1)$. By Lemma 3.3 there exists
$p\in P$ and $q\in X$ such that $g_{p,q,t}$ is a face of $\mathcal{P}_{n,2n}$.
However, this is a contradiction since $g_{p,q,t}$ cannot be a face and not
extremal. Thus $\mathcal{P}_{n,2n}$ is not a polyhedral cone. ∎

######  Corollary 3.5.

Let $n,m\in\mathbb{Z}^{+}$ such that $m>2n$, then $\mathcal{P}_{n,m}$ is not a
polyhedral cone.

###### Proof.

If a convex cone is polyhedral, then every face must be polyhedral. Loewy in
[6, Lemma 3.1] showed that $\mathcal{P}_{n,2n}$ is a face of
$\mathcal{P}_{n,m}$ and by Theorem 3.4 that face is not polyhedral. ∎

######  Corollary 3.6.

The cone $\mathcal{P}_{n,2n}$ has an uncountable number of basis elements.

###### Proof.

Start with candidate generators $Q=P\cup X$ as in the proof of Theorem 3.4 and
consider $p,q\in Q$. Construct $g_{p,q,t}(x)$ also as in the proof of Theorem
3.4. For some $t\in(0,1)$ we have that $g_{p,q,t}(x)$ is not extremal. Perturb
the coefficients of $g_{p,q,t}$ so that it is extremal, call it $g_{1}$ and
set $X_{1}=X\cup\\{g_{1}\\}$. Using the same $p,q\in X$, consider
$g_{p,g_{1},t_{2}}$ and $g_{g_{1},q,t_{2}}$ for $t_{1},t_{2}\in(0,1)$ such
that these polynomials are not extremal. Construct $g_{2_{1}}$ and $g_{2_{2}}$
by a similar process to $g_{1}$, and add them to $X_{1}$ to make $X_{2}.$
Continuing in this way, we get $2^{\mathbb{N}}$ generators. ∎

##  4 Properties of the negative coefficients

######  Lemma 4.1.

Let $A\in\mathsf{M}_{n}^{+}$ be a stochastic matrix and
$s,t\in\mathbb{Z}^{+}$, then there exists $\alpha\in\mathbb{R}^{+}$ such that

$A^{s}\leq\alpha_{A}\sum_{k=0}^{n-1}A^{t+k}.$

###### Proof.

Let $A\in\mathsf{M}_{n}^{+}$ be a stochastic matrix and
$s,t\in\mathbb{Z}^{+}$, then we can write $s=qn+r$. By the Caley-Hamilton
theorem $p_{A}(A)=0$ where

$p_{A}(x)=x^{n}+\sum_{k=0}^{n-1}a_{k}x^{k}$

is the characteristic polynomial of $A$. Let
$a=\max\\{|a_{0}|,|a_{1}|,\dots,|a_{n-1}|,1\\}$, then we get that

$A^{n}\leq a\sum_{k=0}^{n-1}A^{k}.$

Substituting in $s$ to the above equation gives

$A^{s}=A^{qn+r}\leq a^{q}A^{r}\left(\sum_{k=0}^{n-1}A^{k}\right)^{q}.$

Notice that when the multinomial theorem is applied to the sum above the
largest power becomes $q(n-1)+r$. Therefore we can repeatedly apply the
multinomial theorem to yield

$A^{s}\leq\alpha_{s}\sum_{k=0}^{n-1}A^{k}.$

Finally we can multiply the right side of the inequality by $A^{t}$ noting
that since $A$ is positive $A^{t}$ is positive so we can scale $\alpha_{s}$ to
$\alpha$ so that the inequality still holds. This gives the desired result.

∎

######  Lemma 4.2.

Let $s,t\in\mathbb{Z}^{+}$ and $S$ be the set of positive stochastic matrices,
then $\alpha=\sup_{A\in S}\alpha_{A}$ is finite where $\alpha_{A}$ is from
Lemma 4.1.

###### Proof.

The suprema, $a$, over $S$ of the modulus of the coefficients of the
characteristic polynomials is bounded following $S$ being compact and the
characteristic polynomial being a continuous operation. Now since $s,t$ are
fixed and we are taking $a$ to a finite power multiplied by a finite constant
from the repeated multinomial theorem applications the resulting $\alpha$ must
be finite. ∎

######  Theorem 4.3.

Let $m\in\mathbb{Z}$, then there exists $\alpha\in\mathbb{R}^{+}$ such that

$\sum_{k=0}^{n-1}\alpha
x^{k}-\left(\sum_{k=n}^{m+n}x^{k}\right)+\sum_{k=m+n+1}^{m+2n}\alpha
x^{k}\in\mathcal{P}_{n}.$

###### Proof.

Let $m\in\mathbb{Z}$, then construct

$p(x)=\sum_{k=0}^{n-1}\alpha
x^{k}-\left(\sum_{k=n}^{m+n}x^{k}\right)+\sum_{k=m+n+1}^{m+2n}\alpha x^{k}.$

where $\alpha$ is the max from Lemma 4.2 over the values of
$s\in\\{n,n+1,\dots,n+m\\}$ and $t\in\\{0,m+n+1\\}$ multiplied by $m$.

Now let $A\in\mathsf{M}^{+}_{n}$ such that $A$ is a stochastic matrix and let
$\rho\in\mathbb{R}^{+}$, then proceed by cases. If $\rho\leq 1$, then

$\displaystyle p(\rho A)$
$\displaystyle=\sum_{k=0}^{n-1}\alpha\rho^{k}A^{k}-\left(\sum_{k=n}^{m+n}\rho^{k}A^{k}\right)+\sum_{k=m+n+1}^{m+2n}\alpha\rho^{k}A^{k}$
$\displaystyle\geq\sum_{k=0}^{n-1}\alpha\rho^{n}A^{k}-\left(\sum_{k=n}^{m+n}\rho^{n}A^{k}\right)$
$\displaystyle=\rho^{n}\left(\sum_{k=0}^{n-1}\alpha
A^{k}-\sum_{k=n}^{m+n}A^{k}\right)$

By Lemma 4.1 $\sum_{k=0}^{n-1}\alpha A^{k}-\sum_{k=n}^{m+n}A^{k}\geq 0$ giving
$p(\rho A)\geq 0$. If $\rho>0$, then by a similar calculation we get

$p(\rho A)\geq\rho^{m+n+1}\left(\sum_{k=m+n+1}^{m+2n}\alpha
A^{k}-\sum_{k=n}^{m+n}A^{k}\right).$

Again by Lemma 4.1 $\sum_{k=m+n+1}^{m+2n}\alpha
A^{k}-\sum_{k=n}^{m+n}A^{k}\geq 0$ giving $p(\rho A)\geq 0$. Thus, by Lemma
2.1, $p\in\mathcal{P}_{n}$. ∎

The above theorem says that given large enough first and last coefficients all
the center terms of the polynomial can be made negative. This gives that only
the first and last terms have this nonnegativity requirement.

######  Theorem 4.4.

Let $\alpha\in\mathbb{R}$, then there exists $m\in\mathbb{Z}$ such that

$\sum_{k=0}^{m-1}x^{k}-\alpha x^{m}+\sum_{k=m+1}^{2m}\in\mathcal{P}_{n}.$

###### Proof.

Let $\alpha\in\mathbb{R}$, then choose $m=\lceil\alpha\rceil$. Now $m=qn+r$ so
choose $a=q+1$, then construct

$p(x)=\sum_{k=0}^{an-1}x^{k}-\alpha x^{an}+\sum_{k=an+1}^{2an}x^{k}.$

Now let $A\in\mathsf{M}^{+}_{n}$ such that $A$ is a stochastic matrix and let
$\rho\in\mathbb{R}^{+}$, then proceed by cases. If $\rho\leq 1$, then

$\displaystyle p(\rho A)$
$\displaystyle=\sum_{k=0}^{an-1}\rho^{k}A^{k}-\alpha\rho^{an}A^{an}+\sum_{k=an+1}^{2an}\rho^{k}A^{k}$
$\displaystyle\geq\sum_{k=0}^{an-1}\rho^{an}A^{k}-\alpha\rho^{an}A^{an}+\sum_{k=an+1}^{2an}\rho^{k}A^{k}$
$\displaystyle=\rho^{an}\left(\sum_{k=0}^{an-1}A^{k}-\alpha
A^{an}\right)+\sum_{k=an+1}^{2an}\rho^{k}A^{k}$
$\displaystyle\geq\rho^{an}\left(\sum_{k=0}^{an-1}A^{k}-\alpha A^{an}\right).$

From Lemma 4.1 $\sum_{k=0}^{an-1}A^{k}-\alpha A^{an}\geq 0$ giving $p(\rho
A)\geq 0$.

If $\rho>1$, then we can do a similar calculation to get

$p(\rho A)\geq\rho^{an+1}\left(\sum_{k=an+1}^{2an}A^{k}-\alpha A^{an}\right).$

Again by Lemma 4.1 $\sum_{k=an+1}^{2an}A^{k}-\alpha A^{an}\geq 0$. Thus, by
Lemma 2.1, $p\in\mathcal{P}_{n}$. ∎

This conjecture gives that with enough padding terms on the ends the center
term of the polynomial can be made arbitrarily negative in proportion to the
rest of the terms.

######  Remark 4.5.

Lacking bounds, the results of Theorem 4.4 and Theorem 4.3 are weaker than
Lowey’s [6, Theorem 2.1] for the specific case of one middle negative term.
However they give a more general set of polynomials with negative coefficients
that exist in $\mathcal{P}_{n}$.

##  5 Measure of polynomials restricted to the unit sphere

In this section we will consider the volume that $\mathcal{P}_{n,k}$ takes
within the unit sphere. We are treating $\mathcal{P}_{n,k}$ as a $k+1$
dimensional vector space with respect to the coefficients of the polynomials.

######  Lemma 5.1.

Let $C_{1}$ and $C_{2}$ be convex compact subsets of $\mathbb{R}^{n}$ with
nonempty interior such that $C_{2}\subset C_{1}$, then
$\mathcal{H}^{n}(C_{2})<\mathcal{H}^{n}(C_{1})$.

###### Proof.

Let $C_{1}$ and $C_{2}$ be convex, compact subsets of $\mathbb{R}^{n}$ with
non-empty interior such that $C_{2}\subset C_{1}$ and let $x\in C_{1}\setminus
C_{2}$. Define $S_{x}$ to be the supporting hyperplane of $C_{2}$ that splits
$x$ and $C_{1}$ such that $\text{dist}(S_{x},x)=\epsilon>0$ and let
$\widehat{S}_{x}$ be the family of supporting hyperplanes of the convex hull
of $C_{2}\cup\\{x\\}$ containing $x$. Let $C$ be the convex cone bounded by
$\widehat{S}_{x}$ and $S$. Note by construction $C\subseteq C_{1}$.

Note, we can associate with each ray from $x$ through $C_{2}$ an angle element
$\theta$ and the point $y_{\theta}\in S_{x}$. Let
$R_{\theta}(t)=tx+(1-t)y_{\theta}$ where $0<t<1$. By construction,

$\mathcal{H}^{1}\left(\\{R_{\theta}(t):0<t<1\\}\right)\geq\epsilon>0.$

Let $\widehat{C}$ be the set of all $\theta$s. Writing
$\theta=(\theta_{1},\dots,\theta_{n})$, we have that

$\mathcal{H}^{1}\left(\\{\sigma_{j}:\exists~{}\theta\in\widehat{C}\text{ with
}\theta=(\theta_{1},\dots,\theta_{j}=\sigma_{j},\dots,\theta_{n})\\}\right)\not=0$

for all $j\in\langle n\rangle$. Otherwise $\mathcal{H}^{n}(C_{2})=0$
contradicting that $C_{2}$ has a nonempty interior. Then by the coarea formula
[4, Theorem 3.10] we have

$\mathcal{H}^{n}(C)=\int_{\widehat{C}}\mathcal{H}^{1}\left(\\{R_{\theta}(t):0<t<1\\}\right)~{}d\theta>0.$

Therefore with $C_{2}\cap\text{int}C=\emptyset$ we have

$\mathcal{H}^{n}(C_{2})<\mathcal{H}^{n}(C_{2}\cup
C)\leq\mathcal{H}^{n}(C_{1}).\qed$

######  Definition 5.2.

Define $\pi:\mathcal{P}_{n,k+1}\rightarrow\mathcal{P}_{n,k}$ by projecting off
the $k+1$ term of the polynomial.

Note that the projection operator is continuous.

######  Lemma 5.3.

Let $n,k\in\mathbb{Z}^{+}$ such that $k\geq 2n$, then
$\mathcal{P}_{n,k}\cap\overline{B}_{k+1}$ is a convex compact subset of
$\mathbb{R}^{k+1}$ with nonempty interior.

###### Proof.

As was shown in [3] $\mathcal{P}_{n}$ and by extension $\mathcal{P}_{n,k}$ is
convex and as was shown in [6] $\mathcal{P}_{n,k}$ is closed. The nonempty
interior follows from $\mathcal{P}_{n,k}$ always containing the nonnegative
orthant of $\mathbb{R}^{k+1}$. Finally following $\overline{B}_{k+1}$ forms a
compact subset and $\mathcal{P}_{n,k}$ is closed we get that
$\mathcal{P}_{n,k}\cap\overline{B}_{k+1}$ is compact. ∎

######  Lemma 5.4.

Let $n,k\in\mathbb{Z}^{+}$ such that $k\leq 2n$, then
$\mathcal{P}_{n,k}\subset\pi(\mathcal{P}_{n,k+1})$.

###### Proof.

By Theorem 4.3 there exists polynomials in $\pi(\mathcal{P}_{n,k+1})$ such
that their $k-n$ term be negative. By [3, Theorem 4.11] $\mathcal{P}_{n,k}$
does not have polynomials with their $k-n$ term negative. The result follows
noting that $\mathcal{P}_{n,k}\subset\mathcal{P}_{n,k+1}$. ∎

######  Theorem 5.5.

Let $n,k\in\mathbb{Z}^{+}$ such that $k\leq 2n$, then

$\mathcal{H}^{k+1}\left(\pi(\mathcal{P}_{n,k+1})\cap\overline{B}_{k+1}(0,1)\right)>\mathcal{H}^{k+1}\left(\mathcal{P}_{n,k}\cap\overline{B}_{k+1}(0,1)\right)$

###### Proof.

Follows from Lemma 5.1, Lemma 5.4, and Lemma 5.3. ∎

######  Theorem 5.6.

Let $n,k\in\mathbb{Z}^{+}$ such that $k\leq 2n$, then

$\mathcal{H}^{k+1}\left(\mathcal{P}_{n+1,k}\cap\overline{B}_{k+1}(0,1)\right)<\mathcal{H}^{k+1}\left(\mathcal{P}_{n,k}\cap\overline{B}_{k+1}(0,1)\right).$

###### Proof.

The result follows from Lemma 5.3, [6, Corollary 2.1] giving that
$\mathcal{P}_{n+1,k}\subset\mathcal{P}_{n,k}$, and by Lemma 5.1. ∎

######  Conjecture 5.7.

Let $n,k\in\mathbb{Z}^{+}$ such that $k\leq 2n$, then

$\mathcal{H}^{k+2}\left(\mathcal{P}_{n,k+1}\cap\overline{B}_{k+2}(0,1)\right)<\mathcal{H}^{k+1}\left(\mathcal{P}_{n,k}\cap\overline{B}_{k+1}(0,1)\right)$

######  Conjecture 5.8.

Let $n,k\in\mathbb{Z}^{+}$ such that $k\leq 2n$, then

$\lim_{k\rightarrow\infty}\frac{\mathcal{H}^{k+1}\left(\mathcal{P}_{n,k}\cap\overline{B}_{k+1}(0,1)\right)}{\mathcal{H}^{k+1}\left(\overline{B}_{k+1}(0,1)\right)}=0.$

######  Remark 5.9.

We are not sure on the behavior of
$\mathcal{H}\left(\mathcal{P}_{n}\cap\overline{B}_{\infty}(0,1)\right)$. In
infinite dimension we lose the compactness of the sphere. While
$\mathcal{P}_{n}$ does not contain any infinite dimensional polynomials it
contains sequences of polynomials that go to infinite dimension. To study this
further it may be easier to consider the set of entire functions instead of
polynomials as was done in [1].

##  6 Concluding remarks

At the end of the previous section we have two conjectures. One potential
avenue for solving these is with further study of $\mathcal{P}_{1,k}$. The
characterization of $\mathcal{P}_{1}$ is known as the Pólya–Szegö theorem, see
[8, Proposition 2], which asserts that $p\in\mathcal{P}_{1}$ if and only if

$p(x)=(f(x))^{2}+x(g(x))^{2}$

where $f,g\in\mathbb{R}[t]$. Following that
$\mathcal{P}_{n}\subset\mathcal{P}_{1}$ this means that all polynomials in
$\mathcal{P}_{n}$ can be written as sums of squares.

Sums of squares tie in closely with quadratic forms. Determining an expression
for the curve that extends out of the nonnegative orthant $\mathcal{P}_{n,2n}$
would be beneficial to characterizing $\mathcal{P}_{n}$. We offer the
following conjecture for a potential avenue of determining that curve.

######  Conjecture 6.1.

There exists a finite $k\in\mathbb{Z}^{+}$ where $f_{k}(\textbf{v})\geq 0$ for
$f_{k}\in\mathbb{R}^{2n}[x]$ implies the polynomial whose coefficients are v
is in $\mathcal{P}_{n,2n}$.

Another way to state the above conjecture is that there are a finite number of
quadratic forms that describe the boundary of $\mathcal{P}_{n,2n}$.

## References

  * [1] G. Bharali and O. Holtz.  Functions preserving nonnegativity of matrices.  SIAM Journal on Matrix Analysis and Applications, 30(1):84–101, 2008.
  * [2] B. J. Clark and P. Paparella.  Polynomials that preserve nonnegative matrices.  Linear Algebra and its Applications, 637:110–118, 2022.
  * [3] B. J. Clark and P. Paparella.  Polynomials that preserve nonnegative matrices of order two.  Mathematics Exchange, 16:58–65, 2022.
  * [4] L. C. Evans and R. F. Gariepy.  Measure theory and fine properties of functions.  Textbooks in Mathematics. CRC Press, Boca Raton, FL, revised edition, 2015.
  * [5] C. R. Johnson, C. Marijuán, P. Paparella, and M. Pisonero.  The NIEP, pages 199–220.  Springer International Publishing, Cham, 2018.
  * [6] R. Loewy.  Proof of a conjecture on polynomials preserving nonnegative matrices.  Linear Algebra and its Applications, 676:267–276, 2023.
  * [7] R. Loewy and D. London.  A note on an inverse problem for nonnegative matrices.  Linear and Multilinear Algebra, 6(1):83–90, 1978.
  * [8] V. Powers and B. Reznick.  Polynomials that are positive on an interval.  Trans. Amer. Math. Soc., 352(10):4677–4692, 2000.
  * [9] R. T. Rockafellar.  Convex analysis, volume 11.  Princeton university press, 1997.


$\mathfrak{g}=\mathfrak{h}\cap C$. Then $\mathfrak{g}$ is an ideal of an
$\mathcal{O}$-order $\Gamma$, which may be strictly contained in
$\mathcal{O}_{C}$. In the case that $\mathfrak{h}$ is equal to $\mathfrak{f}$,
a two-sided ideal of a maximal $\mathcal{O}$-order $\mathcal{M}$ in $A$
containing $\Lambda$, the desired algorithm is described in [BHJ22, §6.6]
(this is a minor modification of [BB06, §3.4–3.7]). This relies crucially on
the computation of the primary decomposition of $\mathfrak{g}$, which can be
accomplished using work of Bley–Endres [BE05] under the assumption that
$\Gamma=\mathcal{O}_{C}$ (which must hold when $\mathfrak{h}=\mathfrak{f}$).
In fact, the computation of the primary decomposition of $\mathfrak{g}$ is the
only obstacle to generalising the algorithm to arbitrary choices of
$\mathfrak{h}$. By removing the restriction that $\Gamma=\mathcal{O}_{C}$ on
the computation of primary decompositions in Corollary 11.3, we thereby obtain
an algorithm for the computation of generators of
$(\Lambda/\mathfrak{h})^{\times}$ for arbitrary proper full two-sided ideals
$\mathfrak{h}$ of $\Lambda$. ∎

###  11.3. Group structure of unit groups of finite rings

Let $\overline{\Lambda}=\Lambda/\mathfrak{h}$. Then $\overline{\Lambda}$ is a
finite ring and an important challenge to compute its units
$\overline{\Lambda}^{\times}$ as an abstract group. The point is that,
although we can compute generators of $\overline{\Lambda}^{\times}$ by
Corollary 11.4, we require a representation of $\overline{\Lambda}^{\times}$
that will allow us to efficiently determine the group-theoretic properties
required for applications, such as the computation of the abelianisation
$\overline{\Lambda}^{\times\mathrm{ab}}$. Specifically, representations which
are useful for actual computations include realisations of
$\overline{\Lambda}^{\times}$ as a subgroup of either
$\mathrm{GL}_{n}(\mathbb{F}_{q})$ for some finite field $\mathbb{F}_{q}$, or
of symmetric groups $\mathfrak{S}_{d}$, both of course with reasonable sizes
for $n$ and $\lvert k\rvert$, or $d$, respectively (see [HEO05]).

Let $\mathrm{Aut}_{\mathbb{Z}}(\overline{\Lambda})$ denote the group of
$\mathbb{Z}$-linear automorphisms of the (additive) $\mathbb{Z}$-module
$\overline{\Lambda}$. Consider the injective homomorphism

$\overline{\Lambda}^{\times}\longrightarrow\mathrm{Aut}_{\mathbb{Z}}(\overline{\Lambda}),\quad
x\longmapsto(y\mapsto xy).$

Since we assume that we can compute generators of
$\overline{\Lambda}^{\times}$, the problem is reduced to finding a suitable
representation for $\mathrm{Aut}_{\mathbb{Z}}(\overline{\Lambda})$. We now
describe two ways in which this can be achieved in practice.

  1. (i)

If $\overline{\Lambda}$ is a free $\mathbb{Z}/n\mathbb{Z}$-algebra of rank $k$
for some $n,k\in\mathbb{Z}_{>0}$, then after choosing a
$\mathbb{Z}/n\mathbb{Z}$-basis we have an isomorphism
$\mathrm{Aut}_{\mathbb{Z}}(\overline{\Lambda})\cong\mathrm{GL}_{k}(\mathbb{Z}/n\mathbb{Z})$.
If we further assume that $n$ is equal to a prime $p$, then this in turn
yields a realisation of $\overline{\Lambda}^{\times}$ as a subgroup of
$\mathrm{GL}_{k}(\mathbb{F}_{p})$.

  2. (ii)

Generators of $\mathrm{Aut}_{\mathbb{Z}}(\overline{\Lambda})$ can be computed
using results of Shoda [Sho28]. These can be used to determine a faithful
permutation representation (see [CH03])
$\mathrm{Aut}_{\mathbb{Z}}(\overline{\Lambda})\longrightarrow\mathfrak{S}_{d}$
for some $d\in\mathbb{Z}_{>0}$, which in turn yields a representation of
$\overline{\Lambda}^{\times}$ as a permutation group.

In general, the method of (i) allows computations to be performed more
efficiently than the method of (ii), but of course the method of (i) is not
always possible. We also note that if $\overline{\Lambda}$ can be written as a
direct product of rings $R_{1}\times\cdots\times R_{s}$, then

$\overline{\Lambda}^{\times}=(R_{1}\times\cdots\times
R_{s})^{\times}=R_{1}^{\times}\times\cdots\times R_{s}^{\times}$

and so either of the above methods can be applied to each component $R_{i}$
individually, which is more efficient than applying either method to
$\overline{\Lambda}$ directly.

##  12\. Improved freeness testing for generalised Swan modules

###  12.1. Setup

Let $K$ be a number field with ring of integers $\mathcal{O}=\mathcal{O}_{K}$,
and let $A$ be a finite-dimensional semisimple $K$-algebra. Let $\Lambda$ be
an $\mathcal{O}$-order in $A$ and let $\mathcal{M}$ be a maximal
$\mathcal{O}$-order in $A$ containing $\Lambda$. Recall from Definition 8.1
that for $\beta\in\mathcal{M}\cap A^{\times}$, the generalised Swan module
$X_{\beta}=X_{\beta,\Lambda,\mathcal{M}}$ is defined to be
$\mathcal{M}\beta\cap\Lambda$.

Algorithms 8.9, 9.1 and 10.2 for determining whether $\Lambda$ has SFC each
rely on the ability to check whether a given (stably free) $\Lambda$-lattice
of the form $X_{\beta}$ is in fact free over $\Lambda$. As explained in the
further details of Step (11) of Algorithm 8.9, in principle, this can be
performed using [BJ11, Algorithm 3.1]. However, this is only practical when
$A$ is of ‘moderate’ dimension. In this section, we shall present a modified
freeness test under assumptions of the following paragraph.

Henceforth assume that $A$ admits a decomposition $A=A_{1}\oplus A_{2}$ of
$K$-algebras such that $A_{1}$ satisfies the Eichler condition. In
applications, we can always assume that $A_{2}\neq 0$ is a direct sum of
totally positive quaternion algebras. If $A_{1}=0$ then we need to use a
slight modification of [BJ11, Algorithm 3.1] as discussed in the further
details of Step (11) of Algorithm 8.9.

Let $e_{1},e_{2}\in A$ be the central idempotents such that $A_{i}=e_{i}A$ for
$i=1,2$. Let $C$ denote the centre of $A$ and let $\mathcal{O}_{C}$ denote the
(unique) maximal $\mathcal{O}$-order in $C$. Let $\mathfrak{f}$ be any proper
full two-sided ideal of $\mathcal{M}$ that is contained in $\Lambda$ and let
$\mathfrak{g}=\mathfrak{f}\cap\mathcal{O}_{C}$. Then the central idempotents
$e_{1}$ and $e_{2}$ induce decompositions

$\mathcal{M}=\mathcal{M}_{1}\oplus\mathcal{M}_{2},\quad\mathfrak{f}=\mathfrak{f}_{1}\oplus\mathfrak{f}_{2},\quad
C=C_{1}\oplus
C_{2},\quad\mathcal{O}_{C}=\mathcal{O}_{C_{1}}\oplus\mathcal{O}_{C_{2}},\quad\mathfrak{g}=\mathfrak{g}_{1}\oplus\mathfrak{g}_{2}.$

For $i=1,2$ let $T_{i}$ denote the image of
$\mathcal{M}_{i}^{\times}\longrightarrow\left(\mathcal{M}/\mathfrak{f}_{i}\right)^{\times}$
and note that $T:=T_{1}\times T_{2}$ is the image of
$\mathcal{M}^{\times}\longrightarrow(\mathcal{M}/\mathfrak{f})^{\times}$.

###  12.2. Criteria for certain ideals to be free

We shall consider left ideals $X$ of $\Lambda$ with the following two
properties: $X+\mathfrak{f}=\Lambda$ and there exists $\beta\in\mathcal{M}\cap
A^{\times}$ such that $\mathcal{M}X=\mathcal{M}\beta$. Note that by
Proposition 8.3, the generalised Swan modules $X_{\beta}$ considered in
Algorithms 8.9, 9.1 and 10.2 always satisfy both these properties.

######  Lemma 12.1.

Let $X$ be a left ideal of $\Lambda$. Suppose that $X+\mathfrak{f}=\Lambda$
and that there exists $\beta\in\mathcal{M}\cap A^{\times}$ such that
$\mathcal{M}X=\mathcal{M}\beta$. Write
$\beta=(\beta_{1},\beta_{2})\in\mathcal{M}_{1}\oplus\mathcal{M}_{2}$. Then the
following are equivalent:

  1. (i)

$X$ is free over $\Lambda$,

  2. (ii)

there exists $\overline{\alpha}\in(\Lambda/\mathfrak{f})^{\times}$ such that
$\overline{\beta}\overline{\alpha}\in T$,

  3. (iii)

there exist $\overline{\alpha}_{2}\in\overline{\beta}_{2}^{-1}T_{2}$ and
$\overline{\alpha}_{1}\in(\mathcal{M}_{1}/\mathfrak{f}_{1})^{\times}$ such
that

$(\overline{\alpha}_{1},\overline{\alpha}_{2})\in(\Lambda/\mathfrak{f})^{\times}\text{
and }\overline{\beta}_{1}\overline{\alpha}_{1}\in T_{1}.$

###### Proof.

The equivalence of (i) and (ii) follows from Proposition 7.1. Statement (iii)
is just an immediate reformulation of (ii). ∎

[BJ11, Algorithm 3.1] essentially uses the the equivalence of conditions (i)
and (ii) in Lemma 12.1 to reduce the freeness test to an enumeration over the
set $T$ of cardinality $\lvert T\rvert=\lvert T_{1}\rvert\cdot\lvert
T_{2}\rvert$. In the following, we show how condition (iii) can be used to
replace this by an enumeration over $T_{2}$ and computations related to the
reduced norm.

By [BHJ22, Lemma 4.4], there exists a surjective group homomorphism
$\overline{\mathrm{nr}}$ that fits into the commutative diagram

$\textstyle{\mathcal{M}_{1}^{\times}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathrm{nr}}$$\textstyle{\mathcal{O}_{C_{1}}^{\times}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{(\mathcal{M}_{1}/\mathfrak{f}_{1})^{\times}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\overline{\mathrm{nr}}}$$\textstyle{(\mathcal{O}_{C_{1}}/\mathfrak{g}_{1})^{\times},}$
(12.1)

where the vertical maps are induced by the canonical projections. For $i=1,2$,
let $\pi_{i}:\Lambda\longrightarrow\mathcal{M}_{i}$ denote the canonical
projection and set $\pi_{i}(\Lambda):=\Lambda_{i}$. Hence we can and do also
consider $\pi_{i}$ as a map $\pi_{i}\colon:\Lambda\longrightarrow\Lambda_{i}$,
depending on context. Note that in fact
$\mathfrak{h}_{i}:=\Lambda\cap\mathcal{M}_{i}$ is a two-sided ideal of
$\Lambda_{1}\oplus\Lambda_{2}$ contained in $\Lambda$.

Each $\pi_{i}$ induces a group homomorphism

$\overline{\pi}_{i}\colon(\Lambda/\mathfrak{f})^{\times}\longrightarrow(\Lambda_{i}/\mathfrak{f}_{i})^{\times},$
(12.2)

which is surjective by [Bas68, Chapter III, (2.9) Corollary]. Let
$\Sigma=\ker(\overline{\pi}_{2})$ and let

$S:=\overline{\mathrm{nr}}(\overline{\pi}_{1}(\Sigma))=\left\\{\overline{\mathrm{nr}}(\overline{\gamma}_{1})\mid\exists\overline{\gamma}_{2}\in(\Lambda_{2}/\mathfrak{f}_{2})^{\times}:(\overline{\gamma}_{1},\overline{\gamma}_{2})\in\Sigma\right\\}.$
(12.3)

Then $S$ is a subgroup of
$\left(\mathcal{O}_{C_{1}}/\mathfrak{g}_{1}\right)^{\times}$ by definition and

$\displaystyle S$
$\displaystyle=\left\\{\overline{\mathrm{nr}}(\overline{\gamma}_{1})\mid\overline{\gamma}_{1}\in\left(\mathcal{M}_{1}/\mathfrak{f}_{1}\right)^{\times}\text{
and
}(\overline{\gamma}_{1},\overline{1})\in\left(\Lambda/\mathfrak{f}\right)^{\times}\right\\},$
$\displaystyle=\left\\{\overline{\mathrm{nr}}(\overline{\gamma}_{1})\mid\overline{\gamma}_{1}\in\left(\mathcal{M}_{1}/\mathfrak{f}_{1}\right)^{\times}\text{
and }(\gamma_{1},1)\in\Lambda\right\\}$

where the first equality follows from (12.3) and the second follows from the
fact that
$(\Lambda/\mathfrak{f})^{\times}=(\mathcal{M}/\mathfrak{f})^{\times}\cap(\Lambda/\mathfrak{f})$
(see [Kar92, Chapter I, Theorem 7.9(iii)]). Let $\sigma$ denote the following
composition of canonical maps

$\mathcal{O}_{C_{1}}^{\times}\longrightarrow\left(\mathcal{O}_{C_{1}}/\mathfrak{g}_{1}\right)^{\times}\longrightarrow\left(\mathcal{O}_{C_{1}}/\mathfrak{g}_{1}\right)^{\times}/S.$

######  Lemma 12.2.

Let $X$ be a left ideal of $\Lambda$. Suppose that $X+\mathfrak{f}=\Lambda$
and that there exists $\beta\in\mathcal{M}\cap A^{\times}$ such that
$\mathcal{M}X=\mathcal{M}\beta$. Then
$\overline{\beta}\in\left(\mathcal{M}/\mathfrak{f}\right)^{\times}$. Write
$\beta=(\beta_{1},\beta_{2})\in\mathcal{M}_{1}\oplus\mathcal{M}_{2}$. Let
$\overline{\alpha}_{2}\in\overline{\beta}_{2}^{-1}T_{2}$ and assume that
$\overline{\gamma}_{1}\in\left(\mathcal{M}_{1}/\mathfrak{f}_{1}\right)^{\times}$
satisfies
$(\overline{\gamma}_{1},\overline{\alpha}_{2})\in\left(\Lambda/\mathfrak{f}\right)^{\times}$.
Then the following are equivalent:

  1. (i)

There exists
$\overline{\alpha}_{1}\in\left(\mathcal{M}_{1}/\mathfrak{f}_{1}\right)^{\times}$
such that
$(\overline{\alpha}_{1},\overline{\alpha}_{2})\in(\Lambda/\mathfrak{f})^{\times}\text{
and }\overline{\beta}_{1}\overline{\alpha}_{1}\in T_{1}$,

  2. (ii)

$\overline{\mathrm{nr}}(\overline{\beta}_{1}\overline{\gamma}_{1})\bmod{S}\in\mathrm{im}(\sigma)$.

Moreover, if these equivalent conditions hold, then $X$ is free over
$\Lambda$.

###### Proof.

We have
$\mathcal{M}=\mathcal{M}(X+\mathfrak{f})=\mathcal{M}X+\mathfrak{f}=\mathcal{M}\beta+\mathfrak{f}$,
and so $\overline{\beta}\in(\mathcal{M}/\mathfrak{f})^{\times}$.

Assume that (i) holds. Then by definition of $T_{1}$ there exists
$u_{1}\in\mathcal{M}_{1}^{\times}$ such that
$\overline{\mathrm{nr}}(\overline{\beta}_{1}\overline{\alpha}_{1})=\overline{\mathrm{nr}}(\overline{u}_{1})=\overline{\epsilon}_{1}$
in $\left(\mathcal{O}_{C_{1}}/\mathfrak{g}_{1}\right)^{\times}$, where
$\epsilon_{1}:=\mathrm{nr}({u}_{1})$. Hence
$\overline{\mathrm{nr}}((\overline{\beta}_{1}\overline{\gamma}_{1})(\overline{\gamma}_{1}^{-1}\overline{\alpha}_{1}))=\overline{\epsilon}_{1}$
and it remains to show that
$\overline{\mathrm{nr}}(\overline{\gamma}_{1}^{-1}\overline{\alpha}_{1})\in
S$. This in turn is a consequence of

$(\overline{\gamma}_{1}^{-1}\overline{\alpha}_{1},\overline{1})=(\overline{\gamma}_{1}^{-1}\overline{\alpha}_{1},\overline{\alpha}_{2}^{-1}\overline{\alpha}_{2})=(\overline{\gamma}_{1},\overline{\alpha}_{2})^{-1}(\overline{\alpha}_{1},\overline{\alpha}_{2})\in\left(\Lambda/\mathfrak{f}\right)^{\times}.$

Assume now that (ii) holds. Then there exists a unit
$\epsilon_{1}\in\mathcal{O}_{C_{1}}^{\times}$ and an element
$(\overline{\delta}_{1},\overline{1})\in\left(\Lambda/\mathfrak{f}\right)^{\times}$
such that
$\overline{\mathrm{nr}}(\overline{\beta}_{1}\overline{\gamma}_{1}\overline{\delta}_{1})=\overline{\epsilon}_{1}$
in $\left(\mathcal{O}_{C_{1}}/\mathfrak{g}_{1}\right)^{\times}$. By Eichler’s
Theorem on units [CR87, (51.34)] there exists
$u_{1}\in\mathcal{M}_{1}^{\times}$ such that
$\overline{\beta}_{1}\overline{\gamma}_{1}\overline{\delta}_{1}=\overline{u}_{1}$,
that is, $\overline{\beta}_{1}\overline{\gamma}_{1}\overline{\delta}_{1}\in
T_{1}$. Since
$(\overline{\gamma}_{1}\overline{\delta}_{1},\overline{\alpha}_{2})=(\overline{\gamma}_{1},\overline{\alpha}_{2})(\overline{\delta}_{1},\overline{1})\in\left(\Lambda/\mathfrak{f}\right)^{\times}$
we may take
$\overline{\alpha}_{1}:=\overline{\gamma}_{1}\overline{\delta}_{1}$.

The final assertion follows immediately from Lemma 12.1. ∎

######  Proposition 12.3.

Let $X$ be a left ideal of $\Lambda$. Suppose that $X+\mathfrak{f}=\Lambda$
and that there exists $\beta\in\mathcal{M}\cap A^{\times}$ such that
$\mathcal{M}X=\mathcal{M}\beta$. Then the following statements hold.

  1. (i)

$X$ is free over $\Lambda$ if and only if there exist
$\overline{\alpha}_{2}\in\overline{\beta}_{2}^{-1}T_{2}$ and
$\overline{\gamma}_{1}\in\left(\mathcal{M}_{1}/\mathfrak{f}_{1}\right)^{\times}$
such that
$(\overline{\gamma}_{1},\overline{\alpha}_{2})\in\left(\Lambda/\mathfrak{f}\right)^{\times}$
and
$\overline{\mathrm{nr}}(\overline{\beta}_{1}\overline{\gamma}_{1})\in\mathrm{im}(\sigma)$.

  2. (ii)

Fix $\overline{\alpha}_{2}\in\overline{\beta}_{2}^{-1}T_{2}$. Suppose there
exists
$\overline{\gamma}_{1}\in\left(\mathcal{M}_{1}/\mathfrak{f}_{1}\right)^{\times}$
such that
$(\overline{\gamma}_{1},\overline{\alpha}_{2})\in\left(\Lambda/\mathfrak{f}\right)^{\times}$
and
$\overline{\mathrm{nr}}(\overline{\beta}_{1}\overline{\gamma}_{1})\in\mathrm{im}(\sigma)$.
Then for every
$\overline{\mu}_{1}\in\left(\mathcal{M}_{1}/\mathfrak{f}_{1}\right)^{\times}$
such that
$(\overline{\mu}_{1},\overline{\alpha}_{2})\in\left(\Lambda/\mathfrak{f}\right)^{\times}$,
we have
$\overline{\mathrm{nr}}(\overline{\beta}_{1}\overline{\mu}_{1})\in\mathrm{im}(\sigma)$.

###### Proof.

(i) Suppose that $X$ is free over $\Lambda$. Then by Lemma 12.1 there exist
$\overline{\alpha}_{2}\in\overline{\beta}_{2}^{-1}T_{2}$ and
$\overline{\alpha}_{1}\in(\mathcal{M}_{1}/\mathfrak{f}_{1})^{\times}$ such
that
$(\overline{\alpha}_{1},\overline{\alpha}_{2})\in(\Lambda/\mathfrak{f})^{\times}\text{
and }\overline{\beta}_{1}\overline{\alpha}_{1}\in T_{1}$. Moreover,
$\overline{\mathrm{nr}}(\overline{\beta}_{1}\overline{\alpha}_{1})\bmod
S\in\mathrm{im}(\sigma)$ by Lemma 12.2, and so we may take
$\overline{\gamma}_{1}=\overline{\alpha}_{1}$. The converse holds again by
Lemma 12.2.

(ii) The elements $\overline{\beta}_{1}$ and $\overline{\gamma}_{1}$ satisfy
Lemma 12.2 (ii). Thus Lemma 12.2 (i) holds, and this is independent of
$\overline{\gamma}_{1}$. Thus if
$\overline{\mu}_{1}\in\left(\mathcal{M}_{1}/\mathfrak{f}_{1}\right)^{\times}$
also satisfies
$(\overline{\mu}_{1},\overline{\alpha}_{2})\in\left(\Lambda/\mathfrak{f}\right)^{\times}$,
then Lemma 12.2 (ii) applied to $\overline{\mu}_{1}$ implies that
$\overline{\mathrm{nr}}(\overline{\beta}_{1}\overline{\mu}_{1})\bmod
S\in\mathrm{im}(\sigma)$. ∎

######  Lemma 12.4.

Let $\alpha_{2}\in\mathcal{M}_{2}$ with
$\overline{\alpha}_{2}\in\left(\mathcal{M}_{2}/\mathfrak{f}\right)^{\times}$.
The following are equivalent:

  1. (i)

There exists an element
$\overline{\gamma}_{1}\in(\mathcal{M}_{1}/\mathfrak{f}_{1})^{\times}$ such
that
$(\overline{\gamma}_{1},\overline{\alpha}_{2})\in\left(\Lambda/\mathfrak{f}\right)^{\times}$,

  2. (ii)

$\pi_{2}^{-1}(\\{\alpha_{2}\\})\neq\emptyset$, where
$\pi_{2}\colon\Lambda\longrightarrow\mathcal{M}_{2}$ is the canonical
projection.

###### Proof.

It is clear that (i) implies (ii). Suppose that (ii) holds. Then there exists
$\alpha_{1}\in\mathcal{M}_{1}$ such that $(\alpha_{1},\alpha_{2})\in\Lambda$.
Thus $\alpha_{2}\in\Lambda_{2}$. By assumption
$\overline{\alpha}_{2}\in(\mathcal{M}_{2}/\mathfrak{f}_{2})^{\times}$ and
hence
$\overline{\alpha}_{2}\in\left(\Lambda_{2}/\mathfrak{f}_{2}\right)^{\times}$
since
$(\Lambda_{2}/\mathfrak{f}_{2})^{\times}=(\mathcal{M}_{2}/\mathfrak{f}_{2})^{\times}\cap(\Lambda_{2}/\mathfrak{f}_{2})$
(see [Kar92, Chapter I, Theorem 7.9(iii)]). Since the canonical map
$\overline{\pi}_{2}\colon(\Lambda/\mathfrak{f})^{\times}\longrightarrow(\Lambda_{2}/\mathfrak{f}_{2})^{\times}$
of (12.2) is surjective, this completes the proof. ∎

######  Algorithm 12.5.

Suppose that $A_{1}$ is Eichler and that every simple component of $A_{2}$ is
a totally definite quaternion algebra. Let $X$ be a left ideal of $\Lambda$.
Suppose that $X+\mathfrak{f}=\Lambda$ and that there exists
$\beta\in\mathcal{M}\cap A^{\times}$ such that
$\mathcal{M}X=\mathcal{M}\beta$. Write
$\beta=(\beta_{1},\beta_{2})\in\mathcal{M}_{1}\oplus\mathcal{M}_{2}$. If $X$
is free over $\Lambda$ then the following algorithm returns $\mathsf{true}$;
otherwise it returns $\mathsf{false}$.

  1. (1)

Compute $T_{2}$.

  2. (2)

Compute $S$.

  3. (3)

Compute $\mathrm{im}(\sigma)$.

  4. (4)

For each $\overline{\alpha}_{2}\in\overline{\beta}_{2}^{-1}T_{2}$ do the
following:

    1. (a)

Compute
$\overline{\gamma}_{1}\in\left(\mathcal{M}_{1}/\mathfrak{f}_{1}\right)^{\times}$
such that
$(\overline{\gamma}_{1},\overline{\alpha}_{2})\in\left(\Lambda/\mathfrak{f}\right)^{\times}$
or, if no such $\overline{\gamma}_{1}$ exists, continue with the next
$\overline{\alpha}_{2}$.

    2. (b)

If
$\overline{\mathrm{nr}}(\overline{\beta}_{1}\overline{\gamma}_{1})\in\mathrm{im}(\sigma)$,
return $\mathsf{true}$.

  5. (5)

Return $\mathsf{false}$.

###### Proof of correctness.

The correctness of the output follows from Proposition 12.3. ∎

###### Further details on each step.

Step (1): This can be performed as described in [BJ11, §7].

Step (2): Although the sets $\Sigma$ and $S$ are finite and can be found by
enumerating $(\Lambda/\mathfrak{f})^{\times}$ and
$(\mathcal{M}_{1}/\mathfrak{f}_{1})^{\times}$, respectively, this is
impractical. We present a practical algorithm for computing $\Sigma$ and $S$
in §12.3.

Step (3): This is straightforward given the output of step (2) and standard
algorithms from computational algebraic number theory (see [Coh00]).

Step 4(a): For a given
$\overline{\alpha}_{2}\in(\mathcal{M}_{2}/\mathfrak{f}_{2})^{\times}$ we can
determine whether there exists
$\overline{\gamma}_{1}\in(\mathcal{M}_{1}/\mathfrak{f}_{1})^{\times}$ such
that
$(\overline{\gamma}_{1},\overline{\alpha}_{2})\in(\Lambda/\mathfrak{f})^{\times}$
(and find such an element if it does exist) as follows. The canonical
projection $\pi_{2}\colon\Lambda\longrightarrow\mathcal{M}_{2}$ is a ring
homomorphism and hence a homomorphism of the underlying finitely generated
abelian groups. Thus we can check condition (ii) of Lemma 12.4 and find
$\delta_{1}\in\mathcal{M}_{1}$ with $(\delta_{1},\alpha_{2})\in\Lambda$ if it
exists (see [Coh00, §4.1]). Note that
$(\overline{\delta}_{1},\overline{\alpha}_{2})\in\Lambda/\mathfrak{f}$ maps to
$\overline{\alpha}_{2}\in(\Lambda_{2}/\mathfrak{f}_{2})^{\times}$ under the
canonical map
$\tilde{\pi}_{2}\colon\Lambda/\mathfrak{f}\to\Lambda_{2}/\mathfrak{f}_{2}$,
but this preimage of $\overline{\alpha}_{2}$ is not necessarily a unit. Since
$\tilde{\pi}_{2}$ is a homomorphism of finite abelian groups, we can determine
random elements of $\ker(\tilde{\pi}_{2})$ and thus of
$(\overline{\delta}_{1},\overline{\alpha}_{2})+\ker(\tilde{\pi}_{2})=\tilde{\pi}_{2}^{-1}(\\{\overline{\alpha}_{2}\\})$
until we have found an invertible preimage.

Step 4(b): This can be performed using the commutative diagram (12.1) and
standard algorithms for finitely generated abelian groups, as presented for
example in [Coh00, §4.1], for example.

Step (5) is trivial. ∎

######  Remark 12.6.

Compared to [BJ11, Algorithm 3.1] where the size of the enumeration set is
essentially the cardinality of the image of the canonical map
$\mathcal{M}^{\times}\longrightarrow\left(\mathcal{M}/\mathfrak{f}\right)^{\times}$,
that is, $\lvert T_{1}\rvert\cdot\lvert T_{2}\rvert$, the enumeration set in
Algorithm 12.12 is of size $\lvert T_{2}\rvert$, and hence only depends on the
component $A_{2}$. Note that $T_{2}$ can be computed as explained in [BJ11,
§4.5] (see also [KV10, Remark 7.5]), and this is much faster than computing
the image of $\mathcal{M}\longrightarrow(\mathcal{M}/\mathfrak{f})^{\times}$
for $\mathcal{M}$ a maximal $\mathcal{O}$-order in an arbitrary finite-
dimensional semisimple $K$-algebra.

###  12.3. Computation of $S$

Recall the definition of $S$ given in (12.3). Since we require only generators
of $S$, it will be enough to consider the computation of (generators of)
$\Sigma=\ker(\overline{\pi}_{2})$. Recall that
$\mathfrak{h}_{1}=\Lambda\cap\mathcal{M}_{1}$ and consider the two-sided ideal
$\tilde{\mathfrak{f}}:=\mathfrak{h}_{1}+\mathfrak{f}=\mathfrak{h}_{1}\oplus\mathfrak{f}_{2}$.
Let

$\overline{\pi}\colon(\Lambda/\mathfrak{f})^{\times}\longrightarrow(\Lambda/\tilde{\mathfrak{f}})^{\times}$

denote the canonical map, which is surjective by [Bas68, Chapter III, (2.9)
Corollary].

######  Lemma 12.7.

We have $\Sigma=\ker(\overline{\pi})$.

###### Proof.

Since the composition
$\Lambda\stackrel{{\scriptstyle\pi_{2}}}{{\longrightarrow}}\Lambda_{2}\longrightarrow\Lambda_{2}/\mathfrak{f}_{2}$
is surjective with kernel $\tilde{\mathfrak{f}}$, we obtain an isomorphism
$\overline{\tau}\colon(\Lambda/\tilde{\mathfrak{f}})^{\times}\longrightarrow(\Lambda_{2}/\mathfrak{f}_{2})^{\times}$
making the diagram

${(\Lambda/\tilde{\mathfrak{f}})^{\times}}$${(\Lambda/\mathfrak{f})^{\times}}$${(\Lambda_{2}/\mathfrak{f}_{2})^{\times}}$$\scriptstyle{\overline{\tau}}$$\scriptstyle{\overline{\pi}}$$\scriptstyle{\overline{\pi}_{2}}$

commute. The claim now follows from $\Sigma=\ker(\overline{\pi}_{2})$. ∎

######  Lemma 12.8.

There exist coprime primary ideals
$\\{\mathfrak{q}_{1},\dotsc,\mathfrak{q}_{r+s}\\}$ and
$\\{\tilde{\mathfrak{q}}_{1},\dotsc,\tilde{\mathfrak{q}}_{r}\\}$ of
$\Lambda\cap C$ such that the following hold:

  1. (i)

we have $\mathfrak{q}_{i}\subseteq\tilde{\mathfrak{q}}_{i}$ for $1\leq i\leq
r$,

  2. (ii)

we have

$\Lambda/\mathfrak{f}\cong\prod_{i=1}^{r+s}\Lambda/(\mathfrak{q}_{i}\Lambda+\mathfrak{f})\quad\text{and}\quad\Lambda/\tilde{\mathfrak{f}}\cong\prod_{i=1}^{r}\Lambda/(\tilde{\mathfrak{q}}_{i}\Lambda+\tilde{\mathfrak{f}}),$

  3. (iii)

we have

$\Sigma\cong\prod_{i=1}^{r}\ker(\tau_{i})\times\prod_{i=1}^{s}(\Lambda/(\mathfrak{q}_{r+i}\Lambda+\mathfrak{f}))^{\times},$

where
$\tau_{i}\colon(\Lambda/(\mathfrak{q}_{i}\Lambda+\mathfrak{f}))^{\times}\longrightarrow(\Lambda/(\tilde{\mathfrak{q}}_{i}\Lambda+\tilde{\mathfrak{f}}))^{\times}$
are the canonical surjections.

###### Proof.

Consider $\mathfrak{g}=\mathfrak{f}\cap C$ and
$\tilde{\mathfrak{g}}=\mathfrak{\tilde{f}}\cap C$, which are full
$(\Lambda\cap C)$-ideals with $\mathfrak{g}\subseteq\tilde{\mathfrak{g}}$. Let
$\mathfrak{p}_{1},\dotsc,\mathfrak{p}_{r}$ and
$\mathfrak{p}_{1},\dotsc,\mathfrak{p}_{r+s}$ be the maximal ideals of
$\Lambda\cap C$ containing $\tilde{\mathfrak{g}}$ and $\mathfrak{g}$
respectively. Let now $\mathfrak{g}=\prod_{i=1}^{r+s}\mathfrak{q_{i}}$ be a
primary decomposition, where $\mathfrak{q}_{i}$ is $\mathfrak{p}_{i}$-primary
for $1\leq i\leq r+s$. Since the $\mathfrak{p}_{i}$ are maximal, it is clear
that for each $1\leq i\leq r$ also $\mathfrak{q}_{i}+\mathfrak{\tilde{g}}$ is
$\mathfrak{p}_{i}$-primary. Thus
$\tilde{\mathfrak{g}}=\mathfrak{g}+\tilde{\mathfrak{g}}=\prod_{i=1}^{r+s}\mathfrak{q}_{i}+\tilde{\mathfrak{g}}=\prod_{i=1}^{r}\tilde{\mathfrak{q}}_{i}$
is a primary decomposition of $\tilde{\mathfrak{g}}$, where
$\tilde{\mathfrak{q_{i}}}:=\mathfrak{q}_{i}+\tilde{\mathfrak{g}}$ is
$\mathfrak{p}_{i}$-primary for $1\leq i\leq r$. This immediately shows (i).
For (ii), note that [BB06, 3.5 Lemma] implies that

$\mathfrak{f}=\bigcap_{i=1}^{r+s}(\mathfrak{q}_{i}\Lambda+\mathfrak{f})\quad\text{
and
}\quad\tilde{\mathfrak{f}}=\bigcap_{i=1}^{r}(\tilde{\mathfrak{q}}_{i}\Lambda+\tilde{\mathfrak{f}}),$

thus the claim follows from the Chinese remainder theorem. Finally, (iii)
follows from (ii) together with Lemma 12.7. ∎

Since we know how to compute generators for each of the groups
$\left(\Lambda/(\mathfrak{q}_{r+i}\Lambda+\mathfrak{f})\right)^{\times}$ by
the results of §11.2, it remains to consider the computation of
$\ker(\tau_{i})$ for $i=1,\ldots,r$. Each element in $\ker(\tau_{i})$ is the
image in $(\Lambda/(\mathfrak{q}_{i}\Lambda+\mathfrak{f}))^{\times}$ of an
element of the form $1+\lambda$ with
$\lambda\in(\tilde{\mathfrak{q}}_{i}\Lambda+\tilde{\mathfrak{f}})$. Note,
however, that not every element in
$1+(\tilde{\mathfrak{q}}_{i}\Lambda+\tilde{\mathfrak{f}})$ is actually a unit
mod $(\mathfrak{q}_{i}\Lambda+\mathfrak{f})$.

######  Lemma 12.9.

Let $\mathfrak{p}$ be a maximal ideal of $\Lambda\cap C$, let $\mathfrak{q}$
and $\tilde{\mathfrak{q}}$ be two $\mathfrak{p}$-primary ideals of
$\Lambda\cap C$ with ${\mathfrak{q}}\subseteq\tilde{\mathfrak{q}}$ and let

$\tau\colon(\Lambda/(\mathfrak{q}\Lambda+\mathfrak{f}))^{\times}\longrightarrow(\Lambda/(\tilde{\mathfrak{q}}\Lambda+\tilde{\mathfrak{f}}))^{\times}$

the canonical projection. Furthermore set

$\tilde{\mathfrak{Q}}:=\tilde{\mathfrak{q}}\Lambda+\tilde{\mathfrak{f}},\quad\mathfrak{Q}_{1}:=\tilde{\mathfrak{q}}\Lambda+\mathfrak{f},\quad\mathfrak{Q}:=\mathfrak{q}\Lambda+\mathfrak{f}.$

Then the following hold:

  1. (i)

for every $\alpha\in\Lambda$ we have

$\alpha\text{ is invertible mod }\mathfrak{Q}\iff\alpha\text{ is invertible
mod }\mathfrak{Q}_{1}.$

  2. (ii)

Identifying $(1+\tilde{\mathfrak{Q}})$ and $(1+\mathfrak{Q}_{1})$ with their
images in $\Lambda/\mathfrak{Q}$ we have
$\ker(\tau)=(1+\tilde{\mathfrak{Q}})\cap\left(\Lambda/\mathfrak{Q}\right)^{\times}$
and the sequence

$0\longrightarrow\frac{1+\mathfrak{Q}_{1}}{1+\mathfrak{Q}}\longrightarrow\ker(\tau)\longrightarrow\frac{(1+\tilde{\mathfrak{Q}})\cap\left(\Lambda/\mathfrak{Q}\right)^{\times}}{1+\mathfrak{Q}_{1}}\longrightarrow
0$

is exact.

###### Proof.

(i) Since both $\tilde{\mathfrak{q}}$ and $\mathfrak{q}$ are
$\mathfrak{p}$-primary, there exists $m>0$ such that
$\tilde{\mathfrak{q}}^{m}\subseteq\mathfrak{q}$. Hence
$\mathfrak{Q}_{1}^{m}\subseteq\mathfrak{Q}$ and every element of
$\mathfrak{Q}_{1}/\mathfrak{Q}$ is nilpotent in $\Lambda/\mathfrak{Q}$. If
$\lambda$ is invertible mod $\mathfrak{Q}_{1}$, then there exist
$\mu\in\Lambda$ and $\xi\in\mathfrak{Q}_{1}$ such that $\lambda\mu=1-\xi$.
Thus in $\Lambda/\mathfrak{Q}$ we have
$\overline{\lambda}\overline{\mu}\cdot\sum_{n=0}^{\infty}\overline{\xi}^{n}=(\overline{1}-\overline{\xi})\cdot\sum_{n=0}^{\infty}\overline{\xi}^{n}=\overline{1}$.
The converse is clear. (ii) now follows easily from (i). ∎

######  Remark 12.10.

In conjunction with Lemma 12.8, Lemma 12.9 yields the following method for
computing generators of $\Sigma$ (and hence of $S$). Primary decompositions in
$\Lambda\cap C$ can be determined using Corollary 11.3 and thus a
decomposition

$\Sigma\cong\prod_{i=1}^{r}\ker(\tau_{i})\times\prod_{i=1}^{s}(\Lambda/(\mathfrak{q}_{r+i}\Lambda+\mathfrak{f}))^{\times},$

with suitable primary ideals $\mathfrak{q}_{i},\tilde{\mathfrak{q}}_{i}$ as in
Lemma 12.8 (iii) can be obtained. For the groups
$(\Lambda/(\mathfrak{q}_{r+i}\Lambda+\mathfrak{f}))^{\times}$, generators can
be obtained by Corollary 11.4 and thus it suffices to determine each
$\ker(\tau_{i})$. For $1\leq i\leq r$ we set $\tau:=\tau_{i}$ and fix the
notation as in Lemma 12.9. Since

$1\longrightarrow\frac{1+\mathfrak{Q}_{1}}{1+\mathfrak{Q}}\longrightarrow\ker(\tau)\longrightarrow\frac{(1+\tilde{\mathfrak{Q}})\cap\left(\Lambda/\mathfrak{Q}\right)^{\times}}{1+\mathfrak{Q}_{1}}\longrightarrow
1$ (12.4)

is exact, it suffices to find generators for the first and third group.
Generators for $\frac{1+\mathfrak{Q}_{1}}{1+\mathfrak{Q}}$ can be computed as
in [BB06, §3.7]. For the computation of generators of the non-trivial group on
the right hand side of (12.4), the elements can be listed as follows:
determine the set of representatives of
$\tilde{\mathfrak{Q}}/\mathfrak{Q}_{1}$ and check for each such representative
$\alpha$ whether $1+\alpha$ it is a unit mod $\mathfrak{Q}$.

###  12.4. A probabilistic algorithm

In the previous section, the computation of $\Sigma$ respectively $S$ was
reduced to the problem of enumerating all elements of quotients of the form
$\tilde{\mathfrak{Q}}/\mathfrak{Q}_{1}$ for two-sided $\Lambda$-ideals
$\tilde{\mathfrak{Q}}$ and $\mathfrak{Q}_{1}$. Since the order of
$\tilde{\mathfrak{Q}}/\mathfrak{Q}_{1}$ can be quite large, we present a
probabilistic approach, which avoids enumeration. We assume that
$S^{\prime}\subseteq S$ is a subgroup and consider the following composition,
which we denote by $\sigma^{\prime}$:

$\mathcal{O}_{C_{1}}^{\times}\longrightarrow\left(\mathcal{O}_{C_{1}}/\mathfrak{g}_{1}\right)^{\times}\longrightarrow{\left(\mathcal{O}_{C_{1}}/\mathfrak{g}_{1}\right)^{\times}}/S^{\prime}.$

Replacing $S$ by $S^{\prime}$ in Lemma 12.2, we obtain the following weaker
statement.

######  Lemma 12.11.

Let $X$ be a left ideal of $\Lambda$. Suppose that $X+\mathfrak{f}=\Lambda$
and that there exists $\beta\in\mathcal{M}\cap A^{\times}$ such that
$\mathcal{M}X=\mathcal{M}\beta$. Write
$\beta=(\beta_{1},\beta_{2})\in\mathcal{M}_{1}\oplus\mathcal{M}_{2}$. Let
$\overline{\alpha}_{2}\in\overline{\beta}_{2}^{-1}T_{2}$ and assume that
$\overline{\gamma}_{1}\in\left(\mathcal{M}_{1}/\mathfrak{f}_{1}\right)^{\times}$
satisfies
$(\overline{\gamma}_{1},\overline{\alpha}_{2})\in\left(\Lambda/\mathfrak{f}\right)^{\times}$.
If
$\overline{\mathrm{nr}}(\overline{\beta}_{1}\overline{\gamma}_{1})\in\mathrm{im}(\sigma^{\prime})$,
then $X$ is free over $\Lambda$.

This yields the following probabilistic variant of Algorithm 12.12.

######  Algorithm 12.12.

Suppose that $A_{1}$ is Eichler and that every simple component of $A_{2}$ is
a totally definite quaternion algebra. Let $X$ be a left ideal of $\Lambda$.
Suppose that $X+\mathfrak{f}=\Lambda$ and that there exists
$\beta\in\mathcal{M}\cap A^{\times}$ such that
$\mathcal{M}X=\mathcal{M}\beta$. If the following algorithm returns
$\mathsf{true}$, then $X$ is free over $\Lambda$; if returns
$\mathsf{inconclusive}$, then nothing can be said about whether $X$ is free
over $\Lambda$ or not.

  1. (1)

Compute $T_{2}$.

  2. (2)

Compute $S^{\prime}$.

  3. (3)

Compute $\mathrm{im}(\sigma^{\prime})$.

  4. (4)

For each $\overline{\alpha}_{2}\in\overline{\beta}_{2}^{-1}T_{2}$ do the
following:

    1. (a)

Compute
$\overline{\gamma}_{1}\in\left(\mathcal{M}_{1}/\mathfrak{f}_{1}\right)^{\times}$
such that
$(\overline{\gamma}_{1},\overline{\alpha}_{2})\in\left(\Lambda/\mathfrak{f}\right)^{\times}$
or, if no such $\overline{\gamma}_{1}$ exists, continue with the next
$\overline{\alpha}_{2}$.

    2. (b)

If
$\overline{\mathrm{nr}}(\overline{\beta}_{1}\overline{\gamma}_{1})\in\mathrm{im}(\sigma^{\prime})$,
return $\mathsf{true}$.

  5. (5)

Return $\mathsf{inconclusive}$.

###### Proof of correctness.

The correctness of the output follows from Lemma 12.11. ∎

###### Further details on each step.

Apart from Step (2), all steps are the essentially the same as in Algorithm
12.12. Step (2) can be performed as follows. Recall that
$S=\overline{\mathrm{nr}}(\overline{\pi}_{1}(\Sigma))$. Thus in order to find
a subgroup $S^{\prime}$ of $S$ it is sufficient to find a subgroup of

$\Sigma=\ker((\Lambda/\mathfrak{f})^{\times}\longrightarrow(\Lambda_{2}/\mathfrak{f}_{2})^{\times})).$

Random elements of $\Sigma$ can be found by sampling preimages of
$\overline{1}\in\Lambda_{2}/\mathfrak{f}_{2}$ under the canonical map
$\Lambda/\mathfrak{f}\longrightarrow\Lambda_{2}/\mathfrak{f}_{2}$ (a
homomorphism of finitely generated abelian groups) and discarding the non-
invertible elements. In this way we obtain a sequence of elements
$(\overline{\alpha}_{i})_{i\in\mathbb{Z}_{\geq 1}}$ in $\Sigma$ and determine
$S^{\prime}:=\langle\overline{\mathrm{nr}}(\bar{\pi}_{1}(\bar{\alpha}_{i}))\mid
i\leq B\rangle$, where $B\in\mathbb{Z}_{\geq 1}$ is either a fixed
predetermined bound or chosen dynamically until $S^{\prime}$ stabilises. ∎

##  13\. Further results on SFC for integral group rings

######  Theorem 13.1.

Let $G$ be one of the following finite groups:

$\tilde{T}\times C_{2},\,\tilde{T}\times Q_{12},\,\tilde{T}\times
Q_{20},\,Q_{8}\rtimes\tilde{T},\,G_{(96,66)},\,G_{(192,183)},\,G_{(480,962)}.$

Then $\mathbb{Z}[G]$ has SFC.

###### Proof.

The result for $\tilde{T}\times C_{2}$ is Theorem 6.6. Note that
$\tilde{T}\times Q_{12}$ and $\tilde{T}\times Q_{20}$ both have quotients
isomorphic to $\tilde{T}\times C_{2}$, so Theorem 6.6 can be recovered from
Lemma 4.1 and the result for either $\tilde{T}\times Q_{12}$ or
$\tilde{T}\times Q_{20}$.

For $G=G_{(96,66)}$, $\tilde{T}\times Q_{12}$ or $\tilde{T}\times Q_{20}$,
there exists a normal subgroup $N$ of order $2$, such that $H:=G/N$ is
isomorphic to $\mathrm{GL}_{2}(\mathbb{F}_{3})$, $G_{(144,127)}$, or
$G_{(280,108)}$, respectively. In each case, $\mathbb{Q}[H]$ satisfies the
Eichler condition and hence so does $\mathbb{Q}[H\times C_{2}]$. Thus
$\mathbb{Z}[H\times C_{2}]$ has LFC by Theorem 3.4. Let
$\Gamma=\mathbb{Z}[G]/\mathrm{Tr}_{N}\mathbb{Z}[G]$. The cardinalities of the
locally free class groups of $\mathbb{Z}[H]$, $\mathbb{Z}[G]$,
$\mathbb{Z}[H\times C_{2}]$ and $\Gamma$ can be computed using the the
algorithm of [BB06, §3], and thus it can be verified that Proposition 6.10 can
be applied to show that $\mathbb{Z}[G]$ has SFC if only if $\Gamma$ has SFC.

For $G=Q_{8}\rtimes\tilde{T}\cong G_{(192,1022)}$, there is a normal subgroup
$N$ of order $2$ such that $H:=G/N$ is isomorphic to $G_{(96,204)}$. It can
easily be checked that $\mathbb{Q}[H]$ satisfies the Eichler condition. Let
$\Gamma=\mathbb{Z}[G]/\mathrm{Tr}_{N}\mathbb{Z}[G]$. Unfortunately,
Proposition 6.10 cannot be applied in this situation because the required
equality (6.3) does not hold. However, $\mathbb{Z}[G]$ can be shown to have
SFC if and only if $\Gamma$ has SFC by an application of Algorithm 10.3 with
$\Lambda_{1}=\mathbb{Z}[H]$ and $\Lambda_{2}=\Gamma$. Note that
$\overline{\Lambda}=\mathbb{F}_{2}[H]$, and so an explicit embedding of
$\overline{\Lambda}^{\times}$ into $\mathrm{GL}_{96}(\mathbb{F}_{2})$ can be
determined as explained in Remark 6.3 (see also §11.3). Crucially, this allows
computations in $\overline{\Lambda}^{\times}$ to be performed reasonably
efficiently.

Therefore, for $G=G_{(96,66)}$, $G_{(192,1022)}$, $\tilde{T}\times Q_{12}$, or
$\tilde{T}\times Q_{20}$, we have shown that $\mathbb{Z}[G]$ has SFC if and
only if $\Gamma$ has SFC. This is highly advantageous from a computational
point of view, since
$\dim_{\mathbb{Q}}\mathbb{Q}\otimes_{\mathbb{Z}}\Gamma=\frac{1}{2}\dim_{\mathbb{Q}}\mathbb{Q}[G]=\frac{1}{2}|G|$.
To verify that $\Gamma$ has SFC, we again apply Algorithm 10.3, this time with
the fibre product induced by the decomposition
$\mathbb{Q}\otimes_{\mathbb{Z}}\Gamma=B_{1}\oplus B_{2}$, with $B_{1}$ the
largest component of $\mathbb{Q}\otimes_{\mathbb{Z}}\Gamma$ satisfying the
Eichler condition (equivalently, with $B_{2}$ the largest component that is
the direct sum of totally definite quaternion algebras). Computations in
$\overline{\Lambda}^{\times}$ are performed by first computing an explicit
embedding into the symmetric group $\mathfrak{S}_{d}$ for some
$d\in\mathbb{Z}_{>0}$ (see §11.3). This is less efficient than working with an
embedding into $\mathrm{GL}_{n}(\mathbb{F}_{p})$ for appropriate choices of
$n$ and $p$, but such an embedding does not exist in general.

For $G=G_{(192,183)}$ or $G_{(480,962)}$, there exists a normal subgroup $N$
of such that $H:=G/N\cong G_{(96,66)}$ and so $\mathbb{Z}[H]$ has SFC by the
result for $G_{(96,66)}$. Let
$\Gamma=\mathbb{Z}[G]/\mathrm{Tr}_{N}\mathbb{Z}[G]$. It can easily be checked
that $\mathbb{Q}\otimes_{\mathbb{Z}}\Gamma$ satisfies the Eichler condition
and thus $\Gamma$ has LFC by Theorem 3.4. Then $\mathbb{Z}[G]$ can be shown to
have SFC by an application of Algorithm 10.3 with $\Lambda_{1}=\Gamma$ and
$\Lambda_{2}=\mathbb{Z}[H]$. Note that $\overline{\Lambda}=\mathbb{F}_{p}[H]$
for $p=2$ or $5$, which allows computations in $\overline{\Lambda}^{\times}$
to be performed reasonably efficiently, as explained above. ∎

######  Theorem 13.2.

Let $G$ be a finite group with $|G|\leq 1023$. Let

$\Sigma=\\{3595,3599,3704,3716,3719,3721,3722,4179,4487,4490,5069,8602,8604,8614\\}.$

Suppose that $G$ is not isomorphic to any of the following groups:

  1. (a)

$G_{(384,m)}$ for $m\in\\{572,577,579,5867,18129,18229\\}$,

  2. (b)

$G_{(576,m)}$ for $m\in\\{1447,2006\\}$,

  3. (c)

$G_{(768,m+1080000)}$ for $n\in\Sigma$,

  4. (d)

$G_{(864,m)}$ for $m\in\\{717,731,732,3021\\}$, or

  5. (e)

$G_{(960,805)}$.

Then $\mathbb{Z}[G]$ has SFC if and only if $G$ has no quotient isomorphic to

  1. (i)

$Q_{4n}\times C_{2}$ for $2\leq n\leq 5$,

  2. (ii)

$\tilde{T}\times C_{2}^{2}$, $\tilde{O}\times C_{2}$, $\tilde{I}\times C_{2}$,

  3. (iii)

$G_{(32,14)}$, $G_{(36,7)}$, $G_{(64,14)}$, $G_{(100,7)}$, or

  4. (iv)

$Q_{4n}$ for $6\leq n\leq 255$.

###### Proof.

We use the GAP [GAP24] small groups database [BEO02], which in particular,
contains all finite groups $G$ with $|G|\leq 1023$. For each such $G$, we
first check whether $\mathbb{Z}[G]$ has SFC by Theorems 4.5, 4.10, 4.11, and
13.1, as well as Corollary 6.9. We then check whether $G$ has a quotient
isomorphic to any of the groups listed in (i), (ii), (iii), or (iv), in which
case $\mathbb{Z}[G]$ fails SFC by Corollary 9.7. These checks can easily be
implemented as a program in GAP [GAP24] or Magma [BCP97]. For
$G_{(480,256)}\cong C_{5}\times G_{(96,66)}$, $G_{(576,7442)}\cong
C_{3}\times(Q_{8}\rtimes\tilde{T})$, and $G_{(960,9669)}\cong
C_{5}\times(Q_{8}\rtimes\tilde{T})$, combination of Theorems 4.6 and 13.1
shows that $\mathbb{Z}[G]$ has SFC. The remaining groups consist of all those
listed in (a)–(e). ∎

######  Corollary 13.3.

Let $G$ be a finite group with $|G|\leq 383$. Then $\mathbb{Z}[G]$ has SFC if
and only if $G$ has no quotient of the form

  1. (i)

$Q_{4n}\times C_{2}$ for $2\leq n\leq 5$,

  2. (ii)

$\tilde{T}\times C_{2}^{2}$, $\tilde{O}\times C_{2}$, $\tilde{I}\times C_{2}$,

  3. (iii)

$G_{(32,14)}$, $G_{(36,7)}$, $G_{(64,14)}$, $G_{(100,7)}$, or

  4. (iv)

$Q_{4n}$ for $6\leq n\leq 95$.

## References

  * [ADOS87] R. C. Alperin, R. K. Dennis, R. Oliver, and M. R. Stein, _$SK_{1}$ of finite abelian groups. II_, Invent. Math. 87 (1987), no. 2, 253–302.
  * [AM69] M. F. Atiyah and I. G. Macdonald, _Introduction to commutative algebra_ , Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969.
  * [Bas65] H. Bass, _The Dirichlet unit theorem, induced characters, and Whitehead groups of finite groups_ , Topology 4 (1965), 391–410.
  * [Bas68] by same author, _Algebraic $K$-theory_, W. A. Benjamin, Inc., New York-Amsterdam, 1968.
  * [BB06] W. Bley and R. Boltje, _Computation of locally free class groups_ , Algorithmic Number Theory (F. Hess, S. Pauli, and M. Pohst, eds.), Lecture Notes in Computer Science, no. 4076, Springer, 2006, pp. 72–86.
  * [BCNS15] O. Braun, R. Coulangeon, G. Nebe, and S. Schönnenbeck, _Computing in arithmetic groups with Voronoï’s algorithm_ , J. Algebra 435 (2015), 263–285.
  * [BCP97] W. Bosma, J. Cannon, and C. Playoust, _The Magma algebra system. I. The user language_ , vol. 24, 1997, Computational algebra and number theory (London, 1993), pp. 235–265.
  * [BE05] W. Bley and W. Endres, _Picard groups and refined discrete logarithms_ , LMS J. Comput. Math. 8 (2005), 1–16.
  * [BEO02] H. U Besche, B. Eick, and E. A. O’Brien, _A millennium project: constructing small groups_ , Internat. J. Algebra Comput. 12 (2002), no. 5, 623–644.
  * [BHJ22] W. Bley, T. Hofmann, and H. Johnston, _Computation of lattice isomorphisms and the integral matrix similarity problem_ , Forum Math. Sigma 10 (2022), Paper No. e87, 36.
  * [BJ11] W. Bley and H. Johnston, _Computing generators of free modules over orders in group algebras II_ , Math. Comp. 80 (2011), no. 276, 2411–2434.
  * [CH03] J. J. Cannon and D. F. Holt, _Automorphism group computation and isomorphism testing in finite groups_ , J. Symbolic Comput. 35 (2003), no. 3, 241–267.
  * [Che86] H.-F. Chen, _The locally free cancellation property of the group ring $\mathbb{Z}[G]$_, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1986\.
  * [Coh00] H. Cohen, _Advanced topics in computational number theory_ , Graduate Texts in Mathematics, vol. 193, Springer-Verlag, New York, 2000.
  * [Cou94] J. Cougnard, _Un anneau d’entiers stablement libre et non libre_ , Experiment. Math. 3 (1994), no. 2, 129–136.
  * [Cou98] by same author, _Anneaux d’entiers stablement libres sur $\mathbb{Z}[H_{8}\times C_{2}]$_, J. Théor. Nombres Bordeaux 10 (1998), no. 1, 163–201. MR 1827291
  * [CR81] C. W. Curtis and I. Reiner, _Methods of representation theory. Vol. I_ , John Wiley & Sons, Inc., New York, 1981.
  * [CR87] by same author, _Methods of representation theory. Vol. II_ , Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1987.
  * [DEF+24] W. Decker, C. Eder, C. Fieker, M. Horn, and M. Joswig (eds.), _The Computer Algebra System OSCAR: Algorithms and Examples_ , 1 ed., Algorithms and Computation in Mathematics, vol. 32, Springer, 8 2024.
  * [FR85] K. Friedl and L. Ronyai, _Polynomial time solutions of some problems in computational algebra_ , pp. 153–162, ACM, 1985.
  * [Fri00] C. Friedrichs, _Berechnung von Maximalordnungen über Dedekindringen_ , Ph.D. thesis, Technische Universität Berlin, 2000.
  * [Frö75] A. Fröhlich, _Locally free modules over arithmetic orders_ , J. Reine Angew. Math. 274(275) (1975), 112–124.
  * [GAP24] The GAP Group, _GAP – Groups, Algorithms, and Programming, Version 4.13.0_ , 2024.
  * [HEO05] D. F. Holt, B. Eick, and E. A. O’Brien, _Handbook of computational group theory_ , Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2005.
  * [HM06] E. Hallouin and C. Maire, _Cancellation in totally definite quaternion algebras_ , J. Reine Angew. Math. 595 (2006), 189–213.
  * [Jac68] H. Jacobinski, _Genera and decompositions of lattices over orders_ , Acta Math. 121 (1968), 1–29.
  * [Joh03] F. E. A. Johnson, _Stable modules and the $D(2)$-problem_, London Mathematical Society Lecture Note Series, vol. 301, Cambridge University Press, Cambridge, 2003.
  * [Kar92] G. Karpilovsky, _Group representations. Vol. 1. Part A_ , North-Holland Mathematics Studies, vol. 175, North-Holland Publishing Co., Amsterdam, 1992, Background material.
  * [KV10] M. Kirschmer and J. Voight, _Algorithmic enumeration of ideal classes for quaternion orders_ , SIAM J. Comput. 39 (2010), no. 5, 1714–1747.
  * [Len92] H. W. Lenstra, Jr., _Algorithms in algebraic number theory_ , Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 2, 211–244.
  * [MS22] S. Maheshwari and R.K. Sharma, _A note on units in $\mathbb{F}_{q}\mathrm{SL}(2,\mathbb{Z}_{3})$_, Ukr Math J 73 (2022), 1331–1337.
  * [Neu99] J. Neukirch, _Algebraic number theory_ , Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 322, Springer-Verlag, Berlin, 1999, Translated from the 1992 German original and with a note by Norbert Schappacher, With a foreword by G. Harder.
  * [Nic20] J. Nicholson, _Cancellation for $(G,n)$-complexes and the swan finiteness obstruction_, arXiv:2005.01664, 2020.
  * [Nic21a] by same author, _A cancellation theorem for modules over integral group rings_ , Math. Proc. Cambridge Philos. Soc. 171 (2021), no. 2, 317–327.
  * [Nic21b] by same author, _On CW-complexes over groups with periodic cohomology_ , Trans. Amer. Math. Soc. 374 (2021), no. 9, 6531–6557.
  * [Nic24] by same author, _The cancellation property for projective modules over integral group rings_ , arXiv:2406.08692, 2024.
  * [NS09] G. Nebe and A. Steel, _Recognition of division algebras_ , J. Algebra 322 (2009), no. 3, 903–909.
  * [Oli81] R. Oliver, _$SK_{1}$ for finite group rings. III_, Algebraic $K$-theory, Evanston 1980 (Proc. Conf., Northwestern Univ., Evanston, Ill., 1980), Lecture Notes in Math., vol. 854, Springer, Berlin, 1981, pp. 299–337.
  * [Oli88] by same author, _Whitehead groups of finite groups_ , London Mathematical Society Lecture Note Series, vol. 132, Cambridge University Press, Cambridge, 1988.
  * [OSC24] _Oscar – open source computer algebra research system, version 1.0.0_ , 2024\.
  * [Rei03] I. Reiner, _Maximal orders_ , London Mathematical Society Monographs, vol. 28, The Clarendon Press Oxford University Press, Oxford, 2003.
  * [RS91] J. Ritter and S. K. Sehgal, _Construction of units in integral group rings of finite nilpotent groups_ , Trans. Amer. Math. Soc. 324 (1991), no. 2, 603–621.
  * [RU74] I. Reiner and S. Ullom, _A Mayer-Vietoris sequence for class groups_ , J. Algebra 31 (1974), 305–342.
  * [Sho28] K. Shoda, _Über die Automorphismen einer endlichen Abelschen Gruppe_ , Math. Ann. 100 (1928), no. 1, 674–686.
  * [Sme15] D. Smertnig, _A note on cancellation in totally definite quaternion algebras_ , J. Reine Angew. Math. 707 (2015), 209–216.
  * [SV19] D. Smertnig and J. Voight, _Definite orders with locally free cancellation_ , Trans. London Math. Soc. 6 (2019), no. 1, 53–86.
  * [Swa80] R. G. Swan, _Strong approximation and locally free modules_ , Ring theory and algebra, III (Proc. Third Conf., Univ. Oklahoma, Norman, Okla., 1979), Lecture Notes in Pure and Appl. Math., vol. 55, Dekker, New York, 1980, pp. 153–223.
  * [Swa83] by same author, _Projective modules over binary polyhedral groups_ , J. Reine Angew. Math. 342 (1983), 66–172.
  * [Vig76] M.-F. Vignéras, _Simplification pour les ordres des corps de quaternions totalement définis_ , J. Reine Angew. Math. 286(287) (1976), 257–277.
  * [Wal74] C. T. C. Wall, _Norms of units in group rings_ , Proc. London Math. Soc. (3) 29 (1974), 593–632.