# Concrete method for recovering the Euler characteristic of quantum
graphs111Accepted by “Journal of Physics A: Mathematical and Theoretical”
(DOI: 10.1088/1751-8121/ab95c1). Work under Creative Commons Attribution 4.0
licence .

Corentin Léna222Department of Mathematics, Stockholm University, 10691
Stockholm, Sweden.
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>and Andrea
Serio22footnotemark: 2

(4th June 2020)

###### Abstract

Trace formulas play a central role in the study of spectral geometry and in
particular of quantum graphs. The basis of our work is the result by Kurasov
which links the Euler characteristic $\chi$ of metric graphs to the spectrum
of their standard Laplacian. These ideas were shown to be applicable even in
an experimental context where only a finite number of eigenvalues from a
physical realization of quantum graph can be measured.

In the present work we analyse sufficient hypotheses which guarantee the
successful recovery of $\chi$. We also study how to improve the efficiency of
the method and in particular how to minimise the number of eigenvalues
required. Finally, we compare our findings with numerical
examples—surprisingly, just a few dozens of eigenvalues can be enough.

Keywords: quantum graphs, trace formula, Euler characteristic.

##  1 Introduction

###  1.1 Physical model

Schrödinger operators on metric graphs have long been studied as simplified
models of complex quantum mechanical systems, notably large molecules [1, 2].
More recently, under the name of _quantum graphs_ , they have been widely used
to describe nano-wires, wave-guides and networks [3, Chapter 8]. They have
also been investigated by mathematicians as a simplified setting in which to
understand complex problems in spectral theory, such as quantum chaos [4],
trace formulas [5, 4, 6, 7, 8] and nodal patterns [9]. From this point of
view, they stand midway between one-dimensional and multi-dimensional
Schrödinger operators. Indeed, metric graphs are one-dimensional objects with
a non-trivial geometry. The central theme in studying quantum graphs is
therefore the interaction of the spectrum with the geometry of the underlying
metric graph.

###  1.2 Mathematical problem

We consider in this work a finite, compact and connected metric graph
$\Gamma$. Following [10], we describe it by a set of $N$ edges
$\\{e_{1},\dots,e_{N}\\}$, with $e_{n}=[x_{2n-1},x_{2n}]$, and a set of $M$
vertices $\\{v_{1},\dots,v_{M}\\}$, which is a partition of the set of
endpoints $\\{x_{p}\,:\,1\leq p\leq 2N\\}$. The associated quantum graph is an
operator in the Hilbert space

$L_{2}(\Gamma)=\oplus_{n=1}^{N}L_{2}(e_{n}).$

More precisely, we define the _standard Laplacian_ $L_{\Gamma}$ on $\Gamma$,
which is the object of our study, in the following way. Its domain
$\mbox{Dom}(L_{\Gamma})$ consists of functions $f\in L_{2}(\Gamma)$ satisfying

  1. 1.

for every $1\leq n\leq N$, $f|_{e_{n}}\in W_{2}^{2}(e_{n})$;

  2. 2.

for every $1\leq m\leq M$,

    1. (a)

$f(x_{p})=f(x_{q})$ whenever the endpoints $x_{p}$ and $x_{q}$ belong to the
vertex $v_{m}$ (continuity condition),

    2. (b)

$\sum_{x_{p}\in v_{m}}\partial f(x_{p})=0$ (balance condition).

In the balance condition, $\partial f(x_{p})$ is the derivative along the edge
with endpoint $x_{p}$, taken towards the inside of the edge. The conditions in
(ii) are called the standard vertex conditions. The action of $L_{\Gamma}$ on
$f\in\mbox{Dom}(L_{\Gamma})$ is then given by the differential expression
$L_{\Gamma}f(x)=-f^{\prime\prime}(x)$ for all $n\in\\{1,\dots,N\\}$ and $x$ in
the interior of $e_{n}$.

It is known that the operator $L_{\Gamma}$ is self-adjoint, non-negative and
has compact resolvent. Its spectrum therefore consists of a sequence of non-
negative eigenvalues $(\lambda_{j})_{j\geq 1}$ of finite multiplicity tending
to $+\infty$ (we repeat them according to their multiplicities). Let us note
that $\lambda_{1}$ is always $0$ and that the hypothesis that $\Gamma$ be
connected implies that it is simple, with the associated eigenfunction
proportional to the constant function $1$. For the sake of convenience, we
will work in the rest of the paper with the _eigenfrequencies_
$k_{j}=\sqrt{\lambda_{j}}$.

Our goal is to recover information about the geometry of the graph from the
knowledge of some of its eigenfrequencies. This is a variation on Kac’s famous
problem “Can one hear the shape of a drum?” [11], with some specificities that
we will address below. The analogue to Kac’s problem in our setting would be
showing that two graphs with the same spectrum are isometric. There are
partial results in that direction. For instance, the eigenfrequencies of a
quantum graph satisfy Weyl’s law: as $j\to+\infty$, $k_{j}\sim\pi
j/{\mathcal{L}}$, where $\mathcal{L}$ is the total length of the graph, i.e.
the sum of the lengths of all its edges (see for instance [12]). The total
length of the graph can therefore be read off the complete spectrum.
Furthermore, the answer to Kac’s problem is positive provided all edge-lengths
of the graph are rationally independent [6, 7]. Nevertheless, if this last
condition is not satisfied, we can find graphs with the same spectrum that are
not isometric [6, 13, 14, 15].

We will restrict ourselves to recovering the main topological invariant of a
connected graph: its Euler characteristic $\chi$, defined by $\chi=M-N$. It is
related to $\beta_{1}$, the number of independent cycles in the graph, by
$\beta_{1}=1-\chi$. Let us point out that $\beta_{1}$ can also be recovered
from the number of zeros of the eigenfunctions, as shown in [16]. These
numbers are however less easily accessible to experiments.

###  1.3 Objectives

We focus on a situation that can be realized experimentally. A microwave
network can be described to a good approximation by a quantum graph, whose
eigenfrequencies correspond to resonances of the system. In [17] the authors
describe the measurement of about 50 resonances of such networks and use this
experimental result to recover $\chi$. Contrary to expectations, they find
this relatively small number of eigenfrequencies to be sufficient. Their
computation is based on a trace formula as we will see below in more details.
Extending the work in this paper, we want to check the correctness of the
method and modify it in order to improve the efficiency, or namely to reduce
the number of eigenfrequencies required.

The total length of the graph is a continuous parameter and an infinite number
of eigenfrequencies are needed to compute it using Weyl’s law, as described
above. By contrast, $\chi$ is integer valued and we can hope to compute it
with only a finite number of them. However, some assumptions on the graph are
needed. Indeed, by attaching a very small loop to some edge in an existing
graph, we decrease $\chi$ by $1$ while altering the first $50$
eigenfrequencies by an arbitrarily small amount. We come back to this point at
the end of Section 5. Therefore, our goal will also be to determine a
reasonable set of assumptions that guarantees the success of our methods.

##  2 Trace formula

###  2.1 Main tool

All our methods for computing the Euler characteristic are based on the trace
formula in [7, 8] (building on previous work in [5, 4, 6]). This formula
connects the spectrum of $L_{\Gamma}$, defined in the previous section, with
the set of periodic orbits in $\Gamma$, to be described below. More precisely,
the spectrum is described by the distribution

$u(k):=2\delta(k)+\sum_{k_{j}>0}\Big{(}\delta(k-k_{j})+\delta(k+k_{j})\Big{)},$
(1)

which is a tempered distribution of order $0$. We denote by $\mathcal{P}$ the
set of closed continuous paths in $\Gamma$ that are allowed to turn back on
themselves only at vertices, which we call _periodic orbits_ , or _orbits_. If
$p\in\mathcal{P}$, we denote by $\mbox{prim}(p)$ any shortest orbit such that
$p$ can be obtained by repeating $\mbox{prim}(p)$. Thus any two such orbits
have the same length, hence $\ell(\mbox{prim}(p))$ is well defined. The
following quantity will play a crucial role in our methods:

$\ell_{\mbox{\tiny min}}:=\min\\{\ell(p)\,:\,p\in\mathcal{P}\\}.$ (2)

######  Observation 2.1.

Notice that $\ell_{\mbox{\tiny min}}$ is given by the minimum between the
length of the shortest loop and twice the length of the shortest edge.

######  Proposition 2.2 (Theorem 1 from [7, 8], also [10]).

We have

$\displaystyle u(k)$
$\displaystyle=\chi\delta(k)+\frac{\mathcal{L}}{\pi}+\frac{1}{\pi}\sum_{p\in\mathcal{P}}\ell(\mbox{prim}(p))S_{V}(p)\cos
k\ell(p),$ (3)

where $S_{V}(p)$ is the product of all the vertex scattering coefficients
along the path $p$. The convergence of the series occurs in the space
$\mathcal{S}^{\prime}(\mathbb{R})$ of tempered distributions.

######  Remark 2.3.

The terms $S_{V}(p)$ will ultimately drop out of our formulas due to our
choice of test functions. Since they will not play a role in our analysis we
just refer to [7] for their definition.

######  Remark 2.4.

Taking the Fourier transform on both sides of Equation (3), we obtain

$\hat{u}(\ell)=\chi+2\mathcal{L}\delta(\ell)+\sum_{p\in\mathcal{P}}\ell(\mbox{prim}(p))S_{V}(p)\Big{(}\delta(\ell-\ell(p))+\delta(\ell+\ell(p))\Big{)},$
(4)

which is the form of the Trace Formula that we will be using in the rest of
the paper.

In all the paper, we define the Fourier transform so that
$\hat{f}(k)=\int_{-\infty}^{+\infty}e^{ik\ell}f(\ell)\,d\ell$ for any $f\in
L_{1}(\mathbb{R})$. By definition of the Fourier transform of a tempered
distribution, for $\varphi$ in the Schwartz class $\mathcal{S}(\mathbb{R})$,
$\hat{u}[\varphi]=u[\hat{\varphi}]$, which means, using Equations (1) and (4),

$\displaystyle\chi\int_{-\infty}^{+\infty}\varphi(\ell)\,d\ell+2\mathcal{L}\varphi(0)+\sum_{p\in\mathcal{P}}\ell(\mbox{prim}(p))S_{V}(p)\left(\varphi(-\ell(p))+\varphi(\ell(p))\right)$
$\displaystyle=2\hat{\varphi}(0)+\sum_{k_{j}>0}\Big{(}\hat{\varphi}(k_{j})+\hat{\varphi}(-k_{j})\Big{)}.$
(5)

Equation (5) also holds for some functions not in $\mathcal{S}(\mathbb{R})$.
For our purpose, we will consider the set $\mathcal{T}$ of functions $\varphi$
satisfying the following assumptions:

  1. 1.

$\varphi$ is continuous on $\mathbb{R}$ and nonnegative;

  2. 2.

$\mbox{supp}(\varphi)\subseteq[0,T]$ for some $T>0$;

  3. 3.

$\int_{-\infty}^{+\infty}\varphi(\ell)\,d\ell=1$;

  4. 4.

the function $F_{\varphi}$ is integrable on $(0,+\infty)$, where
$F_{\varphi}(k):=\sup_{y\geq k}|\Re(\hat{\varphi}(y))|$.

Let us make some comments on Condition (iv). The function $F_{\varphi}$ can be
seen as the smallest non-increasing majorant of $|\Re(\hat{\varphi})|$ on
$(0,+\infty)$. Its integrability is used both to express $\chi$ as the sum of
a convergent series and to prove error estimates.

######  Proposition 2.5.

If $\varphi\in\mathcal{T}$,

$\chi+\sum_{p\in\mathcal{P}}\ell(\mbox{prim}(p))S_{V}(p)\Big{(}\varphi(-\ell(p))+\varphi(\ell(p))\Big{)}=2\hat{\varphi}(0)+2\sum_{k_{j}>0}\Re\left(\hat{\varphi}(k_{j})\right).$
(6)

We prove the above proposition in A. Let us note that whenever $\varphi$ is in
$\mathcal{T}$, so is $\varphi_{t}(l):=t\varphi(t\ell)$, for any $t>0$.

We can now state the result by which we recover the Euler characteristic of
$\Gamma$.

######  Proposition 2.6.

For any $\varphi\in\mathcal{T}$ such that $T=1$ in (ii) then

$\chi=2\hat{\varphi_{t}}(0)+2\sum_{k_{j}>0}\Re\left(\hat{\varphi_{t}}(k_{j})\right)\qquad\forall
t\geq 1/\ell_{\mbox{\tiny min}},$ (7)

where $\ell_{\mbox{\tiny min}}$ is defined in (2).

###### Proof.

Since $t\geq 1/\ell_{\mbox{\tiny min}}$, the support of $\varphi_{t}$ is
contained in $[0,\ell_{\mbox{\tiny min}}]$. Equation (7) then follows
immediately from Equation (6). ∎

In the rest of the paper, we assume that $t\geq 1/\ell_{\mbox{\tiny min}}$.
When we will analyse our method, it will accordingly be important to know a
lower bound of $\ell_{\mbox{\tiny min}}$ in order to guarantee a successful
estimate of $\chi$. On the other hand, from the above proposition we also have
the following corollary, cf. [18].

######  Corollary 2.7.

For any $\varphi\in\mathcal{T}$ then

$\chi=\lim_{t\to\infty}\left(2\hat{\varphi_{t}}(0)+2\sum_{k_{j}>0}\Re\left(\hat{\varphi_{t}}(k_{j})\right)\right).$
(8)

The limit and summation signs in (8) cannot be exchanged since
$\lim_{t\to\infty}\Re\left(\hat{\varphi_{t}}(k)\right)=\hat{\varphi}(0)$
independently of $k$. Hence it is clear that (8) cannot be approximated by the
limit of a finite sum over the smallest, say $J$, eigenfrequencies. Because of
Assumption (iv) on $\varphi$, the summation will be shown to be absolutely
converging (see Section 3). Based on that, our plan is to quantify for each
$t$ how many eigenfrequencies $J$ are necessary for the truncated summation to
differ from (8) by less than $1/2$, and hence the nearest integer to the sum
to coincide with $\chi$. Theorem 4.1 gives an optimal (minimal) number $J^{*}$
of required eigenfrequencies, based on the choice of $t$. As one can expect
the worse the estimate of $\ell_{\mbox{\tiny min}}$ (smaller lower bound),
hence the larger $t$ is, the larger the number $J^{*}$ of required
eigenfrequencies.

######  Remark 2.8.

