Directed Lattice Paths Avoiding Periodic Subset of Points on "Time"-Axis

Basic Information

• Paper ID: 2510.11367
• Title: Directed lattice paths avoiding periodic subset of points on "time"-axis
• Author: S. Tarasov
• Classification: math.CO (Combinatorics)
• Publication Date: October 14, 2025
• Paper Link: https://arxiv.org/abs/2510.11367

Abstract

This paper computes the generating function for the set of directed lattice paths originating from the origin that avoid a periodic subset of even points on the "time"-axis. As an application, we prove a combinatorial identity proposed by P. Hajnal and G.V. Nagy.

Research Background and Motivation

1. Research Problem: This paper investigates the enumeration of directed lattice paths under restrictive conditions, particularly when lattice paths must avoid specific points periodically distributed on the time axis.
2. Problem Significance:
   • Lattice path enumeration is a classical problem in combinatorics with close connections to probability theory and statistical physics
   • Restricted lattice path counting problems have greater practical significance, such as forbidden region problems in random walk theory
   • This research connects lattice path theory with cycle counting theory
3. Limitations of Existing Methods:
   • Traditional approaches primarily focus on restrictions at spatial lattice points, with less emphasis on time-axis restrictions
   • Lack of a unified theoretical framework for handling periodic restrictions
4. Research Motivation:
   • Transform lattice path problems into a spacetime graph perspective, where the time axis represents path progression
   • Model lattice walk problems with universal clock frequencies through periodic restrictions

Core Contributions

1. Established a Complete Theoretical Framework: Transformed directed lattice path problems into solving linear equation systems, where the system matrix becomes a circulant matrix when the forbidden point set is periodic
2. Provided Explicit Generating Function Expressions: Through cycle counting techniques, derived explicit expressions for generating function coefficients in all dimensions
3. Proved the HN Conjecture: Demonstrated the combinatorial identity proposed by P. Hajnal and G.V. Nagy
4. Developed Multi-Section Theory: Advanced the theory of multi-section for generating functions and applied discrete Fourier transforms for computation

Methodology Details

Task Definition

Study directed lattice paths on the $\mathbb{Z}_+ \times \mathbb{Z}^d$ lattice where:

• Paths originate from the origin
• Can only touch the time axis at points in the allowed set $A$
• $A$ is a periodic set of even points, expressed as $A = (\{a_0, a_1, \ldots, a_k\}, t_A)$
• Step set is $S = \{-1, 1\}^d$

Model Architecture

1. Basic Setup

• Define $P(A)$ as the set of all even-length directed lattice paths originating from the origin that can only touch the time axis at points in set $A$
• Use generating function ${}^d P^r(A,t)$ to represent generating functions for such paths starting from allowed points $(2r,0)$

2. Core Linear Equation System

The main theorem establishes the following linear equation system: ${}^d P^r(A,t) - \sum_{q \in A} [{}^d E(t)]_{t_A, Sh(r,q)} {}^d P^q(A,t) = {}^d E_\infty(t)$

Where:

• $Sh(r,q)$ is the shift operation, defined as the distance from point $r$ to point $q$
• $[{}^d E(t)]_{t_A, Sh(r,q)}$ is the multi-section of the primitive $T$-excursion generating function
• ${}^d E_\infty(t)$ is the generating function for escape paths

3. Cycle Counting Method

Establish connections with cycle counting by projecting lattice paths onto the spatial component:

• Primitive $T$-excursions correspond to simple cycles
• Generating function relation: ${}^d E(t) = {}^d SL(t) = 1 - \frac{1}{{}^d L(t)}$
• Escape path generating function: ${}^d E_\infty(t) = \frac{1}{{}^d L(t)(1-4^d t)}$

Technical Innovations

1. Application of Circulant Matrix Theory: When the allowed point set is periodic, the system matrix becomes a principal submatrix of a circulant matrix, enabling exploitation of circulant matrix properties for solution
2. Multi-Section Technique: Compute generating function multi-sections using discrete Fourier transform: $[[G(t)]_{q,0}, \ldots, [G(t)]_{q,q-1}]^{tr} = F_q^{-1} \overrightarrow{G(t), \omega_q}$
3. Unified Cycle Counting Method: Unify problems across all dimensions through cycle counting, avoiding dimensional limitations of traditional reflection principle methods

