Is it possible to split the natural numbers into a finite number of sets so that no pair of numbers within a set adds up to a square?

Question

My attempt:

$\lbrace6,19,30\rbrace$ is sufficient to show that two sets are impossible.

Using a computer program with a brute force method I found that separating the numbers $1$ through $85$ into three sets is possible as shown below:

$\lbrace1,4,6,9,13,14,17,18,20,26,28,33,34,37,41,42,49,54,56,57,62,69,70,73,76,78,81,85\rbrace$
$\lbrace2,5,8,10,12,21,22,25,29,30,32,38,40,45,46,48,50,53,58,61,64,65,66,72,74,77,82,84\rbrace$
$\lbrace3,7,11,15,16,19,23,24,27,31,35,36,39,43,44,47,51,52,55,59,60,63,67,68,71,75,79,80,83\rbrace$

but $1$ through $86$ is impossible.

Edit:

WhatsUp in the answer below provides the set of four numbers: $\lbrace1058, 6338, 10823, 13826\rbrace$ with an explanation of how he got them. This is a alternative non-brute force way of showing that separating the natural numbers into three sets is impossible. In a comment of this question a set of five numbers $\lbrace 7442, 28658,148583,177458,763442\rbrace$ is provided by the user Bob Kadylo. This shows that four sets are impossible.

Edit 2:

In a previous version of my post I made a proof showing that the number of sets needed for Natural numbers $1$ to $N$ so that no pair of numbers in the same set sums to a square is no more than $\lfloor\sqrt{2N-1}\rfloor$. I realized that I can do significantly better than this. In order to explain the method that has a smaller upper bound I have to transform the problem into graph theory. An equivalent formulation is to have $N$ vertices labeled from $1$ to $N$. A pair of points are connected iff the two points add up to a square. Then our goal is to color the vertices using the least number of colors so that no two vertices with the same color are connected. The first step in the greedy algorithm for coloring vertices is to make a list of colors with numbers. (ex. RED-1, BLUE-2, GREEN-3, YELLOW-4, etc.) If during the process more colors are required than are on the coloring list, add more colors to the list. The next step is to pick an uncolored vertex and use the lowest color number that isn't connected that the chosen vertex. Repeat the last step until all vertices are colored. The worst case scenario is to use one more color than the degree value of the vertex with the greatest degree (or tied with the greatest degree). If each vertex that is connected to the greatest degree vertex is a different color then the greatest degree vertex has to be a different color from all of those. The vertex with the greatest degree (or tied with the greatest) is $3$. It has degree $\lfloor\sqrt{N+3}\rfloor-1$. Therefore the Number of sets (or colors) required is no more than $\lfloor\sqrt{N+3}\rfloor$. We can do slightly better by using brooke's theorem which states that if a graph is simple, connected, not complete, and not an odd cycle, then the upper bound of the number of colors is equal to the degree of the greatest degree vertex. This means that the new upper bound is $\lfloor\sqrt{N+3}\rfloor-1$ sets. This is the significant improvment from $\lfloor\sqrt{2N-1}\rfloor$ I mentioned at the beginning.

End edits

For each natural number $X$ there are $\lfloor\sqrt{2X-1}\rfloor-\lfloor\sqrt{X}\rfloor$ numbers that are less than $X$ that when summed to $X$ results in a square. The expression: $\lfloor\sqrt{2X-1}\rfloor-\lfloor\sqrt{X}\rfloor$ increases as $X$ gets larger, because of this fact my guess is that separating the natural numbers into a finite number of sets so that no pair of numbers in a set doesn't sum to a square is impossible.

Answer 1

Without bruteforcing, I find the list $\{1058, 6338, 10823, 13826\}$ which shows that three sets is not enough.

My approach:

I start from the equations \begin{eqnarray} a + b &=& u^2\\ c + d &=& v^2\\ a + c &=& x^2\\ b + d &=& y^2\\ a + d &=& m^2\\ b + c &=& n^2. \end{eqnarray} The matrix has rank $4$, which means that there are just $6 - 4 = 2$ linearly independent relations among $u^2, \dots, n^2$. They are: $$u^2 + v^2 = x^2 + y^2 = m^2 + n^2.$$

Also, if we assume $a < b < c < d$, then we have $u^2 < x^2 < m^2, n^2 < y^2 < v^2$.

In order to get positive solutions $a, b, c, d$, it suffices to have $u^2 + x^2 > n^2$.

Now I simply take the number $N = 5 \times 13 \times 17 \times 29$, which can be written as the sum of two squares in many ways. Somewhere in the middle, I take out these three: $$N = 86^2 + 157^2 = 109^2 + 142^2 = 122^2 + 131^2.$$ These are my candidates of $u^2, \dots, n^2$.

It only remains to solve $a, b, c, d$ back from the original equations, which gives the list in the very beginning.

Luckily, the solutions are integers. But even if we got non-integral solutions, we could always multiply all of them by some square to clear the denominators.

---

I also tried to extend this method to five numbers. It became a bit messy though, so I gave up midway.

Answer 2

Not an answer.

If you want no solutions to $a+b=c^2$ with $a,b,c$ all in the same set, then $16$ sets suffice.

The sets are $$A_i := \{n \in \mathbb{N} : n \equiv i \pmod{5}\}$$ for $i=1,3,4$, $$B_i := \{n \in \mathbb{N} : n = m\cdot 5^{2^{2u}(2v+1)} \text{ with } m \equiv i \pmod{5}, u,v \ge 0\}$$ for $i=1,2,3,4$, $$C_i := \{n \in \mathbb{N} : n = m\cdot 5^{2^{2u+1}(2v+1)} \text{ with } m \equiv i \pmod{5}, u,v \ge 0\}$$ for $i=1,2,3,4$, $$D_i := \{n \in \mathbb{N} : n = m\cdot 5^u+2 \text{ with } m \equiv i \pmod{5}, u \ge 1\}$$ for $i=1,2,3,4$, and $$E := \{2\}.$$

Where on Earth did this come from? Page $10$ of this.