TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

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.

Global planar FMM potential and derivative error

Statement

Assume the collision-free exact-arithmetic branch of Fixed-order planar Laplace fast multipole procedure with order $p \geq 1$ . For each target $i$ in leaf $D_{i}$ , let $F_{i} = {(C, D) \in F : i \in I_{D}}$ be its far cell interactions. For $(C, D) \in F_{i}$ put $R_{C D} = ∣ c_{D} - c_{C} ∣$ , $ρ_{C D} = (a_{C} + a_{D}) / R_{C D} < 1$ , and $Q_{C} = \sum_{j \in I_{C}} ∣ q_{j} ∣$ . If $u_{i}$ is the exact fixed-branch logarithmic potential and ${\tilde{u}}_{i}$ the algorithm output, then $∣ u_{i} - {\tilde{u}}_{i} ∣ \leq \sum_{(C, D) \in F_{i}} \frac{Q_{C} ρ_{C D}^{p + 1}}{(p + 1) (1 - ρ_{C D})} .$ If $g_{i} = \sum_{j \neq i} q_{j} / (z_{i} - z_{j})$ and ${\tilde{g}}_{i}$ is the algorithm's complex derivative output, then $∣ g_{i} - {\tilde{g}}_{i} ∣ \leq \sum_{(C, D) \in F_{i}} \frac{Q_{C}}{R_{C D}} \frac{ρ_{C D}^{p}}{1 - ρ_{C D}} .$ Near interactions are exact. The second estimate is branch-independent; no floating-point rounding error is included.

Facts & Assumptions

Given: Collision-free finite sources, a finite quadtree, order $p \geq 1$ , and the exact-arithmetic local expansions in Fixed-order planar Laplace fast multipole procedure.

[F1]

Finite planar quadtree and separated interaction lists: each far pair has $R_{C D} > a_{C} + a_{D}$ and one analytic logarithm on a disk containing every source-target difference in that pair.

[F2]

Fixed-order planar Laplace fast multipole procedure: P2M/M2M moments are computed through order $p$ , M2L retains source moment indices $n \leq p$ and local degrees $k \leq p$ , L2L re-centers finite polynomials exactly, and direct near pairs are evaluated exactly.

[F3]

Planar Laplace multipole and local translation identities: these finite formulas are the corresponding source and target truncations of the absolutely convergent logarithmic series.

[F4]

Planar FMM lists partition all ordered off-diagonal particle pairs: the far cell products and exact near pairs partition all ordered off-diagonal source-target pairs.

Proof

1.1givenF1F2F3algebra

Fix a far interaction $(C, D)$ contributing to target $i$ , and write $D_{0} = c_{D} - c_{C}$ , $x = z_{i} - c_{D}$ , $y_{j} = z_{j} - c_{C}$ , and $R = ∣ D_{0} ∣$ . Then $∣ x ∣ \leq a_{D}$ , $∣ y_{j} ∣ \leq a_{C}$ , and $ρ = (a_{C} + a_{D}) / R < 1$ by [F1]. The series in [F3] for each source is the double binomial expansion of $L_{C D} (D_{0} + x - y_{j})$ . The algorithm retains all terms with source index $n \leq p$ and target degree $k \leq p$ ; every omitted term has total degree $m = n + k \geq p + 1$ .

2.1givenstep 1.1algebra

For total degree $m$ , the sum of absolute values of the potential terms for one source is at most $∣ q_{j} ∣ \sum_{k = 0}^{m} (\binom{m}{k}) ∣ x ∣^{k} ∣ y_{j} ∣^{m - k} / (m R^{m}) = ∣ q_{j} ∣ (∣ x ∣ + ∣ y_{j} ∣)^{m} / (m R^{m}) \leq ∣ q_{j} ∣ ρ^{m} / m$ . Summing sources and omitted degrees gives an interaction error at most $Q_{C} \sum_{m = p + 1}^{\infty} ρ^{m} / m \leq Q_{C} ρ^{p + 1} / ((p + 1) (1 - ρ))$ , since $1 / m \leq 1 / (p + 1)$ for $m \geq p + 1$ .

2.2givenF1step 1.1algebra

For each total degree $m \geq 1$ , the sum of absolute differentiated monomials for one source, before multiplying by $q_{j}$ , is $\sum_{k = 1}^{m} \frac{k}{m} (\binom{m}{k}) \frac{∣ x ∣^{k - 1} ∣ y_{j} ∣^{m - k}}{R^{m}} = \frac{(∣ x ∣ + ∣ y_{j} ∣)^{m - 1}}{R^{m}} \leq \frac{ρ^{m - 1}}{R} .$ Here a zeroth power is $1$ , including at zero. Every subset of these monomials, in particular the omitted subset from the rectangular truncation $n, k \leq p$ , has absolute sum bounded by the same nonnegative full sum. The series and its differentiated monomials converge absolutely and uniformly on $∣ x ∣ \leq a_{D}$ because $ρ < 1$ , so termwise differentiation is valid. By step 1.1, omitted terms have $m \geq p + 1$ ; multiplying by $∣ q_{j} ∣$ and summing sources and degrees bounds the interaction derivative error by $Q_{C} R^{- 1} \sum_{m = p + 1}^{\infty} ρ^{m - 1} = Q_{C} R^{- 1} ρ^{p} / (1 - ρ)$ . The derivative of any additive branch constant is zero.

3.1givenF2F3F4step 2.1step 2.2algebra∎

By [F4], each off-diagonal particle pair is either one exact direct near interaction or belongs to exactly one far cell product. M2M and L2L introduce no additional truncation error by [F2]–[F3], and L2P evaluates the stored polynomial exactly. Therefore the total potential and derivative errors for target $i$ are bounded by the sums of the finite per-interaction bounds from steps 2.1 and 2.2; all near terms contribute zero error.

Depends on

Used by

Dependency tree · one level

4 results within one dependency step 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

Leslie Greengard and Vladimir Rokhlin, A Fast Algorithm for Particle Simulations, Journal of Computational Physics 73 (1987), 325–348 (standard reference, not scraped)
James Demmel, Fast Hierarchical Methods for the N-body Problem, Part 2, CS267 Lecture 25 (1996) (standard reference, not scraped)