# Generalization of Tamarkin's ARO 1993, final round, problem 10/8: still a conjecture?

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, 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?

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.

• Thanks! I'm looking into this. First observation: you don't need to invoke base-$p$-digits; proving that $d\left(k\right)\geq 1$ (when $k$ is a nonzero multiple of $p-1$) is easy: $\frac{k}{p-1} = \frac{k}{p}+\frac{k}{p^2}+\frac{k}{p^3}+... > \left\lfloor\frac{k}{p}\right\rfloor + \left\lfloor\frac{k}{p^2}\right\rfloor + \left\lfloor\frac{k}{p^3}\right\rfloor +... = v_p\left(k!\right)$ and $\frac{k}{p-1}\in\mathbb Z$ yield $\left\lfloor\frac{k}{p-1}\right\rfloor = \frac{k}{p-1} > v_p\left(k!\right)$, so that $d\left(k\right)\geq 1$. – darij grinberg Jun 16 '11 at 21:09
• Well, the base-$p$ digits interpretation is nice to know about to compute other values of $d(k)$ that come up, for instance $d(p^2+p)$. Also it intuitively explains why we don't have $d(24) \le d(0)+d(0)+d(3)+d(10)+d(11)+1$ or $d(24) \le d(0)+d(0)+d(2)+d(7)+d(15)+1$. – zeb Jun 16 '11 at 21:25
• Speaking of things I don't need to invoke, I also don't actually need to pass to falling powers at the end either... – zeb Jun 16 '11 at 21:26
• Beautiful proof! Though, being completely clueless at digits combinatorics, I found every of your assertions about $d$ easier to check by algebra than by looking at base-$p$ representations. – darij grinberg Jun 16 '11 at 21:54

This problem is a lot of fun! There is a way you can reduce the general problem to studying average-integral polynomials (take an average-integral sequence, pick a finite but large enough subsequence, interpolate using an m-times-average-integral polynomial and then use your result on polynomials to conclude that the p-th power sequence is m-times average-integral), which, at the very least, helps shed some light on the general picture.

If I'm not mistaken the polynomials $a_nx^n+\cdots+a_0$ in $\mathbb Z[x]$ which are average-integral for $p=2$ are the ones for which $$\nu_2(a_k)\geq k-\nu_2(k!)$$ holds for all $k$. Similarly for $p=3$ we have the analogous conditions $$\nu_3(a_k)\geq \lfloor\frac{k}{2}\rfloor-\nu_3(k!).$$

Now something special happens in the cases $p\in \{2,3\}$, that such polynomials are closed under taking $p$th powers (essentially $\lfloor \sum \cdot\rfloor-\sum\lfloor\cdot\rfloor$ can not be large enough to construct a counterexample). But already for $p=5$ you have $1,n^2,n^7,n^{15}$ are all average-integral sequences, therefore so is their sum. But the following sequence $$a_n=(1+n^2+n^7+n^{15})^5$$ is not average-integral, giving us a counterexample.

Edit: Zeb in the comments gave the following counterexample for general $p>3$ $$(1+n^{p+1})^p$$ the reason being that the coefficient at $n^{p^2-1}$ is not divisible by $p^2$.

• A smaller counterexample is given by a_n = (1 + n^3 + n^10 + n^11)^5 – zeb Jun 16 '11 at 9:02
• Thanks! I have some troubles with details though (I am sleep-deprived right now, so they might answer themselves in a few days or make no sense at all): Do you claim that for general $p$, the condition is $v_p\left(a_k\right) = \left\lfloor \frac{k}{p-1} \right\rfloor - v_p\left(k!\right)$ ? And is this what you use to show that $1,n^2,n^7,n^{15}$ are all average-integral sequences for $p=5$ ? – darij grinberg Jun 16 '11 at 9:26
• Even better: I think $a_n=(1+n^{(p+1)})^p$ is a counterexample for every prime $p>3$ – zeb Jun 16 '11 at 9:30
• @darij: that is the heuristic that lead to these counterexamples, but in the end we tested the examples by hand to make sure they actually worked out. – zeb Jun 16 '11 at 9:33
• Okay, I do understand that a polynomial satisfying $v_p\left(a_k\right) \geq \left\lfloor \dfrac{k}{p-1} \right\rfloor - v_p\left(k!\right)$ is average-integral (infinitely often). This is a nice olympiad problem. I do not see how to prove (or disprove) the converse, though. Is any of the sequences $\left(1+n^2+n^7+n^{15}\right)^5$, $\left(1+n^3+n^{10}+n^{11}\right)^5$ and $\left(1+n^{p+1}\right)^p$ checkable to NOT be average-integral without programming (which is something I don't have the time for right now)? (Actually, at which iteration does it fail? At the third one?) – darij grinberg Jun 16 '11 at 13:45