4 ms·

Seeing as we're in the integer world, I'm not sure logs need to show up ever, there's probably a proof path around unique prime factorisations. E.g. it's more o

by pdpi 4y ago

Seeing as we're in the integer world, I'm not sure logs need to show up ever, there's probably a proof path around unique prime factorisations. E.g. it's more or less immediately obvious that n and m would need to share the same prime factors in the same ratios.

justinpombrio 4y ago
Here goes. n^m = m^n, so n^m and m^n share the same prime factorization. Call it p1^x1 * ... * pk^xk. n = n^m^(1/m) = p1^(x1/m) * ... * pk^(xk/m) m = m^n^(1/n) = p1^(x1/n) * ... * pk^(xk/n) Therefore each xi is divisible by both n and m, so it's divisible by lcm(n, m). Call lcm(n, m) = d. Now define: z = p1^(x1/d) * ... * pk^(xk/d) Both n and m are powers of z! n = z^(d/m) m = z^(d/n) Call a=d/m and b=d/n. Then: n^m = (z^a)^(z^b) = z^(az^b) m^n = (z^b)^(z^a) = z^(bz^a) n^m = m^n -> z^(az^b) = z^(bz^a) -> az^b = bz^a EDIT: continuing proof. That's as far as I've got. Can someone run with it?
gjm11 4y ago
The key thing you need is that for n >= 3 the sequence of (n^1/n) is decreasing. You can get that pretty easily without logs. Look at two consecutive terms: n^(1/n) and (n+1)^[1/(n+1)]. The ratio of the first to the second -- we want to prove that this is >1 -- is n^(1/n) / (n+1)^[1/(n+1)]. This is bigger than 1 iff its n(n+1)th power is; that is, iff n^(n+1) / (n+1)^n > 1. We can write this as n (n/(n+1))^n; so what we need is that (n/(n+1))^n > 1/n. (Handwavily: we know that the LHS is about 1/e, so for n>=3 this should be good. But we want a proof and we're trying to do it without nontrivial analytic machinery.) Actually, I prefer to write this as ((n+1)/n)^n < n, or (1+1/n)^n < n. Expand this with the binomial theorem: we get sum {0<=k<=n} of (n choose k) n^-k. And we have (n choose k) = n(n-1)...(n-k+1) / k! < n^k/k! so this is strictly less than sum {0<=k<=n} of 1/k!. And for k>0 we easily have k! >= 2^(k-1) so this sum is no bigger than 1 + 1 + 1/2 + 1/4 + 1/8 + etc. = 3. So, the function on integers n -> n^1/n is decreasing for n >= 3. Now the proof goes through as before. (Maybe there's a more thoroughly number-theory-ish way to do it by looking at prime factorizations, but when I try it that way it always seems to end up rather a mess.) [EDITED to add:] But elsewhere in the discussion users bustermellotron and diffeomorphism give (very similar) neat number-theory-ish proofs, either of which is definitely a better proof than the one using the calculations above.
- bustermellotron 4y ago
  On the other hand, your proof really only needs the binomial theorem and geometric series.
actuallyalys 4y ago
This back-and-forth makes me wonder, is it possible to write proofs about proofs? e.g., you cannot prove this result without logarithms or there must exist a proof that involves prime factors? I suppose at least some proofs vaguely like that are possible because Gödel's incompleteness theorem is one, although I suspect that that same theorem puts some constraints on these "metaproofs."
- pdpi 4y ago
  Well, Proof Theory is a branch of maths in its own right, and Category Theory also has a definite "meta-proof-y" feel to it.
- westurner 4y ago
  Axiomatic system > Axiomatic method https://en.wikipedia.org/wiki/Axiomatic_system#Axiomatic_method https://en.wikipedia.org/wiki/Axiomatic_system#Axiomatic_met... Inference https://en.wikipedia.org/wiki/Inference https://en.wikipedia.org/wiki/Inference ; inductive, deductive, abductive Propositional calculus > Proofs in propositional calculus: https://en.wikipedia.org/wiki/Propositional_calculus https://en.wikipedia.org/wiki/Propositional_calculus Quantum logic: https://en.wikipedia.org/wiki/Quantum_logic https://en.wikipedia.org/wiki/Quantum_logic https://twitter.com/westurner/status/1609495237738496000 https://twitter.com/westurner/status/1609495237738496000 : > [ Is quantum logic the correct or a sufficient logic for propositional logic? ] What are quantum "expectation values"; and how is that Axiomatic wave operator system different from standard propositional calculus?
