Use of algebraically independent numbers for zero recognition of polynomial terms

Daniel Richardson, Ahmed El-Sonbaty

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

A polynomial term is a tree with operators *, +, - on the interior nodes and natural numbers and variables on the frontier. We attempt to decide whether or not such a tree represents the zero polynomial by substituting algebraically independent real numbers for the variables and attempting to decide whether or not the resulting constant is zero. From this we get a probabilistic zero recognition test which is somewhat more expensive computationally than the usual method of choosing random integers in a large interval and evaluating, but which depends on the ability to choose a random point in the unit cube and to approximate a polynomial at that point. We also state a conjecture about algebraic independence measure which would give us a deterministic test with a uniformly chosen test point. The result is that if a polynomial term has s(T) nodes, then the bit complexity of deterministic zero recognition is bounded by O(s(T)M(s(T) length(T))), where length(T) measures the length of the term T, and M(n) is the bit complexity of multiplication of two n-digit natural numbers.
Original languageEnglish
Pages (from-to)631-637
Number of pages7
JournalJournal of Complexity
Volume19
Issue number5
DOIs
Publication statusPublished - 2003

Fingerprint

Polynomials
Natural number
Polynomial
Zero
Term
Polynomial Zeros
Algebraic Independence
Unit cube
Vertex of a graph
Digit
Trees (mathematics)
Multiplication
Interior
Choose
Mathematical operators
Interval
Integer
Operator

Cite this

Use of algebraically independent numbers for zero recognition of polynomial terms. / Richardson, Daniel; El-Sonbaty, Ahmed.

In: Journal of Complexity, Vol. 19, No. 5, 2003, p. 631-637.

Research output: Contribution to journalArticle

Richardson, Daniel ; El-Sonbaty, Ahmed. / Use of algebraically independent numbers for zero recognition of polynomial terms. In: Journal of Complexity. 2003 ; Vol. 19, No. 5. pp. 631-637.
@article{e7519be8e8c94bdf899ce08a2d6206c1,
title = "Use of algebraically independent numbers for zero recognition of polynomial terms",
abstract = "A polynomial term is a tree with operators *, +, - on the interior nodes and natural numbers and variables on the frontier. We attempt to decide whether or not such a tree represents the zero polynomial by substituting algebraically independent real numbers for the variables and attempting to decide whether or not the resulting constant is zero. From this we get a probabilistic zero recognition test which is somewhat more expensive computationally than the usual method of choosing random integers in a large interval and evaluating, but which depends on the ability to choose a random point in the unit cube and to approximate a polynomial at that point. We also state a conjecture about algebraic independence measure which would give us a deterministic test with a uniformly chosen test point. The result is that if a polynomial term has s(T) nodes, then the bit complexity of deterministic zero recognition is bounded by O(s(T)M(s(T) length(T))), where length(T) measures the length of the term T, and M(n) is the bit complexity of multiplication of two n-digit natural numbers.",
author = "Daniel Richardson and Ahmed El-Sonbaty",
note = "ID number: ISI:000185363300001",
year = "2003",
doi = "10.1016/s0885-064x(03)00047-5",
language = "English",
volume = "19",
pages = "631--637",
journal = "Journal of Complexity",
issn = "0885-064X",
publisher = "Elsevier Academic Press Inc",
number = "5",

}

TY - JOUR

T1 - Use of algebraically independent numbers for zero recognition of polynomial terms

AU - Richardson, Daniel

AU - El-Sonbaty, Ahmed

N1 - ID number: ISI:000185363300001

PY - 2003

Y1 - 2003

N2 - A polynomial term is a tree with operators *, +, - on the interior nodes and natural numbers and variables on the frontier. We attempt to decide whether or not such a tree represents the zero polynomial by substituting algebraically independent real numbers for the variables and attempting to decide whether or not the resulting constant is zero. From this we get a probabilistic zero recognition test which is somewhat more expensive computationally than the usual method of choosing random integers in a large interval and evaluating, but which depends on the ability to choose a random point in the unit cube and to approximate a polynomial at that point. We also state a conjecture about algebraic independence measure which would give us a deterministic test with a uniformly chosen test point. The result is that if a polynomial term has s(T) nodes, then the bit complexity of deterministic zero recognition is bounded by O(s(T)M(s(T) length(T))), where length(T) measures the length of the term T, and M(n) is the bit complexity of multiplication of two n-digit natural numbers.

AB - A polynomial term is a tree with operators *, +, - on the interior nodes and natural numbers and variables on the frontier. We attempt to decide whether or not such a tree represents the zero polynomial by substituting algebraically independent real numbers for the variables and attempting to decide whether or not the resulting constant is zero. From this we get a probabilistic zero recognition test which is somewhat more expensive computationally than the usual method of choosing random integers in a large interval and evaluating, but which depends on the ability to choose a random point in the unit cube and to approximate a polynomial at that point. We also state a conjecture about algebraic independence measure which would give us a deterministic test with a uniformly chosen test point. The result is that if a polynomial term has s(T) nodes, then the bit complexity of deterministic zero recognition is bounded by O(s(T)M(s(T) length(T))), where length(T) measures the length of the term T, and M(n) is the bit complexity of multiplication of two n-digit natural numbers.

UR - http://dx.doi.org/10.1016/s0885-064x(03)00047-5

U2 - 10.1016/s0885-064x(03)00047-5

DO - 10.1016/s0885-064x(03)00047-5

M3 - Article

VL - 19

SP - 631

EP - 637

JO - Journal of Complexity

JF - Journal of Complexity

SN - 0885-064X

IS - 5

ER -