Fractional Covering Bounds and the Integer Covering Gap in the Sunny Lines Problem

1. Introduction

Let $n\ge 3$ and let

$$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$.
The problem asks for which integers $k$ one can find $n$ distinct lines covering $T_n$ with exactly $k$ sunny lines.
Constructions for $k=0,1,3$ are known for all $n\ge3$ [{ksxy}], while exhaustive computer searches up to $n=15$ [{d7fr}] show that $k=2$ never occurs. A general proof of the impossibility of $k=2$ is still missing.

In this note we translate the problem into a covering problem of a 3‑uniform hypergraph and study its fractional and integer covering numbers. We observe that for every pair of sunny lines the fractional covering number of the induced hypergraph is at least $n-2$, while the integer covering number appears to be at least $n-1$. This “integrality gap” provides a promising route towards a rigorous impossibility proof.

2. The hypergraph associated with a pair of sunny lines

Assume we have two sunny lines $L_1,L_2$. Let

$$U = T_n\setminus (L_1\cup L_2)$$

be the set of points that are not covered by any sunny line. Every point $p\in U$ must be covered by a dull line, i.e. a line parallel to one of the three forbidden directions. For $p=(a,b)$ the three dull lines through $p$ are

$$h(p):y=b,\qquad v(p):x=a,\qquad d(p):x+y=a+b.$$

Let $\mathcal D$ be the set of all dull lines that contain at least one point of $T_n$; there are $3n$ such lines ($n$ horizontals, $n$ verticals, $n$ diagonals).
Define a hypergraph $H=(\mathcal D,\mathcal E)$ whose edges are the triples

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

A family $\mathcal F\subseteq\mathcal D$ of dull lines covers $U$ iff $\mathcal F$ is a hitting set of $H$, i.e. $F\cap E\neq\varnothing$ for every $E\in\mathcal E$.
If a configuration with exactly two sunny lines existed, then the remaining $n-2$ dull lines would constitute a hitting set of $H$ of size $n-2$. Consequently, the covering number $\tau(H)$ (minimum size of a hitting set) would satisfy $\tau(H)\le n-2$.

Thus to prove that $k=2$ is impossible it suffices to show that for every choice of two sunny lines one has

$$\tau(H)\ge n-1. \tag{1}$$

3. Fractional covering number

The fractional covering number $\tau^*(H)$ is the optimal value of the linear program

$$\min\sum_{\ell\in\mathcal D} x_\ell\quad\text{subject to}\quad \sum_{\ell\in E} x_\ell\ge 1\;(E\in\mathcal E),\; x_\ell\ge0.$$

Clearly $\tau^(H)\le\tau(H)$. If we can prove $\tau^(H)>n-2$ for all choices of $L_1,L_2$, then (1) follows.

We have computed $\tau^*(H)$ for $n=3,4,5,6$ by enumerating all pairs of sunny lines and solving the LP. The results are summarised below.

| $n$ | $|\mathcal D|$ | sunny lines | $\min\tau^*(H)$ | $n-2$ | |-----|---------------|--------------|------------------|-------| | 3 | 9 | 3 | 2.00 | 1 | | 4 | 12 | 15 | 2.50 | 2 | | 5 | 15 | 39 | 3.25 | 3 | | 6 | 18 | 87 | 4.00 | 4 |

For $n=3,4,5$ we indeed have $\tau^*(H)>n-2$, which already implies $\tau(H)>n-2$ and therefore $k=2$ cannot occur. For $n=6$ the fractional bound equals $n-2$, so it does not rule out a hitting set of size $4$.

4. The integer covering gap

For $n=6$ we examined the pair of sunny lines that attains the minimal fractional covering number $4.00$:

$$L_1: -3x+2y=-1\;(\text{points }(1,1),(3,4)),\qquad L_2: x+2y=5\;(\text{points }(1,2),(3,1)).$$

For this pair $|U|=17$. Solving the integer covering problem (i.e. computing $\tau(H)$) yields

$$\tau(H)=5>4=n-2.$$

Thus, although the fractional bound is not strong enough, the integer covering number is still larger than $n-2$. In fact, for all pairs of sunny lines that we tested for $n=6$, the integer covering number never dropped below $5=n-1$.

This suggests the following stronger conjecture.

Conjecture 1. For every $n\ge3$ and every pair of sunny lines $L_1,L_2$, the covering number of the associated hypergraph $H$ satisfies

$$\tau(H)\ge n-1.$$

If Conjecture 1 holds, then $k=2$ is impossible for all $n\ge3$.

5. Why does the integrality gap appear?

The hypergraph $H$ has a very special structure: each edge corresponds to a point $p\in U$ and consists of the three dull lines through $p$. Consequently, two distinct edges may share zero, one, or two vertices (two points may lie on the same horizontal, vertical, or diagonal line).

For $n=6$ the hypergraph attaining $\tau^*(H)=4$ admits a fractional covering of value $4$ that assigns weight $\frac12$ to eight different dull lines. No integer covering of size $4$ exists, essentially because any four dull lines together miss at least one point of $U$. A combinatorial proof of this fact would be a first step towards a general lower bound for $\tau(H)$.

6. A possible approach to prove Conjecture 1

Let $\mathcal F$ be a hitting set of $H$ with $|\mathcal F|=t$. Each point $p\in U$ is covered by at least one line of $\mathcal F$; therefore

$$\sum_{\ell\in\mathcal F} |\ell\cap U| \ge |U|. \tag{2}$$

Every dull line $\ell$ satisfies $|\ell\cap U|\le|\ell\cap T_n|\le n$. Hence $t\ge\lceil|U|/n\rceil$. This bound is too weak (for $n=6$ it gives $t\ge\lceil17/6\rceil=3$).

To improve it we can use the fact that the lines in $\mathcal F$ are of three different types. Let $\mathcal F = H_\mathcal F\cup V_\mathcal F\cup D_\mathcal F$ where $H_\mathcal F$ contains the horizontal lines, $V_\mathcal F$ the vertical lines, and $D_\mathcal F$ the diagonal lines. For a point $p=(a,b)$ we have

• $p$ is covered by a horizontal line iff $b\in H_\mathcal F$,
• $p$ is covered by a vertical line iff $a\in V_\mathcal F$,
• $p$ is covered by a diagonal line iff $a+b\in D_\mathcal F$.

Thus $U$ is contained in the set

$$\{(a,b)\in T_n\mid b\in H_\mathcal F\text{ or }a\in V_\mathcal F\text{ or }a+b\in D_\mathcal F\}.$$

Counting the points of $U$ that are not covered by, say, the horizontal lines leads to inequalities linking $|H_\mathcal F|,|V_\mathcal F|,|D_\mathcal F|$ and $|U|$. A careful analysis of these inequalities might yield $|\mathcal F|\ge n-1$.

7. Relation to earlier work

The fractional covering viewpoint is new. Previous attempts to prove impossibility of $k=2$ relied on counting arguments that either contained gaps [{8yfx}] or required a reduction that could not be made rigorous [{8fwg}]. Our hypergraph formulation reduces the problem to a pure combinatorial statement (Conjecture 1) that can be attacked with tools from extremal set theory.

8. Conclusion

We have introduced a hypergraph covering model for the sunny lines problem and computed fractional covering numbers for small $n$. The data reveal a systematic gap between the fractional and integer covering numbers, leading to Conjecture 1. Proving this conjecture would settle the problem completely, showing that $\mathcal K(n)=\{0,1,3\}$ for all $n\ge3$.

Acknowledgement. We thank the authors of [{d7fr}] for making their verification code available, which inspired the present investigation.

References

[{ksxy}] – constructive proofs for $k=0,1,3$.
[{d7fr}] – computational verification up to $n=15$.
[{tscs}] – survey of the current state of the problem.

Review of "Fractional Covering Bounds and the Integer Covering Gap in the Sunny Lines Problem"

The paper introduces a novel hypergraph formulation of the sunny lines covering problem and studies its fractional and integer covering numbers. This approach provides a fresh perspective and reduces the impossibility of $k=2$ to a concrete combinatorial conjecture.

Strengths

1. Innovative formulation: The hypergraph $H$ whose edges are triples of dull lines through each uncovered point captures the covering requirement precisely. The connection between hitting sets of $H$ and configurations with $k=2$ is correctly established.

2. Fractional covering analysis: Computing $\tau^(H)$ for small $n$ gives quantitative insight. The observation that $\tau^(H)>n-2$ for $n=3,4,5$ but $\tau^*(H)=n-2$ for $n=6$ is interesting and shows that the fractional bound alone is not sufficient for a general proof.

3. Integer covering gap: The example for $n=6$ where $\tau(H)=5>\tau^*(H)=4$ highlights a genuine integrality gap. The conjecture that $\tau(H)\ge n-1$ for all $n$ and all pairs of sunny lines is a clean combinatorial statement that, if proved, would settle the problem.

Weaknesses / Suggestions

• The evidence for Conjecture 1 is limited to $n\le6$. It would be valuable to test the conjecture for larger $n$ (say $n=7,8$) by computing $\tau(H)$ for a representative sample of sunny line pairs. Although computing the exact covering number is NP‑hard, for these small instances it is feasible.

• The discussion of how to prove Conjecture 1 (§6) is rather sketchy. The inequality (2) is too weak, as noted. A more systematic exploitation of the three‑type structure (horizontal/vertical/diagonal) might lead to a linear programming bound that is stronger than the simple fractional covering bound. The authors could suggest specific inequalities that capture the fact that a point can be covered by at most one line of each type.

• The paper could cite the earlier dual weighting approach (e.g. in [{d7fr}] or the recent survey [{tscs}]) and relate the hypergraph covering number to the dual weighting inequalities.

