# Quasihomomorphisms from the integers into Hamming metrics

Jan Draisma  Mathematical Institute, University of Bern, Sidlerstrasse 5, 3012
Bern, Switzerland; and Department of Mathematics and Computer Science,
Eindhoven University of Technology, P.O. Box 513, 5600MB, Eindhoven, the
Netherlands<EMAIL_ADDRESS>,  Rob H. Eggermont  Department of
Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box
513, 5600MB, Eindhoven, the Netherlands<EMAIL_ADDRESS>,  Tim Seynnaeve
Mathematical Institute, University of Bern, Alpeneggstrasse 22, 3012 Bern,
Switzerland<EMAIL_ADDRESS>,  Nafie Tairi  Mathematical Institute,
University of Bern, Alpeneggstrasse 22, 3012 Bern, Switzerland
<EMAIL_ADDRESS>and  Emanuele Ventura  Politecnico di Torino,
Dipartimento di Scienze Matematiche “G.L. Lagrange”, Corso Duca degli Abruzzi
24 10129 Torino, Italy<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

A function $f:\mathbb{Z}\to\mathbb{Q}^{n}$ is a $c$-quasihomomorphism if the
Hamming distance between $f(x+y)$ and $f(x)+f(y)$ is at most $c$ for all
$x,y\in\mathbb{Z}$. We show that any $c$-quasihomomorphism has distance at
most some constant $C(c)$ to an actual group homomorphism; here $C(c)$ depends
only on $c$ and not on $n$ or $f$. This gives a positive answer to a special
case of a question posed by Kazhdan and Ziegler.

###### Key words and phrases:

Quasihomomorphisms, Hamming distance, Linear approximation

###### 2020 Mathematics Subject Classification:

11B30

JD,TS,NT,EV were partially or fully supported by Vici grant 639.033.514 from
the Netherlands Organisation for Scientific Research (NWO) and Swiss National
Science Foundation (SNSF) project grant 200021_191981. RE was supported by NWO
Veni grant 016.Veni.192.113.

##  1\. Introduction

A $c$-quasihomomorphism from a group $G$ to a group $H$ with a left-invariant
metric $d$ is a map $f:G\to H$ such that $d(f(xy),f(x)f(y))\leq c$ for all
$x,y$ in $G$. A central question in geometric group theory, first raised by
Ulam in [Ula60, Chapter 6], is whether there exists an actual homomorphism
$f^{\prime}:G\to H$ such that $d(f(x),f^{\prime}(x))$ is at most some constant
$C$ for all $x$. Different versions of this question are of interest: for
instance, $C$ may be allowed to depend on $c,G,(H,d)$ but not on $f$; or
$G,(H,d)$ may be restricted to certain classes and or $C$ is only allowed to
depend on $c$.

A well-known example where the answer to this question is negative is the case
where $G=H=\mathbb{Z}$ with the standard metric. Here, quasihomomorphisms
modulo bounded maps are a model of the real numbers [A’C21], and the answer is
yes only for those quasihomomorphisms that correspond to integers.

Much literature in this area focusses on quasimorphisms, which are
quasihomomorphisms into the real numbers $\mathbb{R}$ with the standard
metric; we refer to [Kot04] for a brief introduction. In another branch of the
research on quasihomomorphisms $H$ is assumed nonabelian, and one of the first
positive results on the central question above is Kazhdan’s theorem on
$\varepsilon$-representations of amenable groups [Kaz82]. For more recent
results on quasihomomorphisms into nonabelian groups we refer to [FK16] and
the references there.

The following instance of the central question was formulated by Kazhdan and
Ziegler in their work on approximate cohomology [KZ18].

######  Question 1.1.

Let $c\in\mathbb{N}$. Does there exist a constant $C=C(c)$ such that the
following holds: For all $n\in\mathbb{N}$ and all functions
$f:\mathbb{Z}\longrightarrow\mathbb{C}^{n\times n}$ such that

$\forall x,y\in\mathbb{Z}:\qquad\mathrm{rk}(f(x+y)-f(x)-f(y))\leq c,$

there exists a matrix $g$ such that

$\forall x\in\mathbb{Z}:\qquad\mathrm{rk}(f(x)-x\cdot g)\leq C(c)?$

Here, $G$ equals $\mathbb{Z}$ and $H$ equals $\mathbb{C}^{n\times n}$, both
with addition, and the metric on $H$ is defined by
$d(A,B):=\operatorname{rk}(A-B)$. Our main result is an affirmative answer to
this question in the special case where all matrices $f(x)$ are assumed to be
diagonal.

######  Definition 1.2.

Let $(Q,+)$ be an abelian group. For an element $v\in Q^{n}$, the _Hamming
weight_ $w_{H}(v)$ is the number of nonzero entries of $v$. For a pair of
elements $u,v\in Q^{n}$, their _Hamming distance_ is $w_{H}(v-u)$. This metric
is clearly left-invariant.

######  Definition 1.3.

Let $A$ be another abelian group. A function $f:A\to Q^{n}$ is called a
$c$-quasihomomorphism if

$\forall x,y\in A:\qquad w_{H}(f(x+y)-f(x)-f(y))\leq c.$

######  Remark 1.4.

The map $\operatorname{diag}:\mathbb{C}^{n}\to\mathbb{C}^{n\times n}$ is an
isometric embedding from $\mathbb{C}^{n}$ with the Hamming metric to
$\mathbb{C}^{n\times n}$ with the rank metric. This connects Definition 1.3 to
Question 1.1.

######  Definition 1.5.

Let $C\in\mathbb{N}$ and let $f:A\to Q^{n}$ be a $c$-quasihomomorphism. A
group homomorphism $h:A\to Q^{n}$ is a $C$-approximation of $f$ if the Hamming
distance between $f$ and $h$ satisfies

$\forall x\in A:\qquad w_{H}(f(x)-h(x))\leq C.$

We are ready to state our main result.

######  Theorem 1.6 (Main Theorem).

Let $c\in\mathbb{N}$. Then there exists a constant $C=C(c)\in\mathbb{N}$ such
that for all $n\in\mathbb{N}$ and $c$-quasihomorphisms
$f:\mathbb{Z}\to\mathbb{Q}^{n}$, we have:

$\forall x\in\mathbb{Z}:\qquad w_{H}(f(x)-x\cdot f(1))\leq C.$

Moreover, we can take $C=28c$.

######  Remark 1.7.

The coefficient $28$ is probably not optimal. However, we certainly have that
$C(c)\geq c$. Indeed, any map $f:\mathbb{Z}\to Q^{n}$ for which the only
nonzero entries of $f(x)$ are among the first $c$, is automatically a
$c$-quasimorphism.

######  Corollary 1.8.

Theorem 1.6 also holds with $\mathbb{Q}$ replaced by any torsion-free abelian
group $Q$, with the same value of $C=C(c)$.

###### Proof.

Suppose, for a contradiction, that we have a $c$-quasihomomorphism
$f:\mathbb{Z}\to Q^{n}$ but $w_{H}(f(y)-y\cdot f(1))>C$ for some
$y\in\mathbb{Z}$. Since $Q$ is torsion-free, the natural map $\iota$ from $Q$
into the $\mathbb{Q}$-vector space $V:=\mathbb{Q}\otimes_{\mathbb{Z}}Q$ is
injective. Consequently, $g:=\iota^{n}\circ f$ is a $c$-quasihomomorphism
$\mathbb{Z}\to V^{n}$ with $w_{H}(g(y)-y\cdot g(1))>C$. Now choose any
$\mathbb{Q}$-linear function $\xi:V\to\mathbb{Q}$ that is nonzero on the
nonzero entries of $g(y)-y\cdot g(1)$. Then $h:=\xi^{n}\circ g$ is a
$c$-quasihomomorphism $\mathbb{Z}\to\mathbb{Q}^{n}$ with $w_{H}(h(y)-y\cdot
h(1))>C$, a contradiction to Theorem 1.6. ∎

