11institutetext: Computer Science Department
University of California, Irvine
Irvine, CA 92697, USA
11email<EMAIL_ADDRESS>
# Lower Bounds for Non-Adaptive
Shortest Path Relaxation

David Eppstein

###### Abstract

We consider single-source shortest path algorithms that perform a sequence of
relaxation steps whose ordering depends only on the input graph structure and
not on its weights or the results of prior steps. Each step examines one edge
of the graph, and replaces the tentative distance to the endpoint of the edge
by its minimum with the tentative distance to the start of the edge, plus the
edge length. As we prove, among such algorithms, the Bellman–Ford algorithm
has optimal complexity for dense graphs and near-optimal complexity for sparse
graphs, as a function of the number of edges and vertices in the given graph.
Our analysis holds both for deterministic algorithms and for randomized
algorithms that find shortest path distances with high probability.

##  1 Introduction

Dijkstra’s algorithm finds shortest paths in directed graphs when all edge
weights are non-negative, but the problem becomes more difficult when negative
edge weights (but not negative cycles) are allowed. In this case, despite
recent breakthroughs on near-linear time bounds for graphs with small integer
edge weights [5], the best strongly-polynomial time bound for single-source
shortest paths remains that of the Bellman–Ford algorithm [4, 10, 18], which
takes time $O(mn)$ on graphs with $m$ edges and $n$ vertices, or $O(n^{3})$ on
dense graphs.

Both Dijkstra’s algorithm and the Bellman–Ford algorithm (as well as an
unnamed linear-time algorithm for single-source shortest paths in directed
acyclic graphs) can be unified under the framework of _relaxation algorithms_
, also called _label-correcting algorithms_ [8]. These algorithms initialize
tentative distances $D[v]$ from the source vertex to each other vertex $v$, by
setting $D[s]=0$ and $D[v]=+\infty$ for $v\neq s$. Then, they repeatedly
_relax_ the edges of the graph. This means, that for a given edge $u\to v$,
the algorithm updates $D[v]$ to $D[u]+\operatorname{length}(u\to v)$. In
Dijkstra’s algorithm, each edge $u\to v$ is relaxed once, in sorted order by
the tentative distance $D[u]$. In the Bellman–Ford algorithm, an edge can be
relaxed many times. The algorithm starts with the tentative distance equal to
the correct distance for $s$, but not for the other vertices. Whenever the
algorithm relaxes an edge $u\to v$ in the shortest path tree, at a time when
$u$ already has the correct distance, the tentative distance to $v$ becomes
correct as well. Thus, the goal in designing the algorithm is to perform these
distance-correcting relaxations while wasting as little effort as possible on
other relaxations that do not correct any distance, and on the overhead in
selecting which relaxation to perform.

We would like to prove or disprove the optimality of the Bellman–Ford
algorithm among a general class of strongly-polynomial shortest path
algorithms, without restricting the types of computation such an algorithm can
perform, but such a result appears to remain far out of reach. Instead, in
this work we focus only on relaxation algorithms, asking: how few relaxation
steps are needed? Note that, without further assumptions, a shortest path
algorithm could “cheat”, computing a shortest path tree in some other way and
then performing only $n-1$ relaxation steps in a top-down traversal of a
shortest path tree. To focus purely on relaxation, and prevent such cheating,
we consider _non-adaptive relaxation algorithms_ , in which the sequence of
relaxation steps is determined only by the structure of the given graph, and
not on its weights nor on the outcome of earlier relaxation steps. Dijkstra’s
algorithm is adaptive, but the linear-time DAG algorithm is non-adaptive.
Another example of a non-adaptive algorithm comes from past work on the graphs
in which, like DAGs, it is possible to relax every edge once in a fixed order
and guarantee that all tentative distances are correct [12]. As usually
described, the Bellman–Ford algorithm is adaptive. Its typical optimizations
include adaptive rules that disallow repeatedly relaxing any edge $u\to v$
unless the tentative distance to $u$ has decreased since the previous
relaxation, and that stop the entire algorithm when no more allowed
relaxations can be found. However, its same asymptotic time bounds can be
achieved by a non-adaptive version of the Bellman–Ford algorithm, with a
_round-robin_ relaxation sequence, one that merely repeats $n-1$ rounds of
relaxing all edges in the same order per round. A non-adaptive asynchronous
distributed form of the Bellman–Ford algorithm is widely used in _distance
vector routing_ of internet traffic, to maintain paths of minimum hop count
between major internet gateways [13].

###  1.1 Known Upper Bounds

We do not require non-adaptive relaxation algorithms to be round-robin, but we
are unaware of any way to take advantage of this extra flexibility.
Nevertheless, among round-robin algorithms, there is still freedom to choose
the ordering of edges within each round, and this freedom can lead to improved
constant factors in the number of relaxation steps performed by the
Bellman–Ford algorithm.

Yen [21] described a method based on the following idea. Choose an arbitrary
linear ordering for the vertices, and partition the edges into two subsets:
the edges that are directed from an earlier vertex to a later vertex in the
ordering, and the edges that are directed from a later vertex to an earlier
vertex. Both of these two edge subsets define directed acyclic subgraphs of
the given graph, with the chosen linear ordering or its reverse as a
topological ordering. Use a round-robin edge ordering that first relaxes all
of the edges of the first subgraph, in its topological order, and then relaxes
all of the edges of the second subgraph, in its topological order. If any
shortest path is divided into contiguous subpaths that lie within one of these
two DAGs, then each two consecutive subpaths from the first and second DAG
will be relaxed in order by each round of the algorithm. In the worst case,
there is a single shortest path of $n-1$ edges, alternating between the two
DAGs, requiring $\lceil n/2\rceil$ rounds of relaxation. For complete directed
graphs, this method uses $\bigl{(}\tfrac{1}{2}+o(1)\bigr{)}n^{3}$ relaxation
steps, instead of the $\bigl{(}1+o(1)\bigr{)}n^{3}$ that might be used by a
less-careful round-robin method.

As we showed in earlier work [2], an additional constant factor savings can be
obtained by a randomized algorithm that selects from a random distribution of
non-adaptive relaxation sequences, and that obtains a correct output with high
probability rather than with certainty. To do so, use Yen’s method, but choose
the vertex ordering as a uniformly random permutation of the vertices, rather
than arbitrarily. In any shortest path tree, each vertex with more than one
child reduces the number of steps from the source to the deepest leaf by one,
reducing the number of alternations between the two DAGs. For each remaining
vertex with one child in the tree, the probability that it lies between its
parent and child in the randomly selected ordering is $\tfrac{1}{3}$, and when
this happens, it does not contribute to the bound on the number of
alternations. With high probability, the number of these non-contributing
vertices is close to one third of the single-child vertices. Therefore, with
high probability, the maximum number of alternations between the two DAGs
among paths on the shortest path tree is $\bigl{(}\tfrac{2}{3}+o(1)\bigr{)}n$,
and an algorithm that uses this method to perform
$\bigl{(}\tfrac{1}{3}+o(1)\bigr{)}n^{3}$ relaxation steps will find the
correct shortest paths with high probability.

The worst-case asymptotic time of these methods remains $O(n^{3})$ for
complete graphs, and $O(mn)$ for arbitrary graphs with $m$ vertices and $n$
edges. Both Yen’s method and the randomized permutation method can also be
used in adaptive versions of the Bellman–Ford algorithm, with better constant
factors and in the randomized case leading to a Las Vegas algorithm rather
than a Monte Carlo algorithm, but it is their non-adaptive variants that
concern us here.

###  1.2 New Lower Bounds

We provide the following results:

  * •

Any deterministic non-adaptive relaxation algorithm for single-source shortest
paths on a complete directed graph with $n$ vertices must use
$\bigl{(}\tfrac{1}{6}-o(1)\bigr{)}n^{3}$ relaxation steps.

  * •

Any randomized non-adaptive relaxation algorithm for shortest paths on a
complete directed graph with $n$ vertices, that with high probability sets all
distances correctly, must use $\bigl{(}\tfrac{1}{12}-o(1)\bigr{)}n^{3}$
relaxation steps.

  * •

For any $m$ and $n$ with $n\leq m\leq 2\tbinom{n}{2}$, there exists a directed
graph on $m$ edges and $n$ vertices on which any deterministic or high-
probability randomized non-adaptive relaxation algorithm for shortest paths
must use $\Omega(mn/\log n)$ relaxation steps. When
$m=\Omega(n^{1+\varepsilon})$ for some $\varepsilon>0$, the lower bound
improves to $\Omega(mn)$.

These lower bounds hold even on graphs for which all edges weights are zero
and one, for which an adaptive algorithm, Dial’s algorithm, can find shortest
paths in linear time [9].

###  1.3 Related Work

Although we are not aware of prior work in the precise model of computation
that we use, variants of the Bellman–Ford algorithm have been studied and
shown optimal for some other related problems:

  * •

The $k$-walk problem asks for a sequence of exactly $k$ edges, starting and
one vertex and ending at the other, allowing repeated edges. The Bellman–Ford
algorithm can be modified to find the shortest $k$-walk between two vertices
in time $O(kn^{2})$, non-adaptively. In any non-adaptive relaxation algorithm,
the only arithmetic operations on path lengths and edge weights are addition
and minimization, and these operations are performed in a fixed order.
Therefore, the sequence of these operations can be expanded into a circuit,
with two kinds of gates: minimization and addition. The resulting
$(\min,+)$-circuit model of computation is somewhat more general than the
class of relaxation algorithms, because the sequence of operations performed
in this model does not need to come from a sequence of relaxation steps. The
$k$-walk version of the Bellman–Ford algorithm is nearly optimal in the
$(\min,+)$-circuit model: circuit size $\Omega\bigl{(}k(n-k)n\bigr{)}$ is
necessary [14]. However, this $k$-walk problem is different from the shortest
path problem, so this bound does not directly apply to shortest paths.

  * •

Under conditional hypotheses that are standard in fine-grained complexity
analysis, the $O(km)$ time of Bellman–Ford for finding paths of at most $k$
steps, for graphs of $m$ edges, is again nearly optimal: neither the exponent
of $k$ nor the exponent of $m$ can be reduced to a constant less than one. For
large-enough $k$, the shortest path of at most $k$ steps is just the usual
shortest path, but this lower bound applies only for choices of $k$ that are
small enough to allow the result to differ from the shortest path [15].

  * •

Another related problem is the all hops shortest path problem, which asks to
simultaneously compute $k$ paths, having distinct numbers of edges from one to
a given parameter $k$. Again, this can be done in time $O(km)$ by a variant of
the Bellman–Ford algorithm, and it has an unconditional $\Omega(km)$ lower
bound for algorithms that access the edge weights only by path length
comparisons, as Bellman–Ford does [11, 6]. Because it demands multiple paths
as output, this lower bound does not apply to algorithms that compute only a
single shortest path.

  * •

Meyer et al. [17] study a version of the Bellman–Ford algorithm, in which
edges are relaxed in a specific (adaptive) order. They construct sparse
graphs, with $O(n)$ edges, on which this algorithm takes $\Omega(n^{2})$ time,
even in the average case for edge weights uniformly drawn from a unit
interval. This bound applies only to this algorithm and not to other
relaxation orders.

##  2 Deterministic Lower Bound for Complete Graphs

The simplest of our results, and the prototype for our other results, is a
lower bound on the number of relaxations needed by a deterministic non-
adaptive relaxation algorithm, in the worst case, on a complete directed graph
with $n$ vertices.

###### Theorem 2.1

Any deterministic non-adaptive relaxation algorithm for single-source shortest
paths on a complete directed graph with $n$ vertices must use at least
$\bigl{(}\tfrac{1}{6}-o(1)\bigr{)}n^{3}$ relaxation steps.

###### Proof

Fix the sequence $\sigma$ of relaxation steps chosen by any such algorithm. We
will find an assignment of weights for the complete directed graph, such that
the distances obtained by the relaxation algorithm are not all correct until
$\bigl{(}\tfrac{1}{6}-o(1)\bigr{)}n^{3}$ relaxation steps have taken place.
Therefore, in order for the algorithm to be correct, it must make this many
steps. For the weights we choose, the shortest path tree will form a single
directed path, of $n-1$ edges, starting at the source vertex. In order for the
relaxation algorithm to achieve correct distances to all vertices, its
sequence of relaxations must include a subsequence consisting of all path
edges in order. The weights of these edges are unimportant (because we are
considering only non-adaptive algorithms) so we may set all path edges to have
weight zero and all other edges to have weight one.

To determine this path, we choose one at a time its edges in even positions:
its second, fourth, sixth, etc., edge. These chosen edges include every vertex
in the path, so choosing them will also determine the edges in odd positions.
When choosing the $i$th edge (for an even number $i$), we make the choice
greedily, to maximize the position in $\sigma$ of the step that relaxes this
edge and makes its endpoint have the correct distance. Let $s_{i}$ denote this
position, with $s_{0}=0$ as a base case recording the fact that, before we
have relaxed any edges, the source vertex already has the correct distance.
Then the length of $\sigma$ is at least equal to the telescoping sum

$(s_{2}-s_{0})+(s_{4}-s_{2})+(s_{6}-s_{4})+\cdots.$

When choosing edge $i$, for an even position $i$, there are $i-1$ earlier
vertices, whose position in the shortest path is already determined, and
$n-i+1$ remaining vertices. Between step $s_{i-2}$ and step $s_{i}$ of the
relaxation sequence $\sigma$, it must relax all $n-i+1$ edges from the last
endpoint of edge $i-2$ to one of these remaining vertices, and all
$2\tbinom{n-i+1}{2}$ edges between pairs of the vertices that remain to be
corrected. For, if it did not do so, there would be an edge that it had not
relaxed, and choosing this edge next would cause $s_{i}$ to be greater; but
this would violate the greedy choice of edge $i$ to make $s_{i}$ as large as
possible. Therefore,

$s_{i}-s_{i-2}\geq(n-i+1)+2\binom{n-i+1}{2}=(n-i+1)^{2}.$

Summing over all $\lfloor(n-1)/2\rfloor$ choices of edges in even positions
gives, as a lower bound on the total number of relaxation steps,

$\sum_{i=2,4,6,\dots}s_{i}-s_{i-2}\geq\sum_{i=2,4,6,\dots}(n-i+1)^{2}=\frac{n^{3}-n}{6},$

where the closed form for the summation follows easily by induction.

##  3 Randomized Lower Bound for Complete Graphs

It does not make much sense to consider expected time analysis for non-
adaptive algorithms, because these algorithms have a fixed stopping time
(determined as a function of the given graph), and we want their output to be
correct with high probability rather than in any expected sense. Nevertheless,
it is often easier to lower-bound the expected behavior of randomized
algorithms, by using Yao’s principle [20], according to which the expected
cost of a randomized algorithm on its worst-case input can be lower bounded by
the cost of the best deterministic algorithm against any random distribution
of inputs.

In order to convert high-probability time bounds into expectations, we
consider randomized non-adaptive algorithms that are guaranteed to produce the
correct distances, and we define the _reduced cost_ of such an algorithm to be
the number of relaxations that it performs until all distances are correct,
ignoring any remaining relaxations after that point.

###### Lemma 1

If a randomized non-adaptive relaxation algorithm $\mathcal{A}$ takes $s(G)$
steps on any weighted input graph $G$ and computes all distances from the
source vertex correctly with probability $1-o(1)$, then there exists a
randomized non-adaptive relaxation algorithm $\mathcal{B}$ that is guaranteed
to produce correct distances and whose expected reduced cost, on weighted
graphs $G$ with $n$ vertices and $m$ edges, is at most $s(G)+o(mn)$.

###### Proof

Construct algorithm $\mathcal{B}$ by using the relaxation sequence from
algorithm $\mathcal{A}$, appending onto it the sequence of relaxations from a
conventional non-adaptive deterministic Bellman–Ford algorithm. Then with
probability $1-o(1)$ the relaxed cost of $\mathcal{B}$ counts only the
relaxation sequence from algorithm $\mathcal{A}$, of length $s(G)$. With
probability $o(1)$ the relaxed cost extends into the deterministic
Bellman–Ford part of the sequence, of length $O(mn)$. Because this happens
with low probability, its contribution to the expected reduced cost is
$o(mn)$.

###### Corollary 1

Any lower bound on expected reduced cost is also a valid lower bound, up to an
additive $o(mn)$ term, on the number of relaxation steps for a randomized non-
adaptive relaxation algorithm that produces correct distances with high
probability.

With this conversion to expected values in hand, we may now formulate Yao’s
principle as it applies to our problem. We need the following notation:

###### Definition 1

For any graph $G$, with a specified source vertex, let $W_{G}$ be the family
of assignments of real weights to edges of $G$. Let $\mathcal{D}_{G}$ be the
family of probability distributions of weights in $W_{G}$, and let
$\Sigma_{G}$ be the class of relaxation sequences on $G$ that are guaranteed
to produce correct distances from the specified source vertex. For any
randomized non-adaptive relaxation algorithm $\mathcal{A}$ and weight vector
$w\in W_{G}$, let $r_{G}(\mathcal{A},w)$ denote the expected reduced cost of
running algorithm $\mathcal{A}$ on $G$ with edges weighted by $w$. For
$\sigma\in\Sigma_{G}$ and $D\in\mathcal{D}_{G}$ let $\rho_{G}(\sigma,D)$ be
the expected reduced cost of sequence $\sigma$ on weight vectors drawn from
$D$.

######  Lemma 2 (Yao’s principle)

For any graph $G$ with specified source vertex, and any randomized non-
adaptive relaxation algorithm $\mathcal{A}$,

$\min_{\mathcal{A}}\max_{w\in
W_{G}}r_{G}(\mathcal{A},w)=\max_{D\in\mathcal{D}_{G}}\min_{\sigma\in\Sigma_{G}}\rho_{G}(\sigma,D).$

###### Proof

This is just the minimax principle for zero-sum games, applied to a game in
which one player chooses a relaxation sequence $\sigma\in\Sigma_{G}$, the
other player chooses a weight vector $w\in W_{G}$, and the outcome of the game
is the reduced cost for $\sigma$ on $w$. According to that principle, the
value of the best mixed strategy for the sequence player, against its worst-
case pure strategy (the left hand side of the equality in the lemma) equals
the value of the best mixed strategy for the weight player, against its worst-
case pure strategy (the right hand side).

###### Corollary 2

For any weight distribution $D\in\mathcal{D}_{G}$,
$\min_{\sigma\in\Sigma_{G}}\rho_{G}(\sigma,D)$ is a valid lower bound on the
expected reduced cost of any randomized non-adaptive relaxation algorithm that
is guaranteed to produce correct distances.

###### Proof

An arbitrary algorithm $\mathcal{A}$ can only have a greater or equal value to
the left hand side of Lemma 2, and an arbitrary weight distribution $D$ can
only have a smaller or equal value to the right hand side. So the expected
reduced cost of the algorithm, on a worst-case input, can only be greater than
or equal to the value given for $D$ in the statement of the corollary.

###### Theorem 3.1

