4
$\begingroup$

Here's a question I've been asked:

Let $n\in \mathbb{N}$ and let $d_k(n)$ be the number of solutions of $x_1\dots x_k = n, \hspace{5mm}x_i\in \mathbb{N}$

I need to show

$d_k(n) = \sum_{d|n}d_{k-1}(d), \hspace{5mm} k \ge 2$ and that for any $\epsilon > 0$, $d_k(n) = O(n^\epsilon)$ where the implied constant depends only on $k$. I.e $d_k(n) \ll f(k)n^\epsilon$ for some function $f$.

I have to admit, I'm lacking an idea of what $d_k(n)$ looks like. Setting up the base case for an inductive argument isn't difficult, but I'm having a hard time picturing how this being true for an arbitrary $k$ implies the statement for $k+1$. The statement $\epsilon > 0$, $d_k(n) = O(n^\epsilon)$ is also very strange to me, having a CS background. I can kind of see how the choice of $\epsilon$ is arbitrary, since it just varies the implied constant in $O(n^\epsilon$). I can't seem to reconcile any of this in my head. Advice? Thanks for your time.

1 Answers 1

2

For the summation, note that $d_k(n)$ is the number of ordered $k$-tuples $(x_1,x_2, \dots, x_k)$ of $x_2x_2\cdots x_k=n$.

If $d$ is any divisor of $n$, consider the $k$-tuples whose last term $x_k$ is equal to $n/d$. How many of these are there? The $(k-1)$-tuple $(x_1,x_2,\dots, x_{k-1})$ must then have product $d$, and by definition there are $d_{k-1}(d)$ such $(k-1)$-uples. Finally, sum over all $d$ that divide $n$.

For the estimate, probably you are expected to use the just proved sum result, and to use an upper bound on the number of divisors of $n$ to bound $d_k(n)$.

Remark: If you are familiar with the term, note that the relationship just proved shows that $d_k(n)$ is multiplicative, that is, that $d_k(ab)=d_k(a)d_k(b)$ whenever $a$ and $b$ are relatively prime.

That implies that we can write down $d_k(n)$ once we know the structure of the prime power factorization of $n$.

  • 0
    Ahh great idea about it being multiplicative. Things like that are never apparent to me... thought I'm slowly getting better. Thanks for the reply!2012-11-19