Kvant Math Problem 723

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m05s
Source on kvant.digital

Problem

Does there exist an infinite set of natural numbers such that none of the numbers in this set, nor any sum of several of them, is a power of a natural number ($a^k$, where $k \ge 2$)?

L. Hurwitz

Exploration

We seek an infinite set $S \subset \mathbb{N}$ such that no element of $S$ and no finite sum of distinct elements of $S$ is a perfect power $a^k$ with $k \ge 2$.

A naive attempt is to take rapidly growing numbers such as $2^n$. However, sums of powers of two produce all positive integers, and in particular values like $4$, $8$, $9$, $16$, so perfect powers inevitably appear among subset sums.

Another attempt is to take primes. This fails because even small combinations produce perfect powers, for instance $2+2=4$ or $2+7=9$.

The structure of the condition suggests an incremental construction: at each step, one adds a new number while preserving the property for all previously formed finite subset sums. The difficulty lies in controlling infinitely many forbidden equalities of the form

$$x + f = a^k,$$

where $f$ is a previously attainable subset sum and $a^k$ ranges over all perfect powers.

The key idea is that at each stage there are only finitely many previous subset sums, while the set of all perfect powers is countable. This allows choosing each new element outside a countable forbidden set.

The central point is to ensure that this inductive avoidance still guarantees that no future combination of elements produces a perfect power.

Problem Understanding

This is a Type D problem: construction and existence.

We must construct an infinite set $S \subset \mathbb{N}$ such that no finite nonempty subset sum equals $a^k$ for any integers $a \ge 1$, $k \ge 2$.

The core difficulty is controlling infinitely many additive constraints simultaneously while ensuring the construction can proceed indefinitely.

The correct strategy should ensure that at each stage only countably many values are forbidden, allowing a choice of a new natural number outside this set.

Proof Architecture

The proof proceeds by constructing an increasing sequence $(x_n)_{n \ge 1}$ such that the set $S = {x_1, x_2, \dots}$ satisfies the required property.

First, a lemma establishes that at stage $n$, the set of all subset sums of ${x_1, \dots, x_{n-1}}$ is finite.

Second, a lemma shows that for any fixed integer $f$, the set of numbers $x$ such that $x+f$ is a perfect power is countable.

Third, combining these, we show that the union of all forbidden choices for $x_n$ is countable and therefore does not exhaust $\mathbb{N}$.

The hardest direction is verifying that the inductive condition ensures no subset sum involving the newly chosen element can later become a perfect power.

Solution

We construct a sequence $x_1 < x_2 < \cdots$ inductively. Let $S_n = {x_1, \dots, x_n}$ and let $\Sigma_n$ denote the set of all finite nonempty subset sums of $S_n$.

We maintain the inductive property that no element of $\Sigma_n$ is a perfect power.

For $n=1$, choose $x_1$ to be any natural number that is not a perfect power.

Assume $x_1, \dots, x_{n-1}$ are chosen and $\Sigma_{n-1}$ contains no perfect power. Define

$$F_{n-1} = { \sum_{i \in I} x_i : \emptyset \ne I \subset {1, \dots, n-1} }.$$

This set is finite because it has at most $2^{n-1}-1$ elements.

We now choose $x_n$.

For each $f \in F_{n-1}$ and each integer pair $(a,k)$ with $a \ge 1$, $k \ge 2$, consider the forbidden value

$$x = a^k - f.$$

If we choose such an $x$, then $f + x = a^k$, violating the condition. Also, we must avoid $x = a^k$ to ensure $x_n$ itself is not a perfect power.

Thus the forbidden set is

$$B_n = {a^k : a \ge 1, k \ge 2} ;\cup; \bigcup_{f \in F_{n-1}} {a^k - f : a \ge 1, k \ge 2}.$$

For fixed $f$, the set ${a^k - f}$ is countable, and the union over finitely many $f$ remains countable. Adding the countable set of perfect powers shows $B_n$ is countable.

Since $\mathbb{N}$ is infinite and $B_n$ is countable, there exists $x_n \in \mathbb{N} \setminus B_n$.

This choice guarantees two properties. First, $x_n$ is not a perfect power. Second, for every $f \in F_{n-1}$ and every perfect power $a^k$, we have $x_n \ne a^k - f$, hence $f + x_n \ne a^k$.

We now verify that $\Sigma_n$ contains no perfect power. Any subset sum in $\Sigma_n$ either does not include $x_n$, in which case it lies in $\Sigma_{n-1}$ and is not a perfect power by the inductive hypothesis, or it includes $x_n$, in which case it has the form $f + x_n$ for some $f \in F_{n-1}$, and this is not a perfect power by construction.

Thus the induction proceeds for all $n$, and the infinite set $S = {x_n : n \in \mathbb{N}}$ satisfies the required property.

Hence such an infinite set exists.

∎

Verification of Key Steps

The crucial point is the claim that the forbidden set $B_n$ does not exhaust $\mathbb{N}$. This depends on the fact that $F_{n-1}$ is finite, so the union over $f \in F_{n-1}$ of countable sets remains countable. Since $\mathbb{N}$ is infinite and every countable subset is a proper subset, at least one natural number remains available.

Another delicate point is ensuring that no later subset sum involving multiple new elements breaks the property. At stage $n$, every subset sum containing $x_n$ uses exactly one decomposition $f + x_n$ with $f$ coming from previous elements, since all other elements in the subset belong to earlier indices. Thus all potential violations are already excluded by the construction of $x_n$.

A final point is that excluding all numbers of the form $a^k - f$ simultaneously prevents all possible perfect power representations involving $x_n$, since any such representation would force $x_n$ to lie in the forbidden set.

Alternative Approaches

A different approach replaces the countability argument with a more arithmetic construction using rapidly growing numbers and modular restrictions. One can choose $x_n$ so large that it avoids all perfect powers in a prescribed interval determined by previous subset sums. However, controlling the density of perfect powers in intervals requires additional estimates and is less direct.

The inductive avoidance method is preferable because it reduces the problem entirely to countability considerations and subset-sum bookkeeping, avoiding analytic estimates on the distribution of perfect powers.