Given N points on a number line and m total distances between those points, are there efficent ways to optimize for particular values in m?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

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