The squares that answer every request

Rado’s graph is the countable graph that coin tosses almost always produce, and it is characterised by one property. For any two finite, disjoint sets of vertices $U$ and $V$ there is a vertex outside both that is joined to everything in $U$ and to nothing in $V$. Call $(U, V)$ a request and the vertex a witness. Rado’s graph answers every request, of every size, and that single property makes it unique, makes its first-order theory complete, and explains why finite random graphs obey a zero–one law.

No finite graph can answer every request: a request that asks to be joined to every vertex has no witness. But a finite graph can answer every request with $|U| + |V| \le k$, and such a graph is called $k$-extending. It is a finite stand-in for Rado’s graph, good for sentences that only ever ask about $k$ vertices at a time. The question here is how small such a graph can be, and how well one particular construction does.

Squares modulo a prime #

The construction is due to Raymond Paley, who used the same numbers in 1933 to build tables of signs with perpendicular rows. Take a prime $q$ that leaves remainder 1 on division by 4, and the residues $0, 1, \ldots, q - 1$ as vertices. Join two residues when their difference is a nonzero square modulo $q$. Because $-1$ is a square for such primes, the relation is symmetric, and every vertex has exactly $(q - 1)/2$ neighbours — half the others.

The restriction on $q$ is not decoration. For a prime that leaves remainder 3 on division by 4, $-1$ is not a square, so if $a - b$ is a square then $b - a$ is not: the relation is not symmetric, and the construction produces a tournament — a contest in which every pair has a winner — rather than a graph. The Paley tournaments have their own version of the extension property, in which for any small set of players there is another who beats a prescribed part of the set and loses to the rest, and they answered a question of Kurt Schütte’s about tournaments in exactly the same way. The same construction also works over any finite field whose size leaves remainder 1 on division by 4, not only prime ones; the nine-element field gives the smallest example met below.

For $q = 13$ the squares are 1, 3, 4, 9, 10 and 12, so each residue is joined to the six that differ from it by one of those. The request in the figure — a vertex joined to 0 and to 3, and not to 5 — has exactly one witness, 12: it differs from 0 by 12 and from 3 by 9, both squares, and from 5 by 7, which is not.

Thirteen residues are not enough for every request of three, and the failure can be found by hand. Ask for a vertex joined to 1 but to neither 0 nor 2. The neighbours of 1 are 0, 2, 4, 5, 10 and 11, so the candidates outside the request are 4, 5, 10 and 11. Of those, 4 and 10 are joined to 0, and 5 and 11 are joined to 2. Nothing is left. The pattern the request asks for — one edge and two non-edges from the same vertex — simply does not occur at that position, and with only six neighbours for each vertex there is not enough room for every pattern to occur everywhere.

The half of the residues that are squares are scattered in a way that behaves, for many purposes, like the heads in a sequence of fair coin tosses. That is the point of the construction: to get the combinatorial effect of a random graph from a rule that can be written down and checked.

Every request, checked #

Checking that a graph is $k$-extending means trying every request with $|U| + |V| = k$ — every choice of $k$ vertices and every way of splitting them into $U$ and $V$ — and finding a witness for each. For a graph on 89 vertices and $k = 4$ that is over thirty-two million requests. The Paley graph makes the check far cheaper, because adding a constant to every residue preserves differences and so preserves the graph. Any request can be moved to one containing 0, and only those need checking.

The table is the whole answer within its range. The Paley graph on 5 residues, a pentagon, fails requests of two; from 13 residues on, every request of two is answered. Requests of three first succeed at 29, and requests of four at 89. In each row, once a prime succeeds every larger prime in the table succeeds too.

The general theorem says more and less. Using André Weil’s bound on character sums, Andreas Blass, Geoffrey Exoo and Frank Harary, and independently Béla Bollobás and Andrew Thomason, proved in 1981 that the Paley graph on $q$ residues is $k$-extending whenever $q$ is larger than about $k^2 4^k$. That bound — 64, 576 and 4,096 for $k = 2$, 3 and 4 — is a guarantee for every prime above it, and it is far above where the Paley graphs actually start succeeding. The Weil bound treats the squares as if they could conspire as badly as its error term allows; in fact they are much better behaved.

The request seventeen cannot answer #

The graphs that fail are worth looking at, because their failures are not random.

The 17-vertex Paley graph fails a request that looks innocent: find a vertex joined to each of 0, 1 and 2. The squares modulo 17 are 1, 2, 4, 8, 9, 13, 15 and 16, so 0, 1 and 2 are mutually joined — they form a triangle — and a witness would complete it to four mutually joined vertices. The Paley graph on 17 residues contains no such four. It also contains no four mutually unjoined vertices, and that pair of facts is famous: it is the colouring of the edges among seventeen people with no four mutual friends and no four mutual strangers, which shows that the Ramsey number $R(4, 4)$ is greater than 17.

So the graph’s failure to be 3-extending and its fame in Ramsey theory are the same fact. A $k$-extending graph contains every graph on $k + 1$ vertices, since the witnesses can build any pattern one vertex at a time; a graph that avoids a four-vertex clique cannot be 3-extending. The Paley graph on 17 residues is extreme in exactly the way that forbids it from answering every request.

Coins do worse #

A random graph on the same number of vertices, each pair joined by a fair coin, is the thing the Paley graph imitates. At these sizes the imitation is better than the original.

Every Paley graph from 29 vertices on answers every request of three. The coin-toss graphs of the same sizes fail, every one of twenty, up to 89 vertices, and at 113 only twelve of twenty pass. The random construction does guarantee success eventually — with probability tending to one once the number of vertices is large compared with $k^2 2^k$ — but at the sizes drawn it is outclassed by a rule about squares. The comparison is fair to the coins: every coin-toss graph drawn has the same number of vertices as its Paley rival and the same expected number of edges, and the same exhaustive check is run on it, without the translation shortcut, which the random graphs do not allow. The difference is in how the edges are placed, not in how many there are.

The reason is in the counts. For each request of three, about one eighth of the other 98 vertices should be witnesses — a little over twelve — and in both graphs the average is right. But the Paley graph’s counts are bunched tightly, between 10 and 15 for every request, while the coin-toss graph’s spread from 1 to 29. A request fails when its count reaches zero, and it is the long lower tail of the random distribution that reaches zero first. The squares modulo a prime are not random; they are more evenly spread than random, and the evenness is what the Weil bound measures, crudely, and what the table measures exactly.

A graph that looks the same from everywhere #

The Paley graph has far more symmetry than translation. Multiplying every residue by a nonzero square also preserves the graph, since it multiplies every difference by a square and a square times a square is a square. So the maps $x \mapsto ax + b$, with $a$ a square, are all automorphisms: the graph looks the same from every vertex and along every edge.

Multiplying by a non-square does something stranger. It sends squares to non-squares, so it maps the graph onto its own complement: the Paley graph is self-complementary. A request $(U, V)$ in the graph becomes the request $(V, U)$ in the complement, and so, pulled back, a request of the same shape with the roles of joined and unjoined exchanged. That is why the table’s rows do not have to distinguish requests by how many vertices are in $U$ and how many in $V$: a Paley graph answers every request with $|U| = a$, $|V| = b$ exactly when it answers every request with $|U| = b$, $|V| = a$.

Rado’s graph shares both properties. It is also self-complementary, and its automorphism group also acts transitively on vertices and on edges — both consequences of the back-and-forth argument that makes it unique. The Paley graphs are finite objects with the same symmetries as the infinite one, which is part of why they imitate it so well.

Why the squares are so even #

The number of witnesses for a request is a sum over residues of products of terms that say whether each difference is a square. Writing “is a square” as $\tfrac12(1 + \chi)$, where $\chi$ is the Legendre symbol, turns the count into its expected value, $q/2^k$, plus a combination of sums of products of shifted Legendre symbols. Weil’s theorem bounds each such sum by a small multiple of $\sqrt q$, and that is where $k^2 4^k$ comes from: the error must be smaller than the main term for every request at once.

A coin-toss graph has no such bound. Its witness counts are sums of independent coins, with standard deviation about $\sqrt{q}/2^{k/2}$ as well, but with nothing to stop a few of the millions of requests from landing far in the tail. The Paley graph’s counts are deterministic, and every one of them obeys the same bound. Among millions of requests, a guarantee for every one of them beats a typical deviation for most of them, and that is why the table’s thresholds are so much lower than the random ones.

Other ways to build a small one #

Paley graphs are one construction among several. The smallest 2-extending graph of all is known: it has nine vertices, and it is the Paley graph built on the field of nine elements, which is not a prime field. For three and more, the smallest $k$-extending graphs are not known. For three, computer searches and explicit constructions pin the minimum between two bounds that have not met, and in general counting arguments show it cannot be much smaller than a constant times $k 2^k$.

Constructions from finite geometries and from designs compete with the Paley graphs at every size, and each beats the random construction by a constant factor or so in the number of vertices. None beats it by more. The question is the finite shadow of the uniqueness of Rado’s graph: infinitely many requests are answered by one graph, and finitely many need a graph of a size nobody can pin down.

Requests as sentences #

Each extension requirement is a sentence of first-order logic about graphs. “For every two vertices $u$ and $v$ there is a vertex joined to $u$ and not to $v$” is one such sentence, and the full list, one sentence for each pair of sizes $(|U|, |V|)$, is the theory whose only countable model is Rado’s graph. A $k$-extending graph satisfies the sentences of that list up to size $k$ and possibly fails the rest.

That makes the table a table of which axioms each finite graph satisfies, and it connects to the zero–one law. Any single first-order sentence true in Rado’s graph is a consequence of finitely many extension sentences, so it holds in every graph that is $k$-extending for a large enough $k$ — including every Paley graph beyond the corresponding threshold. The Paley graphs therefore satisfy every first-order sentence about graphs that holds in almost every large random graph, provided the prime is large enough for that sentence. This was the point of Blass, Exoo and Harary’s paper: explicit, deterministic graphs that obey the same first-order laws as the infinite random graph, in a setting where, as with structures that obey the same rules in two different ways, the sentences cannot tell the finite model from the infinite one.

What the sentences cannot express is the thing the table measures: the smallest prime at which a given sentence becomes true. First-order logic sees each graph as a model or not a model; it has no way to say “for primes above 89”, and the thresholds are a fact about the squares, not about the logic.

What the search cannot show #

The table is exhaustive over its primes: every request of two, three and four vertices is tried, and the translation that moves requests to 0 is exact, because adding a constant is an automorphism of the Paley graph. What it cannot show is the behaviour of primes beyond 113. That every larger prime succeeds for $k \le 4$ follows from the Weil-bound theorem only above its threshold, which for $k = 4$ is 4,096; between 113 and that threshold, the table’s pattern is evidence, not proof.

The coin-toss comparison uses twenty seeded graphs at each size, and a different set of seeds would give different counts. The claim it supports is the qualitative one — random graphs of these sizes usually fail where Paley graphs pass — and not any particular percentage.

Still open: the smallest extending graph #

The smallest number of vertices a $k$-extending graph can have is known for $k = 1$ and $k = 2$ and for no larger $k$. The random construction shows it is at most about $k^2 2^k$; counting arguments show it is at least about $k 2^k$; and the best explicit constructions, Paley graphs among them, sit near the upper end. Whether the true answer grows like $k 2^k$, like $k^2 2^k$, or somewhere between is not known.

The Paley graphs themselves carry an open question too. Their thresholds in the table — 13, 29, 89 — are far below $k^2 4^k$, and the exact threshold for each $k$ can only be found by search, which becomes infeasible quickly. Whether the true threshold grows like $4^k$, as the Weil argument suggests it might have to, or like $2^k$ times a polynomial, as the random construction would, is not settled.

What a finite graph can say #

A $k$-extending graph satisfies the sentences of Rado’s theory that only ever ask about a few vertices at a time — a finite model of a finite part of an infinite theory, which is the same move compactness makes, run in reverse. The Paley graphs build such models from nothing but the squares modulo a prime, and they build them earlier than coins do, because the squares are not random: they are spread too evenly to leave a request unanswered. Where they fail, as at 17, the failure is a famous piece of order in its own right.