11institutetext: Department of Mathematics and Statistics, University of
Turku, Finland 22institutetext: Department of Computing, University of Turku,
Finland
22email<EMAIL_ADDRESS>
# Asymptotic utility of spectral anonymization

Katariina Perkonoja 1122 0000-0002-3812-0871 Joni Virta 11 0000-0002-2150-2769

###### Abstract

In the contemporary data landscape characterized by multi-source data
collection and third-party sharing, ensuring individual privacy stands as a
critical concern. While various anonymization methods exist, their utility
preservation and privacy guarantees remain challenging to quantify. In this
work, we address this gap by studying the utility and privacy of the spectral
anonymization (SA) algorithm, particularly in an asymptotic framework. Unlike
conventional anonymization methods that directly modify the original data, SA
operates by perturbing the data in a spectral basis and subsequently reverting
them to their original basis. Alongside the original version $\mathcal{P}$-SA,
employing random permutation transformation, we introduce two novel SA
variants: $\mathcal{J}$-spectral anonymization and $\mathcal{O}$-spectral
anonymization, which employ sign-change and orthogonal matrix transformations,
respectively. We show how well, under some practical assumptions, these SA
algorithms preserve the first and second moments of the original data. Our
results reveal, in particular, that the asymptotic efficiency of all three SA
algorithms in covariance estimation is exactly 50% when compared to the
original data. To assess the applicability of these asymptotic results in
practice, we conduct a simulation study with finite data and also evaluate the
privacy protection offered by these algorithms using distance-based record
linkage. Our research reveals that while no method exhibits clear superiority
in finite-sample utility, $\mathcal{O}$-SA distinguishes itself for its
exceptional privacy preservation, never producing identical records, albeit
with increased computational complexity. Conversely, $\mathcal{P}$-SA emerges
as a computationally efficient alternative, demonstrating unmatched efficiency
in mean estimation.

###### Keywords:

Anonymization Limiting distribution Privacy protection Singular value
decomposition Utility

##  1 Introduction

Various anonymization techniques and privacy protocols, such as $k$-anonymity
[16], $l$-diversity [11], $t$-closeness [12], and differential privacy [6],
have been proposed to protect data privacy. While these tools are conceptually
simple, their deeper mathematical properties are often intractable, meaning
that the related anonymization methods generally lack proven theoretical
guarantees, particularly regarding utility preservation, although some
attempts have been made, see, e.g., [5, 19, 1, 14]. As a result, decision-
makers encounter uncertainty when determining acceptable privacy thresholds
for data disclosure, compounded by the trade-off between privacy and utility.
Therefore, there exists a pressing need for theoretical results addressing the
utility preservation of anonymization techniques, alongside their privacy
guarantees.

In this work we study the utility and privacy of the spectral anonymization
(SA) algorithm of Lasko and Vinterbo [10] in the asymptotic framework where
the sample size of $n$ of the observed data grows without bounds. Given an
observed data matrix $X_{n}\in\mathbb{R}^{n\times p}$ with $n$ observations of
$p$ variables, SA anonymizes it as follows: Letting
$H_{n}:=I_{n}-(1/n)1_{n}1_{n}^{\prime}$ be the $n\times n$ centering matrix,
we first find the singular value decompostion (SVD) of the centered data
$H_{n}X_{n}=U_{n}D_{n}V_{n}^{\prime}$, where the matrix of left singular
vectors is $U_{n}=(u_{n1}\mid\cdots\mid u_{np})\in\mathbb{R}^{n\times p}$.
Note that the subscript $n$ in all quantities serves to remind that our
viewpoint is asymptotic (i.e., $n\rightarrow\infty$) and that we are in fact
dealing with sequences of data matrices ($X_{1},X_{2},\ldots$). Let then
$P_{n1},\ldots,P_{np}\in\mathbb{R}^{n\times n}$ be i.i.d. random permutation
matrices sampled uniformly from the set $\mathcal{P}_{n}$ of all $n\times n$
permutation matrices. Denoting by $U_{n0}:=(P_{n1}u_{n1}\mid\cdots\mid
P_{np}u_{np})$ the matrix of permuted singular vectors, the spectral
anonymization of $X_{n}$ is

$\displaystyle
X_{n,\mathcal{P}}=U_{n0}D_{n}V_{n}^{\prime}+1_{n}\bar{x}_{n}^{\prime},$ (1)

where $\bar{x}_{n}:=(1/n)X_{n}^{\prime}1_{n}$. Note that each column of
$U_{n}$ is permuted independently, meaning that $U_{n0}$ is not, in general, a
simple row permutation of $U_{n}$. Intuitively, SA uses a very simple form or
perturbation (permuting observations), which by itself would not guarantee
anonymity, but since it is applied in another basis (given by the right
singular vectors $V_{n}$), anonymity in the original basis is reached.
Technically, any basis could be used, but the spectral basis given by the SVD
is particularly appealing as the matrix $U_{n}$ has uncorrelated columns,
implying that, after returning to the original basis, the anonymized data has
approximately the same first and second moments as the original data. As
argued also by [10], since many standard statistical methods, such as
regression, discriminant analysis, support vector machines, $k$-means
clustering, etc., are based on means and correlations, this preservation of
resemblance (moments) can be seen, more or less, as equivalent to the
preservation of general data utility.

While permuting is possibly the most direct form of perturbation one can apply
in the spectral basis, it is not the only option, and as our first main
contribution, we propose two novel forms of SA, called $\mathcal{J}$-spectral
anonymization and $\mathcal{O}$-spectral anonymization. The original SA
defined in (1) will in the sequel be denoted as $\mathcal{P}$-SA, to
distinguish it from these variants. In $\mathcal{J}$-SA, the transformation
matrices used to perturb $U_{n}$ are drawn uniformly from the set
$\mathcal{J}_{n}$ of all $n\times n$ sign-change matrices (diagonal matrices
with diagonal elements $\pm 1$) and in $\mathcal{O}$-SA these matrices are
drawn from the Haar uniform distribution on the set $\mathcal{O}_{n}$ of all
$n\times n$ orthogonal matrices [15]. The resulting spectral anonymizations of
$X_{n}$ are denoted by $X_{n,\mathcal{J}}$ and $X_{n,\mathcal{O}}$,
respectively. Figure 1 illustrates the effect of the three perturbations in a
simple bivariate scenario.

Figure 1: Illustration of the effects of $\mathcal{P}$-SA (blue),
$\mathcal{J}$-SA (orange) and $\mathcal{O}$-SA (purple) to the original data
(green), with numerical labels corresponding to the row indices of original
data, in a scenario with $n=10$ and $p=2$. $\mathcal{P}$-SA and
$\mathcal{J}$-SA occasionally result in unwanted overlap, wherein a row in the
anonymized data matches another row in the original dataset. In the case of
$\mathcal{J}$-SA, this occurrence is due to coincidental alignment of signs
with those in the original singular vectors, causing the observation to be
duplicated (overlap of same indices), whereas for $\mathcal{P}$-SA, random
permutation of values may cause another row to align with one in the original
dataset (overlap of different indices). Conversely, $\mathcal{O}$-SA induces
arbitrary rotations in the spectral space that prevent exact matches
altogether with probability 1.

As our second main contribution, we investigate the earlier observation,
stated also by Lasko and Vinterbo [10], that $\mathcal{P}$-SA approximately
preserves the means, variances, covariances, and linear correlations of the
original data $X_{n}$. In this work, we quantify this statement in an
asymptotic framework, working, for simplicity, under the assumption that the
rows of $X_{n}$ are sampled i.i.d. from the normal distribution
$\mathcal{N}_{p}(\mu,\Sigma)$ for some fixed $\mu\in\mathbb{R}^{p}$ and
positive definite covariance matrix $\Sigma$. Extensions to other
distributional assumptions are investigated through simulations in Section 3
and discussed further in Section 4. As the multivariate normal distribution is
entirely determined by its means and covariances, evaluating the resemblance
of anonymized data with respect to these moments is equivalent to assessing
general data utility in the present scenario.

As our third main contribution, we conduct a simulation study that
investigates how well the three forms of SA preserve utility and privacy under
a wide range of data scenarios and sample sizes. We are not aware of an
equally extensive benchmarking study having been carried out for the original
SA of [10], although [9] compared the prediction utility of SA to that of a
private Bayesian factor model. Also, closely related to this, [3] conducted a
simulation study assessing utility loss when anonymizing data using another
form of spectral anonymization based on factor analysis and principal
component analysis.

In Section 2 we present our results on the asymptotic utility of the three
forms of SA. The corresponding finite-sample behavior is studied using
simulations in Section 3.1, whereas finite-sample privacy preservation is
investigated in Section 3.2. In Section 4 we conclude with discussion. The
proofs are presented in Appendix 0.A and Appendix 0.B contains additional
simulation figures.

##  2 Asymptotic utility

We divide our theoretical results in two parts, investigating first how well
the SA-methods preserve the first moment (mean vector) and then doing the same
for the second moment (covariance matrix). Recall from Section 1 that we
assume the rows of $X_{n}$ to be i.i.d. from $\mathcal{N}_{p}(\mu,\Sigma)$.
Throughout this section we impose the following technical condition on the
covariance matrix $\Sigma$, which guarantees that the singular spaces of
$H_{n}X_{n}$ are asymptotically identifiable up to sign. This assumption is
mild and practically always satisfied for continuous real data.

###### Assumption 1

The eigenvalues of $\Sigma$ are distinct.

The classical central limit theorem gives for $\bar{x}_{n}$ (the mean of the
original data) the following limiting distribution as $n\rightarrow\infty$:

$\displaystyle\sqrt{n}(\bar{x}_{n}-\mu)\rightsquigarrow\mathcal{N}_{p}(0,\Sigma),$

where $\rightsquigarrow$ denotes convergence in distribution. As our first
result in this section, we derive the limiting distributions of the sample
means
$\bar{x}_{n,\mathcal{P}},\bar{x}_{n,\mathcal{J}},\bar{x}_{n,\mathcal{O}}$ of
the different spectral anonymzations of $X_{n}$.

###### Theorem 2.1

Under Assumption 1, we have the following, as $n\rightarrow\infty$.

$\displaystyle\sqrt{n}(\bar{x}_{n,\mathcal{P}}-\mu)=\sqrt{n}(\bar{x}_{n}-\mu)$
$\displaystyle\rightsquigarrow\mathcal{N}_{p}(0,\Sigma)$
$\displaystyle\sqrt{n}(\bar{x}_{n,\mathcal{J}}-\mu)$
$\displaystyle\rightsquigarrow\mathcal{N}_{p}(0,2\Sigma)$
$\displaystyle\sqrt{n}(\bar{x}_{n,\mathcal{O}}-\mu)$
$\displaystyle\rightsquigarrow\mathcal{N}_{p}(0,2\Sigma)$

Two estimators of the same parameter can be compared based on the “magnitudes”
of their limiting covariance matrices (“smaller” covariance matrix implies
more accurate estimator). Thus, Theorem 2.1 shows that $\mathcal{P}$-SA yields
mean estimation efficiency equivalent to the original data (in fact, the two
estimators are always exactly the same). Whereas $\mathcal{J}$-SA and
$\mathcal{O}$-SA incur a cost in efficiency. Interestingly, this extra cost
has a very simple form and the asymptotic efficiency of these two methods
compared to mean estimation from the original data turn out to be exactly one
half (due to the factor 2 in front of $\Sigma$).

We next conduct an analogous study of covariance matrix estimation. We denote
the sample covariance matrices produced by the three forms of SA as
$S_{n,\mathcal{P}},S_{n,\mathcal{J}},S_{n,\mathcal{O}}$. As a baseline,
Theorem 1 in [17], shows that the limiting distribution of $S_{n}$, the sample
covariance matrix of the original data, is

$\displaystyle\sqrt{n}\mathrm{vec}(S_{n}-\Sigma)\rightsquigarrow\mathcal{N}_{p^{2}}(0,(\Sigma^{1/2}\otimes\Sigma^{1/2})(I_{p^{2}}+K_{p,p})(\Sigma^{1/2}\otimes\Sigma^{1/2})^{\prime}),$

where $\mathrm{vec}(\cdot)$ denotes column-wise vectorization, $\otimes$ is
the Kronecker product, $K_{p,p}$ is the $(p,p)$-commutation matrix [8] and the
square root matrix $\Sigma^{1/2}:=O\Lambda^{1/2}$ is computed using the
eigendecomposition $\Sigma=O\Lambda O^{\prime}$.

###### Theorem 2.2

Under Assumption 1, we have for
$\mathcal{A}\in\\{\mathcal{P},\mathcal{J},\mathcal{O}\\}$ the following, as
$n\rightarrow\infty$.

$\displaystyle\sqrt{n}\mathrm{vec}(S_{n,\mathcal{A}}-\Sigma)\rightsquigarrow\mathcal{N}_{p^{2}}(0,(\Sigma^{1/2}\otimes\Sigma^{1/2})(2I_{p^{2}}+2K_{p,p}-2V_{p})(\Sigma^{1/2}\otimes\Sigma^{1/2})^{\prime}),$

where $V_{p}:=\mathrm{diag}\\{\mathrm{vec}(I_{p})\\}$.

Theorem 2.2 offers us two insights: (a) All three forms of SA are equally
efficient in covariance estimation. (b) Assume next that $O=I_{p}$ in the
eigendecomposition $\Sigma=O\Lambda O^{\prime}$ (since the rotation $O$ only
fixes the coordinate system in which the data are observed, this choice does
not limit our interpretations). Then, for instance when $p=2$, the limiting
covariance matrices of $S_{n}$ and $S_{n,\mathcal{A}}$ take the forms:

$\displaystyle\begin{pmatrix}2\lambda_{1}^{2}&0&0&0\\\
0&\lambda_{1}\lambda_{2}&\lambda_{1}\lambda_{2}&0\\\
0&\lambda_{1}\lambda_{2}&\lambda_{1}\lambda_{2}&0\\\
0&0&0&2\lambda_{2}^{2}\end{pmatrix}\quad\mbox{and}\quad\begin{pmatrix}2\lambda_{1}^{2}&0&0&0\\\
0&2\lambda_{1}\lambda_{2}&2\lambda_{1}\lambda_{2}&0\\\
0&2\lambda_{1}\lambda_{2}&2\lambda_{1}\lambda_{2}&0\\\
0&0&0&2\lambda_{2}^{2}\end{pmatrix},$ (2)

respectively, where $\lambda_{1},\lambda_{2}$ are the marginal variances of
the data. We observe that the elements $(1,1),(4,4)$, giving the asymptotic
variances of the sample variances, are equal in the two matrices, meaning that
the estimation of variances is equally efficient in original data and in SA-
generated data. Whereas, the elements $(2,2),(2,3),(3,2),(3,3)$ in the
matrices (2), corresponding to the asymptotic variances and covariances of the
sample covariances are two times larger for SA than for the original data.
Thus, we conclude that SA makes the estimation of the cross-terms in the
covariance matrix $\Sigma$ more difficult. This is entirely natural
considering that each column of $U_{n}$ is in SA mixed independently of each
other, compromising our ability to detect interactions (sample covariances)
between the columns, but leaving the marginal distribution (sample variances)
of each column intact. For arbitrary rotation $O$, the equivalent
interpretation holds, only this time in the coordinate system specified by
$O$.

##  3 Simulations

To complement the earlier asymptotic results, in this section we study the
finite-sample utility of $\mathcal{P}$-SA, $\mathcal{J}$-SA and
$\mathcal{O}$-SA through a simulation study. As discussed in Section 2,
achieving the exact limiting distribution necessitates an infinite sample
size. Therefore, our focus in Section 3.1 is to evaluate how good of an
approximation the limiting distribution is for finite sample sizes. Rather
than directly comparing empirical distributions to the limiting distribution,
we examine the similarity between the empirical covariance matrices and their
limiting counterparts. Moreover, since $\mathcal{P}$-SA, $\mathcal{J}$-SA and
$\mathcal{O}$-SA are designed for data anonymization, we evaluate their
capability in protecting privacy in Section 3.2 by employing distance-based
record linkage. The source code used for conducting the simulation study
presented in this work is available on GitLab
https://gitlab.utu.fi/kakype/asymptotic-utility-of-spectral-anonymization.git.

Figure 2: The relative error of the empirical covariance matrices of sample
mean (solid line) and sample covariance (dotted line) compared to their
asymptotic covariance matrices for $\mathcal{P}$-SA (blue), $\mathcal{J}$-SA
(orange), and $\mathcal{O}$-SA (purple), when original data (green) is sampled
from a normal distribution meeting the Assumption 1. Sample size is presented
on a logarithmic scale.

###  3.1 Finite-sample utility

We explore the impact of finite data on convergence, considering sample sizes
$n=\\{25,50,100,200,400,800,1600\\}$ and number of variables $p=\\{2,3,6\\}$,
reflecting plausible real-world scenarios. For each combination of $n$ and
$p$, we sample original data $X_{n1}$ from $\mathcal{N}_{p}(\mu,\Sigma)$,
where $\mu=(3,3,\dots,3)\in\mathbb{R}^{p}$ and $\Sigma$ represents a diagonal
matrix with elements $(p,p-1,\dots,1)$ to fulfill Assumption 1. Additionally,
we explore the consequences of deviating from normality and Assumption 1 by
generating three alternative datasets: $X_{n2}$, $X_{n3}$ and $X_{n4}$, whose
rows are sampled i.i.d. from $\mathcal{N}_{p}(\mu,I_{p})$,
$Poisson(\lambda_{1})$ and $Poisson(\lambda_{2})$, respectively, where
$\lambda_{1}=(p,p-1,\dots,1)$, $\lambda_{2}=(1,1,\dots,1)\in\mathbb{R}^{p}$
and $Poisson(c)$ denotes a distribution with indepedent
$Poisson(c_{k})$-distributed marginals. Note that, by the equivariance
properties of the mean and covariance matrix, restricting our attention to
data with uncorrelated variables is without loss of generality.

Each dataset was sampled $M=10000$ times and anonymized using
$\mathcal{P}$-SA, $\mathcal{J}$-SA and $\mathcal{O}$-SA, respectively.
However, due to the $O(n^{3})$ complexity of $\mathcal{O}$-SA, we opted to
perform this form of anonymization only for sample sizes $n\leq 400$.
Subsequently, empirical values were computed according to the left-hand sides
of Theorems 2.1 and 2.2 and the relative errors (RE) of their covariance
matrices across the $M$ datasets were then calculated. By our theoretical
results, these values approach zero as $n\rightarrow\infty$. For instance, in
the case of sample mean (Theorem 2.1) and $\mathcal{P}$-SA, the calculated
value is

$\text{RE}_{\bar{x}_{n,\mathcal{P}}}=\frac{\|\widehat{Cov}_{M}(\sqrt{n}(\bar{x}_{n,\mathcal{P}}-\mu))-\Sigma\|_{F}}{\|\Sigma\|_{F}},$

where $\mu$ and $\Sigma$ are the mean and covariance parameters derived from
the aforementioned data distributions, and $\|\cdot\|_{F}$ represents the
Frobenius norm. Figures 2 and 3 illustrate the results for normally
distributed data, with corresponding representations for Poisson distribution
found in Appendix 0.B.

As predicted by Theorems 2.1 and 2.2, all curves in Figure 2 approach zero
when $n$ grows (notably, even with small sample sizes, the convergence for the
sample mean is eminent). There are no discernible differences in the
convergence among $\mathcal{P}$-SA, $\mathcal{J}$-SA, and $\mathcal{O}$-SA
towards their asymptotic covariance matrices. The relative error for the
sample covariance depends on $p$, higher dimensions requiring a larger sample
size for the RE to converge. When Assumption 1 is violated, Figure 3 indicates
that the empirical covariance matrix of the sample covariance matrix converges
to a different constant than outlined in Theorem 2.2. This implies that
Assumption 1 is necessary for our results to hold. Similar results were
obtained regarding deviation from the normality assumption (Appendix 0.B),
where the sample covariance curves, even for the original data, failed to
converge to zero. Hence, the results in Section 2 are not guaranteed to hold
if the normality assumption is discarded, see Section 4 for further discussion
of this point.

Figure 3: The relative error of the empirical covariance matrices of sample
mean (solid line) and sample covariance (dotted line) compared to their
asymptotic covariance matrices for $\mathcal{P}$-SA (blue), $\mathcal{J}$-SA
(orange), and $\mathcal{O}$-SA (purple), when original data (green) is sampled
from a normal distribution violating the Assumption 1. Sample size is
presented on a logarithmic scale.

###  3.2 Privacy

In addition to assessing empirical convergence with finite data, we wanted to
evaluate the privacy provided by $\mathcal{P}$-SA, $\mathcal{J}$-SA and
$\mathcal{O}$-SA. We used distance-based record linkage, akin to the approach
outlined in [4], with the distinction that all variables were utilized to
compute the shortest Euclidean distance (EUC) between an anonymized record and
any original record. The mean distance across all $m=1,\dots,M$ simulated
datasets was then calculated as follows:

$\text{EUC}_{\mathcal{A}}=\frac{1}{M}\sum_{m=1}^{M}\frac{1}{n}\sum_{i=1}^{n}\min_{j}\|x_{(m),i,\mathcal{A}}-x_{(m),j}\|_{2},$

where $x_{(m),i,\mathcal{A}}$ denotes the $i$th observation vector in the
$m$th anonymized data and $x_{(m),i}$ denotes the equivalent for the $m$th
original data. The distances were computed to the unstandardized data,
aligning with the common practice of publishing datasets in their original
scale. This anticipates potential linkage attempts by adversaries with
external data sources. $\text{EUC}_{\mathcal{A}}$ embodies the privacy-utility
trade-off, where values closer to zero indicate better utility to the original
data but also imply higher privacy risk, with a distance of zero denoting
essentially identical datasets. Consequently, higher values signify stronger
privacy protection. Results of this comparison for normally distributed data
meeting Assumption 1 are depicted in Figure 4.

Figure 4: $\text{EUC}_{\mathcal{A}}$ when the original data is sampled from
normal distribution meeting Assumption 1. The y-axis illustrates the mean
distance $\text{EUC}_{\mathcal{A}}$ between records in anonymized data and any
record in the original data across all datasets, while the x-axis denotes the
sample size on a logarithmic scale. The number of variables $p$ is
distinguished by different linetypes and each anonymization approach is
represented by a unique color.

While all SAs demonstrated comparable performance, $\mathcal{O}$-SA exhibited
the best privacy protection, consistently yielding higher distances compared
to $\mathcal{P}$-SA and $\mathcal{J}$-SA, as illustrated in Figure 4. These
findings remained consistent across all simulation settings (results not
shown). However, $\text{EUC}_{\mathcal{A}}$ is never precisely zero, as this
would imply essentially complete equivalence between the anonymized and
original data, which is highly unlikely for the given SAs. Yet, these
algorithms can produce some matches by chance, as demonstrated in Figure 1,
and for any individual, a direct match would constitute a privacy violation.
Therefore, we supplemented our analysis by evaluating the proportion of
matches, i.e., correctly linked records, relative to the sample size across
all simulated datasets $m=1,\dots,M$:

$\text{Matches}_{m,\mathcal{A}}=\frac{1}{n}\sum_{i=1}^{n}\begin{cases}1&\text{if
}\min_{j}\|x_{(m),i,\mathcal{A}}-x_{(m),j}\|_{2}<\delta,\\\
0&\text{otherwise},\end{cases}$

where the tolerance $\delta$ was set to $10^{-6}$. Results for normally
distributed data meeting Assumption 1 are presented in Figure 5, with a lower
proportion indicating better privacy protection (fewer matches).

Figure 5: Histograms of match proportions when the original data is sampled
from normal distribution meeting Assumption 1. The y-axis represents the
number of simulated datasets while the x-axis indicates the proportion of
matches relative to the sample size, with different SAs represented by
distinct colors. Sample sizes $n>400$ have been omitted here, as they
introduce no new information.

