TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-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.

Explicit work and error rate for dyadic Simpson Smolyak cubature

Statement

Use the dyadic composite-Simpson hierarchy of Nested one-dimensional quadrature levels and differences. Let $d \geq 1$ , $n \geq 2 d$ , and let $f : [0, 1]^{d} \to R$ satisfy the continuous mixed fourth-derivative hypotheses and bounds $M_{S}$ of Mixed-derivative bounds for dyadic Simpson details. Define the isotropic index set $Λ_{n} : = {ℓ \in N_{0}^{d} : ∣ ℓ ∣_{1} \leq n},$ and let $W_{n, d} : = ∣ N_{Λ_{n}} ∣$ be the distinct-node work count of Smolyak cubature on a finite downward-closed index set and Deterministic node merging for Smolyak cubature. For a dyadic node $x$ , let $t (x) = 0$ for $x = 0, 1, 1 / 2$ ; if $x = p / 2^{r + 1}$ is interior and reduced with odd numerator $p$ , let $t (x) = r \geq 1$ . Put $a_{0} : = 3, a_{r} : = 2^{r} (r \geq 1),$ $∥ f ∥_{m i x, d} : = \sum_{\emptyset \neq S \subseteq {1, \dots, d}} {(\frac{17}{2880})}^{∣ S ∣} M_{S}, T_{d} : = \sup_{N \geq 1} \sum_{r = 1}^{N} r^{d - 1} 16^{- r},$ $D_{d} : = 2 \cdot 3^{d} d^{d - 1}, C_{d} : = D_{d}^{4} T_{d} {(\frac{3}{\log 2})}^{5 (d - 1)},$ where $\log$ is the natural logarithm of The natural logarithm as the inverse of the exponential function. Then $T_{d} < \infty$ , and the actual node-union count and error satisfy $W_{n, d} = \sum_{\begin{array}{c} t \in N_{0}^{d} \\ ∣ t ∣_{1} \leq n \end{array}} \prod_{j = 1}^{d} a_{t_{j}}, 2^{n} (\binom{n - 1}{d - 1}) \leq W_{n, d} \leq D_{d} 2^{n} (n + 1)^{d - 1},$ $∣ I_{d} (f) - Q_{Λ_{n}} (f) ∣ \leq T_{d} ∥ f ∥_{m i x, d} 16^{- n} (n + 1)^{d - 1} \leq C_{d} ∥ f ∥_{m i x, d} W_{n, d}^{- 4} (\log (2 + W_{n, d}))^{5 (d - 1)} .$ All constants and the mixed-derivative quantity display their dimension dependence; no weighted-anisotropic tractability claim is made.

Facts & Assumptions

Given: $d \geq 1$ , $n \geq 2 d$ , and $f$ with the continuous mixed derivatives and finite bounds in Mixed-derivative bounds for dyadic Simpson details.

[F1]

Smolyak cubature on a finite downward-closed index set: $Q_{Λ_{n}}$ is the finite sum of tensor details, and $N_{Λ_{n}}$ is the union of its tensor-level node sets.

[F2]

Deterministic node merging for Smolyak cubature: each exact distinct node in this union is evaluated once, including nodes with zero combined weight.

[F3]

Mixed-derivative bounds for dyadic Simpson details: $∣ δ_{ℓ} (f) ∣ \leq M_{S (ℓ)} (17 / 2880)^{∣ S (ℓ) ∣} 16^{- \sum_{j \in S (ℓ)} ℓ_{j}}$ ; its proof bounds every finite absolute-detail subsum.

[F4]

Convergence of dyadic tensor composite-Simpson rules gives tensor-rule convergence for this dyadic hierarchy; Absolute detail reconstruction and omitted-tail error bound then bounds the error by omitted absolute details when the finite-subsum bounds in [F3] give absolute summability.

[F5]

For $m \geq 1$ the number of weak compositions of $n$ into $m$ parts is $(\binom{n + m - 1}{m - 1})$ , and the number of compositions is $(\binom{n - 1}{m - 1})$ for $n \geq 1$ : weak compositions of $m$ into $d$ nonnegative coordinates are counted by $(\binom{m + d - 1}{d - 1})$ .

[F6]

