Average Order of an Arithmetic Function¶

Describe an arithmetic function's aggregate growth with a simpler function whose initial-interval sums are asymptotically equivalent.

Version: v2 · 2026-10-03 · History
Domain-specific #: 12999
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Arithmetic Function Asymptotics, Summatory Methods → Mathematics
Aliases: Average order of arithmetic functions, Arithmetic-function average order

Core Idea¶

An arithmetic function may vary sharply between consecutive integers while its accumulated values follow a simple large-scale law. An average order of \(f\) is a simpler comparator \(g\) for which the two initial-interval sums are asymptotically equivalent:

\[ S_f(x)=\sum_{n\le x}f(n),\qquad S_g(x)=\sum_{n\le x}g(n),\qquad S_f(x)\sim S_g(x)\quad(x\to\infty). \]

Here \(\sim\) normally means \(S_f(x)/S_g(x)\to1\) where the ratio is meaningful. The claim concerns aggregate growth, not \(f(n)/g(n)\to1\) for each integer, nor agreement at almost every integer. Choosing \(g\) continuous or monotone can make the approximation legible, but that is a conventional refinement, not the logical source of average order. The comparator is generally not unique.^[1]^[2]

For example, the divisor-count function \(d(n)\) has \(\sum_{n\le x}d(n)\sim x\log x\), while \(\sum_{n\le x}\log n\sim x\log x\). Thus \(\log n\) is one average order of \(d(n)\). This emphatically does not mean most integers near \(x\) have roughly \(\log x\) divisors: Hardy and Ramanujan's original analysis explains that the divisor function's typical scale is substantially lower and that unusually large values affect the average.^[2]

Structural Signature¶

Sig role-phrases: integer-indexed arithmetic function; initial-interval summatory transform; simpler comparator; ratio-asymptotic equivalence; pointwise and normal-order boundary.

Arithmetic carrier: \(f:\mathbb N\to\mathbb R\) or \(\mathbb C\) associates a number-theoretic value with each positive integer; an order comparison requires the relevant sums to have interpretable asymptotics.
Initial-interval accumulation: \(S_f(x)\) sums all \(f(n)\) for \(n\le x\), smoothing local fluctuations through aggregation.^[1]
Simpler comparator: \(g\) is chosen so \(S_g(x)\) is understood and easier to communicate than \(S_f(x)\); a nice regularity convention can aid this choice.
Asymptotic equivalence: the ratio of the summatory quantities tends to one, not merely remains bounded or has the same rough power of \(x\).^[1]
Interpretive separation: average order is distinct from pointwise size, maximum order and normal order on a density-one set.^[2]
Mean-value case: if \(\frac1x S_f(x)\to c\ne0\), then constant \(g(n)=c\) is an average order because \(S_g(x)\sim cx\). A zero mean needs more care: \(S_g=0\) gives no usable ratio-asymptotic denominator.^[1]

Condensed: integer-valued input sequence + cumulative sum + simpler asymptotically equivalent cumulative sum = average order.

What It Is Not¶

Not a pointwise approximation. \(d(n)\) takes irregular values, and its average order \(\log n\) does not state \(d(n)\sim\log n\) for every \(n\).^[2]
Not normal order. Normal order describes a comparison valid for almost all integers in natural-density terms; average order concerns sums and can be affected disproportionately by sparse large values.^[2]
Not the summatory function itself. \(S_f(x)\) is an accumulated object. Average order is a relation identifying a simpler \(g\) with \(S_g(x)\sim S_f(x)\).
Not unique by definition. Two distinct \(g\)'s can have equivalent leading sums; a chosen smooth or monotone representative does not make the relation uniquely determined.^[1]
Not an unrestricted “mean value zero” assertion. If \(S_f(x)=o(x)\), one may call the mean zero, but \(S_f(x)\sim\sum_{n\le x}0\) is not a valid ordinary ratio-asymptotic statement.
Not automatically a statement about sampled data or probability. The averaging index runs over positive integers, and the assertion is a deterministic number-theoretic limit.

Scope of Application¶

The concept is useful whenever an arithmetic function has a tractable summatory asymptotic even though its individual values vary. Divisor counts, totients, divisor sums and the von Mangoldt function are standard examples. The Encyclopedia of Mathematics lists \(\log n\) for \(d(n)\), \((6/\pi^2)n\) for Euler's totient \(\varphi(n)\), and constant 1 for the von Mangoldt function under the prime number theorem.^[1]

For the divisor-count case, Hardy and Ramanujan explicitly distinguish its average from its typical order. This makes the entry more than a generic use of “average”: it is a named asymptotic relation that can hide rare, large contributions.^[2]

For \(\Lambda(n)\), the prime number theorem gives \(\frac1x\sum_{n\le x}\Lambda(n)=1+o(1)\). Tao's analytic-number-theory lecture notes use this mean-one property in discussing the von Mangoldt weight. Here the constant comparator is legitimate because the leading summatory scale is \(x\ne0\). The example does not assert that \(\Lambda(n)\) is near 1 at most individual integers; in fact it vanishes except at prime powers.^[3]

Clarity¶

The phrase “takes the same values on average” is a mnemonic, not a pointwise equality. The exact test is to compare \(S_f(x)\) and \(S_g(x)\) as \(x\) grows. If their ratio tends to one, the leading cumulative mass agrees. If \(g(n)\) merely resembles a graph of \(f(n)\) at selected points, the average-order condition has not been established.^[1]

For \(d(n)\), the contrast is striking: summing divisor counts through \(x\) yields roughly \(x\log x\), yet the typical divisor count is on a smaller scale. Hardy and Ramanujan warned that one cannot simply infer a strict normal-order equivalence \(d(n)\sim(\log n)^{\log2}\) from their bounds; their “roughly” description and the average-order \(\log n\) answer different questions.^[2]

Manages Complexity¶

Summation suppresses local arithmetic spikes and oscillations, replacing a jagged integer sequence with an asymptotic growth profile. Once a simple \(g\) is known, many calculations need only the leading contribution to \(S_f(x)\), not a formula for every \(f(n)\). This is useful when divisor structure, primes and factorization create irregular local behavior.^[2]^[3]

That economy has a limit. Two arithmetic functions may share an average order while having very different distributions, exceptional sets or error terms. The relation discards information about typical values and fine fluctuations. When those matter, normal-order, distributional or sharper summatory estimates are separate tasks.

Abstract Reasoning¶

Identify \(f\) and prove or obtain an asymptotic for its summatory function \(S_f(x)\). Choose an interpretable \(g\) and independently evaluate \(S_g(x)\). Check the ratio, including that the comparison scale does not vanish in a way that makes \(\sim\) meaningless. State the growth regime and any assumptions. Only then call \(g\) an average order.^[1]

If a numerical mean \(\frac1xS_f(x)\) tends to nonzero \(c\), test the constant comparator \(g(n)=c\). If the mean is zero, do not divide by the zero comparator; use an \(o(x)\) statement or seek a more informative nonzero leading term. Finally, distinguish conclusions about the sum from claims about all or almost all \(n\).

Knowledge Transfer¶

The divisor and von Mangoldt cases share the same architecture: a jagged arithmetic function, an initial-interval sum, and a simpler comparator with matching leading sum. The particular \(g\) changes—\(\log n\) versus 1—because the aggregate growth changes. The structural reasoning transfers without implying any common pointwise behavior.^[2]^[3]

The live Normal Order of an Arithmetic Function is a sibling notion with density-one rather than summatory comparison. The live Divisor Summatory Function is one accumulated object, not the average-order relation. Asymptotic Behavior is a proposed prime parent, subject to prospective DAG review.

Examples¶

Divisor count¶

Let \(d(n)\) count positive divisors of \(n\), and set \(m=\lfloor x\rfloor\). Counting each pair \(ab\le m\) by its first factor gives the executed summatory identity [ \sum_{n\le x}d(n)=\sum_{a=1}^{m}\left\lfloor\frac{m}{a}\right\rfloor =m\sum_{a=1}^{m}\frac1a+O(m) =m\log m+O(m). ] The \(O(m)\) term follows because replacing each of the \(m\) floors by \(m/a\) changes it by less than one; the harmonic sum is \(\log m+O(1)\). Separately, \(\sum_{n\le x}\log n=\log(m!)=m\log m+O(m)\), by integral comparison or Stirling. Their cumulative ratio therefore tends to one, exactly the relation in the Encyclopedia definition and Hardy–Ramanujan's Eq. (1.21). This does not say that \(d(n)\) is close to \(\log n\) for almost every \(n\).^[2]^[1]

Mapped back: \(f=d\); \(g=\log n\); aggregation counts divisor pairs to get \(m\log m+O(m)\); the comparator sum gives the same leading term; the ratio of sums, not values at individual \(n\), tends to one.

Von Mangoldt mean one¶

The von Mangoldt function \(\Lambda(n)\) is zero except at prime powers, where it is a logarithmic weight. The prime number theorem yields \(S_\Lambda(x)\sim x\), so \(g(n)=1\) is an average order. The drastic pointwise difference between 0 and 1 on composite non-prime-powers is precisely why the summatory qualifier matters.^[3]^[1]

Mapped back: \(f=\Lambda\); \(g=1\); aggregate comparison = \(S_\Lambda(x)\sim x\).

