7
$\begingroup$

I thought of this problem as a simplification of the Euler-Brick problem .

$1)$For which $n$ is it possible to find $n$ distinct positive integers $a_1,a_2,\ldots,a_n$ such that all their pairwise sums , namely $a_i+a_j$ , are perfect squares .

For example when $n=3$ we can choose : $4$,$21$ and $60$ (with the sums $25$,$64$ and $81$ ) . Another example is $1$ , $24$ and $120$ .

If it's not possible for every $n$ then let $f(n)$ be the largest number of sums which can be perfect squares simultaneously. So $f(3)=3$ .

I can also achieve $f(4) \geq 4$ with $1,3,35,46$ .

My other question is :

$2)$ What bounds can we achieve for $f(n)$ ? (even for particular values is good ) . What I want is a better than 'linear' bound .

The motivation to ask this came from the Euler Brick problem which asks to find three positive integers $x,y,z$ such that $x^2+y^2$ , $y^2+z^2$ , $x^2+z^2$ are all perfect squares .

There are parametric solutions for this problem but for the $4$D brick problem not even a solution is known (see here https://en.wikipedia.org/wiki/Euler_brick)

This hard $4$D version made me ask this simplified version .

I am (almost) sure that I'm not the first considering this problem so there might be known results in the research literature , but I haven't found them yet.

Thanks for everyone who can help me with this problem . I appreciate all your efforts .

EDIT : I added the distinct condition , else the problem is easy . Here are the details :

Choose some $x=2a^2$ and then choose all the numbers to be $x$ . All the sums are now perfect squares so $f(n)=\binom{n}{2}$ for every $n$ .

$\endgroup$
  • 1
    $\begingroup$ It's easy to see that $f(nk) \geq n f(k)$ by choosing the numbers :$a_1,2^2a_1,\ldots,n^2 a_1,\ldots ,a_k,2^2a_k,\ldots,n^2a_k$ with whom we can form at least $nf(k)$ perfect squares . $\endgroup$ – user252450 Dec 15 '15 at 17:02
  • 3
    $\begingroup$ $(1058,6338,10823,13826)$ shows $f(4)=6$. $\endgroup$ – Zander Dec 16 '15 at 2:02
  • $\begingroup$ @Zander Wow this is incredible . Wish I could up-vote it twice . Thanks a lot . $\endgroup$ – user252450 Dec 16 '15 at 12:22
  • $\begingroup$ @ComplexPhi you may be excited to know that this related problem is still open: math.stackexchange.com/questions/962521/…. Or at least it was last year. $\endgroup$ – Colm Bhandal Dec 17 '15 at 11:50
  • $\begingroup$ @Zander Do you know of a quadruple like (1058,6338,10823,13826) but which has the sum of ALL four distinct positive integers become a perfect square as well? $\endgroup$ – Bob Kadylo Apr 25 '17 at 21:50
3
$\begingroup$

My Latest Answer

I have discovered a less trivial approximation for the growth rate of $f(n)$. But first I want to be rigorous about exactly what $f(n)$ is counting. I'm doing this in case I misinterpreted the question. My understanding is that $f(n)$ is the maximum number of distinct pairs $(i, j)$ with $1 \leq i < j \leq n$ such that there exists a set of $n$ positive integers $\{a_1, a_2, \dots, a_n\}$ with $a_i + a_j = s^2$ for some $s$. Clearly, $f(n) \leq {n \choose 2}$, since we can pick at most ${n \choose 2}$ pairs from $n$ objects.

Now, to find a lower bound for $f(n)$, we just need to find a set of pairs and a corresponding set of values, such that all values indexed by the pairs sum to perfect squares. Let's consider the set $\{1, 2, 3, \dots, n\}$ and define $h(n)$ as the number of distinct pairs of elements in this set that add to perfect squares. Clearly $h(n) \leq f(n)$. I will now put forth a very simple proof demonstration that:

$$n^{\frac32} \sim h(n)$$

Consider adding $n+1$ to the set $\{1, 2, 3, \dots, n\}$. We now form all the pairs $(1, n+1), (2, n+1), \dots, (n, n+1)$ whose corresponding sums are $n+2, n+3, \dots, 2n+1$. Now, let $s(a, b)$ denote the number of perfect squares in the interval $[a, b]$. Then we have:

$$h(n+1) = h(n) + s(n+2, 2n+1)$$

Now, how many perfect squares are in the interval $[n+2, 2n+1]$? Well, roughly there are:

$$\sqrt{2n+1} - \sqrt{n + 2} \approx \sqrt{2n} - \sqrt{n} = \sqrt{n}(\sqrt{2} - 1)$$

So, roughly speaking, we have:

$$h(n+1) \approx h(n) + \sqrt{n}(\sqrt{2} - 1)$$

Expanding out the recursion and factoring out the $(\sqrt{2} - 1)$ then we get:

$$h(n) \sim \sqrt{1} + \sqrt{2} + \dots + \sqrt{n} \sim \int_1^n \sqrt{x}\,dx \sim n^{\frac32}$$

My maths here is not up to my usual standard of rigour, but I think it's sound. This would imply that the growth rate of $f(n)$ is somewhere between $n^{\frac32}$ and $n^2$.


Update: We can arrive at a lower bound for $h(n)$ in a different way, avoiding the use of integration. Consider the set $\{1, 2, 3, \dots, n\}$. There are $\lfloor\sqrt{n}\rfloor$ perfect squares in this set. For each perfect square $k^2$, we can form it with $\lfloor\dfrac{k^2 - 1}{2}\rfloor \geq \dfrac{k^2}{2} - 1$ unique pairs:

$$(1, k^2 - 1), (2, k^2 - 2), \dots, (\lfloor\dfrac{k^2 - 1}{2}\rfloor, \lceil\dfrac{k^2 + 1}{2}\rceil)$$

These aren't all the squares that can be formed, but they are all possible, so they are valid for a lower-bound argument. Let $R=\lfloor\sqrt{n}\rfloor$ for ease of notation. A lower bound is then:

$$\sum_{i=1}^{R}\left(\dfrac{i^2}{2} - 1\right) = \frac12\sum_{i=1}^{R}i^2 - R = \dfrac{R(R+1)(2R+1)}{12} - R$$

Clearly this is of the order $n^{\frac32}$.

My Boring Original Answer

I will give a very trivial answer to $(2)$. We have the bound:

$$n - 1 \leq f(n)$$

To see why, choose $a_1 = 1$ and for all $i \neq 1$ choose $a_i = i^2 - 1$. Then we have that for all $i \neq 1$, $a_i + a_1 = i^2$. Since there are $n - 1$ values of $i \neq 1 \leq n$, we obtain the lower bound.


Update: Paying tribute to the commenter Crostul and the OP ComplexPhi, who have done more work than I, we can improve this lower bound to:

$$f(n) \geq f(k) + n - k$$

for any $k \leq n$.

Noting the discovery of the commenter Zander above, we have that $f(4) = 6$, and so we have the following bound:

$$f(n) \geq n + 2 \;\;\; \mathrm{where} \;\;\; (n \geq 4)$$

$\endgroup$
  • 2
    $\begingroup$ This trivial bound can be slightly improved to $n \le f(n)$ since $f(3)=3$. So, for example, you can take $4, 21 , 60 , a_4 , \dots , a_n$ where $a_i+60$ is a square. $\endgroup$ – Crostul Dec 15 '15 at 16:34
  • 1
    $\begingroup$ Using Crostul's idea we can get $$f(n) \geq f(k)+n-k$$ $\endgroup$ – user252450 Dec 15 '15 at 16:45
  • $\begingroup$ Nice work people. I think the next step now is to figure out the growth rate of $f(n)$. Obviously it's somewhere between $n$ and $n^2$. I wonder if it's something like $n^{\frac32}$ or $n\log(n)$. That would be interesting. $\endgroup$ – Colm Bhandal Dec 16 '15 at 16:54
  • $\begingroup$ @ColmBhandal Wow, never thought that from the simplest possible set : $1,2,3,\ldots ,n$ we can get so many perfect squares . Thanks a lot .Also , your understanding of the problem formulation is the right one . Some questions : 1) Do you think there are other specific sets which can achieve a better lower bound , or this is the best we can get with this type of approach ? 2)Do you think that in general f(n) \geq cn^2 or that $f(n)=o(n^2)$ ? . $\endgroup$ – user252450 Dec 17 '15 at 13:42
  • $\begingroup$ @ComplexPhi these are exciting questions that I have been asking myself. The honest answer is: I don't know. But my intuition tells me that there's a more complicated proof that any set you choose is bounded by $cn^{\frac32}$. I certainly doubt the growth rate is $n^2$, but I will stand corrected if some genius proves me wrong. $\endgroup$ – Colm Bhandal Dec 17 '15 at 15:41

Your Answer

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