An improved constant in Banaszczyk's transference theorem

Divesh Aggarwal; Noah Stephens-Davidowitz

arxiv: 1907.09020 · v1 · pith:NZPJY7QRnew · submitted 2019-07-21 · 🧮 math.MG · math.NT

An improved constant in Banaszczyk's transference theorem

Divesh Aggarwal , Noah Stephens-Davidowitz This is my paper

Pith reviewed 2026-05-24 18:11 UTC · model grok-4.3

classification 🧮 math.MG math.NT

keywords transference theoremcovering radiusdual latticediscrete Gaussianlattice geometrypacking bound

0 comments

The pith

The product of a lattice covering radius and dual shortest vector is bounded above by 0.1275n plus lower-order terms.

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

The paper establishes a stricter upper bound relating the covering radius of any n-dimensional lattice to the shortest nonzero vector length in its dual lattice. It achieves the bound by following the steps of an earlier proof but replacing one inequality with a stronger estimate on the mass of a discrete Gaussian that comes from a packing argument. This substitution improves the leading constant by roughly one-fifth. A reader would care because such transference relations connect fundamental geometric quantities of lattices and appear in proofs throughout the geometry of numbers.

Core claim

The paper proves that for every n-dimensional lattice L the inequality mu(L) lambda_1(L*) is strictly less than (0.1275 + o(1)) times n holds, obtained by inserting a packing-derived upper bound on discrete Gaussian mass into the corresponding place in the original proof of the transference theorem.

What carries the argument

The packing-based upper bound on the mass of the discrete Gaussian distribution, inserted in place of the Fourier-analytic estimate used in the original proof.

Load-bearing premise

The packing bound on discrete Gaussian mass applies directly in the relevant step of the original proof without any further adjustments or loss of the stated constant.

What would settle it

An explicit family of lattices in growing dimension n for which the product mu(L) lambda_1(L*) is at least 0.1275 n plus a term that does not tend to zero would falsify the claimed bound.

read the original abstract

$ \newcommand{\R}{\ensuremath{\mathbb{R}}} \newcommand{\lat}{\mathcal{L}} \newcommand{\ensuremath}[1]{#1} $We show that \[ \mu(\lat) \lambda_1(\lat^*) < \big( 0.1275 + o(1) \big) \cdot n \; , \] where $\mu(\lat)$ is the covering radius of an $n$-dimensional lattice $\lat \subset \R^n$ and $\lambda_1(\lat^*)$ is the length of the shortest non-zero vector in the dual lattice $\lat^*$. This improves on Banaszczyk's celebrated transference theorem (Math. Annal., 1993) by about 20%. Our proof follows Banaszczyk exactly, except in one step, where we replace a Fourier-analytic bound on the discrete Gaussian mass with a slightly stronger bound based on packing. The packing-based bound that we use was already proven by Aggarwal, Dadush, Regev, and Stephens-Davidowitz (STOC, 2015) in a very different context. Our contribution is therefore simply the observation that this implies a better transference theorem.

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 is a short note that improves the constant in Banaszczyk's transference theorem from roughly 0.5 to 0.1275 by direct substitution of a 2015 packing bound.

read the letter

The paper's main point is that Banaszczyk's 1993 proof goes through unchanged if you swap the Fourier-analytic step for the packing-based bound on discrete Gaussian mass from Aggarwal et al. STOC 2015. That swap produces the new constant 0.1275 + o(1) instead of the older one. The contribution is exactly that observation and the arithmetic that follows from it; nothing else in the argument is altered. The 2015 bound was already proved for algorithmic reasons, so the application here is a clean reuse rather than new machinery. The result is therefore new in the specific constant it delivers, and the improvement is real if the substitution carries no hidden loss factors. The manuscript is short and the logic is linear, which makes the claim easy to check once the 2015 bound is in hand. The only soft spot is that the improvement remains modest in absolute terms and rests entirely on one prior result; readers already familiar with the 2015 paper will see the gain immediately, while others will need to verify that the packing bound slots in without adjustment. No circularity appears because the 2015 proof was independent. This note is useful for anyone who cites or applies transference bounds in lattice geometry or cryptography. It is not a deep reworking of the subject, but the constant is better and the argument is transparent, so it deserves referee time rather than a desk rejection.

Referee Report

0 major / 1 minor

Summary. The paper claims an improved transference bound μ(ℒ) λ₁(ℒ*) < (0.1275 + o(1)) n for n-dimensional lattices, improving Banaszczyk's 1993 constant by roughly 20%. The argument follows Banaszczyk's proof exactly except at one step, where the Fourier-analytic estimate on discrete Gaussian mass is replaced by the packing-based bound already established in Aggarwal–Dadush–Regev–Stephens-Davidowitz (STOC 2015). The contribution is presented as the observation that this substitution yields the stated numerical improvement.

Significance. If the direct substitution is valid, the note supplies a modest quantitative sharpening of a classical result in the geometry of numbers. The improvement is parameter-free and rests on an independently proved bound, which is a strength. The result may be of interest to researchers working on lattice algorithms or transference theorems, though the absolute gain (from Banaszczyk's original constant to 0.1275) remains incremental.

minor comments (1)

[Abstract] The abstract and introduction could briefly recall the numerical value of Banaszczyk's original constant (or the precise ratio of improvement) to make the 20% claim immediately verifiable without external lookup.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation to accept the manuscript. No major comments were raised.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's derivation follows Banaszczyk (1993) exactly except for substituting a discrete Gaussian mass bound proven independently in the 2015 STOC paper by Aggarwal et al. (with author overlap). This prior result was established for algorithmic purposes in a separate publication and is externally verifiable; the current contribution is merely the observation that the substitution yields the improved constant. No step reduces by construction to the paper's own inputs, fitted parameters, or unverified self-citation chains. The cited bound is load-bearing but constitutes real external evidence under the evaluation rules.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard Euclidean lattice theory and re-uses a bound already proved elsewhere; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)

standard math Standard properties of Euclidean lattices, dual lattices, covering radius, and shortest vectors
Invoked implicitly throughout any transference theorem; the abstract assumes these definitions and basic facts.

pith-pipeline@v0.9.0 · 5739 in / 1242 out tokens · 25989 ms · 2026-05-24T18:11:58.328133+00:00 · methodology

An improved constant in Banaszczyk's transference theorem

Core claim

What carries the argument

Load-bearing premise

What would settle it

discussion (0)