Rationalize this denominator

[@nrohgof Foghorn Leghorn]

Let a,b,c be nonzero rational numbers, and let cbrt denote the
cube-root function. How can we rationalize the denominator of
1/(a+cbrt(b)+cbrt(c)) ?

This would be possible if we had a polynomial f(x,y,z) with rational
coefficients such that, in the product (x+y+z)f(x,y,z), all occurences
of the variables y and z have exponents divisible by 3. However, I
don't know of such a polynomial or how to find one.

Foghorn Leghorn
moc.enecswen @ nrohgof

[Nobody]

Foghorn Leghorn > wrote in message ...

x+y+z divides (x^3+y^3+z^3)^3 - 27(xyz)^3,

so 1/(cbrt(a)+cbrt(b)+cbrt(c)) can be rationalized to
(something) / ((a+b+c)^3-27abc).

[RM Mentock]

That would be (something) / ((a+b+c)^3-27CBRT(abc)), wouldn't it?

--
RM Mentock

Reality is merely an illusion, albeit a very persistant one -- A.E.

[Nobody]

RM Mentock wrote in message <3DBA439A...@mindspring.com>...

>Nobody wrote:
>>
>> x+y+z divides (x^3+y^3+z^3)^3 - 27(xyz)^3,
>>
>> so 1/(cbrt(a)+cbrt(b)+cbrt(c)) can be rationalized to
>> (something) / ((a+b+c)^3-27abc).
>
>That would be (something) / ((a+b+c)^3-27CBRT(abc)), wouldn't it?
>

No. It wouldn't.

[Stephen J. Herschkorn]

>
>
>
>x+y+z divides (x3+y3+z3)3 - 27(xyz)3
>

Yes, that is correct. How did you come to that result? That is, how
did you see it?

A much more general question: Is it always possible to rationalize a
denominator of radicals? Formally, let D be the extension of Z
which is closed under radicals of positive numbers. That is, D is
the smallest subring of R which contains 1 and has the property that,
for every positive x in D and positive integer n, there exists y
in D such that y^n = x. Is it true that for all x in D there
exists y in D such that xy is in Z?

--
Stephen J. Herschkorn hers...@rutcor.rutgers.edu

[Stephen J. Herschkorn]

> let D be the extension of Z which is closed under radicals of
> positive numbers. That is, D is the smallest subring of R which
> contains 1 and has the property that, for every positive x in D
> and positive integer n, there exists y in D such that y^n = x.

By the way, does D have a name?

[Nobody]

Stephen J. Herschkorn wrote in message
<3DBADF0...@rutcor.rutgers.edu>...

>>
>>
>>
>>x+y+z divides (x3+y3+z3)3 - 27(xyz)3
>>

It was " x+y+z divides (x^3+y^3+z^3)^3 - 27(xyz)^3,"
in my original post.

>
>Yes, that is correct. How did you come to that result? That is, how
>did you see it?
>

x+y+z divides x^3+y^3+z^3-3xyz,
which in turn divides (x^3+y^3+z^3)^3-(3xyz)^3.

>A much more general question: Is it always possible to rationalize a
>denominator of radicals?

Let r be a sum of radicals. Then r is algebraic over Z.
If we write its minimal polynomial as x*P(x) - k = 0,
where P(x) is in Z[x] and k is a non-zero integer,
then 1/r can be rationalized to P(r)/k.

[Virgil]

In article <yPBu9.1846$zX1...@newssvr16.news.prodigy.com>,
"Nobody" <STB...@prodigy.dot.net> wrote:

> Let r be a sum of radicals. Then r is algebraic over Z.
> If we write its minimal polynomial as x*P(x) - k = 0,
> where P(x) is in Z[x] and k is a non-zero integer,
> then 1/r can be rationalized to P(r)/k.

But how would you do it for, say,
1/(sqrt(2) + sqrt(3) + sqrt(5) + sqrt(7) + sqrt(11))?

[Stephen J. Herschkorn]

>
>
>But how would you do it [rationalize the denominator] for, say,

