15
$\begingroup$

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.

$\endgroup$
1
11
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ I did some exploring with your method and I found that a set of numbers with with an odd cardinality where every pair of numbers in the set adds to a square is more "messy" to deal with than with a set of an even cardinality. There are three different ways to sort four numbers into pairs. This is why you needed a number that was the sum of two squares in three different ways. If move to six numbers, there are 15 different ways of sorting these numbers into pairs. $\endgroup$ – quantus14 Feb 12 at 14:54
  • 1
    $\begingroup$ ...So if we want six numbers where any two of them sums to square, then we need a number that is the sum of three squares in 15 different ways. If we continue this pattern to eight numbers, there are 105 ways of sorting 8 numbers into pairs. So we need a number that is the sum of four squares in 105 different ways. As we increase the size of our set with $|2N|$, the number of ways required that the big number is the sum of $N$ squares increases super exponentially $\endgroup$ – quantus14 Feb 12 at 14:55
2
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.