23
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Boris Bukh May 19 '15 at 18:15
  • $\begingroup$ @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. $\endgroup$ – Raphael May 19 '15 at 18:32
5
+100
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.