The Setting
Choiceless polynomial time computes with hereditarily finite objects over the atoms of its input, and a group acting on the atoms moves each such object along its orbit. The inputs here are the grid structures , one for each charge on the vertices of the cubic grid of side with values in , and the group acting is the box group , which contains the group of flows on the grid as a central subgroup. The question is how the size of an object’s orbit under bounds its supports under : if the orbit has at most elements, for a positive integer and a real number , how few atoms can be chosen so that every flow fixing them fixes the object?
The Grid
Fix and let . Scalars lie in the field of integers modulo .✦ A grid vertex is a triple of integers in , and the vertex set has elements.✦
A grid edge is a unit segment between grid vertices parallel to a coordinate axis, given by its lower endpoint: the edge along runs from to , the edge along to and the edge along to .✦ In each family the coordinate along the edge ranges over and the other two over , and the edge set is the disjoint union of the three families.✦ The tail of an edge is the endpoint it starts from✦ and its head the endpoint it ends at.✦ A vertex is incident to when it is the head or the tail of ✦, and the edges at are the edges incident to it.✦ The orientation sign is if , if and otherwise.✦
A grid face is a unit square parallel to a coordinate plane, given by its lowest corner : a face in the plane has the opposite corner , one in the plane and one in the plane , the two coordinates that move ranging over and the third over .✦ The face set is the disjoint union of the three families.✦ The face cycle of a face goes once around its boundary: it is on the two sides crossed in their own direction, on the other two and elsewhere.✦ For the face in the plane with lowest corner , (1)✦ where is the indicator vector of ; the faces in the other two planes are traversed in the same way. The faces on an edge are the faces with , the squares having as a side, and they form the set .✦
The boundary map is the linear map (2)✦ with the indicator vector of a vertex . The flow space is the subspace of flows, the edge labellings whose boundary vanishes at every vertex.✦ Read as flows, the face cycles give the map , .✦
For labellings of a finite set by , the pairing is , linear in ✦, and the nonzero set of is .✦ The curl of an edge labelling is the labelling of the faces by (3)✦
The Support Group
Let be any finite set of faces, any vector space of flows over and any map. The plane carries the symplectic form (4) and is the space of face labellings. The support group is the central extension of by attached to : its elements are the pairs of a face labelling and a flow ✦, and the central element of is .✦
For a weight , the diagonal form is the bilinear form on given by (5)✦ and a subspace of is isotropic for when for all . For a subgroup of , the projection is the subspace of face labellings with for some ✦, and the central part is the subspace of flows with .✦
The Box Group and the Atoms
The box group of the grid is the support group of the grid faces , the flow space and the face cycles .✦ The central flow group of is the additive group of , and the central embedding of into is the map , . For a subgroup of , the face codimension and the flow codimension are (6)
The local group of an edge is the support group of the faces on , the flows and the local cycle , a nonzero scalar; its elements are the pairs of a labelling of by points of and a scalar flow .✦ A local state at a vertex assigns to each edge at an element of .✦ A local state at is compatible when for any two edges at and any face on both; the divergence of a local state at is the net flow into , (7)
For a charge , a configuration at is a compatible local state at with divergence .✦ The atoms of the grid structure are of two disjoint sorts: the edge atoms, the pairs of an edge and an element , and the configuration atoms, the pairs of a vertex and a configuration at .✦ The groups and act on the atoms of .
Supports
The hereditarily finite objects over a set of atoms are the finite sets whose elements are atoms of or again such sets; they form the set .✦ Let a group act on , and so on . A tuple of atoms is a -support of when every with for all satisfies , and is -supported for the action of when some tuple of atoms is a -support of it.
The Claim
Theorem 1. Let be a charge, a positive integer and a real number.
Let act on a set and let have an -orbit of at most elements. Then there is a set of edges with (8)✦ If and has an -orbit of at most elements, then (9)✦ Let act on a set , let be a set of edges and let satisfy for every flow vanishing on . Then there is a tuple of atoms of with (10)✦
Every subgroup of has a set of edges with (11)✦ Let be a subgroup of and a linear form vanishing on . There is an edge labelling with (12)✦ and every with for all satisfies (13)✦
For any finite set , vector space and map , let be a subgroup of and a linear form vanishing on . Then is isotropic for : (14)✦ For a weight , every subspace of isotropic for satisfies (15)✦ If is finite-dimensional, every subgroup of has index (16)✦
In the paper, the result reads: for , a real and whose -orbit has at most elements, has a -support of at most edge atoms, possibly empty.
What Is Checked
The claim is stated over the support group , with the projection and the central part of its subgroups and the forms and ; over the grid of side , with its edges, faces, face cycles, boundary map, flows and curl; over the box group , the central embedding of and the codimensions of subgroups; and over the atoms of and the supports of hereditarily finite objects built on them.
The library proves that every face cycle is a flow, ✦, and that the central embedding is a homomorphism, . It proves too that the projection and the central part of a subgroup of contain zero and are closed under addition and negation.