Exponential growth group: q^x and (-q)^x are incomparable

[dkrenn]

Using q^x for negative q leads to errors.

sage: 1 + (-1)^x + (1/2)^x

gives

RuntimeError: maximum recursion depth exceeded in __instancecheck__

But

sage: (-1)^x + (1/2)^x + 1
1 + (-1)^x + (1/2)^x

works.

Thus make q^x and (-q)^x incomparable; also making cartesian products of growth groups fit to have lexicographic products of non-linear orders.

CC: @behackl @cheuberg

Component: asymptotic expansions

Author: Benjamin Hackl

Branch/Commit: 7881bb3

Reviewer: Clemens Heuberger

Issue created by migration from https://trac.sagemath.org/ticket/19999

[behackl]

comment:1

It seems that there is a problem with the comparison in these cartesian products of growth groups.

This might also cause this behavior:

sage: (-1)^x + O(1/x)
O(x^(-1))

[behackl]

comment:2

I've tried to find the actual reason for this infinite loop. It turns out that the entire poset structure breaks down after inserting (-1)^x:

sage: ex = 1 + (-1)^x
sage: s = ex.summands; s
poset((-1)^x, 1)
sage: print s.repr_full()
poset((-1)^x, 1)
+-- (-1)^x
|   +-- predecessors:   1
|   +-- successors:   1
+-- null
|   +-- no predecessors
|   +-- successors:   1
+-- 1
|   +-- predecessors:   (-1)^x, null
|   +-- successors:   (-1)^x, oo
+-- oo
|   +-- predecessors:   1
|   +-- no successors

[behackl]

comment:3

The problem is that, in general, q^x and (-q)^x can be compared in the sense of

sage: q^x <= (-q)^x and (-q)^x <= q^x
True

For example, the same problem occurrs here:

sage: print (2^x + (-2)^x).summands.repr_full()
poset((-2)^x, 2^x)
+-- (-2)^x
|   +-- predecessors:   2^x
|   +-- successors:   2^x
+-- null
|   +-- no predecessors
|   +-- successors:   2^x
+-- 2^x
|   +-- predecessors:   (-2)^x, null
|   +-- successors:   (-2)^x, oo
+-- oo
|   +-- predecessors:   2^x
|   +-- no successors

I see three possibilities (well, two proper ones...) to fix this.

1. Making the (exponential growth) elements (-q)^x and q^x incomparable. (very simple)

2. The other (equally simple) option would be to check for l <= r and r <= l (in le_lex of combinat/posets/cartesian_product.py) after l == r, and then return False (this means that the poset sees the two elements as incomparable, when actually, they very well are comparable). This introduces inconsistencies (behavior in QQ^x vs. QQ^x * x^QQ...) and should probably not be implemented.

3. Refactoring parts of the MutablePoset such that it properly handles the case where some element can be the successor as well as the predecessor of another element simultanously. I'm not an expert regarding the code there, but I think that while this might be the "correct" solution, it is also the most complicated and it might also have a negative impact on the overall performance of the AsymptoticRing (which is, needless to say, bad).

Opinions?

[behackl]

comment:4

Replying to @behackl:

1. Making the (exponential growth) elements (-q)^x and q^x incomparable. (very simple)

2. The other (equally simple) option would be to check for l <= r and r <= l (in le_lex of combinat/posets/cartesian_product.py) after l == r, and then return False (this means that the poset sees the two elements as incomparable, when actually, they very well are comparable). This introduces inconsistencies (behavior in QQ^x vs. QQ^x * x^QQ...) and should probably not be implemented.

3. Refactoring parts of the MutablePoset such that it properly handles the case where some element can be the successor as well as the predecessor of another element simultanously. I'm not an expert regarding the code there, but I think that while this might be the "correct" solution, it is also the most complicated and it might also have a negative impact on the overall performance of the AsymptoticRing (which is, needless to say, bad).

For the sake of completeness: the fact that absorption does not work properly (O(2^x) should absorb both 2^x and (-2)^x) speaks against the first option.

[dkrenn]

comment:5

Replying to @behackl:

Replying to @behackl:

1. Making the (exponential growth) elements (-q)^x and q^x incomparable. (very simple)

+1 for 1., since then the elements really build a poset.

For the sake of completeness: the fact that absorption does not work properly (O(2^x) should absorb both 2^x and (-2)^x) speaks against the first option.

It's not that nice to have both terms; however, I don't see a good way to fix this at the moment.

[cheuberg]

comment:6

My impressions:

• Refactoring MutablePoset seems to be incorrect. We should make sure to have a poset when we call it a poset.

• Having (-q)^x and q^x incomparable is inconvenient, but no tragedy. (doubles the number of O terms, but I do not see other side effect)

[cheuberg]

comment:7

(continued; trac timeout)

• Having (-q)<= q^x would be fine, but not in the context of a cartesian product where the order would no longer be lexicographic (we'd need to compare |q|, k, sign(q) lexicographically for terms q^n n^k)

• Forbidding negative bases in exponential growth groups. (-q)^n can be modeled by q^n alpha where alpha is a root of alpha^2-1, so the coefficient ring is ZZ[alpha]/(alpha^2-1). Inconvenient, but correct.

[behackl]

Branch: u/behackl/exp-growth-inf-loop

[behackl]

comment:8

I forgot that the proposed refactoring of MutablePoset would result in a structure that does not resemble a poset any more; thanks for the hint.

Therefore, as the resulting increased number of required O-terms is just inconvenient I've implemented option 1.

---

New commits:

c023a81	let (-q)^x and q^x be incomparable
4f3c707	fix lexicographically ordered cartesian products
b506dff	add doctests

[behackl]

Commit: b506dff

[behackl]

Author: Benjamin Hackl

[dkrenn]

comment:9

Replying to @behackl:

4f3c707	fix lexicographically ordered cartesian products

Can you add a doctest there?

[dkrenn]

comment:10

Replying to @behackl:

c023a81	let (-q)^x and q^x be incomparable

I believe the -other.base in

return bool(abs(self.base) <= abs(other.base)) and \
       bool(self.base != -other.base)

is not general enough (you could have complex bases as well).
Why not

bool(abs(self.base) < abs(other.base)) or bool(self.base == other.base)

?

[behackl]

comment:11

Replying to @dkrenn:

Replying to @behackl:

c023a81	let (-q)^x and q^x be incomparable

I believe the -other.base in

return bool(abs(self.base) <= abs(other.base)) and \
       bool(self.base != -other.base)

is not general enough (you could have complex bases as well).
Why not

bool(abs(self.base) < abs(other.base)) or bool(self.base == other.base)

?

Yep, I was thinking of reals a bit too much; I'll change the statement.

[sagetrac-git]

Changed commit from b506dff to 7881bb3

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

09959af	improve doc of change in cartesian_produc.py
7881bb3	fix behavior of non-real bases too

[cheuberg]

comment:13

LGTM.

[cheuberg]

Reviewer: Clemens Heuberger

[vbraun]

Changed branch from u/behackl/exp-growth-inf-loop to 7881bb3