Pisot Sequences

Thanks to the number associated with my diurnal age today, 27204, I was introduced to so-called Pisot sequences that I'm still coming to terms with. Let's start with one of the properties of this number, namely its membership in OEIS A048589:

A048589

Pisot sequence L(7, 9).

The members of the sequence are derived using the following formula:

$$a(n)= \Biggl \lceil \frac{a(n - 1)^2}{a(n - 2)} \Biggr \rceil \\ \text{ where } n \geq 2 \text{ with }a(0)=7 \text{ and } a(1)=9$$The initial members of the sequence are:

7, 9, 12, 16, 22, 31, 44, 63, 91, 132, 192, 280, 409, 598, 875, 1281, 1876, 2748, 4026, 5899, 8644, 12667, 18563, 27204, 39868, 58428, 85629, 125494, 183919, 269545, 395036, 578952, 848494, 1243527, 1822476, 2670967, 3914491, 5736964, 8407928, 12322416, 18059377

However, exactly the same sequence of numbers can be derived from the recurrence relation:$$a(n)=2a(n-1)-  a(n-2) + a(n-3) - a(n-4)\\ \text{ with } a(0)=7, a(1)=9, a(2)=12 \text{ and } a(3)=16$$However, the equivalence may last only up to \(n=1000\) according to the OEIS comments. After that, there is uncertainty. Permalink.

Let's take another example using OEIS A018910:

A018910

Pisot sequence L(4, 5).

Once again, the previous formula can be used with different starting values:$$a(n)= \Biggl \lceil \frac{a(n - 1)^2}{a(n - 2)} \Biggr \rceil \\ \text{ where } n \geq 2 \text{ with }a(0)=4 \text{ and } a(1)=5 $$The initial members of the sequence are:

4, 5, 7, 10, 15, 23, 36, 57, 91, 146, 235, 379, 612, 989, 1599, 2586, 4183, 6767, 10948, 17713, 28659, 46370, 75027, 121395, 196420, 317813, 514231, 832042, 1346271, 2178311, 3524580, 5702889, 9227467, 14930354, 24157819, 39088171, 63245988, 102334157, 165580143

Again, the same sequence can be generated using the recurrence relation (permalink):$$a(n)=2a(n-1)- a(n-3)\\ \text{ with } a(0)=4, a(1)=5 \text{ and } a(2)=7 $$Just to confuse matters we can also generate the sequence using:$$a(n) = \text{ Fibonacci}(n+3)+2$$What the letter L signifies I don't know. Other letters are used with Pisot sequences, including E, P and T. Not all Pisot sequences use the ceiling function. Some use the floor function and others add or subtract a constant. There's not a great deal of introductory information out there about these sorts of sequences. You find yourself in deep mathematical matters very quickly once you start to explore the topic. 

Here is what Google's Bard had to say about them:

Pisot sequences are a type of infinite sequence of real numbers that have a number of interesting and useful properties. They are named after the French mathematician Charles Pisot, who first studied them in the 1930s.

Simple examples of Pisot sequences include:

• The Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
• The Lucas sequence: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...
• The Parry sequence: 0.1101001000101101...

Pisot sequences are important because they have a number of unique properties. For example:

• They are all irrational numbers.
• They are all aperiodic (meaning that they never repeat themselves exactly).
• They are all dense in the real numbers (meaning that between any two real numbers, there is always a Pisot number).

Pisot sequences are connected to Pisot numbers and Salem numbers in the following way:

• A Pisot number is a real number that is greater than 1 and has the property that all of its conjugates are less than 1.
• A Salem number is a real number that is greater than 1 and has the property that all of its conjugates are either less than 1 or equal to 1.

Every Pisot number is the limit of a Pisot sequence, and every Pisot sequence converges to a Pisot number. Salem numbers are a special type of Pisot number.

Here are some of the applications of Pisot sequences:

• They can be used to generate random numbers.
• They can be used to model complex systems, such as the growth of populations and the spread of diseases.
• They can be used to design efficient algorithms for tasks such as sorting and searching.
• Pisot sequences are a fascinating and important area of mathematics, and they have a wide range of applications in other fields.

Tug of War

 Here is an interesting problem that I came across on this site:

  

The Robot Weightlifting World Championship was such a huge success that the organisers have hired you to help design its sequel: a Robot Tug-of-War Competition!

In each one-on-one matchup, two robots are tied together with a rope. The centre of the rope has a marker that begins above position 0 on the ground. The robots then alternate pulling on the rope. The first robot pulls in the positive direction towards 1; the second robot pulls in the negative direction towards -1. Each pull moves the marker a uniformly random draw from [0, 1] towards the pulling robot. If the marker first leaves the interval [‑½, ½] past ½, the first robot wins. If instead it first leaves the interval past -½, the second robot wins.

