15
$\begingroup$

An algebraic number can be identified by its minimal polynomial together with isolating intervals with rational bounds for its real and imaginary parts. The degree of an algebraic number is the degree of its minimal polynomial. There are known algorithms that allow to easily compute sum and product of algebraic numbers in this representation, raise them to a rational power, extract real and imaginary parts, compare them, or evaluate them numerically to an arbitrary precision.

Is there an efficient algorithm that given an algebraic number $\alpha$ in this representation can decide if $\alpha$ can be represented as a sum or product of algebraic numbers of smaller degree?

$\endgroup$
  • 1
    $\begingroup$ By "an efficient algorithm" I mean an algorithm that runs in polynomial or quasi-polynomial time. $\endgroup$ – Vladimir Reshetnikov Feb 9 '16 at 18:18
  • 1
    $\begingroup$ Similar to math.stackexchange.com/q/155122: $\alpha = x + y$ if the minimal polynomial $R$ of $\alpha$ is a resulant $\mathrm{Res}_t(p(t), q(s-t)) = R(s)$, which is a set of $\mathrm{deg}(\alpha)$ polynomial equations in the integer coefficients of unknown polynomials $p$ and $q$ (minimal polynomials of $x,y$). The equations are easy to write down explicitly, but hard to solve (Groebner bases are hard, but maybe some approximate numerical method might work followed by rounding)? $\endgroup$ – Kirill Feb 12 '16 at 0:03
  • $\begingroup$ @Kirill Do you know of any CAS capable of solving this problem? $\endgroup$ – Vladimir Reshetnikov Feb 12 '16 at 17:18
  • 1
    $\begingroup$ I think all of them, like sage/Mathematica/Maple: all you need is symbolic polynomial root-finding (maybe with Groebner bases), like this (quick-and-dirty): gist.github.com/anonymous/478bd74a511575deba83 But those are not even close to polynomial-time. Finding small integer roots to multivariate polynomial systems is a known problem in cryptography (for trying to break RSA, Coppersmith algorithm), but I don't know of any implementations. I don't think my suggestion is efficient. $\endgroup$ – Kirill Feb 12 '16 at 17:59
  • $\begingroup$ @Kirill What's the purpose of coefSubstitutions? $\endgroup$ – Vladimir Reshetnikov Feb 12 '16 at 18:19
5
+300
$\begingroup$

As in https://mathoverflow.net/a/26859/10423, if your number $x$ ($p(x)=0$) is a sum of two algebraic numbers $y, z$, and $[\mathbb{Q}(y): \mathbb{Q}]$ and $[\mathbb{Q}(z): \mathbb{Q}]$ are relatively prime, we would have $$ \mathbb{Q}(x) = \mathbb{Q}(y, z). $$ To use this, we might look for subfields $\mathbb{Q}(y) \subset \mathbb{Q}(x) $ generated by particularly simple elements $y$ ($q(y)=0$). Then $x$ would satisfy a polynomial equation $r(x)=0$ of degree $\deg(x)/deg(y)$ whose coefficients are themselves polynomials in $y$.

This can be done in sage. Define the number field generated by your number in the comment:

t = var('t')
K.<x> = NumberField(t^6-12*t^5+54*t^4-116*t^3+132*t^2-120*t+92)

then loop through all subfields $\mathbb{Q}(y)$ generated by sage's K.optimized_subfields:

xValue = K.polynomial().real_roots()[0]
abstol, reltol = 1e-8, 1e-8
for K0 in K.optimized_subfields(0, name="y"):
    print "K0.<%s>:" % K0[0].gen(), K0[0].polynomial()
    L.<y,z> = K.relativize(K0[1])
    Lp.<w> = K0[0]["w"]
    # print "L: ", L
    Lrp = L.relative_polynomial();
    print "Lrp(x):", Lrp
    print "Lrp(w+z):", Lrp(w+z)
    if all([c.is_integer() for c in Lrp(w+z).coefficients()]):
        print "+++FOUND IT+++"
    print "Weight:", sum(c.global_height() for c in L.relative_polynomial().coefficients())
    # print "Heights:", (x.global_height(), y.global_height(), z.global_height())
    for emb in L.embeddings(ComplexField(200)):
        if abs(emb(y) - xValue) > abstol + reltol * abs(xValue): continue
        print "Embedding: %s: %s" % (z, emb(z))

This code considers, in turn, each subfield generated by $y$, and prints out the polynomials $q(y)\in\mathbb{Q}[y]$ and polynomial $r(x)\in\mathbb{Q}(y)[x]$, checking whether $r(x)$ can be written as a polynomial in $x-y=z$ with integer coefficients.

There are 12 subfields, snipping part of the output, some of the $y$'s are quite simple:

K0.<y3>: t^2 - 2
Lrp(x): x^3 + (-3*y3 - 6)*x^2 + (12*y3 + 18)*x - 14*y3 - 22
Lrp(w+z): w^3 - 6*w^2 + 12*w - 10
+++FOUND IT+++
Weight: 5.49783963670066
Embedding: y3:
-1.4142135623730950488016887242096980785696718753769480731767

$$ x = -\sqrt{2} + \mathrm{Root}_w(w^3-6w^2+12w-10) $$

K0.<y12>: t^6 - 2
Lrp(x): x - y12^3 - y12^2 - 2
Lrp(w+z): w - y12^3 - y12^2 + y12 - 2
Weight: 0.753631429508173
Embedding: y12:
-1.1224620483093729814335330496791795162324111106139867534404

$$ x = -2-y^2-y^3, \qquad y = -2^{1/6} $$

One might also check for all simple linear expressions $x = z + \lambda y$ by expanding $r(z+\lambda y)$ and checking whether all coefficients of $x^{\geq0}y^{>0}$ can be set to $0$ by a particular choice of $\lambda\in\mathbb{Z}$.

In my testing, I used the root near $-72.5006$ of

333030430968457063019646779392 - 23571307899875281888190922752 * x + 11325756868205077014516072448 * x^2 + 2880637967760945947804168192 * x^3 + 782990884159596744735457280 * x^4 + 40070228472035777844367360 * x^5 + 10282486223601703758015488 * x^6 + 192715657601424647782400 * x^7 + 21281445409747778775040 * x^8 - 2726796545369319832704 * x^9 - 83259682551880061952 * x^10 + 4445241731011609472 * x^11 + 1435507363311897496 * x^12 + 355547636535862912 * x^13 + 37061676308129376 * x^14 + 2332115507866947 * x^15 + 238642514161488 * x^16 + 13466590646101 * x^17 + 1032053823392 * x^18 + 55985523438 * x^19 + 2712768664 * x^20 + 109992986 * x^21 + 2837824 * x^22 + 41695 * x^23 + 320 * x^24 * x^25

which is

$$ 7 \mathrm{Root}_{x\approx-1.214}(8 + 3 x^3 + x^5) + 8 \mathrm{Root}_{x\approx-8.000}(2 + 8 x^4 + x^5). $$

So it works for $\deg(x)=25$, but in general it probably takes exponential time or worse, not polynomial. On the plus (?) side it generalizes the problem from looking for sums (not products, though) to looking for polynomial relations with algebraic coefficients.

$\endgroup$
  • $\begingroup$ Thank you, @Kirill. Unfortunately, I am not very familiar with sage. Any chance you can adapt this solution for Mathematica? $\endgroup$ – Vladimir Reshetnikov Feb 14 '16 at 0:08
  • $\begingroup$ @VladimirReshetnikov Sorry, I don't know if the vital functions (optimized_subfields and relativize) are implemented in Mathematica, which is why I used sage. Btw, if you just copy-paste the code into a sage notebook, it will run, and it's mostly just python anyway, so hopefully it's not too useless. I used these docs here: doc.sagemath.org/html/en/reference/number_fields/sage/rings/… $\endgroup$ – Kirill Feb 14 '16 at 0:18
2
$\begingroup$

Just a few comments to get the discussion started.

  1. I don't think that this problem for sums is very meaningful. Every element in ${\mathbb Q}(\sqrt{a},\sqrt{b})$ is a sum of three elements in proper subfields, and an element in ${\mathbb Q}(\sqrt[4]{m})$ is a sum of elements in proper subfields if and only if it is already an element of ${\mathbb Q}(\sqrt{m})$, with the exception of a few cases where the extension happens to be bicyclic.

  2. The problem is more interesting for products. Here the first idea would be writing the ideal $(\alpha)$ of the given element $\alpha$ as a product of prime ideals and then checking whether this product may be written as a product of ideals living in subfields. If $(\alpha)$ is a product of ideals living in subfields then several principal ideal test will show whether they are a product of elements from subfields, up to a unit upstairs. This reduces the problem to writing a unit as a product of units coming from subfields.

My guess is that the latter problem can indeed be solved efficiently by looking at all the real and complex embeddings of the units in the subfields.

$\endgroup$
  • $\begingroup$ Thanks. About (1): What do you mean by "not very meaningful"? Do you want to say there is a simple decision algorithm for this problem? $\endgroup$ – Vladimir Reshetnikov Feb 11 '16 at 19:06
  • $\begingroup$ Perhaps I should have said "not very interesting" in general. The interesting part of the question for me is whether certain numbers may be represented in a simpler way using elements of subfields, and in the case of sums this does not strike me as too interesting. $\endgroup$ – franz lemmermeyer Feb 11 '16 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.