The Setting
Choiceless polynomial time with counting (CPT) computes with hereditarily finite objects over the atoms of its input structure, and its lower bounds are arguments about the supports of these objects under a group acting on the atoms.
The group of this item is built on the cubic grid of side , with chains over : it is a central extension , by the flows on the edges of the grid, of the group of labellings that put a point of the plane on each face. Next to and its commutators, the item defines supports of objects under any group acting on atoms, with their hereditary form.
The Grid
A vertex of the grid of side is a triple of integers in , and the vertex set has elements.✦ An edge of the grid is a unit segment between two vertices parallel to a coordinate axis: runs from to , while and run from to and to .✦ The edge set is the disjoint union of these three families.✦ The tail of an edge is its lower end✦, and its head is its upper end.✦
A face of the grid is a unit square between vertices parallel to a coordinate plane, given by its lowest corner ; its opposite corner is in the plane, in the plane and in the plane.✦ The face set is the disjoint union of the three families.✦
An edge chain is a function , with values in the field of integers modulo , and the edge chains form the vector space ; the vertex chains form in the same way. The boundary map of the grid is the linear map from to given by (1)✦ where is the indicator vector of the vertex , and that of an edge .
The face cycle of a face is the edge chain that goes once around the boundary of .✦ For the face in the plane with lowest corner , (2)✦ and the faces in the and planes are traversed in the same way, with the axes replaced by and by .
Face Labellings and the Group
The plane is the vector space of pairs of elements of , added and scaled coordinatewise.✦ The symplectic form on is (3)✦
Let be a finite set, such as the faces of the grid, a vector space over whose elements are called flows, and a map, with . A face labelling is a map , with value at , and the face labellings form the group under pointwise addition. The group attached to is a central extension of by whose elements are the pairs of a face labelling and a flow .✦
Hereditarily Finite Objects
The set of hereditarily finite objects over a set of atoms is the least set that contains the atoms and every finite set of its own elements.✦ The transitive closure of an object is the set of objects with for some .
A group acting on acts on through the atoms. For an object of , the stabilizer of in is the subgroup of of the elements that fix ; for a tuple of atoms, the pointwise stabilizer of is the subgroup of of the elements that fix each .
The Claim
Definition 1. The flow space of the grid of side is the space of edge chains with zero boundary: (4)✦ Sending each face to its face cycle gives the flow cycle map of the grid, (5)✦ The box group of the grid is the group attached to the flow cycle map: (6)✦ In the box group, as in the group attached to any map from a finite set to a vector space over , the central element of a flow is .✦ It commutes with every element of , (7)✦ and the commutator of two elements and is a central element: (8)✦ The central group of the grid is the flow space as a group, with the sum of flows as its product, (9)✦ and the central embedding is the group homomorphism from the central group to the box group (10)✦ Let a group act on a set of atoms. A tuple of atoms supports an object when its pointwise stabilizer fixes : (11)✦ For , an object is -supported when some tuple of atoms, repetitions allowed, supports it, (12)✦ and hereditarily -supported when and every object of its transitive closure are -supported: (13)✦
In the paper, the result reads: the group , with , and product for a map , has as commutator of and the element , the paper’s being , and a tuple of atoms is a -support of an object when every fixing fixes , the action on hereditarily finite objects being applied recursively to their elements.
For , the supports of (11) are the -supports.
What Is Checked
The definitions are stated over the grid of side with its vertices, edges and faces, its boundary map and its face cycles over ; over the plane with the form and the group attached to a map from a finite set to a vector space over ; and, for supports, over a group acting on a set of atoms and the hereditarily finite objects over them.
The library proves for every face of the grid.✦