Smooth-looking near miss¶

Suppose someone plots a smooth \(g(n)\) through a few observed points of an irregular \(f\) but has no estimate for either cumulative sum. Visual similarity is insufficient. Conversely, a valid \(g\) might be far from \(f(n)\) on most individual integers while still matching the total growth.

Structural Tensions¶

Aggregate compression versus local information. Using summatory equivalence gives a tractable leading total even for irregular \(d(n)\), but pays for that compression by losing information about a typical integer or any particular value. Seeking normal or pointwise order requires a separate, often harder theorem rather than a reinterpretation of the average. Hardy and Ramanujan explicitly distinguish the average and normal questions. Diagnostic: does the desired claim concern the sum, a typical integer, or every integer?^[2]

Simple leading comparator versus precision. A smooth \(g\), such as \(\log n\) for \(d(n)\), communicates the leading trend, but many comparators share the same leading cumulative sum. Hardy and Ramanujan give a more detailed divisor-sum expansion beyond \(x\log x\); retaining that error and secondary term costs a more precise statement but can distinguish estimates that average order alone treats as equivalent. Diagnostic: is only leading asymptotic order needed, or do secondary terms and explicit error matter?^[2]^[1]

Structural–Framed Character¶

Average order sits toward the structural end: the ratio-asymptotic test on two specified summatory functions has a determinate mathematical truth value. The choice to call a comparator “simpler” or useful has some evaluative weight, but does not change the asymptotic relation. Human mathematical practice selects \(g\), an error tolerance and an explanatory aim; it does not create the integer-domain sums being compared. The term arose in analytic-number-theory usage and travels literally from divisor counts to von Mangoldt weights because each instance satisfies the same summatory comparison, not because any dataset can be said to have an “average.” Importing the name into a moving time-series average without the integer summatory test is analogy. The normal-order distinction matters because Hardy and Ramanujan explicitly posed it as a separate density-one question. Its character: a structural asymptotic relation on arithmetic functions, with framed comparator selection and reporting precision.^[1]^[2]

Structural Core vs. Domain Accent¶

The portable skeleton is large-scale comparison under a limiting relation, supplied by the live Asymptotic Behavior as the parent. The domain-bound mechanism is the deterministic initial-interval sum over integers and a simpler arithmetic-function comparator whose summatory ratio tends to one; Hardy–Ramanujan's divisor calculation and the prime-number-theorem case instantiate that exact test. The named entry fails the prime bar because removing the arithmetic carrier and summatory construction leaves only generic asymptotic comparison. A time-series moving average or expected value shares a family resemblance but is not this identity.^[1]^[2]

This entry is a kind of Asymptotic Behavior.

Asymptotic Behavior: the relation concerns \(x\to\infty\) and equality of leading summatory growth; strict parent.
Aggregation: sums collect local values into a global quantity.
Approximation: \(g\) is a deliberately simpler comparator, but agreement is at the summatory level.

Only the first is an upward DAG edge.

Relationships to Other Abstractions¶

Current abstraction Average Order of an Arithmetic Function Domain-specific

Parents (1) — more general patterns this builds on

Average Order of an Arithmetic Function is a kind of Asymptotic Behavior Prime

Average order compares the limiting growth of arithmetic-function initial sums.

Hierarchy paths (2) — routes to 2 parentless roots

Average Order of an Arithmetic Function → Asymptotic Behavior → Approximation → Representation → Abstraction

Show alternative path (1)

Neighborhood in Abstraction Space¶

Average Order of an Arithmetic Function sits in a moderately populated region (48^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Number-Theoretic Properties & Tests (20 abstractions)

Nearest neighbors

Normal Order of an Arithmetic Function — 0.87
Two-Element Boolean Algebra — 0.87
Binade — 0.86
Linear order — 0.86
Smallest-Circle Problem — 0.86

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Normal order asks what size holds on a density-one set; maximum order tracks extremal values; pointwise asymptotics compare \(f(n)\) and \(g(n)\) at each large \(n\); summatory function names \(S_f\) itself. Average order is the asymptotic equivalence \(S_f\sim S_g\), which does not imply the others.^[2]^[1]

References¶

[1] Encyclopedia of Mathematics, “Average order of an arithmetic function”. Specialist definition, regularity convention and standard examples. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n

[2] Hardy and Ramanujan, original paper on the normal number of prime factors, digitized collected-paper text. Original average/normal-order distinction and divisor-count asymptotic. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o

[3] Terence Tao, original analytic-number-theory lecture notes on the transference principle and von Mangoldt weights. Prime-number-theorem mean-one relation for \(\Lambda\). registry ↩a ↩b ↩c ↩d