This was also Day 1 #2 of the South Korean TST.

Just generalize and induct. Also, we only need $x_1\in\{0,1,...,m-1\}$ and $x_2,x_3,...,x_n\in\{0,1\}$. Call a function $g : \mathbb{Z}\to\mathbb{Z}$ $m$-periodic if and only if it is periodic with (not necessarily minimal) period $m$. We will prove the following generalization of the problem. Claim: Let $m\geqslant 2$, $n\geqslant 1$ be integers. Let $g$ be a non-constant, $m$-periodic function, $f\in\mathbb{R}[x_1,x_2,...,x_n]$ be a polynomial such that $$f(x_1,x_2,...,x_n) = g(x_1+x_2+...+x_n)$$for every $x_1,x_2,...,x_n\in\{0,1,...,m-1\}$. Then the total degree of $f$ is at least $n$. Proof: Surprisingly, proving this claim by induction on $n$ is fairly simple. The base case $n=1$ is obvious as $g$ is non-constant. Assume that this is already true for $n-1$. If there is a term with $(x_n)^n$ then we are already done. Let $f_0, f_1, f_2,...,f_{n-1}$ be polynomials in $n-1$ variables such that $$f(x_1,x_2,...,x_n) = \sum_{i=0}^n (x_n)^i\cdot f_i(x_1,x_2,...,x_{n-1}).$$Now here is the key step. Define \begin{align*} F(x_1,x_2,..,x_{n-1}) &:= \sum_{i=1}^n f_i(x_1,x_2,...,x_{n-1}) \\ &= f(x_1,x_2,...,x_{n-1},1) - f(x_1,x_2,...,x_{n-1},0)\\ &= g(x_1+x_2+...+x_{n-1}+1) - g(x_1+x_2+...+x_{n-1}) \end{align*}Thus if we define $h(x) = g(x+1)-g(x)$ and use the induction hypothesis on $h$. If $h$ is constant, then the periodicity of $g$ forces $h\equiv 0$ or $g$ is constant, contradiction. Thus $h$ is non-constant. By induction hypothesis, $\deg F\geqslant n-1$. Thus there exists a term $(x_1)^{a_1}(x_2)^{a_2}...(x_{n-1})^{a_{n-1}}$ which appears in $f_i$ for some $i$ such that $a_1+a_2+...+a_{n-1}\geqslant n-1$. Thus the term $(x_1)^{a_1}(x_2)^{a_2}...(x_{n-1})^{a_{n-1}} (x_n)^i$ appears in $f$ so we are done. The problem follows from taking $$F(x_1,x_2,...,x_n) := f(x_1,x_2,...,x_n) - \frac{x_1+x_2+...+x_n}{m}.$$

Here's my solution during the TST. Functional wrote: Let $m,n\geq 2$ be integers. Let $f(x_1,\dots, x_n)$ be a polynomial with real coefficients such that $$f(x_1,\dots, x_n)=\left\lfloor \frac{x_1+\dots + x_n}{m} \right\rfloor\text{ for every } x_1,\dots, x_n\in \{0,1,\dots, m-1\}.$$Prove that the total degree of $f$ is at least $n$. We prove the problem statement by dividing in two cases. Case 1: $m > n$. Plugging in $x_2=1, x_3=x_4=\cdots =x_n=0$ gives $f(x_1, 1, 0, \cdots, 0)=\left\lfloor \frac{x_1+1}{m} \right\rfloor$. Hence, $f(x_1, 1, 0, \cdots, 0)=0$ if $x_1 \in \{ 0,1,2, \cdots, m-2\}$, and $f(x_1, 0, 0, \cdots, 0)=1$ if $x_1=m-1$. This gives $\deg f(x_1, 1, 0, 0, \cdots , 0) \ge m-1 \ge n$. Note that $\deg f(x_1, x_2, \cdots , x_n) \ge \deg f(x_1, 1, 0, \cdots, 0)$, so $\deg f(x_1, x_2, \cdots , x_n) \ge \deg f(x_1, 1, 0, \cdots, 0) \ge n$, as desired. Case 2: $m \le n$. In this case, we prove that there exists some term in the form $Ax_1^{a_1}x_2^{a_2} \cdots x_n^{a_n}$, where all $a_i$'s are at least $1$. Assume not, then there exist some polynomials $g_1, g_2, \cdots, g_{n-1}$ such that $f=g_1+g_2+\cdots +g_{n-1}$, and for each $i=1,2, \cdots, n-1$, $g_i=0$ if at least one of $x_1, x_2, \cdots , x_{i-1}$ equals $0$.(Just split $f$ in a greedy manner!) The main claim is the following: Claim wrote: For every $i=1,2, \cdots, n$, $$g_i=\sum_{S \subseteq [i-1]} (-1)^{i-1-|S|} \left\lfloor \frac{\sum_{k=1}^{n} x_k -x_i-\sum_{j\in S} x_j}{m} \right\rfloor$$holds. (Here, $[u]$ denotes the set $\{1,2, \cdots, u\}$.) The proof of the claim involves induction on $i$, but instead writing all the boring steps, I'll just work on some small cases(which is enough to generalize). For $i=1$, plug $x_1=0$ in the equation $f=g_1+g_2+\cdots +g_n$, then $g_2, \cdots, g_n$ cancels out, so $g_1=\left\lfloor \frac{x_2+\dots + x_n}{m} \right\rfloor$. For $i=2$, plug $x_2=0$, then $g_3, \cdots, g_n$ cancels out, so $g_2=f-g_1=\left\lfloor \frac{x_1+x_3+\dots + x_n}{m} \right\rfloor-\left\lfloor \frac{x_3+\dots + x_n}{m} \right\rfloor.$ For $i=3$, plug $x_3=0$, then $g_4, \cdots, g_n$ cancels out, so $$g_3=f-g_1-g_2=\left\lfloor \frac{x_1+x_2+x_4\dots + x_n}{m} \right\rfloor-\left\lfloor \frac{x_2+x_4+\dots + x_n}{m} \right\rfloor-\left\lfloor \frac{x_1+x_4+\dots + x_n}{m} \right\rfloor+\left\lfloor \frac{x_4+\dots + x_n}{m} \right\rfloor.$$ Now, since $n \ge m$, take $x_1=x_2=\cdots =x_m=1, x_{m+1}=\cdots =x_n=0$. Then by the claim, $g_1+\cdots +g_n=g_1+\cdots +g_m =0$, but plugging in $f(x_1, \cdots, x_n)=\left\lfloor \frac{x_1+\dots + x_n}{m} \right\rfloor$ gives $f=1$, a contradiction. Hence the proof is complete. $\square$

Lemma: $\deg f(x_1,1,0,...,0) \ge m-1$. Proof: We compute $$\sum_{i=0}^{m-1} (-1)^if(i,1,0,...,0) = (-1)^{m-1} \ne 0.$$ With this lemma the case $m \ge n+1$ is already annihilated. Suppose now $m \le n$. We will only be using $x_i \in \{s_i,s_i+1\}$ for some $(s_i)_{i=1}^n \subseteq \mathbb N_{m-1}^n$ with $\sum_{i=1}^n s_i = s \in \{0,1,...,m-1\}$. Define $f'(x_1,...,x_n) = f(x_1-s_1,...,x_n-s_n)$. Write $$f'(x_1,...,x_n) = \sum_{I \subseteq \mathbb N_n} c(I)\sum_{\alpha \in \mathbb N^{|I|}} \prod_{i=1}^{|I|} x_i^{\alpha_i}.$$It suffices to show that $c(\mathbb N_n) \ne 0$. Consider the following system of $2^n$ equations (obtained by taking a subset $I$ of $\mathbb N_n$ and setting all $x_i$ with $i \in I$ to $1$, the other variables to $0$): $$\sum_{J \subseteq I} c(J) = \lfloor \frac{|I| + s}{m}\rfloor.$$By PIE $$c(\mathbb N_n) = \sum_{I \subseteq \mathbb N_n} \lfloor \frac{|I|+s}{m} \rfloor (-1)^{n-|I|}$$so it suffices to show that this quantity is not $0$, i.e. for all $n \ge m \ge 2$, $$\sum_{i=0}^{n} \lfloor \frac{i+s}{m} \rfloor \binom n i (-1)^i \ne 0.$$Since $\sum_{i=0}^n \frac{i+s}{m} \binom n i (-1)^i = 0$ it is equivalent to check that $$\sum_{r=0}^{m-1}\sum_{k=0}^\infty \frac{r}{m} \binom{n}{mk + r-s} (-1)^{mk+r-s} \ne 0.$$Now note that $\sum_{k} \binom n {mk+r-s} (-1)^{mk+r} = \frac{1}{m}\sum_{t=1}^m \frac{(1-\omega_t)^n}{\omega_t^{r-s}}$ where $\omega_t$ is a primitive $m$th root of unity. Thus $m\times$ the above sum evaluates to $$\sum_{r=0}^{m-1} \frac{r}{m}\sum_{t=0}^{m-1} \frac{(1-\omega_t)^n}{\omega_t^{r-s}}$$$$ = \frac{1}{m}\sum_{t=0}^{m-1} (1-\omega_t)^n \sum_{r=0}^{m-1} \frac{r}{\omega_t^{r-s}}$$$$ = -\frac{1}{m}\sum_{t=0}^{m-1} (1-\omega_t)^n \cdot \frac{m\omega_t^{1+s}}{1-\omega_t}$$$$ = -\sum_{t=0}^{m-1} (1-\omega_t)^{n-1}\omega_t^{1+s}$$ For convenience define $\binom b a = 0$ for $a < 0,b \ge 0$. Then $(-1)\times$ the above expression is equal to $$m\sum_{k\ge 0} (-1)^{mk-1-s} \binom {n-1}{mk-1-s}.$$Let $f(n,t) = \sum_{k \ge 0}(-1)^k \binom{n}{mk-t}$. For convenience define $\frac{b}{a} = 0$ for $b \ge 0 > a$. Then we want $f(n-1, s+1) \ne 0$ for some $0\le s\le m-1$. Suppose this expression is $0$ for each choice of $s$, then $2\nmid m$ (else all terms of the sum will have the same sign). Note the recursion $$f(n,t) = f(n-1,t+1) + f(n-1,t).$$We will only define $f$ over $n,t \ge 0$. Note that for nonnegative $t$, $f(n,t) = -f(n,t+m) = f(n,t+2m)$. Thus $f(0,t) = \begin{cases} 0 & m\nmid t\\ 1 & 2m \mid t\\ -1 & \text{else} \end{cases}$. Now fix $m$ and note that $f(n-1,t) = 0 \forall t \ge 0$ implies (using the recursion) $f(n,t) = 0 \forall t$, and then $f(n+1,t) = 0 \forall t$ and so on. Let $a_n = f(n,0)$, then the sequence $a_n$ satisfies a linear recurrence relation of order $m$ with characteristic polynomial $(1-x)^m - 1$. Since the sequence $(a_n)$ eventually becomes identically zero, we may backtrack to find $a_0 = 0$ as well, but $f(0,0) = 1$, contradiction.

MarkBcc168 wrote: Thus there exists a term $(x_1)^{a_1}(x_2)^{a_2}...(x_{n-1})^{a_{n-1}}$ which appears in $f_i$ for some $i$ such that $a_1+a_2+...+a_{n-1}\geqslant n-1$. Thus the term $(x_1)^{a_1}(x_2)^{a_2}...(x_{n-1})^{a_{n-1}} (x_n)^i$ appears in $f$ so we are done. How do we know that this $i$ must be greater than $0$?

Because $\deg F\geq n-1$ so some monomials with degree $n-1$ must appear in $F$, which in turn must appear in some $f_i$. Also note that the sum in $F$ runs through $i=1$ to $n$ not $i=0$.

