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

Naive all-pairs sphere-contact search has quadratic work

Statement

For $P \geq 2$ spheres, the naive search that evaluates every unordered pair guard exactly once per smooth segment performs $P (P - 1) / 2$ pair-guard evaluations. Thus it uses $O (P^{2})$ pair checks; this count excludes the cost of each certified event solve, dense reintegration, and restart-error certificate. With zero or one sphere the pair list is empty, but the event-driven algorithm is defined for $P \geq 2$ .

Facts & Assumptions

Given: The pair-enumeration loop of Event-driven integration for isolated frictionless spherical impacts and the particle count $P \in N$ .

[F1]

Event-driven integration for isolated frictionless spherical impacts: on each smooth segment, the naive search inspects each unordered pair $i < j$ once; event-certificate solves and reintegration are charged separately.

[F2]

Laws of finite sums and finite products: finite sums split and telescope, and The principle of mathematical induction supplies induction on $P$ .

Proof

1.1F1given

For each lower index $i = 1, \dots, P - 1$ , the loop tests exactly $P - i$ higher indices. Every unordered pair has a unique smaller index, so these sets of tests are disjoint and include every pair once. The count is therefore $\sum_{i = 1}^{P - 1} (P - i)$ .

2.1F2step 1.1givenalgebrainduction∎

Reindexing by $r = P - i$ gives $\sum_{r = 1}^{P - 1} r$ . This sum is $P (P - 1) / 2$ : it is $0$ for $P = 0$ and $P = 1$ , and increasing $P$ to $P + 1$ adds exactly $P$ , which changes $P (P - 1) / 2$ to $P (P + 1) / 2$ ; induction gives the formula. For every $P \geq 2$ , it is at most $P^{2} / 2$ , proving the stated $O (P^{2})$ bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

25 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

David E. Stewart, Dynamics with Inequalities: Impacts and Hard Constraints (standard reference, not scraped)
Dimitri P. Bertsekas, 6.253 Convex Analysis and Optimization, Complete Lecture Notes (standard reference, not scraped)