Wikipedia:Reference desk/Archives/Mathematics/2012 September 6

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 6

Implementing an algorithm to generate Proth Primes

Hello all. I'm trying to implement an efficient Proth Prime generator using Proth's theorem, but there are a few concepts that I am a little unclear about. Primarily:

- How many values of 'a' (on a logarithmic scale, perhaps) must be used to make the primality test deterministic?

- How should a given 'a' be chosen? Start at, say, 2 and then simply increment, or what?

- Would it be more efficient to first calculate the Jacobi symbol and test that 'a' is a quadratic nonresidue, or simply select 'a' by some other means?

Apologies for the ignorance, but I'm a computer programmer, not a mathematician! Thanks.

66.87.80.180 (talk) 00:19, 6 September 2012 (UTC)

For the first question, the complexity of finding a such that (a|p) = −1 deterministically is a difficult open problem. Assuming the generalized Riemann hypothesis for quadratic Dirichlet characters, one can always find an a ≤ 2(ln p)² which either has this property or is a proper divisor of p. On the other hand, unconditionally known bounds are essentially exponential, IIRC they are of the form p^ε for some constant ε.

For the second question, the best way is to chose a randomly. If you want to do it deterministically, I’m not aware of any advantage of doing it any other way than testing small a successively as you write, except that in this case, it suffices to test only prime a.

I don’t quite understand the third question, what other means do you have in mind?—Emil J. 11:45, 6 September 2012 (UTC)

Okay, thanks. Taking all of that into consideration, it seems that I might as well just stick with the Miller-Rabin test and abandon Proth Primes altogether then, as it has a much lower known lower bound (and an even lower heuristic lower bound) besides being suitable for primes of any form anyway. Cheers!

66.87.126.188 (talk) 14:50, 6 September 2012 (UTC)

Polynomial equations

hi, i just wonder what could b so wrong in solving math polynomial eqs. by choosing 2 arbitrary values 4 x, x1 n x2 then compute xm=(x1+x2)/2, wrinting P(x)=P(x-xm)+P(xm) then P(x1)=..similary, P(x2)=similary then somthing like P(y-a)=P(y+a)=0 y=xm a=xm-x1

P 4 ur delight, anyway LOL

Florin, Romania — Preceding unsigned comment added by 93.118.212.93 (talk) 13:02, 6 September 2012 (UTC)

Because for a general polynomial P, P(x) does not equal P(x-xm)+P(xm); for instance, $(x-x_{m})^{2}+x_{m}^{2}=x^{2}-2xx_{m}+2x_{m}^{2}$, which is not x^2 unless $x=x_{m}$ which is unlikely since you have effectively taken xm arbitrary. Straightontillmorning (talk) 14:42, 6 September 2012 (UTC)

It seems like the OP might be groping for something like Newton's method. Looie496 (talk) 17:05, 6 September 2012 (UTC)

More on "Project Euler question" from Sept 5

Ok, with "Convergents (p,q) to the continued fraction expansion of sqrt(2)", it is sqrt(2) because the the equation has the form p^2 = 2*q^2 - 1. Had it been p^2 = 99*q^2 -1 it would have been sqrt(99) I presume.

It was said "Alternate convergents (1,1), (7,5), (41,29) etc. satisfy p^2 = 2*q^2 - 1". This is true by inspection, but how did you get alternates in the first place? Had I thought to do such a thing, I would have tried them all and given up when 9 = 3^2 != 2*2^2 - 1 = 7.

I now follow the mechanism that have been used here, but have no feel as to why/how it was decided theat these were good tools / transforms to use. What points in that direction? -- SGBailey (talk) 15:06, 6 September 2012 (UTC)

What points in that direction ? Mostly previous experience, having seen similar problems before and played around with continued fractions. Starting with

$2b^{2}-2b=n^{2}-n$

a natural first step is to complete the square on both sides, giving

$2\left(b-{\frac {1}{2}}\right)^{2}-{\frac {1}{2}}=\left(n-{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}$

Multiplying both side by 4 to get rid of the fractions gives

$2(2b-1)^{2}-1=(2n-1)^{2}$

So if we set

$p=2n-1\quad q=2b-1$

then we want to find integers p and q such that

$p^{2}=2q^{2}-1$

$\Rightarrow {\frac {p}{q}}\approx {\sqrt {2}}$

which suggests we are looking for rational approximations to sqrt(2). The convergents to the continued fraction expansion of sqrt(2) are one such series of approximations, and I happened to know that they satisfy

$p^{2}=2q^{2}\pm 1$

with alternating signs. So it was then just a case of working out the recurrence relations between alternate convergents, and then translating this back into recurrence relations in terms of b and n instead of p and q. Gandalf61 (talk) 15:56, 6 September 2012 (UTC)

Many thanks. That made sense :-) -- SGBailey (talk) 18:54, 6 September 2012 (UTC)

surjective Homomorphism

Hi. Is it true that any two surjective homomorphisms $S_{4}\rightarrow S_{3}$ have the same kernel? By the correspondence theorem there exists a bijection between subgroups of $S_{4}$ containing the kernel of SOME homomorphism and the subgroups of $S_{3}$ but does this imply that this kernel is the same for any homomorphism?--150.203.114.14 (talk) 23:07, 6 September 2012 (UTC)

According to the symmetric group page, S₄ has only one normal subgroup of order 4 (which I think is the one consisting of the 2,2 cycle types). In that case, that's the only possible kernel of size 4 of a group homomorphism from S₄. Rckrone (talk) 02:28, 7 September 2012 (UTC)

This is easily seen from the class equation, where I've put the lengths of the cycles in each conjugacy class in parentheses: 24 = 1 + 3 (2,2) + 6 (2) + 8 (3) + 6 (4). So there's only one way to collect conjugacy classes into a subset with 4 elements, and that just happens to be a subgroup. --COVIZAPIBETEFOKY (talk) 11:36, 7 September 2012 (UTC)