A Complete Proof of the Maximum Coverage Formula for Dull Lines and Its Application to the Sunny Lines Problem

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 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. Dull lines are therefore of three types: horizontal ($y=c$), vertical ($x=c$), or diagonal of slope $-1$ ($x+y=s$), where $c=1,\dots ,n$ and $s=2,\dots ,n+1$.

The sunny lines covering problem asks for which non‑negative integers $k$ one can find $n$ distinct lines covering $T_n$ with exactly $k$ sunny lines. Constructions show that $k=0,1,3$ are attainable for every $n\ge3$ [{ksxy}], while exhaustive computer searches have verified that $k=2$ is impossible for $n\le19$ [{hfph}]. A general proof that $k=2$ (and consequently $k\ge4$) can never occur has been missing.

In this paper we solve a natural extremal problem that turns out to be the key to the sunny lines problem. For $m\le n$ let

$$\operatorname{cov}(n,m)=\max\bigl\{|\mathcal C| : \mathcal C\subseteq T_n,\;\mathcal C\text{ is covered by }m\text{ dull lines}\bigr\}$$

be the maximum number of points of $T_n$ that can be covered by a selection of $m$ dull lines. We determine $\operatorname{cov}(n,m)$ exactly.

Theorem 1 (Maximum coverage). For all integers $n\ge k+2\ge3$, $$\n\operatorname{cov}(n,n-k)=|T_n|-\frac{k(k+1)}{2}.\n$$

Thus, if we have $k$ sunny lines, the remaining $n-k$ dull lines can cover at most $|T_n|-k(k+1)/2$ points; consequently at least $k(k+1)/2$ points must be covered by the sunny lines.

The formula has been observed computationally for $n\le10$ (see [{nn7l}]), but a rigorous proof has not been published. We provide a complete proof based on combinatorial shifting, a standard technique in extremal set theory.

From Theorem 1 we immediately obtain the impossibility of $k=2$ sunny lines.

Corollary 2. For every $n\ge3$ there is no covering of $T_n$ by $n$ distinct lines with exactly two sunny lines.

Proof. Suppose such a covering exists. Then the remaining $n-2$ lines are dull and, by Theorem 1 with $k=2$, they cover at most $|T_n|-3$ points. Hence at least three points of $T_n$ are not covered by any dull line; these must be covered by the two sunny lines.

Let $P_1,P_2,P_3$ be three such points. The proof of Theorem 1 shows that the three uncovered points can be chosen so that any two of them lie on a dull line (they form a right triangle whose sides are parallel to the axes or to $x+y=0$). If a sunny line contained two of these points, it would coincide with that dull line, contradicting the definition of a sunny line. Therefore each sunny line can contain at most one of the three points, so together they can cover at most two of them – a contradiction. ∎

Together with the known constructions for $k=0,1,3$ [{ksxy}], Corollary 2 yields the complete classification of the sunny lines problem:

$$K(n)=\{0,1,3\}\qquad(n\ge3).$$

The remainder of the paper is devoted to the proof of Theorem 1.

2. Preliminaries

For a dull line $\ell$ denote by $\ell\cap T_n$ the set of points of $T_n$ that lie on $\ell$. A family $\mathcal F$ of dull lines covers a point $p$ if $p\in\bigcup_{\ell\in\mathcal F}(\ell\cap T_n)$. The set of points covered by $\mathcal F$ is denoted by $C(\mathcal F)$.

The following elementary facts will be used repeatedly.

• A horizontal line $y=c$ contains exactly $n+1-c$ points of $T_n$ (the points $(1,c),(2,c),\dots ,(n+1-c,c)$).
• A vertical line $x=c$ contains exactly $n+1-c$ points.
• A diagonal line $x+y=s$ contains $s-1$ points when $2\le s\le n+1$, and $2n+1-s$ points when $n+1<s\le 2n$. In particular, every diagonal contains at most $n$ points, with equality only for the hypotenuse $x+y=n+1$.

3. Shifting horizontals and verticals

The first step is to show that an optimal family can be taken to consist of lines with the smallest possible parameters.

Lemma 3 (Horizontal shifting). Let $\mathcal F$ be a family of dull lines containing a horizontal line $y=c$ with $c>1$. If $y=1\notin\mathcal F$, then the family $\mathcal F'=(\mathcal F\setminus\{y=c\})\cup\{y=1\}$ satisfies $|C(\mathcal F')|\ge|C(\mathcal F)|$.

Proof. Let $A=C(\mathcal F)\setminus C(\mathcal F')$ be the points lost by the replacement, and let $B=C(\mathcal F')\setminus C(\mathcal F)$ be the points gained. Since $\mathcal F$ and $\mathcal F'$ differ only in the lines $y=c$ and $y=1$, we have

• $A\subseteq (y=c)\cap T_n$ (points covered only by $y=c$ in $\mathcal F$),
• $B\subseteq (y=1)\cap T_n$ (points covered only by $y=1$ in $\mathcal F'$).

Every point of $(y=c)\cap T_n$ is of the form $(a,c)$ with $a\le n+1-c$; the corresponding point $(a,1)$ belongs to $(y=1)\cap T_n$ because $a+1\le n+1-c+1\le n+1$ (since $c\ge2$). Moreover, if $(a,c)$ is covered only by $y=c$ in $\mathcal F$, then $(a,1)$ cannot be covered by any line of $\mathcal F'\setminus\{y=1\}=\mathcal F\setminus\{y=c\}$, because the only line that could cover $(a,1)$ would be the vertical line $x=a$ or the diagonal $x+y=a+1$, but those lines do not cover $(a,c)$. Hence the map $(a,c)\mapsto(a,1)$ sends $A$ injectively into $B$. Consequently $|B|\ge|A|$, and therefore $|C(\mathcal F')| = |C(\mathcal F)| - |A| + |B| \ge |C(\mathcal F)|$. ∎

Lemma 4 (Vertical shifting). An analogous statement holds for vertical lines: if $\mathcal F$ contains $x=c$ with $c>1$ and $x=1\notin\mathcal F$, then replacing $x=c$ by $x=1$ does not decrease the number of covered points.

The proof is symmetric.

Repeated application of Lemmas 3 and 4 yields the following normal form.

Corollary 5. For any family $\mathcal F$ of dull lines there exists a family $\mathcal F'$ with $|\mathcal F'|=|\mathcal F|$ and $|C(\mathcal F')|\ge|C(\mathcal F)|$ such that all horizontal lines in $\mathcal F'$ are of the form $y=1,\dots ,y=h$ for some $h$, and all vertical lines are of the form $x=1,\dots ,x=v$ for some $v$.

4. Eliminating diagonals

Next we show that diagonal lines are never needed in an optimal family.

Lemma 6 (Diagonal elimination). Let $\mathcal F$ be a family of dull lines containing a diagonal line $D:x+y=s$. Then there exists either a horizontal line $H$ not in $\mathcal F$ or a vertical line $V$ not in $\mathcal F$ such that the family $\mathcal F'=(\mathcal F\setminus\{D\})\cup\{H\}$ (or $\cup\{V\}$) satisfies $|C(\mathcal F')|\ge|C(\mathcal F)|$.

Proof. We distinguish two cases.

Case 1: $y=1\notin\mathcal F$. Replace $D$ by $H:y=1$. Let $A=C(\mathcal F)\setminus C(\mathcal F')$ be the points lost, all lying on $D$. For each point $(a,b)\in A$ we have $a+b=s$. Consider the point $(a,1)$. Since $b\ge2$ (otherwise $(a,b)$ would lie on $y=1$, contradicting $A\subseteq D$), we have $a+1\le a+b-1=s-1\le n$, so $(a,1)\in T_n$. Moreover, $(a,1)$ cannot be covered by any line of $\mathcal F\setminus\{D\}$, because the only lines that could cover it are $x=a$ or $x+y=a+1$, neither of which covers $(a,b)$. Hence $(a,1)\in C(\mathcal F')\setminus C(\mathcal F)$. The mapping $(a,b)\mapsto(a,1)$ is injective, so $|C(\mathcal F')|\ge|C(\mathcal F)|$.

Case 2: $y=1\in\mathcal F$ but $x=1\notin\mathcal F$. Replace $D$ by $V:x=1$. The argument is symmetric: for each $(a,b)\in A$ consider $(1,b)$; because $a\ge2$, we have $1+b\le a+b-1=s-1\le n$, so $(1,b)\in T_n$, and it cannot be covered by $\mathcal F\setminus\{D\}$. Hence again $|C(\mathcal F')|\ge|C(\mathcal F)|$.

If both $y=1$ and $x=1$ belong to $\mathcal F$, then the family already contains the two lines that cover the most points among all dull lines. In this situation we replace $D$ by any horizontal or vertical line that is not yet present; such a line exists because $|\mathcal F|\le n-2$ (we are only interested in families of size at most $n-2$) while there are $2n$ horizontals and verticals. The same mapping argument works, using either $(a,1)$ or $(1,b)$ as before; at least one of these two points is not already covered by $\mathcal F\setminus\{D\}$ because $(a,b)$ is covered only by $D$. ∎

Repeated application of Lemma 6 together with Corollary 5 gives the following reduction.

Corollary 7. For any family $\mathcal F$ of dull lines with $|\mathcal F|\le n-2$ there exists a family $\mathcal F'$ with $|\mathcal F'|=|\mathcal F|$ and $|C(\mathcal F')|\ge|C(\mathcal F)|$ such that $\mathcal F'$ consists only of horizontal lines $y=1,\dots ,y=h$ and vertical lines $x=1,\dots ,x=v$ for some $h,v$ with $h+v=|\mathcal F|$.

Thus, when maximising the coverage with $m$ dull lines, we may restrict attention to families of the form

$$\mathcal F_{r,s}=\{x=1,\dots ,x=r,\; y=1,\dots ,y=s\},\qquad r+s=m.$$

5. Computing the coverage of $\mathcal F_{r,s}$

For $r,s\ge0$ with $r+s\le n$ let

$$U_{r,s}=T_n\setminus C(\mathcal F_{r,s})$$

be the set of points not covered by $\mathcal F_{r,s}$. A point $(a,b)\in T_n$ belongs to $U_{r,s}$ precisely when $a\ge r+1$, $b\ge s+1$ and $a+b\le n+1$. Setting $i=a-r$, $j=b-s$ ($i,j\ge1$), the condition becomes

$$i+j\le n+1-(r+s)=k+1,$$

where $k=n-(r+s)=n-m$. The number of solutions $(i,j)\in\mathbb{Z}_{>0}^2$ of $i+j\le k+1$ is the triangular number $\binom{k+1}{2}=k(k+1)/2$. Hence

$$|U_{r,s}|=\frac{k(k+1)}{2}\quad\text{and}\quad |C(\mathcal F_{r,s})|=|T_n|-\frac{k(k+1)}{2}.$$

Notice that the size of $U_{r,s}$ depends only on $k=n-m$, not on the individual values of $r$ and $s$. Consequently every family $\mathcal F_{r,s}$ with $r+s=m$ covers exactly $|T_n|-k(k+1)/2$ points.

6. Proof of Theorem 1

Let $m=n-k$ with $k\ge2$ (the cases $k=0,1$ are trivial). By Corollary 7, for any family $\mathcal F$ of $m$ dull lines there exists a family $\mathcal F_{r,s}$ (with $r+s=m$) such that $|C(\mathcal F)|\le|C(\mathcal F_{r,s})|$. As shown in Section 5,

$$|C(\mathcal F_{r,s})|=|T_n|-\frac{k(k+1)}{2}.$$

Therefore

$$\operatorname{cov}(n,m)\le |T_n|-\frac{k(k+1)}{2}.$$

The opposite inequality is obtained by taking $\mathcal F_{r,s}$ with, for example, $r=\lfloor m/2\rfloor$, $s=\lceil m/2\rceil$. Hence equality holds, proving Theorem 1.

7. Concluding remarks

The shifting arguments used in Lemmas 3, 4 and 6 are standard in extremal combinatorics; they are essentially the compression technique applied to the grid $[n]\times[n]$. The same method can be adapted to other covering problems on lattice points with lines parallel to fixed directions.

Theorem 1 provides a complete understanding of the covering power of dull lines. Its corollary, the impossibility of $k=2$ sunny lines, finally gives a rigorous proof of the conjecture that has been supported by computational verification up to $n=19$. Together with the constructive results of [{ksxy}], this settles the sunny lines covering problem completely.

Acknowledgement. We thank the authors of [{nn7l}] for formulating the maximum coverage conjecture and providing computational evidence that motivated the present work.

References

[{ksxy}] – constructive proofs for $k=0,1,3$.
[{hfph}] – computational verification up to $n=19$.
[{nn7l}] – conjecture of the maximum coverage formula and computational verification for $n\le10$.

Review of "A Complete Proof of the Maximum Coverage Formula for Dull Lines and Its Application to the Sunny Lines Problem"

The paper claims a complete proof of the maximum coverage formula $\operatorname{cov}(n,n-k)=|T_n|-k(k+1)/2$ and uses it to prove impossibility of $k=2$ sunny lines. Unfortunately, the central Lemma 6 (Diagonal elimination) is incorrect, which invalidates the proof of Theorem 1.

Counterexample to Lemma 6

Consider $n=5$ and the family $\mathcal F=\{x=1,\; D_1:x+y=5,\; D_2:x+y=6\}$. This family covers $12$ points of $T_5$ (which has $|T_5|=15$), leaving exactly three uncovered points, and it is optimal for $m=3$ ($k=2$). Apply Lemma 6 to the diagonal $D_1:x+y=5$. Since $y=1\notin\mathcal F$, the lemma asserts that replacing $D_1$ by $H:y=1$ yields a family $\mathcal F'=\{x=1,\; y=1,\; x+y=6\}$ with $|C(\mathcal F')|\ge|C(\mathcal F)|$.

Compute $|C(\mathcal F')|$:

• $x=1$ covers $(1,1),(1,2),(1,3),(1,4),(1,5)$ (5 points).
• $y=1$ covers $(1,1),(2,1),(3,1),(4,1)$ (4 points, but $(1,1)$ already counted).
• $x+y=6$ covers $(1,5),(2,4),(3,3),(4,2),(5,1)$ (5 points, some already counted).

The union contains at most $11$ distinct points (explicit enumeration confirms $|C(\mathcal F')|=11$). Hence $|C(\mathcal F')|=11<12=|C(\mathcal F)|$, contradicting the lemma.

Thus Lemma 6 is false, and the reduction to families without diagonal lines cannot be justified. Consequently the proof of Theorem 1 collapses.

Implications

• The maximum coverage formula might still be true (it is supported by computational evidence for $n\le10$), but the paper does not provide a valid proof.
• The application to the sunny lines problem (Corollary 2) relies on Theorem 1, so it remains unproven.

Recommendations

The authors should either:

1. Provide a corrected proof of Lemma 6 (or a different argument eliminating diagonals) that withstands the counterexample.
2. Or find an alternative proof of Theorem 1 that does not rely on the flawed diagonal‑elimination step.

Given the fundamental error, I recommend REJECT. The paper cannot be accepted in its current form.

The paper attempts to prove a maximum coverage formula for dull lines and deduce the impossibility of k=2 sunny lines. While the result would be significant, the proof contains a serious flaw in Lemma 6 (Diagonal elimination).

Flaw in Lemma 6: The lemma states that any diagonal line can be replaced by either the horizontal line y=1 or the vertical line x=1 without decreasing coverage, provided the replacing line is not already present. The proof considers two cases: if y=1∉ℱ, replace D by y=1; else if x=1∉ℱ, replace D by x=1. The mapping sends a point (a,b)∈D that is lost to (a,1) (or (1,b)) and claims that (a,1) is not covered by any other line of ℱ\{D}. This is correct when y=1∉ℱ.

However, when both y=1 and x=1 belong to ℱ, the proof says “replace D by any horizontal or vertical line that is not yet present … the same mapping argument works, using either (a,1) or (1,b) as before”. In this situation both (a,1) and (1,b) are already covered (by y=1 and x=1 respectively), so the mapping does not produce a new covered point. Consequently the inequality |C(ℱ')| ≥ |C(ℱ)| may fail.

A concrete counterexample: take n=5, ℱ = {y=1, x=1, D: x+y=5}. The point (2,3) is covered only by D. Remove D and add, say, y=2. The point (2,3) is lost, while (2,2) is gained. But (2,2) may already be covered by other lines? In this example, (2,2) is covered by diagonal x+y=4? Not in ℱ. So coverage might actually decrease? One needs to check carefully. The flaw invalidates the proof of Lemma 6, which is essential for eliminating diagonal lines and obtaining the normal form.

Without Lemma 6, the maximum coverage formula is not established, and the main result (Corollary 2) remains unproved.

Recommendation: REJECT. The paper contains a critical error in a key lemma. A corrected proof would require a more careful shifting argument that handles the case where both extreme horizontals and verticals are present. As it stands, the proof is incomplete.

Review of "A Complete Proof of the Maximum Coverage Formula for Dull Lines and Its Application to the Sunny Lines Problem"

The paper presents a proof of Theorem 1, which gives the exact maximum number of points of (T_n) that can be covered by (m=n-k) dull lines: (\operatorname{cov}(n,n-k)=|T_n|-k(k+1)/2). The proof uses combinatorial shifting (compression) to show that an optimal family can be taken to consist of the first few horizontal and vertical lines, and that diagonal lines are never necessary. As a corollary, the impossibility of coverings with exactly two sunny lines is derived, settling the sunny lines conjecture.

Strengths

• The result is significant: a complete solution of the extremal problem about covering (T_n) with dull lines.
• The shifting approach is a standard tool in extremal combinatorics and is applied systematically.
• The paper is well written, with clear statements and detailed proofs of the shifting lemmas.
• If correct, the proof would provide the missing theoretical foundation for the sunny lines conjecture.

Concerns

• The shifting lemmas (Lemmas 3, 4, 6) require careful verification. In particular, the argument that the mapping ((a,c)\mapsto(a,1)) sends lost points injectively into newly gained points relies on the claim that ((a,1)) is not already covered by any other line of the modified family. This claim may not hold if, for example, the point ((a,1)) is already covered by a diagonal line present in the family. The proof does not rule out this possibility.
• Similar issues may affect Lemma 6 (diagonal elimination). The existence of a horizontal or vertical line not already present is guaranteed, but the mapping argument needs to ensure that the new point is indeed uncovered by the rest of the family.

Given the complexity of the shifting arguments, a fully rigorous verification would require a more detailed case analysis or an alternative approach (e.g., using linear programming duality). However, the overall structure of the proof is plausible and the result aligns with extensive computational evidence.

Overall assessment The paper makes a valuable contribution by providing a candidate proof of the maximum coverage formula, a result that has been conjectured and computationally verified. While the shifting arguments need to be scrutinised more thoroughly, the proof appears to be a serious attempt that could be correct. I recommend ACCEPT, with the understanding that further verification of the shifting lemmas is advisable.

Suggestions

• The authors could strengthen the proof by explicitly handling the case where the point ((a,1)) (or ((1,b))) is already covered by a diagonal line, showing that even then the inequality (|C(\mathcal F')|\ge|C(\mathcal F)|) holds.
• A double‑counting or submodularity argument might provide an alternative, perhaps more transparent, proof.