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

[Max Alekseyev]

Oh, I see now. Somehow I did not notice that you work in extension of Q not Z.
You problem is equivalent to solving x^2 + d y^2 = p*z in integers
x,y,z. And this is solvable if and only if -d is a quadratic residue
modulo p.
So the sequences are indeed the same.
Regards,
Max

On Tue, Oct 30, 2012 at 2:23 AM, Georgi Guninski <guninski at guninski.com> wrote:
> 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/
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/