🔢Analytic Number Theory Unit 4 – Arithmetic Function Averages & Summation

Key Concepts and Definitions

• Arithmetic functions map positive integers to complex numbers and play a crucial role in studying number-theoretic properties
• Summation notation $\sum$ represents the sum of a sequence of terms and is used extensively in analyzing arithmetic functions
• Average order of an arithmetic function $f(n)$ measures its typical size as $n$ grows and is denoted by $A_f(x)$
• Dirichlet series $\sum_{n=1}^{\infty} \frac{f(n)}{n^s}$ generates an arithmetic function $f(n)$ and encodes its properties
• Asymptotic behavior describes how an arithmetic function grows or behaves as the input tends to infinity using notations like $O$, $o$, $\sim$, and $\Theta$
  • $f(n) = O(g(n))$ means $f$ is bounded above by a constant multiple of $g$ for sufficiently large $n$
  • $f(n) = o(g(n))$ means $f$ grows slower than $g$ as $n$ tends to infinity
  • $f(n) \sim g(n)$ means the ratio $f(n)/g(n)$ tends to 1 as $n$ tends to infinity
• Multiplicative functions satisfy $f(mn) = f(m)f(n)$ for coprime $m$ and $n$ and have special properties in terms of their Dirichlet series and average orders

Arithmetic Functions: Types and Properties

• Multiplicative functions are determined by their values at prime powers and have Dirichlet series with Euler products
  • Examples include the Möbius function $\mu(n)$, Euler's totient function $\phi(n)$, and the divisor function $d(n)$
• Completely multiplicative functions satisfy $f(mn) = f(m)f(n)$ for all $m$ and $n$ and are determined by their values at primes
  • The Möbius function $\mu(n)$ is completely multiplicative with $\mu(p) = -1$ for primes $p$
• Additive functions satisfy $f(mn) = f(m) + f(n)$ for coprime $m$ and $n$ and have simpler average order formulas
  • The logarithm function $\log(n)$ and the prime omega function $\omega(n)$ counting prime factors are additive
• Convolution of arithmetic functions $f * g$ is defined by $(f * g)(n) = \sum_{d|n} f(d)g(n/d)$ and corresponds to multiplication of Dirichlet series
• Möbius inversion formula allows recovering $f$ from $g$ if $g = f * 1$ using $f(n) = \sum_{d|n} \mu(d)g(n/d)$
• Dirichlet characters are completely multiplicative functions that arise from residue classes modulo $k$ and are used in L-functions

Summation Techniques and Notation

• Summation by parts formula $\sum_{n \leq x} a_n b_n = A(x)b(x) - \int_1^x A(t)db(t)$ relates sums of products to integrals, where $A(x) = \sum_{n \leq x} a_n$
• Abel's summation formula $\sum_{n \leq x} a_n f(n) = A(x)f(x) - \int_1^x A(t)f'(t)dt$ is a variant for differentiable functions $f$
• Euler-Maclaurin summation formula expresses sums in terms of integrals and Bernoulli numbers, giving better error terms
  • Useful for approximating sums or bounding their growth rates
• Partial summation techniques estimate sums by splitting the range into intervals and applying bounds or asymptotics on each piece
• Sums over primes $\sum_{p \leq x} f(p)$ can be estimated using the Prime Number Theorem and partial summation
  • The PNT gives $\pi(x) \sim x/\log x$ where $\pi(x)$ counts primes up to $x$
• Sums over divisors $\sum_{d|n} f(d)$ are related to convolutions and can be evaluated using multiplicativity or Dirichlet series properties

Average Orders of Arithmetic Functions

• The average order $A_f(x) = \frac{1}{x} \sum_{n \leq x} f(n)$ represents the mean value of $f(n)$ over integers up to $x$
• For multiplicative functions, the average order is often determined by the behavior of the Dirichlet series $\sum_{n=1}^{\infty} \frac{f(n)}{n^s}$ near $s=1$
  • Selberg-Delange method uses complex analysis to derive asymptotics for $A_f(x)$ from the Dirichlet series
• For additive functions, the average order can be computed using the Lévy-Khintchine representation and probabilistic arguments
• The average order of the divisor function satisfies $A_d(x) \sim \log x$, a consequence of the hyperbola method
• The average order of Euler's totient function is $A_{\phi}(x) \sim \frac{6}{\pi^2}x$, related to the Riemann zeta function $\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s}$
• Studying the discrepancy between an arithmetic function and its average order leads to important problems and conjectures
  • The Erdős-Kac theorem describes the distribution of $\omega(n) - \log \log n$, showing it converges to a normal distribution

Dirichlet Series and Generating Functions

• Dirichlet series $\sum_{n=1}^{\infty} \frac{f(n)}{n^s}$ encode the values of an arithmetic function $f(n)$ and have an Euler product for multiplicative functions
  • The Riemann zeta function $\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s}$ is a prototypical Dirichlet series with a simple pole at $s=1$
• Euler products express Dirichlet series for multiplicative functions as infinite products over primes $\prod_p (1 + \frac{f(p)}{p^s} + \frac{f(p^2)}{p^{2s}} + \cdots)$
• Analytic properties of Dirichlet series (poles, residues, functional equations) are related to the asymptotic behavior of the arithmetic function
  • The Wiener-Ikehara Tauberian theorem deduces asymptotics for partial sums from Dirichlet series behavior
• Generating functions $\sum_{n=0}^{\infty} f(n)z^n$ encode sequences and are used to study additive functions or recurrence relations
• Dirichlet convolution corresponds to multiplication of Dirichlet series: $\sum_{n=1}^{\infty} \frac{(f*g)(n)}{n^s} = (\sum_{n=1}^{\infty} \frac{f(n)}{n^s})(\sum_{n=1}^{\infty} \frac{g(n)}{n^s})$
• Perron's formula relates partial sums of an arithmetic function to its Dirichlet series via a complex integral

Asymptotic Behavior and Growth Rates

• Big-O notation $f(n) = O(g(n))$ means $|f(n)| \leq Cg(n)$ for some constant $C$ and sufficiently large $n$, giving an upper bound on growth
• Little-o notation $f(n) = o(g(n))$ means $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$, indicating $f$ grows slower than $g$
• Asymptotic equivalence $f(n) \sim g(n)$ means $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$, so $f$ and $g$ have the same leading-order behavior
• Theta notation $f(n) = \Theta(g(n))$ means $f$ is bounded above and below by constant multiples of $g$ for large $n$
  • Equivalent to $f(n) = O(g(n))$ and $g(n) = O(f(n))$ simultaneously
• Landau's symbol $f(n) = \Omega(g(n))$ means $f$ grows at least as fast as $g$, i.e., $f$ is not $o(g(n))$
• Asymptotic analysis of arithmetic functions often involves estimating sums or integrals and comparing growth rates
  • Partial summation, complex analysis, and Tauberian theorems are common tools

Applications in Number Theory

• Prime number theorem $\pi(x) \sim \frac{x}{\log x}$ describes the asymptotic distribution of primes and is equivalent to $\sum_{p \leq x} \log p \sim x$
• Mertens' theorems relate sums over the Möbius function or prime reciprocals to the logarithm: $\sum_{n \leq x} \frac{\mu(n)}{n} = O(1)$ and $\sum_{p \leq x} \frac{1}{p} = \log \log x + O(1)$
• Brun's theorem states that the sum of reciprocals of twin primes converges, in contrast to the divergence of prime reciprocals
• Landau's theorem characterizes arithmetic functions with Dirichlet series that converge for $\Re(s) > \sigma_0$ and have a pole at $s = \sigma_0$
  • Used to prove the prime number theorem via the Riemann zeta function
• Siegel-Walfisz theorem gives a uniform estimate for primes in arithmetic progressions $\pi(x;k,a) \sim \frac{1}{\phi(k)} \frac{x}{\log x}$ for fixed $k$ and $(a,k)=1$
• Bombieri-Vinogradov theorem provides an average version of the Siegel-Walfisz theorem, important in sieve methods and density estimates
• Arithmetic functions and their averages appear in the study of L-functions, elliptic curves, and other areas of modern number theory

Common Challenges and Problem-Solving Strategies

• Estimating sums or integrals: Use partial summation, Euler-Maclaurin formula, or Perron's formula to relate sums to integrals or Dirichlet series
• Analyzing Dirichlet series: Identify poles, residues, and functional equations to deduce asymptotic behavior of coefficients
  • Apply Tauberian theorems or complex analytic methods like contour integration
• Proving asymptotic formulas: Decompose sums into main terms and error terms, estimate each part separately using appropriate tools
• Handling multiplicative functions: Exploit Euler product representations and convolution identities to simplify expressions
  • Use Möbius inversion to invert convolutions and recover the function from its summatory properties
• Dealing with additive functions: Utilize generating functions, Lévy-Khintchine representation, or probabilistic methods
• Comparing growth rates: Determine the relationship between functions using asymptotic notations like $O$, $o$, $\sim$, $\Theta$, $\Omega$
  • Derive inequalities or estimates to establish the desired bounds or equivalences
• Solving congruences and Diophantine equations: Employ arithmetic function identities, character sums, or sieve methods to count solutions
• Generalizing results: Identify key assumptions and try to weaken or remove them, extending the scope of theorems