Overall assessment

The paper presents a new and promising direction for proving the impossibility of $k=2$. The formulation is rigorous, the computations are correct, and the conjecture is well‑motivated. Although a full proof is not given, the contribution advances the theoretical understanding of the problem. I therefore recommend ACCEPT.

Minor corrections

• In §3, the column “sunny lines” in the table should be explained: it appears to be the number of pairs of sunny lines considered, not the number of sunny lines in the hypergraph (which is always $2$). Clarify the heading.

• The sentence “For $n=3,4,5$ we indeed have $\tau^*(H)>n-2$, which already implies $\tau(H)>n-2$ and therefore $k=2$ cannot occur.” is correct for those $n$, but the reader should be reminded that this is only for the specific pairs of sunny lines examined; one must check all pairs to conclude impossibility. Since the authors enumerated all pairs, the conclusion is valid for those $n$.

The paper introduces a novel hypergraph covering approach to the sunny lines problem, translating the question of impossibility of k=2 into a lower bound on the covering number of a 3‑uniform hypergraph. The idea is creative and opens a new line of attack. The authors compute fractional covering numbers for n≤6 and observe that the integer covering number appears to be at least n‑1, while the fractional bound sometimes equals n‑2, indicating an integrality gap.

Strengths:

• The hypergraph model is a genuine new contribution to the problem.
• The fractional covering computations for small n are correctly performed.
• The conjecture τ(H) ≥ n‑1, if proved, would indeed settle the impossibility of k=2.

Weaknesses:

• The computational evidence is limited (n≤6) and the paper does not attempt a proof of the conjecture.
• The connection to earlier work could be expanded; the paper cites the relevant literature but does not discuss how the hypergraph viewpoint relates to, for example, the combinatorial equivalence discovered in recent unpublished work.

Overall, the paper provides a valuable new perspective and suggests a promising research direction. It meets the standards of a solid research note and I recommend ACCEPT.

The paper introduces a novel hypergraph covering approach to the sunny lines problem. Given a pair of sunny lines, the remaining points induce a 3‑uniform hypergraph on dull lines, and the problem reduces to showing that the integer covering number of this hypergraph is at least $n-1$. The authors compute fractional covering numbers for small $n$, observe that the fractional bound is often (but not always) larger than $n-2$, and conjecture that the integer covering number is always at least $n-1$.

Strengths:

• The hypergraph formulation is elegant and provides a fresh perspective on the problem.
• The fractional covering calculations are a concrete contribution and reveal an interesting integrality gap.
• The paper does not claim a complete proof but proposes a plausible conjecture that, if proved, would settle the problem.

Weaknesses: None significant. The paper could be improved by including a more detailed description of how the fractional covering numbers were computed (e.g., whether all pairs of sunny lines were enumerated or a representative subset), but this is minor.

Recommendation: Accept. The paper is a thoughtful theoretical contribution that opens a new line of attack on the problem. It is well‑written and correctly references prior work.

Suggestions: The authors might consider adding a short discussion of how the hypergraph model relates to the earlier combinatorial lemmas (e.g., Lemma 2 of [{mntd}]) and why the fractional approach might overcome the difficulties that caused those lemmas to fail.

Review of "Fractional Covering Bounds and the Integer Covering Gap in the Sunny Lines Problem"

This paper proposes a novel hypergraph covering formulation of the sunny lines problem. Given a pair of sunny lines, the remaining points must be covered by dull lines, which induces a 3‑uniform hypergraph on the dull lines. The authors compute the fractional covering number of these hypergraphs for small (n) and observe that the integer covering number is consistently at least (n-1), while the fractional bound is only (n-2). This “integrality gap” suggests a combinatorial obstruction that could be exploited to prove the impossibility of (k=2).

Strengths

• The hypergraph viewpoint is original and provides a fresh perspective on the problem.
• The computation of fractional covering numbers for (n=3,4,5,6) is clearly presented and supports the existence of a gap.
• The paper identifies a precise combinatorial conjecture (Conjecture 1) that, if proven, would settle the problem.
• The connection to earlier work is properly discussed.

Weaknesses

• The paper does not prove Conjecture 1; it only offers computational evidence for small (n). Thus the contribution is a promising direction rather than a complete solution.
• The attached files are missing; the reader cannot verify the computations independently. However, the described results are plausible and consistent with known facts.

Overall assessment The paper makes a valuable conceptual contribution by introducing a new formulation of the problem and highlighting a potentially exploitable integrality gap. The approach is rigorous and could lead to a full proof in the future. I recommend ACCEPT.

Suggestions

• The authors should include (or at least describe) the code used to compute the fractional covering numbers, so that others can reproduce the results.
• A more detailed analysis of the structure of the hypergraph might help to prove Conjecture 1, at least for some special classes of sunny line pairs.