Any randomized non-adaptive relaxation algorithm for shortest paths on a
complete directed graph with $n$ vertices, that with high probability sets all
distances correctly, must use at least
$\bigl{(}\tfrac{1}{12}-o(1)\bigr{)}n^{3}$ relaxation steps.

###### Proof

We apply Corollary 2 to a weight distribution $D$ defined as follows: we
choose a random permutation of the vertices of the given complete graph,
starting with the source vertex, we make the weight of edges connecting
consecutive vertices in order along this permutation zero, and we make all
other weights one. Thus, each weighting of the complete graph drawn from this
distribution will have a unique shortest path tree in the form of a single
path, with all paths from the source vertex equally likely. For any weight
vector $w$ drawn from $D$, let $\pi_{w}$ be this path.

Let $\sigma$ be any relaxation sequence in $\Sigma_{D}$. As in the proof of
Theorem 2.1, we define $s_{i}$ (for a weight vector $w$ to be determined) to
be the step at which the second endpoint of the $i$th edge of $\pi_{w}$ has
its shortest path distance set correctly.

Let $C_{i}$ denote the conditional probability distribution obtained from $D$
by fixing the choice of the first $i$ edges of $\pi_{w}$. Under condition
$C_{i}$, the remaining $n-i-1$ vertices remain equally likely to be permuted
in any order. There are $2\tbinom{n-i-1}{2}$ choices for edge $i+2$, each of
which is equally likely. Therefore, the expected value of $s_{i+2}-s_{i}$ is
greater than or equal to the average, among these edges, of their distance
along sequence $\sigma$ from position $s_{i}$. (It is greater than or equal,
rather than equal, because this analysis does not take into account the
requirement that edge $i+1$ must be relaxed first, before we relax edge
$i+2$.) Sequence $\sigma$ can minimize this average if, in $\sigma$, the next
$2\tbinom{n-i-1}{2}$ relaxation steps after $s_{i}$ are exactly these distinct
edges. When $\sigma$ packs the edges in this minimizing way, the average is
$2\tbinom{n-i-1}{2}/2$; for other sequences it can only be greater. Therefore,

$E[s_{i+2}-s_{i}\mid C_{i}]\geq\binom{n-i-1}{2}.$

Summing these expected differences, over the sequence of values $s_{i}$ for
even $i$, and applying Corollary 1 and Corollary 2, gives the result.

##  4 Lower Bounds for Incomplete Graphs

In our lower bounds for complete graphs, the edges in even and odd positions
of the shortest paths perform very different functions. The edges in even
positions are the ones that, at each step in the shortest path, force the
relaxation sequence to have a large subsequence of relaxation steps.
Intuitively, this is because there are many possible choices for the edge at
the next step and all of these possibilities (in the deterministic bound) or
many of these possibilities (in the randomized bound) must be relaxed before
reaching the edge that is actually chosen. The edges in odd positions, on the
other hand, do not contribute much directly to the length of the sequence of
relaxation steps. Instead, they are used to connect the edges in the even
positions into a single shortest path.

Figure 1: Schematic view of the graphs used for our lower bound construction

To construct graphs that are not complete, for which we can prove analogous
lower bounds, we make this dichotomy more explicit. For a chosen “capacity”
parameter $c$, we will construct graphs that have two designated subsets of
$c$ vertices, $S$ and $T$ (with the source vertex contained in subset $S$). We
will connect the vertices in $T$ to the vertices in $S$ by a biregular
bipartite directed graph of some degree $d\approx m/2c$, a graph in which each
vertex in $T$ has exactly $d$ outgoing neighbors and each vertex in $S$ has
exactly $d$ incoming neighbors. This biregular graph will perform the function
of the even position edges in our complete graph lower bounds: it will have
many edges to choose from, forcing any relaxation algorithm to make a long
subsequence of relaxations between each two chosen edges. The detailed
structure of this graph is not important for our bounds. In the other
direction, from $S$ to $T$, we will construct a special graph with the
property that, no matter which sequence of disjoint edges we choose from the
biregular graph, we can complete this sequence to a path. A schematic view of
this construction is depicted in Fig. 1. We begin the more detailed
description of this structure by defining the graphs we need to connect from
$S$ to $T$. The following definition is standard:

###### Definition 2

A _rearrangeable non-blocking network_ of capacity $c$ is a directed graph $G$
with $c$ vertices labeled as inputs, and another $c$ vertices labeled as
outputs, with the following property. For all systems of pairs of inputs and
outputs that include each input and output vertex at most once, there exists
in $G$ a system of vertex-disjoint paths from the input to the output of each
pair.

###### Observation 3

A complete bipartite graph $K_{c,c}$, with its edges directed from $c$ input
vertices to $c$ output vertices, is a rearrangeable non-blocking network of
capacity $c$, with $2c$ vertices and $c^{2}$ edges. In this case, the disjoint
paths realizing any system of disjoint input-output pairs is just a matching,
formed by the edges from the input to the output in each pair.

###### Lemma 4

For any capacity $c$, there exist rearrangeable non-blocking network of
capacity $c$ with $O(c\log c)$ vertices and edges.

Pippenger [19] credits the proof of Lemma 4 to Beizer [3], who used a
recursive construction. A more recent construction of Alon and Capalbo [1] is
based on blowing up an expander graph, producing enough copies of each vertex
that a system of edge-disjoint paths in the expander can be transformed into a
system of vertex-disjoint paths in the non-blocking network. Their networks
are non-blocking in a stronger sense (the vertex-disjoint paths can be found
incrementally and efficiently), but we do not need that additional property. A
simple counting argument shows that $o(c\log c)$ edges is not possible: to
have enough subsets of edges to connect $c!$ possible systems of pairs, the
number of edges must be at least $\log_{2}c!$. For non-blocking networks with
fewer vertices and more edges we turn to an older construction of Clos [7]:

Figure 2: Three rearrangeable non-blocking networks of capacity 16. Each
network’s input vertices are in its left column and its output vertices are in
the right column. Left: Complete bipartite graph. Center: Three-stage Clos
network, with pairs of input and output vertices in consecutive stages
connected by edges rather than being identified as single vertices. Right:
Nine-stage network obtained by expanding each subunit of the center network
into a three-stage network.

######  Lemma 5 (Clos [7])

Suppose that there exists a rearrangeable non-blocking network $G_{c}$ of
capacity $c$ with $n$ vertices and $m$ edges. Then there exists a
rearrangeable non-blocking network of capacity $c^{2}$ with $3cn-2c^{2}$
vertices and $3cm$ edges.

###### Proof

Construct $3c$ copies of $G_{c}$, identified as $c$ input subunits, $c$
internal subunits, and $c$ output subunits. The input subunits have together
$c^{2}$ input vertices, which will be the inputs of the whole network.
Similarly, the output subunits have together $c^{2}$ output vertices, which
will be the outputs of the whole network. Identify each output vertex of an
input subunit with an input vertex of an internal subunit, in such a way that
each pair of these subunits has exactly one identified vertex. Similarly,
identify each output vertex of an internal subunit with an input vertex of an
output subunit, in such a way that each pair of these subunits has exactly one
identified vertex.

An example of this network, for $c=4$ and $G_{c}=K_{4,4}$, can be seen in an
expanded form as the middle network of Fig. 2. For greater legibility of the
figure, instead of identifying pairs of vertices between subunits, these pairs
have been connected by added edges. Contracting these edges would produce the
network described above.

To produce vertex-disjoint paths connecting any system of disjoint pairs of
inputs and outputs, consider these pairs as defining a multigraph connecting
the input subunits to the output subunits of the overall network. This
multigraph has maximum degree $c$ (each input or output subunit participates
in at most $c$ pairs), and we may apply a theorem of Dénes Kőnig according to
which every bipartite multigraph with maximum degree $c$ has an edge coloring
using $c$ colors [16]. These colors may be associated with the $c$ internal
subunits, and used to designate which internal subunit each path should pass
through. Once this designation is made, each subunit has its own system of
disjoint pairs of inputs and outputs through which its paths should go, and
the paths through each subunit can be completed using the assumption that it
is rearrangeable non-blocking.

###### Corollary 3

For any constant $\varepsilon>0$ and any integer $c\geq 1$, there exist
rearrangeable non-blocking networks of capacity $c$ with $O(c)$ vertices and
$O(c^{1+\varepsilon})$ edges.

###### Proof

We prove the result by induction on the integer
$i=\lceil\log_{2}1/\varepsilon\rceil$. As a base case this is true for
$\varepsilon=1$ (for which $i=0$) and for arbitrary $c$, using the complete
bipartite graph as the network. For smaller values of $\varepsilon$, apply the
induction hypothesis with the parameters $2\varepsilon$ and
$\lceil\sqrt{c}\rceil$, to produce a rearrangeable non-blocking network $N$ of
capacity $\lceil\sqrt{c}\rceil$ with $O(\sqrt{c})$ vertices and
$O(c^{1/2+\varepsilon})$ edges. Applying Lemma 5 to $N$ produces a
rearrangeable non-blocking network of capacity $\geq c$ with $O(c)$ vertices
and $O(c^{1+\varepsilon})$ edges, as desired. Deleting excess vertices to
reduce the capacity to exactly $c$ completes the induction.

###### Theorem 4.1

For any $m$ and $n$ with $n\leq m\leq 2\tbinom{n}{2}$, there exists a directed
graph on $m$ edges and $n$ vertices on which any deterministic or high-
probability randomized non-adaptive relaxation algorithm for shortest paths
must use $\Omega(mn/\log n)$ relaxation steps. When
$m=\Omega(n^{1+\varepsilon})$ for some $\varepsilon>0$, the lower bound
improves to $\Omega(mn)$.

###### Proof