$\mathcal{O}$-SA did not produce any matches, as illustrated in Figure 5, with
a proportion of zero observed across all datasets. Conversely, both
$\mathcal{P}$-SA and $\mathcal{J}$-SA approaches resulted in matches, with the
former indicating a lower frequency compared to the latter. However, as $p$
increased, the number of matches decreased, ultimately leading to no matches
for $\mathcal{P}$-SA and approximately rate of 0.03 for $\mathcal{J}$-SA. This
trend remained consistent across all simulation scenarios, with the Poisson
distribution exhibiting slightly higher match proportion than the normal
distribution, and deviations from Assumption 1 having only a marginal effect
(results not shown).

##  4 Conclusion

Based on our findings with finite data, none of the three methods demonstrated
clear superiority in utility convergence. However, concerning privacy,
$\mathcal{O}$-SA outperformed $\mathcal{P}$-SA and $\mathcal{J}$-SA by never
generating identical records. Hence, we advocate for employing
$\mathcal{O}$-SA for data anonymization, notwithstanding its computational
intensity compared to $\mathcal{P}$-SA and $\mathcal{J}$-SA. For a dataset
size of $n=1000$ and $p=6$, the runtime for $\mathcal{O}$-SA is on average
2.44 seconds, while for $\mathcal{P}$-SA and $\mathcal{J}$-SA, it is 0.002 and
0.001 seconds, respectively (using AMD Ryzen 5 5600X). In practical scenarios,
data anonymization is typically a one-time operation, mitigating concerns over
computational overhead. However, should computational efficiency become
paramount, $\mathcal{P}$-SA emerges as the secondary choice, demonstrating no
matches in our simulations with $p=6$. In case privacy is given secondary
priority, then $\mathcal{P}$-SA offers superior mean estimation efficiency to
its two competitors (Theorem 2.1) and should be used. Nonetheless, further
research is warranted to evaluate these SA algorithms using empirical real-
world data and utility scenarios.

We conclude with comments regarding our assumptions. Our simulations revealed
that Assumption 1 cannot be dispensed with and, indeed, it is relied upon
extensively in our proof techniques in Appendix 0.A. And while the case of
$\Sigma$ having eigenvalues with multiplicity greater than one has no
practical importance, studying also this case would nevertheless complete the
theoretical story behind the method. Application to Poisson-distributed data
revealed that our results do not directly extend outside of normality, which
is to be expected as, again, our proofs use this fact in several places.
However, it might be that the results continue to hold if the normal
distribution is replaced with another distribution that has the same moment
sequence up to a certain moment. This behavior is known as universality in
high-dimensional statistics [7] and we leave its study in the current context
for future work.

####  4.0.1 Acknowledgements

The study was supported by the Finnish Cultural Foundation (grant 00220801)
and the Research Council of Finland (grants 347501 and 353769).

####  4.0.2

The authors have no competing interests to declare that are relevant to the
content of this article.

##  Appendix 0.A Proofs of technical results

######  Proof (Proof of Theorem 2.1)

We begin with the $\mathcal{P}$-SA. Denoting $Y_{n}:=X_{n,\mathcal{P}}$, we
have
$\bar{y}_{n}=\frac{1}{n}Y_{n}^{\prime}1_{n}=\frac{1}{n}V_{n}D_{n}U_{n0}^{\prime}1_{n}+\bar{x}_{n}$.
Observing now that $U_{n0}^{\prime}1_{n}=U_{n}^{\prime}1_{n}$ and that
$V_{n}D_{n}U_{n}^{\prime}1_{n}=0$, the desired result follows from the central
limit theorem.

For the $\mathcal{J}$-SA, we first consider the case where the data come from
$\mathcal{N}_{p}(0,\Lambda)$ for some diagonal matrix $\Lambda$ with strictly
positive and mutually distinct diagonal elements. We then write

$\displaystyle\sqrt{n}\bar{y}_{n}=\frac{1}{\sqrt{n}}Y_{n}^{\prime}1_{n}=\frac{1}{\sqrt{n}}V_{n}D_{n}U_{n0}^{\prime}1_{n}+\sqrt{n}\bar{x}_{n}.$
(3)

Now, the $k$th element of $D_{n}U_{n0}^{\prime}1_{n}$ equals

$\displaystyle
d_{nk}u_{nk}^{\prime}J_{nk}1_{n}=e_{k}^{\prime}D_{n}U_{n}^{\prime}J_{nk}1_{n}=e_{k}^{\prime}V_{n}^{\prime}X_{n}^{\prime}H_{n}J_{nk}1_{n}.$
(4)

We next show that $X_{n}^{\prime}H_{n}J_{nk}1_{n}/\sqrt{n}$ admits a limiting
distribution and is, as such, stochastically bounded. To see this, we let the
$i$th diagonal element of $J_{nk}$ be $s_{n,i}\sim\mathrm{Uniform}\\{-1,1\\}$
and write
$\frac{1}{\sqrt{n}}X_{n}^{\prime}H_{n}J_{nk}1_{n}=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}x_{n,i}s_{n,i}-\sqrt{n}\bar{x}_{n}\frac{1}{n}\sum_{i=1}^{n}s_{n,i}$.
Now, the first term has a limiting distribution (by CLT) and the second term
is $o_{p}(1)$ (by CLT and Slutsky’s lemma). Thus, fixing the sign of $V_{n}$
such that $V_{n}\rightarrow_{p}I_{p}$, we have, by (4) that
$\frac{1}{\sqrt{n}}d_{nk}u_{nk}^{\prime}J_{nk}1_{n}=\frac{1}{\sqrt{n}}e_{k}^{\prime}X_{n}^{\prime}H_{n}J_{nk}1_{n}+o_{p}(1)$.
Using the same in (3), we also obtain
$\sqrt{n}\bar{y}_{n}=\sqrt{n}\bar{x}_{n}+\frac{1}{\sqrt{n}}D_{n}U_{n0}^{\prime}1_{n}+o_{p}(1)$.
This implies that the $k$th element of $\sqrt{n}\bar{y}_{n}$ has the expansion
$(\sqrt{n}\bar{y}_{n})_{k}=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}x_{n,ik}(1+s_{n,i})+o_{p}(1)$.
As $x_{n,ik}(1+s_{n,i})$, $i=1,\ldots,n$, are i.i.d. with mean zero and
variance $2\mathrm{Var}(x_{n,ik})$, and as $x_{n,ik}(1+s_{n,i})$ and
$x_{n,i\ell}(1+s_{n,i})$ are uncorrelated for $k\neq\ell$, the limiting
distribution of $\sqrt{n}\bar{y}_{n}$ is $\mathcal{N}_{p}(0,2\Lambda)$.

Let now $Z_{n}=X_{n}O^{\prime}+1_{n}\mu^{\prime}$ for some $p\times p$
orthogonal matrix $O$ and $\mu\in\mathbb{R}^{p}$. Then,
$Z_{n,\mathcal{P}}=(X_{n,\mathcal{P}}-1_{n}\bar{x}_{n}^{\prime})O^{\prime}+1_{n}(O\bar{x}_{n}+\mu)^{\prime}$,
thus implying that
$\frac{1}{n}Z_{n,\mathcal{P}}^{\prime}1_{n}=O\frac{1}{n}X_{n,\mathcal{P}}^{\prime}1_{n}-O\bar{x}_{n}+O\bar{x}_{n}+\mu$
and
$\sqrt{n}\left(\frac{1}{n}Z_{n,\mathcal{P}}^{\prime}1_{n}-\mu\right)=\sqrt{n}O\bar{y}_{n}\rightsquigarrow\mathcal{N}_{p}(0,2O\Lambda
O^{\prime})$. This completes the proof for $\mathcal{J}$-SA.

For $\mathcal{O}$-SA, the proof is similar to $\mathcal{J}$-SA, and we point
out only the differences next. To see that
$X_{n}^{\prime}H_{n}O_{nk}1_{n}/\sqrt{n}$ is stochastically bounded, we
observe that $O_{nk}1_{n}\sim\sqrt{n}O_{nk}e_{1}\sim\sqrt{n}u_{n}$, where
$u_{n}$ is uniform on the unit sphere $\mathbb{S}^{n-1}$. Moreover, letting
$\chi_{n}$ denote a random variable obeying a $\chi$-distribution with $n$
degrees of freedom that is independent of $u_{n}$, we have
$b_{n}:=\chi_{n}u_{n}\sim\mathcal{N}_{n}(0,I_{n})$ and
$\chi_{n}/\sqrt{n}\rightarrow_{p}1$. Consequently, denoting a generic column
of $X_{n}$ by $x_{n}\sim\mathcal{N}_{n}(0,\lambda I_{n})$, we have
$(1/\sqrt{n})x_{n}^{\prime}H_{n}O_{nk}1_{n}\sim
x_{n}^{\prime}H_{n}u_{n}=x_{n}^{\prime}u_{n}-\bar{x}_{n}1_{n}^{\prime}u_{n}=b_{n}^{-1}(1/\sqrt{n})x_{n}^{\prime}z_{n}-\sqrt{n}\bar{x}_{n}\bar{z}_{n}b_{n}^{-1}$,
showing that $X_{n}^{\prime}H_{n}O_{nk}1_{n}/\sqrt{n}$ is stochastically
bounded. Hence,

$\displaystyle(\sqrt{n}\bar{y}_{n})_{k}=$
$\displaystyle(\sqrt{n}\bar{x}_{n})_{k}+b_{n}^{-1}\frac{1}{\sqrt{n}}e_{k}^{\prime}X_{n}^{\prime}z_{n}+o_{p}(1)=(\sqrt{n}\bar{x}_{n})_{k}+\frac{1}{\sqrt{n}}e_{k}^{\prime}X_{n}^{\prime}z_{n}+o_{p}(1)$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{n}}\sum_{i=1}^{n}x_{n,ik}(1+z_{n,i})+o_{p}(1).$

The limiting distribution of this is $\mathcal{N}(0,2\mathrm{Var}(x_{n,ik}))$,
and rest of the proof follows similarly as for $\mathcal{J}$-SA.

The following lemma is a direct consequence of Proposition 4.1 in [18].

###### Lemma 1

Let $P$ be uniformly random $n\times n$ permutation matrix. Then,
$\mathrm{E}(P)=(1/n)1_{n}1_{n}^{\prime}$,
$\mathrm{E}\\{\mathrm{tr}(P^{2})\\}=2$ and
$\mathrm{E}[\\{\mathrm{tr}(P)\\}^{2}]=2$.

######  Proof (Proof of Theorem 2.2)

Starting again with the case of $\mathcal{N}_{p}(0,\Lambda)$-distributed data
and using the notation of the proof of Theorem 2.1, we have

$\displaystyle\sqrt{n}(S_{n,\mathcal{P}}-\Lambda)=\sqrt{n}\left(\frac{1}{n}Y_{n}^{\prime}Y_{n}-\Lambda-\bar{y}_{n}\bar{y}_{n}^{\prime}\right)=\sqrt{n}\left(\frac{1}{n}Y_{n}^{\prime}Y_{n}-\Lambda\right)+o_{p}(1),$

since $\sqrt{n}\bar{y}_{n}=\mathcal{O}_{p}(1)$. From the proof of Theorem 2.1
we have that $V_{n}D_{n}U_{n0}^{\prime}1_{n}\bar{x}_{n}/\sqrt{n}=o_{p}(1)$,
meaning that

$\displaystyle\begin{split}\sqrt{n}(S_{n,\mathcal{P}}-\Lambda)=&\sqrt{n}\left(\frac{1}{n}V_{n}D_{n}U_{n0}^{\prime}U_{n0}D_{n}V_{n}^{\prime}-\Lambda\right)+o_{p}(1),\\\
=&\sqrt{n}\left(\frac{1}{n}X_{n}^{\prime}H_{n}X_{n}-\Lambda\right)+\frac{1}{\sqrt{n}}V_{n}D_{n}G_{n}D_{n}V_{n}^{\prime}+o_{p}(1),\\\
=&\sqrt{n}\left(\frac{1}{n}X_{n}^{\prime}X_{n}-\Lambda\right)+\frac{1}{\sqrt{n}}V_{n}D_{n}G_{n}D_{n}V_{n}^{\prime}+o_{p}(1),\end{split}$
(5)

where $G_{n}\in\mathbb{R}^{p\times p}$ is a matrix with the elements
$g_{n,kk}=0$, $g_{n,k\ell}=u_{nk}^{\prime}T_{nk}^{\prime}T_{n\ell}u_{n\ell}$,
where $T_{nk}$ are either permutation, sign-change or orthogonal matrices,
depending on the type of SA. We next show that, for every $k\neq\ell$, the
quantity $f_{n,k\ell}:=d_{nk}d_{n\ell}g_{n,k\ell}/\sqrt{n}$ is stochastically
bounded.

For $\mathcal{P}$-SA, this is seen by writing

$\displaystyle\sqrt{n}f_{n,k\ell}=$ $\displaystyle
e_{k}^{\prime}D_{n}U_{n}^{\prime}P_{nk}^{\prime}P_{n\ell}U_{n}D_{n}e_{\ell}=e_{k}^{\prime}V_{n}^{\prime}X_{n}^{\prime}H_{n}P_{nk}^{\prime}P_{n\ell}H_{n}X_{n}V_{n}e_{\ell}$
$\displaystyle=$ $\displaystyle
e_{k}^{\prime}V_{n}^{\prime}(X_{n}^{\prime}P_{nk}^{\prime}P_{n\ell}X_{n})V_{n}e_{\ell}-ne_{k}^{\prime}V_{n}^{\prime}(\bar{x}_{n}\bar{x}_{n}^{\prime})V_{n}e_{\ell},$

which shows that

$\displaystyle f_{n,k\ell}=$
$\displaystyle\frac{1}{\sqrt{n}}e_{k}^{\prime}V_{n}^{\prime}(X_{n}^{\prime}P_{nk}^{\prime}P_{n\ell}X_{n})V_{n}e_{\ell}+o_{p}(1)=\frac{1}{\sqrt{n}}x_{n,k}^{\prime}P_{nk}^{\prime}P_{n\ell}x_{n,\ell}+o_{p}(1),$

where $x_{n,k}$ is the $k$th column of $X_{n}$. For the second equality, we
have used the fact that
$\frac{1}{\sqrt{n}}X_{n}^{\prime}P_{nk}^{\prime}P_{n\ell}X_{n}=\mathcal{O}_{p}(1)$
which holds immediately for the off-diagonal elements by the independence of
$x_{n,k}$ and $x_{n,\ell}$. For the diagonal elements, the stochastic
boundedness is equivalent to showing that
$x_{n}^{\prime}P_{n}x_{n}/\sqrt{n}=\mathcal{O}_{p}(1)$ when
$x_{n}\sim\mathcal{N}_{n}(0,I_{n})$ and $P_{n}$ is a uniformly random $n\times
n$ permutation matrix. Since $\mathrm{E}(x_{n}^{\prime}P_{n}x_{n})=0$, by
Theorem 14.4-1 in [2] we have

$\displaystyle\frac{1}{\sqrt{n}}x_{n}^{\prime}P_{n}x_{n}=\frac{1}{\sqrt{n}}\mathrm{SD}(x_{n}^{\prime}P_{n}x_{n})\cdot\mathcal{O}_{p}(1).$
(6)

Now,
$\mathrm{E}(x_{n}x_{n}^{\prime}P_{n}x_{n}x_{n}^{\prime}|P_{n})=\mathrm{tr}(P_{n})I_{n}+P_{n}+P_{n}^{\prime}$,
giving, using Lemma 1, that
$\mathrm{Var}(x_{n}^{\prime}P_{n}x_{n})=\mathrm{E}[\\{\mathrm{tr}(P_{n})\\}^{2}]+\mathrm{E}\\{\mathrm{tr}(P_{n}^{2})\\}+n=n+4$.
Plugging in to (6), the stochastic boundedness of
$X_{n}^{\prime}P_{nk}^{\prime}P_{n\ell}X_{n}/\sqrt{n}$ and, consequently, that
of $f_{n,k\ell}$ now follows.

For $\mathcal{J}$-SA, the reasoning is similar but we need the extra facts
that $\frac{1}{n}X_{n}^{\prime}J_{nk}J_{n\ell}1_{n}=o_{p}(1)$ and
$\frac{1}{n}1_{n}^{\prime}J_{nk}J_{n\ell}1_{n}=o_{p}(1)$ where the former
holds because $J_{n\ell}J_{nk}X_{n}\sim X_{n}$. Furthermore, instead of Lemma
1, we use $\mathrm{tr}(J_{n}^{2})=n$ and
$\mathrm{E}[\\{\mathrm{tr}(J_{n})\\}^{2}]=n$.

For $\mathcal{O}$-SA, we similarly have that
$\frac{1}{n}X_{n}^{\prime}O_{nk}O_{n\ell}1_{n}=o_{p}(1)$ and
$\frac{1}{n}1_{n}^{\prime}O_{nk}O_{n\ell}1_{n}=o_{p}(1)$, since
$O_{n\ell}O_{nk}X_{n}\sim X_{n}$ and since, reasoning as in the proof of
Theorem 2.1, we have
$\frac{1}{n}1_{n}^{\prime}O_{nk}O_{n\ell}1_{n}=\frac{1}{n}z_{n1}^{\prime}z_{n2}+o_{p}(1)$,
where $z_{n1},z_{n2}\sim\mathcal{N}_{n}(0,I_{n})$ are independent of each
other. Also, instead of Lemma 1, we use for $\mathcal{O}$-SA the bounds
$\mathrm{tr}(O_{n}^{2})\leq n$ and
$\mathrm{E}\\{(P_{n,11}+\cdots+P_{n,nn})^{2}\\}\leq\\{[\mathrm{E}(P_{n,11}^{2})]^{1/2}+\cdots+[\mathrm{E}(P_{n,nn}^{2})]^{1/2}\\}^{2}$,
together with $\mathrm{E}(P_{n,ii})=0$ and $\mathrm{E}(P_{n,ii}^{2})=1/n$.

Thus, for every form of SA, by (5), we have
$\sqrt{n}(S_{n,\mathcal{P}}-\Lambda)=\sqrt{n}(\frac{1}{n}X_{n}^{\prime}X_{n}-\Lambda)+\frac{1}{\sqrt{n}}D_{n}G_{n}D_{n}+o_{p}(1)$.
Writing out the individual elements of
$B_{n}:=\sqrt{n}(S_{n,\mathcal{P}}-\Lambda)$, the diagonal and off-diagonal
thus read

$\displaystyle b_{n,kk}$
$\displaystyle=\sqrt{n}\left(\frac{1}{n}x_{n,k}^{\prime}x_{n,k}-\lambda_{k}\right)+o_{p}(1),$
(7) $\displaystyle b_{n,k\ell}$
$\displaystyle=\frac{1}{\sqrt{n}}x_{n,k}^{\prime}(I_{n}+T_{nk}^{\prime}T_{n\ell})x_{n,\ell}+o_{p}(1).$
(8)

What remains now is to show that $b_{n,kk},b_{n,k\ell}$, $k,\ell=1,\ldots,p$,
$k\neq\ell$, have a limiting joint normal distribution with the desired
covariance matrix. We begin by computing the covariance matrix.

For $\mathcal{P}$-SA, direct computation gives
$\mathrm{Var}(b_{n,kk})=2\lambda_{k}^{2}$ and
$\mathrm{Var}(b_{n,k\ell})=2\lambda_{k}\lambda_{\ell}\\{1+(1/n)\mathrm{E}\mathrm{tr}(P_{nk}^{\prime}P_{n\ell})\\}=2(1+1/n)\lambda_{k}\lambda_{\ell}=2\lambda_{k}\lambda_{\ell}+o(1)$,
where we have used the fact that $\mathrm{E}(P_{nk})=1_{n}1_{n}^{\prime}/n$.
Similarly, we obtain the following non-zero covariances (rest of the
covariances are zero): $\mathrm{Cov}(b_{n,k\ell},b_{n,\ell
k})=\mathrm{Var}(b_{n,k\ell})=2\lambda_{k}\lambda_{\ell}+o(1)$. Analogous
computation reveals that exactly the same asymptotic variances and covariances
are obtained also for the two other forms of SA. Consequently, in each case,
the limiting covariance matrix of
$\sqrt{n}\mathrm{vec}(S_{n,\mathcal{P}}-\Lambda)$ is
$(\Lambda^{1/2}\otimes\Lambda^{1/2})[2I_{p^{2}}+2K_{p,p}-2\mathrm{diag}\\{\mathrm{vec}(I_{p})\\}](\Lambda^{1/2}\otimes\Lambda^{1/2})$.
The form for a general normal distribution now follows with equivariance
arguments as in the proof of Theorem 2.1. That the moments of the limiting
distribution actually are the limits of the moments we computed earlier, is
guaranteed by showing that $b_{n,kk}$ and $b_{n,k\ell}$ are uniformly
integrable. E.g., for $b_{n,k\ell}$, this can be done by denoting
$A:=(1/\sqrt{n})x_{n,k}^{\prime}x_{n,\ell}$ and
$B:=(1/\sqrt{n})x_{n,k}^{\prime}T_{nk}^{\prime}T_{n\ell}x_{n,\ell}$, using
Young’s inequality to bound $\mathrm{E}\\{(A+B)^{4}\\}\leq
a\mathrm{E}(A^{4})+b\mathrm{E}(B^{4})$ for some scalars $a,b\in\mathbb{R}$ and
observing that $T_{nk}x_{n,k}\sim\mathcal{N}_{n}(0,I_{n})$ for each form of
SA. The boundedness of $\mathrm{E}(A^{4})$ and $\mathrm{E}(B^{4})$ now follows
from the moments of the Gaussian distribution.

Next, we still show that the limiting normal distribution actually exists. By
the equivariance properties of the multivariate normal distribution, it is
sufficient to consider only the case $\Lambda=I_{p}$ for this.

We begin with $\mathcal{O}$-SA. Letting $Q_{n1},\ldots,Q_{np}$ be random
orthogonal matrices uniform from the Haar distribution (and independent of all
our other random variables), we have $x_{n,k}\sim Q_{nk}x_{n,k}$. Hence, (7)
and (8) can be written as
$b_{n,kk}=\sqrt{n}\\{(1/n)x_{n,k}^{\prime}x_{n,k}-1\\}+o_{p}(1)$ and
$b_{n,k\ell}=(1/\sqrt{n})x_{n,k}^{\prime}(Q_{nk}^{\prime}Q_{n\ell}+R_{nk}^{\prime}R_{n\ell})x_{n,\ell}+o_{p}(1)$
where $R_{nk}:=O_{nk}Q_{nk}$ is Haar-uniformly distributed orthogonal matrix
and independent of $Q_{nk}$. We then decompose $x_{n,k}=\chi_{nk}u_{nk}$ where
$\chi_{nk}\sim\chi_{n}$ and $u_{nk}$ is uniform on the unit sphere and let
$\chi_{nk1},\chi_{nk2}$ be independent $\chi_{n}$-random variables. Using
these we write the elements $b_{n,kk}$ and $b_{n,k\ell}$ as

$\displaystyle b_{n,kk}$
$\displaystyle=\sqrt{n}\left(\frac{1}{n}(\chi_{nk}u_{nk})^{\prime}(\chi_{nk}u_{nk})-1\right)+o_{p}(1)$
$\displaystyle b_{n,k\ell}$
$\displaystyle=\frac{\chi_{nk}\chi_{n\ell}}{\chi_{nk1}\chi_{n\ell
1}}\frac{1}{\sqrt{n}}(\chi_{nk1}Q_{nk}u_{nk})^{\prime}(\chi_{n\ell
1}Q_{n\ell}u_{n\ell})$
$\displaystyle+\frac{\chi_{nk}\chi_{n\ell}}{\chi_{nk2}\chi_{n\ell
2}}\frac{1}{\sqrt{n}}(\chi_{nk2}R_{nk}u_{nk})^{\prime}(\chi_{n\ell
2}R_{n\ell}u_{n\ell})+o_{p}(1).$

