The Setting
The counterexample to Sidorenko’s conjecture is built on a configuration of points, numbered , and faces, numbered , the face being a set of three points. In order, the faces are , , , , , , , , , , , , , , , , , , , , and .✦
The graph is the incidence graph of the configuration: the bipartite graph on the points and the faces that joins each point to the faces containing it. A corner is a pair of a point and a face with , and is the set of corners.✦
Fix an odd prime , write , and fix an even dimension . Every point receives a symmetric matrix over and every face such a matrix , all independent and uniform. A set of corners spans a subgraph of , and each of its corners is weighted by a kernel of rank , with a sign chosen for that corner, evaluated at . The expected product of these weights is a homomorphism density of the subgraph, each edge carrying its own kernel. The question is how this density compares with the sign model correlation as with fixed, and how a kernel changes when is replaced by .
Symmetric Matrices, Signs and Rank Kernels
Let be a finite field and its quadratic character. The space of symmetric matrices is the subspace of the matrices over formed by the matrices with , and is .✦
For a symmetric bilinear form on a finite-dimensional vector space over , the radical is the subspace of the vectors with for every , and the radical quotient form is the nondegenerate form that induces on .✦ The sign of is (1)✦ where is the Gram matrix of in a basis of ; it is when . The sign of a matrix is the sign of the form on .✦
For a natural number and an integer , the signed rank layer is the set of matrices of rank with ✦, and its mass is (2)✦ For a natural number and an integer , the rank kernel of rank and sign is the real function on attached to the layer .
Layer Correlations
The uniform mean of a real function on a finite set is .✦ For a natural number , an odd prime , a set of pairs of a point and a face, and an integer function on such pairs, the layer correlation is the uniform mean (3)✦ over the families of matrices in indexed by the points and indexed by the faces. For a natural number , an odd prime , a set of pairs of a point and a face and an integer function on such pairs, the sign model correlation is the real number that the sign model, the comparison model for the layer correlation, assigns to these data.
A real function on the odd primes tends to as through odd primes when for every there is a bound with for every odd prime .
The Singular Tail Threshold
A point pair is a set of two points lying together in some face.✦ There are point pairs , numbered , and each lies in exactly two faces. The sides of the face , with and , are , and .✦
Each face carries a three-bit label , from an explicit table that runs from and to . The separation count of a point pair is the Hamming distance between the labels of the two faces containing , a number from to , and .✦
A profile is a pair of a natural number for each face and a natural number for each point pair ; write for . The profile is geometric in dimension when, for every face and every , (4)✦
In dimension , the natural cost of the face is ✦, and the profile cost is (5)✦ where is the triangular function✦.
A tail tuple consists of natural numbers , , and triples and of natural numbers.✦ For a tail tuple , the sizes are , the heights are , the maximal height is and the offset is the real number .
The planted gain of real numbers and real triples is (6)✦ In dimension , the full tail gain of a tail tuple is , and its lower tail gain is .✦
Let and be natural numbers, a natural number and a triple of sizes. The lower tail tuple of and is .✦ A common parameter is an integer with , and .✦ For a rank and a dimension , a base parameter is a quadruple of integers in that is feasible✦, which means that for (7)✦ The planted tail tuple of a common parameter and a base parameter for the rank in dimension is .✦
For natural numbers and and a profile , a choice of tails marks each face full or lower, and gives each full face a common parameter for and a base parameter for the rank , the dimension and the sizes .✦ The face then carries the tail tuple : the planted tail tuple of if is full, the lower tail tuple of and if not. The global tail gain is the sum over the faces of the full tail gain of at full faces and of its lower tail gain at lower ones.✦
The singular tail threshold is a fixed natural number with such that, for every even , every profile geometric in dimension and every choice of tails for it, (8)✦
The Claim
Theorem 1 (Rank-layer limit).
There is a positive integer with the following property. Let be even, let be a set of corners and let be an integer function on the pairs of a point and a face with for every . Then, as through odd primes, (9)✦
The threshold can be taken to be the singular tail threshold : for every natural number with and every and as in (1), as through odd primes, (10)✦
Let be a finite field, and natural numbers, an integer and . Then (11)✦
In the paper, the result reads: there is such that for every fixed even , as through odd primes, for independent uniform , every and all signs on , the mean equals the value of the sign model up to , uniformly in and the signs, and the same holds with in place of , with the page’s for the paper’s . The second form, with , is answered in the box by the reflection rule (11).
What Is Checked
The rank-layer limit (9) and its form (10) are stated over the corners of , the symmetric matrices over with their ranks and signs, the rank kernels of rank , the layer and sign model correlations, limits as through odd primes and, in (10), the singular tail threshold ; the reflection rule (11) is stated over the rank kernels on the symmetric matrices over a finite field. Beyond the claim, the library proves the global tail dichotomy: a natural number at least with the property (8) asked of exists.✦