The Setting
The result that choiceless polynomial time with counting does not capture polynomial time turns on a separating query , a query on finite structures over a vocabulary of eight binary relations. It asks whether a system of linear equations over the field of integers modulo , the field of scalars, has a solution, the unknowns being weights on the atoms of the structure. It is tested on grid structures: for a charge on the vertices of the cubic grid of side , the grid structure has atoms of two sorts, attached to the edges and to the vertices of the grid. The question is how answers on the zero charge and on a point charge, which is at one vertex and at all others.
The Grid
The cubic grid of side has the vertex set of vertices.✦ A charge on the grid is a map , and the total charge of is the sum .
The edges of the grid are the unit segments parallel to the axes. The edge along runs from to , for and ; the edges along and along step in the second and in the third coordinate instead. The edge set is the disjoint union of these three families.✦ The tail of an edge is its lower endpoint ✦, and its head is its upper endpoint✦. A vertex is incident to an edge when it is the head or the tail of ✦, and is the set of edges at ✦. The incidence of a vertex and an edge is the scalar if is the head of , if is its tail, and otherwise.✦
The faces of the grid are the unit squares parallel to the coordinate planes, each given by its lowest corner: the face in the plane at has opposite corners and , for and ✦, and the faces in the and planes are placed the same way; is the set of all faces. The face cycle of a face goes once around its boundary. For the face in the plane at , with the indicator of an edge , (1)✦ and the faces in the other two planes are traversed in the same way, with for their sides along . The set of faces on an edge is the set of faces with .✦ The local cycle of an edge is the map sending to .✦
Local Groups and Configurations
The plane is the set of pairs of scalars, added and scaled coordinatewise.✦ Let be a set of faces, a space whose elements are called flows, and a cycle map. The support group is the central extension, attached to , of the group of face labellings by .✦ The elements of the support group are the pairs of a face labelling and a flow . The local group of an edge is the support group of its local cycle , with the faces and flows in .✦
A local state at a vertex is an assignment to each edge of an element of .✦ A local state at is compatible when the elements it assigns to edges sharing a face agree on that face: (2)✦ The divergence of a local state at is the scalar given by the net flow into , (3) For a charge , a configuration at a vertex is a compatible local state at with .✦
The Grid Structure
The vocabulary consists of the binary relation symbols , , , , and for each scalar , eight in all.✦ A -structure with universe interprets each symbol of as a binary relation on .✦
The grid structure of a charge is the -structure whose universe is the disjoint union of two sorts of atoms: the edge atoms, the pairs of an edge and an element , and the configuration atoms, the pairs of a vertex and a configuration at .✦ In , relates each edge atom to itself and each configuration atom to itself; relates any two edge atoms over the same edge, and any two configuration atoms over the same vertex.✦ The relation joins a configuration atom to the edge atoms for , and joins edge atoms and over the same edge exactly when has flow .
The Query
In a -structure with universe , the edge atoms form the set ✦ and the configuration atoms the set ✦; for , . A configuration atom and an edge atom are incident when there are and with , and .✦ The coefficient of an edge atom at a configuration atom is the scalar (4)✦
Weights are normalized when (5)✦ and weights and are consistent when (6)✦ The separating query holds of when there are weights on and on such that is normalized and and are consistent.✦
The Claim
Theorem 1. Let be the side of the cubic grid, let be the grid structure of a charge , and let be the zero charge.
(i) If , is a vertex and is the point charge at , then (7)✦
(ii) If and satisfies , then (8)✦
(iii) For every , including , (9)✦
What Is Checked
The three statements are made over the grid structures of charges on the cubic grid of side , built from the local groups of the edges and the configurations at the vertices, and over the separating query , defined by normalized and consistent weights on the configuration atoms and edge atoms of a -structure.