Clive Sinclair

Yesterday I read the news that Clive Sinclair has died. This brought back memories of my first encounter with personal computers nearly 40 years ago.

At the time I had a demanding job and three small children, and I was not going to get something like a Commodore PET as some of my colleagues did. Instead, I started on a Sinclair ZX Spectrum in 1982 or 1983.

The machine had a laughably small amount of memory by today’s standard: 16Kb ROM, 48Kb RAM (of which nearly 7Kb were taken up by screen memory and printer buffer, leaving only 41Kb for the user). The machine had its own version of BASIC built-in, with keywords available by a single keypress. But it used a Z80 processor, a variant of the Intel 8080, so with a list of Z80 opcodes it was possible to program it in machine code, by writing a BASIC program to put the appropriate values into memory and then call the code; it was even possible to return a value.

So I used it to prove a theorem.

Suppose that you choose a sum-free set S of natural numbers by the following random procedure. Examine the natural numbers in turn. When examining n, if it happens that n = x+y where x and y have already been put into S, then obviously n cannot be in S; otherwise, choose randomly and independently with probability 1/2 whether to put n into S or not.

This is a fascinating process with many curious properties. It is very easy to see that the probability that no odd number is ever put into S is zero. (If no odd number has so far been put into S, then the next odd number to be examined will have even chance of being put into S.) What about even numbers?

Theorem In the above process, the probability of the event that S contains no even numbers is non-zero.

In fact this probability is about 0.218.

So how does the proof go? Let p_n be the probability that no even number occurs when the numbers 1,…,n have been considered; then the sequence (p_n) is decreasing, and the probability p that there are no even numbers in the final set is its limit. Now there is a simple upper bound for p_n−p, so if we can find a value of n for which p_n exceeds this bound then the theorem is proved. The value of p_n for n even can be computed by finding, for all sets of odd numbers in [1,…,n], the probability of obtaining this set as the initial part of S; a simple sum over 2^n/2 subsets. A slow process, but just the job for the computer. With about a day’s computation on the Spectrum I was able to find a lower bound of about 0.21759 and an upper bound of about 0.21862 for this number.

At various times since, I have thought that it would be possible to get a more accurate estimate; computers today are faster, and the algorithm is easily parallelisable (the individual terms in the sum can be computed independently). But I never got round to it.

Using this, and a similar estimate for a kind of “cross-sum”, I was able to show that, if T is a complete sum-free set modulo m (that is, it is sum-free in the integers mod m, and every element of this quotient not in T is the sum of two elements in T), then the probability that a random sum-free set is contained in the union of congruence classes given by T is positive. (The class {1} modulo 2 is the first example of such a set.) So, unlike some of my favourite examples like the random graph, this measure space contains infinitely many “natural” pieces with positive probability.

And there is more. After a hectic week visiting Neil Calkin in Atlanta, during which we changed our mind several times about whether we were proving that it was zero or positive, we showed that sum-free sets in which 2 is the only even number have positive probability (though rather small). More generally, a set which belongs to T mod m (as above) with finitely many exceptions has positive probability. So there are more such pieces.

I’t like to advertise some open problems about this space, involving the density of a sum-free set (a random variable on the space).

• Does a sum-free set have a density with probability 1?
• Is it true that the spectrum of densities is discrete above 1/6?
• Does it have a continuous part below 1/6?

We think that the answers to the first two questions is “yes”, but are quite uncertain about the third.

By the end of the decade, I had moved to an Atari ST, which could store information on floppy discs. I was commuting from Oxford to London by then, and got a Tandy TRS-80 for writing on the train; I had to write a low-level program to connect it to the Atari, which involved learning about DTR and CTS and other mysteries of RS-232 to do this. By the following decade, though, all these things were obsolete and we were provided with PCs running some version of Windows, which crashed so often that as soon as I could get something better, I did.

But it was Clive Sinclair’s cheap and cheerful machine that got me into this.