The Sequence Reconstruction of Permutations under Hamming Metric with Small Errors

A. Abdollahi, J. Bagherian, H. Eskandari, F. Jafari, M. Khatami, F. Parvaresh, R. Sobhani

arXivarxiv/2601.02844Jan 6, 2026math.GRscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2601.02844
curl -X POST /api/v1/records/arxiv/2601.02844/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.02844/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'