patternMinor
Decidability of Equality of Radical Expressions
Viewed 0 times
radicalequalityexpressionsdecidability
Problem
Consider terms built from elements of $\mathbb Q$ and the operations $+,\times,-,/$, and $\sqrt[n]{\,\cdot\,}$ for each natural number $n$. Given the promise that two terms are well-formed -- that is, there is no division by zero, and no even roots of negative numbers -- is there an algorithm which decides when the two terms are equal?
A related question was posted here, but it is more general (as it allows arbitrary exponentiation, rather than just by rational numbers).
A related question was posted here, but it is more general (as it allows arbitrary exponentiation, rather than just by rational numbers).
Solution
- Algebraic numbers are solutions of polynomials with rational coefficients.
- $+,\times,-,/$ of algebraic numbers result in algebraic numbers because algebraic numbers form a field (1). This means nested radicals are algebraic numbers too (2).
- Nested radicals can be denested by algorithm (3,4).
- Each algebraic number of degree $n$ can be uniquely represented as a $n$ by $n$ matrix of integers under a suitable basis (for example, $[1,x, (x^2+1)/2]$). This representation allows symbolic evaluation of $+,\times,-,/$ by matrix addition, multiplication, and inverse (p.159 of 5,6,7).
- Two terms are equal if their unique representations are identical.
Context
StackExchange Computer Science Q#64392, answer score: 3
Revisions (0)
No revisions yet.