Maximum Sized Sets With Sums That Avoid Squares (Jan. 2021)


1. Problem Introduction

Consider the following questions about sets of natural numbers:

Given a natural number \(n\), what is the largest subset of the natural numbers up to \(n\) such that no sums of two elements from this subset are squares? (For the remainder of the article, we will refer to this maximum subset as "the largest square sumless subset")

What percentage of the natural numbers can we include in a subset that has this "sumless" property?

How does this compare to other sets, ex. avoiding cubes, prime numbers, Fibonacci numbers, etc?

For example: What is the largest square sumless subset of \([1,3]\)?

We can pick either \(\{1\}\) or \(\{3\}\), but not both because \(1+3=2^2\). We also can not pick \(\{2\}\) because \(2+2=2^2\).

This problem is at the intersection of extremal number theory and extremal graph theory, and as with my other pages, I plan to continue to update this page as I find new results. After reading this page, if you have any new results, let me know and I will link to them or add them and attribute them to you.


2. Bounds and Constructions

The density of the squares in the natural numbers up to \(n\) is trivially \(\frac{1}{\sqrt{n}}\) which tends to \(0\) as \(n\) goes to infinity, so perhaps we might expect similar asymptotic behavior for the ratio of the largest square sumless subset to all natural numbers; however, my best lower bound (so far) via construction is \(\frac{1}{3} \approx 33.33%\) and my best upper bound is \(\frac{1}{2}+\epsilon\) beyond the trivial problem of \([1,1]\)

a. Two Lower Bound Constructions

There are two constructions that achieve this bound:

The less complicated construction involves taking all of the numbers \(\equiv 1\mod 3\) because \(2\) is quadratic nonresidue modulo \(3\).

The more complicated construction which achieves this bound is as follows:

Take all of the natural numbers \(x\) such that \(x \equiv (3 \times 4^{y-1}) \mod 4^y\) for some non-zero \(y \in \mathbb{N}\). Given that \(\sum_{y=1}^{\infty}\frac{1}{4^y}=\frac{1}{3}\) we get the lower bound construction.

A brief informal sketch of the proof that this subset contains no squares is as follows:

Take two natural numbers of the required form: \(4^a + 3 \times 4^{a-1}\) and \(4^b + 3 \times 4^{b-1}\) (WLOG, assume that \(a \geq b\))

Adding them together we get \(4^a + 4^b + 3 \times (4^{a-1}+4^{b-1})\)

We can divide through by \(4^{b-1}\) which is a square to get \(4^{a-b+1} + 4 + 3 \times 4^{a-b} + 3\)

When \(a=b\) we have \(4 + 4 + 3 + 3 \equiv 2\mod 4\).

When \(a \neq b\) we have \(4(4^{a-b} + 1 + 3 \times 4^{a-b-1}) + 3 \equiv 3\mod 4\).

\(2\) and \(3\) are quadratic nonresidue modulo \(4\), so the sums of elements in our subset will never be squares.

b. Two Upper Bound Limits

There are two ways of going about proving the upper bound of at least \(\frac{1}{2}+\epsilon\). Here is a very informal sketch of both ideas which also apply to other variants of the problem avoiding other sequences/subsets (ex. cubes or primes).

If there is a square sufficiently close to \(N\), then we split our subset of natural numbers at \(\frac{N}{2}\). At best we can either take \(\left \lfloor \frac{N}{2} \right \rfloor + a\) or \(\left \lfloor \frac{N}{2} \right \rfloor - a\) for all \(a \leq \left \lfloor \frac{N}{2} \right \rfloor\). In this case we are done, we have achieved a maximum density of \(\frac{1}{2}+\epsilon\).

An alternative approach is to iteratively take the next even square, perform this pairing around it, in this way we can assign each natural number to a square and each natural number to a unique pair (aside from those who are halves of squares). Each of these pairs can only contribute 1 number to the final maximal square sumless subset.

This bound is the most flexible when both there is no square sufficiently close to \(N\) and \(N\) is half of a square.

I have phrased this question in terms of sets of natural numbers, but we can just as well construct a graph with natural number vertices, edges between each two vertices when they add to a square, and then ask about the largest independent set of that graph. I believe that a non-trivial upper bound will be found through expressing this problem in that way.


3. Computational Results

I have calculated the maximal sized subsets from [0,1] to [0,100] using an inductive approach and determined the number of unique maximal subsets for each of these subsets of the natural numbers. All of the maximal subsets are slightly better than (or equal to) my best lower bound of \(\frac{1}{3}\), and when plotted, a line with a slope of \( \approx .365\) fits them with \(r^2 \approx .996\).

Below is a table of this information, and beneath this table is a discussion of maximal subsets that avoid other interesting sets of natural numbers.

[1,N]Max Subset SizeNumber of Optimal SubsetsLexically First Maximal Subset (including N) of equal or greater size to the maximal N-1 case
1111
211-
3123
4221 4
5241 5
6321 4 6
7421 4 6 7
842-
9441 4 6 9
104121 4 7 10
11561 4 6 7 11
125181 5 6 7 12
13641 4 6 7 11 13
146181 4 6 7 13 14
156283 5 7 12 14 15
167141 4 6 7 11 13 16
178141 4 6 7 11 13 16 17
18814-
198201 4 7 10 11 13 16 19
208361 4 6 7 11 13 17 20
21981 5 6 7 12 14 16 17 21
229441 4 6 7 11 13 16 17 22
2310171 5 6 7 12 14 16 17 21 23
2410253 5 7 10 14 16 17 21 23 24
251181 5 6 7 12 14 16 17 21 23 25
2611151 5 6 7 12 14 16 17 21 25 26
271271 5 6 7 12 14 16 17 21 23 25 27
2812331 4 6 7 13 14 16 17 25 26 27 28
2912611 4 6 13 14 16 17 25 26 27 28 29
3013121 5 7 10 12 14 16 17 21 23 25 27 30
3113971 4 6 7 13 14 16 17 25 26 27 28 31
321397-
33131231 4 6 7 13 14 17 20 25 26 27 28 33
341441 4 6 7 13 14 16 17 25 26 27 28 31 34
3514383 4 7 10 11 16 17 23 24 27 28 30 31 35
36141341 5 6 7 12 14 16 17 21 23 25 27 34 36
3715154 6 7 11 13 15 16 17 22 24 26 28 31 35 37
3815871 5 6 7 12 14 16 17 21 23 25 27 34 36 38
3916154 6 7 11 13 15 16 17 22 24 26 28 31 35 37 39
4016921 4 6 7 11 13 16 17 22 26 28 31 34 37 39 40
4117154 6 7 11 13 15 16 17 22 24 26 28 31 35 37 39 41
4217331 5 6 12 14 16 17 21 23 25 27 29 34 36 38 40 42
431854 7 11 13 15 16 17 22 24 26 28 30 31 35 37 39 41 43
4418161 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44
4518451 6 12 14 16 17 21 23 25 27 29 31 34 38 40 42 44 45
4619121 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46
4719171 10 12 14 16 19 21 23 25 27 29 31 36 38 40 42 44 46 47
4819474 7 11 13 15 17 20 22 24 26 28 30 31 35 37 39 41 43 48
4920171 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49
502017-
5120261 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 51
5220283 4 7 11 15 16 19 24 26 27 28 31 35 39 41 43 44 47 51 52
5321121 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49 53
542112-
552271 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49 53 55
56227-
572371 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49 53 55 57
58237-
592471 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49 53 55 57 59
60247-
612571 6 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49 53 55 57 59 61
62257-
6325216 12 14 16 17 21 23 25 27 29 31 34 36 38 40 42 44 46 49 53 55 57 59 61 63
6425357 11 13 15 16 22 24 26 28 30 31 35 37 39 41 43 45 47 52 54 56 58 60 62 64
652676 12 14 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65
6626167 11 13 16 22 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66
6726481 7 11 13 16 22 26 28 30 31 37 39 41 43 45 46 47 49 52 56 58 60 62 64 66 67
68261481 7 11 16 22 26 28 30 31 37 39 41 43 45 46 47 49 52 56 58 60 62 64 66 67 68
69261883 5 9 14 24 26 28 29 30 37 39 41 43 45 47 48 49 54 56 58 60 62 64 66 68 69
7027166 12 14 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 70
71271181 7 11 13 16 22 26 28 30 31 37 39 41 43 45 46 47 49 52 56 58 60 62 64 66 67 71
7227118-
73271691 5 6 9 13 14 17 21 25 26 29 33 34 37 41 42 45 46 49 53 57 61 62 65 69 70 73
74272231 5 9 10 13 14 17 21 25 29 30 33 37 38 41 42 45 46 49 53 57 61 65 66 69 73 74
7528663 7 11 12 20 26 27 28 30 31 35 39 41 43 45 47 48 49 56 58 60 62 64 66 67 68 71 75
7628946 12 14 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 70 76
7729323 7 11 16 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77
7829601 5 6 9 13 14 17 21 25 26 29 33 34 37 41 42 45 46 49 53 57 61 62 65 69 70 73 77 78
7930323 7 11 16 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77 79
8030586 12 14 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 70 76 78 80
8131323 7 11 16 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77 79 81
8231586 12 14 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 70 76 78 80 82
8332323 7 11 16 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77 79 81 83
8432586 12 14 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 70 76 78 80 82 84
8533323 7 11 16 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77 79 81 83 85
8633456 12 17 21 23 25 27 29 31 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 67 70 76 78 80 82 84 86
8734203 7 11 16 24 26 28 30 31 35 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77 79 81 83 85 87
883420-
8934963 5 7 14 16 24 26 28 30 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 71 75 77 79 81 83 85 87 89
90341104 6 15 17 23 25 27 29 36 38 40 42 44 46 48 51 53 55 57 59 61 63 65 67 69 74 76 78 80 82 84 86 88 90
9135253 5 7 14 16 24 26 28 37 39 41 43 45 47 49 52 54 56 58 60 62 64 66 68 70 71 75 77 79 81 83 85 87 89 91
9235393 7 12 20 26 27 28 31 35 39 41 43 45 47 48 49 56 58 60 62 64 66 67 68 70 71 75 79 81 83 85 87 89 91 92
9335514 6 17 23 25 27 34 36 38 40 42 44 46 48 49 53 55 57 59 61 63 65 67 69 70 71 78 80 82 84 86 88 90 92 93
94351481 5 7 16 22 26 28 37 39 41 43 45 46 47 49 56 58 60 62 64 66 67 68 69 70 71 79 81 83 85 87 89 91 92 94
95351694 6 15 17 23 25 27 36 38 40 42 44 46 48 51 53 55 57 59 61 63 65 67 69 71 76 78 80 82 84 86 88 90 92 95
9636401 5 7 16 22 26 28 37 39 41 43 45 46 47 49 56 58 60 62 64 66 67 68 69 70 71 79 81 83 85 87 89 91 92 94 96
9736761 5 7 16 22 26 28 37 39 41 43 45 46 49 56 58 60 62 64 66 67 68 69 70 71 79 81 83 85 87 89 91 92 94 96 97
983676-
9936904 6 15 17 23 25 27 36 38 40 42 44 46 48 51 53 55 57 59 61 63 65 67 69 71 74 76 78 80 82 84 86 88 90 92 99
100361623 4 7 11 15 19 20 23 24 27 28 31 35 39 43 47 48 51 55 56 59 63 64 67 68 71 75 79 83 84 87 91 92 95 99 100

