Representing x^2+3y^2

Zeta-Flux · 2005-08-01, 23:38

Let n be a positive integer. There is a very nice formula for the number of ways n can be represented by the quadratic form x^2 + y^2, in terms of the prime factors of n. Does anyone know of a similar formula for the form x^2+3y^2?

Thanks

maxal · 2005-08-03, 01:16

The formula is similar to the one for r₂(n) given at http://mathworld.wolfram.com/SumofSquaresFunction.html.

Let n be represented as
n = 3^c p₁^{2a[sub]1[/sub]} ... p_n^{2a[sub]n[/sub]} q₁^{b[sub]1[/sub]} ... q_r^{b[sub]r[/sub]},
where p₁, ..., p_n are primes of the form 3k+2, and q₁, ..., q_k are primes of the form 3k+1.

Let B=(b₁+1)...(b_r+1). Then the number of representations n=x^2+3*y^2 equals

0 if either of a_i is a half-integer;
6B if n is a multiple of 4;
2B otherwise.

Zeta-Flux · 2005-08-03, 01:34

Seems correct. That is what I guessed, but I couldn't find any official source for it. It turns out I don't need an official proof after all, so I'll just believe you got it right!

Thanks,
Pace

philmoore · 2005-08-03, 05:27

Of course, 2 is a prime = 2 mod 3, so if n is divisible by 4, it must contain an even power of 2 in order to have representations. So Maxal's observation implies than an n divisible by 8 but not by 16 has zero representations.

By the way, I was solving the equation x^2+3y^2=Mp for all Mersenne primes Mp last spring using script files with pfgw, but stopped at Mp=2^3021377-1 because the Euclidean algorithm as implemented in my script file was a bottleneck. Still, it was fun solving Diophantine equations with such huge solutions (450,000+ digits).

maxal · 2005-08-03, 18:40

Quote:

Originally Posted by philmoore

By the way, I was solving the equation x^2+3y^2=Mp for all Mersenne primes Mp last spring using script files with pfgw, but stopped at Mp=2^3021377-1 because the Euclidean algorithm as implemented in my script file was a bottleneck.

What method do you use to find x,y?
I would solve this problem via computing (-3)^(1/2) mod Mp which is quite unrelated to the Euclidean algorithm.

philmoore · 2005-08-03, 21:10

I checked again, and see that I actually went as far as x^2 + 3*y^2 = M6972593 before the GCD implementation was starting to take longer than the powering algorithm.

I believe this is called "Cornacchia's algorithm" or some variant of it:

Q = 2^EXP - 1 ; (This is the Mersenne prime)
SqrtQ = SQRT(Q)
B = 3^(2^(EXP-2)) mod Q ; This was done using George Woltman's code in pfgw
IF (B>Q/2) THEN B=Q-B
A = Q
IF (B<SqrtQ) GOTO Loop_end
Loop_start
T = A mod B
A = B
B = T
IF (B>SqrtQ) GOTO Loop_start
Loop_end
A = SQRT((Q-B^2)/3)

As you see, I wasn't actually using the GCD algorithm to the end, I only went until B<SqrtQ, so before going on to M13466917, I need to write a more efficient implementation than is available in the SCRIPT file capability of the development version of pfgw.

2005-08-01, 23:38	#1
Zeta-Flux May 2003 11000001011₂ Posts	Representing x^2+3y^2 Let n be a positive integer. There is a very nice formula for the number of ways n can be represented by the quadratic form x^2 + y^2, in terms of the prime factors of n. Does anyone know of a similar formula for the form x^2+3y^2? Thanks

2005-08-03, 01:16	#2
maxal Feb 2005 2²×3²×7 Posts	The formula is similar to the one for r₂(n) given at http://mathworld.wolfram.com/SumofSquaresFunction.html. Let n be represented as n = 3^c p₁^{2a[sub]1[/sub]} ... p_n^{2a[sub]n[/sub]} q₁^{b[sub]1[/sub]} ... q_r^{b[sub]r[/sub]}, where p₁, ..., p_n are primes of the form 3k+2, and q₁, ..., q_k are primes of the form 3k+1. Let B=(b₁+1)...(b_r+1). Then the number of representations n=x^2+3y^2 equals 0 if either of a_i is a half-integer; 6B if n is a multiple of 4; 2B otherwise. Last fiddled with by maxal on 2005-08-03 at 01:22*

2005-08-03, 01:34	#3
Zeta-Flux May 2003 7×13×17 Posts	Seems correct. That is what I guessed, but I couldn't find any official source for it. It turns out I don't need an official proof after all, so I'll just believe you got it right! Thanks, Pace

2005-08-03, 05:27	#4
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3·373 Posts	Of course, 2 is a prime = 2 mod 3, so if n is divisible by 4, it must contain an even power of 2 in order to have representations. So Maxal's observation implies than an n divisible by 8 but not by 16 has zero representations. By the way, I was solving the equation x^2+3y^2=Mp for all Mersenne primes Mp last spring using script files with pfgw, but stopped at Mp=2^3021377-1 because the Euclidean algorithm as implemented in my script file was a bottleneck. Still, it was fun solving Diophantine equations with such huge solutions (450,000+ digits).

2005-08-03, 21:10	#6
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 2137₈ Posts	I checked again, and see that I actually went as far as x^2 + 3*y^2 = M6972593 before the GCD implementation was starting to take longer than the powering algorithm. I believe this is called "Cornacchia's algorithm" or some variant of it: Q = 2^EXP - 1 ; (This is the Mersenne prime) SqrtQ = SQRT(Q) B = 3^(2^(EXP-2)) mod Q ; This was done using George Woltman's code in pfgw IF (B>Q/2) THEN B=Q-B A = Q IF (B<SqrtQ) GOTO Loop_end Loop_start T = A mod B A = B B = T IF (B>SqrtQ) GOTO Loop_start Loop_end A = SQRT((Q-B^2)/3) As you see, I wasn't actually using the GCD algorithm to the end, I only went until B<SqrtQ, so before going on to M13466917, I need to write a more efficient implementation than is available in the SCRIPT file capability of the development version of pfgw.