33
$\begingroup$

I asked this question on the NMBRTHRY mailing list on 17 February 2014, but it remains unsolved as far as I know.

Recall that a "powerful number" is a positive integer whose prime factorizations $m = \prod_i p_i^{e_i}$ has each exponent $e_i \geq 2$. (Equivalently $-$ though generally of little use $-$ a positive integer is powerful if and only if it can be written as $m^2 n^3$ for some integers $m,n$.) Pondering this Mathoverflow question led me to ask:

What's the smallest powerful number that can be written as $x^4+y^4$ with $\gcd(x,y) = 1$?

In particular, is it $3088257489493360278725196965477359217 = 427511122^4 + 1322049209^4$?

The gcd condition is needed for the usual reason: if $x^4+y^4$ is powerful then so is $(cx)^4+(cy)^4$, but the converse fails, and indeed any number $m$ can be made powerful by multiplying it by some $c^4$ (say $c=m$ itself); we are not interested in examples such as $17^4 + 34^4 = 17^5$.

There are only about twice as many powerful numbers $m \leq x$ as there are squares [the actual ratio is $A = \zeta(\frac32)/\zeta(3) = 2.17325+$, and if I did this right then the count is given more precisely by $A x^{1/2} - B x^{1/3} + o(x^{1/6})$, where $B = -\zeta(\frac23)/\zeta(2) = 1.48795+$, and the $o(x^{1/6})$ is actually $o(x^{1/12+\epsilon})$ under the Riemann Hypothesis; but this is all tangential to the question at hand].

Thus, as with squares, we expect only finitely many examples of coprime $x,y$ for which $x^5+y^5$ is powerful, but do expect $x^4+y^4$ to be powerful for for an infinite though sparse set of coprime pairs $(x,y)$. True, Fermat showed that there are no solutions of $x^4 + y^4 = z^2$; but there are integers $m$ for which the elliptic curve $x^4 + y^4 = mz^2$ does have infinitely many rational points, and indeed we can use such curves to find powerful $x^4 + y^4$: compute solutions of $x^4 + y^4 = mz^2$ until finding one for which $z$ is divisible by each prime factor of $m$. For example, taking $m=17$ eventually yields $$ 427511122^4 + 1322049209^4 = 17 \cdot 426218494746902449^2 = 17^3 \, 73993169^2 \, 338837713^2. $$ This is the smallest example I found, but this method needn't find solutions of "$x^4 + y^4 = $ powerful" in order of increasing size, and I don't see how to organize an exhaustive search that could provably find the smallest example if it is not much smaller than the solution above (for which $x^4 + y^4 \doteq 3 \cdot 10^{36}$). For what it's worth, Google does not recognize it.

By the way, it's much easier to search for powerful values of $x^4 - y^4$ (again with $\gcd(x,y)=1$), because $x^4-y^4$ factors, and each of the factors $x+y$, $x-y$ must be powerful except possibly for a stray power of $2$. This means that trying all $(x,y)$ with $x+y \leq H$ takes time proportional to $H$. For instance, it took just over 6 hours of gp computation to find that $$ 10113607^4 - 4319999^4 = 6 \cdot 41056761311940^2 = 2^5 \, 3^3 \, 5^2 \, 11^2 \, 23^2 \, 37^2 \, 47^2 \, 313^2 \, 4969^2 $$ is the only example with $x+y \leq 10^8$, even though $x^4 - y^4$ is still quite large (just over $10^{28}$). This example is known to Google, but only as a solution of $x^4-y^4=6z^2$, with nothing about $6z^2$ being powerful, let alone about its being the first such example.

$\endgroup$
  • 1
    $\begingroup$ Google still doesn't recognize your first solution, though it has indexed your question according to search for the title. $\endgroup$ – joro Jan 2 '15 at 12:28
  • $\begingroup$ Is it known that working with powerful $m$ doesn't help? (you need not care about $z$ in this case). $\endgroup$ – joro Jan 2 '15 at 13:36
  • $\begingroup$ You mean, try all powerful $m$ up to about $3 \cdot 10^{36}$? Unfortunately there's too many of them (must be at least $10^{16}$ even when we require that each prime factor be $1 \bmod 8$). $\endgroup$ – Noam D. Elkies Jan 2 '15 at 15:39
  • 3
    $\begingroup$ Um, the curves with $m=17$, $17^3$, $17^5$ are isomorphic (just write $z=17z_1$ or $17^2 z_2$ in $x^2+1=17z^2$), and thus give rise to exactly the same candidates... $\endgroup$ – Noam D. Elkies Jan 2 '15 at 17:54
  • 1
    $\begingroup$ Yes I checked, but not that way: you don't want to wait for gp to count to $10^{16}$, let alone factor every number of at most $16$ digits! Much better to try all coprime $(x,y)$ of opposite parity with $x<y$ and $x^4 + y^4 < 10^{16}$; that's only 40 million or so factorizations, which take a few hours to try (and as expected find nothing). Still it's hopeless to reach $3 \cdot 10^{36}$ this way... Now that it's a couple of months since I posted this question, I should post a partial answer evaluating different strategies, the best of which might make the computation barely feasible. $\endgroup$ – Noam D. Elkies Mar 11 '15 at 23:45
1
$\begingroup$

If coprime integers $x, y$ satisfy $x^4 + y^4 = A C^2$ with $C = A B$ then no prime 3 mod 4 divides the LHS, and that implies $A = a^2 + b^2$ and $B = c^2 + d^2$.

Also, if $x, y$ are coprime then $x^4 + y^4$ is odd or twice odd, so that $A$ and $B$ are also odd, and thus $x^4 + y^4$ is odd.

Furthermore, we can assume that $A$ is squarefree because any squared factor can be absorbed in $C^2$ and then in $B$, and $A$ being squarefree implies that $(a, b) = 1$.

One's first thought is simply to assume that $x^2 + i y^2 = (a + i b)^3 (c + i d)^2$ and search for integer solutions $x, y$ by looping through ranges of $a, b, c, d$.

Another possible search strategy is to consider the equation in the form

$x^4 + y^4 = (a (a^2 + b^2) B)^2 + (b (a^2 + b^2) B)^2$.

Given that $x, y$ are coprime, there must be integers $p, q, r, s$ with $(p, s) = (q, r) = 1$ and pairs $p, s$, $q, r$ of opposite parity, such that:

$x^2, y^2, a(a^2 + b^2) B, b(a^2 + b^2)B = p q - r s, p r + q s, p q + r s, p r - q s$

So one could search over sets of $p, q, r, s$ where for each set the procedure would be as follows:

  1. Determine $P, Q = p q + r s, p r - q s$ and $R, S = p q - r s, p r + q s$
  2. Perform the following in parallel, and abort step in the event any test applies:
    • Denoting $T = (P, Q)$ if $(P/T)^2 + (Q/T)^2$ does not divide $T$
    • For small(ish) primes, e.g. $2, 3, 5$, if $2^{2\alpha+1}$ || R or S etc
    • odd part of |R| or |S| not = 1 mod 8, non-3-divisible part of |R| or |S| not = 1 mod 3, etc, i.e. quadratic residue checks
    • |R| or |S| not a perfect square
  3. Log solution we have found!
$\endgroup$
  • $\begingroup$ In fact if $\gcd(x,y) = 1$ then every odd prime factor of $x^4 + y^4$ is congruent to $1 \bmod 8$, not just $1 \bmod 4$ (and if $x^4+y^4$ is powerful then it must be odd). That does cut down the search space a bit $-$ a number of bits, even $-$ but still not nearly enough to make it feasible to provably find all examples with $x^4 + y^4 < 3 \cdot 10^{36}$. It is, however, one ingredient of the closest thing I have to a feasible strategy, which I may post as a partial answer to my own question if nothing better appears here soon. $\endgroup$ – Noam D. Elkies Jan 10 '15 at 3:53
  • $\begingroup$ I beefed up my suggested method with a few (obvious) extra checks, and this involves calculations of only GCDs, quotients, and square roots (not prime factorisations for example). But, as you say, the search space is very large. So probably a more sophisticated approach is required. $\endgroup$ – John R Ramsden Jan 10 '15 at 18:08

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.