Opened 5 years ago
Closed 5 years ago
#20020 closed enhancement (fixed)
asymptotic expansion generator: singularity analysis (logtype) without renormalization
Reported by:  cheuberg  Owned by:  

Priority:  major  Milestone:  sage7.1 
Component:  asymptotic expansions  Keywords:  
Cc:  behackl, dkrenn  Merged in:  
Authors:  Clemens Heuberger  Reviewers:  Daniel Krenn 
Report Upstream:  N/A  Work issues:  
Branch:  4462b27 (Commits)  Commit:  4462b276a506a8a3439a4cad07fa1df09a4d6892 
Dependencies:  #19969  Stopgaps: 
Description
As a followup to #19969, also implement singularity analysis for (1z)^(alpha)*(log(1/(1z))^beta
, i.e., where the renormalizing factor 1/z
, for integer beta.
Change History (12)
comment:1 Changed 5 years ago by
 Branch set to u/cheuberg/asy/singularitygeneratorlognonnormalized
comment:2 Changed 5 years ago by
 Commit set to 9a6bb5d5203e37c74e8c32cf7f7a034821697561
 Status changed from new to needs_review
comment:3 Changed 5 years ago by
 Commit changed from 9a6bb5d5203e37c74e8c32cf7f7a034821697561 to 2b67cf075c1d227d7942fc02737b17b51ab661f5
Branch pushed to git repo; I updated commit sha1. New commits:
9488698  Trac 19969: remove parameter 'skip_constant_factor'

8938c97  Trac #19969: unique code for all three cases

e769bde  Trac #19969: smaller coefficient rings if possible

feec36a  Trac #19969: prefer coefficients as multiples of 1/Gamma(alpha)

7ad8f16  Trac #19969: remove obsolete comment

e769804  Trac #20020: merge latest version of #19969

af46608  Trac #20020: remove skip_constant_factor

2b67cf0  Trac #20020: increase precision of doctests

comment:4 Changed 5 years ago by
 Dependencies set to #19969
comment:5 Changed 5 years ago by
 Cc dkrenn added; dakrenn removed
comment:6 Changed 5 years ago by
 Branch changed from u/cheuberg/asy/singularitygeneratorlognonnormalized to u/dkrenn/asy/singularitygeneratorlognonnormalized
comment:7 Changed 5 years ago by
 Commit changed from 2b67cf075c1d227d7942fc02737b17b51ab661f5 to 931e5df85430b2f3d51750a0aac3dba730c2e13f
Branch pushed to git repo; I updated commit sha1. New commits:
617e5bf  Trac #19969: rewrite output of doctest so that comparison with Formula in FlajoletSedgewick is easier

456d8c3  Trac #19969: correct whitespaces

b540598  Trac #19969: add an additional doctest

931e5df  Merge branch 'u/dkrenn/asy/SAgeneratorlog' of git://trac.sagemath.org/sage into t/20020/asy/singularitygeneratorlognonnormalized

comment:8 Changed 5 years ago by
 Commit changed from 2b67cf075c1d227d7942fc02737b17b51ab661f5 to 931e5df85430b2f3d51750a0aac3dba730c2e13f
Merged dependencies.
Last 10 new commits:
ebac5c2  Trac #20043: add additional doctest to check parent

33f675d  Merge branch 'u/dkrenn/asy/onetimeszero' of trac.sagemath.org:sage into t/19969/asy/SAgeneratorlog

98e1fc7  Trac #20043: make error message more precise and flexibel

99d7292  Merge branch 't/20043/asy/onetimeszero' into t/19969/asy/SAgeneratorlog

dd7dabf  Trac #19969: fix doctest

1ed6067  Merge branch 'u/dkrenn/asy/SAgeneratorlog' of trac.sagemath.org:sage into t/20020/asy/singularitygeneratorlognonnormalized

617e5bf  Trac #19969: rewrite output of doctest so that comparison with Formula in FlajoletSedgewick is easier

456d8c3  Trac #19969: correct whitespaces

b540598  Trac #19969: add an additional doctest

931e5df  Merge branch 'u/dkrenn/asy/SAgeneratorlog' of git://trac.sagemath.org/sage into t/20020/asy/singularitygeneratorlognonnormalized

comment:9 Changed 5 years ago by
 Commit changed from 931e5df85430b2f3d51750a0aac3dba730c2e13f to 4462b276a506a8a3439a4cad07fa1df09a4d6892
Branch pushed to git repo; I updated commit sha1. New commits:
4462b27  Trac #20020: correct whitespaces

comment:10 followup: ↓ 11 Changed 5 years ago by
 Reviewers set to Daniel Krenn
 Status changed from needs_review to positive_review
From the docstring:
sage: asymptotic_expansions._SingularityAnalysis_non_normalized_( ....: 'n', 1, alpha=2, beta=2, precision=4) / n log(n)^2 + (2*euler_gamma  2)*log(n)  2*euler_gamma + euler_gamma^2  1/6*pi^2 + 2 + n^(1)*log(n)^2 + O(n^(1)*log(n)) Be aware that the last result does *not* coincide with [FS2009]_, they do have a different error term.
I've checked this result and it (in particular, the term n^(1)*log(n)^2
) seems to be correct.
Apart from that, everything looks good.
comment:11 in reply to: ↑ 10 Changed 5 years ago by
Replying to dkrenn:
From the docstring:
sage: asymptotic_expansions._SingularityAnalysis_non_normalized_( ....: 'n', 1, alpha=2, beta=2, precision=4) / n log(n)^2 + (2*euler_gamma  2)*log(n)  2*euler_gamma + euler_gamma^2  1/6*pi^2 + 2 + n^(1)*log(n)^2 + O(n^(1)*log(n)) Be aware that the last result does *not* coincide with [FS2009]_, they do have a different error term.I've checked this result and it (in particular, the term
n^(1)*log(n)^2
) seems to be correct.
I have run numerical tests (via compare_with_values
) for
sage: asymptotic_expansions._SingularityAnalysis_non_normalized_( ....: 'n', 1, alpha=2, beta=2, precision=6) n*log(n)^2 + (2*euler_gamma  2)*n*log(n) + (2*euler_gamma + euler_gamma^2  1/6*pi^2 + 2)*n + log(n)^2 + (2*euler_gamma + 1)*log(n) + euler_gamma + euler_gamma^2  1/6*pi^2 + O(n^(1)*log(n)^2)
the result is
[(5000, 0.1171037?), (10000, 0.1069521?), (15000, 0.101778?), (20000, 0.098395?), (25000, 0.095920?), (30000, 0.093987?), (35000, 0.09242?), (40000, 0.09109?), (45000, 0.08995?), (50000, 0.08896?)]
which very much supports the additional term here (if it were not here, the renormalization would have multiplied with n
, which is clearly not occurring).
I therefore submitted this as an erratum at the book site.
For completeness, here is my code for testing.
@cached_function def H(k): """ Harmonic numbers. Generating function: log(1z)/(1z) """ if k < 1: return 0 else: return 1/k + H(k1) @cached_function def a(k): """ Coefficients of (log(1z))^2: differentiate GF once, obtain 2(log(1z))/(1z), i.e., the harmonic numbers multiplied by 2. Shift and divide by k in order to take differntiation into account. """ return 2*H(k1)/k @cached_function def sum_a(k): """ Summatory function of a(k), thus GF (log(1z))^2/(1z). """ if k<1: return 0 else: return sum_a(k1)+a(k) @cached_function def sum_sum_a(k): """ Summatory function of sum_a(k), thus GF (log(1z))^2/(1z)^2. """ if k<1: return 0 else: return sum_sum_a(k1)+sum_a(k) R.<z> = PowerSeriesRing(QQ, default_prec=100) assert (log(1/(1z)))^2  sum(z^n*2*H(n1)/n for n in range(1, 101)) == O(z^101) assert (log(1/(1z))/(1z))^2  sum(z^n*sum_sum_a(n) for n in range(1, 101)) == O(z^101) %time result = [sum_sum_a(_) > 0 for _ in range(100, 50001, 100)] ae = asymptotic_expansions._SingularityAnalysis_non_normalized_('n', 1, alpha=2, beta=2, precision=6); ae ae.compare_with_values('n', sum_sum_a, srange(5000, 50001, 5000))
comment:12 Changed 5 years ago by
 Branch changed from u/dkrenn/asy/singularitygeneratorlognonnormalized to 4462b276a506a8a3439a4cad07fa1df09a4d6892
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
add generalized lambdacoefficients
implement loggenerator for beta integer > 0
add name to file authors
let ring work with given precision
add doctests
Trac #19993: Arb: parse symbolic expressions
Merge branch 'arb/parsesymbolic' into t/19969/asy/SAgeneratorlog
Trac #20020: Merge #19969
Trac #20020: singularity analysis (logtype) without renormalization
Trac #20020: additional doctests