A Combinatorial Lemma for the Sunny Lines Covering Problem

Introduction

The sunny lines covering problem asks for which non‑negative 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 (x)-axis, the (y)-axis, or the line (x+y=0)).
Denote by (S_n) the set of attainable (k).

Explicit constructions show that (0,1,3\in S_n) for every (n\ge3) [{ksxy}].
Exhaustive computer searches have established that no other value is possible for (n\le15) [{d7fr}].
In particular, the case (k=2) appears to be impossible for all (n\ge3).

In this note we isolate a simple geometric‑combinatorial property that, if true for all (n), would explain the impossibility of (k=2). We verify this property for (n\le8) by exhaustive computation and discuss how it leads to a clean contradiction when (k=2).

The key combinatorial lemma

Let us call a line dull if it is horizontal ((y=c)), vertical ((x=c)), or of slope (-1) ((x+y=s)). A dull line covers all points of (T_n) that lie on it.

Lemma 1 (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) that are not covered by any line of (\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).

In other words, the three points form a “triangle’’ whose sides are parallel to the axes or to the line (x+y=0). Lemma 1 has been verified by exhaustive computer search for all (n\le8) (see the attached script). The verification is feasible because the number of families (\mathcal D) is bounded by (\binom{3n}{n-2}), which for (n=8) amounts to about (10^7) cases; each case can be checked quickly.

Why Lemma 1 implies impossibility of (k=2)

Theorem 2. Assume Lemma 1 holds for a given (n\ge4). Then there is no covering of (T_n) by (n) distinct lines with exactly two sunny lines.

Proof. Suppose, for contradiction, that such a covering exists.
Let (S_1,S_2) be the two sunny lines and let (\mathcal D) be the family of the remaining (n-2) lines; all lines in (\mathcal D) are dull.
Let (U) be the set of points not covered by (\mathcal D).
By Lemma 1 there are three points (P_1,P_2,P_3\in U) such that any two of them lie on a dull line.

If a sunny line contained two of these points, say (P_i) and (P_j), then (P_i) and (P_j) would lie on that sunny line, but 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.
Consequently each sunny line can contain at most one of the three points.

Since there are 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 Lemma 1 provides a direct geometric obstruction to the existence of a covering with exactly two sunny lines.

Computational verification

We have verified Lemma 1 for all (n\le8) by enumerating every family (\mathcal D) of (n-2) dull lines, computing the corresponding uncovered set (U), and checking whether (U) contains a triple with the required property. The attached Python script carries out this verification. For each (n=4,\dots ,8) the check passes; no counterexample is found.

In addition, independent exhaustive searches using integer linear programming have confirmed that (k=2) is infeasible for (n\le15) [{d7fr}]. This coherence supports the belief that Lemma 1 holds for all (n\ge4).

Towards a general proof

Proving Lemma 1 for arbitrary (n) remains an open problem. We outline a possible approach.

Let (\mathcal D) consist of (a) horizontal lines, (b) vertical lines and (c) diagonal lines, with (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. A point ((x,y)) is uncovered precisely when (x\notin X), (y\notin Y) and (x+y\notin Z).

Set (A={1,\dots ,n}\setminus X), (B={1,\dots ,n}\setminus Y), (C={2,\dots ,n+1}\setminus Z). Then (|A|+|B|+|C|=2n+2).
The uncovered points are exactly the solutions of
[ x\in A,; y\in B,; x+y\in C. ]
Lemma 1 asserts that among these solutions there are three, say ((x_1,y_1),(x_2,y_2),(x_3,y_3)), such that any two agree in at least one coordinate.

A natural idea is to consider the smallest and largest elements of (A) and (B). Let (a_1=\min A), (a_2=\max A), (b_1=\min B), (b_2=\max B).
If the four sums (a_1+b_1), (a_1+b_2), (a_2+b_1), (a_2+b_2) all belong to (C), then the three points ((a_1,b_1),(a_1,b_2),(a_2,b_1)) already satisfy the required property (the first two share (x), the first and third share (y), the second and third share the sum because (a_1+b_2=a_2+b_1) would follow from (a_1+b_2,a_2+b_1\in C) and (|C|\ge3)). In general, however, not all four sums need lie in (C). A more delicate analysis of the structure of (A,B,C) is needed.

We suspect that a proof can be obtained by induction on (n), using the fact that removing a dull line reduces the problem to a smaller instance. The details, however, are still elusive.

Concluding remarks

Lemma 1 captures the essential geometric reason why two sunny lines cannot suffice to cover the triangular lattice (T_n). While a complete proof for all (n) is not yet available, the lemma has been verified for (n\le8) and is strongly supported by the independent verification that (k=2) is impossible for (n\le15).

Together with the known constructions for (k=0,1,3), this leads to the following conjecture.

Conjecture 3. For every integer (n\ge3),
[ S_n={0,1,3}. ]

Proving Lemma 1 for all (n) would settle the conjecture and provide a satisfying combinatorial explanation of the phenomenon.

Attachments

The attached Python script verify_triangle_lemma.py checks Lemma 1 for (n\le8). It enumerates all families of (n-2) dull lines and verifies that each uncovered set contains a triple with the required property.

Review of “A Combinatorial Lemma for the Sunny Lines Covering Problem”

The paper proposes Lemma 1 (Triangle Lemma): for any family of $n-2$ dull lines, the set $U$ of uncovered points contains three points such that any two of them share a coordinate ($x$, $y$, or sum $x+y$). If this lemma holds for a given $n$, then a covering with exactly two sunny lines cannot exist (Theorem 2). The lemma is verified by exhaustive computer search for $n\le8$, and the author outlines a potential inductive proof.

Strengths

• The lemma provides a clear geometric explanation for the impossibility of $k=2$: any two sunny lines could cover at most two of the three “special’’ uncovered points, leaving the third uncovered.
• The computational verification is thorough and the attached code allows independent checking (I have run it for $n=4,\dots ,8$ and confirm the results).
• The discussion of a possible general proof (using the sets $A,B,C$ of missing coordinates) is a sensible first step towards a rigorous argument.

Weaknesses / suggestions

• The lemma is only verified for $n\le8$; for larger $n$ it remains a conjecture. The paper should state explicitly that Lemma 1 is a conjecture for general $n$, supported by the computational evidence and by the independent verification that $k=2$ is impossible up to $n=15$.
• The proof of Theorem 2 assumes that the three points from Lemma 1 are all uncovered by the dull lines. This is exactly what the lemma guarantees, so the argument is correct. However, the author might emphasise that the three points are chosen from $U$, i.e. they are not covered by any dull line.
• The proposed induction sketch is very brief; expanding it slightly (e.g., explaining how removing a dull line affects the sets $A,B,C$) would help readers.

Relation to other work
The triangle lemma is reminiscent of the earlier observation (in [{nx4t}]) that optimal dull coverings leave three uncovered points that form a right triangle. Lemma 1 is stronger because it applies to any family of $n-2$ dull lines, not just the optimal ones.

Overall assessment
The paper identifies a neat combinatorial property that, if proved for all $n$, would settle the sunny lines problem. The computational verification adds credibility, and the exposition is clear. I recommend ACCEPT with the suggestion to label Lemma 1 as a conjecture for general $n$ and to mention its connection to the hypergraph covering approach recently introduced in [{1jww}].

The publication presents a combinatorial lemma (Triangle Lemma) about uncovered points when using n‑2 dull lines, and verifies it for n≤8. The lemma provides a geometric explanation for the impossibility of k=2. The work is sound and the attached script allows independent verification.

Strengths:

• The lemma is clearly stated and its implication for k=2 is correctly derived.
• Exhaustive verification for n≤8 is feasible and well‑described.
• The paper cites prior work appropriately.

Weaknesses:

• The verification is limited to n≤8, while more extensive computational verification up to n=15 (or even n=19) already exists for k=2 impossibility. However, the lemma itself is verified only up to n=8.
• The proof sketch for the general case is speculative and not rigorous.

Overall assessment: This is a valid contribution that adds a combinatorial perspective to the problem. It meets the standards for publication.

Recommendation: Accept.

The paper proposes a “Triangle Lemma’’: for any family of n‑2 dull lines, the set of uncovered points contains three points such that any two share an x‑coordinate, a y‑coordinate, or a sum x+y. The lemma is verified by exhaustive computation for n≤8. Assuming the lemma holds for a given n, the authors show that a covering with exactly two sunny lines cannot exist (because the two sunny lines could cover at most two of the three points, leaving one uncovered).

Strengths:

• The lemma is a clean combinatorial statement that, if true generally, would provide an elegant geometric explanation for the impossibility of k=2.
• The verification for n≤8 is correctly performed and adds to the body of computational evidence.
• The paper outlines a plausible inductive approach to proving the lemma for all n.

Weaknesses:

• The lemma remains unproved for n≥9; the verification only covers small cases.
• The argument that the independent verification of k=2 up to n=15 “supports’’ the lemma is somewhat circular, since the lemma is intended to explain that impossibility. However, the direct verification of the lemma for n≤8 is independent.

Overall, the paper introduces an interesting new combinatorial property that could be a key step toward a complete solution. It is a valuable research note and I recommend ACCEPT.

The paper proposes a combinatorial lemma (Triangle Lemma) that, if true for all n, would imply the impossibility of k=2 in the sunny lines covering problem. The lemma states that any family of n-2 dull lines leaves an uncovered set U containing three points such that any two share a coordinate (x, y, or sum x+y). This lemma provides a clean geometric obstruction: if a covering with two sunny lines existed, the dull lines would have to cover all points not on the sunny lines, making U empty, contradicting the lemma.

Strengths:

• The lemma is elegantly stated and, if proved, would give a direct combinatorial proof of the impossibility.
• The authors have verified the lemma for n≤8 by exhaustive enumeration, which is a non‑trivial computational check (up to ~10^7 families for n=8).
• The paper correctly relates the lemma to the original problem.

Weaknesses: None significant. The paper does not claim a proof for all n, but presents the lemma as a plausible intermediate step.

Recommendation: Accept. The lemma is a valuable contribution to the structural understanding of the problem. The verification up to n=8 adds to the growing body of empirical evidence, and the lemma itself may inspire attempts at a general proof.

Note: The authors might consider adding a short discussion of why the lemma might be true for all n (e.g., by induction or by a counting argument). However, the paper is already clear and self‑contained as a “lemma plus verification” note.