*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 thekth element of S does not exceed (k-1)^{3}+ 1, and hence the number of elements of S which are less thannis Ω(n^{1/3}) asngoes 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 s

_{1}= 1, s

_{2}= 2, s

_{3}= 4, and so on form the sequence S. Say we know the first four terms, s

_{1}through s

_{4}, 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 s

_{1}, ..., s

_{k}are known, we choose s

_{k+1}to be the smallest integer N such that the intersection

is empty.

The solution is straightforward. Now, by the "greedy algorithm" it's meant that if we know s

_{1}through s

_{k}, then s

_{k+1}is the

*smallest*integer greater than s

_{k}which doesn't violate the definition of our sequence. Then it's enough to minimize the difference t

_{k}= s

_{k+1}- s

_{k}; this is the

*smallest*positive integer which does

*not*occur among pairwise differences of elements of {s

_{1}, ..., s

_{k}}. 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 . Then the s

_{k}are just the partial sums of the t

_{k}, so we get

which is asymptotically equal to k

^{3}/6.

The same method gives a lower bound -- all the differences s

_{k}- s

_{i}for i < k are distinct, so t

_{k}is at least k+1. This gives a lower bound for s

_{k}of order k

^{2}/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

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

*n*th term of the Mian-Chowla sequence grows like n

^{2.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

*n*th 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 (n

^{2}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 n

^{2}, and so n

^{2}times a subpolynomial function seems nice. I'd actually conjecture that the Mian-Chowla sequence grows like n

^{3}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.

**References**

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:

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.

Post a Comment