1
$\begingroup$

Let us look at the abelian group $V$ of integer valued sequences modulo sequence which are zero almost everywhere.

Let me fix one constant $k\in \mathbb{N}$, which I will omit from the notation. One specific sequence is given by $a_n = \binom{n+k}{n}$. Let $\Sigma^m a$ be the shift of $a$ by $m$, i.e. $(\Sigma^ma)_n =a_{n-m}$. Now I am interested in zero combinations of those shifts.

Question: Given integers $\lambda_m$ (such that almost all,but not all integers are zero) and such that

\[\sum_m \lambda_m(\Sigma^ma)=0 \in V,\]

then $\sum_m |\lambda_m|\ge 2^{k+1}$.

A example where the (conjectured) minimum is obtained is the following. Let $T:V\rightarrow V$ be the difference operator, i.e. it is defined via $(Ta)_n=a_{n+1}-a_n$. Since $a$ is a polynomial of degree $k$, we have $T^{k+1}a =0$ and if we write the left hand side out, we get exactly $2^{k+1}$ as that sum.

Improve this question
$\endgroup$
3
  • $\begingroup$ The first sentence means "... of {\em integer} valued sequences ...", right? $\endgroup$
    – ThiKu
    Commented May 30, 2017 at 14:21
  • 1
    $\begingroup$ Equivalent reformulation: if a polynomial $f(t)$ with integer coefficients is divisible by $(t-1)^{k}$, then the sum of absolute coefficients is not less than $2^{k+1}$. $\endgroup$
    – Fedor Petrov
    Commented May 30, 2017 at 15:03
  • $\begingroup$ @ Fedor: I guess there is an index shift somewhere. In your reformulation it should be "less than $2^k$", since otherwise $p(t)=1$ would be an obvious counterexample. Furthermore it follows that $p = f/(t-1)^k$ must be divisible by $t+1$ (Otherwise plug in $t=-1$). $\endgroup$
    – HenrikRüping
    Commented May 30, 2017 at 16:36

1 Answer 1

Reset to default
1
$\begingroup$

Consider the Laurent polynomial $f(t)=\sum \lambda_m t^m$. It is easy to prove that your conditions are equivalent to a system of $k+1$ equations $f^{(i)}(1)=0$ for $i=0,\dots,k$. In other words, $f(t)=(t-1)^{k+1}h(t)$ for some Laurent polynomial $h$ with integer coefficients. If $h(-1)\ne 0$, we get $|f(-1)|\geqslant 2^{k+1}$, this implies your claim. But if $h(-1)\ne 0$, it may fail, for example, consider $k=2$ and $f(t)=(t-1)(t^2-1)(t^3-1)$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Add the extra condition that the $\lambda$ are all $0,\pm 1.$ If I'm not mistaken it is an open problem if there is always a solution with the absolute values of these coefficients adding to $2k.$ $\endgroup$
    – Aaron Meyerowitz
    Commented May 30, 2017 at 15:56
  • $\begingroup$ Hm so what is the best lower bound possible? $\endgroup$
    – HenrikRüping
    Commented May 30, 2017 at 16:44
  • $\begingroup$ @Aaron, you're referring to the Tarry-Escott (or, multigrade) problem? $\endgroup$
    – Gerry Myerson
    Commented May 31, 2017 at 0:24
  • $\begingroup$ @GerryMyerson Indeed, the Prohet-Tarry-Escott problem is what I had in mind. $\endgroup$
    – Aaron Meyerowitz
    Commented May 31, 2017 at 14:16
  • $\begingroup$ So on my comment I should have said $2k+2.$ Thst is a lower bound and is exact for small values. $\endgroup$
    – Aaron Meyerowitz
    Commented May 31, 2017 at 14:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .