text:
# Synchronizing to Periodicity: The Transient Information and Synchronization Time of Periodic Sequences

## I Introduction

Imagine you are about to begin observing a sequence of events. You know the sequence is periodic; you even know the particular pattern that will repeat. However, you do not know what phase the sequence is in. How many observations, on average, would you have to make before you know with certainty the sequence’s phase? And, as you obtain this certainty, how uncertain are you about the phase? Will the answers to these questions be the same for all sequences of a given period or are there differences between such sequences? What structural properties of a sequence determine the difficulty of synchronization? Here, we answer these questions.

A natural place to begin is with information theory, since it has long been used to analyze the statistical properties of sequences that arise in a variety of settings, including dynamical systems, time-series analysis, statistical mechanics, signal processing, and cryptography . One of the central quantities in these analyses is the entropy rate $`h_\mu `$, the long-time measure of unpredictability of sequences produced by an information source. Although useful and important for quantifying randomness, $`h_\mu `$ does not capture a sequence’s structural properties: its correlation, memory, or statistical complexity. Fortunately, today there are scores of measures of these latter properties. For example, on the information theoretic side, an oft-used measure of memory is the excess entropy $`𝐄`$ — the time-averaged, “all-point” mutual information between a sequence’s past and future .

For any sequence of period $`P`$, it is well known that the entropy rate $`h_\mu `$ vanishes and the excess entropy $`𝐄=\mathrm{log}_2P`$, since a periodic sequence is asymptotically predictable and since $`\mathrm{log}_2P`$ bits of information are needed to store in which of the $`P`$ possible phases a symbol in the sequence is. Thus, all periodic sequences of the same period have the same entropy rate and excess entropy, and so these quantities are unable to capture structural differences between distinct sequences of the same period. In particular, $`h_\mu `$ and $`𝐄`$ cannot help answer the questions posed above.

We turn instead to a recently introduced measure, the transient information $`𝐓`$ , which captures information-theoretic differences between sequences of a given period. We will also make use of the synchronization time $`\tau `$, defined as the average number of observations needed to synchronize to a periodic information source. We shall see that there are indeed significant differences in the synchronization properties of periodic sequences. Furthermore, while $`𝐓`$ and $`\tau `$ are related for extreme cases — minimum and maximum $`𝐓`$ and $`\tau `$ sequences — there is a wide range of $`𝐓`$ and $`\tau `$ values for periodic sequences of the same period.

In the following section we review information sources, entropy rate, and excess entropy. In Sec. III we define $`𝐓`$ and $`\tau `$ more carefully. After a brief discussion of combinatorics and symmetry types of periodic sequences in Sec. IV, in Sec. V we discuss methods used to calculate $`𝐓`$ and $`\tau `$. In Sec. VI we present the results of exhaustively calculating $`𝐓`$ and $`\tau `$ up to period $`23`$. In Secs. VII and VIII, we investigate these results, developing analytic expressions for the minimum and maximum $`𝐓`$ and $`\tau `$ values of a given period, exploring relationships and bounds between the two synchronization measures. Finally, in Sec. IX we summarize and interpret the results, pointing out several applications to coordination in multiagent systems.

## II Entropy Rate and Excess Entropy

### A Information Sources

We shall be concerned with a one-dimensional infinite sequence of variables:

$$\stackrel{}{S}\mathrm{}S_2S_1S_0S_1\mathrm{}.$$
(1)
Here, the $`S_t`$’s are random variables that range over a finite set $`𝒜`$ of alphabet symbols. In general, $`𝒜=\{0,1,\mathrm{},k1\}`$, although in the following, we will restrict ourselves to binary sequences. We denote a block or word of $`L`$ consecutive variables by $`S^LS_1\mathrm{}S_L`$. We follow the convention that a capital letter refers to a random variable, while a lowercase letter denotes a particular value of that variable. Thus, $`s^L=s_0s_1\mathrm{}s_{L1}`$, denotes a particular symbol block of length $`L`$.

We assume that the underlying information source is described by a shift-invariant measure $`\mu `$ on infinite sequences $`\mathrm{}s_2s_1s_0s_1s_2\mathrm{};s_t𝒜`$ . The measure $`\mu `$ induces a family of distributions, $`\{\mathrm{Pr}(s_{t+1},\mathrm{},s_{t+L}):s_t𝒜\}`$, where $`\mathrm{Pr}(s_t)`$ denotes the probability that at time $`t`$ the random variable $`S_t`$ takes on the particular value $`s_t𝒜`$ and $`\mathrm{Pr}(s_{t+1},\mathrm{},s_{t+L})`$ denotes the joint probability over blocks of $`L`$ consecutive symbols. We assume that the source is stationary; $`\mathrm{Pr}(s_{t+1},\mathrm{},s_{t+L})=\mathrm{Pr}(s_1,\mathrm{},s_L)`$.

We are interested in periodic sequences; a sequence is periodic of period $`P`$ if $`s_i=s_{i+P}`$ for all $`i`$. The prime period of the sequence is the smallest such $`P`$. We can specify a periodic sequence by giving the smallest word — the prime word — that is exactly repeated. The prime word is aperiodic, necessarily. For example, $`\mathrm{}1100110011001100\mathrm{}`$ is period $`8`$ (and period $`16`$ and so on), but has prime word $`1100`$ and prime period $`4`$.

### B Entropy Growth and Entropy Rate

Here, we give a brief review of the information-theoretic description of sequences, concentrating on those that are periodic. For more detail about information-theoretic measures of uncertainty and structure in the context of general one-dimensional random sequences, see, e.g., Refs.  and references therein.

The total Shannon entropy of length-$`L`$ blocks is defined by:

$$H(L)\underset{s^L𝒜^L}{}\mathrm{Pr}(s^L)\mathrm{log}_2\mathrm{Pr}(s^L),$$
(2)
where $`L>0`$. The sum is understood to run over all possible blocks of $`L`$ consecutive symbols. The units of $`H(L)`$ are bits. The entropy $`H(L)`$ measures the average uncertainty in identifying one sequence in the set of length-$`L`$ sequences. Equivalently, $`H(L)`$ tells us how many yes-no questions, on average, are needed to determine the value of $`S^L`$. Another way to state this is that $`H(L)`$ sets a lower bound on the size of the code, measured in bits, needed to encode successive outcomes of the random variable $`S^L`$. For more on this coding interpretation of the Shannon entropy, see, e.g., Ref. .

The general behavior of $`H(L)`$ as a function of $`L`$ for periodic information sources is shown schematically in Fig. 1. Note that we define $`H(0)0`$.

The entropy rate $`h_\mu `$ is the rate of increase with respect to $`L`$ of the total Shannon entropy in the large-$`L`$ limit:

$$h_\mu \underset{L\mathrm{}}{lim}\frac{H(L)}{L},$$
(3)
where $`\mu `$ denotes the measure over infinite sequences that induces the $`L`$-block joint distribution $`\mathrm{Pr}(S^L)`$; the units are bits per symbol. One can also define a finite-$`L`$ approximation to $`h_\mu `$,

$`h_\mu (L)`$ $`=`$ $`H(L)H(L1),`$ (4)
$`=`$ $`H[S_L|S_{L1}S_{L2}\mathrm{}S_0],`$ (5)
where $`H[X|Y]`$ is the entropy of the random variable $`X`$ conditioned on the random variable $`Y`$: $`H[X|Y]_{x,y}\mathrm{Pr}(x,y)\mathrm{log}_2\mathrm{Pr}(\mathrm{x}|\mathrm{y})`$. One can then show  that

$$h_\mu =\underset{L\mathrm{}}{lim}h_\mu (L).$$
(6)
Note that Eq. (4) shows that $`h_\mu (L)`$ may be viewed as the slope of $`H(L)`$. For more on this point of view, see Ref. .

Eq. (6) gives us another interpretation of $`h_\mu `$. The entropy rate quantifies the irreducible randomness or unpredictability of the sequences; $`h_\mu `$ measures the randomness that persists even after the statistics of longer and longer blocks are taken into account. Since all periodic sequences are, ultimately, predictable, the entropy rate for all periodic sequences is $`h_\mu =0`$. For a period-$`P`$ sequence $`h_\mu (P)=0`$ and $`h_\mu (L)0`$, for $`L=1,2,\mathrm{},P1`$. This is illustrated in Fig. 2 for three different period-$`8`$ sequences; when the slope of $`H(L)`$ vanishes, $`h_\mu (L)=0`$.

### C Excess Entropy: Apparent Memory

The entropy rate measures the randomness of sequences. A complementary quantity is the excess entropy $`𝐄`$, which measures the deviations of finite-$`L`$ estimates of $`h_\mu `$ from its asymptotic value:

$$𝐄\underset{L=1}{\overset{\mathrm{}}{}}[h_\mu (L)h_\mu ],$$
(7)
The units of $`𝐄`$ are bits. Using this definition, one can show that the excess entropy is the subextensive part of $`H(L)`$ (see, e.g., ); that is,

$$𝐄=\underset{L\mathrm{}}{lim}[H(L)h_\mu L].$$
(8)
This establishes a geometric interpretation for $`𝐄`$, as shown in Fig. 1; it is the $`y`$-intercept of the line to which $`H(L)`$ asymptotes. That is, when $`𝐄`$ is finite, $`H(L)`$ asymptotes to $`𝐄+h_\mu L`$.

Another way to understand excess entropy is through its expression as a mutual information: the mutual information between the past and future semi-infinite halves of the chain of random variables:

$$𝐄=\underset{L\mathrm{}}{lim}I[S_{L+1},S_{L+2},\mathrm{}S_0;S_1S_2\mathrm{}S_L],$$
(9)
when the limit exists . Eq. (9) says that $`𝐄`$ measures the amount of historical information stored in the present that is communicated to the future.

Our focus here is on periodic sequences, for which it is easy to show from one or another of the above definitions that

$$𝐄=\mathrm{log}_2P.$$
(10)
That is, the excess entropy is the total phase information stored in the periodic source. As noted above, the entropy of a random variable gives the average number of yes-no questions (i.e., bits), needed to determine the outcome of the variable. Since the observer starts out equally ignorant of the initial phase, it follows that $`𝐄`$ is a lower bound on the amount of information (in bits) an observer must extract in order to know in which phase the source is — that is, in order for it to be synchronized to the source.

The entropy growth curves $`H(L)`$ for three different period-$`8`$ sequences are shown in Fig. 2. Note that all curves asymptote to the same line, $`𝐄+h_\mu L`$. Since $`h_\mu =0`$ (periodic sequences) and $`𝐄=\mathrm{log}_2P=\mathrm{log}_28=3`$, the $`H(L)`$ curves asymptote to the horizontal line $`H(L)=3`$ bits, when $`L8`$.

Despite the fact that these three period-$`8`$ sequences have the same $`h_\mu `$ and $`𝐄`$, Fig. 2 shows that their entropy growth curves $`H(L)`$ are not the same; for example, they reach the linear asymptote at different $`L`$’s. Do all period-$`8`$ curves have different $`H(L)`$ behaviors? And do these different $`H(L)`$ behaviors matter, or do $`h_\mu `$ and $`𝐄`$ suffice to characterize periodic sequences?

## III Measures of Synchronization

### A Transient Information

To address these questions, we consider the transient information $`𝐓`$, which was introduced by us in Ref.  and is defined by summing the deviations of $`H(L)`$ from its linear asymptote:

$$𝐓\underset{L=0}{\overset{\mathrm{}}{}}\left[𝐄+h_\mu LH(L)\right].$$
(11)
Note that the units of $`𝐓`$ are bits $`\times `$ symbols and that $`𝐓𝐄`$. The transient information is the shaded area in Fig. 1. We refer to $`𝐓`$ as transient, since, unlike $`h_\mu `$ and $`𝐄`$, it is dominated by nonasymptotic quantities: how $`H(L)`$ behaves before it reaches the linear scaling form $`𝐄+h_\mu L`$. By inspection, one sees that the three period-$`8`$ sequences in Fig. 2 all have different $`𝐓`$ values.

As noted above, for finite-$`𝐄`$ processes $`H(L)`$ scales as $`𝐄+h_\mu L`$ for large $`L`$ . When this scaling form is attained, we say that the observer is synchronized to the source. In other words, when

$$𝐓(L)𝐄+h_\mu LH(L)=\mathrm{\hspace{0.17em}0},$$
(12)
we say the observer is synchronized at length-$`L`$ sequences. The quantity $`𝐓(L)`$ provides a measure of the departure from synchronization. Note that $`𝐓(L)`$ is non-negative. Looking at Eq. (11), we see that the transient information $`𝐓`$ may be written as a sum of the $`𝐓(L)`$’s:

$$𝐓=\underset{L=0}{\overset{\mathrm{}}{}}𝐓(L).$$
(13)
To give the transient information a more precise interpretation, let us consider in more detail the synchronization scenario we have in mind. An observer begins making measurements of a sequence, seeing one symbol at a time. The observer knows the periodic sequence it is about to start seeing, but it doesn’t know the phase. That is, the observer knows the period and the prime word that will be repeated. The task for the observer is to make measurements and determine the sequence’s phase. Exact prediction is possible from this point onwards, though not before. How uncertain is the observer during this synchronization process?

To answer this question, we must introduce some additional notation. Before the observer is synchronized, its knowledge is characterized by a distribution over the $`P`$ possible phases of the periodic sequence. Equivalently, the sequence’s phases may be viewed as the periodic source’s internal states. Let $`\phi `$ denote a particular phase, and let $`\mathrm{\Phi }`$ denote the set of all phases. Clearly, $`|\mathrm{\Phi }|=P`$. Next, let $`\mathrm{Pr}(\phi |s^L)`$ denote the probability, as inferred by the observer, that the sequence is in phase $`\phi `$, given that it has just seen the particular sequence of symbols $`s^L`$. The entropy of the distribution of $`\phi `$ measures the observer’s average uncertainty of the phase $`\mathrm{\Phi }`$. Averaging this uncertainty over the possible length-$`L`$ observations, we obtain the average state-uncertainty:

$$(L)\underset{s^L}{}\mathrm{Pr}(s^L)\underset{\phi \mathrm{\Phi }}{}\mathrm{Pr}(\phi |s^L)\mathrm{log}_2\mathrm{Pr}(\phi |s^L).$$
(14)
The quantity $`(L)`$ can be used as a criterion for synchronization. The observer is synchronized to the sequence when $`(L)=0`$ — that is, when it is completely certain about the phase, or internal state, $`\phi \mathrm{\Phi }`$ of the source generating the sequence. And so, when the condition in Eq. (12) is met, we see that $`(L)=0`$, and the uncertainty associated with the next observation is $`0`$.

However, while the observer is still unsynchronized $`(L)>0`$. The average total uncertainty experienced by the observer during the synchronization process is the total synchronization information $`𝐒`$:

$$𝐒\underset{L=1}{\overset{P}{}}(L).$$
(15)
The synchronization information measures the total uncertainty $`(L)`$ experienced by an observer during synchronization. For the periodic sequences under consideration here, it turns out that

$$𝐒=𝐓.$$
(16)
That is, the transient information $`𝐓`$ is equal to the total synchronization information $`𝐒`$.

Eq. (16) is a special case of a theorem recently proved by us in Ref.  and discussed further in Ref. . Here, we briefly sketch the main argument behind Eq. (16). At $`L=0`$, no measurements have been made and the observer posits that each phase is equally likely. The state-uncertainty is thus $`\mathrm{log}_2P=𝐄`$. After $`L`$ observations have been made, the observer has gained, on average, $`H(L)`$ bits of information about the phase of the process. As a result, the average state-uncertainty $`(L)`$ is now $`𝐄H(L)`$. Plugging this last observation into Eq. (15), Eq. (16) follows from the definition of $`𝐓`$, Eq. (11).

As a result of Eq. (16), the transient information $`𝐓`$ provides a direct measure of how difficult or confusing it is to synchronize to a periodic sequence. If a periodic sequence has a large $`𝐓`$, then on average an observer will be highly uncertain about its phase during the synchronization process. The transient information measures a structural property of a sequence — a property captured neither by the entropy rate nor by the excess entropy. If the observer is in a position where it must take immediate action, it does not have the option of waiting for full synchronization. In this circumstance, the synchronization information $`𝐒`$ provides an information-theoretic average-case measure of the error incurred by the observer during the synchronization process.

### B Synchronization Time

In addition to measuring the total uncertainty experienced during synchronization, we can ask a related question: On average, how many measurements must be made before the observer is certain in which state the source is? We call the number $`\tau `$ of measurements, averaged over the $`P`$ possible starting phases, the synchronization time.

For example, consider the periodic sequence $`(0001)^{\mathrm{}}`$. There are four possible phases in which one might begin to observe this sequence. If the first symbols parsed are $`1000`$, then the observer is synchronized after the first observation (a $`1`$). If the observer initially sees $`0100`$, it is synchronized after two symbols. If the observer sees either $`0010`$ or $`0001`$, it is synchronized after three measurements. Each of these initial measurement sequences is equally likely. Thus, on average, it will take

$$\tau =\frac{1+2+3+3}{4}=\mathrm{\hspace{0.17em}2.25}$$
(17)
measurements before the observer is synchronized to $`(0001)^{\mathrm{}}`$.

Below, we conduct a survey of the transient information $`𝐓`$ and synchronization time $`\tau `$ of periodic sequences. Although there is an overall scaling between them, perhaps somewhat surprisingly, we shall see that $`𝐓`$ and $`\tau `$ capture fundamentally different properties of a sequence. We shall also see that within different sequences of a given period there are wide variations of $`𝐓`$ and $`\tau `$. First, however, we pause to consider some combinatorial properties and symmetry classes of periodic sequences.

## IV Entropic Symmetry Types and Combinatorics of Periodic Sequences

How many periodic sequences of a given prime period are there? Aperiodic length-$`P`$ words that are related by an application of a cyclic permutation group $`C_P`$ give the same periodic sequence. Thus, for our purposes — considering infinitely repeated periodic sequences — two length-$`P`$ words related via the group operation $`C_P`$ are equivalent; they yield identical infinite sequences. For example, the aperiodic words $`001`$, $`010`$, and $`100`$ all yield the same, infinite, period-$`3`$ sequence.

However, we are interested in looking for distinct $`H(L)`$ versus $`L`$ behaviors, and this induces another set of equivalences on the period-$`P`$ sequences. Because $`H[X]`$ depends only on the distribution of $`X`$, and not on the values $`X`$ assumes, the entropy of a random variable is unchanged under a one-to-one mapping of alphabet symbols . For the binary cases we are interested in here, this means that the mapping $`01`$ leaves $`H(L)`$ unchanged; for our purposes, the sequence $`(011)^{\mathrm{}}`$ is identical to $`(100)^{\mathrm{}}`$. In terms of group action, swapping $`1`$ and $`0`$ is the action of the symmetric group $`S_1`$. So, any two sequences that are based on binary aperiodic length-$`P`$ words related to each other by some combination of $`S_1`$ and $`C_P`$ will have identical $`H(L)`$ versus $`L`$ behavior.

The number $`L_2`$ of aperiodic binary words inequivalent under $`S_1\times C_P`$ is given by:

$$L_2(P)=\frac{1}{P}\underset{d|P,d\mathrm{odd}}{}\mu (d)2^{P/d}.$$
(18)
The sum runs over all odd positive divisors $`d`$ of $`n`$, and $`\mu (m)`$ is the Möbius function: $`\mu (m)=0`$, if $`m`$ is the product of nondistinct primes; $`+1`$, if $`m`$ is the product of an even number of distinct primes; and $`1`$, otherwise. This result was first obtained by Fine  in 1958 and simplified a few years later by Gilbert and Riordan . These words are also related to a version of the famous necklace problem from combinatorics: the words inequivalent under $`S_1\times C_P`$ are exactly those $`2`$-color necklace sequences with prime period $`P`$ where interchanging bead color is allowed, but turning the necklace over is not.

These aperiodic words are also related to the so-called Lyndon words. A Lyndon word is aperiodic and the lexicographically least among its rotations. An unlabeled Lyndon word is aperiodic and lexicographically least among its rotations and relabelings. Eq. (18), then, also counts the number of binary unlabeled Lyndon words. For more discussion, see Ref.  and sequence #A000048 of Ref. . Titsworth  has pointed out that Eq. (18) also gives the number of distinct finite-state machines needed to produce all periodic binary sequences of prime period $`P`$.

## V Methods

We calculated the transient information $`𝐓`$ and synchronization time $`\tau `$ for all distinct periodic sequences (unlabeled Lyndon words) up to and including period $`P=23`$. To enumerate all of these words of a given period, we used the efficient algorithms available at Ref. .

To calculate $`𝐓`$ and $`\tau `$ for a given length-$`P`$ word, we begin by determining the frequency of occurrence of all its subwords. This is done by parsing the word and its $`P1`$ cyclic permutations into a tree, whose paths from the root to any node are the subwords and each of whose nodes contain the number of subwords found that lead to it from the root.

An example is shown in Fig. 3. Consider the sequence whose prime word is the length-$`5`$ word $`00011`$. We start at the tree root, indicated by the double circle at the top, and follow the leaves labeled with the appropriate symbol. Each time we cross a node we increment the count there by one. We repeat this procedure for all $`5`$ cyclic permutations of $`00011`$.

Once the parse tree is built, $`𝐓`$ can be easily and exactly calculated. First, the node counts are turned into probabilities by normalizing — dividing each count by the period $`P`$. Reading across the tree at level $`\mathrm{}`$ gives the probability of subwords of length $`\mathrm{}`$. In the $`P=5`$ example considered here, $`\mathrm{Pr}(00)=2/5`$, $`\mathrm{Pr}(01)=1/5`$, $`\mathrm{Pr}(10)=1/5`$, and $`\mathrm{Pr}(11)=1/5`$. From these probabilities, the block entropies $`H(L)`$, and, in turn, $`𝐓`$, follow directly by using Eq. (11) and noting that $`𝐄=\mathrm{log}_2P`$ and $`h_\mu =0`$.

Calculating $`\tau `$ is only a bit more involved. After building the parse tree, we reparse each cyclic permutation of the word. As we reparse and proceed down the tree, we monitor the node counts. For each cyclic permutation of the prime word, we follow the corresponding path from the root. When we come to the first node that has a count of $`1`$, we are synchronized. That is, for the $`i^{\mathrm{th}}`$ cyclic permutation of the word, the level $`\mathrm{}`$ at which we first encounter a node count of $`1`$ is the synchronization time $`\tau _i`$ for that permutation. The average synchronization time $`\tau `$ is then simply:

$$\tau =\frac{1}{P}\underset{i=0}{\overset{P1}{}}\tau _i.$$
(19)
For the example in Fig. 3, we have

$$\tau =\frac{1}{5}(3+3+2+2+2)=\mathrm{\hspace{0.17em}2.4}.$$
(20)
As for $`𝐓`$, the above method yields an exact value for $`\tau `$.

For example, in Table I we show the results of calculating the transient information $`𝐓`$ and the synchronization time $`\tau `$ for all five distinct period-$`6`$ sequences. (The reader may find it helpful to verify these results.)

## VI Empirical Results

We empirically investigated the behavior of $`𝐓`$ and $`\tau `$ by first exhaustively enumerating all distinct periodic sequences up to and including period $`P=23`$ and then exactly calculating these two quantities for each using the methods of the previous section. The results are summarized in Figs. 4, 5, 6, 7, and 8. In Table II we show, for periods $`2`$ through $`23`$, the number of distinct periodic sequences, the number of distinct $`𝐓`$ and $`\tau `$ values, and the mean, minimum, and maximum $`𝐓`$ and $`\tau `$ values.

Based on these results, one can make a host of observations. First, note that $`𝐓`$ and $`\tau `$ are not the same for all sequences of a given period. This can be seen in our period-$`6`$ results of Table I, as well as in Figs. 4, 5, and 6. Thus, within a given period, there are many different synchronization behaviors. As noted before, these differences are not accounted for by the entropy rate $`h_\mu `$ and the excess entropy $`𝐄`$, since $`𝐄`$ and $`h_\mu `$ are the same for all sequences with the same period.

Second, there are words with the same period that have identical $`𝐓`$ or identical $`\tau `$ values. This can be seen in Fig. 6, in which we have plotted the count data shown in Table II. The number of distinct $`𝐓`$ and $`\tau `$ values clearly grows less quickly than the total number of distinct periodic sequences. Note also that the number of distinct $`𝐓`$ and $`\tau `$ values grow at different rates. This provides direct evidence that the transient information and the synchronization time measure different qualities. For example, in Table I, note that two sequences have the same $`\tau `$ but different $`𝐓`$’s. The converse also occurs, but much less frequently. There are sequences with the same $`𝐓`$ but different $`\tau `$ values, but this does not occur until $`P=12`$. As can be seen from both Table II and Fig. 6, $`\tau `$ tends to be substantially more degenerate than $`𝐓`$; $`\tau `$ is somehow a coarser measure of a sequence’s synchronization properties.

Third, note that for a given period there is a considerable range of transient information and synchronization time values. This can be seen in Figs. 4 and 5, where the minimum and maximum $`𝐓`$ and $`\tau `$ values are shown as dashed lines. This suggests that there are significant differences in synchronization behaviors among different sequences with the same period. We will return to the question of minimum and maximum $`𝐓`$ and $`\tau `$ sequences in some detail in Sec. VII.

Another way to view the range of $`𝐓`$ values is found in Fig. 7, in which we plot the distribution of $`𝐓`$ values for period-$`16`$ and period-$`23`$ sequences. Note the asymmetry; most $`𝐓`$ values are closer to the minimum $`𝐓`$ than the maximum $`𝐓`$. Similar observations can be made about the distribution of $`\tau `$ values shown in Fig. 8.

Finally, note from Fig. 6 and Table II that the number of distinct $`\tau `$ values is not strictly monotonic with increasing periodicity. Curiously, the number of distinct $`\tau `$ values decreases as the period goes from $`11`$ to $`12`$ and it remains constant in going from $`P=5`$ to $`P=6`$, while it increases for all other $`P`$ increases.

## VII Minimum, Maximum, and Average $`𝐓`$ and $`\tau `$

Here we develop analytical expressions for the extreme behaviors of the transient information and the synchronization time, and we determine how these extreme values grow asymptotically with period. This analysis allows us to derive a number of important conclusions about which complementary structural features these quantities capture.

First, some notational preliminaries. For a given period, we denote by $`𝐓`$ the average transient information, averaged over all distinct prime words. Similarly, $`𝐓_{\mathrm{min}}`$ and $`𝐓_{\mathrm{max}}`$ denote the minimum and maximum $`𝐓`$ values at a given period, respectively. We use similar notation for the average, maximum, and minimum $`\tau `$ values.

### A Maximum-$`𝐓`$ Sequence

A sequence’s transient information $`𝐓`$ is large if $`H(L)`$ approaches its asymptotic value of $`𝐄=\mathrm{log}_2P`$ slowly. This can be deduced graphically from Figs. 1 and 2. The $`H(L)`$ curve that grows most slowly is that in which the distribution over subwords is maximally nonuniform, since the entropy of a random variable decreases as its distribution departs from uniformity. For a given period $`P`$, the sequence with the maximum value of $`𝐓`$ is one consisting of $`P1`$ $`0`$’s followed by an isolated $`1`$, since this sequence is the one whose distribution over subwords is as nonuniform as possible. This behavior is seen in one of the period-$`8`$ sequences shown in Fig. 2.

A direct calculation for the maximal-$`𝐓`$ sequence yields:

$$𝐓_{\mathrm{max}}=\frac{1}{P}\underset{n=2}{\overset{P}{}}n\mathrm{log}_2n.$$
(21)
To develop a functional form for $`𝐓_{\mathrm{max}}`$ we approximate the sum by an integral. After some work, one obtains,

$`𝐓_{\mathrm{max}}`$ $``$ $`{\displaystyle \frac{1}{\mathrm{ln}(16)P}}[\mathrm{\hspace{0.17em}2}PP^2+4\mathrm{ln}(2)`$ (23)
$`+P^2\mathrm{ln}(P)+(1+P)^2\mathrm{ln}(1+P)].`$
For large $`P`$, this scales as

$$𝐓_{\mathrm{max}}\frac{1}{2}P\mathrm{log}_2P.$$
(24)
The values obtained from Eq. (21) agree with the exact numerical results shown in Table II. In Fig. 9 we plot the approximation of Eq. (23) and compare them with our exact numerical results. As expected, the approximation is quite good and improves at larger $`P`$.

The synchronization time $`\tau `$ for the maximum-$`𝐓`$ word can be calculated directly by noticing that one is synchronized as soon as one sees a $`1`$, or after $`P1`$ measurements, whichever comes first. One obtains, for large $`P`$:

$$\tau _{\mathrm{max}\mathrm{T}}\frac{P1}{2},$$
(25)
### B Minimum-$`𝐓`$ Sequences

The minimum-$`𝐓`$ word is particularly easy to analyze when the period is a power of $`2`$. We begin with this special case and use it to derive a simple form for $`𝐓_{\mathrm{min}}`$ as a function of the period.

The sequences with the minimum transient information $`𝐓_{\mathrm{min}}`$ correspond to those whose $`H(L)`$ curves rise most quickly to $`𝐄`$. This is achieved by a sequence whose distribution over subwords, at each subword length, is most nearly uniform and so gives high entropy: the measurements are most informative about the phase.

When the period $`P=2^M`$, where $`M`$ is an integer, the distribution over subwords for the $`𝐓_{\mathrm{min}}`$ sequence is exactly uniform. Words with this property are known as de Bruijn sequences. A binary de Bruijn sequence of order $`k`$ is a binary circular string containing every binary substring of length $`k`$ exactly once. For example, the lexicographically smallest order-$`3`$ binary de Bruijn sequence is $`00010111`$. Note that this was one of the period-$`8`$ sequences whose $`H(L)`$ curve was plotted in Fig. 2. In that figure, the rapid convergence of $`H(L)`$ to $`\mathrm{log}_28=3`$ is clearly seen.

Because every subword appears with equal probability, $`H(L)=L`$, until $`L=\mathrm{log}_2P`$. That is, $`H(L)`$ converges linearly to the excess entropy $`𝐄=\mathrm{log}_2P`$. In other words, the source appears to be a fair coin until synchrony is achieved. At that time, exact predictability becomes possible. This linear convergence can be seen in Fig. 2. The transient information is thus given by the area between $`H(L)`$ and $`\mathrm{log}_2P`$;

$$𝐓_{\mathrm{min}}=\underset{n=1}{\overset{\mathrm{log}_2P}{}}n.$$
(26)
Evaluating the sum, one has:

$$𝐓_{\mathrm{min}}\frac{1}{2}\left(\mathrm{log}_2^2P+\mathrm{log}_2P\right).$$
(27)
Equivalently, since $`𝐄=\mathrm{log}_2P`$, we may write this as:

$$𝐓_{\mathrm{min}}\frac{1}{2}𝐄(𝐄+1).$$
(28)
This result is exact for all $`P`$ that are a power of $`2`$ and serves as an excellent lower bound for $`P`$’s that are not.

For periods that are not a power of $`2`$, the minimum-$`𝐓`$ words are those for which the distribution over subwords is as uniform as possible. For example, for $`P=10`$ there are two prime words with minimum $`𝐓`$: $`0000101111`$ and $`0001011101`$. Each has $`𝐓_{\mathrm{min}}`$ of $`7.39483`$. Note that for each word, the distribution over subwords of length $`1`$ is uniform, while the distribution over words of length $`2`$ is as uniform as can be, given that there are $`10`$ occurrences of subwords of length $`2`$; for each, two length-$`2`$ subwords occur with a frequency of $`3/10`$ and two occur with a frequency of $`2/10`$.

We have obtained an analytic expression for $`𝐓_{\mathrm{min}}`$ for sequences of general period $`P`$. The main idea, as stated above, is to distribute the frequencies of the subwords as uniformly as possible. How uniform this distribution is depends on how $`2^L`$ (the number of subwords of length-$`L`$) divides into the period $`P`$. Following this line of reasoning, we obtain the following results. Let

$$n_p(L)\frac{P}{2^L}$$
(29)
and

$`N_{\mathrm{odd}}(L)`$ $``$ $`P\mathrm{mod}\mathrm{\hspace{0.33em}2}^L,`$ (30)
$`N_{\mathrm{even}}(L)`$ $``$ $`\mathrm{\hspace{0.17em}2}^LN_{\mathrm{odd}}(L).`$ (31)
Here, $`x`$ denotes the floor of $`x`$ — the largest integer smaller than $`x`$. Similarly, $`x`$ is the ceiling of $`x`$ — the smallest integer larger than $`x`$.

The $`H(L)`$ curve converges to $`𝐄=\mathrm{log}_2P`$ by length $`L^{}`$, where

$$L^{}\frac{\mathrm{log}_2P}{2}+\mathrm{\hspace{0.17em}1}.$$
(32)
Then, we find that the transient information is given by:

$$𝐓_{\mathrm{min}}=(L^{}+1)\mathrm{log}_2P\varphi ,$$
(33)
where

$`\varphi `$ $`=`$ $`{\displaystyle \underset{n=1}{\overset{L^{}}{}}}[N_{\mathrm{odd}}{\displaystyle \frac{n_p(L)+1}{n}}\mathrm{log}_2\left({\displaystyle \frac{n_p(L)+1}{n}}\right)`$ (35)
$`N_{\mathrm{even}}(L){\displaystyle \frac{n_p(L)}{n}}\mathrm{log}_2\left({\displaystyle \frac{n_p(L)}{n}}\right)].`$
Values obtained using Eq. (33) agree with the exact results of Table II.

### C Average $`𝐓`$

In Fig. 9 we have also plotted $`𝐓`$, the average value of the transient information, as a function of the period $`P`$. These average values were also given in Table II. The average values appear to be well approximated by

$$𝐓=\frac{1}{2}\mathrm{log}_2^2P+\mathrm{log}_2P.$$
(36)
This is an empirical fit. Note that $`𝐓`$ and $`𝐓_{\mathrm{min}}`$ of Eq. (27) are the same to leading order in $`P`$. This is not surprising, given the asymmetry in the distribution of $`𝐓`$ values evident in Fig. 7.

### D Minimum-$`\tau `$ Sequences

For a given period $`P`$, we found that the sequences with the minimum transient information $`𝐓_{\mathrm{min}}`$ are the same as the sequences with the minimum synchronization time $`\tau _{\mathrm{min}}`$. As noted above, these sequences are those for which the distribution of subwords is most nearly uniform at each subword length. Using this observation, it is possible to derive an analytic expression for $`\tau _{\mathrm{min}}`$ among the sequences of period $`P`$.

As discussed above when considering the minimum-$`𝐓`$ word, if $`P=2^M`$, where $`M`$ is an integer, then the minimum-$`\tau `$ word is such that all subwords appear with equiprobability. In particular, each subword of length $`\mathrm{log}_2P`$ occurs exactly once. Thus, regardless of the phase in which one begins observing such a sequence, there is no ambiguity about the phase of the sequence after making $`\mathrm{log}_2P`$ observations. For observations shorter than $`\mathrm{log}_2P`$, there will always be some uncertainty about the phase of the process. Thus, the synchronization time is:

$$\tau _{\mathrm{min}}=\mathrm{log}_2P=𝐄.$$
(37)
This result is exact when $`P=2^M`$ and is an excellent approximation for other periods.

As mentioned above, $`𝐄`$ is the total phase information stored in the periodic source; it is simply the Shannon entropy of the $`P`$ possible phases. Recall that the entropy of a random variable sets a lower bound on the number of yes-no questions needed, on average, determine the value of that variable. The synchronization time $`\tau `$ is equivalent to this average number of yes-no questions — measuring a binary symbol entails asking a yes-no question of the source. Eq. (37) thus shows that the periodic word with the minimum $`\tau `$ saturates the lower bound set by the entropy.

As was the case for $`𝐓_{\mathrm{min}}`$, one can derive an expression for $`\tau _{\mathrm{min}}`$ for periods that are not a power of $`2`$. As with the minimum-$`𝐓`$ word, in the minimum-$`\tau `$ word the distribution over the subwords is as uniform as possible. In the case where $`P=2^M+1`$, $`P2`$ phases will synchronize in $`M`$ observations. The remaining two phases, though, require an additional observation to synchronize; an additional symbol must be seen to distinguish between these two phases. This was the case, for example, for the period-$`5`$ case considered in Fig. 3. Here, $`P=5=2^2+1`$ and $`M=2`$. Three of the phases synchronize after two observations, while two phases synchronize after three observations.

Generalizing this observation to $`P=2^M+N`$, we obtain the following result:

$$\tau _{\mathrm{min}}=\frac{1}{P}\left[\mathrm{\hspace{0.17em}2}N(M+1)+(P2N)M\right],$$
(38)
where

$$M=\mathrm{log}_2P$$
(39)
and

$$N=P\mathrm{mod}\mathrm{\hspace{0.33em}2}^M.$$
(40)
Eq. (38) can also be written as \[17, seq. A061717\]:

$$\tau _{\mathrm{min}}=\frac{1}{P}\mathrm{log}_2P^P.$$
(41)
The minimum-$`\tau `$ values given by Eq. (38) agree with the exact numerical results shown in Table II. For large $`P`$, Eq. (41) scales as $`\mathrm{log}_2P`$, in agreement with Eq. (37).

### E Maximum-$`\tau `$ Sequence

Recall that the maximum-$`𝐓`$ sequence consisted of $`P1`$ $`0`$’s followed by one $`1`$. For example, the $`𝐓_{\mathrm{max}}`$ sequence is $`000000001`$ for $`P=9`$. However, this is not the maximum-$`\tau `$ sequence. The sequence $`000000001`$ has an $`H(L)`$ that grows very slowly, leading to its large $`𝐓`$. However, once one sees a $`1`$, one is synchronized. Thus, it is possible for an observer to get lucky, see a $`1`$ after one or two observations and be synchronized quickly. As a result, the expected synchronization time for this sequence is relatively low, only $`\tau =4.88889`$.

In contrast, the sequence with the largest synchronization time for period $`9`$ is $`000010001`$ and has $`\tau =6.2222`$. This sequence has the maximum $`\tau `$ due the presence of an additional $`1`$ which prevents an observer from synchronizing after a single observation; this leads to a larger $`\tau `$.

The maximum-$`\tau `$ word for periods $`4`$-$`16`$ are given in Table IV. Note that a maximum-$`\tau `$ word need not be unique, although we find that it is unique for all periods examined, except for $`P=6`$.

For $`P`$ odd, we noticed the maximum-$`\tau `$ word takes on a particularly simple form: two $`1`$’s separated by $`(P3)/2`$ zeros. This allows us to determine a simple expression for $`\tau _{\mathrm{max}}`$ in this case. We find:

$$\tau _{\mathrm{max}}=\frac{3}{4}P\frac{1}{2}\frac{1}{4P},P\mathrm{odd}.$$
(42)
If the period is even, it is also possible to write down an expression for $`\tau _{\mathrm{max}}`$. If $`P`$ is divisible by $`4`$, then

$$\tau _{\mathrm{max}}=\frac{3}{4}P\frac{1}{2}\frac{1}{P},\mathrm{P}\mathrm{divisible}\mathrm{by}\mathrm{\hspace{0.33em}4}.$$
(43)
However, if $`P`$ is divisible by $`2`$, but not by $`4`$, then:

$$\tau _{\mathrm{max}}=\frac{3}{4}P\frac{1}{2}\frac{4}{P},\mathrm{P}\mathrm{divisible}\mathrm{by}\mathrm{\hspace{0.33em}2}\mathrm{and}\mathrm{not}\mathrm{\hspace{0.33em}4}.$$
(44)
Note that, in all cases, to leading order in $`P`$, $`\tau _{\mathrm{max}}`$ grows linearly with $`P`$:

$$\tau _{\mathrm{max}}\frac{3}{4}P.$$
(45)
Also, in all cases the preceding results agree with the exact values obtained by enumeration and shown in Tables II and IV. Eqs. (42) through (44) were obtained by noting various regularities in the enumeration data and not via a first-principles calculation of the subword statistics.

It is also possible to calculate the transient information $`𝐓`$ for the word that maximizes $`\tau `$ for the case in which $`P`$ is odd. Recall that the $`\tau _{\mathrm{max}}`$ word in this case consisted of two $`1`$’s separated by $`(P3)/2`$ zeros. A brute force, direct counting approach yields, for large $`P`$:

$$𝐓_{\mathrm{max}\tau }\frac{1}{4}P𝐄+\frac{P}{2}.$$
(46)
### F Average Synchronization Time $`\tau `$

Figure 10 also shows $`\tau `$, the average synchronization time at a given period, as a function of the period. The dashed line in this figure is an empirical fit:

$$\tau \frac{5}{4}\mathrm{log}_2P.$$
(47)
As was the case with the transient information, the average and minimum synchronization times appear to grow asymptotically at the same rate.

## VIII Relationships between $`\tau `$ and $`𝐓`$

Throughout the foregoing we have argued that there are important structural differences between distinct periodic sequences at a given period. Moreover, the structural properties captured $`𝐓`$ and $`\tau `$, though both related to synchronization, can be different. Perhaps the differences are not surprising. Based on their definitions these quantities have different interpretations: $`𝐓`$ measures the total uncertainty experienced while synchronizing; $`\tau `$ measures the expected number of observations needed in order to synchronize. To clarify the differences and similarities, in this section we analyze more directly the relationship between $`𝐓`$ and $`\tau `$. We shall see that, while there are relationships between $`𝐓`$ and $`\tau `$ for the extremal synchronization behaviors, there is a fairly wide range of $`𝐓`$ and $`\tau `$ combinations possible among different words of the same period.

### A Extreme Synchronizations

We start by summarizing the behaviors of the minimum and maximum values of the transient information $`𝐓`$ and the synchronization time $`\tau `$ to leading order in the period $`P`$ in Table IV. Note the enormous range in $`𝐓`$ and $`\tau `$ values. For example, if $`P=256`$, $`𝐓_{\mathrm{min}}32`$, while $`𝐓_{\mathrm{max}}1024`$. Similarly, for $`P=256`$, $`\tau _{\mathrm{min}}8`$ while $`\tau _{\mathrm{max}}192`$.

Note that for both the minimum and maximum cases, $`𝐓`$ and $`\tau `$ are related to each other by:

$$𝐓=a\tau 𝐄,$$
(48)
where $`a`$ is a constant that does not depend on the period $`P`$. For the minimum-($`𝐓`$, $`\tau `$) case $`a=1/2`$ and for the maximum case $`a=2/3`$. Recall, however, that the maximum-$`𝐓`$ word is not the same as the maximum-$`\tau `$ word. If one uses $`𝐓_{\mathrm{max}}`$ and $`\tau _{\mathrm{max}\mathrm{T}}`$ from Eq. (25) in Eq. (48), one finds $`a=1`$. And, if one uses $`𝐓_{\mathrm{max}\tau }`$ and $`\tau _{\mathrm{max}}`$, one find $`a=1/3`$.

In all cases, note that the ratio of $`𝐓`$ to $`𝐄`$ gives a quantity proportional to $`\tau `$. This ratio may thus be viewed as setting a characteristic time for synchronization.

### B Nonextreme Synchronizations

It turns out, however, that these simple relations mask a wide diversity of synchronization behaviors. Fig. 11, a scatter plot of $`𝐓`$ and $`\tau `$ for all period-$`18`$ sequences, shows that the relationship between $`𝐓`$ and $`\tau `$ for individual sequences is quite a bit more complicated. For example, recall from the previous section that the maximum-$`𝐓`$ sequence does not correspond with the maximum-$`\tau `$ sequence. In the Fig. 11, the maximum-$`𝐓`$ value is shown by a solid triangle and the maximum-$`\tau `$ value by a solid square. The minimum-$`𝐓`$ and -$`\tau `$ sequences are identical, however. This corresponds to the single point in the figure’s lower left corner.

The wide range of points in the scatter plot of Fig. 11 makes it clear that $`𝐓`$ and $`\tau `$ do indeed measure different properties: $`𝐓`$ and $`\tau `$ are not simply rescaled versions of each other. Any simple functional relationship is precluded by the diffuse scatter of points. Said another way, if one lists sequences of a given period in order of increasing $`𝐓`$, this order will not be the same as listing the sequences in order of increasing $`\tau `$.

Although there is considerable spread evident in Fig. 11, there are bounds limiting the range of $`𝐓`$ values at each $`\tau `$.

In fact, one can develop an approximate form for the upper bound in Fig. 11 as follows. Given an arbitrary $`\tau `$ value and the period $`P`$, we are interested in determining the largest possible $`𝐓`$. Call this maximum value $`𝐓_{\mathrm{upper}}`$. Recall that the synchronization time $`\tau _{\mathrm{max}\mathrm{T}}`$ for the maximum $`𝐓`$ word scales as $`P/2`$ for large $`P`$, as shown in Eq. (25). This lets us write

$$𝐓_{\mathrm{max}}=\frac{1}{2}P𝐄=𝐄\tau _{\mathrm{max}\mathrm{T}}.$$
(49)
To maximize $`𝐓`$ for a given $`\tau `$, assume that the given $`\tau `$ is that which maximizes $`𝐓`$. Then, using the above equation, we see that $`𝐓_{\mathrm{upper}}𝐄\tau `$. That is, the slope of the linear upper bound is $`𝐄`$. To get the full equation of the line, we require that it go through the minimum-$`(\tau ,𝐓)`$ point on the lower left hand corner of Fig. 11. Using Eqs. (27) and (37) for the values of $`𝐓_{\mathrm{min}}`$ and $`\tau _{\mathrm{min}}`$, respectively, we then obtain

$$𝐓_{\mathrm{upper}}𝐄[\tau \frac{1}{2}(𝐄1)].$$
(50)
This upper bound is plotted in Fig. 11, with $`𝐄=\mathrm{log}_2184.1699\mathrm{}`$. This upper bound is only approximate because the minimum-($`\tau ,𝐓`$) values used in its calculation are the asymptotic values for large $`P`$. The bound is also approximate because the relationship in Eq. (49), which is true for the maximum-$`𝐓`$ sequence (the solid triangle in the figure), is assumed to hold for all sequences. Despite these approximations, the linear upper bound appears to fit the data quite well, as shown in Fig. 11.

A similar line of reasoning allows us to form a lower bound $`𝐓_{\mathrm{lower}}`$ for the smallest possible $`𝐓`$, given a value of $`\tau `$ and the period $`P`$. From Eqs. (28) and (37), for large $`P`$ we know that $`𝐓_{\mathrm{min}}\frac{1}{2}E^2`$ and $`\tau _{\mathrm{min}}𝐄`$. This gives us

$$𝐓_{\mathrm{min}}=\frac{1}{2}𝐄\tau _{\mathrm{min}}.$$
(51)
To minimize $`𝐓`$, we assume that the given $`\tau `$ is the minimum $`\tau `$. This tells us that the slope of a linear lower bound is $`\frac{1}{2}𝐄`$. Requiring the line to go through the minimum $`\tau ,𝐓`$ point yields

$$𝐓_{\mathrm{lower}}=\frac{1}{2}\tau +\frac{1}{2}E^2.$$
(52)
This is only an approximate bound, for the same reasons that $`𝐓_{\mathrm{upper}}`$ is approximate. Eq. (52) is plotted in Fig. 11. It is indeed a lower bound, but the bound is not very tight.

## IX Discussion and Conclusion

We began by introducing two measures of how difficult it is to synchronize to a sequence: the transient information $`𝐓`$, an information-theoretic measure of the total uncertainty experienced by an observer during the synchronization process; and the synchronization time $`\tau `$, the number of symbols an observer expects to measure before it is synchronized. We exactly calculated $`𝐓`$ and $`\tau `$ for all synchronization-distinct periodic sequences up to and including period $`23`$. We also derived a handful of analytic expressions and approximations for the minimum, maximum, and average $`𝐓`$ and $`\tau `$ as a function of period.

Our results show that there are many structural differences between periodic sequences, even within sequences of the same period. These differences are simply not captured by commonly used information theoretic measures, such as the entropy rate and the excess entropy. Are all periodic sequences of a given period the same from an information-theoretic standpoint? The answer we gave here is “no”; the recently introduced transient information, in fact, captures the information-theoretic differences between sequences of a given period. Are there structural differences between different periodic sequences of the same period? We showed that the answer is “yes” and argued that the differences are significant. Are there distinct classes of periodic sequence? Again, we provided a positive answer, partly by contrasting properties captured by the transient information with a sequence’s group theoretic properties and its synchronization time. The latter measures the average number of observations needed to synchronize to the sequence and, for a given sequence at a given period, this number was neither the same nor simply proportional to the transient information. Nonetheless, at a coarse level, the leading-order approximations we developed provide simple and direct links between the three different concepts of phase memory $`𝐄`$, synchronization time $`\tau `$, and the total uncertainty experienced during synchronization $`𝐓`$.

There are a number of areas in which our results may find application. For one, recognizing the phases of long periodic sequences of the type investigated here is a key technology for current and future large-scale satellite-to-satellite communication systems. These multiagent systems require extremely accurate and robust satellite-to-satellite synchronization  generally for coordination in signal processing and navigation and specifically for estimating inter-satellite signal delays and distances. Synchronization between two satellites is effected by one transmitting a very long ($`P1,000`$) and known binary periodic sequence. The receiver then infers the phase, using a hierarchical correlation algorithm adapted to account for noise corruption of individual symbols during transmission. It turns out that the long periodic acquisition sequences are aperiodic sequences formed from relatively “prime” short aperiodic sequences. In fact, the synchronization properties of the component sequences and the composite acquisition sequence determine bounds on the computational effort and noise robustness that can be achieved by the receiver’s detection system. We conjecture that the transient information of the acquisition sequence is a key parameter determining these properties.

More generally, these results bear on any situation in which an intelligent agent needs to learn the phase of a periodic component in its environment’s behavior; cf. Ref. . This arises in multiagent systems if an agent needs to know where it is in a physical environment that varies periodically in space or time, if it needs to adjust its behavior in response to the repetitive behavior of other agents, or if a collective decision requires coordinated information processing.

Finally, we mention several open questions and directions for future work. First, do these results hold if the synchronization process is noisy and bits flip occasionally? They should extend relatively directly to a class of “noisy-periodic” processes in which one or several symbols in a periodic sequence are random. However, can these results be extended to the full class of finite-memory sources? For a further discussion of the synchronization scenario in a setting not restricted to periodic sequences see Refs.  and .

Second, one may view those sequences at a given period with the same $`𝐓`$ as forming an equivalence class. Recall that distinct periodic sequences were defined by the group $`S_k\times C_P`$. These are the equivalence classes of zero entropy rate, finite excess entropy sequences. But what new algebra or symmetry group of periodic sequences characterizes those sequences that are equally hard to synchronize to, as measured by $`𝐓`$ or $`\tau `$? If we can characterize identical $`𝐓`$ or $`\tau `$ sequences in terms of a symmetry group or algebra, it should be possible to obtain an analytic expression for the number of distinct $`𝐓`$ or $`\tau `$ values at a given period.

Third, as noted above, Titsworth  pointed out that Eq. (18) gives the number of distinct finite-state machines needed to generate all sequences of a given prime period. The picture is that starting in a different state of such a machine gives the cyclic permutations, while exchanging the output symbols gives the permutation $`01`$. Titsworth does not comment on the structure of the synchronizing states of these machines. To account for synchronization one wants each finite-state machine to have a unique start state that corresponds to the condition of an observer not knowing in which phase a periodic sequence starts. It turns out that $`ϵ`$-machines  capture this synchronizing structure in their transient states, and these in turn determine $`𝐓`$. Moreover, this is true for both periodic and random sources. Based on these observations we conjecture that the number of distinct $`𝐓`$ values for a given period is the number of distinct $`ϵ`$-machines needed to recognize all periodic sequences of a given prime period. That is, we conjecture that those sequences with the same $`𝐓`$ value have the same transient $`ϵ`$-machine structure, up to edge relabeling.

In summary, we analyzed what is arguably the simplest class of sequences: zero entropy rate, finite-period sequences. The sequences represent behaviors that are often ignored in many fields as being too simple. As we demonstrated, however, their structural complexity and synchronization properties are rich and subtle. Within a given period, there are large differences in structural complexity, as measured by the transient information $`𝐓`$ and the synchronization time $`\tau `$. Thus, even simple periodic systems are surprisingly complex.

## Acknowledgments

The authors thank James Massey for sending his lecture notes. This work was supported at the Santa Fe Institute under the Computation, Dynamics, and Inference Program via SFI’s core grants from the National Science and MacArthur Foundations. Direct support was provided from DARPA contract F30602-00-2-0583. DPF thanks the Department of Physics and Astronomy at the University of Maine for its hospitality.


format: text

text:
# Scattering of a Long Cosmic String by a Rotating Black Hole

## 1 Introduction

Study of cosmic strings and other topological defects and their motion in an external gravitational field is an interesting problem. Cosmic strings are topologically stable one-dimensional objects which are predicted by unified theories. Cosmic strings (as well as other topological defects) may appear during a phase transition in the early Universe. A detailed discussion of cosmic strings and other topological defects can be found in the book by Shellard and Vilenkin . Cosmic strings are naturally predicted by many realistic models of particle physics. The formation of cosmic strings helps to successfully exit the inflationary era in a number of the inflation models motivated by particle physics . The formation of cosmic strings is also predicted in the most classes of superstring compactification involving the spontaneous breaking of a pseudo-anomalous $`U(1)`$ gauge symmetry ( see e.g.  and references therein). Recent measurements of CMB anisotropy and especially the position of the acoustic peaks exclude some of the earlier proposed scenarios where the cosmic strings are the main origin of CMB fluctuations. On the other hand, recent analysis shows that a mixture of inflation and topological defects is consistent with current CMB data .

A black hole interacting with a cosmic string is a quite rear example of interaction of two relativistic non-local gravitating systems which allows rather complete analysis. This makes this system interesting from pure theoretical point of view. From more ”pragmatic” viewpoint, this system might be a strong source of gravitational waves. But in order to be able to study this effect one needs first to obtain an information on the motion of the string in the black hole background. The situation here is very similar to the case of gravitational radiation from bodies falling into the black hole.

In this paper we consider the scattering of a long cosmic string by a rotating black hole. We assume that a string is thin and its gravitational back reaction can be neglected. If $`\eta `$ is a characteristic energy scale of a phase transition responsible for a string formation then the thickness of a string is $`\rho \eta ^1`$ while its dimensionless mass per unit length parameter $`\mu ^{}=G\mu /c^2\eta ^2`$. For example, for GUT strings $`\rho _{GUT}10^{29}`$cm and $`\mu _{GUT}^{}10^6`$, and for the electroweak phase transitions $`\rho _{EW}10^{14}`$cm and $`\mu _{EW}^{}10^{34}`$. Since $`\mu ^{}1`$ one can neglect (at least in the lowest order approximation) effects connected with gravitational waves radiation during the scattering of the string by a black hole.

We assume that the size of the string is much larger then the Schwarzschild gravitational radius $`r_S=2GM/c^2`$ of a black hole and its total mass is much smaller than the black hole mass. The latter condition together with $`\mu ^{}1`$ means that we can consider a string as a test object. In order to specify the scattering problem we consider the simplest setup, with the string initially far away from the black hole, so that the string has the form of a straight line. We assume that string is initially moving with the velocity $`𝐯`$ towards the black hole and lying in the plane parallel to the rotation axis of the black hole. This plane is located at distance $`b`$ with respect to the parallel “plane” passing through the rotation axis. In analogy with a particle scattering we call $`b`$ the impact parameter.

The scattering of a cosmic string by a non-rotating black hole was previously studied both numerically and analytically . For $`br_S`$ the string moves in the region where the gravitational potential $`GM/r`$ is always small, and one can use a weak-field approximation where the string equation of motion can be solved analytically .

String scattering in the weak field limit can be described in qualitative terms. In the reference frame of the string the gravitational field of the black hole is time dependent and it excites the string’s transversal degrees of freedom. This effect occurs mainly when the central part of the string passes close to the black hole. Since information is propagating along the string at the velocity of light, there always exist two distant regions, ‘right’ and ‘left’, which have not yet felt this excitation. This asymptotic regions of the string continue their motion in the initial plane (‘old phase’). After scattering, when string is moving again far from the black hole, its central part moves again in a plane which is parallel to the initial plane but is shifted below it by a distance $`\kappa =2\pi GMv/\sqrt{c^2v^2}`$ (‘new phase’). There exist two symmetric kink-like regions separating the ‘new’ phase from the ‘old’ one. These kinks move out of the central region with the velocity of light and preserve their form. Besides the amplitude $`\kappa `$, the kinks are characterized by a width $`w`$ which depends on the impact parameter and the initial velocity of the string.

In the strong-field limit this picture qualitatively remains the same for string scattering by a Schwarzschild black hole. This problem was analyzed in detail numerically in . In particular, the quantities $`\kappa `$ and $`w`$ were found for different values of $`b`$ and $`v`$. The numerical calculations in the strong field limit demonstrated also that for special values of the initial impact parameter $`b<b_{crit}(v)`$ a cosmic string is captured by the black hole. The critical impact parameter for capture by the Schwarzschild black hole was obtained in .

In this paper we study of scattering of straight cosmic strings by a rotating black hole. We assume that the initial direction of the string is parallel to the rotational axis of the black hole. Our focus is on the calculation of the same quantities, $`\kappa `$ and $`w`$, and to study how black hole rotation modifies the earlier results for a non-rotating black hole. We present here results for string spacetime evolution, real profiles of a string at different external observer times $`T`$, as well as asymptotic scattering data. Results connected with capture of the string and near-critical scattering will be discussed in another paper.

The paper is organized as follows. Equations for string motion in a curved spacetime and their solutions in the weak field regime are discussed in section 2. Section 3 contains the formulation of the initial and boundary conditions for straight string motion in the Kerr geometry, and the general scheme of the numerical calculations. In section 4 we describe results for strong field scattering of strings in the Kerr spacetime and “real time” profiles of the strings. Section 5 contains information about asymptotic scattering data (displacement parameter and kink profiles) and their dependence on the impact parameter, velocity, and angular velocity of the black hole. Section 6 contains a general discussion. Numerical details are supplied in an appendix.

## 2 Equations of motion

### 2.1 String equation of motion

The worldsheet swept by the string in (4D curved background) space-time can be parametrized by a pair of variables $`\zeta ^A`$ ($`A=0,1`$) so that string motion is described by the equation $`x^\mu =𝒳^\mu (\zeta ^A)`$. The dynamics of the string in a spacetime with metric $`g_{\mu \nu }`$ is described by the Nambu-Goto effective action

$$I_0[𝒳^\mu ]=\mu d^2\zeta \sqrt{\gamma },$$
(2.1)
where

$$\gamma _{AB}=g_{\mu \nu }𝒳_{,A}^\mu 𝒳_{,B}^\nu $$
(2.2)
is the induced metric on the worldsheet. The same equations of motion of the string can be derived from the Polyakov’s form of the action ,

$$I[𝒳^\mu ,h_{AB}]=\frac{\mu }{2}d^2\zeta \sqrt{h}h^{AB}\gamma _{AB}.$$
(2.3)
We use units in which $`G=c=1`$, and the sign conventions of . In (2.3) $`h_{AB}`$ is the internal metric with determinant $`h`$.

The variation of the action (2.3) with respect to $`𝒳^\mu `$ and $`h_{AB}`$ gives the following equations of motion:

$$\mathrm{}𝒳^\mu +h^{AB}\mathrm{\Gamma }_{}^{\mu }{}_{\alpha \beta }{}^{}𝒳_{,A}^\alpha 𝒳_{,B}^\beta =0,$$
(2.4)
$$\gamma _{AB}\frac{1}{2}h_{AB}h^{CD}\gamma _{CD}=0,$$
(2.5)
where

$$\mathrm{}=\frac{1}{\sqrt{h}}_A(\sqrt{h}h^{AB}_B).$$
(2.6)
The first of these equations is the dynamical equation for string motion, while the second one plays the role of a constraint.

We fix internal coordinate freedom by using the gauge in which $`h_{AB}`$ is conformal to the flat two-dimensional metric $`\eta _{AB}=\text{diag}(1,1)`$. In this gauge the equations of motion for the string have the form

$$\mathrm{}𝒳^\mu +\mathrm{\Gamma }_{}^{\mu }{}_{\alpha \beta }{}^{}𝒳_{,A}^\alpha 𝒳_{,B}^\beta \eta ^{AB}=0,$$
(2.7)
and the constraint equations are

$$\gamma _{01}=g_{\mu \nu }\frac{𝒳^\mu }{\tau }\frac{𝒳^\nu }{\sigma }=0,$$
(2.8)
$$\gamma _{00}+\gamma _{11}=g_{\mu \nu }\left(\frac{𝒳^\mu }{\tau }\frac{𝒳^\nu }{\tau }+\frac{𝒳^\mu }{\sigma }\frac{𝒳^\nu }{\sigma }\right)=0.$$
(2.9)
Here, $`\tau \zeta ^0`$, $`\sigma \zeta ^1`$ and $`\mathrm{}=_\tau ^2+_\sigma ^2`$. These constraints are to be satisfied for the initial data. As a consequence of the dynamical equations they are valid for any later time.

### 2.2 Weak field approximation

In the absence of the external gravitational field $`g_{\mu \nu }=\eta _{\mu \nu }`$, where $`\eta _{\mu \nu }`$ is the flat spacetime metric. In Cartesian coordinates ($`T,X,Y,Z`$), $`\eta _{\mu \nu }=\text{diag}(1,1,1,1)`$ and $`\mathrm{\Gamma }_{}^{\mu }{}_{\alpha \beta }{}^{}=0`$, and it is easy to verify that

$$𝒳^\mu =𝒳_0^\mu (\tau ,\sigma )(\tau \mathrm{cosh}\beta ,\tau \mathrm{sinh}\beta +X_0,b,\sigma ),$$
(2.10)
$$h_{AB}=\eta _{AB}\text{diag}(1,1),$$
(2.11)
is a solution of equations (2.4) and (2.5). This solution describes a straight string oriented along the $`Z`$-axis which moves in the $`X`$-direction with constant velocity $`v=\mathrm{tanh}\beta `$. Initially, at $`\tau _0=0`$, the string is found at $`𝒳^\mu (0,\sigma )=(0,X_0,b,\sigma )`$. Later when we use this solution as initial data for a string scattering by a black hole, $`b`$ will play the role of impact parameter. For definiteness we choose $`b>0`$ and $`X_0<0`$, so that $`\beta >0`$.

Let us consider how this solution is modified when the straight string is moving in a weak gravitational field. We assume

$$g_{\mu \nu }=\eta _{\mu \nu }+q_{\mu \nu },$$
(2.12)
$$𝒳^\mu (\zeta )=𝒳_0^\mu (\zeta )+\chi ^\mu (\zeta ),$$
(2.13)
where $`q_{\mu \nu }`$ is the metric perturbation and $`\chi ^\mu `$ is the string perturbation. By making the perturbation of the equation of motion one gets

$$\mathrm{}\chi ^\mu =f^\mu ,$$
(2.14)
where

$$f^\mu =f^\mu (\zeta )=\mathrm{\Gamma }_{}^{\mu }{}_{\alpha \beta }{}^{}(𝒳_0)𝒳_{0,A}^\alpha 𝒳_{0,B}^\beta \eta ^{AB}.$$
(2.15)
We use Cartesian coordinates here so that $`\mathrm{\Gamma }_{}^{\mu }{}_{\alpha \beta }{}^{}`$ is simply the Christoffel symbol for $`q_{\mu \nu }`$.

The linearized constraint equations are

$$\eta _{\mu \nu }\frac{𝒳_0^\mu }{\tau }\frac{\chi ^\nu }{\sigma }+\eta _{\mu \nu }\frac{\chi ^\mu }{\tau }\frac{𝒳_0^\nu }{\sigma }+q_{\mu \nu }\frac{𝒳_0^\mu }{\tau }\frac{𝒳_0^\nu }{\sigma }=0,$$
(2.16)
$$2\eta _{\mu \nu }\left(\frac{𝒳_0^\mu }{\tau }\frac{\chi ^\nu }{\tau }+\frac{𝒳_0^\mu }{\sigma }\frac{\chi ^\nu }{\sigma }\right)+q_{\mu \nu }\left(\frac{𝒳_0^\mu }{\tau }\frac{𝒳_0^\nu }{\tau }+\frac{𝒳_0^\mu }{\sigma }\frac{𝒳_0^\nu }{\sigma }\right)=0.$$
(2.17)
As in the exact non-linear case, if these linearized constraints are satisfied at the initial moment of time $`\tau `$ they are also valid for any $`\tau `$ for a solution $`\chi ^\mu `$ of the dynamical equations (2.14).

The linearized equations can be used to study string motion in the case where it is far away from the black hole. In this case the gravitational field can be approximated as follows:

$$ds^2=(1\frac{2M}{R})dT^2+(1+\frac{2M}{R})(dX^2+dY^2+dZ^2)\frac{4J}{R^3}(XdYYdX)dT,$$
(2.18)
where $`R^2=X^2+Y^2+Z^2`$, and $`M`$ and $`J=aM`$ are the mass and angular momentum of the black hole, respectively. In fact this asymptotic form of the metric is valid for any arbitrary stationary localized distribution of matter, provided that the observer is located far from it. In agreement with (2.18) the gravitational field perturbation can be presented as

$$q_{\mu \nu }=q_{\mu \nu }^N+q_{\mu \nu }^{LT},$$
(2.19)
where the Newtonian and Lense-Thirring parts are

$$q_{\mu \nu }^N=2\phi \delta _{\mu \nu },\phi =\frac{M}{R},q_{\mu \nu }^{LT}=\frac{4J}{R^3}\delta _{(\mu }^0ϵ_{\nu )\alpha 03}X^\alpha .$$
(2.20)
Here $`ϵ_{\alpha \beta \gamma \delta }`$ is the antisymmetric symbol. The Lense-Thirring part $`q_{\mu \nu }^{LT}`$ of the metric  is produced by the rotation of the source of the gravitational field and it is responsible for frame dragging.

### 2.3 Newtonian scattering

In the linear approximation we can study the action of each of the parts of the metric perturbations independently. For the Newtonian part one has the following expression for the force $`f_N^\mu `$

$`f_N^0`$ $`=`$ $`2\mathrm{sinh}(\beta )\mathrm{cosh}(\beta ),\phi _{,1}`$ (2.21)
$`f_N^1`$ $`=`$ $`0,`$ (2.22)
$`f_N^2`$ $`=`$ $`2\mathrm{sinh}^2\beta \phi _{,2},`$ (2.23)
$`f_N^3`$ $`=`$ $`2\mathrm{cosh}^2\beta \phi _{,3},`$ (2.24)
and the constraint equations read

$`\chi _{,\tau }^3\mathrm{cosh}\beta \chi _{,\sigma }^0+\mathrm{sinh}\beta \chi _{,\sigma }^1`$ $`=`$ $`0,`$ (2.25)
$`\chi _{,\sigma }^3\mathrm{cosh}\beta \chi _{,\tau }^0+\mathrm{sinh}\beta \chi _{,\tau }^1`$ $`=`$ $`2\phi \mathrm{cosh}^2\beta .`$ (2.26)
The result $`f^1=0`$ means that in the first order approximation the string lies in the $`YZ`$plane at any fixed time $`\tau =\text{const}`$. The dynamical equations (2.3) can be easily integrated by using the retarded Green function (see ).

We focus now our attention on the behavior of $`\chi ^2`$ which describes the string deflection in the plane orthogonal to its motion. It is easy to show that the asymptotic value of $`\chi ^2(\tau \mathrm{},\sigma )`$ is the same for any fixed $`\sigma `$. We denote it $`b\kappa `$. The following expression is valid for $`\kappa `$

$$\kappa =\frac{1}{2\mathrm{sinh}\beta }_{\mathrm{\Pi }_0}𝑑X𝑑Zf^2,$$
(2.27)
where $`\mathrm{\Pi }_0`$ is the two-dimensional worldsheet swept by the string in its motion in the background spacetime. This integral can be easily calculated since

$$_{\mathrm{\Pi }_0}𝑑X𝑑Z\phi _{,Y}=2\pi M$$
(2.28)
is the flux of the Newtonian field strength through $`\mathrm{\Pi }_0`$. Thus we have

$$\kappa =2\pi M\mathrm{sinh}\beta .$$
(2.29)
At any late moment of time $`\tau `$ the central part of the string is a straight line moving in the plane $`Y=b\kappa `$, while its far distant parts move in the original plane $`Y=b`$. These different “phases” are connected by kinks propagating in the direction from the center with the velocity of light. (For details, see ). We call $`\kappa `$ the displacement parameter. Figure 1 shows the Y-direction displacement for the Newtonian scattering as a function of $`\tau `$ and $`\sigma `$.

### 2.4 Lense-Thirring scattering

In the presence of rotation the Lense-Thirring force acting on the string in the linearized approximation is

$`f_{LT}^0`$ $`=`$ $`6J\mathrm{sinh}^2\beta {\displaystyle \frac{b(X_0+\tau \mathrm{sinh}\beta )}{^5}},`$ (2.30)
$`f_{LT}^1`$ $`=`$ $`0,`$ (2.31)
$`f_{LT}^2`$ $`=`$ $`2J\mathrm{sinh}\beta \mathrm{cosh}\beta \left({\displaystyle \frac{1}{^3}}{\displaystyle \frac{3\sigma ^2}{^5}}\right),`$ (2.32)
$`f_{LT}^3`$ $`=`$ $`6J\mathrm{sinh}\beta \mathrm{cosh}\beta {\displaystyle \frac{b\sigma }{^5}},`$ (2.33)
where $`=\sqrt{(X_0+\tau \mathrm{sinh}\beta )^2+b^2+\sigma ^2}`$. As before, $`f^1=0`$.

The constraint equations now take the form

$$\chi _{,\tau }^3\mathrm{cosh}\beta \chi _{,\sigma }^0+\mathrm{sinh}\beta \chi _{,\sigma }^1=0,$$
(2.34)
$$\chi _{,\sigma }^3\mathrm{cosh}\beta \chi _{,\tau }^0+\mathrm{sinh}\beta \chi _{,\tau }^1=2J\mathrm{sinh}\beta \mathrm{cosh}\beta \frac{b}{^3}.$$
(2.35)
The dynamical equations can be solved analytically. For the initial conditions

$$\chi ^0|_{\tau =0}=0,$$
(2.36)
$$\chi ^2|_{\tau =0}=\frac{\chi ^2}{\tau }|_{\tau =0}=0,$$
(2.37)
$$\chi ^3|_{\tau =0}=\frac{\chi ^3}{\tau }|_{\tau =0}=0,$$
(2.38)
the solution is

$$\chi ^0=Jb\mathrm{sinh}\beta (\frac{(X_0+\tau \mathrm{sinh}\beta )\mathrm{sinh}\beta +\sigma }{\mathrm{\Delta }_{(+)}}+\frac{(X_0+\tau \mathrm{sinh}\beta )\mathrm{sinh}\beta \sigma }{\mathrm{\Delta }_{(++)}}$$

$$\frac{X_0\mathrm{sinh}\beta (\tau \sigma )}{\mathrm{\Delta }_{(+)}\rho _{}}\frac{X_0\mathrm{sinh}\beta (\tau +\sigma )}{\mathrm{\Delta }_{(++)}\rho _+}),$$
(2.39)
$$\chi ^1=0,$$
(2.40)
$$\chi ^2=J\mathrm{sinh}\beta \mathrm{cosh}\beta (\frac{\tau ^2\mathrm{sinh}^2\beta +\tau \sigma \mathrm{sinh}^2\beta +2X_0\tau \mathrm{sinh}\beta +\sigma X_0\mathrm{sinh}\beta +X_0^2+b^2}{\mathrm{\Delta }_{(++)}}$$

$$+\frac{\tau ^2\mathrm{sinh}^2\beta +\tau \sigma \mathrm{sinh}^2\beta 2X_0\tau \mathrm{sinh}\beta +\sigma X_0\mathrm{sinh}\beta X_0^2b^2}{\mathrm{\Delta }_{()}}$$
(2.41)
$$+\frac{X_0\mathrm{sinh}\beta (\tau +\sigma )+X_0^2+b^2}{\mathrm{\Delta }_{(++)}\rho _+}+\frac{X_0\mathrm{sinh}\beta (\tau \sigma )+X_0^2+b^2}{\mathrm{\Delta }_{()}\rho _{}}),$$

$$\chi ^3=Jb\mathrm{sinh}\beta \mathrm{cosh}\beta (\frac{(X_0+\tau \mathrm{sinh}\beta )\mathrm{sinh}\beta \sigma }{\mathrm{\Delta }_{(++)}}\frac{(X_0+\tau \mathrm{sinh}\beta )\mathrm{sinh}\beta +\sigma }{\mathrm{\Delta }_{()}}$$

$$\frac{X_0\mathrm{sinh}\beta (\tau +\sigma )}{\mathrm{\Delta }_{(++)}\rho _+}+\frac{X_0\mathrm{sinh}\beta (\tau \sigma )}{\mathrm{\Delta }_{()}\rho _{}}),$$
(2.42)
$$\mathrm{\Delta }_{\pm \pm }=(X_0\pm (\tau \pm \sigma )\mathrm{sinh}\beta )^2+b^2\mathrm{cosh}^2\beta ,$$
(2.43)
$$\rho _\pm =\sqrt{X_0^2+b^2+(\tau \pm \sigma )^2}.$$
(2.44)
Using these relations it is possible to see that the displacement parameter $`\kappa =lim_\tau \mathrm{}\chi ^2(\tau ,\sigma =0)`$ vanishes for this solution. The reason is the following. Using (2.32) it is easy to present $`f_{LT}^2`$ as

$$f_{LT}^2=2J\mathrm{sinh}\beta \mathrm{cosh}\beta \frac{}{\sigma }\left(\frac{\sigma }{^3}\right).$$
(2.45)
The asymptotic displacement is given by (2.27). The integral over $`Z`$ or, equivalently, the integral over $`\sigma `$ from $`f_{LT}^2`$, which is a total derivative over $`\sigma `$, reduces to boundary terms $`\sigma /^3`$ at $`\sigma =\pm \mathrm{}`$, which vanish.

Figure 2 shows the $`Y`$direction displacement as a function of $`\tau `$ and $`\sigma `$ for the weak field scattering. It should be emphasized that the scale of structures for Lense-Thirring scattering is much smaller than that for Newtonian scattering. This can be easily seen if we compare the Newtonian force $`f_NM/^2`$ with the Lense-Thirring force $`f_{LT}J/^3`$

$$\frac{f_{LT}}{f_N}\frac{J}{M}\frac{J}{Mb}.$$
(2.46)
For the scattering by a rotating black hole $`J=aM`$, where $`|a|/M1`$ is the rotation parameter. Hence

$$\frac{f_{LT}}{f_N}\frac{M}{b}$$
(2.47)
which is small for the weak field scattering. For this reason, in the weak field regime the string profiles for the prograde or retrograde scattering by rotating black hole do not greatly differ from the profiles for the scattering by a non-rotating black hole of the same mass. The situation is different for strong-field scattering: the displacement parameter is different for prograde and retrograde scattering, and for near-critical scattering the profiles of the kinks contain visible structure produced by effects connected with the rotation of the black hole.

## 3 String scattering by a Kerr black hole

### 3.1 String in the Kerr spacetime

Our aim is to study a string motion in the Kerr spacetime. The Kerr metric in Boyer-Lindquist coordinates $`(t,r,\theta ,\varphi )`$ has the form

$`ds^2`$ $`=`$ $`(1{\displaystyle \frac{2Mr}{\mathrm{\Sigma }}})dt^2+{\displaystyle \frac{\mathrm{\Sigma }}{\mathrm{\Delta }}}dr^2+\mathrm{\Sigma }d\theta ^2+{\displaystyle \frac{A\mathrm{sin}^2\theta }{\mathrm{\Sigma }}}d\varphi ^2{\displaystyle \frac{4aMr\mathrm{sin}^2\theta }{\mathrm{\Sigma }}}dtd\varphi ,`$ (3.1)
$`\mathrm{\Sigma }`$ $`=`$ $`r^2+a^2\mathrm{cos}^2\theta ,`$ (3.2)
$`\mathrm{\Delta }`$ $`=`$ $`r^22Mr+a^2,`$ (3.3)
$`A`$ $`=`$ $`(r^2+a^2)^2a^2\mathrm{\Delta }\mathrm{sin}^2\theta ,`$ (3.4)
where $`M`$ is the mass of the black hole, and $`J=aM`$ is its angular momentum ($`0aM`$). At far distances this metric has the asymptotic form (2.18).

In order to be able to deal with the case where part of the string crosses the event horizon for the numerical simulation we adopt the so-called Kerr (in-going) coordinates $`(\stackrel{~}{v},r,\theta ,\stackrel{~}{\varphi })`$

$$ds^2=(1\frac{2Mr}{\mathrm{\Sigma }})d\stackrel{~}{v}^2+2d\stackrel{~}{v}dr\frac{4aMr\mathrm{sin}^2\theta }{\mathrm{\Sigma }}d\stackrel{~}{v}d\stackrel{~}{\varphi }a\mathrm{sin}^2\theta drd\stackrel{~}{\varphi }$$

$$+\mathrm{\Sigma }d\theta ^2+\frac{A\mathrm{sin}^2\theta }{\mathrm{\Sigma }}d\stackrel{~}{\varphi }^2,$$
(3.5)
with

$`\stackrel{~}{v}`$ $`=`$ $`t+r+M\mathrm{ln}|{\displaystyle \frac{\mathrm{\Delta }}{4M^2}}|+{\displaystyle \frac{M^2}{\sqrt{M^2a^2}}}\mathrm{ln}\left|{\displaystyle \frac{rM\sqrt{M^2a^2}}{rM+\sqrt{M^2a^2}}}\right|+M,`$ (3.6)
$`\stackrel{~}{\varphi }`$ $`=`$ $`\varphi +{\displaystyle \frac{a}{2\sqrt{M^2a^2}}}\mathrm{ln}\left|{\displaystyle \frac{rM\sqrt{M^2a^2}}{rM+\sqrt{M^2a^2}}}\right|.`$ (3.7)
The metric (3.1) has the asymptotic form

$$ds^2=dt^2+dr^2+r^2(d\theta ^2+\mathrm{sin}^2\theta d\varphi ^2)+\frac{2M}{r}(dt^2+dr^2)\frac{4aM}{r}\mathrm{sin}^2\theta dtd\varphi .$$
(3.8)
Let us introduce new “quasi-Cartesian” coordinates

$`T`$ $`=`$ $`t,`$
$`X`$ $`=`$ $`R\mathrm{sin}\theta \mathrm{cos}\varphi ,`$
$`Y`$ $`=`$ $`R\mathrm{sin}\theta \mathrm{sin}\varphi ,`$
$`Z`$ $`=`$ $`R\mathrm{cos}\theta ,`$
where

$$r=R+M.$$
(3.9)
One can easily check that the metric (3.8) in the quasi-Cartesian coordinates (3.1) has the asymptotic form (2.18)

It should be emphasized that without the shift (3.9) of the radial coordinate one does not recover (2.18). The reason for this is easy to understand if one considers the same problem for the Schwarzschild geometry. The asymptotic limit of (2.18) with $`a=0`$ can be found in the isotropic coordinates with $`r=\stackrel{~}{R}(1+M/2\stackrel{~}{R})^2`$ in which the spatial part of the metric is conformal to the flat metric. Asymptotically, it is sufficient to use (3.9) which is the leading part of $`r`$ at large $`\stackrel{~}{R}`$.

In what follows we shall use these quasi-Cartesian coordinates for representing the position and the form of the string in the Kerr spacetime even if we are not working in the weak field regime. It should be emphasized that since the space in the Kerr geometry is not flat, plots constructed in these coordinates do not give a “real picture”. This is a special case of a general problem of the visualization of physics in a 4-dimensional curved spacetime.

### 3.2 Initial and boundary conditions

In an ideal situation, we would study scattering by initially placing our infinitely long string at spatial infinity, where the spacetime is flat and the straight string can be described in simple terms. In a numerical scheme, however, the string cannot be infinitely long and we must start the simulation at a finite distance from the black hole. We discuss here the initial and boundary conditions used for the simulations.

In studying the scattering of a straight string, we consider the special case where the string is initially parallel to the axis of rotation of the black hole. We use Cartesian coordinates in the asymptotic region so that $`X`$-axis coincides with the direction of motion and the $`Z`$-axis is along the string (see Fig. 3).

We consider a string segment of length $`L10^4M`$ at a time $`\tau _0`$ and an initial distance $`X_0`$ from the black hole. In order to keep accuracy high and yet prevent the calculation time from being inordinately large, we do not evolve the straight string numerically from this initial position. Instead, we use the weak-field approximation to describe the string configuration at a later time $`\tau _s`$ where the distance $`X_s`$ is closer to the black hole, $`|X_s||X_0|`$ <sup>4</sup><sup>4</sup>4 In our simulations we put $`X_0=10^6M`$ and $`X_s=500M`$ .

Given a sufficiently long string segment, the boundary points move at a great distance from the black hole, so that their evolution can be described by the weak field approximation until information about the interaction with the black hole reaches the boundary. We denote this time as $`\tau _{}`$. Starting from this moment we solve the dynamical equations in the region $`|\sigma |<L(\tau \tau _{})`$ (see figure 4). The larger is the initial value $`L`$ the longer one can go in $`\tau `$ in the simulation. We choose $`L`$ to be large enough to provide the required accuracy in the determining the final scattering data.

Since the boundary conditions found from the weak field regime calculations are not exact there will be disturbance created by this effect. In some cases, when it is important to exclude these disturbances, we used a modified scheme of calculations in which no boundary conditions are used from the very beginning of the simulation. The price for this is that one needs to take longer initial size of $`L`$ which in turn increases the computational time.

### 3.3 Solving dynamical equations and constraints

Using the initial conditions at $`\tau _s`$ and boundary conditions we solve numerically the dynamical equations (2.7). Since the equations are of second order, we use the weak-field approximation to get initial data at $`\tau _s`$ and $`\tau _s+\mathrm{\Delta }\tau `$ in order to completely specify the initial value problem. The numerical scheme uses second-order finite differences and evolves the string configuration using an implicit scheme. Because of the symmetry $`\sigma \sigma `$ it is sufficient to evolve only half of the string worldsheet, $`\sigma 0`$, and use a reflecting boundary condition at the string midpoint. The numerical grid is non-uniform with the denser part following the motion of the kink. We used the constraint equations (2.8-2.9) for an independent check of the accuracy of the calculations. More details on the numerical scheme can be found in the Appendix.

## 4 String profiles for strong field scattering

### 4.1 General picture

Figure 5 demonstrates general features of straight string scattering, here for a string with velocity $`v=0.762`$ ($`\beta =1`$). The four panels show the displacement in the $`Y`$direction as a function of internal coordinates $`(\tau ,\sigma )`$ for weak and strong field scattering.

Figure 5 (a) shows the scattering for an impact parameter $`b=80M`$. The value of the displacement parameter at the largest $`\tau `$ shown is $`\kappa =7.23M`$. This value as well as the form of the kinks are in a very good agreement with the weak-field scattering results. Plots for prograde and retrograde scattering at $`b=80M`$ are virtually indistinguishable from Fig. 5 (a).

Figures 5 (b–d) show the scattering for $`b=6M`$. Qualitatively these plots are similar to weak-field scattering. The main differences are the following: (1) The value of the displacement parameter $`\kappa =11.03M`$ for the non-rotating black hole is significantly larger then $`\kappa =7.23`$ for $`b=80M`$. (2) Effects of rotation are more pronounced. The displacement $`\kappa `$ for retrograde scattering is essentially larger than $`\kappa `$ for the prograde scattering. (3) The string profile after scattering is more sharp, the width of the kinks is visibly smaller that for weak-field scattering.

### 4.2 “Real-time profiles” of the string for strong-field scattering

It should be emphasized that figure 5 give an accurate impression of the displacement effect, but they give a distorted view of the real form of the string. The reason is evident. The grid imposed on the worldsheet is determined by the choice of $`(\tau ,\sigma )`$ coordinates. But a $`\tau =\mathrm{const}`$ section differs from a time $`T=\mathrm{const}`$ section in the laboratory slice of spacetime. The position of the string at given time $`T`$ can be found by using the functions $`T(\tau ,\sigma )`$, $`X(\tau ,\sigma )`$, $`Y(\tau ,\sigma )`$, $`Z(\tau ,\sigma )`$, to find functions $`X(T,Z)`$ and $`Y(T,Z)`$. For fixed $`T`$ these functions determine a position of the string line in 3-space.

Figures 6, 7 and 8 show a sequence of “real-time” profiles for strong-field string scattering at five different coordinate times $`T`$. We ordered them so that the larger number labeling the string corresponds to later time. In figure 6 the black hole is non-rotating. Figures 7 and 8 show the “real-time” profiles for retrograde and prograde scattering for a maximally rotating black hole, respectively. Again we can see that due to frame dragging, the distortion of the string is more pronounced for retrograde scattering.

## 5 Late time scattering data

### 5.1 Displacement parameter

Figure 9 shows the dependence of the displacement parameter $`\kappa `$ on the impact parameter $`b`$ for different velocities $`v`$. For a given value of $`b`$ the curve for $`a/M=1`$ always lies higher than the curves for more positive values of $`a/M`$. This is true for all values of velocity $`v`$, but this difference is more pronounced at large velocities.

The relative location of the curves for given $`v`$ and $`b`$ and different $`a`$ can be explained by frame dragging. Namely, a string in the retrograde motion is effectively slowed down when it passes near the black hole and hence it spends more time near it. As the result its displacement is greater than the displacement for the prograde motion with the same impact parameter. Let us make order of magnitude estimation of this effect. For this purpose we use metric (2.18). We focus our attention on the Lense-Thirring term and neglect for a moment the Newtonian part. Consider first a point particle moving in this metric with the velocity $`v`$ and impact parameter $`b`$. In the absence of rotation it moves with constant velocity so that $`(X=vT,Y=b,Z=0)`$ and the proper time $`\tau `$ is

$$\tau _0=\sqrt{1v^2}T.$$
(5.1)
In the presence of rotation one has

$$d\tau ^2=(1v^2)dT^2\frac{4Jbv}{R^3}dT^2,$$
(5.2)
where

$$R^2=b^2+v^2T^2.$$
(5.3)
For large $`b`$ one can write

$$\tau =\tau _0+\mathrm{\Delta }\tau ,$$
(5.4)
where

$$\mathrm{\Delta }\tau =\frac{2Jbv}{\sqrt{1v^2}}_{\mathrm{}}^{\mathrm{}}\frac{dT}{(b^2+v^2T^2)^{3/2}}=\frac{4J}{b\sqrt{1v^2}}.$$
(5.5)
This quantity $`\mathrm{\Delta }\tau `$ characterize additional time delay for the motion in the Lense-Thirring field. The characteristic time of motion in the vicinity of a black hole is $`\tau _{int}b/v`$. Thus we have

$$\frac{\mathrm{\Delta }\tau }{\tau _{int}}\frac{4Jv}{b^2\sqrt{1v^2}}.$$
(5.6)
One can expect that a similar delay takes place for a string motion. As a result of being longer close to the black hole the string has a larger displacement by the value $`\mathrm{\Delta }\kappa `$ such that

$$\frac{\mathrm{\Delta }\kappa }{\kappa }\frac{\mathrm{\Delta }\tau }{\tau _{int}}\frac{4Ma}{b^2}\mathrm{sinh}\beta .$$
(5.7)
Qualitatively this relation explains dependence of $`\kappa `$ on $`a`$ and $`\beta `$ presented in figure 9.

More generally, if we look at the $`\alpha =a/M`$ in the metric as a parameter, we can use perturbation theory to calculate the effect of rotation. The solution $`𝒳^\mu `$ can be expanded in powers of $`\alpha `$

$$𝒳^\mu =\stackrel{\mu }{\stackrel{0}{𝒳}}+\alpha \stackrel{\mu }{\stackrel{1}{𝒳}}+\alpha ^2\stackrel{\mu }{\stackrel{2}{𝒳}}+\mathrm{},$$
(5.8)
where $`\stackrel{\mu }{\stackrel{0}{𝒳}}(\tau ,\sigma )`$ is the solution for the non-rotating case and $`\stackrel{\mu }{\stackrel{i}{𝒳}}(\tau ,\sigma )`$ are the perturbation corrections.

Numerical calculations show that the first two terms in the perturbation series give very good approximation to the solution as long as we are not close to critical scattering. As a consequence

$$\kappa =\kappa _0\kappa _1\alpha \kappa _2\alpha ^2,$$
(5.9)
where $`\kappa _0`$ is the $`Y`$ displacement for the non-rotating black hole, and $`\kappa _1`$,$`\kappa _2`$ are defined simply as

$$\kappa _{1,2}=\underset{\tau \mathrm{}}{lim}\stackrel{2}{\stackrel{1,2}{𝒳}}(\tau ,0).$$
(5.10)
In the above $`\stackrel{2}{\stackrel{1,2}{𝒳}}`$ denotes the $`Y`$ coordinate corrections. The equations of motion for $`\stackrel{\mu }{\stackrel{1,2}{𝒳}}`$ are linear and $`\stackrel{\mu }{\stackrel{1,2}{𝒳}}`$ can be obtained in one run together with $`\stackrel{\mu }{\stackrel{0}{𝒳}}`$.

In order to determine the coefficients in equation (5.9) we need to extrapolate the relevant data obtained during the simulation to infinity. One possibility is to numerically advance the solution very far from the black hole and simply take the value at the end of the simulation as our estimate. The problem with this approach is that to advance very far by maintaining high accuracy of the solution is a very lengthy process, feasible only for larger impact parameters (since the grid can be sparser).

Our approach was to advance to a moderate distance ($`X_{\mathrm{max}}8000M`$) keeping high accuracy of the solution (judged by the constraint equations). Then we fit the calculated data by the function

$$\kappa (0,\tau )=\kappa +k(\tau \tau _{sh})^\gamma ,$$
(5.11)
where $`\kappa `$, $`k`$, $`\tau _{sh}`$, $`\gamma `$ are the parameters to be fitted. We take our first data point at $`X=1000M`$. To see how consistent this procedure is and to estimate the errors we perform three fits with different set of data points. The first set uses all the data points, the second one uses only the first half, and the third one uses only the last half of the data points. For this particular problem the disturbances from the boundary have adverse effect to the fit therefore we use the null boundary approach.

Our experience shows that the fitting procedure for $`\kappa `$ works much better for larger velocities and larger impact parameters. For the velocities $`v/c=0.762`$, $`0.964`$, $`0.995`$ the estimated values of $`\kappa `$ from all three fits are consistent and differ by no more than 3% <sup>5</sup><sup>5</sup>5For $`b12M`$ the results from the three fits differ by less than 1%.. This fact gives us reasonable confidence that the plotted values of $`\kappa `$ indeed represent the true values.

Unfortunately the situation is not so good for slower velocities. For example for the case $`v/c=0.462`$ the slope of the fitted function $`\kappa (0,\tau )`$ is almost constant during the later phases of the simulation and fits using different sets of data points yield inconsistent (and improbable) values of $`\kappa `$. We expect the behavior of $`\kappa (0,\tau )`$ to change but we did not see it in our data even after driving the simulation four times further then for the other velocities ($`X_{\mathrm{max}}32,000M`$). Again, this behavior is more pronounced for smaller impact parameters $`b`$.

To obtain the values for $`\kappa _1`$ and $`\kappa _2`$ we use the same method as for $`\kappa `$. We did not encounter any difficulties in estimating the values of $`\kappa _1`$ and $`\kappa _2`$ for any of the four velocities. The trend here is the opposite of the one for $`\kappa `$ – the fits work best for smaller velocities and smaller impact parameters. The fits with different set of data points are typically less than $`1`$% appart.

Figure 10 shows the results in a log-log plot. Figure 11 shows the plot of $`\kappa _1/\kappa `$. The straight lines shown are obtained from least square fit. Note that the plots for the velocities $`v/c=0.964`$ and $`v/c=0.995`$ lie on top of each other.

In the interval shown $`\kappa _1`$ and $`\kappa _2`$ can be reasonably approximated by a functions of the form

$$\kappa _{1,2}A_{1,2}(v)\left(\frac{1}{b}\right)^{\lambda _{1,2}}.$$
(5.12)
Similarly for $`\kappa _1/\kappa `$,

$$\frac{\kappa _1}{\kappa }A_3(v)\left(\frac{1}{b}\right)^{\lambda _3}.$$
(5.13)
The values for $`A_{1,2,3}`$ and $`\lambda _{1,2,3}`$ obtained from a linear fit are shown in table 1. By comparing (5.13) with (5.7) one can conclude that the numerical value $`\lambda _3=2.23`$ is close to the value $`2`$, which enters the relation (5.7).

Note that the last data point on the plot for $`\kappa _2`$ is a bit out of a straight line. We are not sure if this is a genuine feature or simply inaccurate data points (e.g., due to round-off errors)<sup>6</sup><sup>6</sup>6The discrepancies are larger than those which could result from the extrapolation procedure.. We did not include these data points into calculation of the values in table 1.

### 5.2 Form of the kinks

Figure 12 shows details of the transition from the “old phase” to the “new phase” for two different impact parameters. We see that the width of the kinks differs significantly. In general the width also depends on the velocity $`v/c`$.. The dependence of the kink width on velocity and the impact parameter can be estimated from the weak field approximation as

$$w\frac{bc}{v}.$$
(5.15)
We operationally define the width of the kink to be the width of the peak of $`dY/d\sigma `$ at $`1/20`$th of its hight. Figure 13 shows comparison of the kink widths obtained from simulation with a function

$$w_{\mathrm{analyt}}=7.14\frac{bc}{v}.$$
(5.16)
The numerical constant was obtained by a fit. The match with the data is very good.

We also noticed that the dependency of the width of the kink on the rotation parameter $`a`$ is rather small. In general

$$w_{a/M=1}<w_{a/M=0}<w_{a/M=1}.$$
(5.17)
For the parameters shown on figure 13 the rotation made a difference from $`3M`$ to $`7M`$ for the extremal black holes.

## 6 Discussion

In this paper we studied the scattering of a long test cosmic string by a rotating black hole. We demonstrated that qualitatively many general features of the weak field scattering are present in scattering of the cosmic string in the strong field regime. Displacement of the string in the $`Y`$direction always has the form of a transition of the string from the initial phase (initial plane) to the final phase (final plane which is parallel to the initial one and displaced in the direction to the black hole by distance $`\kappa `$). The boundary between these phases is a kink moving with the velocity of light away from the center. An important difference between weak- and strong-field scattering is in the dependence of $`\kappa `$ on the impact parameter $`b`$ and velocity $`v`$. In general $`\kappa `$ for strong field scattering is much greater that its value calculated by weak-field approximation. It is also always greater for retrograde scattering than for a prograde scattering. The explanation of this is quite simple: The retrograde string spends more time in the vicinity of the black hole than a prograde one. This effect is a result of the dragging of the string into rotation by the black hole.

The width of the kink for the strong field scattering is smaller than for the scattering in the weak field regime.

As was demonstrated in previous studies for string scattering by non-rotating black holes, for any given velocity there exists a critical value $`b_{crit}`$ of the initial impact parameter so that for $`b<b_{crit}`$ the string is trapped by the black hole, while for $`b>b_{crit}`$ it is scattered by the black hole (and all points on the string reach infinity). In this paper we focus our attention on scattering in the regime where $`b`$ is significantly greater than $`b_{crit}`$. The study of string capture and near-critical string scattering requires modification of the computational program and more time consuming calculations. We are going to present these results in a subsequent publication.

Acknowledgments: The authors are grateful to Don Page for various stimulating discussions. This work was partly supported by the Natural Sciences and Engineering Research Council of Canada. One of the authors (V.F.) is grateful to the Killam Trust for its financial support. M.S. thanks FS Chia PhD Scholarship. Our work made use of the infrastructure and resources of MACI (Multimedia Advanced Computational Infrastructure), funded in part by the CFI (Canada Foundation for Innovation), ISRIP (Alberta Innovation and Science Research investment Program), and the Universities of Alberta and Calgary.

## Appendix A Numerical scheme details

In section 3.2 we briefly described the numerical scheme we adopted. In this appendix we present some more details. Figure 4 shows the overall structure of the time domain.

The numerical grid in the sigma direction is non-uniform. This is very important since there are regions where the string is relatively straight and regions with high curvature. By far the numerically most “sensitive” region is the kink. Therefore we make the grid denser in the vicinity of the kink. The length of the dense zone is chosen to be approximately twice the kink width<sup>7</sup><sup>7</sup>7The grid within each zone is uniform. The steeper the kink the denser the grid must be. Typically, the dense zone is $`3`$$`30`$ times denser then the rest of the grid.

The time step $`\mathrm{\Delta }\tau `$ must not exceed the smallest distance between any two grid points $`\mathrm{\Delta }\sigma `$. A convenient choice turns out to be

$$\mathrm{\Delta }\tau =\mathrm{\Delta }\sigma \sqrt{1v^2/c^2}.$$
(A.1)
This means that dense grid also implies small time step which in turn makes the simulation time longer. The formula (5.15) explains why it is more difficult to deal with small impact parameters and relativistic velocities.

Since the kink is moving away from the central point $`\sigma =0`$ the dense zone must move with it. Therefore we regularly check the position of the kink and adjust the grid when the kink reaches the boundary of the dense zone. This procedure is illustrated in figure 14. Note that we introduced similar (but much shorter) dense zone at the edge of the string. This is to prevent from “cutting” the string too quickly (every time step we lose one grid point). When we change the the grid structure we must use interpolation to obtain the variable values at the new grid points. In our case we used cubic spline which proved to work very well.

At certain stage the two dense zones merge and eventually they disappear altogether (which means that the kink passed the edge of our numerical domain). At this point we can increase $`\mathrm{\Delta }\tau `$ to reflect the sparser grid.

Since our problem is naturally formulated on rectangular grid the finite difference method is used to discretize the equations of motion. To approximate the first and second derivatives we use standard second order centered formulas, e.g.,

$$(_\tau 𝒳^\mu )_{i,j}=\frac{𝒳_{i+1,j}^\mu 𝒳_{i1,j}^\mu }{2\mathrm{\Delta }\tau }$$
(A.2)
$$(_\tau ^2𝒳^\mu )_{i,j}=\frac{𝒳_{i+1,j}^\mu 2𝒳_{i,j}^\mu +𝒳_{i1,j}^\mu }{\mathrm{\Delta }\tau ^2},$$
(A.3)
where index $`i`$ marks the $`i`$-th time step and $`j`$ marks the $`j`$-th grid point in the sigma direction. Similar expressions are used for the spatial derivatives except for the points lying at the boundary between dense and “normal” zones. In that case we must use modified formulas

$$(_\sigma 𝒳^\mu )_{i,j}=\frac{1}{\mathrm{\Delta }\sigma _{j1}+\mathrm{\Delta }\sigma _{j+1}}\left(\frac{\mathrm{\Delta }\sigma _{j1}}{\mathrm{\Delta }\sigma _{j+1}}(𝒳_{i,j+1}^\mu 𝒳_{i,j}^\mu )+\frac{\mathrm{\Delta }\sigma _{j+1}}{\mathrm{\Delta }\sigma _{j1}}(𝒳_{i,j}^\mu 𝒳_{i,j1}^\mu )\right)$$
(A.4)
$$(_\sigma ^2𝒳^\mu )_{i,j}=\frac{2}{\mathrm{\Delta }\sigma _{j1}+\mathrm{\Delta }\sigma _{j+1}}\left(\frac{1}{\mathrm{\Delta }\sigma _{j+1}}(𝒳_{i,j+1}^\mu 𝒳_{i,j}^\mu )\frac{1}{\mathrm{\Delta }\sigma _{j1}}(𝒳_{i,j}^\mu 𝒳_{i,j1}^\mu )\right),$$
(A.5)
where $`\mathrm{\Delta }\sigma _{j1}=\sigma _j\sigma _{j1}`$ and $`\mathrm{\Delta }\sigma _{j+1}=\sigma _{j+1}\sigma _j`$.

After the discretization process we obtain a set of four coupled non-linear equations for the four unknown variables $`𝒳_{i+1,j}^\mu `$ at each grid point $`\sigma _j`$. Since the equations for different $`j`$’s are independent of each other we can solve them in parallel.