# What the set $D=\{|\sigma(x+1)-\sigma(x)||x\in\mathbb{Z}\}$ could be?

Let $$\sigma$$ be a permutation of $$\mathbb{Z}$$ such that the set $$D=\{|\sigma(x+1)-\sigma(x)||x\in\mathbb{Z}\}$$ is finite. What the set $$D$$ could be?

Let $$d$$ be the greatest common divisor of all elements of $$D$$, then by induction we easily have that $$\sigma(x)\equiv \sigma(0) (mod\;d),\forall x\in\mathbb{Z}$$, because $$\sigma$$ is a permutation we must have $$d=1$$, so the all elements of $$D$$ are coprime. We have:

If $$|D|=1$$, then $$D$$ must be $$\{1\}$$, we just take the identity permutation.

If $$|D|=2$$, then $$D=\{a,b\}$$ such that $$gcd(a,b)=1$$. Let $$c=a+b$$, we have $$gcd(c,a)=1$$. We build the permutation $$\sigma$$ as follow: For $$x\in\mathbb{Z}$$, we write $$x=cq+r,q,r\in\mathbb{Z},0\leq r. We choose the unique $$s\in\mathbb{Z}$$ such as $$ar\equiv s(\mod\;c)$$ and define $$\sigma(cq+r)=cq+s$$. Because $$gcd(c,a)=1$$ so $$\sigma$$ is a permutation. By the construction we have $$\sigma(x+1)-\sigma(x)\equiv a(mod\;c),|\sigma(x+1)-\sigma(x)| so either $$\sigma(x+1)-\sigma(x)=a$$ or $$\sigma(x+1)-\sigma(x)=-b$$, so we have $$D=\{|\sigma(x+1)-\sigma(x)||x\in\mathbb{Z}\}$$ as we want.

I don't know how to deal with the case $$|D|>2$$ since the trick for $$|D|=2$$ does not work in this case in general.

• This might be helpful: en.wikipedia.org/wiki/… Oct 7, 2023 at 9:01
• Have you constructed any examples? Determined $D$ for simple permutations? Then see what happens under composition? Oct 8, 2023 at 4:52
• The number $s\in\mathbb{Z}$ such that $ar\equiv s\pmod{c}$ is not unqiue, but determined up to a multiple of $c$. Oct 10, 2023 at 19:21

## 1 Answer

We need the following definitions. For each nonegative integer $$n$$ put $$[n]=\{0,\dots,n\}$$. Let $$D$$ be a finite subset of $$\mathbb N$$. The set $$D$$ is permutable if there exists a permutation $$\sigma$$ of $$\mathbb{Z}$$ such that $$D=\{|\sigma(x+1)-\sigma(x)|:x\in\mathbb{Z}\}.$$ The set $$D$$ is finitely permutable if there exist a natural number $$N$$ and a permutation $$\sigma$$ of $$[N]$$ such that $$\sigma(0)=0$$, $$\sigma(N)=N$$, and $$D=\{|\sigma(x+1)-\sigma(x)|:x\in [N-1]\}.$$

Proposition 1. Any finitely permutable set $$D$$ is permutable.

Proof. There exist a natural number $$N$$ and a permutation $$\sigma$$ of $$[N]$$ such that $$\sigma(0)=0$$, $$\sigma(N)=N$$, and $$D=\{|\sigma(x+1)-\sigma(x)|:x\in [N-1]\}$$. Define a permutation $$\sigma'$$ of $$\mathbb Z$$ as follows. Let $$n\in\mathbb Z$$ be any number. If $$N=1$$ then let $$r=0$$ otherwise there exists a unique nonnegative integer $$r such that $$(N-1)|(n-r)$$. Put $$\sigma'(n)=n-r+\sigma(r)$$. Since $$\sigma'|[N]=\sigma$$, the set $$D$$ is permutable. $$\square$$

Question 2. Is any permutable set finitely permutable?

Proposition 3. Any finite union of finitely permutable sets is finitely permutable.

Proof. It suffices to show that a union of two finitely permutable sets $$D'$$ and $$D''$$ is finitely permutable. There exist natural numbers $$N'$$ and $$N''$$, a permutation $$\sigma'$$ of $$[N']$$, and a permutation $$\sigma''$$ of $$[N'']$$ such that $$\sigma'(0)=0$$, $$\sigma''(0)=0$$, $$\sigma'(N')=N'$$, $$\sigma''(N'')=N''$$, $$D'=\{|\sigma'(x+1)-\sigma'(x)|:x\in [N'-1]\}$$, and $$D''=\{|\sigma''(x+1)-\sigma''(x)|:x\in [N''-1]\}$$. For each $$x\in [N'+N'']$$ put $$\sigma(x)=\sigma'(x)$$, if $$x\in [N']$$, and $$\sigma(x)=\sigma''(x-N')+N'$$, otherwise. Then $$\sigma$$ is a permutation of $$[N'+N'']$$ and $$D\cup D'=\{|\sigma(x+1)-\sigma(x)|:x\in [N+N'-1]\}. \square$$

Your construction for $$|D|=2$$ provides the following proposition.

Proposition 4. For any coprime natural numbers $$m$$ and $$n$$, the set $$\{m,n\}$$ is finitely permutable. $$\square$$

Question 5. Let $$D\subset N$$ be a set such that the greatest common divisor of elements of $$D$$ is $$1$$. Is $$D$$ (finitely) permutable?

The following proposition can be the first step to the affirmative answer to Question 5.

Proposition 6. For any noncoprime natural numbers $$m$$ and $$n$$, the set $$\{m,n,m+n-1\}$$ is finitely permutable.

Proof. Swapping the numbers $$m$$ and $$n$$, if needed, we can assume that $$m\le n$$. Let $$d=\operatorname{GCD}(m,n)$$. Your construction for $$|D|=2$$ provides a permutation $$\sigma$$ of $$[(m+n)/d]$$ such that $$\sigma(0)=0$$, $$\sigma((m+n)/d)=(m+n)/d$$, and $$\{m/d,n/d\}=\{|\sigma(x+1)-\sigma(x)|:x\in [(m+n)/d-1]\}.$$ Define a map $$\sigma'$$ on $$[m+n+d-1]$$ as follows. Let $$x\in [m+n+d-1]$$ be any number. There exists a unique nonnegative integer $$r such that $$d|(x-r)$$. Put $$\sigma'(x)=r+d\sigma((x-r)/d).$$ It is easy to check that $$\sigma'$$ is a permutation of $$[m+n+d-1]$$, $$\sigma'(0)=0$$, $$\sigma'(m+n+d-1)=m+n+d-1$$, and $$\{m,n,m+n-1\}=\{|\sigma(x+1)-\sigma(x)|:x\in [(m+n+d-1]\}.\square$$

Similarly we can show the following

Proposition 7. For any noncoprime natural numbers $$m$$ and $$n$$, and any natural $$k$$, the set $$\{m,n,k(m+n)-1\}$$ is finitely permutable. $$\square$$

Moreover, the construction from Proposition 6 can be inductively generalized to four-element sets, to five-element sets and so forth.