checking if element of QQbar is in QQ

asked 2023-08-30 16:46:10 +0200

pg261 gravatar image

updated 2023-09-01 09:18:31 +0200

FrédéricC gravatar image

I would like to know the most efficient way of checking whether a given element x which is in QQbar actually is in QQ. The obvious way, that is asking x in QQ, does not always work: I have an example for which no answer is produced in several minutes, while x.degree() returns 18 very rapidly (so the element is certainly not in QQ).

Now I check x.degree() == 1, which is better, but on some examples it's still impossible to get a result in a reasonable time.

So I was wondering if anyone knew the very fastest way of obtaining the answer. (I have hundreds of thousands of elements of QQbar, and I need to know which of them are in QQ...)

Edit : I have tried sage_input(x) on one number, for which x.degree() seemed to take a very long time, and it does seem huge indeed, so perhaps the slowness is to be expected. It starts with

R.<y> = QQ[]
RIF512 = RealIntervalField(512)
RR512 = RealField(512)
v = QQbar.polynomial_root(AA.common_polynomial(y^108 + 68004*y^107 + 2292971238*y^106 + 51109008051132*y^105 + 847128116941893513*y^104 + 11136459321510129312480*y^103 + 120944040275150561015208000*y^102 + 1115986520588898954106738693008*y^101 + 8930751629479221489446680712620452*y^100 + 62961183935900437502097267939514726608*y^99 + 395885483512322567640638781252627560094624*y^98 + 2242347971328556178478595187470182159924789216*y^97 + 11535503038920918187810269479084854355202789445188*y^96 + 54269390660779471643106858668214098741160413790240672*y^95 + 234851336491050360542100170120549418461242139278483722168*y^94 + 939569003630299986203466023916881930753077854558405425462160*y^93 + 3490211835252670149247256331453220478710134468215140726060796886*y^92 + 12084161135860812171548648158452586929299853124159455422191690733976*y^91 + 39127445477819813897097350578201509138815301746365355947191046849364460*y^90 + 118834193635640440426978357924069602204303569995237870942404129179353253784*y^89 + 339431414930153584624175760167927030458787824395559124832063620982593184272454*y^88 + 914008587316979610169324522266393486470316485890810584833535325834539591845375520*y^87 + 2325255525666058595638903828649302942489341130326923157478734432098334031117961245944*y^86 + 5599623716538838373608322537699558868191795870505495950293442445752147110596713205528240*y^85 + 12787408442724754213893995626529393993223307270863826470321168842894295344087154710931173436*y^84 + 27735823920352260774281783498610617352976434668417400157621968451890240290776126525793240201904*y^83 + 57223330240259045601668613415140173457018450187726192871526041989829984449684813838150321898877344*y^82 + 112451025217727515917262506500621531971063596471347132306074496600842842754197965290920211733860360672*y^81 + 210740669967907045884992444493112155229328186358263361745499064895003334115907302697598496922153739227836*y^80 +

and goes on like that for so many hundreds of lines that I can't even count.

edit retag flag offensive close merge delete

Comments

How is the initial element in QQbar constructed? Since you have hundreds of thousands of them, you might add at least one of them as an example to the question statement.

rburing gravatar imagerburing ( 2023-08-30 17:52:17 +0200 )edit

They were obtained as rational points on a 0-dimensional variety (and then combined in various ways). I'm not sure how to exhibit one, short of saving it as a .sobj file and somehow attaching it to my question, if possible at all.

pg261 gravatar imagepg261 ( 2023-08-30 22:10:02 +0200 )edit

If x denotes your algebraic number, you can provide a way to reconstruct it by copying the output of:

sage: sage_input(x)
tmonteil gravatar imagetmonteil ( 2023-08-31 00:37:09 +0200 )edit

Just as an idea:

def is_in_QQ(x):
    try:
        QQ(x)
    except ValueError:
        return False
    return True

I don't know if it is any faster than x in QQ.

Max Alekseyev gravatar imageMax Alekseyev ( 2023-08-31 17:04:47 +0200 )edit

No miracles to be expected.

FrédéricC gravatar imageFrédéricC ( 2023-08-31 17:42:42 +0200 )edit
see more comments