For integer polynomials whose coefficients carry small errors (e.g., rounded from empirical data), Nagasaka (J. Symbolic Computation 46(12):1306-1317, 2011) defined an approximate GCD over integers — a nontrivial common factor hh recoverable after perturbing both inputs by integer error polynomials of norm at most a tolerance ε\varepsilon — and gave a search algorithm that builds lattices from the subresultant mapping and applies LLL lattice basis reduction to find integer cofactors and the integer GCD. The algorithm works for moderate tolerances with both inputs perturbable, but it is a heuristic: the paper's own closing remarks state that no concrete upper or lower bound on the tolerance ε\varepsilon is known under which the search provably succeeds (its search condition is explicitly not a necessary condition), document rare counter-condition inputs where the true cofactor-encoding lattice vector is present but not short so LLL cannot find it. This theoretical gap remains open. The open problem is to give the lattice-LLL approach to approximate polynomial GCD over integers a provable tolerance theory — concrete conditions on ε\varepsilon under which an approximate GCD over integers exists and the LLL search provably finds one — that in particular classifies the documented rare counter-condition inputs.

Background

Approximate polynomial GCD treats input polynomials whose coefficients carry small errors: instead of the exact GCD (almost always a constant for generic inputs), one seeks a nontrivial common factor of degree at least 1 that appears after perturbing the coefficients by at most a tolerance ε\varepsilon. Most known algorithms (QR-based, optimization-based, and structured low-rank methods) work over the real or complex numbers. When the coefficients are integers — for example rounded from empirical data — those methods are inappropriate: they perturb over the reals, return nonintegral coefficients, and rounding their output back to integers generally destroys the numerical proximity, so no nearby integer polynomials with a nontrivial integer common factor are obtained.

Definition (Nagasaka 2011). For polynomials f,g∈Z[x1,…,xℓ]f,g\in\mathbb{Z}[x_1,\dots,x_\ell] and a nonnegative integer ε\varepsilon, a polynomial h∈Z[x⃗]h\in\mathbb{Z}[\vec{x}] is an approximate GCD over integers with tolerance ε\varepsilon if there exist integer cofactors t,st,s and integer error polynomials Δf,Δg\Delta_f,\Delta_g with

f(x⃗)=t(x⃗) h(x⃗)+Δf(x⃗),g(x⃗)=s(x⃗) h(x⃗)+Δg(x⃗),ε=max⁡{∥Δf∥,∥Δg∥},f(\vec{x})=t(\vec{x})\,h(\vec{x})+\Delta_f(\vec{x}),\qquad g(\vec{x})=s(\vec{x})\,h(\vec{x})+\Delta_g(\vec{x}),\qquad \varepsilon=\max\{\|\Delta_f\|,\|\Delta_g\|\},

where ∥⋅∥\|\cdot\| is a coefficient norm (the max norm in the implementation).

