This is from the category "problems I cannot believe that are still open". But then again, I don't know whether it is still open; it seems to have escaped the attention of most number theorists and algebraists except for those in olympiad circles. This is the reason I am posting it here.


Let $p$ be a prime. Define a linear operator $F\_p:\mathbb R^{\mathbb Z}\to\mathbb R^{\mathbb Z}$ by


$\left(F\_p f\right)\left(n\right) = \dfrac{f\left(n\right)+f\left(n+1\right)+...+f\left(n+p-1\right)}{p}$ for every $n\in\mathbb Z$ and every $f\in\mathbb R^{\mathbb Z}$.


(Of course, elements of $\mathbb R^{\mathbb Z}$ are just two-sided infinite sequences of reals, written as functions from $\mathbb Z$ to $\mathbb R$. The operator $F\_p$ replaces a sequence by the sequence of the arithmetic means of its $p$-windows.)


An element $f\in \mathbb Z^{\mathbb Z}$ is said to be *average-integral* if it satisfies $F\_p^kf\in\mathbb Z^{\mathbb Z}$ for every nonnegative integer $k$.


For any $f\in\mathbb R^{\mathbb Z}$, define $f^p\in\mathbb R^{\mathbb Z}$ by


$f^p\left(n\right)=\left(f\left(n\right)\right)^p$ for every $n\in\mathbb Z$.


**Conjecture:** If $f\in \mathbb Z^{\mathbb Z}$ is average-integral, then so is $f^p$.


**Remarks:** For $p=2$, this was problem 8 for grade 10 in the Allrussian Mathematical Olympiad 1993, proposed by D. Tamarkin (the one of operad theory fame?). There is a discussion with several proofs of the $p=2$ case [on MathLinks](http://www.artofproblemsolving.com/Forum/viewtopic.php?t=184458), and it shows that the $p=2$ case is actually a tip of an iceberg (namely, for $p=2$, the average-integral elements of $\mathbb Z^{\mathbb Z}$ form a ring, so not only squares but also pointwise products of average-integral elements are average-integral). For $p=3$, the conjecture is still true, but the iceberg apparently is not anmyore; it took me a lengthy computation with combinatorial divisibilities to verify the conjecture. For higher $p$, I don't know of any results at all. Has anything been done since 1993 at all?



Generalization of Tamarkin's ARO 1993, final round, problem 10/8: still a conjecture?
Ok, here's how to show that $(1+n^{p+1})^p$ always gives a counterexample for $p > 3$.


Set $d(k) = \lfloor \frac{k}{p-1} \rfloor - v\_p(k!)$. Note that $d(k)$ is equal to the sum of the base-$p$ digits of $k$, divided by $p-1$, and rounded down, so for instance if $k$ is a nonzero multiple of $p-1$ then we have $d(k) \ge 1$. We have


$p^{d(k)}(F\_pn^k - n^k) = \sum\_{j=0}^{k-1}(p^{d(k)-1}{k\choose j}\sum\_{i=0}^{p-1}i^{k-j})n^j,$


and we have


$d(k)-1 + v\_p({k\choose j}) + v\_p(\sum\_{i=0}^{p-1}i^{k-j}) - d(j) $


$= \lfloor \frac{k}{p-1} \rfloor - \lfloor \frac{j}{p-1} \rfloor - v\_p((k-j)!) - 1 + v\_p(\sum\_{i=0}^{p-1}i^{k-j})$


$ = (d(k-j) + v\_p(\sum\_{i=0}^{p-1}i^{k-j})-1) + (\lfloor \frac{k}{p-1} \rfloor-\lfloor \frac{j}{p-1} \rfloor-\lfloor \frac{k-j}{p-1} \rfloor) \ge 0$,


so by induction on $k$ we can show that $p^{d(k)}n^k$ is average-integral for any $k$.


We have $d(k(p+1)) \le 1$ for $k = 1, ..., p-2$, $d(p^2-1) = 2$, and $d(p^2+p) = 0$. Thus, we easily see that $(1+n^{p+1})^p = 1 + \sum\_{k=1}^{p-2}{p \choose k}n^{k(p+1)} + pn^{p^2-1} + n^{p^2+p}$ is average-integral if and only if $pn^{p^2-1}$ is. Next, note that $pn^{p^2-1}-pn^{\underline{p^2-1}}$ is a sum of multiples of $p$ times monomials $n^k$ with $k < p^2-1$, and that for $k < p^2-1$ we have $d(k) \le 1$, so $pn^{p^2-1}$ is average-integral if and only if $pn^{\underline{p^2-1}}$ is.


Now note that we can express $\frac{\Delta^{p-1}f}{p}$ as an integral linear combination of $F\_pf$ and the shifts of $f$, since we have $(-1)^k{p-1 \choose k} \equiv 1 \pmod{p}$. Thus, if $pn^{\underline{p^2-1}}$ was average-integral then we would have $\frac{\Delta^{p^2-1}pn^{\underline{p^2-1}}}{p^{p+1}} = \frac{p(p^2-1)!}{p^{p+1}}$ an integer, but this is obviously not the case, so we're done. (And thus, $(1+n^{p+1})^p$ fails to be average-integral by the $p+1$st iteration.)


Edit: In fact, we can show that a polynomial in $n$ produces an average-integral sequence if and only if it can be expressed as a $\mathbb{Z}\_{(p)}$-linear combination of terms of the form $p^{d(k)}n^k$, or equivalently if it can be expressed as a $\mathbb{Z}\_{(p)}$-linear combination of terms of the form $p^{d(k)}n^{\underline{k}}$.


The second claim is much easier to prove: we have $\frac{\Delta^{p-1}p^{d(k)}n^{\underline{k}}}{p} = p^{d(k)-1}k^{\underline{p-1}}n^{\underline{k-(p-1)}}$, which is an integer relatively prime to $p$ times $p^{d(k-(p-1))}n^{\underline{k-(p-1)}}$. Also, if $k < p-1$, then $d(k) = 0$ and we can recover the coefficient of $n^{\underline{k}}$ from the first $p-1$ values of the polynomial without doing any multiplication or division by $p$.


For the first claim, take a polynomial which is not an integer combination of terms of the form $p^{d(k)}n^k$, and look at the largest $k$ such that the coefficient on $n^k$ is not a multiple of $p^{d(k)}$. By subtracting off a polynomial that we already know to be average-integral (ignoring denominators other than $p$), we can assume that this is the leading term of the polynomial. Now convert to the falling power basis, and note that the leading term remains the same, to show that this polynomial is not average-integer.


