10
$\begingroup$

Given a bijection $f:\mathbb Z \to \mathbb Z$ where $\mathbb Z$ is the set of all integers, does there always exist two bijections $g:\mathbb Z \to \mathbb Z$ and $h:\mathbb Z \to \mathbb Z$ which satisfy $f(n) = g(n) + h(n), ~ \forall n \in \mathbb Z$ ?

Evidently it does while $\mathbb Z$ is replaced with the set of all rational numbers $\mathbb Q$, since $f(q) = 2f(q) - f(q), ~ \forall q \in \mathbb Q$. Nevertheless, $2f$ doesn't maps $\mathbb Z$ onto $\mathbb Z$, thus it's not a bijection on $\mathbb Z$; therefor we need a new construction for the $\mathbb Z$ case.

Firstly we note that   $0 = 0 + 0$   and \begin{align*} 1 &= (-2) + 3, &\qquad -1 &= 2 + (-3),\\ 2 &= 3 + (- 1), &-2 &= (-3) + 1,\\ 3 &= 1 + 2, &-3 &= (-1) + (-2). \end{align*}

It's easy to show that any bijections on the symmetric integer interval $[-3,3]$ can be represented as a sum of two bijections; or equivalently, all integers $a \in [-3,3]$ can be represented as a sum of two others, i.e., $a = b + c$ where $b, c \in [-3, 3]$, while $a,b,c$ exhausted the integer interval $[-3,3]$ respectively, and keeps $0 = 0 + 0$. For convenience, let's denote this fact as $[-3,3] = [-3,3] + [-3,3]$.

Suppose now we have $[-m, m] = [-m, m] + [-m, m]$, then we may obtain $$[-m + aL, ~ m + aL] = [-m + bL, ~ m + bL] + [-m + cL, ~ m + cL],\qquad L = 2m+1,$$ where $a,b,c \in [-n,n]$ for some positive integers $n$, provided $a = b + c$. Well, if $a,b,c$ form a representation, say, $[-n,n] = [-n,n] + [-n,n]$, then we may get a "larger" representation $$[-m - nL, ~ m + nL] = [-m - nL, ~ m + nL] + [-m - nL, ~ m + nL], \qquad L = 2m+1,$$ through the repeatedly use of "small" representations; and obviously, the larger representation "contains" the small representation as a "subrepresentation", since $0 = 0 + 0$. From now on, we may construct a representation $\mathbb Z = \mathbb Z + \mathbb Z$ by induction, start from $[-3,3] = [-3,3] + [-3,3]$. Thus we've proved that any bijections on $\mathbb Z$ can be represented as a sum of two bijections on $\mathbb Z$.

Now a problem rises:

for any integers $n > 2$, is there always a representation $[-n, n] = [-n, n] + [-n, n]$ ?

Note that by our means of "representation", $0 = 0 + 0$ is required; otherwise it's trivial; note also the above approach we've used for resolving the "$\mathbb{Z}$-representation problem" can't reach all cases.

Anyone can answer this question? Please help me.

3 Answers 3

9

Observation: It is sufficient to resolve the question for $f(n)=n$.

Proof idea: If $n=g(n)+h(n)$ for all $n$, then $f(n)=g(f(n))+h(f(n))$. Conversely, if $f(n)=g(n)+h(n)$ then $n=f(f^{-1}(n))=g(f^{-1}(n))+h(f^{-1}(n))$.

So, if some $f$ can be decomposed into two bijections $h$ and $g$, then every $f$ can be decomposed.

So resolving this question amounts to finding a permutation $g$ of $\mathbb{Z}$ for which $n \mapsto g(n)-n$ is also a permutation. Such permutations are called orthomorphisms.

UPDATE: I asked both Ian Wanless and Tony Evans about this, and they simultaneously pointed out that the existence of such an orthomorphism was proved in:

MR0040293 (12,670f) Bateman, P. T. A remark on infinite groups. Amer. Math. Monthly 57, (1950). 623–624. 20.0X

So we can conclude that, yes, it's always possible.

  • 0
    Thanks very much. But note that my question isn't about the case of the abelian group $\mathbb Z$, infact I've proved in above that there are orthomorphisms of $\mathbb Z$ by induction. Indeed my question is: for any $n>2$, is there always an "orthomorphism" of the integer interval $[−n,n]$, which keeps 0 as it's fixed point? Though $[-n,n]$ may not be a group, I think you know the mean of "orthomorphsim" in this context. By the way, sorry for my poor english.2010-12-13
  • 0
    Hmm... I'm not 100% sure I understand. Perhaps you're after orthomorphisms of $Z_{2n+1}$ which always exist (the simplest examples are linear orthomorphisms, e.g. take $i \mapsto 2i \pmod {2n+1}$). Then instead use the reduced residue system {-n,...,n}.2010-12-13
  • 0
    Yes, I know orthomorphisms of $\mathbb Z_{2n+1}$ always exist, and of $\mathbb Z_{2n}$ always dosen't exist. So if I ristrict my question on the residue system {-n,...,n} (mod 2n+1), we can get an orthomorphism easily; but how to transform these orthomorphisms to the orthomorphisms of integer intervals [-n,n], is not so easy.2010-12-13
  • 0
    Okay, I think I understand now. The first question is the motivation, rather than the question you want answered. Give me a moment, I'm just fleshing out the details of a construction. In the meantime, could you tell me if you are insisting on having 0=0+0 as one of the equations?2010-12-13
  • 0
    Hmm... I prepared a nice answer to the question, then realised you did require 0=0+0. Is there any motivation for this restriction, aside from wanting to make the question more difficult?2010-12-13
  • 0
    Yes, 0 = 0 + 0 is required. Otherwise it's easy to construct: 0 = n -n, -1 = (n-2) -(n-1), -2 = (n-4) -(n-2), ..., -n = -n + 0; n = (n-1) +1, n-1 = (n-3) +2, ..., 1 = -(n-1) +n.2010-12-13
  • 0
    I ended up including my answer (which more or less says what you said above) then added a bit about 0=0+0. The catch is, just because a question is more difficult doesn't make it more interesting.2010-12-13
