Opened 5 years ago

Closed 5 years ago

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

Reported by: Owned by: dkrenn major sage-7.1 asymptotic expansions behackl, cheuberg Benjamin Hackl Clemens Heuberger N/A 7881bb3 (Commits) 7881bb3632dd40cb9add6ce3dfd3e6255e9f82be

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.

### comment:1 Changed 5 years ago by behackl

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))
```

### comment:2 Changed 5 years ago by behackl

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
```

### comment:3 follow-up: ↓ 4 Changed 5 years ago by behackl

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)
1. 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.
1. 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?

### comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 5 years ago by behackl

1. Making the (exponential growth) elements `(-q)^x` and `q^x` incomparable. (very simple)
1. 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.
1. 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.

### comment:5 in reply to: ↑ 4 Changed 5 years ago by dkrenn

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.

### comment:6 Changed 5 years ago by cheuberg

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)

### comment:7 Changed 5 years ago by cheuberg

(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.

### comment:8 follow-ups: ↓ 9 ↓ 10 Changed 5 years ago by behackl

• Authors set to Benjamin Hackl
• Branch set to u/behackl/exp-growth-inf-loop
• Commit set to b506dff52dc57995e229f57144f280516c0b6b8b
• Status changed from new to needs_review

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`

### comment:9 in reply to: ↑ 8 ; follow-up: ↓ 11 Changed 5 years ago by dkrenn

 ​4f3c707 `fix lexicographically ordered cartesian products`

Can you add a doctest there?

### comment:10 in reply to: ↑ 8 Changed 5 years ago by dkrenn

 ​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)
```

?

### comment:11 in reply to: ↑ 9 Changed 5 years ago by 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.

### comment:12 Changed 5 years ago by git

• Commit changed from b506dff52dc57995e229f57144f280516c0b6b8b to 7881bb3632dd40cb9add6ce3dfd3e6255e9f82be

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`

### comment:13 Changed 5 years ago by cheuberg

• Description modified (diff)
• Reviewers set to Clemens Heuberger
• Status changed from needs_review to positive_review
• Summary changed from infinite recursion creating certain asymptotic expansion to Exponential growth group: q^x and (-q)^x are incomparable

LGTM.

### comment:14 Changed 5 years ago by vbraun

• Branch changed from u/behackl/exp-growth-inf-loop to 7881bb3632dd40cb9add6ce3dfd3e6255e9f82be
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.