>1/(sqrt(2) + sqrt(3) + sqrt(5) + sqrt(7) + sqrt(11))?
>
>

Since I am a lazy typist, I use s(") in place of sqrt("). You may verify
that

(s(2)+ s(3)+s(5)+s(7)+s(11)) x
(s(2)+s(3)+s(5)-(s(7)+s(11))) x
(-4+s(6)+s(10)+s(15)+s(77)) x
(-15+s(6)+s(10)+2s(15)) x
(161+50s(6))

is an integer (43684, to be precise).

I did this by trial and error using Mathematica®:

In[9]:= a=Sqrt[2] + Sqrt[3] + Sqrt[5] + Sqrt[7] + Sqrt[11]

In[21]:= b=Expand[a(Sqrt[2] + Sqrt[3] + Sqrt[5]-(Sqrt[7] + Sqrt[11]))]

Out[21]= -8 + 2 Sqrt[6] + 2 Sqrt[10] + 2 Sqrt[15] - 2 Sqrt[77]

In[23]:= c=Expand[b(b+4Sqrt[77])]

Out[23]= -120 + 8 Sqrt[6] - 8 Sqrt[10] - 16 Sqrt[15]

In[25]:= d=Expand[c(c+16(Sqrt[10]+2Sqrt[15]))]

Out[25]= 10304 - 3200 Sqrt[6]

I do not know of a general algorithm for rationalization of
denominators. Does anyone? The existence proof (see, for example,
chapter on field in Herstein IN, Topics in Algebra) is not constructive.

[Stephen J. Herschkorn]

> But how would you do it [rationalize the denominator] for, say,
> 1/(sqrt(2) + sqrt(3) + sqrt(5) + sqrt(7) + sqrt(11))?
>

>> I do not know of a general algorithm for rationalization of
>> denominators. Does anyone? The existence proof (see, for example,
>> chapter on field in Herstein IN, Topics in Algebra) is not constructive.
>

> It was the possibility of a general algorithm I was really looking
> for, although the problem I set was one I failed at back in the days
> before electronic aids were available.

I am toying with following the details of the nonconstructive proofs in
Herstein and seeing if I can turn them into a constructive one, at
least for the exmple cited above. Anyone else care to try?

[Stephen J. Herschkorn]

> But how would you do it [rationalize the denominator] for, say,
> 1/(sqrt(2) + sqrt(3) + sqrt(5) + sqrt(7) + sqrt(11))?
>

>> I do not know of a general algorithm for rationalization of
>> denominators. Does anyone? The existence proof (see, for example,
>> chapter on field in Herstein IN, Topics in Algebra) is not constructive.
>

Here is an algorithm which will work for sums of square roots.

Given x = a0 + sum(a_i * sqrt(b_i), i = 1 to m), where the a_i and
b_i are integers, the b_i are positive, and none of the b_i have
square factors. We wish to find a finite sequence y of linear integer
combinations of square roots such that x * prod(y) is an integer.

Let p be the largest prime which divides b_i for some i, c =
sum {a_i *sqrt(b_i): p | b_i}, and z = x*(2c-x) = c^2 - (x-c)^2.
Then z is a linear integer combination of square roots (i.e., with
square factors removed), and the greatest prime which divides the
reduced "square-rooted" terms of z (i.e., with square factors removed)
is strictly less than p.

Now set x = z and repeat until no square-root terms remain.

We can clearly generalize this method to sums of nth roots of integers
(set z = c^n + [(-1)^(n+1)] * (x-c)^n), and we can convert sums of
mixed roots to sums of roots by the least common factor. (Or, better,
remove nth roots in order of descending n.)

The most number of iterations this algorithm takes is the number of
primes which divide prod(b_i, i = 1 to m). Are there more efficient
algorithms?

And how do we handle radicals of radicals, e.g., 1/((1+sqrt(2))^(1/5) +
(10+sqrt(3+5^(1/4)))^(1/5) + 13^(1/5))?

[Nobody]

Stephen J. Herschkorn wrote in message

<3DBB2E86...@rutcor.rutgers.edu>...

