11institutetext:  Instituto de Astrofísica e Ciências do Espaço, Faculdade de
Ciências da Universidade de Lisboa,
Campo Grande, PT1749-016 Lisboa, Portugal,22institutetext: Departamento de
Física da Faculdade de Ciências da Universidade de Lisboa, Edifício C8,
1749-016 Lisboa, Portugal33institutetext: ECEO, Universidade Lusófona de
Humanidades e Tecnologias, Campo Grande, 376, 1749-024 Lisboa,
Portugal44institutetext: INAF – Osservatorio Astronomico di Trieste, via G. B.
Tiepolo 11, I-34143 Trieste, Italy55institutetext: Institute for Fundamental
Physics of the Universe, Via Beirut 2, I-34151 Miramare, Trieste,
Italy66institutetext: Instituto de Astrofísica de Canarias (IAC), Calle Vía
Láctea s/n, E-38205 La Laguna, Tenerife, Spain77institutetext: Departamento de
Astrofísica, Universidad de La Laguna (ULL), E-38206 La Laguna, Tenerife,
Spain88institutetext: Instituto de Astrofísica e Ciências do Espaço, CAUP,
Universidade do Porto, Rua das Estrelas, 4150-762, Porto,
Portugal99institutetext: Centro de Astrofísica da Universidade do Porto, Rua
das Estrelas, 4150-762 Porto, Portugal1010institutetext: Faculdade de Ciências
e Tecnologia, Universidade Nova de Lisboa, 2829-516 Caparica,
Portugal1111institutetext: Istituto Nazionale di Fisica Nucleare, Sezione di
Trieste, Via Bonomea 265, 34136 Trieste, Italy1212institutetext: Centre for
Astrophysics and Supercomputing, Swinburne University of Technology, Hawthorn,
Victoria 3122, Australia1313institutetext: Observatoire Astronomique de
l’Université de Genève, Chemin Pegasi 51, Sauverny 1290,
Switzerland1414institutetext: Departamento de Física e Astronomia, Faculdade
de Ciências, Universidade do Porto,
Rua Campo Alegre, 4169-007, Porto, Portugal1515institutetext: INAF –
Osservatorio Astrofisico di Torino, via Osservatorio 20, 10025 Pino Torinese,
Italy1616institutetext: Centro de Astrobiología (CSIC-INTA), Crta. Ajalvir km
4, E-28850 Torrejón de Ardoz, Madrid, Spain

# Fundamental physics with ESPRESSO: Constraining a simple parametrisation for
varying $\alpha$

Vitor da Fonseca 1122 Tiago Barreiro 1133 Nelson J. Nunes 1122 Stefano
Cristiani 4455 Guido Cupani 4455
Valentina D’Odorico 4455 Ana C. O. Leite 8899 Catarina M. J. Marques 101099
Carlos J. A. P. Martins 8899 Dinko Milaković 44551111 Paolo Molaro 4455
Michael T. Murphy 121255 Tobias M. Schmidt 131344 Manuel Abreu 1122 Vardan
Adibekyan 881414 Alexandre Cabral 1122 Paolo Di Marcantonio 44
Jonay I. González Hernández 6677 Enric Palle 6677 Francesco A. Pepe 1313
Rafael Rebolo 6677 Nuno C. Santos 881414
Sérgio G. Sousa 881414 Alessandro Sozzetti 1515 Alejandro Suárez Mascareño
6677 Maria-Rosa Zapatero Osorio 1616

###### Abstract

Context. The spectrograph ESPRESSO recently obtained a limit on the variation
of the fine-structure constant, $\alpha$, through measurements along the line
of sight of a bright quasar with a precision of $1.36$ ppm at $1\sigma$ level.
This imposes new constraints on cosmological models with a varying $\alpha$.
We assume such a model where the electromagnetic sector is coupled to a scalar
field dark energy responsible for the current acceleration of the Universe. We
parametrise the variation of $\alpha$ with two extra parameters, one defining
the cosmological evolution of the quintessence component and the other fixing
the coupling with the electromagnetic field.

Aims. The objective of this work is to constrain these parameters with both
astrophysical and local probes. We also carried out a comparative analysis of
how each data probe may constrain our parametrisation.

Methods. We performed a Bayesian analysis by comparing the predictions of the
model with observations. The astrophysical datasets are composed of quasar
spectra measurements, including the latest ESPRESSO data point, as well as
Planck observations of the cosmic microwave background. We combined these with
local results from atomic clocks and the MICROSCOPE experiment.

Results. The constraints placed on the quintessence parameter are consistent
with a null variation of the field, and are therefore compatible with a
$\Lambda$CDM cosmology. The constraints on the coupling to the electromagnetic
sector are dominated by the Eötvös parameter local bound.

Conclusions. More precise measurements with ESPRESSO will be extremely
important to study the cosmological evolution of $\alpha$ as it probes an
interval of redshift not accessible to other types of observations. However,
for this particular model, current available data favour a null variation of
$\alpha$ resulting mostly from the strong MICROSCOPE limits.

###### Key Words.:

Dark Energy, variation of the fine-structure constant

##  1 Introduction

Like the other fundamental constants in physics, the value of the fine-
structure constant, $\alpha\equiv e^{2}/\hbar c$, which defines the strength
of the electromagnetic interaction, is only determined through experimental
measurements in the absence of theoretical predictions. While $\alpha$ has
been measured in the lab with extremely high precision, whether or not it
varies in space or time is still unknown. The detection of any variation would
open prospects beyond the standard model of particle physics (Uzan, 2011).

Locally, strong constraints are obtained on the drift rate of the fine-
structure constant by comparing pairs of atomic clocks. The experiments are
based on the fact that atomic transitions have a frequency that manifests a
different dependency on the value of $\alpha$. Usually, various transitions
are measured in different atoms over a given time span. However, Lange et al.
(2021) obtained the most stringent limit on a temporal drift of the fine-
structure constant by comparing two different transition frequencies provided
by the same ytterbium ion over a period of about 4 years. The authors improved
the limits for the temporal variations of $\alpha$ to $1.0(1.1)\times
10^{-18}/$yr.

On cosmological timescales, the observation of distant quasi-stellar object
(QSO) spectra has proven beneficial for testing the stability of the fine-
structure constant for more than 20 years. The measurements of absorption
lines provide a means to directly determine $\alpha$ in intervening
extragalactic gas clouds that correspond to different look-back times. Data
from Keck/HIRES suggested that $\alpha$ was smaller in the past at redshift
$0.5<z<3$ (Webb et al., 2001; Murphy et al., 2003) whereas an initial analysis
of observations from the southern hemisphere with VLT/UVES did not find any
indication of such fluctuation (Chand et al., 2004). However, a re-analysis of
the UVES spectra, which corrected the absorption-profile-fitting procedure,
produced results consistent with the Keck ones (Murphy et al., 2007, 2008);
though see also Srianand et al. (2007). Subsequent analysis of archival data
from both HIRES and UVES spectrographs successfully reconciled the results
from the two hemispheres by invoking possible spatial variation of the fine-
structure constant across the sky (Webb et al., 2011; King et al., 2012).
Nevertheless, the Keck and VLT spectra suffer from wavelength calibration
errors that undermine the conclusions (Whitmore & Murphy, 2014). In contrast
to the archival data, which was not collected for the specific purpose of
measuring $\alpha$, recent dedicated measurements made with UVES and HIRES
that mitigate wavelength calibration errors are compatible with the null
result (Martins, 2017; Martins & Vila Miñana, 2019; Martins et al., 2022).

It is in this context of technical challenges and stimulating controversies
that the spectrograph ESPRESSO (Pepe et al., 2021) for the VLT was designed
with the specific aim of testing the fine-structure constant stability, unlike
the older high-resolution spectrographs. A highly stabilised environment, the
fibre feed, and the possibility of calibration with a femtosecond-pulsed laser
frequency comb (LFC) make it possible to accurately measure the absorption
features with an exquisite control of systematic errors, effectively removing
wavelength calibration from the error budget. The first ESPRESSO measurements
provide a new constraint on relative variations in $\alpha$, namely
$\Delta\alpha/\alpha=1.31\pm 1.36$ ppm at redshift $z=1.15$, which is
consistent with no cosmological variation (Murphy et al., 2022). Nevertheless,
this additional result is useful for further testing of cosmological models
that predict varying fundamental constants.

This paper considers one particular class of these models, where the dark-
energy component is in the form of quintessence assumed to be non-minimally
coupled to the electromagnetic sector (see Martins, 2017). Indeed, almost
massless scalar fields necessarily couple to matter, provided that the
coupling is not suppressed by a symmetry (Carroll, 1998). The theory supposes
a varying fine-structure constant by coupling the scalar field, $\phi$, to the
electromagnetic Faraday tensor as $B_{F}(\phi)F_{\mu\nu}F^{\,\mu\nu}$, where
$B_{F}$ is the so-called gauge kinetic function (Bekenstein, 1982; Copeland et
al., 2004). Accordingly, the fine-structure constant evolves as $\alpha\propto
B_{F}^{-1}(\phi)$, and therefore depends on the value of the scalar field
which is responsible for the late time acceleration of the Universe expansion
(Riess et al., 1998; Perlmutter et al., 1999). Our aim is to constrain our
model with the help of various observational datasets. To this end, we assume
a linear dependency of the gauge kinetic function on the scalar field, such
that $B_{F}(\phi)=1-\zeta\kappa(\phi-\phi_{0})$, where $\zeta$ is the coupling
constant. Moreover, we use a simple parametrisation for dark energy where the
scalar field linearly scales with the number of e-folds (Nunes & Lidsey,
2004), $\phi^{\prime}=\lambda$, for some constant $\lambda$ (the prime denotes
the derivative with respect to the number of e-folds). The two slopes $\zeta$
and $\lambda$ of the linear dependencies are free parameters of the model.

We made a joint constraint of the two parameters with data from both QSO
spectral lines and atomic clocks, although they can also be separately
constrained. As the light scalar field couples to matter, it entails the
violation of the universality of free fall (Damour & Donoghue, 2010). This
kind of model is therefore extremely constrained from the bound on the weak
equivalence principle (WEP). The level of WEP violation can be quantified with
the Eötvös parameter $\eta$ which relates to $\zeta$ in a model-dependent way
(Carroll, 1998; Dvali & Zaldarriaga, 2002; Chiba & Kohri, 2002). We made use
of the bound on $\eta$ obtained with the MICROSCOPE space mission
(MICROSatellite pour l’Observation du Principe d’Equivalence) in Touboul et
al. (2019) to individually constrain $\zeta$. The MICROSCOPE experiment is
designed to confirm the equivalence between inertial mass and gravitational
mass by observing the free-fall motion of two masses —made of two different
materials— sourced by the Earth’s gravitational field. For $\lambda$, we used
a distance prior based on existing cosmic microwave background (CMB)
constraints for dark energy. This prior imposes stringent cosmological limits
on the evolution of the scalar field from a high-redshift probe.

##  2 Description of a varying $\alpha$ cosmological model

We choose to extend the spatially flat $\Lambda$CDM model by generalising the
cosmological constant $\Lambda$ with a varying canonical and homogeneous
scalar field accounting for dark energy; the scalar field is minimally coupled
to gravity but non-minimally coupled to the electromagnetic field. Assuming
the same matter Lagrangian, $\mathcal{L}_{M}$, as in the standard model
composed of radiation, baryons, and cold dark matter, the overall action that
characterises this theory is given by

$S=-\frac{1}{2\kappa^{2}}\int
R\sqrt{-g}\,d^{\,4}x+\int\left(\mathcal{L}_{M}+\mathcal{L}_{\phi}+\mathcal{L}_{\phi
F}\right)\sqrt{-g}\,d^{\,4}x\,,$ (1)

where $R$ is the Ricci scalar, $g$ is the determinant of the metric
$g_{\mu\nu}$ , and $\kappa^{2}\equiv 8\pi G/c^{4}$ is the gravitational
coupling constant. The Lagrangian density for the quintessence component is
given by

$\mathcal{L}_{\phi}=\frac{1}{2}\partial^{\,\mu}\phi\partial_{\mu}\phi-V\left(\phi\right)\,,$
(2)

while its interaction with the electromagnetic field is represented by the
following Lagrangian density:

$\mathcal{L}_{\phi
F}=-\frac{1}{4}B_{F}\left(\phi\right)F_{\mu\nu}F^{\,\mu\nu}\,,$ (3)

where $V(\phi)$ is the potential of the scalar field, $F_{\mu\nu}$ is the
strength of the electromagnetic field, and $B_{F}(\phi)$ is the gauge kinetic
function which defines the coupling between dark energy and the
electromagnetic sector. In this model, the coupling imposes the variation of
the fine-structure constant whose cosmological evolution is given by

