<p>I am not a CS theory guy. But in ergodic theory this type of mapping is known as <em>finitary</em> 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}}$):</p>

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

<p>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.</p>

CC BY-SA 2.5
2010-11-17T00:54:47.367Z
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.
Aaron Sterling
CC BY-SA 2.5
2010-11-13T00:38:21.283Z
I for one welcome any wacky brainstorming ideas at this point.
Aaron Sterling
CC BY-SA 2.5
2010-11-13T00:41:39.620Z
Note that whether the indices are taken from ℕ or ℤ is irrelevant in this question.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-13T00:04:37.080Z
2010-11-13T00:04:37.080Z
gondolier
<p>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.</p>

<p>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 "<a href="http://math.andrej.com/2009/09/09/constructive-gem-juggling-exponentials/" rel="nofollow">Constructive gem: juggling exponentials</a>".</p>

<p>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:</p>

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

<p>Here is a short note describing the problem in more detail:
<a href="http://www.csc.liv.ac.uk/~cmcq/rec/bib.pdf" rel="nofollow">A conjecture concerning bounded-input bijections of infinite sequences</a>.</p>

<p>Definitions:</p>

<p>A function $f : \prod_{i \in I} X_i \rightarrow \prod_{j\in J} Y_j $ is <em>bounded-input</em> 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})$.</p>

<p>A bijection $f$ is a <em>bounded-input bijection</em> if
it is a bounded-input function.</p>

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

CC BY-SA 2.5
2010-11-14T21:53:01.120Z
Nice question :-) By the way, what is the "simplest" isomorphism between $2^\mathbb{N}$ and $3^\mathbb{N}$ that you know of?
Andrej Bauer
CC BY-SA 2.5
2010-11-11T02:58:53.570Z
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.
Aaron Sterling
CC BY-SA 2.5
2010-11-12T20:13:47.587Z
Although it's not quite the same setup, the construction used at http://cstheory.stackexchange.com/questions/2935/examples-in-which-the-size-of-the-alphabet-geq-2-used-for-an-encoding-matter seems related to this question.
Joshua Grochow
CC BY-SA 2.5
2010-11-13T17:08:44.037Z
The construction I used in my question may look similar, but it deals with injections and surjections, not bijections. Also, the conditions involved deal with prime factorisations, not odd-even-ness.
Alex ten Brink
CC BY-SA 2.5
2010-11-13T18:34:05.453Z
@Alex ten Brink: That's why I posted it as a comment and not an answer :). They might still give someone some inspiration though.
Joshua Grochow
CC BY-SA 2.5
2010-11-13T20:35:21.480Z
@Colin McQuillan: Please consider posting a placeholder answer, so if there is no significant progress by the end of the week, I can award the bounty to you for asking a cool question.
Aaron Sterling
CC BY-SA 2.5
2010-10-10T02:55:17.727Z
It is probably better to copy the definition of “bounded-input bijection” from your note.  I misunderstood the definition until I read it.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-10T08:19:05.827Z
Done. I would like to point out that while the question's motivation comes from category theory semantics, the puzzle itself is combinatorial.
Colin McQuillan
CC BY-SA 2.5
2010-10-10T22:39:57.970Z
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.)
Tsuyoshi Ito
<puzzles><ct.category-theory><topology>
Bounded-input bijections of infinite sequences
Colin McQuillan
# Bounded-input bijections of infinite sequences

(Asked by: username_0 on 2010-10-10)

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. username_1 posted an explanation of what this means on his blog as "[Constructive gem: juggling exponentials](http://math.andrej.com/2009/09/09/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](http://www.csc.liv.ac.uk/~cmcq/rec/bib.pdf).

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.

**Tags:** puzzles, ct.category-theory, topology

> **Comments:**
> **username_5**: It is probably better to copy the definition of “bounded-input bijection” from your note.  I misunderstood the definition until I read it.  
> **username_0**: Done. I would like to point out that while the question's motivation comes from category theory semantics, the puzzle itself is combinatorial.  
> **username_5**: 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.)  
> **username_2**: 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.  
> **username_3**: Although it's not quite the same setup, the construction used at http://cstheory.stackexchange.com/questions/2935/examples-in-which-the-size-of-the-alphabet-geq-2-used-for-an-encoding-matter seems related to this question.  
> **username_4**: The construction I used in my question may look similar, but it deals with injections and surjections, not bijections. Also, the conditions involved deal with prime factorisations, not odd-even-ness.  
> **username_3**: @username_4: That's why I posted it as a comment and not an answer :). They might still give someone some inspiration though.  
> **username_2**: @username_0: Please consider posting a placeholder answer, so if there is no significant progress by the end of the week, I can award the bounty to you for asking a cool question.  
> **username_1**: Nice question :-) By the way, what is the "simplest" isomorphism between $2^\mathbb{N}$ and $3^\mathbb{N}$ that you know of?  

---

## 1 answers

### Answer by username_6 on 2010-11-13. Score: 2

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.

> **Comments:**
> **username_2**: I for one welcome any wacky brainstorming ideas at this point.  
> **username_5**: Note that whether the indices are taken from ℕ or ℤ is irrelevant in this question.  
> **username_2**: 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.  

---

