2
$\begingroup$

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.

$\endgroup$

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.