Woot induction handout p8 moment. By taking the worst case scenario where this is the only ${\mathbb Q}$-linear relation between $b_i$, it's equivalent to find a partition ${\mathbb N} = S_1 \sqcup \dots \sqcup S_{2024}$ to follow the satisfying condition. For all positive integers $d$, we need to have that \[ (G_1(n, d, S_1) \colon G_2(n, d, S_2) \colon \dots \colon G_{2024}(n, d, S_{2024})) = (b_1 : b_2 : \dots : b_{2024}) \]occurs infinitely many times where $G_i(n, d, S) = \sum_{t \in S, t \le n} t^d$. We can do this if we have the following lemma, at which point we can do something like "create an occurence for $d=1$, then $2$, $1$, then $3$, $2$, $1$" and so forth such that each $d$ gets infinitely many occurences. Problem: Let $\{1, 2, \dots, n\} = S_1 \sqcup \dots \sqcup S_{2024}$ be an arbitrary partition and let $d$ be a fixed integer. Show that there exists an $n'$ and $\{1, 2, \dots, n'\} = S_1' \sqcup \dots \sqcup S_{2024}'$ such that \[ (G_1(d, S_1') \colon G_2(d, S_2') \colon \dots \colon G_{2024}(d, S_{2024}')) = (b_1 : b_2 : \dots : b_{2024}) \]where $S_i'$ contains $S_i$ for each $1 \le i \le 2024$ and where $G_i(d, S) = \sum_{t \in S} t^d$. We now reduce this to the case of replacing $2024$ with a generalized $t$ and $b_1 = b_2 = \dots = b_t = 1$. Problem: Let $t$ and $d$ be fixed integers. Show that there exists an $n$ such that the partition $\{1, 2, \dots, n\} = S_1 \sqcup \dots \sqcup S_{t}$ satisfies \[ \sum_{s \in S_1} s^d = \sum_{s \in S_2} s^d = \dots = \sum_{s \in S_t} s^d \]where $S_i$ contains $i$ for each $1 \le i \le t$. Proof. We induct on the stronger condition of \[ \sum_{s \in S_1} s^i = \sum_{s \in S_2} s^i = \dots = \sum_{s \in S_t} s^i \]holding for all $0 \le i \le d$. We induct on $d$. Let $S_{d,i}$ be the corresponding set $i$ for the $d$th iteration. Let $n_d$ be the value of $d$. Define $s_{d,i}$ as the common value for $\sum_{s \in S_{d,j}} s^i$ over all $j$. For the base case of $d = 0$, take $S_{0,1} = \{1, 2t\}, S_{0,2} = \{2, 2t-1\}, \dots S_{0,t} = \{t, t+1\}$ so $n_0 = 2t$. Then for induction, define \[ S_{k+1,i} = \bigsqcup_{1 \le n \le t} (S_{k,n+i-1} + n_k \cdot n) \]where indices are taken cyclically and $A + c = \{a + c \mid a \in A\}$. We then have for $0 \le \ell \le k$, that \begin{align*} \sum_{s \in S_{k+1,i}} s^\ell &= \sum_{1 \le n \le t} \sum_{a \in S_{k,n+i-1}} (a + n_k \cdot n)^\ell \\ &= \sum_{1 \le n \le t} \sum_{a \in S_{k,n+i-1}} \left(\sum_{j=0}^{\ell} \binom{\ell}{j} a^j \cdot (n_k \cdot n)^{\ell-j}\right) \\ &= \sum_{1 \le n \le t} \sum_{j=0}^{\ell} \left(\sum_{a \in S_{k,n+i-1}} \binom{\ell}{j} a^j \cdot (n_k \cdot n)^{\ell-j}\right) \\ &= \sum_{1 \le n \le t} \sum_{j=0}^{\ell} \binom{\ell}{j} \left(s_{k,j} \cdot (n_k \cdot n)^{\ell-j}\right) \\ \end{align*}which is independent of the value chosen for $i$. Finally, for $\ell = k+1$, we have that \begin{align*} &\sum_{s \in S_{k+1,i}} s^{k+1} = \sum_{1 \le n \le t} \sum_{a \in S_{k,n+i-1}} (a + n_k \cdot n)^{k+1} \\ &= \sum_{1 \le n \le t} \sum_{j=1}^{k+1} \binom{k+1}{j} \left(s_{k+1,j} \cdot (n_k \cdot n)^{\ell-j}\right) + \sum_{1 \le n \le t} \sum_{a \in S_{k,n+i-1}} \binom{k+1}{0} \left(a^0 \cdot (n_k \cdot n)^{k+1}\right) \\ \end{align*}The first term is independent of $i$, and since $|S_{k,n+i-1}|$ is independent of $i$ as well, the second term is also independent of $i$. $\blacksquare$ Remark: This is a multivariable variant of the Prouhet-Tarry-Escott problem. For a fun paper about latin squares with this exact claim, and Thue-Morse, see this cool paper. An explicit example for $t = 3, d = 2$ can be found by taking $S_1 = \{1, 6, 14, 17, 9, 10\}$, $S_2 = \{7, 12, 2, 5, 15, 16\}$, and $S_3 = \{13, 18, 8, 11, 3, 4\}$. The sum of squares of the elements of $S_i$ are $703$ regardless of $i$. Then to prove the above claim, take $t$ such that $t \cdot \frac{\min(b_1, \dots, b_{2024})}{b_1 + \dots + b_{2024}} \ge n, b_1 + \dots + b_{2024} \mid t$ to get $S_1, S_2, \dots, S_t$. We take $S_i'$ as the union of $\bigcup_{n \in S_i} S_n$ with unchosen $t \cdot \frac{b_i}{b_1 + \dots + b_{2024}} - |S_i|$ elements chosen from $\{S_{n+1}, \dots, S_t\}$.

