The Setting
A charge on the cubic grid of side is a vector indexed by the set of vertices of the grid, that is, a value in the field of integers modulo at each vertex. Each charge gives a finite structure , its analysis expansion, whose atoms sit on the edges and the vertices of the grid, the charge fixing the net flow at each vertex. Take the zero charge and the unit charge at a single vertex . The question is whether a sentence of the counting logic , with variable names, can tell from when the grid is large against .
Counting Logic and Types
A binary relational structure over a vocabulary with universe interprets each symbol as a binary relation on .✦ The counting formulas over with variable names from a set are built by (1) with , and , and is the set of those whose names come from a fixed set of names. The free variables of a formula are the names that occur in it outside the scope of a quantifier binding them; a sentence is a formula without free variables.✦
Satisfaction under an assignment is the standard one, the counting quantifier holding when exactly elements witness it: (2)✦
The type of an assignment in relative to a finite set of names is the set of formulas with free variables in that satisfies under , (3)✦ The counting type in of a tuple , indexed by a set with entries in a nonempty universe and placed at names by an injection , is the type, relative to the names of the tuple, of the assignment that gives to and a fixed default element of to every other name. The empty tuple has no names, and its counting type is the set of sentences that satisfies.
The Grid
The vertex set of the grid is , with elements.✦ An edge is a unit segment parallel to an axis, given by its lower end: runs from to , and and run along and in the same way.✦ The tail of an edge is its lower end✦ and its head its upper end✦, and is the set of edges. A vertex is incident to an edge when it is its head or its tail✦, and the edges at are the edges incident to .✦ A face is a unit square parallel to the , or plane.✦
The boundary map is the linear map (4)✦ and the orientation sign of a vertex and an edge is if is the head of , if is its tail, and otherwise.✦
The face cycle of a face goes once around its boundary: it is on the two sides of 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✦, and the local cycle of is the map from the faces on to that sends each such face to .
For a set of edges, the component of a vertex off is its connected component in the graph on whose edges are the grid edges outside .✦ A vertex is giant off when this component holds more than half of the vertices: (5)✦
The giant bound for and is the inequality (6)✦ where is the box isoperimetric constant.
Atoms and the Analysis Expansion
For a finite set of faces, a group of flows and a map , the support group is the central extension of the group of face labellings by attached to ✦, where the plane is the set of pairs of scalars.✦ Its elements are the pairs of a face labelling and a flow, the flow of being ✦, and the central element of is .✦ The local group of an edge is the support group over the faces on , with flows in and the local cycle of as .✦
A local state at a vertex is an assignment to each edge at of an element of .✦ A local state at is compatible when for any two edges at and every face on both.✦ The divergence of a local state at is its net flow into , (7)✦ For a charge , a configuration at for is a compatible local state at with divergence .✦
The atoms of a charge are of two sorts: the edge atoms , with an edge and , which form the set , and the configuration atoms , with a configuration at for , which form the set .✦ The atom relations of interpret the eight binary symbols of on these atoms. holds of each edge atom with itself and of each configuration atom with itself; relates any two edge atoms over the same edge and any two configuration atoms over the same vertex; relates to for each edge at ; and, for each , relates to when has flow .✦
A face class label is 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: has the label , and with has the label .✦ The class index of an atom is the position of its class label in a fixed enumeration of the face class labels.✦
The analysis signature consists of the symbols of , a preorder symbol and a raw symbol for each .✦ The analysis expansion of a charge is the binary relational structure over the analysis signature with the atoms of as universe that interprets each symbol of by its atom relation and the other symbols by (8)✦ where and are the flows of and ; holds of no pair other than a pair of edge atoms.
Shifts and Compatible Assignments
Fix charges and and an edge vector . The shift of an element by a scalar is , its product with the central element of ✦, and the shift of a local state at by shifts its element at each edge by .✦ At a vertex with , the shift of a configuration at for is the configuration at for whose local state is that of shifted by .✦ The atom shift by is the relation from atoms of to atoms of that holds between and for every edge atom, and between and for every configuration atom at a vertex with .✦
The block of an atom is the edge or the vertex it lies over✦, and the edges touched by an atom are those of its block: itself for an edge atom over , the edges at for a configuration atom over .✦ For a finite set of names and an assignment of atoms to the names, is the set of edges touched by the atoms with .✦
A compatible assignment on a finite set of names is a pair of assignments of atoms of and of atoms of to the names for which there are an edge vector and a vertex with (9)✦
The Claim
Theorem 1. Let and be natural numbers satisfying the giant bound (6), let be a vertex of the grid, and let and . For every sentence of over the analysis signature and all assignments of atoms of and of atoms of to the names, (10)✦ If the atoms of and the atoms of form nonempty sets, the empty tuple has the same counting type in the two expansions: (11)✦
In the paper, the result reads: for all sufficiently large , the expansions and , where and , satisfy the same sentences, the paper’s being .
What Is Checked
The claim is stated over the analysis expansions (8) of the charges and on the grid of side , the sentences of (1) with their satisfaction, the counting type (3) of the empty tuple, and the giant bound (6).
The library proves two further facts about these constructions. The first is defect transport. Let and satisfy the giant bound, let and be charges, let be sets of edges with , and let satisfy for a vertex , its defect, giant off in the sense of (5). Then there are an edge vector and a vertex with (12)✦
The second carries truth along a system of partial bijections. Let and be binary relational structures over with universes and , and let be a set of triples of a finite set of names in and assignments and . Suppose that for each triple in the correspondence , , is a partial isomorphism: exactly when , and exactly when , for all and . Suppose also that for each triple in and each name some bijection puts in for every . Then for every triple in and every formula over with names from whose free variables lie in , (13)✦