LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

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.

Elementary lower bound for the totient ratio

Statement

For every integer $r \geq 1$ , $φ (r) / r \geq 1 / (1 + \log_{2} r)$ , with $φ (1) = 1$ .

Facts & Assumptions

Given: An integer $r \geq 1$ and its distinct prime divisors.

[F1]

If the distinct prime divisors of $r$ are $p_{1} < \dots < p_{ω}$ , then $φ (r) / r = \prod_{i = 1}^{ω} (1 - 1 / p_{i})$ ; the empty product is $1$ when $r = 1$ (Euler's product formula $φ (n) = n \prod_{p ∣ n} (1 - 1 / p) = \prod_{p^{k} ∥ n} (p^{k} - p^{k - 1})$ for $n \geq 1$ , stated through a finite injective list of its prime divisors).

[F2]

A prime is an integer greater than $1$ with no positive divisors other than $1$ and itself, and every integer $r \geq 2$ is a finite product of primes (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ , The fundamental theorem of arithmetic: every integer $n \geq 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i < r} p_{i} = \prod_{j < s} q_{j}$ with every $p_{i}$ and $q_{j}$ prime, then $r = s$ and $q_{i} = p_{π (i)}$ for some $π \in Sym (r)$ ).

[F3]

Integer multiplication is associative and commutative, and $d ∣ r$ means $r = d c$ for some integer $c$ (The integers form a commutative ring, Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

Proof

1.1givenF1

If $r = 1$ , then $ω = 0$ and [F1] gives $φ (1) / 1 = 1$ , which is the claimed bound. Suppose $r > 1$ .

2.1F1F2step 1.1algebra

For every $i$ , the increasing distinct primes satisfy $p_{i} \geq i + 1$ : there are only $i - 1$ integers strictly between $1$ and $i + 1$ , so fewer than $i$ distinct primes can lie there. Therefore each factor in [F1] obeys $1 - 1 / p_{i} \geq 1 - 1 / (i + 1) = i / (i + 1)$ . Multiplying positive factors gives $φ (r) / r \geq \prod_{i = 1}^{ω} i / (i + 1) = 1 / (ω + 1)$ .

3.1F2F3step 2.1algebra∎

Take a prime factor list for $r$ from [F2] and sort its distinct entries as $p_{1} < \dots < p_{ω}$ , choosing for each value its first occurrence in that finite list. By associativity and commutativity in [F3], regrouping the list gives $r = (p_{1} \dots p_{ω}) c$ for a positive integer $c$ . Thus the distinct-prime product divides $r$ , and since every $p_{i} \geq 2$ , $r \geq 2^{ω}$ . Therefore $ω \leq \log_{2} r$ , so $1 / (ω + 1) \geq 1 / (1 + \log_{2} r)$ . This proves the assertion.

Depends on

Used by

Dependency tree · two levels

58 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

Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415v6 (standard reference, not scraped)