- dvt 4y ago
  > is it possible to write proofs about proofs Yep, I took several metamathematics classes at UCLA! Mostly on proof theory, but also analyzing metamathematical results (like Godel's theorems, Henkin construction, and so on).

by pdpi 4y ago

justinpombrio 4y ago

Here goes. n^m = m^n, so n^m and m^n share the same prime factorization. Call it p1^x1 * ... * pk^xk. n = n^m^(1/m) = p1^(x1/m) * ... * pk^(xk/m) m = m^n^(1/n) = p1^(x1/n) * ... * pk^(xk/n) Therefore each xi is divisible by both n and m, so it's divisible by lcm(n, m). Call lcm(n, m) = d. Now define: z = p1^(x1/d) * ... * pk^(xk/d) Both n and m are powers of z! n = z^(d/m) m = z^(d/n) Call a=d/m and b=d/n. Then: n^m = (z^a)^(z^b) = z^(az^b) m^n = (z^b)^(z^a) = z^(bz^a) n^m = m^n -> z^(az^b) = z^(bz^a) -> az^b = bz^a EDIT: continuing proof. That's as far as I've got. Can someone run with it?

gjm11 4y ago

The key thing you need is that for n >= 3 the sequence of (n^1/n) is decreasing. You can get that pretty easily without logs. Look at two consecutive terms: n^(1/n) and (n+1)^[1/(n+1)]. The ratio of the first to the second -- we want to prove that this is >1 -- is n^(1/n) / (n+1)^[1/(n+1)]. This is bigger than 1 iff its n(n+1)th power is; that is, iff n^(n+1) / (n+1)^n > 1. We can write this as n (n/(n+1))^n; so what we need is that (n/(n+1))^n > 1/n. (Handwavily: we know that the LHS is about 1/e, so for n>=3 this should be good. But we want a proof and we're trying to do it without nontrivial analytic machinery.) Actually, I prefer to write this as ((n+1)/n)^n < n, or (1+1/n)^n < n. Expand this with the binomial theorem: we get sum {0<=k<=n} of (n choose k) n^-k. And we have (n choose k) = n(n-1)...(n-k+1) / k! < n^k/k! so this is strictly less than sum {0<=k<=n} of 1/k!. And for k>0 we easily have k! >= 2^(k-1) so this sum is no bigger than 1 + 1 + 1/2 + 1/4 + 1/8 + etc. = 3. So, the function on integers n -> n^1/n is decreasing for n >= 3. Now the proof goes through as before. (Maybe there's a more thoroughly number-theory-ish way to do it by looking at prime factorizations, but when I try it that way it always seems to end up rather a mess.) [EDITED to add:] But elsewhere in the discussion users bustermellotron and diffeomorphism give (very similar) neat number-theory-ish proofs, either of which is definitely a better proof than the one using the calculations above.

bustermellotron 4y ago
On the other hand, your proof really only needs the binomial theorem and geometric series.

actuallyalys 4y ago

This back-and-forth makes me wonder, is it possible to write proofs about proofs? e.g., you cannot prove this result without logarithms or there must exist a proof that involves prime factors? I suppose at least some proofs vaguely like that are possible because Gödel's incompleteness theorem is one, although I suspect that that same theorem puts some constraints on these "metaproofs."

pdpi 4y ago
Well, Proof Theory is a branch of maths in its own right, and Category Theory also has a definite "meta-proof-y" feel to it.
westurner 4y ago
Axiomatic system > Axiomatic method https://en.wikipedia.org/wiki/Axiomatic_system#Axiomatic_method https://en.wikipedia.org/wiki/Axiomatic_system#Axiomatic_met... Inference https://en.wikipedia.org/wiki/Inference https://en.wikipedia.org/wiki/Inference ; inductive, deductive, abductive Propositional calculus > Proofs in propositional calculus: https://en.wikipedia.org/wiki/Propositional_calculus https://en.wikipedia.org/wiki/Propositional_calculus Quantum logic: https://en.wikipedia.org/wiki/Quantum_logic https://en.wikipedia.org/wiki/Quantum_logic https://twitter.com/westurner/status/1609495237738496000 https://twitter.com/westurner/status/1609495237738496000 : > [ Is quantum logic the correct or a sufficient logic for propositional logic? ] What are quantum "expectation values"; and how is that Axiomatic wave operator system different from standard propositional calculus?
dvt 4y ago
> is it possible to write proofs about proofs Yep, I took several metamathematics classes at UCLA! Mostly on proof theory, but also analyzing metamathematical results (like Godel's theorems, Henkin construction, and so on).