However, the organisers quickly noticed that the robot going second is at a disadvantage. They want to handicap the first robot by changing the initial position of the marker on the rope to be at some negative real number. Your job is to compute the position of the marker that makes each matchup a 50–50 competition between the robots. Find this position to seven significant digits-the integrity of the Robot Tug-of-War Competition hangs in the balance!

I managed to come up with the following program after experimentation with different starting values.

Figure 1: source

I found that a starting value of about -0.285 produced a 50-50 result on average, which is what the person who posed the problem found. See Figure 1. I don't know why an accuracy of seven significant figures was required and I certainly wasn't going to strive for that level of accuracy. In any case, my result was certainly close enough.

Generally the tug-of-war doesn't last long, only one or two randomisations. Figure 2 shows the results for an unusually lengthy match that ended in a win for Robot 1:

Figure 2: permalink

So far this post has been more about programming than mathematics but I was interested in how a number like 0.285 emerges from a problem like this. My result of -0.285 was purely empirical. It turns out that the solution is  the result of evaluating the following expression:$$ \arcsin \left (\frac{\sin(0.5)+\frac{\pi}{4}}{2} \right )-\frac{\pi}{4}$$Now that is interesting and the derivation of this result is explained on this site and reproduced below (where p stands for probability):

In order to find the starting position of the tug-of-war to make a fair fight, we define the function \(f\) on [-0.5, 0.5] as $$f(x) = \text{ p(Player 1 wins at a starting position of } x)$$The symmetry of the game implies $$ \begin{align} f(x) &= \text{ p(Player 1 wins on first move) } + \int_x^{½} \! \text{p(Player 2 wins at position }(-y)) \text{ d}y \\
&= (½ + x) + \int_x^{½}(1 - f(-y) ) \text{ d}y \end{align}$$Differentiating and applying the fundamental theorem of calculus, we get:

\( f’(x) = 1 - (1 - f(-x)) = f(-x)\)

Differentiating again and employing the chain rule, and then substituting the equation above, we get:

\( f’’(x) = f’(-x) \times (-1) = -f’(-x)= -f(x) \) 

 

The general solution to this differential equation is 

 

\(f(x) = A \sin(x) + B \cos(x) \)

