Automated Sequence Asymptotics

Stephen Melczer
melczer.ca/FPSAC25

From Current Software to the Limits of Decidability

Automated Sequence Asymptotics

Stephen Melczer
melczer.ca/FPSAC25

From Current Software to the Limits of Decidability

Three Axioms

1. Life is hard

2. We all have problems

3. We can help each other

Rational

Fibonacci Numbers


$$\begin{aligned}F(z) &= \frac{1}{1-z-z^2} \\[+4mm]&= 1 + z + 2z + 3z + \cdots\end{aligned}$$


Encoding Sequences

Let \((f_n)=f_0,f_1,\dots\) have generating function

 

$$ F(z) = \sum_{n \geq 0}f_nz^n $$

 

Equations satisfied by \(F(z)\) are data structures for \(f_n\).

Rational

Algebraic

Catalan Numbers

 

$$\begin{aligned}F(z) &= \frac{1-\sqrt{1-4z}}{2z} \\[+4mm]&= 1 + z + 2z^2 + 5z^3 + \cdots\end{aligned}$$


 

Encoding Sequences

Let \((f_n)=f_0,f_1,\dots\) have generating function

 

$$ F(z) = \sum_{n \geq 0}f_nz^n $$

 

Equations satisfied by \(F(z)\) are data structures for \(f_n\).

Rational

Algebraic

5-ary Trees

 

$$F(z)=1+zF(z)^5$$
 

Encoding Sequences

Let \((f_n)=f_0,f_1,\dots\) have generating function

 

$$ F(z) = \sum_{n \geq 0}f_nz^n $$

 

Equations satisfied by \(F(z)\) are data structures for \(f_n\).

Rational

Algebraic

5-ary Trees

 

$$F(z)=1+zF(z)^5$$

 

$$F(0)=1$$


 

Encoding Sequences

Let \((f_n)=f_0,f_1,\dots\) have generating function

 

$$ F(z) = \sum_{n \geq 0}f_nz^n $$

 

Equations satisfied by \(F(z)\) are data structures for \(f_n\).

Rational

Algebraic

D-Finite

1234-Avoiding Permutations

 

$$\begin{aligned}&(9z^2 - 9z + 4)A(z) \\&+ z(27z - 5)(z - 1)A'(z) \\&+ z^2(9z - 1)(z - 1)A''(z)=4\end{aligned}$$
 

Encoding Sequences

Let \((f_n)=f_0,f_1,\dots\) have generating function

 

$$ F(z) = \sum_{n \geq 0}f_nz^n $$

 

Equations satisfied by \(F(z)\) are data structures for \(f_n\).

Rational

Algebraic

D-Finite

D-Algebraic

4-Colour Planar Triangulations

(Tutte 1982)

 

$$\begin{aligned}2z^2H''(z)&+5H(z)H''(z)\\&-3z^2H'(z)H''(z)=48z^2\end{aligned}$$


 

Encoding Sequences

Let \((f_n)=f_0,f_1,\dots\) have generating function

 

$$ F(z) = \sum_{n \geq 0}f_nz^n $$

 

Equations satisfied by \(F(z)\) are data structures for \(f_n\).

Rational

Algebraic

D-Finite

D-Algebraic

Encoding Sequences

Let \((f_n)=f_0,f_1,\dots\) have generating function

 

$$ F(z) = \sum_{n \geq 0}f_nz^n $$

 

Equations satisfied by \(F(z)\) are data structures for \(f_n\).

Rational

Algebraic

D-Finite

D-Algebraic

Automatic* to get asymptotics from encoding


 

Encoding Sequences

Let \((f_n)=f_0,f_1,\dots\) have generating function

 

$$ F(z) = \sum_{n \geq 0}f_nz^n $$

 

Equations satisfied by \(F(z)\) are data structures for \(f_n\).

Rational

Algebraic

D-Finite

D-Algebraic

Automatic* to get asymptotics from encoding


 

Encoding Sequences

Undecidable to get asymptotics from encoding


 

Let \((f_n)=f_0,f_1,\dots\) have generating function

 

$$ F(z) = \sum_{n \geq 0}f_nz^n $$

 

Equations satisfied by \(F(z)\) are data structures for \(f_n\).

Rational

Algebraic

D-Finite

D-Algebraic

Automatic* to get asymptotics from encoding


 

Encoding Sequences

Undecidable to get asymptotics from encoding


 

Decidability Open


 

Let \((f_n)=f_0,f_1,\dots\) have generating function

 

$$ F(z) = \sum_{n \geq 0}f_nz^n $$

 

Equations satisfied by \(F(z)\) are data structures for \(f_n\).

P-Recursive Sequences

\(F(z)\) is D-finite if and only if \(f_n\) is P-recursive

 

$$ c_r(n)f_{n+r} + \cdots + c_1(n)f_{n+1} + c_0(n)f_n = 0$$

 

It is automatic to convert D-finite \(F(z) \leftrightarrow\) P-recursive \(f_n\)

For 1234-Avoiding Permutations, we have 

 

$$ (n^2 + 8n + 16)a_{n + 2} - (10n^2 + 42n + 41) a_{n + 1} + (9n^2 + 18n + 9) a_n=0 $$

Encoding P-Recursions

We can encode a P-recursion using the Shift algebra consisting of polynomials in \(S_n\) and \(n\) such that \(S_n n = (n+1)S_n\)

The Shift algebra is implemented in the ore_algebra Sage package (Kauers, Jaroschek, Johansson, Mezzarobba, ...)

Such polynomials act on sequences via

 

$$n \cdot (f_n) = (nf_n) \qquad\qquad S_n \cdot (f_n) = (f_{n+1})$$

sage: [binomial(2*k,k) for k in range(10)]
> [1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620]

We can use P-recurrences to generate terms efficiently

# Algebraic Simplification
sage: Sn * n
> (n + 1)*Sn

ore_algebra

sage: rec.to_list([1],1001)[1000]
> 2048151626989489714335162502980825044396424887981397033820382637671748186202083755828932994182610206201464766319998023692415481798004524792018047549769261578563012896634320647148511523952516512277685886115395462561479073786684641544445336176137700738556738145896300713065104559595144798887462063687185145518285511731662762536637730846829322553890497438594814317550307837964443708100851637248274627914170166198837648408435414308177859470377465651884755146807496946749238030331018187232980096685674585602525499101181135253534658887941966653674904511306110096311906270342502293155911108976733963991149120
# Define the ring of shift operators
from ore_algebra import *
Ind.<n> = PolynomialRing(QQ); Shift.<Sn> = OreAlgebra(Ind)
sage: rec = (n + 1)*Sn - 4*n - 2 
sage: rec.to_list([1],10)
> [1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620]

This recovers that \(\displaystyle f_n = \binom{2n}{n}^2\) satisfies


 

$$ (n+1)^2f_{n+1} = 4(2n+1)^2f_n$$

sage: LST = [binomial(2*k,k)^2 for k in range(10)]
sage: LST
> [1, 4, 36, 400, 4900, 63504, 853776, 11778624, 165636900, 2363904400]

Guessing P-Recursions

You can heuristically solve many problems automatically

sage: guess(LST,Shift)
> (-n^2 - 2*n - 1)*Sn + 16*n^2 + 16*n + 4

Guessing can fail (because non-P-recursive or can't detect)

Walks in \(\mathbb{N}^2\)
 

A Recursion for NSEW Walks

sage: rec = guess([w(n) for n in range(50)], Shift)
sage: rec
> (-n^2 - 7*n - 12)*Sn^2 + (8*n + 20)*Sn + 16*n^2 + 48*n + 32

$$(n^2 - 7n - 12)w_{n+2} = (8n + 20)w_{n+1} + (16n^2 + 48n + 32)w_n$$

@CachedFunction 
def NSEW(i,j,n):
    if i<0 or j<0:               return 0
    elif n==0 and i==0 and j==0: return 1
    elif n==0:                   return 0
    else:                        return NSEW(i-1,j,n-1) + NSEW(i,j-1,n-1) + NSEW(i+1,j,n-1) + NSEW(i,j+1,n-1)
    
def w(n): return add([NSEW(i,j,n) for i in range(n+1) for j in range(n+1)])
sage: print([w(n) for n in range(50)])
> [1, 2, 6, 18, 60, 200, 700, 2450, 8820, 31752, 116424, 426888, 1585584, 5889312, 22084920, 82818450, 312869700, 1181952200, 4491418360, 17067389768, 65166397296, 248817153312, 953799087696, 3656229836168, 14062422446800, 54086240180000, 208618354980000, 804670797780000, 3111393751416000, 12030722505475200, 46619049708716400, 180648817621276050, 701342468412012900, 2722858995011344200, 10588896091710783000, 41179040356653045000, 160381525599596070000, 624643836545795220000, 2436110962528601358000, 9500832753861545296200, 37098489800792700680400, 144860769698333402656800, 566273917911666937658400, 2213616224563788938119200, 8661976530901782801336000, 33894690773093932700880000, 132754205527951236411780000, 519953971651142342612805000, 2038219568872477983042195600, 7989820709980113693525406752]

A Recursion for NSEW Walks

sage: rec = guess([w(n) for n in range(50)], Shift)
sage: rec
> (-n^2 - 7*n - 12)*Sn^2 + (8*n + 20)*Sn + 16*n^2 + 48*n + 32
@CachedFunction 
def NSEW(i,j,n):
    if i<0 or j<0:               return 0
    elif n==0 and i==0 and j==0: return 1
    elif n==0:                   return 0
    else:                        return NSEW(i-1,j,n-1) + NSEW(i,j-1,n-1) + NSEW(i+1,j,n-1) + NSEW(i,j+1,n-1)
    
def w(n): return add([NSEW(i,j,n) for i in range(n+1) for j in range(n+1)])
sage: print([w(n) for n in range(50)])
> [1, 2, 6, 18, 60, 200, 700, 2450, 8820, 31752, 116424, 426888, 1585584, 5889312, 22084920, 82818450, 312869700, 1181952200, 4491418360, 17067389768, 65166397296, 248817153312, 953799087696, 3656229836168, 14062422446800, 54086240180000, 208618354980000, 804670797780000, 3111393751416000, 12030722505475200, 46619049708716400, 180648817621276050, 701342468412012900, 2722858995011344200, 10588896091710783000, 41179040356653045000, 160381525599596070000, 624643836545795220000, 2436110962528601358000, 9500832753861545296200, 37098489800792700680400, 144860769698333402656800, 566273917911666937658400, 2213616224563788938119200, 8661976530901782801336000, 33894690773093932700880000, 132754205527951236411780000, 519953971651142342612805000, 2038219568872477983042195600, 7989820709980113693525406752]
sage: rec.to_list([1,2],10001)[10000]
> 50670858282363109450882533219385259116791651540860443528673788922006774660220135310076567190665877663227497610525216815179429196607949478468748915553152375749653361221125994945474312616551330785108050737125999149418854958253313760788500342419049188481548195955872633072687330360556794612654171049047211290195895456025776601166247232446800350871069853386548640043023875983206449827956660730234679224516097198566173345466226206912806717223010783200431450238527706770095844211019722426251793366950229386021807959129665280523676001799217267052478632201668733187252366897659520599167745871330655916268889673302362801838426936470105250077069488978931901731578966225360615394702370507089360895154065504666700587104090146760929313217351099539933140567655936082655681299170775905165644858153798348028777806004237453498378696816911713139361951420845865726262051994066992649399337204730904228221844913878475687608747835373198738775753219892796436372044015343546795120675525699408340634791486584741790183393940926197374390086240262042582449430164865375076395588987194887307089397649270689537745335338154495687649266578930031902333761475037829692896262498770271425885732492405179293598043990016563687030856649804387654971097362613794337373836758977008636389962314597843633841032627656883778165941274609560000697532642002468084422761062389106453298040757776956335230145086087940477772574847284044421930216720434474352316480161734848238858999080155279923745403969039709287324757374384790603827955162412914486192356944069511090856710652154351840737712407826739855920023546935106586288048874550544058030645736646311458039349446177051326282471808530466683266021672593133197720212428655043054923265926590161898310051318216499390497398335250477461051609836707468126913886101481598934742106657852699731888189564239891907789489387595933629511023855294225309530724153831204725610845446611721868550252331314924946613187780063083051507565617547894672537631737549784736674972279541063483949223264200625606706039828712278483054659143069314802127278851477493792811778662130623812809173425565895682617680056460930895805824229128847565677034763500222393161381064750618863217828812260915349862475933000389771680893042050268128860045233814678778637077487206805899903386504951131300864470272800477247571872568890190240016908973266215311690603721512336252665398854194841921860439222783673632616077033606607575370043713102948169716053281582965203407023561945150993709744512604377333301144388824916266835874668210698181716255976032541348206547750008530136869204301677672429389905688088653644511016402405401585335724639934248663821265735786168392178722012509566084394504530483792197688412603718620224251359211671714502661234813617049047607195898895544174790050741473619122076173331370750128697290361085322992294577671892941694190981025336380459290730894351927467743602393751326990874017063366861015440697608337084352431427879165441654071352622411659851787303492927467526541631418862696851291408996204862731208655648213122704707420619766998429620026069040101314252439416133459035634998364516344321380131632929427600636492953843012117944899150521534124992557855560152667137120679845929053246092174403895384774887585183239306578935477772888275355797760809213411669059334517690561448912884341338748976003574284847087139677085948236978096013857983915122178114425513639671301955992717368692696722002617877706796044652232811091148018991185443833802780876863228852630583041786532910920415578150634108377729235156670187459944174386750855702702405059132900343709662195965203464322999943189352428154278774622860021781931214415337513920463516570928183212496605732190431867813305085280817038220020281427675225994338382780074696444097375114844123823620570656852389281948091185933428624609951335857859486387875474645820101207557896825695213126067264165443422933555661660710279425253575794849141895541145040542894144217961490202799598146579492559083744185206673213882428611299744934247436059812001154919152511036104421799354988278541282082417763413709163100809584644234185712108984426813972363955877331014963814571870715876314298028919846532758435734435284393987172121796802034893803802665485861703351180728339878446281317115400174401961744161674081868686309708448750291674726622882548580616139292421774929961400288903489270461568890469792638480298432587664932171700961790244857182952310453101918294850607072924780368523036133216200764154694161058999645810707980661415273847856731758813121663661609473715027929225665799495419632092905431248660168254869543905446819393377854196395958215756806758051144880153459812938372953456551840063237594037992100684795808937022079510357115173988631043608823473835850180853207386201724496554609818426035210312142952482771541168708024442999685012931625713392233483938269706888945950703908003557170535033107512140782727252179099152178108839492991107741142445993771633863503705221693566188731578674005853050134504167663178597797801964857332669805161653877876642993855469907659008454967266837823861103074554243792696711249985133903641449804181113777278677465243089910796392779094226493655328349171611629505387451363516118666424673542658222517046786231402225793458159247896085710896374815324512470664548054885012039431380502790393737842000547485006282461867171417717003368433937083447993516493850892862173256394450222186575479376603742419525495589844723654393074201550114693434416962705347764401972194458098290779716403939350216414003627470203049211201083288411829874372704692246175461226439735585539879570902721252781444925714489447140199559870112189971578442953111869497236791173960853392385539764375378898274745897236228532519479891041539608227583914229414640560040801894033819396747796435418946937369866989187687235910422901506067920312998698309626368795857248638014481351836817855421838767557901909948438233464390236776468994528549482777553759453890570453460723232583360354139086158457684643045104378875875376069417188546249214473886405631857740880250266157853166591875046834017283606130015861687484068521700358094930116253971948774400

Automated Asymptotics


We can compute series expansions of an asymptotic basis

Thus, there exist \({\color{pink}\lambda_1},{\color{lightblue}\lambda_2} \in \mathbb{C}\) such that

So \(\displaystyle {\color{pink}w_n \sim \lambda_1 \cdot \frac{4^n}{n}}\) because \({\color{pink}\lambda_1\neq0}\)

The solutions of a P-recurrence form a \(\mathbb{C}\)-vector space

$$ w_n = {\color{pink}\lambda_1} \frac{4^n}{n}\left(1 - \frac{3}{2n} + \cdots\right) + {\color{lightblue}\lambda_2} \frac{(-4)^n}{n^2}\left(1 - \frac{9}{2n} + \cdots\right) $$

rec = (-n^2 - 7*n - 12)*Sn^2 + (8*n + 20)*Sn + 16*n^2 + 48*n + 32
show(rec.generalized_series_solutions(n=3))

$$ \left[4^{n}n^{-1}\Bigl(1 - \frac{3}{2} n^{-1} + \frac{19}{8} n^{-2} + O(n^{-3})\Bigr), \qquad (-4)^{n}n^{-3}\Bigl(1 - \frac{9}{2} n^{-1} + \frac{107}{8} n^{-2} + O(n^{-3})\Bigr)\right]$$

Automated Asymptotics


We can compute series expansions of an asymptotic basis

Thus, there exist \({\color{pink}\lambda_1},{\color{lightblue}\lambda_2} \in \mathbb{C}\) such that

The solutions of a P-recurrence form a \(\mathbb{C}\)-vector space

$$ w_n = {\color{pink}\lambda_1} \frac{4^n}{n}\left(1 - \frac{3}{2n} + \cdots\right) + {\color{lightblue}\lambda_2} \frac{(-4)^n}{n^2}\left(1 - \frac{9}{2n} + \cdots\right) $$

How do we prove \({\color{pink}\lambda_1 \neq 0}\) in general?

Back to GF.

rec = (-n^2 - 7*n - 12)*Sn^2 + (8*n + 20)*Sn + 16*n^2 + 48*n + 32
show(rec.generalized_series_solutions(n=3))

$$ \left[4^{n}n^{-1}\Bigl(1 - \frac{3}{2} n^{-1} + \frac{19}{8} n^{-2} + O(n^{-3})\Bigr), \qquad (-4)^{n}n^{-3}\Bigl(1 - \frac{9}{2} n^{-1} + \frac{107}{8} n^{-2} + O(n^{-3})\Bigr)\right]$$

Analytic Combinatorics

There is a strong link between the location and type of singularities of \(F(z)\) and the asymptotics of \(f_n\)

$$[z^n]\frac{1}{(1-2z)^r} \sim 2^n \cdot \frac{n^{r-1}}{(r-1)!} \qquad (r \in \mathbb{N}_{>0}) $$

$$ [z^n]\frac{1}{1-4z} = 4^n \qquad\qquad [z^n]\frac{1}{1-2z} = 2^n$$

$$[z^n]\frac{1}{(1-2z)(1-3z)} = 3^{n+1} - 2^{n+1} $$

$$ [z^n]\frac{1}{1-4z} = 4^n \qquad\qquad [z^n]\frac{1}{1-2z} = 2^n$$

$$[z^n]\frac{1}{(1-2z)(1-3z)} = 3^{n+1} - 2^{n+1} $$

$$[z^n]\frac{1-\sqrt{1-4z}}{2z} \sim 4^n \cdot \frac{n^{-3/2}}{\sqrt{\pi}} $$

Analytic Combinatorics

There is a strong link between the location and type of singularities of \(F(z)\) and the asymptotics of \(f_n\)

There is a strong link between the location and type of singularities of \(F(z)\) and the asymptotics of \(f_n\)

 

Each singularity gives an asymptotic contribution

 

 

There are known formulas for different types of singularities

 

$$(1-\rho z)^\alpha \left(\log \frac{1}{1-\rho z}\right)^\beta \;+\; \cdots \quad\Rightarrow\quad \rho^n \cdot \frac{n^{-\alpha-1}}{\Gamma(-\alpha)}(\log n)^\beta \;+\; \cdots$$

Analytic Combinatorics

A.<n> = AsymptoticRing('n^QQ * QQ^n', coefficient_ring=SR)
def f1(t): return (1-sqrt(1-4*t))/(2*t)
  
show(A.coefficients_of_generating_function(function=f1,
                                           singularities=(1/4),
                                           precision=4))

$$ \frac{1}{\sqrt{\pi}} n^{-\frac{3}{2}} 4^{n} - \frac{9}{8 \, \sqrt{\pi}} n^{-\frac{5}{2}} 4^{n} + \frac{145}{128 \, \sqrt{\pi}} n^{-\frac{7}{2}} 4^{n} - \frac{1155}{1024 \, \sqrt{\pi}} n^{-\frac{9}{2}} 4^{n} + O\!\left(n^{-5} 4^{n}\right) $$

Can compute first 30 terms in the expansion in ~1 second

Analytic Combinatorics

There is a strong link between the location and type of singularities of \(F(z)\) and the asymptotics of \(f_n\)

Analytic Combinatorics

There is a strong link between the location and type of singularities of \(F(z)\) and the asymptotics of \(f_n\)

 

To analyze \(f_n\)

     1. Find singularities of \(F(z)\) closest to the origin

     2. Find leading terms in the series expansions of \(F\)

     3. Add corresponding contributions

GOAL: Do this automatically from algebraic/differential eq.

Encoding D-Finite Equations

# Define the ring of differential operators
sage: Pols.<z> = PolynomialRing(QQ); Diff.<Dz> = OreAlgebra(Pols)
sage: Dz * z
> z*Dz + 1

We can encode a D-finite equation using the Weyl algebra 
consisting of polynomials in \(D_z\) and \(z\) such that \(D_z z = zD_z + 1\)

 

Such polynomials act on sequences via
 

$$z \cdot F(z) = zF(z) \qquad\qquad D_z \cdot F(z) = F'(z)$$

P-Recursive to D-finite

sage: rec.to_D(Diff)
> (16*z^4 - z^2)*Dz^4 + (192*z^3 + 8*z^2 - 8*z)*Dz^3 + (608*z^2 + 44*z - 12)*Dz^2 + (512*z + 40)*Dz + 64

We can also guess D-finite equations directly

We can convert between P-recurrences and D-finite equations

sage: deq = guess([w(n) for n in range(50)],Diff)
sage: deq
> (16*z^4 - z^2)*Dz^3 + (128*z^3 + 8*z^2 - 6*z)*Dz^2 + (224*z^2 + 28*z - 6)*Dz + 64*z + 12

So our walk generating function (very likely) satisfies

$$z^2(4z - 1)(4z + 1)W'''(z) + \cdots + 4(16z + 3)W(z)=0$$

Returning to our quadrant walks

P-Recursive to D-finite

sage: rec.to_D(Diff)
> (16*z^4 - z^2)*Dz^4 + (192*z^3 + 8*z^2 - 8*z)*Dz^3 + (608*z^2 + 44*z - 12)*Dz^2 + (512*z + 40)*Dz + 64

We can also guess D-finite equations directly

We can convert between P-recurrences and D-finite equations

sage: deq = guess([w(n) for n in range(50)],Diff)
sage: deq
> (16*z^4 - z^2)*Dz^3 + (128*z^3 + 8*z^2 - 6*z)*Dz^2 + (224*z^2 + 28*z - 6)*Dz + 64*z + 12

So our walk generating function (very likely) satisfies

$${\color{pink}z^2(4z - 1)(4z + 1)}W'''(z) + \cdots + 4(16z + 3)W(z)=0$$

Returning to our quadrant walks

P-Recursive to D-finite

sage: rec.to_D(Diff)
> (16*z^4 - z^2)*Dz^4 + (192*z^3 + 8*z^2 - 8*z)*Dz^3 + (608*z^2 + 44*z - 12)*Dz^2 + (512*z + 40)*Dz + 64

We can also guess D-finite equations directly

We can convert between P-recurrences and D-finite equations

sage: deq = guess([w(n) for n in range(50)],Diff)
sage: deq
> (16*z^4 - z^2)*Dz^3 + (128*z^3 + 8*z^2 - 6*z)*Dz^2 + (224*z^2 + 28*z - 6)*Dz + 64*z + 12

Returning to our quadrant walks

$${\color{pink}z^2(4z - 1)(4z + 1)=0}$$

Any singularity of \(W(z)\) must satisfy

D-Finite Expansions

The solutions of a D-finite equation form a \(\mathbb{C}\)-vector space


We can compute expansions of a basis around any point

D-Finite Expansions

sage: deq.local_basis_expansions(0)
> [z^(-2) - 4*z^(-1)*log(z) - 8*log(z) - 16*z*log(z) - 8*z - 48*z^2*log(z) - 28*z^2 - 144*z^3*log(z) - 96*z^3,
   z^(-1),
   1 + 2*z + 6*z^2 + 18*z^3]

The solutions of a D-finite equation form a \(\mathbb{C}\)-vector space

There exist constants \({\color{lightblue}\alpha_1},{\color{lightblue}\alpha_2},{\color{lightblue}\alpha_3} \in \mathbb{C}\) such that

$$W(z) = {\color{lightblue}\alpha_1}{\Big(}z^{-2} + \cdots{\Big)} +  {\color{lightblue}\alpha_2}{\Big(}z^{-1} + \cdots{\Big)} +  {\color{lightblue}\alpha_3}{\Big(}1 + \cdots{\Big)}$$


We can compute expansions of a basis around \(z=0\)

D-Finite Expansions

The solutions of a D-finite equation form a \(\mathbb{C}\)-vector space


We can compute expansions of a basis around \({\color{lightgreen}z=1}\)

There exist constants \({\color{lightgreen}\beta_1},{\color{lightgreen}\beta_2},{\color{lightgreen}\beta_3} \in \mathbb{C}\) such that

$$W(z) = {\color{lightgreen}\beta_1}{\Big(}1 + \cdots{\Big)} +  {\color{lightgreen}\beta_2}{\Big(}(z-1) + \cdots{\Big)} +  {\color{lightgreen}\beta_3}{\Big(}(z-1)^2 + \cdots{\Big)}$$

As expected \(W(z)\) analytic at \(z=1\)

sage: deq.local_basis_expansions(1)
> [1 - 38/45*(z - 1)^3 + 568/225*(z - 1)^4 - 86132/16875*(z - 1)^5,
   (z - 1) - 41/15*(z - 1)^3 + 541/75*(z - 1)^4 - 76484/5625*(z - 1)^5,
   (z - 1)^2 - 26/9*(z - 1)^3 + 256/45*(z - 1)^4 - 32039/3375*(z - 1)^5]

D-Finite Expansions

The solutions of a D-finite equation form a \(\mathbb{C}\)-vector space


We can compute expansions of a basis around \({\color{pink}z=1/4}\)

There exist constants \({\color{pink}\gamma_1},{\color{pink}\gamma_2},{\color{pink}\gamma_3} \in \mathbb{C}\) such that

$$W(z) = {\color{pink}\gamma_1}{\Big(}\log(z-1/4) + \cdots{\Big)} +  {\color{pink}\gamma_2}{\Big(}1 + \cdots{\Big)} +  {\color{pink}\gamma_3}{\Big(}(z-1/4) + \cdots{\Big)}$$

What is \({\color{pink}\gamma_1}\)?

sage: deq.local_basis_expansions(1/4)
> [log(z - 1/4) - 6*(z - 1/4)*log(z - 1/4) + 31*(z - 1/4)^2*log(z - 1/4) - 150*(z - 1/4)^3*log(z - 1/4) - 2/3*(z - 1/4)^3 + 2797/4*(z - 1/4)^4*log(z - 1/4) + 55/8*(z - 1/4)^4 - 6363/2*(z - 1/4)^5*log(z - 1/4) - 2869/60*(z - 1/4)^5,
   1 - 14*(z - 1/4)^2 + 108*(z - 1/4)^3 - 1261/2*(z - 1/4)^4 + 3291*(z - 1/4)^5,
   (z - 1/4) - 15/2*(z - 1/4)^2 + 43*(z - 1/4)^3 - 1773/8*(z - 1/4)^4 + 4315/4*(z - 1/4)^5]

Connection Coefficients

We have

$$\begin{aligned}W(z) &= {\color{lightblue}\alpha_1}{\Big(}z^{-2} + \cdots{\Big)} \hspace{0.54in} +  {\color{lightblue}\alpha_2}{\Big(}z^{-1} + \cdots{\Big)} +  {\color{lightblue}\alpha_3}{\Big(}1 + \cdots{\Big)} \\[+4mm] &={\color{pink}\gamma_1}{\Big(}\log(z-1/4) + \cdots{\Big)} +  {\color{pink}\gamma_2}{\Big(}1 + \cdots{\Big)} \hspace{0.15in}+  {\color{pink}\gamma_3}{\Big(}(z-1/4) + \cdots{\Big)} \end{aligned}$$

By counting walks we can compute

$$W(z) = 1 + 2z + 8z^2 + 16z^3 + 60z^4 + \cdots$$
so \(({\color{lightblue}\alpha_1},{\color{lightblue}\alpha_2},{\color{lightblue}\alpha_3})=({\color{lightblue}0},{\color{lightblue}0},{\color{lightblue}1})\)

Numeric analytic continuation: Numerically compute change of basis matrix from \(({\color{lightblue}\alpha_1},{\color{lightblue}\alpha_2},{\color{lightblue}\alpha_3})\) to \(({\color{pink}\gamma_1},{\color{pink}\gamma_2},{\color{pink}\gamma_3})\)

Connection Coefficients

Using ore_algebra we can get 1000 digits in a few seconds!

Thus \(\displaystyle W(z) = {\color{pink}(-1.27324\dots)}\log(z-1/4) + \cdots\)

sage: ini = vector([0,0,1])
sage: bas = deq.numerical_transition_matrix([0,1/4],1e-5) * ini
sage: bas
> ([-1.27324 +/- 1.82e-6] + [+/- 1.87e-12]*I, 
   [-2.39070 +/- 6.34e-6] + [4.00000  +/- 3.82e-6]*I, 
   [12.8907  +/- 5.22e-5] + [-24.0000 +/- 3.06e-5]*I)
sage: loc = deq.local_basis_expansions(1/4,2)
sage: add([a*b for [a,b] in zip(bas,loc)])
> ([-1.273 +/- 1.82e-6] + [+/- 1.87e-12]*I)         *log(z - 1/4) 
+ ([7.63   +/- 4.06e-5] + [+/- 1.1e-11]*I)*(z - 1/4)*log(z-1/4) 
+ ([-2.391 +/- 6.34e-6] + [4.00000  +/- 3.82e-6]*I) *1 
+ ([12.89  +/- 5.22e-5] + [-24.0000 +/- 3.06e-5]*I) *(z - 1/4)

Connection Coefficients

Using ore_algebra we can get 1000 digits in a few seconds!

sage: ini = vector([0,0,1])
sage: bas = deq.numerical_transition_matrix([0,1/4],1e-5) * ini
sage: bas
> ([-1.27324 +/- 1.82e-6] + [+/- 1.87e-12]*I, 
   [-2.39070 +/- 6.34e-6] + [4.00000  +/- 3.82e-6]*I, 
   [12.8907  +/- 5.22e-5] + [-24.0000 +/- 3.06e-5]*I)

And so \(\displaystyle w_n \sim {\color{pink}(1.27324\dots)} \cdot \frac{4^n}{n}\)

sage: loc = deq.local_basis_expansions(1/4,2)
sage: add([a*b for [a,b] in zip(bas,loc)])
> ([-1.273 +/- 1.82e-6] + [+/- 1.87e-12]*I)         *log(z - 1/4) 
+ ([7.63   +/- 4.06e-5] + [+/- 1.1e-11]*I)*(z - 1/4)*log(z-1/4) 
+ ([-2.391 +/- 6.34e-6] + [4.00000  +/- 3.82e-6]*I) *1 
+ ([12.89  +/- 5.22e-5] + [-24.0000 +/- 3.06e-5]*I) *(z - 1/4)

Automating Everything

Dong, M., Mezzarobba (2024)
Algorithm for asymptotics with bounded error

sage: from ore_algebra.analytic.singularity_analysis import *
sage: bound_coefficients(deq, [1, 2, 6], order=2, prec=20)
sage: from ore_algebra.analytic.singularity_analysis import *
sage: bound_coefficients(deq, [1, 2, 6], order=2, prec=20)
> 1.00000*4^n   
* (([1.2732  +/- 4.39e-5] + [+/- 2.04e-18]*I) * n^(-1) 
+ ([-1.9099  +/- 5.60e-5] + [+/- 3.06e-18]*I) * n^(-2) 
+ B([1503.38 +/- 3.05e-3]*n^(-3)*log(n), n >= 7))

Automating Everything

Dong, M., Mezzarobba (2024)
Algorithm for asymptotics with bounded error

Thus 

 

 

when \(n \geq 7\)

$$\begin{aligned}w_n \in \frac{4^{n}}{n} \cdot \biggl( &\left[1.27 \pm 4.39 \cdot 10^{-5}\right]+ \left[-1.91 \pm 5.60 \cdot 10^{-5}\right] \frac{1}{n} + \left[1503.38\pm 3.05 \cdot 10^{-3}\right] \frac{\log^2 n}{n^2} \biggr)\end{aligned}$$

@CachedFunction 
def NSEW(i,j,n):
    if i<0 or j<0:               return 0
    elif n==0 and i==0 and j==0: return 1
    elif n==0:                   return 0
    else:                        return NSEW(i-1,j,n-1) + NSEW(i,j-1,n-1) + NSEW(i+1,j,n-1) + NSEW(i,j+1,n-1)
def w(n): return add([NSEW(i,j,n) for i in range(n+1) for j in range(n+1)])

from ore_algebra import *
from ore_algebra.analytic.singularity_analysis import *
Pols.<z> = PolynomialRing(QQ); Diff.<Dz> = OreAlgebra(Pols);

deq = guess([w(n) for n in range(50)],Diff)
bound_coefficients(deq, [w(n) for n in range(3)])
1.00*4^n*(   
  ([1.27323954473516  +/- 3.09e-15] + [+/- 1.21e-30]*I) * n^(-1) 
+ ([-1.90985931710274 +/- 4.63e-15] + [+/- 1.81e-30]*I) * n^(-2) 
+ ([3.02394391874601  +/- 6.05e-15] + [+/- 6.46e-30]*I) * n^(-3) 
+ [0.318309886183791  +/- 7.53e-16] * (e^(I*arg(-1)))^n * n^(-3)
+ B([3432.030228663511+/- 9.35e-13] * n^(-4)*log(n), n >= 9))

Automatic Positivity Proofs

Yu and Chen (2020): The genus one Canham model for 

biomembrane shape has a unique solution if a P-recursive sequence \((d_n)\) has all positive terms.

M. and Mezzarobba (2022): This sequence has all positive terms

Yu and Chen (2020) - Michalet and Bensimon (1995)

sage: seqini = [72, 1932, 31248, 790101/2, 17208645/4, 338898609/8, 1551478257/4]
sage: deq = (8388593*z^2*(3*z^4 - 164*z^3 + 370*z^2 - 164*z + 3)*(z + 1)^2*(z^2 - 6*z + 1)^2*(z - 1)^3*Dz^3 + 8388593*z*(z + 1)*(z^2 - 6*z + 1)*(66*z^8 - 3943*z^7 + 18981*z^6 - 16759*z^5 - 30383*z^4 + 47123*z^3 - 17577*z^2 + 971*z - 15)*(z - 1)^2*Dz^2 + 16777186*(z - 1)*(210*z^12 - 13761*z^11 + 101088*z^10 - 178437*z^9 - 248334*z^8 + 930590*z^7 - 446064*z^6 - 694834*z^5 + 794998*z^4 - 267421*z^3 + 24144*z^2 - 649*z + 6)*Dz + 6341776308*z^12 - 427012938072*z^11 + 2435594423178*z^10 - 2400915979716*z^9 - 10724094731502*z^8 + 26272536406048*z^7 - 8496738740956*z^6 - 30570113263064*z^5 + 39394376229112*z^4 - 19173572139496*z^3 + 3825886272626*z^2 - 170758199108*z + 2701126946)

sage: bound_coefficients(deq, seqini, order=5, prec=20, n0=50)
> 1.00*5.828?^n
*(([8.072  +/- 1.77e-4] + [+/- 1.57e-12]*I)   *n^3*log(n) 
+ ([1.371  +/- 5.79e-4] + [+/- 1.08e-4 ]*I)   *n^3 
+ ([50.509 +/- 8.16e-4] + [+/- 9.77e-12]*I)   *n^2*log(n) 
+ ([29.70  +/- 2.92e-3] + [+/- 6.71e-4 ]*I)   *n^2 
+ ([106.36 +/- 2.08e-3] + [+/- 2.06e-11]*I)   *n*log(n) 
+ ([118.76 +/- 5.85e-3] + [+/- 1.42e-3 ]*I)   *n 
+ ([72.85  +/- 4.56e-3] + [+/- 1.41e-11]*I)   *log(n) 
+ ([154.7  +/- 0.0133 ] + [+/- 9.55e-4 ]*I)   *1
+ ([-0.28  +/- 3.33e-6] + [+/- 5.49e-14]*I)   *n^(-1)*log(n) 
+ ([35.5   +/- 0.0224 ] + [+/- 3.41e-6 ]*I)   *n^(-1) 
+ B([3056.71 +/- 2.97e-3]*n^(-2)*log(n)^2, n >=50))

Asymptotic expansion shows \(d_n \geq 0\) when \(n \geq 50\)


Check \(d_0,\dots,d_{50}\) by hand

Two Difficulties

Skolem's Problem: When can cancellation occur with multiple singularities of minimal modulus?

Connection Problem: Can we prove when \(\lambda_1=0\)?

Doesn't happen "generically"

Can occur in practice

Main reason D-finite asymptotics still open

Not usually an issue in practice

More Quadrant Walks

Consider walks in \(\mathbb{N}^2\) on the steps N-SE-SW

sage: ini = [1,1,2,3,8,15,39]
sage: deq = (196608*z^16 - 4096*z^15 - 106496*z^14 + 90112*z^13 + 4096*z^12 + 16192*z^11 + 3776*z^10 - 4736*z^9 - 560*z^8 - 124*z^7 - 33*z^6 + 52*z^5 + 7*z^4 - 2*z^3)*Dz^4 + (3145728*z^15 - 462848*z^14 - 1073152*z^13 + 1252352*z^12 + 192512*z^11 + 370112*z^10 + 76800*z^9 - 58176*z^8 - 11152*z^7 - 2468*z^6 - 968*z^5 + 518*z^4 + 90*z^3 - 22*z^2)*Dz^3 + (14155776*z^14 - 3870720*z^13 - 2199552*z^12 + 4733952*z^11 + 1582080*z^10 + 2059392*z^9 + 525696*z^8 - 164256*z^7 - 47904*z^6 - 9648*z^5 - 5508*z^4 + 1236*z^3 + 306*z^2 - 60*z)*Dz^2 + (18874368*z^13 - 7544832*z^12 + 294912*z^11 + 5081088*z^10 + 3201024*z^9 + 3148416*z^8 + 1068864*z^7 - 68832*z^6 - 41136*z^5 - 5520*z^4 - 7584*z^3 + 648*z^2 + 276*z - 36)*Dz + 4718592*z^12 - 2482176*z^11 + 811008*z^10 + 964608*z^9 + 1075200*z^8 + 880128*z^7 + 387648*z^6 + 31296*z^5 + 6864*z^4 + 3024*z^3 - 1320*z^2 + 72*z + 36

sage: bound_coefficients(deq, ini, prec=20)
> 1.00000 * 3^n 
*(([+/- 1.56e-12] + [+/- 1.56e-12]*I)*n^(-1/2) 
+ ([+/- 3.21e-12] + [+/- 3.21e-12]*I)*n^(-3/2) 
+ ([+/- 8.71e-12] + [+/- 8.71e-12]*I)*n^(-5/2) 
+ B([2.18961e+7  +/- 68.1]*n^(-7/2), n >= 10))

We can show \(\displaystyle w_n = {\color{pink}\lambda_1} \cdot \frac{3^n}{\sqrt{n}}(1+\cdots) + O((2\sqrt{2})^n)\) where \({\color{pink}|\lambda_1|<10^{-1000}}\)

How can we (automatically) prove \({\color{pink}\lambda_1=0}\)?

More Quadrant Walks

Consider walks in \(\mathbb{N}^2\) on the steps N-SE-SW

sage: ini = [1,1,2,3,8,15,39]
sage: deq = (196608*z^16 - 4096*z^15 - 106496*z^14 + 90112*z^13 + 4096*z^12 + 16192*z^11 + 3776*z^10 - 4736*z^9 - 560*z^8 - 124*z^7 - 33*z^6 + 52*z^5 + 7*z^4 - 2*z^3)*Dz^4 + (3145728*z^15 - 462848*z^14 - 1073152*z^13 + 1252352*z^12 + 192512*z^11 + 370112*z^10 + 76800*z^9 - 58176*z^8 - 11152*z^7 - 2468*z^6 - 968*z^5 + 518*z^4 + 90*z^3 - 22*z^2)*Dz^3 + (14155776*z^14 - 3870720*z^13 - 2199552*z^12 + 4733952*z^11 + 1582080*z^10 + 2059392*z^9 + 525696*z^8 - 164256*z^7 - 47904*z^6 - 9648*z^5 - 5508*z^4 + 1236*z^3 + 306*z^2 - 60*z)*Dz^2 + (18874368*z^13 - 7544832*z^12 + 294912*z^11 + 5081088*z^10 + 3201024*z^9 + 3148416*z^8 + 1068864*z^7 - 68832*z^6 - 41136*z^5 - 5520*z^4 - 7584*z^3 + 648*z^2 + 276*z - 36)*Dz + 4718592*z^12 - 2482176*z^11 + 811008*z^10 + 964608*z^9 + 1075200*z^8 + 880128*z^7 + 387648*z^6 + 31296*z^5 + 6864*z^4 + 3024*z^3 - 1320*z^2 + 72*z + 36

sage: bound_coefficients(deq, ini, prec=20)
> 1.00000 * 3^n 
*(([+/- 1.56e-12] + [+/- 1.56e-12]*I)*n^(-1/2) 
+ ([+/- 3.21e-12] + [+/- 3.21e-12]*I)*n^(-3/2) 
+ ([+/- 8.71e-12] + [+/- 8.71e-12]*I)*n^(-5/2) 
+ B([2.18961e+7  +/- 68.1]*n^(-7/2), n >= 10))

Bostan and Kauers (FPSAC 2009): Conjectured asymptotics for 23 "small step" models in \(\mathbb{N}^2\)

M. and Wilson (FPSAC 2016): Finished proofs for all models 

The Kernel Method

Rigorous derivation of the D-finite equations for lattice path models usually uses the kernel method

 

1. Get functional equation for \(W(z)\)

 

2. Represent \(W(z)\) using a multivariate series

 

3. Use creative telescoping to get D-finite equation

Idea: Get asymptotics directly from multivariate series

Consider now a \(d\)-variate series
 

$$ F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}z_1^{i_1}\cdots z_d^{i_d} = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}\mathbf{z}^{\mathbf{i}}$$
 

The \(\color{violet}\mathbf{r}-\)diagonal sequence of \(F\) consists of the coefficients
 

$$(f_{n\mathbf{r}}) = f_{\mathbf{0}}, f_\mathbf{r}, f_{2\mathbf{r}},\dots $$

Rational Diagonals

Consider now a \(d\)-variate series
 

$$ F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}z_1^{i_1}\cdots z_d^{i_d} = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}\mathbf{z}^{\mathbf{i}}$$
 

 \((1,1)-\)Diagonal (Main Diagonal)

 

$$\begin{aligned} F(x, y) &= \frac{1}{1 - x - y} \\[+4mm] &= 1 + x + y + 2xy + x^2 + y^2 + 3x^2y + 3xy^2 + y^3 + 6x^2y^2 + \cdots \end{aligned}$$

Rational Diagonals

Rational Diagonals

Consider now a \(d\)-variate series
 

$$ F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}z_1^{i_1}\cdots z_d^{i_d} = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}\mathbf{z}^{\mathbf{i}}$$
 

 \((2,1)-\)Diagonal (Main Diagonal)

 

$$\begin{aligned} F(x, y) &= \frac{1}{1 - x - y} \\[+4mm] &= 1 + x + y + 2xy + x^2 + y^2 + 3x^2y  + \cdots + 15x^4y^2 + \cdots \end{aligned}$$

Generating Function Classes

D-Algebraic

D-Finite

Algebraic

Rational

Generating Function Classes

D-Algebraic

D-Finite

Algebraic

Rational

Rational Diagonal

Assume that the rational function 

$$F(\mathbf{z}) = \frac{G(\mathbf{z})}{H(\mathbf{z})} $$

converges in a neighbourhood of the origin.

 

 

Singular Variety

Assume that the rational function 

$$F(\mathbf{z}) = \frac{G(\mathbf{z})}{H(\mathbf{z})} $$

converges in a neighbourhood of the origin.

 

The singularities of \(F(\mathbf{z})\) form \(\mathcal{V} = \{\mathbf{z}\in\mathbb{C}^d:H(\mathbf{z})=0\}.\)  

 

Singular Variety

Assume that the rational function 

$$F(\mathbf{z}) = \frac{G(\mathbf{z})}{H(\mathbf{z})} $$

converges in a neighbourhood of the origin.

 

The singularities of \(F(\mathbf{z})\) form \(\mathcal{V} = \{\mathbf{z}\in\mathbb{C}^d:H(\mathbf{z})=0\}.\)

Singular Variety

Singular variety \(\mathcal{V}\) is now infinite


Hope: find finite set determining asymptotics of \(\mathbf{r}\)-diagonal

Assume that the rational function 

$$F(\mathbf{z}) = \frac{G(\mathbf{z})}{H(\mathbf{z})} $$

converges in a neighbourhood of the origin.

 

The singularities of \(F(\mathbf{z})\) form \(\mathcal{V} = \{\mathbf{z}\in\mathbb{C}^d:H(\mathbf{z})=0\}.\)

 

\(\mathbf{a}\in\mathcal{V}\) minimal if no \(\mathbf{b}\in\mathcal{V}\) with \(|b_i|<|a_i|\)

Singular Variety

Minimal Points: Singularities closest to the origin

Critical Points

Simplest Case: \(H\) and its partial derivatives never simultaneously vanish (so \(\mathcal{V}\) is a smooth manifold)

 

Then Critical Points are given by the solutions of
 

$$ H(\mathbf{z})=\frac{z_1}{r_1}H_{z_1}(\mathbf{z}) = \cdots = \frac{z_d}{r_d}H_{z_d}(\mathbf{z}) = 0 $$

Critical Points

Simplest Case: \(H\) and its partial derivatives never simultaneously vanish (so \(\mathcal{V}\) is a smooth manifold)

 

Then Critical Points are given by the solutions of
 

$$ H(\mathbf{z})=\frac{z_1}{r_1}H_{z_1}(\mathbf{z}) = \cdots = \frac{z_d}{r_d}H_{z_d}(\mathbf{z}) = 0 $$

In general partition \(\mathcal{V}\) into smooth manifolds (Whitney stratification) and compute critical points of \(\phi(\mathbf{z})=\mathbf{z}^{\mathbf{r}}\) restricted to each manifold

Critical Points

Always defined by a finite set of polynomial equalities and inequalities

Simplest Case: \(H\) and its partial derivatives never simultaneously vanish (so \(\mathcal{V}\) is a smooth manifold)

 

Then Critical Points are given by the solutions of
 

$$ H(\mathbf{z})=\frac{z_1}{r_1}H_{z_1}(\mathbf{z}) = \cdots = \frac{z_d}{r_d}H_{z_d}(\mathbf{z}) = 0 $$

Analytic Combinatorics in Several Variables

ACSV Theorem

If there are a finite number of minimal critical points, and the geometry of \(\mathcal{V}\) is not too bad, then there is a computable asymptotic expansion of \(f_{n\mathbf{r}}\).

 

If the minimal critical points vary uniformly with \(\mathbf{r}\) then one can also (often) prove limit theorems

 

 

ACSV Theorem

If there are a finite number of minimal critical points, and the geometry of \(\mathcal{V}\) is not too bad, then there is a computable asymptotic expansion of \(f_{n\mathbf{r}}\).

 

If the minimal critical points vary uniformly with \(\mathbf{r}\) then one can also (often) prove limit theorems

 

Automated by sage_acsv package for smooth or transverse multiple point cases

Verifies all conditions rigorously except that \(f_\mathbf{i}\) only has a finite number of negative terms

Analytic Combinatorics in Several Variables

ACSV Theorem

If there are a finite number of minimal critical points, and the geometry of \(\mathcal{V}\) is not too bad, then there is a computable asymptotic expansion of \(f_{n\mathbf{r}}\).

 

If the minimal critical points vary uniformly with \(\mathbf{r}\) then one can also (often) prove limit theorems

 

M. and Salvy (2020): Complexity analysis for smooth case

 

Non-negative coefficients: Go from \(\approx O(2^{12d})\) to \(\approx O(2^{4d})\)

Analytic Combinatorics in Several Variables

ACSV Theorem

If there are a finite number of minimal critical points, and the geometry of \(\mathcal{V}\) is not too bad, then there is a computable asymptotic expansion of \(f_{n\mathbf{r}}\).

 

If the minimal critical points vary uniformly with \(\mathbf{r}\) then one can also (often) prove limit theorems

 

M. and Salvy (2020): Complexity analysis for smooth case

 

Luo, M., and Schost (2025+): Futher complexity analysis

Analytic Combinatorics in Several Variables

sage_acsv

Can install with 

sage -pip install sage-acsv

Hackl, Luo, M., Selover, and Wong (2023): Smooth case

 

Hackl, Luo, M., and Schost (2025): Extension to more complicated geometries (and other improvements)

 


 

sage_acsv

Can install with 

sage -pip install sage-acsv

Hackl, Luo, M., Selover, and Wong (2023): Smooth case

 

Hackl, Luo, M., and Schost (2025): Extension to more complicated geometries (and other improvements)

 


