# On the Limits of Information Spread by Memory-less Agents

Niccolò D’Archivio and Robin Vacus Sapienza Università di Roma. Email:
<EMAIL_ADDRESS>University. Email<EMAIL_ADDRESS>
###### Abstract

We address the self-stabilizing bit-dissemination problem, designed to capture
the challenges of spreading information and reaching consensus among entities
with minimal cognitive and communication capacities. Specifically, a group of
$n$ agents is required to adopt the correct opinion, initially held by a
single informed individual, choosing from two possible opinions. In order to
make decisions, agents are restricted to observing the opinions of a few
randomly sampled agents, and lack the ability to communicate further and to
identify the informed individual. Additionally, agents cannot retain any
information from one round to the next. According to a recent publication in
SODA (2024), a logarithmic convergence time without memory is achievable in
the parallel setting (where agents are updated simultaneously), as long as the
number of samples is at least $\Omega(\sqrt{n\log n})$. However, determining
the minimal sample size for an efficient protocol to exist remains a
challenging open question. As a preliminary step towards an answer, we
establish the first lower bound for this problem in the parallel setting.
Specifically, we demonstrate that any protocol with constant sample size
requires asymptotically an almost-linear number of rounds to converge, with
high probability. This lower bound holds even when agents are aware of both
the exact value of $n$ and their own opinion, and encompasses various simple
existing dynamics designed to achieve consensus. Beyond the bit-dissemination
problem, our result sheds light on the convergence time of the “minority”
dynamics, the counterpart of the well-known majority rule, whose chaotic
behavior is yet to be fully understood despite the apparent simplicity of the
algorithm.

##  1 Introduction

Exploring the computational power and limits of well-chosen models – ones that
are simple enough for analytical tractability, and yet relevant to specific
biological scenarios – can lead to insightful conclusion about the functioning
of biological distributed systems [1, 2, 3, 4, 5]. In line with this approach,
we consider the bit-dissemination problem, introduced in [6] in order to
evaluate the possibility to solve two fundamental problems concurrently:
reaching agreement efficiently, while ensuring that an information possessed
initially by a single individual is propagated to the whole group. In order to
fit biological scenarios, the problem features extremely constrained
communications. Agents engage in random interactions with just a few
individuals at a time, as in the $\mathcal{PULL}$ model. Furthermore, they can
only disclose their current decision and no other information, following an
assumption introduced in [7] to model situations in which individuals do not
actively communicate [8].

In this paper, we further restrict attention to memory-less entities lacking
the ability to perform computations over extended periods of time; or at least
not in a sufficiently reliable manner. In particular, this assumption
precludes the possibility to maintain clocks and counters, or to estimate the
tendency of the dynamics. It is likely to be relevant in several biological
ensembles, such as ant colonies [9], slime molds, cells and bacteria [10] or
even plants [11]. We acknowledge that it is always hard to rule out the
possibility that species make use of memory, especially in the case of social
insects. Yet, this modeling choice remains applicable even without
presupposing specific cognitive abilities, as many species often stick to
simple behavioral rules when attempting to reach a consensus, such as quorum
sensing [12] or alignment rules [13].

#### Description of the problem.

More precisely, we consider a group of $n$ agents holding binary opinions. One
of the agents, referred to as the source, knows what opinion is “correct” and
remains with it at all times. Execution proceeds in discrete rounds. We assume
that agents have no memory of what happened in previous rounds, besides their
current opinion. In the parallel setting, all non-source agents are activated
simultaneously in every round, while in the sequential setting, only one non-
source agent, selected uniformly at random, is activated. Upon activation, a
non-source agent $i$ samples a set $S$ consisting of $\ell$ other agents drawn
uniformly at random (with replacement). Then, based only on the opinions of
the agents in $S$ and on its own opinion, Agent $i$ may choose to adopt a new
opinion. In particular, Agent $i$ does not know whether or not $S$ contains
the source. A protocol is successful if every non-source agent eventually
adopts the correct opinion and remains with it forever. Finally, a protocol
must converge independently of the initial opinions of the agents (including
the correct opinion), which can be thought of as being chosen by an adversary.

#### Previous works.

The main parameters of the problems are the activation pattern (which may be
parallel or sequential) and the sample size $\ell$. To compare protocols
across various settings, we are typically interested in their convergence
time, i.e., the total number of activations required to reach consensus w.r.t.
the correct opinion. Here, we will express the convergence time in terms of
parallel rounds: one parallel round corresponds to $n$ activations, which is
equivalent to 1 round in the parallel setting, and $n$ rounds in the
sequential setting.

The bit-dissemination problem without memory was first studied in [14], in the
sequential setting, where nearly matching lower and upper bounds are given. On
the one hand, the authors show that no protocol can converge in less than
$\Omega(n)$ parallel rounds in expectation, regardless of the sample size. On
the other hand, they show that the well-known Voter dynamics (see Protocol 1
in Section 1.1) achieves consensus in $O(n\log^{2}n)$ parallel rounds with
high probability. Since the Voter dynamics only needs the sample size to be
$1$, these results imply that $\ell$ is not a critical parameter in the
sequential setting.

Later, the authors of [15] show that the aforementioned lower bound does not
hold in the parallel setting. In fact, they show that the minority dynamics
(see Protocol 2 in Section 1.1) converges in $O(\log^{2}n)$ parallel rounds
w.h.p., as long as the sample size is at least $\Omega(\sqrt{n\log n})$. This
finding reveals that the best convergence times achievable in the sequential
versus parallel settings differ by an exponential factor. The bit-
dissemination problem is all the more interesting to study as it is one of the
most natural ones exhibiting this property.

Part of the explanation behind this curious phenomenon is that the stochastic
processes involved are of different mathematical natures, in one setting
compared to the other. In the sequential setting, the number of agents with
opinion $1$ may only vary by at most one unit in every round, since only one
agent is activated at a time. Therefore, independently of the protocol being
operated, the evolution of the system can always be described by a “birth-
death” chain, i.e., a Markov chain whose underlying graph is a path of size
$n$. In fact, all proofs in [14] heavily rely on this observation. In
contrast, in the parallel setting, the process may jump from any configuration
to any other – albeit with extremely small probability. On the one hand, this
characteristic allows for fast convergence. For instance, qualitatively
speaking, the minority dynamics succeeds by first reaching a configuration in
which an appropriate proportion of the agents hold the wrong opinion; after
what all non-source agents, perceiving the same minority, simultaneously adopt
the correct opinion. On the other hand, it complicates the analysis of any
protocol in the parallel setting, and even more so the task of deriving lower
bounds. Following on from these works, we are ultimately interested in the
following question:

Is there any protocol achieving a poly-logarithmic convergence time in the
parallel setting,
when the sample size is $o(\sqrt{n})$?

Following the preliminary work of [15], the minority dynamics is a natural
candidate for this task. We also believe that the interest of this dynamic is
not limited to the bit-dissemination problem. Indeed, it is a suitable
protocol for solving more traditional consensus problems (without a source),
for which its convergence time may only be smaller than for the bit-
dissemination problem. In this regard, it is significantly faster that the
Voter dynamics, provided that $\ell$ is large enough. While it is probably no
more effective than majority-like dynamics [16], the latter lack sensitivity
towards an informed individual, and in fact, fail in general to solve the bit-
dissemination problem. However, despite its extreme simplicity, the conditions
under which the minority dynamics is able to converge quickly have not been
identified. While the analysis in [15] relies on a sample size of at least
$\Omega(\sqrt{n\log n})$, the authors do not provide a lower bound for this
parameter, nor do they justify informally why this quantity is necessary.
Therefore, we also consider the following independent question.

What is the minimal sample size for which the minority dynamics
converges in poly-logarithmic time?

As a first step towards answering these questions, we focus on the case that
the sample size is constant, or in other words, independent from $n$. Beyond
analytical tractability, several reasons motivate this assumption. First, many
existing opinion dynamics that have been traditionally studied in the context
of consensus are defined with a small (fixed) number of samples [17]. This is
the case for the Voter dynamics and majority dynamics, but also for the
undecided states dynamics, as well as all population protocols [18], in which
agents interact by pairs. In addition, protocols relying on a sample size that
increases with $n$ implicitly require the agents to have some knowledge about
the size of the population, which is often undesirable or unrealistic in
distributed systems. Finally, real biological entities are most likely
interacting with few of their conspecifics even when they are part of a larger
group. As an illustration, it has been shown empirically that the movement of
any bird in a flock depends mostly on its 6 or 7 closest neighbors, regardless
of how many individuals are present in the vicinity [19, 20], while other
works point at a similar phenomenon in fishes [21].

###  1.1 Problem definition

We consider a finite set $I=\\{1,\ldots,n\\}$ of agents. Let
$X_{t}^{(i)}\in\\{0,1\\}$ be the opinion of Agent $i$ in round $t$. We assume
that Agent $1$ is the source and holds the correct opinion throughout the
execution. Denoting the sample size by $\ell$ (independent from $n$), a
protocol $\mathcal{P}$ is defined as a family of functions

$g_{n}^{[b]}:\\{0,\ldots,\ell\\}\mapsto[0,1].$

Informally, $g_{n}^{[b]}(k)$ represents the probability that an agent
observing $k$ ’1’ out of its $\ell$ samples adopts opinion $1$ in the next
round, provided that the total number of agents is $n$, and that this agent
has opinion $b$ in the current round. More formally, in round $t$, for every
agent $i$ simultaneously:

  1. 1.

A vector $S_{t}^{(i)}\in I^{\ell}$ of size $\ell$ is sampled uniformly at
random (u.a.r.) (the same agent may appear several times in $S_{t}^{(i)}$).

  2. 2.

Writing $k_{t}^{(i)}$ to denote the number of agents with opinion $1$ in
$S_{t}^{(i)}$, Agent $i$ updates its opinion according to

$X_{t+1}^{(i)}\leftarrow 1\text{ with probability
}g_{n}^{\left[X_{t}^{(i)}\right]}(k_{t}^{(i)}),\quad 0\text{ otherwise}.$

For the sake of clarity, let us note a few important consequences of this
definition.

  * •

Non-source agents do not know where the opinions that they observe come from.
In particular, they do not know if $S_{t}^{(i)}$ contains the source.

  * •

Non-source agents do not have identifiers, or in other words, all of them must
run exactly the same update rule. They are also not aware of the round number
(indices are used for analysis purposes only).

  * •

However, non-source agents are aware of their current opinion, as well as the
exact value of $n$.

  * •

Besides their opinion, non-source agents have no memory, in the sense that
their behavior cannot depend on any information from previous rounds.

Since the agents have no memory and no identifiers, the configuration of the
system in round $t$ can be described simply by a pair $(z,X_{t})$, where
$z\in\\{0,1\\}$ denotes the correct opinion, and $X_{t}\in\\{0,\ldots,n\\}$
denotes the number of agents with opinion $1$. For a given
$n\in\operatorname{\mathbb{N}}$, and an initial configuration $C=(z,X_{0})$,
we define the convergence time of protocol $\mathcal{P}$ as the first round
for which all agents have adopted the correct opinion and remain with it
forever, that is:

$\tau_{n}(\mathcal{P},C):=\inf\\{t\geq 0,\text{ for every }s\geq
t,X_{s}=n\cdot z\\}.$

We say that a protocol $\mathcal{P}$ solves the bit-dissemination problem in
time $T(n)$ if for any sequence of initial configurations $\\{C_{n}\\}$,
$\tau_{n}(\mathcal{P},C_{n})\leq T(n)$ w.h.p.111Given a sequence of events
$\\{A_{n}\\}_{n\in\operatorname{\mathbb{N}}}$, we say that “$A_{n}$ happens
with high probability (w.h.p.)” if $\mathbb{P}(A_{n})=1-1/n^{\Omega(1)}$.
Consequently, non-source agents are facing a “self-stabilizing” problem, since
they are required to reach a unique legal configuration (the consensus
compatible with the opinion of the source) from any possible initial
configuration, and remain in it forever. We note, however, that the source
must be considered as part of the environment (and not as a corruptible agent)
in order to fit the traditional definition of self-stabilization.

We conclude this section by defining two important dynamics.

Input: An opinion sample $S$ of size $\ell$.

$X_{t+1}^{(i)}\leftarrow$ a random opinion in $S$

(Since $S$ is sampled u.a.r., this protocol does not depend on the value of
$\ell$, which can be assumed to be $1$ w.l.o.g.)

Protocol 1 The Voter dynamics

Input: An opinion sample $S$ of size $\ell$.

if  _all opinions in $S$ are equal to $x$_ then

$X_{t+1}^{(i)}\leftarrow x$

else

$X_{t+1}^{(i)}\leftarrow$ minority opinion in $S$

Protocol 2 The Minority dynamics [15]

In terms of our definition, the Voter dynamics writes

$g_{n}^{[0]}(k)=g_{n}^{[1]}(k)=:g^{\textrm{voter}}(k)=\frac{k}{\ell},\quad\text{
for every }k\in\\{0,\ldots,\ell\\}.$ (1)

Similarly, assuming ties to be broken u.a.r., the Minority dynamics is given
by

$g_{n}^{[0]}(k)=g_{n}^{[1]}(k)=:g^{\textrm{minority}}(k)=\begin{cases}1\quad\text{if
}k=\ell\text{ or }0<k<\frac{\ell}{2},\\\ \frac{1}{2}\quad\text{if
}k=\frac{\ell}{2},\\\ 0\quad\text{if }k=0\text{ or }\frac{\ell}{2}<k<\ell.\\\
\end{cases}$ (2)

###  1.2 Our Results

We show that, when the sample size is bounded, any protocol that does not have
access to memory needs almost-linear time to solve the bit-dissemination
problem.

######  Theorem 1.

Assume that the sample size $\ell$ is constant. If there exists a function
$T:\operatorname{\mathbb{N}}\mapsto\operatorname{\mathbb{N}}$ and a protocol
$\mathcal{P}$ solving the bit-dissemination problem in time $T(n)$, then for
every $\varepsilon>0$, $T(n)=\Omega(n^{1-\varepsilon})$.

