# A binary invariant of matrix mutation

Roger Casals  University of California Davis, Dept. of Mathematics, USA
<EMAIL_ADDRESS>
###### Abstract.

We construct a binary mutation invariant for skew-symmetric integer matrices.
The invariant is not an integer congruence invariant for matrices of odd size:
we provide examples of congruent such matrices with different values for the
invariant.

###### 2010 Mathematics Subject Classification:

Primary: 13F60. Secondary: 15A15.

##  1\. Introduction

The object of this note will be to construct a binary mutation invariant for
skew-symmetric integer matrices. The invariant is not a congruence invariant
over $\mathbb{Z}$ for integer matrices of odd size. Namely, for any odd
number, there are skew-symmetric integer matrices of that size which are
congruent over $\mathbb{Z}$ and yet their binary invariants differ.

Scientific context. Let $M_{n}(\mathbb{Z})$ denote the set of $n\times n$
integer matrices. Let $B\in M_{n}(\mathbb{Z})$ be an $n\times n$ skew-
symmetric integer matrix. The first definition of matrix mutation in the
mathematical literature is [FZ02, Section 4] and we follow the
presentation111Matrix mutation is defined more generally for skew-
symmetrizable matrices, cf. [FWZ, Section 2.7]. From loc. cit., rank is
preserved under mutation by [BFZ05, Lemma 3.2]. In this note we focus on
(square) skew-symmetric matrices. in [FWZ, Section 2.7]. Let $k\in[n]$ be the
column index at which we mutate. Consider the following two matrices
$J_{k,n},E_{k,n}\in M_{n}(\mathbb{Z})$:

  * -

$J_{k,n}$ denotes the diagonal matrix of size $n\times n$ whose diagonal
entries are all $1$, except for the $(k,k)$ entry, which is $-1$.

  * -

$E_{k,n}=(e_{ij})$ is the $n\times n$ matrix with
$e_{ik}:=\mbox{max}(0,-b_{ik})$ for all $i\in[n]$ and all other entries equal
to 0.

Let us denote $M_{k}:=J_{k,n}+E_{k,n}$, which depends on $k\in[n]$ and $B$. We
refer to $M_{k}$ as the replicating matrix of $B$ at $k\in[n]$. By definition,
the mutation of $B$ at $k$ is the matrix

$\mu_{k}(B):=M_{k}\cdot B\cdot M_{k}^{t}.$

The mutated matrix $\mu_{k}(B)$ is skew-symmetric and thus mutation can be
iterated. Note that mutation at $k$ is involutive, i.e.
$\mu_{k}(\mu_{k}(B))=B$ for any $k\in[n]$. Typically $\mu_{l}(\mu_{k}(B))\neq
B$ if $l\neq k$, $l,k\in[n]$. Two matrices $B_{1},B_{2}\in M_{n}(\mathbb{Z})$
are said to be equal up to a simultaneous permutation of rows and columns if
there exists a permutation matrix $P\in M_{n}(\mathbb{Z})$ such that
$B_{2}=P\cdot B_{1}\cdot P^{t}$. We use the following definition from [FWZ,
Definition 2.8.1]:

######  Definition 1.1.

Two skew-symmetric matrices $B,B^{\prime}\in M_{n}(\mathbb{Z})$ are mutation
equivalent if one can get from $B$ to $B^{\prime}$ by a sequence of mutations,
possibly followed by a simultaneous permutation of rows and columns. $\Box$

Definition 1.1 must be put in contrast with the following notion:

######  Definition 1.2.

Two integer matrices $B,B^{\prime}\in M_{n}(\mathbb{Z})$ are said to be
congruent over $\mathbb{Z}$ if there exists a unimodular matrix $X\in
M_{n}(\mathbb{Z})$ such that $B^{\prime}=X\cdot B\cdot X^{t}$. $\Box$

Throughout this note, congruent always means congruent using only unimodular
matrices $X\in M_{n}(\mathbb{Z})$ with integer entries, as in Definition 1.2
above: e.g. non-integer entries in $\mathbb{Q},\mathbb{R}$ or $\mathbb{C}$ are
not allowed for such $X$. It follows from Definition 1.1 that two skew-
symmetric matrices $B,B^{\prime}\in M_{n}(\mathbb{Z})$ that are mutation
equivalent must be congruent in $M_{n}(\mathbb{Z})$, over $\mathbb{Z}$, as in
Definition 1.2. Therefore, any invariant of congruence (over $\mathbb{Z}$) is
an invariant of mutation. The invariant factors of the Smith normal form (thus
the determinant), and the rank are congruence invariants, see [New97].222The
greatest common divisor of the matrix entries in each column is also a
mutation invariant. The present note is an attempt to use linear algebra to
construct an invariant of matrix mutation that is not an invariant of matrix
congruence over $\mathbb{Z}$.

For $n=2$, mutation negates the entries of the matrix $B$ for any
$k\in\\{1,2\\}$. It is thus immediate to decide whether $B,B^{\prime}\in
M_{2}(\mathbb{Z})$ are mutation equivalent. The article [ABBS08] presents an
algorithm for determining whether two $3\times 3$ skew-symmetric matrices are
mutation equivalent, addressing the $n=3$ case. As per usual, the finite type
case is better understood, cf. [FWZ, Chapter 5], e.g. [FWZ, Theorem
5.11.3.(4)]: the goal is to start exploring the general case, beyond the
finite or affine cases. See also the recent work [FN23] on long mutation
cycles. Beyond what is listed above, and properties such as the existence of a
reddening sequence or a rigid potential [DWZ10, Corollary 8.10], the author
knows of no general mutation invariant, which is not a congruence invariant
(over $\mathbb{Z}$), for higher $n\geq 4$. We believe this to be an important
problem relevant to the theory of cluster algebras, cf. [FWZ, Problem 2.8.2]
and [Fom, Slide 9].

The $\delta$-invariant and main result. Let $B\in M_{n}(\mathbb{Z})$ be an
$n\times n$ skew-symmetric integer matrix with entries $B=(b_{ij})$,
$i,j\in[n]$. Consider the unipotent matrix $V(B)\in M_{n}(\mathbb{Z})$ defined
by

$V(B)_{i,j}:=\begin{cases}b_{ij}&\text{ if }i<j\\\ 1&\text{ if }i=j\\\
0&\text{ if }i>j\\\ \end{cases}$

This matrix satisfies $B=V(B)-V(B)^{t}$ because $B$ is skew-symmetric.
Similarly, consider the symmetric matrix $\mathfrak{S}(B)\in
M_{n}(\mathbb{Z})$ defined by $\mathfrak{S}(B):=V(B)+V(B)^{t}$. In the
notation of [FWZ, Definition 5.11.2], $\mathfrak{S}(B)$ is a quasi-Cartan
companion of $B$.

######  Definition 1.3.

Let $B\in M_{n}(\mathbb{Z})$ be an $n\times n$ skew-symmetric integer matrix.
By definition, the $\delta$-invariant $\delta(B)$ of $B$ is

$\delta(B):=\det(\mathfrak{S}(B))\pmod{4}.$

That is, $\delta(B)$ is the determinant of $\mathfrak{S}(B)$ modulo 4. $\Box$

######  Remark 1.4.

For $n\in\mathbb{Z}$ odd, the $\delta$-invariant is binary valued:
$\delta(B)\equiv 0,2\pmod{4}$ if $n$ is odd. Indeed, $\mathfrak{S}(B)\equiv
B\pmod{2}$ and $\det(B)\equiv 0\pmod{2}$ because $\det(B)=0$, over
$\mathbb{Z}$, as $B$ is skew-symmetric. Therefore $\delta(B)$ is always even
in this case. For $n\in\mathbb{Z}$ even, computations indicate that the
$\delta$-invariant might still be binary: for $n\equiv 0\pmod{4}$, then
$\delta(B)\equiv 0,1\pmod{4}$ and for $n\equiv 2\pmod{4}$, then
$\delta(B)\equiv 0,3\pmod{4}$. $\Box$

The following property, showing that the $\delta$-invariant remains unchanged
under simultaneous permutation of rows and columns, will be proven in Section
2.2.

######  Lemma 1.5.

Let $B\in M_{n}(\mathbb{Z})$ be an $n\times n$ skew-symmetric integer matrix.
Then, for any permutation matrix $P\in M_{n}(\mathbb{Z})$, the equality
$\delta(PBP^{t})\equiv\delta(B)\pmod{4}$ holds. $\Box$

The main result of this article reads as follows:

######  Theorem 1.6.

Let $B\in M_{n}(\mathbb{Z})$ be an $n\times n$ skew-symmetric integer matrix.
If $B^{\prime}\in M_{n}(\mathbb{Z})$ is mutation equivalent to $B$, then

$\delta(B^{\prime})\equiv\delta(B)\pmod{4}.$

$\Box$

Theorem 1.6 is proven in Section 2.3. In contrast to Theorem 1.6, we show that
this $\delta$-invariant is not a congruence invariant over $\mathbb{Z}$ if
$n\in\mathbb{Z}$ is odd:

######  Proposition 1.7.

Let $n\in\mathbb{Z}$ be odd, $n\geq 3$. Then, there exist two skew-symmetric
integer matrices $B,B^{\circ}\in M_{n}(\mathbb{Z})$ such that:

  * (i)

$B$ and $B^{\circ}$ are congruent over $\mathbb{Z}$, i.e. $\exists X\in
M_{n}(\mathbb{Z})$ unimodular such that $B^{\circ}=X\cdot B\cdot X^{t}$,

  * (ii)

$\delta(B)\not\equiv\delta(B^{\circ})\pmod{4}$.

Proposition 1.7 is proven in Section 3.2. A computer randomly generating two
congruent skew-symmetric matrices of odd size quickly finds examples of such
$B,B^{\circ}$ with different $\delta$-invariants.333The author has implemented
such computer calculations in SageMath, see Appendix (Section 4). I do not
know of two congruent skew-symmetric integer matrices of even size with
different $\delta$-invariants.

Acknowledgements. We thank M. Sherman-Bennett and D. Weng for helpful
comments. We are grateful to S. Fomin for useful feedback on an initial draft.
R. Casals is supported by the NSF CAREER DMS-1942363, a Sloan Research
Fellowship of the Alfred P Sloan Foundation and a UC Davis College of L&S
Dean’s Fellowship. $\Box$

Notation. We denote $[n]:=\\{1,2,\ldots,n\\}\subset\mathbb{N}$ and write
$M_{n}(\mathbb{Z})$ for the set of $n\times n$ integer matrices. The
determinant and trace of a matrix $A$ are respectively denoted $\det(X)$ and
$\operatorname{tr}(X)$. The transpose of a matrix $X$ is denoted by $X^{t}$
and its adjugate by $\mbox{adj}(X)$. $\Box$

##  2\. Invariance properties of $\delta(B)$

In this section we prove Lemma 1.5 and Theorem 1.6, concluding that the
$\delta$-invariant is an invariant of matrix mutation. Invariance under
simultaneous permutations of rows and columns is established in Subsection
2.2. Mutation invariance is proven in Subsection 2.3.

###  2.1. Three lemmas about matrices

The arguments we present to prove Lemma 1.5 and Theorem 1.6 use the following
three lemmas. Lemmas 2.1 and 2.3 are general linear algebra, not to do with
matrix mutation. Lemma 2.2 uses features specific to matrix mutation and
replicating matrices.

######  Lemma 2.1.

Let $Z\in M_{n}(\mathbb{Z})$ be a skew-symmetric. Suppose that $V,W\in
M_{n}(\mathbb{Z})$ satisfy $Z=V-V^{t}$ and $Z=W-W^{t}$. The $V-W$ is
symmetric.

###### Proof.

This follows from $(V-W)^{t}=V^{t}-W^{t}=(V-Z)+(Z-W)=V-W$. ∎

######  Lemma 2.2.

Let $B\in M_{n}(\mathbb{Z})$ be an $n\times n$ skew-symmetric integer matrix
and $M_{k}$ its matrix replicating matrix at $k\in[n]$. Then the $i$th
diagonal term $\tau_{ii}$, $i\in[n]$, of the difference

$M_{k}\cdot\mathfrak{S}(B)\cdot M_{k}^{t}-\mathfrak{S}(\mu_{k}(B))$

is of the form $\tau_{ii}=2t_{ii}$ where

$t_{ii}:=\begin{cases}(b_{ik}+\max(0,b_{ik}))\max(0,b_{ik})&\text{ if }i<k,\\\
\qquad\qquad\qquad 0&\text{ if }i=k,\\\
(b_{ik}+\max(0,-b_{ik}))\max(0,-b_{ik})&\text{ if }i>k.\end{cases}$

In particular, $t_{ii}\equiv 0\pmod{2}$ and $\tau_{ii}\equiv 0\pmod{4}$ for
all $i\in[n]$.

###### Proof.

Consider the unipotent matrix $V(B)$ and $M_{k}$: we first compute the
diagonal entries of $M_{k}\cdot V(B)\cdot M_{k}^{t}$. The diagonal entries of
$A:=V(B)\cdot M_{k}^{t}$ are as follows:

$A_{ii}=\begin{cases}b_{ik}\max(0,b_{ik})+1&\text{ if }i<k,\\\
\qquad\quad-1&\text{ if }i=k,\\\ \qquad\quad 1&\text{ if }i>k,\end{cases}$

for $i\in[n]$. The $k$th row of $A$ is the transpose of the $k$th column of
$M_{k}$, i.e. $A_{ki}=\mbox{max}(0,-b_{ik})$ for $i\in[n]$. Since $M_{k}$
coincides with the identity away from the $k$th column, the diagonal entries
of $A$ and its $k$th row suffice to compute the diagonal entries of the
product $M_{k}A=M_{k}V(B)M_{k}^{t}$. These diagonal entries of
$M_{k}V(B)M_{k}^{t}$ are:

$(M_{k}V(B)M_{k}^{t})_{ii}=\begin{cases}(b_{ik}+\max(0,b_{ik}))\max(0,b_{ik})+1&\text{
if }i<k,\\\ \qquad\qquad\qquad 1&\text{ if }i=k,\\\
(b_{ik}+\max(0,-b_{ik}))\max(0,-b_{ik})+1&\text{ if }i>k.\end{cases}$

The diagonal entries of $V(\mu_{k}(B))$ are all 1, as this is a unipotent
matrix. Therefore, the diagonal entries of the difference
$M_{k}V(B)M_{k}^{t}-V(\mu_{k}(B))$ are:

$(M_{k}V(B)M_{k}^{t}-V(\mu_{k}(B)))_{ii}=\begin{cases}(b_{ik}+\max(0,b_{ik}))\max(0,b_{ik})&\text{
if }i<k,\\\ \qquad\qquad\qquad 0&\text{ if }i=k,\\\
(b_{ik}+\max(0,-b_{ik}))\max(0,-b_{ik})&\text{ if }i>k.\end{cases}$

Since $\mathfrak{S}(B)=V(B)+V(B)^{t}$ and
$\mathfrak{S}(\mu_{k}(B))=V(\mu_{k}(B))+V(\mu_{k}(B))^{t}$, the diagonal terms
$\tau_{ii}$ of the difference $M_{k}\cdot\mathfrak{S}(B)\cdot
M_{k}^{t}-\mathfrak{S}(\mu_{k}(B))$ are twice the diagonal terms of the
difference $M_{k}V(B)M_{k}^{t}-V(\mu_{k}(B))$. This proves the required
identity in the statement for the diagonal terms $\tau_{ii}$.

In order to conclude that $t_{ii}$ is even, and thus $\tau_{ii}\equiv
0\pmod{4}$ for all $i\in[n]$, it suffices to note that

$(b_{ik}+\max(0,b_{ik}))\max(0,b_{ik})\equiv\begin{cases}(b_{ik}+0)\cdot
0\equiv 0&\text{ if }\max(0,b_{ik})=0,\\\ \qquad\quad 2b_{ik}^{2}&\text{ if
}\max(0,b_{ik})\neq 0.\end{cases}$

Therefore $t_{ii}$ is always even in either case and $\tau_{ii}\equiv
0\pmod{4}$ for all $i\in[n]$. The argument for $i>k$, i.e. showing
$(b_{ik}+\max(0,-b_{ik}))\max(0,-b_{ik})\equiv 0\pmod{2}$ and thus
$\tau_{ii}\equiv 0\pmod{4}$, is identical. ∎

######  Lemma 2.3.

Let $Y\in M_{n}(\mathbb{Z})$ a symmetric matrix. Suppose that $Y$ has all
diagonal terms equal to zero, i.e. $Y=(y_{ij})$ satisfies $y_{ii}=0$ for all
$i\in[n]$. Then:

  1. (1)

$\operatorname{tr}(XY)\equiv 0\pmod{2}$ for any symmetric matrix $X\in
M_{n}(\mathbb{Z})$, i.e. $\operatorname{tr}(XY)$ is even if $X=X^{t}$.

  2. (2)

$\det(R)\equiv\det(R+2Y)\pmod{4}$ for any symmetric matrix $R\in
M_{n}(\mathbb{Z})$.

###### Proof.

For Part (1), consider the unipotent matrix $V:=V(Y)$. Then $Y\equiv
V-V^{t}\pmod{2}$. Therefore

$XY\equiv X(V-V^{t})\equiv XV-XV^{t}\pmod{2}.$

Since $X=X^{t}$ is symmetric, $XV^{t}=X^{t}V^{t}=(VX)^{t}$. Hence

$\operatorname{tr}(XY)\equiv\operatorname{tr}(XV-(VX)^{t})\equiv\operatorname{tr}(XV)-\operatorname{tr}((VX)^{t})\equiv\operatorname{tr}(XV)-\operatorname{tr}(VX)\equiv
0\pmod{2},$

where we have used $\operatorname{tr}(A^{t})=\operatorname{tr}(A)$ and the
cyclicity $\operatorname{tr}(AF)=\operatorname{tr}(FA)$ for any $A,F\in
M_{n}(\mathbb{Z})$.

For Part (2), consider the expansion of the determinant

(2.1) $\det(R+tY)=\det(R)+\operatorname{tr}(\mbox{adj}(R)Y)\cdot
t+\mathcal{O}(t^{2}),$

where $\mbox{adj}(R)$ denotes the adjugate of $R$. Since $R$ is symmetric, its
adjugate $X:=\mbox{adj}(R)$ is symmetric. By Part (1),
$\operatorname{tr}(\mbox{adj}(R)Y)$ is even. The identity above thus yields

$\det(R+2Y)=\det(R)+2\operatorname{tr}(\mbox{adj}(R)Y)+\mathcal{O}(4),$

where $2\operatorname{tr}(\mbox{adj}(R)Y)$ is divisible by $4$ and
$\mathcal{O}(4)$ indicates all other terms, also divisible by $4$. Note that
the expansion (2.1) of the determinant is valid in finite characteristic if we
use Hasse derivatives to compute the coefficients. In conclusion, reduction
modulo 4 yields the required equality

$\det(R+2Y)\equiv\det(R)\pmod{4}.$

∎

######  Remark 2.4.

I thank L. Shen, who pointed out to me that Lemma 2.3.(2) can be proven
alternatively by showing that
$\det(R)\equiv\det(R+2(\varepsilon_{ij}+\varepsilon_{ji}))\pmod{4}$ via direct
computation, where $R\in M_{n}(\mathbb{Z})$ is any symmetric matrix and
$\varepsilon_{ij}\in M_{n}(\mathbb{Z})$ is the $(i,j)$-elementary matrix, with
zero entries everywhere except for the $(i,j)$-entry, which equals 1. $\Box$

###  2.2. Proof of Lemma 1.5

We now show that the $\delta$-invariant remains unchanged under simultaneous
permutation of rows and columns. Let us denote by $\varepsilon_{ij}\in
M_{n}(\mathbb{Z})$ the elementary matrix with zero entries everywhere except
for the $(i,j)$-entry, which equals 1. Then:

######  Lemma 2.5.

Let $P\in M_{n}(\mathbb{Z})$ be the permutation matrix associated to the
simple transposition $s_{k}$, $k\in[n-1]$. Then
$P\mathfrak{S}(B)P^{t}-\mathfrak{S}(PBP^{t})=2b_{k,k+1}(\varepsilon_{k,k+1}+\varepsilon_{k+1,k})$.

###### Proof.

Since $\mathfrak{S}(B)=V(B)+V(B)^{t}$, it suffices to show the following
identity:

(*)
$PV(B)P^{t}-V(PBP^{t})=b_{k,k+1}(\varepsilon_{k,k+1}+\varepsilon_{k+1,k}).$

Given any matrix $A\in M_{n}(\mathbb{Z})$, all the rows and columns of
$PAP^{t}$ coincide with those of $A$ except for the $k$th and $(k+1)$st rows
and $k$th and $(k+1)$st columns. It thus suffices to study the difference of
$PV(B)P^{t}-V(PBP^{t})$ at those rows and columns. By construction, the
entries of these two matrices $V(PBP^{t}),PV(B)P^{t}$ coincide except at the
entries $(k+1,k)$ and $(k,k+1)$. These entries are:

$(PV(B)P^{t})_{i,j}:=\begin{cases}b_{k,k+1}&\text{ if }(i,j)=(k+1,k)\\\
0&\text{ if }(i,j)=(k,k+1)\\\
\end{cases},\quad(V(PBP^{t}))_{i,j}:=\begin{cases}0&\text{ if
}(i,j)=(k+1,k)\\\ -b_{k,k+1}&\text{ if }(i,j)=(k,k+1).\\\ \end{cases}$

