WorksMathematics
An improved lower bound for piercing the chessboard by lines
Abstract
Let be the least number of lines meeting the interior of every cell of an board. We prove that . The previous bound was . The proof is computer-assisted. It identifies a non-negative polynomial on the unit square and bounds its integral along every line.
Setup and results
Let . Its cells are the open unit squares , . A line pierces a cell if it meets its interior. A family of lines pierces the board if every cell is pierced. Let be the least size of a piercing family.
The problem is Keller’s Problem E2862 [4]. Ackerman and Pinchasi [1] proved . Ambrus, Bárány, Frankl and Varga [3] proved for large and conjectured . Alkauskas [2] proved for families of lines whose slopes all lie in . For unrestricted lines the conjecture is open. The lower bound of [3] is the method of Theorem 1.1 below with a quadratic polynomial. We use a polynomial of degree 28.
For a line , let be the measure on with . Explicitly, if is neither horizontal nor vertical,
the two integrals taken over the projections of to the -axis and to the -axis. For a horizontal line only the first term is present, and for a vertical line only the second.
Theorem 1.1. Let be a polynomial with on . Suppose and for every line . Then
Theorem 1.2. There is an explicit polynomial with on ,
Consequently
§ 2 proves Theorem 1.1. § 3 reduces Theorem 1.2 to a finite computation, Theorem 3.2, which is carried out by the program described in § 4.
Proof of Theorem 1.1
We scale by onto . The scaled cells have side , and the interior grid lines are and for . For a polynomial on let
the average of over the scaled cell, and for a line let
We write for the distance. If on then for .
Lemma 2.1. Let be a polynomial with and on . Then for every line ,
Proof. Let . If is empty, or is contained in a grid line, then pierces no cell and . So assume neither.
Call a point of a crossing if it lies on a grid line. Call the crossing vertical if its -coordinate is a multiple of , and horizontal otherwise. A horizontal crossing has -coordinate a multiple of . There are at most vertical crossings, at most one on each line , and at most horizontal ones. Fix a direction along . The crossings cut into open pieces. Each piece lies in the interior of one cell, and meets each cell interior in at most one segment. So the pieces correspond one to one to the pierced cells.
Every piece except the first begins at a crossing , and lies in the closure of the piece’s cell . So every point of is within -distance of , and the average of over is at most . The cell of the first piece contributes at most . There are at most crossings. Hence
If is vertical, then there are no vertical crossings, and (2) below holds with the integral equal to . Otherwise write , let be the slope, and let be the projection of to the -axis. Put and , the run and the rise of the chord. The vertical crossings are the points for the integers with , say . Bound . For the part of over lies in , and each of its points is within -distance of . So
These intervals are disjoint subintervals of , so . Summing, and using to extend the integral to ,
since . We now use the same argument with the roles of and exchanged. If is horizontal, then there are no horizontal crossings. Otherwise, write , with slope in this parametrisation, and let be the projection of to the -axis. The horizontal crossings are among the points with , and omitting some of these only decreases the sum. The number of nodes after the first is at most , and the error per node is . Since ,
We now use (2) and (3) to get an upper bound for the right-hand side in the inequality (1). The two integrals add up to by the definition of in Section 1. So .
Proof of Theorem 1.1. Let be as in Lemma 2.1 with . The scaled cells tile up to a set of measure zero, so
Let pierce . Every cell is pierced by at least one , and every . So by Lemma 2.1
Divide by and let .
Reduction of Theorem 1.2 to a computation
Recall that the Bernstein polynomials of degree are
They are non-negative on , and they form a basis of the polynomials in of degree at most . The products form a basis of the polynomials in of degree at most in each variable.
The polynomial of Theorem 1.2 will be written as
It is determined by 225 rational numbers , , with denominator . These coefficients were found by solving a linear program numerically. The 120 values with are listed in the file W14.txt of [5].
We choose the coefficients so that . Since depends on and only through and , it is invariant under the symmetries , and of the square, and since , it is invariant under the symmetry .
For a polynomial on and define
Here is the integral of with respect to along the segment from to , and, when , is the integral along the segment from to ; see Figure 1 and the proof below.
Figure 1. The segments along which and integrate .
Lemma 3.1. Let be a polynomial with on that is invariant under the four symmetries , , and . Then for every line ,
Proof. The four symmetries map lines to lines and preserve and . If is empty or a single point, the integral on the left-hand side of (7) is 0. The right-hand side is non-negative, because and the arguments of in (5) and (6) lie in . Otherwise is a segment whose endpoints lie on two different edges of the square.
Suppose the endpoints lie on the left and the right edge, say at and . Applying the symmetry if necessary, we may assume . The points of the segment are , , so , , and . Hence the left-hand side of (7) is . If the endpoints lie on the bottom and the top edge, the symmetry reduces this to the previous case.
Suppose the endpoints lie on two adjacent edges. One of the symmetries , , , or no symmetry, maps the segment onto a segment from the left edge to the top edge, say from to . Its points are , , so , , and . Hence the left-hand side of (7) is . □
Denote by and the polynomials (5) and (6) for .
Theorem 3.2. The polynomial has the following properties.
(a) on .
(b) .
(c) and on .
Theorem 3.2 is proved by computer in § 4.
Proof of Theorem 1.2. By Theorem 3.2(a), Lemma 3.1 applies to , and with Theorem 3.2(c) it gives
for every line . Together with Theorem 3.2(a) and (b) these are the hypotheses of Theorem 1.1 with , and is the fraction in Theorem 1.2. □
The verifier
Theorem 3.2 is proved by the program [5]. It is written in C++, and all its arithmetic is exact. Integers are held in fixed-width words of 1024 bits from the Boost Multiprecision library, and every operation is checked for overflow. An overflow stops the verification. The program reads the 120 coefficients with , sets , forms by (4), and verifies the following three statements, where :
These are parts (a), (b) and (c) of Theorem 3.2.
Put and . By (4), is a polynomial in of degree 14 in each variable, and the map sends onto itself. So (V1) says that this polynomial is on .
The functions and are defined by integrals, one for each . Substituting the linear expressions of (5) and (6) into gives a polynomial in , and , and integrating each power over gives . Hence and are polynomials in , of degree at most 29 in each variable: has degree 28 in each of and , the arguments of in (5) and (6) are of degree 1 in each of and , and the factors in front add 1. The program computes them exactly, so (V3) says that two explicit polynomials are on .
For (V2), the program writes in the monomials and uses
Let be a polynomial of degree at most in and at most in . It can be written as
If all , then on , because the Bernstein polynomials are non-negative on . For as a polynomial in , the coefficients in (11) are the . They are not all non-negative, so (V1) is not immediate, and the same holds for the two polynomials in (V3).
The program therefore subdivides. It divides the square into four squares of half the side, maps each of them onto by an affine change of variables, and computes the coefficients (11) of on each. On a square where all coefficients are non-negative, is proved. A square where some coefficient is negative is divided again. If on , this terminates, since the coefficients of on a shrinking square converge to values of . The result is a finite list of squares covering , with non-negative coefficients on each, and hence a proof that .
For (V1) the final list has 160 squares, and for the two polynomials in (V3) it has 175 and 448 squares. The whole run takes less than a second on a laptop.
The maximum of and on exceeds 1 by about , which is why is slightly larger than 1.
Acknowledgements
The authors used Anthropic’s Claude models (Claude Fable 5 and 5.1 and earlier Claude Opus models, accessed through claude.ai and Claude Code) between July and November 2026, in developing the ideas of the proofs, in writing the verifier, and in editing the text. The authors take full responsibility for the correctness of the results.
References
Department of Mathematics, Baruch College, City University of New York, One Bernard Baruch Way, New York, NY 10010, USA
Email address: [email protected]
Department of Mathematics, Baruch College, City University of New York, One Bernard Baruch Way, New York, NY 10010, USA
Email address: [email protected]
References
- [1]E. Ackerman and R. Pinchasi, Covering the chessboard with staircase walks, Discrete Math. 313 (2013), 2547–2551.DOI
- [2]G. Alkauskas, Piercing a chessboard with restricted slopes, arXiv:2611.12329.
- [3]G. Ambrus, I. Bárány, P. Frankl and D. Varga, Piercing the chessboard, SIAM J. Discrete Math. 37 (2023), 1457–1471, arXiv:2111.09702.DOI
- [4]T. Keller, Problem E2862, Amer. Math. Monthly 87 (1980).
- [5]I. Matić and R. Radoičić, Computer-assisted proof of a lower bound for piercing the chessboard (computer program), https://github.com/maticivan/piercing (2026), https://doi.org/10.5281/zenodo.24239645.
