$\operatorname*{\m@thbbch@rP}_{\bm{d}\sim\mu_{A,\varepsilon}}\mathopen{}\mathclose{{}\left(s(\bm{d};A)\leqslant\tau
n}\right)\geqslant 1-n^{-7}\text{ where
}\tau\mathrel{\mathop{:}}=2\eta+10\log(n)/(\varepsilon n)\,.$

Let $\tilde{d}$ be a scalar such that $s(\tilde{d};A)\leqslant\tau n$. For
$\eta$ and $\log(n)/(\varepsilon n)$ smaller than some constant, we have
$2\eta+\tau\leqslant 0.1$. Then by Lemma 6.10,

$\frac{1}{1+\alpha}\mathopen{}\mathclose{{}\left(d(A^{*})-5(\eta+\tau)(\sigma+\delta)\sqrt{\hat{d}}}\right)\leqslant\tilde{d}\leqslant\frac{1}{1-\alpha}\mathopen{}\mathclose{{}\left(d(A^{*})+5(\eta+\tau)(\sigma+\delta)\sqrt{\hat{d}}}\right)\,.$

Plugging in everything, we have

$\mathopen{}\mathclose{{}\left\lvert\frac{\tilde{d}}{d^{\circ}}-1}\right\rvert\leqslant
O\mathopen{}\mathclose{{}\left(\sqrt{\frac{\log
n}{d^{\circ}n}}+\frac{\log^{2}n}{\sqrt{d^{\circ}}\varepsilon n}+\frac{\eta\log
n}{\sqrt{d^{\circ}}}}\right)\,.$

∎

#### Proof of Theorem 6.1

By Lemma 6.7 and Lemma 6.8.

##  7 Lower bounds

In this section, we prove Theorem 1.5, Theorem 1.7, and Theorem 1.8.

###  7.1 Lower bound for Erdős-Rényi random graphs

In this section, we prove Theorem 1.5.

######  Theorem (Restatement of Theorem 1.5).

Suppose there is an $\varepsilon$-differentially node-private algorithm that,
given an Erdős-Rényi random graph $\m@thbbch@rG(n,p^{\circ})$, outputs an
estimate $\tilde{p}$ satisfying
$\lvert\tilde{p}/p^{\circ}-1\rvert\leqslant\alpha$ with probability $1-\beta$.
Then we must have

$\alpha\geqslant\Omega\mathopen{}\mathclose{{}\left(\frac{\log(1/\beta)}{\varepsilon
n\sqrt{np^{\circ}}}}\right)\,.$

We leave the formal proof of Theorem 1.5 to the end of this section. Now we
sketch the proof idea. One natural idea to prove this theorem is to construct
a coupling $\omega$ of $\m@thbbch@rG(n,p^{\circ})$ and
$\m@thbbch@rG(n,(1-2\alpha)p^{\circ})$ such that for
$(\bm{G},\bm{G}^{\prime})\sim\omega$, the typical distance between $\bm{G}$
and $\bm{G}^{\prime}$ can be well controlled. However, such a coupling is
tricky to construct directly, as the node degrees in an Erdős-Rényi random
graph are not independent. To avoid dealing with such dependence, we instead
consider the directed Erdős-Rényi random graphs, which is inspired by the
proof of [AJK+22, Theorem 1.5]. The directed Erdős-Rényi random graph model,
denoted by $\tilde{\m@thbbch@rG}(n,p^{\circ})$, is a distribution over
$n$-node directed graphs where each edge $(i,j)$ is present with probability
$p^{\circ}$ independently. Since the outdegrees in a directed Erdős-Rényi
random graph are i.i.d. Binomial random variables, it is not so difficult to
construct a coupling of $\tilde{\m@thbbch@rG}(n,p^{\circ})$ and
$\tilde{\m@thbbch@rG}(n,(1-2\alpha)p^{\circ})$. Then we can convert such a
coupling into a coupling of $\m@thbbch@rG(n,p^{\circ})$ and
$\m@thbbch@rG(n,(1-2\alpha)p^{\circ})$.

######  Lemma 7.1 (Coupling).

Let $p^{\circ}\in[0,1]$, $\alpha\in[0,1/2]$, and
$p^{\prime}\mathrel{\mathop{:}}=(1-2\alpha)p^{\circ}$. There exists a coupling
$\omega$ of $\m@thbbch@rG(n,p^{\circ})$ and $\m@thbbch@rG(n,p^{\prime})$ with
the following property. For $(\bm{G},\bm{G}^{\prime})\sim\omega$, the
distribution of $\operatorname{dist}(\bm{G},\bm{G}^{\prime})$ is the binomial
distribution $\mathrm{Bin}(n,\Delta)$ where
$\Delta=\mathrm{TV}(\mathrm{Bin}(n,p^{\circ}),\mathrm{Bin}(n,p^{\prime}))$.
Moreover, if $p^{\circ}\leqslant c$ and $\alpha\leqslant
c^{\prime}/\sqrt{np^{\circ}}$ for some constants $c,c^{\prime}$, then
$\Delta\lesssim\alpha\sqrt{np^{\circ}}$.

###### Proof.

We first show that it suffices to construct a coupling of
$\tilde{\m@thbbch@rG}(n,p^{\circ})$ and $\tilde{\m@thbbch@rG}(n,p^{\prime})$.
For a directed graph $\tilde{G}$, it can be converted into an undirected graph
$U(\tilde{G})$ by letting $\\{i,j\\}\in U(\tilde{G})$ iff $i\leqslant j$ and
$(i,j)\in\tilde{G}$. It is easy to see that333 For a directed graph
$\tilde{G}$, we define its adjacency matrix $\tilde{A}$ to be
$\tilde{A}(i,j)\mathrel{\mathop{:}}=\m@thbbch@rone\\{(i,j)\in\tilde{G}\\}$.
The (node) distance between two $n$-node directed graphs
$\tilde{G},\tilde{G}^{\prime}$, denoted by
$\operatorname{dist}(\tilde{G},\tilde{G}^{\prime})$, is number of nonzero rows
of $\tilde{A}-\tilde{A}^{\prime}$.
$\operatorname{dist}(\tilde{G},\tilde{G}^{\prime})=\operatorname{dist}(U(\tilde{G}),U(\tilde{G}^{\prime}))$.
Also observe that if $\tilde{\bm{G}}\sim\tilde{\m@thbbch@rG}(n,p^{\circ})$
then $U(\tilde{\bm{G}})\sim\m@thbbch@rG(n,p^{\circ})$. Therefore, a coupling
$\tilde{\omega}$ of $\tilde{\m@thbbch@rG}(n,p^{\circ})$ and
$\tilde{\m@thbbch@rG}(n,p^{\prime})$ can be easily converted in to a coupling
$\omega$ of ${\m@thbbch@rG}(n,p^{\circ})$ and ${\m@thbbch@rG}(n,p^{\prime})$
such that, for $(\tilde{\bm{G}},\tilde{\bm{G}}^{\prime})\sim\tilde{\omega}$
and $(\bm{G},{\bm{G}}^{\prime})\sim\omega$, we have

$\operatorname{dist}\mathopen{}\mathclose{{}\left(\tilde{\bm{G}},\tilde{\bm{G}}^{\prime}}\right)\stackrel{{\scriptstyle\mathrm{d}}}{{=}}\operatorname{dist}\mathopen{}\mathclose{{}\left(\bm{G},{\bm{G}}^{\prime}}\right)\,.$

Now we construct a coupling of $\tilde{\m@thbbch@rG}(n,p^{\circ})$ and
$\tilde{\m@thbbch@rG}(n,p^{\prime})$. Instead of sampling each edge
independently, an equivalent way to sample from
$\tilde{}\m@thbbch@rG(n,p^{\circ})$ is as follows. For each $i\in[n]$ :

  * •

Sample an outdegree $\bm{d}\sim\mathrm{Bin}(n,p^{\circ})$.

  * •

Sample a uniformly random subset $\bm{S}\subseteq[n]$ of size $\bm{d}$. For
each $j\in\bm{S}$, add an edge from $i$ to $j$.

Then it is easy to see there exists a coupling $\tilde{\omega}$ of
$\tilde{}\m@thbbch@rG(n,p^{\circ})$ and $\tilde{}\m@thbbch@rG(n,p^{\prime})$
such that if $(\tilde{\bm{G}},\tilde{\bm{G}}^{\prime})\sim\tilde{\omega}$ then
$\operatorname{dist}(\tilde{\bm{G}},\tilde{\bm{G}}^{\prime})\sim\mathrm{Bin}(n,\Delta)$
where

$\Delta=\mathrm{TV}\mathopen{}\mathclose{{}\left(\mathrm{Bin}(n,p^{\circ}),\mathrm{Bin}(n,p^{\prime})}\right)\,.$

We have the following bound on the total variation between binomial
distributions (see e.g. [AJ06, Equation (2.15)]). For $0<p<1$ and $0<x<1-p$,

$\mathrm{TV}\mathopen{}\mathclose{{}\left(\mathrm{Bin}(N,p),\mathrm{Bin}(N,p+x)}\right)\leqslant\frac{\sqrt{e}}{2}\frac{\tau(x)}{(1-\tau(x))^{2}}\,,$

where $\tau(x)\mathrel{\mathop{:}}=x\sqrt{\frac{N+2}{2p(1-p)}}$ , provided
$\tau(x)<1$. Plugging in $N=n$, $p=p^{\circ}$, and $x=2\alpha p^{\circ}$, we
have

$\Delta=\mathrm{TV}\mathopen{}\mathclose{{}\left(\mathrm{Bin}(n,p^{\circ}),\mathrm{Bin}(n,p^{\prime})}\right)\lesssim\alpha\sqrt{np^{\circ}}\,,$

provided $p^{\circ}\leqslant c$ and $\alpha\leqslant
c^{\prime}/\sqrt{np^{\circ}}$ for sufficiently small absolute constants
$c,c^{\prime}$. ∎

###### Proof of Theorem 1.5.

Let $\mathcal{A}$ be an algorithm satisfying the theorem’s assumptions. Let
$p^{\prime}\mathrel{\mathop{:}}=(1-2\alpha)p^{\circ}$. Let $\omega$ be a
coupling of $\m@thbbch@rG(n,p^{\circ})$ and $\m@thbbch@rG(n,p^{\prime})$ as
guaranteed by Lemma 7.1. Then for $(\bm{G},\bm{G}^{\prime})\sim\omega$, we
have $\operatorname{dist}(\bm{G},\bm{G}^{\prime})\sim\mathrm{Bin}(n,\Delta)$
where
$\Delta=\mathrm{TV}(\mathrm{Bin}(n,p^{\circ}),\mathrm{Bin}(n,p^{\prime}))$.