Lee, M., Smolčić (2022): Julia package using homotopy continuation to (non-rigorously) prove minimality without non-negativity assumption

Binomial Examples

Example: Asymptotics of

$$ \binom{2n}{n} = [x^ny^n]\left(\frac{1}{1-x-y}\right) $$

sage: from sage_acsv import diagonal_asymptotics_combinatorial 
                         as diagonal
sage: var('x,y')
sage: diagonal(1/(1-x-y))
> 1/sqrt(pi)*4^n*n^(-1/2) + O(4^n*n^(-3/2))

$$ \binom{2n}{n} =\frac{4^n}{\sqrt{\pi n}} + O\left(\frac{4^n}{n^{3/2}}\right) $$

Binomial Examples

Example: Asymptotics of

$$ \binom{2n}{n} = [x^ny^n]\left(\frac{1}{1-x-y}\right) $$

sage: diagonal(1/(1-x-y), expansion_precision=10)
> 1/sqrt(pi)                                      *4^n*n^(-1/2)  
- 1/8/sqrt(pi)                                    *4^n*n^(-3/2) 
+ 1/128/sqrt(pi)                                  *4^n*n^(-5/2)  
+ 5/1024/sqrt(pi)                                 *4^n*n^(-7/2) 
- 21/32768/sqrt(pi)                               *4^n*n^(-9/2)  
- 399/262144/sqrt(pi)                             *4^n*n^(-11/2) 
+ 869/4194304/sqrt(pi)                            *4^n*n^(-13/2) 
+ 39325/33554432/sqrt(pi)                         *4^n*n^(-15/2) 
- 334477/2147483648/sqrt(pi)                      *4^n*n^(-17/2) 
- 11878603177281105812549/243524645683200/sqrt(pi)*4^n*n^(-19/2) 
+ O(4^n*n^(-21/2))

Binomial Examples

Example: Asymptotics of

$$ \binom{2n}{n} = [x^ny^n]\left(\frac{1}{1-x-y}\right) $$

sage: asm = diagonal(1/(1-x-y), r=[2,1])
sage: asm
> 0.866025403784439?/sqrt(pi)*(27/4)^n*n^(-1/2) 
+ O((27/4)^n*n^(-3/2))
sage: from sage_acsv import get_expansion_terms
sage: get_expansion_terms(asm)[0].coefficient.minpoly()
> x^2 - 3/4

Binomial Examples

Example: Asymptotics of

$$ \binom{2n}{n} = [x^ny^n]\left(\frac{1}{1-x-y}\right) $$

Lattice Path Examples

The number \(w_n\) of N-S-E-W walks in \(\mathbb{N}^2\) satisfies

 

$$w_n = [x^ny^nz^n]\left(\frac{(1+x)(1+y)}{1-zxy(x+1/x+y+1/y)}\right)$$

sage: F = (1+x)*(1+y)/(1-z*x*y*(1/x+x+1/y+y))
sage: diagonal(F, expansion_precision=2)
> 4/pi*4^n*n^(-1) - 6/pi*4^n*n^(-2) + O(4^n*n^(-3))

Lattice Path Examples

The number \(w_n\) of N-S-E-W walks in \(\mathbb{N}^2\) satisfies

 

$$w_n = [x^ny^nz^n]\left(\frac{(1+x)(1+y)}{1-zxy(x+1/x+y+1/y)}\right)$$

$$\frac{4}{\pi} = 1.273239544... = {\color{pink}\lambda_1}$$

sage: F = (1+x)*(1+y)/(1-z*x*y*(1/x+x+1/y+y))
sage: diagonal(F, expansion_precision=2)
> 4/pi*4^n*n^(-1) - 6/pi*4^n*n^(-2) + O(4^n*n^(-3))

Lattice Path Examples

The number \(w_n\) of N-SE-SW walks in \(\mathbb{N}^2\) satisfies

 

$$w_n = [x^ny^nz^n]\left(\frac{(1 + x)(2zx^2y^2 + 2zy^2 - 1)}{(-1 + y)(zx^2y^2 + zy^2 + zx - 1)(zx^2y^2 + zy^2 - 1)}\right)$$

sage: diagonal(F, expansion_precision=2)
> 32.97056274847714?/pi    * 2.828427124746190?^n    * n^(-2) 
  + 0.9705627484771406?/pi * (-2.828427124746190?)^n * n^(-2) 
  + O(2.828427124746190?^n*n^(-3))

GF tracking divisions
and polynomial degree
in Euclidean Algorithm
over \(\mathbb{F}_p[x]\) is

 

$$F(u,z) = \frac{1}{1-pz-p(p-1)uz}$$

sage: getLCLT(1/(1-3*z-6*u*z), z, as_symbolic=True) # p = 3
> 3/2*9^n*e^(-1/4*(2*n - 3*s0)^2/n)/(sqrt(pi)*sqrt(n))

Automated Limit Theorems (with T. Ruza)

Automated Limit Theorems (with T. Ruza)

# Tracking 1s, 2s, and 3s in integer compositions
sage: F = 1/(1-z1*t-z2*t^2-z3*t^3-t^4/(1-t))
sage: getLCLT(F, t, as_symbolic=False)
> (2, n^(-3/2), pi^(-3/2), 4.374949932957845?, # leading factor
[ 348/107   16/107  112/107]                   # covariance    
[  16/107 1024/107  320/107]                   #         matrix
[ 112/107  320/107 2240/107], 
[ 1/4  1/8 1/16])                              # mean
# Tracking rows in horizontally convex polyominoes
sage: F = (x*y*(1-x)^3)/((1-x)^4-x*y*(1-x-x^2+x^3+x^2*y))
sage: getLCLT(F, x)
> 0.3450475264519037?*3.205569430400590?^n/(sqrt(pi)*sqrt(n))
  *e^(-1/14.5501096287814?*(-0.4530745716375183?*n + s0)^2/n)

Other Recent Work

"Non-Generic" Directions

(with A. Kroitor)

Multivariate Algebraic Functions

(with T. Ruza + T. Greenwood, M. C. Wilson)

Ruling out Critical Points "at Infinity"

(with E. Liu + Y. Baryshnikov, A. Ergür, T. George, R. Pemantle)

Bounded Error Terms / Positivity in Several Variables

(with J. H. Smith)

(Some) Underlying Theory

higher-dimensional saddle-point integrals
multidimensional (Leray) residues
cones of hyperbolicity
stratified Morse theory
negative moment Gaussian integrals
rational univariate (Kronecker) representations
symbolic Newton iteration
sparse resultants and discriminants
real algebraic critical point techniques
polynomial amoebas
homotopy solving of polynomial systems
heights and the arithmetic Nullstellensatz
effective resolution of singularities
tropical/toric compactifications

References

enumeration.ca course notes

Focus on computation
melczer.ca/textbook

Most general theory
ACSVproject.org

Try it Out Yourself!

If you find bugs -- let us know!


 

If you can't get something to work, contact me (smelczer@uwaterloo.ca)
 

If it can already be done then I can explain how
(and update the documentation to be clearer)


If it can't then having an interesting application makes it more likely to be added sooner

Thank You!

melczer.ca/FPSAC25

Software presentation by Andrew Luo at noon

If you want to follow along, install the package before then

sage -pip install sage-acsv