Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If you look the at the wikipedia page for the Euler totient function there is a graph of the Euler phi function up to 1000: enter image description here

Out of the plot you can see various trend lines that appear to be linear.

Q1) Are these lines actually lines? (ie do all the points that appear to be on one line actually all solutions to some linear eqn?)

Q2) Given that they're lines and not just something that looks a bit like lines can they be described? and what points are on them?

Q3) Are the points that don't appear to be on lines actually just the first points on lines that would only be 'visible' if we zoomed out and evaluated the Euler phi up to (say) 10000 or whatever number is large enough.

share|improve this question
    
thanks to Zev for including the plot! –  Kate Signos Dec 21 '12 at 15:04
    
No problem @Kate, glad to help! –  Zev Chonoles Dec 21 '12 at 15:14
add comment

3 Answers

In the following $\mathbb{P}$ denotes the set of primes and $p\in\mathbb{P}$ a prime.

We know $\phi(p)=p-1$, so that $\{(p,p-1):p\in\mathbb{P}\}$ is contained in the graph of $\phi$. This set lies on the line $y=x-1$, and corresponds to the steepest line in the graph.

Fix $q\in\mathbb{N}$. Then $\phi(q\cdot p)=\phi(q)(p-1)$ if $p\not\mid q$. The set of points $\{(q\cdot p,\phi(q)(p-1)):p\not\mid q\}$ is contained in the graph of $\phi$ and lies on the line $$y=\phi(q)\Bigl(\frac{x}{q}-1\Bigr).$$ The other lines you see correspond to $q=2$, $3$ and $4$.

share|improve this answer
    
They don't lie on the line $y=\phi(q)(x-1)$ (which would most often be above the line $y=x-1$), because one has $x=qp$, not $x=p$. Also the lines for $q=2$ and $q=4$ coincide. –  Marc van Leeuwen Dec 21 '12 at 15:08
    
@MarcvanLeeuwen Thank you for your observation. I have edited my answer. –  Julián Aguirre Dec 21 '12 at 15:11
    
But it is still not correct. Please read my answer; the lines (other than the topmost one) are not straight. –  Marc van Leeuwen Dec 21 '12 at 15:11
    
@MarcvanLeeuwen I think I got it right this time. –  Julián Aguirre Dec 21 '12 at 15:21
add comment

Some of the "dotted lines" that you're looking at are actually points from lines close to each other, but yes there are some lines.

Most obviously, the upper bound is the line $y=x-1$, which is hit by all the primes.

Going along that same line of thought, think of $\phi(3p)$ for primes $p$ other than $3$. You can compute that $\phi(3p)=2\phi(p)$. This says that if you went and plotted all the values $3p$ for primes other than $3$, you would get the dotted line of points $(3p, 2\phi(p))$ lying on the line $y=2(\frac{x}{3}-1)$.

I'm not sure this can be developed into a complete answer about lines, but it certainly seems to paint a picture for the $n$ which are divisible by a prime $q$ but not by $q^2$. I would suspect that numbers which do not have prime factors with multiplicity 1 are the "stray" points.

share|improve this answer
    
I find $y=2\phi(p)$ hard to decipher as equation for a line, given that this is the plot $y=\phi(x)$. Is this supposed to describe a straight line, and if so could you express in in terms of $x$ and $y$? –  Marc van Leeuwen Dec 21 '12 at 15:18
    
@MarcvanLeeuwen I think that's the way I want the second line. Let me know if there is something I bungled. It looks(?) like one dotted line is a linear transformation of the other. –  rschwieb Dec 21 '12 at 15:31
add comment

Since $\frac{\phi(n)}n=\prod_{p\mid n}\frac{p-1}p$, where the product is over all distinct prime factors, the lines are almost through the origin and mostly exhibit the distribution of distinct small prime factors in $n$, where the eye does not distinguish the differences between the factor $\frac{p-1}p$ for the largest prime factor, which is usually different between the values of $n$ on the same "line".

So the topmost line is for the prime numbers themselves, where $\phi(n)=n-1$, is a straight line almost through the origin; the "halfway" line is for numbers $n=2^kp^l$ (for some relatively large prime $p$); it is almost equal to the line through the origin with slope $\frac12$. In fact it is an almost straight line $\phi(n)=\frac n2-\frac n{2p}$ that holds for such numbers, with downards dents when the final factor $p$ is not so very large. Other "lines" can be explained similarly, but are less and less marked. And none of these lines are straight; if you look carefully there are points that tend to "droop".

Added: in fact one can explain these non-straight lines also as a union of several (in principle infinitely many) very close straight lines and lots of other points nearby. For instance the "line" for values $n=2^kp^l$ can be split into one for $n=2p$, where $\phi(n)=(p-1)=\frac n2-1$, one for $n=4p$, where $\phi(n)=2(p-1)=\frac n2-2$, ..., one for $n=2^kp$ where $\phi(n)=2^{k-1}(p-1)=\frac n2-2^{k-1}$ (which is still relatively close to $y=\frac n2$ when $p$ is very large), and other with higher powers of $p$, for instance $n=2p^2$ given $\phi(n)=p(p-1)=\frac n2-\sqrt{\frac n2}$ which is not a straight line but still relatively close to the line $y=\frac n2$. Indeed even other points would contribute visually to a clustering around (or more precisely just below) the line $y=\frac n2$: when $m=2pq$ is twice a product of two large primes $p<q$, then $\phi(m)=(p-1)(q-1)$ is less than $2q=\frac mp$ away from that line. The same occurs by the way just below the line $y=x-1$ containing $(p,\phi(p))$ for any prime $p$: any number that only has few and very large prime factors will produce a point just below that line.

In the given graph I can only distinguish four lines clearly: the top one with slope $1$ for the prime numbers, the line with slope $\frac12$ for the numbers with only $2$ as small prime factor, the line with slope $\frac23$ for the numbers with only $3$ as small prime factor, and the line with slope $\frac13$ for the numbers with only $2$ and $3$ as small prime factors. Knowing the phenomenon one can discern lines with slopes $\frac45$ and $\frac67$, but already these don't stand out very clearly.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.