The Setting
A choiceless computation on a finite structure builds hereditarily finite objects over the atoms of its input and never chooses among them. Fix a bound , run a program on an input of at most elements whose states up to a stage have at most elements each, and code every element of every state by a hereditarily finite object over the input. The question is how many objects the run touches, counting the input atoms, the codes and everything that occurs in a code as a member, a member of a member and so on, and whether they fit in one small transitive family, that is, a family closed under membership, which the automorphisms of the input also leave invariant. On the grid structures on which choiceless polynomial time with counting is separated from polynomial time, the further question is how many atoms it takes to support each such object. The library answers both for interpretation programs, whose steps are two-dimensional interpretations in Härtig logic.
Hereditarily Finite Objects and Structures
The set of hereditarily finite objects over a set of atoms consists of the atoms of and the finite sets whose elements lie in , two sets being equal when they have the same elements.✦ A map extends to the map that replaces each atom occurring in an object by .✦
A finite structure over a set of binary relation symbols is a finite set , its universe, with a binary relation on for each .✦ An isomorphism of finite structures over is a bijection of their universes such that (1)✦ and an automorphism of is an isomorphism of with itself.
Interpretation Programs and Their Trace
A formula of Härtig logic over in free variables is falsity, an equation or an atomic formula with between two of the variables, the negation of a formula, the conjunction of two formulas, the existential quantification of a formula in one more variable, or the Härtig quantification of two formulas in one more variable, which says that they are satisfied by equally many elements.✦
An interpretation of structures over a set of binary relation symbols in structures over is two-dimensional and consists of formulas of Härtig logic over , (2)✦ where defines the domain as a set of pairs, says which pairs are identified, and defines between pairs the relation named by . The interpretation defines in a structure over the structure over , whose elements are classes of identified pairs.
An interpretation program over consists of a finite set of state symbols, an initial interpretation of structures over in structures over , a step interpretation of structures over in structures over , and two sentences of Härtig logic over , the halting condition and the output condition.✦ The state of after steps on a finite structure over is the finite structure over given by (3)✦
An element of a state, a class of identified pairs, is coded by the set of the codes of its pairs, and the code of a pair is the Kuratowski pair of the codes and of its two coordinates. The base family of a finite structure over with universe for a bound is the finite subset of consisting of the atoms of and the von Neumann ordinals ; it opens the next paragraph, which defines the trace family.
For such a program , a finite structure over with universe and a bound , the trace family of on is the increasing sequence of finite sets , for , that starts from the base family of for and grows by (4)✦ where and are the codes of pairs and the codes of classes that arise in coding the elements of : from and its atoms through when , and from and its codes through when .
Supports
Let a group act on a set of atoms, and through them on . A tuple of atoms supports an object when every element of that fixes each entry of fixes : (5)✦ For a natural number , an object is -supported when some tuple of atoms supports it✦, and hereditarily -supported when every object reached from in finitely many steps down membership, itself, its elements, their elements and so on, is -supported.✦
The Grid Structure
Fix . The grid has side and scalars in the field , where . Its vertex set is , with elements.✦ Its edges are the unit segments parallel to a coordinate axis, each running from its tail to its head: the edge along runs from to , and the edges along and along 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 the head or the tail of ✦, and the edges at are those incident to it✦; the sign is if is the head of , if is its tail, and otherwise.✦ The face set consists of the unit squares parallel to the , the or the plane, each given by its lowest corner.✦
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 boundary map is the linear map given, with the vector that is at the vertex and elsewhere, by (6)✦ and its kernel is the space of flows, the labellings of the edges whose boundary vanishes at every vertex.✦ The central group is written multiplicatively.✦
For a set of faces, a vector space of flows over and a map , the support group attached to is the central extension by of the group of labellings of the faces by points of the plane; its elements are the pairs of a labelling and a flow .✦ The faces on an edge are the faces with ✦, and the local cycle of sends each face on to .✦ The local group of is the support group of its local cycle, with : its elements are the pairs of a labelling of the faces on by points of and a scalar , their flow.✦
A local state at a vertex assigns to each edge at an element of .✦ A local state at is compatible when any two edges and at on a common face receive labellings that agree at , , and the divergence of is the net flow into , (7) For a charge , a configuration at is a compatible local state at whose divergence is .✦
The atoms of a charge are of two sorts: the edge atoms , of an edge and an element , and the configuration atoms , of a vertex and a configuration at .✦ The vocabulary consists of the eight binary symbols , , , , , , , .✦ The grid structure of is the finite structure over whose universe is the set of atoms of , in which 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, relates to for each edge at , and relates to when has flow .
The Claim
Theorem 1. Let be an interpretation program over , let be a finite structure over , let and be natural numbers, and write for .
Suppose that and , that has at most elements, and that each state with has at most elements. Then, for every automorphism of , (8)✦
If has at most elements and each state with has at most elements, then (9)✦
If , then (10)✦
For every isomorphism of finite structures over and every object , (11)✦
Let and let be the grid structure of a charge on the grid of side , with ; let be a positive integer and a real number. Suppose that and , that has at most atoms, that each state with has at most elements, and that . Then, for the action of the central group on the atoms of , (12)✦
In the paper, the result reads: for either of the two inputs and , with and for a vertex , the input atoms, all vertex codes up to halting and all objects recursively occurring as members of those codes belong to an -invariant transitive family of at most objects, being the central extension of the group of face labellings by .
What Is Checked
The claim is stated over interpretation programs of Härtig logic and their states (3), the trace family (4) of hereditarily finite objects over the input, isomorphisms (1) of finite structures acting on these objects through their atoms, and, in (12), the grid structure of a charge, with the central group acting on its atoms and the supports (5) for that action.