Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

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.

share|improve this answer
    
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. –  Triple.J Dec 13 '10 at 7:41
    
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}. –  Douglas S. Stones Dec 13 '10 at 7:54
    
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. –  Triple.J Dec 13 '10 at 8:35
    
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? –  Douglas S. Stones Dec 13 '10 at 9:47
    
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? –  Douglas S. Stones Dec 13 '10 at 10:34

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<i) then
      temp:=A[i];
      A[i]:=A[j];
      A[j]:=temp;
    fi;
    i:=i-1;
  od;
  return A;
end;;

TripleJQuestion2:=function(n)
  local A,B,p,q;
  A:=Concatenation([-n..-1],[1..n]);
  B:=List([1..2*n+1],i->-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.

share|improve this answer
    
Thank you, Stones. Actually this problem is not so important, it's just a math puzzle. –  Triple.J Dec 13 '10 at 12:23

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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