PropositionStatement: AI-generatedProof: AI-generated

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.

Floor and ceiling thresholds in logarithmic degree estimates

Statement

Let $a_{n}, c_{n}$ be real, $b_{n} > 0$ , and for integers $k \geq 0$ put $F_{n} (k) = a_{n} + k \log b_{n} - \log (k!) + c_{n} k$ , where $\log$ is the natural logarithm and $0! = 1$ . Then $F_{n} (k + 1) - F_{n} (k) = \log b_{n} - \log (k + 1) + c_{n}$ .

For $t \geq 0$ , let $m = ⌊ t ⌋$ be the unique integer satisfying $m \leq t < m + 1$ , and let $⌈ t ⌉$ be $m$ if $t = m$ and $m + 1$ otherwise. Define the piecewise linear interpolation ${\tilde{F}}_{n} (t) = (1 - (t - m)) F_{n} (m) + (t - m) F_{n} (m + 1)$ . For either $r = ⌊ t ⌋$ or $r = ⌈ t ⌉$ , $∣ F_{n} (r) - {\tilde{F}}_{n} (t) ∣ \leq ∣ \log b_{n} ∣ + \log (m + 1) + ∣ c_{n} ∣$ .

In particular, fix $γ > 0$ and $C \geq 0$ . If $b_{n} = γ \log n$ , $∣ c_{n} ∣ \leq C$ and $0 \leq m \leq C \log n$ for integers $n$ sufficiently large, then the last difference is at most $4 \log \log n$ for all sufficiently large $n$ , with the threshold depending only on $γ$ and $C$ . Thus it is $O (\log \log n)$ : its absolute value is bounded by a constant multiple of $\log \log n$ eventually. The interpolation uses factorials only at integers; a factorial at a noninteger would require a separately specified extension.

Statement references

Integer part: for every real x there is exactly one integer m with m ≤ x < m + 1

The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

Facts & Assumptions

[F1]

The factorial recursion gives $(k + 1)! = (k + 1) k!$ , with $k! > 0$ , for every integer $k \geq 0$ (The factorial n! and the falling factorial n^k̲, defined by recursion in ℕ).

[F2]

The natural logarithm is increasing on positive reals and satisfies $\log (x y) = \log x + \log y$ there (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

[F3]

Every real number has a unique integer part $m$ with $m \leq t < m + 1$ (Integer part: for every real x there is exactly one integer m with m ≤ x < m + 1).

Proof

Given: The quantities and hypotheses in the statement.

Goal: Prove the increment, interpolation bound, and stated eventual budget.

1.1F1F2algebra

By factorial recursion and the logarithm product law, $\log ((k + 1)!) = \log (k + 1) + \log (k!)$ . Subtracting the two definitions of $F_{n}$ therefore gives $F_{n} (k + 1) - F_{n} (k) = \log b_{n} - \log (k + 1) + c_{n}$ .

2.1F2F3step 1.1algebra

Put $u = t - m$ , so $0 \leq u < 1$ . The interpolation lies on the line segment between $F_{n} (m)$ and $F_{n} (m + 1)$ . Each permitted endpoint is one of these values, so its distance from the interpolation is at most $∣ F_{n} (m + 1) - F_{n} (m) ∣$ . Since $m + 1 \geq 1$ , logarithm monotonicity gives $\log (m + 1) \geq 0$ ; the triangle inequality and step 1.1 yield the stated bound.

3.1F2step 2.1algebra∎

For sufficiently large $n$ , $\log \log n \geq 0$ , and $m + 1 \leq (C + 1) \log n$ . Hence $∣ \log b_{n} ∣ \leq ∣ \log γ ∣ + \log \log n$ and $\log (m + 1) \leq \log (C + 1) + \log \log n$ . The bound in step 2.1 is therefore at most $2 \log \log n + ∣ \log γ ∣ + \log (C + 1) + C$ . As $\log \log n$ tends to infinity, the fixed latter terms are at most $2 \log \log n$ eventually. This proves the $4 \log \log n$ and big-O assertions. The construction only evaluates factorials at $m$ and $m + 1$ .

Depends on

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.