2 Preparations

2.1 Arithmetic functions

We make use of the following well-known upper bound on the number $\tau (w)$ of divisors of a natural number w (see, for example, in [Reference Iwaniec and KowalskiIK04, Equation (1.81)]).

Lemma 2.1 We have

$$ \begin{align*}\tau(w)\leqslant w^{o(1)}\; \end{align*} $$

as $w \rightarrow \infty $ .

Bateman [Reference Banks and ShparlinskiBat49] gives the following upper bound on the coefficients of cyclotomic polynomials.

Lemma 2.2 We have

$$ \begin{align*}A_n\leqslant\exp\left(\frac{1}{2}\tau(n)\log n\right) \end{align*} $$

for all $n\geq 1$ .

We also need to bound the Euler function of the product of the first odd primes.

Lemma 2.3 Let $k = p_2\ldots p_r$ for some integer $r\geq 2$ . Then

$$ \begin{align*}\varphi(p_2\ldots p_r)= 2e^{-\gamma}\frac{k}{\log \log k}(1+o(1)) \end{align*} $$

as $r\rightarrow \infty $ .

Proof This is a direct application of Mertens’ so-called third theorem (see [Reference MacWilliams and SloaneMer74]):

$$ \begin{align*}\frac{\varphi(p_2\ldots p_r)}{p_2\ldots p_r}= \prod_{i=2}^r \left(1-\frac{1}{p_i}\right) = 2 \prod_{i=1}^r \left(1-\frac{1}{p_i}\right)=\frac{ 2e^{-\gamma}}{\log p_r}(1+o(1)). \end{align*} $$

Using that by the prime number theorem

$$ \begin{align*}k = \exp\left(\left(1 + o(1)\right)p_r\right), \end{align*} $$

we conclude the proof.

Finally, we need the following elementary result (see [Reference Hare, Laishram and StollHLS11, Proposition 2.2]), which asserts that $s_2$ is subadditive.

Lemma 2.4 For any $m, n\in \mathbb {N}$ , we have

$$ \begin{align*}s_2(m+n)\leqslant s_2(m)+s_2(n). \end{align*} $$

2.2 Counting smooth numbers

Let $\Psi (x, y)$ denote the number of y-smooth numbers less than or equal to x. We have the following result obtained after simple manipulations, by combining [Reference Hildebrand and TenenbaumHT86, Theorem 3] and [Reference Hildebrand and TenenbaumHT86, Equation (2.4)].

Lemma 2.5 For $x\geq y\geq 2$ and $1\leqslant c\leqslant y$ , we have

$$ \begin{align*} \Psi(cx, y)=\Psi(x, y)& \left(1+\frac{y}{\log x}\right)^{\log c/\log y}\\ & \qquad \times \left(1+O\left(\frac{\log\log(1+y)}{\log^2 y}\cdot\log\left(1+\frac{y}{\log x} \right) \cdot \log c \right)\right)\\ & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \times \left(1+O\left(\frac{1}{u}+\frac{\log y}{y}\right)\right) \end{align*} $$

uniformly, where $u=\log x/\log y$ .

We note that, for completeness, we have presented Lemma 2.5 in full generality, while we only use it for a fixed $c> 1$ and very small (compared to x) values of y. More precisely, we use Lemma 2.5 in the following form.

Lemma 2.6 Fix real numbers $\alpha , \beta>0$ , $c\geq 1$ and $A>1$ . Then

$$ \begin{align*} \Psi(c\alpha x^\beta, \log^A x)\sim c^{1-1/A}\Psi(\alpha x^\beta, \log^A x) \end{align*} $$

as $x\rightarrow \infty $ .

Proof Using Lemma 2.5 with $\alpha x^\beta $ in place of x and $y=\log ^A x$ , we obtain

$$ \begin{align*} \Psi(c\alpha x^\beta, \log^A x) = (1+ o(1)) \Psi(\alpha x^\beta, \log^A x)\left(1+\frac{\log^A x}{\beta\log x+\log \alpha}\right)^{\log c/A\log\log x}. \end{align*} $$

Finally,

$$ \begin{align*} \left(1+\frac{\log^A x}{\beta\log x+\log \alpha}\right)^{\log c/A\log\log x} & = \left((1/\beta+o(1)) \log^{A-1}x\right)^{\log c/A\log\log x} \\ & = (1+o(1)) \left(\log^{A-1}x\right)^{\log c/A\log\log x} \:. \end{align*} $$

Since $ \left ( \log ^{A-1}x\right )^{\log c/A\log \log x} = c^{1-1/A}$ , the result follows.

We also need an asymptotic formula for $\Psi (x, \log ^A x)$ (see, for example, [Reference Graham and ShparlinskiGra08, Equation (1.14)]).

Lemma 2.7 For any fixed $A>1$ , we have

$$ \begin{align*} \Psi(x, \log^A x)=x^{1-1/A+o(1)} \end{align*} $$

as $x\rightarrow \infty $ .

Finally, we need an upper bound of Harper [Reference HarperHar16] on the number of smooth numbers in an arithmetic progression. In fact, we present it in a very special case tailored to our applications. Namely, let $\Psi (x, y; q,a)$ denote the number of y-smooth numbers less than or equal to x in the residue class a modulo q. By [Reference HarperHar16, Smooth Number Result 3, Section 2.1], we have the following estimate.

Lemma 2.8 For any fixed $A>1$ , $\beta>0$ and $\varepsilon>0$ , we have

$$ \begin{align*}\Psi(x^\beta, \log^A x;q, a)\leqslant (x^\beta/q)^{1-1/A} x^{o(1)} \end{align*} $$

for all a as $q \leqslant x^{\beta -\varepsilon }$ and $x\rightarrow \infty $ .

2.3 Sums involving binomial coefficients

We recall the definition (1.4). We frequently use the following result from [Reference Mauduit and RivatMS77, Chapter 10, Corollary 9].

Lemma 2.9 For any natural number n and $0<\rho \leqslant 1/2$ , we have

$$ \begin{align*}\sum_{0\leqslant k\leqslant\rho n}\binom{n}{k}\leqslant 2^{nH(\rho)}. \end{align*} $$

Furthermore, we also need a bound on the product of binomial coefficient or, in other words, on the sum of their logarithms.

Lemma 2.10 For any integer $n\geq 2$ , we have

$$ \begin{align*}\sum_{k=0}^n \log\binom{n}{k}=\frac{1}{2}n^2+O(n\log n). \end{align*} $$

Proof By the Stirling formula, we have $\log n!=n\log n-n+O(\log n)$ for $n\geq 2$ and, therefore,

$$ \begin{align*} \log\binom{n}{k}=n\log n-k\log k-(n-k)\log (n-k)+O(\log n), \end{align*} $$

whenever $2\leqslant k\leqslant n-2$ and $n\geq 2$ . Summing over all k, we see that

$$ \begin{align*} \sum_{k=0}^n \log\binom{n}{k}=n^2\log n-2\sum_{k=1}^n k\log k+O(n\log n). \end{align*} $$

For the remaining sum, partial summation yields

$$ \begin{align*} \sum_{k=1}^n k\log k&=\frac{n(n+1)}{2}\log n-\int_1^n \frac{\lfloor t\rfloor(\lfloor t\rfloor+1)}{2t}\,\mathrm{d}t \\ &=\frac{1}{2}n^2\log n-\int_1^n \frac{t}{2}\,\mathrm{d} t+O(n\log n) \\ &=\frac{1}{2}n^2\log n-\frac{1}{4}n^2+O(n\log n), \end{align*} $$

and hence, we obtain

$$ \begin{align*}\sum_{k=0}^n \log\binom{n}{k}=\frac{1}{2}n^2+O(n\log n) \end{align*} $$

as claimed.

2.4 Character sums modulo powers of $2$

From [Reference BatemanBS19, Theorem 2.1], we deduce the following estimate for character sums modulo powers of $2$ .

Lemma 2.11 There exists an effective constant $\xi>0$ such that for all integers $k\geq 1$ and all non-principal characters $\chi $ modulo $q=2^k$ , we have

$$ \begin{align*}\sum_{n=M+1}^{M+N} \chi(n)\ll N^{1-\xi\ell^2/k^2} \end{align*} $$

uniformly for all integers M and $N=2^\ell $ , where $\ell $ is an integer such that $\ell \leqslant k$ , where implied constant is absolute.

Proof Assume $\chi $ is induced by the primitive character $\widetilde \chi $ modulo $\widetilde q=2^{k_0}$ with $k_0\geq 1$ and let $1\leqslant \widetilde N\leqslant \widetilde q$ such that $N\equiv \widetilde N\pmod {\widetilde q}$ , that is, $\widetilde N=2^{\ell _0}$ with $\ell _0=\ell $ if $\ell \leqslant k_0$ and $\ell _0=k_0$ otherwise. Then

