# Extended MSSM in Supersymmetric $\rm{SO}(10)$ Grand Unification

Sibo Zheng<EMAIL_ADDRESS>Department of Physics, Chongqing
University, Chongqing 401331, P. R. China

(August 3, 2018)

###### Abstract

We apply the perturbative grand unification due to renormalization to
distinguish TeV-scale relics of supersymmetric $\rm{SO}(10)$ scenarios. With
rational theoretical constraints taken into account, we find that for the
breaking pattern of either $\rm{SU}(5)$ or Pati-Salam only extra matter
$\mathbf{16}$ supermultiplet of $SO(10)$ can appear at TeV scale, apart from
MSSM spectrum.

##  I Introduction

The discovery of standard model (SM)-like Higgs 1207.7214 ; 1207.7235
provides a new portal to TeV-scale new physics at the LHC in the forthcoming
years. Among other things, such new physics models may reveal the “nature” of
SM-like Higgs, and offer a novel mechanism to stabilize divergence involving
SM Higgs. For those interesting scenarios in the literature, in this paper we
are restricted to the idea of supersymmetry (SUSY). Specifically, we will
utilize the grand unification (GUT) GG , which is one of the most beautiful
features delivered by SUSY, to distinguish TeV-scale relics of SUSY GUT
models. For reviews on this subject see e.g. Langacker ; SlanskyYR .

In the viewpoint of unification, the minimal supersymmetric standard model
(MSSM) can be embedded into conventional $SU(5)$ DG ; Sakai ; DRW , $SO(10)$
Georgi ; FM  or other GUT models with gauge groups of higher ranks. In the
light of our previous study on $SU(5)$ 1706.01071 , we will continue to
explore the TeV-scale relics of SUSY $SO(10)$ unification. Comparing with
$SU(5)$, the low-energy effective theories of $SO(10)$ are more complex. The
first major reason is that there may be multiple intermediate scales between
the weak and GUT scale. The second reason is that since a lot of higher-
dimensional representations of $SO(10)$ trivially satisfy gauge anomaly free
condition, the constraint imposed by this condition is much weaker in
$SO(10)$. Earlier studies on low-energy effective theory which is consistent
with perturbative SUSY $SO(10)$ unification are based on specific motivations
such as Higgs mass 0807.3055  and neutrino physics 9209215 ; 0408139 ;
0910.3924 .

Instead of particular phenomenological concerns, we will take a systematic
analysis on the low-energy effective theory. In order to simplify the analysis
on extra matter beyond the MSSM spectrum, we will explore $SO(10)$ scenarios
with the following theoretical features.

  * •

The $SO(10)$ unification is strictly perturbative.

  * •

In the chain of gauge symmetry breaking

$\displaystyle{}SO(10)\xrightarrow{H_{1}}G_{1}\xrightarrow{H_{2}}G_{2}\cdots\xrightarrow{H_{n}}G_{\text{SM}},$
(1)

where $G_{\text{SM}}$ refers to the SM gauge group. When the Higgs component
fields responsible for two nearby steps of gauge symmetry breaking can be
contained in a single Higgs supermultiplet, these two Higgs supermultiplets
will be identified as the same one. Otherwise, they differ from each other
111In this situation, the splitting between two nearby scales of gauge
symmetry breaking is generally large. We will impose the relatively strong
constraint that the two Higgs supermultiplets responsible for such large
splitting are forbidden to directly couple to each other..

  * •

In order to avoid dangerous mixings among Higgs vevs $\left<H_{i}\right>$, all
of $H_{i}$ are forbidden to directly couple to each other.

  * •

In order to avoid dangerous masses or mixing effects, neither the MSSM fields
nor extra matters are allowed to directly couple to any Higgs supermultiplets
$H_{i}$ in Eq. (1). 222There is a loophole. When the vev of the last Higgs
$\left<H_{n}\right>$ is of order TeV scale, they are allowed to couple to
$H_{n}$.

The main reason for the last point is that the vacuum expectations (vevs) of
$\left<H_{i}\right>$ would result in large matter masses or large mixing
effects if they were directly coupled to either MSSM fields or extra matters,
which would lead to them playing no role at weak scale. For example, coupling
a $\mathbf{54}$, which can break $SU(5)$ to SM gauge group, to MSSM Higgs
$\mathbf{10_{H}}$ through interaction
$\mathbf{54}\times\mathbf{10_{H}}\times\mathbf{10_{H}}$, yields unfavorable
Higgsino mass for a large vev of SM singlet in $\left<\mathbf{54}\right>$.

Theoretical constraints above have been partially imposed in the literature to
our knowledge. However, they have never been combined together to derive a
systematic analysis on the low-energy effective theory. The paper is organized
as follows. In Sec.II, we discuss the extra matter supermultiplets which are
consistent with our starting points in two well known patterns of gauge
symmetry breaking. In Sec.III, we examine the perturbative unification with
these representations. Finally, we conclude in Sec.IV.

##  II Representations

According to our starting points, in this section we investigate the
representation of extra matter which can directly couple to SM Higgs
$\mathbf{10_{H}}$ in the following two patterns of gauge symmetry breaking,

$\displaystyle{}\rm{A}:SO(10)$ $\displaystyle\xrightarrow{H_{1}}$
$\displaystyle SU(5)\xrightarrow{H_{2}}G_{\text{SM}},$
$\displaystyle\rm{B}:SO(10)$ $\displaystyle\xrightarrow{H_{1}}$ $\displaystyle
SU(4)_{c}\times SU(2)_{L}\times SU(2)_{R}$ $\displaystyle\xrightarrow{H_{2}}$
$\displaystyle SU(3)_{c}\times SU(2)_{L}\times SU(2)_{R}\times U(1)_{B-L}$
$\displaystyle\xrightarrow{H_{3}}$ $\displaystyle G_{\text{SM}}.$

Pattern A GN1 ; GN2 ; GN3 ; Rajpoot  is a two-step breaking with $SU(5)$
subgroup, and pattern B CEG ; PS ; M  is a three-step breaking referred to
Pati-Salam model PS .

Note, in the MSSM the SM fermion matters are described by $\mathbf{16}_{i}$ of
$SO(10)$ with index $i=1-3$, and the SM Higgs is contained in the
$\mathbf{10_{H}}$ of $SO(10)$. In particular, $\mathbf{16}_{i}$ contain three-
generation right-hand neutrinos, whereas $\mathbf{10_{H}}$ is composed of
$\mathbf{5_{H}}$ and $\mathbf{\bar{5}_{H}}$ of $SU(5)$ which contain the two
Higgs doublets of MSSM and two color-triplets.

###  II.1 $SU(5)$

In this pattern of symmetry breaking $H_{1}$ should contain an $SU(5)$
singlet, there are two candidates $H_{1}=\\{\mathbf{16},\mathbf{126}\\}$. The
second Higgs $H_{2}$ should contain a $\mathbf{24}$ of $SU(5)$, which
corresponds to three potential choices
$H_{2}=\\{\mathbf{45},\mathbf{54},\mathbf{210}\\}$. Since $H_{1}\neq H_{2}$,
we take the rational that the splitting between these two broken scales is
large.

With potential assignments on $H_{1}$ and $H_{2}$ above, there are six sets of
combinations. In each case, there may exist four types of dangerous gauge-
invariant superpotentials which violate the last two starting points in the
Sec.I:

$\displaystyle{}H_{1}$ $\displaystyle\times$
$\displaystyle\mathcal{N}\times\mathcal{N};$ $\displaystyle H_{2}$
$\displaystyle\times$ $\displaystyle\mathcal{N}\times\mathcal{N};$
$\displaystyle H_{1}$ $\displaystyle\times$ $\displaystyle
H_{2}\times\mathcal{N};$ $\displaystyle H_{1}$ $\displaystyle\times$
$\displaystyle H_{1}\times H_{2},~{}~{}~{}H_{2}\times H_{2}\times H_{1};$ (2)

where MSSM matter field $\mathcal{N}=\\{\mathbf{16}_{i},\mathbf{10_{H}}\\}$.
In Eq.(II.1), the first three types of superpotentials tender to seed Dirac or
Majorana masses to MSSM matters or MSSM Higgs doublets; and the last type of
gauge invariant superpotentials yields dangerous mixings between vevs of
$H_{1}$ and $H_{2}$.

Firstly, one finds a dangerous operator
$\mathbf{16}\times\mathbf{16}_{i}\times\mathbf{10_{H}}$ of the first type in
Eq.(II.1) which disfavors the choice $H_{1}=\mathbf{16}$. Secondly, due to
dangerous operator $\mathbf{126}\times\mathbf{210}\times\mathbf{10_{H}}$ the
set of $H_{1}=\mathbf{126}$ and $H_{2}=\mathbf{210}$ is also disfavored.
Therefore, we are left with two combinations $H_{1}=\mathbf{126}$ and
$H_{2}=\\{\mathbf{45},\mathbf{54}\\}$. In the case
$(H_{1},H_{2})=(\mathbf{126},\mathbf{54})$, there exists a dangerous operator
$\mathbf{126}\times\mathbf{126}\times\mathbf{54}$. In the last case
$(H_{1},H_{2})=(\mathbf{126},\mathbf{45})$, denote the new matter
supermultiplets with $\mathcal{M}$, we find that unsafe superpotentials
exclude
$\mathcal{M}=\\{\mathbf{10},\bar{\mathbf{16}},\mathbf{120},\mathbf{144},\bar{\mathbf{144}},\mathbf{210}\\}$,
leaving us only two possibilities,

$\displaystyle{}\mathbf{16}_{M}\times\mathbf{16}_{M}\times\mathbf{10_{H}},~{}~{}~{}~{}~{}~{}\mathbf{16}_{M}\times\mathbf{16}_{i}\times\mathbf{10_{H}}.$
(3)

In compared with breaking pattern A, there is another pattern of two-step
breaking 333The author thanks the referee for reminding us this case.

$\displaystyle SO(10)\xrightarrow{H_{1}}G_{\text{SM}}\times
U(1)\xrightarrow{H_{2}}G_{\text{SM}}.$

In this case, the potential choices are $H_{1}=\\{\mathbf{45},\mathbf{210}\\}$
and $H_{2}=\\{\mathbf{16},\mathbf{126}\\}$. According to Eq.(II.1), dangerous
operator $\mathbf{16}\times\mathbf{16}_{i}\times\mathbf{10_{H}}$ excludes the
case $H_{2}=\mathbf{16}$. Morevover, a dangerous operator
$\mathbf{210}\times\mathbf{126}\times\mathbf{10_{H}}$ excludes
$H_{1}=\mathbf{210}$. Therefore, there is only a viable combination
$(H_{1},H_{2})=(\mathbf{45},\mathbf{126})$, in which case the extra matter
$\mathcal{M}$ is similar to those of $SU(5)$ subgroup.

###  II.2 Pati-Salam

In this pattern of symmetry breaking, $H_{1}$ should contain a singlet of
$SU(4)_{c}\times SU(2)_{L}\times SU(2)_{R}$, which has two choices
$H_{1}=\\{\mathbf{54},\mathbf{210}\\}$. $H_{2}$ should contain a singlet of
$SU(3)_{c}$ and $U(1)_{B-L}$, which is a $\mathbf{15}$ of $SU(4)_{c}$. There
are two representations $H_{2}=\\{\mathbf{45},\mathbf{210}\\}$ of $SO(10)$
which include such a $\mathbf{15}$. Finally, $H_{3}=\mathbf{16}$ offers the
breaking of $SU(2)_{R}\times U(1)_{B-L}\rightarrow U(1)_{Y}$.

Since $\mathbf{210}$ contains both a singlet of $SU(4)_{c}\times
SU(2)_{L}\times SU(2)_{R}$ and a $\mathbf{15}$ of $SU(4)_{c}$, according to
the second starting point both $H_{1}$ and $H_{2}$ are identified as
$\mathbf{210}$. In this case, the three-step breaking is approximately two-
step. With $H_{1}=H_{2}=\mathbf{210}$ we are left with a single choice
$(H_{1},H_{2},H_{3})=(\mathbf{210},\mathbf{210},\mathbf{16})$, where similar
to previous discussions about $SU(5)$ there are four viable choices for extra
matters,

$\displaystyle{}\mathbf{16}_{M}$ $\displaystyle\times$
$\displaystyle\mathbf{16}_{M}\times\mathbf{10_{H}},~{}~{}~{}~{}\mathbf{10}_{M}\times\mathbf{54}_{M}\times\mathbf{10_{H}},$
$\displaystyle\mathbf{16}_{M}$ $\displaystyle\times$
$\displaystyle\mathbf{144}_{M}\times\mathbf{10_{H}},~{}~{}\mathbf{144}_{M}\times\bar{\mathbf{144}}_{M}\times\mathbf{10_{H}}.$
(4)

Note, unlike in pattern A, extra matter supermultiplets in Eq.(II.2) are
allowed to directly couple to $H_{3}$. Because the broken scale of
$SU(2)_{R}\times U(1)_{B-L}$ PS ; SU2m1 ; SU2m2  can be close to TeV scale
(see, e.g. SU2c1 ; SU2c2 ; SU2c3 ; SU2c4 ; SU2c5 ; SU2c6 ).

##  III Perturbative Unification

With the theoretical constraints in the Introduction, we have clarified that a
single or two $\mathbf{16}$ supermultiplets are allowed in pattern A, whereas
two $\mathbf{16}$s, a $\mathbf{10}$ with $\mathbf{54}$, a $\mathbf{16}$ with
$\mathbf{144}$ or a pair of vector-like $\mathbf{144}$ may appear in the
pattern B. Now, we examine whether any of them are consistent with the first
constraint - perturbative unification.

We start with the one-loop renormalization group equations (RGEs) for SM gauge
coupling constant,

$\displaystyle{}\frac{d}{dt}\alpha^{-1}_{i}=-\frac{b_{i}}{2\pi},$ (5)

where RG scale $t=\text{ln}\mu$ and coefficients
$b_{i}=(b_{U(1)_{Y}},b_{SU(2)_{L}},b_{SU(3)_{c}})$ are determined by Machacek1
; Machacek2 ,

$\displaystyle{}b_{i}=-\\{\frac{11}{3}C^{i}_{2}(G)-\frac{4}{3}\cdot\kappa\cdot
T(r_{f_{i}})-\frac{1}{6}T(r_{s_{i}})\\}.$ (6)

Here, $C_{2}(G)$ is the quadratic Casimir invariant, and $T(r)$ refers to
dynkin index that depends on details of the representation SlanskyYR .

###  III.1 $SU(5)$

