Results 1 to 2 of 2

Math Help - An extension of Dirichlet's Divisor Problem

  1. #1
    Member
    Joined
    May 2008
    From
    Melbourne Australia
    Posts
    216
    Thanks
    29

    An extension of Dirichlet's Divisor Problem

    Let d_3(n) denote the number of ordered triples of integers whose product is n. Prove that:

     \sum^N_{n=1}d_3(n)=N \log^2 N+O(N \log N)

    HINT: Count the lattice points with positive coordinates under or on the surface defined by xyz=N.

    Something I know:
     \sum^N_{n=0}d(n)=N \log N+cN+O(\sqrt N) for some constant c.

    I can see two possible ways of aproaching this.
    Method 1. If I imagine a unit cube placed onto each point (x,y,z) that lies between the curve xyz=N and the three planes x=1, y=1 and z=1 then the volume (and hence number of) these cubes will exceed the volume under the curve xyz=N. By calculus (very rusty, could be wrong) I find that the volume is  0.5 N \log^2 N. Suggesting that once I consider the negative integer solutions I would get an answer of more than  2 N \log^2 N plus a big O term. Wrong by a factor of 2 and I don't know how to calculate the big O terms!

    Method 2.
     \sum^N_{n=1}d_3(n)=\sum^N_{z=1}([N/z] \log [N/z]+c[N/z]+O(\sqrt {[N/z]})) where [N/z] represents the integer part of N/z. But I have had no luch working through the detail of this idea either!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Let <br />
d_3 ^ + be the number of triplets <br />
\left( {x,y,z} \right) \in \left( {\mathbb{Z}^ +  } \right)^3 <br />
such that <br />
x \cdot y \cdot z = n<br />
, note that: <br />
d_3  = 4 \cdot d_3 ^ +  <br />
because indeed: <br />
3 \cdot d_3 ^ +   = d_3  - d_3 ^ +  <br />
( intepret the RHS as the number of triplets <br />
\left( {x,y,z} \right) \in \mathbb{Z}^3 <br />
such that <br />
x \cdot y \cdot z = n<br />
and at least one of those factors is negative- therefore we must have 2 negatives since <br />
n \in \mathbb{Z}^ +  <br />
)

    Note that: <br />
\sum\limits_{k = 1}^n {f\left( k \right) \cdot \sum\limits_{j = 1}^{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } {g\left( j \right) \cdot \sum\limits_{s = 1}^{\left\lfloor {\tfrac{n}<br />
{{k \cdot j}}} \right\rfloor } {h\left( s \right) \cdot x^{k \cdot j \cdot s} } } }  = \sum\limits_{k = 1}^n {\left( {\sum\limits_{a \cdot b \cdot c = k;a,b,c > 0} {f\left( a \right) \cdot g\left( b \right) \cdot h\left( c \right)} } \right) \cdot x^k } <br />

    Thus: <br />
\sum\limits_{k = 1}^n {\sum\limits_{j = 1}^{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } {\sum\limits_{s = 1}^{\left\lfloor {\tfrac{n}<br />
{{k \cdot j}}} \right\rfloor } 1 } }  = \sum\limits_{k = 1}^n {d_3 ^ +  \left( k \right)} <br />
that is: <br />
\sum\limits_{k = 1}^n {\sum\limits_{j = 1}^{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } {\left\lfloor {\tfrac{n}<br />
{{k \cdot j}}} \right\rfloor } }  = \sum\limits_{k = 1}^n {d_3 ^ +  \left( k \right)} <br />

    By the definition of the floor function: <br />
\sum\limits_{k = 1}^n {d_3 ^ +  \left( k \right)}  \leqslant \sum\limits_{k = 1}^n {\sum\limits_{j = 1}^{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } {\tfrac{n}<br />
{{k \cdot j}}} }  < \sum\limits_{k = 1}^n {d_3 ^ +  \left( k \right)}  + \sum\limits_{k = 1}^n {\sum\limits_{j = 1}^{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } 1 } <br />

    That is: <br />
\sum\limits_{k = 1}^n {d_3 ^ +  \left( k \right)}  \leqslant \sum\limits_{k = 1}^n {\tfrac{n}<br />
{k} \cdot H_{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } }  < \sum\limits_{k = 1}^n {d_3 ^ +  \left( k \right)}  + \sum\limits_{k = 1}^n {\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } <br />

    Now consider that: <br />
\left\{ \begin{gathered}<br />
  \sum\limits_{k = 1}^n {\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor }  = \sum\limits_{k = 1}^n {d\left( k \right)}  = n \cdot \log \left( n \right) + O\left( n \right) \hfill \\<br />
  H_{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor }  = \log \left( {\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } \right) + O\left( 1 \right) \hfill \\ <br />
\end{gathered}  \right.<br />

    Then we get: <br />
\sum\limits_{k = 1}^n {\tfrac{n}<br />
{k} \cdot \log \left( {\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } \right)}  - \sum\limits_{k = 1}^n {d_3 ^ +  \left( k \right)}  =  O\left( n \cdot \log \left( n \right)\right)<br />

    Let's see what happens with that logarithm on the LHS:
    <br />
\sum\limits_{k = 1}^n {\tfrac{n}<br />
{k} \cdot \log \left( {\tfrac{n}<br />
{k}} \right)}  - \sum\limits_{k = 1}^n {\tfrac{n}<br />
{k} \cdot \log \left( {\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } \right)}  = \sum\limits_{k = 1}^n {\tfrac{n}<br />
{k} \cdot \log \left( {\tfrac{n}<br />
{{k \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor }}} \right)} <br />

    Using the definition of the floor function again: <br />
0 = \log \left( 1 \right) \leqslant \log \left( {\tfrac{n}<br />
{{k \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor }}} \right) \leqslant \log \left( {1 + \tfrac{1}<br />
{{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor }}} \right) \leqslant \tfrac{1}<br />
{{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor }}<br />

    Thus: <br />
0 \leqslant \sum\limits_{k = 1}^n {\tfrac{n}<br />
{k} \cdot \log \left( {\tfrac{n}<br />
{k}} \right)}  - \sum\limits_{k = 1}^n {\tfrac{n}<br />
{k} \cdot \log \left( {\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } \right)}  \leqslant \sum\limits_{k = 1}^n {\tfrac{n}<br />
{k} \cdot \tfrac{1}<br />
{{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor }}}  = O\left( n \right)<br />

    That is: <br />
\sum\limits_{k = 1}^n {\tfrac{n}<br />
{k} \cdot \log \left( {\tfrac{n}<br />
{k}} \right)}  + O\left( n \right) = \sum\limits_{k = 1}^n {\tfrac{n}<br />
{k} \cdot \log \left( {\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } \right)} <br />

    Thus: <br />
\sum\limits_{k = 1}^n {\tfrac{n}<br />
{k} \cdot \log \left( {\tfrac{n}<br />
{k}} \right)}  - \sum\limits_{k = 1}^n {d_3 ^ +  \left( k \right)}  =  O\left( n \cdot \log \left( n \right) \right)<br />

    Now we have: <br />
\sum\limits_{k = 1}^n {\tfrac{n}<br />
{k} \cdot \log \left( {\tfrac{n}<br />
{k}} \right)}  = n \cdot \log \left( n \right) \cdot \sum\limits_{k = 1}^n {\tfrac{1}<br />
{k}}  - n \cdot \sum\limits_{k = 1}^n {\tfrac{{\log \left( k \right)}}<br />
{k}}  = \tfrac{n}<br />
{2} \cdot \log ^2 \left( n \right) + O\left[ {n \cdot \log \left( n \right)} \right]<br />
(use integrals to approximate the second sum)

    Thus: <br />
\sum\limits_{k = 1}^n {d_3 ^ +  \left( k \right)}  = \tfrac{n}<br />
{2} \cdot \log ^2 \left( n \right) + O\left[ {n \cdot \log \left( n \right)} \right]<br />

    So this would yield: <br />
\sum\limits_{k = 1}^n {d_3  \left( k \right)}  = 2\cdot n\cdot \log ^2 \left( n \right) + O\left[ {n \cdot \log \left( n \right)} \right]<br />


    PS: When you put \sum^N_{n=1}d(n)=N \log N+cN+O(\sqrt N)<br />
, be careful, that d(n) represents the number of positive divisors of n
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Dirichlet Inverse Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 27th 2011, 11:14 PM
  2. Two questions concerning Laplacian (and a Dirichlet Problem)
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: March 9th 2011, 05:41 AM
  3. Dirichlet problem for a rectangle
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 23rd 2010, 05:42 PM
  4. Holomorphic extension of Dirichlet Series
    Posted in the Number Theory Forum
    Replies: 15
    Last Post: April 26th 2010, 03:43 PM
  5. Dirichlet Divisor problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 7th 2009, 02:12 PM

Search Tags


/mathhelpforum @mathhelpforum