∎

11institutetext:  Walter Ikegami Andersson 22institutetext: Adeel Akram
33institutetext: Tord Johansson 44institutetext: Michael Papenbrock
55institutetext: Jenny Regina 66institutetext: Karin Schönning
77institutetext: Uppsala Universitet, Institutionen för fysik och astronomi,
Uppsala, Sweden 88institutetext: Ralf Kliemt 99institutetext: Helmholtz-
Institut Mainz, Mainz, Germany 1010institutetext: Tobias Stockmanns
1111institutetext: Forschungszentrum Jülich, Institut für Kernphysik, Jülich,
Germany

# A Generalized Approach to Longitudinal Momentum Determination in Cylindrical
Straw Tube Detectors

Walter Ikegami Andersson  Adeel Akram  Tord Johansson  Ralf Kliemt  Michael
Papenbrock  Jenny Regina  Karin Schönning  Tobias Stockmanns

(Received: date / Accepted: date)

###### Abstract

The upcoming PANDA experiment at FAIR will be among a new generation of
particle physics experiments to employ a novel event filtering system realised
purely in software, i.e. a software trigger. To educate its triggering
decisions, online reconstruction algorithms need to offer outstanding
performance in terms of efficiency and track quality. We present a method to
reconstruct longitudinal track parameters in PANDA’s Straw Tube Tracker, which
is general enough to be easily added to other track finding algorithms that
focus on transversal reconstruction. For the pattern recognition part of this
method, three approaches are employed and compared: A combinatorial path
finding approach, a Hough transformation, and a recursive annealing fit. In a
systematic comparison, the recursive annealing fit was found to outperform the
other approaches in every category of quality parameters and reaches a
reconstruction efficacy of 95% and higher.

###### Keywords:

Track reconstruction Annealing fit Hough Transformation

##  1 Introduction

Modern experimental particle physics would be unthinkable without the aid of
computers. Early detectors would yield visual event signatures that could be
discerned by the human eye (e.g. cloud ). Later, algorithms were introduced
for the identification of particle trajectories, not the least due to the
ever-increasing amounts of data. With time, both accelerator and detector
technology improved, leading to larger event and data rates as well as more
complex signatures. As a result, the explored physics landscape grew larger
and a considerable part of the ”low-hanging fruits” could be collected. We
have now reached a point where most of the interesting physics signals are not
only rare, but also look so similar to the background that they can be
difficult to distinguish. Intelligent software that can find the proverbial
needle in the all-growing haystack, is a prerequisite for further progress in
particle physics.

In this article, we contribute with one piece of the puzzle by presenting a
method for reconstructing longitudinal track components in a cylindrical straw
tube detector located in a solenoid magnetic field. While many existing
methods are adapted for tracks originating from the beam-target interaction
point, this method applies to all tracks, also those from the decays of long-
lived particles such as hyperons. We implement this method for the PANDA
experiment, a next-generation facility for hadron physics that is currently
under construction at FAIR in Darmstadt, Germany. We put particular emphasis
on resolving the spatial ambiguity that arises during track reconstruction in
a cylindrical drift detector. Three different algorithms have been tested for
this purpose.

##  2 The PANDA detector

Figure 1: The PANDA detector.

PANDA (antiProton ANnihilations at DArmstadt) , shown in Fig. 1, is designed
as a fixed-target, multi-purpose detector with a wide variety of physics
channels and different reaction topologies in mind. To enable the exclusive
measurement, i.e. reconstruction of all final state particles emerging from a
given reaction, PANDA will cover almost 4$\pi$ of the solid angle and comprise
a range of sub-detectors for the reconstruction of both charged and neutral
particles. The subdetectors are grouped into two main segments: The target
spectrometer, employing a solenoid magnetic field and covering the polar angle
range $10^{\circ}<\theta<160^{\circ}$, and the forward spectrometer, using a
dipole magnetic field and covering the region of $\theta<10^{\circ}$ and
$\theta<5^{\circ}$ in horizontal and vertical direction, respectively. The
purpose of the method presented in this work is to reconstruct the
longitudinal track component of charged particles traversing the target
spectrometer. It utilises the Micro Vertex Detector (MVD) as well as the Straw
Tube Tracker (STT).

###  2.1 The Micro Vertex Detector

The MVD is a cylindrical pixel- and double-sided strip detector enclosing the
interaction point. Its main purpose is to resolve the location of secondary
decays of long-lived particles such as hyperons or hadrons with open-charm.

The MVD consists of a barrel and a forward part. The barrel part is made of
four cylindrical detector layers; the innermost layer has a radius of 2.5 cm
and the outermost a radius of 13.5 cm. The barrel covers a scattering angle
range between $40^{\circ}$ and $150^{\circ}$. The two inner layers consist of
silicon hybrid pixels of dimension $100\times 100\,\mu$m2. The two outer
layers consist of double sided strip detectors. The forward part is made of
six disk layers and covers a scattering angle range between $3^{\circ}$ and
$40^{\circ}$. The first disk is located 2 cm downstream from the interaction
point, the last disk 23 cm. The first four layers consist of pixel detectors,
whereas the last two layers are made up of both pixel and strip detectors.

The MVD is designed to provide a vertex resolution of 100 $\mu$m in the beam
direction and a few tens of $\mu$m in the radial direction. Combined with the
STT and GEM detectors, PANDA will achieve a momentum resolution of
$\sigma_{p}/p<1\%$ mvd_tdr .

###  2.2 Straw Tube Tracker

The STT is the main tracking detector of the target spectrometer and surrounds
the MVD. Being inside a solenoid field, charged particles traverse it along
helical trajectories. The STT is designed for particles in a momentum range
from a few hundred MeV/c up to 8 GeV/c and a scattering angle range between
$22^{\circ}$ and $140^{\circ}$.

The detector consists of 4224 gas-filled tubes, arranged in a hexagonal layout
and filling a cylindrical volume. A vertical gap is left at the centre to make
room for the target system. The inner and outer tube layers are oriented
parallel to the beam pipe, whereas the 8 intermediate layers are tilted by
$\pm 2.9^{\circ}$. The purpose of the latter is to provide longitudinal
information about the particle trajectories. A cross section of the STT is
shown in Fig. 2, where the parallel tubes are presented in green and the
skewed tubes in red or blue.

Figure 2: Cross sectional view of the Straw Tube Tracker in the $xy$-plane.
The green circles represent parallel straws, the blue and red circles the
skewed straws.

The tubes are made from a $27\mu$m thick mylar foil with 10 mm in diameter and
filled with a 90/10 gas mixture of Ar/CO2. The tubes have a conductive inner
layer and a 20 $\mu$m thick gold-plated tungsten anode wire at the centre. A
potential differential of several kV is applied between the cathode layer and
the anode wire. Charged particles traversing the tube ionize the gas,
producing free ions and electrons that are accelerated towards the anode wire.
In the vicinity of the wire ($\mathcal{O}(10\,\mu\textrm{m})$) they produce
more free electrons and ions in an avalanche-like manner, which in turn
results in a signal, large enough for readout.

The time it takes the electrons to reach the anode wire is called the drift
time. By measuring the shortest drift time within a signal, the minimal
distance between the wire and the charged track can be inferred. This distance
is usually referred to as the isochrone radius, which describes a cylindrical
surface around the wire and contains all possible positions that the particle
might have traversed. This is illustrated in Fig. 3.

Figure 3: An illustration of a particle traversing three straw tubes, shown in
the $xy$-plane. The isochrones are represented by blue circles. The green
point indicates the correct position where the distance to the wire is minimal
and the track is tangential to the isochrone.

After a series of straw tubes has been associated to a common track candidate,
the particle track is reconstructed by fitting a trajectory such that it is
tangential to the isochrones. The resolution of the isochrone radius will be
$<150\,\mu$m, whereas the resolution of $z$-position along the wire will be
about 3 mm stt_tdr .

##  3 Pattern recognition

Track reconstruction begins with pattern recognition. In this phase, signals
from individual detector elements are associated to a common track,
originating from the traversing particle. The output consists of sets of hits
together with an initial estimate for the track parameters, e.g. based on a
simple helix fit. The final track parameters are obtained later using a more
sophisticated, usually adaptive fitting method that takes into account
physical effects such as energy loss, as well as imperfections in the
detector. However, at the pattern recognition stage, it is often not only
convenient but also necessary to disregard these effects and instead use the
helix shape as an approximation to the particle trajectory.

###  3.1 Track representation

Assuming that the trajectory of a particle with charge $Q$ moving in the
solenoid field of the target spectrometer can be approximated by a helix or
radius $r$, five parameters are needed to describe the track. A sixth
parameter can be added to define a point along the helix trajectory.

The PANDA target spectrometer has a cylindrical design. A superconducting
solenoid provides an approximately homogeneous magnetic field for the whole
detector volume, bending the trajectories of charged particles into helices
around an axis parallel to the beam axis. Choosing the $z$-axis along the beam
direction, the track can be explicitly represented by the following five
parameters:

  * •

$x_{c}$ \- horizontal coordinate of the helix centre

  * •

$y_{c}$ \- vertical coordinate of the helix centre

  * •

$\omega=Q/r$ \- signed curvature of the helix

  * •

$\phi_{0}$ \- azimuthal angle at the reference $z_{0}$

  * •

$\tan\lambda$ \- dip angle of the helix with $\lambda=\arctan p_{z}/p_{t}$

In this representation, the helix can be analytically described in two
projections. In the $xy$-projection the helix becomes a circle, defined as

$(x-x_{c})^{2}+(y-y_{c})^{2}=r^{2}.$ (1)

It is reduced to a line in the $z\phi$-projection, i.e.

$\phi(z)=kz+\phi_{0},$ (2)

with the slope parameter $k\equiv\tan\lambda$. The azimuthal angle $\phi$ can
be replaced by the arc length

$S=(\phi_{0}-\phi)rQ,$ (3)

where $Q$ is the charge of the track. The arc length is defined such that it
is zero at the starting point of the track and increases positively,
regardless of the charge. The linear relation then becomes

$z(S)=\tan\lambda S+z_{0}.$ (4)

Eq. (4) simplifies the problem considerably, and the task reduces to
identifying a line among a set of points in the $Sz$-space.

##  4 Longitudinal track reconstruction

Figure 4: The isochrone alignment procedure. The isochrone ellipse (red) in
the $xy$-projection is aligned along the STT tube projection such that it is
tangential to the track (black curve). Two possible solutions for the
$z$-position are obtained, $z_{1}$ and $z_{2}$.

The PANDA software framework, PandaRoot pandaroot , contains a variety of
global and local track finding algorithms. While the global methods aim to
take the whole detector into account, the local methods focus on one or few
sub-detectors, such as the Straw Tube Tracker. For the STT in particular, the
existing local track finders focus on reconstructing the transversal track
components. To supplement these track finders, a set of algorithms dedicated
to the extraction of longitudinal position and momentum information of track
candidates was developed and named the PzFinder after the third momentum
component. Since the PzFinder is used during the early stage of the track
reconstruction, the particle trajectory is approximated by a helix which is
described as in Sec. 3.1. The PzFinder requires the three parameters
$x_{c},y_{c}$, and $Q/r$ to be known and provides estimates for $\phi_{0}$ and
$\tan\lambda$ in return, yielding a complete description of the track.

Using this approximation, the track becomes a circle in the $xy$-projection
with constant transversal and longitudinal momentum components $p_{t}$ and
$p_{z}$, respectively. Hence, the particle traverses at a constant rate in $z$
with respect to the helix axis. According to Eq. (4), all true hit positions
of a track candidate should then lie on a straight line in the $(S,z)$
coordinate space.

The $z$-position for each hit in a skewed STT tube is extracted through an
isochrone alignment procedure, illustrated in Fig. 4. The isochrone radius for
each hit is determined beforehand outside the PzFinder. Since these tubes are
skewed, the projection of the isochrone onto the $xy$-plane becomes an
ellipse. The isochrone is aligned such that its centre position lies along the
wire and is tangential to the particle trajectory. This alignment implicitly
gives a solution for the $z$-position. However, during the alignment
procedure, two solutions/points are obtained, introducing a left/right
ambiguity with one solution on either side of the trajectory.

In the following, three different methods are presented to resolve this
ambiguity.

###  4.1 Combinatorial path finder

(a)

(b)

Figure 5: A visualisation of the combinatorial path finder.
LABEL:sub@subfig:combi1 All possible connections are considered. The black
lines are generated by the algorithm to calculate angles. The encircled points
are the $(S,z)$ points that were selected as part of the straightest path.
LABEL:sub@subfig:combi3 Only the lines corresponding to the found path remain.

A combinatorial approach was developed to find the ”straightest” path from one
end of the track to the other, similar to a track road procedure
tracking_overview . First, all possible connections between the $(S,z)$
solutions of neighbouring STT tubes are determined. With two $(S,z)$ solutions
for each hit, this yields four possible connections between neighbouring
tubes. Fig. 5 illustrates the procedure. Given a track candidate with $N$ hits
in the skewed STT layers, the total number of generated lines is $4(N-1)$.
Since there are eight layers of skewed STT tubes, a typical track passing
fairly straight through all these layers will have 24 connections to be
considered.

The ”straightest” path is determined by evaluating the cost function

$w=\sum^{n}_{j}(180^{\circ}-\theta_{j})^{2},$ (5)