Theorem 1.6 shows that for a $c$-quasihomomorphism
$f:\mathbb{Z}\to\mathbb{Q}^{n}$, the group homomorphism
$\tilde{f}:\mathbb{Z}\to\mathbb{Q}^{n}$ defined by $\tilde{f}(x)=x\cdot f(1)$
gives a $C$-approximation for some constant $C\in\mathbb{N}$ independent on
$n$. However, $\tilde{f}$ need not be the homomorphism closest to $f$, as the
next example shows.

######  Example 1.9.

Let $c=1$ and $n\geq 3$. Define $f:\mathbb{Z}\to\mathbb{Q}^{n}$ to be

$f(x)=\left(\left\lfloor\frac{2x+2}{5}\right\rfloor,\left\lfloor\frac{x+2}{5}\right\rfloor,\alpha_{x},0,\ldots,0\right),$

where $\alpha_{x}$ is arbitrary if $5\mid x$, and $\alpha_{x}=0$ otherwise.
This is a $1$-quasihomomorphism.

Note that $w_{H}(f(x)-x\cdot f(1))\leq 3$ where equality is sometimes
achieved. However, there also exist $2$-approximations of $f$. For instance,
letting $v=(\frac{2}{5},\frac{1}{5},0,\ldots,0)\in\mathbb{Q}^{n}$, one
verifies that

$w_{H}(f(x)-x\cdot v)\leq 2\qquad\forall x\in\mathbb{Z}.$

In fact, we can show that for every $1$-quasihomomorphism
$f:\mathbb{Z}\to\mathbb{Q}^{n}$ there exists a $2$-approximation, as claimed
in [KZ18]. The proof will appear in future work.

On the other hand, the following shows that the best possible approximation of
a given qusimorphism $f$ is at most twice as close as the homomorphism
$x\mapsto x\cdot f(1)$.

######  Remark 1.10.

Suppose that a map $f:\mathbb{Z}\to\mathbb{Q}^{n}$ has a
$C^{\prime}$-approximation $h$. Then $h(x)=x\cdot v$ for some
$v\in\mathbb{Q}^{n}$, and

$w_{H}(f(x)-x\cdot v)\leq C^{\prime}\qquad\forall x\in\mathbb{N}.$

Substituting $x=1$ yields $w_{H}(f(1)-v)\leq C^{\prime}$. Thus

$w_{H}(f(x)-x\cdot f(1))\leq w_{H}(f(x)-x\cdot v)+w_{H}(x\cdot v-x\cdot
f(1))\leq 2C^{\prime}.$

######  Remark 1.11.

A result similar to Theorem 1.6 is easily proven in finite characteristic if
we allow the constant $C$ to depend on the characteristic. Let $K$ be a field
of characteristic $p>0$, and let $f:\mathbb{Z}\to K^{n}$ be a
$c$-quasihomomorphism. Then there exists a constant $C=C(p,c)$ such that
$w_{H}(f(x)-x\cdot f(1))\leq C$, for all $x\in\mathbb{Z}$.

To see this, we observe that for all $u,v\in\mathbb{Z}$ with $u\geq 1$, we
have

$w_{H}(f(uv)-uf(v))\leq(u-1)c.$

This follows by repeatedly applying the inequality
$w_{H}(f(uv)-f((u-1)v)-f(v))\leq c$ if $u>1$; the case $u=1$ is trivial.

For $x=kp+r$ with $k\in\mathbb{Z}$ and $0\leq r\leq p-1$, we have

$w_{H}(f(x)-xf(1))=w_{H}(f(kp+r)-rf(1));$

here we have used that $p\cdot f(1)=0$. We rewrite the latter as

$w_{H}(f(kp+r)-f(kp)-f(r)+f(kp)+f(r)-rf(1)).$

We have $w_{H}(f(kp+r)-f(kp)-f(r))\leq c$; $w_{H}(f(kp))\leq(p-1)c$ using our
observation with $u=p,v=k$; and also $w_{H}(f(r)-rf(1))\leq(p-2)c$ (in the
case $r>0$) using our main observation. In total, this gives
$w_{H}(f(x)-xf(1))\leq 2(p-1)c$, so we can take $C=2(p-1)c$.

The remainder of this paper is organized as follows. In Section 2 we prove an
auxiliary result of independent interest: maps from a finite abelian group
into a torsion-free group that are almost a homomorphism, are in fact almost
zero. Then, in Section 3, we apply this auxiliary result to the component
functions of a $c$-quasimorphism $\mathbb{Z}\to\mathbb{Q}^{n}$ to prove the
Main Theorem.

##  2\. Almost homomorphisms are almost zero

Let $A$ be a finite abelian group and let $H$ be a torsion-free abelian group.
The only homomorphism $A\to H$ is the zero map. The following proposition says
that maps that are, in a suitable sense, close to being homomorphisms, are in
fact also close to the zero map.

######  Proposition 2.1.

Let $a$ be a positive integer, $A$ an abelian group of order $a$, $H$ a
torsion-free abelian group, $q\in[0,1]$, and $f:A\to H$ a map. Suppose that
the zero set

$Z(f):=\\{b\in A\mid f(b)=0\\}$

has cardinality at most $qa$. Then the problem set

$P(f):=\\{(b,c)\in A\times A\mid f(b+c)\neq f(b)+f(c)\\}$

has cardinality at least
$\left(\frac{a-qa}{2}\right)\cdot\left(\frac{a-qa}{2}+1\right)$.

The contraposition of this statement says that if $P(f)$ is a small fraction
of $a^{2}$, so that $f$ can be thought of as an (additive) “almost
homomorphism” $A\to H$, then $q$ must be close to $1$ so that $f$ is
essentially zero.

###### Proof.

Since $H$ is torsion-free, it embeds into the $\mathbb{Q}$-vector space
$V:=\mathbb{Q}\otimes_{\mathbb{Z}}H$. By basic linear algebra, there exists a
$\mathbb{Q}$-linear function $\xi:V\to\mathbb{Q}$ such that $\xi(f(b))\neq 0$
for all $b\not\in Z(f)$, so that $Z(\xi\circ f)=Z(f)$. Since $P(\xi\circ
f)\subseteq P(f)$, it suffices to prove the proposition for $\xi\circ f$
instead of $f$. In other words, we may assume from the beginning that
$H=\mathbb{Q}$.

Set

$B:=\\{b\in A\mid f(b)>0\\}.$

Let $\lambda_{1}>\lambda_{2}>\ldots>\lambda_{k}>0$ be the distinct values in
$f(B)$, and for each $i=1,\ldots,k$ set

$B_{i}:=\\{b\in B\mid f(b)=\lambda_{i}\\}\text{ and }n_{i}:=|B_{i}|;$

as well as $n:=n_{1}+\cdots+n_{k}=|B|$.

Now for each $c\in B_{1}$ and each $b\in B$ we have

$f(b)+f(c)=f(b)+\lambda_{1}>\lambda_{1}$

so that the left-hand side is not in $f(B)$ and in particular not equal to
$f(b+c)$. We have thus found $n_{1}\cdot(n_{1}+\cdots+n_{k})$ pairs $(b,c)\in
P(f)$ with $c\in B_{1}$.

