Joined: 4/20/2005
Posts: 2160
Location: Norrköping, Sweden
Topic revival! Here are some interesting problems for you to solve:
A number is algebraic if it is the solution to the equation an*x^n + a(n-1)*x^(n-1) + ... + a1*x1 + a0 = 0, where a1, a2, ... an are integers, not necessarily positive. If the number is not algebraic it's called transcendental.
If a statement below is true, prove it. It it's not true, prove why this is not the case, or at least provide an example where it doesn't hold:
1) A finite linear combination of algebraic numbers are always algebraic. What happens if you have an infinite number of algebraic numbers?
2) A finite product of algebraic numbers are always algebraic. What happens if you have an infinite number of algebraic numbers?
3) Same as 1) but for transcendental numbers.
4) Same as 2) but for transcendental numbers.
5) It is possible to create a function f(a1, a2, ... ,an) that takes a finite number of algebraic numbers to a transcendental number, without f involving any transcendental numbers.
(Note that I do not know the answers to these questions myself, I have just recently been introduced to these terms in school, but it would be interesting to see if any of those statements are true).
1) and 2) are answered on wikipedia, but not proven there.
3) won't hold. Let a and b be transcendental numbers: the linear combination (0*a+0*b) = 0 is algebraic.
4) won't hold either. Just pick an algebraic number a and a transcendental number b, let c = a/b. c should be transcendental as well. Now you've got a pair of transcendental numbers where c*b = a is algebraic.
5) there's of course sin(), cos(), ln() and others that yield transcendental numbers for most algebraic parameters. (sin(0) and ln(1) are algebraic of course).
I don't know if they "involve transcendental numbers", since your requirement isn't clearly defined.
3) pi is transcendental, and so is 4-pi. pi + (4-pi) = 4 is algebraic. (Basically the same as the answer to 4 given above.)
5) I'm not sure what you mean by "involving any transcendental numbers". That said, (2+abs(x))^sqrt(2) should probably work regardless of your definition (if you consider it as a limit where the exponent is approached by rational numbers, thus avoiding any possible mention of transcendental numbers in the definition of exponentiation).
1,2) pi = 4-(4/3)+(4/5)-(4/7)+... = 2*(2/1)*(2/3)*(4/3)*(4/5)*...
So the answer is no in both cases.
3,4) pi, 1-pi, and 1/pi are all transcendental, but pi+(1-pi) = pi*(1/pi) = 1
5) If f is polynomial, then of course not.
If f has the a_i as a power, then the function f=a_1^a_2 works, since for a_1=2, a_2=sqrt(2), 2^sqrt(2) is transcendental by the Gelfond–Schneider theorem.
Joined: 5/2/2006
Posts: 1020
Location: Boulder, CO
Here is a funny challenge--
Write an expression that can generate every string of letters, containing only a and b, where the number of a's is even, and the number of b's is even.
use the * for repeat, and V to represent or.
an example expression could be something like (BB)*, which could generate any string containing only B's where the number of B's is even.
Another useful example is (AVB)*, which can generate any string containing only A's and B's.
Note that there is an answer, but its not pretty.
Here's an easy one, but which might require a bit of ingenuity (I loved this one at school):
lim(x->0+) x^x = ?
("x->0+" means that x approaches zero from the positive axis.)
Give your entire deduction process, not just the plain answer.
For additional fun, try imagining how the graphical representation of the x^x curve looks like before actually checking it.
Joined: 4/20/2005
Posts: 2160
Location: Norrköping, Sweden
I was thinking something like this: Let
y=lim(x->0+) x^x
and let z := ln(y) = lim(x->0+) x*ln(x) which I happened to remember that it approaches 0.
so y = exp(z) approaches exp(0)=1 so the answer is that y approaches 1.
This is probably not the right way of solving it, but it worked. :)
lim(x->0+)x^x=e^(lim(x->0+)x*ln(x))=e^(lim(x->0+)ln(x)/(1/x))=e^lim(x->0+)(1/x)/(-1/x^2))=e^(lim(x->0+)-x^2)=e^0=1 by L'Hôpital's Rule; in fact, it can be proven that if f and g are meromorphic functions of a complex variable z and f(c)=g(c)=0≠f(b) for some b and c in their common domain, then lim(z->c)f(z)^g(z)=1.
let y = x^x
ln y = ln(x^x)
ln y = x ln x
1/y dy/dx = x*(1/x) + (ln x)*1
1/y dy/dx = 1 + ln x
dy/dx = y + y ln x
dy/dx = x^x + x^x ln x
set dy/dx = 0, solve for x
x^x + x^x ln x = 0
x^x ln x = -x^x
ln x = -1
x = e^(-1) = 1/e
Therefore, the minimum value of x^x is (1/e)^(1/e) = 1/e^(1/e) = (e root of e)^(-1)
x^x = exp(ln(x)x), and since ln(x) varies logarithmically with x, it approaches negative infinity more slowly than x, and therefore ln(x)x approaches 0, so x^x approaches 1. by the way, i'm in the camp that defines 0^0 = 1.
i think that the minimum value of x^x would approach 0 as x approaches negative infinity. if you mean where x is a positive real, then the minimum value is exp(-1/e) for x = 1/e.
edit: AQwertyZ beat me to the second one.
Here is a funny challenge--
Write an expression that can generate every string of letters, containing only a and b, where the number of a's is even, and the number of b's is even.
use the * for repeat, and V to represent or.
an example expression could be something like (BB)*, which could generate any string containing only B's where the number of B's is even.
Another useful example is (AVB)*, which can generate any string containing only A's and B's.
Note that there is an answer, but its not pretty.
This should do it I think:
((aa)*|(bb)*|abab|a(bb)*a|b(aa)*b|baba)*
i used | instead of v since it is used in regexps
You can't get abab from that one...unless * is 0 or more repetitions, which is the usual way it's used in defining languages (+ is 1 or more repetitions there)
A similar regular expression is derived in my textbook, Formal Languages and Automata by Peter Linz. The only difference is that the number of bs must be odd instead of even. You can easily represent the solution to the problem as a finite automaton. Then you just follow an algorithm to convert it to a regular expression. The answer turns out to be:
(aa | ab(bb)*ba)*(b | ab(bb)*a)(a(bb)*a | (b | a(bb)*ba)(aa | ab(bb)*ba)*(b | ab(bb)*a))*
I am guessing the regular expression where the number of bs is even is similarly complex.
in fact, it can be proven that if f and g are meromorphic functions of a complex variable z and f(c)=g(c)=0≠f(b) for some b and c in their common domain, then lim(z->c)f(z)^g(z)=1.
I suppose proving that is much more difficult because you can't use the same chain of deductions with generic functions f(x) and g(x).
Bob A wrote:
x^x = exp(ln(x)x), and since ln(x) varies logarithmically with x, it approaches negative infinity more slowly than x, and therefore ln(x)x approaches 0, so x^x approaches 1.
That may be an intuitive proof, but not a formal one, and thus not mathematically valid.
(Besides, even intuitively your deduction is not sound: We are not examining how the two functions behave when they approach infinity, but instead how they behave when they approach x=0. ln(x) actually starts approaching -infinity faster and faster as x gets closer to 0, and it's not at all clear whether x approaches 0 "faster" than ln(x) approaches -infinity.)
by the way, i'm in the camp that defines 0^0 = 1.
Except that you can't use that opinion for anything relating to limits. In other words, if you have this:
lim(x->c) f(x) = 0
lim(x->c) g(x) = 0
lim(x->c) f(x)^g(x) = (lim(x->c) f(x))^(lim(x->c) g(x)) = 0^0 = ?
Even though both functions approach 0, you can't just use your "0^0 = 1" rule and say that the result is 1. There's a simple counter-example: f(x)=0, g(x)=x, for which lim(x->0) f(x)^g(x) = 0.
Joined: 4/20/2005
Posts: 2160
Location: Norrköping, Sweden
Okay, attempt number 2!
lim(x->0)x^x = lim(x->0)(1+(x-1))^x = (use the taylorserie for (1+y)^a with y=x-1 and a=x) =
1 + a1*y + ... + ai*y^ + ...
where ai = x*(x-1)*(x-2)*...*(x-i)/i which closes in on 0 when x closes in on 0 for all i. So all ai are close to 0.
y^i are all numbers that are close to -1 for odd i and close to 1 for even i (because y=x-1 closes in on -1 when x->0). Either way, they are finite and pose no problem when multiplied with a number very close to 0.
So! The sum looks something like this now:
1+ 0*-1 + 0*1 + ... + 0*(+-1) + ... = 1
so the sum, and therefor the expression lim(x->0)x^x, approaches 1.
EDIT: If you don't like it that a is not fix, which it usually is in the taylor serie, just divide the problem into lim(a->0)lim(y->-1)(1+y)^a, making a fix while you compute (1+y)^a and then making a approach 0 afterwards.
You can't get abab from that one...unless * is 0 or more repetitions, which is the usual way it's used in defining languages (+ is 1 or more repetitions there)
* means 0 or more. My solution was wrong but Nitrodon's is correct and shorter too.
Okay, attempt number 2!
lim(x->0)x^x = lim(x->0)(1+(x-1))^x = (use the taylorserie for (1+y)^a with y=x-1 and a=x) =
1 + a1*y + ... + ai*y^ + ...
where ai = x*(x-1)*(x-2)*...*(x-i)/i which closes in on 0 when x closes in on 0 for all i. So all ai are close to 0.
y^i are all numbers that are close to -1 for odd i and close to 1 for even i (because y=x-1 closes in on -1 when x->0). Either way, they are finite and pose no problem when multiplied with a number very close to 0.
So! The sum looks something like this now:
1+ 0*-1 + 0*1 + ... + 0*(+-1) + ... = 1
so the sum, and therefor the expression lim(x->0)x^x, approaches 1.
EDIT: If you don't like it that a is not fix, which it usually is in the taylor serie, just divide the problem into lim(a->0)lim(y->-1)(1+y)^a, making a fix while you compute (1+y)^a and then making a approach 0 afterwards.
That expansion that you used only works if a is constant; however, you can try something like this near r>0 if f(x)=x^x:
Sum(d(f(x),x,r,n)(x-r)^n/n!,n,0,infinity)=
=r^r+r^r*(1+ln(r))(x-r)+r^r*((1+ln(r))^2+1/r)(x-r)^2/2+...
This is a bit simpler if r=1:
Sum(d(f(x),x,1,n)(x-1)^n/n!,n,0,infinity)=
1+(x-1)+(x-1)^2+(x-1)^3/2+(x-1)^4/3+(x-1)^5/12+(x-1)^6*3/40+...
Then just determine the pattern of a_n, the sum of the coefficients of terms in the nth derivative of f with no logarithmic factor, and use the ratio test to determine the radius of convergence: |a_n/a_(n-1)*(x-1)/n|<1 iff |x-1|<n>infinity)n*a_(n-1)/a_n.
Somehow I suspect that the radius of convergence for this series is 1 (because the first derivative, x^x*(1+ln(x)), approaches -infinity as x->0), and for the more general Taylor series it is r, but it is a challenge to determine this.
For positive y, the Taylor series of e^y has only positive terms. Hence e^y is greater than any individual term in the series. In particular, e^y > y^2/2. Thus y*e^-y < y/(y^2/2) = 2/y. Since y*e^-y > 0, this proves that y*e^-y -> 0 as y -> +infinity.
Let x = e^-y. Then y*e^-y = -x*ln(x). This transformation is continuous, and we know the limit of y*e^-y, so therefore we can see that x*ln(x) -> 0 as x -> 0.
x^x = e^(x*ln(x)), and thus we have x^x -> e^0 = 1 as x -> 0.
Continuing with the interesting x^x function:
Warmup problem: Calculate the two solutions for: x^x = 2*x^2 (when x > 0).
A bit harder: For which value of n the equation x^x = n*x^2 has exactly one solution (when x > 0)?
If you want them numerically, they're 2.6983 and .6078 (rounded to 4 decimals). Exact form requires solving the transcendental equation 2^x=2+1/x, which I don't feel like doing, and suspect isn't possible anyways.
The latter merely requires finding the point of tangency of n*x^2 and x^x. the derivative of x^x is x^x*(1+ln x), and the derivative of n*x^2 is 2*n*x. So we solve the simultaneous equations x^x=n*x^2 and x^x*(1+ln x)=2*n*x. multiplying the latter on both sides by x, substituting in the former, and cancelling gives x*(1+ln x)=2. This is another transcendental equation which I don't feel like solving (and suspect isn't possible anyways), but the answer should be a bit more than sqrt(2). Numerically, it's 1.454, which is .04 greater than sqrt(2). solving for n now is simple. n=x^(x-2)=.815
As long as we're having fun with x^x, lets shed our dependence on positive real numbers. For complex z=x+i*y, find a closed form expression for z^z that has no complex exponents except of the form e^(i*a), where a is real.
Exact form requires solving the transcendental equation 2^x=2+1/x, which I don't feel like doing, and suspect isn't possible anyways.
You forgot the word "algebraically" before "possible".
petrie911 wrote:
As long as we're having fun with x^x, lets shed our dependence on positive real numbers. For complex z=x+i*y, find a closed form expression for z^z that has no complex exponents except of the form e^(i*a), where a is real.
z^z=e^(z * log(z))=e^(z * (ln|z|+i*arg(z)))
Assume now that the argument of z is limited to (-pi,pi]. Then:
z^z=e^((x+i*y) * (ln|z|+i*arg(z)))
=e^((x*ln|z|-y*arg(z))+i*(x*arg(z)+y*ln|z|))
=e^(x*ln|z|-y*arg(z))*e^(i*(x*arg(z)+y*ln|z|))
which is of the desired form.
Note that arg(z)=sgn(y)*arccos(x/|z|) if z is not negative real and arg(z)=pi if z is negative real.
As well, |z|=sqrt(x^2+y^2).