where $\theta_{j}$ is the opening angle between two lines connecting at the
same $(S,z)$ point. With two possible points for each STT hit, this leaves
$2^{N}$ possible paths to be evaluated. To reduce the computational footprint,
paths containing an opening angle smaller than $90^{\circ}$ are discarded
right away. Among the remaining points, the correct ones are chosen by
minimising the cost function Eq. (5). In Fig. 5, the selected positions are
marked by blue circles. For this example track, these positions are also the
ones that are closest to the true positions, marked by green stars. This
indicates that the selection process was successful.

The combinatorial nature of this approach brings about a possibly high
computational cost. Since the STT has eight layers of skewed tubes, any fairly
straight particle trajectory creates eight or nine skewed STT hits, resulting
in 256 or 512 combinations to be evaluated. Tracks with a higher curvature can
leave even more hits, increasing the number of combinations exponentially.
Furthermore, the algorithm assumes that all skewed STT hits have been
correctly associated with the track by the preceding pattern recognition.

These considerations leave room for other options to be explored.

###  4.2 Hough transformation

The Hough transformation hough  has been a staple in track reconstruction in
particle physics for more than half a century. It was designed to detect
simple shapes, originally lines, but later also more complex one such as
circles or ellipses hough_more . Since the parameterisation of these shapes
becomes part of the algorithm, it performs best when the points follow this
parameterisation closely and the shape is not distorted by secondary effects
such as energy loss. Since the problem at hand is about finding points on the
same line in $(S,z)$ space, it is reasonable to expect that the classical
Hough transformation could be a good solution.

In order to avoid unbound parameters, the line is described using the Hesse
normal form with the closest distance to the origin $R$ and the inclination
angle $\theta$:

$R=z\cos\theta+S\sin\theta$ (6)

In the Hough transformation a set of lines is generated for each point. All
lines go through the point, but at different inclination angles. The line
parameters are then filled into an accumulator space that is spanned by
$\theta$ and $R$. In the accumulator space, local maxima will emerge for line
parameters that connect multiple points. In our case, the algorithm searches
for only one line connecting the largest number of points. Hence, the
corresponding parameters can be found by selecting the global maximum in the
accumulator space. The $(S,z)$ points contributing to this maximum are chosen
as the correct ones. The procedure is illustrated in Fig. 6. In case the
global maximum is ambiguous, i.e. two bins with the maximum number of entries
are present, a line fit for both sets of $(S,z)$ hits is performed and the bin
resulting in the smallest $\chi^{2}$ is selected as the correct one.

(a)

(c)

(b)

(d)

Figure 6: A visualisation of the Hough transformation algorithm. (a) $(S,z)$
points with three example hits highlighted. (b), (c) and (d), the accumulator
space after the line parameters of hits 1, 2 and 3 have been added,
respectively.

The algorithm can incorporate hits from the MVD detector to improve the
procedure. However, these have to be supplied by a separate, local pattern
recognition algorithm. The method can be extended to reject false MVD hits as
well.

###  4.3 Recursive annealing fit

Annealing procedures found their way into track reconstruction several decades
ago tracking_overview . One possible application is to remove wrongly matched
hits from a track and thereby improve the track fit annealing_belleii . Thus,
the recursive annealing fit operates by removing outliers within a set of
measurements. The rejection of these outlying measurements can be based on the
measurement of a residual, here the distance between one $(S,z)$ point and a
line fit to all $(S,z)$ points.

The initial line fit is performed to all $(S,z)$ points in a track candidate.
Since the detector resolution is much better in the transversal direction than
in the longitudinal, only the uncertainty of the $z$-component of the position
is taken into account. Given that an iterative minimisation has to be
performed, this is a helpful simplification of the fit. The line expression in
Eq. (4) is fitted to the points to extract the slope $\tan\lambda$ and the
starting position $z_{0}$. The fit minimises the $\chi^{2}$

$\chi^{2}=\sum_{i}^{n}\frac{(z_{i}-kS_{i}-z_{0})}{\sigma_{i}^{2}}$ (7)

with respect to the slope $k$ and the intercept $z_{0}$. The index $i$ runs
over all $(S,z)$ points and the uncertainty $\sigma_{z}$ of the $i$-th hit is
denoted $\sigma_{i}$.

The $(S,z)$ points with the largest contribution to the $\chi^{2}$ are
rejected from the skewed STT hits after the initial fit. Specifically, the
$(S,z)$ point with the largest residual is removed and the remaining points
are fitted anew. This procedure is repeated until one $(S,z)$ point has been
removed for every skewed STT hit.

##  5 Data samples

To evaluate the algorithms, two different sets of data samples were produced.

First, a particle generator was used to simulate 1000 events with four muons,
two of each charge, orginating from the interaction point and isotropically
and monochromatically distributed. This was done with each of the momenta of
0.1, 0.2, 0.5, 1.0, 2.0, and 5.0 GeV/c to cover a wide range of expected
particle momenta. Muons have two main advantages: i) they interact mainly
electromagnetically with the detector material, hence their measurement is
less obscured by strong processes compared to hadrons and ii) being 200 times
heavier than electrons, they are less prone to change direction through
scattering. The muons in these samples originate from the interaction point
and are emitted uniformly within the acceptance of the Straw Tube Tracker,
i.e. the polar angle $\theta\in[22^{\circ},140^{\circ}]$ and the azimuthal
angle $\phi\in[0^{\circ},360^{\circ}]$.

More general data sets are provided by the Dual Parton Model generator dpm ,
offering a realistic composition of known processes that occur in
$\overline{p}p$ collisions. Four samples at the beam momenta 1.642, 4.6, 7.0,
and 15.0 GeV/c, with 5000 events in each sample, were produced in this study.
The first three points bear relevance to specific physics channels, whereas
the fourth point corresponds to the maximum beam momentum at which the PANDA
experiment will operate.

##  6 Results

###  6.1 Efficienty and Purity

(a)

(b)

Figure 7: Sample efficiency LABEL:sub@subfig:pzperf_eff and purity
LABEL:sub@subfig:pzperf_pur of $(S,z)$ points selected by the Recursive
Annealing fit (black dots), Combinatorial Path Finder (blue upwards
triangles), and Hough transformation (red downwards triangles). The
statistical uncertainties have been calculated, but vanish behind the markers
in the plot.

As a first step, the performance of the PzFinder is assessed by investigating
the efficiency and purity of the $(S,z)$ point selection, i.e. the resolution
resulting from the left-right ambiguity. It is assumed that for each skewed
STT hit in a track candidate one correct and one false $(S,z)$ point exists.
The $(S,z)$ point closest to in $z$ to the Monte Carlo truth position is then
selected as the correct one. The selection efficiency is defined as

$\epsilon=\frac{N_{hit}}{N_{hit}^{MC}},$ (8)

where $N_{hit}$ is the number of found hits that belong to one reference track
and $N_{hit}^{MC}$ the total number of hits created by that reference track.
Introducing the total number of found hits as $N_{hit}^{tot}$, the purity is
given as

$purity=\frac{N_{hit}}{N_{hit}^{tot}}.$ (9)

The efficiencies and purities of the three algorithms are shown in Fig. 7 for
the momentum points described in Sec. 5. While all three algorithms reach
$80\%$ for momenta above 0.2 GeV/c in both observables, the Recursive
Annealing Fit performs best with efficiencies and purities above $95\%$.

###  6.2 Hough transformation binning

Naturally, the bin width of $R$ and $\theta$ can have great impact on the
efficiency of this procedure. The choice of a proper bin width is often
informed by external parameters, such as the detector resolution.

Figure 8: RoC curve of the Hough transformation algorithm with different bin
widths of the accumulator space. Each point is classified by the number of
bins in $R$ and $\theta$. The optimal choice is highlighted in red.

To find the optimal binning for sec. 6.1, different numbers of bins were
tested on a sample of 1 GeV/c muons: $N^{R}_{bin}=25,50,100$ and
$N^{\theta}=45,90,180$ for the parameters $R$ and $\theta$, respectively. Fig.
8 displays the purity and efficiency for these binnings as a pseudo Receiver
Operating Characteristics curve (ROC curve), illustrating the performance of
binary classifiers.

The figure shows a good balance of binning choices, as some favour efficiency
over purity and vice versa. The parameter set closest to (1,1) on the curve is
chosen as optimal. Henceforth, the Hough transformation was used with the
parameters $N^{R}_{bin}=25$ and $N^{\theta}_{bin}=90$. The optimal binning for
this procedure depends on the detector resolution and thereby on the particle
momentum. However, with further increasing particle momenta, the momentum
resolution increases and hence this binning will remain a good choice.

###  6.3 Spatial Resolution

(a)

(b)

Figure 9: Example distributions determining the distribution mean, root mean
square, and standard deviation. A Gaussian function was fitted in both cases
(red line). LABEL:sub@subfig:z The reconstructed longitudinal position $z$.
LABEL:sub@subfig:pl The reconstructed longitudinal momentum $p_{l}$. The plots
were produced from a data sample with muons with a momentum of 1 GeV/c.

(a)

(b)

(c)

Figure 10: Quality observables of the $z$-position of $(S,z)$ points selected
by the Recursive Annealing fit (black dots), Combinatorial Path Finder (blue
upwards triangles), and Hough transformation (red downwards triangles). Shown
are distribution mean LABEL:sub@subfig:deltazmean, the root mean square
LABEL:sub@subfig:deltazrms, and the standard deviation
LABEL:sub@subfig:deltazstd.

(a)

(b)

(c)

Figure 11: Quality observables of the longitudinal momentum $p_{l}$ of track
reconstructed by the Recursive Annealing fit (black dots), Combinatorial Path
Finder (blue upwards triangles), and Hough transformation (red downwards
triangles). Shown are distribution mean LABEL:sub@subfig:plresmean, the root
mean square LABEL:sub@subfig:plresrms, and the standard deviation
LABEL:sub@subfig:plresstd.

After selecting the $(S,z)$ points of a track candidate with the PzFinder, the
spatial reconstruction quality can be assessed by studying the $z$-position
error
$\Delta z=z_{rec}-z_{MC}$ for each hit. An example distribution for the
reconstructed longitudinal position $z$ of 1 GeV/c muons is shown in Fig. 9a.
Since the distribution does not always follow a well defined Gaussian shape,
the standard deviation was approximated from the Full Width at Half Maximum
(FWHM) using

$\sigma_{z}=\textrm{FWHM}/2.355.$ (10)

Fig. 10 shows the $\Delta z$ distribution mean, root mean square, and standard
deviation for all three algorithms. Above particle momenta of $0.1\,$GeV/c,
the mean values of the distributions are close to zero. The root mean square
values are around 3 cm for higher particle momenta. The standard deviation, on
the other hand, quickly reaches values below 5 mm. Even before using an
adaptive fitting method, e.g. Kalman Filter kalman , this comes close to the
design value for the resolution of 3 mm stt_tdr .

###  6.4 Longitudinal Momentum Resolution

To assess the quality of the longitudinal momentum reconstruction, we define
the relative longitudinal momentum resolution as

$Res(p_{l})=\frac{\left(p_{l}^{rec}-p_{l}^{MC}\right)}{p_{l}^{MC}},$ (11)

with $p_{l}^{rec}$ and $p_{l}^{MC}$ being the reconstructed and Monte Carlo
momentum, respectively. An example distribution of the reconstructed
longitudinal momentum $p_{l}$ for 1 GeV/c muons can be seen in fig. 9b. The
same considerations as in sec. 6.3 also apply here. The quality parameters for
the longitudinal momentum reconstruction are shown in Fig. 11: the mean of the
longitudinal momentum distribution, the root mean square, and the standard
deviation. All three algorithms perform similarly, with the Recursive
Annealing Fit slightly outperforming the others. The root mean square and
standard deviation are lowest in the range of $0.2-0.5\,$GeV/c. As stated
before, low momentum particles are difficult to reconstruct with accuracy and
precision. At higher momenta, the particle trajectories become straighter,
introducing a larger uncertainty to the momentum reconstruction.

###  6.5 DPM samples

(a)

(b)

(c)

(d)

(e)

(f)

Figure 12: Quality observables for the Recursive Annealing fit (black dots),
Combinatorial Path Finder (blue upwards triangles), and Hough transformation
(red downwards triangles) applied on several data samples using a DPM
generator at several simulated momenta of the antiproton beam. Shown are the
efficiency LABEL:sub@subfig:pleff_dpm, the purity LABEL:sub@subfig:plpur_dpm,
the distribution mean for the $z$-position reconstruction
LABEL:sub@subfig:deltazMean_dpm and the corresponding standard deviation
LABEL:sub@subfig:deltazStd_dpm, as well as the distribution for reconstructed
longitudinal momentum $p_{l}$ LABEL:sub@subfig:plresMean_dpm and the
corresponding standard deviation LABEL:sub@subfig:plresStd_dpm.

In addition to clean muons, the PzFinder was tested on samples generated using
a DPM generator. The corresponding quality observables are given in fig. 12.
As before, the Recursive Annealing Fit outperforms the other methods in terms
efficiency and purity, yielding values of 95% and higher. The quality of the
spatial and momentum reconstruction is comparable to the clean muon case.

###  6.6 Run-time performance

Figure 13: Run-time performance numbers in milliseconds. From left to right:
no PzFinder, Recursive Annealing Fit, Combinatorial Path Finder, Hough
Transformation. Add a better description here. Different parts of of the
reconstruction code were measured: The preceding event reconstruction (yellow,
horizontally striped), the interface between the PzFinder and PandaRoot (blue,
vertically striped), the common part of the PzFinder (red, checkered), and the
algorithm used for resolving the left/right ambiguity (green, solid).