$$ \begin{align*}\sum_{n=M+1}^{M+N} \chi(n)=\sum_{n=M+1}^{M+N} \widetilde \chi(n)=\sum_{n=M+1}^{M+\widetilde N} \widetilde \chi(n), \end{align*} $$

since complete sums of characters (of length $\widetilde q$ in this case) vanish. By [Reference BatemanBS19, Theorem 2.1], there is an effective constant $\xi _0>0$ such that

$$ \begin{align*}\sum_{n=M+1}^{M+\widetilde N} \widetilde \chi(n)\ll {\widetilde N}^{1-\xi_0{\ell_0}^2/{k_0^2}}\; \end{align*} $$

and the implied constant is absolute. Put $\xi =\min \{1/2, \xi _0\}$ .

Assuming first that $\ell _0=\ell $ , then clearly ${\widetilde N}^{1-\xi {\ell _0}^2/{k_0^2}}\leqslant N^{1-\xi \ell ^2/k^2}$ , so we are done. Now assume that $k_0<\ell $ and $\ell _0=k_0$ . Then we have

$$ \begin{align*} k_0(1-\xi)\leqslant k_0(1-\xi\ell^2/k^2) < \ell(1-\xi\ell^2/k^2), \end{align*} $$

and therefore once again ${\widetilde N}^{1-\xi {\ell _0}^2/{k_0^2}}\leqslant N^{1-\xi \ell ^2/k^2}$ .

2.5 Smooth numbers with some bits prescribed

Using techniques from [Reference GranvilleGS08] and modifying the proof of [Reference ShparlinskiShp06, Theorem 6], we prove the following lemma.

Lemma 2.12 Let $A>1$ and $\varepsilon>0$ be fixed real numbers with $2\varepsilon < 1-1/A$ . Then for sufficiently large n and any binary string $\sigma $ of length

$$ \begin{align*}m\leqslant n_0\left(1-\left(\frac{\left(1-1/A\right)\left(1/A+2\varepsilon\right)}{\xi\left(1-1/A-2\varepsilon\right)}\right)^{1/3}\right)\;, \end{align*} $$

where $n_0=\lfloor (1/2-1/2A-\varepsilon )n\rfloor $ and $\xi $ is the constant from Lemma 2.11, there exist at least $2^{n(1-1/A)-m+o(n)}$ odd n-bit integers which are $n^A$ -smooth and have the bit pattern $\sigma $ at the positions $n_0-1, \dots , n_0-m$ .

Proof Let $\mathcal {W}$ be the set of odd $n^A$ -smooth numbers in the interval $(2^{(n-1)/2}, 2^{n/2}]$ , and let s denote the number defined by the binary string $\sigma $ . We count the number $T(k)$ of solutions $w_1, w_2\in \mathcal {W}$ of $w_1w_2\equiv 2^{n_0-m}s+k\pmod {2^{n_0}}$ for $0\leqslant k<2^{n_0-m}$ . Then the product $w_1w_2$ is $n^A$ -smooth and has n bits as well as the desired bit pattern.

Let $\mathcal {X}$ be the set of multiplicative characters modulo $2^{n_0}$ . As in [Reference GranvilleGS08], recalling the orthogonality relation

(2.1) $$ \begin{align} \sum_{\chi\in\mathcal{X}} \chi(u)=\begin{cases} 0, & \text{if } u\not\equiv 1\quad\pmod{2^{n_0}}, \\ 2^{n_0-1}, & \text{if } u\equiv 1\quad\pmod{2^{n_0}} \end{cases} \end{align} $$

(see, for example, [Reference Iwaniec and KowalskiIK04, Section 3.2]), we can express $T(k)$ as

$$ \begin{align*} T(k)=\frac{1}{2^{n_0-1}}\sum_{w_1,w_2\in\mathcal{W}}\sum_{\chi\in\mathcal{X}} \chi\left((2^{n_0-m}s+k)w_1^{-1}w_2^{-1}\right), \end{align*} $$

where the inverses are taken modulo $2^{n_0}$ (recall that $w_1, w_2\in \mathcal {W}$ are odd). Also observe that $T(k)=0$ if k is even.

If k is odd, separating the contribution from the principal character $\chi _0$ and changing the order of summation, we obtain

