The two-way rewriting in action: Removing the mystery of Euler–Glaisher's map

AbstractStarting with Euler's bijection between the partitions into odd parts and the partitions into distinct parts, one basic activity in combinatorics is to establish partition identities by so-called ‘bijective proofs,’ which amounts to constructing explicit bijections between two classes of the partitions under consideration.The aim of this paper is to give a global view on the Glaisher-type bijections and related rewriting maps.Glaisher's map is a bijection between partitions with no part divisible by m and partitions with no parts repeated m or more times, that uses basic number theoretic techniques. O’Hara's rewriting map is also a bijection between those two sets (the map consists of repeated replacing any m occurrences of a part, say z, by the number mz). It is remarkable that both of these bijections are identical. Moreover, the bijections produced for many partition identities by the refine machinery developed by, for example, Remmel, Gordon, O’Hara, and Sellers, Sills, and Mullen, turn out to be the same bijections as the ones found by Euler and generalized by Glaisher.Here we give a quite paradoxical answer to the question of why Euler–Glaisher's bijections arise so persistently from their applications, namely: Whatever Euler-like partition identities we take, one and the same Euler–Glaisher's map will be suited for all of them.We prove this by giving an alternate description of the bijections using two-way rewriting bijections between any two equinumerous partition ideals of order 1, provided, as a partial case, by a general criterion from Kanovich [Finding direct partition bijections by two-directional rewriting techniques, Discrete Math. 285(1–3) (2004) 151–166]. The tricky part of the proof is that, generally speaking, Euler–Glaisher's mapping differs from the rewriting mapping derived, but both mappings are proved to behave identically on all partitions that might have been involved as elements of some equinumerous ‘Euler pairs’.We generalize Glaisher's mapping by simply substituting mixed radix expansions for the base m expansions in Glaisher's original construction. With this direct generalization we extend the Euler–Glaisher's phenomenon to any two equinumerous partition ideals of order 1, whenever one of the ideals consists of partitions into parts from a set. As a useful part of the proof, we develop a natural generalization of Andrews–Subbarao's criterion [G.E. Andrews, Two theorems of Euler and a general partition theorem, Proc. Amer. Math. Soc. 20(2) (1969) 499–502; M.V. Subbarao, Partition theorems for Euler pairs, Proc. Amer. Math. Soc. 28(2) (1971) 330–336]