I accidentally wrote a special case of this problem March last year; proceeded to solve in 30 minutes AFTER TEST. We will drop the pairwise distinct condition for obvious reasons. WLOG we may assume all the $b_i$ are $1$; if some are not one we'll just append it again to the list of reals until it is $1$. Let there be $k$ of these. We will consider the following construction inductively: We start with $a_1, \dots, a_k$. Then apply the following process: Take the current sequence, copy it $k-1$ times, then shift the copies up by $1$, $2$, ... $k-1$, then append. Take indices modulo $k$. For $k=3$, the construction is as follows: \[ ([a_1, a_2, a_3], [a_2, a_3, a_1], [a_3, a_1, a_2]), ([a_2, \dots \](here the groupings are used to indicate when sequences are copied.) We claim this works. Firstly note that if we split into blocks of $k$, we obtain a degree $d-1$ polynomial in terms of $n$, which is linear in all the $a_i$. Now our construction does what we want it to do: if you consider summing $k$ of these blocks, the highest degree term just has indices cycle, since the sum is of the form \[ P(a_1, a_2, \dots, a_k, n) + P(a_2, a_3, \dots, a_1, n+k) + \cdots + P(a_k, a_1, \dots, a_{k-1}, n+k(k-1)) \]for a multivariate polynomial $P$. Viewing the highest degree terms in $n$, we see that $n + \text{constant}$ doesn't affect the coefficients, which is linear in all the $a_i$. By the cyclic property of our sequence, and the fact that $\sum a_i = 0$, we find that the highest degree term in $n$ vanishes. Thus we set this polynomial to be $P_2$, and note that all the coefficients are linear in $a_i$ again. Now repeating this with say, $P_2(a_1, \dots, n) + P_2(a_2, \dots, n+k^2) + \cdots$, we again decrease the degree. It is now obvious that induction brings this to a degree $0$ polynomial, from which cyclically summing again finishes. Therefore any polynomial eventually gets reduced to the zero polynomial, and hence for a finite degree $d$ there are infinitely many integers $n$ for which the sum is $0$.

$\textbf{Remark}.$ March 23, 2023. the thing i wrote

