List Reconstruction Problem with List Size Two

(2) National University of Singapore; Binh Vu (1); Hanoi; Shuche Wang (2); Singapore); Van Khu Vu (1) ((1) VinUniversity; Vietnam

arxiv: 2605.23638 · v1 · pith:PACQVE5Fnew · submitted 2026-05-22 · 🧮 math.CO · cs.IT· math.IT

List Reconstruction Problem with List Size Two

Binh Vu (1) , Shuche Wang (2) , Van Khu Vu (1) ((1) VinUniversity , Hanoi , Vietnam , (2) National University of Singapore , Singapore) This is my paper

Pith reviewed 2026-05-25 04:07 UTC · model grok-4.3

classification 🧮 math.CO cs.ITmath.IT

keywords Hamming ballsintersection cardinalityasymptotic ratelist reconstructionHamming spacecoding theoryassociative memorieslinear scaling

0 comments

The pith

The maximum asymptotic rate of three Hamming-ball intersections is expressed explicitly as a function of the linear scaling parameters α and β.

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

This paper studies the cardinality of intersections among three balls in the Hamming space when both the radius of each ball and the distance between centers grow linearly with block length n. It derives the largest possible exponential growth rate of such intersections under these scalings. A sympathetic reader would care because the resulting rate governs whether list-reconstruction algorithms remain feasible when a constant fraction of symbols are erroneous. The derivation extends earlier fixed-parameter results to the linear-error regime that arises in large-block coding and associative-memory applications.

Core claim

When each ball has radius αn and the three centers are pairwise distance βn apart, the largest asymptotic rate of the intersection size is given by an explicit function of the two parameters α and β.

What carries the argument

The asymptotic rate of the triple intersection cardinality under linear radius and distance scaling.

If this is right

The rate supplies an upper bound on the size of any list that can be reconstructed from three noisy versions of a codeword when error fractions are constant.
Numerical evaluation of the function shows how the three-ball rate relates to the known two-ball intersection rate.
The expression permits direct comparison of reconstructibility thresholds across different linear error regimes.

Where Pith is reading between the lines

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

The same scaling approach could be applied to intersections of four or more balls to treat list sizes larger than two.
Phase transitions in the rate function might mark sharp changes in the feasibility of linear-error list reconstruction.
The derived rate could be used to test whether particular code constructions achieve the predicted intersection sizes.

Load-bearing premise

The radii and inter-center distances must scale exactly linearly with block length so that a well-defined limiting rate exists as n tends to infinity.

What would settle it

An explicit computation, for any fixed α and β, of the exact exponential growth rate of a concrete triple intersection that differs from the claimed function.

Figures

Figures reproduced from arXiv: 2605.23638 by (2) National University of Singapore, Binh Vu (1), Hanoi, Shuche Wang (2), Singapore), Van Khu Vu (1) ((1) VinUniversity, Vietnam.

read the original abstract

The problem of computing the cardinality of the intersection of multiple balls in the Hamming space has attracted a lot of attention recently due to their applications in the list reconstruction problem and information retrieval in Associative Memories. In previous work, most of the results are for the cases where the radii of each ball, $r$ and the distance between the centers of these balls, $k$ are fixed when the length $n$ of each codeword tend to infinity. In this work, we focus on the case where $r = \alpha n$ and $k=\beta n$ for some constants $\alpha$ and $\beta$ and compute the maximum asymptotic rate of the cardinality of the intersection of three balls. We provide the maximum asymptotic rate as a function of two parameters $\alpha$ and $\beta$. We also provide numerical results and compare these results with the intersection of two balls.

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.

Desk Editor's Note private letter to a colleague

The paper gives an explicit asymptotic rate for the intersection of three Hamming balls when radii and center distances both scale linearly with n.

read the letter

The main point is that the authors compute the maximum asymptotic rate of |B(x, αn) ∩ B(y, αn) ∩ B(z, αn)| when the pairwise distances are βn, and they express that rate as a function of α and β. This moves beyond the fixed-r-and-k setting that dominated earlier work on the same intersection problem. They also run numerical comparisons against the two-ball case, which is useful for seeing how the extra ball affects the rate. The linear-scaling regime is the natural one for applications in list reconstruction, so the extension itself is the right direction. The derivation is not shown in the abstract, so the real test is whether the counting or optimization argument in the full text actually yields a clean, computable expression without hidden fitting or loose bounds. The existence of the limit follows from standard subadditivity or type-counting arguments, so that part looks solid. This is a narrow but concrete result aimed at people who need multi-ball intersection sizes for coding-theory bounds or associative-memory analysis. A reader working on list-decoding rates in the linear regime will get direct use out of the formula and the plots. It is worth sending to peer review because the claim is specific, the regime is standard, and the comparison to the two-ball case adds a small but clear incremental value.

Referee Report

2 major / 2 minor

Summary. The manuscript studies the asymptotic rate of the intersection of three Hamming balls of radius αn whose centers are pairwise at distance βn. It claims to derive and provide the maximum such rate (i.e., lim (1/n) log |B(x,αn) ∩ B(y,αn) ∩ B(z,αn)|) explicitly as a function of the two parameters α and β, extending prior fixed-parameter results, and supplies numerical comparisons with the two-ball case.

Significance. If the claimed explicit rate function is correctly obtained from a combinatorial argument (e.g., via types or subadditivity), the result supplies a concrete extension of ball-intersection cardinality bounds to the linear-scaling regime that is directly applicable to list-reconstruction and associative-memory problems.

major comments (2)

[Abstract] Abstract: the central claim is that an explicit maximum asymptotic rate is provided as a function of α and β, yet neither the closed-form expression nor the optimization problem (or type-distribution program) that yields it appears in the abstract or is summarized; without this the combinatorial derivation cannot be verified from the supplied text.
[Main result section] Main result (presumably §3 or §4): the existence of the normalized log-cardinality limit is asserted under linear scaling, but the manuscript must state whether the rate is obtained by a concrete optimization over joint types on three centers or by some other explicit counting argument; the current presentation leaves this step opaque.

minor comments (2)

[Title/Abstract] Title refers to 'List Size Two' while the abstract and claim concern the intersection of three balls; a brief sentence clarifying why three centers are required for list size two would remove ambiguity.
[Numerical results] Numerical results section: the comparison with the two-ball intersection should include the precise parameter values of α and β used in the plots and state whether the three-ball rate is always strictly smaller.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and will incorporate revisions to improve clarity.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim is that an explicit maximum asymptotic rate is provided as a function of α and β, yet neither the closed-form expression nor the optimization problem (or type-distribution program) that yields it appears in the abstract or is summarized; without this the combinatorial derivation cannot be verified from the supplied text.

Authors: We agree that the abstract would benefit from a more explicit summary of the rate. The manuscript derives the rate via an optimization over joint types, but the abstract presents only a high-level statement. In the revision we will expand the abstract to include a concise description of the optimization program (over the joint type distribution of the three centers) that defines the asymptotic rate as a function of α and β. revision: yes
Referee: [Main result section] Main result (presumably §3 or §4): the existence of the normalized log-cardinality limit is asserted under linear scaling, but the manuscript must state whether the rate is obtained by a concrete optimization over joint types on three centers or by some other explicit counting argument; the current presentation leaves this step opaque.

Authors: The rate is obtained by a concrete optimization over joint types on the three centers (via the method of types). We acknowledge that the current text does not state this derivation step with sufficient explicitness. In the revised manuscript we will add a clear statement in the main result section identifying the optimization program and briefly outlining the combinatorial argument that establishes the limit. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives an explicit expression for the maximum asymptotic rate of the intersection cardinality of three Hamming balls under linear scaling r=αn and k=βn. This is obtained via standard combinatorial or information-theoretic optimization over types (as is conventional for such normalized log-volumes), with the result stated directly as a function of the two parameters α and β; no equation reduces the claimed rate to a fitted input, a self-referential definition, or a load-bearing self-citation. The additional numerical comparison to the two-ball case is presented as an independent verification step rather than a definitional tautology.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of an asymptotic rate limit under linear scaling and on standard combinatorial counting in the Hamming metric; no free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption The limit (1/n) log |intersection of three balls| exists and is finite for r = αn, k = βn.
Invoked to define the maximum asymptotic rate as a function of α and β.

pith-pipeline@v0.9.0 · 5700 in / 1090 out tokens · 33953 ms · 2026-05-25T04:07:13.761346+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

f3(α, β) = max_{(θ,δ)∈Dα,β} Φα,β(θ, δ) where Φ = (β/2)H(p1(θ)) + β H(p23(θ,δ)) + (1-3β/2)H(p4(θ,δ))

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

Efficient reconstruction of sequences,

V . I. Levenshtein, “Efficient reconstruction of sequences,”IEEE Trans- actions on Information Theory, vol. 47, no. 1, pp. 2–22, 2002

work page 2002
[2]

Information retrieval with varying number of input clues,

V . Junnila and T. Laihonen, “Information retrieval with varying number of input clues,”IEEE Transactions on Information Theory, vol. 62, no. 2, pp. 625–638, 2015

work page 2015
[3]

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

V . Junnila, T. Laihonen, and T. Lehtil ¨a, “The levenshtein’s sequence reconstruction problem and the length of the list,”IEEE Transactions on Information Theory, vol. 70, no. 2, pp. 1050–1066, 2023

work page 2023
[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 Transactions on Information Theory, vol. 65, no. 4, pp. 2155–2165, 2018

work page 2018
[5]

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 Transactions on Information Theory, vol. 67, no. 6, pp. 3322–3341, 2020

work page 2020
[6]

On the intersections of q-ary hamming balls,

V . Junnila, T. K. Laihonen, T. Lehtil ¨a, and P. P. Devaraj, “On the intersections of q-ary hamming balls,” in2025 IEEE Information Theory Workshop (ITW). IEEE, 2025, pp. 1–6

work page 2025
[7]

On list decoding of insertions and deletions under the reconstruction model,

M. Abu-Sini and E. Yaakobi, “On list decoding of insertions and deletions under the reconstruction model,” in2021 IEEE International Symposium on Information Theory (ISIT). IEEE, 2021, pp. 1706–1711

work page 2021
[8]

On levenshtein’s reconstruction problem under insertions, dele- tions, and substitutions,

——, “On levenshtein’s reconstruction problem under insertions, dele- tions, and substitutions,”IEEE Transactions on Information Theory, vol. 67, no. 11, pp. 7132–7158, 2021

work page 2021
[9]

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

——, “On the intersection of multiple insertion (or deletion) balls and its application to list decoding under the reconstruction model,”IEEE Transactions on Information Theory, vol. 70, no. 5, pp. 3262–3297, 2023

work page 2023
[10]

Asymptotic improvement of the gilbert- varshamov bound on the size of binary codes,

T. Jiang and A. Vardy, “Asymptotic improvement of the gilbert- varshamov bound on the size of binary codes,”IEEE Transactions on Information Theory, vol. 50, no. 8, pp. 1655–1664, 2004

work page 2004
[11]

Improving the gilbert-varshamov bound for q-ary codes,

V . Vu and L. Wu, “Improving the gilbert-varshamov bound for q-ary codes,”IEEE transactions on information theory, vol. 51, no. 9, pp. 3200–3208, 2005

work page 2005
[12]

Exponential decay of intersection vol- ume with applications on list-decodability and gilbert-varshamov type bound,

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

work page 2022
[13]

Cohen, I

G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein,Covering codes. Elsevier, 1997, vol. 54

work page 1997
[14]

On the intersection and unions of hamming spheres,

I. Honkala, “On the intersection and unions of hamming spheres,”The very knowledge of coding, pp. 70–81, 1987

work page 1987

[1] [1]

Efficient reconstruction of sequences,

V . I. Levenshtein, “Efficient reconstruction of sequences,”IEEE Trans- actions on Information Theory, vol. 47, no. 1, pp. 2–22, 2002

work page 2002

[2] [2]

Information retrieval with varying number of input clues,

V . Junnila and T. Laihonen, “Information retrieval with varying number of input clues,”IEEE Transactions on Information Theory, vol. 62, no. 2, pp. 625–638, 2015

work page 2015

[3] [3]

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

V . Junnila, T. Laihonen, and T. Lehtil ¨a, “The levenshtein’s sequence reconstruction problem and the length of the list,”IEEE Transactions on Information Theory, vol. 70, no. 2, pp. 1050–1066, 2023

work page 2023

[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 Transactions on Information Theory, vol. 65, no. 4, pp. 2155–2165, 2018

work page 2018

[5] [5]

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 Transactions on Information Theory, vol. 67, no. 6, pp. 3322–3341, 2020

work page 2020

[6] [6]

On the intersections of q-ary hamming balls,

V . Junnila, T. K. Laihonen, T. Lehtil ¨a, and P. P. Devaraj, “On the intersections of q-ary hamming balls,” in2025 IEEE Information Theory Workshop (ITW). IEEE, 2025, pp. 1–6

work page 2025

[7] [7]

On list decoding of insertions and deletions under the reconstruction model,

M. Abu-Sini and E. Yaakobi, “On list decoding of insertions and deletions under the reconstruction model,” in2021 IEEE International Symposium on Information Theory (ISIT). IEEE, 2021, pp. 1706–1711

work page 2021

[8] [8]

On levenshtein’s reconstruction problem under insertions, dele- tions, and substitutions,

——, “On levenshtein’s reconstruction problem under insertions, dele- tions, and substitutions,”IEEE Transactions on Information Theory, vol. 67, no. 11, pp. 7132–7158, 2021

work page 2021

[9] [9]

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

——, “On the intersection of multiple insertion (or deletion) balls and its application to list decoding under the reconstruction model,”IEEE Transactions on Information Theory, vol. 70, no. 5, pp. 3262–3297, 2023

work page 2023

[10] [10]

Asymptotic improvement of the gilbert- varshamov bound on the size of binary codes,

T. Jiang and A. Vardy, “Asymptotic improvement of the gilbert- varshamov bound on the size of binary codes,”IEEE Transactions on Information Theory, vol. 50, no. 8, pp. 1655–1664, 2004

work page 2004

[11] [11]

Improving the gilbert-varshamov bound for q-ary codes,

V . Vu and L. Wu, “Improving the gilbert-varshamov bound for q-ary codes,”IEEE transactions on information theory, vol. 51, no. 9, pp. 3200–3208, 2005

work page 2005

[12] [12]

Exponential decay of intersection vol- ume with applications on list-decodability and gilbert-varshamov type bound,

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

work page 2022

[13] [13]

Cohen, I

G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein,Covering codes. Elsevier, 1997, vol. 54

work page 1997

[14] [14]

On the intersection and unions of hamming spheres,

I. Honkala, “On the intersection and unions of hamming spheres,”The very knowledge of coding, pp. 70–81, 1987

work page 1987