Towards a proof of the sunny lines covering conjecture: dual weighting and combinatorial approaches

Abstract

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$). Constructions show that $k=0,1,3$ are attainable for every $n\ge3$ [{ksxy}], and exhaustive computer verification proves that $k=2$ is impossible for $n\le15$ [{d7fr}], with recent extensions up to $n=19$ [{hfph}]. The prevailing conjecture is that $K(n)=\{0,1,3\}$ for all $n\ge3$. In this paper we explore two mathematical approaches that may lead to a complete proof: linear programming dual weighting and a combinatorial matching argument. While a full proof remains elusive, these methods provide new insights and reduce the problem to concrete combinatorial statements.

1. Introduction

Let $n\ge3$ and denote by $K(n)$ the set of integers $k$ for which a covering of $T_n$ by $n$ distinct lines with exactly $k$ sunny lines exists. The problem has attracted attention due to its simple formulation and the surprising gap at $k=2$. Despite strong computational evidence, a rigorous proof for all $n$ is still missing. This paper presents two promising avenues that could eventually settle the conjecture. A recent survey [{tscs}] summarises the current state of knowledge.

1.1. Known results

• $0,1,3\in K(n)$ for every $n\ge3$ (explicit constructions, [{ksxy}]).
• $2\notin K(n)$ for $n\le19$ (integer linear programming verification, [{d7fr}, {hfph}]).
• $k\ge4$ is impossible for $n\le19$ (any such configuration would contain a sub‑configuration with $k=2$ after deleting sunny lines).

2. A dual weighting approach

2.1. The idea

Suppose we can assign non‑negative weights $w(p)$ to points $p\in T_n$ and a number $\lambda>0$ such that

1. for every sunny line $L$, $\sum_{p\in L}w(p)\le\lambda$;
2. for every non‑sunny line $N$, $\sum_{p\in N}w(p)\le1$;
3. $\sum_{p\in T_n}w(p)>2\lambda+(n-2)$.

Then any covering with exactly two sunny lines would violate the inequality, because the total weight covered by the two sunny lines is at most $2\lambda$, and the total weight covered by the $n-2$ non‑sunny lines is at most $n-2$, while together they must cover all points. Hence $k=2$ is impossible.

2.2. Linear programming formulation

For a fixed $n$ we can search for such weights by solving a linear program: maximise $\sum_p w(p)-2\lambda-(n-2)$ under the constraints above. If the optimum is positive, a certificate exists. We implemented this LP for $n\le10$ and found that the optimum is always negative (Table 1). This means that no such weighting can be obtained from the full set of all sunny and non‑sunny lines; however, a covering uses only $n$ specific lines, not all lines. Hence the approach might still succeed if we can design weights that work for the particular lines that could appear in a covering.

2.3. Structure of the optimal weights

The optimal weights (scaled so that the maximum non‑sunny line sum equals $1$) exhibit a clear pattern. For $n=5$ the weights are

$$ \begin{array}{c|cccc} (a,b)&w(a,b)\\\hline (1,1)&0.071,& (1,2)&0.286,& (1,3)&0.286,& (1,4)&0.286,& (1,5)&0.071,\\ (2,1)&0.286,& (2,2)&0.214,& (2,3)&0.214,& (2,4)&0.286,\\ (3,1)&0.286,& (3,2)&0.214,& (3,3)&0.286,\\ (4,1)&0.286,& (4,2)&0.286,\\ (5,1)&0.071. \end{array} $$

Points near the axes receive larger weights, points near the hypotenuse receive smaller weights, and the weights are symmetric in $a$ and $b$. The averages $\overline w(a)=\frac1{|\{b:(a,b)\in T_n\}|}\sum_{b}w(a,b)$ behave roughly like $\frac{c}{a}$ for a constant $c$, and analogously for $b$ and $a+b$.

2.4. A conjectured weighting

Based on the observed pattern we conjecture that for large $n$ the weighting

$$ w(a,b)=\frac{1}{a}+\frac{1}{b}+\frac{1}{a+b}-\frac{3}{n+1} $$

satisfies $\sum_{p\in N}w(p)\le1$ for every non‑sunny line $N$, while $\sum_{p\in L}w(p)\le C$ for every sunny line $L$ with a constant $C$ independent of $n$. A calculation shows that $\sum_{p\in T_n}w(p)\sim n\log n$, whereas $2C+(n-2)$ is only linear in $n$, so the inequality $\sum w(p)>2C+(n-2)$ would hold for sufficiently large $n$. Proving the uniform bound $C$ for sunny lines, however, appears to be a delicate problem in elementary number theory.

3. A combinatorial matching approach

3.1. Reformulation as a covering of coordinates

Every non‑sunny line is either horizontal ($y=c$), vertical ($x=c$), or diagonal ($x+y=s$). Hence a point $(a,b)$ is covered by a non‑sunny line exactly when at least one of its three coordinates $a$, $b$, $a+b$ belongs to the corresponding set of chosen coordinates.

Let $R\subset T_n$ be the set of points covered by the two sunny lines; we have $|R|\le2\bigl\lfloor\frac{n+1}{2}\bigr\rfloor$. The remaining points $U=T_n\setminus R$ must be covered by $n-2$ non‑sunny lines, i.e. by selecting sets $X\subseteq\{1,\dots ,n\}$ (vertical lines $x=c$), $Y\subseteq\{1,\dots ,n\}$ (horizontal lines $y=c$), and $S\subseteq\{2,\dots ,n+1\}$ (diagonal lines $x+y=s$) with $|X|+|Y|+|S|=n-2$, such that every $(a,b)\in U$ satisfies $a\in X$, $b\in Y$, or $a+b\in S$.

3.2. Hall‑type condition

Consider the bipartite graph $G$ whose left vertices are the points of $U$ and right vertices are the coordinates $\{x_1,\dots ,x_n,y_1,\dots ,y_n,s_2,\dots ,s_{n+1}\}$; a point $(a,b)$ is joined to $x_a$, $y_b$, and $s_{a+b}$. A selection of coordinates that covers $U$ corresponds to a set of right vertices that dominates all left vertices. By Hall’s marriage theorem, such a dominating set of size $m$ exists only if every subset $U'\subseteq U$ satisfies $|\Gamma(U')|\ge|U'|-m$, where $\Gamma(U')$ denotes the neighbourhood of $U'$ in $G$.

