1
$\begingroup$

In continutation to a question that i asked earlier and got answered here :Discretizing a mathematical equation This is a bijective mapping from the set of ordered tuples $(x,y,z)$ where each $x,y,z\in \{1,2,\dots,n\}$ to itself. $$ \begin{align} x'&=\text{mod}(2(x-1),n)+1+\mathbf{1}[\text{mod}(z,4)= 2\text{ or }\text{mod}(z,4)=0] \\ y'&=\text{mod}(2(y-1),n)+1+\mathbf{1}[\text{mod}(z,4)= 3\text{ or }\text{mod}(z,4)=0] \\ z'&=\lceil z/4\rceil + (n/4)\Big(1.\mathbf{1}[n/2<x] + 2\cdot \mathbf{1}[n/2<y]\Big) \end{align} $$ where $\def\1{{\bf 1}}\1[S]$ be a function which is equal to $1$ if the statement $S$ is true, and zero otherwise.

Since it is a bijective mapping I want to find it's inverse. I have deduced the following results but still not been able to get the inverse. So here s my work

$1.$ Given $(x',y',z')$ if I see that if $x'$ and $y'$ both are odd then $z\equiv 1$ mod $4$.

$2.$ Observing the value of $z'$ I deduce that $\begin{cases} z'\leq n/4, &\implies x\leq n/2~\text{and}~y\leq n/2\\ n/4< z'\leq n/2, &\implies x>n/2 ~\text{and}~y\leq n/2~\\ n/2 <z'\leq 3n/4, &\implies x\leq n/2~\text{and}~y>n/2~\\ z'>3n/4, &\implies x> n/2~\text{and}~y>n/2~ \end{cases}$

$3.$ So if $z'$ belongs to the first case then $z=4\cdot(z')+1$

$4.$ if $z'$ belongs to the second case then $z=4\cdot(z'-n/4-1)+1$

$5.$ if $z'$ belongs to the third case then $z=4\cdot(z'-n/2-1)+1$

$6.$ if $z'$ belongs to the fourth case then $z=4\cdot(z'-3n/4-1)+1$

The similar cases if $x'$ is odd and $y'$ is even $\implies z\equiv 3~\text{mod}~4$

If $x'$ is even and $y'$ is odd $\implies z\equiv 2~\text{mod}~4$

If $x'$ is even and $y'$ is even $\implies z\equiv 0~\text{mod}~4$

But i doubt that this is correct. and also how to deduce expressions for $x,y,z$. Can somebody check?

$\endgroup$
  • $\begingroup$ Statement 1 isn't true. Take, for example, n=7, x=1, y=5 and z=3 $\endgroup$ – André Porto May 24 at 18:47
  • $\begingroup$ i forgot to mention $n\equiv 0\mod~4$ $\endgroup$ – Upstart May 24 at 18:58
  • $\begingroup$ Well, it seems to be a hypothesis to construct the bijection. $\endgroup$ – André Porto May 24 at 19:13
  • $\begingroup$ Yeah, indeed, because of the n/4 on the z' expression. $\endgroup$ – André Porto May 24 at 19:14
  • $\begingroup$ yes indeed it is a hypothesis $\endgroup$ – Upstart May 24 at 19:16
1
$\begingroup$

