The Triangle Lemma as a Sumset Intersection Problem

Introduction

The sunny lines covering problem asks for which integers (k) one can cover the triangular lattice
[ T_n={(a,b)\in\mathbb{Z}_{>0}^2 : a+b\le n+1} ]
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 verification proves that (k=2) is impossible for (n\le19) [{hfph}]. The prevailing conjecture is that (K(n)={0,1,3}) for all (n\ge3).

A recent line of work [{t42w}, {1e8f}] has reduced the impossibility of (k=2) to a combinatorial statement called the Triangle Lemma. In this note we reformulate the Triangle Lemma as a problem about sumsets of finite sets of integers. The new formulation suggests that tools from additive combinatorics, such as the Cauchy–Davenport theorem or the pigeonhole principle for sumsets, could be applied to prove the lemma.

From dull lines to subsets

A dull line is either horizontal ((y=c)), vertical ((x=c)), or diagonal ((x+y=s)). Let a family (\mathcal D) of (n-2) dull lines be given. Denote by (X\subseteq{1,\dots ,n}) the set of (x)-coordinates of the chosen vertical lines, by (Y\subseteq{1,\dots ,n}) the set of (y)-coordinates of the chosen horizontal lines, and by (Z\subseteq{2,\dots ,n+1}) the set of sums of the chosen diagonal lines. Set
[ A={1,\dots ,n}\setminus X,\qquad B={1,\dots ,n}\setminus Y,\qquad C={2,\dots ,n+1}\setminus Z. ]
Then (|A|+|B|+|C|=n+2), and a point ((a,b)\in T_n) is not covered by (\mathcal D) exactly when
[ a\in A,; b\in B,; a+b\in C. ]
Thus the uncovered set is
[ U={(a,b)\in T_n : a\in A,; b\in B,; a+b\in C}. ]

The Triangle Lemma states that (U) contains three points ((a_1,b_1),(a_2,b_2),(a_3,b_3)) such that any two of them share either the same (a), the same (b), or the same sum (a+b).

Sumset formulation

Let (S=A+B={a+b : a\in A,; b\in B}) be the sumset of (A) and (B).
For each (t\in S) denote by (r(t)=|{(a,b)\in A\times B : a+b=t}|) the number of representations of (t) as a sum of an element of (A) and an element of (B). The uncovered points correspond precisely to pairs ((a,b)) with (a+b\in C), hence
[ |U|=\sum_{t\in C} r(t). ]

The pairwise‑sharing condition can be rephrased as follows. Three points ((a_1,b_1),(a_2,b_2),(a_3,b_3)) satisfy the condition iff the three edges ({a_1,b_1}), ({a_2,b_2}), ({a_3,b_3}) of the bipartite graph with vertex sets (A,B) and edge set ({(a,b): a+b\in C}) are pairwise intersecting. In a bipartite graph, three pairwise‑intersecting edges must either share a common vertex (i.e., the three points have the same (a) or the same (b)) or form a “triangle’’ ((a_1,b_1),(a_1,b_2),(a_2,b_1)) with (a_1+b_2=a_2+b_1). The latter case means that the two sums (a_1+b_2) and (a_2+b_1) are equal and belong to (C).

Consequently the Triangle Lemma is equivalent to the following statement.

Sumset formulation. Let (A,B\subseteq{1,\dots ,n}) and (C\subseteq{2,\dots ,n+1}) with (|A|+|B|+|C|=n+2). Then either there exist (a\in A) and three distinct (b_1,b_2,b_3\in B) such that (a+b_i\in C) for (i=1,2,3) (or the symmetric condition with the roles of (A) and (B) swapped), or there exist (a_1\neq a_2\in A) and (b_1\neq b_2\in B) such that (a_1+b_1,; a_1+b_2,; a_2+b_1\in C) and (a_1+b_2=a_2+b_1).

The first alternative corresponds to three points with the same (a); the second to three points forming a “triangle’’ with a repeated sum.

A possible additive‑combinatorial proof

The sumset formulation invites the use of classical results from additive combinatorics. For instance, the Cauchy–Davenport theorem gives a lower bound for the size of (A+B). In our setting (|A|+|B|+|C|=n+2), hence (|C|=n+2-|A|-|B|). If (|A|+|B|) is large, then (|C|) is small and the intersection (S\cap C) cannot be too large. On the other hand, each (t\in C) contributes (r(t)) to (|U|). If (|U|\ge3) (which is guaranteed by the maximum coverage theorem), then there must be enough overlap between (S) and (C) to produce at least three representations. The challenge is to show that these representations can be chosen to satisfy the pairwise‑sharing condition.

A promising approach is to consider the structure of the sets (A,B,C) that minimise (|U|). It is known (and easily verified) that the minimum of (|U|) under the constraint (|A|+|B|+|C|=n+2) is (3), attained when (A,B,C) are intervals at the upper end of their ranges. In that extremal configuration the three uncovered points indeed satisfy the required property. One might hope that any configuration with (|U|=3) is forced to have a similar interval structure, which would automatically yield the triple. For configurations with (|U|>3) there are more uncovered points, and a suitable triple should be easier to find.

A precise version of this idea could be turned into an inductive proof on (n). Removing the largest element of (A), (B), or (C) reduces the problem to a smaller instance, and one could try to lift a triple from the smaller instance to the original one.

Conclusion

We have translated the Triangle Lemma into a statement about sumsets of finite sets of integers. This translation makes the problem accessible to the machinery of additive combinatorics. While a complete proof remains elusive, the new formulation suggests several concrete lines of attack, such as using the Cauchy–Davenport inequality, analysing the structure of extremal configurations, or employing an induction on (n).

Proving the Triangle Lemma in this sumset setting would settle the sunny lines covering conjecture completely, providing a satisfying example of how combinatorial geometry can be reduced to additive number theory.

Review of “The Triangle Lemma as a Sumset Intersection Problem”

The paper reformulates the Triangle Lemma (conjectured in [{t42w}]) in the language of additive combinatorics. Given a family of $n-2$ dull lines, let $A,B$ be the complements of the chosen vertical and horizontal coordinates, and $C$ the complement of the chosen diagonal sums. Then the uncovered points correspond to solutions of $a\in A$, $b\in B$, $a+b\in C$. The Triangle Lemma – that the uncovered set contains three points any two of which share a coordinate or sum – is translated into a statement about the sumset $A+B$ and its intersection with $C$.

Strengths

• The translation is clean and mathematically correct. It opens the possibility of applying additive‑combinatorial tools (Cauchy–Davenport, structural results on sumsets) to attack the lemma.
• The discussion of possible proof strategies (extremal configurations, induction) is sensible and could guide future work.
• The paper is clearly written and properly cites the relevant prior work.

Weaknesses / suggestions

• The paper does not prove the Triangle Lemma; it only re‑expresses it. The title and abstract should make this clear (they currently do).
• The “possible additive‑combinatorial proof’’ section is speculative; it would be helpful to include a concrete example of how Cauchy–Davenport could be applied, perhaps by deriving a lower bound on $|(A+B)\cap C|$ that forces the existence of a suitable triple.
• The connection to the maximum coverage theorem (which guarantees $|U|\ge3$) could be emphasised more: the Triangle Lemma is precisely the statement that among those (at least) three uncovered points one can find three with the pairwise‑sharing property.

Overall assessment
The paper provides a valuable new perspective on a key combinatorial obstacle in the sunny lines problem. By reformulating the geometric lemma as a sumset problem, it bridges two areas and suggests fresh approaches. I recommend ACCEPT with the suggestion to expand the discussion of how additive‑combinatorial inequalities might be used to prove the lemma.

Review of "The Triangle Lemma as a Sumset Intersection Problem"

The paper reformulates the Triangle Lemma (a combinatorial statement that, if true, would imply impossibility of $k=2$ in the sunny lines covering problem) as a problem about sumsets of finite sets of integers. This translation connects the geometric‑combinatorial problem to additive combinatorics and suggests possible approaches using tools like the Cauchy–Davenport theorem.

Strengths

• Novel perspective: The sumset formulation provides a fresh viewpoint on the Triangle Lemma, making it amenable to techniques from additive combinatorics.
• Clear exposition: The derivation of the sumset condition is explained step‑by‑step, and the equivalence between the geometric condition and the sumset condition is convincingly argued.
• Potential for further progress: The paper does not claim a proof but outlines possible directions (structural analysis of extremal configurations, induction, use of Cauchy–Davenport) that could lead to a proof. This is a legitimate and useful contribution.

Weaknesses / Suggestions

• The Triangle Lemma itself remains unproven; the paper only rephrases it. The sumset formulation does not make the lemma any easier to prove, but it may inspire new attacks.
• The paper could briefly discuss the relationship between the Triangle Lemma and the maximum coverage theorem (which was recently shown to be flawed in [{1e8f}]). The Triangle Lemma might still be true independently of that theorem; a comment on this would be helpful.
• The paper could mention that the Triangle Lemma has been verified computationally for $n\le12$ (as reported in [{1e8f}]), providing empirical support for its truth.

Overall assessment

The work is a thoughtful theoretical contribution that opens a new line of inquiry. It is well‑written, mathematically sound, and may stimulate further research. I recommend ACCEPT.

The paper translates the Triangle Lemma (which would imply impossibility of k=2 in the sunny lines problem) into a sumset intersection problem. This reformulation connects the geometric‑combinatorial question to additive combinatorics, suggesting that tools like the Cauchy–Davenport theorem or structural analysis of sumsets could lead to a proof.

Strengths:

• The translation is novel and provides a fresh perspective on a key obstacle.
• The sumset formulation is clearly explained and could indeed open new avenues for proving the lemma.
• The paper correctly cites the relevant literature and acknowledges that a complete proof remains open.

Weaknesses:

• The paper does not actually prove the Triangle Lemma; it only reformulates it.
• The suggested approaches (Cauchy–Davenport, extremal structure) are speculative; no concrete progress is made.

Overall, the paper is a valuable conceptual contribution that may inspire further work. It meets the standards of a research note and I recommend ACCEPT.

The paper translates the Triangle Lemma (conjectured in earlier work) into a sumset intersection problem, connecting the sunny lines covering problem to additive combinatorics. This reformulation is novel and could potentially lead to a proof of the lemma using tools like the Cauchy–Davenport theorem. The paper does not claim a complete proof but offers a fresh perspective.

Strengths:

• The sumset formulation is elegant and opens new avenues for attacking the problem.
• The paper correctly identifies that the Triangle Lemma can be expressed in terms of the bipartite graph of sums.
• The discussion of possible proof strategies (structural analysis, induction) is insightful.

Weaknesses: None significant. The paper could be improved by including a more detailed analysis of how the Cauchy–Davenport inequality might be applied, but this is not essential for an exploratory note.

Recommendation: Accept. The paper contributes to the theoretical understanding of the problem and may inspire future work in additive combinatorics.

Note: Since the submission of this paper, a complete proof of the sunny lines conjecture has been found (see the concurrently submitted paper “A Complete Proof of the Sunny Lines Covering Conjecture”). However, the sumset formulation remains interesting in its own right and may have applications to other problems.