0
$\begingroup$

The final point $(9)$ is the lemma that I am establishing a proof for, all the relevant lemma are there I guess I just need help fine tuning things, Although I have no idea how I will prove $(10)$ if indeed it is true for all primes.

Consider the Unique prime factorization of a natural number $n$:

$$n=\prod _{j=1}^{\omega \left( n \right) }{p_{{n,j}}}^{\nu_{{n,j}}}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(0)$$

One could, in a heuristic sense, expect that the sum of all sums up to and including the multiplicity of all the distinct prime factors of $n$ will have proportion to the total number of divisors of $n$ somehow.

So we begin by defining the sum of the multiplicities of the unique prime factors of $n$:

$$\Upsilon \left( n \right) =\sum _{j=1}^{\omega \left( n \right) }\nu_{ {n,j}} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(1)$$

$$\sum _{k=1}^{\Upsilon \left( n \right) +1}{\frac { \left( \Upsilon \left( n \right) +1 \right) !}{k!\, \left( \Upsilon \left( n \right) -k+1 \right) !}}=2^{\Upsilon \left( n \right) +1}-1 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(2)$$

$${\Biggl\{\frac {{2}^{n} \left( {2}^{\Upsilon \left( n \right) +1}-1+{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1}-1,\tau \left( n \right) \right) \right) }{{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\}=0\quad\quad\quad\quad\quad\quad\quad\quad\quad(3)$$

$${\Biggl\{\frac {\tau(n)\left( {2}^{\Upsilon \left( n \right) +1}-1+{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1}-1,\tau \left( n \right) \right) \right) }{2{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\}=0\quad\quad\quad\quad\quad\quad(4)$$

$${\Biggl\{\frac {{2}^{n} }{{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\}=0\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(5)$$

$${\Biggl\{\frac {\tau(n)\left( {2}^{\Upsilon \left( n \right) +1}-1 \right) }{2{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\}=\frac{1}{2}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(6)$$

$$\exists k \in \mathbb N \land k \gt 1\quad \operatorname{s.t} \sqrt{n}=k \Rightarrow \quad{\Biggl\{\frac {\tau(n)\left({\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) \right) }{2{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1}-1,\tau \left( n \right) \right) }} \Biggr\}=\frac{1}{2}\quad\quad\quad(7)$$

$$\not\exists k \in \mathbb N \land k \gt 1 \quad\operatorname{s.t} \sqrt{n}=k \Rightarrow \quad{\Biggl\{\frac {\tau(n)\left({\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) \right) }{2{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1}-1,\tau \left( n \right) \right) }} \Biggr\}=0\quad\quad\quad(8)$$

$$\exists k \in \mathbb N \land k \gt 1 \quad\operatorname{s.t} \sqrt{n}=k \Rightarrow{\Biggl\{\frac{{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right)}{2}}\Biggr\}=\frac{1}{2}\quad\quad\quad(7\operatorname{i})$$

$$\not\exists k \in \mathbb N \land k \gt 1\quad \operatorname{s.t} \sqrt{n}=k \Rightarrow{\Biggl\{\frac{{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right)}{2}}\Biggr\}=0\quad\quad\quad(8\operatorname{i})$$

Where ${\{x}\}$ is the fractional part of $x$.

Where $\tau(n)$ is the total number of divisors of $x$.

The 2-adic valuation of the total number of divisors of $n$ can also be expressed in term of the sum of the multiplicities of the unique prime factors of $n$:

$$\nu_{{2}} \left( \tau(n) \right)=\frac{\ln(\gcd(2^{\Upsilon \left( n \right)+1},\tau(n)))}{\ln(2)}\quad\quad\quad(9)$$

The generalization to the p-adic valuation of the total number of divisors of $n$ also seems to be true: $$\nu_{{p}} \left( \tau(n) \right)=\frac{\ln(\gcd(p^{\Upsilon \left( n \right)+1},\tau(n)))}{\ln(p)}\quad\quad\quad(10)$$

Indeed, the following generalizations to any $p$ would appear to be true , giving more substance to the truth value of $(10)$,I am too tired to use my talking words tbh:

$${\Biggl\{\frac {\tau(n)\left( {p}^{\Upsilon \left( n \right) +1}-1+{\it \gcd} \left( {p}^{\Upsilon \left( n \right) +1}-1,\tau \left( n \right) \right) \right) }{{\it \gcd} \left( {p}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\}=0\quad\quad\quad\quad\quad\quad(4\operatorname{i})$$

$${\Biggl\{\frac {{p}^{n} }{{\it \gcd} \left( {p}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\}=0\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(5\operatorname{i})$$

$${\Biggl\{\frac {{\it \gcd} \left( {p}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }{{p}^{\Upsilon \left( n \right)-n+1} }} \Biggr\}=0\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(5\operatorname{ii})$$

$$1 \leq {\frac {\tau(n)\left( {p}^{\Upsilon \left( n \right) +1}-1 \right) }{\gcd\left( {p}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }}-p\Biggl\lfloor {\frac {\tau(n)\left( {p}^{\Upsilon \left( n \right) +1}-1 \right) }{p\gcd\left( {p}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\rfloor \leq p-1\quad\quad\quad\quad\quad\quad(11)$$

$\endgroup$
  • $\begingroup$ What you have in mind is unclear, if $n$ is squarefree it simplifies a lot since $\tau(n) = 2^{\omega(n)}$ $\endgroup$ – reuns Sep 30 '18 at 23:36
  • $\begingroup$ In the case that $n$ is square free yes we have $\Upsilon \left( n \right)=\omega(n)$ you are correct, but I don't understand what you are referring to when you say "it" simplifies, seeing that the relation I have posted the discussion about is for the p-adic valuation for $\tau(n)$, which is obviously going to be equal to $1$ for all $p$ that divide $\tau(n)$ and $0$ for those that don't in the case that $n$ is square free $\endgroup$ – Adam Sep 30 '18 at 23:56
  • $\begingroup$ Well yes the sum of the multiplicities of the unique prime factors of a number is going to be greater than or equal to the p-adic valuation for any particular prime number, but the fact that this is the total number of divisors I think requires more than that. Also, a divisibility relation cannot be simply justified with an inequality in my opinion, but I'm also not entirely sure of what else I want as proof over and above it $\endgroup$ – Adam Oct 1 '18 at 0:28
  • $\begingroup$ I think the inequality $(11)$ that I just included into the post now is probably the most important part that needs rigorous proof at this point $\endgroup$ – Adam Oct 1 '18 at 0:39
1
$\begingroup$

Summing up my comments and filling in some gaps:

To show (10) (which includes (9) as a special case):

For any prime $p$ and integer $x$, by definition of the $p$-adic value, we have $\nu_p(x)=\log_p(\gcd(p^r,x))$ if and only if $r$ is an integer $\ge \nu_p(x)$. So equation (10) boils down to the claim that $$\Upsilon(n)+1≥\nu_p(\tau(n))$$ for all $p$ and $n$.

Now to see this, use that $\displaystyle \tau(n) = \prod_{j=1}^{\omega(n)} (\nu_{n,j}+1)$ (according to wikipedia, where $\tau$ is called $\sigma_0$). So for any $p$,

$$\nu_p(\tau(n)) = \sum_{j=1}^{\omega(n)} \nu_p(\nu_{n,j}+1)$$

Now for any integer $a$ and prime $p$, we have $\nu_p(a) \le a-1$, hence we even have the stronger

$$\nu_p(\tau(n)) \le \sum_{j=1}^{\omega(n)} \nu_{n,j} =\Upsilon(n).$$

To show (11):

Calling $x=$ the first fraction in (11), and looking at the function $f(x)=x−p \lfloor x/p\rfloor$, shows that (11) is equivalent to $x$ not being within any of the intervals $(kp−1,kp+1)$ with $k \in \Bbb Z$. Since the denominator of $x$ divides $\tau(n)$, the fraction $x$ is actually an integer itself, so the claim is equivalent to $x$ not being of the form $kp$ with $k \in \Bbb Z$.

This in turn is true by (10), since according to that, the denominator of $x$ is exactly $p^{\nu_p(\tau(n))}$, which exactly cancels the powers of $p$ that are in $\tau(n)$, and the other factor $(p^{whatever}-1)$ is obviously not divisible by $p$.

$\endgroup$
  • $\begingroup$ Ok so my only remaining issue is then those I have labelled $(7\operatorname{i})$ & $(8\operatorname{i})$ $\endgroup$ – Adam Oct 3 '18 at 2:57
  • 1
    $\begingroup$ Note that the formula I quoted from WP shows that if $n$ is a square, $\tau(n)$ is odd. This easily proves both 7i and 8i. $\endgroup$ – Torsten Schoeneberg Oct 3 '18 at 3:12
  • 1
    $\begingroup$ Ok thankyou so much for your assistance Torsten I can see now this was far more straight forward than the considerations I had been previously considering $\endgroup$ – Adam Oct 10 '18 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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