Algebraic independence in multivariate elimination

Definitions and mathematical statement

For polynomials $g_1,\ldots,g_s\in{\mathbb{Q}}[x_1,\ldots,x_r]$, algebraic independence over ${\mathbb{Q}}$ means \[ P(g_1,\ldots,g_s)\ne0\qquad\text{for every nonzero }P\in{\mathbb{Q}}[Y_1,\ldots,Y_s]. \] Equivalently the substitution homomorphism from ${\mathbb{Q}}[Y_1,\ldots,Y_s]$ is injective; necessarily $s\leq r$. This is stronger than linear independence of coefficient vectors or distinct leading monomials.

In a usual small-root setting one has polynomial congruences modulo an integer $N$ and an unknown integer vector $\alpha$ with prescribed coordinate bounds. Lattice constructions seek auxiliary polynomials $g_i$ that vanish at $\alpha$ over the integers, so elimination can recover the small root. The source asks for conditions or constructions ensuring the required algebraic independence among the auxiliary polynomials.

The conditions must concern the actual small-root construction, not just an unrelated algebraically independent polynomial list: the common vanishing and smallness/height bounds must be retained. The record does not give the input congruences, variable count, root bounds, polynomial-shift family, lattice reduction procedure, number of auxiliaries, or efficiency/rigor target.

Algebraic independence alone also does not guarantee that the common zero set is zero dimensional or that the desired root is isolated; those are separate elimination hypotheses. The supplied summary's leading-monomial language must therefore not be read as a complete criterion for successful root extraction. The task is to make the stated independence step rigorous in specified multivariate families, not a blanket proof that every multivariate small-root attack succeeds.

Short English statement

Give verifiable conditions or constructions making the auxiliary polynomials in multivariate small-root methods algebraically independent, while preserving their common small root and size bounds. Distinguish this from linear independence and from isolated-root elimination.

Sources

• Local UnsolvedMath registry, permanent ID 8800026, exact source code catalogue entry, "Algebraic independence in multivariate elimination"; attributed to Alexander May, no proposed year supplied. Registry status open, classification OPEN-TRIAGE.
• IPAM Workshop on Number Theory and Cryptography---Open Problems (2006), attachment 6222, PDF page 20, printed slide 15, https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Supplied pdf-and-legacy-ppt visual audit accessed July 29, 2026. Provenance records 17 PDFs and two legacy PPT decks inspected with repeated builds/solved definitions excluded; no PDF/PPT was accessed here.
• The supplied summary describes heuristic independence assumptions in multivariate Coppersmith-style methods, special-case rigorous results, and no verified general guarantee. It supplies no precise special-case references or definition of independent leading monomials; these remarks are not treated as a general elimination theorem.
• Provenance flags current primary-literature status and redistribution terms NEEDS_REVIEW.