# Two conjectures about zero inner products and dissociated sets

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.

• Comments: 1) $P(A_i=0)$ is $C/\sqrt{n}$ if $v=1$ identically, but if not if $v=0$ say. 2) Do you care about $n/4$ as opposed to $n/1000$? 3) It is easy to get $2^{-n/\log n}$ instead of $2^{-n/4}$ by letting $v$ to be the vector that is all $1$ except that $n$'th position that is $0$. Do you have a better bound? – Boris Bukh May 19 '15 at 18:15
• @BorisBukh 1) Thank you. 2) $n/1000$ would be fine too. 3) For my purposes I need $2^{-n/C}$ for some constant $C \geq 1$. I don't have any such bound sadly. I don't have anything significantly better than the trivial bound you gave. – Raphael May 19 '15 at 18:32

Thank you Raphael for this very interesting and challenging problem! The following is an approximate argument supporting both Conjecture 1 and Conjecture 2. Perhaps it can give a hint at how to construct a more rigorous proof.

Let me start by reformulating Conjecture 1 somewhat. As has already been indicated in the question, we can from the $2n$-dimensional vector $v$ construct a $m \times n$ Toeplitz matrix $M$ with elements $M_{m+1-i,j} = v_{i+j-1}$ for $j=1,...n$ and $i=1,...,m$ (where $m=\lfloor \frac n{\log_2n} \rfloor < n$). Defining, furthermore, $a_i = A_{m+1-i}$ (i.e., just reversing the order of the elements), we then have in matrix notation $a=Mw$, and Conjecture 1 can be re-stated in the following form:

Conjecture 1*

For sufficiently large $n$, there exists a Toeplitz matrix $M \in \{0,1\}^{m \times n}$, with $m=\lfloor \frac n{\log_2n} \rfloor$, such that $P(Mw=0)\leq2^{-\frac n4}$.

I will now construct an argument supporting Conjecture 1* (or actually, as we will see, a somewhat stronger conjecture).

Let us define the characteristic function (= "Fourier transform") of the distribution of the vector $a=Mw$ as $$\tilde P(\xi) = \left\langle {\rm e}^{2\pi{\rm i}\,\xi^{\rm T}Mw} \right\rangle_w \ , \hspace{2cm} (1)$$ where $\left\langle \cdots \right\rangle_w$ denotes the average over $w \in \{-1,0,1\}^n$ with the probabilities specified in the question. Since the random vector $a=Mw$ has integer components, the quantity we are interested in can be expressed by the following $m$-dimensional integral: $$P(Mw=0) = \int_{[-\frac12,\frac12]^m} {\rm d}^m\xi \ \tilde P(\xi) \ . \hspace{2cm} (2)$$ On the other hand, the $w$ average in $(1)$ can easily be carried out explicitly, with the result $$\tilde P(\xi) = \prod_{j=1}^n \cos^2 \left( \pi \sum_{i=1}^m \xi_i M_{ij} \right) \ . \hspace{2cm} (3)$$ We thus have an $n$-fold product of periodic $\cos^2$ terms, being a function of $m$ real variables $\xi_i$, each of which is integrated over the interval $[-\frac12,\frac12]$. Since this multiple integral seems too hard to do, I use the following approximation: $$\cos^2 (\pi t) \approx \sum_{k=-\infty}^\infty {\rm e}^{-4\pi(t-k)^2} \ , \hspace{2cm} (4)$$ which has been chosen in such a way that its maximum value is close to $1$ (the maximum of $\cos^2$) and that it also preserves the integral value $\int_{-1/2}^{1/2} {\rm d}t\ \cos^2 (\pi t) = \frac12$ over one period. Now we can re-write $(2)$ as \begin{align} P &\approx \int_{[-\frac12,\frac12]^m} {\rm d}^m\xi \ \prod_{j=1}^n \left[ \sum_{k_j=-\infty}^\infty {\rm e}^{-4\pi \big( \sum_{i=1}^m \xi_i M_{ij} - k_j \big)^2} \right] \nonumber\\ &= \sum_{k\, \in\, \mathbb Z^n} \left[ \int_{[-\frac12,\frac12]^m} {\rm d}^m\xi \ \ {\rm e}^{-4\pi (M^{\rm T}\xi-k)^{\rm T}(M^{\rm T}\xi-k)} \right] \ . \nonumber \hspace{2cm} (5) \end{align} The integrand is now a multidimensional gaussian, which would be easy to handle if the $k$ sum were an integral instead of a sum, and/or if the bounds of the $\xi$ integration were at infinity instead of $\pm1$. I will now describe ways to circumvent these problems.

First I will try to turn the $\xi$ integration with finite integration bounds into a pure gaussian integral with bounds at infinity. The idea is to perform a singular-value decomposition of $M$, re-interpret $\xi \in [-\frac12,\frac12]^m$ as a random vector with i.i.d. components (each having mean $0$ and variance $\langle \xi_i^2 \rangle = \frac\gamma{8\pi}$), and then apply the central limit theorem. The variance parameter $\gamma$ has the definite value $$\gamma\, = 8\pi \int_{-\frac12}^{\frac12}{\rm d}\xi\, \xi^2 = \frac{2\pi}3 \ , \hspace{2cm} (6)$$ but for the moment I will keep it as a parameter. Expressing the $m$-dimensional $\xi$ integration as a stochastic average, $\langle \cdots \rangle_\xi = \int_{[-\frac12,\frac12]^m} {\rm d}^m\xi(\cdots)$, Eq. $(5)$ reads $$P \approx \sum_{k\, \in\, \mathbb Z^n} \left\langle {\rm e}^{-4\pi \big(M^{\rm T}\xi-k\big)^{\rm T}\big(M^{\rm T}\xi-k\big)} \right\rangle_\xi \ . \hspace{2cm} (7)$$ Now we use the singular value decomposition $M=V \Sigma U^{\rm T}$ with orthoganal matrices $V$, $U$ and a rectangular diagonal matrix $\Sigma$, containing on its diagonal the (non-negative) singular values $\sigma_i$ of $M$. Denoting the orthonormal column vectors of $U$ by $U_j$ ($j=1,...,n$) and those of $V$ by $V_i$ ($i=1,...,m$) we can write this decomposition as follows: $$M = \sum_{i=1}^m \sigma_i V_i U_i^{\rm T} \ . \hspace{2cm} (8)$$ The eigenvalues of $MM^{\rm T}$ are $\lambda_i = \sigma_i^2$ ($i=1,...,m$) . Inserting $(8)$ into $(7)$ then yields $$P \approx \sum_{k\, \in\, \mathbb Z^n} \left\langle {\rm e}^{-4\pi \big( \sum_{i=1}^m \lambda_i \eta_i^2 - 2 \sum_{i=1}^m \eta_i \sigma_i U_i^{\rm T}k + k^{\rm T} k \big)} \right\rangle_\eta \ , \hspace{2cm} (9)$$ with $\eta_i = V_i^{\rm T}\xi$ (i.e., $\eta = V^{\rm T}\xi$). If we assume that all the components of the matrix $V$ have "similar size" ($\approx m^{-\frac12}$) in some suitable sense (for instance, they might be normal distributed with variance $m^{-1}$), it follows from the central limit theorem that for large $m$ the $\eta_i$ are uncorrelated gaussian random variables with zero mean and covariance matrix $\langle \eta_i \eta_j \rangle = \frac\gamma{8\pi} V_i^{\rm T}V_j = \frac\gamma{8\pi} \delta_{ij}$. This in turn suggests that, asymptotically, $(9)$ can be re-written as \begin{align} P &\sim \sum_{k\, \in\, \mathbb Z^n} \left[ (\gamma/4)^{-\frac m2} \int_{\mathbb R^m} {\rm d}^m\eta \ \ {\rm e}^{-4\pi \big( \sum_{i=1}^m\eta_i^2/\gamma + \sum_{i=1}^m \lambda_i \eta_i^2 - 2 \sum_{i=1}^m \eta_i \sigma_i U_i^{\rm T}k + k^{\rm T} k \big)} \right] \nonumber\\ &\sim \left[ \prod_{i=1}^m \big( 1 + \gamma\, \lambda_i \big)^{-\frac12} \right] \sum_{k\, \in\, \mathbb Z^n} \exp {-4\pi \left[ \sum_{i=1}^m \frac{(U_i^{\rm T}k)^2}{1 + \gamma\, \lambda_i} + \sum_{j=m+1}^n (U_j^{\rm T}k)^2 \right]} \ . \nonumber \hspace{.5cm} (10) \end{align} Note that according to $(10)$, it seems that the quantity $P$ asymptotically only depends on the eigenvalue spectra of the (symmetric) matrices $\Lambda = MM^{\rm T}$, i.e. on the $\lambda_i$. (In addition, it may depend, in some subtle way, on the orthonormal vectors $U_j$ defined by the singular value decomposition of $M$, but let me disregard this possibility for the moment.)
The matrix elements of $\Lambda = MM^{\rm T}$ can be expressed in the form $$\Lambda_{ij} = \frac n4 (\delta_{ij} + 1) + \mu_{ij} \ , \hspace{2cm} (11)$$ where $\mu_{ij}$ are gaussian random variables with mean $0$ and variance $\langle \mu_{ij}^2 \rangle \approx \frac n4$ (but not necessarily uncorrelated with each other). Using random matrix theory one can shown that the distribution of the eigenvalues $\lambda_i$ of such a $m \times m$ matrix $\Lambda$ for $m \ll n$ is sharply peaked around $\lambda = \frac n4$ (the width of the distribution being $\lambda_{\rm max} - \lambda_{\rm min} \approx \sqrt{mn}$), apart from a single large eigenvalue which is of the order $\lambda \approx \frac{mn}4$. Strictly speaking, random matrix theory guarantees this only if either the $\mu_{ij}$ or the original matrix elements $M_{ij}$ are independent random variables, but numerical experiments suggest that it also holds for random Toeplitz (or circulant) matrices $M$ (I have done such tests for matrix sizes up to $m=4\times10^3$, $n=2\times10^5$). From this I conclude that we can replace all $\lambda_i$ in $(10)$ by $\frac n4$, except one which is $\sim \frac{mn}4$.

