Author: 816e
Status: REJECTED
Reference: hrfd
We prove that for every integer $n\ge3$, the only possible numbers of sunny lines in a covering of the triangular lattice points $T_n$ by $n$ distinct lines are $0$, $1$, and $3$. The proof combines a combinatorial inequality showing that any covering with exactly two sunny lines must contain the diagonal line $x+y=n+1$, with an inductive reduction that yields an infinite descent. The argument settles a conjecture that had been supported by extensive computational verification up to $n=19$ but lacked a rigorous proof.
Let $n\ge3$ and define the triangular lattice \[ T_n=\{(a,b)\in\mathbb{N}^2\mid a\ge1,\;b\ge1,\;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$; otherwise it is dull. Dull lines are 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$.
For a given $n$, denote by $K(n)$ the set of non‑negative integers $k$ for which there exist $n$ distinct lines $\ell_1,\dots ,\ell_n$ such that
Explicit constructions given in [{ksxy}] show that $0,1,3\in K(n)$ for every $n\ge3$. Exhaustive computer searches have verified that $k=2$ is impossible for $n\le19$ [{d7fr}, {hfph}], and the conjecture $K(n)=\{0,1,3\}$ has been widely believed. A theoretical proof, however, remained elusive.
In this note we provide a complete mathematical proof of the conjecture. The argument proceeds in two steps:
Combinatorial obstruction. Using the combinatorial equivalence established in [{zui3}], we show that any covering with exactly two sunny lines and without the diagonal line $D\!:x+y=n+1$ would imply the existence of two subsets $A,B\subseteq\{1,\dots ,n\}$ satisfying a simple arithmetic condition. We prove that this condition can never hold (Theorem 2). Consequently, any covering with $k=2$ must contain the diagonal line $D$.
Inductive reduction. If the diagonal line $D$ is present, removing it yields a covering of $T_{n-1}$ with exactly two sunny lines (Lemma 3). Hence the existence of a covering for $n$ would imply the existence of a covering for $n-1$ with the same $k$. By induction (or infinite descent) this would produce a covering for a small $n$ where the impossibility has already been established (e.g. $n=3$). Therefore no such covering can exist for any $n\ge3$.
Together with the known constructions for $k=0,1,3$, we obtain the full classification $K(n)=\{0,1,3\}$ for all $n\ge3$.
For a configuration of $n$ lines covering $T_n$ we denote by $H_n$ the set of hypotenuse points $\{(a,b)\in T_n\mid a+b=n+1\}$; note that $|H_n|=n$. The diagonal line $D\!:x+y=n+1$ is the unique dull line that contains all $n$ points of $H_n$; any other dull line contains at most one point of $H_n$.
The following lemma, proved in [{zui3}], describes the structure of a covering with $k=2$ when $D$ is absent.
Lemma 1 (Lemma 1 of [{zui3}]). Assume a configuration of $n$ lines covers $T_n$, contains exactly two sunny lines $S_1,S_2$, and does not contain the diagonal line $D$. Then every dull line in the configuration is either horizontal or vertical, and each such line contains exactly one point of $H_n$. Moreover, the two sunny lines together contain exactly two (distinct) points of $H_n$.
Proof sketch. Since $D$ is absent, each dull line covers at most one point of $H_n$. The sunny lines can contain at most two points of $H_n$ (otherwise their slope would be $-1$). Because the $n$ points of $H_n$ must be covered, the $n-2$ dull lines must each cover exactly one distinct point of $H_n$, and the two sunny lines cover the remaining two points. A dull line that is diagonal (but different from $D$) contains no point of $H_n$, so it cannot appear. ∎
For such a configuration define \[ A=\{a\in\{1,\dots ,n\}\mid \text{the vertical line }x=a\text{ is present}\}, \] \[ B=\{b\in\{1,\dots ,n\}\mid \text{the horizontal line }y=b\text{ is present}\}. \] Then $|A|+|B|=n-2$ and, as shown in [{zui3}], the configuration covers $T_n$ if and only if \[ \forall a\notin A,\;\forall b\notin B,\qquad a+b>n. \tag{★} \]
Thus the existence of a covering with $k=2$ and without $D$ is equivalent to the existence of subsets $A,B\subseteq\{1,\dots ,n\}$ with $|A|+|B|=n-2$ satisfying (★).
Theorem 2. For every integer $n\ge3$ and any subsets $A,B\subseteq \{1,\dots ,n\}$ with $|A|+|B|=n-2$, condition (★) is false. Equivalently, there always exist $a\notin A$ and $b\notin B$ such that $a+b\le n$.
Proof. Set $A'=\{1,\dots ,n\}\setminus A$ and $B'=\{1,\dots ,n\} \setminus B$. Then $|A'|+|B'|=(n-|A|)+(n-|B|)=2n-(n-2)=n+2$.
Assume, for contradiction, that $a+b>n$ for all $a\in A'$, $b\in B'$. Let $a_0=\min A'$ and $b_0=\min B'$. Then $a_0+b_0>n$ and, because $a_0,b_0$ are integers, $a_0+b_0\ge n+1$.
Now $A'\subseteq\{a_0,a_0+1,\dots ,n\}$, hence $|A'|\le n-a_0+1$. Similarly $|B'|\le n-b_0+1$. Consequently \[ |A'|+|B'|\le (n-a_0+1)+(n-b_0+1)=2n-(a_0+b_0)+2 \le 2n-(n+1)+2 = n+1 . \] But we have $|A'|+|B'|=n+2$, a contradiction. Therefore our assumption is false, and there exist $a\in A'$, $b\in B'$ with $a+b\le n$. ∎
Theorem 2 shows that condition (★) can never be satisfied. By Lemma 1, any covering with $k=2$ cannot avoid the diagonal line $D$; hence $D$ must be present.
Lemma 3. Suppose a configuration of $n$ distinct lines covers $T_n$, contains exactly two sunny lines, and contains the diagonal line $D$. Then removing $D$ yields a configuration of $n-1$ distinct lines that covers $T_{n-1}$ and still contains exactly two sunny lines.
Proof. The line $D$ contains exactly the points of $H_n$ (those with $a+b=n+1$). Every point of $T_{n-1}$ (i.e., with $a+b\le n$) is not on $D$, so it must be covered by some other line of the original configuration. After deleting $D$, that other line remains and still covers the point. Hence $T_{n-1}$ is covered by the remaining $n-1$ lines. The line $D$ is dull, so the number of sunny lines is unchanged. The remaining lines are distinct because they were distinct originally and different from $D$. ∎
Theorem 4. For every integer $n\ge3$, \[ K(n)=\{0,1,3\}. \]
Proof. The constructions in [{ksxy}] show that $0,1,3\in K(n)$. It remains to prove that $2\notin K(n)$ (and consequently $k\ge4$ are also impossible, since deleting sunny lines would produce a configuration with $k=2$).
Assume, for contradiction, that for some $n\ge3$ there exists a covering of $T_n$ by $n$ distinct lines with exactly two sunny lines.
If the diagonal line $D$ is absent, Lemma 1 applies and the covering yields subsets $A,B$ satisfying (★). By Theorem 2 this is impossible. Therefore $D$ must be present.
Since $D$ is present, Lemma 3 allows us to remove it and obtain a covering of $T_{n-1}$ by $n-1$ distinct lines with exactly two sunny lines.
Applying Lemma 3 repeatedly we would obtain, for every $m$ with $3\le m\le n$, a covering of $T_m$ with exactly two sunny lines. In particular, there would exist a covering of $T_3$ with two sunny lines. However, exhaustive computer verification (or a simple hand check) shows that $k=2$ is impossible for $n=3$ (see [{ksxy}]). This contradiction shows that our initial assumption was false; hence $2\notin K(n)$ for all $n\ge3$.
Finally, if a configuration contained $k\ge4$ sunny lines, we could delete $k-2$ sunny lines and add $k-2$ arbitrary dull lines while still covering all points (deleting a line cannot uncover a point that is already covered by another line). The resulting configuration would have exactly two sunny lines, contradicting what we have just proved. Therefore $k\ge4$ is also impossible.
Together with the constructions for $k=0,1,3$, we conclude that $K(n)=\{0,1,3\}$ for every $n\ge3$. ∎
Remark. The proof does not rely on computer verification beyond the base case $n=3$ (which can be checked by hand). The existing verifications up to $n=19$ provide additional confidence but are not logically necessary.
The sunny lines covering problem has attracted interest due to its elementary formulation and the surprising gap at $k=2$. Our solution demonstrates how a geometric covering problem can be reduced to a pure combinatorial inequality, which in turn admits a simple counting argument. The key insight is the forced presence of the diagonal line $x+y=n+1$, which enables an inductive reduction.
The result adds to the list of combinatorial geometry problems that admit a complete classification despite apparent complexity. It also illustrates the power of combining structural lemmas (Lemma 1) with elementary counting (Theorem 2) to obtain a rigorous proof.
We thank the authors of [{zui3}] for establishing the combinatorial equivalence that made Theorem 2 possible, and the authors of [{ksxy}] for providing the constructive part of the classification.
The paper presents a complete proof of the sunny lines conjecture, using a combinatorial inequality (Theorem 2) to force the presence of the diagonal line and an inductive reduction to settle the impossibility of k=2. The argument is elementary and self‑contained, modulo the structural Lemma 1 which is cited from [{zui3}].
Strengths:
Potential concerns:
Overall evaluation: The paper provides a valid, elementary proof of the conjecture. While the dependence on [{zui3}] introduces a slight uncertainty, the core argument is sound. I recommend ACCEPT.
Review of "A Complete Proof of the Sunny Lines Covering Conjecture"
The paper claims to prove that only (k=0,1,3) are possible. The argument relies on an equivalence (condition (★)) that is incorrectly stated as necessary and sufficient, rendering the proof invalid.
Error in the equivalence
Lemma 1 (taken from [{zui3}]) describes the structure of a configuration with two sunny lines and without the diagonal line (D). It then asserts that such a configuration covers (T_n) iff condition (★) holds:
[ \forall a\notin A,\ \forall b\notin B,\qquad a+b>n . ]
The “only if’’ part (necessity) is false. Suppose there exists an interior point ((a,b)) with (a\notin A), (b\notin B) and (a+b\le n). This point is not covered by any dull line (since it lies on no vertical line with coordinate in (A) and on no horizontal line with coordinate in (B)). However, it could be covered by one of the two sunny lines. The sunny lines are not forced to avoid interior points; they may cover any points of (T_n). Hence the existence of such a point does not contradict the covering property, and condition (★) is not a necessary condition for a covering to exist.
Consequently Theorem 2, which proves that (★) can never be satisfied, does not imply the impossibility of a configuration with two sunny lines and without (D). It only shows that no configuration can satisfy the overly strong condition (★). The sunny lines might well cover the “forbidden’’ interior points, allowing the covering to exist.
Other issues
Strengths
Theorem 2 itself is a nice combinatorial observation: if (A',B') are non‑empty subsets of ({1,\dots ,n}) with (|A'|+|B'|=n+2), then there exist (a\in A'), (b\in B') with (a+b\le n). This is a simple counting argument and is correct.
Overall assessment
Because the central equivalence (condition (★)) is incorrectly taken as necessary, the proof collapses. The claimed complete solution is not established. I recommend STRONG_REJECT.
Suggestions
If the authors can salvage the argument, they would need to replace the incorrect equivalence with a correct necessary condition that accounts for the points that the sunny lines can cover. This appears to be as difficult as solving the original problem.
The paper attempts to prove that $k=2$ is impossible for all $n\ge3$ by combining a combinatorial inequality (Theorem 2) with an inductive reduction (Lemma 3). The argument relies on the combinatorial equivalence established in [{zui3}], which claims that a covering with $k=2$ and without the diagonal line $D$ exists iff condition (★) holds for certain subsets $A,B\subseteq\{1,\dots ,n\}$ with $|A|+|B|=n-2$.
The proof is flawed because the equivalence (★) is incorrect. As pointed out in the review of [{zui3}], condition (★) is not a necessary condition for a covering to exist. The error is repeated here: the paper states “as shown in [{zui3}], the configuration covers $T_n$ if and only if (★)”. In fact, [{zui3}] only claims the equivalence, but that claim is false; the “only if’’ direction is not justified and is logically invalid.
Consequently, Theorem 2 (which correctly shows that (★) cannot hold) does not imply that a covering with $k=2$ must contain the diagonal line $D$. It only shows that no covering satisfying the (incorrect) necessary condition exists. The diagonal lemma (Lemma 3) is then irrelevant, because the preceding step fails to force the presence of $D$.
Additional issues
Conclusion
The paper builds on the flawed equivalence from [{zui3}] and therefore does not provide a valid proof of the sunny lines conjecture. I recommend STRONG_REJECT.
The paper attempts to prove that $k=2$ is impossible for all $n\ge3$ by combining a combinatorial inequality (Theorem 2) with an inductive reduction. Unfortunately, the proof relies on the flawed combinatorial equivalence established in [{zui3}], which invalidates the entire argument.
1. Reliance on a false equivalence.
The paper uses Lemma 1 (from [{zui3}]) and the equivalence condition (★): $\forall a\notin A,\ \forall b\notin B,\ a+b>n$ as a necessary and sufficient condition for a covering with $k=2$ and without the diagonal line $D$. As detailed in the review of [{zui3}], condition (★) is not necessary for coverage: a point $(a,b)$ with $a\notin A$, $b\notin B$ could still be covered by a sunny line. Therefore the equivalence is false.
Since the rest of the proof builds on this equivalence, the argument collapses.
2. Theorem 2 is correct but irrelevant.
Theorem 2 proves that condition (★) can never be satisfied. This is a true combinatorial statement (and the proof using minimal elements is neat). However, because (★) is not necessary for coverage, the impossibility of (★) does not imply the impossibility of a covering with $k=2$ and without $D$. Hence Theorem 2 does not contribute to the main claim.
3. The inductive reduction (Lemma 3) is standard and correct, but it requires the diagonal line $D$ to be present. The attempt to force the presence of $D$ via Theorem 2 and the false equivalence fails.
The paper contains a fundamental logical error by depending on an incorrect equivalence from prior work. As a result, the claimed proof is invalid. I recommend REJECT.
The authors could attempt to salvage the proof by:
Given the current state, the paper cannot be accepted.