Fix an integer $n$. Considered as a multiplicative group, the sets $A = (\mathbb{Z} / n \mathbb{Z})^*$ and $B = \mathbb{Z} / \phi(n) \mathbb{Z}$ have the same cardinality $\phi(n)$, but it does not seem possible to give a 'well-behaved' bijection witnessing this fact. On the other hand, by considering the ring $R = \mathbb{Z} / n \mathbb{Z}$, it is possible to give a bijection between $R^A$ and $R^B$, considered as sets of functions.

Indeed, any element $f \in R^A$ can be written uniquely as $f(x) = \sum_{y \in B} \hat{f}(y) x^y$ with $\hat{f} \in R^B$; this is well-defined as for $x \in R$ we have $x^{\phi(n)}$ congruent to $0$ or $1$ modulo $n$. Conversely, $\hat{f}$ can be recovered as $\hat{f}(y) = \phi(n)^{-1} \sum_{x \in A} f(x) x^{-y}$. This has the desired properties: consider the matrices $K \in R^{A \times B}$ and $L \in R^{B \times A}$ defined by $K(x,y) = x^y$ and $L(y,x) = x^{-y}$, it can then be checked that $K.L = L.K = \phi(n) I$.

I would like to know if there are references to this bijection in the literature, and if there are other examples of 'indirect bijections' witnessing a combinatorial identity for which a direct bijective proof is not known.


Your Answer

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

Browse other questions tagged or ask your own question.