0
$\begingroup$

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

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

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jul 24, 2014 at 4:52

You must log in to answer this question.

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