$$ \begin{align*} T(k) &= \frac{(\#\mathcal{W})^2}{2^{n_0-1}}+\frac{1}{2^{n_0-1}}\sum_{\substack{\chi\in\mathcal{X} \\ \chi\neq \chi_0}} \chi(2^{n_0-m}s+k) \sum_{w_1,w_2\in\mathcal{W}} \chi\left(w_1^{-1}w_2^{-1}\right) \\ &= \frac{(\#\mathcal{W})^2}{2^{n_0-1}} + \frac{1}{2^{n_0-1}}\sum_{\substack{\chi\in\mathcal{X} \\ \chi\neq \chi_0}} \chi(2^{n_0-m}s+k) \left(\sum_{w\in\mathcal{W}} \chi\left(w^{-1}\right)\right)^2 \;. \end{align*} $$

This yields

(2.2) $$ \begin{align} \sum_{k=0}^{2^{n_0-m}-1} T(k)=\frac{(\#\mathcal{W})^2}{2^m}+\Delta\;, \end{align} $$

where, using $ \chi \left (w^{-1}\right ) = \overline \chi (w)$ , the error term $\Delta $ is given by

$$ \begin{align*}\Delta=\frac{1}{2^{n_0-1}}\sum_{\substack{\chi\in\mathcal{X} \\ \chi\neq \chi_0}}\sum_{k=0}^{2^{n_0-m}-1} \chi(2^{n_0-m}s+k)\left(\sum_{w\in\mathcal{W}} \overline{\chi}(w)\right)^2\;. \end{align*} $$

Now, we estimate $\Delta $ , again following [Reference GranvilleGS08]. Namely, we have

$$ \begin{align*}|\Delta|\leqslant \frac{1}{2^{n_0-1}}\sum_{\substack{\chi\in\mathcal{X} \\ \chi\neq \chi_0}} \left|\sum_{k=0}^{2^{n_0-m}-1} \chi(2^{n_0-m}s+k)\right|\left|\sum_{w\in\mathcal{W}} \chi(w)\right|{}^2 \end{align*} $$

by the triangle inequality. By Lemma 2.11, we have the estimate

$$ \begin{align*}\sum_{k=0}^{2^{n_0-m}-1}\chi(2^{n_0-m}s+k)\ll 2^{(n_0-m)(1-\xi(n_0-m)^2/n_0^2)} \end{align*} $$

for any non-principal character $\chi \in \mathcal {X}$ and $n_0$ sufficiently large. Moreover, by our choice of m and $n_0$ , we may further estimate

$$ \begin{align*} n_0-m& \geq \frac{n_0}{\xi^{1/3}}\left(\frac{\left(1-1/A\right)\left(1/A+2\varepsilon\right)}{1-1/A-2\varepsilon}\right)^{1/3} \\ &=\frac{n_0}{\xi^{1/3}}\left(\frac{1}{1-1/A-2\varepsilon}-1\right)^{1/3}(1-1/A)^{1/3} \\ &\geq\frac{n_0}{\xi^{1/3}}\left(\frac{n}{2n_0}-1+o(1)\right)^{1/3}(1-1/A)^{1/3}\\ &=\frac{n_0^{2/3}}{\xi^{1/3}}(n/2-n_0)^{1/3}(1-1/A)^{1/3}+o(n), \end{align*} $$

and therefore the estimate above becomes

$$ \begin{align*}\sum_{k=0}^{2^{n_0-m}-1}\chi(2^{n_0-m}s+k)\ll 2^{n_0-m-(n/2-n_0)(1-1/A)+o(n)}\;. \end{align*} $$

Thus, we can further estimate

$$ \begin{align*} |\Delta|&\ll 2^{-m-(n/2-n_0)(1-1/A)+o(n)}\sum_{\substack{\chi\in\mathcal{X} \\ \chi\neq \chi_0}} \left|\sum_{w\in\mathcal{W}} \chi(w)\right|{}^2\\ &\ll 2^{-m-(n/2-n_0)(1-1/A)+o(n)}\sum_{\chi\in\mathcal{X}} \left|\sum_{w\in\mathcal{W}} \chi(w)\right|{}^2 \\ &= 2^{-m-(n/2-n_0)(1-1/A)+o(n)}\sum_{\chi \in \mathcal{X}} \sum_{w_1,w_2 \in \mathcal{W}} \chi(w_1w_2^{-1})\;. \end{align*} $$

To estimate the last sum, we change the order of summation and use the orthogonality relations (2.1). Namely, by Lemma 2.8, there are at most $2^{(n/2-n_0)(1-1/A)+o(n)}$ elements of ${\mathcal W}$ in any given residue class modulo $2^{n_0}$ , so we obtain

$$ \begin{align*} \sum_{w_1,w_2 \in \mathcal{W}}\sum_{\chi \in \mathcal{X}} \chi(w_1w_2^{-1})&=2^{n_0-1}\cdot\#\{(w_1, w_2)\in\mathcal{W}^2: w_1\equiv w_2\quad\pmod{2^{n_0}}\} \\ & \leqslant 2^{n_0+(n/2-n_0)(1-1/A)+o(n)} \#\mathcal{W}\;. \end{align*} $$

Therefore, we overall get

$$ \begin{align*}|\Delta|\ll 2^{n_0-m+o(n)}\#\mathcal{W}\;. \end{align*} $$

To compare the error term with the main term, we need to determine $\#{\mathcal W}$ . To do this, observe that for any x, there is a bijection

$$ \begin{align*} \{w\in [1, x/2]:~w \; n^A\text{-smooth}\}&\overset{1\,:\,1}{\longleftrightarrow}\{w\in [1, x]:~w\text{ even}, n^A\text{-smooth}\}, \\ w&\mapsto 2w \end{align*} $$

and thus, the number of odd $n^A$ -smooth numbers up to x is given by $\Psi (x, n^A)-\Psi (x/2, n^A)$ . Therefore, Lemma 2.6 yields

$$ \begin{align*} \#\mathcal{W}&=\left(\Psi(2^{n/2}, n^A)-\Psi(2^{n/2-1}, n^A)\right) \\ &\hspace{2cm}-\left(\Psi(2^{(n-1)/2}, n^A)-\Psi(2^{(n-1)/2-1}, n^A)\right) \\ &\sim \Psi(2^{(n-1)/2-1}, n^A)\left(2^{3(1-1/A)/2}-2^{1-1/A}-2^{(1-1/A)/2}+1\right) \end{align*} $$

and due to

$$ \begin{align*}2^{3(1-1/A)/2}-2^{1-1/A}-2^{(1-1/A)/2}+1=(2^{(1-1/A)/2}-1)^2(2^{(1-1/A)/2}+1)\;, \end{align*} $$

this is a positive proportion of $\Psi (2^{(n-1)/2-1}, n^A)$ . Moreover, according to Lemma 2.7,

$$ \begin{align*} \Psi(2^{(n-1)/2-1}, n^A)& \geq \Psi(2^{(n-3)/2}, (n-3)^A\log^A 2/2^A)\\ & = 2^{(n-3)(1-1/A+o(1))/2}=2^{n(1-1/A+o(1))/2}\;. \end{align*} $$

Combining both results, we deduce that

(2.3) $$ \begin{align} \#\mathcal{W}\geq 2^{n(1-1/A+o(1))/2}\;. \end{align} $$

Therefore, the ratio of the error term to the main term in (2.2) can be bounded by

$$ \begin{align*} \frac{|\Delta|}{(\#\mathcal{W})^2/2^m}&\ll \frac{2^{n_0-m+o(n)}\#\mathcal{W}}{(\#\mathcal{W})^2/2^m}=\frac{2^{n_0+o(n)}}{\#\mathcal{W}}\leqslant \frac{2^{n_0+o(n)}}{2^{n(1-1/A)/2}} \\ &\leqslant \frac{2^{n(1-1/A-2\varepsilon)/2+o(n)}}{2^{n(1-1/A)/2}}=2^{-\varepsilon n +o(n)}=o(1)\;. \end{align*} $$

Thus, putting this result back into (2.2), we obtain

$$ \begin{align*}\sum_{k=0}^{2^{n_0-m}-1} T(k)=\frac{(\#\mathcal{W})^2}{2^m}(1+o(1))\;. \end{align*} $$

Using (2.3) again, we see that this becomes

$$ \begin{align*}\sum_{k=0}^{2^{n_0-m}-1} T(k)\geq \frac{2^{n(1-1/A+o(1))}}{2^m}(1+o(1))=\frac{2^{n(1-1/A+o(1))}}{2^m}\;. \end{align*} $$

To conclude, it still remains to check how many pairs $(w_1, w_2)$ yield the same product $w=w_1w_2$ . However, any such product w satisfies $w\leqslant 2^n$ by construction and hence, by Lemma 2.1, it can occur at most $2^{o(n)}$ times. Therefore, the number of pairwise distinct products is at least

$$ \begin{align*}2^{o(n)} \sum_{k=0}^{2^{n_0-m}-1} T(k) \geq \frac{2^{n(1-1/A+o(1))}}{2^m}\; \end{align*} $$

as claimed.

3 Proof of Theorem 1.1

Let $\varepsilon>0$ . We set

$$ \begin{align*}n_0=\left\lfloor(1/2-1/2A-\varepsilon)n\right\rfloor \quad \text{and} \quad m=\left\lfloor n_0\left(1-\left(\frac{\left(1-1/A\right)\left(1/A+2\varepsilon\right)}{\xi\left(1-1/A-2\varepsilon\right)}\right)^{1/3}\right)\right\rfloor\;. \end{align*} $$

It is also convenient to define

$$ \begin{align*}\mu = m/n \end{align*} $$

and note that there are some constants $c_2> c_1>0$ depending only on A, but not on $\varepsilon $ such that for a sufficiently small $\varepsilon $ ,

$$ \begin{align*}\left(\xi A\right)^{-1/3} +c_1\varepsilon \leqslant \left(\frac{\left(1-1/A\right)\left(1/A+2\varepsilon\right)}{\xi\left(1-1/A-2\varepsilon\right)}\right)^{1/3} \leqslant \left(\xi A\right)^{-1/3} +c_2\varepsilon. \end{align*} $$

Note that the positivity of $c_1$ is crucial for us and, in particular, this implies that for some constants $C_2> C_1>0$ depending only on A, we have

(3.1) $$ \begin{align} \mu_0(A) - C_2\varepsilon\leqslant \mu \leqslant \mu_0(A) -C_1\varepsilon , \end{align} $$

where $\mu _0(A)$ is given by (1.2) with $\zeta = \xi ^{-1/3}$ .

Applying Lemma 2.12 with the above values of $n_0$ and m, we see that the number T of odd n-bit $n^A$ -smooth numbers with a string of m zeros at the positions $n_0-1, \dots , n_0-m$ is at least

(3.2) $$ \begin{align} T\geq\frac{2^{n(1-1/A+o(1))}}{2^m}=2^{(n-m) (1-1/(1-\mu)A)+o(n)}. \end{align} $$

Now, consider the $n-m$ bits that we have not prescribed yet. If at most a proportion $\rho <\vartheta _0(A)$ of them are zeros, where $\vartheta _0(A)$ is given by (1.3), then, by Lemma 2.9, we can have at most

$$ \begin{align*}\sum_{0\leqslant k\leqslant\rho(n-m)} \binom{n-m}{k}\leqslant 2^{(n-m)H(\rho)} \end{align*} $$

different integers. However, since $\rho <\vartheta _0(A)$ , we know that

$$ \begin{align*} H(\rho)< 1-\frac{1}{(1-\mu_0(A) )A } <1-\frac{1}{(1-\mu )A }. \end{align*} $$

Recalling (3.2), we conclude that

$$ \begin{align*}2^{(n-m)H(\rho)} < T \end{align*} $$

if n is sufficiently large.

Thus, at least one of the T odd n-bit $n^A$ -smooth numbers not only has a string of m consecutive zeros, which is by construction, but also has at least a proportion of $\rho $ zeros among the remaining $n-m$ digits. That is, we see from (3.1) that its binary expansion contains at least

$$ \begin{align*} m+\rho(n-m)& = (1-\rho)m +\rho n = n\left(\mu (1-\rho)+ \rho\right)\\ & \geqslant n\left(\mu_0(A) (1-\rho)+\rho - C_2 (1-\rho) \varepsilon\right)\\ & \geqslant n\left(\mu_0(A) + \rho(1-\mu_0(A)) - C_2 (1-\rho) \varepsilon\right) \end{align*} $$

zeros. Choosing $\rho>\vartheta $ concludes the proof since $\varepsilon $ is arbitrarily small.

4 Proof of Theorem 1.2

Put $k=p_2\ldots p_r$ for some $r>2$ and consider $m=2^k+1$ . We assume that $r \rightarrow \infty $ , so we also have $k \rightarrow \infty $ .

We have the following factorization into cyclotomic polynomials:

$$ \begin{align*}m=2^k+1=-\prod_{d\mid k} \Phi_d(-2), \end{align*} $$

and we can bound the factors using Lemmas 2.2 and 2.1 as

$$ \begin{align*} |\Phi_d(-2)|&\ll A_d 2^{\varphi(d)}\leqslant \exp\left(\frac{1}{2}\tau(d)\log d\right)2^{\varphi(d)} \\ &\ll \exp\left(k^{o(1)}\log k\right)2^{\varphi(d)}\ll 2^{\varphi(d)+k^{o(1)}}\leqslant 2^{\varphi(k)+k^{o(1)}}. \end{align*} $$

Moreover, due to our choice of k, Lemma 2.3 implies

$$ \begin{align*} |\Phi_d(-2)& \leqslant 2^{( 2e^{-\gamma}+o(1))k/\log \log k}\\ & \leqslant m^{( 2e^{-\gamma}+o(1))/\log \log k}=m^{( 2e^{-\gamma}+o(1))/\log\log \log m}. \end{align*} $$

In particular, m is $m^{(2e^{-\gamma }+o(1))/\log \log \log m}$ -smooth.

Now, we consider the number

(4.1) $$ \begin{align} N=m^{\ell}, \end{align} $$

where $\ell =\lfloor \beta k\rfloor $ for $\beta =2\alpha \log 2$ . Without loss of generality, we assume that k is large enough so $\ell \geqslant 2$ . Thus N has

(4.2) $$ \begin{align} n=k\ell+O(\ell)=\beta^{-1} \ell^2+O(\ell) \end{align} $$

bits, provided that $k \rightarrow \infty $ . Due to

$$ \begin{align*}\ell\sim\beta k\sim \frac{\beta\log m}{\log 2}=\frac{2\alpha\log N}{\ell}, \end{align*} $$

we also have $\ell \sim (2\alpha \log N)^{1/2}$ . In particular,

$$ \begin{align*} \log \log \log N & = \log \log\left(\ell \log m\right) \leqslant \log \log \left( \left(2 \log m\right)^2\right) \\ & = \log\left( 2 \left(\log \log m + O(1) \right)\right) = \left(1+o(1)\right)\log \log \log m. \end{align*} $$

Therefore, we see that

$$ \begin{align*} m^{( 2e^{-\gamma}+o(1))/\log\log\log m}&=N^{( 2e^{-\gamma}+o(1))/(\ell \log\log \log N)} \\ &=N^{\left(2e^{-\gamma}+o(1)\right)/\left((2\alpha\log N)^{1/2}\log\log \log N\right)} = Y^{1+o(1)}, \end{align*} $$

that is, N is $Y^{1+o(1)}$ -smooth.

We now estimate the sparsity of N. By the binomial theorem, we know that

$$ \begin{align*} N=(2^k+1)^\ell=\sum_{j=0}^\ell \binom{\ell}{j}2^{kj}. \end{align*} $$

Noting that $\binom {\ell }{j}$ can have at most $\log \binom {\ell }{j}/\log 2+1$ binary digits and using the subadditivity of the sum of binary digits guaranteed by Lemma 2.4, we see that Lemma 2.10 shows that the total number of nonzero digits of N is at most

$$ \begin{align*} \frac{1}{\log 2}\sum_{j=0}^\ell \log\binom{\ell}{j}+(\ell+1)&=\frac{1}{2\log 2}\ell^2+O(\ell\log\ell) \\ &=\alpha n+O\left(n^{1/2}\log n\right), \end{align*} $$

where we have used that $\ell ^2=\beta n+O\left (n^{1/2}\right )$ due to (4.2) in the last step. This proves the claim.

5 Proof of Theorem 1.3

We proceed exactly as in the proof of Theorem 1.2 up to the point where we defined N in (4.1). If $\alpha =0$ , we choose $\ell =1$ and are done; otherwise, let $\ell =\lfloor k^\beta \rfloor $ for

$$ \begin{align*} \beta=\frac{\alpha}{2-\alpha}.\end{align*} $$

Without loss of generality, we assume that k is large enough so $\ell \geqslant 2$ . Thus N has

(5.1) $$ \begin{align} n=k\ell+O(\ell)=\ell^{1+1/\beta}+O\left(\ell^{1/\beta}\right) \end{align} $$

bits, provided that $k \rightarrow \infty $ . Due to

$$ \begin{align*} \ell\sim k^\beta \sim \left(\frac{\log m}{\log 2}\right)^\beta= \left(\frac{\log N}{\ell\log 2} \right)^\beta, \end{align*} $$

we also have $\ell \sim (\log N/\log 2)^{\beta /(1+\beta )}$ . In particular,

$$ \begin{align*} \log \log \log N & = \log \log\left(\ell \log m\right) \leqslant \log \log \left( \left(2 \log m\right)^{1+\beta}\right) \\ & = \log\left( (1+\beta) \left(\log \log m + O(1) \right)\right) \\ &= \left(1+o(1)\right)\log \log \log m. \end{align*} $$

Therefore, we see that

$$ \begin{align*} m^{( 2e^{-\gamma}+o(1))/\log\log\log m}&=N^{( 2e^{-\gamma}+o(1))/(\ell \log\log \log N)} \\ &=N^{\left( 2e^{-\gamma}+o(1)\right)/\left((\log N/\log 2)^{\beta/(1+\beta)}\log\log \log N\right)} = Y^{1+o(1)}, \end{align*} $$

that is, N is $Y^{1+o(1)}$ -smooth.

As before, we see that the number of nonzero digits of N is at most

$$ \begin{align*} \frac{1}{2\log 2}\ell^2+O(\ell\log\ell)&=\frac{1}{2\log 2}n^{2\beta/(1+\beta)}+O(n^{\beta/(1+\beta)}\log n) \\ &=\frac{1}{2\log 2}n^\alpha+O(n^{\alpha/2}\log n) \end{align*} $$

due to $\ell =n^{\beta /(1+\beta )}+O(1)$ by (5.1) and this concludes the proof.

6 Comments

It is also interesting to study smooth values amongst balanced integers, that is, positive integers with equally many ones and zeros in their binary expansion.

Using simple counting arguments, one can show that, for any integer n, there exist $2n$ -bit balanced integers which are Y-smooth, where

(6.1) $$ \begin{align} Y = 2^{2n - \left(1/\sqrt{\pi} + o(1)\right)n^{1/2}}. \end{align} $$

Indeed, first, we observe that by the Stirling formula, the number of $2n$ -bit balanced integers is given by

(6.2) $$ \begin{align} \binom{2n-1}{n-1} = \left(1/2\sqrt{\pi} + o(1)\right)\frac{4^n}{n^{1/2}}. \end{align} $$

However, for any $u\in [1,2]$ ,

$$ \begin{align*} \Psi(x, x^{1/u}) = \left(1 -\log u\right) x + O(x/\log x) \end{align*} $$

(see [Reference Graham and ShparlinskiGra08, Equations (1.3) and (1.8)]). Thus, if $u =1 +\eta $ with $\eta \asymp (\log x)^{-1/2}$ , then the number of non- $x^{1/u}$ -smooth numbers $N \leqslant x$ can be estimated as

(6.3) $$ \begin{align} x- \Psi(x, x^{1/u}) = (1+ o(1))\eta x. \end{align} $$

Hence, for a sufficiently small $\varepsilon> 0$ with $\eta = \left (1/2\sqrt {\pi }-\varepsilon \right )n^{-1/2}$ and sufficiently large n, we obtain from (6.2) and (6.3) that

$$ \begin{align*} 4^n - \Psi\left(4^n, 4^{n/\left(1+(1/2\sqrt{\pi} -\varepsilon)n^{-1/2}\right)}\right) < \binom{2n-1}{n-1} , \end{align*} $$

and since $\varepsilon> 0$ is arbitrary, we see that we can take Y as in (6.1).

Furthermore, with a similar technique as in the proofs of Theorems 1.2 and 1.3, one can give an explicit construction of infinitely many rather smooth balanced numbers. Namely, taking

$$ \begin{align*} k_1=p_2\ldots p_r \qquad \mbox{and} \qquad k_2=p_3\ldots p_r=k_1/3, \end{align*} $$

the same argument as above shows that $2^{k_1}+1$ is $2^{(2e^{-\gamma }+o(1))k_1/\log \log k_1}$ -smooth and $2^{k_2}-1$ is $2^{(2e^{-\gamma }+o(1))k_2/\log \log k_2}$ -smooth. Thus, the number $N=(2^{k_1}+1)(2^{k_2}-1)$ is $2^{(2e^{-\gamma }+o(1))k_1/\log \log k_1}=N^{(3e^{-\gamma }/2+o(1))/\log \log \log N}$ -smooth and it has $n = k_1+k_2=4k_2$ total digits, exactly $n/2$ of which are ones.