$\alpha\left(\phi\right)=\alpha_{0}B_{F}^{-1}\left(\phi\right)\,,$ (4)

where $\alpha_{0}\approx 1/137$ is the present-day value. As the possible
variations in $\alpha$ are necessarily small, one can harmlessly assume that
the Taylor expansion of $B_{F}(\phi)$ at first order is valid on cosmological
timescales,

$B_{F}\left(\phi\right)=1-\zeta\kappa\left(\phi-\phi_{0}\right)\,,$ (5)

where $\phi_{0}$ is the field present value and $\zeta$ is a dimensionless
constant that parametrises the linear dependency of the gauge kinetic function
on the scalar field. It follows from Eq. (4) that $\zeta$ is also the slope of
the linear dependency of the effective fine-structure constant on the scalar
field,

$\frac{\Delta\alpha}{\alpha}\equiv\frac{\alpha-\alpha_{0}}{\alpha_{0}}=\zeta\kappa\left(\phi-\phi_{0}\right)\,.$
(6)

For testing this model, we use the parametrisation for dark energy of Nunes &
Lidsey (2004) where quintessence scales with the number of e-folds,
$N\equiv\ln a$,

$\kappa\left(\phi-\phi_{0}\right)=\lambda N\,,$ (7)

for a given constant $\lambda$. Logarithmic dependencies on the scale factor
exist in dilaton-type models inspired by string theories in which $\lambda$
has different values in the acceleration, matter, and radiation eras (Damour
et al., 2002). The scalar field potential, $V(\phi)$, derived in Nunes &
Lidsey (2004), takes the form of a double exponential which is able to bring
the Universe towards its late time acceleration almost irrespectively of the
initial conditions (Barreiro et al., 2000):

$V\left(\phi\right)=A\,e^{-\frac{3}{\lambda}\kappa\phi}+B\,e^{-\lambda\kappa\phi}\,,$
(8)

where the mass scales $A$ and $B$, normalised to $\phi_{0}=0$, are completely
fixed by the cosmological parameters

$\displaystyle A$
$\displaystyle=\frac{\lambda^{2}}{3-\lambda^{2}}\frac{3H_{0}^{2}}{2\kappa^{2}}\,\Omega_{m},$
(9) $\displaystyle B$
$\displaystyle=\frac{\lambda^{2}-6}{3-\lambda^{2}}\,\frac{3H_{0}^{2}}{2\kappa^{2}}\left(\frac{\lambda^{2}}{3}-1+\Omega_{m}\right)\,,$
(10)

where $H_{0}$ and $\Omega_{m}$ are respectively the current Hubble expansion
rate and today’s abundance of matter.

We were motivated in the choice of this parametrisation by the fact that it
appropriately helps to constrain the dark energy equation of state, $w$. It
also captures a wide range of evolution at low redshift with only one extra
degree of freedom (da Fonseca et al., 2022). In this respect, it usefully
complements the familiar CPL parametrisation (Chevallier & Polarski, 2001;
Linder, 2003). Our additional parameter $\lambda$ sets today’s dark energy
equation of state:

$w_{0}=-1+\frac{\lambda^{2}}{3\left(1-\Omega_{m}\right)}\,.$ (11)

This dark energy parametrisation possesses a $\Lambda$CDM limit when
$w_{0}\rightarrow-1$ for $\lambda\rightarrow 0$ , allowing a direct test of
departures from the concordance model. At higher redshift, during matter
domination, $w\rightarrow 0$, making it by construction a well-behaved model
(see Nunes, 2004). According to the parametrisation, the cosmological
variation of $\alpha$ in Eq. (6) becomes

$\frac{\Delta\alpha}{\alpha}=\zeta\lambda\ln
a=-\zeta\lambda\ln\left(1+z\right)\,.$ (12)

Thus we obtain a model in which the relative variation in $\alpha$ scales with
the number of e-folds, the amplitude of the linear dependency being the
product of the two additional parameters, $\zeta\lambda$. The value of the
fine-structure constant therefore logarithmically depends on redshift. This
model only adds two extra degrees of freedom to the standard model, limiting
the degeneracies between cosmological parameters. As the two parameters are
perfectly degenerated, we constrain the model in the following section by
adding priors and external datasets to the observations that specifically
constrain $\Delta\alpha/\alpha$.

##  3 Selection of observational data to constrain the model

Two observables sensitive to the product $\zeta\lambda$ are available to
constrain the two parameters jointly. Firstly, the predictions of Eq. (12) can
be compared to astrophysical measurements in extragalactic clouds based on QSO
absorption spectra, and secondly, we used the current drift rate of the fine-
structure constant constrained by atomic clocks.

Table 1: QSO dataset. The first column is the name of the source,
$z_{\textrm{abs}}$ is the absorber redshift of the measurement along the line
of sight, $\Delta\alpha/\alpha$ is the respective measured variation of the
fine-structure constant in parts per million (ppm), with the corresponding
quadrature sum of statistical uncertainty and systematic error ($1\sigma$).
The two last columns give respectively the name of the spectrograph used and
the reference of the measurement.

Quasar | $z_{\textrm{abs}}$ | $\Delta\alpha/\alpha$ | Spectrograph | Reference
---|---|---|---|---
|  | (ppm) |  |
J0120$+$2133 | $0.729$ | $0.73\pm 6.42$ | HDS | 1
J0026$-$2857 | $1.023$ | $3.54\pm 8.87$ | UVES | 2
J0058$+$0041 | $1.072$ | $-1.35\pm 7.16$ | HIRES | 2
3 quasars | $1.080$ | $4.30\pm 3.40$ | HIRES | 3
HS1549$-$1919 | $1.143$ | $-7.49\pm 5.53$ | UVES/HIRES/HDS | 4
HE0515$-$4414 | $1.151$ | $1.31\pm 1.36$ | ESPRESSO | 5
HE0515$-$4414 | $1.151$ | $-1.42\pm 0.85$ | UVES | 6
HE0515$-$4414 | $1.151$ | $-0.27\pm 2.41$ | HARPS | 7
J1237$+$0106 | $1.305$ | $-4.54\pm 8.67$ | HIRES | 2
J0120$+$2133 | $1.325$ | $2.60\pm 4.19$ | HDS | 1
HS1549$+$1919 | $1.342$ | $-0.70\pm 6.61$ | UVES/HIRES/HDS | 4
J0841$+$0312 | $1.342$ | $3.05\pm 3.93$ | HIRES | 2
J0841$+$0312 | $1.342$ | $5.67\pm 4.71$ | UVES | 2
J0120$+$213 | $1.343$ | $8.36\pm 12.16$ | HDS | 1
J0108$-$0037 | $1.371$ | $-8.45\pm 7.34$ | UVES | 2
HE0001$-$2340 | $1.580$ | $-1.50\pm 2.60$ | UVES | 8
J1029$+$1039 | $1.622$ | $-1.70\pm 10.11$ | HIRES | 2
HE1104$-$1805 | $1.661$ | $-4.70\pm 5.30$ | HIRES | 3
HE2217$-$2818 | $1.692$ | $1.30\pm 2.60$ | UVES | 9
HS1946$+$7658 | $1.738$ | $-7.90\pm 6.20$ | HIRES | 3
HS1549$+$1919 | $1.802$ | $-6.42\pm 7.25$ | UVES/HIRES/HDS | 4
Q1103$-$2645 | $1.839$ | $3.30\pm 2.90$ | UVES | 10
Q2206$-$1958 | $1.921$ | $-4.65\pm 6.41$ | UVES | 2
Q1755$+$57 | $1.971$ | $4.72\pm 4.71$ | HIRES | 2
PHL957 | $2.309$ | $-0.65\pm 6.84$ | HIRES | 2
PHL957 | $2.309$ | $-0.20\pm 12.93$ | UVES | 2
J0035$-$0918 | $2.340$ | $-12.0\pm 11.0$ | ESPRESSO | 11

(1) Murphy & Cooksey (2017); (2) Murphy et al. (2016); (3) Songaila & Cowie
(2014); (4) Evans et al. (2014); (5) Murphy et al. (2022); (6) Kotûs et al.
(2016); (7) Milaković et al. (2020); (8) Agafonova et al. (2011); (9) Molaro
et al. (2013); (10) Bainbridge & Webb (2017); (11) Welsh et al. (2020).

Figure 1: Measurements of the QSO dataset.The most recent ESPRESSO data point
is shown in red (Murphy et al., 2022).

As for the astrophysical measurements, our dataset referred to as ‘QSO’ is
analogous to that of Martinelli et al. (2021) to ensure comparability with
previous works similar to the present one, where it is common practice to test
cosmological models with a set of dedicated and well-calibrated absorption
line measurements of $\Delta\alpha/\alpha$. We refer the reader to Sect. 3 of
Martins (2017) for a thorough review. The dataset consists of 27 measurements
in systems that are located at different redshifts along several quasar lines
of sight (see Table 1). These allow us to place constraints on the value of
the fine-structure constant up to redshift $z=2.34$ as illustrated by Fig. 1.
In order to ensure some degree of homogeneity of the sample, the dataset is
limited to those measurements that were well calibrated and specifically taken
to test the stability of $\alpha$, including the most recent ESPRESSO result
(Murphy et al., 2022). The 27 measurements were obtained under dedicated
conditions whereby the data acquisition procedures ensured tailored wavelength
calibration and control of systematic errors.

In particular, the result from redshift ${z=1.692}$ was obtained with the
HE2217$-$2818 spectrum (Molaro et al., 2013) under the UVES Large Program for
testing fundamental physics. The program was designed to test the possible
cosmological variations in $\alpha$ that were previously detected through the
analysis of the archival statistical sample of quasar spectra composed of 293
Keck/HIRES and VLT/UVES measurements (Webb et al., 2011). It involved several
observational groups to improve the calibration and optimise the data
reduction and analysis pipeline. Under the same program, the separate
observation of the equatorial quasar HS1549$+$1919 by VLT, Keck, and Subaru
(Evans et al., 2014) led to the removal of the long-range distortions in the
wavelength scales of the quasar spectra affecting the UVES, HIRES, and HARPS
spectrographs from the systematic errors (Whitmore & Murphy, 2014). This
improvement was achieved by comparing the spectra obtained with the three
telescopes and using ‘supercalibration’ techniques. The corresponding data
points in Table 1 are the average of the three measurements from each absorber
system, ${z=1.143}$, ${z=1.342,}$ and ${z=1.802,}$ respectively.

Likewise, Murphy & Cooksey (2017) followed a supercalibration procedure to
correct the long-range distortions in two Subaru quasar spectra. A blinded
analysis provided the following three measurements from absorbers where
$\Delta\alpha/\alpha$ is relatively well constrained: $z=0.729$, $1.325,$ and
$1.343$ towards J0120$+$2133\. Furthermore, instead of using the common iron
or magnesium quasar absorptions lines, precise limits on the variability of
$\alpha$ were obtained by Murphy et al. (2016) with zinc and chromium lines
which are the most sensitive to its relative variation, and also more
resistant to long-range distortions of the wavelength calibration. These are
measurements taken from the following absorber positions: ${z=1.023}$ towards
J0226$-$2857, ${z=1.072}$ towards J0058$+$0041, ${z=1.305}$ towards
J1237$+$0106, ${z=1.371}$ towards J0108$-$0037, ${z=1.622}$ towards
J1029$+$1039, ${z=1.921}$ towards Q2206$-$1958, and ${z=1.971}$ towards
Q1755$+$57\. The QSO dataset also includes two measurements from ${z=1.342}$
towards J0841$+$0312 and two measurements from ${z=2.309}$ towards PHL957
because they were independently taken using different telescopes and accepted
into the main results of Murphy et al. (2016).

By correcting the UVES spectra of HE0515$-$4414 with well-calibrated spectra
from the High Accuracy Radial velocity Planet Searcher (HARPS), Kotûs et al.
(2016) obtained a measurement of high sensitivity from an intervening
absorption system at $z=1.151$. Additionally, we make use of the objective
measurement obtained in Bainbridge & Webb (2017) by applying artificial
intelligence to automatise the analysis pipeline of the absorption spectra
from the ${z=1.839}$ absorber towards Q1103$-$2645\. We also include in the
sample the measurement at ${z=1.080}$ of Songaila & Cowie (2014) where careful
attention was paid to the wavelength calibration and control of systematic
errors to aim for precision in measuring $\Delta\alpha/\alpha$. The data point
is the result of the weighted average from eight absorbers towards
HE1104$-$1805A, HS1700$+$6416, and HS1946$+$7658 (the values for the
individual systems were not given). The dataset contains an older measurement
from $z=1.580$ in the line of sight of quasar HE0001$-$2340 obtained by
Agafonova et al. (2011) who studied the extent to which the Mg II lines used
as anchor were affected by isotopic shifts and tested the local accuracy of
the wavelength scale calibration. It should be noted that Noterdaeme, P. et
al. (2021) concluded that the strong enhancement of heavy Mg isotopes was
probably due to distortion in the UVES wavelength scale.

More recent measurements are also taken into account: one from science
verification observations obtained with ESPRESSO and calibrated with LFC from
${z=2.340}$ towards J0035$-$0918 (Welsh et al., 2020), and another from new
observations of the $z=1.151$ absorption system along the HE0515$-$4414
sightline aided by LFC for the HARPS wavelength calibration (Milaković et al.,
2020). Finally, we take account of the first precise ESPRESSO measurement with
LFC calibration (Murphy et al., 2022), as the main motivation of the present
paper, from $z=1.151$ towards HE0515$-$4414\. As in the case of the absorbers
towards J0841+0312 and PHL957, for which two different data points are used,
we keep three measurements towards HE0515$-$4414 because they can be
considered independent in the statistical analysis. The three measurements
were obtained using different spectrographs (HARPS, UVES and ESPRESSO), yet
with appropriate wavelength calibration and control of systematic errors.

We define the likelihood of the QSO dataset, namely the probability of getting
the $\Delta\alpha/\alpha$ measurements given our theory, as follows:

$\ln\mathcal{L}_{\textrm{\tiny{QSO}}}=-\frac{1}{2}\sum\limits_{i}\frac{1}{\sigma_{i}^{2}}\left[\left.\frac{\Delta\alpha}{\alpha}\right|_{\textrm{\tiny{th}}}\left(z_{i}\right)-\left.\frac{\Delta\alpha}{\alpha}\right|_{\textrm{\tiny{obs}}}\left(z_{i}\right)\right]^{2}\,,$
(13)

where $i$ denotes the $i^{\textrm{\tiny{th}}}$ observation in Table 1,
$\sigma_{i}$ and $z_{i}$ are respectively the corresponding standard deviation
and absorber redshift. The subscripts ‘th’ and ‘obs’ stand for the theoretical
prediction of Eq. (12) and the $i^{\textrm{\tiny{th}}}$ measurement,
respectively.

Regarding the current $\alpha$ drift rate, $(\dot{\alpha}/\alpha)_{0}$,
according to our parametrisation it simplifies to

$\left(\frac{\dot{\alpha}}{\alpha}\right)_{0}=\zeta\lambda H_{0}=\zeta\lambda
h\,\left(1.02\,\times 10^{-10}\right)\,{\rm yr^{-1}}\,,$ (14)

where the dot denotes derivation with respect to cosmic time and $h$ is the
Hubble parameter. We note that there is a degeneracy with the current
expansion rate, $H_{0}\equiv 100h$ km/s/Mpc. The drift rate is locally
constrained in lab experiments based on the comparison of atomic clocks, the
strongest bound being in Lange et al. (2021),

$\left(\frac{\dot{\alpha}}{\alpha}\right)_{0}=\left(1.0\pm 1.1\right)\times
10^{-18}\,\,\textrm{yr}^{-1}\,.$ (15)

We refer to this constraint as ‘atomic clocks’. The corresponding likelihood
is simply

$\ln\mathcal{L}_{\textrm{\tiny{clocks}}}=-\frac{1}{2}\frac{\left[\left.\left(\frac{\dot{\alpha}}{\alpha}\right)_{0}\right|_{\textrm{\tiny{th}}}-\left.\left(\frac{\dot{\alpha}}{\alpha}\right)_{0}\right|_{\textrm{\tiny{obs}}}\right]^{2}}{\sigma^{2}}\,,$
(16)

where again the subscripts ‘th’ and ‘obs’ stand for the theoretical prediction
of Eq. (14) and the bound in Eq. (15) respectively, while $\sigma$ is the
error in the measurement.

Moreover, it is possible to break the degeneracies between $\zeta$ and
$\lambda$ by imposing individual constraints on them. To this end, we use the
Eötvös parameter, $\eta$, as observable to separately constrain the
electromagnetic coupling $\zeta$ by considering the following relation
(Carroll, 1998; Dvali & Zaldarriaga, 2002):

$\eta\approx 10^{-3}\zeta^{2}\,.$ (17)

The parameter $\eta$ quantifies the level of violation of the weak equivalence
principle induced by the variation of $\alpha$ (Damour & Donoghue, 2010). We
make use of the local bound on $\eta$ in Touboul et al. (2019) placed by the
space-based MICROSCOPE experiment, as it is the most stringent:

$\eta=\left(-0.1\pm 1.3\right)\times 10^{-14}\,.$ (18)

We call this bound ‘MICROSCOPE’, for which we define the likelihood such that

$\ln\mathcal{L}_{\textrm{\tiny{MICRO}}}=-\frac{1}{2}\frac{\left(\eta_{\textrm{\tiny{micro}}}-\eta\right)^{2}}{\sigma^{2}}\,,$
(19)

where $\eta_{\textrm{\tiny{micro}}}$ and $\sigma$ are given by Eq. (18).
Moreover, this latter is a Gaussian prior put on $\zeta$ in the statistical
analysis.

As for $\lambda$, to ease the calculation, we constructed a multivariate
Gaussian prior that approximatively summarises the geometrical constraints
inferred in da Fonseca et al. (2022), where the present scalar field
parametrisation was tested with Planck data, regardless of the
electromagnetism coupling. We therefore apply it on the vector of free
parameters, $\nu=(\lambda,\omega_{b},\omega_{c},H_{0})$, without $\zeta$,
where $\omega_{b}\equiv\Omega_{b}h^{2}$ is today’s baryon density and
$\omega_{c}\equiv\Omega_{c}h^{2}$ is today’s density of cold dark matter111da
Fonseca et al. (2022) additionally contemplate a coupling within the dark
sector parametrised with a constant $\beta$, which we consider to be vanishing
here.. Our Gaussian prior, which is analogous to Betoule et al. (2014), has
the following likelihood form

$\ln\mathcal{L}_{\textrm{\tiny{cmb}}}=-\frac{1}{2}\left(\nu-\nu_{\textrm{\tiny{cmb}}}\right)^{\top}C_{\textrm{\tiny{cmb}}}^{-1}\left(\nu-\nu_{\textrm{\tiny{cmb}}}\right)\,,$
(20)

where
$\nu_{\textrm{\tiny{cmb}}}=(\lambda,\omega_{b},\omega_{c},H_{0})_{\textrm{\tiny{cmb}}}=(0.,0.02267,0.1210,66.8)$,
and $C_{\textrm{\tiny{cmb}}}$ is the best-fit covariance matrix marginalised
over all the fixed parameters, taken from the previous study carried out in da
Fonseca et al. (2022):

${\small C_{\textrm{\tiny{cmb}}}=\begin{pmatrix}3.0\times 10^{-3}&-9.8\times
10^{-9}&-2.2\times 10^{-6}&1.8\times 10^{-3}\\\ -9.8\times 10^{-9}&3.6\times
10^{-8}&-1.8\times 10^{-8}&-2.1\times 10^{-5}\\\ -2.2\times 10^{-6}&-1.8\times
10^{-8}&8.9\times 10^{-6}&-5.5\times 10^{-3}\\\ 1.8\times 10^{-3}&-2.1\times
10^{-5}&-5.5\times 10^{-3}&3.6\end{pmatrix}}\,.$ (21)

We refer to this likelihood as ‘Planck prior’.

It is worthwhile noting that the Planck prior is built from a dark energy
model that does not foresee any coupling with the electromagnetic sector.
However, it was demonstrated that the CMB angular power spectrum is most
sensitive to the value of the fine-structure constant at recombination time
because varying $\alpha$ changes the ionisation history in the early Universe
(Kaplinghat et al., 1999). The effects on the anisotropies are degenerate with
other cosmological parameters whereas we limit the CMB constraints to a
distance prior that does not take into account the variation of $\alpha$. It
is therefore important to assess whether our approximation is accurate enough.
To do so, we adapted the Einstein-Boltzmann code CLASS (Blas et al., 2011) to
accommodate the potential of our specific scalar field parametrisation in Eq .
(8), and to include the evolution of the variation of the fine-structure
constant obtained in Eq. (12). We used this code to compute the angular power
spectra of the CMB. Figure 2 shows the competing effects of our two parameters
$\lambda$ and $\zeta$ on the position and amplitude of the acoustic peaks,
when the other cosmological parameters are fixed to Planck 2018 values
(Aghanim et al., 2020a). On the one hand, as the presence of the scalar field
speeds up the expansion of the Universe background, the comoving angular
distance to the last scattering surface decreases with respect to
$\Lambda$CDM. The increase in the Hubble rate slightly shifts the anisotropies
towards larger scales. Moreover, the amplitude of the peaks is larger in
comparison with the concordance model. The non-negligible contribution of dark
energy in the early Universe reduces the fractional energy density of matter
at the time of decoupling. On the other hand, as recapitulated in Hart &
Chluba (2017), larger $\alpha$ shifts the peaks towards smaller scales because
of the earlier recombination, and enhances their amplitude via the suppression
of photon diffusion damping. The opposite effects hold for decreasing
$\alpha,$ whereas $\lambda$ influences the power spectrum irrespective of its
sign.

In light of the examination of the degeneracies, we find it necessary in the
following section to compare statistical results between the Planck prior that
is insensitive to $\zeta$ and a more comprehensive Planck likelihood, referred
to as ‘full Planck’ hereafter, which is sensitive to $\alpha$ variation. We
used the legacy likelihood Planck TT, TE, EE described in Aghanim et al.
(2020b), where TT, TE, and EE stand for the angular power spectra of the
temperature auto-correlation, the temperature and polarisation cross-
correlation, and the polarisation auto-correlation, respectively. This derives
from the data collected by the Planck satellite on the anisotropies of the CMB
in the form of Stokes intensity and linear polarisation maps complemented by
intensity maps. The information is split into temperature T and the E mode
polarisation component to construct the likelihood of a given theoretical
model power spectrum given the observed one, taking account of correlations
between the TT, TE, and EE spectra for the higher multipoles ($l>29$). We
limited the likelihood to the so-called lite version which contains 613 data
points and marginalises over the instrumental and foreground effects.

Figure 2: CMB temperature power spectra for the dark energy parameter
$\lambda=0.4$ and different values of the electromagnetic coupling $\zeta$.

##  4 Bayesian inference and likelihood analysis

We constrained the cosmological parameters of our model,
$\\{\zeta,\lambda,\omega_{b},\omega_{c},H_{0}\\}$, by reconstructing the
posterior probability distribution (PPD) in the parameter space. The PPD is
defined as the product of the uncorrelated likelihoods specified in Sect. 3,
depending on different combinations of datasets. We sampled the parameter
space with the Monte Carlo code Monte Python (Audren et al., 2013) and the
Nested Sampling algorithm (Skilling, 2006) through the Multinest library
(Feroz et al., 2009) wrapped with PyMultiNest (Buchner et al., 2014). The
theoretical predictions were computed with our modified version of CLASS where
we also implemented the observables defined in Sect. 3. We adopted the GetDist
package (Lewis, 2019) to analyse and plot the resulting Monte Carlo samples.

To begin with, we estimated the accuracy of the CMB distance prior by
combining the QSO dataset with the Planck prior and then with full Planck
(varying $\alpha$ at recombination to take into account its effects on the
anisotropies). In the former, we applied a flat prior on $\zeta\in[-400,400]$
ppm. In the latter, we also included in the parameter space the absolute
calibration, $A_{\textrm{planck}}$, as the only nuisance parameter, and the
other three relevant cosmological parameters $\\{n_{s},\ln
10^{10}A_{s},\tau_{\textrm{reio}}\\}$, where $n_{s}$ is the spectral index of
the primordial power spectrum whose amplitude $A_{s}$ is normalised at a pivot
scale $k_{*}=0.05$ Mpc-1, and $\tau_{\textrm{reio}}$ is the optical depth to
reionisation.

The results of the two Bayesian analyses are reported in Table 2 where we can
see that the differences in the mean values and uncertainties for the $\zeta$
posterior are insignificant. The Planck prior slightly increases the
uncertainty by $0.13\sigma$ for the posterior $\lambda$. It may be counter-
intuitive that full-Planck improves the constrains despite it having more free
parameters than the distance prior. Nonetheless, one can also expect that the
additional constraint at recombination in the former case strengthens the
limits on both posteriors.

Table 2: Comparison between the Planck distance prior and full Planck, and
comparative constraining power of the ESPRESSO data point (mean and $68\%$
limits).

Likelihoods | $\zeta$ | $\lambda$
---|---|---
| (ppm) |
QSO + full Planck | $2\pm 130$ | $0.000\pm 0.023$
QSO + Planck prior | $0\pm 140$ | $0.000\pm 0.026$
QSO without ESPRESSO | $2\pm 150$ | $0.000\pm 0.027$
ESPRESSO only | $0\pm 170$ | $0.000\pm 0.032$
222 Both likelihoods of the bottom panel include the Planck prior.

The response of the CMB anisotropies to the variation of the fine-structure
constant can therefore be neglected in the model at stake. If we take the
example of the ESPRESSO data point, giving a one ppm constraint around
redshift $z=1$, the variation in $\alpha$ would be about $10$ ppm at
recombination time according to Eq. (12), which is indeed insufficient to
produce detectable effects. Therefore, we did not use the full Planck
likelihood because it is more computationally demanding with marginal benefit.
In the rest of the analysis, we systematically combined the Planck prior with
the other datasets in order to account for the correlation between
cosmological parameters including $\lambda$.

We proceeded with a Bayesian inference that combined the QSO + Planck prior
datasets with and without the recent ESPRESSO measurement in order to look at
its added value in constraining the electromagnetic coupling $\zeta$ (to which
we applied the same flat prior as above). The confidence contours in the
$(\lambda,\zeta)$ plane in Fig. 3 are indeed slightly improved by the addition
of the this data point. We also provide the results obtained with ESPRESSO
alone in the same figure. Table 2 shows that using this single measurement
places constraints of the same order at $1\sigma$ confidence level.

Figure 3: Constraining power of the ESPRESSO data point with respect to QSO (+
Planck Prior in every case). Probability distribution and 2D marginalised
contours (68% and 95% confidence level).

We wanted to combine the astrophysical observations (QSO + Planck prior) with
the local bounds, starting with the current $\alpha$ drift rate. The results
are given in Table 3. The addition of the bound placed by the atomic clocks
further tightens the constraints both on the electromagnetic coupling $\zeta$
and the scalar field parameter $\lambda$, as shown in Fig. 4. According to
Eqs. (14) and (15), the atomic clock data constrain the product of the two
parameters by approximatively

$\delta(\zeta\lambda)\sim 10^{-8}/h\,,$ (22)

which is two orders of magnitude stronger than with astrophysical data. For
example, using the ESPRESSO data point located at $z_{\textrm{abs}}\sim 1$,
Eq. (12) gives

$\delta(\zeta\lambda)\sim 10^{-6}/\ln 2\,.$ (23)

We supplemented the analysis with the MICROSCOPE bound, which is a Gaussian
prior on $\zeta$ as mentioned earlier in Sect. 3. Including the Eötvös
parameter leads to the tightest constraint on the electromagnetic coupling,
$\zeta=0.0\pm 1.6$ ppm, relaxing the dark energy parameter $\lambda$ as shown
in Fig. 5. This behaviour is similar to the findings of the forecasts in
Calabrese et al. (2014) for $\Delta\alpha/\alpha$ null results. As the
confidence contours are dramatically reduced for the electromagnetic coupling,
as illustrated by the zoom onto the probability distributions and confidence
contours shown in Fig. 6, larger values of $\lambda$ are allowed in order to
achieve vanishing $\Delta\alpha/\alpha$ thanks to the correlation between the
two parameters encapsulated in Eq. (12).

Similar conclusions can be drawn by inspecting directly the posterior on the
product $\zeta\lambda$ which is the quantity sensitive to the variation of
$\alpha$. Figure 7 shows its correlation with the dark energy equation of
state $w_{0}$ given in Eq.(11). Both one-sigma constraints become more
stringent when the atomic clocks are included on top of the QSO+Planck prior:
the limits on the dark energy equation of state change from
$1+w_{0}<1.14\times 10^{-4}$ to $1+w_{0}<1.13\times 10^{-5}$, and on the
product posterior from $\zeta\lambda=0.25^{+0.56}_{-0.63}$ to
$\zeta\lambda=0.013^{+0.014}_{-0.017}$. The addition of the MICROSCOPE bound
does not greatly modify the posterior distribution of the product but it
affects the dark energy equation of state. Without the $\eta$ bound, the
product posterior is dominated by the Planck limit on $\lambda$, allowing a
wider range of values for the electromagnetic coupling. Conversely, the strong
MICROSCOPE constraint on $\zeta$ increases the possible values of $\lambda$,
taking the dark energy equation of state gently away from a cosmological
constant, $1+w_{0}<2.89\times 10^{-4}$. The constraints placed on $w_{0}$ by
the CMB in our parametrisation are stronger than those forecasted for the
Euclid mission (Euclid Collaboration et al., 2020) in Martinelli et al. (2021)
with the CPL parametrisation. Consequently, we obtain weaker constraints on
$\zeta$ in light of the above discussion.

Figure 4: Probability distribution and 2D marginalised contours (68% and 95%
confidence level).

Figure 5: Probability distribution for the two extra parameters posteriors
$\lambda$ and $\zeta$.

Figure 6: Zoom onto the probability distributions and confidence contours. Table 3: Constraints on the two additional parameters and their product (mean and $68\%$ limits) obtained with different dataset combinations. Likelihoods | $\zeta$ | $\lambda$ | $\zeta\lambda$
---|---|---|---
| (ppm) |  | (ppm)
QSO + Planck prior | $0\pm 140$ | $0.000\pm 0.026$ | $0.25^{+0.56}_{-0.63}$
\+ atomic clocks | $0\pm 110$ | $0.000\pm 0.020$ | $0.013^{+0.014}_{-0.017}$
\+ MICROSCOPE | $0.0\pm 1.6$ | $0.000\pm 0.032$ | $0.011^{+0.013}_{-0.017}$

Figure 7: $\zeta\lambda$ and dark energy equation of state posteriors.
Probability distribution and 2D marginalised contours (68% and 95% confidence
level).

##  5 Conclusions

Current astrophysical probes of the stability of fundamental constants
associated with local tests allow us to constrain dark energy models with
varying $\alpha$. We constructed a simple parametrisation for this kind of
model that adds just two degrees of freedom beyond $\Lambda$CDM, under the
assumption that the scalar field fuelling dark energy is also driving the time
variation of the fine-structure constant. As with the CPL parametrisation, the
limited number of parameters is key in the ability of a given model to be
efficiently constrained by observations.

We used the most recent QSO measurements in combination with CMB data. The
astrophysical probes therefore combined low-redshift with high-redshift
observations to obtain complementary constraints from the late and early
Universe on the entire parameter space of our model. We confirm that the
sensitivity of the CMB anisotropies to the electromagnetic coupling can be
neglected to good accuracy, enabling us to use a simple distance prior instead
of a comprehensive Planck likelihood in the Bayesian inference, and save
significant computational time.

We put constraints on the parameter $\lambda$ responsible for the quintessence
evolution and on the coupling $\zeta$ with the electromagnetic sector.
Regarding the parametric evolution of the scalar field as a function of
redshift, the constraints obtained on $\lambda$ are compatible with null
variation, or in other words, with a cosmology with a cosmological constant as
dark energy. As it is the product $\zeta\lambda$ that is being constrained in
the parametrisation, the tight limits on $\lambda$ loosen the constraints on
$\zeta$ through the degeneracy between the two parameters, because as
$\lambda\rightarrow 0$ any coupling value is capable of reproducing the null
results of varying $\alpha$. A similar feature was found with the CPL
parametrisation of the dark energy equation of state (Calabrese et al., 2014).

Despite the differences in the uncertainties, every data combination suggests
a vanishing electromagnetic coupling, which corresponds to null results and is
consistent with a stable fine-structure constant. While the new ESPRESSO data
point improves the astrophysical limits on $\zeta$, it is the local
constraints that largely dominate, particularly those from the violation of
the weak equivalence principle (see also Martins et al., 2022). The addition
of the strong Eötvös parameter bound placed with the MICROSCOPE satellite
gives $\zeta=0.0\pm 1.6$ ppm which is two orders of magnitude more stringent
than the constraints obtained from the astrophysical probes in combination
with the atomic clocks. The stronger constraint on $\zeta$ loosens those on
$\lambda$ and allows slightly higher values for the dark energy equation of
state. For the model considered here, the precision in the ESPRESSO
measurement needs to increase by two orders of magnitude in order to be
competitive with the atomic clocks. However, as the astrophysical measurements
correspond to higher redshifts, this estimate is clearly model dependent.
Beyond the model assumed in the present paper, ESPRESSO is essential in
producing precise measurements in a redshift regime not tested by other
probes. It would be interesting to evaluate how these conclusions hold when
considering models involving departures from this simple parametrisation for
the evolution of the field.

## Acknowledgements

This work was financed by FEDER–Fundo Europeu de Desenvolvimento Regional
funds through the COMPETE 2020–Operational Programme for Competitiveness and
Internationalisation (POCI), and by Portuguese funds through FCT - Fundação
para a Ciência e a Tecnologia under projects POCI-01-0145-FEDER-028987,
PTDC/FIS-AST/28987/2017, PTDC/FIS-AST/0054/2021 and EXPL/FIS-AST/1368/2021, as
well as UIDB/04434/2020 & UIDP/04434/2020, CERN/FIS-PAR/0037/2019, PTDC/FIS-
OUT/29048/2017. MTM acknowledges the support of the Australian Research
Council through Future Fellowship grant FT180100194. The INAF authors
acknowledge financial support of the Italian Ministry of Education,
University, and Research with PRIN 201278X4FL and the ”Progetti Premiali”
funding scheme. TMS also acknowledges the support from the Swiss National
Science Foundation (SNSF) and the University of Geneva. M-RZO acknowledges
funding under project PID2019-109522GB-C51 of the Spanish Ministerio de
Ciencia e Investigación. ASM and JIGH acknowledge financial support from the
Spanish Ministry of Science and Innovation (MICIN) project
PID2020-117493GB-I00. ASM also acknowledges financial support from the Spanish
Ministry of Science and Innovation (MICINN) under 2018 Juan de la Cierva
program IJC2018-035229-I, as well as from the Government of the Canary Islands
project ProID2020010129.

