Pith. sign in

REVIEW 3 major objections 6 minor 31 references

Orthogonality Defects of HKZ-Reduced Bases

T0 review · 3 major / 6 minor · reviewed 2026-08-28 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The supremum of orthogonality defects of HKZ-reduced bases satisfies log D_n / (n log n) -> 2 as n -> infinity, and D_4 = 4375/1024.

desk verdict Novel asymptotic result with a serious internal inconsistency in the key lemma; likely true but needs a corrected proof. read the letter →

arxiv 2608.22943 v1 pith:SXWCGIWV submitted 2026-08-24 math.NT

Zhixing Li This is my paper · ORCID
classification math.NT
keywords basesdefectsorthogonalitydenotedeterminedimensionalexacthermite--korkine--zolotarev
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Lattices are regular arrays of points, and a basis is a set of vectors that generates the array. When the basis vectors are close to perpendicular, they are useful in cryptography and in the geometry of numbers. The orthogonality defect measures how far a basis is from being perfectly perpendicular: a defect of 1 means the basis is orthogonal, and larger numbers mean more skew. HKZ reduction is a standard procedure that tries to make every basis vector as short as possible, and this paper studies the worst possible defect after such reduction.

The first result is an asymptotic formula. It shows that the logarithm of the worst defect, divided by n log n, tends to 2 as the dimension n grows. The proof builds a family of HKZ-reduced bases by gluing together two different blocks: one is a nearly triangular block with half-integer coefficients, the other is a basis supplied by a known construction of Hanrot and Stehle. The combined basis has a defect large enough to match the known upper bound up to lower-order terms.

The second result is exact and computer-assisted. In four dimensions, the paper constructs an explicit HKZ-reduced basis with defect 4375/1024, which is about 4.27, and then proves no four-dimensional HKZ-reduced basis can do better. The proof splits the space of parameters into boxes, discards boxes using exact rational interval arithmetic, and analyzes the remaining small neighborhoods with Taylor estimates. The code for the interval computation is included in the appendix.

Extended reading notes

Core claim

Theorem 1.1: lim_{n→∞} log D_n/(n log n) = 2, where D_n is the supremum of the orthogonality defect over n-dimensional HKZ-reduced bases. If the paper is correct, the worst HKZ-reduced basis has defect growing like exp(2 n log n + o(n log n)), and previous upper bounds of order exp(2 n log n) are asymptotically tight.

Load-bearing premise

The lower-bound construction for Theorem 1.1 relies on Lemma 3.2, which cites Hanrot and Stehle [8] for the existence of an HKZ-reduced basis C_s with first minimum 1 and product of squared Gram-Schmidt lengths e^{6(s-1)} s^{-s}. The paper does not reproduce the proof; if that external construction were false or misstated, the lower bound log D_n ≥ 2 n log n - n log log n - O(n) would not follow. Location: Section 3, Lemma 3.2, proof line 'See Hanrot and Stehle [8, Theorems 1-2 and Corollary 1]'.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper studies the orthogonality defect of Hermite–Korkine–Zolotarev (HKZ)-reduced bases. Its central result is Theorem 1.1, which claims lim_{n→∞} log D_n/(n log n) = 2, where D_n is the supremum of the defect over all n-dimensional HKZ-reduced bases. The lower bound is obtained by constructing a family of HKZ-reduced bases formed by orthogonally gluing an r-dimensional all-half block A_r with an s-dimensional block C_s taken from Hanrot and Stehlé; the upper bound is inherited from Lagarias–Lenstra–Schnorr. The paper also determines the exact value D_4 = 4375/1024, disproving a conjecture of Porter, Dable-Heath, and Ling, and claims that the extremal four-dimensional basis is unique up to similarity. The four-dimensional proof combines a finite characterization of HKZ-reduced forms, sign-normalization into eight boxes, a computer-assisted exact rational covering, and a local analytic inequality.

Significance. If the asymptotic result is correct, it closes the exponential gap between the known upper bound log D_n ≤ 2 n log n + O(n) and the previous lower bound log D_n ≥ n log n − O(n), identifying the precise growth rate exp(2 n log n + o(n log n)). The four-dimensional computation is a valuable, independently checkable contribution: the machine-assisted part uses exact rational interval arithmetic, the full code is included in Appendix A, and the local inequality in Lemma 4.4 is proved analytically. The paper also gives a concrete counterexample to a published conjecture, which is a useful data point for the behavior of HKZ reduction in low dimensions. These strengths are substantial even though the asymptotic proof contains, as detailed below, two points that need to be repaired.

major comments (3)
  1. [Section 3, Lemma 3.2] The displayed formula for the squared Gram–Schmidt lengths d_j is internally inconsistent. For s=2 the formula gives d_1=1 and d_2=e^{12}/2, so the product d_1 d_2 equals e^{12}/2, whereas the asserted identity (3.4) gives e^6/4. If the product in the formula is instead read as running to t=s, then d_1=e^{6(s+1)/s}≠1, contradicting the requirement ∥c_1∥=1. Thus Lemma 3.2 as printed cannot be true. The proof of Proposition 3.3 uses only the product formula (3.4) and the minimum condition (3.3), so the lower bound of Theorem 1.1 depends directly on a statement that is currently both unproved in the manuscript and, as written, false. The author should correct the formula or, preferably, quote precisely the Hanrot–Stehlé theorem that yields (3.4), and show that the cited result indeed gives the stated product with the stated minimum.
  2. [Section 3, proof of Theorem 1.1, Eq. (3.7)] The step from the crossing equation to the claimed location of ρ_n is mathematically incorrect. The equation (n−ρ_n)/(ρ_n+4) = log(n−ρ_n) − 5 + o(1) does not imply ρ_n = n/log n − 4 + o(1). Solving the equation asymptotically gives ρ_n = n/log n + 5n/(log n)^2 + O(n/(log n)^3), not the displayed expression. The leading term n/log n is sufficient for the final limit, and the later expansion of log F_n(ρ_n) would still yield the same leading terms, but the proof as written contains a false assertion at a load-bearing point. The argument can be repaired, for instance by choosing r_n = ⌊n/log n⌋ and directly deriving log F_n(r_n) = 2 n log n − n log log n + O(n), or by giving a correct asymptotic solution of the crossing equation. The manuscript should be revised to remove the false statement.
  3. [Section 4, proof of Theorem 1.2, uniqueness claim] The final paragraph of the proof states that the four equality cases identified by Lemmas 4.2–4.4 are related by unimodular changes of basis and all correspond, up to similarity, to the lattice of Lemma 4.1, but no explicit transformations or argument are provided. Since the uniqueness assertion is part of the stated theorem, the author should supply the concrete unimodular matrices that connect the four candidate centers p_{\eta,\theta}, or otherwise give a short proof that all four cases represent the same lattice up to similarity.
minor comments (6)
  1. [Section 3, Eq. (3.7)] The notation Φ_n(r) is introduced as log R_n(r), but two lines later it is treated as a function of s=n−r. Please state the variable change explicitly to avoid confusion.
  2. [Section 3, Eq. (3.7)] The expansion Φ_n(r) = 5 − log(n−r) + (n−r)/(r+4) + o(1) is used for r in an interval of width Θ(n/log n). Please specify that the o(1) is uniform over the range considered, since the subsequent O((log n)^2/n) bound for the discrete derivative relies on that uniformity.
  3. [Section 4, Lemma 4.2] In the last estimate of the proof, the sentence 'The last estimate also uses D_3 = 25/12' is cryptic; the derivation of the upper bound 325/96 should be expanded so the reader can verify how the known three-dimensional value enters.
  4. [Appendix A] The constant SCALES in the code is used for relative-width splitting but is not explained in the surrounding text; a brief comment in the proof of Lemma 4.3 would make the code easier to audit.
  5. [Throughout] The typesetting of the product in Lemma 3.2 is hard to read; the expression 's−1Y' should be replaced by a standard product sign, and the exponent −1/t should be set on the factor e^{−6(t+1)} rather than on the whole product.
  6. [References] Reference [8] is cited as an INRIA technical report; if a published version of Hanrot–Stehlé exists, the author should cite both the report and the published version.
Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The ledger is clean: no fitted physical constants and no invented entities. The main extraneous inputs are two external theorems: the Hanrot-Stehle construction for the asymptotic lower bound and Novikova's finite reduction characterization for D4. The block size r and the radius epsilon_0 are proof parameters, not data-derived constants.

free parameters (2)
  • block size r = r ≈ n/log n, more precisely r ≈ n/(log n - 4)
    The lower bound is optimized over r, the dimension of the all-half block in B_{r,s}. This is a proof parameter, not a data fit, but the final asymptotic statement depends on choosing r in this range.
  • local box radius epsilon_0 = 1/1024
    In the D4 proof, the radius of the neighborhoods N_{eta,theta} is chosen by hand; the computer search and Lemma 4.4 are tailored to this value.
assumptions (4)
  • domain assumption Hanrot-Stehle construction of HKZ-reduced basis C_s with d_j as in Lemma 3.2 (cited [8])
    Used to build the second block in B_{r,s}; the proof is not included in this paper.
  • domain assumption Novikova's finite characterization of 4-dimensional HKZ-reduced forms by 21 inequalities (cited [21], restated in [22])
    The D4 upper-bound search treats these finite constraints as necessary and sufficient for HKZ reduction in dimension 4.
  • standard math Korkine-Zolotarev inequalities (4.1) for HKZ-reduced forms
    Classical inequalities used to restrict d2, d3, d4 in Lemma 4.2.
  • standard math Upper bound D_n ≤ gamma_n^n (n+3)!/(6·4^n) of Lagarias, Lenstra, and Schnorr
    Used for the limsup side of Theorem 1.1, together with the classical estimate gamma_n ≤ n.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Orthogonality Defects of HKZ-Reduced Bases." pith.science (2026). https://pith.science/paper/SXWCGIWV

