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.

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$)

share|improve this question
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
add comment

3 Answers 3

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'$.)

share|improve this answer
add comment

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.

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

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.

share|improve this answer
add comment

Your Answer


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.