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?

Solution 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.

Solution 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.