I am trying to maximize the function $$ S(f)=\sum_{j=0}^{n-\frac{n-1}{t}}(-1)^j{n-\frac{n-1}{t}\choose{j}}\sum_{i=0}^{\frac{n-1}{t}}(-1)^{f(i-j)}(t-1)^i{\frac{n-1}{t}\choose{i}} $$ for a function $f:\mathbb{Z}\rightarrow\{0,1\}$. So, I want to find a sequence of signs + and -, which maximizes S(f). One can easily compute this expression for $f(x)=0$ and for $f(x)=1$. In the first case one will obtain $0$, in the second - $$(-1)^{\frac{n-1}{t}}(t-2)^{\frac{n-1}{t}}2^{n-\frac{n-1}{t}}.$$ One can also consider $n\gg t$.

Any ideas to find the best function $f$?

  • $\begingroup$ $n$ and $t$ given, $t > 1$? $(n-1)/t$ an integer? How did this problem arise? $\endgroup$ – Robert Israel Jul 23 '14 at 19:36
  • $\begingroup$ Yes, n,t are integers, $n>t$, $t>1$. $\endgroup$ – user56357 Jul 24 '14 at 3:53
  • $\begingroup$ You mean, $f(x)=1$, and not $f(x)=x$ i suppose. (I edited the question) $\endgroup$ – Per Alexandersson Aug 22 '14 at 20:24

Let $m = (n-1)/t$. For convenience, I'll assume this is an integer.
For fixed $k$, the contribution from terms with $i-j=k$ is $$ (-1)^{f(k)} \sum_{j=\max(0,-k)}^{\min(n-m,m-k)} (-1)^j {{n-m}\choose j} {m \choose {j+k}} (t-1)^{j+k} $$ So you choose $f(k)$ to make that contribution $\ge 0$.

| cite | improve this answer | |
  • $\begingroup$ Actually, this expression can be reformulated with help of q-Krawtchouk polynomials and it was a staring point. Unfortunately, nobody knows the way to predict, whether a given Krawtchouk polynomial is greater than $0$. $\endgroup$ – user56357 Jul 24 '14 at 4:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.