This implies Identity (* ‣ 2.2) above and thus the lemma. ∎

Let us now use Lemma 2.5 to show Lemma 1.5, as follows. Since any permutation
can be written as a product of simple transpositions, it suffices to show that
$\delta(B)\equiv\delta(PBP^{t})\pmod{4}$ for $P$ the permutation matrix of a
simple transposition. For that, note that the matrix

$T:=-b_{k,k+1}(\varepsilon_{k,k+1}+\varepsilon_{k+1,k})$

has all diagonal terms equal to zero; it is also symmetric. By Lemma 2.5
above, Lemma 2.3.(2) can be applied to the symmetric matrix
$R:=P\mathfrak{S}(B)P^{t}$ and the matrix $Y:=T$. Lemma 2.3.(2) implies:

$\det(\mathfrak{S}(PBP^{t}))\stackrel{{\scriptstyle\ref{lem:perm1}}}{{\equiv}}\det(P\mathfrak{S}(B)P^{t}+2\cdot
T)\stackrel{{\scriptstyle\ref{lem:2}.(2)}}{{\equiv}}\det(P\mathfrak{S}(B)P^{t})\equiv\det(\mathfrak{S}(B))\pmod{4}.$

Thus, for any permutation $P\in M_{n}(\mathbb{Z})$, the equality
$\delta(PBP^{t})\equiv\delta(B)\pmod{4}$ is satisfied. $\Box$

###  2.3. Proof of Theorem 1.6

The goal is to show

$\det(\mathfrak{S}(\mu_{k}(B)))\equiv\det(\mathfrak{S}(B))\pmod{4}$

for any $k\in[n]$. Indeed, Lemma 1.5 has already shown that the
$\delta$-invariant remains unchanged under simultaneous permutations of rows
and columns. It therefore suffices to establish invariance under matrix
mutation.

Note that we have the identity $\mu_{k}(B)=V(\mu_{k}(B))-V(\mu_{k}(B))^{t}$
and the identity

$\mu_{k}(B)=M_{k}BM_{k}^{t}=M_{k}(V(B)-V(B)^{t})M_{k}^{t}=M_{k}V(B)M_{k}^{t}-(M_{k}V(B)M_{k}^{t})^{t}.$

By Lemma 2.1 applied to $Z:=\mu_{k}(B)$, $V:=M_{k}V(B)M_{k}^{t}$ and
$W:=V(\mu_{k}(B))$, the difference

$T:=M_{k}V(B)M_{k}^{t}-V(\mu_{k}(B))$

is a symmetric matrix $T\in M_{n}(\mathbb{Z})$. Therefore

(**)
$\begin{split}M_{k}\mathfrak{S}(B)M_{k}^{t}-\mathfrak{S}(\mu_{k}(B))&=M_{k}(V(B)+V(B)^{t})M_{k}^{t}-(V(\mu_{k}(B))+V(\mu_{k}(B))^{t})\\\
&=(M_{k}V(B)^{t}M_{k}^{t}-V(\mu_{k}(B))^{t})+(M_{k}(V(B))M_{k}^{t}-V(\mu_{k}(B)))\\\
&=2T.\end{split}$

By Lemma 2.2, the diagonal entries $t_{ii}$ of $T$ are even for all $i\in[n]$.
Therefore the reduction of $T$ modulo 2 is a symmetric matrix with zero
diagonal terms and the reduction of $2T$ modulo 4 is a symmetric matrix with
zero diagonal terms. Let $T^{\circ}\in M_{n}(\mathbb{Z})$ be the unique
integer matrix whose entries are $0$ or $1$ and $T^{\circ}\equiv T\pmod{2}$.
In particular, all diagonal terms of $T^{\circ}$ are zero. We ease notation
with $M:=M_{k}$. Let us apply Lemma 2.3.(2) to $R:=M\mathfrak{S}(B)M^{t}$ and
$Y:=T^{\circ}$. Then

$\det(M\mathfrak{S}(B)M^{t})\stackrel{{\scriptstyle\ref{lem:2}.(2)}}{{\equiv}}\det(M\mathfrak{S}(B)M^{t}+2T^{\circ})\pmod{4}.$

By construction, $2T\equiv 2T^{\circ}\pmod{4}$ and thus
$\det(M\mathfrak{S}(B)M^{t})\equiv\det(M\mathfrak{S}(B)M^{t}+2T)\pmod{4}$.
Since $M$ is unimodular, we also have
$\det(M\mathfrak{S}(B)M^{t})=\det(\mathfrak{S}(B))$. Therefore

$\det(\mathfrak{S}(\mu_{k}(B)))\stackrel{{\scriptstyle(\ref{eq:1})}}{{\equiv}}\det(M\mathfrak{S}(B)M^{t}+2T)\stackrel{{\scriptstyle\ref{lem:2}.(2)}}{{\equiv}}\det(M\mathfrak{S}(B)M^{t})\equiv\det(\mathfrak{S}(B))\pmod{4}.$

In conclusion, $\det(\mathfrak{S}(B))$ modulo 4 is a mutation invariant.
$\Box$

######  Remark 2.6.

At the core of the argument is the equality

$M\mathfrak{S}(B)M^{t}-\mathfrak{S}(\mu_{k}(B))=2T,$

where $T$ has all diagonal entries even and $M=M_{k}$ is a replicating matrix
for $B$. Let $\mathbb{S}\subset M_{n}(\mathbb{Z})$ denote the subset of
symmetric matrices. Any function $f:\mathbb{S}\longrightarrow\mathcal{C}$ to a
set $\mathcal{C}$ such that

$f(S)=f(MSM^{t}-2T),\quad\forall T\in\mathbb{S}\mbox{ such that
}T_{ii}=0\quad\forall i\in[n],$

gives a candidate mutation invariant $\delta_{f}(B):=f(\mathfrak{S}(B))$.
There are choices of $f$ that lead to trivial invariants. For instance, if
$f(A)=\operatorname{tr}(A)\pmod{2}$, then the associated invariant
$\delta_{f}(B)=\operatorname{tr}(\mathfrak{S}(B))\pmod{2}$ would be always
zero, since the diagonal terms of $\mathfrak{S}(B)$ are all even. Note that
any $f$ which is a congruence invariant and satisfies the equality in Lemma
2.3.(2) must satisfy the condition above. The binary $\delta$-invariant we
defined above corresponds to $f(A)=\det(A)\pmod{4}$. Indeed, the determinant
modulo 4 satisfies the condition above by virtue of being a congruence
invariant and Lemma 2.3.(2). Finally, we remark that the multiset of invariant
factors of the Smith normal form (even modulo 4), which is a congruence
invariant, does not satisfy the equality in Lemma 2.3.(2), even if one
restricts to symmetric matrices with $2$ in the diagonal entries. $\Box$

##  3\. Examples and comments

The following are some computations and remarks with regards to the
$\delta$-invariant. Proposition 1.7 is proven in Subsection 3.2 below.

###  3.1. Two $5\times 5$ congruent matrices with different
$\delta$-invariants

Consider the two matrices

$B=\left(\begin{array}[]{rrrrr}0&5&26&101&74\\\ -5&0&10&38&27\\\
-26&-10&0&27&34\\\ -101&-38&-27&0&83\\\
-74&-27&-34&-83&0\end{array}\right),\qquad
B^{\prime}=\left(\begin{array}[]{rrrrr}0&693&6624&4074&-8446\\\
-693&0&1136&1853&-4238\\\ -6624&-1136&0&11029&-26677\\\
-4074&-1853&-11029&0&-2349\\\ 8446&4238&26677&2349&0\end{array}\right).$

The matrices $B,B^{\prime}$ are congruent $B^{\prime}=XBX^{t}$ via the matrix

$X=\left(\begin{array}[]{rrrrr}0&2&-3&4&-13\\\ 0&1&-2&4&-11\\\
-1&4&-11&32&-85\\\ -1&-2&0&13&-31\\\ 1&2&4&-25&56\end{array}\right),$

where $\det(X)=1$. By virtue of being congruent, the Smith elementary divisors
of $B$ and $B^{\prime}$ coincide, even with multiplicity. They are 1 with
multiplicity four and 0 with multiplicity one. Similarly, the determinant of
both $B,B^{\prime}$ is 0 and their rank is 4. For both $B,B^{\prime}$, the
greatest common divisors of each of their columns all equal 1. The
$\delta$-invariants are $\delta(B)=0$ and $\delta(B^{\prime})=2$. The appendix
contains more examples of such congruent pairs $B,B^{\prime}$, generated
randomly with SageMath, and the code to generate them.

###  3.2. A simple example in all odd sizes

Let us prove Proposition 1.7. Consider the matrix $A_{n}\in M_{n}(\mathbb{Z})$
for any odd $n\in\mathbb{N}$:

$A_{n}=\sum_{i=1}^{n}\varepsilon_{i,i+1}-\sum_{i=1}^{n}\varepsilon_{i+1,i},$

where $\varepsilon_{ij}$ is the $(i,j)$-elementary matrix. It is skew-
symmetric. A direct computation shows

$\delta(A_{n})=\begin{cases}0&\text{ if }n\equiv 3\pmod{4},\\\ 2&\text{ if
}n\equiv 1\pmod{4}.\end{cases}$

Consider the unimodular matrix $X_{n}\in M_{n}(\mathbb{Z})$ defined as
$X_{n}:=\mbox{Id}_{n}+\varepsilon_{1n}$. Then, congruence by $X$ affects the
$\delta$-invariant of $A_{n}$ as follows:

$\delta(X_{n}A_{n}X_{n}^{t})=\begin{cases}2&\text{ if }n\equiv 3\pmod{4},\\\
0&\text{ if }n\equiv 1\pmod{4}.\end{cases}$

Indeed, for $n\geq 5$,
$X_{n}A_{n}X_{n}^{t}=A_{n}+(\varepsilon_{n-1,1}-\varepsilon_{1,n-1})$ and the
above values of the $\delta$-invariant follow. The case $n=3$ is also covered
by this construction. This concludes Proposition 1.7: for any odd
$n\in\mathbb{N}$, $n\geq 3$, the $\delta$-invariant is not a congruence
invariant.

###  3.3. Comparison to Markov constant in rank 3

In the rank three case $n=3$, we can write

$B:=\left(\begin{array}[]{rrr}0&p&q\\\ -p&0&r\\\ -q&-r&0\end{array}\right)$

for some integers $p,q,r\in\mathbb{Z}$. The articles [ABBS08, FT19] introduce
and study an integer quantity $C(B)$ to each skew-symmetric matrix $B$ which
is invariant under mutation. Consider the Markov constant
$C(p,q,r)=p^{2}+q^{2}+r^{2}-pqr$ associated to $p,q,r\in\mathbb{Z}$. The
mutation invariant is defined as $C(B):=C(p,q,-r)$ if the underlying quiver
$Q(B)$ is acyclic, and as $C(B):=C(p,q,r)$ if the underlying quiver $Q(B)$
contains a cycle. A direct computation shows that

$\det(\mathfrak{S}(B))=2\,pqr-2\,p^{2}-2\,q^{2}-2\,r^{2}+8.$

Therefore $\delta(B)\equiv 2\cdot C(B)\pmod{4}$.

###  3.4. Comparison to Arf invariant

The Arf invariant of a quadratic form in a $\mathbb{Z}_{2}$-vector space is a
binary invariant. It might be natural to compare the $\delta$-invariant to the
Arf invariant of a quadratic form associated to an integer skew-symmetric
matrix $B\in M_{n}(\mathbb{Z})$. Let $N\subset\mathbb{Z}_{2}^{n}$ be a free
$\mathbb{Z}_{2}$-submodule of rank $r=\mbox{rk}(B)$ such that $B|_{N}$ is a
non-degenerate skew-symmetric bilinear form. Consider the basis
$v_{1},\ldots,v_{n}$ of vectors of $\mathbb{Z}_{2}^{n}$ in which the matrix
$B$ represents a non-degenerate bilinear skew-symmetric form and assume that
$N=\langle v_{1},\ldots,v_{r}\rangle$. Consider the unique quadratic
refinement $q_{B}:N\longrightarrow\mathbb{Z}_{2}$ of $B$ such that

$q_{B}(v_{i})=1,\qquad q_{B}(v+w)=q_{B}(v)+q_{B}(w)+v^{t}Bw,\quad\forall
v,w\in N,$

where the vectors are understood as column vectors. We define the Arf
invariant $\operatorname{Arf}(B)$ of $B$ (restricted to $N$) to be the Arf
invariant $\operatorname{Arf}(q_{B})$ of this quadratic refinement. See
[Knu91, Chapter IV.4.7] for the definition of the Arf invariant of a quadratic
form in characteristic 2. Consider the following two skew-symmetric matrices
$B,B^{\prime}\in M_{n}(\mathbb{Z})$:

$B=\left(\begin{array}[]{rrrrr}0&0&1&1&0\\\ 0&0&-1&0&0\\\ -1&1&0&-1&0\\\
-1&0&1&0&1\\\ 0&0&0&-1&0\end{array}\right),\quad
B^{\prime}=\left(\begin{array}[]{rrrrr}0&1&1&1&0\\\ -1&0&-1&0&0\\\
-1&1&0&-1&0\\\ -1&0&1&0&1\\\ 0&0&0&-1&0\end{array}\right).$

Their ranks are $\mbox{rk}(B)=\mbox{rk}(B)=4$. It is verified that
$\delta(B)=2$ and $\delta(B^{\prime})=0$ by direct computation. Let us now
argue that $\operatorname{Arf}(B)=\operatorname{Arf}(B^{\prime})=1$, and
therefore the $\delta$-invariant $\delta(B)$ is different than the above
defined $\operatorname{Arf}(B)$. We compute $\operatorname{Arf}(B)$ and
$\operatorname{Arf}(B^{\prime})$ by choosing symplectic bases of $B$ and
$B^{\prime}$.

The following vectors $\\{e_{1},f_{1},e_{2},f_{2}\\}$ are a symplectic basis
for $B$:

$e_{1}=\left(0,\,0,\,1,\,0,\,0\right),\quad
e_{2}=\left(1,\,1,\,0,\,0,\,0\right),\quad
f_{1}=\left(0,\,1,\,0,\,0,\,0\right),\quad
f_{2}=\left(0,\,1,\,0,\,1,\,0\right).$

That is, they satisfy $e_{i}Be_{j}=0$, $f_{i}Bf_{j}=0$,
$e_{i}Bf_{j}=\delta_{ij}$, for all $i,j\in[2]$. In such a sympectic basis, the
Arf invariant can be computed as

$\operatorname{Arf}(q_{B})=q_{B}(e_{1})q_{B}(f_{1})+q_{B}(e_{2})q_{B}(f_{2})=(1\cdot
1)+(1+1+B_{12})\cdot(1+1+B_{24})=1$

Similarly, the following vectors
$\\{e^{\prime}_{1},f^{\prime}_{1},e^{\prime}_{2},f^{\prime}_{2}\\}$ are a
symplectic basis for $B$:

$e^{\prime}_{1}=\left(1,\,0,\,0,\,0,\,0\right),\quad
e^{\prime}_{2}=\left(0,\,-1,\,0,\,1,\,0\right),\quad
f^{\prime}_{1}=\left(0,\,1,\,0,\,0,\,0\right),\quad
f^{\prime}_{2}=\left(0,\,0,\,0,\,0,\,1\right).$

Then
$\operatorname{Arf}(q_{B^{\prime}})=q_{B^{\prime}}(e^{\prime}_{1})q_{B^{\prime}}(f^{\prime}_{1})+q_{B^{\prime}}(e^{\prime}_{2})q_{B^{\prime}}(f^{\prime}_{2})=(1\cdot
1)+(1+1+B^{\prime}_{24})\cdot 1=1$.

###  3.5. Case of quivers from plabic fences

Let $B=B_{\beta}\in M_{n}(\mathbb{Z})$ be the skew-symmetric matrix associated
to a plabic fence with positive braid word $\beta$, cf. [FPST17, Section
12].444Here $B$ is considered as a square matrix, with no frozen variables.
For simplicity, plabic fences will be considered with all vertical edges with
black on top and white on bottom. Suppose that the 0-framed closure of $\beta$
is a knot, i.e. the permutation associated to $\beta$ acts transitively on
$[n]$. Then $\delta(B)\equiv\Delta_{\beta}(-1)\pmod{4}$ where $\Delta_{\beta}$
is the Alexander polynomial of the knot $K_{\beta}$. Note that the Arf
invariant of the knot $K_{\beta}$ is $\operatorname{Arf}(K_{\beta})=0$ if
$\Delta_{\beta}(-1)\equiv\pm 1\pmod{8}$ and $\operatorname{Arf}(K_{\beta})=1$
if $\Delta_{\beta}(-1)\equiv\pm 3\pmod{8}$. In these cases, the
$\delta$-invariant does not necessarily determine the Arf invariant. To wit,
present the $(2,3)$ and the $(2,7)$-torus knots as the 0-framed closures of
the 2-stranded positive braid words $\beta_{1}=\sigma_{1}^{3}$ and
$\beta_{2}=\sigma_{1}^{7}$, respectively. These give examples of
$B,B^{\prime}$ with different Arf invariants but same $\delta$-invariant.

######  Remark 3.1.

The existence or non-existence of a reddening sequence is another binary
mutation invariant of $B$, see [Mul16, Corollary 19]. It is a non-trivial
invariant. It does not coincide with the $\delta$-invariant. To wit, the
$A_{n}$ linear quiver admits a reddening sequence for all $n\in\mathbb{N}$. As
stated in Subsection 3.2, for $n\equiv 1\pmod{4}$, its $\delta$-invariant is
$2$. For $n\equiv 3\pmod{4}$, its $\delta$-invariant is $0$. $\Box$

##  4\. Appendix

Here are two more explicit examples of pairs $(B,X)$ with $B,X\in
M_{n}(\mathbb{Z})$ such that $X$ is unimodular, $B$ is skew-symmetric and $B$
is not mutation equivalent to $XBX^{t}$, distinguished by the
$\delta$-invariant.

For $n=9$:

$B=\left(\begin{array}[]{rrrrrrrrr}0&4&13&-3&-22&35&-74&201&190\\\
-4&0&0&2&-31&-61&54&-48&32\\\ -13&0&0&-1&-1&25&-37&77&55\\\
3&-2&1&0&12&93&-123&230&124\\\ 22&31&1&-12&0&109&-129&211&71\\\
-35&61&-25&-93&-109&0&-92&118&18\\\ 74&-54&37&123&129&92&0&-514&-175\\\
-201&48&-77&-230&-211&-118&514&0&97\\\
-190&-32&-55&-124&-71&-18&175&-97&0\end{array}\right)$

$X=\left(\begin{array}[]{rrrrrrrrr}4&-14&-38&-20&73&76&204&807&2977\\\
3&-5&-22&-5&18&43&119&546&2214\\\ -5&14&49&14&-47&-102&-296&-1316&-5267\\\
5&-5&-25&-4&17&46&113&555&2307\\\ 2&-3&-16&-6&21&27&73&306&1170\\\
-2&5&17&5&-18&-33&-88&-398&-1590\\\ -1&4&10&6&-22&-20&-53&-201&-718\\\
-4&13&45&14&-50&-88&-246&-1084&-4285\\\
-3&8&28&8&-28&-54&-151&-674&-2684\end{array}\right).$

For $n=13$, we can choose the skew-symmetric matrix $B$ to be

$\left(\begin{array}[]{rrrrrrrrrrrrr}0&2&-2&11&-31&-35&128&-408&86&-316&-1288&-4120&-8869\\\
-2&0&1&-12&42&65&-255&706&17&-168&2475&11745&26626\\\
2&-1&0&10&-33&-49&190&-534&3&59&-1851&-8455&-19089\\\
-11&12&-10&0&-6&6&-45&53&121&-541&368&4295&10366\\\
31&-42&33&6&0&18&-136&157&385&-1714&1116&13387&32336\\\
35&-65&49&-6&-18&0&-32&293&-352&1512&502&-5255&-13801\\\
-128&255&-190&45&136&32&0&-327&34&-98&-1084&-4297&-9552\\\
408&-706&534&-53&-157&-293&327&0&-211&1041&-3078&-18715&-43439\\\
-86&-17&-3&-121&-385&352&-34&211&0&332&-539&-4019&-9493\\\
316&168&-59&541&1714&-1512&98&-1041&-332&0&-1229&-15981&-38721\\\
1288&-2475&1851&-368&-1116&-502&1084&3078&539&1229&0&11612&28373\\\
4120&-11745&8455&-4295&-13387&5255&4297&18715&4019&15981&-11612&0&23684\\\
8869&-26626&19089&-10366&-32336&13801&9552&43439&9493&38721&-28373&-23684&0\end{array}\right)$

and the unimodular matrix $X$ to be

$X=\left(\begin{array}[]{rrrrrrrrrrrrr}-5&9&10&-64&112&-539&1968&4901&7622&10674&28116&7513&25176\\\
2&1&13&-80&68&-436&1745&4451&7043&10350&26013&8751&31233\\\
3&-3&-2&10&-28&126&-446&-1102&-1687&-2315&-6263&-1421&-4527\\\
-3&0&-7&51&-32&237&-982&-2530&-4041&-6051&-14906&-5465&-19870\\\
2&-5&-12&73&-86&486&-1873&-4735&-7425&-10714&-27461&-8411&-29361\\\
2&-3&-2&13&-31&137&-483&-1191&-1838&-2519&-6778&-1605&-5161\\\
-1&2&11&-60&64&-380&1486&3768&5915&8584&21895&6870&24140\\\
0&2&11&-69&68&-405&1597&4057&6399&9331&23634&7676&27175\\\
-1&3&11&-66&75&-423&1629&4110&6449&9287&23828&7287&25411\\\
2&-3&-8&48&-60&332&-1275&-3225&-5053&-7284&-18687&-5691&-19838\\\
-1&-4&-19&118&-110&681&-2700&-6874&-10846&-15869&-40096&-13149&-46672\\\
0&2&13&-77&79&-469&1836&4653&7319&10629&27053&8590&30254\\\
3&-4&-5&28&-52&250&-907&-2260&-3504&-4901&-12943&-3391&-11301\end{array}\right).$

Examples for higher $n$ can be readily found, but they do not fit in this
document with the standard fontsize. The examples above hopefully illustrate
that some pairs of congruent matrices can be shown to be not mutation
equivalent with the $\delta$-invariant.

The following function “Non_MutationEquivalent_but_congruent”, written in
Python, can generate examples of such $B,X$ with SageMath 9.0:

⬇

1def triu(m):

2 t = matrix(m.base_ring(), m.nrows(), sparse=True)

3 for (i,j) in m.nonzero_positions():

4 if i < j:

5 t[i,j] = m[i,j]

6 return t+matrix.identity(m.nrows())

7

8def Non_MutationEquivalent_but_congruent(iter,size):

9 for i in range(0,iter):

10 N=random_matrix(ZZ, size, algorithm=’unimodular’, upper_bound=50000);

11 V=triu(N);

12 B=V-V.transpose();

13 C=V+V.transpose();

14 print(’The matrix B is:’);

15 show(B);

16 d=C.determinant();

17 X=random_matrix(ZZ, size, algorithm=’unimodular’, upper_bound=50000);

18 print(’The matrix X is:’);

19 show(X);

20 Bp=X*B*(X.transpose());

21 Vp=triu(Bp);

22 Cp=Vp+Vp.transpose();

23 dp=Cp.determinant();

24 print(’The mod 4 invariant of B is:’,mod(d,4));

25 print(’The mod 4 invariant of XBXt is:’,mod(dp,4));

26 if mod(dp,4)!=mod(d,4):

27 print(’The invariants are different for this congruent pair.’);

28 if mod(dp,4)==mod(d,4):

29 print(’The invariants are equal for this congruent pair.’);

30 print(’------------ End of case \------------:’, i);

## References

  * [ABBS08] Ibrahim Assem, Martin Blais, Thomas Brüstle, and Audrey Samson.  Mutation classes of skew-symmetric $3\times 3$-matrices.  Comm. Algebra, 36(4):1209–1220, 2008.
  * [BFZ05] Arkady Berenstein, Sergey Fomin, and Andrei Zelevinsky.  Cluster algebras. III. Upper bounds and double Bruhat cells.  Duke Math. J., 126(1):1–52, 2005.
  * [DWZ10] Harm Derksen, Jerzy Weyman, and Andrei Zelevinsky.  Quivers with potentials and their representations II: applications to cluster algebras.  J. Amer. Math. Soc., 23(3):749–790, 2010.
  * [FN23] Sergey Fomin and Scott Neville.  Long mutation cycles.  arXiv:2304.11505, 2023.
  * [Fom] Sergey Fomin.  Quiver mutations.  Open Problems in Algebraic Combinatorics, slides at OPAC 2022 website.
  * [FPST17] Sergey Fomin, Pavlo Pylyavskyy, Eugenii Shustin, and Dylan Thurston.  Morsifications and mutations.  preprint, 2017.
  * [FT19] Anna Felikson and Pavel Tumarkin.  Geometry of mutation classes of rank 3 quivers.  Arnold Math. J., 5(1):37–55, 2019.
  * [FWZ] Sergey Fomin, Lauren Williams, and Andrei Zelevinsky.  Introduction to Cluster Algebras.  arXiv:2008.09189.
  * [FZ02] Sergey Fomin and Andrei Zelevinsky.  Cluster algebras I.  J. Amer. Math. Soc., 15(2):497–529, 2002.
  * [Knu91] Max-Albert Knus.  Quadratic and Hermitian forms over rings, volume 294 of Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].  Springer-Verlag, Berlin, 1991.  With a foreword by I. Bertuccioni.
  * [Mul16] Greg Muller.  The existence of a maximal green sequence is not invariant under quiver mutation.  Electron. J. Combin., 23(2):Paper 2.47, 23, 2016.
  * [New97] Morris Newman.  The Smith normal form.  In Proceedings of the Fifth Conference of the International Linear Algebra Society (Atlanta, GA, 1995), volume 254, pages 367–381, 1997.