In the case of $SU(5)$ subgroup there are two intermediate scales
$\Lambda_{\text{SUSY}}$ and $\Lambda_{5}$ between $M_{Z}$ and $\Lambda_{10}$,
corresponding to SUSY and $SU(5)$ breaking, respectively. The $b_{i}$
coefficients are given by 444In order to eliminate the triplet fields in
$\mathbf{10_{H}}$ some additional matter representations may be required as
well. Nevertheless, they are usually decoupled below the scale $\Lambda_{5}$,
which don’t affect the RG analysis between $M_{Z}$ and $\Lambda_{5}$.

$\displaystyle{}b_{i}$ $\displaystyle=$
$\displaystyle\begin{cases}(41/10,-19/6,-7),&\mu\in[M_{\text{Z}},\Lambda_{\text{SUSY}}]\\\
(33/5+\delta b_{1}(\mathbf{M}),1+\delta b_{2L}(\mathbf{M}),-3+\delta
b_{3}(\mathbf{M})),&\mu\in[\Lambda_{\text{SUSY}},\Lambda_{5}]\\\ \end{cases}$
$\displaystyle b_{5}$ $\displaystyle=$ $\displaystyle~{}~{}\delta
b_{5}(\mathbf{M}),~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\mu\in[\Lambda_{5},\Lambda_{10}]$
(7)

where $b_{5}$ denotes the $b$ coefficient of $SU(5)$ subgroup, and $\delta
b_{i}(\mathbf{M})$ refer to contributions to $b$ coefficients due to extra
matter. In particular, $\delta b_{i}(\mathbf{16}_{M})=(2,2,2)$ and $\delta
b_{i}(\mathbf{16}_{M}+\mathbf{16}_{M})=(4,4,4)$, respectively in Eq.(III.1).
Fig.1 shows the plots of RG running of SM gauge coupling constants according
to Eq.(III.1). It reveals that for $\Lambda_{\text{SUSY}}=1$ TeV the $SU(5)$
unification occurs at $\Lambda_{5}\simeq 10^{16.3}$ GeV. Moreover, the
$SO(10)$ unification in both cases can occur at $\Lambda_{10}$ large than
$10^{18}$ GeV. Comparing $\Lambda_{5}$ with $\Lambda_{10}$, one finds that
there is indeed sufficient splitting between them, which verifies previous
arguments.

Figure 1: One-loop RGEs for SM gauge coupling $\alpha^{-1}_{1}$ (green),
$\alpha^{-1}_{2}$ (blue) and $\alpha^{-1}_{3}$ (red) for extra matter
$\mathbf{16}_{M}$ (dashed) and $\mathbf{16}_{M}+\mathbf{16}_{M}$ (solid),
respectively. Here SUSY breaking scale $\Lambda_{\text{SUSY}}=1$ TeV.

###  III.2 Pati-Salam

In the case of Pati-Salam model there are two intermediate scales
$\Lambda_{\text{SUSY}}$ and $\Lambda_{\text{R}}$ between $M_{Z}$ and
$\Lambda_{10}$, which denotes SUSY and $SU(2)_{R}\times U(1)_{B-L}$ breaking
scale, respectively. In this case the coefficients $b_{i}$ are given by,

$\displaystyle{}b_{i}=\begin{cases}(41/10,-19/6,-7),&\mu\in[M_{\text{Z}},\Lambda_{\text{SUSY}}]\\\
(33/5+\delta b_{1}(\mathbf{M}),1+\delta b_{2}(\mathbf{M}),-3+\delta
b_{3}(\mathbf{M})),&\mu\in[\Lambda_{\text{SUSY}},\Lambda_{\text{R}}]\\\
\end{cases}$ (8)

for the RG scale between $M_{Z}$ and $\Lambda_{\text{R}}$, and

$\displaystyle{}b_{i}=(6+2+\delta b_{B-L}(\mathbf{M}),0+2+\delta
b_{2L}(\mathbf{M}),0+2+\delta b_{2R}(\mathbf{M}),-3+2+\delta
b_{3}(\mathbf{M})),~{}~{}\mu\in[\Lambda_{R},\Lambda_{10}]$

for the RG scale between $\Lambda_{\text{R}}$ and $\Lambda_{10}$. Above the RG
scale $\Lambda_{R}$, MSSM matters and Higgs field $H_{3}=\mathbf{16}$
contributes to $\delta b_{i}=(6,0,0,-3)$ and $\delta b_{i}=(2,2,2,2)$ in
Eq.(III.2), respectively. Regardless of what extra matter appears above
$\Lambda_{\text{SUSY}}$ and what kind of Higgs $H_{1,2,3}$ above
$\Lambda_{\text{R}}$, $SO(10)$ unification at the one-loop level yields
$\ln(\Lambda_{10}/\Lambda_{\text{R}})\simeq 2.53$ 9602391 ; 9911272 , which
uniquely determines $\Lambda_{\text{R}}$ once the content of extra matters is
identified.

Take a pair of $\mathbf{16}_{M}$ for example, they contribute to $\delta
b_{i}(\mathbf{M})=(4,4,4)$ and $\delta b_{i}(\mathbf{M})=(4,4,4,4)$ in Eq.(8)
and Eq.(III.2), respectively, which gives rise to $\Lambda_{\text{R}}\simeq
10^{15.5}$ GeV, unified gauge coupling $\alpha^{-1}\simeq 5.45$, and
$\Lambda_{10}\simeq 10^{16.7}$ GeV. Fig.2 shows the RG running of SM gauge
coupling constant, which offers us perturbative $SO(10)$ unification. Note,
the RG running of $SU(2)_{R}$ gauge coupling constant between $\Lambda_{R}$
and $\Lambda_{10}$ coincides with that of $SU(2)_{L}$, and as required
$\alpha^{-1}_{Y}$ is equal to
$\frac{3}{5}\alpha^{-1}_{2R}+\frac{2}{5}\alpha^{-1}_{B-L}$ at RG scale
$\Lambda_{R}$.

Repeat the analysis for other choices on extra matters in Eq.(II.2). We find
that in these cases $b$ coefficients such as $\delta
b_{i}(\mathbf{10}_{M}+\mathbf{54}_{M})=(11.5,11.5,11.5,11.5)$ are always too
large to support the idea of perturbative unification.

Figure 2: One-loop RGEs for SM gauge coupling $\alpha^{-1}_{1}$ (green),
$\alpha^{-1}_{2L}$ (blue), $\alpha^{-1}_{3}$ (red) and
$\alpha^{-1}_{\text{B-L}}$ (black) for extra matter
$\mathbf{16}_{M}+\mathbf{16}_{M}$. For $\Lambda_{\text{SUSY}}=1$ TeV one
obtains $\Lambda_{\text{R}}\simeq 10^{15.5}$ GeV and $\Lambda_{10}\simeq
10^{16.7}$ GeV. The RG running of $SU(2)_{R}$ gauge coupling constant between
$\Lambda_{R}$ and $\Lambda_{10}$ coincides with that of $SU(2)_{L}$.

##  IV Conclusion

In the forthcoming years we will enter into a new era of precise Higgs
physics, which means that studying new physics through the Higgs portal will
become very interesting. In this paper, we have utilized perturbative
unification due to renormalization to explore the low energy effective theory
of SUSY $SO(10)$ scenarios. With the rational theoretical constraints taken
into account, we find that for the breaking pattern of either $\rm{SU}(5)$ or
Pati-Salam only $\mathbf{16}$ supermultiplet can appear at TeV scale apart
from the MSSM spectrum.

The quarks or leptons in the $\mathbf{16}$ supermultiplet(s) can be either
chiral or vector-like. Note, vector-like fermion mass requires addition of SM
singlet (with vev of order TeV) which does not affect our discussions. While
the chiral case has been excluded, the vector-like quarks or leptons are
smoking guns in these SUSY $SO(10)$ scenarios. Moreover, the neutral fermions
of singlet or doublets of the $\mathbf{16}$ supermultiplet can serve as dark
matter totally, or partially with the neutralinos of the MSSM.

###### Acknowledgements.

The author is grateful to Dr. J. Zhang for discussions. This work is supported
in part by the National Natural Science Foundation of China under Grant
No.11775039 and the Fundamental Research Funds for the Central Universities
with project No. cqu2017hbrc1B05 at Chongqing University.

## References

  * (1) G. Aad et al. [ATLAS Collaboration], Phys. Lett. B716, 1 (2012), arXiv:1207.7214 [hep-ex].
  * (2) S. Chatrchyan et al. [CMS Collaboration], Phys. Lett. B716, 30 (2012), arXiv:1207.7235 [hep-ex].
  * (3) H. Georgi and S. L. Glashow, Phys. Rev. Lett. 32, 438 (1974).
  * (4) P. Langacker, Phys. Rept. 72, 185 (1981).
  * (5) R. Slansky, Phys. Rept. 79, 1 (1981).
  * (6) S. Dimopoulos and H. Georgi, Nucl. Phys. B 193, 150 (1981).
  * (7) N. Sakai, Z. Phys. C 11, 153 (1981).
  * (8) S. Dimopoulos, S. Raby and F. Wilczek, Phys. Rev. D 24, 1681 (1981).
  * (9) H. Georgi, in: Particles and Fields 1974, ed. C.E. Carlson (AIP, NY, 1975) p. 575.
  * (10) H. Fritzsch and P. Minkowski, Ann. Phys. 93, 193 (1975).
  * (11) S. Zheng, Eur. Phys. J. C 77, no. 9, 588 (2017), [arXiv:1706.01071 [hep-ph]].
  * (12) K. S. Babu, I. Gogoladze, M. U. Rehman and Q. Shafi, Phys. Rev. D 78, 055017 (2008). [arXiv:0807.3055 [hep-ph]].
  * (13) K. S. Babu and R. N. Mohapatra, Phys. Rev. Lett. 70, 2845 (1993), [hep-ph/9209215].
  * (14) H. S. Goh, R. N. Mohapatra and S. Nasri, Phys. Rev. D 70, 075022 (2004), [hep-ph/0408139].
  * (15) P. S. B. Dev and R. N. Mohapatra, Phys. Rev. D 81, 013001 (2010), [arXiv:0910.3924 [hep-ph]].
  * (16) H. Georgi and D.V. Nanopoulos, Phys. Lett. 82B , 392(1979).
  * (17) H. Georgi and D.V. Nanopoulos, Nucl. Phys. 155B, 52(1979).
  * (18) H. Georgi and D.V. Nanopoulos, Phys. Lett. 159B, 16 (1979).
  * (19) S. Rajpoot, Phys. Rev. D22, 2244 (1980).
  * (20) M.S. Chanowitz, J. Ellis and M.K. Galllard, Nucl. Phys. B128, 506 (1977).
  * (21) J. C. Pati and A. Salam, Phys. Rev. D 10, 275 (1974), Erratum: [Phys. Rev. D 11, 703 (1975)].
  * (22) A. Masiero, Phys. Lett. B93, 295 (1980).
  * (23) R. N. Mohapatra and J. C. Pati, Phys. Rev. D 11, 2558 (1975).
  * (24) G. Senjanovic and R. N. Mohapatra, Phys. Rev. D 12, 1502 (1975).
  * (25) G. Beall, M. Bander and A. Soni, Phys. Rev. Lett. 48, 848 (1982).
  * (26) G. Ecker, W. Grimus and H. Neufeld, Nucl. Phys. B 229, 421 (1983).
  * (27) P. Langacker and S. U. Sankar, Phys. Rev. D 40, 1569 (1989).
  * (28) Y. Zhang, H. An, X. Ji and R. N. Mohapatra, Nucl. Phys. B 802, 247 (2008), [arXiv:0712.4218 [hep-ph]].
  * (29) A. Maiezza, M. Nemevsek, F. Nesti and G. Senjanovic, Phys. Rev. D 82, 055022 (2010), [arXiv:1005.5160 [hep-ph]].
  * (30) S. Bertolini, A. Maiezza and F. Nesti, Phys. Rev. D 89, no. 9, 095028 (2014), [arXiv:1403.7112 [hep-ph]].
  * (31) M. E. Machacek and M. T. Vaughn, Nucl. Phys. B 236, 221 (1984).
  * (32) M. E. Machacek and M. T. Vaughn, Nucl. Phys. B 249, 70 (1985).
  * (33) M. Bastero-Gil and B. Brahmachari, Nucl. Phys. B 482, 39 (1996), [hep-ph/9602391].
  * (34) R. N. Mohapatra, [hep-ph/9911272].


††thanks: Present address: CERN, 1211, Geneva 23, Switzerland.††thanks:
Present address: Department of Physics, University of Liverpool, Liverpool,
L69 7ZE, United Kingdom††thanks: Present address: Université Paris-Saclay,
CNRS/IN2P3, IJCLab, 91405 Orsay, France.††thanks: Present address: Université
Paris-Saclay, CNRS/IN2P3, IJCLab, 91405 Orsay, France.††thanks: Present
address: Wako Nuclear Science Center (WNSC), Institute of Particle and Nuclear
Studies (IPNS), High Energy Accelerator Research Organization (KEK), Wako,
Saitama 351-0198, Japan††thanks: Present address: Institut für Kernphysik,
Technische Universität Darmstadt, 64289 Darmstadt, Germany.††thanks: Present
address: ARC Centre of Excellence for Engineered Quantum Systems, School of
Physics, The University of Sydney, NSW 2006, Australia.

# Laser spectroscopy of neutron-rich 207,208Hg isotopes: Illuminating the kink
and odd-even staggering in charge radii across the $N=126$ shell closure