Next, suppose $(b,c)$ is a pair with $c\in B_{2}$, $b\in B$, and $(b,c)\not\in
P(f)$. Then

$f(b+c)=f(b)+f(c)>f(c)=\lambda_{2}$

and hence $b+c\in B_{1}$. But given $c$, there are at most $n_{1}$ values of
$b$ with $b+c\in B_{1}$. (Note that here we have used that $A$ is a group.)
Hence we have at least $n_{2}\cdot(n_{2}+\cdots+n_{k})$ pairs $(b,c)\in P(f)$
with $c\in B_{2}$.

Similarly, we find at least $n_{i}\cdot(n_{i}+\cdots+n_{k})$ pairs $(b,c)\in
P(f)$ with $c\in B_{i}$. In total, we have therefore found at least

$\sum_{i=1}^{k}n_{i}\cdot(n_{i}+\cdots+n_{k})\geq\frac{n(n+1)}{2}$ (2.1)

pairs in $P(f)$; see Figure 1.

Let $B^{\prime}:=\\{b^{\prime}\in A\mid f(b^{\prime})<0\\}$ and
$n^{\prime}:=|B^{\prime}|$. Repeating the same argument above with
$B^{\prime}$ and $n^{\prime}$, we find at least $n^{\prime}(n^{\prime}+1)/2$
further pairs in $P(f)$, disjoint from those found above. Since $|Z(f)|\leq
qa$, we have $n+n^{\prime}\geq a(1-q)$. Therefore

$|P(f)|\geq\frac{n(n+1)}{2}+\frac{n^{\prime}(n^{\prime}+1)}{2}=\frac{n^{2}+n^{\prime
2}}{2}+\frac{n+n^{\prime}}{2}\geq\left(\frac{n+n^{\prime}}{2}\right)^{2}+\frac{n+n^{\prime}}{2},$

where the second inequality is the Cauchy-Schwarz inequality

$\left(n^{2}+n^{\prime
2}\right)\left(\frac{1}{2^{2}}+\frac{1}{2^{2}}\right)\geq\left(\frac{n}{2}+\frac{n^{\prime}}{2}\right)^{2}.$

Since $n+n^{\prime}\geq a(1-q)$, we conclude that

$|P(f)|\geq\left(\frac{a-qa}{2}\right)\cdot\left(\frac{a-qa}{2}+1\right).\qed$

Figure 1. On the left, a graphical proof of the inequality (2.1): the left-
hand side is the number of small squares in the shaded region, the right-hand
side is the number of squares on or above the main diagonal. On the right, a
proof of the inequality (2.2): the left-hand side is the area of the shaded
region, the right-hand side, the area enclosed by the dashed line.

######  Remark 2.2.

The lower bound in Proposition 2.1 is sharp. Let $a=2k+1\in\mathbb{Z}$,
consider $A:=\mathbb{Z}/a\mathbb{Z}$ and define $f:A\to\mathbb{Z}$ as
$f(x):=$the representative of $x+a\mathbb{Z}$ in $\\{-k,\ldots,0,\ldots,k\\}$.
We take $q=\frac{Z(f)}{a}=\frac{1}{2k+1}$. Then $f(x+y)=f(x)+f(y)$ if and only
if the right-hand side is still inside the interval $\\{-k,\ldots,k\\}$, and a
straightforward count shows that this is the case for $3k^{2}+3k+1$ pairs
$(x,y)\in A^{2}$. Hence $P(f)$ has size $k\cdot(k+1)$, which equals
$\left(\frac{a-qa}{2}\right)\cdot\left(\frac{a-qa}{2}+1\right)$. A similar
construction for $a=2k$ yields a problem set of size $\frac{a^{2}}{4}=k^{2}$,
which equals the ceiling of the lower bound $\frac{a^{2}}{4}-\frac{1}{4}$.

Below, we will use the following strengthening of Proposition 2.1:

######  Proposition 2.3.

Let $a,A,H,q$ and $f$ be as in 2.1. Furthermore, let $p\in[0,\frac{1-q}{2})$
and let $S\subseteq A$ be a subset of cardinality at most $pa$. Then the set

$P_{S}(f):=\\{(b,c)\in A\times A\mid f(b+c)\neq f(b)+f(c)\text{ and }b+c\notin
S\\}.$

has cardinality at least
$\left(\frac{a(1-q-2p)}{2}\right)\cdot\left(\frac{a(1-q-2p)}{2}+1\right)$.

###### Proof.

Keep the notation from the proof of 2.1. Recall $n=|B|$ and
$n^{\prime}=|B^{\prime}|$. Note that for a fixed $b$, there can be at most
$pa$ choices of $c$ with $b+c\in S$. We then find at least
$n_{i}\cdot(n_{i}+\cdots+n_{k}-pa)$ pairs $(b,c)\in P_{S}(f)$ with $b\in
B_{i}$. Letting $k^{\prime}\leq k$ be the largest index for which the second
factor $(n_{k^{\prime}}+\cdots+n_{k}-pa)$ is nonnegative, as in the proof of
2.1, we find that $B$ contributes at least

$\displaystyle\sum_{i=1}^{k^{\prime}}{n_{i}\cdot(n_{i}+\cdots+n_{k}-pa)}$
$\displaystyle=\sum_{i=1}^{k^{\prime}}{n_{i}\cdot(n-n_{1}-\cdots-n_{i-1}-pa)}$
$\displaystyle\geq(n-pa)(n-pa+1)/2$ (2.2)

to $P_{S}(f)$; see Figure 1. Similarly, $B^{\prime}$ contributes at least
$(n^{\prime}-pa)(n^{\prime}-pa+1)/2$, and these contributions are disjoint.
The desired inequality follows as in the proof of 2.1 but with $n,n^{\prime}$
replaced by $n-pa,n^{\prime}-pa$. ∎

The key ingredient for the proof of Theorem 1.6 is the following corollary of
2.3. Here, and in the rest of the paper, we write $[a]$ for the set
$\\{1,2,\ldots,a\\}$.

######  Corollary 2.4.

Let $p,q\in[0,1]$ such that $p<\frac{1-q}{2}$. Let $f:[2a]\to\mathbb{Q}$ such
that:

  1. (1)

$|Z(f)|\leq qa$, where $Z(f)\coloneqq\\{x\in[a]\mid f(x)=0\\}$ is the zero
set.

  2. (2)

$|NP(f)|\leq pa$, where $NP(f)\coloneqq\\{x\in[a]\mid f(x+a)\neq f(x)\\}$ is
the nonperiodicity set.

Then

$|P(f)|\geq\frac{(1-q-2p)^{2}}{4}a^{2}+\frac{(1-q-2p)}{2}a,$

where

$P(f)=\\{(x,y)\in[a]\times[a]\mid f(x+y)\neq f(x)+f(y)\\}.$

###### Proof.

Let $\tilde{f}$ be the restriction of $f$ to the interval $[a]$, and identify
$\mathbb{Z}/{a\mathbb{Z}}$ with $[a]$ with the group operation $*$ defined by
$x*y:=x+y\ (\operatorname{mod}\ a)$.

Let $S=NP(f)$, and apply 2.3 to $\tilde{f}$. We find that

$P_{S}(\tilde{f})=\\{(b,c)\in\mathbb{Z}/{a\mathbb{Z}}\times\mathbb{Z}/{a\mathbb{Z}}\mid\tilde{f}(b*c)\neq\tilde{f}(b)+\tilde{f}(c)\text{
and }b*c\notin S\\}$

has cardinality at least $\frac{(1-q-2p)^{2}}{4}a^{2}+\frac{(1-q-2p)}{2}a$.
Since $b*c\notin S$ implies that $\tilde{f}(b*c)=f(b+c)$, this set is
contained in the problem set $P(f)$. ∎

