Lagmental Vicfred

A Floor Sum Counts Divisors in a Hyperbola by Vicfred

Last updated: Sat 09 December 2017

tags: mathematics, arithmetic functions, Dirichlet convolution, Mobius inversion

Summing floor x over d counts lattice points under uv at most x and leads to the Dirichlet hyperbola method. Keeping the exact identity in view prevents the geometric or probabilistic intuition from drifting.

Notation

Arithmetic functions \(f:\mathbf N\to\mathbf C\) form a commutative ring under Dirichlet convolution. Multiplicative functions are determined by their values on prime powers \(p^k\).

$$ \sum_{n\le x}\tau(n)=\sum_{d\le x}\left\lfloor\frac xd\right\rfloor $$

The formulas should not be merged too early. The datum \(\mathsf D\), the conclusion \(\mathsf C\), and the bridge \(\Longrightarrow\) have three different logical jobs.

$$ \sum_{n\le x}\tau(n)=2\sum_{d\le\sqrt x}\left\lfloor\frac xd\right\rfloor-\lfloor\sqrt x\rfloor^2 $$

Stress the formula

A worked instance is useful here because it exposes every index that the compressed statement hides.

$$ \#\{(u,v)\in\mathbf N^2:uv\le x\}=\sum_{\substack{u,v\ge1\\uv\le x}}1 $$

Interpretation

A good test for understanding is to change the presentation while keeping the invariant fixed. The aligned form makes that comparison unusually easy.

$$ \begin{aligned} \mathsf{D}\;&:\quad \sum_{n\le x}\tau(n)=\sum_{d\le x}\left\lfloor\frac xd\right\rfloor,\\[5pt] \mathsf{C}\;&:\quad \sum_{n\le x}\tau(n)=2\sum_{d\le\sqrt x}\left\lfloor\frac xd\right\rfloor-\lfloor\sqrt x\rfloor^2. \end{aligned} $$

Limit of the argument

Pointwise multiplication and Dirichlet convolution are different operations. Möbius inversion reverses convolution with the constant-one function, not ordinary multiplication.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \sum_{n\le x}\tau(n)=2\sum_{d\le\sqrt x}\left\lfloor\frac xd\right\rfloor-\lfloor\sqrt x\rfloor^2 \end{gathered}} $$

This is enough machinery for one note: an exact object, a worked case, a structural law, and a clearly marked boundary. Each layer can now be tested independently.

This article was posted on Wed 14 June 2017. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.