Divisors on Overlapped Intervals and Multiplicative Functions

José Manuel Rodríguez Caballero Département de Mathématiques UQAM Case Postale 8888, Succ. Centre-ville Montréal, Québec H3C 3P8 Canada

        rodriguez caballero.jose manuel@uqam.ca

Abstract

Reutenauer and Kassel introduced a family P_{n}(q) of polynomials defined in terms of divisors of n on overlapped intervals. The evaluation of P_{n}(q) at roots of unity of order 2, 3, 4, 6 form well-known integer sequences related to the number of integer solutions of the equations x^{2} + y^{2} = n, x^{2} + 2y^{2} = n, and x^{2} + xy + y^{2} = n. Also, P_{n}(1) is the sum of divisors of n. In this paper we define a new family L_{n}(q) of polynomials defined in terms of divisors of n on overlapped intervals, slightly modifying the definition of P_{n}(q). The values of L_{n}(q) at q = 1 and q = −1 are related to the sum of divisors of n and to the number of integer solutions of the equations x^{2} + xy + y^{2} = n and x^{2} + 3y^{2} = n.

1 Introduction

For a given integer n ≥ 1, consider the two-sided sequence

p_{n,k} = ln (k + \sqrt{k^{2} + 2 n}) ,

where k ∈ ℤ and define the intervals

P_{n,k} = (p_{n,k} − ln 2, p_{n,k}] .

Kassel and Reutenauer [2] introduced the polynomials^{1}

\frac{P_{n}(q)}{q^{n−1}} = ∑_{d|n} ∑_{k∈ℤ} 1_{P_{n,k}} (ln d) q^{k},

where 1_{A}(x) is the characteristic function of the set A, i.e., 1_{A}(x) = 1 if x ∈ A, otherwise 1_{A}(x) = 0. Each polynomial P_{n}(q) is monic of degree 2n−2, its coefficients are non-negative integers and it is self-reciprocal [3]. The evaluations of P_{n}(q) at some complex roots of 1 have number-theoretical interpretations [3], e.g.,

σ(n) = P_{n}(1),
\frac{r_{1,0,1}(n)}{4} = P_{n}(−1),
\frac{r_{1,0,2}(n)}{2} = |P_{n} (\sqrt{−1})| ,
\frac{r_{1,1,1}(n)}{6} = Re P_{n} (\frac{−1 + \sqrt{−3}}{2}) ,

where σ(n), \frac{r_{1,0,1}(n)}{4}, \frac{r_{1,0,2}(n)}{2} and \frac{r_{1,1,1}(n)}{6} are multiplicative functions [5] given by

σ(n) = ∑_{d|n} d,
r_{a,b,c}(n) = # {(x, y) ∈ ℤ^{2} : a x^{2} + b x y + c y^{2} = n} .

Furthermore, for q = \frac{1+\sqrt{−3}}{2}, the same sequence n ↦ P_{n}(q) is related to r_{1,0,1}(n) in three ways [4], depending on the congruence class of n in ℤ/3ℤ,

|P_{n} (\frac{1 + \sqrt{−3}}{2})| = \begin{cases}r_{1,0,1}(n), & if n ≡ 0 (mod 3); \\ \frac{1}{4} r_{1,0,1}(n), & if n ≡ 1 (mod 3); \\ \frac{1}{2} r_{1,0,1}(n), & if n ≡ 2 (mod 3). \end{cases}

For any integer n ≥ 1, consider the two-sided sequence

ℓ_{n,k} = ln (\frac{3}{2} k + \sqrt{(\frac{3}{2} k)^{2} + 3 n})

and the intervals

L_{n,k} = (ℓ_{n,k} − ln 3, ℓ_{n,k}] ,

1The original definition of P_{n}(q), which we refer to as Kassel-Reutenauer polynomials [2] is rather different, but equivalent, to the one presented here. We preferred to take the logarithm of the divisors in place of the divisors themselves in order to work with intervals P_{n,k} of constant length.

\begin{matrix}ℓ_{6,k} \\ ln d \\ -6 \\ -5 \\ -4 \\ -3 \\ -2 \\ -1 \\ 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 1 \\ 2 \\ 3 \\ 6 \end{matrix}

Figure 1: Representation of L_{6}(q).

where k runs over the integers. Define a variation of the polynomials P_{n}(q) as follows:

\frac{L_{n}(q)}{q^{n−1}} = ∑_{d|n} ∑_{k∈ℤ} 1_{L_{n,k}} (ln d) q^{k}.