Efficiency, purity, and resolution observables take a dominant role when
assessing the applicability of our algorithm in an offline processing
environment, i.e. after the experiment was carried out and the data has been
taken. During online processing, though, the reconstruction algorithms have to
keep pace with the event and data rate of the ongoing experiment.

Fig. 13 shows timing measurements of four different cases, the event
reconstruction without the PzFinder, and then with the PzFinder for each of
its three different algorithms. The run-time is broken down into different
parts of the code: The event reconstruction before the invocation of the
PzFinder (yellow, horizontally striped), the interface between the PzFinder
and PandaRoot which consists mainly of exchanging data between the two (blue,
vertically striped), the bulk of the PzFinder code (red, checkered), which
includes for example the isochrone alignment procedure and writing of output,
but not the algorithm for resolving the isochrone ambiguity, which is
displayed separately (green, solid). The measurements were repeated 5 times
with the smallest run-time taken as the result. The machine used was an Intel
Core i7-4770 CPU at 3.40 GHz.

At present, the interface between the PzFinder and PandaRoot adds the largest
contribution to the event reconstruction time. With the goal in mind to keep
the tool generically usable by multiple track finders in its prototype form, a
lot of input and output data is being copied via a singleton run-time task
manager. In the future, this can be mitigated or even circumvented, for
example, by passing references and offering a more direct integration between
the PzFinder and other track finders. The PzFinder sans ambiguity resolution
itself adds about 60% to the execution time. Since this is the common part of
the tool, future optimisation will benefit all configurations. Among the three
algorithms for ambiguity resolution, the Combinatorial Path Finder adds the
largest additional run-time, close to the common part itself. The Hough
transformation is about $2.5\times$ faster. However, the Recursive Annealing
Fit outperforms the others by an order of magnitude, resulting in an almost
negligible computational footprint.

##  7 Summary

We have implemented and investigated three different algorithms for the
reconstruction of the longitudinal momentum in the Straw Tube Tracker of the
PANDA experiment. Among these three algorithms, the Recursive Annealing Fit
offered the best qualitative results, yielding efficiencies and purities of
95% and higher for particle momenta above 0.2 GeV/c. Even without adaptive
fitting, the reconstructed spatial and momentum resolution comes close to the
design goals set for the detector. When compared to the other two methods, the
computational simplicity results in faster execution times, which adds to its
appeal.

The PzFinder is constructed in such a general way that it can be added or
integrated into other track finding algorithm, that only reconstruct
transversal track components, in a straightforward way. The procedure should
also be applicable to other detectors of a similar geometry, for example the
forward tracking stations of the PANDA detector.

The results justify further investigation as to whether the Recursive
Annealing Fit should be applied to other parts of the track reconstruction
chain. The extrapolation of a locally reconstructed track to another
subdetector would be a possible use case.

## References

  * (1) N. N. Das Gupta and S. K. Ghosh, Rev. Mod. Phys., 18, 225 (1946)
  * (2) W. Erni et al., arXiv:1207.6581 (2012)
  * (3) W. Erni et al., Eur. Phys. J. A, 49, 25 (2013)
  * (4) S. Spataro, JoP: Conf. Series, 119m 032035 (2008)
  * (5) A. Strandlie and R. Frühwirth, Rev. Mod. Phys., 82, 1419-1458 (2010)
  * (6) P. V. C. Hough, Conf. Proc., C590914, 554-558 (1959)
  * (7) R. O. Duda and P. E. Hart, Commun. ACM, 15, 11-15 (1972)
  * (8) S. Spataro, EPJ Web Conf., 214, 02039 (2019)
  * (9) A. Capella et al., Physics Reports, 236, 225-329 (1994)
  * (10) R. Früwirth, Nucl. Instrum. Meth. A, 262, 444-450 (1987)


# The Fourier Transform of Restrictions of Functions on the Slice

Shravas Rao Northwestern University

###### Abstract

This paper considers the Fourier transform over the slice of the Boolean
hypercube. We prove a relationship between the Fourier coefficients of a
function over the slice, and the Fourier coefficients of its restrictions. As
an application, we prove a Goldreich-Levin theorem for functions on the slice
based on the Kushilevitz-Mansour algorithm for the Boolean hypercube.

##  1 Introduction

Boolean functions, or functions over $\\{0,1\\}^{n}$, are central to computer
science. One tool that has found many uses is Fourier analysis, which involves
defining an orthonormal basis separate from the standard basis, but with many
useful properties. One such property is that this basis consists of
eigenvectors of the Boolean hypercube, the graph whose vertices are
$\\{0,1\\}^{n}$ with an edge between two vectors $u$ and $v$ if they differ in
exactly one coordinate. Fourier analysis over the Boolean hypercube has led to
many applications, including in learning theory, property testing,
pseudorandomness, voting theory, and more. For a more complete treatment, see
[O’D14].

In recent years, much attention has been drawn to functions on the slice,
$\binom{[n]}{k}=\\{v\mid v\in\\{0,1\\}^{n},\sum_{i=1}^{n}v_{i}=k\\}$ or the
subset of $\\{0,1\\}^{n}$ that consists of vectors with exactly $k$ $1$’s for
some fixed $k$. Like in the case of the Boolean hypercube, one can also define
an orthonormal basis separate from the standard basis, over functions on the
slice. In particular, one can consider the eigenvectors of the Johnson graph,
the graph whose vertices are elements of the slice, with an edge between two
vectors $u$ and $v$ if they differ in exactly two coordinates. Thus, this
basis can be seen as an analogue of the Fourier transform, but for the slice.

Such a basis was given explicitly in [Fil16] and [Sri11], and this basis has
subsequently found many applications in analogues of major theorems for the
Boolean hypercube, but now for the slice. These include Friedgut’s theorem
[Fil16], various versions of the invariance principle [FM19, FKMW18], the
Kindler-Safra theorem [KK20], and a theorem due to Nisan and Szegedy regarding
juntas [FI19]. In this paper, we continue this line of work of proving
analogues for the slice.

Fourier analysis on the hypercube has been particularly useful when
considering restrictions of functions. In particular, if
$f:\\{0,1\\}^{n}\rightarrow\mathbb{R}$ is a function, and $z\in\\{0,1\\}^{t}$
for $t\leqslant n$, we let its restriction,
$f_{z}:\\{0,1\\}^{n-t}\rightarrow\mathbb{R}$, be the function defined by
$f_{z}(x)=f(x\circ z)$ where $\circ$ denotes concatenation. In particular, one
can relate the Fourier coefficients of $f$ with the Fourier coefficients of
$f_{z}$.

Recall that the orthonormal basis for the Fourier transform can be indexed by
subsets of the set $[n]$. Then for any $t$ and any $S\subseteq[n-t]$,

$\sum_{T\in[n]\backslash[n-t]}\widehat{f}(S\cup
T)^{2}=\sum_{z\in\\{0,1\\}^{t}}\widehat{f_{z}}(S)^{2}$ (1)

where $\widehat{f}(S)$ denotes the projection onto the vector indexed by $S$
(see Corollary 3.22 in [O’D14]).

In the case of the slice, one can also define a restriction, where given
$f:\binom{[n]}{k}\rightarrow\mathbb{R}$ and $z\in\\{0,1\\}^{t}$ for
$t\leqslant n$, we let $f_{z}:\binom{n-t}{k-|z|}\rightarrow\mathbb{R}$ be
defined by $f_{z}(x)=f(x\circ z)$, where $|z|=|\\{i:\,z_{i}=1\\}|$ denotes the
Hamming weight of $z$. If $z$ contains more than $k$ $1$’s, then $f_{z}$ is an
empty function. In this work, we show that an identity similar to Eq. (1)
holds for the slice.

In the slice, the orthonormal basis for the Fourier transform is now indexed
by subsets of $[n]$ with a certain property. Let
$\mathcal{H}_{n,\min\\{k,n-k\\}}$ be the collection of subsets
$S=\\{s_{1},s_{2},\ldots,s_{i}\\}$ of $[n]$ of size at most $k$ such that
$s_{j}\geqslant 2j$ for all $j$, when the elements of $S$ are listed in sorted
order. Then the vectors in the orthogonal basis from [Fil16] and [Sri11] can
be indexed by elements of $\mathcal{H}_{n,\min\\{k,n-k\\}}$. We note that a
vector indexed by the set $S$ in the orthogonal basis for the slice differs
significantly from the vector indexed by the same set in the orthogonal basis
for the Boolean hypercube.

The main result of this paper is the following theorem, which generalizes Eq.
(1) to the slice.

######  Theorem 1.1.

Let $f:\binom{[n]}{k}\rightarrow\mathbb{R}$, and let $i\leqslant k$.

Then for any $t$ and any $S\subseteq[n-t]$,

$\sum_{z\in\\{0,1\\}^{t}}\widehat{f_{z}}(S)^{2}=\sum_{T\subseteq[n]\backslash[n-t]}\widehat{f}(S\cup
T)^{2}$

Again, $\widehat{f}(S)$ denotes the projection onto the vector indexed by $S$.
For convenience, we will let $\widehat{f}(S)=0$ if $S$ is not a subset in
$\mathcal{H}_{n,\min\\{k,n-k\\}}$ or $f$ is an empty function.

Eq. (1) has many applications, one of which includes the Goldreich-Levin
theorem [GL89, KM93]. Informally, this theorem says that if the Fourier
coefficients of a function are concentrated on just a few vectors, then the
function can be learned efficiently. As an application of Theorem 1.1, we show
that a similar theorem applies in the case of the slice, following the
Kushilevitz-Mansour algorithm.

######  Theorem 1.2.

Given query access to a function $f\in{\binom{[n]}{k}}\rightarrow\\{-1,1\\}$
and $0<\tau\leqslant 1$, there is a $\mathit{poly}(n,1/\tau)$-time algorithm
that with high probability outputs a list $L=\\{U_{1},\ldots,U_{\ell}\\}$ of
subsets of $[n]$ such that

  * •

$|\widehat{f}(U)|\geqslant\tau\cdot\sqrt{\binom{n}{k}}$ implies that $U\in L$

  * •

$U\in L$ implies that
$|\widehat{f}(U)|\geqslant\tau/2\cdot\sqrt{\binom{n}{k}}$

###  1.1 Future Work

It would be interesting to see if Theorem 1.1 leads to other analogues of
theorems for the Boolean hypercube to the slice.

It would also be interesting to see to what extent the orthonormal basis for
slice can be extended to high-dimensional expanders, and additionally, if
there exist analogues of theorems for the Boolean hypercube on high
dimensional expanders.

Similarly to how expander graphs can be thought of as sparse approximations of
the complete graph, high dimensional expanders can be thought of as sparse
approximations of the Johnson graph. In recent years, many constructions of
high dimensional expanders have been developed [LSV05a, LSV05b, KO18, CTZ20].
The theory of constructions of high dimensional expanders have already led to
many applications in theoretical computer science, including mixing times of
Markov chains [ALGV19, AL20, CGM21] and coding theory [AJQ+20, DHK+21].

Unlike regular expander graphs, one has control beyond just the second
eigenvalue, as shown in work by Kaufman and Oppenheim [KO20]. In particular,
the spectrum of high dimensional expanders approximates the spectrum of the
Johnson graph. Both Kaufman and Oppenheim, and work by Dikstein, Dinur,
Filmus, and Harsha [DDFH18] give different decompositions into approximate
eigenspaces. The latter allows one to obtain an analogue of the Freidgut-
Kalai-Naor theorem for high dimensional expanders. It would be interesting to
obtain more explicit descriptions of approximate eigenvectors in these
approximate eigenspaces, that might allow one to prove more analogues for high
dimensional expanders. In particular, one hope is that the structure of the
orthonormal basis for the slice can used as inspiration to construct an
approximately orthonormal basis for high dimensional expanders, which can then
be used to prove analogues of theorems for the Boolean hypercube, but now for
high dimensional expanders.

##  2 Preliminaries

Denote by $[n]$ the set $\\{1,2,\ldots,n\\}$ and by $\binom{[n]}{k}$ the set
$\\{v\mid v\in\\{0,1\\}^{n},\sum_{i=1}^{n}v_{i}=k\\}$ or the subset of
$\\{0,1\\}^{n}$ that consists of vertices with exactly $k$ $1$’s for some
fixed $k$.

Given a string $x\in\\{0,1\\}^{n}$, denote by $|x|$ the Hamming weight of $x$,
that is, $|x|=\sum_{i=1}^{n}x_{i}$.

As stated in the introduction, we denote by $\mathcal{H}_{n,k}$ the set of
subsets $S=\\{s_{1},s_{2},\ldots,s_{i}\\}$ of $[n]$ of size at most $k$ such
that $s_{j}\geqslant 2j$ for all $j$, when the elements of $S$ are listed in
sorted order. Note that by Bertrand’s ballot problem, there are
$\binom{n}{|S|}-\binom{n}{|S|-1}$ sets in $\mathcal{H}_{n,k}$ of size $|S|$,
and thus $|\mathcal{H}_{n,k}|=\binom{n}{k}$.

Given a vector $v\in\mathbb{R}^{N}$ we define the $\ell_{p}$-norm by

$\|v\|_{p}^{p}=\sum_{i=1}^{N}|v_{i}|^{p}.$

We define the inner product for two vectors $u,v\in\mathbb{R}^{N}$ to be

$\langle u,v\rangle=\sum_{i=1}^{N}u_{i}v_{i}.$