To the best of our knowledge, this is the first non-trivial lower-bound for
this problem in the parallel setting. Note that it also holds when agents can
choose from more than 2 opinions, provided that they may not adopt an opinion
that they have never seen or adopted222This is an arguably natural assumption,
without which increasing the number of opinions directly increases the amount
of information communicated at each interaction.. Indeed, in that case, a
lower bound could be obtained by assuming a binary initial configuration and
reducing to Theorem 1.

The proof of Theorem 1 is presented in Section 4, and uses a general result on
Markov chains, described in Section 3, as a black box. Among other classical
arguments, it relies on an original idea which can be summarized as follows.
For every protocol $\mathcal{P}$, we define

$F_{n}(p):=-p+\sum_{k=0}^{\ell}\binom{\ell}{k}p^{k}(1-p)^{\ell-k}\left(p\,g_{n}^{[1]}(k)+(1-p)\,g_{n}^{[0]}(k)\right).$
(3)

The sum in Eq. 3 corresponds to the probability that a non-source agent, taken
uniformly at random, adopts opinion 1, given that the current proportion of
agents with opinion $1$ is $p$. Informally, $F_{n}(p)$ measures the bias of
$\mathcal{P}$ towards opinion $1$, or in other words:

${\rm I\kern-3.00003ptE}\left(\frac{X_{t+1}}{n}\mid
X_{t}=x_{t}\right)\approx\frac{x_{t}}{n}+F_{n}\left(\frac{x_{t}}{n}\right)$

(see Proposition 5 for a more accurate statement). The fact that $\ell$ is
constant w.r.t. $n$ directly implies that $F_{n}$, as a polynomial in $p$, has
a constant degree, and therefore a constant number of roots within the
interval $[0,1]$. We are able to exploit this property by considering a well-
chosen interval of constant length between two roots of $F_{n}$. If $F_{n}$ is
negative on this interval, i.e., $\mathcal{P}$ tends to make the proportion of
$1$-opinions decrease, we show that the process will be slow to reach
consensus every time the correct opinion is $1$. Conversely, if it is
positive, we show that fast convergence fails whenever the correct opinion is
$0$.

In terms of the dependency on $n$, we show that our lower bound is nearly
tight (up to a logarithmic factor) by adapting a well-known result to our
setting. Its proof does not introduce any novel argument and is deferred to
Appendix B.

######  Theorem 2.

The Voter dynamics (Protocol 1) solves the bit-dissemination problem in
$O(n\log n)$ rounds w.h.p.

However, when it comes to parameter $\ell$, a gap remains between our lower
bound and the upper bound in [15], where it is shown that the minority
dynamics solves the problem in $O(\log^{2}n)$ rounds w.h.p. when $\ell$ is at
least $\Omega(\sqrt{n\log n})$.

On the one hand, we believe that our techniques cannot be used to extend the
lower bound to a higher value of $\ell$. Indeed, if $\ell=\Omega(\log n)$, it
is already possible for a protocol to converge in just one round w.h.p. from
configurations that are arbitrarily far away from the consensus. This
observation destroys any hope of restricting the analysis to a small interval
of the configuration space. In contrast, this phenomenon does not happen
w.h.p. in our setting (see Proposition 4).

On the other hand, to this day, there is no good reason to think that
$\Theta(\sqrt{n\log n})$ is the smallest value of $\ell$ allowing for an
efficient protocol (such as the minority dynamics). As previously mentioned,
the authors of [15] do not provide any argument supporting this claim, and
simulations suggest that its convergence might be fast even when the sample
size is qualitatively small (although in general, numerical results shed
little light on asymptotic behaviours). Yet, rigorously analysing its
convergence time seems highly challenging, and is left for future work.

###  1.3 Other Related Works

The bit-dissemination problem was also studied under the assumption that
agents can use a moderate amount of memory. An efficient protocol is
identified in [7], and achieves consensus in $O(\mathrm{polylog}~{}n)$
parallel rounds with high probability. It relies on agents being able to
memorize $\log\log n$ bits of information from one round to the next and
requires a sample size logarithmic in $n$. Other candidates are mentioned in
[6] but are not analysed. The authors of [22] show that the problem can be
solved in the context of population protocols with a memory of only constant
size. Importantly however, population protocols do not fit the framework of
passive communications. Specifically, interaction rules in this model depend
on the exact states of the agents, and not just on their binary opinion.

The bit-dissemination problem is a specific case of the majority bit-
dissemination problem, introduced in [6] and also addressed in [22]. In this
variant, the number of source agents is arbitrarily large, and they may have
conflicting preferences. The opinions of sources must not necessarily be in
line with their preferences, and they can participate to the protocol in the
same way as regular agents. The correct opinion is defined as the most
widespread preference among sources. On the one hand, an efficient solution
can be derived from the results in [22, 23], but require active
communications, and relies on memory. On the other hand, the authors of [7]
show that the majority bit-dissemination problem is impossible with passive
communications.

More generally, many works within the opinion dynamics literature investigate
the influence of the presence of “stubborn” or “biased” agents on the
behaviour of the system. Typically, these works focus on a single arbitrary
process, mainly the Voter dynamics [24, 25, 26, 27, 28], and to the best of
our knowledge, do not establish general lower bounds. In contrast, our goal is
to better understand the difficulty of spreading information as an algorithmic
problem; therefore, we do not want to rule out any imaginable protocol within
the constraints of our setting. Furthermore, they often investigate different
questions, such as the impact of the number of sources or they position in the
network on the convergence time, or assume that sources may have conflicting
opinions.

##  2 Preliminaries

In this section, we make a few general observations that we will use later in
our analysis.

Conditioning on Agent $i$ sampling exactly $k$ times the opinion “1”, for
every $k\in\\{0,\ldots,\ell\\}$, we obtain that

$\mathbb{P}\left(X_{t+1}^{(i)}=1\mid
X_{t}=x_{t},~{}X_{t}^{(i)}=b\right)=\sum_{k=0}^{\ell}\binom{\ell}{k}\left(\frac{x_{t}}{n}\right)^{k}\left(1-\frac{x_{t}}{n}\right)^{\ell-k}g_{n}^{[b]}(k).$
(4)

After convergence has happened, i.e., $X_{t}\in\\{0,n\\}$, this probability
must be equal to $0$ or $1$ respectively so that a consensus is maintained.
This imposes a constraint on any protocol attempting to solve the bit-
dissemination problem, which can be formalized as follows (due to lack of
space, the proof is deferred to Appendix C).

######  Proposition 3.

Any protocol $\mathcal{P}$ solving the bit-dissemination problem must satisfy
$g_{n}^{[0]}(0)=0$ and $g_{n}^{[1]}(\ell)=1$.

Accordingly, we will always assume that $g_{n}^{[0]}(0)=0$ and
$g_{n}^{[1]}(\ell)=1$. Using this assumption, we can show a general upper
bound on the fraction of agents with opinion $0$ that can change opinion in a
single time step.

######  Proposition 4.

Let $c\in(0,1)$ and consider a protocol $\mathcal{P}$ solving the bit-
dissemination problem. There is a constant $y=y(c,\ell)\in(c,1)$ s.t. for
every $n$ large enough, and $x_{t}\leq c\,n$,

$\mathbb{P}\left(X_{t+1}\leq y\,n\mid X_{t}=x_{t}\right)\geq
1-\exp\left(2\,n^{-1/2}\right).$

###### Proof.

Let $t\in\operatorname{\mathbb{N}}$, and $x_{t}\leq cn$. By Eq. 4, and since
we assumed $g_{n}^{[0]}(0)=0$,

$\displaystyle\mathbb{P}\left(X_{t+1}^{(i)}=0\mid
X_{t}=x_{t},X_{t}^{(i)}=0\right)$
$\displaystyle=1-\sum_{k=0}^{\ell}\binom{\ell}{k}\left(\frac{x_{t}}{n}\right)^{k}\left(1-\frac{x_{t}}{n}\right)^{\ell-k}g_{n}^{[0]}(k)$
$\displaystyle=\sum_{k=0}^{\ell}\binom{\ell}{k}\left(\frac{x_{t}}{n}\right)^{k}\left(1-\frac{x_{t}}{n}\right)^{\ell-k}\left(1-g_{n}^{[0]}(k)\right)$
$\displaystyle\geq\left(1-\frac{x_{t}}{n}\right)^{\ell}\geq(1-c)^{\ell}.$

Let $Y$ be the number of agents with opinion $0$ in round $t$, that keep
opinion $0$ in round $t+1$ (conditioned on $X_{t}=x_{t}$). By assumption,
$n-X_{t}\geq(1-c)n$, so the last equation implies the following
domination333Given two real-valued random variables $X$ and $Y$, we say that
$X$ is stochastically dominated by $Y$, and write $X\preceq Y$, if for every
$x\in\operatorname{\mathbb{R}}$, $\mathbb{P}(X>x)\leq\mathbb{P}(Y>x)$.:

$Y\succeq\mathrm{Binomial}\left((1-c)n,(1-c)^{\ell}\right):=Z.$

Let $a=a(c,\ell):=(1-c)^{\ell+1}$, so that ${\rm
I\kern-3.00003ptE}\left(Z\right)=an$. Let $a^{\prime}:=a-n^{-1/4}$. For $n$
large enough, we have $a^{\prime}>a/2$. By  (Hoeffding’s bound)., we have

$\displaystyle\mathbb{P}\left(Z\leq\frac{an}{2}\right)\leq\mathbb{P}\left(Z\leq
a^{\prime}n\right)=\mathbb{P}\left(Z\leq{\rm
I\kern-3.00003ptE}(Z)-n^{3/4}\right)\leq\exp\left(-2n^{1/2}\right).$

Finally, setting $y=y(c,\ell):=1-a/2$, we obtain

$\mathbb{P}\left(X_{t+1}\geq y\,n\mid
X_{t}=x_{t}\right)\leq\mathbb{P}\left(Y\leq\frac{an}{2}\right)\leq\mathbb{P}\left(Z\leq\frac{an}{2}\right)\leq\exp\left(-2\,n^{1/2}\right),$

which concludes the proof of Proposition 4. ∎

Finally, the following proposition justifies the informal claim made in
Section 1.2 according to which the function $F_{n}$, defined in Eq. 3,
represents the “bias” of the corresponding protocol towards opinion $1$.

######  Proposition 5.

For every protocol $\mathcal{P}$, and every $x_{t}\in[n]$,

$\displaystyle{\rm I\kern-3.00003ptE}\left(X_{t+1}\mid X_{t}=x_{t}\right)$
$\displaystyle\leq x_{t}+n\,F_{n}\left(\frac{x_{t}}{n}\right)+1,$ (5)
$\displaystyle{\rm I\kern-3.00003ptE}\left(X_{t+1}\mid X_{t}=x_{t}\right)$
$\displaystyle\geq x_{t}+n\,F_{n}\left(\frac{x_{t}}{n}\right)-1.$ (6)

###### Proof.

For a non-source agent $i\in I\setminus\\{1\\}$ and an opinion
$b\in\\{0,1\\}$, let

$P_{b}:=\mathbb{P}\left(X_{t+1}^{(i)}=1\mid
X_{t}=np,~{}X_{t}^{(i)}=b\right)=\sum_{k=0}^{\ell}\binom{\ell}{k}p^{k}(1-p)^{\ell-k}g_{n}^{[b]}(k),$

where the second equality is a restatement of Eq. 4. Note that by definition
of $F_{n}$,

$F_{n}(p)=p\,P_{1}+(1-p)P_{0}-p.$ (7)

There are $X_{t}-z$ non-source agents with opinion 1 in round $t$, and
$n-X_{t}-(1-z)$ non-source agents with opinion 0. Hence,

$\displaystyle{\rm I\kern-3.00003ptE}\left(X_{t+1}\mid X_{t}=np\right)$
$\displaystyle=z+(np-z)P_{1}+\big{(}n-np-(1-z)\big{)}P_{0}$
$\displaystyle=n\big{(}pP_{1}+(1-p)P_{0}\big{)}+z(1-P_{1})-(1-z)P_{0}$
$\displaystyle=np+nF(p)+z(1-P_{1})-(1-z)P_{0}.$ (by Eq. 7)

Note that for any $z\in\\{0,1\\}$, since $P_{0},P_{1}\in[0,1]$, we have

$-1\leq z(1-P_{1})-(1-z)P_{0}\leq+1,$

from which Eqs. 5 and 6 follow. ∎

##  3 An Intermediate Results on Markov Chains

In this section, we present a general result that we will use later as a black
box. Informally, the theorem says that if a Markov chain is a super-martingale
over an interval of values, and given that it cannot skip the interval
entirely, then the time required to cross the interval is at least the time
needed by a martingale to escape it.

######  Theorem 6.

Let $\\{X_{t}\\}_{t\in\operatorname{\mathbb{N}}}$ be a Markov chain on
$\mathbb{Z}$ and $\varepsilon>0$. If there are
$a_{1}<a_{2}<a_{3}\in\operatorname{\mathbb{R}}$ s.t.

  * (i)

for every $x_{t}\in\\{a_{1}\,n,...,a_{3}\,n\\}$, ${\rm
I\kern-3.00003ptE}(X_{t+1}\mid X_{t}=x_{t})\leq x_{t}+1$,

  * (ii)

for every $x_{t}<a_{1}\,n$, $\mathbb{P}(X_{t+1}>a_{2}\,n\mid
X_{t}=x_{t})=\exp\left(-n^{\Omega(1)}\right)$,

  * (iii)

$\mathbb{P}(|X_{t+1}-{\rm I\kern-3.00003ptE}\left(X_{t+1}\mid
X_{t}\right)|>n^{1/2+\varepsilon/4})<2\exp\left(-2n^{\varepsilon/2}\right)$,

then for $X_{0}=\frac{a_{2}+a_{3}}{2}$ and $n$ large enough, we have w.h.p.

$\inf\\{t\in\operatorname{\mathbb{N}},X_{t}\geq a_{3}\,n\\}\geq
n^{1-\varepsilon}.$

###### Proof.

Let $\epsilon>0$, and $T=n^{1-\epsilon}$. Let $Y_{t}:=X_{t}-t$. We will
consider the Doob decomposition of $Y_{t}$: for every $t\geq 1$, let

