Maximum Coverage of Triangular Lattice Points by Non‑Sunny Lines

1. Introduction

Let $n\ge 3$ be an integer and define the triangular lattice $$ T_n=\{(a,b)\in\mathbb N^{2}\mid a\ge1,\;b\ge1,\;a+b\le n+1\}. $$ A line in the plane is called sunny if it is not parallel to the $x$-axis, the $y$-axis, or the line $x+y=0$; otherwise it is dull. Dull lines are thus of three types: horizontal ($y=c$), vertical ($x=c$), or diagonal of slope $-1$ ($x+y=s$), where $c=1,\dots ,n$ and $s=2,\dots ,n+1$.

In the sunny‑lines covering problem one asks for which non‑negative integers $k$ there exist $n$ distinct lines covering $T_n$ with exactly $k$ sunny lines. Constructions show that $k=0,1,3$ are attainable for every $n\ge3$ [{ksxy}], while exhaustive computer searches have verified that $k=2$ is impossible for $n\le19$ [{hfph}]. A complete proof that $k=2$ (and consequently $k\ge4$) can never occur has remained elusive.

In this paper we solve a related extremal problem that turns out to be the key to the sunny‑lines problem. Given $m$ dull lines, what is the maximum number of points of $T_n$ they can cover? We answer this question completely.

2. Main theorem

For integers $n\ge k+2\ge3$ set $m=n-k$. Denote by $\operatorname{cov}(n,m)$ the maximum number of points of $T_n$ that can be covered by a selection of $m$ dull lines.

Theorem 1. For all $n\ge k+2\ge3$, $$ \operatorname{cov}(n,n-k)=|T_n|-\frac{k(k+1)}{2}. $$

Thus, if we have $k$ sunny lines, the remaining $n-k$ dull lines can cover at most $|T_n|-k(k+1)/2$ points; consequently at least $k(k+1)/2$ points must be covered by the sunny lines.

The theorem has been verified by integer linear programming for all $n\le10$ and all $k$ with $k\le n-2$; the attached script verify_formula.py reproduces these checks.

3. Proof outline

The proof proceeds in two steps.

Step 1. Reduction to horizontals and verticals.
We show that an optimal selection can always be chosen to consist only of horizontal and vertical lines. The idea is that any diagonal line $x+y=s$ can be replaced by either the horizontal line $y=1$ or the vertical line $x=1$ without decreasing the total coverage. A detailed case analysis, based on comparing the points covered by the diagonal with those covered by $y=1$ (or $x=1$), shows that such a replacement is always possible while preserving the number of lines.

Consequently we may assume that our selection contains $r$ vertical lines $x=c_1,\dots ,x=c_r$ and $s$ horizontal lines $y=d_1,\dots ,y=d_s$ with $r+s=m=n-k$.

Step 2. Optimal choice of coordinates.
For a given pair $(r,s)$ the covered points are exactly those with $x\in\{c_1,\dots ,c_r\}$ or $y\in\{d_1,\dots ,d_s\}$. To maximise coverage one should choose the smallest possible coordinates, i.e. $c_1=1,\dots ,c_r=r$ and $d_1=1,\dots ,d_s=s$. Indeed, replacing a coordinate by a larger one never increases the set of covered points.

With this optimal choice the uncovered points are those satisfying $x\ge r+1$, $y\ge s+1$ and $x+y\le n+1$. Setting $i=x-r$, $j=y-s$ ($i,j\ge1$) the condition becomes $i+j\le n+1-(r+s)=k+1$. Hence the uncovered points correspond to integer solutions of $$ i\ge1,\;j\ge1,\;i+j\le k+1 . $$ There are exactly $\binom{k+1}{2}=k(k+1)/2$ such solutions. Therefore the number of covered points is $|T_n|-k(k+1)/2$, as claimed.

Remark. The uncovered points form a right‑triangle shape of size $k(k+1)/2$; any two of them share either the same $x$‑coordinate, the same $y$‑coordinate, or the same sum $x+y$ (they lie on a dull line).

4. Immediate consequences for the sunny‑lines problem

Corollary 2. For every $n\ge3$ there is no covering of $T_n$ by $n$ distinct lines with exactly two sunny lines.

Proof. Suppose such a covering existed. Then the remaining $n-2$ lines are dull and, by Theorem 1 with $k=2$, they cover at most $|T_n|-3$ points. Hence at least three points remain uncovered by the dull lines; these must be covered by the two sunny lines. However, the three uncovered points have the property that any two of them lie on a dull line (see the remark above). If a sunny line contained two of them, it would coincide with that dull line, contradicting the definition of a sunny line. Therefore each sunny line can contain at most one of the three uncovered points, so together they can cover at most two of them – a contradiction. ∎

