# Shifted convolution sums motivated by string theory

Ksenia Fedosova & Kim Klinger-Logan

###### Abstract.

In [2], it was conjectured that a particular shifted sum of even divisor sums
vanishes, and in [11], a formal argument was given for this vanishing. Shifted
convolution sums of this form appear when computing the Fourier expansion of
coefficients for the low energy scattering amplitudes in type IIB string
theory [7] and have applications to subconvexity bounds of $L$-functions. In
this article, we generalize the argument from [11] and rigorously evaluate
shifted convolution of the divisor functions of the form
$\displaystyle\sum_{\stackrel{{\scriptstyle
n_{1}+n_{2}=n}}{{n_{1},n_{2}\in\mathbb{Z}\setminus\\{0\\}}}}\sigma_{r_{1}}(n_{1})\sigma_{r_{2}}(n_{2})|n_{1}|^{P}$
and $\displaystyle\sum_{\stackrel{{\scriptstyle
n_{1}+n_{2}=n}}{{n_{1},n_{2}\in\mathbb{Z}\setminus\\{0\\}}}}\sigma_{r_{1}}(n_{1})\sigma_{r_{2}}(n_{2})|n_{1}|^{Q}\log|n_{1}|$
where $\sigma_{\nu}(n)=\sum_{d\mid n}d^{\nu}$. In doing so, we derive exact
identities for these sums and conjecture that particular sums similar to but
different from the one found in [2] will also vanish.

keywords: shifted convolution sum, divisor function, Hurwitz zeta function

##  1\. Introduction

Shifted convolution sums have a long history of being studied by number
theorists [1, 3, 8, 9, 10, 12, 13, 14, 15]. Recently, the AdS/CFT
correspondence and Yang-Mills theory gives a surprising hint towards the exact
evaluation of shifted convolution sums of divisor functions. Namely, [2]
conjectured that for any $n\neq 0$ and

$\displaystyle\varphi(n_{1},n_{2})=30-\tfrac{n^{2}}{4n_{1}^{2}}-\tfrac{n^{2}}{4n_{2}^{2}}-\tfrac{3n}{n_{1}}-\tfrac{3n}{n_{2}}+\mathopen{}\mathclose{{}\left(15-\tfrac{30n_{1}}{n}}\right)\log|n_{1}|+\mathopen{}\mathclose{{}\left(15-\tfrac{30n_{2}}{n}}\right)\log|n_{2}|,$

the following equality holds:

(1.1) $\displaystyle\sum_{\stackrel{{\scriptstyle
n_{1}+n_{2}=n}}{{n_{1},n_{2}\in\mathbb{Z}\setminus\\{0\\}}}}\varphi(n_{1},n_{2})\sigma_{2}(n_{1})\sigma_{2}(n_{2})=2\sigma_{2}(n)\mathopen{}\mathclose{{}\left(\tfrac{\zeta(2)n^{2}}{4}+15\zeta^{\prime}(-2)}\right),$

where $\zeta$ denotes the Riemann zeta function. The fact that this sum is
both infinite and and involves even divisor functions makes it particularly
challenging to work with. In [11], the authors give a formal argument
verifying (1.1).

In this paper, we examine what can be rigorously proven using the argument
presented in [11]. We apply similar methods to extend these results to more
general convolution sums and give a precise equality. More explicitly, we
rigorously evaluate for any $n\in\mathbb{Z}\setminus\\{0\\}$ and for certain
$r_{1},r_{2},P,Q\in\mathbb{C}$,

(1.2) $\sum_{\stackrel{{\scriptstyle
n_{1}+n_{2}=n}}{{n_{1},n_{2}\in\mathbb{Z}\setminus\\{0\\}}}}\sigma_{r_{1}}(n_{1})\sigma_{r_{2}}(n_{2})|n_{1}|^{P}\text{
and }\sum_{\stackrel{{\scriptstyle
n_{1}+n_{2}=n}}{{n_{1},n_{2}\in\mathbb{Z}\setminus\\{0\\}}}}\sigma_{r_{1}}(n_{1})\sigma_{r_{2}}(n_{2})|n_{1}|^{Q}\log|n_{1}|$

in Theorems 1.1 and 1.2 respectively. In doing so we identify the obstacle to
making the formal argument found in [11] rigorous. The exact results found
contain extra terms which do not appear in (1.1). If we further assume that we
may interchange the operations of taking an infinite sum and meromorphic
continuation, this generalizes the argument in [11], and we recover (1.1) as
desired. With the help of this non-rigorous argument, we obtain other
identities of a similar form, see Conjecture 1.3.

The initial motivation for the study of sums (1.2) is their appearance in
string theory. The sum (1.1) arises in the Fourier modes of the homogeneous
solution to differential equations involving Eisenstein series which yield
coefficients for to the low energy scattering amplitude in type IIB string
theory [7]. More generally, sums of a similar form arise in the maximally
supersymmetric $\mathcal{N}=4$ super-Yang-Mills theory when studying duality
properties of certain correlation functions in the $1/N$ expansion [6].
However, as previously noted, shifted convolution sums more generally are of
great interests to number theorists as well. Specifically, certain information
on shifted convolution sums could yield progress on subconvexity problems for
modular $L$-functions [1, 13].

###  1.1. Main results

Let $c,d\in\mathbb{N}$. If $\gcd(c,d)$ divides $n$, we let

(1.3) $\displaystyle B:=\\{b\in\mathbb{Z}:\exists\,a\in\mathbb{Z}\text{ such
that }ad-bc=n\\},$ (1.4) $\displaystyle b^{*}:=\arg\min_{b\in
B}\\{|b|\\}\quad\text{and}\quad a^{*}:=\frac{n+b^{*}c}{d}.$

It is convenient to introduce

(1.5) $\displaystyle u_{c,d}$ $\displaystyle:=\frac{b^{*}\gcd(c,d)}{d}.$

Moreover, we denote $\displaystyle\delta_{2\mid
P}=\begin{cases}1,\quad&\text{for }P\in 2\mathbb{Z},\\\
0,\quad&\text{otherwise.}\end{cases}$

######  Theorem 1.1.

Let $n\in\mathbb{Z}\setminus\\{0\\}$, $r_{2}\in\mathbb{R}$,
$r_{1}\in\mathbb{C}$ with $\text{Re}(r_{1})<-1$, and $P\in\mathbb{Z}$ be such
that $P\ll_{r_{2}}0$ and let $u_{c,d}$ be as in (1.5). Then

$\displaystyle\sum_{\stackrel{{\scriptstyle
n_{1}+n_{2}=n}}{{n_{1},n_{2}\in\mathbb{Z}\setminus\\{0\\}}}}$
$\displaystyle\sigma_{r_{1}}(n_{1})\sigma_{r_{2}}(n_{2})n_{2}^{P}=-n^{P}\sigma_{r_{2}}(n)\zeta(-r_{1})$
(1.6) $\displaystyle+(-1)^{P}2\delta_{2\mid
P}\zeta(-P)\zeta(-r_{2}-P)\sum_{d\mid
n}d^{r_{1}+P}\prod_{p|d}\mathopen{}\mathclose{{}\left(1+(1-p^{P})(p^{r_{2}}+\ldots+p^{v_{p}(d)r_{2}})}\right)$
$\displaystyle+(-1)^{P}\sum_{\stackrel{{\scriptstyle
d\in\mathbb{N}}}{{d\not\hskip 2.5pt\mid
n}}}d^{r_{1}+r_{2}+2P}\sum_{\stackrel{{\scriptstyle 0<c^{\prime}\leq
d}}{{\gcd(c^{\prime},d)|n}}}\frac{\zeta(-r_{2}-P,\frac{c^{\prime}}{d})}{\gcd(c^{\prime},d)^{P}}\cdot\sum_{m\in\mathbb{Z}}(m+u_{c^{\prime},d})^{P},$

where the product $\prod_{p|d}$ is taken over all prime divisors $p$ of $d$
while the sum $\sum_{d|n}$ is taken over all divisors $d$ of $n$, and
$v_{p}(d)$ denotes the valuation of $d$ at $p$. The first two terms in the
right hand side of (1.6) admit meromorphic continuations111Note that
$2\delta_{2|P}$ may be continued as a meromorphic function in many ways.
Specifically, we choose $e^{\pi iP}+1$ for $P\in\mathbb{C}$. to
$P\in\mathbb{C}$ and $r_{1}\in\mathbb{C}$. The restriction of the second term
to $r_{2}\in 2\mathbb{Z}$ and $r_{2}+P\in\mathbb{N}_{0}$ equals

$\begin{cases}-\zeta(r_{2})\sigma_{r_{1}}(n),\quad&r_{2}+P=0,\\\
0,\quad&r_{2}+P\in\mathbb{N}.\end{cases}$

Moreover, under the same condition, an inner sum in the third term admits a
meromorphic continuation to $P\in\mathbb{C}$ and vanishes:
$\displaystyle\sum_{\stackrel{{\scriptstyle 0<c^{\prime}\leq
d}}{{\gcd(c^{\prime},d)|n}}}\frac{\zeta(-r_{2}-P,\frac{c^{\prime}}{d})}{\gcd(c^{\prime},d)^{P}}\cdot\sum_{m\in\mathbb{Z}}(m+u_{c^{\prime},d})^{P}=0.$

It is very tempting to change the order of taking a meromorphic continuation
and an infinite sum and thus deduce from Theorem 1.1 that for
$n\in\mathbb{Z}\setminus\\{0\\}$ and $r_{1}\in\mathbb{R}-\\{-1\\}$,

(1.7) $\displaystyle\sum_{\stackrel{{\scriptstyle
n_{1}+n_{2}=n}}{{n_{1},n_{2}\in\mathbb{Z}\setminus\\{0\\}}}}\sigma_{r_{1}}(n_{1})\sigma_{r_{2}}(n_{2})n_{2}^{P}$

appears to be equal to

(1.8)
$\displaystyle-n^{P}\sigma_{r_{2}}(n)\zeta(-r_{1})+\begin{cases}-\zeta(r_{2})\sigma_{r_{1}}(n),&\quad
r_{2}+P=0,\\\ 0,&\quad r_{2}+P\in\mathbb{N}.\end{cases}$

However, we cannot justify the vanishing of the last term in (1.6) and thus
cannot infer that (1.7) is equal to (1.8).

The following statement is a result analogous to Theorem 1.1 but where each
summand is multiplied by $\log|n_{2}|$.

######  Theorem 1.2.

Let $n\in\mathbb{Z}\setminus\\{0\\}$, $\text{Re}(r_{1})<-1$, $Q\in\mathbb{Z}$
be such that $Q\ll_{r_{2}}0$, and ${\text{Re}(r_{2})<-2-Q}$ and let $u_{c,d}$
be as in (1.5). Then

$\displaystyle\sum_{\stackrel{{\scriptstyle
n_{1}+n_{2}=n}}{{n_{1},n_{2}\in\mathbb{Z}\setminus\\{0\\}}}}\sigma_{r_{1}}(n_{1})\sigma_{r_{2}}(n_{2})n_{2}^{Q}\log|n_{2}|=-\zeta(-r_{1})\sigma_{r_{2}}(n)n^{Q}\log|n|$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ +2(-1)^{Q}\sum_{d\mid n}\delta_{2\mid
Q}\,d^{\,Q+r_{1}}\zeta(-Q)\mathopen{}\mathclose{{}\left(\frac{\partial}{\partial
t_{1}}+\frac{\partial}{\partial
t_{2}}}\right)\mathopen{}\mathclose{{}\left.\mathopen{}\mathclose{{}\left(\sum_{c\in\mathbb{N}}c^{t_{1}}\gcd(c,d)^{t_{2}}}\right)}\right|_{\begin{subarray}{c}t_{1}=r_{2}+Q\\\
t_{2}=-Q\end{subarray}}$ (1.9) $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \
+2(-1)^{Q}\sum_{d\mid n}\delta_{2\mid
Q}\,d^{\,Q+r_{1}}(\log(d)\zeta(-Q)-\zeta^{\prime}(-Q))\sum_{c\in\mathbb{N}}\frac{c^{r_{2}+Q}}{\gcd(c,d)^{Q}}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ +(-1)^{Q}\sum_{\stackrel{{\scriptstyle
d\in\mathbb{N}}}{{d\not\hskip 2.5pt\mid
n}}}d^{r_{1}}\mathopen{}\mathclose{{}\left(\frac{cd}{\gcd(c,d)}}\right)^{Q}\log\mathopen{}\mathclose{{}\left|\frac{cd}{\gcd(c,d)}}\right|\sum_{m\in\mathbb{Z}}(m+u_{c,d})^{Q}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ +(-1)^{Q}\sum_{\stackrel{{\scriptstyle
d\in\mathbb{N}}}{{d\not\hskip 2.5pt\mid
n}}}\frac{d^{r_{1}+r_{2}+2Q}}{(\gcd(c,d))^{Q}}\sum_{\stackrel{{\scriptstyle
0<c^{\prime}\leq d}}{{\gcd(c^{\prime},d)\mid
n}}}\zeta(-r_{2}-Q,\tfrac{c^{\prime}}{d})\sum_{m\in\mathbb{Z}}\frac{\log|m+u_{c^{\prime},d}|}{(m+u_{c^{\prime},d})^{-Q}}.$

The first three terms admit a meromorphic continuation222As before, note that
$2\delta_{2|Q}$ may be continued as a meromorphic function in many ways.
Specifically, we choose $e^{\pi iQ}+1$ for $Q\in\mathbb{C}$. in $Q$ and
$r_{1}$ to $\mathbb{C}$. For certain values of $r_{1},r_{2},Q$ the first three
terms significantly simplify; specifically,

$\displaystyle\begin{cases}-\zeta(-r_{1})\sigma_{r_{2}}(n)n^{Q}\log|n|,&\quad
Q\in\mathbb{N}$ and $r_{2}+Q\in\mathbb{N},\\\
\sigma_{r_{1}}(n)\zeta^{\prime}(-r_{2}),&\quad Q=0\text{ and
}r_{1},r_{2}\in\mathbb{N},\\\
(\frac{\log|n|}{2}-\log(2\pi))\sigma_{0}(n),&\quad Q=0$ and
$r_{1}=r_{2}=0.\end{cases}$

The meromorphic continuations of the inner sums of the last two terms to
$Q\in\mathbb{N}_{0}$ vanish; namely,

$\sum_{m\in\mathbb{Z}}(m+u_{c,d})^{Q}=0$

and

$\sum_{\stackrel{{\scriptstyle 0<c^{\prime}\leq d}}{{\gcd(c^{\prime}d,d)\mid
n}}}\zeta(-r_{2}-Q,\tfrac{c^{\prime}}{d})\sum_{m\in\mathbb{Z}}(m+u_{c^{\prime},d})^{Q}\log|m+u_{c^{\prime},d}|=0.$

Again, it is tempting to change the order of taking a meromorphic continuation
and an infinite sum and thus deduce from Theorem 1.2 that for $r_{1}$ and
$r_{2}$ as above and $n\in\mathbb{Z}\setminus\\{0\\}$,

(1.10) $\displaystyle\sum_{\stackrel{{\scriptstyle
n_{1}+n_{2}=n}}{{n_{1},n_{2}\in\mathbb{Z}\setminus\\{0\\}}}}\sigma_{r_{1}}(n_{1})$
$\displaystyle\sigma_{r_{2}}(n_{2})n_{2}^{Q}\log|n_{2}|$

appears to be equal to

(1.11)
$\displaystyle\begin{cases}-\zeta(-r_{1})\sigma_{r_{2}}(n)n^{Q}\log|n|,&\quad
Q\in\mathbb{N}$ and $r_{2}+Q\in\mathbb{N},\\\
\sigma_{r_{1}}(n)\zeta^{\prime}(-r_{2}),&\quad Q=0\text{ and
}r_{1},r_{2}\in\mathbb{N},\\\
(\frac{\log|n|}{2}-\log(2\pi))\sigma_{0}(n),&\quad Q=0$ and $r_{1}=r_{2}=0.\\\
\end{cases}$

However, we cannot justify the vanishing of the last two terms of (1.2) and so
we cannot deduce this identity.

At the same time, if we assume (1.8) and (1.11), we would recover (1.1).
Moreover, we obtain other conjectural identities which are supported by
numerical evidence.

######  Conjecture 1.3.

For any $n\in\mathbb{Z}\setminus\\{0\\}$,

(1.12) $\sum_{\stackrel{{\scriptstyle
n_{1},n_{2}\in\mathbb{Z}\setminus\\{0\\}}}{{n_{1}+n_{2}=n}}}\sigma_{0}(n_{1})\sigma_{0}(n_{2})\Big{[}2+\tfrac{n_{2}-n_{1}}{n}\log|\tfrac{n_{1}}{n_{2}}|\Big{]}=\sigma_{0}(n)(2-\log\mathopen{}\mathclose{{}\left(4\pi^{2}|n|}\right)).$

Moreover, for $n_{1}n_{2}\neq 0$, set

$\displaystyle\varphi(n_{1},n_{2})=$
$\displaystyle\tfrac{11}{3}-20n_{1}n^{-1}+20n_{1}^{2}n^{-2}$
$\displaystyle+\mathopen{}\mathclose{{}\left(1-12n_{1}n^{-1}+30n_{1}^{2}n^{-2}-20n_{1}^{3}n^{-3}}\right)\log\mathopen{}\mathclose{{}\left|n_{1}}\right|$
$\displaystyle+\mathopen{}\mathclose{{}\left(1-12n_{2}n^{-1}+30n_{2}^{2}n^{-2}-20n_{2}^{3}n^{-3}}\right)\log\mathopen{}\mathclose{{}\left|n_{2}}\right|.$

Then we have

(1.13) $\displaystyle\sum_{\stackrel{{\scriptstyle
n_{1},n_{2}\in\mathbb{Z}\setminus\\{0\\}}}{{n_{1}+n_{2}=n}}}\sigma_{0}(n_{1})$
$\displaystyle\sigma_{0}(n_{2})\varphi(n_{1},n_{2})=\sigma_{0}(n)\mathopen{}\mathclose{{}\left(\tfrac{11}{3}-\log(4\pi^{2}|n|)}\right).$

In general, the numerical evidence does not support (1.8) or (1.11).333 That
is, take $d>0$ and let
$\varphi(n_{1},n_{2})=\sum_{j=0}^{d}\mathopen{}\mathclose{{}\left(a_{j}n_{1}^{j}+b_{j}n_{2}^{j}+c_{j}n_{1}^{j}\log|n_{1}|+d_{j}n_{2}^{j}\log|n_{2}|}\right),$
with $a_{j},b_{j},c_{j},d_{j}\in\mathbb{C}$ chosen in such a way that
$\varphi(n_{1},n-n_{1})=o(|n_{1}|^{-1})$. If the informal argument could be
justified in the current form, then the sum $\sum_{\stackrel{{\scriptstyle
n_{1},n_{2}\in\mathbb{Z}\setminus\\{0\\}}}{{n_{1}+n_{2}=n}}}\sigma_{0}(n_{1})\sigma_{0}(n_{2})\varphi(n_{1},n_{2})$
should be equal to
$\sigma_{0}(n)\mathopen{}\mathclose{{}\left[a_{0}+b_{0}+(c_{0}+d_{0})\log(\sqrt{|n|}/2\pi)+\frac{1}{2}\sum_{j=1}^{d}\mathopen{}\mathclose{{}\left(a_{j}+b_{j}+(c_{j}+d_{j})\log|n|}\right)n^{j}}\right].$
However, while the numerical evidence supports the claim for $d\leq 4$, for
$d\geq 5$ the equality doesn’t hold, as calculations with the help of Pari/GP
indicate. Similarly, an informal argument cannot be justified for $r_{1}\neq
0,r_{2}\neq 0$. As we will prove in an upcoming article with Danylo Radchenko,
the differences between sums similar to those in Conjecture 1.3 and their
informal evaluations with the help of (1.8) and (1.11) depend on Fourier
coefficients of certain Hecke eigenforms.

###  1.2. Related research

Sums involving divisor functions have received a considerable attention from
number theorists due to their connection to the subconvexity of $L$-functions
and other problems, see [3, 8, 9, 10, 12, 14, 15, 16]. However, much of what
has been classically studied relates to odd divisor functions, that is,
$\sigma_{\nu}(\cdot)$ for odd $\nu$. Furthermore, the mentioned sources
usually demand that $n_{1}$ and $n_{2}$, while satisfying $n_{1}+n_{2}=n$,
belong to a finite set. For example, it is typical to examine truncated
shifted convolution sums where $0<n_{1}<n$ and $0<n_{2}<n$.

There are, however, results which do not demand that $n_{1}$ and $n_{2}$
belong to a finite set. In [4], Diamantis studies

(1.14) $\sum_{\stackrel{{\scriptstyle
n_{1}\in\mathbb{N}}}{{n_{1}>h}}}\sigma_{\alpha}(n_{1})\sigma_{\beta}(h-n_{1})n_{1}^{-s}$

for $h\in\mathbb{Z}\text{ and }\alpha,\beta,s\in\mathbb{C}$ was considered.
There, the author characterizes the ratios of non-critical values of
$L$-functions, corresponding to normalized weight $k$ cuspidal eigenforms, in
terms of (1.14). Additionally, Diamantis analytically continues (1.14) in $s$
(although not to the whole $\mathbb{C}$) by expressing it as a sum of
Estermann $L$-functions (which in turn are linear combinations of Hurwitz zeta
functions). We note that Theorem 1.1 also expresses a convolution sum in terms
of Hurwitz zeta functions; however, it does not appear to be of the form as in
[4].

###  1.3. Acknowledgments

The authors would like to thank Michael Green for originally suggesting this
problem. The authors would also like to thank Danylo Radchenko and Stephen D.
Miller for their insightful conversations. K. K-L. acknowledges support from
NSF DMS-2001909.

##  2\. Preliminaries

In this section, we include supporting lemmas needed for the main theorems.
Specifically, Lemma 2.1 is a known result regarding Hurwitz zeta functions. We
also extend upon some results proven in [11] (Lemma 2.2 and Lemma 2.4444 Lemma
2.4 is given in [11] for a special case but is extended here without much
change in the argument for this more general set up. ).

For $s\in\mathbb{Z}$ with $s$ sufficiently large and $a\in\mathbb{C}$ with
$\text{Re}(a)\in(0,1)$,

(2.1) $\displaystyle\sum_{m\in\mathbb{Z}}(m+a)^{-s}$
$\displaystyle=\zeta(s,a)+e^{\pi is}\zeta(s,1-a).$

We note that the right hand side of (2.1) is defined for all $a\in\mathbb{C}$
and is a meromorphic function in $s\in\mathbb{C}$. Similarly, for
$s\in\mathbb{Z}$ with $\text{Re}(s)$ sufficiently large and $a\in\mathbb{C}$
with $\text{Re}(a)\in(0,1)$,

(2.2) $\displaystyle\sum_{m\in\mathbb{Z}}(m+a)^{-s}\log|m+a|$
$\displaystyle=\partial_{s}\zeta(s,a)+e^{\pi is}\partial_{s}\zeta(s,1-a).$

For the following lemma, we write
$\displaystyle\sum_{m\in\mathbb{Z}}(m+a)^{-s}$ and
$\displaystyle\sum_{m\in\mathbb{Z}}(m+a)^{-s}\log|m+a|$ in the sense of
meromorphic continuation as in (2.1) and (2.2).

######  Lemma 2.1.

For $s\in-\mathbb{N}_{0}$ and any $a\in\mathbb{C}$,

(2.3) $\displaystyle\zeta(s,1-a)=(-1)^{s+1}\zeta(s,a)$

and for any $s\in\mathbb{Z}$ and $a\in\mathbb{C}\setminus\mathbb{Z}$,

(2.4)
$\displaystyle\sum_{m\in\mathbb{Z}}(m+a)^{-s}=(-1)^{s}\sum_{m\in\mathbb{Z}}(m-a)^{-s}$

and

(2.5)
$\displaystyle\sum_{m\in\mathbb{Z}}(m+a)^{-s}\log|m+a|=(-1)^{s}\sum_{m\in\mathbb{Z}}(m-a)^{-s}\log|m-a|.$

Moreover, for $a\in\mathbb{C}\setminus\mathbb{Z}$ and $s\in-\mathbb{N}_{0}$,

(2.6) $\displaystyle\sum_{m\in\mathbb{Z}}(m+a)^{-s}=0.$

###### Proof.

Without loss of generality assume $\text{Re}(a)\in(0,1)$. We note that values
of $\zeta(s,a)$ for $s\in-\mathbb{N}$ are related to the Bernoulli polynomials
[5, (25.11.14)]:

$\zeta(s,a)=\frac{B_{-s+1}(a)}{s-1},$

and the Bernoulli polynomials satisfy [5, (24.4.3)]:

$B_{-s+1}(a)=(-1)^{-s+1}B_{-s+1}(1-a).$

This proves the first statement of the lemma. The equality (2.4) follows from
(2.1):

$\displaystyle(-1)^{-s}\zeta(s,1-a)+\zeta(s,a)=(-1)^{-s}\mathopen{}\mathclose{{}\left[\zeta(s,1-a)+(-1)^{-s}\zeta(s,1-(1-a))}\right].$

Similarly, (2.5) can be obtained similar to (2.4). In order to show (2.6), we
note that by (2.3),

$(-1)^{-s}\zeta(s,1-a)+\zeta(s,a)=((-1)^{-s-s+1}+1)\zeta(s,a)$

vanishes. ∎

The following lemma is contained in [11, Lemma 5.1]. However, for the
convenience of the reader, we added more details to the proof of the
statement.

######  Lemma 2.2.

For $\text{Re}(s)>1$, $\text{Re}(s+k)>1$ and $d\in\mathbb{N}$,

(2.7)
$\displaystyle\sum_{c\in\mathbb{N}}\frac{\log|\gcd(c,d)|}{c^{s}}=\zeta(s)\sum_{\ell|d}\Lambda(\ell)\ell^{-s},$

