Opened 7 years ago
Closed 7 years ago
#19999 closed defect (fixed)
Exponential growth group: q^x and (q)^x are incomparable
Reported by:  Daniel Krenn  Owned by:  

Priority:  major  Milestone:  sage7.1 
Component:  asymptotic expansions  Keywords:  
Cc:  Benjamin Hackl, Clemens Heuberger  Merged in:  
Authors:  Benjamin Hackl  Reviewers:  Clemens Heuberger 
Report Upstream:  N/A  Work issues:  
Branch:  7881bb3 (Commits, GitHub, GitLab)  Commit:  7881bb3632dd40cb9add6ce3dfd3e6255e9f82be 
Dependencies:  Stopgaps: 
Description (last modified by )
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 nonlinear orders.
Change History (14)
comment:1 Changed 7 years ago by
comment:2 Changed 7 years ago by
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 followup: 4 Changed 7 years ago by
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.
 Making the (exponential growth) elements
(q)^x
andq^x
incomparable. (very simple)
 The other (equally simple) option would be to check for
l <= r and r <= l
(inle_lex
ofcombinat/posets/cartesian_product.py
) afterl == r
, and then returnFalse
(this means that the poset sees the two elements as incomparable, when actually, they very well are comparable). This introduces inconsistencies (behavior inQQ^x
vs.QQ^x * x^QQ
...) and should probably not be implemented.
 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 theAsymptoticRing
(which is, needless to say, bad).
Opinions?
comment:4 followup: 5 Changed 7 years ago by
Replying to behackl:
 Making the (exponential growth) elements
(q)^x
andq^x
incomparable. (very simple)
 The other (equally simple) option would be to check for
l <= r and r <= l
(inle_lex
ofcombinat/posets/cartesian_product.py
) afterl == r
, and then returnFalse
(this means that the poset sees the two elements as incomparable, when actually, they very well are comparable). This introduces inconsistencies (behavior inQQ^x
vs.QQ^x * x^QQ
...) and should probably not be implemented.
 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 theAsymptoticRing
(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 Changed 7 years ago by
Replying to behackl:
Replying to behackl:
 Making the (exponential growth) elements
(q)^x
andq^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 both2^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 7 years ago by
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
andq^x
incomparable is inconvenient, but no tragedy. (doubles the number ofO
terms, but I do not see other side effect)
comment:7 Changed 7 years ago by
(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 termsq^n n^k
)
 Forbidding negative bases in exponential growth groups.
(q)^n
can be modeled byq^n alpha
where alpha is a root ofalpha^21
, so the coefficient ring isZZ[alpha]/(alpha^21).
Inconvenient, but correct.
comment:8 followups: 9 10 Changed 7 years ago by
Authors:  → Benjamin Hackl 

Branch:  → u/behackl/expgrowthinfloop 
Commit:  → b506dff52dc57995e229f57144f280516c0b6b8b 
Status:  new → 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 followup: 11 Changed 7 years ago by
comment:10 Changed 7 years ago by
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)
?
comment:11 Changed 7 years ago by
Replying to dkrenn:
Replying to behackl:
c023a81 let (q)^x and q^x be incomparable
I believe the
other.base
inreturn 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 7 years ago by
Commit:  b506dff52dc57995e229f57144f280516c0b6b8b → 7881bb3632dd40cb9add6ce3dfd3e6255e9f82be 

comment:13 Changed 7 years ago by
Description:  modified (diff) 

Reviewers:  → Clemens Heuberger 
Status:  needs_review → positive_review 
Summary:  infinite recursion creating certain asymptotic expansion → Exponential growth group: q^x and (q)^x are incomparable 
LGTM.
comment:14 Changed 7 years ago by
Branch:  u/behackl/expgrowthinfloop → 7881bb3632dd40cb9add6ce3dfd3e6255e9f82be 

Resolution:  → fixed 
Status:  positive_review → closed 
It seems that there is a problem with the comparison in these cartesian products of growth groups.
This might also cause this behavior: