# Transcendence of Sturmian Numbers over an Algebraic Base

Florian Luca
School of Mathematics, University of the Witwatersrand
Private Bag 3, Wits 2050, South Africa
Research Group in Algebraic Structures and Applications
King Abdulaziz University, Jeddah, Saudi Arabia
<EMAIL_ADDRESS>Joël Ouaknine
Max Planck Institute for Software Systems
Saarland Informatics Campus, Saarbrücken, Germany
<EMAIL_ADDRESS>James Worrell
Department of Computer Science
University of Oxford, Oxford OX1 3QD, UK
<EMAIL_ADDRESS>
###### Abstract

We consider numbers of the form
$S_{\beta}(\bm{u}):=\sum_{n=0}^{\infty}\frac{u_{n}}{\beta^{n}}$ for
$\bm{u}=\langle u_{n}\rangle_{n=0}^{\infty}$ a Sturmian sequence over a binary
alphabet and $\beta$ an algebraic number with $|\beta|>1$. We show that every
such number is transcendental. More generally, for a given base $\beta$ and
given irrational number $\theta$ we characterise the
$\overline{\mathbb{Q}}$-linear independence of sets of the form
$\left\\{1,S_{\beta}(\bm{u}^{(1)}),\ldots,S_{\beta}(\bm{u}^{(k)})\right\\}$,
where $\bm{u}^{(1)},\ldots,\bm{u}^{(k)}$ are Sturmian sequences having slope
$\theta$.

We give an application of our main result to the theory of dynamical systems,
showing that for a contracted rotation on the unit circle with algebraic
slope, its limit set is either finite or consists exclusively of
transcendental elements other than its endpoints $0$ and $1$. This confirms a
conjecture of Bugeaud, Kim, Laurent, and Nogueira [3].

##  1 Introduction

A famous conjecture of Hartmanis and Stearns asserts that a real number
$\alpha$ whose sequence of digits can be produced by a linear-time Turing
machine (in the sense that for all $n$, given input $n$ in unary the machine
outputs the first $n$ digits of $\alpha$ in time $O(n)$) is either rational or
transcendental. This conjecture remains open and is considered to be very
difficult. A weaker version—proposed by Cobham and eventually proved by
Adamczewski, Bugeaud, and Luca [2]—asserts the transcendence of an irrational
automatic real number. The underlying intuition is that the sequence of digits
of an irrational algebraic number cannot be too simple. Indeed, the main
technical result of [2] is that over an integer base every number whose
sequence of digits has linear subword complexity is either rational or
transcendental. Cobham’s conjecture is an immediate corollary, given that
automatic sequences have linear subword complexity.

In this paper we prove a transcendence result for numbers whose digit
sequences are Sturmian words (sometimes called mechanical words). Such words
have minimal subword complexity among non-ultimately periodic words and have a
natural characterisation in terms of dynamical systems as codings of rotations
on the unit circle. The novelty of this work is that we handle expansions over
an arbitrary algebraic base rather than just an integer base. Here we are
motivated by applications to control theory and dynamical systems.

An infinite sequence $\bm{u}=u_{0}u_{1}u_{2}\ldots$ over a binary alphabet is
said to be _Sturmian_ if the number $p(n)$ of different length-$n$ factors in
$\bm{u}$ satisfies $p(n)=n+1$ for all $n\in\mathbb{N}$, see [11]. Coven and
Hedlund [4] show that an infinite word such that $p(n)\leq n$ for some $n$ is
necessarily ultimately periodic. Thus Sturmian words have minimal subword
complexity among non-ultimately periodic words over a binary alphabet
$\\{0,1\\}$. The letters in a Sturmian word have a limiting frequency—the
limit frequency of the letter $1$ is called the _slope_ of the word. Related
to this, Sturmian words have a natural characterisation in terms of dynamical
systems, namely as codings of the orbits of irrational rotations on
$\mathbb{R}/\mathbb{Z}$. Perhaps the best known example of a Sturmian word is
the _Fibonacci word_. This is defined as the limit $\bm{f}_{\infty}$ of the
sequence $(\bm{f}_{n})_{n=0}^{\infty}$ of finite strings over the binary
alphabet $\\{0,1\\}$, defined by the recurrence $\bm{f}_{0}:=0$,
$\bm{f}_{1}:=01$, and $\bm{f}_{n}=\bm{f}_{n-1}\bm{f}_{n-2}$ for all $n\geq 2$.
The limit is well defined since $\bm{f}_{n}$ is a prefix of $\bm{f}_{n+1}$ for
all $n\in\mathbb{N}$. The Fibonacci word has slope $1/\phi$, where
$\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio. It so happens that the
Fibonacci word is morphic, although it is not automatic.

Let $\bm{u}$ be a Sturmian word over a finite alphabet
$\Sigma\subseteq\overline{\mathbb{Q}}$ and let $\beta\in\overline{\mathbb{Q}}$
be such that $|\beta|>1$. Then we call
$S_{\beta}(\bm{u}):=\sum_{n=0}^{\infty}\frac{u_{n}}{\beta^{n}}$ a _Sturmian
number_ with _sequence of digits_ $\bm{u}$ and _base_ $\beta$.111Our notion of
Sturmian number is more permissive than that of Morse and Hedland [10] who
restricted to the case of an integer base $b>1$ and digit sequence $\bm{u}$
over alphabet $\\{0,\ldots,b-1\\}$. Ferenczi and Mauduit [5] proved the
transcendence of every number $S_{\beta}(\bm{u})$ over an integer base
$\beta>1$. Their proof combined combinatorial properties of Sturmian sequences
with a $p$-adic version of the Thue-Siegel-Roth Theorem, due to Ridout. This
result was strengthened by Bugeaud _et al._ [3] to show
$\overline{\mathbb{Q}}$-linear independence of sets of the form
$\left\\{1,S_{\beta}(\bm{u}^{(1)}),S_{\beta}(\bm{u}^{(2)})\right\\}$ where
$\bm{u}^{(1)},\bm{u}^{(2)}$ are Sturmian words having the same slope and
$\beta>1$ is an integer. In the case of an algebraic base $\beta$, Laurent and
Nogueria [12] observe that if $\bm{u}$ is a characteristic Sturmian word (cf.
Section 3), then the transcendence of $S_{\beta}(\bm{u})$ follows from a
result of Loxton and Van der Poorten [8, Theorem 7] concerning transcendence
of Hecke-Mahler series.

In this paper we give a common generalisation of the above three results. For
every algebraic base $\beta$ and irrational slope $\theta$ we give sufficient
and necessary conditions for $\overline{\mathbb{Q}}$-linear independence of a
set of Sturmian numbers
$\left\\{1,S_{\beta}(\bm{u}^{(1)}),\ldots,S_{\beta}(\bm{u}^{(k)})\right\\}$,
where $\bm{u}^{(1)},\ldots,\bm{u}^{(k)}$, where are Sturmian sequences of
slope $\theta$. Our characterisation relies on a new combinatorial criterion
on a sequence $\bm{u}$ that ensures transcendence of $S_{\beta}(\bm{u})$ for
$\beta$ an algebraic base. Similar to [3], the Subspace Theorem plays a major
role in our argument. In [7] we give a more elaborate and powerful
transcendence criterion that allows proving $\overline{\mathbb{Q}}$-linear
independence results about Sturmian numbers (again with a common slope) over
different algebraic bases.

For a sequence $\bm{u}$ with linear subword complexity (i.e., such that
$\lim\inf_{n}\frac{p(n)}{n}<\infty$), it is shown in [1] that
$S_{\beta}(\bm{u})$ is transcendental under the condition that $\beta$ is a
Pisot number (i.e., a real algebraic integer greater than one all of whose
Galois conjugates have absolute value less than one). Compared to the main
result of this paper, the class of sequences considered by [1] is more general
(requiring merely linear subword complexity rather than the stronger condition
of being Sturmian), but the condition on the base is more restrictive (being a
Pisot number rather than merely an algebraic number of absolute value strictly
greater than one).

In Section 5 we give an application of our main result to the theory of
dynamical systems. We consider the set $C$ of limit points of a contracted
rotation $f$ on the unit interval, where $f$ is assumed to have an algebraic
contraction factor. The set $C$ is finite if $f$ has a periodic orbit and is
otherwise a Cantor set, that is, it is homeomorphic to the Cantor ternary set
(equivalently, it is compact, nowhere dense, and has no isolated points). In
the latter case we show that all elements of $C$ except its endpoints $0$ and
$1$ are transcendental. Our result confirms a conjecture of Bugeaud, Kim,
Laurent, and Nogueira, who proved a special case of this result in [3]. We
remark that it is a longstanding open question whether the actual Cantor
ternary set contains any algebraic elements other than $0$ or $1$.

##  2 Preliminaries

Let $K$ be a number field of degree $d$ and let $M(K)$ be the set of _places_
of $K$. We divide $M(K)$ into the collection of _infinite places_ , which are
determined either by an embedding of $K$ in $\mathbb{R}$ or a complex-
conjugate pair of embeddings of $K$ in $\mathbb{C}$, and the set of _finite
places_ , which are determined by prime ideals in the ring $\mathcal{O}_{K}$
of integers of $K$.

For $x\in K$ and $v\in M(K)$, define the absolute value $|x|_{v}$ as follows:
$|x|_{v}:=|\sigma(x)|^{1/d}$ in case $v$ corresponds to a real embedding
$\sigma:K\rightarrow\mathbb{R}$; $|x|_{v}:=|\sigma(x)|^{2/d}$ in case $v$
corresponds to a complex-conjugate pair of embeddings
$\sigma,\overline{\sigma}:K\rightarrow\mathbb{C}$; finally,
$|x|_{v}:=N(\mathfrak{p})^{-\mathrm{ord}_{\mathfrak{p}}(x)/d}$ if $v$
corresponds to a prime ideal $\mathfrak{p}$ in $\mathcal{O}$ and
$\mathrm{ord}_{\mathfrak{p}}(x)$ is the order of $\mathfrak{p}$ as a divisor
of the ideal $x\mathcal{O}$. With the above definitions we have the _product
formula_ : $\prod_{v\in M(K)}|x|_{v}=1$ for all $x\in K^{\ast}$. Given a set
of places $S\subseteq M(K)$, the ring $\mathcal{O}_{S}$ of _$S$ -integers_ is
the subring comprising all $x\in K$ such $|x|_{v}\leq 1$ for all finite places
$v\in S$.

For $m\geq 2$ the _absolute Weil height_ of $\bm{x}=(x_{1},\ldots,x_{m})\in
K^{m}$ is defined to be

$H(\bm{x}):=\prod_{v\in M(K)}\max(|x_{1}|_{v},\ldots,|x_{m}|_{v})\,.$

This definition is independent of the choice of field $K$ containing
$x_{1},\ldots,x_{m}$. Note the restriction $m\geq 2$ in the above definition.
For $x\in K$ we define its height $H(x)$ to be $H(1,x)$. For a non-zero
polynomial $f=\sum_{i=0}^{s}a_{i}X^{i}\in K[X]$, where $s\geq 1$, we define
its height $H(f)$ to be the height of its coefficient vector
$(a_{0},\ldots,a_{s})$.

The following classical result of Schlickewei will be instrumental in our
approach.

######  Theorem 1 (Subspace Theorem).

Let $S\subseteq M(K)$ be a finite set of places, containing all infinite
places and let $m\geq 2$. For every $v\in S$ let $L_{1,v},\ldots,L_{m,v}$ be
linearly independent linear forms in $m$ variables with algebraic
coefficients. Then for any $\varepsilon>0$ the solutions
$\bm{x}\in\mathcal{O}_{S}^{m}$ of the inequality

$\prod_{v\in S}\prod_{i=1}^{m}|L_{i,v}(\bm{x})|_{v}\leq
H(\bm{x})^{-\varepsilon}$

are contained in finitely many proper subspaces of $K^{m}$.

We will also need the following more elementary proposition.

######  Proposition 2.

[6, Proposition 2.3] Let $f\in K[X]$ be a polynomial with at most $k+1$ terms.
Assume that $f$ can be written as the sum of two polynomials $g$ and $h$,
where every monomial of $g$ has degree at most $d_{0}$ and every monomial of
$h$ has degree at least $d_{1}$. Let $\beta$ be a root of $f$ that is not a
root of unity. If $d_{1}-d_{0}>\frac{\log(k\,H(f))}{\log H(\beta)}$ then
$\beta$ is a common root of $g$ and $h$.

##  3 Stuttering Sequences

Let $A\subseteq\overline{\mathbb{Q}}$ be a finite alphabet. An infinite
sequence $\bm{u}=u_{0}u_{1}u_{2}\ldots\in A^{\omega}$ is said to be
_stuttering_ if for all $w>0$ there exist sequences $\langle
r_{n}\rangle_{n=0}^{\infty}$ and $\langle s_{n}\rangle_{n=0}^{\infty}$ of
positive integers and $d\geq 2$ such that:

  1. S1

$\langle r_{n}\rangle_{n=0}^{\infty}$ is unbounded and $s_{n}\geq wr_{n}$ for
all $n\in\mathbb{N}$;

  2. S2

for all $n\in\mathbb{N}$ there exist integers $0\leq
i_{1}(n)<\ldots<i_{d}(n)\leq s_{n}$ such that the strings $u_{0}\ldots
u_{s_{n}}$ and $u_{r_{n}}\ldots u_{r_{n}+s_{n}}$ differ at the set of indices
$\bigcup_{j=1}^{d}\\{i_{j}(n),i_{j}(n)+1\\}$;

  3. S3

we have $i_{d}(n)-i_{1}(n)=\omega(\log r_{n})$ and, writing $i_{0}(n):=0$ and
$i_{d+1}(n):=s_{n}$ for all $n$, we have $i_{j+1}(n)-i_{j}(n)=\omega(1)$ for
all $j\in\\{0,1,\ldots,d\\}$;

  4. S4

for all $n\in\mathbb{N}$ and $j\in\\{1,2\ldots,d\\}$ we have
$u_{i_{j}(n)}+u_{i_{j}(n)+1}=u_{i_{j}(n)+r_{n}}+u_{i_{j}(n)+r_{n}+1}$.

The notion of a stuttering sequence is reminiscent of the transcendence
conditions of [1, 3, 5] in that it concerns periodicity in an infinite word.
Roughly speaking, a sequence $\bm{u}$ is stuttering if for all $w>0$ there are
arbitrarily long prefixes of $\bm{u}$ that, modulo a fixed number of
mismatches, comprise $w$ repetitions of some finite word. The fact that the
number $w$ of repetitions is arbitrary is key to our being able to prove
transcendence results over an arbitrary algebraic base $\beta$. In
compensation, our condition allows repetitions with a certain number of
discrepancies. This should be contrasted with the notion of stammering
sequence in [1, Section 4], where there is no allowance for such discrepancies
and in which the quantity corresponding to $w$ is fixed.

######  Example 3.

To illustrate the notion of stuttering sequence, we recall the example of the
Fibonacci word. That this sequence is stuttering is a consequence of Theorem
4. Here in fact the sequence of shifts $\langle r_{n}\rangle_{n=0}^{\infty}$
witnessing that the Fibonacci word is stuttering is the Fibonacci sequence
$\langle 1,1,2,3,5,\ldots\rangle$. Below we align the Fibonacci word
$\bm{f}_{\infty}$ with its shift $\bm{f}_{\infty}^{(5)}$ by $r_{5}=5$,
underlining the mismatches which arise in consecutive pairs that satisfy
Condition S4.

$\displaystyle\bm{f}_{\infty}:=\,$ $\displaystyle
010010\underline{10}01001010010\underline{10}010010\underline{10}0100101001\ldots$
$\displaystyle\bm{f}_{\infty}^{(5)}:=\,$ $\displaystyle
010010\underline{01}01001010010\underline{01}010010\underline{01}0100101001\ldots$

In what follows, we use the following representation of Sturmian words. Write
$I:=[0,1)$ for the unit interval and given $x\in\mathbb{R}$ denote the integer
part of $x$ by $\lfloor x\rfloor$ and the fractional part of $x$ by
$\\{x\\}:=x-\lfloor x\rfloor\in I$. Let $0<\theta<1$ be an irrational number
and define the _rotation map_ $T=T_{\theta}:I\rightarrow I$ by
$T(y)=\\{y+\theta\\}$. Given $x\in I$, the _$\theta$ -coding of $x$_ is the
infinite sequence $\bm{u}=u_{1}u_{2}u_{3}\ldots$ defined by $u_{n}:=1$ if
$T^{n}(x)\in[0,\theta)$ and $u_{n}:=0$ otherwise. As shown by Morse and
Hedlund, $\bm{u}$ is a Sturmian word and, up to changing at most two letters,
all Sturmian words over a binary alphabet arise as codings of the above type
for some choice of $\theta$ and $x$. In particular, for the purposes of
establishing our transcendence results we may work exclusively with codings as
defined above. The number $\theta$ is equal to the slope of the Sturmian word,
as defined in Section 1. The $\theta$-coding of $0$ is in particular called
the _characteristic Sturmian word of slope $\theta$_.

The main result of this section is as follows:

######  Theorem 4.

Let $\theta\in(0,1)$ be irrational. Given a positive integer $k$, let
$c_{0},\ldots,c_{k}\in\mathbb{C}$ and $x_{1},\ldots,x_{k}\in I$. Suppose that
$x_{i}-x_{j}\not\in\mathbb{Z}\theta+\mathbb{Z}$ for all $i\neq j$. Writing
$\langle u_{n}^{(i)}\rangle_{n=0}^{\infty}$ for the $\theta$-coding of
$x_{i}$, for $i=1,\ldots,k$, define
$u_{n}:=c_{0}+\sum_{i=1}^{k}c_{i}u_{n}^{(i)}$ for all $n\in\mathbb{N}$. Then
$\bm{u}=\langle u_{n}\rangle_{n=0}^{\infty}$ is stuttering.

###### Proof.

We start by recalling some basic facts about the continued-fractions. Write
$[a_{0},a_{1},a_{2},a_{3},\ldots]$ for the simple continued-fraction expansion
of $\theta$. Given $n\in\mathbb{N}$, we write
$\frac{p_{n}}{q_{n}}:=[a_{0},a_{1},\ldots,a_{n}]$ for the $n$-th convergent.
Then $\langle q_{n}\rangle_{n=0}^{\infty}$ is a strictly increasing sequence
of positive integers such that $\|q_{n}\theta\|=|q_{n}\theta-p_{n}|$, where
$\|\alpha\|$ denotes the distance of a given number $\alpha\in\mathbb{R}$ to
the nearest integer. We moreover have that $q_{n}\theta-p_{n}$ and
$q_{n+1}\theta-p_{n+1}$ have opposite signs for all $n$. Finally we have the
_law of best approximation_ : $q\in\mathbb{N}$ occurs as one of the $q_{n}$
just in case $\|q\theta\|<\|q^{\prime}\theta\|$ for all $q^{\prime}$ with
$0<q^{\prime}<q$.

To establish that $\bm{u}$ is stuttering, given $w>0$ we define $\langle
r_{n}\rangle_{n=0}^{\infty}$ to be the subsequence of $\langle
q_{n}\rangle_{n=0}^{\infty}$ comprising all terms $q_{n}$ such that
$\|q_{n}\theta\|=q_{n}\theta-p_{n}>0$. Note that we either have $r_{n}=q_{2n}$
for all $n$ or $r_{n}=q_{2n+1}$ for all $n$, so $\langle
r_{n}\rangle_{n=0}^{\infty}$ is an infinite sequence that diverges to
infinity. Next, write $d=(k+1)w$ and for all $n\in\mathbb{N}$ define $s_{n}$
be the greatest number such that the words $u_{0}\ldots u_{s_{n}}$ and
$u_{r_{n}}\cdots u_{r_{n}+s_{n}}$ have Hamming distance at most $2d$. Since
$\bm{u}$ is not ultimately periodic, $s_{n}$ is thereby well-defined.

Condition S2. Denote the set of positions at which $u_{0}\ldots u_{s_{n}}$ and
$u_{r_{n}}\ldots u_{s_{n}+r_{n}}$ differ by

$\displaystyle\Delta_{n}:=\big{\\{}m\in\\{0,\ldots,s_{n}\\}:u_{m}\neq
u_{m+r_{n}}\big{\\}}\,.$ (1)

We claim that for $n$ sufficiently large, $m\in\Delta_{n}$ if and only if
there exists $\ell\in\\{1,\ldots,k\\}$ such that one of the following two
conditions holds:

  1. (i)

$T^{m}(x_{\ell})\in[1-\|r_{n}\theta\|,1)$,

  2. (ii)

$T^{m}(x_{\ell})\in[\theta-\|r_{n}\theta\|,\theta)$.

We claim furthermore that for all $m$ there is most $\ell$ such that one of
above conditions holds.

Assuming the claim, since $T^{m}(x_{\ell})\in[1-\|r_{n}\theta\|,1)$ if and
only if $T^{m+1}(x_{\ell})\in[\theta-\|r_{n}\theta\|,\theta)$, it follows that
the elements of $\Delta_{n}$ come in consecutive pairs, i.e., we can write

$\Delta_{n}=\bigcup_{j=1}^{d}\\{i_{j}(n),i_{j}(n)+1\\}\,,$

where $i_{1}(n)<\ldots<i_{d}(n)$ are the elements $m\in\Delta_{n}$ that
satisfy Condition (i) above for some $\ell$.

It remains to prove the claim. To this end note that for a fixed
$\ell\in\\{1,\ldots,k\\}$ we have $u_{m}^{(\ell)}\neq u_{m+r_{n}}^{(\ell)}$
iff exactly one of $T^{m}(x_{\ell})$ and $T^{m+r_{n}}(x_{\ell})$ lies in the
interval $[0,\theta)$ iff either Condition (i) or Condition (ii) holds.
Moreover, since $x_{\ell}-x_{\ell^{\prime}}\neq\theta\pmod{1}$ for
$\ell\neq\ell^{\prime}$, we see that for $n$ sufficiently large there is at
most one $\ell\in\\{1,\ldots,k\\}$ such that one of these two conditions
holds. Equivalently, for all $m$ there is at most one $\ell$ such that
$u_{m}^{(\ell)}\neq u_{m+r_{n}}^{(\ell)}$. We deduce that $u_{m}\neq
u_{m+r_{n}}$ if and only if $u_{m}^{(\ell)}\neq u_{m+r_{n}}^{(\ell)}$ for some
$\ell\in\\{1,\ldots,k\\}$. This concludes the proof of the claim.

Condition S1. Our objective is to show that $s_{n}\geq wr_{n}$ for all
$n\in\mathbb{N}$. We have already established that there are $d=(k+1)w$
distinct $m\in\Delta_{n}$ that satisfy Condition (i), above, for some
$\ell\in\\{1,\ldots,k\\}$. Thus there exists $\ell_{0}\in\\{1,\ldots,k\\}$ and
$\Delta^{\prime}_{n}\subseteq\Delta_{n}$ such that $|\Delta^{\prime}_{n}|\geq
w$ and all $m\in\Delta_{n}^{\prime}$ satisfy Condition (i) for
$\ell=\ell_{0}$. In this case we have
$\|(m_{1}-m_{2})\theta\|<\|r_{n}\theta\|$ for all
$m_{1},m_{2}\in\Delta_{n}^{\prime}$. By the law of best approximation it
follows that every two distinct elements of $\Delta_{n}^{\prime}$ have
difference strictly greater than $r_{n}$. But this contradicts
$|\Delta_{n}^{\prime}|=w$ given that
$\Delta_{n}^{\prime}\subseteq\\{0,1,\ldots,wr_{n}\\}$.∎

Condition S3. By definition of $i_{1}(n),\ldots,i_{d}(n)$, for all
$j\in\\{1,\ldots,d\\}$ there exists $\ell_{j}(n)\in\\{1,\ldots,k\\}$ with
$T^{i_{j}(n)}(x_{\ell_{j}(n)})\in[1-\|r_{n}\theta\|,1)$. Now, for all
$n\in\mathbb{N}$ and $1\leq j_{1}<j_{2}\leq d$ we have

$\displaystyle\|(i_{j_{2}}(n)-i_{j_{1}}(n))\theta+x_{\ell_{j_{2}}(n)}-x_{\ell_{j_{1}}(n)}\|\leq\|r_{n}\theta\|\,.$
(2)

We claim that the left-hand side of (2) is non-zero. Indeed, the claim holds
if $\ell_{j_{2}}(n)=\ell_{j_{1}}(n)$ because $\theta$ is irrational, while the
claim also holds in case $\ell_{j_{2}}(n)\neq\ell_{j_{1}}(n)$ since in this
case we have
$x_{\ell_{j_{2}}(n)}-x_{\ell_{j_{1}}(n)}\not\in\mathbb{Z}\theta+\mathbb{Z}$ by
assumption. Since moreover the right-hand side of (2) tends to zero as $n$
tends to infinity, we have that $i_{j_{2}}(n)-i_{j_{1}}(n)=\omega(1)$. On the
other hand, if $\ell_{j_{2}}(n)=\ell_{j_{1}}(n)$ then we even have
$i_{j_{2}}(n)-i_{j_{1}}(n)\geq r_{n}=\omega(\log r_{n})$ by the law of best
approximation. Hence we certainly have $i_{d}(n)-i_{1}(n)=\omega(\log r_{n})$.

Finally, defining $i_{0}(n):=0$ we have $i_{1}(n)-i_{0}(n)=\omega(1)$ by the
requirement that $T^{i_{1}(n)}(x_{\ell_{1}(n)})\in[1-\|r_{n}\theta\|,1)$ and
the fact that $\|r_{n}\theta\|$ converges to $0$. Setting $i_{d+1}(n):=s_{n}$
for all $n$, we also have $i_{d+1}(n)-i_{d}(n)=\omega(1)$ by the maximality
condition in the definition of $s_{n}$.

Condition S4. Consider $m\in\Delta_{n}$ satisfying Condition (i) above, i.e.,
such that $T^{m}(x_{\ell})\in[1-\|r_{n}\theta\|,1)$ for some
$\ell\in\\{1,\ldots,k\\}$. Then we have

$u^{(\ell)}_{m}=0,\,u^{(\ell)}_{m+1}=1\quad\text{and}\quad
u^{(\ell)}_{m+r_{n}}=1,\,u^{(\ell)}_{m+r_{n}+1}=0\,.$

Moreover for all $\ell^{\prime}\neq\ell$ and $n$ sufficiently large we have

$u^{(\ell^{\prime})}_{m}=u^{(\ell^{\prime})}_{m+r_{n}}\quad\text{and}\quad
u^{(\ell^{\prime})}_{m+1}=u^{(\ell^{\prime})}_{m+r_{n}+1}\,.$

We conclude that $u_{m}+u_{m+1}=u_{m+r_{m}}+u_{m+r_{n}+1}$, establishing
Condition S4. ∎

##  4 A Transcendence Result

######  Theorem 5.

Let $A$ be a finite set of algebraic numbers and suppose that $\bm{u}\in
A^{\omega}$ is a stuttering sequence. Then for any algebraic number $\beta$
with $|\beta|>1$, the sum $\alpha:=\sum_{n=0}^{\infty}\frac{u_{n}}{\beta^{n}}$
is transcendental.

###### Proof.

Suppose for a contradiction that $\alpha$ is algebraic. By scaling we can
assume without loss of generality that $A$ consists solely of algebraic
integers. Let $K=\mathbb{Q}(\beta)$ be the field generated over $\mathbb{Q}$
by $\beta$ and write $S\subseteq M(K)$ for the set comprising all infinite
places of $K$ and all finite places of $K$ corresponding to prime-ideal
divisors of the ideal $\beta\mathcal{O}_{K}$.

Applying the stuttering condition (for a value of $w$ to be determined later),
we obtain $d\geq 2$ such that for all $n\in\mathbb{N}$ there are positive
integers $r_{n},s_{n},i_{1}(n),\ldots,i_{d}(n)$ satisfying conditions S1–S4.
By condition S2, for all $n$ if we define

$c_{j}(n):=(u_{i_{j}(n)+r_{n}}-u_{i_{j}(n)})+(u_{i_{j}(n)+r_{n}+1}-u_{i_{j}(n)+1})\beta^{-1},\quad
j\in\\{1,2,\ldots,d\\}$

and $\alpha_{n}:=\sum_{j=0}^{r_{n}}{u_{j}}{\beta^{r_{n}-j}}$ then we have

$\displaystyle\left|\beta^{r_{n}}\alpha-\alpha-\alpha_{n}-c_{1}(n)\beta^{-i_{1}(n)}-\cdots-
c_{d}(n)\beta^{-i_{d}(n)}\right|<|\beta|^{-s_{n}}\,,$ (3)

Note that $c_{1}(n),\ldots,c_{d}(n)$ are non-zero by Condition S4. By passing
to a subsequence we can furthermore assume without loss of generality that
$c_{1}=c_{1}(n),\ldots,c_{d}=c_{d}(n)$ are constant, independent of $n$.

To set up the application of the Subspace Theorem, define a family of linear
forms $L_{i,v}$, for $1\leq i\leq 3+d$ and $v\in{S}$, by

$\begin{array}[]{rcl}L_{i,v}(x_{1},\ldots,x_{3+d})&:=&x_{i}\;\mbox{for all
$(i,v)\neq(3,v_{0})$, and }\\\ L_{3,v_{0}}(x_{1},\ldots,x_{3+d})&:=&\alpha
x_{1}-\alpha x_{2}-x_{3}-\sum_{j=1}^{d}c_{j}x_{3+j}\,.\end{array}$

Write
$\bm{b}_{n}:=\left(\beta^{r_{n}},1,\alpha_{n},\beta^{-i_{1}(n)},\ldots,\beta^{-i_{d}(n)}\right)$
and let $M\geq 2$ be an upper bound of the set of real numbers

$\left\\{|\gamma|_{v}:\gamma\in\\{\beta\\}\cup A,\,v\in S\right\\}\,.$

Then for all $v\neq v_{0}$ we have

$|L_{3,v}(\bm{b}_{n})|_{v}=|\alpha_{n}|_{v}\leq\sum_{j=0}^{r_{n}}M^{j+1}\leq
M^{r_{n}+2}\,,$

while $|L_{3,v_{0}}(\bm{b}_{n})|_{v_{0}}\leq|\beta|^{-s_{n}/{\deg(\beta)}}$ by
(3). Furthermore, for $i\neq 3$, by the product formula we have
$\prod_{v\in{S}}|L_{i,v}(\bm{b}_{n})|_{v}=1$. Altogether we have

$\displaystyle\prod_{v\in{S}}\prod_{i=1}^{d+3}|L_{i,v}(\bm{b}_{n})|_{v}\leq
M^{(r_{n}+2)|S|}\cdot|\beta|^{-s_{n}/{\deg(\beta)}}\,.$ (4)

Since $s_{n}\geq wr_{n}$ we have that for $w$ sufficiently large the right-
hand side of (4) is less than $|\beta|^{-s_{n}/{2\deg(\beta)}}$. On the other
hand there exists a constant $c$ such that the height of $\bm{b}_{n}$
satisfies the bound $H(\bm{b}_{n})\leq|\beta|^{cs_{n}}$ for all $n$. Thus
there exists $\varepsilon>0$ such that the right-hand side of (4) is at most
$H(\bm{b}_{n})^{-\varepsilon}$ for all $n$. Since $\bm{b}_{n}$ is a vector of
$S$-units we can apply the Subspace Theorem to obtain a non-zero linear form
$L(x_{1},\ldots,x_{3+d})$ with coefficients in $K$ such that $L(\bm{b}_{n})=0$
for infinitely many $n\in\mathbb{N}$.

Denote by $\mathrm{vars}(L)\subseteq\\{x_{1},\ldots,x_{3+d}\\}$ the set of
variables that appear in $L$ with non-zero coefficient. We claim that
$x_{3}\in\mathrm{vars}(L)$. Indeed, suppose for a contradiction that
$x_{3}\not\in\mathrm{vars}(L)$. Then for all $n$, $L(\bm{b}_{n})$ is a fixed
linear combination of the numbers
$\beta^{r_{n}},1,\beta^{-i_{1}(n)},\ldots,\beta^{-i_{d}(n)}$. By Item S3 the
gaps beween successive exponents in these powers of $\beta$ tend to infinity
with $n$ and hence a fixed linear combination of such powers cannot vanish for
arbitrarily large $n$.

We have that $L(\bm{b}_{n})$ is a linear combination of a most $r_{n}+d+1$
powers of $\beta$, whose respective exponents lie in the set
$\\{0,1,\ldots,r_{n}\\}\cup\\{-i_{1}(n),\ldots,-i_{d}(n)\\}$. From Item S3
there exists $j_{0}\in\\{1,\ldots,d-1\\}$ such that
$i_{j_{0}+1}(n)-i_{j_{0}}(n)=\omega(\log r_{n})$. By Proposition 2 the
condition $L(\bm{b}_{n})=0$ entails, for $n$ sufficiently large, that
$\mathrm{vars}(L)$ is contained either in $\\{x_{1},\ldots,x_{j_{0}+3}\\}$ or
in $\\{x_{j_{0}+4},\ldots,x_{d}\\}$. Since we know that
$x_{3}\in\mathrm{vars}(L)$ the former inclusion applies.

We have established that
$x_{3}\in\mathrm{vars}(L)\subseteq\\{x_{1},\ldots,x_{j_{0}+3}\\}$. Thus by a
suitable linear combination of the forms $L_{3,v_{0}}$ and $L$, so as to
eliminate the variable $x_{3}$, we obtain a non-zero linear form
$L^{\prime}(x_{1},\ldots,x_{3+d})$ with algebraic coefficients that does not
mention $x_{3}$ and such that $|L^{\prime}(\bm{b}_{n})|<|\beta|^{-s_{n}}$ for
infinitely many $n$. Note that $L^{\prime}(\bm{b}_{n})$ is a fixed linear
combination of at most $d+2$ powers of $\beta$, with respective exponents in
the set $\\{r_{n},0,-i_{1}(n),\ldots,-i_{d}(n)\\}$. Moreover by Item S3 the
gaps between consecutive elements of this set tend to infinity with $n$. It
follows that $|L^{\prime}(\bm{b}_{n})|\gg|\beta|^{-i_{d}(n)}$. But since
$s_{n}-i_{d}(n)=\omega(1)$, this contradicts
$|L^{\prime}(\bm{b}_{n})|<|\beta|^{-s_{n}}$. ∎

We have the following immediate corollary of Theorem 4 and Theorem 5.

######  Theorem 6.

Let $\beta$ be an algebraic number with $|\beta|>1$. Let $0<\theta<1$ be
irrational and let $x_{1},\ldots,x_{k}\in I$ be such that
$x_{i}-x_{j}\not\in\mathbb{Z}\theta+\mathbb{Z}$ for $i\neq j$. For
$i=1,\ldots,k$, define
$\alpha_{i}:=\sum_{n=0}^{\infty}\frac{u_{n}^{(i)}}{\beta^{n}}$, where $\langle
u_{n}^{(i)}\rangle_{n=0}^{\infty}$ is the $\theta$-coding of $x_{i}$. Then the
set $\\{1,\alpha_{1},\ldots,\alpha_{k}\\}$ is linearly independent over the
field $\overline{\mathbb{Q}}$ of algebraic numbers.

##  5 Application to Limit Sets of Contracted Rotations

Let $0<\lambda,\delta<1$ be real numbers such that $\lambda+\delta>1$. We call
the map $f=f_{\lambda,\delta}:I\rightarrow I$ given by $f(x):=\\{\lambda
x+\delta\\}$ a _contracted rotation_ with slope $\lambda$ and _offset_
$\delta$. Associated with $f$ we have the map
$F=F_{\lambda,\delta}:\mathbb{R}\rightarrow\mathbb{R}$, given by
$F(x)=\lambda\\{x\\}+\delta+\lfloor x\rfloor$. We call $F$ a _lifting_ of $f$:
it is characterised by the properties that $F(x+1)=F(x)+1$ and
$\\{F(x)\\}=f(\\{x\\})$ for all $x\in\mathbb{R}$. The _rotation number_
$\theta=\theta_{\lambda,\delta}$ of $f$ is defined by

$\theta:=\lim_{n\rightarrow\infty}\frac{F^{n}(x_{0})}{n}\,,$

where the limit exists and is independent of the initial point
$x_{0}\in\mathbb{R}$.

If the rotation number $\theta$ is irrational then the restriction of $f$ to
the _limit set_ $\bigcap_{n\geq 0}f^{n}(I)$ is topologically conjugated to the
rotation map $T=T_{\theta}:I\rightarrow I$ with $T(y)=\\{y+\theta\\}$. The
closure of the limit set is a Cantor set $C=C_{\lambda,\delta}$, that is, $C$
is compact, nowhere dense, and has no isolated points. On the other hand, if
$\theta$ is rational then the limit set $C$ is the unique periodic orbit of
$f$. For each choice of slope $0<\lambda<1$ and irrational rotation number
$0<\theta<1$, there exists a unique offset $\delta$ such that
$\delta+\lambda>1$ and the map $f$ has rotation number $\theta$. It is known
that such $\delta$ must be transcendental if $\lambda$ is algebraic [12].

$1$$\delta$$\delta+\lambda-1$$0$$\frac{1-\delta}{\lambda}$$1$ Figure 1: A plot
of $f_{\lambda,\delta}:I\rightarrow I$

The main result of this section is as follows:

######  Theorem 7.

Let $0<\lambda,\theta<1$ be such that $\lambda$ is algebraic and $\theta$ is
irrational. Let $\delta$ be the unique offset such that the contracted
rotation $f_{\lambda,\delta}$ has rotation number $\theta$. Then every element
of the limit set $C_{\lambda,\delta}$ other than $0$ and $1$ is
transcendental.

A special case of Theorem 7, in which $\lambda$ is assumed to be the
reciprocal of an integer, was proven in [3, Theorem 1.2]. In their discussion
of the latter result the authors conjecture the truth of Theorem 7, i.e., the
more general case in which $\lambda$ may be algebraic. As noted in [3], while
$C_{\lambda,\delta}$ is homeomorphic to the Cantor ternary set, it is a
longstanding open problem, formulated by Mahler [9], whether the Cantor
ternary set contains irrational algebraic elements.

###### Proof of Theorem 7.

For a real number $0<x<1$ define

$\displaystyle\xi_{x}$ $\displaystyle:=$ $\displaystyle\sum_{n\geq
1}\left(\lceil x+(n+1)\theta\rceil-\lceil x+n\theta\rceil\right)\lambda^{n}$
$\displaystyle\xi^{\prime}_{x}$ $\displaystyle:=$ $\displaystyle\sum_{n\geq
1}\left(\lfloor x+(n+1)\theta\rfloor-\lfloor
x+n\theta\rfloor\right)\lambda^{n}\,.$

Note that for all $x$ the binary sequence $\langle\,\lceil
x+(n+1)\theta\rceil-\lceil x+n\theta\rceil:n\in\mathbb{N}\,\rangle$ is the
coding of $-x-\theta$ by $1-\theta$ (as defined in Section 3) and hence is
Sturmian of slope $1-\theta$. Similarly, the binary sequence $\langle\,\lfloor
x+(n+1)\theta\rfloor-\lfloor x+n\theta\rfloor:n\in\mathbb{N}\,\rangle$ is the
coding of $x+\theta$ by $\theta$ and hence is Sturmian of slope $\theta$. Thus
for all $x$, both $\xi_{x}$ and $\xi^{\prime}_{x}$ are Sturmian numbers.

It is shown in [3, Lemma 4.2]222The proof of the lemma is stated for $\beta$
an integer but carries over without change for $\beta$ algebraic. that for
every element of $y\in C_{\lambda,\delta}\setminus\\{0,1\\}$, either there
exists $z\in\mathbb{Z}$ and $0<x<1$ with $x\not\in\mathbb{Z}\theta+\mathbb{Z}$
such that

$y=z+\xi_{0}-\xi_{-x}$

or else there exists a strictly positive integer $m$ and
$\gamma\in\mathbb{Q}(\beta)$ such that

$y=\gamma+(1-\beta^{-m})\,\xi^{\prime}_{0}\,.$

In either case, transcendence of $y$ follows from Theorem 6. ∎

Acknowledgements. The authors would like to thank Pavol Kebis and Andrew
Scoones for helpful feedback and corrections.

## References

  * [1] B. Adamczewski and Y. Bugeaud, “On the complexity of algebraic numbers I, Expansions in integer bases”, Ann. Math. 165, (2007), pp. 547–566.
  * [2] B. Adamczewski, Y. Bugeaud and F. Luca, “Sur la complexité des nombres algébriques”, C. R. Acad. Sci. Paris 339, (2004), pp. 11–14.
  * [3] Y. Bugeaud, D. H. Kim, M. Laurent and A. Nogueira. “On the Diophantine nature of the elements of Cantor sets arising in the dynamics of contracted rotations”, Ann. Scuola Normale Superiore di Pisa 5, Vol. XXII, (2021), pp. 1691–1704.
  * [4] E. M. Coven and G. A. Hedlund. “Sequences with minimal block growth”, Math Systems Theory 7, (1973), pp. 138–153.
  * [5] S. Ferenczi and C. Mauduit, “Transcendence of Numbers with a Low Complexity Expansion”, Journal of Number Theory 67 (1997), pp. 146–161.
  * [6] H W. Lenstra, “Finding small degree factors of lacunary polynomials”, Number Theory in Progress: Diophantine Problems and Polynomials, Proceedings of the International Conference on Number Theory, (1997).
  * [7] F. Luca, J. Ouaknine and J. Worrell, “On the transcendence of a series related to Sturmian words”, arXiv:2204.08268 (2022).
  * [8] J. H. Loxton and A. J. van der Poortrn, “Arithmetic properties of certain functions in several variables III”, Bull. Austral. Math. Soc. 16, (1977), pp. 15–47.
  * [9] K. Mahler. “Some suggestions for further research.”, Bull. Austral. Math. Soc. 29 (1984), pp. 101–108.
  * [10] M. Morse and G. A. Hedlund. “Symbolic dynamics”, Amer. J. Math 60, (1938), pp. 815–866.
  * [11] M. Morse and G. A. Hedlund. “Symbolic dynamics II: Sturmian Trajectories.”, Amer. J. Math 62(1), (1940), pp. 1–4.
  * [12] M. Laurent and A. Noguiera. “Rotation number of contracted rotations”, J. Modern Dynamics  12, (2018), pp. 175–191.


#  Evidence of social learning across symbolic cultural barriers in  sperm
whales

Antonio Leitao  CENTAI Institute, Corso Inghilterra 3, 10138 TO, Italy
Project CETI, New York, NY, 10003 USA  Maxime Lucas  CENTAI Institute, Corso
Inghilterra 3, 10138 TO, Italy  Project CETI, New York, NY, 10003 USA  Simone
Poetto  CENTAI Institute, Corso Inghilterra 3, 10138 TO, Italy  Project CETI,
New York, NY, 10003 USA  Center for Modern Interdisciplinary Technologies,
Nicolaus Copernicus University, Toruń, Poland  Taylor A. Hersh  Comparative
Bioacoustics Group, Max Planck Institute for Psycholinguistics, Nijmegen,
Netherlands  Marine Mammal Institute, Oregon State University, Newport, OR,
United States  Shane Gero  Project CETI, New York, NY, 10003 USA  Department
of Biology, Carleton University, Ottawa, Ontario, Canada  The Dominica Sperm
Whale Project, Roseau, Dominica  David F. Gruber  Project CETI, New York, NY,
10003 USA  Department of Natural Sciences, City University of New York, Baruch
College, New York, NY, United States  Michael Bronstein  Project CETI, New
York, NY, 10003 USA  Department of Computer Science, University of Oxford,
Oxford, UK  Giovanni Petri  CENTAI Institute, Corso Inghilterra 3, 10138 TO,
Italy  Project CETI, New York, NY, 10003 USA  NPLab, Network Science
Institute, Northeastern University London, London, UK  IMT Lucca, Lucca, Italy

###### Abstract

We provide quantitative evidence suggesting social learning in sperm whales
across socio-cultural boundaries, using acoustic data from the Pacific and
Atlantic Oceans. Traditionally, sperm whale populations are categorized into
clans based on their vocal repertoire: the rhythmically patterned click
sequences (codas) that they use. Among these codas, identity codas function as
symbolic markers for each clan, accounting for 35-60% of codas they produce.
We introduce a computational method to model whale speech, which encodes
rhythmic micro-variations within codas, capturing their vocal style. We find
that vocal style-clans closely align with repertoire-clans. However, contrary
to vocal repertoire, we show that sympatry increases vocal style similarity
between clans for non-identity codas, i.e. most codas, suggesting social
learning across cultural boundaries. More broadly, this subcoda structure
model offers a framework for comparing communication systems in other species,
with potential implications for deeper understanding of vocal and cultural
transmission within animal societies.

##  1 Introduction

Cultural transmission is defined as the transmission of information or
behaviors between individuals of the same species by means of social learning
[1]. While humans represent a benchmark of such capacity, cultural
transmission has been observed in a wide variety of animals, including
cetaceans [2, 3], songbirds [4], non-human primates [5], and insects [6]. It
typically takes one of three forms: vertical transmission, from adult kin to
young kin; oblique transmission, from unrelated adults to young; or horizontal
transmission, from peer to peer [7].

When animals have the capacity for social learning, group-specific differences
can arise and remain stable when they become distinguishable by symbolic
markers: arbitrary group-identity signals that are recognizable by both
members of the group itself and by members of other groups [8, 9]. In humans,
symbolic markers can take a myriad of forms, ranging from visible signs, such
as tattoos or garments, to communication cues or signals, such as idiomatic
sentences or accents [8, 9, 10]. In animals, however, quantitative evidence of
symbolic markers is remarkably scarce, one exception being recent results on
the use of identity codas in sperm whale social communication [11].

Figure 1: Statistical modeling of subcoda structure in sperm whales.  A Sperm
whale communication consists of rhythmic sequences of clicks, called codas. A
coda is specified by a sequence of inter-click intervals (ICIs). Codas are
classified into types based on their rhythmic pattern, which can have various
degrees of regularity (e.g., 4R2 vs 1+3). B Social groups of sperm whales
employ specific vocal repertoires: the set of coda types they use and their
associated usage frequencies. As an illustration, we show those of the EC1 and
EC2 clans from the Dominica dataset [12]. Only the most numerous coda types
are shown: the rest of the vocal repertoires consists of more coda types with
residual frequencies. C The subcoda structure can be modeled by considering
rhythmic variations within codas of the same coda type. To do so, codas are
represented as sequences of discrete inter-click intervals (dICIs), by
discretizing absolute ICIs into discrete bins, which can then be considered
akin to symbols (e.g. A, B, C, …), providing a tokenization of codas.
Different instances of a single coda type can correspond to slightly different
dICI sequences. The resulting dICI sequences are modeled using variable-length
Markov chains, which can be represented as subcoda trees. These trees can be
built for an individual speaker or for a group of speakers, and capture the
statistical and memory structures of rhythm variations within codas and in the
transitions between those. In other words, the tree captures a vocal style—how
they say what they say. The vocal styles of different groups of sperm whales
can be quantitatively compared by calculating a distance between their subcoda
trees.

Sperm whales live in multi-tiered societies and have a complex vocal
communication system [13]. They communicate through rhythmic patterns (codas)
of short broadband sounds (clicks), which have traditionally been classified
into a finite set of coda types based on the total number of clicks, their
rhythm, and their tempo [14, 15] (Fig. 1A).  For example, the 4-regular (4R2)
type refers to a pattern of four evenly spaced clicks, whereas the 1+3 type
refers to two clicks separated by a longer pause followed by two clicks in
quick succession. Coda types are thus standardized rhythmic patterns, but
individual vocalizations of a given coda type exhibit micro-variations around
that pattern.

The set of vocalized coda types (coda usage) combined with how frequently each
is vocalized (coda frequency) makes up a vocal repertoire (Fig. 1B).  For
example, the 4R2 coda is used by many sperm whales, but other coda types are
more specific in their usage or frequency to certain groups of sperm whales.
While there is evidence of individual variation in vocal repertoires [16, 17,
18], sperm whales belonging to the same social unit—a stable, matrilineally-
based group of whales, share a common vocal repertoire that is stable across
years [17, 18, 19]. Social units that share substantial parts of their
repertoire are said to be part of the same vocal clan [20, 21]. There is clear
social segregation between members of different clans, even when living in
sympatry, and thus clans mark a higher level of social organization, which
appears to be defined on the basis of cultural vocal markers [20, 21, 11] (see
Table 1 for a summary of the key concepts).

The clan specific and frequent usage of certain coda types, termed identity
codas [15, 11], align with the expectations for symbolic markers of group
membership [9]. Furthermore, quantitative evidence that sperm whales
themselves use identity codas as such markers has recently emerged: the more
two clans overlap in geographic space, the more different their identity coda
usage is [11]. This is consistent with computational models [9] of the
evolution of symbolic marking, which predict that differences between cultural
norms will be starkest when inter-group interactions are more common (e.g., in
boundary or overlap regions).

All remaining coda types have been referred to as non-identity (non-ID) codas
and constitute a very large fraction of sperm whales’ total number of coda
utterances. In fact, the total number of emitted non-ID codas accounts for
more than 6 out of 10 codas (see SM Section 1.1 for the counts per clan and
per coda type). This begets the question: if ID codas are used as clan
identity signals, what can be said about the remaining 65% of codas?

Here, we introduce a novel descriptive framework that focuses on the subcoda
structure, that is, the  rhythmic micro-variations of intervals between clicks
within codas  (Fig. 1C).  This framework, formally encoded in what we call a
“subcoda tree”, captures how codas are uttered: a vocal style. We find that
variations in this vocal style, even for a single coda type, identify an
individual’s social unit and clan, effectively fingerprinting vocal
repertoires. With this, we add a new dimension with respect to previous
approaches based on which codas are said—vocal repertoires. Thus, we propose a
new concept of vocal identity of sperm whales that comprises both vocal style
and vocal repertoire.

By applying our modeling framework to acoustic data from the Atlantic and
Pacific Oceans, we obtain two main results. First, we partition sperm whale
populations into vocal style-defined clans, which we find to recapitulate the
previously defined vocal repertoire clans. This confirms that our method does
capture meaningful speech characteristics. Second, and crucially, we find that
the vocal style of non-ID codas is more similar for more sympatric clans, i.e.
clans whose territory overlaps more spatially. In contrast, we do not find an
effect of sympatry on the similarity of vocal styles when studying only ID
codas. This suggests that geographic overlap induces vocal styles to become
more similar between clans, without jeopardizing each clan’s acoustic identity
signals. Our results strengthen previous results on the use of ID codas as
symbolic markers, while  supporting cultural transmission and social learning
of vocalizations among whales of _different_ clans, as predicted by
theoretical models [22].

Concept |  Description
---|---
Click |  Sharp broadband pulses [23]
Inter-click interval (ICI) |  Time interval between two consecutive clicks
Coda |  Stereotyped, short series of clicks produced by sperm whales in social situations [14]
Coda type |  Categorical classification of codas based on rhythm and tempo of coda inter-click intervals [16]
Coda frequency |  Usage frequency of each coda type
Coda sample |  Set of codas recorded during one event
Coda usage |  Set of coda types used by a group of whales
Identity codas |  Subset of coda types most frequently used by a sperm whale clan; canonically used to define vocal clans.
Non-identity codas |  Coda types produced by whales belonging to multiple vocal clans (i.e., all coda types that are not identity codas)
Vocal clan |  Higher-order level of social organization delineated based on social units that share a substantial part of their vocal repertoire [11, 20]
Vocal repertoire |  Coda usage and frequency combined. Description of what sperm whales say.
Vocal style |  Encodes the rhythmic variations within codas. Description of how sperm whales emit codas
Vocal identity |  Concept comprising both vocal style and vocal repertoire
Table 1: Summary of key concepts

## Results

### Subcoda structure captures variability in sperm whale communication

Figure 2: Vocal style recovers social structure of vocal clans in Dominica
sperm whales. A We show the similarity of vocal style, measured as subcoda
tree-distance, among social units within a vocal clan (within, darker color
shade) and between two clans (between, lighter color shade). We used the
manual clan assignments from [21] as ground truth. Vocal style is more similar
within clans than between clans. B We show the hierarchical clustering of
social unit subcoda trees. Each leaf corresponds to a social unit, and the
colors below show their known clan assignments. The clustering recovers the
two-clan structure observed in past work [21].

We model the internal structure of codas,  in terms of rhythmic variations at
the level of clicks, by using variable length Markov chains (VLMCs). Our
analytical pipeline is illustrated in Fig. 1C. We build each VLMC in two main
steps. We first convert codas, naturally represented as sequences of
continuous, absolute, inter-click intervals (ICIs), to sequences of discrete
ICIs (dICIs), by discretizing time into bins. In this way, each dICI
represents a narrow range of possible ICI values. The bins have a fixed width
(or resolution) $\delta t$ and thus implicitly correspond to the temporal
resolution of our representation (see Methods for details on the optimal
choice of $\delta t$). Note that although ICIs have units of time (seconds),
dICIs are (unit-less)  symbols (e.g. A, B, C, etc.), representing multiples of
$\delta t$ (and so the smaller $\delta t$, the more the symbols). For example,
the shortest ICIs will be mapped to the symbol A whereas longer ones will be
mapped to symbols further down the alphabet. Hence, each coda (a sequence of
ICIs) is mapped to a sequence of  discrete symbols (a sequence of dICIs). The
second part of the pipeline focuses on modeling  the internal structure of
codas in terms of dICI sequences. Essentially, we want to estimate transition
probabilities from a dICI sub-sequence to the next dICI (Fig. 1B). A standard
way would be to describe this using $k$-order Markov chain models, which
encode information on previous sub-sequences up to $k$ steps in the past of
the sequence. However, it is possible that different sequences of dICIs
contain different amounts of information or memory regarding potential next
dICIs. This is akin to what happens with words (e.g., a word beginning with
“re” can continue in more ways than one starting with “zy”). To account for
this possibility while also retaining only the most compressed statistical
representation of how  codas are structured in terms of dICIs, we employ
VLMCs.

VLMCs are generalizations of standard (fixed-memory) Markov chains that allow
sub-sequences of dICIs of variable lengths . Longer sequences are kept only if
they are significantly more informative in predicting the next dICI than
random chance, yielding an optimally compressed representation (see Methods
for details on model fitting and selection,  including the optimal choice of
$\delta t$). Furthermore, VLMCs naturally have a tree structure (see Fig. 1C),
because of the natural order between sequences and their sub-sequences. In
particular, each node represents a sub-sequence of dICIs, and is equipped with
a probability distribution of transitions to the next dICIs. The origin node
corresponds to the empty sequence, leaf nodes correspond to the longest
sequences, and all nodes forming the branch in between correspond to the sub-
sequences of that leaf node. Thus, we call VLMCs fitted to coda ICI data
subcoda trees.

Note that dICI sequences encode rhythmic variations within codas. Indeed, a
coda type is a standard rhythmic pattern that can be realized with variations
in its ICIs and thus in its dICIs too. For example, the 4R2 coda type can be
vocalized as BCC but also as CBB (in a representation with, say, 26 symbols).
In that sense, subcoda trees, through the dICIs sequences that they contain
and their transition probabilities, capture information about a vocal style.
Four more features of subcoda trees are noteworthy: (i) because the method’s
input is a set of codas, we can build subcoda trees for repertoires
corresponding to different social scales, from individual sperm whales, to
social units, all the way up to vocal clans; (ii) the difference between
different subcoda trees can be measured using a probabilistic distance (see
Methods), which we can use to compare subcoda trees across sperm whale clans;
(iii) certain features of the vocal style can be quantified via metrics on the
subcoda tree: for example we can define a complexity of the vocal style
measured by an entropy on the tree; and (iv) subcoda trees can also be used as
generative models, to create new synthetic codas in the form of dICI sequences
to train downstream machine learning models.

