# Ground states of one-dimensional dipolar lattice bosons at unit filling

Mateusz Ła̧cki  Institute of Theoretical Physics, Jagiellonian University in
Krakow, ul. Lojasiewicza 11, 30-348 Kraków, Poland  Henning Korbmacher
Institut für Theoretische Physik, Leibniz Universität Hannover, Germany  G. A.
Domínguez-Castro  Institut für Theoretische Physik, Leibniz Universität
Hannover, Germany  Jakub Zakrzewski<EMAIL_ADDRESS>Institute of
Theoretical Physics, Jagiellonian University in Krakow, ul. Lojasiewicza 11,
30-348 Kraków, Poland  Mark Kac Complex Systems Research Center, Jagiellonian
University in Krakow, Łojasiewicza 11, 30-348 Kraków, Poland  Luis Santos
Institut für Theoretische Physik, Leibniz Universität Hannover, Germany

(August 28, 2024)

###### Abstract

Recent experiments on ultracold dipoles in optical lattices open exciting
possibilities for the quantum simulation of extended Hubbard models. When
considered in one dimension, these models present at unit filling a
particularly interesting ground-state physics, including a symmetry-protected
topological phase known as Haldane insulator. We show that the tail of the
dipolar interaction beyond nearest-neighbors, which may be tailored by means
of the transversal confinement, does not only modify quantitatively the
Haldane insulator regime and lead to density waves of larger periods, but
results as well in unexpected insulating phases. These insulating phases may
be topological or topologically trivial, and are characterized by peculiar
correlations of the site occupations. These phases may be realized and
observed in state-of-the-art experiments.

Ultra cold quantum systems in optical lattices and tweezer arrays offer
extraordinary possibilities for the quantum simulation of many-body lattice
models [1, 2, 3]. Whereas these systems are typically characterized by on-site
interactions, with the exception of relatively weak super-exchange terms [4],
recent experiments on dipolar systems, including magnetic atoms [5], polar
molecules [6], and Rydberg gases [7], open the possibility to simulate lattice
models with significant inter-site interactions. Extended Hubbard models [8]
have been already realized using magnetic atoms [9, 10], including the very
recent observation of density-wave patterns [10].

One-dimensional extended Bose-Hubbard models (EBHMs) are particularly
interesting at unit filling, since they present in addition to the superfluid,
Mott insulator and density-wave phases, the so-called Haldane insulator [11,
12, 13], a symmetry protected topological phase, characterized by a string
order, and a doubly-degenerate entanglement spectrum [14]. This phase is
directly linked to the Haldane phase of spin-$1$ chains [15, 16], since for
strong-enough on-site interactions, EBHMs may be mapped to spin-$1$ models
[11].

Although major features of the physics of polar lattice gases may be
understood using models with only nearest-neighbor interactions, for
sufficiently large dipole moments, the tail of the dipolar interactions beyond
nearest neighbors, which is typically assumed as decaying as $1/r^{3}$, with
$r$ the inter-site distance, may become relevant [11, 17, 18]. The dipolar
tail leads to quantitative modifications of the Haldane insulator parameter
region, but it does not compromise its existence [11]. In addition, it is
expected that strong-enough interactions beyond nearest neighbors should lead
to density waves with longer integer spatial periods.

Figure 1: Ground-state phase diagrams as a function of the on-site
interactions $U/t$ and nearest-neighbor interaction $V/t$, for (a) nearest-
neighbor model, (b) $1/r^{3}$ dipolar tail, and (c) dipolar tail for
$\beta_{eff}=1$. In panel (c), dotted black lines indicate the cuts evaluated
in detail in Fig. 2, and the grey area is the region in which our iDMRG
results do not provide accurate results due to the unit cell and the maximal
occupation per site considered. In all panels, dotted yellow boundaries
indicate approximate HI-SF and TTI-SF boundaries which could not be fully
established in our iDMRG numerics.

In this Letter, we show that, surprisingly, the dipolar tail results as well
in the appearance of unexpected insulating phases. For the usually considered
$1/r^{3}$ dipolar tail, we find at low on-site interactions a topologically
trivial spatially disordered insulator (TTI). Moreover, by properly choosing
the transversal confinement it is possible to taylor a milder decay of the
dipolar tail [19, 20, 21], which results not only in an enhanced TTI region,
but also in an additional topological insulator (TI) phase, characterized by a
doubly-degenerate entanglement spectrum. This phase resembles the Haldane
insulator, but it cannot be trivially mapped to an integer spin chain. We show
that the TTI and TI phases present peculiar correlations of the site
occupations that we characterize using generalized string correlations, which
may be measured using quantum gas microscope techniques [22]. We characterize
the corresponding phase transitions. In particular, the TTI (TI) phases
undergo, for large-enough dipolar strength, a second-order transition
belonging to the 3-state (4-state) Potts universality class into a density
wave with a period of 3 (4) sites. These phases may be realized and observed
in state-of-the-art experiments.

## Model.–

We consider dipolar bosons of mass $m$ in a 1D optical lattice
$V_{0}\sin^{2}(\pi z/a)$, where $V_{0}$ is the lattice depth and $a$ is the
lattice spacing, of length $L$, confined transversally by an isotropic
harmonic potential $\frac{1}{2}m\omega_{\perp}^{2}(x^{2}+y^{2})$, where
$\omega_{\perp}$ is the trap frequency. The system is described by an EBHM

$\displaystyle\hat{H}$ $\displaystyle=$
$\displaystyle-t\sum_{i}\left(\hat{b}^{\dagger}_{i+1}\hat{b}_{i}+\mathrm{H.c.}\right)$
(1) $\displaystyle+$
$\displaystyle\frac{U}{2}\sum_{i}\hat{n}_{i}\left(\hat{n}_{i}\\!-1\right)+\sum_{i}\sum_{j>0}V_{j}\hat{n}_{i}\hat{n}_{i+j},$

where $t$ is the (nearest-neighbor) hopping amplitude, $\hat{b}^{\dagger}_{i}$
($\hat{b}_{i}$) is the creation (annihilation) operator at site $i$,
$\hat{n}_{i}=\hat{b}^{\dagger}_{i}\hat{b}_{i}$ the corresponding number
operator, and $U$ characterizes the on-site interactions. The dipole-induced
inter-site interactions are given by $V_{j}=VG_{j}(B)$ [20], where $V$ is the
interaction strength between nearest-neighboring sites, and the decay of the
dipolar tail is given by $G_{j}(B)=f(\sqrt{B}j)/f(\sqrt{B})$ with
$f(\xi)=2\xi-\sqrt{2\pi}(1+\xi^{2})e^{\xi^{2}/2}\mathrm{erfc}(\xi/\sqrt{2})$,
where $B=\frac{\pi^{2}\zeta}{2}(1-\frac{\zeta}{2\sqrt{s}})^{-1}$ with
$\zeta=\hbar\omega_{\perp}/E_{R}$, $s=V_{0}/E_{R}$, and
$E_{R}=\frac{\pi^{2}\hbar^{2}}{2ma^{2}}$ the recoil energy. Although the
dipolar tail eventually decays for large $j$ as $1/j^{3}$, at short distances
it may significantly depart from that dependence due to the transversal
confinement. This departure is uniquely characterized by the exponent
$\beta_{\text{eff}}$, with $V_{2}/V=1/2^{\beta_{\text{eff}}}$. The case
$\beta_{\text{eff}}=3$ corresponds to the usually assumed $V_{j}=V/j^{3}$ at
all distances. With lower $\beta_{\text{eff}}$, $V_{j}$ may be significantly
enhanced, modifying the ground-state properties, as discussed below.

In the following, we evaluate the ground state at unit filling using the
infinite density-matrix renormalization group (iDMRG) technique, with bond
dimensions up to $\chi=1200$, and a unit cell of $12$ sites, truncating the
inter-site interactions $V_{j}$ at $20$ sites. Since we are interested in
regimes of low $U/t$ values, we consider in our numerical simulations up to
$5$ particles per site (larger occupations do not modify our conclusions). We
assume that the lattice is deep-enough, such that we can neglect the effect of
density-assisted hopping [23, 8, 24].

## Nearest-neighbor model.–

For the case of nearest-neighbor interactions, $V_{j}=V\delta_{j,1}$ (Fig.
1(a)), the ground-state phase diagram splits into four phases [12] (we do not
consider the regime of low $U/t$ and large $V/t$, characterized by phase
separation [25, 26]): a superfluid (SF) phase at low $U/t$ and $V/t$,
characterized by power-law decaying single-particle correlations
$C_{\text{SP}}(i,j)=\langle\hat{b}^{\dagger}_{i}\hat{b}_{j}\rangle$, and three
insulating phases (with exponentially decaying $C_{\text{SP}}$): Mott
insulator (MI), density wave with a period of two sites (2DW), and Haldane
insulator (HI). These insulators relate, respectively, with the large-$D$,
Néel, and Haldane phases of spin-$1$ chains with single-ion anisotropy [27].
This is because at large-enough $U/t$ only site occupations $0$, $1$, and $2$
play a significant role, and hence the EBHM maps into a spin-$1$ model [11].

The MI displays finite parity order

$\mathcal{O}_{P}=\lim_{|i-j|\rightarrow\infty}\langle
e^{i\pi\sum_{i<k<j}\delta\hat{n}_{k}}\rangle.$ (2)

with $\delta\hat{n}_{i}=\hat{n}_{i}-1$, and vanishing string order [15]

$\mathcal{O}_{S}=\lim_{|i-j|\rightarrow\infty}\langle\delta\hat{n}_{i}e^{i\pi\sum_{i<k<j}\delta\hat{n}_{k}}\delta\hat{n}_{j}\rangle.$
(3)

The 2DW phase, occurring at sufficiently large $V/t$, shows a staggered
density-density correlation revealed by a peak at momentum $k=\pi$ in its
structure factor

$S(k)=\frac{1}{L^{2}}\sum_{i,j}e^{ik(i-j)}\langle\hat{n}_{i}\hat{n}_{j}\rangle,$
(4)

with $L$ the number of sites. Finally, the HI phase, occurring at intermediate
$U/t$ ad $V/t$ values, presents a finite ${\cal O}_{S}$ and vanishing ${\cal
O}_{P}$. The HI is further characterized by its entanglement spectrum
$\\{\lambda_{i}\\}$, i.e. the eigenvalues of the reduced density matrix
$\rho_{A}=\mathrm{Tr}_{B}\rho$, obtained from the overall density matrix
$\rho$ when partitioning the system into two subsystems $A$ and $B$. The HI is
a symmetry-protected topological phase with a double-degenerate entanglement
spectrum [14], i.e. $P_{\Lambda}=0$, with

$P_{\Lambda}=\sqrt{\sum_{i}\left(\lambda_{2i}-\lambda_{2i+1}\right)^{2}}.$ (5)

Figure 2: (a) Degeneracy of the entanglement spectrum, $P_{\Lambda}$, as a
function of $V/t$ for $\beta_{\textrm{eff}}=1$ and $U/t=3$ (dotted horizontal
line in Fig. 1 (c). (b) The same $P_{\Lambda}$ shown as a function of $U/t$
for $V/t=2.75$ (dotted vertical line in Fig. 1(c)). (c) String correlations
$R_{E}$ and $R_{O}$ (see text) for the parameter range of panel (a). (d) Same
as (c) but for parameters of panel (b).

## Phase diagram of a polar lattice gas.–

The dipolar tail modifies quantitatively the extension of the HI parameter
region (panels (b) and (c) of Fig. 1), but does not compromise its existence
[11]. At large $V/t$, additional DW phases appear, with period $\ell=3$ (3DW),
$4$ (4DW), and so on, characterized by peaks at $k=2\pi/\ell$ in the structure
factor $S(k)$. The $\ell$DW and $(\ell+1)$DW phases are separated from each
other by a first-order phase transition at
$(U/V)_{\ell}=2\sum_{s>0}\left[nG_{s\ell}-(\ell+1)G_{s(\ell+1)}\right]$.
Interestingly, for low $U/t$ values, the dipolar tail results in additional
phases which we term TTI (topologically-trivial insulator) and TI (topological
insulator), which to the best of our knowledge have remained up to now
unnoticed. The TTI phase is apparent even for the case of an unmodified
$1/j^{3}$ dipolar tail (Fig. 1 (b)). Decreasing $\beta_{\textrm{eff}}$
enhances the TTI region and reveals the TI phase, see Fig. 1 (c). We discuss
below the nature of these unexpected phases.

## TTI phase.–

The TTI phase is an insulator (with exponentially decaying $C_{SP}$)
sandwiched between the 3DW and the HI phase. In contrast to the HI, the
entanglement spectrum is not doubly degenerate, i.e. $P_{\Lambda}\neq 0$ (see
panels (a) and (b) of Fig. 2). Also, the TTI presents no structure factor peak
at $k\neq 0$. In particular, the peak at $k=2\pi/3$, characterizing the 3DW,
vanishes at the TTI-3DW transition (Fig. 3(a)). Despite of the lack of spatial
ordering, the TTI displays intriguing correlations of the site occupations,
which we characterize by means of the generalized string correlations [28]

$R(q)=\lim_{j\to\infty}\frac{\langle\hat{P}_{0}(q)e^{i\pi\sum_{0<k<j}\sum_{s}\hat{P}_{k}(2s)}\hat{P}_{j}(q)\rangle}{\langle\hat{P}_{0}(q)\hat{P}_{j}(q)\rangle},$
(6)

where $\hat{P}_{i}(q)=\prod_{k\neq s}(\hat{n}-k)/\prod_{k^{\prime}\neq
q}(q-k^{\prime})$ project into states with $q$ particles at site $i$. The
correlation $R(q)$ measures the parity of the number of evenly occupied sites
between two sites occupied by $q$ particles. We may characterize the
insulating phases by monitoring $R_{E}=\sum_{s}R(2s)$ and
$R_{O}=\sum_{s}R(2s+1)$, as illustrated in Fig. 2(c) and Fig. 2(d). In
particular, the HI phase, with its diluted antiferromagnetic order of
alternated empty sites (holons) and doubly-occupied ones (doublons) within a
set of otherwise singly-occupied sites (singlons), is characterized by
$R_{O}\simeq 0$ and $R_{E}<0$.

Figure 3: (a1) Sketch of the number distribution deep within the 3DW phase:
$(030)$ blocks (blue slabs) with occasional interspersed defects $(021)$ or
$(120)$ (red slabs)induced by hopping. (a2) In the TTI, regions with holons,
singlons, and doublons (red slabs) are interspersed with a low filling of
$(030)$ blocks (blue slabs), which retain a tendency to form pairs. (b)
Structure factor $S(k=2\pi/3)$ and triplon population $P_{3}$ at the TTI-3DW
interface for $U/V=0.74$. (c) Triplon correlation $\eta_{r}(3)$ and (d)
probability $\mathcal{Q}_{r}$ to find nearest triplons at a distance $r$ (see
text), for $U/t=2.8$ and $V/t=3.8$, well within the TTI phase. In all cases we
consider $\beta_{\mathrm{eff}}=1$.

Deep in the 3DW phase, i.e. at large $V/t$ for $(U/V)_{2}<(U/V)<(U/V)_{3}$,
the ground state is approximately a crystal of triply-occupied sites
(triplons) $|\dots 030030030\dots\rangle$, with maximal triplon population
$P_{3}\equiv\sum_{i}\langle\hat{P}_{i}(3)\rangle=L/3$. Due to hopping, $(030)$
blocks occassionally decay into defects $(120)$ or $(021)$ as depicted in Fig.
3(a1). The 3DW is hence characterized by $R_{O}>0$, since between two triplons
there is always an even number of doublons plus holons. Moreover, $R_{E}=0$,
due to the arbitrary parity of the number of evenly-occupied sites between two
holons or two doublons.

When $V$ decreases the number of defects in the 3DW increases. At a critical
$V$, which coincides with half triplon filling, $P_{3}\simeq L/6$ – Fig. 3(b)
– the system enters the TTI phase. Defects $(021)$ an $(120)$ unravel due to
hopping, and the parity order associated to pairs $(12)$ or $(21)$,
$\mathcal{O}_{P}(1,2)=\langle(-1)^{\sum_{i<l<j}(P_{1}(l)+P_{2}(l))}\rangle$
which is finite inside the 3DW, vanishes at the 3DW-TTI transition. However,
most hops only affect holons, singlons and doublons located between $(030)$
blocks (orange region in Fig. 3 (a2)), which do not modify $R_{E}$ or $R_{O}$.
As a result, correlations $R_{E}\simeq 0$ and $R_{O}>0$ are preserved in the
TTI phase, compare panels (c) and (d) in Fig. 2.

Moreover, although the long-range 3DW order is lost, short-range triplon
correlations
$\eta_{r}(3)=\frac{1}{3}\langle\hat{P}_{i}(3)\hat{P}_{i+r}(3)\rangle/\langle\hat{P}_{i}(3)\rangle^{2}$
are still significant, see Fig. 3(c). For comparison, note that
$\eta_{3n}(3)=1$ and $\eta_{3n\pm 1}(3)=0$ deeply inside the 3DW phase.
Further understanding is achieved by monitoring the probability that nearest-
neighboring triplons are $r$ sites apart,
$\mathcal{Q}_{r}=\bar{\mathcal{Q}}_{r}/\sum_{r}\bar{\mathcal{Q}}_{r}$, with

$\bar{\mathcal{Q}}_{r}=\langle\hat{P}_{j}(3)[\Pi_{j<k<j+r}(1-\hat{P}_{k}(3))]\hat{P}_{j+r}(3)\rangle.$
(7)

Deep in the 3DW phase, $\mathcal{Q}_{r}$ presents obviously a single peak at
$r=3$. When $V/t$ decreases, the formation of defects leads to finite
$\mathcal{Q}_{6,9,\dots}$. Upon a further decrease of $V/t$, triplon
destruction leads to an approximately random separation between nearest
triplons in the TTI phase, resulting in the exponential tail in the
$\mathcal{Q}_{r}$ distribution observed in Fig. 3(d)). At short distances the
triplon distribution is however not random. Triplons strongly block each other
up to two sites apart. Moreover, triplons in the TTI phase still keep a marked
tendency to form pairs placed three sites apart, as also indicated by the
strong correlation $\eta_{3}(3)$ observed in Fig. 3(c). All these correlations
vanish when the TTI transitions into the SF.

## TI phase.–

Remarkably, whereas reducing $V/t$ induces the melting of the 3DW into the
TTI, melting of the 4DW leads to a qualitatively different (TI) phase. As for
the TTI, the TI phase is an insulator with exponentially-decaying
$C_{\text{SP}}$ and has no spatial order. In particular, the peak of $S(k)$ at
$k=\pi/2$ characterizing the 4DW phase vanishes when entering the TI. Deep in
the 4DW phase, the state $|\dots 004000400\dots\rangle$ fulfills $R_{E}<0$ and
$R_{O}=0$. Hopping results in defects $(31)$ and $(13)$, which do not affect
these correlations. At the 3DW-TI phase transition the pairing order
$\mathcal{O}_{P}(1,3)=\langle(-1)^{\sum_{i<l<j}(P_{1}(l)+P_{3}(l))}\rangle$
vanishes, however, the $R_{E}$ and $R_{O}$ correlations are maintained, as for
the TTI phase with $R_{E}<0$ and $R_{O}\simeq 0$, as for the HI. Remarkably,
again as for the HI, the TI displays a doubly-degenerate entanglement
spectrum, see Fig 2 (b). However, in contrast to the HI where only holons,
singlons and doublons played a relevant role, the TI presents a large
probability to display triplons and four-fold occupied sites. As a result, the
string-order $\mathcal{O}_{S}$ vanishes in the TI phase.

## Phase transitions.–

Whereas the direct transitions occurring at large-enough $U/t$ and $V/t$
between MI and 2DW and between the $\ell$DW phases are first-order, those
between the insulating phases occurring at low $U/t$ and $V/t$ are second-
order. These transitions are characterized by the behavior of the von Neumann
entanglement entropy $S_{vN}$ at criticality, which we obtain from our iDMRG
calculations, and which up to a constant acquires the form [29]:

$S_{vN}(\chi)=\frac{c}{6}\log\xi_{\chi},$ (8)

where $\chi$ is the bond dimension, $\xi_{\chi}$ is the $\chi$-dependent
correlation length, and $c$ is the central charge. As it is well known, the
MI-HI transition is in the Luttinger liquid universality class with $c=1$ [30,
13]. Our results show that the HI-TTI, and TTI-TI transitions are
characterized as well by $c=1$ (see Fig. 4). As it is also known [30, 13], we
recover that the HI-2DW transition belongs to the Ising universality class
with $c=1/2$. In contrast, the TTI-3DW transition is well described by the
minimal conformal field theory with $c=4/5$, corresponding to the 3-state
Potts universality class, whereas the TI-4DW transition is characterized by
$c=1$, corresponding to the 4-state Potts universality class [31], see Fig. 4.

Figure 4: Entanglement entropy scaling with the correlation length obtained
from iDMRG calculations for the HI-TTI and TTI-3DW transitions (obtained,
respectively, for $U/t=3$, $V/t\approx 3.434$ and $U/t\approx 3.479$,
$V/t\approx 4.688$), and for the TTI-TI and TI-4DW transitions (obtained,
respectively, for $U/t=3$, $V/t\approx 4.331$ and $U/t\approx 1.319$,
$V/t\approx 2.481$). The numerical value extracted is in good agreement with
$c=1$ for HI-TTI, TTI-TI and TI-4DW, and $c=4/5$ for TTI-3DW. In all cases we
consider $\beta_{\mathrm{eff}}=1$.

## Conclusions.–

For one-dimensional polar lattice gases at unit filling, the long-range tail
of the dipolar interaction does not only result, as expected, in a
quantitative modication of the Haldane-insulator parameter region, and in the
existence of density waves with larger integer spatial periods, but also in
the unexpected appearance of additional insulating phases. These spatially
disordered phases present peculiar correlations of site occupations, and may
be either topological (TI) or topologically trivial (TTI). For a $1/r^{3}$
dipolar tail, the TTI is found for $2\lesssim V/t\lesssim 5$, readily
accessible in on-going dysprosium experiments [10]. The observation of the TI
demands softening the transversal confinement to modify the decay of the
dipolar tail. Since this softening reduces $V/t$, the observation of the TI
phase may demand the use of Dy in UV lattices, or the use of polar molecules,
which should be both available in the near future.

###### Acknowledgements.

M.Ł. and J.Z. thank R. Kraus and G. Morigi for interesting discussions. We
acknowledge support of National Science Centre (Poland) via Opus grant
2019/35/B/ST2/00838 (M.Ł.). This research was also funded by National Science
Centre (Poland) under the OPUS call within the WEAVE programme
2021/43/I/ST3/01142 (J.Z.) as well as by the Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation) – Project-ID 274200144 – SFB 1227 DQ-mat
within the project A04, FOR2247, and under Germany’s Excellence Strategy –
EXC-2123 Quantum-Frontiers – 390837967. We gratefully acknowledge Poland’s
high-performance Infrastructure PLGrid (HPC Centers: ACK Cyfronet AGH, PCSS,
CI TASK, WCSS) for providing computer facilities and support within
computational grant no. PLG/2022/015951.

