Polynomial-shape dependence in small-root algorithms

Definitions and mathematical statement

For an integer polynomial in $m$ variables write \[ f(x_1,\ldots,x_m)=\sum_{\alpha\in S}c_\alpha x^\alpha, \qquad c_\alpha\ne0, \] where $S\subset{\mathbb{N}}_0^m$ is its support. Its Newton polytope is the convex hull of $S$. These are natural descriptions of polynomial shape, but the source does not define whether shape also includes coefficients, degree patterns, variable changes, or other data.

A common modular small-root task uses a modulus $N>1$ and bounds $X_1,\ldots,X_m>0$ and seeks integer tuples satisfying \[ f(x_1,\ldots,x_m)\equiv0\pmod N, \qquad |x_i|\le X_i. \] Coppersmith-type methods use polynomial/lattice constructions to recover such roots in suitable size ranges. The source does not restrict the question to this exact modular task; integer-equation roots, univariate versus multivariate cases, and variant modulus assumptions require specification.

The problem is to understand and control how polynomial shape affects these methods, for example the provable recoverable root region, complexity, or success of the chosen lattice construction. It gives no exact shape invariant, algorithm family, optimality criterion, coefficient-height assumptions, or guarantee to be proved. In multivariate formulations, hypotheses ensuring that produced relations determine the desired roots also need stating. The support and Newton-polytope definitions identify possible input data; they do not assert a new support-based bound.

Short English statement

Determine which features of a polynomial govern Coppersmith-type root-size bounds and algorithm behavior, and how to exploit or control them. The original request is a research program rather than a fixed quantitative conjecture.

The supplied summary names support-aware work of Howgrave-Graham, Jochemsz--May, Blömer--May, and Coron, but gives no exact theorem resolving the general shape-dependence request. It reports partial bounds while retaining OPEN-TRIAGE. The 2006 source's current status needs a primary-literature audit.

Sources

• Local UnsolvedMath registry, permanent ID 8800025, source code catalogue entry, "Polynomial-shape dependence in small-root algorithms," proposed by Alexander May. Dataset curation and metadata: Ulam AI and UnsolvedMath Contributors, CC BY 4.0.
• IPAM, Workshop on Number Theory and Cryptography --- Open Problems (2006), Attachment 6222, PDF page 18, printed slide 13, schedule locator https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule; pdf-and-legacy-ppt visual-audit extraction, accessed 2026-07-29.
• Howgrave-Graham, Jochemsz--May, Blömer--May, and Coron are named in the supplied summary without complete primary citations or exact support-dependent bounds.
• Source provenance reports inspection of 17 PDFs and two legacy PPT decks among 19 surviving attachments, excluding repetitions and solved definitions; this is supplied provenance, not a new inspection claimed here.
• Current primary-literature status audit and redistribution terms NEEDS_REVIEW for the publicly accessible author/publisher copy, separately from the dataset licence.