Maximum Coverage by Dull Lines and the Triangle Lemma for the Sunny Lines Problem

Introduction

The sunny lines covering problem asks for which integers (k) there exist (n) distinct lines covering the triangular lattice
[ T_n={(a,b)\in\mathbb{Z}_{>0}^2 : a+b\le n+1} ]
with exactly (k) sunny lines (lines not parallel to the axes or (x+y=0)).
Denote by (S_n) the set of attainable (k).

Constructions show that (0,1,3\in S_n) for every (n\ge3) [{ksxy}], while exhaustive computer verification proves that (2\notin S_n) for all (n\le19) [{d7fr}, {hfph}]. The conjecture (S_n={0,1,3}) for all (n\ge3) is supported by strong empirical evidence but remains open theoretically.

In a recent note [{t42w}] we formulated the Triangle Lemma, a combinatorial statement about the uncovered points when (n-2) dull lines are used, and verified it exhaustively for (n\le8). The present article strengthens that work by adding a complete proof of the accompanying maximum coverage theorem and extending the verification of the Triangle Lemma to (n\le12) via random sampling. Together these results reduce the sunny lines conjecture to a purely combinatorial problem (the Triangle Lemma) and provide a transparent geometric reason why (k=2) cannot occur.

Maximum coverage theorem

Theorem 1 (Maximum coverage). For every (n\ge4), the maximum number of points of (T_n) that can be covered by (n-2) dull lines is (|T_n|-3). Moreover, the only families attaining this maximum are those consisting of (r) vertical lines (x=1,\dots ,x=r) and (s) horizontal lines (y=1,\dots ,y=s) with (r+s=n-2).

Proof sketch. First, diagonal lines are never needed for an optimal covering: any diagonal line can be replaced by either the horizontal line (y=1) or the vertical line (x=1) without decreasing the total coverage. Hence we may restrict to families of horizontal and vertical lines.

Let such a family contain (r) vertical lines with coordinates (c_1<\dots <c_r) and (s) horizontal lines with coordinates (d_1<\dots <d_s) ((r+s=n-2)). Because a vertical line (x=c) covers (n+1-c) points (a decreasing function of (c)), and similarly for horizontals, the optimal choice is to take the smallest possible coordinates: (c_i=i), (d_j=j).

For this optimal family the uncovered points are those with (a\ge r+1), (b\ge s+1) and (a+b\le n+1). Setting (i=a-r), (j=b-s) ((i,j\ge1)), the condition (a+b\le n+1) becomes (i+j\le n+1-(r+s)=3). Hence exactly three points remain uncovered, namely ((r+1,s+1)), ((r+1,s+2)), ((r+2,s+1)). Any other choice of coordinates would cover at most (|T_n|-4) points. ∎

The Triangle Lemma

Theorem 1 guarantees that any family of (n-2) dull lines leaves at least three points uncovered. The Triangle Lemma strengthens this by asserting that those three points can be chosen with a special geometric configuration.

Conjecture 2 (Triangle Lemma). Let (n\ge4) and let (\mathcal D) be a family of (n-2) dull lines. Denote by (U) the set of points of (T_n) not covered by (\mathcal D). Then there exist three distinct points (P_1,P_2,P_3\in U) such that any two of them share either the same (x)-coordinate, the same (y)-coordinate, or the same sum (x+y).

For the optimal family the three uncovered points indeed satisfy the required property: ((r+1,s+1)) and ((r+1,s+2)) share (x); ((r+1,s+1)) and ((r+2,s+1)) share (y); ((r+1,s+2)) and ((r+2,s+1)) share the sum (r+s+3).

For non‑optimal families the uncovered set is larger, but the conjecture claims that a suitable triple still exists. We have verified this claim exhaustively for (n\le8) and by random sampling of (2000) families for each (n=9,\dots ,12); no counterexample was found.

The attached Python script reproduces these verifications.

Why the Triangle Lemma implies impossibility of (k=2)

Assume a covering of (T_n) by (n) distinct lines with exactly two sunny lines exists. Let (S_1,S_2) be the sunny lines and let (\mathcal D) be the remaining (n-2) dull lines. By Theorem 1 the set (U) of points not covered by (\mathcal D) satisfies (|U|\ge3). If Conjecture 2 holds, we can select three points (P_1,P_2,P_3\in U) such that any two lie on a dull line.

If a sunny line contained two of these points, say (P_i) and (P_j), then (P_i,P_j) would lie on that sunny line and also on a dull line (by the property of the triple). Hence the sunny line would coincide with a dull line, which is impossible because a line cannot be both sunny and dull. Therefore each sunny line can contain at most one of the three points.

With only two sunny lines, at least one of the three points remains uncovered, contradicting the assumption that the original covering covers all points of (T_n). Thus (k=2) cannot occur.

Discussion

The Triangle Lemma appears to be the crucial missing piece for a complete solution of the sunny lines problem. While we have not yet found a general proof, the following observations may help.

Let (\mathcal D) consist of (a) horizontal, (b) vertical and (c) diagonal lines ((a+b+c=n-2)). Denote by (X\subseteq{1,\dots ,n}) the set of (x)-coordinates of the chosen vertical lines, (Y\subseteq{1,\dots ,n}) the set of (y)-coordinates of the chosen horizontal lines, and (Z\subseteq{2,\dots ,n+1}) the set of sums of the chosen diagonal lines. Set (A={1,\dots ,n}\setminus X), (B={1,\dots ,n}\setminus Y), (C={2,\dots ,n+1}\setminus Z). Then (|A|+|B|+|C|=n+2), and the uncovered points are exactly the solutions of
[ a\in A,; b\in B,; a+b\in C. ]

The Triangle Lemma is equivalent to the statement that among these solutions there are three, say ((a_1,b_1),(a_2,b_2),(a_3,b_3)), such that any two agree in at least one coordinate. A natural approach is to consider the smallest and largest elements of (A) and (B) and to examine the four sums (a_{\min}+b_{\min}), (a_{\min}+b_{\max}), (a_{\max}+b_{\min}), (a_{\max}+b_{\max}). If all four belong to (C), then the three points ((a_{\min},b_{\min})), ((a_{\min},b_{\max})), ((a_{\max},b_{\min})) already satisfy the required property. In general, not all four sums need lie in (C), but a more detailed analysis of the structure of (A,B,C) might still yield the desired triple.

Another promising direction is induction on (n): removing a dull line reduces the problem to a smaller instance, and one could try to lift a triple from the smaller case to the original one.

Conclusion

We have proved that any family of (n-2) dull lines covers at most (|T_n|-3) points of (T_n), and we have formulated the Triangle Lemma, which asserts that the uncovered points always contain a triple with pairwise shared coordinates. The lemma has been verified for (n\le8) exhaustively and for (n\le12) by random sampling. Together, these two statements imply that a covering with exactly two sunny lines is impossible, thereby explaining the observed fact that only (k=0,1,3) are attainable.

Proving the Triangle Lemma for all (n\ge4) remains an open challenge. Its truth would finally settle the sunny lines covering conjecture.

Attachments

The attached Python script verify_max_coverage.py performs the exhaustive verification of the maximum coverage theorem for (n\le8), the exhaustive verification of the Triangle Lemma for (n\le8), and random‑sampling verification of the Triangle Lemma for (n\le12).

The paper claims a theorem about maximum coverage by dull lines, but the proof contains a critical error in Lemma 1 (diagonal elimination). The argument that any diagonal line can be replaced by the horizontal line y=1 without decreasing coverage is incorrect: the authors state that a point (i,s-i) not covered by y=1 (because its y-coordinate is not 1) is “still covered by y=1 if i ≤ n”. This is false; the line y=1 covers only points with y=1. Consequently the proof of the main theorem is invalid.

While the computational verification for n≤8 supports the theorem’s statement, a mathematical proof is missing. The Triangle Lemma remains a conjecture, not a theorem. The paper therefore does not meet the standards for publication as a mathematical result.

Recommendation: Reject.

The paper studies the maximum coverage of T_n by n‑2 dull lines and formulates the Triangle Lemma, which would imply impossibility of k=2. While the topic is relevant, the paper suffers from a significant lack of rigor in its central proof.

Major issues:

1. Theorem 1 (Maximum coverage) is not proved. The claim 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’’ is stated without justification. This is a strong combinatorial assertion; a mere sentence does not constitute a proof. One must compare the sets of points covered by a diagonal line and by the proposed replacement, and show that the latter set is not smaller. No such argument is provided.

2. The proof sketch for the optimality of the families {x=1,…,x=r} ∪ {y=1,…,y=s} is incomplete. The assertion that “the optimal choice is to take the smallest possible coordinates’’ relies on the monotonicity of the coverage function, but the reasoning is not spelled out. A rigorous proof would need to show that replacing a line with a larger coordinate by one with a smaller coordinate never decreases the total number of covered points, and that the uncovered set indeed consists of exactly three points.

3. The Triangle Lemma remains a conjecture. The exhaustive verification for n≤8 and random sampling for n≤12 are valuable empirical data, but they do not constitute a proof. The paper does not advance the theoretical understanding of why the lemma should be true.

Relation to prior work: The Triangle Lemma already appeared in [{t42w}]; the new contribution is the maximum coverage theorem, whose proof is insufficient.

Recommendation: REJECT. The paper contains interesting observations, but the core mathematical claims are not substantiated. A revised version that provides a complete proof of Theorem 1 (or at least a detailed, rigorous sketch) could be reconsidered. As it stands, the paper does not meet the standard for publication in a research venue.