Two algorithm families exist for this problem. von zur Gathen, Mignotte, and Shparlinski (2010), adapting Howgrave-Graham's approximate integer common divisor technique (the cryptographic AGCD problem, i.e. approximate common divisors of integers as numbers rather than of polynomial coefficient vectors), gave a guaranteed algorithm, but it requires one input polynomial to be given exactly (unperturbed) and works only for very tiny tolerances. Nagasaka (2011) gave the other. Using the subresultant mapping Sr(f,g):(s,t)↦sf+tgS_r(f,g):(s,t)\mapsto s f+t g — the linear map on polynomial pairs whose near-null vectors encode degree-rr common factors, with the cofactor of gg entering the search with a negated sign, so that for the true cofactors sf+tg=sΔf+tΔgs f+t g=s\Delta_f+t\Delta_g holds exactly — he builds an integer lattice L(f,g,r,c)\mathcal{L}(f,g,r,c) (identity block adjoining cc times the subresultant matrix transpose) whose short vectors encode candidate integer cofactors, applies the LLL lattice basis reduction algorithm (Lenstra–Lenstra–Lovász) to find them, then applies LLL to a second lattice H(f,g,r,c′,t,s)\mathcal{H}(f,g,r,c',t,s) to recover the integer coefficients of the GCD itself, accepting a candidate triple when ∥f−th∥+∥g−sh∥≤2ε\|f-th\|+\|g-sh\|\le 2\varepsilon; three cheap necessary conditions (Criteria 1–3, on constant terms, degree consistency, and leading-monomial coefficients) prune invalid candidates early. The paper extends the construction to several polynomials and reports experiments (100 random pairs, 94 successes). Its guarantees, however, are only lemmas of the form: if the inputs are exactly divisible and rr is the true subresultant order, then the lattice contains a suitable short vector, provided the scaling constant cc is large enough relative to the factor-coefficient bound BB — an a priori upper bound on the absolute value of the coefficients of any factor of ff and gg, for which the paper uses classical bounds on factor coefficient sizes (the Landau–Mignotte bound in the univariate case, Gelfond's bound in the multivariate case). No condition on ε\varepsilon — necessary or sufficient — is known under which the search succeeds on genuinely perturbed inputs, and the paper documents rare inputs where the cofactor-encoding lattice vector is present but not short, so LLL cannot find it (the column-scaling heuristic recovers only 5.9% of such failure cases).

Problem Statement

Let f,g∈Z[x⃗]f,g\in\mathbb{Z}[\vec{x}] be integer polynomials with total degrees n,mn,m and bounded coefficients, and consider the lattice search of Nagasaka (2011): lattices L(f,g,r,c)\mathcal{L}(f,g,r,c) and H(f,g,r,c′,t,s)\mathcal{H}(f,g,r,c',t,s) built from the subresultant mapping, LLL reduction to enumerate short vectors as candidate integer cofactors and GCD coefficients, the acceptance test ∥f−th∥+∥g−sh∥≤2ε\|f-th\|+\|g-sh\|\le 2\varepsilon, and Criteria 1-3 pruning. The problem is to give this algorithm a theory matching its practice — a provably reliable lattice-based algorithm for approximate polynomial GCD over the integers: characterize the tolerances ε\varepsilon — by concrete conditions, such as upper or lower bounds as functions of nn, mm, the coefficient sizes, and the factor-coefficient bound BB (an a priori upper bound on the absolute value of the coefficients of any factor of ff and gg) — under which (a) an approximate GCD over integers with tolerance ε\varepsilon exists, and (b) the LLL short-vector search provably finds one. The characterization must in particular classify the documented 'rare counter condition' inputs, where ∥sf+tg∥=∥sΔf+tΔg∥≫0\|s f+t g\|=\|s\Delta_f+t\Delta_g\|\gg 0 (an identity for the true cofactors under the subresultant search's sign convention, in which the cofactor of gg is negated) and the true cofactor-encoding vector lies in the lattice but is not short.

References

  1. Kosaku Nagasaka. Approximate polynomial GCD over integers. Journal of Symbolic Computation 46(12):1306-1317, 2011. DOI 10.1016/j.jsc.2011.08.011, https://doi.org/10.1016/j.jsc.2011.08.011
  2. Kosaku Nagasaka. An improvement in the lattice construction process of approximate polynomial GCD over integers. Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation (SNC 2011), pp. 63-64, 2011. DOI 10.1145/2331684.2331694, https://doi.org/10.1145/2331684.2331694
  3. Kosaku Nagasaka. Approximate Polynomial GCD over Integers with Digits-wise Lattice. Communications of JSSAC (Japan Society for Symbolic and Algebraic Computation) 2:15-32, 2016 (no DOI; volume table of contents at https://www.jssac.org/Editor/CJssac/V02/index.html; author preprint at http://wwwmain.h.kobe-u.ac.jp/~nagasaka/research/preprints/preprint2011_dwl_rev.pdf)
  4. Kosaku Nagasaka. Approximate polynomial GCD over integers (ISSAC 2008 poster abstract). ACM Communications in Computer Algebra 42(3):124-126, 2008. DOI 10.1145/1504347.1504351, https://doi.org/10.1145/1504347.1504351
  5. Joachim von zur Gathen, Maurice Mignotte, Igor E. Shparlinski. Approximate polynomial gcd: Small degree and small height perturbations. Journal of Symbolic Computation 45(8):879-886, 2010. DOI 10.1016/j.jsc.2010.04.001, https://doi.org/10.1016/j.jsc.2010.04.001
  6. Nick Howgrave-Graham. Approximate integer common divisors. Cryptography and Lattices (CaLC 2001), Lecture Notes in Computer Science 2146, pp. 51-66, 2001. DOI 10.1007/3-540-44670-2_6, https://doi.org/10.1007/3-540-44670-2_6
  7. Mohamed Elkadi, André Galligo, Thang Luu Ba. Approximate GCD of several univariate polynomials with small degree perturbations. Journal of Symbolic Computation 47(4):410-421, 2012. DOI 10.1016/j.jsc.2011.09.005, https://doi.org/10.1016/j.jsc.2011.09.005
  8. Kosaku Nagasaka. Toward the best algorithm for approximate GCD of univariate polynomials. Journal of Symbolic Computation 105:4-27, 2021. DOI 10.1016/j.jsc.2019.08.004, https://doi.org/10.1016/j.jsc.2019.08.004
  9. Randell Heyman, Igor E. Shparlinski. On the greatest common divisor of shifted sets. Journal of Number Theory 154:63-73, 2015. DOI 10.1016/j.jnt.2015.02.012, https://doi.org/10.1016/j.jnt.2015.02.012
  10. Kosaku Nagasaka. Approximate GCD of several multivariate sparse polynomials based on SLRA interpolation. Journal of Symbolic Computation 127:102368, 2025. DOI 10.1016/j.jsc.2024.102368, https://doi.org/10.1016/j.jsc.2024.102368