Loading ...
Sorry, an error occurred while loading the content.

The density of the primes among x^y+y^x or x^y-y^x

Expand Messages
  • Andrey Kulsha
    Hello group, just digged up some of my thoughts on the subject: http://tech.groups.yahoo.com/group/primenumbers/message/15715
    Message 1 of 1 , Jun 10, 2010
    • 0 Attachment
      Hello group,

      just digged up some of my thoughts on the subject:

      http://tech.groups.yahoo.com/group/primenumbers/message/15715
      http://tech.groups.yahoo.com/group/primenumbers/message/15721

      They are somehow summarized in this bugfixed copy of my old message to Decio Luiz Gazzoni Filho:

      * * * * * * *

      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.

      With best regards,

      Andrey Kulsha

      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.