# Slowly rotating black holes with exact Killing tensor symmetries

Finnian Gray<EMAIL_ADDRESS>Perimeter Institute, 31 Caroline
Street North, Waterloo, ON, N2L 2Y5, Canada  Department of Physics and
Astronomy, University of Waterloo, Waterloo, Ontario, Canada, N2L 3G1  David
Kubizňák<EMAIL_ADDRESS>Perimeter Institute, 31 Caroline
Street North, Waterloo, ON, N2L 2Y5, Canada  Department of Physics and
Astronomy, University of Waterloo, Waterloo, Ontario, Canada, N2L 3G1

(February 15, 2022)

###### Abstract

We present a novel family of slowly rotating black hole solutions in four, and
higher dimensions, that extend the well known Lense–Thirring spacetime and
solve the field equations to linear order in rotation parameter. As “exact
metrics” in their own right, the new (non-vacuum) spacetimes feature the
following two remarkable properties: i) near the black hole horizon they can
be cast in the, manifestly regular, Painlevé–Gullstrand form and ii) they
admit exact Killing tensor symmetries. We show these symmetries are inherited
from the principal Killing–Yano tensor of the exact rotating black hole
geometry in the slow rotation limit. This provides a missing link as to how
the exact hidden symmetries emerge as rotation is switched on. Remarkably, in
higher dimensions the novel generalized Lense–Thirring spacetimes feature a
rapidly growing number of exact irreducible rank-2, as well as higher-rank,
Killing tensors – giving a first example of a physical spacetime with more
hidden than explicit symmetries.

##  I Introduction

Within the framework of Hamiltonian dynamics one can distinguish two kinds of
symmetries: explicit symmetries, that induce a non-trivial action on the
configuration space, and, dynamical symmetries, which are the genuine
symmetries of the phase space. Since the latter “remain hidden” on the
configuration space, they are sometimes referred to as hidden symmetries.

Perhaps the most familiar example of a hidden symmetry in the context of
general relativity is associated with a Killing tensor [1]. This is a
symmetric rank-$p$ tensor
$K^{\alpha_{1}\dots\alpha_{p}}=K^{(\alpha_{1}\dots\alpha_{p})}$ obeying the
following Killing tensor equation:

$\nabla^{(\beta}K^{\alpha_{1}\dots\alpha_{p})}=0\,,$ (1)

which for $p=1$ yields a Killing vector. Eq. (1) represents an overdetermined
partial differential equation that imposes severe restrictions on the
background metric, e.g. [2]. Once present in a given spacetime, Killing
tensors give rise to monomial integrals of motion for geodesic trajectories –
the most famous example being Carter’s constant in the Kerr geometry [3].
Killing tensors may also give rise to symmetry operators of the scalar wave
equation and underlie its separability [4].

Killing tensors form a subalgebra of the full algebra of symmetric tensor
fields under an operation called the Schouten–Nijenhuis (SN) bracket [5, 6].
That is, given two Killing tensors $A^{\alpha_{1}\dots\alpha_{p}}$ and
$B^{\beta_{1}\dots\beta_{q}}$, their SN bracket

$\displaystyle[A,B]_{\mbox{\tiny SN}}^{\alpha_{1}\dots\alpha_{p+q-1}}$
$\displaystyle=$ $\displaystyle
pA^{\gamma(\alpha_{1}\dots\alpha_{p-1}}\nabla_{\gamma}B^{\alpha_{p}\dots\alpha_{p+q-1})}$
(2)
$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!-qB^{\gamma(\alpha_{1}\dots\alpha_{q-1}}\nabla_{\gamma}A^{\alpha_{q}\dots\alpha_{q+p-1})}\,$

yields another Killing tensor. In terms of these brackets, the Killing tensor
equation (1) is conveniently expressed as $[K,g]_{\mbox{\tiny
SN}}^{\alpha_{1}\dots\alpha_{p}}=0$ .

A trivial example of a Killing tensor is the metric itself, another is
obtained by taking a symmetrized product of Killing vectors. If a Killing
tensor cannot be decomposed into a linear combination of products of lower
rank Killing tensors, it is called irreducible. Reducible Killing tensors are
trivial in the sense that they generate no new conserved quantities and can
typically be excluded from further considerations. While spacetimes with exact
irreducible Killing tensors are quite rare, the pivotal examples include the
Kerr family of black hole spacetimes in all dimensions [7, 8] as well as
various supergravity solutions, e.g. [9, 10].

Another, perhaps even more intricate, example of a hidden symmetry is that of
Killing–Yano tensors [11] which are in some sense the square root of
Killing–tensors. In particular, of special importance for black hole physics
is the principal Killing–Yano tensor [12, 13], which is a 2-form
$h_{\alpha\beta}$ obeying the following equations:

$\nabla_{\gamma}h_{\alpha\beta}=2g_{\gamma[\beta}\xi_{\alpha]}\,,\quad\xi_{\alpha}=-\frac{1}{3}\nabla_{\gamma}h^{\gamma}{}_{\alpha}\,.$
(3)

It turns out that starting with one such object, one may be able to generate a
whole tower of Killing tensors. The first of these (and the only one in four
dimensions) is given by

$K_{\alpha\beta}=\bigl{(}(*h)\cdot(*h)\bigr{)}_{\alpha\beta}=Q_{\alpha\beta}-\frac{1}{2}g_{\alpha\beta}Q^{\gamma}{}_{\gamma}\,,$
(4)

where $Q_{\alpha\beta}=h_{\alpha\gamma}h_{\beta}{}^{\gamma}$, and we have
defined
$(\omega\cdot\omega)_{\alpha\beta}=\frac{1}{p!}\omega_{\alpha\gamma_{1}\dots\gamma_{p}}\omega_{\beta}{}^{\gamma_{1}\dots\gamma_{p}}$
for any $(p+1)$-form $\omega$. Notably, this construction applies to the
Killing tensor of the Kerr geometry [12] and its higher-dimensional
generalizations [8], where it guarantees the complete integrability of
geodesic motion [3, 7, 14].

It is the aim of the present paper to construct a new class of solutions with
exact Killing tensors. Namely, we pick up the threads on the recent
observation [15] that an appropriately modified Lense–Thirring spacetime [16],
which describes a field of a slowly rotating body, admits the exact Killing
tensor. We show that this result can be extended to the whole family of
(possibly charged) generalized Lense–Thirring spacetimes with a cosmological
constant in four and higher dimensions.

These spacetimes are “derived” from the corresponding exact black hole
solutions (seeds) in the slow rotation approximation. As such they inherit the
approximate hidden symmetries of the exact seed solutions. Remarkably, when
these metrics are “appropriately modified”, the approximate Killing tensor
symmetry becomes exact. In addition, the obtained spacetimes are regular on
the black hole horizon and close to its vicinity can be cast in the
Painlevé–Gullstrand (PG) form, see [17, 18].

##  II Exact Kerr–Newmann-AdS solution and its slow rotation expansion

To start our discussion, let us recapitulate the exact
Einstein–Maxwell-$\Lambda$ solution for a rotating black hole – known as the
Kerr–Newmann-AdS metric [19], which we write in the “standard Boyer–Lindquist
form” [20]:

$\displaystyle ds^{2}$ $\displaystyle=$
$\displaystyle-\frac{\Delta}{\Sigma}\left[dt-\frac{a\sin^{2}\\!\theta}{\Xi}d\phi\right]^{2}+\frac{\Sigma}{\Delta}dr^{2}+\frac{\Sigma}{S}d\theta^{2}$
$\displaystyle+\frac{S\sin^{2}\\!\theta}{\Sigma}\left[adt-\frac{r^{2}+a^{2}}{\Xi}d\phi\right]^{2}\,,$
$\displaystyle{A}$ $\displaystyle=$
$\displaystyle-\frac{qr}{\Sigma}\left(dt-\frac{a\sin^{2}\\!\theta}{\Xi}d\phi\right)\,,$
(5)

where $A$ is the vector potential and $F=dA$ the corresponding field strength,
$a$ is the rotation parameter,

$\displaystyle\Sigma$ $\displaystyle=$ $\displaystyle
r^{2}+a^{2}\cos^{2}\\!\theta\,,\quad\Xi=1-\frac{a^{2}}{\ell^{2}}\,,\quad
S=1-\frac{a^{2}}{\ell^{2}}\cos^{2}\\!\theta\,,$ $\displaystyle\Delta$
$\displaystyle=$
$\displaystyle(r^{2}+a^{2})\Bigl{(}1+\frac{r^{2}}{\ell^{2}}\Bigr{)}-2mr+q^{2}\,,$
(6)

$m$ and $q$ are the mass and charge parameters, and $\ell$ is the AdS radius.
One can check that the geometry at the horizon, located at $r=r_{+}$, given by
the largest root $\Delta(r_{+})$ is regular, and in particular, the
Kretschmann scalar,

$I=R_{\alpha\beta\gamma\delta}R^{\alpha\beta\gamma\delta}\,,$ (7)

is smooth at $r=r_{+}$. As written, the solution rotates at infinity – this
rotation can be removed by “going to the non-rotating frame”: $d\phi\to
d\phi-a/\ell^{2}dt$.

The metric is the algebraically special type D and admits a fundamental hidden
symmetry, encoded in the principal Killing–Yano tensor $h$, which obeys (3),
and is explicitly given by $h=db$ , where

$2b=r^{2}\bigl{(}dt-a\sin^{2}\\!\theta\frac{d\phi}{\Xi}\bigr{)}-a^{2}\cos^{2}\\!\theta\bigl{(}dt-\frac{ad\phi}{\Xi}\bigr{)}\,.$
(8)