We first explain the construction. We use $0$-indexing (so the starting sequence is $a_0$, $a_1$, $\dots$, $a_{2023}$. Let $m=b_1+b_2+\dots+b_n$. Select $a_{2024}, \dots, a_{m-1}$ such that $a_0+a_1+\dots+a_{m-1}=0$ (in particular by having $b_i$ copies of $a_i$). We claim that the sequence $$a_i = a_{s_m(i)}$$works, where $s_m(\bullet)$ denote sum of digits in base $m$ taken modulo $\boldsymbol m$. To prove this, we claim the following. Claim. Let $d < k$ be positve integers. For any real number $a_0$, $a_1$, $\dots$, $a_{m-1}$ such that $a_0+a_1+\dots+a_{m-1}=0$, we have $$T(a_0,\dots,a_{m-1}) := \sum_{i=0}^{m^k-1} a_{s_m(i)} i^d = 0.$$ Proof. Notice that $T : \mathbb R^m\to\mathbb R$ is linear. Thus, it suffices to show the identity for basis of the hyperplane $\{(a_0,\dots,a_{m-1})\in\mathbb R^m : a_0+\dots+a_{m-1}=0\}$. Let $\omega=e^{2\pi i/m}$. We claim that for any $r=1,2,\dots,m-1$, we have $$T(1, \omega^r, \omega^{2r},\dots,\omega^{(m-1)r}) = 0,$$which suffices since $(1,\omega^r,\omega^{2r},\dots,\omega^{m-1}r)$ for $r=0,1,\dots,m-1$ forms a Vandemonde matrix, so they are all linearly independent. To prove this, consider the polynomial $$F(x) := \sum_{i=0}^{m^k-1} \omega^{s_m(i)\cdot r} x^i = \prod_{j=0}^{k-1} \left(1+\omega^r x^{m^{j-1}} + \omega^{2r}x^{2m^{j-1}} + \dots + \omega^{(m-1)r}x^{(m-1)m^{j-1}}\right)$$This polynomial is divisible by $(1-x)^k$ because each factor in the product is divisible by $(1-x)$. Thus, for any $j < k$, we have $$F^{(j)}(1) = \sum_{i=0}^{m^k-1} \omega^{s_m(i)\cdot r} \tbinom ij = 0,$$and taking linear combination across all $j=0,1,\dots,d$, we get that $$T(1,\omega^r,\omega^{2r},\dots,\omega^{(m-1)r}) = \sum_{i=0}^{m^k-1} \omega^{s_m(i)\cdot r} i^d=0,$$as desired. $\blacksquare$

time for an actual writeup Let $m \geq 2$ be an arbitrary positive integer; we're going to construct a sort of "$m$-valued Thue-Morse sequence" as follows: start with $0,\ldots,m-1$ and call this $S(m,1)$. To construct $S(m,n+1)$ from $S(m,n)$, we start with $S(m,n)$, then append $S(m,n)$ with each $i$ replaced by $i+1$ (everything modulo $m$), then append $S(m,n)$ with each $i$ replaced by $i+2$, and so on until appending $S(m,n)$ with each $i$ replaced by $i-1$. For $m=2$ this is just the normal Thue-Morse sequence, and for $m=3$ we have $S(3,2)=0,1,2,1,2,0,2,0,1$. $1$-index this sequence, so e.g. $S(3,2)_2=1$. Why is this relevant? Let $P(x)$ be a polynomial of degree $d$; for some choice of $m$ consider the polynomials $p_{i,n}(x)=\sum_{S(m,n)_j=i} P(x+j)$ for $0 \leq i \leq m-1$. I claim that degree $d$ through degree $d-n+1$ terms of each $p_{i,n}$ are the same across all $i$. This follows by induction on $n$, with the base case of $n=1$ being trivial. For the inductive step, observe that $$p_{i,n+1}(x)=p_{i,n}(x)+p_{i+1,n}(x+m^n)+p_{i+2,n}(x+2m^n)+\cdots+p_{i-1,n}(x+(m-1)m^n).$$We only have to check that as $i$ varies, the $(n+1)$-th highest degree term remains the same, since everything larger is taken care of by hypothesis. Indeed, if $c_{i,n}$ denoted the coefficient of the degree $d-n$ term in $p_{i,n}$ then the degree $d-n$ term in $p_{i,n+1}(x)$ will be $c_{i,n}+c_{i+1,n}+\cdots+c_{i-1,n}$ which is independent of $i$, which finishes the induction. The important consequence of this fact is that all $p_{i,d+1}(x)$ are equal. It is time to do the actual problem. We are essentially saying that we want to partition $\mathbb{Z}^+$ into $2024$ sets $S_1,\ldots,S_{2024}$ such that $i \in S_i$ such that for each $d>0$ there are infinitely many $n$ with $\frac{1}{d_i}\sum_{S_i \ni k \leq n} k^d$ equal for all $i$. In fact, we are going to prove that if we have already determined the partition for $1,\ldots,N_0$, then for any given $d>0$ we can partition $N_0+1,\ldots,N$ such that $\frac{1}{d_i}\sum_{S_i \ni k \leq N} k^d$ are equal for all $i$. In fact, this is very simple. First pick a suitable $N_1$ and arbitrarily (!) assign $N_0+1,\ldots,N_1$ such that all $\frac{1}{d_i}|S_i \cap [1,N_1]|$ are equal. Then consider the sequence $S(N_1,d+1)$ and assign $N_1+1,\ldots,N_1^{d+1}$ such that any $N_1+1\leq i \leq N_1^{d+1}$ goes into the same subset as $S(n_1,d+1)_i \leq N_1$. The properties of $S(N_1,d+1)$ then imply that all $\sum_{S(N_1,d+1)_k=i} k^d$ are equal across all $1 \leq i \leq N_i$, so all $\frac{1}{d_i}\sum_{S_i \ni k \leq N_1^{d+1}} k^d$ are equal as well. Thus we may let $N=N_1^{d+1}$ and conclude. To finish, we may simply take some sequence of positive integers where every positive integer appears infinitely many times (something like $1,1,2,1,2,3,1,2,3,4,\ldots$ works quite well) and read it off in order, determining the partition for the next "few" numbers to generate a valid $n$ when $d$ equals the read-off number each time. This finishes the problem. $\blacksquare$ Remark: Actually the last part can be simplified somewhat: because of how we're doing things, every $n$ we generate for a given $d$ works for all $d'<d$ as well, so we can use the sequence $1,2,3,\ldots$ as well. Remark: Really the problem is the exact same if we assume all $b_i$ are $1$ and replace $2024$ with any positive integer (the latter being an obvious thing that we can do) by "splitting up" each $a_i$ into $b_i$ copies of itself.

popop614 wrote:

$\textbf{Remark}.$ March 23, 2023. the thing i wrote

Actually this particular special case is not particularly new: see part (b) of Balkan MO Shortlist 2021/A4 and the Prouhet-Tarry-Escott Problem. I haven't ever seen the tstst problem itself before. (also, what would a polynomial of infinite degree look like?? lmao)

Let $b_1 + b_2 + \cdots + b_{2024} = k$, and select $a_{2025}, a_{2026}, \dots, a_k$ such that $\sum_{i=1}^{k} a_i = 0$ which can be done by just expanding out each $b_i$. The following claim finishes the problem. Claim: Let $f(i)$ be the sum of digits of $i-1$ in base $k$ taken $\pmod{k}$. If $d \le m$ are positive integers, then $$\sum_{i=1}^{k^m} a_{f(i)} \cdot i^d = 0$$ Proof. We may assume that $(b_1, b_2, \dots, b_{2024})$ is the only linear combination that allows the sum to be $0$, meaning that we can essentially let each $a_i = \left[ \omega^i \right]^\ell$ where $\omega$ is a $k$th root of unity, and prove the identity for all $\ell = 0, 1, 2, \dots, k-1$. This is due to the key lemma of how there exists only one linear combination of roots of unity with prime order that is $0$ where all coefficients are equal. Proving the identity for all $\ell$ allows us to biject $a_i$ to non prime roots of unity as well. We just assume $\ell = 1$, because essentially every case is identical to this, as the zero case is trivial to deal with. We examine the generating function \begin{align*} P(x) = \sum_{i=1}^{k^m} \omega^{f(i)} \cdot x^i = x \cdot \sum_{i=1}^{k^m} \omega^{f(i)} \cdot x^{i-1} = x \cdot \prod_{i = 0}^{m-1} \sum_{j = 0}^{k-1} \omega^{j} x^{j \cdot k^{i}} \end{align*}where the use of the root of unity essentially gets rid of the $\pmod k$ condition in $f(i)$ and we can freely use a generating function to represent base $k$. We drop the $x$ term in front because it is useless and won't change anything. Note that clearly $(x-1)^m$ divides $P(x)$ as each term in the product has $1$ as a root. Now, taking the $n$th derivative were $n \le m$ gives $P^{ (n)}(1) = \sum_{i=1}^{k^m} \left[ \omega^{f(i)} \cdot (i-1)(i-2) \cdots (i-n) \right]= 0$. We can vary $0 \le n \le d$ and take linear combinations to annihilate all coefficients except the lone $i^d$ term in front to get the desired $$\sum_{i=1}^{k^m} \omega^{f(i)} \cdot i^d = 0$$and we are finished.

DFT solution given by ORZORZ ayh: (lazy to translate)