By the utility assumption of algorithm $\mathcal{A}$,

$\operatorname*{\m@thbbch@rP}_{\mathcal{A},\m@thbbch@rG(n,p^{\circ})}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\bm{G})-p^{\circ}}\right\rvert<\alpha
p^{\circ}}\right)\geqslant 1-\beta\,.$

As algorithm $\mathcal{A}$ is $\varepsilon$-DP, we have for any graphs
$G,G^{\prime}$ that,

$\operatorname*{\m@thbbch@rP}_{\mathcal{A}}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(G^{\prime})-p^{\prime}}\right\rvert<\alpha
p^{\circ}}\right)\leqslant
e^{\varepsilon\cdot\operatorname{dist}(G,G^{\prime})}\cdot\operatorname*{\m@thbbch@rP}_{\mathcal{A}}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(G)-p^{\prime}}\right\rvert<\alpha
p^{\circ}}\right)\,.$

Taking expectation w.r.t. the coupling $\omega$ on both sides gives

$\displaystyle\operatorname*{\m@thbbch@rE}_{\omega}\operatorname*{\m@thbbch@rE}_{\mathcal{A}}\m@thbbch@rone\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\bm{G}^{\prime})-p^{\prime}}\right\rvert<\alpha
p^{\circ}}\right\\}$
$\displaystyle\leqslant\operatorname*{\m@thbbch@rE}_{\omega}e^{\varepsilon\cdot\operatorname{dist}(\bm{G},\bm{G}^{\prime})}\cdot\operatorname*{\m@thbbch@rE}_{\mathcal{A}}\m@thbbch@rone\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\bm{G})-p^{\prime}}\right\rvert<\alpha
p^{\circ}}\right\\}\,,$
$\displaystyle\operatorname*{\m@thbbch@rP}_{\mathcal{A},\tilde{}\m@thbbch@rG(n,p^{\prime})}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\bm{G}^{\prime})-p^{\prime}}\right\rvert<\alpha
p^{\circ}}\right)$
$\displaystyle\leqslant\operatorname*{\m@thbbch@rE}_{\omega,\mathcal{A}}e^{\varepsilon\cdot\operatorname{dist}(\bm{G},\bm{G}^{\prime})}\cdot\m@thbbch@rone\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\bm{G})-p^{\prime}}\right\rvert<\alpha
p^{\circ}}\right\\}\,.$ (7.1)

By the utility assumption of algorithm $\mathcal{A}$ and
$p^{\prime}<p^{\circ}$, the left-hand side of Eq. 7.1 is at least $1-\beta$.
Using the Cauchy-Schwartz inequality, the right-hand side of Eq. 7.1 can be
upper bounded as follows,

$\displaystyle\operatorname*{\m@thbbch@rE}_{\omega,\mathcal{A}}e^{\varepsilon\cdot\operatorname{dist}(\bm{G},\bm{G}^{\prime})}\cdot\m@thbbch@rone\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\bm{G})-p^{\prime}}\right\rvert<\alpha
p^{\circ}}\right\\}$
$\displaystyle\leqslant\sqrt{\operatorname*{\m@thbbch@rE}_{\omega,\mathcal{A}}e^{2\varepsilon\cdot\operatorname{dist}(\bm{G},\bm{G}^{\prime})}}\sqrt{\operatorname*{\m@thbbch@rE}_{\omega,\mathcal{A}}\m@thbbch@rone\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\bm{G})-p^{\prime}}\right\rvert<\alpha
p^{\circ}}\right\\}}$
$\displaystyle\leqslant\sqrt{\operatorname*{\m@thbbch@rE}_{\mathrm{Bin}(n,\Delta)}e^{2\varepsilon\cdot\bm{X}}}\sqrt{\operatorname*{\m@thbbch@rP}_{\mathcal{A},\tilde{}\m@thbbch@rG(n,p^{\circ})}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\bm{G})-p^{\prime}}\right\rvert<\alpha
p^{\circ}}\right)}\,.$

By squaring both sides of Eq. 7.1 and plugging in the above two bounds, we
have

$(1-\beta)^{2}\leqslant\operatorname*{\m@thbbch@rE}_{\mathrm{Bin}(n,\Delta)}\mathopen{}\mathclose{{}\left[e^{2\varepsilon\cdot\bm{X}}}\right]\cdot\operatorname*{\m@thbbch@rP}_{\mathcal{A},\tilde{}\m@thbbch@rG(n,p^{\circ})}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\bm{G})-p^{\prime}}\right\rvert<\alpha
p^{\circ}}\right)\,.$

Using the formula for the moment generating function of binomial
distributions, we have

$\operatorname*{\m@thbbch@rE}_{\mathrm{Bin}(n,\Delta)}\mathopen{}\mathclose{{}\left[e^{2\varepsilon\cdot\bm{X}}}\right]=\mathopen{}\mathclose{{}\left(1+\Delta(e^{2\varepsilon}-1)}\right)^{n}\leqslant
e^{n\Delta(e^{2\varepsilon}-1)}\,.$

Then

$\operatorname*{\m@thbbch@rP}_{\mathcal{A},\m@thbbch@rG(n,p^{\circ})}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\bm{G})-p^{\prime}}\right\rvert<\alpha
p^{\circ}}\right)\geqslant(1-\beta)^{2}\cdot
e^{-n\Delta(e^{2\varepsilon}-1)}\,.$

Since $p^{\prime}-p^{\circ}=2\alpha p^{\circ}$, the two events
$\\{\hat{p}:\lvert\hat{p}-p^{\circ}\rvert<\alpha p^{\circ}\\}$ and
$\\{\hat{p}:\lvert\hat{p}-p^{\prime}\rvert<\alpha p^{\circ}\\}$ are disjoint.
Thus,

$\operatorname*{\m@thbbch@rP}_{\mathcal{A},\m@thbbch@rG(n,p^{\circ})}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\bm{G})-p^{\prime}}\right\rvert<\alpha
p^{\circ}}\right)\leqslant
1-\operatorname*{\m@thbbch@rP}_{\mathcal{A},\m@thbbch@rG(n,p^{\circ})}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\bm{G})-p^{\circ}}\right\rvert<\alpha
p^{\circ}}\right)\leqslant\beta\,.$

Therefore, we have the following lower bound

$\Delta\geqslant\frac{2\log(1-\beta)+\log(1/\beta)}{n(e^{2\varepsilon}-1)}\,,$

which is $\Delta\gtrsim\frac{\log(1/\beta)}{n\varepsilon}$ for samll enough
$\varepsilon$ and $\beta$.

By Lemma 7.1, if $p^{\circ}\leqslant c$ and $\alpha\leqslant
c^{\prime}/\sqrt{np^{\circ}}$ for some constants $c,c^{\prime}$, then
$\Delta\lesssim\alpha\sqrt{np^{\circ}}$. Combined with the lower bound
$\Delta\gtrsim\frac{\log(1/\beta)}{n\varepsilon}$, we have

$\alpha\gtrsim\frac{\log(1/\beta)}{n\varepsilon\sqrt{np^{\circ}}}\,.$

∎

###  7.2 Lower bound for inhomogeneous random graphs

In this section, we prove Theorem 1.7 and Theorem 1.8.

We first show the lower bound for the error rate of robust estimation.

######  Theorem (Restatement of Theorem 1.7).

Suppose there is an algorithm satisfies the following guarantee for any
symmetric matrix $Q^{\circ}\in[0,1]^{n\times n}$. Given an $\eta$-corrupted
inhomogeneous random graph $\m@thbbch@rG(n,Q^{\circ})$, the algorithm outputs
an estimate $\hat{p}$ satisfying
$\lvert\hat{p}/p^{\circ}-1\rvert\leqslant\alpha$ with probability at least
$0.99$, where $p^{\circ}=\sumop\slimits@_{i,j}Q^{\circ}_{ij}/(n^{2}-n)$. Then
we must have $\alpha\geqslant\Omega(R\eta)$, where
$R=\max_{i,j}Q^{\circ}_{ij}/p^{\circ}$.

###### Proof.

Let $p^{\circ}\in[0,1]$, and let $Q^{\circ}\in[0,1]^{n\times n}$ be the
matrix, in which all entries are $p^{\circ}$, except for the rows and columns
corresponding to a set of $\eta n$ nodes setting to be $Rp^{\circ}$. Let $Q$
be the matrix, in which all entries are $p^{\circ}$, except for the rows and
columns corresponding to a set of $\eta n$ nodes setting to be $0$.

We construct the following pair of distributions $\mathcal{D}_{0}$ and
$\mathcal{D}_{1}$:

  * •

$\mathcal{D}_{0}$: The distribution of $\bm{G}\sim\m@thbbch@rG(Q^{\circ})$.

  * •

$\mathcal{D}_{1}$: The distribution of $\bm{G}\sim\m@thbbch@rG(Q)$.

Then we have $\frac{1}{n^{2}}\mathopen{}\mathclose{{}\left\lvert\lVert
Q^{\circ}\rVert_{1}-\lVert Q\rVert_{1}}\right\rvert\geqslant\Omega(R\eta
n^{2}p^{\circ})$.

On the other hand, there is a coupling between
$\tilde{G}\sim\m@thbbch@rG(Q^{\circ})$ and
$\tilde{G^{\prime}}\sim\m@thbbch@rG(Q)$ such that
$\text{dist}(\tilde{G},\tilde{G^{\prime}})\leqslant\eta n$. Therefore, the two
distributions are indistinguishable under the $\eta$-corruption model. Since
the edge density of $\m@thbbch@rG(Q^{\circ})$ differs from $\m@thbbch@rG(Q)$
by $\Omega(R\eta p^{\circ})$, no algorithm can achieve error rate $o(R\eta
p^{\circ})$ with probability $1-o(1)$ for both distributions under the
corruption of $\eta$-fraction of the nodes. ∎

######  Theorem (Restatement of Theorem 1.8).

Suppose there is an $\varepsilon$-differentially node-private algorithm
satisfies the following guarantee for any symmetric matrix
$Q^{\circ}\in[0,1]^{n\times n}$. Given an inhomogeneous random graph
$\m@thbbch@rG(n,Q^{\circ})$, the algorithm outputs an estimate $\hat{p}$
satisfying $\lvert\hat{p}/p^{\circ}-1\rvert\leqslant\alpha$ with probability
$1-\beta$, where $p^{\circ}=\sumop\slimits@_{i,j}Q^{\circ}_{ij}/(n^{2}-n)$.
Then we must have

$\alpha\geqslant\Omega\mathopen{}\mathclose{{}\left(\frac{R\log(1/\beta)}{n\varepsilon}}\right)\,,$

where $R=\max_{i,j}Q^{\circ}_{ij}/p^{\circ}$.

###### Proof of Theorem 1.8.

We will prove the lower bound by constructing a pair of distributions
$\mathcal{D}_{0}$ and $\mathcal{D}_{1}$ such that the total variation distance
between them is small, but the difference in edge density is significant. Then
since $\varepsilon$-differentially node-private algorithm needs to have
similar distributions in the output, it could not succeed in accurately
estimating the edge density accurately under both distributions.

Let $\eta\in[0,0.001)$. Let $p^{\circ}\in[0,1]$, and let
$Q^{\circ}\in[0,1]^{n\times n}$ be the matrix, in which all entries are
$p^{\circ}$, except for the rows and columns corresponding to a set of $\eta
n$ nodes setting to be $0$. Let $Q$ be the matrix, in which all entries are
$p^{\circ}$, except for the rows and columns corresponding to a set of $\eta
n$ nodes setting to be $Rp^{\circ}$.

We construct the following pair of distributions $\mathcal{D}_{0}$ and
$\mathcal{D}_{1}$:

  * •

$\mathcal{D}_{0}$: The distribution of $\bm{G}\sim\m@thbbch@rG(Q^{\circ})$.

  * •

$\mathcal{D}_{1}$: The distribution of $\bm{G}\sim\m@thbbch@rG(Q)$.

Let $p^{\prime}=\frac{\lVert Q^{\circ}\rVert_{1}}{n^{2}}$ and $p=\frac{\lVert
Q\rVert_{1}}{n^{2}}$. We have $\mathopen{}\mathclose{{}\left\lvert
p-p^{\prime}}\right\rvert\geqslant R\eta p^{\circ}$.

On the other hand, there is a coupling between $\tilde{G}\sim\m@thbbch@rG(Q)$
and $\tilde{G^{\prime}}\sim\m@thbbch@rG(Q^{\circ})$ such that
$\text{dist}(\tilde{G},\tilde{G^{\prime}})\leqslant\eta n$. Taking expectation
w.r.t. the coupling $\omega$ on both sides gives

$\displaystyle\operatorname*{\m@thbbch@rE}_{\omega}\operatorname*{\m@thbbch@rE}_{\mathcal{A}}\m@thbbch@rone\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\tilde{\bm{G}}^{\prime})-p}\right\rvert<\frac{R\eta}{2}p^{\circ}}\right\\}$
$\displaystyle\leqslant\operatorname*{\m@thbbch@rE}_{\omega}e^{\varepsilon\cdot\operatorname{dist}(\tilde{\bm{G}},\tilde{\bm{G}}^{\prime})}\cdot\operatorname*{\m@thbbch@rE}_{\mathcal{A}}\m@thbbch@rone\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\tilde{\bm{G}})-p}\right\rvert<\frac{R\eta}{2}p^{\circ}}\right\\}\,,$
$\displaystyle\operatorname*{\m@thbbch@rP}_{\mathcal{A},\tilde{}\m@thbbch@rG(Q^{\circ})}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\tilde{\bm{G}}^{\prime})-p}\right\rvert<\frac{R\eta}{2}p^{\circ}}\right)$
$\displaystyle\leqslant\operatorname*{\m@thbbch@rE}_{\omega,\mathcal{A}}e^{\varepsilon\cdot\operatorname{dist}(\tilde{\bm{G}},\tilde{\bm{G}}^{\prime})}\cdot\m@thbbch@rone\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\tilde{\bm{G}})-p}\right\rvert<\frac{R\eta}{2}p^{\circ}}\right\\}\,.$

By the utility assumption of algorithm $\mathcal{A}$ and $p<p^{\circ}$, the
left-hand side is at least $1-\beta$. Using the Cauchy-Schwartz inequality,
the right-hand side can be upper bounded as follows,

$\displaystyle\operatorname*{\m@thbbch@rE}_{\omega,\mathcal{A}}e^{\varepsilon\cdot\operatorname{dist}(\tilde{\bm{G}},\tilde{\bm{G}}^{\prime})}\cdot\m@thbbch@rone\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\tilde{\bm{G}})-p}\right\rvert<\frac{R\eta}{2}p^{\circ}}\right\\}$
$\displaystyle\leqslant\sqrt{\operatorname*{\m@thbbch@rE}_{\omega,\mathcal{A}}e^{2\varepsilon\cdot\operatorname{dist}(\tilde{\bm{G}},\tilde{\bm{G}}^{\prime})}}\sqrt{\operatorname*{\m@thbbch@rE}_{\omega,\mathcal{A}}\m@thbbch@rone\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\tilde{\bm{G}})-p}\right\rvert<\frac{R\eta}{2}p^{\circ}}\right\\}}$
$\displaystyle\leqslant\exp(\varepsilon\eta
n)\sqrt{\operatorname*{\m@thbbch@rP}_{\mathcal{A},\tilde{}\m@thbbch@rG(Q)}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\tilde{\bm{G}})-p}\right\rvert<\frac{R\eta}{2}p^{\circ}}\right)}\,.$

Thus

$(1-\beta)^{2}\leqslant\exp(\varepsilon\eta
n)\cdot\operatorname*{\m@thbbch@rP}_{\mathcal{A},\tilde{}\m@thbbch@rG(Q)}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\tilde{\bm{G}})-p}\right\rvert<\frac{R\eta}{2}p^{\circ}}\right)\,.$

Then

$\operatorname*{\m@thbbch@rP}_{\mathcal{A},\tilde{}\m@thbbch@rG(Q)}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\tilde{\bm{G}})-p}\right\rvert<\frac{R\eta}{2}p^{\circ}}\right)\geqslant(1-\beta)^{2}\cdot\exp(-\varepsilon\eta
n)\,.$

Since $\lvert p-p^{\circ}\rvert\geqslant R\eta p^{\circ}$, the two events
$\\{\hat{p}:\lvert\hat{p}-p^{\circ}\rvert<\frac{R\eta}{2}p^{\circ}\\}$ and
$\\{\hat{p}:\lvert\hat{p}-p\rvert<\frac{R\eta}{2}p^{\circ}\\}$ are disjoint,
which implies

$\operatorname*{\m@thbbch@rP}_{\mathcal{A},\tilde{}\m@thbbch@rG(Q)}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\tilde{\bm{G}})-p}\right\rvert<\frac{R\eta}{2}p^{\circ}}\right)\leqslant
1-\operatorname*{\m@thbbch@rP}_{\mathcal{A},\tilde{}\m@thbbch@rG(Q)}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\mathcal{A}(\tilde{\bm{G}})-p^{\circ}}\right\rvert<\frac{R\eta}{2}p^{\circ}}\right)\leqslant\beta\,.$

Therefore, we have $\beta\geqslant(1-\beta)^{2}\exp(-\varepsilon\eta n)$. As
result, we need to have
$\eta\geqslant\Omega\mathopen{}\mathclose{{}\left(\frac{\log(\beta)}{\varepsilon
n}}\right)$. Thus we have

$\lvert
p-p^{\prime}\rvert\geqslant\Omega\mathopen{}\mathclose{{}\left(\frac{R\log(\beta)p^{\circ}}{\varepsilon
n}}\right)\,.$

Since $p^{\circ}\geqslant p^{\prime}$, it follows that

$\lvert
p-p^{\prime}\rvert\geqslant\Omega\mathopen{}\mathclose{{}\left(\frac{R\log(\beta)p^{\prime}}{\varepsilon
n}}\right)\,,$

which finishes the proof. ∎

## References

  * [AJ06] José A Adell and Pedro Jodrá, _Exact kolmogorov and total variation distances between some familiar discrete distributions_ , Journal of Inequalities and Applications 2006 (2006), 1–8.
  * [AJK+22] Jayadev Acharya, Ayush Jain, Gautam Kamath, Ananda Theertha Suresh, and Huanyu Zhang, _Robust estimation for random graphs_ , Conference on Learning Theory, PMLR, 2022, pp. 130–166.
  * [AKT+23] Daniel Alabi, Pravesh K Kothari, Pranay Tankala, Prayaag Venkat, and Fred Zhang, _Privately estimating a gaussian: Efficient, robust, and optimal_ , Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023, pp. 483–496.
  * [AUZ23] Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou, _From robustness to privacy and back_ , International Conference on Machine Learning, PMLR, 2023, pp. 1121–1146.
  * [BBDS13] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet, _Differentially private data analysis of social networks via restricted sensitivity_ , Proceedings of the 4th conference on Innovations in Theoretical Computer Science, 2013, pp. 87–96.
  * [BC17] Christian Borgs and Jennifer Chayes, _Graphons: A nonparametric method to model, estimate, and design algorithms for massive networks_ , Proceedings of the 2017 ACM Conference on Economics and Computation, 2017, pp. 665–672.
  * [BCS15] Christian Borgs, Jennifer T. Chayes, and Adam Smith, _Private graphon estimation for sparse graphs_ , 2015.
  * [BCSZ18] Christian Borgs, Jennifer Chayes, Adam Smith, and Ilias Zadik, _Revealing network structure, confidentially: Improved rates for node-private graphon estimation_ , 2018.
  * [BJR07] Béla Bollobás, Svante Janson, and Oliver Riordan, _The phase transition in inhomogeneous random graphs_ , Random Structures & Algorithms 31 (2007), no. 1, 3–122.
  * [BS14] Boaz Barak and David Steurer, _Sum-of-squares proofs and the quest toward optimal algorithms_ , Proceedings of the International Congress of Mathematicians—Seoul 2014. Vol. IV, Kyung Moon Sa, Seoul, 2014, pp. 509–533. MR 3727623
  * [BS16] , _Proofs, beliefs, and algorithms through the lens of sum-of-squares_ , lecture notes, 2016.
  * [BvH16] Afonso S. Bandeira and Ramon van Handel, _Sharp nonasymptotic bounds on the norm of random matrices with independent entries_ , Ann. Probab. 44 (2016), no. 4, 2479–2506. MR 3531673
  * [CCAd+23] Hongjie Chen, Vincent Cohen-Addad, Tommaso d’Orsi, Alessandro Epasto, Jacob Imola, David Steurer, and Stefan Tiegel, _Private estimation algorithms for stochastic block models and mixture models_ , Advances in Neural Information Processing Systems 36 (2023), 68134–68183.
  * [CDd+24] Hongjie Chen, Jingqiu Ding, Tommaso d’Orsi, Yiding Hua, Chih-Hung Liu, and David Steurer, _Private graphon estimation via sum-of-squares_ , arXiv preprint arXiv:2403.12213 (2024).
  * [DL09] Cynthia Dwork and Jing Lei, _Differential privacy and robust statistics_ , Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, pp. 371–380.
  * [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith, _Calibrating noise to sensitivity in private data analysis_ , Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006\. Proceedings 3, Springer, 2006, pp. 265–284.
  * [DR14] Cynthia Dwork and Aaron Roth, _The algorithmic foundations of differential privacy_ , Foundations and Trends® in Theoretical Computer Science 9 (2014), no. 3–4, 211–407.
  * [DSSU17] Cynthia Dwork, Adam Smith, Thomas Steinke, and Jonathan Ullman, _Exposed! a survey of attacks on private data_ , Annual Review of Statistics and Its Application 4 (2017), 61–84.
  * [FKP+19] Noah Fleming, Pravesh Kothari, Toniann Pitassi, et al., _Semialgebraic proofs and efficient algorithm design_ , Foundations and Trends® in Theoretical Computer Science 14 (2019), no. 1-2, 1–221.
  * [GH22] Kristian Georgiev and Samuel Hopkins, _Privacy induces robustness: Information-computation gaps and sparse mean estimation_ , Advances in Neural Information Processing Systems (S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, eds.), vol. 35, Curran Associates, Inc., 2022, pp. 6829–6842.
  * [HKM22] Samuel B Hopkins, Gautam Kamath, and Mahbod Majid, _Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism_ , Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pp. 1406–1417.
  * [HKMN23] Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan, _Robustness implies privacy in statistical estimation_ , Proceedings of the 55th Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC 2023, Association for Computing Machinery, 2023, p. 497–506.
  * [HL18] Samuel B. Hopkins and Jerry Li, _Mixture models, robustness, and sum of squares proofs_ , Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (New York, NY, USA), STOC 2018, Association for Computing Machinery, 2018, p. 1021–1034.
  * [HLL83] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt, _Stochastic blockmodels: First steps_ , Social networks 5 (1983), no. 2, 109–137.
  * [Hop20] Samuel B Hopkins, _Mean estimation with sub-gaussian rates in polynomial time_ , The Annals of Statistics 48 (2020), no. 2, 1193–1213.
  * [HRH02] Peter D Hoff, Adrian E Raftery, and Mark S Handcock, _Latent space approaches to social network analysis_ , Journal of the american Statistical association 97 (2002), no. 460, 1090–1098.
  * [KMV22] Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker, _Private robust estimation by stabilizing convex relaxations_ , Proceedings of Thirty Fifth Conference on Learning Theory (Po-Ling Loh and Maxim Raginsky, eds.), Proceedings of Machine Learning Research, vol. 178, PMLR, 02–05 Jul 2022, pp. 723–777.
  * [KNRS13] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith, _Analyzing graphs with node differential privacy_ , Theory of Cryptography: 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, Springer, 2013, pp. 457–476.
  * [KRSY11] Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev, _Private analysis of graph structure_ , Proceedings of the VLDB Endowment 4 (2011), no. 11, 1146–1157.
  * [KSS18] Pravesh K Kothari, Jacob Steinhardt, and David Steurer, _Robust moment estimation and improved clustering via sum of squares_ , Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 1035–1046.
  * [LKKO21] Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh, _Robust and differentially private mean estimation_ , Advances in neural information processing systems 34 (2021), 3887–3901.
  * [LKO22] Xiyang Liu, Weihao Kong, and Sewoong Oh, _Differential privacy and robust statistics in high dimensions_ , Conference on Learning Theory, PMLR, 2022, pp. 1167–1246.
  * [MT07] Frank McSherry and Kunal Talwar, _Mechanism design via differential privacy_ , 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), IEEE, 2007, pp. 94–103.
  * [NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith, _Smooth sensitivity and sampling in private data analysis_ , Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, pp. 75–84.
  * [NS09] Arvind Narayanan and Vitaly Shmatikov, _De-anonymizing social networks_ , 2009 30th IEEE symposium on security and privacy, IEEE, 2009, pp. 173–187.
  * [PS17] Aaron Potechin and David Steurer, _Exact tensor completion with sum-of-squares_ , Proceedings of the 2017 Conference on Learning Theory, 2017.
  * [RSS18] Prasad Raghavendra, Tselil Schramm, and David Steurer, _High dimensional estimation via sum-of-squares proofs_ , Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, World Scientific, 2018, pp. 3389–3423.
  * [SU19] Adam Sealfon and Jonathan Ullman, _Efficiently estimating erdos-renyi graphs with node differential privacy_ , Advances in Neural Information Processing Systems 32 (2019).

##  Appendix A Sum-of-squares background

###  A.1 Sum-of-squares hierarchy

In this paper, we use the sum-of-squares semidefinite programming hierarchy
[BS14, BS16, RSS18] for both algorithm design and analysis. The sum-of-squares
proof-to-algorithm framework has been proven useful in many optimal or state-
of-the-art results in algorithmic statistics [HL18, KSS18, PS17, Hop20]. We
provide here a brief introduction to pseudo-distributions, sum-of-squares
proofs, and sum-of-squares algorithms.

#### Pseudo-distribution

We can represent a finitely supported probability distribution over n by its
probability mass function $\mu\colon{}^{n}\to\m@thbbch@rR$ such that
$\mu\geqslant 0$ and $\sumop\slimits@_{x\in\operatorname{supp}(\mu)}\mu(x)=1$.
We define pseudo-distributions as generalizations of such probability mass
distributions by relaxing the constraint $\mu\geqslant 0$ to only require that
$\mu$ passes certain low-degree non-negativity tests.

######  Definition A.1 (Pseudo-distribution).

A _level- $\ell$ pseudo-distribution_ $\mu$ over n is a finitely supported
function $\mu:{}^{n}\rightarrow\m@thbbch@rR$ such that
$\sumop\slimits@_{x\in\operatorname{supp}(\mu)}\mu(x)=1$ and
$\sumop\slimits@_{x\in\operatorname{supp}(\mu)}\mu(x)f(x)^{2}\geqslant 0$ for
every polynomial $f$ of degree at most $\ell/2$.

We can define the expectation of a pseudo-distribution in the same way as the
expectation of a finitely supported probability distribution.

######  Definition A.2 (Pseudo-expectation).

Given a pseudo-distribution $\mu$ over n, we define the _pseudo-expectation_
of a function $f:{}^{n}\to\m@thbbch@rR$ by

$\mathop{\tilde{\m@thbbch@rE}}_{\mu}f\mathrel{\mathop{:}}=\sumop\slimits@_{x\in\operatorname{supp}(\mu)}\mu(x)f(x)\,.$
(A.1)

The following definition formalizes what it means for a pseudo-distribution to
satisfy a system of polynomial constraints.

######  Definition A.3 (Constrained pseudo-distributions).

Let $\mu:{}^{n}\to\m@thbbch@rR$ be a level-$\ell$ pseudo-distribution over n.
Let $\mathcal{A}=\\{f_{1}\geqslant 0,\ldots,f_{m}\geqslant 0\\}$ be a system
of polynomial constraints. We say that _$\mu$ satisfies $\mathcal{A}$_ at
level $r$, denoted by
$\mu\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-1.23135pt]{7.3525pt}{0.47787pt}\rule[0.75348pt]{7.3525pt}{0.47787pt}\raisebox{-5.96742pt}{\makebox[7.3525pt]{\leavevmode\hbox{\set@color$\scriptstyle{r}$}}}\raisebox{2.95354pt}{\makebox[7.3525pt]{\leavevmode\hbox{\set@color$\scriptstyle{}$}}}$}}}\mathcal{A}$,
if for every multiset $S\subseteq[m]$ and every sum-of-squares polynomial $h$
such that $\deg(h)+\sumop\slimits@_{i\in
S}\max\\{\deg(f_{i}),r\\}\leqslant\ell$,

$\mathop{\tilde{\m@thbbch@rE}}_{\mu}h\cdot\prodop\slimits@_{i\in
S}f_{i}\geqslant 0\,.$ (A.2)

We say $\mu$ satisfies $\mathcal{A}$ and write
$\mu\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-1.23135pt]{8.00003pt}{0.47787pt}\rule[0.75348pt]{8.00003pt}{0.47787pt}\raisebox{-2.95354pt}{\makebox[8.00003pt]{\leavevmode\hbox{\set@color$\scriptstyle{}$}}}\raisebox{2.95354pt}{\makebox[8.00003pt]{\leavevmode\hbox{\set@color$\scriptstyle{}$}}}$}}}\mathcal{A}$
(without further specifying the degree) if
$\mu\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-1.23135pt]{7.49994pt}{0.47787pt}\rule[0.75348pt]{7.49994pt}{0.47787pt}\raisebox{-7.46465pt}{\makebox[7.49994pt]{\leavevmode\hbox{\set@color$\scriptstyle{0}$}}}\raisebox{2.95354pt}{\makebox[7.49994pt]{\leavevmode\hbox{\set@color$\scriptstyle{}$}}}$}}}\mathcal{A}$.

We remark that if $\mu$ is an actual finitely supported probability
distribution, then we have
$\mu\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-1.23135pt]{8.00003pt}{0.47787pt}\rule[0.75348pt]{8.00003pt}{0.47787pt}\raisebox{-2.95354pt}{\makebox[8.00003pt]{\leavevmode\hbox{\set@color$\scriptstyle{}$}}}\raisebox{2.95354pt}{\makebox[8.00003pt]{\leavevmode\hbox{\set@color$\scriptstyle{}$}}}$}}}\mathcal{A}$
if and only if $\mu$ is supported on solutions to $\mathcal{A}$.

#### Sum-of-squares proof

We introduce sum-of-squares proofs as the dual objects of pseudo-
distributions, which can be used to reason about properties of pseudo-
distributions. We say a polynomial $p$ is a sum-of-squares polynomial if there
exist polynomials $(q_{i})$ such that $p=\sumop\slimits@_{i}q_{i}^{2}$.

######  Definition A.4 (Sum-of-squares proof).

A _sum-of-squares proof_ that a system of polynomial constraints
$\mathcal{A}=\\{f_{1}\geqslant 0,\ldots,f_{m}\geqslant 0\\}$ implies
$q\geqslant 0$ consists of sum-of-squares polynomials
$(p_{S})_{S\subseteq[m]}$ such that444Here we follow the convention that
$\prodop\slimits@_{i\in S}f_{i}=1$ for $S=\emptyset$.

$q=\sumop\slimits@_{\text{multiset
}S\subseteq[m]}p_{S}\cdot\prodop\slimits@_{i\in S}f_{i}\,.$

