The Sequence Reconstruction of Permutations under Hamming Metric with Small Errors
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _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 |