I think the phi function should be even for n > 2 based on this article: https://en.wikipedia.org/wiki/Euler's_totient_function
The function is multiplicative so we only need to consider its value for prime powers but phi of a prime power, pn, is equal to pn-1(p - 1). The p - 1 makes it even for odd prime p.
Good. I hadn't seen yet that its being a multiplicative function allowed us to ignore all but prime powers, though I usually suspect something like that in similar situations. We could just break it down as a bijection between *Z/pq and *Z/p x *Z/q, I suppose. Does a bijection make it both homomorphic and isomorphic?
Last edited by desiresjab; 12-15-2016 at 04:35 PM.
The bijection https://en.wikipedia.org/wiki/Bijection is a one-to-one and onto mapping between the elements of two sets. One can use a bijection to show that the two sets have the same number of elements. The only requirement is that the elements be all used once and only once between the two sets.
If one talks about various homomorphisms https://en.wikipedia.org/wiki/Homomorphism then there is an algebraic structure that the map preserves when the elements are mapped from one set to the other. That is, not any mapping between the elements of the two sets will do.
Trying to get my morhisms straight. The character of isomorphisms seems to change a liitle from field to field, and homomorhisms are not the same thing as homeomorhisms.Originally Posted by YesNo
But the precise meanings of bijections, injections and surjections are super stable, from what I can tell. Finite rings, a familiar stomping ground, are surjective, bijective and injective at the same time. Who could forget that? So that matter is settled as far as finite rings are concerned.
I am looking around for something to look at. I may investigate that phi function phenomenon and see if I can find any rule to how fast an argument under iteration of the function devolves to a pure power of 2. Hopefully, the reason will be easy to spot, or it could turn into a prolonged investigation. That is not so bad either. There are always connections to be spotted between these major functions.
As I see it, homeomorphisms preserve closeness rather than an algebraic structure: https://en.wikipedia.org/wiki/Homeomorphism
I suspect if one has a bijective homomorphism or a bijective homeomorphism then the inverse mapping exists. Not only is the algebra or topological structure preserved but also the number of elements involved. One should be able to go backwards having that. It has been a while since I thought about these ideas. I imagine most mappings that don't preserve anything between the two sets.
Earlier this year I went through an abstract algebra course on YouTube. I did it crazy fast--like thirty-eight lectures in three or four days. I was only able to retain some parts, but it was a good introduction to the language. They never did give a proof of quadratric reciprocity though they were hitting all around it. It amazrd me that complicated proofs and other undertakings were dealt with in a few sweeps of the chalk in that language. I guess this is because so much information is already contained and assumed in the forms they are using. One knows the engine from looking at the schematic of it rather than getting one's hands greasy down among the gears, was my impression of abstract algebra. I will probably slip in some of the language now and then. Mainly, as you know, I like greasy hands in mathematics. The reason abstract mathematics exists is because the smartest people were no longer able to see through the gears and wires of the engine to work on what had to be worked on. They knew there was structure there. If they couldn't, then I cannot either, but I am trying to be sure of where they stopped even as I try to learn the higher ways of schematics--bijections and isomorphisms et al. I want to have the same relationship with numbers they had before they made the transfer. For instance, Ramanujan took a good look at Brocard's problem. What did he see that made him decide he could not solve this one? None of us will ever see what Ramanujan saw, but we might somehow reach the same conclusion for a similar reason.
The only person I believe to have had as much talent for numbers is Gauss, who had the formal training such a mind needs from an early age. It seems reasonable to assume that Ramanujan might have changed the world of mathematics as vastly as Gauss did, had he been born under more propitious circumstances that afforded him an early start under expert guidance. These minds only require nudging in the right direction here and there. Euler began his higher education in mathematics at about thirteen when he went to study with the Bernoullis. One cannot say Gauss would have contributed more had he been given the opportunity to study with somone of Bernoulli caliber earlier on. The people instructing Gauss in his primary years were merely good not great, from all accounts. The duke of Brunswick had taken note of the young prodigy and made sure he was in a place of learning. There was a student or student-teacher six or seven years Gauss's senior interested in mathematics that the prodigy consorted with. This was perfectly enough. One can be quite assured that Gauss was equipped to solve any problem any mathematician up to his to his time and fifty years beyond ever solved, even those that were solved during his liftetime by others who were also great matheticians. What Abel and Galois did in proving there was no general method for solving equations of 5th degree and beyond, was a discovery for the ages, and it happened during Gauss's prime. Why didn't Gauss make that discovery?
One has only to look at how full the plate of Gauss was, at what he got done, to forgive him for leaving this major discovery out of his fireplace mantle collection. He was busy at that precise moment calculating in his head the orbit of Ceres from a few degrees of arc he had been given. It was an open problem in the world of mathematics, and one that had to be solved fast. Many were scurrying to calculate an orbit so the discovery of a new planetoid would not be lost. Luckily, there was already a computer in the world in 1822. When the time came only one set of calculations was correct. Ceres remergred from behind the sun where and when Gauss said it would. This was not the first time he had amazed the world, but this cemented his reputation for all time. While he was calculating the orbit in his head hre invented a new tool to assist him that we now call the Method of Least Squares. This is a tool now in universal use. Even Gauss could only work on so many things at a time. Few but Ripe, was his motto, remember. It is not true that he worked on only a few problems, but it is true that he brought most of them to ripeness that he did engage with. His mind was perhaps not superior to that of Euler but his method was cleaner and superior, I believe. Euler chopped down more individual trees than anyone. Gauss cleared forests and usually built a ranch on the spot. Euler did not build nearly as many ranches. That, I believe, is why Gauss is regarded a little higher, not only by myselgf but by mathematicians in general. None of this to detract from the legacy of Euler, who is one of my idols, but merely to point out that the talent of Gauss has probably not been seen in the world again except for perhaps Ramanujan, who had a pitiful start yet still made mighty contributions.
Euler was able to calculate to fifty decimal places in his head when he needed to. Gauss's solution was different--he simply memorized a book of logarithm tables in a day or two and the problem was taken care of. Now he could hold up for examination in his head any logarithms he wished to compare, and when he needed a logarithm it was right there at his disposal.
It is obvious I am too spent to discuss math right now, or I would be writing math instead of writing about mathematicans. It is good recreation. I will try again later to look at math.
I have a hard time remembering five digits of pi. Memorizing a table of logarithms is probably out of the question for me. I have heard of people with synaesthesia who can see numbers as colors or shapes.
That guy from England, Daniel Tamet (not sure of spelling) has that synesthetic power, we might as well call it. Damage or deformation of the copus callosum which may have repaired itself the best way it could, seems to have something to do with the function of seeing numbers as colored shapes or smelling the notes of a flute concerto like a flower show.
I do not know if any synesthete ever turned his or her dysfunction into a mighty contribution in any of the arts or sciences. Interesting question. In which field would success be most likely? I suppose there are different degrees of the dysfunction, from light to full blown. Tesla might be candidate. Not sure. In the old days this ability is something that geniuses might have very intelligently hidden, for fear of being chained to a post while hags ran for kindling. Goethe had an unusual mind that grasped science differently than the standard model of the time. Could he have been one?
They might have all been synaesthetic, but that may not be the correct word for it. Intuitive might be better. Or they were able to communicate better with their goddesses. Synaesthesia may be labelled a dysfunction but it appears to be just not normal functioning. I don't know if there is any brain correlates for it nor if there is anything wrong with it.
That is why I italicized dysfunction.
Just for fun, and to do for factorials what is done for powers, consider the list below.
1!-0!=0
2!-1!=1
3!-2!=4
4!-3!=18
5!-4!=96
6!-5!=600
The recursive formula for a division of two consecutive factorials would be n!=(n+1)!/n+1. Very easy.
A formula for a subtaction of two consecutive factorials n!-(n-1)!, must look like this:
n!-n!/n, and after manipulation like
n!(n-1)/n= (n-1)(n-1)!=
n!-(n-1)!=(n-1)2(n-2)!. We also like the following from above because it is a factorial times a simple ratio, fast to work and succinct:
n!(n-1)/n.
* * * * *
To respond to my own question about why repeated iteration of the φ function on a number eventually reduces to a pure power of 2 before it has to by virtue of merely being even, after staring long at the Wiki-peja article on the function, one finds this statement, which not only proves that it does happen but shows why and when as well, if one contemplates:
φ(n) is even for n>2. Moreover, if n has r distinct odd prime factors, then 2r|φ(n). The vertical bar means “divides.”
* * * * *
Of the unsloved problems involving the φ function, Lehmer's conjecture looks captivating.
Last edited by desiresjab; 12-17-2016 at 01:23 PM.
Lehmer's totient problem sounds interesting. It is the first I heard of it: https://en.wikipedia.org/wiki/Lehmer's_totient_problem I would be happy to understand how someone got as far as they did with that conjecture.
I think it makes sense that if there are r distinct odd composite primes dividing n then 2r divides the totient of n. More factors of 2 than r may divide it as well. I don't know what it means for a number to eventually reduce to a pure power of 2 before it has to by virtue of merely being even. One would have to find a measure for that concept, but one might exist.
Regard Lehmer's conjecture, I can see why any such n so that φ(n) | n - 1 must be a Carmichael number. The order of any prime p dividing n would divide φ(n) and so divide n - 1 implying that p[sup]n-1[\sup] = 1 (mod n): http://mathworld.wolfram.com/LehmersTotientProblem.html
What about the other results?
(1) Why must it be square-free? (Edit: I can see why it must be square-free. If pr divides n then pr-1(p-1) divides n - 1. So p divides both n and n - 1 if r > 1. That implies p divides 1. So it must be square-free.)
(2) Why must it have at least 7 (or 11 or 14) distinct primes dividing it?
(3) Why must it be greater than 1023?
(4) Why must it be odd? (Edit: I can see why it must be odd. If n were even then n - 1 is odd. By assumption φ(n) | n - 1, but φ(n) is even for n > 2. Considering the two cases for n <= 2: For n = 2, n is prime and since the conjecture only applies to composite n, n = 2 does not count. Since 1 is not a composite number either, n = 1 is not covered by the conjecture either.)
Here's another reference: http://math.stackexchange.com/questi...otient-problem
(5) Why are there no counterexamples of the form k2k + 1 (Here's the paper: http://citeseerx.ist.psu.edu/viewdoc...=rep1&type=pdf)
(6) Why are there no Fibonacci numbers as counterexamples?
(7) Is the following solution to the problem correct or not? https://www.youtube.com/watch?v=swbZqPjrcGk (Edit: This doesn't convince me. We can skip the powers of b since we know n must be square-free. So let composite n = bC where b is prime then if φ(n) = n - 1, we have φ(bC) = φ(b)φ(C) = n - 1 = bC - 1. So φ(C) = (bC - 1)/(b - 1). I don't see why that could not reduce to an integer. It would be an integer if C = 1 (more generally C = bk), but then n would be prime or not be square-free.)
Last edited by YesNo; 12-17-2016 at 07:33 PM.
The more I am thinking of William Bouris' proof that Lehman numbers do not exist, the more I think there might be something to it. The basic idea is that φ(C) = (bC - 1)/(b - 1) cannot be an integer unless C = bk for some integer k which would imply that n is prime or n is not square-free. If that can be shown then there are no composite n = bC with b prime. That would be the same as saying bC is not congruent to 1 mod (b - 1). At any rate, this would be another way to look for a counterexample if one actually existed.
Since I saw that all numbers did eventually reduce to a power of 2, the iterated function must necessarily reach a power of 2 merely by virtue of the function always being even. Why? There is no escape for the iterated φ function. We already know certain facts, do we not?
φ(φ(18))=2
φ(17)=16
φ(16)=8
φ(15)=8
φ(φ(13))=4
φ(12) above
φ(φ(11))=4
φ(10) above
φ(φ(9))=2
φ(8)=4
φ(φ(7))=2
φ(6) above
φ(5)=4, etc.
We already know these values and more for small values. A number descending from above in a function doomed always to spit back as output an even result, and whose last value is known to be 1, must eventually come to rest at 2, since that is the only argument for which the function will output 1. So it is quite forced for that reason, if for no other, and it turns out there is another reason, which returns pure powers of 2 as function values long before the hand of the function is forced to produce a power of 2 simply because its next value must be even.
Posting Permissions
Reply With Quote