T. Day Goodacre<EMAIL_ADDRESS>The University of Manchester, School
of Physics and Astronomy, Oxford Road, M13 9PL Manchester, United Kingdom
CERN, CH-1211 Geneva 23, Switzerland  TRIUMF, Vancouver V6T 2A3, Canada  A.V.
Afanasjev  Department of Physics and Astronomy, Mississippi State University,
MS 39762, USA  A.E. Barzakh  Petersburg Nuclear Physics Institute, NRC
Kurchatov Institute, Gatchina 188300, Russia  B.A. Marsh  CERN, CH-1211 Geneva
23, Switzerland  S. Sels  CERN, CH-1211 Geneva 23, Switzerland  KU Leuven,
Instituut voor Kern- en Stralingsfysica, B-3001 Leuven, Belgium  P. Ring
Fakultät für Physik, Technische Universität München, D-85748 Garching, Germany
H. Nakada  Department of Physics, Graduate School of Science, Chiba
University, Yayoi-cho, I-33, Inage, Chiba 263-8522, Japan  A.N. Andreyev
Department of Physics, University of York, York, YO10 5DD, United Kingdom
Advanced Science Research Center (ASRC), Japan Atomic Energy Agency (JAEA),
Tokai-mura, Japan  P. Van Duppen  KU Leuven, Instituut voor Kern- en
Stralingsfysica, B-3001 Leuven, Belgium  N.A. Althubiti  The University of
Manchester, School of Physics and Astronomy, Oxford Road, M13 9PL Manchester,
United Kingdom  Physics Department, Faculty of Science, Jouf University,
Aljouf, Saudi Arabia  B. Andel  KU Leuven, Instituut voor Kern- en
Stralingsfysica, B-3001 Leuven, Belgium  Department of Nuclear Physics and
Biophysics, Comenius University in Bratislava, 84248 Bratislava, Slovakia  D.
Atanasov  Max-Planck-Institut für Kernphysik, Saupfercheckweg 1, 69117
Heidelberg, Germany  J. Billowes  The University of Manchester, School of
Physics and Astronomy, Oxford Road, M13 9PL Manchester, United Kingdom  K.
Blaum  Max-Planck-Institut für Kernphysik, Saupfercheckweg 1, 69117
Heidelberg, Germany  T.E. Cocolios  The University of Manchester, School of
Physics and Astronomy, Oxford Road, M13 9PL Manchester, United Kingdom  KU
Leuven, Instituut voor Kern- en Stralingsfysica, B-3001 Leuven, Belgium  J.G.
Cubiss  Department of Physics, University of York, York, YO10 5DD, United
Kingdom  G.J. Farooq-Smith  The University of Manchester, School of Physics
and Astronomy, Oxford Road, M13 9PL Manchester, United Kingdom  KU Leuven,
Instituut voor Kern- en Stralingsfysica, B-3001 Leuven, Belgium  D.V. Fedorov
Petersburg Nuclear Physics Institute, NRC Kurchatov Institute, Gatchina
188300, Russia  V.N. Fedosseev  CERN, CH-1211 Geneva 23, Switzerland  K.T.
Flanagan  The University of Manchester, School of Physics and Astronomy,
Oxford Road, M13 9PL Manchester, United Kingdom  The Photon Science Institute,
The University of Manchester, Manchester, M13 9PL, United Kingdom  L.P.
Gaffney  KU Leuven, Instituut voor Kern- en Stralingsfysica, B-3001 Leuven,
Belgium  School of Computing, Engineering, and Physical Sciences, University
of the West of Scotland, Paisley PA1 2BE, United Kingdom  L. Ghys  KU Leuven,
Instituut voor Kern- en Stralingsfysica, B-3001 Leuven, Belgium  Belgian
Nuclear Research Center SCK$\bullet$CEN, Boeretang 200, B-2400 Mol, Belgium
M. Huyse  KU Leuven, Instituut voor Kern- en Stralingsfysica, B-3001 Leuven,
Belgium  S. Kreim  Max-Planck-Institut für Kernphysik, Saupfercheckweg 1,
69117 Heidelberg, Germany  CERN, CH-1211 Geneva 23, Switzerland  D. Lunney
CSNSM-IN2P3, Université de Paris Sud, Orsay, France  K.M. Lynch  The
University of Manchester, School of Physics and Astronomy, Oxford Road, M13
9PL Manchester, United Kingdom  CERN, CH-1211 Geneva 23, Switzerland  V. Manea
Max-Planck-Institut für Kernphysik, Saupfercheckweg 1, 69117 Heidelberg,
Germany  Y. Martinez Palenzuela  KU Leuven, Instituut voor Kern- en
Stralingsfysica, B-3001 Leuven, Belgium  CERN, CH-1211 Geneva 23, Switzerland
P.L. Molkanov  Petersburg Nuclear Physics Institute, NRC Kurchatov Institute,
Gatchina 188300, Russia  M. Rosenbusch  Universität Greifswald, Institut für
Physik, 17487 Greifswald, Germany  R.E. Rossel  CERN, CH-1211 Geneva 23,
Switzerland  Institut für Physik, Johannes Gutenberg-Universität, D-55099
Mainz, Germany  S. Rothe  CERN, CH-1211 Geneva 23, Switzerland  L. Schweikhard
Universität Greifswald, Institut für Physik, 17487 Greifswald, Germany  M.D.
Seliverstov  Petersburg Nuclear Physics Institute, NRC Kurchatov Institute,
Gatchina 188300, Russia  P. Spagnoletti  School of Computing, Engineering, and
Physical Sciences, University of the West of Scotland, Paisley PA1 2BE, United
Kingdom  C. Van Beveren  KU Leuven, Instituut voor Kern- en Stralingsfysica,
B-3001 Leuven, Belgium  M. Veinhard  CERN, CH-1211 Geneva 23, Switzerland  E.
Verstraelen  KU Leuven, Instituut voor Kern- en Stralingsfysica, B-3001
Leuven, Belgium  A. Welker  CERN, CH-1211 Geneva 23, Switzerland  Institut für
Kern- und Teilchenphysik, Technische Universität Dresden, Dresden 01069,
Germany  K. Wendt  Institut für Physik, Johannes Gutenberg-Universität,
D-55099 Mainz, Germany  F. Wienholtz  CERN, CH-1211 Geneva 23, Switzerland
Universität Greifswald, Institut für Physik, 17487 Greifswald, Germany  R.N.
Wolf  Max-Planck-Institut für Kernphysik, Saupfercheckweg 1, 69117 Heidelberg,
Germany  Universität Greifswald, Institut für Physik, 17487 Greifswald,
Germany  A. Zadvornaya  KU Leuven, Instituut voor Kern- en Stralingsfysica,
B-3001 Leuven, Belgium  K. Zuber  Institut für Kern- und Teilchenphysik,
Technische Universität Dresden, Dresden 01069, Germany

###### Abstract

The mean-square charge radii of 207,208Hg ($Z=80,N=127,128$) have been studied
for the first time and those of 202,203,206Hg ($N=122,123,126$) remeasured by
the application of in-source resonance-ionization laser spectroscopy at ISOLDE
(CERN). The characteristic kink in the charge radii at the $N=126$ neutron
shell closure has been revealed, providing the first information on its
behavior below the $Z=82$ proton shell closure. A theoretical analysis has
been performed within relativistic Hartree-Bogoliubov and non-relativistic
Hartree-Fock-Bogoliubov approaches, considering both the new mercury results
and existing lead data. Contrary to previous interpretations, it is
demonstrated that both the kink at $N=126$ and the odd-even staggering (OES)
in its vicinity can be described predominately at the mean-field level, and
that pairing does not need to play a crucial role in their origin. A new OES
mechanism is suggested, related to the staggering in the occupation of the
different neutron orbitals in odd- and even-$A$ nuclei, facilitated by
particle-vibration coupling for odd-$A$ nuclei.

Experimental investigations of nuclear charge radii have revealed a rich
abundance of regular patterns, abrupt changes and non-linear trends along
isotopic chains across the nuclear chart [1, 2]. Two near-universal features
include kinks at neutron shell closures and odd-even staggering (OES), where
an odd-$N$ isotope has a smaller charge radius than the average of its two
even-$N$ neighbors [1, 3]. The commonality of these features indicates that
their origin is general and independent of local microscopic phenomena. As
such, measurements of kinks and OES provide a particularly stringent benchmark
for nuclear theory [4, 5, 6, 7, 8, 9].

Historically, the majority of the discussion pertaining to the effect of shell
closures on charge radii focused on the kink in the lead isotopic chain across
$N=126$ [4, 5, 6, 10, 11], which is shown in the inset of Fig. 1. A variety of
theoretical approaches have been employed to investigate this kink.
Relativistic mean field studies have described it with varying degrees of
success [5, 12]. By contrast, calculations in non-relativistic density
functional theories (NR-DFTs) based on conventional functionals were unable to
reproduce the kink [4, 8]. The differences between the descriptions in these
theoretical frameworks are related to the relative occupations of the neutron
$\nu 1i_{11/2}$ and $\nu 2g_{9/2}$ orbitals (located above the $N=126$ shell
closure), with the magnitude of the kink being driven by the occupation of the
$\nu 1i_{11/2}$ orbital [11]. The extension of non-relativistic functionals,
by the addition of gradient terms into the pairing interaction, has been
demonstrated as a possible way to improve their description of OES and the
kink [6, 8]. An alternative approach is the inclusion of a density dependence
in the spin-orbit interaction [7, 13, 14], derived from the chiral three-
nucleon interaction by Kohno [15].

Figure 1: Systematics of the difference in mercury ground state (g.s.) and
isomer mean-square charge radii. Data from the present work are shown by red
symbols, earlier data are taken from [16] (black) and [17] (blue). The inset
highlights the kink at $N=126$ and the neighboring OES in both the mercury and
lead [18] isotopic chains. The lead isotopes are arbitrarily displaced from
those of mercury for clarity. The dashed lines through $N=124,126$ in the
inset are added to highlight the kinks. Statistical uncertainties are smaller
than the data points.

The optimal method of quantifying the kink at $N=126$ considers isotopes with
$N=124,126,128$, to avoid contributions from either OES or possible
deformation in isotopes further from the shell closure. However, in contrast
to the regions near $N=50$ and $N=82$ [1], there are limited experimental data
on charge radii behavior across $N=126$ (specifically for $N=128$), with
corresponding measurements available only for $Z=82$ [18] and $Z=83$ [19].

In this Letter we report the first study of charge radii across $N=126$ in the
mercury $(Z=80)$ isotopic chain, thus enabling the $Z$-dependence of the kink
at $N=126$ to be probed and providing the first benchmark for theory in the
region below the $Z=82$ proton shell closure. These new data motivated us to
undertake a comparative theoretical investigation of the kinks and OES in lead
and mercury charge radii across $N=126$. By applying both spherical
relativistic Hartree-Bogoliubov (RHB) [20] and spherical non-relativistic
Hartree-Fock-Bogoliubov (NR-HFB) [21] approaches, we explored whether an
alternative explanation of the kink and OES is possible. This was also the
first study of OES within a relativistic framework.

The experimental data originates from the same measurement campaign as
described in Refs. [17, 22], where neutron-deficient mercury isotopes were
also studied (Fig. 1). Therefore, only a brief experimental overview is
included here. Mercury isotopes were produced at the CERN-ISOLDE facility [23]
by impinging a 1.4-GeV proton beam from the Proton Synchrotron Booster on to a
molten-lead target. The neutral reaction products effused into the anode
cavity of a Versatile Arc Discharge and Laser Ion Source (VADLIS) [24]. Laser
light from the ISOLDE Resonance Ionization Laser Ion Source (RILIS) complex
[25] was used to excite three sequential atomic transitions, for the resonance
ionization of the mercury isotopes [26]. The photo-ions were extracted and
mass separated by the ISOLDE general purpose separator and then directed to
either a Faraday cup for direct photo-ion detection, or to the ISOLTRAP Paul
trap [27] and multi-reflection time-of-flight mass spectrometer (MR-ToF MS)
[28] for single-ion counting and discrimination from isobaric contamination.

The first of the three atomic transitions ($5d^{10}6s^{2}$ ${}^{1}S_{0}$
$\rightarrow$ $5d^{10}6s6p$ ${}^{3}P_{1}^{\circ}$, 253.65 nm) was probed by
scanning a frequency-tripled titanium-sapphire laser (full width at half
maximum bandwidth $<$1 GHz before tripling) [29]. Isotope shifts (IS),
$\delta\nu^{A,A^{\prime}}=\nu^{A}-\nu^{A^{\prime}}$, in the frequency of this
transition were measured for mercury nuclei with $A=202,203,206,207,208$
relative to the stable reference isotope with $A^{\prime}=198$. Sample spectra
are presented in Fig. 2. Details of the scanning and fitting procedures can be
found in Refs. [30, 22] and Refs. [22, 31], respectively, with further
information on the data analysis in Refs. [32, 33]. The relative changes in
the mean-square charge radii, $\delta\langle r^{2}\rangle^{A,A^{\prime}}$,
were extracted from the measured $\delta\nu^{A,A^{\prime}}$ values via
standard methods described in the supplemental material [34].

Figure 2: Sample hyperfine spectra for 206-208Hg, with the photo-ion rate
measured using the MR-ToF MS. The centroids are indicated with black lines,
red lines represent fitting with Voigt profiles.

The extracted $\delta\nu^{A,A^{\prime}}$ and $\delta\langle
r^{2}\rangle^{A,A^{\prime}}$ values are presented in Table 1 and the
$\delta\langle r^{2}\rangle^{A,A^{\prime}}$ data are plotted in Fig. 1. There
is a visible kink at $N=126$, with a magnitude similar to that in the lead
isotopic chain. The IS for 202,203Hg, and the remeasured neutron-deficient
isotopes [17, 22] from the same experimental campaign, are in good agreement
with literature. For 206Hg there is a $\approx$ 500-MHz discrepancy between
this work and the thesis value of Ref. [35] cited in [16], which is discussed
in Ref. [32]. Given the agreement of the results from the present experimental
campaign with the other literature data, the ${\delta\nu^{206,198}}$ value
from this work is used for the following discussion.

Table 1:  $\delta\nu^{A,198}$ values in the 253.65 nm line from this work and literature. $\delta\langle r^{2}\rangle^{A,198}$ values are calculated as described in the supplemental material [34]. Statistical uncertainties are shown in parentheses and systematic uncertainties in curly brackets. Isotope | $I^{\pi}$ | $\delta\nu^{A,198}$ | $\delta\langle r^{2}\rangle^{A,198}$ | Ref.
---|---|---|---|---
A |  | (MHz) | (fm2) |
202 | 0 | -10 100(180) | 0.197(3){14} | This work
|  | -10 102.4(42) | 0.1973(1){138} | [16]
203 | 5/2- | -11 870(200) | 0.232(4){16} | This work
|  | -11 750(180) | 0.2295(35) {161} | [16]
206 | 0 | -20 930(160) | 0.409(3){29} | This work
|  | -20 420(80) | 0.3986(16){280} | [16, 35]
207 | (9/2-) | -25 790(190) | 0.503(4){35} | This work
208 |  | -32 030(160) | 0.624(3){44} | This work

To interpret the data, a new RHB code was developed which enables the blocking
of selected single-particle orbitals and allows for fully self-consistent
calculations of the ground and excited states in odd-$A$ nuclei. A separable
version of the Gogny pairing is used [36], with the pairing strength of Ref.
[37]. The NL3*, DD-PC1, DD-ME2 and DD-ME$\delta$ covariant energy density
functionals (CEDF) were employed, the global performance of which was tested
in Ref. [37]. The functionals achieved a comparable description of the kink
and the OES, thus only the DD-ME2 results are discussed below. The results for
the other functionals will be included in a follow-up paper [38].

The NR-HFB calculations were performed assuming spherical symmetry with the
semi-realistic M3Y-P6a interaction, the spin-orbit properties of which were
modified [13] to improve the description of the charge radii of proton-magic
nuclei [7, 14, 13]. We applied it here for the first time to the mercury
isotopic chain. For $N\leq 126$, isotopes with
$\langle\beta_{2}^{2}\rangle^{1/2}<0.1$ were considered, where
$\langle\beta_{2}^{2}\rangle$ is the mean-square deformation deduced from
$\delta\langle r^{2}\rangle$ using the droplet model [3, 39]. This restriction
corresponds to $N\geq 116$ and $N\geq 121$ for lead and mercury isotopes,
respectively.

The importance of a simultaneous agreement of energetic and geometric nuclear
observables in such investigations has been highlighted previously [6]. Thus,
in addition to calculating the charge radii, we also checked the quality of
the binding energy description. There is a good agreement between the DD-ME2
and experimental binding energies for both lead and mercury isotopes [40]. The
rms deviation is 1.3 MeV and 1.1 MeV for 198-214Pb and 201-208Hg,
respectively, a comparable performance to the widely used NR-DFT functional
UNEDF1 [41] (1.4 MeV and 1.0 MeV for lead and mercury, respectively [42]). The
binding and separation energy descriptions of all of the employed CEDFs will
be discussed in detail in Ref. [38].

Two different procedures labeled as “LES” and “EGS” are used for the blocking
in odd-$A$ nuclei and the results of respective calculations are labeled by
the “Functional-Procedure” labels (for example, DD-ME2-EGS). In the LES
procedure, the lowest in energy configuration is used: this is similar to all
earlier calculations of OES [6, 43]. In the EGS procedure, the configuration
with the spin and parity of the blocked state corresponding to those of the
experimental ground state is employed, although it is not necessarily the
lowest in energy. For example, in the RHB(DD-ME2) calculations the EGS
configurations with a blocked $\nu 2g_{9/2}$ state are located at excitation
energies of 137 keV, 122 keV and 96 keV above the ground state configurations
with a blocked $\nu 1i_{11/2}$ state in 209,211,213Pb. At first glance, this
contradicts experimental findings that the ground state is based on the $\nu
2g_{9/2}$ orbital in odd-$A$ lead isotopes with $N>126$. However, particle-
vibration coupling (PVC) lowers the energy of this state below that of the
$\nu 1i_{11/2}$ one (see Fig. 5 in Ref. [44]) so that it becomes the lowest in
energy in the PVC calculations. Note that PVC significantly improves the
accuracy of the description of the energies of experimental states in model
calculations [44, 45]. However, it is neglected in the present study since its
impact on charge radii is still an open theoretical question.

The results of the RHB and NR-HFB calculations are presented in Fig. 3,
together with the experimental results for the lead and mercury chains. In
both cases, the kink at $N=126$ is visibly better reproduced in the RHB (DD-
ME2) calculations.

Figure 3:  $\delta\langle r^{2}\rangle^{A,A^{\prime}}$ of lead (a) and mercury
(b) isotopes relative to 208Pb and 206Hg ($N=126$), respectively. Experimental
mercury data: this work and [16], experimental lead data: [18], the
statistical uncertainties are smaller than the data points. RHB(DD-ME2)
results: this work, NR-HFB(M3Y-P6a) results: this work (mercury) and [14]
(lead), NR-HFB(UNEDF1) results: [42].

To facilitate a quantitative comparison of the experimental and theoretical
results, two indicators are employed. OES is quantified considering the
isotope’s nearest neighbors via the commonly used three-point indicator

$\Delta\langle r^{2}\rangle^{(3)}(A)=\frac{1}{2}\left[\langle
r^{2}(A-1)\rangle+\langle r^{2}(A+1)\rangle-2\langle r^{2}(A)\rangle\right].$
(1)

To quantify the shell effect at $N=126$, the kink indicator of Ref. [8] is
used which considers the isotope’s next-to-nearest neighbors and is defined as

$\Delta R^{(3)}(A)=\frac{1}{2}\left[R(A-2)+R(A+2)-2R(A)\right],$ (2)

where $R(A)=\langle r^{2}\rangle^{1/2}(A)$ is the charge radius of the isotope
with mass $A$ of the element under consideration. Note that the kink indicator
is independent of the blocking procedure in odd-$A$ nuclei and therefore we
omit the corresponding specifications (LES or EGS) in the discussion of the
kink.

$\Delta\langle r^{2}\rangle^{(3)}(A)$ and $\Delta R^{(3)}(A)$ values
calculated from the experimental results and theoretical calculations for both
lead and mercury are presented in Fig. 4, and the $\Delta R^{(3)}(A)$ values
are listed in the supplemental material [34]. It is evident in Figs. 4 (a) and
4 (b) that the magnitude of the kinks in the isotopic chains are comparable,
suggesting that the kink at $N=126$ is broadly insensitive to the change of
the occupied proton states when crossing $Z=82$ ($\pi 2d_{3/2}$ in mercury and
$\pi 3s_{1/2}$ in lead). In addition, the RHB(DD-ME2) calculations best
reproduce the kink, while the NR-HFB(M3Y-P6a) and NR-HFB(Fy($\Delta$r) [8])
results underestimate and overestimate its magnitude, respectively. It is
worth noting that both the RHB(DD-ME2) and NR-HFB(M3Y-P6a) approaches are
reasonably successful in the reproduction of the absolute charge radius values
for 206Hg and 208Pb, the details are included in the supplemental material
[34].

In both approaches, the OES is best reproduced if the EGS procedure is applied
(see Figs. 4 (c), (d) and Fig. 5). If the LES procedure is applied, the
experimental OES is significantly underestimated for all nuclei under study in
the RHB calculations and for $N<126$ nuclei in the NR-HFB calculations. Note
that for simplicity we show only NR-HFB results with both procedures in Fig. 4
(c) and (d).

For a better understanding of the underlying mechanisms of both the kink and
OES, we also performed RHB calculations without pairing for lead isotopes. The
labels identifying such results contain “np”. Significantly, a kink is still
present in the results as depicted in Fig. 4 (a), due to the occupation of the
$\nu 1i_{11/2}$ orbital. This indicates a mechanism alternative to the one
based on gradient terms in pairing interactions [6, 8].

Figure 4: Comparison of experimental and theoretical $\Delta R^{(3)}(A)$ and
$\Delta\langle r^{2}\rangle^{(3)}(A)$ values for isotopes of lead, (a) and
(c), respectively, and mercury (b) and (d), respectively. Experimental values
are taken from this work and from Ref. [16] (mercury) and Ref. [18] (lead).
The RHB(DD-ME2) and NR-HFB(M3Y-P6a) results are obtained in this work and the
NR-HFB results with Fy($\Delta r$) and UNEDF1 are taken from Refs. [8] and
[42], respectively. Experimental uncertainty is depicted as translucent gray
bars in (a) and (b), and as error bars in (c) and (d).

The RHB results with and without pairing are compared via $\Delta\langle
r^{2}\rangle^{(3)}(A)$ in Fig. 5. OES appears in these calculations (the
curves labeled as “DD-ME2-EGS” and “DD-ME2-np-EGS”) under the condition that,
in odd-$A$ nuclei, the EGS procedure is used. One can see that the inclusion
of pairing somewhat reduces this effect. However, OES is mostly absent if the
LES procedure is used in odd-$A$ nuclei.

Figure 5: Comparison of experimental and theoretical $\Delta\langle
r^{2}\rangle^{(3)}(A)$ values for lead isotopes. Experimental data from [18],
theoretical results are from this work. See text for details.

Let us consider the lead isotopes with $N\geq 126$ for a more detailed
discussion of the origin of OES in the calculations without pairing. By
designating the ground state of 208Pb as a “core” and noting that PVC lowers
the energy of the $\nu 2g_{9/2}$ state below $\nu 1i_{11/2}$ in odd-$A$ nuclei
[44], the sequence of the ground states in the $N\geq 126$ nuclei can be
described as “core” (208Pb), “core”$\otimes\nu(2g_{9/2})^{1}$ (209Pb),
“core”$\otimes\nu(2i_{11/2})^{2}$ (210Pb),
“core”$\otimes\nu(2i_{11/2})^{2}(2g_{9/2})^{1}$ (211Pb) and so on in the
relativistic calculations without pairing. The $\nu 1i_{11/2}$ orbital has a
smaller rms-radius than the $\nu 2g_{9/2}$ orbital. However, because of the
isovector nature of nuclear forces its occupation leads to a larger charge
radius as compared with the occupation of $\nu 2g_{9/2}$ orbital. Thus, the
staggering in their occupation between odd and even isotopes results in the
OES seen in Fig. 5.

On the contrary, in the majority of conventional non-relativistic functionals,
the $\nu 2g_{9/2}$ orbital is lower in energy than the $\nu 1i_{11/2}$
orbital. This is in agreement with experimental data on the structure of the
ground states in odd-mass nuclei, but creates a problem in the description of
the kinks. In addition, in calculations with and without pairing this leads to
the sole or predominant occupation of the $\nu 2g_{9/2}$ state in even-even
and odd-even nuclei with $N>126$ and thus to a negligible or comparatively
small OES. To address this, several prescriptions have been suggested over the
years to increase the occupation of the $\nu 1i_{11/2}$ orbital in the $N>126$
lead nuclei. One approach includes a modification of the spin-orbit
interaction leading either to the inversion of the relative energies of these
two states or to their proximity in energy [46, 47, 48, 49, 50, 11]. The NR-
HFB results with M3Y-P6a shown in Figs. 3 and 4 are also based on a
modification of the spin-orbit interaction, with the inclusion of a density
dependent term in the spin-orbit channel. Alternatively, the so-called Fayans
functionals employ a specific form of the pairing interaction containing a
gradient term [51, 6, 43, 8]. Although this improves the general description
of experimental data, discrepancies between theory and experiment still exist
in the lead and tin isotopic chains [8]. Moreover, pairing becomes a dominant
contributor to the kink and OES [8].

The present RHB interpretation of the kinks and OES differs from that
suggested in [8], which is based on non-relativistic Skyrme and Fayans
functionals. In the RHB approach, the kink and OES are already present in the
calculations without pairing. Thus, the evolution of charge radii with neutron
number depends significantly on the mean-field properties. Pairing acts only
as an additional tool which mixes different configurations and somewhat
softens the evolution of charge radii as a function of neutron number.

In conclusion, the determination of the $\delta\langle
r^{2}\rangle^{A,A^{\prime}}$ of 207,208Hg has revealed a kink at $N=126$ in
the mercury nuclear charge radii systematics, with a magnitude comparable to
that in the lead isotopic chain. These new data have been analyzed via both
RHB and NR-HFB approaches, together with the traditional magic-$Z$ theoretical
benchmark of the lead isotopic chain. We demonstrate that the kinks at the
$N=126$ shell closure and the OES in the vicinity, are currently best
described in the RHB approach without any readjustment of the parameters
defined in Ref. [52]. According to the RHB calculations, the kink at $N=126$
in $\delta\langle r^{2}\rangle^{A,A^{\prime}}$ originates from the occupation
of the $\nu 1i_{11/2}$ orbital located above the $N=126$ shell gap. A new
mechanism for OES is suggested, related to the staggering in the occupation of
neutron orbitals between odd and even isotopes and facilitated by PVC in odd-
mass nuclei. Thus, contrary to previous interpretations, it is determined that
both the kink and OES in charge radii can be defined predominantly in the
particle-hole channel.

###### Acknowledgements.

This project has received funding through the European Union’s Seventh
Framework Programme for Research and Technological Development under grant
agreements 267194 (COFUND), 262010 (ENSAR), 289191 (LA3NET) and 267216
(PEGASUS). This project has received funding from the European Union’s Horizon
2020 research and innovation programme grant agreement No 654002. This
material is based upon work supported by the US Department of Energy, Office
of Science, Office of Nuclear Physics under Award No. DE-SC0013037, and by the
DFG cluster of excellence “Origin and Structure of the Universe”
(www.universe-cluster.de). S. S. acknowledges a SB PhD grant from the former
Belgian Agency for Innovation by Science and Technology (IWT), now
incorporated in FWO-Vlaanderen. This work was supported by the RFBR according
to the research project N 19-02-00005; the ERC Consolidator Grant No. 648381;
the IUAP-Belgian State Science Policy (BRIX network P7/12), FWO-Vlaanderen
(Belgium) and GOA’s 10/010 and 10/05 and starting grant STG 15/031 from KU
Leuven; the Science and Technology Facilities Council Consolidated Grant Nos.
ST/F012071/1 and ST/P003885/1, Continuation Grant No. ST/J000159/1 and Ernest
Rutherford Grant No. ST/L002868/1; the Slovak Research and Development Agency,
contract No. APVV-14-0524; the BMBF (German Federal Ministry for Education and
Research) grants Nos. 05P12HGCI1, 05P15HGCIA and 05P18HGCIA.

## .1

### .1.1

