# Can every line or every j-plane contain all integers exactly once in $\mathbb N^i$

For which pairs of integers $0<j<i$, is there a function $f:\mathbb N^i \to \mathbb N$, $f(x_1,x_2,...,x_i)$ which outputs every positive integer exactly once when any $i-j$ of the variables are kept constant on any $(i-j)$-tuple of positive integers, while the other $j$ variables are varied over all $j$-tuples of positive integers?

And is there a $g$, defined on all infinite sequences of positive integers, such that for all such sequences, if we replace any one element by a variable, say $x$, then $g(x)$ is a bijection between the integers? (ie. $j=1, i=\infty$)

-
There is always such a function if $j=1$ and $i$ is finite: take the bitwise exclusive-or. (With the convention that $\mathbb{N}$ contains 0 - obviously this choice doesn't affect the question.) –  Colin McQuillan Jan 6 '12 at 13:05

For $i=\infty$ and $j=1$ there is such a function, if we assume the axiom of choice. I'll use the convention that $\mathbb{N}$ contains zero. Say that two sequences are equivalent if they differ in finitely many places, and choose a representative of each equivalence class. Define $f$ on a sequence $x$ by taking the representative $x'$ of its class and setting $f(x)=\bigoplus (x_i\oplus x_i')$ where $\oplus$ is also bitwise exclusive-or. (Note that there are only finitely many non-zero values $x_i\oplus x_i'$.)

-

Here is an answer for $0<j<i$ (and $i$ finite, though you could extend to $i=\infty$ using the trick in my other answer).

Pick a prime $p$ larger than $ij$. We will think of integers as being infinite sequences modulo $p$, and write $x\oplus x'$ for addition modulo p "without carrying". Also if $a$ is an integer mod $p$ then $ax$ is "digitwise" multiplication by $a$. I hope that makes sense.

Let $a$ be a primitive root modulo $p$. Define $f:\mathbb{N}^i\rightarrow \mathbb{N}^j$ by setting $f_k(x_1,\cdots,x_i)$ to $x_1 \oplus a^k x_2 \oplus a^{2k} x_3 \oplus \cdots \oplus a^{(i-1)k} x_i$. It doesn't matter that the codomain is $\mathbb{N}^j$ because this set is countable. And your condition boils down to checking that a Vandemonde matrix is non-singular.

-
I don't see why you couldn't have edited this into the previous answer... –  Asaf Karagila Jan 6 '12 at 15:31

Start with the first non-trivial case, $i=2$ and $j=1$. In this case you can think of the desired $f$ as a binary operation $\oplus$ on $\mathbb{N}$, and you want each row and column of the operation table for $\oplus$ to be a permutation of $\mathbb{N}$. One obvious way to ensure that is to make $\oplus$ a group operation on $\mathbb{N}$. The most familiar operations on $\mathbb{N}$ aren’t group operations, so perhaps the easiest way to accomplish this is to replace $\mathbb{N}$ temporarily by a countably infinite set on which we do know a natural group operation. Two come to my mind immediately: ordinary addition on $\mathbb{Z}$, and symmetric difference, which I’ll denote by $\triangle$, on the set of finite subsets of $\mathbb{N}$, which I’ll denote by $\mathscr{F}$.

Let $\varphi:\mathbb{N}\to\mathbb{Z}$ be any bijection; then setting $$m\oplus n=\varphi^{-1}\Big(\varphi(m)+\varphi(n)\Big)$$ makes $\oplus$ a group operation on $\mathbb{N}$. Alternatively, we could let $\varphi:\mathbb{N}\to\mathscr{F}$ be a bijection and set $$m\oplus n=\varphi^{-1}\Big(\varphi(m)\triangle\varphi(n)\Big)\;.\tag{1}$$ This second alternative is attractive, because there’s a very natural choice for the bijection $\varphi$: if $$n=\sum_{k\ge 0}\frac{b_k}{2^k}\;,$$ where $b_k\in\{0,1\}$ for each $k\in\mathbb{N}$, is the unique binary representation of $n$, let $\varphi(n)=$ $\{k\in\mathbb{N}:b_k=1\}$. If you write all of your integers in binary and use $(1)$ to define $\oplus$, $m\oplus n$ is simply the exclusive OR (or non-carrying sum) of $m$ and $n$.

The next question is how to generalize this. If $i$ is finite and $j=1$, the most straightforward generalization works: let $f\big(\langle n_1,\dots,n_i\rangle\big)=n_1\oplus\cdots\oplus n_i$. Then if $1\le k\le i$ and $a=$ $n_1\oplus \cdots\oplus n_{k-1}\oplus n_{k+1}\oplus\cdots\oplus n_i$, $f\big(\langle n_1,\dots,n_i\rangle\big)=a\oplus n_k$ for each value of $n_k$, i.e., we get a row of the operation table for $\oplus$, which is a permutation of $\mathbb{N}$. For $j>1$, however, we need a new idea.

Part of it is a different application of an old one, namely, that we can substitute any countably infinite set for $\mathbb{N}$ and use a suitable bijection to translate between this set and $\mathbb{N}$. The more substantial part is that it might be easier to get a map $f:\mathbb{N}^i\to\mathbb{N}^j$ with the property that if $S$ is a subset of $\mathbb{N}^j$ obtained by fixing $j-i$ coordinates arbitrarily and allowing the remaining $i$ to range over $\mathbb{N}$, $f\upharpoonright S:S\to\mathbb{N}^i$ is a bijection. If we had that, we could compose it with a bijection $\mathbb{N}^j\to\mathbb{N}$ to get the desired map.

A more familiar setting for maps of the form $S^j\to S^i$ is elementary linear algebra, which also offers easy ways to tell whether a map is a bijection. To take advantage of this, let’s replace $\mathbb{N}$ by $\mathbb{Q}$ (via any handy bijection) and look for a linear transformation $f:\mathbb{Q}^i\to\mathbb{Q}^j$ with the property that if $S$ is a subset of $\mathbb{Q}^j$ obtained by fixing $j-i$ coordinates arbitrarily and allowing the remaining $i$ to range over $\mathbb{Q}$, $f\upharpoonright S:S\to\mathbb{Q}^i$ is a bijection.

Such a linear transformation can be represented by its matrix $A$, which will be $j\times i$, and the condition on the restrictions of the map translates to the requirement that each $j\times j$ submatrix of $A$ (obtained by deleting $i-j$ columns) be invertible. (The resulting maps are affine, rather than linear, thanks to the fixed coordinates, but this is not a problem.) All that’s needed, then, is a set of $i$ vectors in $\mathbb{Q}^j$ with the property that any $j$ of them are linearly independent to serve as the columns of $A$, and it’s clear that such a set exists: it can be chosen one at a time, since at each stage only finitely many $(j-1)$-dimensional subspaces of $\mathbb{Q}^i$ need be avoided by the new vector. The computational details might get a bit messy, but this approach clearly does show that functions of the desired kind exist whenever $0<j<i<\omega$.

At about this point I finally realized that Colin McQuillan used the same basic idea in his answer, though in a way that avoids introducing $\mathbb{Q}$; his answer is so concise that I simply didn’t see what he was doing until I’d done something similar myself. His solution of the case $i=\omega,j=1$ is considerably less opaque, but as long as I’ve done this much already, I’ll expand on it a little.

The trick is in a sense to reduce the problem to the case of finite $i$ and $j=1$, though the value of $i$ depends on the choice of $x\in\mathbb{N}^\mathbb{N}$. For $x,y\in\mathbb{N}^\mathbb{N}$ write $x\sim y$ iff $\{k\in\mathbb{N}:x_k\ne y_k\}$ is finite; it’s easy to check that $\sim$ is an equivalence relation. Let $X\subseteq\mathbb{N}^\mathbb{N}$ intersect each $\sim$-class in a singleton, and for each $x\in\mathbb{N}^\mathbb{N}$ let $\hat x$ be the unique element of $X$ such that $x\sim\hat x$. Thus, $\{k\in\mathbb{N}:x_k\oplus\hat x_k\ne 0\}$ is finite for each $x\in\mathbb{N}^\mathbb{N}$, where $\oplus$ is as in $(1)$ above, and the function $$f(x)=\bigoplus_{k\in\mathbb{N}}(x_k\oplus\hat x_k)$$ is well-defined.

Now fix $x\in\mathbb{N}^\mathbb{N}$ and $k\in\mathbb{N}$, and for each $n\in\mathbb{N}$ let $x^n$ be the unique element of $\mathbb{N}^\mathbb{N}$ such that $$x^n_r=\begin{cases}n,&\text{if }r=k\\ x_r,&\text{if }r\ne k\;; \end{cases}$$

clearly $\widehat{x^n}=\hat x$ for each $n\in\mathbb{N}$. Thus, if $$m=\hat x_k\oplus\bigoplus_{r\in\mathbb{N}\setminus\{k\}}(x_r\oplus\hat x_r)\;,$$ then $f(x^n)=n\oplus m$ for each $n\in\mathbb{N}$, which runs over $\mathbb{N}$ as $n$ does.

-