Semiformal method I. Pólya’s theorem for the complete graph K ℕ K_{\mathbb{N}} with complex edge weights
M. Klazar (UK, Praha) and R. Horský (VŠE, Praha) · 2025
Read Semiformal method I. Pólya’s theorem for the complete graph K ℕ K_{\mathbb{N}} with complex edge weights by M. Klazar (UK, Praha) and R. Horský (VŠE, Praha) (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00914.txt.
Introduction
M. Klazar and R. Horsky generalize a famous result of Polya about random walks. Polya's theorem describes the limiting chances that a walk on a grid, starting at the origin, ever visits a given point. Their version replaces the grid with the complete directed graph on the natural numbers, where every vertex connects to every other.
Edges carry complex number weights, and coefficients in generating functions may themselves be infinite series, extending the symbolic method of enumerative combinatorics. The authors obtain sixteen generalizations of Polya's theorem, and the approach also covers Markov chains on the natural numbers starting at one. An appendix proves key values of an auxiliary function used in the argument.
Catalog record
| CREATOR | M. Klazar (UK, Praha) and R. Horský (VŠE, Praha) |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-00914
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Semiformal method I. Pólya’s theorem for the complete graph K ℕ K_{\mathbb{N}} with complex edge weights M. Klazar (UK, Praha) and R. Horský (VŠE, Praha) Abstract Using the semiformal method in combinatorics we generalize Pólya’s theorem. This theorem determines the limiting probability that walks in the grid graph ℤ d \mathbb{Z}^{d} visit the given vertex. We generalize it to the countable complete graph K ℕ K_{\mathbb{N}} with edge weights in ℂ \mathbb{C} . In part II we treat edge weights in ℂ [ [ x 1 , … , x k ] ] \mathbb{C}[[x_{1},\dots,x_{k}]] . 1 Introduction Let d,n\in\mathbb{N} ( =\{1,2,\dots\} ) and \overline{v}\in\mathbb{Z}^{d} , where \mathbb{Z}=\{\dots,-1,0,1,\dots\} are the integers. Let P_{d}(\overline{v},n) be the probability that a walk of length n in the grid graph \mathbb{Z}^{d} starting at \overline{0} visits in a step i>0 the vertex \overline{v} . In 1921, G. Pólya proved in [ 24 ] a theorem, which we generalize, asserting that for every vertex \overline{v} , \lim_{n\to\infty}P_{d}(\overline{v},\,n)\left\{\begin{array}[]{lll}=1&\dots&\text{if $d\leq 2$ and}\\ <1&\dots&\text{if $d\geq 3$}\,.\end{array}\right. Pólya’s theorem is almost always cited in the special case with \overline{v}=\overline{0} , although he proved it for any vertex \overline{v} (see [ 16 , Section 1] for a translated quote from [ 24 ] ). A selection of articles and books discussing Pólya’s theorem is [ 3 , 4 , 6 , 9 , 11 , 13 , 18 , 19 , 20 , 21 , 25 , 26 , 29 , 30 ] . We generalize it as follows. Let {\textstyle\mathbb{N}_{2}=\binom{\mathbb{N}}{2}=\{e\colon\;e\subset\mathbb{N}\wedge|e|=2\}} be edges of the countable complete graph K_{\mathbb{N}}=\langle\mathbb{N},\mathbb{N}_{2}\rangle on the vertex set \mathbb{N} . For a finite set A we denote by |A| ( \in\mathbb{N}_{0}=\{0,1.\dots\} ) its cardinality. Let h\colon\mathbb{N}_{2}\to\mathbb{C} be a complex edge weight. \mathbb{C} denotes the field of complex numbers, which is endowed with the usual Archimedean absolute value |z|=\sqrt{z\cdot\overline{z}} . For n\in\mathbb{N}_{0} let W(n) be the set of walks of length n in K_{\mathbb{N}} starting at the vertex 1 . Thus W(0)=\{\langle 1\rangle\} and for n>0 the set W(n) is infinite and countable. For v\in\mathbb{N} let W(v,n) be the subset of W(n) of the walks that visit the vertex v in a step i>0 . We extend the weight in the usual multiplicative way to {\textstyle h\colon\bigcup_{n=0}^{\infty}W(n)\to\mathbb{C}\,.} Let W\subset\bigcup_{n=0}^{\infty}W(n) . If the series {\textstyle\sum_{w\in W}h(w)} absolutely converges, we denote its sum by h(W) . (Results on series are reviewed in the next section.) Suppose that for every n\in\mathbb{N}_{0} the series \sum_{w\in W(n)}h(w) absolutely converges. Then so does \sum_{w\in W(v,n)}h(w) and we consider the generating function {\textstyle A_{h,v}(x)=\sum_{n\geq 0}h(W(v,\,n))x^{n}\ \ (\in\mathbb{C}[[x]])\,.} Our generalizations of Pólya’s theorem are formulas for the quantities {\textstyle A_{h,v}(1)=\sum_{n\geq 0}h(W(v,\,n))\,\text{ and }\,\lim_{n\to\infty}h(W(v,\,n))\,.} The formulas appear in fourteen theorems: Theorems 3.2 – 3.7 in Section 3 and Theorems 4.2 – 4.9 in Section 4 . Pólya’s theorem is subsumed in five of them. Theorems 3.5 and 3.7 extend cases d\geq 3 and d\leq 2 , respectively, when \overline{v}=\overline{0} . Theorems 4.6 ( 4.7 ) and 4.9 extend cases d\geq 3 and d\leq 2 , respectively, when \overline{v}\neq\overline{0} . We have fourteen generalizations of one theorem for three reasons. First, in Pólya’s theorem weights are nonnegative real numbers and convergence of infinite series is automatically absolute. For complex weights we consider both kinds of convergence, absolute and conditional one. We also consider, for nonnegative real weights, series with sum +\infty . Second, Pólya’s theorem lives in the probabilistic setup where weights of edges incident to a fixed vertex sum up to 1 . We consider the case when this condition is kept (convex weights) and the case when it is dropped. Third, already Pólya’s theorem is in reality two theorems because the cases \overline{v}=\overline{0} and \overline{v}\neq\overline{0} differ in complexity of proofs. In our generalization we distinguish cases v=1 and v\neq 1 as well. Now 3\cdot 2\cdot 2=12 ; two more generalizations arise by variations of assumptions. We explain how our approach includes Pólya’s original problem. If f\colon A\to B is a map and C is any set (not necessarily a subset of A ), we call the set f[C]=\{f(x)\colon\;x\in A\cap C\}\ \ (\subset B) the image of C by f . Let d\in\mathbb{N} and \overline{v}\in\mathbb{Z}^{d} . We take any bijection f\colon\mathbb{Z}^{d}\to\mathbb{N} such that f(\overline{0})=1 , and set v=f(\overline{v}) . The grid graph on \mathbb{Z}^{d} , which is the graph \langle\mathbb{Z}^{d},E_{d}\rangle with the edges {\textstyle\{\overline{a},\,\overline{b}\}\in E_{d}\iff\sum_{i=1}^{d}|a_{i}-b_{i}|=1\,,} determines the weight h\colon\mathbb{N}_{2}\to\{\frac{1}{2d},0\} by the relation h(e)\neq 0 iff e=f[e^{\prime}] for some e^{\prime}\in E_{d} . Then for every n\in\mathbb{N}_{0} we have P_{d}(\overline{v},\,n)=h(W(v,\,n))\,. We structure our article as follows. In Section 2 we review infinite series with complex summands and generating functions. Sections 3 and 4 contain our main results, the mentioned fourteen generalizations of Pólya’s theorem. Section 5 contains concluding remarks. We continue our investigation in [ 17 ] (see Section 5 for more details). In Sections 3 and 4 we use what we term the semiformal method in (enumerative) combinatorics. It extends the symbolic method in combinatorics [ 2 , 8 , 10 , 12 , 22 , 23 , 27 ] from finite to countable sets. In our situation such extension is natural and inevitable, coefficients in generating functions A_{h,v}(x) arise as sums of infinite series \sum_{w\in W(v,n)}h(w) . We develop the semiformal method more in [ 14 ] . Why “semiformal”? Generating “functions” in the symbolic method are formal power series with coefficients determined by finite operations. Our extension allows operations based on limit transitions. See [ 15 ] more applications of the semiformal method. 2 Series and generating functions in \mathbb{C} We review series and generating functions in the domain \mathbb{C} . A series (in \mathbb{C} ) is a map h\colon X\to\mathbb{C} , defined on an at most countable set X . We write it as \sum_{x\in X}h(x) . We say that \sum_{x\in X}h(x) absolutely converges if two equivalent conditions hold. 1. For some c>0 and every finite set Y\subset X we have \sum_{x\in Y}|h(x)|\leq c . 2. If X is countable, then for every bijection f\colon\mathbb{N}\to X , the limit s=\lim_{n\to\infty}{\textstyle\sum_{i=1}^{n}h(f(i))} exists and does not depend on f . We call s the sum of the series and denote it again by \sum_{x\in X}h(x) . If the set X=\{x_{1},x_{2},\dots,x_{n}\}\neq\emptyset is finite, then every series \sum_{x\in X}h(x) absolutely converges and has the sum h(x_{1})+h(x_{2})+\dots+h(x_{n})\,. For X=\emptyset we define the sum as 0 . If {\textstyle U(x)=\sum_{n\geq 0}u_{n}x^{n}\ \ (\in\mathbb{C}[[x]])} is a formal power series, so that x is a formal variable, we denote for any x\in\mathbb{C} by F_{U}(x) the sum of the power series \sum_{n\geq 0}u_{n}x^{n} , if it absolutely converges. Let h\colon\mathbb{N}_{2}\to\mathbb{C} . A walk w in K_{\mathbb{N}} is any (n+1) -tuple w of vertices v_{i}\in\mathbb{N} , w=\langle v_{0},\,v_{1},\,\dots,\,v_{n}\rangle\,, such that n\in\mathbb{N}_{0} and v_{i-1}\neq v_{i} for every i\in[n] ( =\{1,2,\dots,n\} , [0]=\emptyset ). The length n of w is is n ( \in\mathbb{N}_{0} ). We extend h to walks. For n>0 we set {\textstyle h(w)=\prod_{i=1}^{n}h(\{v_{i-1},\,v_{i}\})\,,} and for n=0 we define h(w)=1 . Recall that W(n) is the set of walks w in K_{\mathbb{N}} with length n such that v_{0}=1 . Definition 2.1 (lightness) A weight h\colon\mathbb{N}_{2}\to\mathbb{C} is light if for every n\in\mathbb{N}_{0} the series {\textstyle\sum_{w\in W(n)}h(w)} absolutely converges. Let S=\sum_{x\in X}h(x) be a series. If Y\subset X , we say that \sum_{x\in Y}h(x) is a