0
$\begingroup$

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.

  • 0
    Actually there are C(n,2) = n(n-1)/2 terms in the product.2010-12-23
  • 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).2010-12-23
  • 0
    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 :)2010-12-23
  • 0
    This problem has been moved to a higher level. See http://math.stackexchange.com/questions/15366/2010-12-24

1 Answers 1

2

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

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

  • 0
    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.2010-12-23
  • 0
    @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.2010-12-23
  • 0
    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).2010-12-23