A strange bijection without fixed points

Question

Is it possible to construct a bijection $F:\mathbb Z \to \mathbb Z$ without fixed points (i.e. such that $F(i)\neq i$ for all $i \in \mathbb Z$) such that for all $j\in\mathbb Z_{\neq 0}$,

$$\lim_{n\to \infty} \frac{1}{n}\sum_{k=0}^{n-1}F(jk)-jk=0?$$

For the moment I'm just able to do the following observation:

Since $F(jk)-jk\neq 0$ for all $j\in\mathbb Z_{\neq 0}, k\in \mathbb{Z}_{\geq 0}$, then for every fixed $j \in \mathbb Z_{\neq 0}$ there must be infinitely many $k\geq 0$ s.t. $F(jk)-jk>0$ and infinitely many $k\geq 0$ s.t. $F(jk)-jk<0$. This, in my mind, implies that $F$ has to be "really chaotic" and at the moment I do not know how to construct such a bijection.

Any idea? Any help?

Answer 1

I will summarize the progress on this problem and then explain some further directions of inquiry.

Antkam answered the question affirmatively, via a randomness argument. Specifically, let $I_k = \{3k-1,3k,3k+1\}$ for $k \in \mathbb{Z}$ and define $F : \mathbb{Z} \to \mathbb{Z}$ by defining it on each $I_k$ via (1) $F(3k-1) = 3k, F(3k) = 3k+1, F(3k+1) = 3k-1$ or (2) $F(3k-1) = 3k+1, F(3k) = 3k-1, F(3k+1) = 3k$, the choice of (1) or (2) being random $\frac{1}{2}-\frac{1}{2}$ (independent as $k$ ranges). We show that for each fixed $j \not = 0$, with probability $1$ it holds that $\lim_{N \to \infty} \frac{1}{N}\sum_{n=0}^{N-1} (F(jn)-jn) = 0$; it will then follow that, with probability $1$, it holds that for each $j \not = 0$, $\lim_{N \to \infty} \frac{1}{N}\sum_{n=0}^{N-1} (F(jn)-jn) = 0$. If $3 \mid j$, then $F(jn)-jn$ is i.i.d. $+1,-1$ with probability $\frac{1}{2}-\frac{1}{2}$ as $n$ ranges, so the sum clearly converges to $0$ almost surely. If $3 \nmid j$, then $(F(jn)-jn)+(F(j(n+1))-j(n+1))+(F(j(n+2))-j(n+2))$ has mean $0$ (since $\{n,n+1,n+2\} = \{0,1,2\}$ mod $3$) and is independent as $n$ ranges over multiples of $3$, so, once again, the sum converges to $0$ almost surely.

(Presumably) building off Antkam's idea, Reinhard Meier answered the question affirmatively, via an explicit construction. In the above notation, define $F$ on $I_0$ via (1), $I_1,I_2$ via (2), $I_3,I_4,I_5$ via (1), $I_6,I_7,I_8,I_8$ via (2), etc., and on $I_{-1},I_{-2}$ via (2), $I_{-3},I_{-4},I_{-5}$ via (1), etc.. Fix $j \not = 0$. If $3 \mid j$, then, after a while, $F(jn)-jn$ has long stretches of $+1$, then long stretches of $-1$, then long stretches of $+1$, etc., but a computation shows that the stretches are not too long to negate all the previous cancellation. If $3 \not \mid j$, then, after a while, $F(jn)-jn$ has long stretches of $+1,+1,-2,+1,+1,-2,\dots$, or $-1,-1,+2,-1,-1,+2,\dots$, so this case is really fine.

A leftover question for the curious pupil is how small we can make $\sum_{n \le N} (F(jn)-jn)$ as a function of $N \to \infty$ (uniformly in $j$). For example, Antkam's answer gives $\sum_{n \le N} (F(jn)-jn) = \Omega(\sqrt{N\log\log N})$ infinitely often for each fixed $j \not = 0$ (law of iterated logarithm), while Reinhard's answer gives $\sum_{n \le N} (F(jn)-jn) = \Omega(\sqrt{N})$ when $j$ is a multiple of $3$. Can we, for example, get an $F$ with $\sum_{n \le N} (F(jn)-jn) = O(\log N)$ as $N \to \infty$ for each fixed $j \not = 0$?

This leftover question is actually really closely related to the Erdös discrepancy problem, if we restrict to bijections $F$ defined as bijections on each $I_k$. Indeed, restricting to $j = 3k$, a multiple of $3$, we want to see how small we can make $\sum_{n \le N} F(3nk) = \sum_{n \le N} \epsilon_{nk}$, where $\epsilon_n$ is $+1$ if we define $F$ on $I_k$ via option (1) and $-1$ otherwise. It is strongly believed that the smallest we can make this is $\log N$, with equality occurring for an example coming from Borwein, Choi, and Croons, in which you let $\epsilon_n$ be defined on primes via $\epsilon_p = 1$ if $p \equiv 1 \pmod{3}$, $\epsilon_p = -1$ if $ p \equiv 2 \pmod{3}$, and $\epsilon_3 = 1$, and then defined on all positive integers so as to make it completely multiplicative. I haven't yet figured out if this example works for our problem here yet (i.e. if we're fine for $j$ not divisible by $3$).

So, nearly certainly, any $F$ with $\sum_{n \le N} (F(jn)-jn) = o(\log N)$ as $N \to \infty$ for each fixed $j \not = 0$ will have to be constructed differently than via defining it on the $I_k$'s.

Answer 2

UPDATE Jan 21: I now think this can be made rigorous, by using the countable additivity axiom. See the end. However, my theory background is not that strong so I'm not sure it works, and comments / corrections are most welcome.

---

Not a rigorous solution / too long for a comment.

It seems like a "locally random" $F$ would work. Specifically, consider this family of $F$, i.e. $F$ of this form:

• Partition $\mathbb{Z}$ into subsets of size $3$ (which I will call triplets) as follows: $A_m = \{3m-1, 3m, 3m+1\} ~\forall m \in \mathbb{Z}$

• For each $A_m$, "randomly" pick one of two fixed-point-free permutations of the $3$ elements. The picks are independent among different intervals, and each permutation is picked with equal prob $=\frac12$. Let $\sigma$ be the permutation picked and define $F(n) = \sigma(n)$ for $n \in A_m$.

E.g. a sample $F$ might map $-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10$ into $0, 1, -1, 4, 2, 3, 7, 5, 6, 9, 10, 8$ respectively.

Now consider the main OP requirement. If $j$ is a multiple of $3$, then $jk$ are the middle elements of triplets, and if the permutations were picked i.i.d. as described, then $\forall k \in \mathbb{N}: F(jk) - jk \in \{+1, -1\}$ with equal prob. Obviously the required limit is $0$ with probability $1$.

If $j$ is not a multiple of $3$, then $j$ is co-prime with $3$, so the $jk$ in the long run would be equal proportions of the beginning, the middle and the end of triplets. For the beginning number of the form $jk = 3m-1, F(jk) - jk \in \{+1, +2\}$ with equal prob, but this is balanced out by the ending numbers of the form $jk = 3m+1$ where $F(jk) - jk \in \{-2, -1\}$ with equal prob. Again, the required limit would be $0$ with probability $1$.

What the above argument says is that, for a random $F$ picked as described, the probability it will meet the requirement for any given $j$ is $1$. However, that does not allow me to conclude that there is an $F$ which satisfies the requirements for all $j$. In my mind here are three possible ways to proceed, but I don't know how to do any of them:

First, maybe there is something akin to Borel-Cantelli that can apply here? Or perhaps we can simply appeal to the countable additivity axiom of probability? See the end for a possible argument along this line. What we're saying is rather similar to saying that in a sequence of fair i.i.d. coin-flips to pick $X \in \{-1, +1\}$, not only the the sample mean $\to 0$ (almost surely), but the sample mean for a countable number of pre-defined subsequences, each of them also $\to 0$ (almost surely).

Second, what if we substitute a "pseudo-random" sequence, such as the binary digits of $\pi$? Then any claim that the (deterministic) $F$ that results violates the OP requirement for a certain $j$ is equivalent to saying the binary digits of $\pi$ satisfy a certain bias. IIRC that would be a huge surprise (although not a proven impossibility).

Third, maybe I'm just over-thinking all this. Perhaps there is a way to pick the permutations (i.e. coin flips) deterministically and prove, using elementary number theory, that the OP requirement is satisfied for all $j$.

Sadly, I don't know how to complete the argument using one of these, or any other method.

---

UPDATE Jan 21: I now think appealing to the countable union axiom works, as follows.

First we will use this re-ordering of $\mathbb{Z}: 0, 1, -1, 2, -2, 3, -3, \dots$ and we will write $j <_r i$ and say $j$ is "earlier" than $i$, if $j$ appears before $i$ in this order.

For any $F$, if it violates the OP requirement for some $j \neq 0$, then there is an "earliest" such $j$ (in the above order) for that $F$. Let $E_i$ be the set of bijections which violate the OP requirement for $j=i$ but not for any earlier $j <_r i$, i.e. $F \in E_i \iff \forall j <_r i$ the limit $=0$ and for $j=i$ the limit either doesn't exist or is non-zero.

Clearly the $E_i$'s are disjoint sets, by construction. Further, for any specific $i$, a random $F$ would meet the OP requirement for $j=i$ almost surely, which implies $P(E_i) = 0$.

Now we appeal to the countable additivity axiom of probability:

$$P( \bigcup_{i \in \mathbb{Z_{\neq 0}}} E_i) = \sum_{i \in \mathbb{Z_{\neq 0}}} P(E_i) = 0$$

But $\bigcup_{i \in \mathbb{Z_{\neq 0}}} E_i$ is the set of bijections that violate the OP requirement for some $i$, so the complement is the set of bijections that meet the OP requirement for all $i$, and this complement has probability $1$.

In short, bijections meeting the OP requirement (for all $j$) not only exist, they have probability $1$. Nevertheless, my argument is non-constructive, so I cannot exhibit such an $F$ explicitly.