MarkBcc168 wrote: Because $\deg F\geq n-1$ so some monomials with degree $n-1$ must appear in $F$, which in turn must appear in some $f_i$. Also note that the sum in $F$ runs through $i=1$ to $n$ not $i=0$. Thanks for assisting me with reading

MarkBcc168 wrote: Just generalize and induct. Also, we only need $x_1\in\{0,1,...,m-1\}$ and $x_2,x_3,...,x_n\in\{0,1\}$. Call a function $g : \mathbb{Z}\to\mathbb{Z}$ $m$-periodic if and only if it is periodic with (not necessarily minimal) period $m$. We will prove the following generalization of the problem. Claim: Let $m\geqslant 2$, $n\geqslant 1$ be integers. Let $g$ be a non-constant, $m$-periodic function, $f\in\mathbb{R}[x_1,x_2,...,x_n]$ be a polynomial such that $$f(x_1,x_2,...,x_n) = g(x_1+x_2+...+x_n)$$for every $x_1,x_2,...,x_n\in\{0,1,...,m-1\}$. Then the total degree of $f$ is at least $n$. Proof: Surprisingly, proving this claim by induction on $n$ is fairly simple. The base case $n=1$ is obvious as $g$ is non-constant. Doesn't your base case fail right away because \[n = 1 \Rightarrow f(x_1) = \lfloor{\frac{x_1}{m}}\rfloor = 0 \Rightarrow f(x_1) = 0 \Rightarrow deg(f) = 0\]?

$\lfloor\frac{x_1}{m}\rfloor$ is not $m$-periodic.

MarkBcc168 wrote: Just generalize and induct. Also, we only need $x_1\in\{0,1,...,m-1\}$ and $x_2,x_3,...,x_n\in\{0,1\}$. Call a function $g : \mathbb{Z}\to\mathbb{Z}$ $m$-periodic if and only if it is periodic with (not necessarily minimal) period $m$. We will prove the following generalization of the problem. Claim: Let $m\geqslant 2$, $n\geqslant 1$ be integers. Let $g$ be a non-constant, $m$-periodic function, $f\in\mathbb{R}[x_1,x_2,...,x_n]$ be a polynomial such that $$f(x_1,x_2,...,x_n) = g(x_1+x_2+...+x_n)$$for every $x_1,x_2,...,x_n\in\{0,1,...,m-1\}$. Then the total degree of $f$ is at least $n$. Proof: Surprisingly, proving this claim by induction on $n$ is fairly simple. The base case $n=1$ is obvious as $g$ is non-constant. Assume that this is already true for $n-1$. If there is a term with $(x_n)^n$ then we are already done. Let $f_0, f_1, f_2,...,f_{n-1}$ be polynomials in $n-1$ variables such that $$f(x_1,x_2,...,x_n) = \sum_{i=0}^n (x_n)^i\cdot f_i(x_1,x_2,...,x_{n-1}).$$Now here is the key step. Define \begin{align*} F(x_1,x_2,..,x_{n-1}) &:= \sum_{i=1}^n f_i(x_1,x_2,...,x_{n-1}) \\ &= f(x_1,x_2,...,x_{n-1},1) - f(x_1,x_2,...,x_{n-1},0)\\ &= g(x_1+x_2+...+x_{n-1}+1) - g(x_1+x_2+...+x_{n-1}) \end{align*}Thus if we define $h(x) = g(x+1)-g(x)$ and use the induction hypothesis on $h$. If $h$ is constant, then the periodicity of $g$ forces $h\equiv 0$ or $g$ is constant, contradiction. Thus $h$ is non-constant. By induction hypothesis, $\deg F\geqslant n-1$. Thus there exists a term $(x_1)^{a_1}(x_2)^{a_2}...(x_{n-1})^{a_{n-1}}$ which appears in $f_i$ for some $i$ such that $a_1+a_2+...+a_{n-1}\geqslant n-1$. Thus the term $(x_1)^{a_1}(x_2)^{a_2}...(x_{n-1})^{a_{n-1}} (x_n)^i$ appears in $f$ so we are done. The problem follows from taking $$g(x_1,x_2,...,x_n) := f(x_1,x_2,...,x_n) - \frac{x_1+x_2+...+x_n}{m}.$$ How can $g$ have period $m$ if $f$ is defined up to $x_1 + x_2 + \cdots + x_n \leq n(m - 1)$? We have $n(m - 1) = (n - 1)(m - 1) + (m - 1) = m + ((n - 1)(m - 1) - 1) \geq m$, which is already period greater than $m$

The $m$-periodic function I'm applying induction for is $\left\lfloor\frac xm\right\rfloor-\frac xm$, which is clearly $m$-periodic.

