WorksMathematics
The Möbius function of factorizations with a simple prime factor
Abstract
The poset of factorizations of a positive integer (ordered by refinement) is known to have a very irregular Möbius function. We prove that this function becomes completely explicit whenever is divisible by a prime to the first power only (). Specifically, between a factorization with factors and itself, the Möbius function is given by multiplied by the number of ways to order the factors that are not divisible by . As a consequence, the sum of the absolute values of the Möbius function over this interval equals twice the number of ordered factorizations of .
Introduction
Writing a positive integer as a product of integers greater than one (ignoring order), we can order these factorizations by refinement: one factorization refines another if it is obtained by splitting some of the factors further. This relation turns the set of factorizations of into a finite poset, with the prime factorization at the bottom and the trivial factorization at the top. When is squarefree, this poset is simply the lattice of set partitions, whose Möbius function was computed independently by Schützenberger, Frucht, and Rota; in particular, the Möbius value for an -element set is [5, 6, 7]. However, as soon as any prime factor repeats, the poset ceases to be a lattice, and its Möbius function becomes notoriously difficult to control.
This difficulty arises even for prime powers. The factorizations of correspond to the integer partitions of , and Ziegler showed that this poset fails to be Cohen–Macaulay for large [4], ruling out standard topological tools for computing its Möbius function. For a general integer , the poset is equivalent to the partition poset of the multiset of prime factors of , studied by Hersh and Kleinberg [1]. They observed that the classical Möbius function is not multiplicative across blocks and instead introduced a multiplicative deformation , proving a product formula for it when one element of the multiset appears with multiplicity one. Meanwhile, the sum of absolute values of the ordinary Möbius function over all factorizations of was recently added to the On-Line Encyclopedia of Integer Sequences as A369713 [3], but without an explicit formula.
The purpose of this note is to show that the standard Möbius function itself satisfies a product formula analogous to that of Hersh and Kleinberg and much more whenever possesses at least one simple prime factor. Our main result is stated as follows.
Theorem 1. Let where is a prime not dividing , and let be a factorization of into factors. Let be the multiplicities of the distinct factors of that are not divisible by . Then
2020 Mathematics Subject Classification. 06A07, 05A17, 11N25.
Key words and phrases. Möbius function, factorizations, multiplicative partitions, partitions of a multiset, ordered factorizations.
Corresponding author: Daniel Yaqubi. In particular, if and , then the Möbius function between the prime factorization of and itself is
The number on the right is the number of ways to arrange the prime factors of in a row, so its absolute value counts the ordered factorizations of into primes. The theorem cannot be proved by a naive induction on upper intervals, because an upper interval of a factorization poset is in general not again a factorization poset; we explain this in Example 4. The way around it is to work in a slightly larger class of posets, which is closed under taking upper intervals, and to find a sign-reversing argument there.
Coarsening posets
It is convenient to encode a positive integer by its vector of exponents. A factorization of is then a finite multiset of nonzero vectors in whose sum is , and it refines another factorization if its vectors can be grouped so that the group sums are the vectors of the other. We generalize this as follows.
Definition 2. Let be a finite multiset of nonzero vectors in . A coarsening of is a multiset obtained by partitioning into groups and replacing each group by its sum. The set of coarsenings of is ordered by declaring if is a coarsening of .
The relation is transitive because groupings compose, and antisymmetric because a proper coarsening has fewer vectors, so is a poset with least element and greatest element the one-vector multiset . If consists of unit vectors, taken times, then is the poset of factorizations of . The point of the definition is the following observation, immediate from the definitions.
Lemma 3. For every , the upper interval of is equal to .
Example 4. For consider the factorization . Its seven factors are of four kinds, with multiplicities 2, 2, 2, 1, and one might expect the interval to look like the factorization poset of an integer with exponents 2, 2, 2, 1, whose Möbius function between bottom and top is 90. In fact . The reason is that the factor already present in can also be produced by merging a with a , so that different groupings of the factors of give the same coarsening. The interval is , but it is not isomorphic to a factorization poset.
Let us call a vector of marked if its last coordinate is positive, and say that is pointed if exactly one of its vectors is marked and that vector has last coordinate 1. In a coarsening of a pointed multiset there is again exactly one marked vector, namely the sum of the group containing the marked vector of , so every element of is pointed. For a pointed multiset we write for its number of vectors and for the number of distinct sequences formed by its unmarked vectors; if these have multiplicities , then .
Lemma 5. If is pointed and , then
Proof. Let be the marked vector of and , which is nonempty. For let be the multiset obtained from by subtracting from its marked vector and discarding the result if it is zero. Since the marked vector of is plus the sum of a group of vectors of , the multiset is a coarsening of . Conversely, let have distinct vectors with multiplicities . The elements with are exactly and, for , the multiset obtained from by replacing one copy of with ; these multisets are distinct, since their marked vectors are distinct. For we have and . For the -th element we have and
Hence the contribution of the fibre of is
because . Summing over gives the claim. □
Theorem 6. If is pointed, then the Möbius function of between its least and greatest elements is .
Proof. We argue by induction on ; for both sides equal 1. Let and write for the greatest element. By the defining recursion of the Möbius function,
For the interval equals by Lemma 3, and is pointed with , so by induction. Lemma 5 now gives . □
Proof of Theorem 1. Take the exponent vectors with respect to the primes of , listing last. Since divides exactly once, a factorization of is a pointed multiset, its marked vector being the factor divisible by . By Lemma 3 the interval of is , and Theorem 6 gives , which is the first formula. For the prime factorization the unmarked vectors are with multiplicity , and . □
The total absolute Möbius function
Let , the sum running over all factorizations of ; this is the sequence A369713 [3]. Let be the number of ordered factorizations of , that is, of ways to write as an ordered product of integers greater than one, with . It satisfies for , and its Dirichlet series is [2].
Corollary 7. If with a prime not dividing and , then .
Proof. By Theorem 1, is the number of orderings of the factors of not divisible by . A factorization together with such an ordering is the same thing as a divisor of , recording the factor , together with an ordered factorization of . Hence . □
For instance and , in agreement with [3]. The entry [3] also contains the conjecture that for some constant . In the case covered by the corollary this holds with : by induction, , so . The Dirichlet series shows that the exponent can be lowered to any number larger than the root of .
In the course of these computations, carried out with two independent programs, we obtained and , whereas the entry [3] lists 5, 5, 11 and 11. In all four cases the poset is small enough to check by hand; for the Möbius values of , , , and relative to are . These have no simple prime factor, and all of them admit factorizations with two equal composite factors.
Integers without a simple prime factor
When every prime divides at least twice, Example 4 shows that the structure is genuinely different, and we have no general formula. Table 1 lists the Möbius function between the prime factorization and for some exponent patterns, computed exhaustively.
| exponents | exponents | exponents | |||
Table 1. The Möbius function between the prime factorization and for some exponent patterns without a simple prime.
For prime powers the value is and for and, according to our computations, for . The column is deceptive: it reads for , suggesting , but continues with and . The signs, on the other hand, behave regularly.
Conjecture 8. The Möbius function between the prime factorization of and is either or has the sign , and it vanishes for with .
For integers with a simple prime factor the sign statement is part of Theorem 1. For the others it holds in every case we computed, which includes all with and all entries of Table 1.
Acknowledgement
Computations and parts of the exposition were carried out with the assistance of the AI system Claude (Anthropic).
References
Department of Pure Mathematics, Ferdowsi University of Mashhad, Mashhad, Iran
Email address: [email protected], [email protected]
Department of Computer Science, University of Torbat-e Jam, Torbat-e Jam, Iran
Email address: [email protected], [email protected]
References
- [1]P. Hersh and R. Kleinberg, A multiplicative deformation of the Möbius function for the poset of partitions of a multiset, Contemporary Mathematics, American Mathematical Society; available at https://plhersh.math.ncsu.edu/muquestions.pdf.
- [2]E. Hille, A problem in “Factorisatio Numerorum”, Acta Arith. 2 (1936), 134–144.DOI
- [3]OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, Sequence A369713, https://oeis.org/A369713.
- [4]G. M. Ziegler, On the poset of partitions of an integer, J. Combin. Theory Ser. A 42 (1986), 215–222.DOI
- [5]M.-P. Schützenberger, Contribution aux applications statistiques de la théorie de l’information, Publ. Inst. Statist. Univ. Paris 3 (1954), 3–117.
- [6]R. Frucht and G.-C. Rota, La función de Möbius para el retículo de particiones de un conjunto finito, Scientia 122 (1963), 111–115.
- [7]G.-C. Rota, On the foundations of combinatorial theory I. Theory of Möbius functions, Z. Wahrscheinlichkeits-theorie Verw. Gebiete 2 (1964), 340–368.DOI