Let r = a1*m1^(1/n1) + ... + at*mt^(1/nt),
where for each i ai is a non-zero integer,
mi and ni are pos. integers.

[If we can do it for integers, we can do it for rationals.]

Let us write bi for mi^(1/ni).
Then the product of _all_ expressions of the form
e1*a1*b1 + e2*a2*b2 + ... + et*at*bt,
where ei is _any_ (complex) ni-th root of unity,
is an integer which we'll call h.

Thus 1/r = s/h,
where s is the product of all expressions of the form
e1*a1*b1 + e2*a2*b2 + ... + et*at*bt,
where ei is _any_ ni-th root of unity,
but with (e1, e2, ..., et) =/= (1, 1, ..., 1).

To show that s is in Z[b1, b2, ..., bt],
note that the product of all expressions of the form
x - (e1*a1*b1 + e2*a2*b2 + ... + et*at*bt),
where ei is _any_ ni-th root of unity, is in Z[X].
If we write this polynomial as x*P(x) - k,
then 1/r = P(r)/k.
Since h = (+/-)k, so s = (+/-)P(r), and is in Z[b1,..bt].

[Iain Davidson]

Stephen J. Herschkorn <hers...@rutcor.rutgers.edu> wrote in message
news:3DBB3843...@rutcor.rutgers.edu...

There is a general method based on companion matrices and their
characteristic equations.
If,say, x^3 -2x^2 +3x -5 = 0
its companion matrix C is
| 0 1 0|
| 0 0 1|
|5 -2 2|
i.e. the eigenvalues of C
satisfy x^3 -2x^2 +3x -5 = 0

If the expression you want to rationalize is
1/(a + br + cr^2), r^3 -2r^2 +3r -5 = 0
The matrix, M, that has u = (a + br + cr^2) as an
eigenvalue is
a*I_3 + b*C + c*C^2 = M

Find the inverse of M , then 1/(a + br + cr^2) =t
satisfies an equation of the form
t^3 -Pt^2 -Qt - R =0

t = P +Qu + Ru^2

If you have an expression of the form, say,
u = A*sqrt(2) + B*cubrt(3) where the companion
matrices have different order you have to use
the Kronecker product.

[Oscar Lanzi III]

There's a neat way to do it with a sum of any number of square roots of
rational numbers.

We suppose that there are 2^k square roots -- if not, insert sqrt(0)
terms to make it so. Now treat the square roots as a vector and dot
multiply it successively with the columns of what is known as a
"two-level orthgonal array". The term comes from the theory of
statistical experimental design, which describes how the arrays can be
built for any number of rows and columns equal to 2^k. The resulting
array consists of a column of +1's followed by 2^k-1 columns containing
+1 and -1, patterned in such fashion that any two columns (or any two
rows) will be orthogonal to each other.

Then multiply the dot products together. The result is a rational
number.

Example: rationalize 1+sqrt(2)+sqrt(3).

Render it as sqrt(1)+sqrt(2)+sqrt(3)+sqrt(0), adding one zero term to
make 2^2 terms in all. The appropriate orthogonal array for 2^2 terms
is (best viewed in fixed width fonts):

+1 +1 +1 +1
+1 -1 +1 -1
+1 +1 -1 -1
+1 -1 -1 +1

So our dot products are

sqrt(1)+sqrt(2)+sqrt(3)+sqrt(0) sqrt(1)-sqrt(2)+sqrt(3)-sqrt(0)
sqrt(1)+sqrt(2)-sqrt(3)-sqrt(0)
sqrt(1)-sqrt(2)-sqrt(3)+sqrt(0)

or, removing sqrt(0) and setting sqrt(1) = 1:

1+sqrt(2)+sqrt(3)
1-sqrt(2)+sqrt(3)
1+sqrt(2)-sqrt(3)
1-sqrt(2)-sqrt(3)

and the product of these four numbers is

-8