$\displaystyle A_{0}:=0$ $\displaystyle\quad\text{and for all }t>0,\quad
A_{t}:=\sum_{k=1}^{t}\left({\rm I\kern-3.00003ptE}\left(Y_{k}\mid
Y_{k-1}\right)-Y_{k-1}\right),$ $\displaystyle M_{0}:=Y_{0}$
$\displaystyle\quad\text{and for all }t>0,\quad
M_{t}:=Y_{0}+\sum_{k=1}^{t}\left(Y_{k}-{\rm I\kern-3.00003ptE}\left(Y_{k}\mid
Y_{k-1}\right)\right).$

With this definition, one can check that $Y_{t}=M_{t}+A_{t}$, and that
$\\{M_{t}\\}_{t\in\operatorname{\mathbb{N}}}$ is a martingale. The main ideas
of the proof are depicted on Figure 1.

Figure 1: Sketch of the proof of Theorem 6. (a) By assumption (ii), with high
probability, $Y_{t}$ cannot jump from below $a_{1}\,n-t$ to above $a_{2}\,n-t$
in a single step, let alone $a_{2}\,n$. (b) In Claim 7, we use assumption (i)
and the properties of the Doob’s decomposition to show that, if
$a_{1}\,n-t\leq Y_{t}\leq M_{t}$, then $Y_{t}$ cannot jump above $M_{t}$ in a
single step. (c) In Claim 8, we use the Azuma-Hoeffding inequality to show
that $M_{t}$ remains in the interval $[a_{2}\,n+T,a_{3}\,n-T]$ for at least
$T$ rounds w.h.p. Overall, (a) (b) and (c) implies that $Y_{t}$ must remain
below $a_{3}\,n-T$ for at least $T$ rounds w.h.p., yielding the desired
conclusion.

First, we show that by construction and Assumption (i), $Y_{t}$ can never
“jump over” $M_{t}$ in one round, as long as it starts from the interval
$\\{a_{1}n-t,\ldots,a_{3}n-t\\}$.

######  Claim 7.

For every $t\in\operatorname{\mathbb{N}}$,

$M_{t}\geq Y_{t}\text{ and }Y_{t}\in\\{a_{1}n-t,\ldots,a_{3}n-t\\}\implies
M_{t+1}\geq Y_{t+1}.$

###### Proof.

Let $y_{t}\in\\{a_{1}n-t,\ldots,a_{3}n-t\\}$ and $m_{t}\geq y_{t}$, and
consider the event

$\mathcal{E}:=\left\\{Y_{t}=y_{t}\mathbin{\scalebox{1.5}{$\cap$}}M_{t}=m_{t}\right\\}.$

We have

$\displaystyle{\rm I\kern-3.00003ptE}\left(Y_{t+1}\mid Y_{t}=y_{t}\right)$
$\displaystyle={\rm I\kern-3.00003ptE}\left(X_{t+1}-(t+1)\mid
X_{t}=y_{t}+t\right)$ $\displaystyle={\rm I\kern-3.00003ptE}\left(X_{t+1}\mid
X_{t}=y_{t}+t\right)-(t+1)$ $\displaystyle\leq(y_{t}+t+1)-(t+1)$ (by (i))
$\displaystyle=y_{t}.$

Therefore,

$\left(A_{t+1}-A_{t}\mid\mathcal{E}\right)=\bigg{(}{\rm
I\kern-3.00003ptE}\left(Y_{t+1}\mid
Y_{t}\right)-Y_{t}\mid\mathcal{E}\bigg{)}={\rm
I\kern-3.00003ptE}\left(Y_{t+1}\mid Y_{t}=y_{t}\right)-y_{t}\leq 0.$

Since $m_{t}\geq y_{t}$, this implies

$\left(A_{t+1}\mid\mathcal{E}\right)\leq\left(A_{t}\mid\mathcal{E}\right)=\left(Y_{t}-M_{t}\mid\mathcal{E}\right)=y_{t}-m_{t}\leq
0,$

and thus,

$\left(Y_{t+1}\mid\mathcal{E}\right)=\left(M_{t+1}+A_{t+1}\mid\mathcal{E}\right)\leq\left(M_{t+1}\mid\mathcal{E}\right),$

which concludes the proof of Claim 7. ∎

Now, using Azuma’s inequality and Assumptions (ii) and (iii), we establish
high probability bounds on the martingale $M_{t}$.

######  Claim 8.

With high probability, for every $t\leq T$, $a_{2}\,n+T<M_{t}<a_{3}\,n-T$.

###### Proof.

By construction, and since $X_{t}$ and $Y_{t}$ only differ by a deterministic
quantity,

$M_{t+1}-M_{t}=Y_{t+1}-{\rm I\kern-3.00003ptE}\left(Y_{t+1}\mid
Y_{t}\right)=X_{t+1}-{\rm I\kern-3.00003ptE}\left(X_{t+1}\mid X_{t}\right).$

By assumption (iii) in the statement, this implies

$\mathbb{P}\left(|M_{t+1}-M_{t}|>n^{\frac{1}{2}+\frac{\varepsilon}{4}}\right)\leq
2\exp\left(-2\,n^{\frac{\varepsilon}{2}}\right).$

By the union bound,

$\mathbb{P}\left(\exists s\leq
t,|M_{s+1}-M_{s}|>n^{\frac{1}{2}+\frac{\varepsilon}{4}}\right)\leq
2\,t\exp\left(-2\,n^{\frac{\varepsilon}{2}}\right).$

Let $\alpha=(a_{3}-a_{2})/4$, so that

$M_{0}+\alpha\,n=X_{0}+\alpha\,n=\frac{a_{2}+a_{3}}{2}\,n+\alpha\,n=a_{3}\,n-\alpha\,n,\qquad\text{
and }M_{0}-\alpha\,n=a_{2}\,n+\alpha\,n.$ (8)

By the  (Azuma-Hoeffding inequality). applied to
$\\{M_{t}\\}_{t\in\operatorname{\mathbb{N}}}$, we then have for every $t\leq
T$,

$\displaystyle\mathbb{P}\left(|M_{t}-M_{0}|>\alpha n\right)$
$\displaystyle\leq
2\exp\left(-\frac{\alpha^{2}n^{2}}{2\,t\,n^{1+\frac{\varepsilon}{2}}}\right)+2\,t\exp\left(-2\,n^{\frac{\varepsilon}{2}}\right)$
$\displaystyle\leq
2\exp\left(-\frac{\alpha^{2}n^{2}}{2\,T\,n^{1+\frac{\varepsilon}{2}}}\right)+2\,T\exp\left(-2\,n^{\frac{\varepsilon}{2}}\right)$
(since $t\leq T$) $\displaystyle=2\exp\left(-\frac{\alpha^{2}}{2}\cdot
n^{\frac{\varepsilon}{2}}\right)+2\,T\exp\left(-2\,n^{\frac{\varepsilon}{2}}\right).$
(since $T=n^{1-\varepsilon}$)

By the union bound,

$\mathbb{P}\left(\exists t\leq T,|M_{t}-M_{0}|>\alpha n\right)\leq
2T\exp\left(-\frac{\alpha^{2}}{2}\cdot
n^{\frac{\varepsilon}{2}}\right)+2\,T^{2}\exp\left(-2\,n^{\frac{\varepsilon}{2}}\right)=o(n^{-2}).$
(9)

Finally, note that for $n$ large enough, $T=n^{1-\epsilon}<\alpha\,n$, and
hence,

$\displaystyle\mathbb{P}\left(\exists t\leq
T,M_{t}\notin\\{a_{2}\,n+T,\ldots,a_{3}\,n-T\\}\right)$
$\displaystyle\leq\mathbb{P}\left(\exists t\leq
T,M_{t}\notin\\{a_{2}\,n+\alpha\,n,\ldots,a_{3}\,n-\alpha\,n\\}\right)$
$\displaystyle=\mathbb{P}\left(\exists t\leq
T,|M_{t}-M_{0}|>\alpha\,n\\}\right)$ (by Eq. 8) $\displaystyle=o(n^{-2}),$ (by
Eq. 9)

which concludes the proof of Claim 8. ∎

Next, we use Claims 7 and 8 and Assumption (ii) of the theorem to show that
$Y_{t}$ can never jump over $M_{t}$, with high probability.

######  Claim 9.

With high probability, for every $t\leq T$, $M_{t}\geq Y_{t}$.

###### Proof.

We will be conditioning on the two following events:

$\displaystyle\mathcal{E}_{1}$ $\displaystyle:=\left\\{\forall t\leq T,\quad
Y_{t}<a_{1}\,n-t\implies Y_{t+1}\leq a_{2}\,n-t\right\\},$
$\displaystyle\mathcal{E}_{2}$ $\displaystyle:=\left\\{\forall t\leq T,\quad
a_{2}\,n+T<M_{t}<a_{3}\,n-T\right\\}.$

Note that $\mathcal{E}_{2}$ happen w.h.p. as a consequence of Claim 8.
Moreover,

$\displaystyle\mathbb{P}(\mathcal{E}_{1})$
$\displaystyle=1-\mathbb{P}\left(\bigcup\limits_{t=0}^{T}\\{Y_{t}\leq
a_{1}\,n-t\\}\mathbin{\scalebox{1.5}{$\cap$}}\\{Y_{t+1}>a_{2}\,n-t\\}\right)$
$\displaystyle=1-\mathbb{P}\left(\bigcup\limits_{t=0}^{T}\\{X_{t}\leq
a_{1}\,n\\}\mathbin{\scalebox{1.5}{$\cap$}}\\{X_{t+1}>a_{2}\,n\\}\right)$
$\displaystyle\geq 1-\sum_{t=0}^{T}\mathbb{P}\left(X_{t}\leq
a_{1}\,n~{}\mathbin{\scalebox{1.5}{$\cap$}}~{}X_{t+1}>a_{2}\,n\right)$ (by the
union bound) $\displaystyle\geq
1-\sum_{t=0}^{T}\mathbb{P}\left(X_{t+1}>a_{2}\,n\mid X_{t}\leq
a_{1}\,n\right)$ $\displaystyle\geq 1-T\exp\left(-n^{\Omega(1)}\right)$ (by
assumption (ii)) $\displaystyle\geq 1-o(n^{-2}).$ (since
$T=n^{1-\varepsilon}$)

Hence, $\mathcal{E}_{1}$ also happens w.h.p., and so does
$\mathcal{E}_{1}\mathbin{\scalebox{1.5}{$\cap$}}\mathcal{E}_{2}$. To conclude
the proof, we will show that

$\mathcal{E}_{1}\mathbin{\scalebox{1.5}{$\cap$}}\mathcal{E}_{2}\implies\forall
t\leq T,M_{t}\geq Y_{t}.$ (10)

We will proceed by induction on $t$. By definition, we have $M_{0}=Y_{0}$.
Now, let $t<T$, and consider the case that $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$ hold, and that $M_{t}\geq Y_{t}$.

  * •

If $Y_{t}<a_{1}\,n-t$, we have

$Y_{t+1}\underset{(\mathcal{E}_{1})}{\leq}a_{2}\,n-t\leq
a_{2}\,n+T\underset{(\mathcal{E}_{2})}{<}M_{t+1}.$

  * •

Otherwise, by induction hypothesis and $\mathcal{E}_{2}$, we have
$a_{1}\,n-t\leq Y_{t}\leq M_{t}<a_{3}n-T<a_{3}n-t$. In this case, $M_{t+1}\geq
Y_{t+1}$ follows as a consequence of Claim 7.

By induction, we deduce that Eq. 10 hold, which concludes the proof of Claim
9. ∎

Finally, we are ready to conclude. By Claim 9, with high probability, for
every $t\leq T$, $X_{t}\leq M_{t}+t$. Therefore,

$\inf\\{t\in\operatorname{\mathbb{N}},X_{t}>a_{3}n\\}\geq\inf\\{t\in\operatorname{\mathbb{N}},M_{t}>a_{3}n-t\\}\quad\text{w.h.p.}$

Moreover, by Claim 8,

$\inf\\{t\in\operatorname{\mathbb{N}},M_{t}>a_{3}n-t\\}>T\quad\text{w.h.p.},$

which gives the desired result. ∎

By symmetry, the following result can be deduced directly from Theorem 6.

######  Corollary 10.

Let $\\{X_{t}\\}$ be a Markov chain on $\mathbb{Z}$ and $\varepsilon>0$. If
there are $a_{1}<a_{2}<a_{3}\in\operatorname{\mathbb{R}}$ s.t.

  * (i)

for every $x_{t}\in\\{a_{1}\,n,...,a_{3}\,n\\}$, ${\rm
I\kern-3.00003ptE}(X_{t+1}\mid X_{t}=x_{t})\geq x_{t}-1$,

  * (ii)

for every $x_{t}>a_{3}\,n$, $\mathbb{P}(X_{t+1}<a_{2}\,n\mid
X_{t}=x_{t})=\exp(-n^{\Omega(1)})$,

  * (iii)

$\mathbb{P}(|X_{t+1}-{\rm I\kern-3.00003ptE}\left(X_{t+1}\mid
X_{t}\right)|>n^{1/2+\varepsilon/4})<2\exp\left(-2n^{\varepsilon/2}\right)$,

then for $X_{0}=\frac{a_{1}+a_{2}}{2}$ and for $n$ large enough, we have
w.h.p.

$\inf\\{t\in\operatorname{\mathbb{N}},X_{t}\leq a_{1}\,n\\}\geq
n^{1-\varepsilon}.$

###### Proof.

It is easy to check that if the assumptions of Corollary 10 hold for
$\\{X_{t}\\}_{t\in\operatorname{\mathbb{N}}}$ and some constants
$a_{1}<a_{2}<a_{3}$, then the assumptions of Theorem 6 hold w.r.t.
$\\{-X_{t}\\}_{t\in\operatorname{\mathbb{N}}}$ and $-a_{3}<-a_{2}<-a_{1}$
respectively – and the conclusion follows. ∎

##  4 The Main Proof

###  4.1 The Voter Dynamics

First, we focus on the Voter dynamics (Protocol 1) and show that it satisfies
the lower bound stated in Theorem 1, which we will prove in its full
generality in Section 4.2. We start by observing that for $g^{\textrm{voter}}$
defined in Eq. 1, and by definition in Eq. 3,

