Andrew Granville Created 2026-10-13 Updated 2026-11-05
Andrew Granville coauthored work on the pretentious approach to multiplicative number theory with Kannan Soundararajan. The approach compares multiplicative functions through quantitative measures of their agreement, revealing structure behind cancellations and mean values.[ref]
Multiplicative number theory: The pretentious approach by Andrew Granville and K. Soundararajan. author attribution and the described mathematical development
Portrait of Andrew Granville
. External portrait hosted by Université de Montréal. Source. Archimedean character Created 2026-09-24 Updated 2026-11-05
An Archimedean character on the positive integers is the completely multiplicative functionIts modulus is one. The identity proves complete multiplicativity, while gives the constant-one arithmetic function. These functions form the comparison family in Halász theorem: a large mean of a bounded multiplicative function can arise when its prime values resemble those of one such character.
Divisor function Created 2026-09-24 Updated 2026-11-05
The divisor function counts the positive integer divisors of a positive integer . In particular , because has just one positive integer divisor. More generally the notation gives and the sum-of-divisors function . Thus the divisor function counts the positive integer divisors, while adds their sizes. [ref]
Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781 lecture notes, Definition 2.1.2 and Theorem 2.1.6
If the prime factorization is with distinct prime numbers and positive exponents , thenThe short proof is a count: each positive integer divisor has a unique form , where . There are choices at each prime number, and choosing them gives every positive integer divisor exactly once. For there are no prime factors and the product is .
For , choose and to obtain . The six values are ; sorted, the positive integer divisors are . Therefore . The diagram makes the independent exponent choices visible.
The prime factorization gives a three-by-two array of positive integer divisors , so the divisor function has
. Details. This count is useful because a known prime factorization gives without testing every smaller positive integer for divisibility. It also proves the divisor function is a multiplicative function: coprime integers have disjoint prime factors, so their exponent choices combine. For example , but , so it is not a completely multiplicative function. Equivalently, under Dirichlet convolution, counting ordered pairs of positive integers whose product is .
Divisor sum Created 2026-09-24 Updated 2026-11-05
The divisor sum of an arithmetic function assigns to each positive integer the sumOnly positive integer divisors are included, so . The weights can count the integer divisors, measure their sizes, or record other arithmetic information: the constant-one arithmetic function gives the divisor function, whereas the identity arithmetic function gives the sum-of-divisors function.
Equivalently, , where is Dirichlet convolution and is the constant-one arithmetic function. If is a multiplicative function, then is a multiplicative function by Multiplicativity of Dirichlet convolution. [ref]
Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781 notes on floor and arithmetic functions, Proposition 2.4.2 and Theorem 2.6.1
Here is the mechanism. For positive coprime integers , every positive integer divisor of has a unique form with and ; moreover, are coprime integers. Thus a multiplicative function satisfiesAt a prime power, the divisor sum becomes . This turns a calculation over many integer divisors into short local calculations at prime powers.
Kannan Soundararajan Created 2026-10-24 Updated 2026-11-05
Kannan Soundararajan coauthored an account of pretentious multiplicative number theory with Andrew Granville. Measuring how closely a multiplicative function resembles a structured model helps organize its averages and cancellation behavior.[ref]
Multiplicative number theory: The pretentious approach by Andrew Granville and K. Soundararajan. author attribution and the described mathematical development
Portrait of Kannan Soundararajan
. King of Hearts. CC BY-SA 3.0, via Wikimedia Commons. Source. Min_25 sieve Created 2026-10-20 Updated 2026-11-05
The Min_25 sieve computes summatory multiplicative functions by isolating weighted prime sums and then restoring composite contributions. A useful basic form applies when for primes , the degree is small, and values on prime powers can be computed efficiently. The formulas below explain the two stages; optimized implementations differ in scheduling and cost.[ref]
Min_25 sieve explanation in the ABC370 editorial. general multiplicative-function framework, Lucy DP and Min_25 sieve sections
Use quotient arguments . There are distinct values: indices at most contribute that many, and larger indices yield values below . The floor function identity keeps later quotients in this table.
For each exponent , initialize . Process primes in increasing order, and eligible in decreasing order, applyingThis removes composites whose smallest prime factor is . The subtraction inside parentheses excludes earlier primes from the possible cofactors. Decreasing ensures each smaller argument still has its pre- value. After sieving, is the desired sum of over primes up to .
To restore composites, let be the th prime and let sum over with every prime factor greater than . Set for . Otherwise its prime contribution is , and addUnique decomposition by smallest prime factor and its full exponent proves this recurrence: mixed numbers use the first term, pure powers use the second. With , and , the answer is . No complete-multiplicativity assumption is needed.
For the Euler totient function up to six, the prime contribution is . The composites add , and gives total twelve. This independently chosen small example checks that prime powers and mixed products are both counted once.
Möbius function Created 2026-09-24 Updated 2026-11-05
The Möbius function assigns a cancellation weight to each positive integer:Thus a squarefree integer contributes a sign determined by its number of distinct prime factors; a repeated prime factor makes the weight zero. This packages the alternating signs of inclusion-exclusion into an arithmetic function. [ref]
Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781 lecture notes, Definition 2.1.2
For example, , , and , since . In contrast, : all three have the square of the prime number as a divisor. On prime powers, and for .
The Möbius function is a multiplicative function: for coprime integers, their prime factors are disjoint, so either a squared prime factor forces both sides of to vanish, or the counts of distinct prime factors add and their signs multiply. It is not a completely multiplicative function, since . Its Möbius divisor-sum identity makes it the inverse of the constant-one arithmetic function under Dirichlet convolution: , the Identity for Dirichlet convolution. This is why the small set of weights can undo an entire divisor sum.
Multiplicative function Created 2026-10-13 Updated 2026-11-05
An arithmetic function is a multiplicative function when and for all coprime integers , meaning their greatest common divisor is . The condition excludes the identically zero function. This definition makes no assertion about a pair whose greatest common divisor exceeds . [ref]
Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781 lecture notes, Definition 2.2.1
For the divisor function, the integer divisors of are , those of are , and those of are . HenceHere and are coprime integers. In contrast, , because the integer divisors of are . Thus the divisor function is a multiplicative function but not a completely multiplicative function.
The practical gain is that prime factorization reduces all values to values at prime powers. For distinct prime numbers and positive exponents ,For instance, since and are coprime integers; replacing by additionally requires a completely multiplicative function. The short proof repeatedly applies the defining rule to prime powers belonging to different prime numbers, which are coprime integers.
Multiplicativity of an arithmetic function Created 2026-10-06 Updated 2026-10-14
For an arithmetic function, multiplicativity means and whenever are positive coprime integers. It allows values of an arithmetic function to be assembled from its values on prime powers, as explained under multiplicative function.
Multiplicativity of Dirichlet convolution Created 2026-10-14 Updated 2026-11-05
The Dirichlet convolution of two multiplicative functions is a multiplicative function. For positive coprime integers , every positive integer divisor of has a unique form with and , by prime factorization. The pairs and are each coprime integers, so the defining rules for the two multiplicative functions separate the sum:Also . This short argument proves multiplicativity of both the divisor function and the sum-of-divisors function . The result need not be a completely multiplicative function, even when both inputs are: fails at . [ref]
Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781 lecture notes, Theorem 2.6.1
Multiplicativity of the Euler totient function Created 2026-09-24 Updated 2026-11-05
For coprime positive integers , Euler's totient function satisfiesThe Chinese remainder theorem gives a bijection from congruence classes modulo to pairs of congruence classes modulo and . A class is a unit modulo exactly when both component classes are units, because being coprime to is equivalent to being coprime to each factor. Counting these pairs proves the identity. The case where a factor is one follows from .
For example, . The coprimality assumption matters: whereas . Thus the Euler totient function is a multiplicative function, rather than a completely multiplicative function.
For , let denote the algebraic conjugate, not necessarily ordinary complex conjugation when . Conjugation respects multiplication, and . ThereforeIf is a unit in a ring, choose its inverse in the same ring. Then , and both norms are nonnegative integers, forcing . Conversely, if , then , so belongs to the ring. Thus is a unit in a ring exactly when .
For negative , the equation becomes . If , its integer solutions give the four units . If , the term forces , leaving . HenceFor , the element has field norm . Its powers , , are all units by multiplicative function and are distinct, since their positive real values strictly increase with . Thus has infinitely many units. This argument concerns the stated integer-coefficient ring; it does not replace it by a larger ring of algebraic integers.
The Möbius function satisfies for and is zero for . ThereforeThe inverse local factor is . Consequently the inverse under Dirichlet convolution is the Liouville functionwhere counts prime factors with multiplicity. Both functions are multiplicative functions. At with , their convolution is , while its value at one is one. Multiplicativity then proves on every positive integer. Its Dirichlet series is for .
Pretentious distance Created 2026-09-24 Updated 2026-11-05
For multiplicative functions bounded in modulus by one, their pretentious distance up to isIt compares their values on prime numbers, weighting smaller primes more heavily. It need not be a metric: values away from primes are invisible, and can be positive when . For unit-modulus prime values it has the precise prime-restriction metric for pretentious distance interpretation.[ref]
Pretentious Multiplicative Functions and an Inequality for the Zeta-Function by Andrew Granville and Kannan Soundararajan. pp. 206–208: the prime-weighted comparison and its mean-value interpretation
Radical of an integer Created 2026-10-06 Updated 2026-10-20
The radical of an integer is the product of its distinct prime factors, each included exactly once. If the prime factorization is with distinct prime numbers and positive integer exponents , thenThus the radical of an integer remembers which prime factors occur and forgets their prime valuations. At , the empty product gives . The domain of a function here is the positive integers; zero is excluded. [ref]
https://pub.math.leidenuniv.nl/~evertsejh/dio12-ex4.pdf. Jan-Hendrik Evertse, Diophantine approximation, Homework IV, Exercise 20: definition of the integer radical
For example, has distinct prime factors , so . Similarly,using the prime factorizations , and . The prime omega function counts the retained prime factors, while the total number of prime factors counts their occurrences before repetitions are removed.
The radical of an integer is its largest squarefree divisor. Indeed, a squarefree divisor chooses at most one copy of each prime factor, so it divides ; the radical of an integer itself is a squarefree divisor. Consequently,The last statement follows because every nonzero prime valuation is then one. It includes , a squarefree integer. Applying the radical of an integer twice also changes nothing: .
The radical of an integer for : squarefree integers lie on the diagonal, and horizontal families share their prime support of an integer
. Details. For any positive integers , the exact product rule isTo prove it, a prime factor dividing just one input occurs once in the numerator and not in the denominator. A prime factor dividing both occurs twice in the numerator and once in the denominator, since it divides their greatest common divisor. Each prime factor of therefore remains exactly once. For coprime integers, the denominator is , proving the radical of an integer is a multiplicative function. It is not a completely multiplicative function: .
For a worked example with shared prime factors, take and . Their greatest common divisor is , and , soThis explains why prime support of an integer is useful: questions about the presence of prime factors can discard their multiplicities. For example, the squarefree divisors of are exactly the integer divisors of , namely . Also if and only if , because coprimality depends only on shared prime factors.
A further characterization uses mutual divisibility of powers: for positive integers ,If their prime supports of an integer agree, sufficiently large make all the required prime valuations large enough. Conversely, these two divisibility relations force each prime factor of either input to divide the other. For and , one can take and : and .
Sum-of-divisors function Created 2026-10-03 Updated 2026-11-05
The sum-of-divisors function adds all positive integer divisors of a positive integer, including the number itself:It is the divisor sum of the identity arithmetic function , so under Dirichlet convolution. Both factors are multiplicative functions, hence so is the sum-of-divisors function. The notation distinguishes it from other weighted divisor sums. [ref]
Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781 notes, Definition 2.1.2 and Proposition 2.2.2(e)
For a prime number and a nonnegative exponent , the positive integer divisors of the prime power are precisely . Their finite geometric series givesFor example, . For a prime factorization with distinct prime numbers and positive exponents , multiplicativity givesFor , this is an empty product, equal to . [ref]
Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781 notes, Theorem 2.1.8 with k equal to one
The distributive property makes the formula especially beautiful: choosing one term from each factor produces each positive integer divisor exactly once, by the fundamental theorem of arithmetic. For , the choices form a three-by-two grid with entries , where and . Adding its rows givesThe divisor function counts six cells; the sum-of-divisors function adds their six values. Once the prime factorization is known, the product formula avoids testing every candidate integer divisor. Shared prime factors require care: , so the sum-of-divisors function is not a completely multiplicative function.
The sum-of-divisors function for : each grid entry is a positive integer divisor, and the weighted total is
. Details. Subtracting the number itself gives the proper-divisor sum . Comparing with distinguishes perfect numbers, deficient numbers, and abundant numbers. For , ; for , . Both are perfect numbers. The calculation makes a deficient number, while makes an abundant number. These comparisons turn the sizes of integer divisors into a classification of positive integers. [ref]
The proper-divisor sum for : perfect numbers lie on , deficient numbers below it, and abundant numbers above it
. Details. This connection is ancient: Euclid's Elements, Book IX, Proposition 36, constructs a perfect number by multiplying the last term of by their sum, when that sum is a prime number. In modern notation, put and , with and a prime number. The sum-of-divisors function proves the construction immediately:Consequently the proper-divisor sum is . Taking produces the perfect numbers . [ref]
Book IX, Proposition 36. Euclid, Elements IX.36, translated text and commentary by David Joyce
Triangle inequality for pretentious distance Created 2026-09-24 Updated 2026-11-05
For multiplicative functions bounded in modulus by one, the pretentious distance satisfiesHere products mean pointwise products of arithmetic functions. For complex numbers of modulus at most one, write and . The bounds and giveApply this with and at each prime , divide by , and use the triangle inequality for the resulting finite Euclidean norm. This proves the displayed product inequality.[ref]





