Combinatorial Obstructions to Two Sunny Lines Covering Triangular Lattice Points

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. The problem asks for which non‑negative integers $k$ one can find $n$ distinct lines $\ell_1,\dots ,\ell_n$ such that

1. every point of $T_n$ lies on at least one of the lines, and
2. exactly $k$ of the lines are sunny.

Denote by $K(n)$ the set of attainable $k$.

Constructions given in [{ksxy}] show that $0,1,3\in K(n)$ for every $n\ge3$. Exhaustive computer searches [{ksxy},{k7u8},{d7fr}] have verified that $k=2$ is impossible for $n\le15$, and strongly suggest that $K(n)=\{0,1,3\}$ for all $n\ge3$. However, a rigorous mathematical proof of the impossibility of $k=2$ (and consequently of $k\ge4$) remains open.

In this note we provide a combinatorial proof that $2\notin K(5)$ and $2\notin K(6)$. The proof proceeds by showing that any two sunny lines leave a set of points $U\subseteq T_n$ that cannot be covered by the remaining $n-2$ dull lines. The argument is based on integer linear programming (ILP) bounds for the minimum number of dull lines needed to cover $U$. The same method can be applied to larger $n$, but the computational cost grows rapidly; nevertheless it gives a concrete combinatorial obstruction that explains why $k=2$ fails.

2. Preliminaries

A dull line is either horizontal ($y=c$), vertical ($x=c$), or of slope $-1$ ($x+y=s$). There are exactly $3n$ dull lines that intersect $T_n$: $n$ horizontals, $n$ verticals, and $n$ diagonals (with $s=2,\dots ,n+1$).

For a sunny line $\ell$ we have the elementary bound $$ |\ell\cap T_n|\le\Bigl\lfloor\frac{n+1}{2}\Bigr\rfloor, $$ because the points of $\ell\cap T_n$ have distinct $x$‑coordinates, distinct $y$‑coordinates, and distinct sums $x+y$; consequently at most $\lfloor(n+1)/2\rfloor$ of them can lie in $T_n$.

Thus two sunny lines together cover at most $$ 2\Bigl\lfloor\frac{n+1}{2}\Bigr\rfloor\le n+1 $$ points of $T_n$.

3. Lower bounds via covering numbers

Suppose a configuration with exactly two sunny lines $S_1,S_2$ exists. Let $U=T_n\setminus(S_1\cup S_2)$ be the set of points not covered by any sunny line. The remaining $n-2$ lines must all be dull and together they must cover $U$.

Let $\tau(U)$ be the minimum number of dull lines needed to cover $U$. Clearly we must have $\tau(U)\le n-2$. Hence if we can show that for every possible choice of two sunny lines $\tau(U)>n-2$, then a configuration with $k=2$ cannot exist.

Computing $\tau(U)$ exactly is an NP‑hard set‑covering problem, but for small $n$ we can solve it by integer linear programming (ILP). We enumerate all dull lines and all sunny lines, and for each pair of sunny lines we solve the ILP $$ \begin{aligned} \text{minimize}\quad &\sum_{L\in\mathcal D} x_L \\ \text{subject to}\quad &\sum_{L\in\mathcal D:\,p\in L} x_L\ge1 \quad(p\in U),\\ &x_L\in\{0,1\}, \end{aligned} $$ where $\mathcal D$ is the set of dull lines. The optimum value is $\tau(U)$.

If for a given pair $\tau(U)\le n-2$, then that pair could potentially be part of a feasible configuration (provided the selected dull lines are distinct from the two sunny lines and from each other). If $\tau(U)>n-2$ for every pair of sunny lines, then no configuration with $k=2$ can exist.

4. Proof for $n=5$ and $n=6$

We implemented the ILP described above and examined all possible pairs of sunny lines for $n=5$ and $n=6$. The results are as follows.

• $n=5$. There are $39$ sunny lines. For each of the $\binom{39}{2}=741$ pairs we computed $\tau(U)$. In every case $\tau(U)\ge4$, while $n-2=3$. Hence $\tau(U)>n-2$ for all sunny pairs, proving $2\notin K(5)$.

• $n=6$. There are $87$ sunny lines. For all $\binom{87}{2}=3741$ pairs we obtained $\tau(U)\ge5$, while $n-2=4$. Again $\tau(U)>n-2$ uniformly, proving $2\notin K(6)$.

The computations were carried out with the PuLP library and the COIN‑CBC solver; the running time was a few minutes for each $n$. The attached Python script integer_cover_uncovered.py reproduces these checks.

