Arithmetic functions refresher

This page is a beginner-friendly refresher for experiments about arithmetic functions (i.e. functions \(f:\mathbb{N}\to\mathbb{C}\) that encode number-theoretic structure).

For deeper treatments, see [Apostol, 1976], [Niven et al., 1991], and [Tenenbaum, 2015].

What “arithmetic function” usually means

An arithmetic function is any function of a positive integer \(n\). Common themes:

  • prime factorization drives the behavior of many functions

  • multiplicativity lets you reduce to prime powers

  • averages and summatory functions reveal global structure

Examples you will meet often:

  • Euler’s totient \(\varphi(n)\) (coprime residues)

  • Möbius \(\mu(n)\) and Mertens \(M(x)=\sum_{n\le x}\mu(n)\)

  • divisor counts \(d(n)\) and sums \(\sigma_k(n)\)

  • prime-factor counting \(\omega(n),\Omega(n)\)

  • von Mangoldt \(\Lambda(n)\) (prime powers)

  • Carmichael’s \(\lambda(n)\) (group exponent mod \(n\))

Multiplicative vs. additive

Multiplicative

An arithmetic function \(f\) is multiplicative if

\[ f(1)=1,\qquad f(ab)=f(a)f(b)\;\; \text{whenever }\gcd(a,b)=1. \]

If \(n=\prod p_i^{\alpha_i}\) then multiplicativity gives

\[ f(n)=\prod f(p_i^{\alpha_i}). \]

Typical: \(\varphi,\mu,\sigma_k,d,J_k,\lambda\).

Additive

A function \(g\) is additive if

\[ g(ab)=g(a)+g(b)\;\; \text{whenever }\gcd(a,b)=1, \]

and completely additive if the relation holds for all \(a,b\) (no gcd condition). Typical: \(\Omega(n)\) is completely additive; \(\omega(n)\) is additive.

Why averages matter

Many experiments compare:

  • pointwise behavior of \(f(n)\)

  • cumulative behavior \(\sum_{k\le n} f(k)\)

  • distribution of \(f(n)\) over ranges

Analytic/probabilistic number theory focuses on these averages; see [Montgomery and Vaughan, 2006] and [Tenenbaum, 2015].

Common experiment patterns

  • Value distribution: histograms of \(f(n)\) for \(n\le N\)

  • Scatter vs. factorization features: compare \(f(n)\) with \(\log n\), \(\omega(n)\), etc.

  • Normal order: show “typical size” vs. rare extremes (e.g. Erdős–Kac behavior)

  • Summatory oscillations: \(M(x)\), \(\sum_{n\le x}\lambda(n)\), etc.

  • Extremal orders: highly composite numbers maximize \(d(n)\) (see [Ramanujan, 1915])

Experiments in this repository

  • E121 — Multiplicativity stress tests across core arithmetic functions.

  • E123 — Correlation matrix of arithmetic functions on 1..N (empirical relationships).