A More Efficient Algorithm for Finding the Number of Permutations of $\mathbb{ZZ}/n\mathbb{ZZ}$ with Distinct Partial Sums

Technical Summary: A More Efficient Algorithm for Finding the Number of Permutations of Z/nZ with Distinct Partial Sums

Problem Statement
This paper addresses the enumeration of specific permutations within the additive group of integers modulo $n$ ($\mathbb{Z}/n\mathbb{Z}$), where $n$ is an even integer. The core problem involves counting the number of permutations $\sigma = (\sigma_0, \sigma_1, \dots, \sigma_{n-1})$ such that the set of partial sums (or "factorials" in the group context) are all distinct. Specifically, the paper focuses on the sequence A141599 in the On-Line Encyclopedia of Integer Sequences (OEIS), which counts the number of "difference sets" for permutations of $\mathbb{Z}/2k\mathbb{Z}$ with distinct differences.

A permutation has distinct differences if the set of values $d_i \equiv \sigma_i - \sigma_{i-1} \pmod n$ for $1 \le i \le n-1$ contains every non-zero element of $\mathbb{Z}/n\mathbb{Z}$ exactly once. The authors note that such permutations only exist when $n$ is even. The computational challenge lies in the fact that the total number of permutations ($n!$) grows factorially, making brute-force enumeration infeasible for larger $n$.

Methodology
The authors propose a recursive backtracking algorithm that significantly improves upon previous brute-force approaches by pruning the search space early. The methodology rests on three main pillars:

1. Bijection between Difference Sets and Sequencings:
   The paper establishes a formal bijection (Theorem 1) between "difference sets with distinct differences" and "sequencings" of $\mathbb{Z}/n\mathbb{Z}$. A sequencing is defined as a permutation where the partial sums $s(\sigma, i) = \sum_{j=0}^i \sigma_j$ are all distinct. The proof demonstrates that a difference set $D_\tau = (d_1, \dots, d_{n-1})$ can be mapped to a sequencing $\sigma = (0, d_1, \dots, d_{n-1})$, and vice versa. This allows the authors to count sequencings instead of difference sets directly.

2. Symmetry Reduction via Multiplication:
   Leveraging Lemma 2, the authors utilize the property that if $\sigma$ is a sequencing and $r$ is an integer coprime to $n$ ($\gcd(r, n) = 1$), then the element-wise product $(r\sigma_0, r\sigma_1, \dots, r\sigma_{n-1})$ is also a sequencing. This allows the algorithm to compute sequencings for a specific "branch" (permutations starting with $0, 1$) and multiply the count by Euler's totient function $\phi(n/d)$ to account for other branches, rather than computing them individually.

3. Recursive Branch Pruning (Algorithm 2):
   The core of the new algorithm is a recursive search that constructs partial permutations. Unlike previous brute-force methods that validated full permutations, this algorithm maintains a state of "partial sums" (partials).

   • Pruning Logic: If adding a new element to the partial permutation results in a partial sum that has already been seen (or equals 0 prematurely), the branch is immediately abandoned.
   • Efficiency: This prevents the algorithm from exploring the $(n-k)!$ permutations that would extend an invalid partial sequence. For example, in $\mathbb{Z}/20\mathbb{Z}$, the partial sequence $(0, 1, 19)$ yields a partial sum of 0 at index 2, which is invalid; the algorithm discards this entire branch, saving $17!$ potential calls to a validator.

Key Contributions

• New Terms for OEIS A141599: Using the improved algorithm, the authors calculated the 10th, 11th, and 12th terms of the sequence (corresponding to $n=20, 22, 24$). The values are:
  • $n=20$: 5,074,931,072
  • $n=22$: 298,557,044,000
  • $n=24$: 21,224,961,132,544
    The 10th and 11th terms were independently verified by Bert Dobbelaere.
• Theoretical Unification: The paper provides a rigorous proof of the bijection between difference sets and sequencings, unifying classical results (Gilbert, Gordon) with the current computational approach.
• Algorithmic Optimization: The introduction of the recursive branch search with early termination based on partial sum collisions represents the most efficient known method for this specific counting problem to date.

Results and Data Analysis
The paper presents data (Tables 1 and 2) comparing the number of sequencings to the total number of permutations ($n!$) for even $n$ up to 22. The results indicate that the ratio of sequencings to total permutations decreases strictly and rapidly as $n$ increases, dropping by approximately an order of magnitude with each step. For $n=22$, the ratio is approximately $2.66 \times 10^{-10}$.

This empirical evidence supports the efficacy of the pruning strategy. Because valid sequencings are extremely sparse within the space of all permutations, generating and validating full permutations is inefficient. The recursive approach, which eliminates invalid partial paths immediately, aligns with the observed sparsity.

Significance and Claims
The authors claim that their algorithm is the most efficient known to date for computing terms of sequence A141599. They argue that while the time complexity remains super-polynomial (likely worse than exponential but better than $O(n!)$), the pruning technique offers a "strict improvement" over brute-force methods by avoiding wasted computation on invalid branches.

The paper modestly concludes that further improvements to the counting algorithm are likely limited unless new mathematical transformations can be identified. Specifically, they suggest that future progress might depend on identifying a complete set of transformations (beyond the multiplication by coprime integers) that can map a small set of known sequencings to the entire set for a given $n$, thereby potentially bypassing the need for exhaustive search entirely. However, they do not propose such transformations in this work, noting that the current recursive approach is the state-of-the-art for solving the problem as defined.