* [61] B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šrndić, P. Laskov, G. Giacinto, and F. Roli, “Evasion attacks against machine learning at test time,” in Joint European conference on machine learning and knowledge discovery in databases, pp. 387–402, Springer, 2013.
  * [62] J. Jo and Y. Bengio, “Measuring the tendency of cnns to learn surface statistical regularities,” arXiv preprint arXiv:1711.11561, 2017.
  * [63] D. Hendrycks and T. Dietterich, “Benchmarking neural network robustness to common corruptions and perturbations,” in International Conference on Learning Representations, 2018.
  * [64] L. Huang, A. D. Joseph, B. Nelson, B. I. Rubinstein, and J. Tygar, “Adversarial machine learning,” in Proceedings of the 4th ACM workshop on Security and artificial intelligence, pp. 43–58, ACM, 2011.
  * [65] N. Carlini, A. Athalye, N. Papernot, W. Brendel, J. Rauber, D. Tsipras, I. Goodfellow, A. Madry, and A. Kurakin, “On evaluating adversarial robustness,” arXiv preprint arXiv:1902.06705, 2019.
  * [66] A. Ilyas, L. Engstrom, A. Athalye, and J. Lin, “Black-box adversarial attacks with limited queries and information,” arXiv preprint arXiv:1804.08598, 2018.
  * [67] F. Pierazzi, F. Pendlebury, J. Cortellazzi, and L. Cavallaro, “Intriguing properties of adversarial ml attacks in the problem space,” in 2020 IEEE Symposium on Security and Privacy (SP), pp. 1332–1349, IEEE, 2020.
  * [68] E. Tabassi, K. J. Burns, M. Hadjimichael, A. D. Molina-Markham, and J. T. Sexton, “A taxonomy and terminology of adversarial machine learning,” 2019.
  * [69] A. Pattanaik, Z. Tang, S. Liu, G. Bommannan, and G. Chowdhary, “Robust deep reinforcement learning with adversarial attacks,” in Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 2040–2042, International Foundation for Autonomous Agents and Multiagent Systems, 2018.
  * [70] F. Tramèr, F. Zhang, A. Juels, M. K. Reiter, and T. Ristenpart, “Stealing machine learning models via prediction apis,” in 25th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 16), pp. 601–618, 2016.
  * [71] M. Jagielski, N. Carlini, D. Berthelot, A. Kurakin, and N. Papernot, “High accuracy and high fidelity extraction of neural networks,” in 29th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 20), 2020.
  * [72] M. Fredrikson, S. Jha, and T. Ristenpart, “Model inversion attacks that exploit confidence information and basic countermeasures,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 1322–1333, 2015.
  * [73] N. Papernot, P. McDaniel, and I. Goodfellow, “Transferability in machine learning: from phenomena to black-box attacks using adversarial samples,” arXiv preprint arXiv:1605.07277, 2016.
  * [74] Y. Liu, X. Chen, C. Liu, and D. Song, “Delving into transferable adversarial examples and black-box attacks,” arXiv preprint arXiv:1611.02770, 2016\.
  * [75] X. Yuan, P. He, Q. Zhu, R. R. Bhat, and X. Li, “Adversarial examples: Attacks and defenses for deep learning,” arXiv preprint arXiv:1712.07107, 2017\.
  * [76] A. Kurakin, I. Goodfellow, and S. Bengio, “Adversarial examples in the physical world,” arXiv preprint arXiv:1607.02533, 2016.
  * [77] U. Jang, X. Wu, and S. Jha, “Objective metrics and gradient descent algorithms for adversarial examples in machine learning,” in Proceedings of the 33rd Annual Computer Security Applications Conference, pp. 262–277, 2017.
  * [78] N. Carlini and D. Wagner, “Towards evaluating the robustness of neural networks,” in 2017 IEEE Symposium on Security and Privacy (SP), pp. 39–57, IEEE, 2017.
  * [79] N. Papernot, P. McDaniel, X. Wu, S. Jha, and A. Swami, “Distillation as a defense to adversarial perturbations against deep neural networks,” in 2016 IEEE Symposium on Security and Privacy (SP), pp. 582–597, IEEE, 2016.
  * [80] F. Croce and M. Hein, “Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks,” arXiv preprint arXiv:2003.01690, 2020.
  * [81] M. Mosbach, M. Andriushchenko, T. Trost, M. Hein, and D. Klakow, “Logit pairing methods can fool gradient-based attacks,” arXiv preprint arXiv:1810.12042, 2018.
  * [82] F. Croce and M. Hein, “Minimally distorted adversarial examples with a fast adaptive boundary attack,” arXiv preprint arXiv:1907.02044, 2019.
  * [83] F. Croce, M. Andriushchenko, and M. Hein, “Provable robustness of relu networks via maximization of linear regions,” in the 22nd International Conference on Artificial Intelligence and Statistics, pp. 2057–2066, 2019.
  * [84] S. Sabour, Y. Cao, F. Faghri, and D. J. Fleet, “Adversarial manipulation of deep representations,” arXiv preprint arXiv:1511.05122, 2015.
  * [85] S.-M. Moosavi-Dezfooli, A. Fawzi, O. Fawzi, and P. Frossard, “Universal adversarial perturbations,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1765–1773, 2017.
  * [86] P.-Y. Chen, Y. Sharma, H. Zhang, J. Yi, and C.-J. Hsieh, “Ead: elastic-net attacks to deep neural networks via adversarial examples,” in Thirty-second AAAI conference on artificial intelligence, 2018.
  * [87] A. Ghiasi, A. Shafahi, and T. Goldstein, “Breaking certified defenses: Semantic adversarial examples with spoofed robustness certificates,” arXiv preprint arXiv:2003.08937, 2020.
  * [88] T. B. Brown, D. Mané, A. Roy, M. Abadi, and J. Gilmer, “Adversarial patch,” arXiv preprint arXiv:1712.09665, 2017.
  * [89] J. Chen, M. I. Jordan, and M. J. Wainwright, “Hopskipjumpattack: A query-efficient decision-based attack,” arXiv preprint arXiv:1904.02144, 2019.
  * [90] B. Biggio, B. Nelson, and P. Laskov, “Poisoning attacks against support vector machines,” arXiv preprint arXiv:1206.6389, 2012.
  * [91] T. Gu, B. Dolan-Gavitt, and S. Garg, “Badnets: Identifying vulnerabilities in the machine learning model supply chain,” arXiv preprint arXiv:1708.06733, 2017.
  * [92] A. Shafahi, W. R. Huang, M. Najibi, O. Suciu, C. Studer, T. Dumitras, and T. Goldstein, “Poison frogs! targeted clean-label poisoning attacks on neural networks,” in Advances in Neural Information Processing Systems, pp. 6103–6113, 2018.
  * [93] J. R. Correia-Silva, R. F. Berriel, C. Badue, A. F. de Souza, and T. Oliveira-Santos, “Copycat cnn: Stealing knowledge by persuading confession with random non-labeled data,” in 2018 International Joint Conference on Neural Networks (IJCNN), pp. 1–8, IEEE, 2018.
  * [94] T. Orekondy, B. Schiele, and M. Fritz, “Knockoff nets: Stealing functionality of black-box models,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4954–4963, 2019.
  * [95] A. K. Das, S. Zeadally, and D. He, “Taxonomy and analysis of security protocols for internet of things,” Future Generation Computer Systems, vol. 89, pp. 110–125, 2018.
  * [96] S. Hansman and R. Hunt, “A taxonomy of network and computer attacks,” Computers & Security, vol. 24, no. 1, pp. 31–43, 2005.
  * [97] I. Rosenberg, A. Shabtai, Y. Elovici, and L. Rokach, “Adversarial learning in the cyber security domain,” arXiv preprint arXiv:2007.02407, 2020.
  * [98] “Total malware.”
  * [99] A. Calleja, A. Martín, H. D. Menéndez, J. Tapiador, and D. Clark, “Picking on the family: Disrupting android malware triage by forcing misclassification,” Expert Systems with Applications, vol. 95, pp. 113–126, 2018.
  * [100] O. Suciu, R. Marginean, Y. Kaya, H. Daume III, and T. Dumitras, “When does machine learning $\\{$FAIL$\\}$? generalized transferability for evasion and poisoning attacks,” in 27th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 18), pp. 1299–1316, 2018.
  * [101] K. S. Han, J. H. Lim, B. Kang, and E. G. Im, “Malware analysis using visualized images and entropy graphs,” International Journal of Information Security, vol. 14, no. 1, pp. 1–14, 2015.
  * [102] W. Hu and Y. Tan, “Generating adversarial malware examples for black-box attacks based on gan,” arXiv preprint arXiv:1702.05983, 2017.
  * [103] W. Hu and Y. Tan, “Black-box attacks against rnn based malware detection algorithms,” in Workshops at the Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
  * [104] A. Al-Dujaili et al., “Adversarial deep learning for robust detection of binary encoded malware,” in 2018 IEEE Security and Privacy Workshops (SPW), pp. 76–82, IEEE, 2018.
  * [105] F. Kreuk, A. Barak, S. Aviv-Reuven, M. Baruch, B. Pinkas, and J. Keshet, “Deceiving end-to-end deep learning malware detectors using adversarial examples,” arXiv preprint arXiv:1802.04528, 2018.
  * [106] F. Kreuk, A. Barak, S. Aviv-Reuven, M. Baruch, B. Pinkas, and J. Keshet, “Adversarial examples on discrete sequences for beating whole-binary malware detection,” arXiv preprint arXiv:1802.04528, pp. 490–510, 2018.
  * [107] E. Raff, J. Barker, J. Sylvester, R. Brandon, B. Catanzaro, and C. K. Nicholas, “Malware detection by eating a whole exe,” in Workshops at the Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
  * [108] M. Sahami, S. Dumais, D. Heckerman, and E. Horvitz, “A bayesian approach to filtering junk e-mail,” in Learning for Text Categorization: Papers from the 1998 workshop, vol. 62, pp. 98–105, Madison, Wisconsin, 1998.
  * [109] D. Lowd and C. Meek, “Good word attacks on statistical spam filters.,” in CEAS, vol. 2005, 2005.
  * [110] G. Wang, T. Wang, H. Zheng, and B. Y. Zhao, “Man vs. machine: Practical adversarial detection of malicious crowdsourcing workers,” in 23rd $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 14), pp. 239–254, 2014.
  * [111] P. Negi, A. Sharma, and C. Robustness, “Adversarial machine learning against keystroke dynamics,” 2017.
  * [112] M. F. Zeager, A. Sridhar, N. Fogal, S. Adams, D. E. Brown, and P. A. Beling, “Adversarial learning in credit card fraud detection,” in 2017 Systems and Information Engineering Design Symposium (SIEDS), pp. 112–116, IEEE, 2017\.
  * [113] G. Apruzzese, M. Colajanni, L. Ferretti, and M. Marchetti, “Addressing adversarial attacks against security systems based on machine learning,” in 2019 11th International Conference on Cyber Conflict (CyCon), vol. 900, pp. 1–18, IEEE, 2019.
  * [114] Z. Lin, Y. Shi, and Z. Xue, “Idsgan: Generative adversarial networks for attack generation against intrusion detection,” arXiv preprint arXiv:1809.02077, 2018.
  * [115] M. Arjovsky, S. Chintala, and L. Bottou, “Wasserstein gan,” arXiv preprint arXiv:1701.07875, 2017.
  * [116] I. Homoliak, M. Teknos, M. Ochoa, D. Breitenbacher, S. Hosseini, and P. Hanacek, “Improving network intrusion detection classifiers by non-payload-based exploit-independent obfuscations: An adversarial approach,” arXiv preprint arXiv:1805.02684, 2018.
  * [117] H. Zhang, X. Yu, P. Ren, C. Luo, and G. Min, “Deep adversarial learning in intrusion detection: A data augmentation enhanced framework,” arXiv preprint arXiv:1901.07949, 2019.
  * [118] M. Usama, M. Asim, S. Latif, J. Qadir, et al., “Generative adversarial networks for launching and thwarting adversarial attacks on network intrusion detection systems,” in 2019 15th International Wireless Communications & Mobile Computing Conference (IWCMC), pp. 78–83, IEEE, 2019.
  * [119] J. Aiken and S. Scott-Hayward, “Investigating adversarial attacks against network intrusion detection systems in sdns,” in 2019 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN), pp. 1–7, IEEE, 2019.
  * [120] Y. E. Sagduyu, Y. Shi, and T. Erpek, “Iot network security from the perspective of adversarial deep learning,” in 2019 16th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON), pp. 1–9, IEEE, 2019.
  * [121] F. Liang, C. Shen, and F. Wu, “An iterative bp-cnn architecture for channel decoding,” IEEE Journal of Selected Topics in Signal Processing, vol. 12, no. 1, pp. 144–159, 2018.
  * [122] H. Sun, X. Chen, Q. Shi, M. Hong, X. Fu, and N. D. Sidiropoulos, “Learning to optimize: Training deep neural networks for wireless resource management,” in 2017 IEEE 18th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pp. 1–6, IEEE, 2017.
  * [123] T. J. O’Shea, J. Corgan, and T. C. Clancy, “Convolutional radio modulation recognition networks,” in International conference on engineering applications of neural networks, pp. 213–226, Springer, 2016.
  * [124] T. J. O’Shea, T. Roy, and T. C. Clancy, “Over-the-air deep learning based radio signal classification,” IEEE Journal of Selected Topics in Signal Processing, vol. 12, no. 1, pp. 168–179, 2018.
  * [125] J. Canedo and A. Skjellum, “Using machine learning to secure iot systems,” in 2016 14th annual conference on privacy, security and trust (PST), pp. 219–222, IEEE, 2016.
  * [126] Y. Meidan, M. Bohadana, A. Shabtai, J. D. Guarnizo, M. Ochoa, N. O. Tippenhauer, and Y. Elovici, “Profiliot: a machine learning approach for iot device identification based on network traffic analysis,” in Proceedings of the symposium on applied computing, pp. 506–509, 2017.
  * [127] M. Miettinen, S. Marchal, I. Hafeez, N. Asokan, A.-R. Sadeghi, and S. Tarkoma, “Iot sentinel: Automated device-type identification for security enforcement in iot,” in 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS), pp. 2177–2184, IEEE, 2017.
  * [128] R. Feinman, R. R. Curtin, S. Shintre, and A. B. Gardner, “Detecting adversarial samples from artifacts,” arXiv preprint arXiv:1703.00410, 2017\.
  * [129] M. Sadeghi and E. G. Larsson, “Adversarial attacks on deep-learning based radio signal classification,” IEEE Wireless Communications Letters, vol. 8, no. 1, pp. 213–216, 2018.
  * [130] Y. Shi, Y. E. Sagduyu, T. Erpek, K. Davaslioglu, Z. Lu, and J. H. Li, “Adversarial deep learning for cognitive radio security: Jamming attack and defense strategies,” in 2018 IEEE International Conference on Communications Workshops (ICC Workshops), pp. 1–6, IEEE, 2018.
  * [131] A. Albaseer, B. S. Ciftler, and M. M. Abdallah, “Performance evaluation of physical attacks against e2e autoencoder over rayleigh fading channel,” in 2020 IEEE International Conference on Informatics, IoT, and Enabling Technologies (ICIoT), pp. 177–182, IEEE, 2020.
  * [132] M. Sadeghi and E. G. Larsson, “Physical adversarial attacks against end-to-end autoencoder communication systems,” IEEE Communications Letters, vol. 23, no. 5, pp. 847–850, 2019.
  * [133] J. W. Stokes, D. Wang, M. Marinescu, M. Marino, and B. Bussone, “Attack and defense of dynamic analysis-based, adversarial neural malware detection models,” in MILCOM 2018-2018 IEEE Military Communications Conference (MILCOM), pp. 1–8, IEEE, 2018.
  * [134] S. Kokalj-Filipovic, R. Miller, and J. Morman, “Targeted adversarial examples against rf deep classifiers,” in Proceedings of the ACM Workshop on Wireless Security and Machine Learning, pp. 6–11, 2019.
  * [135] N. Dalvi, P. Domingos, S. Sanghai, and D. Verma, “Adversarial classification,” in Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 99–108, 2004.
  * [136] E. Raff, J. Barker, J. Sylvester, R. Brandon, B. Catanzaro, and C. Nicholas, “Malware detection by eating a whole exe,” arXiv preprint arXiv:1710.09435, 2017.
  * [137] O. Suciu, S. E. Coull, and J. Johns, “Exploring adversarial examples in malware detection,” arXiv preprint arXiv:1810.08280, 2018.
  * [138] Y. Peng, J. Su, X. Shi, and B. Zhao, “Evaluating deep learning based network intrusion detection system in adversarial environment,” in 2019 IEEE 9th International Conference on Electronics Information and Emergency Communication (ICEIEC), pp. 61–66, IEEE, 2019.
  * [139] O. Ibitoye, O. Shafiq, and A. Matrawy, “Analyzing adversarial attacks against deep learning for intrusion detection in iot networks,” in 2019 IEEE Global Communications Conference (GLOBECOM), pp. 1–6, IEEE, 2019.
  * [140] M. Kloft and P. Laskov, “Online anomaly detection under adversarial impact,” in Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 405–412, 2010.
  * [141] B. Biggio, G. Fumera, and F. Roli, “Security evaluation of pattern classifiers under attack,” IEEE transactions on knowledge and data engineering, vol. 26, no. 4, pp. 984–996, 2013.
  * [142] J. Uesato, B. O’Donoghue, A. v. d. Oord, and P. Kohli, “Adversarial risk and the dangers of evaluating against weak attacks,” arXiv preprint arXiv:1802.05666, 2018.
  * [143] F. Liao, M. Liang, Y. Dong, T. Pang, X. Hu, and J. Zhu, “Defense against adversarial attacks using high-level representation guided denoiser,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1778–1787, 2018.
  * [144] A. S. Suggala, A. Prasad, V. Nagarajan, and P. Ravikumar, “Revisiting adversarial risk,” in The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2331–2339, 2019.
  * [145] A. Fawzi, H. Fawzi, and O. Fawzi, “Adversarial vulnerability for any classifier,” in Advances in Neural Information Processing Systems, pp. 1178–1187, 2018.
  * [146] D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry, “There is no free lunch in adversarial robustness (but there are unexpected benefits),” arXiv preprint arXiv:1805.12152, vol. 2, no. 3, 2018.
  * [147] W. Brendel, J. Rauber, and M. Bethge, “Decision-based adversarial attacks: Reliable attacks against black-box machine learning models,” arXiv preprint arXiv:1712.04248, 2017.
  * [148] C. Guo, J. S. Frank, and K. Q. Weinberger, “Low frequency adversarial perturbation,” arXiv preprint arXiv:1809.08758, 2018.
  * [149] A. Nayebi and S. Ganguli, “Biologically inspired protection of deep networks from adversarial attacks,” arXiv preprint arXiv:1703.09202, 2017.
  * [150] Y. Yanagita and M. Yamamura, “Gradient masking is a type of overfitting,” International Journal of Machine Learning and Computing, vol. 8, no. 3, 2018\.
  * [151] G. Hinton, O. Vinyals, and J. Dean, “Distilling the knowledge in a neural network,” arXiv preprint arXiv:1503.02531, 2015.
  * [152] D. Meng and H. Chen, “Magnet: a two-pronged defense against adversarial examples,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 135–147, ACM, 2017.
  * [153] J. H. Metzen, T. Genewein, V. Fischer, and B. Bischoff, “On detecting adversarial perturbations,” arXiv preprint arXiv:1702.04267, 2017.
  * [154] K. Grosse, N. Papernot, P. Manoharan, M. Backes, and P. McDaniel, “Adversarial perturbations against deep neural networks for malware classification,” arXiv preprint arXiv:1606.04435, 2016.
  * [155] Y. Song, T. Kim, S. Nowozin, S. Ermon, and N. Kushman, “Pixeldefend: Leveraging generative models to understand and defend against adversarial examples,” arXiv preprint arXiv:1710.10766, 2017.
  * [156] F. Tramèr, N. Papernot, I. Goodfellow, D. Boneh, and P. McDaniel, “The space of transferable adversarial examples,” arXiv preprint arXiv:1704.03453, 2017.
  * [157] L. Schmidt, S. Santurkar, D. Tsipras, K. Talwar, and A. Madry, “Adversarially robust generalization requires more data,” in Advances in Neural Information Processing Systems, pp. 5014–5026, 2018.
  * [158] H. Li, S. Zhou, W. Yuan, J. Li, and H. Leung, “Adversarial-example attacks toward android malware detection system,” IEEE Systems Journal, vol. 14, no. 1, pp. 653–656, 2019.
  * [159] Y. Xie, C. Shi, Z. Li, J. Liu, Y. Chen, and B. Yuan, “Real-time, universal, and robust adversarial attacks against speaker recognition systems,” in ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1738–1742, IEEE, 2020.
  * [160] Y. Gong, B. Li, C. Poellabauer, and Y. Shi, “Real-time adversarial attacks,” arXiv preprint arXiv:1905.13399, 2019.
  * [161] E. Bagdasaryan, A. Veit, Y. Hua, D. Estrin, and V. Shmatikov, “How to backdoor federated learning,” in International Conference on Artificial Intelligence and Statistics, pp. 2938–2948, 2020.
  * [162] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” ACM Transactions on Intelligent Systems and Technology (TIST), vol. 10, no. 2, pp. 1–19, 2019.
  * [163] G. Aceto, D. Ciuonzo, A. Montieri, and A. Pescapé, “Mobile encrypted traffic classification using deep learning,” in 2018 Network Traffic Measurement and Analysis Conference (TMA), pp. 1–8, IEEE, 2018.
  * [164] E. Hesamifard, H. Takabi, and M. Ghasemi, “Cryptodl: Deep neural networks over encrypted data,” arXiv preprint arXiv:1711.05189, 2017.
  * [165] M. Lotfollahi, M. J. Siavoshani, R. S. H. Zade, and M. Saberian, “Deep packet: A novel approach for encrypted traffic classification using deep learning,” Soft Computing, vol. 24, no. 3, pp. 1999–2012, 2020.
  * [166] E. Klein, R. Mislovaty, I. Kanter, A. Ruttor, and W. Kinzel, “Synchronization of neural networks by mutual learning and its application to cryptography,” in Advances in Neural Information Processing Systems, pp. 689–696, 2005\.


# Using Recurrent Neural Networks to Predict Aspects of 3-D Structure of
Folded Copolymer Sequences

Ronan G. Reilly1, M-Tahar Kechadi1,
Yuri A. Kuznetosov2, Edward G. Timoshenko2,
and Kenneth A. Dawson2 E-mail<EMAIL_ADDRESS>
(Department of Computer Science1
and Department of Chemistry2,
University College Dublin, Ireland )

###### Abstract

The neural network techniques are developed for artificial sequences based on
approximate models of proteins. We only encode the hydrophobicity of the amino
acid side chains without attempting to model the secondary structure. We use
our approach to obtain a large set of sequences with known 3-D structures for
training the neural network. By employing recurrent neural networks we
describe a way to augment a neural network to deal with sequences of realistic
length and long-distant interactions between the sequence regions.

## Introduction

Neural networks have been applied with some limited success to the problem of
predicting the secondary [1,2] and tertiary [3,4] structure of proteins based
on their amino acid residue sequence. The number of sequences for which there
is a known 3-D structure is relatively limited. The rate at which 3-D
structures are being solved is at least one order of magnitude lower than the
rate at which new protein sequences are being determined [3]. In addition, a
limitation in the neural network approaches taken to date is their inability
to deal with very long sequences, and with the possibility of dependencies
between different regions of a sequence [8]. The work described here is an
attempt to address these limitations. In order to obtain a large set of
sequences with known 3-D structures for training the neural network, we use
the approach described in [5] to generate a set of artificial copolymers
consisting of hydrophobic and hydrophilic units with a known 3-D structure
when folded. By employing recurrent neural networks and building on the
approach described in [3, 4], we describe a way to augment a neural network
with both with a facility to deal with sequences of realistic length, and with
a mechanism for handling possible long-distant interactions between regions of
the sequence. These sequences are very approximate models of real proteins,
given that we only encode the hydrophobicity of the amino acid side chains,
and there is no attempt to model their secondary or super-secondary structure.
Nonetheless, the neural network techniques developed using artificial
sequences are readily applicable to real proteins.

## Sequence generation

In order to study the structure of copolymer folding we use the painting
method described in [5]. The general approach is as follows:

>
> 1\. An open homopolymer sequence of a fixed size is chosen;
> 2\. This homopolymer sequence is allowed to fold into a globule using a
> Monte Carlo simulation method [8]; SRNs and Protein Folding
> 3\. The globule shape depends on the position of each monomer in the
> sequence and the interactions between them. Since this globule is not always
> compact, only spherical globules are considered for the next stage;
> 4\. The core of the globule is painted. The volume of the coloured core is
> determined by the desired hydrphobicity ratio along the chain. A typical
> ration is 50:50. The technique used to do the painting is called the regular
> hull painting algorithm;
> 5\. The coloured sequences obtained are considered as copolymer sequences.
> The Monte Carlo simulation method is then used to refold the copolymer
> sequences to determine how compactly they collapse.

In the case of this experiment, a subset of 500 of the sequences generated by
this painting technique were coded as hydrophobicity and repeatedly refolded
using the Monte Carlo simulation technique. The quality of the refolded
sequence was measured by the disorder parameter $\Psi$:

$\Psi=\frac{1}{2N^{2}}\sum_{ij}(\lambda_{i}+\lambda_{j})D_{ij}$ $\mbox{where
}D_{ij}=\frac{1}{3}\left((x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}+(z_{i}-z_{j})^{2}\right),$
$\mbox{and }\lambda=\biggl{\\{}\begin{array}[]{ll}-1\mbox{\ for
hydrophobic}\\\ +1\mbox{\ for hydrophillic}\end{array}\biggr{.}$

For an ideally folded sequence with hydrophobic units on the inside of the
globule and hydrophilic on the outside, the value for $\Psi$ tends to zero.
Any deviation from this ideal gives larger positive or negative values. As a
result of the refolding experiments it was possible to assign a given sequence
to one of three categories: sequences that folded well (60%), sequences that
folded poorly (37%), and sequences that folded very poorly (3%). In the case
of the poor folders, these often comprised a globule with a trailing strand,
or in some cases two small globules. Thus, they appeared to be moving in the
right direction, and given more iterations in the Monte Carlo simulation would
eventually produce a compactly folded globule.

## SRN architecture

A simple recurrent network (SRN) is an extension to the standard feedforward
neural network and was first proposed by Elman [6] (cf. Figure 1). Its main
use to date has been in the area of modelling time series data and the
acquisition of grammar. A common feature of both sentence structures and
protein structures is the inherent sequential nature of the “input”, and the
sometimes non-sequential nature of the inter-relationships between different
regions of the sequence. So, for example, in a sentence “The cat who chased
the dog bites the mouse” there is agreement in number between the first noun
“cat” and the verb “bite”. This is referred to as a long-distance dependency.
Similar long-distance interactions are also possible between the sub-
structures of a folded protein [8]. Furthermore, a significant strength of
SRNs is their ability to deal with sequences of varying and potentially
unlimited length.

The main difference between the SRN architecture and a regular feed-forward
neural network is that it permits the state of the hidden units at the
previous time step to be part of the input at the next time step. This
provides the network with an attenuated memory of its inputs at preceding time
steps (and not just the most recent one), and permits it to use information
from earlier inputs in the processing of current ones.

## A General Input Representation

As well as choosing the correct architecture for carrying out protein
structure prediction, a key factor in the success or otherwise of any
artificial neural network approach to this challenge is the way in which the
problem is presented to the network, particularly the choice of input
representation. In addition to exploring the use of SRNs, another goal of this
project is to try to develop an input representation that provides as much
information as possible within the constraints of the number of input units
available.

In both of the application to be discussed below, the input to the network is
in the form of a moving window through which a given subset of the copolymer
sequence is input. Such an input technique is similar to that employed by [1]
and [3]. However, given that we will be restricting ourselves to binary
representations of polymer sequences where a hydrophilic unit is coded as “1”
and a hydrophobic unit is coded as a “0”, there is the possibility of using a
moving window with a number of different resolutions (cf. Figure 2). The
number of input units used in the two applications described here is 50 for
the elements of the sequence, plus one used to indicate when the entire
sequence has been input to the network. This latter unit is referred to as the
reset unit, because when it is switched on, the feedback from the hidden units
is reset to a vector of zeros. For the central 10 units of the input , there
is a one-to-one mapping between sequence elements and the input units of the
network. However, as one moves away from the centre, to the right and left,
the resolution of the input units is reduced. Thus in the adjacent blocks of
the 10 units, each input unit codes the average of four binary units. In the
next pair of blocks, the units code for the average of 10 units. This gives a
form of “fisheye” lens effect which permits an effective window size of 280,
albeit with diminishing resolution as one moves away from its centre.

## The Experiments

The purpose of the following two experiments was to test the feasibility of
using an SRN to predict various aspects of the structure of a folded
copolymer. The first experiment was designed to predict the propensity of the
sequence to refold successfully, that is to which of the two refolding classes
the sequence belonged. The second experiment attempted the more ambitious goal
of predicting the 3-D structure of those sequences that refolded the best
(i.e., with a value for $\Psi$ of near zero). The structure of the folded
sequence was represented to the network in the form of a binary distance
inequality matrix (DIM). Both experiments can be considered as preliminary
steps towards developing a system to predict the 3-D structure of real
proteins.

### Materials

The initial set of materials used in both experiments comprised 500 painted
and refolded copolymers of length 120, produced using the painting technique
described earlier. All sequences consisted of a series of 1s and 0s, with “1”
representing a hydrophilic element and “0”, a hydrophobic one.

### Refolding ability

In the first set of experiments, a simple recurrent network was used to
predict the refolding class of the open co-polymer. Only two classes were
used: good and poor. Because of the low percentage of very poor folding
sequences, it was not feasible to train the network on this class of data. The
input sequence was pre- processed through a multi-resolution window as
described in the previous section. The task of the SRN was to switch on one of
two output units indicating to which folding class the sequence belonged.

The prediction network consisted of 51 input units, 10 hidden units111A number
of hidden unit values were tested (80, 40, 20), and 10 proved to be optimal.,
10 feedback units, and 2 output units. This network was trained on 100 folded
and painted sequences using the backpropagation learning algorithm [7], with
the learning rate parameter set to 0.01, and the momentum parameter to 0.5.
The training patterns for the SRN consisted of a series of vectors generated
from the multi-resolution window as it was shifted across the open sequence,
10 units at a time. This meant that a sequence of 120 would take 12 input
presentations to be completely presented to the network. The activation values
from the network’s hidden units at the previous time step was provided as
input, in addition to each window vector. When the window came to the end of a
sequence, the hidden unit feedback was set to a vector of zeros. For each of
the 12 window presentations, the target for the two output units was the same:
the refolding class of the input sequence. The network was trained for 300
complete passes (epochs) through the training set.

| Refolding class
---|---
Network prediction | Good | Bad
good | p(g$|$G) = 0.73 | p(g$|$B) = 0.27
bad | p(b$|$G) = 0.59 | p(b$|$B) = 0.41
Table 1: Performance of the SRN in predicting the quality of refolded
sequences it has not been trained on. The values in cells represent
conditional probabilities, where “g” is the network prediction and “G” is the
actual classification of the sequence. The network was trained on 100
sequences, and then tested with an additional 100.

### Refolding prediction results

The real valued output of this network was converted to a single binary
decision value by assuming the largest of the two outputs from the network to
indicate a classification decision (i.e., good or bad refolder). This was then
compared to the actual classification of the sequence. The results in Table 1
are representative of the results of a number of training replications and are
given in the form of conditional probabilities. Typically, after 300 or so
passes through the training set, the network learned to perform the
classification task with 100% accuracy. It was then tested on an additional
100 sequences not seen during training. As can be seen, while the network is
good at predicting good folding sequences, it tends to misclassify badly
folding sequences as good ones.

### Distance inequality matrix prediction

A distance inequality matrix (DIM) is a binary version of the 2-D matrix of
Euclidean distances between each element and every other in the sequence. In
this study, distances greater than 3 monomers were coded as 0.5, less than 3
as -0.5. The task of the network was to output a series of 10x20 sub-matrices
of the overall distance matrix for a given input sequence in row major order.
The overall architecture of the SRN is given in Figure 3.

As with the earlier refolding prediction experiment, the SRN was trained by
inputting a binary coded protein using a moving window across the entire
sequence. The structure of the input window has already been described (see
Figure 2). At its centre is a 10 unit one-to-one representation of the
sequence fragment, while the elements either side of the window are
represented with diminishing resolution. However, in the case of the DIM
prediction task, each window was used to generate a sequence of 10x20 sub-
matrices of the overall DIM (see Figure 4). These sub-matrices corresponded to
the rows of the DIM associated with the 10 elements of the sequence at the
centre of the window. Rather than getting the network to output an entire row,
it was generated in a series of steps. The 10x20 sub-matrices partially
overlap (by 50%), thus providing some element of redundancy in the
construction of the overall matrix. The matrix is also symmetric about the
diagonal, and this was also exploited in constructing a full DIM for a given
sequence. From a set of 200 refolded sequences a subset of the best refolders
was selected. These were then divided into a training set and a test set of
(70 and 69 respectively). An SRN comprising 51 input units, 80 hidden units,
and 200 output units was trained for 500 epochs to predict the DIM for the 100
sequences in the training set. A learning rate of 0.01 and a momentum of 0.5
was used. The network was then tested on its ability to predict accurately the
DIM for the set of 100 sequences that it had not been trained on.

### Distance matrix results

Testing the DIM prediction network involved reconstructing a matrix from the
real-valued network output, converting it to binary form and then comparing it
to the actual DIM for that sequence. As has already been mentioned, both the
diagonality of the matrix and the 50% overlap between the adjacent 10x20
output sub-matrices was exploited in this reconstruction. In both the diagonal
and overlap cases, where there were multiple estimates for a given cell of the
DIM, an average of these values was used. The averaging of the overlap was
done prior to averaging across the diagonal. After averaging, the
reconstructed matrix was converted to a DIM by thresholding the values at 0.5.
The percentage of elements of the target and output DIMs that are in the same
state (i.e., on or off) is then calculated and used to measure prediction
accuracy.

Accuracy of prediction
---
training set (n=70) | test set (n=69)
80% | 77%
Table 2: Performance of SRN in predicting the distance inequality matrix of
refolded copolymer sequences of length 120. The figures represent the average
prediction performance over the n sequences comprising each set.

As can be seen from Table 2, the training performance achieves an 80% level of
accuracy, while a fairly respectable 77% accuracy is attained on the unseen
test set of sequences. In evaluating these results it should be borne in mind
that the there are a number of equally acceptable folded configurations for
any of the good sequences used in this task. Therefore it is not possible to
predict precisely what configuration a sequence will adopt when folded. The
best way to view what this network does is predict a configuration that is
typical for a particular type of sequence.

## Discussion

The results of these experiments have shown that while SRNs have a poor
ability to determine the refoldability of a given copolymer sequence, they
appear to be able to predict with some degree of accuracy the 3-D structure of
folded copolymers. In both cases, predictions are based on the hydrophobicity
of sequence elements. In the first experiment, the network proved more
reliable in its prediction of good folders than poor ones. This suggests that
determining the badness of a folding is based on fairly subtle and relatively
inaccessible information in the sequence. On the other hand, the second
experiment suggests that the use of the DIM prediction framework seems a
viable technique for accurately predicting a structure for folded copolymers.
Moreover, the technique presented are not limited to any particular sequence
length, and could be trained on a sequence of different lengths.

## Future work

The next goal of the research described here, is to generalise the results to
longer sequences, and to apply the techniques described here to real protein
sequences with secondary as well as tertiary structure. Bohr and his co-
workers [3,4] have used non-recurrent feed-forward networks which takes a sub-
sequence of the amino acid residue sequence in an input window222Bohr and
colleagues use a window with uniform resolution, unlike the method employed
here. and outputs both the rows of the DIM associated with the residue in the
window’s centre and the class of secondary structure (e.g., $\alpha$-helix,
$\beta$-sheet) to which it belongs. On the basis of the research described
here, it is conjectured that it may not be necessary to explicitly train the
SRN to recognise the secondary structure of the subsequence, given that the
window provides a relatively large view of the sequence neighbourhood compared
to Bohr’s method, and thus may permit the implicit “recognition” of secondary
structure.

## References

  * [1] Qian, N., and Sejnowski, T.J. (1988). Predicting the secondary structure of globular proteins using neural network models. J. Mol. Biol., 202, 865-884.
  * [2] McGregor, M. J., Flores, T. P., & Sternberg, M.J.E. (1989). Prediction of beta turns in proteins using neural networks. Protein Eng., 2, 521-526.
  * [3] Bohr, J., Bohr, H., Brunak, S., Cotterill, R.M.J., Fredholm, H., Lautrup, B., Petersen, S.B. (1990). A novel approach to prediction of the 3-dimensional structures of protein backbones by neural networks. FEBS Letter, 261, 43-46.
  * [4] Bohr, J., Bohr, H., Brunak, S., Cotterill, R.M.J., Fredholm, H., Lautrup, B. and Petersen, S.B. (1993) Protein Structures from Distance Inequalities. J. Mol. Biol., 231, 861-869.
  * [5] Kechadi, M-T, Reilly, R.G., Kuznetsov, Y., Timoshenko, E., Dawson, K. A study of sequence distributions of a painted globule as a model for proteins with good folding properties. arXiv:cond-mat/0104440.
  * [6] Elman, J.E. (1990). Finding structure in time. Cognitive Science, 14, 179-211.
  * [7] Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning internal representations by error propagation. In D. E. Rumelhart, J. L. McClelland, & The PDP Research Group (Eds.), Parallel distributed processing. Explorations in the microstructure of cognition. Volume 1: Foundations. Cambridge, MA: MIT Press.
  * [8] Klinger, T.M., & Brutlag, D.L. (1994). Discovering structural correlations in alpha helices. Protein Science, 3, 1847-1857.
  * [9] Binder, K. (1987). Applications of Monte Carlo methods in statistical physics, 2nd Edition. Berlin: Springer-Verlag.