[seqfan] Re: min(d(p^n-1)) for sufficiently large p

hv at crypt.org hv at crypt.org
Thu May 27 20:38:43 CEST 2010

[Rearranged to un-top-post.]

Max Alekseyev <maxale at gmail.com> wrote:
:On Thu, May 27, 2010 at 7:51 AM,  <hv at crypt.org> wrote:
:> %I A000001
:> %S A000001 4,32,8,160,8,384,8,384,16,256,8,7680,8,128,32,1792,8,4096,8,3840,32,
:> %T A000001 256,8,36864,16,128,32,2560,8,24576,8,4096,32,128,32,327680,8,128,32,
:> %U A000001 36864,8,18432,8,2560,128,256,8,344064,16,1024,32,2560,8,20480,32,
:> %N A000001 p^n-1 has at least a(n) divisors for all sufficiently large primes p
:> %F A000001 a(n) = d(A079612(n)) . 2^d(n) (where d(n)=A000005(n))
:> %e A000001 From A079612() we know that 24 must divide p^2-1 for all primes p except 2 and 3. With a finite number of small exceptions, the factors p-1 and p+1 must contribute either an additional distinct prime factor or enough small repeated factors to ensure that d(p^2-1) >= d(24qr) with q, r distinct primes > 3, so a(2) = d(24qr) = 32.
:> %Y A000001 Cf. A000005, A079612.
:> %K A000001 new,nonn
:> %O A000001 1,1
:> %A A000001 hv at crypt.org (Hugo van der Sanden)
:> Is it reasonable to name this sequence in this way? I do not mean to imply,
:> for example, that stating a(1)=4 means I have a proof of the infinitude of
:> Sophie Germain primes, only that d(p-1) is known to be >=4 by well-known
:> algebraic and modular considerations.
:> If it is not reasonable, maybe the name should be changed to correspond to
:> the formula and the old name moved to a comment. However that feels like
:> it would be a less satisfactory (and much less useful) name.
:> I welcome any other suggestions for improving this sequence.

:I think the current definition is imprecise in two ways: first, it
:sounds like the bound a(n) for d(p^n - 1) may depend on how large the
:prime p is;

I'm not sure how to express it better than the phrase from the example:
"with a finite number of small exceptions". It might be possible to come
up with an accurate bound on the largest possible such exception, but
I don't know it right now. (Thinks) I think the largest opportunity for
an exception for given n is when p-1 is of the form \prod q_i^k_i, such
that \prod q_i divides A079612(n), and such that d(2(p-1)) . 2^{d(n)-1} < a(n).

:second, it is not said that the bound is tight.

The bound is *not* tight - please see the sentence in my original message
above that starts "I do not mean to imply ...".

:I would suggest to define the sequence via the limit inferior "lim
:inf" notation to make it precise. E.g.:
:a(n) = lim inf A000005(p^n - 1) as p tends to infinity over the primes

By your proposed definition we'd have to say "no terms of this sequence
are known" - before you could say even that a(1)=4 you would have to prove
there are an infinite number of Sophie Germain primes.


More information about the SeqFan mailing list