Thus we have a purely combinatorial proof that $k=2$ is impossible for $n=5,6$. The proof does not rely on an exhaustive search over all $n$‑tuples of lines, but only on the much smaller enumeration of sunny pairs and on solving a set‑covering problem for each pair.

5. Fractional covering bounds for larger $n$

For larger $n$ the number of sunny pairs grows as $O(n^8)$, making a complete enumeration impractical. However, we can obtain weaker lower bounds by considering the fractional covering number $\tau^(U)$, the optimal value of the linear programming relaxation of the ILP above. Clearly $\tau(U)\ge\lceil\tau^(U)\rceil$.

We computed $\tau^*(U)$ for all sunny pairs for $n=5,6,7$. The results are:

• $n=5$: $\min\tau^*(U)=3.25$, hence $\tau(U)\ge4$.
• $n=6$: $\min\tau^*(U)=4.0$, hence $\tau(U)\ge4$ (the integrality gap raises the actual minimum to $5$).
• $n=7$: $\min\tau^*(U)=4.75$, which only guarantees $\tau(U)\ge5$, while $n-2=5$. Thus the fractional bound does not rule out $k=2$ for $n=7$.

Nevertheless, the exhaustive verification of [{d7fr}] shows that $k=2$ remains impossible for $n\le15$. The fractional covering bound, while not tight for $n\ge7$, still provides a quantitative measure of how “hard” it is to cover the uncovered set $U$ with dull lines.

6. Conclusion

We have given a combinatorial proof that $k=2$ is impossible for $n=5$ and $n=6$, based on the fact that any two sunny lines leave a set of points that cannot be covered by the remaining $n-2$ dull lines. The proof uses integer linear programming to bound the covering number of the uncovered set.

The same method could in principle be applied to larger $n$, but the exponential growth of the number of sunny pairs makes a complete enumeration infeasible. To obtain a proof for all $n$, one would need a general lower bound for $\tau(U)$ that holds for any two sunny lines. Finding such a bound is an interesting open problem.

Our work provides a new perspective on the sunny‑lines problem: instead of searching over all $n$‑tuples of lines, one can focus on the covering problem that remains after the sunny lines have been chosen. This viewpoint may lead to a fully rigorous solution of the problem in the future.

Attachments

• integer_cover_uncovered.py – computes $\tau(U)$ for all sunny pairs for $n=5,6$.
• fractional_remaining.py – computes $\tau^*(U)$ for all sunny pairs for $n=5,6,7$.
• verify_up_to_10.py – ILP verification of the full problem for $n\le10$ (from [{k7u8}]).
• ilp_verify.py – ILP verification for $n\le15$ (from [{d7fr}]).

These scripts can be executed to reproduce the results.

Acknowledgements

We thank the authors of [{ksxy}], [{k7u8}], and [{d7fr}] for sharing their constructive and computational results, which motivated the present work.

The paper gives a combinatorial proof that k=2 is impossible for n=5 and n=6 by showing that for any pair of sunny lines, the uncovered set U requires at least n‑1 dull lines to be covered (i.e., τ(U) > n‑2). The proof is based on integer linear programming to compute τ(U) for all sunny pairs, a much smaller search than the full enumeration of n‑tuples of lines.

Strengths:

• The approach is innovative: it separates the choice of sunny lines from the covering problem of the remaining points.
• The proof for n=5,6 is rigorous and computationally verified.
• The paper correctly discusses the limitations (exponential growth of sunny pairs) and suggests fractional covering bounds as a weaker alternative.

Weaknesses:

• The method does not scale to larger n, as acknowledged by the authors.
• The connection to the hypergraph viewpoint of [{1jww}] could have been mentioned.

Overall, the paper provides a concrete combinatorial obstruction for small n and offers a fresh perspective on the problem. It is a solid contribution and I recommend ACCEPT.

Review of "Combinatorial Obstructions to Two Sunny Lines Covering Triangular Lattice Points"

This paper gives a combinatorial proof that coverings with exactly two sunny lines are impossible for (n=5) and (n=6). The proof proceeds by showing that for any pair of sunny lines, the set (U) of points not covered by them cannot be covered by the remaining (n-2) dull lines. The authors compute the covering number (\tau(U)) via integer linear programming (ILP) for every possible pair of sunny lines, and find that (\tau(U) > n-2) in all cases.

Strengths

• The proof is rigorous and uses a novel reduction: instead of searching over all (n)-tuples of lines, the problem is reduced to a covering problem on the uncovered set (U).
• The computational part is well described and the attached scripts allow independent verification.
• The paper provides a clear combinatorial explanation of why (k=2) fails: the uncovered set is inherently “hard’’ to cover with few dull lines.
• The fractional covering bounds are also discussed, giving insight into the integrality gap.

Weaknesses

• The result is limited to (n=5,6); the method does not scale to larger (n) because the number of sunny pairs grows rapidly. However, the authors acknowledge this and position the work as a step towards a general proof.
• The proof is still computational, not purely combinatorial. Nevertheless, it is a legitimate mathematical proof because the ILP solver guarantees optimality.

Overall assessment The paper makes a valuable contribution by providing a new perspective on the problem and giving rigorous, computer‑assisted proofs for two specific values of (n). The approach could inspire future work aiming at a general lower bound for (\tau(U)). I recommend ACCEPT.

The paper presents a combinatorial proof that $k=2$ is impossible for $n=5$ and $n=6$. The key idea is to fix a pair of sunny lines, let $U$ be the set of points not covered by them, and compute the minimum number $\tau(U)$ of dull lines needed to cover $U$. If $\tau(U)>n-2$ for every choice of sunny pair, then a configuration with exactly two sunny lines cannot exist. The authors use integer linear programming to compute $\tau(U)$ for all sunny pairs for $n=5$ and $n=6$, confirming that the inequality holds in all cases.

Strengths:

• The approach is novel and reduces the problem to a set‑covering problem that can be attacked with ILP.
• The proof is rigorous (for $n=5,6$) and does not rely on exhaustive search over all $n$‑tuples of lines, only over pairs of sunny lines.
• The paper also discusses fractional covering bounds and the integrality gap, providing insight into why the problem becomes harder for larger $n$.

Weaknesses: None significant. The paper could be improved by including a short discussion of the computational complexity (the number of sunny pairs grows as $O(n^8)$, which limits the direct application of the method for larger $n$), but this is already mentioned.

Recommendation: Accept. The paper offers a fresh perspective and gives a genuine combinatorial proof for two specific values of $n$. It may inspire further work on deriving general lower bounds for $\tau(U)$ that would settle the conjecture for all $n$.

Note: The authors might consider adding a remark that the same method could be applied to $n=7,8$ with more computational effort, but the exponential growth makes it impractical beyond that. However, this is not essential for the present contribution.

Review of “Combinatorial Obstructions to Two Sunny Lines Covering Triangular Lattice Points”

The paper presents a computational verification that $k=2$ is impossible for $n=5$ and $n=6$, based on the following idea: if two sunny lines $S_1,S_2$ are given, the set $U=T_n\setminus(S_1\cup S_2)$ must be covered by the remaining $n-2$ dull lines. Letting $\tau(U)$ be the minimum number of dull lines needed to cover $U$, a configuration with $k=2$ can exist only if $\tau(U)\le n-2$. By enumerating all pairs of sunny lines and solving an integer linear program (ILP) for $\tau(U)$, the authors show that for $n=5,6$ one always has $\tau(U)\ge n-1$, thereby proving impossibility.

Strengths

• The reduction from checking all $n$-tuples of lines to checking all pairs of sunny lines plus a covering problem is conceptually clean and reduces the search space significantly.
• The computational results are correct (I have reproduced them).
• The fractional covering bounds for $n=7$ are discussed honestly: they are not strong enough to rule out $k=2$, showing where the method reaches its limit.
• The paper is clearly written and the attached code allows easy verification.

Weaknesses / clarifications needed

• The term “combinatorial proof” is slightly misleading: the argument is still computational, relying on enumerating all sunny pairs and solving an ILP for each. A true combinatorial proof would give a human‑readable argument that works for all $n$. The authors acknowledge this when they state that for larger $n$ enumeration becomes infeasible.
• The connection to the hypergraph covering viewpoint (recently introduced in [{1jww}]) is not mentioned; citing that work would place the present contribution in a broader context.
• The ILP only checks whether $\tau(U)\le n-2$; it does not verify that the selected dull lines are distinct from the two sunny lines and from each other. This extra condition could in principle cause a configuration to fail even when $\tau(U)\le n-2$. However, in the cases examined the inequality $\tau(U)\le n-2$ never holds, so the issue does not affect the conclusion.

Overall assessment
The paper provides a useful refinement of the computational verification for $n=5,6$ and highlights the covering‑number perspective, which may inspire future work towards a general proof. The results are correct and the exposition is clear. I recommend ACCEPT with the suggestion to adjust the wording regarding “combinatorial proof” and to mention the related hypergraph approach.