TLP.39 wrote: $\lfloor\frac{x_1}{m}\rfloor$ is not $m$-periodic. You're setting $g$ to be $m$-periodic not $f$. $f(x_1) = \lfloor\frac{x_1}{m}\rfloor = 0$ by definition of the problem statement. Base case $n = 2$ works but there's also other technical flaws I believe. $g$ being periodic implies that $h$ is nonconstant, but $h$ doesn't say anything about the degree of $f$ because $g$ is not a polynomial. Just pretend \[m = 2 \Rightarrow f(x_1, x_2, \cdots, x_n) = \rfloor\frac{\sum x_i}{2}\lfloor\]\[\Rightarrow g(x) = \rfloor\frac{x}{2}\lfloor | x \leq n\]First off, $g$ cannot be $m$-periodic because $g(x) = \lfloor\frac{\sum x_i}{m}\rfloor$ is varies across $0 \leq x \leq n(m - 1)$, and clearly $n(m - 1) \geq m$, with equality at $m = n = 2$. It can be periodic, but definitely not degree $m$. Obviously $g$ cannot be constant since $f$ is not constant. Since $g$ is a nonconstant periodic function, it cannot be a polynomial, and thus $g(x + 1) - g(x)$ being nonconstant says nothing about the polynomial, because a $g$ can repeat $0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, \cdots$ and $h$ would be $1, 1, 1, 1, 1, 1, -6, 1, 1, 1, 1, 1, 1, -6, \cdots$ which is nonconstant, but is also not a polynomial, which literally says nothing about $f$. Also, $g = \lfloor\frac{x}{m}\rfloor - \frac{x}{m}$ is clearly not equal to $f$, as $f$ is nonnegative over the given domain, and $g$ is clearly nonpositive. Also the induction hypothesis states that any function $f$ that satisfies the given conditions over $x_1, x_2, ... x_{n-1} \in \{0, 1, 2, ... m-1\}$ has degree at least $n - 1$. $F$ does not satisfy these conditions and therefore the induction hypothesis does not apply. We have \[F = g(\sum x_i + 1) - g(\sum x_i) = \lfloor\frac{g(\sum x_i + 1)}{m}\rfloor - \lfloor\frac{g(\sum x_i)}{m}\rfloor \leq 1\]which already fails for $\sum x_i \geq 2m$. By individual steps, 1) Base case $n = 1$ fails since $deg(f(x_1) = 0) = 0$ works. 2) $g$ can be periodic but not $m$-periodic because $f$ goes from $0$ to $n - \lceil\frac{n}{m}\rceil$ over $0 \leq \sum x_i \leq n(m - 1)$ and $n(m - 1) \geq m$ with equality at $m = n = 2$. 3) Assume $g$ is indeed periodic. Induction hypothesis does not apply to $h$ i) because $h$ is not a polynomial since $g$ is not a polynomial ii) since $h$ does not satisfy the requirements of the hypothesis, which are the requirements of the question, as reasoned above $h(x) = g(x + 1) - g(x) \leq 1$ for all $x$ which clearly does not satisfy the requirements. 4) Since you're defining $F$ to be a polynomial, it can only be written in terms of $g$ when $x_1, x_2, ... x_n \in \{0, 1, ... m - 1\}$, and not for all $x_i$. Induction hypothesis does not apply to $h$ and therefore not to $F$. 5) $g$ isn't even equal to $f$ over the "small" $x_i$ requirements. $g$ is negative and $f$ is positive.

Why is $deg(f)=0?$ Note that $f$ in the claim is not the same one as in the problem. Rather, $f(x)$ (for the case $n=1$) is a single-variable polynomial which is equal to $g(x)$ for all $x\in\{0,1,2,...,m-1\},$ where $g$ is some random non-constant $m$-periodic function $g$ (which, again, is not related to any function in the original problem statement.) Here, if $deg(f)=0,$ then $g$ must be constant, a contradiction to the condition statement '$g$ is non-constant.'

TLP.39 wrote: Why is $deg(f)=0?$ Note that $f$ in the claim is not the same one as in the problem. Rather, $f(x)$ (for the case $n=1$) is a single-variable polynomial which is equal to $g(x)$ for all $x\in\{0,1,2,...,m-1\},$ where $g$ is some random non-constant $m$-periodic function $g$ (which, again, is not related to any function in the original problem statement.) Here, if $deg(f)=0,$ then $g$ must be constant, a contradiction to the condition statement '$g$ is non-constant.' Regardless of the definition of $f$ if the generalization attempts to extend the property to $n = 1$ it fails because $f(x_1) = 0$ is a counterexample. It's like you're given a sequence $a_0 = 1, a_1 = 1, a_2 = 2, a_3 = 3$, etc. and you want to prove that $a_n = n$ for all positive $n$. You try to generalize and show that $a_n = n$ for all $n$ but now your proof doesn't work anymore because there's a counterexample. Also, $f$ in the induction assumes a "beginning" equal to $g$, which is $m$-periodic. Just for simplicity, just suppose $g$ goes $0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3$ etc., and thus $f$ is a polynomial that does as well. The generalization proves $f$ is at least degree $n$ but there doesn't exist such an $m$-periodic function that creates the $f$ given in the problem. You're proving that if $f$ starts the same as $g$, or $0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3$ until a certain point, then $f$ is at least degree $n$, and this is all fine, but $g$ is $m$-periodic implies that $f$ is $m$-periodic at the beginning. Even though $f$ is not the same as the one in the problem, since there $f$ in the problem will almost never be $m$-periodic the generalization does not apply. $f$ in the problem goes something like $0, 0, 0, 1, 1, 1, 2, 2, 2$ etc., and there's no $g$ that results in that. $f(x_1) = 0$ does not directly nullify the base case. But the base case $n = 1$ assumes the result extends to $n = 1$, and applies to the problem if $n = 1$ but it does not, because here does $f(x_1) = 0$ become a counterexample

jclash wrote: it fails because $f(x_1) = 0$ is a counterexample. Point is that $f(x_1)=0$ is not a counterexample. If $f(x_1)=0,$ then $g$ must be identically zero, which contradicts with the given condition. In case of misunderstanding, $g$ is not $\lfloor \frac{x_1}{m}\rfloor$.

The point is I have included the condition that $g$ must be nonconstant in the claim. It's worth noting that the condition $n\geq 2$ is used in the very last step to ensure the non-constant condition. The claim allows $n=1$ for the ease of argument.

