Problem 1717

We will show that the sequence exists for all $n \ge 3$.

For $n = 2$, the sequence cannot exist. If it existed, we would have $a_k = -2a_{2k}$ for all $k$, from which $a_1 = (-2)^r a_{2r}$ for all $r$ by induction. Then $a_1$ would have to be divisible by $2^r$ for all $r$, which is impossible for $a_1 \ne 0$.

Now fix $n \ge 3$. We will show that the desired sequence exists. The construction is a repeated application of the Chinese Remainder Theorem, but the details require substantial care.

First we prove two lemmas.

Lemma 1. It is possible to partition the positive integers into subsets $S_1, S_2, S_3, \dots$ so that for every positive integer $k$,
(i) the numbers $(n-1)k$ and $nk$ are in the same subset, and
(ii) the numbers $k, 2k, \dots, (n-2)k$ are all in strictly earlier subsets than $(n-1)k$.

*Proof.* Define a function $f$ from the positive integers to the positive reals as follows. Let $P$ be the set of primes dividing $n$. No element of $P$ divides $n-1$. For any positive integer $k$, write its prime factorization $k = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$, and then define
$$f(k) = \prod_{p_i \notin P} p_i^{e_i} \cdot \prod_{p_i \in P} (p_i^{e_i})^{\log_n(n-1)}.$$
Notice that for every $k$, we have
$$f((n-1)k) = (n-1)f(k) = f(nk), \qquad (4)$$
whereas for each $t = 1, 2, \dots, n-2$, we have
$$f(tk) \le tf(k) < f((n-1)k). \qquad (5)$$
Also notice that for each $k$, $f(k) \ge k^{\log_n(n-1)}$, which implies that for any fixed $C$, there can only be finitely many values of $k$ with $f(k) < C$. Therefore, we may arrange the elements of the image of $f$ in the increasing order $x_1 < x_2 < x_3 < \dots$. Now let $S_i = f^{-1}(x_i)$ for each $i$. The sets $S_i$ are a partition of the positive integers, and (4) and (5) ensure that they satisfy (i) and (ii), respectively. $\square$

Lemma 2. Let $p$ and $q$ be relatively prime positive integers and $t_1, t_2, \dots, t_r$ arbitrary integers. Then it is possible to choose nonzero integers $b_1, b_2, \dots, b_{r+1}$ such that
$$pb_i + qb_{i+1} = t_i \quad \text{for } i = 1, 2, \dots, r. \qquad (6)$$
*Proof.* We use induction on $r$. If $r=1$, then since $p$ and $q$ are relatively prime, we can find $c, d$ such that $pc+qd=1$. Then $b_1 = ct_1$ and $b_2 = dt_1$ satisfy (6). Now suppose we have $b_1, \dots, b_r$ satisfying (6) for $i=1, 2, \dots, r-1$. If we choose any integer $k$ and replace each $b_i$ with $b'_i = b_i + (-1)^i p^{i-1} q^{r-i} k$, then (6) still holds for $i=1, 2, \dots, r-1$, and $pb'_r = pb_r + (-1)^r p^{r-1} k$. Since $p$ and $q$ are relatively prime, we can choose $k$ so as to make $pb'_r$ congruent to $t_r$ modulo $q$, and then we take $b_{r+1} = (t_r - pb'_r)/q$. Then the numbers $b'_1, b'_2, \dots, b'_r, b_{r+1}$ satisfy (6) for $i=1, 2, \dots, r$.

This shows that we can find $b_1, b_2, \dots, b_{r+1}$ satisfying (6), but they may not all be nonzero. However, once again, we can make the replacements $b'_i = b_i + (-1)^i p^{i-1} q^{r+1-i} k$ for any integer $k$, and the new sequence still satisfies (6). By an appropriate choice of $k$, we can ensure each $b'_i$ is nonzero. $\square$

Now both lemmas are proven, and we resume the main proof. We will construct terms of the sequence inductively, but not in the order $a_1, a_2, \dots$.

Suppose $S$ is any set of positive integers, and we have chosen nonzero integers $a_k$ for each $k \in S$. Say that there is a *conflict* in $S$ if there exists some $k$ such that $k, 2k, \dots, nk$ are all in $S$, and
$$a_k + 2a_{2k} + \dots + n a_{nk} \neq 0.$$
Let $S_1, S_2, \dots$ be as given by Lemma 1. We will inductively define our sequence as follows:

a. *Step 1:* Choose nonzero values $a_k$ for all $k \in S_1$ simultaneously, without creating a conflict in $S_1$.

b. *Step $t > 1$:* Given the values of $a_k$ for $k \in S_1 \cup \cdots \cup S_{t-1}$ chosen at previous steps, choose nonzero integers $a_k$ for all $k \in S_t$ simultaneously, without creating a conflict in $S_1 \cup \cdots \cup S_t$.

If we can show that each step of this process can indeed be carried out, then it will eventually define $a_k$ for all positive integers $k$, satisfying the required condition
$$a_k + 2a_{2k} + \cdots + n a_{nk} = 0 \qquad (7)$$
for all $k$ (since no conflicts are created).

For Step 1, Lemma 1 implies we can choose $a_k$ arbitrarily for $k \in S_1$ without creating any conflicts, since $(n-1)k, nk \notin S_1$ for all $k$. Now for Step $t > 1$, suppose the $a_k$ have been assigned already for all $k \in S_1 \cup S_2 \cup \cdots \cup S_{t-1}$. We need to assign $a_k$ for $k \in S_t$ without creating any new conflicts. This just requires that the new assignments satisfy (7) for all integers $k$ such that $(n-1)k$ and $nk$ are in $S_t$. For any other value $k$, either $\{k, 2k, \dots, nk\} \nsubseteq S_1 \cup \cdots \cup S_t$ so no conflict can be created, or else Lemma 1 implies $\{k, 2k, \dots, nk\} \subseteq S_1 \cup \cdots \cup S_{t-1}$ so that the corresponding constraint (7) has been dealt with at an earlier step.

Thus for each $k$ such that $(n-1)k, nk \in S_t$, we have a constraint
$$(n-1)a_{(n-1)k} + n a_{nk} = X_k, \qquad (8)$$
where $X_k = -(a_k + \cdots + (n-2)a_{(n-2)k})$ is determined by the assignments made at previous steps. We just need to show that it is possible to choose $a_k$ for all $k \in S_t$ such that all these constraints are satisfied.

Form a directed graph whose vertices are the elements of $S_t$, with an edge leading from $(n-1)k$ to $nk$ whenever both numbers are in $S_t$. Then every component of this graph is either a single vertex or a (directed) path. We wish to show that nonzero integer values can be assigned to elements of $S_t$ so that for each edge, the corresponding constraint (8) is satisfied. It suffices to show this for each component of the graph. If the component is a single vertex, any nonzero value works. Otherwise, it is a path $k_1, k_2, \dots, k_{r+1}$, and Lemma 2 ensures that we can choose nonzero integer values for $a_{k_1}, a_{k_2}, \dots, a_{k_{r+1}}$ so as to satisfy (8) for each edge.

This shows that each step of our constructive process can indeed be performed successfully, eventually constructing every term of the sequence.

(By Dai Yang). We claim that such a sequence exists for all $n$ except $n = 2$. If we assume that $n = 2$, then
$$a_1 = -2a_2 = 4a_4 = -8a_8 = \dots$$
which is impossible since $a_1$ cannot be divisible by arbitrarily large powers of 2. Thus no valid sequence exists for $n = 2$.

For $n \ge 3$, we begin with the following lemma.

Lemma 3. If there exists a multiplicative function $f(x)$ from $\mathbb{N}$ to $\mathbb{Z}$ such that $f(x) \ne 0$ for all $x$ and
$$f(1) + 2f(2) + \cdots + n f(n) = 0,$$
then there exists a sequence $\{a_i\}$ satisfying the desired conditions.