1

Firstly, consider the case when we are not obliged to have the equation 0=0+0.

The question becomes: given $n \geq 1$ does there exist two permutations $g,h$ of $A:=\{-n,-n+1,\ldots,n\}$ such that $n=g(i)+h(i)$ where addition is addition over the integers (and therefore is not closed on $A$).

We can interpret an instance of this question as a set of $n$ non-attacking semiqueens on an $(2n+1) \times (2n+1)$ chessboard (with rows and columns indexed by $A$) such that no semiqueen is in cell $(i,j)$ whenever $i+j \not\in A$. [semiqueens move up-and-down, left-and-right and along one diagonal]

So the instance you cite above is illustrated by this figure:

alt text

Just as with orthomorphisms of $\mathbb{Z}_n$ we can find linear constructions:

alt text

So we can take the equations

  • $0=n+(-n)$, $1=(n-1)+(-n+2)$, up to $n=0+n$, along with
  • $-1=-n+(n-1)$, $-2=(-n+1)+(n-3)$, up to $-n=-1+(-n+1)$.

So, g(n) takes the values $\{n,n-1,\ldots,0\}$ in the first step and $\{-n,-n+1,\ldots,-1\}$ in the second and h(n) takes the values $\{-n,-n+2,\ldots,n\}$ in the first step and $\{n-1,n-3,\ldots,-n+1\}$ in the second step. Hence both g and h are bijections of $A$, and we can clearly see that $i \mapsto g(i)-h(i)$ is also a bijection.

So, yes, I guess it is easy in this case.

Warning: Although the motivation for this question was to prove the existence of an orthomorphism of $\mathbb{Z}$, this is insufficient to prove it.


Now lets consider the case when the equation 0=0+0 is required. We can generate some small random examples, for example, in GAP.

RandomPermutationList:=function(n)
  local A,i,j,temp;
  A:=List([1..n],k->k);
  i:=n;
  while(i>=2) do
    j:=Random([1..i]);
    if(j-n-1+i);
  while(true) do
    q:=RandomPermutationList(2*n);
    p:=Concatenation(List([1..n],i->A[q[i]]),[0],List([1..n],i->A[q[n+i]]));
    if(Set(List([1..2*n+1],i->p[i]-B[i]))=B and p[n+1]=0) then return p; fi;
  od;
  return fail;
end;;

This was successful for $4 \leq n \leq 8$:

alt text

alt text

alt text

alt text

alt text

So, combined with the fact that there are many orthomorphisms of $\mathbb{Z}_n$, it seems very likely that an instance of the desired construction exists for all $n \geq 3$.

But, continuing further (i.e. finding a constructions for all $n \geq 3$) could require considerable effort. If you're really keen on resolving this problem, you could generate lots of random examples, and hope you could generalise enough of them to cover all $n \geq 3$. But why would you want to do this? It's not likely to give a surprising result, and it seems to be a fairly contrived problem (yes, the problem is harder if we assume the equation 0=0+0 is required, but why would anyone be interested in this problem?). And also, unless you somehow build these constructions recursively, you're probably not going to solve the orthomorphisms of $\mathbb{Z}$ existence question.

  • 0
    Thank you, Stones. Actually this problem is not so important, it's just a math puzzle.2010-12-13
0

This question is ancient (for MSE), but I feel compelled to point out that an orthomorphism for $\mathbb Z$ is not even this complicated to construct; in fact it is amenable to a just-do-it proof:

As Douglas observed we can assume $f(n)=n$ without loss of generality. Now construct $g$ and $h$ in stages. In each stage we have already selected values of $g(n)$ and $h(n)$ at finitely many $n$. For each $k\in \mathbb Z$, according to your favorite enumeration of $\mathbb Z$, do:

  1. If $g(k)$ and $h(k)$ are not yet defined, then define $g(k)=i$ and $h(k)=k-i$, where $i$ is prettiest integer such that $g$ does not already hit $i$ and $h$ does not already hit $k-i$.

    (This assumes that prettiness well-orders $\mathbb Z$, but since that is the only demand on the concept, the reader will be able to select a suitable aesthetic here).

  2. If $g$ does not yet hit $k$, then define $g(i)=k$ and $h(i)=i-k$ where $i$ is the prettiest integer such that $g(i)$ and $h(i)$ are still undefined and $h$ does not already hit $i-k$.

  3. As 2, but mutatis mutandis with $g$ and $h$ swapped.

After $\omega$ many steps, $g$ and $h$ are total (because of step 1), surjective (because of step 2 and 3, respectively), and injective (by construction because only values that are not already hit will be chosen).

Before iterating over the $k$s we can select finitely many (consistent) values for $g$ and $h$ just as we please -- so achieving $0=0+0$ if one wants that is trivial.