Question

Establish below for any prime \(p\) \[\tau(p!) = 2\tau((p-1)!)\\~\\\sigma(p!) =
(p+1)\sigma((p-1)!)\\~\\\phi(p!)=(p-1)\phi((p-1)!)\]

Answer 1

Since these are all multiplicative functions and we know p is prime means it's relatively prime to all numbers less than it\[\Large GCD( p , (p-1)!) = 1\] we can separate it out since we know \[\Large \tau(p)=2 \\ \Large \sigma(p)=p+1\\ \Large \phi(p)=p-1\] There we have it. =P That was pretty fun.

Answer 2

Thats it!

Answer 3

Are there more functions like these? They are pretty interesting. So here's a modified version using the primorial, can we evaluate these?\[\Large \tau(p_n \#) \\ \Large \sigma ( p_n\#) \\ \Large \phi(p_n \#)\]

Answer 4

Interesting, do we get
\[\tau(p_n \#) = 2^n\]

?

Answer 5

Yeah, that's what I'm getting. But the other two I don't think evaluate so nicely. But if you expand them as polynomials I guess that's as close as you can get.

Answer 6

In my laziness to express both at once lol\[\Large \sigma/\phi (p_n\#) = \prod_{i=1}^n (p_i \pm 1)\]

Answer 7

lol we should enforce the readers to interpret it as sigma "OR" phi

Answer 8

Another function with many interesting properties is Liouville \(\lambda \)-function
http://en.wikipedia.org/wiki/Liouville_function

this is multiplicative too

Answer 9

If we want to think back to that stuff I said about the modified arithmetic derivative: \[\large \sigma(p_n \#) = \sum_{i=0}^{n} (p_i \#)^{[i]}=p_n \#+ (p_n \#)' + (p_n \#)''+ \cdots\]

Answer 10

To be less abstract and to remember real quick before I start looking into the Liouville function, \[\Large p_2 \# = p_1p_2 =2*3 \\ \Large \sigma(6)=(2+1)(3+1)= \\ \Large (2*3)+(2+3)+1 = \\ \Large (p_1p_2)+(p_1p_2)'+(p_1p_2)''\]

So what's the Liouville function used for, I see it's connected to the Omega function for counting the prime factors in the exponents... Kind of interesting I think we can make any additive function by using a multiplicative function as an exponent which is really cool!

Answer 11

wait I said that wrong... we can always make a multiplicative function out of an additive function if we use it as an exponent. But I guess maybe we can reverse that somehow if we take multiplicative functions and do logarithm stuff with them maybe? I'm still reading the Liouville article but it is involved in a lot of interesting things like the Riemann zeta function? Also what's this mean

"The Liouville function's Dirichlet inverse is the absolute value of the Möbius function."

Answer 12

I forgot, Mobius function is "the" most important function of all. Look it up first

Answer 13

I am trying to recall that sum of divisors of primorial and arithmetic derivatives

Answer 14

Well the way I wrote it is the version I sorta came up with wio and you messing around on here, so it's slightly different but what it does is each derivative takes every possible combination of that may numbers and makes them =1 and adds all of them up. It doesn't necessarily have to be for primes, but here's an example: \[\Large n= p*q*r \\ \Large n' = qr+pr+pq \\ \Large n'' = r+q+p \\ \Large n'''=1 \\ \Large n'''' = 0\]

so for example n''=p+q+r because we can pick three possible ways to pick two, pq, pr, and qr and those all become 1.

Also, if for instance we don't know n=pqr and we just know n=a*r we can still do derivatives: \[\Large n'' = (ar)'' = a''r+a'r'+ar'' \\ \Large a''r + a'1+a0 \\ \Large n'' = a''r+a'\] Of course we can plug in a=pq into this later if we find it somehow. \[\Large a = pq \\ \Large a' = p+q \\ \Large a'' = 1\] Then plug it in\[\Large n'' = (1)r +(p+q) = p+q+r\] Just to sort of remind you some of how it works.

Answer 15

Woah so are there like "cube free" versions of the mobius function? The fact that the Mobius function is multiplicative is already a good sign, interesting.

Answer 16

I think square free integers are interesting because they are a product of distinct single prime factors. This is the reason they show up in areas like pseudo primes and in many other identities... Here I am restating that number of divisors of primorial which we messed with earlier in terms of square-free numbers

If \(n\) is square free integer then \(\tau(n) = 2^k\), where \(k\) is the number of primes in the factorization of \(n\)

I am not sure if we can find any cool properties of "cube free" numbers hmm

Answer 17

Playing around a little for integer n>0\[\Large \mu(p_{2n} \#) = 1 \\ \Large \mu(p_{2n-1} \#) = -1\]

Answer 18

some properties/results related to square-free integers that i can recall :

1) every absolute pseudo prime is square free
2) the mother of all number theoretic functions : mobius function is defined based on square free integers
3) All known Fermat numbers are square free
...

Answer 19

Yeah I guess primorials are really just a special case of square free integers where the primes are consecutive.

Answer 20

Hmm interesting, I guess I should be thinking about square free integers more then

Answer 21

Haha with primorials you're doing that already i guess

also nobody knows if there exists a mersenne primes thats not square free

Answer 22

A fun thing I'm thinking of is every square free integer can be written as a product of decreasing and constantly inverted fraction primorials... Maybe I should just write it: \[\Large n = p_{a_i} \# \cdot \frac{1}{p_{a_{i-1}}\# } \cdot p_{a_{i-2}}\# \cdot \frac{1}{p_{a_{i-3}}\# } \cdots \] So for example, if we look at 65=5*13 we can write it as \[\Large 65 = 13 \# \frac{1}{11 \#}5 \# \frac{1}{3\#}\] which is super clunky and weird, but kind of amusing to me I guess haha.

Answer 23

Neat :) Here is the main reason for mobius function to become famous


If \[f(n) = \sum\limits_{d|n}g(d)\]

then we can obtain the function \(g\) by :

\[g(n) =\sum\limits_{d|n}\mu(d) f(n/d) \]

This is called mobius inverse

Answer 24

Something about the fact that 2^3 comes before 3^2 makes me really interested in what you've just said about mersenne numbers and square free hmmm...

Answer 25

Woah can you show me an example of using that, and how does someone find that out?

Answer 26

Lets work an example when \(f(n) = \tau(n)\) :

We know that \[\tau(n) = \sum\limits_{d|n}1\]

take mobius inverse and see if we get back \(1\)

Answer 27

simply apply the inverse formula for now, we can work the proof after seeing few examples maybe

Answer 28

Ok give me a sec.

Answer 29

In above example, \(f(n)=\tau(n)\) and \(g(n) = 1\)

Answer 30

I'm not sure how to go about doing this but if say n has 2 prime factors I can write this out: \[\Large \mu(1)\tau(pq)+\mu(p)\tau(q)+\mu(q)\tau(p)+\mu(pq)\tau(1) = \\ \Large 4-2-2+1 = 1\] I'm kind of thinking I could generalize this further to prove it but not sure.

Answer 31

that looks good
\(\large \sum\limits_{d|n}\mu(d)\tau(n/d)=1\)

Answer 32

I can also see that \[n=p^2 \\ 1*3-2+0=1\] It's interesting

Answer 33

Right the function obtained by taking mobius inverse is also multiplicative if the original function is multiplicative

Answer 34

Another example :
prove below by using mobius inverse
\[\sum\limits_{d|n}\mu(d)\sigma(n/d)= n\]

Answer 35

Oh I just had a bit of insight ok give me a moment to think about this. I can see that I can immediately throw away all the terms that are square divisors.

Answer 36

I can't really see how to prove this. I guess in my mind I can kind of see it telescoping away the other factors of n leaving just n behind, but not really sure how to show that.

Answer 37

\(\sigma(n) = \sum\limits_{d|n}d\)

taking mobius inverse give that earlier result

Answer 38

we have touched many interesting functions but forgot about the most familiar one

Answer 39

Ohhh I see you just reversed how you used it, I was thinking of how to prove the moebius inversion, but I see what you're doing now

Answer 40

floor function is kinda neat too :

For ANY function \(f\) we have

\[\sum_{n=1}^N\sum_{d|n}f(d) =\sum_{n=1}^N f(n) \left\lfloor \frac{N}{n}\right\rfloor \]

Answer 41

it has to be discussed when talking about important functions ;p

Answer 42

I see I see. This is really powerful and unexpected. I'm not even sure what to do with this yet it's like too good haha

Answer 43

Here is a neat result I have finished working on just now
http://math.stackexchange.com/questions/1190722/sum-n-1n-lambdann-n-sqrtn-identity-involving-liouville-lambda-fun/1190738#1190738

Answer 44

that link has a proof of an identity tat relates louville, mobius and flor functions

Answer 45

This is quite a lot for me to take in, I feel completely lost. How can we prove the Moebius Inversion? I think that will help

Answer 46

Sorry *Dirichlet Inverse

Answer 47

proof is kinda easy, i never found it that interesting compared to its applications, lets try and prove it quick

Answer 48

From reading the article I can see how this is a convolution since each function within it will go over the same values. So that's kind of a relief to me. I think these applications are amazing though, I just can't really see how anyone would have thought this up haha.

Answer 49

This is true correct? \[\large \sum_{d|n} f(d) g(\frac{n}{d}) = \sum_{d|n}g(d)f(\frac{n}{d}) \]

Answer 50

Yes as \(d\) runs over all the divisors of \(n\), we get the same overall sum.

Answer 51

Interesting, I was just playing around with \[\Large \sum_{d|n} \mu(d)\mu(\frac{n}{d}) = g(n)\] but I can't seem find out what g(n) is, other than it is a function that basically forms an identity for the mobius function. \[\Large \mu(n)=\sum_{d|n} g(d)\]