Abstract
In this article we extend Alon’s Nullstellensatz to functions which have multiple zeros at the common zeros of some polynomials g 1,g 2, …, g n , that are the product of linear factors. We then prove a punctured version which states, for simple zeros, that if f vanishes at nearly all, but not all, of the common zeros of g 1(X 1), …,g n (X n ) then every residue of f modulo the ideal generated by g 1, …, g n , has a large degree.
This punctured Nullstellensatz is used to prove a blocking theorem for projective and affine geometries over an arbitrary field. This theorem has as corollaries a theorem of Alon and Füredi which gives a lower bound on the number of hyperplanes needed to cover all but one of the points of a hypercube and theorems of Bruen, Jamison and Brouwer and Schrijver which provides lower bounds on the number of points needed to block the hyperplanes of an affine space over a finite field.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon: Combinatorial Nullstellensatz, Combin. Probab. Comput.8 (1999), 7–29.
N. Alon and Z. Füredi: Covering the cube by affine hyperplanes, European J. Combin.14 (1993), 79–83.
S. Ball: On intersection sets in Desarguesian affine spaces, European J. Combin.21 (2000), 441–446.
A. E. Brouwer and A. Schrijver: The blocking number of an affine space, J. Combin. Theory Ser. A24 (1978), 251–253.
A. A. Bruen: Polynomial multiplicities over finite fields and intersection sets, J. Combin. Theory Ser. A60 (1992), 19–33.
M. Cámara, J. Moragas and A. Lladó: On a Häggkavist’s conjecture with the polynomial method, Electr. Notes in Discrete Math.29 (2007), 559–563.
W. Fulton: Algebraic Curves, Benjamin, 1969.
D. Hefetz: Anti-magic graphs via the combinatorial Nullstellensatz, J. Graph Theory50 (2005), 263–272.
R. Jamison: Covering finite fields with cosets of subspaces, J. Combin. Theory Ser. A22 (1977), 253–266.
Gy. Károlyi: A compactness argument in the additive theory and the polynomial method, Discrete Math.302 (2005), 124–144.
A. Kézdy: ρ-valuations for some stunted trees, Discrete Math.306 (2006), 2786–2789.
T. G. Ostrom and F. A. Sherk: Finite projective planes with affine subplanes, Canad. Math. Bull.7 (1964), 549–559.
U, Schauz: Colorings and orientations of matrices and graphs, Electron. J. Combin.13 (2006), 12 pp.
Z-W. Sun and Y-N. Yeh: On various restricted sumsets, J. Number Theory114 (2005), 209–220.
Author information
Authors and Affiliations
Corresponding author
Additional information
The first author acknowledges the support of the Ramon y Cajal programme of the Spanish Ministry of Science and Education.
Both authors acknowledge the support of the projects MTM2005-08990-C02-01 and MTM2008-06620-C03-01 of the Spanish Ministry of Science and Education and the project 2005SGR00256 of the Catalan Research Council.
An erratum to this article is available at http://dx.doi.org/10.1007/s00493-011-2837-7.