$F_{n}^{\textrm{voter}}(p)=-p+\sum_{k=0}^{\ell}\binom{\ell}{k}p^{k}(1-p)^{\ell-k}\cdot\frac{k}{\ell}=-p+p=0.$

Then, we conclude by applying the following result.

######  Lemma 11.

Consider a protocol $\mathcal{P}$ satisfying $F_{n}=0$ for every $n$ large
enough. There exists a sequence of configurations $\\{C_{n}\\}$ such that for
every $\epsilon>0$, with high probability,

$\tau(\mathcal{P},C_{n})>n^{1-\varepsilon}.$

###### Proof.

We want to apply Theorem 6 with $a_{1}=1/4$, $a_{2}=1/2$, $a_{3}=3/4$. If the
three hypotheses hold, we have for the initial configuration
$C_{n}:=(z=1,X_{0}=\frac{a_{2}\,n+a_{3}\,n}{2})$,

$\tau_{n}\\{\mathcal{P},C_{n}\\}\geq\inf\\{t\in\operatorname{\mathbb{N}},X_{t}>a_{3}n\\}\geq
n^{1-\varepsilon}.$

Now, let us show that the hypotheses hold:

  * (i)

Since $F_{n}=0$ for $n$ large enough, we have by Proposition 5

${\rm I\kern-3.00003ptE}(X_{t+1}\mid X_{t}=x_{t})\leq x_{t}+1.$

  * (ii),(iii)

We can apply  (Hoeffding’s bound).; conditioning on $X_{t}$, $X_{t+1}$ is sum
of $n$ Bernoulli random variables, then, choosing
$\delta=n^{1/2+\varepsilon/4}$, for any $\varepsilon>0$,

$\mathbb{P}(|X_{t+1}-{\rm I\kern-3.00003ptE}\left(X_{t+1}\mid
X_{t}\right)|>n^{1/2+\varepsilon/4})<2\exp\left(-2n^{\varepsilon/2}\right),$

proving (iii). Moreover, if $x_{t}<a_{1}\,n$ and $n$ large enough, (ii)
follows from

$\mathbb{P}(X_{t+1}>a_{2}n)\leq\mathbb{P}(X_{t+1}>n^{1/2+1/4}+{\rm
I\kern-3.00003ptE}\left(X_{t+1}\mid
X_{t}=x_{t}\right))<2\exp\left(-2n^{1/2}\right).$

∎

###  4.2 General Case

Our main result (Theorem 1) will follow as a consequence of Theorem 12 below.

######  Theorem 12.

For every $\varepsilon>0$ and every protocol $\mathcal{P}$, there exists an
infinite set $\mathcal{S}\subseteq\operatorname{\mathbb{N}}$ and a sequence of
configurations $\\{C_{n}\\}$ such that for every $n\in\mathcal{S}$,

$\mathbb{P}\left(\tau(\mathcal{P},C_{n})>n^{1-\varepsilon}\right)\geq
1-\frac{1}{n^{\Omega(1)}}.$

In other words, the convergence time of $\mathcal{P}$ restricted to
$\mathcal{S}$ is greater than $n^{1-\varepsilon}$ w.h.p.

###### Proof.

Recall the definition of $F_{n}$ in Eq. 3. If there is
$N\in\operatorname{\mathbb{N}}$ s.t. for every $n\geq N$, $F_{n}=0$, then we
can conclude by applying Lemma 11. Otherwise, there is an infinite set
$\mathcal{S}_{0}\subseteq\operatorname{\mathbb{N}}$ s.t. for every
$n\in\mathcal{S}_{0}$, $F_{n}\neq 0$, which we will assume from now on.

By definition in Eq. 3, $F_{n}$ is a polynomial of degree at most $\ell+1$.
For $n\in\mathcal{S}_{0}$, let $d_{n}$ be the number of roots of $F_{n}$ in
the interval $[0,1]$ (counted with multiplicity). By Proposition 3,
$g_{n}^{[0]}(0)=0$ and $g_{n}^{[1]}(\ell)=1$, so $F_{n}(0)=F_{n}(1)=0$, and
thus $d_{n}\in\\{2,\ldots,\ell+1\\}$. Since $d_{n}$ can only adopt finitely
many values, there exists $d\in\\{2,\ldots,\ell+1\\}$ and an infinite set
$\mathcal{S}_{1}\subseteq\mathcal{S}_{0}$ s.t. for every
$n\in\mathcal{S}_{1}$, $d_{n}=d$.

For $n\in\mathcal{S}_{1}$, let $0=r_{n}^{(1)}\leq\ldots\leq r_{n}^{(d)}=1$ be
the roots of $F_{n}$ within the interval $[0,1]$, with multiplicity, in
increasing order. The sequence $\big{\\{}(r_{n}^{(1)}\leq\ldots\leq
r_{n}^{(d)})\big{\\}}_{n\in\mathcal{S}_{0}}$ is bounded in
$\operatorname{\mathbb{R}}^{d}$ by definition. Hence, by the Bolzano-
Weierstrass theorem, there exists a converging sub-sequence of
$\big{\\{}(r_{n}^{(1)},\ldots,r_{n}^{(d)})\big{\\}}_{n\in\mathcal{S}_{0}}$;
i.e., there are $0=r_{\infty}^{(1)}\leq\ldots\leq r_{\infty}^{(d)}=1$ together
with an infinite set $\mathcal{S}_{2}\subseteq\mathcal{S}_{1}$ s.t. for every
$k\in[d]$,

$\lim_{\begin{subarray}{c}n\rightarrow+\infty\\\
n\in\mathcal{S}_{2}\end{subarray}}r_{n}^{(k)}=r_{\infty}^{(k)}.$ (11)

Let

$k_{0}:=\min\\{k\in[\ell],r_{\infty}^{(k)}=1\\}.$

Note that $k_{0}\geq 2$ (since $r_{\infty}^{(1)}=0$) and by definition,
$r_{\infty}^{(k_{0}-1)}<1=r_{\infty}^{(k_{0})}$. Moreover, for every
$n\in\mathcal{S}_{2}$, $F_{n}$ is non-zero and has constant sign on
$(r_{n}^{(k_{0}-1)},r_{n}^{(k_{0})})$. Therefore, there exists an infinite set
$\mathcal{S}_{3}\subseteq\mathcal{S}_{2}$ s.t.

  1. 1.

either $\forall n\in\mathcal{S}_{3}$, $F_{n}<0$ on
$(r_{n}^{(k_{0}-1)},r_{n}^{(k_{0})})$,

  2. 2.

or $\forall n\in\mathcal{S}_{3}$, $F_{n}>0$ on
$(r_{n}^{(k_{0}-1)},r_{n}^{(k_{0})})$.

In the remainder of the proof, we will analyse these two cases separately. The
reader is strongly encouraged to consult Figures 3 and 2 respectively for a
clearer understanding of the argument.

Figure 2: Illustration of the arguments for Case 1. We consider a
configuration in which the correct opinion is $1$. Constant $a_{1}$ is fixed
arbitrarily in the interval $(r_{\infty}^{(k_{0}-1)},1)$ Then, $a_{2}$ is
chosen according to Proposition 4 to ensure that $X_{t}$ cannot jump from
below $a_{1}\,n$ to above $a_{2}\,n$. Finally, $a_{3}$ is set anywhere in the
interval $(a_{2},1]$. By assumption, $F_{n}<0$ on $[a_{1},a_{3}]$, and we can
eventually apply Theorem 6.

#### Case 1.

Let $a_{1}\in(r_{\infty}^{(k_{0}-1)},1)$. Let
$a_{2}=a_{2}(a_{1},\ell)\in(a_{1},1)$ given by Proposition 4, s.t. for $n$
large enough,

$\text{for every }x_{t}\leq a_{1}\,n,\quad\mathbb{P}(X_{t+1}\leq a_{2}\,n\mid
X_{t}=x_{t})\geq 1-\exp(2\,n^{-1/2}).$

Let $a_{3}\in(a_{2},1)$. By Eq. 11, for $n$ large enough,
$r_{n}^{(k_{0}-1)}<a_{1}$ and $r_{n}^{(k_{0})}>a_{3}$. We now wish to use
Theorem 6, with $a_{1},a_{2},a_{3}$ as we just defined. Let us check that
every assumption holds:

  * •

For every $x_{t}\in\\{a_{1}\,n,\ldots,a_{3}\,n\\}$, we have
$x_{t}/n\in[a_{1},a_{3}]\subset[r_{n}^{(k_{0}-1)},r_{n}^{(k_{0})}]$, and so
$F_{n}(x_{t}/n)<0$ by assumption. Therefore, Eq. 5 gives

${\rm I\kern-3.00003ptE}\left(X_{t+1}\mid X_{t}=x_{t}\right)\leq
x_{t}+n\,F_{n}\left(\frac{x_{t}}{n}\right)+1<x_{t}+1,$ (12)

so assumption (i) in the statement of Theorem 6 holds.

  * •

Assumption (ii) holds by Proposition 4.

  * •

Finally, assumption (iii) follows from  (Hoeffding’s bound).: conditioning on
$X_{t}$, $X_{t+1}$ is sum of $n$ Bernoulli random variables, then the result
follow choosing $\delta=n^{1/2+\varepsilon/4}$.

Assuming that the source has opinion $z=1$, we apply Theorem 6, which implies
the existence of an initial configuration $C_{n}$ s.t. the convergence time is
bounded:

$\tau(g,C_{n})=\inf\\{t\in\operatorname{\mathbb{N}},X_{t}=n\\}\geq\inf\\{t\in\operatorname{\mathbb{N}},X_{t}\geq
a_{3}\,n\\}\geq n^{1-\varepsilon}.$

Figure 3: Illustration of the arguments for Case 2. We consider a
configuration in which the correct opinion is $0$. Constants $a_{1},a_{2}$ and
$a_{3}$ are chosen arbitrarily in the interval $(r_{\infty}^{(k_{0}-1)},1)$.
By assumption, $F_{n}>0$ on $[a_{1},a_{3}]$. Moreover, once $a_{2}$ and
$a_{3}$ are fixed, we give a lower-bound on $F_{n}$ on the interval
$[r_{n}^{(k_{0})},1]$, by letting $r_{n}^{(k_{0})}$ be sufficiently close to
$1$, in order to ensure that $X_{t}$ cannot jump from above $a_{3}\,n$ to
below $a_{2}\,n$. Eventually, we are able to apply Corollary 10.

#### Case 2.

Let $a_{1},a_{2},a_{3}\in(r_{\infty}^{(k_{0}-1)},1)$, with
$r_{\infty}^{(k_{0}-1)}<a_{1}<a_{2}<a_{3}<1$. First, we show that by taking
$n$ large enough, we can have $F_{n}$ be arbitrarily small on the interval
$[r_{n}^{(k_{0})},1]$.

######  Claim 13.

For every $\delta>0$, for $n$ large enough: $r_{n}^{(k_{0})}>(1+a_{3})/2$, and
for every $p\in[r_{n}^{(k_{0})},1]$, $F_{n}(p)>-\delta$.

###### Proof.

Let $\delta>0$ and $n\in\mathcal{S}_{2}$. Since $F_{n}$ has bounded
coefficients and degree $d$, and since $F_{n}(r_{n}^{(k_{0})})=F_{n}(1)=0$, by
Claim 17 in Appendix C we obtain the existence of $C_{0}$ s.t.

$\text{for every
}p\in[r_{n}^{(k_{0})},1],\quad|F_{n}(p)|<C_{0}\cdot(1-r_{n}^{(k_{0})}).$ (13)

By Eq. 11 and by definition of $k_{0}$, $r_{n}^{(k_{0})}$ tends to $1$ as $n$
goes to $+\infty$. If $n$ is large enough,

$r_{n}^{(k_{0})}>\max\left\\{1-\frac{\delta}{C_{0}},\frac{1+a_{3}}{2}\right\\}.$
(14)

By Eq. 13, this implies that $|F_{n}(p)|<\delta$ on $[r_{n}^{(k_{0})},1]$,
which, together with Eq. 14, concludes the proof of Claim 13. ∎

Now, we use the previous result to establish a lower bound on $p+F_{n}(p)$
when $p\geq a_{1}$.

######  Claim 14.

For $n$ large enough,

  * •

for every $p\in[a_{1},a_{3}]$, $p+F_{n}(p)>p$.

  * •

for every $p\in[a_{3},1]$, $p+F_{n}(p)>a_{3}$.

###### Proof.

For $p\in[a_{1},r_{n}^{(k_{0})})$, $F_{n}(p)>0$ by assumption. Therefore:

  * •

for every $p\in[a_{1},a_{3}]$, $p+F_{n}(p)>p$.

  * •

for every $p\in[a_{3},r_{n}^{(k_{0})})$, $p+F_{n}(p)>p\geq a_{3}$.

All is left to prove is that $p+F_{n}(p)>a_{3}$ on $[r_{n}^{(k_{0})},1]$. Let
$\delta=(1-a_{3})/2$, and let $n$ large enough for Claim 13 to hold w.r.t.
$\delta$. For every $p\in[r_{n}^{(k_{0})},1]$, we have

$\displaystyle p+F_{n}(p)$ $\displaystyle>r_{n}^{(k_{0})}-\delta$ (by Claim 13
and definition of $p$)
$\displaystyle=a_{3}+\left(\frac{1-a_{3}}{2}-\delta\right)+\left(r_{n}^{(k_{0})}-\frac{1+a_{3}}{2}\right)$
$\displaystyle>a_{3},$ (by Claim 13 and definition of $\delta$)

which concludes the proof of Claim 14. ∎

Finally, similarly to the first case, we use Corollary 10 to conclude. Again,
we start by checking that all assumptions hold. Let $n$ be large enough for
Claim 14 to hold.

  * •

For every $x_{t}\in\\{a_{1}\,n,\ldots,a_{3}\,n\\}$, we have
$x_{t}/n+F_{n}(x_{t}/n)>x_{t}/n$ by Claim 14. Therefore, Eq. 6 rewrites