It will often be convenient to index vectors by vectors rather than integers,
that is, to let $v$ be a vector in $\mathbb{R}^{\binom{[n]}{k}}$ for some $n$
and $k$. It will often be convenient to identify vectors as functions, that
is, to represent $v\in\mathbb{R}^{n}$ as $f_{v}:[n]\rightarrow\mathbb{R}$, or
$v\in\mathbb{R}^{\binom{[n]}{k}}$ as
$f_{v}:{\binom{[n]}{k}}\rightarrow\mathbb{R}$ where in both cases, one obtains
$f_{v}$ from $v$ via $f_{v}(x)=v_{x}$.

By the Cauchy-Schwarz inequality, one can relate the $\ell_{1}$-norm of a
vector with its $\ell_{2}$-norm as follows.

######  Claim 2.1.

For all $v\in\mathbb{R}^{N}$,

$\|v\|_{1}\leqslant\sqrt{N}\|v\|_{2}$

We denote by $I_{N}$ the $\mathbb{R}^{N\times N}$ identity matrix.

##  3 An orthonormal basis of eigenvectors for the Johnson graph

Recall that the Johnson graph is defined by $G=(V,E)$ where $V=\binom{[n]}{k}$
and $E=\left\\{(v,u)\mid\sum_{i=1}^{n}|v_{i}-u_{i}|=2\right\\}$. Let $A_{n,k}$
be the corresponding adjacency matrix.

In this section we give with proof an orthonormal basis of eigenvectors for
the Johnson graph. The claims and theorems in this section will be used in
Section 4 to prove Theorem 1.1. We stress that all of the results in this
section are known, and can be found in the works of Stanley [Sta88, Sta90],
Filmus [Fil16], Srinivasan [Sri11], and Filmus and Lindzey [FL20]. When
illustrative, however, we give the proofs of the various statements.

We start by defining a collection of matrices that will help yield the
eigenvectors of $A_{n,k}$.

Let $P^{\uparrow}_{n,k}\in\mathbb{R}^{\binom{[n]}{k+1}\times\binom{[n]}{k}}$
be the matrix defined by

$P^{\uparrow}_{n,k}(x,y)=\begin{cases}1&\text{if }y_{i}=1\text{ implies
}x_{i}=1\\\ 0&\text{otherwise}\end{cases}$ (2)

Let $P^{\downarrow}_{n,k+1}=(P^{\uparrow}_{n,k})^{*}$.

Let

$P^{\uparrow}_{n,i,k}=P^{\uparrow}_{n,k-1}P^{\uparrow}_{n,k-1}\cdots
P^{\uparrow}_{n,i}$

and

$P^{\downarrow}_{n,k,i}=P^{\downarrow}_{n,i+1}P^{\downarrow}_{n,i+2}\cdots
P^{\downarrow}_{n,k}.$

For simplicity, we let
$P^{\uparrow}_{n,k,k}=P^{\downarrow}_{n,k,k}=I_{\binom{n}{k}}$.

Let $P^{\vee}_{n,k}=P^{\uparrow}_{n,k-1}P^{\downarrow}_{n,k}$ and
$P^{\wedge}=P^{\downarrow}_{n,k+1}P^{\uparrow}_{n,k}$. The following fact
shows that $P^{\vee}_{n,k}$ and $P^{\wedge}_{n,k}$ differ only by a multiple
of the identity matrix.

######  Claim 3.1.

$P^{\vee}_{n,k}=P^{\wedge}_{n,k}-(n-2k)I_{\binom{[n]}{k}}$

Similarly, one can show that $A_{n,k}$ differs from $P^{\vee}_{n,k}$ and
$P^{\wedge}_{n,k}$ by a multiple of the identity matrix. Thus, for the rest of
this paper, we focus on determining an orthonormal basis of eigenvectors for
$P^{\vee}_{n,k}$ and $P^{\wedge}_{n,k}$.

The following claim shows that to determine the eigenvectors of
$P^{\vee}_{n,k}$ and $P^{\wedge}_{n,k}$, it is enough to determine the
nullspace of $P^{\downarrow}_{n,i}$ for all $i\leqslant k$. This will be under
the assumption that $P^{\downarrow}_{n,i}$ has full rank when $i\leqslant
n/2$, which we will prove in Claims 3.5 and 3.6.

######  Claim 3.2.

Let $v\in\mathbb{R}^{\binom{[n]}{i}}$ be a vector such that
$P^{\downarrow}_{n,i}v=0$. Then,

$P^{\vee}_{n,k}P^{\uparrow}_{n,i,k}v=(n-k-i+1)(k-i)P^{\uparrow}_{n,i,k}v.$

and

$P^{\wedge}_{n,k}P^{\uparrow}_{n,i,k}v=(n-k-i)(k-i+1)P^{\uparrow}_{n,i,k}v.$

The following claim shows that if $P^{\downarrow}_{n,i}v=0$, then
$P^{\uparrow}_{n,i,k}v=0$ if $k>n-i$. Thus, in the case that $k>n/2$, one only
needs to consider the nullspace of $P^{\downarrow}_{n,i}$ for $i\leqslant
n-k$. In fact, we will compute
$\displaystyle\frac{\left\|P^{\uparrow}_{n,|S|,k}v\right\|_{2}^{2}}{\left\|v\right\|_{2}^{2}}$
when $P^{\downarrow}_{n,i}v=0$, which will be useful in Section 3.2

######  Claim 3.3.

Let $v\in\mathbb{R}^{\binom{[n]}{i}}$ be a vector such that
$P^{\downarrow}_{n,i}v=0$ for $i\leqslant n/2$. Then,

$\frac{\left\|P^{\uparrow}_{n,i,k}v\right\|_{2}^{2}}{\|v\|_{2}^{2}}=\frac{(n-2i)!(k-i)!}{(n-k-i)!},$

if $k\leqslant n-i$, and is otherwise $0$.

###### Proof.

We prove this using induction on $i$. In the base case when $k=i$, the Claim
follows as $P^{\uparrow}_{n,i,k}v=v$.

Now, assume that the statement is true for $P^{\uparrow}_{n,i,k-1}v$. Then,

$\displaystyle\left\|P^{\uparrow}_{n,i,k}v\right\|_{2}^{2}$
$\displaystyle=\left\langle
P^{\uparrow}_{n,k-1}P^{\uparrow}_{n,i,k-1}v,P^{\uparrow}_{n,k-1}P^{\uparrow}_{n,ik-1}v\right\rangle$
$\displaystyle=\left\langle
P^{\uparrow}_{n,i,k-1}v,P^{\wedge}_{n,k-1}P^{\uparrow}_{n,i,k-1}v\right\rangle$
$\displaystyle=(n-k-i+1)(k-i)\left\langle
P^{\uparrow}_{n,i,k-1}v,P^{\uparrow}_{n,i,k-1}v\right\rangle$ (3)
$\displaystyle=(n-k-i+1)(k-i)\frac{(n-2i)!(k-i-1)!}{(n-k-i+1)!}$
$\displaystyle\frac{(n-2i)!(k-i)!}{(n-k-i)!}$ (4)

as desired, where the third equality follows from Claim 3.2 and the fourth
equality follows from the inductive hypothesis.

If $k=n-i+1$, then Eq. (3) is $0$, and it follows that
$\left\|P^{\uparrow}_{n,i,k}v\right\|_{2}=0$ whenever $k>n-i+1$ by the
definition of $P^{\uparrow}_{n,i,k}$. ∎

Note that the assumption that $P^{\downarrow}_{n,i}$ has full-rank when
$i\leqslant n/2$ combined with Claims 3.2 and 3.3 yields a subspace of
eigenvectors with equal eigenvalue of dimension $\binom{n}{i}-\binom{n}{i-1}$.
For a fixed $k$ and summing over all $i$ from $0$ to $\min\\{k,n-k\\}$, this
is $\binom{n}{\min\\{k,n-k\\}}$ eigenvectors, and thus, this gives a complete
basis of eigenvectors.

The following claim shows that to determine an orthogonal basis of
eigenvectors of $P^{\vee}_{n,k}$ and $P^{\wedge}_{n,k}$ it is enough to
determine an orthogonal basis for the nullspace of $P^{\downarrow}_{n,i}$ for
all $i\leqslant\min\\{k,n-k\\}$. That is, applying
$P^{\uparrow}_{n,i^{\prime}}$ to two orthogonal vectors preserves
orthogonality. Recall that the eigenvectors of a symmetric matrix with
different eigenvalues are orthogonal, and thus it is sufficient to determine
an orthogonal basis for the nullspace of $P^{\downarrow}_{n,i}$ for each $i$.

######  Claim 3.4.

Let $v_{1}$ and $v_{2}$ be such that $\langle v_{1},v_{2}\rangle=0$ and
$P^{\downarrow}_{n,i}v_{i}=0$ for all $i$. Then

$\left\langle
P^{\uparrow}_{n,i,k}v_{1},P^{\uparrow}_{n,i,k}v_{2}\right\rangle=0$

.

###### Proof.

We prove this on induction on $k$.

When $k=i$, the statement is obvious.

Assume that $\left\langle
P^{\uparrow}_{n,i,k-1}v_{1},P^{\uparrow}_{n,i,k-1}v_{2}\right\rangle=0$. Then
through a similar sequence of equalities as Eq. (4), one sees that

$\displaystyle\left\langle
P^{\uparrow}_{n,i,k}v_{1},P^{\uparrow}_{n,i,k}v_{2}\right\rangle$
$\displaystyle=(n-k-i+1)(k-i)\left\langle
P^{\uparrow}_{n,i,k-1}v_{1},P^{\uparrow}_{n,i,k-1}v_{2}\right\rangle$
$\displaystyle=0$

as desired. ∎

We note that Claims 3.1, 3.2 3.3, and 3.4 can be generalized to sequentially
differential posets (of which, the collection of subsets of $[n]$ is an
example), as is done in the work of Stanley [Sta88, Sta90].

###  3.1 An orthogonal basis for the nullspace of $P^{\downarrow}_{n,k}$

In this section, we give an orthogonal basis for the nullspace of
$P^{\downarrow}_{n,k}$ when $k\leqslant n/2$. This basis was found by
Srinivasan [Sri11] and independently by Filmus [Fil16]. For completeness, we
include the proof that this is an orthogonal basis due to Srinivasan.

Note that

$P^{\downarrow}_{n,k}=\begin{bmatrix}P^{\downarrow}_{n-1,k}&I_{\binom{n-1}{k}}\\\
0&P^{\downarrow}_{n-1,k-1}\end{bmatrix}$

if $k\leqslant n/2$, where if $k=1$, then we remove the bottom two blocks. In
particular, the fact that $P^{\downarrow}_{n,k}$ can be written recursively in
terms of $P^{\downarrow}_{n-1,k}$ and $P^{\downarrow}_{n-1,k-1}$ suggests that
an orthogonal basis for the nullspace of the former matrix can be obtained
from orthogonal bases for the nullspace of the latter matrices.

Let $S$ be a subset in $\mathcal{H}_{n,k}$. Recall that this means that when
the elements $S$ are listed in sorted order as
$\\{s_{1},s_{2},\ldots,s_{|S|}\\}$, that $s_{i}\geqslant 2i$ for all $i$. We
associate with each $S$ a vector $\chi_{n,S}$ such that
$P^{\downarrow}_{n,|S|}\chi_{n,S}=0$. We define $\chi_{n,S}$ recursively as
follows.

$\chi_{n,S}=\begin{cases}[1]&\text{if }|S|=0\\\ \begin{bmatrix}\chi_{n-1,S}\\\
0\end{bmatrix}&\text{if }n\not\in S\\\
\begin{bmatrix}-\displaystyle\frac{P^{\uparrow}_{n-1,|S|-1}\chi_{n-1,S\backslash\\{n\\}}}{n-2|S|+1}\\\
\chi_{n-1,S\backslash\\{n\\}}\end{bmatrix}&\text{otherwise}\end{cases}$ (5)

We briefly give some intuition behind restricting $S$ to only those subsets in
$\mathcal{H}_{n,k}$. Consider a set $S$ of size at most $k$ that is not in
$\mathcal{H}_{n,k}$. Let $S=\\{s_{1},\ldots,s_{|S|}\\}$ be in sorted order,
and let $i$ be the smallest integer such that $s_{i}<2i$. Then either $i=1$
and $s_{i}=1$, or $s_{i-1}\geqslant 2i-2$ and $s_{i}=2i-1$. Thus,
$s_{i}-2i+1=0$, and $\chi_{n,S}$ is not well-defined.

By Bertrand’s ballot problem, there are $\binom{n}{|S|}-\binom{n}{|S|-1}$ sets
in $\mathcal{H}_{n,k}$ of size $|S|$. Thus, proving that $\chi_{n,S}$ is in
the nullspace of $P^{\downarrow}_{n,|S|}$ and that if $|S_{1}|=|S_{2}|$ and
$S_{1}\neq S_{2}$, then
$\left\langle\chi_{n,S_{1}},\chi_{n,S_{2}}\right\rangle=0$ are both enough to
obtain an orthogonal basis for the nullspace of $P^{\downarrow}_{n,k}$ and
also show it has full rank.

We first show that $\chi_{n,S}$ is in fact in the nullspace of
$P^{\downarrow}_{n,|S|}$.

######  Claim 3.5.

For all $S\in\mathcal{H}_{n,k}$, $P^{\downarrow}_{n,|S|}\chi_{n,S}=0$.

###### Proof.

We prove this using induction on $n$ and $|S|$.

If $S=\\{n^{\prime}\\}$, then

$\chi_{n,S}=\begin{bmatrix}\smash[b]{\underbrace{\begin{matrix}-\frac{1}{n^{\prime}-1}&-\frac{1}{n^{\prime}-1}&\cdots&-\frac{1}{n^{\prime}-1}\end{matrix}}_{n^{\prime}-1\text{
times}}}&1&0&0&\cdots\end{bmatrix}^{*}.$

Thus, $P^{\downarrow}_{n,1}\chi_{n,S}=0$.

If $n\not\in S$, then
$P^{\downarrow}_{n,|S|}\chi_{n,S}=P^{\downarrow}_{n-1,|S|}\chi_{n,S}=0$ by the
inductive hypothesis.

If $n\in S$, then

$\displaystyle P^{\downarrow}_{n,|S|}\chi_{n,S}$
$\displaystyle=\begin{bmatrix}-\displaystyle\frac{P^{\wedge}_{n-1,|S|-1}\chi_{n-1,S\backslash\\{n\\}}}{n-2|S|+1}+\chi_{n-1,S\backslash\\{n\\}}\\\
P^{\downarrow}_{n-1,|S|-1}\chi_{n-1,S\backslash\\{n\\}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}-\displaystyle\frac{P^{\vee}_{n-1,|S|-1}\chi_{n-1,S\backslash\\{n\\}}}{n-2|S|+1}-\chi_{n-1,S\backslash\\{n\\}}+\chi_{n-1,S\backslash\\{n\\}}\\\
0\end{bmatrix}$ $\displaystyle=0.$

where the second inequality follows from the relationship between
$P^{\wedge}_{n-1,|S|-1}$ and $P^{\vee}_{n-1,|S|-1}$ and the inductive
hypothesis, and the third inequality also follows from the inductive
hypothesis. ∎

The following claim shows that if $|S_{1}|=|S_{2}|$ and $S_{1}\neq S_{2}$,
then $\chi_{n,S_{1}}$ and $\chi_{n,S_{2}}$ are orthogonal. Recall that
eigenvectors of a symmetric matrix with different eigenvalues are orthogonal.
Thus, this claim along with Claim 3.6 are enough to prove that the given basis
is orthogonal.

######  Claim 3.6.

For $S_{1},S_{2}\in\mathcal{H}_{n,k}$, if $|S_{1}|=|S_{2}|$ and $S_{1}\neq
S_{2}$, then $\left\langle\chi_{n,S_{1}},\chi_{n,S_{2}}\right\rangle=0$.

###### Proof.

We prove this using induction on $n$.

Consider the base case of $|S_{1}|=|S_{2}|=1$. In particular, let
$S_{1}=\\{n_{1}\\}$ and let $S_{2}=\\{n_{2}\\}$, and without loss of
generality, assume that $n_{2}>n_{1}$. Then

$\chi_{n}(S_{i})=\begin{bmatrix}\smash[b]{\underbrace{\begin{matrix}-\frac{1}{n_{i}-1}&-\frac{1}{n_{i}-1}&\cdots&-\frac{1}{n_{i}-1}\end{matrix}}_{n_{i}-1\text{
times}}}&1&0&0&\cdots\end{bmatrix}^{*}.$

and the claim clearly holds.

For the inductive step, assume that the statement is true for all pairs
$\chi_{n^{\prime}}(S_{1}^{\prime})$ and $\chi_{n^{\prime}}(S_{2}^{\prime})$
where $n^{\prime}<n$ and $|S_{1}^{\prime}|=|S_{2}^{\prime}|$. Then there are
three cases.

Case 1: If neither $S_{1}$ nor $S_{2}$ contain $n$, then
$\left\langle\chi_{n,S_{1}},\chi_{n,S_{2}}\right\rangle=0$ by the inductive
hypothesis.

Case 2: If both $S_{1}$ and $S_{2}$ contain $n$, then

$\displaystyle\left\langle\chi_{n,S_{1}},\chi_{n,S_{2}}\right\rangle$
$\displaystyle=\frac{1}{(n-2|S_{2}|+1)^{2}}$
$\displaystyle\left\langle\chi_{n-1,S_{1}\backslash\\{n\\}},P^{\wedge}_{n-1,|S_{2}|-1}\chi_{n-1,S_{2}\backslash\\{n\\}}\right\rangle$
$\displaystyle+\left\langle\chi_{n-1,S_{1}\backslash\\{n\\}},\chi_{n-1,S_{2}\backslash\\{n\\}}\right\rangle$
$\displaystyle=\frac{1}{(n-2|S_{2}|+1)^{2}}$
$\displaystyle\left\langle\chi_{n-1,S_{1}\backslash\\{n\\}},P^{\vee}_{n-1,|S_{2}|-1}\chi_{n-1,S_{2}\backslash\\{n\\}}\right\rangle$
$\displaystyle+\frac{n-2|S_{2}|+2}{(n-2|S_{2}|+1)}\left\langle\chi_{n-1,S_{1}\backslash\\{n\\}},\chi_{n-1,S_{2}\backslash\\{n\\}}\right\rangle$
$\displaystyle=0$

where the second equality follows from Fact 3.1 and the third inequality
follows from the inductive hypothesis for $S_{1}\backslash\\{n\\}$ and
$S_{2}\backslash\\{n\\}$, and the fact that
$P^{\downarrow}_{n-1,|S_{2}|-1}\chi_{n-1}(S_{2}\backslash\\{n\\})=0$.

Case 3: If only $S_{2}$ contains $n$, then

$\displaystyle\left\langle\chi_{n,S_{1}},\chi_{n,S_{2}}\right\rangle$
$\displaystyle=\left\langle\chi_{n-1}(S_{1}),\frac{P^{\uparrow}_{n-1,|S_{2}|-1}\chi_{n-1,S_{2}\backslash\\{n\\}}}{n-2|S_{2}|+1}\right\rangle$
$\displaystyle=\left\langle
P^{\downarrow}_{n-1,k}\chi_{n-1}(S_{1}),\frac{\chi_{n-1,S_{2}\backslash\\{n\\}}}{n-2|S_{2}|+1}\right\rangle$
$\displaystyle=0$

where the last inequality follows from the fact that
$P^{\downarrow}_{n-1,|S_{2}|}\chi_{n-1,S_{1}}=0$. ∎

We summarize below.

######  Theorem 3.7.

The set of vectors

$\left\\{P^{\uparrow}_{n,|S|}\chi_{n,S}\mid
S\in\mathcal{H}_{n,\min\\{k,n-k\\}}\right\\}$

form an orthogonal basis of eigenvectors for $A_{n,k}$, the adjacency matrix
of the Johnson graph.

###### Proof.

The theorem follows by applying Claims 3.2, 3.3, 3.4, 3.5, and 3.6, and
noticing that $|\mathcal{H}_{n,\min\\{k,n-k\\}}|=\binom{n}{k}$ and that
eigenvectors with distinct eigenvalues are orthogonal. ∎

###  3.2 A computation of the norm

In this section, we compute the norm of $P^{\uparrow}_{n,|S|,k}\chi_{n,S}$.
This combined with Theorem 3.7 will yield a set of orthonormal eigenvectors
that can be used to construct a Fourier transform over the slice. The results
in this section can be found in [Fil16]. We give an inductive proof that
follows the framework of Srinivasan [Sri11] and Filmus and Lindzey [FL20].

We start by computing the norm of $\chi_{n,S}$.

######  Claim 3.8.

Let $S=\\{s_{1},\ldots,s_{|S|}\\}$ be such that $s_{1}\leqslant
s_{2}\leqslant\cdots\leqslant s_{|S|}$. Then,

$\left\|\chi_{n,S}\right\|_{2}^{2}=\prod_{i=1}^{|S|}\frac{s_{i}-2i+2}{s_{i}-2i+1}$

###### Proof.

We prove this using induction on $n$. For the base case, if
$S=\\{n^{\prime}\\}$, then

$\chi_{n,S}=\begin{bmatrix}\smash[b]{\underbrace{\begin{matrix}-\frac{1}{n^{\prime}-1}&-\frac{1}{n^{\prime}-1}&\cdots&-\frac{1}{n^{\prime}-1}\end{matrix}}_{n^{\prime}-1\text{
times}}}&1&0&0&\cdots\end{bmatrix}^{*}.$

and thus,

$\left\|\chi_{n,S}\right\|_{2}^{2}=1+\frac{1}{n^{\prime}-1}=\frac{n^{\prime}}{n^{\prime}-1}$

as desired.

If $n\not\in S$, then

$\left\|\chi_{n,S}\right\|_{2}^{2}=\left\|\chi_{n-1,S}\right\|_{2}^{2}=\prod_{i=1}^{|S|}\frac{s_{i}-2i+2}{s_{i}-2i+1}$

where the second inequality follows from the inductive hypothesis.

If $n\in S$, then

$\displaystyle\left\|\chi_{n,S}\right\|_{2}^{2}$
$\displaystyle=\left\|\chi_{n-1,S\backslash\\{n\\}}\right\|_{2}^{2}+\frac{1}{(n-2|S|+1)^{2}}\left\|P^{\uparrow}_{n-1,|S|-1}\chi_{n-1,S\backslash\\{n\\}}\right\|_{2}^{2}$
$\displaystyle=\left\|\chi_{n-1,S\backslash\\{n\\}}\right\|_{2}^{2}+\frac{1}{(n-2|S|+1)^{2}}\left\langle\chi_{n-1,S\backslash\\{n\\}},P^{\wedge}_{n,|S|-1}\chi_{n-1,S\backslash\\{n\\}}\right\rangle$
$\displaystyle=\left(1+\frac{1}{n-2|S|+1}\right)\left\|\chi_{n-1,S\backslash\\{n\\}}\right\|_{2}^{2}$
$\displaystyle=\frac{n-2|S|+2}{n-2|S|+1}\prod_{i=1}^{k-1}\frac{s_{i}-2i+2}{s_{i}-2i+1}$
$\displaystyle=\prod_{i=1}^{|S|}\frac{s_{i}-2i+2}{s_{i}-2i+1}$

where the third equality follows from the fact that
$\chi_{n-1,S\backslash\\{n\\}}$ is an eigenvector of $P^{\wedge}_{n,k-1}$, and
the fourth equality follows from the inductive hypothesis. ∎

Finally, we can compute
$\left\|P^{\uparrow}_{n,|S|,k}\chi_{n,S}\right\|_{2}^{2}$.

######  Claim 3.9.

$\left\|P^{\uparrow}_{n,|S|,k}\chi_{n,S}\right\|_{2}^{2}=\frac{(n-2|S|)!(k-|S|)!}{(n-k-|S|)!}\prod_{i=1}^{k}\frac{s_{i}-2i+2}{s_{i}-2i+1}$

###### Proof.

The claim follows by applying Claims 3.3 and 3.8. ∎

Finally, we give a formula definition for the Fourier coefficients of a
function on the slice.

######  Definition 3.10.

For $f\in\mathbb{R}^{\binom{[n]}{k}}$ and
$S\in\mathcal{H}_{n,\min\\{k,n-k\\}}$, define

$\widehat{f}(S)=\frac{1}{\left\|P^{\uparrow}_{n,|S|,k}\chi_{n,S}\right\|_{2}}\left\langle
f,P^{\uparrow}_{n,|S|,k}\chi_{n,S}\right\rangle.$

Here, $P^{\uparrow}$ is defined in Eq. (2) and $\chi_{n,S}$ is defined in Eq.
(5). It will be convenient to define $\widehat{f}(S)$ even when $S$ is not in
$\mathcal{H}_{n,\min\\{k,n-k\\}}$, in which case we let $\widehat{f}(S)=0$.

##  4 Restrictions of functions on the slice

In this section, we state and prove our main theorem regarding a relationship
between the Fourier coefficients of a function on the slice, and the Fourier
coefficients of its restrictions.

######  Definition 4.1 (Restriction).

Let $f:\binom{[n]}{k}\rightarrow\mathbb{R}$. For $m<n$, and
$z\in\\{0,1\\}^{m}$, let $f_{z}:{\binom{[n-m]}{k-|z|}}\rightarrow\mathbb{R}$
(where $|z|=\sum_{i=1}^{m}z_{i}$ is the Hamming weight of $z$) be the function
defined by $f_{z}(x)=f(x\circ z)$ where $\circ$ denotes concatenation.

We start with the following theorem.

######  Theorem 4.2.

Let $f:\binom{[n]}{k}\rightarrow\mathbb{R}$. Then, for all
$S\in\mathcal{H}_{n-1,\min\\{k,n-k\\}}$,

$\widehat{f}(S)=\frac{1}{\sqrt{n-2|S|}}\left(\sqrt{n-k-|S|}\widehat{f_{0}}(S)+\sqrt{k-|S|}\widehat{f_{1}}(S)\right).$

Additionally, if $|S|<\min\\{k,n-k\\}$, then

$\widehat{f}(S\cup\\{n\\})=\frac{1}{\sqrt{n-2|S|}}\left(-\sqrt{k-|S|}\widehat{f_{0}}(S)+\sqrt{n-k-|S|}\widehat{f_{1}}(S)\right)$

Thus, if $|S|<\min\\{k,n-k\\}$, then

$\widehat{f_{0}}(S)=\frac{1}{\sqrt{n-2|S|}}\left(\sqrt{n-k-|S|}\widehat{f}(S)-\sqrt{k-|S|}\widehat{f}(S\cup\\{n\\})\right)$

and

$\widehat{f_{1}}(S)=\frac{1}{\sqrt{n-2|S|}}\left(\sqrt{n-k-|S|}\widehat{f}(S\cup\\{n\\})+\sqrt{k-|S|}\widehat{f}(S)\right)$

