Dimension reduction in small-root lattices

Definitions and mathematical statement

An integer lattice has dimension equal to its rank: if $L=B{\mathbb{Z}}^d\subset{\mathbb{R}}^D$ and $B$ has linearly independent columns, then $\operatorname{rank}L=d$. In small-root methods, coefficient vectors of suitable auxiliary polynomials, after scaling variables by proposed root bounds, form a lattice used for short-vector extraction and root recovery.

May asks whether the lattice dimension in the stated small-root constructions can be reduced. The constructions themselves are absent from this excerpt. The supplied summary indicates that the intended comparison preserves the achievable root bound; deleting basis vectors or monomials without retaining the root-recovery guarantee would not answer that version of the question.

For context, a common modular small-root task is to find integers $x_1,\ldots,x_s$ with $|x_i|<X_i$ satisfying $f(x_1,\ldots,x_s)\equiv0\pmod N$. This is only an illustration: the source does not specify whether its constructions are univariate or multivariate, modular or over the integers, or what polynomial degree, modulus assumptions, and root bounds they use. It also does not give the baseline dimension or a requested reduction factor. A precise comparison must fix the construction, parameter regime, guaranteed root range, and whether success is rigorous or heuristic. Rank and the ambient coefficient-vector length must likewise be distinguished if the baseline lattices are not full rank.

Short English statement

Can the lattices in the specified small-root methods be made smaller while retaining their achievable root bounds? The original constructions, dimensions, and recovery guarantees are missing from the extract.

Sources

• Local UnsolvedMath registry, permanent ID 8800028, source code catalogue entry; attributed to Alexander May; no proposal year supplied; update 2026-08-06.
• IPAM, Workshop on Number Theory and Cryptography --- Open Problems (2006), attachment 6222, PDF page 24, printed slide 18: https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Registry access date 2026-07-29; PDF and legacy-PPT visual audit. Provenance reports 19 surviving attachments, 17 PDFs and two legacy PPT decks, with repetitions and solved definitions excluded. Present status and redistribution terms require review.
• The supplied summary refers to dimension-reduced Coppersmith variants and mentions Howgrave--Graham, Coron, and Blömer--May, but gives no exact papers, baseline construction, or bound-preserving comparison theorem. It reports partial progress while retaining the general question as open.