***unexpected chracter: ...,return(b)=0));return(1);}{reduce(f)=local(D,
? E13=ellinit([0,0,0,-4,16]*Mod(1,13)) *** singular curve in ellinit.I was just wondering if that is part of what we are supposed to do for the problem, or if it is a mistake.
? \r filename.gp
f(z0) = f'(z0) = ... = f(r-1)(z0) = 0but
f(r)(z0) =/= 0.Thus its first r derivates (the 0th through (r-1)st) vanish at z0, but the r-th derivative does not.
Is Doud's algorithm not guaranteed to compute the full torsion group? I > am puzzled by the following behavior: > > ? e=ellinit([0,0,0,-10846856157922827,434814147916401568208454]); > ? elltors(e) > %2 = [6, [6], [[59485323, 8627776560]]] > ? for(i=1,6, print(ellpow(e,[59485323,8627776560],i))) > [59485323, 8627776560] > [60777003, 8689777200] > [-120260022, 0] > [60777003, -8689777200] > [59485323, -8627776560] > [0] > ? ellisoncurve(e,[60091419,0]) > %3 = 1 > ? ellpow(e,[60091419,0],2) > %4 = [0] > > So [60091419, 0] is in the torsion group, but not in the cyclic > group generated by [59485323, 8627776560].
Yes, Doud's algorithm should give the full torsion subgroup. Evidently Doud's algorithm as implemented in PARI requires the curve to be in "minimal form", and it doesn't change the form to be minimal for you. Behold: ? e=ellinit([0,0,0,-10846856157922827,434814147916401568208454]); ? elltors(e) %2 = [6, [6], [[59485323, 8627776560]]] ? f=ellglobalred(e) %3 = [2676208470, [6, 3, 3, 0], 62208] ? ee=ellchangecurve(e,f[2]) %4 = [1, 0, 0, -8369487776175, 9319575518172005625, 1, -16738975552350, 37278302072688022500, -70048316315967228725625000, 401735413256401, -8052113850303732744601, 46367070089839400992758295329000000, 64836617580550319021577618714177184806649201/46367070089839400992758295329000000, [1671349.999999999999999999999, 1669205.999999999999999999999, -3340556.250000000000000000000]~, 0.004703740756481346451602644899, 0.001403443255552375980283896400*I, 1689.788153472741998765595537, -163.7145638235014246650611570*I, 0.000006601433240550576622182616090] ? elltors(ee) %5 = [12, [6, 2], [[2307180, 1512439725], [1669206, -834603]]] The MathSciNet review of Doud's paper: Doud, Darrin(1-IL) A procedure to calculate torsion of elliptic curves over $Q$. (English. English summary) Manuscripta Math. 95 (1998), no. 4, 463--469. The author gives an algorithm for computing the rational torsion subgroups of an elliptic curve using the standard Weierstrass analytic parametrization. The Lutz-Nagell algorithm is particularly simple, but involves testing a potentially large number of cubic equations for integral roots, as well as necessitating factorization of the discriminant of the curve. This latter calculation can be a stumbling block when the coefficients of the curve become large. The current algorithm is very attractive, with most of its run time computing values of the $\wp$ function. The author has made available the algorithm in GP-PARI code, and gives several examples of computations where the results are demonstrably superior to current torsion programs.
(6 points) Many number theorists, such as myself one week ago, incorrectly think that Lutz-Nagell works well in practice. Describe the steps you {\em would} take if you were to use the Lutz-Nagell theorem (Lecture 27) to compute the torsion subgroup of the elliptic curve E defined by the equation
Here is a hint. Start with the equation y^2 + xy + y = x^3. Think
of it as a quadratic equation with unknown y:
y^2 + (x+1)y - x^3 = 0
Now use the quadratic formula to write
y = (-b + sqrt(b^2-4ac))/2a.
Then 2a*y + b = sqrt(b^2 - 4ac), so if we set Y = 2*a*y + b, we have
Y^2 = b^2 - 4ac = a cubic polynomial in x,
and you are well on your way!
E(K) = { (x,y) in K x K : y^2 = x^3 + ax + b }.
\documentclass{article}
\usepackage{graphicx}
\begin{document}
This works for me!\\
\includegraphics{picture}
\end{document}
For more information, check out epslatex.ps or
l2e-grfguide.dvi.
{orderform(a, iden)=
local(product, order);
order = 1;
product = a;
if (a == iden, return(order), order++);
while(order > 0,
if ((product = composition(a, product)) == iden,
return(order), order++);
)
}
composition([4,3,15],[2,-1,29])(these two come up when computing the reduced forms for D = -231). Is there some problem with the PARI code or maybe my computer hasn't enough power?
Yes, there was a bug. If you didn't already find it yourself, change
line 15 of forms.gp from
if(c < a,
to
if(c < a || (c==a && b< 0),
I've changed the version of forms.gp available at
http://modular.math.washington.edu/edu/Fall2001/124/lectures/lecture24/
Second, it takes about 10 minutes to compute the reduced forms of
discriminants -12104 and -10015. For those of you who are either
impatient or have with slow computers, I've included the reduced forms
of those two discriminants at the end of this email. You could paste
this list into PARI and work with it.
Reduced forms of discriminant -12104:
[[1, 0, 3026], [10, -4, 303], [10, 4, 303], [13, -8, 234], [13, 8,
234], [15, -14, 205], [15, -4, 202], [15, 14, 205], [15, 4, 202], [17,
0, 178], [18, -8, 169], [18, 8, 169], [2, 0, 1513], [25, -14, 123],
[25, 14, 123], [26, -8, 117], [26, 8, 117], [27, -10, 113], [27, 10,
113], [3, -2, 1009], [3, 2, 1009], [30,-16, 103], [30, -4, 101], [30,
16, 103], [30, 4, 101], [34, 0, 89], [39, -34, 85], [39, -8, 78], [39,
34, 85], [39, 8, 78], [41, -14, 75], [41, 14, 75], [45, -26, 71], [45,
-44, 78], [45, 26, 71], [45, 44, 78], [5, -4, 606], [5, 4, 606], [50,
-36, 67], [50, 36, 67], [51, -34, 65], [51, 34, 65], [54, -44, 65],
[54, 44, 65], [6, -4, 505], [6, 4, 505], [9, -8, 338], [9, 8, 338]]
Reduced forms of discriminant -10015:
[[1, 1, 2504], [10, -5, 251], [10, 5, 251], [14, -11, 181], [14, -3,
179], [14, 11, 181], [14, 3, 179], [16, -15, 160], [16, 15, 160], [17,
-7, 148], [17, 7, 148], [19, -13, 134], [19, 13, 134], [2, -1, 1252],
[2, 1, 1252], [20, -15, 128], [20, 15, 128], [23, -17, 112], [23, 17,
112], [28, -17, 92], [28, -25, 95], [28, 17, 92], [28, 25, 95], [32,
-15, 80], [32, 15, 80], [34, -27, 79], [34, -7, 74], [34, 27, 79],
[34, 7, 74], [35, -25, 76], [35, 25, 76], [37, -7, 68], [37, 7, 68],
[38, -13, 67], [38, -25, 70], [38, 13, 67], [38, 25, 70], [4, -1,
626], [4, 1, 626], [40, -15, 64], [40, 15, 64], [43, -41, 68], [43,
41, 68], [46, -17, 56], [46, -29, 59], [46, 17, 56], [46, 29, 59],
[49, -31, 56], [49, 31, 56], [5, 5, 502], [7, -3, 358], [7, 3, 358],
[8, -1, 313], [8, 1, 313]]
? x=5 %1 = 5 ? kill(x) ? x %2 = x ? x^2 %3 = x^2
? {for(x=1,3,
? for(y=1,2,
? p print("x^2 + y^2 = ", x^2+y^2)
? )
? )}
x^2 + y^2 = 2
x^2 + y^2 = 5
x^2 + y^2 = 5
x^2 + y^2 = 8
x^2 + y^2 = 10
x^2 + y^2 = 13
-- William
for(x=0, something, for(y=0,something, etc.
if(x^2 + y^2 + z^2 + w^2 == number,
print out x, y, z, and w.
f(a) = 2a^2(a+1)^2+1 = 2a^4 + 4a^3 + 2a^2 + 1
is a sum of two squares. I stared at this for a few minutes and didn't
see an obvious reason. Then I wrote a tiny program to list
sums of two squares of quadratic polynomials with small
coefficients and looked to see whether or not 2x^4 + 4x^3 + 2x^2 + 1
appeared in the list. It does.
x^2 + (x+1)^2 = z^2.Multiply out and rearrange terms and do a little algebra to get
2x^2 + 2x + 1 - z^2 = 0Now complete the square to make the above expression look something like
2*X^2 - Z^2 = -1/2
for some X and Y. Now do a little more algebra to get something
like Z^2 - 2X^2 = 2, which you know how to deal with.
"22/7 is correct to 3 decimal places"In fact,
pi = 3.1415926... and 22/7 = 3.1428571...so this author agrees with my usage.
|x - c_n| < 1/(q_n*q_{n+1}) <= 1/(n*(n+1))
to find an n such that
|sqrt(5) - c_n| < 10^(-3).Then compute cn. In practice, you'll probably get an even better approximation. For problem 7, just compute.
pn pn-2
----- = an + ----------
pn-1 pn-1
In exercise 4 (i), there is only one positive root. The two roots of 3*x2-6*x-2 are approximately 2.29099444873 and -0.29099444873, so only one is positive. The first is the value of the continued fraction.
However, to answer your question, you can decide which root is correct
by computing the first few partial convergents of the continued
fraction and seeing which root they converge to. It will quickly be
clear that one of the two roots is out of the question.
znorder(Mod(a,p)) == p-1if and only if a is a primitive root modulo p.
phi(p^2) = p^2 - p = p*(p-1).
If you can find an element of order p, and another of order (p-1), then
their product will have order phi(p^2).
> (1) KTH POWER RESIDUES
> When we say that a number "a" is a kth power residue mod p, we mean that a
> == x^k mod p. Now, do we make the distinction that x is in the set
> {1,2,3,...,p-1}? Or, might x be greater than any of these numbers? (And,
> if x is indeed greater, will it always be the case that x^k is congruent to
> one of numbers in the set raised to the kth power--that is, we can simply
> replace x^k by y^k, y in {1,2,3,...,p-1}?--This is, I think, related to the
> earlier question, your proof of which still confuses me.)
It doesn't matter whether or not x is in the set {1,2,3,...,p-1}.
Suppose x is any integer and a == x^k (mod p). Let r be such that
x = c*p + r with 0 < r < p. Then a == r^k (mod p). This is because,
if x == r (mod p), then x^k == r^k (mod p). Very explicitly, if
p | x - r, then p | x^k - r^k = (x-r)(x^(k-1)+...+r^(k-1)).
> (2) PAGE 66: "Half the numbers 1,2,...,p-1 are quadratic residues and the
> other half are quadratic non-residues. The quadratic residues are
> congruent to the numbers 1^2, 2^2, ... , [1/2(p-1)]^2." HUH???????
> WHY??????? And why do we stop at [1/2(p-1)]^2
First, we stop at [1/2(p-1)]^2, because the number between [1/2(p-1)]
and p-1 are congruent to the _negatives_ of the numbers between 1 and
[1/2(p-1)]^2, and a^2 = (-a)^2. The numbers 1^2, 2^2, ... (mod p) are
the quadratic residues because the quadratic residues are, by definition,
exactly the set of distinct squares modulo p.
> And, I'm probably bound to stop by tomorrow for more.
Please do.
> Incidentally, the question on the 122 homework was to prove that in Fp, the
> set of all x^2, with x in Fp, is a group--is this the same thing as showing
> that all quadratic resiudes are a group?
I assume you mean "prove that the set of all _nonzero_ x^2 in F_p is a group",
since it's not a group without the nonzero condition. And yes, this is the
same as showing that the set of all quadratic resiudes are a group.
> (If so, how do I know that I'm
> not leaving any out by just squaring and reducing each element of Fp)
If a number is a square, then it's the square of something. As discussed
in question (1) above, that something can be taken < p.
In Lecture 11 you write:
Remark 2.4 There are \phi(n) primitive roots modulo ..., since there are ... ways to choose ...
It is not very clear to me why differenct choices of a_i lead to
different generators.
Answer:
I just added a proof of this to the remark. You can either try to read
the remark in this email, or view the
new version of lecture 11.
There are $\vphi(p-1)$ primitive roots modulo~$p$, since there are
$q_i^{n_i} - q_i^{n_i-1}$ ways to choose $a_i$. To see this, we check
that two distinct choices of sequence $a_1,\ldots, a_r$ define two
different primitive roots. Suppose that
$$
a_1 a_2 \cdots a_r = a'_1 a'_2 \cdots a'_r,
$$
with $a_i$, $a'_i$ of order $q_i^{n_i}$, for $i=1,\ldots,r$.
Upon raising both sides of this equality to the power
$s = q_2^{n_2}\cdots q_r^{n_r}$, we see that
$a_1^s = a_1'^s$. Since $\gcd(s,q_1^{n_1})=1$,
there exists~$t$ such that $st\con1\pmod{q_1^{n_1}}$.
It follows that
$$
a_1 = (a_1^s)^t = (a_1'^s)^t = a'_1.
$$
Upon canceling $a_1$ from both sides, we see that $a_2 \cdots a_r =
a'_2 \cdots a'_r$; by repeating the above argument, we see that $a_i =
a'_i$ for all~$i$. Thus, different choices of the $a_i$ must lead to
different primitive roots; in other words, if the primitive roots are the
same, then the $a_i$ were the same.
? ?write
write(filename,a): write the string expression a (same output as print) to
filename.
? for(n=1,7,write("testfile", n!,"\t",n))
p-1 = q*i + r
with 0<=r
x^p = (1 + ... + 1)^p ==
1^p + ... + 1^p + (bunch of other stuff divisible by p),
This is the same as saying that x^p = x (mod p).
The key step is to show that the bunch of other stuff is divisible
by p, and that follows from a binomial-theorem like formula for
(x_1 + x_2 + ... + x_n)^p.