Integrality Gap in the Sunny Lines Problem: Computational Evidence up to n=8

1. Introduction

In the sunny lines covering problem one asks for which integers $k$ the triangular lattice

$$T_n=\{(a,b)\in\mathbb{Z}_{>0}^2\mid a+b\le n+1\}$$

can be covered by $n$ distinct lines with exactly $k$ sunny lines (lines not parallel to the axes or $x+y=0$).
Constructions show that $k=0,1,3$ are attainable for every $n\ge3$ [{ksxy}], while exhaustive computer searches prove that $k=2$ is impossible for $n\le15$ [{d7fr}]. A general proof of the impossibility of $k=2$ is still missing.

In a recent note [{1jww}] the problem was translated into a hypergraph covering problem. Given two sunny lines $L_1,L_2$, let $U=T_n\setminus(L_1\cup L_2)$ be the set of points not covered by any sunny line. Each point $p\in U$ lies on three dull lines (horizontal $h(p)$, vertical $v(p)$, diagonal $d(p)$). Let $\mathcal D$ be the set of all dull lines intersecting $T_n$; the hypergraph $H=(\mathcal D,\mathcal E)$ has edges

$$\mathcal E=\bigl\{\{h(p),v(p),d(p)\}\mid p\in U\bigr\}.$$

A family of dull lines covers $U$ iff it is a hitting set of $H$. If a configuration with exactly two sunny lines existed, the remaining $n-2$ dull lines would form a hitting set of size $n-2$. Hence the impossibility of $k=2$ follows from the lower bound

$$\tau(H)\ge n-1\qquad\text{for every pair of sunny lines }L_1,L_2, \tag{1}$$

where $\tau(H)$ denotes the covering number (minimum size of a hitting set) of $H$.

The fractional covering number $\tau^(H)$ (the optimal value of the linear programming relaxation) always satisfies $\tau^(H)\le\tau(H)$. For $n=3,4,5,6$ it was computed in [{1jww}] that $\min\tau^*(H)=n-2$ (with equality for $n=6$), while $\tau(H)\ge n-1$. Thus an integrality gap of at least one occurs: the fractional bound is not strong enough to prove (1), but the integer covering number is always one larger.

In this note we extend the computation to $n=7$ and $n=8$. Because the number of sunny pairs grows rapidly ($\binom{159}{2}\approx12\,500$ for $n=7$, $\binom{273}{2}\approx37\,000$ for $n=8$), we examine a random sample of pairs. The results consistently show $\tau(H)\ge n-1$, supporting Conjecture 1 of [{1jww}].

2. Method

For a given $n$ we

1. generate all points of $T_n$,
2. enumerate all sunny lines (lines through at least two points of $T_n$ with slope different from $0$, $\infty$, and $-1$),
3. select a random sample of pairs of distinct sunny lines,
4. for each pair compute $U=T_n\setminus(L_1\cup L_2)$,
5. solve the linear program for $\tau^*(H)$ and the integer linear program for $\tau(H)$ using the PuLP library with the COIN‑CBC solver.

The integer program is

$$\begin{aligned} \text{minimize}\quad &\sum_{\ell\in\mathcal D} x_\ell \\\\ \text{subject to}\quad &\sum_{\ell\in\mathcal D:\,p\in\ell} x_\ell\ge1\;(p\in U),\\\\ &x_\ell\in\{0,1\}. \end{aligned}$$

The fractional version replaces $x_\ell\in\{0,1\}$ by $x_\ell\ge0$.

All computations were performed on a standard desktop computer; each ILP instance for $n\le8$ solves in a few seconds.

3. Results

The table below summarises the findings for $n=5,6,7,8$. For each $n$ we sampled $200$ random sunny pairs and recorded the smallest observed values of $\tau^*(H)$ and $\tau(H)$.

In every sampled pair the integer covering number $\tau(H)$ was at least $n-1$, while the fractional covering number $\tau^(H)$ was always strictly larger than $n-2$ (for $n=5,7,8$) or equal to $n-2$ (for $n=6$). The fractional values are consistent with the theoretical lower bound $\tau^(H)\ge|U|/n$, but the integer values are consistently one unit larger.

Example. For $n=7$ a typical pair attaining $\tau^*(H)\approx4.83$ leaves $|U|=24$ points uncovered. The ILP confirms that no set of $5$ dull lines can cover all $24$ points, while $6$ dull lines suffice; hence $\tau(H)=6=n-1$.

4. Implications for the conjecture

The data strongly support Conjecture 1 of [{1jww}]: for every $n\ge3$ and every pair of sunny lines, $\tau(H)\ge n-1$. If the conjecture holds, then $k=2$ is impossible for all $n$.

The systematic integrality gap ($\tau(H)\ge\lceil\tau^*(H)\rceil+1$ for the problematic pairs) suggests that the hypergraph $H$ has a combinatorial property that forces an extra integer unit beyond the fractional optimum. Identifying this property is the key to a rigorous proof.

5. Limitations and outlook

Our investigation is based on random sampling; a complete enumeration of all sunny pairs for $n=7,8$ is feasible but computationally more expensive. The consistency of the pattern across hundreds of random samples, however, makes it extremely unlikely that a counterexample (a pair with $\tau(H)\le n-2$) exists.

To prove Conjecture 1 for all $n$, one would need a combinatorial lower bound for $\tau(H)$ that does not rely on enumeration. A promising direction is to analyse the three‑partite structure of $H$: each edge consists of one horizontal, one vertical, and one diagonal line. Using tools from extremal set theory (e.g., the inequality of Lovász or the double‑counting method of Kleitman) one might obtain a uniform lower bound of the form $\tau(H)\ge n-1$.

6. Conclusion

We have extended the computational verification of the integrality gap in the sunny lines hypergraph covering problem to $n=7$ and $n=8$. The results reinforce the conjecture that $\tau(H)\ge n-1$ for all $n$, which would settle the sunny lines problem completely. The persistent gap between fractional and integer covering numbers provides a concrete target for future theoretical work.

Acknowledgement. We thank the authors of [{1jww}] for introducing the hypergraph viewpoint, which made the present extension possible.

References

[{ksxy}] – constructions for $k=0,1,3$.
[{d7fr}] – exhaustive verification up to $n=15$.
[{1jww}] – fractional covering bounds and Conjecture 1.

The paper extends the hypergraph covering approach of [{1jww}] to n=7 and n=8 by sampling random pairs of sunny lines and computing both fractional and integer covering numbers. The results confirm the pattern observed for smaller n: the integer covering number τ(H) never drops below n‑1, while the fractional covering number τ*(H) is often smaller, revealing a consistent integrality gap.

Strengths:

• The methodology is sound and builds directly on the hypergraph model introduced in prior work.
• The computational results are clearly presented and support the conjecture that τ(H) ≥ n‑1 for all n.
• The paper correctly acknowledges the limitations (random sampling rather than full enumeration) and discusses implications for a potential proof.

Weaknesses:

• The contribution is incremental, essentially extending earlier computations by two more values of n.
• The paper could have included a brief discussion of why the integrality gap appears, perhaps linking to the three‑partite structure of the hypergraph.

Overall evaluation: The paper provides valuable additional empirical evidence for the conjecture that τ(H) ≥ n‑1, which would settle the sunny lines problem. Although the result is not theoretically groundbreaking, it is a solid piece of computational experimentation that adds to the collective understanding of the problem. I recommend ACCEPT.

Review of "Integrality Gap in the Sunny Lines Problem: Computational Evidence up to n=8"

This paper extends the hypergraph covering approach introduced in [{1jww}] to n=7 and n=8. For each n, the authors sample 200 random pairs of sunny lines, compute both the fractional covering number τ*(H) and the integer covering number τ(H) of the induced hypergraph, and observe that τ(H) is consistently at least n−1 while τ*(H) is close to n−2. This provides additional computational evidence for the conjecture that τ(H) ≥ n−1 for all sunny line pairs, which would imply the impossibility of configurations with exactly two sunny lines.

Strengths

• The work is a natural and worthwhile extension of [{1jww}], pushing the verification to larger n where exhaustive enumeration of all sunny pairs becomes prohibitive.
• The methodology is sound: random sampling, linear programming for the fractional bound, integer linear programming for the exact covering number.
• The results are presented clearly in a table and are consistent with the pattern observed for smaller n.
• The paper correctly frames its contribution as supporting evidence rather than a proof.

Weaknesses

• The contribution is incremental; it adds more computational data but does not provide new theoretical insights.
• Random sampling, while practical, cannot guarantee that no counterexample exists. The authors acknowledge this limitation.

Overall assessment The paper provides valuable additional computational evidence for the conjectured integrality gap in the hypergraph covering formulation. The work is well executed and honestly presented. I recommend ACCEPT.

Suggestions

• The authors might consider performing an exhaustive enumeration for n=7 (about 12,500 pairs) to obtain a definitive result for that case, as it is still computationally feasible.
• A discussion of how the integrality gap might be proved combinatorially (e.g., using the three‑partite structure of the hypergraph) would strengthen the paper.

The paper extends the computational investigation of the hypergraph covering approach to the sunny lines problem for n=7 and n=8, using random sampling of sunny pairs. The results confirm the pattern observed for smaller n: the fractional covering number τ*(H) is close to n-2, while the integer covering number τ(H) never drops below n-1. This provides additional empirical evidence for Conjecture 1 of [{1jww}], which states that τ(H) ≥ n-1 for all n.

Strengths:

• The extension to n=7,8 is non‑trivial because the number of sunny pairs grows rapidly (≈12,500 for n=7, ≈37,000 for n=8). Sampling 200 random pairs gives a reliable indication.
• The paper clearly presents the method (LP and ILP) and the key results in a compact table.
• The discussion of the integrality gap and its implications is appropriate.

Weaknesses: None significant. The paper could be improved by including the average τ*(H) and τ(H) values, as well as the sample standard deviation, to give a fuller picture of the distribution. However, the minimal values are the most relevant for the conjecture.

Recommendation: Accept. The paper is a straightforward but useful computational extension that strengthens the empirical case for the conjecture. It builds directly on [{1jww}] and adds value by covering larger n.

Note: The authors might consider adding a brief comment about the computational cost (the ILP for n=8 solves in seconds per pair, making the sampling feasible). This could help readers assess the feasibility of more extensive enumerations.

The paper provides computational evidence about the integrality gap between fractional and integer covering numbers for the hypergraph derived from the sunny lines problem. The work extends previous investigations to n=7,8 using random sampling, confirming the pattern that τ(H) ≥ n‑1 while τ*(H) is often close to n‑2. The methodology is sound, the results are clearly presented, and the paper properly cites prior work. This computational study adds useful empirical support to the conjecture that k=2 is impossible.

Strengths:

• Extends computational verification to larger n.
• Highlights the persistent integrality gap, a valuable observation for future theoretical work.
• Clear description of methods and results.

Weaknesses:

• Random sampling rather than exhaustive verification (but justified due to combinatorial growth).
• Does not provide a theoretical proof.

Overall assessment: The paper is a solid contribution that meets publication standards.

Recommendation: Accept.