LemmaStatement: 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.

Planar Laplace multipole and local translation identities

Statement

For the P2M, M2M, M2L, L2L and L2P formulas of Fixed-order planar Laplace fast multipole procedure, P2M gives the source moments about a leaf center, M2M gives exactly the same moments about a parent center, and the finite M2L coefficients are the degree- $0$ through degree- $p$ Taylor coefficients of the order- $p$ source multipole polynomial about the target center. L2L is exact re-centering of the resulting degree- $p$ polynomial, and L2P evaluates it exactly. For every $n \geq 0$ define $M_{n} (C) = \sum_{j \in I_{C}} q_{j} (z_{j} - c_{C})^{n}$ ; the algorithm stores only $n \leq p$ . For a far pair $(C, D)$ and $z$ in the target cell, the fixed-branch source potential also has the absolutely convergent outer expansion $M_{0} (C) L_{C D} (z - c_{C}) - \sum_{n = 1}^{\infty} M_{n} (C) / (n (z - c_{C})^{n})$ .

Facts & Assumptions

Given: A far source/target cell pair, its fixed analytic logarithm, finite source moments, and the order- $p$ translation formulas.

[F1]

Finite planar quadtree and separated interaction lists: for a far pair with centers $c_{C}, c_{D}$ , radii $a_{C}, a_{D}$ , and $R = ∣ c_{D} - c_{C} ∣$ , one has $a_{C} + a_{D} < R$ and one analytic logarithm is fixed on a disk containing all pair differences.

[F2]

Fixed-order planar Laplace fast multipole procedure: P2M stores $M_{n} = \sum_{j} q_{j} (z_{j} - c_{C})^{n}$ ; M2M uses the binomial shift over nonempty children (empty children have zero moments); M2L uses the displayed finite local coefficients; L2L uses the binomial re-centering formula over nonempty-cell edges; L2P evaluates the local polynomial and its derivative.

Proof

1.1givenF1algebra

For $∣ w ∣ < 1$ , the geometric series $1 / (1 + t) = \sum_{r = 0}^{\infty} (- t)^{r}$ converges uniformly on each closed disk $∣ t ∣ \leq r_{0} < 1$ . Integrating it from $0$ to $w$ gives the analytic branch identity $\log (1 + w) = \sum_{m = 1}^{\infty} (- 1)^{m + 1} w^{m} / m$ .

1.2F2algebra

For a nonempty child cell $E$ of $C$ , write $z_{j} - c_{C} = (z_{j} - c_{E}) + (c_{E} - c_{C})$ and apply the finite binomial theorem to its $n$ th power. Summing over the sources in each nonempty child and then over the nonempty children gives $M_{n} (C) = \sum_{E} \sum_{r = 0}^{n} (\binom{n}{r}) (c_{E} - c_{C})^{n - r} M_{r} (E)$ for every $n \leq p$ ; empty children contribute zero. This is exactly the M2M pass.

1.3F2algebra

If a parent local polynomial is $\sum_{k = 0}^{p} L_{k} (z - c_{D})^{k}$ , put $z - c_{D} = (z - c_{E}) + (c_{E} - c_{D})$ and expand each power. The coefficient of $(z - c_{E})^{j}$ is $\sum_{k = j}^{p} (\binom{k}{j}) L_{k} (c_{E} - c_{D})^{k - j}$ ; hence L2L exactly re-centers the polynomial without adding truncation error.

2.1F1step 1.1algebra

For a far pair $(C, D)$ , put $z - c_{C} = D_{0} + x$ with $D_{0} = c_{D} - c_{C}$ and $∣ x ∣ \leq a_{D}$ . Then $∣ D_{0} + x ∣ \geq R - a_{D} > a_{C}$ . Substituting $w = - (z_{j} - c_{C}) / (z - c_{C})$ into the branch-normalized series from step 1.1 and summing the finite source set gives $M_{0} (C) L_{C D} (z - c_{C}) - \sum_{n \geq 1} M_{n} (C) / [n (z - c_{C})^{n}]$ . The branch is $L_{C D}$ because both $z - c_{C}$ and $z - z_{j}$ lie in its disk and the difference of their logarithms is the series that vanishes at $z_{j} = c_{C}$ . The convergence is absolute because $∣ z_{j} - c_{C} ∣ / ∣ z - c_{C} ∣ < 1$ .

2.2F1step 1.1algebra

For a far pair put $D = c_{D} - c_{C}$ , $x = z - c_{D}$ and $y = z_{j} - c_{C}$ . By [F1], $∣ x - y ∣ \leq ∣ x ∣ + ∣ y ∣ < R = ∣ D ∣$ . The branch-normalized logarithm therefore has expansion $L_{C D} (D + x - y) = L_{C D} (D) + \sum_{m \geq 1} (- 1)^{m + 1} (x - y)^{m} / (m D^{m})$ .

3.1F2step 2.2algebra

Expand $(x - y)^{m}$ by the binomial theorem and set $m = n + k$ . For $n \geq 1, k \geq 0$ , the coefficient of $x^{k} y^{n}$ is $(- 1)^{k + 1} (\binom{n + k - 1}{k}) / (n D^{n + k})$ , since $(\binom{n + k}{k}) / (n + k) = (\binom{n + k - 1}{k}) / n$ . The terms with $n = 0$ are $M_{0} L_{C D} (D)$ for $k = 0$ and $(- 1)^{k + 1} M_{0} / (k D^{k})$ for $k \geq 1$ ; the terms with $k = 0, n \geq 1$ are $- M_{n} / (n D^{n})$ . Summing $y^{n}$ over sources replaces it by $M_{n}$ , and retaining $0 \leq n, k \leq p$ yields precisely the M2L formulas in [F2].

4.1F2step 1.3algebra∎

Substitution of a target point into the re-centered degree- $p$ polynomial is exactly L2P, and termwise differentiation gives its derivative formula. These are finite polynomial identities and require no additional convergence assumption.

Depends on

Used by

Global planar FMM potential and derivative error Theorem

Dependency tree · one level

2 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)
Michael O’Neil, Integral Equations and Fast Algorithms, complete course lecture notes (2017) (standard reference, not scraped)
James Demmel, Fast Hierarchical Methods for the N-body Problem, Part 2, CS267 Lecture 25 (1996) (standard reference, not scraped)