## References

  * Lewenstein  _et al._ [2007] M. Lewenstein, A. Sanpera, V. Ahufinger, B. Damski, A. Sen(De), and U. Sen, Ultracold atomic gases in optical lattices: mimicking condensed matter physics and beyond, Advances in Physics 56, 243 (2007), https://doi.org/10.1080/00018730701223200 .
  * Bloch  _et al._ [2008] I. Bloch, J. Dalibard, and W. Zwerger, Many-body physics with ultracold gases, Rev. Mod. Phys. 80, 885 (2008).
  * Lewenstein  _et al._ [2012] M. Lewenstein, A. Sanpera, and V. Ahufinger,  _Ultracold Atoms in Optical Lattices: Simulating quantum many-body systems_ (Oxford University Press, Oxford, 2012).
  * Trotzky  _et al._ [2008] S. Trotzky, P. Cheinet, S. Fölling, M. Feld, U. Schnorrberger, A. M. Rey, A. Polkovnikov, E. A. Demler, M. D. Lukin, and I. Bloch, Time-resolved observation and control of superexchange interactions with ultracold atoms in optical lattices, Science 319, 295 (2008), https://www.science.org/doi/pdf/10.1126/science.1150841 .
  * Chomaz  _et al._ [2022] L. Chomaz, I. Ferrier-Barbut, F. Ferlaino, B. Laburthe-Tolra, B. L. Lev, and T. Pfau, Dipolar physics: a review of experiments with magnetic quantum gases, Reports on Progress in Physics 86, 026401 (2022).
  * Bohn  _et al._ [2017] J. L. Bohn, A. M. Rey, and J. Ye, Cold molecules: Progress in quantum engineering of chemistry and quantum matter, Science 357, 1002 (2017).
  * Browaeys and Lahaye [2020] A. Browaeys and T. Lahaye, Many-body physics with individually controlled Rydberg atoms, Nature Physics 16, 132 (2020).
  * Dutta  _et al._ [2015] O. Dutta, M. Gajda, P. Hauke, M. Lewenstein, D.-S. Luehmann, B. A. Malomed, T. Sowiński, and J. Zakrzewski, Non-standard Hubbard models in optical lattices: a review, Rep. Prog. Phys. 78, 066001 (2015).
  * Baier  _et al._ [2016] S. Baier, M. J. Mark, D. Petter, K. Aikawa, L. Chomaz, Z. Cai, M. Baranov, P. Zoller, and F. Ferlaino, Extended Bose-Hubbard models with ultracold magnetic atoms, Science 352, 201 (2016), https://www.science.org/doi/pdf/10.1126/science.aac9812 .
  * Su  _et al._ [2023] L. Su, A. Douglas, M. Szurek, R. Groth, S. F. Ozturk, A. Krahn, A. H. Hébert, G. A. Phelps, S. Ebadi, S. Dickerson, F. Ferlaino, O. Marković, and M. Greiner, Dipolar quantum solids emerging in a Hubbard quantum simulator (2023), arXiv:2306.00888 [cond-mat.quant-gas] .
  * Dalla Torre  _et al._ [2006] E. G. Dalla Torre, E. Berg, and E. Altman, Hidden order in 1d Bose insulators, Phys. Rev. Lett. 97, 260401 (2006).
  * Rossini and Fazio [2012] D. Rossini and R. Fazio, Phase diagram of the extended Bose-Hubbard model, New Journal of Physics 14, 065012 (2012).
  * Ejima  _et al._ [2014] S. Ejima, F. Lange, and H. Fehske, Spectral and entanglement properties of the bosonic Haldane insulator, Phys. Rev. Lett. 113, 020401 (2014).
  * Pollmann  _et al._ [2010] F. Pollmann, A. M. Turner, E. Berg, and M. Oshikawa, Entanglement spectrum of a topological phase in one dimension, Phys. Rev. B 81, 064439 (2010).
  * den Nijs and Rommelse [1989] M. den Nijs and K. Rommelse, Preroughening transitions in crystal surfaces and valence-bond phases in quantum spin chains, Phys. Rev. B 40, 4709 (1989).
  * Kennedy and Tasaki [1992] T. Kennedy and H. Tasaki, Hidden ${\mathrm{Z}}_{2}$×${\mathrm{Z}}_{2}$ symmetry breaking in Haldane-gap antiferromagnets, Phys. Rev. B 45, 304 (1992).
  * Biedroń  _et al._ [2018] K. Biedroń, M. Ła̧cki, and J. Zakrzewski, Extended Bose-Hubbard model with dipolar and contact interactions, Phys. Rev. B 97, 245102 (2018).
  * Kraus  _et al._ [2020] R. Kraus, K. Biedroń, J. Zakrzewski, and G. Morigi, Superfluid phases induced by dipolar interactions, Phys. Rev. B 101, 174505 (2020).
  * Wall and Carr [2013] M. L. Wall and L. D. Carr, Dipole–dipole interactions in optical lattices do not follow an inverse cube power law, New Journal of Physics 15, 123005 (2013).
  * Korbmacher  _et al._ [2023a] H. Korbmacher, P. Sierant, W. Li, X. Deng, J. Zakrzewski, and L. Santos, Lattice control of nonergodicity in a polar lattice gas, Phys. Rev. A 107, 013301 (2023a).
  * Korbmacher  _et al._ [2023b] H. Korbmacher, G. A. Domínguez-Castro, W.-H. Li, J. Zakrzewski, and L. Santos, Transversal effects on the ground state of hard-core dipolar bosons in one-dimensional optical lattices, Phys. Rev. A 107, 063307 (2023b).
  * Gross and Bakr [2021] C. Gross and W. S. Bakr, Quantum gas microscopy for single atom and spin detection, Nature Physics 17, 1316 (2021).
  * Sowiński  _et al._ [2012] T. Sowiński, O. Dutta, P. Hauke, L. Tagliacozzo, and M. Lewenstein, Dipolar molecules in optical lattices, Phys. Rev. Lett. 108, 115301 (2012).
  * Kraus  _et al._ [2022] R. Kraus, T. Chanda, J. Zakrzewski, and G. Morigi, Quantum phases of dipolar bosons in one-dimensional optical lattices, Phys. Rev. B 106, 035144 (2022).
  * Batrouni  _et al._ [2014] G. G. Batrouni, V. G. Rousseau, R. T. Scalettar, and B. Grémaud, Competing phases, phase separation, and coexistence in the extended one-dimensional bosonic Hubbard model, Phys. Rev. B 90, 205123 (2014).
  * Kottmann  _et al._ [2021] K. Kottmann, A. Haller, A. Acín, G. E. Astrakharchik, and M. Lewenstein, Supersolid-superfluid phase separation in the extended Bose-Hubbard model, Phys. Rev. B 104, 174514 (2021).
  * Chen  _et al._ [2003] W. Chen, K. Hida, and B. C. Sanctuary, Ground-state phase diagram of $s=1$ $\mathrm{XXZ}$ chains with uniaxial single-ion-type anisotropy, Phys. Rev. B 67, 104401 (2003).
  * [28] Additional precaution is necessary due to the oscillatory character of the string-like correlations in the $\ell$DW phases. Hence, before taking the limit $j\rightarrow\infty$ we first average over few $j$ sites respecting the phase periodicity. In this way the oscillations in $R(q)$ in $\ell$DW phases cancel out to zero.
  * Calabrese and Lefevre [2008] P. Calabrese and A. Lefevre, Entanglement spectrum in one-dimensional systems, Phys. Rev. A 78, 032329 (2008).
  * Berg  _et al._ [2008] E. Berg, E. G. Dalla Torre, T. Giamarchi, and E. Altman, Rise and fall of hidden string order of lattice bosons, Phys. Rev. B 77, 245119 (2008).
  * Dotsenko [2020] V. S. Dotsenko, Four spins correlation function of the q states Potts model, for general values of q. Its percolation model limit q$\rightarrow$1, Nuclear Physics B 953, 114973 (2020).


# Low complexity, low probability patterns and consequences
for algorithmic probability applications

Mohamed Alaskandarani  Centre for Applied Mathematics and Bioinformatics
(CAMB), Department of Mathematics and Natural Sciences, Gulf University for
Science and Technology, Kuwait  Kamaludin Dingle  Correspondence:
<EMAIL_ADDRESS>Centre for Applied Mathematics and Bioinformatics (CAMB),
Department of Mathematics and Natural Sciences, Gulf University for Science
and Technology, Kuwait  Department of Chemical Engineering and Biotechnology,
Cambridge University, UK  Department of Computing and Mathematical Sciences,
Caltech, USA

###### Abstract

Developing new ways to estimate probabilities can be valuable for science,
statistics, and engineering. By considering the information content of
different output patterns, recent work invoking algorithmic information theory
has shown that a priori probability predictions based on pattern complexities
can be made in a broad class of input-output maps. These algorithmic
probability predictions do not depend on a detailed knowledge of how output
patterns were produced, or historical statistical data. Although
quantitatively fairly accurate, a main weakness of these predictions is that
they are given as an upper bound on the probability of a pattern, but many low
complexity, low probability patterns occur, for which the upper bound has
little predictive value. Here we study this low complexity, low probability
phenomenon by looking at example maps, namely a finite state transducer,
natural time series data, RNA molecule structures, and polynomial curves. Some
mechanisms causing low complexity, low probability behaviour are identified,
and we argue this behaviour should be assumed as a default in the real world
algorithmic probability studies. Additionally, we examine some applications of
algorithmic probability and discuss some implications of low complexity, low
probability patterns for several research areas including simplicity in
physics and biology, a priori probability predictions, Solomonoff induction
and Occam’s razor, machine learning, and password guessing.

Keywords: Algorithmic probability; Kolmogorov complexity; prediction;
induction.

##  I Introduction

Many problems in science, statistics, and engineering revolve around
estimating probabilities of events. This is especially true in the current
climate, where machine learning and data science are enjoying broad
applications. Hence developing new methods for calculating, bounding, or
predicting probabilities is valuable. One direction for such predictions is in
theoretical computer science where _algorithmic information theory_
solomonoff1960preliminary ; kolmogorov1965three ; chaitin1975theory ;
li2008introduction  (AIT) provides a theoretical framework for studying
randomness, probability, and complexity. The central quantity of AIT is
_Kolmogorov complexity_ , $K(x)$, which measures the complexity of an
individual object or pattern $x$ via the amount of information required to
describe or generate $x$. The object could be a binary string, integer, graph,
or indeed anything that can be represented as a binary string. The AIT coding
theorem levin1974laws  establishes a fundamental connection between complexity
and probability predictions in very general settings. It states that the
chances that some output $x$ is produced via some generic computation
mechanism is directly related to the complexity of $x$. More formally, the
coding theorem states that $P(x)\sim 2^{-K(x)}$ where $P(x)$ is the
probability that an output $x$ is generated by a (prefix optimal) universal
Turing machine fed with a random binary program input. $P(x)$ is known as the
_algorithmic probability_ of $x$, and the associated probability distribution
is known as the _universal distribution_ solomonoff2003kolmogorov .

(a)

(b)

(c)

(d)

Figure 1: Simplicity bias plots with low complexity, low probability outputs.
Blue dots represent different binary string output patterns. The black line is
the upper bound of Eq. (3). Probabilities $P(x)$ are the fraction of random
inputs that map to output $x$. $\tilde{K}(x)$ are estimated complexity values
for each output $x$. There are many data points far below the upper bound;
these points are low Kolmogorov complexity, low probability (LKLP) output
patterns. The maps studied are: (a) A finite state transducer (FST) with data
taken from ref. dingle2020generic ; (b) time series patterns from the World
Bank Open Data, with data taken from dingle2022note ; (c) computationally
predicted RNA secondary structures from 1 million randomly sampled input
sequences; and (d) discretised polynomials curves generated with $x\in$(0,1)
and random coefficients, data taken from dingle2018input .

Algorithmic probability and AIT results are typically difficult to apply in
real-world settings due to the fact that $K(x)$ is uncomputable, the theorems
assume the presence of universal Turing machines (UTMs), and the results are
asymptotic and stated with accuracy to within an unknown constant. Despite
these theoretical difficulties, in practice many successful applications of
AIT have been made based, for example in bioinformatics
cilibrasi2005clustering ; ferragina2007compression , physics
avinery2019universal , signal denoising vitanyi2013similarity , among many
other applications li2008introduction . Mostly these applications use standard
compression algorithms to approximate $K(x)$, sometimes combined with various
forms of theorem approximation. Algorithmic probability estimates have been
made numerically by random sampling legg2011approximation  and enumeration
delahaye2012numerical ; soler2014calculating ; zenil2019coding  of computer
programs.

From a very different perspective, algorithmic probability estimates have also
been made via deriving a weaker form of the coding theorem, applicable in
real-world contexts dingle2018input , taking the form of an upper bound. This
weaker form upper bound was applied in a range of input-output maps to make a
priori predictions of the probability of different shapes and patterns, such
as the probability of different RNA shapes appearing on a random choice of
genetic sequence, or the probability of differential equation solution profile
shapes, on random choice of input parameters, and several other examples
dingle2018input ; dingle2020generic . Surprisingly, it was found that
probability estimates could be made directly from the complexities of the
shapes themselves, without recourse to the details of the map or reference to
how the shapes were generated. The authors of dingle2018input  termed this
phenomenon of an inverse relation between complexity and probability
_simplicity bias_ (SB). One important drawback of this work is that only an
upper bound prediction was made, rather than a direct probability value
prediction. In contrast to original coding theorem, in practice it has been
observed that many simple patterns have low probability dingle2018input . Such
low Kolmogorov complexity, low probability (LKLP) outputs present a weakness
in the predictive ability of the upper bound, because for these outputs their
complexity and probability values are largely disconnected and hence
predicting one from the other is more challenging. Understanding the causes
and properties of LKLP outputs may help to improve the accuracy of
applications of algorithmic probability, such as better a priori probability
predictions and induction. In this work we investigate LKLP behaviour, and its
implications for applied algorithmic probability via some examples from
previously published works.

##  II Background theory

Some brief accessible background theory is given here; more formal and
detailed presentations are available in, eg refs. li2008introduction ;
calude2002information ; gacs1988lecture . A universal Turing machine (UTM)
turing1936computable  is an abstract general computing device which can
simulate any other Turing machine. A UTM has the highest computational
capacity, and can implement any conceivable algorithm which could in principle
be run on a computer. A programming language is called _Turing complete_ (or
computationally universal) if the language is sufficiently expressive to be
able to simulate a UTM, and therefore implement any algorithm. Common
languages like Python, C, FORTRAN, etc are Turing complete. If a function can
be computed by a finite mechanical procedure, then it a computable function.
For computable functions, all inputs or programs eventually halt, and cannot
(for example) run on forever in an infinite loop. Common functions like
polynomials, exponentials, trigonomentric functions, etc are computable.

The Kolmogorov complexity $K_{U}(x)$ of a string $x$ with respect to $U$, is
defined solomonoff1960preliminary ; kolmogorov1965three ; chaitin1975theory
as

$K_{U}(x)=\min_{p}\\{|p|:U(p)=x\\}$ (1)

where $p$ is a binary program for a prefix optimal UTM $U$, and $|p|$
indicates the length of the binary program $p$ in bits. Due to the invariance
theorem li2008introduction  for any two optimal UTMs $U$ and $V$,
$K_{U}(x)=K_{V}(x)+O(1)$ so that the complexity of $x$ is independent of the
machine, up to additive constants. Hence we conventionally drop the subscript
$U$ in $K_{U}(x)$, and speak of ‘the’ Kolmogorov complexity $K(x)$.
Informally, $K(x)$ can be defined as the length of a shortest program that
produces $x$, or simply as the size in bits of the compressed version of $x$.
If $x$ contains repeating patterns like $x=1010101010101010$ then it is easy
to compress, and hence $K(x)$ will be small. On the other hand, a randomly
generated bit string of length $n$ is highly unlikely to contain any
significant patterns, and hence can only be described via specifying each bit
separately without any compression, so that $K(x)\approx n$ bits. Other names
for $K(x)$ are _descriptional complexity_ , _algorithmic complexity_ , and
_program-size complexity_. Fundamentally, $K(x)$ measures the amount of
information to describe or generate $x$ precisely and unambiguously. Note that
Shannon information and Kolmogorov complexity are closely related to each
other grunwald2004shannon , but also differ fundamentally because Shannon
information quantifies the information content of a random source, while
Kolmogorov complexity quantifies the information of individual sequences or
objects.

Solomonoff invented algorithmic probability solomonoff2009algorithmic , but it
was later formalised and extended by Levin levin1974laws , who proved the AIT
_coding theorem_ in 1974 which states that

$P(x)=2^{-K(x)+O(1)}$ (2)

where $P(x)$ is the probability that UTM $U$ generates output string $x$ on
being fed random bits as a program (again we have dropped the subscript $U$).
Thus, high complexity outputs have exponentially low probability, and simple
outputs must have high probability.

Coding theorem-like behaviour in real-world input-output maps was studied,
leading to the observation of a phenomenon called _simplicity bias_ (SB)
dingle2018input . SB is captured mathematically as

$P(x)\leq 2^{-a\tilde{K}(x)-b}$ (3)

where $P(x)$ is the (computable) probability of observing output $x$ on random
choice of inputs, and $\tilde{K}(x)$ is the estimated Kolmogorov complexity of
the output $x$: complex outputs from input-output maps have lower
probabilities, and high probability outputs are simpler. The constants $a>0$
can often be estimated without recourse to sampling, but just by knowing or
estimating the total number of different possible outputs dingle2018input .
Using $b=0$ is the default guess for this constant, but it can also be fit to
the data via partial sampling.

A complete understanding of exactly which maps will show SB has not been
developed, but SB is expected to appear in many input-output maps, under
fairly general conditions. Importantly, the map should be ‘simple’
(technically of $O(1)$ complexity) to prevent the map itself from dominating
over inputs in defining output patterns. If an arbitrarily complex map was
permitted, outputs could have arbitrary complexities and probabilities, and
thereby remove any connection between probability and complexity. Strong bias
is a prerequisite for SB, typically the relative value of the largest and
smallest probabilities should be more than the value of the number of outputs,
ie for $N_{O}$ outputs, $\max(P(x))/\min(P(x))>N_{O}$.

##  III Results

###  III.1 Low complexity, low probability behaviour is very common

Based on numerical experiments using the upper bound of Eq. (3), Dingle et al
dingle2018input  reported that many outputs $x$ have probability values far
below their predicted upper bounds, ie $P(x)\ll 2^{-a\tilde{K}(x)-b}$ for many
$x$. This observation was not due to the bound being trivially loose, because
it is a tight bound for many outputs. Significantly, the small fraction of
outputs which were close to the upper bound absorbed most of the probability
mass, or in other words most of the inputs map to outputs for which the bound
is tight. As a consequence it was shown dingle2018input ; dingle2020generic
analytically and numerically that for an output $x$ generated by a random
input, with high probability $P(x)\approx 2^{-a\tilde{K}(x)-b}$.