Experimental Setup

Theoretical Verification

This paper is primarily theoretical research, with results verified through:

1. Special Case Verification: For the $d=1$ case, verify that results are consistent with known Catalan numbers and Dyck path theory
2. Concrete Example Computation: Calculate generating functions for specific periodic sets $A_1 = (\{0\}, 2)$ and $A_2 = (\{0,1\}, 4)$

Computational Examples

• For $A_1$: ${}^1 P^0(A_1, t)_{2,0} = \frac{1}{\sqrt{1-(4t)^2}}$
• For $A_2$: ${}^1 P^0(A_2, t)_{4,0} = \frac{1}{\sqrt{1-(4t)^4}}$

Experimental Results

Main Results

1. Proof of the HN Conjecture

Proved that for periodic set $A_k = (\{0,1,\ldots,k\}, 2k)$: ${}^1 P^0(A_k, t)_{2k,0} = \frac{1}{\sqrt{1-(4t)^{2k}}}$

2. Circulant Matrix Determinant Formula

Established the key identity: $\frac{\det(B_1)}{\det(C_1)} = \det[({}^1 C_{2k})^{-1}] = \frac{1}{\sqrt{1-(4t)^{2k}}}$

3. Analytical Expressions

For the $d=2$ case, obtained analytical expressions involving elliptic integrals: ${}^2 L(t) = \frac{2}{\pi}K(4\sqrt{t})$ where $K(q)$ is the complete elliptic integral of the first kind.

Theoretical Findings

1. Dimensional Complexity: Analytical complexity of generating functions grows sharply with dimension:
   • $d=1$: Algebraic function
   • $d=2$: Transcendental but D-finite function
   • $d=3$: Non-D-finite function
2. Power of Periodicity: Periodic restrictions enable transformation of otherwise complex problems into finite-dimensional linear systems

Related Work

1. Classical Lattice Path Theory: Based on Feller's probability textbook and reflection principle
2. Pólya's Random Walk Problem: Classical work on return probabilities of random walks on lattice points
3. Circulant Matrix Theory: Theoretical foundations from Davis's circulant matrix monograph
4. Cycle Counting: Modern exposition of Pólya's random walk theorem by Novak

Conclusions and Discussion

Main Conclusions

1. Established a complete theoretical framework for handling directed lattice paths under periodic restrictions
2. Successfully proved the HN conjecture, demonstrating the applied value of the theory
3. Provided a unified computational method applicable to all dimensions

Limitations

1. Methods primarily apply to periodic restrictions; may not extend to general restrictions
2. Computational complexity remains high in higher dimensions
3. Some analytical expressions involve special functions, making practical computation difficult

Future Directions

1. Generalize to more general restriction conditions
2. Investigate methods for handling non-periodic cases
3. Explore connections with other combinatorial structures

In-Depth Evaluation

Strengths

1. Theoretical Completeness: Provides a complete theoretical framework from problem formulation to solution
2. Methodological Innovation: Cleverly transforms lattice path problems into circulant matrix problems
3. Technical Depth: Synthesizes multiple techniques including generating functions, circulant matrices, and Fourier transforms
4. Applied Value: Successfully resolves a specific combinatorial conjecture

Weaknesses

1. Computational Complexity: Practical computation remains difficult in higher dimensions
2. Limited Applicability: Primarily restricted to periodic cases
3. Limited Examples: Relatively few concrete computational examples

Impact

1. Theoretical Contribution: Provides new theoretical tools for restricted lattice path problems
2. Methodological Value: Circulant matrix methods may apply to other combinatorial problems
3. Application Prospects: Potential applications in probability theory and statistical physics

Applicable Scenarios

1. Random walk problems with periodic restrictions
2. Restricted path integrals in statistical physics
3. Generating function computation in combinatorial enumeration

References

The paper cites the following important literature:

• Feller's probability textbook (foundations of random walk theory)
• Davis's circulant matrix monograph (circulant matrix theory)
• Pólya's classical papers on random walks on lattices
• Papers by Hajnal and Nagy proposing the original conjecture
• Standard references on special functions and elliptic integrals