# Repeatedly applying the Combinatorial Nullstellensatz for Zero-sum Grids to
Martin Gardner’s minimum no-3-in-a-line problem

Seunghwan Oh, John R. Schmitt, Xianzhi Wang Department of Mathematics,
Middlebury College, Middlebury, VT 05753.Department of Mathematics, Middlebury
College, Middlebury, VT 05753. Supported in part by Fulbright Austria.
Corresponding author<EMAIL_ADDRESS>of Mathematics,
Texas A&M University, College Station, TX 77843-3368.

###### Abstract

In 1976 Martin Gardner posed the following problem: “What is the smallest
number of [queens] you can put on an [$n\times n$ chessboard] such that no
[queen] can be added without creating three in a row, a column, or a
diagonal?” The work of Cooper, Pikhurko, Schmitt and Warrington showed 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. When $n>1$ is odd, Gardner
conjectured the lower bound to be $n+1$. We prove this conjecture in the case
that $n$ is congruent to 1 modulo 4. The proof relies heavily on a recent
advancement to the Combinatorial Nullstellensatz for zero-sum grids due to
Bogdan Nica.

Keywords: Combinatorial Nullstellensatz, chessboard, zero-sum grid, Martin
Gardner

##  1 Introduction.

The 1976 Mathematical Games column in Scientific American (see Gardner [6],
Chapter 5, pg. 71) posed the question: What is the minimum number of counters
that can be placed on an $n\times n$ chessboard, no three in a line, such that
adding one more counter on any vacant square will produce three in a line?
This is the minimum no-3-in-a-line problem. There are different ways to
interpret ‘line’. We may take the word in its broadest sense, allowing for a
straight line of any orientation. In this case, we point the reader to the
recent work of Aichholzer, Eppstein, and Hainzl [1]. However, we restrict our
attention to when ‘line’ refers only to orthogonals and diagonals (as was also
done in [3]); this is the _queens version_ of the problem since it properly
relates to how a queen is permitted to move in a game of chess.

Figure 1 shows a $9\times 9$ chessboard with a placement of $10$ queens with
no three in a line. This placement is _maximal_ , that is, any additional
queen will create three in a line. For example, an additional queen placed in
the top left corner produces three in a line along the main diagonal. This
particular placement is also of minimum size (where size of a placement is the
number of queens in the placement), that is, there is no placement with nine
or fewer queens meeting the requirements.

9x9maxfield=i9, borderwidth=0.5mm, color=white, colorwhitebackfields,
color=white, markregion=a1-z24, showmover=false, hlabelwidth=18pt,
hlabellift=2pt [ labelbottom=true, labelleft=true, labelbottomformat= ,
labelleftformat= , style=9x9, setpieces=Qb7, Qb8, Qc8, Qc5, Qd4, Qd5, Qe6,
Qe7, Qf4, Qf6, padding=1ex, ]

Figure 1: An example of a maximal placement with $10$ queens on a $9\times 9$
board.

A history of the queens version problem is given in [3]111The published
version of this paper contains an editorial error in the abstract. The arxiv
version 2 corrects this error.. Here we offer a brief summary of known
results. Cooper, Pikhurko, Schmitt and Warrington [3] gave the following.

######  Theorem 1.

[Cooper, Pikhurko, Schmitt, Warrington [3]] For $n\geq 1$, the answer to
Gardner’s no-3-in-a-line queens version problem is at least $n$, except in the
case when $n$ is congruent to $3$ modulo $4$, in which case one less may
suffice.

An elementary, ad hoc proof in the case of $n$ even was given, yet the
approach only yielded a lower bound of $n-1$ when $n$ is odd. To obtain the
full result, the proof of Theorem 1 relied on Alon’s Combinatorial
Nullstellensatz (reproduced here as Theorem 3).222Alon’s seminal work [2]
contains many applications of this theorem, and these have served as a huge
inspiration to many, including ourselves. This inspiration continues into this
present paper.

Let $m_{3}(n)$ denote the answer to Gardner’s no-3-in-a-line queens version
problem on an $n\times n$ chessboard. Gardner knew the precise value of
$m_{3}(n)$ for small values of $n$, and a few more precise values were given
in [3]. Subsequently, Rob Pratt [10] framed the problem as an integer linear
programming problem and Don Knuth [8] brought the power of SAT-solvers to bear
on the problem. Their results are cumulatively stated as an entry in the On-
line Encyclopedia of Integer Sequences [11, A219760]. All values for which
$m_{3}(n)$ is known precisely are given in Table 1.

$n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
$m_{3}(n)$ | 1 | 4 | 4 | 4 | 6 | 6 | 8 | 9 | 10
$n$ | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18
$m_{3}(n)$ | 10 | 12 | 12 | 14 | 15 | 16 | 17 | 18 | 18
$n$ | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27
$m_{3}(n)$ | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 26 | 28
Table 1: All known values of $m_{3}(n)$.

The data given in Table 1 suggested to us that for $n$ odd and $n\geq 3$ that
we should have $m_{3}(n)\geq n+1$; Gardner conjectured the same [5]333In a
typed letter that Martin Gardner wrote to John H. Conway dated 2 June 1975, he
wrote, “It would be nice if the minimum for all odd $n$ were $n+1$, and for
all even $n$, $n$ or $n+2$.”. We prove the conjecture in the case that $n$ is
congruent to 1 modulo 4 as our main result.

######  Theorem 2.

For $n$ congruent to 1 modulo 4 and $n\geq 5$, we have $m_{3}(n)\geq n+1$.

The proof of our main result relies on a mixture of the polynomial method,
combinatorial arguments and linear algebra, some of which are similar to those
found in [3]. However, a new, key ingredient is a recent strengthening of
Alon’s Combinatorial Nullstellensatz due to Bogdan Nica [9]. Before stating
Nica’s theorem, we recall Part II of the Combinatorial Nullstellensatz (i.e.,
the Non-vanishing Corollary).

######  Theorem 3.

[Combinatorial Nullstellensatz, Theorem 1.2 [2]] Let $F$ be an arbitrary
field, and let $f=f(x_{1},\ldots,x_{n})$ be a polynomial in
$F[x_{1},\ldots,x_{n}]$. Suppose the degree $\deg(f)$ of $f$ is
$\sum_{i=1}^{n}t_{i}$, where each $t_{i}$ is a non-negative integer, and
suppose the coefficient of $\prod_{i=1}^{n}x_{i}^{t_{i}}$ in $f$ is nonzero.
Then, if $S_{1},\ldots,S_{n}$ are subsets of $F$ with $|S_{i}|>t_{i}$, there
are $s_{1}\in S_{1},\ldots,s_{n}\in S_{n}$ so that $f(s_{1},\ldots,s_{n})\neq
0$.

We say that a subset $S$ of a field $F$ is a zero-sum if the sum of the
elements in $S$ is the zero of the field. In the case that each of the $S_{i}$
is a zero-sum subset of the field, Nica [9] showed that the same conclusion in
Theorem 3 holds under a slightly weaker degree restriction placed upon the
degree of the polynomial. Nica’s result is as follows.

######  Theorem 4.

