A Sierpinski-style conjecture for X^Y+Y^X?

[Batalov]

Is there a Sierpinski-style conjecture for X^Y+Y^X?
I.e. "there exist (infinitely many?) such X>4 that X^Y+Y^X is composite for all Y>1".

Y=1 needs to be excluded for apparent reasons (trivial solutions 1^P-1+(P-1)¹).

It is easy to see that for X+1 prime, Y must be divisible by X+1. Because of that some X values are very thin, and get sieved out from small areas completely (e.g. X=1012 or X=1600).

X=4 is (another trivial) solution, because:
- for Y even, X^Y+Y^X is even
- for Y odd, and has an Aurifeuillian factorization.
But this is not a very satisfying solution.

What about X>4?

[Batalov]

P.S. All odd powers of 4 admit the same factorization, but this is also trivial.
Interesting would non-trivial solutions be. :yoda:

[XYYXF]

On the Aurifeuillian factorizations: https://groups.yahoo.com/neo/groups/...messages/16204

On the "density" of the primes: https://groups.yahoo.com/neo/groups/...messages/21531

[henryzz]

It does seem that some values of X don't seem to have any easily found primes.
X=6, 10, 13, 16 and 17 for example have no primes upto at least Y=500k excluding Y=1.
It might be a nice idea to try and find some primes for these values of X.
I suspect that it is likely just that they are so low weight rather than there being a full covering set for most of these. I can't see a reason why that would be impossible though similar to the conjectures covered by CRUS.

[XYYXF]

Originally Posted by XYYXF

On the "density" of the primes: https://groups.yahoo.com/neo/groups/...messages/21531

Let me copy that here.

Define w(p, y) for integer y > 0 and prime p this way (there d = gcd(y, p-1), f = (p-1)/d):

if p|y then w(p, y) = 1 else
if (-y)^f = 1 (mod p) then w(p, y) = d else w(p, y) = 0

Note that w(p, y) is periodic with period p*(p-1):
w(p, y) = w(p, y mod (p^2-p))

It's also clear from the definition (and from the sum over orders modulo p) that
sum[w(p, y), {y from 1 to p^2-p}] = p^2-p[*]

There are values of w(p,y) for p = 2, 3, 5, 7, where y runs from 0 to p^2-p-1:
(1 1)
(1 1 2 1 0 1)
(1 1 0 1 4 1 2 1 0 1 1 1 0 1 2 1 0 1 0 1)
(1 1 0 0 0 1 6 1 0 0 2 1 0 1 1 3 0 1 0 1 2 1 0 1 0 1 2 3 1 1 0 1 0 0 2 1 0 1 2 0 2 1)

Let's also define w'(p, y) in the same way as w(p, y), but use y^f instead of (-y)^f, so we'll obtain
w'(p, y mod (p^2-p)) = w(p, (-y) mod (p^2-p))

Conjecture A:
If, for a given y, we sieve out all x^y+y^x divisible by q|(p-1) for all such q's, then exactly w(p, y)/p of remaining numbers will be divisible by p.

Conjecture A':
If, for a given y, we sieve out all x^y-y^x divisible by q|(p-1) for all such q's , then exactly w'(p, y)/p of remaining numbers will be divisible by p.

Conjectures are equal each to other, so let's prove the latter.

1° It's clear that w'(p, y) = 1 when p | y.

2° It's also easy to show that w'(p, y) = 1 when p does not divide y and gcd(y, p-1) = 1. Indeed, there's only one solution of x^y = y^n (mod p) for every integer n from 1 to p-1, so we'll sieve out exactly 1/p of candidates with (x mod (p-1)) = n for every n where such candidates exist, yielding in 1/p of total.

3° Now let p does not divide y, and gcd(y, p-1) = d > 1. Let g is the order of y (mod p). We need to prove that

if g divides (p-1)/d, then w'(p, y) = d.

Once it's proven, we don't need to prove that in other cases w'(p, y) = 0, because of[*] and the fact that exactly 1/p of the numbers x^y-y^x, which are co-prime to p-1, are divisible by p. Indeed, if there were more than 1/p, the same situation would appear for x^y+y^x, giving too many y^x divisible by p.

Now let's show that (under conditions 3°) if w'(p, y) > 0, then w'(p, y) = d. The way is similar to 2°: if there are solutions of x^y = a (mod p) for some a <> 0 (mod p), then there are exactly d such solutions.

So, after all, the only thing to prove is Lemma 1:

if p does not divide y, gcd(y, p-1) = d > 1, g is the order of y (mod p) and g divides (p-1)/d, then w'(p, y) > 0.

It looked for me somewhat obvious in 2003, but now I come closer and feel myself having no idea how to prove it. :(

Maybe you have some?

* * * * * * *

The products

Weight(y) = Product[(p-w(p, y))/(p-1), {p is prime}],
Weight'(y) = Product[(p-w'(p, y))/(p-1), {p is prime}]

give us estimates of the "density" of primes of the form x^y+y^x or x^y-y^x respectively, where y is frozen, as well as Yves Gallot's estimators for Generalized Fermats: http://perso.wanadoo.fr/yves.gallot/papers/ccdgfpn.html

Note that, in practice, we need quite large ranges of x's to make these estimators working.