For what polynomials P(n) with integer coefficients can a positive integer be assigned to every lattice point in R3 so that for every integer n≥1, the sum of the n3 integers assigned to any n×n×n grid of lattice points is divisible by P(n)? Proposed by Andre Arslan
Problem
Source: ELMO 2013/5, by Andre Arslan; also Shortlist N2
Tags: algebra, polynomial, geometry, 3D geometry, modular arithmetic, number theory, hehecombinatoricstoo
19.06.2013 19:29
Note : I misuse the word cube, it should be rectangular prism. I claim the answer is P(x)=c⋅xn 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)≠0. Then take a prime p>max 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.
19.06.2013 20:03
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.
29.06.2013 05:16
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.
31.10.2022 00:08
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)).
23.11.2022 09:32
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
25.08.2024 18:55
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!