Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Everything is in $\mathbb{Z}$. Let $v_1 < v_2 < ... < v_n = k$, and $v_1 = 1$ for $k >> n$. Let $ P = \Pi_{i < j} (v_j - v_i)$. How can I show that $P \le k^{n^2}$?

There are $n + (n-1) + ... + 1 = \frac{n(n+1)}{2}$ terms in the product. Starting from $v_n - v_{n-1} = 1$, etc. Clearly, $P = 1(1*2)(1*2*3) ...(k-1)! = \Pi_{i=1}^{i=k-1} i!$. But I'm not sure about this superfactorial(?).

Also, I noticed that the product $P$ is very similar to the determinant of a Vandermonde matrix.

share|improve this question
    
Actually there are C(n,2) = n(n-1)/2 terms in the product. –  Mitch Schwartz Dec 23 '10 at 8:11
1  
Also, please check for other typos. In the question title you have 1 <= v_1 and (v_i - v_j), but in the question body you have 1 = v_1 (subject to k >> n?) and (v_j - v_i). –  Mitch Schwartz Dec 23 '10 at 8:17
    
I think you should construct the matrix and work from the definition of the determinant. Say you estimate the value of the determinant by its absolute value, and then use the triangle rule and the definition of the determinant and then estimate each $v_i$ by $k$. Might work :) –  Alexei Averchenko Dec 23 '10 at 13:24
    
This problem has been moved to a higher level. See math.stackexchange.com/questions/15366 –  Christian Blatter Dec 24 '10 at 13:27
add comment

1 Answer 1

up vote 1 down vote accepted

First note that there are a total of $1 + 2 + \cdots + (n-1)$ terms i.e. a total of $\frac{n(n-1)}{2}$ terms.

And $\forall n \in \mathbb{N}$, $\frac{n(n-1)}{2} < n^2$.

And $|v_i - v_j| < k$, $\forall i,j$ since $v_{i} \in [1,k]$.

Hence, we get $\displaystyle \prod_{i<j} |v_i - v_j| < k^{\frac{n(n-1)}{2}} < k^{n^2}$.

The last inequality follows from the fact that $\frac{n(n-1)}{2} < n^2$ and $k>1$

share|improve this answer
    
This suggests that a far tighter bound is available. Getting to $$(k-1)^{\frac{n(n-1)}{2}}$$ falls out of your argument, but that still doesn't use that most of the v's are between 1 and k. –  Ross Millikan Dec 23 '10 at 15:30
    
@Ross: True. You could push in fact push the bound further by noting that $j \leq v_j \leq k-(n-j)$ and hence $|v_i - v_j| \leq \min(|k-(n-i) - j|,|k-(n-j) - i|)$ or something similar. –  user17762 Dec 23 '10 at 15:37
    
I tried the naive thing of equally distributing the v's and calculated the specific result, but the product is higher if you slide them toward the end (just by experiment with n=5). –  Ross Millikan Dec 23 '10 at 18:14
add comment

Your Answer

 
discard

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