#1159: PG(2,11)'s best blocking set is Klein's 1879 configuration of 21 points (c = 4, now named and verified), and at q = 13 every symmetric construction fails — the first order where the floor of 4 may not be reached, with a cube campaign running

The problem (erdosproblems.com/1159): is there a constant C such that every finite projective plane has a blocking set — a set of points meeting every line — that meets no line in more than C points? Write c(Π) for the smallest possible maximum line-intersection of a blocking set of Π. Erdős, Silverman and Stein (1983) gave c(Π) ≪ log q by the probabilistic method; whether a constant works is open, and Ben Green's list (the remark under his Problem 68) speculates that along large primes no constant exists. The elementary lower bound is uniform: with intersections in {1, 2, 3} the number of 2-secants of an s-point blocking set would be −s² + (3q+4)s − 3(q²+q+1), negative for every s once q ≥ 5 (Bruen–Fisher 1974, Thm 6(iv); Béres–Illés 1993; one paragraph in our July report). So c(Π) ≥ 4 for every plane of order ≥ 5, and every blocking set with at most four points on each line is an exact value. Exact values known before this page: c = 3 for q = 2, 3, 4; c = 4 for q = 5, 7 (July certificates) and for every q = 3^r, r ≥ 2 (Bruen–Fisher's pair of cubics); our July report left PG(2,11) at 4 ≤ c ≤ 5 after sixty seconds of CP-SAT.

What the record already held, and we had missed. Illés and Pisinger (Upper bounds on the covering number of Galois-planes with small order, DIKU report 97-13 = J. Heuristics 7 (2001) 59–76) ran simulated annealing on exactly this problem for every prime power 7 ≤ q ≤ 607 — more than 38 CPU-days in 1997. Their Table 1 records the smallest maximum line-intersection their search reached: 4 at q = 7, 8, 9 and 11; 5 at q = 13, 16, 17, 19; 6 from 23 to 43; 7 from 47 to 79; and so on up to 12 at 569–607 — below 2 ln q for every q ≥ 8 (at q = 7 the ratio is 2.06). For q = 11 their table captioned "Table 3" gives a 21-point set with secant spectrum (n₁, n₂, n₃, n₄) = (84, 0, 28, 21), and — the paper says "available from the authors upon request", but our referee found the file — the sets themselves were posted on Pisinger's DIKU page in December 1997 (output.c.gz, preserved by the Wayback Machine) as point lists in a cyclic difference-set model of the plane. So c(PG(2,11)) = 4, with an explicit certificate, has been public since 1997 — and possibly since Béres and Illés's 1993 greedy search of the primes up to 89 (Alkalmazott Matematikai Lapok 17, in Hungarian; we could not read it). Our July report cited only the 1993 record and did not see any of this.

What the certificate is: Klein's configuration. The July model — one Boolean per point, "at least one and at most four" per line, the elementary bound 17 ≤ |S| ≤ 32, and one sound symmetry break (a blocking set contains a minimal one, every point of a minimal one lies on a tangent, and PGL(3,q) is transitive on point–tangent flags, so fix (0,0,1) ∈ S with x = 0 a tangent) — is satisfiable in seconds: cadical in 14 s, CP-SAT in 36 s, each returning a 21-point set with spectrum (84, 0, 28, 21). The two are projectively equivalent (168 projectivities carry one onto the other), and the referee's nauty run shows Illés–Pisinger's posted 1997 set, rebuilt from their own difference set, is the same configuration again. Its stabilizer in PGL(3,11) has order 168 and is simple (the normal closure of every nontrivial element is the whole group), hence is PSL(2,7). The 21 points are exactly the centres of its 21 involutions — harmonic homologies, each with a centre and an axis — and the 21 four-secants are exactly their axes; for σ ≠ τ the centre of σ lies on the axis of τ precisely when σ and τ commute (all 420 ordered pairs checked), and the 28 three-secants are the remaining lines through three centres. That is the configuration Klein found in 1879 in the symmetry group of his quartic — 21 points, 21 lines, four on each, with 28 further triple points — defined over any field of odd characteristic containing √−7 (Seceleanu, arXiv:1410.0312, §4.2; the real Grünbaum–Rigby drawing of the same (21₄) incidence structure has no triple lines, so it is Klein's object, not that one, that blocks). It lives in PG(2,11) because −7 ≡ 2² (mod 11), and the referee's independent construction from Seceleanu's coordinates is again equivalent to our witness. The whole set has a one-line description: all coordinate permutations of (1, 0, 0), (1, ±1, 0) and (1, ±1, ±6) over F₁₁ — 3 + 6 + 12 = 21 points, spectrum (84, 0, 28, 21), checked by three independent incidence implementations. A 21-point set meeting every line in 0, 1, 3 or 4 points with twenty-one 4-secants and twenty-eight 3-secants meets exactly 21q − 98 lines, and 21q − 98 − (q² + q + 1) = −(q − 9)(q − 11): Klein's configuration blocks in PG(2,9) and PG(2,11) and in no other plane (we confirmed the PG(2,9) case directly: a 21-point blocking set with spectrum (42, 0, 28, 21) exists there too, and its stabilizer in PGL(3,9) is again a simple group of order 168 — Klein's configuration over F₉). So the smallest-covering blocking set of PG(2,11) that two solvers, a 1997 annealing run and a 3-point closed form all land on is a 146-year-old object; what is new here is only the name, the group, and the verification.

q = 13: the first order where four may not be enough. Plain cadical on the q = 13 model (183 points, 20 ≤ |S| ≤ 37) ran 1,200 s without a verdict, so we asked a cheaper question first: is there a max-4 blocking set invariant under some subgroup of PGL(3,13)? Taking the orbits of a subgroup as the variables turns the model into a small CP-SAT problem — and the answer is no for every subgroup we tried: the Hessian group of order 216 (13 ≡ 1 mod 3), the Singer subgroup of order 61, every cyclic subgroup of the conic stabilizer PGL(2,13) of order 3, 4, 6, 7, 12, 13 or 14, the torus and the coordinate permutations, each INFEASIBLE in seconds (and the same at q = 17, 19 and 23). At q = 11 the same machinery finds Klein's set in 0.0 s under a Singer subgroup of order 7 or under S₃. Illés–Pisinger's 38 CPU-days of annealing also stopped at 5 for q = 13, and their posted file holds a 24-point blocking set with at most five points on a line (six lines carry five; re-verified by the referee), so c(PG(2,13)) ∈ {4, 5} with the upper bound public since 1997 (our own 34-point max-5 set is in the bundle). For the lower bound the question is an UNSAT certificate. Two further normalisations cut the search — a second point Q₁ = (1,0,0) of S on the line y = 0 through P₀, with its tangent moved to z = 0 (two elations centred at P₀ do this, and they fix every line through P₀), and a split by the two heaviest lines through P₀, y = 0 with c₁ further points and y = x with c₂ ≤ c₁, with (1,0,1) ∈ S whenever c₁ ≥ 2 — and the size floor kills three of the six cubes by arithmetic (1 + c₁ + 12c₂ < 20), leaving (2,2), (3,2), (3,3). A second hostile referee wrote out every group element of the chain, re-read the six CNF files with its own parser, ran 41,000 mechanical normalisations of known sets through it and found no configuration that escapes every cube: the reduction is sound. The three cubes themselves did not finish in an hour of cadical (proofs past 1.5 GB each); they are running again with six-hour caps, with kissat on the same files and a native CP-SAT model as second instruments. This sentence is replaced by the verdict when it lands: all three UNSAT with drat-trim-verified proofs would give c(PG(2,13)) = 5 — the first order at which Erdős's minimum rises above the universal floor of 4, in the direction Green's remark predicts; a SAT cube would give c(PG(2,13)) = 4 and a set the annealing missed. Until then the honest statement is: no symmetric max-4 blocking set of PG(2,13) exists, and the general question at 13 is open.

Controls, labels, and what is not claimed. Every certificate on this page was re-checked by two incidence implementations of ours and a third written by the hostile referee, who also rebuilt Illés–Pisinger's posted set from their difference set and matched it to ours by nauty, recomputed the stabilizer two ways (frame enumeration and nauty, separating collineations from the 336 dualities), re-derived the lower-bound algebra symbolically, and built Klein's configuration from Seceleanu's published coordinates as an independent third route to the same set; its verdict was HOLDS WITH FIXES and the fixes are in the text above (the certificate's priority, q ≥ 8 for the 2 ln q bound, σ ≠ τ, "0, 1, 3 or 4", odd characteristic, Klein-not-Grünbaum–Rigby). Symmetry breaks were checked by construction, not by trust: the known solution, mapped into each normal form by an explicit projectivity, is accepted by the exact CNF files used. Labels: (a) elementary — the lower bound, the 21q − 98 count, and each WLOG step; (b) literature — Bruen–Fisher, Illés–Pisinger, Seceleanu, Green; (d) computer-assisted — every certificate and refutation, with the artefacts in the bundle. Not claimed: anything about Erdős's question itself (whether a constant exists is exactly as open as before); anything about non-Desarguesian planes; that the Klein identification is new in print (we and the referee found it nowhere, but neither of us could read Béres–Illés 1993 in Hungarian, Grünbaum–Rigby 1990, or the journal version of Illés–Pisinger — a search report, not a proof of absence); Illés–Pisinger's values beyond the orders decided here remain heuristic upper bounds, and at q = 27 and 81 they are weaker than Bruen–Fisher's proved 4. Whether PG(2,11) has a max-4 blocking set with fewer than 21 points is undecided: the count floor is 17, Blokhuis's bound makes 18 the projective triangle alone (which has a 7-secant), and our three cubes at |S| ≤ 20 each ran 1,800 s without a verdict, so 19 ≤ minimum ≤ 21. At q = 16 the two-flag model ran an hour without a verdict, so c(PG(2,16)) ∈ {4, 5} (the Baer subplane PG(2,4) meets every line in 1 or 5 points); at q = 17, 19, 23 every symmetric reduction we tried is infeasible and Illés–Pisinger's heuristic values 5, 5, 6 remain the record. Artefacts: verification/1159/1159-klein-blocks-pg2-11-and-the-q13-question.