The Sequence Reconstruction of Permutations under Hamming Metric with Small Errors
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |