11
$\begingroup$

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.

  • 0
    No problem @Kate, glad to help!2012-12-21

3 Answers 3

5

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$.

  • 0
    Why does the line for $q=3$ look like it has more points in this graph than the line for $q=2$?2018-07-20
3

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.

  • 0
    @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.2012-12-21
1

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, 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.