Prove: there are polynomials S1,S2,… in the variables x1,x2,…,y1,y2,… with integer coefficients satisfying, for every integer n≥1, ∑d∣nd⋅Sn/dd=∑d∣nd⋅(xn/dd+yn/dd)(∗)Here, the sums run through the positive divisors d of n. For example, the first two polynomials are S1=x1+y1 and S2=x2+y2−x1y1, which verify identity (∗) for n=2: S21+2S2=(x21+y21)+2⋅(x2+y2).
Problem
Source: 2018 Brazil 4th TST Day 2 #5
Tags: algebra, polynomial
24.03.2019 06:01
26.03.2019 02:31
We prove that the Sn have integer coefficients by induction on n with base case n=1 obvious. For the inductive step, suppose S1,S2,…,Sn−1 all have integer coefficients. Let p be a prime with vp(n)=k>0; it suffices to show that pk∣∑d∣nd⋅(xn/dd+yn/dd)−∑d∣n,d≠ndSn/dd and repeating over all p will finish. Let n=pm, so every d which is not a divisor of m will vanish from the above sum when taken modulo pk; thus it's enough to show pk∣∑d∣md⋅(xn/dd+yn/dd)−∑d∣mdSn/dd. Let Ti(x1,x2,…,y1,y2,…)=Si(xp1,xp2,…,yp1,yp2,…) for every i, so by the problem hypotheses applied to the Ti,xpi,ypi the previous sum equals ∑d∣md⋅(xpm/dd+ypm/dd)−∑d∣mdSpm/dd=∑d∣md(Tm/dd−Spm/dd). Now I claim that pk divides each term of this final sum. Indeed, let md=plq for some p∤q, so it's enough to show pl+1∣Tplqd−Spl+1qd. Then by the inductive hypothesis A=Spqd is an integer polynomial, and by the Frobenius Endomorphism we have that Tqd=A+Bp for some polynomial B with integer coefficients, so we'd like to show p^{l+1} \mid (A+Bp)^{p^l} - A^{p^l} = \displaystyle\sum_{1\le i\le p^l} (Bp)^i A^{p^l-i} \binom{p^l}{i}. In fact p^{l+1} now divides every term of this final sum, because v_p \left(p^i \binom{p^l}{i}\right) = v_p \left( p^i \cdot \dfrac{p^l}{i} \binom{p^l-1}{i-1} \right) \ge i + l - v_p (i) \ge l+1\iff i\ge v_p (i)+1, which is clearly true for i\ge 1, so we're done. (Clarification for below posts: All divisibility here refers to polynomial divisibility in \mathbb Z[x]. )
26.03.2019 03:47
tastymath75025 wrote: . Let p be a prime with v_p (n)=k>0; it suffices to show that p^k \mid \displaystyle\sum_{d\mid n} d \cdot (x_d^{n/d} + y_d^{n/d}) - \displaystyle\sum_{d\mid n,d\neq n} dS_d^{n/d} and repeating over all p will finish. Here you only proved that S_n is integer for all integer values of x1,..., but this is not enough. A simple example would be S(x)=\frac{x^2+x}{2} that is integer for all integer values of x but does not have integer coefficients.
26.03.2019 04:21
Gomes17 wrote: tastymath75025 wrote: . Let p be a prime with v_p (n)=k>0; it suffices to show that p^k \mid \displaystyle\sum_{d\mid n} d \cdot (x_d^{n/d} + y_d^{n/d}) - \displaystyle\sum_{d\mid n,d\neq n} dS_d^{n/d} and repeating over all p will finish. Here you only proved that S_n is integer for all integer values of x1,..., but this is not enough. A simple example would be S(x)=\frac{x^2+x}{2} that is integer for all integer values of x but does not have integer coefficients. I'm pretty sure he's using polynomial divisibility rather than integer divisibility here... eg. the polynomial 2 is not considered to divide the polynomial x^2+x in \mathbb Z[x].
26.03.2019 20:21
Where did he mention that he was using polynomial divisibility?
27.03.2019 00:09
He is trying to prove S_n has integer coefficients by showing that n divides the coefficients in some polynomial sum (i.e. the polynomial n divdies some other polynomial). Of course he is using polynomial divisiblity Regardless, I don't understand what the complaint is, as the rest of the solution is still valid replacing integer with polynomial divisibility at every point
27.03.2019 05:52
tastymath75025 wrote: We prove that the S_n have integer coefficients by induction on n with base case n=1 obvious. For the inductive step, suppose S_1,S_2,\dots, S_{n-1} all have integer coefficients. Let p be a prime with v_p (n)=k>0; it suffices to show that p^k \mid \displaystyle\sum_{d\mid n} d \cdot (x_d^{n/d} + y_d^{n/d}) - \displaystyle\sum_{d\mid n,d\neq n} dS_d^{n/d} and repeating over all p will finish. Let n=pm, so every d which is not a divisor of m will vanish from the above sum when taken modulo p^k; thus it's enough to show p^k\mid \displaystyle\sum_{d\mid m} d\cdot (x_d^{n/d} + y_d^{n/d}) - \displaystyle\sum_{d\mid m} dS_d^{n/d}. Let T_i (x_1,x_2,\dots, y_1,y_2,\dots) = S_i (x_1^p, x_2^p, \dots, y_1^p, y_2^p, \dots) for every i, so by the problem hypotheses applied to the T_i, x_i^p,y_i^p the previous sum equals \displaystyle\sum_{d\mid m} d \cdot ( x_d^{pm/d} + y_d^{pm/d} ) - \displaystyle\sum_{d\mid m} dS_d^{pm/d} = \displaystyle\sum_{d\mid m} d \left( T_d^{m/d} - S_d^{pm/d}\right). Now I claim that p^k divides each term of this final sum. Indeed, let \dfrac{m}{d} = p^lq for some p\nmid q, so it's enough to show p^{l+1} \mid T_d^{p^lq}- S_d^{p^{l+1}q}. Then by the inductive hypothesis A = S_d^{pq} is an integer polynomial, and by the Frobenius Endomorphism we have that T_d^q = A + Bp for some polynomial B with integer coefficients, so we'd like to show p^{l+1} \mid (A+Bp)^{p^l} - A^{p^l} = \displaystyle\sum_{1\le i\le p^l} (Bp)^i A^{p^l-i} \binom{p^l}{i}. In fact p^{l+1} now divides every term of this final sum, because v_p \left(p^i \binom{p^l}{i}\right) = v_p \left( p^i \cdot \dfrac{p^l}{i} \binom{p^l-1}{i-1} \right) \ge i + l - v_p (i) \ge l+1\iff i\ge v_p (i)+1, which is clearly true for i\ge 1, so we're done. (Clarification for below posts: All divisibility here refers to polynomial divisibility in \mathbb Z[x]. ) Congratulations! Nobody solved this problem in the test!