The corresponding irreducible Killing tensor, constructed from $h$ according
to (4), reads:

$\displaystyle K$ $\displaystyle=$
$\displaystyle\frac{a^{2}\cos^{2}\\!\theta}{\Delta\Sigma}\Bigl{(}(r^{2}+a^{2})\partial_{t}+a\Xi\partial_{\phi}\Bigr{)}^{2}-\frac{a^{2}\cos^{2}\\!\theta\Delta}{\Sigma}(\partial_{r})^{2}$
(9) $\displaystyle+\frac{r^{2}}{\Sigma
S\sin^{2}\\!\theta}(a\sin^{2}\\!\theta\partial_{t}+\Xi\partial_{\phi})^{2}+\frac{Sr^{2}}{\Sigma}(\partial_{\theta})^{2}\,.$

Together with the two explicit symmetries, $\partial_{t}$ and
$\partial_{\phi}$, it guarantees the complete integrability of geodesic motion
in these spacetimes [19, 21].

Let us now perform the linear in $a$ expansion to the above exact solution.
This yields the following approximate to $O(a)$ solution of the
Einstein–Maxwell-$\Lambda$ equations:

$\displaystyle ds^{2}$ $\displaystyle=$ $\displaystyle-
fdt^{2}+\frac{dr^{2}}{f}+2a\sin^{2}\\!\theta(f-1)dtd\phi\,,$
$\displaystyle+r^{2}\sin^{2}\\!\theta d\phi^{2}+r^{2}d\theta^{2}+O(a^{2})\,,$
$\displaystyle A$ $\displaystyle=$
$\displaystyle-\frac{q}{r}\bigr{(}dt-a\sin^{2}\\!\theta
d\phi\bigr{)}+O(a^{2})\,,$ (10)

where

$f=1-\frac{2M}{r}+\frac{q^{2}}{r^{2}}+\frac{r^{2}}{\ell^{2}}\,.$ (11)

Of course, the spacetime inherits the hidden symmetries of the full solution
to the linear order in $a$, given by

$\displaystyle 2b$ $\displaystyle=$
$\displaystyle{r^{2}}dt-{ar^{2}\sin^{2}\\!\theta}d\phi+O(a^{2})\,,$ (12)
$\displaystyle K$ $\displaystyle=$ $\displaystyle
2a\partial_{t}\partial_{\phi}+\frac{1}{\sin^{2}\\!\theta}(\partial_{\phi})^{2}+(\partial_{\theta})^{2}+O(a^{2})\,.$
(13)

Note that since the metric is stationary and axisymmetric, the first term in
(13) is just a product of Killing vectors and can be excluded.

A tempting possibility is to truncate the $O(a^{2})$ terms in (10), and treat
the resultant fields as “exact” (not necessarily a solution of the field
equations). However, the spacetime has several “drawbacks”. Namely, as exact
metric, it is singular on what would be the black hole horizon $f=0$, noting
for example that the Kretschmann scalar (7) diverges there at $O(a^{2})$.
Second, both (truncated to $O(a)$) hidden symmetries (12) and (13) remain only
approximate. Finally, the metric cannot be cast in the PG form [22].

##  III Generalized Lense–Thirring metric

To fix the above “drawbacks”, let us instead consider the following
modification of the above slowly rotating solution:

$\displaystyle ds^{2}$ $\displaystyle=$ $\displaystyle-
fdt^{2}+\frac{dr^{2}}{f}+r^{2}\sin^{2}\\!\theta\Bigl{(}d\phi\\!+\\!\frac{a(f-1)}{r^{2}}dt\Bigr{)}^{2}\\!\\!+\\!r^{2}d\theta^{2}\,,$
$\displaystyle A$ $\displaystyle=$
$\displaystyle-\frac{q}{r}\Bigl{(}dt-a\sin^{2}\\!\theta\bigl{[}d\phi+\frac{a}{fr^{2}}dr\bigr{]}\Bigr{)}\,,$
(14)

with metric function $f$ given by Eq. (11). In what follows, we shall call it
the generalized Lense–Thirring solution, c.f. [22]. Formally, it can be
obtained by “completing the square” in the truncated solution (10) (together
with an appropriate modification of the vector potential $A$ to achieve
regularity of the electromagnetic invariants on the horizon). As such, it
still solves the Einstein–Maxwell-$\Lambda$ system to $O(a)$, as well as
admitting the approximate hidden symmetries (12) and (13).

However, when understood as an exact (filled with matter) spacetime,111One
should be a bit cautious about the physicality of the extra matter supporting
the (modified) Lense–Thirring spacetimes. In particular, when $Q=0=\Lambda$,
the tetrad component of the Einstein tensor is
$G^{\hat{0}\hat{0}}=-\frac{1}{2}R=-(3aM\sin\theta/r^{4})^{2}$, yielding a
negative energy density [22]. This is partly emended in the presence of the
additional ordinary matter – for example in our case the EM field dominates
near infinity and guarantees there positive energy density. However, we expect
that the generic Lense–Thirring spacetimes may need to be (at least partly)
supported by exotic matter violating the standard energy conditions.  it is a
much better approximation for a slowly rotating black hole than the above
truncated solution since it is regular on the horizon – the curvature scalars,
such as $I$ (7), no longer diverge at $f=0$ and the metric can be cast (at
least in the vicinity of the horizon) in the manifestly regular PG form, see
appendix A for more details. It also has an ergosphere and will feature
superradiant phenomena, e.g. [23]. Most remarkably, the generalized
Lense–Thirring spacetime (III) falls into a class of the Benenti and
Francaviglia metrics [24] (see also [25] for some recent applications). This
means that not only does the metric posses an exact Killing tensor, the
separability of the scalar wave equation and integrability of the geodesics
are guaranteed.222In particular, one can check that Carter’s criterion [4]
$\nabla_{\alpha}(k_{\gamma}{}^{[\alpha}R^{\beta]\gamma})$=0 is satisfied.
Interestingly, one can also check that the criteria required for separability
of the conformally coupled scalar equation are not satisfied, even though this
equation does separate for Kerr–NUT–AdS spacetimes [26]..

The corresponding exact Killing tensor is given by

$K=\frac{1}{\sin^{2}\\!\theta}(\partial_{\phi})^{2}+(\partial_{\theta})^{2}\,,$
(15)

and can be understood as a slow rotation (truncated) version of the
approximate Killing tensor (13). Interestingly, this Killing tensor can be
written in the following suggestive form:

$K=L_{x}^{2}+L_{y}^{2}+L_{z}^{2}\,,$ (16)

where $L_{z}=\partial_{\phi}$ is a Killing vector of (III) and vectors $L_{x}$
and $L_{y}$ are given by

$\displaystyle L_{x}$ $\displaystyle=$
$\displaystyle\cot\theta\cos\phi\partial_{\phi}+\sin\phi\partial_{\theta}\,,$
$\displaystyle L_{y}$ $\displaystyle=$
$\displaystyle-\cot\theta\sin\phi\partial_{\phi}+\cos\phi\partial_{\theta}\,,$
(17)

which upon recovering the spherical symmetry ($a\to 0$) would be the remaining
two $SO(3)$ Killing vectors. Since $L_{z}$ and $\partial_{t}$ are the only two
Killing vectors present in the spacetime (III), it can be checked that the
above Killing tensor is irreducible.

Moreover, we may define the following 2-form:

$h^{(0)}=db^{(0)}\,\quad 2b^{(0)}=r^{2}dt\,,$ (18)

obtained by the $a\to 0$ limit of the 2-form (12). While this is not a
principal tensor even to the linear order in $a$, it yields the above exact
Killing tensor (15) via the formula (4) (with $h\to h^{(0)}$). We also note
that

$\xi^{(0)}=-\frac{1}{3}\nabla\cdot
h^{(0)}=\partial_{t}+a\Bigl{(}\frac{q^{2}}{3r^{4}}-\frac{1}{\ell^{2}}\Bigr{)}\partial_{\phi}\,,$
(19)

which is an _exact_ Killing vector when $q=0$.

Let us finally mention that the generalized Lense–Thirring spacetime (III) is,
contrary to the exact solution (II), algebraically general and describes a
slowly rotating charged black hole (or rotating body) that can be assigned the
following asymptotic charges:

$M=m\,,\quad J=ma\,,\quad Q=q\Bigl{(}1+\frac{2a^{2}}{3\ell^{2}}\Bigr{)}\,,$
(20)

and is surrounded by (charged) matter. To linear order in $a$, the
corresponding first law of black hole thermodynamics coincides with that of
the spherical charged AdS black hole, e.g. [27].

##  IV Higher-dimensional Lense–Thirring spacetimes

The above construction becomes even more remarkable in higher dimensions. To
illustrate this, let us start from the full Kerr-AdS metric in $d$ spacetime
dimensions [28]:

$\displaystyle ds^{2}$ $\displaystyle=$
$\displaystyle-W(1+r^{2}/\ell^{2})dt^{2}+\frac{2M}{U}\Bigl{(}Wdt+\sum_{i=1}^{m}\frac{a_{i}\mu_{i}^{2}d\phi_{i}}{\Xi_{i}}\Bigr{)}^{2}$
(21)
$\displaystyle+\sum_{i=1}^{m}\frac{r^{2}+a_{i}^{2}}{\Xi_{i}}\bigl{(}\mu_{i}^{2}d\phi_{i}^{2}+d\mu_{i}^{2})+\frac{Udr^{2}}{V-2M}+\epsilon
r^{2}d\nu^{2}$
$\displaystyle+\frac{1}{W(l^{2}-r^{2})}\Bigl{(}\sum_{i=1}^{m}\frac{r^{2}+a_{i}^{2}}{\Xi_{i}}\mu_{i}d\mu_{i}+\epsilon
r^{2}\nu d\nu\Bigr{)}^{2}\,,$

where

$\displaystyle W$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{m}\frac{\mu_{i}^{2}}{\Xi_{i}}+\epsilon\nu^{2}\,,\quad
V=r^{\epsilon-2}(1+r^{2}/\ell^{2})\prod_{i=1}^{m}(r^{2}+a_{i}^{2})\,,$
$\displaystyle U$ $\displaystyle=$
$\displaystyle\frac{V}{1+r^{2}/\ell^{2}}\Bigl{(}1-\sum_{i=1}^{m}\frac{a_{i}^{2}\mu_{i}^{2}}{r^{2}+a_{i}^{2}}\Bigr{)}\,,\quad\Xi_{i}=1-\frac{a_{i}^{2}}{\ell^{2}}\,.$
(22)

Here, $\epsilon=1,0$ for even, odd dimensions,
$m=\bigl{[}\frac{d-1}{2}\bigr{]}$ (where $[A]$ denotes the whole part of $A$),
and the coordinates $\mu_{i}$ and $\nu$ obey a constraint

$\sum_{i=1}^{m}\mu_{i}^{2}+\epsilon\nu^{2}=1\,.$ (23)

The metric admits [13, 8] a principal Killing–Yano tensor, $h=db$,

$2b=\Bigl{(}r^{2}+\sum_{\mu=1}^{m}a_{i}^{2}\mu_{i}^{2}(1+\frac{r^{2}+a_{i}^{2}}{\ell^{2}\Xi_{i}}\Bigr{)}dt+\sum_{i=1}^{m}a_{i}\mu_{i}^{2}\frac{r^{2}+a_{i}^{2}}{\Xi_{i}}d\phi_{i}\,,$
(24)

which generates the towers of explicit and hidden symmetries, see [8].

By repeating the procedure above, we arrive at the following slowly rotating
generalized Lense–Thirring solution (written now in non-rotating at infinity
coordinates):

$\displaystyle ds^{2}$ $\displaystyle=$ $\displaystyle-
fdt^{2}+\frac{dr^{2}}{f}+r^{2}\sum_{i=1}^{m}\mu_{i}^{2}\Bigl{(}d\phi_{i}+\frac{2Ma_{i}}{r^{2m+\epsilon}}dt\Bigr{)}^{2}$
(25) $\displaystyle+$
$\displaystyle\\!r^{2}(\sum_{i=1}^{m}\\!d\mu_{i}^{2}\\!+\\!\epsilon
d\nu^{2})\,,\
f\\!=\\!1-\frac{2M}{r^{2m-2+\epsilon}}+\frac{r^{2}}{\ell^{2}}\,.\ $

As before, the metric is regular on the horizon, $f=0$, near its vicinity
admits the PG form (see appendix A), and inherits the following approximate
principal Killing–Yano tensor:

$2b=r^{2}dt+r^{2}\sum_{i=1}^{m}a_{i}\mu_{i}^{2}d\phi_{i}\,.$ (26)

Surprisingly, in addition, we have a fast growing (with number of dimensions)
tower of exact Killing tensors. Explicitly, let us define the set
$S=\\{1,..,m\\}$ and let $I\in P(S)$ where $P(S)$ is the power set of $S$,
then we have the following objects:

$\displaystyle 2b^{(I)}$ $\displaystyle\equiv r^{2}(dt+\sum_{i\in
I}a_{i}\mu_{i}^{2}d\phi_{i})\,,\quad\,h^{(I)}\equiv db^{(I)}\,,$ (27)
$\displaystyle f^{(I)}$
$\displaystyle\equiv\frac{1}{(|I|+1)!}*\big{(}\underbrace{h^{(I)}\wedge\dots\wedge
h^{(I)}}_{|I|+1\ \mbox{\tiny times}}\big{)}\,,$ (28)

where $|I|$ denotes the size of the set $I$. These generate the following
exact rank-2 Killing tensors:

$\displaystyle K^{(I)}_{\mu\nu}$ $\displaystyle=\big{(}\prod_{i\in
I}a_{i}\big{)}^{-2}\,(f^{(I)}\cdot f^{(I)})_{\mu\nu}\,.$ (29)

Note that, this construction “coincides” with the one for the full Kerr-AdS
geometry [8], replacing the principal Killing–Yano tensor $h$ with its
appropriate limits $h^{(I)}$ at the relevant order of the small rotation
parameters expansion.

Of course, in a given dimension, not all of these are non-trivial. In fact, it
is only $K^{(\emptyset)}$ which exists in all dimensions $d\geq 4$, and is
given by our familiar formula (4) (with $h\to h^{(\emptyset)}$). Explicitly,
these Killing tensors take the following simple form:

$\displaystyle K^{(I)}$ $\displaystyle=\\!\\!\\!\\!\\!\sum\limits_{i\not\in
I}^{m-1+\epsilon}\\!\bigg{[}\bigr{(}1-\mu_{i}^{2}-\\!\sum_{j\in
I}\mu_{j}^{2}\bigr{)}(\partial_{\mu_{i}})^{2}-2\\!\\!\\!\\!\sum_{j\not\in
I\cup\\{i\\}}\\!\\!\\!\\!\mu_{i}\mu_{j}\,\partial_{\mu_{i}}\partial_{\mu_{j}}\bigg{]}$
$\displaystyle+\sum\limits_{i\not\in I}^{m}\bigg{[}\frac{1-\sum_{j\in
I}\mu^{2}_{j}}{\mu_{i}^{2}}(\partial_{\phi_{i}})^{2}\bigg{]}\,.$ (30)

It turns out, however, that $\sum_{i=0}^{m-3}{m\choose i}$ of these are
reducible, leaving

$k=\sum_{i=0}^{m-2+\epsilon}{m\choose i}-\sum_{i=0}^{m-3}{m\choose
i}=\frac{1}{2}m(m-1+2\epsilon)$ (31)

irreducible rank-2 Killing tensors in $d$ dimensions. Contrary to the exact
Kerr-AdS spacetimes whose number of rank-2 Killing tensors grows linearly with
number of spacetime dimensions, in our case the growth is quadratic. For
example, already in $d=8$ we have (for distinct rotation parameters) 6
irreducible rank-2 Killing tensors and only $m+1=4$ independent Killing
vectors – that is the number of hidden symmetries exceeds the number of the
explicit ones (more so once we also count higher rank Killing tensors obtained
by various combinations of SN brackets – see below). However, this is still
much smaller than the maximum possible number of rank-2 Killing tensors in a
given dimension $d$, which for rank-$p$ Killing tensor $(p\geq 1)$ reads, e.g.
[2]:

$k_{\max}=\frac{1}{d}\Bigl{(}\begin{matrix}d+p\\\
p+1\end{matrix}\Bigr{)}\Bigl{(}\begin{matrix}d+p-1\\\
p\end{matrix}\Bigr{)}\,,$ (32)

and for $d=8$ and $p=2$ gives $k_{\max}=540$.

In addition to the above rank-2 Killing tensors, one can also generate
(potentially irreducible) higher-rank Killing tensors via the SN brackets (2).
Our construction thus provides a physically well motivated example in the
long-standing search for spacetimes with higher-rank Killing tensors [29, 30,
31]. Of course, these objects are, at the same time, approximate (to linear
order in rotation parameters) higher-rank Killing tensors for the full Kerr-
AdS geometry (21). We have verified up to $d=13$ that the SN bracket of any
two Killing tensors vanishes if the intersection of the two labels equals the
first. That is,

$[K^{(I_{1})},K^{(I_{2})}]_{\mbox{\tiny SN}}=0\,,$ (33)

if $I_{1}\cap I_{2}=I_{1}$. Otherwise, a new Killing tensor is generated. In
particular, in $d$ dimensions this implies (taking into account explicit
symmetries and the metric as well) the existence of $d$ mutually commuting
symmetry objects – a necessary requirement for complete (and again exact)
integrability of geodesic motion in the spacetime (25). We expect this to
remain true also in higher dimensions.

Finally we close by illustrating the above construction in $d=6$ dimensions.
In this case $k=3$ and we have the following irreducible rank-2 Killing
tensors:

$\displaystyle K^{(\emptyset)}$ $\displaystyle=$
$\displaystyle\frac{1}{\mu_{1}^{2}}(\partial_{\phi_{1}})^{2}+\frac{1}{\mu_{2}^{2}}(\partial_{\phi_{2}})^{2}+(1-\mu_{1}^{2})(\partial_{\mu_{1}})^{2}$
$\displaystyle-2\mu_{1}\mu_{2}(\partial_{\mu_{1}})(\partial_{\mu_{2}})+(1-\mu_{2}^{2})(\partial_{\mu_{2}})^{2}\,,$
$\displaystyle K^{(1)}$ $\displaystyle=$
$\displaystyle\frac{1-\mu_{1}^{2}}{\mu_{2}^{2}}(\partial_{\phi_{2}})^{2}-(1-\mu_{1}^{2}-\mu_{2}^{2})(\partial_{\mu_{2}})^{2}\,,$
(34) $\displaystyle K^{(2)}$ $\displaystyle=$
$\displaystyle\frac{1-\mu_{2}^{2}}{\mu_{1}^{2}}(\partial_{\phi_{1}})^{2}-(1-\mu_{1}^{2}-\mu_{2}^{2})(\partial_{\mu_{1}})^{2}\,.$

Their SN brackets are

$[K^{(\emptyset)},K^{(1)}]_{\mbox{\tiny
SN}}=0=[K^{(\emptyset)},K^{(2)}]_{\mbox{\tiny SN}}\,,\
M=[K^{(1)},K^{(2)}]_{\mbox{\tiny SN}}\,,$ (35)

where $M$ is the new rank-3 Killing tensor with the following components:

$\displaystyle M^{\mu_{1}\mu_{2}\mu_{2}}$ $\displaystyle=$
$\displaystyle-\frac{4\mu_{1}(\mu_{1}^{2}+\mu_{2}^{2}-1)}{3}=\mu_{2}^{2}M^{\phi_{2}\phi_{2}\mu_{1}}\,,$
$\displaystyle M^{\mu_{1}\mu_{1}\mu_{2}}$ $\displaystyle=$
$\displaystyle\frac{4\mu_{2}(\mu_{1}^{2}+\mu_{2}^{2}-1)}{3}=\mu_{1}^{2}M^{\phi_{1}\phi_{1}\mu_{2}}\,.$
(36)

Provided no additional irreducible rank-2 Killing tensors exist in this
spacetime, $M$ is also irreducible. This tensor further generates rank-4
Killing tensors via SN brackets with $K^{(1)}$ and $K^{(2)}$, and so on.

##  V Conclusions

Starting in four dimensions, we have seen how a “small modification” of the
linear in $a$ expansion of the exact Kerr–Newmann-AdS black hole solution
gives rise to an, in many ways, preferred slowly rotating geometry. This
generalized Lense–Thirring spacetime, is (when taken as an exact metric)
manifestly regular on the black hole horizon and admits an exact Killing
tensor.

This observation fills an important gap in understanding as to how the exact
hidden symmetries of the full Kerr–Newmann-AdS geometry emerge as the rotation
is switched on. While the non-rotating (spherical) solution admits an exact
principal Killing–Yano and Killing tensor, these are trivial, the latter being
reducible – given by a product of Killing vectors derived from the rotational
symmetry (and possibly time independence). Adding a small rotation to $O(a)$
breaks the full rotational symmetry and the approximate hidden symmetries
become non-trivial. Remarkably a simple modification of the metric at
$O(a^{2})$ yields a spacetime which in 4 dimensions is of the Benenti and
Francaviglia class of spacetimes [24] in which separability of the Klein-
Gordon and Hamilton–Jacobi equations is guaranteed. The exact irreducible
Killing tensor can be understood as a (truncated) version of the approximate
Killing tensor generated from the approximate principal Killing–Yano tensor.
Both these hidden symmetries become exact, when the full Kerr–Newmann-AdS
solution is considered.

Naturally, a similar construction also works in higher dimensions, which we
have explicitly demonstrated for Kerr-AdS spacetimes in all dimensions,
however the structure is much richer. The corresponding generalized
Lense–Thirring spacetimes admit a rapidly growing tower of exact rank-2 and
higher-rank Killing tensors, that is a “slow rotation seed” of the associated
(much smaller) tower of rank-2 Killing tensors for the full Kerr-AdS geometry.
Although the higher-dimensional Lense–Thiring spacetime (25) is not explicitly
in the Benenti–Francaviglia form, we have a tower of Killing tensors growing
faster than the number of Killing vectors – providing a first example of a
physically interesting spacetime with larger number of hidden symmetries than
the explicit ones.

We expect this construction to be quite general and apply to many other
rotating black hole spacetimes with hidden symmetries (e.g. [9, 10]). In
particular, note that while in our paper we have focused on negative
$\Lambda$, the same construction would also work for $\Lambda$ positive. It
remains an interesting open question whether similar construction would also
work for higher order expansions in rotation parameters, providing thus even a
more complete link between the generalized Lense–Thirring spacetimes and the
exact black hole solutions.

## Acknowledgements

F.G. acknowledges support from the Natural Sciences and Engineering Research
Council of Canada (NSERC) via a Vanier Canada Graduate Scholarship. This work
was supported by the Perimeter Institute for Theoretical Physics and by NSERC.
Research at Perimeter Institute is supported in part by the Government of
Canada through the Department of Innovation, Science and Economic Development
Canada and by the Province of Ontario through the Ministry of Colleges and
Universities. Perimeter Institute and the University of Waterloo are situated
on the Haldimand Tract, land that was promised to the Haudenosaunee of the Six
Nations of the Grand River, and is within the territory of the Neutral,
Anishnawbe, and Haudenosaunee peoples.

## References

  * [1] M. Walker and R. Penrose, _On quadratic first integrals of the geodesic equations for type{22} spacetimes_, _Commun. Math. Phys._ 18 (1970) 265.
  * [2] T. Houri, K. Tomoda and Y. Yasui, _On integrability of the Killing equation_ , _Class. Quant. Grav._ 35 (2018) 075014 [1704.02074].
  * [3] B. Carter, _Global structure of the Kerr family of gravitational fields_ , _Phys. Rev._ 174 (1968) 1559.
  * [4] B. Carter, _Killing Tensor Quantum Numbers and Conserved Currents in Curved Space_ , _Phys. Rev. D_ 16 (1977) 3395.
  * [5] J.A. Schouten, _Uber differentialkomitanten zweier kontravarianter grossen_ , in _Proc. Kon. Ned. Akad. Wet. Amsterdam_ , vol. 43, pp. 449–452, 1940.
  * [6] A. Nijenhuis, _Jacobi-type identities for bilinear differential concomitants of certain tensor fields_ , _Indag. Math._ 17 (1955) 390.
  * [7] V.P. Frolov and D. Stojkovic, _Particle and light motion in a space-time of a five-dimensional rotating black hole_ , _Phys. Rev. D_ 68 (2003) 064011 [gr-qc/0301016].
  * [8] V. Frolov, P. Krtous and D. Kubiznak, _Black holes, hidden symmetries, and complete integrability_ , _Living Rev. Rel._ 20 (2017) 6 [1705.05482].
  * [9] Z.W. Chong, M. Cvetic, H. Lu and C.N. Pope, _General non-extremal rotating black holes in minimal five-dimensional gauged supergravity_ , _Phys. Rev. Lett._ 95 (2005) 161301 [hep-th/0506029].
  * [10] D.D.K. Chow, _Symmetries of supergravity black holes_ , _Class. Quant. Grav._ 27 (2010) 205009 [0811.1264].
  * [11] K. Yano, _Some remarks on tensor fields and curvature_ , _Annals of Mathematics_ (1952) 328.
  * [12] R. Floyd, _The dynamics of Kerr fields_ , _PhD Thesis, London_ (1973) .
  * [13] V.P. Frolov and D. Kubiznak, _Hidden Symmetries of Higher Dimensional Rotating Black Holes_ , _Phys. Rev. Lett._ 98 (2007) 011101 [gr-qc/0605058].
  * [14] D.N. Page, D. Kubiznak, M. Vasudevan and P. Krtous, _Complete integrability of geodesic motion in general Kerr-NUT-AdS spacetimes_ , _Phys. Rev. Lett._ 98 (2007) 061102 [hep-th/0611083].
  * [15] J. Baines, T. Berry, A. Simpson and M. Visser, _Killing Tensor and Carter Constant for Painlevé–Gullstrand Form of Lense–Thirring Spacetime_ , _Universe_ 7 (2021) 473 [2110.01814].
  * [16] J. Lense and H. Thirring, _On the influence of the proper rotation of a central body on the motion of the planets and the moon, according to Einstein’s theory of gravitation_ , _Zeitschrift für Physik_ 19 (1918) 156.
  * [17] K. Martel and E. Poisson, _Regular coordinate systems for Schwarzschild and other spherical space-times_ , _Am. J. Phys._ 69 (2001) 476 [gr-qc/0001069].
  * [18] V. Faraoni and G. Vachon, _When Painlevé–Gullstrand coordinates fail_ , _Eur. Phys. J. C_ 80 (2020) 771 [2006.10827].
  * [19] B. Carter, _Hamilton-Jacobi and Schrodinger separable solutions of Einstein’s equations_ , _Commun. Math. Phys._ 10 (1968) 280.
  * [20] S.W. Hawking, C.J. Hunter and M. Taylor, _Rotation and the AdS / CFT correspondence_ , _Phys. Rev. D_ 59 (1999) 064005 [hep-th/9811056].
  * [21] B. Carter, _A new family of Einstein spaces_ , _Physics Letters A_ 26 (1968) 399.
  * [22] J. Baines, T. Berry, A. Simpson and M. Visser, _Painlevé–Gullstrand form of the Lense–Thirring Spacetime_ , _Universe_ 7 (2021) 105 [2006.14258].
  * [23] R. Brito, V. Cardoso and P. Pani, _Superradiance: New Frontiers in Black Hole Physics_ , _Lect. Notes Phys._ 906 (2015) pp.1 [1501.06570].
  * [24] S. Benenti and M. Francaviglia, _Remarks on certain separability structures and their applications to general relativity_ , _General Relativity and Gravitation_ 10 (1979) 79.
  * [25] G.O. Papadopoulos and K.D. Kokkotas, _On Kerr black hole deformations admitting a Carter constant and an invariant criterion for the separability of the wave equation_ , _Gen. Rel. Grav._ 53 (2021) 21 [2007.12125].
  * [26] F. Gray, T. Houri, D. Kubizňák and Y. Yasui, _Symmetry operators for the conformal wave equation in rotating black hole spacetimes_ , _Phys. Rev. D_ 104 (2021) 084042 [2101.06700].
  * [27] D. Kubiznak and R.B. Mann, _P-V criticality of charged AdS black holes_ , _JHEP_ 07 (2012) 033 [1205.0559].
  * [28] G.W. Gibbons, H. Lu, D.N. Page and C.N. Pope, _Rotating black holes in higher dimensions with a cosmological constant_ , _Phys. Rev. Lett._ 93 (2004) 171102 [hep-th/0409155].
  * [29] J. Brink, _Spacetime Encodings II - Pictures of Integrability_ , _Phys. Rev. D_ 78 (2008) 102002 [0807.1179].
  * [30] G.W. Gibbons, T. Houri, D. Kubiznak and C.M. Warnick, _Some Spacetimes with Higher Rank Killing-Stackel Tensors_ , _Phys. Lett. B_ 700 (2011) 68 [1103.5366].
  * [31] M. Cariglia and A. Galajinsky, _Ricci-flat spacetimes admitting higher rank Killing tensors_ , _Phys. Lett. B_ 744 (2015) 320 [1503.02162].

##  Appendix A Painlevé–Gullstrand form

In what follows we shall demonstrate that the generalized Lense–Thirring
spacetimes can, at least in the vicinity of the black hole horizon, be cast in
the PG form [17, 18]. As we shall see this can be formally achieved by a
simple coordinate transformation, c.f. [22, 15].

Let us start in four dimensions, having the solution (III). The PG coordinates
are traditionally associated with a free-falling observer starting from rest
at infinity and moving (at infinity) radially inward. However, since our
metrics have possibly AdS asymptotics, this is no longer achievable (due to
the AdS “attraction” timelike geodesics do not reach asymptotic infinity).
Formally, however, one can consider radially infalling observers starting from
rest at a finite radius from the black hole, determined for simplicity by
$f(r_{0})=1$ – restricting to regions with $f\leq 1$. (For asymptotically flat
spacetimes $r_{0}$ approaches infinity.) The corresponding 4-velocity then
reads:

$u=dt+\frac{\sqrt{1-f}}{f}dr\,.$ (37)

Setting the latter equal to $dT$, where $T$ is the proper time of the
observer, we arrive at the following coordinate transformation:

$dt=dT-\frac{\sqrt{1-f}}{f}dr\,,$ (38)

upon which the solution (III) can be written as

$\displaystyle ds^{2}$ $\displaystyle=$ $\displaystyle-
dT^{2}+(dr+\sqrt{1-f}dT)^{2}+r^{2}d\theta^{2}$ $\displaystyle+$ $\displaystyle
r^{2}\sin^{2}\\!\theta\Bigl{(}d\phi+\frac{a(f-1)}{r^{2}}dT-\frac{a(f-1)\sqrt{1-f}}{r^{2}f}dr\Bigr{)}^{2}\,,$
$\displaystyle A$ $\displaystyle=$
$\displaystyle-\frac{q}{r}\Bigl{(}dT-a\sin^{2}\\!\theta\bigl{[}d\phi+\frac{a}{fr^{2}}dr\bigr{]}\Bigr{)}\,.$
(39)

Here we have dropped the pure gauge term proportional to $dr$. Formally, one
can bring the metric in the PG form by setting

$d\phi=d\Phi+\frac{a(f-1)\sqrt{1-f}}{r^{2}f}dr\,,$ (40)

upon which we recover

$\displaystyle ds^{2}$ $\displaystyle=$ $\displaystyle-
dT^{2}+(dr+\sqrt{1-f}dT)^{2}+r^{2}d\theta^{2}$ (41)
$\displaystyle+r^{2}\sin^{2}\\!\theta\Bigl{(}d\Phi+\frac{a(f-1)}{r^{2}}dT\Bigr{)}^{2}\,,$
$\displaystyle A$ $\displaystyle=$
$\displaystyle-\frac{q}{r}\Bigl{(}dT-a\sin^{2}\\!\theta\Bigl{[}d\Phi+\frac{a(1+\sqrt{1-f}(f-1))}{fr^{2}}dr\Bigr{]}\Bigr{)}\,.$

Obviously, the spatial hypersurfaces $T=$const. are all intrinsically flat,
and the metric as well as the vector potential are manifestly non-singular for
$f=0$. The fact that the Lense–Thirring spacetimes can be brought into the PG
form by a coordinate transformation shows that the Killing tensor discovered
in [15] coincides with the one studied in this paper for vanishing
cosmological constant and $q=0$. At the same time it shows that the metrics
(2.3) and (2.4) in [22] are at least locally diffeomorphic.

Similarly, the higher-dimensional Lense–Thirring spacetimes (25) can be cast
in the higher-dimensional version of the PG form close to the horizon, by the
following change of coordinates:

$\displaystyle dt$ $\displaystyle=$ $\displaystyle
dT-\frac{\sqrt{1-f}}{f}dr\,,$ $\displaystyle d\phi_{i}$ $\displaystyle=$
$\displaystyle d\Phi_{i}+\frac{2Ma_{i}\sqrt{1-f}}{fr^{2m+\epsilon}}dr\,,$ (42)

upon which the metric takes the following PG form:

$\displaystyle ds^{2}$ $\displaystyle=$ $\displaystyle-
dT^{2}+(dr+\sqrt{1-f}dT)^{2}+r^{2}(\sum_{i=1}^{m}d\mu_{i}^{2}+\epsilon
d\nu^{2})$
$\displaystyle+r^{2}\sum_{i=1}^{m}\mu_{i}^{2}\Bigl{(}d\Phi_{i}+\frac{2Ma_{i}}{r^{2m+\epsilon}}dT\Bigr{)}^{2}\,,$
$\displaystyle f$ $\displaystyle=$ $\displaystyle
1-\frac{2M}{r^{2m-2+\epsilon}}+\frac{r^{2}}{\ell^{2}}\,,$ (43)

which is non-singular on the horizon $f=0$ and whose $T=$const. slices are
manifestly flat.


# Proving properties of some greedily-defined integer recurrences via automata
theory

Jeffrey Shallit
School of Computer Science
University of Waterloo
Waterloo, ON N2L 3G1
Canada
<EMAIL_ADDRESS>Research supported by NSERC, grant 2018-04118.

###### Abstract

Venkatachala on the one hand, and Avdispahić & Zejnulahi on the other, both
studied integer sequences with an unusual sum property defined in a greedy
way, and proved many results about them. However, their proofs were rather
lengthy and required numerous cases. In this paper, I provide a different
approach, via finite automata, that can prove the same results (and more) in a
simple, unified way. Instead of case analysis, we use a decision procedure
implemented in the free software Walnut. Using these ideas, we can prove a
conjecture of Quet and find connections between Quet’s sequence and the
“married” functions of Hofstadter.

##  1 Introduction

Let $\mathbb{N}=\\{0,1,2,\ldots\\}$ denote the natural numbers. In 2009, B. J.
Venkatachala [6] studied the properties of an amazing sequence of natural
numbers $(f(n))_{n\geq 0}$, whose first few values are given in Table 1.

The sequence $f(n)$ can be defined inductively, using a greedy algorithm, as
follows: $f(0)=0$, and for $n\geq 1$, $f(n)$ is the least natural number such
that

  * (a)

$f(n)\not\in\\{f(0),f(1),\ldots,f(n-1)\\}$;

  * (b)

the sum $\sum_{1\leq i\leq n}f(i)$ is divisible by $n$.

The problem of constructing such a sequence was proposed earlier by Shapovalov
[9].

The related sequence $h$ is defined by the equation

$h(n)={1\over n}\bigl{(}f(1)+\cdots+f(n)\bigr{)}$

for $n\geq 1$. Table 1 gives the first few values.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$f(n)$ | 0 | 1 | 3 | 2 | 6 | 8 | 4 | 11 | 5 | 14 | 16 | 7 | 19 | 21 | 9 | 24 | 10 | 27 | 29 | 12
$h(n)$ | 0 | 1 | 2 | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 7 | 8 | 9 | 9 | 10 | 10 | 11 | 12 | 12
Table 1: Table of the first few values of the sequences $f$ and $h$.

The sequence $f$ is sequence A019444 in the OEIS [10], and the sequence $h$ is
sequence A019446 in the OEIS. Also note that $f(n)=\href
https://oeis.org/A002251(n-1)+1$ for $n\geq 1$.

Venkatachala obtained many interesting results about these numbers, but his
proofs required long case analysis. In this note we show how to obtain very
simple proofs of these results, and many others in Venkatachala’s paper, with
Walnut, a theorem-prover for automatic sequences [5, 8]. We can also obtain
some new results. It simply suffices to state the theorems as first-order
logic assertions, and let Walnut verify them. All verifications in this paper
were done in a matter of seconds on a laptop.

Similarly, in 2020, Avdispahić & Zejnulahi [1] studied two sequences
$(z(n))_{n\geq 0}$ and $(m(n))_{n\geq 0}$ tabulated in Table 2.

The sequence $z(n)$ can be defined inductively, using a greedy algorithm, as
follows: $z(0)=0$, and for $n\geq 1$, $z(n)$ is the least natural number such
that

  * (a)

$z(n)\not\in\\{z(0),z(1),\ldots,z(n-1)\\}$;

  * (b)

the sum $\sum_{2\leq i\leq n}z(i)$ is divisible by $n+1$.

The sequence $m$ is defined by the relation

$m(n)={1\over{n+1}}\bigl{(}z(2)+\cdots+z(n)\bigr{)}$

for $n\geq 1$. Table 2 gives the first few values.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$z(n)$ | 0 | 1 | 3 | 5 | 2 | 8 | 10 | 4 | 13 | 15 | 6 | 18 | 7 | 21 | 23 | 9 | 26 | 28 | 11 | 31
$m(n)$ | 0 | 0 | 1 | 2 | 2 | 3 | 4 | 4 | 5 | 6 | 6 | 7 | 7 | 8 | 9 | 9 | 10 | 11 | 11 | 12
Table 2: Table of the first few values of the sequences $z$ and $m$.

The sequence $z(n)$ is sequence A340510 in the OEIS, and the sequence $m(n)$
is sequence A005379. This latter sequence also appears in Hofstadter’s
celebrated book [4, p. 137] and was analyzed by Stoll [11].

Avdispahić & Zejnulahi obtained many results on these sequences. Once again,
we can obtain the same results in a much simpler way using finite automata.

##  2 Automata for the Venkatachala sequences

As Venkatachala observed, these sequences are related to the golden ratio
$\varphi=(1+\sqrt{5})/2$. So we might suspect they are related to the so-
called Zeckendorf numeration system [12]; in fact, that they are computable by
a finite automaton.

In this numeration system, natural numbers are represented as binary strings;
the string $a_{1}a_{2}\cdots a_{t}$ represents the number $\sum_{1\leq i\leq
t}a_{i}F_{t+2-i}$, where $F_{0}=0$, $F_{1}=1$, and $F_{n}=F_{n-1}+F_{n-2}$ are
the Fibonacci numbers. In general, numbers may have multiple representations,
but uniqueness is obtained if we insist that $a_{i}a_{i+1}=0$ for all $i$.

We can use the “guessing” procedure discussed in [8] to find candidate
automata computing the functions $f$ and $h$, based on actual computed initial
values. They are depicted in Figures 1 and 2. We call these automata fp and
hp, respectively, and the functions they compute $f^{\prime}$ and
$h^{\prime}$.

Figure 1: Fibonacci automaton for $f^{\prime}(n)$. Figure 2: Fibonacci
automaton for $h^{\prime}(n)$.

These automata operate as follows. The automaton fp (respectively, hp)
computes $f^{\prime}(n)$ (respectively, $h^{\prime}(n)$), as follows: one
feeds the automaton with the Zeckendorf representation of $n$ and $x$ in
parallel, starting with the most significant digits, and padding a shorter
input with leading zeros, if necessary. Starting in state $0$, and following
the arrows, one arrives at an accepting state (depicted with a double circle)
if and only if $x=f^{\prime}(n)$ (respectively, $x=h^{\prime}(n)$). Automata
like these are called “Fibonacci-synchronized”, and their properties are
discussed in [7].

Technically speaking, these automata compute relations on
$\mathbb{N}\times\mathbb{N}$. Our first step is to check that these relations
are actually functions. We can do this with the following Walnut code. It
checks that there is a value associated with every argument, and no argument
has two or more values associated with it.

    eval func_f_check1 "?msd_fib An Ex $fp(n,x)":
    eval func_f_check2 "?msd_fib An ~Ex,y x!=y & $fp(n,x) & $fp(n,y)":
    eval func_h_check1 "?msd_fib An Ex $hp(n,x)":
    eval func_h_check2 "?msd_fib An ~Ex,y x!=y & $hp(n,x) & $hp(n,y)":

Walnut returns TRUE for each command.

It may be helpful to explain the syntax here. eval is a command to evaluate
the first-order formula in quotes whose name is given immediately after the
command. The ?msd_fib tells Walnut that numbers are to be represented in the
Zeckendorf numeration system. A is the universal quantifier $\forall$ and E is
the existential quantifier $\exists$. The symbol & represents logical AND, and
~ represents logical NOT.

Now we know that $f^{\prime}$ and $h^{\prime}$ are indeed natural-number
valued functions. We now have to check that $f^{\prime}=f$ and $h^{\prime}=h$.
The first step is to check that our guessed functions $f^{\prime},h^{\prime}$
satisfy the relation

$(n+1)h^{\prime}(n+1)-nh^{\prime}(n)=f^{\prime}(n+1)$ (1)

for all $n\geq 0$. And to check this, we will compute a linear representation
for the difference $(n+1)h^{\prime}(n+1)-nh^{\prime}(n)-f^{\prime}(n+1)$ and
verify that it represents the $0$ function.

Here, by a linear representation, we mean a triple $(v,\mu,w)$, where $v$ is a
$1\times n$ vector, $w$ is an $n\times 1$ vector, and $\mu$ is an $n\times n$
matrix-valued morphism on the alphabet $\\{0,1\\}$. The number $n$ is called
the rank of the linear representation. In this paper, a linear representation
for a sequence $a(n)$ means that if $n$ is written as a binary string
$e_{1}e_{2}\cdots e_{t}$ in Zeckendorf representation, then
$a(n)=v\mu(e_{1})\cdots\mu(e_{t})w$. For more information about linear
representations, see [2].

We start by using Walnut to construct the linear representations for $n$,
$n+1$, $h^{\prime}(n)$, $h^{\prime}(n+1)$, and $f^{\prime}(n+1)$:

    eval en n "?msd_fib i<n":
    eval enp1 n "?msd_fib i<=n":
    eval hn n "?msd_fib Ex $hp(n,x) & i<x":
    eval hnp1 n "?msd_fib Ex $hp(n+1,x) & i<x":
    eval fnp1 n "?msd_fib Ex $fp(n+1,x) & i<x":

These representations have rank $6,6,8,9,$ and $19$, respectively.

From these representations we can, using the algorithms in [2], construct the
linear representation for
$(n+1)f^{\prime}(n+1)-nf^{\prime}(n)-h^{\prime}(n+1)$. It has rank 121\. When
we minimize this linear representation, we get the $0$ representation. Thus
Eq. (1) is proved.

Now, substituting successively $1$, $2$, $\ldots$, $n-1$ for $n$ in Eq. (1),
and adding up the resulting equations, gives

$nh^{\prime}(n)=f^{\prime}(1)+\cdots+f^{\prime}(n).$ (2)

In particular, since by its definition as an automaton, the quantity
$h^{\prime}(n)$ is always an integer, this proves that $\sum_{1\leq i\leq
n}f^{\prime}(i)$ is divisible by $n$. Furthermore, once we verify that
$f=f^{\prime}$, then Eq. (2) will show that $h=h^{\prime}$.

Now it remains to verify that $f^{\prime}(n)=f(n)$ for all $n$. We do this by
induction. The base case is $n=0$. For the induction step, we assume we have
shown $f(i)=f^{\prime}(i)$ for $0\leq i<n$, and we want to prove it for $n$.

First, let us rule out the possibility that $f(n)>f^{\prime}(n)$. To do this,
it suffices to check that
$f^{\prime}(n)\not\in\\{f^{\prime}(0),f^{\prime}(1),\ldots,f^{\prime}(n-1)\\}$,
which by induction shows that
$f^{\prime}(n)\not\in\\{f(0),f(1),\ldots,f(n-1)\\}$.

    eval check_fp_membership "?msd_fib An,x,i,y ($fp(n,x) & $fp(i,y) & i<n)
       => x!=y":

and Walnut returns TRUE.

Next, let us rule out the possibility that $f(n)<f^{\prime}(n)$. To do this,
we first prove that $f^{\prime}(n)<2n$ for all $n\geq 1$:

    eval check_fp_inequality1 "?msd_fib An,x (n>=2 & $fp(n,x)) => x<2*n":

Thus the only two possibilities left are $f(n)=f^{\prime}(n)$ or
$f(n)=f^{\prime}(n)-n$. To rule out the second one, it suffices to show that
either

$f^{\prime}(n)-n\leq 0\quad\text{ or }\quad
f^{\prime}(n)-n\in\\{f^{\prime}(0),f^{\prime}(1),\ldots,f^{\prime}(n-1)\\}.$

    eval check_fp_inequality2 "?msd_fib An,x $fp(n,x) =>
       (x<=n | Ei,y i<n & $fp(i,y) & x=n+y)":

And Walnut returns TRUE. Thus we have proved that $f^{\prime}(n)=f(n)$, and
hence $h^{\prime}(n)=h(n)$. From now on, then, we can replace $f^{\prime}$
with $f$ and $h^{\prime}$ with $h$.

######  Remark 1.

In the last part of the proof, we have also shown an alternative
characterization of the sequence $(f(n))_{n\geq 1}$; namely, that it is the
lexicographically least sequence of distinct positive integers with the
property that all values of $f(n)-n$ are also distinct. This was observed by
Ivan Neretin in the comments to sequence A019444.

##  3 Results of Venkatachala

Now that we have proved the correctness of the automata, we can easily re-
prove the results of Venkatachala. All we have to do is translate his claims
into first-order logic.

######  Theorem 2.

  * (a)

$h$ is a nondecreasing function of $n$ .

  * (b)

$h(n)\leq n$ for $n\geq 0$.

  * (c)

$h(n+1)\in\\{h(n),h(n)+1\\}$ for $n\geq 0$.

  * (d)

If $n\geq 0$ then $h(n+1)=h(n)\Leftrightarrow f(n+1)=h(n)$.

  * (e)

If $n\geq 0$ then $h(n+1)=h(n)+1\Leftrightarrow f(n+1)=h(n)+n+1$.

  * (f)

If $n\geq 1$ then $h(h(n))+h(n+1)=n+2$.

  * (g)

If $n\geq 0$ then $f(f(n))=n$.

  * (h)

If $n\geq 1$ then $h(h(n)+n)=n+1$.

  * (i)

If $n\geq 1$ then $h(n)=\lfloor n\varphi\rfloor-n+1$.

  * (j)

The function $h$ does not assume the same value at three distinct integers.

  * (k)

For $n\geq 0$ we have $h(n+2)>h(n)$.

  * (l)

The function $h$ is onto.

  * (m)

The function $f$ is onto.

  * (n)

The function $f$ is one-to-one.

  * (o)

For $n\geq 6$ we have $h(n)\leq n-2$.

  * (p)

If $f(n+1)>h(n)$, then $f(j)>h(n)$ for all $j\geq n+1$.

  * (q)

There are no integers $k\geq 2$ and $\ell$ such that $f(k-1)=\ell$ and
$f(k)=\ell+1$.

###### Proof.

We will need Walnut code for $\lfloor n\varphi\rfloor$, $\lfloor
n/\varphi\rfloor$, and $\lfloor n\varphi^{2}\rfloor$. These can be found in
[8].

    reg shift {0,1} {0,1} "([0,0]|[0,1][1,1]*[1,0])*":
    def phin "?msd_fib (s=0 & n=0) | Ex $shift(n-1,x) & s=x+1":
    def phi2n "?msd_fib (s=0 & n=0) | Ex,y $shift(n-1,x) &
       $shift(x,y) & s=y+2":
    def noverphi "?msd_fib Et $phin(n,t) & s+n=t":

We use the following Walnut code.

    eval testa "?msd_fib An,x,y ($h(n,x) & $h(n+1,y)) => x<=y":
    eval testb "?msd_fib An,x $h(n,x) => x<=n":
    eval testc "?msd_fib An,x,y ($h(n,x) & $h(n+1,y)) => (y=x | y=x+1)":
    eval testd "?msd_fib An,x,y,z ($h(n,x) & $h(n+1,y) & $f(n+1,z)) =>
       (y=x <=> z=x)":
    eval teste "?msd_fib An,x,y,z ($h(n,x) & $h(n+1,y) & $f(n+1,z)) =>
       (y=x+1 <=> z=x+n+1)":
    eval testf "?msd_fib An,x,y,z (n>=1 & $h(n,x) & $h(x,y)
       & $h(n+1,z)) => y+z=n+2":
    eval testg "?msd_fib An,x,y ($f(n,x) & $f(x,y)) => y=n":
    eval testh "?msd_fib An,x,y (n>=1 & $h(n,x) & $h(x+n,y))
       => y=n+1":
    eval testi "?msd_fib An,x,y (n>=1 & $h(n,x) & $phin(n,y))
       => x+n=y+1":
    eval testj "?msd_fib ~En1,n2,n3,x (n1<n2) & (n2<n3) &
       $h(n1,x) & $h(n2,x) & $h(n3,x)":
    eval testk "?msd_fib An,x,y ($h(n,x) & $h(n+2,y)) => y>x":
    eval testl "?msd_fib Ax En $h(n,x)":
    eval testm "?msd_fib Ax En $f(n,x)":
    eval testn "?msd_fib An1,n2 (Ex $f(n1,x) & $f(n2,x)) => n1=n2":
    eval testo "?msd_fib An,x (n>=6 & $h(n,x)) => x+2<=n":
    eval testp "?msd_fib An,x,y ($f(n+1,x) & $h(n,y) & x>y) =>
       (Aj,t (j>=n+1 & $f(j,t)) => t>y)":
    eval testq "?msd_fib ~Ek,l k>=2 & $f(k-1,l) & $f(k,l+1)":

