Department of
Applied
Mathematics

Covering lattice points by subspaces and counting point-hyperplane incidences

Martin Balko

Abstract

(joint work with J. Cibulka and P. Valtr)

Let d and k be integers with 1 <= k <= d-1. Let Lambda be a d-dimensional lattice and let K be a d-dimensional compact convex body symmetric about the origin. We provide estimates for the minimum number of k-dimensional linear subspaces needed to cover all points in the intersection of Lambda with K.

In particular, our results imply that the minimum number of k-dimensional linear subspaces needed to cover the d-dimensional n x ... x n grid is at least Omega(n^(d(d-k)/(d-1)-epsilon)) and at most O(n^(d(d-k)/(d-1))), where epsilon > 0 is an arbitrarily small constant. This nearly settles a problem mentioned in the book of Brass, Moser, and Pach.

We also find tight bounds for the minimum number of k-dimensional affine subspaces needed to cover the intersection of Lambda and K. We use these new results to improve the best known lower bounds for the maximum number of point-hyperplane incidences by Brass and Knauer.