ALMOST ODD RANDOM SUM-FREE SETS

NEIL J. CALKIN AND P. J. CAMERON

Abstract. We show that if S_{1} is a strongly complete sum-free set of positive integers, and if S_{0} is a finite sum-free set, then with positive probability a random sum-free set U contains S_{0} and is contained in S_{0} ∪ S_{1}. As a corollary we show that with positive probability, 2 is the only even element of a random sum-free set.

1. introduction

In this paper we shall extend the results of Cameron [5] and Calkin [1] on the structure of a random sum-free set.

A set S of positive integers is sum-free if there do not exist x, y, z ∈ S with x + y = z. We shall call a sum-free set ultimately complete if there exists n_{0} so that ∀n > n_{0}, n ∈ S ∪ (S + S), that is, every sufficiently large integer not in S is a sum of elements in S. We define

r_{S}(n) = |{x : x ≤ n, x, n − x ∈ S}|

to be the number of distinct representations of n as a sum of elements of S. If

lim_{n∉S} \frac{r_{S}(n)}{log(n)} → ∞

then we shall call S strongly complete. We note that there are no known examples of sum-free sets for which r_{S}(n) → ∞ but r_{S}(n)/n → 0: modular complete sum-free sets give rise to sets for which r_{S}(n) grows linearly.

Cameron [6] introduced a probability measure μ on the set S of all sum-free sets as follows: there is a natural bijection from the set 2IN to S which induces a probability measure on S. This measure corresponds to the following construction of a random sum-free set U: Set U = ∅: consider each integer n in order: if n ∈ U + U then increase n by one: if n ∉ U + U then toss a fair coin: if heads, then set U = U ∪ {n}, and increase n by one; otherwise increase n by one.

Observe that if S ⊂ {1, 2, 3, … n} is a finite sum-free set, then

Pr_{μ}(U ∩ {1, 2, 3, … n} = S) = 2^{−n+t}

where t = |(S + S) ∩ {1, 2, 3, … n}|, since we have to prescribe the outcome of a cointoss for exactly n − t integers.

2. The Main Result

Cameron [5] showed that if S is the sum-free set corresponding to a complete modular sum-free set (modulo m) then Pr(U ⊂ S) > 0, and Calkin [1] showed that if S is a strongly complete sum-free set then Pr(U ⊂ S) > 0. Cameron [6] asked whether the probability that a random sum-free set contains 2 and no other even element is positive. In this paper we prove a much stronger result, replacing 2 by an arbitrary finite sum-free set S_{0}, and the odd numbers by an arbitrary strongly complete sum-free set S_{1}.

Theorem 1. Let S_{1} be a strongly complete sum-free set: for any finite sum-free set S_{0}, Pr(S_{0} ⊂ U ⊂ S_{0} ∪ S_{1}) > 0.

In our proof we shall assume that the least element of S_{1} is at least twice as large as the largest element of S_{0}: this is not a severe restriction, since in particular it implies the theorem above. Proof: Our proof will require a probability measure ν on the set F of all sum-free sets lying between S_{0} and S_{0} ∪ S_{1}, defined in the following manner: set U = S_{0}, and consider the integers n ∈ S_{1} in order: if n ∈ U + S_{0}, move to the next n ∈ S_{1}; if n ∉ U + S_{0}, toss a coin: if it is heads, then set U = U ∪ {n} and move to the next n ∈ S_{1}; otherwise, move to the next n ∈ S_{1}.

In other words, we randomly construct a sum-free set U constrained to lie between S_{0} and S_{0} ∪ S_{1}: whenever we have a choice of whether to add an element to U we toss a coin to decide. Since the least element of S_{1} is greater than twice the largest element of S_{0}, and since S_{1} is sum-free, the only times we have to toss a coin correspond to values in S_{0} + S_{1}.

We shall denote by ν_{n} the measure obtained in this fashion after decisions have been made for all elements less than or equal to n. Then if F is an event, we define F_{n} = {F ∩ {1, 2, 3, …, n}|F ∈ F}. If F is the limit of F_{n} as n → ∞ (in the sense that F ∈ F if and only if F ∩ {1, 2, 3, …, n} ∈ F_{n} for all n, we have ν(F) = lim_{n→∞} ν_{n}(F_{n}).

In particular, if F is an event which depends only on elements less than or equal to n, then

ν(F) = ν_{m}(F_{m}) ∀m ≥ n

since all decisions about elements less than n have been made by this stage.

Observe that ν is not just the conditional measure given S_{0} ⊂ U ⊂ S_{0} ∪ S_{1}: in the conditional measure sets for which only a few elements of IN \ (S_{0} ∪ S_{1}) are not sums are weighted more heavily than those having many elements not excluded as sums, since the latter require more coin tosses: with ν this is not the case.

However, the measures μ and ν are related as follows:

Lemma 1. Let t_{n}(U) = |{1, 2, 3, …, n} \ (S_{0} ∪ S_{1} ∪ (U + U))| be the number of elements of {1, 2, 3, …, n} \ (S_{0} ∪ S_{1}) not represented as a sum in U, that is the number of extra coin-tosses used in the μ model over the ν model. Then

Pr_{μ}(S_{0} ⊂ U ⊂ S_{0} ∪ S_{1}) = lim_{n→∞} Pr_{μ_{n}}(S_{0} ⊂ U ∩ {1, 2, 3, …, n} ⊂ S_{0} ∪ S_{1})

= lim_{n→∞} ∑_{F ∈F_{n}} Pr_{ν_{n}}(U ∩ {1, 2, 3, …, n} = F)2^{−t_{n}(F)}

= lim_{n→∞} E_{ν_{n}}(2^{−t_{n}(U)}).

Proof: clear.

Hence, if we wish to show that Pr_{μ}(S_{0} ⊂ U ⊂ S_{0} ∪ S_{1}) > 0, it suffices to show that there exists a c > 0 so that for all n, E_{ν_{n}}(2^{−t_{n}(U)}) > c.

We shall now show that with positive (ν) probability, t_{n}(U) is bounded, independent of n; more specifically, we show that if n ∈ S_{1} + S_{1} then Pr_{ν_{n}}(n ∉ U + U) is small; in fact, that

∑_{n∈S_{1}+S_{1}} Pr_{ν_{n}}(n ∉ U + U) < ∞.

Then an effective version of Borel Cantelli will give us our result: indeed, if n_{0} is such that

∑_{n∈S_{1}+S_{1},n>n_{0}} Pr_{ν_{n}}(n ∉ U + U) < 1 − ϵ,

then

Pr_{ν_{n}}(n ∉ U + U∀n ∈ S_{1} + S_{1}, n > n_{0}) > ϵ,

and hence

E(2^{−t_{n}(U)}) > ϵ2^{−n_{0}} > 0,

and our proof will be complete.

Let the largest element of S_{0} be k, and set t = ⌈r_{S}(n)/(k + 1)⌉ − 1. Then we have Lemma 2.

Pr_{ν_{n}}(n ∉ U + U) ≤ (1 − 2^{−2(2k+1)})^{t}

Proof: Since we have r_{S}(n) pairs x, y ∈ S with x ≤ y, x + y = n, we can find x_{1}, x_{2}, x_{3}, …, x_{t}, y_{1}, y_{2}, y_{3}, … y_{t} with x_{i} + y_{i} = n and x_{i+1} − x_{i} > k, y_{t} − x_{t} > k: indeed, just pick every (k + 1)st pair and discard the pair closest to n/2.

The key here is that if we force x_{i} − k, x_{i} − k + 1, …, x_{i} − 2, x_{i} − 1, x_{i} + 1, x_{i} + 2, …, x_{i} +k −1, x_{i} +k to be omitted from U (requiring at most 2k coin tosses to be specified) then the other elements of U have no impact on whether x_{i} is included in U: moreover, whether or not x_{i} ∈ U has no impact on other elements of U.

Now let X_{i} be 1 if x_{i} ∈ U and x_{i} − k, x_{i} − k + 1, …, x_{i} − 2, x_{i} − 1, x_{i} + 1, x_{i} + 2, …, x_{i} + k − 1, x_{i} + k ∉ U, and 0 otherwise, and define Y_{i} similarly. Then

Pr_{ν_{n}}(X_{i} = 1|X_{1}, X_{2}, …, X_{i−1}, X_{i+1}, …, X_{t}, Y_{i}, Y_{2}, … Y_{t}) ≥ 2^{−(2k+1)}

and similarly for Y_{i}. Since n ∉ U + U can only happen if for each i, at least one of X_{i}, Y_{i} is equal to 0, we have

Pr_{ν_{n}}(X_{1}Y_{1} = 0) ≤ (1 − 2^{−(2k+1)})
Pr_{ν_{n}}(X_{2}Y_{2} = 0|X_{1}Y_{1} = 0) ≤ (1 − 2^{−(2k+1)})
.
.
.
Pr_{ν_{n}}(X_{t}Y_{t} = 0|X_{1}Y_{1} = 0, … X_{t−1}Y_{t−1} = 0) ≤ (1 − 2^{−(2k+1)})

and hence

Pr_{ν_{n}}(n ∉ U + U) ≤ Pr_{ν_{n}}(X_{1}Y_{1} = 0, X_{2}Y_{2} = 0, …, X_{t}Y_{t} = 0)
≤ (1 − 2^{−(2k+1)})^{t},

completing the proof of the lemma.

Since S_{1} is strongly complete,

∑_{n∈S_{1}+S_{1}} ((1 − 2^{−2(2k+1)})^{1/(k+1)})^{r_{S}(n)} < ∞

and the proof of the theorem is complete.

We note that everything above is for a fair coin: however, the statement remains true for a coin with probability p of heads, and 1 − p of tails, so long as p is strictly between 0 and 1: we omit the proof, as it is essentially the same as the above.

We also note that the proof of the theorem gives us a way to estimate the probability that S_{0} ⊂ U ⊂ S_{0} ∪ S_{1} rather more effectively than by randomly generating sum-free sets with respect to the measure μ and counting the proportion that have the desired property, namely by generating with respect to the measure ν and estimating the expected value of the random variable 2^{−t_{n}(U)}. Computer simulations of this type suggest that the probability that a random sum-free set contains the element 2 and no other even element is about 0.00016.

3. Further Questions

1. It is natural to ask now whether this theorem covers almost all sum-free sets, that is, is it true that with probability 1, a random sum-free set is only finitely far from being contained in a strongly sum-free sum-free set?

2. One candidate for showing that the answer to Question 1 is false is the following: for α ∈ (0, 1) \ lQ, define S_{α} = \{n|\{nα\} ∈ (\frac{1}{3}, \frac{2}{3})\} where \{x\} denotes the fractional part of x. Calkin and Erdös [2] have shown that for each irrational α, S_{α} is incomplete. What is

Pr_{μ}(U ⊂ S_{α} for some α ∈ (0, 1) \ lQ)?

3. An old conjecture of Dickson [7] is equivalent to the following: if S is complete then S is ultimately periodic (i.e. there is a period m and an n_{0} so that from n_{0}, S consists of exactly the same elements modulo m): this would imply that r_{S}(n) has linear growth or has a bounded subsequence. There is evidence that Dickson’s conjecture may be false [4, 3]: if so, do there exist sets with r_{S}(n) → ∞ but r_{S}(n)/n → 0?

4. If we construct a random sum-free set using a coin with bias p, we have a new measure Pr_{μ,p} on the set of all sum-free sets. Let Odd denote the set of all subsets of the odd numbers: is it true that Pr_{μ,p}(Odd) is increasing in p? Given a pair S_{0}, S_{1} of sum-free sets, with S_{0} finite and S_{1} strongly complete, for which value of p is Pr_{μ,p}(S_{0} ⊂ U ⊂ S_{0} ∪ S_{1}) maximized? It is clear that if S_{0} is non-empty then the limiting value of this probability as p tends to 0 or 1 is 0 (since if p is small, so is the probability that we include the elements of S_{0}, and as p tends to 1, the probability that U is contained in the odd numbers tends to 1).

5. It follows from the methods in this paper that, conditioned on the only even element being 2, a random sum-free set almost surely has density 1/6. Moreover, in the case where S_{1} comes from a modular complete sum-free set, the limiting density exists and is rational. Is it true that almost surely a random sum-free set (constructed with a fair coin) has a limiting density? If so, must the density be rational?

References

[1] Neil J. Calkin. On the structure of a random sum-free set. To appear.

[2] Neil J. Calkin and P. Erdös. On a class of aperiodic sum-free sets. To appear.

[3] Neil J. Calkin and Steven R. Finch. Difference densities of sum-free sets. In preparation.

[4] Neil J. Calkin and Steven R. Finch. Necessary and sufficient conditions for periodicity of sum-free sets. In preparation.

[5] P. J. Cameron. On the structure of a random sum-free set. Probability Theory and Related Fields, 76(4):523–531, 1987.

[6] P. J. Cameron. Portrait of a typical sum-free set. In C. Whitehead, editor, Surveys in Combinatorics 1987, volume 123 of London Mathematical Society Lecture Notes, pages 13–42. Cambridge University Press, 1987.

[7] Richard K. Guy. Unsolved Problems in Number Theory. Springer Verlag, 1981. Problem E32.

School Of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332

   E-mail address: calkin@math.gatech.edu

School of Mathematical Sciences, Queen Mary and Westfield College, Mile End Road, London, E1 4NS

   E-mail address: P.J.Cameron@qmw.ac.uk