## Hull and Dobell’s first theorem

$$\require{cancel}$$

One of the most widely used types of pseudo-random number generator is the linear congruential sequence. These are defined by recurrence relations of the form $$\label{eq:genrandnum_hull_dobell_01} x_{i+1} \ \equiv \ ax_{i} + c \quad (\operatorname{mod} m)$$ where all the terms are non-negative integers. The usual terminology is that $$a$$ is called the ‘multiplier’, $$c$$ the ‘increment’ and $$m$$ the ‘modulus’.

Any such sequence must be periodic since it contains at most $$m$$ different numbers each of which is determined only by its predecessor. The period can therefore never exceed $$m$$ but even that cannot be guaranteed. A long period is necessary but not sufficient for good pseudo-randomness, so it is important to understand the conditions that determine its length.

That is the objective of a paper published in 1962 by T. E. Hull and A. R. Dobell (Hull and Dobell, 1962). If you have read anything about the subject you have probably heard of something commonly referred to as ‘the Hull-Dobell theorem’. The paper actually presents two theorems, but it seems that only the first gets called ‘the’.

Considering them in reverse order, the second theorem is about sequences where $$c = 0$$, i.e. ‘multiplicative’ ones. It makes use of some quite advanced number-theoretical concepts and even Hull and Dobell admit that:

‘The basic theorem for the multiplicative congruential methods is more complicated and more difficult than for the mixed congruential methods.’
for which reason they present only a condensed proof, referring the reader to textbooks to flesh out the details.

The first theorem, on the other hand, is not so difficult, and Hull and Dobell present their proof in full. This theorem is about sequences where $$c \neq 0$$, which H&D refer to as ‘mixed’. The theorem says that, in that case, a period of length $$m$$ is achievable and will occur if:

1. $$c$$ and $$m$$ are coprime,

2. all the prime factors of $$m$$ divide $$a-1$$ and

3. if 4 divides $$m$$, then 4 divides $$a-1$$.

The proof, despite what H&D say, is not easy to follow, and their paper is a classic of ‘proof by intimidation’. Unpacking all the ‘it is easy to show that’s and all the ‘obviously’s took me weeks. I therefore thought I’d post my workings in case there is anyone out there who might like to see them. Maybe I might attempt the second theorem at some point in the future.

## But what exactly is $$i$$ really?

Most books and courses on complex numbers introduce the mysterious square root of minus one by assigning it a symbol, usually but not always the letter $$i$$, and then use it in calculations as if it were any other number. They make no attempt to explain what $$i$$ ‘really is’ and assume that once the student has done enough calculations with it they will forget any metaphysical angst they may originally have had. This could be likened to the attitude in certain branches of physics that has been caricatured as ‘shut up and calculate’. For example in 1831 the great Carl Friedrich Gauss, after initially worrying about ‘the true metaphysics of the square root of $$-1$$’, wrote:

If one formerly contemplated this subject from a false point of view and therefore found a mysterious darkness, this is in large part attributable to clumsy terminology. Had one not called $$+1$$, $$-1$$ and $$\sqrt{-1}$$ positive, negative and imaginary (or even impossible) units but instead, say, direct, inverse, or lateral units, then there could scarcely have been talk of such darkness.

This is just brushing the problem under the carpet. Calling it a ‘lateral unit’ merely renames it without providing any insight, and no matter how familiar you are with its use, as soon as someone asks you what $$i$$ really is you will realise you still don’t know. Some books answer this question by saying that a complex number is ‘really’ just a two-dimensional vector but that is only a partial explanation and technically not even that. Fortunately it is possible to give a satisfactory answer to this question. This article explains how.