Almost all primes have a multiple of small Hamming weight

Abstract

Recent results of Bourgain and Shparlinski imply that for almost all primes $p$ there is a multiple $mp$ that can be written in binary as $mp=1+2^{m_1}+\cdots +2^{m_k},1\le m_1<\cdots <m_k,$ with $k=66$ or $k=16$, respectively. We show that $k=6$ (corresponding to Hamming weight $7$) suffices. We also prove there are infinitely many primes $p$ with a multiplicative subgroup $A=<g>\subset {\mathbb{F}}_p^{\ast }$, for some $g\in \{2,3,5\}$, of size $|A|\gg p/(\log p{)}^3$, where the sum-product set $A\cdot A+A\cdot A$ does not cover ${\mathbb{F}}_p$ completely.

References in corpus (5)

• Some new inequalities in additive combinatorics
• On the period of the linear congruential and power generators
• Divisors of shifted primes
• An improved estimate on sums of product sets
• Additive properties of product sets in an arbitrary finite field