Universal Shift Congruences for Weighted Permutation Sequences
Abstract
The involution numbers 1,1,2,4,10,26,… repeat modulo $3$, $5$ and $7$. We explain this, and many similar patterns, by one rule. Many sequences count permutations in which every cycle of length m carries a weight wm (involutions, derangements, "sets of lists", and many others in the OEIS). Writing A(n) for such a count, the rule is A(n+k)≡ A(n)A(k) modulo lcm(n,k). It generalizes our earlier proof of the case modulo k for one such sequence, but now it holds for all weights at once, as a coefficientwise congruence between universal polynomials, and we find the largest modulus that works for the universal polynomials, nk/rad(gcd(n,k)), and show that nothing larger does. We then show that passing from k to pk behaves like raising to the p-th power modulo a high power of p, with a sharp exponent for the polynomials, which gives A(pr)≡(w1+(p−1)wp)pr−1 modulo pr for odd p, and explains why the prime $2$ is special. A family of sequences defined by Lagrange inversion fits the same framework, which proves Bala's conjecture for the whole family (the single sequence A278070 had been proved earlier by an automated system) and the divisibility observed in the entries A251568 and A251569. As further applications we prove OEIS conjectures of Richman, Hanna, van Hoeij and Bala (A227937), and the theorems apply to 101 OEIS sequences, whose congruences are recorded in a supplementary catalogue. Higher-order versions of the content formula are treated in a separate paper.
Related
- A Unified Framework for p-adic Congruences and p-adic Interpolations of Sequences
- Permutation XOR cellular automata: partial-shift connections and half-primitive polynomials
- Dyadic Structure of the Two-Block Odd Partition Function and Theta-Weighted Congruences for pod(n)
- Time-reliability optimization of multi-pass underfill dispensing sequences on printed circuit boards: a schedule-dependent reliability model solved by a multiset-permutation binary-addition-tree algorithm
- Profinite approach to S-adic shift spaces II: Invertible directive sequences
BibTeX
@misc{kallat2026universal,
title = {{Universal Shift Congruences for Weighted Permutation Sequences}},
author = {Ahaan Kallat},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15849},
eprint = {2610.15849},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15849},
}
RIS
TY - UNPB
TI - Universal Shift Congruences for Weighted Permutation Sequences
AU - Ahaan Kallat
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15849
UR - https://arxiv.org/abs/2610.15849
AB - The involution numbers 1,1,2,4,10,26,… repeat modulo $3$, $5$ and $7$. We explain this, and many similar patterns, by one rule. Many sequences count permutations in which every cycle of length m carries a weight w_m (involutions, derangements, "sets of lists", and many others in the OEIS). Writing A(n) for such a count, the rule is A(n+k)≡ A(n)A(k) modulo lcm(n,k). It generalizes our earlier proof of the case modulo k for one such sequence, but now it holds for all weights at once, as a coefficientwise congruence between universal polynomials, and we find the largest modulus that works for the universal polynomials, nk/rad(gcd(n,k)), and show that nothing larger does. We then show that passing from k to pk behaves like raising to the p-th power modulo a high power of p, with a sharp exponent for the polynomials, which gives A(p^r)≡(w_1+(p−1)w_p)^p^r−1 modulo p^r for odd p, and explains why the prime $2$ is special. A family of sequences defined by Lagrange inversion fits the same framework, which proves Bala's conjecture for the whole family (the single sequence A278070 had been proved earlier by an automated system) and the divisibility observed in the entries A251568 and A251569. As further applications we prove OEIS conjectures of Richman, Hanna, van Hoeij and Bala (A227937), and the theorems apply to 101 OEIS sequences, whose congruences are recorded in a supplementary catalogue. Higher-order versions of the content formula are treated in a separate paper.
ER -