To illustrate the LKLP phenomenon, in Figure 1 we show four probability-
complexity plots. The probabilities $P(x)$ are calculated as the fraction of
random inputs which produce output $x$. The complexity $\tilde{K}(x)$ denotes
an estimate of the Kolmogorov complexity of each output, using a slightly
adapted dingle2018input  version of the famous Lempel-Ziv lempel1976complexity
1976 complexity measure. The black lines are fitted upper-bounds, depicting
the SB upper bound of Eq. (3). All four maps have been studied in earlier
works, and are: (a) a finite state transducer (FST), which is a simple generic
model of computation, but unlike a UTM has a very limited computational
capacity (being the lowest on the Chomsky hierarchy). Here the outputs are
length 30 bits, and were obtained from thorough sampling of binary string
inputs, and the data was taken from ref. dingle2020generic . (b) Time series
data taken from the World Bank Open Data project (https://data.worldbank.org),
which have been discretised to binary strings (of length 16 bits) while
studying SB dingle2022note . (c) Computationally predicted lorenz2011viennarna
RNA secondary structures obtained from randomly sampling 1 million sequences
of length $L=35$ nucleotides. Following the protocol of ref. dingle2018input
in which SB in computationally generated RNA structures was first reported,
predicted dot-bracket structures were converted to binary strings and
complexity values were thereby estimated. (d) Polynomial curves
$y=\sum_{i=1}^{14}\alpha_{i}x^{i}$ with Gaussian random coefficients
$\alpha_{i}$ and $x\in(0,1)$, with data from dingle2018input . The curves were
discretised to binary strings by the up/down method hansen2001model ;
willbrand2005identifying . More details of these maps and relevant analyses
can be found in the original cited papers.

It is apparent that in each panel of Figure 1 the data points show a similar
‘triangle’ shape, with some points closely following the upper bound (black
line), but at the same time for each complexity value a large variation in
probability values is observed, inferred from the many points far below the
bound. Occupying the bottom left corner of the ‘triangles’ are the outputs
which exhibit the strongest LKLP behaviour, because they have very low
probability, but at the same time have relatively low complexity values. This
LKLP ‘triangle’ depicted in all maps of Figure 1 appears in essentially all
examples of SB studied so far, including in biology johnston2022symmetry ,
machine learning valle2018deep , and other contexts dingle2018input  (Supp.
Info.).

In Figure 1 and in most other SB examples cited, the previously described
complexity estimator $\tilde{K}(x)$ based on the Lempel-Ziv complexity measure
was used. However, LKLP outputs have also been observed when using other
complexity measures, such as those used in protein quaternary structures and
polyominos johnston2022symmetry , so LKLP outputs are not merely an artefact
of the Lempel-Ziv complexity measure. From another angle, nearly all the cited
complexity-probability plots showing SB were generated via random sampling of
inputs, and so it might be suggested that with more sampling, or full
enumeration of inputs, LKLP outputs would disappear or at least become much
less pronounced. However, this suggestion is countered by the observation that
LKLP behaviour is also observed in maps for which probabilities were directly
calculated by enumerating every possible input, for example L-systems
dingle2018input  and RNA length $L=15$ nucleotides dingle2020generic . Perhaps
the only clear example of a map which does not show strong LKLP behaviour is
in a small polyomino system using path complexity (see Fig 4.2(a) in Chapter 4
of ref. dingle2014probabilistic ).

To avoid confusion, we stress that LKLP behaviour is not due to a failing of
complexity measures to detect patterns. If, say, the Lempel-Ziv measure failed
to detect an important pattern and thereby assigned a high complexity to an
output which is actually simple, then the opposite behaviour would be observed
in the complexity-probability plots, where some outputs would be far _above_
the upper bound, not far below the bound.

A well known limitation of the original coding theorem is choice of UTM, the
problem being that algorithmic probability estimates from different machines
will differ leike2015bad , and there is no known way to remove this dependence
muller2010stationary . However, due to the invariance theorem, this machine
dependence is only a problem for (typically small) outputs with low
complexities, for which $O(1)$ terms due to translating between UTMs may
dominate, but this is not a problem for large complexity strings. This machine
dependence limitation may not be of great concern perhaps, because many real-
world phenomenon are highly complex. In contrast, LKLP outputs do not
disappear for large complexity outputs, and so LKLP can be seen as a more
serious problem for applied algorithmic probability than machine dependence.

Finally, in many maps which exhibit SB, some patterns are actually impossible
to make, such that $P(x)=0$, so this could be viewed as an extreme form of
LKLP behaviour.

###  III.2 Estimating which of two outputs is more likely

Another way to examine and quantify LKLP behaviour is in terms of predicting
which of two outputs has higher probability. In the absence of LKLP outputs,
if $K(x)<K(y)$ for two strings $x$ and $y$ then it follows from Eq. (2) that
$P(x)>P(y)$, ignoring $O(1)$ terms. With LKLP behaviour, the direct connection
between probability and complexity is disrupted, and $K(x)<K(y)$ does not
imply that $P(x)>P(y)$ necessarily. Note that predicting which of two strings
has higher probability does not depend on estimating or fitting the parameters
$a$ and $b$ in Eq. (3); only the complexity values are required. This kind of
calculation was done earlier by dingle2018input ; dingle2022note .

The manner in which the strings $x$ and $y$ are chosen also affects the
strength of the connection between complexity and probability. If $x$ and $y$
result from randomly chosen inputs, then they will be sampled with weights
according to their probabilities, and in this case
$P(x)$$\approx$$2^{-a\tilde{K}(x)-b}$ and
$P(y)$$\approx$$2^{-a\tilde{K}(y)-b}$ dingle2020generic . In this probability-
weighted sampling scenario, for randomly generated outputs, the probability-
complexity connection is quite strong. Hence we should expect to be able to
predict whether $P(x)>P(y)$ or $P(x)<P(y)$ just from the complexity values,
with quite high accuracy. If instead $x$ and $y$ are chosen uniformly randomly
from the full set of possible outputs, then we can expect the probability-
complexity connection to be less strong, and predicting whether $P(x)>P(y)$ or
$P(x)<P(y)$ just from the complexity values will be less accurate.

Here we computationally study the question of which of two strings has higher
probability, both using the randomly generated pairs $x,y$ and also uniformly
sampled $x,y$. The protocol we employ is: predict $P(x)>P(y)$ if $K(x)<K(y)$,
$P(x)<P(y)$ if $K(x)>K(y)$, and we randomly guess which has higher probability
if $K(x)=K(y)$. Note that there will be relatively few unique complexity
values (eg only $\sim n$ values for strings of length $n$), and hence it
happens quite commonly that two random strings have the same complexity, while
it is relatively rare for two strings to have exactly the same probability
value.

For both probability-weighted sampling and uniform sampling, the protocol just
described has a null prediction accuracy level of 50% (assuming a null
hypothesis that output complexity has no predictive value). The calculated
accuracy values (after 10,000 sampled pairs) are: FST probability-weighted
sampling achieved an accuracy of 79% and uniform sampling an accuracy of 63%;
time series 81% and 80%; RNA 78% and 71%; polynomial 82% and 73%. It is quite
striking that high levels of accuracy can be achieved just by complexity
estimates, which does not even require estimating the values of $a$ or $b$. As
expected, the accuracy values for probability-weighted sampling are higher,
while substantially lower for uniform sampling, but still substantially above
the 50% null model mark. Overall, the effect of LKLP outputs it clear: while
some % accuracy values are (surprisingly) high, they are still substantially
below 100% which is what we would expect in the absence of LKLP outputs.

Note that true uniform sampling strictly requires knowing the full set of
outputs, which might entail fully enumerating all inputs, or very thorough
input sampling. In the four maps studied here, only the FST map was thoroughly
sampled whereas the other maps were sampled partially (eg for RNA, only
$10^{6}$ sampled inputs out of a possible $4^{30}\sim 10^{18}$ RNA sequence
inputs were made). Hence our stated accuracy values for ‘uniform sampling’
will be somewhat overestimates for RNA, time series, and polynomials, but for
the FST map the accuracy value of 63% is likely to be close to the true value.

(a)

(b)

(c)

(d)

Figure 2: Rank plots of probabilities, separated by complexity values. Each
coloured line depicts the decay in probability of outputs with the same
complexity value $k$. The complexity values $k$ are shown in the figure
legends. The plots present the same data as in Figure 1, but now plotted as
rank plots separated by complexity value. (a) FST; (b) time series; (c) RNA
structures; and (d) random polynomials. In each case, a similar pattern of
decay is observed, and almost all rank plots decay to the lowest probability
for that map.

###  III.3 Why do low complexity, low probability
outputs exist?

We have seen LKLP outputs in essentially all the maps we have studied. Why are
they so common? In the original AIT coding theorem given in Eq. (2), there are
no LKLP output patterns, except in the rather modest sense that the $O(1)$
term in the exponent allows for relatively small variation of probabilities
within a constant, mathematically $|K(x)-\log_{2}(1/P(x))|<c$ for some
constant $c$. The reason simple outputs cannot have very low probability in
the original AIT coding theorem is that the theorem is based on random prefix
codes run on a UTM. In a UTM an output $x$ always has a program $p$ of length
$K(x)$ by definition of Kolmogorov complexity. The probability that the
specific program $p$ appears as the first $p$ bits of the random binary
program is $2^{-K(x)}$ and therefore $P(x)\geq 2^{-K(x)}$ implying that all
simple strings must have high probability. Hence in this UTM setting, it is
not possible to have LKLP outputs with $P(x)\ll 2^{-K(x)+O(1)}$.

Computable maps lack some computational power as compared to UTMs, which means
that there are some algorithms which they cannot implement (for example, ones
that don’t halt). As suggested earlier dingle2020generic  the weaker
computational ability of these computable maps suggests that they may not be
able to compute some output patterns which are nonetheless simple, or at least
cannot compute them with efficient short programs. Hence we can expect some
type of LKLP in computable maps, and the lower bound $P(x)\geq 2^{-K(x)}$ does
not necessarily hold.

Looking more closely at the lower bound vs. upper bound contrast, it appears
that the upper bound on $P(x)$ is more fundamental. The justification is that
if the upper bound was violated, and some complex outputs had high
probability, then it would be as if the map itself was creating information,
which is not possible, assuming that the map is ‘simple’ with $O(1)$
complexity. In contrast, no fundamental information theory violations arise if
a simple output has a low probability, which helps to understand their common
occurrence.

It is worth noting that LKLP behaviour is not actually a mathematical
necessity for computable maps in general if a computable estimate of
complexity is used. To see why, one could easily directly construct a map
which has outputs with probability $2^{-\tilde{K}(x)}$, for some (computable)
choice of $\tilde{K}(x)$ such as a Lempel-Ziv complexity measure. By
construction, all probabilities would sit on the upper bound, with no LKLP
outputs. A less contrived instance where LKLP behaviour may be less common is
in maps for which inputs are organised into ‘constrained’ and ‘unconstrained’
regions greenbury2015organization , which is similar to a Shannon-Fano coding.
Having said that, even in this setting it is possible to have simple patterns
with low probability.

In ref. dingle2020generic  it was suggested that LKLP outputs are
intrinsically simple yet ‘hard’ to make for the specific map, and it was shown
analytically that such outputs coincide with those that can only be generated
(via the map) with simple input. Indeed, a lower bound on $P(x)$ based on
complexity inputs and outputs was derived.

Illustrating the ‘hard to make’ argument in the present context, we can take
time series as an example, for which we find that the bit strings
$x$=1111111011111111 and $y$=0000000011111111 in Figure 1(b) were assigned the
same low complexity value, and yet $y$ had a $\sim$$10^{3}$ fold higher
probability than $x$, which was a LKLP output. Thinking about common time
series patterns from everyday experience, we can see that $y$ is ‘easy’ to
make for a time series because the binary string pattern $y$ would result from
essentially any gradually increasing series, such as linear or exponential
growth, both of which are very common. In contrast, even though $x$ is simple
— just a string of 1’s with a single 0 in the middle — it would be ‘hard’ to
make such a string because in the discretisation process a ‘1’ denotes a
series value above the mean value of the series, and 0 denotes below. Hence to
generate $x$ would require one very low value in the middle of a stretch of
high values, which is quite unlikely to occur in a time series. Given the way
the series was discretised in terms of above/below the mean value of the
string, we can expect that strings with an excess of 1’s or 0’s will have low
probability, even if they are not complex. For RNA secondary structure a ‘hard
to make’ output was given in ref. dingle2020generic  where it was pointed out
that the dot-bracket representation of an RNA structure such as
(.(.(.(.(.(.(.(.(.(…).).).).).).).).).) would be thermodynamically
unfavourable due to many lone chemical bonds, and therefore it would have very
low probability, despite being a simple symmetric structure. More generally,
it is not hard to see that a given map will have certain biases towards or
against certain patterns, and these map-specific biases can affect
probabilities strongly, independently of pattern complexity.

Another way that LKLP outputs can occur is if the complexity measure is too
coarse, assigning too few complexity values. For a binary string of length
$n$, there are around $n$ possible complexity values, so if a measure assigns
much less than $n$ complexity values, then different complexity values will be
combined together into one grouping, but their true complexities will actually
be varied, and hence we can expect their probabilities to vary also,
apparently yielding LKLP outputs.

The fact that the LKLP ‘triangle’ is common to essentially all maps studied so
far in the literature suggests there may be a general explanation. Burkat &
Dingle burkat2022note  studied SB in the Bernoulli process with parameter
$\neq 0.5$, and reported that both the single highest and single lowest
probability outputs are also the simplest, and pointed out the cause of LKLP
outputs in the Bernoulli map is easy to understand. As an extension, we
propose here that if an output is (even roughly) made up of statistically
independent parts, then the output may be approximated as a (biased) Bernoulli
process, for which we expect LKLP behaviour burkat2022note . As an example,
for a time series of some fixed length $n$, the non-adjacent values are
typically correlated only weakly, hence roughly independent, especially if
separated by longer intervals. Even for RNA secondary structure for which
there are definite correlations between distant parts of the sequence due to
bonding interactions, but nonetheless much of the structure is roughly
independent of other structure provided the sequence is not very short. This
line of argument might help to explain some instances of LKLP outputs.

(a)

(b)

(c)

(d)

Figure 3: Number of 0/1 of changes in an output string vs the output
probability, for just one complexity value $k$. (a) For the FST map, there is
a clear decay in probability with increasing numbers of 0/1 changes, using
complexity $k=$ 17; (b) similarly for the time series data, there is a clear
decay, using $k=$ 14; (c) For the RNA there is a strong decay after an initial
increase, using $k=$ 22; (d) no trend for the polynomials data, using $k=$ 19.

(a)

(b)

(c)

(d)

Figure 4: The number of 1’s in an output string vs the string’s probability.
For each example map a plot is given for just one complexity value $k$, the
second simplest, chosen to aid illustration. (a) The FST example shows a
linear trend in log probability with increasing number of 1’s, using
complexity $k=$17; (b) Large and small numbers of 1’s are not favoured in the
time series, using $k=$14; (c) RNA shows an overall negative relation, using
$k=$22; (d) polynomials, similar to time series, large and small numbers of
1’s are not favoured, using $k=$19.

###  III.4 Rank plots of probability values, separated by complexity

We now study the distribution of LKLP probabilities for the four maps shown in
Figure 1 above. Within Figure 1, LKLP outputs appear as a ‘column’ of
overlapping blue dots stretching down from the black line upper bound, but the
distribution of those LKLP probability values is not easy to discern. Instead
in Figure 2 for each of those maps, a loglog plot is given showing the rank
and probability of each output, coloured separately by complexity value $k$,
so that the distribution is more easily visualised.

There are some common patterns to these disparate rank plots: In nearly all
cases the rank plots for all complexity values decay to the same lowest
probability, eg for the FST data in Figure 2(a) all the complexity values from
$k=14$ to $k=46$ decay to a similar low probability value of close to
$10^{-8}$. It is not clear exactly why this occurs with such consistency. This
needs to be explored in future work.

Another observation is that the probability decay follows a similar form, with
the lowest complexity curves starting at a high probability and quickly
decaying, and the higher complexity curves starting lower probability and
slowly decaying. This observation can be rationalised by noting that for low
complexities, there are exponentially few possible outputs (ie few simple
patterns), yet some of these have exponentially high probability as expected
from SB. As the complexity increases, it is well known from AIT that there are
exponentially more possible patterns for a given complexity value, yet the
maximum probability decays exponentially (consistent with the upper bound of
Eq. 3), which explains why the rank plots become wider and less tall for
higher complexities.

Interestingly, in the FST map, which has the cleanest data, the profile of the
different curves appear to depict a straight line decay on the loglog plot,
suggesting some kind of Zipf’s power law upper bound on the rank decay
profiles. Although the other maps do not show this power-law behaviour
clearly, they are also more noisy datasets. We conjecture that some kind of
Zipf’s law may be a more general feature of these kinds of plots.

It was shown dingle2020generic  that the sum of the probability mass of
outputs with $\log_{2}$ probability that is at least $\Delta$ bits below the
upper bound is no more than $2^{-\Delta+1+O(1)}$. This implies that if there
is decay in probabilities, it should be at least exponential. However this
does not explain why there is, for all maps, a roughly smooth exponential
decay to the same lowest probability. This remains and open question for
future work.

###  III.5 Is there a bias against changes in natural data?

We saw that map-specific idiosyncrasies can bias output probabilities via
patterns which are hard to make for the map but are not in themselves very
complex. But are there any general trends which are likely to be common across
different real world maps? The AIT coding theorem in Eq. (2) and the related
upper bound in Eq. (3) are based on fundamental information content of
patterns assumed to be generated by UTMs, but in the natural world many
patterns may not be physically easy to make. We suspect there is a disconnect
between simple patterns with low information content, and those which are easy
to make by real world systems. As an example, the patterns $x=$00000001111111
and $y=$01010101010101 have similar complexity from an information
perspective, eg they have the same entropy and same size. But it may be that
oscillations of $y$ are ‘harder’ to maintain in the physical world than the
one simple change in $x$, because change is often expensive in terms of energy
or mechanics (with notable exceptions like pendulums, but even they can be
easily upset). A more extreme example is the Champernowne’s number
0.123456789101112…. which again is a very simple in terms of information
content, but it is hard to see how any natural system in the physical world
could make such a pattern. Potentially these kinds of patterns may be LKLP in
a range of different computable, physically relevant maps.

As a first brief investigation into whether change is ‘hard’ to generate for
natural systems and hence associated to LKLP outputs, we study just the
frequency of 0/1 changes in outputs. By “changes” we mean the number of times
a 1 is followed by a 0, or a 0 followed by a 1, eg the string 00111010 has
four changes, and the string 0000 has no changes. We ask: for two strings of
the same complexity value $k$, does the probability of an output decrease with
increasing numbers of 0/1 changes?

Figure 3 shows plots for the number of changes vs probability for each map. To
aid illustration in the figure, for each map we chose just a single complexity
value $k$, which was the second lowest of the output complexity value. The
reason for this choice is that LKLP behaviour is most pronounced for very low
complexities. For the FST, time series, and RNA there is a clear trend showing
an exponential decay in probability with increasing number of 0/1 changes. The
polynomial case does not show a trend, but on the other hand there are only
two value (2 and 3 changes) which makes observing a trend difficult.

The linear correlation and $p-$values for the trends are given here in the
format of complexity value, correlation coefficient, and $p-$value. For
brevity, values are only reported if either the $p$-value was statistically
significant (taken as $<0.05$) or the correlation coefficient $r$ was non-
trivial, taken here as $r<-0.4$. FST: $k=$14, $r$=-0.95, $p$-value=0.01;
$k=$17, $r$=-0.49, $p$-value=3e-05. Time series: $k=$12, $r$=-0.80,
$p$-value=3e-08; $k=$14, $r$=-0.44, $p$-value=1e-05; $k=$16, $r$=-0.42,
$p$-value=1e-14; $k=$18, $r$=-0.46, $p$-value=1e-50. RNA: $k=$19, $r$=-0.82,
$p$-value=0.002; $k=$22, $r$=-0.84, $p$-value=1e-06; $k=$24, $r$=-0.46,
$p$-value=3e-18; $k=$26, $r$=-0.46, $p$-value= 6e-38; $k=$29, $r$=-0.45,
$p$-value=2e-168. Polynomial: $k=$16, $r$=-0.95, $p$-value= 6e-51; $k=$22,
$r$=-0.70, $p$-value= 6e-321.

We conclude that a bias for or against changes is a simple mechanism that can
quickly lead to exponentially large variation in probabilities, for outputs
with the same informational complexity. Further, we tentatively conjecture
that in the natural data the bias is more likely to be against changes.

###  III.6 Bias for 1s or 0s

Another simple mechanism which might conceivably strongly affect probabilities
is a bias for or against 1’s or 0’s. In terms of information theory, 1’s and
0’s are given equal weighting, and all common complexity measures would assign
equal complexity to a string and to the same string but with the 0’s and 1’s
flipped, eg 010110 flipped to become 101001. Despite this, it is easy to
imagine that a natural system may have a bias for 1’s or 0’s, and hence the
symmetry in information between a string and its flipped counterpart would not
extend to a similarity in the probabilities of the two strings (Cf.
burkat2022note ). Further, if a discretisation such as converting a real-
valued time series into a binary string was performed, then how exactly this
was done could bias for 0’s or 1’s.

We investigate this potential bias in the four maps described above. Figure 4
shows the scatter plots for each map, with the number of 1’s in a string vs
the probability of the string. Again here just one complexity value $k$ for
each map is used; if there was no LKLP behaviour, then all strings would have
the same probability. The FST example in Figure 4(a) has clear bias against
1’s, with exponentially decaying probability with more and more 1’s. The time
series and polynomial data do not display a linear trend, but rather large and
small fractions of 1’s are associated with lower probabilities, which for the
time series can be expected from the way the discretisation was done. The
reason is less clear for the polynomial example. The RNA example has an
overall bias against 1’s, but it is not quite a linear trend. Based on these
few examples, there is no obvious common relation between the number of 1’s in
a string and its probability.

The linear correlation and $p-$value are given now, but only for correlations
that were both non-trivial and statistically significant. FST: $k$=14,
$r$=-0.95, $p$-value=0.01; $k=$17, $r$=-0.50, $p$-value=2e-05; $k=$22,
$r$=-0.41, $p$-value=4e-65. Time series: no linear relations. RNA: $k$=19,
$r$=-0.82, $p$-value=0.002; $k$=22, $r$=-0.84, $p$-value=1e-06; $k$=24,
$r$=-0.48, $p$-value=6e-20; $k$=26, $r$=-0.50, $p$-value=6e-45; $k$=29,
$r$=-0.47, $p$-value=2e-189. Polynomial: No linear correlations.

It seems that exponentially varying probability, unrelated to complexity, can
easily arise in natural systems from biases for 1’s or 0’s and/or changes and
oscillations. This helps to understand LKLP behaviour, but a full
understanding of the ubiquitous ‘triangle’ scatter plots we see arising from
SB remains to be determined.

##  IV Applying algorithmic probability

###  IV.1 Systems effectively equivalent to a UTM

Algorithmic probability has been applied or invoked in many different areas of
science and mathematics, where implicitly or explicitly the original coding
theorem involving a UTM is assumed. No physical computational system can
actualise a UTM in the strictest sense, because a UTM requires infinite
computational resources, including infinite memory and computation time, while
this is not possible in practice. Nonetheless, if a system is at least Turing
complete, and if a large memory resource is available which can be expanded as
needed, and ‘long’ computations are permitted, then the system can be
considered effectively equivalent to a UTM.

We have seen that for computable maps, low Kolmogorov complexity, low
probability (LKLP) outputs are ubiquitous and their existence can be
understood from a number of angles. While the original coding theorem in Eq.
(2) states a direct connection between Kolmogorov complexity and probability,
in applications of algorithmic probability to real world scenarios, if it is
known that the system under consideration is not effectively equivalent to a
UTM, then LKLP outputs should be expected.

Additionally, even if a system has this effective equivalence property and
hence has the ability to implement arbitrary algorithms, another issue is
whether or not it is reasonable to assume that the system is processing purely
random input programs (hence any conceivable algorithm might be implemented),
or instead is merely implementing some random inputs to some computable
functions for which LKLP outputs might be expected. (Indeed, whether the input
programs being processed are reasonably modelled as random at all is another
question.) For example, a desktop computer with a Turing complete language
compiler like Python is effectively equivalent to a UTM, but if the computer
is used to run RNA structure prediction with random RNA sequences, then we can
still expect that the outputs we are observing will show LKLP behaviour like
in Figure 1(c). In this scenario, the UTM-equivalent computational capacity of
the underlying system (ie the desktop computer) does not preclude LKLP
outputs, and is in a sense irrelevant. Even though the computer is effectively
a UTM, we do not expect to see patterns like the algorithmically simple digits
of $\pi$ (or perhaps even some non-pseudo random patterns) appearing with high
probability, because the programs sampled are not relevant to that type of
pattern.

###  IV.2 Two questions for physical systems

The preceding discussion suggests two questions in reference to when we expect
LKLP outputs: Is the physical system of interest likely to be effectively
equivalent to a UTM? If effectively UTM equivalent, is it reasonable to assume
that the physical system of interest is running random programs for which all
manner of algorithms might be computed, or instead computing only a small
fraction of computable algorithms?

Regarding the first question, the physical universe does support universal
computation, because it can (and is) performed within the universe. Moreover,
Wolfram (Chapter 12 of wolfram2002new ) has proposed the Principle of
Computational Equivalence which states that systems in nature which are not
obviously simple, eg the weather, have maximally possible computational power,
implying that many or even most natural systems operate effectively equivalent
to a UTM. Other work on undecidability in physics moore1990unpredictability ;
svozil1993randomness ; cubitt2015undecidability ; aguirre2021undecidability
and the computational capacity of physical world aaronson2005guest ;
zenil2013computable ; lloyd2006programming  may tend to support the
possibility of high-level computation in the natural world. Despite these
points, the Principle has not been proven to hold and it is not clear that it
does actually hold very commonly in nature.

Regarding the second question, there are many examples in nature of maps which
are clearly not performing arbitrary algorithms, but instead only performing a
narrow set of computable functions. In biology, the mapping from DNA sequence
programs to biological forms can often be modelled with computable
mathematical functions, and hence we can expect LKLP behaviour. Another
example: the time series pattern describing the daily temperature in London,
UK, over the year has been ‘computed’ from a variety of input factors such as
global air currents and cloud movements. But this computation is described by
computable mathematical functions (and some uncomputable random noise), and
hence we can expect LKLP behaviour if there is any SB in this system. It may
be that the weather system could in principe perform arbitrary computations,
but it is far from clear that it is actually doing this, and hence LKLP
behaviour might be expected.

Because computable maps abound in nature, and UTM-equivalent systems are not
obviously very common, and even if they are, do not commonly implement the
full range of possible algorithms, we suggest that LKLP behaviour should be
the default assumption in applications of algorithmic probability in real-
world settings. We now highlight a selection of applications of algorithmic
probability and see how or if LKLP behaviour is relevant.

###  IV.3 Explaining symmetry and simplicity in biology

It has recently been argued johnston2022symmetry  that a significant factor
causing the symmetry and simplicity in many biological forms (eg in large
symmetric biomolecules, petal arrangements in flowers) is due to simplicity
bias described by the upper bound in Eq. (3). This application of algorithmic
probability is unproblematic, because even in the presence of LKLP outputs,
there remains a bias towards simpler outputs.

###  IV.4 Time series prediction

The authors of ref. dingle2022note  invoked algorithmic probability and the
upper bound in Eq. (3) to make predictions about natural time series data
taken from the World Bank Open Data project (the example time series data set
described above was taken from their study). They proposed to make a kind of
‘forecasting without historical data’. In this prediction context, LKLP
outputs do cause a problem for prediction, because although the predicted
upper bound closely matches the upper bound of the data, the presence of LKLP
outputs imply that many series extrapolations will be predicted to have high
probability (on account of being simple) but in fact have low probability.
This amounts to a significant weakness in the prediction due to LKLP outputs.
A similar challenge to prediction accuracy may also affect the prediction-by-
compression of time series studied by Ryabko et al ryabko2016compression .

###  IV.5 What will I see next?

Müller muller2020law  has recently proposed a novel application of algorithmic
probability as a framework for addressing fundamental problems in theoretical
physics, such as why the universe obeys simple laws. He points out that many
problems in science and philosophy reduce to the question “ _What will I see
next?_ ”, and suggests that this single unified approach to framing questions
about the world also has a single unified approach to answering them in all
contexts uniformly, namely (conditional) algorithmic probability. To see how,
we briefly recap some relevant theory hutter2007algorithmic : the continuous
universal a priori probability $M(x)$ is defined as

$M(x)=\sum_{p:V(p)=x*}2^{-|p|}$ (4)

where $p$ is a program that runs on some UTM $V$ and produces an output string
which starts with $x$ and then continues (perhaps never halting), denoted by
$x*$. So $M(x)$ is the probability that an infinite string begins with $x$.
Now, $M(y|x):=M(xy)/M(x)$ provides a general method for predicting the
extrapolation $y$ given a history $x$. Further, Solomonoff showed that even if
$\mu$ is some computable (eg real world) probability distribution over binary
strings, then the conditional probability prediction problem $\mu(y|x)$ can be
estimated by $M(y|x)$, with $\mu$-probability 1 if $|x|\rightarrow\infty$ and
$\mu$ is low complexity computable function solomonoff1978complexity . We
point out that predictions based on $M(y|x)$ may be very inaccurate, ie
$M(y|x)\gg\mu(y|x)$, if $y$ may is a LKLP pattern, however.

Returning to the unified approach to framing questions about the world, Müller
takes as a starting point the assumption that there is only the state of the
observer (which is not fundamentally embedded into anything), and then
postulates that what happens next to that observer is dictated by algorithmic
probability. He goes on to show that this looks to the observer as if he/she
was embedded in some computable probabilistic world. Finally, assuming there
is an external world with computable laws within which the observer is
embedded, then it is proposed that algorithmic probability gives approximately
correct predictions for what the observer sees next, as indicated by the close
quantitative relation between $\mu(y|x)$ and $M(y|x)$.

Do LKLP outputs impact the stated goal to address a unified question in a
unified manner? Given that algorithmic probability was directly postulated
muller2020law  to be the best way to approach the question of “ _What will I
see next?_ ”, it is perhaps inappropriate to consider whether it is reasonable
to assume the presence of a UTM. Nonetheless it is worth noting that LKLP
outputs may be relevant if the manner in which the state of the observer is
updated is not in fact reasonably modelled as the result of (random) programs
fed into a system which is effectively equivalent to a UTM, but instead as
outputs from computable maps.

Müller also suggested that algorithmic probability helps to explain why we see
a “simple” world and physics laws. Even with LKLP behaviour, this argument
would still hold, because the simplicity bias upper bound still favours simple
(compressible) outcomes and extrapolations of historical patterns.

Somewhat related to the preceding, Lloyd lloyd2010computational  has argued
that quantum fluctuations act a random programs which are computed by the
universe, to produce complexity in the universe. Lloyd’s argument (which
invokes AIT) explicitly proposes that the universe acts as a computer; it
would be interesting to consider the implications (if any) for LKLP outputs
this perspective on the physical universe.

###  IV.6 Universal gambling

A universal gambling scheme which considers specific individual outcomes (and
explicitly was based on Kolmogorov complexity) was introduced by Cover
cover1974universal  in 1974, in which it was suggested that an investment
portfolio should be constructed while respecting probability predictions
essentially similar to algorithmic probability. In more detail, an investor
having observed a binary string financial time series $x_{1}x_{2}\dots x_{i}$
for some index $i$, in predicting whether the next bit will be a 0, the
formula Cover suggested was $p(0)=2^{l(x_{1}x_{2}\dots
x_{i}0)}$/$2^{l(x_{1}x_{2}\dots x_{i})}$, and $p(1)$ is similarly defined. In
this formula $l(z)$ measures the minimum codelength for some string $z$, which
is fundamentally the same notion as the Kolmogorov complexity of $z$, which
appears in the coding theorem.

It seems reasonable to assume that the natural context for applying this
universal gambling strategy, that is time series in financial markets, are not
the result of UTMs but rather some computable processes. Hence it seems likely
that LKLP behaviour would be a challenge for the strategy, due to the
possibility that for example $x_{1}x_{2}\dots x_{i}0$ might be simpler than
$x_{1}x_{2}\dots x_{i}1$ but due to LKLP behaviour, the latter is more likely.
We are not saying that the gambling scheme is invalid, just that its efficacy
would be reduced somewhat in the presence of LKLP outputs.

###  IV.7 Solomonoff induction and Occam’s razor

Occam’s razor is a fundamental principle of scientific reasoning, philosophy,
and model selection hansen2001model  stating that simpler explanations or
models should take preference over more complex ones sep-simplicity . Despite
its wide application and common sense appeal, a formal grounding for this
principle has been a challenge for philosophy. Solomonoff introduced the idea
of algorithmic probability in the 1960’s li2008introduction ;
solomonoff2009algorithmic  as part of an investigation into induction, and it
has been argued that his formal method of induction has solved the long-
standing philosophical problem of why simpler explanations should be preferred
vallinder2012solomonoff ; kirchherr1997miraculous ;
rathmanner2011philosophical . Solomonoff’s basic argument is that because
simple hypotheses/explanations are a priori more likely to appear from a
random program running on a UTM, then given some observed data the simplest
hypothesis/explanation should have the highest probability and hence should be
preferred (assuming it explains some observed data as well as another
competing hypothesis).

Does LKLP behaviour affect the applicability of Solomonoff induction to the
real world? If we assume that the contexts within which induction is to be
made — presumably the physical world — result from random programs fed into a
UTM, then LKLP do not even exist. However, as discussed above it seems
reasonable to assume that the physical world is the result of computable
physical laws and therefore we can expect (many) LKLP outputs. Solomonoff
induction is premised on the fact that a given simple pattern (hypothesis) is
a priori more likely than some other given more complex one, and interestingly
this property still holds albeit in a weaker sense, even with LKLP outputs.

Recall that we saw above (Section III.2) when predicting whether $x$ or $y$ is
more likely, that for both probability-weighted and uniform sampling simpler
strings tend to have higher probability. However, because uniform sampling the
prediction accuracy is low, eg 63% for uniform sampling with the FST, this
suggests that while Solomonoff induction is still valid in LKLP settings, it
is less likely to to lead to correct induction as compared to in the UTM
setting for which complexity and probability is much more closely connected.
Therefore a challenge to applying Solomonoff induction in the real world is
faced because when weighing up two hypotheses $H_{1}$ and $H_{2}$ that both
explain the observed data, $H_{1}$ may be simpler than $H_{2}$, but perhaps
$H_{1}$ is a LKLP output and hence much less likely than $H_{2}$. By
extension, there is a challenge to justifying Occam’s razor in the real
physical world — it is still valid even with LKLP, but the argument for
preferring simpler hypotheses is somewhat weakened.

Relatedly, Hutter has formed a universal theory of artificial intelligence
based on algorithmic probability and Solomonoff induction hutter2004universal
(see also Legg and Veness legg2011approximation  for a numerical
implementation of the theory). The implications of LKLP outputs for this
research project will be similar to those for Occam’s razor, namely if the
intelligent agent is making observations resulting from an environment that is
known to generated by a computable map, then it is still true that often a
given simpler hypothesis is a priori more likely than some given complex
hypothesis, but not that rarely the reverse is true. Hence in the computable
setting it may be that this form of induction is less likely to to lead to
correct predictions as compared to the UTM setting.

###  IV.8 DNN generalisation

Another recent and important application of simplicity bias is in machine
learning, where it has been argued valle2018deep  that the surprising
generalisation ability of deep neural networks (DNN) is due in part to the
fact that DNN are biased towards simple functions (by invoking Eq. (3)), and
natural functions are also biased towards simple functions, so the problem of
learning functions is significantly easier than it would be if there was no
simplicity bias in functions. Because LKLP behaviour is also found in DNN
valle2018deep , and LKLP has been observed in so many other natural settings,
this raises a question: does LKLP behaviour create a challenge for this
invocation of algorithmic probability? One way to look at this is to ask, do
the simple functions in nature coincide with the simple functions towards
which the DNN are biased? Without LKLP outputs in either DNN or nature, they
would automatically coincide, but this is no longer automatic given that LKLP
outputs exist. If the natural functions are highly probable simple functions
but different to the highly probable functions that DNN produce (or at least
not a subset of these functions) then the argument for why DNN generalise is
weaker. On the other hand, if highly probable natural functions do coincide
(or are at least a subset) of the highly probable functions generated by DNN
then it would be interesting to consider why this is. This question relates to
our earlier question regarding whether there might be common patterns to which
types of outputs are LKLP: if different maps or systems have completely
unrelated LKLP patterns, then an overlap between different systems is less
likely as compared to if there are more general typical patterns across
different systems.

###  IV.9 Password guessing

Although not based on Kolmogorov complexity and Levin’s Eq. (2), an
essentially very similar probability prediction method has been derived by
workers in information theory. Merhav and Feder merhav1998universal  point out
in an influential review of _universal prediction_ that $2^{-LZ(x)}$ is a
universal probability assignment for prediction, citing the work of ref.
plotnik1992upper  and others. In this context, $LZ(x)$ is the Lempel-Ziv
compression complexity measure, which is very similar to the measure used in
most studies of SB. Merhav and Cohen merhav2019universal  have recently used
this $2^{-LZ(x)}$ universal probability predictor in a cryptography setting,
where they suggested that it forms an optimal method for guessing passwords.
It would be interesting to investigate any examples of LKLP passwords. If they
did occur, then they might represent a source of wasted guesses of the
guessing strategy, because the strategy would assign a high probability of
$\sim 2^{-LZ(x)}$ to some password $x$, which is in fact very rarely used as a
password by people.

##  V Discussion

We have investigated the occurrence of low Kolmogorov complexity, low
probability (LKLP) outputs in computable functions with randomly sampled
inputs. The central messages are that (a) LKLP outputs have been observed in
essentially all maps for which simplicity bias (SB) has been studied; (b) LKLP
outputs are expected in computable maps for theoretical reasons; (c) there
appears to be some common statistical patterns to the distributions of the
LKLP outputs which form a kind of ‘triangle’ shape in probability-complexity
plots; and (d) when applying algorithmic probability in real world
applications, LKLP outputs should be the default expectation unless there is
good reason to expect that the outputs are indeed generated by purely random
programs fed into a universal Turing machine (UTM), which we suggest is
probably an uncommon scenario in science, engineering, finance, etc. Further,
we briefly surveyed some works in which algorithmic probability in some form
has been invoked, and discussed some possible implications of LKLP outputs,
including studies of a priori predictions, Solomonoff induction and Occam’s
razor. The main LKLP implication is that the connection between complexity and
probability is considerably less strong, as compared to in the original
algorithmic information theory (AIT) coding theorem.

A main motivation for this study is developing theory for improved a priori
probability predictions. The AIT coding theorem states that output
probabilities can be directly found via the Kolmogorov complexity of the
output, rather than, say, using historical frequency statistics to estimate
probabilities. In earlier work dingle2018input  a practical weaker version of
this AIT coding theorem was presented, in the form of an upper bound on
probabilities, rather than a direct estimate of probabilities. Understanding
the causes and nature of LKLP outputs which fall far below the upper bound may
help to improve predictions of the probabilities of those outputs, and hence a
stronger theory of a priori probability predictions may be laid out.

Although algorithmic probability was originally formulated in the context of
random algorithms/programs that generate outputs via a computer, we stress
that algorithmic probability estimates — especially the upper bound of Eq. (3)
— are not limited to what are usually understood as algorithms per se. Instead
these estimates can be applied to a wide range of problems for which output
patterns result from mathematical functions with some form of input
parameters. For example, the parameters of a large ordinary differential
equation system are not usually understood as an ‘algorithm’ for the solution
profile, nonetheless the upper bound has been shown to predict the probability
of outputs in such systems dingle2018input ; johnston2022symmetry . Even more
distant from a computer running a program, the upper bound has been shown to
work well in predicting natural time series patterns dingle2022note  for which
both the notion of program and computer is much less clearly defined.

There has been a lot of discussion in the statistics and philosophy
communities regarding how to choose a Bayesian prior, and AIT promises to be
one way to address this hutter2007universal . Our work here is directly
relevant to making practical implementations of this AIT answer to the
Bayesian prior question.

Several open question remain. In general, how can we better understand the
causes and nature of LKLP outputs? Given a small sample of outputs, can these
be used to predict which outputs are likely to be LKLP, and which are likely
to be close to the bound? Why is it that the data points form ‘triangles’ in
Figure 1 and other simplicity bias studies? Are there common patterns across
different system dictating which outputs will be LKLP? How can we best
incorporate simplicity bias probability predictions into other probability
estimation approaches, such as machine learning?

Acknowledgements: KD acknowledges financial support from the Gulf University
for Science and Technology Seed Grant (grant number 234271). We thank Paris
Flood, Iain Johnston, Ard Louis, Nora Martin, Christopher Mingard, and Markus
Müller for valuable discussions and suggestions related to this work.

Data availability: The data sets generated during and analysed during the
current study are available from the corresponding authors on request.

Author contributions: MA performed the numerical calculations. KD conceived
the study and wrote the paper.

## References

  * [1] R. J. Solomonoff.  A preliminary report on a general theory of inductive inference (revision of report v-131).  Contract AF, 49(639):376, 1960.
  * [2] A.N. Kolmogorov.  Three approaches to the quantitative definition of information.  Problems of information transmission, 1(1):1–7, 1965.
  * [3] Gregory J Chaitin.  A theory of program size formally identical to information theory.  Journal of the ACM (JACM), 22(3):329–340, 1975.
  * [4] M. Li and P.M.B. Vitanyi.  An introduction to Kolmogorov complexity and its applications.  Springer-Verlag New York Inc, 2008.
  * [5] L.A. Levin.  Laws of information conservation (nongrowth) and aspects of the foundation of probability theory.  Problemy Peredachi Informatsii, 10(3):30–35, 1974.
  * [6] Ray J Solomonoff.  The kolmogorov lecture the universal distribution and machine learning.  The Computer Journal, 46(6):598–601, 2003.
  * [7] Kamaludin Dingle, Guillermo Valle Pérez, and Ard A Louis.  Generic predictions of output probability based on complexities of inputs and outputs.  Scientific reports, 10(1):1–9, 2020.
  * [8] Kamaludin Dingle, Rafiq Kamal, and Boumediene Hamzi.  A note on a priori forecasting and simplicity bias in time series.  arXiv preprint arXiv:2203.05391, 2022.
  * [9] Kamaludin Dingle, Chico Q Camargo, and Ard A Louis.  Input–output maps are strongly biased towards simple outputs.  Nature communications, 9(1):761, 2018.
  * [10] R. Cilibrasi and P.M.B. Vitányi.  Clustering by compression.  Information Theory, IEEE Transactions on, 51(4):1523–1545, 2005\.
  * [11] P. Ferragina, R. Giancarlo, V. Greco, G. Manzini, and G. Valiente.  Compression-based classification of biological sequences and structures via the universal similarity metric: experimental assessment.  BMC bioinformatics, 8(1):252, 2007.
  * [12] Ram Avinery, Micha Kornreich, and Roy Beck.  Universal and accessible entropy estimation using a compression algorithm.  Physical review letters, 123(17):178102, 2019.
  * [13] Paul MB Vitányi.  Similarity and denoising.  Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 371(1984), 2013.
  * [14] Shane Legg and Joel Veness.  An approximation of the universal intelligence measure.  arXiv preprint arXiv:1109.5951, 2011.
  * [15] J.P. Delahaye and H. Zenil.  Numerical evaluation of algorithmic complexity for short strings: A glance into the innermost structure of algorithmic randomness.  Appl. Math. Comput., 219:63–77, 2012.
  * [16] Fernando Soler-Toscano, Hector Zenil, Jean-Paul Delahaye, and Nicolas Gauvrit.  Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines.  PloS one, 9(5):e96223, 2014.
  * [17] Hector Zenil, Liliana Badillo, Santiago Hernández-Orozco, and Francisco Hernández-Quiroz.  Coding-theorem like behaviour and emergence of the universal distribution from resource-bounded algorithmic probability.  International Journal of Parallel, Emergent and Distributed Systems, 34(2):161–180, 2019.
  * [18] C.S. Calude.  Information and randomness: An algorithmic perspective.  Springer, 2002.
  * [19] P. Gács.  Lecture notes on descriptional complexity and randomness.  Boston University, Graduate School of Arts and Sciences, Computer Science Department, 1988.
  * [20] Alan Mathison Turing.  On computable numbers, with an application to the entscheidungsproblem.  J. of Math, 58(345-363):5, 1936.
  * [21] Peter Grunwald and Paul Vitányi.  Shannon information and Kolmogorov complexity.  arXiv preprint cs/0410002, 2004.
  * [22] Ray J Solomonoff.  Algorithmic probability: Theory and applications.  In Information theory and statistical learning, pages 1–23. Springer, 2009.
  * [23] A. Lempel and J. Ziv.  On the complexity of finite sequences.  Information Theory, IEEE Transactions on, 22(1):75–81, 1976.
  * [24] Ronny Lorenz, Stephan H Bernhart, Christian Höner Zu Siederdissen, Hakim Tafer, Christoph Flamm, Peter F Stadler, and Ivo L Hofacker.  Viennarna package 2.0.  Algorithms for molecular biology, 6(1):26, 2011.
  * [25] Mark H Hansen and Bin Yu.  Model selection and the principle of minimum description length.  Journal of the American Statistical Association, 96(454):746–774, 2001.
  * [26] K. Willbrand, F. Radvanyi, J.P. Nadal, J.P. Thiery, and T.M.A. Fink.  Identifying genes from up–down properties of microarray expression series.  Bioinformatics, 21(20):3859–3864, 2005.
  * [27] Iain G Johnston, Kamaludin Dingle, Sam F Greenbury, Chico Q Camargo, Jonathan PK Doye, Sebastian E Ahnert, and Ard A Louis.  Symmetry and simplicity spontaneously emerge from the algorithmic nature of evolution.  Proceedings of the National Academy of Sciences, 119(11):e2113883119, 2022.
  * [28] Guillermo Valle-Perez, Chico Q Camargo, and Ard A Louis.  Deep learning generalizes because the parameter-function map is biased towards simple functions.  arXiv preprint arXiv:1805.08522, 2018.
  * [29] Kamaludin Dingle.  Probabilistic bias in genotype-phenotype maps.  PhD thesis, University of Oxford, 2014.
  * [30] Jan Leike and Marcus Hutter.  Bad universal priors and notions of optimality.  In Conference on Learning Theory, pages 1244–1259. PMLR, 2015.
  * [31] Markus Müller.  Stationary algorithmic probability.  Theoretical Computer Science, 411(1):113–130, 2010.
  * [32] SF Greenbury and Sebastian Edmund Ahnert.  The organization of biological sequences into constrained and unconstrained parts determines fundamental properties of genotype–phenotype maps.  Journal of The Royal Society Interface, 12(113):20150724, 2015.
  * [33] Jedrzej Burkat and Kamaludin Dingle.  A note on simplicity bias in the bernoulli process.  In preparation, 2022.
  * [34] S. Wolfram.  A New Kind of Science.  Wolfram Media, 2002.
  * [35] Cristopher Moore.  Unpredictability and undecidability in dynamical systems.  Physical Review Letters, 64(20):2354, 1990.
  * [36] Karl Svozil.  Randomness & undecidability in physics.  World Scientific, 1993.
  * [37] Toby S Cubitt, David Perez-Garcia, and Michael M Wolf.  Undecidability of the spectral gap.  Nature, 528(7581):207–211, 2015.
  * [38] Anthony Aguirre, Zeeya Merali, and David Sloan.  Undecidability, uncomputability, and unpredictability, 2021.
  * [39] Scott Aaronson.  Guest column: Np-complete problems and physical reality.  ACM Sigact News, 36(1):30–52, 2005.
  * [40] Hector Zenil.  A computable universe: understanding and exploring nature as computation.  World Scientific, 2013.
  * [41] Seth Lloyd.  Programming the universe: a quantum computer scientist takes on the cosmos.  Vintage, 2006.
  * [42] Boris Ryabko, Jaakko Astola, and Mikhail Malyutov.  Compression-based methods of statistical analysis and prediction of time series.  Springer, 2016.
  * [43] Markus P Müller.  Law without law: from observer states to physics via algorithmic information theory.  Quantum, 4:301, 2020.
  * [44] Marcus Hutter, Shane Legg, and Paul MB Vitanyi.  Algorithmic probability.  Scholarpedia, 2(8):2572, 2007.
  * [45] Ray Solomonoff.  Complexity-based induction systems: comparisons and convergence theorems.  IEEE transactions on Information Theory, 24(4):422–432, 1978.
  * [46] Seth Lloyd.  The computational universe.  Information and the nature of reality: From physics to metaphysics, pages 92–103, 2010.
  * [47] TM Cover.  Universal gambling schemes and the complexity measures of kolmogorov and chaitin. rep. no. 12, statistics dep, 1974.
  * [48] Alan Baker.  Simplicity.  In Edward N. Zalta, editor, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Winter 2016 edition, 2016.
  * [49] Aron Vallinder.  Solomonoff induction: A solution to the problem of the priors?  2012\.
  * [50] WW Kirchherr, M Li, PMB Vitanyi, et al.  The miraculous universal distribution.  Mathematical Intelligencer, 1997.
  * [51] Samuel Rathmanner and Marcus Hutter.  A philosophical treatise of universal induction.  Entropy, 13(6):1076–1136, 2011.
  * [52] Marcus Hutter.  Universal artificial intelligence: Sequential decisions based on algorithmic probability.  Springer Science & Business Media, 2004.
  * [53] Neri Merhav and Meir Feder.  Universal prediction.  IEEE Transactions on Information Theory, 44(6):2124–2147, 1998\.
  * [54] Eli Plotnik, Marcelo J Weinberger, and Jacob Ziv.  Upper bounds on the probability of sequences emitted by finite-state sources and on the redundancy of the lempel-ziv algorithm.  IEEE transactions on information theory, 38(1):66–72, 1992.
  * [55] Neri Merhav and Asaf Cohen.  Universal randomized guessing with application to asynchronous decentralized brute–force attacks.  IEEE Transactions on Information Theory, 66(1):114–129, 2019.
  * [56] Marcus Hutter.  On universal prediction and bayesian confirmation.  Theoretical Computer Science, 384(1):33–48, 2007.