View Single Post
Old 2004-03-10, 15:48   #20
xilman's Avatar
May 2003
Down not across

17·619 Posts

Originally Posted by Bob Silverman
Actually Paul, the size of the root does matter. Let's use your example
and look at a 'typical' lattice point. (say (3x10^6, 3x10^6)) (choose
another if you like)

We have two polynomials. The corresponding norms at lattice point (b,a)
are a + 10^37 b and a^6 + 10b^6. For our typical point, the norms are
about 3x10^43 and 7x10^39. Note that the linear norm is larger. The
product is about 2x10^82

If we were to use a quintic, the linear norm becomes about 3 x 10^51
while the algebraic norm shrinks to 2 x 10^33. The product is now about
6 x 10^84, i.e. larger.

A septic would yield norms of about 3x10^38 and 2 x 10^46.

Having equal norms would be optimal.

The size of the root affects the norm of the linear polynomial. There is a
ying-yang effect. Reducing one norm increases the other and vice versa.
We want the product to be as small as possible averaged over the sieve

See my recent paper for a more detailed analysis.

Bob, I agree with you (with the reservations noted in my original about the analysis only being a first cut) if the linear polynomial is of the form x-m where m is the root.

Note there is nothing in the NFS which requires a polynomial to be linear, though a linear polynomial is very frequently used because of the difficulty in finding good polynomials of higher degree which share a common root with other polynomial(s) in use.

Neither is there any requirement that a linear polynomial by x-m. I gave an explicit example where the root m is very large but the poynomial norms are quite small. That polynomial was x/m - 1.

I further note that Kleinjung's method of finding quintics for GNFS finds linear polynomials of the form ax+b where neither a nor b are equal to the value of the common root.

I stand by my claim that (subject to the agreed disclaimer) that the size of the coefficients of the polynomials are much more important than the size of the root. By taking x-m as your linear polynomial you are implicitly agreeing with me as in this particular case the root is a coefficient of a polynomial.

I do, of course, agree that ideally the degrees and coefficients of the polynomials should be chosen that the norms are as close to each other as possible and as small as possible (again, subject to considerations which can be found in Murphy's thesis).

xilman is offline