28
$\begingroup$

Here is a puzzle I haven't managed to solve. I would like to know if this problem is already known, or has an easy solution.

It is possible to define a bijection $ 3^\mathbb{N} \cong 5^\mathbb{N} $ using the properties of bicartesian closed categories. Andrej Bauer posted an explanation of what this means on his blog as "Constructive gem: juggling exponentials".

This bijection has an interesting property: it is "bounded-input" meaning that each component of the output depends only on boundedly many components of the input. However, for $k,l\geq 2$ it seems that this construction can only show that $ k^\mathbb{N} $ and $ l^\mathbb{N} $ are isomorphic if $k$ and $l$ are both odd or both even. This leaves open the question:

Is there a bounded-input bijection from $ 2^\mathbb{N} $ to $ 3^\mathbb{N} $?

Here is a short note describing the problem in more detail: A conjecture concerning bounded-input bijections of infinite sequences.

Definitions:

A function $f : \prod_{i \in I} X_i \rightarrow \prod_{j\in J} Y_j $ is bounded-input if there exists an integer $k$ such that each component of the output of $f$ depends only on at most $k$ components of the input. More formally, $f$ is bounded-input if for each index $j \in J$ there are indices $i_1,\dotsb,i_k \in I$ and a function $f_m : X_{i_1}\times\dotsb\times X_{i_k} \rightarrow Y_j$ such that for all $x \in X$ the component $f(x)_j$ equals $f_j(x_{i_1},\dotsb,x_{i_k})$.

A bijection $f$ is a bounded-input bijection if it is a bounded-input function.

A bijection $f$ is a bounded-input isomorphism if it and its inverse are bounded-input functions. This is also interesting.

$\endgroup$
  • $\begingroup$ It is probably better to copy the definition of “bounded-input bijection” from your note. I misunderstood the definition until I read it. $\endgroup$ – Tsuyoshi Ito Oct 10 '10 at 2:55
  • 1
    $\begingroup$ Done. I would like to point out that while the question's motivation comes from category theory semantics, the puzzle itself is combinatorial. $\endgroup$ – Colin McQuillan Oct 10 '10 at 8:19
  • 1
    $\begingroup$ The most annoying thing about this problem is that it looks easy! All sets $(2k)^{\mathbb{N}}$ are bounded-input isomorphic to each other, and so are all sets $(2k+1)^{\mathbb{N}}$. I cannot see any reason why these two cannot be made bounded-input isomorphic by using a variation of the isomorphisms used in the existing proofs, but such attempts seem to fail. Aghh. (I have no experience in this field, so I may be off the mark.) $\endgroup$ – Tsuyoshi Ito Oct 10 '10 at 22:39
  • 1
    $\begingroup$ I really like this conjecture, and it's been hanging out for a month now. I'll give a bounty to anyone who solves it or makes substantial progress in either direction. $\endgroup$ – Aaron Sterling Nov 11 '10 at 2:58
  • 3
    $\begingroup$ Nice question :-) By the way, what is the "simplest" isomorphism between $2^\mathbb{N}$ and $3^\mathbb{N}$ that you know of? $\endgroup$ – Andrej Bauer Nov 14 '10 at 21:53
2
+50
$\begingroup$

I am not a CS theory guy. But in ergodic theory this type of mapping is known as finitary isomorphisms. For example people considered if two Bernoulli sequences of the same entropy is finitarily isomorphic or not. For example (this is one-sided shift because it seems you are concerned with $P^{\mathbb{N}}$ rather than $P^{\mathbb{Z}}$):

A. Del Junco, “Finitary codes between one-sided Bernoulli shifts,” Ergodic Theory Dynamical Systems, vol. 1, pp. 285–301, 1981.

P.S. I intend to leave this as a comment but I cannot due to lack of reputation. Let me know if it is completely off-topic then I will delete it.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I for one welcome any wacky brainstorming ideas at this point. $\endgroup$ – Aaron Sterling Nov 13 '10 at 0:38
  • 2
    $\begingroup$ Note that whether the indices are taken from ℕ or ℤ is irrelevant in this question. $\endgroup$ – Tsuyoshi Ito Nov 13 '10 at 0:41
  • $\begingroup$ I've awarded the full bounty to this answer, because, if I did nothing, the answer would receive half the bounty anyway, as the most upvoted (and having received at least two votes). If someone posts a full or partial proof at a later date, and I see it, I'll probably start another bounty, to award rep to the solver. $\endgroup$ – Aaron Sterling Nov 17 '10 at 0:54
0
$\begingroup$

I think an isomorphism between $k^\mathbb{N}$ and $2^\mathbb{N}$ should be provided by any collection of exclusive and exhaustive binary prefixes of size $k$, for example for $k = 3$ we could us "0", "10", and "11". In more general, we can use "0", "10", "110", ..., "11...10", "11...11" where the second to last has $k - 2$ ones and the last has $k - 1$.

The exclusive and exhaustive nature allows us to define the inverse ($2^\mathbb{N} \to k^\mathbb{N}$) in the obvious fashion.

The boundedness in the forwards direction is easy since each input digits provides at least one output digit the $i$th binary digit is easily determined by no more than the first $i$ $k$-ary digits.

The boundedness in the backwards direction is a little uglier. With the prefix collection I gave above each $k$-ary digit "reads" from at most $k$ binary digits and so the $i$th $k$-ary digit is determined by no more than the first $k i$ binary digits.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This is not bounded-input in either direction. According to the definition of a bounded-input function, you need a uniform bound on the number of input variables which each output variable depends. In the forward direction of your mapping, the i-th output variable depends on the first i input variables, so there is no uniform bound. In the backward direction, the i-th output variable depends on the first ki input variables. $\endgroup$ – Tsuyoshi Ito Nov 10 '10 at 4:40
  • 1
    $\begingroup$ D'oh. I'm going to go read the question for the 1.5th time. :( $\endgroup$ – Keith Amling Nov 10 '10 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.