The above trace formula holds for the standard Laplacian, specifically for
standard vertex conditions imposed at all the vertices. In [19, 20] are
presented versions of the trace formula for more general vertex conditions
where in particular the constant term in $\hat{u}$ may differ from $\chi$.
Hence our method might not be applicable in presence of vertex conditions
other than standard. It is even possible that $\chi$ cannot be recovered
knowing the whole spectrum of the graph: see [13, 14, 15] for an example of
two graphs with mixed vertex conditions which have distinct values of $\chi$
despite being isospectral.

###  2.2 Choice of the test function

Let us apply Formula (7) to a triangular function:

$\psi(\ell):=4\ell\mathds{1}_{[0,1/2]}(\ell)+4(1-\ell)\mathds{1}_{[1/2,1]}(\ell).$

Everywhere in the paper, $\mathds{1}_{A}$ stands for the characteristic
function of the set $A$. We find

$\displaystyle\hat{\psi}(k):=\int_{0}^{1}\psi(\ell)e^{ik\ell}\,d\ell=e^{ik/2}\left(\frac{\sin(k/4)}{k/4}\right)^{2}.$

Proposition (2.6) then gives us the following expression for $\chi$, assuming
$t\geq 1/\ell_{\mbox{\tiny min}}$:

$\chi=2+2\sum_{k_{j}>0}\cos(k_{j}/2t)\left(\frac{\sin(k_{j}/4t)}{k_{j}/4t}\right)^{2}.$
(9)

We can also apply the same formula to a truncated trigonometric function:

$\varphi(\ell):=(1-\cos(2\pi\ell))\mathds{1}_{[0,1]}(\ell)$

We find

$\displaystyle\hat{\varphi}(k)$
$\displaystyle:=\int_{0}^{1}\left(1-\frac{e^{2i\pi\ell}}{2}-\frac{e^{-2i\pi\ell}}{2}\right)e^{ik\ell}\,d\ell$
$\displaystyle=-\frac{8\pi^{2}}{k(k-2\pi)(k+2\pi)}e^{ik/2}\sin(k/2)$

We deduce another expression for $\chi$, valid whenever $t\geq
1/\ell_{\mbox{\tiny min}}$:

$\chi=2-8\pi^{2}\sum_{k_{j}>0}\frac{\sin(k_{j}/t)}{k_{j}/t(k_{j}/t-2\pi)(k_{j}/t+2\pi)}.$
(10)

This formula is the one employed in [17].

In order to recover $\chi$ from a finite set of eigenfrequencies, we have to
replace the series on the right-hand side of Formulas (9) and (10) by partial
sums. Since the terms in the second series go to zero more quickly than in the
first, we can expect that fewer eigenfrequencies are necessary to find a close
approximation of $\chi$, which we will then be rounded (up or down) to the
nearest integer. Both numerical trials and the analysis of the experimental
results in [17] confirm this. The more regular $\varphi$ is, the faster
$\hat{\varphi}$ decays at infinity. We can then wonder how much we can
decrease the number of eigenfrequencies used to compute $\chi$. To study this
question, we will consider the one-parameter family of test functions

$\varphi_{d}(\ell)=C_{d}\left(1-\cos(2\pi\ell)\right)^{d}\mathds{1}_{[0,1]}(\ell),$

where $d$ is a positive integer, which we call _order_ , and $C_{d}$ is chosen
so that $\int_{-\infty}^{+\infty}\varphi_{d}(\ell)\,d\ell=1$. We easily check
that the function $\varphi_{d}$ is of class $\mathcal{C}^{2d-1}$ on
$\mathbb{R}$. We show in B that

$C_{d}=\frac{2^{d}(d!)^{2}}{(2d)!}$

and that the Fourier transform of $\varphi_{d}$ is

$\hat{\varphi}_{d}(k)=\frac{(-1)^{d}(d!)^{2}}{\pi\Pi_{j=-d}^{d}(k/(2\pi)+j)}e^{ik/2}\sin(k/2).$

Our goal is to give rigorous error estimates and to perform numerical trials
for this family of functions.

##  3 General estimate

###  3.1 Calculation with exact spectrum

For a fixed graph $\Gamma$, we assume that only the smallest $J$ eigenvalues
of the standard Laplacian are known. We consider the distribution (1)
evaluated on the Fourier transform of a generic function
$\varphi\in\mathcal{T}$ and split the expression in the following way

$u[\hat{\varphi}_{t}]=\underbrace{2\sum_{j\leq
J}\Re\left(\hat{\varphi_{t}}(k_{j})\right)}_{\textstyle
S_{J}(t)}+\underbrace{2\sum_{j>J}\Re\left(\hat{\varphi_{t}}(k_{j})\right)}_{\textstyle
R_{J}(t)}.$ (11)

We call $S_{J}(t)$ the _truncated sum_ and $R_{J}(t)$ the _remainder_ or
_tail_. We have

$|S_{J}(t)-\chi|\leq|u[\hat{\varphi}_{t}]-\chi|+|R_{J}(t)|.$ (12)

Let $\varphi\in\mathcal{T}$ such that $T=1$ in Condition (ii) be fixed.
Because of Proposition 2.6 when $t\geq 1/\ell_{\mbox{\tiny min}}$ the term
$|u[\hat{\varphi}_{t}]-\chi|$ is zero, hence $|S_{J}(t)-\chi|\leq|R_{J}(t)|$.

$\displaystyle|R_{J}(t)|$ $\displaystyle\leq
2\sum_{j>J}|\Re\hat{\varphi}(k_{j}/t)|$ (13) $\displaystyle\leq
2\sum_{j>J}\sup_{k\geq
k_{j}}\left|\Re\hat{\varphi}(k/t)\right|=2\sum_{j>J}F_{\varphi}(k_{j}/t),$
(14)

where $F_{\varphi}$, is defined in Condition (iv) of $\mathcal{T}$. In
particular, $F_{\varphi}$ is positive decreasing to zero 333This follows
immediately from the fact that $\Re\hat{\varphi}$ has only isolated zeros.
Indeed, it is a real-analytic function which is not identically zero.. At this
point we employ the classical eigenvalue estimate
$k_{j}\geq(j-M)\pi/\mathcal{L}$ (see for instance [21]) and we bound the
summation over the integers of a monotone function by its integral.

$\displaystyle|R_{J}(t)|$ $\displaystyle\leq
2\sum_{j>J-M}F_{\varphi}\left(\frac{\pi}{\mathcal{L}}\frac{j}{t}\right)$ (15)
$\displaystyle\leq
2\int_{J-M}^{\infty}F_{\varphi}\left(\frac{\pi}{\mathcal{L}}\frac{x}{t}\right)\,dx$
(16)
$\displaystyle=2\frac{\mathcal{L}t}{\pi}\int_{\frac{\pi}{\mathcal{L}t}(J-M)}^{\infty}F_{\varphi}\left(\mbox{x}\right)\,d\mbox{x}=:\mathcal{E}_{\varphi}(J-M,\mathcal{L}t).$
(17)

The function $\mathcal{E}_{\varphi}:\mathbb{R}^{2}_{+}\to\mathbb{R}_{+}$ is
continuous, positive, and monotone with respect to both arguments. In
particular $\mathcal{E}_{\varphi}(J-M,\cdot)$ is strictly monotone increasing,
while $\mathcal{E}_{\varphi}(\cdot,{\mathcal{L}t})$ is strictly monotone
decreasing to zero. Since $\chi$ is an integer number (generally negative) it
is enough to ensure that $|R_{J}(t)|<1/2$ in order to compute $\chi$.
Therefore we define $J_{\mbox{\tiny
min}}(M,\mathcal{L}t):=\min\\{J\in\mathbb{N}:\mathcal{E}_{\varphi}(J-M,\mathcal{L}t)<1/2\\}$,
this is the minimum number of eigenvalues needed for computing $\chi$. This
can be further extended to the case where only partial information on $\Gamma$
is known. The result is summarised in