*Proof.* Assume that $f(x)$ satisfies the hypothesis. Let $a_k = f(k)$ for all $k$. Since $f(x)$ is multiplicative, we have for all positive integers $k$ that
$$\begin{aligned} a_k + 2a_{2k} + \dots + n a_{nk} &= f(k) + 2f(2k) + \dots + n f(nk) \\ &= k f(1) + 2k f(2) + \dots + n k f(n) \\ &= k(f(1) + 2f(2) + \dots + n f(n)) \\ &= 0. \end{aligned} \quad \square$$

We now use Lemma 3 to establish the following lemma.

Lemma 4. If there exist primes $p$ and $q$ satisfying $\sqrt{n} < q < p \le n$ and $p > \frac{n}{2}$, then there exists a sequence $\{a_i\}$ satisfying the desired conditions.

*Proof.* Let $p$ and $q$ be given. For a prime $r$, define $v_r(k)$ to be the largest exponent $v$ such that $r^v \mid k$. Let $f(x) = a^{v_p(x)} b^{v_q(x)}$ for all positive integers $x$, where $a$ and $b$ are nonzero integers. Clearly $f(x)$ is a multiplicative function. We will find suitable values for $a$ and $b$ so that $f(x)$ satisfies the conditions of Lemma 3.

Let the multiples of $q$ that are less than or equal to $n$ be $q, 2q, \dots, m q$ for some $m$. Since $\sqrt{n} < q$, we have $m < q$. Note also that the only multiple of $p$ that is less than or equal to $n$ is $p$ itself. Hence, for all $\ell$ satisfying $1 \le \ell \le n$, we have
$$f(\ell) = \begin{cases} a & \text{if } \ell = p \\ b & \text{if } \ell = q, 2q, \dots, m q \\ 1 & \text{otherwise.} \end{cases}$$
Therefore, for some constant $d$, we have
$$f(1) + 2f(2) + \dots + n f(n) = a p + b q + 2 b q + \dots + m b q + d = a p + b \frac{q m(m+1)}{2} + d. \quad (9)$$
Note that $m < q < p$, so that $\text{gcd}(p, \frac{q m(m+1)}{2}) = 1$. By Bézout's Identity, there exist integers $a'$ and $b'$ for which $a' p + b' \frac{q m(m+1)}{2} = 1$, hence after appropriate scaling, we obtain $a$ and $b$ so that
$$a p + b \frac{q m(m+1)}{2} = -d.$$
Then (9) reduces to
$$f(1) + 2f(2) + \dots + n f(n) = 0.$$
Note that we can also stipulate that $a$ and $b$ be nonzero. Therefore, $f(x)$ satisfies the hypothesis of Lemma 3, so a valid sequence $\{a_i\}$ exists. $\square$

It now suffices to list for each $n \ge 3$ either a function $f(x)$ satisfying Lemma 3 or a pair of primes $p$ and $q$ satisfying Lemma 4.

* If $n = 3$, let $f(x) = (-1)^{v_3(x)}$. Note that $f(1) + 2f(2) + 3f(3) = 0$, as required by Lemma 3.
* If $n = 4$, let $f(x) = (-1)^{v_2(x)}(-1)^{v_3(x)}$.
* If $n = 5, 6, 7, 8$, let $p = 5$ and $q = 3$.
* If $n = 9, 10$, let $p = 7$ and $q = 5$.
* If $11 \le n \le 16$, let $p = 11$ and $q = 7$.
* If $n > 16$, by Bertrand's Postulate, we can find a prime $p$ satisfying $\frac{n}{2} < p \le n$, and a prime $q$ satisfying $\frac{n}{4} < q \le \frac{n}{2}$. For all $n > 16$, we have $\frac{n}{4} > \sqrt{n}$, so $p$ and $q$ satisfy the conditions of Lemma 4.

This exhausts all values of $n \ge 3$, so we are done.