CorollaryStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck passverified 2026-09-24 (gpt-6-sol)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Prime number theorem

Statement

As $x \to \infty$ , $π (x) \sim x / \log x, θ (x) \sim x, ψ (x) \sim x .$ These three asymptotic assertions are equivalent.

Facts & Assumptions

Given: The data and hypotheses of the statement.

[F1]

Prime number theorem arithmetic progressions: For each fixed $q \geq 1$ and each unit class $a$ modulo $q$ , $π (x; q, a) \sim Li (x) / φ (q)$ . In particular, the case $q = 1$ gives $π (x) \sim Li (x)$ .

[F2]

Logarithmic integral asymptotic expansion: For each fixed integer $m \geq 1$ , as $x \to \infty$ , $Li (x) = \sum_{j = 0}^{m - 1} \frac{j! x}{\log^{j + 1} x} + O_{m} (\frac{x}{\log^{m + 1} x}) .$

[F3]

Abel summation recovers the prime-counting function from theta: For every real $x \geq 2$ , $π (x) = \frac{θ (x)}{\log x} + \int_{2}^{x} \frac{θ (t)}{t \log^{2} t} d t .$

[F4]

Psi and theta differ by at most a square-root term: There are positive constants $K_{1}, K_{2}$ such that for every real $x \geq 2$ , $0 \leq ψ (x) - θ (x) \leq K_{1} \sqrt{x} \log x$ and, for all sufficiently large $x$ , $ψ (x) - θ (x) \leq K_{2} \sqrt{x} .$

Proof

1.1F1F2

Apply the progression theorem at $q = 1$ , where every prime belongs to the unique unit class and $φ (1) = 1$ . Its counting asymptotic and the first Li term give $π (x) \sim x / \log x$ .

1.2F3

Independently, if $θ (x) \sim x$ , the exact Abel formula gives $π (x) \sim x / \log x$ : its integral is $O (x / \log^{2} x)$ , by splitting at $\sqrt{x}$ and using $θ (t) = O (t)$ .

2.1F4step 1.1step 1.2∎

Conversely summing $\log p = \log x - \int_{p}^{x} d t / t$ over the finitely many primes $p \leq x$ gives $θ (x) = π (x) \log x - \int_{2}^{x} π (t) d t / t$ . If $π (t) \sim t / \log t$ , the integral is $O (x / \log x) = o (x)$ by the same square-root split, so $θ (x) \sim x$ . Finally $0 \leq ψ (x) - θ (x) = O (\sqrt{x} \log x) = o (x)$ , proving both directions between theta and psi. Combine these implications with the first step.

Depends on

Used by

Nth prime asymptotic Corollary
Dirichlet density alone does not give a counting asymptotic Counterexample
Newman tauberian prime number theorem Example
Logspace uniform iterated multiplication threshold circuits Lemma

Dependency tree · two levels

17 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

§1.3, Lemma 1.7 (standard reference, not scraped)