If such a proof exists, we say that $\mathcal{A}$ _(sos-)proves_ $q\geqslant
0$ within degree $\ell$, denoted by
$\mathcal{A}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{6.91663pt}{0.47787pt}\raisebox{-6.82222pt}{\makebox[6.91663pt]{\leavevmode\hbox{\set@color$\scriptstyle{\ell}$}}}\raisebox{1.96112pt}{\makebox[6.91663pt]{\leavevmode\hbox{\set@color$\scriptstyle{}$}}}$}}}q\geqslant
0$. In order to clarify the variables quantified by the proof, we often write
$\mathcal{A}(x)\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.00063pt}{0.47787pt}\raisebox{-6.82222pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{\ell}$}}}\raisebox{1.96112pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{x}$}}}$}}}q(x)\geqslant
0$. We say that the system $\mathcal{A}$ _sos-refuted_ within degree $\ell$ if
$\mathcal{A}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{6.91663pt}{0.47787pt}\raisebox{-6.82222pt}{\makebox[6.91663pt]{\leavevmode\hbox{\set@color$\scriptstyle{\ell}$}}}\raisebox{1.96112pt}{\makebox[6.91663pt]{\leavevmode\hbox{\set@color$\scriptstyle{}$}}}$}}}-1\geqslant
0$. Otherwise, we say that the system is _sos-consistent_ up to degree $\ell$,
which also means that there exists a level-$\ell$ pseudo-distribution
satisfying the system.

The following lemma shows that sum-of-squares proofs allow us to deduce
properties of pseudo-distributions that satisfy some constraints.

######  Lemma A.5.

Let $\mu$ be a pseudo-distribution, and let $\mathcal{A},\mathcal{B}$ be
systems of polynomial constraints. Suppose there exists a sum-of-squares proof
$\mathcal{A}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.45248pt}{0.47787pt}\raisebox{-6.08612pt}{\makebox[8.45248pt]{\leavevmode\hbox{\set@color$\scriptstyle{r^{\prime}}$}}}\raisebox{1.96112pt}{\makebox[8.45248pt]{\leavevmode\hbox{\set@color$\scriptstyle{}$}}}$}}}\mathcal{B}$.
If
$\mu\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-1.23135pt]{7.3525pt}{0.47787pt}\rule[0.75348pt]{7.3525pt}{0.47787pt}\raisebox{-5.96742pt}{\makebox[7.3525pt]{\leavevmode\hbox{\set@color$\scriptstyle{r}$}}}\raisebox{2.95354pt}{\makebox[7.3525pt]{\leavevmode\hbox{\set@color$\scriptstyle{}$}}}$}}}\mathcal{A}$,
then
$\mu\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-1.23135pt]{23.64648pt}{0.47787pt}\rule[0.75348pt]{23.64648pt}{0.47787pt}\raisebox{-7.07854pt}{\makebox[23.64648pt]{\leavevmode\hbox{\set@color$\scriptstyle{r\cdot
r^{\prime}+r^{\prime}}$}}}\raisebox{2.95354pt}{\makebox[23.64648pt]{\leavevmode\hbox{\set@color$\scriptstyle{}$}}}$}}}\mathcal{B}$.

#### Sum-of-squares algorithm

Given a system of polynomial constraints, the _sum-of-squares algorithm_
searches through the space of pseudo-distributions that satisfy this
polynomial system by semidefinite programming.

Since semidefinite programing can only be solved approximately, we can only
find pseudo-distributions that approximately satisfy a given polynomial
system. We say that a level-$\ell$ pseudo-distribution _approximately
satisfies_ a polynomial system, if the inequalities in Eq. A.2 are satisfied
up to an additive error of $2^{-n^{\ell}}\cdot\lVert
h\rVert\cdot\prodop\slimits@_{i\in S}\lVert f_{i}\rVert$, where
$\lVert\cdot\rVert$ denotes the Euclidean norm555The choice of norm is not
important here because the factor $2^{-n^{\ell}}$ swamps the effects of
choosing another norm. of the coefficients of a polynomial in the monomial
basis.

######  Theorem A.6 (Sum-of-squares algorithm).

There exists an $(n+m)^{O(\ell)}$-time algorithm that, given any explicitly
bounded666A system of polynomial constraints is _explicitly bounded_ if it
contains a constraint of the form $\|x\|^{2}\leqslant M$. and satisfiable
system777Here we assume that the bit complexity of the constraints in
$\mathcal{A}$ is $(n+m)^{O(1)}$. $\mathcal{A}$ of $m$ polynomial constraints
in $n$ variables, outputs a level-$\ell$ pseudo-distribution that satisfies
$\mathcal{A}$ approximately.

######  Remark A.7 (Approximation error and bit complexity).

For a pseudo-distribution that only approximately satisfies a polynomial
system, we can still use sum-of-squares proofs to reason about it in the same
way as Lemma A.5. In order for approximation errors not to amplify throughout
reasoning, we need to ensure that the bit complexity of the coefficients in
the sum-of-squares proof are polynomially bounded.

###  A.2 Useful sum-of-squares lemmas

######  Lemma A.8.

$\\{x^{2}=x\\}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.00063pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{2}$}}}\raisebox{1.96112pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{x}$}}}$}}}0\leqslant
x\leqslant 1\,.$

###### Proof.

The first inequality is trivial due to
$\\{x^{2}=x\\}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.00063pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{2}$}}}\raisebox{1.96112pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{x}$}}}$}}}x=x^{2}\geqslant
0$. For the second inequality, it follows that

$\\{x^{2}=x\\}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.00063pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{2}$}}}\raisebox{1.96112pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{x}$}}}$}}}x\leqslant\frac{x^{2}}{2}+\frac{1}{2}=\frac{x}{2}+\frac{1}{2}\,.$

Rearranging the terms, we get

$\\{x^{2}=x\\}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.00063pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{2}$}}}\raisebox{1.96112pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{x}$}}}$}}}x\leqslant
1\,.$

∎

######  Lemma A.9.

$\\{x^{2}=x,y^{2}=y\\}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{13.62817pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[13.62817pt]{\leavevmode\hbox{\set@color$\scriptstyle{4}$}}}\raisebox{3.32222pt}{\makebox[13.62817pt]{\leavevmode\hbox{\set@color$\scriptstyle{x,y}$}}}$}}}1-xy\leqslant(1-x)+(1-y)\,.$

###### Proof.

By Lemma A.8, it follows that

$\\{x^{2}=x,y^{2}=y\\}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{13.62817pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[13.62817pt]{\leavevmode\hbox{\set@color$\scriptstyle{2}$}}}\raisebox{3.32222pt}{\makebox[13.62817pt]{\leavevmode\hbox{\set@color$\scriptstyle{x,y}$}}}$}}}0\leqslant
x,y\leqslant 1\,.$

Therefore, we have

$\displaystyle\\{x^{2}=x,y^{2}=y\\}$
$\displaystyle\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{13.62817pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[13.62817pt]{\leavevmode\hbox{\set@color$\scriptstyle{4}$}}}\raisebox{3.32222pt}{\makebox[13.62817pt]{\leavevmode\hbox{\set@color$\scriptstyle{x,y}$}}}$}}}(1-y)(1-x)\geqslant
0$
$\displaystyle\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{13.62817pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[13.62817pt]{\leavevmode\hbox{\set@color$\scriptstyle{4}$}}}\raisebox{3.32222pt}{\makebox[13.62817pt]{\leavevmode\hbox{\set@color$\scriptstyle{x,y}$}}}$}}}1-x-y\geqslant-
xy$
$\displaystyle\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{13.62817pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[13.62817pt]{\leavevmode\hbox{\set@color$\scriptstyle{4}$}}}\raisebox{3.32222pt}{\makebox[13.62817pt]{\leavevmode\hbox{\set@color$\scriptstyle{x,y}$}}}$}}}2-x-y\geqslant
1-xy\,.$

∎

######  Lemma A.10.

Given constant $C$, we have

$\\{-C\leqslant x\leqslant
C\\}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.00063pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{2}$}}}\raisebox{1.96112pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{x}$}}}$}}}x^{2}\leqslant
C^{2}\,.$

###### Proof.

$\displaystyle\\{-C\leqslant x\leqslant C\\}$
$\displaystyle\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.00063pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{2}$}}}\raisebox{1.96112pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{x}$}}}$}}}(C-x)(C+x)\geqslant
0$
$\displaystyle\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.00063pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{2}$}}}\raisebox{1.96112pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{x}$}}}$}}}C^{2}-x^{2}\geqslant
0$
$\displaystyle\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.00063pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{2}$}}}\raisebox{1.96112pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{x}$}}}$}}}C^{2}\geqslant
x^{2}\,.$

∎

######  Lemma A.11.

Given constant $C$, we have

$\\{x^{2}\leqslant
C^{2}\\}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.00063pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{2}$}}}\raisebox{1.96112pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{x}$}}}$}}}-C\leqslant
x\leqslant C\,.$

###### Proof.

For the first inequality, we have

$\\{x^{2}\leqslant
C^{2}\\}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.00063pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{2}$}}}\raisebox{1.96112pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{x}$}}}$}}}x\geqslant-\frac{x^{2}}{2C}-\frac{C}{2}\geqslant-\frac{C^{2}}{2C}-\frac{C}{2}=-C\,.$

For the second inequality, we have

$\\{x^{2}\leqslant
C^{2}\\}\mathrel{\leavevmode\hbox{\set@color\raisebox{3.44444pt}{$\rule[-6.45831pt]{0.47787pt}{12.91663pt}\rule[-0.23894pt]{8.00063pt}{0.47787pt}\raisebox{-6.47223pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{2}$}}}\raisebox{1.96112pt}{\makebox[8.00063pt]{\leavevmode\hbox{\set@color$\scriptstyle{x}$}}}$}}}x\leqslant\frac{x^{2}}{2C}+\frac{C}{2}\leqslant\frac{C^{2}}{2C}+\frac{C}{2}=C\,.$

∎

##  Appendix B Concentration inequalities

######  Lemma B.1 (Average degree concentration).

Let $Q^{\circ}$ be an $n$-by-$n$ edge connection probability matrix and let
$d^{\circ}\mathrel{\mathop{:}}=d(Q^{\circ})$. Let
$\bm{A}\sim\m@thbbch@rG(n,Q^{\circ})$. Then for any $\delta\in(0,1)$,

$\operatorname*{\m@thbbch@rP}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert
d(\bm{A})-d^{\circ}}\right\rvert\geqslant\delta d^{\circ}}\right)\leqslant
2\exp\mathopen{}\mathclose{{}\left(-\frac{\delta^{2}nd^{\circ}}{6}}\right)\,,$

###### Proof.

Let
$\mu\mathrel{\mathop{:}}=\operatorname*{\m@thbbch@rE}\sumop\slimits@_{i<j}\bm{A}_{ij}=\sumop\slimits@_{i<j}p_{ij}$.
Using Chernoff bound, for $\delta\in(0,1)$,

