Distances from differences of roots of polynomials to the nearest integers

V. I. Galiev; A. F. Polupanov; I. E. Shparlinski

doi:10.1016/0020-0190(92)90006-H

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 journal › Article › peer-review

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 (n⁴log(H(f)+1))^1+ε is given. This problem arises when constructing algorithms for solving some systems of ODE.

Original language	English
Pages (from-to)	143-146
Number of pages	4
Journal	Information Processing Letters
Volume	43
Issue number	3
DOIs	https://doi.org/10.1016/0020-0190(92)90006-H
Publication status	Published - 14 Sept 1992
Externally published	Yes

Keywords

Algorithms
computational complexity
polynomials with integer coefficients
systems of differential equations

Access to Document

10.1016/0020-0190(92)90006-H

Cite this

@article{bda77d4ac88947fa9bbf145c418eda4f,

title = "Distances from differences of roots of polynomials to the nearest integers",

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.",

keywords = "Algorithms, computational complexity, polynomials with integer coefficients, systems of differential equations",

author = "Galiev, \{V. I.\} and Polupanov, \{A. F.\} and Shparlinski, \{I. E.\}",

year = "1992",

month = sep,

day = "14",

doi = "10.1016/0020-0190(92)90006-H",

language = "English",

volume = "43",

pages = "143--146",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Distances from differences of roots of polynomials to the nearest integers

AU - Galiev, V. I.

AU - Polupanov, A. F.

AU - Shparlinski, I. E.

PY - 1992/9/14

Y1 - 1992/9/14

N2 - 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.

AB - 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.

KW - Algorithms

KW - computational complexity

KW - polynomials with integer coefficients

KW - systems of differential equations

UR - https://www.scopus.com/pages/publications/28144442439

U2 - 10.1016/0020-0190(92)90006-H

DO - 10.1016/0020-0190(92)90006-H

M3 - Article

AN - SCOPUS:28144442439

SN - 0020-0190

VL - 43

SP - 143

EP - 146

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

Distances from differences of roots of polynomials to the nearest integers

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this