And all of them return TRUE. ∎

For a different approach, see the recent paper of Dekking [3].

##  4 Automata and the Avdispahić & Zejnulahi sequences

Once again, we can easily guess candidate Fibonacci automata for these
sequences from their initial values. Once guessed, we can verify their
correctness exactly as we did in Sections 2. We omit the details.

The automaton for $z$ has $18$ states and that for $m$ has $8$ states. They
are depicted in Figures 3 and 4.

Figure 3: Fibonacci automaton for $z(n)$. Figure 4: Fibonacci automaton for
$m(n)$.

Once we have the automata we can easily prove the following results of
Avdispahić & Zejnulahi:

######  Theorem 3.

  * (a)

If $n=F_{k}$ for $k\geq 2$ then $z(n)=F_{k+1}$.

  * (b)

If $n=F_{k}-1$ for $k\geq 4$ then $z(n)=F_{k-1}-1$.

  * (c)

If $n=\lfloor k\tau^{2}\rfloor$ and $n\not=F_{i}$ for $i>2$ and
$n\not=F_{i}-1$ for $i>4$, then $z(n)=\lfloor k\tau\rfloor$.

  * (d)

If $n=\lfloor k\tau\rfloor$ and $n\not=F_{i}$ for $i>2$ and $n\not=F_{i}-1$
for $i>4$, then $z(n)=\lfloor k\tau^{2}\rfloor$.

  * (e)

If $n>2$ and $m(n-1)\not=z(i)$ for $1\leq i<n$, then $z(n)=m(n)=m(n-1)$.

  * (f)

If $n>2$ and $m(n-1)=z(i)$ for some $i$, $1\leq i<n$, then $z(n)=m(n-1)+n+1$
and $m(n)=m(n-1)+1$.

  * (g)

The sequence $z(n)$ is onto.

  * (h)

The sequence $z(n)$ is one-one.

###### Proof.

We use the following Walnut code:

    reg isfib msd_fib "0*10*":
    reg adjfib msd_fib msd_fib "[0,0]*[0,1][1,0][0,0]*":
    eval parta "?msd_fib Ax,y ($adjfib(x,y) & x>=2) => $zp(x,y)":
    eval partb "?msd_fib Ax,y ($adjfib(x,y) & y>=5) => $zp(y-1,x-1)":
    eval partc "?msd_fib Ak,n,x ($phi2n(k,n) & $phin(k,x) & (~$isfib(n))
       & (~$isfib(n+1))) => $zp(n,x)":
    eval partd "?msd_fib Ak,n,x ($phin(k,n) & $phi2n(k,x) & (~$isfib(n)) &
       (~$isfib(n+1))) => $zp(n,x)":
    eval parte "?msd_fib An,x,y,w (n>2 & $zp(n,x) & $mp(n,y) & $mp(n-1,w) &
    (Ai,r (i>=1 & i<n & $z(i,r)) => r!=w)) => (x=w & y=w)":
    eval partf "?msd_fib An,x,y,w (n>2 & $zp(n,x) & $mp(n,y) & $mp(n-1,w) &
    (Ei,r i>=1 & i<n & $zp(i,r) & r=w)) => (x=w+n+1 & y=w+1)":
    eval partg "?msd_fib Ax En $zp(n,x)":
    eval parth "?msd_fib An1,n2 (Ex $zp(n1,x) & $zp(n2,x)) => n1=n2":

