Complexity in Enumerative Combinatorics — Conjecture 8 (cf. [Zei])

Definitions and mathematical statement

Let $O=(0,0)\in{\mathbb{Z}}^2$. For an integer $n\geq 0$, a nearest-neighbor lattice walk of length $n$ is a sequence $(v_0,\ldots,v_n)$ of lattice points such that $\lVert v_{i+1}-v_i\rVert_1=1$ for every $0\leq i<n$. It is closed at the origin if $v_0=v_n=O$.

The source describes $a_n$ as the number of self-avoiding walks from $O$ to $O$ in ${\mathbb{Z}}^2$ of length $n$, and states the following conjecture, attributed to Pak (2018), Conjecture 8, with the qualification "cf. [Zei]": \[ \text{The sequence }\{a_n\}\text{ has no Wilfian formula of type }\mathrm{(W1)}. \]

This formulation has unresolved definitions. If self-avoidance means that all vertices are distinct, a positive-length walk cannot return to its starting vertex. A possible closed-walk convention instead requires $v_0,\ldots,v_{n-1}$ to be pairwise distinct and allows $v_n=v_0$; the supplied record does not establish that this is the intended convention. That convention alone permits a length-two walk traversing an edge and immediately returning, so any exclusion of such walks also requires clarification. The record does not specify whether walks are counted as vertex sequences or identified under changes of starting point, reversal, or lattice symmetries, nor does it specify the treatment of length zero.

The record also does not define a Wilfian formula of type $\mathrm{(W1)}$. In particular, it supplies no computational model, input and output encoding, or complexity bound for this term. Consequently, the displayed conjecture preserves the source wording, but its counting convention and computational predicate require clarification before it becomes a fully specified mathematical assertion.

Short English statement

The supplied conjecture says that the numbers of closed self-avoiding square-lattice walks admit no Wilfian formula of type $\mathrm{(W1)}$. Both the closed-walk counting convention and the definition of $\mathrm{(W1)}$ are missing from the record. Its supplied status is open; this draft does not independently verify that status.

Sources

• Local UnsolvedMath registry, supplied complete source record: permanent ID $800324$, exact source problem code catalogue entry, upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82. The registry attributes the problem to Pak, gives the year 2018, and labels it open.
• Pak, Complexity Problems in Enumerative Combinatorics (2018), Conjecture 8. Supplied source URL: https://arxiv.org/abs/1803.06636. The record reports extraction by arxiv_latex and access on 2026-10-16; these are supplied provenance details, not evidence of independent source consultation for this draft.
• The supplied title and background include the attribution/context qualification "cf. [Zei]". No bibliographic identification of [Zei] is supplied.