The Sequence Reconstruction of Permutations under Hamming Metric with Small Errors
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917188339761152 |
|---|---|
| author | Abdollahi, A. Bagherian, J. Eskandari, H. Jafari, F. Khatami, M. Parvaresh, F. Sobhani, R. |
| author_facet | Abdollahi, A. Bagherian, J. Eskandari, H. Jafari, F. Khatami, M. Parvaresh, F. Sobhani, R. |
| contents | 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)\). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_02844 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Sequence Reconstruction of Permutations under Hamming Metric with Small Errors Abdollahi, A. Bagherian, J. Eskandari, H. Jafari, F. Khatami, M. Parvaresh, F. Sobhani, R. Group Theory Information Theory Combinatorics 94B25, 68P30, 94A15 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)\). |
| title | The Sequence Reconstruction of Permutations under Hamming Metric with Small Errors |
| topic | Group Theory Information Theory Combinatorics 94B25, 68P30, 94A15 |
| url | https://arxiv.org/abs/2601.02844 |