Around Pelikán’s conjecture on very odd sequences

Pieter Moree and Patrick Solé

Abstract

Very odd sequences were introduced in 1973 by Pelikán who conjectured that there were none of length ≥ 5. This conjecture was disproved first by MacWilliams and Odlyzko [15] in 1977 and then by two different sets of authors in 1992 [1], 1995 [8]. We give connections with duadic codes, cyclic difference sets, levels (Stufen) of cyclotomic fields, and derive some new asymptotic results on the length of very odd sequences and the number of such sequences of a given length.

1 Introduction

For a given natural number n consider the sequence a_{1} … a_{n} with a_{i} ∈ {0, 1} for 1 ≤ i ≤ n. For 0 ≤ k ≤ n − 1, put A_{k} = ∑_{i=1}^{n−k} a_{i}a_{i+k}. We say that a_{1} … a_{n} is a very odd sequence if A_{k} is odd for 1 ≤ k ≤ n. By S(n) we denote the number of very odd sequences of length n. Pelikán [23] conjectured that there are no very odd sequences of length n ≥ 5. However, the sequence 101011100011 (for which the corresponding A_{k}’s are 7, 3, 3, 1, 3, 3, 3, 1, 1, 1, 1, 1) disproves this conjecture. Alles [1] showed that if S(n) > 0, then also S(7n − 3) > 0 and thus showed that there are infinitely many counterexamples to Pelikán’s conjecture. In his note [1] Alles raised two questions:

(1) Does S(n) > 0 imply n ≡ 0, 1(mod 4)?

(2) Does S(n) > 0 imply S(n) = 2^{k} for some integer k? These two questions, which also appear as unsolved problem E38 in [6], were positively answered in [8].

All of the above was, however, already known much earlier [15]. For a and b coprime integers, let ord_{a}(b) denote the smallest positive integer r such that a^{r} ≡ 1(mod b). Let P = {7, 23, 31, 47, 71, 73, 79, …} denote the set of odd primes p for which ord_{2}(p) is odd (throughout this paper the letter p will be used to denote primes). MacWilliams and Odlyzko proved that S(n) > 0 iff 2n − 1 is composed only from primes in P. (Alternatively we can formulate this as S(n) > 0 iff the order of 2 modulo 2n − 1 is odd.) Since 7 ∈ P, Alles result that S(n) > 0 implies S(7n − 3) > 0, immediately follows. Using the supplementary law of quadratic reciprocity it is easily seen, as already noticed in [15], that p ∈ P implies p ≡ ±1(mod 8). Thus if S(n) > 0, then 2n − 1 ≡ ±1(mod 8) and from this it follows that the answer to question (1) is affirmative. In [15] question (2) was answered in the affirmative also; to be more precise it was shown that if S(n) > 0 then X^{2n−1} − 1 decomposes over 𝔽_{2} into an odd number of distinct irreducible factors, say 2h + 1 irreducible factors in total and that, moreover, S(n) = 2^{h}. R. van der Veen and E. Nijhuis [35] described and implemented an algorithm to determine all very odd sequences of a given length. Moreover, they showed that, for n > 1, a very odd sequence is never periodic.

Mathematics Subject Classification (2000). 11N64, 94B15, 11N37

Let N(x) denote the number of n ≤ x for which very odd sequences of length n exist. Let Li(x) denote the logarithmic integral. By [17, Theorem 2] it follows that

P(x) = \frac{7}{24}Li(x) + O (\frac{x(log log x)^{4}}{log^{3} x} ) ,  (1)

where P(x) denotes the number of primes p ≤ x in P. Using Theorem 4 of [17] it then follows there exists a c_{0} > 0 such that

N(x) = c_{0} \frac{x}{log^{17/24} x} (1 + O (\frac{(log log x)^{5}}{log x} )) .  (2)

Since lim_{x→∞} N(x)/x = 0, it follows in particular that Pelikán’s conjecture holds true for almost all integers n. The estimates (1) and (2) sharpen the assertions P(x) ∼ \frac{7}{24} \frac{x}{log x}, respectively N(x) = o(x) made in [15].

The analysis of very odd sequences and that of Ducci sequences [3] shows a certain analogy (in the latter case the factorization of (1+x)^{n}+1 over 𝔽_{2}[X] plays an important role and there is also a link with Artin’s primitive root conjecture).

In Sections 2 and 3 the connection between very odd sequences and coding theory, respectively the Stufe (level) of cyclotomic fields is considered. In Section 4 a formula for S(n) is derived (Proposition 2). In Section 5 the value distribution of S(n) is then considered, using some results related to Artin’s primitive root conjecture (Theorem 2 and Theorem 3). It is shown that under the Generalized Riemann Hypothesis (GRH) the preimage of the value 2^{e} is infinite, provided we can find just one integer n of a certain type satisfying S(n) = 2^{e} (Theorem 4). This leads us then into a query of finding such integers and motivates the introduction of the notion of solution tableaux (Section 6.1). In the final section it is shown that certain values of S(n) are much more sparse than others.

2 Codes and Pelikán’s conjecture

For coding theoretic terminology, we refer to [16].

Lemma 1 We have S(n) > 0 iff there exists a [2n, n] extended binary cyclic code. In particular, there are very odd sequences of length \frac{p+1}{2} for all odd primes p ≡ ±1(mod 8), and of length 2^{m} for all even integers m ≥ 2.

Proof. Write b_{k} := a_{k−1} and b(x) := ∑_{k=0}^{n−1} b_{k}x^{k}, with x an indeterminate. With this notation as observed in [15], the definition of a very odd sequence amounts to the polynomial identity x^{2n−1} +1 = (x+1)b(x)b^{∗}(x), the ∗ denoting reciprocation. From that, we see that the cyclic code of length 2n + 1 and generator b(x) is self-orthogonal of dimension n. By adding an overall parity-check we obtain a self-dual code of length 2n.

The two infinite families of lengths correspond to, respectively, quadratic residue codes attached to the prime p and Reed-Muller codes RM(\frac{m}{2}, m + 1) (see [16]). □

We denote by C(n) the number of nonequivalent codes of length 2n obtained by the preceding lemma. The celebrated [24, 12, 8] Golay code arises on taking n = 12. More generally, we obtain duadic codes with multiplier −1 which have received much attention in the last twenty years [11, 21]. In the special case of n a multiple of 8, these codes are, furthermore, doubly even. There are generalizations over 𝔽_{4} [22], 𝔽_{q} [28, 29] and over rings [9, 14]. The following connection with difference sets is proved differently in [29, Thm 6.2.1.] and in a very general setting in [25].

Lemma 2 If there is a 2 − (N, K, λ) cyclic difference set with K and λ both odd, then there is a very odd sequence of length (N + 1)/2.

Proof. We use the ring morphism (given by reduction mod 2) between the algebra 𝔽_{2}[x]/(x^{N} − 1), where binary cyclic codes of length N live and the group algebra ℤ[C_{N}] which occurs in the following characterization [2, Lemma 3.2, p. 312] of difference sets of the cyclic group C_{N} :

DD^{−1} = K − λ + λC_{N}.

The difference set D is then the set of exponents of x in the b(x) of the preceding proof. □

The following construction generalizes Alles’s [1], who took m = 4. Let a (resp. b) denote a very odd sequence of length n (resp. m). Let a(X) (resp. b(X)) denote their associated polynomials in 𝔽_{2}[X]. By a ⊗ b we shall mean the sequence of attached polynomial a(X)b(X^{2n−1}). Explicitly this amounts to the sequence obtained by taking b, replacing each b_{i} ∈ b by a block of m zeros (if b_{i} = 0) or a (if b_{i} ≠ 0), and finally inserting a sequence of n − 1 zeros between each of these blocks. The following result is given without a proof in [8].

Lemma 3 If a and b are very odd sequences of respective lengths n and m, then a ⊗ b is a very odd sequence of length 2mn − n − m + 1. If a′ and b′ are very odd sequence of lengths n and m, then a ⊗ b = a′ ⊗ b′ implies a = a′ and b = b′.