###### Proof.

If $k=0$, then $f=f_{0}$, and $|S|=0$, and the theorem holds. Similarly, if
$k=n$, then $f=f_{1}$ and $|S|=0$ and the theorem also holds.

If $|S|=k$, then $\widehat{f}(S)=\widehat{f_{0}}(S)$ as $\chi_{n,S}(x)=0$ if
$x_{n}=1$, and again, the theorem holds. If $|S|=n-k$, then recall that
$P^{\uparrow}_{n-1,|S|,k}\chi_{n-1,S}=0$ by Claim 3.3, and thus
$\widehat{f}(S)=\widehat{f_{1}}(S)$, and again, the theorem holds.

Thus, we can assume that $f_{0}$ and $f_{1}$ are not empty functions, and that
$S\in\mathcal{H}_{n-1,\min\\{k-1,n-k-1\\}}$, and in particular, has a
corresponding vector in the orthogonal basis for both $A_{n-1,k}$ and
$A_{n-1,k-1}$.

Let $f_{0}^{\prime}:{\binom{[n]}{k}}\rightarrow\mathbb{R}$ be defined by
$f_{0}^{\prime}(x)=f(x)$ if $x_{n}=0$ and $f_{0}^{\prime}(x)=0$ otherwise.
Additionally, let $f_{1}^{\prime}:{\binom{[n]}{k}}\rightarrow\mathbb{R}$ be
defined by $f_{1}^{\prime}(x)=f(x)$ if $x_{n}=1$, and $f_{1}^{\prime}(x)=0$
otherwise.

Let $i=|S|$. Note that because $f=f^{\prime}_{0}+f^{\prime}_{1}$, for all $S$,

$\displaystyle\widehat{f}(S)$
$\displaystyle=\frac{1}{\left\|P^{\uparrow}_{n,i,k}\chi_{n,S}\right\|_{2}}\left\langle
f_{0}^{\prime},P^{\uparrow}_{n,i,k}\chi_{n,S}\right\rangle+\frac{1}{\left\|P^{\uparrow}_{n,i,k}\chi_{n,S}\right\|_{2}}\left\langle
f_{1}^{\prime},P^{\uparrow}_{n,i,k}\chi_{n,S}\right\rangle$ (6)

We start with the first inequality. We have that $\left\langle
f_{0}^{\prime},P^{\uparrow}_{n,i,k}\chi_{n,S}\right\rangle=\left\langle
f_{0},P^{\uparrow}_{n-1,i,k}\chi_{n-1,S}\right\rangle$, as
$f_{0}^{\prime}(x)=0$ if $x_{n}=0$. Thus, the right-hand side of Eq. (6) is
equal to

$\displaystyle\
\frac{1}{\left\|P^{\uparrow}_{n,i,k}\chi_{n,S}\right\|_{2}}\left\langle
f_{0},P^{\uparrow}_{n-1,i,k}\chi_{n-1,S}\right\rangle$
$\displaystyle+\frac{1}{\left\|P^{\uparrow}_{n,i,k}\chi_{n,S}\right\|_{2}}\left\langle
P^{\downarrow}_{n,k,i}f_{1}^{\prime},\chi_{n,S}\right\rangle$
$\displaystyle=\frac{\left\|P^{\uparrow}_{n-1,i,k}\chi_{n-1,S}\right\|_{2}\widehat{f_{0}}(S)}{\left\|P^{\uparrow}_{n,i,k}\chi_{n,S}\right\|_{2}}+\frac{k-i}{\left\|P^{\uparrow}_{n,i,k}\chi_{n,S}\right\|_{2}}\left\langle
P^{\downarrow}_{n-1,k-1,i}f_{1},\chi_{n-1,S}\right\rangle$
$\displaystyle=\frac{\left\|P^{\uparrow}_{n-1,i,k}\chi_{n-1,S}\right\|_{2}\widehat{f_{0}}(S)}{\left\|P^{\uparrow}_{n,i,k}\chi_{n,S}\right\|_{2}}+\frac{k-i}{\left\|P^{\uparrow}_{n,i,k}\chi_{n,S}\right\|_{2}}\left\langle
f_{1},P^{\uparrow}_{n-1,i,k-1}\chi_{n-1,S}\right\rangle$
$\displaystyle=\frac{\left\|P^{\uparrow}_{n-1,i,k}\chi_{n-1,S}\right\|_{2}\widehat{f_{0}}(S)}{\left\|P^{\uparrow}_{n,i,k}\chi_{n,S}\right\|_{2}}+\frac{(k-i)\widehat{f_{1}}(S)\left\|P^{\uparrow}_{n-1,i,k-1}\chi_{n-1,S}\right\|_{2}}{\left\|P^{\uparrow}_{n,i,k}\chi_{n,S}\right\|_{2}}$
(7)

where the sequence of inequalities uses the fact that
$\chi_{n,S}(x)=\chi_{n-1,S}(x)$ unless $x_{n}=1$, in which case
$\chi_{n,S}(x)=0$. The first equality also uses the fact that
$\left(P^{\downarrow}_{n,k,i}f_{1}^{\prime}\right)(x)=(k-i)\left(P^{\downarrow}_{n-1,k-1,i}f_{1}\right)(x)$
if $x_{n}=0$. By Claim 3.9, Eq. (7) is equal to

$\displaystyle\sqrt{\frac{n-k-i}{n-2i}}\widehat{f_{0}}(S)+\frac{(k-i)}{\sqrt{(n-2i)(k-i)}}\widehat{f_{1}}(S)=\frac{1}{\sqrt{n-2i}}\left(\sqrt{n-k-i}\widehat{f_{0}}(S)+\sqrt{k-i}\widehat{f_{1}}(S)\right)$

as desired.

Now, let $i=|S|+1$, and let $S^{\prime}=S\cup\\{n\\}$. To prove the second
inequality, note that the right-hand side of Eq. (6) is equal to

$\displaystyle\frac{1}{\left\|P^{\uparrow}_{n,i,k}\chi_{n,S^{\prime}}\right\|_{2}}$
$\displaystyle\left\langle
P^{\downarrow}_{n,k,i}f_{0}^{\prime},\chi_{n,S^{\prime}}\right\rangle+\frac{1}{\left\|P^{\uparrow}_{n,i,k}\chi_{n,S^{\prime}}\right\|_{2}}\left\langle
P^{\downarrow}_{n,k,i}f_{1}^{\prime},\chi_{n,S^{\prime}}\right\rangle$
$\displaystyle=\frac{-\left\langle
P^{\downarrow}_{n-1,k,i}f_{0},P^{\uparrow}_{n-1,i-1}\chi_{n-1,S^{\prime}\backslash\\{n\\}}\right\rangle}{(n-2i+1)\left\|P^{\uparrow}_{n,i,k}\chi_{n,S^{\prime}}\right\|_{2}}$
$\displaystyle+\frac{\frac{-(k-i)}{n-2i+1}\left\langle
P^{\downarrow}_{n-1,k-1,i}f_{1},P^{\uparrow}_{n-1,i-1}\chi_{n-1,S^{\prime}\backslash\\{n\\}}\right\rangle+\left\langle
P^{\downarrow}_{n-1,k-1,i-1}f_{1},\chi_{n-1,S^{\prime}\backslash\\{n\\}}\right\rangle}{\left\|P^{\uparrow}_{n,i,k}\chi_{n,S^{\prime}}\right\|_{2}}$
$\displaystyle=\frac{-\left\langle
P^{\downarrow}_{n-1,k,i-1}f_{0},\chi_{n-1,S^{\prime}\backslash\\{n\\}}\right\rangle}{(n-2i+1)\left\|P^{\uparrow}_{n,i,k}\chi_{n,S^{\prime}}\right\|_{2}}+\frac{n-k-1+1}{n-2i+1}\left\langle
P^{\downarrow}_{n-1,k-1,i-1}f_{1},\chi_{n-1,S^{\prime}\backslash\\{n\\}}\right\rangle$
$\displaystyle=\frac{-\left\|P^{\uparrow}_{n-1,i-1,k}\chi_{n,S^{\prime}\backslash\\{n\\}}\right\|_{2}}{(n-2i+1)\left\|P^{\uparrow}_{n,i,k}\chi_{n,S^{\prime}}\right\|_{2}}\widehat{f_{0}}(S^{\prime}\backslash\\{n\\})+\frac{(n-k-i+1)\left\|P^{\uparrow}_{n-1,i-1,k-1}\chi_{n,S^{\prime}\backslash\\{n\\}}\right\|_{2}}{(n-2i+1)\left\|P^{\uparrow}_{n,i,k}\chi_{n,S^{\prime}}\right\|_{2}}\widehat{f_{1}}(S^{\prime}\backslash\\{n\\})$
(8)

where the first equality follows from the definition of $\chi_{n,S}$ along
with the fact that
$\left(P^{\downarrow}_{n,k,i}f_{1}^{\prime}\right)(x)=(k-i)\left(P^{\downarrow}_{n-1,k-1,i}f_{1}\right)(x)$
if $x_{n}=0$. Again, by Claim 3.9, Eq (8) is equal to

$\frac{-1}{n-2i+1}\sqrt{\frac{(n-2i+1)(n-2i+1)(k-i+1)}{n-2i+2}}\widehat{f_{0}}(S^{\prime}\backslash\\{n\\})+\frac{n-k-i+1}{n-2i+1}\sqrt{\frac{(n-2i+1)(n-2i+1)}{(n-2i+2)(n-k-i+1)}}\widehat{f_{1}}(S^{\prime}\backslash\\{n\\})\\\
=\frac{1}{\sqrt{n-2i+2}}\left(-\sqrt{k-i+1}\widehat{f_{0}}(S^{\prime}\backslash\\{n\\})+\sqrt{n-k-i+1}\widehat{f_{1}}(S^{\prime}\backslash\\{n\\})\right)$

as desired. ∎

Finally, we prove the following relationship between the Fourier coefficients
of $f$ and the Fourier coefficients of restrictions of $f$.

######  Corollary 4.3.

Let $f:\binom{[n]}{k}\rightarrow\mathbb{R}$, and let $i\leqslant k$. Then for
all $S\in\mathcal{H}_{\min\\{k,n-k\\}}$,

$\widehat{f_{0}}(S)^{2}+\widehat{f_{1}}(S)^{2}=\widehat{f}(S)^{2}+\widehat{f}(S\cup\\{n\\})^{2}.$

Additionally,

$\sum_{z\in\\{0,1\\}^{t}}\widehat{f_{z}}(S)^{2}=\sum_{T\subseteq[n]\backslash[n-t]}\widehat{f}(S\cup
T)^{2}$

###### Proof.

The first statement follows from Theorem 4.2, and the second follows by
induction. ∎

##  5 A Goldreich-Levin Theorem for the slice

In this section, we prove Theorem 1.2, a Goldreich-Levin theorem for the
slice. Informally, this theorem states that the large Fourier coefficients of
a function can be efficiently detected. With the machinery of Corollary 4.3,
the algorithm and proof of correctness are essentially the same as for the
Boolean hypercube. However, some care is required in estimating quantities of
the form

$\sum_{S\subseteq[n]\backslash[i]}\widehat{f}(U\cup S)^{2}$

for a given function $f$ and a given set $U\subseteq[i]$. For completeness, we
give the algorithm.

The algorithm uses a divide and conquer strategy due to Kushilevitz and
Mansour [KM93].

Let $L\leftarrow\\{\emptyset\\}$

for  _$i\leftarrow 0$ to $n-1$_ do

for  _Each $U\in L$_ do

Estimate $\sum_{S\subseteq[n]\backslash[i]}\widehat{f}(U\cup S)^{2}$ by
$w_{1}$

Estimate $\sum_{S\subseteq[n]\backslash[i]}\widehat{f}(U\cup\\{i+1\\}\cup
S)^{2}$ by $w_{2}$

Remove $U$ from $L$.

if  _$w_{1}\geqslant\tau^{2}/2$_ then

Add $U$ to $L$

end if

if  _$w_{2}\geqslant\tau^{2}/2$_ then

Add $U\cup\\{i+1\\}$ to $L$

end if

end for

end for

Algorithm 1 Goldreich-Levin for the slice

Much of the analysis is identical to the algorithm for the Boolean hypercube.
As in the case of the Boolean hypercube, the algorithm identifies a set of
Fourier coefficients with large total weight, starting with the set of all
Fourier coefficients. At each step, it splits each set into two, estimates the
total weights of all of the subsets, and removes those subsets with small
total weight. If the algorithm is able to estimate the total weight
accurately, then at any given point, it will only identify
$\mathit{poly}(\tau)$ different sets. (For a complete analysis, one can also
refer to Section 3.5 of [O’D14]).

Thus, it is enough to show that one can estimate
$\sum_{S\subseteq[n]\backslash[i]}\widehat{f}(U\cup S)^{2}$ and
$\sum_{S\subseteq[n]\backslash[i]}\widehat{f}(U\cup\\{i\\}\cup S)^{2}$ in
$\mathit{poly}(n,1/\tau)$-time to error $(\tau^{2}/2)\binom{n}{k}$ with
probability at least $1-1/\mathit{poly}(n,1/\tau)$.

######  Theorem 5.1.

