Rich line covering bound over a finite field
ID: rich-line-covering-bound-over-a-finite-field
Suppose every point of lies on an affine line in a vector space meeting a subset in at least points, with . A smaller would admit a nonzero multivariate polynomial of total degree at most vanishing on it, by the dimension of a bounded-total-degree polynomial space. Each selected line then has more roots of a polynomial than the degree of its restriction, so the polynomial vanishes at every point. The Schwartz-Zippel lemma forbids this because . Thus the displayed bound holds, and is at least . This is a point-covering condition; the finite-field Kakeya set condition instead quantifies over directions.
New to topics? Read the docs here!