Proof. We know that, by hypothesis, Y^{2m−1} + 1 = (Y + 1)b(Y)b^{∗}(Y). Letting Y = X^{2n−1} and using the hypothesis on a, that is X^{2n−1}+1 = (X +1)a(X)a^{∗}(X), we see that c(X) := a(X)b(X^{2n−1}), satisfies X^{2N−1} + 1 = (X + 1)c(X)c^{∗}(X), for 2N − 1 = (2n − 1)(2m − 1), i.e. N = 2mn − n − m + 1.

Conversely, writing c(X)=A(X)B(X), with A, B such that

• the order of the roots of A divide 2n − 1

• the order of the roots of B does not divide 2n − 1

we see that such a factoring is unique. We claim that A = a and B(X) = b(X^{2n−1}) is of that shape. Indeed, if β^{2n−1} = 1 and b(β^{2n−1}) = 0 we have that 1 is a root of b(X), contradicting the definition of b. Alternatively note that the second part of the assertion follows from the explicit construction of a ⊗ b. □

Corollary 1 We have S(2mn − n − m + 1) ≥ S(m)S(n).

3 Connection with the Stufe of a cyclotomic field

Let K be a field. Then the Stufe (or level) of K, s(K), is defined as the smallest number s (if this exists) such that −1 = α_{1}^{2} + ⋯ + α_{s}^{2} with all α_{i} ∈ K. If the Stufe does not exist, it is not difficult to see that there exists an order ≤ on K that is compatible with the field operations (i.e. K is orderable). Pfister proved that the Stufe of any field, if it exists, is a power of two. For m ≥ 1, let K_{m} = ℚ(e^{2πi/m}). Hilbert proved that s(K_{m}) ≤ 4 for m ≥ 3. Fein et al. [5] proved that s(K_{2m−1}) = 2 iff ord_{2}(2m − 1) is even. We thus obtain the following lemma.

Lemma 4 We have S(n) > 0 iff s(K_{2n−1}) = 4.

Note that if 4|m, then clearly s(K_{m}) = 1 and for m odd we have K_{2m} = K_{m}, thus once we know s(K_{m}) for every odd m, we know the Stufe of every cyclotomic field. Lemma 4 then shows that knowing for which n we have S(n) > 0 is equivalent with knowing the Stufe for every cyclotomic field. Interestingly enough, knowing the Stufe of every imaginary quadratic number field is equivalent with knowing which integers can be represented as a sum of three integer squares (Gauss’ famous three-squares theorem), see [27]. Let St_{4}(x) count the number of m ≤ x such that s(K_{2m−1}) = 4. Then from Lemma 4 and (2) we infer that

St_{4}(x) = N(x) = c_{0} \frac{x}{log^{17/24} x} (1 + O (\frac{(log log x)^{5}}{log x} )) .

4 An explicit formula for S(n)

It is not difficult to derive an explicit formula for S(n). To this end we first study the factorization of X^{n} − 1 into irreducibles over 𝔽_{q}, with q a power of a prime p. If n = mp^{e}, with p ∤ n, then since X^{n} − 1 = (X^{m} − 1)^{p^{e}} over 𝔽_{q}, we can reduce to the case where (n, q) = 1. Then we have the following result.

Lemma 5 Let q be the order of a finite field. If (n, q) = 1, then X^{n} − 1 factors into

i_{q}(n) = ∑_{d|n} \frac{φ(d)}{ord_{q}(d)}  (3)

distinct irreducible factors over 𝔽_{q}.

Proof. The assumption (n, q) = 1 ensures that the irreducibles will be distinct. Let Φ_{d}(X) denote the cyclotomic polynomial of degree d. We have X^{n} − 1 = ∏_{d|n} Φ_{d}(X), cf. [13, Theorem 2.45]. It is not difficult to show [13, Theorem 2.47] that the polynomial Φ_{d}(X) decomposes into ϕ(d)/ord_{q}(d) irreducibles over 𝔽_{q} each having degree ord_{q}(d). On combining these results, the proof is then completed. □

The above formula for i_{2}(n) together with results from [11], then yields the following first few values.

Table 1: S(n) and C(n) for small n

\begin{matrix}n & S(n) & C(n) \\ 4 & 2 & 1 \\ 12 & 2 & 1 \\ 16 & 8 & 2 \\ 24 & 2 & 1 \\ 25 & 4 & 1 \\ 36 & 2 & 1 \\ 37 & 16 & 2 \\ 40 & 2 & 1 \\ 45 & 16 & 2 \\ 52 & 2 & 1 \\ 64 & 512 & 30 \end{matrix}

For q ∤ n, let r_{q}(n) = φ(n)/ord_{q}(n). Note that r_{q}(n) = [(ℤ/nℤ)^{∗} : ⟨q⟩]. This quantity is sometimes called the (residual) index of q in (ℤ/nℤ)^{∗}.

Lemma 6

1) Suppose that δ|d and (d, q) = 1, then r_{q}(δ)|r_{q}(d).

2) If r_{q}(p) = r_{q}(p^{2}), then r_{q}(p^{e}) = r_{q}(p) for every e ≥ 1.

Proof. 1) The natural projection of multiplicative groups (ℤ/dℤ)^{∗} → (ℤ/δℤ)^{∗} gives rise to the projection (ℤ/dℤ)^{∗}/⟨q⟩ → (ℤ/δℤ)^{∗}/⟨q⟩, and so r_{q}(δ) divides r_{q}(d) as claimed.

2) It is a well-known, and easy to prove, result in elementary number theory that if ord_{2}(p) = n and ord_{2}(p^{2}) = pn, then ord_{2}(p^{e}) = p^{e−1}n for e ≥ 1. □

Let f(X) ∈ ℤ[X] be an irreducible monic polynomial over ℚ. A celebrated result of Dedekind (see e.g. [20, Theorem 4.12]) relates the factorization of f(X) over 𝔽_{p} to the factorization of the ideal (p) into prime ideals in the ring of integers O of the quotient field ℚ[X]/f(X) (to each irreducible f_{i}(X) of f(X) over 𝔽_{p} corresponds a prime ideal lying over (p) in O of degree deg(f_{i})). When we apply this with f(X) = Φ_{d}(X) we see that in ℤ[ζ_{d}], the ring of integers of ℚ(ζ_{d}), the prime ideal (p) factorizes as (p) = P_{1} ⋯ P_{g}, where each P_{i} has degree ord_{p}(d) and g = r_{p}(d) (see e.g. [20, Theorem 4.16]). This interpretation of r_{p}(d) together with some basic facts from algebraic number theory gives another proof of Lemma 6 in case q = p. From the above remarks it follows that i_{p}(n), for p ∤ n, counts the total number of prime ideals (p) factorizes in, in all the cyclotomic subfields of ℚ(ζ_{n}).

The formula for i_{q}(n) given in Lemma 5 also arises in some other mathematical contexts, see e.g. [24, 33, 34]. In particular we like to recall the following important result due to Ulmer [33].

Theorem 1 Let p be a prime, n a positive integer, and d a divisor of p^{n} + 1 that is coprime with 6. Let q be a power of p and let E be the elliptic curve over 𝔽_{q}(t) defined by y^{2} + xy = x^{3} − t^{d}. Then the j-invariant of E is not in 𝔽_{q}, the conjecture of Birch and Swinnerton-Dyer holds for E, and the rank of E(𝔽_{q}(t)) equals i_{q}(d).

The function i_{q} is neither multiplicative nor additive, but we can still prove something in this direction. The proof will make use of the following proposition, the proof of which is left to the reader. (It requires elementary number theory only.)

Proposition 1 Suppose that q ∤ n_{1}n_{2}.

1) If (n_{1}, n_{2}) = 1, then i_{q}(n_{1}n_{2}) ≥ i_{q}(n_{1})i_{q}(n_{2}).