For example, in order to compute L_{6}(q) from the definition, we need to consider the intervals (ℓ_{6,k} − ln 3, ℓ_{6,k}] on the real line and to count the number of values of ln d inside each interval, where d runs over the divisors of n. These data are shown in Figure 1, where the numbers ℓ_{6,k} are plotted on the line below (the corresponding values of k are labelled) whereas the numbers ln d are plotted on the line above (the corresponding values of d are labelled). Counting the number of intersections between the horizontal and the vertical lines, we obtain that the coefficients of \frac{L_{6}(q)}{q^{6−1}} are as follows:

\frac{L_{6}(q)}{q^{6−1}} = q^{5} + q^{4} + q^{3} + 2 q^{2} + 2 q + 2 q^{0} + 2 q^{−1} + 2 q^{−2} + q^{−3} + q^{−4} + q^{−5}.

Like P_{n}(q), the polynomial L_{n}(q) is monic of degree 2 n − 2, self-reciprocal and its coefficients are non-negative integers. The aim of this paper is to express the multiplicative functions [5, p. 421] \frac{r_{1,1,1}(n)}{6} and \frac{r_{1,0,3}(n)}{2} in terms of the evaluations of L_{n}(q) at roots of the unity. More precisely, we will prove the following result.

Theorem 1. For each n ≥ 1,

\underline{A002324}(n) := \frac{r_{1,1,1}(n)}{6} = 4 σ(n) − 3 L_{n} (1) ,  (1)
\underline{A096936}(n) := \frac{r_{1,0,3}(n)}{2} = L_{n} (−1) .  (2)

2 Auxiliary results for the first identity of Theorem 1

For any n ≥ 1, we will use the notation

d_{a,m}(n) := # {d|n : d ≡ a (mod m)} .

We will use the following well-known result [1]. Lemma 2. For all integers n ≥ 1,

\frac{r_{1,1,1}(n)}{6} = d_{1,3}(n) − d_{2,3}(n).

Lemma 3. For any integer n ≥ 1,

3 ⌈3^{−1} n⌉ − n = \begin{cases}0, & if n ≡ 0 (mod 3); \\ 2, & if n ≡ 1 (mod 3); \\ 1, & if n ≡ 2 (mod 3). \end{cases}
n − 3 ⌊3^{−1} n⌋ = \begin{cases}0, & if n ≡ 0 (mod 3); \\ 1, & if n ≡ 1 (mod 3); \\ 2, & if n ≡ 2 (mod 3). \end{cases}

Proof. It is enough to evaluate 3 ⌈3^{−1} n⌉ − n and 3 ⌈3^{−1} n⌉ − n at n = 3k + r, for k ∈ ℤ and r ∈ {0, 1, 2}. Lemma 4. For any pair of integers n ≥ 1 and k, the inequalities

ℓ_{n,k} − ln 3 < ln d ≤ ℓ_{n,k}

hold if and only if the inequalities

3^{−1} d − \frac{n}{d} ≤ k < d − 3^{−1} \frac{n}{d}

hold. Proof. The inequalities

ℓ_{n,k} − ln 3 < ln d ≤ ℓ_{n,k}

are equivalent to

ln d ≤ ℓ_{n,k} < ln d + ln 3.

Applying the strictly increasing function x ↦ \frac{e^{x}}{3} −n e^{−x} to the last inequalities we obtain the following equivalent inequalities

3^{−1} d − \frac{n}{d} ≤ k < d − 3^{−1} \frac{n}{d}.

Indeed, \frac{e^{ln d}}{3} − n e^{− ln d} = 3^{−1} d − \frac{n}{d}, \frac{e^{ln d+ln 3}}{3} − n e^{−(ln d+ln 3)} = d − 3^{−1} \frac{n}{d} and

\frac{e^{ℓ_{n,k}}}{3} − n e^{−ℓ_{n,k}} = \frac{\frac{3}{2} k + \sqrt{(\frac{3}{2} k)^{2} + 3 n}}{3} − \frac{n}{\frac{3}{2} k + \sqrt{(\frac{3}{2} k)^{2} + 3 n}}
= \frac{\frac{3}{2} k + \sqrt{(\frac{3}{2} k)^{2} + 3 n}}{3} + \frac{\frac{3}{2} k − \sqrt{(\frac{3}{2} k)^{2} + 3 n}}{3}
= k.

So the lemma is proved. Lemma 5. Let n ≥ 1 be an integer. For all d|n,

∑_{k∈ℤ} 1_{L_{n,k}} (ln d) = ⌈d − 3^{−1} \frac{n}{d}⌉ − ⌈3^{−1} d − \frac{n}{d}⌉ .

Proof. For all integers n ≥ 1 and k, we have that

∑_{k∈ℤ} 1_{L_{n,k}} (ln d)
= # {k ∈ ℤ : ℓ_{n,k} − ln 3 < ln d ≤ ℓ_{n,k}}
= # \{k ∈ ℤ : 3^{−1} d − \frac{n}{d} ≤ k < d − 3^{−1} \frac{n}{d}\} (Lemma 4)
= # \{k ∈ ℤ : ⌈3^{−1} d − \frac{n}{d}⌉ ≤ k < ⌈d − 3^{−1} \frac{n}{d}⌉\}
= ⌈d − 3^{−1} \frac{n}{d}⌉ − ⌈3^{−1} d − \frac{n}{d}⌉ .

So the lemma is proved.

3 Auxiliary results for the second identity of Theo-

rem 1

We will use the following well-known result [5, p. 421]. Lemma 6. The function \frac{r_{1,0,3}(n)}{2} is multiplicative.

We will use the following well-known result [1]. Lemma 7. For all integers n ≥ 1,

\frac{r_{1,0,3}(n)}{2} = d_{1,3}(n) − d_{2,3}(n) + 2 (d_{4,12}(n) − d_{8,12}(n)) .

Recall that the nonprincipal Dirichlet character mod 3 is the 3-periodic arithmetic function χ_{3}(n) given by χ_{3}(0) = 0, χ_{3}(1) = 1 and χ_{3}(2) = −1.

Lemma 8. For all n ≥ 1,

\frac{(−1)^{⌊3^{−1} n⌋} − (−1)^{⌈3^{−1} n⌉}}{2} = (−1)^{n−1} χ_{3}(n).

Proof. It is enough to substitute n = 3k + r, with k ∈ ℤ and r ∈ {0, 1, 2}, in both sides in order to check that they are equal.

Lemma 9. For all n ≥ 1,

∑_{d|n} (−1)^{\frac{n}{d} −1} (−1)^{d−1} χ_{3}(d) = (−1)^{n−1} \frac{r_{1,0,3}(n)}{2}.

Proof. By Lemma 6, the function \frac{r_{1,0,3}(n)}{2} is multiplicative. Also, it is easy to check that the functions (−1)^{n−1} and χ_{3}(n) are multiplicative. So the functions f(n) = (−1)^{n−1} \frac{r_{1,0,3}(n)}{2} and (−1)^{n−1} χ_{3}(n) are multiplicative, because the multiplicative property is preserved by ordinary product. The function g(n) = ∑_{d|n} (−1)^{\frac{n}{d} −1} (−1)^{d−1} χ_{3}(d) is multiplicative, because Dirichlet convolution preserves the multiplicative property. So it is enough to prove that f (p^{k}) = g (p^{k}) for each prime power p^{k}.

Considering the case p = 2. The following elementary equivalences hold for any integer m ≥ 0,

2^{m} ≡ 1 (mod 3) ⟺ m ≡ 0 (mod 2),
2^{m} ≡ 2 (mod 3) ⟺ m ≡ 1 (mod 2),
2^{m} ≡ 4 (mod 12) ⟺ m ≡ 0 (mod 2) and m ≠ 0,
2^{m} ≡ 8 (mod 12) ⟺ m ≡ 1 (mod 2) and m ≠ 1.

So, for each integer k ≥ 1,

d_{1,3} (2^{k}) = #[0, k] ∩ 2ℤ = ⌊\frac{k}{2}⌋ + 1,
d_{2,3} (2^{k}) = #[1, k] ∩ (2ℤ + 1) = ⌈\frac{k}{2}⌉ ,
d_{4,12} (2^{k}) = #[2, k] ∩ 2ℤ = ⌊\frac{k}{2}⌋ ,
d_{8,12} (2^{k}) = #[3, k] ∩ (2ℤ + 1) = ⌈\frac{k}{2}⌉ − 1.

For any k ≥ 1, it follows that

g (2^{k}) = ∑_{j=0}^{k} (−1)^{2^{k−j}−1} (−1)^{2^{j}−1} χ_{3} (2^{j})

= ∑_{j=0}^{k} (−1)^{2^{k−j}−1} (−1)^{2^{j}−1} (−1)^{j}

= −1 − (−1)^{k} + ∑_{j=1}^{k−1} (−1)^{j}

= −1 − (−1)^{k} + \frac{−1 − (−1)^{k}}{2}
= −3 \frac{1 + (−1)^{k}}{2}
= −3 (1 + ⌊\frac{k}{2}⌋ − ⌈\frac{k}{2}⌉)
= − ((⌊\frac{k}{2}⌋ + 1) − ⌈\frac{k}{2}⌉ + 2 (⌊\frac{k}{2}⌋ − (⌈\frac{k}{2}⌉ − 1)))
= (−1)^{2^{k}−1} (d_{1,3} (2^{k}) − d_{2,3} (2^{k}) + 2 (d_{4,12} (2^{k}) − d_{8,12} (2^{k})))
= f (2^{k}) (Lemma 7).

Let p and k ≥ 1 be an odd prime and an integer respectively. Noticing that (−1)^{p^{j}−1} = 1 for all 0 ≤ j ≤ k. Also, d_{4,12} (p^{k}) = d_{8,12} (p^{k}) = 0, because p^{k} has not even divisor. So, for any k ≥ 1,

g (p^{k}) = ∑_{j=0}^{k} (−1)^{p^{k−j}−1} (−1)^{p^{j}−1} χ_{3} (p^{j})

= ∑_{j=0}^{k} χ_{3} (p^{j})
= d_{1,3} (p^{k}) − d_{2,3} (p^{k})
= (−1)^{p^{k}−1} (d_{1,3} (p^{k}) − d_{2,3} (p^{k}) + 2 (d_{4,12} (p^{k}) − d_{8,12} (p^{k})))
= f (p^{k}) (Lemma 7).

Therefore, f(n) = g(n) for all n ≥ 1.

Lemma 10. For each d|n,

∑_{k∈ℤ} 1_{L_{n,k}} (ln d) (−1)^{k} = \frac{1}{2} ((−1)^{⌈3^{−1} d− \frac{n}{d}⌉} − (−1)^{⌈d−3^{−1} \frac{n}{d}⌉}) .

Proof. For any integer n ≥ 1 and any d|n,

∑_{k∈ℤ} 1_{L_{n,k}} (ln d) (−1)^{k} = ∑_{3^{−1} d− \frac{n}{d} ≤k<d−3^{−1} \frac{n}{d}} (−1)^{k} (Lemma 4)
= ∑_{⌈3^{−1} d− \frac{n}{d} ⌉≤k<⌈d−3^{−1} \frac{n}{d} ⌉} (−1)^{k} .

Substituting a = ⌈3^{−1} d − \frac{n}{d}⌉, b = ⌈d − 3^{−1} \frac{n}{d}⌉ and q = −1 in the geometric sum

∑_{a≤k<b} q^{k} = \frac{q^{a} − q^{b}}{1 − q}

we obtain

∑_{k∈ℤ} 1_{L_{n,k}} (ln d) (−1)^{k} = \frac{(−1)^{⌈3^{−1} d− \frac{n}{d}⌉} − (−1)^{⌈d−3^{−1} \frac{n}{d}⌉}}{1 − (−1)}
= \frac{1}{2} ((−1)^{⌈3^{−1} d− \frac{n}{d}⌉} − (−1)^{⌈d−3^{−1} \frac{n}{d}⌉}) .

So the lemma is proved.

4 Proof of the main result

We proceed now with the proof of the main result of this paper. Proof of Theorem 1. Identity (1) follows from the following transformations,

L_{n}(1) = ∑_{d|n} ∑_{k∈ℤ} 1_{L_{n,k}} (ln d)
= ∑_{d|n} (⌈d − 3^{−1} \frac{n}{d}⌉ − ⌈3^{−1} d − \frac{n}{d}⌉) (Lemma 5)
= ∑_{d|n} (d + \frac{n}{d}) + ∑_{d|n} ⌈−3^{−1} \frac{n}{d}⌉ − ∑_{d|n} ⌈3^{−1}d⌉
= ∑_{d|n} (d + \frac{n}{d}) − ∑_{d|n} ⌊3^{−1} \frac{n}{d}⌋ − ∑_{d|n} ⌈3^{−1}d⌉

