Polynomial Methods for Grid Covering Problems

Master thesis (2024)

Authors

L.K.M. Verlinde Electrical Engineering, Mathematics and Computer Science

Contributors

C.E. Groenland Discrete Mathematics and Optimization - EEMCS (mentor)
A. Bishnoi Discrete Mathematics and Optimization - EEMCS (mentor)
Dion Gijswijt Discrete Mathematics and Optimization - EEMCS (mentor)
J.M.A.M. van Neerven Analysis - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
More Info
expand_more

Published Date

21-06-2024

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

Consider an arbitrary finite grid in some field. How many hyperplanes are required so that every point is contained in at least k hyperplanes, except for one point that is not allowed to be contained in any hyperplane? To solve this so-called hyperplane grid covering problem, the polynomial method has proven to be extremely useful in finding bounds on the minimum number of hyperplanes required. This has given rise to a second problem: the polynomial grid covering problem. This problem considers the minimum degree of a polynomial such that every grid point is a root with multiplicity k, except for one point where the polynomial does not vanish. We study these two related problems for multiple grids: the hypercube, the vector space over the binary field and grids in the Cartesian plane. Since polynomial covers in the latter have not been studied before, we provide algorithms and techniques to study these covers. We also explore the link between grid coverings and two results from algebraic geometry: the Footprint Bound and the Cayley-Bacharach Theorems.