Let us construct the inverse function. First, fix the parameter $ q=\lfloor (z'-1)/(n/4)\rfloor $.

Analyzing the terms $\Big(1.\mathbf{1}[n/2<x] + 2\cdot \mathbf{1}[n/2<y]\Big)$ on the definition of $z'$, we conclude that:

(i) $q=0 \Rightarrow$ $x, y\leq n/2$;

(ii) $q=1 \Rightarrow$ $x> n/2$ and $y\leq n/2$;

(iii) $q=2 \Rightarrow$ $x\leq n/2$ and $y> n/2$;

(iv) $q=3 \Rightarrow$ $x,y>n/2$.

Recovering $x$:

Analyzing the definition of $x'$, we conclude that

  • If $x'$ is odd then $x'= mod(2(x-1),n) + 1$, and since $1\leq x\leq n$, there are only two possibilities: $$ x'= 2(x-1) + 1\mbox{ or } x'= 2(x-1) - n + 1, $$ the first one when $x\leq n/2$ and the second one when $x> n/2$. Both these cases are expressed, relying on the value of $q$, by: $$ x'=2(x-1) - n\mathbf{1}[q=1\mbox{ or } 3] + 1, $$ which conclusion is made by using the facts (i)-(iv). Therefore, obtaining $x$ in terms of $x'$ above, we get: $$ x=\frac{x'+1+n\mathbf{1}[q=1\mbox{ or } 3 \mbox{ or } 4]}{2} $$
  • If $x'$ is even, then $x'= mod(2(x-1),n) + 2$, and proceeding analogously we get that $$ x=\frac{x'+n\mathbf{1}[q=1\mbox{ or } 3]}{2}. $$

The difference between the two cases above can be expressed by a $\mathbf1$ function as follows: $$ x=\frac{x'+n\mathbf{1}[q=1\mbox{ or } 3]+\mathbf{1}[\mbox{x' is odd}]}{2} $$

Finally, substituing the value of $q$ above, we get $$ x=\frac{x'-n\mathbf{1}\Big[\lfloor(z'-1)/(n/4)\rfloor=1\mbox{ or } 3\Big]+\mathbf{1}[\mbox{x' is odd}]}{2}. $$

Recovering $y$

To recover $y$ the argument is analogous to the one concerning $x$. We find that $$ y=\frac{y'+n\mathbf{1}\Big[\lfloor (z'-1)/(n/4)\rfloor\geq2\Big]+\mathbf{1}[\mbox{y' is odd}]}{2}. $$

Recovering z:

As you said, we can determine $mod(z,4)$ by the following:

  • Both $x'$ and $y'$ are even $\Rightarrow$ $mod(z,4)=0$;
  • Both $x'$ and $y'$ are odd $\Rightarrow$ $mod(z,4)=1$;
  • $x'$ is even and $y'$ is odd $\Rightarrow$ $mod(z,4)=2$;
  • $x'$ is odd and $y'$ is even $\Rightarrow$ $mod(z,4)=3$.

Define $Mod(a,b)$ to be the usual $mod(a,b)$ function, except that it returns $b$ instead of $0$.

Write $z= 4\cdot s + mod(z,4)$, for some $0\leq s \leq n/4$. There are two cases:

  • Case 1. $mod(z,4)=0$. Then, by the definition of $z'$, $$ z'=s + (n/4)\Big(\mathbf{1}[n/2<x] + 2\cdot \mathbf{1}[n/2<y]\Big). $$ Also, since in this case $z=4s$ and $z\neq0$, we have $1\leq s \leq n/4$, and therefore, $s=Mod(z',n/4)$. Consequently, $$ z=4Mod(z',n/4). $$

  • Case 2. $mod(z,4)>0$. Then, by the definition of $z'$, $$ z'=s + 1 + (n/4)\Big(\mathbf{1}[n/2<x] + 2\cdot \mathbf{1}[n/2<y]\Big). $$ Also, in this case, since $z=4s+mod(z,4)>4s$ and $z\leq n$, then certainly, $$ 0\leq s \leq n/4-1\ \Rightarrow\ 1\leq s + 1 \leq n/4, $$ and therefore, $s + 1 = Mod(z',n/4)$. Consequently, $$ z=4(Mod(z',n/4)-1) + mod(z,4). $$

The differences between the cases above may be expressed by a $\mathbf 1$ function as follows: $$ z=4\Big(Mod(z',n/4)-\mathbf{1}[mod(z,4)\neq 0]\Big) + mod(z,4). $$

$\endgroup$
  • $\begingroup$ i guess you didn't edit $q$ to $s$ but thanx for a detailed explaination, i will check it $\endgroup$ – Upstart May 25 at 6:53
  • $\begingroup$ Yeah, sorry about that $\endgroup$ – André Porto May 25 at 10:38
  • $\begingroup$ There are a few errors i guess. 1). $x'=2(x-1)+1$ or $x'=2(x-1)-n$ not $+n$ as you have written, because that part is extra so we fold it back in. $\endgroup$ – Upstart May 26 at 20:43
  • $\begingroup$ i figured out the problems in your equations for $x$ and $y$. Consider the odd case for $x$ . If $(z' \leq n/4~\text{or}~ n/2< z'\leq 3n/4)$ Then the case $x= 2(x-1) +1$ will be implemented. and if $( n/4< z'\leq n/2 ~\text{or}~z'>3n/4)$ then $ 2(x-1) +n +1$ will be implemented $\endgroup$ – Upstart May 27 at 8:10
  • $\begingroup$ Yeah, you are right. We shall fix those mistakes then. You were right about the change of the sign of $n$ (oops). But I didn't understand the other mistake. I guess it ha to do with the values $z'=n/4$, $z'=n/2$, and so on. It's a mistake with the conclusions on the value $q$. One way to fix it is to change the definition of $q$ to $q=\lfloor (z'-1)/(n/4)\rfloor$. $\endgroup$ – André Porto May 27 at 13:33

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.