5
$\begingroup$

This is a question a student asked me when I was teaching a class. When I use the notation $\sum_{d|n}f(d)$, each divisor is only counted once without multiplicity. If $n=4$, then $\sum_{d|4}f(d)=f(1)+f(2)+f(4)$ instead of $\sum_{d|4}f(d)=f(1)+2f(2)+f(4)$. But instead of just telling the student, this is just what this notation is defined. It is the convention. I can also say, oh you can think of $f(4)$ as "counting the multiplicity" but I am also not satisfied with this answer as well. Are there any more insightful explanations from experts in number theory?

For example, in the definition of the divisor sum functions $\sigma_k(n)$, we don't count the multiplicity of a divisor. But is there a reason that "counting the multiplicity of a divisor" not so interesting? Or there are people who seriously studied it and I just missed an important part of literature.


As per comments below, maybe let me try to define "multiplicity" here, which is by no means standard definitions in number theory, there are two possible ways I can think of (when that student asked this question, they didn't think very hard about it. They just believe $2$ shouldn't be counted just once as a divisor of $4$):

Definition 1: If $d\ne 1$ is a divisor of $n$, then the multiplicity of $d$ in $n$ is the largest $k$ such that $d^k|n$. The multiplicity of $1$ in $n$ is considered as $1$.

For example, the multiplicity of $2$ in $8$ is $3$. The multiplicity of $6$ in $12$ under this definition is $1$.

Definition 2: If If $d\ne 1$ is a divisor of $n$, suppose $d=p_1^{r_1}\cdots p_l^{r_l}$ and $n=d=p_1^{s_1}\cdots p_k^{s_k}$ with $l\le k, r_i\le s_i$, then the multiplicity of $d$ in $n$ is $\binom{s_1}{r_1}\cdots \binom{s_l}{r_l}$.

For example, the multiplicity of $6$ in $12$ under this definition is $2$, since $6=2\times 3$ and there are two choices for $2$ in the prime decomposition of $12$.

$\endgroup$
6
  • 4
    $\begingroup$ What is multiplicity? The amount of times $d$ divides $n$? Meaning $n/d$? if so, that is a Dirichlet convolution with identity function, so its kind of the same information? $\endgroup$
    – Phicar
    Nov 8, 2023 at 1:31
  • 3
    $\begingroup$ I think it's more usual to talk about the multiplicity of a prime divisor, because there is a natural useful multiset of prime numbers associated to every number. The sense in which "$2$ appears three times in $72$" is I think more meaningful than the sense in which "$6$ appears twice in $72$", since the latter isn't part of a useful decomposition of $72$. (I assume that by multiplicity of a divisor $d$ of $n$ you mean the largest $m$ such that $d^m \mid n$). Besides, you'd have to multiply $f(1)$ by infinity.. $\endgroup$ Nov 8, 2023 at 1:42
  • 1
    $\begingroup$ $\sum_{d|n} d f(d)$ is not the most attractive alternative. If $f(n)$ is multiplicative, the simplest new multiplicative function by convolution is $g(n)= \sum_{d|n} \frac{n}{d} f(d).$ Your idea of counting things resembles a mean in statistics, and average values and weighted average values of arithmetical functions do have a place. Do you have Hardy and Wright? $\endgroup$
    – Will Jagy
    Nov 8, 2023 at 2:45
  • $\begingroup$ I see a slight difference between the terms "divisor" and "factor". A number either divides $n$, or doesn't divide $n$; there is no multiplicity. A factor of $n$ is part of something larger, a product of several numbers which equals $n$. A factor has a multiplicity in the product. So then we must ask, what product are you considering? $\endgroup$
    – mr_e_man
    Nov 8, 2023 at 4:04
  • 1
    $\begingroup$ @Phicar I added two possible ways of definition for multiplicity of a divisor. $\endgroup$
    – No One
    Nov 8, 2023 at 23:35

1 Answer 1

5
$\begingroup$

Consider that the “divides” or “is-a-factor-of” relation is a partial order (reflexive, antisymmetric, and transitive). So in a sense, a sum $\sum_{d|n} f(d)$ is analogous to $\sum_{d=0}^n f(d)$, in that it sums over all integers “less than” $n$ in the poset $({\bf N}, |)$.

$\endgroup$
1
  • $\begingroup$ There is a lot lurking behind this answer. Consider also how Mobius inversion generalizes (see the WP article on incidence algebra, with examples), or how Dirichlet series are the arithmetic analogue of generating functions (relating to the multiplicative and additive structure of the naturals). $\endgroup$
    – coiso
    Nov 8, 2023 at 4:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .