Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a set of distances S, choose N unique points P on a number line such that the distances between the N points occur in S as much as possible. That is, maximize the occurence in S of the distances between the N points.

For example:

S = {2, 4}, N = 4

One answer would be P = {2, 4, 6, 8}, since the distances between the points P are 2, 2, 2, 2, 4, 4, 6. Only 6 is not in S.

or

S = {7, 13, 14, 22} N = 4501

answer ???

I'm not looking for an exact answer (although an exact answer wouldn't hurt) but rather I am trying to avoid reinventing the wheel (fun though it may be). What mathematical tools could I use to avoid bruteforcing the possible values of P. How should how would you approach this problem?

share|improve this question
add comment

3 Answers

up vote 1 down vote accepted

Some comments expanding on gowers' hunch: we may as well assume that the elements of S have gcd 1. If the size of the set is |S| = m and the sum of the elements of S is k then taking a block of N consecutive integers for $N \geq m$ gives (mN - k) pairs. There's also a theoretical maximum of $mN - \binom{m + 1}{2}$: every element of any N-set can be the larger half of at most m pairs, except that the smallest element can be the larger half of at most 0, the second-smallest can be the larger half of at most 1, etc., and the m-th smallest can be the larger half of at most (m - 1).

This theoretical maximum is achieved for S = {1, 2, ..., m} and matches gowers' strategy in this case. However, usually there's some gap between gowers' strategy and the theoretical max, and in some cases we can definitely do better than gowers' strategy: for example, with S = {1, 5, 10} and N = 12, a block of 12 consecutive integers gives us 11 + 7 + 2 = 20 pairs while an arithmetic progression with step size 5 gets us 11 + 10 = 21 pairs. So for small values of N we can sometimes do better by ignoring certain elements of S.

share|improve this answer
add comment

This feels to me more like additive combinatorics than additive geometry, though the flavour of the problem may change when N gets large. If f is the characteristic function of A, g is the characteristic function of -A, and h is the characteristic function of the set you want the differences to lie in, then you seem to be interested in the value of $\langle f*g,h\rangle$. This makes sense on the Fourier side, so if you are looking for estimates rather than exact answers it could possibly help to look at $\langle |\hat{f}|^2,\hat{h}\rangle$, to which it is equal.

My guess is that for the example you said you don't know the answer to, your best bet is to take P to be an arithmetic progression with common difference 1. More generally (and my hunch is that this wouldn't be too hard to prove) for any fixed set S, the best you can do is take an arithmetic progression with common difference equal to the highest common factor of the elements of S.

share|improve this answer
add comment

You may want to look into what are called Golomb Rulers:

http://en.wikipedia.org/wiki/Golomb_ruler

share|improve this answer
    
+1, oh thanks that looks neat! –  eth0 Mar 17 '10 at 14:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.