[seqfan] Re: Is this sequence duplicate of A088192 Distance between the primes and the largest quadratic residues modulo the primes

[Georgi Guninski]

There was minor bug in my program involving prime powers.

Now my sequence agrees with A088192 for p < 10^7 and p=23 is
certainly not a counterexample.

I don't try to solve x^2 + d y^2 = p.

I try to factor p over the number field with defining polynomial
x^2 + d and check if the result is a single ideal with exponent 1
(not sure if this makes sense but suppose this is what idealfactor() does).


{
issquQd(p)=
local(K,d,v);
/*
smallest d s.t. prime p is composite in Q[sqrt(-d)], i.e.
the factorization of p in the number field with defining polynomial
x^2 + d is not a single ideal with exponent 1.
*/
for(d=1,p,v=idealfactor(bnfinit(x^2+d),p);if( #(v~) !=1 || v[1,2] != 1,return(d)));
return(-1);
}

{
A088192(p)=
local(i);
for(i=1,p,
if(Mod(-i,p)^((p-1)\2)==1,return(i));
);
return(-1);
}

? forprime(p=2,10^7,a1=issquQd(p);a2=A088192(p);if(a1!=a2,print("diff=",p)))
? ##
  ***   last result computed in 17min, 10,400 ms.
? 

On Mon, Oct 29, 2012 at 06:42:00PM -0400, Max Alekseyev wrote:
> I think the smallest counterexample is prime(9)=23 with A088192(9)=5.
> 23 is not representable in the form x^2 + 5*y^2.
> Max
> 
> On Mon, Oct 29, 2012 at 6:00 PM, Max Alekseyev <maxale at gmail.com> wrote:
> > A088192(n) can be defined defined as the smallest d>0 such that -d is
> > a quadratic residue modulo p = prime(n).
> > At the same time, in your sequence a(n) = d if and only if p is
> > representable in the form x^2+d*y^2.
> > While -d being a quadratic residue modulo p is necessary condition for
> > such a representation, it is not sufficient. Additionally it is
> > required that a certain polynomial, denoted f_d(x), has zeros modulo
> > p. For details, see http://math.rice.edu/~av15/Files/Gauss.pdf
> > That is, in general we have a(n) >= A088192(n) but I currently do a
> > reason why it should be a(n) = A088192(n). So my bet is that there
> > exists a counterexample for this equality (in this counterexample,
> > f_d(x) would have no zeros modulo p).
> >
> > Regards,
> > Max
> >
> > On Mon, Oct 29, 2012 at 12:00 PM, Georgi Guninski <guninski at guninski.com> wrote:
> >> Is this sequence duplicate of A088192 Distance between the primes and the largest quadratic residues modulo the primes
> >>
> >> A088192 Distance between the primes and the largest quadratic residues modulo the primes
> >>
> >> I am trying to compute a(n)=smallest d s.t. the n-th prime is
> >> composite in Q[sqrt(-d)].
> >>
> >> Using idealfactor() the pari script is:
> >>
> >> {ndi(d,p)=#idealfactor(bnfinit(x^2+d),p)~==1}
> >>  forprime(p=2,300,for(d=1,p,if(!ndi(d,p),print1(d,",");break) ))
> >> 2,1,3,2,1,1,2,5,1,3,1,1,2,5,1,2,1,2,7,1,3,2,1,1,1,3,2,1,1,3,2,1,2,1,3,1,2,5,1,2,1,7,1,1,3,2,3,2,1,1,7,1,2,1,5,1,3,1,1,2,1,
> >>
> >> 1. Is this a correct way to compute it? (Checking for being an integer
> >> norm gives very few differences)
> >> 2. Is this the same as A088192?
> >>
> >> Thanks.
> >>
> >>
> >> _______________________________________________
> >>
> >> Seqfan Mailing list - http://list.seqfan.eu/
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/