$\displaystyle\operatorname*{\m@thbbch@rP}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert\sumop\slimits@_{i<j}\bm{A}_{ij}-\mu}\right\rvert\geqslant\delta\mu}\right)$
$\displaystyle\leqslant
2\exp\mathopen{}\mathclose{{}\left(-\frac{\delta^{2}\mu}{3}}\right)\,,$
$\displaystyle\operatorname*{\m@thbbch@rP}\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left\lvert
d(\bm{A})-d^{\circ}}\right\rvert\geqslant\delta d^{\circ}}\right)$
$\displaystyle\leqslant
2\exp\mathopen{}\mathclose{{}\left(-\frac{\delta^{2}nd^{\circ}}{6}}\right)\,.$

∎

######  Lemma B.2 (Degree distribution).

Let $Q^{\circ}$ be an $n$-by-$n$ edge connection probability matrix. Let $d$
be a parameter such that $d\geqslant 5$ and $\lVert
Q^{\circ}\rVert_{\infty}\leqslant d/n$. Then for every $t\in[2e^{2},\log n]$,
an inhomogeneous random graph $\m@thbbch@rG(n,Q^{\circ})$ has at least
$e^{-t}n$ nodes with degree at least $td$ with probability at most
$\exp(-te^{-t}nd/4)$.

###### Proof.

Let $\bm{m}_{k}$ denote the number of nodes with degree at least $k$ in
$\m@thbbch@rG(n,Q^{\circ})$. Then for every $\gamma\in[0,1]$,

$\displaystyle\operatorname*{\m@thbbch@rP}\mathopen{}\mathclose{{}\left(\bm{m}_{td}\geqslant\gamma
n}\right)$ $\displaystyle\leqslant{n\choose\gamma n}{\gamma n^{2}\choose\gamma
ntd/2}\mathopen{}\mathclose{{}\left(\frac{d}{n}}\right)^{\gamma ntd/2}$
$\displaystyle\leqslant\mathopen{}\mathclose{{}\left(\frac{e}{\gamma}}\right)^{\gamma
n}\mathopen{}\mathclose{{}\left(\frac{2e}{t}}\right)^{\gamma ntd/2}$
$\displaystyle=\exp\mathopen{}\mathclose{{}\left(-\gamma
n\mathopen{}\mathclose{{}\left(\frac{td}{2}\log\frac{t}{2e}-\log\frac{e}{\gamma}}\right)}\right)\,.$

Plugging in $\gamma=e^{-t}$ gives

$\operatorname*{\m@thbbch@rP}\mathopen{}\mathclose{{}\left(\bm{m}_{td}\geqslant
e^{-t}n}\right)\leqslant\exp\mathopen{}\mathclose{{}\left(-te^{-t}n\mathopen{}\mathclose{{}\left(\frac{d}{2}\log\frac{t}{2e}-1-1/t}\right)}\right)\,.$

For $t\in[2e^{2},\log n]$ and $d\geqslant 5$,

$\operatorname*{\m@thbbch@rP}\mathopen{}\mathclose{{}\left(\bm{m}_{td}\geqslant
e^{-t}n}\right)\leqslant\exp\mathopen{}\mathclose{{}\left(-te^{-t}n\mathopen{}\mathclose{{}\left(\frac{d}{2}-\frac{5}{4}}\right)}\right)\leqslant\exp\mathopen{}\mathclose{{}\left(-te^{-t}nd/4}\right)\,.$

∎

######  Lemma B.3 (Degree pruning).

Let $Q^{\circ}$ be an $n$-by-$n$ edge connection probability matrix. Let $d$
be a parameter such that $d\geqslant 5$ and $\lVert
Q^{\circ}\rVert_{\infty}\leqslant d/n$. Then with probability at least
$1-n^{1-d/4}$, an inhomogeneous graph $\m@thbbch@rG(n,Q^{\circ})$ has the
following property. For all $t\in[2e^{2},\log n]$, the number of edges
incident to nodes with degree at least $td$ is at most $2te^{-t}nd$;

###### Proof.

Let $\bm{m}_{k}$ denote the number of nodes with degree at least $k$ in
$\m@thbbch@rG(n,Q^{\circ})$. By Lemma B.2, for any $t\in[2e^{2},\log n]$ and
$d\geqslant 5$,

$\operatorname*{\m@thbbch@rP}\mathopen{}\mathclose{{}\left(\bm{m}_{td}\geqslant
e^{-t}n}\right)\leqslant\exp\mathopen{}\mathclose{{}\left(-te^{-t}nd/4}\right)\leqslant
n^{-d/4}\,.$

Applying union bound, the event that $m_{k}\leqslant e^{-k/d}n$ for any
integer $k\in[2e^{2}d,(\log n)d]$ happens with probability at least
$1-n^{1-d/4}$. We condition our following analysis on this event.

Fix a $t\in[2e^{2},\log n]$. The number of edges incident to nodes with degree
at least $td$ is at most

$\displaystyle\sumop\slimits@_{i=0}(t+i+1)d\cdot
e^{-(t+i)}n=nd\sumop\slimits@_{i=t}(i+1)e^{-i}=nde^{-t}\mathopen{}\mathclose{{}\left(\frac{e}{e-1}t+\frac{e^{2}}{(e-1)^{2}}}\right)\leqslant
2te^{-t}nd\,.$

∎

######  Lemma B.4 (Degree-truncated subgraph).

Let $Q^{\circ}$ be an $n$-by-$n$ edge connection probability matrix and let
$d^{\circ}\mathrel{\mathop{:}}=d(Q^{\circ})$. Let $d$ be a parameter such that
$d\geqslant 5$ and $\lVert Q^{\circ}\rVert_{\infty}\leqslant d/n$. For
$\delta\in(0,1)$, an inhomogeneous graph $\bm{A}\sim\m@thbbch@rG(n,Q^{\circ})$
has the following property with probability at least
$1-n^{1-d/4}-\exp(-\delta^{2}nd^{\circ}/6)$. For every $t\in[2e^{2},\log n]$,
$A$ contains an $n$-node subgraph $\tilde{A}$ of such that

  * •

$(\tilde{A}\m@thbbch@rone)_{i}\leqslant td$ for any $i\in[n]$;

  * •

$(1-\delta)d^{\circ}-4te^{-t}d\leqslant
d(\tilde{A})\leqslant(1+\delta)d^{\circ}$.

###### Proof.

By Lemma B.1 and Lemma B.3, $\bm{A}\sim\m@thbbch@rG(n,Q^{\circ})$ has the
following two properties with probability at least
$1-n^{1-d/4}-\exp(-\delta^{2}nd^{\circ}/6)$.

  * •

$\lvert d(A)-d^{\circ}\rvert\leqslant\delta d^{\circ}$.

  * •

For all $t\in[2e^{2},\log n]$, the number of edges incident to nodes with
degree at least $td$ is at most $2te^{-t}nd$.

Consider a graph $A$ with the above two properties. Fix a $t\in[2e^{2},\log
n]$. By removing at most $2te^{-t}nd$ edges from $A$, we can obtain a graph
$\tilde{A}$ such that the maximum degree of $\tilde{A}$ is at most $td$.
Moreover,

$\displaystyle d(\tilde{A})\geqslant
d(A)-4te^{-t}d\geqslant(1-\delta)d^{\circ}-4te^{-t}d\,,$ $\displaystyle
d(\tilde{A})\leqslant d(A)\leqslant(1+\delta)d^{\circ}\,.$

∎

######  Lemma B.5 (Spectral bound [BvH16]).

Let $\bm{A}\sim\m@thbbch@rG(n,p_{0})$ and suppose $np_{0}\geqslant 5$. Then
with probability at least $1-n^{-\Omega(1)}$,

$\mathopen{}\mathclose{{}\left\lVert\bm{A}-p_{0}(\m@thbbch@rone{}^{\top}-\mathrm{Id})}\right\rVert_{\mathrm{op}}\leqslant
O\mathopen{}\mathclose{{}\left(\sqrt{np_{0}\log n}}\right)\,.$


Dyonic black holes in Kaluza-Klein theory with a Gauss-Bonnet action

S. Mignemi††∗ e-mail<EMAIL_ADDRESS>
Dipartimento di Matematica, Università di Cagliari

via Ospedale 72, 09124 Cagliari, Italy

and INFN, Sezione di Cagliari

Cittadella Universitaria, 09042 Monserrato, Italy

Abstract

We consider a five-dimensional Einstein-Gauss-Bonnet model, which gives rise
after dimensional reduction to Einstein gravity nonminimally coupled to
nonlinear electrodynamics. The black hole solutions of the four-dimensional
model modify the Reissner-Nordström solutions of general relativity. The
gravitational field presents the standard singularity at $r=0$, while the
electric field can be regular everywhere if the magnetic charge vanishes.

1\. Introduction In his career, Richard Kerner has given important
contributions to the Kaluza-Klein framework, in particular showing that also
nonabelian gauge theories can be obtained from the process of dimensional
reduction by increasing the number of internal dimensions [1]. He was also one
of the first to notice the relevance of Gauss-Bonnet (GB) terms in the action
of higher-dimensional theories, showing that they give rise to nonlinear
contributions to the electrodynamics in the reduced theory [2].††1 This was
also independently observed by Buchdal [3].

Nonlinear electrodynamics was first proposed by Heisenberg and Euler [4] to
give an effective classical description of quantum electrodynamics in a
suitable limit. A general formulation, which includes also the model studied
in [2.3] as a special case, was given by Plebanski [5]. However, the action
obtained from dimensional reduction of the GB action enjoys peculiar algebraic
properties. Some solutions of this model in flat space, hence neglecting
gravity, have been discussed in [2,6,7].

In the present paper, we are interested in the full theory containing both
gravity and Maxwell fields. We have recently shown that a five-dimensional
Kaluza-Klein theory containing GB contributions admits exact solutions that
modify the Reissner-Nordström (RN) metric of general relativity [7]. In
particular, when the nonminimal coupling between gravity and Maxwell fields
arising from the dimensional reduction is neglected, its dyonic solutions
display an everywhere regular electric field [7]. These modifications could in
principle give experimental evidence of the existence of extra dimensions.

Here, we give a more complete discussion of the dyonic solutions of the model,
that takes into account also the nonminimal interaction terms. It turns out
that, contrary to the case where these terms are neglected, the electric field
can be regular everywhere only for vanishing magnetic field.††2 The existence
of solutions with regular electric field was predicted also in [8], using
different methods. This may be considered as a favourable feature of the
model, since magnetic monopoles are not observed in nature.