### Vocal style recovers vocal clan structure

Figure 3: Vocal style recovers social structure of vocal clans in Pacific
Ocean sperm whales. A We show the similarity of vocal style, measured as
subcoda tree-distance, between coda samples within a vocal clan (within,
darker color shade) and between a clan and all others (between, lighter color
shade). We used the vocal clans identified in [11]. Vocal style is more
similar within a clan than between clans. B We show the hierarchical
clustering of subcoda trees. Each leaf corresponds to a coda sample, and the
colors below show their vocal clan assignments (based on coda usage) from
[11]. We find generally good overlap between the groups obtained from
clustering vocal style and those from vocal repertoire, with the exception of
the Short clan (red) that is somewhat mixed with the Palindrome (orange) and
Rapid Increasing (yellow) clans.

The information about vocal style contained in subcoda trees is sufficient to
recover the social structure of sperm whales (social units and clans). We show
this in two ways. First, we analyze a dataset from sperm whales in Dominica
(Dominica dataset) [21]. This dataset has rich annotations (coda type
annotations, identity of recorded whales, social relations of recorded whales)
which makes it particularly useful for validation. Specifically, the sperm
whales in the Dominica dataset are divided into well known social clans, each
composed of several social units, each with its own specific vocal
repertoires, and thus can be defined as two different vocal clans. For each
social unit in this dataset, we aggregate the individual whales’  coda samples
and build a subcoda tree. Computing the distance between these trees (see
Methods), we find that the distances between social units within the same clan
are significantly smaller than between clans (Fig. 2A). We also find that an
agglomerative clustering (average linkage, see Methods for details) on the
distance between the subcoda trees correctly clusters social units into their
respective clans (Fig. 2B). Without a priori knowledge of the clan
memberships, we used vocal style to recover the existing classification of
social units into two clans, which was previously done based on similarity
between vocal repertoires (i.e., coda types and usage) [21].

Second, we find that the subcoda structure of synthetic codas, generated from
subcoda trees fitted on real data, closely reproduces that of real codas. To
do this, we first train a simple classifier to assign codas to one of the two
vocal clans, based on coda type. Variations of the same classifier, trained on
the same real data, have been shown to discriminate between individual whales,
social units, and clans with high accuracy [12]. We train the classifier on
real codas, and then test it on both real and synthetic ones. The synthetic
codas were generated using the subcoda tree of each clan, with a number of
codas similar to that of the original dataset for a fair comparison (see
Methods for details). We find that synthetic codas are correctly classified
into their clans with an accuracy close ($\sim 85\%$) to that obtained on the
real data ($\sim 90\%$, see Supplementary Materials Section $4$).

Motivated by these results, we extend our analysis to a much larger dataset
from the Pacific Ocean (Pacific dataset) [11]. This dataset is more sparsely
annotated because of the breadth of its spatial coverage. We restricted our
analyses to a well-sampled subset ($n=57$ coda samples) of the full Pacific
dataset (see Methods for details). Coda  samples are only labeled by the
spatial position at which they were recorded, but no information is available
about the identity of the vocalizing sperm whales (see Methods for details).
In fact, each repertoire likely contains codas from multiple individuals of a
single clan. It has recently been shown that these  coda samples can be
divided into seven vocal clans based on their coda usage [11]. We use those
clans as a benchmark for the following analysis.

Since there is no social unit-level information for this dataset, we fit a
subcoda tree for each repertoire (i.e., all of the codas recorded on a single
day in a single region). Trees are significantly more similar for  coda
samples belonging to the same vocal clan than for those belonging to different
vocal clans (Fig. 3A). We also find that clustering  coda samples based on
vocal style returns a dendrogram that closely matches the one obtained from
coda usage in [11] (Fig. 3B). The major exception we find is the Short clan
(red), named because member whales produce short codas with very few clicks,
for which anomalous results were previously reported as well [11]. In our
case, this is due to the Short clan being less well localized in the space of
trees, while the other clans have well-defined centroids (see Supplementary
Materials Fig. $9$ for a low-dimensional representation subcoda tree metric
space).

Therefore, we find that sperm whale vocal clans in the Atlantic Ocean
(Caribbean Sea) and Pacific Ocean can be identified by a vocal identity that
encompasses both clan-specific  vocal repertoire [21, 24, 20, 11] and vocal
style as defined in this work.

### Clan sympatry impacts vocal style of non-ID codas only

Figure 4: Clan overlap influences non-ID coda vocal styles Comparing the
similarities of different VLMC models fit for each Pacific Ocean clan for both
ID and non-ID coda  samples. The y-axis represents the measured distance
between the subcoda trees, and the x-axis shows the geographical clan overlap
(as calculated in [11]). Each point represents a pairwise comparison between
two clans. The effect of overlap on ID coda vocal style similarity is minimal
and non-significant while the opposite is true for non-ID codas: overlapping
clans produce non-ID codas with a more similar vocal style. The VLMC distances
are also typically much greater for ID codas than for non-ID codas. Note that
while these results are visually opposite to those reported in Hersh et al.
[10], they support the same final conclusions (see “Identity and non-identity
codas show different trends” for details).

While interesting, the fact that both vocal repertoires and vocal styles
discriminate between clans might imply that considering both could be
redundant for vocal identity. However, we find that this is not the case when
we consider the functional role of ID versus non-ID codas.

More precisely, different clans can share significant portions of their total
range, overlapping across large swaths of ocean. Such sympatric clans exhibit
a decreasing similarity of their ID coda usage with increasing clan overlap
[11]. This means that the more two clans overlap in space, the more dissimilar
their vocal repertoires are in terms of ID coda types and their usage
frequency. This is consistent with the idea that ID codas are used as symbolic
markers to delineate cultural boundaries between social groups [11, 9]. In
contrast, non-ID coda usage do not show any relationship to clan overlap.

We find the exact opposite effect when considering vocal style. The similarity
in vocal style for ID codas across clans does not depend on the level of clan
overlap (Fig. 4a). In contrast, the similarity in vocal style for non-ID codas
displays a clear and significant increase (i.e., decreasing subcoda tree-
distance) as clan spatial overlap increases (Fig. 4b). In the Supplementary
Materials (see Section $2.4.2$), we show that the same results hold at the
single coda type level, in addition to the whole clan level , along with an
analysis of the confidence intervals. These results imply  that the internal
structure of codas is more similar for groups that likely spend more time in
the same space, akin to accents aligning in human populations that share the
same territory [25, 26].  This also highlights the complementarity of vocal
repertoire and style: the trends are different precisely because the two
concepts describe different aspects of whale speech.

## Discussion

We have presented a general method for modeling animal communication systems
and their complexity based on VLMCs. In the context of sperm whales, this new
method allows the extraction of subcoda trees, which succinctly describe the
internal temporal structure of codas. Previous work on the structure of sperm
whale communication has largely focused on supra-level coda analyses: for
example, by classifying codas into types, quantifying how often different
types are used, and distinguishing between individual whales, social units, or
clans based on those counts [18, 27]. Here, we adopted a more fine-scale
approach by investigating potential structure within codas. To do so, we used
VLMCs to model the transition probability of observing a specific ICI given
the previous ones. A VLMC,  or here a subcoda tree, encodes all those
probabilities but only for  dICI sequences that are informative—other
sequences are automatically discarded. As such, a  subcoda tree is a
statistically validated representation of the internal memory structure of
codas at the level of sequences of clicks.  It contains information about
important rhythmic variations and transitions between them: a vocal style.

Using such representations, we propose a novel concept of vocal identity for
sperm whales composed of vocal repertoire (what they say) and vocal style (how
they say it), the latter being captured by our framework. We find that: (i)
vocal styles vary between social units and clans, and can be used to
distinguish them; (ii) the similarity of clan vocal styles for non-ID codas
increases with increasing spatial overlap, while no change occurs for ID
codas; and (iii) social learning across symbolic cultural boundaries most
parsimoniously explains the observed trends.

### Vocal style recovers hierarchical social structure

Using the Dominica dataset, sperm whales had previously been divided into two
vocal clans, based on their vocal repertoires and observed social interactions
[21]. In our study, comparing the vocal styles of those same whales led to the
same assignment of social units to two vocal clans. Similarly, for the Pacific
dataset, clustering based on vocal styles yielded clans that were in good
agreement with those previously defined based on vocal repertoires [11]
(Supplementary Materials for an extended comparison). The difference between
the two partitions was mainly due to the Short clan, which was more spread out
in subcoda tree space than the other clans, causing overlap with other clans
that showed less variability. This variability could be linked to the fact
that Short clan whales typically make codas with very few (e.g., three or
four) clicks, leading to subcoda trees with very few nodes. In Ref. [11], the
authors observe a similar lack of uniformity in coda usage of the Short clan.

### Identity and non-identity codas show different trends

For ID codas, we show that the similarity between clan vocal styles is not
affected by spatial overlap, while it has recently been shown that the
similarity between clan vocal repertoires decreases with overlap [11]. This
means that spatial overlap does not affect how whales produce ID codas (in
terms of their fine-scale rhythmic structure; our results) but does affect how
often they produce them. In contrast, for non-ID codas, we show that the
similarity between vocal styles increases with spatial overlap between two
clans, while no change was observed for vocal repertoires in previous work on
the same dataset. In other words, increasing spatial overlap is correlated
with more similar fine-scale rhythmic structure of non-ID codas produced by
whales from different clans (our results), but does not affect how often non-
ID codas are produced. Our study thus supports and nuances the results of
Hersh et al. [11]. We provide further support for selection acting to produce
unambiguous, recognizable identity signals in the ID codas. However, ID codas
only account for 35% of the total vocalizations; the remaining 65% of codas
have traditionally been lumped into a catch-all category (i.e., non-ID codas)
and their function remains enigmatic (these numbers are an average over the
Pacific clans, and go up to 93% for non-ID codas when counting number of coda
types instead of number of codas emitted, see SM 1.1 for details). We could
still discriminate among clans using non-ID coda vocal style; however, the
increased similarity of non-ID coda vocal styles between clans with greater
spatial overlap, as demonstrated here, suggests that non-ID codas are likely
vocal cues and not identity signals like the ID codas. Accordingly, vocal
repertoire and vocal style capture different and complementary information on
sperm whale communication, and should be considered in tandem in future
studies.

### Evidence for social learning across cultural boundaries

There are several potential mechanisms driving the similarity in non-ID coda
vocal styles—but not ID coda vocal styles—across spatially overlapped clans:
environmental variation, genetics, and/or social learning.

Local adaptation to specific ecological conditions can lead to geographic
variation in acoustic signals [28]. If environmental pressures alone were
responsible for the trends we observe in sperm whales, this would imply that
(i) more spatially overlapped clans experience more similar environments, (ii)
non-ID coda vocal style is impacted by or dependent on environmental
parameters, and (iii) ID coda vocal style is not impacted by/dependent on
environmental parameters. Although the first point is somewhat intuitive, to
date there is no evidence that coda production systematically varies with
environment. In fact, clans are recognizable across ocean basins, making local
adaptation an unlikely driver of the observed trend in non-ID coda vocal
style.

If genetic relatedness were responsible, this would imply that (i) more
spatially overlapped clans are more genetically related, (ii) non-ID coda
vocal styles are genetically inherited, and (iii) ID coda vocal styles are not
genetically inherited. If all three requirements were met, then the observed
similarity in non-ID coda vocal styles for more spatially overlapped clans
could be due to genetic determination under a general isolation by distance
structure. However, research to date suggests this scenario is unlikely.
Rendell et al. [29] found little evidence to support genetics as an
explanation of differences in vocal dialects among clans in the Pacific Ocean.
Furthermore, Alexander et al. [30] found that regional genetic differentiation
in the Pacific Ocean is very low: while social group is important for
explaining both mitochondrial and nuclear DNA variance, geographic region is
not. This contrasts with results from the Indian Ocean, where region was the
strongest predictor of mitochondrial DNA variance. Given that gene flow in
sperm whales is largely male-mediated and that mitochondrial DNA haplotypes
are broadly shared across the Pacific Ocean, it is unlikely that coda dialects
are genetically determined [30, 31]. Agent-based models grounded in empirical
data from Pacific Ocean sperm whales further support coda usage as socially
learned, not genetically inherited [22]. To fully rule out a genetic
explanation for our results, the analyses in [29] could be replicated for ID
coda usage and non-ID coda usage separately. This would shed light on whether
certain coda types are genetically inherited vs. socially learned, as has been
suggested for some humpback whale (Megaptera novaeangliae) vocalizations [32].

The most parsimonious explanation for the observed similarity of non-ID coda
vocal styles of clans with increasing spatial overlap is social learning
across clan boundaries.  This is remarkable, given that sperm whale clans
belonging to different clans have rarely been observed physically interacting
at sea [3]. However, that does not preclude the possibility that they are
within acoustic range of each other [33] and that cross-cultural social
learning opportunities arise.  This explanation is compatible with (and
bolsters) past work suggesting that ID and non-ID codas function differently
in sperm whale communication, and further suggests that they experience
different evolutionary pressures [22]. Whether social learning has facilitated
stochastic (i.e., cultural drift) or deterministic (i.e., cultural selection)
processes is more difficult to determine, and it is unclear whether the
observed non-ID coda vocal style alignment has been neutral or adaptive [34,
28]. Importantly, these findings  suggest that vocal learning in sperm whales
may not be limited to vertical transmission from related adults to young kin,
but that horizontal and/or oblique social learning from outside the natal
social unit might also be occuring.

Vocal identity in sperm whales is thus consistent with both cultural selection
on ID codas to maintain discrete signals for vocal recognition in sympatry,
and social learning between clans leading to a vocal style more similar to
that of other whales with which they are in acoustic contact more frequently.
This highlights a more complex system of transmission in which clan identity
is maintained through selection, while gradual change over time may occur
within and across clans for vocalizations which do not function in social
recognition and thus may create similar vocal styles.

### Future directions

Our results can be expanded in multiple ways in future work. The first, and
the simplest conceptually, would be to conduct the present analysis on a
larger dataset. More codas would improve the quality of the statistical
analyses and ensure that all codas are represented in realistic proportions
for each clan. Moreover, longitudinal datasets might provide direct evidence
to discriminate between the social learning hypothesis and competing ones
(e.g. drift in vocal style). Similarly, confirmations could emerge from large
scale genetic datasets addressing the issues of phylogenetic relatedness (or
lack thereof) in clans that are closer in vocal style distance. Such datasets
do not exist at present, but efforts towards automated and semi-automated
collection techniques are underway (e.g. Project CETI [35]). Second, from a
methodological perspective, we could add spectral information (in terms of
acoustic frequencies) to the temporal information currently used. Although
sperm whale acoustic communication seems mostly based on rhythm, spectral
features of individual clicks may convey additional information. This
possibility could be incorporated into our method by labeling the dICIs
according to the frequency content of the associated click (or by extending
the available “alphabet” for the VLMC). Third, it would be interesting to
investigate in more detail the function of non-ID codas. Indeed, even though
ID codas were only recently formally named for the first time, they have been
the primary focus of sperm whale coda research for decades. As previously
mentioned, non-ID codas are a catch-all category for anything that is not an
ID coda, but that does not mean that all non-ID codas function in the same
way. To start to unveil their function, we need to consider the context
(behavioral, environmental, etc.) in which different non-ID codas are produced
[36]. The pattern we documented may or may not apply to all non-ID codas, but
it is at least strong enough that we detect the relationship with clan spatial
overlap when collectively considering all non-ID codas.

## Methods

### Acoustic data

In social situations, sperm whales acoustically communicate through short
bursts of clicks with recognizable patterns based on rhythm and tempo referred
to as codas. Codas are generally represented as sequences of ICIs, equivalent
to a time series of click onsets.

We analyzed two datasets in the present study. The Dominica dataset contains
8719 annotated codas recorded in the Atlantic Ocean off the island of Dominica
between 2005 and 2019. The codas come from 12 social units grouped into two
vocal clans (EC1 and EC2). The Pacific dataset was collected between 1978 and
2017 at 23 locations in the Pacific Ocean (the recording methods are available
in the supplementary materials of [11]). The codas were divided into  coda
samples according to their recording day and each repertoire was assigned a
single vocal clan inferred in [11]. When considering a clan-level analysis
(Fig. 3) all  coda samples were used to compute the subcoda trees (23555
codas). However, when analysing at a  coda samples level (Fig. 4), we
discarded  coda samples with less than 200 codas with statistical inference in
mind, resulting in a final count of 57  coda samples (17046 codas) for the
Pacific.

### Representation of sperm whale communication as discrete inter-click
intervals

As a preliminary step, we discretized the (continuous) ICI values into bins of
width $\delta t$ seconds. In other words, we represented the continuum of ICI
values by a finite set of discrete ICIs (dICIs) based on the duration of the
ICI. The bin width $\delta t$ controls the temporal resolution of the
representation: a higher value of $\delta t$ implies a coarser representation
with fewer dICIs. We also imposed an upper bound $t_{\text{max}}$: any ICI
value greater than that was truncated to $t_{\text{max}}$. This ensured that
the set of dICIs was finite. Note that although ICIs have units of time
(seconds), dICIs are unitless (they represent time intervals). The resulting
representation of ICIs as dICIs is a discrete random variable defined as

$X_{\delta
t,t_{\text{max}}}=\left\lfloor\frac{\min\left(\text{ICI},t_{\text{max}}\right)}{\delta
t}\right\rfloor,$ (1)

which takes values in the finite set
$\mathcal{X}=\\{0,1,\dots,\lfloor\frac{t_{\text{max}}}{\delta t}\rfloor\\}$.
We represented the sequences of ICIs by sequences of dICIs from that finite
set. Note that any ICI value above $t_{\text{max}}$ is mapped to the dICI
$\lfloor\frac{t_{\text{max}}}{\delta t}\rfloor$ and therefore represents the
end of a coda. We set $t_{\text{max}}=1$ (longer than any ICI) and $\delta
t=0.05$ throughout the analysis (see Supplementary Materials section $3.3.2$
for justification of this choice and section $3.4.3$ for an analysis on the
influence of this parameter).

### Variable length Markov chains

We then modeled these dICI sequences using variable length Markov chains
(VLMCs). VLMCs provide the large memory advantage of higher-order Markov
chains when needed, without the drawback of having too many unnecessary
parameters in the model.

Fitting a VLMC is the process of deciding how much memory is necessary to
model specific sequences. The criterion for making this decision is the
following: longer sequences are discarded if their distribution of transition
probabilities is similar to that of shorter subsequences. This process is
often called context tree estimation and consists of two steps.

The first step is to consider $\mathcal{W}_{D}$ the set of all sequences of
maximum length $D$ (which we set to 10) and to assign the following
probability distribution $q_{w}$ to each sequence:

$q_{w}=P(X|w),$ (2)

that is, the probability of observing a state $x\in\mathcal{X}$ given the
sequence $w$.

The second step is to prune the sequences that do not add information. Take
two sequences $u,w\in\mathcal{W}_{D}$, one being the suffix of the other $w$ =
$\sigma u$. The information gained $H_{w}$ by considering the longer sequence
can be measured with a weighted Kullback-Leibler (KL) divergence $D_{KL}$
[37]. The longer memory sequence $w$ is kept only if the information gain is
greater than some threshold $K$ [38, 39]

$\Delta H_{w}=N(w)D_{KL}(q_{w}||q_{u})>K$ (3)

where $N(w)$ denotes the length of sequence $w$. Sequences that satisfy this
condition are called contexts and sequences that do not are discarded. A VLMC
can be defined as the set of these contexts $w$ and their associated
probability distribution $q_{w}$ (see Supplementary Materials section $3.1$
for details).

A VLMC can be visualized as a tree by representing each context $w$ by a node
and setting the root node as the context of length zero. Contexts that are
subsequences of each other are then part of the same branches, which end with
the longest contexts.

### Quantitative Comparison of VLMCs

If two VLMC models $T_{1}$ and $T_{2}$ are built over the same finite set of
dICIs $\mathcal{X}$, there exists a map $\phi_{1}:\mathcal{W}_{D}\rightarrow
T_{1}$ that maps any sequence of elements of $\mathcal{X}$ into the longest
sequence present in $T_{1}$, and similarly for $T_{2}$. This map also induces
a map between the probability distributions of $T_{1}$ and $T_{2}$. Given two
distributions over the same set $\mathcal{X}$, we can measure how different
they are with the $KL$ divergence. Therefore, it is possible to define a
dissimilarity between $T_{1}$ and $T_{2}$ by considering the average $KL$
divergence over all sequences of $T_{1}$ and their map
$\phi_{1}(T_{2})\subseteq T_{1}$

$\displaystyle d_{KL}(T_{1},T_{2})$ $\displaystyle=\frac{1}{|T_{1}|}\sum_{w\in
T_{1}}D_{KL}\left(q_{w}||p_{\phi_{1}(w)}\right)$ (4)

Refer to the Supplmentary Materials section $3.4$ for a more detailed
explanation.

This results in a dissimilarity measure that captures not just the difference
in emission distribution but also the structural differences of the associated
context trees. When comparing the distribution of distances in Fig. 2A and
Fig. 3A we performed a Kolmogorov–Smirnov test to test if the distances
between social units/ coda samples of the same clan and distances between
social units/ coda samples of different clans had come from the same
distribution. For every pair, we can reject the hypothesis of the distances
coming from the same distribution with $95\%$ confidence.

### Hierachical Clustering of VLMCs

The dendrograms in Fig. 2B and Fig. 3B were obtained by hierarchical
clustering using average linkage on the set of subcoda trees (VLMCs). Since
the distance is not symmetric, for agglomerative clustering we considered the
symmetric distance:

$d_{KL}(T_{1},T_{2})=\max\left\\{d_{KL}(T_{1},T_{2}),d_{KL}(T_{2},T_{1})\right\\}.$
(5)

### Measuring clan overlap

We used the clan spatial overlap values from [11]. Briefly, given two clans A
and B, and the  coda samples associated to them, the amount of geographical
overlap of A in B was measured as the fraction of  coda samples belonging to
clan A that were recorded within 1000 kilometers of at least one repertoire of
clan B.  One thousand kilometers is the approximate annual home range span of
sperm whales in the eastern tropical Pacific [40, 41].

