The Setting
Choiceless polynomial time with counting does not capture polynomial time, and the structures that show it are built from the cubic grid of side and a charge , a labelling of its vertices by the field . Each charge gives an analysis structure on a set of atoms, and the flows of the grid act on these atoms. The question is when two tuples of atoms that no formula of counting logic with variables tells apart are carried one onto the other by a flow, and how long such tuples may be against .
The Grid
The scalars form the field of integers modulo , in which . The grid of side has the vertex set , with elements.✦ Its edges are the unit segments parallel to the axes, each running from its lower end, the tail, to its upper end, the head: runs from to , with and , while and raise the second and the third coordinate instead. The edge set is the disjoint union of these three families.✦ A vertex is incident to an edge when it is its head or its tail✦, and is if is the head of , if it is the tail, and otherwise.✦
The faces are the unit squares parallel to the coordinate planes, each given by its lowest corner, and the face set is the disjoint union of the faces in the , and planes.✦ Write for the indicator vector of an edge or a vertex . The face cycle of a face goes once around its boundary, with 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)✦ and 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.✦
The boundary map is the linear map (2) The kernel of the boundary map is the space of flows, the labellings of the edges whose boundary vanishes at every vertex, and the central flow group is written multiplicatively.✦
Local Groups and Configurations
The local cycle of an edge is the map on the faces on that sends to the nonzero scalar .✦ The local group of is the support group attached to this cycle, the central extension by the flows of the group of labellings of the faces on by points of the plane .✦ The elements of are the pairs of a labelling of the faces on by points of , the face part of , and a scalar , the flow of .✦ The central element of a flow is ✦, and the local shift of by is the product .✦
The edges at a vertex are the edges incident to it.✦ A local state at assigns to each edge at an element of ✦, and it is compatible when, for any two edges and at and any face on both, and have the same face part at .✦ The divergence of a local state at is its net flow into , (3)✦ For a charge , a configuration for at is a compatible local state at whose divergence is .✦
For an edge vector , the shift of a local state at by is the local state whose element at each edge at is the local shift of by .✦ If is a second charge with , the shift by of a configuration for at is the configuration for at with the shifted local state.✦
Atoms and the Analysis Structure
For a charge , the atoms of the grid structure come in two disjoint sorts: the edge atoms with and , which form the set , and the configuration atoms with and a configuration for at , which form the set .✦
The vocabulary consists of the eight binary symbols , , , , , , , , and the atom relations interpret them on the atoms.✦ relates each edge atom to itself and each configuration atom to itself; relates any two edge atoms on the same edge and any two configuration atoms at the same vertex. relates each configuration atom to the edge atoms for the edges at , and, for , relates to exactly when has flow .
A face class label is either a pair of an edge and a labelling of the faces on by points of , or a pair of a vertex and such a labelling for each edge at .✦ The class label of an atom keeps its face data: receives with the face part of , and receives with the face parts of all the .✦ The class index of an atom is the position of its class label in a fixed enumeration of the face class labels.✦
A binary relational structure over a vocabulary is a set , its universe, together with a binary relation on interpreting each symbol of .✦ The analysis signature is the finite vocabulary made of a copy of each symbol of , a preorder symbol and a raw difference symbol for each .✦ The analysis structure of a charge is the binary relational structure over the analysis signature whose universe is the set of atoms of , in which each symbol of is its atom relation, holds when the class index of is at most that of , and holds of two atoms exactly when they are edge atoms and on the same edge with .✦
For charges and and an edge vector , the atom shift by is the relation from the atoms of to those of that relates each edge atom to and, at each vertex with , each configuration atom to , where is the shift of by .✦ A flow acts on the atoms of by the atom shift by , and is the atom to which sends the atom .
Counting Types and Homogeneity
The formulas of the counting logic over a vocabulary , with variable names from a set , are built from , the equations and the atoms with by negation, conjunction, existential quantification and exact counting quantification for .✦ For a natural number , is the logic whose names are .
Satisfaction in a binary relational structure with universe , under an assignment , is the usual one, with true when exactly elements satisfy under updated to send to .✦ The free variables of a formula are the names occurring in it outside the scope of a quantifier binding them, existential or counting.✦ The type of an assignment relative to a finite set of names is the set of formulas with and .✦
Let have a nonempty universe , let be a tuple of elements of indexed by a finite set , and let be an injection of into the names of . The counting type of at is the type, relative to the names of the tuple, of the assignment giving each name the value : (4)✦
Let a group act on the universe of . The structure is -homogeneous through in when, for every , every injection of into the names of and any two -tuples and of elements of , (5)✦
The box isoperimetric constant is .✦ A natural number meets the width condition for when (6)
The Claim
Theorem 1. Let , let be a natural number, and let be a charge such that has at least one atom. Let be a finite set whose size meets the width condition (6), let be an injection of into the names of , and let and be -tuples of atoms of with . Then (7)✦ and (8)✦ For empty , any two -tuples and of atoms of satisfy (9)✦ for every and every charge , with no other hypothesis. For every natural number that meets the width condition, (10)✦
In the paper, the result reads: if satisfies and two -tuples in the same have equal -types, then some maps the first tuple to the second, and for empty tuples the statement holds without any width hypothesis.
What Is Checked
The claim is stated over the analysis structure of a charge on the grid of side and its atoms, the counting types (4) of tuples of atoms placed at the names of , the central flow group acting on the atoms, the atom shift, the width condition (6) and homogeneity (5).
About these constructions, the library proves that the boundary map (2) is linear, so that is a subspace of , and that the shift by an edge vector keeps a local state at compatible and raises its divergence by .