[Combinatorial Nullstellensatz for Zero-sum Grids, [9]] Let $F$ be an
arbitrary field, and let $f=f(x_{1},\ldots,x_{n})$ be a polynomial in
$F[x_{1},\ldots,x_{n}]$. Suppose the degree $\deg(f)$ of $f$ is
$1+\sum_{i=1}^{n}t_{i}$, where each $t_{i}$ is a non-negative integer, and
suppose the coefficient of $\prod_{i=1}^{n}x_{i}^{t_{i}}$ in $f$ is nonzero.
Then, if $S_{1},\ldots,S_{n}$ are zero-sum subsets of $F$ with
$|S_{i}|>t_{i}$, there are $s_{1}\in S_{1},\ldots,s_{n}\in S_{n}$ so that
$f(s_{1},\ldots,s_{n})\neq 0$.

This Nullstellensatz for Zero-sum Grids is, in fact, a particular case of a
more expansive theorem that we won’t discuss here. Roughly, it says that we
may relax the degree constraints on the polynomial to reach the same
conclusion of the Combinatorial Nullstellensatz whenever the grid is
“structured”, see [9]. As far as we know, the proof of Theorem 2 represents
the first application of this particular generalization of the Combinatorial
Nullstellensatz [9] outside of that paper. It is interesting to us whenever a
generalization of Alon’s Nullstellensatz is truly needed for a combinatorial
problem, as is the case for our main result.

This paper is organized as follows. In Section 2 we give the necessary
definitions and a sketch of the proof of Theorem 2. In Section 3 we prove
Theorem 2. In Section 4 we provide some further remarks and also include
insights into the difficulty of showing $m_{3}(n)\geq n+1$ for the case when
$n$ is 3 modulo 4.

##  2 Definitions and notation

We adopt many of the definitions and notation originally used in [3], with one
important exception. We consider the infinite square ${\mathbb{Z}}$-lattice as
a chessboard and its vertices as squares of the chessboard. A board $B$ is a
finite subset of the chessboard. For $n$ odd, let $\overline{B}_{n}$ denote
the board
$[-\frac{n-1}{2},\frac{n-1}{2}]\times[-\frac{n-1}{2},\frac{n-1}{2}].$444This
is the key difference to the set-up as compared to that of [3] as we now are
considering a zero-sum grid, thus facilitating the use of Theorem 4. We may
refer to a square of $\overline{B}_{n}$ by the coordinates $(x,y)$ of its
corresponding vertex. As we are interested in the queens version of the
problem, the lines that we concern ourselves with have slope $0,+1,-1,$ or
$\infty$ and contain vertices of the lattice — so, throughout we use line to
refer to a line of this type. Any subset $S$ of the infinite square lattice
may be considered a placement of queens, or placement for short, by imagining
a queen on each corresponding square of the chessboard. The size of a
placement $S$ is its cardinality $|S|$. We say that two queens of a placement
${\cal Q}$ define a line if they lie on the same row, column or diagonal. In
such a way, the placement ${\cal Q}$ defines a set of lines, the set of lines
defined by the collinear pairs of ${\cal Q}$. A line is said to cover a square
if the coordinates of the square is in the zero locus of the line. A placement
is called good if does not contain $3$ queens in a line and loses this
property upon the addition of a queen to an unoccupied square. A queen is said
to be lonely if she is not collinear with any other queen. We illustrate a
placement with a lonely queen in Figure 2, where there exists one lonely queen
in the topmost row (i.e., she has coordinates $(0,2)$).

5x5maxfield=e5, borderwidth=0.5mm, color=white, colorwhitebackfields,
color=white, colorblackbackfields, markregion=a1-z24, showmover=false,
hlabelwidth=18pt, hlabellift=2pt [ labelbottom=true, labelleft=true,
labelbottomformat= , labelleftformat= , style=5x5, setpieces=Qa1, Qe1, Qb2,
Qd2, Qb3, Qd3, Qa4, Qe4, Qc5, padding=1ex, ]

Figure 2: An example of a good placement with one lonely queen on a $5\times
5$ board.

We now sketch the proof of Theorem 2. We will consider a good placement ${\cal
Q}$ of size at most $4k+1$. The proof will divide into two cases, which
roughly depend on the number of lonely queens. In the first case, when the
number of lonely queens is not one, when $q<4k+1$ or when the number of lines
defined by ${\cal Q}$ is not maximized, ${\cal Q}$ will define a set of lines
and together these lines (and perhaps some additional lines) will be used to
construct a polynomial that vanishes on the squares of the chessboard.
However, we will be able to show that the coefficient on a leading monomial of
this polynomial, which is of ‘small degree,’ is non-zero, thus obtaining a
contradiction to Alon’s Combinatorial Nullstellensatz. (The proof in the first
case is essentially that found in [3] for the proof of Theorem 1.) The second
case, when the number of lonely queens is one, $q=4k+1$ and the number of
lines defined by ${\cal Q}$ is maximized, is more involved. In this case,
Alon’s Nullstellensatz will be insufficient. Like in the previous case, we use
the set of lines defined by ${\cal Q}$ to construct several polynomials. For
each of the four possible slopes of a line passing through the lonely queen,
we define a polynomial so that it vanishes on all the squares of the
chessboard. For each polynomial, we calculate the coefficient of an
appropriate monomial, which is in terms of the coordinates of the lonely queen
and sums of the intercepts of the defining lines of ${\cal Q}$. To compute
this coefficient requires nothing more sophisticated than the Binomial
Theorem. If one of these four coefficients is non-zero, then we obtain a
contradiction to Nica’s Combinatorial Nullstellensatz for Zero-sum Grids. If
each of these four coefficients is zero, then, together with some geometric
and combinatorial arguments that yield additional equations, we will be able
to construct a homogeneous system of linear equations whose solution yields
the location of the lonely queen to be centered on the board (i.e., she has
coordinates $(0,0)$) along with some other attributes of the placement. This
structural information allows for a combinatorial argument that finishes the
proof.

##  3 Proof of Main Theorem

Proof of Theorem 2

Let $n=4k+1$ and $k\geq 1$. Let ${\cal Q}$ be a good placement on
$\overline{B}_{n}$ with size $q=|{\cal Q}|\leq 4k+1$. Let
$\mathcal{Q}^{\prime}$ denote the (possibly empty) subset of lonely queens in
${\cal Q}$. Let $|\mathcal{Q}^{\prime}|=q^{\prime}$. We work towards a
contradiction.

Case 1: $q^{\prime}\neq 1$, $q<4k+1$, or $q^{\prime}=1$ and some queen(s) that
is not lonely participates in defining fewer than $4$ lines.

We proceed by constructing a polynomial $f(x,y)$ of total degree $8k$ that
vanishes on each square $(x,y)\in\overline{B}_{n}$. We will then obtain a
contradiction through a suitable application of the Combinatorial
Nullstellensatz.

We construct $f$ as a product of linear factors of three different types. The
first type consists of the set of lines defined by $\mathcal{Q}$. Since the
placement $\mathcal{Q}$ is good, every unoccupied square of $\overline{B}_{n}$
is in the zero locus of at least one line of the first type.

There may be some lonely queens in $\mathcal{Q}$, which by definition are not
on any defining line. For each $Q_{i}\in\mathcal{Q}^{\prime}$ we will
artificially define a new line (of the second type) that passes through the
square occupied by $Q_{i}$. While we are free to choose any one of the four
possible slopes for each line, it is most convenient to distribute the slopes
as evenly as possible. Every occupied square is in the zero locus of at least
one line of either of the first two types.

For each of the four possible slopes there are at most
$\left\lfloor\frac{q-q^{\prime}}{2}\right\rfloor$ lines of that slope of the
first type and at most $\left\lceil\frac{q^{\prime}}{4}\right\rceil$ lines of
that slope of the second type. If $q^{\prime}\neq 1$ or if $q<4k+1$, these
quantities sum to at most $2k$. If $q^{\prime}=1$ and some queen(s) that is
not lonely participates in defining fewer than $4$ lines, then one of the four
possible slope directions has at most $2k-1$ lines and we define a new line
through the lonely queen to have that slope. As necessary, define new,
distinct lines (of the third type) in each of the four directions so that
there are exactly $2k$ lines of each slope among the three types. (The lines
of the third type serve only to facilitate the application of the
Combinatorial Nullstellensatz; it is immaterial which squares they vanish on.)

Let $\mathcal{L}=\\{L_{1},\ldots,L_{8k}\\}$ be the set of $8k$ lines and let
$l_{i}=0$ be the equation in variables $x$ and $y$ defining $L_{i}$. We then
define

$f(x,y)=\prod_{i=1}^{8k}l_{i}\in\mathbb{R}[x,y].$

As desired, the polynomial $f(x,y)=0$ for every $(x,y)\in\overline{B}_{n}$ as
every unoccupied square is on a line of the first type and every occupied
square is on a line of either the first or second type. By construction, the
total degree of $f$ is $8k$. If we group the factors in $f$ according to
slope, we see that $f$ can be rewritten as

$f(x,y)=\prod_{j=1}^{2k}(x-\alpha_{j})(y-\beta_{j})(x-y-\gamma_{j})(x+y-\delta_{j})$

for suitable constants $\alpha_{j},\beta_{j},\gamma_{j},\delta_{j}$. The
leading monomials of $f(x,y)$ are the same as that of
$g(x,y)=x^{2k}y^{2k}(x^{2}-y^{2})^{2k}$. From the Binomial Theorem, we
conclude that the coefficient of the top-degree term $x^{4k}y^{4k}$ is
$\pm{2k\choose k}$, i.e. the coefficient is nonzero.

We now apply Theorem 3 to $f(x,y)$, where $t_{1}=t_{2}=4k$ and
$S_{1}=S_{2}=\\{-2k,\ldots,2k\\}$, to obtain that there are $s_{1}\in
S_{1},s_{2}\in S_{2}$ such that $f(s_{1},s_{2})\neq 0$. We have reached a
contradiction.

Case 2: $q=4k+1$, $q^{\prime}=1$ and all other queens participate in defining
a line of each of the four possible slopes.

As we did in Case 1, we employ the polynomial method; this time we will apply
Theorem 4.

We start by constructing a polynomial $f_{1}:=f_{1}(x,y)$ of total degree
$8k+1$ that vanishes on each square $(x,y)\in\overline{B}_{n}$. The polynomial
$f_{1}$ will be a product of linear factors of two different types. The first
type is given by the set of lines defined by $\mathcal{Q}$. Since the
placement $\mathcal{Q}$ is good, every unoccupied square of $\overline{B}_{n}$
is in the zero locus of at least one line of the first type. As given by the
restrictions of the case, there is one lonely queen in $\mathcal{Q}^{\prime}$
which is not on any defining line. For this one lonely queen
$Q\in\mathcal{Q}^{\prime}$ we artificially define a new line that passes
through the square occupied by $Q$. While we are free to choose any one of the
four possible slopes for this one line, at this point in the proof we choose
slope $\infty$. Every occupied square is covered by at least one line of
either of the two types.

For each of the four possible slopes there are exactly $\frac{4k}{2}=2k$ lines
of that slope of the first type and precisely one line of slope $\infty$ of
the second type. (Unlike in Case 1, we need not define lines of the third
type.)

Let $\mathcal{L}=\\{L_{1},\ldots,L_{8k+1}\\}$ be our set of $8k+1$ lines and
let $l_{i}=0$ be the equation in variables $x$ and $y$ defining $L_{i}$. We
then define

$f_{1}(x,y)=\prod_{i=1}^{8k+1}l_{i}\in\mathbb{R}[x,y].$

As desired, the polynomial $f_{1}(x,y)=0$ for every $(x,y)\in\overline{B}_{n}$
as every unoccupied square is on a line of the first type and every occupied
square is on a line of either the first or second type. By construction, the
total degree of $f$ is $8k+1$. Let $(\alpha_{0},\beta_{0})$ denote the square
occupied by the lonely queen. If we group the factors in $f_{1}$ according to
slope, we see that $f_{1}$ can be rewritten as

$f_{1}(x,y)=(x-\alpha_{0})\prod_{j=1}^{2k}(x-\alpha_{j})(y-\beta_{j})(x-y-\gamma_{j})(x+y-\delta_{j})$

for suitable constants $\alpha_{j},\beta_{j},\gamma_{j},\delta_{j}$.

If can we conclude that the coefficient of the term $x^{4k}y^{4k}$ is nonzero,
then we may apply Theorem 4 to $f_{1}(x,y)$, where $t_{1}=t_{2}=4k$ and
$S_{1}=S_{2}=\\{-2k,\ldots,2k\\}$ (zero-sum sets), to obtain that there are
$s_{1}\in S_{1},s_{2}\in S_{2}$ such that $f_{1}(s_{1},s_{2})\neq 0$, thus
obtaining a contradiction.

We thus ‘expand’ $f_{1}(x,y)$ and ‘collect’ like terms so that we might
determine the coefficient of $x^{4k}y^{4k}$. Since we are only interested in
the coefficient on this term, we focus our analysis only on it. Note that this
term has degree one less than the degree of $f_{1}$. So, to obtain such a
monomial in the expansion, from the $8k+1$ linear factors, we must choose the
$x$-variable $4k$ times, the $y$-variable $4k$ times and thus some constant
once. We think of choosing that constant first and so partition our analysis
based upon whether the constant that we have chosen is some
$\alpha_{j},\beta_{j},\gamma_{j}$ or $\delta_{j}$.

  1. 1.

Choose some $\alpha_{j}$ first for some $0\leq j\leq 2k$.
The remaining factors with their constant terms removed (since we can’t choose
them) are:

$x^{2k}y^{2k}(x-y)^{2k}(x+y)^{2k}.$

This equals

$x^{2k}y^{2k}(x^{2}-y^{2})^{2k}=x^{2k}y^{2k}\sum_{\ell=0}^{2k}{2k\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-\ell}.$

The only choice of $\ell$ which yields the desired monomial is $\ell=k$, which
gives a coefficient of ${2k\choose k}(-1)^{k}$. This is the contribution for
each $\alpha_{j}$. Thus, we have a total contribution to the coefficient of
the desired monomial of $(-1)^{k}{2k\choose k}\sum_{j=0}^{2k}-\alpha_{j}.$

  2. 2.

Choose some $\beta_{j}$ first for some $1\leq j\leq 2k$.
The remaining factors with their constant terms removed (since we can’t choose
them) are:

$x^{2k+1}y^{2k-1}(x-y)^{2k}(x+y)^{2k}.$

This equals

$x^{2k+1}y^{2k-1}(x^{2}-y^{2})^{2k}=x^{2k+1}y^{2k-1}\sum_{\ell=0}^{2k}{2k\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-\ell}.$

There is no choice of $\ell$ which yields the desired monomial, which is true
for each $\beta_{j}$. Thus, we have a total contribution to the coefficient of
the desired monomial of $0.$

  3. 3.

Choose some $\gamma_{j}$ first for some $1\leq j\leq 2k$.

The remaining factors with their constant terms removed (since we can’t choose
them) are:

$x^{2k+1}y^{2k}(x-y)^{2k-1}(x+y)^{2k}.$

This equals

$\displaystyle x^{2k+1}y^{2k}(x+y)(x^{2}-y^{2})^{2k-1}$ $\displaystyle=$
$\displaystyle
x^{2k+1}y^{2k}(x+y)\sum_{\ell=0}^{2k-1}{2k-1\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-1-\ell}$
$\displaystyle=$ $\displaystyle
x^{2k+2}y^{2k}\sum_{\ell=0}^{2k-1}{2k-1\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-1-\ell}$
$\displaystyle+x^{2k+1}y^{2k+1}\sum_{\ell=0}^{2k-1}{2k-1\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-1-\ell}.$

Only in the first of the two summands is there a choice of $\ell$ which yields
the desired monomial; it is $\ell=k-1$, which gives a coefficient of
${2k-1\choose k-1}(-1)^{k}$. This is the contribution for each $\gamma_{j}$.
Thus, we have a total contribution to the coefficient of the desired monomial
of $(-1)^{k}{2k-1\choose k-1}\sum_{j=1}^{2k}-\gamma_{j}.$

  4. 4.

Choose some $\delta_{j}$ first for some $1\leq j\leq 2k$.

The remaining factors with their constant terms removed (since we can’t choose
them) are:

$x^{2k+1}y^{2k}(x-y)^{2k}(x+y)^{2k-1}.$

This equals

$\displaystyle x^{2k+1}y^{2k}(x-y)(x^{2}-y^{2})^{2k-1}$ $\displaystyle=$
$\displaystyle
x^{2k+1}y^{2k}(x-y)\sum_{\ell=0}^{2k-1}{2k-1\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-1-\ell}$
$\displaystyle=$ $\displaystyle
x^{2k+2}y^{2k}\sum_{\ell=0}^{2k-1}{2k-1\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-1-\ell}$
$\displaystyle-x^{2k+1}y^{2k+1}\sum_{\ell=0}^{2k-1}{2k-1\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-1-\ell}.$

Only in the first of the two summands is there a choice of $\ell$ which yields
the desired monomial; it is $\ell=k-1$, which gives a coefficient of
${2k-1\choose k-1}(-1)^{k}$. This is the contribution for each $\delta_{j}$.
Thus, we have a total contribution to the coefficient of the desired monomial
of $(-1)^{k}{2k-1\choose k-1}\sum_{j=1}^{2k}-\delta_{j}.$

The sum of these four contributions is the coefficient $C^{f_{1}}{(4k,4k)}$ on
$x^{4k}y^{4k}$ in $f_{1}(x,y)$. It is

$\displaystyle C^{f_{1}}{(4k,4k)}$ $\displaystyle=$
$\displaystyle(-1)^{k}{2k\choose
k}\sum_{j=0}^{2k}-\alpha_{j}+(-1)^{k}{2k-1\choose
k-1}\sum_{j=1}^{2k}-\gamma_{j}+(-1)^{k}{2k-1\choose
k-1}\sum_{j=1}^{2k}-\delta_{j}.$

If this coefficient is non-zero, then by Theorem 4 we are done. Thus, assume
it is zero.

We repeat the above procedure for the placement $\mathcal{Q}$ with the one
lonely queen at $(\alpha_{0},\beta_{0})$ by defining a similar polynomial
$f_{2}(x,y)$, this time with a line of slope $0$ through the lonely queen, as
follows.

Let

$f_{2}(x,y)=(y-\beta_{0})\prod_{j=1}^{2k}(x-\alpha_{j})(y-\beta_{j})(x-y-\gamma_{j})(x+y-\delta_{j})$

for suitable constants $\alpha_{j},\beta_{j},\gamma_{j},\delta_{j}$.

By repeating the above procedure or, perhaps more simply, by noting the
symmetries between $f_{1}(x,y)$ and $f_{2}(x,y)$, the coefficient
$C^{f_{2}}{(4k,4k)}$ on $x^{4k}y^{4k}$ in $f_{2}(x,y)$ is

$\displaystyle C^{f_{2}}{(4k,4k)}$ $\displaystyle=$
$\displaystyle(-1)^{k}{2k\choose
k}\sum_{j=0}^{2k}-\beta_{j}+(-1)^{k}{2k-1\choose
k-1}\sum_{j=1}^{2k}-\gamma_{j}+(-1)^{k}{2k-1\choose
k-1}\sum_{j=1}^{2k}-\delta_{j}.$

If this coefficient is non-zero, then by Theorem 4 we are done. Thus, assume
it is zero.

We repeat the above procedure for the placement $\mathcal{Q}$ with the one
lonely queen at $(\alpha_{0},\beta_{0})$ by defining a similar polynomial
$f_{3}(x,y)$, this time with a line of slope $+1$ through the lonely queen, as
follows.

Let

$f_{3}(x,y)=(x-y-\gamma_{0})\prod_{j=1}^{2k}(x-\alpha_{j})(y-\beta_{j})(x-y-\gamma_{j})(x+y-\delta_{j})$

for suitable constants $\alpha_{j},\beta_{j},\gamma_{j},\delta_{j}$.

As above, we ‘expand’ $f_{3}(x,y)$ and ‘collect’ like terms so that we might
determine the coefficient of $x^{4k}y^{4k}$. Since we are only interested in
the coefficient on this term, we focus our analysis only on it. Note that this
term has degree one less than the degree of $f_{3}$. So, to obtain such a
monomial in the expansion, from the $8k+1$ linear factors, we must choose the
$x$-variable $4k$ times, the $y$-variable $4k$ times and thus some constant
once. We think of choosing that constant first and so partition our analysis
based upon whether the constant that we have chosen is some
$\alpha_{j},\beta_{j},\gamma_{j}$ or $\delta_{j}$.

  1. 1.

Choose some $\alpha_{j}$ first for some $1\leq j\leq 2k$.
The remaining factors with their constant terms removed (since we can’t choose
them) are:

$x^{2k-1}y^{2k}(x-y)^{2k+1}(x+y)^{2k}.$

This equals

$\displaystyle x^{2k-1}y^{2k}(x-y)(x^{2}-y^{2})^{2k}$ $\displaystyle=$
$\displaystyle
x^{2k-1}y^{2k}(x-y)\sum_{\ell=0}^{2k}{2k\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-\ell}$
$\displaystyle=$ $\displaystyle
x^{2k}y^{2k}\sum_{\ell=0}^{2k}{2k\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-\ell}$
$\displaystyle-x^{2k-1}y^{2k+1}\sum_{\ell=0}^{2k}{2k\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-\ell}.$

