The Setting
Lower bounds for choiceless polynomial time with counting (CPT) compare two structures through the hereditarily finite sets built over their elements. The sets that matter have small supports hereditarily: the set, its elements, their elements and so on are each fixed by every element of a given group that fixes some short tuple of atoms. The question is when two structures and that a counting logic with variables cannot distinguish give universes of such sets that a counting logic with fewer variables cannot distinguish either.
The library answers it for two structures in one binary vocabulary with groups acting on them, in a form with arbitrary sets of variables, and for the grid structures on which the separation of CPT from polynomial time is built, under the central flow group.
Counting Logic and Types
A binary relational structure over a vocabulary is a set , its universe, with a binary relation on for each symbol of .✦ The formulas of counting logic over with variables from a set are built from , equations and atoms , for and , by negation, conjunction, existential quantification and, for each natural number , the counting quantifier .✦ Satisfaction under an assignment is defined by recursion on as for first-order logic, with (1)✦ The free variables of a formula are those occurring in it outside the scope of a quantifier binding them, and a sentence is a formula without free variables.✦ We write for counting logic with the variables ; two structures are -equivalent when they satisfy the same sentences of .
Let be a tuple of elements of indexed by a finite set , and let an injection place the entry at the variable . The counting type of under is the set of formulas (2)✦ and for the empty tuple it is the set of sentences true in .
A structure on which a group acts is homogeneous under through length in when, for every and every injection of into , any two -tuples and of of the same type under lie in one -orbit: (3)✦
Hereditarily Supported Sets
For a set of atoms, is the set of hereditarily finite objects over : the atoms, which have no elements, and the finite sets whose elements are again in , two sets being equal when they have the same elements.✦ Let a group act on , and with it on . A tuple of atoms supports an object of when (4)✦ An object of is -supported when some tuple of atoms supports it✦, and hereditarily -supported when , its elements, their elements and so on are all -supported.✦ The domain is the set of hereditarily -supported objects of .✦
For a vocabulary , the vocabulary consists of a membership symbol , an atom symbol and the symbols of , all binary.✦ For a structure over with acting on its universe, is the structure over with universe and, for in it and , (5)✦
The Grid Structures
The grid of side , for a positive integer , has vertex set .✦ Its edge set consists of the unit segments parallel to the , and axes, each directed from its tail to its head, the endpoint with the larger coordinate along it✦, and its face set of the unit squares parallel to the , and planes✦. With the indicator vector of a vertex , the boundary map is the linear map (6)✦ the flows are the elements of ✦, and the central flow group is written multiplicatively, so that adding flows is multiplying in ✦. The face cycle of a face goes once around : it is on the two sides crossed in their own direction, on the other two and elsewhere.✦
The local group of an edge is the central extension, attached to the coefficients of the faces on (those having as a side), of the group of labellings of these faces by points of the plane by the group ; its elements are the pairs of such a labelling, the face part, and a scalar, the flow.✦ A local state at a vertex assigns to each edge at , an edge with head or tail , an element of its local group.✦ A local state at is compatible when the elements at any two edges at have the same face part at every face whose boundary passes through both.✦ The divergence of a local state at is the net flow into , the sum over the edges at of times the flow at , where is if is the head of and if is its tail.✦ For a charge , a configuration at is a compatible local state at with divergence .✦
The grid structure of a charge is the structure over the vocabulary of eight binary symbols whose atoms are the edge atoms , with in the local group of , and the configuration atoms , with a configuration at . Here relates each edge atom to itself and each configuration atom to itself, any two edge atoms over one edge and any two configuration atoms over one vertex; relates to for each edge at , and, for , relates to when has flow . The central flow group acts on the atoms of every .
The analysis expansion is the structure on the same atoms over the analysis signature , which adds to a preorder symbol and a raw symbol for each . The symbols of keep their relations. The class label of an atom is obtained from the atom by keeping its edge or vertex and only the face parts of its group elements.✦ The class index of an atom is the position of its class label in a fixed enumeration of all class labels, and holds when the class index of is at most that of . Finally relates to when the flow of minus that of is .✦
The box constant is ✦, and and satisfy the giant component bound when (7)✦
The Claim
Theorem 1. (a) Let and be nonempty structures over one binary vocabulary , let groups and act on them by automorphisms, and let , and be positive integers with . Suppose that and are -equivalent and that each is homogeneous under through length in . Then every sentence of over satisfies (8)✦
(b) Let and be nonempty structures over , let groups and act on them, and let be a positive integer, a set of variables and a finite set of variables. Fix an injection placing the entries of a pair of -tuples at distinct variables of , and an injection placing the entries of a family of -tuples indexed by at distinct variables of . Suppose that in each any two pairs of -tuples with the same type under lie in one -orbit, as do any two such families with the same type under , and that and satisfy the same sentences of counting logic with variables from . Then every sentence over with variables from satisfies (9)✦
(c) Let , and be positive integers and a natural number, let be a vertex of the grid of side , and suppose that the grid structures and of the charges and have atoms. With , suppose that , that , and that and satisfy the giant component bound (7). Then every sentence of over satisfies (10)✦
In the paper, the result reads: if and are nonempty finite structures in the same binary vocabulary, , and , , are positive integers with such that and satisfy the same sentences and in each any two tuples of length at most with the same type lie in the same -orbit, then the structures and of the objects of such that and every object in its transitive closure have a -support of length at most , with membership, an atom predicate and the relations of , false on non-atoms, satisfy the same sentences.
What Is Checked
The three statements are stated over counting logic with its satisfaction relation, free variables and types of tuples; over the hereditarily finite objects on a set of atoms, their supports under a group action and the structures with membership, atom predicate and base relations; over homogeneity through a length; and, in (10), over the grid structures , their analysis expansions , the central flow group , the box constant and the giant component bound (7).