Now, above $(\chi_{nk}\chi_{n\ell})/(\chi_{nk1}\chi_{n\ell
1})\rightarrow_{p}1$ and $(\chi_{nk}\chi_{n\ell})/(\chi_{nk2}\chi_{n\ell
2})\rightarrow_{p}1$. Moreover, $\chi_{nk}u_{nk}$, $\chi_{nk1}Q_{nk}u_{nk}$
and $\chi_{nk2}R_{nk}u_{nk}$ are independent of each other and all obey the
$\mathcal{N}_{n}(0,I_{n})$-distribution. Hence, by CLT and Slutsky’s lemma,
the desired joint limiting normal distribution for $b_{n,kk}$ and
$b_{n,k\ell}$, $k,\ell=1,\ldots,p$, $k\neq\ell$, is obtained in the case of
$\mathcal{O}$-SA.

For $\mathcal{J}$-SA, the joint limiting normality follows directly from the
standard multivariate CLT, once we observe that the transformations
$J_{n1},\ldots,J_{np}$ do not “mix” the observation sequences and retain their
i.i.d. nature.

What is thus left is $\mathcal{P}$-SA. In that case, we use the Cramér-Wold
device combined with the CLT for local dependency neighbourhoods [13, Theorem
3.6]. We demonstrate the proof below in the case $p=2$, the general case
following analogously (but with more cluttered notation). That is, the claim
holds for $p=2$ once we show that
$S_{n}:=a_{11}\sqrt{n}(\frac{1}{n}x^{\prime}x-1)+a_{12}\frac{1}{\sqrt{n}}x^{\prime}(I_{n}+P)y+a_{22}\sqrt{n}(\frac{1}{n}y^{\prime}y-1)$
admits a limiting normal distribution where $a_{11},a_{12},a_{22}$ are
arbitrary constants, $P$ is a uniformly random $n\times n$ orthogonal matrix
and $x,y\sim\mathcal{N}_{n}(0,I_{n})$ are independent of each other and $P$.
Our objective is to use [13, Theorem 3.6], where we will take (using their
notation)
$X_{i}=a_{11}(x_{i}^{2}-1)/\sqrt{n}+a_{12}x_{i}(y_{i}+y_{\delta(i)})/\sqrt{n}+a_{22}(y_{i}^{2}-1)/\sqrt{n}$,
where $\delta$ is the permutation mapping corresponding to the permutation
matrix $P$, and
$\sigma^{2}=\mathrm{Var}(S_{n})=2a_{11}+2a_{12}(1+1/n)+2a_{22}$.

Inspection of the proof of their Theorem 3.6 reveals that the dependency
neighbourhood $N_{i}$ can be taken to be random (as they are for us), as long
as their maximal degree is almost surely some finite $D$ (as it is for us,
since $x_{i}(y_{i}+y_{\delta(i)})$ depends on maximally two other terms), when
specific modifications to the proof/result are done: (i) The first term on the
RHS of the statement of Theorem 3.6 can be kept as such, but when deriving it,
the sums of the form “$\sum_{j\in N_{i}}$” have to be replaced with
“$\sum_{j=1}^{n}\mathbb{I}(j\in N_{i})$”, since $N_{i}$ are random. (ii) In
their formula (3.12), we decompose the term
$\mathrm{Var}(\sum_{i=1}^{n}\sum_{j\in N_{i}}X_{i}X_{j})$ as

$\displaystyle\mathrm{E}\left\\{\mathrm{Var}\left(\sum_{i=1}^{n}\sum_{j\in
N_{i}}X_{i}X_{j}\mid
P\right)\right\\}+\mathrm{Var}\left\\{\mathrm{E}\left(\sum_{i=1}^{n}\sum_{j\in
N_{i}}X_{i}X_{j}\mid P\right)\right\\}$ $\displaystyle\leq$ $\displaystyle
14D^{3}\sum_{i=1}^{n}\mathrm{E}(X_{i}^{4})+\mathrm{Var}\\{\mathrm{Var}(S_{n}\mid
P)\\},$

where the inequality uses the variance bound derived in the proof of [13,
Theorem 3.6] (for our conditioned-upon dependency neighborhoods) and the
second term uses the fact that $\mathrm{Var}(\sum_{i=1}^{n}X_{i}\mid
P)=\mathrm{E}(\sum_{i=1}^{n}\sum_{j\in N_{i}}X_{i}X_{j}\mid P)$.

Now, as $D$ is fixed, as $\sigma^{2}$ approaches a non-zero constant when
$n\rightarrow\infty$, and as the $X_{i}$ are identically distributed, the
desired claim holds once we show that

$\displaystyle\mathrm{E}|X_{1}|^{3}=o(1/n),\quad\mathrm{E}X_{1}^{4}=o(1/n)\quad\mbox{and}\quad\mathrm{Var}\\{\mathrm{Var}(S_{n}\mid
P)\\}=o(1).$ (9)

For the third claim in (9), we have $\mathrm{Var}(S_{n}\mid
P)=2a_{11}+2a_{12}\\{1+(1/n)\mathrm{tr}(P)\\}+2a_{22}$. Hence,

$\displaystyle\mathrm{Var}\\{\mathrm{Var}(S_{n}\mid
P)\\}=\frac{4a_{12}^{2}}{n^{2}}\mathrm{Var}\\{\mathrm{tr}(P)\\}\leq\frac{4a_{12}^{2}}{n^{2}}\mathrm{E}[\\{\mathrm{tr}(P)\\}^{2}]=\frac{8a_{12}^{2}}{n^{2}},$

where we use Lemma 1, taking care of the third claim. Then, as $X_{1}$ equals
$1/\sqrt{n}$ times a random variable with all moments finite,
$X_{1}=(1/\sqrt{n})\\{a_{11}(x_{1}^{2}-1)+a_{12}x_{1}(y_{1}+y_{\sigma(i)})+a_{22}(y_{1}^{2}-1)\\}$,
the first two claims in (9) also trivially hold. This conludes the proof in
the case $p=2$ and the general case is handled exactly analogously.

##  Appendix 0.B Additional figures

Figure 6 shows the results of the utility simulation study in Section 3.1 for
Poisson-distributed data. The top (bottom) row of Figure 6 is analogous to
Figure 2 (Figure 3).

Figure 6: The relative error of the empirical covariance matrices of sample
mean (solid line) and sample covariance (dotted line) compared to their
asymptotic covariance matrices for $\mathcal{P}$-SA (blue), $\mathcal{J}$-SA
(orange), and $\mathcal{O}$-SA (purple). In the top row, the original data
(green) is sampled from a Poisson distribution meeting the Assumption 1 while
on the second row the assumption is violated. Sample size is presented on a
logarithmic scale.

## References

  * [1] Awan, J., Kenney, A., Reimherr, M., Slavković, A.: Benefits and pitfalls of the exponential mechanism with applications to Hilbert spaces and functional PCA. In: Proceedings of the 36th International Conference on Machine Learning. vol. 97, pp. 374––384. PMLR (2019)
  * [2] Bishop, Y.M., Fienberg, S.E., Holland, P.W.: Discrete Multivariate Analysis: Theory and Practice. Springer Science & Business Media (2007)
  * [3] Calviño, A., Aldeguer, P., Domingo-Ferrer, J.: Factor analysis for anonymization. In: 2017 IEEE International Conference on Data Mining Workshops (ICDMW). pp. 984–991 (2017)
  * [4] Domingo-Ferrer, J., Torra, V.: Disclosure risk assessment in statistical data protection. Journal of Computational and Applied Mathematics 164-165, 285–293 (2004)
  * [5] Dunsche, M., Kutta, T., Dette, H.: Multivariate mean comparison under differential privacy. In: International Conference on Privacy in Statistical Databases. pp. 31–45. Springer (2022)
  * [6] Dwork, C.: Differential privacy. In: International Colloquium on Automata, Languages, and Programming. pp. 1–12. Springer Berlin Heidelberg (2006)
  * [7] Johnstone, I.M., Paul, D.: PCA in high dimensions: An orientation. Proceedings of the IEEE 106(8), 1277–1292 (2018)
  * [8] Kollo, T., von Rosen, D.: Advanced Multivariate Statistics with Matrices. Springer (2005)
  * [9] Kundu, S., Suthaharan, S.: Privacy-preserving predictive model using factor analysis for neuroscience applications. In: IEEE International Conference on Big Data Security on Cloud (BigDataSecurity), High Performance and Smart Computing (HPSC) and Intelligent Data and Security (IDS). pp. 67–73. IEEE (2019)
  * [10] Lasko, T.A., Vinterbo, S.A.: Spectral anonymization of data. IEEE Transactions on Knowledge and Data Engineering 22(3), 437–446 (2009)
  * [11] Machanavajjhala, A., Kifer, D., Gehrke, J., Venkitasubramaniam, M.: l-diversity. ACM Transactions on Knowledge Discovery from Data 1 (2007)
  * [12] Ninghui, L., Tiancheng, L., Venkatasubramanian, S.: t-Closeness: Privacy beyond k-anonymity and l-diversity (2007)
  * [13] Ross, N.: Fundamentals of Stein’s method. Probability Surveys 8, 210–293 (2011)
  * [14] Seeman, J., Reimherr, M., Slavković, A.: Exact privacy guarantees for Markov chain implementations of the exponential mechanism with artificial atoms. In: Advances in Neural Information Processing Systems. vol. 34, pp. 13125–13136. Curran Associates, Inc. (2021)
  * [15] Stewart, G.W.: The efficient generation of random orthogonal matrices with an application to condition estimators. SIAM Journal on Numerical Analysis 17(3), 403–409 (1980)
  * [16] Sweeney, L.: k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowlege-Based Systems 10 (2002)
  * [17] Tyler, D.E.: Radial estimates and the test for sphericity. Biometrika 69(2), 429–436 (1982)
  * [18] Viana, M.A.: The covariance structure of random permutation matrices. Contemporary Mathematics 287, 303–326 (2001)
  * [19] Xiao, H., Ye, Y., Devadas, S.: Local differential privacy in decentralized optimization. arXiv preprint (2019)


# Adelic interpretation of the Euler characteristic for one-dimensional global
fields

Weronika Czerniawska

###### Abstract

Tate’s ’Fourier analysis in Number Fields and Hecke’s zeta function’, preceded
by work of Iwasawa, showed in that adelic language can be extremely useful for
arithmetic purposes. In fact one can see this work as one of the main impulses
for development of arithmetic geometry. Indeed, it developed a theory in which
number fields and function fields of algebraic curves are seen as objects of
the same kind. In this paper we generalize the work of Tate. By using certain
natural renormalization of Haar measure on adeles we obtain the relative
Riemann-Roch theorem out of the adelic Poisson summation formulae. We express
the relative Euler characteristics using purely adelic language. The formulas
not only cover absolute and relative case, but also both the case of an
arithmetic curve and a projective curve over a finite field. These results are
inspired by work of A.Borisov [1] that views the size of cohomology as a
dimension of so-called ghost space i.e. a locally compact abelian group
enriched with an appropriate structure of convolution of Haar measures on it.

toc

##  1 Introduction