2) If (n_{1}, n_{2}) = 1 and (ord_{q}(n_{1}), ord_{q}(n_{2})) = 1, then i_{q}(n_{1}n_{2}) = i_{q}(n_{1})i_{q}(n_{2}).

3) If i_{q}(p_{1}^{e_{1}} ⋯ p_{s}^{e_{s}}) is prime, then for every 1 ≤ i ≤ s there exists a j ≠ i such that (ord_{q}(p_{i}^{e_{i}}), ord_{q}(p_{j}^{e_{j}})) > 1.

4) We have i_{q}(n_{1}n_{2}) ≥ i_{q}(n_{1}) + i_{q}(n_{2}) − 1.

Proof. 1+2) If (d_{1}, d_{2}) = 1, then ord_{q}(d_{1}, d_{2}) = lcm(ord_{q}(d_{1}), ord_{q}(d_{2})) and so ord_{q}(d_{1}d_{2}) ≤ ord_{q}(d_{1})ord_{q}(d_{2}). If in addition (ord_{q}(n_{1}), ord_{q}(n_{2})) = 1, then ord_{q}(d_{1}d_{2}) = ord_{q}(d_{1})ord_{q}(d_{2}).

3) This is a corollary to part 2.

4) We have

i_{q}(n_{1}n_{2}) = ∑_{d|n_{1}n_{2}} r_{q}(d) ≥ ∑_{d|n_{1}} r_{q}(d) + ∑_{{d|n_{2} \atop d≠1}} r_{q}(n_{1}d) ≥ i_{q}(n_{1}) + i_{q}(n_{2}) − 1,

where in the derivation of the latter inequality we used part 1 of Lemma 6. □

The results from [15] as described above together with Lemma 5 yield an explicit formula for S(n).

Proposition 2 Let i_{2} be as in Lemma 5. We have

