pith. sign in

arxiv: 2606.09158 · v1 · pith:RUVVBUJEnew · submitted 2026-06-08 · 🧮 math.CO · cs.DM

The Size of the Intersection of q-ary Hamming Balls

Ville Junnila , Tero Laihonen , Tuomo Lehtil\"a , Pavan Padavu Devaraj This is my paper

Pith reviewed 2026-06-27 16:32 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords Hamming ballsintersection cardinalityq-ary codescombinatorial enumerationDNA data storageball intersectionscoding theory
0
0 comments X

The pith

An exact formula determines the size of the intersection of s q-ary Hamming balls once centers satisfy specific structural alignments beyond pairwise distances.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives an exact formula for the number of sequences that lie inside every one of s Hamming balls of given radii in q-ary space of length n. Pairwise distances between the centers prove insufficient to fix this number, so the work isolates the additional coordinate-wise agreement patterns among the centers that make the intersection size unique. The result matters for DNA-based storage, where overlapping balls represent possible read sets and their sizes affect code design. For three balls with a prescribed minimum distance between centers, the formula supplies necessary and sufficient conditions that achieve the largest possible intersection when n is large and q is not 6.

Core claim

The authors present an exact formula for the cardinality of the intersection of s Hamming balls of varying radii over a q-ary alphabet. It is known that the distances between the center points are not enough, in general, to determine the size of the intersection. Based on the formula, more refined structural properties of the center points are identified that determine the exact size. For s=3 the necessary and sufficient conditions are given to obtain the maximum size under a given minimum distance when n is sufficiently large (for all q≥2, q≠6).

What carries the argument

The exact intersection cardinality formula, which counts points according to their per-coordinate agreement patterns with the centers and requires the centers to satisfy additional alignment conditions identified by the formula itself.

If this is right

  • The intersection cardinality is fixed once the centers meet the structural conditions the formula extracts.
  • For three centers with fixed minimum distance the largest intersection occurs precisely when those structural conditions hold, for large n and q not equal to 6.
  • The formula permits direct computation of the intersection size for any centers obeying the required properties.
  • Asymptotic behavior of the intersection size is determined for sufficiently large n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The formula supplies an explicit way to evaluate inclusion-exclusion terms when bounding unions of Hamming balls.
  • It could be used to optimize the placement of multiple reference sequences in DNA storage so that their common coverage region is maximized under distance constraints.
  • Small-length instances can be enumerated by computer and checked against the formula to confirm the structural conditions.

Load-bearing premise

The centers must satisfy additional structural properties beyond pairwise distances, properties that the formula itself identifies, in order for the intersection size to be uniquely determined.

What would settle it

A pair of center configurations that agree on all the structural properties named by the formula yet produce different intersection cardinalities, or a small-n example where the formula output differs from direct enumeration.

Figures

Figures reproduced from arXiv: 2606.09158 by Pavan Padavu Devaraj, Tero Laihonen, Tuomo Lehtil\"a, Ville Junnila.

Figure 1
Figure 1. Figure 1: The intersection IT (S) of three balls centered at words c 1 , c 2 and c 3 with pairwise distances d1, d2 and d3, where T = (t1, t2, t3). Let S = {c 1 , c 2 , . . . , c s} be a subset of Z n q and T = (t1, t2, . . . , ts) be a list of nonnegative integers. For the rest of the paper, we make the natural assumption that tm ≤ n for each m ∈ [1, s]. The intersection of the Hamming balls Btm(c m) (m ∈ [1, s]) i… view at source ↗
read the original abstract

The interest in studying the size of the intersection of multiple $q$-ary Hamming balls has grown due to the recent advances in DNA-based data storage systems. We present an exact formula for the cardinality of the intersection of $s$ Hamming balls of varying radii over a $q$-ary alphabet. It is known that the distances between the center points of the Hamming balls are not enough, in general, to determine the size of the intersection. Based on our formula, we are able to find more refined structural properties of the center points for determining the exact size of the intersection. Moreover, we also analyze the size of the intersection for sufficiently large $n$. When $s=3$, we give the necessary and sufficient conditions (for all $q\ge 2$, $q\neq 6$ and sufficiently large $n$) to obtain the maximum size of the intersection when the center points of the Hamming balls have a given minimum distance and demonstrate how to compute it using our general formula.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript presents an exact formula for the cardinality of the intersection of s Hamming balls of varying radii over a q-ary alphabet. It observes that pairwise distances between centers are generally insufficient to determine the intersection size and uses the formula to identify additional structural properties of the centers that suffice for uniqueness. For s=3, the paper gives necessary and sufficient conditions (for q≥2, q≠6 and sufficiently large n) under which the intersection attains its maximum size given a prescribed minimum distance among the centers, and shows how to evaluate the size via the general formula. Asymptotic analysis for large n is also included.

