Another sum-free set problem

Last week I posted a periodicity problem about sum-free sets. This is only one of a sheaf of unanswered questions about these objects. Here is another. You may want to look back to the earlier post for the method of constructing a random sum-free set. In brief: consider the natural numbers in turn; if the number considered is the sum of two numbers already included, then it must be excluded; otherwise toss a fair coin to decide whether to include it or not.

The density of a set S of natural numbers is defined to be the limit, as n tends to infinity, of the proportion of the numbers in {1,…,n} which belong to S (if this limit exists). The Law of Large Numbers says that, if we choose a set of random natural numbers by tossing a fair coin without the sum-free constraint, then almost surely its density will be 1/2 (that is, the probability that the density either fails to exist or is not equal to 1/2 is zero). The first of today’s questions is:

Does the density of a random sum-free set exist almost surely?

For the rest of this post I will assume that the answer is “yes”. (Otherwise, the questions can be modified to take account of this, but become less simple to state.) Now the next (and main) question is:

What is the distribution of the density (as a random variable on the space of sum-free sets?

The answer is much more complicated than in the case without constraint. I mentioned in the last post that the probability that S consists entirely of odd numbers is about 0.218. Conditioned on this, the density is almost surely 1/4. So the density has a point mass of 0.218 at the point 1/4.

There is a heuristic explanation of this. Suppose that, by chance, we have chosen a fairly long initial segment of S, and have not yet seen any even numbers. Then the odd numbers in S are unconstrained – each was determined by the coin coming down heads – so we will have picked close to 1/2 of the odd numbers with high probability, by the Law of Large Numbers. What happens next? Since the odd numbers are unconstrained, there is a high probability that the next even number we look at will be excluded because it is the sum of two odd numbers in the set; but the next odd number is still unconstrained. So the pattern of odd numbers, once established, tends to continue.

This argument (made rigorous) can be generalised. It applies if the odd numbers are replaced by the numbers congruent to 2 or 3 mod 5, or 1 or 4 mod 5, or various other cases. More precisely, let T be a subset of Zn, the integers mod n. Say that T is complete sum-free if

  • it is sum-free (in Zn); and
  • any element of Zn not in T is the sum of two elements of T.

Now if T is complete sum-free, then the probability that a random sum-free set is contained in the congruence classes in T is non-zero, and conditioned on this, its density is almost surely |T|/2n.

This gives infinitely many point masses in the density distribution. We know that the largest is at 1/4, and the next largest at 1/5; it is thought that they occur at discrete points (with gaps between them) above 1/6, though this has not been proved. Below 1/6, we don’t really know what happens.

We do know that these mass points do not account for everything. Neil Calkin and I proved that the event that the random sum-free set contains 2 but no other even number is non-zero (though very small). Such sets can have positive density, though calculating the conditional distribution is harder since there is no single largest set containing all of them. More generally, sets that differ only finitely from a subset of a complete sum-free set have positive probability.

The main question I would like to pose is: does the density distribution have a continuous part below 1/6? I had some hope of finding that it did, given a simple construction of Paul Erdős. If α is an irrational number, then the set of numbers n for which the fractional part of nα lies between 1/3 and 2/3 is always sum-free. Of course, such a set has density 1/3, and so we would expect a random subset of it to have density 1/6. Encouraged by this, I discovered a similar family of sum-free sets whose density varies continuously. Unfortunately, these contribute only a null set to the probability space, and don’t show up in the density spectrum.

At various times, I have done computer experiments on this. Here is a picture of an approximation to the density distribution.

Density spectrum

Density spectrum for random sum-free set

This picture was obtained by choosing many random sum-free subsets of {1,…,105} and plotting the density of each on the picture. This is like using a spectrograph; the longer you are prepared to watch, the sharper the picture becomes. The sets which will contribute to the masses at 1/4 and 1/5 are clearly visible; the next one, 3/16 (corresponding to sets contained in complete sum-free sets {3,4,5} mod 8 or {1,4,7} mod 8), is beginning to take shape. It is also clear that a significant change occurs at 1/6, but of course no such picture will distinguish between discrete (but dense) and continuous!

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems. Bookmark the permalink.

1 Response to Another sum-free set problem

  1. Pingback: Question: Maximal density for incomplete sum-free partitions? « Number Bunching

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.