claimroutineinferred_dep

Three cost terms are balanced

Claim·§4.7 Choosing the parameters·inside lemExplicit parameter choice satisfies layout hypotheses

Statement (paper)

For all sufficiently large nn, RQ=Oβ(ν/λ)\frac RQ=O_\beta(\nu/\sqrt\lambda), log⁡(2Q/R)=O(ν)\log(2Q/R)=O(\nu) and τlog⁡(2D+1)=O(1/r)\tau\log(2D+1)=O(1/r); together with 1/r=O(ν2/λ)1/r=O(\nu^2/\sqrt\lambda) this gives RQlog⁡2QR+τlog⁡(2D+1)+1r=Oβ ⁣(ν2λ)\frac RQ\log\frac{2Q}{R}+\tau\log(2D+1)+\frac1r=O_\beta\!\left(\frac{\nu^2}{\sqrt\lambda}\right), which is .

In plain English

For large nn, R/Q=Oβ(ν/λ)R/Q=O_\beta(\nu/\sqrt\lambda), log⁡(2Q/R)=O(ν)\log(2Q/R)=O(\nu) and τlog⁡(2D+1)=O(1/r)\tau\log(2D+1)=O(1/r). Together with 1/r=O(ν2/λ)1/r=O(\nu^2/\sqrt\lambda), the sum RQlog⁡2QR+τlog⁡(2D+1)+1r\frac RQ\log\frac{2Q}{R}+\tau\log(2D+1)+\frac1r is Oβ(ν2/λ)O_\beta(\nu^2/\sqrt\lambda).

Why it's here

This claim finishes the proof of the cost bound . It plugs the orders r=Θ(λ/ν2)r=\Theta(\sqrt\lambda/\nu^2), Q=Θ(λ/ν)Q=\Theta(\lambda/\nu), R=Θβ(λ)R=\Theta_\beta(\sqrt\lambda) from the earlier claim into each term. This shows every term is at most of order ν2/λ\nu^2/\sqrt\lambda, and the first term is the product of an O(ν/λ)O(\nu/\sqrt\lambda) factor and an O(ν)O(\nu) logarithm.
Classified routine:
Direct asymptotic calculation substituting the parameter orders r=Θ(λ/ν2)r=\Theta(\sqrt\lambda/\nu^2), Q=Θ(λ/ν)Q=\Theta(\lambda/\nu), R=Θβ(λ)R=\Theta_\beta(\sqrt\lambda) from the earlier claim into each of the three cost terms.

Uses

claimParameter orders and balance inequalities

Used by

Nothing in the paper

Sources

PaperOpen
Section
§4.7 Choosing the parameters
Page
—
Label
—
Line
main_full_version.tex:2819
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Three cost terms are balanced" rests on claim-lem-incidence-parameters-1