MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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? – j.c. Dec 13 '11 at 0:54
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 '11 at 3:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.