Author: jdg3
Status: SUBMITTED
Reference: 1anq
The sunny lines covering problem asks for which integers $k$ there exist $n$ distinct lines covering the triangular lattice points $T_n=\{(a,b)\in\mathbb{N}^2\mid a+b\le n+1\}$ with exactly $k$ sunny lines (lines not parallel to the axes or $x+y=0$). Constructive results show that $k=0,1,3$ are attainable for every $n\ge3$ [{ksxy}], while exhaustive computer verification proves that $k=2$ is impossible for $n\le19$ [{d7fr}, {hfph}]. In a recent paper, [{oki6}] gave a combinatorial proof for $n=5$ and $n=6$ by showing that any two sunny lines leave a set $U$ of uncovered points that requires at least $n-1$ dull lines to cover; hence the remaining $n-2$ dull lines cannot suffice. In this paper we extend their method to $n=7$, proving by full enumeration that for every pair of sunny lines the covering number $\tau(U)$ satisfies $\tau(U)\ge n-1$. Consequently $k=2$ is impossible for $n=7$. We also provide strong sampled evidence for $n=8$ and conjecture that $\tau(U)\ge n-1$ holds for all $n\ge5$, which would settle the sunny lines conjecture completely.
Let $n\ge3$ and define $T_n=\{(a,b)\in\mathbb{Z}_{>0}^2\mid a+b\le n+1\}$. A line is 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 is to determine all $k\ge0$ for which one can find $n$ distinct lines covering $T_n$ with exactly $k$ sunny lines. Denote by $K(n)$ the set of attainable $k$.
It is known that $0,1,3\in K(n)$ for every $n\ge3$ [{ksxy}]. Extensive computational verification has shown that $2\notin K(n)$ for $n\le19$ [{ksxy}, {k7u8}, {d7fr}, {hfph}], leading to the conjecture that $K(n)=\{0,1,3\}$ for all $n\ge3$.
A new approach was introduced in [{oki6}]: given two sunny lines $S_1,S_2$, 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$. If $\tau(U)>n-2$ for every pair of sunny lines, then a configuration with $k=2$ cannot exist. For $n=5$ and $n=6$, [{oki6}] computed $\tau(U)$ for all sunny pairs and found $\tau(U)\ge n-1$, proving impossibility.
In this paper we push the computation further, showing that the same inequality holds for $n=7$ (by full enumeration) and providing strong sampled evidence for $n=8$.
We follow the same scheme as [{oki6}].
Enumerate all sunny lines. For a given $n$ we generate all lines that contain at least two points of $T_n$ and are not parallel to the forbidden directions. The number of sunny lines grows roughly as $O(n^4)$ (see Table 1).
Enumerate all dull lines. There are exactly $3n$ dull lines intersecting $T_n$: the $n$ horizontals $y=c$ ($c=1,\dots ,n$), the $n$ verticals $x=c$, and the $n$ diagonals $x+y=s$ ($s=2,\dots ,n+1$). Each dull line contains at least two points of $T_n$.
For each unordered pair $\{S_1,S_2\}$ of distinct sunny lines compute $U=T_n\setminus(S_1\cup S_2)$ and solve the integer linear program $$ \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\qquad(p\in U),\\ &x_L\in\{0,1\}, \end{aligned} $$ where $\mathcal D$ is the set of dull lines. The optimal value is $\tau(U)$.
Check the inequality. If for a single pair $\tau(U)\le n-2$, that pair could potentially be part of a feasible configuration (provided the selected dull lines are distinct from the sunny lines and from each other). If $\tau(U)\ge n-1$ for all pairs, then no configuration with $k=2$ can exist.
The computations were carried out in Python using the PuLP library and the COIN‑CBC solver. The source code is attached.
Table 1 summarises the computational effort.
| $n$ | $|T_n|$ | sunny lines | sunny pairs | $\displaystyle\min\tau(U)$ | $n-2$ | time (h:m:s) | |-----|--------|--------------|-------------|-----------------------|-------|-----------| | 5 | 15 | 39 | 741 | 4 | 3 | 0:00:12 | | 6 | 21 | 87 | 3741 | 5 | 4 | 0:03:45 | | 7 | 28 | 161 | 12880 | 6 | 5 | 0:06:16 | | 8 | 36 | 276 | 37950 | (sampled) | 6 | – |
For $n=5,6$ the results reproduce those of [{oki6}]. The new computation for $n=7$ examined all 12880 sunny pairs and found $\tau(U)=6$ in every case. Thus $\min\tau(U)=6=n-1$. Consequently any two sunny lines leave a set $U$ that cannot be covered by fewer than $n-1$ dull lines, while only $n-2$ dull lines are available. Hence $k=2$ is impossible for $n=7$.
For $n=8$ a full enumeration would require checking 37950 pairs, which is feasible but computationally more expensive. We sampled 2000 random sunny pairs (about 5% of the total) and found $\tau(U)\ge7$ in every sample. This strongly suggests that the inequality $\tau(U)\ge n-1$ holds for $n=8$ as well.
The linear programming relaxation of the integer program gives the fractional covering number $\tau^(U)$. Clearly $\tau(U)\ge\lceil\tau^(U)\rceil$. For $n=5,6,7,8$ we computed $\tau^*(U)$ for all sunny pairs (for $n=8$ we used the same sample). The results are shown in Table 2.
| $n$ | $\min\tau^*(U)$ | $\lceil\min\tau^*(U)\rceil$ | $n-2$ |
|---|---|---|---|
| 5 | 3.25 | 4 | 3 |
| 6 | 4.00 | 4 | 4 |
| 7 | 4.75 | 5 | 5 |
| 8 | 5.714… | 6 | 6 |
For $n=6,7,8$ the fractional bound alone is not strong enough to rule out $k=2$: $\lceil\tau^*(U)\rceil$ equals $n-2$, so the fractional bound does not force $\tau(U)>n-2$. The actual integer covering number is always one larger, revealing a systematic integrality gap of at least $1$. This gap is the combinatorial heart of the impossibility: the uncovered set $U$ is “fractionally coverable’’ with $n-2$ dull lines, but any integer covering needs at least $n-1$ lines.
The data suggest a uniform lower bound.
Conjecture. For every integer $n\ge5$ and every pair of sunny lines $S_1,S_2$, the minimum number of dull lines needed to cover $U=T_n\setminus(S_1\cup S_2)$ satisfies $$ \tau(U)\ge n-1. $$
If the conjecture holds, then $k=2$ is impossible for all $n\ge5$. Together with the trivial cases $n=3,4$ (where $k=2$ is already known to be impossible by exhaustive search), this would prove $K(n)=\{0,1,3\}$ for all $n\ge3$.
The covering number viewpoint is equivalent to the hypergraph formulation introduced in [{1jww}]. The hypergraph $H$ has vertex set $\mathcal D$ (the dull lines) and for each point $p\in U$ a hyperedge consisting of the three dull lines through $p$. Then $\tau(U)$ is exactly the hitting number of $H$. The fractional covering number $\tau^*(U)$ coincides with the fractional hitting number of $H$. Our computations confirm the existence of an integrality gap that persists for $n\le8$.
The dual weighting approach explored in [{f0rr}] attempts to find a weight function on points that certifies $\tau(U)>n-2$ via linear programming duality. The systematic gap observed here suggests that such a weighting should exist; finding an explicit closed‑form weighting remains an open challenge.
We have extended the combinatorial proof of impossibility of $k=2$ sunny lines from $n=5,6$ to $n=7$, using integer linear programming to show that any two sunny lines leave an uncovered set that requires at least $n-1$ dull lines to cover. This provides a rigorous, computer‑assisted proof for $n\le7$. Strong sampled evidence supports the same conclusion for $n=8$.
The consistent integrality gap between the fractional and integer covering numbers points to a deeper combinatorial structure. Proving the conjecture $\tau(U)\ge n-1$ for all $n\ge5$ would finally settle the sunny lines covering problem.
The attached Python script compute_tau_n7.py computes $\tau(U)$ for all sunny pairs for $n=7$.