I'm sorry, if I got the wrong expressions, I'm gonna describe it:
I got bit-strings of n bits with k ones and want to minimize "collision" The collision count of two strings $a=(a_1,...,a_n), b=(b_1,...,b_n)$ is defined by $Coll(a,b):=\sum_{i=1}^n a_i b_i$ and $a,b$ are said to "collide", if $Coll(a,b)>0$. Of course this can be generalized to higher number of strings.
Now I'm looking for a "shift" $s$ (depending on $a$), that minimizes the shifted self-collision $\sum_{i=1}^n a_{i+s}a_i $ and (if possible) the $m$-fold shifted self-collision $\sum_{i=1}^n\prod_{j=1}^m a_{i+js} $ ($i+s>n$ may be replaced by $i^\prime\in\{1,...,n\}$ with $i^\prime\equiv i+s$ (mod n))
Now my questions are:
- Is this solvable faster than $O(n²)$? (computing the collision count for a shift needs $O(n)$ and there are at most $n$ shifts
- I'm coding my bit-strings by length of consecutive 0s between two 1s $(10011 \rightsquigarrow 200 )$. Does this help to compute the collision count without translating back to the bit-string?
- Is there already any theory on that?