######  Theorem 3.1.

Let $\Gamma$ be a graph which

  * •

has at most $\overline{M}$ vertices, i.e. $M\leq\overline{M}$;

  * •

has total length at most $\overline{\mathcal{L}}$, i.e.
$\mathcal{L}\leq\overline{\mathcal{L}}$;

  * •

has its shortest orbits at least $\underline{\ell_{\mbox{\tiny min}}}$ long,
i.e. $\ell_{\mbox{\tiny min}}\geq\underline{\ell_{\mbox{\tiny min}}}$.

Let $\varphi\in\mathcal{T}$ with $T=1$ and let
$t=1/\underline{\ell_{\mbox{\tiny min}}}$. Then $J\geq J_{\mbox{\tiny
min}}=J_{\mbox{\tiny min}}(\overline{M},\overline{\mathcal{L}}t)$ eigenvalues
of the standard Laplacian on $\Gamma$ suffice for recovering the Euler
characteristic of $\Gamma$ via the formula

$\chi(\Gamma)=\mbox{\emph{nint}}\left[S_{J}\left(t\right)\right],$ (18)

where $\mbox{\emph{nint}}(x)$ denotes the nearest integer function.

###### Proof.

Because $t=1/\underline{\ell_{\mbox{\tiny min}}}\geq 1/\ell_{\mbox{\tiny
min}}$ then Proposition 2.6 implies $|\chi-u(\hat{\varphi_{t}})|=0$, hence
(12) reads $|\chi-
S_{J}(t)|\leq|R_{J}(t)|\leq\mathcal{E}_{\varphi}(J-M,\mathcal{L}t)$. Because
of the monotonicity of $\mathcal{E}_{\varphi}$, we have
$\mathcal{E}_{\varphi}(J-M,\mathcal{L}t)\leq\mathcal{E}_{\varphi}(J-\overline{M},\overline{\mathcal{L}}t)$.
Hence for $J\geq J_{\mbox{\tiny min}}$ it follows that $|\chi-S_{J}(t)|<1/2$,
and thus we obtain (18). ∎

Notice that the cases $S_{J}(t)=\chi\pm 1/2$ is excluded, hence we do not need
to worry of the definition of the function $\mbox{nint}[\cdot]$ over the half
integers.

We notice that the hypothesis of the above theorem cannot be relaxed too much.
In particular, the condition $\ell_{\mbox{\tiny
min}}\geq\underline{\ell_{\mbox{\tiny min}}}$ is crucial, because adding small
loops to any graph perturbs its smallest eigenvalues only a little, but at the
same time it does dramatically affect its topological structure, decreasing
$\chi$ by $1$.

We also notice that the quantity $\overline{\mathcal{L}}$ can be obtained from
other information on the graph when available. For instance if the number of
edges of the graph is at most $\overline{N}$ then
$\displaystyle\mathcal{L}\leq\min_{2\leq j\leq J}({j}+\overline{N})\pi/k_{j}$.

######  Remark 3.2.

The above Theorem 3.1 can be reproduced after replacing $F_{\varphi}$ by any
other majorant function monotone decreasing. The $J_{\mbox{\tiny min}}$
computed will be different. We will use this remark in Section 4.

###  3.2 Calculation with approximate spectrum

Since we have in mind to apply our method in an experimental context we need
to consider the case where the eigenvalues are known only up to some
approximation. We denote by $\\{\widetilde{k}_{j}\\}_{j=1}^{J}$ the
approximate spectrum where each eigenfrequency is measured with precision
$\delta$, meaning that $\left|\widetilde{k}_{j}-k_{j}\right|\leq\delta$ for
all $1\leq j\leq J$. Hence we define $\widetilde{S}_{J}(t)=2\sum_{j\leq
J}\Re\hat{\varphi_{t}}(\tilde{k}_{j})$ the truncated sum evaluated at the
approximated eigenvalues, hence our new aim is to approximate $\chi$ from
$\widetilde{S}_{J}(t)$. Therefore to the error contribution
$\mathcal{E}_{\varphi}(J-M,\mathcal{L}t)$ we need to add a new term

$\left|\widetilde{S}_{J}(t)-\chi\right|\leq\mathcal{E}_{\varphi}(J-M,\mathcal{L}t)+\left|\widetilde{S}_{J}(t)-S_{J}(t)\right|.$
(19)

This second term can be bounded linearly in $\delta$ in the following way

$\displaystyle\left|\widetilde{S}_{J}(t)-S_{J}(t)\right|$
$\displaystyle=\left|2\sum_{j\leq
J}\Re(\hat{\varphi}(\widetilde{k_{j}}/t)-\hat{\varphi}(k_{j}/t))\right|$ (20)
$\displaystyle\leq 2\left|\sum_{j\leq
J}\int_{0}^{1}\left(\cos{\widetilde{k_{j}}\ell/t}-\cos{k_{j}\ell/t}\right)\varphi(\ell)\,d\ell\right|$
(21) $\displaystyle\leq 2\left|\sum_{j\leq
J}\int_{0}^{1}-2\sin{\frac{(\widetilde{k_{j}}-k_{j})\ell}{2t}}\sin{\frac{(\widetilde{k_{j}}+k_{j})\ell}{2t}}\varphi(\ell)\,d\ell\right|$
(22) $\displaystyle\leq\frac{2\delta}{t}\sum_{j\leq
J}\left|\int_{0}^{1}\sin{\frac{(\widetilde{k_{j}}+k_{j})\ell}{2t}}\varphi(\ell)\,d\ell\right|$
(23) $\displaystyle\leq\frac{2\delta J}{t}.$ (24)

Therefore we define

$\widetilde{\mathcal{E}}_{\varphi}(J-M,\mathcal{L},t):=\mathcal{E}_{\varphi}(J-M,\mathcal{L}t)+\frac{2\delta
J}{t}.$ (25)

For this new function there does not necessarily always exists $J$ such that
$\widetilde{\mathcal{E}}_{\varphi}(J-M,\mathcal{L},t)<1/2$. For simplicity we
consider separately the following two inequalities, which together are
sufficient:

  * •

$\mathcal{E}_{\varphi}(J-M,\mathcal{L}t)<1/4$;

  * •

$2\delta J/t<1/4$.

We derive from them the following two conditions:

  * •

$J\geq\widetilde{J}_{\mbox{\tiny
min}}(M,\mathcal{L}t):=\min\\{J\in\mathbb{N}:J>M,\,\mathcal{E}_{\varphi}(J-M,\mathcal{L}t)<1/4\\};$
(26)

  * •

$\delta\leq\widetilde{\delta}_{\mbox{\tiny max}}(t,J):=t/(8J).$ (27)

If the first $J$ eigenvalues are known such that both the above conditions are
satisfied then we are able to compute the Euler characteristic via the
approximated spectrum. The above analysis can be summarised in the following

######  Theorem 3.3.

Let $\Gamma$, $\varphi$ and $t$ be as in the hypotheses of Theorem 3.1, and
moreover let the first $J$ eigenvalues of the standard Laplacian on $\Gamma$
be known up to error $\delta$. Assume that $J$ and $\delta$ satisfy both
conditions (26) and (27) with $M,\mathcal{L}$ replaced by
$\overline{M},\overline{\mathcal{L}}$. Then the Euler characteristic of
$\Gamma$ can be recovered via the following formula

$\chi(\Gamma)=\mbox{\emph{nint}}\left[\widetilde{S}_{J}\left(t\right)\right].$
(28)

##  4 Example of a family of test functions

###  4.1 Error estimate and optimal order

We now apply the analysis in Section 3 to the test functions $\varphi_{d}$
introduced at the end of Section 2. In the rest of the section, we assume that
$t=1/\underline{\ell_{\mbox{\tiny min}}}$. We have

$\Re\left(\hat{\varphi}_{d}(k)\right)=\frac{(-1)^{d}(d!)^{2}\sin(k)}{2\pi\Pi_{j=-d}^{d}(k/(2\pi)+j)},$

so that, when $k>2\pi d$,

$F_{\varphi}(k)\leq\frac{(d!)^{2}}{2\pi(k/(2\pi)-d)^{2d+1}}.$

Let us write $R_{d,J}(t)$ for the remainder denoted in Section 3 by
$R_{J}(t)$, in the case where $\hat{\varphi}=\hat{\varphi}_{d}$. According to
Remark 3.2, we find, for $J>2t\mathcal{L}d+M$,

$\left|R_{d,J}(t)\right|\leq\frac{{2}t\mathcal{L}}{\pi}\int_{\frac{\pi}{t\mathcal{L}}(J-M)}^{+\infty}\frac{(d!)^{2}}{2\pi(k/(2\pi)-d)^{2d+1}}\,dk=\frac{(d!)^{2}(2t\mathcal{L})^{2d+1}}{2\pi
d(J-M-2t\mathcal{L}d)^{2d}}.$

Using the inequality $d!\leq\sqrt{2\pi d}d^{d}e^{-d+{1/12}}$ (see for instance
Formula (3.9) in [22]), we find that

$\left|R_{d,J}(t)\right|\leq\varepsilon(M,\rho,d,J),$ (29)

with $\rho:=2t\mathcal{L}$ and

$\varepsilon(\mu,\gamma,\alpha,\beta):=\frac{\alpha^{2\alpha}e^{-2\alpha+1/6}\gamma^{2\alpha+1}}{(\beta-\mu-\gamma\alpha)^{2\alpha}}.$
(30)

Let us note that we have replaced the discrete (integer) values $d$ and $J$ by
the continuous parameters $\alpha$ and $\beta$.

######  Theorem 4.1.

For fixed $M$ and $\rho$ positive and $\overline{\varepsilon}\in(0,1)$, there
exists $J^{*}$, the smallest among the integers $J$ such that
$\varepsilon(M,\rho,d,J)\leq\overline{\varepsilon}$ is satisfied for some $d$.
There exists then $d^{*}$, the smallest positive integer $d$ such that
$\varepsilon(M,\rho,d,J^{*})\leq\overline{\varepsilon}$. Furthermore, these
integers are given by the following formulas

$J^{*}=\min\\{\lceil\beta(\overline{\varepsilon},M,\rho,d)\rceil\,:\,d\in\\{\lfloor\alpha^{*}(\overline{\varepsilon},\rho)\rfloor,\lceil\alpha^{*}(\overline{\varepsilon},\rho)\rceil\\}\\}$
(31)

and

$d^{*}=\min\\{d\,:\,d\in\\{1,\dots,\lceil\alpha^{*}(\overline{\varepsilon},\rho)\rceil\\}\mbox{
and }\lceil\beta(\overline{\varepsilon},M,\rho,d)\rceil=J^{*}\\},$ (32)

where

$\beta(\overline{\varepsilon},M,\rho,d)=M+\rho
d\left(1+\frac{1}{e}\left(\frac{e^{1/6}\rho}{\overline{\varepsilon}}\right)^{1/(2d)}\right)$

and

$\alpha^{*}(\overline{\varepsilon},\rho)=\frac{1}{2(1+W(1))}\ln\left(\frac{e^{1/6}\rho}{\overline{\varepsilon}}\right).$

######  Remark 4.2.

We denote by $W(1)$ the unique positive number satisfying $W(1)e^{W(1)}=1$.
The notation $W(1)$ is standard and denotes the value of the Lambert
W-function at $1$ (see [23, Eq. 4.13.1]).

######  Remark 4.3.

Existence of the integers $J^{*}$ and $d^{*}$ follows immediately from the
fact that $\beta\mapsto\varepsilon(M,\rho,d,\beta)$ decreases to $0$ for any
positive integer $M$ and $d$ and any $\rho>0$. Our actual goal is thus to
prove Equations (31) and (32), which we use to compute them.

###### Proof of Theorem 4.1.

It follows from Equation (30) that the unique $\beta\in(M+\rho\alpha,+\infty)$
which solves the equation
$\varepsilon(M,\rho,\alpha,\beta)=\overline{\varepsilon}$ is

$\beta(\overline{\varepsilon},M,\rho,\alpha)=M+\rho\alpha\left(1+\frac{1}{e}\left(\frac{e^{1/6}\rho}{\overline{\varepsilon}}\right)^{1/(2\alpha)}\right).$
(33)

This implies that, for any positive integer $d$, the smallest integer $J$ such
that $\varepsilon(M,\rho,d,J)\leq\overline{\varepsilon}$ is equal to
$\lceil\beta(\overline{\varepsilon},M,\rho,d)\rceil$. Differentiating Equation
(33) with respect to $\alpha$, we find

$\frac{d}{d\alpha}\beta(\overline{\varepsilon},M,\rho,\alpha)=\rho\left(1+\frac{1}{e}\left(\frac{e^{1/6}\rho}{\overline{\varepsilon}}\right)^{1/(2\alpha)}\left(1-\frac{1}{2\alpha}\ln\left(\frac{e^{1/6}\rho}{\overline{\varepsilon}}\right)\right)\right).$

Using the substitution

$s:=\frac{1}{2\alpha}\ln\left(\frac{e^{1/6}\rho}{\overline{\varepsilon}}\right)-1,$

we see that this derivative vanishes if, and only if, $se^{s}=1$. This
equation has a unique positive solution which is, by definition, $s=W(1)$.
Therefore, the derivative vanishes only at
$\alpha=\alpha^{*}(\overline{\varepsilon},\rho)$, with

$\alpha^{*}(\overline{\varepsilon},\rho)=\frac{1}{2(1+W(1))}\ln\left(\frac{e^{1/6}\rho}{\overline{\varepsilon}}\right).$

We can easily check that the derivative is negative below that value and
positive above, so that
$\alpha\mapsto\beta(\overline{\varepsilon},M,\rho,\alpha)$ is first decreasing
and then increasing. The function
$d\mapsto\beta(\overline{\varepsilon},M,\rho,d)$ takes its smallest value
among all positive integers for the largest integer below
$\alpha^{*}(\overline{\varepsilon},\rho)$ or the smallest integer above.
Equations (31) and (32) then follow easily.

∎

##  5 Numerical examples

We have numerically tested our method on some graphs for which we have
computed the exact spectrum up to machine error precision and then added an
error term uniformly distributed with prescribed variance. In this section we
give an overview of the implemented algorithm and show a few examples of its
application. We recall the quantities that appear in the numerical analysis:

  * •

$t$ is the rescaling parameter of the test function;

  * •

$d,(d^{*})$ is the order of the test function $\varphi_{d}$, (respectively the
minimal order according to equation (32));

  * •

$J,(J^{*})$ is the number of the first smallest eigenfrequencies used to
compute $S_{J}(t)$, (respectively the minimal number according to Equation
(31));

  * •

$S_{J}(t)$ is the truncated sum defined in (11) computed on the first $J$
eigenfrequencies of the exact spectrum where the test function is rescaled by
$t$;

  * •

$\widetilde{S}_{J}(t)$ is the same truncated sum as $S_{J}(t)$, but computed
on a sample of the spectrum affected by a certain error term.

In view of the result of Proposition 2.6 one might expect to obtain a good
approximation of $\chi$ by computing the limit as $t\to\infty$ of the right
hand side of (7). Unfortunately this works out only if all eigenvalues are
taken into account in the computation.

###  5.1 Code overview

The code consists of three distinct parts each of them developed to run on the
software Mathematica [24].

  1. 1.

The first part is a GUI for building a graph with a drawing, drag-and-drop
method and inserting the lengths of the edge.

  2. 2.

The second part contains an algorithm which computes the eigenvalues of the
standard Laplacian of the graph in input. This is based on the von Below
formula [25] which holds for equilateral metric graphs, cf. [12, 10]. This
code shares parts with an other study in [26] on how this method can be
extended to approximate eigenvalues of non equilateral metric graphs. Several
samples of approximate spectra $\\{\widetilde{k}_{j}\\}_{j\in\mathbb{N}}$ are
realized by summing a pseudo-random number uniformly distributed over a
prescribed interval to the exact spectrum: $\widetilde{k}_{j}=k_{j}+e_{j}$,
$e_{j}\sim\mathcal{U}([-\delta,+\delta])$.

  3. 3.

The last part computes the parameters $d^{*},J^{*}$, and Formula (18), plots
the maps $t,J\mapsto S_{J}(t)$ and several instances of the the maps
$t,J\mapsto\widetilde{S}_{J}(t)$ over different samples of spectra with error
terms, and compares the error bound $\varepsilon(M,2t\mathcal{L},d,J)+2\delta
J/t$ with the numerical errors $|\widetilde{S}_{J}(t)-\chi|$ over different
values of $t$ and $J$.

###  5.2 Comparison of the theoretical bounds with the experimental error

Figure 1: On the left the Lasso graph, $\chi=0$, the loop has length
$\ell_{1}=1$ and the pendant edge has length $\ell_{2}=5$, hence
$\ell_{\mbox{\tiny min}}=1$, $\rho=12$ and $d^{*}=1$; on the right the graph
$K_{5},\chi=-5$, each edge has assigned length one, hence $\ell_{\mbox{\tiny
min}}=2$, $\rho=10$ and $d^{*}=1$. The lengths of the edges are not to scale.

Here we present some computations of $S_{J}(t)$ and $\widetilde{S}_{J}(t)$
under different values of $J$ and $t$ compared with $\chi$ performed for the
graphs Lasso and $K_{5}$ (see Figure 1). We used the test function of optimal
order $d^{*}$, equal to $1$ in both cases.

Figure 2: Plots for the Lasso graph: In the first three plots $J=J^{*}=48$ is
fixed and the value $t=1/\ell_{\mbox{\tiny min}}=1$ is shown with the dashed
vertical line. In the bottom right plot $t=1/\ell_{\mbox{\tiny min}}=1$ is
fixed. The samples of approximate spectra are computed with $\delta\approx
2.6\cdot 10^{-3}$.

Let us explain how the numerical results are displayed in Figures 2 and 3.

Top left

: the function $t\mapsto S_{J}(t)$ (in black) is compared with

several instances of $t\mapsto\widetilde{S}_{J}(t)$, corresponding to
different samples of the approximate spectrum. The curves are not visibly
distinguishable despite the different error terms.

Top right

: the function $t\mapsto S_{J}(t)$ is compared for two different test
functions, $\varphi_{d}$ (black solid curve) and the triangular function
$\psi$ (blue dashed curve).

Bottom left

:

several instances of the error $t\mapsto|\chi-\widetilde{S}_{J}(t)|$ (purple
solid curves) are compared with the theoretical bounds
$t\mapsto\varepsilon(M,\rho,d,J)+2\delta J/t$ (the red thick dashed curve,
with the thin curves representing the two addends) We recall that we have
assumed $t\geq 1/\ell_{\mbox{\tiny min}}$ when we computed the theoretical
bounds.

Bottom right

:

several instances of the error $J\mapsto|\chi-\widetilde{S}_{J}(t)|$ (purple
dots) are compared with the theoretical bound
$J\mapsto\varepsilon(M,\rho,d,J)+2\delta J/t$ (the red thick dashed curve,
with the thin curves representing the two addends).

Figure 3: Plots for the graph $K_{5}$: in the first three plots $J=J^{*}=41$
is fixed and the value $t={1/\ell_{\mbox{\tiny min}}}=0.5$ is shown with the
dashed vertical line. In the bottom right plot $t={1/\ell_{\mbox{\tiny
min}}}=0.5$ is fixed. The samples of approximate spectra are computed with
$\delta\approx 1.5\cdot 10^{-3}$.

######  Observation 5.1.

We now gather some observations which hold for both Figures 2 and 3.

  1. 1.

In the two plots at the top right we notice that the black curve approximates
$\chi$ with higher precision than the blue curve, i.e. it stays within
distance $1/2$ from $\chi$ for a certain interval in $t$. This shows that the
method with $\varphi_{d}$ is significantly more efficient compared with $\psi$
in terms of number of eigenfrequencies sufficient in order to compute $\chi$.

  2. 2.

The two plots at the bottom show that the theoretical bound exceeds the
numerical error by at least a factor $10^{2}$. This phenomenon can be
explained by the several cancellations occurring inside the tail $R_{d,J}(t)$
which we did not take into account in (29).

  3. 3.

In the bottom left plots it can be observed that both the theoretical bound
and the numerical error grow with respect to the parameter $t$, indicating
that it is important for the effectiveness of the method to have a good lower
bound of $\ell_{\mbox{\tiny min}}$.

  4. 4.

In the bottom right plot we observe that for $J$ growing the numerical error
stabilizes at small positive values different for different samples. This
suggests that the precision does not improve by taking $J\gg J^{*}$ and that
the error mainly depends on the contribution from the first terms in the
summation $\widetilde{S}_{J}(t)$.

  5. 5.

The theoretical bound shows to be even worse with respect to the numerical
error for $J\gg J^{*}$, this can be explained by the decreasing magnitude of
the Fourier coefficients of the test function $\varphi$ inside
$|\widetilde{S}_{J}(t)-S_{J}(t)|$, which we did not take into account in
(20–24).

###  5.3 Additional examples

We compare the numerical computation of $\chi$ for the following three
equilateral graphs $K_{5}$, $K_{5}$ with one edge made pendant, i.e.
disconnected at one end-point, and $K_{3,3}$. These graphs have Euler
characteristic respectively $\chi=-5,-4$ and $-3$, they have all three been
constructed equilateral with each edge of length one. The first two graphs are
chosen to have very close spectra. We can numerically observe that only $1$ in
$5$ of their eigenfrequencies differ significantly (figure 4).

Figure 4: For each graph in figure we plot the functions $t\mapsto S_{J}(t)$
with $d=1$ and $J=30$: $K_{3,3}$ (blue dotted curve), $K_{5}$ with one
endpoint disconnected (red dashed curve) and $K_{5}$ (green solid curve).

###  5.4 Influence of the order of the test function

From Theorem 4.1 we can notice that the values of $d^{*}$ and
$J^{*}-M=\lceil\beta(\overline{\varepsilon},M,\rho,d)-M\rceil$ depend only on
the parameters $\rho$ and $\overline{\varepsilon}$. Following the idea
described in Section 3.2, we fix $\overline{\varepsilon}=1/4$ and, for
increasing values of $\rho$, we compute the values of $d^{*}$ and bounds of
$J^{*}-M$. The results are shown in the following table.

| $\rho$ |  | $d^{*}$ |  | $J^{*}-M$ |
---|---|---|---|---|---|---
$2$ | $\leq\rho\leq$ | $15.6$ | $1$ | $5$ | $\leq J^{*}-M\leq$ | $65$
$15.6$ | $\leq\rho\leq$ | $16.5$ |  $1$ or $2$ | $65$ | $\leq J^{*}-M\leq$ | $70$
$16.5$ | $\leq\rho\leq$ | $421$ | $2$ | $70$ | $\leq J^{*}-M\leq$ | $2912$
$421$ | $\leq\rho\leq$ | $423$ |  $2$ or $3$ | $2912$ | $\leq J^{*}-M\leq$ | $2925$
$423$ | $\leq\rho\leq$ | $10^{4}$ | $3$ | $2925$ | $\leq J^{*}-M\leq$ | $10^{5}$

Cases for which $d^{*}>1$ occur for $\rho>16.5$ i.e.
$\mathcal{L}>8.3\cdot\ell_{\mbox{\tiny min}}$. This depends on two factors:
the distribution of the length of the edges and the number of edges. We can
identify two extreme cases.

  * •

The distribution of the edge length has large variance, i.e. the length of the
shortest edge is very small compared to the total length. For instance, a
Lasso graph with the loop at least $8$ times shorter than the pendant edge.

  * •

The distribution of the edge length has null, or very small variance, but the
number of edges is relatively large, at least $17$ if the graph does not have
loops. For instance, the equilateral $K_{7}$.

##  Appendix A Proof of Proposition 2.6

A priori, we only know that Formula (5) holds for test functions $\varphi$ in
the Schwartz class. In order to extend it to functions in the set
$\mathcal{T}$, we use a standard argument of regularization by convolution.
Let us give more details.

We choose a function $\theta:\mathbb{R}\to\mathbb{R}$ of class $C^{\infty}$,
non-negative, whose support is in $[-1,1]$. We also require that $\theta$ is
even and that $\int_{-\infty}^{+\infty}\theta(\ell)\,d\ell=1$. It follows that
$\hat{\theta}$ is real-valued and even, with $\hat{\theta}(0)=1$ and
$|\hat{\theta}(k)|\leq 1$ for all $k\in\mathbb{R}$. For any positive integer
$n$, we define $\theta_{n}(\ell):=n\theta(n\ell)$. We have
$\hat{\theta}_{n}(k)=\hat{\theta}\left(\frac{k}{n}\right)$ for all
$k\in\mathbb{R}$.

Let us fix $\varphi\in\mathcal{T}$ and a positive integer $n$. The function
$\varphi_{n}:=\theta_{n}*\varphi$ is of class $C^{\infty}$ with support in
$\left[-\frac{1}{n},L+\frac{1}{n}\right]$ and satisfies
$\int_{-\infty}^{+\infty}\varphi_{n}(\ell)\,d\ell=1$. Formula (5) applies and
gives us

$\displaystyle\chi+2\mathcal{L}\varphi_{n}(0)+\sum_{p\in\mathcal{P}}\ell(\mbox{prim}(p))S_{V}(p)\left(\varphi_{n}(-\ell(p))+\varphi_{n}(\ell(p))\right)$
$\displaystyle=2\hat{\varphi}(0)+2\sum_{k_{j}>0}{\hat{\theta}\left(\frac{k_{j}}{n}\right)}\Re\left(\hat{\varphi}(k_{j})\right),$
(34)

where the series in the left-hand side reduces to a finite sum.

For all $\ell\in\mathbb{R}$, $\varphi_{n}(\ell)\to\varphi(\ell)$ as
$n\to\infty$, so the left-hand side of Equation (34) converges to

$\chi+\sum_{p\in\mathcal{P}}\ell(\mbox{prim}(p))S_{V}(p)\left(\varphi(-\ell(p))+\varphi(\ell(p))\right).$

Condition (iv) in the definition of the set $\mathcal{T}$ implies that the
series

$\sum_{k_{j}>0}\Re\left(\hat{\varphi}(k_{j})\right)$

is absolutely convergent. On the other hand,

$\left|\hat{\theta}\left(\frac{k_{j}}{n}\right)\Re\left(\hat{\varphi}(k_{j})\right)\right|\leq\left|\Re\left(\hat{\varphi}(k_{j})\right)\right|,$

while ${\hat{\theta}\left(\frac{k_{j}}{n}\right)}\to\hat{\theta}(0)=1$ as
$n\to\infty$. It follows that

$\sum_{k_{j}>0}\hat{\theta}\left(\frac{k_{j}}{n}\right)\Re\left(\hat{\varphi}(k_{j})\right)\to\sum_{k_{j}>0}\Re\left(\hat{\varphi}(k_{j})\right)$

as $n\to\infty$, using for instance the Dominated Convergence Theorem for the
counting measure associated with the sequence $(k_{j})_{j\geq 1}$. Taking the
limit $n\to\infty$ in Equation (34) therefore yields the desired result.

##  Appendix B Fourier transform of the test functions

Let us recall that we are considering the family of test functions

$\varphi_{d}(\ell)=C_{d}\left(1-\cos(2\pi\ell)\right)^{d}\mathds{1}_{[0,1]}(\ell),$

with $d$ a positive integer. To apply Proposition 2.6, we need to compute the
Fourier transform of $\varphi_{d}$, and also to determine the normalisation
constant $C_{d}$. Let us set, for $k\in\mathbb{R}$,

$I_{d}(k):=\int_{0}^{1}\left(1-\cos(2\pi\ell)\right)^{d}e^{ik\ell}\,d\ell.$

Standard trigonometric identities give us

$I_{d}(k):=2^{d}\int_{0}^{1}\sin(\pi\ell)^{2d}e^{ik\ell}\,d\ell=(-1)^{d}2^{-d}\int_{0}^{1}(e^{i\pi\ell}-e^{-i\pi\ell})^{2d}e^{ik\ell}\,d\ell.$

We can evaluate quickly the integral on the right using complex integration,
and assuming $k>2\pi d$. Let us denote by $\gamma$ the closed path in the
complex plane $\mathbb{C}$ obtained by adding the path $\gamma_{0}$,
consisting of the segment $[-1,1]$ traversed in the positive direction, and
$\gamma_{1}$, the semi-circle centered at $0$ traversed in the anti-clockwise
direction from $1$ to $-1$. Then
$I_{d}(k)=(-1)^{d}2^{-d}/(i\pi)\int_{\gamma_{1}}f(z)\,dz$, with

$f(z)=\frac{1}{z}\left(z-\frac{1}{z}\right)^{2d}z^{k/\pi}=(z^{2}-1)^{2d}z^{k/\pi-2d-1}.$

Since $\int_{\gamma}f(z)\,dz=0$, we obtain

$I_{d}(k)=-(-1)^{d}2^{-d}/(i\pi)\int_{\gamma_{0}}f(z)\,dz.$