Compositions of $n$ into $k$ positive parts are counted by $(\binom{n - 1}{k - 1})$ : compositions of $m$ into $k$ positive parts are counted by $(\binom{m - 1}{k - 1})$ for $m, k \geq 1$ .

[F7]

For $∣ r ∣ < 1$ , $\sum_{k \geq 0} r^{k} = 1 / (1 - r)$ , and for $∣ r ∣ \geq 1$ the series diverges: a geometric series with ratio of absolute value less than one has bounded partial sums.

[F8]

The natural logarithm as the inverse of the exponential function and Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: $\log$ is strictly increasing on positive reals, $\log 1 = 0$ , $\log (x y) = \log x + \log y$ , and repeated use gives $\log (2^{n}) = n \log 2$ ; in particular $\log 2 > 0$ .

[F9]

Finite sums and finite products, by recursion and Laws of finite sums and finite products: finite sums split over disjoint finite index sets, are monotone in nonnegative summands, and telescope.

[F10]

The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ : $(\binom{m}{k})$ counts the $k$ -element subsets of an $m$ -element set, with the stated boundary values. An ordered $q$ -tuple from an $m$ -element set has $m^{q}$ possibilities: there is one empty tuple for $q = 0$ , and each extension appends one of the $m$ entries, giving the count by induction on $q$ .

[F11]

The binomial theorem in $R$ : $(x + y)^{n} = \sum_{k < n + 1} ι ⁣ (\binom{n}{k}) x^{k} y^{n - k}$ : $\sum_{j = 0}^{d - 1} (\binom{d - 1}{j}) = 2^{d - 1}$ .

[F12]

Dedekind completeness: the least-upper-bound property: every nonempty real set bounded above has a finite supremum.

[F13]

Monotonicity of $x \mapsto x^{n}$ and of $n \mapsto a^{n}$ and Inverses of positives are positive, and reciprocation reverses order: if $r \geq 1$ and $j \geq 1$ , then $r^{j} \geq r > 0$ , so $r^{- j} \leq r^{- 1}$ (with equality when $r^{j} = r$ , and reciprocal order when $r^{j} > r$ ); powers are as in Integer powers $a^{m}$ .

[F14]

Every complete ordered field is Archimedean: for every real $x$ there is a natural $R \geq 1$ with $x < R$ .

[F15]

Integer powers $a^{m}$ : $2^{0} = 1$ and $2^{m + 1} = 2^{m} \cdot 2$ .

[F16]

The multiplicative identity is positive: $1 > 0$ .

Proof

1.1givenF7F11F12F13F14algebra

Set $b_{r} = r^{d - 1} 16^{- r}$ . By [F11] and [F13], for $r \geq 1$ and $j \geq 1$ we have $r^{- j} \leq r^{- 1}$ ; hence $b_{r + 1} / b_{r} = (1 + 1 / r)^{d - 1} / 16 \leq (1 + (2^{d - 1} - 1) / r) / 16$ . Put $C : = 2^{d - 1} - 1 \geq 0$ . If $C = 0$ , take $R = 1$ ; if $C > 0$ , [F14] gives a natural $R \geq 1$ with $2 C < R$ . For every $r \geq R$ , the ratio is at most $(3 / 2) / 16 = 3 / 32 < 1 / 2$ . Induction then bounds the tail by a geometric sequence with ratio $1 / 2$ , so [F7] bounds its partial sums; adding the finite initial segment bounds every partial sum. The partial sums form a nonempty bounded set, so [F12] defines a finite supremum $T_{d}$ .

1.2givenF1F2algebra

A node of $X_{ℓ} = {k / 2^{ℓ + 1} : 0 \leq k \leq 2^{ℓ + 1}}$ belongs to every level at least its minimal level $t (x)$ . The three nodes of minimal level zero are $0, 1 / 2, 1$ . For $r \geq 1$ , a node of minimal level $r$ has reduced form $p / 2^{r + 1}$ with odd $p$ and $0 < p < 2^{r + 1}$ , giving exactly $2^{r}$ choices. A node tuple belongs to $N_{Λ_{n}}$ iff its minimal-level vector $t$ satisfies $∣ t ∣_{1} \leq n$ : that condition itself supplies an admissible index, and any index containing the tuple has each coordinate at least its minimal level. Multiplying the coordinate counts and summing over these vectors proves the exact work formula.

