7
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I agree with you. Thanks a lot for this! Somehow I hadn't thought of it. (By the way, I was curious to see the results of this construction so I implemented it a3nm.net/git/gcd_difference/tree/calc.cpp -- it works ine but computing a sequence of size 10 already takes a lot of time because the numbers get very big.) Thanks again! $\endgroup$ – a3nm Mar 12 '17 at 10:06
  • $\begingroup$ @a3nm : No, this is not very practical. I just wanted to show that there were Special sequences of all lengths. I think the fact that Special sequences can be expressed as a family of congrunce equations might be exploited in a way that produces better-sized numbers. $\endgroup$ – steven gregory Mar 12 '17 at 15:13
  • $\begingroup$ @a3nm - I don't know if this is any faster, but you can replace $a \equiv 0 \pmod{|b-a|}$ with $|a-b| \mid a$. $\endgroup$ – steven gregory Mar 13 '17 at 3:24
  • $\begingroup$ Thanks for the idea, but I don't think that testing divisibility is the bottleneck. The problem is that the numbers get large very quickly. The special sequence with 9 elements already consists of numbers with over 2000 digits, and the one for 10 elements is even worse. $\endgroup$ – a3nm Mar 13 '17 at 13:31
  • $\begingroup$ @a3nm: If you use something that has arbitrary precision integers it shouldn't take too long. The 10 element series should have less than 18000 digits per number. I would expect Mathematica or Python to make quick work of the construction as you just need the LCM of the 9 numbers. $\endgroup$ – Ross Millikan May 29 '17 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.