S(n) = \{ \begin{matrix}0 & if ord_{2}(2n − 1) is even; \\ \sqrt{2}^{i_{2}(2n−1)−1} & if ord_{2}(2n − 1) is odd. \end{matrix}

Note that if ord_{2}(2n − 1) is odd, then for every divisor d > 1 of 2n − 1 we have that ϕ(d)/ord_{2}(d) is even. Thus i_{2}(2n − 1) is odd and S(n) is an integer, as a priori it has to be.

Using part 4 of Proposition 1 and the latter proposition, an alternate proof of Corollary 1 is obtained. We like to point out that often S(mn+(m−1)(n−1)) > S(m)S(n); it can be shown for example that S(n^{2} + (n − 1)^{2}) = S(n)^{2} > 0 iff ord_{2}(2n − 1) is odd and 2n − 1 is of the form p^{k} with ord_{2}(p) ≠ ord_{2}(p^{2}). From this equivalence and (2), we infer that S(n^{2} + (n − 1)^{2}) ≠ S(n)^{2} for almost all n with S(n) > 0. Part 1 of Proposition 1 can also be turned into a, not so elegant, inequality for S.

It is easy to show that ord_{2}(p) = ord_{2}(p^{2}) iff 2^{p−1} ≡ 1(mod p^{2}). Primes satisfying the latter congruence are known as Wieferich primes and are discussed more extensively in the next section.

5 On the value distribution of S(n)

By Proposition 2 and the remark that if ord_{2}(2n − 1) is odd, then i_{2}(2n − 1) is odd, we infer that S(n) ∈ {0, 1, 2, 4, 8, 16, 32, …}. For v an integer, let N_{v}(x) denote the number of n ≤ x for which S(n) = v and let N_{v} be the corresponding set of natural numbers n.

Proposition 3 Let e ≥ 1 be any natural number. Then N_{2^{e}} is non-empty.

Proof. Let p be any prime with p ≡ 3(mod 4), ord_{2}(p) = (p − 1)/2 and 2^{\frac{p−1}{2}} ≢ 1(mod p^{2}) (the prime 7 will do), then we claim that (p^{e} + 1)/2 ∈ N_{e}. Our assumptions imply that r_{2}(p) = r_{2}(p^{2}) and thus, by Proposition 6, we infer that r_{2}(p^{k}) = r_{2}(p) = 2 for k ≥ 1. Hence i_{2}(p^{e}) = 2e + 1. Note that ord_{2}(p^{e}) is odd. By Proposition 2 it then follows that S(\frac{p^{e}+1}{2}) = 2^{e}. □

Corollary 2 We have Im(S) = {0, 1, 2, 4, 8, …}.

Proof. This follows from Im(S) ⊆ {0, 1, 2, 4, 8, …}, the proposition, S(1) = 1 and S(2) = 0. □

The sets N_{0} and N_{1} are relatively well understood; we have N_{0}(x) = [x] − N(x), which together with (2) gives a good estimate and furthermore N_{1} = {1}. It remains to deal with N_{2^{e}} for e ≥ 1. We propose the following strengthening of Proposition 3.

Conjecture 1 Let e ≥ 1 be any natural number. There are infinitely many integers n for which S(n) = 2^{e}.

Put

P_{m} = \{p > 2 : \frac{p − 1}{m} is odd and ord_{2}(p) = \frac{p − 1}{m}\}

and

P′_{m} = \{p ∈ P_{m} : 2^{\frac{p−1}{m}} ≢ 1(mod p^{2})\}.

Note that if p ∈ P_{m}, but p ∉ P′_{m}, then ord_{2}(p) = ord_{2}(p^{2}) and hence p is a Wieferich prime. The proof of Proposition 3 shows that if we could prove that there are infinitely many primes in P′_{2} such that, the truth of Conjecture 1 follows. Although it seems very likely there are indeed infinitely many such primes, proving this is quite another matter. A prime being in P_{2} is closely being related to the Artin primitive root conjecture and a prime p satisfying 2^{\frac{p−1}{2}} ≡ 1(mod p^{2}), is closely related to Wieferich’s criterion for the first case of Fermat’s Last Theorem. Wieferich proved in 1909 that if there is a nontrivial solution of x^{p} + y^{p} = z^{p} with p ∤ xyz, then 2^{p−1} ≡ 1(mod p^{2}) (hence the terminology Wieferich prime). Despite extensive computational efforts, the only Wieferich primes ever found are 1093 and 3511 [4]. Note that 3511 ∈ P_{2}\P′_{2} and that 1093 ∉ ∪_{m=1}^{∞}(P_{m}\P′_{m}). Heuristics suggest that up to x there are only O(log log x) Wieferich primes. If we replace 2 in Wieferich’s congruence by an arbitrary integer a (i.e., consider primes p such that a^{p−1} ≡ 1(mod p^{2})), then it is known that on average (the O(log log x) heuristic holds true [19], where the averaging is over a. Assuming the abc-conjecture it is known [26] that there are ≫ log x/ log log x primes p ≤ x that are non-Wieferich primes. For our purposes it would be already enough to know that there only o(x/ log x) Wieferich primes ≤ x, however, even this is unproved.

The situation regarding P_{m} is slightly more promising. Under GRH we can namely prove the following result. Our proof rests on a variation of Hooley’s proof of Artin’s primitive root conjecture that belongs to a class of variations of this problem dealt with by H.W. Lenstra [10]. This relieves us from the burden of dealing with its analytic aspects.

Theorem 2 (GRH). Let m be a natural number. Let ν_{2}(m) denote the exponent of 2 in m. If m is odd or ν_{2}(m) = 2, then P_{m} is empty. In the remaining cases we have, under GRH,

P_{m}(x) = \frac{2Aϵ_{1}(m)}{3m^{2}} ∏_{p|m} \frac{p^{2} − 1}{p^{2} − p − 1} \frac{x}{log x} + O (\frac{x log log x}{(log x)^{2}}) ,  (4)

where A = ∏_{p} (1 − \frac{1}{p(p−1)}) ≈ 0.3739558136 … denotes the Artin constant and

ϵ_{1}(m) = \{ \begin{matrix}1 & if ν_{2}(m) = 1; \\ 2 & if ν_{2}(m) ≥ 3. \end{matrix}

Proof. If m is odd, then (p − 1)/m is even and hence P_{m} is empty. If 4||m, then (p − 1)/m is odd implies that p ≡ 5(mod 8) and ord_{2}(p − 1) = (p − 1)/m implies that (\frac{2}{p}) = 1. By the supplementary law of quadratic reciprocity the conditions (\frac{2}{p}) = 1 and p ≡ 5(mod 8) cannot be satisfied at the same time. Hence P_{m} is empty.

For the remainder of the proof we assume GRH. Then it can be shown, cf. [10, 36] that the set of primes p such that ord_{2}(p) = (p − 1)/m satisfies an asymptotic of the form (4) with constant

∑_{n=1}^{∞} \frac{μ(n)}{[ℚ(ζ_{nm}, 2^{1/nm}) : ℚ]}.  (5)

Let f be an arbitrary natural number. If in addition to requiring ord_{2}(p) = (p − 1)/m, we also require p ≡ 1(mod f), it is readily seen that the sum in (5) has to be replaced by

δ(f, m) = ∑_{n=1}^{∞} \frac{μ(n)}{[ℚ(ζ_{f}, ζ_{nm}, 2^{1/nm}) : ℚ]}.

Let r = ν_{2}(m). Note that (p−1)/m is odd iff p ≡ 1+2^{r}(mod 2^{r+1}). We conclude that (4) holds with constant δ(2^{r}, m) − δ(2^{r+1}, m). It is not difficult to see that

δ(2^{r}, m) − δ(2^{r+1}, m) = ∑_{{n=1 \atop 2∤n}}^{∞} \frac{μ(n)}{[ℚ(ζ_{2nm}, 2^{1/nm}) : ℚ]}.  (6)

Let s|t. It is known (cf. [18, Lemma 1]) that

[ℚ(ζ_{t}, 2^{1/s}) : ℚ] = \{ \begin{matrix}φ(t)s/2 & if 2|s and 8|t; \\ φ(t)s & otherwise. \end{matrix}  (7)

On using the latter formula for the degree, we infer after some tedious calculation that the constant in (6) equals the constant in (4). □

Corollary 3 (GRH). If e is odd or 4|e, then N_{2^{e}} is an infinite set.

Proof. If p ∈ P_{2e}, then S(\frac{p+1}{2}) = 2^{e}. Hence the infinitude of P_{2e} for e is odd and for 4|e, implies the result. □

Corollary 3 shows that under GRH Conjecture 1 holds true, provided that e is odd or 4|e. It is possible to go further than this, but this requires a result going beyond Theorem 2:

Theorem 3 (GRH). Suppose that ν_{2}(e) ≠ 1. Let a and f be integers such that 4e|f, ν_{2}(4e) = ν_{2}(f), (a, f) = 1 and a ≡ 1 + 2e(mod 4e). There exists an integer v such that for all squarefree n we have a ≡ 1(mod (f, 2en)) iff (n, v) = 1. The density of primes p such that r_{2}(p) = 2e and p ≡ a(mod f) exists, is positive, and is given by

\frac{ϵ_{1}(2e)}{φ([f, 2e])2e} ∏_{p∤v}(1 − \frac{φ([f, 2e])}{φ([f, 2ep])p}) .

Corollary 4 (GRH). Suppose that ν_{2}(2e) ≠ 2, 2 ∤ f, (e, f) = 1 and (a, f) = 1. Then the set P_{2e} ∩ {p : p ≡ a(mod f)} contains infinitely many primes.

Proof of Theorem 3. The existence of the density, denoted by δ, follows by the work of Lenstra [10]. One obtains that

δ = ∑_{n=1}^{∞} \frac{μ(n)c_{2}(a, f, 2en)}{[ℚ(ζ_{f}, ζ_{2en}, 2^{1/2en}) : ℚ]},

with

c_{2}(a, f, k) = \{ \begin{matrix}1 & if σ_{a}|_{ℚ(ζ_{f})∩ℚ(ζ_{k},2^{1/k})} = id; \\ 0 & otherwise \end{matrix} ,

where σ_{a} is the automorphism of ℚ(ζ_{f}) : ℚ uniquely determined by σ_{a}(ζ_{f}) = ζ_{f}^{a}. Under the conditions of the result one infers that

ℚ(ζ_{f}) ∩ ℚ(ζ_{2en}, 2^{1/2en}) = ℚ(ζ_{(f,2en)})

and hence c_{2}(a, f, 2en) = 1 iff a ≡ 1(mod (f, 2en)). Let n be squarefree. Note that there exists an integer v such that a ≡ 1(mod (f, 2en)) iff (n, v) = 1. We infer that [ℚ(ζ_{f}, ζ_{nm}, 2^{1/nm}) : ℚ] = [ℚ(ζ_{[f,2en]}, 2^{1/2en}) : ℚ] = φ([f, 2en])2en/ϵ_{1}(2e), by (7). We thus find that

δ = \frac{ϵ_{1}(2e)}{φ([f, 2e])2e} ∑_{(n,v)=1} \frac{μ(n)φ([f, 2e])}{φ([f, 2en])n} = \frac{ϵ_{1}(2e)}{φ([f, 2e])2e} ∏_{p∤v}(1 − \frac{φ([f, 2e])}{φ([f, 2ep])p}) > 0,

where we used that the sum is absolutely convergent and has a summand that is a multiplicative function in n. □

Remark. An alternative way of proving Theorem 2 is to use the, Galois-theoretic, method of Lenstra, Moree and Stevenhagen [12], cf. [30]. This yields, a priori, that the density is of the form (1+∏_{p|2ft} E_{p})A, where the E_{p} are (real) character averages and hence −1 ≤ E_{p} ≤ 1.

Now, under GRH, we can prove some further results regarding Conjecture 1.

Proposition 4 (GRH). Let e be a natural number. Suppose that 1 + 2e is not a prime number congruent to 5(mod 8), then S(n) = 2^{e} for infinitely many n.

Proof. If p ∈ P_{2e}, then S(\frac{p+1}{2}) = 2^{e}. Hence the infinitude of P_{2e} for e is odd and for 4|e, implies the result in case 1 + 2e ≢ 5(mod 8). Next suppose that 1 + 2e ≡ 5(mod 8) and is not a prime. Then there exist natural numbers e_{1} and e_{2} with 1 + 2e = (1 + 2e_{1})(1 + 2e_{2}) and 1 + 2e_{1} ≢ 5(mod 8) and e_{2} ≥ 1. Suppose that n is such that 2n − 1 = 7^{e_{2}}q with

q ≢ 1(mod 6e_{1}) and q ≢ 1(mod 14e_{1}) and q ∈ P_{2e_{1}}.  (8)

The conditions on q ensure that q ≠ 7 and, moreover, (7ord_{2}(7), ord_{2}(q)) = 1 and hence r_{2}(7^{k}q) = r_{2}(7^{k})r_{2}(q) for every k. It follows that

i_{2}(2n − 1) = ∑_{d|7^{e_{2}}} r_{2}(d) + r_{2}(q) ∑_{d|7^{e_{2}}} r_{2}(d) = (1 + 2e_{1})(1 + 2e_{2}) = 1 + 2e,

and hence S(n) = 2^{e}. Since e_{1} ≢ 2(mod 4), it follows by Theorem 3 that there are infinitely many primes q satisfying (8). □

Some of the cases left open by the previous results are covered by the following result.

Proposition 5 (GRH). Suppose that 1 + 2e = z with z a prime satisfying z ≡ 5(mod 104), then S(n) = 2^{e} for infinitely many n.

Proof. The n for which 2n − 1 = 7^{2}p, where (ord_{2}(p), 21) = 3 and p ∈ P_{(z−5)/13} will do. Now invoke Theorem 3. □

For the values of S(n) hitherto not covered, the following result can sometimes be applied. Recall that ω(n) = ∑_{p|n} 1. We define ω_{1}(n) = ∑_{p||n} 1, i.e. the number of distinct prime factors p of n such that p^{2} ∤ n. Note that ω_{1}(n) ≤ ω(n).

Theorem 4 (GRH). Suppose that S(n) = 2^{e} for some n with ω_{1}(2n − 1) ≥ 1, then there are infinitely many n for which S(n) = 2^{e}.

Our proof rests on the following exchange principle.

Proposition 6 Let p and q be odd primes and m be a natural number such that (m, 2pq) = 1, r_{2}(p) = r_{2}(q) and (\frac{p−1}{r_{2}(p)}, ord_{2}(m)) = (\frac{q−1}{r_{2}(q)}, ord_{2}(m)), then i_{2}(pm) = i_{2}(qm).

Proof. The proof is a consequence of the identity

∑_{d|m} r_{2}(pm) = ∑_{d|m} r_{2}(p)r_{2}(m)(ord_{2}(p), ord_{2}(d)),

and the observation from elementary number theory that if a_{1}, a_{2}, b and d are natural numbers with (a_{1}, b) = d and (a_{2}, b) = d, then the equality (a_{1}, β) = (a_{2}, β) is satisfied for all β|b. □

Proof of Theorem 4. The assumption ω_{1}(2n − 1) ≥ 1 implies that 2n − 1 = pm with p ∤ m. By Theorem 2 there exists a number e with ν_{2}(2e) ≠ 2 such that p ∈ P_{2e}. Let q be any prime number such that

q ∈ P_{2e} and (\frac{q − 1}{r}, ord_{2}(m)) = (\frac{p − 1}{r}, ord_{2}(m)),  (9)

then by Proposition 6 we infer that S(qm) = S(pm) = 2^{e}. By Theorem 3 there are infinitely many primes q satisfying (9) and thus S(\frac{qm+1}{2}) = 2^{e}. □

6 Value distribution of S(n) on n’s with 2n − 1 squarefree

Before returning to the value distribution of S(n), we address the easier problem of studying the value distribution of S(n) with n restricted to those n for which 2n − 1 is squarefree. Let V = {e : μ(2n − 1) ≠ 0 and S(n) = 2^{e}}. Let

r_{μ}(e) = max{ω(2n − 1) : μ(2n − 1) ≠ 0 and S(n) = 2^{e}}.

and

min_{μ}(e) = min{2n − 1 : ω(2n − 1) = r_{μ}(e), μ(2n − 1) ≠ 0 and S(n) = 2^{e}},

if this exists. In the sequel we will also need the related quantities r_{ω_{1}}(e) and r_{ω}(e). Let

r_{ω_{1}}(e) = max{ω_{1}(2n−1) : S(n) = 2^{e}} and r_{ω}(e) = max{ω(2n−1) : S(n) = 2^{e}},

and min_{ω_{1}}(e) and min_{ω}(e) be defined as the smallest value of 2n − 1 for which ω_{1}(2n−1) = r_{ω_{1}}(e), respectively ω(2n−1) = r_{ω}(e) and S(n) = 2^{e} (if these exist). Note that r_{μ}(e), r_{ω_{1}}(e) and r_{ω}(e) exist and satisfy r_{μ}(e) ≤ r_{ω_{1}}(e) ≤ r_{ω}(e).

Lemma 7 We have r_{μ}(e) ≤ r_{ω_{1}}(e) ≤ r_{ω}(e) ≤ [\frac{log(2e+1)}{log 3}] for e ≥ 0.

Proof. Suppose S(n) = 2^{e}. The number 2n − 1 is composed of only primes p ∈ P. Write 2n − 1 = p_{1}^{e_{1}} ⋯ p_{s}^{e_{s}}. Then i_{2}(2n − 1) ≥ i_{2}(p_{1} ⋯ p_{s}). We have ord_{2}(p_{i}) ≤ (p_{i} − 1)/2 and ord_{2}(d) ≤ ϕ(d)2^{−ω(d)}. Thus

i_{2}(2n − 1) ≥ i_{2}(p_{1} ⋯ p_{s}) ≥ ∑_{d|p_{1}···p_{s}} 2^{ω(d)} = 3^{s}.

If s > [log(2e + 1)/ log 3], then it follows that i_{2}(2n − 1) > 2e + 1 and hence S(2n − 1) > 2^{e}. □

We now formulate the main result of this section.

Theorem 5 (GRH). Given an integer e, it is a finite problem to determine whether there exist e ∈ V. The quantity r_{μ}(e) can be effectively computed.

In order to prove it, it turns out to be fruitful to introduce the notion of a solution tableau.

6.1 Solution tableaux

Let s ≥ 2. We define a map λ : ℤ_{>0}^{s} → ℤ_{>0}^{s}, (a_{1}, …, a_{s}) → (l_{1}, …, l_{s}) as follows. We put l_{i} = lcm((a_{1}, a_{i}), …, (a_{i−1}, a_{i}), (a_{i+1}, a_{i}), …, (a_{s}, a_{i})) for 1 ≤ i ≤ s. Note that ν_{p}(l_{i}) = ν_{p}(a_{i}) if ν_{p}(a_{i}) ≤ ν_{p}(a_{j}) for some j ≠ i and ν_{p}(l_{i}) = max{ν_{p}(a_{1}), …, ν_{p}(a_{i−1}), ν_{p}(a_{i+1}), …, ν_{p}(a_{s})} otherwise. In particular, if there exist i and j with i ≠ j such that

ν_{p}(a_{i}) = ν_{p}(a_{j}) = max{ν_{p}(a_{1}), …, ν_{p}(a_{s})},  (10)

then ν_{p}(l_{i}) = ν_{p}(a_{i}). If (10) holds for every prime p (with i and j possibly depending on p), then (a_{1}, …, a_{s}) is said to be realizable. If (a_{1}, …, a_{s}) is realizable, then ν_{p}(l_{i}) = ν_{p}(a_{i}) for every 1 ≤ i ≤ s and every prime p and hence λ(a_{1}, …, a_{s}) = (a_{1}, …, a_{s}). The terminology realizable is motivated by the following result.

Proposition 7 We have (m_{1}, …, m_{s}) ∈ Im(λ) iff (m_{1}, …, m_{s}) is realizable.

Proof. ‘⇒’. By assumption λ(a_{1}, …, a_{s}) = (m_{1}, …, m_{s}) for some (a_{1}, …, a_{s}) ∈ ℤ_{>0}^{s}. W.l.o.g. assume that ν_{p}(m_{1}) = max{ν_{p}(m_{1}), …, ν_{p}(m_{s})}. Then it follows that p^{ν_{p}(m_{1})}|(a_{1}, a_{i})|m_{i} for some 1 < i ≤ s and so ν_{p}(m_{i}) = ν_{p}(m_{1}). ‘⇐’. If (m_{1}, …, m_{s}) is realizable, then λ(m_{1}, …, m_{s}) = (m_{1}, …, m_{s}). □

Suppose (m_{1}, …, m_{s}) is realizable and that a_{i} is coprime with ∏_{j=1}^{i−1} a_{j} ∏_{j=1}^{s} m_{j} for i = 1, …, s, then λ(a_{1}m_{1}, …, a_{s}m_{s}) = (m_{1}, …, m_{s}). Thus if (m_{1}, …, m_{s}) is in Im(λ), then clearly its preimage is an infinite set. However, if λ(a_{1}, …, a_{s}) = (l_{1}, …, l_{s}), then for i ≠ j, (a_{i}, a_{j}) = (l_{i}, l_{j}). Thus from a set of merely s numbers all s(s−1)/2 gcd’s (a_{i}, a_{j}) can be computed. This is the motivation of introducing the map λ as it leads to a simple expression (11) for i_{2}(p_{1} ⋯ p_{s}). Note that alternatively i_{2}(p_{1} ⋯ p_{s}) can be expressed in terms of r_{2}(p_{i}), 1 ≤ i ≤ s and the s(s − 1)/2 gcd’s (ord_{2}(p_{i}), ord_{2}(p_{j})).

Proposition 8 Given (a_{1}, …, a_{s}) ∈ ℤ_{>0}^{s}, let λ(a_{1}, …, a_{s}) = (l_{1}, …, l_{s}). We have

lcm(a_{i_{1}}, …, a_{i_{k}}) = \frac{a_{i_{1}} … a_{i_{k}}}{l_{i_{1}} … l_{i_{k}}} lcm(l_{i_{1}}, …, l_{i_{k}}),

where k ≥ 2 and 1 ≤ i_{1} < i_{2} < … < i_{k} ≤ s.

Proof. It is enough to prove the assertion in case a_{i} = p^{e_{i}} with e_{i} ≥ 0. W.l.o.g. assume that e_{1} ≤ e_{2} ≤ … ≤ e_{s}. On noting that l_{i} = p^{e_{i}} for i < s and that l_{s} = p^{e_{s−1}}, the result follows after a simple computation. □

Let p_{1}, …, p_{s} be distinct odd primes. Using the latter proposition we infer that

i_{2}(p_{1} ⋯ p_{s}) = ∑_{v_{1}=0}^{1} … ∑_{v_{s}=0}^{1} e_{1}^{v_{1}} ⋯ e_{s}^{v_{s}} \frac{l_{1}^{v_{1}} ⋯ l_{s}^{v_{s}}}{lcm(l_{1}^{v_{1}}, …, l_{s}^{v_{s}})},  (11)

with (e_{1}, …, e_{s}) = (r_{2}(p_{1}), …, r_{2}(p_{s})) and λ(ord_{2}(p_{1}), …, ord_{2}(p_{s})) = (l_{1}, …, l_{s}), where we order the prime factors p_{1} … p_{s} in such a way that e_{i} ≤ e_{j} for i ≤ j and l_{i} ≤ l_{j} if e_{i} = e_{j}. We say that ({e_{1} \atop l_{1}} ⋯ {e_{s} \atop l_{s}}) is the tableau associated to m = p_{1} ⋯ p_{s}. We say that ({e_{1} \atop l_{1}} ⋯ {e_{s} \atop l_{s}}) is a solution tableau if ν_{2}(e_{i}) ≠ 2, e_{i} is even and l_{i} is odd for every l_{i} and, moreover, (l_{1}, …, l_{s}) is realizable. The value associated to a solution tableau is the quantity in the right hand side of (11). The following result is a consequence of Theorem 3.

Proposition 9 The tableau associated to a squarefree integer 2n − 1 satisfying S(n) = 2^{e} is a solution tableau. Given any solution tableau T, under GRH, there exist infinitely many squarefree integers 2n − 1 such that the associated solution tableau equals T.

Example 1. Let us consider the tableau ({2 \atop 3} {2 \atop 15} {8 \atop 5}). Note that it is a solution tableau corresponding to the value 601 of i_{2}. Let us try to find an m = p_{1}·p_{2}·p_{3} having this tableau associated to it. We need to find primes p_{1}, p_{2} in P_{2} and p_{3} in P_{8} such that (ord_{2}(p_{1}), ord_{2}(p_{2})) = 3, (ord_{2}(p_{1}), ord_{2}(p_{3})) = 1 and (ord_{2}(p_{2}), ord_{2}(p_{3})) = 5. Any p_{1} in P_{2} satisfying p_{1} ≡ 1(mod 3) will fit the bill. E.g. p_{1} = 79. Any p_{2} in P_{2} satisfying p_{2} ≡ 1(mod 15) and p_{2} ≢ 1(mod 13) will do, e.g. p_{2} = 991. Finally any p_{3} ∈ P_{8} satisfying p_{3} ≡ 2(mod 3), p_{3} ≡ 1(mod 5), p_{3} ≢ 1(mod 11) and p_{3} ≢ 1(mod 13) will do, e.g. p_{3} = 1721. We have, as expected, i_{2}(79·991·1721) = 601. (Despite the numerous conditions on p_{3}, by Corollary 4 there exist, under GRH, infinitely many such primes.)

Proposition 10 Let r ≥ 1 be any integer. The set of tableaux associated to the set {m : 2 ∤ ord_{2}(m), μ(m) ≠ 0, i_{2}(m) ≤ r} is finite.

Proof. By Lemma 7 we have ω(m) ≤ r_{μ}(e). Thus the number of entries in a row of an associated tableau is bounded by r_{μ}(e). Now fix any s ≤ r_{μ}(e). Note that i_{2}(p_{1} … p_{s}) ≥ e_{1} … e_{s}l_{1} … l_{s}/lcm(l_{1}, …, l_{s}). There are only finitely many possibilities for e_{1}, …, e_{s}, l_{1}, …, l_{s} such that ({e_{1} \atop l_{1}} ⋯ {e_{s} \atop l_{s}}) is a solution tableau and i_{2}(p_{1} … p_{s}) ≤ r. □

Example 2. We try to find all primes z ≡ 5(mod 8) with z ≤ 229 for which there are distinct primes p and q both in P such that i_{2}(p · q) = z. This leads us to find all z of the above form for which there are e_{1}, e_{2} and w satisfying 1 + 2e_{1} + 2e_{2} + 4e_{1}e_{2}w = z with ν_{2}(e_{1}) ≠ 1, ν_{2}(e_{2}) ≠ 1 and w ≥ 3 is odd. There are solutions precisely for z ∈ {101, 157, 197, 269, 317, 349, 421, 509, …}. The associated solution tableau is ({2e_{1} \atop w} {2e_{2} \atop w}). In each case one can find p and q corresponding to this solution tableau. E.g., when z = 421 an associated solution tableau is ({2 \atop 5} {38 \atop 5}). A solution corresponding to this is p = 71 and q = 174991.

Proof of Theorem 5. One can effectively determine the solution tableaux corresponding to the given value of e and hence r_{μ}(e) (it is the largest number of columns amongst these solution tableaux). Note that by Proposition 10 there are only finitely many associated solution tableaux. If there is no associated solution tableau, then e ∉ V. If there is a solution tableau, then under GRH, it is possible to find an m corresponding to it (cf. Example 1) and thus e ∈ V.

We now also have the tools to show that the upper bound in Lemma 7 is sharp for infinitely many e.

Proposition 11 (GRH). Let s ≥ 2. If e = (3^{s} − 1)/2, then r_{μ}(e) = r_{ω_{1}}(e) = r_{ω}(e) = s.

Proof. A solution tableau with s+1 columns clearly does not exist. On the other hand T = ({2 \atop 1} … {2 \atop 1}) (s columns) is a solution tableau. Now apply Proposition 9. □

Remark. If we restrict e to be such that 1 + 2e is prime, then the upper bound is far from sharp. This is a consequence of part 3 of Proposition 1.

6.2 The general problem revisited

Theorem 5 has the following more important variant.

Theorem 6 (GRH). Assume that the number of primes p ≤ x such that ord_{2}(p) is odd and p is a Wieferich prime is o(x/ log x). Given an integer e, it is a finite problem to determine whether or not there exist n with S(n) = 2^{e} and ω_{1}(2n − 1) ≥ 1. The quantities r_{ω_{1}}(e) and r_{ω}(e) can be effectively computed.

For clarity, we first consider some examples. It will be convenient to divide the integers n with ord_{2}(n) odd in two classes. We say n = ∏_{i=1}^{s} p_{i}^{e_{i}} is of type II if there exists i and j such that e_{i} ≥ 2 and p_{i}|ord_{2}(p_{j}) and of type I otherwise.

Example 3. We try to find all primes z ≡ 5(mod 8) with z ≤ 229 for which there are distinct primes p and q both in P such that i_{2}(p^{r} · q^{s}) = z, with r, s ≥ 1. -Let us assume first that p^{r} ·q^{s} is of type I. Then we have to find all z of the above form for which there are e_{1}, e_{2}, r, s and w satisfying 1+2e_{1}r+2e_{2}s+4e_{1}e_{2}rsw = z with ν_{2}(e_{1}) ≠ 1, ν_{2}(e_{2}) ≠ 1 and w ≥ 3 odd. On making the substitution f_{1} = e_{1}r and f_{2} = e_{2}r, we have to solve 1 + 2f_{1}r + 2f_{2}s + 4f_{1}f_{2}w, with w ≥ 3 is odd. This equation is of the same format as the one arising in Example 2, except that now there are no restrictions on f_{1} and f_{2}. There are solutions precisely for r ∈ \{101, \underline{109}, 157, \underline{173}, 197, 269, 317, 349, 421, 509, …\}. The two underlined numbers did not arise in Example 2. A preimage for 109 is readily found using Proposition 5. One finds that, e.g., i_{2}(7^{2} · 73) = 109. For 173 one finds that the preimage has to be of the form p^{2} ·q with solution tableau ({2 \atop 5} {8 \atop 5}) associated to p·q. One finds that 71^{2} · 1721 is the smallest preimage of the required format. -Next assume that p^{r} · q^{s} is of type II. In this case i_{2}(p^{r} · q^{s}) ≥ 11 + 4min{p, q}. We only have to analyze the case where p ∈ {7, 23, 31, 47}. The only prime z ≡ 5(mod 8) with z ≤ 229 that is assumed as value turns out to be 197. This can happen only if p or q equals 23, e.g., i_{2}(23^{3} · 47) = 197 (we leave the details to the reader).

Example 4. We try to find all primes z ≡ 5(mod 8) with z ≤ 229 for which there exists an integer m with ord_{2}(m) is odd and ω(m) ≥ 3 such that i_{2}(m) = z. In case ω(m) ≥ 4 one has i_{2}(m) ≥ 2 · 2 · 2 · 2 · 3 · 5 = 240, so assume that ω(m) = 3. In case m is of type I one finds, using solution tableaux, that there is no such z. Indeed, the smallest prime z ≡ 5(mod 8) occurring thus is 509. It arises only if m = p^{2} · q · r and the solution tableau associated to p · q · r is ({2 \atop 5} {2 \atop 5} {2 \atop 5}). One finds that, e.g., i_{2}(71^{2} · 191 · 271) = 509. The smallest prime z ≡ 5(mod 8) occurring for a type II integer is 389. One has, e.g., i_{2}(7^{2} · 71 · 191) = 389.

In Example 3 one can see the following exchange principle for integers of type I at work.

Proposition 12 Suppose that s ≥ 2 and (p, ord_{2}(m)) = 1 and q is a prime satisfying r_{2}(q) = ∑_{j=1}^{s} r_{2}(p^{j}) (that is ord_{2}(q) = sr_{2}(p) in case q is not a Wieferich prime), then i_{2}(p^{s} · m) = i_{2}(q · m).

For the prime q above r_{2}(q) is even, but it is not necessarily the case that ord_{2}(q) is odd.

We say that ({e_{1} \atop l_{1}} ⋯ {e_{s} \atop l_{s}}) is a generalized solution tableau if 2|e_{i}, 2 ∤ l_{i} for 1 ≤ i ≤ s and, moreover, (l_{1}, …, l_{s}) is realizable. In order to find an integer m of type I such that i_{2}(m) = r and ord_{2}(m) is odd, we first determine all generalized solution tableaux ({f_{1} \atop l_{1}} ⋯ {f_{s} \atop l_{s}}) associated to r. If there are none, there is no solution. If there is a generalized solution tableau and ν_{2}(f_{i}) ≠ 2 for 1 ≤ i ≤ s, the generalized solution tableau is even a solution tableau and a squarefree integer m can be found such that i_{2}(m) = r. W.l.o.g. suppose that ν_{2}(f_{i}) = 2 for 1 ≤ i ≤ t and ν_{2}(f_{i}) ≠ 2 for t < i ≤ s. Put e_{i} = f_{i}/2 for 1 ≤ i ≤ t and e_{i} = f_{i} for t < i ≤ s. Then we want to find an integer m of the form m = p_{1}^{2} ⋯ p_{t}^{2}·p_{t+1} ⋯ p_{s}, where p_{1}, ⋯, p_{t} are non-Wieferich primes and p_{1} ·p_{2} ⋯ p_{s} has associated solution tableau ({e_{1} \atop l_{1}} ⋯ {e_{s} \atop l_{s}}). Under GRH and the assumption that the number of Wieferich primes with ord_{2}(p) odd is o(x/ log x), we are guaranteed that such an integer m exists. It can be found proceeding as in Example 1.

The integers of type II can be dealt with as in Example 3 (and, likewise, there are only finitely many possibilities for the smallest prime in the corresponding number 2n − 1 and each of these cases can be analysed further using the solution tableau method).

This rather informal discussion can be turned into a formal proof of Theorem 6. We leave the details to the interested reader.

The examples together with some additional arguments then yield the correctness of the following table (for the notation see the beginning of Section 6).

Table 2: Sparse values of S(n)

1 + 2e min_{μ}(e) min_{ω_{1}}(e) min_{ω}(e) r_{μ}(e) r_{ω_{1}}(e) r_{ω}(e)
5  −  −  7^{2}  0  0  1
13  −  −  31^{2}  0  0  1
29  −  −  631^{2}  0  0  1
37  −  −  127^{2}  0  0  1
53  −  −  14327^{2}  0  0  1
61  −  −  3391^{2}  0  0  1
101  7 · 631  7 · 631  7 · 631  2  2  2
109  −  7^{2} · 73  7^{2} · 73  0  1  2
149  −  −  11471^{2}  0  0  1
157 71 · 631 71 · 631 71 · 631  2  2  2
173  −  71^{2} · 1721 71^{2} · 1721 0  1  2
181  −  −  23671^{2}  0  0  1
197 151 · 919 7^{3} · 151 7^{3} · 151  2  2  2
229  −  −  248407^{2}  0  0  1

Indeed, using the method of solution tableaux we found that for 1 + 2e ≤ 771 there exists an integer n with ω_{1}(n) ≥ 1 and S(n) = 2^{e}, with the exception of 1 + 2e = 5, 13, 29, 37, 53, 61, 149, 181, 229 and the possible exception of 461, 541 and 757. Sometimes the corresponding values of n were quite large, for example, i_{2}(7^{14} · 73) = 709. Thus merely computing i_{2}(n) over a large range of n will leave many values in the image unreached.

7 Analytic aspects

We will see that the scarcity of certain values of S(n) is brought out by analytic number theory.

Note that N_{2}(x) = P_{2}(2x − 1) and hence, by Theorem 2, we have under GRH that

N_{2}(x) = A\frac{x}{log x} + O (\frac{x log log x}{(log x)^{2}}) .

Similarly we see that n ∈ N_{4} iff 2n − 1 = p with p ∈ P_{4} or 2n − 1 = p^{2} with p ∈ P′_{2}. On invoking Theorem 2 we obtain that, under GRH,

N_{4}(x) ≤ A\frac{\sqrt{2x}}{log x} + O (\frac{\sqrt{x} log log x}{(log x)^{2}}) .

We actually conjecture that equality holds. Likewise, we conclude that n ∈ N_{8} if 2n − 1 = p^{3} with p ∈ P′_{2} or 2n − 1 = p with p ∈ P_{6}. Thus, under GRH, we deduce on invoking Theorem 2 that

N_{8}(x) = \frac{8Ax}{45 log x} + O (\frac{x log log x}{(log x)^{2}}) .

The asymptotic behaviour of N_{16}(x) is dominated by the number of prime pairs (p, q) with p < q such that r_{2}(p) = r_{2}(q) = 2, (ord_{2}(p), ord_{2}(q)) = 1 and p · q ≤ 2x − 1. We are inclined to believe that this number is a positive fraction of all pairs (p, q) with p < q and such that p · q ≤ 2x − 1, which, as is well-known [7], grows asymptotically as 2x log log x/ log x. Thus we are tempted to conjecture that

N_{16}(x) ∼ c_{0} \frac{x log log x}{log x},

for some positive constant c_{0}.

The following result shows that the values 2^{e} for which r_{ω_{1}}(e) = 0 deserve the predicate sparse.

Proposition 13 If r_{ω_{1}}(e) = 0, then N_{2^{e}}(x) ≪ \sqrt{x}. If r_{ω_{1}}(e) ≥ 1, then

\frac{x}{log x} ≪ N_{2^{e}}(x) ≤ (ζ(2) + o_{e}(1))\frac{x}{log x}(log log x)^{r_{ω_{1}}(e)−1},

where the lower bound holds under the assumption of GRH.

Proof. In case r_{ω_{1}}(e) = 0, we are counting a subset of the square-full numbers (a number is squarefull if p|n implies p^{2}|n). As is well-known, cf. [31], the number of squarefull integers m ≤ x grows asymptotically as ζ(3/2)\sqrt{x}/ζ(3). The proof of the lower bound is a consequence of Proposition 6 and Theorem 3. As for the upper bound, notice that N_{2^{e}}(x) is bounded above by the number of integers m ≤ 2x−1 such that ω_{1}(m) ≤ r_{ω_{1}}(e). Let C be an arbitrary positive constant. By the method of Sathe-Selberg [7, 32] we find that uniformly for 1 ≤ k ≤ C log log x we have

#\{m ≤ x : ω_{1}(m) = k\} ∼ F (\frac{k}{log log x})\frac{x}{log x} · \frac{(log log x)^{k−1}}{(k − 1)!} ,  (12)

where

F (z) = \frac{1}{Γ(z + 1)} ∏_{p} (1 + \frac{z}{p} + \frac{1}{p^{2} − 1}) (1 − \frac{1}{p})^{z},

where as usual Γ(z) denotes the gamma function. From this estimate the result follows on noting that F (0) = ζ(2). □

We think the upper bound in the latter result is much closer to the truth:

Conjecture 2 Suppose that r_{ω_{1}}(e) ≥ 1, then

\frac{x}{log x}(log log x)^{r_{ω_{1}}(e)−1} ≪ N_{2^{e}}(x) ≪ \frac{x}{log x}(log log x)^{r_{ω_{1}}(e)−1}, x → ∞.

Acknowledgement. We thank Prof. E.W. Clark for pointing out the references given in the proof of Lemma 5 and Prof. Shallit for pointing out reference [34].

Part of the research of the first author was carried out whilst he was temporary assistant professor in the PIONIER-group of Prof. E. Opdam at the University of Amsterdam. He also likes to thank Dr. F. Breuer for bringing [3] to his attention.

References

[1] P. Alles, On a conjecture of Pelikán, J. Combin. Theory Ser. A 60 (1992), 312–313.

[2] T. Beth, D. Jungnickel and H. Lenz, Design theory, Vol. I, 2nd edition, Encyclopedia of Mathematics and its Applications, 69, Cambridge University Press, Cambridge, 1999. xx+1100 pp..

[3] F. Breuer, E. Lötter and A. B. van der Merwe, Ducci sequences and cyclotomic polynomials, preprint.

[4] R. Crandall, K. Dilcher and C. Pomerance, A search for Wieferich and Wilson primes, Math. Comp. 66 (1997), 433–449.

[5] B. Fein, B. Gordon and J. H. Smith, On the representation of −1 as a sum of two squares in an algebraic number field, J. Number Theory 3 (1971), 310–315.

[6] R. K. Guy, Unsolved problems in number theory, Springer, 1994.

[7] A. Hildebrand, On the number of prime factors of an integer, Ramanujan revisited (Urbana-Champaign, Ill., 1987), 167–185, Academic Press, Boston, MA, 1988.

[8] N. F. J. Inglis and J. D. A. Wiseman, Very odd sequences, J. Combin. Theory Ser. A 71 (1995), 89–96.

[9] P. Langevin and P. Solé, Duadic codes over Z_{4}, Finite Fields Appl. 6 (2000), 309–326.

[10] H. W. Lenstra Jr., On Artin’s conjecture and Euclid’s algorithm in global fields, Invent. Math. 42 (1977), 201–224.

[11] J.S. Leon, J.M. Masley and V. Pless, Duadic codes, IEEE Trans. Inform. Theory 30 (1984), 709–714.

[12] H. W. Lenstra, Jr., P. Moree and P. Stevenhagen, Character sums for primitive root densities, in preparation.

[13] R. Lidl and H. Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications 20, Addison-Wesley, Reading, MA, USA, 1983. xx+755 pp..

[14] S. Ling and P. Solé, Duadic Codes over 𝔽_{2} + u𝔽_{2}, Appl. Algebra Engrg. Comm. Comput. 12 (2001), 365–379.

[15] F. J. MacWilliams and A. M. Odlyzko, Pelikan’s conjecture and cyclotomic cosets, J. Combin. Theory Ser. A 22 (1977), 110–114.

[16] F. J. MacWilliams and N. J. A. Sloane, The theory of error correcting codes, (two volumes), North-Holland, Elsevier Science Publisher, 1977.

[17] P. Moree, On the divisors of a^{k} + b^{k}, Acta Arith. 80 (1997), 197–212.

[18] P. Moree, On the distribution of the order and index of g(mod p) over residue classes, arXiv:math.NT/0211259, to appear in J. Number Theory.

[19] L. Murata, The distribution of primes satisfying the condition a^{p−1} ≡ 1(mod p^{2}), Acta Arith. 58 (1991), 103–111.

[20] W. Narkiewicz, Elementary and analytic theory of algebraic numbers, Second edition. Springer-Verlag, Berlin, 1990. xiv+746 pp..

[21] V. Pless, Q-codes, J. Combin. Theory Ser. A 43 (1986), 258–276.

[22] V. Pless, J.M. Masley and J.S. Leon, On weights in duadic codes, J. Combin. Theory Ser. A 44 (1987), 6–21.

[23] J. Pelikán, Contribution to “Problems”, Colloq. Math. Soc. János Bolyai 10, p. 1549, North-Holland, Amsterdam, 1975.

[24] T. D. Rogers, The graph of the square mapping on the prime fields, Discrete Math. 148 (1996), 317–324.

[25] J.J. Rushanan, Duadic codes and difference sets, J. Combin. Theory Ser. A 57 (1981), 254–261.

[26] J. H. Silverman, Wieferich’s criterion and the abc-conjecture, J. Number Theory 30 (1988), 226–237.

[27] C. Small, Sums of three squares and levels of quadratic number fields, Amer. Math. Monthly 93 (1986), 276–279.

[28] M. Smid, Duadic codes, IEEE Trans. Inform. Theory 33 (1987), 432–433.

[29] M. Smid, Duadic codes, Master thesis, University of Eindhoven (1986).

[30] P. Stevenhagen, The correction factor in Artin’s primitive root conjecture, J. Théor. Nombres Bordeaux 15 (2003), 383–391.

[31] D. Suryanarayana, On the order of the error function of the square-full integers, Period. Math. Hungar. 10 (1979), 261–271.

[32] G. Tenenbaum, Introduction to analytic and probabilistic number theory, Cambridge Studies in Advanced Mathematics 46, Cambridge University Press, Cambridge, 1995. xvi+448 pp..

[33] D. Ulmer, Elliptic curves with large rank over function fields, Ann. of Math. 155 (2002), 295-315.

[34] T. Vasiga and J. Shallit, On the iteration of certain quadratic maps over GF (p), Discrete Math. 277 (2004), 219–240.

[35] R. van der Veen and E. Nijhuis, Very odd sequences, Report on second year student project (Dutch, partly in English), 2004, University of Amsterdam, available at http://staff.science.uva.nl/∼alejan/project.html.

[36] S.S. Wagstaff, Jr., Pseudoprimes and a generalization of Artin’s conjecture, Acta Arith. 41 (1982), 141–150.

Max-Planck-Institut für Mathematik, Vivatsgasse 7, D-53111 Bonn, Germany.

e-mail: moree@mpim-bonn.mpg.de

CNRS-I3S, ESSI, Route des Colles, 06903 Sophia Antipolis, France.

e-mail: ps@essi.fr