## References

  * Agafonova et al. (2011) Agafonova, I. I., Molaro, P., Levshakov, S. A., & Hou, J. L. 2011, aap, 529, A28
  * Aghanim et al. (2020a) Aghanim, N., Akrami, Y., Ashdown, M., et al. 2020a, Astronomy & Astrophysics, 641, A6
  * Aghanim et al. (2020b) Aghanim, N., Akrami, Y., Ashdown, M., et al. 2020b, Astronomy & Astrophysics, 641, A5
  * Audren et al. (2013) Audren, B., Lesgourgues, J., Benabed, K., & Prunet, S. 2013, JCAP, 1302, 001
  * Bainbridge & Webb (2017) Bainbridge, M. B. & Webb, J. K. 2017, Monthly Notices of the Royal Astronomical Society, 468, 1639
  * Barreiro et al. (2000) Barreiro, T., Copeland, E. J., & Nunes, N. J. 2000, Phys. Rev., D61, 127301
  * Bekenstein (1982) Bekenstein, J. D. 1982, Phys. Rev. D, 25, 1527
  * Betoule et al. (2014) Betoule, M., Kessler, R., Guy, J., et al. 2014, Astronomy & Astrophysics, 568, A22
  * Blas et al. (2011) Blas, D., Lesgourgues, J., & Tram, T. 2011, Journal of Cosmology and Astroparticle Physics, 2011, 034–034
  * Buchner et al. (2014) Buchner, J., Georgakakis, A., Nandra, K., et al. 2014, Astron. Astrophys., 564, A125
  * Calabrese et al. (2014) Calabrese, E., Martinelli, M., Pandolfi, S., et al. 2014, Physical Review D, 89
  * Carroll (1998) Carroll, S. M. 1998, Physical Review Letters, 81, 3067–3070
  * Chand et al. (2004) Chand, H., Srianand, R., Petitjean, P., & Aracil, B. 2004, Astronomy & Astrophysics, 417, 853–871
  * Chevallier & Polarski (2001) Chevallier, M. & Polarski, D. 2001, International Journal of Modern Physics D, 10, 213, (uses Latex, 12 pages, 6 Figures) Minor corrections, Figures 4, 6 revised. Conclusions unchanged
  * Chiba & Kohri (2002) Chiba, T. & Kohri, K. 2002, Progress of Theoretical Physics, 107, 631
  * Copeland et al. (2004) Copeland, E. J., Nunes, N. J., & Pospelov, M. 2004, Physical Review D, 69
  * da Fonseca et al. (2022) da Fonseca, V., Barreiro, T., & Nunes, N. J. 2022, Physics of the Dark Universe, 35, 100940
  * Damour & Donoghue (2010) Damour, T. & Donoghue, J. F. 2010, Phys. Rev. D, 82, 084033
  * Damour et al. (2002) Damour, T., Piazza, F., & Veneziano, G. 2002, Physical Review D, 66
  * Dvali & Zaldarriaga (2002) Dvali, G. & Zaldarriaga, M. 2002, Physical Review Letters, 88
  * Euclid Collaboration et al. (2020) Euclid Collaboration, Blanchard, A., Camera, S., et al. 2020, A&A, 642, A191
  * Evans et al. (2014) Evans, T. M., Murphy, M. T., Whitmore, J. B., et al. 2014, Monthly Notices of the Royal Astronomical Society, 445, 128–150
  * Feroz et al. (2009) Feroz, F., Hobson, M. P., & Bridges, M. 2009, Monthly Notices of the Royal Astronomical Society, 398, 1601–1614
  * Hart & Chluba (2017) Hart, L. & Chluba, J. 2017, Monthly Notices of the Royal Astronomical Society, 474, 1850–1861
  * Kaplinghat et al. (1999) Kaplinghat, M., Scherrer, R. J., & Turner, M. S. 1999, Physical Review D, 60
  * King et al. (2012) King, J. A., Webb, J. K., Murphy, M. T., et al. 2012, Monthly Notices of the Royal Astronomical Society, 422, 3370–3414
  * Kotûs et al. (2016) Kotûs, S. M., Murphy, M. T., & Carswell, R. F. 2016, Monthly Notices of the Royal Astronomical Society, 464, 3679
  * Lange et al. (2021) Lange, R., Huntemann, N., Rahm, J. M., et al. 2021, Phys. Rev. Lett., 126, 011102
  * Lewis (2019) Lewis, A. 2019 [arXiv:1910.13970]
  * Linder (2003) Linder, E. 2003, Physical review letters, 90, 091301
  * Martinelli et al. (2021) Martinelli, M., Martins, C. J. A. P., Nesseris, S., et al. 2021, Astronomy & Astrophysics, 654, A148
  * Martins (2017) Martins, C. J. A. P. 2017, Reports on Progress in Physics, 80, 126902
  * Martins et al. (2022) Martins, C. J. A. P., Cristiani, S., Cupani, G., et al. 2022, Fundamental physics with ESPRESSO: Constraints on Bekenstein and dark energy models from astrophysical and local probes
  * Martins et al. (2022) Martins, C. J. A. P., Ferreira, F. P. S. A., & Marto, P. V. 2022, Physics Letters B, 827, 137002
  * Martins & Vila Miñana (2019) Martins, C. J. A. P. & Vila Miñana, M. 2019, Physics of the Dark Universe, 25, 100301
  * Milaković et al. (2020) Milaković, D., Lee, C.-C., Carswell, R. F., et al. 2020, Monthly Notices of the Royal Astronomical Society, 500, 1–21
  * Molaro et al. (2013) Molaro, P., Centurión, M., Whitmore, J. B., et al. 2013, aap, 555, A68
  * Murphy & Cooksey (2017) Murphy, M. T. & Cooksey, K. L. 2017, Monthly Notices of the Royal Astronomical Society, 471, 4930
  * Murphy et al. (2016) Murphy, M. T., Malec, A. L., & Prochaska, J. X. 2016, Monthly Notices of the Royal Astronomical Society, 461, 2461–2479
  * Murphy et al. (2022) Murphy, M. T., Molaro, P., Leite, A. C. O., et al. 2022, A&A, 658, A123
  * Murphy et al. (2003) Murphy, M. T., Webb, J. K., & Flambaum, V. V. 2003, Monthly Notices of the Royal Astronomical Society, 345, 609–638
  * Murphy et al. (2007) Murphy, M. T., Webb, J. K., & Flambaum, V. V. 2007, Physical Review Letters, 99
  * Murphy et al. (2008) Murphy, M. T., Webb, J. K., & Flambaum, V. V. 2008, Monthly Notices of the Royal Astronomical Society, 384, 1053–1062
  * Noterdaeme, P. et al. (2021) Noterdaeme, P., Balashev, S., Ledoux, C., et al. 2021, A&A, 651, A78
  * Nunes (2004) Nunes, N. J. 2004, AIP Conf. Proc., 736, 135
  * Nunes & Lidsey (2004) Nunes, N. J. & Lidsey, J. E. 2004, Phys. Rev., D69, 123511
  * Pepe et al. (2021) Pepe, F., Cristiani, S., Rebolo, R., et al. 2021, Astronomy & Astrophysics, 645, A96
  * Perlmutter et al. (1999) Perlmutter, S. et al. 1999, Astrophys. J., 517, 565
  * Riess et al. (1998) Riess, A. G. et al. 1998, Astron. J., 116, 1009
  * Skilling (2006) Skilling, J. 2006, Bayesian Analysis, 1, 833
  * Songaila & Cowie (2014) Songaila, A. & Cowie, L. L. 2014, The Astrophysical Journal, 793, 103
  * Srianand et al. (2007) Srianand, R., Chand, H., Petitjean, P., & Aracil, B. 2007, In response to the comments by Murphy et al. (arxiv:0708.3677)
  * Touboul et al. (2019) Touboul, P., Métris, G., Rodrigues, M., et al. 2019, Classical and Quantum Gravity, 36, 225006
  * Uzan (2011) Uzan, J.-P. 2011, Living Reviews in Relativity, 14, 2
  * Webb et al. (2011) Webb, J. K., King, J. A., Murphy, M. T., et al. 2011, Physical Review Letters, 107
  * Webb et al. (2001) Webb, J. K., Murphy, M. T., Flambaum, V. V., et al. 2001, Physical Review Letters, 87
  * Welsh et al. (2020) Welsh, L., Cooke, R., Fumagalli, M., & Pettini, M. 2020, Monthly Notices of the Royal Astronomical Society, 494, 1411–1423
  * Whitmore & Murphy (2014) Whitmore, J. B. & Murphy, M. T. 2014, Monthly Notices of the Royal Astronomical Society, 447, 446–462


Lalign

(1) $\displaystyle\BODY$

Ralign

(2) $\displaystyle\BODY$

# Datatype defining rewrite systems for the ring of integers, and for natural
and integer arithmetic in unary view

Jan A. Bergstra and Alban Ponse
Informatics Institute, section Theory of Computer Science
University of Amsterdam
https://staff.fnwi.uva.nl/j.a.bergstra/ https://staff.fnwi.uva.nl/a.ponse/

###### Abstract

A datatype defining rewrite system (DDRS) is a ground-complete term rewriting
system, intended to be used for the specification of datatypes. As a follow-up
of an earlier paper we define two concise DDRSes for the ring of integers,
each comprising only twelve rewrite rules, and prove their ground-
completeness. Then we introduce DDRSes for a concise specification of natural
number arithmetic and integer arithmetic in unary view, that is, arithmetic
based on unary append (a form of tallying) or on successor function. Finally,
we relate one of the DDRSes for the ring of integers to the above-mentioned
DDRSes for natural and integer arithmetic in unary view.
_Keywords and phrases:_ Datatype defining rewrite system, Equational
specification, Integer arithmetic, Natural number arithmetic

###### Contents

  1. 1 Introduction
  2. 2 DDRSes for the ring of integers
    1. 2.1 A concise DDRS for ${\mathbb{Z}}_{r}$
    2. 2.2 An alternative DDRS for ${\mathbb{Z}}_{r}$
  3. 3 DDRSes for natural number and integer arithmetic in unary view
    1. 3.1 Concise DDRSes for ${\mathbb{N}}_{U}$ and ${\mathbb{Z}}_{U}$
    2. 3.2 From the ring of integers to unary view
    3. 3.3 Successor function instead of unary append
  4. 4 Conclusions

##  1 Introduction

In Table 1 we recall the axioms for commutative rings over the signature
$\Sigma_{r}=\\{0,1,-,+,\cdot\\}$. Our point of departure is that these axioms
characterize integer arithmetic, while leaving open how numbers are
represented (apart from the constants $0,1\in\Sigma_{r}$). In this paper we
introduce a few simple specifications for the concrete datatype determined by
these axioms, and for natural number and integer arithmetic with numbers
represented in unary view, that is, in a numeral system based on unary append
(a form of tallying) or on successor function.

x + (y + z) &= (x+y) + z x+y = y + x x+0 = x x + (-x) = 0 (x ⋅y) ⋅z &= x ⋅(y
⋅z) x ⋅y = y ⋅x 1⋅x=x x ⋅(y + z) = (x ⋅y) + (x ⋅z)

Table 1: Axioms for commutative rings

Given some signature, a datatype defining rewrite system (DDRS) consists of a
number of equations over that signature that define a term rewriting system
when interpreting the equations from left to right. A DDRS must be ground-
complete, that is, strongly terminating and ground-confluent (for some general
information on term rewriting systems see e.g. [5]). While equational
specifications are used to determine abstract datatypes, a DDRS is meant to be
used for the specification of a _concrete_ datatype, which is a canonical term
algebra: for each congruence class of closed terms, a unique representing term
is chosen, and this set of representing closed terms — _canonical terms_ or
_normal forms_ — is closed under taking subterms.

In [2], DDRSes for natural number arithmetic (defining addition and
multiplication) and integer arithmetic (also defining the unary minus
operator) were specified according to three views:

  1. 1.

The _unary_ view. In this view, number representation is based on the constant
$0$ and either the well-known successor function $S(x)$, or a unary append
constructor (a form of tallying).

  2. 2.

The _binary_ view, in which number representation is based on constants for
the two digits $0$ and $1$, and on two binary append constructors.

  3. 3.

The _decimal_ view, in which number representation is based on constants for
the ten digits $0,1,\dots,9$, and on ten binary append constructors.

Furthermore, each of these DDRSes contains equations for rewriting constructor
terms in one of other views to a term in the DDRS’es view, e.g., the DDRSes
for the unary view contain the equation $1=S(0)$ for the constant 1 in binary
view and in decimal view. The design of these DDRSes is geared towards
obtaining comprehensible specifications of natural number and integer
arithmetic in binary and decimal view. The successor function $S(x)$ and
predecessor function $P(x)$ appeared to be instrumental auxiliary functions
for this purpose, thereby justifying the incorporation of the unary view as a
separate view.

This paper is a follow-up of [2]. In Section 2 we define two different DDRSes
for the ring of integers that both contain only twelve equations, and prove
their ground-completeness. In Section 3 we provide DDRSes for the unary view
that are more concise than those in [2], and relate one of the DDRSes for the
ring of integers to these DDRSes. We end the paper with some conclusions in
Section 4. In [2] we wrote that we judge the DDRSes for the unary view to be
“irrelevant as term rewriting systems from which an efficient implementation
can be generated”, and we now also draw some positive conclusions.

##  2 DDRSes for the ring of integers

In [1, 2] we defined a DDRS consisting of fifteen equations for the (concrete)
datatype ${\mathbb{Z}}_{r}$ over the signature $\Sigma_{r}$ of (commutative)
rings. Normal forms are 0 for zero, the positive numerals 1 and $t+1$ with $t$
a positive numeral, and the negations of positive numerals, thus $-t$ for each
positive numeral $t$.

In this section we consider two different DDRSes that define
${\mathbb{Z}}_{r}$ and both contain only twelve equations. In Section 2.1 we
define a DDRS that is close to the one defined in [1, 2], and in Section 2.2
we consider an alternative DDRS that is deterministic with respect to
rewriting a sum of two nonnegative normal forms.

###  2.1 A concise DDRS for ${\mathbb{Z}}_{r}$

The DDRS $D_{1}$ in Table 2 defines the datatype ${\mathbb{Z}}_{r}$. The
difference between the DDRS $D_{1}$ in Table 2 and the DDRS for
${\mathbb{Z}}_{r}$ defined in [1, 2] is that equation 2 replaces the four
equations 1+(-1)&=0,
(x+1)+(-1)=x,
x+(-(y+1))=(x+(-y))+(-1),
(-x)+(-y)=-(x+y).

In the remainder of this section we prove the ground-completeness of the DDRS
$D_{1}$.

x+0 &=x 0+x =x x + (y+z) = (x+y)+z x ⋅0 =0 x ⋅1 =x x ⋅(y+z) =(x⋅y)+(x⋅z) -0&=0
(-1)+1=0 (-(x+1))+1=-x -(-x) =x x+(-y)=-((-x)+y) x ⋅(-y) =-(x⋅y)

Table 2: The DDRS $D_{1}$ for the datatype ${\mathbb{Z}}_{r}$ that specifies
the ring integers

######  Lemma 2.1.1.

The DDRS $D_{1}$ for ${\mathbb{Z}}_{r}$ in Table 2 is strongly terminating.

###### Proof.

Define the following weight function $|x|$ on closed terms over $\Sigma_{r}$
to ${\mathbb{N}}$:

$\displaystyle|0|=2,$ $\displaystyle|{-}x|=|x|+1,$ $\displaystyle|1|=2,$
$\displaystyle|x+y|=|x|+3|y|,$ $\displaystyle|x\cdot y|=|x|^{|y|}.$

Thus, $|t|\geq 2$ for each closed term $t$. For arbitrary closed terms $u,r$
and $s$ we find $3\cdot|s|>|s|+1$, thus

$|u|^{3|s|}>|u|^{|s|+1}\geq 2\cdot|u|^{|s|}>|u|^{|s|}+1,$

and thus $|u|^{3|s|}-1>|u|^{|s|}$. Also, $|u|^{|r|}>3$, hence

$|u|^{|r|}\cdot(|u|^{3|s|}-1)>3\cdot|u|^{|s|}$

and thus $|u|^{|r|}\cdot|u|^{3|s|}>|u|^{|r|}+3\cdot|u|^{|s|}$, and hence
$|u\cdot(r+s)|>|(u\cdot r)+(u\cdot s)|$, which proves that application of
equation 2 reduces weight. Furthermore,

$\displaystyle|u+(-r)|$ $\displaystyle=|u|+3(|r|+1)$
$\displaystyle>(|u|+1+3|r|)+1$ $\displaystyle=|{-}((-u)+r)|,$

which proves that application of equation 2 reduces weight. It easily follows
that applications of all remaining equations on closed terms also imply weight
reduction, which implies that the DDRS $D_{1}$ is strongly terminating. ∎

######  Theorem 2.1.2.

The DDRS $D_{1}$ for ${\mathbb{Z}}_{r}$ defined in Table 2 is ground-complete.

###### Proof.

See Corollary 2.2.2. ∎

###  2.2 An alternative DDRS for ${\mathbb{Z}}_{r}$

The DDRS $D_{1}$ can be “simplified” by instantiating and combining several
equations. In Table 3 we provide the DDRS $D_{2}$ that also specifies the
datatype ${\mathbb{Z}}_{r}$, where the differences with $D_{1}$ show up in the
tags: equations 3, 3 and 3 replace 2, 2 and 2, respectively.

x+0 &=x 0+1 =1 x + (y+1) = (x+y)+1 x ⋅0 =0 x ⋅1 =x x ⋅(y+1) =(x⋅y)+x -0&=0
(-1)+1=0 (-(x+1))+1=-x -(-x) =x x+(-y)=-((-x)+y) x ⋅(-y) =-(x⋅y)

Table 3: The DDRS $D_{2}$ for the datatype ${\mathbb{Z}}_{r}$ that specifies
the ring integers

######  Theorem 2.2.1.

The DDRS $D_{2}$ for ${\mathbb{Z}}_{r}$ defined in Table 3 is ground-complete.

###### Proof.

With the weight function defined in the proof of Lemma 2.1.1 it follows that
$D_{2}$ is strongly terminating: equations 3 and 3 are instances of the
associated $D_{1}$-equations 2 and 2, and equation 3 is the result of an
instance of the associated equation 2 and an application of 2.

It remains to be proven that $D_{2}$ is ground-confluent. Define the set
$\mathit{NF}$ of closed terms over $\Sigma_{r}$ as follows:

$\displaystyle\mathit{NF}$
$\displaystyle=\\{0\\}\cup{\mathit{NF}^{+}}\cup{\mathit{NF}^{-}},$
$\displaystyle{\mathit{NF}^{+}}$ $\displaystyle=\\{1\\}\cup\\{t+1\mid
t\in{\mathit{NF}^{+}}\\},$ $\displaystyle{\mathit{NF}^{-}}$
$\displaystyle=\\{-t\mid t\in{\mathit{NF}^{+}}\\}.$

It immediately follows that if $t\in\mathit{NF}$, then $t$ is a normal form
(no rewrite step applies). Furthermore, two distinct elements in $\mathit{NF}$
have distinct values in ${\mathbb{Z}}$. Clearly, the equations in Table 2 are
semantic consequences of the axioms for commutative rings (Table 1). In order
to prove ground-confluence of this DDRS it suffices to show that for each
closed term over $\Sigma_{r}$, either $t\in\mathit{NF}$ or $t$ has a rewrite
step, so that each normal form is in $\mathit{NF}$.

We prove this by structural induction on $t$. The base cases $t\in\\{0,1\\}$
are trivial. For the induction step we have to consider three cases:

  1. 1.

Case $t=-r$. Assume that $r\in\mathit{NF}$ and apply case distinction on $r$:

     * •

if $r=0$, then $t\to 0$ by equation 2,

     * •

if $r\in{\mathit{NF}^{+}}$, then $t\in\mathit{NF}$,

     * •

if $r\in{\mathit{NF}^{-}}$, then $t$ has a rewrite step by equation 2.

  2. 2.

Case $t=u+r$. Assume that $u,r\in\mathit{NF}$ and apply case distinction on
$r$:

     * •

if $r=0$, then $t\to u$ by equation 2,

     * •

if $r=1$, then apply case distinction on $u$:

       * –

if $u=0$, then $t\to 1$ by equation 3,

       * –

if $u\in{\mathit{NF}^{+}}$, then $t\in\mathit{NF}$,

       * –

if $u=-1$, then $t\to 0$ by equation 2,

       * –

if $u=-(u^{\prime}+1)$, then $t$ has a rewrite step by equation 2,

     * •

if $r=r^{\prime}+1$, then $t\to(u+r^{\prime})+1$ by equation 3,

     * •

if $r=-r^{\prime}$ with $r^{\prime}\in{\mathit{NF}^{+}}$, then
$t\to-((-u)+r^{\prime})$ by equation 2.

  3. 3.

Case $t=u\cdot r$. Assume that $u,r\in\mathit{NF}$ and apply case distinction
on $r$:

     * •

if $r=0$, then $t\to 0$ by equation 2,

     * •

if $r=1$, then $t\to u$ by equation 2,

     * •

if $r=r^{\prime}+1$, then $t\to(u\cdot r^{\prime})+u$ by equation 3,

     * •

if $r=-r^{\prime}$ with $r^{\prime}\in{\mathit{NF}^{+}}$, then $t\to-(u\cdot
r^{\prime})$ by equation 2.

∎

######  Corollary 2.2.2.

The DDRS $D_{1}$ for ${\mathbb{Z}}_{r}$ defined in Table 2 is ground-complete.

###### Proof.

The equations of the DDRS $D_{1}$ are semantic consequences of the axioms for
commutative rings (Table 1). It suffices to consider the proof of Theorem
2.2.1 and to observe that each rewrite step by one of the equations 3, 3, and
3 implies a rewrite step of the associated equation in $D_{1}$. With Lemma
2.1.1 this proves that $D_{1}$ is ground-complete. ∎

A particular property of $D_{2}$ concerns the addition of two nonnegative
normal forms.

######  Proposition 2.2.3.

With respect to addition of two nonnegative normal forms, the DDRS $D_{2}$ in
Table 3 is deterministic. That is, for nonnegative normal forms
$t,t^{\prime}$, in each state of rewriting of $t+t^{\prime}$ to its normal
form, only one equation (rewrite rule) applies.

###### Proof.

By structural induction on $t^{\prime}$. For $t^{\prime}\in\\{0,1\\}$ this is
immediately clear.

If $t^{\prime}=r+1$, then the only possible rewrite step is
$t+(r+1)\stackrel{{\scriptstyle\text{\ref{Rm3}}}}{{\longrightarrow}}(t+r)+1$.
If $r=1$, this is a normal form, and if $r=r^{\prime}+1$, the only redex in
$(t+(r^{\prime}+1))+1$ is in $t+(r^{\prime}+1)$, and by induction the latter
rewrites deterministically to some normal form $u$ not equal to 0.

Consider this reduction: $t+(r^{\prime}+1)\to...\to u$. Then
$(t+(r^{\prime}+1))+1\to...\to u+1$, and in each state of this reduction the
rightmost addition $..+1$ does not establish a new redex according to
equations 2, 3 and 3, and results in $u+1$, which is also a normal form. ∎

It is clear that for example $1+t^{\prime}$ with $t^{\prime}$ a negative
normal form also rewrites deterministically in $D_{2}$, and that this
determinism is not preserved for $t+t^{\prime}$ if $t=0$, e.g.,

$\displaystyle
0+(-(r+1))\stackrel{{\scriptstyle\text{\ref{R11}}}}{{\longrightarrow}}-((-0)+(r+1))\left[\begin{array}[]{l}\stackrel{{\scriptstyle\text{\ref{Rm3}}}}{{\longrightarrow}}-(((-0)+r)+1)\stackrel{{\scriptstyle\text{\ref{R7}}}}{{\longrightarrow}}\\\\[5.69054pt]
\stackrel{{\scriptstyle\text{\ref{R7}}}}{{\longrightarrow}}~{}{-}(0+(r+1))\hfill\stackrel{{\scriptstyle\text{\ref{Rm3}}}}{{\longrightarrow}}\end{array}\right]{-}((0+r)+1),$

or if $t$ is a negative normal form, e.g.,

$\displaystyle(-t)+(-(r+1))\stackrel{{\scriptstyle\text{\ref{R11}}}}{{\longrightarrow}}-((-(-t))+(r+1))\left[\begin{array}[]{l}\stackrel{{\scriptstyle\text{\ref{Rm3}}}}{{\longrightarrow}}-(((-(-t))+r)+1)\stackrel{{\scriptstyle\text{\ref{R10}}}}{{\longrightarrow}}\\\\[5.69054pt]
\stackrel{{\scriptstyle\text{\ref{R10}}}}{{\longrightarrow}}~{}{-}(t+(r+1))\hfill\stackrel{{\scriptstyle\text{\ref{Rm3}}}}{{\longrightarrow}}\end{array}\right]{-}((t+r)+1).$

However, our interest in deterministic reductions concerns nonnegative normal
forms and we return to this point in the next section. Finally, note that with
respect to multiplication of two nonnegative normal forms, the DDRS $D_{2}$ is
not deterministic:

$0\cdot(1+1)\stackrel{{\scriptstyle\text{\ref{Rm6}}}}{{\longrightarrow}}(0\cdot
1)+0\left[\begin{array}[]{l}\stackrel{{\scriptstyle\text{\ref{R4}}}}{{\longrightarrow}}0+0\stackrel{{\scriptstyle\text{\ref{R1}}}}{{\longrightarrow}}\\\\[5.69054pt]
\stackrel{{\scriptstyle\text{\ref{R1}}}}{{\longrightarrow}}~{}0\cdot
1\hfill\stackrel{{\scriptstyle\text{\ref{R4}}}}{{\longrightarrow}}\end{array}\right]0.$

##  3 DDRSes for natural number and integer arithmetic in unary view

In this section we consider a simple form of number representation that is
related to tallying and establishes a unary numeral system based on the
constant 0. The _unary append_ is the one-place (postfix) function

$\\_\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip
1.13809pt1:{\mathbb{Z}}\to{\mathbb{Z}}$

and is an alternative notation for the successor function $S(x)$. In [2,
App.C] the unary append is used to define (concrete) datatypes for natural
number arithmetic and integer arithmetic. The signature we work in is
$\Sigma_{U}=\\{0,-,~{}\\_\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip
1.13809pt1,+,\cdot\\}$, where $-$ represents the unary minus function.

For natural numbers, normal forms are 0 for zero, and applications of the
unary append function that define all successor values: each natural number
$n$ is represented by $n$ applications of the unary append to 0 and can be
seen as representing a sequence of $1$’s of length $n$ having 0 as a single
prefix, e.g.

$(0\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1)\hskip
1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1$

is the normal form that represents $2$ and can be abbreviated as $011$. We
name the resulting datatype ${\mathbb{N}}_{U}$. For integers, each minus
instance $-t$ of a nonzero normal form $t$ in ${\mathbb{N}}_{U}$ is a normal
form over $\Sigma_{U}$, e.g.

$-((0\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1)\hskip
1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1)$

is the normal form that represents $-2$ and can be abbreviated as $-011$. We
name the resulting datatype ${\mathbb{Z}}_{U}$.

In Section 3.1 we introduce concise DDRSes based on $\Sigma_{U}$. In Section
3.2 we investigate in what way the DDRS $D_{2}$ for the ring of integers is
related, and in Section 3.3 we briefly discuss the use of the successor
function as an alternative for unary append.

###  3.1 Concise DDRSes for ${\mathbb{N}}_{U}$ and ${\mathbb{Z}}_{U}$

