LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

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.

Hyperplane arrangement upper count and general-position count

Statement

For integers $m \geq 0$ and $d \geq 1$ , the complement of any $m$ affine hyperplanes in $R^{d}$ has at most $\sum_{j = 0}^{d} (\binom{m}{j})$ connected components, with $(\binom{m}{j}) = 0$ for $j > m$ . If the hyperplanes are in general position, meaning every $q \leq d$ of them meet in codimension $q$ and no $d + 1$ have a common point, the number of components is exactly this sum; such arrangements exist for every $m, d$ . On a zero-dimensional affine image there is at most one full-dimensional activation cell.

Statement references

Serra et al., Lemma 5 and proof: hyperplane arrangement bound

Telgarsky, Chapter 5: depth and approximation context

Facts & Assumptions

Given: Integers $m \geq 0$ , $d \geq 0$ , and an arrangement of $m$ affine hyperplanes in $R^{d}$ , where for $d = 0$ the arrangement is interpreted as sign conditions on a single point.

Proof

1.1givenconstruct

Let $R (m, d)$ be the largest possible number of complementary regions. With no hyperplanes or in dimension zero, $R (0, d) = R (m, 0) = 1$ . Adding the last hyperplane $H$ splits only old regions that meet $H$ ; each old region is convex, so its intersection with $H$ contributes at most one region of the arrangement induced on $H ≅ R^{d - 1}$ . Hence $R (m, d) \leq R (m - 1, d) + R (m - 1, d - 1)$ .

2.1step 1.1algebraconstruct∎

Induction on $m + d$ and Pascal's identity give $R (m, d) \leq \sum_{j = 0}^{d} (\binom{m - 1}{j}) + \sum_{j = 0}^{d - 1} (\binom{m - 1}{j}) = \sum_{j = 0}^{d} (\binom{m}{j})$ . If the arrangement is in general position, its restriction to $H$ is also in general position and has $m - 1$ hyperplanes in dimension $d - 1$ ; every one of its regions lies in one old region and cuts that region into two, so the recurrence is equality. Such arrangements exist: choose distinct $t_{1}, \dots, t_{m}$ and use $H_{i} : \sum_{k = 1}^{d} t_{i}^{k - 1} x_{k} = t_{i}^{d}$ . Any $q \leq d$ normals are independent by the Vandermonde determinant, while no $d + 1$ equations have a common solution because their augmented Vandermonde matrix is invertible. The same induction gives the claimed exact sum.

Used by

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

Serra, Tjandraatmadja, and Ramalingam, Bounding and Counting Linear Regions of Deep Neural Networks, Lemma 5 (standard reference, not scraped)
Matus Telgarsky, Deep learning theory lecture notes, Chapter 5 (standard reference, not scraped)