Difference set of difference set

Question

I am a hobby computer scientist and searching for an algorithm to construct a set of n numbers (integers) with certain properties.

Property 1 / Step 1

All pairwise differences of the elements should be unique. From what I read, I think this is called 'difference set'.

Property 2 / Step 2

Having constructed all differences in step 1, we build the differences of the new set again. The resulting elements should also be as unique as possible. Meaning equal differences should be minimal.

What I have so far

It is clear to me, that "step 1" implies, that the largest number in the set is of order n². I was hoping that after "step 2" the largest number would not increase too much (like n² * log(n)), but my simulations suggest an order of n³.

Example 1

The set {0,1,4,9} fullfills poperty 1, but it fails on property 2.

After steps 1 we have the difference set {0, 1, 3, 4, 5, 8, 9}. If arranged in a table one can write:

0 1 4 9   
  0 3 8
    0 5
      0

It is clear, that 9-4 and 8-3 have the same difference. Due to the construction some differences cannot be prevented.

But 5-1 = 4-0 is a difference which should not happen in step 2.

Example 2

The set {0,1,4,13} fullfills poperty 1 and property 2.

0 1 4 13   
  0 3 12
    0  9
       0

The only equal differences occur, when four choosen numbers form a "rectangle", like 13-4 = 9 -0

I would really appreciate any help!

Answer 1

I’m assuming from the examples that you are only considering non-negative differences.

Let us first see what “as unique as possible” means. If the original set is $\{a_i:0\le i<n\}$, the set of differences is $$\{0\}\cup\{a_i-a_j:i,j<n,a_i>a_j\},$$ thus one checks easily that the set of second-order differences consists of the elements

• $0$,

• $a_i-a_j$ for $i,j<n$ such that $a_i>a_j$,

• $|a_i+a_j-a_k-a_l|$ for $i,j,k,l<n$ such that $a_i>a_k\ge a_j$, $a_k>a_l$.

Moreover, all the expressions above are pairwise distinct if the $a_i$'s are sufficiently linearly independent. Thus, the maximal size of the second-difference set is $$2\binom n4+\binom n3+\binom n2+1=\frac{n^4}{12}+O(n^3).$$ Consequently, any set $\{a_i:i<n\}$ of non-negative integers that attains this maximum has to have $\max_ia_i=\Omega(n^4)$.

It is possible to meet the $O(n^4)$ bound by a modification of the Erdős–Turán construction of Golomb rulers. Given $n$, we fix a prime $p$ such that $p\ge\max\{n,5\}$ and $p=(1+o(1))n$. Then we define a set $\{a_i:0\le i<n\}$ of numbers $a_i<64p^3n=(64+o(1))n^4$ by $$a_i=(4p)^3i+(4p)^2(i^2\bmod p)+4p(i^3\bmod p)+(i^4\bmod p).$$

Lemma: $a_i+a_j+a_k+a_l=a_{i'}+a_{j'}+a_{k'}+a_{l'}$ only if $\{i,j,k,l\}=\{i',j',k',l'\}$ as multisets (i.e., including multiplicities).

Proof: By considering base-$4p$ expansion, we have $$i^d+j^d+k^d+l^d\equiv i'^d+j'^d+k'^d+l'^d\pmod p$$ for each $d\le 4$, thus using Newton’s identities in $\mathbb F_p$, we obtain $$e_d(i,j,k,l)\equiv e_d(i',j',k',l')\pmod p$$ for each $d\le 4$, where $e_d(x_0,x_1,x_2,x_3)$ denotes elementary symmetric polynomials. In other words, we get the identity of polynomials $$(X-i)(X-j)(X-k)(X-l)=(X-i')(X-j')(X-k')(X-l')$$ in $\mathbb F_p[X]$. Since this polynomial uniquely determines $\{i,j,k,l\}\subseteq\mathbb F_p$ as the multiset of its roots, the lemma follows.

Corollary: $a_i+a_j-a_k-a_l=a_{i'}+a_{j'}-a_{k'}-a_{l'}$ only if $\{i,j,k',l'\}=\{i',j',k,l\}$ as multisets.

In other words, the second-order differences $a_i+a_j-a_k-a_l$ coincide only when necessary; thus, the $2\binom n4+\binom n3+\binom n2+1$ expressions for elements of the second-order difference set of $\{a_i:i<n\}$ as given in the beginning of this post are pairwise distinct.