2.1givenF3F4F6F9F10step 1.1algebra

Fix a finite $F \subseteq N_{0}^{d} ∖ Λ_{n}$ and group its indices by the nonempty active-coordinate subset $S$ of size $k$ . If the positive coordinates sum to $m = n + r$ , then $r \geq 1$ ; there are at most $(\binom{m - 1}{k - 1})$ such tuples by [F6]. Since this coefficient counts $(k - 1)$ -element subsets, listing each subset in increasing order injects them into ordered $(k - 1)$ -tuples with entries from a set of $m$ elements; thus $(\binom{m - 1}{k - 1}) \leq m^{k - 1}$ . Since $m = n + r \leq (n + 1) r$ , each fixed- $S$ contribution is at most $M_{S} (17 / 2880)^{k} 16^{- n} (n + 1)^{d - 1} r^{d - 1} 16^{- r}$ . Summing over the finitely many $r$ present in $F$ , enlarging to the partial sum through the largest such $r$ , and then summing over $S$ gives $\sum_{ℓ \in F} ∣ δ_{ℓ} (f) ∣ \leq T_{d} ∥ f ∥_{m i x, d} 16^{- n} (n + 1)^{d - 1}$ . Taking the supremum over finite $F$ bounds the omitted absolute-detail tail; [F4] gives the first error inequality.

2.2givenF5F6F9F10F15F16step 1.2algebra

By the node classification and exact formula in step 1.2, the number of level vectors with $∣ t ∣_{1} = m$ is $(\binom{m + d - 1}{d - 1})$ by [F5], and each has $\prod_{j} a_{t_{j}} \leq 3^{d} 2^{m}$ . Since $(\binom{m + d - 1}{d - 1})$ counts $(d - 1)$ -element subsets, increasing enumeration injects them into ordered $(d - 1)$ -tuples from a set of $m + d$ elements, giving $(\binom{m + d - 1}{d - 1}) \leq (m + d)^{d - 1}$ . The finite geometric sum is $\sum_{m = 0}^{n} 2^{m} = \sum_{m = 0}^{n} (2^{m + 1} - 2^{m}) = 2^{n + 1} - 1 < 2^{n + 1}$ : the term identity follows from [F15], telescoping from [F9], and $1 > 0$ from [F16]. Hence $W_{n, d} \leq 3^{d} (n + d)^{d - 1} \sum_{m = 0}^{n} 2^{m} < 2 \cdot 3^{d} 2^{n} (n + d)^{d - 1} \leq D_{d} 2^{n} (n + 1)^{d - 1}$ , since $n + d \leq d (n + 1)$ . For a lower bound, restrict to vectors with all $t_{j} \geq 1$ and $∣ t ∣_{1} = n$ . There are $(\binom{n - 1}{d - 1})$ by [F6], and each contributes $\prod_{j} a_{t_{j}} = 2^{n}$ .

3.1givenF8step 1.2step 2.1step 2.2algebra∎

From step 2.2, $2^{n} \geq W_{n, d} / (D_{d} (n + 1)^{d - 1})$ , so $16^{- n} \leq D_{d}^{4} W_{n, d}^{- 4} (n + 1)^{4 (d - 1)}$ . The exact work formula in step 1.2 contains the contribution of the vector $t = (n - d + 1, 1, \dots, 1)$ , whose entries are positive because $n \geq 2 d$ ; this contribution is $2^{n}$ , so $W_{n, d} \geq 2^{n}$ . Hence [F8] yields $\log (2 + W_{n, d}) \geq n \log 2$ . As $n \geq 2 d \geq 2$ , $n + 1 \leq (3 / 2) n \leq 3 \log (2 + W_{n, d}) / \log 2$ . Substituting these inequalities into step 2.1's error estimate gives the second bound with the stated $C_{d}$ .

Depends on

Used by

Dependency tree · two levels

100 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

T. Gerstner and M. Griebel, Sparse Grids, Encyclopedia of Quantitative Finance, §§Classical Sparse Grids and Numerical Integration (standard reference, not scraped)
T. Gerstner and M. Griebel, Dimension-Adaptive Tensor-Product Quadrature, §2 (standard reference, not scraped)
N. Zabaras, Sparse Grid Collocation Methods, lecture notes, slides 17–21 (standard reference, not scraped)