The method works also with negative square roots in the original sum.
Simply insert a negative square root in place of the positive one in the
appropriate slot in the square root vector, then carry out the operation
described above. Thus if we start with 1-sqrt(2)+sqrt(2), we will have
-sqrt(2) in the original vector and change the sign of sqrt(2) in all
the dot products given above. We end up in this case with the same set
of dot procuts in a different order, and again multiplying them together
gives the rational product -8.

--OL

[Stephen J. Herschkorn]

>
>
>But how would you do it [rationalize the denominator] for, say,
>1/(sqrt(2) + sqrt(3) + sqrt(5) + sqrt(7) + sqrt(11))?
>

> Here is an algorithm which will work for sums of square roots.

>
> Given x = a0 + sum(a_i * sqrt(b_i), i = 1 to m), where the a_i and
> b_i are integers, the b_i are positive, and none of the b_i
> have square factors. We wish to find a finite sequence y of linear
> integer combinations of square roots such that x * prod(y) is an
> integer.
>
> Let p be the largest prime which divides b_i for some i, c =

> sum {a_i *sqrt(b_i): p | b_i}, and z = x*(2c-x) = c2 - (x-c)2.

> Then z is a linear integer combination of square roots (i.e., with
> square factors removed), and the greatest prime which divides the
> reduced "square-rooted" terms of z (i.e., with square factors
> removed) is strictly less than p.
>
> Now set x = z and repeat until no square-root terms remain.
>
> We can clearly generalize this method to sums of nth roots of
> integers (set z = c^n + [(-1)^(n+1)] * (x-c)^n)

Oops. Not only is that generalization not clear, it is wrong. One can
see this by applying the algorithm to cbrt(2) + cbrt(4). I can fix this
for sums of cube roots:
letting p be the largest prime as before and rewrite x as a cbrt(p) +
b cbrt(p^2) + c, where the cbrt(p) does not divide (in Z extended by
cube roots) a, b, or c (which are not integers in this formula). Call
this u+v+w by matching up the three summands in order. Then, as
Nobody has indicated, z = x*(u^2+v^2+w^2-uv-vw-uv) = u^3 + v^3 + w^3 -
3uvw, where all cube roots of powers of p disappear.

To get this to work for general nth roots, we need a polynomial
q_n(x1,x2,...,x_n) such that (x1+x2+...+x_n) divides
q_n(x1,x2,...,x_n) and roots of powers of prime p drop out of
q_n(c0, c1 p^(1/n), c2 p^(2/n),..., c_(n-1) p^[(n-1)/n]). (Homogeneity
is not a sufficient condition for q_n to satisfy the latter property; is
it necessary?) I suspect there is always such a polynomial; does
anyone (or Nobody) know its general form?

On other algorithms: Thanks to Nobody (I don't mean that pejoratively!)
for showing an easily described construction of denominator
rationalization. However, modestly (:-), it looks to me like my method
is more efficient. For example, in Virgil's problem, my algorithm
finishes after at most five iterations (it actually ends in four), while
Nobody's method requires multiplication by 32 sums of five terms each.
Perhaps closer inspection and tinkering will show my algorithm requires
more work (e.g., determination of prime factors and the use of these
polynomials q_n) and Nobody's can be made more efficient.

Iain's algorithm is quite nice, though I wonder about the complexity of
the matrix operations; again, perhaps these can be implemented
efficiently. Oscar's algorithm for square roots is also nice, but again
requires a large number of multiplications.

[Oscar Lanzi III]

I had a typo at one point. I mentioned 1-sqrt(2)+sqrt(2) near the end,
and I meant 1-sqrt(2)+sqrt(3). Of course 1-sqrt(2)+sqrt(2) is trivial.

My math, I hope, is better than my typing.

--OL

[Oscar Lanzi III]

I have a hunch that with complex cases we WILL have a nontrivial amount
of arithmetic with any algorithm (if this is a problem with square
roots, as Stephen Herschkorn suggests, perish the thought of what to do
with more complicated radicals). Possibly the better part of this
problem, even for square roots, is optimizing the arithmetic operations.
Maybe we can use symmetry characterisrtics to derive some products from
others?

--OL