2\. The model As is well known, the Einstein-Hilbert action can be generalized
in dimensions higher than four, by the introduction of the Lovelock terms [9].
These give the most general extensions of the Einstein-Hilbert action that
give rise to second order field equations in arbitrary dimensions. One of
their most notable properties is that they do not introduce new degrees of
freedom in the spectrum in addition to the graviton, and therefore avoid the
presence of ghosts or tachyons, in contrast with most higher-derivative
actions [10]. In lower dimensions they are total derivatives and do not
contribute to the equations of motion. In particular, in five dimension, the
only term of this type is the so-called Gauss-Bonnet term,

$S=R^{\mu\nu\rho\sigma}R_{\mu\nu\rho\sigma}-4R^{\mu\nu}R_{\mu\nu}+R^{2}.$

The dimensional reduction of these generalized actions gives rise to models of
gravity coupled to nonlinear electrodynamics, which as a consequence of the
properties of the higher-dimensional theory, contain only graviton and photon
excitations, and are therefore relevant from a phenomenological perspective.

Therefore, we consider a five-dimensional Einstein-Gauss-Bonnet theory, with
action [1,2,7]

$I=\int\sqrt{-g}\ d^{5}x(R+\alpha S),$ $None$

where $\alpha$ is a coupling constant and $R$ the Ricci scalar. The coupling
constant $\alpha$ has dimension $[L]^{2}$, and is usually assumed to be
positive for stability reasons. Arguments based on quantum gravity or string
theory fix it to be of Planck scale, but in any case observations set a very
small upper limit on its value [8].

We make the simple ansatz for the five-dimensional metric††3 We set
$\mu,\nu=0,\dots,4$; $i,j=0,\dots,3$. [9-10]

$g_{\mu\nu}=\left(\matrix{g_{ij}+4A_{i}A_{j}&2A_{i}\cr 2A_{j}&1}\right),$
$None$

where $A_{i}$ is the Maxwell potential and we have chosen the normalization in
order to simplify the dimensionally reduced action.

Discarding total derivatives, the action reduces to [2,3,13]

$I=\int\sqrt{-g}\
d^{4}x\left[R-F^{ij}F_{ij}+3\alpha\Big{[}(F^{ij}F_{ij})^{2}-2F^{ij}F_{jk}F^{kl}F_{li}\Big{]}-2\alpha
L_{int}\right],$ $None$

where $F_{ij}=\partial_{i}A_{j}-\partial_{j}A_{i}$ and the interaction term is

$L_{int}=F^{ij}F^{kl}(R_{ijkl}-4R_{ik}\delta_{jl}+R\,\delta_{ik}\delta_{jl}).$
$None$

If one neglects $L_{int}$, the action describes a model of gravity minimally
coupled to a specific form of nonlinear electrodynamics. Exact asymptotically
flat spherically symmetric solutions of (3) in the absence of $L_{int}$ have
been investigated in [7], where it was shown that the Reissner-Nordström
solution of general relativity is modified in the dyonic case. In particular,
for $\alpha>0$, the solutions read

$A=a(r)\,dt+P\cos\theta\,d\phi,$ $None$
$ds^{2}=-e^{2\nu}dt^{2}+e^{-2\nu}dr^{2}+r^{2}(d\theta^{2}+\sin^{2}\theta\,d\phi^{2}),$
$None$

with $P$ the magnetic monopole charge, and radial electric field $E\equiv
F_{01}$,

$E={da\over dr}={Qr^{2}\over r^{4}+3\alpha P^{2}},$ $None$

while the metric function is

$e^{2\nu}=\ 1-{2M\over r}+{P^{2}\over r^{2}}+{Q^{2}\over
2\sqrt{2{\tilde{\alpha}}}r}\left[\pi+\arctan\left(1-{\sqrt{2}\,r\over\sqrt{\tilde{\alpha}}}\right)-\arctan\left(1+{\sqrt{2}\,r\over\sqrt{\tilde{\alpha}}}\right)+{1\over
2}\log{r^{2}-\sqrt{2{\tilde{\alpha}}}\,r+{\tilde{\alpha}}\over
r^{2}+\sqrt{2{\tilde{\alpha}}}\,r+{\tilde{\alpha}}}\right],$ $None$

where we have set ${\tilde{\alpha}}=\sqrt{3\alpha P^{2}}$. The asymptotic
behavior of the solution is given by

$e^{2\nu}=1-{2M\over r}+{Q^{2}+P^{2}\over r^{2}}-{3\bar{\alpha}P^{2}Q^{2}\over
5r^{6}}+o\left({1\over r^{7}}\right),$ $None$

and has therefore the same form as for RN up to order $1/r^{5}$. It follows
that the integration constants $M$ and $Q$ can be identified with the mass and
the electric charge. The electric field is regular everywhere, and the
properties of the metric are analogous to those of the RN solution: a
curvature singularity is present at the origin and for $M$ greater than its
extremal value is shielded by two horizons.

If $\alpha<0$, instead, a singularity of the electric field appears at
$r_{0}=\sqrt{\tilde{\alpha}}$, where now ${\tilde{\alpha}}=\sqrt{-3\alpha
P^{2}}$. The metric takes a slightly different form,

$e^{2\nu}=\ 1-{2M\over r}+{P^{2}\over r^{2}}+{Q^{2}\over
2\sqrt{\tilde{\alpha}}\,r}\left[{\pi\over
2}-\arctan{r\over\sqrt{\tilde{\alpha}}}-{1\over
2}\log{r-\sqrt{\tilde{\alpha}}\over r+\sqrt{\tilde{\alpha}}}\right].$ $None$

A spherical curvature singularity occurs at $r=r_{0}$ and the solution can
have one or two horizons depending on the specific values of the parameters,
while the asymptotic behavior is still given by (9).

It is evident that the effects of nonlinear electrodynamics are more relevant
at small $r$, and tend to vanish at infinity.

3\. The solution We now consider the asymptotically flat spherically symmetric
solution of the field equations stemming from the action (3), when also the
term $L_{int}$ is included. In this case it is not possible to find an exact
solution, and we must proceed perturbatively.

We look for spherically symmetric solutions with electromagnetic field of the
dyonic form (5) and

$ds^{2}=-e^{2\nu}dt^{2}+e^{2\lambda-2\nu}dr^{2}+e^{2\rho}d\Omega^{2},$ $None$

where $\nu$, $\lambda$ and $\rho$ are functions of $r$.

After integration by parts, the action becomes

$\eqalign{I=&\ 2\int dr\bigg{[}(2\nu^{\prime}\rho^{\prime}+\rho^{\prime
2})e^{2\nu-\lambda+2\rho}+e^{\lambda}+a^{\prime
2}e^{-\lambda+2\rho}-P^{2}e^{\lambda-2\rho}\cr&+4\alpha\bigg{(}3P^{2}a^{\prime
2}e^{-\lambda-2\rho}+a^{\prime 2}\rho^{\prime
2}e^{2\nu-3\lambda+2\rho}-a^{\prime
2}e^{-\lambda}+2P^{2}\nu^{\prime}\rho^{\prime}e^{2\nu-\lambda-2\rho}\bigg{)}\bigg{]}},$
$None$

where ${}^{\prime}=d/dr$.

Varying with respect to the fields, and then choosing the gauge $e^{\rho}=r$,
the independent field equations can be put in the form

$\eqalignno{&\lambda^{\prime}=-{4\alpha\over r}\left(a^{\prime
2}e^{-2\lambda}+{P^{2}\over r^{3}}\lambda^{\prime}+{3P^{2}\over
r^{4}}\right),&(13)\cr&(re^{2\nu})^{\prime}+4\alpha
P^{2}{(e^{2\nu})^{\prime}\over r^{3}}=\left(1-{P^{2}\over
r^{2}}\right)e^{2\lambda}-r^{2}a^{\prime 2}+4\alpha\,a^{\prime
2}\left(1-3e^{2\nu-2\lambda}-{3P^{2}\over
r^{2}}\right),&(14)\cr&\left[r^{2}e^{-\lambda}\left(1+12\alpha\,{P^{2}\over
r^{4}}+4\alpha\,{e^{2\nu-2\lambda}-1\over
r^{2}}\right)a^{\prime}\right]^{\prime}=0.&(15)}$

An important effect of the nonminimal gravity-Maxwell coupling $L_{int}$ is
that the metric field $\lambda$ no longer vanishes. This is a common feature
in presence of nonminimally coupled Maxwell fields.

Also the radial electric field $E\equiv F_{01}$ is modified with respect to
the solution (7), since (15) gives

$E=a^{\prime}={Q\,r^{2}e^{\lambda}\over
r^{4}+4\alpha\left(e^{2\nu-2\lambda}-1\right)r^{2}+12\alpha P^{2}},$ $None$

where $Q$ is an integration constant that can be identified with the electric
charge.

The equations (13)-(15) do not admit a solution in analytical form, so we
perturb in the small parameter $\alpha$ around the Reissner-Nordström
background

$ds^{2}=-Adt^{2}+A^{-1}dr^{2}+r^{2}d\Omega^{2},\qquad E={Q\over r^{2}},$
$None$

with

$A=1-{2M\over r}+{Q^{2}+P^{2}\over r^{2}}.$ $None$

The perturbative expansion will be valid for large values of $r$, namely
$r\gg\sqrt{\alpha}$.

As is well known, the horizons of the RN metric are located at

$r^{\ast}_{\pm}=M\pm\sqrt{M^{2}-Q^{2}-P^{2}}.$ $None$

In order to simplify some expressions, in the following we shall write the RN
mass $M$ in terms of the outer horizon and of the charges as

$M={{r^{\ast}_{+}}^{2}+Q^{2}+P^{2}\over 2r^{\ast}_{+}}.$ $None$

We now define the perturbations $\sigma(r)$, $\gamma(r)$ and $\phi(r)$ through
an expansion at order $\alpha$ around a RN background,

$e^{2\nu}=A+\alpha\sigma,\qquad\lambda=\alpha\gamma,\qquad E={Q\over
r^{2}}(1+\alpha\phi),$ $None$

where of course, $\lambda=0$ for RN.

Integrating (13), we obtain at order $\alpha$

$\gamma={Q^{2}+3P^{2}\over r^{4}}.$ $None$

Substitution in (15) gives

$\phi={8M\over r^{3}}-{3Q^{2}+13P^{2}\over r^{4}}.$ $None$

Finally, substituting the previous results in (13) and integrating, one
obtains

$\sigma={2(Q^{2}-P^{2})\over r^{4}}-{2M(Q^{2}-P^{2})\over
r^{5}}+{6Q^{4}-8P^{2}Q^{2}-2P^{4}\over 5r^{6}}.$ $None$

In all the solutions, we have chosen boundary conditions such that the
corrections vanish at infinity. Hence, at order $\alpha$,

