2

What would it take to create a feasibly computable injective function sending elements of $\mathbb{Z}_{k}$ (for the largest possible $k$) into, say, the set of distinct states of a bag of $n$ freely tumbling 3x3x3 standard Rubik's Cubes without twisted corners? I thank commenter “Karl” for pointing out that the lexographic ordering of possible bag states exists, but is not feasible to directly compute in the general case.

$\text{log}_2{({8! \times 3^7 \times \frac{12!}{2} \times 2^{11}})} \approx 65.229 \gt 64$, so I can clearly see that at least injecting $\mathbb{Z}_{2^{64}}$ is possible in the single-cube case, and I thank Daniel Schepler for an enlightening comment making that possibility a reality by suggesting to use mixed-base arithmetic as an essentially trivial bijection, which is easily computed in a reasonable amount of time, with the set of positive integers less than the order of the group.

My original expansion of the question remains, however: if you have multiple otherwise indistinguishable cubes tumbling freely together (e.g. in a drawer), I believe the number of bits stored per cube should be $\text{log}_2{({ \binom { 8! \times 3^7 \times 12! \div 2 \times 2^{11} + n - 1 } {n}} )} \div n$; this doesn't drop below $64$ until $n=5$, so, if my math is correct, then one could even theoretically create a function that works as a codec to store arbitrary 256-bit blobs in “rubik's socks” (containers with 4 standard cubes inside of them).

Has such a function ever been discussed, proposed, or invented before now?

Approximately how much effort would it be to create it? Would it be an hour's labor? An afternoon's labor? A dissertation's worth of labor? Or would it, like the 1-cube case, only take a few seconds of lucky insight to nail down?

JamesTheAwesomeDude
  • 235
  • 1
    I think you have the inequality the wrong way round. You need to go up to $2^{66}$. I think it should be possible, because there are ways of ordering the elements of a group like this, but I am not sure what the point of doing it is. – Derek Holt May 04 '23 at 17:08
  • 2
    The point of doing it would (per the [tag:recreational-mathematics] tag) be fun — the idea to store something like a cryptographic key in such a whimsical medium might be usable as an element of an ARG puzzle, etc. – JamesTheAwesomeDude May 04 '23 at 17:17
  • Also, why would $2^{66}$ be required? I want to store a 64-bit integer, so if the space has 65-and-a-half bits, there should be plenty of room to store (inject) a slightly smaller number— the unused elements of the codomain only serve as a smidgen of error detection if anything, no? – JamesTheAwesomeDude May 04 '23 at 17:19
  • Use [tag:tag-name] to create a link to the tag tag-name. Use *text* for text. – Shaun May 04 '23 at 17:19
  • You are right about the order of the group, so of course it's possible. This seems to be more of a problem of defining how nice you want the function. It can't be a homomorphism as the order of the Rubik's cube group is not divisible by $2^64$. – D. Song May 04 '23 at 17:24
  • Also, your formula for the number of states of $n$ unordered cubes cannot be correct as it is not an integer for large $n$. The numerator has no prime factors above 11 but the denominator $n!$ can have arbitrarily large prime factors. – D. Song May 04 '23 at 17:25
  • As I noted, the non-1:1 mapping is actually a slight advantage since it gives at least a smidgen of error detection; the extra redundancy could also be burned as slack to soak the unordering penalty if creating multi-cube bundles. I think you're right about the formula I proposed for multi-cube state count being slightly wrong, though. – JamesTheAwesomeDude May 04 '23 at 17:28
  • 1
    I don't see the difficulty in creating an explicit bijection between integers less than the order of the group, and Rubik's cube configurations. For example, treat the integer as having digits of mixed base $8,7,\ldots,2$ to specify edge positions, $12,\ldots,3$ for corner positions (where then the two remaining corners are uniquely determined), then 11 digits in base 2 for edge orientations (the remaining edge orientation is uniquely determined), then 7 digits in base 3 for corner orientations (the remaining corner orientation is uniquely determined). – Daniel Schepler May 04 '23 at 18:34
  • @DanielSchepler That's a very clever approach, but I think it only gets part of the way to a solution: doesn't that leave unaddressed the big question of how you avoid mapping numbers to unreachable states— such as states that require disassembling the whole cube? – JamesTheAwesomeDude May 04 '23 at 19:31
  • 1
    I was already mentioning the restrictions that ensure you don't get unreachable states: cutting off the permissible permutations of corners by half, cutting the permissible edge orientations by half, cutting the permissible corner orientations by one third. – Daniel Schepler May 04 '23 at 19:49
  • Since you've already got a single-cube scheme and an ordered list of cubes could just be treated as concatenated data, the interesting part of this question is the fact that the cubes are indistinguishable except by their states. There ought to be a general solution to this (for any unordered bag of stateful objects) that doesn't depend much on the details of Rubik's cubes. – Karl May 07 '23 at 06:49
  • But you should probably clarify some requirements on the encoding/decoding scheme. Otherwise, why not just let each drawer state represent its index in the lexicographically-ordered list of all possible distinguishable states? – Karl May 07 '23 at 06:50
  • @Karl Thanks for talking through that detail with me. I forgot that the lexographic-ordering mapping exists; it's not what I'm looking for, but it does indeed fit the question as I originally posed it. I'll clarify my requirements. (Ask a fish what water is, or a computer scientist what "feasibly computable" is...) – JamesTheAwesomeDude May 07 '23 at 16:26
  • 1
    I think the lexicographic solution is pretty easy to implement (by modeling the entire list as a recursive lazy concatenation of sublists that can calculate their length without recursing). By the way, $\binom nk$ isn't exactly right since duplicate elements are possible. There are $\binom{n+k-1}k$ multisets of size $k$ with elements from $[n]$. – Karl May 07 '23 at 17:42
  • 1
    Related: https://math.stackexchange.com/questions/1368526/fast-way-to-get-a-combination-given-its-position-in-reverse-lexicographic-or/1370461#1370461 – Karl May 19 '23 at 00:12

1 Answers1

1

Has such a function ever been discussed, proposed, or invented before now?

I was not able to find any prior art on the specific idea of “scrambled Rubik’s Cubes as data storage medium”.

To reify this idea completely required 2 steps:

  1. Injecting integers into cube scrambles

  2. Injecting integers into multisets of integer representatives of cube scrambles

Approximately how much effort would it be to create it? … A dissertation's worth of labor?

Each of these steps, thankfully, turned out to be a pretty straightforward application only of existing techniques; no new research was required to solve this!

The first step can be done (h/t Daniel Schepler from Math Overflow) by putting the input integer in a particular mixed radix form, then applying the Fisher–Yates algorithm (or any true shuffle algorithm) to scramble the pieces of the cube with the integer's digits in lieu of random numbers; this creates a bijection—needing no discoveries newer than 1938. (Additional storage can be got by using further digits to twist the corners and flip the edges; though care must be taken to avoid prescribing illegal scrambles.)

The second step can be done (h/t pseudonymous “Y. Beer” from Grant Sanderson's Summer of Math Exposition creators' forum) by treating the bag as a multiset of (integer representatives of) cube scrambles, then applying the combinatorial representation of integers—which was at least invented by 2005.

Details

1. $\mathbb{Z}_n \leftrightarrow \text{scramble}$

Legal scrambles of a single Rubik's cube can be modeled as a mixed-radix number, as follows:

  • Eleven of the radices are $12, 11, \dots, 2$; their digits are consumed in lieu of random values in a pseudo-shuffle of the edge pieces.

  • Six of the radices are $8, 7, \dots, 3$; their digits are likewise consumed as inputs to the same pseudo-shuffle on the corner pieces. (The last swap here is constrained to keep the resulting scramble legal.)

  • Eleven of the radices are $2$; their digits determine the orientation of the first eleven edge pieces. (The orientation of the last edge piece is constrained by legality.)

  • Seven of the radices are $3$; their digits determine through what angle the first seven corner pieces will be twisted. (The twist of the last corner is likewise constrained by legality, so that the total twist of all corners is $0 \text{ mod } 3$.)

  • (Obviously, if desired, this can be generalized pretty easily to variant cubes such as picture cubes, by adding extra radices for the extra degrees of freedom, taking care to divide out any constraints on them.)

Now that you've got a bijection between $\mathbb{Z}_{\text{the order of a Rubik's orbit}}$ and concrete scrambles within that orbit, it's straightforward to store your 65-and-a-quarter-ish bits of entropy in the cube.

But, obviously, we're not done yet. If you want to store more than 1 cube in a bag, and have that bag encode a commensurately larger integer, inefficiencies from the obvious "naive" scheme of spending the high bits on synthetically ordering the cubes drop the system's capacity below 64 bits per cube once you surpass just $k=2$ cubes, and consume all additional storage beyond $k=2^{64}$ cubes per bag, which is just sad. To solve that…

2. $\mathbb{N} \leftrightarrow \text{multiset}(n, k)$

A “bag” of potentially scrambled and otherwise indistinguishable cubes here is represented as a multiset of cardinality $k = \text{quantity of cubes}$, with elements from a set of cardinality $n={({12!})}\times{({8!\div 2})}\times{({2^{11}})}\times{({3^{7}})}$.

However, the combinatorial number system works with combinations, not multisets. The workaround for this is a bijection between combinations and multisets:

  • first, use a bit of creativity with the combinatorial number system to biject the input into $\left\{c \in {\mathcal{P}\left(\mathbb{N}\right)} \mid \forall x \in c \left( \left( n+\left\lvert c\right\rvert-1 \right) \gt x \right) \right\}$;

  • from there, it's a straightforward bijection ($c \mapsto \biguplus\left\{\left[x-i\right] \mid \left( i = \left\lvert \left\{y \in c \mid y \lt x\right\}\right\rvert \right) \right\}$[notation] or [x-i for i, x in enumerate(sorted(c))]) over to a multiset of valid scramble representatives.

JamesTheAwesomeDude
  • 235