# Jumping in the integers

Consider infinite digraphs whose vertices are the integers $\mathbb Z$, with the property that there are exactly two arcs coming out of each vertex. (There is no restriction on the number of in-coming arcs.)

The question: is there such a digraph such that for $m,n\in\mathbb Z$, with $m<n$, there is a directed path from $m$ to $n$ of length $O(\log(n-m))$?

This problem is an abstraction of one arising in data structures (imagine a linked list with two links per node). Years ago I was confident I had solved it, but I can't find my notes and right now I only see $O(\log(n-m)^2)$.

In addition to existence, it would be nice if there is an effective algorithm for following the path, i.e. given that you are at $m$ you can quickly figure out how to get to $n$ in $O(\log(n-m))$ steps. Define "quickly" as you like.

-
[Strictly speaking $O(\log(n-m))$ is impossible when $n-m = 1$... But it seems we're both treating this as $O(1 + \log(n-m))$.] –  Noam D. Elkies Sep 12 '11 at 1:01

Yes, such a directed graph exists, with a "quickly" computable path of length $O(\log|n-m|)$ from $m$ to $n$ for any distinct integers $m,n$.

I'll first construct a digraph with this property but with each vertex having out-degree at most $8$, then show how to get from it a digraph of out-degree $2$.

Denote by $v(x)$ the $2$-adic valuation of the integer $x$, which is the unique integer $e \geq 0$ such that $x/2^e$ is an odd integer; conventionally $v(0) = \infty$.

The graph edges emanating from $x$ will be as follows. If $x$ has valuation $e>0$ then $$x \rightarrow x \pm 1, \phantom+ x \pm 2^{e-1}, \phantom+ x \pm 2^e, \phantom+ x \pm 3\cdot 2^e.$$ If $x$ is odd, omit $x \pm 2^{e-1}$ so $x$ goes only to $x \pm 1$ and $x\pm 3$. If $x=0$ then $x\mapsto \pm 1$ only.

Then:

(i) For each $e \geq 0$, the integers of valuation $e$ constitute an arithmetic progression of common difference $2^{e+1}$. We can get from such $x$ to $x \pm 2^{e+1}$ in two steps: if $e=0$ then add or subtract $1$ twice; if $e>0$ then add or subtract $2^{e-1}$ and then $3 \cdot 2^{e-1}$.

(ii) If $v(x) = e$ and $|n-m| \leq 2^e$ we can get from $m$ to $n$ in at most $2 \phantom. \log_2 |n-m| + 1$ steps. Indeed if $|n-m| = 2^e$ one step suffices, so assume $|n-m| < 2^e$ and then $|n-m| \in [2^d, 2^{d+1})$ with $d < e$. By symmetry we may assume $n>m$. Then $$m \rightarrow m + 1 \rightarrow m + 2 \rightarrow m+4 \rightarrow \cdots \rightarrow m+2^d$$ in $d+1$ steps, and then in a further $d - v(n)$ steps we reach $n$ by writing $$n = m + 2^d + 2^{d-1} \pm 2^{d-2} \pm 2^{d-3} \pm \cdots \pm 2^{d-v(n)}.$$

(iii) If $v(m) = e < f$, and $n$ is the integer of valuation exactly $f$ that's nearest to $m$, then we can get from $m$ to $n$ in $f-e$ steps. At the $i$-th step, add either $\pm 2^{e+i-1}$ or $\pm 3 \cdot 2^{e+i-1}$ to reach a number of valuation exactly $e+i$; there are two choices, so take the one closer to $n$. The distance to $n$ always stays below $2^f$ so at step $f-e$ we hit $n$.

(iv) Finally, suppose $m$ is odd and $|n-m| \in [2^k, 2^{k+1})$. Find $n'$ of valuation $k$ such that $|n-n'| \leq 2^k$. Thus $|m-n'| < 3 \cdot 2^k$. By (iii), in $k$ steps we get from $m$ to some $n_1$ such that $|m-n_1| < 2^k$ and $v(n_1) = k$. So either $n_1=n'$ or $n_1 = n' \pm 2^{k+1}$, and in the latter case we reach $n'$ in a further two steps using (i). Then in at most $2k+1$ further steps we reach $n$ using (ii).

We are done, in a total of $3 \phantom. \log_2 |n-m| + O(1)$ steps, because if $m$ is not odd then we can use our first step to move to the odd number $m \pm 1$ closer to $n$.

Now to get from out-degree $8$ down to $2$: for each $x \in {\bf Z}$ choose $f_i(x)$ for $i=0,1,2,\ldots,7$ so that $\{f_0(x),f_1(x),f_2(x),\ldots,f_7(x)\}$ is the set of integers reachable from $x$ (with repetitions if $x$ is odd or zero). Define a new graph of out-degree $2$ as follows: write every integer as $8x+i$ for some $x \in \bf Z$ and $i\in\{0,1,2,\ldots,7\}$, and then $8x+i \rightarrow 8f_i(x)$ and $8x+i \rightarrow 8x+i'$ where $i'=0$ if $i=7$ and $i'=i+1$ otherwise. That is, we partition $\bf Z$ into directed $8$-cycles, which consumes only one outgoing edge per integer and leaves us with $8$ further edges per cycle to assign as we wish, letting us use our graph of out-degree $8$. Each step of our algorithm then expands to at most $8$, because we might have to take as many as $7$ steps cycling around until we reach the correct $i$ to make the next step in our original graph, and then at the end we might still have to spend an extra $7$ steps to reach the target $n$ within its cycle. But that's still at most $24 \phantom. \log_2 |n-m| + O(1)$ steps, and still with an explicit and "quick" algorithm.

[EDIT we can reduce $3 \phantom. \log_2 |n-m| + O(1)$ to $\frac52 \log_2 |n-m| + O(1)$ by compressing $$m \rightarrow m + 1 \rightarrow m + 2 \rightarrow m+4 \rightarrow \cdots \rightarrow m+2^d$$ to $$m \rightarrow m + 1 \rightarrow m + 4 \rightarrow m+16 \rightarrow \cdots \rightarrow m+2^d,$$ and there's probably another multiple of $\log_2|n-m|$ to be saved by permuting $f_0(x),f_1(x),f_2(x),\ldots,f_7(x)$ to reduce the number of steps spent within directed $8$-cycles.]

-
That's great! My recollection is that there is a solution with one edge going just to the next vertex (x->x+1), and the other edge going forward some distance. Can you see that, or rule it out? –  Brendan McKay Sep 4 '11 at 14:48
Don't you need edges going backward? Gerhard "Ask Me About System Design" Paseman, 2011.09.04 –  Gerhard Paseman Sep 4 '11 at 17:42
@Brendan: i) Thanks! ii) Without backtracking I only see the same $\log^2$ construction that I guess you found, but I can't immediately prove that the directed distance cannot be $O(\log(n-m))$.  @Gerhard: The original question specified $m<n$, and backwards edges aren't necessary to get from any integer to any larger integer, though they might be needed to achieve the desired $O(\log(n-m))$ distance. –  Noam D. Elkies Sep 4 '11 at 17:53