The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little progress, I would be very grateful to hear if anyone sees a way to approach them.

Consider a $2n$-dimensional vector $v$ with $v_i \in \{0,1\}$. Now consider an $n$-dimensional vector $w$ with $w_i \in \{-1,0,1\}$. The elements $w_i$ are sampled independently so that $P(w_i = -1) = P(w_i = 1) = 1/4$ and $P(w_i=0) = 1/2$.

Indexing from $1$, we now define $A_i = \sum_{j=1}^n w_j v_{i+j-1}$ to be the $i$th inner product between $w$ and a subvector of $v$. We know that $P(A_i = 0) \sim 1/\sqrt{\pi n}$ if all the elements of $v$ equal $1$.

**Conjecture 1**

For all sufficiently large $n$, there exists a vector $v \in \{0,1\}^{2n}$ such that $$P{\left(\forall i \leq \frac{n}{\log_2{n}}, A_i = 0\right)} \leq 2^{-\frac{n}{4}}.$$

Computationally expensive numerical experiments suggest that conjecture 1 is plausibly true. It is still interesting, and open as far as I know, to show the same result with $n/4$ replace by $n/C$ for any $C \geq 4$. In fact even an upper bound such as $2^{-n/\sqrt{\log_2{n}}}$ would be interesting.

However computational experiments suggest that the following even stronger conjecture holds which I will now set out.

A set, all of whose subset sums are pairwise distinct, is called *dissociated*. A classic question asks what is the largest possible size of a dissociated subset of the set $\{0,1\}^n\subset{\mathbb R}^n$. It is known that the largest size of its dissociated subset is
$$ \frac12(1+o(1))\,n\log_2 n; $$
see, for instance, this paper by Bshouty for details and a historical account.

In our problem, we require the dissociated subset to also have the property that there is some way of arranging the vectors within it as columns of a Toeplitz matrix.

**Conjecture 2**

The largest size of dissociated subset of the set $\{0,1\}^n\subset{\mathbb R}^n$ with the additional restriction that there is some way of arranging the vectors within it as columns of a Toeplitz matrix is $$ \frac12(1+o(1))\,n\log_2 n. $$

As far as I know, no non-trivial asymptotic results are known at all for this particular problem formulation. In a similar fashion to Conjecture 1, just about any superlinear lower bound would be a significant first step.

Computer experiments show that the largest sizes for $n=2,3,4,5,6,7,8,9,10$ appear to be $2,4,5,7,9,12,14,16,19$. These are the same as the largest sizes of a dissociated subset *without* the Toeplitz restriction (see the linked MO question above for examples of these). If anyone can find a way to find solutions for larger $n$ (or even verify my existing results) that would potentially be useful.

We can regard the rows of a Toeplitz matrix as consecutive $n$-length subvectors of the vector $v$ in Conjecture 1.

Here is a maximal solution for $n=3$.

\begin{pmatrix} 1&1&0&1\\ 0&1&1&0\\ 0&0&1&1 \end{pmatrix}

Here is a maximal solution for $n=7$ .

\begin{pmatrix} 1&0&1&0&0&1&1&0&1&1&1&1\\ 1&1&0&1&0&0&1&1&0&1&1&1\\ 1&1&1&0&1&0&0&1&1&0&1&1\\ 0&1&1&1&0&1&0&0&1&1&0&1\\ 0&0&1&1&1&0&1&0&0&1&1&0\\ 1&0&0&1&1&1&0&1&0&0&1&1\\ 0&1&0&0&1&1&1&0&1&0&0&1 \end{pmatrix}

A standard method to prove that large dissociated sets exist is via the probabilistic method. That is pick one uniformly at random and show there is a non-zero probability that it is dissociated. I don't see how to use this approach for my problem however.