The sizes at which a sentence can come true

There is a relation such that ended its account of Fagin’s theorem with the oldest question in the subject, Heinrich Scholz’s of 1952. Take a sentence of first-order logic about a relation — “every point is related to exactly one other”, say — and ask at which finite sizes some relation makes it true. The set of those sizes is the sentence’s spectrum, and the essay recorded what is known about spectra as a class: they are exactly the sets of numbers that a machine can recognise in nondeterministic exponential time, and whether the complement of a spectrum is always a spectrum is open.

That is a statement about all spectra at once. This essay measures particular ones, and the measurement turns out to have a fixed shape. A spectrum can be computed one size at a time by searching every structure of that size, and for small sizes the search is quick. But a spectrum is an infinite set, and no amount of searching reaches the end of it. Every spectrum below was finished by a proof, and the interesting thing is how different the proofs have to be.

A sentence that counts to two #

The first sentence is the plainest: every point is related to exactly one point other than itself, and the relation is symmetric. In first-order logic that is “for every $x$ there is a $y \ne x$ with $R(x, y)$, and for every $z$ with $R(x, z)$, $z = y$”, together with symmetry. A structure satisfying it is a graph in which every point has exactly one neighbour, which is a perfect matching, and a perfect matching exists exactly when the number of points is even.

So the spectrum is the even numbers. That is worth a second look, because a game that decides what can be said proves that no first-order sentence about a bare set can say “the set has an even number of elements”: two large enough sets look identical to any sentence of bounded quantifier depth. The matching sentence gets around that by asking for a relation, and the spectrum is a question about whether a relation exists — an implicit second-order quantifier of exactly the kind Fagin’s theorem is about. The sentence is first-order; the spectrum is where the guessing happens.

The figure’s first row is the even numbers, every one of them filled solid: a matching on $2m$ points is written down at once, and on an odd number the pairing argument is a proof in a line.

Every two points with exactly one friend in common #

The second sentence is the friendship condition: every two distinct points have exactly one common neighbour. Read as people and friendships, it describes a society in which any two people have exactly one mutual friend.

One family of examples is easy to find. Take a centre and arrange the others in pairs, joining each pair to each other and to the centre: a windmill of triangles sharing one point. Two points in the same blade have the centre as their only common neighbour; a blade point and the centre have the blade partner; two points in different blades have the centre. The windmill has $2k + 1$ points for $k$ blades, so every odd size is in the spectrum.

The search asks whether there is anything else, and it asks it of every graph. On $n$ points there are $2^{n(n-1)/2}$ labelled graphs — $2^{28}$, about 268 million, on eight — so the search builds them a point at a time and abandons a partial graph the moment two of its points already share two neighbours, since adding points never takes a common neighbour away. That pruning is what makes eight points quick: the tree of partial graphs the search actually visits is a few million nodes, against the 268 million graphs it accounts for.

What it finds is exactly the windmills. At three points there is one graph, the triangle; at five, fifteen labelled graphs, which is five choices of centre times three ways to pair the remaining four; at seven, 105, which is seven centres times fifteen pairings. At two, four, six and eight points there is nothing, because a windmill has an odd number of points and nothing else satisfies the sentence. The spectrum is the odd numbers, and to eight points the computation has checked not only the sizes but the structures.

The proof that reaches past the search #

Eight is not infinity, and the statement that every friendship graph is a windmill — so that the spectrum is the odd numbers and nothing else — is the friendship theorem of Paul Erdős, Alfréd Rényi and Vera Sós, from 1966. Its proof has two halves, and only the second needs anything beyond counting.

The first half shows that a friendship graph either has a point joined to every other point, in which case it is a windmill at once, or is regular: every point has the same number $k$ of neighbours. The argument takes two points that are not joined, pairs each neighbour of one with its unique common neighbour with the other, and checks that this pairing is a bijection, so the two degrees are equal; a short case analysis spreads the equality to every pair. Counting the walks of length two from one point then gives the size, $n = k(k-1) + 1$.

The bijection is worth seeing once, because it is the only place the hypothesis is used with any subtlety. Let $u$ and $v$ be two points that are not joined. Each neighbour $x$ of $u$ has exactly one common neighbour with $v$, call it $f(x)$, and $f(x)$ is a neighbour of $v$. If two neighbours $x$ and $x'$ of $u$ had the same image $y$, then $u$ and $y$ would have two common neighbours, $x$ and $x'$ — unless $y = u$, which cannot happen since $u$ and $v$ are not joined. So $f$ is one-to-one from the neighbours of $u$ into the neighbours of $v$, and the same argument run backwards gives a map the other way, so the two degrees agree. Any two points that are not joined have equal degree, and when no point is joined to everything that is enough, with one more short step, to make every degree equal.

The size follows by counting walks. From a fixed point, its $k$ neighbours each have $k - 1$ further neighbours, giving $k(k - 1)$ walks of length two that do not return; every other point, the start’s own neighbours included, is the end of exactly one of them, since it has exactly one common neighbour with the start. So the points other than the start number $k(k-1)$, and $n = k(k-1) + 1$.

The second half is the eigenvalue count that the figure draws. Write the graph’s adjacency matrix $A$: the friendship condition says that $A^2$ has $k$ on its diagonal and 1 everywhere else, so $A^2 = (k - 1)I + J$, where $J$ is the matrix of ones. That pins down the eigenvalues — $k$ once, and $\pm\sqrt{k-1}$ on all the others — and the trace of $A$ is zero, since no point is its own neighbour. So the eigenvalues sum to zero: $k$ plus a whole number of copies of $\sqrt{k-1}$, which forces $k / \sqrt{k-1}$ to be a whole number.

It almost never is. If $k - 1$ is not a perfect square, the ratio is irrational; if $k - 1 = s^2$, the ratio is $(s^2 + 1)/s$, which is whole only when $s$ divides 1. So $s = 1$ and $k = 2$, and the graph has three points: the triangle, which has a point joined to every other and is a windmill after all. The dots in the figure are that ratio, and the labelled ones are the squares, $k = 5, 10, 17, 26, 37$, each falling between two gridlines.

This is the trick that settles Moore graphs too, and as many points as two steps allow runs it there with a different matrix identity, ending with degrees 2, 3, 7 and possibly 57. The friendship version is the cleaner one because the eigenvalue condition leaves no survivors except the degenerate case.

Seven players, every pair beaten #

The third sentence is about tournaments — relations in which, for every two distinct players, exactly one beats the other. It says: for every two players, some third player beats both. Kurt Schütte asked whether tournaments with this property exist at all, and Erdős answered in 1963 that they do, for every version of the question, with a count rather than an example.

The smallest example is drawn. Put seven players round a circle and let player $i$ beat $i + 1$, $i + 2$ and $i + 4$, counted round the circle. The numbers 1, 2 and 4 are the squares in arithmetic modulo 7, and they have a property that does all the work: every non-zero remainder modulo 7 is the difference of two of them in exactly one way. So for two players $a$ and $b$ there is exactly one player $w$ for whom both $a - w$ and $b - w$ are squares, and that $w$ beats both. Every pair has a common conqueror, and in fact exactly one.

The same three numbers are the lines of the Fano plane, where $\{i + 1, i + 2, i + 4\}$ for $i = 0, \dots, 6$ are its seven lines and the unique-difference property is the statement that two points lie on one line. The tournament and the plane are one structure read two ways, which is the same arithmetic that the squares that answer every request uses to give Paley graphs their extension property.

The search says seven is the least. Every tournament on two to six players fails — the search tries all $2^{15} = 32{,}768$ labelled tournaments on six players and finds that each leaves some pair unbeaten — and among the $2^{21} = 2{,}097{,}152$ on seven, exactly 240 succeed. That is $7! = 5{,}040$ relabellings of the circle tournament divided by its 21 symmetries, so on seven players the circle tournament is the only one. George and Esther Szekeres proved in 1965 that seven is the least, and that nineteen is the least for the sentence one quantifier longer, in which every three players have a common conqueror.

Searching the middle and counting the rest #

Seven is in the spectrum, and the figure at the top has every size after it filled. The fills from 8 to 20 are each a tournament found by search, and the ones from 21 on are a proof, and the second figure of tournaments shows why the proof has to wait until 21.

The search for a single tournament at each size is a local one: start from coin tosses, and flip one game at a time, keeping the flip whenever it does not increase the number of pairs no third player beats. From 7 to 20 players it reaches zero at every size. The sizes it finds are not in doubt — each tournament is checked pair by pair — but finding is all the search does; it says nothing about 21.

Erdős’s argument covers every size from 21 on with a single calculation. Decide every game by a fair coin. A given pair of players is beaten by a given third player with probability one quarter, so it escapes all $n - 2$ of the others with probability $(3/4)^{n-2}$, and the expected number of pairs that nobody beats is

$$\binom{n}{2}\left(\tfrac{3}{4}\right)^{n-2}.$$

When that expectation is below one, some tournament must have no such pair at all, since a count that is a whole number in every tournament cannot average below one unless it is zero in some. The expectation is 1.07 at 20 players and 0.89 at 21, and it falls from there for ever.

