Note : I misuse the word cube, it should be rectangular prism. I claim the answer is $P(x) = c \cdot x^n$ for some non-zero integer $c$ and non-negative integer $n$. First, we prove if a polynomial $P$ works it must be of this form. Take an irreducible divisor $P'$ of $P(x)$ and assume $P'(0) \neq 0$. Then take a prime $p > \max(P'(0), a_{(0,0,0)})$ where $a_{(0,0,0)}$ denotes the number on the origin and $p$ satisfies $p|P'(k)$ for some $k$. Clearly $k \not \equiv 0 \pmod{p}$ as $P'(0) \neq 0$, so by Dirichlet's Theorem there exist primes $a,b,c,d,e,f,g,h$ such that $a \equiv b \equiv ... \equiv h \equiv k \pmod{p}$. Now, it is clear that every $abcd \times ab \times a$ cube of lattice points satisfies that the sum of its elements is divisible by $p$. Similarly every $abcd \times ab \times b$ satisfies a similar conclusion. It follows by Bezout's Lemma that $\gcd(a, b) =1$ we can find positive integers $x,y$ such that $a \cdot x - b \cdot y = \pm 1$ (WLOG it is $+$). Then by sticking together $x$ $abcd \times ab \times a$ blocks and then subtracting out $y$ blocks of $abcd \times ab \times b$ we get $p$ divides the sum of the elements of a $abcd \times ab \times 1$ cube. By similar logic it also holds true for a $abcd \times cd \times 1$ cube. Then by the same Bezout argument, $p$ divides the sum of elements of a $abcd \times 1 \times 1$ cube. Similarly $p$ divides the sum of elements of a $efgh \times 1 \times 1$ cube. But then by Bezout again, it divides the sum of elements of any $1 \times 1 \times 1$ cube. Considering the cube at the origin, we get a contradiction because as $0 < a_{(0,0,0)} < p$, $p \nmid a_{(0,0,0)}$. It follows we require $x|P'(x)$ and thus it follows $P$ must be of the form $z \cdot x^n$ for $z$ a non-zero integer $z$ and $n$ a non-negative integer. Now for the construction. It obviously suffices to construct it for the case of one dimension and then assign to the point $(x,y,z)$ the value given at $x$ for the one dimensional case. Call $Q(n)$ the value at $n$ in the 1d analog. WLOG $P(x) = x^n$, because we can just scale $Q$ by $c$ to account for a leading coefficient. Now let $Q(1) = 1$ and $Q(2) = 2^n - 1$. We now go through a recursive process defining $Q(0), Q(3), Q(-1), Q(4), Q(-2)...$ and so on. Suppose we are defining $Q(k)$ and it is the $m^{th}$ number we are defining. If $k$ is negative, then we will define $Q(k) \equiv Q(k+z) \pmod{z^n}$ for each $1 \le z \le m-1$ and for $k$ positive replace $Q(k+z)$ with $Q(k-z)$. Obviously if such a $Q(k)$ exists at each step, then we would be done. To prove such a solution exists when solving the system of congruences it suffices to check that when $\gcd(a,b) \neq 1$, we have $Q(k+a) \equiv Q(k+b) \pmod{\gcd(a,b)^n}$. Luckily, this is easy since we have $Q(k+a) \equiv Q(k+b) \pmod{|b-a|^n}$ and as $\gcd(a,b)|(b-a)$, it follows the system is consistent and thus a solution exists by CRT. Therefore we are done. Apparently the construction stumped everyone at MOP... hmm the construction is (very) silly.

dinoboy wrote: Apparently the construction stumped everyone at MOP... hmm the construction is (very) silly. I think a more accurate statement is "almost everyone at MOP failed to realize that there were solutions of degree higher than three". The construction is not hard once you realize it's possible.

dinoboy wrote: Luckily, this is easy since we have $Q(k+a) \equiv Q(k+b) \pmod{|b-a|^n}$ and as $\gcd(a,b)|(b-a)$, it follows the system is consistent and thus a solution exists by CRT. Therefore we are done. Apparently the construction stumped everyone at MOP... hmm the construction is (very) silly. Yeah, I personally think that analyzing the 1D case makes the answer and construction pretty clear. Also, note that polynomial constructions cannot work for $cx^{d+1}$ in $d$ dimensions. Suppose otherwise, and take a minimal degree $f(x_1,\ldots,x_d)$; then $f$ isn't constant, so $f'(x_1,\ldots,x_d) = f(x_1+1,\ldots,x_d+1) - f(x_1,\ldots,x_d)$ is a working polynomial of strictly smaller degree.

dinoboy wrote: Note : I misuse the word cube, it should be rectangular prism. I claim the answer is $P(x) = c \cdot x^n$ for some non-zero integer $c$ and non-negative integer $n$. First, we prove if a polynomial $P$ works it must be of this form. Take an irreducible divisor $P'$ of $P(x)$ and assume $P'(0) \neq 0$. Then take a prime $p > \max(P'(0), a_{(0,0,0)})$ where $a_{(0,0,0)}$ denotes the number on the origin and $p$ satisfies $p|P'(k)$ for some $k$. Clearly $k \not \equiv 0 \pmod{p}$ as $P'(0) \neq 0$, so by Dirichlet's Theorem there exist primes $a,b,c,d,e,f,g,h$ such that $a \equiv b \equiv ... \equiv h \equiv k \pmod{p}$. Now, it is clear that every $abcd \times ab \times a$ cube of lattice points satisfies that the sum of its elements is divisible by $p$. Similarly every $abcd \times ab \times b$ satisfies a similar conclusion. It follows by Bezout's Lemma that $\gcd(a, b) =1$ we can find positive integers $x,y$ such that $a \cdot x - b \cdot y = \pm 1$ (WLOG it is $+$). Then by sticking together $x$ $abcd \times ab \times a$ blocks and then subtracting out $y$ blocks of $abcd \times ab \times b$ we get $p$ divides the sum of the elements of a $abcd \times ab \times 1$ cube. By similar logic it also holds true for a $abcd \times cd \times 1$ cube. Then by the same Bezout argument, $p$ divides the sum of elements of a $abcd \times 1 \times 1$ cube. Similarly $p$ divides the sum of elements of a $efgh \times 1 \times 1$ cube. But then by Bezout again, it divides the sum of elements of any $1 \times 1 \times 1$ cube. Considering the cube at the origin, we get a contradiction because as $0 < a_{(0,0,0)} < p$, $p \nmid a_{(0,0,0)}$. It follows we require $x|P'(x)$ and thus it follows $P$ must be of the form $z \cdot x^n$ for $z$ a non-zero integer $z$ and $n$ a non-negative integer. Now for the construction. It obviously suffices to construct it for the case of one dimension and then assign to the point $(x,y,z)$ the value given at $x$ for the one dimensional case. Call $Q(n)$ the value at $n$ in the 1d analog. WLOG $P(x) = x^n$, because we can just scale $Q$ by $c$ to account for a leading coefficient. Now let $Q(1) = 1$ and $Q(2) = 2^n - 1$. We now go through a recursive process defining $Q(0), Q(3), Q(-1), Q(4), Q(-2)...$ and so on. Suppose we are defining $Q(k)$ and it is the $m^{th}$ number we are defining. If $k$ is negative, then we will define $Q(k) \equiv Q(k+z) \pmod{z^n}$ for each $1 \le z \le m-1$ and for $k$ positive replace $Q(k+z)$ with $Q(k-z)$. Obviously if such a $Q(k)$ exists at each step, then we would be done. To prove such a solution exists when solving the system of congruences it suffices to check that when $\gcd(a,b) \neq 1$, we have $Q(k+a) \equiv Q(k+b) \pmod{\gcd(a,b)^n}$. Luckily, this is easy since we have $Q(k+a) \equiv Q(k+b) \pmod{|b-a|^n}$ and as $\gcd(a,b)|(b-a)$, it follows the system is consistent and thus a solution exists by CRT. Therefore we are done. Apparently the construction stumped everyone at MOP... hmm the construction is (very) silly. I think we need to add the condition that $m^n\mid (Q(k)+\ldots+Q(k+m))$ (resp. $m^n\mid(Q(k)+\ldots+Q(k-m))$) during the inductive definition of $Q$. Or we will just get $P(n)\mid (Q(k+n)-Q(k))$ but not $P(n)\mid(Q(k)+\ldots+Q(k+n-1))$.

We claim the answer is $P(x)=c \cdot x^k$ Let $f(x,y,z)$ be the number assigned to the point $(x,y,z)$. Assume that a polynomial $P(n)$ works, If we let \[ a_k = \sum_{x \leq n} \sum_{y \leq n} f(x,y,k) \]then $\ldots, a_{-1}, a_0, a_1, \ldots$ is the 1D version of the original problem. So, we work with the 1D case from now on. We will denote $P$ by $P_0$ from now on. Notice that $a$ divides $b$ implies $P_0(a)$ divides $P_0(b)$. Claim: $x$ divides $P_0(x)$ or $P_0$ is constant Let $P_0(x) = x \cdot P_1(x)+C$. We would like to show $C=0$. We have \[ n \cdot P_1(n)+C \text{ divides } nk \cdot P_1(nk)+C \]\[ \implies n \cdot P_1(n)+C \text{ divides } nk \cdot P_1(nk) - n \cdot P(n)= n(P_1(nk)-P(n))\] Since $C \not = 0$, we can choose infinitely many $n$ where $\gcd(n,C)=1=\gcd(n \cdot P_1(n)+C,n)$. So, $n \cdot P_1(n)+C \text{ divides } P_1(nk)-P(n)$. But $\deg(n \cdot P_1(n)+C)>\deg(P_1(nk)-P(n))$. Implying the LHS gets larger than the RHS for sufficiently large $n$. So, the divisibility cannot hold. $\square$ Thus, we will let $P_0(x) = x \cdot P_1(x)$ Claim: $P_1$ is divisible by $x$ or $P_1$ is constant. Recall we have $P_0(n)$ divides $\sum_{i=1}^n a_{k+i}$ for every $k$ and $n$. This implies that $n$ and $P_1(n)$ divides $\sum_{i=1}^n a_{k+i}$. So, \[ a_{k} \equiv a_{k+n} \equiv a_{k+P_1(n)} \pmod{P_1(n)} \]by bezouts identity, we have $a_k \equiv a_{k + \gcd(n,P_1(n))} \pmod{P_1(n)}$. Assume that $\gcd(n,P_1(n))=1$ infinitely often. This means that $a_k \equiv a_{k+1} \pmod{P_1(n)}$ for infinitely many choices of $n$. Implying the sequence $a_i$ is constant, so $P_0$ is constant. Thus, $\gcd(n,P_1(n))=1$ finitely often. Hence, if we choose sufficiently large primes $p_1,p_2, \ldots$ then $p_i$ divides $P_1(p_i)$ for all $i$. So, $P_1(p_i) \equiv P_1(0) \equiv 0 \pmod{p_i}$ for infinitely many primes. Thus, $P_1(0)=0$, giving $x$ divides $P_1(x)$ as desired. $\square$ We proceed the same proof inductively for $P_2,P_3, \ldots$. Each one is either divisible by the identity or constant. Thus, $P(x) = c \cdot x^k$ as desired. Now, for construction. We can do a "just do it approach" on $a_0,a_1,a_{-1},a_2,a_{-2}, \ldots$. Choosing each one appropriately. We can do this by CRT. We are done, yay! $\blacksquare$

lol I like how this problem is essentially equivalent to the 1D case The only answers are $P(n) = c n^k$ for $k \geq 0$. Construction: It suffices to construct for $P(n) = n^k$. Let $R(x, y, z)$ be the number associated at every point $(x, y, z) \in \mathbb N^3$; we extend $R$ to $\mathbb Z^3$ by defining $R(-x, y, z) = R(x, y, z)$ and so on, so we will only consider in $\mathbb N^3$ from now on. We will define the function \[Q(x, y, z) = \sum_{x'=0}^x \sum_{y'=0}^y \sum_{z'=0}^z R(x', y', z')\]to be a prefix sum, so in particular the sum of any $n \times n \times n$ block is given by \[\sum_{x'=x-n+1}^x \sum_{y'} \sum_{z'} R(x', y', z') = Q(x, y, z) - \sum_{\mathrm{cyc}} Q(x-n, y, z) + \sum_{\mathrm{cyc}} Q(x-n, y-n, z) + Q(x-n, y-n, z-n).\] Claim: For $k$ fixed, there exists a function $Q(n)$ defined on $\mathbb Z_{\geq 0}$ such that for any prime power $p^\ell$, \[Q(m) \equiv Q(n) \pmod {p^{k\ell}}\]whenever $m \equiv n \pmod {p^\ell}$. Proof: By induction. Let $Q(0) = 0$. Furthermore, suppose that the condition is true for all $m', n' < n$. For each $n$ and prime $p$, let $p^\ell$ be the largest power of $p$ less than $n$, and let $Q(n)$ be the minimal solution to the system of congruences \[Q(n) \equiv Q\left(n \bmod p^{\ell}\right) \pmod {p^{k\ell}}\]across all such prime powers $p^\ell$ by CRT. Then, for any smaller prime power $p^r$, if $m \equiv n \pmod {p^r}$, we have \[Q(n) \equiv Q\left(n \bmod p^\ell\right) \equiv Q\left(n \bmod p^r \right) \equiv Q(m) \pmod {p^{r\ell}}\]by the inductive hypothesis. $\blacksquare$ We now define $Q(x, y, z) = Q(x)Q(y)Q(z)$ for $Q$ satisfying the properties of the claim. Then for any $n$ and $p \mid n$ with $\nu_p(n) = \ell$, the condition implies \[Q(x, y, z) \equiv Q(x', y', z') \pmod {p^{k\ell}}\]by definition of the $Q$'s. Using the prefix sum formula, $p^{k\ell}$ divides the sum of the $n \times n \times n$ block at $(x, y, z)$, ergo $n^k$ also divides the sum. Restriction: Suppose $P(n)$ is not of the above form. Take a nonconstant polynomial $P' \mid P$ with $P'(0) \neq 0$. Consider the sequence $Q(0), Q(1), \dots$ given by $Q(m) = Q(m, n-1, n-1)$. Because the $n \times n \times n$ block given by $m+1 \leq x \leq m+n$, $0 \leq y \leq n-1$, $0 \leq z \leq n-1$ has sum of $R(x, y, z)$'s a multiple of $P'(n)$, it follows that \[Q(m) \equiv Q(m+n) \pmod {P'(n)}\]for all $m, n \in \mathbb N$. Claim: Suppose that $p \mid P'(n)$ for some $p \nmid n$. Then $Q(m) \equiv Q(m') \pmod p$ for any $m, m' \in \mathbb N$. Proof. We have $p \mid P'(n)$ and $p \mid P'(n+p)$ as $P'$ is a polynomial, so $\{Q(n) \bmod p\}$ is periodic mod $n$ and $n+p$. But $\gcd(n, n+p) = 1$, so by Bezout's lemma, $\{Q(n) \bmod p\}$ is periodic mod $1$, i.e. it is constant. $\blacksquare$ Claim: There exist infinitely many $p$ with $p \mid P'(0)$. Proof. By Schur's theorem, there exist infinitely many $p$ with $p \mid P'(n)$ for some $n$ as $P'$ is nonconstant. If the claim were false, there would exist infinitely many $p$ with $p \mid P'(n)$ and $n \nmid p$, so by the previous claim, $\{Q(n) \bmod p\}$ is periodic modulo infinitely many primes $p$. This implies $Q$ is constant, or $R(x, y, z) = 0$, contradiction. $\blacksquare$ But then we must have $P'(0) = 0$, contradiction!