Question

Is there some way to refine this divisor inequality?

Answer 1

\[\tau(a^n-1) \ge \tau(a-1)\tau(n)\]
I just found that while playing around, but I think it could probably be improved.

Answer 2

I found this while playing with stuff like this, in base \(5\) the number:

\[5^6-1 = 444444\]
So I realized I could factor this as:

\[4*1*111111=4*1001*111=4*10101*11\]
so we see \(\tau(6)\) comes in because 1, 11, 111, 1001, 10101, and 111111 are all divisors. Each of these can be combined with all the divisors of 4 which are 1, 2, and 4 so \(\tau(5-1)\) comes in that way.

Answer 3

.

Answer 4

what is \( \tau \) in this case?

Answer 5

Oh, also from the geometric series,

\[a^n-1=(a-1 )\sum_{k=0}^{n-1} a^k\]
So it's really not super surprising after all I guess.

\[\tau(a^n-1) = \tau\left((a-1 )\sum_{k=0}^{n-1} a^k\right) \ge \tau(a-1)\tau\left(\sum_{k=0}^{n-1} a^k\right) \ge \tau(a-1)\tau(n)\]
Might need to think about this, not sure if what I just wrote is 100% true.

Answer 6

@p0sitr0n it's the divisor counting function, it's pretty simple really. I'll give you some examples, it literally counts the number of divisors of a function and tells you.

\[\tau(3)=2\] because 1 and 3 are both of the numbers that divide 3.

\[\tau(6)=4\] because 1,2,3, and 6 are all the four numbers 6.

Answer 7

ah ok. Similar to Euler's totient function but for divisors I guess

Answer 8

also, you switched to base 5, does that work for any base, or only when you take \( a \) ?

Answer 9

Yeah it works in every base, it's probably simplest to see in base 10, for instance:

\[10^4-1= 9999\]

The reason it works is because you just have to think of a number 1 less than the base and put them in all the slots, 1+ that will carry over to create a power of that base. Sorta weird. The factoring bit is also strange but it works out too and is a little easier to see maybe if you write out terms of the geometric series.

Also good comment on the euler totient function, they're both pretty closely related because they're both multiplicative functions which means you can do this separation \(f(a*b)=f(a)*f(b)\) as long as \(\gcd(a,b)=1\). They can be related by something called the Dirichlet convolution which is like a fancy way of talking about identities of the Riemann zeta function.

Answer 10

.

Answer 11

Although not really related might as well share,
\(\varphi(n)\) is the euler totient function, \(\sigma(n)\) is the sum of divisors function, then they are related in this way:
\[(\varphi \star \tau)(n)=\sigma (n)\]

the star is the convolution which means:

\[\sigma(n) =\sum_{d|n} \varphi(d) \tau(\tfrac{n}{d})\]

As an example of what the hell this is:

\[\sigma(6)=\varphi(1)\tau(6)+\varphi(2)\tau(3)+\varphi(3)\tau(2)+\varphi(6)\tau(1)\]
\[(1+2+3+6) = 1*4+1*2+2*2+2*1\]
\[12=12\]
scary stuff lol

Answer 12

Yeah I've done a little of continuous convolutions with integrals but for numerical analysis lol

Answer 13

But that thing could be true, you should do it with induction on \( n \)

Answer 14

I know it's true cause it comes from a change of variables after multiplying two series together. The derivation of the Dirichlet convolution is the same as the derivation of the convolution for a Fourier transform or Laplace transform.

Answer 15

Here's a quick run down of how the proof goes, get a series like this: \[D(f;s)=\sum_{n=1}^\infty \frac{f(n)}{n^s}\]
Now if you get two of them and multiply them together, you'll get another series that is of the same form,
\[D(f;s)D(g;s)=D(h;s)\]
\[\sum_{n=1}^\infty\sum_{m=1}^\infty \frac{f(n)g(m)}{(nm)^s} = \sum_{k=1}^\infty \frac{g(k)}{k^s}\]
From here \(nm=k\) and then insert a bit of tricky algebra and you get:
\[g(k)=\sum_{n|k}^k f(n)g(\tfrac{k}{n})\]
and you're done.

Run through the same thing with any Laplace transform proof if you are having doubts or whatever it's gonna be the same sorta issues you might have with this will show up in that as well.

Answer 16

The multiplicative functions form an abelian group with this Dirichlet convolution by the way. Like super super weird.

Answer 17

\[\tau(\sum_{k=0}^{n-1} a^k ) \ge \tau(n) ?\]

Answer 18

Base 'a' makes it obvious
Wonder if there is another way to see this

Answer 19

Yeah that seems questionable to me too. I know we can factor it like this for instance:

\[\sum_{k=0}^{n-1}a^k = \left( \sum_{k=0}^{(n-1)/m}a^k\right)\left(\sum_{\ell=0}^{m-1} a^\ell \right)\]
if m divides n-1

Answer 20

Uhh proof of:
\[\sum_{p=0}^{n-1}a^p = \left( \sum_{k=0}^{(n-1)/m}a^k\right)\left(\sum_{\ell=0}^{m-1} a^\ell \right)\]

\[\left( \sum_{k=0}^{(n-1)/m}a^k\right)\left(\sum_{\ell=0}^{m-1} a^\ell \right)= \sum_{k=0}^{(n-1)/m}\sum_{\ell=0}^{m-1} a^{k+\ell }\]
substitute \(k+\ell =p\)
\[\sum_{k=0}^{(n-1)/m}\sum_{\ell=0}^{m-1} a^p =??? =\sum_{p=0}^{n-1}a^p\]
hehehe... Ok idk but like it looks like it should work out, like expanded out as an example:

\[(1+a+a^2+a^3)(1+a^4) \] \[= 1+a+a^2+a^3+a^{0+4}+a^{1+4}+a^{2+4}+a^{3+4}\]

Answer 21

Looks very nice!

Answer 22

We're looking at divisors of n-1 here
whereas earlier we have looked at divisors of n

Answer 23

I'm still trying to put all pieces together

Answer 24

Has a nice little recursion to it:

\[\tau(a^{n-1}-1) \ge \tau(a-1)\tau(n-1)\]
Similarly,
\[\tau(a^{b^{c-1}-1}-1) \ge \tau(a-1)\tau(b-1)\tau(c-1)\]
Interesting thing is the right hand side is completely symmetric so you can rearrange it kinda cute.

\[\tau(b^{c^{a-1}-1}-1) \ge \tau(a-1)\tau(b-1)\tau(c-1)\]

Answer 25

Yeah I think I realized I left something out. What I was thinking and what I wrote down is not the same thing, here this should work out now:

\[\sum_{p=0}^{n-1}a^p = \left( \sum_{k=0}^{(n-1)/m}a^k\right)\left(\sum_{\ell=0}^{m-1} a^{m\ell} \right)\]
if m divides n-1.

The thing I missed was the extra exponent \(m\ell\) in one of the sums.

Answer 26

To be fair I'm not sure if my correction is right either, but really I'm just sorta writing down exactly what happens in bases when you multiply and factor stuff apart like I've been doing. I'm sorta tired cause I need to change schedules, earlier when I was typing up some stuff I wrote like \(1+a^2+a^3\) and completely skipped \(a\), like seriously can't count right now lol

Answer 27

I see the idea. You're basically trying to put 0's in between 'a', in the second product

Answer 28

I sorta remembered something with that last thing though, cause Wildberger said you can't factor \(10^{10^{10^\cdots}}+23\) with a power tower of ten 10s there. This sorta recursive thing could at least put a lower bound on the number of factors which might be interesting.

Answer 29

In a disgusting turn of events I found something terrible.
When x,y, and z are all mutually relatively prime,
\[\tau\left((x+1)^{(y+1)^z-1}-1\right) \ge \tau(xyz)\]
Sorta neat although the relatively prime part is not necessary for the grossness I warned about. By using the binomial theorem on the top and then using the binomial theorem AGAIN we have:

\[(x+1)^{(y+1)^z-1}-1=\sum_{m=1}^{\sum_{n=1}^z \binom{z}{n}y^n} \binom{\sum_{n=1}^z \binom{z}{n}y^n}{m}x^m\]
Ahahaha...

Answer 30

:o

Answer 31

Youve made the right hand side cuter and left hand side turned a bit messy. I dont wana have another sleepless night. You should have some rest lol

Answer 32

More trash, if you look carefully you'll notice we can now factor out an x and y...
\[\tau\left((x+1)^{(y+1)^z-1}-1\right)=\tau \left(x\sum_{m=1}^{y\sum_{n=1}^z \binom{z}{n}y^{n-1}} \binom{y\sum_{n=1}^z \binom{z}{n}y^{n-1}}{m}x^{m-1} \right)\]

So it looks like that the x can be factored out if relatively prime, and we have:
\[\tau(x)\tau \left(\sum_{m=1}^{y\sum_{n=1}^z \binom{z}{n}y^{n-1}} \binom{y\sum_{n=1}^z \binom{z}{n}y^{n-1}}{m}x^{m-1} \right) \ge \tau(x)\tau(y)\tau(z)\]
Wel the real issue is that this thing can naturally be extended infinitely deep. It's sorta interesting but sorta not idk lol