# Difference set of difference set

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!

• The description is not quite clear to me. But a set with $n$ elements has on the order of $n^2$ differences; if those are distinct, there are on the order of $n^4$ their differences. Thus, the best you can hope for is the largest integer to have magnitude $O(n^4)$. Commented Apr 23, 2021 at 14:39
• The second set allows some duplicates. If you look at the table und fix two numbers of the same row (or column) then the difference of those numbers occur in all others rows too. So I think/hoped the order may be less den than O(n^4). Commented Apr 23, 2021 at 14:46
• It is certainly possible to have $\Omega(n^4)$ second order differences. E.g., if the set is $\{4^i:0\le i<n\}$, the second-order difference set will include all numbers of the form $4^i+4^l-4^j-4^k$ for $n>i>j\ge k>l$ or $n>i>k>l>j$, $4^i-4^j$ for $n>i>j$, and $0$. These are pairwise distinct, and their number is thus $2\binom n4+\binom n3+\binom n2+1=\frac1{12}n^4+O(n^3)$. So the question is how small can the elements be to achieve this bound (obviously, the ones I used are exponentially large). Commented Apr 23, 2021 at 15:08
• Ohhh thank you so much for this comment. This clarifies a lot. Since I am new here. Is there some way I can "vote" your answer/comment? Commented Apr 23, 2021 at 15:12
• This was just a comment, not an answer. You can upvote a comment using the triangle to the left of the comment, though I’m not sure if it requires some reputation (I believe you need to have 15 reputation points to be able to upvote questions and answers, but I don’t know if that applies to comments, too). Comments are not of much significance, anyway. Commented Apr 23, 2021 at 15:39

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, the set of differences is $$\{0\}\cup\{a_i-a_j:i,ja_j\},$$ thus one checks easily that the set of second-order differences consists of the elements

• $$0$$,

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

• $$|a_i+a_j-a_k-a_l|$$ for $$i,j,k,l 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 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 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 as given in the beginning of this post are pairwise distinct.

• Very interesting construction. Thank you very much! Commented May 5, 2021 at 16:45