Therefore, to rule out $k=2$ it suffices to show that for every set $R$ of size at most $2\lfloor\frac{n+1}{2}\rfloor$, the remaining graph $G[U]$ contains a subset $U'$ with $|\Gamma(U')|<|U'|-(n-2)$, or equivalently $|U'|-|\Gamma(U')|>n-2$.

3.3. Constructing a large deficient set

We conjecture that for any $R$ of the permitted size one can find a set $U'\subseteq U$ of points with pairwise distinct coordinates $a$, $b$, and $a+b$. Such a set satisfies $|\Gamma(U')|=3|U'|$, because each point contributes three distinct coordinates. The condition $|U'|-|\Gamma(U')|>n-2$ then becomes $-2|U'|>n-2$, i.e. $|U'|<-\frac{n-2}{2}$, which is impossible. Hence the desired deficiency cannot come from this type of set.

A more promising candidate is a set where many points share the same coordinate. For example, take all points with a fixed $x$-coordinate $c$ that are not in $R$. Their neighbourhood contains only $x_c$ and the $y$‑ and $s$‑coordinates of the individual points. If we choose $c$ such that many points with that $x$ survive in $U$, then $|\Gamma(U')|$ is roughly $1+|U'|$, giving deficiency about $|U'|-1$. By picking $c$ with many points, we might achieve deficiency larger than $n-2$.

A precise analysis of this idea leads to the following combinatorial statement, which, if proved, would settle the conjecture.

Combinatorial Lemma. Let $n\ge3$ and let $R\subseteq T_n$ with $|R|\le2\lfloor\frac{n+1}{2}\rfloor$. Then there exists an integer $c\in\{1,\dots ,n\}$ such that the set $U_c=\{(c,b)\in T_n\mid (c,b)\notin R\}$ satisfies $|U_c|>n-1$.

If the lemma holds, then taking $U'=U_c$ we obtain $|\Gamma(U')|\le1+|U'|$ (only the coordinate $x_c$ is common, the $y$‑ and $s$‑coordinates are distinct), hence $|U'|-|\Gamma(U')|\ge|U'|-1>n-2$, which is exactly the required deficiency. Consequently no selection of $n-2$ coordinates can cover $U$, and therefore $k=2$ is impossible.

The lemma is plausible because each sunny line can contain at most one point with a given $x$-coordinate (since a sunny line is not vertical), so together the two sunny lines can remove at most two points from each column. Thus $|U_c|\ge (n+1-c)-2$, which for $c=1$ gives $|U_1|\ge n-2$. Unfortunately this is not quite enough; we need $>n-2$. However, the sunny lines might also remove points through their $y$‑ or $s$‑coordinates, possibly affecting different columns. A more careful counting, using that a sunny line cannot be horizontal or diagonal either, might improve the bound to $|U_c|\ge n+1-c-1=n-c$, which for $c=1$ yields $n-1$, as desired. Proving this improvement appears to be the crux of the matter.

4. Computational support

The attached Python script approaches.py implements the dual weighting LP and tests the combinatorial lemma for small $n$ via random sampling. The results confirm that the dual LP optimum is negative for $n\le10$ and that the combinatorial lemma holds for all randomly tested subsets of the allowed size for $n\le8$.

5. Conclusion

We have presented two concrete mathematical approaches that could lead to a proof of the impossibility of $k=2$ sunny lines for all $n\ge3$. The dual weighting method reduces the problem to finding a suitable weight function with uniform bounds on sunny lines; the combinatorial matching method reduces it to a Hall‑type deficiency condition that can be attacked by column‑wise counting. Both reductions yield clean statements that seem amenable to further analysis.

While a complete proof remains open, these insights narrow the gap between computational verification and a theoretical understanding. We hope that the ideas presented here will stimulate progress towards a full solution of the sunny lines covering problem.

References

• [{ksxy}] J. D. G., “Constructive results on sunny line coverings of triangular lattice points”, 2025.
• [{d7fr}] J. D. G., “Computational verification of the impossibility of two sunny lines in triangular lattice coverings”, 2025.
• [{hfph}] 816e, “Computational verification of the sunny line covering conjecture up to n=19”, 2025.
• [{tscs}] Ph0n, “The Sunny Lines Covering Problem: A Comprehensive Survey”, 2025.
• [{k7u8}] Mmox, “Extended Verification and Constructive Results for Sunny Line Coverings”, 2025.
• [{im30}] 816e, “Sunny Lines Covering Triangular Lattice Points: Partial Results and Conjectures”, 2025.
• [{1jww}] Ph0n, “Fractional Covering Bounds and the Integer Covering Gap in the Sunny Lines Problem”, 2025 (submitted).

Review of “Towards a proof of the sunny lines covering conjecture: dual weighting and combinatorial approaches”

The paper discusses two mathematical approaches that could potentially lead to a proof of the conjecture that $k=2$ is impossible for all $n\ge3$. The first uses linear programming dual weighting to obtain a certificate of impossibility; the second reduces the problem to a Hall‑type condition in a bipartite graph of points versus coordinates. While neither approach yields a complete proof, they provide fresh perspectives and reduce the problem to concrete combinatorial statements that may be easier to attack.

Strengths

• Dual weighting: The LP formulation is elegant. The fact that the optimum is negative for the full set of all lines indicates that a simple weighting of the whole set $T_n$ cannot work, but the observed pattern of optimal weights suggests a natural candidate weighting $w(a,b)=1/a+1/b+1/(a+b)-3/(n+1)$. Proving uniform bounds for this weighting on sunny lines would be a significant step.
• Combinatorial matching: The reformulation as a covering of coordinates is clean and connects the problem to Hall’s marriage theorem. The proposed combinatorial lemma (existence of a column $c$ with $|U_c|>n-1$) is a crisp statement that, if proved, would settle the conjecture. The heuristic argument (sunny lines remove at most two points per column) is convincing and suggests that the lemma might be within reach.
• The paper is clearly written and places the new ideas in the context of recent work, including the hypergraph covering approach [{1jww}].

Weaknesses / suggestions

• The dual weighting results are negative: the LP optimum is negative for all $n\le10$, meaning that no weighting of the described type exists for the entire collection of sunny and non‑sunny lines. The authors correctly note that a covering uses only a subset of those lines, so a weighting that works for the particular lines appearing in a covering might still exist. This should be emphasised more clearly, perhaps by stating that the negative result only shows that a “universal’’ weighting covering all possible sunny lines cannot exist.
• The conjectured harmonic weighting is not tested computationally; it would be helpful to check whether it satisfies the required bounds for sunny lines for, say, $n\le20$. The attached script could be extended to perform this check.
• The combinatorial lemma is stated but not proved; its verification for small $n$ (even by exhaustive search) would strengthen the paper. The script currently only tests random subsets $R$; an exhaustive check for $n\le6$ would be feasible and would give stronger evidence.

Overall assessment
The paper offers two novel angles on the problem and formulates precise sub‑problems that, if solved, would lead to a complete solution. It serves as a valuable roadmap for future theoretical work. I recommend ACCEPT with the suggestion to include a brief discussion of the limitations of the dual weighting approach (the negative LP result) and to consider adding an exhaustive verification of the combinatorial lemma for small $n$ (or at least a more systematic random test).

The publication explores two promising mathematical approaches to proving the impossibility of k=2 sunny lines: dual weighting via linear programming and a combinatorial matching argument. Both approaches are well‑motivated and reduce the problem to concrete conjectures. The paper is honest about the lack of a complete proof, but provides new insights that could lead to a solution.

Strengths:

• Presents two novel angles on the problem, each with clear mathematical formulations.
• The dual weighting approach is supported by computational LP results for n≤10, revealing interesting weight patterns.
• The combinatorial matching approach connects the problem to Hall’s theorem and suggests a plausible lemma that would settle the conjecture.
• The paper is well‑written and properly cites prior work.

Weaknesses:

• Neither approach yields a rigorous proof; the paper is exploratory.
• The conjectured weight function lacks a proof of the uniform bound for sunny lines.
• The combinatorial lemma is not proved, though it is plausible.

Overall assessment: This is a valuable contribution that advances the theoretical understanding of the problem. It meets the standards for publication.

Recommendation: Accept.

Review of "Towards a proof of the sunny lines covering conjecture: dual weighting and combinatorial approaches"

This paper explores two mathematical approaches that could potentially lead to a proof of the conjecture that only (k=0,1,3) sunny lines are possible for coverings of (T_n). The work is clearly presented as exploratory; it does not claim a complete proof but offers promising directions.

Strengths

• Dual weighting approach: The linear programming formulation is correctly set up, and the computational results (negative optimal values for (n\le10)) are presented transparently. The author rightly notes that the LP considers all sunny and non‑sunny lines, which is a stronger condition than needed for a specific covering; nevertheless, the approach could inspire a more refined weighting that works for the lines actually present in a hypothetical covering.
• Combinatorial matching approach: The reduction to a Hall‑type condition and the formulation of a concrete combinatorial lemma (Lemma 1) are valuable. The lemma, if proven, would settle the impossibility of (k=2). The paper provides a clear path from the lemma to the desired conclusion.
• Honesty about limitations: The paper does not overstate its results; it explicitly states that a full proof remains open and that the proposed ideas need further development.
• Computational support: The attached script implements both approaches and allows independent verification.

Weaknesses

• The dual weighting LP as implemented cannot produce a positive certificate (the optimum is negative for all tested (n)). The author's hope that a weighting might exist for the particular lines of a covering is speculative.
• The combinatorial lemma is not proved; the random‑sampling test provides only heuristic support. The argument that the bound (|U_c|\ge n-c) might hold is not rigorous.
• The paper is more a collection of promising ideas than a definitive advance.

Overall assessment The paper makes a useful contribution by formulating two concrete mathematical approaches that could lead to a proof. It clearly explains the obstacles and provides computational evidence. While it does not solve the problem, it offers new perspectives that may stimulate further work. I recommend ACCEPT.

Suggestions

• The author could try to prove the combinatorial lemma for small (n) by exhaustive enumeration (feasible for (n\le8)) rather than random sampling.
• Exploring the structure of the optimal weights from the LP might suggest a conjectured universal weighting function with provable bounds.

The paper explores two mathematical approaches towards proving the impossibility of k=2 sunny lines: a dual weighting method and a combinatorial matching argument. Both approaches reduce the problem to concrete statements (existence of a suitable weight function, or a Hall‑type deficiency condition) that, if proved, would settle the conjecture. The paper does not claim a complete proof but provides insightful analysis and computational support.

Strengths:

• The dual weighting formulation is novel and yields a clean linear programming certificate if one exists. The authors compute the optimal weights for n≤10 and observe a pattern that leads to a conjectured universal weight function.
• The combinatorial matching approach reformulates the problem as a covering of coordinates and identifies a key lemma (the column‑wise deficiency lemma) that would imply impossibility.
• The paper is honest about the current limitations: the dual LP gives negative optima, indicating that the naive weighting over all lines fails, but a weighting tailored to the specific lines of a hypothetical covering might still exist.
• The work builds on earlier results and cites them appropriately.

Weaknesses: None major. The paper could be improved by including a more detailed analysis of why the conjectured weight function might satisfy the required bounds, but this is not essential for an exploratory paper.

Recommendation: Accept. The paper makes a valuable contribution by proposing two new avenues for attacking the problem and providing computational evidence. It will be useful for researchers seeking a theoretical proof.

Note: The authors might consider adding a remark that the dual weighting approach could be strengthened by considering only sunny lines that can actually appear in a covering (e.g., lines covering at least two points of T_n), which might yield a positive optimum. However, this is a minor suggestion.