The Setting
The proof that choiceless polynomial time with counting does not capture polynomial time works with grid structures , built on the cubic grid of side from a charge on its vertex set , over the field of integers modulo . This lemma belongs to the step where small orbits are shown to have sparse supports, and it is linear algebra on the grid alone. Label the edges of the grid by elements of , and suppose that the signed sum of the labels around a face is nonzero for only faces: on how few edges must the labelling differ from the differences of a vertex function along the edges? The answer is a vertex function whose differences along the edges, subtracted from the labelling, leave a labelling that is nonzero on few edges, together with a bound on the number of those edges for an explicit choice of the vertex function.
The Grid
Fix the side . A grid vertex of the cubic grid of side is a triple of integers in , so that the vertex set has elements.โฆ
A grid edge is a unit segment between two grid vertices, parallel to a coordinate axis and named by its lower endpoint.โฆ The edge along runs from to , for and ; the edges from to and from to are indexed in the same way, the coordinate that moves running up to and the other two up to . The edge set is the disjoint union of the three families.โฆ The tail of an edge is its lower endpointโฆ, and its head is its upper endpoint, where the coordinate in the edgeโs direction is replaced by its successor.โฆ
A grid face is a unit square with its corners at grid vertices, parallel to a coordinate plane and named by its lowest corner.โฆ The face in the plane has opposite corners and , for and โฆ; the faces and have opposite and respectively, the two coordinates that move running up to and the third up to . The face set is the disjoint union .โฆ
Gradient and Curl
An edge labelling of the grid is a function , an element of , and a vertex function is a function . The gradient of a vertex function is the edge labelling given by (1)โฆ
The face cycle of a face is the edge labelling that goes once around the boundary of : it is on the two sides crossed in their own direction, on the other two and elsewhere.โฆ For a face in the plane, with the indicator vector of the edge , (2)โฆ and the faces in the and planes are traversed in the same way, the first axis of the plane taking the part of and the second the part of .
The curl of an edge labelling is the function whose value at a face is the signed sum of around it: (3) The support of a function from a finite set into is the set of points at which is nonzero.โฆ
Potentials and Residuals
For an edge labelling and a coordinate , the potentials of at are prefix sums of labels along coordinate lines, and the residuals are the edge labellings left by subtracting their gradients in turn: (4)
For an edge labelling and a value of the first coordinate, the set of consists of the faces in the plane at which is nonzero, and the set of of those in the plane; the set of consists of the pairs with for which the face , in the plane , has nonzero curl.
The Claim
Theorem 1. Let , let be an edge labelling of the cubic grid of side , and let be the number of faces at which its curl is nonzero. Then there is a vertex function with (5)โฆ Moreover, for every the residual of at satisfies (6)โฆ
In the paper, the result reads: if has nonzero curl on exactly faces of the box, there is a vertex function such that is supported on at most edges, and in particular is a gradient when .
What Is Checked
Both claims are stated over edge labellings of the cubic grid of side with values in , through the gradient (1), the curl (3) taken against the face cycles (2) and the sizes of supports; (6) is stated in addition over the potentials and residuals (4) at and the sets , and of faces of nonzero curl.