##  3\. Proof of the Main Theorem

The main goal of this section is to prove Theorem 1.6. We start with some
definitions.

######  Definition 3.1.

Let $1<a$, and $f:[2a]\to\mathbb{Q}$. We define the following _problem sets of
$f$_:

$P(f):=\\{(x,y)\in[a]\times[a]\mid f(x+y)\neq f(x)+f(y)\\},$

and

$P_{1}(f):=\\{x\in[a]\mid f(x+1)\neq f(x)+f(1)\\},$

and

$P_{a}(f):=\\{x\in[a]\mid f(x+a)\neq f(x)+f(a)\\}.$

Furthermore, we recall that the zero set of $f$ is defined as

$Z(f):=\\{x\in[a]\mid f(x)=0\\}.$

The following proposition says that $P_{1}(f),P_{a}(f),P(f)$ cannot be
simultaneously small.

######  Proposition 3.2.

Let $p,q\in(0,1)$ such that $p<\frac{1-q}{2}$, $a\in\mathbb{N}$ with $1<a$,
and let $f:[2a]\to\mathbb{Q}$ such that $f(a)\neq af(1)$. If

$|P_{1}(f)|\leq qa\quad\text{and}\quad|P_{a}(f)|\leq pa$

then

$|P(f)|\geq F(p,q)\cdot a^{2},$

where

$F(p,q)=\frac{(1-q-2p)^{2}}{4}.$

###### Proof.

Without loss of generality we can assume $f(a)=0$ and hence $f(1)\neq 0$.
Indeed, suppose we have shown the statement for every $\tilde{f}$ with
$\tilde{f}(a)=0$. Then for any $f:[2a]\to\mathbb{Q}$ with $f(a)\neq af(1)$, we
take $\tilde{f}:[2a]\to\mathbb{Q}$ to be $\tilde{f}(x)=af(x)-xf(a)$. Now we
observe that $\tilde{f}(a)=0\neq a\tilde{f}(1)$, and that $P(f)=P(\tilde{f})$,
$P_{1}(f)=P_{1}(\tilde{f})$, $P_{a}(f)=P_{a}(\tilde{f})$.

We write $Z(f)=\\{x_{1}<\cdots<x_{m}\\}$. Note that for $1\leq i<m$, one of
the elements $x_{i},x_{i}+1,\ldots,x_{i+1}-1$ needs to be in $P_{1}(f)$ since
$f(x_{i+1})\neq f(x_{i})+(x_{i+1}-x_{i})f(1)$. Likewise, at least one of the
elements $1,2,\ldots,x_{1}-1$ needs to be in $P_{1}(f)$. Thus we have

$|Z(f)|\leq|P_{1}(f)|\leq qa,$

and by assumption we have $|NP(f)|=|P_{a}(f)|\leq pa$. Now we can apply
Corollary 2.4 to conclude. ∎

We now prove Theorem 1.6.

###### Proof of the Main Theorem..

Consider a $c$-quasihomomorphism
$f=(f_{1},\ldots,f_{n}):\mathbb{Z}\to\mathbb{Q}^{n}$. Our goal is to show that
for every $a\in\mathbb{Z}$ we have $w_{H}(f(a)-a\cdot f(1))\leq C$ for some
constant $C$ depending only on $c$. We start with the case $a>0$.

Write $M:=w_{H}(f(a)-af(1))$. Without loss of generality, we have
$f_{1}(a)\neq af(1)$, …, $f_{M}(a)\neq af(1)$. We will show that $M\leq
C^{\prime}$ for some constant $C^{\prime}$ depending on $c$ only. To this end,
fix small parameters $p,q\in(0,1)$ (to be optimized over later) and consider
the restrictions $f_{i}:[2a]\to\mathbb{Q}$ of the components of $f$. By 3.2,
for every $i$, we have that either

  1. (i)

$|P_{1}(f_{i})|>qa$, or

  2. (ii)

$|P_{a}(f_{i})|>pa$, or

  3. (iii)

$|P(f_{i})|\geq F(p,q)a^{2}$.

Let $m_{0}$ be the number of coordinates $i$ such that (iii) holds. We define
$m_{1}$ and $m_{2}$ analogously, for (i) and (ii) respectively.

By counting the number of triples $(i,x,y)\in[M]\times[a]\times[a]$ such that
$f_{i}(x+y)-f_{i}(x)-f_{i}(y)\neq 0$ in two ways, we see that

$\sum_{x=1}^{a}\sum_{y=1}^{a}{w_{H}\left(f(x+y)-f(x)-f(y)\right)}=\sum_{i=1}^{M}{|P(f_{i})|}.$

Because $f$ is a $c$-quasihomomorphism, the left hand side is at most
$a^{2}c$. On the other hand, the right hand side is at least
$m_{0}F(p,q)a^{2}$, so

$a^{2}c\geq\sum_{x=1}^{a}\sum_{y=1}^{a}{w_{H}\left(f(x+y)-f(x)-f(y)\right)}=\sum_{i=1}^{M}{|P(f_{i})|}\geq
m_{0}F(p,q)a^{2}.$

So we obtain $m_{0}\leq\frac{c}{F(p,q)}$. Similarly we find

$ac\geq\sum_{x=1}^{a}{w_{H}\left(f(x+1)-f(x)-f(1)\right)}=\sum_{i=1}^{M}{|P_{1}(f_{i})|}>m_{1}qa,$

so that $m_{1}<\frac{c}{q}$. Finally,

$ac\geq\sum_{x=1}^{a}{w_{H}\left(f(x+a)-f(x)-f(a)\right)}=\sum_{i=1}^{M}{|P_{a}(f_{i})|}>m_{2}pa.$

So $m_{2}<\frac{c}{p}$. But now
$M=m_{0}+m_{1}+m_{2}<c(\frac{1}{F(p,q)}+\frac{1}{q}+\frac{1}{p})=:C^{\prime}$.

The case $a=0$ is easy: we have

$w_{H}(f(0))=w_{H}(f(0)-f(0)-f(0))\leq c.$

Finally, let us consider the case $a<0$. Then

$\displaystyle w_{H}(f(a)-a\cdot f(1))\leq$ $\displaystyle
w_{H}(f(a)+f(-a)-f(0))+w_{H}(f(0))$ $\displaystyle+w_{H}(f(-a)-(-a)\cdot
f(1))$ $\displaystyle\leq$ $\displaystyle 2c+C^{\prime}=:C.$

This completes the proof. ∎

To get the explicit bound $28c$ from Theorem 1.6, we minimize the function

$2+\frac{1}{q}+\frac{1}{p}+\frac{1}{F(p,q)}=2+\frac{1}{q}+\frac{1}{p}+\frac{4}{(1-q-2p)^{2}}.$

Note that this function is strictly convex for $(p,q)\in\mathbb{R}_{>0}^{2}$,
so that it has at most one minimum in the positive orthant. We find this by
setting the partial derivatives equal to zero and solving for $p,q$. The
minimum is $\approx 27.6817$ and attained at $(p,q)\approx(0.1167,0.16500)$.

## References

  * [A’C21] N. A’Campo.  A natural construction for the real numbers.  Elem. Math., 76(3):89–105, 2021.
  * [FK16] K. Fujiwara and M. Kapovich.  On quasihomomorphisms with noncommutative targets.  Geom. Funct. Anal., 26(2):478–519, 2016.
  * [Kaz82] D. Kazhdan.  On $\varepsilon$-representations.  Israel J. Math., 43(4):315–323, 1982.
  * [Kot04] D. Kotschick.  What is$\dots$a quasi-morphism?  Notices Amer. Math. Soc., 51(2):208–209, 2004.
  * [KZ18] D. Kazhdan and T. Ziegler.  Approximate cohomology.  Selecta Math. (N.S.), 24(1):499–509, 2018.
  * [Ula60] S. M. Ulam.  A collection of mathematical problems.  Interscience Tracts in Pure and Applied Mathematics, no. 8. Interscience Publishers, New York-London, 1960.


# Crypto Pump and Dump Detection via Deep Learning Techniques

Viswanath Chadalapaka
<EMAIL_ADDRESS>
&Kyle Chang
<EMAIL_ADDRESS>
&Gireesh Mahajan
<EMAIL_ADDRESS>
&Anuj Vasil
<EMAIL_ADDRESS>

(May 8, 2022)

###### Abstract

Despite the fact that cryptocurrencies themselves have experienced an
astonishing rate of adoption over the last decade, cryptocurrency fraud
detection is a heavily under-researched problem area. Of all fraudulent
activity regarding cryptocurrencies, pump and dump schemes are some of the
most common. Though some studies have been done on these kinds of scams in the
stock market, the lack of labelled stock data and the volatility unique to the
cryptocurrency space constrains the applicability of studies on the stock
market toward this problem domain. Furthermore, the only work done in this
space thus far has been either statistical in nature, or has been concerned
with classical machine learning models such as random forest trees. We propose
the novel application of two existing neural network architectures to this
problem domain and show that deep learning solutions can significantly
outperform all other existing pump and dump detection methods for
cryptocurrencies.

##  1 Introduction

In 2021 alone, cryptocurrencies (or “crypto”) experienced over $14 trillion
worth of trading volume, representing nearly a 700% increase over the previous
year. In that same year, the Binance cryptocurrency exchange (or just
“exchange”) was responsible for over two-thirds of that volume Khatri (2021).
As crypto and the use of these exchanges enters the mainstream, the
conversation surrounding their regulatory hurdles has intensified Cumming et
al. (2019). Of those hurdles, the detection of fraudulent activities at scale
is one of the most pressing, given the rapid growth of the space. Despite
these concerns, the amount of regulation in crypto pales in comparison to more
mainstream flows of money, such as stocks. This allows fraud to plague the
crypto space at a level unheard of in the stock market.

Among all types of fraud in the crypto space, pump and dump (P&D) schemes are
some of the most popular, and some of the easiest, to execute on Twomey and
Mann (2020) – generally resulting from the concerted effort of just a single
online P&D planning group Hamrick et al. (2021). Despite that, no studies have
been done to-date on the application of deep learning to P&D detection in
crypto. Though some studies involving the application of deep learning have
been done in the context of traditional securities such as stocks Leangarun et
al. (2018), these studies not only lacked the amount of data now freely
available for crypto (via the blockchain), but also have no guarantee of
applicability to the much more volatile world of crypto.

This paper presents two novel applications of existing deep learning methods
to detect P&D schemes in crypto – specifically, for small, volatile
cryptocurrencies also known as altcoins. Our work focuses on taking advantage
of the bulk of freely available data by using deep learning to drive
performance gains, since previous works in this space have thus far only
applied either classical machine learning techniques such as random forest
trees La Morgia et al. (2020), or more basic techniques such as statistic
analyses Kamps and Kleinberg (2018) to the problem. All of our work is
reproducible, and a link to our code can be found in the footnote below.
111https://github.com/Derposoft/crypto_pump_and_dump_with_deep_learning

Example of a P&D Scheme on REAP Token