${\rm I\kern-3.00003ptE}\left(X_{t+1}\mid X_{t}=x_{t}\right)\geq
x_{t}+n\,F_{n}\left(\frac{x_{t}}{n}\right)-1\geq x_{t}-1,$

so assumption (i) in the statement of Corollary 10 holds.

  * •

For every $x_{t}\in\\{a_{3}\,n,\ldots,n\\}$, we have
$x_{t}/n+F_{n}(x_{t}/n)>a_{3}$ by Claim 14. Therefore, Eq. 6 rewrites

${\rm I\kern-3.00003ptE}\left(X_{t+1}\mid X_{t}=x_{t}\right)\geq
x_{t}+n\,F_{n}\left(\frac{x_{t}}{n}\right)-1\geq a_{3}\,n-1.$

Therefore, by  (Hoeffding’s bound).,

$\displaystyle\mathbb{P}\left(X_{t+1}<a_{2}\,n\mid X_{t}=x_{t}\right)$
$\displaystyle\geq\mathbb{P}\left(X_{t+1}<{\rm
I\kern-3.00003ptE}\left(X_{t+1}\right)-\frac{a_{3}-a_{2}}{2}n\mid
X_{t}=x_{t}\right)$
$\displaystyle\leq\exp\left(-2\left(\frac{a_{3}-a_{2}}{2}\right)^{2}n\right),$

and so assumption (ii) holds.

  * •

Finally, assumption (iii) follows from  (Hoeffding’s bound)., as in the first
case.

Assuming that the source has opinion $z=0$, we apply Corollary 10, which
implies the existence of an initial configuration $C_{n}$ s.t. the convergence
time is bounded:

$\tau(g,C_{n})=\inf\\{t\in\operatorname{\mathbb{N}},X_{t}=0\\}\geq\inf\\{t\in\operatorname{\mathbb{N}},X_{t}\leq
a_{1}n\\}\geq n^{1-\varepsilon}.$

∎

##  5 Discussion and Future Works

In this paper, we explore the minimal requirements for simultaneously reaching
consensus and propagating information in a distributed system. We consider
memory-less and anonymous agents, which update their opinion synchronously
after observing the opinions of a few other agents sampled uniformly at
random, and whose goal is to converge on the correct opinion held by a single
“source” individual. In addition, we adopt the self-stabilizing framework,
which in a memory-less setting, means that convergence must happen for any
possible initialization of the opinions of the agents (including the source).
Under this model, we show that to obtain a convergence time better than
$n^{1-\epsilon}$, the number $\ell$ of samples obtained by each agent in every
round must necessarily tend towards infinity as $n$ increases. Our result
extends the range of values of $\ell$ for which the performance of the
“minority” dynamics (Protocol 2) is characterized. Our technique, which
consists in translating the sample size into the degree of a well-chosen
polynomial, and then inspecting its roots, is simple yet quite novel (to the
best of our knowledge), and may be used to show similar results in other
settings.

The ultimate goal of our work is to fully characterize the complexity of the
bit-dissemination problem in the parallel setting and in the absence of
memory, as a function of the sample size. Regarding values of $\ell$ allowing
poly-logarithmic convergence time, there is still a large gap between our
lower bound $\ell=\Omega(1)$ and the upper bound $\ell=O(\sqrt{n\log n})$
mentioned in [15]. Closing or narrowing this gap, even specifically for the
minority dynamics, would be of appreciable interest in our opinion.

Another natural continuation would be to generalize our result to protocols
using a constant amount of memory. If feasible, the resulting lower bound
would still be compatible with the algorithm of [7], which requires
$\Omega(\log\log n)$ bits of memory.

## Acknowledgements

We would like to thank Andrea Clementi for his feedback and organisational
role, Amos Korman for providing helpful comments and originally coming up with
the minority dynamics, and Luca Trevisan for initially suggesting to seek this
result and giving preliminary ideas.

## References

  * [1] Yehuda Afek, Noga Alon, Omer Barad, Eran Hornstein, Naama Barkai, and Ziv Bar-Joseph.  A biological solution to a fundamental distributed computing problem.  Science, 331(6014):183–185, January 2011.
  * [2] Ofer Feinerman, Amos Korman, Zvi Lotker, and Jean-Sebastien Sereni.  Collaborative search on the plane without communication.  In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, PODC ’12, pages 77–86, New York, NY, USA, July 2012. Association for Computing Machinery.
  * [3] Yuval Emek and Roger Wattenhofer.  Stone age distributed computing.  In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC ’13, pages 137–146, New York, NY, USA, July 2013. Association for Computing Machinery.
  * [4] Mohsen Ghaffari, Cameron Musco, Tsvetomira Radeva, and Nancy Lynch.  Distributed house-hunting in ant colonies.  In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15, pages 57–66, New York, NY, USA, July 2015. Association for Computing Machinery.
  * [5] Andrea Clementi, Francesco d’Amore, George Giakkoupis, and Emanuele Natale.  Search via parallel Lévy walks on z2.  In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC’21, pages 81–91, New York, NY, USA, July 2021. Association for Computing Machinery.
  * [6] Lucas Boczkowski, Amos Korman, and Emanuele Natale.  Minimizing message size in stochastic communication patterns: Fast self-stabilizing protocols with 3 bits.  In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, pages 2540–2559. Society for Industrial and Applied Mathematics, January 2017.
  * [7] Amos Korman and Robin Vacus.  Early adapting to trends: Self-stabilizing information spread using passive communication.  In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC’22, pages 235–245, New York, NY, USA, July 2022. Association for Computing Machinery.
  * [8] Étienne Danchin, Luc-Alain Giraldeau, Thomas J. Valone, and Richard H. Wagner.  Public information: From nosy neighbors to cultural evolution.  Science, 305(5683):487–491, July 2004.
  * [9] Ofer Feinerman and Amos Korman.  Individual versus collective cognition in social insects.  Journal of Experimental Biology, 220(1):73–82, January 2017.
  * [10] Melissa B. Miller and Bonnie L. Bassler.  Quorum sensing in bacteria.  Annual Review of Microbiology, 55(1):165–199, 2001.
  * [11] Anthony Trewavas.  Plant intelligence: Mindless mastery.  Nature, 415(6874):841–841, February 2002.
  * [12] David J. T. Sumpter, Jens Krause, Richard James, Iain D. Couzin, and Ashley J. W. Ward.  Consensus decision making by fish.  Current Biology, 18(22):1773–1777, November 2008.
  * [13] Tamás Vicsek and Anna Zafeiris.  Collective motion.  Physics Reports, 517(3):71–140, August 2012.
  * [14] Luca Becchetti, Andrea Clementi, Amos Korman, Francesco Pasquale, Luca Trevisan, and Robin Vacus.  On the role of memory in robust opinion dynamics.  In Edith Elkind, editor, Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, volume 1, pages 29–37, Macao, August 2023. International Joint Conferences on Artificial Intelligence Organization.
  * [15] Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, and Isabella Ziccardi.  The minority dynamics and the power of synchronicity.  In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, pages 4155–4176. Society for Industrial and Applied Mathematics, Alexandria, Virginia, U.S., January 2024.
  * [16] Mohsen Ghaffari and Johannes Lengler.  Nearly-tight analysis for 2-choice and 3-majority consensus dynamics.  In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC ’18, pages 305–313, New York, NY, USA, July 2018. Association for Computing Machinery.
  * [17] Luca Becchetti, Andrea Clementi, and Emanuele Natale.  Consensus dynamics: An overview.  ACM SIGACT News, 51(1):58–104, March 2020.
  * [18] James Aspnes and Eric Ruppert.  An introduction to population protocols.  In Benoît Garbinato, Hugo Miranda, and Luís Rodrigues, editors, Middleware for Network Eccentric and Mobile Applications, pages 97–120. Springer, Berlin, Heidelberg, 2009.
  * [19] M. Ballerini, N. Cabibbo, R. Candelier, A. Cavagna, E. Cisbani, I. Giardina, V. Lecomte, A. Orlandi, G. Parisi, A. Procaccini, M. Viale, and V. Zdravkovic.  Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study.  Proceedings of the National Academy of Sciences of the United States of America, 105(4):1232–1237, January 2008.
  * [20] William Bialek, Andrea Cavagna, Irene Giardina, Thierry Mora, Edmondo Silvestri, Massimiliano Viale, and Aleksandra M. Walczak.  Statistical mechanics for natural flocks of birds.  Proceedings of the National Academy of Sciences, 109(13):4786–4791, March 2012.
  * [21] Yael Katz, Kolbjørn Tunstrøm, Christos C. Ioannou, Cristián Huepe, and Iain D. Couzin.  Inferring the structure and dynamics of interactions in schooling fish.  Proceedings of the National Academy of Sciences, 108(46):18720–18725, November 2011.
  * [22] Bartłomiej Dudek and Adrian Kosowski.  Universal protocols for information dissemination using emergent signals.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 87–99, New York, NY, USA, June 2018. Association for Computing Machinery.
  * [23] Paul Bastide, George Giakkoupis, and Hayk Saribekyan.  Self-stabilizing clock synchronization with 1-bit messages.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, pages 2154–2173. Society for Industrial and Applied Mathematics, January 2021.
  * [24] V. Sood and S. Redner.  Voter model on heterogeneous graphs.  Physical Review Letters, 94(17):178701, May 2005.
  * [25] Ercan Yildiz, Asuman Ozdaglar, Daron Acemoglu, Amin Saberi, and Anna Scaglione.  Binary opinion dynamics with stubborn agents.  ACM Transactions on Economics and Computation, 1(4):19:1–19:30, December 2013.
  * [26] Mikaela Irene D. Fudolig and Jose Perico H. Esguerra.  Analytic treatment of consensus achievement in the single-type zealotry voter model.  Physica A: Statistical Mechanics and its Applications, 413:626–634, November 2014.
  * [27] Arpan Mukhopadhyay, Ravi R. Mazumdar, and Rahul Roy.  Binary opinion dynamics with biased agents and agents with different degrees of stubbornness.  In 2016 28th International Teletraffic Congress (ITC 28), pages 261–269, Würzburg, Germany, September 2016. IEEE.
  * [28] V. Moeinifar and S. Gündüç.  Zealots’ effect on opinion dynamics in complex networks.  Mathematical Modeling and Computing, 8(2):pp. 203, Wed, 05/05/2021 - 17:53.
  * [29] Fan Chung and Linyuan Lu.  Concentration inequalities and martingale inequalities: A survey.  Internet Mathematics, 3(1):79–127, January 2006.
  * [30] Yehuda Hassin and David Peleg.  Distributed probabilistic polling and applications to proportionate agreement.  Information and Computation, 171(2):248–268, December 2001.

##  Appendix A Probabilistic Tools

######  Theorem 15 (Hoeffding’s bound).

Let $X_{1},\ldots,X_{n}$ be i.i.d. random variables taking values in
$\\{0,1\\}$, let $X=\sum_{i=1}^{n}X_{i}$ and $\mu={\rm
I\kern-3.00003ptE}(X)=n\mathbb{P}(X_{1}=1)$. Then it holds for all $\delta>0$
that

$\mathbb{P}\left(X\geq\mu+\delta\right)\leq\exp\left(-\frac{2\delta^{2}}{n}\right).$

The following version of Azuma’s inequality, which accounts for the
possibility that the martingale makes a large jump with a small probability,
appears in [29, Section 8, p.34].

######  Theorem 16 (Azuma-Hoeffding inequality).

Let $(X_{t})_{t\in\operatorname{\mathbb{N}}}$ be a martingale, and let
$T\in\operatorname{\mathbb{N}}$. If there is $p>0$ and $c_{1},\ldots,c_{T}$
such that

$\mathbb{P}\left(\exists t\leq T,X_{t}-X_{t-1}>c_{t}\right)\leq p,$

then for every $\delta>0$,

$\mathbb{P}\left(|X_{T}-X_{0}|>\delta\right)\leq
2\exp\left(-\frac{\delta^{2}}{2\sum_{t=1}^{T}c_{t}^{2}}\right)+p.$

##  Appendix B Upper Bound for the Voter Dynamics

The following proof involves only classical arguments (see, for instance, [25]
and [30, Section 2.4]). We nonetheless present it here for the sake of
completeness.

###### Proof of Theorem 2.

The reader who is not already familiar with the idea is strongly encouraged to
refer to Figure 4 for an illustration.

Without loss of generality, we consider the Voter dynamics with $\ell=1$. In
this case, the sample $S_{t}^{(i)}$ of a non-source agent $i\neq 1$ in round
$t$ is simply an element of the set $I=\\{1,\ldots,n\\}$ of all agents, drawn
uniformly at random. In the case of the source, for the sake of the argument,
we let $S_{t}^{(1)}=1$ for every $t\in\operatorname{\mathbb{N}}$, i.e., we
consider that the source agent applies the Voter rule but always samples
itself.

Now, let us fix an horizon $T$. We will proceed by examining $n$ random walks
$\\{W_{T-t}^{(i)}\\}_{t\leq T}$, defined on the same randomness, but for which
the time flows backward. Specifically, for every $i\in I$, let
$W_{T}^{(i)}=i$, i.e., every random walk “starts” at a different position.
Moreover, for $t<T$, let

$W_{t}^{(i)}:=S_{t}^{\left(W_{t+1}^{(i)}\right)}.$

In other words, if a random walk is in position $j$ in round $t+1$, and if
Agent $j$ samples $i$ in round $t$, then the random walk “moves” to $i$ in
round $t$. Note that by definition, if a random walk moves to position $1$ in
round $t$, it will remain in position $1$ for all remaining rounds:

$W_{t}^{(i)}=1\implies\forall s\in\\{1,\ldots,t\\},W_{s}^{(i)}=1.$ (15)

Moreover, if the random walk indexed by $i$ ends up in position $1$ (in round
$1$), it implies that the agent of index $W_{t}^{(i)}$ holds the correct
opinion in round $t$:

$W_{1}^{(i)}=1\implies X_{t}^{\left(W_{t}^{(i)}\right)}=z.$ (16)

To show that, we can simply proceed by induction on $t$, using the definition
of the random walks. Eqs. 15 and 16 together implies that if the random walks
indexed by $i$ ever moves to position $1$, then Agent $i$ has the correct
opinion in round $T$:

$\exists t\leq T,W_{t}^{(i)}=1\implies X_{T}^{(i)}=z.$ (17)

Therefore, for every $i\neq 1$,

$\displaystyle\mathbb{P}\left(X_{T}^{(i)}\neq z\right)$
$\displaystyle\leq\mathbb{P}\left(\forall t\leq T,W_{t}^{(i)}\neq 1\right)$
(by Eq. 17)
$\displaystyle\leq\prod_{t=0}^{T-1}\mathbb{P}\left(S_{t}^{\left(W_{t+1}^{(i)}\right)}\neq
1\mid W_{t+1}^{(i)}\neq 1\right)$ (by the chain rule)
$\displaystyle=\left(1-\frac{1}{n}\right)^{T}.$ (since samples are uniform and
independent)

Note that this bound holds trivially for $i=1$. Therefore, by the union bound,

$\mathbb{P}\left(\forall i\in I,X_{T}^{(i)}=z\right)=1-\mathbb{P}\left(\exists
i\in I,X_{T}^{(i)}\neq z\right)\geq 1-\sum_{i\in
I}\mathbb{P}\left(X_{T}^{(i)}\neq z\right)\geq
1-n\left(1-\frac{1}{n}\right)^{T}.$

Taking $T=2n\log n$, for $n$ large enough,

$\left(1-\frac{1}{n}\right)^{2n\log n}=\exp\left(2n\log
n\log\left(1-1/n\right)\right)\leq\exp\left(-2\log n\right)=\frac{1}{n^{2}},$

which concludes the proof of Theorem 2. ∎

Figure 4: Depiction of the dual process behind the proof of Theorem 2. The
color of the circle in row $t$, column $i$, corresponds to the opinion of
Agent $i$ in round $t$: it is black if $X_{t}^{(i)}=1$, and white otherwise.
An arrow is drawn from $(i,t+1)$ to $(j,t)$ if $S_{t}^{(i)}=j$, i.e., if Agent
$i$ observes Agent $j$ in round $t$ (and thus adopts their opinion in round
$t+1$). Red circles depict the locations of $n$ coalescing random walks going
backward in time, and initially present at every location. Random walks at a
location $i>1$ make a move using the same randomness as the samples, while the
source acts like a sink. If all random walks have coalesced in less than $T$
rounds, it implies that the opinion of each agent in round $T$ comes from the
source, and thus that the dynamics has reached consensus on the correct
opinion.

##  Appendix C Missing Proofs

###### Proof of Proposition 3.

The main idea is that a protocol failing to satisfy these conditions cannot
enforce consensus. Assume, for the sake of contradiction, that
$g_{n}^{[0]}(0)>0$. Consider the starting configuration $C:=(z=0,X_{0})$ for
any value of $X_{0}$, and recall the definition of the convergence time of a
protocol $\mathcal{P}$:

$\tau_{n}(\mathcal{P},C):=\inf\\{t\geq 0,\text{ for every }s\geq
t,X_{s}=n\cdot z\\}.$

If for some $t$, $X_{t}=0$, we have

$\displaystyle\mathbb{P}(\cap_{s\geq t}\\{X_{s}=0\\})$
$\displaystyle=\prod_{s\geq
t}\mathbb{P}(\cap_{s=t}^{t+j}\\{X_{s}=0\\})\cdot\mathbb{P}(\cap_{s\geq
t}\\{X_{s}=0\\}\mid\cap_{s=t}^{t+j}\\{X_{s}=0\\}))$
$\displaystyle\leq\prod_{s\geq
t}\mathbb{P}(\cap_{s=t}^{t+j}\\{X^{(2)}_{s}=0\\})$ (for every
$j\in\operatorname{\mathbb{N}}$)
$\displaystyle=\left(1-g_{n}^{[0]}(0)\right)^{j},$

which tends to $0$ as $j$ tends to $+\infty$. We conclude that
$\tau_{n}(\mathcal{P},C)=+\infty$ almost surely, and hence, the protocol does
not solve the bit-dissemination problem. By symmetry, we obtain the other
statement about $g_{n}^{[1]}(\ell)$. ∎

######  Claim 17.

For every $M,d$, there exists $C_{0}=C_{0}(M,d)>0$ s.t. for every polynomial
$P$ of degree $d$ and coefficients bounded by $M$, every $a,b\in[0,1]$ with
$P(a)=P(b)=0$, and every $x\in[a,b]$, $P(x)<C_{0}\cdot(b-a)$.

###### Proof.

Since $P$ has degree $d$ and coefficients bounded by $M$, there exists
$C=C(M,d)$ s.t. $|P^{\prime}(x)|<C$ on $[0,1]$. Therefore, for every
$x\in[a,(a+b)/2]$, we have

$|P(x)|=|P(x)-P(a)|<C\cdot(x-a)<C\cdot\frac{b-a}{2}.$

Similarly, for every $x\in[(a+b)/2,b]$, we have

$|P(x)|=|P(b)-P(x)|<C\cdot(b-x)<C\cdot\frac{b-a}{2}.$

Taking $C_{0}=C/2$ concludes the proof of Claim 17. ∎


# The quasi bound spectrum of H2

E. M. Roueffa and H. Abgralla CONTACT E. M. Roueff. Email:
<EMAIL_ADDRESS>
Molecular Physics
https://www.tandfonline.com/doi/10.1080/00268976.2022.2122887 aObservatoire de
Paris, 5, Place J. Janssen, Meudon 92190, France

###### Abstract

We compute the radiative ro-vibrational emission spectrum of H2 involving
quasibound states via a simple numerical method of resolution of the
Schrödinger equation by introducing a modified effective molecular potential.
The comparison of the eigenvalues obtained with our approximation and other
theoretical methods based on scattering resonance properties is excellent.
Electric quadrupole and magnetic dipole contributions are calculated and we
confirm the previous computations of Forrey of the electric quadrupole
transition Einstein coefficients. The astrophysical relevance of such
quasibound levels is emphasized.

###### keywords:

Molecular Hydrogen; shape resonance; infrared;

##  1 Introduction

The presence of quasibound levels of molecular H2 located above its
dissociation limit is known since many years from its VUV emission spectrum,
as reported by Dabrowski [1] and Roncin & Launay [2].

The first tentative computations of quasibound levels have been performed by
Waech and Bernstein [3] by studying the energy dependence of the phase-shifts
in an analytic expansion of the H2 ground state potential. Schwenke [4],
followed by Selg [5], have subsequently developed theoretical methods to
compute the position and dissociation widths of the different quasibound
levels of H2 with the available numerical potential energy functions of H2
from the properties of the scattering matrix.

These levels, also defined as shape resonances [6], have however attracted
little interest until 2016 in the astrophysical community, where Forrey [7]
computed the enhancement in the H + H $\rightarrow$ H2 \+ $h\nu$ electric
quadrupole radiative association reaction provided by these resonances and its
potential relevance for the primordial universe chemistry. Forrey [7] also
computed the Einstein emission coefficients of the electric quadrupole
transitions involving quasibound - bound and quasibound - quasibound levels.
In the same year, Pike et al. [8] report several highly excited H2 transitions
observed in Herbig-Haro 7, including the (2-1)S(27) transition where the upper
level lies above the dissociation limit, corresponding thus to an upper
quasibound level, but no specific comment to this issue is discussed and the
value of the corresponding Einstein coefficient is missing without any further
remark.

The computations presented by Forrey [7] were subsequently vigorously
criticized by Pérez et al. [9] who claim for orders of magnitude different
values of the transition and dissociative probabililities. These last results
have been reasserted by Molano and Arango [10] who discuss phase-space
propagation and stability analysis of the 1-dimensional Schrödinger equation
for finding bound and resonance states of rotationally excited H2.

It is worth mentioning at this point that the Ubachs group in Amsterdam has
been able to probe some of these highly excited rotational quasibound levels
thanks to a new experimental setup involving three VUV lasers [11, 12] , where
highly rotationally excited H2 is produced from the photodissociation of H2S
induced by a 2-photon absorption experiment. These studies beautifully confirm
the energy level positions of H2 derived from the theoretical computations of
the ground state electronic potential of H2 by Czachorowski et al. [13].

We revisit in this paper the infrared spectrum of H2 involving its quasibound
levels and provide the associated transition wavenumbers and corresponding
Einstein emission coefficients. We introduce both the contribution of electric
quadrupole and magnetic dipole moments as first emphasized by Pachucki and
Komasa [14] and introduced by Roueff et al. [15] for the bound-bound infrared
spectrum of H2. We present in Section 2 the numerical method and the molecular
data used in the computations and report our results in Section 3. Our summary
and conclusions are given in Section 4.

##  2 Numerical computations

We are mainly interested in the electric quadrupole and magnetic dipole
transition matrix elements that allow to quantify the possible transition
intensities and take advantage of the previously computed quasibound energy
level positions [4, 5].

The procedure is the following: we extend, from the value $R=R_{max}$, the
effective potential energy function

$V_{eff}(R,J)=V(R)+\frac{\hbar^{2}J\,(J+1)}{2\mu R^{2}}$ (1)

by a constant value equal to the maximum of the bump induced by the
centrifugal barrier as displayed by the solid curve in Fig 1, that is defined
as $V_{eff}^{mod}(R,J)$ :

$\displaystyle V_{eff}^{mod}(R,J)$ $\displaystyle=$ $\displaystyle
V(R)+\frac{\hbar^{2}J\,(J+1)}{2\mu R^{2}}\,\,\,\,\,\,{\mbox{${ifR\leq
R_{max}}$}}$ $\displaystyle=$ $\displaystyle
V(R_{max})\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,{\mbox{${ifR\geq
R_{max}}$ }},$

The potential energy function $V(R)$ is the adiabatic potential of the X
ground state of H2 where the adiabatic correction computed in [16] is appended
to the Born-Oppenheimer interaction energy displayed in [17]. We then solve
the Schrödinger equation to find the bound levels within this potential using
our standard renormalized Numerov method [18]:

$-\frac{\hbar^{2}}{2\mu}\cdot\frac{d^{2}f_{v,J}(R)}{dR^{2}}+V_{eff}^{mod}(R,J)f_{v,J}(R)=E_{v,J}f_{v,J}(R)$
(3)

where $\mu=M_{\mathrm{p}}/2$ is the nuclear reduced mass of H2,

The step size in the radial variable is 0.01 au (atomic unit). We have
verified that reducing that value by a factor of two does not change the first
four numerical figures of the radiative emission rate. The maximum range over
which the wave-functions are propagated is 12 au. The reduced mass is taken as
918.0764 $m_{e}$111A more acccurate value is now available from CODATA21 [19]
but we keep the same value as in our previous calculations [20] to preserve
the consistency of our results.. The solutions found above the dissociation
limit at $V(R)=0$ correspond to the quasibound solutions.

Figure 1: Modified effective potential of H2 for J=29, $V_{eff}^{mod}$,
displayed as a full line and corresponding eigenvalues. $V_{eff}(R)$ is
displayed as a dotted line from $R=R_{max}$.

In the special case where J=29, corresponding to Figure 1, we obtain two bound
solutions corresponding to $v$ = 0 and 1 and three quasibound levels
corresponding to $v$ = 2, 3 and 4. The shape of the potential beyond the bump
corresponding to $R_{max}$ has in fact no influence on the search of bound
eigenvalues, as checked here for the positions of levels corresponding to
$v=0$ and 1. Table 2 displays the eigenvalues of the Schrödinger equation
corresponding to J=29 obtained with $V_{eff}$ and $V_{eff}^{mod}$. We also
report the values computed by Schwenke [4] with his adiabatic potential for
comparison in order to test our method within the closest approximation (see
below). The bound energies are identical with the two procedures. The
comparison between columns 3 and 4 concerning the quasibound levels (with
positive eigenvalues) is very impressive and the differences are less than a
wavenumber, except for the highest $v$, that is close to the maximum located
at 3403.209507 cm-1 (corresponding to 0.4219442eV) for J=29.

Eigenvalues of molecular H2 in its ground electronic state corresponding to
J=29.  $v$ $V_{eff}$ $V_{eff}^{mod}$ reported in [4] cm-1 cm-1 cm-1 0 -3693.15
-3693.15 1 -1471.81 -1471.81 2 — 473.39 474.14 3 — 2092.35 2092.99 4 — 3252.73
3251.01

We compare then in Table 2 the quasibound eigenvalues obtained with our
procedure (E${}_{adiab}^{pw}$) and the results reported in [4, 5], where the
authors determine the resonance parameters (position and width) from the poles
of the scattering matrix at complex energies [4] or by the detailed
investigation of the energy dependence of the phase shifts and amplitude of
the real stationary scattering-state function [5]. Schwenke [4] uses the Born-
Oppenheimer potential function of Kolos and Wolniewicz [21] (Eadiab) and
additional nonadiabatic correction (Enonadiab) whereas Selg [5] includes the
more recent calculations of Komasa et al. [22] (ESelg). Table 2 also displays
the available experimental determinations Eexp derived from the VUV spectra,
as reported from [5]. The values followed by ${\dagger}$ are the results
obtained in Lai et al. [23] from the previously quoted three VUV laser
experiment performed in Amsterdam.

The origin is taken at the dissociation limit. The eigenvalues obtained by
using our approximate method, using the most recent adiabatic potential
function, are within less than a wavenumber close to the adiabatic
computations of Schwenke [4]. Such an agreement fully corroborates our
approach, as the adiabatic potential functions used in the two computations
are very close.

Comparison between different methods to compute the eigenvalues of quasibound
levels of H2 and experimental derivations.  Eadiab Enonadiab ESelg Eexp
E${}_{adiab}^{pw}$ Eused Ref [4] [4] [5] present work $v_{u}$ $J_{u}$ cm-1
cm-1 cm-1 cm-1 cm-1 cm-1 0 32 432.68 428.28 … 431.82 428.28 1 31 1061.27
1056.79 … 1060.47 1056.79 2 29 474.14 469.65 469.81 470.09 473.39 469.81 5 24
233.77 229.44 229.32 229.11 233.16 229.32 3 29 2092.99 2088.70 2088.48 2088.59
2092.35 4 29 3251.01 3247.77 3247.69 3248.60 3252.73 3 28 1062.40 1057.98
1057.94 … 1061.71 4 28 2459.34 2455.46 2455.00 … 2459.09 4 27 1561.58 1557.38
1557.13 1556.93 1560.98 4 26 600.44 596.06 595.98 596.06 599.80 5 26 1948.26
1944.53 1944.08 1943.99 1948.02 5 25 1121.73 1117.63 1117.36 1117.37 1121.17 6
24 1523.54 1519.98 1519.53 1519.45 1523.33 6 23 772.07 768.08 767.79 767.81
771.54 7 22 1181.63 1178.28 1177.83 1177.76 1181.49 7 21 510.08 506.26 505.93
505.9310${\dagger}$ 509.60 8 20 917.19 914.11 913.67 913.76 917.20 8 19 331.40
327.78 327.43 327.4291${\dagger}$ 330.96 9 18 721.83 719.11 718.69 718.67
722.24 9 17 228.65 225.31 224.95 224.9410${\dagger}$ 228.25 10 16 581.81
579.61 579.25 … 583.29 10 15 189.78 186.83 186.46 186.4542${\dagger}$ 189.45
11 14 475.78 474.24 474.79 475.33 477.43 11 13 195.25 192.84 192.50
192.4945${\dagger}$ 195.08 Eexp are the experimental values deduced from the
VUV emission spectra [1] and reported in [5], except for the values with a
${\dagger}$ that are taken from the 3 VUV laser experiment [23].
E${}_{adiab}^{pw}$ is the value derived with our approximation of the modified
potential displayed in Fig 1. Eused is the value used for deriving the
transition wavenumbers displayed in Table 3.1.

We use then the $f_{v^{\prime},J^{\prime}}(R)$ eigenfunctions, solutions of
the radial Schrödinger equation (3), to compute the matrix elements of the
electric quadrupole and magnetic dipole moments within the X ground electronic
potential of H2, as in [15], and derive the corresponding Einstein emission
coefficients.

The electric quadrupole emission rate is given by

$\displaystyle W_{v^{\prime}J^{\prime}\rightarrow v"J"}^{EQ}$ $\displaystyle=$
$\displaystyle 2.797\times
10^{-23}\cdot\tilde{\nu}^{5}\cdot\frac{1}{(2J^{\prime}+1)}$
$\displaystyle\cdot\sum_{MM^{\prime}}|<J^{\prime}M^{\prime}f_{X,v^{\prime},J^{\prime}}(R)|Q(R)_{Wol}|J"M"f_{X,v",J"}(R)>|_{au}^{2}$

and the magnetic dipole emission rate is obtained from:

$W_{v^{\prime}J\rightarrow v"J}^{MD}=8.00\times
10^{-18}\cdot\tilde{\nu}^{3}\cdot
J(J+1)\cdot|<f_{X,v^{\prime},J}(R)|g(R)|f_{X,v",J}(R)>|^{2}$ (5)

The electric quadrupole moment $Q(r)_{Wol}$ and the magnetic dipole moment
$g(r)$ functions are taken respectively from [24] and [14] and expressed in
atomic units. The transition wavenumbers $\tilde{\nu}$ introduced in formulae
(4) and (5) are computed from the quasibound energy terms reported in column 8
of Table 2 that correspond to the most accurate values and are expressed in
reciprocal centimeters.

##  3 Results

###  3.1 Potentially observable radiative transitions involving quasibound
levels

Properties of the infrared spectrum emitted from quasibound levels of H2.
Transition $\tilde{\nu}$ $\tilde{\nu}^{adiab}$ $\lambda$ $\lambda^{adiab}$
$W^{EQ}$ $W^{EQ}_{Forrey}$ $W^{MD}$ At Ad Ek label cm-1 cm-1 $\mu$m $\mu$m s-1
s-1 s-1 s-1 s-1 cm-1 (0-0) S(30) 2721.56 2722.44 3.6744 3.6732 4.727E-06
4.73E-06 0.000E+00 4.727E-06 8.118E-23 428.28 (0-1) S(30) 620.50 620.79
16.1160 16.1085 3.601E-10 3.60E-10 0.000E+00 3.601E-10 8.118E-23 428.28 (1-0)
Q(31) 1974.02 1974.82 5.0658 5.0637 3.604E-09 3.60E-09 2.416E-07 5.219E-06
2.449E-07 1056.79 (1-0) S(29) 4752.38 4753.62 2.1042 2.1037 2.101E-06 2.10E-06
0.000E+00 5.219E-06 2.449E-07 1056.79 (1-1) S(29) 2531.65 2532.29 3.9500
3.9490 2.872E-06 2.87E-06 0.000E+00 5.219E-06 2.449E-07 1056.79 (1-2) S(29)
586.98 587.09 17.0364 17.0332 4.963E-10 4.96E-10 0.000E+00 5.219E-06 2.449E-07
1056.79 (2-0) O(31) 1387.04 1387.73 7.2096 7.2060 2.704E-11 2.70E-11 0.000E+00
5.482E-06 1.230E-13 469.81 (2-0) Q(29) 4165.40 4166.53 2.4007 2.4001 3.144E-08
3.14E-8 1.448E-08 5.482E-06 1.230E-13 469.81 (2-0) S(27) 7034.45 7035.97
1.4216 1.4213 2.240E-07 2.24E-7 0.000E+00 5.482E-06 1.230E-13 469.81 (2-1)
Q(29) 1944.67 1945.20 5.1423 5.1409 5.139E-09 5.15E-9 3.896E-07 5.482E-06
1.230E-13 469.81 (2-1) S(27) 4590.29 4591.18 2.1785 2.1781 2.944E-06 2.95E-6
0.000E+00 5.482E-06 1.230E-13 469.81 (2-2) S(27) 2399.19 2399.54 4.1681 4.1675
1.873E-06 1.87E-6 0.000E+00 5.482E-06 1.230E-13 469.81 (2-3) S(27) 489.60
489.53 20.4248 20.4279 2.582E-10 2.58E-10 0.000E+00 5.482E-06 1.230E-13 469.81
(5 -0) O(26) 8253.69 8255.664 1.2116 1.2113 4.366E-10 4.36E-10 0.000E+00
4.226E-06 1.354E-10 229.32 (5 -0) Q(24) 11205.89 11208.21 0.8924 0.8922
1.005E-09 1.01E-10 1.742E-11 4.226E-06 1.354E-10 229.32 (5 -0) S(22) 14176.89
14179.51 0.7054 0.7052 4.462E-09 4.46E-9 0.000E+00 4.226E-06 1.354E-10 229.32
(5 -1) O(26) 5704.04 5705.38 1.7531 1.75273 3.225E-09 3.23E-09 0.000E+00
4.226E-06 1.354E-10 229.32 (5 -1) Q(24) 8455.09 8456.74 1.1827 1.1825
1.758E-08 1.76E-8 2.025E-10 4.226E-06 1.354E-10 229.32 (5 -1) S(22) 11236.10
11238.042 0.8900 0.8898 1.141E-08 1.14E-8 0.000E+00 4.226E-06 1.354E-10 229.32
(5 -2) O(26) 3399.86 3400.63 2.9413 2.94063 9.871E-10 9.83E-10 0.000E+00
4.226E-06 1.354E-10 229.32 (5 -2) Q(24) 5939.36 5940.42 1.6837 1.6834
1.038E-07 1.04E-7 3.835E-09 4.226E-06 1.354E-10 229.32 (5 -2) S(22) 8524.34
8525.67 1.1731 1.1729 1.250E-08 1.25E-8 0.000E+00 4.226E-06 1.354E-10 229.32
(5 -3) O(26) 1363.64 1363.95 7.3333 7.3317 7.582E-10 7.57E-10 0.000E+00
4.226E-06 1.354E-10 229.32 (5 -3) Q(24) 3673.35 3673.90 2.7223 2.7219
1.159E-07 1.16E-7 1.000E-07 4.226E-06 1.354E-10 229.32 (5 -3) S(22) 6051.26
6052.04 1.6525 1.6523 8.018E-07 8.02E-7 0.000E+00 4.226E-06 1.354E-10 229.32
(5 -4) Q(24) 1680.50 1680.67 5.9506 5.9500 1.238E-09 1.24E-9 4.252E-07
4.226E-06 1.354E-10 229.32 (5 -4) S(22) 3832.39 3832.73 2.6093 2.6091
2.269E-06 2.27E-6 0.000E+00 4.226E-06 1.354E-10 229.32 (5 -5) S(22) 1892.38
1892.42 5.2843 5.2842 3.527E-07 3.53E-7 0.000E+00 4.226E-06 1.354E-10 229.32
(5 -6) S(22) 271.92 271.91 36.776 36.777 1.658E-11 1.65E-11 0.000E+00
4.226E-06 1.354E-10 229.32 $\tilde{\nu}$, $\tilde{\nu}^{adiab}$ are the
transition wavenumbers computed respectively from Eused, E${}^{pw}_{adiab}$ in
Table 2, whereas $\lambda$, $\lambda^{adiab}$ are the corresponding
wavelengths. $W^{EQ}$ is the electric quadrupole contribution to the Einstein
radiative emission coefficient from the present computations.
$W^{EQ}_{Forrey}$ is the value reported from [7]. $W^{MD}$ is the magnetic
dipole contribution to the Einstein radiative emission coefficients. At and Ad
are the total radiative decay rate and the dissociation rate of the upper
level. Ek is the quasibound upper level energy position above the dissociation
limit.

Whereas the full set of radiative transition emission rates between quasibound
- bound and quasibound - quasibound levels is computed and available on
request, we only report in Table 3.1 the potentially infrared observable
transitions involving upper quasibound levels for which the dissociation rate
Ad is significantly smaller than the total radiative decay rate At. The most
accurate transition wavenumbers and associated wavelengths correspond to
columns 2 and 4.

One such transition, (2-1) S(27), has already been reported in the literature
[8], but the Einstein coefficient was not available, preventing any physical
interpretation. We also point out that an unidentified transition reported at
2.1044 $\mu$m in [8] could correspond to our prediction of the (1-0) S(29)
transition at 2.1042 $\mu$m that has a relatively strong Einstein coefficient
of 2.1 $\times$ 10-6 s-1 and corresponds to an upper energy level at 1056.79
cm-1 above the dissociation limit, equivalent to an energy of 53,489 K above
$v=0,J=0$, the ground rovibrational level of H2.

We do not discuss here the derivation of the dissociation rate Ad, nor the
associated resonance width $\tilde{\Gamma}=A_{d}/(2\pi c)$ and take the values
reported in [5]. We note that the magnetic dipole contribution may
significantly exceed the electric quadrupole, as in the case of the (1-0 )
Q(31), (2-1) Q(29) and (5-4) Q(24) transitions. The uncertainty linked to the
quasibound level positions is emphasized by the comparison between
$\tilde{\nu}$, $\tilde{\nu}^{adiab}$ and $\lambda$, $\lambda^{adiab}$ and is
shown to be very small. We have checked that they have no impact on the
transition emission rate values reported in Table 3.1. We also report the
values of the electric quadrupole transition emission rates calculated in [7]
for which the agreement is found excellent, confirming thus their approach and
contradicting the claims and the results displayed in [9, 10]. We note in
passing that the predicted transition (1-2) S(29) at 17.03 $\mu$m takes place
between two quasibound levels. The dissociation rate of the lower level $v$ =
2, $J$ = 29 is much less than that of the upper level $v=1,J=31$. Then the
dissociation rate is given by the value corresponding to the upper level.

###  3.2 The $v=14,\,J=4$ case

The $v=14,J=4$ level deserves a special comment as it is not clear presently
if this level is above or below the dissociation limit. When using the
potential function of [13], solving the Schrödinger equation results in a
level that is slightly bound, at a level of ${-0.0274}$ cm-1. The combination
of various Lyman transition wavenumbers involving $v=14,J=4$ by Selg [5] does
not lead to conclusive results. We display the corresponding infrared emission
spectrum arising from $v=14,J=4$ in the separate Table 3.2, that could bring
an additional experimental possibility to probe the nature of that energy
level. The dissociation rate is strictly 0 if the level is bound. Selg [25]
suggests that this level becomes quasibound thanks to the hyperfine structure
effect and obtains a width $\Gamma$ of 2.1338 $\times$ 10-18 eV, corresponding
to a lifetime of 308 s and a dissociation rate of 3.2 $\times$ 10-3 s-1.
Whereas this lifetime is large for terrestrial laboratory conditions, it is
short at the astrophysical scales. That value is also claimed to be rather
sensitive to the relativistic and quantum electrodynamics corrections [25] .

Characteristics of the infrared spectrum arising from the level $v=14$ and
$J$=4 of H2.  Transition $\tilde{\nu}^{adiab}$ $\tilde{\nu}$ $\lambda^{adiab}$
$\lambda$ $W^{EQ}$ $W^{EQ}_{Forrey}$
$W^{EQ}_{\rm{J{\acute{o}}{\acute{z}}wiak}}$ $W^{MD}$ label cm-1 cm-1 $\mu$m
$\mu$m s-1 s-1 s-1 s-1 (14-0) O(6) 33703.15 33704.60 0.2967 0.2967 7.675E-13
7.12E-13 3.949E-13 0.000E+00 (14-0) Q(4) 34949.24 34950.76 0.2861 0.2861
1.402E-14 1.12E-14 1.141E-14 1.907E-17 (14-0) S(2) 35763.67 35765.22 0.2796
0.2796 4.301E-13 4.25E-13 3.674E-13 0.000E+00 (14-1) O(6) 29663.65 29664.29
0.3371 0.3371 8.827E-12 8.34E-12 4.629E-12 0.000E+00 (14-1) Q(4) 30846.66
30847.35 0.3242 0.3242 1.453E-15 2.44E-15 3.318E-15 6.459E-16 (14-1) S(2)
31620.20 31620.92 0.3163 0.3162 7.831E-12 7.46E-12 6.491E-12 0.000E+00 (14-2)
O(6) 25856.91 25856.81 0.3867 0.3867 5.045E-11 4.76E-11 2.627E-11 0.000E+00
(14-2) Q(4) 26978.14 26978.08 0.3707 0.3707 7.424E-13 7.42E-13 7.096E-13
7.808E-15 (14-2) S(2) 27711.68 27711.65 0.3609 0.3609 6.921E-11 6.62E-11
5.802E-11 0.000E+00 (14-3) O(6) 22278.93 22278.15 0.4489 0.4489 1.788E-10
1.71E-11 9.437E-11 0.000E+00 (14-3) Q(4) 23339.23 23338.49 0.4285 0.4285
1.960E-11 1.82E-11 1.755E-11 5.037E-14 (14-3) S(2) 24033.34 24032.62 0.4161
0.4161 4.159E-10 3.94E-10 3.458E-10 0.000E+00 (14-4) O(6) 18927.65 18926.27
0.5283 0.5284 4.356E-10 4.13E-10 2.276E-10 0.000E+00 (14-4) Q(4) 19927.34
19925.99 0.5018 0.5019 1.794E-10 1.72E-10 1.660E-10 2.697E-13 (14-4) S(2)
20582.30 20580.96 0.4859 0.4859 1.843E-09 1.76E-9 1.543E-09 0.000E+00 (14-5)
O(6) 15803.22 15801.29 0.6328 0.6329 6.710E-10 6.44E-10 3.547E-10 0.000E+00
(14-5) Q(4) 16742.01 16740.11 0.5973 0.5974 1.059E-09 1.00E-9 9.695E-10
1.122E-12 (14-5) S(2) 17357.70 17355.81 0.5761 0.5762 6.535E-09 6.21E-9
5.449E-09 0.000E+00 (14-6) O(6) 12908.28 12905.89 0.7747 0.7748 4.900E-10
4.62E-10 2.547E-10 0.000E+00 (14-6) Q(4) 13785.19 13782.81 0.7254 0.7255
4.521E-09 4.31E-9 4.162E-09 3.697E-12 (14-6) S(2) 14361.03 14358.67 0.6963
0.6964 1.895E-08 1.80E-8 1.583E-08 0.000E+00 (14-7) O(6) 10248.53 10245.76
0.9757 0.9760 6.814E-11 6.13E-11 3.416E-11 0.000E+00 (14-7) Q(4) 11061.63
11058.86 0.9040 0.9042 1.611E-08 1.53E-8 1.477E-08 8.560E-12 (14-7) S(2)
11596.54 11593.76 0.8623 0.8625 4.700E-08 4.46E-10 3.919E-08 0.000E+00 (14-8)
O(6) 7833.35 7830.29 1.2766 1.2771 8.648E-09 8.28E-9 4.589E-09 0.000E+00
(14-8) Q(4) 8579.59 8576.52 1.1656 1.1660 4.628E-08 4.41E-8 4.265E-08
1.649E-11 (14-8) S(2) 9071.74 9068.66 1.1023 1.1027 9.460E-08 9.01E-8
7.916E-08 0.000E+00 (14-9) O(6) 5676.83 5673.63 1.7615 1.7625 4.647E-08
4.40E-8 2.436E-08 0.000E+00 (14-9) Q(4) 6351.62 6348.38 1.5744 1.5752
8.297E-08 7.86E-8 7.607E-08 8.284E-11 (14-9) S(2) 6798.30 6795.03 1.4710
1.4717 1.210E-07 1.15E-7 1.008E-07 0.000E+00 (14-10) O(6) 3799.29 3796.14
2.6321 2.6343 5.795E-08 5.49E-8 3.042E-08 0.000E+00 (14-10) Q(4) 4395.87
4392.63 2.2749 2.2765 5.714E-08 5.42E-8 5.244E-08 6.860E-10 (14-10) S(2)
4793.09 4789.80 2.0863 2.0878 5.673E-08 5.38E-8 4.731E-08 0.000E+00 (14-11)
O(6) 2229.54 2226.70 4.4852 4.4910 1.336E-08 1.26E-8 6.997E-09 0.000E+00
(14-11) Q(4) 2737.94 2734.94 3.6524 3.6564 6.916E-09 6.54E-9 6.326E-09
2.260E-09 (14-11) S(2) 3079.90 3076.81 3.2469 3.2501 1.796E-09 1.70E-9
1.484E-09 0.000E+00 (14-12) O(6) 1008.78 1006.64 9.9130 9.9340 1.804E-10
1.69E-10 9.403E-11 0.000E+00 (14-12) Q(4) 1413.76 1411.35 7.0734 7.0854
2.739E-11 2.61E-11 2.568E-11 1.744E-09 (14-12) S(2) 1691.82 1689.27 5.9108
5.9197 1.349E-09 1.28E-9 1.130E-09 0.000E+00 (14-13) O(6) 199.07 198.21
50.2325 50.4513 1.164E-14 1.07E-14 6.157E-15 0.000E+00 (14-13) Q(4) 474.57
473.24 21.0717 21.13074 1.053E-11 9.82E-12 9.661e-12 1.422E-10 (14-13) S(2)
675.05 673.47 14.8136 14.8485 1.138E-10 1.07E-10 9.483E-11 0.000E+00 (14-14)
S(2) 94.92 94.90 105.3536 105.3695 7.280E-15 6.71E-15 6.049E-15 0.000E+00
$\tilde{\nu}^{adiab}$, $\tilde{\nu}$ are the transition wavenumbers computed
respectively from E ($v=14,J=4$) = -0.0273 cm-1, E ($v=14,J=4$) = 1.2467 cm-1
whereas $\lambda^{adiab}$ , $\lambda$ are the corresponding wavelengths.
$W^{EQ}$ is the electric quadrupole contribution to the Einstein coefficient
from the present computations. $W^{EQ}_{Forrey}$ and
$W^{EQ}_{\rm{J{\acute{o}}{\acute{z}}wiak}}$ are the values reported from [7]
and calculated from [26]. $W^{MD}$ is the magnetic dipole contribution. The
total radiative decay rate of v=4, J=4 is 6.991E-07 s-1.

However, we note that $J=4$ corresponds to para-H2, that implies that the
total nuclear spin is zero, cancelling possible hyperfine couplings and
degeneracy. The hyperfine components of all rovibrational quadrupole
transitions of o-H2 together with the single para-H2 transitions have in fact
been computed by [26] who use the potential function of [13] and the H2Spectre
code of Czachorowski222Fortran source code, 2019, ver7.0, University of
Warsaw, Poland; 2019
http://www.qcg.home.amu.edu.pl/qcg/public.html/H2Spectre.html.. We have
verified that the $\tilde{\nu}^{adiab}$ values reported in Table 3.2 are
perfectly corresponding to the transition frequencies reported in [26] for the
quadrupole emission transitions arising from $v=14,J=4$ (as well as for the
other transitions). However, the electric quadrupole transition emission rates
computed from [26] are slightly different from our values and those of [7] as
displayed in Table 3.2. We use the formula

$W_{v^{\prime}J^{\prime}\rightarrow v"J"}^{EQ}=2.797\times
10^{-23}\cdot\tilde{\nu}^{5}\cdot{\rm{Quad.\,Moment}}^{2}$

where $\tilde{\nu}={\rm{Frequency}}/c$, using the values ’Frequency’ and
’Quad. Moment’ reported in the supplementary information of [26]333$c$ is the
light velocity = 2.99792458e10 cm/s.. The values are within less than 20% for
Q and S transitions but they reach a systematic factor of about 2 for the O(6)
transitions. We find similar discrepancies for the O emission rates of other
para-H2 transitions whereas our computations agree very well with those of
Wolniewicz et al. [24].

The magnetic dipole contribution to the emission rate is found negligible here
compared to the electric quadrupole contribution. Detection of one of the
transitions displayed in Table 3.2 would require a dissociation rate
significantly smaller than the total radiative decay rate of 6.99 $\times$
10-7 s-1, corresponding to a lifetime larger than 16 days.

The comparison with the computations reported in [7] is again found very good
for the electric quadrupole emission rates. The only significant discrepancy
is obtained in the case of the (14-1) Q(4) electric quadrupole transition
emission rate for which a factor close to two is present. However, the
extremely low emission rate value of the order of 10-15 s-1 and a $\Delta
v=13$ gap explain the specific sensitivity of the corresponding matrix element
to the molecular parameters used in the computations.

##  4 Conclusions

We propose a new and simple way to compute radiative emission rates involving
quasibound state levels where the corresponding eigenfunction is computed as a
bound state trapped in a modified long range potential. We confirm the
approach of Forrey [7] and contradict the assertions of [9] in their
applications to electric quadrupole transitions in ground state molecular
Hydrogen. The procedure is valid for any diatomic system with a
${}^{1}\Sigma^{+}$ X ground state and easily extendable to an open shell
system where additional hamiltonian terms should be included. We provide
accurate wavelengths, wave-numbers and emission rates for both electric
quadrupole and magnetic dipole transitions in H2 thanks to the highly precise
molecular potential function including adiabatic and relativistic corrections
[13]. This is beautifully confirmed by the comparison with astrophysical
spectra [8] for the (2-1) S(27) transition at 2.1785 $\mu$m found towards the
shocked region Herbig-Haro 7. The corresponding upper level is quasibound and
located 470 cm-1 above the dissociation limit of H2 and the corresponding
Einstein coefficient is 2.94 $\times$ 10-6 s-1.

We also suggest that the unidentified transition reported at 2.1044 $\mu$m in
these same observations could correspond to (1-0) S(29), predicted at 2.1042
$\mu$m in our computations with a radiative transition emission rate of 2.1
$\times$ 10-6 s-1. The corresponding upper quasibound level is located at 1056
cm-1 above the dissociation limit in that case. This is the first time, to our
knowledge, that transitions emitted from quasibound levels are identified in
astrophysical environments. The role of quasibound levels is well recognized
in chemical reactivity [6, 27] but there are no study of their possible
collisional excitation in the literature. The total radiative decay of that
state is 5.22 $\times$ 10-6 s-1, whereas its dissociation rate is 2.45
$\times$ 10-7 s-1. Such an observation could then be used to constrain the
lifetime of that excited molecular hydrogen cloud, i.e. about or less than
1/(2.45 $\times$ 10-7) s-1, corresponding to less than 2 months! The present
identifications open a new challenge for studying astrophysical shocked
regions.

We finally predict the possible infrared spectrum emitted from $v=14,J=4$, a
level for which the quasibound nature is under debate. The para character of
that level implies a total nuclear spin $I=0$, preventing any hyperfine
splitting at long range, contrarily to the suggestion of [25].

## Acknowledgements

We thank the referees for useful comments and for driving our attention on the
$v=14,J=4$ level and to the reference [26]. We acknowledge support from the
Programme National de Physique et Chimie du Milieu Interstellaire (PCMI) of
CNRS/INSU with INC/INP co-funded by CEA and CNES.

## References

  * [1] I. Dabrowski, Canadian Journal of Physics 62, 1639 (1984).
  * [2] J.Y. Roncin and F. Launay, J. Phys. Chem. Ref. Data 4, 1 (1994).
  * [3] T.G. Waech and R.B. Bernstein, J. Chem. Phys.46 (12), 4905–4911 (1967).
  * [4] D.W. Schwenke, Theoretica Chimica Acta 74, 381–402 (1988).
  * [5] M. Selg, J. Chem. Phys.136 (11), 114113–114113 (2012).
  * [6] R.A. Bain and J.N. Bardsley, Journal of Physics B Atomic Molecular Physics 5 (2), 277–285 (1972).
  * [7] R.C. Forrey, Journal of Physics B Atomic Molecular Physics 49 (19), 194002 (2016).
  * [8] R.E. Pike, T.R. Geballe, M.G. Burton and A. Chrysostomou, ApJ822 (2), 82 (2016).
  * [9] K.D. Pérez, J.C. Arce and J.G. López, ApJS243 (1), 1 (2019).
  * [10] J.S. Molano and C.A. Arango, Chemical Physics Letters 762, 138171 (2021).
  * [11] K.F. Lai, E.J. Salumbides, W. Ubachs and M. Beyer, Phys. Rev. Lett.127 (18), 183001 (2021).
  * [12] K.F. Lai, M. Beyer, E.J. Salumbides and W. Ubachs, Journal of Physical Chemistry A 125 (5), 1221–1228 (2021).
  * [13] P. Czachorowski, M. Puchalski, J. Komasa and K. Pachucki, Phys. Rev. A98 (5), 052506 (2018).
  * [14] K. Pachucki and J. Komasa, Phys. Rev. A83 (3), 032501 (2011).
  * [15] E. Roueff, H. Abgrall, P. Czachorowski, K. Pachucki, M. Puchalski and J. Komasa, A&A630, A58 (2019).
  * [16] K. Pachucki and J. Komasa, J. Chem. Phys.141 (22), 224103 (2014).
  * [17] K. Pachucki, Phys. Rev. A 82, 032509 (2010).
  * [18] B.R. Johnson, J. Chem. Phys.67, 4086–4093 (1977).
  * [19] E. Tiesinga, P.J. Mohr, D.B. Newell and B.N. Taylor, Journal of Physical and Chemical Reference Data 50 (3), 033105 (2021).
  * [20] H. Abgrall, E. Roueff, F. Launay and J.Y. Roncin, Canadian Journal of Physics 72, 856 (1994).
  * [21] W. Kołos and L. Wolniewicz, J. Chem. Phys.43 (7), 2429–2441 (1965).
  * [22] J. Komasa, K. Piszczatowski, G. Łach, M. Przybytek, B. Jeziorski and K. Pachucki, Journal of Chemical Theory and Computation 7 (10), 3105–3115 (2011).
  * [23] K.F. Lai, E.J. Salumbides, M. Beyer and W. Ubachs, arXiv e-prints arXiv:2112.00817 (2021).
  * [24] L. Wolniewicz, I. Simbotin and A. Dalgarno, ApJS115, 293–313 (1998).
  * [25] M. Selg, EPL (Europhysics Letters) 96 (1), 10009 (2011).
  * [26] H. Jóźwiak, H. Cybulski and P. Wcisło, J. Quant. Spec. Radiat. Transf.253, 107186 (2020).
  * [27] H. Abgrall, A. Giusti-Suzor and E. Roueff, Astrophys. Journal Letters 207, L69–L72 (1976).