TLP.39 wrote: jclash wrote: it fails because $f(x_1) = 0$ is a counterexample. Point is that $f(x_1)=0$ is not a counterexample. If $f(x_1)=0,$ then $g$ must be identically zero, which contradicts with the given condition. Before anything, $g$ is not $\lfloor \frac{x_1}{m}\rfloor$. Since $f$ is defined in the problem, obviously in the problem such an $f$ will always exist. However, since he's defining $g$ first and $f$ based off $g$, you're assuming say function $R(g) = f$ is surjective into $\mathbb{R}^n$ when it's not. Since $f$ is defined based off $g$ you can no longer assume $f$ can be whatever you want. Namely, you can no longer assume you can just make $f$ satisfy the conditions. For simplicity define $\mathbb{S}$ as the set of polynomials $f(x_1, x_2, ... x_n) = \lfloor\frac{\sum x_i}{m}\rfloor$ for $x_i \in \{0, 1, ... m - 1\}$. Question asks you to prove a property for all $f \in \mathbb{S}$. Proof defines $g$ as $m$-periodic, defines $f(x_i | 1 \leq i \leq n) = g(\sum x_i)$ over $x_i \in \{0, 1, ... m - 1\}$. Thus, just call $f$ "$m$-periodic at the beginning". While the proof shows all $f$ in the range of $R(g) = f$ have degree at least $n$, $\mathbb{S} \notin range(R)$. More specifically, $R(g) = f \in \mathbb{S}$ iff $m = n = 2$ Take $m = 3, n = 2$ for example. We have $f(0, 0) = 0, f(0, 1) = 0, f(0, 2) = 0, f(1, 1) = 0, f(1, 2) = 1, f(2, 2) = 1$. There exists no $m$-periodic $g$ that can produce this $f$ by the proof definition. Sure $g$ and $f$ can be something else in the proof. But that just means that the generalization no longer applies if such $f$ and $g$ don't exist. More specifically when you try to create this $g$ you run into $g(0) = 0, g(1) = 0, g(2) = 0, g(3) = 1, g(4) = 1$ and bam, period of $g$ is already at least 5

As I said earlier, $f_{claim}$ and $f_{problem}$ is not the same polynomial. This means that $f_{claim}(x_1)\neq\lfloor\frac{x_1}{m}\rfloor.$ Anyway, to settled this, this is what @Markbcc168 did: MarkBcc168 wrote: Claim: Let $m\geqslant 2$, $n\geqslant 1$ be integers. Let $q$ be a non-constant, $m$-periodic function, $p\in\mathbb{R}[x_1,x_2,...,x_n]$ be a polynomial such that $$p(x_1,x_2,...,x_n) = q(x_1+x_2+...+x_n)$$for every $x_1,x_2,...,x_n\in\{0,1,...,m-1\}$. Then the total degree of $p$ is at least $n$. Here, I change the name of polynomial/function to reduce confusion between $f_{problem}$ and $f_{claim}$ (which is now named $p$.) By letting $p(x_1,x_2,...,x_m)=q(x_1+x_2+...+x_m)=f_{problem}(x_1,x_2,...,x_m)-\frac{x_1+x_2+...+x_n}{m}$ for all $x_1,...,x_m\in\{0,1,...,m-1\},$ $q$ will satisfies the condition in the claim, thus, $p$ will have degree $n,$ and thus $f(x_1,x_2,...,x_m)=p(x_1,x_2,...,x_m)+\frac{x_1+x_2+...+x_n}{m}$ will have degree $n$, too.

What you're doing is showing $f_{claim}$ satisfies $p$ property. You cannot generalize to $f_{problem}$ because $f_{claim}$ will never equal $f_{problem}$ and therefore you cannot use this reasoning to state that $f_{problem}$ satisfies $p$ property. It's like a problem asks you to prove $p$ property for function $f(x) = x$. Then your proof goes define $g: \mathbb{R} \to \mathbb{R}_+$ and define $f_{claim} = \sqrt{g}$. You prove $p$ property for $f_{claim}$, and that's all fine. However, $f_{claim}$ will never equal $f(x) = x$ because there exists no $g$ such that $\sqrt{g(x)} = x$ for all $x$. I'm not saying the proof is incorrect. I'm saying the proof doesn't result in the problem statement, not to mention another flaw or two

The point is that $f_{problem}$ need not to satisfy such property. The fact that $f_{problem}(x_1,x_2,...,x_n)-\frac{x_1+x_2+...+x_n}{m}$ satisfies the property is enough to prove that $f_{problem}(x_1,x_2,...,x_n)-\frac{x_1+x_2+...+x_n}{m}$ has degree at least $n$.

I see what you're saying for $n \geq 2$. The thing is that the proof works on the basis that if $g = f - \frac{\sum x_i}{m}$ is degree $n$, then $f$ is also degree $n$. However this doesn't work for $n = 1$ because the linear terms can cancel out making it degree $0$.

Case 1: $m\ge n$. Note that $f(x,0,0,\ldots, 0)$ gives that the polynomial with only $x_1$ has roots $0$ through $m-1$. Thus, it always yields $0$ and we can WLOG that it is $0$. Now, consider $P(x)=f(x,1,0,\ldots, 0)$. Note that $P(x)$ has roots $0,1,\ldots, m-2$, so it is of the form $Cx(x-1)\ldots (x-(m-2))$. However, $C\neq 0$ because $P(m-1)\neq 0$. Hence, $P(x)$ has degree at least $m-1$. However, since all terms of $P(x)$ are divisible by $x_2$ as we assumed that there are no terms with only $x_1$, the polynomial $f(x_1,x_2,0,\ldots, 0)$ has degree at least $m\ge n$, as desired. Case 2: $m<n$. We will show that there is in fact a term divisible by $x_i\,\forall 1\le i\le n$. To do this, suppose we plug in a value $t$ for a set $S$ of the $x_i$, and $0$ for the rest. The condition tells us that the sum of all terms consisting of only elements of $S$ when $t$ is plugged in is $\left\lfloor\frac{|S|t}{m}\right\rfloor$. So, if we want to find the sum of all terms consisting of all the elements of $\{x_i\}$ when $t$ is plugged in, we can use PIE to get this value to be $$\sum_{S\in\{x_i\}}\left\lfloor\frac{|S|t}{m}\right\rfloor(-1)^{n-|S|}=\sum_{k=0}^n \left\lfloor\frac{kt}{m}\right\rfloor\binom{n}{k}(-1)^{n-k}$$As long as this value is nonzero, we will be done. However, we can try repeating these same steps except whenever $x_1$ is part of $S$, we will plug in $t+1$ instead. This means that we can either have $\left\lfloor\frac{|S|t}{m}\right\rfloor$ or $\left\lfloor\frac{|S|t+1}{m}\right\rfloor$ depending on if $x_1$ is in $S$. Normally, such an alteration will not change the value of the floor. In fact, the only terms which this will impact are those were $kt\equiv -1\pmod m$. If we denote $s=-t^{-1}\pmod m$, then the difference between our initial summation and the new one which has $x_1=t+1$ is just $$\sum_{i=0}^n\binom{n-1}{s-1+mi}(-1)^{n-(s-1+mi)}$$As a nonzero value for either the initial sum with $x_1=t$ or the new one with $x_1=t+1$ would indicate our desired term, we just need that the difference is nonzero. Of course, this is evident if $2|m$. This is because the exponent of $-1$ will not change over the sum, and hence the magnitude is obviously nonzero. So, assume instead that $m$ is odd. So, our sum has the same magnitude as $\sum_{i=0}^n\binom{n-1}{s-1+mi}(-1)^i$. Lastly, note that we never set $t$ to any particular value. With this in mind, we can vary $t$ between $1$ and $m-1$ to recover any nonzero value for $s$. Hence, the only way in which we would not have our desired term is if $S_x=\sum_{i=0}^n\binom{n-1}{x+mi}(-1)^i$ holds for all $0\le x<m-1$, and $m$ is an odd number at least $3$. Note that $S_x$ can be written in terms of roots of unity as $\frac{1}{m}\sum_{i=0}^{m-1}\omega^{-xi}(1-\omega^i)^n$, where $\omega=e^{\frac{2i\pi}{m}}$. However, it is easy to see that $(1,\omega^{-x},\omega^{-2x},\ldots)$ for $0\le x<m-1$ form a basis on the plane $y_1+\omega y_2+\omega^2 y_3+\ldots+\omega^{m-1}y_m=0$. Thus, if $S_x$ were always zero, this entire plane would be the null space for the linear transformation $\sum_{i=0}^{m-1}y_{i+1}(1-\omega^i)^n$. However, plugging in $(-\omega,1,0,\ldots, 0)$ shows this is not the case. Hence, we are done.

Solved with Luke Robitaille and Raymond Feng. We instead consider the polynomial \[R(x_1,\ldots,x_n)=x_1+\cdots+x_n-mf(x_1,\ldots,x_n),\]which reflects the remainder when \(x_1+\cdots+x_n\) is divided by \(m\), and show \(\deg R\ge n\). We induct on \(n\), with base case \(n=1\) trivial. For \(n\ge2\), assume the hypothesis for \(n-1\), and assume for contradiction \(\deg R\le n-1\). Write \[R(x_1,\ldots,x_n)=\sum_{i\ge0}x_n^i\cdot R_i(x_1,\ldots,x_{n-1}),\]so that \(\deg R_i\le n-1-i\) for each \(i\). Consider the polynomial \begin{align*} P(x_1,\ldots,x_{n-1}) &=R(x_1,\ldots,x_{n-1},0)+\frac{m-1}2-\frac1m\sum_{i=0}^{m-1}R(x_1,\ldots,x_{n-1},i). \end{align*}Since \(P\) may be expressed as a linear combination of \(R_1\), \(R_2\), \(\ldots\), it follows that \(\deg P\le n-2\). On the other hand, since \(\sum_{i=0}^{m-1}R(x_1,\ldots,x_{n-1},i)=0+1+\cdots+(m-1)=\frac{m(m-1)}2\) for \(x_1,\ldots,x_{n-1}\in\{0,1,\ldots,m-1\}\), it follows that \(P(x_1,\ldots,x_{n-1})\) is the remainder when \(x_1+\cdots+x_{n-1}\) is divided by \(m\). By the inductive hypothesis, \(\deg P\ge n-1\), contradiction.

