5
$\begingroup$

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<c$. 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)|<c$ 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.

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

1 Answer 1

2
+50
$\begingroup$

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<N$ 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<d$ 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .