La función estándar de emparejamiento de Cantor $J:\Bbb N \times \Bbb N \to \Bbb N$ que enumera los antidiagonales es eficiente en el sentido de que asigna $(m,n)$ en orden creciente por $m+n$ (de modo que esto puede ser visto como la "métrica de complejidad" que es minimizada por esta función de emparejamiento). Pero funciona muy mal cuando una entrada es mucho mayor que la otra; por ejemplo $J(0,n)=O(n^2)$ lo que significa que utilizar la función de emparejamiento de forma desequilibrada para tuplas superiores, es decir $J(x_1, J(x_2,\dots, J(x_{n-1},x_n)))$ conduce a un crecimiento exponencial $O(k^{2n})$ cuando $x_n=k$ y los otros se fijan en, digamos, $0$ .
El análisis de la entropía de la información sugiere que para almacenar dos números $m,n$ debería requerir aproximadamente $\log_2 m+\log_2n$ bits para almacenar, y una función de emparejamiento con esta propiedad mostraría un crecimiento lineal, no exponencial, en situaciones de emparejamiento desequilibrado.
¿Existe una función de emparejamiento tal que $\ell(J(m,n))\le\ell(m)+\ell(n)+O(\log\log(m+n))$ donde $\ell(x)=\lfloor\log_2x\rfloor+1\approx \log_2 x$ ? (No es necesario que sea biyectiva, sólo inyectiva, si eso lo hace más fácil.) Una estrategia de codificación es leer $\bar m,\bar n\in\{0,1\}^*$ como cadenas binarias, y luego formar la expresión $\bar m\,\$ \,\bar n $ as a string in the alphabet $ \{0,1, \$\}$ y codificar en ternario. Pero esto produce $\ell(J(m,n))=\log_23(\ell(m)+\ell(n)+1)$ que está desfasado por un factor $\log_23$ de lo óptimo.
(Puntos extra si puedes dar una función de emparejamiento óptima que utilice sólo operaciones algebraicas estándar sin recurrir a trucos de bits como éste).
