Is there an elementary description of $$N(a)=\Big|\Big\{x\in\{0,1,\dots,\Big\lfloor\frac a2\Big\rfloor-1,\Big\lfloor\frac a2\Big\rfloor\Big\}:\sqrt{x(a-x)}\in\Bbb Z\}\Big|$$ and though likely non-monotone how does it grow (heuristically $N(a)=O(\log a)$)?

This was my heuristic. Number of pairs in $[1,a]$ with product as perfect squares is $O(a\log a)$ while number of pairs in $[1,a]$ with sum $a$ is $O(a)$ and so expected intersection should be $O(\log a)$.

  • $\begingroup$ If you define $N'(a) = |\{x\in \{1,\dots,a-1\} : \sqrt{x(a-x)}\in \mathbb{Z}\}|$, then the sequence $N'(1),\dots,N'(50)$ agrees with the first $50$ terms of A092147 in the OEIS: "Number of even-length palindromes among the $k$-tuples of partial quotients of the continued fraction expansions of $n/r$, $r=1,\dots,n$." And it's easy to see that the function $N'$ is related to your function $N$ by $N(a) = \lfloor \frac{N'(a)}{2} \rfloor + 1$. $\endgroup$ Dec 27 '17 at 19:45
  • $\begingroup$ @AlexKruckman Interesting that it is related to palindromes. why? $\endgroup$
    – Mr.
    Dec 28 '17 at 7:29
  • 1
    $\begingroup$ I don't know. It would be very interesting to see a proof that these two sequences are equal. $\endgroup$ Dec 28 '17 at 14:01

As hinted in Alex Kruckman's comment, it is easier to work with $$N'(a) = \left|\{x\in \{1,\dots,a-1\} : \sqrt{x(a-x)}\in \mathbb{Z}\}\right|,$$ which is the same as $N(a)$ up to a factor of $2$. It is straightforward to see that $N'(a)$ equals the number of representations $$a=d(y^2+z^2),\qquad \gcd(y,z)=1,$$ the connection being $d=\gcd(x,a-x)$, $x=dy^2$, $a-x=dz^2$, $\sqrt{x(a-x)}=dyz$.

The number of ways a number $n$ can be written as a sum of two coprime squares is a multiplicative function $r(n)$ given by $r(2)=1$, $r(p^k)=2$ when $p\equiv 1\pmod{4}$, and $r(p^k)=0$ for all other prime powers $p^k$. So $r(n)$ is quite similar to the divisor function $\tau(n)=\sum_{n=de}1$, and $N'(n)$ is quite similar to the generalized divisor function $\tau_3(n)=\sum_{n=def}1$. In particular, the maximal order of $N'(n)$ is much larger than $\log n$, namely $\exp((c+o(1))\log n/\log\log n)$ for some constant $c>0$ (the peak values occur for $n$'s which are products of distinct primes congruent to $1$ modulo $4$). I am pretty sure the constant equals $c=\log 3$ as in the case of $\tau_3(n)$, but I have not verified this formally.

  • $\begingroup$ I was going by this. Number of pairs in $[1,n]$ with product as perfect squares is $O(n\log n)$ and number of pairs in $[1,n]$ with sum $n$ is $O(n)$. So expected intersection should be $O(\log n)$. Why does this heuristic fail? $\endgroup$
    – Mr.
    Dec 28 '17 at 7:27
  • $\begingroup$ @777: Your heuristic fails, because it is not a proof. The statements that I wrote have proofs, so try to understand those instead. In particular, if $n$ is the product of the first $k$ primes congruent to $1$ mod $4$, then the number of representations $n=y^2+z^2$ is $2^k$, which grows much faster than any power of $\log n$, since $k$ is on the scale of $\log n/\log\log n$ instead of $\log\log n$. On the other hand, each representation $n=y^2+z^2$ yields an appropriate $x$, namely $x=y^2$ and $a-x=z^2$ whose product is the square $(yz)^2$. $\endgroup$
    – GH from MO
    Dec 28 '17 at 9:05
  • $\begingroup$ —and indeed we are counting factorizations $a=def$, but with $e=y+iz$ and $f=y-iz$ instead of usual integer factorizations. $\endgroup$ Dec 28 '17 at 16:34

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.