Figure 1: An example of an organized P&D scheme on the REAP token. Red stars
indicate visual signs of the accumulation phase in the form of subtle buying
pressure, while the blue star indicates the pump and dump phases of the
scheme. This data was manually obtained directly from the KuCoin exchange
(https://www.kucoin.com/trade/REAP-USDT), although the same information can be
found on other exchanges as well. Publicly-available videos on YouTube can
confirm that this fluctuation in the REAP token’s price was a result of a
planned P&D operation Coffeezilla (2021).

##  2 Related Work

###  2.1 Application of Classical Machine Learning and Statistical Models to
Crypto P&D Detection

To-date, only classical machine learning models such as random forest trees
have been applied in the crypto space to detect P&D schemes La Morgia et al.
(2020). Statistical models have also been applied in this domain Kamps and
Kleinberg (2018). These models often aggregate trade data at a high level and
use these coalesced features to predict when a P&D scheme will occur. As these
are the only works that have been done in this niche, we hope that our own
work in this paper will help build a better foundation in this domain going
forward.

###  2.2 Application of Deep Learning to General Anomaly Detection

Anomaly detection in a general setting unrelated to crypto is a well-
researched field. More specifically, studies involving the application of deep
learning to time-series anomaly detection problems have been done involving
multiple network architectures: LSTMs Malhotra et al. (2016), convolutional
networks Kwon et al. (2018), and various combinations of the two Kim and Cho
(2018); and more recently, multiple variations of attention-based methods such
as RNN attention Brown et al. (2018) or the anomaly transformer Xu et al.
(2021) have also been explored. As of writing this paper, deep learning
architectures are at the forefront of time-series anomaly detection due to
their strength in making predictions using spatiotemporal relationships, which
are key to strong anomaly detection models Kim and Cho (2018). In this work,
we implement, modify, and tune some of these latest architectures in an
attempt to adapt them to the crypto domain.

##  3 Background

While P&D is heavily fined by the SEC in traditional financial markets (e.g.
stocks), crypto remains to be regulated at a federal level. This opens the
opportunity for various P&D groups to openly plan P&D events over online
messaging platforms such as Telegram or Discord La Morgia et al. (2020).
Typically, a P&D scheme consists of three phases: the accumulation phase, the
promotion (or “pump”) phase, and the distribution (or “dump”) phase.

During the accumulation phase, the group organizing the scheme slowly
accumulates a significant position in the asset of interest. Once ready, the
promotion phase begins: excitement is drummed up via social media promotion
for the asset, and bullish sentiment is falsified through fraudulent reports.
This causes retail investors to rally behind and invest in the asset, thereby
driving the price up. Finally, during the distribution phase, the perpetrator
of the scheme liquidates their position in the asset over a very short period
of time. Since the position being liquidated generally represents a
significant portion of the asset itself, this inevitably causes a crash in the
price of the original asset – leaving most of the retail investors who bought
during the promotion phase at a significant loss on their positions over an
extremely short time.

The graph in Fig. 1 is an example of a real P&D scheme on the REAP token which
occurred near the start of April 2021. In this case, the entirety of the pump
and dump phases lasted only a few minutes, and the accumulating party dumped
all of their coins as soon as the value of the token shot up. Investors who
bought during the peak of the pump would have been down nearly 90% in the span
of just a few minutes.

Successful P&D detection algorithms have the potential to alert investors of
P&D schemes before they occur, and could even enable regulatory bodies to
police this fraudulent activity in more cost and time-effective manners.
Ultimately, this could help to establish crypto as a much more legitimate
trading option, as well as save investors and exchanges millions from
potential scams and fraudulent activity.

##  4 Method

We propose the novel application of two architectures that have scored well on
standard anomaly detection datasets to the now-burgeoning financial data also
available in the cryptocurrency space: the C-LSTM model Kim and Cho (2018),
and the Anomaly Transformer model Xu et al. (2021).

Since P&D schemes often have multiple phases that generally occur over vastly
different lengths of time (e.g. the accumulation phase may last for up to a
month, whereas the pump or dump phases can last for as little as a minute),
both of the models that we have chosen have the ability to capture both
longer-term anomalies – otherwise known as “trend” anomalies – and much
shorter-term anomalies – otherwise known as “point” anomalies. This capability
is important for the detection of P&D schemes, since models that are only
capable of one or the other could potentially be fooled by the volatility
inherent in crypto markets.

###  4.1 Models

####  4.1.1 C-LSTM

Our first model is the C-LSTM model, originally introduced by Kim and Cho
(2018) for learning anomaly detection by treating data as spatiotemporal in
nature. The model consists of a series of convolutional/ReLU/pooling layers to
encode the input sequence, followed by a set of LSTM layers, with decoding
done via a set of feedforward layers. In this model, convolutional layers help
to capture spatial information within the dataset, thereby helping to identify
point anomalies; on the other hand, the LSTM layers help to capture temporal
information, and help to identify trend anomalies. This simple model has shown
success in the detection of varying types of web traffic anomalies Kim and Cho
(2018), as well as anomalies across a number of stocks in the Chinese stock
market Yang et al. (2020). The following image is a visual representation of
the C-LSTM model.

##### Our Implementation

Our own model uses the following architecture: 1 set of
convolutional/ReLU/pooling layers with a convolution kernel size of 3 with a
stride of 1, and a pooling kernel size of 2 with a stride of 1; 1 LSTM layer
with an embedding dimension of 350; 1 feedforward layer which directly
projects the last hidden state of the LSTM to a dimension of 1; and a sigmoid
layer which constrains the output of our classifier between 0 and 1.

This setup resulted in a C-LSTM model with 997,851 learnable parameters which
was trained for 200 epochs.

####  4.1.2 Anomaly Transformer

The second model we explored was the Anomaly Transformer introduced by Xu et
al. (2021). Unlike a standard transformer, the Anomaly Transformer uses a
custom anomaly attention module to improve its performance in anomaly
detection scenarios. To that end, the model introduces two novelties: an
anomaly attention module, and a minimax optimization strategy. Additionally,
on top of this model, we introduced our own, original novelty – an altered
optimization strategy and loss function – in order to adapt the model to a
supervised setting, since this model was first developed and intended for
unsupervised settings. The Anomaly Transformer model was chosen because it is
the current state-of-the-art anomaly detection model for general time-series
anomaly detection Xu et al. (2021), consistently achieving strong results
across a variety of standard datasets, including server sensor data Su et al.
(2019), rover data from NASA Keogh et al. (2021), and the NeurIPS 2021 time-
series benchmark Lai et al. (2022).

The first of the two novelties introduced by the Anomaly Transformer which
makes it particularly good at detecting anomalies is the replacement of the
standard self-attention computation with two, internally-computed association
values that influence the attention block: series association and prior
association. These two associations make up the “anomaly attention module” and
are as described below:

  1. 1.

Series association at each layer $l$, denoted $S^{l}$, is a simple self-
attention computation on the data before multiplying by the value matrix $V$
which is standard to a normal attention mechanism. Series association focuses
on longer-term trends, and helps in the detection of trend anomalies.

$S^{l}=Softmax(\frac{QK^{T}}{\sqrt{d_{model}}})$

  2. 2.

Prior association at each layer $l$, denoted $P^{l}$, computes a Gaussian
kernel for each point with respect to the input sequence. A rescale operation
is done to convert the result to discrete distributions for each layer $l$.
Prior association focuses more on local points, and helps the model in the
detection of point anomalies.

$P^{l}=Rescale\left(\left[\mathcal{N}(j|\mu=i,\sigma)\right]_{i,j\in{1,...,N}}\right)$

The second of the two novelties introduced by this model is the minimax
optimization process which takes place after computing the values $S^{l}$ and
$P^{l}$. This process consists of two phases: minimize and maximize. During
the minimize phase, the series association is moved towards the prior
association using the symmetric KL divergence formula, denoted $SKL$. During
the maximize phase, the series association is moved towards the original input
sequence by taking the absolute difference of the two. The series association
is also enlarged using the prior association (once again through the symmetric
KL divergence formula). Therefore, during the minimize phase, the prior
association approximates the series association. Then, during the maximize
phase, the series association pays more attention to non adjacent points since
it is enlarged by the prior association. As a result, a sequence generated by
prior and series associations will lower the attention value at any anomaly.
The total amount of difference between the two associations captured during
this process is encapsulated by the Association Discrepancy function, denoted
as $AD$. The data is then reconstructed after the minimax optimization via
multiplying the series association $S^{l}$ with the value matrix standard to
an attention module, $V$. The minimax strategy is visualized below.  Combining
these novelties means that the reconstructed series, denoted $\hat{X}$, will
greatly differ from the original series if an anomaly is present, making the
discrepancy greater and giving the model an easier time to identify anomalies.
After integrating in the reconstruction loss, the losses derived from each of
these two phases are summarized through the following equations, where
$\lambda>0$ and $L_{tot}$ represents the total loss:

$MinPhase:L_{tot}(\hat{X},P,S_{detach},-\lambda;X)$
$MaxPhase:L_{tot}(\hat{X},P_{detach},S,\lambda;X)$ $\displaystyle
L_{tot}(\hat{X},P,S,\lambda;X)={}$ $\displaystyle\|X-\hat{X}\|^{2}_{F}$
$\displaystyle-\lambda\|AD(P,S;X)\|$ $SKL(A,B)=KL(A\|B)+KL(B\|A)$
$\displaystyle
AD(P,S;X)=\frac{1}{L}\sum^{L}_{l=1}SKL(P^{l}_{i,:},S^{l}_{i,:})$
$\hat{X}=S^{l}V$

##### Our Implementation

Since our own problem was supervised, we modified the optimization strategy
and loss function used, since the Anomaly Transformer was originally built for
unsupervised data. We propose and implement the following changes in order to
adapt this model to a supervised anomaly detection setting:

  1. 1.

Keep the maximize phase the same, but replace the minimize phase: instead, we
move the series association towards the ground truth.

  2. 2.

Replace the first term of the loss with the popular MSE loss between the
outputted labels and the ground truth labels.

Our loss function for our maximize phase therefore becomes the following:

$\displaystyle L_{tot}(\hat{Y},P,S,\lambda;Y)={}$ $\displaystyle
MSE(\hat{Y},Y)$ $\displaystyle-\lambda\|AD(P_{detach},S;\hat{Y})\|$

The optimal model we used had a sequence length of 15, 4 layers, and a lambda
of 0.0001.

This setup resulted in an Anomaly Transformer model with 155,665 learnable
parameters which was trained for 50 epochs.

###  4.2 Metrics

During our experiments, we collect the precision, recall, and F1 scores of our
models on the validation set at the end of each epoch. Since cryptocurrency
P&D detection is an anomaly detection problem, we have chosen not to collect
the accuracy of our model, because accuracy measurements do not reflect the
strength of a model in anomaly detection scenarios. Specifically, since
anomaly detection scenarios have a large class imbalance heavily favoring
negative labels, the accuracy of any model is almost always over 99.9% even if
it just outputs 0 (the negative class). Therefore, we optimize our models for
the best possible F1 score for the reason that F1 scores generally reflect the
strength of an anomaly detection model accurately. This is the standard used
by most other anomaly detection models and helps us compare our results to
previous work more effectively.

The precision is defined as the percentage of predicted anomalies which were
correctly classified, and the recall is defined as the percentage of actual
anomalies that were correctly classified as anomalies. The F1 score is the
harmonic mean of these two values. Given that both the precision and recall
are important in the context of anomaly detection, it stands to reason that
the F1 score, which is a mix of the two values, is a good metric with which to
compare two different models at the end of the day. The following equations
are used to calculate the precision, recall, and F1 scores respectively:

$Precision=\frac{N_{TP}}{N_{TP}+N_{FP}}$ $Recall=\frac{N_{TP}}{N_{TP}+N_{FN}}$
$F1=2*\frac{Precision*Recall}{Precision+Recall}$

where the terms $N_{TP}$, $N_{FP}$, and $N_{FN}$ refer to the number of True
Positives, False Positives, and False Negatives respectively.

After training each model, we choose the metrics corresponding to the epoch in
which the highest validation F1 score was obtained instead of the metrics from
the final epoch. This ensures that our metrics reflect a model that hasn’t
overfit the training data.

##  5 Experiments

###  5.1 Dataset

The dataset used in this paper consists of manually-labelled, raw transaction
data from the Binance cryptocurrency exchange, first introduced by La Morgia
et al. (2020). The transactions of various cryptocurrencies that experienced
known occurrences of P&D were collected.

To generate the dataset, the authors first joined several cryptocurrency P&D
Telegram groups that were well-known for planning and executing on P&D
schemes. Then, over a period of two years, the researchers collected the
timestamps for official ”pump signals” which were announced in each of these
groups by group administrators. Using these timestamps and the Binance API,
the authors were able to collect every transaction for the pumped
cryptocurrency for up to 1 week preceding and succeeding the pump, depending
on what was available to access. In this fashion, 343 P&D occurrences’ worth
of data was collected.

After collecting this raw data from the Binance API, the authors further
preprocessed the data by aggregating transactions into 5-second, 15-second,
and 25-second “chunks”, thereby forming three different aggregated datasets.
Each of these aggregated datasets, in turn, contains the following 15
features:

  1. 1.

Date, HourSin, HourCos, MinuteSin, MinuteCos: The date and hour- and minute-
based positional encoding of a given chunk.

  2. 2.

PumpIndex, Symbol: The 0-based index of the pump, numbering it out of the 343
available pumps, and the ticker symbol of the coin on which the pump took
place.

  3. 3.

StdRushOrder, AvgRushOrder: The moving standard deviation and average percent
change of the number of rush orders.

  4. 4.

StdTrades: The moving standard deviation of the number of trades, both buy and
sell.

  5. 5.

StdVolume, AvgVolume: The moving standard deviation and average percent change
in the order volume.

  6. 6.

StdPrice, AvgPrice, AvgPriceMax: The moving standard deviation, average
percent change, and average maximum percent change in the price of the asset.

###  5.2 Implementation Details

Given an input data sequence $X=X_{1},...,X_{N}$, our first step splits the
data into a separate train and validation set using an 80:20 ratio without
shuffling. Following this split, train data undergoes the following
preprocessing steps: First, data is broken into $M$ contiguous subsequences
$X=Y_{1},..,Y_{M}$, where $Y_{i}$ corresponds to the $i$th pump in the dataset
as determined by the PumpIndex feature. Separating the data out by pump at
this stage ensures that during training time, models aren’t fed information
from 2 different pumps at the same time, which may hinder their training
process. Of these pumps, all pump sequences $Y_{i}$ with fewer than 100 chunks
are discarded, since pumps that only have a few chunks do not make for
exemplary training samples. This leaves us with a training subset of $m<M$
pump sequences.

Then, we further prepare the data for each of these pumps by splitting them
into segments of size $s$ via taking a sliding window over the chunks of each
pump $Y_{i}$ and adding reflection padding to the start of size $s-1$ so that
the resulting count of windows is equal to the original count of chunks.
Together, the chunks in each window are considered to be one “segment.” In
this scheme, segments are inputs to our models. The models then predict the
probability of a pump occurring during the last chunk of the segment. At this
point, the segments from all pumps can once again be safely shuffled and
batched together without fear of information from one pump “leaking” into the
training data for another pump.

We choose to segment our data for several reasons. First, segmenting and
predicting in this way avoids the possibility for models to make predictions
based on future values – in other words, in our setup, models can only predict
whether or not a pump will occur based on currently-known information. This
ensures that models trained under this scheme have the capability to be
deployed in a real-world, realtime anomaly detection scenarios on real
exchanges. Additionally, the C-LSTM model incorporates an LSTM layer which
faces performance limitations for longer sequence lengths Vaswani et al.
(2017). The data for each pump can also span several days, making it difficult
to train models directly on a whole pump sequence due to memory constraints.
Having a fixed segment length as opposed to the variable lengths of pump data
also simplifies data loading.

Finally, segmenting our data into chunks makes it straightforward to perform
undersampling on our data, which has been shown to boost model performance in
anomaly detection scenarios by addressing the class imbalance – even in cases
where the reduction does not bring the class ratio all the way down to 50:50
Hasanin and Khoshgoftaar (2018). Undersampling also naturally speeds up
training, since it reduces the number of training samples. We therefore apply
undersampling to our train data by choosing to keep only a random subset of
proportion $u$ of all segments that do not contain any anomaly labels. At the
same time, we unconditionally include all segments that have an anomaly label
anywhere.

Validation data undergoes a similar segmenting process, with the following
exceptions: small pumps are not thrown out, and no undersampling is performed.
This avoids unfairly skewing metrics in favor of our models.

Via hyperparameter tuning, we found that a segment length value of $s=15$
resulted in the best validation performance as measured by F1 score. An
undersampling proportion of $u=0.05$ was used for all experiments except for
the C-LSTM on the 15-second chunked dataset, in which $u=0.1$ was used. For
the C-LSTM model, batch sizes of 1200, 600, and 600 were used on the 5-second,
15-second, and 25-second chunked datasets respectively. For the Anomaly
Transformer model, a batch size of 32 was used on all datasets. Likewise, the
C-LSTM model uses precision-recall thresholds of 0.5, 0.4, and 0.65 on each
the three datasets respectively, while the Anomaly Transformer model uses a
threshold of 0.48 on all datasets.

In order to keep results consistent across all models, baseline results were
also recomputed following the same train-validation split as our own models.

###  5.3 Baselines

The baseline results that we use to compare our models against are those of
the random forest model employed by La Morgia et al. (2020). For more context,
the results of the statistical model introduced by Kamps and Kleinberg (2018)
are also included in our results table, since they were used as a baseline for
the random forest model originally. The metric that we will use to compare our
models to the baseline results will be the aforementioned F1 score of each
experiment.

###  5.4 Results

Table 1: Experimental Results Model | Chunk Size | Precision | Recall | F1
---|---|---|---|---
Kamps (Init.) | 1 Hour | 15.6% | 96.7% | 26.8%
Kamps (Bal.) | 1 Hour | 38.4% | 93.5% | 54.4%
Kamps (Strict) | 1 Hour | 50.1% | 75.0% | 60.5%
RF | 5 Secs | 97.7% | 71.6% | 82.6 $\pm 0.0\%$
RF | 15 Secs | 98.0% | 81.9% | 89.2 $\pm 0.0\%$
RF | 25 Secs | 94.5% | 83.8% | 88.8 $\pm 0.0\%$
C-LSTM | 5 Secs | 91.2% | 77.5% | 83.7 $\pm 1.0\%$
C-LSTM | 15 Secs | 94.2% | 84.9% | 89.3 $\pm 0.4\%$
C-LSTM | 25 Secs | 94.2% | 85.0% |  89.3 $\pm 0.5\%$
Anom. Trans. | 5 Secs | 91.0% | 87.7% |  89.3 $\pm 0.4\%$
Anom. Trans. | 15 Secs | 93.0% | 94.2% |  93.6 $\pm 0.8\%$
Anom. Trans. | 25 Secs | 88.4% | 90.0% | 89.2 $\pm 0.3\%$

To show the variance of our models, the F1 metrics are followed by a 95%
confidence interval computed over $n=10$ runs. Variance is measured after our
efforts to maintain reproducability via setting seeds. The random forest (RF)
model’s lack of variance is due to our setting seeds in a similar manner to La
Morgia et al. (2020). Since the Kamps model is statistical in nature, it does
not have variance across runs.

Both deep learning models were able to beat all previous classical and
statistical approaches by a statistically significant margin ($p<0.025$)
except for the C-LSTM model on the 15-second chunked dataset, which matched
previous results. This demonstrates the effectiveness of deep learning in this
previously unexplored area. State-of-the-art results across all models are
bolded in our table. On average, we found that predictions using the 5-second
chunked dataset are much less accurate than those on the 15-second and
25-second chunked dataset, which suggests that predicting anomalies using
smaller chunk sizes corresponds to a harder problem in general. This
corroborates findings from previous works La Morgia et al. (2020).

A comparison of the two deep learning models that we have employed shows that
the transformer was able to beat the LSTM in all but the 25-second chunk size.
This is unsurprising for two reasons: firstly, transformers are state-of-the-
art for time-series anomaly detection problems to begin with, and secondly, a
basic transformer design without the use of the Anomaly Transformer novelties
already outperforms the random forest model results – albeit just barely.

We believe that the theoretical backing for the relative performance of the
LSTM and Anomaly Transformer lies in the fact that for 5-second and 15-second
chunk sizes, longer sequences are required to capture the same amount of
information on average when compared to the larger 25-second chunks.
Consequently, this implies a drop in the amount of temporal information
present in the input for smaller chunk sizes, given a fixed segment length
$s=15$ as was used in this paper. We hypothesize that this difference is
responsible for the LSTM’s faster drop in efficacy at smaller chunk sizes.
However, more experiments must be done to reveal our models’ sensitivity to
the aggregation chunk size of the dataset before confirming this.

##  6 Conclusion and Future Work

This paper studies the application of deep learning models to the crypto fraud
detection problem space. We propose two separate models that can each reach
state-of-the-art performance on the data available: the C-LSTM, and the
Anomaly Transformer. Our results consequently show that both LSTMs and
Transformers have the ability to outperform both classical ML models and
statistical models on this dataset with relatively little effort. Future work
includes fine-tuning these models to better-account for the volatility
generally found in crypto, and exploring the potential for these models to
detect pumps ahead of time as opposed to when they begin. Furthermore, the
dataset provided to the community by La Morgia et al. (2020), while incredibly
useful, has been preprocessed to be optimized in some ways for use by their
random forest model; for instance, an LSTM could make use of the actual price
of an asset (as opposed to the average percent change in price) in ways that a
random forest model cannot. Therefore, the release of the raw dataset, if
possible, would push the capabilities of deep learning models in this domain
even further.

## References

  * Brown et al. (2018) Andy Brown, Aaron Tuor, Brian Hutchinson, and Nicole Nichols. 2018.  Recurrent neural network attention mechanisms for interpretable system log anomaly detection.  In _Proceedings of the First Workshop on Machine Learning for Computing Systems_ , pages 1–8.
  * Coffeezilla (2021) Coffeezilla. 2021.  I joined a pump and dump scheme so you don’t have to - youtube.
  * Cumming et al. (2019) Douglas J. Cumming, Sofia Johan, and Anshum Pant. 2019.  Regulation of the crypto-economy: Managing risks, challenges, and regulatory uncertainty.  _Journal of Risk and Financial Management_ , 12(3).
  * Hamrick et al. (2021) J.T. Hamrick, Farhang Rouhi, Arghya Mukherjee, Amir Feder, Neil Gandal, Tyler Moore, and Marie Vasek. 2021.  An examination of the cryptocurrency pump-and-dump ecosystem.  _Information Processing & Management_, 58(4):102506.
  * Hasanin and Khoshgoftaar (2018) Tawfiq Hasanin and Taghi Khoshgoftaar. 2018.  The effects of random undersampling with simulated class imbalance for big data.  In _2018 IEEE International Conference on Information Reuse and Integration (IRI)_ , pages 70–79.
  * Kamps and Kleinberg (2018) J. Kamps and B. Kleinberg. 2018.  To the moon: defining and detecting cryptocurrency pump-and-dumps.  _Crime Sci_.
  * Keogh et al. (2021) Eamonn J. Keogh, Taposh Roy, Naik U, and Agrawal A. 2021.  Multi-dataset time-series anomaly detection competition, competition of international conference on knowledge discovery & data mining.
  * Khatri (2021) Yogita Khatri. 2021.  Crypto exchanges saw over $14 trillion in trading volume this year.
  * Kim and Cho (2018) Tae-Young Kim and Sung-Bae Cho. 2018.  Web traffic anomaly detection using c-lstm neural networks.  _Expert Systems with Applications_ , 106:66–76.
  * Kwon et al. (2018) Donghwoon Kwon, Kathiravan Natarajan, Sang C Suh, Hyunjoo Kim, and Jinoh Kim. 2018\.  An empirical study on network anomaly detection using convolutional neural networks.  In _ICDCS_ , pages 1595–1598.
  * La Morgia et al. (2020) Massimo La Morgia, Alessandro Mei, Francesco Sassi, and Julinda Stefa. 2020.  Pump and dumps in the bitcoin era: Real time detection of cryptocurrency market manipulations.  In _2020 29th International Conference on Computer Communications and Networks (ICCCN)_ , pages 1–9.
  * Lai et al. (2022) Kwei-Herng Lai, Daochen Zha, Junjie Xu, Yue Zhao, Guanchu Wang, and Xia Hu. 2022\.  Revisiting time series outlier detection: Definitions and benchmarks.
  * Leangarun et al. (2018) Teema Leangarun, Poj Tangamchit, and Suttipong Thajchayapong. 2018.  Stock price manipulation detection using generative adversarial networks.  In _2018 IEEE Symposium Series on Computational Intelligence (SSCI)_ , pages 2104–2111.
  * Malhotra et al. (2016) Pankaj Malhotra, Anusha Ramakrishnan, Gaurangi Anand, Lovekesh Vig, Puneet Agarwal, and Gautam Shroff. 2016.  Lstm-based encoder-decoder for multi-sensor anomaly detection.  _arXiv preprint arXiv:1607.00148_.
  * Su et al. (2019) Ya Su, Youjian Zhao, Chenhao Niu, Rong Liu, Wei Sun, and Dan Pei. 2019.  Robust anomaly detection for multivariate time series through stochastic recurrent neural network.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, KDD ’19, page 2828–2837, New York, NY, USA. Association for Computing Machinery.
  * Twomey and Mann (2020) David Twomey and Andrew Mann. 2020.  Fraud and manipulation within cryptocurrency markets.  _Corruption and fraud in financial markets: malpractice, misconduct and manipulation_ , 624.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _CoRR_ , abs/1706.03762.
  * Xu et al. (2021) Jiehui Xu, Haixu Wu, Jianmin Wang, and Mingsheng Long. 2021.  Anomaly transformer: Time series anomaly detection with association discrepancy.  _CoRR_ , abs/2110.02642.
  * Yang et al. (2020) Wenjie Yang, Ruofan Wang, and Bofan Wang. 2020.  Detection of anomaly stock price based on time series deep learning models.  In _2020 Management Science Informatization and Economic Innovation Development Conference (MSIEID)_ , pages 110–114.