The Setting
Throughout, is the incidence graph of 13 points and 22 faces: the bipartite graph on the points and the faces in which each point is joined to the faces containing it, the faces being the triples , , , , , , , , , , , , , , , , , , , , , . Two points of a common face form a point pair, and there are 33 point pairs.
The kernels here are built from symmetric matrices over , the field with elements for an odd prime . A vertex carries a type and one symmetric matrix for each coordinate of a finite set , and an edge compares the matrices at its two ends at the coordinates that a random activation switches on, the activation being drawn with a law that depends on the two types. The question is the homomorphism density of in such a kernel as .
Laws and Activations
A finite probability law on a finite set is a function with ✦, and the expectation of a real function on is .✦ The product of laws on finite sets is the law on with weight at , under which the coordinates are independent✦; the uniform law on gives each point the weight .✦
An activation on is a pair of a set of active coordinates and a sign vector .✦ The entry of an activation at a coordinate is if and otherwise✦, and its character on a set is the Boolean monomial of its signs on when is active: (1)✦ An activation law on is a finite probability law on the activations on . An activation law on satisfies the zero-moment condition when for every nonempty , and the activation moment of is the function on pairs of subsets of given by (2)✦
Corners and Labellings
A corner is a face with a slot .✦ The points of each face are listed in increasing order ✦, the point of the corner is ✦, and the 66 corners are the edges of , the corner joining to . The slots , , of also hold its sides , , , which are point pairs.✦ The left pair and the right pair of the corner are the two sides of through , the left one in the lower slot. The corners of a point pair form the set of corners with .✦ Each face carries a fixed three-bit label; the faces carry in order , , , , , , , , , , , , , , , , , , , , , . The separation count of a point pair is the number of places, from to , at which the three-bit labels of the two faces containing differ.
A labelling assigns to each of the 33 point pairs a nonempty set .✦ For a family of real functions on pairs of subsets of , one for each corner, the active coefficient is (3) For a family of activations on , one for each corner, the expanded model is (4)✦ the middle product running over the 33 point pairs.
Matrix Kernels
Fix a finite field with quadratic character and a natural number , and let be the space of symmetric matrices over .✦ The sign of a symmetric bilinear form on a finite-dimensional space over is for a Gram matrix of the nondegenerate form that induces on , and it is when has rank zero✦; the sign of is that of the form .✦ For , the signed rank layer is the set of matrices in of rank and sign ✦, and its mass is .✦ For , the rank kernel is the real function on whose value at depends on whether lies in .
The sample kernel of an activation on and the activation kernel of an activation law on are the functions of two tuples and in given by (5) The conditional moment of a family of activation laws on , one for each corner, is the average (6)✦ over all choices of a tuple for each point and a tuple for each face , each choice with the same weight; over it is written .
Typed Kernels
For finite probability laws on finite sets and , the bipartite moment of a real function on is the homomorphism density (7)✦ where are independent with the law on and are independent with the law on .
Let and be finite sets of types, with finite probability laws on and on , and let be a family of activation laws on indexed by ; its swapped family , indexed by , has . The typed matrix kernel of is the function on , with and , given by (8)✦ and its typed laws on and are the products of and of with the uniform law on .✦ Its bipartite moment is taken with the typed laws, and over the kernel is written .
A type assignment is a pair of a map from the points to and a map from the faces to . The type law is the product law on type assignments, with weight (9)✦ At the corner receives the law , and these laws form the family . The typed coefficient is the active coefficient at ✦, and the averaged coefficient is .✦
The singular tail threshold is a fixed integer, at least , such that the global tail dichotomy of the last section holds in every even dimension .✦
The Claim
Theorem 1. Let , and be finite sets, and finite probability laws on and , and a family of activation laws on indexed by . Limits are taken as through the odd primes.
(i) If every satisfies the zero-moment condition and is even with , then (10)✦
(ii) Over and for every , (11)✦
(iii) Over , for even and for all and , (12)✦
Let further be a family of activation laws on , one for each corner, each satisfying the zero-moment condition, and let .
(iv) If is even with , then (13)✦
(v) If the activations are independent, each with law , then (14)✦
In the paper, the result reads: under the zero-moment condition, in an even dimension fixed as in Lemma 3.1 and for fixed type laws and activation laws, , where stands for and for , and the transpose has the analogous formula with the roles of the type sets exchanged.
The library gives the transpose by (12): is the typed kernel of , to which (10) applies with and exchanged.
What Is Checked
The claim is stated over the incidence graph with its corners, their points and their left and right pairs; activation laws on a finite set with their characters, activation moments and the zero-moment condition; the active coefficient over labellings of the point pairs and the expanded model; the signs, signed rank layers and rank kernels on over , with the sample, activation and typed matrix kernels built from them; the conditional and bipartite moments with the typed laws and the type law; the typed and averaged coefficients; and the singular tail threshold , limits being taken as through the odd primes.
About the threshold, the library proves the global tail dichotomy. A geometric profile in dimension is an assignment of natural numbers to the faces and to the point pairs such that for each side of and , the sum running over the three sides of .✦ The profile cost of in dimension is , where , the first sum runs over the 22 faces with , the inner sum running over the three sides of , and the second sum runs over the 33 point pairs .✦ A tail tuple consists of natural numbers , , and two triples of natural numbers and ✦; its tail sizes are ✦, its tail heights are ✦, its maximal tail height is the largest of ✦, and its tail offset is ✦. The tail gain in dimension of a tail tuple is, at a face marked full, the planted gain with , the sums running over , and, at a face not marked full, the triangular number .✦ Some faces are marked full. Put and for the side of the face in slot .✦ At a face marked full, a tail choice is a pair of an integer with , and , and a quadruple of integers between and such that, with , one has , for distinct , , and for each , , and ✦; it determines the tail tuple ✦. At a face not marked full the tail choice is trivial, and it determines the tail tuple ✦. A global tail choice in dimension assigns a tail choice to each face✦, and its global tail gain is the sum, over the 22 faces , of the tail gain in dimension of the tail tuple that determines at ✦. Let be even, let be a geometric profile in dimension , and let be a global tail choice, which assigns to each face a tail choice for , a pair as above if is marked full and the trivial choice otherwise. Then either the global tail gain of is strictly smaller than the profile cost of , or every is , every is or and the global tail gain is two thirds of the sum of the triangular numbers over the point pairs.✦