Significance. An explicit, closed-form expression for multi-ball intersections in the q-ary Hamming metric would be a useful addition to coding theory, especially given the motivating application to DNA storage. The refinement of the center-configuration data beyond pairwise distances addresses a known limitation and, if the derivation is correct, supplies a concrete combinatorial tool. The s=3 maximality conditions for large n are a concrete, falsifiable output that could be checked against small cases or simulations.

major comments (1)
  1. [Abstract, §1] Abstract and §1: the central claim is the existence and utility of an exact formula, yet the provided text supplies neither the formula itself nor its derivation; without these it is impossible to verify correctness, scope, or whether the formula is parameter-free or reduces to enumeration.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed review and insightful comments on our manuscript. We address the major comment below.

read point-by-point responses

  1. Referee: [Abstract, §1] Abstract and §1: the central claim is the existence and utility of an exact formula, yet the provided text supplies neither the formula itself nor its derivation; without these it is impossible to verify correctness, scope, or whether the formula is parameter-free or reduces to enumeration.

    Authors: The exact formula for the cardinality of the intersection and its derivation are presented in Section 2 of the full manuscript, with applications and further analysis in subsequent sections. The abstract and introduction provide a high-level overview, which is standard practice. However, to facilitate verification as noted by the referee, we will revise the introduction (§1) to include an explicit statement of the main formula. This will make the central result more immediately accessible without altering the structure. revision: yes

Circularity Check

0 steps flagged

No significant circularity; formula derived by direct enumeration

full rationale

The paper states it presents an exact formula obtained via combinatorial enumeration of the intersection of q-ary Hamming balls. The abstract explicitly notes that pairwise distances are insufficient and that the formula itself identifies the additional structural properties needed for uniqueness; this is a forward derivation rather than a reduction to fitted inputs or self-referential definitions. No load-bearing self-citations, ansatzes smuggled via prior work, or renamings of known results are indicated in the provided material. The central claim remains self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard combinatorial counting over finite alphabets and the definition of Hamming distance; no free parameters, invented entities, or non-standard axioms are indicated in the abstract.

axioms (1)
  • standard math Standard rules for counting strings over a finite alphabet with position-wise symbol agreements and disagreements
    Any exact intersection formula for Hamming balls must invoke these counting principles.

pith-pipeline@v0.9.1-grok · 5720 in / 1145 out tokens · 25075 ms · 2026-06-27T16:32:00.979593+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 7 canonical work pages

  1. [1]

    On the intersections ofq-ary Hamming balls,

    V . Junnila, T. Laihonen, T. Lehtil¨a, and P. D. Pavan, “On the intersections ofq-ary Hamming balls,” in2025 IEEE Information Theory Workshop (ITW), 2025, pp. 1–6

    2025

  2. [2]

    Exact size of intersections of Hamming balls inZ n q ,

    ——, “Exact size of intersections of Hamming balls inZ n q ,” inProceedings of 2026 IEEE International Symposium on Information Theory (ISIT), 2026

    2026

  3. [3]

    Efficient reconstruction of sequences,

    V . I. Levenshtein, “Efficient reconstruction of sequences,”IEEE Trans. Inform. Theory, vol. 47, no. 1, pp. 2–22, 2001

    2001

  4. [4]

    On the uncertainty of information retrieval in associative memories,

    E. Yaakobi and J. Bruck, “On the uncertainty of information retrieval in associative memories,”IEEE Trans. Inform. Theory, vol. 65, no. 4, pp. 2155–2165, 2018

    2018

  5. [5]

    On the number of error correcting codes,

    D. Dong, N. Mani, and Y . Zhao, “On the number of error correcting codes,”Combinatorics, Probability and Computing, vol. 32, no. 5, pp. 819–832, 2023

    2023

  6. [6]

    Cohen, I

    G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein,Covering Codes. Elsevier, 1997

    1997

  7. [7]

    On the intersections and unions of Hamming spheres,

    I. Honkala, “On the intersections and unions of Hamming spheres,” in a collection: The Very Knowledge of Coding, studies in honor of Aimo Tiet ¨av¨ainen on the occasion of his fiftieth birthday July 6, 1987, editors Laakso and Salomaa, pp. 70–81, 1987

    1987

  8. [8]

    On Levenshtein’s channel and list size in information retrieval,

    V . Junnila, T. Laihonen, and T. Lehtil¨a, “On Levenshtein’s channel and list size in information retrieval,”IEEE Trans. Inform. Theory, vol. 67, no. 6, pp. 3322–3341, 2020

    2020

  9. [9]

    Levenshtein’s sequence reconstruction problem and results for larger alphabet sizes,

    ——, “Levenshtein’s sequence reconstruction problem and results for larger alphabet sizes,”Theoretical Computer Science, vol. 1045, p. 115279, 2025

    2025

  10. [10]

    The Levenshtein’s sequence reconstruction problem and the length of the list,

    ——, “The Levenshtein’s sequence reconstruction problem and the length of the list,”IEEE Trans. Inform. Theory, vol. 70, no. 2, pp. 1050–1066, 2024. 23

    2024

  11. [11]

    Reconstruction from deletions in racetrack memories,

    Y . M. Chee, R. Gabrys, A. Vardy, V . K. Vu, and E. Yaakobi, “Reconstruction from deletions in racetrack memories,” in2018 IEEE Information Theory Workshop (ITW). IEEE, 2018, pp. 1–5

    2018

  12. [12]

    On Levenshtein’s reconstruction problem under insertions, deletions, and substitutions,

    M. Abu-Sini and E. Yaakobi, “On Levenshtein’s reconstruction problem under insertions, deletions, and substitutions,”IEEE Trans. Inform. Theory, vol. 67, no. 11, pp. 7132–7158, 2021

    2021

  13. [13]

    A characterization of the DNA data storage channel,

    R. Heckel, G. Mikutis, and R. N. Grass, “A characterization of the DNA data storage channel,”Scientific reports, vol. 9, no. 1, pp. 1–12, 2019

    2019

  14. [14]

    On the intersection of multiple insertion (or deletion) balls and its application to list decoding under the reconstruction model,

    M. Abu-Sini and E. Yaakobi, “On the intersection of multiple insertion (or deletion) balls and its application to list decoding under the reconstruction model,”IEEE Trans. Inform. Theory, vol. 70, no. 5, pp. 3262–3297, 2024

    2024

  15. [15]

    High-capacity digital polymers: storing images in single molecules,

    E. Laurent, J.-A. Amalian, M. Parmentier, L. Oswald, A. Al Ouahabi, F. Dufour, K. Launay, J.-L. Cl ´ement, D. Gigmes, M.-A. Delsucet al., “High-capacity digital polymers: storing images in single molecules,”Macromolecules, vol. 53, no. 10, pp. 4022–4029, 2020

    2020

  16. [16]

    String reconstruction from substring compositions,

    J. Acharya, H. Das, O. Milenkovic, A. Orlitsky, and S. Pan, “String reconstruction from substring compositions,”SIAM J. Discrete Math., vol. 29, no. 3, pp. 1340–1371, 2015. [Online]. Available: https://doi.org/10.1137/140962486

    work page doi:10.1137/140962486 2015

  17. [17]

    List decoding of error-correcting codes: Winning thesis of the 2002 ACM doctoral dissertation competition,

    V . Guruswami, “List decoding of error-correcting codes: Winning thesis of the 2002 ACM doctoral dissertation competition,” Lecture notes in computer science, 2004

    2002

  18. [18]

    R. E. Blahut,Theory and practice of error control codes. Addison-Wesley Publishing Company, 1983

    1983

  19. [19]

    Strengthening the Gilbert–Varshamov bound,

    A. Barg, S. Guritman, and J. Simonis, “Strengthening the Gilbert–Varshamov bound,”Linear Algebra and its Applications, vol. 307, no. 1-3, pp. 119–129, 2000

    2000

  20. [20]

    Applications of graph containers in the Boolean lattice,

    J. Balogh, A. Treglown, and A. Z. Wagner, “Applications of graph containers in the Boolean lattice,”Random Structures & Algorithms, vol. 49, no. 4, pp. 845–872, 2016

    2016

  21. [21]

    Exponential decay of intersection volume with applications on list-decodability and Gilbert- Varshamov type bound,

    J. Kim, H. Liu, and T. Tran, “Exponential decay of intersection volume with applications on list-decodability and Gilbert- Varshamov type bound,”IEEE Transactions on Information Theory, vol. 69, no. 5, pp. 2841–2854, 2022

    2022

  22. [22]

    Deriving shape space parameters from immunological data,

    D. J. Smith, S. Forrest, R. R. Hightower, and A. S. Perelson, “Deriving shape space parameters from immunological data,” Journal of theoretical biology, vol. 189, no. 2, pp. 141–150, 1997

    1997

  23. [23]

    The Helly number of Hamming balls and related problems,

    N. Alon, Z. Jin, and B. Sudakov, “The Helly number of Hamming balls and related problems,”arXiv preprint arXiv:2405.10275, 2024

    arXiv 2024

  24. [24]

    ¨Uber Mengen konvexer K ¨orper mit gemeinschaftlichen Punkte,

    E. Helly, “ ¨Uber Mengen konvexer K ¨orper mit gemeinschaftlichen Punkte,”Jahresbericht der Deutschen Mathematiker- Vereinigung, vol. 32, pp. 175–176, 1923

    1923

  25. [25]

    Deza,Stirling numbers, ser

    E. Deza,Stirling numbers, ser. Selected Chapters of Number Theory: Special Numbers. World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, [2024] ©2024, vol. 3. [Online]. Available: https://doi.org/10.1142/13463

    work page doi:10.1142/13463 2024

  26. [26]

    The Stirling numbers of the second kind and their applications,

    S. Bagui and K. Mehra, “The Stirling numbers of the second kind and their applications,”Alabama Journal of Mathematics, vol. 47, no. 1, pp. 1–22, 2024

    2024

  27. [27]

    Pseudo-partitions, transversality and locality: A combinatorial characterization for the space measure in algebraic proof systems,

    I. Bonacina and N. Galesi, “Pseudo-partitions, transversality and locality: A combinatorial characterization for the space measure in algebraic proof systems,” inProceedings of the 4th Innovations in Theoretical Computer Science Conference (ITCS). Berkeley, California, USA: ACM, 2013, pp. 455–471. [Online]. Available: https://doi.org/10.1145/2422436.2422486

    work page doi:10.1145/2422436.2422486 2013

  28. [28]

    Fourier-Motzkin elimination and its dual,

    G. B. Dantzig and B. C. Eaves, “Fourier-Motzkin elimination and its dual,”J. Combinatorial Theory Ser. A, vol. 14, pp. 288–297, 1973. [Online]. Available: https://doi.org/10.1016/0097-3165(73)90004-6

    work page doi:10.1016/0097-3165(73)90004-6 1973

  29. [29]

    Cohen, I

    G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein,Covering codes, ser. North-Holland Mathematical Library. Amsterdam: North-Holland Publishing Co., 1997, vol. 54

    1997

  30. [30]

    A. E. Brouwer, A. M. Cohen, and A. Neumaier,Distance-regular graphs, ser. Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1989, vol. 18. [Online]. Available: https://doi.org/10.1007/978-3-642-74341-2

    work page doi:10.1007/978-3-642-74341-2 1989

  31. [31]

    Levin,Discrete mathematics: An open introduction, 3rd ed

    O. Levin,Discrete mathematics: An open introduction, 3rd ed. Chapman and Hall/CRC, 2025

    2025

  32. [32]

    Fast computation of multinomial coefficients,

    L. C. Araujo, J. a. P. H. Sans ˜ao, and A. S. Vale-Cardoso, “Fast computation of multinomial coefficients,”Numer. Algorithms, vol. 88, no. 2, pp. 837–851, 2021. [Online]. Available: https://doi.org/10.1007/s11075-020-01059-5

    work page doi:10.1007/s11075-020-01059-5 2021

  33. [33]

    Integer multiplication in timeO(nlogn),

    D. Harvey and J. van der Hoeven, “Integer multiplication in timeO(nlogn),”Ann. of Math. (2), vol. 193, no. 2, pp. 563–617, 2021. [Online]. Available: https://doi.org/10.4007/annals.2021.193.2.4

    work page doi:10.4007/annals.2021.193.2.4 2021