Let $g(x_1,\cdots,x_n)=x_1+\cdots+x_n - mf(x_1,\cdots,x_n)$, then $g(x_1,\cdots,x_n)=R(x_1+\cdots+x_n,m)$ for all $x_1,\cdots,x_n\in \{0,1,\cdots,m-1\}$ where $R$ denote the remainder. Consider finite differences $$\Delta_{a_1,x_1} \Delta_{a_2,x_2} \cdots \Delta_{a_n,x_n}= \sum\limits_{0\le j_1\le a_1}\sum\limits_{0\le j_2\le a_2} \cdots \sum\limits_{0\le j_n\le a_n} (-1)^{j_1+\cdots+j_n} \binom{a_1}{j_1} \binom{a_2}{j_2} \cdots \binom{a_n}{j_n} g(j_1,\cdots,j_n)$$ Let $S=a_1+\cdots+a_n$, then if this value is nonzero we can see $\deg g\ge S$. We sum over all $j_1+\cdots+j_n=T$. By generalized Vandermonde, $$\sum\limits_{0\le j_t\le a_t \forall t, \sum j_t=T} (-1)^{j_1+\cdots+j_n} \binom{a_1}{j_1} \binom{a_2}{j_2} \cdots \binom{a_n}{j_n} = (-1)^T \binom ST$$ Therefore, this sum is simply $\sum\limits_{T=0}^S (-1)^T \binom ST R(T,m)=\sum\limits_{r=0}^{m-1} r \sum\limits_{T=0}^S (-1)^T \binom ST f(T,r)$ where $f(T,r)=1$ if $m\mid T-r$ and is $0$ otherwise. Let $\omega=e^{\frac{2\pi i}{m}}$, then we can rewrite $f(T,r)=\frac 1m \sum\limits_{j=0}^{m-1} \omega^{j(T-r)}$ We have $=\sum\limits_{r=0}^{m-1} r \sum\limits_{T=0}^S (-1)^T \binom ST \sum\limits_{j=0}^{m-1} \omega^{j(T-r)} = \sum\limits_{T=0}^S (-1)^T \binom ST \sum\limits_{j,r=0}^{m-1} r\omega^{jT-jr} =\sum\limits_{T=0}^S (-1)^T \binom ST \sum\limits_{j=0}^{m-1} \omega^{jT} \sum\limits_{r=0}^{m-1} r\omega^{-jr}$ Fr $j\ne 0$, we first deal with $\sum\limits_{r=0}^{m-1} r\omega^{-jr}=\sum\limits_{r=0}^{m-1} \sum\limits_{s=1}^r \omega^{-jr} = \sum\limits_{s=1}^{m-1} \sum\limits_{r=s}^{m-1} \omega^{-jr} = \sum\limits_{s=1}^{m-1} \frac{1-\omega^{-js}}{\omega^{-j}-1} = \frac{m}{\omega^{-j}-1} $ Therefore, we have $\frac 1m\sum\limits_{T=0}^S (-1)^T \binom ST\sum\limits_{j=0}^{m-1} \omega^{jT} \sum\limits_{r=0}^{m-1} r\omega^{-jr} = \sum\limits_{T=0}^S (-1)^T \binom ST\sum\limits_{j=0}^{m-1} \omega^{jT} \frac{1}{\omega^{-j}-1} = \sum\limits_{j=0}^{m-1} \frac{1}{\omega^{-j}-1} \sum\limits_{T=0}^S (-\omega^j)^T \binom ST = \sum\limits_{j=1}^{m-1} \frac{1}{\omega^{-j}-1} (1-\omega^j)^S $ Suppose this is 0 for $S=n(m-1), \cdots, n(m-1)-(m-2)$. This means $\sum\limits_{j=1}^{m-1} (1-\omega^j)^{S-1} =0$ for $m-1$ consecutive values of $S$. Note this is a Newton Sum, and we can apply recursion to see $\sum\limits_{j=1}^{m-1} (1-\omega^j)^{0} =0$, absurd! Therefore, $\deg g \ge (n-1)(m-1)+1 \ge n$ Note: If $P(x)$ is the polynomial with minimal degree such that $P(x)=\lfloor \frac xm \rfloor$ for all $0\le x\le n(m-1)$, this method basically takes finite differences of $g$ to be the same as the finite differences of $P$, and thereby proving $\deg g\ge \deg P$. Note $P(x+m)-P(x)-1$ vanishes at $x=0, \cdots, (n-1)(m-1)-1$, so it follows that $\deg(P(x+m)-P(x))\ge (n-1)(m-1)$, so $\deg P(x)\ge (n-1)(m-1)+1$. Consider the leading term $[x^t]$ term of $P(x)$ where $t\ge nm-m+1$. Then the t'th finite difference of $P$ cannot vanish. Since the t'th finite difference of $P$ is equal to a similar finite difference of $f$, it follows that $\deg f\ge \deg P$, as needed.

Hope I didn't fakesolve here, but let's see how this turns out: Let $g_0(x_1,\dots, x_n)= f(x_1,\dots, x_n) - \frac{x_1+\dots + x_n}{m}$, $g_1(x_1,\dots, x_n)= f(x_1,\dots, x_n) - \frac{x_1+\dots + x_n}{m} + \frac{1}{m}$ define $g_i$ up to $g_{m-1})$ similarly. Note that each $g$ must have the same degree (as the degree of each $g$ can be verified by bashing to be greater than $1$) and has exactly $m^{n-1}$ zeros across $\{0,1,\cdots , m-1\}^n$. Let $G(x_1,\dots, x_n) = \prod g_i(x_1, \dots, x_n)$ Then, for every $x_1, x_2 \cdots ,x_n \in \{0,1,\cdots , m-1\}$ we have $G(x_1,\dots, x_n) = 0$ since any two $g_i$ cannot share a zero and in total the product of all of these $g_i$ therefore has exactly $m^n$ zeros, or for sets of values on $\{0,1,\cdots , m-1\}^n$. As $G$ is not always equal to $0$, by Alon's Combinatorial Nullstellensatz we have the total degree of $G$ is at least $mn$ and therefore each $G$ must have degree at least $n$.

The case with $n<m$ is an immediate consequence of the Combinatorial Nullstellensatz. If $n\ge m$, I claim that taking $x_i\in \{0,1\}$ is sufficient to establish the desired claim. Work with $g=x_1+x_2+\ldots +x_n-m\cdot f$ instead of $f$, so that $g(x_1,\ldots,x_n)=[x_1+\ldots+x_n\pmod{m}]$. Consider $h(x_1,\ldots,x_{n-1})=g(x_1,\ldots,x_{n-1},1)-g(x_1,\ldots,x_{n-1},0)+P(x_1+\ldots+x_{n-1})$, where $P$ is the polynomial with degree $n-1$ that is equal to $m-1$ whenever $m|1+x_1+\ldots+x_{n-1}$ and $-1$ otherwise. Suppose that $g(x_1,\ldots,x_{n-1},1)-g(x_1,\ldots,x_{n-1},0)$ has degree at most $n-2$; as $P$ has a nonzero $\prod\limits_{i=1}^{n-1} x_i$ term, $h$ also would, but then by the Combinatorial Nullstellensatz, $h$ cannot vanish for all $x_1,\ldots,x_{n-1}\in \{0,1\}^{n-1}$, contradiction. Hence, $g(x_1,\ldots,x_{n-1},1)-g(x_1,\ldots,x_{n-1},0)$ has degree at least $n-1$ excluding $x_n$, and it also has factor $x_n$, totaling to a degree of $n$.

