Distances from differences of roots of polynomials to the nearest integers

V. I. Galiev, A. F. Polupanov*, I. E. Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

We present tight bounds for distances from differences of roots of the polynomial f(x)∈R[x] over a discrete normed commutative ring R without zero divisors to the nearest element of R. In the case most interesting for applications, R=Z, an algorithm for the determination of the existence of nonzero integers among these differences in time (n4log(H(f)+1))1+ε is given. This problem arises when constructing algorithms for solving some systems of ODE.

Original languageEnglish
Pages (from-to)143-146
Number of pages4
JournalInformation Processing Letters
Volume43
Issue number3
DOIs
Publication statusPublished - 14 Sep 1992
Externally publishedYes

Keywords

  • Algorithms
  • computational complexity
  • polynomials with integer coefficients
  • systems of differential equations

Fingerprint Dive into the research topics of 'Distances from differences of roots of polynomials to the nearest integers'. Together they form a unique fingerprint.

Cite this