Only in the first of the two summands is there a choice of $\ell$ which yields
the desired monomial; it is $\ell=k$, which gives a coefficient of ${2k\choose
k}(-1)^{k}$. This is the contribution for each $\alpha_{j}$. Thus, we have a
total contribution to the coefficient of the desired monomial of
$(-1)^{k}{2k\choose k}\sum_{j=1}^{2k}-\alpha_{j}.$

  2. 2.

Choose some $\beta_{j}$ first for some $1\leq j\leq 2k$.
The remaining factors with their constant terms removed (since we can’t choose
them) are:

$x^{2k}y^{2k-1}(x-y)^{2k+1}(x+y)^{2k}.$

This equals

$\displaystyle x^{2k}y^{2k-1}(x-y)(x^{2}-y^{2})^{2k}$ $\displaystyle=$
$\displaystyle
x^{2k}y^{2k-1}(x-y)\sum_{\ell=0}^{2k}{2k\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-\ell}$
$\displaystyle=$ $\displaystyle
x^{2k+1}y^{2k-1}\sum_{\ell=0}^{2k}{2k\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-\ell}$
$\displaystyle-x^{2k}y^{2k}\sum_{\ell=0}^{2k}{2k\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-\ell}.$

Only in the second of the two summands is there a choice of $\ell$ which
yields the desired monomial; it is $\ell=k$, which gives a coefficient of
$(-1){2k\choose k}(-1)^{k}$. This is the contribution for each $\beta_{j}$.
Thus, we have a total contribution to the coefficient of the desired monomial
of $(-1)^{k+1}{2k\choose k}\sum_{j=1}^{2k}-\beta_{j}.$

  3. 3.

Choose some $\gamma_{j}$ first for some $0\leq j\leq 2k$.

The remaining factors with their constant terms removed (since we can’t choose
them) are:

$x^{2k}y^{2k}(x-y)^{2k}(x+y)^{2k}.$

This equals

$\displaystyle x^{2k}y^{2k}(x^{2}-y^{2})^{2k}$ $\displaystyle=$ $\displaystyle
x^{2k}y^{2k}\sum_{\ell=0}^{2k}{2k\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-\ell}.$

The only choice of $\ell$ which yields the desired monomial is $\ell=k$, which
gives a coefficient of ${2k\choose k}(-1)^{k}$. This is the contribution for
each $\gamma_{j}$. Thus, we have a total contribution to the coefficient of
the desired monomial of $(-1)^{k}{2k\choose k}\sum_{j=0}^{2k}-\gamma_{j}.$

  4. 4.

Choose some $\delta_{j}$ first for some $1\leq j\leq 2k$.

The remaining factors with their constant terms removed (since we can’t choose
them) are:

$x^{2k}y^{2k}(x-y)^{2k+1}(x+y)^{2k-1}.$

This equals

$\displaystyle x^{2k}y^{2k}(x-y)^{2}(x^{2}-y^{2})^{2k-1}$ $\displaystyle=$
$\displaystyle
x^{2k}y^{2k}(x^{2}-2xy+y^{2})\sum_{\ell=0}^{2k-1}{2k-1\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-1-\ell}$
$\displaystyle=$ $\displaystyle
x^{2k+2}y^{2k}\sum_{\ell=0}^{2k-1}{2k-1\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-1-\ell}$
$\displaystyle-2x^{2k+1}y^{2k+1}\sum_{\ell=0}^{2k-1}{2k-1\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-1-\ell}$
$\displaystyle+x^{2k}y^{2k+2}\sum_{\ell=0}^{2k-1}{2k-1\choose\ell}(x^{2})^{\ell}(-y^{2})^{2k-1-\ell}.$

Amongst the three summands, there is a choice of $\ell=k-1$ in the first, no
choice in the second and a choice of $\ell=k$ in the third. This yields a
coefficient of $(-1)^{k}{2k-1\choose k-1}+(-1)^{k-1}{2k-1\choose k}=0.$ This
is the contribution for each $\delta_{j}$. Thus, we have a total contribution
to the coefficient of the desired monomial of $0.$

The sum of these four contributions is the coefficient $C^{f_{3}}{(4k,4k)}$ on
$x^{4k}y^{4k}$ in $f_{3}(x,y)$. It is

$\displaystyle C^{f_{3}}{(4k,4k)}$ $\displaystyle=$
$\displaystyle(-1)^{k}{2k\choose
k}\sum_{j=1}^{2k}-\alpha_{j}+(-1)^{k+1}{2k\choose
k}\sum_{j=1}^{2k}-\beta_{j}+(-1)^{k}{2k\choose k}\sum_{j=0}^{2k}-\gamma_{j}.$

If this coefficient is non-zero, then by Theorem 4 we are done. Thus, assume
it is zero.

We repeat the above procedure for the placement $\mathcal{Q}$ with the one
lonely queen at $(\alpha_{0},\beta_{0})$ by defining a similar polynomial
$f_{4}(x,y)$, this time with a line of slope $-1$ through the lonely queen, as
follows.

Let

$f_{4}(x,y)=(x+y-\delta_{0})\prod_{j=1}^{2k}(x-\alpha_{j})(y-\beta_{j})(x-y-\gamma_{j})(x+y-\delta_{j})$

for suitable constants $\alpha_{j},\beta_{j},\gamma_{j},\delta_{j}$.

By repeating the above procedure or, perhaps more simply, by noting the
symmetries between $f_{3}(x,y)$ and $f_{4}(x,y)$, the coefficient
$C^{f_{4}}{(4k,4k)}$ on $x^{4k}y^{4k}$ in $f_{4}(x,y)$ is

$\displaystyle C^{f_{4}}{(4k,4k)}$ $\displaystyle=$
$\displaystyle(-1)^{k}{2k\choose
k}\sum_{j=1}^{2k}-\alpha_{j}+(-1)^{k}{2k\choose
k}\sum_{j=1}^{2k}-\beta_{j}+(-1)^{k}{2k\choose k}\sum_{j=0}^{2k}-\delta_{j}.$

If this coefficient is non-zero, then by Theorem 4 we are done. Thus, assume
it is zero.

We have now reached the following system of linear equations:

$\displaystyle
C^{f_{1}}{(4k,4k)}=0,C^{f_{2}}{(4k,4k)}=0,C^{f_{3}}{(4k,4k)}=0,C^{f_{4}}{(4k,4k)}=0.$
(1)

Next we generate four additional linear equations via some geometric and
combinatorial observations.

Consider the lonely queen located on square $(\alpha_{0},\beta_{0})$: the
values of $\alpha_{0}$ and $\beta_{0}$ determine the values of $\gamma_{0}$
and $\delta_{0}$ as follows. The line of slope $+1$ that goes through the
square $(\alpha_{0},\beta_{0})$ has equation

$y-\beta_{0}=1(x-\alpha_{0}),~{}~{}~{}x-y-(\alpha_{0}-\beta_{0})=0$