Now we can try to further evaluate $(10)$. If we were allowed to replace the $k$ sum by an $n$-dimensional integral then we would obtain \begin{align} \sum_{k\, \in\, \mathbb Z^n} \exp-4\pi(\cdots) &\sim \int_{k\, \in\, \mathbb R^n} {\rm d}^n k \ \exp-4\pi(\cdots) \nonumber\\ &= 2^{-n} \left[ \prod_{i=1}^m \big( 1 + \gamma\, \lambda_i \big)^{\frac12} \right] \nonumber\\ &\sim 2^{-n}\, m^\frac12 \left( \frac{\gamma\, n}4 \right)^{\frac m2} \ , \nonumber \hspace{2cm} (12) \end{align} which together with $(10)$ would immediately imply that $P$ has the lowest possible value $P \sim 2^{-n}$ for any $m$. However, we know that at least for small $m$ the last expression in $(12)$ must be wrong, since the $k=0$ term of the sum is always equal to $1$ and so that the whole sum can never become smaller than $1$. Furthermore, $(12)$ can of course only be a reasonable approximation if many terms in the sum make some substantial contribution, i.e., if the sum itself is much larger than $1$.
On the basis of the above arguments I therefore believe that the following holds, asymtotically for large $n$: $$\sum_{k\, \in\, \mathbb Z^n} \exp-4\pi(\cdots) \sim \max\left\{ 1,\ 2^{-n}\, m^\frac12 \left( \frac{\gamma\, n}4 \right)^{\frac m2} \right\} \ . \hspace{2cm} (13)$$ We can now combine $(13)$ with $(10)$. Asymptotically, the factor $m^\frac12$ in $(13)$ is irrelevant and $2^{-n}\, m^\frac12 \left( \frac{\gamma\, n}4 \right)^{\frac m2} \geq 1$ is equivalent to $m \geq \frac{2n}{\log_2 ( \gamma n/4)}$, and so we obtain: $$P \sim \begin{cases} \quad 2^{-n} \ , \quad m > \frac{2n}{\log_2 ( \gamma n/4)} \\ \left( \frac{\gamma\, n}4 \right)^{-\frac m2} \ , \quad m \leq \frac{2n}{\log_2 ( \gamma n/4)} \end{cases} \ . \hspace{2cm} (14)$$ In particular, if we choose $m$ to be $$m = \beta \frac{2n}{\log_2 ( \gamma\, n/4)} \ , \hspace{2cm} (15)$$ with some constant $\beta \in ]0,1]$ of our choice, then we obtain $$P \sim \left( \frac{\gamma\, n}4 \right)^{-\beta \frac{n}{\log_2 ( \gamma n/4)}} = 2^{-\beta n} \ . \hspace{2cm} (16)$$ Furthermore, $(15)$ implies that $m \sim \beta \frac{2n}{\log_2 n}$ asymptotically, so the assumptions in Conjecture 1* (or in the original Conjecture 1) correspond to $\beta=\frac12$. In that case, $(16)$ seems to lead to the prediction $P(Mw=0) \sim 2^{-\frac n2}$, for any "typical" random matrix $M \in \{0,1\}^{m \times n}$, whether of a Toeplitz form or not. This is a stronger statement (exponent larger by a factor 2) than Conjecture 1.

Finally, as already indicated in the beginning of this answer, I believe that the presented argument also has a bearing on Conjecture 2. Namely, from the first line of $(14)$ (or by setting $\beta = 1$ in $(15)$ and $(16)$) we see that it predicts that if $m \geq \frac{2n}{\log_2 n}$ then $P(Mw=0) \sim 2^{-n}$ asymptotically. As far as I understand, this in turn would mean that the set of columns of a randomly chosen matrix $M \in \{0,1\}^{m \times n}$, whether of a Toeplitz form or not, is "weakly dissociated" in the sense that the fraction of all sub-sets whose sum is not distinct from all others tends to zero in the limit $n \to \infty$.