We construct a graph according to the construction outlined above, in which we
choose a capacity $c$, set up two disjoint sets $S$ and $T$ of $c$ vertices,
connect $T$ to $S$ by a biregular bipartite digraph of some degree $d$, and
connect $S$ to $T$ by a rearrangeable non-blocking network of capacity $c$. We
allocate at least $m/2$ edges to the biregular graph, and the rest to the non-
blocking network, giving $d\approx m/2c$. For the $\Omega(mn/\log n)$ bound,
we use the non-blocking network of Lemma 4, with $c=\Theta(n/\log n)$. For the
$\Omega(mn)$ bound, we use the non-blocking network of Corollary 3, with
$c=\Theta(n)$. In both cases, we can choose the parameters of these networks
to achieve these asymptotic bounds without exceeding the given numbers $n$ and
$m$ of vertices and edges. We pad the resulting graph with additional vertices
and edges in order to make the numbers of vertices and edges be exactly $n$
and $m$, and set the weights of these padding edges to be high enough that
they do not interfere with the remaining construction.

Next, we choose a random distribution on weights for the resulting network so
that, for every relaxation sequence $\sigma$, the expected reduced cost of
$\sigma$, for weights from this distribution, matches the lower bound in the
statement of the lemma. For deterministic non-adaptive relaxation algorithms,
this will give the desired lower bound directly, via the simple fact that the
worst case of any distribution is always at least its expectation. For
randomized algorithms, the lower bound will follow using Corollary 1 and
Corollary 2 to convert the lower bound on expected reduced cost into a high-
probability lower bound.

As in Theorem 3.1, the random distribution on weights that we use is
determined from a random distribution on paths from the source, such that the
shortest path tree for the weighted graph will contain the chosen path. We can
accomplish this by setting the lengths of the path edges to zero and all other
edge lengths to one. Unlike in Theorem 3.1, these paths will not necessarily
include all vertices in the graph and the shortest path tree may contain other
branches. To choose a random path, we simply choose a sequence of edges in the
biregular graph, one at a time, in order along the path. In each step, we
choose uniformly at random among the subset of edges in the biregular graph
that are disjoint from already-chosen edges. Because of the biregularity of
the biregular part of our graph, each chosen edge is incident to at most
$2(d-1)$ other edges, and eliminates these other edges from being chosen
later. At least $c/2$ choices are possible before there are no more disjoint
edges, and throughout the first $c/4$ choices there will remain at least $m/4$
edges to choose from, disjoint from all previous edges. The sequence ends when
there are no more such edges to choose. Once we have chosen this sequence of
edges from the biregular graph, we construct a set of vertex-disjoint paths in
the rearrangeable nonblocking network that connects them in sequence into a
single path.