@misc{pith2026260822943,
  author       = {Pith},
  title        = {Pith review of: Orthogonality Defects of HKZ-Reduced Bases},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SXWCGIWV}},
  note         = {Machine review of arXiv:2608.22943}
}
abstract

Let $D_n$ denote the supremum of the orthogonality defects over all $n$-dimensional Hermite--Korkine--Zolotarev (HKZ)-reduced bases. This paper shows that $\lim_{n\to\infty} \log D_n/(n\log n)=2$. We also determine the exact value $D_4=4375/1024$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [8]

    Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases

    G. Hanrot and D. Stehlé,Worst-case Hermite–Korkine–Zolotarev reduced lattice bases, Technical Report RR-6422, INRIA, 2008; arXiv:0801.3331v2

    work page Pith review arXiv 2008

  2. [1]

    Ajtai and C

    M. Ajtai and C. Dwork,A public-key cryptosystem with worst-case/average-case equivalence, in: Proc. 29th Annu. ACM Sympos. Theory Comput., ACM, 1997, 284–293. doi:10.1145/258533.258604

    work page arXiv 1997

  3. [2]

    Bennett,A block enumeration technique for lattice basis reduction, manuscript, 2018

    H. Bennett,A block enumeration technique for lattice basis reduction, manuscript, 2018. Available athttps://home.cs.colorado.edu/~hbennett/publications/bases.pdf

    work page 2018

  4. [3]

    Bieberbach and I

    L. Bieberbach and I. Schur,Über die Minkowskische Reduktionstheorie der positiven quadratischen Formen, Sitzungsber. Preuss. Akad. Wiss. Phys.-Math. Kl. (1928), 510–535; correction, 1929, p. 508

    work page 1928

  5. [4]

    H. F. Blichfeldt,A new principle in the geometry of numbers, with some applications, Trans. Amer. Math. Soc. 15 (1914), 227–235. doi:10.1090/S0002-9947-1914-1500976-6

    work page doi:10.1090/s0002-9947-1914-1500976-6 1914

  6. [5]

    J. H. Conway and N. J. A. Sloane,Sphere Packings, Lattices and Groups, 2nd ed., Springer-Verlag, New York, 1993. doi:10.1007/978-1-4757-2249-9

    work page doi:10.1007/978-1-4757-2249-9 1993

  7. [6]

    Goldreich, S

    O. Goldreich, S. Goldwasser, and S. Halevi,Public-key cryptosystems from lattice reduction problems, in: Advances in Cryptology—CRYPTO ’97, Lecture Notes in Comput. Sci. 1294, Springer, 1997, 112–131. doi:10.1007/BFb0052231

    work page doi:10.1007/bfb0052231 1997

  8. [7]

    P. M. Gruber and C. G. Lekkerkerker,Geometry of Numbers, North-Holland Math. Library 37, 2nd ed., North-Holland, Amsterdam, 1987

    work page 1987

Show all 31 references
  1. [9]

    Hermite,Extraits de lettres de M

    C. Hermite,Extraits de lettres de M. Ch. Hermite à M. Jacobi sur différents objets de la théorie des nombres, J. Reine Angew. Math. 40 (1850), 261–315. doi:10.1515/crll.1850.40.261; doi:10.1515/crll.1850.40.279. ORTHOGONALITY DEFECTS OF HKZ-REDUCED BASES 17

    doi

  2. [10]

    Hoffstein, J

    J. Hoffstein, J. Pipher, and J. H. Silverman,NTRU: A ring-based public key cryptosystem, in: Algorithmic Number Theory—ANTS-III, Lecture Notes in Comput. Sci. 1423, Springer, 1998, 267–288. doi:10.1007/BFb0054868

    1998 doi

  3. [11]

    Korkine and G

    A. Korkine and G. Zolotareff,Sur les formes quadratiques, Math. Ann. 6 (1873), 366–389. doi:10.1007/BF01442795

    doi

  4. [12]

    J. C. Lagarias, H. W. Lenstra, Jr., and C. P. Schnorr,Korkin–Zolotarev bases and successive minima of a lattice and its reciprocal lattice, Combinatorica 10 (1990), 333–348. doi:10.1007/BF02128669

    1990 doi

  5. [13]

    A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász,Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515–534. doi:10.1007/BF01457454

    1982 doi

  6. [14]

    Mahler,On Minkowski’s theory of reduction of positive definite quadratic forms, Quart

    K. Mahler,On Minkowski’s theory of reduction of positive definite quadratic forms, Quart. J. Math. Oxford Ser. 9 (1938), 259–262. doi:10.1093/qmath/os-9.1.259

    1938 doi

  7. [15]

    Mahler,On reduced positive definite quaternary quadratic forms, Nieuw Arch

    K. Mahler,On reduced positive definite quaternary quadratic forms, Nieuw Arch. Wiskunde (2) 22 (1946), 207–212

    1946

  8. [16]

    Martinet,Perfect Lattices in Euclidean Spaces, Grundlehren Math

    J. Martinet,Perfect Lattices in Euclidean Spaces, Grundlehren Math. Wiss. 327, Springer, Berlin, 2003. doi:10.1007/978-3-662-05167-2

    2003 doi

  9. [17]

    Martinet,Hermite versus Minkowski, arXiv:1403.1457v1 (2014)

    J. Martinet,Hermite versus Minkowski, arXiv:1403.1457v1 (2014)

    2014 arXiv

  10. [18]

    Minkowski,Über Geometrie der Zahlen, Jahresber

    H. Minkowski,Über Geometrie der Zahlen, Jahresber. Dtsch. Math.-Ver. 1 (1892), 64–65

  11. [19]

    Minkowski,Diskontinuitätsbereich für arithmetische äquivalenz, J

    H. Minkowski,Diskontinuitätsbereich für arithmetische äquivalenz, J. Reine Angew. Math. 129 (1905), 220–274. doi:10.1515/crll.1905.129.220

    1905 doi

  12. [20]

    L. J. Mordell,Observation on the minimum of a positive quadratic form in eight variables, J. London Math. Soc. 19 (1944), 3–6. doi:10.1112/jlms/19.73_Part_1.3

    1944 doi

  13. [21]

    N. V. Novikova,Domains of Korkin–Zolotarev reduction of positive quadratic forms inn≤ 8variables and reduction algorithms for these domains, Soviet Math. Dokl. 27 (1983), 557–560; translated from Dokl. Akad. Nauk SSSR 270 (1983), 48–51

    1983

  14. [22]

    R. A. Pendavingh and S. H. M. van Zwam,New Korkin–Zolotarev inequalities, SIAM J. Optim. 18 (2007), 364–378. doi:10.1137/060658795

    2007 doi

  15. [23]

    Porter, E

    C. Porter, E. Dable-Heath, and C. Ling,A new bound for the orthogonality defect of HKZ reduced lattices, Res. Number Theory 10 (2024), art. 65. doi:10.1007/s40993-024-00554-1

    2024 doi

  16. [24]

    Remak,Über die Minkowskische Reduktion der definiten quadratischen Formen, Compos

    R. Remak,Über die Minkowskische Reduktion der definiten quadratischen Formen, Compos. Math. 5 (1938), 368–391

    1938

  17. [25]

    B. L. van der Waerden,Die Reduktionstheorie der positiven quadratischen Formen, Acta Math. 96 (1956), 265–309. doi:10.1007/BF02392364

    1956 doi

  18. [26]

    B. L. van der Waerden,Das Minimum vonD/(f11f22 · · ·f 55)für reduzierte positive quinäre quadratische Formen, Aequationes Math. 2 (1969), 233–247

    1969

  19. [27]

    S. H. M. van Zwam,New Korkin–Zolotarev inequalities: Implementation and numerical data, SPOR Report 2006-05, Eindhoven University of Technology, 2006

    2006

  20. [28]

    Wen and X.-W

    J. Wen and X.-W. Chang,On the KZ reduction, IEEE Trans. Inform. Theory 65 (2019), 1921–1935. doi:10.1109/TIT.2018.2868945

    2019

  21. [29]

    Zong,Sphere Packings, Springer-Verlag, New York, 1999

    C. Zong,Sphere Packings, Springer-Verlag, New York, 1999. doi:10.1007/b98975

    1999 doi

  22. [30]

    Zong,The mathematical foundation of post-quantum cryptography, Research 8 (2025), art

    C. Zong,The mathematical foundation of post-quantum cryptography, Research 8 (2025), art. 0801. doi:10.34133/research.0801

    2025 doi

  23. [31]

    Zong,Some mathematical problems behind lattice-based cryptography, Cryptography 10 (2026), no

    C. Zong,Some mathematical problems behind lattice-based cryptography, Cryptography 10 (2026), no. 1, art. 10. doi:10.3390/cryptography10010010. School of Mathematics, Nanjing University, Nanjing 210093, P. R. China Email address:zhixing.li.math@gmail.com

    2026 doi

Pith tools

Reviewed August 28, 2026 · model on record in the stance chip above.