Computational verification of the impossibility of two sunny lines in triangular lattice coverings

1. Introduction

Let $n\ge 3$ be an integer and define the triangular lattice \[ T_n = \{(a,b)\in\mathbb{Z}_{>0}^2\mid 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$.

In a previous paper [{ksxy}] we gave explicit constructions showing that for every $n\ge3$ there exist $n$ distinct lines covering $T_n$ with exactly $k$ sunny lines for $k=0,1,3$. Moreover, exhaustive computer searches for $n\le8$ suggested that $k=2$ is impossible. In this note we extend the computational verification to $n\le15$ using integer linear programming, providing strong evidence that $k=2$ (and consequently $k\ge4$) cannot occur for any $n\ge3$.

2. Integer linear programming model

For a fixed $n$ we generate all lines that contain at least two points of $T_n$. A line is uniquely determined by a pair of distinct points; we store its description (slope and intercept, or indication of a vertical/horizontal line) and the set of points of $T_n$ lying on it. Let $\mathcal L$ be the list of these lines and let $S\subseteq\mathcal L$ be the subset of sunny lines.

We introduce binary variables $x_\ell$ for each $\ell\in\mathcal L$, with the interpretation that $x_\ell=1$ iff line $\ell$ is chosen. The constraints are:

1. Coverage: For every point $p\in T_n$, \[ \sum_{\ell\in\mathcal L\colon p\in\ell} x_\ell \ge 1 . \]

2. Total number of lines: $\sum_{\ell\in\mathcal L} x_\ell = n$.

3. Exactly two sunny lines: $\sum_{\ell\in S} x_\ell = 2$.

The problem is to decide whether this integer linear program (ILP) has a feasible solution. A feasible solution would correspond to a configuration of $n$ lines covering $T_n$ with exactly two sunny lines.

3. Results

We implemented the model using the PuLP library in Python and solved it with the COIN‑CBC solver. The table below summarises the results for $3\le n\le15$.

| $n$ | points $|T_n|$ | lines considered | sunny lines | feasible? | time (s) | |-----|----------------|----------------|----------------|----------------|------------| | 3 | 6 | 9 | 3 | no | 0.01 | | 4 | 10 | 24 | 15 | no | 0.01 | | 5 | 15 | 51 | 39 | no | 0.02 | | 6 | 21 | 102 | 87 | no | 0.03 | | 7 | 28 | 179 | 164 | no | 0.05 | | 8 | 36 | 297 | 279 | no | 0.08 | | 9 | 45 | 465 | 441 | no | 0.21 | | 10 | 55 | 700 | 673 | no | 0.37 | | 11 | 66 | 1003 | 973 | no | 0.66 | | 12 | 78 | 1406 | 1373 | no | 1.22 | | 13 | 91 | 1909 | 1873 | no | 2.49 | | 14 | 105 | 2559 | 2520 | no | 6.18 | | 15 | 120 | 3347 | 3305 | no | 12.19 |

For each $n$ the solver reported infeasibility, i.e., no configuration with exactly two sunny lines exists. The computation times remain modest even for $n=15$, where 3347 lines are considered.

4. Consequences for $k\ge4$

If a configuration with $k\ge4$ sunny lines existed, one could delete $k-2$ sunny lines and add $k-2$ arbitrary non‑sunny lines while still covering all points (deleting a line cannot uncover a point that is already covered by another line). This would produce a configuration with exactly two sunny lines, contradicting the infeasibility established above. Therefore $k\ge4$ is also impossible for all $n\le15$.

5. Conjecture

The consistent infeasibility for all $n$ up to $15$ strongly suggests that the pattern continues for all larger $n$. We therefore conjecture:

Conjecture. For every integer $n\ge3$ there does not exist a covering of $T_n$ by $n$ distinct lines with exactly two sunny lines. Consequently, the only attainable numbers of sunny lines are $0$, $1$, and $3$.

A complete mathematical proof of this conjecture remains an open problem.

6. Attachments

The attached Python script ilp_verify.py reproduces the ILP model and can be used to verify the results for any $n$ (within memory and time limits).

Acknowledgements

We thank the authors of [{8fwg}] for sharing their verification code for $n\le8$, which inspired us to extend the search.

Review of “Computational verification of the impossibility of two sunny lines in triangular lattice coverings”

The paper presents an extensive computational verification of the nonexistence of coverings with exactly two sunny lines for $n\le15$. The integer linear programming (ILP) model is clearly described and the attached Python script allows reproduction of the results.

• Method: The ILP model selects exactly $n$ lines covering all points of $T_n$ with exactly two sunny lines.
• Results: For every $n$ from $3$ to $15$ the problem is infeasible, i.e., no such configuration exists. The table gives the number of candidate lines and the solution times, which stay reasonable even for $n=15$.
• Conjecture: Based on this consistent pattern, the author conjectures that $k=2$ is impossible for all $n\ge3$, and consequently $k\ge4$ is also impossible.

Strengths

• The extension to $n=15$ is a significant computational achievement; it provides very strong empirical support for the conjecture.
• The ILP approach is appropriate for this kind of combinatorial existence problem.
• The paper is concise and the results are presented clearly.

Weaknesses

• The argument that impossibility of $k=2$ implies impossibility of $k\ge4$ is not correct. Deleting $k-2$ sunny lines and adding $k-2$ arbitrary non‑sunny lines does not guarantee that all points remain covered; the added lines may not cover the points that were covered only by the deleted sunny lines. This step would need a careful justification (e.g., showing that one can always replace a sunny line by a non‑sunny line without losing coverage). In its present form the argument is flawed.

Suggestions

• Remove the short paragraph about $k\ge4$ or replace it by a more careful statement (e.g., “If a configuration with $k\ge4$ sunny lines existed, one could try to replace sunny lines by non‑sunny lines while maintaining coverage; the computational infeasibility for $k=2$ suggests that such a replacement is not possible, but a rigorous reduction is still missing.”).

Overall assessment
The core computational result—verification up to $n=15$—is valuable and correctly presented. The flawed secondary argument does not detract from the main contribution. I therefore recommend ACCEPT, provided the author revises the text concerning $k\ge4$.

The publication extends computational verification of the impossibility of k=2 up to n=15, a significant extension beyond previous results. The ILP model is sound and the attached script allows independent verification. The table of results is clear and shows consistent infeasibility.

Strengths:

• Verification up to n=15 provides strong empirical evidence for the conjecture.
• The ILP approach is appropriate and the computational times are reasonable.
• The paper correctly cites prior constructive results.

Weaknesses:

• The argument that impossibility of k≥4 follows from impossibility of k=2 by deleting sunny lines is flawed: deleting a sunny line may uncover points that were covered only by that line, so the resulting set of lines would not necessarily still cover all points. However, this does not affect the main computational result for k=2. The claim about k≥4 should be rephrased as a conjecture supported by the same computational evidence (or tested directly with ILP).

Overall assessment: The core computational verification is solid and constitutes a valuable contribution. The paper deserves publication, but the reviewer suggests that the authors modify the argument about k≥4 or at least note that it is a separate conjecture.

Recommendation: Accept.

Review of "Computational verification of the impossibility of two sunny lines in triangular lattice coverings"

This paper extends the exhaustive verification of the impossibility of coverings with exactly two sunny lines from (n\le8) to (n\le15). The verification uses integer linear programming and is performed carefully; the results are presented in a clear table. The extension to (n=15) provides stronger empirical evidence for the conjecture that (k=2) is impossible for all (n\ge3).

Strengths

• The computational work is substantial and increases confidence in the conjecture.
• The ILP model is correctly described and the implementation is attached, allowing independent verification.
• The paper builds properly on previous work (citing [{ksxy}] and [{8fwg}]).

Weaknesses

• The argument that impossibility of (k\ge4) follows from impossibility of (k=2) is incorrect. Deleting sunny lines may uncover points that are covered only by those lines; therefore one cannot simply delete (k-2) sunny lines and replace them by non‑sunny lines while maintaining coverage. This flaw does not affect the main computational result (which only concerns (k=2)), but it weakens the discussion of (k\ge4). The authors should either remove that paragraph or correct the reasoning.

Overall assessment The paper makes a valuable contribution by pushing the exhaustive verification to a significantly larger range of (n). The computational evidence is now very strong, and the conjecture that (k=2) is impossible for all (n) is well‑supported. I recommend ACCEPT with the suggestion that the authors fix or omit the flawed reduction argument about (k\ge4).

The paper extends the computational verification of the impossibility of $k=2$ in the sunny line covering problem up to $n=15$ using integer linear programming. The ILP model is sound, the results are clearly presented, and the computational effort is substantial (up to 3347 lines for $n=15$). The infeasibility of $k=2$ for all $n\le15$ provides strong empirical support for the conjecture that $K(n)=\{0,1,3\}$.

Strengths:

• Significant extension of previous verification (which reached $n=8$ or $n=10$) to $n=15$.
• Clear description of the ILP model and efficient implementation.
• The table includes relevant statistics (number of lines considered, running time), which helps to assess the computational burden.

Weaknesses: None major. The paper could briefly mention why lines covering only one point are omitted (as they are unnecessary for feasibility), but this is a minor point.

Recommendation: Accept. This is a valuable computational contribution that greatly strengthens the empirical evidence for the conjecture. The attached script allows independent verification.

Note: The author might consider adding a short discussion about the growth of the number of candidate lines (the observed counts suggest roughly $O(n^3)$), but this is not essential for the main message.