# Maximize combinatorial sum for boolean function

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

• $n$ and $t$ given, $t > 1$? $(n-1)/t$ an integer? How did this problem arise? – Robert Israel Jul 23 '14 at 19:36
• Yes, n,t are integers, $n>t$, $t>1$. – user56357 Jul 24 '14 at 3:53
• You mean, $f(x)=1$, and not $f(x)=x$ i suppose. (I edited the question) – 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$.
• 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$. – user56357 Jul 24 '14 at 4:52