Suppose that $k$ is a positive integer. A bijective map $f : Z \to Z$ is said to be $k$-jumpy if $|f(z) - z| \le k$ for all integers $z$. Is it that case that for every $k$, each $k$-jumpy map is a composition of $1$-jumpy maps? It is well known that this is the case when the support of the map is finite.
Problem
Source: Balkan MO Shortlist 2013 A7 BMO
Tags: composition, algebra, mapping, bijection, bijective function, positive integers
GorgonMathDota
30.03.2020 15:45
Bump this.
TLP.39
25.04.2020 12:54
I believe that there are some typos in the problem statement. If $Z$ is the set of integers, then the only 1-jumpy map is the identity function.
parmenides51
25.04.2020 16:08
I had a typo in the inequality, the correct is $|f(z) - z| \le k$ and not $|f(z) - z| < k$, thanks for noticing that something was not ok
GorgonMathDota
03.05.2020 19:56
Bump again!
BlazingMuddy
04.05.2020 05:06
Yes.
NoteBut I don't think that it is necessarily a composition of at most $k$ $1$-jumpy maps.
We analyze the property of $k$-jumpy maps for all $k \geq 1$. First, observe that an inverse of a $k$-jumpy map is also $k$-jumpy.
LemmaLet $f$ be a $k$-jumpy map. If there exists an integer $x$ such that $f(x + i) = x + k + i$ for all $i = 0, 1, \ldots, 2k - 1$, then $f(n) = n + k$ for all integers $n$. Similarly, if there exists an integer $x$ such that $f(x + i) = x - k + i$ for all $i = 0, 1, \ldots, 2k - 1$, then $f(n) = n - k$ for all integers $n$.
ProofThe proofs for these two statements are analogue, so we will just prove the first statement. We will use induction.
Suppose that for some $j \geq 2k$, we have $f(x + i) = x + k + i$ for all $0 \leq i < j$. Consider that $x + j - k \leq f(x + j) \leq x + j + k$. But all values between $x + j - k = f(x + j - 2k)$ and $x + j + k - 1 = f(x + j - 1)$ have been taken. So, $f(x + j) = x + j + k$.
By a similar approach, we can conclude that $f(x - 1) = x + k - 1$, and induction to the left finishes the proof. Note that the base case has been established by the lemma hypothesis.
Now, we induct on $k$, with the base case $k = 1$ being trivial.
Fix $k \geq 2$, suppose that $f$ is a $k$-jumpy map, and all $(k - 1)$-jumpy maps are a (finite) composition of $1$-jumpy maps. Our goal is to construct a bijective function $g$, consisting of finitely many $1$-jumpy maps, such that $g \circ f$ is a $(k - 1)$-jumpy map. Then, $f = g^{-1} \circ g \circ f$ would be a finite composition of $1$-jumpy maps.
If either $f(x) = x + k$ for all $x \in \mathbb{Z}$ or $f(x) = x - k$ for all $x \in \mathbb{Z}$, then can just pick either $g(x) = x + 1$ or $g(x) = x - 1$. So, suppose that $f$ is not those two functions. Let $S = \{x \in \mathbb{Z} | f(x) = x + k\}$. Let $T = \{x \in S | x - 1 \not\in S\}$, and for each $x \in S$, let $\ell_x$ be the positive integer such that $x, x + 1, \ldots, x + \ell_x - 1 \in S$ but $x + \ell_x \not\in S$. By the lemma, $S$ consists of blocks of consecutive integers, the length of each is less than $2k$, so $\ell_x < 2k$.
Fix $x$, and fix $y_x = f^{-1}(x + k - 1)$. By bijectivity and property of $S$, $x + 2k - 1 \geq y_x \geq x + \ell_x$. Now, consider the value swap between $f(y)$ and $f(x + \ell_x - 1)$. Then, swap $f(y)$ and $f(x + \ell_x - 2)$, and so on, until finally we swap the value of $f(y)$ and $f(x)$. This consists of $\ell_x \leq 2k - 1$ swaps. The final result is $f(x + i) = x + i + k - 1$ for each $0 \leq i \leq \ell_x - 1$ and $f(y_x) = x + \ell_x + k - 1$, so $1 - k \leq \ell_x - k \leq f(y_x) - y_x \leq k - 1$. On the other hand, these swaps are independent between each $x \in T$ ($y_{x_1} \neq y_{x_2}$ for each $x_1 \neq x_2$ in $T$). Hence, the collections of swaps at each step for all $x \in T$ can be merged as one collection of swaps, giving us a total of $\max\{\ell_x : x \in S\} \leq 2k - 1$ collections of swaps. But these collections of swaps form one $1$-jumpy mapping. Thus, these swap operations form a composition of $2k - 1$ $1$-jumpy maps, say $g$.
Now, $(g \circ f)(x) \neq f(x)$ if and only if $x \in S$ or $x - 1 \in S$. But as shown above, for all $x \in S$, $(g \circ f)(x) = x + k - 1$.
We do a similar operation using the set $S' = \{x \in \in \mathbb{Z} | g(f(x)) = x - k\}$ instead, resulting in a function $h$, a composition of $2k - 1$ $1$-jumpy maps, such that for all $x$ with either $x \in S'$ or $x + 1 \in S'$, $h(g(f(x))) = x - k + 1$, and for all other $x$, $h(g(f(x))) = x$. Thus, $h \circ g \circ f$ is a $(k - 1)$-jumpy map. The desired bijective function is $h \circ g$.
The induction step is done, so we are done.
We also proved something stronger: A $k$-jumpy map is a composition of at most $2k^2 - 1$ $1$-jumpy maps.
I am pretty sure that the bound $2k^2 - 1$ can be lowered to $k^2$.
Maybe, consider instead both $S$ and $S'$ simultaneously when building the reduction operation.
On the other hand, if indeed $k^2$ is an upper bound, is it sharp?