On the restricted sumsets containing powers of an integer (Q6056560)

Let $\mathbb N$ be the set of positive integers, $[a,b] = \{n \in \mathbb Z; a \le n \le b\}$, and $\gcd A$ be the greatest common factor of the elements of $A$. For $h \ge 1$, define the $h$-fold sumset and the $h$-fold restricted sumset \[ hA = \{a_1+\dots+a_h; a_1, \dots, a_h \in A\}, \text{ and } h\wedge A = \{a_1+\dots+a_h; a_1, \dots, a_h \in A, a_i \neq a_j \text{ if } i \neq j\}, \] respectively. Let $A(n) = \sum_{\substack{1 \le a \le n\\a \in A}} 1$. For $c \in \mathbb Z$, let $c-A = \{c-a; a \in A\}$. \textit{P. Erdős} [in: Graph theory and its applications: East and West. Proceedings of the first China-USA international conference, held in Jinan, China, June 9--20, 1986. New York: New York Academy of Sciences. 132--145 (1989; Zbl 0790.11015)] conjectured that if $n \in \mathbb N$ and $A \subset [1,3n]$ with $|A| \ge n+1$, then there is a power of $2$ that can be represented as the sum of distinct elements of $A$. Then \textit{P. Erdős} and \textit{G. Freiman} [J. Number Theory 34, No. 1, 1--12 (1990; Zbl 0697.10047)] proved that this conjecture holds for sufficiently large $n$, and they showed that there are at most $c \log n$ pairwise distinct elements of $A$ the sum of which is a power of $2$, where $c > 0$ is absolute. At the same time, \textit{M. B. Nathanson} and \textit{A. Sárközy} [Acta Arith. 54, No. 2, 147--154 (1989; Zbl 0693.10040)] proved that at most $30,961$ distinct elements are needed. After some improvements on such results (see [\textit{M. B. Nathanson} and \textit{A. Sárközy}, Acta Arith. 54, No. 2, 147--154 (1989; Zbl 0693.10040); \textit{G. A. Freiman}, in: Sets, graphs and numbers. A birthday salute to Vera T. Sós and András Hajnal. Amsterdam: North-Holland Publishing Company. 279--286 (1992; Zbl 0796.11005); \textit{V. F. Lev}, Combinatorica 16, No. 3, 413--416 (1996; Zbl 0862.11008); \textit{V. F. Lev}, Acta Arith. 132, No. 3, 197--204 (2008; Zbl 1143.11010)]), \textit{H. Pan} [J. Number Theory 117, No. 1, 216--221 (2006; Zbl 1101.11045)] showed that for any $\varepsilon>0$ and any sufficiently large $n \in \mathbb N$, if $A \subset [1,n]$ with $\gcd A = 1$ and $|A| > \varepsilon n$, then there are integers $x \ge 0$ and $k = k(\varepsilon) \ge 1$ such that $2^x \in kA$. The following question is naturally to be considered. Problem 1.1. How dense can $A$ be if no power of $2$ can be represented as the sum of distinct elements of $A$? The paper answer this question. For $r \in \mathbb N$, $r \ge 2$, let \[ m(r) = \min\{w \in \mathbb N; rad(w) \mid r \text{ and }r\text{ is not a primitive root of }w\}, \] where $rad(1)=1$ and $rad(w)$ is the product of all the distinct prime factors of $w$. It is easy to see that $m(r) \ge 3$. For $r \in \mathbb N$, $r \ge 2$, let $p$ be the least prime with $p \nmid r$ and let \[ M(r) = \{s \in \mathbb N; 1 < s < m(r) \text{ and }r\text{ is a primitive root of }s\}. \] Let \[ h(r) = \begin{cases} r(m(r)-1) &\text{ if }r\text{ is not a primitive root of }p, \\ \max\{ 2\lceil r(m(r)-1)/2 \rceil, \max_{s \in M(r)} f_r(s)\} &\text{ if }r\text{ is a primitive root of }p, \end{cases} \] where $f_r(s) = \frac{1}{s}(r^{\varphi(s)} - 1)m(r) + (r^{\varphi(s)} + 1)\lceil s^{-1}m(r) - 1 \rceil + 1$, and $\varphi(s)$ is the Euler's totient function. For $A \subset \mathbb N$, if there is a power of $r$ that can be represented as the sum of distinct elements of $A$, then $rad(\gcd A) \mid r$. Let $A_1 \subset A$ be the set of all elements which are the middle terms of at least $h(r)$ three-term arithmetic progressions in $A$. Let $|A| \ge 2(h(r)-1)$. The main results of this paper are the following. Theorem 1.2. Let $r \in \mathbb N$, $r \ge 2$. For $n \in \mathbb N$ sufficiently large, if $A \subset [1,n]$ with $rad(\gcd A) \mid r$ and $|A| > \frac{n}{m(r)}$, $|A_1| \ge \frac{n}{m(r)\gcd A}+1$, then there is a power of $r$ that can be represented as the sum of at most $h(r)$ distinct elements of $A$. Theorem 1.3. Let $r \in \mathbb N$, $r \ge 2$, and let $\varepsilon > 0$ be real. For $n \in \mathbb N$ sufficiently large, if $A \subset [1,n]$ with $rad(\gcd A) \mid r$ and $|A| > \left( \frac{1}{m(r)} + \varepsilon \right)n$, then there is a power of $r$ that can be represented as the sum of at most $h(r)$ distinct elements of $A$. Theorem 1.4. Let $r \in \mathbb N$, $r \ge 2$. Then for infinitely many positive integers $n$, there exists $B \subset [1,n]$ with $\gcd B = 1$ and $|B| > \frac{n}{m(r)}$ such that no power of $r$ can be represented as the sum of distinct elements of $B$. For an infinite set of positive integers, the authors obtained similar results (see Corollary 1.5).