When Roots are Random

Good random number generators are hard to come by. However, a famous conjecture states that there are actually an infinite number of perfect random number generators right at our doorstep: Recall that an algebraic number is a complex number that is a root of a polynomial with integer coefficients. The conjecture states that the sequence of digits of any irrational algebraic number is random (regardless of the base of the number system we use: binary, decimal, whatever).

Unfortunately, the current state of number theory is not advanced enough for a proof of the conjecture to be within reach in the forseeable future.

In this project, we will consider the possibility of the randomness of algebraic numbers from a practical perspective: Even if the conjecture holds true, randomness is an asymptotic phenomenon, and it will be completely useless if the randomness of a number first becomes apparent after, say, $10^{10^{10}}$ of its digits -- we need it to appear quickly.

Thus, it is necessary to compile statistics of the first many blocks of digits of algebraic numbers. This requires fast algorithms for computing roots of polynomials and clever implementations of these.

To focus our efforts, we will consider only a class of numbers thought quite likely to exhibit random behaviour: The Pisot numbers -- roots of monic integer polynomials that are greater than one, and whose conjugate roots all have absolute value strictly less than one (famous Pisot numbers are the Golden Number $(1+\sqrt{5})/2$ and the socalled Plastic Constant).

The project is of a highly experimental nature, and it is the first of its kind -- students who succesfully complete the project can boast of having performed the first experimental study of the distribution of digits in Pisot numbers; a project report of sterling quality could conceivably lead to a publishable paper in a reputable journal.

An ideal project should:

• Implement, in $C\makebox[1.5ex]{+}\makebox[1.5ex]{+}{}$, a new algorithm due to Gupta and Mittal [2,3] for computation of the root of an integer polynomials having largest absolute value among the roots.

• Compare said algorithm with the state-of-the-art implementation of similar methods from standard linear algebra packages (that are mostly based on floating point arithmetic as opposed to the Gupta/Mittal integer-based algorithms).

• Use the most efficient of the above methods to generate as many digits of chosen Pisot numbers as possible within a reasonable time frame.

• Compile statistics of the blocks of digits in Pisot numbers attesting their (possible lack of) usefulness as random number generators.

• Provide a brief introduction to Pisot numbers, random digit expansions, and the employed root-finding algorithms; good sources are [4,1,5]