Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download
Project: Math 582b
Views: 597

Problem 1:

  • Give some fun examples of K.optimized_representation, where K is a number field.

  • Explain in a short very high level paragraph roughly how K.optimized_representation works (start with K.optimized_representation??).

  • I think K.optimized_representation is potentially disturbingly inefficient. Do you agree. Give an example illustrating how it is maybe doing way more than it should be.

K = NumberField([x^2 + p for p in [2,3,5,7]],'a').absolute_field('b') L = K.optimized_representation()[0] f = K.polynomial() g = L.polynomial() print('old polynomial: ' + str(f) + ' with largest coefficient: ' + str(max(f.coefficients()))) print('new polynomial: ' + str(g) + ' with largest coefficient: ' + str(max(g.coefficients())))
old polynomial: x^16 + 136*x^14 + 6476*x^12 + 141912*x^10 + 1513334*x^8 + 7453176*x^6 + 13950764*x^4 + 5596840*x^2 + 46225 with largest coefficient: 13950764 new polynomial: x^16 - 4*x^15 - 14*x^14 + 56*x^13 + 131*x^12 - 484*x^11 - 300*x^10 + 2372*x^9 - 4060*x^8 - 2036*x^7 + 18642*x^6 - 14624*x^5 + 21971*x^4 - 19796*x^3 + 8848*x^2 - 2060*x + 2881 with largest coefficient: 21971
# from pari docs K = CyclotomicField(5).extension(x^5-5,'a').absolute_field('b') L = K.optimized_representation()[0] f = K.polynomial() g = L.polynomial() print('old polynomial: ' + str(f) + ' with largest coefficient: ' + str(max(f.coefficients()))) print('new polynomial: ' + str(g) + ' with largest coefficient: ' + str(max(g.coefficients())))
old polynomial: x^20 - 5*x^19 + 15*x^18 - 35*x^17 + 70*x^16 - 141*x^15 + 260*x^14 - 355*x^13 + 95*x^12 + 1460*x^11 - 3279*x^10 + 3660*x^9 - 2005*x^8 - 705*x^7 + 9210*x^6 - 13506*x^5 + 7145*x^4 + 2740*x^3 + 1040*x^2 + 320*x + 256 with largest coefficient: 9210 new polynomial: x^20 + 25*x^10 + 5 with largest coefficient: 25

K.optimized_representation eventually computes f.polred(2) (where f=K.pari_polynomial()) which calls the polred_aux routine in pari. For each subfield of K, the routine computes the minimal polynomials of small linear combinartions of an LLL-basis. It keeps the polynomials with degree equal to the degree of the subfield and then returns the polynomial with smallest discriminant. We only take one polynomial so f.polred(2) is doing too much work since it computes a polynomial for each subfield. This can be a problem if K has many subfields.

%time K = NumberField([x^2 + p for p in [2,3,5,7,11,13]],'a').absolute_field('b') f = K.pari_polynomial() out = f.polred(2)
CPU time: 23.30 s, Wall time: 23.83 s
%md To contrast, `f.polredbest(1)` does only computes nice polynomials for `K`. 9a4ecdeb-3cb3-4c09-9ce1-ab920e46f81d︠ %time L = NumberField([x^2 + p for p in [2,3,5,7,11,13]],'a').absolute_field('b') f = K.pari_polynomial() out = f.polredbest(1)
CPU time: 10.82 s, Wall time: 11.02 s