The Sequence Reconstruction of Permutations under Hamming Metric with Small Errors

The sequence reconstruction problem asks for the recovery of a sequence from multiple noisy copies, where each copy may contain up to $r$ errors. In the case of permutations on $n$ letters under the Hamming metric, this problem is closely related to the parameter $N(n,r)$, the maximum intersection size of two Hamming balls of radius $r$. While previous work has resolved $N(n,r)$ for small radii ($r \leq 4$) and established asymptotic bounds for larger $r$, we present new exact formulas for $r \in \{5,6,7\}$ using group action techniques. In addition, we develop a formula for $N(n,r)$ based on the irreducible characters of the symmetric group $S_n$, along with an algorithm that enables computation of $N(n,r)$ for larger parameters, including cases such as $N(43,8)$ and $N(24,14)$.

No reviews yet.

No comments yet.