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.
Chebyshev's theta function has linear lower and upper bounds
Statement
There exist positive constants and a real number such that
for every real .
Facts & Assumptions
Given: A real number .
The central binomial coefficient satisfies for every natural number (Central binomial coefficient bounds).
For every prime and natural , primes with divide , and in general (Prime valuations in the central binomial coefficient).
The binomial theorem gives (The binomial theorem in : ).
The closed form holds for ( for ; hence , the quotient is a natural number, and ).
The logarithm satisfies and (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).
Induction on is valid (The principle of mathematical induction).
Proof
Put for real . We claim that Let be the largest prime with . Then and , so it suffices to prove the claim when is prime. For this is immediate. Let be an odd prime, and assume inductively that for every integer with . Then Every prime in the second product divides by [L4], because it appears in the numerator and in neither denominator factorial. Also [L3] gives and the two equal middle terms therefore satisfy . Thus So the claim holds for every real .
Again by [L2], the factorization of can be written as where Using the trivial estimate on each layer and for , we get
By definition of and the logarithm law in [L5], for every real .
The lower bound in [L1] and [L5] give Combining this with step 1.2 shows Since , choose so large that for every . Then
Let , and put . Then and , so by monotonicity of and step 2.2, Step 2.1 also gives for every . Thus the theorem holds with , , and .
Depends on
- Chebyshev's theta function
- Central binomial coefficient bounds
- Prime valuations in the central binomial coefficient
- Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm
- The binomial theorem in $\mathbb{R}$: $(x+y)^{n} = \sum_{k<n+1} \iota\!\binom{n}{k}\, x^{k} y^{\,n-k}$
- $\binom{n}{k}\,k!\,(n-k)! = n!$ for $k \le n$; hence $\binom{n}{k}\,k! = n^{\underline{k}}$, the quotient $n!/(k!(n-k)!)$ is a natural number, and $\binom{n}{k} = \binom{n}{n-k}$
- The principle of mathematical induction
Used by
Dependency tree · two levels
47 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
- Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 2 (standard reference, not scraped)
- Karl-Dieter Crisman, Number Theory: In Context and Interactive (standard reference, not scraped)