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

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.

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).

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

Is the above a reasonable "bottom-line" summary?

quasi
.

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: Conjecture regarding Hamming correlation of linearly independent binary vectors
    ... Even then the conjecture cannot be true; ... given any positive integer k, ... the probability that any two rows have ... the matrix is invertible approaches the positive constant ...
    (sci.math.research)
  • Re: x^n + y^n (mod p)
    ... the probability that ... conjecture is false is the infinite product ... hence the infinite product is 0. ... number theory is full of innocent-looking problems that turn out ...
    (sci.math)