Powers of a Prime in the Image of Summatory Valuation Functions

Introduction

For a positive integer $k$ let $v_2(k)$ denote the exponent of 2 in $k$. In a joint paper with J. Dixmier, J.-L. Nicolas considered the function

which is the exponent of $1+X$ in the factorization of $(1+X)(1+X^2)\cdots(1+X^n)$ into irreducible factors over $\mathbb{F}_2[X]$, and in his list of open questions [1] he asked how often a power of 2 belongs to the image of $c$. The sequence $(c(n))_{n\ge1}=1,3,4,8,9,11,12,20,\ldots$ of the partial sums of the highest power of 2 dividing $k$ is the sequence M2344 of the encyclopedia of Sloane and Plouffe [2]. It satisfies the recurrence $c(2n)=2c(n)+n$ and the formulas $c(2^r)=2^{r-1}(r+2)$ and $c(2^r-1)=r2^{r-1}$ [1], and the recurrence splits at half, a class of recurrences whose identities and periodic oscillations are studied by Hwang, Janson and Tsai [3]. With

Nicolas showed that $A(x)\to\infty$ and $B(x)\to\infty$, and asked whether the behaviour of $A(x)$ can be made precise; his table gives, for instance, the values 635 for $x=1000$ and 5963 for $x=10000$ [1], which are the numbers of exponents $1\leq a\leq x$ in $\mathcal{A}$, that is $A(x)-1$ in the notation (2), since $c(1)=2^0$ (§ 10). He obtained these limits from three families: $2^a\notin c(\mathbb{N})$ when $a=2^r+r-2$; $a+(2^a-11)/3\in\mathcal{A}$ for odd $a$; and $a+(2^a-10)/3\notin\mathcal{A}$ for even $a$ [1].

The same list contains a question on a family of fractions, namely the size of the largest numerator $A(N)$ of $\prod_{n\leq N}((n+1)/n)^{\varepsilon(n)}$ with $\varepsilon(n)\in\{-1,0,1\}$; for that question de la Bretèche, Pomerance and Tenenbaum proved $\log A(N)=\{\kappa+o(1)\}N\log N$ with an explicit constant $\kappa\approx0.107005$ [4]. The present paper is concerned with the question on $c(n)$ only.

Contributions. We prove the following results.

• The identity $c(n)=n+\frac{1}{2}\sum_{i\in\mathcal{B}(n)}2^i$, where $\mathcal{B}(n)$ is the set of positions of the binary digits 1 of $n$, equivalently $c(n)=n+\sum_{k\geq1}2^{k-1}\lfloor n/2^k\rfloor$, and the equivalence $a\in\mathcal{A}\Longleftrightarrow2^{a+3}=\sum_{j\in T}2^{j2^j}$ for a finite set $T$ of positive integers (Lemma 2.1, Theorem 2.2).

• The numbers $j2^j$ form a superincreasing sequence. Consequently, for every $a\geq0$ there is at most one integer $K\geq2$ that can be the largest element of $T$, namely the solution of $K+\lceil\log_2K\rceil=a+3$, and such a $K$ fails to exist exactly for $a=2^r+r-2$, $r\geq1$ (Theorem 3.3). This recovers the first family of Nicolas and shows that it is the only obstruction of this kind.

• A recursion on pairs of integers bounded by $a+3$ that decides whether $a\in\mathcal{A}$ in at most $a+1$ steps, without handling integers of size $2^a$ (Theorem 4.1, Corollary 4.2).

• Infinite explicit families of members of $\mathcal{A}$, given by the closed formula $c(2^{K-2}+2^{K-s-2})=2^{K+h-3}$ for $s=2^k$, $k\geq0$, $h\equiv k\pmod{2^k+1}$ and $K=(2^{h+s}+s)/(2^s+1)$ (Theorem 5.1), and infinite explicit families of non-members, indexed by $s=3$ and by $s=2^i$, $i\geq1$ (Theorem 6.1). The second and third families of Nicolas are the cases $s=1$ of Theorem 5.1 and $s=2$ of Theorem 6.1. These families are complete in the following sense: they are exactly the exponents that Algorithm 1 decides in at most one iteration (Theorem 6.2).

• Explicit lower bounds for both counting functions (Theorem 7.1):

so that $\frac{5}{4}+\frac{E}{2}=2.0533475\ldots$.

• The states of the recursion form a forest: the roots are the states $(J,0)$, one at each level, and the failing states, whose number up to level $L$ is given by an explicit formula; each state $(J',w')$ has exactly $v_2(J'+1+w')$ children; and the initial states are the states with $J+1+w$ a power of 2 (Theorem 8.4). The root of the tree of a successful state is determined by the least element of its representing set, and exactly half of the successful states of each level lie in the tree of the root $(1,0) (Proposition 8.5). The sets $S_J$ satisfy the recursion $S_J=\{c/2:c\in S_{J-1}\}\cup\{(c+J)/2:c\in S_{J-1}\text{ odd}\}$ for odd $J$ and $S_J=\{c/2,c+J/2:c\in S_{J-1}\text{ even}\}$ for even $J$; in particular $S_J$ is periodic with period $J/2$ for even $J$ (Theorem 8.6). The symmetry yields three further explicit families, among them $c(2^{2^r}-1)=2^{2^r+r-1}$ (Theorem 8.7), and the improved bounds $A(x)\geq(3.9655\ldots+o(1))\log_2x$ and $B(x)\geq(2.8178\ldots+o(1))\log_2x$ (Theorem 8.8). The sets $S_J$ of successful states, the roots $(J,0)$: the number $N(J)=|S_J|$ counts the sets $T\subseteq\{1,\ldots,J\}$ with $\sum_{j\in T}j2^j\equiv0\pmod{2^{J+1}}$, $S_J$ is symmetric under $w\mapsto J-1-w$, $N(2k+1)=N(2k)$, and $4\mid N(J)$ for $J\geq4$ (§ 8).

• The analogue for every prime $p$ (§ 9), with the complete description of the immediate failures, the bottom-up recursion and the symmetry $w \mapsto(p-1)K-w$ (Theorems 9.6 and 9.7): $c_p(n)=\sum_{k\le n}p^{v_p(k)}$ is the exponent of $1-X$ in $(1-X)(1-X^p)\cdots(1-X^{p^n})$ over $\mathbb{F}_p[X]$; the reduction to digit sums of the numbers $p^i((p-1)i+p)$, the unique candidate, the exponents $(p^g-1)/(p-1)+g-1$ without candidate, the recursion, and explicit families, among them a family of non-members with no analogue for $p=2$ (Theorems 9.3, 9.4 and 9.5).