Are there arbitrarily large sets $S$ of natural integers such that the difference of each pair is their GCD?

I am interested in sets $S \subseteq \mathbb{N}$ of natural integers with the following property: for any $i, j \in S$, then the greatest common divisor of $i$ and $j$ is the absolute value of their difference, $|i - j|$. Equivalently, this amounts to requiring that the difference $|i-j|$ divides $i$ and $j$.

Are there sets $S$ of arbitrarily large cardinality with this property?

Examples of such sets $S$ of cardinality up to 9 are given in sequence A213918 of the OEIS, but there is no discussion there about whether arbitrarily large such sets exist.

My intended use for this would be to obtain a variant of Van der Waerden's theorem, to show that from an infinite word one can extract arbitrarily large monochromatic arithmetic progressions with the added condition that the common difference of the arithmetic progression divides its first term.

Solution 1:

DEFINITION: Positive integers $a$ and $b$ are Special if $\gcd(a,b) = |a-b|$.

LEMMA$1$: Positive integers $a$ and $b$ are Special if and only if $a \equiv 0 \bmod{|b-a|}$.

PROOF: Suppose that $a$ and $b$ are Special. Then $|b-a|$ divides $a$. Hence $a \equiv 0 \bmod |a-b|$.

Suppose that $a \equiv 0 \bmod |b-a|$. If $a > b$, then $b = a - |b-a|$. If $a < b$, then $b = a + |b-a|$. In either case $b \equiv 0 \bmod |b-a|$. Since $b-a = \pm |b-a|$ and $|b-a|$ divides both $a$ and $b$, it follows that $\gcd(a,b) = |b-a|$.

DEFINITION: We say that an increasing sequence of positive integers $\mathbf s = \{s_0,\; s_1,\; s_2,\; \dots,\; s_n\}$ is Special if, for every $0 \le i < j \le n$, $s_i$ and $s_j$ are special.

An immediate consequence of LEMMA$1$ is

THEOREM$1$: Suppose that the increasing sequence $\mathbf s = \{s_0,\; s_1,\; s_2,\; \dots,\; s_n\}$ is Special and let $\sigma = \operatorname{lcm}\left\{ s_i \right\}_{i=0}^n$. then the sequence $\mathbf s'=\{\sigma,\; \sigma+s_0,\; \sigma+s_1,\; \sigma+s_2,\; \dots,\; \sigma+s_n\}$ is Special

For example, the sequence $\mathbf s = \{2,3,4\}$ is Special and $\sigma = \operatorname{lcm}\{ 2,3,4 \} = 12$. Then $\mathbf s' = \{12,14,15,16\}$ is Special.

$\mathbf s''=\{1680, 1692, 1694, 1695, 1696\}$.

ADDENDUM (4/5/2017)

We will present an example from which the more general case should be clear. Suppose $A < B < C < D < E$ and we wish to test whether or not $\mathbf S = \{A,B,C,D,E\}$ is Special.

This will be equivalent to showing that the following pairs are special:

$$\begin{array}{cccc} (A,B) &(A,C) &(A,D) &(A,E) \\ &(B,C) &(B,D) &(B,E) \\ &&(C,D) &(C,E) \\ &&&(D,E) \\ \end{array}$$

Which is equivalent to showing that

$$\begin{array}{cccc} B-A \mid A & C-A \mid A & D-A \mid A & E-A \mid A \\ & C-B \mid B & D-B \mid B & E-B \mid B \\ && D-C \mid C & E-C \mid C \\ &&& E-D \mid D \end{array}$$

We "encode" this as

$$\begin{array}{lrrrr} A: & B-A & C-A & D-A & E-A \\ B: & & C-B & D-B & E-B \\ C: & && D-C & E-C \\ D: & &&& E-D \\ E: \end{array}$$

and call the result a GCD table for the sequence (A,B,C,D,E). For example, the GCD table for the sequence $(1680, 1692, 1694, 1695, 1696)$ is

$$\begin{array}{lrrrr} 1680: & 12 & 14 & 15 & 16 \\ 1692: & & 2 & 3 & 4 \\ 1694: & && 1 & 2 \\ 1695: & &&& 1 \\ 1696: \end{array}$$

Note that

$12,14,15,$ and $16$ divide $1680$,

$2,3$ and $4$ divide $1692$,

$1$ and $2$ divide $1694$, and

$1$ divides $1695$.

That is enough information to prove that the sequence $(1680, 1692, 1694, 1695, 1696)$ is Special.

Note also that

$(2,3,4) = (14-12, 15-12, 16-12)$,

$(1,2) = (3-2, 4-2)$, and

$1 = 2-1$.

The implied pattern is, in fact, always true.

GCD tables are very useful for generating Special sequences.

Consider, for example the Special sequence $(2,3,4)$. Its GCD table is

$$\begin{array}{lrrrr} 2: & 1 & 2 \\ 3: && 1\\ 4: \end{array}$$

let's refer to the table on the right side of the semicolons in a GCD table as the GCD pattern. It shouldn't come as a suprise that other Special sequences will have the same GCD pattern. So, we ask ourselves, "When is the following a GCD table of a Special sequence?"

$$\begin{array}{rrrrr} n : & 1 & 2 \\ n+1 : && 1\\ n+2 : \end{array}$$

The answer is, when $2 \mid n$. So $\{(2n, 2n+1, 2n+2): n \in \mathbb Z^+\}$ is a family of special sequences.

Can some of the sequences in this family be extended to a Special sequence containing four elements?

$$\begin{array}{rrrrr} 2n : & \color{red}1 & \color{red}2 & x+2 \\ 2n+1 : && \color{red}1 & x+1\\ 2n+2 : &&& x \\ 2n+2+x: \end{array}$$

We can ignore the red GCD's because of the way that this table was constructed. They have already been "tested" and they have passed. So we must find an $x$ such that $$ x \mid 2n+2, \quad x+1 \mid 2n+1, \quad x+2 \mid 2n$$

If $x=1$, then $1 \mid 2n+2,\; 2 \mid 2n+1$ and $ 3 \mid 2n$. This set of relations cannot be satisfied.

If $x=2$, then $2 \mid 2n+2,\; 3 \mid 2n+1$ and $ 4 \mid 2n$.

The relation $2 \mid 2n+2$ is always true.

$3 \mid 2n+1 \implies 3 \mid n+2 \implies n \equiv 1 \pmod 3$

$4 \mid 2n \implies 2 \mid n \implies n \equiv 0 \pmod 2$.

We find that $n \equiv 4 \pmod 6$.

Letting $x=2$ and $n=6m + 4$, we get

$$\begin{array}{rrrrr} 12m+8 : & \color{red}1 & \color{red}2 & \color{red}4 \\ 12m+9 : && \color{red}1 & \color{red}3 \\ 12m+10: &&& \color{red}2 \\ 12m+12: \end{array}$$

and we see that, for example, $(8,9,10,12)$ is a Special sequence.

Can we extend this GCD pattern? Let's see.

$$\begin{array}{rrrrr} 12n+8 : &\color{red}1 &\color{red}2 & \color{red}4 & x+4 \\ 12n+9 : &&\color{red}1 & \color{red}3 & x+3\\ 12n+10: &&&\color{red}2 & x+2\\ 12n+12: &&&& x \\ 12n + 12 + x: \end{array}$$

So we need to find a positive integer, $x$ such that

$$ x+4 \mid 12n+8, \quad x+3 \mid 12n+9, \quad x+2 \mid 12n+10, \quad x \mid 12n+12 $$

The first good value of $x$ is $12$. Letting $x=12$, we get the relations

$$ 16 \mid 12n+8, \quad 15 \mid 12n+9, \quad 14 \mid 12n+10, \quad 12 \mid 12n+12 $$

• $12 \mid 12n+12$ is true for all $n$.
• $ 14 \mid 12n+10 \implies 7 \mid 6n + 5 \implies 7 \mid n+2 \implies n \equiv 5 \pmod 7$
• $15 \mid 12n+9 \implies 5 \mid 4n+3 \implies 5 \mid n+2 \implies n \equiv 3 \pmod 5$
• $16 \mid 12n+8 \implies 4 \mid 3n + 2 \implies 4 \mid n + 2 \implies n \equiv 2 \pmod 4$

Using the Chinese remainder theorem, we find $n \equiv 138 \pmod{140}$.

Letting $x=12$ and $n=138m + 140$, we get

$$\begin{array}{rrrrr} 1680m + 1664: & \color{red}1 & \color{red}2 & \color{red}4 & \color{red}{16}\\ 1680m + 1665: && \color{red}1 & \color{red}3 & \color{red}{15}\\ 1680m + 1666: &&& \color{red}2 & \color{red}{14}\\ 1680m + 1668: &&&& \color{red}{12}\\ 1680m + 1676: \end{array}$$

So, we see that $(1664, 1665, 1666, 1668, 1676)$ is a Special sequence.

Addendum 5/29/2017

For the sake of expedience, I offer the following theorems without proof. First, I want to remark that there is no reason a Special sequence can't start with $0$.

\begin{array}{c|ccccc} x_1 & \delta_{12} & \delta_{13} & \delta_{14} & \cdots & \delta_{1n}\\\hline x_2 && \delta_{23} & \delta_{24} & \cdots & \delta_{2n}\\\hline x_3 &&& \delta_{34} & \cdots & \delta_{3n}\\\hline \vdots &&&& \ddots & \vdots\\\hline x_{n-1} &&&&&\delta_{n-1,n} \\\hline x_n \end{array}

THEOREM Let $x_1, x_2, x_3, \dots, x_n$ be a strictly increasing sequence of integers. Define $\delta_{ij} = x_j - x_i$. Then $x_1, x_2, x_3, \dots, x_n$ is a Special sequence if and only if, for every $1 \le i < j \le n, \; \delta_{ij} \mid x_i$.

DEFINITION We define the period of a Special sequence to be the number $N$ where $N$ equals the least common multiple of all of the $\delta_{ij}$.

THEOREM Let $(a_1, a_2, \dots, a_n)$ be a Special sequence with a period of $N$. Then $(N+a_1, N+a_2, \dots, N+a_n)$ is also a Special sequence with a period of $N$.

THEOREM Let $(a_1, a_2, \dots, a_n)$ be a Special sequence with a period of $N$ and with $0 < a_1 < a_2 \cdots < a_n$. Then $(0, a_1, a_2, \dots, a_n)$ is also a Special sequence.

THEOREM Let $(a_1, a_2, \dots, a_n)$ be a Special sequence with period $N$. Then $(N-a_n, N-a_{n-1}, \dots, N-a_2, N-a_1)$ is also a Special sequence with a period of $N$. We call this sequence the reflection of the sequence $(a_1, a_2, \dots, a_n)$.

EXAMPLES

$$\begin{array}{c|ccccc} 0 & 1 & 2 \\\hline 1 && 1\\\hline 2 \end{array}$$

We see from the table above that $(0,1,2)$ is a special sequence with a period of $2$ that is equal to its reflection.

Also $2+(0,1,2) = (2,3,4)$ is a Special sequence with a period of $2$.

$$\begin{array}{c|ccccc} 2 & 1 & 2 \\\hline 3 && 1\\\hline 4 \end{array}$$

Hence $(0,2,3,4)$ is a special sequence with a period of $12$. $$\begin{array}{c|ccccc} 0 & 2 & 3 & 4 \\\hline 2 && 1 & 2\\\hline 3 &&& 1 \\\hline 4 \end{array}$$

Its reflection also has a period of $12$.

$$\begin{array}{c|ccccc} 8 & 1 & 2 & 4 \\\hline 9 && 1 & 3\\\hline 10 &&& 2 \\\hline 12 \end{array}$$

You should have the idea now how to generate ever larger Special sequences.