The Setting
Let and consider the cubic grid of side , whose vertex set consists of the triples of integers with .✦ A charge gives the grid structure , whose elements are atoms attached to the edges and to the vertices of the grid and whose relations interpret the vocabulary of eight binary relation symbols. Its analysis expansion adds to relations built from the face data and the flows of the atoms. Structures of this kind are compared in the counting logic with variable names, through the types of tuples of atoms.
The Grid Structure
A grid edge is a unit segment between two vertices, parallel to a coordinate axis and oriented from its tail to its head, the end whose coordinate in the edge’s direction is the larger; is the set of edges.✦ The edges at a vertex , written , are those with as head or tail✦, and the edge vertex incidence is if is the head of , if is its tail, and otherwise.✦
A grid face is a unit square parallel to a coordinate plane, and is the set of faces.✦ 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.✦ The faces on an edge are the faces with , the squares having as a side; they form the set .✦
The local group of an edge is the central extension of the group of face labellings by attached to the local cycle of .✦ Its elements are the pairs of a face labelling and a flow .✦
A local state at a vertex assigns to each edge an element of .✦ A configuration at is a local state at that is compatible, in that for any two edges and any face on both, and whose divergence is the charge at : (1)✦
The atoms of are of two disjoint sorts: an edge atom is an edge with an element , and a configuration atom is a vertex with a configuration at .✦ The relations of interpret the symbols of . holds of each edge atom with itself and of each configuration atom with itself; relates any two edge atoms on the same edge and any two configuration atoms at the same vertex; relates a configuration atom to the edge atom for each edge ; and , for , relates edge atoms on one edge through the flow of a product in : (2)✦
The Definition
Definition 1. For a vocabulary of binary relation symbols, a -structure is a set , its universe, with a binary relation on for each : (3)✦
A class label is a pair of an edge and a face labelling , or a pair of a vertex and a face labelling for each edge ; the class labels form the finite set (4)✦ The class map sends an atom of to its class label in , keeping its face labellings and forgetting its flows: (5)✦
The analysis vocabulary adds to a binary symbol and a binary symbol for each : (6)✦ For , the raw difference is the binary relation on atoms that holds between two edge atoms on the same edge whose flows differ by , and never holds of a pair with a configuration atom in it: (7)✦ Fix a bijection . The analysis expansion of is the -structure on the atoms of that interprets each symbol of as does, each as in (7), and as the total preorder (8)✦
The counting formulas over with variable names from a set are generated by (9)✦ The counting logic is the set of counting formulas over whose variable names come from a set with elements. The free names of a formula are given by (10)✦ For an assignment , write for the assignment that sends to and agrees with elsewhere. Satisfaction is defined by recursion on : is never satisfied, and are negation and conjunction, and (11)✦
The type of an assignment at a finite set of names is the set of formulas with free names in that satisfies under : (12)✦ Let be nonempty, let be a tuple in indexed by a set and an injection placing its entries at names, and let send to and every other name to a fixed element of . The type of placed at is the type of at , a set of formulas: (13)✦
For a real number , the number of variable names is (14)✦
In the paper, the result reads: adds to the total preorder coming from a fixed order of the classes and , and the relations between edge atoms on the same edge with , where and are the last coordinates of the two atoms; is first-order logic with equality, and exact counting quantifiers with at most variable names, with the -types of tuples; and .
What Is Checked
The definitions are stated over the grid structure of a charge on the grid of side , with its edge and configuration atoms, the local groups and the relations of , and, for the counting logic, over an arbitrary vocabulary of binary relation symbols and an arbitrary set of variable names.