and the line of slope $-1$ that goes through the square
$(\alpha_{0},\beta_{0})$ has equation

$y-\beta_{0}=-1(x-\alpha_{0}),~{}~{}~{}x+y-(\alpha_{0}+\beta_{0})=0.$

As a result, we have

$\displaystyle\alpha_{0}-\beta_{0}-\gamma_{0}=0,$ (2)
$\displaystyle\alpha_{0}+\beta_{0}-\delta_{0}=0.$ (3)

Now consider the other $4k$ queens of ${\cal Q}\setminus{\cal Q^{\prime}}$
(i.e., those that are not lonely). For each such queen there exists an
$\alpha\in\\{\alpha_{1},\ldots,\alpha_{2k}\\}$ and
$\beta\in\\{\beta_{1},\ldots,\beta_{2k}\\}$ that give her coordinates. The
line of slope $+1$ that goes through the square $(\alpha,\beta)$ has equation

$y-\beta=1(x-\alpha),~{}~{}~{}x-y-(\alpha-\beta)=0$

and the line of slope $-1$ that goes through the square $(\alpha,\beta)$ has
equation

$y-\beta=-1(x-\alpha),~{}~{}~{}x+y-(\alpha+\beta)=0.$

As a result, we have $\gamma=\alpha-\beta$ for some
$\gamma\in\\{\gamma_{1},\ldots,\gamma_{2k}\\}$ and $\delta=\alpha+\beta$ for
some $\delta\in\\{\delta_{1},\ldots,\delta_{2k}\\}$. As each such diagonal
line is defined by two queens, upon considering the $4k$ equations deriving
from the $-1$-slope lines each element of
$\\{\gamma_{1},\ldots,\gamma_{2k}\\}$ occurs twice in this set of equations;
similarly, in the $4k$ equations deriving from the $+1$-slope lines each
element of $\\{\delta_{1},\ldots,\delta_{2k}\\}$ occurs twice. Thus, we can
write the following:

$\displaystyle\sum_{Q\in{\cal Q}\setminus{\cal
Q^{\prime}}}(\alpha-\beta)=2\sum_{i=1}^{2k}\gamma_{i},$ (4)

and

$\displaystyle\sum_{Q\in{\cal Q}\setminus{\cal
Q^{\prime}}}(\alpha+\beta)=2\sum_{i=1}^{2k}\delta_{i}.$ (5)

The restrictions of Case 2 give that each queen in ${\cal Q}\setminus{\cal
Q^{\prime}}$ is contained in both a vertical line and a horizontal line. As a
result, each $\alpha\in\\{\alpha_{1},\ldots,\alpha_{2k}\\}$ and each
$\beta\in\\{\beta_{1},\ldots,\beta_{2k}\\}$ appears twice on the left side of
each of Equation 4 and Equation 5. This enables us to rewrite the left side of
Equations 4 and 5 to obtain

$\displaystyle
2\sum_{i=1}^{2k}\alpha_{i}-2\sum_{i=1}^{2k}\beta_{i}=2\sum_{i=1}^{2k}\gamma_{i},$
(6)

and

$\displaystyle
2\sum_{i=1}^{2k}\alpha_{i}+2\sum_{i=1}^{2k}\beta_{i}=2\sum_{i=1}^{2k}\delta_{i}.$
(7)

We may scale and rewrite Equations 6-7 as

$\displaystyle\sum_{i=1}^{2k}\alpha_{i}-\sum_{i=1}^{2k}\beta_{i}-\sum_{i=1}^{2k}\gamma_{i}=0,$
(8)

and

$\displaystyle\sum_{i=1}^{2k}\alpha_{i}+\sum_{i=1}^{2k}\beta_{i}-\sum_{i=1}^{2k}\delta_{i}=0.$
(9)

At this point, we have now generated a homogeneous system of eight linear
equations - these are Equations 1, 2, 3, 8, 9 \- in the variables
$\alpha_{0},\beta_{0},\gamma_{0},\delta_{0},\sum_{j=1}^{2k}\alpha_{j},\sum_{j=1}^{2k}\beta_{j},\sum_{j=1}^{2k}\gamma_{j},\sum_{j=1}^{2k}\delta_{j}.$
For notational convenience we set $\omega:=(-1)^{k}{2k\choose k}$ and express
these equations using the following augmented matrix.

$\mathbf{[{\bf
A}~{}~{}0]}=\blockarray{ccccccccc}\alpha_{0}&\beta_{0}\gamma_{0}\delta_{0}\sum_{j=1}^{2k}\alpha_{j}\sum_{j=1}^{2k}\beta_{j}\sum_{j=1}^{2k}\gamma_{j}\sum_{j=1}^{2k}\delta_{j}\\\
\block{[ccccccccc]}\omega 000\omega 0\omega/2\omega/20\\\ 0\omega
000\omega\omega/2\omega/20\\\ 00\omega 0\omega-\omega\omega 00\\\
000\omega\omega\omega 0\omega 0\\\ 1-1-1000000\\\ 110-100000\\\ 00001-1-100\\\
0000110-10\\\ $

Guassian elimination yields the following row reduced $8\times 8$ coefficient
matrix:

$\mathbf{{\bf
A}}\sim\blockarray{cccccccc}\alpha_{0}&\beta_{0}\gamma_{0}\delta_{0}\sum_{j=1}^{2k}\alpha_{j}\sum_{j=1}^{2k}\beta_{j}\sum_{j=1}^{2k}\gamma_{j}\sum_{j=1}^{2k}\delta_{j}\\\
\block{[cccccccc]}10000001\\\ 01000001\\\ 00100000\\\ 00010002\\\
0000100-0.5\\\ 0000010-0.5\\\ 00000010\\\ 00000000\\\ $

We see that the null space of $A$ is spanned by the following vector,

$\begin{bmatrix}1&1&0&2&-0.5&-0.5&0&-1\end{bmatrix}^{\intercal}.$

Note, for a vector ${\bf x}$ not in the null space, at least one entry of
$A{\bf x}$ is nonzero. If this nonzero entry is among the first $4$ entries,
then at least one of
$C^{f_{1}}{(4k,4k)},C^{f_{2}}{(4k,4k)},C^{f_{3}}{(4k,4k)},C^{f_{4}}{(4k,4k)}$
is nonzero, a contradiction to Theorem 4. If this nonzero entry is among the
latter $4$ entries, then it contradicts a relationship we found in one of
Equations 2, 3, 8, 9.

The vectors in the null space of $A$ imply that the lonely queen has
coordinates $(s,s)$ for $s\in\\{-2k,\ldots,2k\\}$, so the lonely queen is on
the line $y=x$, i.e. the ‘back-diagonal’ of the chessboard. If we rotate the
placement by 90-degrees counter-clockwise, then the placement we obtain
satisfies the conditions of Case 2 and has the lonely queen on the ‘forward-
diagonal’, i.e., on the line $y=-x$. Applying all of the previous arguments to
this new placement shows that the lonely queen must be on the back-diagonal.
Thus, the lonely queen is at the center, i.e., she has coordinates $(0,0)$.
This implies that the only vector ${\bf x}$ in the null space of $A$ which we
need to be concerned with is the zero vector. Thus,