We find

$I_{d}(k)=\frac{(-1)^{d+1}}{2^{d}i\pi}\left(\int_{0}^{1}(t^{2}-1)^{2d}t^{k/\pi-2d-1}\,dt-e^{ik}\int_{0}^{1}(t^{2}-1)^{2d}t^{k/\pi-2d-1}\,dt\right),$

the two terms on the right-hand side being the integral on the positive and
negative part of $\gamma_{0}$, respectively. Using the change of variable
$t=\sqrt{s}$, we transform the expression into

$\displaystyle I_{d}(k)$
$\displaystyle=\frac{(-1)^{d+1}}{2^{d+1}i\pi}(1-e^{ik})\int_{0}^{1}(s-1)^{2d}{s}^{k/(2\pi)-d-1}\,{ds}$
$\displaystyle=\frac{(-1)^{d}}{2^{d}\pi}e^{ik/2}\sin(k/2)B(2d+1,k/(2\pi)-d),$

where $B$ denotes the Euler beta function. We have

$B(2d+1,k/(2\pi)-d)=\frac{\Gamma(2d+1)\Gamma(k/(2\pi)-d)}{\Gamma(k/(2\pi)+d+1)}=\frac{(2d)!}{\Pi_{j=-d}^{d}(k/(2\pi)+j)},$

where the last equality results from using, $2d+1$ times, the identity
$\Gamma(x+1)=x\Gamma(x)$. We obtain

$I_{d}(k)=\frac{(-1)^{d}(2d)!}{2^{d}\pi\Pi_{j=-d}^{d}(k/(2\pi)+j)}e^{ik/2}\sin(k/2).$

Both sides of the equation define a function of $k$ which is holomorphic in
$\mathbb{C}$. The equality, which we have proved for $k>2\pi d$, therefore
holds for $k\in\mathbb{C}$ by the principle of isolated zeros. In particular,
we find

$C_{d}^{-1}=I_{d}(0)=\frac{(2d)!}{2^{d}(d!)^{2}},$

and finally

$\hat{\varphi}_{d}(k)=\frac{(-1)^{d}(d!)^{2}}{\pi\Pi_{j=-d}^{d}(k/(2\pi)+j)}e^{ik/2}\sin(k/2).$

## Acknowledgement

The authors are grateful to Pavel Kurasov for suggesting to study the problem,
providing valuable ideas, and allowing them to consult the preprints of [10,
17]. C.L. was partially supported by the Swedish Research Council (Grant
D0497301). The authors wish to thank the two anonymous referees for the
corrections and useful remarks.

## References

  * [1] Linus Pauling.  The diamagnetic anisotropy of aromatic molecules.  The Journal of Chemical Physics, 4(10):673–677, 1936.
  * [2] Klaus Ruedenberg and Charles W. Scherr.  Free‐electron network model for conjugated systems. i. theory.  The Journal of Chemical Physics, 21(9):1565–1581, 1953.
  * [3] Pavel Exner and Hynek Kovařík.  Quantum waveguides.  Theoretical and Mathematical Physics. Springer, Cham, 2015.
  * [4] Tsampikos Kottos and Uzy Smilansky.  Periodic orbit theory and spectral statistics for quantum graphs.  Annals of Physics, 274(1):76 – 124, 1999.
  * [5] Jean-Pierre Roth.  Le spectre du laplacien sur un graphe.  In Gabriel Mokobodzki and Didier Pinchon, editors, Théorie du Potentiel, pages 521–539, Berlin, Heidelberg, 1984. Springer Berlin Heidelberg.
  * [6] Boris Gutkin and Uzy Smilansky.  Can one hear the shape of a graph?  Journal of Physics A: Mathematical and General, 34(31):6061–6068, jul 2001.
  * [7] Pavel Kurasov and Marlena Nowaczyk.  Inverse spectral problem for quantum graphs.  Journal of Physics A: Mathematical and General, 38(22):4901–4915, may 2005.
  * [8] Pavel Kurasov and Marlena Nowaczyk.  Corrigendum: Inverse spectral problem for quantum graphs.  Journal of Physics A: Mathematical and General, 39(4):993–993, jan 2006.
  * [9] Ram Band, Gregory Berkolaiko, Hillel Raz, and Uzy Smilansky.  The number of nodal domains on quantum graphs as a stability index of graph partitions.  Comm. Math. Phys., 311(3):815–838, 2012.
  * [10] Pavel Kurasov.  Spectral theory of quantum graphs.  (In preparation), 2020.
  * [11] Mark Kac.  Can one hear the shape of a drum?  Amer. Math. Monthly, 73(4, part II):1–23, 1966.
  * [12] Gregory Berkolaiko and Peter Kuchment.  Introduction to quantum graphs, volume 186 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, 2013.
  * [13] Ram Band, Talia Shapira, and Uzy Smilansky.  Nodal domains on isospectral quantum graphs: the resolution of isospectrality?  Journal of Physics A: Mathematical and General, 39(45):13999–14014, oct 2006.
  * [14] Ram Band, Ori Parzanchevski, and Gilad Ben-Shach.  The isospectral fruits of representation theory: quantum graphs and drums.  Journal of Physics A: Mathematical and Theoretical, 42(17):175202, apr 2009.
  * [15] Ori Parzanchevski and Ram Band.  Linear representations and isospectrality with boundary conditions.  J. Geom. Anal., 20(2):439–471, 2010.
  * [16] Lior Alon, Ram Band, and Gregory Berkolaiko.  Nodal statistics on quantum graphs.  Comm. Math. Phys., 362(3):909–948, 2018.
  * [17] Michał Ławniczak, Pavel Kurasov, Szymon Bauch, Małgorzata Białous, Vitalii Yunko, and Leszek Sirko.  Hearing euler characteristic of graphs.  Phys. Rev. E, 101:052320, May 2020.
  * [18] Pavel Kurasov.  Schrödinger operators on graphs and geometry. I. Essentially bounded potentials.  J. Funct. Anal., 254(4):934–953, 2008.
  * [19] Jens Bolte and Sebastian Endres.  The trace formula for quantum graphs with general self adjoint boundary conditions.  Ann. Henri Poincaré, 10(1):189–223, 2009.
  * [20] Pavel Kurasov and Marlena Nowaczyk.  Geometric properties of quantum graphs and vertex scattering matrices.  Opuscula Math., 30(3):295–309, 2010.
  * [21] Gregory Berkolaiko.  An elementary introduction to quantum graphs.  In Geometric and computational spectral theory, volume 700 of Contemp. Math., pages 41–72. Amer. Math. Soc., Providence, RI, 2017.
  * [22] Emil Artin.  The gamma function.  Translated by Michael Butler. Athena Series: Selected Topics in Mathematics. Holt, Rinehart and Winston, New York-Toronto-London, 1964.
  * [23] NIST Digital Library of Mathematical Functions.  http://dlmf.nist.gov/, Release 1.0.25 of 2019-12-15.  F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
  * [24] Wolfram Research, Inc.  Mathematica, Version 11.3.  Champaign, IL, 2018.
  * [25] Joachim von Below.  A characteristic equation associated to an eigenvalue problem on $c^{2}$-networks.  Linear Algebra Appl., 71:309–325, 1985.
  * [26] Matthias Hoffman, Andrea Serio, and Francesco Tudisco.  Approximation of eigenfunctions of metric graphs.  (In preparation), 2020.