= \frac{2}{3} ∑_{d|n} (d + \frac{n}{d}) + \frac{1}{3} ∑_{d|n} (\frac{n}{d} − 3 ⌊3^{−1} \frac{n}{d}⌋) − \frac{1}{3} ∑_{d|n} (3 ⌈3^{−1}d⌉ − d)

= \frac{4σ(n)}{3} + \frac{d_{1,3}(n) + 2d_{2,3}(n)}{3} − \frac{2d_{1,3}(n) + d_{2,3}(n)}{3} (Lemma 3)
= \frac{4σ(n)}{3} − \frac{d_{1,3}(n) − d_{2,3}(n)}{3}
= \frac{4}{3} σ(n) − \frac{1}{3} \frac{r_{1,1,1}(n)}{6} (Lemma 2).

Identity (2) follows from the following transformations,

\frac{L_{n} (−1)}{(−1)^{n−1}} = ∑_{d|n} ∑_{k∈ℤ} 1_{L_{n,k}} (ln d) (−1)^{k}

= ∑_{d|n} \frac{1}{2} ((−1)^{⌈3^{−1} d− \frac{n}{d}⌉} − (−1)^{⌈\frac{n}{d} −3^{−1} d⌉}) (Lemma 10)

= ∑_{d|n} \frac{1}{2} ((−1)^{⌈3^{−1} d⌉− \frac{n}{d}} − (−1)^{\frac{n}{d} −⌊3^{−1} d⌋})

= ∑_{d|n} (−1)^{\frac{n}{d} −1} \frac{(−1)^{⌊3^{−1} d⌋} − (−1)^{⌈3^{−1} d⌉}}{2}
= ∑_{d|n} (−1)^{\frac{n}{d} −1} (−1)^{d−1} χ_{3}(d) (Lemma 8)

= (−1)^{n−1} \frac{r_{1,0,3}(n)}{2} (Lemma 9).

So the theorem is proved.

5 Final remarks

1. Let k be a field and R be a k-algebra. The codimension of an ideal I of R is the dimension of the quotient R/I as a vector space over k.

We let ℤ⊕ℤ denote the free abelian group of rank 2. Let k = 𝔽_{q} be the finite field with q elements and R = 𝔽_{q} [ℤ ⊕ ℤ] be its group algebra. Kassel and Reutenauer [2] proved that, for any prime power q, the number of ideals of codimension n ≥ 1 of 𝔽_{q} [ℤ ⊕ ℤ] is (q − 1)^{2} P_{n}(q). So it is natural to look for connections between the values of L_{n}(q), when q is a prime power, and the algebraic structures related to 𝔽_{q}.

2. The polynomials P_{n}(q) are generated by the product [3]

∏_{m≥1} \begin{matrix}(1 − t^{m}) & 2 \\ (1 − q t^{m}) & (1 − q^{−1} t^{m}) \end{matrix} = 1 + (q + q^{−1} − 2) ∑_{n=1}^{∞} \frac{P_{n}(q)}{q^{n−1}} t^{n}.

It would be interesting to find a similar generating function for L_{n}(q).

6 Acknowledgments

The author deeply thanks Prof. S. Brlek and Prof. C. Reutenauer for reading carefully the paper and for providing useful comments. The author gratefully acknowledges the referee.

References

[1] M. D. Hirschhorn, Three classical results on representations of a number, in D. Foata and G.-N. Han, eds., The Andrews Festschrift, Springer, 2001, pp. 159–165.

[2] C. Kassel and C. Reutenauer, Counting the ideals of given codimension of the algebra of Laurent polynomials in two variables, Michigan Math. J., to appear.

[3] C. Kassel and C. Reutenauer, Complete determination of the zeta function of the Hilbert scheme of n points on a two-dimensional torus, Ramanujan J., to appear.

[4] C. Kassel and C. Reutenauer, The Fourier expansion of η(z) η(2z) η(3z) / η(6z), Archiv Math. 108 (2017), 453–463.

[5] L. V. Lorenz, Œuvres scientifiques de L. Lorenz, Vol. 2, Lehmann & Stage, 1899.

[6] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, available at

   http://oeis.org.

2010 Mathematics Subject Classification: Primary 11A25; Secondary 11A07, 11A05. Keywords: multiplicative function, representation by quadratic form, polynomial, divisor.

(Concerned with sequences \underline{A002324} and \underline{A096936}.)

Received September 16 2017; revised versions received October 13 2017; October 21 2017. Published in Journal of Integer Sequences, October 29 2017.

Return to Journal of Integer Sequences home page.