Parity splitting: a crosscut adds the two crossing counts #
Lemma 2.7. A crosscut P of a simple closed polygon C cuts it into two arcs A₁, A₂, and
the two closed curves Jᵢ = Aᵢ ∪ P satisfy π_C = π_{J₁} + π_{J₂} off C ∪ P. The blueprint
calls this identity "the whole of the polygonal crosscut theorem": Lemma 2.6 exhibits two cells
of Ω ∖ P, and this is what says there are no others.
Where the split is made, and why #
The crossing count of Schoenflies/Parity.lean is a function of a List Piece, not of a set,
and not of a ClosedPolygon. Two edge lists with the same carrier can have different parity —
a list that traverses one segment twice is the obvious example — so the identity cannot be
stated for the sets Aᵢ ∪ P. It is stated, and proved, for edge lists:
the edge list of `C` is `A₁ ++ A₂`, that of `Jᵢ` is `Aᵢ ++ K`,
where K is the edge list of the crosscut. Then π_{J₁} + π_{J₂} = π_{A₁} + π_{A₂} + 2 π_K
and the crosscut's contribution cancels mod 2. That is parity_split, and it needs no
geometry at all — no simplicity, no direction, no separation. Everything the blueprint's
picture contributes is in the hypothesis that the lists decompose that way.
Two mismatches between "the edge list of Jᵢ is Aᵢ together with K" and literal list
equality have to be absorbed, because a consumer building Jᵢ as a ClosedPolygon controls
neither:
- the edges come in some cyclic order of that polygon's own choosing, and
- one of the two curves must traverse the crosscut backwards, so its pieces are the reversed pairs.
SameEdges is the equivalence that forgives exactly these two: a permutation of the lists
after each piece has been put in canonical order by Schoenflies.orientPiece. Parity, carrier,
closedness and non-levelness are all invariant under it (SameEdges.parity_eq,
SameEdges.cover_eq, SameEdges.isChainFrom, SameEdges.hgt_ne), so a consumer may hand over
its edge list in whatever order and orientation it happens to have —
sameEdges_of_perm_reverse_swap absorbs both mismatches in one step.
Nothing is assumed about the sets: ClosedPolygon.carrier_eq_of_sameEdges derives
Jᵢ.carrier = Aᵢ ∪ P from the edge lists alone, so the geometric hypothesis a consumer has to
discharge is only ever combinatorial.
The construction #
ClosedPolygon.arcPieces C a k is the edge list of the arc of C that leaves vertex a and
runs forward through k edges — the object the split produces, exported as an object rather
than hidden behind an existential. Its two governing facts are
ClosedPolygon.arcPieces_split_perm:arcPieces C a k ++ arcPieces C (a + k) (m + 3 - k)is a permutation ofC.pieces— the arcs really do partition the edges; andClosedPolygon.isChainFrom_arcPieces: the arc's mod-2boundary is its two end vertices, which is what makesAᵢ ++ Ka closed chain and hence eligible for every parity theorem.
IsChainFrom is the open-path companion of Schoenflies.IsClosedChain, stated by the same
duality; IsChainFrom.isClosedChain_append is the one-line reason that an arc and a crosscut
with the same two ends close up. pathPieces turns a polyline into such a chain, which is how
the crosscut itself is normally presented.
The endpoints of the crosscut are taken to be vertices of C; the blueprint's opening
move, "subdivide C at p and q", is what puts them there, and is parity_subdivide
(Lemma 2.1) applied before any of this. Nothing below re-proves it. A consumer whose crosscut
lands in the interiors of edges rewrites with parity_subdivide first and then applies
parity_split to the subdivided list, whose hypotheses are about lists and not about polygons;
what such a consumer must supply for itself is the decomposition of the subdivided list into
two arcs, which arcPieces does not provide — arcPieces splits C.pieces at vertices.
Blueprint #
SameEdges,IsChainFrom,pathPieces,ClosedPolygon.arcPieces— the definition of the split. "After the subdivision the edge set ofCis the disjoint union of the edge sets ofA₁andA₂, and the edge set ofJᵢis that ofAᵢtogether with that ofP."parity_split,ClosedPolygon.parity_splitting— Lemma 2.7, equation (2.2)π_C = π_{J₁} + π_{J₂}.ClosedPolygon.crosscut_inside_exactly_one,ClosedPolygon.crosscut_outside_agree— the "Consequently" of Lemma 2.7, which is where Theorem 2.3 enters: a point ofInt(C)offPlies inside exactly one ofJ₁, J₂, and a point ofExt(C)offPlies inside both or inside neither.ClosedPolygon.parity_eq_one_iff— the two halves of the last sentence of Theorem 2.3, read as a single criterion.ClosedPolygon.carrier_eq_of_sameEdges,ClosedPolygon.notMem_carrier_of_sameEdges— the bridge back to the sets:JᵢoccupiesAᵢ ∪ P, so "offCand offP" is "offJᵢ".
One lemma here strengthens one on main: mark_swap' drops the non-levelness hypothesis of
Schoenflies.mark_swap, because a level edge is crossed from nowhere and so contributes 0
under either name. Its home is Schoenflies/Parity.lean.
Edge lists up to order and orientation #
Parity, carrier and closedness are all functions of the multiset of unoriented edges. This section says so, so that a consumer may present the edge list of a curve in any order and with either name for each edge.
orientPiece either leaves a piece alone or reverses it; that is all this file uses.
Two edge lists carry the same edges: they agree after reordering, each edge being free
to be named by either of its two ends first. This is the relation under which "the edge list of
Jᵢ is that of Aᵢ together with that of P" is true — a ClosedPolygon built on Aᵢ ∪ P
lists its edges in its own cyclic order, and traverses one of the two pieces backwards.
Equations
- Schoenflies.SameEdges L₁ L₂ = (List.map Schoenflies.orientPiece L₁).Perm (List.map Schoenflies.orientPiece L₂)
Instances For
The shape a consumer arrives with. A ClosedPolygon built on Aᵢ ∪ P lists its edges
in a cyclic order of its own choosing — any permutation — and one of the two must run the
crosscut backwards, which reverses the list and names every piece the other way round. All of
that is forgiven at once.
Every edge of L₁ is an edge of L₂, up to the naming of its two ends.
Chains with two ends #
Schoenflies.IsClosedChain says the mod-2 boundary of an edge list vanishes. An arc and a
crosscut are not closed; each has a boundary, namely its two ends, and closing them up is the
statement that the two boundaries agree. Stated by the same duality as IsClosedChain, so that
the two definitions compose with nothing but List.sum_append.
L is a chain from p to q: its mod-2 boundary is p together with q. Stated by
duality, exactly as Schoenflies.IsClosedChain is.
Equations
- Schoenflies.IsChainFrom L p q = ∀ (f : Schoenflies.Plane → ZMod 2), (List.map (fun (P : Schoenflies.Piece) => f P.1 + f P.2) L).sum = f p + f q
Instances For
A chain whose two ends coincide is a closed chain, and conversely.
Chains compose end to end.
Two chains with the same two ends close up. This is the whole reason Aᵢ ∪ P is a
closed curve as far as the crossing count is concerned.
The edges of a polyline #
How a crosscut is normally presented: a list of points. pathPieces reads off its edges, and
isChainFrom_pathPieces says its boundary is the two ends of the list.
A polyline is a chain from its first point to its last.
The two arcs of a polygon #
arcPieces C a k is the edge list of the arc of C that leaves vertex a and runs forward
through k edges. Its two ends are vertices a and a + k, and for k ≤ m + 3 the two arcs
arcPieces C a k and arcPieces C (a + k) (m + 3 - k) between them use each edge of C
exactly once.
The edge list of the arc of C that leaves vertex a and runs forward through k edges.
For k ≤ m + 3 this is one of the two arcs a crosscut with endpoints C.vertex a and
C.vertex (a + k) cuts C into; the other is arcPieces C (a + k) (m + 3 - k).
Equations
Instances For
Running through all m + 3 edges from vertex 0 is the whole edge list.
An arc is a chain from its first vertex to its last. The telescoping sum of the
blueprint's "counting edge by edge", read off Schoenflies.sum_range_boundary.
The two arcs from a vertex use every edge exactly once. Cutting the cycle at a is a
rotation, and a rotation is a permutation: the list is X ++ Y and C.pieces is Y ++ X.
The two curves of the split are closed chains. An arc from C.vertex a to
C.vertex (a + k) and a crosscut with the same two ends close up.
A curve of the split occupies its arc together with the crosscut. Only the edge list of
J is assumed related to the split; its carrier then is what the blueprint calls Aᵢ ∪ P.
Hence a point off C and off the crosscut is off J: the blueprint's "a point of
Int(C) off P" needs nothing else.
The identity #
Everything above was the definition. The identity itself is one line of ZMod 2 arithmetic:
the crosscut is counted once in each of π_{J₁} and π_{J₂}, so its contribution cancels.
Parity splitting (Lemma 2.7), in edge-list form and with no geometry whatever. If the
edge list of C is the two arcs A₁, A₂ and the edge list of Jᵢ is Aᵢ together with the
crosscut's list K — in each case up to reordering and up to reversing individual edges — then
π_{J₁} + π_{J₂} = π_C at every point of the plane.
The hypotheses carry all of the blueprint's picture; the proof is that K is counted twice.
Parity splitting (Lemma 2.7) for a simple closed polygon cut at two of its vertices.
K is the edge list of the crosscut, L₁ and L₂ the edge lists of the two curves
Jᵢ = Aᵢ ∪ P; each is required only to carry the right edges, in any order and with either
name for each edge.
No hypothesis on K is needed: whatever it is, it is counted once on each side and cancels.
What the identity says about the regions #
Theorem 2.3 fixes the two values of π for each of the three curves — 1 on the bounded
region, 0 on the unbounded one — and the identity then reads off the blueprint's
"consequently".
The crossing count decides the region (Theorem 2.3, last sentence, as a criterion).
Off the polygon, π_C = 1 exactly on the bounded region.
A point inside C and off the crosscut is inside exactly one of J₁, J₂ — the first
half of the "Consequently" of Lemma 2.7. The left side of the splitting identity is 1, so
exactly one of the two right-hand terms is.
"Off the crosscut" is x ∉ cover K; that x is off J₁ and off J₂ as well is not assumed
but derived, by notMem_carrier_of_sameEdges.
A point outside C and off the crosscut is inside both of J₁, J₂ or inside neither —
the second half of the "Consequently" of Lemma 2.7. The left side of the splitting identity is
0, so the two right-hand terms agree.