28 December 2007

On the Mian-Chowla sequence

An interesting problem from Additive Combinatorics by Terence Tao and Van Vu. (This is almost a direct quote; I've modified it slightly in order to be able to render it entirely in HTML.)

Exercise 6.2.5. Let S = {1, 2, 4, 8, 13, 21, 31, ...} be the Sidon set of positive integers constructed by the greedy algorithm (this set is sometimes known as the Mian-Chowla sequence). Show that the kth element of S does not exceed (k-1)3 + 1, and hence the number of elements of S which are less than n is Ω(n1/3) as n goes to infinity.

A Sidon set, for those of you who don't know, is a set for which all the pairwise sums are distinct. Tao and Vu credit this result to Stöhr; see below. A rough translation of the title of that paper is "Solved and unsolved questions on bases of sequences of natural numbers", although my German isn't so good. (I've been looking for mathematics written in German, though, because my department requires me to be able to read two of mathematical French, German, and Russian -- I've already passed the French and I know a little German and no Russian -- so I might try to read this, or at least parts of it.)

First, an example of where these numbers are coming from. Let s1 = 1, s2 = 2, s3 = 4, and so on form the sequence S. Say we know the first four terms, s1 through s4, are 1, 2, 4, 8. Then 9 can't be in the sequence, because 9 + 1 = 8 + 2. 10 can't be in it, because 10 + 2 = 8 + 4. 11 can't be in it, because 11 + 1 = 8 + 4. And 12 can't be in it, because 12 + 4 = 8 + 8. But none of 13 + 1, 13 + 2, 13 + 4, and 13 + 8 are pairwise sums of {1, 2, 4, 8}, so the fifth term is 13. It turns out to be easier, I think, to think in terms of differences instead of sums; we say that 9 can't be in the sequence because 9 - 2 = 8 - 1, and so on. So if s1, ..., sk are known, we choose sk+1 to be the smallest integer N such that the intersection
\{ N-s_i \}_{1 \le i \le k} \cap \{ s_j - s_i \}_{1 \le i < j \le k}

is empty.

The solution is straightforward. Now, by the "greedy algorithm" it's meant that if we know s1 through sk, then sk+1 is the smallest integer greater than sk which doesn't violate the definition of our sequence. Then it's enough to minimize the difference tk = sk+1 - sk; this is the smallest positive integer which does not occur among pairwise differences of elements of {s1, ..., sk}. There are k(k-1)/2 such differences, and they're not necessarily distinct, so the smallest positive integer which doesn't occur is at most (k(k-1)/2) + 1, or ${k \choose 2} + 1$. Then the sk are just the partial sums of the tk, so we get
s_k \le 1 + \sum_{j=1}^k \left( {j \choose 2} + 1 \right) = {k+1 \choose 3} + k + 1

which is asymptotically equal to k3/6.

The same method gives a lower bound -- all the differences sk - si for i < k are distinct, so tk is at least k+1. This gives a lower bound for sk of order k2/2.

The continuation of the sequence can be found in the Encyclopedia of Integer Sequences; it shares its first eight terms with this sequence, with which I confused it at first. The condition for computing this "impostor sequence" is that
\{ N - s_k \} \cap \{ s_j - s_i \}_{1 \le i < j \le k}

be empty. The impostor sequence begins {1, 2, 4, 8, 13, 21, 31, 45, 60, ...} and it's at the term "60" that it first differs from the Mian-Chowla sequence. We have 60-45 = 15, and 15 never occurs as a difference between any of the first eight terms. But 60 - 31 = 31 - 2 = 29, so 60 isn't the ninth term of the Mian-Chowla sequence; that turns out to be 66. The divergence only gets wider after that. But the upper and lower bounds that I gave above still apply!

It appears (from computations of Frank Chu) that the nth term of the Mian-Chowla sequence grows like n2.8. I don't know why this should be, though. However, the sequence I confused it with is the partial sums of the segmented numbers; the nth segmented number is about n lg lg n (this is just a conjecture, but a reasonable one) and so my impostor sequence should grow like (n2 lg lg n)/2, which fits the known values reasonably well. Since my impostor sequence has fairly weak conditions allowing us to extend it, I would conjecture that its growth rate is close to the lower bound, of order n2, and so n2 times a subpolynomial function seems nice. I'd actually conjecture that the Mian-Chowla sequence grows like n3 divided by some subpolynomial function -- but which one? Finally, something about the fact that we're looking at collisions between the difference sets makes me think that there might be a probabilistic model for this problem.

Frank Chu. Notes on the Mian-Chowla Sequence. http://www.cumc.math.ca/2004/mc.pdf
A. Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe, I, II. J. Reine Angew. Math. 194 (1955), 40-65; 111-140.
Terence Tao and Van Vu, Additive Combinatorics. Cambridge: Cambridge University Press, 2006.
Encyclopedia of Integer Sequences: A004978, A005282.

1 comment:

Anatoly Vorobey said...

To be slightly pedantic, you didn't prove what was requested - an inequality for every k, not just asymptotically. For k=1,2, your estimate happens to be greater than (k-1)^3+1 asked for. I imagine proving the exact inequality would be easy by induction, using the same bound of k(k-1)/2+1 for the difference between successive elements, but I haven't worked out the details.