Warnings Second Theorem with Resricted Variables

We present a restricted variable generalization of Warnings Second Theorem (a result giving a lower bound on the number of solutions of a low degree polynomial system over a finite field, assuming one solution exists). This is analogous to Brinks restricted variable generalization of Chevalleys Theorem (a result giving conditions for a low degree polynomial system not to have exactly one solution). Just as Warnings Second Theorem implies Chevalleys Theorem, our result implies Brinks Theorem. We include several combinatorial applications, enough to show that we have a general tool for obtaining quantitative refinements of combinatorial existence theorems.

Martin Gardners minimum no-3-in-a-line problem

In Martin Gardners October, 1976 Mathematical Games column in Scientific American, he posed the following problem: What is the smallest number of [queens] you can put on a board of side n such that no [queen] can be added without creating three in a row, a column, or a diagonal? We use the Combinatorial Nullstellensatz to prove that this number is at least n, except in the case when n is congruent to 3 modulo 4, in which case one less may suffice. A second, more elementary proof is also offered in the case that n is even.