Skip to main content
MathOverflow

Return to Question

fixed typo (i think)
Source Link
Per Alexandersson
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

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)=x$$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$?

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)=x$. 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$?

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

added 32 characters in body
Source Link
user56357
user56357
  • 1
  • 1

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)=x$. 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}}.$$ AnyOne can also consider $n\gg t$.

Any ideas to find the best function $f$?

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)=x$. 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}}.$$ Any ideas to find the best function $f$?

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)=x$. 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$?

Source Link
user56357
user56357
  • 1
  • 1

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)=x$. 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}}.$$ Any ideas to find the best function $f$?