Ramanujan J DOI 10.1007/s11139-014-9618-z
On the elements of sets with even partition function N. Baccar
Received: 2 April 2014 / Accepted: 20 July 2014 © Springer Science+Business Media New York 2014
Abstract Let P ∈ F2 [z] such that P(0) = 1 and degree(P) ≥ 1. Nicolas, Ruzsa and that there exists a unique subset A = A(P) of N such that Sárközy proved n ≡ P(z) (mod 2), where p(A, n) is the number of partitions of n p(A, n)z n≥0 with parts in A. Let m be an odd positive integer and let S(A, m) be the 2-adic integer given S(A, m) = χ (A, m) + 2χ (A, 2m) + 4χ (A, 4m) + · · · = ∞ byk the expansion k m), where χ (A, ·) is the characteristic function of the set A. By 2 χ (A, 2 k=0 knowing the expansion S(A, m), one can obtain the elements of the set A of the form 2k m. In this paper, we prove that S(A, m) is an algebraic number. Keywords Partitions · Periodic sequences · Order of a polynomial · Cyclotomic polynomials · Resultant · 2-Adic integers · The Graeffe transformation Mathematics Subject Classification
11P83 · 11B50 · 11D88
1 Introduction Let N be the set of positive integers and let A be a non-empty subset of N. For n ∈ N, a partition of n with parts in A is a finite non-increasing sequence n 1 , n 2 , . . . , n k belonging to A such that n = n1 + n2 + · · · + nk .
N. Baccar (B) Dép. de Math Inf., Université de Sousse ISITCOM Hammam Sousse, 5 Bis Rue 1 Juin 1955, 4011 Hammam Sousse, Tunisia e-mail:
[email protected]
123
N. Baccar
The number of partitions of n with parts in A is denoted by p(A, n) with p(A, 0) = 1. The set A is called an even partition set if the sequence ( p(A, n))n≥0 is even from a certain point on. Let F2 be the field with two elements and let P be a polynomial of positive degree in F2 [z] such that P(0) = 1. Nicolas, Ruzsa and Sárközy(see [16]) proved that there is a unique even partition set A = A(P) satisfying the congruence
p(A, n)z n ≡ P(z)
(mod 2).
(1.1)
n≥0
Two issues arise in the study of such sets: a qualitative aspect which deals with the question whether a positive integer n is in A or not? and a quantitative aspect, whose purpose is the asymptotic study of the counting function of the set A = A(P); that is, the function A(P, x) defined by A(P, x) = |{n ∈ A : n ≤ x}|. From now on, for any odd positive integer d, we write s(d) for the order of 2 modulo d; that is, s(d) is the smallest positive integer such that 2s(d) ≡ 1 (mod d). We also use r (d) to denote the positive integer satisfying ϕ(d) = s(d)r (d), where ϕ is Euler’s function. In [9], [10] and [17], the authors determined the elements of the set A(P), when P(z) = 1+z +z 3 +z 4 +z 5 and P(z) = 1+z +z 3 . They obtained asymptotic formulas for the related counting function. This was generalized in [3] for irreducible P with prime order p. Here, the order of a polynomial P is the smallest positive integer w such that P(z) divides 1 + z w in F2 [z]. Let the factorization of P into irreducible factors over F2 [z] be P = Q α1 1 Q α2 2 · · · Q αt t . We denote by P ∗ the squarefree kernel of P; that is, P ∗ = Q 1 Q 2 · · · Q t the product of the distinct irreducible polynomials dividing P. In [11], F. Ben Saïd et al proved that the counting function A(P, x) of the set A(P) satisfies A(P, x) x(log x)
1 − r (β)
,
where β is the order of P ∗ . In [8], Ben Saïd and Nicolas improved on the constant c = c(β) for which A(P, x) x(log x)−c . Let m be an odd positive integer. By χ (A, n), we denote the characteristic function of the set A = A(P); that is, we put χ (A, n) = 1 if n ∈ A and zero otherwise. We
123
Set elements with even partition function
define the 2-adic integer S(A, m) by the expansion S(A, m) = χ (A, m) + 2χ (A, 2m)+4χ (A, 4m) + · · · =
∞
2k χ (A, 2k m).
(1.2)
k=0
By knowing S(A, m) modulo 2k+1 , we can deduce the values of χ (A, 2i m) for all i, i ≤ k. This may explain the importance of such expansion in the study of the sets A(P), since S(A, m) gives a complete description of the elements of the set A(P) of the form 2k m. The aim of the present paper is to prove the following theorem: Theorem 1.1 Let P ∈ F2 [z] be a polynomial of positive degree with P(0) = 1 and A(P) be the set satisfying (1.1). Then, for all odd positive integer m, the 2-adic integer S(A(P), m) defined by (1.2) is algebraic. Moreover, the proof of Theorem 1.1 gives a way to compute an explicit polynomial for whose S(A(P), m) is a root. Theorem 1.1 extends a result proved in [1] when P is irreducible of prime order p in F2 [z] ( in this case, the minimal polynomial of S(A(P), m) is obtained explicitly when s( p) = p−1 2 (see [1] and [3]) and when p−1 s( p) = 3 (see [2])). As an example, we consider the case p = 7 (see [9]): here, the only irreducible polynomials in F2 [z] of order 7 are P1 (z) = 1 + z + z 3 and P2 (z) = 1 + z 2 + z 3 since in F2 [z], 1 + z 7 = (1 + z)(1 + z + z 3 )(1 + z 2 + z 3 ). In this case, we have y 2 − y + 2 = y − S(A(P1 ), 1) (y − S(A(P2 ), 1)), where S(A(P1 ), 1) = 1 + 2 + 23 + 24 + 26 + 213 + · · · + 2997 + · · · and S(A(P2 ), 1) = 2 + 22 + 25 + 27 + 28 + 29 + · · · + 2999 + · · ·, and so the elements of A(P1 ) (resp. A(P2 )) of the form 2k are 1, 2, 23 , 24 , 26 , 213 , . . . , 2997 , . . . (resp. 2, 22 , 25 , 27 , 28 , 29 , . . . , 2999 , . . .). As described in [16], the set A(P) is constructed by recursion, and this enables to give an algorithm that allows us to compute only the first elements of A(P). On the other hand, as it can be seen in the last example, solving the equation satisfied by S(A(P), m) allows us to obtain the elements of A(P) of the form 2k m for large values of k. In Sect. 2, we recall some important facts and give some preliminary results on even partition sets. In Sect. 3, the proof of Theorem 1.1 is given.
123
N. Baccar
2 Some results on even partition sets Let P be a polynomial in F2 [z] of positive degree such that P(0) = 1 and let β be the order of P ∗ . Definition 2.1 Let Z2 be the 2-adic ring. We shall say that two formal power series f (z) and g(z) with coefficients in Z2 are congruent modulo a 2-adic integer M and write f (z) ≡ g(z) (mod M), if their coefficients of the same power of z are congruent modulo M. Congruences of formal power series may be added, multiplied and derivated. Moreover, we have the following: if f (z) ≡ g(z) (mod M) and f (0) = g(0) = 1, then
1 1 ≡ f (z) g(z)
(mod M).
Definition 2.2 The Graeffe transformation. Let K be some field and K[[z]] be the ring of formal power series with coefficients in K. For an element f (z) = a0 + a1 z + a2 z 2 + . . . + an z n + . . . of this ring, the product f (z) f (−z) = b0 + b1 z 2 + b2 z 4 + . . . + bn z 2n + . . . is an even power series. We shall call G( f ) (Graeffe transformation) the series G( f )(z) = b0 + b1 z + b2 z 2 + . . . + bn z n + . . . . It follows immediately that for f, g ∈ K[[z]], G( f g) = G( f )G(g).
(2.1)
We shall use the following notation for the iterates of f by the transformation G: f (0) = f, f (1) = G( f ), . . . , f (k) = G( f (k−1) ) = G (k) ( f ). If G( f ) = f , then for all k, G (k) ( f ) = f , and we will say that f is a fixed point of the Graeffe transformation (for example f (z) = 1 − z q , where q is an odd integer). Let us assume now that K = Z2 . As in [7], it is easy to see that if f and g are in Z2 [[z]], then (2.2) f (1) ≡ f (mod 2), and for any 2-adic integer M, f ≡g
123
(mod 2M) ⇒ f (1) ≡ g(1)
(mod 4M).
(2.3)
Set elements with even partition function
Moreover, the last property is generalized (cf. [7]) to f ≡g
(mod 2) ⇒ f (k) ≡ g(k)
(mod 2k+1 ), ∀k ≥ 0.
(2.4)
Using the elementary theory of finite fields (see [14]), we know that 1 − zβ =
φd (z),
(2.5)
d |β
where φd is the cyclotomic polynomial of index d. Since β is odd, then φβ factors in F2 [z] into r (β) distinct irreducible polynomials, each of degree s(β) and of order β. It will also be of use to include here the following basic identities concerning cyclotomic polynomials: β (1 − z d )μ(d) . (2.6) φβ (z) = d |β
In [1] (see also [3]), it is proved that the polynomial P can be extended in a 2-adic such that polynomial P ≡ P(k) P
(mod 2k+1 ), ∀k ≥ 0.
(2.7)
Let Q is a polynomial of F2 [z] of positive degree such that Q(0) = 1. Therefore, from (2.1), it follows that Q. PQ = P (2.8) Let A = A(P) be the even partition set defined by (1.1). Let m be an odd positive integer and let σ (A, n) denote the sum of those divisors of n belonging to A; that is, σ (A, n) =
d.
(2.9)
d | n, d∈A
It is proved (see [4]) that for all k ≥ 0, β is a period of the sequence (σ (A, 2k n) mod 2k+1 )n≥1 . Moreover, if P is irreducible in F2 , then for all k ≥ 0, σ (A, 2k β) ≡ −s(β)
(mod 2k+1 ).
(2.10)
Let (Z/βZ)∗ denote the group of invertible residues modulo β and let < 2 > be its subgroup generated by 2. Consider the action of < 2 > on the set Z/βZ given by a n = an for all a ∈< 2 > and n ∈ Z/βZ. Then, denote the orbit of some n ∈ Z/βZ by Oβ (n); that is, Oβ (0) = {0}, and Oβ (n) = {2 j n mod β, 0 ≤ j ≤ s(β/δ) − 1},
(2.11)
123
N. Baccar
where δ := δ(n) = gcd(β, n). It is easy to see that for every non-negative integer h, we have Oβ (2h n) = Oβ (n). Moreover, for all positive integer i, one has {2 j n mod β, is(β/δ) ≤ j ≤ (i + 1)s(β/δ) − 1} = Oβ (n).
(2.12)
Such action allows one to write (Z/βZ)/<2> = {Oβ (x1 ), . . . , Oβ (xr (β) )} ∪ {Oβ (xr (β)+1 ), . . . , Oβ (x f ), Oβ (0)}, (2.13) where Oβ (x1 ), . . . , Oβ (xr (β) ) are the invertible orbits, while Oβ (xr (β)+1 ), . . . , Oβ (x f ), Oβ (0) are the non-invertible ones. We will always set xr (β) = 1. In [4], it is proved that if q mod β and n mod β are in the same orbit, then for all k ≥ 0, σ (A, 2k q) ≡ σ (A, 2k n)
(mod 2k+1 ).
(2.14)
In particular (taking q = 2n), σ (A, 2k+1 n) ≡ σ (A, 2k n)
(mod 2k+1 )
Hence, we shall consider the 2-adic integers ρ(A, n) defined by ρ(A, n) ≡ σ (A, 2k n)
(mod 2k+1 ), ∀k ≥ 0.
(2.15)
One may easily verify that the sequence (ρ(A, n))n≥1 is periodic with period β. Moreover, it turns out (see [1] and [3]) that +∞
ρ(A, n)z n = z
n=1
(z) P . P(z)
(2.16)
The last equality with the properties of the logarithmic derivative gives ρ(A(P Q), n) = ρ(A(P), n) + ρ(A(Q), n).
(2.17)
Let S(A, m) be the 2-adic integer given by (1.2). Using (2.9) and (2.15), one can see that d S(A, d). (2.18) ρ(A, m) = d |m
Applying Möbius inversion formula on the last equality, we obtain m S(A, m) =
d |m
where m
=
p | m, p prime
Möbius’s function.
123
m m = , μ(d)ρ A, μ(d)ρ A, d d
(2.19)
d |m
p denotes the radical of m with
1 = 1, and where μ is the
Set elements with even partition function
Lemma 2.1 Let α be a positive integer and let S(A(P α ), m) be the 2-adic integer defined by (1.2). Then (2.20) S(A(P α ), m) = αS(A(P), m) Proof From (2.17), we see that ρ(A(P α ), n) = αρ(A(P), n), which when combined with (2.19) gives the desired result.
(2.21)
Remark 2.1 According to what has been said in the previous lemma, in the case α is a power of 2, the set A(P α ) can be expressed in terms of the set A(P), in other words q
A(P 2 ) = 2q · A(P) := {2q n, n ∈ A(P)}. Let K be some field, H (z) = a0 +a1 z +· · ·+an z n and L(z) = b0 +b1 z +· · ·+bk z k be polynomials in K[z] of degrees n and k, respectively. We denote the resultant of H and L by resz (H (z), L(z)) and recall the following well-known results (see, for instance, [15]). Lemma 2.2 (i) The resultant resz (H (z), L(z)) is a homogeneous multivariate polynomial, with integer coefficients, and of degree n + k in the n + k + 2 variables ai and b j . (ii) If H (z) is written as H (z) = an (z − z 1 )(z − z 2 ) · · · (z − z n ) in the splitting field of H over K, then n k L(z i ). (2.22) resz (H (z), L(z)) = an i=1
(iii) If z 1 , z 2 , . . . , z n and q1 , q2 , . . . , qν are the roots of H and L, respectively, in an algebraic closure K of K , then the nν roots of the polynomial resz (H (y −z), L(z)) in K are z i + q j , 1 ≤ i ≤ n, 1 ≤ j ≤ ν. 3 Elements of even partition sets Let P be a polynomial in F2 [z] of positive degree such that P(0) = 1 and let β be the order of P ∗ . Let A = A(P) be the even partition set obtained from (1.1) and let m be an odd positive integer. The goal of this section was to prove that the elements of the even partition set A(P) satisfying (1.1), of the form 2k m, are given by the 2-adic expansion of some root of a polynomial Rm (y) ∈ Z[y]. In other words, we prove that the 2-adic integer S(A, m) defined by (1.2) is an algebraic number and explain how to obtain a polynomial Rm (y) ∈ Z[y] having S(A, m) as a root. For this, we proceed in three steps: we will start with the case where P is an irreducible polynomial, then we consider the case P is a product of power of irreducible polynomials of same order and we end by the general case. In what follows, we set s = s(β) and r = r (β) and recall that (3.1) Z/βZ = Oβ (x1 ) ∪ Oβ (x2 ) ∪ · · · Oβ (x f ) ∪ Oβ (0).
123
N. Baccar
3.1 Case P is an irreducible polynomial Let φβ be (cf. Sect. 2) the cyclotomic polynomial of index β and write φβ (z) ≡
r
P (z) (mod 2),
(3.2)
=1
where the P ’s are the only irreducible polynomials over F2 [z] of the same degree s and all of which are of order β. It follows from (2.6) and (2.1) that φβ is a fixed point of the Graeffe transformation. Therefore, from (2.8), we have 1 P r . 2 · · · P φβ = P1 P 2 · · · Pr = P
(3.3)
r (ζ ) = 0. Let ζ be a β-th primitive root of unity over the 2-adic field Q2 and such that P s−1 2 2 r are the roots of P Since for all k ≥ 0, ( Pr )(k) = Pr , it follows that ζ, ζ , . . . , ζ and the polynomials P can be arranged so that (see (2.13)) (z) = (−1)s (z − ζ x )(z − ζ 2x ) · · · (z − ζ 2s−1 x ), 1 ≤ ≤ r. P
(3.4)
For all , 1 ≤ ≤ r , let A = A(P ) be the even partition set satisfying (1.1). Lemma 3.1 Let v be a positive integer and let ρ(A , v) be the 2-adic integer defined by (2.15). Then (3.5) ρ(A , v) = −D(θ vx ), 1 ≤ ≤ r, where θ = ζ −1 and D(z) is the polynomial given by D(z) = z + z 2 + · · · + z 2
s−1 mod β
.
(3.6)
Proof Using the fact that β is a period of (ρ(Ar , n))n≥1 and that θ is β-th root of unity, it suffices to prove the last lemma when v ∈ {1, 2, . . . , β}. Since ∞
n≡v
ρ(Ar , n)z = ρ(Ar , v) n
n=1 (mod β)
∞
z v+uβ ,
u=0
it follows that ⎛ ∞
ρ(Ar , n)z n =
n=1
123
β−1 v=1
⎞ ∞
⎜ ⎜ ⎝ n≡v
n=1 (mod β)
∞
⎟ ρ(Ar , n)z n ⎟ ⎠+ n≡0
n=1 (mod β)
ρ(Ar , n)z n .
Set elements with even partition function
Therefore, ∞
ρ(Ar , n)z n =
β−1 1 zβ ρ(Ar , v)z v + ρ(Ar , β) . β 1−z 1 − zβ
(3.7)
v=1
n=1
On the other hand, from (3.4), we get s−1 s ∞ r (z) z P j =− (z/ζ 2 )n z = j 2 r (z) P z−ζ j=0 j=0 n=1 ⎛
=−
s−1 β−1 ⎜ ⎜ ⎝ v=1
j=0
⎛
∞
n≡v
⎞ ∞
j
(z/ζ 2 )n +
n=1 (mod β)
n≡0
⎞
n=1 (mod β)
⎟ j (z/ζ 2 )n ⎟ ⎠
+∞ s−1 β−1 zv zβ ⎠ ⎝ z uβ + j 1 − zβ ζ 2 v u=0 j=0 v=1 ⎛ ⎞ β−1 s−1 1 zβ j =− zv ⎝ θ2 v⎠ − s , β 1−z 1 − zβ
=−
v=1
j=0
where θ = ζ1 . Using (2.16) and comparing the last equality with (3.7), we obtain (3.5) for = r . To get (3.5) for all , 1 ≤ ≤ r , we just have to replace in the above proof
r by and ζ by ζ x . For , 1 ≤ ≤ r , let S(A , m) be the 2-adic integer defined by (1.2). We define the polynomial Dm by Dm (z) =
f
λ(m, h)Bh (z) + sγ (m),
(3.8)
h=1
where Bh (z) is the polynomial given by Bh (z) =
s−1
z2
jx
h
mod β
(3.9)
j=0
and
λ(m, h) = m d
γ (m) =
μ(d),
(3.10)
d |m
mod β ∈Oβ (x h )
μ(d).
(3.11)
d |m
m d ≡0 (mod β)
123
N. Baccar
Clearly, γ (m) = 0 if β | m while if β m, we have
γ (m) =
μ(d) =
d | gcd(
m, m β)
if m = β if m = β
1 0
We now have the tools necessary to prove the following Proposition 3.1 Under the above notation, S(A1 , m), S(A2 , m), . . . , S(Ar , m) are the roots of the polynomial Rm (y) ∈ Z[y] given by Rm (y) = resz φβ (z), my + Dm (z) ,
(3.12)
where φβ (z) is the cyclotomic polynomial of index β. Proof It follows from (2.19) that ⎛ m S(A , m) =
f ⎜ ⎜ ⎜ ⎝ h=1
⎞
m d
μ(d)ρ(A ,
d |m
mod β ∈Oβ (x h )
m ⎟ ⎟ )⎟ + d ⎠ m d ≡0
which, by (2.14) and (2.15), gives ⎛ m S(A , m) =
f h=1
μ(d)ρ(A ,
d |m
(mod β)
m ), d
⎞
⎜ ⎜ ρ(A , x h ) ⎜ ⎝
m d
d |m
mod β ∈Oβ (x h )
⎟ ⎟ μ(d)⎟ − s ⎠
μ(d).
d |m
m d ≡0 (mod β)
Consequently, m S(A , m) =
f
λ(m, h)ρ(A , x h ) − sγ (m),
h=1
which, by (3.5) and (3.9), gives m S(A , m) = −
f
λ(m, h)Bh (θ x ) − sγ (m).
h=1
From (3.8) and the last equality, we have Dm (θ x ) = −m S(A , m).
(3.13)
From (3.3), (2.22) and (3.4), it follows that the polynomial defined by (3.12) can be written as r s−1 i my + Dm (θ 2 x ) . Rm (y) = =1 i=0
123
Set elements with even partition function
Now recall that for all i, 0 ≤ i ≤ s − 1, i
Bh (θ 2 x ) =
s−1
i+ j x
θ2
xh
, 1 ≤ h ≤ f.
j=0
Let t = |Oβ (x x h )|. We claim that the last sum does not depend on i since from (2.11) and (2.12), s−1
s
θ
2i+ j x x h
=
j=0
t −1 (l+1)t−1
l=0
i+ j x
θ2
j=lt
s t −1 (l+1)t−1
= =
xh
l=0
j=lt
s−1
θ2
jx
xh
θ2
jx
xh
.
j=0 i
Hence, Dm (θ 2 x ) = Dm (θ x ) and so Rm (y) =
r s my + Dm (θ x ) . =1
Finally, from (3.13), it follows that Rm (y) = m ϕ(β)
r
(y − S(A , m))s ,
=1
which gives the desired result. Remark 3.1 Let M(y) be the polynomial of Q[z] defined by M(y) := M(P)m (y) =
1 m ϕ(β)
1
(Rm (y)) s .
(3.14)
Taking m = 1, we have M(y) = (y − D(θ ))(y − D(θ x1 )) · · · (y − D(θ xr −1 )). We note that D(θ ), D(θ x1 ), . . . , D(θ xr −1 ) are the Gaussian periods corresponding to the subgroup < 2 > which are known to be conjugate and distinct (see [12]). So, one can deduce that M(y) can be regarded as the minimal polynomial of the algebraic numbers S(A1 , 1), S(A2 , 1), . . . , S(Ar , 1). Hence, it is naturel to ask whether similar deduction can be given when m = 1?
123
N. Baccar
3.2 If P is a product of powers of irreducible polynomials of the same order Let us assume that P = Q α1 1 Q α2 2 · · · Q αt t is the irreducible factorization of P over F2 , where Q 1 , Q 2 , . . . and Q t are of same order β. It follows immediately from (2.17) that ρ(A(P), n) = α1 ρ(A(Q 1 ), n) + α2 ρ(A(Q 2 ), n) + · · · + αt ρ(A(Q t ), n). Therefore, from (2.19), we have S(A(P), m) = α1 S(A(Q 1 ), m) + α2 S(A(Q 2 ), m) + · · · + αt S(A(Q t ), m). Let ζ be a β-th primitive root of unity over the 2-adic field Q2 . It follows that there exist a1 , a2 , . . . , at distinct in {x1 , x2 , . . . , xr } (see (3.4)) so that i (z) = (−1)s (z − ζ ai )(z − ζ 2ai ) · · · (z − ζ 2s−1 ai ), 1 ≤ i ≤ t, Q
(3.15)
i ’s are the polynomial defined by (2.7). Consequently, by (3.5), for all where the Q v ≥ 1, (3.16) ρ(A(Q i ), v) = −D(θ vai ), 1 ≤ i ≤ t, where θ = ζ −1 and D(z) is the polynomial given by (3.6). In this case, it turns out to be fruitful to consider the polynomials T := T (P) of F2 [z] given by T = H1α1 H2α2 · · · Htαt , 1 ≤ ≤ r, where H1 , H2 , . . . , and Ht are irreducible polynomials of F2 of order β such that i (z) = (−1)s (z − ζ ai x )(z − ζ 2ai x ) · · · (z − ζ 2s−1 ai x ), 1 ≤ i ≤ t. H One can easily see that P = Tr . We may now state the following Proposition 3.2 The 2-adic integers S(A(T1 ), m), S(A(T2 ), m), . . . and S(A(Tr ), m) are the roots of the polynomial Rm given by Rm (y) = resz φβ (z), my + Cm (z) , where Cm (z) =
f h=1
λ(m, h)
t
αi Bh,i (z) + sγ (m)
i=1
with Bh,i (z) =
s−1 j=0
123
(3.17) t
αi ,
(3.18)
i=1
z2
jx
h ai
mod β
,
(3.19)
Set elements with even partition function
where λ(m, h) and γ (m) are, respectively, defined by (3.10) and (3.11). Proof The concept of proof is similar to the proof of Proposition 3.1.
Remark 3.2 By following the same steps as in the proof of Proposition 3.1, we obtain r s Rm (y) = my + Cm (θ x ) ,
(3.20)
=1
with Cm (θ x ) = −m S(A(T ), m), 1 ≤ ≤ r. 1
1 Unlike the previous case, the polynomial M(y) = m ϕ(β) (Rm (y)) s is not necessarily the minimal polynomial of S(A(P), m), since for some = , it can happen that S(A(T ), m) = S(A(T ), m). However, M(y) can be seen as a power of the minimal polynomial of S(A(P), m). This can be illustrated by the example where P is the product of two irreducible polynomials of order β = 113. In this case, we have s = 28, r = 4,
Z/113Z = O113 (3) ∪ O113 (9) ∪ O113 (27) ∪ O113 (1) ∪ O113 (0), and we take x1 = 3, x2 = 9, x3 = 27 and x4 = 1. Let ζ be a 113-th primitive root of unity over Q2 and take θ = ζ −1 . We assume that P = P1 P2 where P1 and P2 are irreducible polynomials of order 113 such that 1 (z) = (z − ζ )(z − ζ 2 ) · · · (z − ζ 227 ) P and 2 (z) = (z − ζ 9 )(z − ζ 18 ) · · · (z − ζ 9.227 ). P Recall that T = H1 H2 (1 ≤ ≤ 4), where 1 (z) = (z − ζ x )(z − ζ 2x ) · · · (z − ζ 227 x ) H and 2 (z) = (z − ζ 9x )(z − ζ 18x ) · · · (z − ζ 9.227 x ). H We remark that 3 · O113 (9) = O113 (27), 27 · O113 (9) = O113 (3) and 9 · O113 (9) = O113 (1); therefore, T1 = T3 and T2 = T4 . Consequently, when taking m = 1, we obtain M(y) =
y − S(A(T1 ), 1)
y − S(A(T2 ), 1)
2
,
123
N. Baccar
and so M(y) is the square of the minimal polynomial of S(A(P), 1). On the other hand, 27 27 1 j j 28 z 2 mod 113 + z 2 9 mod 113 ) = (y 2 − y − 28)2 . M(y) = resz (φ113 (z), y + j=0
j=0
For the five remaining possibilities of P represented as a product of two distinct irreducible polynomials of order 113, the corresponding polynomial M(y) will have one of the following forms ⎛ ⎞⎞ 1 ⎛ 28 27 27 j j z 2 mod 113 + z 2 3 mod 113 ⎠⎠ = y 4 − 2y 3 − 55y 2 • ⎝resz ⎝φ113 (z), y + ⎛
+ 56y + 332 ⎛
• ⎝resz ⎝φ113 (z), y +
j=0 27 j=0
j=0
z
2j
mod 113
+
27
⎞⎞ 1
28
z
2 j 27 mod 113
⎠⎠
= y 4 − 2y 3
j=0
− 55y + 56y + 332 ⎛ ⎞⎞ 1 28 27 27 j j • ⎝resz ⎝φ113 (z), y + z 2 27 mod 113 + z 2 9 mod 113 ⎠⎠ = y 4 − 2y 3 2
⎛
j=0
j=0
− 55y 2 + 56y + 332 ⎛ ⎛ ⎞⎞ 1 28 27 27 j j 2 9 mod 113 2 3 mod 113 ⎠⎠ ⎝ ⎝ • resz φ113 (z), y + z + z = y 4 − 2y 3 j=0
j=0
− 55y 2 + 56y + 332 ⎛ ⎛ ⎞⎞ 1 28 27 27 j j 2 27 mod 113 2 3 mod 113 ⎠⎠ ⎝ ⎝ • resz φ113 (z), y + z + z = (y 2 − y − 28)2 , j=0
j=0
giving the minimal polynomial only in the four first cases. 1 and P 2 do not allow us to determine the Unfortunately, the expressions of P corresponding polynomials P1 and P2 . However, this can be done by computing the first few elements of the sets A(P) for the six possibilities of P represented as a product of two distinct irreducible polynomials of order 113 and then comparing S(A(P), 1) with the roots in Z2 of y 2 − y − 28. Doing so, we obtain 2, 3, 4, 5, and 6 for the different possible values of S(A(P), 1) mod 23 . Since the roots of y 2 − y − 28 are y1 = 22 + 24 + 25 + 26 + 210 + 212 + 214 + 218 + 219 + 220 + 221 + 225 + · · · and y2 = 1 + 22 + 23 + 27 + 28 + 29 + 211 + 213 + 215 + 216 + 217 + 222 + 223 + · · · , then the corresponding P = P1 P2 is such that S(A(P), 1) mod 23 = 4 or 5 which yields P1 (z) = 1 + z 3 + z 4 + z 6 + z 7 + z 13 + z 14 + z 15 + z 21 + z 22 + z 24 + z 25 + z 28 and P2 (z) = 1+z 5 +z 6 +z 8 +z 11 +z 12 +z 13 +z 14 +z 15 +z 16 +z 17 +z 20 +z 22 +z 23 +z 28
123
Set elements with even partition function
or P1 (z) = 1 + z 2 + z 6 + z 8 + z 9 + z 10 + z 14 + z 18 + z 19 + z 20 + z 22 + z 26 + z 28 and P2 (z) = 1 + z 3 + z 4 + z 5 + z 6 + z 8 + z 9 + z 10 + z 13 + z 14 + z 15 + z 18 + z 19 + z 20 + z 22 + z 23 + z 24 + z 25 + z 27 + z 28 . 3.3 Proof of Theorem 1.1 Now, we consider the general case and write P = ization of P over F2 . Using the fact that S(A(P), m) =
i
Piαi for the irreducible factor-
S(A(Piαi ), m)
i
and Lemma 2.2 (iii), one can deduce that S(A(P), m) is algebraic. It follows that by grouping the Pi having the same order and taking into account the above cases, we obtain a polynomial M(P)(y) with integer coefficients having S(A(P), m) as a root. An example: Let Q = P1a P2b P3c where P1 (z) = 1 + z + z 2 , P2 (z) = 1 + z + z 3 and P3 (z) = 1 + z + z 2 + z 4 + z 6 + z 7 + z 8 are irreducible of order, respectively, 3, 7 and 17. Taking m = 1, we obtain M(P1a )(y) = y − a, M(P2b )(y) = y 2 − by + 2b2 and M(P3c )(y) = y 2 − cy − 4c2 . Hence, we define M(P1a P2b )(y) and M(Q)(y) by M(P1a P2b )(y) = resz M(P1a )(y − z), M(P2b )(z) , M(Q)(y) = resz M(P1a P2b )(y − z), M(P3c )(z) , which give M(P1a P2b )(y) = y 2 − (2a + b)y + a 2 + ab + 2b2 and M(Q)(y) = y 4 + (−4a − 2b − 2c)y 3 + (5b2 + 3bc − 7c2 + 6ab + 6a 2 + 6ac)y 2 + (−6a 2 c + 7bc2 + 14ac2 + 8c3 − 4a 3 − 10ab2 − 5b2 c − 6abc − 6a 2 b − 4b3 )y + a 4 + 3a 2 bc + 5a 2 b2 + 5ab2 c + 2a 3 b − 7abc2 + 2a 3 c − 7a 2 c2 + 4ab3 − 8ac3 + 2b3 c + 16c4 − 4bc3 + 4b4 + 14b2 c2 Let e be the degree of S(A(P), m) as an algebraic number. Let us write P = j N j , where the irreducible factors of each of the polynomials N j over F2 are of
123
N. Baccar
the same order β j . Since each of the polynomials M(N j ) is of degree r (β j ), then by constructing M(P) as we did in the last example, one can deduce that e ≤ j r (β j ). Remark 3.3 Let us consider the case where m is divisible by some prime p belonging
to Oβ (1). Then, for all d dividing m p , we have, for all h, 1 ≤ h ≤ f , m m mod β ∈ Oβ (x h ) ⇐⇒ mod β ∈ Oβ (x h ). pd d So, we get
λ(m, h) = m d
d| m p mod β ∈Oβ (x h )
μ(d) − m pd
μ(d) = 0.
d| m p mod β ∈Oβ (x h )
By the same way, we obtain γ (m) = 0. This leads to S(A(P), m) = 0, and that the set A(P) does not contain elements of the form 2k m. This result has already been proved in [11], Theorem 1, (i).
β divides m, since in such case, for Remark 3.4 The same things happen when β m ≡ 0 (mod β), so that λ(m, h) = 0 and γ (m) = all d dividing m
, we have d μ(d) = 0. d |m
References 1. Baccar, N.: Sets with even partition function and 2-adic integers. Period. Math. Hung. 55(2), 177–193 (2007) 2. Baccar, N., Zekraoui, A.: Sets with even partition function and 2-adic integers II. J. Int. Seq. 13 (2010), Article 10.1.3 3. Baccar, N., Ben Saïd, F.: On sets such that the partition function is even from a certain point on. Int. J. Number Theory 5(3), 1–22 (2009) 4. Baccar, N., Ben Saïd, F., Zekraoui, A.: On the divisor function of sets with even partition functions. Acta Math. Hung. 112(1–2), 25–37 (2006) 5. Ben Saïd, F.: On a conjecture of Nicolas-Sárközy about partitions. J. Number Theory 95, 209–226 (2002) 6. Ben Saïd, F.: On some sets with even valued partition function. Ramanujan J. 9, 63–75 (2005) 7. Ben Saïd, F., Nicolas, J.-L.: Sets of parts such that the partition function is even. Acta Arith. 106, 183–196 (2003) 8. Ben Saïd, F., Nicolas, J.-L.: On the counting function of sets with even partition function. Publ. Math. Debr. 79(3–4), 36 (2011) 9. Ben Saïd, F., Nicolas, J.-L.: Even partition functions, Séminaire Lotharingien de Combinatoire 46, B46i (2002). http://www.mat.univie.ac.at/~slc/ 10. Ben Saïd, F., Nicolas, J.-L., Zekraoui, A.: On the parity of generalized partition function III. Journal de Théorie des Nombres de Bordeaux 22(1), 51–78 (2010) 11. Ben Saïd, F., Lahouar, H., Nicolas, J.L.: On the counting function of the sets of parts such that the partition function takes even values for n large enough. Discret. Math. 306, 1115–1125 (2006) 12. Gurak, S.: On the minimal polynomial of gauss periods for prime powers. Math. Comput. 75(256), 2021–2035 (2006) 13. Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers. Clarendon, Oxford (1979) 14. Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications. Cambridge University Press, New York (1994)
123
Set elements with even partition function 15. Mignotte, M.: Mathématiques pour le calcul formel. Presses Universitaires de France, Paris (1989) 16. Nicolas, J.-L., Ruzsa, I.Z., Sárközy, A.: On the parity of additive representation functions. J. Number Theory 73, 292–317 (1998) 17. Nicolas, J.-L.: On the parity of generalized partition functions II. Period. Math. Hung. 43, 177–189 (2001)
123
