Analytic & Probabilistic Number Theory

Intuition, Vocabulary and Foundations

Analytic number theory studies arithmetic objects by measuring their collective behavior. Instead of asking whether one integer is prime, it asks how many primes lie below a large threshold. Instead of evaluating one divisor count, it studies the accumulated or average value across an interval. The perspective resembles traffic analysis: individual cars are irregular, but total flow can obey stable large-scale laws.

Let $\pi(x)$ denote the number of primes not exceeding $x$. The Prime Number Theorem states $\pi(x)\sim x/\log x$, meaning that the ratio approaches $1$ as $x\to\infty$. It suggests that a large integer near $x$ behaves heuristically like a prime with probability about $1/\log x$. For example, $\pi(100)=25$, while $100/\log 100\approx21.7$. The estimate is informative but not exact, especially for small inputs.

A summatory function converts an arithmetic function into a cumulative signal: $F(x)=\sum_{n\le x}f(n)$. Examples include the divisor summatory function $\sum_{n\le x}\tau(n)$ and the Mertens function $M(x)=\sum_{n\le x}\mu(n)$. An average order $g(n)$ describes the typical accumulated scale when $\sum_{n\le x}f(n)\sim\sum_{n\le x}g(n)$; it need not approximate every individual value.

Dirichlet series encode arithmetic sequences as $D_f(s)=\sum_{n=1}^{\infty}f(n)n^{-s}$. Multiplication of Dirichlet series corresponds to Dirichlet convolution where convergence permits. Dirichlet characters encode residue classes multiplicatively, and their orthogonality isolates congruence conditions. Probabilistic models supply useful predictions about prime searches, but a heuristic probability is not a proof about any specific integer.

Step-by-Step Derivations and Algorithms

Partial summation is the discrete analogue of integration by parts. If $A(x)=\sum_{n\le x}a_n$, then for a differentiable weight $f$,

$$ \sum_{n\le x}a_n f(n)=A(x)f(x)-\int_1^x A(t)f'(t)\,dt, $$

with endpoint conventions adjusted to the application. It transfers information about an unweighted summatory function into a weighted sum, including estimates for weighted prime sums.

Character orthogonality acts as a residue-class filter. For reduced residues $a$ and $n$ modulo $q$, the normalized sum $\varphi(q)^{-1}\sum_{\chi\bmod q}\overline{\chi(a)}\chi(n)$ equals $1$ when $n\equiv a\pmod q$ and $0$ otherwise. This turns a congruence-restricted sum into character-twisted sums, provided nonunits and normalization are handled explicitly.

Harmonic decomposition exploits the fact that $\lfloor n/i\rfloor$ assumes only $O(\sqrt n)$ distinct values. If $q=\lfloor n/i\rfloor$, the quotient persists through $r=\lfloor n/q\rfloor$. An exact loop therefore processes $[i,r]$ at once and jumps to $r+1$.

For randomized prime generation, a $b$-bit odd candidate lies near $2^b$. The Prime Number Theorem gives density about $1/(b\log2)$ among all nearby integers and approximately twice that among odd candidates, leading to an expected $(b\log2)/2$ odd trials. This is a model-based expectation, not a hard upper bound.

flowchart TD
    A["State the arithmetic quantity"] --> B{"Exact or asymptotic goal?"}
    B -->|Exact| C["Build a summatory identity"]
    C --> D{"Repeated floor quotients?"}
    D -->|Yes| E["Use harmonic blocks"]
    D -->|No| F["Use sieve or direct summation"]
    B -->|Asymptotic| G["Choose analytic encoding"]
    G --> H{"Residue restriction?"}
    H -->|Yes| I["Apply character orthogonality"]
    H -->|No| J["Use partial summation or Dirichlet series"]
    E --> K["Verify with an exact oracle"]
    F --> K
    I --> L["Attach theorem and error regime"]
    J --> L
    L --> M["Label guarantees and heuristics"]

Implementation, Complexity and Engineering

The reference implementation builds an exact sieve oracle, compares $\pi(x)$ with elementary asymptotic estimates, evaluates the divisor summatory function directly and by harmonic grouping, and verifies character orthogonality for the two real characters modulo $4$. Returned labels distinguish exact values from heuristic estimates.

Floating-point formulas are used only for estimates. They never determine primality or an exact arithmetic answer. Large-input systems should record the range of every explicit bound, avoid unstable subtraction, and use higher precision when required by the error budget.

from math import isqrt, log


def prime_table(limit):
    if limit < 0:
        raise ValueError("limit must be nonnegative")
    sieve = bytearray(b"\x01") * (limit + 1)
    sieve[0] = 0
    if limit >= 1:
        sieve[1] = 0
    for prime in range(2, isqrt(limit) + 1):
        if sieve[prime]:
            start = prime * prime
            sieve[start : limit + 1 : prime] = b"\x00" * (
                (limit - start) // prime + 1
            )
    return sieve


def prime_count_prefix(limit):
    sieve = prime_table(limit)
    prefix = [0] * (limit + 1)
    count = 0
    for value in range(limit + 1):
        count += sieve[value]
        prefix[value] = count
    return sieve, prefix


def prime_count_estimates(x):
    if x < 2:
        return {"kind": "heuristic asymptotic", "pnt": 0.0, "second_order": 0.0}
    lx = log(x)
    return {
        "kind": "heuristic asymptotic",
        "pnt": x / lx,
        "second_order": x / lx + x / (lx * lx),
    }


def divisor_summatory_direct(n):
    if n < 0:
        raise ValueError("n must be nonnegative")
    return sum(n // divisor for divisor in range(1, n + 1))


def divisor_summatory_harmonic(n):
    """Return sum_{d <= n} floor(n / d) in O(sqrt(n)) blocks."""
    if n < 0:
        raise ValueError("n must be nonnegative")
    total = 0
    left = 1
    blocks = []
    while left <= n:
        quotient = n // left
        right = n // quotient
        total += quotient * (right - left + 1)
        blocks.append((left, right, quotient))
        left = right + 1
    return total, blocks


def chi_mod_4(kind, value):
    residue = value % 4
    if residue % 2 == 0:
        return 0
    if kind == "principal":
        return 1
    if kind == "odd":
        return 1 if residue == 1 else -1
    raise ValueError("unknown character")


def character_filter_mod_4(value, target):
    if target not in (1, 3):
        raise ValueError("target must be 1 or 3 modulo 4")
    total = sum(
        chi_mod_4(kind, target) * chi_mod_4(kind, value)
        for kind in ("principal", "odd")
    )
    return total // 2


def expected_odd_trials_for_b_bit_prime(bits):
    if bits < 2:
        raise ValueError("bits must be at least 2")
    return bits * log(2) / 2


sieve, pi = prime_count_prefix(100)
assert pi[10] == 4
assert pi[100] == 25
assert [i for i, flag in enumerate(sieve) if flag][:6] == [2, 3, 5, 7, 11, 13]

exact = divisor_summatory_direct(100)
grouped, blocks = divisor_summatory_harmonic(100)
assert exact == grouped == 482
assert blocks[0] == (1, 1, 100)
assert blocks[-1] == (51, 100, 1)
assert len(blocks) <= 2 * isqrt(100)

for value in range(1, 40):
    assert character_filter_mod_4(value, 1) == int(value % 4 == 1)
    assert character_filter_mod_4(value, 3) == int(value % 4 == 3)

estimates = prime_count_estimates(100)
assert 21 < estimates["pnt"] < 22
assert expected_odd_trials_for_b_bit_prime(2048) > 700

try:
    divisor_summatory_harmonic(-1)
    raise AssertionError("negative input was accepted")
except ValueError:
    pass

print("all tests passed")

Applications, Case Studies and Exercises

Analytic estimates help size prime tables, predict randomized search work, and select between exact and asymptotic methods. Their practical value depends on disciplined labels: exact harmonic decomposition can produce a production answer, while a Prime Number Theorem estimate may guide capacity planning but cannot replace validation.