where $\Lambda$ is the von Mangoldt function. Moreover,

(2.8)
$\displaystyle\sum_{c\in\mathbb{N}}\frac{(\gcd(c,d))^{k}}{c^{s+k}}=\zeta(s+k)\prod_{p|d}\mathopen{}\mathclose{{}\left(1+(1-p^{-k})(p^{-s}+\ldots+p^{-v_{p}(d)s})}\right),$

where the product is taken over all possible prime divisors $p$ and $v_{p}(d)$
denotes the valuation of $d$ at prime $p$. The sum in (2.8) admits a
meromorphic continuation in both $s$ and $k$, for which the following holds:

(2.9)
$\displaystyle\zeta(s+k)\prod_{p|d}\mathopen{}\mathclose{{}\left(1+(1-p^{-k})(p^{-s}+\ldots+p^{-v_{p}(d)s})}\right)=\begin{cases}0,\quad&s+k\in-2\mathbb{N},\\\
-d^{k}/2,\quad&s+k=0.\end{cases}$

###### Proof.

The first two identities follow from [11, Lemma 5.1]. We note that for any
$d\in\mathbb{N}$ and $\text{Re}(s)>1$,

(2.10)
$\displaystyle\mathopen{}\mathclose{{}\left|\frac{\log|\gcd(c,d)|}{c^{s}}}\right|\leq\mathopen{}\mathclose{{}\left|\frac{\log|c|}{c^{s}}}\right|=o(|c|^{-1+\varepsilon}),\quad
c\to\infty$

for an arbitrary $\varepsilon>0$, and

$|(\gcd(c,d))^{k}|\leq\begin{cases}1,\quad&\text{Re}(k)<0,\\\
|c^{k}|,\quad&\text{Re}(k)\geq 0,\end{cases}$

thus

(2.11)
$\displaystyle\mathopen{}\mathclose{{}\left|\frac{(\gcd(c,d))^{k}}{c^{s+k}}}\right|\leq\max\\{|c^{-s}|,|c^{-k-s}|\\}.$

The estimates (2.10) and (2.11) imply that for $\text{Re}(s)>1$,
$\text{Re}(s+k)>1$, the sums in (2.7) and (2.8) converge. The right sides of
both can be meromorphically continued by taking the meromorphic continuation
of the Riemann zeta function and the meromorphic continuations of
$\sum_{\ell|d}\Lambda(\ell)\ell^{-s}$ and
$\prod_{p|d}\mathopen{}\mathclose{{}\left(1+(1-p^{-k})(p^{r_{2}}+\ldots+p^{-v_{p}(d)s})}\right)$.
The formula (2.9) follows from (2.8) by a direct substitution. ∎

We additionally need the following lemma that evaluates derivatives of
meromorphic continuation of (2.8) at specific points.

######  Corollary 2.3.

For $d\in\mathbb{N}$,

(2.12) $\displaystyle\mathopen{}\mathclose{{}\left.\frac{\partial}{\partial
t_{1}}\mathopen{}\mathclose{{}\left(\sum_{c\in\mathbb{N}}c^{t_{1}}\gcd(c,d)^{t_{2}}}\right)}\right|_{\begin{subarray}{c}t_{1}=r_{1}\\\
t_{2}=0\end{subarray}}=-\zeta^{\prime}(-r_{1})$

and

(2.13) $\displaystyle\mathopen{}\mathclose{{}\left.\frac{\partial}{\partial
t_{2}}\mathopen{}\mathclose{{}\left(\sum_{c\in\mathbb{N}}c^{t_{1}}\gcd(c,d)^{t_{2}}}\right)}\right|_{\begin{subarray}{c}t_{1}=r_{1}\\\
t_{2}=0\end{subarray}}=\zeta(-r_{1})\sum_{\ell\mid
d}\Lambda(\ell)\ell^{r_{1}}.$

###### Proof.

We use (2.8) with $t_{1}=-s-k$ and $t_{2}=k$,

(2.14)
$\displaystyle\sum_{c\in\mathbb{N}}c^{t_{1}}\gcd(c,d)^{t_{2}}=\zeta(-t_{1})\prod_{p|d}\mathopen{}\mathclose{{}\left(1+(1-p^{-t_{2}})(p^{t_{1}+t_{2}}+\ldots+p^{v_{p}(d)(t_{1}+t_{2})})}\right).$

To establish (2.12), we note

$\frac{\partial}{\partial
t_{1}}\mathopen{}\mathclose{{}\left(1+(1-p^{-t_{2}})(p^{t_{1}+t_{2}}+\ldots+p^{v_{p}(d)(t_{1}+t_{2})})}\right)\big{|}_{t_{2}=0}=0.$

Thus, taking the derivative of both sides of (2.14), considering the
meromorphic continuation, and substituting $t_{2}=0,t_{1}=r_{1}$, we obtain

$\displaystyle\frac{\partial}{\partial t_{1}}$
$\displaystyle\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left.\sum_{c\in\mathbb{N}}c^{t_{1}}\gcd(c,d)^{t_{2}}}\right)}\right|_{\begin{subarray}{c}t_{1}=r_{1}\\\
t_{2}=0\end{subarray}}$
$\displaystyle=-\mathopen{}\mathclose{{}\left.\zeta^{\prime}(-r_{1})\prod_{p|d}\mathopen{}\mathclose{{}\left(1+(1-p^{-t_{2}})(p^{t_{1}+t_{2}}+\ldots+p^{v_{p}(d)(t_{1}+t_{2})})}\right)}\right|_{\begin{subarray}{c}t_{1}=r_{1}\\\
t_{2}=0\end{subarray}}$ $\displaystyle=-\zeta^{\prime}(-r_{1}),$

which implies (2.12). In order to show (2.13), we note that

$\mathopen{}\mathclose{{}\left.\frac{\partial}{\partial
t_{2}}(1-p^{-t_{2}})}\right|_{t_{2}=0}=p^{-t_{2}}\log p\big{|}_{t_{2}=0}=\log
p$

and

$\mathopen{}\mathclose{{}\left.1+(1-p^{-t_{2}})(p^{t_{1}+t_{2}}+\ldots+p^{v_{p}(d)(t_{1}+t_{2})})}\right|_{t_{2}=0}=1.$

We thus get

$\displaystyle\frac{\partial}{\partial t_{2}}(1+(1-p^{-t_{2}})$
$\displaystyle(p^{t_{1}+t_{2}}+\ldots+p^{v_{p}(d)(t_{1}+t_{2})}))\big{|}_{t_{2}=0}$
$\displaystyle=\mathopen{}\mathclose{{}\left.\frac{\partial}{\partial
t_{2}}(1-p^{-t_{2}})}\right|_{t_{2}=0}\mathopen{}\mathclose{{}\left.\cdot(p^{t_{1}+t_{2}}+\ldots+p^{v_{p}(d)(t_{1}+t_{2})})}\right|_{t_{2}=0}$
$\displaystyle=\log(p)\cdot(p^{t_{1}}+\ldots+p^{v_{p}(d)t_{1}}).$

Summing over all possible prime divisors of $d$, we obtain

$\displaystyle\zeta(-r_{1})\frac{\partial}{\partial t_{2}}$
$\displaystyle\mathopen{}\mathclose{{}\left.\mathopen{}\mathclose{{}\left(\prod_{p|d}(1+(1-p^{-t_{2}})(p^{t_{1}+t_{2}}+\ldots+p^{v_{p}(d)(t_{1}+t_{2})}))}\right)}\right|_{\begin{subarray}{c}t_{1}=r_{1}\\\
t_{2}=0\end{subarray}}$ $\displaystyle=$
$\displaystyle\zeta(-r_{1})\sum_{p\mid
d}\log(p)\cdot(p^{r_{1}}+\ldots+p^{v_{p}(d)r_{1}}).$

We can instead write this as a sum over all divisors of $d$ with the help of
the von Mangoldt function

$\zeta(-r_{1})\sum_{\ell\mid d}\Lambda(\ell)\ell^{r_{1}}$

yielding (2.13). ∎

The following lemma allows us to rewrite the sums over
$a,b\in\mathbb{Z}\setminus\\{0\\}$ with $ad-bc=n$ for a fixed
$n\in\mathbb{Z}\setminus\\{0\\}$ as a sum over integers for
$c,d\in\mathbb{N}$. Additionally, we denote

(2.15) $\displaystyle v_{c,d}$ $\displaystyle:=\frac{cd}{\gcd(c,d)}$

and

$\delta_{c|n}:=\begin{cases}1,\quad&\text{$c$ divides $n$,}\\\
0,\quad&\text{$c$ does not divide $n$},\end{cases}$

for $c,d\in\mathbb{N}$. We use the notation that $2$ divides $0$, thus we
write $\delta_{2|0}=1.$

######  Lemma 2.4.

Let $n\in\mathbb{Z}\setminus\\{0\\}$, $c,d\in\mathbb{N}$,
$f:\mathbb{Z}\to\mathbb{C}$ and let

$\displaystyle\mathcal{T}_{n}(c,d)$
$\displaystyle:=\sum_{\stackrel{{\scriptstyle
a,b\in\mathbb{Z}\setminus\\{0\\}}}{{ad-bc=n}}}f(bc),$

where the sum above is over all possible $a,b\in\mathbb{Z}\setminus\\{0\\}$
with $ad-bc=n$; if there exists no such $c,d$, then the sum is equal to zero.
Then $\mathcal{T}_{n}(c,d)$ can be rewritten as

(2.16)
$\mathcal{T}_{n}(c,d)=\begin{cases}\sum_{m\in\mathbb{Z}}f((m+u_{c,d})v_{c,d})-\delta_{c\mid
n}f(-n)-\delta_{d\mid n}f(0),\quad&\gcd(c,d)\mid n,\\\
0,\quad&\gcd(c,d)\not\hskip 2.5pt\mid n\end{cases}$

for $u_{c,d},v_{c,d}\in\mathbb{C}$ defined in (1.5) and (2.15), respectively.

###### Proof.

If $\gcd(c,d)\not\hskip 2.5pt\mid n$, then there do not exist
$a,b\in\mathbb{Z}$ such that ${ad-bc=n}$ holds, and $\mathcal{T}_{n}(c,d)=0$.
We let $B,b^{*}$ and $a^{*}$ be as in (1.3) and (1.4).

We note that the set $B$ is parameterized by $m\in\mathbb{Z}$, and each of its
elements takes the form

(2.17) $\displaystyle b(m)=b^{*}+\frac{m}{\gcd(c,d)}d.$

The corresponding $a(m)\in\mathbb{Z}$, defined by the property
$a(m)d-b(m)c=n$, is equal to

(2.18) $a(m)=a^{*}+\frac{m}{\gcd(c,d)}c.$

We rewrite

$\displaystyle
b(m)c=\mathopen{}\mathclose{{}\left(\frac{b^{*}\gcd(c,d)}{d}+m}\right)\frac{cd}{\gcd(c,d)}=(m+u_{c,d})v_{c,d}$

and obtain

$\mathcal{T}_{n}(c,d)=\begin{cases}\sum^{*}f((m+u_{c,d})v_{c,d}),\quad&\gcd(c,d)\mid
n,\\\ 0,\quad&\gcd(c,d)\not\hskip 2.5pt\mid n,\end{cases}$

where the sum $\sum^{*}$ is taken over all possible $m\in\mathbb{Z}$ such that
$a(m)b(m)\neq 0$. We consider the following possibilities:

  1. (i)

Let $d\mid n$, then the definition of $B$ implies $b^{*}=0$. Thus the
definition of $u_{c,d}$, (1.5), implies $u_{c,d}=0$ and

$a(m)b(m)=\frac{md}{\gcd(c,d)}\frac{n+\frac{m}{\gcd(c,d)}cd}{d}=\frac{md}{\gcd(c,d)}\mathopen{}\mathclose{{}\left(\frac{n}{d}+\frac{mc}{\gcd(c,d)}}\right).$

    1. (1)

If $c\not\hskip 2.5pt\mid n$, then $\frac{n}{d}+\frac{mc}{\gcd(c,d)}=0$ has no
integer solutions in $m$. Thus, the only integer $m$ such that $a(m)b(m)=0$ is
$m=0$. In this case

$f((m+u_{c,d})v_{c,d})|_{m=0}=f(0).$

    2. (2)

If $c\mid n$, then either $m=0$ or $m=-\frac{n\gcd(c,d)}{cd}$ in which case

$f((m+u_{c,d})v_{c,d})|_{m=-\frac{n\gcd(c,d)}{cd}}=f(-n).$

  2. (ii)

Let $d\not\hskip 2.5pt\mid n$.

    1. (1)

If $c\not\hskip 2.5pt\mid n$, then $a(m)b(m)$ cannot be equal to zero.

    2. (2)

If $c\mid n$, then $b^{*}=-\frac{n}{c}$, and $a^{*}=0$. Moreover, when
$a(m)b(m)=0$ then $a(m)=0$ and so $m=0.$

Thus, if $d\mid n$, the term $f(0)$ has to be omitted, and if $c\mid n$, the
term $f(-n)$ has to be omitted. That implies (2.16) and finishes the proof. ∎

##  3\. Proofs of main theorems

The main goals of this section is to rigorously evaluate (1.2) and prove
Theorems 1.1 and 1.2.

###  3.1. Proof of Theorem 1.1

We first need the following lemma:

######  Lemma 3.1.

Let $n\in\mathbb{Z}\setminus\\{0\\}$, $r_{2}\in\mathbb{R}$, $d\in\mathbb{N}$
and $P\in\mathbb{Z}$ with $P\ll_{r_{2}}0$, then the sum

(3.1)
$\displaystyle\sum_{c\in\mathbb{N}}c^{r_{2}}\sum_{\stackrel{{\scriptstyle
a,b\in\mathbb{Z}\setminus\\{0\\}}}{{ad-bc=n}}}(bc)^{P}$

equals

$(-1)^{P+1}n^{P}\sigma_{r_{2}}(n)+2d^{P}\delta_{2\mid
P}\zeta(-P)\zeta(-r_{2}-P)\prod_{p|d}\mathopen{}\mathclose{{}\left(1+(1-p^{P})(p^{r_{2}}+\ldots+p^{v_{p}(d)r_{2}})}\right),$

for $d\mid n$ and equals

$\displaystyle(-1)^{P+1}n^{P}\sigma_{r_{2}}(n)+d^{r_{2}+2P}\sum_{\stackrel{{\scriptstyle
0<c^{\prime}\leq
d}}{{\gcd(c^{\prime},d)|n}}}\frac{\zeta(-r_{2}-P,\frac{c^{\prime}}{d})}{\gcd(c^{\prime},d)^{P}}\sum_{m\in\mathbb{Z}}(m+u_{c^{\prime},d})^{P},$

for $d\not\hskip 2.5pt\mid n$.

###### Proof of Lemma 3.1.

In what follows, we consider two different cases: $d\mid n$ and $d\not\hskip
2.5pt\mid n$.

First assume $d\mid n$. In this case, we have $\gcd(c,d)\mid n$, and the
definition of $b^{*}$ in (1.4) implies $b^{*}=0$. Hence, by (2.15),
$u_{c,d}=0$. With the help of Lemma 2.4, we write

$\displaystyle\sum_{\stackrel{{\scriptstyle
a,b\in\mathbb{Z}\setminus\\{0\\}}}{{ad-bc=n}}}(bc)^{P}$
$\displaystyle=\sum_{m\in\mathbb{Z}\setminus\\{0\\}}(mv_{c,d})^{P}-(-n)^{P}\delta_{c\mid
n}$ (3.2)
$\displaystyle\stackrel{{\scriptstyle\eqref{def:yn}}}{{=}}2\delta_{2\mid
P}\mathopen{}\mathclose{{}\left(\frac{cd}{\gcd(c,d)}}\right)^{P}\zeta(-P)+(-1)^{P+1}\delta_{c\mid
n}n^{P}.$

Multiplying by $c^{r_{2}}$ and summing over $c\in\mathbb{N}$, we obtain

$\displaystyle\sum_{c\in\mathbb{N}}c^{r_{2}}$
$\displaystyle\mathopen{}\mathclose{{}\left(2\delta_{2\mid
P}\mathopen{}\mathclose{{}\left(\frac{cd}{\gcd(c,d)}}\right)^{P}\zeta(-P)+(-1)^{P+1}\delta_{c\mid
n}n^{P}}\right)$ (3.3) $\displaystyle=2d^{P}\delta_{2\mid
P}\zeta(-P)\sum_{c\in\mathbb{N}}\frac{c^{P+r_{2}}}{\gcd(c,d)^{P}}+(-1)^{P+1}n^{P}\sigma_{r_{2}}(n).$

Finally, Lemma 2.2 gives

$\sum_{c\in\mathbb{N}}\frac{c^{P+r_{2}}}{\gcd(c,d)^{P}}=\zeta(-r_{2}-P)\prod_{p|d}\mathopen{}\mathclose{{}\left(1+(1-p^{P})(p^{r_{2}}+\ldots+p^{v_{p}(d)r_{2}})}\right),$

and, together with (3.3), this implies the first statement of the lemma.

When $d\not\hskip 2.5pt\mid n$ and $\gcd(c,d)\mid n$,

$\displaystyle\sum_{\stackrel{{\scriptstyle
a,b\in\mathbb{Z}\setminus\\{0\\}}}{{ad-bc=n}}}(bc)^{P}$
$\displaystyle=(-1)^{P+1}\delta_{c\mid
n}n^{P}+\sum_{m\in\mathbb{Z}}((m+u_{c,d})v_{c,d})^{P}$ (3.4)
$\displaystyle\stackrel{{\scriptstyle\eqref{def:yn}}}{{=}}(-1)^{P+1}\delta_{c\mid
n}n^{P}+\mathopen{}\mathclose{{}\left(\frac{cd}{\gcd(c,d)}}\right)^{P}\sum_{m\in\mathbb{Z}}(m+u_{c,d})^{P},$

and when $d\not\hskip 2.5pt\mid n$ and $\gcd(c,d)\not\hskip 2.5pt\mid n$,

$\sum_{\stackrel{{\scriptstyle a,b\in\mathbb{Z}\setminus\\{0\\}}}{{ad-
bc=n}}}(bc)^{P}=0.$

When $d\not\hskip 2.5pt\mid n$, multiplying (3.4) by $c^{r_{2}}$ and summing
over $c$, we obtain

(3.5)
$\displaystyle\sum_{c\in\mathbb{N}}c^{r_{2}}\sum_{\stackrel{{\scriptstyle
a,b\in\mathbb{Z}\setminus\\{0\\}}}{{ad-bc=n}}}(bc)^{P}$
$\displaystyle=(-1)^{P+1}n^{P}\sigma_{r_{2}}(n)+\sum_{\stackrel{{\scriptstyle
c\in\mathbb{N}}}{{\gcd(c,d)\mid
n}}}\frac{c^{r_{2}+P}d^{P}}{\gcd(c,d)^{P}}\sum_{m\in\mathbb{Z}}(m+u_{c,d})^{P}.$

We note that for any function $f:\mathbb{N}\to\mathbb{C}$,

(3.6) $\sum_{\stackrel{{\scriptstyle c\in\mathbb{N}}}{{\gcd(c,d)\mid
n}}}f(c)=\sum_{\stackrel{{\scriptstyle 0<c^{\prime}\leq
d}}{{\gcd(c^{\prime},d)\mid n}}}\sum_{j=0}^{\infty}f(jd+c^{\prime}),$

and for any $j\in\mathbb{N}_{0}$ and $c^{\prime}\in\mathbb{Z}$,

(3.7) $\gcd(jd+c^{\prime},d)=\gcd(c^{\prime},d)\quad\text{and}\quad
u_{c^{\prime},d}=u_{jd+c^{\prime},d}.$

Rewriting the second term in (3.5) with the help of (3.6), we get

$\displaystyle\sum_{\stackrel{{\scriptstyle 0<c^{\prime}\leq
d}}{{\gcd(c^{\prime}+jd,d)|n}}}\sum_{j=0}^{\infty}$
$\displaystyle\frac{(jd+c^{\prime})^{r_{2}+P}d^{P}}{\gcd(c^{\prime}+jd,d)^{P}}\sum_{m\in\mathbb{Z}}(m+u_{c^{\prime}+jd,d})^{P}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:gcd_doesnt_change_much}}}{{=}}\sum_{\stackrel{{\scriptstyle
0<c^{\prime}\leq
d}}{{\gcd(c^{\prime},d)|n}}}\sum_{j=0}^{\infty}\frac{(jd+c^{\prime})^{r_{2}+P}d^{P}}{\gcd(c^{\prime},d)^{P}}\sum_{m\in\mathbb{Z}}(m+u_{c^{\prime},d})^{P}$
$\displaystyle=d^{r_{2}+2P}\sum_{\stackrel{{\scriptstyle 0<c^{\prime}\leq
d}}{{\gcd(c^{\prime},d)|n}}}\frac{\zeta(-r_{2}-P,\frac{c^{\prime}}{d})}{\gcd(c^{\prime},d)^{P}}\sum_{m\in\mathbb{Z}}(m+u_{c^{\prime},d})^{P},$

where $u_{c,d}$ is defined as in (1.5). This implies the second statement of
the Lemma. ∎

###### Proof of Theorem 1.1.

Assuming the factorization

$n_{1}=ad,\quad n_{2}=-bc,\quad a,b,c,d\in\mathbb{Z},$

we rewrite each summand in the left hand side of (1.6) as

$\displaystyle\sum_{d\in\mathbb{N}}d^{r_{1}}\sum_{c\in\mathbb{N}}c^{r_{2}}\sum_{\stackrel{{\scriptstyle
a,b\in\mathbb{Z}\setminus\\{0\\}}}{{ad-bc=n}}}(-bc)^{P}.$

Then we multiply the formula in Lemma 3.1 by $(-1)^{P}$ and obtain (1.6).

Now, we need to deal with the meromorphic continuation. We note that
$2\delta_{2\mid P}$ can be meromorphically continued by taking $1+e^{2\pi
iP}$. We consider the second term on the right side of (1.6). There are three
possible cases:

  1. (1)

If $r_{2}+P\in 2\mathbb{N}+1$, then $\delta_{2\mid n}$ vanishes.

  2. (2)

If $r_{2}+P\in 2\mathbb{N}$, then $\zeta(-r_{2}-P)$ vanishes.

  3. (3)

If $r_{2}+P=0$, then $r_{2}\in 2\mathbb{Z}$ implies $P\in 2\mathbb{Z}$. Using
(2.9), we obtain that the second line in the right hand side of (1.6) becomes
$(-1)^{P+1}\zeta(r_{2})\sigma_{r_{1}}(n)$. Since we assumed $P=-r_{2}$ and
$r_{2}$ is even, $(-1)^{P+1}=-1$.

It remains to show, for $d\not\hskip 2.5pt\mid n$,

(3.8) $\displaystyle\sum_{\stackrel{{\scriptstyle 0<c^{\prime}\leq
d}}{{\gcd(c^{\prime},d)|n}}}\frac{\zeta(-r_{2}-P,\frac{c^{\prime}}{d})}{\gcd(c^{\prime},d)^{P}}\sum_{m\in\mathbb{Z}}(m+u_{c^{\prime},d})^{P}=0.$

We note the element $c^{\prime}=d$ is not present in the sum (3.8) because, in
this case, $\gcd(c^{\prime},d)=d$ divides $n=ad-bc$, but this contradicts the
assumption $d\not\hskip 2.5pt\mid n$. For any other $c^{\prime}$, there is a
pair $d-c^{\prime}$ in the sum $0<c^{\prime}\leq d$ (for $c^{\prime}=d/2$, we
consider $c^{\prime}$ to be its own pair). We note that
$\gcd(d-c^{\prime},d)=\gcd(c^{\prime},d)$ and
$u_{d-c^{\prime},d}=-u_{c^{\prime},d}$ imply

$\displaystyle\frac{\zeta(-r_{2}-P,1-\frac{c^{\prime}}{d})}{\gcd(d-c^{\prime},d)^{P}}\sum_{m\in\mathbb{Z}}(m+u_{d-c^{\prime},d})^{P}$
$\displaystyle=\frac{\zeta(-r_{2}-P,1-\frac{c^{\prime}}{d})}{\gcd(c^{\prime},d)^{P}}\sum_{m\in\mathbb{Z}}(m-u_{c^{\prime},d})^{P}$
(3.9)
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:lemma2.2full_sum}}}{{=}}(-1)^{P}\frac{\zeta(-r_{2}-P,1-\frac{c^{\prime}}{d})}{\gcd(c^{\prime},d)^{P}}\sum_{m\in\mathbb{Z}}(m+u_{c^{\prime},d})^{P}.$

We can rewrite (3.8) by grouping together contributions from the elements
$c^{\prime}$ and $d-c^{\prime}$ and applying (3.9) to get

$\frac{1}{2}\sum_{\stackrel{{\scriptstyle 0<c^{\prime}\leq
d}}{{\gcd(c^{\prime},d)|n}}}\frac{\zeta(-r_{2}-P,\frac{c^{\prime}}{d})+(-1)^{P}\zeta(-r_{2}-P,1-\frac{c^{\prime}}{d})}{\gcd(c^{\prime},d)^{P}}\cdot\sum_{m\in\mathbb{Z}}(m+u_{c^{\prime},d})^{P}.$

In turn, (2.3) implies that for $r_{2}+P\in\mathbb{N}_{0}$ and $r_{2}\in
2\mathbb{Z}$, the sum above vanishes. ∎

###  3.2. Proof of Theorem 1.2

In order to prove Theorem 1.2, we need the following lemma.

######  Lemma 3.2.

Let $n\in\mathbb{N}$, $d\in\mathbb{N}$, $Q\in\mathbb{Z}$ with $Q\ll_{r_{2}}0$,
and $\text{Re}(t_{2})<-2-Q$, then the sum

(3.10)
$\displaystyle\sum_{c\in\mathbb{N}}c^{r_{2}}\sum_{\stackrel{{\scriptstyle
a,b\in\mathbb{Z}\setminus\\{0\\}}}{{ad-bc=n}}}(bc)^{Q}\log|bc|$

equals

(3.11) $\displaystyle(-1)^{Q+1}\sigma_{r_{2}}(n)n^{Q}\log|n|$ $\displaystyle\
\ \ \ \ +2\delta_{2\mid
Q}d^{Q}\zeta(-Q)\mathopen{}\mathclose{{}\left(\frac{\partial}{\partial
t_{1}}+\frac{\partial}{\partial
t_{2}}}\right)\mathopen{}\mathclose{{}\left.\mathopen{}\mathclose{{}\left(\sum_{c\in\mathbb{N}}c^{t_{1}}\gcd(c,d)^{t_{2}}}\right)}\right|_{\begin{subarray}{c}t_{1}=r_{2}+Q\\\
t_{2}=-Q\end{subarray}}$ $\displaystyle\ \ \ \ \ +2\delta_{2\mid
Q}d^{Q}(\log(d)\zeta(-Q)-\zeta^{\prime}(-Q))\sum_{c\in\mathbb{N}}\frac{c^{r_{2}+Q}}{\gcd(c,d)^{Q}},$

for $d\mid n$, and equals

$\displaystyle(-1)^{Q+1}\sigma_{r_{2}}(n)n^{Q}\log|n|$ $\displaystyle\ \ \ \ \
+\mathopen{}\mathclose{{}\left(\frac{cd}{\gcd(c,d)}}\right)^{Q}\log\mathopen{}\mathclose{{}\left|\frac{cd}{\gcd(c,d)}}\right|\sum_{m\in\mathbb{Z}}(m+u_{c,d})^{Q}$
$\displaystyle\ \ \ \ \
+\frac{d^{r_{2}+2Q}}{(\gcd(c,d))^{Q}}\sum_{\stackrel{{\scriptstyle
0<c^{\prime}\leq d}}{{\gcd(c^{\prime}+jd,d)\mid
n}}}\zeta(-r_{2}-Q,\tfrac{c^{\prime}}{d})\sum_{m\in\mathbb{Z}}\frac{\log|m+u_{c^{\prime}+jd,d}|}{(m+u_{c^{\prime}+jd,d})^{-Q}}$

for $d\not\hskip 2.5pt\mid n$.

###### Proof of Lemma 3.2.

As in the proof of Lemma 3.1, we use Lemma 2.4 and note again that when $d\mid
n$, we have $b^{*}=0$. Thus for $d\mid n$, we write

$\displaystyle\sum_{\stackrel{{\scriptstyle
a,b\in\mathbb{Z}\setminus\\{0\\}}}{{ad-bc=n}}}(bc)^{Q}\log|bc|=$
$\displaystyle\sum_{m\in\mathbb{Z}\setminus\\{0\\}}(mv_{c,d})^{Q}\log|mv_{c,d}|-(-n)^{Q}\log|n|\delta_{c\mid
n}$ $\displaystyle\stackrel{{\scriptstyle\eqref{def:yn}}}{{=}}$
$\displaystyle(-1)^{Q+1}\delta_{c\mid n}n^{Q}\log|n|$ $\displaystyle\
+2\delta_{2\mid
Q}\mathopen{}\mathclose{{}\left(\frac{cd}{\gcd(c,d)}}\right)^{Q}\mathopen{}\mathclose{{}\left(\log\mathopen{}\mathclose{{}\left(\frac{cd}{\gcd(c,d)}}\right)\zeta(-Q)-\zeta^{\prime}(-Q)}\right)$
$\displaystyle=$ $\displaystyle(-1)^{Q+1}\delta_{c\mid n}n^{Q}\log|n|$
$\displaystyle\ +2\delta_{2\mid
Q}\frac{(cd)^{Q}}{\gcd(c,d)^{Q}}\log(c)\zeta(-Q)$ $\displaystyle\
-2\delta_{2\mid Q}\frac{(cd)^{Q}}{\gcd(c,d)^{Q}}\log(\gcd(c,d))\zeta(-Q)$
$\displaystyle\ +2\delta_{2\mid
Q}\frac{(cd)^{Q}}{\gcd(c,d)^{Q}}(\log(d)\zeta(-Q)-\zeta^{\prime}(-Q)).$

We multiply the expression above by $c^{r_{2}}$ and sum over $c\in\mathbb{N}$.
The first term becomes

$\displaystyle\sum_{c\in\mathbb{N}}c^{r_{2}}(-1)^{Q+1}\delta_{c\mid
n}n^{Q}\log|n|$
$\displaystyle=(-1)^{Q+1}n^{Q}\log|n|\sum_{c\in\mathbb{N}}c^{r_{2}}\delta_{c\mid
n}$ $\displaystyle=(-1)^{Q+1}n^{Q}\log|n|\sigma_{r_{2}}(n).$

The second line becomes

$\displaystyle\sum_{c\in\mathbb{N}}c^{r_{2}}2\delta_{2\mid
Q}\frac{(cd)^{Q}}{\gcd(c,d)^{Q}}\log(c)\zeta(-Q)$
$\displaystyle=2\delta_{2\mid
Q}d^{Q}\zeta(-Q)\sum_{c\in\mathbb{N}}\frac{c^{r_{2}+Q}}{\gcd(c,d)^{Q}}\log(c)$
(3.12) $\displaystyle=2\delta_{2\mid Q}d^{Q}\zeta(-Q)\frac{\partial}{\partial
t_{1}}\mathopen{}\mathclose{{}\left.\mathopen{}\mathclose{{}\left(\sum_{c\in\mathbb{N}}c^{t_{1}}\gcd(c,d)^{t_{2}}}\right)}\right|_{\begin{subarray}{c}t_{1}=r_{2}+Q\\\
t_{2}=-Q\end{subarray}}$

since
$\displaystyle\sum_{c\in\mathbb{N}}\frac{c^{r_{2}+Q}}{\gcd(c,d)^{Q}}\log(c)$
is absolutely convergent for $\text{Re}(t_{2})<-2-Q$.

The third line becomes

$\displaystyle-\sum_{c\in\mathbb{N}}c^{r_{2}}2\delta_{2\mid Q}$
$\displaystyle\frac{(cd)^{Q}}{\gcd(c,d)^{Q}}\log(\gcd(c,d))\zeta(-Q)$ (3.13)
$\displaystyle=-2\zeta(-Q)\delta_{2\mid
Q}d^{Q}\sum_{c\in\mathbb{N}}\frac{c^{r_{2}+Q}}{\gcd(c,d)^{Q}}\log(\gcd(c,d))$
$\displaystyle=2\zeta(-Q)\delta_{2\mid Q}d^{Q}\frac{\partial}{\partial
t_{2}}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left.\sum_{c\in\mathbb{N}}c^{t_{1}}\gcd(c,d)^{t_{2}}}\right)}\right|_{\begin{subarray}{c}t_{1}=r_{2}+Q\\\
t_{2}=-Q\end{subarray}}$

since
$\displaystyle\sum_{c\in\mathbb{N}}\frac{c^{r_{2}+Q}}{\gcd(c,d)^{Q}}\log(c)$
is absolutely convergent for $\text{Re}(t_{2})<-2-Q$.

The fourth line becomes

$\displaystyle\sum_{c\in\mathbb{N}}c^{r_{2}}2\delta_{2\mid Q}$
$\displaystyle\frac{(cd)^{Q}}{\gcd(c,d)^{Q}}(\log(d)\zeta(-Q)-\zeta^{\prime}(-Q))$
(3.14) $\displaystyle=2\delta_{2\mid
Q}d^{Q}(\log(d)\zeta(-Q)-\zeta^{\prime}(-Q))\sum_{c\in\mathbb{N}}\frac{c^{r_{2}+Q}}{\gcd(c,d)^{Q}}.$

When $d\not\hskip 2.5pt\mid n$ and $\gcd(c,d)\mid n$,

$\displaystyle\sum_{\stackrel{{\scriptstyle
a,b\in\mathbb{Z}\setminus\\{0\\}}}{{ad-bc=n}}}(bc)^{Q}\log|bc|$
$\displaystyle=(-1)^{Q+1}\delta_{c\mid
n}n^{Q}\log|n|+\sum_{m\in\mathbb{Z}}((m+u_{c,d})v_{c,d})^{Q}\log|(m+u_{c,d})v_{c,d}|$
$\displaystyle\stackrel{{\scriptstyle\eqref{def:yn}}}{{=}}(-1)^{Q+1}\delta_{c\mid
n}n^{Q}\log|n|$ $\displaystyle\ \ \ \ \
+\mathopen{}\mathclose{{}\left(\frac{cd}{\gcd(c,d)}}\right)^{Q}\log\mathopen{}\mathclose{{}\left|\frac{cd}{\gcd(c,d)}}\right|\sum_{m\in\mathbb{Z}}(m+u_{c,d})^{Q}$
(3.15) $\displaystyle\ \ \ \ \
+\mathopen{}\mathclose{{}\left(\frac{cd}{\gcd(c,d)}}\right)^{Q}\sum_{m\in\mathbb{Z}}(m+u_{c,d})^{Q}\log|m+u_{c,d}|.$

Multiplying by $c^{r_{2}}$ and summing over $c$, we leave the first and the
second line as it is and rewrite the third line similar to the proof of Lemma
3.1,

$\displaystyle\sum_{c\in\mathbb{N}}c^{r_{2}}$
$\displaystyle\mathopen{}\mathclose{{}\left(\frac{cd}{\gcd(c,d)}}\right)^{Q}\sum_{m\in\mathbb{Z}}(m+u_{c,d})^{Q}\log|m+u_{c,d}|$
$\displaystyle=\sum_{j=0}^{\infty}\sum_{\stackrel{{\scriptstyle
0<c^{\prime}\leq d}}{{\gcd(c^{\prime}+jd,d)\mid
n}}}\frac{(jd+c^{\prime})^{r_{2}+Q}d^{Q}}{(\gcd(c,d))^{Q}}\sum_{m\in\mathbb{Z}}(m+u_{c^{\prime}+jd,d})^{Q}\log|m+u_{c^{\prime}+jd,d}|$
$\displaystyle=\frac{d^{r_{2}+2Q}}{(\gcd(c,d))^{Q}}\sum_{\stackrel{{\scriptstyle
0<c^{\prime}\leq d}}{{\gcd(c^{\prime},d)\mid
n}}}\zeta(-r_{2}-Q,\tfrac{c^{\prime}}{d})\sum_{m\in\mathbb{Z}}(m+u_{c^{\prime},d})^{Q}\log|m+u_{c^{\prime},d}|.$

∎

###### Proof of Theorem 1.2.

The theorem follows from Lemma 3.2 similarly to the proof of Theorem 1.1.

The first term in the right side of (1.2) admits a meromorphic continuation
trivially. For the second and the third summands in (1.2), we consider the
cases $Q\in\mathbb{N}$ and $Q=0$ separately.

For $Q\in\mathbb{N}$, $\delta_{2\mid Q}\zeta(-Q)$ vanishes. This implies that
what remains from the second and the third terms is

(3.16) $\displaystyle-(-1)^{Q}2\delta_{2\mid Q}\zeta^{\prime}(-Q)\sum_{d\mid
Q}\sum_{c\in\mathbb{N}}\frac{c^{r_{2}+Q}}{\gcd(c,d)^{Q}}.$

By Lemma 2.2, (3.16) is a multiple of $\delta_{2\mid Q}\zeta(-r_{2}-Q)$. If we
additionally assume that $Q+r_{2}\in\mathbb{N}$, then $\delta_{2\mid
Q}\zeta(-r_{2}-Q)=0$, and (3.16) vanishes.

For $Q=0$, by Lemma 2.3, (3.12) becomes

$-2\zeta(0)\zeta^{\prime}(-r_{2})=\zeta^{\prime}(-r_{2}).$

For $Q=0$, by Lemma 2.3, (3.13) becomes

$-2\zeta(0)\sum_{c\in\mathbb{N}}c^{r_{2}}\log|\gcd(c,d)|=\sum_{c\in\mathbb{N}}c^{r_{2}}\log|\gcd(c,d)|=\zeta(-r_{2})\sum_{\ell\mid
d}\Lambda(\ell)\ell^{r_{2}}.$

For $Q=0$, (3.14) becomes

$2(\log(d)\zeta(0)-\zeta^{\prime}(0))\zeta(-r_{2})=-\zeta(-r_{2})\log\mathopen{}\mathclose{{}\left(\frac{d}{2\pi}}\right).$

Combining these three terms, we obtain

$\zeta^{\prime}(-r_{2})+\zeta(-r_{2})\sum_{\ell\mid
d}\Lambda(\ell)\ell^{r_{2}}-\zeta(-r_{2})\log\mathopen{}\mathclose{{}\left(\frac{d}{2\pi}}\right).$

For $r_{2}>0$, this is equal to $\zeta^{\prime}(-r_{2})$, and for $r_{2}=0$,
this is equal to $-\log(2\pi)$.

Finally, the sum

$\sum_{m\in\mathbb{Z}}(m+u_{c,d})^{Q}$

