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 →

The failures of political journalism

Howard Rudd

I've just watched a video of an interesting talk entitled ‘The failures of political journalism’ delivered by the journalist Helen Lewis on 29 May 2019 at a seminar organised by Oxford University's ‘Reuters Institute’. It can be seen on the institute's website and also on Youtube. The talk identified ‘seven deadly sins’ that political journalists perpetrated over the course of last two general elections and the two referendums. This article will first briefly discuss them then suggest some new ones. The sins are:

Read more →

Review of ‘Dangerous Hero: Corbyn's ruthless plot for power’, by Tom Bower

Howard Rudd

This book posits that the hard left plans to end democracy in Britain. Describing the aftermath of the 2015 Labour leadership election, Bower writes:

‘Commentators criticised Corbyn's ‘poverty of ambition’ for failing to win the political centre, but they misunderstood. As unwilling as ever to compromise, he planned to defeat the PLP, transform Labour into a genuinely Marxist party, and win sufficient electoral votes to become prime minister. Just the one victory would be enough. Thereafter, McDonnell boasted, their changes would be ‘irreversible’. [ … ] Just as Corbyn and McDonnell intended to revise the Labour Party's rules to permanently protect their coup from any challenge by social democrats, they would change the British constitution to cement their victory. The result of the second general election would be a foregone conclusion.’

This may seem like a paranoid conspiracy theory but by telling Jeremy Corbyn's life story Tom Bower tries to show that it isn't as paranoid as it sounds.

The book is a tabloid hatchet job, its nature given away by the large typeface. Throughout the book Bower regularly assumes the reader holds a number of conservative attitudes thereby potentially alienating readers who don't, probably the very ones he is most trying to convince, in whose minds those of the book's criticisms that are genuinely valid may be devalued. For example:

Read more →

Book review: ‘Fossil Capital: The Rise of Steam Power and the Roots of Global Warming’, by Andreas Malm.

Howard Rudd

When I bought this book I thought it was going to be a history of steam power in the textile industry in the eighteenth and nineteenth centuries. I was looking forward to reading about cross‑compound engines, Corliss valve gear, centrifugal governors and indicator diagrams.

When I opened it I was surprised to discover that it is, in fact, a sequel to Karl Marx’s Capital. It attempts to weave (no pun intended) the idea of fossil fuel into the fabric of Marx’s theory of class struggle. It aims to show that capitalism and fossil energy are so intimately connected that they cannot be separated, from which it follows, according to the author, that only the overthrow of capitalism can avert climate change.

The book is full of words and phrases that only Marxists use, such as ‘structural crisis’, ‘surplus value’, ‘historical process’, ‘commodity fetishism’, ‘primitive accumulation’, ‘subsumption of labour’, ‘property relations’ and even ‘bourgeois property relations’. The author appears to have a checklist of ideas from Das Kap and to be ticking them off one by one.

I should have guessed from its title that it would be something like this, in which case I wouldn’t have bought it. If you are tempted to buy it for the same reason as I was you now know everything you need to know about it and I will forgive you if you don’t read any further.

Read more →

What’s happening with Swansea Bay tidal lagoon?

Howard Rudd

Am I the only person who’s bemused about what’s happening to the Swansea Bay tidal lagoon? It looks like precisely nothing, though it would be just my luck for a deal to be announced five minutes after I post this article. If that happens, then don’t bother reading the rest!

As far back as July the FT reported that the project’s investors were warning that the delay in making a decision was putting the project at risk. According to Wales Online, a bunch of Swansea councillors met with Secretary of State for Business, Energy and Industrial Strategy Greg Clark on 30 October to urge him to speed things up, but two weeks later there have still been no announcements about what is happening. I wondered whether an announcement might have been made at the recent International Tidal Energy Summit earlier this week, but there’s still no news.

I don’t understand why the government couldn’t have given it a definitive unambiguous yes or no several years ago. But I have a theory, and here it is.

Read more →