$\displaystyle\alpha_{0},\beta_{0},\gamma_{0},\delta_{0},\sum_{j=1}^{2k}\alpha_{j},\sum_{j=1}^{2k}\beta_{j},\sum_{j=1}^{2k}\gamma_{j},\sum_{j=1}^{2k}\delta_{j}=0.$
(10)

With the location information provided by Equation 10 and the restrictions of
Case 2, we now turn to a combinatorial and geometric argument to finish the
proof.555Figure 3 is an example of a placement satisfying Equation 10 yet is
not good.

9x9maxfield=i9, borderwidth=0.5mm, color=white, colorwhitebackfields,
color=white, markregion=a1-z24, showmover=false, hlabelwidth=18pt,
hlabellift=2pt

[ markstyle=cross,markfields=b2,h2,c3,e3,g3,c5,g5,c7,e7,g7,b8,h8,
labelbottom=true, labelleft=true, labelbottomformat= , labelleftformat= ,
style=9x9, setpieces=Qe5,Qd1,Qf1,Qa4,Qi4,Qa6,Qi6,Qd9,Qf9, padding=1ex, ]

Figure 3: A placement of 10 queens on a $9\times 9$ board which corresponds to
the zero vector in Nul $A$. Sqaures marked with a cross indicate those squares
for which the additional placement of a queen would not yield three-in-a-line.

We distinguish between the lines of slope $0$ or $\infty$ defined by ${\cal
Q}$ and those of slope $\pm 1$. To this end, set $U\subseteq\overline{B}_{n}$
to be the set of squares left uncovered by a line of slope $0$ or $\infty$,
where the lonely queen does not define a line. Notice that $U$ defines a
rectangular sub-board. For any index
$i\in\\{\frac{-(n-1)}{2},\ldots,\frac{n-1}{2}\\}$ (respectively
$j\in\\{\frac{-(n-1)}{2},\ldots,\frac{n-1}{2}\\}$) let $C_{i}=\\{(i,\ell)\in
U:\,\frac{-(n-1)}{2}\leq\ell\leq\frac{n-1}{2}\\}$ (respectively
$R_{j}=\\{(\ell,j)\in U:\,\frac{-(n-1)}{2}\leq\ell\leq\frac{n-1}{2}\\}$). The
sets $C_{i}$ and $R_{j}$ keep track of the squares in $U$ for each column and
row, respectively. Let $a<b$ be the minimum and maximum indices, respectively,
for which $C_{i}\neq\emptyset$. Define $a^{\prime}<b^{\prime}$ analogously for
the sets $R_{j}$. The number of the $C_{i}$ and $R_{j}$ that are nonempty is
$n-2k=4k+1-2k=2k+1$. The $8k$ squares that form the set $C_{a}\cup C_{b}\cup
R_{a^{\prime}}\cup R_{b^{\prime}}$ will be referred to as the perimeter of
$U$.

Without loss of generality, we may assume $b-a\geq b^{\prime}-a^{\prime}$ as
otherwise we may rotate the placement by $90^{\circ}$; also, note that
$b-a\geq b^{\prime}-a^{\prime}\geq 2k$. Consider the case that
$b-a>b^{\prime}-a^{\prime}$ (i.e. the inequality is strict, $U$ is rectangular
but not square). In this case, there are at least $4k+1$ (and at most $4k+2$)
empty squares of $C_{a}\cup C_{b}$, each of which must be covered by a line of
slope $\pm 1$. However, each such line can cover at most one of these squares.
As there are $4k$ such lines, we fall short of being able to cover each such
square. So, we may conclude that $b-a=b^{\prime}-a^{\prime}$.

If the lonely queen were to occupy a square in $C_{a}$ (that is, $a=0$), then
all vertical lines defined by ${\cal Q}$ would be to the left of center
contradicting that $\sum_{i=1}^{2k}\alpha_{i}=0$. A similar contradiction
would be reached if the lonely queen were to occupy a square in $C_{b}$ (that
is, $b=0$): all vertical lines defined by ${\cal Q}$ would be to the right of
center contradicting that $\sum_{i=1}^{2k}\alpha_{i}=0$. Thus, the squares of
$C_{a}\cup C_{b}$ are empty of queens. Likewise, the squares of
$R_{a^{\prime}}\cup R_{b^{\prime}}$ are empty of queens. Thus, the perimeter
of $U$ is empty of queens.

$U$$C_{a}$$R_{a^{\prime}}$$C_{b}$$R_{b^{\prime}}\
$$a$$b$$a^{\prime}$$b^{\prime}$$(a,\ a^{\prime})$$(b,\ a^{\prime})$$(b,\
b^{\prime})$$(a,\ b^{\prime})$$0$$0$$2k$$-2k$$2k$$-2k$

Figure 4: The $8k$ squares that form the perimeter of $U$ and some covering
lines.

Consider the $8k$ squares that form the perimeter of $U$ as shown in Figure 4.
As the perimeter of $U$ is empty of queens, each of these squares must be
covered by a line of slope $\pm 1$. Such a line can cover at most 2 such
squares. With a total of $4k$ diagonal lines ($2k$ of slope $+1$ and $2k$ of
slope $-1$) and $8k$ squares, each diagonal line must cover 2 squares. This
forces the $-1$-slope diagonal covering the squares $(a,b^{\prime})$ and
$(b,a^{\prime})$ and forces the $+1$-slope diagonal covering the squares
$(a,a^{\prime})$ and $(b,b^{\prime})$ to exist. Also, a $-1$-slope line that
covers a square of $C_{a}\setminus\\{(a,a^{\prime}),(a,b^{\prime})\\}$ must
also cover a square of
$R_{a^{\prime}}\setminus\\{(a,a^{\prime}),(b,a^{\prime})\\}$; likewise, a
$-1$-slope line that covers a square of
$C_{b}\setminus\\{(b,a^{\prime}),(b,b^{\prime})\\}$ must also cover a square
of $R_{b^{\prime}}\setminus\\{(a,b^{\prime}),(b,b^{\prime})\\}$. Also, a
$+1$-slope line that covers a square of
$C_{a}\setminus\\{(a,a^{\prime}),(a,b^{\prime})\\}$ must also cover a square
of $R_{b^{\prime}}\setminus\\{(a,b^{\prime}),(b,b^{\prime})\\}$; likewise, a
$+1$-slope line that covers a square of
$C_{b}\setminus\\{(b,a^{\prime}),(b,b^{\prime})\\}$ must also cover a square
of $R_{a^{\prime}}\setminus\\{(a,a^{\prime}),(b,a^{\prime})\\}$. Suppose that
there are $p$ lines of slope $-1$ covering squares of
$(C_{a}\setminus\\{(a,a^{\prime}),(a,b^{\prime})\\})\cup(R_{a^{\prime}}\setminus\\{(a,a^{\prime}),(b,a^{\prime})\\})$.
The remaining $2k-1-p$ lines of slope $-1$ cover the squares of
$(C_{b}\setminus\\{(b,a^{\prime}),(b,b^{\prime})\\})\cup(R_{b^{\prime}}\setminus\\{(a,b^{\prime}),(b,b^{\prime})\\})$,
leaving $4k-2-2(2k-1-p)=2p$ squares of this set uncovered, with $p$ squares in
$C_{b}\setminus\\{(b,a^{\prime}),(b,b^{\prime})\\}$ and $p$ squares in
$R_{b^{\prime}}\setminus\\{(a,b^{\prime}),(b,b^{\prime})\\}$. These squares
must be covered by $+1$-slope lines, for an additional $2p$ lines of slope
$+1$. These $2p$ lines together with the $+1$-slope diagonal covering
$(a,a^{\prime})$ and $(b,b^{\prime})$ give a total of $2p+1$ such lines, which
is an odd number of such lines. However, we said that the number of lines of
slope $+1$ is $2k$, which is even, and this contradiction finishes the proof.

