For any positive integer $n$, define $$c_n=\min_{(z_1,z_2,...,z_n)\in\{-1,1\}^n} |z_1\cdot 1^{2018} + z_2\cdot 2^{2018} + ... + z_n\cdot n^{2018}|.$$Is the sequence $(c_n)_{n\in\mathbb{Z}^+}$ bounded?
Problem
Source: Serbia TST 2018 P6
Tags: algebra, combinatorics
29.05.2018 14:00
29.05.2018 14:28
The name of the above lemma is Prouhet–Tarry–Escott problem.
06.06.2018 07:33
Sorry, but how does this lemma help?
06.06.2018 09:50
MarkBcc168 wrote:
It even holds over any basis,it's an old problem from Kvant which i posted and if i remember correctly Darij posted a solution. Amazingly on the actual TST i hadn't even thought about it.
06.06.2018 10:47
Basically, it tells that for any group of $2^{2019}$ consecutive numbers, there exists a way to assign $z_i$ so that the resulting sum is zero. Thus the sequence is bounded by $\max\{a_1,a_2,...,a_{2^{2019} }\}$.
09.11.2019 19:53
MarkBcc168 wrote:
How can we prove this lemma?
11.08.2020 21:51
We generalize this problem. Namely, we prove that $$c_n=\min_{(z_1,z_2,...,z_n)\in\{-1,1\}^n} |z_1\cdot P(1) + z_2\cdot P(2) + ... + z_n\cdot P(n)|.$$ is bounded for any (integer) polynomial $P$. The proof goes by induction on the degree. The constant polynomial case is immediate (alternating signs). Consider the polynomial $Q(x)=P(x+1)-P(x)$, which has degree $\deg P -1$. For $n$ even, take $-z_1=z_2=y_1 , -z_3=z_4=y_2 ,...$ then we have $$z_1\cdot P(1) + z_2\cdot P(2) + ... + z_n\cdot P(n) = y_1 \cdot Q(1) + y_2 \cdot Q(3) +... + y_{\frac{n}{2}} \cdot Q(n-1)$$ In this case, we may simply apply our inductive hypothesis to the polynomial $R(x)=Q(2x-1)$, which again has a degree at most $\deg P -1$. To the case $n$ odd, we start by $-z_2 = z_3 =y_1 , -z_4=z_5=y_2,...$. In this case, $$z_1\cdot P(1) + z_2\cdot P(2) + ... + z_n\cdot P(n) = (z_1 \cdot P(1)) +(y_1 Q(2) + y_2 Q(4) +...+y_{\frac{n-1}{2}} Q(n-1))$$ So, by applying our result to $H(x)=Q(2x)$ and using triangle inequality, we again get our desired result . Therefore the bound $B_P \le \max (|P(1)|+ B_H, B_R)$ works and we are done (where $B_S$ is the bound of polynomial $S$).
08.10.2021 19:25