Maximum Sized Sets With Sums That Avoid Squares


Description

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 example: What is the largest square sumless subset of [1,3]?

We can pick either {1} or {3}, but not both because 1+3=22. We also can not pick {2} because 2+2=22.


Theoretic Results

Simple 1 / 3 Lower Bound

Take all of the numbers x ≡ 1 mod 3 because 2 is quadratic nonresidue modulo 3.

This produces the following sequence: 1, 4, 7, 10, 13, 16, 19, 22, ...

Alternative 1 / 3 Lower Bound

Take all of the numbers x ≡ 3×4y-1 mod 4y for all y > 0.

This produces the following sequence: 3, 7, 11, 12, 15, 19, 23, 24, ...

Consider the following short proof that this sequence has no square sums:

Let 4a + 3×4a-1 and 4b + 3×4b-1 be two numbers with a ≥ b > 0.

Adding them together we get 4a + 4b + 3×(4a-1+4b-1).

We can divide through by 4b-1, which is a square, to get 4a-b+1 + 4 + 3×4a-b + 3.

When a = b we have 4 + 4 + 3 + 3 ≡ 2 mod 4.

When a > b we have 4(4a-b + 1 + 3×4a-b-1) + 3 ≡ 3 mod 4.

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

1 / 2 Upper Bound

Consider the square which is closest to n and partition the natural numbers at n / 2, so for all 0 < a < n / 2, we can either take (n / 2) - a or (n / 2) + a but never both.


Computational Results

I calculated the largest subsets and the number of unique largest subsets from [1,1] to [1,100].

All of the subsets are only slightly better than (or equal to) my best lower bound of 1 / 3.

[1,n]Largest Subset SizeNumber of Largest SubsetsLexically First Largest Subset (including n) of equal or greater size to the Largest 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

zachdestefano (at) gmail (dot) com