A Note on Second-Order Expected Maximum-Load Bounds for Binary Linear Hashing

Nader H. Bshouty

arxiv: 2605.18335 · v1 · pith:FXOE74RNnew · submitted 2026-05-18 · 💻 cs.DS

A Note on Second-Order Expected Maximum-Load Bounds for Binary Linear Hashing

Nader H. Bshouty This is my paper

Pith reviewed 2026-05-19 23:47 UTC · model grok-4.3

classification 💻 cs.DS

keywords binary linear hashingmaximum loadtail boundsexpected maximum loadrandom linear mapssecond-order asymptoticskeys-into-bins

0 comments

The pith

Binary linear hashing matches fully independent hashing on the second-order term in expected maximum load.

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

The paper improves the tail bound on the maximum load M of a random linear map h from F2^u to F2^ℓ applied to a set S of size n=2^ℓ. For R>1 satisfying R ℓ^{1-1/R} ≥ D ln ℓ, the probability that M exceeds R log n / log log n is bounded by O((log log n)^2 / (R^2 (log n)^{2-2/R})). Integrating the tail produces the expectation bound E[M] ≤ (1 + (1+o(1)) log log log n / log log n) * log n / log log n. This places binary linear hashing on equal footing with fully random hashing through the leading term and the dominant second-order correction.

Core claim

By performing a base optimization of the exponential-potential method introduced in Jaber et al. (STOC 2025), the note derives a tail bound with improved exponent 2-2/R in the denominator for the probability that the maximum load exceeds R log n / log log n. This yields an integrated expectation that matches the fully independent case up to a (1+o(1)) factor in the second-order term log log log n / log log n. A separate argument also supplies a sharp single-bucket tail Pr[Load_h(y) > 2^a - 2] ≤ γ^{-1} 2^{-a^2} that is asymptotically tight by a subspace construction.

What carries the argument

Optimized exponential-potential function whose base case produces the tail exponent 2-2/R without extra error terms

If this is right

Expected maximum load matches the fully independent scale through both the leading log n / log log n term and the dominant correction (1+o(1)) log log log n / log log n.
The same optimized potential yields a tail that is polynomially small in 1/R and super-polynomially small in n.
A separate self-contained argument gives a sharp constant-factor tail for any fixed bucket that is tight by explicit subspace examples.
Union bounds over all buckets lose the 2^ℓ factor, so the single-bucket result does not directly imply the global maximum-load bound.

Where Pith is reading between the lines

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

Applications that previously required fully random hashing for second-order load guarantees may now safely substitute linear hashing over GF(2).
The same optimization technique could be tested on linear maps over larger fields or on higher-moment bounds for the load distribution.
If the single-bucket tail can be derandomized or combined with limited-independence arguments, it might yield efficient constructions with explicit second-order guarantees.

Load-bearing premise

The optimization step in the exponential-potential analysis can be executed without introducing new error terms that would spoil the improved 2-2/R exponent.

What would settle it

Compute or simulate the exact tail probability Pr[M ≥ R log n / log log n] for concrete large ℓ and R satisfying the hypothesis, and check whether it decays at the claimed rate (log n)^{2-2/R} rather than staying constant in R.

read the original abstract

Let $S\subseteq F_2^u$ have size $n=2^\ell$, and let $h:F_2^u\to F_2^\ell$ be a uniformly random linear map. For $y\in F_2^\ell$, write $Load_h(y):=|h^{-1}(y)\cap S|$, and let $M(S,h):=\max_{y\in F_2^\ell} Load_h(y)$ be the maximum load. Jaber, Kumar and Zuckerman (STOC 2025) proved that the expected maximum load of $h$ on $S$ is at most $16\log n/\log\log n$, matching the fully independent keys-into-bins scale up to constants. Their proof also gives the tail estimate \[ \Pr\left[ M(S,h)\ge R\frac{\log n}{\log\log n} \right] \le O\left(\frac{1}{R^{2}}\right). \] We record a base optimization in their exponential-potential method showing that binary linear hashing nearly matches fully independent hashing also at the level of the second-order maximum-load scale. For every $R>1$ satisfying $R\ell^{1-1/R}\ge D\ln\ell$, where $D$ is an absolute constant, we prove \[ \Pr\left[ M(S,h)\ge R\frac{\log n}{\log\log n} \right] \le O\left( \frac{(\log\log n)^2}{R^2(\log n)^{2-2/R}} \right). \] Integrating this tail yields \[ E[M(S,h)] \le \left( 1+ (1+o(1)) \frac{\log\log\log n}{\log\log n} \right) \frac{\log n}{\log\log n}. \] Thus binary linear hashing matches fully independent hashing in the leading term and matches the dominant second-order correction up to a $1+o(1)$ factor. We also prove, by an independent self-contained argument, a sharp tail bound for one prescribed bucket: for fixed $y\in F_2^\ell$, \[ \Pr[ Load_h(y)>2^a-2]\le \gamma^{-1}2^{-a^2}, \] where $ \gamma=\prod_{j\ge1}(1-2^{-j}) $. A subspace construction shows that this is asymptotically tight even in the leading constant as $ a\to\infty $. However, this controls only a fixed bucket; a direct union bound over all buckets loses a factor $ 2^\ell $.

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

This note sharpens the second-order max-load bound for random linear hashing via a base optimization of the exponential potential, matching the independent case up to 1+o(1) in the next term.

read the letter

The main point is that this note improves the tail bound for the maximum load in binary linear hashing by optimizing the exponential potential from the Jaber et al. STOC 2025 paper. Under the condition that R times ell to the power 1-1/R is at least D ln ell, the probability that the max load hits R log n over log log n is at most order (log log n squared) over R squared times (log n) to the 2-2/R. This integrates to an expectation bound of one plus one plus o one times log log log n over log log n, all times the main log n over log log n term. So it gets the second-order term matching the fully independent case up to the 1+o(1) factor. The paper does a good job with the single prescribed bucket tail bound, which is sharp and shown tight by subspace construction. That part is self-contained and doesn't rely on the union bound over all buckets, which would lose the 2^ell factor. On the linear hashing side, the optimization seems to go through without degrading the exponent, thanks to the condition absorbing potential extra factors from the dependencies among loads. There is no sign of circular reasoning or parameter fitting here; it's a direct technical extension. A small concern is whether the condition restricts the range of R too much in practice, but for large ell it works fine. The stress test worry about additional multiplicative factors from the linear map is likely handled by that explicit condition, so the claimed precision on the second-order term should be okay. This is aimed at people doing fine-grained analysis of hashing schemes in theory. Readers who need precise asymptotics for max load will find it useful. It is worth sending to peer review as a concise note that sharpens an existing result without major new machinery.

Referee Report

2 major / 2 minor

Summary. The manuscript is a note refining the analysis of maximum load for binary linear hashing. Building on Jaber et al. (STOC 2025), it optimizes the exponential-potential method to derive a stronger tail bound: for R>1 with R ℓ^{1-1/R} ≥ D ln ℓ, Pr[M(S,h) ≥ R log n / log log n] ≤ O( (log log n)^2 / (R^2 (log n)^{2-2/R}) ). Integrating this yields E[M(S,h)] ≤ (1 + (1+o(1)) log log log n / log log n) * log n / log log n. It also gives a sharp tail bound Pr[Load_h(y) > 2^a - 2] ≤ γ^{-1} 2^{-a^2} for fixed y, shown tight by subspace construction.

Significance. If the optimization carries through without degrading the exponent, the result establishes that binary linear hashing matches fully independent hashing not only in the leading O(log n / log log n) term but also in the dominant second-order correction up to a 1+o(1) factor. This is a meaningful technical advance over the constant-factor bound in prior work. The self-contained single-bucket tail and its asymptotic tightness proof are additional strengths.

major comments (2)

[Proof of the improved tail bound] The derivation of the tail bound with denominator (log n)^{2-2/R} rests on carrying the base optimization of the exponential-potential function from Jaber et al. to the linear map setting. The manuscript must explicitly confirm that linear dependencies among the Load_h(y) values do not introduce multiplicative factors or weaken the exponent; the condition R ℓ^{1-1/R} ≥ D ln ℓ is introduced to absorb such errors, but the verification step is load-bearing for the claimed precision of the integrated second-order term.
[Integration step for the expectation] The integration of the tail bound to obtain the (1+o(1)) log log log n / log log n correction assumes the tail holds for all R satisfying the given condition and that the range of admissible R is sufficient to justify the o(1) factor. The manuscript should include an explicit calculation showing the range of R for which the condition holds and how it covers the regime needed for the second-order expectation bound.

minor comments (2)

The absolute constant D is left unspecified; providing an explicit numerical upper bound on D would allow direct verification of the condition for concrete parameters.
[Single-bucket tail bound] In the single-bucket tightness argument, the subspace construction is said to match the leading constant γ^{-1} asymptotically as a→∞; a brief indication of how the construction achieves this would strengthen the claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our note. We address the major comments point by point below, agreeing that additional explicit verification and calculation will improve clarity. These will be incorporated in the revision.

read point-by-point responses

Referee: [Proof of the improved tail bound] The derivation of the tail bound with denominator (log n)^{2-2/R} rests on carrying the base optimization of the exponential-potential function from Jaber et al. to the linear map setting. The manuscript must explicitly confirm that linear dependencies among the Load_h(y) values do not introduce multiplicative factors or weaken the exponent; the condition R ℓ^{1-1/R} ≥ D ln ℓ is introduced to absorb such errors, but the verification step is load-bearing for the claimed precision of the integrated second-order term.

Authors: We agree that an explicit confirmation strengthens the argument. The condition R ℓ^{1-1/R} ≥ D ln ℓ is introduced precisely to absorb any additional error terms or multiplicative factors arising from linear dependencies when adapting the exponential-potential method to the linear-map setting; these dependencies contribute only lower-order effects that are dominated by the given threshold without weakening the exponent 2-2/R. In the revised manuscript we will add a short dedicated paragraph in the proof that walks through the relevant steps of the potential-function analysis and verifies that no extra factors invalidate the claimed bound. revision: yes
Referee: [Integration step for the expectation] The integration of the tail bound to obtain the (1+o(1)) log log log n / log log n correction assumes the tail holds for all R satisfying the given condition and that the range of admissible R is sufficient to justify the o(1) factor. The manuscript should include an explicit calculation showing the range of R for which the condition holds and how it covers the regime needed for the second-order expectation bound.

Authors: We will include the requested explicit calculation in the integration section. For any R ≥ 1 + C (log log log n / log log n) with sufficiently large absolute constant C, the inequality R ℓ^{1-1/R} ≥ D ln ℓ holds for all sufficiently large ℓ, because 1-1/R ≈ (R-1) yields ℓ^{1-1/R} ≫ (ln ℓ)/R. This admissible range comfortably covers the values of R needed to integrate the tail and obtain the (1+o(1)) log log log n / log log n correction term. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation extends external prior method

full rationale

The paper performs a base optimization of the exponential-potential function introduced in the externally cited Jaber et al. (STOC 2025) work to obtain the improved tail bound with exponent 2-2/R, subject to the explicit condition R ℓ^{1-1/R} ≥ D ln ℓ. This step is a direct mathematical refinement rather than a self-definition or fitted-input renaming, and the resulting integrated expectation bound follows from standard tail integration without reducing to quantities defined in terms of themselves. The separate single-bucket tail bound is explicitly labeled as an independent self-contained argument with a subspace tightness construction, confirming the overall chain does not collapse to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on standard probabilistic method techniques and linear algebra over F_2. No new free parameters are introduced; the optimization is deterministic given the prior potential function.

axioms (1)

domain assumption The exponential-potential method from Jaber et al. (STOC 2025) applies to binary linear maps with the stated base optimization.
Invoked to derive the improved tail exponent.

pith-pipeline@v0.9.0 · 6048 in / 1356 out tokens · 34527 ms · 2026-05-19T23:47:58.962125+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.

We record a base optimization in their exponential-potential method showing that binary linear hashing nearly matches fully independent hashing also at the level of the second-order maximum-load scale.

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

12 extracted references · 12 canonical work pages

[1]

Is linear hashing good? InProceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 465–474, 1997

Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, and G´ abor Tardos. Is linear hashing good? InProceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 465–474, 1997

work page 1997
[2]

Linear hash functions.Journal of the ACM, 46(5):667–683, 1999

Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, and G´ abor Tardos. Linear hash functions.Journal of the ACM, 46(5):667–683, 1999

work page 1999
[3]

Kumar, and David Zuckerman

Michael Jaber, Vinayak M. Kumar, and David Zuckerman. Linear hashing is optimal. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 245–255,

work page
[4]

Also available as arXiv:2505.14061

work page arXiv
[5]

Balls into bins

Martin Raab and Angelika Steger. “Balls into bins”—A simple and tight analysis. InRandom- ization and Approximation Techniques in Computer Science, RANDOM 1998, Lecture Notes in Computer Science, vol. 1518, pages 159–170. Springer, 1998

work page 1998
[6]

Linear hashing withℓ ∞ guarantees and two-sided Kakeya bounds

Manik Dhar and Zeev Dvir. Linear hashing withℓ ∞ guarantees and two-sided Kakeya bounds. TheoretiCS, 3:Article 8, 2024. Preliminary version inProceedings of the 63rd IEEE Symposium on Foundations of Computer Science, pages 419–428, 2022

work page 2024
[7]

Gaston H. Gonnet. Expected length of the longest probe sequence in hash code searching. Journal of the ACM, 28(2):289–304, 1981

work page 1981
[8]

Stein’s method and the rank distribution of random matrices over finite fields.Annals of Probability, 43(3):1274–1314, 2015

Jason Fulman and Larry Goldstein. Stein’s method and the rank distribution of random matrices over finite fields.Annals of Probability, 43(3):1274–1314, 2015. 18 A Potential lemmas In this appendix we include self-contained proofs of the potential lemmas used in the main text. The first lemma packages the potential-evolution estimates of Jaber–Kumar–Zucke...

work page 2015
[9]

SinceZ≥2rs, we have F Z d ≤F 2rs d + 8 √ 3 d (Z−2rs)

Indeed, on the quadratic part its derivative is 96u, and the quadratic part ends atu= 1/ √ 48, where the derivative equals 8 √ 3. SinceZ≥2rs, we have F Z d ≤F 2rs d + 8 √ 3 d (Z−2rs). Taking expectations and usingE(Z−2rs)≤r 2s2, we get E F Z d ≤F 2rs s(2 +s) + 8 √ 3 s(2 +s) r2s2 =F 2r 2 +s + 8 √ 3r 2s 2 +s . We now show that the right-hand side is at most...

work page
[10]

Therefore, by linearity of expectation, Eh[Ta(h)] =|I a|n−a

Hence Pr h [h(ui1) =· · ·=h(u ia) =y] = 2 −ℓa =n −a. Therefore, by linearity of expectation, Eh[Ta(h)] =|I a|n−a. 23 Since|I a| ≤m a, we get Eh[Ta(h)]≤ m n a =λ a. Now supposeZ y ≥q. Then the setA={u i :h(u i) =y}has size at leastq. By Lemma 1,A contains at least M(q) := a−1Y j=0 (q+ 1−2 j) ordered linearly independenta-tuples. Thus Zy ≥q=⇒T a(h)≥M(q). By...

work page
[11]

Therefore Pr H [M(S, H)≥T]≤2p T

Hence Proposition 19 gives Pr [M(S, H)≥T|His surjective]≤p T . Therefore Pr H [M(S, H)≥T]≤2p T . Finally, the restriction ofHto the embedded copy ofF u 2 is a uniformly random linear map Fu 2 →F ℓ 2, and the loads are computed only using points ofS. Thus the same estimate holds for a uniformly random linear maph:F u 2 →F ℓ

work page
[12]

The previous theorem can be written in terms of the fully independent large-load scalet

Absorbing the factor 2 into the constant proves the theorem. The previous theorem can be written in terms of the fully independent large-load scalet. Corollary 21(Comparison with the fully independent scale).Letn= 2 ℓ, letS⊆F u 2 have sizem, and letλ:=m/n. Lett=t(m, n)be defined by tln t eλ = lnn. Then, for everyR >1satisfying R t λ 1−1/R ≥D, one has Pr h...

work page

[1] [1]

Is linear hashing good? InProceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 465–474, 1997

Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, and G´ abor Tardos. Is linear hashing good? InProceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 465–474, 1997

work page 1997

[2] [2]

Linear hash functions.Journal of the ACM, 46(5):667–683, 1999

Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, and G´ abor Tardos. Linear hash functions.Journal of the ACM, 46(5):667–683, 1999

work page 1999

[3] [3]

Kumar, and David Zuckerman

Michael Jaber, Vinayak M. Kumar, and David Zuckerman. Linear hashing is optimal. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 245–255,

work page

[4] [4]

Also available as arXiv:2505.14061

work page arXiv

[5] [5]

Balls into bins

Martin Raab and Angelika Steger. “Balls into bins”—A simple and tight analysis. InRandom- ization and Approximation Techniques in Computer Science, RANDOM 1998, Lecture Notes in Computer Science, vol. 1518, pages 159–170. Springer, 1998

work page 1998

[6] [6]

Linear hashing withℓ ∞ guarantees and two-sided Kakeya bounds

Manik Dhar and Zeev Dvir. Linear hashing withℓ ∞ guarantees and two-sided Kakeya bounds. TheoretiCS, 3:Article 8, 2024. Preliminary version inProceedings of the 63rd IEEE Symposium on Foundations of Computer Science, pages 419–428, 2022

work page 2024

[7] [7]

Gaston H. Gonnet. Expected length of the longest probe sequence in hash code searching. Journal of the ACM, 28(2):289–304, 1981

work page 1981

[8] [8]

Stein’s method and the rank distribution of random matrices over finite fields.Annals of Probability, 43(3):1274–1314, 2015

Jason Fulman and Larry Goldstein. Stein’s method and the rank distribution of random matrices over finite fields.Annals of Probability, 43(3):1274–1314, 2015. 18 A Potential lemmas In this appendix we include self-contained proofs of the potential lemmas used in the main text. The first lemma packages the potential-evolution estimates of Jaber–Kumar–Zucke...

work page 2015

[9] [9]

SinceZ≥2rs, we have F Z d ≤F 2rs d + 8 √ 3 d (Z−2rs)

Indeed, on the quadratic part its derivative is 96u, and the quadratic part ends atu= 1/ √ 48, where the derivative equals 8 √ 3. SinceZ≥2rs, we have F Z d ≤F 2rs d + 8 √ 3 d (Z−2rs). Taking expectations and usingE(Z−2rs)≤r 2s2, we get E F Z d ≤F 2rs s(2 +s) + 8 √ 3 s(2 +s) r2s2 =F 2r 2 +s + 8 √ 3r 2s 2 +s . We now show that the right-hand side is at most...

work page

[10] [10]

Therefore, by linearity of expectation, Eh[Ta(h)] =|I a|n−a

Hence Pr h [h(ui1) =· · ·=h(u ia) =y] = 2 −ℓa =n −a. Therefore, by linearity of expectation, Eh[Ta(h)] =|I a|n−a. 23 Since|I a| ≤m a, we get Eh[Ta(h)]≤ m n a =λ a. Now supposeZ y ≥q. Then the setA={u i :h(u i) =y}has size at leastq. By Lemma 1,A contains at least M(q) := a−1Y j=0 (q+ 1−2 j) ordered linearly independenta-tuples. Thus Zy ≥q=⇒T a(h)≥M(q). By...

work page

[11] [11]

Therefore Pr H [M(S, H)≥T]≤2p T

Hence Proposition 19 gives Pr [M(S, H)≥T|His surjective]≤p T . Therefore Pr H [M(S, H)≥T]≤2p T . Finally, the restriction ofHto the embedded copy ofF u 2 is a uniformly random linear map Fu 2 →F ℓ 2, and the loads are computed only using points ofS. Thus the same estimate holds for a uniformly random linear maph:F u 2 →F ℓ

work page

[12] [12]

The previous theorem can be written in terms of the fully independent large-load scalet

Absorbing the factor 2 into the constant proves the theorem. The previous theorem can be written in terms of the fully independent large-load scalet. Corollary 21(Comparison with the fully independent scale).Letn= 2 ℓ, letS⊆F u 2 have sizem, and letλ:=m/n. Lett=t(m, n)be defined by tln t eλ = lnn. Then, for everyR >1satisfying R t λ 1−1/R ≥D, one has Pr h...

work page