vanishes by (2.6). The inner sum in the last term on the right side of (1.2)
vanishes by the similar argument as for (3.8) in Theorem 1.1. ∎

## References

  * [1] V. Blomer, _Shifted convolution sums and subconvexity bounds for automorphic L-functions_ , International Mathematics Research Notices 2004 (2004), no. 73, 3905–3926.
  * [2] S. M. Chester, M. B. Green, S. S. Pufu, Y. Wang, and C. Wen, _New modular invariants in $\mathcal{N}=4$ super-Yang-Mills theory_, J. High Energy Phys. (2021), no. 4, Paper No. 212, 56.
  * [3] B. Cho, D. Kim, and H. Park, _Evaluation of a certain combinatorial convolution sum in higher level cases_ , Journal of Mathematical Analysis and Applications 406 (2013), no. 1, 203–210.
  * [4] N. Diamantis, _Kernels of $L$-functions and shifted convolutions_, Proc. Amer. Math. Soc. 148 (2020), no. 12, 5059–5070. MR 4163822
  * [5] _NIST Digital Library of Mathematical Functions_ , http://dlmf.nist.gov/, Release 1.1.6 of 2022-06-30, F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
  * [6] K. Fedosova and K. Klinger-Logan, _Whittaker Fourier type solutions to differential equations arising from string theory_.
  * [7] M. B. Green, S. D. Miller, and P. Vanhove, _$SL(2,\mathbb{Z})$ -invariance and D-instanton contributions to the $D^{6}R^{4}$ interaction_, Commun. Number Theory Phys. 9 (2015), no. 2, 307–344.
  * [8] H. Hahn, _Convolution sums of some functions on divisors_ , The Rocky Mountain Journal of Mathematics (2007), 1593–1622.
  * [9] J. G. Huard, Z. M. Ou, B. K. Spearman, and K. S. Williams, _Elementary evaluation of certain convolution sums involving divisor functions_ , Number theory for the Millennium 2 (2002), 229–274.
  * [10] A. Kim, D. Kim, and L. Yan, _Convolution sums arising from divisor functions_ , Journal of the Korean Mathematical Society 50 (2013), no. 2, 331–360.
  * [11] K. Klinger-Logan, S. Miller, and D. Radchenko, _The $D^{6}R^{4}$ interaction as Poincaré series, and a related shifted convolution sum_, preprint (2022).
  * [12] M. Lemire and K. S. Williams, _Evaluation of two convolution sums involving the sum of divisors function_ , Bulletin of the Australian Mathematical Society 73 (2006), no. 1, 107–115.
  * [13] P. Michel, _The subconvexity problem for Rankin-Selberg L-functions and equidistribution of Heegner points_ , Annals of Mathematics 160 (2004), no. 1, 185–236.
  * [14] E. Ntienjem, _Evaluation of the convolution sum involving the sum of divisors function for 22, 44 and 52_ , Open Mathematics 15 (2017), no. 1, 446–458.
  * [15] H. Park, _The multinomial convolution sum of a generalized divisor function_ , Open Mathematics 20 (2022), no. 1, 419–430.
  * [16] S. Ramanujan, _On certain arithmetical functions_ , Trans. Cambridge Philos. Soc. (1916), no. 22, 159 – 184.


# BRR: Preserving Privacy of Text Data Efficiently on Device

Ricardo Silva Carvalho  Theodore Vasiloudis  Oluwaseyi Feyisetan

###### Abstract

With the use of personal devices connected to the Internet for tasks such as
searches and shopping becoming ubiquitous, ensuring the privacy of the users
of such services has become a requirement in order to build and maintain
customer trust. While text privatization methods exist, they require the
existence of a trusted party that collects user data before applying a
privatization method to preserve users’ privacy. In this work we propose an
efficient mechanism to provide metric differential privacy for text data on-
device. With our solution, sensitive data never leaves the device and service
providers only have access to privatized data to train models on and analyze.
We compare our algorithm to the state-of-the-art for text privatization,
showing similar or better utility for the same privacy guarantees, while
reducing the storage costs by orders of magnitude, enabling on-device text
privatization.

Differential Privacy, NLP, Efficiency

##  1 Introduction

As users interact with more and more edge devices through text and speech,
organizations are able to train models on the data received from users to
offer better services and drive business. However, research has demonstrated
that machine learning models trained on sensitive data can be attacked, and
sensitive information about individuals extracted from the original training
data[18].

In order to build and maintain customer trust, companies must protect the
privacy of their users, so that they will continue to use and be delighted by
the products offered, without mistrust towards the platform and the data
holder. The best way to ensure that is by sending no sensitive data to the
service provider at all, known as the zero-trust model[6]. That way sensitive
data never leaves the device, and users can be assured that even in the event
of a data breach of the service provider, their private data will not be
compromised.

Differential Privacy (DP) [6] has emerged as the most well-established
technique to provide privacy guarantees for individuals. However, DP was
originally designed to deal with continuous data, while categorical and text
data pose an additional challenge [5]. DP works by applying noise to inputs,
and for a naive approach to work for text in the zero-trust model, it would
have to ensure that a word can be replaced by _any_ other word in the
vocabulary, potentially ruining the utility of the algorithm.

To deal with this restriction, previous research has proposed applying a
privatization step in the continuous embedding space instead [8], using a
generalization of DP for metric spaces called _metric-DP_ [2]. These methods
work by retrieving the embedding vector of the word we want to privatize,
adding noise, then replacing the word with the one closest to the new noisy
vector in the embedding space. However, these methods assume a central
authority that gathers the data of all the users and applies the privatization
mechanism to generate a new privatized dataset, before training downstream NLP
models. If we try using these mechanisms on-device, the space cost would be
prohibitive. The embedding vectors plus the nearest neighbor index necessary
to retrieve the perturbed words from the noisy embedding can reach several
gigabytes.

In this paper we propose an approach that allows for zero-trust text data
privatization, ensuring that sensitive data never leave the device of the
user, improving trust to the service. The key component of our approach is to
use binary embedding vectors [20] to dramatically shrink the space and
computational costs of storing and querying the word embeddings, while
maintaining semantic meaning. Using binary word embedding vector
representations, we propose a text privatization mechanism based on the
randomized response [21], and prove that the mechanism satisfies metric-DP.

In summary, our contributions are the following:

  * •

We propose a zero-trust algorithm for on-device text privatization, using
binary embeddings and randomized response.

  * •

A proof that our mechanism satisfies metric-DP is included, more specifically
for Hamming distance.

  * •

We develop theoretical methods for comparing metric-DP mechanisms that use
different metrics, allowing consistent privacy-utility evaluation.

  * •

Finally, our empirical evaluation demonstrates the computational advantages of
the approach compared to the state-of-the-art, while maintaining better or
similar utility.

##  2 Related Work

Fernandes et al. [8] were one of the first to use metric differential privacy
on text data. They focused on the “bag of words” representation of documents
and applied the Earth Mover’s metric to obtain privatized bags, being also the
first work to perform individual word privatization in the context of metric
differential privacy. Following this context, the Madlib111We refer to this
algorithm with the name used in [3] mechanism [10] adds noise to embedding
vectors of words, working on the Euclidean space and adding Laplacian noise.
After introducing noise, the mechanism outputs the word that is closest to the
noisy vector in the embedding space. The algorithm presented in [9] is a
follow-up to [10] although it appeared later. This mechanism works in a
hierarchical embedding space, where the embedding vector of an input word is
perturbed with noise from a hyperbolic distribution. These works successfully
illustrated the privacy-utility trade-off on metric differential privacy, and
empirically showed that we can achieve reasonable privacy guarantees with the
impact on the utility of downstream text models being dependent on the
complexity of the downstream task. For example, the complex question-answering
task was more affected than binary classification.

Feyisetan et al. [9] compare the hyperbolic mechanism to Madlib [10]. However,
since the two algorithms use different metric functions, the evaluation of
privacy via only matching the $\varepsilon$ parameter of differential privacy
can be improved. In this sense, Feyisetan et al. [9] compares the privacy of
the two mechanisms, looking at the probability of not changing a word after
noise injection, i.e. the probability that the mechanism returns the exact
same word used as input. Even though this notion can be intuitively seen as a
level of indistinguishability, it cannot guarantee a fair comparison between
mechanisms. In Section 5 we propose a method that ensures a more fair
comparison, based on a privacy loss bound.

Finally, to the best of our knowledge, our work is the first to apply metric
differential privacy on text data efficiently on-device. This application
scenario allows users to share only already privatized data, keeping their
sensitive information local. In this sense, our intended use is similar to the
goals of Local Differential Privacy (LDP)[6]. Nonetheless, previous work on
LDP focused on aggregate statistics, instead of individual word privatization.
Examples are Google’s RAPPOR [7], Apple’s DP distributed system [19] and
Microsoft’s Private Collection of Telemetry Data [4]. In the context of
individual privatization of a given input, in our case word, using LDP would
mean adding extremely amounts of noise, which metric-DP relaxes by including
distance metrics within the differential privacy guarantees.

##  3 Preliminaries

Consider a user giving as input a word $w$ from a discrete fixed domain
$\mathcal{W}$. For any pair of inputs $w$ and $w^{\prime}$, we assume a
distance function $d:\mathcal{W}\times\mathcal{W}\rightarrow\mathbb{R}_{+}$,
in a given space of representation of these words. Specifically, we consider a
word embedding model $\phi:\mathcal{W}\rightarrow\mathbb{R}^{n}$ will be used
to represent words, and the distance function can be a valid metric applicable
to the embedding vectors.

Our goal is to select a word from $\mathcal{W}$, based on a given input, such
that the privacy of the user, with respect to their word choice, is preserved.
From an attacker’s perspective, the output of an algorithm working over an
input $w$ or $w^{\prime}$ will become more similar as these inputs become
closer according to the distance $d(w,w^{\prime})$. In other words, if two
words are close on the embedding space, they tend to generate similar results
with same probabilities.

With that in mind, we will work on Metric-Differential Privacy [2], a privacy
standard defined for randomized algorithms with input from a domain
$\mathcal{W}$ that are equipped with a distance metric
$d:\mathcal{W}\times\mathcal{W}\rightarrow\mathbb{R}_{+}$ satisfying the
formal axioms of a metric. In this context, algorithms satisfying metric-DP
will have privacy guarantees that depend not only on the privacy parameter
$\varepsilon$, but also on the particular distance metric $d$ being used.

######  Definition 3.1.

(Metric Differential privacy [2]) Given a distance metric
$d:\mathcal{W}\times\mathcal{W}\rightarrow\mathbb{R}_{+}$, a randomized
mechanism $\mathcal{M}:\mathcal{W}\rightarrow\mathcal{Y}$ is $\varepsilon
d$-differentially private if for any $w,w^{\prime}\in\mathcal{W}$ and all
outputs $y\in\mathcal{Y}$ we have:

$\displaystyle\Pr[\mathcal{M}(w)=y]\leq e^{\varepsilon
d(w,w^{\prime})}\Pr[\mathcal{M}(w^{\prime})=y]$ (1)

Usually, on the standard definition of differential privacy[6], the privacy
guarantees provided by different mechanisms are compared by looking at the
$\varepsilon$ value, such that mechanisms with same $\varepsilon$ give the
same privacy guarantee. For a fair evaluation on metric-DP using
$\varepsilon$, we also have to consider the distance metrics used, since it
also affects the privacy guarantees, as we can see from Definition 3.1. We
describe our theoretically motivated method to enable a fair privacy
comparison of mechanisms with different metrics in Section 5.

For Euclidean distance as metric, as discussed on Section 2, the current
state-of-the-art is the Madlib mechanism. It uses the Laplace mechanism to add
Laplacian noise to a given vector in order to obtain a private output.

Algorithm 1 \- Madlib: Word Privatization Mechanism for Metric Differential
Privacy

0: Finite domain $\mathcal{W}$, input word $w\in\mathcal{W}$ and privacy
parameter $\varepsilon$.

0: Privatized word $\hat{w}$.

1: Compute embedding $\phi_{w}=\phi(w)$

2: Perturb embedding to obtain $\hat{\phi}_{w}=\phi_{w}+N$ with noise density
$p_{N}(z)\propto\exp(-\varepsilon\left\lVert z\right\rVert)$

3: Obtain perturbed element:
$\hat{w}=argmin_{y\in\mathcal{W}}\left\lVert\phi(y)-\hat{\phi}_{w}\right\rVert$

4: Return $\hat{w}$

For a Euclidean metric
$d:\mathcal{W}\times\mathcal{W}\rightarrow\mathbb{R}_{+}$, Madlib provides
metric differential privacy.

######  Theorem 1.

For a Euclidean distance metric $d$, Algorithm 1 is $\varepsilon
d$-differentially private. Proof in [10].

Next we develop our algorithm that satisfies metric-DP, giving formal proof of
its privacy guarantees.

##  4 Mechanism

