Séminaire Lotharingien de Combinatoire 46 (2002), Article B46i

EVEN PARTITION FUNCTIONS

by

F. Ben saïd^{1} Faculté des Sciences de Monastir Avenue de l’environnement 5000, Monastir, Tunisie

                e-mail : Fethi.BenSaid@fsm.rnu.tn

and

J.-L. Nicolas^{1} Institut Girard Desargues, UMR 5028, Bât. Doyen Jean Braconnier, Université Claude Bernard (Lyon 1), 21 Avenue Claude Bernard, F-69622 Villeurbanne Cedex, France

                   e-mail : jlnicola@in2p3.fr

Abstract. Let A be a set of positive integers. Let us denote by p(A, n) the number of partitions of n with parts in A. While the study of the parity of the classical partition function p(ℕ, n) (where ℕ is the set of positive integers) is a deep and difficult problem, it is easy to construct a set A for which p(A, n) is even for n large enough : as explained in a paper of I.Z. Ruzsa, A. Sárközy and J.-L. Nicolas published in 1998 in the Journal of Number Theory, if B is a subset of {1, 2, …, N}, there is a unique set A = A_{0}(B, N) such that A ∩ {1, 2, …, N} = B and p(A, n) is even for n > N.

In this paper we recall some properties of the sets A_{0}(B, N), we describe the factorization into primes of the elements of the set A_{0}({1, 2, 3}, 3), and prove that the number of elements of this set up to x is asymptotically equivalent to c\frac{x}{(log x)^{3/4}} , where c = 0.937 . . ..

Résumé. Si A est un ensemble d’entiers positifs, nous noterons p(A, n) le nombre de partitions de n dont les parts sont dans A. L’étude de la parité de la fonction usuelle de partition p(ℕ, n) (où ℕ est l’ensemble des entiers positifs) est un problème profond et difficile ; mais il est facile de construire un ensemble A tel que le nombre p(A, n) soit pair pour tout n assez grand : dans un article paru au Journal of Number Theory en 1998, I.Z. Ruzsa, A. Sárközy et J.-L. Nicolas montrent que si B est un sous-ensemble de {1, 2, …, N}, il existe un seul ensemble A = A_{0}(B, N) tel que A ∩ {1, 2, …, N} = B et p(A, n) est pair pour n > N.

1Research partially supported by French-Tunisian exchange program, C.M.C.U. n^{o} 99/F 1507 and by CNRS, Institut Girard Desargues, UMR 5028.

Dans cet article, nous rappelons quelques propriétés des ensembles A = A_{0}(B, N), nous décrivons la décomposition en facteurs premiers des éléments de A_{0}({1, 2, 3}, 3) et nous montrons que le nombre des éléments de cet ensemble inférieurs à x est équivalent à c\frac{x}{(log x)^{3/4}} , où c = 0.937 . . ..

1 Introduction.

ℕ_{0} and ℕ denote the set of the non negative integers, resp. positive integers. A will denote a set of positive integers, and its counting function will be denoted by A(x) :

A(x) = |{a : a ≤ x , a ∈ A}|.

If A = {a_{1}, a_{2}, …} ⊂ ℕ (where a_{1} < a_{2} < ⋯), then p(A, n) denotes the number of partitions of n with parts in A, that is the number of solutions of the equation

a_{1}x_{1} + a_{2}x_{2} + … = n  (1.1)

in non negative integers x_{1}, x_{2}, . . .. As usual, we shall set

p(A, 0) = 1 and p(A, n) = 0 for n < 0.  (1.2)

We shall use the generating function :

F (z) = F_{A}(z) = ∑_{n=0}^{∞} p(A, n)z^{n} = ∏_{a∈A} \frac{1}{1 − z^{a}} ·  (1.3)

When A = ℕ it seems highly probable that the number of integers n ≤ x such that p(ℕ, n) is even is close to x/2 as x → ∞; but the known results are rather poor (see [11], [14], [15] and the references in them). That is the reason for which, in [11], it was observed that there exist sets A such that p(A, n) is even for n large enough. In this paper, we want to investigate the properties of such sets.

For i = 0 or 1, if A ⊂ ℕ and there is a number N such that

p(A, n) ≡ i (mod 2) for n ∈ ℕ , n > N.  (1.4)

then A is said to possess property P_{i}(N).

If i = 0 or 1, B is a finite set of positive integers, and N ∈ ℕ satisfying

B = {b_{1}, …, b_{k}} ≠ ∅, 0 < b_{1} < ⋯ < b_{k},  N ≥ b_{k}  (1.5)

then there is (cf. [11]) a unique set A ⊂ ℕ such that

A ∩ {1, 2, …, N} = B  (1.6)

and possessing property P_{i}(N) ; we will denote it by A_{i}(B, N).

Let us recall the construction of A_{i}(B, N) as described in [11], when, for instance, i = 0. The set A = A_{0}(B, N) will be defined by recursion. We write A_{n} = A ∩ {1, 2, …, n} so that

A_{N} = A ∩ {1, 2, …, N} = B.

Assume that n ≥ N + 1 and A_{n−1} has been defined so that p(A, m) is even for N + 1 ≤ m ≤ n − 1. Then set

n ∈ A if and only if p(A_{n−1}, n) is odd.

It follows from the construction that for n ≥ N + 1, we have

if n ∈ A , p(A, n) = 1 + p(A_{n−1}, n)
if n ∉ A , p(A, n) = p(A_{n−1}, n)

which shows that p(A, n) is even for n ≥ N + 1. Note that in the same way, any finite set B = {b_{1}, b_{2}, …, b_{k}} can be extended to a set A so that A_{b_{k}} = B and the parity of p(A, n) is given for n ≥ N + 1 (where N is any integer such that N ≥ b_{k}).

It has been shown in [5] (cf. Proposition 4) that, except the case i = 1, B = {1}, the set A_{i}(B, N) is always infinite.

If A ⊂ ℕ, let χ(A, n) denote the characteristic function of A, i.e.,