To both function field of an algebraic curve over an finite field and a number
field one can associate its ring of adeles which is locally compact,
Pontryagin self-dual abelian group. It is the restricted direct product of all
the completions of the base field. In his PhD thesis, John Tate used Fourier
analysis on adelic rings of number fields to prove analytic continuation and
functional equation for Hecke’s zeta functions. Another important result
appearing in that work is the Riemann-Roch theorem which is a direct
consequence of the Poisson summation formula for the ring of adeles. One can
see that this method allows us to obtain uniformly both the case of a
(completed) spectrum of a number field and a proper algebraic curve over a
finite field ([12, Chapter 7.2], [14, Proposition 1]. It is surprising if one
realises that in the geometric case the Euler characteristic is just an
alternating sum of the dimensions of the cohomology groups viewed as vector
spaces over the field of definition whereas in the arithmetic case it is a
covolume of an an appropriate lattice. In spite of that, Fourier analysis on
rings of adeles miraculously provides us with the point of view from which the
geometric and the arithmetic case look the same. One has to keep in mind that
this analogy triggered the development of geometric approach to problems of
number theory. As geometric counterparts of some of the most fundamental open
problems in number theory are solved, deepening the understanding of the
geometric-arithmetic analogy is of utmost importance (see [8],[15]).

This work revisits the global (adelic) Fourier analysis approach to geometry
of one-dimensional global fields. We write the Euler characteristic for a
given divisor can be obtained as a single integral of the associated
eigenfunction of the adelic Fourier transform. With this approach it is easy
to see that the Riemann-Roch theorem holds. Serre’s duality can be obtained
via Fourier transform correspondences.

Another important aspect of the existing Riemann-Roch theory is functoriality.
We extend the method to the relative case i.e. morphisms between curves like
in [9, Section V.1] (except that we also cover its geometric counterpart). It
is also compatible with functorial approach that gives Grothendieck-Riemann-
Roch theorem for one-dimensional global fields (see for example [11, Chapter
III] for the number field case). Surprisingly this can be achieved by using a
natural renormalisation of the Haar measure on the ring of adeles through
global Poisson summation formulae.

More specifically we can write

$\chi_{L/K}(D_{\alpha})=\log\int\limits_{\mathbb{A}_{L/K}}f_{\alpha}$

where $D_{\alpha}$ is a divisor on the given curve associated with an idele (a
unit in the ring of adeles) $\alpha$, $f_{\alpha}$ is an eigenfunction of the
global Fourier transform and the integral is taken over the ring of adeles
$A_{L}$ and the lower notation $L/K$ only indicates that the integral is taken
over an appropriate “relative” normalisation of the Haar measure on
$\mathbb{A}_{L}$ associated to the given field extension; i.e. $\mu_{L/K}$
such that

$\mu_{L/K}(O_{L})=|N_{K/\mathbb{Q}}\mathfrak{d}_{L/K}|_{\infty}^{-1/2}$

i.e. the measure of the ring of integers of the number field $L$ is equal to
the square root of the absolute value of the norm $N_{K/\mathbb{Q}}$ relative
discriminant $\mathfrak{d}_{L/K}$.

The paper is organized in the following way: first we recall the theory of
local and global discriminant which will play a role in the normalization of
the Haar measures fixed later. We recall briefly the theory of adeles for one
dimensional global fields.

In the following section we define functions on adelic subspaces that give us
the size of cohomology spaces as appropriate adelic integrals. We see that the
Riemann-Roch theorem holds and deduce Serre’s duality using Fourier analysis
on number fields. In the section 4 we introduce the relative theory. In the
last section we show that in our setting we obtain the Riemann-Roch theorem as
stated in [9]. In the appendix we quickly outline Fourier analysis on local
non-archimedean fields that is used multiple times to complete calculations
presented in this paper and is less classical than Fourier analysis on
archimedean local fields.

These developments are not only inspired by mentioned Tate’s thesis but also
by A.Borisov’s work on arithmetic cohomology theory introduced in [1]. Even
though we operate with eigenfunctions of the global Fourier transform instead
of cohomology spaces, one can see that those two approaches encode the same
data (see 3.1). It is worth pointing out that the Relative Riemann-Roch
theorem ([9, Theorem V.1.2]) is applied ([9, Lemma V.3.5]) in the proof of the
Falting-Riemann-Roch theorem ([9, Theorem V.3.4]. Therefore the theory
developed here is not only interesting on its own, but also is a little step
towards a two-dimensional generalization.

### Acknowledgements

This work was supported by the SNSF-grants 182111, 204125 as well as by NCCR
SwissMAP.

##  2 Background

###  2.1 Preliminaries

In this paper we uniformly treat all one-dimensional global fields $K$ i.e.
number fields and the fields of functions of projective geometrically integral
algebraic curves over a finite field. In particular, $K$ is a finite extension
of the field of rational numbers $Q=\mathbb{Q}$ in the arithmetic case and $K$
is a finite separable extension of $Q=\mathbb{F}_{p}(t)$, where $t$ is
transcendental over $\mathbb{F}_{p}$ and $\mathbb{F}_{p}$ is a finite filed
with $p$ elements. We will refer to spectra of number fields as arithmetic
curves. The results in this paper are uniform for both arithmetic and
algebraic curves. We denote by $O_{K}$ the ring of integers of $K$, which is
the integral closure of $Z=\mathbb{Z}$, $Z=\mathbb{F}_{p}[t]$ for the
archimedean and the geometric case respectively. We denote by $X_{K}$ the
“geometric object” associated to the global field $K$: if $K$ is a number
field, then $X_{K}$ is the Arakelov completion of the set of prime ideals of
$O_{K}$ $\operatorname{Spec}O_{K}$; if $K$ is a function field, then $X_{K}$
is the corresponding algebraic curve. When $K$ is a number field, we denote by
$\sigma:K\to\mathbb{C}$ a generic field embedding, and we identify conjugate
embeddings of $K$. In this way $\sigma$ can be thought as an archimedean place
$v$ of $K$ and moreover we fix the constant

$e_{v}:=\begin{cases}1&\text{ if $v$ is real }\\\ 2&\text{ if $v$ is complex
}\end{cases}$

which is the degree of $K_{v}$ over the field of real numbers $\mathbb{R}$. We
define the absolute discriminant

$d_{K}=\left\\{\begin{array}[]{cc}|\mathfrak{d}_{K/\mathbb{Q}}|_{\infty}&K\text{
number field,}\\\ q_{K}^{2g_{K}-2}&K\text{ function field.}\end{array}\right.$

Where $|\mathfrak{d}_{K/\mathbb{Q}}|_{\infty}$ is the absolute value of the
absolute discriminant of the number field $K$ (see [11, page 15]), $q_{K}$ is
the cardinality of the field of constants of $K$ and $g_{K}$ is the genus of
the curve $X_{K}$.

For an extension $L/K$ of global, one dimensional fields, we have the notion
of global relative discriminant $\mathfrak{d}_{L/K}$ which is an ideal of
$O_{K}$ in the arithmetic case, and a divisor in the geometric case.

###  2.2 Local fields

A place $v$ of a global field $K$ is an equivalence class of absolute value
functions on $K$. The completion $K_{v}$ is a locally compact additive group
with the topology induced by the absolute value and it will simply called a
local field. Therefore there exists a Haar measure on $K_{v}$ which is unique
up to a positive constant and we fix a measure in the following way:

$\mu_{v}(O_{K_{v}})=d_{K_{v}}:=|\mathfrak{d}_{K_{v}/{Q}_{p}}|_{p}^{1/2}$

where $\mathfrak{d}_{K_{v}/Q_{p}}$ is the local absolute discriminant for
$p|v$ (see [11, Chapter III §2]), and $Q_{p}$ is the local field of $Q$ at the
place $p$. When $v$ is archimedean we set the standard Lebesgue measure if
$K_{v}=\mathbb{R}$ and twice the standard Lebesgue measure if
$K_{v}=\mathbb{C}$. It turns out that $K_{v}$ is non canonically Pontryagin
self dual for any $v$, as shown in [13, 2.2]. The measure we fixed are such
that for each local Fourier transform the following inversion formula holds
(see [13, Theorem 2.2.2]):

$f(\xi)=\hat{\hat{f}}(-\xi)\;\text{ for }f\in L^{1}(K_{v})\,.$

If $w$ is a place of $L$ lying over $v$ we have the notion of relative
discriminant $\mathfrak{d}_{L_{w}/K_{v}}$ with respect to the extension
$L_{w}/K_{v}$, which can be seen as an ideal of $O_{K}$. One can check the
precise definitions of these objects in [11, Chapter III.2]. By [11, Chapter
III.2, (2.11)] we have the following relation between local and global
discriminants :

$\mathfrak{d}_{L/K}=\prod_{w}\prod_{w|v}\mathfrak{d}_{L_{w}/L_{v}}$

where $v$ runs through places of $K$ and $w$ runs through places of $L$. One
can deduce that

$d_{K}:=|\mathfrak{d}_{K}|_{\infty}=\prod\limits_{v}|\mathfrak{d}_{K_{v}}|^{-1}_{v}$

by product formula, and the following equality:

$d_{L/K}=\prod\limits_{v\nmid\infty}\prod\limits_{w|v}|\mathfrak{d}_{L_{w}/K_{v}}|^{-1}_{v}\hskip
14.22636pt\text{ where }\hskip 14.22636ptd_{L/K}:=d_{L}/d_{K}^{[L:K]},$ (1)

(see for example [7]).

In the geometric case we can always choose the transcendental element $t$ of
$K$ such that the extension $L/K$ is unramified for each infinite place, i.e.
the local doscriminant $\mathfrak{d}_{L_{w}/K_{v}}$ is trivial for $v|w$
infinite (see [7]).

###  2.3 Adeles

We remind that the ring of adeles is defined as

$\mathbb{A}_{K}=\\{(a_{v})_{v}\in\prod\limits_{v}K_{v}\,|\,a_{v}\in
O_{v}\,\text{ for all but finitely many }v\\}.$

The invertible adeles

$\mathbb{A}^{\times}_{K}=\\{(u_{v})_{v}\in\prod\limits_{v}K^{\times}_{v}\,|\,u_{v}=O^{\times}_{v}\,\text{
for all but finitely many }v\\}.$

are called ideles. The adeles form a topological ring endowed with the
restricted direct product topology (see [13, Section 3]). It is important to
keep in mind that it is different from the topology induced by the product
topology on $\prod_{v}K_{v}$. Adele ring is a special case of restricted
direct product of topological abelian groups with respect to their compact
subgroups. In particular the conditions imposed on the direct product make the
additive group of adeles locally compact and (non canonically) Pontryagin
self-dual.The considered Haar measure $\mu$ on $\mathbb{A}_{K}$ is just a
restricted direct product of local Haar measures ([13, Section 3.3]). The
Fourier inversion formula holds as a consequence of these properties holding
for the local fields (see [13, Section 3]).

######  Remark 2.1.

For each locally compact group the Haar measure is unique up to a constant.
For Pontryagin self-dual groups the Fourier inversion formula can hold
(without a constant factor) for exactly one normalisation of this measure. In
our case it holds exactly for the measure
$\mu_{v}(O_{K_{v}})=d_{K_{v}}:=|\mathfrak{d}_{K_{v}/{Q}_{p}}|_{p}^{1/2}$.

It follows that on $\mathbb{A}^{\times}_{K}$ we have induced an absolute value
function: if $u=(u_{v})$, then we put $|u|=\prod_{v}|u_{v}|_{v}$. With such a
choice it can be shown that $\mathbb{A}_{K}$ is a locally compact additive
group. It has been shown that

  * •

With the diagonal embedding $K$ can be seen as a discrete subgroup of
$\mathbb{A}_{K}$.

  * •

The quotient $\mathbb{A}_{K}/K$ is compact.

  * •

$\mathbb{A}_{K}$ is (non-canonically) self dual in the sense of Pontryagin.

We have a surjective group homomorphism

$\mathbb{A}_{K}^{\times}$$\mathrm{Div}(X_{K})$$(\alpha)_{v}$$D_{\alpha}:=\displaystyle{\sum\limits_{v}n_{v}(\alpha_{v})[v].}$

$\in$

$\in$

In the number field case by $\operatorname{Div}(X)$ we mean the group of
Arakelov divisors. The Haar measure $\mu$ on $\mathbb{A}_{K}$ that we’ve
chosen is such that the induced measure on the quotient gives
$\mu(\mathbb{A}_{K}/K)=1$.

##  3 Adelic representation of the size of cohomology and the Euler
characteristics

It is not clear how to define an arithmetic cohomology space as our object is
no longer a scheme after adding the part at infinity. As we saw through our
remark there also exist several approaches and ways of thinking about
arithmetic cohomology theory. Nevertheless, Riemann-Roch formulae requires
only the “size of the cohomolgy”. In the geometric case this is the dimension
of the groups of cohomology.

We consider the following adelic function associated to an idele $\alpha$

$f_{\alpha}=\prod\limits_{v}f_{\alpha_{v}}(u_{v}):\mathbb{A}_{K}\to\mathbb{R}$

where

$f_{\alpha_{v}}(u_{v})=\left\\{\begin{array}[]{ll}\operatorname{char}_{O_{v}}(\alpha_{v}^{-1}u_{v})&v\text{
non-archimedean}\\\ &\\\
\exp{(-e_{v}\pi|\alpha_{v}^{-1}u_{v}|_{v}^{2/e_{v}})}&v\text{ archimedean
}.\end{array}\right.$

where $\operatorname{char}_{O_{v}}$ is again the characteristic function of
$O_{v}\subset K_{v}$. Notice that it is a product of shifts of eigenfunctions
of the local Fourier transforms. We define a function

$\bar{f}_{\alpha}:$$\mathbb{A}_{K}/K$$\mathbb{R}$$a+K$$\displaystyle{\left(\int\limits_{K}f_{\alpha}(u)du\right)^{-1}\left(\int\limits_{K}f_{\alpha}(a+u)du\right)}$

$\in$

$\in$

It is easy to see that $\bar{f}_{\alpha}$ is well defined on the quotient
$\mathbb{A}_{K}/K$.

We define

$h^{0}(D_{\alpha}):=\log\int_{K}f_{\alpha}$
$h^{1}(D_{\alpha}):=\log\left(\int_{\mathbb{A}_{K}/K}\bar{f}_{\alpha}\right)^{-1}$

with the probabilistic measure. Therefore it makes sense to define

$\chi(D_{\alpha}):=\log\int\limits_{\mathbb{A}_{K}}f_{\alpha}.$

Thanks to the Weil’s equation for the Haar measure (see [5, Chapter 5 §11.1])
we have the following fundamental relation:

$\int\limits_{\mathbb{A}_{K}}f_{\alpha}=\int\limits_{\mathbb{A}_{K}/K}\int\limits_{K}\bar{f}_{\alpha},$

and therefore one sees that

$\int\limits_{\mathbb{A}_{K}}f_{\alpha}=\int\limits_{K}f_{\alpha}\cdot\int\limits_{\mathbb{A}_{K}/K}\bar{f}_{\alpha}.$

It is equivalent to

$\chi(D_{\alpha})=h^{0}(D_{\alpha})-h^{1}(D_{\alpha})$

and justifies the definition of $\chi$. It is easy to see that

$\chi_{K}(D_{\alpha})=\log|\alpha|+\log|\kappa_{K}|.$

Indeed, the value of the integral for any $D_{\alpha}$ is uniquely determined
by the adelic norm $[\alpha O_{K}:\mathbb{Z}]=\frac{\mu_{K}(\alpha
O_{L})}{\mu_{K}(O_{L})}=|\alpha|$ (see [16, Chapter 1]) and the measure
$\mu_{L/K}(O_{L})$. Note that the adelic norm is a product of local norms (see
[13] Lemma 4.1.2.) with the same relation with the local Haar measure
$\frac{\mu_{K_{v}}(\alpha O_{K_{v}})}{\mu_{K_{v}}(O_{K_{v}})}=|\alpha|_{v}$.
Hence, one sees that the value of $\int_{\mathbb{A_{K}}}f_{\alpha}$ is equal
to $\int_{\mathbb{A_{K}}}f_{1}$ scaled by the adelic absolute value $|\alpha|$
of $\alpha$.

We know that the Pontryagin dual of $K$ is $\mathbb{A}_{K}/K$. It is easy to
check that

$\widehat{\bar{f}_{\alpha}}=\left(\int\limits_{K}f_{\alpha}\right)^{-1}\cdot\widehat{f_{\alpha}}=\left(\int\limits_{K}f_{\alpha}\right)^{-1}\cdot
f_{\alpha^{-1}\kappa}$

where $\widehat{\bar{f}_{\alpha}}$ is the Fourier transform of
$\bar{f}_{\alpha}$ with respect to the measure and the character (determined
by the standard character of $\mathbb{A}_{K}$) of $\mathbb{A}_{K}/K$ and
$\widehat{f_{\alpha}}$ is the Fourier transform of $f_{\alpha}$ with respect
to the measure and the standard character of $\mathbb{A}_{K}$. Bare in mind
that here we consider the restriction of $f_{\alpha^{-1}}$ as the Fourier
transform of $\bar{f}_{\alpha}$; that is as a function on $K$ rather than on
$\mathbb{A}_{K}$. Since $f_{\beta}(0)=1$ for any $\beta$, one can notice that

$\left(\widehat{\bar{f}_{\alpha}}(0)\right)^{-1}\cdot{\bar{f}_{\alpha}}$

is the inverse Fourier transform of $f_{\alpha^{-1}\kappa}$ with respect to
the measure and the character on $K$. Taking the Fourier transform of this
relation is now easy to see that

$h^{0}(D_{\alpha^{-1}\kappa})=h^{1}(D_{\alpha})$ (2)

Indeed, we have

$\int\limits_{K}f_{\alpha^{-1}\kappa}=\widehat{f}_{\alpha^{-1}\kappa}(0)\hskip
28.45274pt\int\limits_{\mathbb{A}_{K}/K}\bar{f}_{\alpha}=\widehat{\bar{f}_{\alpha}}(0).$

Relation 2 is nothing else, but Serre’s duality.

######  Remark 3.1.

Notice that our theory is compatible with the theory introduced in [1]. Even
though we don’t explicitly point out the cohomology spaces, one can see that
the functions we use for obtaining the ’size of cohomology’ encodes the date
of a ghost space of the first kind (see [1, Lemma 2.2, Definition 5.1]).
Indeed, the non-archimedean part of the function $f_{\alpha}$ are
characteristic functions that encode the fractional ideal

$I_{D_{\alpha}}=\prod\limits_{v}P_{v}^{-n_{v}},$

whereas the archimedean part of $f_{\alpha}$ corresponds to the function
$u:I_{D_{\alpha}}\to\mathbb{R}$. Notice, (see [1, Section 2]) that the
function $u$ satisfies all but one (idempotency) of the properties
characterising characteristic functions. From this point of view local
components of $f_{\alpha}$ are somewhat analogous. At the same time the local
factors of $f_{\alpha}$ are all eigenfunctions of the local Fourier transform.
To give broader perspective to our approach it is worth stressing out that we
have an exact sequence

$K\to\mathbb{A}_{K}\to\mathbb{A}_{K}/K,$

to which we associate the functions $f_{\alpha}$ ( restricted to K),
$\bar{f}_{\alpha}$, $f_{\alpha}$ for an idele $\alpha$ associated to a divisor
$D_{\alpha}$. We can compare it to the sequence

$I_{D_{\alpha}}\to
I_{D_{\alpha}}\otimes\mathbb{R}\to(I_{D_{\alpha}}\otimes\mathbb{R})/I_{D_{\alpha}}$

of ghost spaces of the first kind (see [1, Section 5]).One can see that the
integral of our functions over the adelic spaces in the first sequence are
equal to the dimensions of the ghost spaces in the second sequence. In
particular both approaches give the same Euler characteristic as defined in
[9].

######  Remark 3.2.

Due to Serre’s duality being a consequence of Fourier duality we can see that
$h^{0}(D_{\alpha})$ and $h^{1}(D_{\alpha^{-1}})$ are bond by Heisenberg
indeterminacy principle. Indeed, we have the Heisenberg inequality, with in
case of the Gaussian distribution becomes an equality. See [1, Page 9] for a
related comment about ghost spaces.

##  4 Relative Euler characteristic

Fix a finite extension of global fields $L/K$ and let $w$ be a place lying
above $v$. We fix a normalization of the Haar measure on a local field $L_{w}$
with respect to a local field for which the measure of the ring of integers
$O_{L_{w}}$ is the square root of the relative discriminant of $L_{w}/K_{v}$,
i.e:

$\int\limits_{L_{w}/K_{v}}\mathrm{char}_{O_{L_{w}}}:=|\mathfrak{d}_{L_{w}/K_{v}}|_{v}^{-1/2}$

where $\mathfrak{d}_{L_{w}/K_{v}}$ is the relative discriminant. We will call
it the local relative measure. By taking an integral over $L_{w}/K_{v}$ we
mean an integral with respect to the relative measure. Given the local
relative measures for each place we define a global adelic measure $\mu_{L/K}$
like in [13] 3.3. Note that the relative discriminant is equal to the local
ring of integers almost everywhere i.e.

$\int_{L_{w}/K_{v}}\mathrm{char}_{O_{L_{w}}}=1\text{ for almost all }w,$

which is a necessary condition for defining a global measure. Then we define
the relative Euler characteristic

$\chi_{L/K}(D_{\alpha})=\log\int\limits_{\mathbb{A}_{L/K}}f_{\alpha}$

where by integral over ’relative adeles’ $\mathbb{A}_{L/K}$ we mean the
integral over $\mathbb{A}_{L}$ with the relative measure. One has

$\chi_{L/K}(D_{1})=\log\prod\limits_{w}\int\limits_{L_{w}/K_{v}}\mathrm{char}_{O_{L_{w}}}=\log\left(\prod\limits_{v}\prod\limits_{w|v}|\mathfrak{d}_{L_{w}/K_{v}}|^{-1/2}_{v}\right)=-\frac{1}{2}\log|\mathfrak{d}_{L/K}|_{v}$

By 1 we get

$-\frac{1}{2}\log|\mathfrak{d}_{L/K}|_{v}=-\frac{1}{2}\log\left|\mathfrak{d}_{L}\big{/}{\mathfrak{d}_{K}}^{[L:K]}\right|_{v}.$

Similarly to the absolute case the value of the integral for any $D_{\alpha}$
is uniquely determined by the adelic norm $[\alpha
O_{L}:O_{L}]=\frac{\mu_{L/K}(\alpha O_{L})}{\mu_{L/K}(O_{L})}=|\alpha|$ and
the measure $\mu_{L/K}(O_{L})$. Therefore, one has

$\chi_{L/K}(D_{\alpha})=\log|\alpha|+\log|\kappa_{L/K}|$

where $\kappa_{L/K}$ is the idele associated to the divisor of the relative
discriminant $\mathfrak{d}_{L}$. Note that this definition agrees with the
relative Euler characteristic defined in [9] V §1.Indeed

$\chi_{L/K}(D_{\alpha})=\log|\alpha|+\log|\mathfrak{d}_{L/K}|=\log|\alpha|+\log|\kappa_{L}|-[L:K]\log|\kappa_{K}|=\chi_{L}(D_{\alpha})-[L:K]\chi_{K}(D_{1,K}),$

where by $D_{1,K}$ we mean the zero divisor on $\mathrm{Spec}\,K$ i.e. the
divisor associated to the trivial idele.

To conclude, we point out that the absolute Euler $\chi_{L}$ characteristic is
a special case of the relative Euler characteristic $\chi_{L/K}$; i.e. it is
the relative Euler characteristic taken for $K={Q}$.

######  Remark 4.1.

The relative Euler characteristic in the number fields case is frequently
referred to as the Minkowski Euler characteristics. Since we work
simultaneously with number fields and function fields we decided to refer to
it simply as Euler characteristic.

##  5 Riemann-Roch for one-dimensional global fields

We easily get

$\chi_{L}(D_{\alpha})-\chi_{L}(D_{1})=\log|\alpha|$

which is the Riemann-Roch theorem as stated in [9, Chapter V,Theorem 1.2 ] and
[11, Chapter III,Proposition 3.4 ] . We also have

$\chi_{L/K}(D_{\alpha})-\chi_{L/K}(D_{1})=\log|\alpha|$

which is relative Riemann-Roch theorem. It agrees with ([9, Chapter V, Theorem
1.2]) except that here we state it uniformly for all one-dimensional global
fields. It is also worth noticing that the formula also agrees with what we
would obtain in [13] using the relative normalisation of the Haar measure.
Indeed, the Riemann-Roch statement has the following form

$\frac{1}{|\alpha|}\sum\limits_{u\in K}\hat{f}(u/\alpha)=\sum\limits_{u\in
K}f(\alpha u)$

rewrites in our language as

$\frac{1}{|\alpha|}\int\limits_{K}\hat{f_{1}}(u\alpha^{-1})=\int\limits_{K}f_{1}(\alpha
u)$

i.e.
$f=f_{1}=\prod\limits_{v}\mathrm{char}_{O_{v}}\times\prod\limits_{v|\infty}\exp{(-e_{v}\pi|u_{v}|_{v}^{2/e_{v}})}.$
Calculating it with respect to any Haar measure $\mu$ ,i.e. assuming we take
the Fourier transform with respect to any, not necessarily self-dual, Haar
measure on $\mathbb{A}_{K}$, one obtains

$\frac{1}{|\alpha|}\int\limits_{K}\mu(O_{v}){f_{\kappa}}(u\alpha^{-1})=\int\limits_{K}f_{1}(\alpha
u)$

which is

$\frac{\mu(O_{v})}{|\alpha|}\int\limits_{K}{f_{\alpha\kappa}}(u)=\int\limits_{K}f_{\alpha^{-1}}(u)$

Therefore taking the $\log$ of this equation and taking the relative measure
as $\mu$ one gets

$\log{d}_{L/K}-\log{|\alpha|}+h^{0}(D_{\alpha\kappa})=h^{0}(D_{\alpha^{-1}})$

which gives us the desired formula after applying Serre’s duality 2 and 1.

######  Remark 5.1.

In [13] one takes $K=\mathbb{Q}$. The relative measure for this extension is
the unique self dual measure on $\mathbb{A}_{L}$. As a different normalisation
of the Haar measure, the relative measures for extensions $L/K$ where
$K\neq\mathbb{Q}$ are not self-dual. Therefore the Poisson summation formula
holds with a non-trivial constant. It is exactly this constant that produces
the correction term in the relative Euler characteristic, as shown in the
above calculation.

######  Remark 5.2.

This formula agrees with [1, Theorem 5.3] and [14, Proposition 1] for
$K=\mathbb{Q}$. It also agrees with the one given by the Grothendieck-Riemann-
Roch theorem (see [11, Chepter III §7, §8] for the arithmetic case. We have
the same formulas for the geometric case). Therefore we have the full right to
call our Euler characteristic and Rieman-Roch theorem relative.

Note that the Euler characteristics can be written in the following form

$\chi_{L/K}(D_{\alpha})=\log{\int\limits_{\mathbb{A}_{L}}f_{\alpha}}{\left(\,\,{\int\limits_{\mathbb{A}_{K}}f_{1}}\right)^{-[L:K]}}=\log{\int\limits_{\mathbb{A}_{L}}f_{\alpha}}{\left(\,\,{\int\limits_{\mathbb{A}_{L}}f_{K,1}}\right)^{-1}}.$

where $K\subset L$ is a finite extension of one-dimensional global fields and
$f_{K,1}$ is

$(f_{K,1})_{w}=\left\\{\begin{array}[]{lrl}\mathrm{char}_{O_{v}}(u_{v})&v|w\text{
non-archimedean}\\\ &\\\ \exp{(-e_{v}\pi|u_{v}|_{v}^{2/e_{v}})}&v|w\text{
archimedean }.\end{array}\right.$

where $W$ ranges over places of $L$ and $O_{v}$ is the ring of integers of the
local field $K_{v}$ of $K$.

##  6 Future perspectives

As we mentioned before the relative Riemann-Roch theorem is used in the
horizontal divisor part of the proof of the Falting-Riemann-Roch theorem. The
next very important ingredient is the Arakelov adjunction formula. It is an
interesting question if one can extend the ideas presented in this paper to
obtain a global reformulation of the formula. It is also natural to ask if the
method generalises to higher dimensions. In collaboration with P.Dolce and
I.Fesenko. we obtained very promising results in dimension two. There exists
generalization of adeles to any scheme called Beilinson adeles ([6]). It was
extended to the case of arithmetic surfaces in [2]. It is well known that it
is not possible to develop a desirable theory of integration on two-
dimensional Beilinson adeles ([4],[3]). Nevertheless, the Faltings metric on
the determinant of cohomology suggests that we rather want to measure the
cohomology spaces than the whole space of adeles. Our work shows that it is
indeed possible to integrate on adelic spaces corresponding to cohomology
spaces. Naturally the main difficulty is to capture the Faltings metric at the
places at infinity. Here is another reason where the Arakelov adjunction
formula, which constitutes a bridge between dimension one and dimension two,
could be very useful. It would be also interesting to check if the theory
presented in this paper is compatible with [10].

##  Appendix A Fourier analysis on non-archimedean local fields

In this appendix we briefly recall the basic results of Fourier analysis on
one-dimensional non-archimedean local fields.

Let $K$ be a global field, let $v$ be a non-archimedean place of $K$ and fix a
uniformising element $\pi_{v}$. Then the completion $K_{v}$ is a finite
extension of the field $Q$ that can be either $\mathbb{Q}_{p}$ or
$\mathbb{F}_{p}((t))$ for a prime number $p$ and we fix $[K_{v}:Q]=n$. The
residue field of $K_{v}$ is denoted by $k(v)$, we have
$[k(v)\colon\mathbb{F}_{p}]=d\leq n$ and we fix the following absolute value
on $K_{v}$

$x\mapsto|x|_{v}:=(\\#k(v))^{-v(x)}.$

Let $\mu_{v}$ be _any_ Haar measure on $K_{v}$; we recall that for any
measurable set $S\subseteq K_{v}$ and any $x\in K_{v}$ it holds that:

$\mu(xS)=|x|_{v}\mu(S)$

On $Q$ there is the following choice of standard character $\psi_{v}$.

  * •

If $Q=\mathbb{Q}_{p}$, we fix the following map
$\Lambda:\mathbb{Q}_{p}\to\mathbb{R}$:

$\Lambda(x):=\sum^{-1}_{i=-k}a_{i}\quad\text{ if $x=\sum_{i\geq-k}a_{i}p^{i}$
and $a_{i}\in\\{0,\ldots,p-1\\}$}$

and we put

$\displaystyle\psi_{v}\colon\mathbb{Q}_{p}$ $\displaystyle\to$
$\displaystyle\mathbb{S}^{1}$ $\displaystyle x$ $\displaystyle\mapsto$
$\displaystyle\exp(-2\pi i\Lambda(x))$

  * •

If $Q=\mathbb{F}_{p}((t))$

$\displaystyle\psi_{v}:\mathbb{F}_{p}((t))$ $\displaystyle\to$
$\displaystyle\mathbb{S}^{1}$ $\displaystyle\sum_{i}a_{i}t^{i}$
$\displaystyle\mapsto$ $\displaystyle\exp\left(\frac{2\pi
i\widetilde{a}_{-1}}{p}\right)$

where $\widetilde{a}_{-1}$ is any lift to $\mathbb{Z}$ of the coefficient
$a_{-1}$.

At this point the standard character $\chi_{v}:K_{v}\to\mathbb{S}^{1}$ is
defined as $\chi_{v}:\psi_{v}\circ\operatorname{Tr}_{K|K_{0}}$.

######  Lemma A.1.

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

$\int_{\pi_{v}^{m}O_{v}}\\!\\!\chi_{v}(x)dx=\begin{cases}(p^{d})^{-m}\mu_{v}(O_{v})&\text{if
$m\geq 0$}\\\ 0&\text{otherwise}\end{cases}$

###### Proof.

_Case $m\geq 0$._ Remember that the trace map sends $O_{v}$ to the ring of
integers of $K_{0}$, therefore then $\chi_{v}(x)$ restricted to
$\pi_{v}^{m}\mathcal{O}_{v}$ is identically $1.$ It means that the integral is

$\mu_{v}(\pi_{v}^{m}O_{v})=(p^{d})^{-m}\mu_{v}(O_{v})\,.$

_case $m<0$._ There exists $y\in\pi_{v}^{m}O_{v}$ such that $\chi_{v}(y)\neq
1$, then after making the change of variables $x\mapsto x+y$ we get:

$\int_{\pi_{v}^{m}O_{v}}\\!\\!\chi_{v}(x)dx=\int_{\pi_{v}^{m}O_{v}}\\!\\!\chi_{v}(x+y)dx=\chi_{v}(y)\int_{\pi_{v}^{m}O_{v}}\\!\\!\chi_{v}(x)dx$

Hence the only possibility is
$\displaystyle\int_{\pi_{v}^{m}O_{v}}\\!\\!\chi_{v}(x)dx=0$. ∎

######  Lemma A.2.

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

$\int_{K_{v}}\operatorname{char}_{\pi^{m}\mathcal{O}_{v}}(x)\chi_{v}(-xy)dx=\begin{cases}(p^{d})^{-m}\mu_{v}(O_{v})&\text{if
$y\in\pi_{v}^{-m}O_{v}$}\\\ 0&\text{otherwise}\end{cases}$

###### Proof.

If $y\in\pi_{v}^{-m}O_{v}$, then $xy\in\mathcal{O}_{v}$ for
$x\in\pi_{v}^{m}O_{v}$, hence the integral reduces to

$\int_{\pi_{v}^{m}\mathcal{O}_{v}}dx=\mu_{v}(\pi_{v}^{m}O_{v})=p^{-dm}\mu_{v}(\mathcal{O}_{v}).$

If $y\notin\pi_{v}^{-m}O_{v}$ then the integrand is not the constant $1$ and
with the same change of variables of the proof of Lemma (A.1) one shows that
the integral is $0$. ∎

Thus we are able to write explicitly the Fourier tranform

$\widehat{f}(x):=\int_{K_{v}}f(y)\chi_{v}(-xy)dy$

when $f=\operatorname{char}_{\pi_{v}^{m}\mathcal{O}_{v}}$:

$\widehat{\operatorname{char}}_{\pi_{v}^{m}O_{v}}(x)=\int_{K_{v}}\operatorname{char}_{\pi_{v}^{m}O_{v}}(y)\chi_{v}(-xy)dy=\int_{\pi_{v}^{m}O_{v}}\chi_{v}(-xy)dy=$
$=(p^{d})^{-m}\mu_{v}(O_{v})\operatorname{char}_{\pi_{v}^{-m}O_{v}}(x)$

where the last equality follows from Lemma A.2.

## References

  * [1] A. Borisov.  Convolution structures and arithmetic cohomology.  Compositio Mathematica, 136(3):237–254, 2003.
  * [2] W. Czerniawska and P. Dolce.  Adelic geometry on arithmetic surfaces II: Completed adeles and idelic Arakelov intersection theory.  J. Number Theory, 211:235–296, 2020.
  * [3] I. Fesenko.  Adelic approach to the zeta function of arithmetic schemes in dimension two.  Mosc. Math. J., 8(2):273–317, 399–400, 2008.
  * [4] I. Fesenko.  Analysis on arithmetic schemes. II.  J. K-Theory, 5(3):437–557, 2010.
  * [5] V.P. Havin, N.K. Nikolski, D. Dynin, S. Dynin, and V.P. Gurarii.  Commutative Harmonic Analysis II: Group Methods in Commutative Harmonic Analysis (Encyclopaedia of Mathematical Sciences (25)).  Springer, 10 2012.
  * [6] A. Huber.  Adèle für Schemata und Zariski-Kohomologie.  In Schriftenreihe des Mathematischen Instituts der Universität Münster, 3. Serie, Heft 3, volume 3 of Schriftenreihe Math. Inst. Univ. Münster 3. Ser., page 86. Univ. Münster, Math. Inst., Münster, 1991.
  * [7] M. Jarden and G. Prasad.  The discriminant quotient formula for global fields.  Publications Mathematiques De l’IHES, 69:115–117, 12 1989.
  * [8] K. Kato and F. Trihan.  On the conjecture of Birch-Swinnerton-Dyer in characteristic $p>0$.  Inventiones Mathematicae, 153:537–592, 2003.
  * [9] S. Lang.  Introduction to Arakelov Theory.  Springer, 1988.
  * [10] T. McMurray Price.  Numerical cohomology.  Algebraic Geometry, 4(2):136–159, mar 2017.
  * [11] J. Neukirch.  Algebraic Number Theory (Grundlehren der mathematischen Wissenschaften, 322).  Springer, hardcover edition, 5 1999.
  * [12] D. Ramakrishnan and R.J. Valenza.  Fourier Analysis on Number Fields.  Graduate Texts in Mathematics. Springer New York, 2013.
  * [13] J. T. Tate.  Fourier analysis in number fields, and Hecke’s zeta-functions.  In Algebraic Number Theory (Proc. Instructional Conf., Brighton, 1965), pages 305–347. Thompson, Washington, D.C., 1967.
  * [14] G. van der Geer and R. Schoof.  Effectivity of Arakelov divisors and the theta divisor of a number field.  Selecta Math. (N.S.), 6(4):377–398, 2000.
  * [15] A. Weil.  On the Riemann hypothesis in function-fields.  Proc. Nat. Acad. Sci. U.S.A., 27:345–347, 1941.
  * [16] A. Weil.  Basic Number Theory.  Springer, paperback edition, 2 1995.