Mathematics

Hull and Dobell’s first theorem

Howard Rudd
\(\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 \begin{equation}\label{eq:genrandnum_hull_dobell_01} x_{i+1} \ \equiv \ ax_{i} + c \quad (\operatorname{mod} m) \end{equation} 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.

Read more →

But what exactly is \(i\) really?

Howard Rudd

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.

Read more →

The mathematics of lockdowns

Howard Rudd

During the pandemic the death rate per 100,000 of population has varied widely between countries. For example at the time of writing the UK's rate is 72.51 while Germany's is 13.40, a factor of 5 smaller despite the two countries being superficially similar in other ways (https://en.wikipedia.org/wiki/COVID-19_pandemic_death_rates_by_country, snapshot at time of writing: https://en.wikipedia.org/w/index.php?title=COVID-19_pandemic_death_rates_by_country&oldid=985851183).

There are obviously many things that the UK and Germany did differently but the media have particularly focused on the fact that Germany locked down earlier than the UK. Coronavirus was first confirmed in Germany on January 27 and they locked down on March 13, a period of 46 days, whereas the first two cases in the UK were confirmed on January 31 and lockdown began on March 23, a period of 52 days, six days later than in Germany.

This doesn't seem like a huge difference. Could it really be that locking down a mere six days earlier could have reduced the UK's death rate by four fifths? This article attempts to answer this question. To do so requires only simple school-level maths.

Read more →