χ(A, n) = \{ \begin{matrix}1 & if & n ∈ A \\ 0 & if & n ∉ A, \end{matrix}  (1.7)

and for n ≥ 1,

σ(A, n) = ∑_{d | n} χ(A, d)d = ∑_{d | n, d∈ A} d.  (1.8)

It is relevant to consider σ(A, n), since, as shown in [11], taking the logarithmic derivative of F (z) = F_{A}(z) defined by (1.3) yields

z \frac{F′(z)}{F (z)} = ∑_{n=1}^{∞} σ(A, n)z^{n}.  (1.9)

It has been proved in [5] that for any positive integer k and any set A = A_{i}(B, N), the sequence

(σ(A, 2^{k}n) mod 2^{k+1})_{n≥1} is periodic.  (1.10)

(We denote by a mod b the remainder in the Euclidean division of a by b.) Note that (1.10) was already proved for k = 0 in [11], and for k = 1 in [3]. The value of the smallest period in (1.10) is recalled in Theorem A below, proved in [5]. Before stating Theorem A, we need to introduce two definitions.

Definition 1 Let 𝔽_{2} be the field with two elements and Q(z) ∈ 𝔽_{2}[z] be a polynomial satisfying Q(0) ≠ 0. The order β of Q is the least positive integer such that Q(z) divides 1 + z^{β} in 𝔽_{2}[z] (cf. [9], chap. 3).

From now on, we shall assume that i = 0, for simplicity (the case i = 1 can be found in [5]). For B and N as in (1.5) and A = A_{0}(B, N), let us define the polynomial P (already considered in [12] and [5]) :

P (z) = ∑_{0≤n≤J} ε_{n}z^{n}  (1.11)

where J is the largest integer such that p(A, J) is odd (such a J does exist since, from (1.2), p(A, 0) = 1), and ε_{n} is defined by

p(A, n) ≡ ε_{n} (mod 2), ε_{n} ∈ {0, 1}.  (1.12)

Theorem A (cf. Theorem 2 of [5]). Let B and N as in (1.5), A = A_{0}(B, N), and P be the polynomial defined by (1.11) and (1.12). Let the factorization of P into irreducible factors over 𝔽_{2}[z] be

P = Q_{1}^{α_{1}}Q_{2}^{α_{2}} … Q_{s}^{α_{s}}.  (1.13)

We denote by β_{i} the order of Q_{i}(z) (cf. Definition 1), and for all k ≥ 0, we set

J_{k} = {j; 1 ≤ j ≤ s, α_{j} ≡ 2^{k} (mod 2^{k+1})},  (1.14)
I_{k} = J_{0} ∪ J_{1} ∪ … ∪ J_{k} = {j; 1 ≤ j ≤ s, α_{j} ≢ 0 (mod 2^{k+1})}  (1.15)

and

q_{k} = lcm _{j∈I_{k}} β_{j}  (1.16)

(with q_{k} = 1 if I_{k} = ∅). Then, for all k ≥ 0, q_{k} is odd and is the smallest period of (1.10) so that

σ(A, 2^{k}(n + q_{k})) ≡ σ(A, 2^{k}n) (mod 2^{k+1}).  (1.17)

Note that if 2^{k_{0}} is the highest power of 2 dividing any exponent α_{j} in (1.13), for k > k_{0}, we have J_{k} = ∅, I_{k} = I_{k_{0}},

q_{k} = q =^{def} lcm (β_{1}, β_{2}, …, β_{s})

and q is a common period for all the sequences (σ(A, 2^{k}n) mod 2^{k+1})_{n≥1}, k ≥ 0.

Remark 1. In [3], one can find examples of B and N such that q_{0} ≠ q_{1}.

Note that (1.10) was already proved for k = 0 in [11], and for k = 1 in [3].

By Möbius inversion formula, (1.8) gives

nχ(A, n) = ∑_{d | n} μ(d)σ(A, n/d)  (1.18)

where μ is the Möbius function. If n is odd, by (1.10) with k = 0, we know the value of σ(A, n) mod 2, and this allows us from (1.18) to determine χ(A, n) for any set A = A_{i}(B, N). This has been done in [12] for A = A_{0}({1, 2, 3}, 3) and in [13] for A = A_{0}({1, 2, 3, 4, 5}, 5). In [3], the validity of (1.10) for k = 1 has been used to determine the elements of A = A_{0}({1, 2, 3}, 3) which are congruent to 2 modulo 4.

Similarly, it is possible to deduce from (1.10) the value of χ(A, n) where n is any positive integer. For that, it is convenient for m odd to introduce the sum

S(m, k) = χ(A, m) + 2χ(A, 2m) + … + 2^{k}χ(A, 2^{k}m).  (1.19)

If n writes n = 2^{k}m with k ≥ 0 and m odd, (1.8) implies

σ(A, n) = σ(A, 2^{k}m) = ∑_{d | m} dS(d, k),  (1.20)

which, by Möbius inversion formula, gives

mS(m, k) = ∑_{d | m} μ(d)σ(A, n/d) = ∑_{d | \overline{m}} μ(d)σ(A, n/d),  (1.21)

where \overline{m} = ∏_{p | m} p denotes the radical of m. In the above sums, n/d is

always a multiple of 2^{k}, so that, from (1.10) , the value of σ(A, n/d) and thus the value of S(m, k) are known modulo 2^{k+1}. Therefore, from (1.19), we can deduce the value of χ(A, 2^{i}m) for i ≤ k.

In Section 4, by the above described method, the multiplicative structure of the elements of A = A_{0}({1, 2, 3}, 3) will be given (Theorem 2), with the surprising property that, for this set A, the 2-adic expansion :

1 + 2χ(A, 2) + 4χ(A, 4) + … + 2^{k}χ(A, 2^{k}) + …  (1.22)

is one of the 2-adic roots of the equation x^{2} − x + 2 = 0. From Theorem 2, and from an extension of the so-called Selberg-Delange formula given in [4], we shall give in Section 5 (Theorem 3) an asymptotic estimation for A(x) :

A(x) ∼ c\frac{x}{(log x)^{3/4}} , x → ∞  (1.23)

where c is a constant the value of which is approximately 0.937.

The work done in Sections 3 and 4 for the set A = A_{0}({1, 2, 3}, 3) could be done, in principle, for any set A = A_{i}(B, N). But, for technical reasons, the calculation can be difficult. We hope to return to this subject in an other article.

We are pleased to thank M. Deléglise for computing the values of A(x) (cf. Section 5), D. Barsky, K. Belabas and A. Sárközy for several remarks.

2 The Graeffe transformation.

Let us consider the ring of formal power series ℂ[[z]]. For an element

f(z) = a_{0} + a_{1}z + a_{2}z^{2} + … + a_{n}z^{n} + …

of this ring, the product

f(z)f(−z) = b_{0} + b_{1}z^{2} + b_{2}z^{4} + … + b_{n}z^{2n} + …

is an even power series with

b_{0} = a_{0}^{2}, b_{1} = 2a_{0}a_{2} − a_{1}^{2}, …, b_{n} = 2 (∑_{i=0}^{n−1}(−1)^{i}a_{i}a_{2n−i}) + (−1)^{n}a_{n}^{2}. (2.1)

We shall call g = G(f) the series

g(z) = G(f)(z) = b_{0} + b_{1}z + b_{2}z^{2} + … + b_{n}z^{n} + ….  (2.2)

Note that we have

g(z^{2}) = G(f)(z^{2}) = f(z)f(−z).  (2.3)

Example. If q is an odd integer and f(z) = 1 − z^{q}, we have f(z)f(−z) = (1 − z^{q})(1 + z^{q}) = 1 − z^{2q}, and

G(f) = f.  (2.4)

If f is a polynomial of degree n which does not vanish in 0, and if f̃(z) = z^{n}f(1/z) is the reciprocal polynomial of f, then we have

G(f̃) = (−1)^{n}{ \atop G(f)}.  (2.5)

It is obvious that, for any two series f and g, the formulas

G(fg) = G(f)G(g)  (2.6)

and, if g(0) = 1,

G(f/g) = G(f)/G(g)  (2.7)

hold. We shall often use the following notation for the iterates of f by the transformation G :

f_{0} = f, f_{1} = G(f), f_{2} = G(f_{1}), …, f_{k} = G(f_{k−1}) = G^{(k)}(f), … (2.8)

Proposition 1. Let f be a polynomial of degree n whose roots are z_{1}, z_{2}, …, z_{n} and leading coefficient is a_{n}. Then the polynomial g = G(f), where G is defined by (2.2), has a leading coefficient equal to (−1)^{n}a_{n}^{2} and its roots are z_{1}^{2}, z_{2}^{2}, …, z_{n}^{2}.

Proof. From the relations

f(z) = a_{n}(z − z_{1})(z − z_{2}) … (z − z_{n})

and

f(−z) = a_{n}(−z − z_{1})(−z − z_{2}) … (−z − z_{n})

it follows that

f(z)f(−z) = (−1)^{n}a_{n}^{2}(z^{2} − z_{1}^{2})(z^{2} − z_{2}^{2}) … (z^{2} − z_{n}^{2})

and therefore, from (2.3)

g(z) = G(f)(z) = (−1)^{n}a_{n}^{2}(z − z_{1}^{2})(z − z_{2}^{2}) … (z − z_{n}^{2}),  (2.9)

which completes the proof of Proposition 1. □

In numerical analysis (cf. [8], [2] or [16]), the Graeffe method is used to compute an approximate value of the roots of a polynomial equation f(x) = 0. The first step of the method is to calculate f_{k} defined by (2.8) for k large enough. From Proposition 1, the roots of f_{k} are z_{1}^{2^{k}}, …, z_{n}^{2^{k}}, and, if we assume that |z_{1}| > |z_{2}| > … > |z_{n}|, the sum of the roots of f_{k} is close to z_{1}^{2^{k}} which yields an approximate value for |z_{1}|. This old method is being revisited in the frame of computer algebra (cf. [7]).

Proposition 2. Let f(z) ∈ ℂ[[z]], f(0) ≠ 0,and

z \frac{f′(z)}{f(z)} = ∑_{n=1}^{∞} a_{n}z^{n}.  (2.10)

Then, for k ≥ 1, we have

∑_{n=1}^{∞} a_{2^{k}n}z^{n} = z \frac{f′_{k}(z)}{f_{k}(z)} = \frac{z}{f_{k}(z)} \frac{d}{dz} f_{k}(z),  (2.11)

where f_{k} = G^{(k)}(f) is defined by (2.2) and (2.8).

Remark 2. Here and in the sequence, f′_{k} will denote the derivative of f_{k} (and not the k-iterate of f′).

Proof. We shall prove Proposition 2 by induction on k. For k = 1 and z = y^{2}, we have from (2.10) and (2.3)

∑_{n=1}^{∞} a_{2n}z^{n} = ∑_{n=1}^{∞} a_{2n}y^{2n} = \frac{1}{2} ∑_{n=1}^{∞}(a_{n}y^{n} + a_{n}(−y)^{n})

= \frac{1}{2} (y \frac{f′(y)}{f(y)} − y \frac{f′(−y)}{f(−y)}) = \frac{y}{2} \frac{f′(y)f(−y) − f(y)f′(−y)}{f(y)f(−y)}
= \frac{y}{2f_{1}(y^{2})} \frac{d}{dy} f_{1}(y^{2}) = z \frac{f′_{1}(z)}{f_{1}(z)}.  (2.12)

Further, the induction on k is easy, by substituting a_{2^{k}n} to a_{2n} and f_{k−1} to f in (2.12). □

Definition 2. We shall say that two power series f, g with integral coefficients are congruent modulo M (where M is any positive integer) if their coefficients of same degree are congruent modulo M. In other words, if

f(z) = a_{0} + a_{1}z + a_{2}z^{2} + … + a_{n}z^{n} + … ∈ ℤ[[z]]

and

g(z) = b_{0} + b_{1}z + b_{2}z^{2} + … + b_{n}z^{n} + … ∈ ℤ[[z]]

then,

f ≡ g (mod M) ⟺ ∀n ≥ 0, a_{n} ≡ b_{n} (mod M).  (2.13)

Congruences of formal power series may be added or multiplied. If

f ≡ g (mod M)  (2.14)

and

u ≡ v (mod M), u ∈ ℤ[[z]], v ∈ ℤ[[z]]

then

f + u ≡ g + v (mod M) and fu ≡ gv (mod M).  (2.15)

You may derivate (2.14) and get

f′ ≡ g′ (mod M).  (2.16)

Moreover, if f(0) = g(0) = 1, 1/f and 1/g have integer coefficients and we have, if (2.14) holds

\frac{1}{f} ≡ \frac{1}{g} (mod M).  (2.17)

It is also easy to see that, for f ∈ ℤ[[z]] and G defined by (2.2) we have

G(f) ≡ f (mod 2).  (2.18)

Proposition 3. Let f and g be two formal power series with integral coefficients such that f ≡ g (mod 2). Then, for k ≥ 0, we have

f_{k} ≡ g_{k} (mod 2^{k+1}),  (2.19)

where f_{k} = G^{(k)}(f) and g_{k} = G^{(k)}(g) are defined by (2.2) and (2.8).

Proof. Let us start by proving that if u, v ∈ ℤ[[z]] satisfy

u ≡ v (mod 2M)  (2.20)

where M is any positive integer, then u_{1} = G(u) and v_{1} = G(v) satisfy

u_{1} ≡ v_{1} (mod 4M).  (2.21)

It follows from (2.20) that there exists w ∈ ℤ[[z]] such that

u(z) = v(z) + 2Mw(z).

Further, from (2.3)

u_{1}(z^{2}) = u(z)u(−z) = (v(z) + 2Mw(z))(v(−z) + 2Mw(−z))
= v_{1}(z^{2}) + 2M[v(z)w(−z) + w(z)v(−z)] + 4M^{2}w_{1}(z^{2}),

where w_{1} = G(w). But the above bracket is obviously congruent to 0 modulo 2 so that

u_{1}(z^{2}) ≡ v_{1}(z^{2}) (mod 4M)

which, by substituting z to z^{2}, yields (2.21).

We shall prove Proposition 3 by induction on k. For k = 0, from (2.8), (2.19) is just our hypothesis f ≡ g (mod 2). Let us assume that (2.19) holds for a non negative value of k; then applying (2.21) with u = f_{k}, v = g_{k} and M = 2^{k} will give

f_{k+1} ≡ g_{k+1} (mod 2^{k+2})

and the proof of Proposition 3 is completed. □

3 The set A = A_{0}({1, 2, 3}, 3).

In all this Section, A will denote the set A_{0}({1, 2, 3}, 3) ; we shall write p(n), σ(n), χ(n) instead of p(A, n), σ(A, n), χ(A, n) respectively. We shall recall in Lemma 1 some classical results on congruences modulo 2^{k}.

Lemma 1. Let a, b and c be integers.

(i) If a is odd and k ≥ 3, the congruence

x^{2} ≡ a (mod 2^{k})  (3.1)

has no solution if a ≢ 1 (mod 8), and has four solutions if a ≡ 1 (mod 8). Two of them satisfy

x^{2} ≡ a (mod 2^{k+1}).  (3.2)

If ρ_{k} is a solution of (3.1) which satisfies (3.2) then the four solutions of (3.1) are ±ρ_{k} and ±ρ_{k} + 2^{k−1}. By the method of Hensel, ρ_{k} can be calculated by induction : if ρ_{k}^{2} ≡ a + ε2^{k+1} (mod 2^{k+2}), ε ∈ {0, 1}, then ρ_{k+1} = ρ_{k} + ε2^{k+1}.

(ii) the congruence

x^{2} − x + a ≡ 0 (mod 2^{k})  (3.3)

has no solution if a is odd ; if a is even, it has two solutions, one is even and the other one is odd. They can be calculated by Hensel’s method : if τ_{k} satisfies (3.3), then τ_{k+1} = τ_{k} + ε2^{k} is determined from

ε ≡ \frac{τ_{k}^{2} − τ_{k} + a}{2^{k}} (mod 2).  (3.4)

(iii) Any congruence x^{2} + bx + c ≡ 0 (mod 2^{k}) can be put on the form (3.1) or (3.3) after a change of variable y = x + ⌊b/2⌋.

(iv) In the 2-adic field ℚ_{2}, the equation x^{2} − a = 0 has two roots if and only if a ≡ 1 (mod 8). If x_{1} and x_{2} are the two solutions, we have x_{i} ≡ ±ρ_{k} (mod 2^{k}).

(v) In the 2-adic field ℚ_{2}, the equation x^{2} − x + a = 0 has two roots x_{1} and x_{2} if and only if a is even. Moreover, x_{i} mod 2^{k} are solutions of (3.3).

Proof of (i). It is a classical result that each odd residue class modulo 2^{k} for k ≥ 3 can be written ±5^{λ} with 0 ≤ λ < 2^{k−2}. From this result, it is not difficult to prove (i). We may observe that, if ρ is a solution of (3.2),

(±ρ + 2^{k−1})^{2} ≡ a + 2^{k} (mod 2^{k+1})

so that ±ρ + 2^{k−1} are solutions of (3.1) but not of (3.2).

The Hensel method can be found in [1] or [10]. It can be accelerated to calculate ρ_{k+1}, …, ρ_{2k−1} in terms of ρ_{k}.

Proof of (ii). If τ_{k} is a solution of (3.3), τ_{k} mod 2 is a solution of x^{2} − x+a ≡ 0 (mod 2). But if a is odd this last congruence has no solution while, if a is even, it has two solutions 0 and 1. Both can be extended to solutions of (3.3), by using (3.4) with k = 1, 2, . . ..

An other possibility to solve (3.3) is to set y = 2x − 1. We have y^{2} = 4x^{2}−4x+1 ≡ 1−4a (mod 2^{k+2}). But the four solutions of this last congruence give only two solutions to (3.3).

Since the sum of the two roots is 1 they must have a different parity. To show (3.4), we calculate

(τ_{k} + ε2^{k})^{2} − (τ_{k} + ε2^{k}) + a ≡ τ_{k}^{2} − τ_{k} + a − ε2^{k} (mod 2^{k+1}).

Proof of (iii). It is obvious.

Proof of (iv). If

x_{1} = ε_{0} + ε_{1}2 + ε_{2}2^{2} + … + ε_{k}2^{k} + …

is a 2-adic solution of x^{2} − a = 0, then, by writing x_{1} = U_{k} + 2^{k}R_{k}, we have U_{k} = x_{1} mod 2^{k} and x_{1}^{2} = a ≡ U_{k}^{2} (mod 2^{k+1}), so that U_{k} satisfies (3.1) and (3.2) and thus, from (i), U_{k} = ±ρ_{k}. In the other way, by the Hensel method, each root of (3.1) satisfying (3.2) can be extended in a 2-adic solution.

Proof of (v). The proof of (v) looks like the one of (iv), but it is easier since (3.3) has only two solutions while (3.1) has four solutions, and the proof of Lemma 1 is completed. □

Theorem 1. Let A = A_{0}({1, 2, 3}, 3). Then :

(i) For all k ≥ 0, the sequence σ(2^{k}n) mod 2^{k+1} is periodic in n with period q_{k} = 7.

(ii) If u_{k} = σ(2^{k}) mod 2^{k+1} and v_{k} = σ(3.2^{k}) mod 2^{k+1} then

σ(2^{k}n) ≡ u_{k}, v_{k}, −3 (mod 2^{k+1}), respectively as (\frac{n}{7}) = 1, −1, 0. (3.5)

where (\frac{n}{7}) is the Legendre symbol.

(iii) u_{k} and v_{k} are the two solutions of the congruence

x^{2} − x + 2 ≡ 0 (mod 2^{k+1})  (3.6)

and satisfy

u_{k} + v_{k} ≡ 1 (mod 2^{k+1}) and u_{k} · v_{k} ≡ 2 (mod 2^{k+1}).  (3.7)

Moreover, if k ≥ r,

u_{k} ≡ u_{r} (mod 2^{r+1}).  (3.8)

(iv) The equation

x^{2} − x + 2 = 0  (3.9)

has two solutions in the 2-adic field ℚ_{2} ; the odd one is

x_{1} = 1 + 2 + 2^{3} + 2^{4} + 2^{6} + 2^{13} + 2^{14} + 2^{18} + 2^{19} + 2^{22} + 2^{25} + …. (3.10)

We have

u_{k} ≡ x_{1} (mod 2^{k+1}) .  (3.11)

Moreover, the elements of A which are powers of 2 are 1, 2, 2^{3}, 2^{4}, 2^{6}, 2^{13}, …; they are determined by

x_{1} = ∑_{k=0}^{∞} χ(2^{k})2^{k}.  (3.12)

Proof of (i). The polynomial P defined by (1.11) and (1.12) is

P (z) = 1 + z + z^{3}  (3.13)

since p(0) = 1, p(1) = 1, p(2) = 2 and p(3) = 3. It is irreducible over 𝔽_{2}[z] so that, in (1.13), s = 1 and Q_{1} = P. So, it follows from Theorem A that β_{1} = 7 and q_{k} = 7 for all k ≥ 0, which proves (i).

Proof of (ii). We shall denote by H the other irreducible polynomial of degree 3 over 𝔽_{2}[z],

H(z) = 1 + z^{2} + z^{3}.  (3.14)

From (2.8) and Proposition 1, the leading coefficient of P_{k} = G^{(k)}(P) is −1, and from (2.2), (1.2), (1.11) and (1.12)

P_{k}(0) = 1  (3.15)

so that we can write

P_{k}(z) = G^{(k)}(P)(z) = 1 + a_{k}z + b_{k}z^{2} − z^{3}.  (3.16)

Now, we observe that, from (3.13) and (3.14) the polynomials P and H are reciprocal. So, from (3.16) and (2.5) we have

H_{k}(z) = G^{(k)}(H)(z) = 1 − b_{k}z − a_{k}z^{2} − z^{3}.  (3.17)

But we have

\frac{1 − z^{7}}{1 − z} = 1 + z + z^{2} + z^{3} + z^{4} + z^{5} + z^{6} ≡ P (z)H(z) (mod 2), (3.18)

and this implies, from (2.7), (2.4), (2.6) and Proposition 3 that

\frac{1 − z^{7}}{1 − z} = 1 + z + z^{2} + z^{3} + z^{4} + z^{5} + z^{6} ≡ P_{k}(z)H_{k}(z) (mod 2^{k+1}).  (3.19)

By expanding the product P_{k}H_{k} from (3.16) and (3.17), we get from (3.19)

a_{k} − b_{k} ≡ 1 (mod 2^{k+1}) and a_{k} · b_{k} ≡ −2 (mod 2^{k+1}).  (3.20)

By applying Proposition 2 to (1.9) (where F (z) = F_{A}(z) is defined by (1.3), we get :

∑_{n=1}^{∞} σ(2^{k}n)z^{n} = z \frac{F′_{k}(z)}{F_{k}(z)}  (3.21)

where F_{k} is the k-iterate of F by the transformation G (cf. (2.8)), and F′_{k} =

\frac{d}{dz} (F_{k}(z)). It follows from (1.3), (1.4), (1.11) and (1.12) that

F ≡ P (mod 2)  (3.22)

and Proposition 3 implies that

F_{k} ≡ P_{k} (mod 2^{k+1})  (3.23)

for all k ≥ 0. We deduce from (3.15) and (3.23) that

F_{k}(0) = P_{k}(0) = 1  (3.24)

and thus, from (2.15), (2.16) and (2.17), (3.23) implies

z \frac{F′_{k}(z)}{F_{k}(z)} ≡ z \frac{P′_{k}(z)}{P_{k}(z)} (mod 2^{k+1}).  (3.25)

Therefore, from (3.21) and (3.25), it follows :

∑_{n=1}^{∞} σ(2^{k}n)z^{n} ≡ z \frac{P′_{k}(z)}{P_{k}(z)} (mod 2^{k+1}).  (3.26)

From (3.26) and (3.19), we have

∑_{n=1}^{∞} σ(2^{k}n)z^{n} ≡ z \frac{P′_{k}(z)}{P_{k}(z)} ≡ z \frac{(1 − z)P′_{k}(z)H_{k}(z)}{1 − z^{7}} (mod 2^{k+1}).  (3.27)

The expansion of the numerator of the right hand side of (3.27) from (3.16), (3.17) and (3.20) yields

z(1 − z)P′_{k}(z)H_{k}(z) ≡  (3.28)
a_{k}z + a_{k}z^{2} − b_{k}z^{3} + a_{k}z^{4} − b_{k}z^{5} − b_{k}z^{6} − 3z^{7} (mod 2^{k+1}).

By expanding the denominator of the right hand side of (3.27) :\frac{1}{1 − z^{7}} =

1 + z^{7} + z^{14} + …, it follows from (3.27) and (3.28) that

\begin{matrix}σ(2^{k}n) ≡ & a_{k} & a_{k} & −b_{k} & a_{k} & −b_{k} & −b_{k} & −3 (mod 2^{k+1}) \\ resp. as n ≡ & 1 & 2 & 3 & 4 & 5 & 6 & 0 (mod 7). \end{matrix} \} (3.29)

The congruences (3.29) give for n = 1 and n = 3

u_{k} = σ(2^{k}) ≡ a_{k} (mod 2^{k+1}) and v_{k} ≡ σ(3 · 2^{k}) ≡ −b_{k} (mod 2^{k+1}). (3.30)

Since the quadratic residue classes modulo 7 are 1, 2 and 4, (3.29) and (3.30) prove (ii).

Proof of (iii). Formula (3.7) follows from (3.20) and (3.30), and yields u_{k}(1 − u_{k}) ≡ 2 (mod 2^{k+1}) ; so, u_{k} is a solution of the congruence (3.6). By the same way v_{k} can be proved to be also a solution of (3.6).

Finally, if k ≥ r,

u_{k} = σ(2^{k}) = u_{r} + ∑_{j=r+1}^{k} χ(2^{j})2^{j} ≡ u_{r} (mod 2^{r+1}),

which shows (3.8) and completes the proof of (iii).

Proof of (iv). Note that u_{k} = σ(2^{k}) is odd (since 1 ∈ A) while v_{k} is even (since 1, 3 ∈ A). Since its discriminant −7 is congruent to 1 modulo 8 (cf. Lemma 1), the equation (3.9) has two roots in ℚ_{2}, x_{1} ≡ 1 (mod 2) and x_{2} ≡ 0 (mod 2). Moreover, x_{1} mod 2^{k+1} is solution of (3.6), and as it is smaller than 2^{k+1} (like u_{k}) it is equal to u_{k} (because u_{k} ≡ 1 (mod 2)) and so, (3.11) is proved. Similarly, v_{k} = x_{2} mod 2^{k+1}.

The expansion (3.10) has been calculated with the function polrootspadic of PARI. The expansion of x_{2} is

x_{2} = 2 + 2^{2} + 2^{5} + 2^{7} + 2^{8} + 2^{9} + 2^{10} + 2^{11} + 2^{12} + 2^{15} + 2^{16} + …. (3.31)

At the exception of 2^{1}, the powers of 2 appear either in x_{1} or in x_{2} ; the reason is that

x_{1} + x_{2} = 1 = 2 + \frac{1}{1 − 2} = 2 + ∑_{n=0}^{∞} 2^{n}.

Since u_{k} has been defined as equal to σ(2^{k}) = ∑_{i=0}^{k} χ(2^{i})2^{i}, (3.12) follows from

(3.11) and this completes the proof of Theorem 1. □

Numerical table

\begin{matrix}k = & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ u_{k} = & 1 & 3 & 3 & 11 & 27 & 27 & 91 & 91 & 91 & 91 & 91 & 91 & 91 & 8283 \\ v_{k} = & 0 & 2 & 6 & 6 & 6 & 38 & 38 & 166 & 422 & 934 & 1958 & 4006 & 8102 & 8102 \end{matrix}

4 The elements of A = A_{0}({1, 2, 3}, 3).

Let us define two classical arithmetic functions. If n is a positive integer, ω(n) will denote the number of distinct primes dividing n while Ω(n) will be the number of primes dividing n according to multiplicity. We are now ready to state Theorem 2 which gives the multiplicative structure of the elements of A.

Theorem 2. Let A = A_{0}({1, 2, 3}, 3). Then :

(i) The elements of A of the form 2^{k} are determined by Theorem 1 (iv). Similarly, the elements of A of the form 7 · 2^{k} are determined by the even solution x_{7} of the 2-adic equation 7x^{2} + 7x + 2 = 0

x_{7} = ∑_{k=0}^{∞} χ(7 · 2^{k})2^{k}  (4.1)
= 2 + 2^{2} + 2^{3} + 2^{6} + 2^{7} + 2^{9} + 2^{10} + 2^{12} + 2^{16} + 2^{18} + 2^{20} + 2^{21} + …

(ii) Let p be an odd prime congruent to 1, 2 or 4 modulo 7 (i.e.,(\frac{p}{7}) = 1). Then (p, a) = 1 for all a ∈ A.

(iii) If n ∈ ℕ and 49 divides n, then n ∉ A.

(iv) Let n = 2^{k}m, and

m = p_{1}^{λ_{1}}p_{2}^{λ_{2}} … p_{h}^{λ_{h}}  (4.2)

where p_{i} are primes, distinct and congruent to 3, 5 or 6 modulo 7 and λ_{i} are positive integers. We assume that h = ω(m) ≥ 1 (i.e. m ≠ 1) and recall that Ω(m) = λ_{1} + … + λ_{h}.

• (a) If k ≤ h − 2, then n ∉ A and 7n ∉ A.

• (b) If k = h − 1, then, without any restriction, n ∈ A and 7n ∈ A.

• (c) If k = h − 1 + r, with r ≥ 1, then n ∈ A if and only if

m ≡ (−1)^{Ω(m)}(1 − 2u_{r})ℓ^{−1} (mod 2^{r+1}), ℓ = 1, 3, 5, …, 2^{r} − 1. (4.3)

Moreover, the expansion

x_{m} = 1 + χ(2^{h}m)2 + χ(2^{h+1}m)2^{2} + … + χ(2^{h+j}m)2^{j+1} + …  (4.4)

is one of the two 2-adic solutions of the equation

m^{2}x^{2} + 7 = 0.  (4.5)

• (d) If k = h − 1 + r, with r ≥ 1, then 7n ∈ A if and only if

m ≡ (−1)^{Ω(m)}(2u_{r} − 1)7^{−1}ℓ^{−1} (mod 2^{r+1}), ℓ = 1, 3, 5, …, 2^{r} − 1. (4.6)

Moreover, the expansion

x_{7,m} = 1 + χ(7 · 2^{h}m)2 + … + χ(7 · 2^{h+j}m)2^{j+1} + …  (4.7)

is one of the two 2-adic solutions of the equation

7m^{2}x^{2} + 1 = 0.  (4.8)

We may observe that for k = 0, 1, 2, we have for m odd, m ≠ 1

n = 2^{k}m ∈ A ⟺ 7n = 7 · 2^{k}m ∈ A.  (4.9)

Remark 3. Theorem 2 has been proved for k = 0 in [12] and for k = 1 in [3].

Proof of (i). From (1.19), we have

S(7, k) = χ(7) + χ(7 · 2)2 + … + χ(7 · 2^{k})2^{k}  (4.10)

and by (1.21) and (3.5)

7S(7, k) = ∑_{d | 7} μ(d)σ (\frac{7 · 2^{k}}{d} )
= σ(7 · 2^{k}) − σ(2^{k}) ≡ −3 − u_{k} (mod 2^{k+1}), (4.11)

so that S(7, k) ≡ (−3 − u_{k})7^{−1} (mod 2^{k+1}). Since, from Theorem 1 (iii), u_{k} is solution of (3.6), a simple calculation shows that S(7, k) is a solution of 7x^{2} + 7x + 2 ≡ 0 (mod 2^{k+1}). From (3.5), σ(7) = 1 + 7χ(7) ≡ −3 (mod 2) so that χ(7) = 0 and, from (4.10), S(7, k) is even, which proves (i).

Proof of (ii). Let us suppose that n = 2^{k}m ∈ A, m odd and multiple of a prime p ≡ 1, 2, 4 (mod 7). Here we have from (1.19)

S(m, k) = χ(m) + χ(2m)2 + … + χ(2^{k}m)2^{k} < 2^{k+1}.  (4.12)

We get from (1.21)

mS(m, k) = ∑_{d | \overline{m}} μ(d)σ (\frac{n}{d}) = ∑_{d | (\overline{m}/p)} μ(d) [σ (\frac{n}{d}) − σ (\frac{n}{pd})] . (4.13)

But, from (3.5), the above bracket is congruent to 0 modulo 2^{k+1}, since

(\frac{n/d}{7}) = (\frac{n/pd}{7})×(\frac{p}{7}) = (\frac{n/pd}{7}). This implies that S(m, k) is congruent

to 0 modulo 2^{k+1}, and as 0 ≤ S(m, k) < 2^{k+1}, S(m, k) vanishes and, from (4.12), χ(n) = χ(2^{k}m) also vanishes which proves (ii).

Proof of (iii). Let us now suppose that n = 2^{k}m ∈ A, m odd and multiple of 49. If we define S(m, k) by (4.12), (4.13) still holds if we replace p by 7. Now, in the bracket, both \frac{n}{d} and \frac{n}{7d} are multiple of 7, so that, from (3.5), again the bracket is congruent to 0 modulo 2^{k+1}. The proof of (iii) ends in the same terms than the one of (ii) above.

Proof of (iv). We shall need the following lemma :

Lemma 2. With m, n, h, k as in Theorem 2 (iv), u_{k} as defined in Theorem 1, S(m, k) as defined by (4.12) (or 1.19), we have

mS(m, k) ≡ 2^{h−1}(2u_{k} − 1)(−1)^{Ω(m)} (mod 2^{k+1}),  (4.14)

and

7mS(7m, k) ≡ −2^{h−1}(2u_{k} − 1)(−1)^{Ω(m)} (mod 2^{k+1}).  (4.15)

Proof of Lemma 2. With n = 2^{k}m, we have from (1.21),

mS(m, k) = ∑_{d | \overline{m}} μ(d)σ (\frac{n}{d}) = ∑_{\begin{matrix}d | \overline{m} \\ μ(d)=1 \end{matrix}} σ (\frac{n}{d}) − ∑_{\begin{matrix}d | \overline{m} \\ μ(d)=−1 \end{matrix}} σ (\frac{n}{d})  (4.16)

with \overline{m} = p_{1} … p_{h}. Since (\frac{2}{7}) = 1 and (\frac{p_{i}}{7} ) = −1, we have

(\frac{n}{7}) = (−1)^{Ω(m)} and (\frac{n/d}{7}) = (−1)^{Ω(m)}μ(d).

Let us assume that Ω(m) is even ; then we get from (4.16) and (3.5)

mS(m, k) ≡ u_{k} ( ∑_{\begin{matrix}d | \overline{m} \\ μ(d)=1 \end{matrix}} 1) − v_{k} ( ∑_{\begin{matrix}d | \overline{m} \\ μ(d)=−1 \end{matrix}} 1) (mod 2^{k+1}).  (4.17)

The first (resp. second) sum is the number of subsets of {1, 2, …, h} with an even (resp. odd) cardinal ; they are both equal to 2^{h−1} (since h ≥ 1), and from (3.7), (4.17) yields

mS(m, k) ≡ 2^{h−1}(2u_{k} − 1) (mod 2^{k+1}).  (4.18)

If Ω(m) is odd, the same calculation leads to a formula looking like (4.18) where (2u_{k} − 1) is replaced by (1 − 2u_{k}) so that, in both cases, (4.14) is proved.

With n still being equal to 2^{k}m, we have from (1.21)

7mS(7m, k) = ∑_{d | (7\overline{m})} μ(d)σ (\frac{7n}{d}) =∑_{d | \overline{m}} μ(d)σ (\frac{7n}{d})−∑_{d | \overline{m}} μ(d)σ (\frac{n}{d}) . (4.19)

But, 7n/d ≡ 0 (mod 7) so that, by (3.5), σ (\frac{7n}{d}) ≡ −3 (mod 2^{k+1}) and

since \overline{m} ≠ 1, ∑_{d | \overline{m}} μ(d) = 0. Therefore, it follows from (4.19) and (4.16) that

7mS(7m, k) ≡ − ∑_{d | \overline{m}} μ(d)σ (\frac{n}{d}) ≡ −mS(m, k) (mod 2^{k+1}),  (4.20)

which, together with (4.14) proves (4.15). □

Let us prove now Theorem 2 (iv) :

Proof of (iv) (a). If k ≤ h − 2, it follows from Lemma 2 (4.14) that

S(m, k) ≡ 0 (mod 2^{k+1}).

From (4.12), this implies S(m, k) = 0 (since 0 ≤ S(m, k) < 2^{k+1}), and, therefore, χ(n) = χ(2^{k}n) = 0, i.e. n ∉ A.

By using (4.15) instead of (4.14), it can be proved in the same way that χ(7n) = 0, i.e. 7n ∉ A.

Proof of (iv) (b). If k = h − 1, (4.14) writes

mS(m, k) ≡ 2^{k}(2u_{k} − 1)(−1)^{Ω(m)} (mod 2^{k+1})  (4.21)

so that S(m, k) is a multiple of 2^{k}, and, by dividing (4.21) by 2^{k}, S(m, k)/2^{k} is odd. But then, from (4.12), S(m, k) = 2^{k}χ(2^{k}m) = 2^{k}χ(n) and thus χ(n) = 1 and n ∈ A. A similar proof shows that 7n ∈ A.

Proof of (iv) (c). It follows from (4.14) that S(m, k) is a multiple of 2^{h−1} and by dividing (4.14) by 2^{h−1} and using (3.8), we get

m\frac{S(m, k)}{2^{h−1}} ≡ (2u_{k} − 1)(−1)^{Ω(m)} ≡ (2u_{r} − 1)(−1)^{Ω(m)} (mod 2^{r+1}). (4.22)

But, from (4.12), we have

\frac{S(m, k)}{2^{h−1}} = 1 + χ(2^{h}m)2 + … + χ(2^{k}m)2^{r},  (4.23)

since, by (b), χ(2^{h−1}m) = 1. Let x be the solution of the congruence

mx ≡ −(2u_{r} − 1)(−1)^{Ω(m)} (mod 2^{r+1}),  (4.24)

satisfying 0 ≤ x < 2^{r+1} ; then, from (4.22), 2^{r+1} − x is equal to \frac{S(m, r)}{2^{h−1}}. So,

if x < 2^{r}, it follows from (4.23) that χ(n) = χ(2^{k}m) = 1 while, if x > 2^{r}, χ(n) = 0.

Since u_{k} satisfies (3.6),

((2u_{r} − 1)(−1)^{Ω(m)})^{2} = 4u_{r}^{2} − 4u_{r} + 1 ≡ −7 (mod 2^{r+3})  (4.25)

and, so, from (4.22), \frac{S(m, r)}{2^{h−1}} is a solution of m^{2}x^{2} + 7 ≡ 0 (mod 2^{r+3}), and thus, from (4.23) and Lemma 1, x_{m} is a solution of the 2-adic equation (4.5).

By using (4.3) with r = 1 we know that 2^{h}m ∈ A if and only if m(−1)^{Ω(m)} ≡ 3 (mod 4). Thus

χ(2^{h}m) ≡ \frac{(−1)^{Ω(m)}m − 1}{2} (mod 2)  (4.26)

which allows us to distinguish for x_{m} between the two roots of (4.5).

Proof of (iv) (d). It is the same proof than the proof of (c). We just have to show (4.9), which follows immediately from (4.3) and (4.6) by noting that 7^{−1} ≡ −1 (mod 8). In particular, for r = 1, (4.3) and (4.6) coïncide so that χ(7·2^{h}m) = χ(2^{h}m), and thus, formula (4.26) still holds when replacing χ(2^{h}m) by χ(7 · 2^{h}m). □

If m = p_{1}^{λ_{1}} … p_{h}^{λ_{h}}, for r ≤ 5, (4.3) and (4.6) can be written as

χ(2^{h}m) = χ(7 · 2^{h}m) = 1 ⟺ (−1)^{Ω(m)}m ≡ 3 (mod 4)

χ(2^{h+1}m) = χ(7 · 2^{h+1}m) = 1 ⟺ (−1)^{Ω(m)}m ≡ 1, 3 (mod 8)

χ(2^{h+2}m) = 1 ⟺ (−1)^{Ω(m)}m ≡ 9, 11, 13, 15 (mod 16)
χ(7 · 2^{h+2}m) = 1 ⟺ (−1)^{Ω(m)}m ≡ 1, 3, 5, 7 (mod 16)

χ(2^{h+3}m) = 1 ⟺ (−1)^{Ω(m)}m ≡ 1, 5, 11, 15, 19, 23, 25, 29 (mod 32)

χ(7 · 2^{h+3}m) = 1 ⟺ (−1)^{Ω(m)}m ≡ 1, 3, 5, 7, 9, 11, 13, 15 (mod 32)

χ(2^{h+4}m) = 1 ⟺
(−1)^{Ω(m)}m ≡ 1, 3, 5, 7, 11, 15, 17, 21, 25, 27, 29, 31, 41, 45, 51, 55 (mod 64)
χ(7 · 2^{h+4}m) = 1 ⟺
(−1)^{Ω(m)}m ≡5, 7, 9, 11, 21, 23, 25, 27, 33, 35, 45, 47, 49, 51, 61, 63 (mod 64).

5 Estimation of A(x)

In this Section, we want to estimate A(x) where A will denote the set A_{0}({1, 2, 3}, 3) ; in view of using the description of the elements of A given in Theorem 2, we need some definitions.

Let us denote by F the set of the integers

n = 2^{h}p_{1}^{λ_{1}}p_{2}^{λ_{2}} … p_{h}^{λ_{h}}, h ≥ 1, p_{i} ≡ 3, 5, 6 (mod 7).  (5.1)

The elements of F are

F = {6, 10, 18, 26, 34, 38, 50, 54, 60, 62, 82, 94, …}.  (5.2)

In [4], it has been proved that the asymptotic equivalence

F (x) = |\{n ∈ F; n ≤ x\}| ∼ γ \frac{x}{(log x)^{3/4}}  (5.3)

holds for x → ∞, with

γ = \frac{1}{4Γ(5/4)} (\frac{6}{π\sqrt{7}})^{1/4} γ_{1}  (5.4)

and

γ_{1} = ∏_{p≡3,5,6 (mod 7)} ((1 + \frac{1}{2p − 2}) (1 − \frac{1}{p})^{1/2} (1 − \frac{1}{p^{2}} )^{−1/4}) . (5.5)

Calculating the product (5.5) with the primes up to 100000 yields for γ_{1} the approximate value 1.07517. Note that, with the method described in [6], it is possible to calculate γ_{1} with a very high precision. From Γ(5/4) = 0.906402 and (5.4) the approximate value of γ is

γ = 0.2733.  (5.6)

If δ(n) is the characteristic function of F, the Dirichlet’s series ∑_{n=1}^{∞} \frac{δ(n)}{n^{s}} has

an Eulerian product for ℜs > 1

∑_{n=1}^{∞} \frac{δ(n)}{n^{s}} = ∏_{p≡3,5,6 (mod 7)} (1 + \frac{1}{(2p)^{s}} + \frac{1}{2^{s}p^{2s}} + … + \frac{1}{2^{s}p^{ks}} + …)

= ∏_{p≡3,5,6 (mod 7)} (1 + \frac{1}{2^{s}(p^{s} − 1)}) .  (5.7)

In [4], the proof of (5.3) starts from formula (5.7).

For i = 0 or 1, ℓ odd, and r ≥ 0 we define

F_{i; r, ℓ} = {2^{h}m ∈ F, Ω(m) ≡ i (mod 2), m ≡ ℓ (mod 2^{r+1})}. (5.8)

It has been proved in [4] that for r fixed, and x going to infinity, we have for any i and ℓ

F_{i; r, ℓ}(x) = |\{n ∈ F_{i; r, ℓ} , n ≤ x\}| ∼ \frac{γ}{2^{r+1}} \frac{x}{(log x)^{3/4}} ·  (5.9)

From (5.3), (5.9) and Theorem 2, we shall prove

Theorem 3. Let A = A_{0}({1, 2, 3}, 3). The number A(x) of elements of A up to x satisfies, when x tends to infinity :

A(x) ∼ \frac{24γ}{7} \frac{x}{(log x)^{3/4}}  (5.10)

where γ is defined by (5.4) ; an approximate value of 24γ/7 is 0.937.

Proof. Let A′ be the subset of A whose elements are of the form 2^{k} or 7 · 2^{k}. The number of such elements up to x is clearly

A′(x) = O(log(x)), x → ∞.  (5.11)

Now, it follows from Theorem 2 (i) and (iv) that

A = A′ ∪ ⋃_{r=0}^{∞} (A^{(r)} ∪ A^{(r,7)})  (5.12)

where the elements of A^{(r)} are the n’s, n ∈ A, n = 2^{h−1+r}p_{1}^{λ_{1}} … p_{h}^{λ_{h}} and similarly, the elements of A^{(r,7)} are the n’s, n ∈ A, n = 7 · 2^{h−1+r}p_{1}^{λ_{1}} … p_{h}^{λ_{h}}.

From Theorem 2 (iv) (b) it follows that for r = 0,

A^{(0)} = \frac{1}{2}F and A^{(0)}(x) = F (2x),  (5.13)

and

A^{(0,7)} = \frac{7}{2}F and A^{(0,7)}(x) = F (\frac{2x}{7}) .  (5.14)

In the same way, if a^{−1} denotes an inverse of a modulo 2^{r+1}, Theorem 2 (iv)

(c) and (d) implies for r ≥ 1

A^{(r)}(x) = ∑_{ℓ∈\{1,3,...,2^{r}−1\}}(F_{0; r, (1−2u_{r})ℓ^{−1}} (\frac{x}{2^{r−1}} )+F_{1; r, (2u_{r}−1)ℓ^{−1}} (\frac{x}{2^{r−1}} )) (5.15)

and

A^{(r,7)}(x) = ∑_{ℓ∈\{1,3,...,2^{r}−1\}} F_{0; r, (2u_{r}−1)(7ℓ)^{−1}} (\frac{x}{7 · 2^{r−1}} )
+ ∑_{ℓ∈\{1,3,...,2^{r}−1\}} F_{1; r, (1−2u_{r})(7ℓ)^{−1}} (\frac{x}{7 · 2^{r−1}} ) .  (5.16)

It also follows from Theorem 2 that, for any r ≥ 0, A^{(r)} ⊂ 2^{r−1}F and A^{(r,7)} ⊂ 7 · 2^{r−1}F so that

A^{(r)}(x) ≤ F (\frac{x}{2^{r−1}} ) and A^{(r,7)}(x) ≤ F (\frac{x}{7 · 2^{r−1}} ) ≤ F (\frac{x}{2^{r−1}} ) . (5.17)

Moreover, from (5.3) and (5.2), there exists an absolute constant K such that

F (x) ≤ K \frac{x}{(log x)^{3/4}} for x > 1 and F (x) = 0 for x < 6.  (5.18)

It follows from (5.17) and (5.18) that A^{(r)}(x) = A^{(r,7)}(x) = 0 for r > \frac{log(x/3)}{log 2} so that (5.12) implies

A(x) = A′(x) + ∑_{r=0}^{R′′} (A^{(r)}(x) + A^{(r,7)}(x)) , R′′ = ⌊\frac{log(x/3)}{log 2}⌋ . (5.19)

Now, we cut the sum (5.19) in three parts :

A(x) = A′(x) + ∑_{r=0}^{R} + ∑_{r=R+1}^{R′} + ∑_{r=R′+1}^{R′′} =^{def} A′(x) + S + S′ + S′′,  (5.20)

where R is a large but fixed integer, and R′ is defined by 2^{R′−1} ≤ \sqrt{x} < 2^{R′}. We have from (5.17)

S′′ = ∑_{r=R′+1}^{R′′} (A^{(r)}(x) + A^{(r,7)}(x)) ≤ 2 ∑_{r=R′+1}^{R′′} F (\frac{x}{2^{r−1}} ) ;

and, by observing that, for r ≤ R′′, \frac{x}{2^{r−1}} ≥ 6, we get from (5.18)

S′′ ≤ 2K ∑_{r=R′+1}^{R′′} \frac{x}{(2^{r−1})(log 6)^{3/4}} ≤ \frac{2Kx}{2^{R′−1}} ≤ 4K\sqrt{x}.  (5.21)

Similarly, we get

S′ = ∑_{r=R+1}^{R′} (A^{(r)}(x) + A^{(r,7)}(x)) ≤ 2 ∑_{r=R+1}^{R′} F (\frac{x}{2^{r−1}} )
≤ 2K ∑_{r=R+1}^{R′} \frac{x}{(2^{r−1})(log(x/2^{R′−1}))^{3/4}} ≤ 2K ∑_{r=R+1}^{R′} \frac{x}{2^{r−1}(log \sqrt{x})^{3/4}}
≤ 2^{1+3/4}K \frac{x}{(log x)^{3/4}} ∑_{r=R+1}^{∞} \frac{1}{2^{r−1}} ≤ \frac{8K}{2^{R}} \frac{x}{(log x)^{3/4}} ·  (5.22)

We deduce from (5.15), (5.16) and (5.9) that, for r ≥ 1 and r fixed,

A^{(r)}(x) ∼ \frac{γ}{2^{r}} \frac{x}{(log x)^{3/4}} and A^{(r,7)}(x) ∼ \frac{γ}{7 · 2^{r}} \frac{x}{(log x)^{3/4}} (x → ∞). (5.23)

Since R is fixed, we get from (5.13), (5.14), (5.3) and (5.23) for x tending to infinity

S = A^{(0)}(x) + A^{(0,7)}(x) + ∑_{r=1}^{R} (A^{(r)}(x) + A^{(r,7)}(x))

∼ \frac{8γ}{7} \frac{x}{(log x)^{3/4}} (2 + ∑_{r=1}^{R} \frac{1}{2^{r}} ) = \frac{8γ}{7} (3 − \frac{1}{2^{R}} ) \frac{x}{(log x)^{3/4}} . (5.24)

By making R going to infinity, (5.10) follows from (5.20), (5.11), (5.21), (5.22) and (5.24) and the proof of Theorem 3 is completed. □

The following table has been calculated by M. Deléglise by using the multiplicative structure of the elements of A = A_{0}({1, 2, 3}), 3) given by Theorem 2. The last line is the asymptotic result of Theorem 3.

Numerical table

x  A(x)  A(x) (log x)^{3/4} /x
10^{2}  47  1.48
10^{3}  293  1.25
10^{4}  2 204  1.16
10^{5}  17 604  1.100
10^{6} 148 834  1.066
10^{7} 1 297 167  1.043
10^{8} 11 562 386  1.028
. . . . . . . . . .  …
∞  0.937

References

[1] E.J. Barbeau, Polynomials, Springer-Verlag, 1989.

[2] E.H. Bareiss, Resultant procedure and the mecchanisation of the Graeffe process, Journal of the ACM, 7 (1960), 346-386.

[3] F. Ben saïd, On a conjecture of Nicolas-Sárközy about partitions, to appear in J. Number Theory.

[4] F. Ben saïd et J.-L. Nicolas, Sur une extension de la formule de Selberg-Delange, to be published.

[5] F. Ben saïd et J.-L. Nicolas, Sets of parts such that the partition function is even, submitted to Acta Arithmetica.

[6] H. Cohen, High precision computation of Hardy-Littlewood constants, preprint.

[7] X. Gourdon, Thèse, http ://pauillac.inria.fr/algo/gourdon/thesis /html [8] C.H. Graeffe, Die Auflösung der höheren numerischen Gleichungen, Zu-

rich, 1837.

[9] R. Lidl and H. Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, revised edition, 1994.

[10] M.Mignotte, Mathématiques pour le calcul formel, P.U.F., Paris, 1989 ; english translation : Mathematics for computer algebra, Springer-Verlag, 1992.

[11] J.-L. Nicolas, I.Z. Ruzsa and A. Sárközy, On the parity of additive representation functions, J. Number Theory 73 (1998), 292-317.

[12] J.-L. Nicolas and A. Sárközy, On the parity of generalized partition functions, to appear in the proceedings of the Millennium Conference, Urbana, Illinois, May 2000.

[13] J.-L. Nicolas, On the parity of generalised partition functions II, Periodica Mathematica Hungarica, 43 (2001), 177-189.

[14] K. Ono, Parity of the partition function in arithmetic progressions, J. Reine Angew. Math. 472 (1996), 1-15.

[15] K. Ono, Distribution of the partition function modulo m, Ann. of Math. 151 (2000), 293-307.

[16] A. Ralston and P. Rabinowitz, A first course in numerical analysis, McGraw-Hill, 1978.