Opened 4 years ago

Closed 4 years ago

#20020 closed enhancement (fixed)

asymptotic expansion generator: singularity analysis (log-type) without renormalization

Reported by: cheuberg Owned by:
Priority: major Milestone: sage-7.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 follow-up to #19969, also implement singularity analysis for (1-z)^(-alpha)*(log(1/(1-z))^beta, i.e., where the renormalizing factor 1/z, for integer beta.

Change History (12)

comment:1 Changed 4 years ago by cheuberg

  • Branch set to u/cheuberg/asy/singularity-generator-log-non-normalized

comment:2 Changed 4 years ago by cheuberg

  • Commit set to 9a6bb5d5203e37c74e8c32cf7f7a034821697561
  • Status changed from new to needs_review

Last 10 new commits:

cab11f4add generalized lambda-coefficients
20d095eimplement log-generator for beta integer > 0
a17ee52add name to file authors
2957212let ring work with given precision
c83baa8add doctests
f39f484Trac #19993: Arb: parse symbolic expressions
c1dd748Merge branch 'arb/parse-symbolic' into t/19969/asy/SA-generator-log
58c0386Trac #20020: Merge #19969
40c6e4fTrac #20020: singularity analysis (log-type) without renormalization
9a6bb5dTrac #20020: additional doctests

comment:3 Changed 4 years ago by git

  • Commit changed from 9a6bb5d5203e37c74e8c32cf7f7a034821697561 to 2b67cf075c1d227d7942fc02737b17b51ab661f5

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

9488698Trac 19969: remove parameter 'skip_constant_factor'
8938c97Trac #19969: unique code for all three cases
e769bdeTrac #19969: smaller coefficient rings if possible
feec36aTrac #19969: prefer coefficients as multiples of 1/Gamma(alpha)
7ad8f16Trac #19969: remove obsolete comment
e769804Trac #20020: merge latest version of #19969
af46608Trac #20020: remove skip_constant_factor
2b67cf0Trac #20020: increase precision of doctests

comment:4 Changed 4 years ago by cheuberg

  • Dependencies set to #19969

comment:5 Changed 4 years ago by dkrenn

  • Cc dkrenn added; dakrenn removed

comment:6 Changed 4 years ago by dkrenn

  • Branch changed from u/cheuberg/asy/singularity-generator-log-non-normalized to u/dkrenn/asy/singularity-generator-log-non-normalized

comment:7 Changed 4 years ago by git

  • Commit changed from 2b67cf075c1d227d7942fc02737b17b51ab661f5 to 931e5df85430b2f3d51750a0aac3dba730c2e13f

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

617e5bfTrac #19969: rewrite output of doctest so that comparison with Formula in Flajolet-Sedgewick is easier
456d8c3Trac #19969: correct whitespaces
b540598Trac #19969: add an additional doctest
931e5dfMerge branch 'u/dkrenn/asy/SA-generator-log' of git://trac.sagemath.org/sage into t/20020/asy/singularity-generator-log-non-normalized

comment:8 Changed 4 years ago by dkrenn

  • Commit changed from 2b67cf075c1d227d7942fc02737b17b51ab661f5 to 931e5df85430b2f3d51750a0aac3dba730c2e13f

Merged dependencies.


Last 10 new commits:

ebac5c2Trac #20043: add additional doctest to check parent
33f675dMerge branch 'u/dkrenn/asy/one-times-zero' of trac.sagemath.org:sage into t/19969/asy/SA-generator-log
98e1fc7Trac #20043: make error message more precise and flexibel
99d7292Merge branch 't/20043/asy/one-times-zero' into t/19969/asy/SA-generator-log
dd7dabfTrac #19969: fix doctest
1ed6067Merge branch 'u/dkrenn/asy/SA-generator-log' of trac.sagemath.org:sage into t/20020/asy/singularity-generator-log-non-normalized
617e5bfTrac #19969: rewrite output of doctest so that comparison with Formula in Flajolet-Sedgewick is easier
456d8c3Trac #19969: correct whitespaces
b540598Trac #19969: add an additional doctest
931e5dfMerge branch 'u/dkrenn/asy/SA-generator-log' of git://trac.sagemath.org/sage into t/20020/asy/singularity-generator-log-non-normalized

comment:9 Changed 4 years ago by git

  • Commit changed from 931e5df85430b2f3d51750a0aac3dba730c2e13f to 4462b276a506a8a3439a4cad07fa1df09a4d6892

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

4462b27Trac #20020: correct whitespaces

comment:10 follow-up: Changed 4 years ago by dkrenn

  • 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 4 years ago by cheuberg

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(1-z)/(1-z)
    """
    if k < 1:
        return 0
    else:
        return 1/k + H(k-1)
@cached_function
def a(k):
    """
    Coefficients of (-log(1-z))^2: differentiate GF once,
    obtain 2(-log(1-z))/(1-z), i.e., the harmonic numbers multiplied by 2.
    Shift and divide by k in order to take differntiation into account.
    """
    return 2*H(k-1)/k
@cached_function
def sum_a(k):
    """
    Summatory function of a(k), thus GF (-log(1-z))^2/(1-z).
    """
    if k<1:
        return 0
    else:
        return sum_a(k-1)+a(k)
@cached_function
def sum_sum_a(k):
    """
    Summatory function of sum_a(k), thus GF (-log(1-z))^2/(1-z)^2.
    """
    if k<1:
        return 0
    else:
        return sum_sum_a(k-1)+sum_a(k)
R.<z> = PowerSeriesRing(QQ, default_prec=100)
assert (log(1/(1-z)))^2 - sum(z^n*2*H(n-1)/n for n in range(1, 101)) == O(z^101)
assert (log(1/(1-z))/(1-z))^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 4 years ago by vbraun

  • Branch changed from u/dkrenn/asy/singularity-generator-log-non-normalized to 4462b276a506a8a3439a4cad07fa1df09a4d6892
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.