Given query access to a function $f:{\binom{[n]}{k}}\rightarrow\\{-1,1\\}$ and
a set $U\subseteq[i]$ for some integer $i$, then
$\mathit{poly}(n,1/\varepsilon,1/\tau)$ samples are sufficient to compute
$\sum_{S\in[n]\backslash[i]}\widehat{f}(U\cup S)^{2}$ up to error
$\varepsilon\binom{[n]}{k}$ with probability at least
$1-1/\mathit{poly}(n,1/\tau)$.

###### Proof.

By Corollary 4.3, we have

$\frac{1}{\binom{n}{k}}\sum_{S\subseteq[n]\backslash[i]}\widehat{f}(U\cup
S)^{2}=\sum_{z\in\\{0,1\\}^{n-i}}\frac{\binom{i}{k-|z|}}{\binom{n}{k}}\frac{1}{\binom{i}{k-|z|}}\widehat{f_{z}}(U)^{2}.$
(9)

Let $x$ be a random variable over $\\{0,1\\}^{n-i}$ where $x=z$ with
probability $\frac{\binom{i}{k-|z|}}{\binom{n}{k}}$. Note that such a
probability distribution is well-defined, as
$\sum_{z\in\\{0,1\\}^{n-i}}\binom{i}{k-|z|}=\binom{n}{k}$. Then the right-hand
side of Eq. (9) can be rewritten as

$\mathbb{E}_{x}\left[\frac{\widehat{f_{x}}(S)^{2}}{\binom{i}{k-|x|}}\right]=\mathbb{E}_{x}\left[\frac{1}{\left\|P^{\uparrow}_{i,|S|,k-|x|}\chi_{i,S}\right\|_{2}^{2}}\frac{\langle
f_{x},P^{\uparrow}_{i,|S|,k-|x|}\chi_{i,S}\rangle^{2}}{\binom{i}{k-|x|}}\right].$

For each $x$ in $\\{0,1\\}^{n-i}$, let $y_{1}$ and $y_{2}$ be independent
random variables over $\binom{[i]}{k-|x|}$ distributed according to the
absolute value of the coordinates $P^{\uparrow}_{i,|S|,k-|x|}\chi_{i,S}$. In
particular, we let the probability that $y_{1}=T$ be
$\frac{\left|P^{\uparrow}_{i,|S|,k-|x|}\chi_{i,S}\right|}{\left\|P^{\uparrow}_{i,|S|,k-|x|}\chi_{i,S}\right\|_{1}}$
and thus we obtain

$\mathbb{E}_{x}\left[\frac{\widehat{f_{x}}(S)^{2}}{\binom{i}{k-|x|}}\right]=\mathbb{E}_{x,y_{1},y_{2}}\left[\frac{\left\|P^{\uparrow}_{i,|S|,k-|x|}\chi_{i,S}\right\|_{1}^{2}}{\left\|P^{\uparrow}_{i,|S|,k-|x|}\chi_{i,S}\right\|_{2}^{2}}\frac{f_{z}(y_{1})f_{z}(y_{2})\operatorname{sign}\left(\left(P^{\uparrow}_{i,|S|,k-|x|}\chi_{i,S}\right)_{y_{1}}\right)\operatorname{sign}\left(\left(P^{\uparrow}_{i,|S|,k-|x|}\chi_{i,S}\right)_{y_{2}}\right)}{\binom{i}{k-|x|}}\right]$

By Claim 2.1, and the fact that $f(S)\in\\{-1,1\\}$ for all $S$, it follows
that the random variable inside the expectation is bounded above by $1$. Thus,
by a Chernoff bound, $O(\log(n)/\varepsilon^{2})$ samples are sufficient to
compute $\sum_{S\subseteq[n]\backslash[i]}\widehat{f}(U\cup S)^{2}$ up to
error $\varepsilon\binom{n}{k}$ with probability at least
$1-1/\mathit{poly}(n,1/\tau)$. ∎

## References

  * [AJQ+20] V. L. Alev, F. G. Jeronimo, D. Quintana, S. Srivastava, and M. Tulsiani.  List decoding of direct sum codes.  In _Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms_ , pages 1412–1425. SIAM, Philadelphia, PA, 2020.
  * [AL20] V. L. Alev and L. C. Lau.  Improved analysis of higher order random walks and applications.  In _STOC ’20—Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1198–1211. ACM, New York, [2020] ©2020.  doi:10.1145/3357713.3384317.
  * [ALGV19] N. Anari, K. Liu, S. O. Gharan, and C. Vinzant.  Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid.  In _STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1–12. ACM, New York, 2019\.  doi:10.1145/3313276.3316385.
  * [CGM21] M. Cryan, H. Guo, and G. Mousa.  Modified log-Sobolev inequalities for strongly log-concave distributions.  _Ann. Probab._ , 49(1):506–525, 2021.  ISSN 0091-1798.  doi:10.1214/20-AOP1453.
  * [CTZ20] D. Conlon, J. Tidor, and Y. Zhao.  Hypergraph expanders of all uniformities from Cayley graphs.  _Proc. Lond. Math. Soc. (3)_ , 121(5):1311–1336, 2020.  ISSN 0024-6115.  doi:10.1112/plms.12371.
  * [DDFH18] Y. Dikstein, I. Dinur, Y. Filmus, and P. Harsha.  Boolean function analysis on high-dimensional expanders.  In _Approximation, randomization, and combinatorial optimization. Algorithms and techniques_ , volume 116 of _LIPIcs. Leibniz Int. Proc. Inform._ , pages Art. No. 38, 20. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018.
  * [DHK+21] I. Dinur, P. Harsha, T. Kaufman, I. L. Navon, and A. Ta-Shma.  List-decoding with double samplers.  _SIAM J. Comput._ , 50(2):301–349, 2021.  ISSN 0097-5397.  doi:10.1137/19M1276650.
  * [FI19] Y. Filmus and F. Ihringer.  Boolean constant degree functions on the slice are juntas.  _Discrete Math._ , 342(12):111614, 7, 2019.  ISSN 0012-365X.  doi:10.1016/j.disc.2019.111614.
  * [Fil16] Y. Filmus.  An orthogonal basis for functions over a slice of the Boolean hypercube.  _Electron. J. Combin._ , 23(1):Paper 1.23, 27, 2016.
  * [FKMW18] Y. Filmus, G. Kindler, E. Mossel, and K. Wimmer.  Invariance principle on the slice.  _ACM Trans. Comput. Theory_ , 10(3):Art. 11, 37, 2018.  ISSN 1942-3454.  doi:10.1145/3186590.
  * [FL20] Y. Filmus and N. Lindzey.  Murali’s basis for the slice, 2020.
  * [FM19] Y. Filmus and E. Mossel.  Harmonicity and invariance on slices of the Boolean cube.  _Probab. Theory Related Fields_ , 175(3-4):721–782, 2019.  ISSN 0178-8051.  doi:10.1007/s00440-019-00900-w.
  * [GL89] O. Goldreich and L. A. Levin.  A hard-core predicate for all one-way functions.  In D. S. Johnson, editor, _Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA_ , pages 25–32. ACM, 1989.  doi:10.1145/73007.73010.
  * [KK20] N. Keller and O. Klein.  A structure theorem for almost low-degree functions on the slice.  _Israel J. Math._ , 240(1):179–221, 2020.  ISSN 0021-2172.  doi:10.1007/s11856-020-2062-4.
  * [KM93] E. Kushilevitz and Y. Mansour.  Learning decision trees using the Fourier spectrum.  _SIAM J. Comput._ , 22(6):1331–1348, 1993.  ISSN 0097-5397.  doi:10.1137/0222080.
  * [KO18] T. Kaufman and I. Oppenheim.  Construction of new local spectral high dimensional expanders.  In _STOC’18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ , pages 773–786. ACM, New York, 2018.  doi:10.1145/3188745.3188782.
  * [KO20] T. Kaufman and I. Oppenheim.  High order random walks: beyond spectral gap.  _Combinatorica_ , 40(2):245–281, 2020.  ISSN 0209-9683.  doi:10.1007/s00493-019-3847-0.
  * [LSV05a] A. Lubotzky, B. Samuels, and U. Vishne.  Explicit constructions of Ramanujan complexes of type $\~{A}_{d}$.  _European J. Combin._ , 26(6):965–993, 2005.  ISSN 0195-6698.  doi:10.1016/j.ejc.2004.06.007.
  * [LSV05b] A. Lubotzky, B. Samuels, and U. Vishne.  Ramanujan complexes of type $\~{A}_{d}$.  volume 149, pages 267–299. 2005.  doi:10.1007/BF02772543.  Probability in mathematics.
  * [O’D14] R. O’Donnell.  _Analysis of Boolean functions_.  Cambridge University Press, New York, 2014.  ISBN 978-1-107-03832-5.  doi:10.1017/CBO9781139814782.
  * [Sri11] M. K. Srinivasan.  Symmetric chains, Gelfand-Tsetlin chains, and the Terwilliger algebra of the binary Hamming scheme.  _J. Algebraic Combin._ , 34(2):301–322, 2011.  ISSN 0925-9899.  doi:10.1007/s10801-010-0272-2.
  * [Sta88] R. P. Stanley.  Differential posets.  _J. Amer. Math. Soc._ , 1(4):919–961, 1988.  ISSN 0894-0347.  doi:10.2307/1990995.
  * [Sta90] R. P. Stanley.  Variations on differential posets.  In _Invariant theory and tableaux (Minneapolis, MN, 1988)_ , volume 19 of _IMA Vol. Math. Appl._ , pages 145–165. Springer, New York, 1990\.


${\mathsf{T}}(t)$, we define a prior mean vector and a prior covariance matrix
over ${\mathbf{t}},{\mathbf{E}}$ given by

$\displaystyle{\mathbf{m}}$
$\displaystyle=m_{\mathsf{T}}({\mathbf{t}})=\begin{bmatrix}m_{\mathsf{T}}(t_{1})\\\
\vdots\\\ m_{\mathsf{T}}(t_{n})\end{bmatrix}$ (81) $\displaystyle{\mathbf{K}}$
$\displaystyle=k_{\mathsf{T}}({\mathbf{E}},{\mathbf{E}})=\begin{bmatrix}k_{\mathsf{T}}(E_{i},E_{j})\end{bmatrix}_{1\leq
i,j\leq n}.$ (82)

Further, consider the temperatures internal variability covariance matrix
defined by

${\boldsymbol{\Gamma}}=\gamma_{\mathsf{T}}({\mathbf{t}},{\mathbf{t}})=\begin{bmatrix}\gamma_{\mathsf{T}}(t_{i},t_{j})\end{bmatrix}_{1\leq
i,j\leq n}.$ (83)

Then the prior distribution over temperatures is exactly given by the
multivariate normal distribution
${\mathcal{N}}({\mathbf{m}},{\mathbf{K}}+\sigma^{2}{\boldsymbol{\Gamma}})$.
Let us denote
${\mathbf{K}}_{\sigma^{2}}={\mathbf{K}}+\sigma^{2}{\boldsymbol{\Gamma}}$ for
conciseness. Then, we can exactly evaluate the marginal probability of
${\mathbf{T}}\in{\mathbb{R}}^{n}$ under the prior distribution following

$p({\mathbf{T}}|{\mathbf{E}},{\mathbf{t}})=\frac{1}{\sqrt{(2\pi)^{n}\det({\mathbf{K}}_{\sigma^{2}})}}\exp\left(-\frac{1}{2}({\mathbf{T}}-{\mathbf{m}})^{\top}{\mathbf{K}}_{\sigma^{2}}^{-1}({\mathbf{T}}-{\mathbf{m}})\right),$
(84)

which can be used as maximisation objective to tune model hyperparameters such
that the observed temperatures ${\mathbf{T}}$ have the greatest possible
likelihood under the prior. In practice, we prefer working with the marginal
log-likelihood for computational stability. It is given by closed-form by

$\boxed{\log
p({\mathbf{T}}|{\mathbf{E}},{\mathbf{t}})=-\frac{1}{2}\left\\{n\log(2\pi)+\log\det({\mathbf{K}}_{\sigma^{2}})+\left({\mathbf{T}}-{\mathbf{m}}\right)^{\top}{\mathbf{K}}_{\sigma^{2}}^{-1}\left({\mathbf{T}}-{\mathbf{m}}\right)\right\\}}$
(85)

####  A.4.2 Analytical expression of the posterior distribution

Suppose that we want to emulate the global temperature response for a
different emission scenario where we have access to greenhouse gas and
aerosols emission data $E_{1}^{*},\ldots,E^{*}_{m}$ at observation times
$t_{1}^{*}<\ldots<t^{*}_{m}$. We concatenate them into

${\mathbf{t}}^{*}=\begin{bmatrix}t_{1}^{*}\\\ \vdots\\\
t_{m}^{*}\end{bmatrix}\in{\mathbb{R}}^{m},\qquad{\mathbf{E}}^{*}=\begin{bmatrix}E_{1}^{*}\\\
\vdots\\\ E_{m}^{*}\end{bmatrix}\in{\mathbb{R}}^{m\times d},$ (86)

where $d\geq 0$ is the number of emission agents $\chi_{1},\ldots,\chi_{d}$ we
observe emissions from.

Using the posterior mean and covariance functions when ${\mathsf{T}}(t)$ is
updated with the training set ${\mathcal{D}}$, we define a posterior mean
vector and posterior covariance matrix over
${\mathbf{t}}^{*},{\mathbf{E}}^{*}$ given by

$\displaystyle\bar{\mathbf{m}}^{*}$
$\displaystyle=\bar{m}_{\mathsf{T}}({\mathbf{t}}^{*})$ (87)
$\displaystyle\bar{\mathbf{K}}^{*}$
$\displaystyle=\bar{k}_{\mathsf{T}}({\mathbf{E}}^{*},{\mathbf{E}}^{*}).$ (88)

Further, consider the emulated temperatures internal variability covariance
matrix defined by

${\boldsymbol{\Gamma}}^{*}=\gamma_{\mathsf{T}}({\mathbf{t}}^{*},{\mathbf{t}}^{*}).$
(89)

Then, the posterior distribution over emulated temperatures is exactly given
by the multivariate normal distribution
${\mathcal{N}}(\bar{\mathbf{m}}^{*},\bar{\mathbf{K}}^{*}+\sigma^{2}{\boldsymbol{\Gamma}}^{*})$.
Let us denote
$\bar{\mathbf{K}}^{*}_{\sigma^{2}}=\bar{\mathbf{K}}^{*}+\sigma^{2}{\boldsymbol{\Gamma}}^{*}$
for conciseness. This means that for a given temperature vector
${\mathbf{T}}^{*}\in{\mathbb{R}}^{m}$, we can exactly evaluate the probability
of ${\mathbf{T}}^{*}$ under the predicted distribution following

$\boxed{p({\mathbf{T}}^{*}|{\mathcal{D}},{\mathbf{E}}^{*},{\mathbf{t}}^{*})=\frac{1}{\sqrt{(2\pi)^{m}\det(\bar{\mathbf{K}}^{*}_{\sigma^{2}})}}\exp\left(-\frac{1}{2}({\mathbf{T}}^{*}-\bar{\mathbf{m}}^{*})^{\top}\left(\bar{\mathbf{K}}_{\sigma^{2}}^{*}\right)^{-1}({\mathbf{T}}^{*}-\bar{\mathbf{m}}^{*})\right).}$
(90)

The vector ${\mathbf{T}}^{*}$ may be a retained test scenario, in which case
computing
$p({\mathbf{T}}^{*}|{\mathcal{D}},{\mathbf{E}}^{*},{\mathbf{t}}^{*})$ provides
an evaluation of the emulated posterior
${\mathcal{N}}(\bar{\mathbf{m}}^{*},\bar{\mathbf{K}}^{*}_{\sigma^{2}})$.
${\mathbf{T}}^{*}$ may also simply correspond to temperature for which we
would like to assess the probability under emission scenario
$\\{{\mathbf{t}}^{*},{\mathbf{E}}^{*}\\}$. A natural application is in
detection attribution studies. Indeed, we can take ${\mathbf{T}}^{*}$ to be
observed historical temperatures, and
$\\{{\mathbf{t}}^{*},{\mathbf{E}}^{*}\\}$ to be a counterfactual historical
scenario without anthropogenic forcing. By evaluating
$p({\mathbf{T}}^{*}|{\mathcal{D}},{\mathbf{E}}^{*},{\mathbf{t}}^{*})$ we would
be able to assess to the probability of historical temperatures observations
to occur in a scenario without anthropogenic forcing.

The posterior distribution can also be used to draw a sample ${\mathbf{V}}$ if
needed following

${\mathbf{V}}=\left(\bar{\mathbf{K}}^{*}_{\sigma^{2}}\right)^{\nicefrac{{1}}{{2}}}{\mathbf{U}}+\bar{\mathbf{m}}^{*},\quad{\mathbf{U}}\sim{\mathcal{N}}(0,{\mathbf{I}}_{m}).$
(91)

Finally, whilst the above is formulated for global mean surface temperatures,
we can also derive analytical forms for the posterior distribution over the
radiative forcing and for spatially-resolved emulation.

##  Appendix B Complementary experimental results

###  B.1 Comparison of plain GP baseline with ClimateBench GP emulator from
watsonparris2021climatebench

####  B.1.1 Modelling differences

The plain GP baseline we use is analogous to the GP emulator from ClimateBench
[Watson-Parris . (2021)], but differs in two aspects.

First, we use in our plain GP baseline a covariance structure with automatic
relevance determination, denoted as
$\rho(E,E^{\prime})=C_{3/2}(E,E^{\prime})$, where $C_{3/2}$ denotes the
Matérn-3/2 covariance (see Appendix C.2).

This kernel introduces a different lengthscale parameter $\ell_{\chi}$ for
each atmospheric agent $\chi$, which is tuned through maximizing the marginal
loglikelihood. It is explicitely given by

$\rho(E,E^{\prime})=C_{3/2}(E,E^{\prime})=\left(1+\sqrt{3\sum_{\chi}\frac{(E^{\chi}-E^{\prime\chi})^{2}}{\ell_{\chi}^{2}}}\right)\exp\left(-\sqrt{3\sum_{\chi}\frac{(E^{\chi}-E^{\prime\chi})^{2}}{\ell_{\chi}^{2}}}\right),$
(92)

where $E^{\chi}$ denotes global emission level for agent
$\chi\in\\{\text{CH}_{4},\text{SO}_{2},\text{BC}\\}$, while for
$\chi=\text{CO}2$, it denotes global cumulative emission levels.

In contrast, watsonparris2021climatebench adopt an additive kernel structure
given by

$\rho(E,E^{\prime})=\sum_{\chi}\sigma_{\chi}C_{3/2}(E^{\chi},E^{\prime\chi})=\sum_{\chi}\sigma_{\chi}\left(1+\sqrt{3}\frac{|E^{\chi}-E^{\prime\chi}|}{\ell_{\chi}}\right)\exp\left(-\sqrt{3}\frac{|E^{\chi}-E^{\prime\chi}|}{\ell_{\chi}}\right).$
(93)

This additive structure introduces additional complexity through the variance
terms $\sigma_{\chi}$, which modulate the of each atmospheric agent to the
covariance, and need to be tuned alongside the lengthscales $\ell_{\chi}$.
From a functional perspective, choosing an additive kernel is equivalent to
representing the temperature response as the sum of independent GPs, where
each GP model the response to a single atmospheric agent. Further details on
the covariance function be found in [Watson-Parris . (2021), Appendix A2].

Second, in our plain GP baseline $E^{\text{SO}_{2}}$ and $E^{\text{BC}}$
correspond to global emission levels, whereas watsonparris2021climatebench
used the 5 principal components of spatial emission maps for SO2 and BC. We
anticipate that spatially-resolved inputs for aerosols emissions should
improve the model’s ability to predict spatially-resolved surface temperatures
features.

####  B.1.2 Predictive performance comparison

To compare the predictive performance against our plain GP and FaIRGP, we
evaluate the ClimateBench GP for the emulation of global and spatial mean
surface temperature anomaly and report scores in Table 8. All emulators are
trained on the same training data : historical, SSP126, SSP370, SSP585.
Predictive performance is evaluated for the emulation of SSP245 since this is
the test data used in [Watson-Parris . (2021)].

Table 8: Scores of ClimateBench GP, our Plain GP baseline and FaIRGP for the
task of emulating global and spatial mean surface temperatures on SSP245 ;
scores are computed over 2015-2100 period for global emulation and over
2080-2100 period for spatial emulation ; the best emulator scores are
highlighted in bold ; $\uparrow\\!/\\!\downarrow$ indicates higher/lower is
better.

| Emulator | RMSE$\;\downarrow$ | MAE$\;\downarrow$ | Bias | LL$\;\uparrow$ | Calib95 | CRPS$\;\downarrow$
---|---|---|---|---|---|---|---
Global | ClimateBench GP | 0.12 | 0.10 | 0.01 | -0.45 | 1.0 | 0.15
Plain GP | 0.09 | 0.07 | 0.03 | 0.67 | 1.0 | 0.06
FaIRGP | 0.09 | 0.08 | -0.01 | 0.71 | 1.0 | 0.06
Spatial | ClimateBench GP | 0.43 | 0.32 | -0.13 | -0.69 | 0.98 | 0.25
Plain GP | 0.56 | 0.40 | -0.19 | -0.70 | 0.97 | 0.28
FaIRGP | 0.36 | 0.26 | -0.05 | -0.34 | 0.99 | 0.20

Overall, FaIRGP demonstrates improved scores compared to the ClimateBench
baseline GP across various metrics, both in terms of global and spatial
emulation. In terms of global emulation, the predictive performance of the
Plain GP appears to be better than that of the ClimateBench GP. However, when
it comes to spatial surface temperature emulation, the ClimateBench GP
outperforms the Plain GP. This improvement can likely be attributed to the
utilization of spatially-resolved aerosol information as input in the
ClimateBench GP.

blo

###  B.2 Emulating anthropogenic aerosols forcing

Figure 10: Emulated global mean surface temperature anomaly over 1850-2014 for
the hist-aer scenario with FaIRGP trained over historical, SSP126, SSP245,
SSP370, SSP585. Figure 11: Maps of surface temperatures averaged for the hist-
aer experiment averaged over 1900-2014 period. Top-Left: Groundtruth
NorESM2-LM surface temperatures map. Top-Right: Prediction with the FaIR
pattern scaling baseline. Bottom-Left: Prediction with Plain GP posterior
mean. Bottom-Right: Prediction with the FaIRGP posterior mean.

##  Appendix C Complementary material on Gaussian processes

###  C.1 Additional illustrations for Gaussian processes

We provide here additional illustrations to develop intuition on how GPs can
be used for a regression task. Consider a simple regression problem
$y={\mathsf{f}}(x)+\upvarepsilon$ where
$\upvarepsilon\sim{\mathcal{N}}(0,\sigma^{2})$. Let $k(x,x^{\prime})$ be a
user-specified covariance function, and suppose we place a prior
${\mathsf{f}}(x)\sim{\operatorname{GP}}(0,k)$.

Figure 12 plots the mean function and the 95% credible interval that results
from our choice of prior over the regression function. Since this is
effectively a probability distribution over functions, we can draw samples
from it. Figure 13 shows the plots of 10 functions samples from this
distribution.

Figure 12: Plot of the ${\mathsf{f}}(x)\sim{\operatorname{GP}}(0,k)$ prior
mean function and 95% confidence region. Figure 13: Same Figure 12, but
plotting on top functions that are samples from the distribution over
functions specified by ${\mathsf{f}}(x)\sim{\operatorname{GP}}(0,k)$.

Figure 14 shows how the prior can be updated with observations of $y$, thereby
updating it into a posterior. Because the posterior is still a probability
distribution, we can still draw samples from it as shown in Figure 15.
However, the functions drawn are now constrained by the data and provide a
better fit to observations. The posterior GP therefore induces a probability
distribution over functions that provide a sound fit to observations

Figure 14: Plots of the posterior mean function and posterior 95% credible
interval when updating the prior with 0, (top-left), 1 (top-right), 2 (bottom-
left) and 10 (bottom-right) observations. Figure 15: Plots of the posterior
mean function and posterior 95% credible interval with 10 observations + plots
of functions sampled from the posterior distribution specified over functions.

###  C.2 Matérn covariance

The Matérn covariances are a class of stationary covariance functions widely
used in spatial statistics. The Matérn-$\nu$ covariance between two points
$x,x^{\prime}\in{\mathbb{R}}$ is given by

$C_{\nu}(x,x^{\prime})=\frac{2^{1-\nu}}{\Gamma(\nu)}\left(\sqrt{2\nu}\frac{|x-x^{\prime}|}{\ell}\right)^{\nu}K_{\nu}\left(\sqrt{2\nu}\frac{|x-x^{\prime}|}{\ell}\right),$
(94)

where $\Gamma$ is the gamma function, $K_{\nu}$ is the modified Bessel
function and $\ell>0$ is a lengthscale hyperparameter.

The covariance function expression considerably simplifies for $\nu=p+1/2$
where $p\in{\mathbb{N}}$. For example, for $\nu=1/2$ ($p=0$) and $\nu=3/2$
($p=1$) we have

$\displaystyle C_{1/2}(x,x^{\prime})$
$\displaystyle=\exp\left(-\frac{|x-x^{\prime}|}{\ell}\right)$ (95)
$\displaystyle C_{3/2}(x,x^{\prime})$
$\displaystyle=\left(1+\sqrt{3}\frac{|x-x^{\prime}|}{\ell}\right)\exp\left(-\sqrt{3}\frac{|x-x^{\prime}|}{\ell}\right)$
(96)

When $x,x^{\prime}\in{\mathbb{R}}^{d}$, the distance $|x-x^{\prime}|$ can be
substituted by the norm
$\|x-x^{\prime}\|=\sqrt{\sum_{i=1}^{d}(x_{i}-x_{i}^{\prime})^{2}}$. The
covariance is called an _automatic relevance determination_ (ARD) kernel when
each dimension has its own independent lengthscale parameter $\ell_{i}>0$. For
example, the Matérn-$1/2$ and Matérn-$3/2$ ARD kernel write

$\displaystyle C_{1/2}(x,x^{\prime})$
$\displaystyle=\exp\left(-\sqrt{\sum_{i=1}^{d}\frac{(x_{i}-x_{i}^{\prime})^{2}}{\ell_{i}^{2}}}\right)$
(97) $\displaystyle C_{3/2}(x,x^{\prime})$
$\displaystyle=\left(1+\sqrt{3\sum_{i=1}^{d}\frac{(x_{i}-x_{i}^{\prime})^{2}}{\ell_{i}^{2}}}\right)\exp\left(-\sqrt{3\sum_{i=1}^{d}\frac{(x_{i}-x_{i}^{\prime})^{2}}{\ell_{i}^{2}}}\right).$
(98)

When a Matérn-$p+1/2$ covariance function is used as a kernel for a GP, draws
from the GP are $p$ times continuously differentiable (with convention that
$0$ times means simply continuous).