- Sep 8, 2008Hello,

Perhaps you may be interested to check out the conjecture, which I

have made lately (and info on possible directions in proving it - see

below) ?

NO "n" exist, such that

( n! + prime(n) )

yields integral m^k

where k>1

i.e.

n! + prime(n) != m^k

Kurt Foster responded to my post with the partial proof for k=2

see NMBRTHRY Archives – September 2008

Prior to Kurt Foster's solution, David Harden together with Daniel

Berend responded to my post (on the SeqFan mail list) with the similar

proof for the case of squares - see at the very bottom of the attached

below email chain.

Thanks,

Best Regards,

Alexander R. Povolotsky

---------- Forwarded message ----------

From: Alexander Povolotsky <apovolot@...>

Date: Aug 28, 2008 8:14 PM

Subject: remark from Noam Elkies

To: Florian Luca <fluca@...>

Dear Florian,

Regarding C and c, which both were cited by you, and towards refining

ABC ability to quantify upper n limit, Noam Elkies made the following

remark:

" If one could show that c>0 is such, that the radical is always at

least c*C^(4/5), then I can give you an upper bound on n, such

that n! + prime(n) is a perfect power, and then what remains - it's

just a finite computation to show/verify that none of those remaining

candidates {n*} satisfy p_n* +n*! = m^k "

So (if I understood correctly what Noam Elkies meant in his remark as

"radical" ) then my question to you would be - is proving that

Rad(n!*p_n*m) >= c*C^(4/5)

possible ?

Thanks,

Regards,

Alexander R. Povolotsky

=================================================On Thu, Aug 28, 2008 at 9:45 AM, Florian Luca <fluca@...> wrote:

> Dear Alex

>

> Thanks for the conjecture. Igor mentioned linear forms in logarithms. Here is

> how they work in your case:

>

> Write

>

> n!=m^k-p_n

>

> m and p_n are odd. The exponent of 2 in n! is roughly about n (it is \ge

> n-(log(n+1))/log 2).

>

> Linear forms in logarithms tell you

> that the exponent of 2 on the right is at most

>

> C*log m *log p_n * log k.

>

> Here C is a constant. Since log p_n is roughly log n

> and log k cannot exceed log n either (because m>n),

> you get that the above bound is << log m (log> n)^2.

> So,

> log m>> n/(log n)^2, which in turn puts k<<(log n)^2.

>

> So, you know now that k is not too large. You have an argument for 2 which

> is very nice. Would it work for 3:

>

> p_n is a cubic residue modulo all primes q=1 mod 3 <n.

> Is this enough to get a contradiction? Probably.

> Then you can do it for 5, 7, up to all primes up to O((log n)^2).

> Heuristically it should work at least under GRH and so on. Namely, given

> a prime p, the probability that a number which is not a pth power

> looks like a pth power modulo q, a prime which is 1 mod p, is 1/p.

> Assuming some independence over q, you multiply these probabilities up

> to x, to get > (1/p)^{pi(x,p,1)}.

>

> If p=O((log x)^2)), then the above amount is the reciprocal of

>

> p^{pi(x,p,1)} which is about exp(x log p/p(log x)). Since p is a power of

> logarithm of x, this number is huge (it is at least exp(c x/(log x)^3) with

> some constant c.

> So, you expect that there should be no p_n such that

> p_n = m^p mod q for all primes q=1 mod p not exceeding n,

> and all primes p=O((log > n)^2) for large n.

> The preprint that Igor sent could help to prove this under GRH.

>

> Conditionally, it also follows immediately from ABC that there are no

> solutions for large n, and the argument that I made above can be

> immediately modified to prove that the set of n such that n!+p_n

> is a perfect power is of asymptotic density zero. I am not sure if the full

> thing can be finished off unconditionally by these arguments only. But

> maybe there is something that escapes me.

>

> Cheers,

> Florian

> ---------- Original Message -----------

> From: "Alexander Povolotsky" <apovolot@...>

> To: fluca@...

> Sent: Thu, 28 Aug 2008 05:00:47 -0400

> Subject: conjecture: n! + prime(n) != m^k

>

>> Dear Florian - Igor Shparlinski kindly recommended me to ask your

>> advise/opinion re proving of my conjecture.

>>

>> Thanks,

>> Regards,

>> Alexander R. Povolotsky

>> ---------- Forwarded message ----------

>> From: Igor Shparlinski <igor@...>

>> Date: Wed, Aug 27, 2008 at 10:10 PM

>> Subject: Re: n! + prime(n) != m^k

>> To: Alexander Povolotsky <apovolot@...>

>>

>> Hi,

>>

>> I don't see why the case k = 2 is any special?

>> In fact the proof uses an variant of argument, which

>> has been used in studying so-called x-pseudosquares:

>> the claim is the p(n)-is an n-pseudosquare which is

>> impossible, by say Polya-Vinogradov. I'm attaching a

>> paper where you can find further references

>>

>> Why can't you extend the proof to any k

>> (which is not too large).

>> On the other hand, when k is large

>> then form in logarithms may already give you something.

>> Actually they may already give everything you

>> need starting with k = 2.

>> I would suggest that you forward this question to

>> Florian Luca who would be the best person to ask.

>> Florian's email address is fluca@....

>>

>> Best wishes,

>> Igor

>> At 8:53 PM -0400 27/8/08, Alexander Povolotsky wrote:

>> >

>> > Hello Dear Igor,

>> >

>> > Perhaps you may be interested to check out the conjecture,

>> > which I have made lately ?

>> >

>> > NO "n" exist, such that

>> > ( n! + prime(n) )

>> > yields integral m^k

>> > where k>1 ?

>> > The formal proof (from David Harden with further proof improvement

>> > from Daniel Berend) so far only provided (in reply

>> > to my posting) for k=2 (see below).

>> Regards,

>> Alexander R. Povolotsky

>> =========================================================

>> David Harden wrote:

>>

>> It is trivial to check this for n<=3.

>> So we may assume that n >= 4, which means n! is a multiple of 8 and

>> that p_n is odd.

>> Then n! + p_n = x^2

>> means p_n == x^2 (mod 8).

>> Since p_n is odd, x^2 is odd and, therefore, x^2 == 1 (mod 8) so p_n

>> == 1 (mod 8).

>>

>> Let q be an odd prime with q <= n.

>> (Note that q < p_n.)

>> Then p_n == x^2 (mod q) so (using Legendre symbol notation)(p_n/q) =

>> 1. Since p_n == 1 (mod 4), quadratic reciprocity tells us that

>> (q/p_n) = 1. Also, (2/p_n) = 1 because p_n == 1 (mod 8). This means

>> that the smallest prime quadratic nonresidue (equivalently, the

>> smallest positive quadratic nonresidue) modulo p_n is > n ~

>> p_n/(log(p_n) - 1). This is very large; known effective bounds on

>> the smallest quadratic nonresidue modulo a prime fall well under

>> this. You have probably searched up to n large enough for these

>> bounds to apply and conclude the proof.

>>

>> ---- David

>> ********************************************************************************

>> >From : berend daniel <berend@...>

>> To : David Harden <oddleehr@...>, pevnev@..., Alexander

>> Povolotsky <apovolot@...>

>> Subject : Re:

>> Does any "n" exist, such that ( n! + prime(n) ) yields integral

>> square ? Date : Mon, Aug 11, 2008 03:21 AM

>>

>> You don't need the bounds on quadratic non-residues.

>> Once you you know that all primes up to n are quadratic residues,

>> so are all numbers up to p_n, all of whose prime divisors do not

>> exceed n. This mean that most integers up to p_n are quadratic residues.

>> But only half of them are. ... Contradiction.

>>

>> Best,

>> Dani

>> ---------- Forwarded message ----------

>> From: berend daniel <berend@...>

>> Date: Aug 12, 2008 5:28 AM

>> Subject: Re: Does then NO "n" exist, such that ( n! + prime(n) )

>> yields integral m^k where k>1 ?

>>

>> --------- Forwarded message ----------

>> From: berend daniel <berend@...>

>> Date: Aug 12, 2008 5:28 AM

>> Subject: Re: Does then NO "n" exist, such that ( n! + prime(n) )

>> yields integral m^k where k>1 ?

>> To: Alexander Povolotsky <apovolot@...>

>> Cc: David Harden <oddleehr@...>

>>

>> Alexander Povolotsky wrote:

>> > Does then NO "n" exist, such that

>> > ( n! + prime(n) )

>> > yields integral m^k

>> > where k>1 ?

>> >

>> > Thanks,

>> > Regards,

>> > Alexander R. Povolotsky

>>

>> I certainly believe that's the case, but this doesn't seem to follow

>> from the same considerations, as the function x\to x^k is sometimes

>> onto.

>>

>> Best,

>> Dani