In Table 4 we define the DDRS $\mathit{Nat}_{1}$ for the datatype
${\mathbb{N}}_{U}$ over the signature $\Sigma_{U}\setminus\\{-\\}$. This is an
alternative for the DDRS for natural number arithmetic in unary view defined
in [2, App.C], in particular equation 4 replaces the equation x⋅(y :_ u
1)&=(x⋅y)+x. Below we prove that $\mathit{Nat}_{1}$ is deterministic with
respect to addition and multiplication of two normal forms.

x+0 &=x x + (y :_ u 1) = (x :_ u 1)+y x ⋅0 &=0 x ⋅(y :_ u 1) = x+(x⋅y)

Table 4: The DDRS $\mathit{Nat}_{1}$ for ${\mathbb{N}}_{U}$, natural numbers
in unary view with unary append function

The transition to DDRSes for ${\mathbb{Z}}_{U}$ can be taken in different
ways. As an alternative to the equations for negative numbers in unary view
provided in [2, App.C], we provide in Table 5 the DDRS $\mathit{Int}_{1}$ that
defines a smaller extension of $\mathit{Nat}_{1}$ to integer numbers (thus, to
the datatype ${\mathbb{Z}}_{U}$): equation 5 replaces the three equations 0 +
x &= x,
(x :_ u 1) + (-(y :_ u 1)) = x+(-y),
(-x) + (-y) = -(x+y).

x+0 &=x x + (y :_ u 1) = (x :_ u 1)+y x ⋅0 =0 x ⋅(y :_ u 1) = x+(x⋅y) -0&=0
(-(x :_ u 1)) :_ u 1=-x -(-x) =x x+(-y)=-((-x)+y) x ⋅(-y) =-(x⋅y)

Table 5: The DDRS $\mathit{Int}_{1}$ for ${\mathbb{Z}}_{U}$ that specifies
integer arithmetic over $\Sigma_{U}$

The following example shows that with respect to addition of negative normal
forms, the DDRS $\mathit{Int}_{1}$ is not deterministic:
(-011)+01⟶4((-011)1)+0 [⟶5(-01)+0⟶4⟶4(-011)1 ⟶5] -01.

######  Lemma 3.1.1.

The DDRSes $\mathit{Nat}_{1}$ for ${\mathbb{N}}_{U}$ (Table 4), and
$\mathit{Int}_{1}$ for ${\mathbb{Z}}_{U}$ (Table 5) are strongly terminating.

###### Proof.

Modify the weight function $|x|$ defined in the proof of Lemma 2.1.1 to closed
terms over $\Sigma_{U}$ by deleting the clause $|1|=2$ and adding the clause

$\displaystyle|x\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip
1.13809pt1|=|x|+2.$

Then $|t|\geq 2$ for each closed term $t$, and thus $|t|<|t|^{|u|}$ for each
closed term $u$, so

$\displaystyle|t\cdot(u\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip
1.13809pt1)|$ $\displaystyle=|t|^{|u|+2}$ $\displaystyle\geq 4\cdot|t|^{|u|}$
$\displaystyle=|t|^{|u|}+3\cdot|t|^{|u|}$ $\displaystyle>|t|+3\cdot|t|^{|u|}$
$\displaystyle=|t+(t\cdot u)|,$

and hence each 4-rewrite step on a closed term reduces its weight. It easily
follows that all remaining equations also reduce weight, hence this DDRS for
${\mathbb{Z}}_{U}$ is strongly terminating. As a consequence, the DDRS for
${\mathbb{N}}_{U}$ is also strongly terminating. ∎

######  Theorem 3.1.2.

The DDRSes for $\mathit{Nat}_{1}$ for ${\mathbb{N}}_{U}$ (Table 4), and
$\mathit{Int}_{1}$ for ${\mathbb{Z}}_{U}$ (Table 5) are ground-complete.

###### Proof.

By Lemma 3.1.1 it remains to be shown that both these DDRSes are ground-
confluent. We prove this for the DDRS for ${\mathbb{Z}}_{U}$, which implies
ground-confluence of the DDRS for ${\mathbb{N}}_{U}$. Define the set $N$ as
follows:

$\displaystyle N$ $\displaystyle=\\{0\\}\cup N^{+}\cup N^{-},$ $\displaystyle
N^{+}$ $\displaystyle=\\{0\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip
1.13809pt1\\}\cup\\{t\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip
1.13809pt1\mid t\in N^{+}\\},$ $\displaystyle N^{-}$ $\displaystyle=\\{-t\mid
t\in N^{+}\\}.$

It immediately follows that if $t\in N$, then $t$ is a normal form (no rewrite
rule applies). Furthermore, with the semantical equation

$x\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1=x+1,$

it follows that two distinct elements in $N$ have distinct values in
${\mathbb{Z}}$, and that the equations in Table 5 are semantic consequences of
the axioms for commutative rings (Table 1). In order to prove ground-
confluence it suffices to show that for each closed term $t$ over
$\Sigma_{1}$, either $t\in N$ or $t$ has a rewrite step, so that each normal
form is in $N$.

We prove this by structural induction on $t$. The base case is simple: if
$t=0$, then $t\in N$.

For the induction step we have to distinguish four cases:

  1. 1.

Case $t=-r$. Assume that $r\in N$ and apply case distinction on $r$:

     * •

if $r=0$, then $t\to 0$ by equation 5,

     * •

if $r=r^{\prime}\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1$,
then $t\in N$,

     * •

if $r=-(r^{\prime}\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1)$,
then $t\to r^{\prime}\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1$
by equation 5.

  2. 2.

Case $t=r\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1$. Assume
that $r\in N$ and apply case distinction on $r$:

     * •

if $r=0$, then $t\in N$,

     * •

if $r=r^{\prime}\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1$,
then $t\in N$,

     * •

if $r=-(r^{\prime}\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1)$,
then $t\to-r^{\prime}$ by equation 5.

  3. 3.

Case $t=u+r$. Assume that $u,r\in N$ and apply case distinction on $r$:

     * •

if $r=0$, then $t\to u$ by equation 4,

     * •

if $r=r^{\prime}\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1$,
then $t\to(u\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip
1.13809pt1)+r^{\prime}$ by equation 4,

     * •

if $r=-(r^{\prime}\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1)$,
then $t\to-((-u)+r^{\prime}\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip
1.13809pt1)$ by equation 5.

  4. 4.

Case $t=u\cdot r$. Assume that $u,r\in N$ and apply case distinction on $r$:

     * •

if $r=0$, then $t\to 0$ by equation 4,

     * •

if $r=r^{\prime}\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1$,
then $t\to u+(u\cdot r^{\prime})$ by equation 4,

     * •

if $r=-(r^{\prime}\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1)$,
then $t\to-(u\cdot(r^{\prime}\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip
1.13809pt1))$ by equation 5.

∎

A particular property of the DDRS $\mathit{Nat}_{1}$ for ${\mathbb{N}}_{U}$ is
captured in the following proposition.

######  Proposition 3.1.3.

With respect to addition and multiplication of normal forms, the DDRS
$\mathit{Nat}_{1}$ in Table 4 is deterministic. That is, for normal forms
$t,t^{\prime}$, in each state of rewriting of $t+t^{\prime}$ and $t\cdot
t^{\prime}$ to their normal form, only one equation (rewrite rule) applies.

###### Proof.

The case for addition is simple: applicability of equations 4 or 4 excludes
the other.
The case for multiplication follows by structural induction on $t^{\prime}$.
Case $t^{\prime}=0$. Equation 4 defines the only possible rewrite step.
Case $t^{\prime}=0\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1$.
Equation 4 defines the only possible rewrite step, resulting in $t+(t\cdot
0)$, which rewrites deterministically to $t+0$ and then to $t$.
Case $t^{\prime}=(r\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip
1.13809pt1)\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1$. Equation
4 defines the only possible rewrite step, deterministically resulting in a
repeated addition $t+(t+(...+(t+0)..))$ with at least two occurrences of $t$.
It is easily seen that the only redex in any such term is $t+0$, thus it
remains to be shown that each repeated addition $t+(...+(t+t)..)$ with at
least two occurrences of $t$ rewrites deterministically, which can be shown
with induction to the length $\ell$ of this sequence.

  * •

Case $\ell=2$. According to the case for addition, $t+t$ rewrites
deterministically.

  * •

Case $\ell>2$. The only redex is in the right argument, say $s$. By induction,
$s$ rewrites deterministically to $u\hskip 1.13809pt{:_{\hskip
0.56905ptu}}\hskip 1.13809pt1$ for some normal form $u$ (not equal to 0). Thus
$t+s$ has a reduction to $t+u\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip
1.13809pt1$. In each intermediate step in this reduction, each expression has
the form $t+(u_{1}+u_{2})$ and has no redex in which $t+(..)$ occurs, thus
this reduction is also deterministic and results in $t+(u\hskip
1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1)$. According to the case for
addition, $t+(u\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1)$
rewrites deterministically.

∎

###  3.2 From the ring of integers to unary view

In this section we relate the DDRS $D_{2}$ for the ring of integers
${\mathbb{Z}}_{r}$ to integer arithmetic as defined in the previous section.
If we use $t\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1$ as an
alternative notation for $t+1$ in $D_{2}$ and then delete all equations that
contain the constant $1$, we obtain the DDRS $\mathit{Int}_{2}$ given in Table
6, which provides an alternative specification of integer arithmetic over the
signature $\Sigma_{1}$ comparable to the DDRS $\mathit{Int}_{1}$ for
${\mathbb{Z}}_{U}$ defined in Table 5. Equations 6 (replacing 4) and 6
(replacing 4) are new. Of course, $\ref{U1}+\ref{Um2}+\ref{U3}+\ref{Um4}$
define an alternative DDRS $\mathit{Nat}_{2}$ for natural number arithmetic.

x+0 &=x x + (y :_ u 1) = (x+y) :_ u 1 x ⋅0 =0 x ⋅(y :_ u 1) =(x⋅y)+x -0&=0
(-(x :_ u 1)) :_ u 1=-x -(-x) =x x+(-y)=-((-x)+y) x ⋅(-y) =-(x⋅y)

Table 6: The DDRS $\mathit{Int}_{2}$ for ${\mathbb{Z}}_{U}$, where equations 4
– 6 define the DDRS $\mathit{Nat}_{2}$ for natural number arithmetic

######  Theorem 3.2.1.

The DDRSes $\mathit{Nat}_{2}$ for ${\mathbb{N}}_{1}$ and $\mathit{Int}_{2}$
for ${\mathbb{Z}}_{1}$ (Table 6) are ground-complete.

###### Proof.

Using the weight function defined in the proof of Lemma 3.1.1, it easily
follows that these DDRSes are strongly terminating.

It remains to be shown that these DDRSes are ground-confluent and it suffices
to prove this for the DDRS $\mathit{Int}_{2}$. Equations 6 and 6 are semantic
consequences of the axioms for commutative rings. It immediately follows from
the proof of Theorem 3.1.2 that 6 implies a rewrite step if 4 does, and 6
implies a rewrite step if 4 does. Hence the DDRS $\mathit{Int}_{2}$ is ground-
complete. ∎

Furthermore, Proposition 2.2.3 implies that the DDRS $\mathit{Int}_{2}$ is
deterministic with respect to rewriting a sum of two nonnegative normal forms.
However, $\mathit{Int}_{2}$ is not deterministic with respect to
multiplication of two nonnegative normal forms:

$0\cdot(0\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip
1.13809pt1)\stackrel{{\scriptstyle\text{\ref{Um4}}}}{{\longrightarrow}}(0\cdot
0)+0\left[\begin{array}[]{l}\stackrel{{\scriptstyle\text{\ref{U1}}}}{{\longrightarrow}}~{}0\cdot
0\hfill\stackrel{{\scriptstyle\text{\ref{U3}}}}{{\longrightarrow}}\\\\[5.69054pt]
\stackrel{{\scriptstyle\text{\ref{U3}}}}{{\longrightarrow}}0+0\stackrel{{\scriptstyle\text{\ref{U1}}}}{{\longrightarrow}}\end{array}\right]0.$

###  3.3 Successor function instead of unary append

Finally, we consider the adaptations of the DDRSes defined in Sections 3.2 and
3.1 (in that order) to the successor function $S(x)$. Replacing all $t\hskip
1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1$-occurrences by $S(t)$ in
the DDRSes $\mathit{Nat}_{2}$ and $\mathit{Int}_{2}$ defined in Table 6
results in the DDRSes $\mathit{Nat}_{3}$ and $\mathit{Int}_{3}$ in Table 7,
which define alternative and concise DDRSes for natural number and integer
arithmetic in unary view with successor function. The same replacement in the
DDRSes $\mathit{Nat}_{1}$ (Table 4) and $\mathit{Int}_{1}$ (Table 5) results
in the DDRSes $\mathit{Nat}_{4}$ and $\mathit{Int}_{4}$ defined in Table 8.
Normal forms are $0,S(0),S(S(0)),\dots$ and for integers also the negations of
all nonzero normal forms.

x+0 &=x x + S(y) = S(x+y) x ⋅0 =0 x ⋅S(y) = (x⋅y)+x -0&=0 S(-S(x))=-x -(-x) =x
x+(-y)=-((-x)+y) x ⋅(-y) =-(x⋅y)

Table 7: The DDRS $\mathit{Int}_{3}$ for integer arithmetic with the constant
0 and successor function, where the equations in the left column define the
DDRS $\mathit{Nat}_{3}$ for natural number arithmetic

x+0 &=x x + S(y) = S(x)+y x ⋅0 =0 x ⋅S(y) = x+(x⋅y) -0&=0 S(-S(x))=-x -(-x) =x
x+(-y)=-((-x)+y) x ⋅(-y) =-(x⋅y)

Table 8: The DDRS $\mathit{Int}_{4}$ for integer arithmetic with the constant
0 and successor function, where the equations in the left column define the
DDRS $\mathit{Nat}_{4}$ for natural number arithmetic

Theorems 3.2.1 and 3.1.2 immediately imply the following corollary with
respect to these alternative representations.

######  Corollary 3.3.1.

The DDRSes $\mathit{Nat}_{3}$ and $\mathit{Int}_{3}$ defined in Table 7 are
ground-complete. The two DDRSes $\mathit{Nat}_{4}$ and $\mathit{Int}_{4}$
defined in Table 8 are ground-complete.

The DDRS $\mathit{Nat}_{3}$ defined in Table 7 defines natural number
arithmetic with 0 and successor function, and is very common (see, e.g. [4, 6,
8]). Furthermore, this DDRS is deterministic with respect to addition of two
normal forms (cf. Proposition 2.2.3), but not with respect to their
multiplication (cf. (5) in Section 3.2).

We note that the DDRS $\mathit{Int}_{3}$ for ${\mathbb{Z}}_{1}$ defined in
Table 7 provides an alternative of smaller size for the datatype
${\mathbb{Z}}_{ubd}$ defined in [2]111The name ${\mathbb{Z}}_{ubd}$ refers to:
${\mathbb{Z}}$ in unary view with conversion from binary and decimal notation
(and view). when in the latter the equations for predecessor and conversion
from binary and decimal notation are disregarded: equation 8, used to complete
the definition of addition on the integers, replaces equations [u8] – [u10] in
our earlier paper [2], while the remaining eight equations are those defined
in [2] for ${\mathbb{Z}}_{ubd}$.

Finally, the DDRS $\mathit{Nat}_{4}$ is deterministic with respect to addition
and multiplication of two normal forms (cf. Proposition 3.1.3). However,
equation 8 (as a rewrite rule) is less common for defining addition on this
concrete datatype for natural number arithmetic, and neither is equation 8 for
defining multiplication on the natural numbers. In [7] this specification
(modulo symmetry) occurs as a running example.

##  4 Conclusions

In this paper we specify integer arithmetic for the ring of integers and for
numbers represented in a unary numeral system by DDRSes that contain less
equations than the associated DDRSes discussed in our paper [2]. In all cases,
this is due to the equation

$x+(-y)=-((-x)+y),$

which is used to complete the definition of addition for integers for negative
normal forms.

A general property of the DDRSes defined in this paper is that the recursion
in the definitions of addition and multiplication takes place on the right
argument of these operators (as is common), if necessary first replacing
negation. Of course, we could have used recursion on the left argument
instead, obtaining symmetric versions of these DDRSes (for natural number
arithmetic with successor function, this is done in e.g. [3, 7, 9]).

In Section 2 we provided two DDRSes for the datatype ${\mathbb{Z}}_{r}$, the
ring of integers with the set $\mathit{NF}$ of normal forms defined by

$\displaystyle\mathit{NF}$
$\displaystyle=\\{0\\}\cup{\mathit{NF}^{+}}\cup{\mathit{NF}^{-}},$
$\displaystyle{\mathit{NF}^{+}}$ $\displaystyle=\\{1\\}\cup\\{t+1\mid
t\in{\mathit{NF}^{+}}\\},$ $\displaystyle{\mathit{NF}^{-}}$
$\displaystyle=\\{-t\mid t\in{\mathit{NF}^{+}}\\}.$

Each of these DDRSes consists of only twelve equations. Perhaps the DDRS
$D_{2}$ is most attractive: it is comprehensible and deterministic with
respect to addition of (two) nonnegative normal forms. We leave it as an open
question whether ${\mathbb{Z}}_{r}$ can be specified by a DDRS with less
equations (starting from the set $\mathit{NF}$ of normal forms). Another open
question is to find a DDRS for ${\mathbb{Z}}_{r}$ based on $\mathit{NF}$ that
is also deterministic with respect to rewriting $t\cdot t^{\prime}$ for
nonnegative normal forms $t$ and $t^{\prime}$.222Note that the alternative for
equation 2 suggested by the DDRS $\mathit{Int}_{2}$, that is, the equation
$x\cdot(y+1)=x+(x\cdot y)$ does not solve this open question: although the
reduction
$1\cdot((((1+1)+1)+1)+1)~{}\twoheadrightarrow~{}1+(1+(1+(1+1)))~{}\smash{\stackrel{{\scriptstyle\text{\ref{Rm3}}}}{{\longrightarrow}}}~{}1+(1+((1+1)+1))~{}\smash{\stackrel{{\scriptstyle\text{\ref{Rm3}}}}{{\longrightarrow}}}1+((1+(1+1))+1)$
is deterministic, the last term has a rewrite step to $(1+(1+(1+1)))+1$ and to
$1+(((1+1)+1)+1)$.

In Section 3 we provided two DDRSes for natural number and integer arithmetic
in unary view, based on the constant 0 and unary append (instead of successor
function). Both DDRSes for integer arithmetic contain only nine equations and
we leave it as an open question whether the concrete datatype
${\mathbb{Z}}_{1}$ can be specified as a DDRS with less equations. Concerning
their counterparts that define natural number arithmetic ($\mathit{Nat}_{1}$
and $\mathit{Nat}_{2}$, both containing four equations), the DDRS
$\mathit{Nat}_{1}$ is deterministic with respect to addition and
multiplication of normal forms (Proposition 3.1.3). Furthermore, the DDRSes
$\mathit{Nat}_{1}$ and $\mathit{Nat}_{2}$ are attractive, if only from a
didactical point of view:

  1. 1.

Positive numbers are directly related to tallying and admit an easy
representation and simplifying abbreviations for normal forms, such as 011 for
$(0\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1)\hskip
1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1$, or even 11 or $||$ when
removal of the leading zero in positive numbers is adopted.

  2. 2.

Natural number arithmetic on small numbers can be represented in a
comprehensible way that is fully independent of the learning of any positional
system for number representation, although names of numbers (zero, one, two,
and so on) might be very helpful.333In English, Dutch and German, this naming
is up to twelve independent of decimal representation, and in French this is
up to sixteen. Furthermore, notational abbreviations for units of five, like
in
1111111111or$||||$$||||$$||$or$011111~{}11111~{}11$
can be helpful because $0111111111111$ (thus twelve) is not very well readable
or easily distinguishable from $011111111111$ (thus eleven).

With respect to negative numbers, similar remarks can be made, but displaying
computations according to the DDRSes $\mathit{Int}_{1}$ and $\mathit{Int}_{2}$
will be more complex and bracketing seems to be unavoidable. Consider for
example

$(-(\;||\;))~{}+$$||||$$||||$$||$
$\displaystyle=\begin{picture}(120.0,1.0)(90.0,0.0)\put(96.0,0.0){$(-(\;||\;)\;|\;)~{}+$}
\put(160.0,0.0){$||||$} \put(157.0,-2.0){\line(2,1){18.0}}
\put(180.0,0.0){$||||$} \put(177.0,-2.0){\line(2,1){18.0}}
\put(200.0,0.0){$|$}
\end{picture}=\begin{picture}(110.0,1.0)(90.0,0.0)\put(96.0,0.0){$(-(\;|\;))~{}+$}
\put(150.0,0.0){$||||$} \put(147.0,-2.0){\line(2,1){18.0}}
\put(170.0,0.0){$||||$} \put(167.0,-2.0){\line(2,1){18.0}}
\put(190.0,0.0){$|$} \end{picture}=~{}\dots$

Although it can be maintained that as a constructor, unary append is a more
illustrative notation than successor function, it is of course only syntactic
sugar for that function. In Section 3.3 we provided DDRSes with successor
function, in order to emphasize their conciseness and comprehensibility for
integer arithmetic.

Furthermore, if we add the predecessor function $P(x)$ to the DDRSes defined
in Section 3 by the three equations

[P1] $\displaystyle P(0)$ $\displaystyle=-(0\hskip 1.13809pt{:_{\hskip
0.56905ptu}}\hskip 1.13809pt1)$ respectively $\displaystyle P(0)$
$\displaystyle=-S(0)$ [P2] $\displaystyle P(x\hskip 1.13809pt{:_{\hskip
0.56905ptu}}\hskip 1.13809pt1)$ $\displaystyle=x$ respectively $\displaystyle
P(S(x))$ $\displaystyle=x$ [P3] $\displaystyle P(-x)$ $\displaystyle=-(x\hskip
1.13809pt{:_{\hskip 0.56905ptu}}\hskip 1.13809pt1)$ respectively
$\displaystyle P(-x)$ $\displaystyle=-S(x)$

we find that the resulting DDRSes improve on those for unary view defined in
[2] in terms of simplicity and number of equations.

Finally, if we also add the subtraction function $x-y$ by the single equation

[Sub] $\displaystyle x-y$ $\displaystyle=x+(-y)\hskip 256.0748pt$

this also improves on the specification of integer arithmetic in unary view in
[8], which does not employ the unary minus function and uses seventeen rules,
and thus eighteen rules when adding the minus function by the rewrite rule

$-x~{}\to~{}0-x.$

However, we should mention that in [8], $P(0),P(P(0)),...$ are used as normal
forms for negative numbers, instead of $-(0\hskip 1.13809pt{:_{\hskip
0.56905ptu}}\hskip 1.13809pt1),-((0\hskip 1.13809pt{:_{\hskip
0.56905ptu}}\hskip 1.13809pt1)\hskip 1.13809pt{:_{\hskip 0.56905ptu}}\hskip
1.13809pt1),...$ or $-S(0),-S(S(0)),...$.

## References

  * [1] Bergstra, J.A. and Ponse, A. (2016). Fracpairs and fractions over a reduced commutative ring.  _Indagationes Mathematicae_ , 27:727–748 (doi.org/10.1016/j.indag.2016.01.007). Preprint available at arXiv/1411.4410v2 [math.RA] (2016, 22 Jan).
  * [2] Bergstra, J.A. and Ponse, A. (2016). Three datatype defining rewrite systems for datatypes of Integers each extending a datatype of Naturals. Available at arXiv:1406.3280v4 [cs.LO], 18 July 2016.
  * [3] Bouma, L.G. and Walters, H.R. (1989). Implementing algebraic specifications.  In J.A. Bergstra, J. Heering, and P. Klint (Eds.): _Algebraic Specification_ (Chapter 5), Addison-Wesley, pp. 199–282.
  * [4] Klop, J.W. and Vrijer, R.C. de (2003). _First-order term rewriting systems_. Chapter 2 in [5], pp. 24–59.
  * [5] Terese (2003). _Term Rewriting Systems_.  Cambridge Tracts in Theoretical Computer Science, Vol. 55, Cambridge University Press.
  * [6] Urso, P. and Kounalis, E. (2003). “Term partition” for mathematical induction.  In R. Nieuwenhuis (Ed.): _RTA 2003_ , Lecture Notes in Computer Science, Vol. 2706, Springer, pp. 352–366. Extended version available at https://hal.inria.fr/inria-00072023/document (2006).
  * [7] Walters, H.R. (1990). Hybrid implementations of algebraic specifications.  In H. Kirchner, W. Wechler (Eds.): _Algebraic and Logic Programming_ , Lecture Notes in Computer Science, Vol. 463, Springer, pp. 40–54.
  * [8] Walters, H.R. and Zantema, H. (1995). Rewrite systems for integer arithmetic.  In J. Hsiang (Ed.): _Rewriting Techniques and Applications (Proceedings 6th International Conference, RTA’95)_ , Lecture Notes in Computer Science, Vol. 914, Springer, pp. 324–338. Preprint available at http://oai.cwi.nl/oai/asset/4930/4930D.pdf.
  * [9] Zantema H. (2003). _Termination_. Chapter 6 in [5], pp. 181–259.