标题： 裂平面上的行走：其他方法 显示英文标题

标题： Walks on the slit plane: other approaches

摘要： 设S是Z²的一个有限子集。 在步长属于S的穿孔平面上的行走是指点序列(0,0)=w_0, w_1, ..., w_n，使得对于所有i，w_{i+1}-w_i属于S，并且没有点w_i（i>0）位于半线H= {(k,0): k <= 0}上。 在最近的一篇论文中，G. Schaeffer和作者计算了对于几个集合S的穿孔平面上行走的长度生成函数S(t)。因此得到的所有生成函数都被证明是代数的：例如，在普通的正方形格点上，S(t) =\frac{(1+\sqrt{1+4t})^{1/2}(1+\sqrt{1-4t})^{1/2}}{2(1-4t)^{3/4}}。 这种代数性的组合原因仍然不清楚。 在本文中，我们提出了两种新的方法来求解穿孔平面模型。 其中一种方法简化并扩展了原始论文中的函数方程方法。 另一种方法受到Lawler的一个论点的启发；它更具组合性，并解释了与模型相关的三个级数乘积的代数性。 它也可以被视为经典循环引理的扩展。 这两种方法适用于任何步长集合S。 我们展示了一个大的集合S族，其穿孔平面上行走的生成函数是代数的，另一个集合S族，其生成函数既不是代数的，甚至也不是D-有限的。 这些例子暗示了代数性和超越性之间的边界在哪里，并呼吁对集合S进行全面分类。 显示英文摘要

摘要： Let S be a finite subset of Z^2. A walk on the slit plane with steps in S is a sequence (0,0)=w_0, w_1, ..., w_n of points of Z^2 such that w_{i+1}-w_i belongs to S for all i, and none of the points w_i, i>0, lie on the half-line H= {(k,0): k =< 0}. In a recent paper, G. Schaeffer and the author computed the length generating function S(t) of walks on the slit plane for several sets S. All the generating functions thus obtained turned out to be algebraic: for instance, on the ordinary square lattice, S(t) =\frac{(1+\sqrt{1+4t})^{1/2}(1+\sqrt{1-4t})^{1/2}}{2(1-4t)^{3/4}}. The combinatorial reasons for this algebraicity remain obscure. In this paper, we present two new approaches for solving slit plane models. One of them simplifies and extends the functional equation approach of the original paper. The other one is inspired by an argument of Lawler; it is more combinatorial, and explains the algebraicity of the product of three series related to the model. It can also be seen as an extension of the classical cycle lemma. Both methods work for any set of steps S. We exhibit a large family of sets S for which the generating function of walks on the slit plane is algebraic, and another family for which it is neither algebraic, nor even D-finite. These examples give a hint at where the border between algebraicity and transcendence lies, and calls for a complete classification of the sets S.