Sross314 wrote: Hope I didn't fakesolve here, but let's see how this turns out: Let $g_0(x_1,\dots, x_n)= f(x_1,\dots, x_n) - \frac{x_1+\dots + x_n}{m}$, $g_1(x_1,\dots, x_n)= f(x_1,\dots, x_n) - \frac{x_1+\dots + x_n}{m} + \frac{1}{m}$ define $g_i$ up to $g_{m-1})$ similarly. Note that each $g$ must have the same degree (as the degree of each $g$ can be verified by bashing to be greater than $1$) and has exactly $m^{n-1}$ zeros across $\{0,1,\cdots , m-1\}^n$. Let $G(x_1,\dots, x_n) = \prod g_i(x_1, \dots, x_n)$ Then, for every $x_1, x_2 \cdots ,x_n \in \{0,1,\cdots , m-1\}$ we have $G(x_1,\dots, x_n) = 0$ since any two $g_i$ cannot share a zero and in total the product of all of these $g_i$ therefore has exactly $m^n$ zeros, or for sets of values on $\{0,1,\cdots , m-1\}^n$. As $G$ is not always equal to $0$, by Alon's Combinatorial Nullstellensatz we have the total degree of $G$ is at least $mn$ and therefore each $G$ must have degree at least $n$. The polynomial $G$ doesn't need to have a maximal degree monomial where the degree of every $x_i$ is less than $m-1$. Maybe all maximal degree monomials have degree of some $x_i$ greater than $m-1$. This means you cannot apply Alon's nullstellensatz this way. That's the reason all other solutions consider some function that's symmetric over the $x_i$ and then bound the degree of that.

A patch of Sross314's arguement: FTSOC assume that $1 \le \deg f < n$. Taking the remainder with respect to $x_i(x_i - 1)(x_i - 2)\dots (x_i - (m-1))$ gives a minimal polynomial. WLOG assume $f$ is symmetric, or else we can redefine it as the average of its permuted variables. Let $f_i(x_1, x_2, \dots, x_n)$ be $x_1 + x_2 + \dots + x_n$ for $i \ge 1$ and let $f_0(x_1, x_2, \dots, x_n)$ be defined by Lagrange interpolation as $1$ if $x_1 + x_2 + \dots + x_n = 0$ and else the identity on $m, 2m, \dots, \left\lfloor \frac{n(m-1)}{m} \right\rfloor \cdot m$. Define the following polynomials \begin{align*} F &= \prod_{i=0}^{m-1} (m \cdot f(x_1, x_2, \dots, x_n) - f_i(x_1 + x_2 + \dots + x_n) + i) \\ G &= \prod_{s=1}^{n} \prod_{t=1}^{m-1} (x_s - t). \end{align*} Note that both these polynomials vanish on $\{0,1,\dots, m-1\}^n \setminus (0, 0, \dots, 0)$ and that $\deg F < \deg G = nm - n$. Then, consider $c$ such that $G - cF$ entirely vanishes. Then, $(x_1x_2 \dots x_n)^{m-1}$ is a maximal term, which contradicts combinatorial nullstellensatz.

Suppose not. Let $f$ be the polynomial with the fewest inputs which violates the problem condition. We can easily check the number of inputs $n$ is not $2$. If it were, then $f$ would have to be linear, and we can easily check $f$ linear don't work for two inputs. Assume WLOG that our function $f$ is symmetric in all of its inputs. If not, we can sum $f$ over all permutations of inputs and divide by $n!$, and this is a symmetric $f$ which still works. Now consider $f(0, 0, x_3, x_4, \ldots, x_n)$. Consider $$g(x_3,\ldots x_n)=f(m-1,1,x_3,x_4 \ldots x_n)-f(0,0,x_3, \ldots x_4)-1$$. This polynomial is identically $0$ when the other inputs are integers between $0$ and $m-1$. Also observe that it has degree at most $n-2$. This is because the maximum degree term in $f$ is $n-1$, and any term left over in $g$ must have degree at least $1$ in $x_1$, $x_2$. Rewrite $f$ as a polynomial in Newton sums. Consider only $x_i \in {0,1}$. Then all Newton sums are equal, and they range from $0$ to $n-2$. This means our polynomial $g$ of degree $n-2$ has $n-1$ roots for the differing values of the Newton sums, so it is identically $0$. Thus, we have $f(m-1,1,x_3,x_4, \ldots x_n)$ is identically equal to $f(0,0,x_3,x_4, \ldots x_n)+1$. It is pretty easy to get a contradiction from here given the symmetry property. One approach to this is to count the minimal number of $x_i$'s (not counting duplicates), say $a$ in a term of $f$. Then we have $f(0,0,\ldots, x_{n-a+2}, x_{n-a+3}, \ldots x_n)=0$, where we have $a-1$ nonzero terms. However, we have $f(m-1,1,\ldots, x_{n-a+2}, x_{n-a+3}, \ldots x_n)$ is not constant, which is a contradiction.

By Lagrange interpolation, let $P \in \mathbb{R}[x]$ be the minimal polynomial such that $P(x)=\lfloor \tfrac{x}{m}\rfloor$ for $x \in \{0,\ldots,n(m-1)\}$, so $d:=\deg P \leq n(m-1)$. I claim that we have $d\geq n$. Let $Q(x)=P(x+1)-P(x)$, so it has degree at most $d-1$. We have $Q(x) \in \{0,1\}$ for $x \in \{1,\ldots,n(m-1)\}$, so the polynomial $Q(x)(Q(x)-1)$ has $n(m-1)$ roots, yet is clearly nonzero (since $Q$ isn't constant, and hence can't always be in $\{0,1\}$) and thus $2(d-1) \geq n(m-1)$. If $m \geq 3$ this implies $d \geq n$, so now we deal with $m=2$. In this case, we can actually explicitly write down all of the first $n$ finite differences of $P$ on $\{0,\ldots,n\}$: the $k$-th difference alternates between $+2^k$ and $-2^k$, by induction. The $n$-th difference is thus not identically $0$, so $\deg P \geq n$. Now consider the $\mathbb{R}[x_1,\ldots,x_n]$ polynomial $f(x_1,\ldots,x_n)-P(x_1+\cdots+x_n)$, which vanishes on $\{0,\ldots,m-1\}^n$. If $\deg f<n$, then since $d \geq n$ it follows that the $(x_1+\cdots+x_n)^d$ term is "intact" in this polynomial, so since $d \leq n(m-1)$ by the binomial theorem we can find some term $x_1^{m-1}x_2^{m-1}\ldots x_{i-1}^{m-1}x_i^j$ in its expansion for some $j \leq m-1$. But this contradicts combinatorial nullstellensatz. $\blacksquare$