##  4 Concluding remarks

###  4.1 Placements that correspond to the zero vector

When $n=8k+1$ we can describe some placements that correspond to the zero
vector in Nul $A$ as follows. Select $k$ squares with coordinates
$(x_{1},y_{1}),\ldots,(x_{k},y_{k})$ such that these meet the following
conditions: $0<x_{i},y_{i}\leq 2k,\frac{y_{i}}{x_{i}}<1$, the values
$x_{1},y_{1},\ldots,x_{k},y_{k}$ are distinct and for any $i\neq j$ we have
$\frac{y_{i}}{x_{i}}\neq\frac{y_{j}}{x_{j}}$. Next consider ‘folding’ the
board across the $x-$axis, then folding it across the $y-$axis, and finally
folding it along the line $y=x$. Consider the $8$ squares that ‘stack’ on top
of a selected square and place a queen in each of these. Do this for each
selected square. We have now placed $8k$ queens. Finally, place a lonely queen
at $(0,0)$, for a total of $8k+1$ queens. It is easy to check that this
placement is in Nul $A$. From a geometric perspective, the placement will look
like $k$ octagons that are ‘nested’ and centered at $(0,0)$. The placement
given in Figure 3 is such a placement derived from this scheme where $n=9$ and
the set of initial selected squares consists of one square with coordinates
$(4,1)$; it is one of six possible placements for $n=9$ via this scheme.

When $n=5$ there are no placements that meet the conditions of Case 2 since a
queen in $\mathcal{Q}\setminus\mathcal{Q}^{\prime}$ forces the existence of
four other queens and together with the lonely queen the placement would have
at least $6>n$ queens. When $n=8k+5$ we have not found any placements that
correspond to the zero vector in Nul $A$.

###  4.2 Other cases to consider

When $n=4k+3$, we also believe that $m_{3}(n)\geq n+1.$ At this point of our
investigations, we have not been able to establish this lower bound. However,
there are some sub-cases for which we can establish this improved lower bound:
we sketch the proof here by following the polynomial method template provided
in Case 1 of the proof of Theorem 2. By considering a good placement ${\cal
Q}$ of size at most $4k+3$ on $\overline{B}_{n}$ with at most $2k$ defined
lines of slope $\pm 1$, the polynomial of degree $8k+4$

$g(x,y)=\prod_{j=1}^{2k+2}(x-\alpha_{j})(y-\beta_{j})\prod_{j=1}^{2k}(x-y-\gamma_{j})(x+y-\delta_{j})$

can be constructed so as to vanish on all squares of the chessboard yet has a
non-zero coefficient on the monomial $x^{4k+2}y^{4k+2}$ by the Binomial
Theorem. Thus, by Theorem 3 we reach a contradiction. This approach will
settle all cases where $q^{\prime}\geq 2$ and some others. However, one
particularly challenging sub-case that we cannot resolve is when
$q^{\prime}=0$ and the number of lines defined by ${\cal Q}$ is maximized
(i.e. there are $2k+1$ lines defined by ${\cal Q}$ in each of the four
slopes). In this sub-case, one might consider the following polynomial

$h(x,y)=\prod_{j=1}^{2k+1}(x-\alpha_{j})(y-\beta_{j})(x-y-\gamma_{j})(x+y-\delta_{j}).$

A leading monomial suitable for an application of the Combinatorial
Nullstellensatz is again $x^{4k+2}y^{4k+2}$. However, this monomial has the
same coefficient as the same monomial in
$x^{2k+1}y^{2k+1}(x^{2}-y^{2})^{2k+1},$ which is zero. Thus, a polynomial
method approach seems problematic. At the same time, the combinatorial
approach that comes towards the end of Case 2 in the proof of Theorem 2 seems
problematic for the following reason. In such a placement, there will be up to
four queens that are neither lonely nor in a defining line of each possible
slope. Gaining information about the coordinates of these queens appears
difficult and it could be that these particular queens are located on the
perimeter of $U$.

Turning to a different set of cases: there are small cases of $n$ even where
it has been established that $m_{3}(n)=n+1.$ From Table 1, we see that these
values are $n=8,14,16,20,22,24$. There is no discernible pattern to us.

Recently, Di Stefano, Klavz̆ar, Krishnakumar, Tuite and Yero [4] have extended
Gardner’s problem to graph theory. This, too, looks like an interesting line
of inquiry.

##  5 Acknowledgments

The second author wishes to thank Fulbright Austria and the Algebra and Number
Theory Group at the University of Graz for the support of his work and their
warm hospitality. This work commenced when he was a visitor there in the
spring of 2022.

The authors wish to thank Greg Warrington of U. Vermont for reading an early
draft and suggesting the idea of rotating the placement at the end of Case 2
in the proof of Theorem 2.

## References

  * [1] O. Aichholzer, D. Eppstein, E. Hainzl,  Geometric dominating sets—a minimum version of the no-three-in-line problem.  Comput. Geom. 108(2023), Paper No. 101913, 15 pp.
  * [2] N. Alon,  Combinatorial Nullstellensatz.  Recent trends in combinatorics (Mátraháza, 1995). Combin. Probab. Comput., 8 no. 1–2 (1999) 7–29.
  * [3] A. Cooper, O. Pikhurko, J. Schmitt, G. Warrington,  Martin Gardner’s minimum no-3-in-a-line problem.  Amer. Math. Monthly 121 (2014), no. 3, 213–221 and https://arxiv.org/abs/1206.5350v2.
  * [4] G. Di Stefano, S. Klavz̆ar, A. Krishnakumar, J. Tuite, I. Yero,  Lower General Position Sets in Graphs.  arXiv:2306.09965v1
  * [5] M. Gardner,  Papers 1957–1986 (Box 37, Folders 12 and 13, and Box 40, Folder 4).  Special Collections and University Archives, Stanford University, Stanford, CA.
  * [6] —,  Penrose Tiles to Trapdoor Ciphers…And the Return of Dr. Matrix, revised edition.  The Mathematical Association of America, Washington, DC 1997\.
  * [7] —,  Martin Gardner’s Mathematical Games.  MAA Spectrum, Mathematical Association of America, Washington, DC 2005.
  * [8] D. Knuth,  personal communication.
  * [9] B. Nica,  Polynomials over structured grids.  Combin. Probab. Comput. 32 (2023), no.2, 284–298.
  * [10] R. Pratt,  personal communication.
  * [11] N. Sloane,  The on-line encyclopedia of integer sequences, (http://www.research.att.com/$\sim$njas/sequences).