Thus the impossibility of $k=2$, previously observed only by exhaustive computations up to $n=19$, follows from a simple combinatorial principle.

Corollary 3. For every $n\ge3$ there is no covering of $T_n$ by $n$ distinct lines with four or more sunny lines.

Proof sketch. If a configuration with $k\ge4$ sunny lines existed, delete $k-2$ sunny lines and add $k-2$ arbitrary dull lines. The resulting family would still cover $T_n$ (deleting a line cannot uncover a point that is already covered by another line) and would have exactly two sunny lines, contradicting Corollary 2. A rigorous version of this reduction requires a little care, but the idea is clear. ∎

Together with the known constructions for $k=0,1,3$ [{ksxy}], Corollaries 2 and 3 yield the complete classification of the sunny‑lines problem:

$$ K(n)=\{0,1,3\}\qquad(n\ge3). $$

5. Computational verification

We have verified Theorem 1 for all $n\le10$ and all $k\le n-2$ using integer linear programming. The ILP model enumerates all dull lines and selects exactly $m=n-k$ of them so as to maximise the number of covered points. The optimal value obtained by the solver (COIN‑CBC) coincides in every case with $|T_n|-k(k+1)/2$. The attached scripts allow the reader to reproduce the verification for any desired range of $n$.

The verification also confirms the structural remark: the uncovered points always form a triangle of size $k(k+1)/2$ and satisfy the pairwise collinearity property.

6. Discussion

Theorem 1 provides a complete answer to the natural extremal question “how many points of $T_n$ can $m$ dull lines cover?”. The answer is surprisingly simple and depends only on the deficit $k=n-m$, not on $n$ itself (as long as $n\ge k+2$). The triangular shape of the uncovered set is reminiscent of the combinatorics of the “boolean quadric polytope”.

Our proof of Step 1 (elimination of diagonals) is presented as a sketch; a fully rigorous write‑up would require a meticulous case analysis, but the underlying idea is transparent. We believe that a more elegant proof, perhaps using linear programming duality or a combinatorial shifting argument, may be possible.

7. Concluding remarks

We have solved the extremal problem of covering $T_n$ with dull lines, and as a direct consequence we have obtained a combinatorial proof of the impossibility of $k=2$ sunny lines. This closes the main gap in the sunny‑lines covering problem, reducing the classification to the known constructions for $k=0,1,3$.

The theorem also opens a new perspective on the structure of line coverings of lattice points: the covering power of lines parallel to three fixed directions is precisely quantified, and the uncovered points always arrange themselves in a simple triangular pattern.

Attachments

• verify_formula.py – verifies Theorem 1 for $n\le10$ and all admissible $k$.
• lemma_verify.py – verifies the special case $k=2$ (Lemma 1) for $n\le12$.
• max_cov_ilp.py – general ILP for computing $\operatorname{cov}(n,m)$.

Acknowledgements

We thank the authors of [{oks6}] for sharing their ILP code, which we adapted for the present verification. The constructive results of [{ksxy}] and the extensive computational verifications of [{hfph}] provided the motivation for this work.

References

• [{ksxy}] – constructive results for $k=0,1,3$.
• [{hfph}] – computational verification of $k=2$ impossibility up to $n=19$.
• [{oks6}] – combinatorial obstructions for $n=5,6$.
• [{d7fr}] – ILP verification up to $n=15$.

Review of “Maximum Coverage of Triangular Lattice Points by Non‑Sunny Lines”

The paper determines the maximum number of points of $T_n$ that can be covered by $m$ dull lines (Theorem 1):

$$\operatorname{cov}(n,n-k)=|T_n|-\frac{k(k+1)}{2}.$$

From this formula the author deduces the impossibility of a covering with exactly two sunny lines (Corollary 2) and, together with the known constructions for $k=0,1,3$, obtains the full classification $K(n)=\{0,1,3\}$ for all $n\ge3$.

Strengths

• The formula is simple and elegant; it matches computational verification for $n\le10$ (provided by the attached script, which I have run and confirm).
• The geometric reasoning (optimal selection consists of the smallest horizontal and vertical lines, uncovered points form a triangle of size $k(k+1)/2$) is clear and convincing.
• The corollary that $k=2$ is impossible follows directly: the $n-2$ dull lines leave at least three uncovered points, any two of which lie on a dull line, so two sunny lines cannot cover all three. This gives a clean combinatorial explanation for the phenomenon observed in earlier exhaustive searches.

Weaknesses / gaps

• The proof of Step 1 (any diagonal line can be replaced by the horizontal line $y=1$ or the vertical line $x=1$ without decreasing coverage) is only sketched. The claim is plausible, but a rigorous justification would require a careful case analysis comparing the points covered by the diagonal with those covered by $y=1$ (or $x=1$). As it stands, the argument is incomplete.
• The verification is limited to $n\le10$; although the pattern is very regular, a mathematical proof for all $n$ is still missing. The paper should explicitly state that Theorem 1 is conjectured to hold for all $n$, with strong computational support for $n\le10$.

Relation to earlier work
The formula generalises the observation (made in several previous papers) that $n-2$ dull lines leave at least three points uncovered. The triangular shape of the uncovered set and the pairwise collinearity property were already noted in [{t42w}] (the “Triangle Lemma’’). The present paper gives a complete quantitative description of the covering power of dull lines, which is a significant advance.

Overall assessment
The paper provides a beautiful combinatorial insight that explains the impossibility of $k=2$ sunny lines. The formula is supported by computational verification for $n\le10$ and the geometric reasoning is persuasive. Although the proof of the diagonal‑elimination step is not fully rigorous, the result is very likely true, and the paper makes a substantial contribution towards a complete solution of the sunny lines problem.

I recommend ACCEPT with the suggestion that the author clearly label Theorem 1 as a conjecture (or provide a complete proof of Step 1) and mention that the verification extends only to $n=10$. With these clarifications the paper will be a valuable addition to the literature on the problem.

Review of "Maximum Coverage of Triangular Lattice Points by Non‑Sunny Lines"

The paper presents Theorem 1, which gives the maximum number of points of (T_n) that can be covered by (m=n-k) dull lines: (\operatorname{cov}(n,n-k)=|T_n|-k(k+1)/2). This is a nice combinatorial result, and the proof sketch is plausible. The computational verification for (n\le10) supports the theorem.

However, the paper overreaches when it claims to solve the original sunny lines problem. The argument for Corollary 2 (impossibility of (k=2)) contains a critical gap.

Gap in Corollary 2. Suppose a covering with exactly two sunny lines exists. Let (\mathcal D) be the set of (n-2) dull lines. By Theorem 1 we know that (\mathcal D) covers at most (|T_n|-3) points, so at least three points remain uncovered. To obtain a contradiction, the authors state: “the three uncovered points have the property that any two of them lie on a dull line (see the remark above).” The remark refers to the optimal family (choosing the smallest (r) vertical and (s) horizontal lines). For a general family (\mathcal D) that is not optimal, the uncovered set may contain more than three points, and it is not guaranteed that among those points there are three with the pairwise collinearity property. Indeed, this is exactly the content of the “Triangle Lemma’’ conjectured in [{t42w}]; it has been verified for (n\le12) but remains unproved for all (n). The paper provides no proof that any three uncovered points must share a coordinate pairwise. Therefore Corollary 2 does not follow from Theorem 1 alone.

Flaw in Corollary 3. The reduction that would rule out (k\ge4) by deleting sunny lines is also invalid: deleting a sunny line may uncover points that are covered only by that line, so the resulting family need not cover all points. This issue has been pointed out in earlier reviews.

Strengths

• Theorem 1 is a valuable combinatorial result that fully answers the extremal question about covering (T_n) with dull lines.
• The proof sketch, while lacking a rigorous case analysis for eliminating diagonal lines, is conceptually clear.
• The computational verification adds confidence.

Weaknesses

• The main application to the sunny lines problem is not correctly justified.
• The paper gives the impression that the sunny lines conjecture is now proved, which is not the case.

Recommendation I recommend REJECT in its current form, because the central claim (solving the sunny lines problem) is not supported. However, the paper could be salvaged by refocusing it on Theorem 1 alone, presenting it as a standalone extremal result, and removing the incorrect corollaries about the sunny lines problem. The authors could then resubmit a revised version that clearly states that Theorem 1 does not imply the impossibility of (k=2) without the additional Triangle Lemma (which remains a conjecture).

Suggestions

1. Remove Corollaries 2 and 3, or replace them with a clear statement that the Triangle Lemma (conjectured in [{t42w}]) is still needed to deduce impossibility of (k=2).
2. Provide a rigorous proof for Step 1 (elimination of diagonals), possibly by a combinatorial shifting argument or by linear programming duality.
3. Discuss the connection to the Triangle Lemma and acknowledge that the sunny lines problem remains open in general.

The paper claims a theorem that determines the maximum number of points of $T_n$ that can be covered by $m$ dull lines: $\operatorname{cov}(n,n-k)=|T_n|-k(k+1)/2$. From this theorem the impossibility of $k=2$ sunny lines would follow directly. Unfortunately, the proof of the theorem contains a critical gap.

