example where rsimp takes tooo long

[Ralf Hemmecke]

Hi Waldek,

I just wanted to report a case where rsimp takes too long, see
attachment. Maybe you have other examples, but this one appeared as part
of a real computation and it took me a while to figure out that rsimp
was to blame.

ResourceFunction["RadicalDenest"] from Mathematica also fails on that
example, but aborts after a certain period of time and gives back a
warning and the input expression.

BTW, clearly rsimp is not a full-blown user functon (yet), but if it
will be can you invent a name that sticks to the convention of having
full names (not abbreviations) in exported functions? Thank you.

Ralf

[Waldek Hebisch]

You give dependent roots above (177 = 59*3). After eliminating dependent
roots rsimp fails reasonably fast.

--
Waldek Hebisch

[Qian Yun]

Is there a command to find if an expression contains dependent roots?

- Qian

[Waldek Hebisch]

On Thu, Jul 11, 2024 at 12:10:07PM +0800, Qian Yun wrote:
> Is there a command to find if an expression contains dependent roots?

No. I am working on code to do this. General case requires
factoring, basically given a_1^{m_1}, ..., a_n^{m_n} where
m_i = n_i/d_i one tries to factor

x^{d_i} - a_i^{d_im_i}

over field generated by a_1^{m_1}, ..., a_{i-1}^{m_{i-1}}. If
this factors, then roots are dependent. OTOH if roots are properly
ordered, starting from simplest ones and at each stage polynomial
above is irreducible, than roots are independent. Note: one
needs to order roots because at each stage we need to know that
coefficients are independent which involves roots contanined
within a_1^{m_1}, ..., a_{i-1}^{m_{i-1}}.

In non-nested case there are simpler criteria. Theoretically the
simplest case is when base field contans appropriate roots of 1.
Then roots are independent if and only if a_1, ..., a_n are
multiplicatively independent. This can be checked using GCD
decomposition (implemented in MULDEP) and solving for exponents
over finite fields (I have a private code to do this). For example
for 3, 59, 177 we have

gcdDecomposition([3, 59, 177])

+1 0 1+
(51) [basis = [3, 59], transform = | |]
+0 1 1+
Type: Record(basis: Vector(Integer),transform: Matrix(Integer))

which tells you that 177 = 3*59. Of course corresponding equation
for exponents remain valid over finite fields, so root of the same
degree are dependent.

As I wrote, I have code which can detect such dependencies, but it
is important to produce "good" releation which is efficient for
elimination of dependencies. ATM I do not have this.

Note: In general we do not have roots of one in base field, then
criterion is given by theorem of Kneser: one considers group C
generated by roots modulo K^{*}, where K^{*} means multiplicative
group of the base fields. Kneser give the following conditions:
- any primitive root of 1 of prime degree contained in C must be
contained in K
- if C contains element of form 1 + \omega, where \omega is
primitive root of degree 4, then \omega is contained in K
If those conditions are satisfied, then degree of K(C) over K
is the same as index of K^{*} in C. In other words, if conditions
above are satisfied and radicands are multiplicatively independent,
then root are independent.

Kneser theorem works over rather general base fields (IIRC one
needs to assume that the field extention above is separable).
However, to use it effectively we need a method to find out
structure of C, which works well in case when K is a fraction
field of unique factorization ring. Of course rational numbers
are fraction field of integer, so they work as a base field.
One could also use rational numbers extended say by sqrt(2),
because corresponding ring has unique factorization. But
quite frequently algebraic extentions of integers fail to
have unique factorization, so simple metod fails and one needs
to go back to more expensive methods. Actually, one could
still play various tricks and when they work one would learn
if roots are dependent or not. But it is not clear which
tricks are worth doing.

--
Waldek Hebisch