Our proposed mechanism will employ metric differential privacy to sanitize
words via their embedding vectors. The challenge with protecting the privacy
is that, for any given input word, the output of a DP algorithm as defined in
[6] can be any word in the vocabulary, i.e. the outputs of a mechanism for any
pair of inputs words are relatively similar. Metric-DP provides a
generalization of DP that allows adjusting the privacy of an input by
leveraging a given distance metric, thus being a suitable framework for
improved utility in the text scenario.

However, algorithms like Madlib rely on having access to word embedding
vectors and an approximate nearest neighbor index to map noisy vectors to
words. The space cost of these can range from hundreds of MB to several GBs.
Thus, using such representations to sanitize words on a user’s device would be
impractical. In this context, recent research [20, 17] has focused on
converting pre-trained real valued embedding vectors into binary
representations. They explicitly aim at keeping the semantic meaning while
transforming representations. These works show experimental results on machine
learning tasks with the binarization of word embeddings leading to a loss of
approximately 2% in accuracy, with the upside of reducing the embedding’s size
by 97%. Thus, in this work we propose to use binary embeddings of words,
obtained from transforming publicly available continuous representations, such
as GloVe [16] or FastText [1]. In addition, specialized nearest neighbor
indexes for binary vectors exist [15], that dramatically reduce the space and
time cost of nearest neighbor retrieval.

Randomized Response (RR) [22] is a mechanism that provably [21] obtains better
utility than the classical Laplace mechanism for binary data collection. RR is
a method that dates back to 1965, its original purpose being to motivate
survey respondents to answer questions truthfully, without the risk of
exposing any private information. For sensitive yes/no questions, survey
participants would use a spinner, similar to flipping a coin, and based on its
outcome, would either respond truthfully if, for example, the coin came up
heads, or respond yes otherwise. This mechanism provides individuals plausible
deniability, while allowing researchers to de-bias the results and obtain the
aggregate metrics they need. In our case, RR flips a given input bit of an
embedding vector with probability inversely proportional to the privacy
parameter $\varepsilon$. We describe a general version [21] of RR on Algorithm
2.

Algorithm 2 \- RR: Randomized Response

0: Bit $b\in\\{0,1\\}$ and privacy parameter $\varepsilon$.

0: Privatized bit $\hat{b}$.

1: Set $\hat{b}=b$ with probability
$\frac{e^{\varepsilon}}{1+e^{\varepsilon}}$, otherwise $\hat{b}=1-b$

2: Return $\hat{b}$

RR satisfies metric differential privacy with respect to the privacy parameter
$\varepsilon$ and Hamming distance. Since this is the first time RR is applied
to metric-DP, we include a proof of its privacy guarantees.

######  Theorem 2.

For a Hamming metric $d$, Algorithm 2 is $\varepsilon d$-differentially
private.

###### Proof.

For $RR$ to satisfy metric differential privacy with Hamming distance metric
$d$, we have to show that, for two bits $b$ and $b^{\prime}$ and response bit
$y$ we get:

$\displaystyle\frac{\Pr[RR(b)=y]}{\Pr[RR(b^{\prime})=y]}\leq e^{\varepsilon
d(b,b^{\prime})}$ (2)

For $b=b^{\prime}$ we have $\Pr[RR(b)=y]=\Pr[RR(b^{\prime})=y]$ and also
$d(b,b^{\prime})=0$, therefore Equation 2 is satisfied.

For $b\neq b^{\prime}$, from the definition of RR, we have:

$\displaystyle\frac{\Pr[RR(b)=y]}{\Pr[RR(b^{\prime})=y]}\leq\frac{\frac{e^{\varepsilon}}{1+e^{\varepsilon}}}{\frac{1}{1+e^{\varepsilon}}}=e^{\varepsilon}$

Since for $b\neq b^{\prime}$ we also get $d(b,b^{\prime})=1$, this means we
also have Equation 2 satisfied for this case.

∎

We now describe our mechanism, denoted as Binary embeddings over Randomized
Response (BRR), described in Algorithm 3. BRR uses binary embedding vectors to
represent words and applies RR to make each binary vector differentially
private.

Algorithm 3 \- BRR: Mechanism for Text as Binary Embeddings over Randomized
Response

0: Finite domain $\mathcal{W}$, input word $w\in\mathcal{W}$ and privacy
parameter $\varepsilon$.

0: Privatized word $\hat{w}$.

1: Compute binary embedding vector $\phi_{w}=\phi(w)$

2: Perturb word embedding vector using Randomized Response to obtain
$\hat{\phi}_{w}=RR(\phi_{w},\varepsilon)$

3: Obtain perturbed word:
$\hat{w}=argmin_{y\in\mathcal{W}}\left\lVert\phi(y)-\hat{\phi}_{w}\right\rVert$

4: Return $\hat{w}$

With the algorithm described, we state the privacy guarantees of BRR.

######  Theorem 3.

For a Hamming metric $d$, Algorithm 3 is $\varepsilon d$-differentially
private.

###### Proof.

For embeddings that are independent of the data, the nearest neighbor search
is just a post-processing step, thus without privacy loss. Therefore we only
have to analyze the privacy of releasing the perturbed embedding vector.

Consider $d$ as the Hamming distance and $M$ as the mechanism inside BRR that
performs the embedding perturbation, such that each word $w\in\mathcal{W}$ has
a binary embedding representation $\phi_{w}:\\{0,1\\}^{n}$. Then for a given
output vector $y:\\{0,1\\}^{n}$, with $i$’th bit as $y_{i}$ and any pair of
inputs $w,w^{\prime}\in\mathcal{W}$, with $i$’th bits as $w_{i}$ and
$w^{\prime}_{i}$, from using RR on a single bit position $i$ we have that:

$\displaystyle\frac{\Pr[M(w_{i})=y_{i}]}{\Pr[M(w^{\prime}_{i})=y_{i}]}\leq
e^{\varepsilon d(w_{i},w_{i}^{\prime})}$

For $n$ bits, multiplying probabilities for each of them, we then have:

$\displaystyle\frac{\Pr[M(w)=y]}{\Pr[M(w^{\prime})=y]}$ $\displaystyle=$
$\displaystyle\prod\limits_{i=1}^{n}\frac{\Pr[M(w_{i})=y_{i}]}{\Pr[M(w^{\prime}_{i})=y_{i}]}$
$\displaystyle\leq
e^{\varepsilon\sum\limits_{i=1}^{n}d(w_{i},w_{i}^{\prime})}=e^{\varepsilon
d(w,w^{\prime})}$

where the last step comes from the definition of the Hamming distance.

∎

BRR is similar to the Madlib Mechanism, differing in the use of binary
embeddings instead of real-valued, and Randomized Response instead of the
Laplace mechanism. Since RR is proven to be better than Laplace mechanism for
binary data [21], if our semantic loss for transforming embeddings into binary
is smaller than the gains of using RR instead of Laplace, then BRR is a
promising approach compared to Madlib.

More importantly, our mechanism is suitable to privatize data on-device due to
the use of binary embeddings and specialized nearest neighbor index. On one
side, we have the memory/storage size reduction of using binary embedding
vectors, and additionally we gain computational efficiency in the perturbation
with RR, implemented as sampling from a binomial distribution together with a
XOR operation, which can be done efficiently at the hardware level. With these
optimizations, the user would only need to share already privatized data,
keeping ownership of the sensitive data. This is a highly desirable feature,
as it allows the use of valuable user data for NLP tasks, but sensitive
information never leaves the user’s device.

##  5 Comparing Metric-DP Mechanisms

One issue with a fair evaluation of BRR against Madlib is that they use
different distance functions. To solve this we propose fixing a _privacy
ratio_ that allows us to obtain similar privacy guarantees, even when two
mechanisms use different distance metrics. Due to space limitations we provide
a brief description here and refer the interested reader to Appendix A for a
detailed motivation of the method.

To compare mechanisms with different distance metrics, we consider an estimate
of _privacy loss bound_ $\varepsilon\cdot\mathcal{P}_{d}$, where
$\mathcal{P}_{d}$ is defined as an aggregate distance measurement based on the
distances between all possible pairs of words. In this work, we use either
$\mathcal{P}_{d}^{avg}$ where we average the distances of all pairs, or
$\mathcal{P}_{d}^{max}$ where we use the maximum distance between any two
words, for each mechanism. To fairly compare the privacy of two mechanisms, we
equalize their bounds via a privacy ratio.

######  Definition 5.1 (Method to Fix Privacy).

Given two randomized mechanisms $\mathcal{M}_{A}$ and $\mathcal{M}_{B}$ both
taking inputs from $\mathcal{X}$ to output space $\mathcal{Y}$, satisfying
respectively $\varepsilon_{A}d_{A}$-DP and $\varepsilon_{B}d_{B}$-DP, we
denote the privacy ratio as
$\mathcal{R}_{d_{A},d_{B}}=\mathcal{P}_{d_{A}}/\mathcal{P}_{d_{B}}$. In order
to ensure a similar privacy loss on both mechanisms, for any given
$\varepsilon_{A}$ defined for $\mathcal{M}_{A}$ we need to set:

$\displaystyle\varepsilon_{B}=\mathcal{R}_{d_{A},d_{B}}\cdot\varepsilon_{A}$
(3)

In practice, to compare two mechanisms $\mathcal{M}_{A}$ and
$\mathcal{M}_{B}$, first we calculate the aggregate distances, e.g. max or
average distances between all words, $\mathcal{P}_{d_{A}}$ and
$\mathcal{P}_{d_{B}}$. Then we obtain the privacy ratio
$\mathcal{R}_{d_{A},d_{B}}=\mathcal{P}_{d_{A}}/\mathcal{P}_{d_{B}}$. Then for
experiments we can simply choose for $\mathcal{M}_{A}$ any value of
$\varepsilon_{A}$ and then for $\mathcal{M}_{B}$ we set
$\varepsilon_{B}=\mathcal{R}_{d_{A},d_{B}}\cdot\varepsilon_{A}$. This implies
that
$\varepsilon_{B}\cdot\mathcal{P}_{d_{B}}=\varepsilon_{A}\cdot\mathcal{P}_{d_{A}}$,
fixing the estimate of privacy loss for the two mechanisms considered.

By calculating the privacy ratio $\mathcal{R}_{d_{A},d_{B}}$ we can get values
$\varepsilon_{A}$ and $\varepsilon_{B}$ to obtain similar privacy guarantees
of two mechanisms $\mathcal{M}_{A}$ and $\mathcal{M}_{B}$. We note that
previous work [9] compared the privacy of two mechanisms looking at the
probability that a mechanism returns the exact same word used as input.
However, such notion does not always give a fair comparison between
mechanisms, as that can vary considerably on embedding spaces. In contrast,
our method is theoretically robust, with well defined bounds.

##  6 Experiments

In this section we compare BRR to previous work in terms of privacy, utility
and efficiency. Since in DP we usually have a privacy-utility trade-off when
applying mechanisms, we will fix the privacy of our mechanisms in order to
compare their utility, using the methodology described in Section 5. Our
experiments will use the IMDB dataset [13], with training data being 50% of
the original training dataset, validation data being the other 50% of the
original training data, and testing data being 50% of the original testing
dataset. The experiments were performed on an AWS EC2 p3.2xlarge instance.
More specific setup is described on the next paragraphs.

Privacy: In our experiments we vary $\varepsilon$ for Madlib and set the
$\varepsilon$ for BRR using the privacy ratio. To have a more conservative
approach, we use an average distance aggregation $\mathcal{P}_{d}^{avg}$ to
fix privacy loss of BRR and Madlib. We note though that using
$\mathcal{P}_{d}^{max}$ would give significantly better results for BRR in
comparison to Madlib.

Utility: To evaluate the utility of the metric-DP mechanisms, we build ML
models for sentiment analysis on training data privatized by each mechanism
and compare the accuracy of the trained models on a separate testing dataset.
For Madlib we use Euclidean distance on a fixed embedding space from GloVe
[16] with 300 dimensions. BRR starts from the same embedding, then transforms
it into a binary representation with 256 dimensions as described in [20]. The
sentiment classification models follow the FastText classifier [12]. The
accuracy on the test dataset is shown in Figure 1(a).

(a) Utility Evaluation

(b) MIA Evaluation

Figure 1: Comparison of mechanisms with 95% confidence interval over 10
independent trials for various $\varepsilon$. Baseline is built with models
trained on original sensitive data. $\varepsilon$ is first set for Madlib and
transformed for BRR using the method from Section 5.

As seen in Figure 1(a), in terms of utility, we obtain similar results for
Madlib’s $\varepsilon$ under 5, and improved results for BRR for larger
$\varepsilon$, where each setting is averaged over 5 independent trials, with
the shaded are showing the 95% confidence interval.

Defense against attacks: We also include the results of a Membership Inference
Attack (MIA) [18], which tries to infer the presence of observations used to
train a given model based only on black-box access, that is, the attacker is
only able to query the deployed model and does not have access to specific
weights. Lower score of the attack is better, representing more privacy
preservation.

In summary, we have a target model that we can only query, e.g. through a
public API, which we plan to attack to determine membership of particular
users in its training set. To attack the target model we train a shadow model,
based on disjoint data we have available. This model tries to emulate the
behavior of the target model. For example, we could try attacking a next-word
prediction model trained on private data, by training a similar model using
data from a user’s public Twitter feed. Our dataset will then have two labels.
The first called member we use to train the shadow model. The second, called
non-member we set aside to train an attack model that will tell us if an
example was part of the training data of the target model.