4. Other Sets? (Or why squares?)

Perhaps this will be the only time that you will hear this, but of all the sets that I have tried, the primes are the least interesting (at least in the range that I tested). To avoid prime numbers, you can either select all of the even natural numbers or all of the odd natural numbers except for \(1\). In the extremal case, \(\frac{1}{2}+\epsilon\) density is the best that I can achieve. On bounded intervals of natural numbers, ex. [0,N], to improve this construction would require the following two conditions:

I conjecture that the maximal subset is this trivial solution.

The next two logical directions to go was to extend my search to maximal subsets that avoid cubes and that avoid Fibonacci Numbers.

The subsets that avoid these two sequences have similar densities at a small scale, but their growth is very different in this window.

Here is a graph of these values where blue is the max subset avoiding square sums, black is the max subset avoiding cube sums, and red is is max avoiding Fibonacci numbers.

The cubes oscillate between plateaus and sharp increases in max set subset size, while the Fibonacci case increases the maximum subset size more regularly. Both have a large number of maximal subsets for each value of \(N\) as well.

As an interesting note, the greedy approach of taking the next lowest possible value that does not sum with any existing values or itself to be a cube produces the exact same subset as the Lexically First Maximal Subset for the range of values that I checked. The places where the graph increases are the numbers which are included in this subset.

This greedy approach eventually fails to generate maximal subsets (it drastically decreases in density as you continue to larger sets of higher natural numbers). It is trivially possible to take \(\frac{1}{3}\) of the natural numbers by selecting all numbers with a remainder of \(1\), \(2\), or \(3\) modulo \(9\). (Proof omitted), and the density of the numbers selected by the greedy approach as \(N\) increases dips down near \(\frac{1}{4}\) around \(N=50,000\) before rebounding and increasing. Depending on the values that you use to seed the greedy approach (that is to say fix certain initial values to be part of the subset), it is possible to get wildly different curves; however, the best one appears to be unseeded in contrast to what we see for greedy squares and Fibonacci numbers.

Below is a graph of the density of this greedy subsets avoiding cubes for large values of \(N\), showing the aforementioned rebound behavior:

More theoretical work is needed to determine if this initial local behavior for Fibonacci numbers and cubes continues for larger intervals of the natural numbers.


5. Open Questions

(a) Can the upper and lower bounds on the size of subsets whose sums avoid squares be improved? (If so, how?)

(b) Can the upper and lower bounds on the size of subsets whose sums avoid cubes be improved? (If so, how?)

(c) Subsets whose sums avoid Fibonacci numbers are particularly resistant to trivial constructions. Is there a good construction over the natural numbers?

(d) Can we find non-trivial upper and lower bounds on the size of subsets whose sums avoid Fibonacci numbers? (If so, what are they?)

(e) Is the construction for subsets that avoid primes maximal for all \(N\)?

(f) Suppose instead I am picking a subset of rational numbers in the interval [0,1], how does the density of the maximal subset of this interval whose sums avoid rational squares compare to the natural numbers case?


Email: zachdestefano@gmail (dot) com

Back to My Recreational Math, Puzzles, and Ideas