betaFeedback

WorksMathematics

The Möbius function of factorizations with a simple prime factor

Abstract

The poset of factorizations of a positive integer nn (ordered by refinement) is known to have a very irregular Möbius function. We prove that this function becomes completely explicit whenever nn is divisible by a prime qq to the first power only (q2∤nq^2 \nmid n). Specifically, between a factorization with kk factors and nn itself, the Möbius function is given by (−1)k−1(-1)^{k-1} multiplied by the number of ways to order the factors that are not divisible by qq. 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 n/qn/q.

Introduction

Writing a positive integer nn 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 nn into a finite poset, with the prime factorization at the bottom and the trivial factorization nn at the top. When nn 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 rr-element set is (−1)r−1(r−1)!(-1)^{r-1}(r-1)! [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 pkp^k correspond to the integer partitions of kk, and Ziegler showed that this poset fails to be Cohen–Macaulay for large kk [4], ruling out standard topological tools for computing its Möbius function. For a general integer nn, the poset is equivalent to the partition poset of the multiset of prime factors of nn, 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 μ′\mu', 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 nn 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 nn possesses at least one simple prime factor. Our main result is stated as follows.

Theorem 1. Let n=mqn=mq where qq is a prime not dividing mm, and let xx be a factorization of nn into kk factors. Let c1,…,csc_1,\ldots,c_s be the multiplicities of the distinct factors of xx that are not divisible by qq. Then

μ(x,n)=(−1)k−1(k−1)!c1!⋯cs!.\mu(x,n)=(-1)^{k-1}\frac{(k-1)!}{c_1!\cdots c_s!}.

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 m=p1e1⋯prerm = p_1^{e_1} \cdots p_r^{e_r} and Ω(m)=e1+⋯+er\Omega(m) = e_1 + \cdots+ e_r, then the Möbius function between the prime factorization of nn and nn itself is

(−1)Ω(m)Ω(m)!e1!⋯er!(-1)^{\Omega(m)} \frac{\Omega(m)!}{e_1! \cdots e_r!}

The number on the right is the number of ways to arrange the prime factors of mm in a row, so its absolute value counts the ordered factorizations of mm 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 n=p1a1⋯ptatn = p_1^{a_1} \cdots p_t^{a_t} is then a finite multiset of nonzero vectors in Nt\mathbb{N}^t whose sum is (a1,…,at)(a_1, \ldots, a_t), 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 WW be a finite multiset of nonzero vectors in Nt\mathbb{N}^t. A coarsening of WW is a multiset obtained by partitioning WW into groups and replacing each group by its sum. The set U(W)\mathcal{U}(W) of coarsenings of WW is ordered by declaring y≤zy \leq z if zz is a coarsening of yy.

The relation is transitive because groupings compose, and antisymmetric because a proper coarsening has fewer vectors, so U(W)\mathcal{U}(W) is a poset with least element WW and greatest element the one-vector multiset {∑W}\{\sum W\}. If WW consists of unit vectors, eie_i taken aia_i times, then U(W)\mathcal{U}(W) is the poset F(n)\mathcal{F}(n) of factorizations of nn. The point of the definition is the following observation, immediate from the definitions.

Lemma 3. For every y∈U(W)y \in\mathcal{U}(W), the upper interval [y,{∑W}][y, \{\sum W\}] of U(W)\mathcal{U}(W) is equal to U(y)\mathcal{U}(y).

Example 4. For n=p3q3r2n = p^3q^3r^2 consider the factorization x=p⋅p⋅q⋅q⋅r⋅r⋅pqx = p \cdot p \cdot q \cdot q \cdot r \cdot r \cdot pq. Its seven factors are of four kinds, with multiplicities 2, 2, 2, 1, and one might expect the interval [x,n][x,n] 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 μ(x,n)=92\mu(x,n) = 92. The reason is that the factor pqpq already present in xx can also be produced by merging a pp with a qq, so that different groupings of the factors of xx give the same coarsening. The interval [x,n][x,n] is U(x)\mathcal{U}(x), but it is not isomorphic to a factorization poset.

Let us call a vector of WW marked if its last coordinate is positive, and say that WW 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 WW, so every element of U(W)\mathcal{U}(W) is pointed. For a pointed multiset yy we write ∣y∣|y| for its number of vectors and N(y)N(y) for the number of distinct sequences formed by its unmarked vectors; if these have multiplicities c1,…,csc_1,\ldots,c_s, then N(y)=(∣y∣−1)!/(c1!⋯cs!)N(y) = (|y|-1)!/(c_1! \cdots c_s!).

Lemma 5. If WW is pointed and ∣W∣≥2|W| \geq2, then

∑y∈U(W)(−1)∣y∣−1N(y)=0.\sum_{y \in\mathcal{U}(W)} (-1)^{|y|-1} N(y) = 0.

Proof. Let ww be the marked vector of WW and W′=W∖{w}W' = W \setminus\{w\}, which is nonempty. For y∈U(W)y \in\mathcal{U}(W) let ρ(y)\rho(y) be the multiset obtained from yy by subtracting ww from its marked vector and discarding the result if it is zero. Since the marked vector of yy is ww plus the sum of a group of vectors of W′W' , the multiset ρ(y)\rho(y) is a coarsening of W′W'. Conversely, let z∈U(W′)z \in\mathcal{U}(W') have distinct vectors v1,…,vhv_1,\ldots,v_h with multiplicities d1,…,dhd_1,\ldots,d_h. The elements yy with ρ(y)=z\rho(y)=z are exactly z∪{w}z\cup\{w\} and, for j=1,…,hj=1,\ldots,h, the multiset obtained from zz by replacing one copy of vjv_j with vj+wv_j+w; these h+1h+1 multisets are distinct, since their marked vectors are distinct. For y=z∪{w}y=z\cup\{w\} we have ∣y∣=∣z∣+1|y|=|z|+1 and N(y)=∣z∣!/(d1!⋯dh!)N(y)=|z|!/(d_1!\cdots d_h!). For the jj-th element we have ∣y∣=∣z∣|y|=|z| and

N(y)=(∣z∣−1)!d1!⋯(dj−1)!⋯dh!=dj∣z∣⋅∣z∣!d1!⋯dh!.N(y)=\frac{(|z|-1)!}{d_1!\cdots(d_j-1)!\cdots d_h!}=\frac{d_j}{|z|}\cdot\frac{|z|!}{d_1!\cdots d_h!}.

Hence the contribution of the fibre of zz is

(−1)∣z∣∣z∣!d1!⋯dh!(1−∑j=1hdj∣z∣)=0,(-1)^{|z|}\frac{|z|!}{d_1!\cdots d_h!}\left(1-\sum_{j=1}^{h}\frac{d_j}{|z|}\right)=0,

because d1+⋯+dh=∣z∣d_1+\cdots+d_h=|z|. Summing over z∈U(W′)z\in\mathcal{U}(W') gives the claim. □

Theorem 6. If WW is pointed, then the Möbius function of U(W)\mathcal{U}(W) between its least and greatest elements is (−1)∣W∣−1N(W)(-1)^{|W|-1}N(W).

Proof. We argue by induction on ∣W∣|W|; for ∣W∣=1|W|=1 both sides equal 1. Let ∣W∣≥2|W|\ge2 and write 1^\hat{1} for the greatest element. By the defining recursion of the Möbius function,

μ(W,1^)=−∑y∈U(W)y≠Wμ(y,1^).\mu(W,\hat{1})=-\sum_{\substack{y\in\mathcal{U}(W)\\y\ne W}}\mu(y,\hat{1}).

For y≠Wy\ne W the interval [y,1^][y,\hat{1}] equals U(y)\mathcal{U}(y) by Lemma 3, and yy is pointed with ∣y∣<∣W∣|y|<|W|, so μ(y,1^)=(−1)∣y∣−1N(y)\mu(y,\hat{1})=(-1)^{|y|-1}N(y) by induction. Lemma 5 now gives μ(W,1^)=(−1)∣W∣−1N(W)\mu(W,\hat{1})=(-1)^{|W|-1}N(W). □

Proof of Theorem 1. Take the exponent vectors with respect to the primes of nn, listing qq last. Since qq divides nn exactly once, a factorization xx of nn is a pointed multiset, its marked vector being the factor divisible by qq. By Lemma 3 the interval [x,n][x,n] of F(n)\mathcal{F}(n) is U(x)\mathcal{U}(x), and Theorem 6 gives μ(x,n)=(−1)k−1N(x)\mu(x,n)=(-1)^{k-1}N(x), which is the first formula. For the prime factorization the unmarked vectors are eie_i with multiplicity eie_i, and k−1=Ω(m)k-1=\Omega(m). □

The total absolute Möbius function

Let a(n)=∑x∣μ(x,n)∣a(n)=\sum_x|\mu(x,n)|, the sum running over all factorizations xx of nn; this is the sequence A369713 [3]. Let H(m)H(m) be the number of ordered factorizations of mm, that is, of ways to write mm as an ordered product of integers greater than one, with H(1)=1H(1)=1. It satisfies H(m)=∑d∣md<mH(d)H(m)=\sum_{\substack{d\mid m\\d<m}}H(d) for m>1m>1, and its Dirichlet series is 1/(2−ζ(s))1/(2-\zeta(s)) [2].

Corollary 7. If n=mqn=mq with qq a prime not dividing mm and m>1m>1, then a(n)=2H(m)a(n)=2H(m).

Proof. By Theorem 1, ∣μ(x,n)∣|\mu(x,n)| is the number of orderings of the factors of xx not divisible by qq. A factorization together with such an ordering is the same thing as a divisor dd of mm, recording the factor qdqd, together with an ordered factorization of m/dm/d. Hence a(n)=∑d∣mH(m/d)=H(m)+∑d∣md<mH(d)=2H(m)a(n)=\sum_{d\mid m}H(m/d)=H(m)+\sum_{\substack{d\mid m\\d<m}}H(d)=2H(m). □

For instance a(60)=2H(12)=16a(60)=2H(12)=16 and a(24)=2H(8)=8a(24)=2H(8)=8, in agreement with [3]. The entry [3] also contains the conjecture that a(n)≤nca(n)\le n^c for some constant cc. In the case covered by the corollary this holds with c=2c=2: by induction, H(m)≤∑d∣md<md2≤m2∑j≥2j−2<m2H(m)\le\sum_{\substack{d\mid m\\d<m}}d^2\le m^2\sum_{j\ge2}j^{-2}<m^2, so a(n)≤2(n/q)2≤n2/2a(n)\le2(n/q)^2\le n^2/2. The Dirichlet series shows that the exponent can be lowered to any number larger than the root ρ≈1.7286\rho\approx1.7286 of ζ(ρ)=2\zeta(\rho)=2.

In the course of these computations, carried out with two independent programs, we obtained a(16)=a(81)=4a(16)=a(81)=4 and a(36)=a(64)=10a(36)=a(64)=10, whereas the entry [3] lists 5, 5, 11 and 11. In all four cases the poset is small enough to check by hand; for n=16n = 16 the Möbius values of 1616, 8⋅28 \cdot2, 4⋅44 \cdot4, 4⋅2⋅24 \cdot2 \cdot2 and 2⋅2⋅2⋅22 \cdot2 \cdot2 \cdot2 relative to 1616 are 1,−1,−1,1,01, -1, -1, 1, 0. These nn 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 nn 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 nn for some exponent patterns, computed exhaustively.

exponentsμ\muexponentsμ\muexponentsμ\mu
(2,2)(2,2)−1-1(3,3)(3,3)−3-3(4,4)(4,4)−8-8
(3,2)(3,2)22(4,3)(4,3)55(5,4)(5,4)1313
(4,2)(4,2)−3-3(5,3)(5,3)−8-8(6,4)(6,4)−22-22
(5,2)(5,2)44(6,3)(6,3)1313(5,5)(5,5)−18-18
(6,2)(6,2)−5-5(2,2,2)(2,2,2)−16-16(3,2,2)(3,2,2)3131
(7,2)(7,2)77(8,2)(8,2)−9-9(4,2,2)(4,2,2)−52-52
(3,3,2)(3,3,2)−72-72(2,2,2,2)(2,2,2,2)−312-312

Table 1. The Möbius function between the prime factorization and nn for some exponent patterns without a simple prime.

For prime powers nkn^k the value is 11 and −1-1 for k=1,2k = 1, 2 and, according to our computations, 00 for 3≤k≤103 \leq k \leq10. The column n=paq2n = p^a q^2 is deceptive: it reads −1,2,−3,4,−5-1, 2, -3, 4, -5 for 2≤a≤62 \leq a \leq6, suggesting (−1)a+1(a−1)(-1)^{a+1}(a - 1), but continues with 77 and −9-9. The signs, on the other hand, behave regularly.

Conjecture 8. The Möbius function between the prime factorization of nn and nn is either 00 or has the sign (−1)Ω(n)+1(-1)^{\Omega(n)+1}, and it vanishes for n=pkn = p^k with k≥3k \geq3.

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 nn with Ω(n)≤8\Omega(n) \leq8 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. [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. [2]E. Hille, A problem in “Factorisatio Numerorum”, Acta Arith. 2 (1936), 134–144.DOI
  3. [3]OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, Sequence A369713, https://oeis.org/A369713.
  4. [4]G. M. Ziegler, On the poset of partitions of an integer, J. Combin. Theory Ser. A 42 (1986), 215–222.DOI
  5. [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. [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. [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

Paper details

vlnc:W_z93utd52
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude (Anthropic)

View statement
Looking for related papers…
Contents