Project: Math 582b

Path: lectures / 2016-02-10-unit-group / 2016-02-10-unit-group.sagews

Views: ²⁴⁹⁵

Feb 10, 2016: computing the unit group

William Stein

1. Recall: Unit group

For a number field $K$ , the unit group $U=U_K$ is the group of units of $R=\mathcal{O}_K$ . The main fact is Dirichlet's unit theorem, which gives the abstract structure of $U$ as an abelian group: it's $U/U_{\rm tor} = \ZZ^{r_1+r_2-1}$ , where $r_1$ is the number of real embeddings $K\hookrightarrow \RR$ , $r_2$ is the number of pairs of complex conjugate embeddings of $K$ , and $U_{\rm tor}$ is a finite group.

This stuff isn't easy to prove - it's a central result in a first course. It uses the log embedding from $U$ to $\RR^{r_1+r_2}$ , which embeds $U$ (mod torsion) as a lattice in a codimension 1 subspace.

So computing the rank of the unit group is very easy. Computing actual generators -- even writing them down (!) -- can be extremely time consuming. It's connected to the difficulty of computing classgroups. The two problems are entangled, though in funny ways. E.g., for real quadratic fields the class group is often tiny, but the unit group (which always has rank 1) often has very large generators. We will see something similar with rank 1 elliptic curves later.

2. Real Quadratic Fields

Exercise: run this code, which computes a generator for the unit group (or, as you know, solution to Pell's equation...

# table of values
v = []
for d in [2..1000]:
    if is_fundamental_discriminant(d):
        K = QuadraticField(d)
        h = K.class_number()
        r = K.unit_group()
        gen = K(r.gens()[1])
        print d,  h, gen
        v.append([d,len(str(gen))])

# plot of size of unit (in characters!)
line(v)

1 1/2*a + 1/2
1 1/2*a + 1
1 1/2*a - 2
1 1/2*a + 3/2
1 a - 4
1 1/2*a + 5/2
1 a + 5
1 3/2*a - 8
1 1/2*a + 5/2
1 4*a + 23
1 a + 6
2 1/2*a - 3
1 5*a + 32
1 3/2*a - 10
1 1/2*a + 7/2
1 2*a + 15
1 20*a - 151
2 1/2*a + 4
1 5/2*a + 39/2
2 a + 8
1 3/2*a - 25/2
1 125*a + 1068
1 39/2*a + 170
1 1/2*a - 9/2
2 1/2*a - 9/2
1 21*a - 197
1 53*a + 500
1 5/2*a + 24
1 3/2*a - 29/2
1 569*a + 5604
1 a + 10
2 1/2*a - 5
2 4*a - 41
1 25/2*a + 261/2
1 73*a - 776
2 a - 11
1 273/2*a + 1520
1 1484*a + 16855
1 15/2*a + 173/2
2 3*a + 35
1 149*a + 1744
2 1/2*a + 6
1 8*a - 95
4 a - 12
1 5/2*a - 61/2
1 3*a + 37
2 2*a + 25
1 17/2*a + 213/2
1 928*a + 11775
2 1/2*a + 13/2
2 a - 13
1 531/2*a + 3482
1 1/2*a + 13/2
1 4692*a - 62423
1 97/2*a + 1305/2
1 1794*a - 24335
2 5*a + 68
1 7/2*a + 48
1 126985*a - 1764132
1 a + 14
1 36332*a + 515095
2 7/2*a - 50
2 3/2*a - 43/2
1 3220*a - 46551
1 5/2*a + 73/2
1 260952*a - 3844063
2 6*a + 89
2 1/2*a + 15/2
3 1/2*a + 15/2
2 13/2*a - 99
1 1517*a - 23156
1 69/2*a + 530
1 5/2*a + 77/2
1 4574225*a - 71011068
1 4*a + 63
1 542076*a + 8553815
1 117/2*a + 1861/2
3 a + 16
2 4*a + 65
2 373*a - 6072
1 5967/2*a + 48842
1 5*a + 82
2 44*a - 727
1 157/2*a - 2613/2
2 15*a - 251
1 63445*a + 1063532
1 413/2*a - 3480
2 1/2*a + 17/2
1 1/2*a + 17/2
2 5/2*a + 43
1 1311/2*a - 22745/2
2 28*a - 489
1 287/2*a + 5045/2
2 3*a - 53
1 7170685*a + 126862368
3 9/2*a - 80
1 5/2*a + 89/2
3 12*a + 215
4 1/2*a - 9
1 131016*a + 2376415
1 9/2*a + 82
1 55335641*a - 1015827336
1 15/2*a - 277/2
1 561*a - 10405
2 364*a + 6761
2 3/2*a + 28
1 493*a + 9210
1 3793*a - 71264
2 1/2*a - 19/2
2 165/2*a + 1574
2 1/2*a + 19/2
1 265*a + 5118
1 110532*a + 2143295
2 12*a - 233
2 2*a + 39
1 52*a - 1015
2 4884*a - 95831
1 65*a - 1282
1 2342444*a + 46437143
1 173/2*a - 3447/2
5 a + 20
2 5*a + 101
1 5534176685*a - 111921796968
1 22419/2*a - 227528
1 3/2*a - 61/2
1 4178268*a - 85322647
1 21685/2*a + 444939/2
2 389/2*a - 4005
1 93/2*a - 962
2 7/2*a - 145/2
1 347483377*a + 7230660684
1 1/2*a - 21/2
2 a - 21
2 14*a - 295
4 1/2*a + 21/2
1 8941705*a - 189471332
1 7/2*a + 149/2
2 48*a + 1025
1 2764111349*a + 59089951584
2 105/2*a - 1126
1 17/2*a + 365/2
2 736*a - 15871
3 3/2*a - 65/2
1 14127*a + 306917
3 4*a - 87
2 11/2*a + 120
2 43961*a + 964140
2 a + 22
2 1/2*a - 11
1 343350596*a - 7592629975
2 11/2*a - 122
2 5/2*a - 111/2
1 53912*a - 1201887
1 1261/2*a - 28225/2
4 36*a + 809
1 419775/2*a - 4730624
1 41/2*a - 925/2
1 465/2*a - 10573/2
4 5/2*a + 57
1 5624309*a - 128377240
1 927/2*a - 10610
2 1/2*a + 23/2
1 6303*a + 145925
1 8300492*a - 192349463
1 60037/2*a - 1396425/2
2 84*a + 1961
2 2*a - 47
1 26562217704*a - 624635837407
1 6578829/2*a + 77563250
1 5*a - 118
2 22072*a - 522785
2 13/2*a - 309/2
3 6*a + 143
1 121359005*a + 2894863832
2 1/2*a + 12
1 16*a + 383
7 a - 24
1 279/2*a + 6725/2
2 6*a - 145
1 179625/2*a - 4359377/2
1 24665*a - 600632
1 399/2*a - 9749/2
1 5689030769845*a + 139468303679532
1 140634693/2*a + 1728148040
2 24544*a - 605695
1 3989/2*a + 98763/2
2 858*a + 21295
1 1650989*a + 41009716
2 10*a - 249
2 1/2*a - 25/2
1 308*a - 7743
1 17519124*a + 440772247
2 105/2*a - 1324
1 1426687145*a + 36120833468
2 5/2*a - 127/2
1 44104892095380*a - 1123593226162199
1 5019135/2*a + 64080026
1 65/2*a + 1661/2
1 69605/2*a - 1789539/2
1 66007821*a + 1700902565
2 532*a + 13719
1 13/2*a + 168
1 11803/2*a - 305285/2
1 1881620424025*a - 48813455293932
1 a + 26
4 1/2*a + 13
1 411679015748*a - 10743166003415
2 29/2*a - 759/2
4 4*a - 105
2 55*a + 1451
6 5*a + 132
1 445*a - 11782
2 8932*a - 237161
1 685217*a + 18245310
2 60*a - 1601
1 197976*a + 5286367
1 313191/2*a - 4190210
1 9/2*a + 241/2
1 693898530122112*a + 18632176943292415
2 a - 27
2 18*a - 487
3 1/2*a + 27/2
1 9318468*a + 252975383
2 9/2*a + 245/2
2 275*a - 7501
2 467820*a + 12769001
2 123/2*a + 1682
1 473/2*a - 12945/2
1 11243313484*a - 308526027863
1 49769*a - 1369326
2 1887*a - 52021
3 29*a - 800
1 650783/2*a - 8994000
1 590222604844777*a - 16367374077549540
1 5/2*a + 139/2
2 7*a + 195
4 8*a + 223
4 1/2*a + 14
1 2419140*a + 67606199
6 a - 28
1 1133/2*a - 31825/2
4 156*a + 4393
1 1153080099/2*a - 16266196520
1 13/2*a - 367/2
2 51/2*a - 1447/2
2 221/2*a - 3141
1 15253424933*a + 433852026040
2 2*a + 57
1 76*a + 2167
5 12*a - 343
1 565/2*a - 16189/2
1 2074*a + 59535
1 537965*a - 15489282
4 a - 29
1 19162705353/2*a - 278354373650
1 51536656330476*a - 1501654712948695
1 941/2*a - 27483/2
1 23766887823*a + 695359189925
1 277325*a - 8118568
2 3/2*a + 44
2 35/2*a + 1027/2
2 11844089*a + 348345108
1 1675/2*a + 49377/2
2 17/2*a - 251
4 5/2*a - 74
1 8149*a + 241326
1 3581882825*a - 106316171432
2 4*a + 119
2 5*a + 149
1 443786188413453504*a + 13231974717803657215
3 15/2*a + 224
1 77/2*a + 2301/2
4 20*a + 599
4 a - 30
8 1/2*a + 15
4 12*a - 361
1 15/2*a + 226
1 17068312251564*a - 515734243080407
1 39/2*a - 1181/2
2 3*a + 91
1 83104627139412*a + 2522057712835735
4 5/2*a + 76
1 2667927065*a + 81317086468
1 2464*a + 75263
1 16015008052621*a - 490226695010796
6 3/2*a + 46
1 37/2*a + 1135/2
2 1061/2*a + 32685/2
2 378*a + 11663
1 88979677*a - 2746864744
1 400729/2*a - 6195120
2 1/2*a - 31/2
2 1/2*a + 31/2
2 436540*a - 13588951
1 28956*a - 903223
1 236003105*a + 7376748868
2 2831*a - 88805
6 13*a - 408
2 5427/2*a + 85292
1 3283/2*a + 103245/2
3 84*a + 2647
1 2689*a - 84906


︠2e60b73e-8374-4a11-a303-90062b7bf8fai︠
%md

Right now -- right down a quick rough guess based on the above for how the "regulator" (=basically number of digits of unit generators) behaves as a function of d.

Right now -- right down a quick rough guess based on the above for how the "regulator" (=basically number of digits of unit generators) behaves as a function of d.


︠a825d5ca-b42e-4f1b-a07c-fc42086e9058︠
%md
**YOUR GUESS:**




︠e629780c-5939-4a7b-9319-cd4f80702690︠
# Now compute a few unit groups around 10^6...

for d in [10^6..10^6+30]:
    if is_fundamental_discriminant(d):
        K = QuadraticField(d)
        h = K.class_number()
        r = K.unit_group()
        print d,  h, K(r.gens()[1]), len(str(K(r.gens()[1])))

1000001 94 a - 1000 8
1000005 16 400*a - 400001 14
1000009 2 131731949169813620780494186441161519380499070292337127649862339072134473632943312341556427087242012746554344673825760769467027686849333793343573810259395964748208549412412741483305692130001329633333075281230217829758932842702222304410486454502872773917486912406002804131674004323997815240928957626474869524072489439933974669117852985595180255385222655903404415553912917*a - 131732541962251104958446508559172816749261629408940182763560517514222068343817199785105625290874393837094399323109737911421592462396723534045889424720529630685543080360611534097841219959333070939538951538511319148737851845962392555633023124925488987124645062359938683753459021275756736866491223186853581759003980384726828407476716628178359185793252137729757690522499660200 746
1000012 2 41123402834921837870290889177958718884124444591911833557498261135595584478978738725391444130934178789152426933664974621934415588*a + 41123649574598630591583714336691868613830878946541858267371195420109136915684531110440767105657021944273503325465327913778044075423 264
1000013 8 1685951787/2*a - 1685962745651/2 32
1000021 7 12293007234809307263859343923621025809587177775240*a + 12293136310707627853019613935137096708751236402803551 108
1000024 1 347121172028397111000264260761608605069465095316017295911429606584845410378224305009883888892995104976871760425584284900804105008974130298141502791422236593541207869750198114645644006269458057102716898816700736423761223775034284481451950375634034504301106659493340471238138921505522819446735909359325347289607451084480910433633981180862625982088447977778865897394993782401494091066881137264424646364251106749793414310530046692337871461169612926283202425894617896560846388113349488357653993683937786087401346847613331126189642870669550811215828711683749791649790436265601306743501*a + 347125337457469027287745689662972760345544834222367562907669606641350892228136000156285122845908854230729772041247803012696416976282686267874684031713444721324778198053022472516175702053601802436505162160742135650376695328875843578042616762902655645797317053038046138886726148316329573260125666590352293862599541087009221242937246210401414642640943774579749316053175406018987801826918469112042524366401211323978922451754091326121971729246091529228061034428126229272407626061597428876982538832962538721783461434878954100057814490791353412988265584980139118970602025860974423349964805 1166
1000028 1 8497077702440779803522608502830121489040461543213198369151120463547892179900606718680353742415560882683763431381763139118405/2*a - 4248598330347956008693629155162520293113477409154625942344341995309833271071799816343848179328024200573420185290947838981771224 258
1000029 2 805329166990891356807575099159106441516553744294576773765893859560353696621041054169656544601262562797528672020816756107/2*a + 805340844179153723603397899227221733707047041322897535209753784444579006718151499531416428119115987864889570254222596283445/2 252


︠4620f07f-9f42-4967-a378-832bf7cecee3i︠
%md
## 3. Unit Groups using Sage

I think John Cremona mostly wrote a lot of the [unit group code in Sage](https://github.com/sagemath/sage/blame/master/src/sage/rings/number_field/unit_group.py).  Of course, the real deep work is done by [PARI/GP](http://pari.math.u-bordeaux.fr/).

The [Sage reference manual](http://doc.sagemath.org/html/en/reference/number_fields/sage/rings/number_field/unit_group.html) explains things pretty nicely. Here's an example:

3. Unit Groups using Sage

I think John Cremona mostly wrote a lot of the unit group code in Sage. Of course, the real deep work is done by PARI/GP.

The Sage reference manual explains things pretty nicely. Here's an example:

# from yesterday
K.<a> = NumberField(x^4 + x + 2016)
K

Number Field in a with defining polynomial x^4 + x + 2016

# Exercise: from this, what is the structure of U_K/tor?
K.signature()

(0, 2)

%time U = K.unit_group()

Error in lines 1-1
Traceback (most recent call last):
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 5965, in unit_group
    U = UnitGroup(self,proof)
  File "sage/misc/classcall_metaclass.pyx", line 326, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (/projects/sage/sage-6.10/src/build/cythonized/sage/misc/classcall_metaclass.c:1239)
    return cls.classcall(cls, *args, **kwds)
  File "sage/misc/cachefunc.pyx", line 1304, in sage.misc.cachefunc.WeakCachedFunction.__call__ (/projects/sage/sage-6.10/src/build/cythonized/sage/misc/cachefunc.c:8470)
    w = self.f(*args, **kwds)
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/structure/unique_representation.py", line 1021, in __classcall__
    instance = typecall(cls, *args, **options)
  File "sage/misc/classcall_metaclass.pyx", line 493, in sage.misc.classcall_metaclass.typecall (/projects/sage/sage-6.10/src/build/cythonized/sage/misc/classcall_metaclass.c:1665)
    return (<PyTypeObject*>type).tp_call(cls, args, kwds)
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/unit_group.py", line 257, in __init__
    pK = K.pari_bnf(proof)
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 3608, in pari_bnf
    if bnf.bnfcertify() != 1:
  File "sage/libs/pari/gen.pyx", line 6705, in sage.libs.pari.gen.gen.bnfcertify (/projects/sage/sage-6.10/src/build/cythonized/sage/libs/pari/gen.c:129797)
    pari_catch_sig_on()
  File "sage/ext/interrupt/interrupt.pyx", line 88, in sage.ext.interrupt.interrupt.sig_raise_exception (/projects/sage/sage-6.10/src/build/cythonized/sage/ext/interrupt/interrupt.c:924)
    raise KeyboardInterrupt
KeyboardInterrupt

CPU time: 52.17 s, Wall time: 76.29 s

proof.number_field(False)

%time U = K.unit_group()  # why do you think this is so fast after doing the above?

CPU time: 0.00 s, Wall time: 0.00 s

Unit group with structure C2 x Z of Number Field in a with defining polynomial x^4 + x + 2016

U.torsion_generator()

u0

K(U.torsion_generator())

-1

# brace yourself!
U.fundamental_units()

[289435621835716557955558482373469197475107090829993567943663573405130530791279730410306274989252159506935736858405161642225710357492197014107680856156727551956745294340767181098830384755394919325268917544786135982965474710309776369211672518851289116702381167147678538599560722106641985961341653023539142805457735172531109558103467696639431993842876860546379924484790477436509140877532069243940811872296121973271821574099499716951974830985638867746710292890439440828546868995940192775087412387388030339710599831367019522608993211763795617277098752462066077060358960610647865454974961386256554410989107727275510065261703995196166006852755982987961835595429805062129006762210589180165757929954609610955422801743630664810357326904995792141472227665812742356398135440251129079957986070241262755815518192546163439617912277895295496769781885810394615223145664059644259269944902060991942788781165051515049333759995709549543114651566024477652705617268925078776382350342612744882081845253871770949376187938163098925169688819591577972808581052671727904411350542058293636702357865726558067792241203270891720986819868315498887118395459755847110081244670168394134486162919443476049408522593756789681544113758031656999481324191234800484111250960821620052863487509882277814869837801685827219338233981321305821348813396068581055296904305233478903836039700091831940377234341090979137119196802110513554615125434413498828019527806457699880721085025089558117458367851602305620806928428004043112752357667218815668887590718574874151185335543709868606059316033818177396851603186431265456599416297701929562150273141502736024068436912813115590752992764237747804670041904136208613600116303575817937317078096224104688700840208859599891044660979410899983147684312117117052113993194760526357580920454627129232799326187913291827540879778585884374745467384180561678344551532795931133615644658182914582372984018400815563655315861220043171355490610994151275702381150571540440686231437072532120667114089012084096248458324038778357042000389187184572877329513090256701120612063506210034033534401509526062901345919835080402613226977633064105070640640128985973496738413117230160851076941850872378972953623706882182563761251997470423076701684536406636173449613246571541466976626510974423975060218746167620805387884878932940521097629091256628156239962241490992163226294654489157237960459745668623307110400189840347190959494856743909832520561766908212582824233040848242523055288681508625622759670187280644412044929611702488143629921857110789187783727678576729283575791245384007034370273638229124414982055637488960339283581168453453075467617070710058575025225091469034626747470199165524099177581781924880029554862380250088990355494229732763779922686388660746380013572338834997852123812984662741787389889958997680934008750432078834891986248791032071656466515712964533207182728746597022310474862582488975599000487012556508822836756271234636442956122050229288243645042315968532127701222945266353855032316882184571792539721400486201514974561864591911669911867892824816959669536944356337070141205062057850207366174741626138827440308525354702968158779628508419611420619218375663719668659913939998838929167434689687053920870955609192606082766392727758300177571944651366099972967540171238374699557300688058648110957329223760614623135752770292454173587769533055994463900652807805048439781281525359049438508941032942335724646070028120126064044734877499874517590627480957367435228558981008501446007220827342799466739006467931315158170808565209155651292304323320753441978768115437268732481047527390852762959245110765332177231247181460320140494930181540502962806397255831367075775766207300270592029482046488388825417855626384132368986588685958102498117165233145389647324887970256329715624820463333721496017838215618030806262221036889111910265987599026350658172925514329281642019363991212453592680672472053851260651149095864627702090495107847487088294720449949191123222920602267910540377920257063553061783418768792660471829811121542191713383023478222720686594432363690746623478222796920978829330468144176003788744498475099823798897672879239962432977622681055842738144009298641535040289061392698048040385174334939895700010386183219405630125104125760643060787677529514611822093843053410482371500729192228327949740914908183739603202972022336455090409820063742805114477282660514447063219397741302310017941144254400163027254702325853523020371797216723115334303228356982000691973578305681866134522484162747996358327178384464659886781448773701550159222662411965044041286397237329994657901472060286995883641005920220321346533931244111152980556649724390009714296105691734064644372383995663947468301436622056524501070557436502955487272815890798961295965387065106121268974488751502835383884519546458924544252870328915630049926439682679588116290176747950955040290510652393391809887849445365714068980357762934262158915677368027493060777347830125869289682255906012366998543350402331054951700182456202646971577307191506857160722669754321541677785983702768037600085729832004354658363181104313149545058992221787081269084055695926730916010166596369277416441663906609980289490483811862968246528616723681882131208327602235666849821224830229579084518114087331984152135666624564874746217763079946248071494842128550313630246371148440012866181422984297283609146917823275122772677284031145231746920547503809232164378317274975802024261915824898654115950262219398571732370029146684141343458758668156012190987918846499218163102346713625328590414991776681659316889895278203955615787777007566538753582563013664679886265301006218451697089697188291810702893262042782448535820046013744680760263823044430163548824321278294494034396893197899742095485888947425737905146073283971251146531852310808061424734796427069177263100022532840138968931396483391159000887439872892735619891715102982182926414175071268802653214946801201734090429046604162663473501295851575789561185799300390253043967130731100725150714299214999434463254847186663290015622168963677529863706366295897140371350148819108191382051578472783748603805349959015698010990254231485995995334709258901968029140382092947255706120340113460589585916374826091324405766054351356160148184969605657133856689622933551405162718915193758541200946410029586540819648540440582799793766140439907735267258966142076084652874450374604598469769323000746759011548983007705794768478462238744406207961896894396532726748914561214417731436160421809769692549307256536716967478088322039381408732658585708057233378831752914867671543751579013828283873366009371449880455745986261353003512515022583208726833668511167357483070146206283296847994511988251244680420816071585632685669922414815103072057703904326698223199891969004275344722332810276651393874853499241102631045724653643911116133513168746588891860156961657463530301613545376696040161417869216905829694088898206245972039765891139639070344694094449800646190283463314805149649520973753718496086806711646578751771984667595273734043322816193452745545307353489766838797130641987170385040564245650666983151641650025374578266537539077226211118415394846395192125842725870382354197312606030891755306717001793326371367045141718289606625188835114296641501241114809458640496497614366999706390991775306430870416240822473890382135928533872923456279314770797746768046557534877404054714551978049392971129874578687172750655081412224851426912398177794309915789622855884556243037345183419965787154856449545897503798386182134947705934062487473640895328223734107087578444480310098349476072406337557911299136521098551712261386421215456945337508634450304759785969902971932054462330412476793099930882455210249944211307100857346554066533589072171751397291189477690346423667753520695747114501368204711291549531919893835843436261410597231472055970881531169426963963553260251093382390203462648011730429288213589438896648253798557629566377940378734284622825157217986900247280387479042041536815185121314581817588470971430966539255788251147648520708042922995484848852981710908201422328481854389020806302865160095068049685583659029547207112936954127794823800762114363057607187997255612061992459520635661568477433685047774894564985934234068346109471441444034270421848171348712100133886838835581285172707465917252735721975429075804685633102529703658833862417540455507679787715482543242929123165003323327586775277809549266847487496404097751047335425052728982726050403481569281642751864623468512293243274644395936118375991743001054543158246888204441135599032242653802879386797724659438767276593296176072400535212520044450114138717613607406399796157700869264165796908817999799882349894319939493035388799817209308693662085107669785068273761353477040546300196973611779249254680775047459687779369710066825323632271146000609635545219965327548180057953327671233088236220992456103622502591178098486342954544238627755962501979719916673870959686902818541592551718366131321807619350891728908386459699705990751790013338732484041282897144346451885793997747329183473608489120711202458571828373864992892008800239497715815569938576285502728281226621208956875852668750357628166972401392195733338087583505936577700185935926680247262621752317431177051539902724410623730676540530578636671048459490681901720733859410562548764724996345015291991804279260447852615079084878509408163477247852041939200600678618488077754421146962127848957041059119674324632870984441575738445034111698134116719974438584057945828755441437041548985162692281301092351251082195033766025977902468582350923218162573209547229226077372159540697278795340652614837952491084242890432114118690833520657601103765784503416905750929895851207065888177803751570764367672314566577274281562287442633916258210413214794015033524487108164015880552106606246366842121177423275691291948045067323216070804305413365772475404994081027599593593271866845874204490872629099084406413302213702775447190685439046937533074752387211591582617706161977655688073490828940000561778011200468630290612668266568726331604826833587842005463109115390938949923789781694481423297272167335626799682664843336381861474510474951159842428875838144682719447292635160006337370037021536214540165851406524473187816982907977484531708624245544400166156333451223561249866011231725436688958757900089396547330194004132591659572021040023514411822557818351052955475323392433480063977807841152077389777644832549104034907391402937614063008397138757845068500917548240891665705217598969557001158080593610039840957449206675197039791821353574100479866259923046156573120304692773470639181261685940858786558290315725305713146927184638561798169118644534177739243188372142274335077022401770066748793555222382915529622357945283865135934648078561415318329795904399971471267693999785592440710427595053415563014181449625414358455499930418428799554774346722989292833153717891748738510786637130110754790928472484801096673679730904627262229767339390311997128660131402474745542292735369223680120609497203081021071335387762665762231584776985355151021364583645604326571546832925901294176952230481448302026302232401084040483180249421079154307972074415146011636867915123375458491359560376616073816598235447870139849741927050008226731577613982932952102752061211974608592056563602960931848554342855937627813129568699940304313776040252285769844835445080173399039965773793536186842872000657861947108182680620752061042193867989304339419204763811224729216011292445017620180608761557202598793491927951455574396461589242022339467206768738281864805023817710482030270086860196082686048716187231435305625011719074631951358151477391915951763960810876083075616905159305862018009646552653575565263700001450660926404136159407055703408744549618536751382978839840564338571973120125066839732080852841674830821106149472685538174910120305999373072197403869161922829145386821024479070965578059923524379111368411579442596084668171770106523048266593608900877030942148321948791264110117782716404562713023153454611219063747783158634530383211076458458558982291204689834498680574139563864232878984782644226479285265211678541756761860931870165264645702033377156933613922581422999188814051470994027547799893141308805260263576851320936273490145124532155629282923038123498095076654301938282179300104234377165969814541093057918628069003967719977056867493738186061203727147115541050912755252329731817054424457333661343193356482397729079728795938877615578426069852450240438810447924965471864358839989450907048464871422179232055612170272365946331105774209161570371671003377562975463011621871967323726524121086028668779986761283980154501043616462185168787277436801363809890663252268905446232107997755141145469337141973287917980488687057294362312212873022354771191035532419943733983468491988371309275313877384220259844642228008127792583209704276841035594451106332667599458239937099546692312541929410734197050232951237347930579282732690604653959470921903386089516540868510765478491386873329062954801693615490668512961997530781862354740651272983270505708299316244857361292854671670724271819604332378270258550343602979988366707977286718949930866352227729872679121777173381090407726981685031819166404131567862589428398426074256724516518374219173931470986564279934119014717424761897464501469733516193446813205157958586794653416643756798770716366676482682560224284340490779190321182024841976220488311536156249229503922066711533838026512954593153484408158305897422679679319054841137734326449118963181594816167387873335742170205147095747246260251085086913415837912281943896017889824128280363352432095037002042376849096935508426454633411445713264391193903600105324447248336043103538680387962365487196861613518488190559676654548237298998783261300172142238713305423715862078273205307401218129269384838857206307860183649093322891761517988552908108467377745910043282620177829914596456647481186832174121048850339375199826812128821634995493533810891028724334585646062549406315478122621150423291240862182900090971186902694252067182296352338296147787359852115769044325568456609866673987592192363697481275868453256378003420725962283646384004689006006337759327810060049886776320930614113262951257334703953494935029838770036755930946835927384398025046605992945884142347686937141481830219547181739224989260898167276090760169372425832118746369779927158418493241683081515823079619019290581335356137879290416238120826275046632525928496034698949969123673711017290853258668113746076013807935472801969259648921890854186273244375487183342885566148375174403768328578790373024279069484494263247015741427602628926248943498788501500169697783271469226498383429367002330901892561272976266064233438688048998971263632461717769107788303791152202991523000396105350051123393082072348655137937026698381193798025785466559579212461475947806807523889565526684078579713945001850596316111227303598875887186311974122358527618317347965070485673551414794180391352054207550155640638560476638501314117762417333494644797577299789235163981906019834733704491492127929325899173005580113376880947979823274071550625333915899602128234785674512910835325270991037231689843714006274585510780889933184074976151495141495197664756618987374223276932643845581892772854323058909149985077933959650540516686319698991044646982319471750250548600108317589081408409312413630551483706550946163343796686107990760474213548892424122961744034521538807652702857615288177880335979173330823160078652999807607339702998200931365154443840429125624605370314515634803399411858823450991115739445149277709512297381008486562247783407166011000815389803101579553962907034090296814281086563248705437235380513409460265900944514907488907321282881606398009345032253228229129475076717712074327563868539610154251037165791915999993731639656000879972548731368008972058143265484269594342598133138680225081708393911664824030765891877421761047799840451829806429401454358948308963489458619271184541878677045123629812839797399103002369088103819807142647577338920674361633823076767228983188369855439487483936340139654110940809465703453462741343637307492042539834576406695845051037827287870916962222264051215195933370660946076410579977506598666746305345625399020409275306305809449794416547674033018807669870982639946890302363465926339210628189382042619781199797183532592128039006443962355982477938745139529100072379091010399520680877051820928212522930991253331355461627725853197767879745666014383618083841927391380691031746798157484518660179638900296897619696999990404852700533910191900261629077007503627690432533569442467614733841731954243822689884314182436424777907461060712687705702655151272382435078192677306739379610863649677044636869640079791978346308990830810147441159510140455240042163851610015286762411730772804520130561202873509411736961760072833457824683844815855742755106714768041732862580226980478889001844889161339406749868430722674715166250208812548385792947620694253916498973322621347624405946718606908351211044880182033542959776537482797336203662809178517335867330912187452064838186193341186716139953036258014735651411813538946306852683978705421073171790817396170960878141166068555191711245002274695950983679977798734019123666321764634317254991228535589642679411353209822922475143145774670689003581005359424287474247097711306201276604425163006952739895238218593334873392177778048473919948228028441300321280976805698583477648177437118088574008769968788984491312547611288860179067459346113813645764936644876035724804057739831035517302286846773563152991970720440467487776820227776087174108806167488956145152057756266243685848781836728397913889331540150494221311533186291596137248388471903800723319503279568878612290960223951482068772167253954727624654774178423592504195962704480062621483219988143555464396290923105719947523061278280922282968792055130514175037576147710939063581856978936891014985803314265570063228283281564082842117714529826818433537386924653762175509755117424926277320841547779285266339436626056263555731711179015686005448535311759664486423645840599185945353921545710190835290609663737679457679283825589974740220619133561466871540337412445231897329234974486256901426058124650328666495018162486054023932643547536269471717453195872496489178079631125744429319173598461549899161709900736794677845977080300856292429122846282479996811714749675939217438314752485403538468702263848258059371512557746756359250070600741024260435101944602111881022603711330830467850296485448324645210553271645511257858092887763041023397152016751955351384910858177663616337856391665656371054663504204366283555150825473420663319208909341454942669235715050834895576404779118541069148345606126375563817381826019813183067096208494680743957147324110422535151251138592648991221015075130142759709165709454311016195219196206494624656133723294745830195917684040746249992946753935549428150477729983226044692531432110610258063025298253219572951412155332327675395011236628180331382922816740881359079674527890855389478502186824473932550366154240577796169851972268031625697192976494760560514240016180692458208531660620724068756176040772812775878865839162431746618592571877383162856643513801501470530168619767341456978335106219829450822926609098957640641779517666278906682577537452983388371915825906156012550698703032862657721076986061080838781391243453762217270729130405239361603479300440852857251260031562930581169093373739162976399307494780248936828003271322859817599051821041804696012390177763460126944870154936190955325473969709910022868752185296199193938942690289938128358244191346954144584814587221068748090955018363416690266705540390789514619978654587078539903843286865819418283364090452804447827202886312247621281712995782015181379497778203452068237222637016061990337709803228574262974700523120012557282323396263289630977993730296355788306246229739918870952403960578524183040720933584788188992340769326342356732905776575666292857570234725229419832991188258514487762896596744934566080624320293645684171606053449137991554547100524956432569045576467737265768847231624548029536907926963899710323342284542982296716638098785281519215956491974189531485289408308301099256148188687128373599769687881032946369227576386762163858424404404440407256926710503416354512256924717370159542589799707787645251876635146700463752563041475558307660989307185143850714759663432523988179822516217000287906293110559448128118342160781520520424369742944930405953261724937284451656042350848418541438785608129066654093570455446838397352839946820234363473013905005405740678742364513372576548270559849358594323589295989317168580826697285158714325104974370404901826409819116608927502973145579358471135479922141157688272381528596153681876152144165220585044809759083559139483743306272066170724742285715524378231743253656989058389286604479591151749783156279192869639795390099780490471206724081632190271497794645333458090477201886999162369270051377549514538162634610488644636941923678521203367986384469700089850642265786067238504715659821128464714590794548771675971992074138204729617616234768948889007496695610914684487123026528030795981058946309122543052911321646043536616976415482425823535903993660106682947140032860321161938747885594036451455179641035720966277227862436455255221687227771036198529977811467100121535193297244244830649207359565322754334934304977800940450865036685425507323996272985432075876794806280655790936767340248926127851931558214193405877414060837107487647625469222878204455884704536560800353874068156026306372183482701607459860144812815088478387678464099279318656098149331781499144815511520665081805851971590237688164794279583036293921919960927765127257506941577946259317330024028434330678279204235516766775675773560265680504662397805310865223083404022495131797050933656144578674441602844924794589807901451348934531912902256393228638395796179621248860633009480901634861212409984050262237741482292045676588691333058705766423602963678144071431705241725253835801072713068868419797123015282724236581099080820185602472874946190191886462913652943848744570439800025132190574717133969835236746732316682082815911211128314087015743855635130786688515519848359533761560568967529280908829506284857620361275437828139219015881418555805636522316040451965782834898250323279186575216880812577918432821846064462867920240160187898507088337743873385875437769365669557789388945794719842097175409513034917392770152221427272611197735131223726621441649319574259448248742218973101175954664279881770446702206176430093291737487252150467345327109720656212420961682964233825196084160563290647579109937502285714563753799651631163719320582777520232708202984208391801601806133408572467723716671819503338489319657614026723235850690875086060903335872228897128912005690849705477774980472711790563899979741289308471530420564680793610995828076586762522188357866548101186069302316437612367348317232906494691519574657119797051112619547604787586586766982068812990894893581292366228936863119435427570873822735298350715234180598309129658678023691573476575852100759382309537022999936493292165736035953000837747268695484931577355830420562352727021722775664814086941196354789160214110051793242265951269644755180841123152139518349982571931403827812601442048445478562237608853023804986955227154572612867292677887679168702718452287214593002352988882652884127799394406915707418229054805950730460338069937266620330172761424934511404306503874534197691586846473688946659415843998682317759963805990846627021662105523886966140435754126370208291086738287306263393114505184894343372675475634484278356065203337556490872959251290785311809272268494979730357314013831054738825071866342785170374235430974439247776351084583823551844554454666164388012912359570703988031138646824971419626303721906247860010887589739273806217574453848951178911208064753685743082266406475147306461897720683033356492499601652458750816929805034450195180780944497778454656553472954999105491418328212722025353764486083390618288719780939906202736934772122593839051548452517143181397717391104239003811215589777958839975379791653356268402703449823429499963903377212966354465163058890430005287248324225319800606201301243498867293116188420097355222890063843651184675273231682978547407716762379737146468416360063893979689459184934982570215345076512303547707023424423950389511388567185191754263444951722624753871876927907694890214394157189124786828936202328448627020013102880501571334959911850179442085636204878818530620252345758621480660881636088191001203891674139755892180762944205161456305045732620918335469683270591286419795376179568086659037305333150036526232960457755406832836331972041093598520774881165446894694990129344231943345390527738089549964715775010556924470432398264185158743858159756830980641382053469940411280427794921713739658429340031265524775287302992930207125874249831989021315298063453836923758003022653579377634315286468250638132034048095616623122513071231136785461516915034339596067833611386859667835373559234003995322484841780830268431180504805598371538227836479264216143419990766719012411788884998702634181564049276819367290671845020198524608893062485895278058345451996143951562848432837051239525834960379618449419693901809957499828427225335366253320309681757227594799119012832089174350186146326349136221396677001545734593298788262706978934740937114332103348541622073852984184603220715728101255226472590859671748536514063367588823964961637276303501935062120334630639329533847534918162465118497238565108364487042197725975178104172202829700863924953244230660270136214200105206689211601901134040042730965912315419909679654343547857443699490631186279131012882547961773372233793093025019683125268761679621035282680503886812503786807260131099247286414287253873026613461078358760024209790515445532440013442638730963533625098525994480222341510262173625144160417832346199172565725507805350895413656107364380399803443975367428398380941136096172522136138547841194515126697256990805705597959973047297382183749123817906843884742493094812320502532221329137448363159836405585382841802026368756319343227540464863869917230595836451096745706173871414025111358944599557183359398735388270422422353708959920091362832361077995319703693732622202937799144539519535408264804302933504391374619042750947034784551236861866207797339620990654522641856886551431138063432087305633778811136745546407659511117056772335486125194331612127838666518167216840274347530280608362751370652985447323506642592134284304238523312220239766651104329150237018363578576678757509553215399091515518499733849047973827969283022526641716810532192886993984205159489468312910154623927053634319005956806800536646884141948777665956282021099251192454568593949394874714087575702987561128028209463561670261375506166639715326088433348577748705161187834398037287298386236723360969632750669688428417032657321971700689151371701765305185652654508659208733776915267243686075936768352110996873293932324814731081407302276200184131262081543720749069840555862359608984667385357075020074842825354636581747102252968109361180271598283530832789816655220929023467260444770460625359526355353807364415676155105127586436515792620024511865450442026943670535063566597802754678972338584704191794418766042127616363007122817647965612016871645404173723111313509196591129206179115540428005369026103608092594539346539181485369372091814804483606979459958609506548867263282960017378085297575654141392192449993733082874587160079531823408352216593453696398474510841686275031595769594639572782788817692981258205751592570053289125276237338264325015684270197051745726095031086249365890595263510535919107861708483568841003924146272268893986050285398380932188091133662509388528421399941364395978982606719072089484949559076742640417986274823895094271128472161672383669005862257796987585986766342104333797733640603228152117632750337503539976068056978547149596282470154878297890369177727047215017984175071024232773108362152782003411945597158786123836713772639903686701879752749445805272309067078198618020495531813171478926256368729474166208124310219292839444722209129590633043022895974957500125123545198711812431372475993229864829448438923822264077247989941841938137805225479554634730443714778752399299219815663613770288532446474883188812326882942449695283810380640155771113352226740386786193186494626826151618283215263785645859766968438126768631583430442314451900588820126437903606022361499895901232307448142960981641589801316979466409490446145391857956342066502590419045586554505130758425774939598362673004897127792515218816854086103086730685751287842435721995329558997690793996682966418631463345432702562644670732222664871289497097576368335569494932869655720918837456601970601772978115185538528519324405710041343936910937716049865013222268434491815852081890234985533037162680713260169675246612848432322958490608516822984005762409246794733938881263377431603803289613718869944539454956274071251291387973501803426659496976190883568848399694383986792517078944609362347829369272124426422515448034789434137720133624110768986432700886215842610440730280441773084356655444098991004242114551043493290566016677712674981325907185093315759023185193291862233713444218293521542393122135490225283526422885938589694787656174075895905141395160463363525907560393102469897041134178566685866276048708952220690077836752457396158945202210008409899325169336151117679016314632854620770776016598443417737116713633296966666602732679041437456223259746273618686174536790050738074463657400058167703623190851913866333501271570201799912926570605769675221452628052472143900049336744704011038424630281777237368495710744371197607002919035574080055421332026691288398036018758814813530379813688358095238739670828403329944719693114744967463325095200316796987226671218104290152760376666228367284221619849296857684624720170493638862545285423787592067830575525583526825462003533433680076607113754025657369901686609058023352921365954274800241690496437754407563306550822294540954584393787485024315545492246504093495793712109437574048909103455922188761746783049723298124557997331219794130521144370993343951338892684749261282718706781483645869361010975172119191877773182076461596595499090713879761141940075455808742483887231013460424374615092653497692632017322818595588085156199931050372874493947006187908470527401676830404930744760536489827003994416731001870202532343977449480544333617203160672480694987053163858266010255060785915880495307867039082492407642128948198381224799214327336127826108663552261558418560425991915111244379286161890858632682282531025004721373517447398109786640222077575129494060179370311113780478038225765109681549744279843553529901038913716917624685880639695141185649973784691417538030760795428128263047820768509292822232474836437298564516838719669206316339463094203397609437701259178454830616593133066171177259599589226484957369256677442086820808679876751534321761758739511346543629178831261792966899709265920207168199977294632366254063356694625834879536825019433772090031943720098558988179492891472785599556075553074280316599656607370615914488915537914895442987273824026308238209894126898759232239479461734678413497172922452638882134774447092526590611660846573988159797954043013097168164075314214825872082900913316126287331335707930644218351220553735479950691615042739779094241862650225712565430151379739813269410179611724431439620178772252044483713408502119466720370412124030545118721688205426729213177143014541962474132149201630470687278658013204813824126071117708156399643451141082379358771662371755947623787718882984737319437342259531687556629148059148869430149818712175831363903399895805452830992878533571347522441204239049173458248979600174669259904806305307762091420884992778346216548173521923484228468892653593619600059001595222744863433369961250075000533498056084487845794144554001024819561733103010374516487949379581737621756755673979816073602160031621949826904891015448950184138901251756630999575602453758246900556822269684925156560999257681263113311002615922697918668957029544671483454356025440152440202764794830801103315143435997284191870765682731598910210964550512223240597556215556872635443260692278329269289888345657553718692918561467364959926588546860907349342472125987893225603824126766803846739161988949468908378941105018678460454646029560272714606671106173045446464335160935760294107402294352841518106665591737126907815256867646214928377015047118846857209729894272087132763761811501638790567846557876404282080483039458441163840142402142655911930326351215547829115008968781393768510530238608570001716416849732262883209124708815784594540628480380344771350085886769791920517286273120789575743222037342407994590975611018629624223636754377330707690458220450195432350121494026191092314721323484056089483786637849321950945422537949196279406529995027156152524906229681434131386282061293864064230023384208222340627834802626592731312328638271754192404818328522477299828297088685713270781808706087729564455667850642372216765806271853302484110505907928200905579247970027485160521740119111943050662973304297817402580072065344118793063008115998117856203125544275582598823200516817572230575992223894069962811275125892556638441482599855587731123253109639153962866027390422221000924211640972583388657768417126939269149955471026097916663019525807648538601625928072771165409801227998595367096220925076362325542348428413190308526796806993617004274669529737770512538825306852801017434739935013487849925039573989971468611969785515640003235547034348402295098285890661755352026513470470807742715625133226406534749684622802551793018672444345329161066590238479710871792509499405603244470386941641714812008182581535467712823529243293504237577146831038292709414939986025013462276368035733814238583511046660852434891340486600314065752607195441612359282531509244129700188263424649118158072740635208217888696143897963580358260560728711483787491840461750543943466775784262165792161301456206580035279339321891669652740237737599083521514953433862538721968030114422569623202983808109068521380450736507893177252714386893427598263171420878205040892464239520713682904709803221758234688921909727117012089237274549742876023143133931189816114956379314002227304950229901071028164717083628962128181769642939910078918172207479267839023680224031567488362248664377360725216385922349464260608730865558620784220987309987421724310113114823930258136776336074311739962529740383097177565281258696272481138074065659915740565529871064982408559959339020760784603537426838641454169975305810983217922828224921593773330267706445061564681910098059382445638338338166434446980752379188514191081403723953572723184026339962889508079678979809386075392856407826028821618964270918635689493555576581294313801907735915869167229631397571932809034433764250937798453759261527711384297040380117144206186348561376465828834311170267937719283019181616467908208167934235615202944270169039376987365198953723948236379753898717153621164866610080042921291929488459116777344489611332302712988073885844896499428974906651045180202192655643195029185732736806275334110077571362704966669049660871059357453187886373408052373806425716341567108527272151091872753927360569476219611965567863363308058340112824389371007627715676755989530831079071107273421784565278406056421008320274325319509637057139035060995636473787208006224024525297592959778738154223678206415064565653596797712328699617777170703605766086433912113545107062770784668987872648918703306969808320537986790375886528113070981753367373354572517198525634797396026053318575876889141429490882358952939289030831594003835340392805238138575815522332715226616880196345988851625256751300627466765680758434326564046915136010254583084735146984208412581251628071486162283449874685724994618145259333839843445657270746817759390547361964867701178670047634376873344072278031136417645425847349009643030368011969897886870647943284788827932067410131899082931388625436039520134024328132845709040205801989202442172458946790463654377692318005936559433498322309251087498545242516601381724329385368564906443074370383033392768076347660629489090630862371708898894752171722144536890668761681575143475485353494983749807123236718559699416846824797987754347324565009646972382733367932219105139870912563139319880831788470878702129890643012031074465144791894495084409982541322243489765677580637391379983282509882460373790814565319633064272395928224701887677513644438632541613317642675881370611130355305586592242530829141299330810895890749550314837269831541499806323652474816839139451751461362697985296814041950425154947215293822201107265782279674880196133543641269531527472741768005585253647918279420546067065600836810176689779565300377582051604292719390383578492697248152074339170234750219791326300238103402283129546381613985873371733566273604452625144217688703856790848017406208226752554641494022935742550156445747255772750769227080185575534516155105375515371559974490664943510098536482103846768125062405783029008488508301893829020997811200703414742602961651973910000556115523767088456694073050294163918472933902887605199559624484212754859200351853251418640887032861184302756440613819861583352958998665255008496543694595723448241652321281447322466738599985643977295466788587402442243121214189601790259594931894742080623436495010788995946860445956617459202301029085855065148237000302976041768528731589090972547816926927212029697797234302401475342380833731886022601565635902407038091271861833717701816481005185422072935446154159348930331161216629340365696688044335385567050477713377961154827880680022589694242393266980193072554616060457288592269220654910327496527592323482091979648055317305577581347296834577799303516391275993360025113828088052334651170344077504443028773790564515655117821340554974085908628454647500853575601218990758505601522141773495763768334330781989352666040065735963534452200420924150039244934457758716799122000336666171817733653152583239054437357289711606187487487951534639008333098936713765869571312554508873137443445394679029756239889621696295066970666747194349195031494274097838873779454448324941608779700772661029183185813933524408264707896994228271314986271073263498936672927666619222919536539730903288388165335684650189103930945953307457235765984363602429902080381658031276240995906215054514363103496873767218555918495219440454517714116955149327021519390700141941814863155027281702941804284116770477593930227173590227114498261077058343427496759735892915446858143793207052291365967586088220241546758308272640750194952617851145736201607211826522021273297114389330653654706120534399992125752002898939930341689038799372616272964324699273117401791101511683754255772897389389969615380812966223191265746612295676107794607141351163381916165435529896820775567345666451939178457032851123607096690679912080872969103749801908485703236598015242925387066934393142005837624190033617990269160545998800145765337011917090346552255983658553514449859680729500533294306012995038280640367269259455418872461988088146295832461448709391992667440601414012991250320378161577595947982613967668633435449750482567350696101737380686598844190145170462305225299778928213473875509511952349034924416412020593086243541330662699727387967490482639047539095560361429808422866121466495266040356936011882206865257899241980930924846022679974509286156992688930410462322332969327811048130259042403726640032193054914433695621121637742360956472785243316005250705646810647142889612926673615884402449628456109919322945069507726876635003573062404786324730919682926988190195549033478611825078058668960898606930180177507739376278821802212853843308184232785513586783559527056797409466911869441089114254862006342768015227506586949459784241152721693035409738770769231851345825443934774691403527605322744299431750022432504885396526588130090078684831316810374971429687152218569157407066995831308013700566308011149398767925681038209825097004602598254009457635018280532898740158627044301324306453201255622224819641465348390061723344069719220321027827989943635049995488282290085404097161389751072835638610524867725498556814105922044872229068292483138115822361893181180059642357347167153491429080318547434505042751253096243047866248192006003783178027406353112295021771563987156369901601814937606002967688266411363326099352196280284042328994799915713941047828358341680423009306898084897985748464276252297337610406172839779158576657101424069726012243767576762599838892999018997194962384088064226205279229329191598965693115617594692210961076198040900448669713092209741618235406728361657878477[...]

len(str(U.fundamental_units()))

175598

175598/2550.

68.8619607843137

Yep, a humble little "random" degree four polynomial... results in a rank 1 unit group whose generator would take over 50 pages to print out!

(Sometimes you can write down a solution without writing it out -- see http://www.math.leidenuniv.nl/~psh/ANTproc/01lenstra.pdf)

Exercise:

Make up a field and compute a unit group with structure $(\ZZ/2\ZZ) \times \ZZ \times \ZZ$ .


︠f2c3966d-96a5-455b-98cd-23580979b0ae︠

︠d2fbfdde-2f5d-41e4-b087-38d4a6b4d17f︠
︠3c5bf9c6-1a4e-4dc9-819e-dd444d9c1b71i︠
%md
By the way, unit groups work fine for relative number fields:

By the way, unit groups work fine for relative number fields:

K.<a,b> = NumberField([x^2 + 1, x^3 + 2])
K

Number Field in a with defining polynomial x^2 + 1 over its base field

K.unit_group().fundamental_units()

[-1/2*b^2*a - 1/2*b^2 - 1, (-1/2*b^2 + 1)*a - 1/2*b^2 - b]

# But they latex horribly...
show(K.unit_group())

\displaystyle

\mathrm{AbelianGroup}( 3, (4, 0, 0) )$$



︠49354d22-5520-4d40-acb7-6913b42f5e41︠

︠d76dcc36-08c8-42bb-af63-86bd9764cc32i︠
%md
## 4. $S$-unit groups

Given a finite set $S$ of primes of $R$, the $S$ unit group $U_{K,S}$ is the group of elements $x \in K$
such that $(x)$ is a product of primes in $S$.

4. $S$ -unit groups

Given a finite set $S$ of primes of $R$ , the $S$ unit group $U_{K,S}$ is the group of elements $x \in K$ such that $(x)$ is a product of primes in $S$ .

K.<a> = NumberField(x^2 - 2016)
U = K.unit_group()
U
U.fundamental_units()

Unit group with structure C2 x Z of Number Field in a with defining polynomial x^2 - 2016
[1/3*a + 15]

K.S_unit_group??

K.S_unit_group([2])   # this doesn't work. GRR - confusing design making proof= be first input...

Error in lines 1-1
Traceback (most recent call last):
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 6090, in S_unit_group
    U = UnitGroup(self,proof,S=S)
  File "sage/misc/classcall_metaclass.pyx", line 326, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (/projects/sage/sage-6.10/src/build/cythonized/sage/misc/classcall_metaclass.c:1239)
    return cls.classcall(cls, *args, **kwds)
  File "sage/misc/cachefunc.pyx", line 1302, in sage.misc.cachefunc.WeakCachedFunction.__call__ (/projects/sage/sage-6.10/src/build/cythonized/sage/misc/cachefunc.c:8392)
    return self.cache[k]
  File "sage/misc/weak_dict.pyx", line 878, in sage.misc.weak_dict.WeakValueDictionary.__getitem__ (/projects/sage/sage-6.10/src/build/cythonized/sage/misc/weak_dict.c:3834)
    cdef PyObject* wr = PyDict_GetItemWithError(self, k)
  File "sage/misc/weak_dict.pyx", line 149, in sage.misc.weak_dict.PyDict_GetItemWithError (/projects/sage/sage-6.10/src/build/cythonized/sage/misc/weak_dict.c:1126)
    ep = mp.ma_lookup(mp, <PyObject*><void*>key, PyObject_Hash(key))
TypeError: unhashable type: 'list'

K.S_unit_group(S=[2])   # unlik for the S class group, the elements have to generate prime ideals (this is good)

Error in lines 1-1
Traceback (most recent call last):
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 6073, in S_unit_group
    raise ValueError("Not all elements of %s are prime ideals"%(S,))
ValueError: Not all elements of (Fractional ideal (2),) are prime ideals

K.S_class_group([2])   # inconsistent with S_unit_group

Error in lines 1-1
Traceback (most recent call last):
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 3839, in S_class_group
    if all(P.is_principal() for P in S):
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 3839, in <genexpr>
    if all(P.is_principal() for P in S):
  File "sage/structure/element.pyx", line 420, in sage.structure.element.Element.__getattr__ (/projects/sage/sage-6.10/src/build/cythonized/sage/structure/element.c:4675)
    return getattr_from_other_class(self, P._abstract_element_class, name)
  File "sage/structure/misc.pyx", line 259, in sage.structure.misc.getattr_from_other_class (/projects/sage/sage-6.10/src/build/cythonized/sage/structure/misc.c:1771)
    raise dummy_attribute_error
AttributeError: 'sage.rings.integer.Integer' object has no attribute 'is_principal'

K.S_class_group([K.ideal(2)])   # inconsistent with S_unit_group (as mentioned above)

S-class group of order 1 of Number Field in a with defining polynomial x^2 - 2016

K.S_unit_group([K.ideal(2)])

Error in lines 1-1
Traceback (most recent call last):
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 6090, in S_unit_group
    U = UnitGroup(self,proof,S=S)
  File "sage/misc/classcall_metaclass.pyx", line 326, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (/projects/sage/sage-6.10/src/build/cythonized/sage/misc/classcall_metaclass.c:1239)
    return cls.classcall(cls, *args, **kwds)
  File "sage/misc/cachefunc.pyx", line 1302, in sage.misc.cachefunc.WeakCachedFunction.__call__ (/projects/sage/sage-6.10/src/build/cythonized/sage/misc/cachefunc.c:8392)
    return self.cache[k]
  File "sage/misc/weak_dict.pyx", line 878, in sage.misc.weak_dict.WeakValueDictionary.__getitem__ (/projects/sage/sage-6.10/src/build/cythonized/sage/misc/weak_dict.c:3834)
    cdef PyObject* wr = PyDict_GetItemWithError(self, k)
  File "sage/misc/weak_dict.pyx", line 149, in sage.misc.weak_dict.PyDict_GetItemWithError (/projects/sage/sage-6.10/src/build/cythonized/sage/misc/weak_dict.c:1126)
    ep = mp.ma_lookup(mp, <PyObject*><void*>key, PyObject_Hash(key))
TypeError: unhashable type: 'list'

US = K.S_unit_group(S=[K.factor(2)[0][0]])
US

S-unit group with structure C2 x Z x Z of Number Field in a with defining polynomial x^2 - 2016 with S = (Fractional ideal (1/12*a - 4),)

US.fundamental_units()

[1/3*a + 15, 1/12*a - 4]

for u in US.fundamental_units():
    print u.norm()

1
2

Exercise: make up a quadratic imaginary field $K$ and a set $S$ of prime ideals so that $U_{K,S}$ has rank $5$ .




︠cc2392e2-f071-468b-ba02-73512259b5b3︠