For any given relaxation sequence $\sigma$, as in the proof of Theorem 3.1,
let $\tau$ be the subsequence of edges in $\sigma$ that belong to the
biregular part of the graph, and consider a modified relaxation algorithm
that, after relaxing each edge in $\tau$, immediately relaxes all edges of the
non-blocking network. Define the reduced cost for $\tau$ to be the number of
relaxation steps made from $\tau$ before all distances are correct, not
counting the relaxation steps in the non-blocking network. Clearly, this is at
most equal to the reduced cost for $\sigma$, because $\sigma$ might fail to
relax a path in the non-blocking network when $\tau$ succeeds, causing the
computation of shortest path distances using $\sigma$ to fall behind that for
$\tau$. Define $t_{i}$ to be the step in the relaxation sequence for $\tau$
that relaxes the $i$th chosen edge from the biregular graph, making the
distance to its ending vertex correct. Then the expectation of $t_{i}-t_{i-1}$
(conditioned on the choice of the first $i-1$ edges is at least the average,
over all edges that were available to be chosen as the $i$th edge, of the
number of steps along $\tau$ from $t_{i-1}$ to the next occurrence of that
edge. This expectation is minimized when the edges occurring immediately
following position $t_{i-1}$ in $\tau$ are exactly the next available edges,
and is equal to half the number of available edges; for other possibilities
for $\tau$, the expectation can only be even larger. The expected reduced cost
for $\tau$ equals the sum of these differences $t_{i}-t_{i-1}$. Since there
are $\Omega(c)$ steps in which the number of available edges is $\Omega(m)$,
the expected reduced cost for $\tau$ is $\Omega(cm)$. The expected reduced
cost for $\sigma$ can only be larger, and plugging in the value of $c$ (coming
from our choice of which type of non-blocking network to use) gives the
result.

##  5 Conclusions and Open Problems

We have shown that, for a wide range of choices for $m$ and $n$, the
Bellman–Ford algorithm is asymptotically optimal among non-adaptive relaxation
algorithms. Adaptive versions of the Bellman–Ford algorithm are faster, but
only by constant factors. Is it possible to prove that, among adaptive
relaxation algorithms, Bellman–Ford is optimal? Doing so would require a
careful specification of what information about the results of relaxation
steps can be used in choosing how to adapt the relaxation sequence.

The constant factors of $\tfrac{1}{6}$ and $\tfrac{1}{12}$ in our
deterministic and randomized lower bounds for complete graphs are far from the
constant factors of $\tfrac{1}{2}$ and $\tfrac{1}{3}$ in the corresponding
upper bounds. Can these gaps be tightened? Is it possible to make them tight
enough to distinguish deterministic and randomized complexity? Alternatively,
is it possible to improve the deterministic methods to match the known
randomized upper bound?

For sparse graphs ($m=O(n)$), our lower bound falls short of the Bellman–Ford
upper bound by a logarithmic factor. Can the lower bound in this range be
improved, or can the Bellman–Ford algorithm for sparse graphs be improved?

In this work, we considered the worst-case number of relaxation steps used by
non-adaptive relaxation algorithms for the parameters $m$ and $n$. But it is
also natural to look at this complexity for individual graphs, with unknown
weights. For any given graph, there is some relaxation sequence that is
guaranteed to find shortest path distances for all weightings of that graph,
with as few relaxation steps as possible. An algorithm of Haddad and Schäffer
[12] can find such a sequence for the special case of graphs for which it is
as short as possible, one relaxation per edge. What is the complexity of
finding or approximating it more generally?

## Acknowledgements

This research was supported in part by NSF grant CCF-2212129.

## References

  * [1] Noga Alon and Michael R. Capalbo.  Finding disjoint paths in expanders deterministically and online.  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20–23, 2007, Providence, RI, USA, Proceedings, pages 518–524. IEEE Computer Society, 2007.  doi:10.1109/FOCS.2007.19.
  * [2] Michael J. Bannister and David Eppstein.  Randomized speedup of the Bellman–Ford algorithm.  In Conrado Martínez and Hsien-Kuei Hwang, editors, Proceedings of the 9th Meeting on Analytic Algorithmics and Combinatorics, ANALCO 2012, Kyoto, Japan, January 16, 2012, pages 41–47. SIAM, 2012.  doi:10.1137/1.9781611973020.6.
  * [3] B. Beizer.  The analysis and synthesis of signal switching networks.  In Proceedings of the Symposium on Mathematical Theory of Automata, New York, April 1962, pages 563–572. Polytechnic Press of the Polytechnic Institute of Brooklyn, 1962.
  * [4] Richard Bellman.  On a routing problem.  Quarterly of Applied Mathematics, 16:87–90, 1958.  doi:10.1090/qam/102435.
  * [5] Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen.  Negative-weight single-source shortest paths in near-linear time.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 – November 3, 2022, pages 600–611. IEEE, 2022.  doi:10.1109/FOCS54457.2022.00063.
  * [6] Gang Cheng and Nirwan Ansari.  Finding all hops shortest paths.  IEEE Communications Letters, 8(2):122–124, 2004.  doi:10.1109/LCOMM.2004.823365.
  * [7] Charles Clos.  A study of non-blocking switching networks.  Bell System Technical Journal, 32(2):406–424, March 1953.  doi:10.1002/j.1538-7305.1953.tb01433.x.
  * [8] Narsingh Deo and Chi Yin Pang.  Shortest-path algorithms: taxonomy and annotation.  Networks, 14(2):275–323, 1984.  doi:10.1002/net.3230140208.
  * [9] Robert B. Dial.  Algorithm 360: Shortest-path forest with topological ordering [H].  Communications of the ACM, 12(11):632–633, 1969.  doi:10.1145/363269.363610.
  * [10] L. R. Ford, Jr. and D. R. Fulkerson.  A shortest chain algorithm.  In Flows in Networks, pages 130–134. Princeton University Press, 1962.
  * [11] Roch Guérin and Ariel Orda.  Computing shortest paths for any number of hops.  IEEE/ACM Transactions on Networkin, 10(5):613–620, 2002.  doi:10.1109/TNET.2002.803917.
  * [12] Ramsey W. Haddad and Alejandro A. Schäffer.  Recognizing Bellman–Ford-orderable graphs.  SIAM Journal on Discrete Mathematics, 1(4):447–471, 1988.  doi:10.1137/0401045.
  * [13] Charles Hedrick.  Routing Information Protocol.  Request for Comments, RFC 1058. Network Working Group, June 1988.  URL: https://www.rfc-editor.org/rfc/rfc1058.
  * [14] Stasys Jukna and Georg Schnitger.  On the optimality of Bellman-Ford-Moore shortest path algorithm.  Theoretical Computer Science, 628:101–109, 2016.  doi:10.1016/j.tcs.2016.03.014.
  * [15] Tomasz Kociumaka and Adam Polak.  Bellman–Ford is optimal for shortest hop-bounded paths.  Electronic preprint arxiv:2211.07325, February 14 2023.
  * [16] Dénes Kőnig.  Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre.  Mathematische Annalen, 77:453–465, 1916.  doi:10.1007/BF01456961.
  * [17] Ulrich Meyer, Andrei Negoescu, and Volker Weichert.  New bounds for old algorithms: on the average-case behavior of classic single-source shortest-paths approaches.  In Alberto Marchetti-Spaccamela and Michael Segal, editors, Theory and Practice of Algorithms in (Computer) Systems – First International ICST Conference, TAPAS 2011, Rome, Italy, April 18–20, 2011. Proceedings, volume 6595 of Lecture Notes in Computer Science, pages 217–228. Springer, 2011.  doi:10.1007/978-3-642-19754-3_22.
  * [18] Edward F. Moore.  The shortest path through a maze.  In Proc. Internat. Sympos. Switching Theory 1957, Part II, pages 285–292. Harvard Univ. Press, Cambridge, Mass., 1959.
  * [19] Nicholas Pippenger.  On rearrangeable and non-blocking switching networks.  Journal of Computer and System Sciences, 17(2):145–162, 1978\.  doi:10.1016/0022-0000(78)90001-6.
  * [20] Andrew Chi-Chih Yao.  Probabilistic computations: toward a unified measure of complexity.  In 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October – 1 November 1977, pages 222–227. IEEE Computer Society, 1977.  doi:10.1109/SFCS.1977.24.
  * [21] Jin Y. Yen.  Shortest Path Network Problems, volume 18 of Mathematical Systems in Economics.  Verlag Anton Hain, Meisenheim am Glan, 1975.


# Power spectrum of primordial perturbations during ultra-slow-roll inflation
with back reaction effects

Shu-Lin Cheng1<EMAIL_ADDRESS>Da-Shin Lee2<EMAIL_ADDRESS>Kin-Wang Ng1,3<EMAIL_ADDRESS>1Institute of Physics, Academia Sinica,
Taipei 11529, Taiwan, R.O.C.  2Department of Physics, National Dong Hwa
University, Hualien 97401, Taiwan, R.O.C.  3Institute of Astronomy and
Astrophysics, Academia Sinica, Taipei 11529, Taiwan, R.O.C.

###### Abstract

We develop a nonperturbative method through the Hartree factorization to
examine the quantum fluctuation effects on the single-field inflationary
models in a spatially flat FRW cosmological space-time. Apart from the
background field equation as well as the Friedmann equation with the
corrections of quantum field fluctuations, the modified Mukhanov-Sasaki
equations for the mode functions of the quantum scalar field are also derived
by introducing the nonzero $\Delta_{B}$ term. We consider the Universe
undergoing the slow roll (SR)-ultra slow roll (USR) -slow roll (SR) inflation
where in particular the presence of the USR inflation triggers the huge growth
of $\Delta_{B}$ that in turn gives the boost effects to the curvature
perturbations for the modes that leave horizon in the early times of the
inflation. However, the cosmic friction term in the mode equation given by the
Hubble parameter presumably prohibits the boost effects. Here we propose two
representative models to illustrate these two competing terms.

##  I Introduction

Inflation is the leading paradigm that prevails in the evolution of the early
universe. During the stage of primordial acceleration, vacuum fluctuations of
the gravitational and matter fields are amplified to the cosmological scales,
giving the approximately scale invariant spectrum of small density
fluctuations on large scales, which are ultimately responsible for the CMB
anisotropies and the large scale structure of our Universe KT .

The recent detection of one of the gravitational wave events is speculated due
to the merging of two 30 $M_{\odot}$ black holes, which might be primordial
black holes (PBHs), resulting in LIGO coalescences ABB . In addition, PBHs
could comprise a considerable fraction of the dark matter, and thus leave
imprints throughout the history of the Universe CAR ; MES ; CAR1  (see Ref.
SAS  for a review). There has been increasing interest in the possibility of
breaking scale invariance on small scales with a spike in the power spectrum,
resulting in structures such as PBHs. The models include trapped inflation
CHENG , Higgs inflation EZQcrit , double inflation KAN , radiative plateau
inflation BAL  or some string realizations CLN ; CIC ; OZS ; DAL , to cite a
few. To generate a spike in the power spectrum, the inflation scenario must
deviate from the slow-roll (SR) regime that typically gives the scale
invariant power spectrum. Ultra-slow-roll (USR) inflation has been proposed as
a transient phase of single-field inflation KIN ; MAR ; CHE ; BYR .
Nevertheless, in this scenario the very small inflaton velocity will be
significantly influenced by quantum kicks, giving its fluctuations comparable
to the mean value. A natural framework to involve quantum kicks is through the
stochastic inflation STA . Several works FIR ; PAT ; BIA ; EZQ  have been
devoted to the study of this quantum noise effects and find a significant
boost of PBH production.

Alternatively, the quantum fluctuation effects arising from the inflaton field
itself to the curvature perturbations through the quantum loop calculations
are considered in Ref. boyan1 . It is known that in the case of minimally
coupled massless inflaton fluctuations in de Sitter space-time they suffer
from the infrared divergence fordbunch . During the SR inflation where our
Universe is in approximately de Sitter space-time, the resulting scale
invariant power spectrum introduces the strong infrared enhancement of the
one-loop corrections in $\langle\varphi^{2}\rangle$ given by the inflation
field fluctuations $\varphi$ to be defined in the text later that in turn
induce sizable effects to the slow roll parameters. Then the study is to
extend to the USR inflation as a transition phase. In particular, when the
Universe goes from the USR to SR regimes, there exists the accompanying large
value of $\langle\varphi^{2}\rangle$ due to the combined effects of the strong
infrared enhancement and the spike in the power spectrum weican . In this
work, we will adopt the approach to taking into account the quantum field
fluctuations $\langle\varphi^{2}\rangle$ self-consistently by implementing the
Hartree factorization. We then introduce two models when with no inclusion of
$\langle\varphi^{2}\rangle$ they are consistent with the observations. We plan
to adopt the method developed here to see whether or not the quantum field
fluctuations will give sizable effects in each of the models.

Our presentation is organized as follows. In next section, we introduce the
single-field inflationary models in a metric of the perturbed spatially flat
Friedmann-Robertson-Walker (FRW) cosmological space-time starting from the
Arnowitt-Deser-Misner (ADM) form by following weican . We then separate the
classical homogeneous background field ($\Phi_{0}$) from the quantum field
fluctuations ($\varphi$). The background field in the FRW metric with the
quantum loop corrections through $\langle\varphi^{2}\rangle$ is derived
whereas the scale factor follows the modified Friedmann equations also
including the loop contributions. The equations of motion for the mode
functions of $\varphi$ can be derived from the quadratic terms of the field
$\varphi$ in the Lagrangian density as in weican  where in this work we
further implement the Hartree factorization for self-consistently taking into
account $\langle\varphi^{2}\rangle$. The power spectrum of primordial
perturbations in a spatially flat gauge can be expressed in terms of the mode
functions. In Sec. III, we introduce two models for the Universe undergoing
the SR-USR-SR inflation to compute the power spectrum of the curvature
perturbations, with which to further examine the effects of quantum field
fluctuations to the power spectrum. Concluding remarks and discussions are in
Sec. IV.

##  II Single-field inflation model

We consider the inflation model given by

$\displaystyle S=$ $\displaystyle S_{g}+S_{\phi}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\int d^{4}x\sqrt{-g}R+\int
d^{4}x\sqrt{-g}\Bigg{[}-\frac{1}{2}\;\partial_{\mu}\phi\,\partial^{\mu}\phi-V(\phi)\Bigg{]}\;$
(1)

with $M_{Pl}^{-2}=8\pi G_{N}$ set to be $M_{Pl}^{-2}=1$, which will be
restored if necessary. One shall start from the metric in the Arnowitt-Deser-
Misner (ADM) form in the $3+1$ decomposition with ${\cal N}$ the lapse
function and ${\cal N}^{i}$ the shift-vector as well as the 3 spatial
dimensions metric $h_{ij}$ clu ; kaz ; weican . In particular, for a spatially
flat Friedmann-Robertson-Walker (FRW) cosmological space-time ${\cal N}=1$,
${\cal N}_{i}=0$, and $h_{ij}=a^{2}(t)\delta_{ij}$ where $a$ is a scale
factor. In the ADM formalism, $h_{ij}$ and $\phi$ are dynamical variables
whereas ${\cal N}$ and ${\cal N}_{i}$ are Lagrangian multipliers due to the
Hamiltonian and momentum constraints. In the course of inflation, we consider
the homogeneous mean field $\Phi_{0}$ and the quantum fluctuations around it
$\varphi(\vec{x},t)$ defined as

$\phi(\vec{x},t)=\Phi_{0}(t)+\varphi(\vec{x},t)\;,$ (2)

with

$\langle\varphi(\vec{x},t)\rangle=0\;.$ (3)

The expectation value is given by the non-equilibrium quantum state that later
will be specified to be the Bunch-Davies state often studied in the
literature. It is found more convenient to work in the spatially flat gauge by
writing ${\cal N}=1+\delta{\cal N}$ where $\delta{\cal N},{\cal N}_{i}$, and
$\varphi$ are perturbed fields. Notice that $\delta{\cal N}$ and ${\cal
N}_{i}$ are all suppressed not only by $1/M^{2}_{Pl}$ but also due to the
smallness of $\dot{\Phi}_{0}$ during both SR or USR inflations, and they are

$\delta{\cal N}\propto\sqrt{\epsilon}\,,\quad\quad\quad{\cal
N}_{i}\propto\sqrt{\epsilon}\,.$ (4)

Henceforth, $\delta{\cal N}$ and ${\cal N}_{i}$ can be ignored as compared
with loop effects from quantum scalar field of the order of the power spectrum
of the curvature perturbations $\propto H/(M_{Pl}\sqrt{\epsilon})$ where $H$
is the Hubble parameter and $\epsilon$ is the Hubble flow parameter being
small during the USR and SR inflations weican . The tadpole method (see Ref.
boyan3  and references therein) then is implemented to derive the equation of
motion with the loop corrections for the homogeneous expectation value of the
inflaton field from the action (II) by requiring the condition
$\langle\varphi(\vec{x},t)\rangle=0$:

$\ddot{\Phi}_{0}+3\,H\,\dot{\Phi}_{0}+V^{\prime}(\Phi_{0})+\frac{1}{2}V^{\prime\prime\prime}(\Phi_{0})\,\langle\varphi^{2}(\vec{x},t)\rangle=0\,,$
(5)

where the dot means the time derivative of the cosmic time $t$. The Hubble
parameter $H$ obtained from the Hamiltonian constraint with ${\cal N}=1$,
${\cal N}_{i}=0$ and $h_{ij}=a^{2}\delta_{ij}$ giving the Friedmann equation
becomes weican

$\displaystyle H^{2}$
$\displaystyle=\frac{1}{3M^{2}_{Pl}}\bigg{\langle}\frac{1}{2}{\dot{\phi}^{2}}+\frac{\partial_{i}\phi\partial_{i}\phi}{2a^{2}}+V(\phi)\bigg{\rangle}$
(6)
$\displaystyle=\frac{1}{3M^{2}_{Pl}}\Big{(}\frac{1}{2}{{\dot{\Phi}_{0}}}^{2}+V(\Phi_{0})\Big{)}+\frac{1}{3M^{2}_{Pl}}\bigg{\langle}\frac{1}{2}{\dot{\varphi}}^{2}+\frac{\partial_{i}\varphi\partial_{i}\varphi}{2a^{2}}+\frac{1}{2}V^{\prime\prime}(\Phi_{0})\varphi^{2}+\cdot\cdot\cdot\bigg{\rangle}$
$\displaystyle=H_{0}^{2}+\delta H^{2}\,,$

where

$H_{0}^{2}=\frac{1}{3M^{2}_{Pl}}\Big{(}\frac{1}{2}{\dot{\Phi_{0}}}^{2}+V(\Phi_{0})\Big{)}\,,$
(7)

and the loop correction to the Hubble parameter $\delta H^{2}$ is given by

$\delta
H^{2}=\frac{1}{3M^{2}_{Pl}}\bigg{\langle}\frac{1}{2}{\dot{\varphi}}^{2}+\frac{\partial_{i}\varphi\partial_{i}\varphi}{2a^{2}}+\frac{1}{2}V^{\prime\prime}(\Phi_{0})\varphi^{2}\bigg{\rangle}\,.$
(8)

Additionally, the spatial Fourier transform of the field operator
$\varphi_{k}$ obeys the mode equations, which can be read off from the
quadratic terms of $\varphi$ in the Lagrangian density (II) with the further
Hartree factorization approximation, namely $\varphi^{4}\rightarrow
6\langle\varphi^{2}\rangle\varphi^{2}$, as clu ; kaz ; weican

$\ddot{\varphi_{k}}+3H\dot{\varphi_{k}}+\left[\frac{k^{2}}{a^{2}}+V^{\prime\prime}(\Phi_{0})-\frac{1}{a^{3}M_{P}^{2}}\frac{d}{dt}\left(\frac{a^{3}\dot{\Phi_{0}}^{2}}{H}\right){+\frac{1}{2}V^{[4]}(\Phi_{0})\,\langle\varphi^{2}\rangle}\right]\varphi_{k}=0.$
(9)

However, $\langle\varphi^{2}\rangle$ has the usual ultraviolet divergence in
the loop momentum integral that can be removed by a proper procedure of
regularization/renormalization by defining the renormalized counterpart. In
the case of minimally coupled massless inflaton fluctuations in de Sitter
space-time, it also suffers from the infrared divergence fordbunch . In Ref.
boyan1 , its infrared enhancement giving sizable effects to the slow roll
parameters is studied. Later the infrared enhancement is also explored in the
USR inflation weican . In this work, we self-consistently incorporate
$\langle\varphi^{2}\rangle$ into the dynamics where in particular the infrared
momentum modes $(k\leq H)$ are taken into account by introducing the momentum
cutoff $\Lambda=H$ in the momentum integration.

Next, the Hubble flow parameters are defined as

$\epsilon=-\frac{\dot{H}}{H^{2}},\quad\eta=\frac{\dot{\epsilon}}{\epsilon H}.$
(10)

We can re-write Eq. (9) in terms of
$\zeta_{k}=\delta\varphi_{k}/(\sqrt{2\epsilon})$ as

$\ddot{\zeta_{k}}+\left(3+\eta\right)H\dot{\zeta_{k}}+\left[\frac{k^{2}}{a^{2}}+\Delta_{B}\right]\zeta_{k}=0,$
(11)

where

$\displaystyle\Delta_{B}$ $\displaystyle=$
$\displaystyle\Delta_{B0}+{V^{[4]}(\Phi_{0})\,\langle\zeta^{2}\rangle\,\epsilon}$
$\displaystyle\Delta_{B0}$ $\displaystyle=$ $\displaystyle
V^{\prime\prime}[\Phi_{0}]-\frac{1}{a^{3}M_{P}^{2}}\frac{d}{dt}\left(\frac{a^{3}\dot{\Phi}_{0}^{2}}{H}\right)+\frac{H}{2}\dot{\eta}-\frac{H^{2}}{4}\eta^{2}+\frac{3H^{2}}{2}\eta.$
(12)

Notice that ignoring the quantum fluctuations corrections
$\langle\varphi^{2}\rangle$ or $\langle\zeta^{2}\rangle$ of the redefined
variable in $\Delta_{B}$ above, $\Delta_{B}\rightarrow\Delta_{B0}$. Then,
using the equation of motion for $\Phi_{0}$ again by neglecting the
contributions from quantum fluctuations in (5) as well as the Friedmann
equation for $H_{0}$ (7) that the dynamics of the background fields are taken
into account only lead to $\Delta_{B0}=0$. Then, the equation of motion for
$\zeta$ in (11) reduces to the known Mukhanov-Sasaki equation msvar .
Nevertheless, including the quantum fluctuations will give the nonzero
$\Delta_{B}$ in (12) with the contributions from the nonzero $\Delta_{B0}$ via
(5) and (6), which implicitly have the quantum fluctuation corrections, and
also from the term of $V^{[4]}(\Phi_{0})\,\langle\zeta^{2}\rangle\,\epsilon$.
Thus, $\Delta_{B}\neq 0$ becomes the indicator, giving the effects from the
quantum fluctuations to the curvature perturbation to be discussed later. Here
the initial conditions for $\zeta_{k}$ are chosen to be the standard Bunch-
Davies vacuum states. For the early times $|k\tau|\gg 1$ where $\tau$ is the
conformal time, $d\tau=dt/a$, the mode functions behave the same as free-field
modes in the Minkowski space-time, i.e.,

$\zeta_{k}\to\frac{1}{\sqrt{2k}}e^{-ik\tau}\frac{1}{a\sqrt{2\epsilon}}.$ (13)

As such the power spectrum of the curvature perturbation is given by

$\Delta^{2}_{\zeta_{k}}=\frac{k^{3}}{2\pi^{2}}\left|\zeta_{k}\right|^{2}.$
(14)

When ignoring $\langle\varphi^{2}\rangle$, for small $\epsilon$ and $|\eta|$,
the Hubble parameter $H$ is approximately a constant where the scale factor is
$a=e^{H_{0}t}=-1/(H_{0}\tau)$ in a era of de Sitter spacetime, and Eq. (11)
has a simple analytic solution,

$\zeta_{k}=\frac{\pi^{1/2}H_{0}}{2k^{3/2}}\frac{1}{\sqrt{2\epsilon}}(-k\tau)^{3/2}H^{(1)}_{3/2}(-k\tau),$
(15)

giving the power spectrum of the curvature perturbations

$\Delta^{2}_{\zeta_{k}}=\frac{H_{0}^{2}}{8\pi^{2}\epsilon}\,.$ (16)

In fact, in the theory of quantum fields in curved spacetime, there is no
unique choice of a vacuum state. In this article we focus on the standard
choice often adopted in the literature, which allows us to include the quantum
corrections into the standard results in the literature. A study of quantum
loop corrections with different initial states is an important aspect that
deserves further study. In the next section, we will study the effects of the
back reaction of $\langle\varphi^{2}\rangle$ to the curvature perturbations.

##  III quantum fluctuations in SR-USR-SR inflation

In this section, we calculate the power spectrum of the curvature perturbation
numerically. We utilize the inflation models with an inflection point that
will generate a large spike in the power spectrum as the source for the
production of PBHs. Here we provide two models where if we ignore the effects
of quantum fluctuations effects, the amplitude of the power spectrum of the
curvature perturbation as well as the levels of the scalar spectral index, the
tensor-to-scalar ratio, and the scalar spectral index running on large
cosmological scales are all consistent with the Planck measurements:
$\Delta_{\zeta_{k}}^{2}\simeq 2.4\times 10^{-9}$, $n_{s}\simeq 0.97$,
$r<0.06$, and $|dn_{s}/d\ln k|<0.013$ planckinflation ; bk18 . Using the
Hartree factorization to self-consistently take into account quantum field
fluctuations, we examine the backreaction effects of
$\langle\varphi^{2}\rangle$ to the dynamics.

###  III.1 Model 1

The first model potential $V(\phi)$ is parametrized as

$V(\phi)=V_{0}\left(1+c_{1}\frac{\phi}{\Lambda}+\frac{c_{2}}{2}\frac{\phi^{2}}{\Lambda^{2}}+\frac{c_{3}}{3!}\frac{\phi^{3}}{\Lambda^{3}}+\frac{c_{4}}{4!}\frac{\phi^{4}}{\Lambda^{4}}+\frac{c_{5}}{5!}\frac{\phi^{5}}{\Lambda^{5}}\right),$
(17)

with

$\displaystyle c_{\Lambda}=0.3,\quad V_{0}={1.0}\times 10^{-14},$
$\displaystyle c_{1}={-0.7276}\times
10^{-4},\;c_{3}=-0.52,\;c_{4}=1.0,\;c_{5}=-0.6407.$ (18)

The typical profile of the $V(\varphi)$ is depicted in Fig. 1.

Figure 1: The inflaton potential $V(\phi)$ in Eq. (17), normalized by $V_{0}$.
All dynamical variables in this figure and in the following figures are
rescaled by the reduced Planck mass, $M_{p}=2.435\times 10^{18}$ GeV.  Figure
2: Evolution of $H$ (dashed line) and $\phi$ (solid line) against e-folds $N$,
with $H_{i}=7.65\times 10^{-8}$, $\Phi_{0i}=8.42\times 10^{-4}$, and
${\dot{\Phi}}_{0i}=1.43\times 10^{-11}$. Note that the inflation ends at
$N\sim 60$. Figure 3: Evolution of $\log(\epsilon/\epsilon_{i})$ (dashed line)
and $\eta$ (solid line) against e-folds $N$, where $\epsilon_{i}$ is the
initial value of $\epsilon$. Figure 4: Evolution of
$\left|\zeta_{k}\right|^{2}$ without back reaction (blue dashed line) and with
back reaction (red solid line) against e-folds $N$, where $k/k_{i}=10^{4}$ and
$k_{i}=H_{i}$. Figure 5: Evolution of $|\dot{\zeta}_{k}|^{2}$ without back
reaction (blue dashed line) and with back reaction (red solid line) against
e-folds $N$, where $k/k_{i}=10^{4}$ and $k_{i}=H_{i}$. Figure 6: Evolution of
$\Delta_{B}$ against e-folds $N$. Figure 7: Power spectrum of the curvature
perturbation $\Delta_{\zeta_{k}}$ without back reaction (blue dashed line),
with back reaction (red solid line), and from the analytic result in Eq. (16)
evaluated at the horizon-crossing time for each k-mode (black thin solid line)
against e-folds $N$.

By taking account of the quantum fluctuation effects, the solutions for the
mean field $\Phi_{0}$, the Hubble parameter $H$ and the modes of quantum field
fluctuations $\zeta_{k}$ can be found by self-consistently solving the
background field equations in (5), and the Friedmann equation (6) with the
loop corrections, together with the mode equations (11) that also include the
contributions from the quantum field fluctuations themselves. The initial
conditions of the mean field are set to be $\Phi_{0i}=8.4\times 10^{-4}$ and
${\dot{\Phi}}_{0i}=1.43\times 10^{-11}$ and those of the mode functions are
the standard Bunch-Davies vacuum states. The evolution of the mean field
$\Phi_{0}$ and Hubble parameter $H$ is shown in Fig. 2 against the number of
e-folds after the beginning of inflation defined by
$N=\int^{t}_{0}H\left(t^{\prime}\right)dt^{\prime}$. According to (10), the
Hubble flow parameters $\epsilon$ and $\eta$ are drawn in Fig. 3. It turns out
that the mean field $\Phi_{0}$ starts at $\Phi_{0i}\sim 10^{-4}$, and slowly
rolls down the potential hill in Fig. 1 to $\Phi_{0}\sim 0.1$ in $N\sim 0-33$
where the Universe is in the slow-roll regime with small values of $\epsilon$
and $\eta$. Then, the slope of the potential profile drives the mean field
quickly settling into another phase of the ultra-slow regime where $\Phi_{0}$
is sitting around the inflection point of the effective potential at
$\Phi_{0}\sim 0.9$ also seen in Fig. 2. There exists a sharp SR to USR
transition at $N\sim 33$ in Fig. 3 where a relatively large change in
$\epsilon$ results in the change in the value of $\eta$ to $\eta\sim-7$ at
$N\sim 33$, entering the new phase of the USR with the ignorable acceleration
of the dynamics of the mean field. The USR lasts within $N\sim 33-40$ when
$|\eta|$ remains relatively large. Later, the value $|\eta|$ decreases and
$\eta$ becomes positive. This in turn increases the value of $\epsilon$ and
brings the phase back to the SR regime. Finally, the inflation phase has a
exit at $N\sim 60$.

It is also found that although in the course of the Universe inflation and in
the models of interest, the backreaction of $\langle\varphi^{2}\rangle$ does
not play a significant role in the evolution of the background fields.
Instead, they indeed give visible effects in the mode functions $\zeta_{k}$
for relatively small $k$ modes, which will affect the power spectrum of the
curvature perturbations for superhorizon modes. The numerical results of
$\left|\zeta_{k}\right|^{2}$ and $|\dot{\zeta}_{k}|^{2}$ as a function of $N$
are displayed in Figs. 4 and 5 respectively with a Fourier mode
$k/k_{i}=10^{4}$ for illustration. They are the relatively small $k$ modes
with $k_{i}$ and $k$ corresponding to the modes crossing out of the horizon at
the start of the inflation and at the early time ${N\sim 8}$, respectively. We
find the large boost effect due to quantum fluctuations to the mode function
$\zeta_{k}$, starting from $N\sim 40$ onwards until the end of the inflation
at $N\sim 60$. This deviation can be ascribed to the nonzero $\Delta_{B}$ in
the mode equations (11) where $\Delta_{B}=0$ when ignoring quantum
fluctuations. As shown in Fig. 6, the value of $|\Delta_{B}|$ starts to grow
from the onset of the inflation, drops its value at the SR-USR transition. It
then hugely regrows after entering the USR phase with its effects to trigger
the boost in the mode functions $\zeta_{k}$ until the end of the inflation
while the Hubble parameter serving as the cosmic friction effect is not large
enough to hinder the boost. Given the equations for $\zeta_{k}$ in (11),
evidently two competing factors, which are the growth of $\Delta_{B}$ solely
due to the quantum field fluctuations and the cosmic friction given by the
Hubble parameter $H$, will determine whether or not the backreaction effects
are visible in the model of interest. In the first model above, the boost
effects occur for the modes $k/k_{i}\lesssim 10^{11}$, which satisfy
$k^{2}/a^{2}\ll|\Delta_{B}|$ at $N=60$ in order to receive the significant
effects from the nonzero $\Delta_{B}$ seen in the mode equations (11). What we
learn is as follows. The need of the USR inflation is to generate the large
enough fluctuations at relevant scales becoming the potential sources of the
primordial black hole production. Nevertheless, the created fluctuations will
backreact the dynamics of the mode functions if they are treated self-
consistently as in our approach. This results in the sizable boost effects in
particular on the small $k$ modes. As a consequence, Fig. 7 shows the power
spectrum of the curvature perturbation $\Delta_{\zeta_{k}}$ with (red solid
line) and without (blue dashed line) backreaction effects due to quantum
fluctuations. This is one of the main results in our work. As expected, the
backreaction effects will induce noticeable deviation in small $k$ modes in
particular when the Universe has the USR inflation. The range of such low-$k$
modes self-consistently depends on the value of $\Delta_{B}$ solely given by
quantum fluctuations. In the second model we propose in this paper, the Hubble
parameter can be sufficiently large so that the boost effects driven by the
quantum fluctuations turn out to be insignificant.

###  III.2 Model 2

The second model we propose to study is parametrized as EZQ

$V(\phi)=\frac{\lambda}{12}\phi^{2}\nu^{2}\frac{6-4a\frac{\phi}{\nu}+3\frac{\phi^{2}}{\nu^{2}}}{\big{[}1+b\frac{\phi^{2}}{\nu^{2}}\big{]}^{2}},$
(19)

where

$\displaystyle{\lambda=1.86\times 10^{-6},\quad\nu=0.196,\quad a=0.7071,\quad
b=1.5\,,}$ (20)

and the corresponding potential profile is shown in Fig. 8. To start from the
SR inflation, the initial conditions for the mean field are chosen to be
$\Phi_{0i}=2.41$ and $\dot{\Phi}_{0i}=-2.86\times 10^{-7}$ and with the
parameters above in the model the Hubble parameter $H_{i}=9.71571\times
10^{-6}$. Again, without inclusion of the backreaction effects, the use of the
chosen parameters can successfully interpret the observations planckinflation
; bk18 . Applying the nonperturbative approach we develop can examine the
quantum field fluctuation effects. The evolution of the background field
$\Phi_{0}$ and the Hubble parameter are shown in Fig. 9 although the inclusion
of $\langle\zeta^{2}\rangle$ just gives the insignificant change in their
evolution as in model 1. The evolution of the Hubble flow parameters is also
depicted in Fig. 10 where the SR inflation starts from $N=0$ and ends at
$N\sim 60$. As in model 1, there exists the SR-USR-SR transition and thus
$\Delta_{B}$ evolves similarly as shown in Fig. 11, which in particular
largely regrows during the transition period, potentially giving the boost to
$\zeta_{k}$. However, in model 2, the Hubble parameter is sufficiently large
to prohibit the growth in $\zeta_{k}$ for all modes, resulting in the minute
effects from the quantum field fluctuations to $\Delta_{\zeta_{k}}$ shown in
Fig. 12. In this work, we provide a self-consistent method to incorporate the
quantum field fluctuations, which is a necessity to examine the backreaction
effects from them. We will leave the study to find out in a given model the
critical value of the Hubble parameter and its time-dependent behavior, below
which the corrections from the quantum field fluctuations become of importance
to our future work.

Figure 8: The inflaton potential $V(\phi)$ in Eq. (19) for model 2 and
$V_{0}=V(\Phi_{0i})$. All dynamical variables in this figure and in the
following figures are rescaled by the reduced Planck mass, $M_{p}=2.435\times
10^{18}$ GeV.  Figure 9: Evolution of $H$ (dashed line) and $\phi$ (solid
line) against e-folds $N$, with $H_{i}=9.72\times 10^{-6}$, $\Phi_{0i}=2.41$,
and ${\dot{\Phi}}_{i}=-2.86\times 10^{-7}$ for model 2. Note that the
inflation ends at $N\sim 60$. Figure 10: Evolution of
$\log(\epsilon/\epsilon_{i})$ (dashed line) and $\eta$ (solid line) against
e-folds $N$ for model 2, where $\epsilon_{i}$ is the initial value of
$\epsilon$. Figure 11: Evolution of $\Delta_{B}$ against e-folds $N$ for model
2. Figure 12: Power spectrum of the curvature perturbation
$\Delta_{\zeta_{k}}$ without back reaction (blue dashed line), with back
reaction (red solid line), and from the analytic result in Eq. (16) evaluated
at the horizon-crossing time for each k-mode (black thin solid line) against
e-folds $N$ for model 2. The dashed and solid curves overlap each other.

##  IV summary and looking ahead

In this work, we develop a nonperturbative method to examine the quantum
fluctuation effects on the single-field inflationary models in a spatially
flat FRW cosmological space-time. We mainly follow the work of weican
starting from the metric of the perturbed spatially flat FRW cosmological
space-time in the ADM form, and then separate the classical homogeneous
background field $\Phi_{0}$ from the quantum field fluctuations $\varphi$. In
a spatially flat gauge, the equation of motion for the background field in the
FRW metric as well as the modified Friedmann equation of the scale factor with
quantum fluctuation corrections are derived. We adopt the Hartree
factorization and treat the quantum field fluctuations
$\langle\varphi^{2}\rangle$ in a self-consistent manner in which the the
equations of motion for mode functions of the quantum field $\varphi$ are also
derived. In there the new variable $\Delta_{B}$ depending on not only the
background field $\Phi_{0}$ and the Hubble parameter $H$ but also the quantum
field fluctuations $\langle\varphi^{2}\rangle$ is introduced. In particular
$\Delta_{B}$ vanishes according to the background field equation and the
Friedmann equation as long as all quantum fluctuations are ignored. This
reduces the mode equation to the known Mukhanov-Sasaki equation. Thus,
$\Delta_{B}\neq 0$ is the indicator, giving the effects from the quantum
fluctuations to the curvature perturbations, which in a spatially flat gauge
can be computed from the solutions of the mode functions. We then consider the
models in which the Universe undergoes the SR-USR-SR inflation where with no
inclusion of $\langle\varphi^{2}\rangle$, the created curvature perturbations
are consistent with the observations and also show a spike at relevant scales
as the source for the primordial black hole production. Nevertheless, although
quantum fluctuations do not play a significant role in the evolution of the
background fields, they trigger the huge growth of $\Delta_{B}$ in particular
during the transition from USR back to the second SR inflation. As a result,
the growth of $\Delta_{B}$ in turn gives the boost effects to the curvature
perturbations to the modes that leave the horizon in the early times of the SR
inflation. Whether or not the boost effects can be visible also depends on the
cosmic friction term given by the Hubble parameter in the mode equations. Here
we present two models to illustrate the competition between the boost and the
friction force effects. In our future work, we plan to further study the
critical value of the Hubble parameter and its time-dependent behavior, below
which the corrections from the quantum field fluctuations become of importance
in a given model of interest. Thus, it will be also of great interest to
construct a successful model to interpret the observations and generate large
enough spike for the PBH production where the accompanying large quantum
fluctuations need to be taken into account.

###### Acknowledgements.

This work was supported in part by the Ministry of Science and Technology
(MOST) of Taiwan, R.O.C. under grant numbers 109-2112-M-259-003 (DSL) and
109-2112-M-001-003 (KWN).

## References

  * (1) E. W. Kolb , M. S. Turner, The Early Universe Addison Wesley, Redwood City, C.A. 1990.
  * (2) B. P. Abbott et al. , Phys. Rev. Lett. 116, 061102 (2016).
  * (3) B. J. Carr and S. W. Hawking, Mon. Not. Roy. Astron. Soc. 168, 399 (1974).
  * (4) P. Meszaros, Astron. Astrophys. 37, 225 (1974).
  * (5) B. J. Carr, Astrophys. J. 201, 1 (1975).
  * (6) M. Sasaki, T. Suyama, T. Tanaka, and S. Yokoyama, Class. Quant. Grav. 35, 063001 (2018).
  * (7) S.-L. Cheng, W. Lee, and K.-W. Ng, Production of high stellar-mass primordial black holes in trapped inflation, J. High Energy Phys. 02, 008 (2017).
  * (8) J. M. Ezquiaga, J. Garcia-Bellido, and E. R. Morales, Primordial Black Hole production in Critical Higgs Inflation, Phys. Lett. B 776, 345 (2018).
  * (9) K. Kannike, L. Marzola, M. Raidal, and H. Veermäe, Single Field Double Inflation and Primordial Black Holes, JCAP 1709, 020 (2017).
  * (10) G. Ballesteros and M. Taoso, Phys. Rev. D 97, 023501 (2018).
  * (11) S.-L. Cheng, W. Lee, and K.-W. Ng, Primordial black holes and associated gravitational waves in axion monodromy inflation, JCAP, 07, 001 (2018).
  * (12) M. Cicoli, V. A. Diaz, and F. G. Pedro, Primordial Black Holes from String Inflation, JCAP 06, 034 (2018).
  * (13) O. Özsoy, S. Parameswaran, G. Tasinato, and I. Zavala, Mechanisms for Primordial Black Hole Production in String Theory, JCAP 07, 005 (2018).
  * (14) I. Dalianis, A. Kehagias, and G. Tringas, Primordial Black Holes from alpha-attractors, JCAP 01, 037 (2019).
  * (15) W. H. Kinney, Horizon crossing and inflation with large eta, Phys. Rev. D 72, 023515 (2005).
  * (16) J. Martin, H. Motohashi, and T. Suyama, Ultra Slow-Roll Inflation and the non-Gaussianity Consistency Relation, Phys. Rev. D 87, 023514 (2013).
  * (17) S.-L. Cheng, W. Lee, and K.-W. Ng, Superhorizon curvature perturbation in ultraslow-roll inflation, Phys. Rev. D 99, 063524 (2019).
  * (18) C. T. Byrnes, P. S. Cole, and S. P. Patil, Steepest growth of the power spectrum and primordial black holes, JCAP 06, 028 (2019).
  * (19) A. A. Starobinsky, Stochastic De Sitter (inflationary) stage in the early Universe, Lect. Notes Phys. 246, 107 (1986).
  * (20) C. Pattison, V. Vennin, H. Assadullahi, and D. Wands, Quantum diffusion during inflation and primordial black holes, JCAP 10, 046 (2017); Stochastic inflation beyond slow roll, JCAP 07, 031 (2019).
  * (21) M. Biagetti, G. Franciolini, A. Kehagias, and A. Riotto, Primordial Black Holes from Inflation and Quantum Diffusion, JCAP 07, 032 (2018).
  * (22) J. M. Ezquiaga and J. Garcia-Bellido, Quantum diffusion beyond slow-roll: implications for primordial black-hole production, JCAP 08, 018 (2018).
  * (23) H. Firouzjahi, A. Nassiri-Rad, M. Noorbala, Stochastic Ultra Slow Roll Inflation, JCAP 01, 040 (2019).
  * (24) D. Boyanovsky, H. J. de Vega, and N. G. Sanchez, Nucl. Phys. B 747, 25 (2006).
  * (25) A. Vilenkin and L. H. Ford, Phys. Rev. D 26, 1231 (1982); T. S. Bunch and P. C. W. Davies, Proc. R. Soc. London A 360, 117 (1978).
  * (26) W.-C. Syu, D.-S. Lee, and K.-W. Ng, Quantum loop effects to the power spectrum of primordial perturbations during ultra slow-roll inflation, Phys. Rev. D 101, 025013 (2020).
  * (27) T. Clunan and D. Seery, Relics of spatial curvature in the primordial non-gaussianity, JCAP 1001, 032 (2010).
  * (28) K. Sugimura and E. Komatsu, Bispectrum from open inflation , JCAP 11, 065 (2013).
  * (29) D. Boyanovsky, H. J. de Vega, R. Holman, D.-S. Lee and A. Singh, Phys. Rev. D 51, 4419 (1995); D. Boyanovsky, M. D’Attanasio, H. J. de Vega, R. Holman and D.-S. Lee, Phys. Rev. D 52, 6805 (1995).
  * (30) M. Sasaki, Prog. Theor. Phys. 76, 1036 (1986); V. F. Mukhanov, Zh. Eksp. Teor. Fiz. 94N7, 1 (1988) [Sov. Phys. JETP 67, 1297 (1988)].
  * (31) Planck Collaboration, Y. Akrami et al.,Planck 2018 results. X. Constraints on inflation, A & A 641, A10 (2020).
  * (32) Keck Array and BICEP2 Collaborations: P. A. R. Ade et al., BICEP2 / Keck Array x: Constraints on Primordial Gravitational Waves using Planck, WMAP, and New BICEP2/Keck Observations through the 2015 Season, Phys. Rev. Lett. 121, 221301 (2018).