# An Algebraic Interpretation of the Super Catalan Numbers

Kevin Limanta
School of Mathematics and Statistics, UNSW Sydney
<EMAIL_ADDRESS>
###### Abstract

We extend the notion of polynomial integration over an arbitrary circle $C$ in
the Euclidean geometry over general fields $\mathbb{F}$ of characteristic zero
as a normalized $\mathbb{F}$-linear functional on
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ that takes polynomials that
evaluate to zero on $C$ to zero and is $SO(2,\mathbb{F})$-invariant. This
allows us to not only build a purely algebraic integration theory in an
elementary way, but also give the super Catalan numbers

$\displaystyle S(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}$

an algebraic interpretation in terms of values of this algebraic integral over
some circle applied to the monomials $\alpha_{1}^{2m}\alpha_{2}^{2n}$.

##  1 Introduction

This is the second of our series of papers building an integration theory of
polynomials over unit circles over a general field $\mathbb{F}$. The first
paper [9] deals with the case $\mathbb{F}$ is finite of odd characteristic, in
which the family of integers $S(m,n)$ called the super Catalan numbers and
their closely related family of rational numbers $\Omega(m,n)$ called the
circular super Catalan numbers play a prominent role. They are defined as

$\displaystyle
S(m,n):=\frac{(2m)!(2n)!}{m!n!(m+n)!},\quad\Omega(m,n):=\frac{S(m,n)}{4^{m+n}}$

and are indexed by two elements in $\mathbb{N}$ which for us includes $0$.

The super Catalan numbers were first introduced by Catalan [3] in 1874 and the
first modern study of these numbers was initiated by Gessel [7] in 1992. They
generalized the Catalan numbers $c_{n}$ since $S(1,n)=2c_{n}$. The integrality
of $S(m,n)$ can be observed from the relation
$4S\left(m,n\right)=S\left(m+1,n\right)+S\left(m,n+1\right)$ which yields the
Pascal-like property $\Omega(m,n)=\Omega(m+1,n)+\Omega(m,n+1)$.

No combinatorial interpretation of $S(m,n)$ is known for general $m$ and $n$
to date, in contrast to over $200$ interpretations of the Catalan numbers
[12]. However, for $m=2$, there is some interpretations in terms of cubic
trees by Pippenger [10] and blossom trees by Schaeffer [11], and when $m=2,3$,
as pairs of Dyck paths with restricted heights by Gessel and Xin [8]. When
$n=m+s$ for $0\leq s\leq 3$, Chen and Wang showed that there is an
interpretation in terms of restricted lattice paths [4]. There is also some
weighted interpretation of $S\left(m,n\right)$ as a certain value of
Krawtchouk polynomials by the work of Georgiadis, Munemasa, and Tanaka [6] and
another in terms of positive and negative $2$-Motzkin paths by Allen and
Gheorghiciuc [1].

The aim of this paper is twofold. The first one is to build, in a rather
elementary way, a polynomial integration theory over circles in the Euclidean
geometry over general fields of characteristic zero without recourse to the
usual Riemann integral and limiting processes. We shall see that this allows
us to give the super Catalan numbers a purely algebraic interpretation, which
is our second objective.

Here and throughout, $\mathbb{F}$ is a general field of characteristic zero
with multiplicative identity $1_{\mathbb{F}}$ or sometimes just $1$ if the
context is clear. We denote by $\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$
the algebra of polynomials in $\alpha_{1}$ and $\alpha_{2}$ over $\mathbb{F}$
with multiplicative identity $\mathbf{1}$. Our algebraic integral over a
circle $C$ is a linear functional $\phi$ on
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$, called a circular integral
functional with respect to $C$, which satisfies three conditions:
$\phi(\mathbf{1})=1_{\mathbb{F}}$ (Normalization), $\phi(\pi)=0$ whenever
$\pi$ evaluates to the zero function on $C$ (Locality), and $\phi$ is
rotationally-invariant (Invariance).

When $\mathbb{F}=\mathbb{R}$, there is a well-known formula for the integral
of polynomials on the unit sphere $S^{n-1}$ (see [2] or [5]).

###### Theorem 1.1

Let $n\geq 2$ and $S^{n-1}$ denote the $\left(n-1\right)$-dimensional unit
sphere in $\mathbb{R}^{n}$. If $\mu$ is the usual rotationally invariant
measure on $S^{n-1}$, then by writing $b_{i}=\frac{1}{2}\left(d_{i}+1\right)$,

$\displaystyle\int_{S^{n-1}}x_{1}^{d_{1}}x_{2}^{d_{2}}\ldots
x_{n}^{d_{n}}\,d\mu=\begin{cases}\dfrac{2}{\Gamma\left(b_{1}+b_{2}+\cdots+b_{n}\right)}{\displaystyle\prod\limits_{i=1}^{n}}\Gamma\left(b_{i}\right)&\text{if
each }d_{i}\text{ is even}\\\ 0&\text{otherwise.}\end{cases}$

We may see from Theorem 1.1 above, when $n=2$, $d_{1}=2m$, and $d_{2}=2n$, we
obtain

$\displaystyle\frac{2\Gamma\left(b_{1}\right)\Gamma\left(b_{2}\right)}{\Gamma\left(b_{1}+b_{2}\right)}=\frac{2\Gamma\left(m+\frac{1}{2}\right)\Gamma\left(n+\frac{1}{2}\right)}{\Gamma\left(m+n+1\right)}=2\pi\frac{(2m)!(2n)!}{4^{m+n}m!n!(m+n)!}=2\pi\Omega(m,n)$

so if the integral is normalized, we get just the circular super Catalan
numbers.

In [9], we showed that the polynomial integration theory over finite field of
odd characteristics is analogous to the $\mathbb{F}=\mathbb{R}$ case, which we
summarize below.

###### Theorem 1.2

Let $p>2$ be a prime and $q=p^{r}$ for some $r\in\mathbb{N}$. In the Euclidean
geometry over $\mathbb{F}_{q}$ with multiplicative identity $1_{q}$, the unit
circle is $S^{1}=\left\\{\left[x_{1},x_{2}\right]\in\mathbb{F}_{q}^{2}\colon
x^{2}+y^{2}=1_{q}\right\\}$. Let $k$ and $l$ be any natural numbers for which
$0\leq k+l<q-1$. Then the functional $\psi_{b,q}$ on
$\mathbb{F}_{q}\left[\alpha_{1},\alpha_{2}\right]$ given by

$\psi_{b,q}\left(\alpha_{1}^{k}\alpha_{2}^{l}\right)=-\left(\frac{-1}{p}\right)^{r}\sum_{\left[x,y\right]\in
S^{1}}x^{k}y^{l}=\begin{cases}\Omega\left(m,n\right)\mathrm{mod}\,p&\mbox{if
}k=2m\mbox{ and }l=2n\\\ 0&\mbox{otherwise}\end{cases}$

is the unique circular integral functional with respect to $S^{1}$. Here
$\left(\frac{-1}{p}\right)$ is the usual Legendre symbol.

Now we present our main result. For $a\in\mathbb{Q}$, $a1_{\mathbb{F}}$ is the
embedding of $a$ in $\mathbb{F}$. The unit circle $S^{1}$ in this setting will
be defined in the next section.

###### Theorem 1.3

For any $k,l\in\mathbb{N}$, the linear functional $\psi$ on
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ defined by

$\psi\left(\alpha_{1}^{k}\alpha_{2}^{l}\right)=\left\\{\begin{array}[]{cl}\Omega\left(m,n\right)1_{\mathbb{F}}&\text{if
}k=2m\text{ and }l=2n\text{,}\\\ 0&\text{otherwise}\end{array}\right.$ (1)

is the unique circular integral functional with respect to $S^{1}$.

##  2 Circular Integral Functional

Denote by $\mathbb{A}=\mathbb{A}(\mathbb{F})$ the two-dimensional affine plane
$\left\\{\left[x,y\right]\ \colon\ x,y\in\mathbb{F}\right\\}$, with the
objects $\left[x,y\right]$ called points. There is then the space
$\mathbb{F}^{\mathbb{A}}$ consisting of functions from $\mathbb{A}$ to
$\mathbb{F}$ which is an $\mathbb{F}$-algebra under pointwise addition and
multiplication, and the evaluation map
$\varepsilon\colon\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]\rightarrow\mathbb{F}^{\mathbb{A}}$
which is an algebra homomorphism. Clearly we may regard
$\mathbb{F}\left[\alpha_{1}\right]$ as a subalgebra of
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$. Recall that any non-zero
polynomial in $\mathbb{F}\left[\alpha_{1}\right]$ of degree $d$ has at most
$d$ roots.

The group $GL(2,\mathbb{F})$ of invertible $2\times 2$ matrices with entries
in $\mathbb{F}$ left acts on $\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ as
follows: if $\pi=\pi\left(\alpha_{1},\alpha_{2}\right)$ then

$h\cdot\pi=\begin{pmatrix}h_{11}&h_{12}\\\
h_{21}&h_{22}\end{pmatrix}\cdot\pi:=\pi\left(h_{11}\alpha_{1}+h_{21}\alpha_{2},h_{12}\alpha_{1}+h_{22}\alpha_{2}\right).$
(2)

Additionally, $GL(2,\mathbb{F})$ right acts on $\mathbb{A}$ and left acts on
$\mathbb{F}^{\mathbb{A}}$ as follows:

$\displaystyle\left[x_{1},x_{2}\right]\cdot h$
$\displaystyle:=\left[h_{11}x_{1}+h_{21}x_{2},h_{12}x_{1}+h_{22}x_{2}\right]$
$\displaystyle(h\cdot f)(x_{1},x_{2})$
$\displaystyle:=f\left(\left[x_{1},x_{2}\right]\cdot
h\right)=f(h_{11}x_{1}+h_{21}x_{2},h_{12}x_{1}+h_{22}x_{2}).$

The group $SO(2,\mathbb{F})$ of matrices $h$ that satisfy $h^{-1}=h^{T}$ of
determinant $1_{\mathbb{F}}$ is then a subgroup of $GL(2,\mathbb{F})$ and is
called the rotation group. The action of $SO(2,\mathbb{F})$ on
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ is induced as the restriction
of the action of $GL(2,\mathbb{F})$ on
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$. This action respects
evaluation: for any $h\in SO(2,\mathbb{F})$ and
$\pi\in\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$,

$\varepsilon\left(h\cdot\pi\right)=h\cdot\varepsilon\left(\pi\right).$ (3)

In a similar manner, we also get an action of $SO(2,\mathbb{F})$ on
$\mathbb{A}$ and $\mathbb{F}^{\mathbb{A}}$.

We define a symmetric bilinear form on $\mathbb{A}$, given by
$\left[x_{1},y_{1}\right]\cdot\left[x_{2},y_{2}\right]:=x_{1}x_{2}+y_{1}y_{2}$.
The associated quadratic form
$\left[x,y\right]\cdot\left[x,y\right]=x^{2}+y^{2}$ then gives rise to the
(Euclidean) unit circle

$S^{1}=S^{1}\left(\mathbb{F}\right):=\left\\{\left[x,y\right]\in\mathbb{A}\colon
x^{2}+y^{2}=1_{\mathbb{F}}\right\\}.$

###### Lemma 2.1

Each point on $S^{1}$ except $[-1,0]$ can be written as
$\left[\frac{1-u^{2}}{1+u^{2}},\frac{2u}{1+u^{2}}\right]$ for some
$u\in\mathbb{F}$ such that $1+u^{2}\neq 0$. Consequently, $S^{1}$ is an
infinite set.

Proof. The identity
$\left(\frac{1-u^{2}}{1+u^{2}}\right)^{2}+\left(\frac{2u}{1+u^{2}}\right)^{2}=1_{\mathbb{F}}$
holds for all $u\in\mathbb{F}$ for which $u^{2}\neq-1$. The line $y=ux+u$
through the points $\left[-1,0\right]$ and $\left[0,u\right]$ intersects
$S^{1}$ in exactly two points, $\left[-1,0\right]$ and
$\left[\frac{1-u^{2}}{1+u^{2}},\frac{2u}{1+u^{2}}\right]$. Hence every point
on $S^{1}$ except $\left[-1,0\right]$ corresponds to exactly one
$u\in\mathbb{F}$ for which $u^{2}\neq-1$. Since there are infinitely many
$u\in\mathbb{F}$ for which $u^{2}\neq-1$, $S^{1}$ is an infinite set.

###### Corollary 2.2

The rotation group $SO(2,\mathbb{F})$ admits a parametrization

$\displaystyle
SO(2,\mathbb{F})=\left\\{h_{u}=\frac{1}{1+u^{2}}\begin{pmatrix}1-u^{2}&-2u\\\
2u&1-u^{2}\end{pmatrix}\colon\
u\in\mathbb{F},u^{2}\neq-1\right\\}\cup\left\\{-I\right\\}.$

We now introduce the central object of this paper: a linear functional on
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ that generalizes normalized
integration over the Euclidean unit circle over $\mathbb{R}$. We say that a
linear functional
$\phi\colon\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]\rightarrow\mathbb{F}$
is a circular integral functional on
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ with respect to $S^{1}$
precisely when it satisfies the following three conditions:

(Normalization)

For the multiplicative identity $\mathbf{1}$ of
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$, we have
$\phi\left(\mathbf{1}\right)=1_{\mathbb{F}}$.

(Locality)

If $\pi\in\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ such that
$\varepsilon(\pi)$ is the zero function on $S^{1}$, then $\phi(\pi)=0$.

(Invariance)

The functional $\phi$ is $SO(2,\mathbb{F})$-invariant:
$\phi(h\cdot\pi)=\phi(\pi)$ for any
$\pi\in\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ and $h\in
SO(2,\mathbb{F})$.

##  3 Existence and Uniqueness

Our strategy to prove Theorem 1.3 is divided into two main steps. First, we
show that $\psi$ satisfies the Normalization, Locality, and Invariance
conditions. Next, we demonstrate that if such a circular integral functional
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ with respect to $S^{1}$ exists,
it is uniquely determined.

It is easy to see that the Normalization condition holds. The next two lemmas
are needed to prove the Locality of $\psi$.

###### Lemma 3.1

Both
$S^{1}_{x_{1}}=\left\\{x_{1}\in\mathbb{F}\,\colon\,\left[x_{1},x_{2}\right]\in
S^{1}\right\\}$ and
$S^{1}_{x_{2}}=\left\\{x_{2}\in\mathbb{F}\,\colon\,\left[x_{1},x_{2}\right]\in
S^{1}\right\\}$ have infinitely many elements.

Proof. For any $\left[x_{1},x_{2}\right]\in S^{1}$, we have that
$\left[x_{2},x_{1}\right]\in S^{1}$, so $S^{1}_{x_{1}}=S^{1}_{x_{2}}$. If
$S^{1}_{x_{1}}=S^{1}_{x_{2}}$ is finite, then so is $S^{1}_{x_{1}}\times
S^{1}_{x_{2}}$ and consequently $S^{1}$. This contradicts the fact that
$S^{1}$ is infinite from Lemma 2.1.

The crucial property of polynomials in
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ that evaluate to the zero
function on $S^{1}$ is that they must lie in
$\left\langle\alpha_{1}^{2}+\alpha_{2}^{2}-1\right\rangle$, the ideal
generated by $\alpha_{1}^{2}+\alpha_{2}^{2}-1$. We offer an elementary proof
below by utilising the multivariate polynomial division which requires a
choice of monomial ordering. This has a flavour of Hilbert’s Nullstellensatz
which usually works over algebraically closed fields, although our argument
does not assume that $\mathbb{F}$ is an algebraically closed field.

###### Lemma 3.2

If $\pi\in\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ satisfies
$\varepsilon(\pi)=0$ on $S^{1}$, then
$\pi\in\left\langle\alpha_{1}^{2}+\alpha_{2}^{2}-1\right\rangle$.

Proof. Fix a monomial ordering $\preccurlyeq$ such that
$\alpha_{1}^{k_{1}}\alpha_{2}^{l_{1}}\preccurlyeq\alpha_{1}^{k_{2}}\alpha_{2}^{l_{2}}$
if either $k_{1}<k_{2}$ or $k_{1}=k_{2}$ and $l_{1}<l_{2}$. With respect to
this ordering, any $\pi\in\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ can be
written as
$\pi=\left(\alpha_{1}^{2}+\alpha_{2}^{2}-1\right)\pi_{0}+\alpha_{2}\omega+\rho$
for some $\pi_{0}\in\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ and
$\omega,\rho\in\mathbb{F}\left[\alpha_{1}\right]$.

Since $\pi$ evaluates to the zero function on $S^{1}$, we have that

$0=\varepsilon(\pi)(x_{1},x_{2})=x_{2}\varepsilon(\omega)(x_{1},x_{2})+\varepsilon(\rho)(x_{1},x_{2})=x_{2}\varepsilon(\omega)(x_{1},0)+\varepsilon(\rho)(x_{1},0)$
(4)

for all $\left[x_{1},x_{2}\right]\in S^{1}$, with the last equation is due to
$\omega,\rho\in\mathbb{F}\left[\alpha_{1}\right]$. Now consider the set
$S^{1}_{\ast}=\left\\{\left[x_{1},x_{2}\right]\in S^{1}\,\colon\,x_{2}\neq
0\right\\}$ which is non-empty since $[0,1]\in S^{1}_{\ast}$. For any
$\left[x_{1},x_{2}\right]\in S^{1}_{\ast}$, the point
$\left[x_{1},-x_{2}\right]\in S^{1}_{\ast}$ is different from
$\left[x_{1},x_{2}\right]$ so (4) forces
$\varepsilon(\omega)(x_{1},0)=\varepsilon(\rho)(x_{1},0)=0$ for all
$\left[x_{1},x_{2}\right]\in S^{1}$. By Lemma 3.1, $\omega$ and $\rho$ have
infinitely many roots, so they must be the zero polynomial.

######  Theorem 3.3 (Locality of $\psi$)

The linear functional $\psi$ satisfies the Locality condition.

Proof. If $\pi\in\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ evaluates to
the zero function on $S^{1}$, then
$\pi\in\left\langle\alpha_{1}^{2}+\alpha_{2}^{2}-1\right\rangle$ from Lemma
3.2. By linearity, it suffices to show that

$\displaystyle\psi\left(\left(\alpha_{1}^{2}+\alpha_{2}^{2}-1\right)\alpha_{1}^{k}\alpha_{2}^{l}\right)=\psi\left(\alpha_{1}^{k+2}\alpha_{2}^{l}\right)+\psi\left(\alpha_{1}^{k}\alpha_{2}^{l+2}\right)-\psi\left(\alpha_{1}^{k}\alpha_{2}^{l}\right)$

vanishes. Clearly it does if either $k$ or $l$ is odd, and if $k=2m$ and
$l=2n$, the right-hand side simplifies to
$\Omega\left(m+1,n\right)+\Omega\left(m,n+1\right)-\Omega\left(m,n\right)=0$
by the Pascal-like property.

Finally, to prove the Invariance of $\psi$, we need the following three
lemmas.

###### Lemma 3.4

For any $h\in SO(2,\mathbb{F})$ and natural numbers $k,l$, each term of
$h\cdot\alpha_{1}^{k}\alpha_{2}^{l}$ has degree $k+l$.

Proof. By using (2),
$h\cdot\alpha_{1}^{k}\alpha_{2}^{l}=\left(h_{11}\alpha_{1}+h_{21}\alpha_{2}\right)^{k}\left(h_{12}\alpha_{1}+h_{22}\alpha_{2}\right)^{l}$.
Expanding this using the Binomial Theorem, we see that the degree of each term
is always $k+l$.

###### Lemma 3.5

For any natural numbers $m$ and $h\in SO(2,\mathbb{F})$, we have that
$\psi\left(h\cdot\alpha_{1}^{2m}\right)=\psi\left(\alpha_{1}^{2m}\right)$ and
$\psi\left(h\cdot\alpha_{1}^{2m-1}\alpha_{2}\right)=\psi\left(\alpha^{2m-1}\alpha_{2}\right)$.

Proof. The statement is obviously true for $h=-I$. Now for $h=h_{u}$ defined
in Corollary 2.2,

$\displaystyle\psi\left(h_{u}\cdot\alpha_{1}^{2m}\right)=\sum_{s=0}^{2m}\binom{2m}{s}\left(\frac{1-u^{2}}{1+u^{2}}\right)^{s}\left(\frac{2u}{1+u^{2}}\right)^{2m-s}\psi\left(\alpha_{1}^{s}\alpha_{2}^{2m-s}\right)$

but since the odd indices do not contribute to the sum, we just need to
consider the even indices:

$\displaystyle\psi\left(h_{u}\cdot\alpha_{1}^{2m}\right)$
$\displaystyle=\sum_{s=0}^{m}\binom{2m}{2s}\left(\frac{1-u^{2}}{1+u^{2}}\right)^{2s}\left(\frac{2u}{1+u^{2}}\right)^{2m-2s}\psi\left(\alpha_{1}^{2s}\alpha_{2}^{2m-2s}\right)$
$\displaystyle=\sum_{s=0}^{m}\binom{2m}{2s}\Omega\left(s,m-s\right)\left(\frac{1-u^{2}}{1+u^{2}}\right)^{2s}\left(\frac{2u}{1+u^{2}}\right)^{2m-2s}1_{\mathbb{F}}$
$\displaystyle=\frac{\left(2m\right)!}{4^{m}m!m!}\sum_{s=0}^{m}\binom{m}{s}\left(\frac{1-u^{2}}{1+u^{2}}\right)^{2s}\left(\frac{2u}{1+u^{2}}\right)^{2m-2s}1_{\mathbb{F}}.$
(5)

Using the Binomial Theorem, (5) simplifies to

$\psi\left(\alpha_{1}^{2m}\right)\left(\left(\frac{1-u^{2}}{1+u^{2}}\right)^{2}+\left(\frac{2u}{1+u^{2}}\right)^{2}\right)^{m}=\psi\left(\alpha_{1}^{2m}\right)1_{\mathbb{F}}.$

The proof that
$\psi\left(h_{u}\cdot\alpha_{1}^{2m-1}\alpha_{2}\right)=\psi\left(\alpha_{1}^{2m-1}\alpha_{2}\right)$
is more involved but done similarly.

###### Lemma 3.6

If $\pi\in\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ evaluates to the zero
function on $S^{1}$, then so does $h\cdot\pi$ for any $h\in SO(2,\mathbb{F})$.

Proof. For an arbitrary $h\in SO(2,\mathbb{F})$, the map
$\left[x_{1},x_{2}\right]\mapsto\left[x_{1},x_{2}\right]\cdot h$ is a
bijection on $S^{1}$. Choose any $\left[x_{1},x_{2}\right]\in S^{1}$, then
$\left[x_{1},x_{2}\right]=\left[u_{1},u_{2}\right]\cdot h^{-1}$ for some
$\left[u_{1},u_{2}\right]\in S^{1}$. Using (3),

$\displaystyle\varepsilon(h\cdot\pi)(x_{1},x_{2})=\left(h\cdot\varepsilon(\pi)\right)(x_{1},x_{2})=\varepsilon(\pi)(\left[x_{1},x_{2}\right]\cdot
h)=\varepsilon(\pi)(u_{1},u_{2})=0$

where the last equality follows from the assumption on $\pi$. Consequently
$h\cdot\pi$ evaluates to the zero function on $S^{1}$.

######  Theorem 3.7 (Invariance of $\psi$)

The linear functional $\psi$ satisfies the Invariance condition.

Proof. It is sufficient to show that
$\psi\left(h\cdot\alpha_{1}^{k}\alpha_{2}^{l}\right)=\psi\left(\alpha_{1}^{k}\alpha_{2}^{l}\right)$
for any $k,l\in\mathbb{N}$ and $h\in SO(2,\mathbb{F})$. As before, the
statement is obviously true for $h=-I$, so we will only show that
$\psi\left(h_{u}\cdot\alpha_{1}^{k}\alpha_{2}^{l}\right)=\psi\left(\alpha_{1}^{k}\alpha_{2}^{l}\right)$.
If $k+l$ is odd, then by Lemma 3.4 each term of
$h_{u}\cdot\alpha_{`}^{k}\alpha_{2}^{l}$ has an odd degree and therefore
$\psi\left(h_{u}\cdot\alpha_{1}^{k}\alpha_{2}^{l}\right)=0=\psi\left(\alpha_{1}^{k}\alpha_{2}^{l}\right)$.

The polynomial
$\pi=\alpha_{1}^{2m}\alpha_{2}^{2n}-\alpha_{1}^{2m}\left(1-\alpha_{1}^{2}\right)^{n}$
evaluates to the zero function on $S^{1}$ and therefore by Lemma 3.6,

$\displaystyle\psi\left(h_{u}\cdot\alpha_{1}^{2m}\alpha_{2}^{2n}\right)$
$\displaystyle=$
$\displaystyle\psi\left(h_{u}\cdot\alpha_{1}^{2m}\left(1-\alpha_{1}^{2}\right)^{n}\right)=\sum_{s=0}^{n}\left(-1\right)^{s}\binom{n}{s}\psi\left(h_{u}\cdot\alpha_{1}^{2m+2s}\right).$

Now by Lemma 3.5,
$\psi\left(h_{u}\cdot\alpha_{1}^{2m+2s}\right)=\psi\left(\alpha_{1}^{2m+2s}\right)$
and therefore this lets us retrace the steps:

$\displaystyle\psi\left(h_{u}\cdot\alpha_{1}^{2m}\alpha_{2}^{2n}\right)=\sum_{s=0}^{n}\left(-1\right)^{s}\binom{n}{s}\psi\left(\alpha_{1}^{2m+2s}\right)=\psi\left(\alpha_{1}^{2m}\left(1-\alpha_{1}^{2}\right)^{n}\right)=\psi\left(\alpha_{1}^{2m}\alpha_{2}^{2n}\right)$

where in the last equality we used the Locality of $\pi$ again. The case $k$
and $l$ are both odd is treated similarly. The conclusion thus follows by the
linearity of $\psi$.

Next, we proceed to show that $\psi$ is the only circular integral functional
on $\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ with respect to $S^{1}$.

######  Theorem 3.8 (Existence implies uniqueness)

If $\phi$ is any circular integral functional on
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ with respect to $S^{1}$, then
$\phi$ is uniquely determined.

Proof. By linearity, it suffices to show that
$\phi(\alpha_{1}^{k}\alpha_{2}^{l})$ is uniquely determined for any
$k,l\in\mathbb{N}$. Using the Invariance property with $h=-I$, we obtain
$\phi(\alpha_{1}^{k}\alpha_{2}^{l})=\phi(-I\cdot\alpha_{1}^{k}\alpha_{2}^{l})=(-1)^{k+l}\phi(\alpha_{1}^{k}\alpha_{2}^{l})$
so $\phi(\alpha_{1}^{k}\alpha_{2}^{l})=0$ whenever $k+l$ is odd.

For $m\geq 1$, another application of the Invariance property with $h=h_{u}$
from Corollary 2.2 gives

$\displaystyle\phi\left(\alpha_{1}^{2m}\right)=\phi\left(h_{u}\cdot\alpha_{1}^{2m}\right)=\frac{1}{\left(1+u^{2}\right)^{2m}}\sum_{s=0}^{2m}\binom{2m}{s}\left(1-u^{2}\right)^{s}\left(2u\right)^{2m-s}\phi\left(\alpha_{1}^{s}\alpha_{2}^{2m-s}\right).$

We multiply both sides by $\left(1+u^{2}\right)^{2m}$ and split the summation
depending on the parity of $s$ to obtain

$\displaystyle\left(1+u^{2}\right)^{2m}\phi\left(\alpha_{1}^{2m}\right)$
$\displaystyle=\sum_{s=0}^{m}\binom{2m}{2s}\left(1-u^{2}\right)^{2s}\left(2u\right)^{2m-2s}\phi\left(\alpha_{1}^{2s}\alpha_{2}^{2m-2s}\right)+$
$\displaystyle\quad\,\sum_{s=1}^{m}\binom{2m}{2s-1}\left(1-u^{2}\right)^{2s-1}\left(2u\right)^{2m-2s+1}\phi\left(\alpha_{1}^{2s-1}\alpha_{2}^{2m-2s+1}\right).$
(6)

The polynomials
$\pi_{1}=\alpha_{1}^{2s}\alpha_{2}^{2m-2s}-\alpha_{1}^{2s}\left(1-\alpha_{1}^{2}\right)^{m-s}$
and
$\pi_{2}=\alpha_{1}^{2s-1}\alpha_{2}^{2m-2s+1}-\alpha_{1}^{2s-1}\left(1-\alpha_{1}^{2}\right)^{m-s}\alpha_{2}$
both evaluate to the zero function on $S^{1}$ so by Locality, we must have
that

$\displaystyle\phi\left(\alpha_{1}^{2s}\alpha_{2}^{2m-2s}\right)$
$\displaystyle=\phi\left(\alpha_{1}^{2s}\left(1-\alpha_{1}^{2}\right)^{m-s}\right)=\sum_{t=0}^{m-s}\left(-1\right)^{t}\binom{m-s}{t}\phi\left(\alpha_{1}^{2s+2t}\right),$
(7) $\displaystyle\phi\left(\alpha_{1}^{2s-1}\alpha_{2}^{2m-2s+1}\right)$
$\displaystyle=\phi\left(\alpha_{1}^{2s-1}\left(1-\alpha_{1}^{2}\right)^{m-s}\alpha_{2}\right)=\sum_{t=0}^{m-s}\left(-1\right)^{t}\binom{m-s}{t}\phi\left(\alpha_{1}^{2s+2t-1}\alpha_{2}\right)$
(8)

respectively. By (7) and (8), equation (6) becomes

$\displaystyle\left(1+u^{2}\right)^{2m}\phi\left(\alpha_{1}^{2m}\right)$
$\displaystyle=$
$\displaystyle\sum_{s=0}^{m}\sum_{t=0}^{m-s}\left(-1\right)^{t}\binom{2m}{2s}\binom{m-s}{t}\left(1-u^{2}\right)^{2s}\left(2u\right)^{2m-2s}\phi\left(\alpha_{1}^{2s+2t}\right)+$
$\displaystyle\sum_{s=0}^{m}\sum_{t=0}^{m-s}\left(-1\right)^{t}\binom{2m}{2s-1}\binom{m-s}{t}\left(1-u^{2}\right)^{2s-1}\left(2u\right)^{2m-2s+1}\phi\left(\alpha_{1}^{2s+2t-1}\alpha_{2}\right).$

Now the following polynomial of degree at most $4m$ in
$\mathbb{F}\left[\beta\right]$, namely

$\displaystyle\pi$
$\displaystyle=\left(1+\beta^{2}\right)^{2m}\phi\left(\alpha_{1}^{2m}\right)-\sum_{s=0}^{m}\sum_{t=0}^{m-s}\left(-1\right)^{t}\binom{2m}{2s}\binom{m-s}{t}\left(1-\beta^{2}\right)^{2s}\left(2\beta\right)^{2m-2s}\phi\left(\alpha_{1}^{2s+2t}\right)-$
$\displaystyle\quad\,\sum_{s=0}^{m}\sum_{t=0}^{m-s}\left(-1\right)^{t}\binom{2m}{2s-1}\binom{m-s}{t}\left(1-\beta^{2}\right)^{2s-1}\left(2\beta\right)^{2m-2s+1}\phi\left(\alpha_{1}^{2s+2t-1}\alpha_{2}\right)$

has infinitely many roots, so $\pi$ is identically zero. By extracting the
coefficient of $\beta$ and $\beta^{2}$ respectively we get
$4m\phi\left(\alpha_{1}^{2m-1}\alpha_{2}\right)=0$ and
$8m^{2}\phi\left(\alpha_{1}^{2m}\right)-4m\left(2m-1\right)\phi\left(\alpha_{1}^{2m-2}\right)=0$.

Since $m$ is arbitrary, we must have for any $m\geq 1$,
$\phi\left(\alpha_{1}^{2m-1}\alpha_{2}\right)=0$ and the first-order
recurrence relation
$2m\phi\left(\alpha_{1}^{2m}\right)=\left(2m-1\right)\phi\left(\alpha_{1}^{2m-2}\right)$
with the initial condition $\phi\left(\mathbf{1}\right)=1_{\mathbb{F}}$. Thus
we see that $\phi\left(\alpha_{1}^{2m}\right)$ and
$\phi\left(\alpha_{1}^{2m-1}\alpha_{2}\right)$ are uniquely determined for all
$m\geq 1$.

Finally, by utilizing the Locality condition again, both
$\phi\left(\alpha_{1}^{2m+1}\alpha_{2}^{2n+1}\right)$ and
$\phi\left(\alpha_{1}^{2m}\alpha_{2}^{2n}\right)$ are uniquely determined
since

$\displaystyle\phi\left(\alpha_{1}^{2m+1}\alpha_{2}^{2n+1}\right)$
$\displaystyle=\phi\left(\alpha_{1}^{2m+1}\left(1-\alpha_{1}^{2}\right)^{n}\alpha_{2}\right)=\sum_{s=0}^{n}\left(-1\right)^{n}\binom{n}{s}\phi\left(\alpha_{1}^{2m+2s+1}\alpha_{2}\right),$
$\displaystyle\phi\left(\alpha_{1}^{2m}\alpha_{2}^{2n}\right)$
$\displaystyle=\phi\left(\alpha_{1}^{2m}\left(1-\alpha_{1}^{2}\right)^{n}\right)=\sum_{s=0}^{n}\left(-1\right)^{n}\binom{n}{s}\phi\left(\alpha_{1}^{2m+2s}\right).$

This concludes the proof.

##  4 Generalization to Arbitrary Circles

Fix a point $\left[a,b\right]\in\mathbb{A}$ and a non-zero $r\in\mathbb{F}$.
We define $S^{1}_{r,\left[a,b\right]}$ to be the collection of points
$\left[x,y\right]\in\mathbb{A}$ such that
$\left(x-a\right)^{2}+\left(y-b\right)^{2}=r^{2}$. A linear functional
$\phi_{r,\left[a,b\right]}\colon\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]\rightarrow\mathbb{F}$
is a circular integral functional on
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ with respect to
$S^{1}_{r,\left[a,b\right]}$ if the following conditions are satisfied:

(Normalization)

For the multiplicative identity $\mathbf{1}$ of
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$, we have
$\phi_{r,\left[a,b\right]}(\mathbf{1})=r$.

(Locality)

If $\pi\in\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ such that
$\varepsilon(\pi)=0$ on $S^{1}_{r,\left[a,b\right]}$, we have
$\phi_{r,\left[a,b\right]}\left(\pi\right)=0$.

(Invariance)

For any $\pi\in\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ and $h\in
SO(2,\mathbb{F})$,
$\phi_{r,\left[a,b\right]}\left(h\cdot\pi\right)=\phi_{r,\left[a,b\right]}\left(\pi\right)$.

By employing the same analysis, the existence and uniqueness of a circular
integral functional on $\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ with
respect to $S^{1}_{r,\left[a,b\right]}$ can be derived from that of $\psi$.

###### Theorem 4.1

There is one and only one circular integral functional on
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ with respect to
$S^{1}_{r,\left[a,b\right]}$, given by

$\displaystyle\psi_{r,\left[a,b\right]}\left(\alpha_{1}^{k}\alpha_{2}^{l}\right)=r\psi\left(\left(a+r\alpha_{1}\right)^{k}\left(b+r\alpha_{2}\right)^{l}\right)$

where $\psi$ is the circular integral functional on
$\mathbb{F}\left[\alpha_{1},\alpha_{2}\right]$ with respect to $S^{1}$.

Now we are finally able to give an algebraic interpretation of the super
Catalan numbers $S(m,n)$.

######  Theorem 4.2 (An algebraic interpretation of $S(m,n)$)

Over $\mathbb{Q}$, for any $m,n\in\mathbb{N}$, we have that
$2S(m,n)=\psi_{2,\left[0,0\right]}\left(\alpha_{1}^{2m}\alpha_{2}^{2n}\right)$.

Proof. It follows immediately from Theorem 4.1. We have that

$\psi_{2,\left[0,0\right]}\left(\alpha_{1}^{2m}\alpha_{2}^{2n}\right)=2\psi\left(\left(2\alpha_{1}\right)^{2m}\left(2\alpha_{2}\right)^{2n}\right)=\frac{2^{2m+2n+1}}{4^{m+n}}S\left(m,n\right)1_{\mathbb{Q}}=2S\left(m,n\right)$

as desired.

## Acknowledgement

The author thanks Hopein Tang for the helpful discussions.

## References

  * [1] Emily Allen and Irina Gheorghiciuc, A weighted interpretation for the super Catalan numbers, Journal of Integer Sequences, 17.3 (2014).
  * [2] John A. Baker, Integration Over Spheres and the Divergence Theorem for Balls, The American Mathematical Monthly, 104:1 (1997), 36-47.
  * [3] Eugène Catalan, Question 1135, Nouvelles Annales de Mathématiques (02) 13 (1874), 207.
  * [4] Xin Chen and Jane Wang, The super Catalan numbers $S\left(m,m+s\right)$ for $s\leq 4$, arXiv preprint arXiv:1208.4196 (2012).
  * [5] Gerald Folland, How to integrate a polynomial over a sphere, The American Mathematical Monthly, 108:5 (2001), 446-448.
  * [6] Evangelos Georgiadis, Akihiro Munemasa, and Hajime Tanaka, A note on super Catalan numbers, Interdisciplinary Information Sciences 18.1 (2012), 23-24.
  * [7] Ira Gessel, Super Ballot Numbers, Journal of symbolic computation, 14.2-3 (1992): 179-194.
  * [8] Ira Gessel and Guoce Xin, A combinatorial interpretation of the numbers $6\left(2n\right)!/n!\left(n+2\right)!$, Journal of Integer Sequences, Volume 8, 05.2.3 (2005).
  * [9] Kevin Limanta, Super Catalan Numbers and Fourier Summation over Finite Fields, arXiv preprint arXiv:2108.10191 (2022).
  * [10] Nicholas Pippenger and Kristin Schleich, Topological characteristics of random triangulated surfaces, Random Structure Algorithms 28 (2006), 247-288.
  * [11] Gilles Schaeffer. A combinatorial interpretation of super-Catalan numbers of order two, unpublished manuscript. 2003.
  * [12] Richard Stanley, Catalan Numbers, Cambridge University Press, 2015.


11institutetext: Department of Computer Engineering, Koç University, Istanbul,
Turkey
11email: {bbalioglu23, akhodaie22, ataweel20<EMAIL_ADDRESS>
# Grid-Based Decompositions for Spatial Data under Local Differential Privacy

Berkay Kemal Balioglu  Alireza Khodaie  Ameer Taweel
M. Emre Gursoy

###### Abstract

Local differential privacy (LDP) has recently emerged as a popular privacy
standard. With the growing popularity of LDP, several recent works have
applied LDP to spatial data, and grid-based decompositions have been a common
building block in the collection and analysis of spatial data under DP and
LDP. In this paper, we study three grid-based decomposition methods for
spatial data under LDP: Uniform Grid (UG), PrivAG, and AAG. UG is a static
approach that consists of equal-sized cells. To enable data-dependent
decomposition, PrivAG was proposed by Yang et al. as the most recent adaptive
grid method. To advance the state-of-the-art in adaptive grids, in this paper
we propose the Advanced Adaptive Grid (AAG) method. For each grid cell,
following the intuition that the cell’s intra-cell density distribution will
mimic its neighbors, AAG performs uneven cell divisions depending on the
neighboring cells’ densities. We experimentally compare UG, PrivAG, and AAG
using three real-world location datasets, varying privacy budgets, and query
sizes. Results show that AAG provides higher utility than PrivAG,
demonstrating the superiority of our proposed approach. Furthermore, UG’s
performance is heavily dependent on the choice of grid size. When the grid
size is chosen optimally in UG, AAG still beats UG for small queries, but UG
beats AAG for large (coarse-grained) queries.

###### Keywords:

Local differential privacy location privacy spatial grids location-based
services spatial data management.

##  1 Introduction

Large volumes of spatial data are nowadays available for collection and
analysis, thanks to the popularity of smartphones, connected cars, location-
based services (LBS), and social networks. There is great value in collecting
and analyzing this data for deriving insights and improving products and
services. On the other hand, ensuring the privacy of spatial data is
imperative since it contains sensitive information about individuals, such as
their home and work addresses, frequently visited locations, and personal
habits. In recent years, differential privacy has become a widely accepted
standard for privacy protection. Differential privacy has two main flavors:
centralized DP which assumes the existence of a trusted aggregator, and local
DP (LDP) which removes the need for a trusted aggregator. In LDP, each user
locally perturbs their data on their own device and shares the perturbed
version with the aggregator. LDP has recently received significant attention
from the academia and industry, and it has been deployed in products of
various tech companies such as Apple, Google, and Microsoft [4, 7, 9, 10].

With the growing popularity of LDP, several recent works have applied LDP to
spatial data and LBS [1, 8, 13, 19, 23, 25]. However, in many applications of
DP and LDP to spatial data, the data needs to be discretized so that the input
and output domains of the privacy mechanisms are discrete and finite. Grid-
based decompositions, which decompose the overall geospatial area $\Omega$
into non-overlapping cells, are a popular method for this purpose. After a
grid is laid, the user’s location can be discretized by determining which cell
it falls inside. Indeed, uniform and adaptive grids have been widely used in
the DP and LDP literature for trajectory collection and sharing [8, 23], range
query answering [18], synthetic data generation [11, 12], and so forth.

A uniform grid (UG) partitions the geospatial area $\Omega$ into $N\times M$
cells of equal size. However, the uniform grid is a static approach that does
not adapt to the underlying data distribution [18, 23]. It may result in a
poor partitioning of $\Omega$ when certain regions of $\Omega$ are too crowded
or too sparse (i.e., too high density or too low density). To enable density-
dependent decomposition of $\Omega$, the adaptive grid approach was proposed
[18, 23, 12]. The main idea of an adaptive grid is to first lay a uniform grid
$\mathcal{G}_{1}$ over the given $\Omega$, and according to the cell density
estimations obtained from users, further divide each individual cell (i.e.,
adapt the grid). To the best of our knowledge, the most recent adaptive grid
approach in LDP is PrivAG proposed by Yang et al. [23].

In this paper, we advance the state-of-the-art in adaptive grids by proposing
Advanced Adaptive Grid (AAG). In PrivAG, when a certain cell
$C_{k}\in\mathcal{G}_{1}$ needs to be divided further, this division is done
evenly. In AAG, we propose to perform this division by taking into account
$C_{k}$’s neighboring cells. This is because $C_{k}$’s intra-cell density
distribution is likely to be affected by its neighbors. For example, if
$C_{k}$’s right neighbor is dense but the left neighbor is sparse, then the
intra-cell density of $C_{k}$ is likely to be skewed towards the right.
Following the intuition behind adaptive grids which is to place many small
cells in dense areas but few large cells in sparse areas, instead of dividing
$C_{k}$ evenly, we perform an uneven division in AAG which is weighted
proportional to the neighbors’ densities. Furthermore, we propose heuristic
strategies to handle edge cells and corner cells which lack one or more
neighbors. In addition, motivated by our empirical observation that the
parameter choices in PrivAG yield adaptive grids with cell counts that are too
similar to $\mathcal{G}_{1}$, we propose new parameter values for AAG.

We experimentally compare the three grid approaches (UG, PrivAG, AAG) using
three real-world location datasets (Gowalla, Porto, Foursquare) by measuring
their errors in answering spatial density queries. We measure their Average
Query Errors (AQE) with different privacy budgets $\varepsilon$ and query
sizes $\rho$. We find that the AQEs of UG are heavily dependent on the grid
size, i.e., it performs well when the grid size is chosen optimally, but it
can perform quite poorly otherwise. After determining optimal grid sizes for
UG and then comparing it with PrivAG and AAG, we observe that: (i) AAG is
preferable to PrivAG across all $\varepsilon$ and $\rho$, demonstrating that
our AAG improves the state-of-the-art adaptive grid approach in LDP, (ii) AAG
is the best approach when $\rho$ is small, and (iii) UG is the best approach
when $\rho$ is large, e.g., for computing answers to large queries or for
fetching coarse (high-level) statistics.

Contributions. In summary, our main contributions are the following:

  * •

We propose a novel approach called Advanced Adaptive Grid (AAG) for grid-based
spatial data decompositions under LDP.

  * •

We experimentally show that AAG yields lower error compared to the state-of-
the-art adaptive grid approach in LDP, called PrivAG [23].

  * •

We show that the errors of UG are highly dependent on the grid size. When the
grid size is chosen optimally, then AAG still beats UG for small queries. Yet,
UG is the best approach when the queries are large.

##  2 Background

###  2.1 Data Model and Notations

Let $\mathcal{U}=\\{u_{1},u_{2},u_{3},...\\}$ denote the set of users in the
system where $|\mathcal{U}|$ is the total number of users, and let the two-
dimensional geospatial area be denoted by $\Omega$. For each user $u_{i}$, the
user’s true location is represented by $l_{i}$, such that $l_{i}\in\Omega$ and
$l_{i}$ consists of a pair of (latitude, longitude) coordinates. We assume
that the boundaries of the overall domain $\Omega$ are not privacy-sensitive,
and therefore, they can be known by all parties in the system. On the other
hand, each user’s location is privacy-sensitive and must be protected. For
example, if $\Omega$ corresponds to the city of Istanbul, the boundaries of
Istanbul are publicly known. In contrast, the locations of each user within
Istanbul need to be protected.

###  2.2 Local Differential Privacy

Local differential privacy (LDP) is a widely accepted standard for
safeguarding privacy, and it has been used in various products of tech
companies such as Apple, Google, and Microsoft [7, 9]. In LDP, users’ data is
perturbed on their devices before being collected by the aggregator (also
called the “server”). After collecting perturbed data from users, the server
uses estimation methods to recover statistics pertaining to the general
population $\mathcal{U}$. However, since each user’s data is perturbed, the
server cannot infer exact information about a specific user. In our context,
since the private information that needs to be protected by LDP is each user’s
location $l_{i}$, we define LDP as follows.

######  Definition 1 ($\varepsilon$-LDP)

A randomized algorithm $\Psi$ satisfies $\varepsilon$-local differential
privacy ($\varepsilon$-LDP), where $\varepsilon>0$, if and only if for any two
inputs $l_{i},l^{*}_{i}$, it holds that:

$\forall y\in
Range(\Psi):~{}~{}~{}~{}\frac{{Pr}[\Psi(l_{i})=y]}{{Pr}[\Psi(l^{*}_{i})=y]}\leq
e^{\varepsilon}$ (1)

where $Range(\Psi)$ stands for the set of all possible outputs of the
algorithm $\Psi$.

$\varepsilon$-LDP ensures that having observed the output $y$, the server (or
any other party who observed $y$) is not able to distinguish whether the
original location of the user was $l_{i}$ or $l^{*}_{i}$ with probability more
than the odds ratio controlled by $e^{\varepsilon}$. The strength of the
privacy protection is controlled by the parameter $\varepsilon$, commonly
known as the privacy budget. Lower $\varepsilon$ yields stronger privacy.

###  2.3 Optimized Local Hashing

Numerous LDP protocols have been proposed to minimize utility loss and/or
communication cost under various conditions. In this paper, we use a state-of-
the-art protocol called Optimized Local Hashing (OLH) [20] due to its high
utility and low communication cost [5, 10]. Similar to other LDP protocols,
OLH consists of two main components: (i) user-side encoding and perturbation
to satisfy LDP on users’ devices, and (ii) server-side estimation after
collecting perturbed data from the user population.

User-Side Perturbation in OLH: OLH uses hash functions to reduce the size of
the input domain $\mathcal{D}$. To address the issue of recurring hash
collisions, a family of hash functions $\mathcal{H}$ is used such that each
user chooses a different hash function from $\mathcal{H}$. Let $\mathcal{H}$
be a hash function family such that each $H\in\mathcal{H}$ maps a value from
$\mathcal{D}$ to an integer between 1 and $m$, i.e.,
$H:\mathcal{D}\rightarrow[1,m]$. User $u$ with true value $v_{u}$ chooses a
hash function from $\mathcal{H}$ uniformly at random
$H_{u}\leftarrow_{\$}\mathcal{H}$ and computes the integer $x_{u}\leftarrow
H_{u}(v_{u})$. Then, the perturbation step takes $x_{u}$ as input and produces
a perturbed integer $x^{\prime}_{u}\in[1,m]$ with the probabilities:

$\forall_{i\in[1,m]}:~{}\text{Pr}[x^{\prime}_{u}=i]=\begin{cases}\frac{e^{\varepsilon}}{e^{\varepsilon}+m-1}&\text{
if }x_{u}=i\\\ \frac{1}{e^{\varepsilon}+m-1}&\text{ if }x_{u}\neq
i\end{cases}$ (2)

The user sends the resulting tuple $\langle H_{u},x^{\prime}_{u}\rangle$ to
the server. Following [20, 21], we use the default value of $m$ as
$m=e^{\varepsilon}+1$, which optimizes utility.

Server-Side Estimation in OLH: The server receives tuples from users
$u\in\mathcal{U}$. To perform estimation for some value $v\in\mathcal{D}$, the
server first computes $Sup(v)$ = total number of tuples for which the
condition $x^{\prime}_{u}=H_{u}(v)$ holds. Then, the server estimates the
number of occurrences of value $v$ in the population using the following
unbiased estimator $\Phi(v)$:

$\Phi(v)=\frac{(e^{\varepsilon}+m-1)\cdot(m\cdot
Sup(v)-|\mathcal{U}|)}{(e^{\varepsilon}-1)\cdot(m-1)}$ (3)

##  3 Grid-Based Decompositions Under LDP

Grid-based decompositions are commonly used in the DP and LDP literature for
spatial data collection and analysis [8, 11, 12, 18, 23]. They employ uniform
or adaptive grid structures to partition the geospatial area $\Omega$ into
cells. Then, the user’s location $l_{i}$ is discretized by determining which
cell it falls inside. We first describe the Uniform Grid (UG) approach in
Section 3.1, then the existing adaptive grid approach called PrivAG [23] in
Section 3.2, and finally our novel Advanced Adaptive Grid approach called AAG
in Section 3.3.

###  3.1 Uniform Grid (UG)

A uniform grid partitions the geospatial area $\Omega$ into $N\times M$ cells
of equal size. We denote this grid by
$\mathcal{G}_{uni}=(C_{1},C_{2},...,C_{N\times M})$ where each
$C_{j}\in\mathcal{G}$ is one cell. The geographic coverage of all cells are
disjoint from one another. User $u_{i}$ with location $l_{i}$ discretizes
his/her location by finding which $C_{i}\in\mathcal{G}$ their $l_{i}$ falls
inside. Then, to satisfy LDP, the cell information $C_{i}$ needs to be
perturbed. Hence, we feed $C_{i}$ into the OLH protocol with the appropriate
parameters.

Algorithm 1 Collecting location data with LDP using a grid

1:Input: Users $\mathcal{U}$, grid $\mathcal{G}$, privacy budget $\varepsilon$

2:Output: Densities of each cell in $\mathcal{G}$

3:

4:$\triangleright$ User-side discretization and perturbation

5:for each user $u_{i}\in\mathcal{U}$ do

6: for each cell $C_{j}\in\mathcal{G}$ do

7: if $l_{i}$ falls inside $C_{j}$ then

8: Set user’s true cell as: $C_{i}\leftarrow C_{j}$

9: break

10: Execute the user-side OLH protocol with true value = $C_{i}$, domain
$\mathcal{D}$ = $\mathcal{G}$, and privacy budget = $\varepsilon$

11: Send the resulting tuple $\langle H_{u},x^{\prime}_{u}\rangle$ to the
server

12:

13:$\triangleright$ Server-side estimation

14:Server receives $\langle H_{u},x^{\prime}_{u}\rangle$ from all
$u_{i}\in\mathcal{U}$

15:for each cell $C_{j}\in\mathcal{G}$ do

16: Compute $Sup(C_{j})$ as the number of tuples for which
$x^{\prime}_{u}=H_{u}(C_{j})$

17: Compute estimate $\Phi(C_{j})$ using Equation 3

18:return $\Phi(C_{1})$, $\Phi(C_{2})$, … for all $C_{j}\in\mathcal{G}$

An overview of LDP location data collection using $\mathcal{G}_{uni}$ is shown
in Algorithm 1. For each user $u_{i}$ with location $l_{i}$, the user first
finds their true cell $C_{i}$, i.e., which cell in the grid their location
falls inside (lines 6-9). After finding $C_{i}$, the user executes the OLH
protocol by treating their true value as $C_{i}$, the domain of the protocol
as $\mathcal{G}_{uni}=(C_{1},C_{2},...,C_{N\times M})$, and using the privacy
budget $\varepsilon$. Since OLH satisfies $\varepsilon$-LDP, the perturbation
of $C_{i}$ using OLH achieves $\varepsilon$-LDP. Note that since $l_{i}$ is
discretized as $C_{i}$, the domain of OLH is also discretized:
$\mathcal{D}=\mathcal{G}_{uni}=(C_{1},C_{2},...,C_{N\times M})$, instead of
using a continuous domain $\mathcal{D}=\Omega$. Each user sends the OLH
protocol output to the server. The server receives the outputs from all users
and then proceeds to estimate the density of each cell
$C_{j}\in\mathcal{G}_{uni}$. Here, the density of a cell corresponds to the
number of users whose locations are in that cell. The estimation of each cell
$C_{j}\in\mathcal{G}_{uni}$ is performed one by one (lines 15-17), using the
server-side estimation procedures of OLH explained in Section 2.3. Finally,
the estimated densities are returned (line 18).

Note that although Algorithm 1 is given with the OLH protocol, it is possible
to collect location data using a uniform grid with other LDP protocols such as
GRR, RAPPOR, and OUE [10, 20]. The general intuition and procedure remain the
same, but the user-side perturbation (lines 10-11) and server-side estimation
(lines 16-17) steps would be changed according to the LDP protocol in use.

###  3.2 Existing Adaptive Grid: PrivAG

UG is a static approach that does not adapt to the underlying data
distribution [18, 23]. It may result in a poor partitioning of $\Omega$ in
scenarios where certain regions are too crowded or too sparse (too high
density or too low density). For example, when a cell is too crowded, then
further partitioning it into smaller cells enables a better understanding of
the detailed data distribution within that cell. Yet, the uniform grid is not
able to achieve this. On the other hand, if a certain region of $\Omega$ is
sparse, then the cells in that region will have zero or near-zero density, and
the uniform grid will be over-partitioning that region. Over-partitioned cells
with zero density lead to utility loss since their estimated densities are
likely to be non-zero due to LDP perturbation, leading to fictitious and
skewed results. To overcome these limitations and enable data-dependent
decompositions, the adaptive grid approach was proposed in DP and LDP [18,
23]. The main idea of an adaptive grid is to first lay a uniform grid
$\mathcal{G}_{1}$ over the given $\Omega$, and according to the cell density
estimations obtained from users, further divide each individual cell (i.e.,
adapt the grid) to obtain the final grid.

To the best of our knowledge, the most recent adaptive grid approach in LDP is
PrivAG, proposed by Yang et al. [23]. In PrivAG, the server first divides the
set of users $\mathcal{U}$ into two groups: $\mathcal{U}_{1}$ and
$\mathcal{U}_{2}$. Then, the server constructs a uniform grid
$\mathcal{G}_{1}$ of size $g_{1}\times g_{1}$ and broadcasts $\mathcal{G}_{1}$
to users in $\mathcal{U}_{1}$. Based on $\mathcal{G}_{1}$, users in
$\mathcal{U}_{1}$ discretize their locations and use OLH to send their
perturbed outcomes to the server. The server estimates the densities of each
cell in $\mathcal{G}_{1}$. Then, for each cell $C_{k}\in\mathcal{G}_{1}$, the
server further partitions $C_{k}$ into $g_{2}^{k}\times g_{2}^{k}$ cells,
where $g_{2}^{k}$ depends on $\Phi(C_{k})$ and several other parameters (more
detail below). After all cells are partitioned according to their $g_{2}^{k}$,
the resulting adaptive grid $\mathcal{G}_{ag}$ is obtained. Then,
$\mathcal{G}_{ag}$ is advertised to users in $\mathcal{U}_{2}$ and desired
statistics are obtained using $\mathcal{G}_{ag}$, e.g., cell densities or
Hidden Markov Model weights [23].

Variables $g_{1}$ and $g_{2}^{k}$. Since the values of $g_{1}$ and $g_{2}^{k}$
have an important impact on the grid that is constructed, Yang et al. [23]
propose guidelines for choosing them. According to their guidelines, $g_{1}$
should be chosen as:

$g_{1}=\sqrt{2\alpha\cdot(e^{\varepsilon}-1)\cdot\sqrt{\frac{|\mathcal{U}|}{e^{\varepsilon}}}}$
(4)

Then, for each cell $C_{k}$ with estimated density $\Phi(C_{k})$, its
$g_{2}^{k}$ should be chosen as:

$g_{2}^{k}=\sqrt{2\alpha\cdot\Phi(C_{k})\cdot(e^{\varepsilon}-1)\cdot\sqrt{\frac{(1-\sigma)\cdot|\mathcal{U}|}{e^{\varepsilon}}}}$
(5)

Here, $\alpha$ is a small constant recommended to take values between [0.01,
0.02], and $\sigma$ denotes the proportion of users in $\mathcal{U}_{1}$,
i.e., $\sigma=\frac{|\mathcal{U}_{1}|}{|\mathcal{U}|}$. It is recommended for
$\sigma$ to be in the range [0.1, 0.3]. An algorithmic overview of the PrivAG
approach is given in Algorithm 2.

Algorithm 2 Algorithmic summary of the PrivAG approach

1:Input: Users $\mathcal{U}$, parameters $\alpha$ and $\sigma$, privacy budget
$\varepsilon$

2:Output: Densities of each cell in adaptive grid $\mathcal{G}_{ag}$

3:

4:$\triangleright$ First phase of PrivAG

5:Server computes $g_{1}$ according to Equation 4

6:Server divides $\mathcal{U}$ into two groups $\mathcal{U}_{1}$ and
$\mathcal{U}_{2}$ such that $|\mathcal{U}_{1}|$ = $\sigma\times|\mathcal{U}|$

7:Server lays $g_{1}\times g_{1}$ uniform grid $\mathcal{G}_{1}$ on $\Omega$

8:Call Algorithm 1 with $\mathcal{U}_{1}$, $\mathcal{G}_{1}$ and $\varepsilon$
to obtain $\Phi(C_{1})$, $\Phi(C_{2})$, … for all $C_{k}\in\mathcal{G}_{1}$

9:

10:$\triangleright$ Second phase of PrivAG

11:for each cell $C_{k}\in\mathcal{G}_{1}$ do

12: Compute $g_{2}^{k}$ according to Equation 5

13: Divide $C_{k}$ into $g_{2}^{k}\times g_{2}^{k}$ cells of equal size

14:Let $\mathcal{G}_{ag}$ denote the resulting grid after the above divisions

15:Call Algorithm 1 with $\mathcal{U}_{2}$, $\mathcal{G}_{ag}$ and
$\varepsilon$ to obtain $\Phi(C_{1})$, $\Phi(C_{2})$, … for all cells in
$\mathcal{G}_{ag}$

###  3.3 Proposed Approach: Advanced Adaptive Grid (AAG)

As a key contribution of our paper, we propose the Advanced Adaptive Grid
(AAG) approach which advances PrivAG. Consider Figure 1, which exemplifies a
uniform grid with user densities written inside the cells (on the left),
PrivAG (in the middle), and our proposed AAG (on the right). Say that the
first phase of PrivAG laid a 3 $\times$ 3 uniform grid $\mathcal{G}_{1}$ on
$\Omega$, and the resulting densities of cells are shown on the left of Figure
1. In its second phase, PrivAG iterates through each $C_{k}\in\mathcal{G}_{1}$
and decides how to further divide $C_{k}$. Say that in the current iteration,
$C_{k}$ is the middle cell in Figure 1, and it is found that $g_{2}$ = 2.
Then, PrivAG divides the middle cell into 2 $\times$ 2 = 4 equally sized cells
as shown in Figure 1. Our critical intuition is that the division of this
middle cell into equal-sized cells is suboptimal. This is because there are
10.000 users in the upper neighbor whereas 50.000 users in the lower neighbor.
Furthermore, there are 2.000 users in the left neighbor whereas 4.000 users in
the right neighbor. Based on these neighbor cells’ densities, it is likely
that the bottom right corner of $C_{k}$ is denser whereas the upper left
corner is more sparse, because the intra-cell distribution is likely to be
mimicked by neighbor cells. According to the original intuition behind
adaptive grids [18, 23], it is desirable to have many small cells in dense
areas but few large cells in sparse areas. Following this intuition, instead
of dividing $C_{k}$ evenly (as done in PrivAG), our AAG approach proposes to
divide the cell by taking into account the neighbors’ densities. Therefore,
the vertical division of the cell is done with the ratio 1-to-5 which is
proportional to the densities of the upper and lower neighbors (10.000 vs
50.000), whereas the horizontal division is done with the ratio 1-to-2 which
is proportional to the left and right neighbors (2.000 vs 4.000). The result
is shown in Figure 1 (on the right).

Figure 1: Difference between PrivAG and AAG

We give an algorithmic overview of our proposed AAG approach in Algorithm 3.
The first phase of AAG is identical to PrivAG, i.e., it lays a $g_{1}\times
g_{1}$ uniform grid $\mathcal{G}_{1}$ on $\Omega$ and obtains the cell
densities $\Phi(C_{1})$, $\Phi(C_{2})$, … for all $C_{k}\in\mathcal{G}_{1}$
using $\varepsilon$-LDP. The core difference lies in the second phase of AAG.
After computing $g_{2}^{k}$, instead of dividing cell $C_{k}$ uniformly, AAG
performs the following. First, it calculates the horizontal split location
using the densities of the left and right neighbors. That is, denoting the
left neighbor of $C_{k}$ by $C^{L}_{k}$ and the right neighbor of $C_{k}$ by
$C^{R}_{k}$, the horizontal split location $hsplit$ is calculated as:

$hsplit=\frac{\Phi(C^{R}_{k})}{\Phi(C^{L}_{k})+\Phi(C^{R}_{k})}\times(\text{width
of }C_{k})$ (6)

Similarly, to calculate the vertical split location, the densities of the
upper and lower neighbors are used. Denoting the upper neighbor of $C_{k}$ by
$C^{U}_{k}$ and the lower neighbor of $C_{k}$ by $C^{B}_{k}$, the vertical
split location $vsplit$ is calculated as:

$vsplit=\frac{\Phi(C^{B}_{k})}{\Phi(C^{U}_{k})+\Phi(C^{B}_{k})}\times(\text{height
of }C_{k})$ (7)

Then, $C_{k}$ is divided horizontally using $hsplit$ and vertically using
$vsplit$. As a result, four subcells of $C_{k}$ are obtained (as exemplified
in the rightmost example in Figure 1). If $g_{2}^{k}>2$, then each of the four
subcells needs to be further divided. This further division is done uniformly,
i.e., uniformly into $(g_{2}^{k}-1)/2$ pieces horizontally and
$(g_{2}^{k}-1)/2$ pieces vertically, to make sure that $C_{k}$ is divided into
$g_{2}^{k}\times g_{2}^{k}$ subcells overall.

Algorithm 3 Algorithmic summary of the AAG approach

1:Input: Users $\mathcal{U}$, parameters $\alpha$ and $\sigma$, privacy budget
$\varepsilon$

2:Output: Densities of each cell in adaptive grid $\mathcal{G}_{aag}$

3:

4:$\triangleright$ First phase of AAG

5:The first phase of AAG is the same as PrivAG

6:

7:$\triangleright$ Second phase of AAG

8:for each cell $C_{k}\in\mathcal{G}_{1}$ do

9: Compute $g_{2}^{k}$ according to Equation 5

10: Compute $hsplit$ for $C_{k}$ according to Equation 6

11: Compute $vsplit$ for $C_{k}$ according to Equation 7

12: Divide $C_{k}$ into four subcells using $hsplit$ and $vsplit$

13: if $g_{2}^{k}>2$ then

14: Uniformly divide each subcell into $\frac{g_{2}^{k}-1}{2}$ pieces
horizontally and vertically

15:Let $\mathcal{G}_{aag}$ denote the resulting grid after the above divisions

16:Call Algorithm 1 with $\mathcal{U}_{2}$, $\mathcal{G}_{aag}$ and
$\varepsilon$ to obtain $\Phi(C_{1})$, $\Phi(C_{2})$, .. for all cells in
$\mathcal{G}_{aag}$

Handling edge and corner cells. When $C_{k}$ is a cell that is located on one
of the edges or corners of $\mathcal{G}_{1}$, it will lack one or more
neighbors. For example, consider the top left cell in Figure 1, which is a
corner cell. This cell has a lower neighbor and a right neighbor, therefore
$\Phi(C^{B}_{k})$ and $\Phi(C^{R}_{k})$ can be found. However, it does not
have an upper neighbor or a left neighbor, therefore $\Phi(C^{U}_{k})$ and
$\Phi(C^{L}_{k})$ are not available. Similarly, if a cell is an edge cell,
then it has three neighbors but it lacks one neighbor. For example, a cell
that is on the rightmost edge of $\mathcal{G}_{1}$ has its left, upper, and
lower neighbors, but it lacks a right neighbor. For cells that lack one or
more neighbors, computing their $hsplit$ and $vsplit$ locations via Equations
6 and 7 using zero densities for the missing neighbors leads to erroneous
results. To address this problem, we perform the following. If any of the
neighbors of the current cell $C_{k}$ is missing, then $C_{k}$ uses its own
density $\Phi(C_{k})$ in place of the missing neighbor’s density. For example,
for the top left cell which lacks an upper neighbor and left neighbor, instead
of assuming $\Phi(C^{U}_{k})=0$ and $\Phi(C^{L}_{k})=0$, we enforce:
$\Phi(C^{U}_{k})=\Phi(C_{k})$ and $\Phi(C^{L}_{k})=\Phi(C_{k})$.

Choice of $g_{1}$ and $g_{2}^{k}$. Recall that the $\alpha$ and $\sigma$
parameters in PrivAG affect the values of $g_{1}$ and $g_{2}^{k}$. As we
experimented with PrivAG and AAG, we observed that the recommended values for
the $\alpha$ and $\sigma$ parameters in PrivAG yield adaptive grids
$\mathcal{G}_{aag}$ with cell counts that are similar to the initial uniform
grid $\mathcal{G}_{1}$. This caused our $\mathcal{G}_{aag}$ to be similar to
$\mathcal{G}_{1}$, which diminishes the benefits of using an adaptive grid. To
address this problem, we propose to use different values for the $\alpha$ and
$\sigma$ parameters in AAG, leading to different choices of $g_{1}$ and
$g_{2}^{k}$. In essence, our choices aim to obtain an increased number of cell
divisions in dense regions so that dense regions can be partitioned and
represented in more detail, but without causing excessively large $g_{2}^{k}$.
Specifically, as opposed to the default values of $\alpha$ and $\sigma$ in
PrivAG, we use $\alpha$ = 0.25 and $\sigma$ = 0.5 in AAG. The increased value
of $\alpha$ in AAG directly increases the chosen $g_{1}$ and $g_{2}^{k}$
values, per Equations 4 and 5. Increased $\sigma$ has two effects. First, it
causes the estimated densities $\Phi(C_{k})$ used in Equation 5 to be more
accurate, since a larger $\mathcal{U}_{1}$ is used to estimate them. Thus, the
accuracy of $g_{2}^{k}$ computations will be increased. Second, since
$\sqrt{(1-\sigma)}$ appears in Equation 5, it slightly decreases the value of
$g_{2}^{k}$. This slight decrease is much less pronounced than the increase
caused by $\sigma$, and it positively contributes to the calculation of
$g_{2}^{k}$ by ensuring that the chosen $g_{2}^{k}$ will not be excessively
large.

Table 1: Number of resulting cells in different grid approaches Dataset |  Grid |  $\varepsilon$ = 0.5 |  $\varepsilon$ = 1 |  $\varepsilon$ = 3 |  $\varepsilon$ = 5
---|---|---|---|---|---
Gowalla |  Initial $\mathcal{G}_{1}$ | 36 | 81 | 324 | 900
PrivAG | 42 | 96 | 440 | 1358
AAG | 276 | 567 | 2451 | 8745
Porto | Initial $\mathcal{G}_{1}$ | 25 | 49 | 225 | 625
PrivAG | 31 | 63 | 256 | 745
AAG | 188 | 390 | 1567 | 4503
Foursquare | Initial $\mathcal{G}_{1}$ | 16 | 36 | 121 | 361
PrivAG | 19 | 45 | 162 | 455
AAG | 107 | 235 | 957 | 2794

In Table 1, we provide a subset of our experiment results showing the number
of cells in the initial grid $\mathcal{G}_{1}$, the final grid produced by
PrivAG, and the final grid produced by AAG. We repeat this experiment using
three datasets: Gowalla, Porto, Foursquare (more details about the datasets
are provided in Section 4), and $\varepsilon$ values ranging between 0.5 and
5. We observe from Table 1 that especially for lower $\varepsilon$ values such
as 0.5 and 1, the number of cells in $\mathcal{G}_{1}$ is very similar to
PrivAG. This supports our motivation that PrivAG’s division of dense cells is
not sufficiently detailed. In contrast, our choices in AAG ensure that the
grids produced by AAG always have a larger number of cells compared to
$\mathcal{G}_{1}$.

##  4 Experiments and Discussion

###  4.1 Experiment Setup and Datasets

In this section, we experimentally compare the three grid-based decomposition
methods (UG, PrivAG, AAG) under varying parameters. We implemented all
algorithms and methods in Python. We use three real-world location datasets in
our experiments: Gowalla, Porto, and Foursquare. To account for LDP
randomness, each experiment is repeated 10 times and the average results are
reported.

Gowalla: Gowalla was a location-based social networking site where users
shared their locations via check-ins. From the full dataset [3], we extracted
check-ins made in the United States, between longitudes -124.26 and -71.87 and
latitudes 25.45 and 47.44. Consequently, we have 3,451,190 remaining
locations.

Porto: The Porto dataset contains trips of 442 taxis driving in the city of
Porto. It was released as part of the Taxi Service Prediction Competition in
ECML-PKDD [16]. The original dataset contains full taxi trips, i.e.,
trajectories with multiple location readings per trip. We pre-processed it by
keeping only one randomly sampled location from each trip and treated them as
the current locations of users $\mathcal{U}$. We only used the locations
between longitudes -8.691294 and -8.552009 and latitudes 41.138351 and
41.185935, corresponding to the city of Porto. This resulted in 1,620,157
remaining locations.

Foursquare: The Foursquare dataset contains location check-ins of social media
users in Tokyo, between April 2012 and February 2013 [22]. We used this
dataset without pre-processing. In total, the dataset contains 573,703
locations.

###  4.2 Utility Metric

Following previous works, we use spatial density queries for utility
measurement [1, 12, 18, 23]. A spatial density query $q$ with geospatial area
denoted by $A(q)$ is a query of the form: “How many users are located within
$A(q)$”? Let $ans_{q}$ denote the ground truth answer of $q$, i.e., the answer
that would be computed if all users’ locations were known exactly, without
privacy constraints. Using a grid $\mathcal{G}$ and estimated cell densities
$\Phi(C_{k})$ for $C_{k}\in\mathcal{G}$, the noisy answer of $q$ (denoted by
$ans^{\prime}_{q}$) can be calculated as follows. First, $ans^{\prime}_{q}$ is
initialized as 0. Then, each cell $C_{k}\in\mathcal{G}$ is visited one by one:

  1. 1.

Denoting by $A(C_{k})$ the geospatial area of $C_{k}$, if $A(C_{k})$ is
disjoint from $A(q)$, then $C_{k}$ is ignored.

  2. 2.

If $A(C_{k})$ is fully contained within $A(q)$, then $ans^{\prime}_{q}$ is
increased by $\Phi(C_{k})$.

  3. 3.

If $A(C_{k})$ partially intersects with $A(q)$, then $ans^{\prime}_{q}$ is
increased proportional to the intersection amount, i.e.:

$ans^{\prime}_{q}=ans^{\prime}_{q}+\Phi(C_{k})\times\frac{||A(C_{k})\cap
A(q)||}{||A(C_{k})||}$ (8)

Average Query Error (AQE): We generate $\gamma$ = 500 number of random queries
$q_{1},q_{2},...$ with different $A(q_{i})$ and compute their $ans_{q_{i}}$
and $ans^{\prime}_{q_{i}}$. Then, we measure the average error between
$ans_{q_{i}}$ and $ans^{\prime}_{q_{i}}$ using the AQE metric:

$AQE=\frac{1}{\gamma}*\sum\limits_{i=1}^{\gamma}\frac{|ans_{q_{i}}-ans^{\prime}_{q_{i}}|}{max\\{ans_{q_{i}},b\\}}$
(9)

Here, $b$ denotes a bound to mitigate the dominating effect of queries with
extremely high selectivities (extremely low $ans_{q_{i}}$) [11, 12]. We set
the value of $b$ as: $b=2\%\times|\mathcal{U}|$.

###  4.3 Uniform Grid Experiments

Figure 2: AQEs of $N\times N$ uniform grids $\mathcal{G}_{uni}$ with varying
$N$, fixed $\varepsilon$ = 1. From left to right: Gowalla dataset, Porto
dataset, Foursquare dataset.

To measure the utility impact of the number of cells on the Uniform Grid (UG),
we generate $N\times N$ uniform grids with various $N$ and measure their AQEs.
The results are shown in Figure 2. It can be observed from Figure 2 that AQEs
are highly dependent on the value of $N$. If $N$ is badly chosen (e.g., too
small or too large), then AQEs can be 3-4 times higher compared to the case
when $N$ is near-optimal. Furthermore, results on all three datasets follow a
U-shaped curve, e.g., $N$ between 15-20 seems to be optimal for the Gowalla
dataset, $N$ = 10 seems to be optimal for the Porto dataset, and $N$ between
7-12 seems to be optimal for the Foursquare dataset. The fact that different
$N$ values are best for different datasets makes it difficult to determine a
good value of $N$ prior to data collection in practice. Overall, we can
conclude that the UG approach is highly sensitive to the choice of $N$, and
the optimal choice of $N$ varies from one dataset to another. In the rest of
the experiments, we use the best results (i.e., optimized choice of $N$) when
comparing UG with other approaches.

###  4.4 Comparison of Grid Approaches

In this section, we compare the three grid approaches (UG, PrivAG, AAG) using
different-sized random queries. To do so, we enforce that the random queries
we generate for calculating AQE have size: $A(q)=\rho\times\Omega$, where
$\rho\in(0,1]$ is the query size parameter. In Table 2, we fix $\varepsilon$ =
1 and vary the value of $\rho$ between 0.005% and 0.5%. Note that these are
relatively low values of $\rho$, i.e., the generated queries are small. We use
the bold notation in Table 2 when comparing the two adaptive grid approaches
(PrivAG vs AAG), i.e., the one that yields lower AQE is written in bold. This
helps to demonstrate the improvement of AAG compared to PrivAG. We use the
grey cell background to denote the best-performing approach when comparing all
three (UG vs PrivAG vs AAG).

Table 2: AQEs with varying query sizes $\rho$, fixed $\varepsilon$ = 1. Dataset |  Method |  $\rho$ = 0.005% |  $\rho$ = 0.01% |  $\rho$ = 0.05% |  $\rho$ = 0.1% |  $\rho$ = 0.5%
---|---|---|---|---|---|---
Gowalla |  UG | 0.0034 | 0.0067 | 0.0279 | 0.0485 | 0.120
PrivAG | 0.0039 | 0.0077 | 0.0374 | 0.0728 | 0.305
AAG | 0.0023 | 0.0051 | 0.0236 | 0.0460 | 0.185
Porto | UG | 0.0028 | 0.0045 | 0.0180 | 0.0321 | 0.082
PrivAG | 0.0034 | 0.0056 | 0.0283 | 0.0540 | 0.205
AAG | 0.0025 | 0.0045 | 0.0247 | 0.0501 | 0.195
Foursquare | UG | 0.0032 | 0.0054 | 0.0243 | 0.0416 | 0.126
PrivAG | 0.0036 | 0.0062 | 0.0291 | 0.0547 | 0.203
AAG | 0.0025 | 0.0043 | 0.0234 | 0.0450 | 0.177

The results in Table 2 show that AAG achieves lower error compared to PrivAG
in all settings. In addition, AAG also achieves lower error compared to UG in
the majority of settings. However, as $\rho$ increases, UG starts performing
better than AAG. This implies that for fine-grained density modeling and
small-sized queries, AAG is the best approach. This is an intuitive result,
considering that AAG excels in dividing dense areas in a detailed fashion.
Yet, for more coarse (high-level) density statistics, UG can perform better.
Another observation we make from Table 2 is that when $\rho$ increases, the
errors also increase. This is because increasing $\rho$ causes the
intersection between $A(q_{i})$ and various cells to increase, therefore
$ans_{q_{i}}$ and $ans^{\prime}_{q_{i}}$ become larger. Hence, overall noise
amount increases as well, and among the two factors in the denominator of
Equation 9, $ans_{q_{i}}$ starts to dominate rather than $b$. Consequently,
higher AQEs are obtained.

In Table 3, we perform the same experiment but with much larger $\rho$ values,
ranging between 2% and 10%. For such large $\rho$ values, we observe that UG
achieves lower AQE compared to PrivAG and AAG in all cases. It should be noted
that these results use optimized $N$ values for UG, hence they do not account
for potentially suboptimal choices of $N$. On the other hand, comparing PrivAG
versus AAG, we once again observe that AAG beats PrivAG.

Table 3: AQEs with varying query sizes $\rho$, fixed $\varepsilon$ = 1. Much larger $\rho$ values are used in this table compared to Table 2. Dataset |  Method |  $\rho$ = 2% |  $\rho$ = 4% |  $\rho$ = 6% |  $\rho$ = 8% |  $\rho$ = 10%
---|---|---|---|---|---|---
Gowalla |  UG | 0.20 | 0.21 | 0.24 | 0.22 | 0.21
PrivAG | 0.83 | 1.15 | 1.32 | 1.29 | 1.25
AAG | 0.52 | 0.71 | 0.73 | 0.73 | 0.72
Porto | UG | 0.12 | 0.12 | 0.11 | 0.12 | 0.09
PrivAG | 0.54 | 0.76 | 0.85 | 0.91 | 0.91
AAG | 0.38 | 0.49 | 0.60 | 0.61 | 0.65
Foursquare | UG | 0.17 | 0.20 | 0.19 | 0.22 | 0.21
PrivAG | 0.48 | 0.63 | 0.68 | 0.70 | 0.71
AAG | 0.40 | 0.56 | 0.64 | 0.70 | 0.71

###  4.5 Impact of the Privacy Budget $\varepsilon$

In this section, we keep the query sizes $\rho$ fixed and vary the privacy
budgets $\varepsilon$ between 0.5 and 5. Table 4 provides the results with
$\rho$ = 0.01% and Table 5 provides the results with $\rho$ = 4%. In both
tables, we use the same bold and grey color highlight strategies that we used
in the previous section. According to the results in Table 4, when $\rho$ =
0.01%, AAG is the best approach. It yields the lowest AQEs across all
$\varepsilon$. On the other hand, when $\rho$ = 4%, UG becomes the best
approach as shown in Table 5. This is parallel to the results reported in the
previous section. When $\rho$ = 4%, although AAG consistently beats PrivAG, it
cannot reach UG’s low AQE values.

Table 4: AQEs with varying privacy budgets $\varepsilon$, fixed $\rho$ = 0.01%. Dataset |  Method |  $\varepsilon$ = 0.5 |  $\varepsilon$ = 1 |  $\varepsilon$ = 3 |  $\varepsilon$ = 5
---|---|---|---|---|---
Gowalla |  UG | 0.0070 | 0.0066 | 0.0064 | 0.0056
PrivAG | 0.0075 | 0.0077 | 0.0072 | 0.0062
AAG | 0.0047 | 0.0051 | 0.0049 | 0.0041
Porto | UG | 0.0048 | 0.0045 | 0.0045 | 0.0045
PrivAG | 0.0058 | 0.0056 | 0.0059 | 0.0060
AAG | 0.0048 | 0.0045 | 0.0049 | 0.0049
Foursquare | UG | 0.0055 | 0.0054 | 0.0051 | 0.0048
PrivAG | 0.0060 | 0.0062 | 0.0061 | 0.0069
AAG | 0.0044 | 0.0043 | 0.0040 | 0.0047
Table 5: AQEs with varying privacy budgets $\varepsilon$, fixed $\rho$ = 4%. Dataset |  Method |  $\varepsilon$ = 0.5 |  $\varepsilon$ = 1 |  $\varepsilon$ = 3 |  $\varepsilon$ = 5
---|---|---|---|---|---
Gowalla |  UG | 0.28 | 0.23 | 0.17 | 0.19
PrivAG | 1.09 | 1.15 | 1.08 | 0.98
AAG | 0.68 | 0.71 | 0.68 | 0.76
Porto | UG | 0.16 | 0.12 | 0.10 | 0.09
PrivAG | 0.77 | 0.76 | 0.71 | 0.71
AAG | 0.49 | 0.49 | 0.62 | 0.63
Foursquare | UG | 0.26 | 0.19 | 0.16 | 0.16
PrivAG | 0.69 | 0.63 | 0.75 | 0.69
AAG | 0.61 | 0.56 | 0.55 | 0.51

In both tables, we observe that as $\varepsilon$ increases, AQEs of UG
decrease. This is an intuitive result since higher $\varepsilon$ means less
perturbation caused by LDP, therefore results are more accurate. On the other
hand, although this trend holds for UG, it does not always hold for PrivAG and
AAG. For example, despite increasing $\varepsilon$, there are cases in PrivAG
and AAG in which AQE values increase. The reason is that, as shown in
Equations 4 and 5, $\varepsilon$ is used in the choice of $g_{1}$ and
$g_{2}^{k}$. Hence, changing $\varepsilon$ also changes the grid structures in
PrivAG and AAG. These structural changes may affect $ans^{\prime}_{q}$
positively or negatively, and LDP perturbation is no longer the only factor in
the accuracy of $ans^{\prime}_{q}$. Hence, we do not see a consistent trend
between $\varepsilon$ and AQE in PrivAG and AAG. On the other hand, this
observation shows that if the choices of $g_{1}$ and $g_{2}^{k}$ are made in a
more optimized fashion, especially in high $\varepsilon$ regions, there is
potential to improve utility. This can be a good avenue for future work.

Combining all experiment results, we arrive at the following take-away
messages: (i) AAG is preferable to PrivAG across all $\varepsilon$ and $\rho$,
(ii) AAG is the best approach when $\rho$ is small, e.g., for computing
answers to small queries or for detailed statistics, and (iii) UG is the best
approach when $\rho$ is large, e.g., for computing answers to large queries or
for coarse statistics.

##  5 Related Work

The rising popularity of LDP in recent years has led to growing interest in
its application to spatial data, given the widespread use of location-based
services (LBS) and the importance of protecting location privacy. Chen et al.
[2] proposed a variant of LDP called personalized LDP (PLDP), and developed
methods for spatial data aggregation under PLDP. Wang et al. [19] developed
L-SRR to enable LBS tasks while satisfying LDP. Hong et al. [13] studied the
problem of reducing the expected error of each perturbed location when
collecting location data with LDP. Kim et al. [15] and Navidan et al. [17]
applied LDP to indoor positioning. Cunningham et al. [6] proposed a mechanism
for trajectory sharing under LDP using n-grams, and Zhang et al. [25] proposed
a mechanism for trajectory perturbation using points’ adjacent direction
information to improve utility. Du et al. [8] proposed LDPTrace for
synthesizing realistic location trajectories under LDP, which utilizes a
uniform grid for discretization.

Hu et al. [14] studied the problem of continuously releasing location
statistics from streaming data while protecting privacy using $w$-event level
LDP. Alptekin and Gursoy [1] studied the problem of building quadtrees for
spatial data under LDP. Yao et al. [24] proposed a framework for collecting
users’ locations under LDP for Unmanned Aerial Vehicles (UAVs), utilizing a
quadtree-based approach. Most closely related to our work is the work of Yang
et al. [23], who studied the problem of collecting location trajectories under
LDP. For this problem, they developed an adaptive grid approach called PrivAG.
We experimentally show that our AAG improves PrivAG.

##  6 Conclusion

In this paper, we studied three grid-based decomposition approaches under LDP:
Uniform Grid (UG), PrivAG, and AAG. Our proposed AAG approach advances the
state-of-the-art adaptive grid approach (PrivAG) by performing cell divisions
according to neighboring cells’ densities. We experimentally compared UG,
PrivAG, and AAG using three datasets and multiple parameter values
($\varepsilon$ and $\rho$). We observed that AAG always beats PrivAG, and it
also beats UG when $\rho$ is small. However, when $\rho$ is large, UG with a
near-optimal choice of grid size becomes better than AAG. In future work, we
plan to compare these three grid approaches against tree-based decompositions.
Furthermore, we will investigate methods to improve PrivAG and AAG’s utility
especially in high $\varepsilon$ regimes.

## Acknowledgments

This study was supported by Scientific and Technological Research Council of
Türkiye (TUBITAK) under Grant Number 121E303. The authors thank TUBITAK for
their support.

## References

  * [1] Alptekin, E., Gursoy, M.E.: Building quadtrees for spatial data under local differential privacy. In: IFIP Annual Conference on Data and Applications Security and Privacy. pp. 22–39. Springer (2023)
  * [2] Chen, R., Li, H., Qin, A., Kasiviswanathan, S.P., Jin, H.: Private spatial data aggregation in the local setting. In: 2016 IEEE 32nd International Conference on Data Engineering (ICDE). pp. 289–300. IEEE (2016)
  * [3] Cho, E., Myers, S.A., Leskovec, J.: Friendship and mobility: user movement in location-based social networks. In: 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. pp. 1082–1090 (2011)
  * [4] Cormode, G., Jha, S., Kulkarni, T., Li, N., Srivastava, D., Wang, T.: Privacy at scale: Local differential privacy in practice. In: Proceedings of the 2018 International Conference on Management of Data. pp. 1655–1658. ACM (2018)
  * [5] Cormode, G., Maddock, S., Maple, C.: Frequency estimation under local differential privacy. Proceedings of the VLDB Endowment 14(11), 2046–2058 (2021)
  * [6] Cunningham, T., Cormode, G., Ferhatosmanoglu, H., Srivastava, D.: Real-world trajectory sharing with local differential privacy. Proceedings of the VLDB Endowment 14(11), 2283–2295 (2021)
  * [7] Ding, B., Kulkarni, J., Yekhanin, S.: Collecting telemetry data privately. In: Advances in Neural Information Processing Systems. pp. 3571–3580 (2017)
  * [8] Du, Y., Hu, Y., Zhang, Z., Fang, Z., Chen, L., Zheng, B., Gao, Y.: Ldptrace: Locally differentially private trajectory synthesis. Proceedings of the VLDB Endowment 16(8), 1897–1909 (2023)
  * [9] Erlingsson, Ú., Pihur, V., Korolova, A.: Rappor: Randomized aggregatable privacy-preserving ordinal response. In: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. pp. 1054–1067. ACM (2014)
  * [10] Gursoy, M.E., Liu, L., Chow, K.H., Truex, S., Wei, W.: An adversarial approach to protocol analysis and selection in local differential privacy. IEEE Transactions on Information Forensics and Security 17, 1785–1799 (2022)
  * [11] Gursoy, M.E., Liu, L., Truex, S., Yu, L.: Differentially private and utility preserving publication of trajectory data. IEEE Transactions on Mobile Computing 18(10), 2315–2329 (2018)
  * [12] Gursoy, M.E., Liu, L., Truex, S., Yu, L., Wei, W.: Utility-aware synthesis of differentially private and attack-resilient location traces. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. pp. 196–211 (2018)
  * [13] Hong, D., Jung, W., Shim, K.: Collecting geospatial data under local differential privacy with improving frequency estimation. IEEE Transactions on Knowledge and Data Engineering (2022)
  * [14] Hu, R., Li, H., Li, J., Wang, Z., Wang, B.: Continuous release of temporal correlation location statistics with local differential privacy. Multimedia Tools and Applications pp. 1–19 (2023)
  * [15] Kim, J.W., Kim, D.H., Jang, B.: Application of local differential privacy to collection of indoor positioning data. IEEE Access 6, 4276–4286 (2018)
  * [16] Moreira-Matias, L., Gama, J., Ferreira, M., Mendes-Moreira, J., Damas, L.: Predicting taxi–passenger demand using streaming data. IEEE Transactions on Intelligent Transportation Systems 14(3), 1393–1402 (2013)
  * [17] Navidan, H., Moghtadaiee, V., Nazaran, N., Alishahi, M.: Hide me behind the noise: Local differential privacy for indoor location privacy. In: 2022 IEEE European Symposium on Security and Privacy Workshops. pp. 514–523. IEEE (2022)
  * [18] Qardaji, W., Yang, W., Li, N.: Differentially private grids for geospatial data. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE). pp. 757–768. IEEE (2013)
  * [19] Wang, H., Hong, H., Xiong, L., Qin, Z., Hong, Y.: L-srr: Local differential privacy for location-based services with staircase randomized response. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. p. 2809–2823. Association for Computing Machinery, New York, NY, USA (2022)
  * [20] Wang, T., Blocki, J., Li, N., Jha, S.: Locally differentially private protocols for frequency estimation. In: Proc. of the 26th USENIX Security Symposium. pp. 729–745 (2017)
  * [21] Wang, T., Li, N., Jha, S.: Locally differentially private frequent itemset mining. In: IEEE Symposium on Security and Privacy (SP). IEEE (2018)
  * [22] Yang, D., Zhang, D., Zheng, V.W., Yu, Z.: Modeling user activity preference by leveraging user spatial temporal characteristics in lbsns. IEEE Transactions on Systems, Man, and Cybernetics: Systems 45(1), 129–142 (2014)
  * [23] Yang, J., Cheng, X., Su, S., Sun, H., Chen, C.: Collecting individual trajectories under local differential privacy. In: 2022 23rd IEEE International Conference on Mobile Data Management (MDM). pp. 99–108. IEEE (2022)
  * [24] Yao, A., Pal, S., Li, X., Zhang, Z., Dong, C., Jiang, F., Liu, X.: A privacy-preserving location data collection framework for intelligent systems in edge computing. Ad Hoc Networks 161, 103532 (2024)
  * [25] Zhang, Y., Ye, Q., Chen, R., Hu, H., Han, Q.: Trajectory data collection with local differential privacy. Proceedings of the VLDB Endowment 16(10), 2591–2604 (2023)


# Bethe Ansatz and Rogers-Ramanujan-type identities.

Sergey M. Sergeev

###### Abstract

The Rogers-Ramanujan identity for $\\!\\!\phantom{|}{}_{1}\psi_{1}$

$\sum_{n\in\mathbb{Z}}\frac{(a;q)_{n}}{(b;q)_{n}}z^{n}\;=\;\frac{(q,b/a,az,q/az;q)_{\infty}}{(b,q/a,z,b/az;q)_{\infty}}$

can be classified as one related to the Bethe Ansatz for “chain length $N=1$,
ground state XXZ model with an arbitrary negative spin”.

Department of Theoretical Physics, Research School of Physics and Engineering,
Australian National University, Canberra, ACT 0200, Australia
and
Faculty of Science and Technology,
University of Canberra, Bruce ACT 2617, Australia

In this note we observe some exotic way to produce the spectrum of auxiliary
transfer matrices for $\mathcal{U}_{q}(\widehat{sl}_{2})$ models. This way is
equivalent to the standard Bethe Ansatz, however it uses different variables.
As a by-product, the method is related to generalisations of the Rogers-
Ramanujan identity [1] mentioned in the Abstract. Note, we observe the Rogers-
Ramanujan identities of a type different from those obtained by Andrews,
Baxter and Forrester [2].

Our staring point is the Baxter’s equation,

$t(x)Q(x)\;=\;(1-\xi x)^{N}Q(qx)\>+\;\omega q^{S}(\xi-x)^{N}Q(x/q)\;,$ (1)

where $t(x)$ stands for the auxiliary transfer-matrix,

$t(x)\;=\;1+\omega
q^{S}\xi^{N}+t_{1}x+\cdots+t_{N-1}x^{N-1}+\;(\omega+q^{S}\xi^{N})(-x)^{N}\;,$
(2)

$N$ is the chain length, $S$ is “total spin”, $\omega$ is a field, and $Q(x)$
is a polynomial of degree $S$. Standard finite-dimensional case corresponds to
$\xi=q^{-j}$ where $j$ is a half-integer local spin. However, we assume here
another regime,

$\displaystyle|q|\;<\;1\;,\quad|\xi|\;<\;1\;.$ (3)

Lowest and highest terms of $t(x)$ as well the other terms in (1) come from
unessential details of properly defined $\mathcal{U}_{q}(\widehat{sl}_{2})$
$L$-operators. The Bethe-Ansatz equations

$(1-\xi x)^{N}Q(qx)\>+\;\omega
q^{S}(\xi-x)^{N}Q(x/q)\;=\;0\quad\textrm{on}\quad Q(x)\;=\;0\;,$ (4)

are regarded as a closed system of equations for $S$ zeros of $Q(x)$, solution
of (4) provides eigenvalue of $t(x)$.

However, equation (1) allows one to introduce different than $Q(x)$ objects.
Consider two more $TQ$-type equations,

$\left\\{\begin{array}[]{l}\displaystyle t(x)H(x)\;=\;H(x/q)\;+\;\omega
q^{S}(1-\xi x)^{N}(\xi-qx)^{N}H(qx)\;,\\\ \\\ \displaystyle
t^{\prime}(x)H^{\prime}(x)\;=\;H^{\prime}(qx)\;+\;\omega^{-1}q^{S}(1-\xi/x)^{N}(\xi-q/x)^{N}H^{\prime}(x/q)\;,\end{array}\right.$
(5)

where

$t^{\prime}(x)\;=\;t(x)/\omega(-x)^{N}\;,$ (6)

and

$H(x)\;=\;1+h_{1}x+h_{2}x^{2}+\cdots\;,\quad
H^{\prime}(x)\;=\;1+h_{1}^{\prime}/x+h_{2}^{\prime}/x^{2}+\cdots\;.$ (7)

For an arbitrary $t(x)$, $H$ and $H^{\prime}$ are the uniquely defined seria
convergent everywhere except $x=\infty$ and $x=0$ correspondingly. Moreover,
the functions $H$ and $H^{\prime}$ have the remarkable matrix product
representations. Let

$L(x)\;=\;\left(\begin{array}[]{cc}\displaystyle t(x)&-\gamma(x)\\\
\displaystyle 1&\displaystyle 0\end{array}\right)\;,\quad
L^{\prime}(x)\;=\;\left(\begin{array}[]{cc}\displaystyle
t^{\prime}(x)&\displaystyle 1\\\
\displaystyle-\gamma^{\prime}(x)&\displaystyle 0\end{array}\right)\;,$ (8)

where (see (5))

$\gamma(x)\;=\;\omega q^{S}(1-\xi x)^{N}(\xi-
qx)^{N}\;,\quad\gamma^{\prime}(x)\;=\;\omega^{-1}q^{S}(1-\xi/x)^{N}(\xi-q/x)^{N}\;.$
(9)

The following semi-infinite matrix products are well defined:

$L(x)L(qx)(q^{2}x)\cdots\;=\;\frac{1}{1-\omega
q^{S}\xi^{N}}\left(\begin{array}[]{c}\displaystyle H(x/q)\\\
H(x)\end{array}\right)\left(1,-\omega q^{S}\xi^{N}\right)\;,$ (10)

and

$\cdots
L^{\prime}(x/q^{2})L^{\prime}(x/q)L^{\prime}(x)\;=\;\frac{1}{1-\omega^{-1}q^{S}\xi^{N}}\left(\begin{array}[]{c}\displaystyle
1\\\
\displaystyle-\omega^{-1}q^{S}\xi^{N}\end{array}\right)\left(H^{\prime}(qx),H^{\prime}(x)\right)\;.$
(11)

Next, for general $t(x)$, the Wronskian of $H,H^{\prime}$,

$\Theta(x)\;=\;H^{\prime}(x)H(x/q)-q^{S}(\xi-x)^{N}(\xi-q/x)^{N}H^{\prime}(x/q)H(x)\;,$
(12)

satisfies

$\Theta(x)\;=\;\omega(-x)^{N}\Theta(qx)\;,$ (13)

so that the $\theta$-function expansion holds:

$\Theta(x)\;=\;\Theta_{0}\;\prod_{k=1}^{N}(x/z_{k};q)_{\infty}(qz_{k}/x;q)_{\infty}\;,\quad\prod_{k=1}z_{k}\;=\;\omega^{-1}\;.$
(14)

Matrix product representation allows one to write $\Theta(x)$ as a matrix
product infinite in both directions. The set of $\\{z_{k}\\}$ is the set of
variables alternative to the standard Bethe variables, i.e. to the set of
zeros of $Q(x)$. The real aim of this note is to reformulate the Bethe Ansatz
equations (4) in the terms of $\\{z_{k}\\}$.

To do this, let us assume (1) and compute the Wronskians of $H^{\\#}$ and $Q$:

$\left\\{\begin{array}[]{l}\displaystyle H(x/q)Q(x)-\omega
q^{S}(\xi-x)^{N}H(x)Q(x/q)\;=\;(1-\omega q^{S}\xi^{N})(\xi
x;q)_{\infty}^{N}\;,\\\ \\\ \displaystyle
H^{\prime}(x)Q^{\prime}(x/q)-\omega^{-1}q^{S}(\xi-q/x)^{N}H^{\prime}(x/q)Q^{\prime}(x)\;=\;\kappa(1-\omega^{-1}q^{S}\xi^{N})(q\xi/x;q)_{\infty}^{N}\;,\end{array}\right.$
(15)

where $Q(0)=1$, $Q^{\prime}(x)\;=\;Q(x)/x^{S}$ and
$\kappa=Q^{\prime}(\infty)$. Consequence of (15) is

$Q(x)\;=\;(1-\omega q^{S}\xi^{N})\frac{H^{\prime}(x)(\xi
x;q)_{\infty}^{N}}{\Theta(x)}+\kappa
x^{S}(1-\omega^{-1}q^{S}\xi^{N})\frac{H(x)(\xi/x;q)_{\infty}^{N}}{\Theta(qx)}\;.$
(16)

Thus we obtain the quantisation condition equivalent to the initial Bethe-
Ansatz equations (4). Namely, for given arbitrary $t(x)$, one computes
$H^{\\#}(x)$ and therefore $\\{z_{k}\\}$. Then, the spectral equations,
alternative but equivalent to (4), are

$H^{\prime}(x)(\xi
x;q)_{\infty}^{N}+\kappa^{\prime}x^{S}(-x)^{N}H(x)(\xi/x;q)_{\infty}^{N}\;=\;0\quad\textrm{on}\quad
x\in\\{z_{k}\\}\;,$ (17)

where $\kappa^{\prime}$ in this approach is an extra parameter, i.e. in fact
the number of equations in (17) is $N-1$ in accordance to the number of
independent $\\{z_{k}\\}$, $\prod z_{k}=\omega^{-1}$.

Note that for the case of the modular double and quantum dilogarithms, when
polynomial $Q(x)$ is undefined, equations of the type (17) play the role of
the major spectral equations, see [3, 4, 5, 6].

Now suppose that all spectral equations are solved, i.e. (4) or (17) are
satisfied, and equation (16) becomes an identity. Equations (15) can be solved
with respect to $H^{\\#}$,

$H(x/q)\;=\;(1-\omega q^{S}\xi^{N})Q(x/q)(\xi
x;q)_{\infty}^{N}\sum_{n=0}^{\infty}\frac{\displaystyle(\omega
q^{S}\xi^{N})^{n}}{Q(q^{n-1}x)Q(q^{n}x)}\frac{(x/\xi;q)_{n}^{N}}{(\xi
x;q)_{n}^{N}}\;,$ (18)

and

$H^{\prime}(qx)\;=\;\kappa(1-\omega^{-1}q^{S}\xi^{N})Q^{\prime}(qx)(\xi/x;q)_{\infty}^{N}\sum_{n=0}^{\infty}\frac{\displaystyle(\omega^{-1}q^{S}\xi^{N})^{n}}{Q^{\prime}(q^{n+1}x)Q^{\prime}(q^{n}x)}\frac{(1/\xi
x;q)_{n}^{N}}{(\xi/x;q)_{n}^{N}}\;.$ (19)

Using this, one can bring the identity (16) to the form

$\sum_{n\in\mathbb{Z}}\frac{\displaystyle(\omega
q^{S}\xi^{N})^{n}}{Q(q^{n-1}x)Q(q^{n}x)}\frac{(x/\xi;q)_{n}^{N}}{(\xi
x;q)_{n}^{N}}\;=\;\frac{(q/x)^{S}}{\kappa(1-\omega
q^{S}\xi^{N})(1-\omega^{-1}q^{S}\xi^{N})}\;\frac{\displaystyle\Theta(x)}{\displaystyle(\xi
x;q)_{\infty}^{N}(q\xi/x;q)_{\infty}^{N}}\;.$ (20)

In particular, in the case $N=1$ and $S=0$, $Q(x)=1$, equation (20) becomes
the Rogers-Ramanujan identity mentioned in the Appendix (we did not discuss
the normalisation constant $\Theta_{0}$).

Relation (20) is a particular case of more general one,

$\psi(x)\;\stackrel{{\scriptstyle
def}}{{=}}\;\sum_{n}z^{n}f(q^{n}x)\prod_{k=1}^{N}\frac{\displaystyle(x/a_{k};q)_{n}}{\displaystyle(x/b_{k};q)_{n}}\;=\;\frac{\displaystyle
W(x)}{\displaystyle\prod_{k=1}^{N}(x/b_{k};q)_{\infty}(qa_{k}/x;q)_{\infty}}\;,$
(21)

where, since

$\psi(x)\;=\;z\prod_{k=1}^{N}\frac{(1-x/a_{k})}{(1-x/b_{k})}\;\psi(qx)\;,$
(22)

function $W(x)$ satisfies

$W(x)\;=\;z\frac{(-x)^{N}}{\prod_{k}a_{k}}\;W(qx)\;.$ (23)

This note gives an example of way how to avoid extra poles of $f(x)$ in (21),
what is the Bethe Ansatz equations (4), so that $W(x)$ becomes a theta-
function, and clarifies the structure of this theta-function.

Acknowledgement. I would like to thank Vladimir Bazhanov and Vladimir
Mangazeev for valuable discussions. Also I acknowledge the support of the
Australian Research Council grant DP190103144.

## References

  * [1] G. Gasper and M. Rahman, M.  Basic Hypergeometric Series (2nd ed., Encyclopedia of Mathematics and its Applications).  Cambridge University Press, 2004.
  * [2] G. E. Andrews, R. J. Baxter and P. J. Forrester.  Eight-vertex SOS model and generalised Rogers-Ramanujan-type identities.  Journal of Statistical Physics, Vol 35, pages 193-266, 1884.
  * [3] S. Sergeev.  Quantization scheme for modular $q$-difference equations.  Theoretical and Mathematical Physics, Vol 142(3), pages 422-430, 2005.
  * [4] R. Kashaev and S. Sergeev.  Spectral equations for the modular oscillator.  Reviews in Mathematical Physics, Vol 30(07), page1840009, 2018.
  * [5] R. Kashaev and S. Sergeev.  On the spectrum of the local ${\mathbb{P}}^{2}$ mirror curve.  Annales Henri Poincare, Vol 21(11), pages 3479-3497, 2020.
  * [6] O. Babelon, K. K. Kozlowski, and V. Pasquier.  Baxter operator and Baxter equation for $q$-Toda and Toda2 chains.  Reviews in Mathematical Physics, Vol 30(06), page 1840003, 2018.