$e^{2\nu}\sim 1-{2M\over r}+{Q^{2}+P^{2}\over
r^{2}}+2\alpha\left({Q^{2}-P^{2}\over r^{4}}-{M(Q^{2}-P^{2})\over
r^{5}}+{3Q^{4}-4P^{2}Q^{2}-P^{4}\over 5r^{6}}\right),$ $None$

$e^{2\lambda}\sim 1+2\alpha\,{Q^{2}+3P^{2}\over r^{4}},$ $None$

$E\sim{Q\over r^{2}}\left(1+{8\alpha M\over
r^{3}}-{\alpha(3Q^{2}+13P^{2})\over r^{4}}\right).$ $None$

Our approximation works well for $r\to\infty$. At leading orders in $1/r$ the
asymptotic behavior is the same as in RN. Therefore, we can still identify $M$
with the mass of the black hole and $Q$ and $P$ with its electric and magnetic
charge. Notice that the corrections to the RN solutions are much larger than
in the case where the $L_{int}$ term is neglected, since they are now
$o(1/r^{4})$. Also, they are no longer symmetric in $Q$ and $P$ at leading
order in $\alpha$.

The horizons are displaced with respect to the RN solutions, where they are
located at $r^{\ast}_{\pm}$. At first order in $\alpha$, one has
$r_{\pm}=r^{\ast}_{\pm}+\alpha\Delta r_{\pm}$, where

$\Delta r_{\pm}=-{\sigma\over A^{\prime}}\Big{|}_{r=r^{\ast}_{\pm}}.$ $None$

It follows that

$\Delta
r_{\pm}={5(P^{2}-Q^{2}){r^{\ast}_{\pm}}^{2}-3P^{4}+8P^{2}Q^{2}-Q^{4}\over
5{r^{\ast}_{\pm}}^{3}({r^{\ast}_{\pm}}^{2}-P^{2}-Q^{2})},$ $None$

where to simplify the expression we have chosen as independent parameters
$r^{\ast}_{+}\,(r^{\ast}_{-})$, $Q$ and $P$. The actual values of these
displacements strongly depend on the charges.

A calculation shows that the condition of extremality is, at first order in
$\alpha$,

$M^{2}=P^{2}+Q^{2}+{\alpha\over
5}\,{P^{4}+4Q^{2}P^{2}-3Q^{4}\over(P^{2}+Q^{2})^{2}}.$ $None$

Depending on the values of $Q$ and $P$ the correction with respect to the RN
case can be both positive or negative. We recall however that, while the value
of $r_{+}$ obtained in this way is in general well approximated by (29), the
value of $r_{-}$ is reliable only for very small values of $\alpha$.

In this approximation, the metric function $e^{2\nu}$ does not differ much
from that of RN and the causal structure should therefore be analog. Hence,
for $M$ greater than extremality, one has two horizon, while a naked
singularity is present for $M$ less than its extremal value. However, this is
not necessarily true for greater values of $\alpha$, where the approximation
fails.

Using standard definitions it is possible to derive the thermodynamical
quantities associated to the black hole from the behaviour of the metric
functions near the outer horizon,. The temperature can be calculated from the
formula

$T={1\over 4\pi}\,e^{-\lambda}(e^{2\nu})^{\prime}\big{|}_{r=r_{+}}\sim{1\over
4\pi}\Big{[}A^{\prime}(1-\alpha\gamma)+\alpha\sigma^{\prime}\Big{]}_{r=r_{+}}.$
$None$

Hence,

$\eqalign{T\sim&\ {1\over
4\pi{r^{\ast}_{+}}^{3}}\bigg{(}{r^{\ast}_{+}}^{2}-P^{2}-Q^{2}\cr&-2\alpha\
{7P^{6}+25P^{4}Q^{2}+17P^{2}Q^{4}-Q^{6}-14P^{4}{r^{\ast}_{+}}^{2}-36P^{2}Q^{2}{r^{\ast}_{+}}^{2}+2Q^{4}{r^{\ast}_{+}}^{2}+5(Q^{2}+P^{2}){r^{\ast}_{+}}^{4}\over
5{r^{\ast}_{+}}^{4}({r^{\ast}_{+}}^{2}-P^{2}-Q^{2})}\bigg{)}.}$ $None$

The entropy $S$ is usually identified with the area of the horizon, namely,

$S\sim
4\pi{r^{\ast}_{+}}^{2}\left(1-2\alpha{3P^{4}-8P^{2}Q^{2}+Q^{4}+5(Q^{2}-P^{2}){r^{\ast}_{+}}^{2}\over
5{r^{\ast}_{+}}^{4}({r^{\ast}_{+}}^{2}-P^{2}-Q^{2})}\right).$ $None$

It follows that the thermodynamical quantities display a complicate dependence
on the charges.

It is also interesting to investigate the behavior of the solutions near the
singularity. This can be calculated by an expansion in powers of $r$ near
$r=0$. Setting

$e^{\nu}\sim r^{h},\qquad e^{\lambda}\sim r^{l},\qquad E\sim r^{k},$

and substituting in the field equations (13)-(15), one obtains $h=-2$, $l=-3$
and $k=-1$. It follows that the metric functions and the electric field
diverge for $r=0$, thus destroying the nice property of the solution of sect.
2 to have a finite electric field at the origin.

The only exception is for $P=0$. In this case, the electric field vanishes at
the origin. In fact now $h=-1$, $l=0$ and $k=1$. The existence of electric
solutions regular at the origin in absence of magnetic field has also been
noticed in [8]. However, for small values of $Q$, numerical solutions show
that the solutions become singular at a point $r_{0}>0$, presenting a
spherical singularity, similarly with the $\alpha<0$ solutions of sect. 2.

Remarkably, the behaviour of the solution is therefore opposite to those with
$L_{int}=0$, since regular solution can now exist only if $P=0$.

4\. Numerical calculations

The solutions of (13)-(15) can also be obtained numerically. This is
especially interesting for $r\ll\alpha$, where the perturbative calculation of
the previous section fails. In fig. 1 are reported the metric functions and
the electric field for $\alpha=0.01$, $M=1$, and several values of $Q$ and
$P$, such that $Q^{2}+P^{2}=1/2$, so that $r_{+}\sim 0.7$. The metric
functions $e^{\nu}$ and $e^{\lambda}$ do not change much for different values
of the charges. In particular, $\epsilon^{2\nu}$ is similar to the RN
solution, while $e^{-2\lambda}=1$ for $r\gg\sqrt{\alpha}$ and then fades to 0
for $r\to 0$. In general, a curvature singularity is present at $r=0$ and the
causal structure is essentially the same as that of the RN solution. Also the
electric field is singular at the origin as in the RN solution.

As mentioned before, an interesting special case is given by $P=0$. In fig. 2
are depicted the metric functions $e^{2\nu}$, $e^{-2\lambda}$ and the electric
field $F$ for $M=1$ and different values of the electric charge. For our
choice of the parameters, if $Q>0.44$ the electric field is regular at the
origin. The possibility of such behaviour had been noticed in [8] using
different methods. However, for smaller $Q$ a singularity occurs for a finite
value of $r$ and the metric functions and the electric field diverge there.

Fig. 1: The metric function $\scriptstyle{e^{2\nu}}$ and
$\scriptstyle{e^{-2\lambda}}$ and the electric field $\scriptstyle{F}$ for
black holes with mass $\scriptstyle{M\;=\;1}$,
$\scriptstyle{Q^{2}+P^{2}\;=\;{1\over 2}}$ and $\scriptstyle{Q\;=\;0.1}$ (in
cyano), $\scriptstyle{Q\;=\;0.3}$ (in blue), $\scriptstyle{Q\;=\;0.5}$ (in
green), $\scriptstyle{Q\;=\;0.7}$ (in red).

Fig. 2: The metric function $\scriptstyle{e^{2\nu}}$ and
$\scriptstyle{e^{-2\lambda}}$ and the electric field $\scriptstyle{F}$ for
black holes with mass $\scriptstyle{M\;=\;1}$, $\scriptstyle{P\;=\;0}$, and
$\scriptstyle{Q\;=\;0.1}$ (in cyano), $\scriptstyle{Q\;=\;0.3}$ (in blue),
$\scriptstyle{Q\;=\;0.5}$ (in green), $\scriptstyle{Q\;=\;0.7}$ (in red),
$\scriptstyle{Q\;=\;0.9}$ (in magenta). As it is evident from the graphs, the
curves with $\scriptstyle{Q\;=\;0.1}$, $\scriptstyle{Q\;=\;0.3}$ display a
singularity at $\scriptstyle{r_{0}\;=\;0.08}$, $\scriptstyle{r_{0}\;=\;0.06}$
respectively.

5\. Conclusions We have studied the solutions of the dimensionally reduced
Kaluza-Klein theory with Einstein-Gauss-Bonnet action, including the
interaction terms that were disregarded in ref. [7]. A surprising consequence
of the inclusion of $L_{int}$ in the action is that dyonic solutions no longer
display a regular electric field, like the solutions of sect. 2 [7], but
instead such behaviour can occur for pure electric solutions.

An extension of our research would be the introduction of a scalar field in
the ansatz of dimensional reduction [14,15]. In this case the GB term is
present also in the reduced four-dimensional theory, coupled to the scalar.
This fact may modify the structure of the solutions, see e.g. [16].

References

[1] R. Kerner, Ann. Inst. H. Poincaré Phys.Theor. 9, 143 (1968). [2] R.
Kerner, C. R. Acad. Sc. Paris 304, 621 (1987). [3] H.A. Buchdal, J. Phys. A12,
1037 (1979). [4] W. Heisenberg and H. Euler, Z. Phys. 98, 714 (1936). [5] J.
Plebański, Lectures on non-linear electrodynamics, NORDITA, Copenhagen, 1968.
[6] R. Kerner, in Proceedings of Varna Summer School, ”Infinite Dimensional
Lie Algebras and Quantum Field Theory”, World Scientific 1987,
arXiv:2303.10603. [7] S. Mignemi, Int. J. Mod. Phys. A37, 2250065 (2022). [8]
H.H. Soleng and Ø. Grøn, Ann. Phys. 240, 432 (1995). [9] D. Lovelock, J. Math.
Phys. 12, 498 (1971). [10] B. Zumino, Phys. Rep. 137, 109 (1986). [11] T.
Kaluza, Sitz. Preuss. Akad. Wiss., Math. Phys. 1, 966 (1921). [12] O. Klein,
Z. Phys. 37, 895 (1926). [13] F. Müller-Hoissen, Phys. Lett. B201, 325 (1998).
[14] P. Jordan, Naturwissenschaften 11, 250 (1946). [15] M.Y. Thiry, Compt.
Rend. Acad. Sci. Paris 226, 216 (1948). [16] S. Mignemi and N.R. Stewart,
Phys. Rev. D47, 5259 (1993).