A p-adic Valuation Calculus for Permutations with Restricted Cycle Lengths
Abstract
Let a_A(n) be the number of permutations of {1,...,n} all of whose cycle lengths lie in a set A. We develop a valuation calculus for these numbers. Mobius inversion writes the exponential generating function as an Euler product, and at a prime p the factors with non-p-integral exponents, the blocks, determine a finite knapsack problem. Its optimal value gives a lower bound for v_p(a_A(n)), and the bound is attained exactly when one residue modulo p, the sum of the terms of the optimal choices, does not vanish. For a fixed set A and prime p the bounds and residues for all n <= N cost O(N^2) operations. When one block is strictly the most efficient, the valuation inside each residue class is that of a locally analytic p-adic function. We use the calculus to determine the 2-adic and 3-adic valuations for cycle lengths at most 3, 4 and 5, to prove the divisibility conjectures recorded in A378495, A079128, A193437 and A193438 and the 3-adic statements recorded in A057693 and A070945, and to treat 99 OEIS sequences in all. We also prove sharp divisibility and gcd theorems, show that at n = 111 the gcd of the counts over all sets of excluded cycle lengths containing {1,2,3} is one third of the gcd over the sets {1,2,3,k}, and determine eventual divisibility and tail gcds modulo composite integers. Part of the paper is formalized in Lean 4.
Related
- Distributions of Mesh Patterns of Short Lengths on Separable Permutations
- Rotating bases for finite element exterior calculus: closed-form change of basis under vertex permutations
- Extremal graphs with cycle lengths in a fixed residue class
- Minimising the harmonic sum of cycle lengths
- The Erdős-Gallai bound for consecutive even cycle lengths
BibTeX
@misc{kallat2026padic,
title = {{A p-adic Valuation Calculus for Permutations with Restricted Cycle Lengths}},
author = {Ahaan Kallat},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40342},
eprint = {2610.40342},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40342},
}
RIS
TY - UNPB
TI - A p-adic Valuation Calculus for Permutations with Restricted Cycle Lengths
AU - Ahaan Kallat
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40342
UR - https://arxiv.org/abs/2610.40342
AB - Let a_A(n) be the number of permutations of {1,...,n} all of whose cycle lengths lie in a set A. We develop a valuation calculus for these numbers. Mobius inversion writes the exponential generating function as an Euler product, and at a prime p the factors with non-p-integral exponents, the blocks, determine a finite knapsack problem. Its optimal value gives a lower bound for v_p(a_A(n)), and the bound is attained exactly when one residue modulo p, the sum of the terms of the optimal choices, does not vanish. For a fixed set A and prime p the bounds and residues for all n <= N cost O(N^2) operations. When one block is strictly the most efficient, the valuation inside each residue class is that of a locally analytic p-adic function. We use the calculus to determine the 2-adic and 3-adic valuations for cycle lengths at most 3, 4 and 5, to prove the divisibility conjectures recorded in A378495, A079128, A193437 and A193438 and the 3-adic statements recorded in A057693 and A070945, and to treat 99 OEIS sequences in all. We also prove sharp divisibility and gcd theorems, show that at n = 111 the gcd of the counts over all sets of excluded cycle lengths containing {1,2,3} is one third of the gcd over the sets {1,2,3,k}, and determine eventual divisibility and tail gcds modulo composite integers. Part of the paper is formalized in Lean 4.
ER -