### Statistical Testing

On Fig. 2 and Fig. 3 we compare the distributions of distances between subcoda
trees of  coda samples/social units of the same clan (within) and of different
clans (between). The purpose is to assess whether these distributions
originate from the same underlying population. We employ both the
Kolmogorov–Smirnov test and the T-test. The observed p-values were well below
$0.01$ for all clans. This allows us to confidently reject the hypothesis that
there is no difference between the vocal style between different clans. For
more information check the Supplementary Materials in section $3.4.2$.

To assess the existence of a relationship between clan overlap and vocal style
similarity, we applied an ordinary least squares linear regression model
(OLS). We show the resulting $p$ values of the OLS statistical test at the
bottom left of each plot of Fig. 4 along with the observed $r^{2}$ value.  To
assess whether there is true difference between the two cases, we also
bootstrapped the linear regression calculation to obtain 95% confidence
intervals for the slopes of the fits, resulting in both negative and positive
values in the ID case, but only negative slope values for the non-ID case,
thus confirming our interpretation.

## Acknowledgments

This study was funded by Project CETI via grants from Dalio Philanthropies and
Ocean X; Sea Grape Foundation; Rosamund Zander/Hansjorg Wyss, Chris
Anderson/Jacqueline Novogratz through The Audacious Project: a collaborative
funding initiative housed at TED. TAH was supported by Max Planck Group Leader
funding to Andrea Ravignani of the Max Planck Institute for Psycholinguistics.
The Dominica coda dataset originates from The Dominica Sperm Whale Project
which was supported by a FNU fellowship for the Danish Council for Independent
Research supplemented by a Sapere Aude Research Talent Award, a Carlsberg
Foundation expedition grant, a grant from Focused on Nature, two Explorer
Grants from the National Geographic Society (all to SG), and supplementary
grants from the Arizona Center for Nature Conservation, Quarters For
Conservation, the Dansk Akustisks Selskab, Oticon Foundation, and the Dansk
Tennis Fond. Further funding was provided by Discovery and Equipment grants
from the Natural Sciences and Engineering Research Council of Canada to Hal
Whitehead (Dalhousie University) and a FNU large frame grant and a Villum
Foundation Grant to Peter Madsen (Aarhus University). The publicly accessible
Pacific Ocean sperm whale coda dataset we used in this study emanates from the
Global Coda Dialect Project, a consortium of scientists conducting sperm whale
acoustics research worldwide. Members of the consortium who contributed to the
Pacific Ocean dataset include: Luke Rendell, Mauricío Cantor, Lindy Weilgart,
Masao Amano, Steve M. Dawson, Elisabeth Slooten, Christopher M. Johnson, Iain
Kerr, Roger Payne, Andy Rogan, Ricardo Antunes, Olive Andrews, Elizabeth L.
Ferguson, Cory Ann Hom-Weaver, Thomas F. Norris, Yvonne M. Barkley, Karlina P.
Merkens, Erin M. Oleson, Thomas Doniol-Valcroze, James F. Pilkington, Jonathan
Gordon, Manuel Fernandes, Marta Guerra, Leigh Hickmott and Hal Whitehead. We
are grateful to Scott Baker and Alana Alexander for answering questions about
sperm whale genetics.

## References

  * [1] Rendell, L. & Whitehead, H.  Culture in whales and dolphins.  _Behav. Brain Sci._ 24, 309–324 (2001).
  * [2] Whiten, A., Ayala, F. J., Feldman, M. W. & Laland, K. N.  The extension of biology through culture.  _Proc. Natl. Acad. Sci._ 114, 7775–7781 (2017).
  * [3] Whitehead, H. & Rendell, L.  _The cultural lives of whales and dolphins_ (University of Chicago Press, 2014).
  * [4] Slater, P.  The cultural transmission of bird song.  _Trends Ecol. Evol._ 1, 94–97 (1986).
  * [5] Luncz, L. V., Wittig, R. M. & Boesch, C.  Primate archaeology reveals cultural transmission in wild chimpanzees (pan troglodytes verus).  _Philos. Trans. R. Soc. B_ 370, 20140348 (2015).
  * [6] Alem, S. _et al._ Associative mechanisms allow for social learning and cultural transmission of string pulling in an insect.  _PLoS Biol._ 14, e1002564 (2016).
  * [7] Cavalli-Sforza, L. L. & Feldman, M. W.  _Cultural transmission and evolution: A quantitative approach_.  16 (Princeton University Press, 1981).
  * [8] Barth, F.  Introduction.  In _Ethnic Groups and Boundaries_ (Little Brow, 1969).
  * [9] McElreath, R., Boyd, R. & Richerson, P.  Shared norms and the evolution of ethnic markers.  _Curr. Anthropol._ 44, 122–130 (2003).
  * [10] Boyd, R. & Richerson, P. J.  The evolution of ethnic markers.  _Cult Anthropol_ 2, 65–79 (1987).
  * [11] Hersh, T. A. _et al._ Evidence from sperm whale clans of symbolic marking in non-human cultures.  _Proc. Natl. Acad. Sci._ 119, e2201692119 (2022).
  * [12] Bermant, P. C., Bronstein, M. M., Wood, R. J., Gero, S. & Gruber, D. F.  Deep Machine Learning Techniques for the Detection and Classification of Sperm Whale Bioacoustics.  _Sci. Rep._ 9, 12588 (2019).
  * [13] Cantor, M., Gero, S., Whitehead, H. & Rendell, L.  Sperm whale, the largest toothed creature on earth.  In _Ethology and behavioral ecology odontocetes_ , 261–280 (Springer, 2019).
  * [14] Watkins, W. A. & Schevill, W. E.  Sperm whale codas.  _J. Acoust. Soc. Am._ 62, 1485 (1977).
  * [15] Hersh, T. A., Gero, S., Rendell, L. & Whitehead, H.  Using identity calls to detect structure in acoustic datasets.  _Methods Ecol. Evol._ 12, 1668–1678 (2021).
  * [16] Weilgart, L. & Whitehead, H.  Coda communication by sperm whales (_Physeter_ _macrocephalus_) off the Galápagos Islands.  _Can. J. Zool._ 71, 744–752 (1993).
  * [17] Schulz, T., Whitehead, H., Gero, S. & Rendell, L.  Individual vocal production in a sperm whale (physeter macrocephalus) social unit.  _Mar. Mammal Sci._ 27, 149–166 (2010).
  * [18] Gero, S., Whitehead, H. & Rendell, L.  Individual, unit and vocal clan level identity cues in sperm whale codas.  _R. Soc. Open Sci._ 3, 150372 (2016).
  * [19] Rendell, L. & Whitehead, H.  Spatial and temporal variation in sperm whale coda vocalizations: stable usage and local dialects.  _Anim. Behav._ 70, 191–198 (2005).
  * [20] Rendell, L. E. & Whitehead, H.  Vocal clans in sperm whales (Physeter macrocephalus).  _Proc. Royal Soc. B_ 270, 225–231 (2003).
  * [21] Gero, S., Bøttcher, A., Whitehead, H. & Madsen, P. T.  Socially segregated, sympatric sperm whale clans in the Atlantic Ocean.  _R. Soc. Open Sci._ 3, 160061 (2016).
  * [22] Cantor, M. _et al._ Multilevel animal societies can emerge from cultural transmission.  _Nat. Commun._ 6, 8091 (2015).
  * [23] Backus, R. H. & Schevill, W. E.  Physeter clicks.  _Whales, dolphins, and porpoises_ 510–527 (1966).
  * [24] Vachon, F., Hersh, T., Rendell, L., Gero, S. & Whitehead, H.  Ocean nomads or island specialists? culturally driven habitat partitioning contrasts in scale between geographically isolated sperm whale populations.  _R. Soc. Open Sci._ 9, 211737 (2022).
  * [25] Cohen, E.  The evolution of tag-based cooperation in humans: The case for accent.  _Curr. Anthropol._ 53, 588–616 (2012).
  * [26] Henrich, J. & Muthukrishna, M.  The origins and psychology of human cooperation.  _Annu. Rev. Psychol._ 72, 207–240 (2021).
  * [27] Oliveira, C. _et al._ Sperm whale codas may encode individuality as well as clan identity.  _J. Acoust. Soc. Am._ 139, 2860–2869 (2016).
  * [28] Sun, K. _et al._ Geographic variation in the acoustic traits of greater horseshoe bats: testing the importance of drift and ecological selection in evolutionary processes.  _PLoS One_ 8, e70368 (2013).
  * [29] Rendell, L., Mesnick, S. L., Dalebout, M. L., Burtenshaw, J. & Whitehead, H.  Can genetic differences explain vocal dialect variation in sperm whales, physeter macrocephalus?  _Behav. Genet._ 42, 332–343 (2012).
  * [30] Alexander, A. _et al._ What influences the worldwide genetic structure of sperm whales (physeter macrocephalus)?  _Mol. Ecol._ 25, 2754–2772 (2016).
  * [31] Lyrholm, T., Leimar, O., Johanneson, B. & Gyllensten, U.  Sex–biased dispersal in sperm whales: contrasting mitochondrial and nuclear genetic structure of global populations.  _Proceedings of the Royal Society of London. Series B: Biological Sciences_ 266, 347–354 (1999).
  * [32] Epp, M. V., Fournet, M. E., Silber, G. K. & Davoren, G. K.  Allopatric humpback whales of differing generations share call types between foraging and wintering grounds.  _Sci. Rep._ 11, 16297 (2021).
  * [33] Madsen, P., Wahlberg, M. & Møhl, B.  Male sperm whale (physeter macrocephalus) acoustics in a high-latitude habitat: implications for echolocation and communication.  _Behav. Ecol. Sociobiol._ 53, 31–41 (2002).
  * [34] Deecke, V. B., Ford, J. K. & Spong, P.  Dialect change in resident killer whales: implications for vocal learning and cultural transmission.  _Anim. Behav._ 60, 629–638 (2000).
  * [35] Andreas, J. _et al._ Towards understanding the communication in sperm whales.  _iScience_ 25, 104393 (2022).
  * [36] Frantzis, A. & Alexiadou, P.  Male sperm whale (physeter macrocephalus) coda production and coda-type usage depend on the presence of conspecifics and the behavioural context.  _Can. J. Zool._ 86, 62–75 (2008).
  * [37] Kullback, S. & Leibler, R. A.  On information and sufficiency.  _Ann. Math. Stat._ 22, 79–86 (1951).
  * [38] Mächler, M. & Bühlmann, P.  Variable length markov chains: methodology, computing, and software.  _J. Comput. Graph. Stat._ 13, 435–455 (2004).
  * [39] Galves, A., Galves, C., Garcia, J. E., Garcia, N. L. & Leonardi, F.  Context tree selection and linguistic rhythm retrieval from written texts.  _Ann. Appl. Stat._ 6, 186–209 (2012).
  * [40] Whitehead, H.  Analysis of animal movement using opportunistic individual identifications: application to sperm whales.  _Ecology_ 82, 1417–1432 (2001).
  * [41] Whitehead, H., Coakes, A., Jaquet, N. & Lusseau, S.  Movements of sperm whales in the tropical pacific.  _Marine Ecology Progress Series_ 361, 291–300 (2008).