## References

  * Angeli  _et al._ [2009] I. Angeli, Y. P. Gangrsky, K. P. Marinova, I. N. Boboshin, S. Y. Komarov, B. Ishkhanov, and V. Varlamov, N and Z dependence of nuclear charge radii, J. Phys. G 36, 085102 (2009).
  * Campbell  _et al._ [2016] P. Campbell, I. D. Moore, and M. R. Pearson, Laser spectroscopy for nuclear structure physics, Prog. Part. Nucl. Phys. 86, 127 (2016).
  * Otten [1989] E. W. Otten, Nuclear Radii and Moments of Unstable Isotopes, in  _Treatise on Heavy Ion Science_ (Springer US, Boston, MA, 1989) pp. 517–638.
  * Tajima  _et al._ [1993] N. Tajima, P. Bonche, H. Flocard, P.-H. Heenen, and M. S. Weiss, Self-consistent calculation of charge radii of Pb isotopes, Nucl. Phys. A 551, 434 (1993).
  * Sharma  _et al._ [1993] M. M. Sharma, G. A. Lalazissis, and P. Ring, Anomaly in the charge radii of Pb isotopes, Phys. Lett. B 317, 9 (1993).
  * Fayans  _et al._ [2000] S. A. Fayans, S. V. Tolokonnikov, E. L. Trykov, and D. Zawischa, Nuclear isotope shifts within the local energy-density functional approach, Nucl. Phys. A 676, 49 (2000).
  * Nakada [2019] H. Nakada, Irregularities in nuclear radii at magic numbers, Phys. Rev. C 100, 044310 (2019).
  * Gorges et al. [2019] C. Gorges et al., Laser Spectroscopy of Neutron-Rich Tin Isotopes: A Discontinuity in Charge Radii across the N=82 Shell Closure, Phys. Rev. Lett. 122, 192502 (2019).
  * de Groote et al. [2020] R. P. de Groote et al., Measurement and microscopic description of odd-even staggering of charge radii of exotic copper isotopes, Nat. Phys. 16, 620 (2020).
  * Nikšić  _et al._ [2002] T. Nikšić, D. Vretenar, P. Ring, and G. A. Lalazissis, Shape coexistence in the relativistic Hartree-Bogoliubov approach, Phys. Rev. C 65, 054320 (2002).
  * Goddard  _et al._ [2013] P. M. Goddard, P. D. Stevenson, and A. Rios, Charge radius isotope shift across the N=126 shell gap, Phys. Rev. Lett. 110, 032503 (2013).
  * Lalazissis  _et al._ [1999] G. A. Lalazissis, S. Raman, and P. Ring, Ground-state properties of even-even nuclei in the relativistic mean-field theory, At. Data Nucl. Data Tables 71, 1 (1999).
  * Nakada [2015] H. Nakada, Further evidence for three-nucleon spin-orbit interaction in isotope shifts of nuclei with magic proton numbers, Phys. Rev. C 92, 044307 (2015).
  * Nakada and Inakura [2015] H. Nakada and T. Inakura, Effects of three-nucleon spin-orbit interaction on isotope shifts of Pb nuclei, Phys. Rev. C 91, 021302 (2015).
  * Kohno [2012] M. Kohno, Strength of reduced two-body spin-orbit interaction from a chiral three-nucleon force, Phys. Rev. C 86, 061301 (2012).
  * Ulm et al. [1986] G. Ulm et al., Isotope shift of 182Hg and an update of nuclear moments and charge radii in the isotope range 181Hg-206Hg, Z. Phys. A: Hadrons Nucl. 325, 247 (1986).
  * Marsh et al. [2018] B. A. Marsh et al., Characterization of the shape-staggering effect in mercury nuclei, Nat. Phys. 14, 1163 (2018).
  * Anselment  _et al._ [1986] M. Anselment, W. Faubel, S. Göring, A. Hanser, G. Meisel, H. Rebel, and G. Schatz, The odd-even staggering of the nuclear charge radii of Pb isotopes, Nucl. Phys. A 451, 471 (1986).
  * Barzakh  _et al._ [2018] A. E. Barzakh, D. V. Fedorov, V. S. Ivanov, P. L. Molkanov, F. V. Moroz, S. Y. Orlov, V. N. Panteleev, M. D. Seliverstov, and Y. M. Volkov, Shell effect in the mean square charge radii and magnetic moments of bismuth isotopes near N=126, Phys. Rev. C 97, 014322 (2018).
  * Vretenar  _et al._ [2005] D. Vretenar, A. V. Afanasjev, G. Lalazissis, and P. Ring, Relativistic Hartree-Bogoliubov theory: static and dynamic aspects of exotic nuclear structure, Phys. Rep. 409, 101 (2005).
  * Nakada [2020] H. Nakada, Properties of exotic nuclei and their linkage to the nucleonic interaction, Int. J. Mod. Phys. E 29, 1930008 (2020).
  * Sels et al. [2019] S. Sels et al., Shape staggering of mid-shell mercury isotopes from in-source laser spectroscopy compared with Density Functional Theory and Monte Carlo Shell Model calculations, Phys. Rev. C 99, 044306 (2019).
  * Catherall et al. [2017] R. Catherall et al., The ISOLDE facility, J. Phys. G 44, 094002 (2017).
  * Day Goodacre et al., T. [2016] Day Goodacre et al., T., Blurring the boundaries between ion sources: The application of the RILIS inside a FEBIAD type ion source at ISOLDE, Nucl. Instrum. Meth. B 376, 39 (2016).
  * Fedosseev  _et al._ [2017] V. Fedosseev, K. Chrysalidis, T. Day Goodacre, B. Marsh, S. Rothe, C. Seiffert, and K. Wendt, Ion beam production and study of radioactive isotopes with the laser ion source at ISOLDE, J. Phys. G 44, 084006 (2017).
  * Day Goodacre  _et al._ [2016] T. Day Goodacre, D. Fedorov, V. N. Fedosseev, L. Forster, B. A. Marsh, R. E. Rossel, S. Rothe, and M. Veinhard, Laser resonance ionization scheme development for tellurium and germanium at the dual Ti:Sa–Dye ISOLDE RILIS, Nucl. Instrum. Meth. A 830, 510 (2016).
  * Herfurth et al. [2001] F. Herfurth et al., A linear radiofrequency ion trap for accumulation, bunching, and emittance improvement of radioactive ion beams, Nuc. Instrum. Meth. A 469, 254 (2001).
  * Wolf et al. [2013] R. N. Wolf et al., ISOLTRAP’s multi-reflection time-of-flight mass separator/spectrometer, Int. J. Mass Spectrom. 349-350, 123 (2013).
  * Rothe  _et al._ [2013] S. Rothe, V. N. Fedosseev, T. Kron, B. A. Marsh, R. E. Rossel, and K. D. A. Wendt, Narrow linewidth operation of the RILIS titanium: Sapphire laser at ISOLDE/CERN, Nucl. Instrum. Meth. B 317, 561 (2013).
  * Rossel [2015] R. E. Rossel,  _A Distributed Monitoring and Control System for the Laser Ion Source RILIS at CERN-ISOLDE_ , M.Sc thesis, Hochschule RheinMain (2015).
  * Seliverstov et al. [2014] M. D. Seliverstov et al., Electromagnetic moments of odd-A 193-203,211Po isotopes, Phys. Rev. C 89, 034323 (2014).
  * Day Goodacre [2016] T. Day Goodacre,  _Developments of the ISOLDE RILIS for radioactive ion beam production and the results of their application in the study of exotic mercury isotopes_ , Ph.D. thesis, The University of Manchester, https://cds.cern.ch/record/2254839 (2016).
  * Sels [2018] S. Sels,  _Laser Spectroscopy of Neutron-Deficient Mercury Isotopes and Commissioning of a Gas-jet Based RFQ Ion Guide_ , Ph.D. thesis, KU Leuven, https://cds.cern.ch/record/2652298 (2018).
  * [34] See Supplemental Material at […], for 1. details on the extraction of the relative changes in the mean-square charge radii from the isotope shifts, 2. the kink indicator values and 3. the absolute charge radius values at $N$=126 [18, 8, 17, 42, 3, 22, 16, 53, 54, 55].
  * Dabkiewicz [1980] P. Dabkiewicz,  _Laserspektroskopische Bestimmung der Formisomerie in 185Hg und der Isotopieverschiebung von 206Hg_, Ph.D. thesis, The Johannes Gutenberg University of Mainz (1980).
  * Tian  _et al._ [2009] Y. Tian, Z. Y. Ma, and P. Ring, A finite range pairing force for density functional theory in superfluid nuclei, Phys. Lett. B 676, 44 (2009).
  * Agbemava  _et al._ [2014] S. E. Agbemava, A. V. Afanasjev, D. Ray, and P. Ring, Global performance of covariant energy density functionals: Ground state observables of even-even nuclei and the estimate of theoretical uncertainties, Phys. Rev. C 89, 054320 (2014).
  * [38] T. Day Goodacre, et al., in preparation .
  * Berdichevsky and Tondeur [1985] D. Berdichevsky and F. Tondeur, Nuclear core densities, isotope shifts, and the parametrization of the droplet model, Z. Phys. A: Hadrons Nucl. 322, 141 (1985).
  * Audi  _et al._ [2017] G. Audi, F. G. Kondev, M. Wang, W. J. Huang, and S. Naimi, The NUBASE2016 evaluation of nuclear properties, Chinese Phys. C 41, 030001 (2017).
  * Kortelainen  _et al._ [2012] M. Kortelainen, J. McDonnell, W. Nazarewicz, P.-G. Reinhard, J. Sarich, N. Schunck, M. V. Stoitsov, and S. M. Wild, Nuclear energy density optimization: Large deformations, Phys. Rev. C 85, 024304 (2012).
  * [42] Mass Explorer, http://massexplorer.frib.msu.edu. Accessed:2020-06-01 .
  * Reinhard and Nazarewicz [2017] P.-G. Reinhard and W. Nazarewicz, Toward a global description of nuclear charge radii: Exploring the Fayans energy density functional, Phys. Rev. C 95, 064328 (2017).
  * Litvinova and Afanasjev [2011] E. V. Litvinova and A. V. Afanasjev, Dynamics of nuclear single-particle structure in covariant theory of particle-vibration coupling: from light to superheavy nuclei, Phys. Rev. C 84, 014305 (2011).
  * Afanasjev and Litvinova [2015] A. V. Afanasjev and E. Litvinova, Impact of collective vibrations on quasiparticle states of open-shell odd-mass nuclei and possible interference with the tensor force, Phys. Rev. C 92, 044317 (2015).
  * Sharma  _et al._ [1995] M. M. Sharma, G. Lalazissis, J. König, and P. Ring, Isospin Dependence of the Spin-Orbit Force and Effective Nuclear Potentials, Phys. Rev. Lett. 74, 3744 (1995).
  * Reinhard and Flocard [1995] P.-G. Reinhard and H. Flocard, Nuclear effective forces and isotope shifts, Nucl. Phys. A 584, 467 (1995).
  * Stone and Reinhard [2007] J. R. Stone and P.-G. Reinhard, The Skyrme interaction in finite nuclei and nuclear matter, Prog. Part. Nucl. Phys. 58, 587 (2007).
  * Bender  _et al._ [2003] M. Bender, P.-H. Heenen, and P.-G. Reinhard, Self-consistent mean-field models for nuclear structure, Rev. Mod. Phys. 75, 121 (2003).
  * Erler  _et al._ [2011] J. Erler, P. Klüpfel, and P.-G. Reinhard, Self-consistent nuclear mean-field models: example Skyrme–Hartree–Fock, J. Phys. G 38, 033101 (2011).
  * Fayans  _et al._ [1994] S. A. Fayans, E. L. Trykov, and D. Zawischa, Influence of effective spin-orbit interaction on the collective states of nuclei, Nucl. Phys. A 568, 523 (1994).
  * Lalazissis  _et al._ [2005] G. A. Lalazissis, T. Nikšić, D. Vretenar, and P. Ring, New relativistic mean-field interaction with density-dependent meson-nucleon couplings, Phys. Rev. C 71, 024312 (2005).
  * Fricke and Heilig [2004] G. Fricke and K. Heilig,  _Nuclear Charge Radii_ , 1st ed., edited by H. Schopper, Landolt-Börnstein - Group I Elementary Particles, Nuclei and Atoms, Vol. 20 (Springer-Verlag, Berlin/Heidelberg, 2004) pp. 1–419.
  * Angeli and Marinova [2013] I. Angeli and K. Marinova, Table of experimental nuclear ground state charge radii: An update, At. Data Nucl. Data Tables 99, 69 (2013).
  * Torbohm  _et al._ [1985] G. Torbohm, B. Fricke, and A. Rosén, State-dependent volume isotope shifts of low-lying states of group-II a and -II b elements, Phys. Rev. A 31, 2038 (1985).


2020

Tang et al.

Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization
subject to Knapsack and $k$-System Constraints

Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization
subject to Knapsack and $k$-System Constraints

Shaojie Tang Naveen Jindal School of Management, The University of Texas at
Dallas

In this paper, we study the non-monotone adaptive submodular maximization
problem subject to a knapsack and a $k$-system constraints. The input of our
problem is a set of items, where each item has a particular state drawn from a
known prior distribution. However, the state of an item is initially unknown,
one must select an item in order to reveal the state of that item. There is a
utility function which is defined over items and states. Our objective is to
sequentially select a group of items to maximize the expected utility.
Although the cardinality-constrained non-monotone adaptive submodular
maximization has been well studied in the literature, whether there exists an
approximation solution for the knapsack-constrained or $k$-system constrained
adaptive submodular maximization problem remains an open problem. It fact, it
has only been settled given the additional assumption of pointwise
submodularity. In this paper, we remove the common assumption on pointwise
submodularity and propose the first approximation solutions for these
problems. Inspired by two recent studies on non-monotone adaptive submodular
maximization, we develop a sampling-based randomized algorithm that achieves a
$\frac{1}{10}$ approximation for the case of a knapsack constraint and that
achieves a $\frac{1}{2k+4}$ approximation ratio for the case of a $k$-system
constraint.

##  1 Introduction

In Golovin and Krause (2011), they extend the study of submodular maximization
from the non-adaptive setting Nemhauser et al. (1978) to the adaptive setting.
They introduce the notions of adaptive monotonicity and submodularity, and
show that a simple adaptive greedy policy achieves a $1-1/e$ approximation
ratio if the utility function is adaptive submodular and adaptive monotone.
Although there have been numerous research studies on adaptive submodular
maximization under different settings Chen and Krause (2013), Tang and Yuan
(2020), Tang (2020), Yuan and Tang (2017a), Fujii and Sakaue (2019), most of
them assume adaptive monotonicity. For the case of maximizing a non-monotone
adaptive submodular function subject to a cardinality constraint, Tang (2021)
develops the first constant approximation solution. For the case of maximizing
a non-monotone adaptive submodular and pointwise submodular function,
Amanatidis et al. (2020), Cui et al. (2021) develop effective solutions for
the case of a knapsack and a $k$-system constraints, respectively. Note that
adaptive submodularity does not imply pointwise submodularity and vice versa
Guillory and Bilmes (2010), Golovin and Krause (2011), and this raises the
following question: Does there exist an approximation solution for maximizing
a knapsack-constrained or a $k$-system constrained non-monotone adaptive
submodular function without resorting to pointwise submodularity?

In this paper, we answer the above question affirmatively by proposing the
first approximation solutions for both knapsack or a $k$-system constraints.
Note that many practical constraints, including cardinality, matroid,
intersection of $k$ matroids, $k$-matchoid and $k$-extendible constraints, all
belong to the family of $k$-system constraints. In particular, we develop a
$\frac{1}{10}$ approximate solution for maximizing a knapsack-constrained non-
monotone adaptive submodular function. Technically speaking, our design is an
extension of the classic modified density greedy algorithm Wolsey (1982),
Amanatidis et al. (2020). In particular, their design is required to maintain
two candidate policies, i.e., one is to choose a best singleton and the other
one is to choose items in a density-greedy manner, while our design maintains
three candidate policies in order to drop the common assumption about
pointwise submodularity. For the case of a $k$-system constraint, we are
inspired by the sampling based policy proposed in Cui et al. (2021) and
develop a similar policy that achieves a $\frac{1}{2k+4}$ approximation ratio
without resorting to pointwise submodularity. We list the performance bounds
of the closely related studies in Table 1.

Source | Ratio | Constraint | Require pointwise submodularity?
---|---|---|---
Gotovos et al. (2015) | $\frac{1}{e}$ | cardinality constraint | Yes
Amanatidis et al. (2020) | $\frac{1}{9}$ | knapsack constraint | Yes
Cui et al. (2021) | $\frac{1}{k+2\sqrt{k+1}+2}$ |  $k$-system constraint | Yes
Tang (2021) | $\frac{1}{e}$ | cardinality constraint | No
this work | $\frac{1}{10}$ | knapsack constraint | No
this work | $\frac{1}{2k+4}$ |  $k$-system constraint | No
Table 1: Approximation for non-monotone adaptive submodular function
maximization

##  2 Preliminaries

We first introduce some important notations. In the rest of this paper, we use
$[m]$ to denote the set $\\{0,1,2,\cdots,m\\}$, and we use $|S|$ to denote the
cardinality of a set $S$.

###  2.1 Items and States

We consider a set $E$ of $n$ items, where each item $e\in E$ is in a
particular state from $O$. We use $\phi:E\rightarrow O$ to denote a
_realization_ , where $\phi(e)$ represents the state of $e\in E$. Let
$\Phi=\\{\Phi(e)\mid e\in E\\}$ denote a random realization, where $\Phi(e)\in
O$ is a random realization of the state of $e\in E$. The state of each item is
unknown initially, one must pick an item $e\in E$ before observing the value
of $\Phi(e)$. We assume there is a known prior probability distribution
$p(\phi)=\\{\Pr[\Phi=\phi]:\phi\in U\\}$ over realizations $U$. For any subset
of items $S\subseteq E$, we use $\psi:S\rightarrow O$ to denote a _partial
realization_ and $\mathrm{dom}(\psi)=S$ is called the _domain_ of $\psi$.
Consider any realization $\phi$ and any partial realization $\psi$, we say
that $\psi$ is consistent with $\phi$, i.e., $\psi\prec\phi$, if they are
equal everywhere in the domain of $\psi$. We say that $\psi$ is a
_subrealization_ of $\psi^{\prime}$, i.e., $\psi\subseteq\psi^{\prime}$, if
$\mathrm{dom}(\psi)\subseteq\mathrm{dom}(\psi^{\prime})$ and they are equal
everywhere in $\mathrm{dom}(\psi)$. Moreover, we use $p(\phi\mid\psi)$ to
denote the conditional distribution over realizations conditioned on a partial
realization $\psi$: $p(\phi\mid\psi)=\Pr[\Phi=\phi\mid\psi\prec\Phi]$. There
is a non-negative utility function $f$ that is defined over items and their
states: $f:2^{E}\times O^{E}\rightarrow\mathbb{R}_{\geq 0}$.

###  2.2 Policies and Problem Formulation

A typical adaptive policy works as follows: select the first item and observe
its state, then continue to select the next item based on the observations
collected so far, and so on. After each selection, we observe some _partial
realization_ $\psi$ of the states of some subset of $E$, for example, we are
able to observe the partial realization of the states of those items which
have been selected. Formally, any adaptive policy can be represented as a
function $\pi$ that maps a set of observations to a distribution
$\mathcal{P}(E)$ of $E$: $\pi:2^{E}\times O^{E}\rightarrow\mathcal{P}(E)$,
specifying which item to pick next based on the current observation.

######  Definition 2.1 (Policy Concatenation)

Given two policies $\pi$ and $\pi^{\prime}$, let $\pi@\pi^{\prime}$ denote a
policy that runs $\pi$ first, and then runs $\pi^{\prime}$, ignoring the
observation obtained from running $\pi$.

Let the random variable $E(\pi,\phi)$ denote the subset of items selected by
$\pi$ under a realization $\phi$. The expected utility $f_{avg}(\pi)$ of a
policy $\pi$ is

$\displaystyle f_{avg}(\pi)=\mathbb{E}_{\Phi\sim
p(\phi),\Pi}f(E(\pi,\Phi),\Phi)$ (1)

where the expectation is taken over $\Phi$ with respect to $p(\phi)$ and the
random output of $\pi$. For ease of presentation, let
$f(e)=\mathbb{E}_{\Phi\sim p(\phi)}f(\\{e\\},\Phi)$.

######  Definition 2.2 (Independence System)

Given a ground set $E$ and a collection of sets $\mathcal{I}\subseteq 2^{E}$,
the pair $(E,\mathcal{I})$ is an _independence system_ if

  1. 1.

$\emptyset\in\mathcal{I}$;

  2. 2.

$\mathcal{I}$, which is called the _independent sets_ , is downward-closed,
that is, $A\in\mathcal{I}$ and $B\subseteq A$ implies that $B\in\mathcal{I}$.

A set $B\in\mathcal{I}$ is called a _base_ if $A\in\mathcal{I}$ and
$B\subseteq A$ imply that $B=A$. A set $B\in\mathcal{I}$ is called a base of
$R$ if $B\subseteq R$ and $B$ is a base of the independence system
$(R,2^{R}\cap\mathcal{I})$.

######  Definition 2.3 ($k$-System)

An independence system $(E,\mathcal{I})$ is a $k$-system for an integer $k\geq
1$ if for every set $R\subseteq E$, the ratio between the sizes of the largest
and smallest bases of $R$ is upper bounded by $k$.

Let $\Omega$ denote the set of feasible policies and let $U^{+}=\\{\phi\in
U\mid p(\phi)>0\\}$. For the case of knapsack constraint, define
$\Omega=\\{\pi|\forall\phi\in U^{+},\sum_{e\in E(\pi,\phi)}c_{e}\leq b\\}$
where $c_{e}$ is the cost of $e$, which is fixed and pre-known, and $b$ is the
budget constraint. For the case of $k$-system constraint, define
$\Omega=\\{\pi|\forall\phi\in U^{+},E(\pi,\phi)\in\mathcal{I}\\}$ where
$(E,\mathcal{I})$ is a $k$-system. Our goal is to find a feasible policy
$\pi^{opt}$ that maximizes the expected utility, i.e.,
$\pi^{opt}\in\arg\max_{\pi\in\Omega}f_{avg}(\pi)$.

###  2.3 Adaptive Submodularity and Pointwise Submodularity

We start by introducing the conditional expected marginal utility of an item.

######  Definition 2.4 (Conditional Expected Marginal Utility of an Item)

For any partial realization $\psi$ and any item $e\in E$, the conditional
expected marginal utility $\Delta(e\mid\psi)$ of $e$ conditioned on $\psi$ is

$\Delta(e\mid\psi)=\mathbb{E}_{\Phi}[f(\mathrm{dom}(\psi)\cup\\{e\\},\Phi)-f(\mathrm{dom}(\psi),\Phi)\mid\psi\prec\Phi]$

where the expectation is taken over $\Phi$ with respect to
$p(\phi\mid\psi)=\Pr(\Phi=\phi\mid\psi\prec\Phi)$.

We next introduce the concept of _adaptive submodularity_.

###### Definition 2.5

Golovin and Krause (2011)[Adaptive Submodularity] A function $f:2^{E}\times
O^{E}$ is adaptive submodular with respect to a prior distribution $p(\phi)$,
if for any two partial realizations $\psi$ and $\psi^{\prime}$ such that
$\psi\subseteq\psi^{\prime}$, and any item $e\in E$ such that
$e\notin\mathrm{dom}(\psi^{\prime})$, the following holds:

$\Delta(e\mid\psi)\geq\Delta(e\mid\psi^{\prime})$

For comparison purpose, we further introduce the _pointwise submodularity_.

###### Definition 2.6

Golovin and Krause (2011)[Pointwise Submodularity] A function $f:2^{E}\times
O^{E}\rightarrow\mathbb{R}_{\geq 0}$ is pointwise submodular if $f(S,\phi)$ is
submodular in terms of $S\subseteq E$ for all $\phi\in U^{+}$. That is, for
any $\phi\in U$, any two sets $E_{1}\subseteq E$ and $E_{2}\subseteq E$ such
that $E_{1}\subseteq E_{2}$, and any item $e\notin E_{2}$, we have
$f(E_{1}\cup\\{e\\},\phi)-f(E_{1},\phi)\geq
f(E_{2}\cup\\{e\\},\phi)-f(E_{2},\phi)$.

The above property is referred to as state-wise submodularity in Amanatidis et
al. (2020). Note that adaptive submodularity does not imply pointwise
submodularity and vice versa.

Algorithm 1 Sampling-based Adaptive Density-Greedy Policy $\pi^{sad}$

1: $S_{1}=\emptyset$, $S_{2}=\emptyset$, $e^{*}=\arg\max_{e\in E}f(e)$, $t=1$,
$\psi_{0}=\emptyset$, $C=b$.

2: Sample a number $r_{0}$ uniformly at random from $[0,1]$

3: for $e\in E$ do

4: let $r_{e}\sim\mathrm{Bernoulli}(\delta_{0})$

5: if $r_{e}=1$ then

6: $S_{1}=S_{1}\cup\\{e\\}$

7: else

8: $S_{2}=S_{2}\cup\\{e\\}$

9: if $r_{0}\in[0,\delta_{1})$ then {Adopting the first candidate policy
$\pi^{1}$}

10: pick $e^{*}$

11: else if $r_{0}\in[\delta_{1},\delta_{1}+\delta_{2})$ then {Adopting the
second candidate policy $\pi^{2}$}

12: $F_{1}=\\{e|e\in S_{1},f(e)>0\\}$

13: while $F_{1}\neq\emptyset$ do

14: $e_{t}\leftarrow\arg\max_{e\in
F_{1}}\frac{\Delta(e\mid\psi_{t-1})}{c_{e}}$

15: select $e_{t}$ and observe $\Phi(e_{t})$

16: $\psi_{t}=\psi_{t-1}\cup\\{(e_{t},\Phi(e_{t}))\\}$

17: $C=C-c_{e_{t}}$

18: $S_{1}=S_{1}\setminus\\{e_{t}\\}$, $F_{1}=\\{e\in S_{1}|C\geq c_{e}\mbox{
and }\Delta(e\mid\psi_{t-1})>0\\}$, $t\leftarrow t+1$

19: else {Adopting the third candidate policy $\pi^{3}$}

20: $F_{2}=\\{e|e\in S_{2},f(e)>0\\}$

21: while $F_{2}\neq\emptyset$ do

22: $e_{t}\leftarrow\arg\max_{e\in
F_{2}}\frac{\Delta(e\mid\psi_{t-1})}{c_{e}}$

23: select $e_{t}$ and observe $\Phi(e_{t})$

24: $\psi_{t}=\psi_{t-1}\cup\\{(e_{t},\Phi(e_{t}))\\}$

25: $C=C-c_{e_{t}}$

26: $S_{2}=S_{2}\setminus\\{e_{t}\\}$, $F_{2}=\\{e\in S_{2}|C\geq c_{e}\mbox{
and }\Delta(e\mid\psi_{t-1})>0\\}$, $t\leftarrow t+1$

##  3 Knapsack Constraint

###  3.1 Algorithm Design

We first present the design of our _Sampling-based Adaptive Density-Greedy
Policy_ $\pi^{sad}$ subject to a knapsack constraint. A detailed description
of $\pi^{sad}$ is listed in Algorithm 1. Our policy is composed of three
candidate policies: $\pi^{1}$, $\pi^{2}$, and $\pi^{3}$. The first candidate
policy $\pi^{1}$ selects a singleton with the maximum expected utility. The
other two candidates $\pi^{2}$ and $\pi^{3}$ follow a simple density-greedy
rule to select items from two random sets respectively. Our final policy
$\pi^{sad}$ randomly picks one solution from the above three candidates such
that $\pi^{1}$ is selected with probability $\delta_{1}$, $\pi^{2}$ is
selected with probability $\delta_{2}$, and $\pi^{3}$ is selected with
probability $1-\delta_{1}-\delta_{2}$. All parameters will be decided later.
Although the framework of $\pi^{sad}$ is similar to the modified density
greedy algorithm Amanatidis et al. (2020), where they only maintain two
candidate policies (one is to choose a high value item and the other one is to
choose items in a greedy manner), its performance analysis is very different,
as their results hold only if the utility function is both adaptive submodular
and pointwise submodular. Later we show that $\pi^{sad}$ achieves a constant
approximation ratio without resorting to the property of pointwise
submodularity. We next describe $\pi^{1}$, $\pi^{2}$, and $\pi^{3}$ in
details.

Design of $\pi^{1}$. Selecting a singleton $e^{*}$ with the maximum expected
utility, i.e., $e^{*}=\arg\max_{e\in E}f(e)$.

Design of $\pi^{2}$. Partition $E$ into two disjoint subsets $S_{1}$ and
$S_{2}$ (or $E\setminus S_{1}$) such that $S_{1}$ contains each item
independently with probability $\delta_{0}$. $\pi^{2}$ selects items only from
$S_{1}$ in a density-greedy manner as follows: In each round $t$, $\pi^{2}$
selects an item $e_{t}$ with the largest “benefit-to-cost” ratio from $F_{1}$
conditioned on the current observation $\psi_{t-1}$

$e_{t}\leftarrow\arg\max_{e\in F_{1}}\frac{\Delta(e\mid\psi_{t-1})}{c_{e}}$

where $F_{1}=\\{e\in S_{1}|C\geq c_{e}\mbox{ and
}\Delta(e\mid\psi_{t-1})>0\\}$. Here we use $C$ to denote the remaining budget
before entering round $t$. After observing the state $\Phi(e_{t})$ of $e_{t}$,
we update the partial realization using
$\psi_{t}=\psi_{t-1}\cup\\{(e_{t},\Phi(e_{t}))\\}$. This process iterates
until $F_{1}$ becomes an empty set.

Design of $\pi^{3}$. Partition $E$ into two disjoint subsets $S_{1}$ and
$S_{2}$ (or $E\setminus S_{1}$) such that $S_{1}$ contains each item
independently with probability $\delta_{0}$. $\pi^{3}$ selects items only from
$S_{1}$ in the same density-greedy manner as used in the design of $\pi^{2}$.

###  3.2 Performance Analysis

Note that all existing results on non-monotone adaptive submodular
maximization Amanatidis et al. (2020), Cui et al. (2021) require Lemma 4 of
Gotovos et al. (2015), whose proof relied on the assumption of the pointwise
submodularity of the utility function. To relax this assumption, we first
provide two technical lemmas, whose proofs do not require pointwise
submodularity. We use $\mathrm{range}(\pi)$ to denote the set containing all
items that $\pi$ selects for some $\phi\in U^{+}$, i.e.,
$\mathrm{range}(\pi)=\\{e|e\in\cup_{\phi\in U^{+}}E(\pi,\phi)\\}$.

###### Lemma 3.1

If $f:2^{E}\times O^{E}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular
with respect to $p(\phi)$, then for any three policies $\pi^{a}$, $\pi^{b}$,
and $\pi^{c}$ such that
$\mathrm{range}(\pi^{b})\cap\mathrm{range}(\pi^{c})=\emptyset$, we have

$\displaystyle f_{avg}(\pi^{a}@\pi^{b})+f_{avg}(\pi^{a}@\pi^{c})\geq
f_{avg}(\pi^{a})$ (2)

_Proof:_ For each $r\in\\{a,b,c\\}$, let
$\overrightarrow{\psi^{r}}=\\{\psi^{r}_{0},\psi^{r}_{1},\psi^{r}_{2},\cdots,\psi^{r}_{|\overrightarrow{\psi^{r}}|-1}\\}$
denote a fixed run of $\pi^{r}$, where for each
$t\in[|\overrightarrow{\psi^{r}}|-1]$, $\psi^{r}_{t}$ is the partial
realization of the first $t$ selected items. For ease of presentation, let
$\psi^{r}$ denote the final observation
$\psi^{r}_{|\overrightarrow{\psi^{r}}|-1}$ of $\overrightarrow{\psi^{r}}$ for
short. For each $e\in\mathrm{range}(\pi^{c})$ and $t\in[n-1]$, let
$I(\pi^{c},e,t+1)$ be indicator variable that $e$ is selected as the
$(t+1)$-th item by $\pi^{c}$. Let
$\overrightarrow{\Psi^{a}},\overrightarrow{\Psi^{b}},\overrightarrow{\Psi^{c}}$
denote random realizations of
$\overrightarrow{\psi^{a}},\overrightarrow{\psi^{b}},\overrightarrow{\psi^{c}}$,
respectively. Then we have

$\displaystyle f_{avg}(\pi^{a}@\pi^{c})-f_{avg}(\pi^{a})~{}$
$\displaystyle=\mathbb{E}_{(\overrightarrow{\Psi^{a}},\overrightarrow{\Psi^{c}})}[\sum_{e\in\mathrm{range}(\pi^{c}),t\in[|\overrightarrow{\Psi^{c}}|-2]}\mathbb{E}[I(\pi^{c},e,t+1)|\Psi^{c}_{t}]\Delta(e\mid\Psi^{a}\cup\Psi^{c}_{t})]~{}$
$\displaystyle=\mathbb{E}_{(\overrightarrow{\Psi^{a}},\overrightarrow{\Psi^{b}},\overrightarrow{\Psi^{c}})}[\sum_{e\in\mathrm{range}(\pi^{c}),t\in[|\overrightarrow{\Psi^{c}}|-2]}\mathbb{E}[I(\pi^{c},e,t+1)|\Psi^{c}_{t}]\Delta(e\mid\Psi^{a}\cup\Psi^{c}_{t})]$
(3)

where the first expectation is taken over the prior joint distribution of
$\overrightarrow{\psi^{a}}$ and $\overrightarrow{\psi^{c}}$ and the second
expectation is taken over the prior joint distribution of
$\overrightarrow{\psi^{a}}$, $\overrightarrow{\psi^{b}}$and
$\overrightarrow{\psi^{c}}$.

$\displaystyle f_{avg}(\pi^{a}@\pi^{b}@\pi^{c})-f_{avg}(\pi^{a}@\pi^{b})~{}$
$\displaystyle=\mathbb{E}_{(\overrightarrow{\Psi^{a}},\overrightarrow{\Psi^{b}},\overrightarrow{\Psi^{c}})}[\sum_{e\in\mathrm{range}(\pi^{c}),t\in[|\overrightarrow{\Psi^{c}}|-2]}\mathbb{E}[I(\pi^{c},e,t+1)|\Psi^{c}_{t}]\Delta(e\mid\Psi^{a}\cup\Psi^{b}\cup\Psi^{c}_{t})]$
(4)

where the expectation is taken over the prior joint distribution of
$\overrightarrow{\psi^{a}}$, $\overrightarrow{\psi^{b}}$and
$\overrightarrow{\psi^{c}}$.

Because $f:2^{E}\times O^{E}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive
submodular with respect to $p(\phi)$, and
$\mathrm{range}(\pi^{b})\cap\mathrm{range}(\pi^{c})=\emptyset$, then for any
given realizations
$(\overrightarrow{\psi^{a}},\overrightarrow{\psi^{b}},\overrightarrow{\psi^{c}})$
after running $\pi^{a}@\pi^{b}@\pi^{c}$, any
$t\in[|\overrightarrow{\psi^{c}}|-2]$, and any item
$e\in\mathrm{range}(\pi^{c})$, we have
$\Delta(e\mid\psi^{a}\cup\psi^{c}_{t})\geq\Delta(e\mid\psi^{a}\cup\psi^{b}\cup\psi^{c}_{t})$
due to $e\notin\mathrm{dom}(\psi^{b})$. This together with (3) and (4) implies
that

$\displaystyle f_{avg}(\pi^{a}@\pi^{c})-f_{avg}(\pi^{a})\geq
f_{avg}(\pi^{a}@\pi^{b}@\pi^{c})-f_{avg}(\pi^{a}@\pi^{b})$

Hence,

$\displaystyle f_{avg}(\pi^{a}@\pi^{b}@\pi^{c})~{}$ (5) $\displaystyle=$
$\displaystyle
f_{avg}(\pi^{a})+(f_{avg}(\pi^{a}@\pi^{b})-f_{avg}(\pi^{a}))+(f_{avg}(\pi^{a}@\pi^{b}@\pi^{c})-f_{avg}(\pi^{a}@\pi^{b}))~{}$
$\displaystyle\leq$ $\displaystyle
f_{avg}(\pi^{a})+(f_{avg}(\pi^{a}@\pi^{b})-f_{avg}(\pi^{a}))+(f_{avg}(\pi^{a}@\pi^{c})-f_{avg}(\pi^{a}))$

Because $f_{avg}(\pi^{a}@\pi^{b}@\pi^{c})\geq 0$, we have

$\displaystyle
f_{avg}(\pi^{a})+(f_{avg}(\pi^{a}@\pi^{b})-f_{avg}(\pi^{a}))+(f_{avg}(\pi^{a}@\pi^{c})-f_{avg}(\pi^{a}))\geq
0$ (6)

It follows that

$\displaystyle f_{avg}(\pi^{a}@\pi^{b})+f_{avg}(\pi^{a}@\pi^{c})$
$\displaystyle=f_{avg}(\pi^{a})+(f_{avg}(\pi^{a}@\pi^{b})-f_{avg}(\pi^{a}))+f_{avg}(\pi^{a})+(f_{avg}(\pi^{a}@\pi^{c})-f_{avg}(\pi^{a}))$
$\displaystyle\geq f_{avg}(\pi^{a})$

The inequality is due to (6). $\Box$

We next present the second technical lemma.

###### Lemma 3.2

Let $\pi\in\Omega$ denote a policy that selects items from $S$ in the same
density-greedy manner as used in the design of $\pi^{2}$ and $\pi^{3}$, where
$S$ is a random set that is obtained by independently picking each item with
probability $\sigma$. If $f:2^{E}\times O^{E}\rightarrow\mathbb{R}_{\geq 0}$
is adaptive submodular with respect to $p(\phi)$, then

$\displaystyle(2+\frac{1}{\sigma})f_{avg}(\pi)+f(e^{*})\geq
f_{avg}(\pi^{opt}@\pi)$ (7)

_Proof:_ In the proof of Theorem 4 of Amanatidis et al. (2020), they show that
(7) holds if $f:2^{E}\times O^{E}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive
submodular and pointwise submodular with respect to $p(\phi)$. In fact, we can
prove a more general result by relaxing the assumption about the property of
pointwise submodularity, i.e., we next show that (7) holds if $f:2^{E}\times
O^{E}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular with respect to
$p(\phi)$. By inspecting the proof of (7) of Amanatidis et al. (2020), it is
easy to find that the only part that requires the property of pointwise
submodularity is the proof of Lemma 5. We next show that Lemma 5 holds without
resorting to pointwise submodularity.

Before restating Lemma 5 in Amanatidis et al. (2020), we introduce some
notations. Let
$\overrightarrow{\psi}=\\{\psi_{0},\psi_{1},\psi_{2},\cdots,\psi_{|\overrightarrow{\psi}|-1}\\}$
denote a fixed run of $\pi$, where for any $t\in[|\overrightarrow{\psi}|-1]$,
$\psi_{t}$ represents the partial realization of the first $t$ selected items.
For notation simplicity, for every $\overrightarrow{\psi}$, let
$\psi^{\prime}$ denote the final observation
$\psi_{|\overrightarrow{\psi}|-1}$ for short. Note that in Amanatidis et al.
(2020), they defer the “sampling” phase of $\pi$ without affecting the
distributions of the output, that is, they toss a coin of success $\sigma$ to
decide whether or not to add an item to the solution each time after an item
is being considered. Let $M(\overrightarrow{\psi})$ denote those items which
are considered but not chosen by $\pi$ which have positive expected marginal
contribution to $\psi^{\prime}$ under $\overrightarrow{\psi}$. Lemma 5 in
Amanatidis et al. (2020) states that
$f_{avg}(\pi)\geq\sigma\times\sum_{\overrightarrow{\psi}}\Pr[\overrightarrow{\psi}]\sum_{e\in
M(\overrightarrow{\psi})}\Delta(e\mid\psi^{\prime})$ where
$\Pr[\overrightarrow{\psi}]$ is the probability that $\overrightarrow{\psi}$
occurs.

For any item $e\in E$, let $\Lambda_{e}$ denote the set of all possible
partial realizations $\psi$ such that $\psi$ is observed right before $e$ is
being considered, i.e., $\Lambda_{e}=\\{\psi\mid\mbox{$\psi$ is the last
observation before $e$ is being considered}\\}$. Let $\mathcal{D}_{e}$ denote
the prior distribution over all partial realizations in $\Lambda_{e}$, i.e.,
for each $\psi\in\Lambda_{e}$, $\mathcal{D}_{e}(\psi)$ is the probability that
$e$ has been considered and $\psi$ is the last observation before $e$ is being
considered. It follows that

$\displaystyle f_{avg}(\pi)$ $\displaystyle=$ $\displaystyle\sum_{e\in
E}\mathbb{E}_{\Psi\sim\mathcal{D}_{e}}[\sigma\times\Delta(e\mid\Psi)]$
$\displaystyle\geq$ $\displaystyle\sum_{e\in
E}\mathbb{E}_{\Psi\sim\mathcal{D}_{e}}[\sigma\times\sum_{\overrightarrow{\psi}}\Pr[\overrightarrow{\psi}\mid\Psi,e]\Delta(e\mid\psi^{\prime})]$
$\displaystyle=$ $\displaystyle\sigma\times\sum_{e\in
E}\mathbb{E}_{\Psi\sim\mathcal{D}_{e}}[\sum_{\overrightarrow{\psi}}\Pr[\overrightarrow{\psi}\mid\Psi,e]\Delta(e\mid\psi^{\prime})]$
$\displaystyle=$
$\displaystyle\sigma\times\sum_{\overrightarrow{\psi}}\Pr[\overrightarrow{\psi}](\sum_{e\in
M(\overrightarrow{\psi})}\Delta(e\mid\psi^{\prime}))$

where $\Pr[\overrightarrow{\psi}\mid\Psi,e]$ is the probability that
$\overrightarrow{\psi}$ occurs conditioned on the event that $e$ is being
considered and $\Psi$ is the last observation before $e$ is being considered.
The first equality is due to the assumption that each item is sampled with
probability $\sigma$, and the inequality is due to the observations that
$e\notin\mathrm{dom}(\psi^{\prime})$, $\Psi\subseteq\psi^{\prime}$ and
$f:2^{E}\times O^{E}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular.
$\Box$

Lemma 3.2, together with the design of $\pi^{2}$ and $\pi^{3}$, implies the
following two corollaries.

###### Corollary 3.3

If $f:2^{E}\times O^{E}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular
with respect to $p(\phi)$, then
$(2+\frac{1}{\delta_{0}})f_{avg}(\pi^{2})+f(e^{*})\geq
f_{avg}(\pi^{opt}@\pi^{2})$.

###### Corollary 3.4

If $f:2^{E}\times O^{E}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular
with respect to $p(\phi)$, then
$(2+\frac{1}{1-\delta_{0}})f_{avg}(\pi^{3})+f(e^{*})\geq
f_{avg}(\pi^{opt}@\pi^{3})$.

Now we are ready to present the main theorem of this section.

###### Theorem 3.5

If $f:2^{E}\times O^{E}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular
with respect to $p(\phi)$, then for $\delta_{1}=1/5$, $\delta_{2}=2/5$, and
$\delta_{0}=1/2$, we have
$f_{avg}(\pi^{sad})\geq\frac{1}{10}f_{avg}(\pi^{opt})$.

_Proof:_ Recall that $\pi^{2}$ and $\pi^{3}$ start with a random partition of
$E$ into two disjoint subsets according to the same distribution. It is safe
to assume that $\pi^{2}$ and $\pi^{3}$ share a common phase of generating such
a partition as this assumption does not affect the expected utility of either
$\pi^{2}$ or $\pi^{3}$. Thus, given a fixed partition $(S_{1},S_{2})$,
$\pi^{2}$ and $\pi^{3}$ are running on two disjoint subsets because $\pi^{2}$
selects items only from $S_{1}$ and $\pi^{3}$ selects items only from $S_{2}$.
It follows that $\mathrm{range}(\pi^{2})\cap\mathrm{range}(\pi^{3})=\emptyset$
conditional on any fixed pair of $(S_{1},S_{2})$. Letting
$\mathbb{E}[f_{avg}(\pi^{opt}@\pi^{2})+f_{avg}(\pi^{opt}@\pi^{3})|(S_{1},S_{2})]$
denote the conditional expected value of
$f_{avg}(\pi^{opt}@\pi^{2})+f_{avg}(\pi^{opt}@\pi^{3})$ conditioned on
$(S_{1},S_{2})$, Lemma 3.1 implies that for any fixed pair of $(S_{1},S_{2})$,

$\displaystyle\mathbb{E}[f_{avg}(\pi^{opt}@\pi^{2})+f_{avg}(\pi^{opt}@\pi^{3})|(S_{1},S_{2})]\geq\mathbb{E}[f_{avg}(\pi^{opt})|(S_{1},S_{2})]~{}$
$\displaystyle=f_{avg}(\pi^{opt})$ (8)

The equality is due to the observation that the expected utility of the
optimal solution $\pi^{opt}$ is independent of the realizations of $S_{1}$ and
$S_{2}$. Taking the expectation of
$\mathbb{E}[f_{avg}(\pi^{opt}@\pi^{2})+f_{avg}(\pi^{opt}@\pi^{3})|(S_{1},S_{2})]$
over $(S_{1},S_{2})$, (8) implies that

$\displaystyle f_{avg}(\pi^{opt}@\pi^{2})+f_{avg}(\pi^{opt}@\pi^{3})\geq
f_{avg}(\pi^{opt})$ (9)

Hence,

$\displaystyle(2+\frac{1}{\delta_{0}})f_{avg}(\pi^{2})+f(e^{*})+(2+\frac{1}{1-\delta_{0}})f_{avg}(\pi^{3})+f(e^{*})~{}$
$\displaystyle\geq f_{avg}(\pi^{opt}@\pi^{2})+f_{avg}(\pi^{opt}@\pi^{3})~{}$
$\displaystyle\geq f_{avg}(\pi^{opt})$ (10)

The first inequality is due to Corollary 3.3 and Corollary 3.4. The second
inequality is due to (9). Because $f(e^{*})=f_{avg}(\pi^{1})$, (10) implies
that

$\displaystyle(2+\frac{1}{\delta_{0}})f_{avg}(\pi^{2})+(2+\frac{1}{1-\delta_{0}})f_{avg}(\pi^{3})+2f_{avg}(\pi^{1})\geq
f_{avg}(\pi^{opt})$

Recall that $\pi^{sad}$ randomly picks one solution from
$\\{\pi^{1},\pi^{2},\pi^{3}\\}$ such that $\pi^{1}$ is picked with probability
$\delta_{1}$, $\pi^{2}$ is picked with probability $\delta_{2}$, and $\pi^{3}$
is picked with probability $1-\delta_{1}-\delta_{2}$. If we set
$\delta_{1}=\frac{2}{(2+\frac{1}{\delta_{0}})+(2+\frac{1}{1-\delta_{0}})+2}$
and
$\delta_{2}=\frac{2+\frac{1}{\delta_{0}}}{(2+\frac{1}{\delta_{0}})+(2+\frac{1}{1-\delta_{0}})+2}$,
then we have

$\displaystyle f_{avg}(\pi^{sad})=$
$\displaystyle\frac{2+\frac{1}{\delta_{0}}}{(2+\frac{1}{\delta_{0}})+(2+\frac{1}{1-\delta_{0}})+2}f_{avg}(\pi^{2})+\frac{2+\frac{1}{1-\delta_{0}}}{(2+\frac{1}{\delta_{0}})+(2+\frac{1}{1-\delta_{0}})+2}f_{avg}(\pi^{3})$
$\displaystyle+\frac{2}{(2+\frac{1}{\delta_{0}})+(2+\frac{1}{1-\delta_{0}})+2}f_{avg}(\pi^{1})\geq\frac{1}{6+\frac{1}{\delta_{0}}+\frac{1}{1-\delta_{0}}}f_{avg}(\pi^{opt})$

If we set $\delta_{0}=1/2$, then
$f_{avg}(\pi^{sad})\geq\frac{1}{10}f_{avg}(\pi^{opt})$. $\Box$

_Remark:_ Recall that under the optimal setting, $\delta_{0}=1/2$, which
indicates that $\pi^{2}$ is identical to $\pi^{3}$. Thus, we can simplify the
design of $\pi^{sad}$ to maintain only two candidate policies $\pi^{1}$ and
$\pi^{2}$. In particular, given that $\delta_{1}=1/5$ and $\delta_{2}=2/5$
under the optimal setting, $\pi^{sad}$ randomly picks a policy from $\pi^{1}$
and $\pi^{2}$ such that $\pi^{1}$ is picked with probability $1/5$ and
$\pi^{2}$ is picked with probability $4/5$. It is easy to verify that this
simplified version of $\pi^{sad}$ and its original version have identical
output distributions.

Algorithm 2 Sampling-based Adaptive Greedy Policy $\pi^{sag}$

1: $S_{1}=\emptyset$, $S_{2}=\emptyset$, $\psi_{0}=\emptyset$, $V=\emptyset$.

2: Sample a number $r_{0}$ uniformly at random from $[0,1]$

3: for $e\in E$ do

4: let $r_{e}\sim\mathrm{Bernoulli}(\delta_{0})$

5: if $r_{e}=1$ then

6: $S_{1}=S_{1}\cup\\{e\\}$

7: else

8: $S_{2}=S_{2}\cup\\{e\\}$

9: if $r_{0}\in[0,\delta_{1})$ then {Adopting the first candidate policy
$\pi^{1}$}

10: $F_{1}=\\{e|e\in S_{1},f(e)>0\\}$

11: while $F_{1}\neq\emptyset$ do

12: $e_{t}\leftarrow\arg\max_{e\in F_{1}}\Delta(e\mid\psi_{t-1})$

13: select $e_{t}$ and observe $\Phi(e_{t})$

14: $\psi_{t}=\psi_{t-1}\cup\\{(e_{t},\Phi(e_{t}))\\}$

15: $V\leftarrow V\cup\\{e_{t}\\}$

16: $S_{1}=S_{1}\setminus\\{e_{t}\\}$, $F_{1}=\\{e\in
S_{1}|V\cup\\{e\\}\in\mathcal{I}\mbox{ and }\Delta(e\mid\psi_{t-1})>0\\}$,
$t\leftarrow t+1$

17: else {Adopting the second candidate policy $\pi^{2}$}

18: $F_{2}=\\{e|e\in S_{2},f(e)>0\\}$

19: while $F_{2}\neq\emptyset$ do

20: $e_{t}\leftarrow\arg\max_{e\in F_{2}}\Delta(e\mid\psi_{t-1})$

21: select $e_{t}$ and observe $\Phi(e_{t})$

22: $\psi_{t}=\psi_{t-1}\cup\\{(e_{t},\Phi(e_{t}))\\}$

23: $V\leftarrow V\cup\\{e_{t}\\}$

24: $S_{2}=S_{2}\setminus\\{e_{t}\\}$, $F_{2}=\\{e\in
S_{2}|V\cup\\{e\\}\in\mathcal{I}\mbox{ and }\Delta(e\mid\psi_{t-1})>0\\}$,
$t\leftarrow t+1$

##  4 $k$-System Constraint

###  4.1 Algorithm Design

We next present a _Sampling-based Adaptive Greedy Policy_ $\pi^{sag}$ subject
to a $k$-system constraint. A detailed description of $\pi^{sag}$ is listed in
Algorithm 2. $\pi^{sag}$ randomly picks one solution from two candidate
policies, $\pi^{1}$ and $\pi^{2}$, such that $\pi^{1}$ is selected with
probability $\delta_{1}$, $\pi^{2}$ is selected with probability
$1-\delta_{1}$. Both $\pi^{1}$ and $\pi^{2}$ follow a simple greedy rule to
select items from two random sets respectively. We next describe $\pi^{1}$ and
$\pi^{2}$ in details. All parameters will be optimized later.

Design of $\pi^{1}$. Partition $E$ into two disjoint subsets $S_{1}$ and
$S_{2}$ (or $E\setminus S_{1}$) such that $S_{1}$ contains each item
independently with probability $\delta_{0}$. $\pi^{1}$ selects items only from
$S_{1}$ in a greedy manner as follows: In each round $t$, $\pi^{1}$ selects an
item $e_{t}$ with the largest marginal value from $F_{1}$ conditioned on the
current observation $\psi_{t-1}$

$e_{t}\leftarrow\arg\max_{e\in F_{1}}\Delta(e\mid\psi_{t-1})$

where $F_{1}=\\{e\in S_{1}|V\cup\\{e\\}\in\mathcal{I}\mbox{ and
}\Delta(e\mid\psi_{t-1})>0\\}$. Here $V$ denotes the first $t-1$ items
selected by $\pi^{1}$. After observing the state $\Phi(e_{t})$ of $e_{t}$, we
update the partial realization using
$\psi_{t}=\psi_{t-1}\cup\\{(e_{t},\Phi(e_{t}))\\}$. This process iterates
until $F_{1}$ becomes an empty set.

Design of $\pi^{2}$. Partition $E$ into two disjoint subsets $S_{1}$ and
$S_{2}$ (or $E\setminus S_{1}$) such that $S_{1}$ contains each item
independently with probability $\delta_{0}$. $\pi^{2}$ selects items only from
$S_{2}$ in the same greedy manner as used in the design of $\pi^{1}$.

###  4.2 Performance Analysis

Before presenting the main theorem, we first provide a technical lemma from
Cui et al. (2021).

###### Lemma 4.1

Cui et al. (2021) Let $\pi\in\Omega$ denote a feasible $k$-system constrained
policy that chooses items from $S$ in the same greedy manner as used in the
design of $\pi^{1}$ and $\pi^{2}$, where $S$ is a random set that is obtained
by independently picking each item with probability $\sigma$. If
$f:2^{E}\times O^{E}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular
with respect to $p(\phi)$, then $(k+\frac{1}{\sigma})f_{avg}(\pi)\geq
f_{avg}(\pi^{opt}@\pi)$.

Lemma 4.1, together with the design of $\pi^{1}$ and $\pi^{2}$, implies the
following two corollaries.

###### Corollary 4.2

If $f:2^{E}\times O^{E}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular
with respect to $p(\phi)$, then $(k+\frac{1}{\delta_{0}})f_{avg}(\pi^{1})\geq
f_{avg}(\pi^{opt}@\pi^{1})$.

###### Corollary 4.3

If $f:2^{E}\times O^{E}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular
with respect to $p(\phi)$, then
$(k+\frac{1}{1-\delta_{0}})f_{avg}(\pi^{2})\geq f_{avg}(\pi^{opt}@\pi^{2})$.

Now we are ready to present the main theorem of this section.

###### Theorem 4.4

If $f:2^{E}\times O^{E}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular
with respect to $p(\phi)$, then for $\delta_{1}=1/2$ and $\delta_{0}=1/2$, we
have $f_{avg}(\pi^{sag})\geq\frac{1}{2k+4}f_{avg}(\pi^{opt})$.

_Proof:_ Following the same proof as for (9), we have

$\displaystyle f_{avg}(\pi^{opt}@\pi^{1})+f_{avg}(\pi^{opt}@\pi^{2})\geq
f_{avg}(\pi^{opt})$ (11)

Hence,

$\displaystyle(k+\frac{1}{\delta_{0}})f_{avg}(\pi^{1})+(k+\frac{1}{1-\delta_{0}})f_{avg}(\pi^{2})~{}$
$\displaystyle\geq f_{avg}(\pi^{opt}@\pi^{1})+f_{avg}(\pi^{opt}@\pi^{2})~{}$
$\displaystyle\geq f_{avg}(\pi^{opt})$ (12)

The first inequality is due to Corollary 4.2 and Corollary 4.3. The second
inequality is due to (11).

Recall that $\pi^{sag}$ randomly picks one solution from
$\\{\pi^{1},\pi^{2}\\}$ such that $\pi^{1}$ is picked with probability
$\delta_{1}$ and $\pi^{2}$ is picked with probability $1-\delta_{1}$. If we
set
$\delta_{1}=\frac{k+\frac{1}{\delta_{0}}}{(k+\frac{1}{\delta_{0}})+(k+\frac{1}{1-\delta_{0}})}$,
then

$\displaystyle f_{avg}(\pi^{sag})=$
$\displaystyle\frac{k+\frac{1}{\delta_{0}}}{(k+\frac{1}{\delta_{0}})+(k+\frac{1}{1-\delta_{0}})}f_{avg}(\pi^{1})+\frac{k+\frac{1}{1-\delta_{0}}}{(k+\frac{1}{\delta_{0}})+(k+\frac{1}{1-\delta_{0}})}f_{avg}(\pi^{2})$
$\displaystyle\geq\frac{1}{(k+\frac{1}{\delta_{0}})+(k+\frac{1}{1-\delta_{0}})}f_{avg}(\pi^{opt})$

If we set $\delta_{0}=1/2$, then
$f_{avg}(\pi^{sag})\geq\frac{1}{2k+4}f_{avg}(\pi^{opt})$. $\Box$

_Remark:_ Recall that under the optimal setting, $\delta_{0}=1/2$, which
indicates that $\pi^{1}$ is identical to $\pi^{2}$. Thus, we can simplify the
design of $\pi^{sag}$ such that it maintains only one policy $\pi^{1}$. It is
easy to verify that this simplified version of $\pi^{sag}$ and its original
version have identical output distributions.

## References

  * Amanatidis et al. (2020) Amanatidis, Georgios, Federico Fusco, Philip Lazos, Stefano Leonardi, Rebecca Reiffenhäuser. 2020.  Fast adaptive non-monotone submodular maximization subject to a knapsack constraint.  Advances in neural information processing systems.
  * Asadpour and Nazerzadeh (2016) Asadpour, Arash, Hamid Nazerzadeh. 2016.  Maximizing stochastic monotone submodular functions.  Management Science 62 2374–2391.
  * Chen and Krause (2013) Chen, Yuxin, Andreas Krause. 2013.  Near-optimal batch mode active learning and adaptive submodular optimization.  ICML (1) 28 8–1.
  * Cui et al. (2021) Cui, Shuang, Kai Han, Tianshuai Zhu, Jing Tang, Benwei Wu, He Huang. 2021.  Randomized algorithms for submodular function maximization with a $k$-system constraint.  International Conference on Machine Learning. PMLR, 2222–2232.
  * Fujii and Sakaue (2019) Fujii, Kaito, Shinsaku Sakaue. 2019.  Beyond adaptive submodularity: Approximation guarantees of greedy policy with adaptive submodularity ratio.  International Conference on Machine Learning. 2042–2051.
  * Golovin and Krause (2011) Golovin, Daniel, Andreas Krause. 2011.  Adaptive submodularity: Theory and applications in active learning and stochastic optimization.  Journal of Artificial Intelligence Research 42 427–486.
  * Gotovos et al. (2015) Gotovos, Alkis, Amin Karbasi, Andreas Krause. 2015.  Non-monotone adaptive submodular maximization.  Twenty-Fourth International Joint Conference on Artificial Intelligence.
  * Guillory and Bilmes (2010) Guillory, Andrew, Jeff Bilmes. 2010.  Interactive submodular set cover.  Proceedings of the 27th International Conference on International Conference on Machine Learning. 415–422.
  * Krause and Guestrin (2007) Krause, Andreas, Carlos Guestrin. 2007.  Near-optimal observation selection using submodular functions.  AAAI, vol. 7. 1650–1654.
  * Nemhauser et al. (1978) Nemhauser, George L, Laurence A Wolsey, Marshall L Fisher. 1978.  An analysis of approximations for maximizing submodular set functions-i.  Mathematical programming 14 265–294.
  * Tang (2020) Tang, Shaojie. 2020.  Price of dependence: stochastic submodular maximization with dependent items.  Journal of Combinatorial Optimization 39 305–314.
  * Tang (2021) Tang, Shaojie. 2021.  Beyond pointwise submodularity: Non-monotone adaptive submodular maximization in linear time.  Theoretical Computer Science 850 249–261.
  * Tang and Yuan (2020) Tang, Shaojie, Jing Yuan. 2020.  Influence maximization with partial feedback.  Operations Research Letters 48 24–28.
  * Wolsey (1982) Wolsey, Laurence A. 1982.  Maximising real-valued submodular functions: Primal and dual heuristics for location problems.  Mathematics of Operations Research 7 410–425.
  * Yuan and Tang (2017a) Yuan, Jing, Shao-Jie Tang. 2017a.  Adaptive discount allocation in social networks.  Proceedings of the 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing. 1–10.
  * Yuan and Tang (2017b) Yuan, Jing, Shaojie Tang. 2017b.  No time to observe: adaptive influence maximization with partial feedback.  Proceedings of the 26th International Joint Conference on Artificial Intelligence. 3908–3914.