For this step, we use 50% of the original IMDB testing data to train a shadow
model, another 50% to validate it. Models created for utility evaluation are
the target for the attack. The attack model is an MLP with two layers having
64 hidden nodes each, with ReLU activations. Results are on Figure 1(b). We
can see that for the various privacy levels represented by $\varepsilon$
tested, we obtain practical privacy protection, represented by the drop in AUC
of the attack model. More specifically, we see that as we increase
$\varepsilon$, which decreases the formal privacy guarantees of DP, we also
obtain also less empirical privacy, represented by larger AUC. In this case,
for very large $\varepsilon>12$ we see a bigger impact on MIA for BRR.
However, even though Madlib has smaller impact seen on MIA, that is not a
formal privacy guarantee. Therefore, such large values of $\varepsilon$ are
not recommended for both mechanisms on the dataset analyzed. Finally, we note
that for $\varepsilon\leq 12$, where both mechanisms have AUC of approximately
$0.50$ for MIA, we see BRR with similar or better utility than Madlib.

Efficiency: To evaluate how efficient the mechanisms are on different aspects,
we consider the size of embedding vectors and index for approximate nearest
neighbors, the wall time of privatization per word and total wall time per
mechanism. For nearest neighbors search, we use FAISS [11], a library that
deals with both real and binary vectors.

For our relatively small vocabulary, the nearest neighbors index built for BRR
achieved a compression rate of 97.9% (4MB vs. 200MB), while the vocabulary
file, along with embeddings, was also 98.5% smaller (6MB vs. 300MB) compared
to the ones used by Madlib.

Figure 2: Wall-time comparison between BRR and Madlib on IMDB dataset.

For a fair time comparison, we looked for optimal ways of improving the
computation of nearest neighbors during privatization of both BRR and Madlib.
This step is the most time consuming of both methods and Madlib uses real-
valued data with the Euclidean distance, while BRR uses binary data and the
Hamming distance.

In our experiments, BRR was on average 68% faster to privatize a word compared
to Madlib, as we can see on Figure 2. Using binary embedding vectors
significantly improved the running time of our solution compared to using
real-valued vectors, due to the possibility of using more efficient algorithms
and hardware-level optimizations through binary operations. We used the FAISS
library222https://github.com/facebookresearch/faiss that implements algorithms
[15] tailored for binary data, for both exact and approximate nearest
neighbors search. We note that FAISS has additional features in the library
that we did not apply but could be further explored, such as product
quantization, which is a technique for lossy compression of high-dimensional
vectors, and PCA. Similarly, for Madlib we use approximate nearest neighbors,
more specifically the Annoy library333https://github.com/spotify/annoy. This
speeds the retrieval at the cost of losing the guarantee to find the exact
nearest neighbor.

##  7 Conclusion

We presented a mechanism for efficient text privatization on-device with
formal differential privacy guarantees. We demonstrated that our new mechanism
enables performing privatization on-device through the use of binary
embeddings, providing zero-trust privacy for customers, while maintaining
better or competitive utility than the state-of-the-art. As future work, we
plan to implement improvements in the nearest neighbors search step, exploring
smaller dimensionality of embedding vectors and including privatization of
word context vectors for improved utility. We are currently exploring other DP
mechanisms like using the exponential mechanism[14] that allows for the use of
any metric function in the privatization process. Finally, a related line of
work is how to achieve on-device privacy for tasks like Automatic Speech
Recognition.

## References

  * Bojanowski et al. [2017] Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov.  Enriching word vectors with subword information.  _Transactions of the Association for Computational Linguistics_ , 5:135–146, Dec 2017.  ISSN 2307-387X.  doi: 10.1162/tacl˙a˙00051.  URL http://dx.doi.org/10.1162/tacl_a_00051.
  * Chatzikokolakis et al. [2013] Konstantinos Chatzikokolakis, Miguel E Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi.  Broadening the scope of differential privacy using metrics.  In _International Symposium on Privacy Enhancing Technologies Symposium_ , pages 82–102. Springer, 2013.
  * Diethe [2020] Thomas Diethe.  Preserving privacy in analyses of textual data, 2020.  URL https://www.amazon.science/blog/preserving-privacy-in-analyses-of-textual-data.
  * Ding et al. [2017] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin.  Collecting telemetry data privately.  In _Advances in Neural Information Processing Systems_ , pages 3571–3580, 2017.
  * Dwork and Roth [2014] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  _Theoretical Computer Science_ , 9(3-4):211–407, 2014.
  * Dwork et al. [2006] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , pages 265–284. Springer, 2006.
  * Fanti et al. [2016] Giulia Fanti, Vasyl Pihur, and Úlfar Erlingsson.  Building a rappor with the unknown: Privacy-preserving learning of associations and data dictionaries.  _Proceedings on Privacy Enhancing Technologies_ , 2016(3):41–61, 2016.
  * Fernandes et al. [2018] Natasha Fernandes, Mark Dras, and Annabelle McIver.  Author obfuscation using generalised differential privacy.  _CoRR_ , abs/1805.08866, 2018.  URL http://arxiv.org/abs/1805.08866.
  * Feyisetan et al. [2019] Oluwaseyi Feyisetan, Tom Diethe, and Thomas Drake.  Leveraging hierarchical representations for preserving privacy and utility in text.  In _2019 IEEE International Conference on Data Mining (ICDM)_ , pages 210–219. IEEE, 2019.
  * Feyisetan et al. [2020] Oluwaseyi Feyisetan, Borja Balle, Thomas Drake, and Tom Diethe.  Privacy- and utility-preserving textual analysis via calibrated multivariate perturbations.  In _Proceedings of the 13th International Conference on Web Search and Data Mining_ , WSDM ’20, page 178–186, New York, NY, USA, 2020. Association for Computing Machinery.  ISBN 9781450368223.  doi: 10.1145/3336191.3371856.  URL https://doi.org/10.1145/3336191.3371856.
  * Johnson et al. [2017] Jeff Johnson, Matthijs Douze, and Hervé Jégou.  Billion-scale similarity search with gpus.  _arXiv preprint arXiv:1702.08734_ , 2017.
  * Joulin et al. [2017] Armand Joulin, Edouard Grave, Piotr Bojanowski, and Tomas Mikolov.  Bag of tricks for efficient text classification.  _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers_ , 2017.  doi: 10.18653/v1/e17-2068.  URL http://dx.doi.org/10.18653/V1/E17-2068.
  * Maas et al. [2011] Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts.  Learning word vectors for sentiment analysis.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , pages 142–150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics.  URL http://www.aclweb.org/anthology/P11-1015.
  * McSherry and Talwar [2007] Frank McSherry and Kunal Talwar.  Mechanism design via differential privacy.  In _FOCS_ , volume 7, pages 94–103, 2007.
  * Norouzi et al. [2012] Mohammad Norouzi, Ali Punjani, and David J Fleet.  Fast search in hamming space with multi-index hashing.  In _2012 IEEE conference on computer vision and pattern recognition_ , pages 3108–3115. IEEE, 2012.
  * Pennington et al. [2014] Jeffrey Pennington, Richard Socher, and Christopher D Manning.  Glove: Global vectors for word representation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 1532–1543, 2014.
  * Shen et al. [2019] Dinghan Shen, Pengyu Cheng, Dhanasekar Sundararaman, Xinyuan Zhang, Qian Yang, Meng Tang, Asli Celikyilmaz, and Lawrence Carin.  Learning compressed sentence representations for on-device text processing.  _arXiv preprint arXiv:1906.08340_ , 2019.
  * Shokri et al. [2017] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov.  Membership inference attacks against machine learning models.  In _2017 IEEE Symposium on Security and Privacy (SP)_ , pages 3–18. IEEE, 2017.
  * Team [2017] Apple Differential Privacy Team.  Learning with privacy at scale.  _Available athttps://machinelearning.apple.com/2017/12/06/learning-with-privacy-at-scale.html_, 2017\.
  * Tissier et al. [2019] Julien Tissier, Christophe Gravier, and Amaury Habrard.  Near-lossless binarization of word embeddings.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 7104–7111, 2019.
  * Wang et al. [2016] Yue Wang, Xintao Wu, and Donghui Hu.  Using randomized response for differential privacy preserving data collection.  In _EDBT/ICDT Workshops_ , volume 1558, pages 0090–6778, 2016.
  * Warner [1965] Stanley L Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  _Journal of the American Statistical Association_ , 60(309):63–69, 1965.

##  Appendix A Motivation for Privacy Ratio

In the standard definition of differential privacy [6], the privacy guarantees
provided by different mechanisms are compared by looking only at the
$\varepsilon$ value: mechanisms with same $\varepsilon$ provide the same
privacy guarantees. However, referring to Equation 1 we see that for metric-DP
the privacy bound is directly impacted not only by $\varepsilon$ but also by
the distance metric. As a result, comparing mechanisms with different metrics
is a non-trivial task. In this context we propose calculating, for each
mechanism, a privacy loss bound for all $x,x^{\prime}\in\mathcal{X}$.

To compare privacy among mechanisms first we look at the privacy loss, which
is a general function defined for randomized mechanisms, not specific to any
differential privacy definition.

######  Definition A.1.

Let $\mathcal{M}:\mathcal{X}\rightarrow\mathcal{Y}$ be a randomized mechanism
with density function $p_{\mathcal{M}(x)}(y)$, then for any
$x,x^{\prime}\in\mathcal{X}$ and all outputs $y\in\mathcal{Y}$ the privacy
loss function is defined as:

$\displaystyle\mathcal{L}_{\mathcal{M},x,x^{\prime}}(y)=\ln\bigg{(}\frac{p_{\mathcal{M}(x)}(y)}{p_{\mathcal{M}(x^{\prime})}(y)}\bigg{)}$
(4)

Every differentially private mechanism will have by definition an upper bound
for $\mathcal{L}_{\mathcal{M},x,x^{\prime}}(y)$, and more specifically,
metric-DP, as we show next.

######  Corollary A.1.

Given a randomized mechanism $\mathcal{M}:\mathcal{X}\rightarrow\mathcal{Y}$
that is $\varepsilon d$-differentially private for a given distance function
$d:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}_{+}$, we have that for
any $x,x^{\prime}\in\mathcal{X}$ and all outputs $y\in\mathcal{Y}$:

$\displaystyle\mathcal{L}_{\mathcal{M},x,x^{\prime}}(y)<\varepsilon\cdot
d(x,x^{\prime})$ (5)

From Equation 5 above we can see that the privacy loss bound of any pair
$x,x^{\prime}$ depends on their distance and $\varepsilon$. Therefore, for a
given metric $d$ we propose calculating $d(x,x^{\prime})$ for every possible
pair $x,x^{\prime}\in\mathcal{X}$ in order to obtain the overall bound on the
privacy loss. With these distances, we can define a privacy measurement
$\mathcal{P}_{d}$ for the maximum or average, as we now formalize.

######  Definition A.2.

For a given distance function
$d:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}_{+}$ and finite space
$\mathcal{X}$, we define the privacy measurement $\mathcal{P}_{d}^{max}$ and
$\mathcal{P}_{d}^{avg}$ as:

$\displaystyle\mathcal{P}_{d}^{max}=\max_{\forall
x,x^{\prime}\in\mathcal{X}}d(x,x^{\prime})$ (6)
$\displaystyle\mathcal{P}_{d}^{avg}=\sum_{\forall
x,x^{\prime}\in\mathcal{X}}d(x,x^{\prime})/|\mathcal{X}|^{2}$ (7)

For example, in the context of words as input, $\mathcal{P}_{d}$ can be
calculated using a given distance metric on the embedding space for every word
in the vocabulary. Comparing the two privacy measurements above, we note that
$\varepsilon\cdot\mathcal{P}_{d}^{max}$ has the advantage of giving an overall
bound on the privacy loss. This can be derived from Equations 5 and 6, such
that for any $x,x^{\prime}\in\mathcal{X}$ and all outputs $y\in\mathcal{Y}$,
the privacy loss is bounded by:

$\displaystyle\mathcal{L}_{\mathcal{M},x,x^{\prime}}(y)<\varepsilon\cdot
d(x,x^{\prime})<\varepsilon\cdot\max_{\forall
x,x^{\prime}\in\mathcal{X}}d(x,x^{\prime})=\varepsilon\cdot\mathcal{P}_{d}^{max}$
(8)

On the other hand, $\mathcal{P}_{d}^{avg}$ gives average distance bounds over
a given space $\mathcal{X}$, which is a more conservative approach and may be
of interest to avoid spaces with outliers that individually would largely
affect the privacy loss upper bound.

Given the above, $\varepsilon\cdot\mathcal{P}_{d}^{avg}$ or
$\varepsilon\cdot\mathcal{P}_{d}^{max}$ can be used as estimates of privacy
loss bounds, which allows us to fairly compare mechanisms using different
distance metrics, as defined in Section 5 by equalizing their bounds through a
privacy ratio.