All of the Walnut commands return TRUE. ∎

##  5 New results

The advantage to our approach is that, once the automata are obtained, it
becomes almost trivial to test additional conjectures and prove new results.
We give a few examples.

######  Theorem 4.

Suppose $n\geq 1$. Then

$f(n)=\begin{cases}\lfloor n\varphi\rfloor,&\text{ if $\exists m\ n-1=\lfloor
m\varphi\rfloor$;}\\\ \lfloor
n/\varphi\rfloor+1,&\text{otherwise.}\end{cases}$

###### Proof.

We use the following Walnut code:

    eval chk1 "?msd_fib An,x (n>=1 & $fp(n,x) & Em $phin(m,n-1))
       => $phin(n,x)":
    eval chk2 "?msd_fib An,x (n>=1 & $fp(n,x) & ~Em $phin(m,n-1))
       => $noverphi(n,x-1)":

∎

######  Corollary 5.

$\lfloor n/\varphi\rfloor+1\leq f(n)\leq\lfloor n\varphi\rfloor$ for all
$n\geq 1$.

We now prove a theorem linking the functions of the two papers.

######  Theorem 6.

We have $z(n)\in\\{f(n),f(n)+n,f(n)+1,f(n)-n\\}$ for all $n\geq 0$.

###### Proof.

We use the following Walnut code:

    eval thm6 "?msd_fib An,x,y ($fp(n,x) & $zp(n,y)) => (y=x|y=x+n|y=x+1|y+n=x)":

and Walnut returns TRUE. ∎

######  Remark 7.

One may reasonably ask for simple characterizations of the $n$ for which each
case occurs. The answer is that $n$ for which $z(n)=f(n)$, $z(n)=f(n)+n$,
$z(n)=f(n)+1$, $z(n)=f(n)-n$ are accepted by automata of $7$, $5$, $6$, and
$9$ states, respectively, and these are easy to compute with Walnut.

Furthermore, by examining these automata, we easily see that $z(n)=f(n)$ if
and only if $n=0$ or $n=F_{2k+1}$ for $k\geq 0$.

Similarly, $z(n)=f(n)+n$ if and only if $n=0$ or $n=\lfloor
k\varphi^{2}\rfloor+1$ for some $k\geq 1$. This can easily be proved with
Walnut.

##  6 Going further

###  6.1 Hofstadter’s married functions

Hofstadter [4] defined two sequences he called “married” functions, via the
system of recurrences

$\displaystyle b(n)$ $\displaystyle=n-a(b(n-1))$ $\displaystyle a(n)$
$\displaystyle=n-b(a(n-1)),$

for $n\geq 1$, with initial values $a(0)=1$, $b(0)=0$. Here $(a(n))$ is
A005378 and $(b(n))$ is A005379. The first few values are given in Table 3.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$a(n)$ | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 | 5 | 6 | 6 | 7 | 8 | 8 | 9 | 9 | 10 | 11 | 11
$b(n)$ | 0 | 0 | 1 | 2 | 2 | 3 | 4 | 4 | 5 | 6 | 6 | 7 | 7 | 8 | 9 | 9 | 10 | 11 | 11
Table 3: Hofstadter’s “married” functions.

We can use our techniques to guess and prove the automata for these functions.
They are depicted below in Figure 5.

Figure 5: Fibonacci automata ha and hb for the “married” functions $a(n)$
(left) and $b(n)$ (right).

With these automata, we can easily recover the closed forms for these
sequences previously obtained by Stoll [11]:

######  Theorem 8.

Let $\alpha=(\sqrt{5}-1)/2$. Define

$\varepsilon_{1}(n)=\begin{cases}1,&\text{if $n=F_{2k}-1$ for some $k\geq
1$;}\\\ 0,&\text{otherwise;}\end{cases}$

and

$\varepsilon_{2}(n)=\begin{cases}1,&\text{if $n=F_{2k+1}-1$ for some $k\geq
1$;}\\\ 0,&\text{otherwise;}\end{cases}$

Then for $n\geq 0$ we have

$\displaystyle a(n)$ $\displaystyle=\lfloor(n+1)\alpha\rfloor+\epsilon_{1}(n)$
$\displaystyle b(n)$ $\displaystyle=\lfloor(n+1)\alpha\rfloor-\epsilon_{2}(n)$

###### Proof.

We use the following Walnut code:

    reg evenfib msd_fib "0*1(00)*":
    reg oddfib msd_fib "0*10(00)*":

    def eps1 "?msd_fib (x=1 & $evenfib(n+1)) | (x=0 & ~$evenfib(n+1))":
    def eps2 "?msd_fib (x=1 & $oddfib(n+1)) | (x=0 & ~$oddfib(n+1))":

    eval checkstolla "?msd_fib An,x,y,z ($noverphi(n+1,x) & $ha(n,y) &
       $eps1(n,z)) => y=x+z":
    eval checkstollb "?msd_fib An,x,y,z ($noverphi(n+1,x) & $hb(n,y) &
       $eps2(n,z)) => y+z=x":

And TRUE is returned twice. ∎

###  6.2 Quet’s sequence

In a personal communication, Muharem Avdispahić suggested looking at
parameterized versions of the sequences we have studied here. Here is one
possibility: let $k\geq-1$. Define $A_{k}(n)=n$ for $0\leq n\leq k$, and for
$n\geq k$ define $A_{k}(n+1)$ to be the least natural number such that
$A_{k}(n+1)\not\in\\{A_{k}(0),A_{k}(1),\ldots,A_{k}(n)\\}$ and $\sum_{k+1\leq
i\leq n+1}A_{k}(n)\equiv 0\ \mbox{\rm(mod}\ n+k\mbox{\rm)}$. Values of the
first few sequences are given in Table 4.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$A_{-1}(n)$ | 0 | 1 | 2 | 3 | 6 | 4 | 9 | 5 | 12 | 14 | 7 | 17 | 8 | 20 | 22 | 10 | 25 | 11 | 28
$A_{0}(n)$ | 0 | 1 | 3 | 2 | 6 | 8 | 4 | 11 | 5 | 14 | 16 | 7 | 19 | 21 | 9 | 24 | 10 | 27 | 29
$A_{1}(n)$ | 0 | 1 | 3 | 5 | 2 | 8 | 10 | 4 | 13 | 15 | 6 | 18 | 7 | 21 | 23 | 9 | 26 | 28 | 11
$A_{2}(n)$ | 0 | 1 | 2 | 5 | 7 | 9 | 3 | 12 | 4 | 15 | 17 | 6 | 20 | 22 | 8 | 25 | 27 | 10 | 30
$A_{3}(n)$ | 0 | 1 | 2 | 3 | 7 | 9 | 11 | 13 | 4 | 16 | 5 | 19 | 6 | 22 | 24 | 8 | 27 | 29 | 10
$A_{4}(n)$ | 0 | 1 | 2 | 3 | 4 | 9 | 11 | 13 | 15 | 17 | 5 | 20 | 6 | 23 | 7 | 26 | 8 | 29 | 31
Table 4: Parameterized sequences.

Note that $A_{0}(n)=f(n)$ and $A_{1}(n)=z(n)$.

Of particular interest is $A_{-1}(n)$. This is Quet’s sequence $(\href
https://oeis.org/A125147(n-1))_{n\geq 0}$. As an example of the usefulness of
the automaton-based method, we can now prove a conjecture about Quet’s
sequence.

######  Theorem 9.

Quet’s sequence is a permutation of the integers.

###### Proof.

We follow the same sequence of steps as in Section 2 and 3: first, define

$B_{-1}(n+1)={1\over n}\left(\sum_{0\leq i\leq n}A_{-1}(i)\right)$ (3)

for $n\geq 1$, and set $B_{-1}(i)=i$ for $i=0,1$. The first few values of
$B_{-1}(n)$ are given in Table 5.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$B_{-1}(n)$ | 0 | 1 | 3 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 7 | 8 | 8 | 9 | 10 | 10 | 11 | 11 | 12
Table 5: Values of $B_{-1}(n)$.

Next, from the first few computed values of $A_{-1}(n)$ and $B_{-1}(n)$, we
“guess” an automaton for $A_{-1}(n)$ and its associated sequence $B_{-1}(n)$
that we hope will verify Eq. (3).

These automata have 29 and 17 states, respectively, and are depicted in
Figures 6 and 7.

Figure 6: Fibonacci automaton queta for $A_{-1}(n)$. Figure 7: Fibonacci
automaton quetb for $B_{-1}(n)$.

Next, we verify that the guessed automata actually compute functions, say
$A^{\prime}_{-1}(n)$ and $B^{\prime}_{-1}(n)$.

We then check the correctness of the initial values and, using the linear
representations of the automata, check that

$A^{\prime}_{-1}(n+3)=(n+2)B^{\prime}_{-1}(n+3)-(n+1)B^{\prime}_{-1}(n+2)$

for all $n\geq 0$. This proves that the automata really do compute the
functions $A_{-1}(n)$ and $B_{-1}(n)$.

Finally, we use Walnut to check the assertion that $A_{-1}(n)$ is a
permutation of $\mathbb{N}$.

The needed Walnut code is below:

    eval queta_check1 "?msd_fib An Ex $queta(n,x)":
    eval queta_check2 "?msd_fib An ~Ex,y x!=y & $queta(n,x) & $queta(n,y)":
    eval quetb_check1 "?msd_fib An Ex $quetb(n,x)":
    eval quetb_check2 "?msd_fib An ~Ex,y x!=y & $quetb(n,x) & $quetb(n,y)":

    eval en n "?msd_fib i<n":
    eval enp1 n "?msd_fib i<n+1":
    eval enp2 n "?msd_fib i<n+2":
    #6,6,8 states

    eval qan3 n "?msd_fib Ex $queta(n+3,x) & i<x":
    eval qbn3 n "?msd_fib Ex $quetb(n+3,x) & i<x":
    eval qbn2 n "?msd_fib Ex $quetb(n+2,x) & i<x":
    #52,20,17 states

    #check that queta is a permutation of the integers
    eval queta_onto "?msd_fib Ax En $queta(n,x)":
    eval queta_one_one "?msd_fib ~En1,n2,x (n1!=n2) & $queta(n1,x) & $queta(n2,x)":

∎

###  6.3 An unexpected connection

Finally, we show that Quet’s sequence is intimately connected to the “married”
functions of Hofstadter:

######  Theorem 10.

For all $n\geq 2$ we have $B_{-1}(n)=a(n-2)+2$.

###### Proof.

We use the following Walnut command:

    eval quetbcheck "?msd_fib An,x,y (n>=2 & $quetb(n,x) & $ha(n-2,y)) => x=y+2":

which returns TRUE. ∎

Walnut is available at the following URL:

https://cs.uwaterloo.ca/~shallit/walnut.html .

##  7 Acknowledgment

I thank Muharem Avdispahić for his kind suggestion, and Michel Dekking for
pleasant and helpful discussions.

## References

  * [1] M. Avdispahić and F. Zejnulahi.  An integer sequence with a divisibility property.  Fibonacci Quart. 58 (2020), 321–333.
  * [2] J. Berstel and C. Reutenauer.  Noncommutative Rational Series With Applications, Vol. 137 of Encyclopedia of Mathematics and Its Applications.  Cambridge University Press, 2011.
  * [3] Michel Dekking.  On Hofstadter’s $G$-sequence.  ArXiv preprint arXiv:2307.01471v2 [math.CO], July 25 2023. Available at https://arxiv.org/abs/2307.01471.
  * [4] D. R. Hofstadter.  Gödel, Escher, Bach: An Eternal Golden Braid.  Basic Books, 1979.
  * [5] H. Mousavi.  Automatic theorem proving in Walnut.  Arxiv preprint arXiv:1603.06017 [cs.FL], available at http://arxiv.org/abs/1603.06017, 2016.
  * [6] B. J. Venkatachala.  A curious bijection on natural numbers.  J. Integer Sequences 12 (2009), Article 09.8.1.
  * [7] J. Shallit.  Synchronized sequences.  In T. Lecroq and S. Puzynina, editors, WORDS 2021, Vol. 12847 of Lecture Notes in Computer Science, pp. 1–19. Springer-Verlag, 2021\.
  * [8] J. Shallit.  The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut, Vol. 482 of London Math. Soc. Lecture Notes Series.  Cambridge University Press, 2022.
  * [9] A. Shapovalov.  Problem M185.  Quantum 7 (1) (1996), 22, 59.
  * [10] N. J. A. Sloane et al.  The On-Line Encyclopedia of Integer Sequences.  Available at https://oeis.org.
  * [11] T. Stoll.  On Hofstadter’s married functions.  Fib. Quart. 46/47 (2008/9), 62–67.
  * [12] E. Zeckendorf.  Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas.  Bull. Soc. Roy. Liège 41 (1972), 179–182.