I would like to construct a set $S\subseteq\{0,1\}^{2n}$ that satisfy the property:

$$\forall x\neq y\in S\ \ \exists k\in [n]:\forall i,j\in[n], \sum_{t=k+i}^{2n}x_t\neq\sum_{t=k+j}^{2n}y_t$$

In other words, for every two vectors in $S$, there exists $k\in\{0,1,\ldots,n\}$ such that if we delete the first $k$ bits of $x,y$, we can't get the same number of $1$'s in both, after deleting some additional $i,j\in\{0,\ldots,n\}$ bits accordingly.

The motivation for the problem comes from a showing lower bound for a streaming problem in which the answer may rely on approximate sliding window whose size can vary between $n$ and $2n$.

A simple construction for such $S$ is $$\{0^{n+b}1^{n-b}\mid b\in[n]\},$$

As every two words $0^{n+q}1^{n-q}$,$0^{n+a}1^{n-a}$ satisfy the condition for $k=0$.

This gives a lower bound on the size of such $S$ of $n+1$.

If I am not mistaken (didn't get to fully prove it yet), my algorithm implies an upper bound of $O(n^2)$.

What is the maximal size of a set $S$ that satisfies the above property?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.