LemmaStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-09

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.

Admissible parameters for the density recursion

Statement

Let $ℓ$ be subreciprocal, $0 < c < 1 / 2$ , $d > 1$ . Set $z = ℓ (c)^{- 1 / 2}$ and $b = 2 - \log_{2} (1 - z) > 2$ . For $0 < ϵ < c$ , put $L = \log_{2} (1 / ϵ)$ , $Q = \log_{2} ℓ (ϵ)$ , $x = 2^{1 - b} ϵ$ , $p = z ℓ (x)$ , and $η = x^{d} / 4$ . Let $t = - ⌊ - 2 L / \log_{2} p ⌋$ , and $δ = 2^{- 20 b d L^{2} / Q}$ . Then $t$ is the least natural number with $p^{t} \geq ϵ^{- 2}$ and $0 < η < 1, p > 1, p^{2} \geq ℓ (x), 1 \leq t \leq 5 L / Q, δ < x^{d} η^{t} .$ This asserts admissibility of the recursion parameters; no new operation on functions is implicit in the title.

Facts & Assumptions

Given: A subreciprocal $ℓ$ , $0 < c < 1 / 2$ , $d > 1$ , $0 < ϵ < c$ , and the real parameters defined in the statement.

[F1]

From Subreciprocal function and ell divisibility: A function $ℓ : (0, 1 / 2) \to (0, \infty)$ is subreciprocal when it is nonincreasing and satisfies $1 < ℓ (x) \leq 1 / x$ throughout its domain.

[F2]

For every real $y$ , its unique integer part satisfies $⌊ y ⌋ \leq y < ⌊ y ⌋ + 1$ . (Integer part: for every real $x$ there is exactly one integer $m$ with $m \leq x < m + 1$ ).

[F3]

$\log_{b} x = \frac{\log x}{\log b}, b^{\log_{b} x} = x, \log_{b} (b^{u}) = u (u \in R)$ . (Change of base and inversion of the positive-base real exponential).

[F4]

$a^{r + s} = a^{r} a^{s}, (a b)^{r} = a^{r} b^{r}, (a / b)^{r} = a^{r} / b^{r}, (a^{r})^{s} = a^{r s}$ . (The exponent, product, quotient, and iterated-power laws for positive real bases and real exponents).

Proof

1.1F1F3given

By [F1], $ℓ (c) > 1$ , so $0 < z < 1$ and $0 < 1 - z < 1$ . By [F3], $b = 2 - \log_{2} (1 - z) > 2$ satisfies $2^{2 - b} = 1 - z$ . Thus $0 < x = ϵ (1 - z) / 2 < ϵ < c < 1 / 2$ and $0 < η = x^{d} / 4 < 1$ . Every evaluation of $ℓ$ is in its domain.

2.1F1step 1.1algebra

Monotonicity in [F1] gives $ℓ (x) \geq ℓ (ϵ) \geq ℓ (c) = z^{- 2}$ . Consequently $p^{2} = z^{2} ℓ (x)^{2} \geq ℓ (x) > 1$ , so $p > 1$ . Also $0 < Q \leq L$ because $1 < ℓ (ϵ) \leq 1 / ϵ$ , and $\log_{2} p \geq Q / 2 > 0$ .

3.1F2F3step 2.1algebra

Put $u = 2 L / \log_{2} p > 0$ . Apply [F2] to $- u$ and negate: $u \leq t < u + 1$ . Thus $t \geq 1$ is an integer; $t - 1 < u \leq t$ and [F3] give $p^{t - 1} < ϵ^{- 2} \leq p^{t}$ , which proves minimality among naturals. Since $u \leq 4 L / Q$ and $L / Q \geq 1$ , we have $t < 4 L / Q + 1 \leq 5 L / Q$ .

4.1F4step 1.1step 3.1algebra

The inequality $ϵ < 1 / 2$ implies $ϵ^{b - 1} < 2^{1 - b}$ , hence $x > ϵ^{b}$ , and $4^{- t} > ϵ^{2 t}$ . By [F4], $x^{d} η^{t} = 4^{- t} x^{d (t + 1)} > ϵ^{2 t + b d (t + 1)}$ . Finally $4 b d t - [2 t + b d (t + 1)] = b d (3 t - 1) - 2 t \geq 2 t (b d - 1) > 0$ , so this exceeds $ϵ^{4 b d t}$ .

5.1step 3.1step 4.1algebra∎

Using $t \leq 5 L / Q$ gives $ϵ^{4 b d t} = 2^{- 4 b d t L} \geq 2^{- 20 b d L^{2} / Q} = δ$ . Combined with the strict inequality in the preceding step, this proves $δ < x^{d} η^{t}$ and all the asserted bounds.

Source notes

Proof/convention locator: Bucic, Nguyen, Scott and Seymour, Induced subgraph density I, 5.2, setup preceding claim (1).

Depends on

Used by

Dependency tree · two levels

30 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

Bucic, Nguyen, Scott and Seymour, Induced subgraph density I (standard reference, not scraped)