A sum-free set problem

My post on Isbell’s conjecture produced some interesting reactions. So I will try to put up other hard unsolved problems here from time to time, when I have nothing better to do. (As if …)

Here is a problem about sum-free sets of natural numbers.

Background: a set S of natural numbers can equally well be described by a sequence of zeros and ones, whose nth entry is 1 if n is in S, and 0 otherwise. Thus, the sequence corresponding to the set of odd numbers is 101010101… (In this posting, the natural numbers start at 1.)

A set S of natural numbers is sum-free if, whenever x and y belong to S, their sum x+y does not belong to S. Note that x and y are allowed to be equal here.

Suppose that I have a fair coin. I can generate a random sum-free set in the following way. Go through the natural numbers in turn. While considering the number n, check to see whether n=x+y, where we already put x and y into the set. If so, then we must leave it out; if not, we toss the coin and put n into the set if the coin comes down heads, or leave it out otherwise.

For example, if the first four tosses are heads, tails, heads and heads, the
corresponding set S begins like this:

  • first toss heads, so put 1 into S;
  • 2=1+1, so leave out 2;
  • next toss tails, so leave out 3;
  • next toss heads, so put in 4;
  • 5=4+1, so leave out 5;
  • next toss heads, so put in 6;
  • 7=6+1, so leave out 7;
  • 8=4+4, so leave out 8.

My first theorem about sum-free sets is that this procedure will, with positive probability, generate a set consisting entirely of odd numbers. The probability of this happening is about 0.218, but we don’t know it very accurately, and don’t know what kind of number it is (rational, algebraic or transcendental).

Now reconsider this procedure. It doesn’t really matter that we are tossing a fair coin; the output is a sum-free set, no matter what sequence the coin gives us. For example, if the coin always comes down heads, then we generate the set of odd numbers (each even number is the sum of two preceding odd numbers, so is out; each odd number is in since the coin comes down heads).

So what we have is a procedure which takes as input a sequence of 0s and 1s, and produces as output a sum-free set, or (if you prefer) a sequence of 0s and 1s corresponding to a sum-free set (that is, never having 1s in positions x, y and n where n=x+y.

It is known that, if such a transformation can be computed by a finite-state machine, then it must map eventually periodic sequences to eventually periodic sequences. However, the property of being sum-free involves long-range effects, and seems like it should not be computable by a finite-state machine. So we could ask the question:

Problem: Does our “sum-free set machine”, run on an eventually periodic input, produce an eventually periodic output?

A special case of the problem is:

Problem: Does our “sum-free set machine”, run on an input which is eventually all-1 (i.e. has only finitely many 0s), produce an eventually periodic output?

The special problem asks: Suppose that, after a finite number of coin tosses, the coin malfunctions and always comes down heads. Is the output sequence eventually periodic?

Here are two examples.

  • If the coin first comes down tails, and then always heads, it generates the set consisting of numbers congruent to 2 or 3 mod 5; that is, the machine turns 0111111… to 011000110001100…
  • If the coin generates heads and tails alternately (beginning with heads), it generates the set of numbers congruent to 1 mod 3; that is, the machine turns 1010101… into 1001001001…

Now it can be shown that the converse of our problem is true; that is, if the output of the machine is ultimately periodic, then the input producing it must have been ultimately periodic. Also, there is a simple test which can be applied to check the periodicity (in other words, to guarantee after a finite amount of checking, that the observed periodicity of the output will continue for ever).

But the question itself, even in the special case, remains unanswered. Neil Calkin discovered that, if we feed in the input which begins 10010 and repeats with period 5, then we can track the output for tens of thousands of cycles and not discover periodicity!

In fact, we see fascinating patterns form and dissolve as the machine continues its operation. Here, for reference, are the sizes of the first few gaps between consecutive 1s in the output:

3, 2, 5, 3, 5, 5, 6, 2, 6, 2, 6, 5, 8, 5, 9, 6, 5, 9, 11, 6, 5, 3, 8, 9, 9, 2, 8, 3, 6, 5, 14, 6, 12, 6, 21, 5, 6, 5, 12, 11, 9, 9, 10, 10, 16, 5, 21, 9, 9, 5, 25, 11, 10, 14, 9, 6, 11, 19, 11, 6, 12, 8, 12, 9, 18, 9, 15, 5, 9, 18, 9, 8, 16, 5, 9, 5, 12, 12, 18, 15, 6, 8, 9, 5, 15, 3, 14, 9, 12, 9, 15, 12, 18, 5, 9, 12, 18, 12, 9, 5, 15, 15, 9, 11, 15, 9, 9, 12, 12, 5, 18, 9, 9, 8, 12, 15, 15, 6, 14, 9, 9, 12, 21, 5, 12, 12, 19, 5, 15, 18, 9, 9, 18, 6, 11, 12, 12, 5, 15, 9, 15, 12, 15, 3, 14, 9, 12, 12, 24, 9, 12, 5, 12, 9, 21, 9, 12, 5, 15, 12, 15, 9, 18, 9, 8, 6, 15, 5, 9, 12, 15, 5, 12, 12, 18, 9, 8, 6

We badly need a new idea!

Advertisements

About Peter Cameron

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

2 Responses to A sum-free set problem

  1. Pingback: Another sum-free set problem « Peter Cameron's Blog

  2. This post was great.

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.