Present address: ] Los Alamos National Laboratory, Los Alamos, New Mexico
87545, USA.

# Superconducting pairing symmetry in MoTe2

M. M. Piva<EMAIL_ADDRESS>Max Planck Institute for Chemical Physics
of Solids, Nöthnitzer Straße 40, D-01187 Dresden, Germany  L. O. Kutelak
Brazilian Synchrotron Light Laboratory (LNLS), Brazilian Center for Research
in Energy and Materials (CNPEM), Campinas, Sao Paulo, Brazil  Max Planck
Institute for Chemical Physics of Solids, Nöthnitzer Straße 40, D-01187
Dresden, Germany  R. Borth  Max Planck Institute for Chemical Physics of
Solids, Nöthnitzer Straße 40, D-01187 Dresden, Germany  Y. Liu  [  Condensed
Matter Physics and Materials Science Department, Brookhaven National
Laboratory, Upton, New York 11973, USA  C. Petrovic  Condensed Matter Physics
and Materials Science Department, Brookhaven National Laboratory, Upton, New
York 11973, USA  R. D. dos Reis  Brazilian Synchrotron Light Laboratory
(LNLS), Brazilian Center for Research in Energy and Materials (CNPEM),
Campinas, Sao Paulo, Brazil  M. Nicklas<EMAIL_ADDRESS>Max
Planck Institute for Chemical Physics of Solids, Nöthnitzer Straße 40, D-01187
Dresden, Germany

###### Abstract

Topological superconductors have long been sought for their potential use in
quantum computing. The type-II Weyl semimetal MoTe2 is an obvious candidate,
exhibiting a superconducting state below 500 mK at ambient pressure, but the
question remains whether the pairing is conventional $s^{++}$ or topological
$s^{+-}$. The application of external pressure favors the superconducting
state in MoTe2 and suppresses the structural transition from $1T^{\prime}$ to
$T_{d}$. The competition between the two structures leads to a mixed phase
that strongly enhances the disorder present in the system, remarkably without
affecting the superconducting transition temperature, in contrast to the
expectation of $s^{+-}$ pairing superconductivity. Our thorough analysis of
the electrical and Hall resistivities as a function of pressure yields the
most accurate temperature – pressure phase diagram available to date for MoTe2
and a detailed view of the relationship between disorder and
superconductivity, supporting a conventional $s^{++}$ pairing symmetry.

Much effort is devoted to the search for new materials that will enable the
development of more efficient computing and storage systems [1]. In this
regard, compounds or devices hosting Majorana fermions are being extensively
sought. These particles are their own antiparticles, obey non-Abelian
statistics, and have the potential to be used in fault-tolerant quantum
computing [1, 2, 3, 4].

Topological superconductors are promising materials to host Majorana fermions
or Majorana zero modes. They exhibit gap-less excitations in their non-trivial
surface states and an electron-pair condensate, which is a charge neutral
ground state where electrons and holes are indistinguishable, allowing them to
be their own antiparticles [2, 5]. Topological superconductivity was predicted
to be realized in fully gapped superconductors with odd parity symmetry, such
as $p$-wave superconductors [6], where Majorana fermions could exist in the
vortex cores of these materials [2]. Recently it has been found that
topological superconductivity is also possible in $s$-wave superconductors
[7]. For example, in time-reversal invariant Weyl semimetals with s+-
superconductivity, a topological superconducting state might be present when
the sign change of the superconducting gap occurs between Fermi surfaces of
opposite Chern numbers [8].

The transition metal dichalcogenides are excellent candidates to host
topological superconductivity. These materials have the chemical formula
$TX_{2}$ ($T$ = transition metal, $X$ = chalcogenide) and many are predicted
to be Dirac or Weyl semimetals [2]. Of particular interest is MoTe2 [9], which
has three different structural phases [10]. A hexagonal $P6_{3}/mmc$ structure
($2H$ phase) is observed in semiconducting samples, but this phase can be
easily tuned to the monoclinic $P2_{1}/m$ structure ($1T^{\prime}$ phase), due
to the low energy barrier between these structures. Finally, MoTe2 can also
exhibit a non-centrosymmetric orthorhombic $Pmn2_{1}$ structure ($T_{d}$
phase), which is stable at low temperatures or in thin films [11, 12, 13]. At
ambient pressure, a first order structural transition is observed at
$T_{s}\approx 250$ K from the high temperature $1T^{\prime}$ phase to the
$T_{d}$ phase [14, 10, 9, 15, 16, 17, 18, 19, 20, 21, 22]. The variety of
structural phases present in MoTe2 and the small energy scales required to
tune them suggest that structural disorder may play an important role in this
material and that polymorphs might be kinetically stabilized, as is common in
chalcogenides [23].

In the $T_{d}$ phase, MoTe2 is a type-II time-reversal invariant Weyl
semimetal superconductor with a transition temperature ($T_{c}$) around 500 mK
at ambient pressure [24, 25]. The presence of both non-trivial topology and
superconductivity has led to extensive studies investigating the possibility
of topological superconductivity in MoTe2 [26], however the superconducting
pairing symmetry is still unknown. Muon spin rotation ($\mu$SR) [27], point
contact spectroscopy [28], and electronic gating experiments [29] revealed two
band superconductivity, suggesting unconventional $s^{+-}$ or conventional
$s^{++}$ pairing mechanisms, as observed in most of the iron pnictides [30]
and MgB2 [31]. A strong argument in favor of the $s^{+-}$ pairing is the
suppression of $T_{c}$ with increasing disorder, as observed in MoTe2 samples
with different residual resistance ratios (RRR) [25]. However, this cannot
explain the enhanced $T_{c}$ observed in sulfur or Ta-doped samples [32, 33,
34]. Also $\mu$SR experiments cannot discriminate between $s^{+-}$ and
$s^{++}$. Furthermore, other transport measurements have not detected a
superconducting state down to 25 mK in high quality single crystals [15],
while others claim that superconductivity resides in the $1T^{\prime}$ phase
[35]. Therefore, the realization of a superconducting non-trivial $s^{+-}$
phase in $T_{d}$ MoTe2 is strongly debated.

The application of external pressure suppresses the structural transition and
strongly enhances $T_{c}$, as previously observed in many reports [16, 27, 15,
17, 18, 19]. However, a gray area remains in the temperature – pressure
($T-p$) phase diagram of MoTe2, the so-called mixed phase region, where both
$T_{d}$ and $1T^{\prime}$ structural phases are present. The existence of
these different structural domains increases the disorder in the material,
leading to higher residual resistivities and suppressed quantum oscillation
amplitudes [19, 18]. This enhancement of disorder may allow to distinguish
between $s^{+-}$ and $s^{++}$ superconductivity in MoTe2, as was previously
demonstrated for iron pnictides [36].

In this work we report a detailed study of the $T-p$ phase diagram of MoTe2
using longitudinal and Hall resistivity measurements. Our data, taken at very
small pressure steps, provide the most accurate $T-p$ phase diagram available
to date for MoTe2 and a detailed view of the relationship between structural
phase transitions and superconductivity. A strong enhancement of the
structural disorder in the mixed phase region was observed, remarkably without
affecting the superconducting state, in contrast to the expectation for a
$s^{+-}$ pairing state. Our findings shed new light on the pairing symmetry of
the low pressure superconducting state of MoTe2 and favor a conventional
$s^{++}$ pairing mechanism.

The electrical transport properties of single crystalline MoTe2 grown from Te
flux [24, 22] were studied under hydrostatic pressure using a piston-cylinder
type pressure cell with silicon oil as the pressure transmitting medium and
lead as the pressure gauge [37]. The magnetic field was applied parallel to
the $c$-axis and the current was perpendicular to the field. Temperatures down
to 50 mK and magnetic fields up to 9 T were achieved in different commercial
cryostats.

The $T-p$ phase diagram of MoTe2 has been reported in several works before
[16, 27, 20, 35, 15, 38, 17, 21, 18, 19], and for bulk samples a consensus has
been reached that (i) at ambient pressure, a first-order type structural
transition from the $1T^{\prime}$ to the $T_{d}$ phase takes place around 250
K, which is suppressed to zero temperature in the vicinity of 1 GPa, and that
(ii) at low temperatures, a superconducting phase is present in the entire
temperature-pressure phase diagram up to 3 GPa and beyond. Only the early work
of Qi et al. [16] reported the presence of a structural transition up to about
3 GPa, which was not confirmed by later studies. This work has also led to the
misconception that there is an almost instantaneous increase in $T_{c}$ within
the $T_{d}$ phase below 1 GPa. All more recent studies show a smooth increase
in $T_{c}$ [27, 20, 35, 17, 18].

The behavior summarized above is also observed in our study. We find an
anomaly in the temperature dependence of the electrical resistivity $\rho(T)$
that characterizes the first-order structural transition from $1T^{\prime}$ to
$T_{d}$ at 246(2) K at ambient pressure [see the black arrow in Fig. 1(a)].
Increasing pressure suppresses the structural transition temperature $T_{s}$
to 53(5) K at 0.87 GPa. Above this pressure, our $\rho(T)$ data show no
evidence for the structural phase transition. Already at 0.93 GPa any feature
is missing.

To further investigate the first-order-like suppression of $T_{s}$, we
performed temperature runs at closely spaced pressure points in the region
around the critical pressure $p_{c}\approx 0.9$ GPa. These data confirm the
sudden suppression of $T_{s}$ and show a remarkable change in the curvature of
$T_{s}(p)$. With increasing pressure, $T_{s}(p)$ changes from a concave to a
convex curvature and shows a tendency to saturate before $T_{s}(p)$ is
abruptly suppressed [see the phase diagram in Fig. 3(a)]. This behavior can be
taken as a further indication of a first-order-like suppression of $T_{s}$. At
low temperatures, we observe a strong variation of the normal state
resistivity with pressure and zero resistance, indicating the development of a
superconducting state [see Fig. 1(b)]. Applying pressure increases the
superconducting transition temperature $T_{c}$. We note that the
superconducting transition remains narrow at all pressures.

Figure 1: (a) Electrical resistivity ($\rho$) as a function of temperature for
selected pressures. The arrows indicate the structural transition temperature.
(b) Enlarged view of the low temperature region.

The residual resistivity ratio, ${\rm RRR}=\rho_{300{\rm K}}/\rho_{5{\rm K}}$,
is the appropriate parameter to estimate the degree of disorder-related
scattering present in a material. Figure 2(a) shows that the high-temperature
resistivity $\rho_{300{\rm K}}$ decreases monotonically with pressure, but the
RRR value is strongly suppressed in the mixed-phase region. The competition
between the two structural phases leads to an enhancement of the structural
disorder as well as the disorder-induced scattering in MoTe2. The monotonic
variation of $\rho_{300{\rm K}}(p)$ precludes any extrinsic origin. A clear
indication of the structural origin of the enhanced disorder in the mixed-
phase region is obtained by subtracting the electrical resistivity at 0 from
the 9 T curve. As shown in Fig. 2(b), no resistivity anomaly is observed in
the difference, ruling out a magnetic origin for the $\rho$ enhancement.
Remarkably, the superconducting state is not affected by the increasing
disorder in the mixed-phase region, as $T_{c}$ is monotonically enhanced with
increasing pressure. Moreover, there is a sharp transition to the
superconducting state that occurs independently of the pronounced changes in
the resistivity value, as shown in Fig. 2(c).

Figure 2: (a) Left-axis, electrical resistivity at 300 K ($\rho_{300{\rm K}}$)
and right-axis, residual resistivity ratio (RRR) as a function of pressure.
The dashed and dotted black lines are guides to the eyes. (b) $\rho(p)$ at 5 K
at 0 and 9 T and the difference between the two curves. (c) Electrical
resistivity ($\rho$) in the low temperature range at selected temperatures as
a function of pressure.

In the following we reconcile the implications of the structural transition,
i.e. an inversion symmetry breaking transition from the centrosymmetric
$1T^{\prime}$ to the non-centrosymmetric $T_{d}$ phase, on the
superconductivity, which has been proposed to be topological in the $T_{d}$
phase. $\rho_{\rm 5K}(p)$, the isothermal resistivity at 5 K, is a good
measure of the residual resistivity since there is little temperature
variation in $\rho(T)$ at low temperatures $T\lesssim 10$ K and the sample is
in the normal state at this temperature throughout the pressure window studied
here [see Fig. 2(c)]. It is pressure independent with a value of 1.7
$\mu\Omega$cm up to about 0.75 GPa, followed by a rapid rise to about 3.4
$\mu\Omega$cm at 1.01 GPa. Upon further pressure increase, $\rho_{\rm 5K}(p)$
decreases again to a constant value of 1.4 $\mu\Omega$cm, which is slightly
smaller than the ambient pressure value. The pressure independent behavior in
the low- and high-pressure region away from the mixed phase suggests that
pressure does not lead to any kind of structural defects and only drives the
structural phase transition from the $T_{d}$ to the $1T^{\prime}$ phase. The
pronounced maximum in $\rho_{\rm 5K}(p)$ is therefore directly related to
additional scattering contributions in the mixed phase region and defines its
range at low temperatures between about 0.75 and 1.4 GPa.

Figure 3: (a), (b) Color maps of the electrical resistivity ($\rho$) as a
function of temperature for all studied pressures. Green and purple circles
denote $T_{s}$ and $T_{c}$, respectively. The gray lines in (a) are
equipotential lines of the resistivity and the dotted lines are guides for the
eye. The data used to create the color maps are shown in the Supplemental
Material [39] and are available at Ref. [40]. Figure 4: Carrier densities for
(a) electrons and (b) holes and mobilities for (c) electrons and (d) holes for
MoTe2. The inset in (a) presents the reduced $\chi^{2}$ obtained with the fits
considering two-band or four-band models. The highlighted area indicates the
coexistence region of the two structural phases $T_{d}$ and $1T^{\prime}$
occurs.

To better visualize the features present in the electrical resistivity of
MoTe2, we show a color map in Fig. 3(a). At high temperatures the structural
transition (green symbols) produces a distinct feature in the resistivity
equipotential lines. Below about 50 K the feature does not move with pressure
and remains at about 0.8 GPa. This indicates the first-order-like suppression
of $T_{s}$, which is convincingly shown in the enlarged view of the low-
temperature region in Fig. 3(b). The shading also indicates the region of
increased structural disorder before the onset of superconductivity at lower
temperatures. It is remarkable to see how the superconducting $T_{c}$
increases smoothly in this region. This behavior is not expected for two
separate SC phases with different order parameter symmetry in the
$1T^{\prime}$ and $T_{d}$ structures and suggests the existence of a single
superconducting phase in MoTe2.

The analysis of the Hall conductivity gives more information about the carrier
densities $n_{e(h)}$ and mobilities $\mu_{e(h)}$ (see the Supplemental
Material [39] for further details). Here $e(h)$ denotes electron(hole)-like
charge carriers. We obtain the longitudinal
$\sigma_{xx}=\rho_{xx}/(\rho_{xx}^{2}+\rho_{xy}^{2})$ and the transverse
$\sigma_{xy}=-\rho_{xy}/(\rho_{xx}^{2}+\rho_{xy}^{2})$ conductivities from our
electrical and Hall resistivities. In MoTe2, the application of external
pressure enhances the transport contribution of four pockets (two holes and
two electrons), as previously reported [35]. Therefore, the two-band model is
more suitable for pressures lower than 1.12 GPa, while a four-band model has
been applied for higher pressures, as clearly evidenced by the reduced
$\chi^{2}$ obtained with the fits [see the inset of Fig. 4(a)]. In the mixed-
phase region, the results of the two models partly overlap. Figure 4
summarizes the pressure evolution of the carrier densities and mobilities
obtained from the transport data at 5 K for holes and electrons. At ambient
pressure, the carrier density values are similar to previous reports [17]. The
highlighted gray area represents the mixed-phase region. One can see a smooth
increase in the carrier densities of both electrons and holes with increasing
pressure, which then starts to decrease in the mixed-phase region, reaching a
minimum at 0.84 GPa [see Figs. 4(a) and 4(b)]. Above this pressure the carrier
densities start to increase again and saturate at high pressures for all 4
pockets. Both electron and hole mobilities are suppressed with increasing
pressure and reach a minimum in the mixed-phase region [see Figs. 4(c) and
4(d)]. After the appearance of the new hole and electron pockets, the mobility
for one pocket is almost pressure independent, while for the others it is
strongly increased and then saturates above 1.5 GPa. These results highlight
the distinct differences in the electronic properties of the $1T^{\prime}$ and
$T_{d}$ phases, in contrast to the smooth evolution of the superconducting
$T_{c}$ as a function of pressure over the entire pressure range studied.

Our results show a smooth variation of $T_{c}(p)$, independent of the large
increase in the residual resistivity, indicating enhanced disorder scattering,
near the critical pressure where $T_{s}$ is suppressed. Furthermore,
pronounced changes in the electronic properties were evidenced by the distinct
pressure evolution of the charge carrier density and mobility. These features
enabled us to draw conclusions about the possible superconducting order
parameter(s) in MoTe2. A topological $s^{+-}$ superconducting state has been
proposed to be realized in the non-centrosymmetric $T_{d}$ phase and a
conventional $s^{++}$ state in the centrosymmetric $1T^{\prime}$ phase [27,
41]. However, it is quite challenging to directly probe the relationship
between the superconducting state and the crystalline structure as a function
of pressure at temperatures below 5 K. While $s^{++}$ superconductivity is
nearly insensitive to structural disorder, $s^{+-}$ is expected to be strongly
suppressed by it [8, 6]. We observe an enhancement of $T_{c}$ with increasing
pressure in the mixed-phase regime where the residual resistivity is maximal.
This seems to rule out the possibility of topological $s^{+-}$ pairing in
MoTe2. We therefore propose a scenario in which only the $1T^{\prime}$ phase
exhibits (conventional) superconductivity at low temperatures and the $T_{d}$
phase remains normal at all pressures.

Previous studies proposing a topological $s^{+-}$ pairing in MoTe2 based on
the suppression of $T_{c}$ as a function of disorder did not consider the
possible presence of the $1T’$ phase at low temperatures in the entire
pressure range down to ambient pressure. Our proposal implies that a small
amount of the $1T^{\prime}$ phase is already present in the material at low
pressures. Cho et al. actually report the presence of the $1T^{\prime}$ phase
at ambient pressure as a function of the residual resistivity ratio [42].
According to this work, the ${\rm RRR}=178$ of our sample would imply a very
small fraction of the $1T^{\prime}$ phase of a few percent present at ambient
pressure. This is not inconsistent with other work claiming only the presence
of the $T_{d}$ phase at low temperatures, since such a small volume fraction
of the $1T^{\prime}$ phase may not be resolved in X-ray diffraction. Evidence
for the presence of the $1T^{\prime}$ phase at low pressures has been reported
in Ref. [15, 42] and no zero-resistance state has been observed in samples
lacking the $1T^{\prime}$ structure. We note that even a small volume fraction
of the $1T^{\prime}$ phase in the sample could cause a sharp superconducting
jump in resistivity and produce a full-volume diamagnetic shielding in AC
susceptibility experiments, as previously reported for polycrystalline samples
[27]. The smooth evolution of $T_{c}(p)$ is also difficult to reconcile with
an expected phase transition from a topological $s^{+-}$ to a conventional
$s^{++}$ superconducting state. Our proposal of a (conventional)
superconducting state in the $1T^{\prime}$ phase, present over the entire
pressure range at low temperatures, explains the observed behavior in a
natural way.

In conclusion, we have performed a detailed investigation of the temperature –
pressure phase diagram of MoTe2 by electrical transport experiments. Our data
reveal a first-order-like suppression of the structural phase transition and a
strong increase of the disorder scattering contribution to the electrical
resistivity in the mixed-phase regime around the first order phase transition.
Surprisingly, we find a smooth increase of the superconducting transition
temperature over the whole pressure range. This leads us to conclude that
topological $s^{+-}$ superconductivity is most likely not realized in MoTe2.
Based on our data, we argue that only the $1T^{\prime}$ phase exhibits
superconductivity at low temperatures.

Data that underpin the ﬁndings of this paper are available at Edmond – the
open research data repository of the Max Planck Society at Ref. [40].

###### Acknowledgements.

We acknowledge fruitful discussions with Michael Baenitz, Takuto Fuji and
Hiroshi Yasuoka. This project has received funding from the European Union’s
Horizon 2020 research and innovation programme under the Marie Skłodowska-
Curie grant agreement No 101019024. This work was also supported by the São
Paulo Research Foundation (FAPESP) grants 2018/0823-0, 2021/02314-9 and
2022/05447-2. Work at Brookhaven National Laboratory was supported by U.S.
DOE, Office of Science, Office of Basic Energy Sciences under Contract No. DE-
SC0012704 (materials synthesis). R.D.d.R. and L.O.K. acknowledge financial
support from the Max Planck Society under the auspices of the Max Planck
Partner Group R. D. dos Reis of the Max Planck Institute for Chemical Physics
of Solids, Dresden, Germany.

## References

  * He  _et al._ [2019] M. Y. He, H. M. Sun, and Q. L. He, Topological insulator: Spintronics and quantum computations, Front. Phys. 14, 43401 (2019).
  * Sharma  _et al._ [2022] M. M. Sharma, P. Sharma, N. K. Karn, and V. P. S. Awana, Comprehensive review on topological superconducting materials and interfaces, Supercond. Sci. Technol. 35, 083003 (2022).
  * Nayak  _et al._ [2008] C. Nayak, S. H. Simon, A. Stern, M. Freedman, and S. Das Sarma, Non-Abelian anyons and topological quantum computation, Rev. Mod. Phys. 80, 1083 (2008).
  * Lian  _et al._ [2018] B. Lian, X. Q. Sun, A. Vaezi, X. L. Qi, and S. C. Zhang, Topological quantum computation based on chiral Majorana fermions, Proc. Natl. Acad. Sci. USA 115, 10938 (2018).
  * Wilczek [2009] F. Wilczek, Majorana returns, Nat. Phys. 5, 614 (2009).
  * Qi and Zhang [2011] X.-L. Qi and S.-C. Zhang, Topological insulators and superconductors, Rev. Mod. Phys. 83, 1057 (2011).
  * Sato  _et al._ [2010] M. Sato, Y. Takahashi, and S. Fujimoto, Non-Abelian topological orders and Majorana fermions in spin-singlet superconductors, Phys. Rev. B 82, 134521 (2010).
  * Hosur  _et al._ [2014] P. Hosur, X. Dai, Z. Fang, and X.-L. Qi, Time-reversal-invariant topological superconductivity in doped Weyl semimetals, Phys. Rev. B 90, 045130 (2014).
  * Paul  _et al._ [2023] S. Paul, S. Talukdar, R. S. Singh, and S. Saha, Topological Phase Transition in MoTe2: A Review, Phys. Status Solidi RRL 17, 2200420 (2023).
  * Guo and Liu [2021] J. Guo and K. Liu, Recent progress in two-dimensional MoTe2 hetero-phase homojunctions, Nanomaterials 12, 110 (2021).
  * Cui  _et al._ [2019] J. Cui, P. L. Li, J. D. Zhou, W. Y. He, X. W. Huang, J. Yi, J. Fan, Z. Q. Ji, X. N. Jing, F. M. Qu, Z. G. Cheng, C. L. Yang, L. Lu, K. Suenaga, J. W. Liu, K. T. Law, J. H. Lin, Z. Liu, and G. T. Liu, Transport evidence of asymmetric spin-orbit coupling in few-layer superconducting 1Td-MoTe2, Nat. Commun. 10, 2044 (2019).
  * He  _et al._ [2018] R. He, S. Z. Zhong, H. H. Kim, G. H. Ye, Z. P. Ye, L. Winford, D. McHaffie, I. Rilak, F. C. Chen, X. Luo, Y. P. Sun, and A. W. Tsen, Dimensionality-driven orthorhombic MoTe2 at room temperature, Phys. Rev. B 97, 041410 (2018).
  * Kowalczyk  _et al._ [2023] H. Kowalczyk, J. Biscaras, N. Pistawala, L. Harnagea, S. Singh, and A. Shukla, Gate and Temperature Driven Phase Transitions in Few-Layer MoTe2, ACS Nano 17, 6708– (2023).
  * Clarke  _et al._ [1978] R. Clarke, E. Marseglia, and H. Hughes, A low-temperature structural phase transition in $\beta$-MoTe2, Philos. Mag. B 38, 121 (1978).
  * Heikes  _et al._ [2018] C. Heikes, I. L. Liu, T. Metz, C. Eckberg, P. Neves, Y. Wu, L. D. Hung, P. Piccoli, H. B. Cao, J. Leao, J. Paglione, T. Yildirim, N. P. Butch, and W. Ratcliff, Mechanical control of crystal symmetry and superconductivity in Weyl semimetal MoTe2, Phys. Rev. Mater. 2, 074202 (2018).
  * Qi  _et al._ [2016] Y. P. Qi, P. G. Naumov, M. N. Ali, C. R. Rajamathi, W. Schnelle, O. Barkalov, M. Hanfland, S. C. Wu, C. Shekhar, Y. Sun, V. Suss, M. Schmidt, U. Schwarz, E. Pippel, P. Werner, R. Hillebrand, T. Forster, E. Kampert, S. Parkin, R. J. Cava, C. Felser, B. H. Yan, and S. A. Medvedev, Superconductivity in Weyl semimetal candidate MoTe2, Nat. Commun. 7, 11038 (2016).
  * Hu  _et al._ [2019] Y. J. Hu, Y. T. Chan, K. T. Lai, K. O. Ho, X. Y. Guo, H. P. Sun, K. Y. Yip, D. H. L. Ng, H. Z. Lu, and S. K. Goh, Angular dependence of the upper critical field in the high-pressure 1T’ phase of MoTe2, Phys. Rev. Mater. 3, 034201 (2019).
  * Hu  _et al._ [2020] Y. J. Hu, W. C. Yu, K. T. Lai, D. Sun, F. F. Balakirev, W. Zhang, J. Y. Xie, K. Y. Yip, E. I. P. Aulestia, R. Jha, R. Higashinaka, T. D. Matsuda, Y. Yanase, Y. Aoki, and S. K. Goh, Detection of hole pockets in the candidate type-II Weyl semimetal MoTe2 from Shubnikov-de Haas quantum oscillations, Phys. Rev. Lett. 124, 076402 (2020).
  * Liu  _et al._ [2020] I. L. Liu, C. Heikes, T. Yildirim, C. Eckberg, T. Metz, H. Kim, S. Ran, W. D. Ratcliff, J. Paglione, and N. P. Butch, Quantum oscillations from networked topological interfaces in a Weyl semimetal, npj Quantum Mater. 5, 62 (2020).
  * Takahashi  _et al._ [2017] H. Takahashi, T. Akiba, K. Imura, T. Shiino, K. Deguchi, N. K. Sato, H. Sakai, M. S. Bahramy, and S. Ishiwata, Anticorrelation between polar lattice instability and superconductivity in the weyl semimetal candidate MoTe2, Phys. Rev. B 95, 100501 (2017).
  * Dissanayake  _et al._ [2019] S. Dissanayake, C. R. Duan, J. J. Yang, J. Liu, M. Matsuda, C. M. Yue, J. A. Schneeloch, J. C. Y. Teo, and D. Louca, Electronic band tuning under pressure in MoTe2 topological semimetal, npj Quantum Mater. 4, 45 (2019).
  * Yang  _et al._ [2017] J. Yang, J. Colen, J. Liu, M. C. Nguyen, G.-w. Chern, and D. Louca, Elastic and electronic tuning of magnetoresistance in MoTe2, Sci. Adv. 3, eaao4949 (2017).
  * Kanatzidis [2017] M. G. Kanatzidis, Discovery-synthesis, design, and prediction of chalcogenide phases, Inorg. Chem. 56, 3158 (2017).
  * Wang  _et al._ [2016] Z. Wang, D. Gresch, A. A. Soluyanov, W. Xie, S. Kushwaha, X. Dai, M. Troyer, R. J. Cava, and B. A. Bernevig, MoTe2: a type-II Weyl topological metal, Phys. Rev. Lett. 117, 056805 (2016).
  * Rhodes  _et al._ [2017] D. Rhodes, R. Schönemann, N. Aryal, Q. Zhou, Q. Zhang, E. Kampert, Y.-C. Chiu, Y. Lai, Y. Shimura, G. McCandless, _et al._ , Bulk Fermi surface of the Weyl type-II semimetallic candidate $\gamma$-MoTe2, Phys. Rev. B 96, 165134 (2017).
  * Luo  _et al._ [2016] X. Luo, F. C. Chen, J. L. Zhang, Q. L. Pei, G. T. Lin, W. J. Lu, Y. Y. Han, C. Y. Xi, W. H. Song, and Y. P. Sun, T-d-MoTe2: A possible topological superconductor, Appl. Phys. Lett. 109, 136 (2016).
  * Guguchia  _et al._ [2017] Z. Guguchia, F. von Rohr, Z. Shermadini, A. T. Lee, S. Banerjee, A. Wieteska, C. Marianetti, B. Frandsen, H. Luetkens, Z. Gong, _et al._ , Signatures of the topological $s^{+-}$ superconducting order parameter in the type-II Weyl semimetal Td-MoTe2, Nat. Commun. 8, 1 (2017).
  * Luo  _et al._ [2020] J. W. Luo, Y. N. Li, J. W. Zhang, H. R. Ji, H. Wang, J. Y. Shan, C. X. Zhang, C. Cai, J. Liu, Y. Wang, Y. Zhang, and J. Wang, Possible unconventional two-band superconductivity in MoTe2, Phys. Rev. B 102, 064502 (2020).
  * Jindal  _et al._ [2023] A. Jindal, A. Saha, Z. Li, T. Taniguchi, K. Watanabe, J. C. Hone, T. Birol, R. M. Fernandes, C. R. Dean, A. N. Pasupathy, _et al._ , Coupled ferroelectricity and superconductivity in bilayer Td-MoTe2, Nature 613, 48 (2023).
  * Fernandes  _et al._ [2022] R. M. Fernandes, A. I. Coldea, H. Ding, I. R. Fisher, P. Hirschfeld, and G. Kotliar, Iron pnictides and chalcogenides: a new paradigm for superconductivity, Nature 601, 35 (2022).
  * Szabó  _et al._ [2001] P. Szabó, P. Samuely, J. Kačmarčík, T. Klein, J. Marcus, D. Fruchart, S. Miraglia, C. Marcenat, and A. Jansen, Evidence for two superconducting energy gaps in MgB2 by point-contact spectroscopy, Phys. Rev. Lett. 87, 137005 (2001).
  * Li  _et al._ [2018] Y. Li, Q. Gu, C. Chen, J. Zhang, Q. Liu, X. Hu, J. Liu, Y. Liu, L. Ling, M. Tian, _et al._ , Nontrivial superconductivity in topological MoTe2-xSx crystals, Proc. Natl. Acad. Sci. U.S.A. 115, 9503 (2018).
  * Chen  _et al._ [2016] F. Chen, X. Luo, R. Xiao, W. Lu, B. Zhang, H. Yang, J. Li, Q. Pei, D. Shao, R. Zhang, _et al._ , Superconductivity enhancement in the S-doped Weyl semimetal candidate MoTe2, Appl. Phys. Lett. 108, 162601 (2016).
  * [34] Y. Zhang, F. Fei, R. Liu, T. Zhu, B. Chen, T. Qiu, Z. Zuo, J. Guo, W. Tang, L. Zhou, _et al._ , Enhanced Superconductivity and Upper Critical Field in Ta-Doped Weyl Semimetal Td-MoTe2, Adv. Mater. 10.1002/adma.202207841.
  * Lee  _et al._ [2018] S. Lee, J. Jang, S.-I. Kim, S.-G. Jung, J. Kim, S. Cho, S. W. Kim, J. Y. Rhee, K.-S. Park, and T. Park, Origin of extremely large magnetoresistance in the candidate type-II Weyl semimetal MoTe2-x, Sci. Rep. 8, 1 (2018).
  * Ghigo  _et al._ [2018] G. Ghigo, D. Torsello, G. Ummarino, L. Gozzelino, M. A. Tanatar, R. Prozorov, and P. Canfield, Disorder-driven transition from $s_{\pm}$ to $s_{++}$ superconducting order parameter in proton irradiated Ba(Fe1-xRhx)2As2 single crystals, Phys. Rev. Lett. 121, 107001 (2018).
  * Nicklas [2015] M. Nicklas, Pressure probes, in  _Strongly Correlated Systems_ (Springer, 2015) pp. 173–204.
  * Takahashi  _et al._ [2019] H. Takahashi, K. Hasegawa, T. Akiba, H. Sakai, M. S. Bahramy, and S. Ishiwata, Giant enhancement of cryogenic thermopower by polar structural instability in the pressurized semimetal MoTe2, Phys. Rev. B 100, 195130 (2019).
  * [39] The Supplemental Material at url provides additional information on the two-band and four-band model fits of the longitudinal and Hall conductivity. It also contains the electrical resistivity as a function of temperature at every studied pressure. It includes Ref. [35] .
  * [40] See 10.17617/3.WSL8ZP.
  * Guguchia  _et al._ [2020] Z. Guguchia, A. M. dos Santos, F. O. von Rohr, J. J. Molaison, S. Banerjee, D. Rhodes, J. X. Yin, R. Khasanov, J. Hone, Y. J. Uemura, M. Z. Hasan, H. Luetkens, E. S. Bozin, and A. Amato, Pressure Induced Topological Quantum Phase Transition in Weyl Semimetal Td-MoTe2, J. Phys. Soc. Jpn. 89, 094707 (2020).
  * Cho  _et al._ [2017] S. Cho, S. H. Kang, H. S. Yu, H. W. Kim, W. Ko, S. W. Hwang, W. H. Han, D. H. Choe, Y. H. Jung, K. J. Chang, Y. H. Lee, H. Yang, and S. W. Kim, Te vacancy-driven superconductivity in orthorhombic molybdenum ditelluride, 2D Materials 4, 021030 (2017).


# On Periodic Points in Covering Systems

Wang Yihan
<EMAIL_ADDRESS>
###### Abstract

We study a system of intervals $I_{1},\ldots,I_{k}$ on the real line and a
continuous map $f$ with $f(I_{1}\cup I_{2}\cup\ldots\cup I_{k})\supseteq
I_{1}\cup I_{2}\cup\ldots\cup I_{k}$. It’s conjectured that there exists a
periodic point of period $\leq k$ in $I_{1}\cup\ldots\cup I_{k}$. In this
paper, we prove the conjecture by a discretization method and reduce the
initial problem to an interesting combinatorial lemma concerning cyclic
permutations. We also obtain a non-concentration property of periodic points
of small periods in intervals.

##  1 Introduction

We consider a continuous mapping $f$: $\mathbb{R}\to\mathbb{R}$, and $k$
closed intervals $I_{1},I_{2},...,I_{k}$. Throughout this paper, $f^{l}$
denotes the $l$-th iterate of $f$. And all the mappings are assumed to be
continuous unless otherwise noted.

######  Definition 1.1.

We call $(I_{1},I_{2},\ldots,I_{k};f)$ a $covering\ system$ if $f(I_{1}\cup
I_{2}\cup\ldots\cup I_{k})\supseteq I_{1}\cup I_{2}\cup\ldots\cup I_{k}$.

This concept was first introduced by S. A. Bogatyi and E. T. Shavgulidze in
their paper [1], when they tried to obtain an analogue of Sharkovskii’s
theorem for an arbitrary tree. They proved the existence of a periodic point
of period $\leq g(n)$ in a covering system and established an upper bound for
$g(n)$ $(g(n)\leq 2(n^{2}-1)g(n-1)^{n-2})$. Moreover, they showed $g(n)=n$ for
$n\leq 4$ and conjectured in the remark that $g(n)=n$ holds for all
$n\in\mathbb{N}$, which is proved in this paper as the main theorem.

######  Theorem 1.2.

For any covering system $(I_{1},I_{2},\ldots,I_{k};f)$, there exists $x_{0}\in
I_{1}\cup I_{2}\cup\ldots\cup I_{k}$ and $l\leq k$ such that
$f^{l}(x_{0})=x_{0}$.

We will prove this theorem by a discretization method, which reduces the
initial problem to a lemma in combinatorics. The main idea is to cut the
intervals into small subintervals and perturb the mapping $f$ to get a cyclic
permutation. And the proof of the theorem is completed by observing a property
of cyclic elements of $S_{n}$.

The proof of the main theorem 1.2 will be divided into several steps and
discussed in the following sections. We now state a well-known proposition
which will be frequently used in the proof of theorem 1.2.

######  Proposition 1.3 (the case $k=1$).

Let $f:I\to\mathbb{R}$ satisfy $f(I)\supseteq I$. Then there exists a fixed
point of $f$ in $I$.

This fact is an easy consequence of the intermediate value theorem in calculus
so we omit the proof. And we will see later that for $k$ larger, most cases
can be reduced to this fundamental one.

We would like to end this introduction with the statement of the main lemma
used in the proof of theorem 1.2, which studies the properties of cyclic
permutations. Actually, this lemma is an extension of a lemma proved in
Sharkovskii’s celebrated paper [2]. See the remark below.

######  Definition 1.4.

Let $f$ be a cyclic permutation in the symmetric group $S_{n}$, $i.e.$, $f$
can be written as $(i_{1}i_{2}\ldots i_{n})$, meaning that $f:i_{1}\to
i_{2}\to\ldots\to i_{n}\to i_{1}$. And let $A_{i}=\\{i,i+1\\}$
$(i=1,2,\ldots,n-1)$ be $(n-1)$ particular sets. We define the characteristic
number $m_{i}$ of each $A_{i}$ as

$m_{i}=\min\\{m\arrowvert\ (convf)^{m}(A_{i})\supseteq A_{i}\\}.$

Here, $convf(A)=$ convex hull of $f(A)=\\{\min f(A),\min f(A)+1,\ldots,\max
f(A)\\}$ for any finite set $A\subseteq\mathbb{N}$.

And we define the characteristic sequence of $f$ to be

$m_{1}^{\prime}\leq m_{2}^{\prime}\leq\ldots\leq m_{n-1}^{\prime},$

where $\\{m_{i}^{\prime}\\}$ is a rearrangement of $\\{m_{i}\\}$.

######  Example 1.5.

If $f=(136245)\in S_{6}$, then we can calculate $m_{1}=m_{3}=m_{5}=3$,
$m_{2}=2$, $m_{4}=1$. The characteristic sequence is $1\leq 2\leq 3\leq 3\leq
3$.

Take $m_{2}$ as an example. Since $f(A_{2})=f(\\{2,3\\})=\\{4,6\\}$,
$convf(A_{2})=conv\\{4,6\\}=\\{4,5,6\\}$; and $f(\\{4,5,6\\})=\\{1,2,5\\}$,
$conv\\{1,2,5\\}=\\{1,2,3,4,5\\}$; therefore,
$(convf)^{2}(A_{2})=\\{1,2,3,4,5\\}\supseteq A_{2}$ and we have $m_{2}=2$.

Now we can state our main lemma.

######  Lemma 1.6.

For any cyclic permutation $f$ in the symmetric group $S_{n}$, the
characteristic sequence $\\{m_{i}^{\prime}\\}$ of $f$ satisfies
$m_{i}^{\prime}\leq i$, $i=1,2,\ldots,n-1$.

######  Remark 1.7.

(1) For another form of this lemma more closely related to the initial
problem, see lemma 2.3 in the next section.

(2) In theorem 7 of Sharkovskii’s paper [2], it is actually proved that
$m_{i}^{\prime}\leq n-1$, for $i=1,2,\ldots,n-1$. Therefore, this lemma is a
generalization of that result.

Meanwhile, this lemma leads in some sense to a non-concentration property of
periodic points with lower periods. Namely, it follows that if
$x_{k_{1}}<x_{k_{2}}<\ldots<x_{k_{n}}$ is an orbit of periodic points of
period $n$ under $f$, then between any two adjacent points $x_{k_{i}}$ and
$x_{k_{i+1}}$, there exists a periodic point $y_{i}$ of period $m_{i}\leq
n-1$. Futhermore, these $(n-1)$ numbers $m_{i}$ can be rearranged to have
$m_{i}^{\prime}\leq i$. In other words, all the periodic points of period
$\leq i$ cannot lie only in $(i-1)$ of the intervals
$[x_{k_{j}},x_{k_{j+1}}]$, $1\leq j\leq n-1$.

(3) One can see that the statement of lemma 1.6 doesn’t involve any notations
in analysis. And hence it is of independent interest in the study of the
symmetric group $S_{n}$ in combinatorics.

(4) It is necessary to require the permutation be cyclic. As a counterexmaple,
consider $f=(13)(2)\in S_{3}$, then the characteristic numbers are
$m_{1}=m_{2}=2$.

We organize the paper as follows. In section 2, we introduce the
discretization method and reduce theorem 1.2 in dynamics to a lemma in
combinatorics. Then in section 3, we prove the equivalence of the lemma in
section 2 and the one stated above. Finally in section 4, we prove lemma 1.6 .

##  2 Discretization

In this section we show that Theorem 1.2 can be proved by solving another
discrete problem related to it. The main idea is to divide the initial
intervals into smaller subintervals, such that the image of each subinterval
under $f$ contains the whole of some other subintervals, not just part of
them. However, it may happen that no matter how you divide the intervals,
there will be an interval whose image under $f$ contains only part of another
interval. What saves us here is that, we can consider perturbation of $f$ if
the intervals are cut into enough small pieces. Indeed, we will use the
following lemma:

######  Lemma 2.1.

If there is a covering system $(I_{1},I_{2},\ldots,I_{k};f)$ such that
$\forall x\in I_{1}\cup\ldots\cup I_{k}$, and $\forall\>l\leq k,f^{l}(x)\neq
x,$ then $\exists\>\delta>0$ depending on $f$, $s.t.$, whenever $\lVert
g-f\rVert_{C(\mathbb{R})}<\delta$, it also holds that $g^{l}(x)\neq x$, for
all $l\leq k$, $x\in I_{1}\cup\ldots\cup I_{k}$.

###### Proof.

Recall that $f$ has a periodic point of period $\leq k$ in
$I_{1}\cup\ldots\cup I_{k}$ is equivalent to that
$F(x)=(f(x)-x)\ldots(f^{k}(x)-x)$ has a zero in $I_{1}\cup\ldots\cup I_{k}$.
Therefore, we only need to control $\lvert f^{l}(x)-g^{l}(x)\rvert$ for $1\leq
l\leq k$, $x\in I_{1}\cup\ldots\cup I_{k}$. And this will be done inductively.
Indeed, we can write:

$f^{l+1}(x)-g^{l+1}(x)=f(f^{l}(x))-f(g^{l}(x))+f(g^{l}(x))-g(g^{l}(x))$

And if we assume we have proved $\lvert f^{l}(x)-g^{l}(x)\rvert$ is
sufficiently small (at least less than 1) for all $x\in I_{1}\cup\ldots\cup
I_{k}$, then choose a closed interval $[p,q]$ containing
$f^{l}(I_{1}\cup\ldots\cup I_{k})$. We will have $g^{l}(I_{1}\cup\ldots\cup
I_{k})\subseteq[\,p-1,\,q+1\,]$. Thus, we will obtain a control of $\lvert
f^{l+1}(x)-g^{l+1}(x)\rvert$ when $x\in I_{1}\cup\ldots\cup I_{k}$, since $f$
is uniformly continuous on $[\,p-1,\,q+1\,]$ and $\lVert
g-f\rVert_{C(\mathbb{R})}<\delta$. Finally, we repeat the procedure $k$ times
and get the conclusion. ∎

Now we can introduce the discrete problem related to Theorem 1.2. To begin
with, we make a technical assumption on the initial covering system in Lemma
2.1. (See remark 2.4 for the reason). Namely, if $I_{j}=[a_{j},b_{j}]$ and
$f(I_{j})=[c_{j},d_{j}]$ in the given covering system
$(I_{1},I_{2},\ldots,I_{k};f)$, then we can assume
$f(\\{a_{j},b_{j}\\})=\\{c_{j},d_{j}\\}$ without loss of generality, since we
can replace $I_{j}$ by a smaller subinterval if necessary.

Let $a_{1}<b_{1}<a_{2}<b_{2}<\ldots<a_{k}<b_{k}$ be all the end points of the
intervals $I_{1},\ldots,I_{k}$ and denote
$M_{0}=\\{a_{1},b_{1},\ldots,a_{k},b_{k}\\}$. Consider their images
$f(M_{0})=\\{f(a_{1}),\ldots,f(b_{k})\\}$ and we eliminate the points which
don’t belong to $I_{1}\cup\ldots\cup I_{k}$ to obtain a set $S_{1}\subseteq
f(M_{0})$. Put $M_{1}=M_{0}\cup S_{1}$. Inductively, in each step we consider
the image of $M_{i}$ under the mapping $f$ and we eliminate those points
dropping out of $I_{1}\cup...\cup I_{k}$ to get a set $S_{i+1}\subseteq
f(M_{i})$. Then let $M_{i+1}=M_{i}\cup S_{i+1}$.

Finally we obtain a sequence of sets $M_{0}\subseteq
M_{1}\subseteq\ldots\subseteq M_{i}\subseteq\ldots$, where each $M_{i}$
contains the images of the initial end point set $M_{0}$ under
{$id,f,f^{2},\ldots,f^{i}$} except for those dropping out of
$I_{1}\cup\ldots\cup I_{k}$.

Then we can find a sufficiently large integer $N$ such that $\forall x\in
M_{N}-M_{N-1}$, $dist(x,M_{N-1})<\delta$, where $\delta$ comes from Lemma 2.1.
Such $N$ exists because if not, there will be a sequence of disjoint points in
$[a_{1},b_{k}]$ with pairwise distance larger than $\delta$, which is absurd.
Therefore, we can take small perturbation of $f$ to get a map $\tilde{f}$ with
$\lVert\tilde{f}-f\rVert<\delta$, and $\widetilde{M_{N-1}}=\widetilde{M_{N}}$
for $\tilde{f}$. Indeed, we just move each point $(x_{0},f(x_{0}))\in
M_{N-1}\times M_{N}$ on the graph of $f$ to the nearest point
$(x_{0},y_{0})\in\\{x_{0}\\}\times M_{N-1}$ preserving the continuity and the
covering property of $f$. For example, in a neighborhood of each $x_{0}\in
M_{N}$, we can define $\tilde{f}(x)=f(x)\pm\sigma\phi(x-x_{0})$, where
$0\leq\phi\leq 1$ is a cut-off function, $\phi(0)=1$, $\sigma<\delta$ is
chosen so that $\tilde{f}(x_{0})\in M_{N-1}$. And for different $x_{0}$ we
choose different signs $\pm$ so that $(I_{1},I_{2},\ldots,I_{k};\tilde{f})$ is
still a covering system. (See Figure 1 and 2.)

Thus, if we divide the intervals into small pieces using the points in
$\widetilde{M_{N}}$, then $\tilde{f}$ will have the nice property that the
image of each subinterval contains entirely another one or more subintervals.
In other words, $\tilde{f}$ can be regarded as a discrete mapping from
$\\{1,2,\ldots,n\\}$ to {subsets of $\\{1,2,\ldots,n\\}$}. Here each number
$j$ represents a small piece of interval $J_{j}$. And $j^{\prime}\in f(j)$ if
$f(J_{j})\supseteq J_{j^{\prime}}$. Note that the image of some interval may
be empty, since we ignore the part outside $I_{1}\cup\ldots\cup I_{k}$. And we
only care about the interval determined by $\\{f(a),f(b)\\}$ if
$a,b\in\widetilde{M_{N}}$, although the image $f([a,b])$ may be larger.

######  Example 2.2.

The two figures illustrate how we perturb $f$ locally to obtain $\tilde{f}$
with $\tilde{f}$ still continuous and inducing a covering system close to the
initial one.

Figure 1: the initial $f$ Figure 2: the construction of $\tilde{f}$

It should also be remarked here that the only useful information of $f$ on the
so called “gaps” (see [1]) between two adjacent intervals $I_{i}$ and
$I_{i+1}$ is the behavior of the end points of each gap. In other words, for
the image $f(J_{j})$ of each small subinterval $J_{j}$, we only focus on the
part $f(J_{j})\cap(I_{1}\cup\ldots\cup I_{k})$. This is the reason why we
eliminate the points outside $I_{1}\cup\ldots\cup I_{k}$ in each step. We will
see later that this information is enough for the proof.

To sum up, once we have a mapping $f$ satisfying the conditions in Lemma 2.1,
we can find an $\tilde{f}$ close enough to $f$, which also satisfies the
conditions but can be viewed as a discrete mapping. Such $f$ and $\tilde{f}$
are counterexamples to Theorem 1.2. Therefore, if we argue by contradiction,
we can easily see that Theorem 1.2 is a corollary of the following lemma,
whose proof will be discussed later.

######  Lemma 2.3.

For any mapping $f$: $\\{1,2,\ldots,n\\}$ $\to$ {subsets of
$\\{1,2,\ldots,n\\}\\}$ such that $\bigcup_{i=1}^{n}f(i)=\\{1,2,\ldots,n\\}$,
and for any partition

$I_{1}=\\{1,2,\ldots,i_{1}\\},I_{2}=\\{i_{1}+1,i_{1}+2,\ldots,i_{2}\\},\ldots,I_{k}=\\{i_{k-1}+1,\ldots,n\\},$

there exists $j\in\\{1,2,\ldots,k\\}$ and $r,s\in I_{j}$ ($r=s$ is allowed)
such that

$(convf)^{l}(\\{r,s\\})\supseteq\\{r,s\\},\quad for\ some\quad l\leq k.$

Here, $convf(A)=$ convex hull of $f(A)=\\{\min f(A),\min f(A)+1,\ldots,\max
f(A)\\}$ for any finite set $A\subseteq\mathbb{N}$.

######  Remark 2.4.

We emphasize here again the difference between $f([a,b])$ and $[f(a),f(b)]$.
In general the former is larger. And one may worry that the discrete mapping
$f$ induced from a covering system does not satisfy the corresponding covering
property $\bigcup_{i=1}^{n}f(i)=\\{1,2,\ldots,n\\}$, since in the definition
of $f$, $j^{\prime}\in f(j)$ iff $f(J_{j})\supseteq J_{j^{\prime}}$, where
$f(J_{j})$ is understood in the sense of $[f(a),f(b)]$ rather than $f([a,b])$.
However, this problem can be easily handled by considering the initial
covering system to be minimal. (See [1] for more details.) That is, in
particular, the end points of each $I_{j}$ are mapped to the end points of
$f(I_{j})$. And it’s now easily checked that the perturbation and
discretization preserve the covering property of $f$, since the perturbation
does not change the position of the end points of $f(I_{j})$ essentially.

###### Proof of Theorem 1.2 by lemma 2.3.

Suppose the covering system $(I_{1},\ldots,I_{k};f)$ is a counterexample to
Theorem 1.2. Then as mentioned above, after perturbation, we can assume $f$
satisfies the conditions of lemma 2.3. Therefore the conclusion of lemma 2.3
gives us a subinterval of $I_{j}$ represented by $conv\\{r,s\\}$ whose image
under $f^{l}$ contains itself. Thus there must exist a periodic point of
period $\leq l\leq k$ in $I_{j}$, a contradiction. ∎

##  3 Equivalence of the Two Lemmas

Although lemma 2.3 reduces Theorem 1.2 to a discrete problem, it is not
satisfactory since it involves something inconvenient to deal with, like
convex hull and partition. In the following we will simplify the conditions in
lemma 2.3 and find another description of it which only depends on the own
property of a permutation. And the main goal of this section is to prove the
equivalence of lemma 1.6 and lemma 2.3.

Let $f$ be in lemma 2.3. We can assume further:

(1)$\quad\forall i\neq j$, $f(i)\cap f(j)=\emptyset$.

(2)$\quad\forall i$, $f(i)\neq\emptyset$.

(3)$\quad\forall i$, $f(i)$ contains exactly one element.

(4)$\quad f$ is a cyclic permutation in the symmetric group $S_{n}$, $i.e.$,
$f$ can be written as $(i_{1}i_{2}\ldots i_{n})$.

Indeed, (1) can be realized since we can move out the common part of $f(i)$
and $f(j)$ from one of them without changing the property
$\bigcup_{i=1}^{n}f(i)=\\{1,2,\ldots,n\\}$.

(2) is also satisfied because we can eliminate the number $i$ and restrict the
mapping $f$ to $\\{1,2,\ldots,n\\}-\\{i\\}$ if necessary.

(3) is a consequence of (1), (2) and the condition
$\bigcup_{i=1}^{n}f(i)=\\{1,2,\ldots,n\\}$. Indeed, one can apply the
operations in (1) and (2) repeatedly until a minimal case. This couldn’t be an
endless process because we are dealing with finite sets. And one can prove
that the minimal set cannot be empty because the covering property is
preserved.

For (4), note that $f\in S_{n}$ because of (3). Suppose $f$ is not cyclic.
Then choose an orbit $(i_{1}\ldots i_{m})$ of $f$ ($m<n$) and restrict both
$f$ and the partition $I_{1},\ldots,I_{k}$ to $\\{i_{1},\ldots,i_{m}\\}$.

In conclusion, we obtain:

######  Proposition 3.1.

It is sufficient to consider $f\in S_{n}$ and $f$ being cyclic in lemma 2.3.

Now we turn to the proof of the equivalence of lemma 2.3 and lemma 1.6. (See
also Definition 1.4.)

######  Proposition 3.2.

Lemma 1.6 implies lemma 2.3.

###### Proof.

As mentioned above, we can assume $f\in S_{n}$ being cyclic, without loss of
generality.

Suppose lemma 1.6 is true. Then for any partition

$I_{1}=\\{1,2,\ldots,i_{1}\\},\quad
I_{2}=\\{i_{1}+1,\ldots,i_{2}\\},\quad\ldots,\quad
I_{k}=\\{i_{k-1}+1,...,n\\},$

the $(k-1)$ characteristic numbers
$\\{m_{i_{1}},m_{i_{2}},\ldots,m_{i_{k-1}}\\}$ cannot cover
$\\{m_{1}^{\prime},\ldots,m_{k}^{\prime}\\}$. Therefore, $\exists\,t\neq
i_{1},\ldots,i_{k-1}$, and $l\leq k$ such that $m_{t}=m_{l}^{\prime}\leq k$,
since $m_{1}^{\prime}\leq\ldots\leq m_{k}^{\prime}\leq k$ in the
characteristic sequence. In other words,

$(convf)^{m_{t}}(A_{t})\supseteq A_{t},\quad where\quad
A_{t}=\\{t,t+1\\}\subseteq some\ I_{j}.$

Therefore, we can just choose $r=t,\ s=t+1$ in lemma 2.3.

∎

Recall that in one-dimensional dynamics we often consider a directed graph
associated to a periodic orbit (For more details, see [3] or chapter 1 of
[4]). Namely, if $f$ is a cyclic permutation in Definition 1.4, we can
construct a directed graph $\Gamma_{f}$ with $(n-1)$ vertices
$\\{A_{1},A_{2},\ldots,A_{n-1}\\}$, where $A_{i}=\\{i,i+1\\}$ is defined in
1.4. And there is an edge from $A_{i}$ to $A_{j}$ if and only if
$convf(A_{i})\supseteq A_{j}$.

######  Example 3.3.

Let $f=(136245)\in S_{6}$ as in example 1.5. Then the associated directed
graph $\Gamma_{f}$ is drawn in figure 3.

Figure 3: the directed graph $\Gamma_{f}$

Thus, we see directly from the definition that the following proposition
holds:

######  Proposition 3.4.

For a cyclic $f\in S_{n}$ and its associated directed graph $\Gamma_{f}$, the
characteristic number $m_{i}$ is equal to the minimal length of cycles
starting from $A_{i}$ in $\Gamma_{f}$.

Using directed graphs, we can complete the proof of the equivalence of the two
lemmas.

######  Proposition 3.5.

Lemma 1.6 is equivalent to lemma 2.3.

###### Proof.

Suppose lemma 2.3 is true. For a cyclic $f\in S_{n}$, suppose on the contrary
that there is a $k\leq n-1$ such that $m_{k}^{\prime}\geq k+1$, and $k$ is the
minimal number with this property. Then there are only $(k-1)$ characteristic
numbers $m_{i_{1}},m_{i_{2}},\ldots,m_{i_{k-1}}\leq k$. Without loss of
generality, assume $i_{1}<\ldots<i_{k-1}$. And consider the partition:

$I_{1}=\\{1,2,\ldots,i_{1}\\},\quad
I_{2}=\\{i_{1}+1,\ldots,i_{2}\\},\quad\ldots,\quad
I_{k}=\\{i_{k-1}+1,\ldots,n\\}.$

By lemma 2.3, we can find $j,l\leq k$ and $r,s\in I_{j}$ ($r<s$) such that

$(convf)^{l}(\\{r,s\\})\supseteq\\{r,s\\}.$

Note that $r=s$ cannot happen in this case, since $m_{r}=m_{s}\geq k+1$. Now
if we extend $f$ to be a piecewise linear mapping from the interval $[1,n]$ to
$[1,n]$, then we will obtain $f^{l}([r,s])\supseteq[r,s]$. Therefore, there
exists $x_{0}\in[r,s]$ with $f^{l}(x_{0})=x_{0}$. Note that since $f$ is
cyclic as a permutation in $S_{n}$ and $l\leq k\leq n-1$, $x_{0}$ cannot
belong to $\\{1,2,\ldots,n\\}$. Consequently, $x_{0}\in(t,t+1)$ for some
integer $t\in[r,s-1]$ and it is similar for
$f(x_{0}),f^{2}(x_{0}),\ldots,f^{l-1}(x_{0})$. Since $f$ is piecewise linear,
$x_{0}\in(t,t+1)$, $f(x_{0})\in(t^{\prime},t^{\prime}+1)$ imply
$f([t,t+1])\supseteq[t^{\prime},t^{\prime}+1]$, and it is similar for other
pairs of points. So the orbit
$\\{x_{0},f(x_{0}),\ldots,f^{l-1}(x_{0}),f^{l}(x_{0})\\}$ gives a cycle of
length $l\leq k$ starting from the vertex $A_{t}$ in the associated directed
graph $\Gamma_{f}$, which implies $m_{t}\leq k$. But this $t$ together with
$i_{1},\ldots,i_{k-1}$ gives $k$ characteristic numbers $\leq k$,
contradicting $m_{k}^{\prime}\geq k+1$.

Combined with Proposition 3.2, the proof is completed. ∎

Therefore, we have reduced the initial problem on the existence of periodic
points to a lemma in combinatorics on the properties of cyclic permutations.
In the next section, we will prove the lemma and that will complete the proof
of theorem 1.2.

We end this section with some examples of cyclic permutations whose
characteristic sequences are known.

######  Example 3.6.

(1) Let $f\in S_{n}$ be $(1\to 2\to\ldots\to n\to 1)$. And more generally,
$f(i)\equiv i+m\pmod{n}$, where $(m,n)=1$. Then the characteristic sequence of
$f$ is $1\leq 2\leq\ldots\leq n-1$.

(2) Let $f\in S_{2n+1}$ be of Stefan type (see [2] or [5] for more details),
that is,

$1\to(n+1)\to(n+2)\to n\to(n+3)\to(n-1)\to\ldots\to 2n\to 2\to(2n+1)\to 1.$

Then the characteristic sequence of $f$ is

$1\leq 2\leq 2\leq 4\leq 4\leq\ldots\leq 2n-2\leq 2n-2\leq 2n.$

(3) In [6], the author gives all the directed graphs associated to cyclic
permutations in $S_{5}$.

##  4 Proof of the Lemma in Combinatorics

We finally prove lemma 1.6 in this section. We first recall some definitions
and notations from one-dimensional dynamics and linear algebra.

######  Definition 4.1.

Let $f\in S_{n}$ be a cyclic permutation and $\Gamma_{f}$ be its associated
directed graph. (See the discussion before propositon 3.4.) We can define
$T_{f}$ to be the $(n-1)\times(n-1)$ adjacency matrix of $f$ and $\Gamma_{f}$.
That is, $T_{ij}=1$, if $convf(A_{j})\supseteq A_{i}$, or equivalently, if
there is an edge from vertex $A_{j}$ to vertex $A_{i}$ in $\Gamma_{f}$.
Otherwise, $T_{ij}=0$.

######  Example 4.2.

Let $f=(136245)\in S_{6}$ be the permutation in example 1.5 and example 3.3.
Then the adjacency matrix $T_{f}$ is

$\begin{bmatrix}&0&0&0&1&1&\\\ &0&0&0&1&0&\\\ &1&0&0&1&0&\\\ &0&1&0&1&0&\\\
&0&1&1&0&0&\end{bmatrix}$

We denote the field $\\{0,1\\}$ with exactly two elements by $\mathbb{F}_{2}$.
And we say $A\equiv B\pmod{2}$ for integer valued matrices $A$ and $B$, when
$A=B$ as matrices in $M(\mathbb{F}_{2})$.

######  Proposition 4.3.

For any cyclic permutation $f\in S_{n}$ and $l\in\mathbb{N}_{+}$, it holds
that $T_{f}^{l}\equiv T_{f^{l}}\pmod{2}$.

A proof of this proposition can be found in [4], Chapter 1, Propositon 20. And
for readers’ convenience, we give a sketch of proof here.

###### Sketch of proof.

Given $f=(i_{1}i_{2}\ldots i_{n})\in S_{n}$ cyclic, we first extend $f$ to be
a continuous piecewise linear mapping from the closed interval $[1,n]$ to
itself. And recall we define $A_{i}=\\{i,i+1\\}$. Later on we will also regard
$A_{i}$ as the closed interval $[i,i+1]$.

Now by the definition of $T_{f}$ and the continuity of $f$, $(T_{f})_{ij}=1$
iff $f(A_{j})\supseteq A_{i}$. Consider the interval $A_{i}=[i,i+1]$ and its
image $f^{l}(A_{i})$. In general, we cannot expect
$f^{l}(A_{i})=[f^{l}(i),f^{l}(i+1)]$ to hold, where $[a,b]$ denotes the closed
interval whose end points are $a$ and $b$. We can only say that
$f^{l}(A_{i})\supseteq[f^{l}(i),f^{l}(i+1)]$ for continuous $f$. However, if
we count the multiplicity of each point in the image $f^{l}(A_{i})$, we will
find that $f^{l}(A_{i})=[f^{l}(i),f^{l}(i+1)]$ actually holds in the sense of
mod 2. Indeed, $f^{l}(A_{i})$ can be viewed as a continuous curve in
$\mathbb{R}$ starting from the point $f^{l}(i)$ and ending at $f^{l}(i+1)$.
Therefore, every point $p\in f^{l}(A_{i})$ is counted an even number of times
in this curve, unless $p\in[f^{l}(i),f^{l}(i+1)]$.

Finally recall the definition of $T_{f}$ and $T_{f^{l}}$, and we get the
conclusion of the proposition in the sense of mod 2. ∎

######  Remark 4.4.

If the readers are familiar with representation theory of the symmetric group
$S_{n}$, then they may find that $T_{f}$ defined above is just the matrix of
the tautological representation of $f$ mod 2.

######  Corollary 4.5.

For cyclic $f\in S_{n}$, we have $T_{f}^{n}\equiv I\pmod{2}$, where
$I=I_{n-1}$ is the unit matrix.

######  Theorem 4.6.

For cyclic $f\in S_{n}$, the characteristic polynomial of $T_{f}$, viewed as
the determinant of a matrix in $M_{n-1}(\mathbb{F}_{2})$, is exactly:

$\det(\lambda I-T_{f})=1+\lambda+\lambda^{2}+\ldots+\lambda^{n-1}\pmod{2}.$

We need the following lemma:

######  Lemma 4.7.

There exists a vector $\alpha\in\mathbb{F}_{2}^{n-1}$ such that
$\alpha,T_{f}\alpha,\ldots,T_{f}^{n-2}\alpha$ are linearly independent over
the field $\mathbb{F}_{2}$.

###### Proof.

We claim that if $f\in S_{n}$ is written as $(i_{1}i_{2}\ldots i_{n})$, then
the vector
$\alpha=(0,\ldots,0,1,\ldots,1,0,\ldots,0)^{T}=\sum_{j=i_{1}}^{i_{2}-1}e_{j}$
(or $\sum_{j=i_{2}}^{i_{1}-1}e_{j}$) satisfies the desired property, where
$e_{j}\in\mathbb{F}_{2}^{n-1}$ is the unit vector whose $j$-th component is
$1$.

We prove the claim by induction on $n$. The case $n=2$ is trivial. We assume
the statement holds for all natural numbers $<n$, and we will prove it for
$n$.

Suppose

$\mu_{1}\alpha+\mu_{2}T_{f}\alpha+\ldots+\mu_{n-1}T_{f}^{n-2}\alpha=0.$

By the definition of $\alpha$, $f=(i_{1}i_{2}\ldots i_{n})\in S_{n}$, as well
as the argument in the proof of proposition 4.3, we can see that

$T_{f}^{m}\alpha=\sum_{j=i_{m+1}}^{{i_{m+2}-1}}e_{j},\quad
or\sum_{j=i_{m+2}}^{{i_{m+1}-1}}e_{j},\quad\forall m\leq n-2.$

In other words, if we view each vector $e_{j}$ as the closed interval
$[j,j+1]$ it represents, then we find that

$\alpha=[i_{1},i_{2}],\quad
T_{f}\alpha=[i_{2},i_{3}],\quad\ldots\quad,T_{f}^{n-2}\alpha=[i_{n-1},i_{n}].$

Now if $i_{1}=1$, take the inner product with $e_{1}$, and we obtain:

$0=\left(\mu_{1}\alpha+\mu_{2}T_{f}\alpha+\ldots+\mu_{n-1}T_{f}^{n-2}\alpha,\>e_{1}\right)=\mu_{1},$

because $i_{2},\ldots,i_{n}\geq 2$ and hence $(T_{f}^{m}\alpha,e_{1})=0$ for
$1\leq m\leq n-2$. Similarly we can obtain $\mu_{1}=0$ when $i_{1}=n$.

If $2\leq i_{1}\leq n-1$, then since $i_{1}$ does not appear as the end points
of $T_{f}^{m}\alpha$, $[i_{1}-1,i_{1}]$ and $[i_{1},i_{1}+1]\subseteq
or\not\subseteq T_{f}^{m}\alpha$ at the same time, where $m\geq 1$. Or
equivalently,

$(T_{f}^{m}\alpha,e_{i_{1}-1})=(T_{f}^{m}\alpha,e_{i_{1}}),\quad 1\leq m\leq
n-2.$

And then if we take the inner product with $(e_{i_{1}-1}+e_{i_{1}})$, we
obtain:

$0=\left(\mu_{1}\alpha+\mu_{2}T_{f}\alpha+\ldots+\mu_{n-1}T_{f}^{n-2}\alpha,\>(e_{i_{1}-1}+e_{i_{1}})\right)=\mu_{1}\pmod{2},$

Anyway, we find that $\mu_{1}=0$ and consequently,

$\mu_{2}T_{f}\alpha+\ldots+\mu_{n-1}T_{f}^{n-2}\alpha=0.$

Now if we put $g=(i_{2}i_{3}\ldots i_{n})\in S_{n-1}$ and $\beta=T_{f}\alpha$
with the $i_{1}$-th component dropped, we can see that
$T_{f}^{m}\alpha=T_{g}^{m-1}\beta$, regardless of the $i_{1}$-th component of
$T_{f}^{m}\alpha$. This is easily seen to be true since one can find
$T_{f}^{m}\alpha=T_{g}^{m-1}\beta=[i_{m+1},i_{m+2}]$ as intervals. And the
following holds for $\beta$ and $T_{g}$:

$\mu_{2}\beta+\mu_{3}T_{g}\beta+\ldots+\mu_{n-1}T_{g}^{n-3}\beta=0.$

By induction hypothesis we conclude that $\mu_{2}=\ldots=\mu_{n-1}=0$.
Therefore, we have proved that the claim also holds for $n$. This completes
the proof of the lemma. ∎

######  Corollary 4.8.

The minimal polynomial $g(\lambda)$ of $T_{f}$ has degree at least $n-1$, and
therefore equals the characteristic polynomial.

###### Proof.

Suppose $\deg g(\lambda)\leq n-2$, then we have $g(T_{f})\alpha=0$, which
contradicts the lemma above. And the second statement follows by Cayley-
Hamilton’s theorem. (Note that $T_{f}$ is an $(n-1)\times(n-1)$ matrix.) ∎

With these results, we can compute the characteristic polynomial of $T_{f}$.

###### Proof of Theorem 4.6.

It follows from corollary 4.5 and 4.8 that

$\det(\lambda
I-T_{f})=g(\lambda)\mid(\lambda^{n}-1)=(1+\lambda)(1+\lambda+\lambda^{2}+\ldots+\lambda^{n-1})\pmod{2}.$

Moreover, since the only degree-one irreducible polynomials are $\lambda$ and
$\lambda+1$ in $\mathbb{F}_{2}[\lambda]$, the right hand side can be further
decomposed as

$1+\lambda+\lambda^{2}+\ldots+\lambda^{n-1}=(1+\lambda)^{m}h(\lambda),$

where $m\geq 0$, and $h(\lambda)$ is a product of several irreducible
polynomials of degree $\geq 2$. Hence, by comparing the degree we conclude
that

$\det(\lambda I-T_{f})=1+\lambda+\lambda^{2}+\ldots+\lambda^{n-1}\pmod{2}.$

∎

###### Proof of lemma 1.6.

We show that if the coefficient of $\lambda^{n-1-i}$ in $\det(\lambda
I-T_{f})$ is nonzero, then $m_{i}^{\prime}\leq i$ holds for the characteristic
sequence in lemma 1.6.

Let us consider how the coefficients in $\det(\lambda I-T_{f})$ are computed.
It is then easily seen that the coefficient of $\lambda^{n-1-i}$ is nonzero
implies the existence of an $i\times i$ principle matrix $P_{i}$ of $T_{f}$
whose determinant is nonzero. It then follows that there exists at least one
diagonal of $P_{i}$ whose elements are all equal to 1. Now it is easily
checked that this diagonal give rise to several cycles of length $\leq i$ in
the associated directed graph $\Gamma_{f}$. And the vertices of these cycles
correspond to the subscripts of the columns of $P_{i}$. Thus there exist at
least $i$ vertices in $\Gamma_{f}$, from whom the minimal length of cycles
starting are all $\leq i$. By proposition 3.4, this means that at least $i$ of
the characteristic numbers $\leq i$. So $m_{i}^{\prime}\leq i$. ∎

## Acknowledgement

I would like to thank Prof. S. A. Bogatyi for introducing the problem to me.
And I thank my supervisor, Prof. Tian Gang, for his encouragement as well as
helpful suggestions. I’m also grateful to Dr. Ye Yanan and Dr. Zhao Yikai for
writing computer programs to verify some claims.

## References

  * [1] S. A. Bogatyi and E. T. Shavgulidze.  Periodic points of a map of a system of intervals.  Mathematical Notes of the Academy of Sciences of the Ussr, 43(3):210–219, 1988.
  * [2] A. N. Sharkovskii.  Coexistence of cycles of a continuous map of the line into itself.  International Journal of Bifurcation and Chaos, 5(5):1263–1273, 1995.
  * [3] Uhland Burkart.  Interval mapping graphs and periodic points of continuous function.  Journal of Combinatorial Theory, Series B, 32(1):57–68, 1982.
  * [4] L. S. Block and W. A. Coppel.  Dynamics in One Dimension.  Springer, 1992.
  * [5] P. Štefan.  A theorem of Šarkovskii on the existence of periodic orbits of continuous endomorphisms of the real line.  Communications in Mathematical Physics, 54(3):237–248, 1977.
  * [6] Philip D. Straffin.  Periodic points of continuous functions.  Mathematics Magazine, 51(2):99–105, 1978.


# Penalization Framework For Autonomous Agents Using Answer Set Programming

Vineel S. K. Tummala Computer Science and Software Engineering
Miami University
Oxford, USA<EMAIL_ADDRESS>
###### Abstract

This paper presents a framework for enforcing penalties on intelligent agents
that do not comply with authorization or obligation policies in a changing
environment. A framework is proposed to represent and reason about penalties
in plans, and an algorithm is proposed to penalize an agent’s actions based on
their level of compliance with respect to authorization and obligation
policies. Being aware of penalties an agent can choose a plan with a minimal
total penalty, unless there is an emergency goal like saving a human’s life.
The paper concludes that this framework can reprimand insubordinate agents.

##  1 Introduction and Motivation

A framework will be presented that can enforce penalties on intelligent agents
in a changing environment if autonomous agents don’t obey authorization or
obligation policies. Policies for an agent A acting in a changing
domain/environment T are encoded as a set of conditions that describes whether
an agent’s actions are permitted or not, and whether the agent is obligated to
perform an action or not perform it. In some cases, an autonomous agent can
choose to perform an unauthorized action. In this case, the agent is forced to
pay a penalty, where it can be reprimanded for its actions or lose its job for
insubordination [2]. To make this possible, an architecture will be created to
represent and reason about penalties in plans.

As autonomous agents continue to develop, it is necessary that proper policy
representation and comprehension exist. It is essential to monitor the issues
within the environment to ensure that agents act appropriately. Autonomous
agents are intended to perform certain actions without any instructions or
interference from a controller (pilot or driver) of the agent. The activities
of an autonomous agent are often modeled after human behavior so that the
agent can perform tasks that humans would. In order to do this, human behavior
needs to be accurately represented. This can be successfully achieved by a
logical approach, using declarative programming languages. Declarative
programming languages are able to define human behavior correctly and in an
understandable way. One such declarative programming language is Answer Set
Programming [3],

##  2 Background and overview of the existing literature

In this section, background work related to the penalization framework for
autonomous agents will be described. I assume that the reader is familiar with
Answer Set Programming (ASP) [9, 8], a declarative programming language with
roots in Logic Programming and Nonmonotonic reasoning [5], and the ASP solver
Clingo111https://potassco.org/Clingo/. Full details about Clingo can be found
in the papers by Calimeri et al. [4] and Gebser et al. [6]. I also assume
familiarity of the reader with autonomous intelligent agents.

###  2.1 Transition Systems

In order for intelligent agents to be functional and autonomous, they require
a proper description of the changing environment in which they act. Transition
systems are a tool that is used to describe these domains. Transition systems
are fundamentally directed graphs that represent a changing domain, in which
the nodes represent the state of the domain, and actions that might occur in
the domain are represented by arcs [2]. As a result, the domain is altered
from one state to another. Transition diagrams can become huge if many fluents
are being tracked, thus they are not used in practice. They can be represented
in a more concise way by an action language 222See https://www.diva-
portal.org/smash/get/diva2:1716299/FULLTEXT01.pdf which is a high-level
declarative language.

###  2.2 Policies

The proposed research will be focusing on agents which are aware of policies.
Policies are sets of rules to follow in a given domain or environment and are
also described using declarative programming languages. Given a policy, P,
with respect to a given environment T, all actions performed in the said
environment can be judged based on whether or not they follow the rules
defined by the policy. In the case of an intelligent agent, it is important
for it to be aware of all the policies in advance in order to comply with all
the necessities when coming up with plans for action. The following section
will define compliance to policy, look into both authorization and obligation
policies.

####  2.2.1 Authorization

Authorization policies are policies in which an agent is either permitted
(authorized) or not permitted (not authorized) to perform an action. Gelfond
and Lobo [10] define Authorization Policy Language (APL) to describe
authorization policies in a dynamic system $\Sigma=\langle A,T\rangle$, with
an agent A and a transition diagram/environment T. This language is
implemented through Answer Set Programming (ASP). The signature of APL
includes a predicate for authorization policies permitted(e) where e is an
elementary action of A. [10].

####  2.2.2 Obligation

An obligation policy is one in which an agent is obligated to carry out an
action or not to carry it out. AOPL is a policy language to describe systems
with an agent A and a transition diagram T over signature $\Sigma$, similar to
APL [10]. Known as Authorization and Obligation Policy Language, Gelfond and
Lobo [10] designed this language, to extend APL with obligation policies by
adding a new symbol obl(h) where h is an elementary action of A or negation of
any such action [10]. This language is implemented through ASP.

###  2.3 Compliance

Compliance denotes whether an action or set of actions should be taken or not
in accordance with a given policy P. A set of actions is defined as strongly
compliant, weakly compliant, or non-compliant. Strongly compliant means that
no rules were broken and it allows/supports their execution. If there is no
sufficient information then it is called weakly compliant, and if the actions
have broken one or more policies then it is called as non-compliant.

####  2.3.1 Authorization Compliance

Compliance in relation to authorization policies, as defined by APL($\Sigma$),
can be divided into strongly compliant, weakly compliant, or not compliant
[10].

####  2.3.2 Obligation Compliance

For obligation policies defined through AOPL($\Sigma$), events are classified
into compliant or non-compliant [10]. Unlike authorization policies, there are
no weakly compliant events with respect to obligations.

###  2.4 Planning

A plan is a sequence of actions taken by an agent in order to achieve a given
goal [7]. Answer Set Planning [11] refers to the use of Answer Set Programming
to solve different types of planning problems by adding a planning module to
an ASP description of a changing environment. Answer sets of the resulting
program correspond to possible plans.

##  3 Goal of the research

The goal of the proposed research is to create a penalization framework for
autonomous agents using ASP where autonomous agents are penalized if they do
any job/task that they are not intended to do according to the policy.

###  3.1 Constructing the Framework

In this section, we present our ideas for constructing a penalization
framework for autonomous agents.

####  3.1.1 Encoding the penalties

In order for these penalties to be imposed on the agents we will create a
statement to penalize the agents. we will choose a specific scale to impose
penalty points for agents; as of now the scale is 1-3, in the actual framework
we will explore different possibilities.

We keep track of the values as low, medium, and high to help the agent
calculate the value of the penalty while choosing the plans.

####  3.1.2 Calculating the total penalty

We calculate the total penalty, in the end, using the aggregate sum in
Clingo333https://potassco.org/Clingo/run/ (solver for ASP). Aggregates are
functions that combine the values of a set of terms to produce a single value.
Using this function we add up all the penalties given to an agent in an
environment and we can evaluate an agent based on these penalties.

##  4 Current status of the research

Collected all background and related work, and created two domains to test the
penalization framework.

###  4.1 Collecting policies and scenarios

When we speak about penalizing autonomous agents, we need to create domains
and scenarios where we evaluate autonomous agents for their actions and
penalize them. Also, to achieve this we need to specify authorization and
obligation policies for the domain beforehand. Conflicts may arise when
Authorization and obligation policies interact or come across each other.
Therefore we need to specify authorization and obligation policies precisely.
First definitions and rules of both the authorization and obligation policies
developed by Gelfond and Lobo [10] must be understood. After fully
understanding the rules that exist, different scenarios can be tested.
Scenarios will be tested to see what an agent selects if it has two non-
compliant plans, and what plan it chooses. Some of the scenarios are:

####  4.1.1 Domain 1: Drone Delivery

Goal: Its goal is to deliver a package to a customer’s doorstep, located in a
suburban area with many houses.

Policy Rules: Consider an autonomous agent in this scenario as a delivery
drone with the following rules to ensure safe and efficient deliveries:

  * •

Always fly at a safe height to avoid obstacles and people on the ground.

  * •

only land on designated landing pads or open spaces to avoid collisions and
ensure safe deliveries.

####  4.1.2 Domain 2: Self-Driving Car

The autonomous agent in this scenario is a self-driving car, programmed with a
set of rules to ensure safe and efficient transportation.

Goal: Its goal is to transport a passenger from their current location to a
specified destination, which involves driving through a busy city street with
heavy traffic.

Policy Rules: Consider an autonomous agent in this scenario as a self-driving
car with the following rules to ensure safe and efficient deliveries:

  * •

Always obey traffic laws and signals, including speed limits, stop signs, and
traffic lights.

  * •

Prioritize the safety of passengers and other drivers on the road.

##  5 Open issues and expected achievements

Open Issues

  * •

We can’t create a penalty for each and every possible action, so should we set
a default value if the action is not encoded?

  * •

Setting a maximum penalty limit after which the agent would be automatically
disabled from its operations for not following the compliance. This would
ensure the agents that they do not perform any operations that are not
compliant.

The expected achievement is to create a framework where autonomous agent
chooses plans with fewer penalties and also according to the strength of the
goal.

## References

  * [1]
  * [2] Justin Blount (2013): _An architecture for intentional agents_.  Ph.D. thesis, 10.4204/EPTCS.345.23.
  * [3] Gerhard Brewka, Thomas Eiter & Miroslaw Truszczynski (2011): _Answer set programming at a glance_.  Commun. ACM 54(12), pp. 92–103, 10.1145/2043174.2043195.
  * [4] Francesco Calimeri, Wolfgang Faber, Martin Gebser, Giovambattista Ianni, Roland Kaminski, Thomas Krennwallner, Nicola Leone, Marco Maratea, Francesco Ricca & Torsten Schaub (2020): _ASP-Core-2 input language format_.  Theory and Practice of Logic Programming 20(2), pp. 294–309, 10.1017/S1471068419000450.
  * [5] Thomas Eiter, Giovambattista Ianni & Thomas Krennwallner (2009): _Answer Set Programming: A Primer_.  In Sergio Tessaris, Enrico Franconi, Thomas Eiter, Claudio Gutierrez, Siegfried Handschuh, Marie-Christine Rousset & Renate A. Schmidt, editors: Reasoning Web. Semantic Technologies for Information Systems, 5th International Summer School 2009, Brixen-Bressanone, Italy, August 30 - September 4, 2009, Tutorial Lectures, Lecture Notes in Computer Science 5689, Springer, pp. 40–110, 10.1007/978-3-642-03754-2_2.
  * [6] Martin Gebser, Benjamin Kaufmann, Roland Kaminski, Max Ostrowski, Torsten Schaub & Marius Schneider (2011): _Potassco: The Potsdam Answer Set Solving Collection_.  AI Commun. 24(2), pp. 107–124, 10.3233/AIC-2011-0491.
  * [7] Michael Gelfond & Yulia Kahl (2014): _Knowledge representation, reasoning, and the design of intelligent agents: The answer-set programming approach_.  Cambridge University Press, 10.1017/CBO9781139342124.
  * [8] Michael Gelfond & Vladimir Lifschitz (1988): _The Stable Model Semantics for Logic Programming_.  In Robert A. Kowalski & Kenneth A. Bowen, editors: Logic Programming, Proceedings of the Fifth International Conference and Symposium, Seattle, Washington, USA, August 15-19, 1988 (2 Volumes), MIT Press, pp. 1070–1080, 10.2307/2275201.
  * [9] Michael Gelfond & Vladimir Lifschitz (1990): _Logic Programs with Classical Negation_.  In David H. D. Warren & Péter Szeredi, editors: Logic Programming, Proceedings of the Seventh International Conference, Jerusalem, Israel, June 18-20, 1990, MIT Press, pp. 579–597, 10.1007/BF03037169.
  * [10] Michael Gelfond & Jorge Lobo (2008): _Authorization and Obligation Policies in Dynamic Systems_.  In Maria Garcia de la Banda & Enrico Pontelli, editors: Logic Programming, 24th International Conference, ICLP 2008, Udine, Italy, December 9-13 2008, Proceedings, Lecture Notes in Computer Science 5366, Springer, pp. 22–36, 10.1007/978-3-540-89982-2_7.
  * [11] Vladimir Lifschitz (1999): _Answer Set Planning (Abstract)_.  In Michael Gelfond, Nicola Leone & Gerald Pfeifer, editors: Logic Programming and Nonmonotonic Reasoning, 5th International Conference, LPNMR’99, El Paso, Texas, USA, December 2-4, 1999, Proceedings, Lecture Notes in Computer Science 1730, Springer, pp. 373–374, 10.1007/3-540-46767-X_28.