Concept

Paley graph

The graph on the residues modulo a prime of the form 4k + 1, with two residues joined when their difference is a square. It is half-dense, highly symmetric and behaves in many ways like a random graph.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

17 points coloured by whether their difference is a square. 17 points on a circle with every pair joined, coloured by whether the difference of their labels is a square modulo 17; the largest set of points all joined by one colour has 3 members.

Eighteen people, and the seventeen that escape

Among any eighteen people, four are mutual acquaintances or four are mutual strangers. Seventeen can be arranged so that neither happens, and the arrangement is not a lucky find — it is a rule about squares.

discrete · Ramsey theory

Which Paley graphs answer every small request. size 2: first passes at 13; size 3: first passes at 29; size 4: first passes at 89; primes checked up to 113.

The squares that answer every request

Rado's graph has, for any finite sets U and V, a vertex joined to all of U and none of V. A finite graph can only answer the small requests, and the Paley graphs — residues modulo a prime, joined when their difference is a square — are the classic way to build one. Checking every request exactly finds the thresholds: 13 residues answer every request of two, 29 every request of three, 89 every request of four. The theorem that guarantees it asks for 64, 576 and 4,096. Coin-toss graphs of the same sizes almost never manage it.

logic · Models

Named alongside it

The objects these essays reach for when they reach for this one.

Quadratic residue Ramsey number Complete graph Counting argument Existence proof Extension property Graph Induction Modular arithmetic Pigeonhole principle Rado graph Random graph

All concepts