Re: x^n + y^n (mod p)

In article <4fqnh3ldjpn6c5tnejt196p0q31rp9neni@xxxxxxx>,
quasi <quasi@xxxxxxxx> wrote:

On Sun, 21 Oct 2007 23:02:57 GMT, Gerry Myerson
<gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

In article <67glh3h7h39d6kd8e2svlh23ki3h3boukm@xxxxxxx>,
quasi <quasi@xxxxxxxx> wrote [with a minor correction]:

Given a positive integer n, and a prime p, define a map

f : Z_p x Z_p --> Z_p

by

f(x,y) = x^n + y^n

Two conjectures ...

Conjecture (1):

For each positive integer n>2, there is at least one prime p such that
f is not surjective.

Let p be a prime congruent to 1 (mod n), say, p = d n + 1.
Then there are only d (non-zero) n-th powers (mod p),

Yes. Assume p = d n + 1. Letting r be a primitive root (mod p), the
nonzero n'th powers (mod p) are r^n, r^(2n), r^(3n), ..., r^(d*n).

so only about d^2 values of f.

Right. In any case, at most d^2 + d + 1.

Now it's surely true (though maybe not yet proved) that d can be
taken smaller than n, so d^2 < p,

In other words, the smallest prime p in the arithmetic progression

n + 1, 2*n + 1, 3*n + 1, ...

has the form p = d n + 1 where d^2 + d + 1 < n.

Hmmm ...

For a given n, I guess that's likely on probabilistic grounds, by
virtue of the density of primes, and the lack of favoritism (mod n)
(as long as the residue (mod n) is relatively prime to n).

But is that probabilistic argument strong enough to suggest that it
should be true for all n?

Let me try ...

Assuming no bias for or against primes in the sequence

n + 1, 2 n + 1, 3 n + 1, ..., a n + 1

where a is the greatest integer such that a^2 + a + 1 < n, the
probability that at least one of them is prime should on the order of

1 - (1 - (1/ln(n)))^(sqrt(n))

Assuming independence as n varies, the (heuristic) probability that
conjecture (1) is false is the infinite product

Prod ( (1 - (1/ln(n)))^(sqrt(n)) )

for n from 3 to infinity.

So we would like to show the above product converges to 0.

But, for large n, each term of the product has order

(1/e)^(sqrt(n)/ln(n))

which is less than 1/e (and in fact, approaches 0),

hence the infinite product is 0.

Thus, based on the above probabilistic considerations, it's likely
that conjecture (1) is true.

I'm not so good on this analytic/probability oriented reasoning, so if
the above heuristic argument is not correct, please advise.

so f is not surjective.

Very nice.

Conjecture (2):

For each positive integer n, and all sufficiently large primes p
(depending on n), f is surjective.

This is true, and follows from Weil's bounds on exponential
sums. I think it's known to be true for p > N_0(n), where
N_0(n) is something like n^4. I'll see if I can chase up some
references. I vaguely recall there was a paper by Chowla.

Thanks.

But I'm a little surprised that two innocent congruence related
questions on my part (conjectures (1) and (2)) end up as apparently
difficult results. I thought they would both be more elementary.

Well, Fermat's Last Theorem must have looked pretty innocent
once upon a time. Goldbach's conjecture, twin primes, etc., etc. -
number theory is full of innocent-looking problems that turn out
to be fiendishly difficult.

To summarize ...

Conjecture (1) appears true on probabilistic grounds, but it may be
the case that no proof is presently achievable (with today's math).

Of course, they may be a simpler way of doing things than what
I outlined. Also, there are some bounds around on the smallest
prime in an arithmetic progression, I just don't know them well
enough to know if they're strong enough to answer the question.
Then again, even the existence of primes in arithmetic progressions
(another innocent-looking problem) turns out to be not so elementary.

Conjecture (2) is true using some (possibly advanced) asymptotic
results in analytic number theory.

I still haven't found the references I'm looking for, but I'm leaning
toward the opinion that nothing half as scary as Weil's work is
needed. I think an answer can be put together from stuff in Ireland
and Rosen's textbook, which is what you might call "advanced
elementary." In particular, they study x^n + y^n = 1 (mod p)
using Jacobi sums. Check it out!

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.

Relevant Pages

  • Re: Evidence for Big Leaps?
    ... single nucleotide mutation can be expressed, ... probability calculation leads to an erroneous conclusion. ... RM conjecture, an additional constraint on the final ... substratum) of the IA algorithms. ...
    (talk.origins)
  • Re: Computability
    ... I am sorry if my difficulties with exposition led you to believe ... And the conjecture _is_ interesting. ... probability and that that order will be the order of exposition next ... client cognitions in a pattern of correalations like "when client ...
    (sci.math)
  • Re: Am I a crank?
    ... Goldbach Conjecture and was thinking of programming it up to see if I ... could find any patterns. ... probabilistic reasons. ... that the conjecture is true with a probability of about 1-10^. ...
    (sci.math)
  • Re: x^n + y^n (mod p)
    ... the probability that ... conjecture is false is the infinite product ... hence the infinite product is 0. ... For each positive integer n, and all sufficiently large primes p ...
    (sci.math)