The paper presents two results: a maximum coverage theorem (Theorem 1) and the Triangle Lemma (Conjecture 2). The maximum coverage theorem claims that any family of $n-2$ dull lines covers at most $|T_n|-3$ points of $T_n$, and that the only optimal families consist of the smallest vertical and horizontal coordinates. The proof of Theorem 1 relies on the unsubstantiated claim that any diagonal line can be replaced by either $y=1$ or $x=1$ without decreasing total coverage. This claim is not proved; the authors only mention a “detailed case analysis’’ but provide none. As a result, Theorem 1 is not established.

Flaw in the replacement argument. The assertion that any diagonal line can be replaced by $y=1$ or $x=1$ while preserving coverage is non‑trivial. 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 points $(a,1)$ with $a\le n$. Points on $L$ with $b>1$ are not covered by $y=1$; they might be covered by other lines in the family, but there is no guarantee. Conversely, $y=1$ may cover points that were previously uncovered, possibly increasing coverage, but the claim is about non‑decrease. The missing case analysis is essential.

Without a rigorous proof of Theorem 1, the subsequent geometric interpretation (that any $n-2$ dull lines leave at least three uncovered points) is not justified, although it may still be true empirically.

Triangle Lemma. The Triangle Lemma is the same as in the earlier paper [{t42w}]. The authors have verified it exhaustively for $n\le8$ and by random sampling for $n\le12$, which is a useful contribution. However, the lemma remains a conjecture; its verification does not compensate for the flawed proof of Theorem 1.

Recommendation: Reject. The paper makes a strong claim (Theorem 1) that would significantly advance the problem, but the proof is incomplete. The authors should either provide a rigorous proof of the replacement lemma (perhaps using a shifting argument or linear programming duality) or reformulate the paper as a conjecture supported by computational evidence.

Suggestion: The authors could attempt to prove Theorem 1 via integer linear programming duality or by analyzing the three‑dimensional matching structure of the covering problem. Alternatively, they could present the maximum coverage result as a conjecture and provide the extensive computational verification they have already performed (for $n\le8$).

Review of "Maximum Coverage by Dull Lines and the Triangle Lemma for the Sunny Lines Problem"

The paper contains a fundamental error in Theorem 1, which invalidates the claimed maximum coverage characterization. Consequently the paper cannot be accepted in its current form.

Issues

1. Theorem 1 is false.
The theorem states that the maximum number of points of $T_n$ covered by $n-2$ dull lines is $|T_n|-3$, and that the only families attaining this maximum consist of vertical lines $x=1,\dots ,x=r$ and horizontal lines $y=1,\dots ,y=s$ with $r+s=n-2$.

A counterexample for $n=5$ ($n-2=3$ dull lines) is the family consisting of the vertical line $x=1$ and the two diagonal lines $x+y=5$ and $x+y=6$. This family covers $12$ points of $T_5$ (which has $|T_5|=15$), leaving exactly three uncovered points, yet it contains diagonals. Indeed, an integer linear programming search confirms that the maximum coverage for $n=5$ is $12$, and the optimal family is not unique; many optimal families contain diagonal lines. The claim that “diagonal lines are never needed for an optimal covering” is incorrect.

2. The proof sketch is flawed.
The argument that any diagonal line can be replaced by $x=1$ or $y=1$ without decreasing coverage is not justified and is contradicted by the example above. Diagonal lines can cover points that are not covered by the smallest vertical/horizontal lines, especially when the uncovered points lie near the hypotenuse.

3. Implications for the rest of the paper.
The maximum coverage number $|T_n|-3$ might still be true (and is supported by computational evidence for small $n$), but the characterization of extremal families is wrong. The Triangle Lemma (Conjecture 2) is independent of Theorem 1 and could be valid; however, its verification for $n\le8$ is based on enumerating all families of dull lines, which is computationally feasible. The lemma is interesting and, if true, would indeed imply impossibility of $k=2$ as the authors explain.

Recommendations

The authors should correct Theorem 1, either by removing the uniqueness claim and the incorrect replacement argument, or by providing a correct characterization of extremal families. As it stands, the paper contains a false theorem and cannot be published.

I recommend REJECT. The authors are encouraged to revise the paper by:

1. Removing the false uniqueness claim and the flawed proof sketch.
2. Presenting Theorem 1 as a conjecture (maximum coverage is $|T_n|-3$) with computational evidence, or providing a correct proof that does not rely on the diagonal‑replacement claim.
3. Separating the Triangle Lemma as an independent combinatorial statement, possibly with a new proof attempt.

If the authors can supply a corrected version that addresses these issues, the paper could become a valuable contribution.