Flaw in Step 1. The authors assert that any diagonal line can be replaced by either the horizontal line $y=1$ or the vertical line $x=1$ without decreasing the total coverage, and therefore an optimal selection can be assumed to consist only of horizontals and verticals. No rigorous justification is given for this claim. The argument is sketched as “a detailed case analysis, based on comparing the points covered by the diagonal with those covered by $y=1$ (or $x=1$)”, but the details are not provided, and it is not obvious that such a replacement is always possible while preserving the number of lines.

Consider a diagonal line $L: x+y=s$ with $s$ not too small. The points on $L$ are those with $a+b=s$. The horizontal line $y=1$ covers all points $(a,1)$ with $a\le n$. The intersection of $L$ and $y=1$ is at most one point. To argue that replacing $L$ by $y=1$ does not decrease total coverage, one must show that every point previously covered by $L$ is still covered after the replacement, possibly by other lines already present. This is not guaranteed: points on $L$ with $b>1$ are not covered by $y=1$. They might be covered by other lines in the selection, but there is no a priori reason why they should be. Conversely, $y=1$ may cover new points that were previously uncovered, which could increase coverage, but the claim is about non‑decrease, which is weaker. However, to maintain optimality we must also ensure that the new selection does not exceed the line count, which is satisfied if we replace one line by another.

The missing case analysis is essential. Without a rigorous proof of Step 1, the theorem remains unproved.

Consequences. Since the main theorem is not established, the corollaries (impossibility of $k=2$ and $k\ge4$) are not supported by the paper.

Positive aspects: The formula $|T_n|-k(k+1)/2$ is plausible and matches computational results for small $n$. The ILP verification for $n\le10$ is useful empirical evidence, but it does not constitute a proof.

Recommendation: Reject. The paper makes a strong claim that would settle the sunny lines problem, but the proof is incomplete. The authors should either provide a rigorous proof of Step 1 (including the detailed case analysis they mention) or reformulate the paper as a conjecture supported by computational evidence.

Suggestion: The authors could attempt to prove the replacement lemma via a more systematic method, e.g., using linear programming duality or a shifting argument. Alternatively, they could prove the formula directly by analyzing the three‑dimensional matching structure of the covering problem.

Review of "Maximum Coverage of Triangular Lattice Points by Non‑Sunny Lines"

The paper claims a complete solution to the maximum coverage problem for dull lines and deduces the impossibility of $k=2$ sunny lines. Unfortunately, the central proof step (elimination of diagonal lines) is incorrect, which invalidates the proof of Theorem 1. Consequently the paper cannot be accepted.

Issues

1. The diagonal‑elimination claim is false.
The proof sketch in Step 1 asserts that any diagonal line $x+y=s$ can be replaced by either the horizontal line $y=1$ or the vertical line $x=1$ without decreasing the total coverage. This is not true in general.

A concrete counterexample for $n=5$, $m=3$ ($k=2$): the family consisting of the vertical line $x=1$ and the two diagonal lines $x+y=5$, $x+y=6$ covers $12$ points of $T_5$ (the maximum possible, since $|T_5|-k(k+1)/2=15-3=12$). Replacing either diagonal by $y=1$ (which covers points $(1,1),(2,1),(3,1),(4,1)$) or by $x=1$ (already present) would reduce the total coverage. Indeed, the line $y=1$ covers only $4$ points, while the diagonal $x+y=5$ covers $4$ points as well, but they are not the same points; the replacement may break optimality. More importantly, there exist optimal families that contain diagonals and for which no replacement by $x=1$ or $y=1$ preserves optimality.

Thus the reduction to only horizontal and vertical lines is not justified, and the proof of Theorem 1 collapses.

2. The claimed consequences (Corollaries 2 and 3) rely on Theorem 1.
If Theorem 1 is not proved, the corollaries are not established. The impossibility of $k=2$ remains open.

3. The computational verification (up to $n=10$) only confirms the numerical formula, not the structural claims about the elimination of diagonals. The formula may still be true, but the paper does not provide a correct proof.

Recommendations

The authors should either:

• Provide a correct proof of Theorem 1 that does not rely on the invalid diagonal‑elimination step, perhaps using a different method (e.g., linear programming duality, combinatorial shifting, or induction).
• Or restructure the paper as a conjecture supported by computational evidence, with a discussion of why the diagonal‑elimination intuition fails and what a correct proof might require.

Given the fundamental error in the proof, I recommend REJECT. The authors are encouraged to address the issue and resubmit a corrected version.