Welcome to MathOverflow

Question

3

NOTE: Slightly more general question follows my specific one at the top

For $1 \leq i,j \leq n$, let $e_{ij}$ be the vector in $\mathbb{R}^{n^{2}}$ with a 1 in entry $(n-1)i + j$, and 0's everywhere else. Then let $v[a,b,c,d] = e_{ac} + e_{bd} - e_{ad} - e_{bc}$, for $1 \leq a < b \leq n$, $1 \leq c < d \leq n$.

My (slightly fuzzy) question: Pick $M$ distinct vectors of the form $v[a,b,c,d]$ for some valid $a,b,c,d$, say uniformly at random. Call them $v_{1}, \ldots, v_{m}$ How large does $M$ have to be in to allow you to write

$v[1,2,1,2] = \sum_{m = 1}^{M} c_{m} v_{m}$

for $c_{m}$ 'small' (e.g. -10 \leq c_{m} \leq 10) with 'high probability'? Of course, if $M \sim n^{4}$, it will be possible, since $v[1,2,1,2]$ itself eventually shows up. But we get a basis around $M \sim n^{2} \log(n)$, and I would like to know if this becomes possible around the time that a basis appears.

MORE GENERALLY: Is there some theory of linear relationships or bases with small coefficients?

flag	asked Dec 12 2011 at 20:10 QAMS 83●3

It seems that there's some kind of random hypergraph model underlying your setup with vertices on the points of a square grid and $M$ random "rectangles" forming the edges. Could you say a word or two about where this question comes from? – jc Dec 13 2011 at 0:54

1

The hypergraph picture seems right, though the problem originally posed doesn't have one. This process comes from bounding the probability of a large deviation for a martingale; it turns out that the typical error size is at most $O(M + \log(\sum_{i} c_{i}^{2}))$ with high probability. The original problem involves perturbing an $n$ by $n$ matrix with these $v[a,b,c,d]$ terms, which really is where they come from; this is an effort to understand some cancellation that might happen. The perturbations are very dependent, and this was the most promising estimate I could find based on simulation. – QAMS Dec 13 2011 at 3:46

Linear relations with small coefficients

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.