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

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

2011-06-05T11:22:02Z

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?

Answer by Gjergji Zaimi for Generalization of Tamarkin's ARO 1993, final round, problem 10/8: still a conjecture?

2011-06-16T08:05:57Z

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$.

Answer by zeb for Generalization of Tamarkin's ARO 1993, final round, problem 10/8: still a conjecture?

2011-06-16T20:40:09Z

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.