The argument is the same one that makes coin-toss graphs answer every finite request: a property that each small configuration fails only with exponentially small probability is enjoyed by almost every random structure once there are enough points to make the exponential beat the number of configurations. Here the configurations are the $\binom{n}{2}$ pairs and the failure probability is $(3/4)^{n-2}$, and the crossover is 21. The method proves existence and gives nothing to look at, which is why the figure needs the search for the sizes below it — and why the circle tournament, which is an object rather than an average, is the more informative answer at seven.

So the spectrum is 1 and every number from 7 on, and it took three methods to show it: exhaustive search below seven, a construction or a search from seven to twenty, and a count from twenty-one. The figure’s bars show the share of random tournaments with the property, which rises from almost none at nine players to 89 per cent at thirty, always above the floor the count guarantees.

What a search can say about a spectrum #

The three sentences fit a pattern that holds for spectra in general.

A search decides one size, and it decides it completely. For a sentence with a fixed vocabulary, the structures of size $n$ are finitely many, so whether $n$ is in the spectrum is decidable for each $n$ — and that is the whole of Jones and Selman’s characterisation seen from below: a spectrum is a set of numbers that a nondeterministic machine recognises by guessing a structure and checking the sentence in it, and the time is exponential in the number of digits because a structure on $n$ points has size polynomial in $n$.

A search cannot decide the spectrum. It says nothing past its last size, and the three sentences show that the last size searched carries no information about the next: the friendship sentence alternates for ever, the tournament sentence fails six times and then never again, and neither pattern is visible to a search that stops at four.

What finishes a spectrum is a proof, and its kind depends on the sentence. The matching sentence needed a pairing argument; the friendship sentence needed a structure theorem — every model is a windmill — that was finished by linear algebra; the tournament sentence needed an existence argument that never exhibits a tournament on 21 players. Spectra in general can be as hard as any set of numbers recognisable in nondeterministic exponential time, so there is no uniform method, and the variety here is a small sample of it.

And spectra combine. The conjunction of two sentences in different relation symbols has the intersection of their spectra, and the disjunction has the union, so the sets above can be combined freely: the evens intersected with the tournament spectrum is every even number from 8 on. Whether the complement of a spectrum is always a spectrum — whether “the sizes at which the friendship sentence fails” is the spectrum of some sentence — is Asser’s question, which the account of Fagin’s theorem recorded as open. For the three sentences here the complements happen to be spectra, the evens and odds of each other, and the finite set $\{2, \dots, 6\}$, which any sentence fixing the size can describe.

Why the search cannot simply be made larger #

The labelled structures on $n$ points number $2^{n(n-1)/2}$ for graphs and the same for tournaments, so each extra point multiplies the work by $2^{n}$. Eight points is 268 million graphs and nine is 69 billion. The friendship search reaches eight only because its pruning is sound — a partial graph in which two points share two neighbours can never be repaired, since adding points and edges only adds common neighbours — and a pruned search that comes back empty is itself a proof, in the precise sense a failed search is a proof gives the phrase.

The tournament sentence has no comparable pruning. Whether a pair is beaten by some third player can change with every game still to be decided, so a partial tournament is never hopeless until it is complete, and the brute force stops at seven players, two million tournaments. Symmetry would help — the search counts every relabelling separately, 5,040 copies of the one tournament on seven players — and a search that generated one tournament from each class of relabellings would go a few sizes further. It would not go to 47.

What the figures cannot show #

The friendship search runs to eight points and the tournament search to seven, and both are exhaustive at those sizes: every labelled structure is accounted for, either visited or pruned for a reason that cannot be undone by adding points. The tournament counts on seven players are a brute-force pass over all two million tournaments, and the 240 is checked against the arithmetic of relabellings rather than trusted.

The tournaments found from 8 to 20 are certificates and are each verified, but the local search that found them is a heuristic; had it failed at some size, the figure would have had to say “not found” rather than “not in the spectrum”. It did not fail.

The random shares are estimates from 600 tournaments at each size, so each bar carries a sampling error of a few per cent. They are drawn to show the shape — rare, then usual — and the claim that every size from 21 on is in the spectrum rests on the count, not on the bars.

Still open: one more player in the sentence #

The tournament sentence has a family of longer relatives: every $k$ players are all beaten by some other player. Erdős’s count shows each has a spectrum containing every large enough size, and the question is where it starts. For $k = 1$ the least size is 3, for $k = 2$ it is 7, and for $k = 3$ it is 19, by the Szekeres proof.

For $k = 4$ it is not known. The least size is at least 47, by a counting argument of the Szekeres type, and at most 67, where the residue tournament modulo 67 is known to work. Every size in between is a finite question, and the search space at 47 players is $2^{1081}$ tournaments; the gap is open because no argument yet cuts that down to something a search can finish, and because the residue tournaments that work so well for small $k$ do not exist at every size.