We need two boundary conditions to determine \(f\) exactly. First, it’s clear we must have \(f(½) = 1\). Second, from the above formula, \(f’(0) = f(0)\). Therefore
$$ \begin{align} A \sin(½) + B \cos(½) &= 1 \text{ and}\\
A \cos(0)- B \sin(0) &= A \sin(0) + B \cos(0) \end{align}$$The second equation implies \(A = B\), and the first equation then gives:$$\begin{align}A &= B\\ &= \frac{ 1} {\sin(½) + \cos(½)} \text{ and so}\\ f(x) &= \frac {\sin(x) + \cos(x)}{\sin(½) + \cos(½)} \end{align}$$Therefore the answer is the solution to: $$ \frac{\sin(x) + \cos(x)}{\sin(½) + \cos(½)} = ½ \text{ on }[-½,0]$$ A calculator can give this to the desired accuracy, -0.2850001…, or by using $$\sin(x) + \cos(x) = \sqrt{2}· \sin(x + \pi/4)$$we can exactly solve that the answer is$$ \arcsin \left (\frac{\sin(0.5+\frac{\pi}{4}}{2} \right )-\frac{\pi}{4}$$I don't fully understand this explanation but I'm exhausted from fine tuning the LaTeX so I'll return to it later.

On the Randomness of Pi's Digits

Much has been written about the randomness of the \(\pi\)'s digits but usually in the context of the decimal number system. Looking at \(\pi\) in terms of the binary number system however, introduces a simplification that can be exploited to investigate its randomness.

The first ten decimal digits of \(\pi\) are 3.141592654 which is represented in binary as:

11.00100100001111110110101010001000100

SageMathCell enables us to examine the first one million decimal digits of \(\pi\), convert these to binary and then graph the cumulative balance between the number of 0's and 1's. The first two 1's are ignored and only the 0's and 1's following the decimal point are considered. Figure 1 shows the result:

Figure 1

Figure 2 shows the code that I used to generate this graph:

Figure 2: permalink

How does this graph compare to that of a sequence of randomly generated 0's and 1's? It's easy enough to undertake this comparison. To this end, I looked at a string of three million randomly generated 0's and 1's because this is approximately the number of binary digits resulting from the conversion of one million decimal digits. The result is shown in Figure 3. Of course, successive repetitions of this algorithm will produce different graphs whereas the graph for \(\pi\) will be always the same. However, it's the general form of the two graphs that I want to compare.

Figure 3: permalink

Figure 4 shows the code that was used to produce this result.

Figure 4: permalink

Not surprisingly, the form of the two graphs is very similar. The point of the exercise is that the conversion of \(\pi\) to binary digits provides an easy visual comparison of its digits with randomly generated 0's and 1's.

ADDENDUM: March 17th 2021

There are of course many interesting facts concerning \(\pi\). Here are some of them:

• The number pi is literally infinitely long. But the number 123456 doesn’t appear anywhere in the first million digits of \( \pi \). It is a bit shocking because if a million digits of \( \pi \) don’t have the sequence 124356, it definitely is the most unique number. Source.
  
  
• Did you know there is actually an entire language based entirely on \( \pi\)? Called Pilish, the numbers of letters in successive words match the digits in \(\pi\). Mike Keith, a devoted Pilish-lover, even wrote an entire book in Pilish called "Not a Wake." The rules of the language and its variants are described here.
  
  
• Rivers bend to \( \pi\): The way a river meanders is described by its sinuosity; the length of its winding path divided by the distance from the source to the ocean as measured in a straight line. Strange as it may be, the average river has a sinuosity of around 3.14, according to the journal Science. Source.

If you hold a mirror to a circle, it looks like a circle. If you hold a mirror up to 3.14, it spells PIE! See Figure 2.

Figure 2: source

Someone has developed a search engine that can be used to find digit sequences in \( \pi \) in the first \(2 \times 10^0 \) digits of \pi. Figure 3 shows the output if 123456789 is input.

Figure 3

Pressing the next link bring brings up what is shown in Figure 4:

Figure 4

      

The site can also be used to find positions of e, \(\sqrt{2} \) and \(\phi\) where SageMath for example struggles with one million decimal places.

Here is a GeoGebra link that will allows the user to use a slider to display decimal places of \(\pi\).

Lotto Simulations

I've written about Lotto before in this post (Oz Lotto) and another (Losing at Lotto). The current post is not about probabilities but simulation. How can we use SageMath to simulate a lottery draw? Well as it turns out it's not too difficult.

The key is to use the ZZ.random_element(lowerbound, upperbound+1) function as in the following code. The trick is not to allow duplicate numbers and that is the reason for the inclusion of Set. This function takes our lotto list which might look like this the list [20, 37, 6, 37, 1, 19, 16] and turns it, after the sort, into the ordered set {1, 6, 16, 19, 20, 37}.

Here is the code I developed. I'm really just a tyro at both Python and SageMath so there may well be much better ways to achieve my goals but this is what I came up with:

# Generate a set of numbers for lotto games
# let N represent how many numbers are required in the game
# let G represent the number of games
# let U represent the upper bound of numbers
G=8
N=7
U=40
for i in range(G):
    lotto=[]
    while len(Set(lotto))<N:
        lotto.append(ZZ.random_element(1,U+1))
    print sorted(Set(lotto))

The following is an example of the output:

[11, 23, 27, 30, 37, 38, 40]
[4, 7, 8, 15, 20, 29, 38]
[8, 9, 13, 14, 21, 28, 36]
[7, 11, 15, 21, 28, 33, 40]
[1, 15, 17, 18, 28, 33, 39]
[4, 7, 11, 14, 18, 29, 32]
[1, 10, 12, 16, 21, 31, 33]
[2, 7, 8, 12, 13, 19, 27]

How really random this output is I don't know. I'm sure SageMath has other ways to generate more truly random numbers but this is sufficient for the modest purposes of the exercise.

The code has the added advantage of being able to accommodate "fixed" numbers. For example, let's say we always want the numbers 23 and 32 included in the output. All that needs to be done is to start with lotto = [23, 32] instead of it being an empty list.

For example:

# Generate a set of numbers for lotto games
# let N represent how many numbers are required in the game
# let G represent the number of games
# let U represent the upper bound of numbers
G=8
N=7
U=40
for i in range(G):
    lotto=[23, 32]
    while len(Set(lotto))<N:
        lotto.append(ZZ.random_element(1,U+1))
    print sorted(Set(lotto))

Here an example of the output:

[10, 11, 21, 23, 32, 35, 37]
[5, 6, 17, 23, 31, 32, 39]
[6, 11, 17, 23, 31, 32, 39]
[3, 15, 18, 23, 26, 30, 32]
[2, 12, 13, 23, 27, 28, 32]
[7, 18, 23, 26, 32, 35, 38]
[2, 11, 17, 19, 23, 32, 33]
[3, 16, 23, 26, 27, 31, 32] 

Not that I expect it will make any difference to my chances of winning but I'll test this out in some coming Lotto games. Oddly enough what got me thinking about generating some random lotto numbers was this article titled JERRY AND MARGE GO LARGE in the Huffington Post. It's about an American couple who exploited a feature in their state's lottery to make millions of dollars. It's quite an interesting story.

As I've been doing I'll include a SageMathCell with the code so that anyone curious can experiment: