# References for this kind of combinatorial objects? (lists of integers with small number of distinct pairwise differences)

While studying something irrelevant (too long and irrelevant to mention here), I stumbled upon lists of integers with a small number of distinct pairwise differences.

Example. Consider the list of numbers: $$[0,1,8,9,16,17,24,25,32,33].$$

Let's only consider positive differences. First we form the positive differences of elements "one step" apart: $$33-32=1, 32-25=7, 25-24=1, 24-17=7, \dots$$ so, we get the differences $1,7,1,7,1,7,1,7,1$. Next, let's form the positive differences of elements "two steps" apart: $$33-25=8, 32-24 = 8, 25-17 =8,\dots$$ so we get the differences $8,8,8,8,8,8,8,8$. If we continue like that, we obtain the following array of differences:

\begin{array}{rrrrrrrrr} 1 & 7 & 1 & 7 & 1 & 7 & 1 & 7 & 1\\ & 8 & 8 & 8 & 8 & 8 & 8 & 8 & 8\\ & & 9 & 15 & 9 & 15 & 9 & 15 & 9\\ & & & 16 & 16 & 16 & 16 & 16 & 16\\ & & & & 17 & 23 & 17 & 23 & 17\\ & & & & & 24 & 24 & 24 & 24\\ & & & & & & 25 & 31 & 25\\ & & & & & & & 32 & 32\\ & & & & & & & & 33 \end{array}

I suspect there is some combinatorial structure here. For one, we have a quite small number of (positive) differences; the set has $10$ distinct elements and only $13$ distinct differences: $1,7,8,9,15,16,17,23,24,25,31,32,33$.

I need to know more about such lists with few distinct differences. Are these studied already? Is there indeed a combinatorial structure here? If so, could you provide the name of those combinatorial objects and some reference?

-
Reminds me of the Erdos distance problems. Big literature, unfortunately as far as I know dimensions 2 and higher. – André Nicolas Jul 5 '13 at 21:20
@AndréNicolas Didn't know about that problem.. That's very interesting. – geo909 Jul 8 '13 at 15:34

A quick thing to notice:

In the single difference case the difference must be a single number from the set

1 7 1 7 1 7 1 7 1 7...

On the double difference case the difference must be sum of 2 consecutive numbers from the set

1 7 1 7 1 7 1 7 1 7...

Which can either be 1 + 7 or 7 + 1 which in either case is 8.

On the triple difference case the difference must be the sum of 3 consecutive numbers from the aforementioned sets and therefore can either take on the value 1 + 7 + 1 = 9 or 7 + 1 + 7 = 15. And so on and so forth...

The pattern therefore that you observe is purely because of the differences of numbers that are "1 step apart". Once you establish that pattern the rest of the patterns for "2 steps, 3 steps" etc.. all crystallize.

Thus you question is whether there is a name for ordered sets of numbers such that the difference between any 2 consecutive terms in the set is one of 2 numbers. I cannot say off the top of my head what that sort of object would be called but we can explore some its basic properties here.

Consider a set of $2k$ elements where k is an integer that has the first value 0 and has the 2 consecutive differences of $a,b$ example:

[0, a, a+b, 2a + b, 2a+2b, 3a+2b, 3a+3b... (k)a+(k-1)b]

if a = 1, b = 7 and k = 10 we get the set that you described.

You may be tempted to ask how many such sets exist? if we have $a_1$ choices of a, $b_1$ choices of b and $k_1$ choices of b which would be trivial to show is just $a_1b_1k_1$. But perhaps you are looking to correspond this set to some other set. Can that be done?

Consider an ordered set of $Q$ elements for some integer $Q$ that takes on the following form:

$[a, s_1+a, 2s_1+a, 3s_1+a... (Q-1)s_1+a]$

Basically just an arithmetic sequence. For every one of these arithmetic sequence sets we can develop your alternating sequence sets by choosing how to split up the individual terms. Let me illustrate with your example.

Consider the set:

$[1, 17, 33, 49, 65]$ The common difference of the terms is 16, the first term is 1. If we take each element of the set, call the element W and solve the equation $2x+1 = w$ and then list the values $x, x+1$ in place of W we create the set:

$[1, 17, 33, 49, 65]$ ---> $[0,1,8,9,16,17,...]$

If we change the value of 1 in $2x + 1 = w$ to a different number then we will get a brand new alternating set of our choice. Thus for any normal arithmetic sequence set it is possible to generate a plethora of alternating arithmetic sequence sets. The pattern between them depends on how you restrict the ability to split individual numbers.

You can also consider sets that alternate between 3 values and 4 values etc... for their consecutive differences and will quickly see that it is possible to create a complex framework for all of this which will involve all sorts of different combinatorial tools to count.

-
Thank you for the providing a on-the-spot theory, that helps a lot. – geo909 Jul 8 '13 at 15:33
It is my pleasure. I've never seen this done before so it looks like something worth exploring :) – frogeyedpeas Jul 8 '13 at 17:46