Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $V = \Pi_{1 \le i < j \le n} (a_j - a_i)$ be the determinant of the Vandermonde matrix where $1 = a_1 < \cdots < a_n = d$ (with $d >> n$). What is the smallest prime $p$ (or the lower bound) such that $p \nmid V$? Preferably $p < n$.

share|improve this question
3  
I don't understand the question. Do you have a particular choice of a_i in mind? –  Qiaochu Yuan Jan 5 '11 at 23:51
1  
I still don't understand the question. Do you want the smallest prime which does not have to divide V? –  Qiaochu Yuan Jan 6 '11 at 0:05
    
Yes. Consider the primes in the range [2 .. d]. Some of them will divide V, other won't. I want the smallest prime p that does not divide V. –  M.S. Jan 6 '11 at 0:07
2  
@M.S.: you do not specify what $a_i$ are. Integers? What are the quantifiers? Should we fix $a_i$, then find $p$ or should we find a $p$ that works for every collection of $a_i$. The question as stated does not make sense. I voted to close. –  Mark Sapir Jan 6 '11 at 1:11
add comment

closed as not a real question by Gjergji Zaimi, Andres Caicedo, Mark Sapir, Felipe Voloch, Qiaochu Yuan Jan 6 '11 at 12:33

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

4 Answers

up vote 4 down vote accepted

Not really clear about what is being asked. If the $a_i$ are all divisible by the same p (choose one) then this p does divide V. Suppose the $a_i$ are 1 ... n, then if $p < n$ then then with $a_i=1$ there is an $a_j$ with $a_j-a_i=p$. If $p \ge n$ then $p \nmid V$. If $p < n$ then in any n numbers there are two with the same residue mod p (pigeonhole) so $p \mid V$. Is a more general context intended?

share|improve this answer
    
I'm looking for a prime $p < n$ such that $p \nmid V$. It is the case that a_1 = 1 (actually, 1 = a_1 < .. < a_n = d and d >> n). –  M.S. Jan 6 '11 at 0:04
    
Under new conditions $d >> n$ it seems easy to me to start with 1 then $a_i$ = $1 + i2^m$ for arbitrarily large (constant) m. The difference from 1 ... n is that differences all have a high power of 2 to add as a factor of the determinant. d can be as large as desired and the prime factors remain lower than n. –  Mark Bennet Jan 6 '11 at 0:42
    
Sorry - last comment could allow n=p as a factor. –  Mark Bennet Jan 6 '11 at 0:46
    
It was my bedtime - use (i-1) in place of i as a factor –  Mark Bennet Jan 6 '11 at 8:29
add comment

To extend Mark Bennet's answer, one could have a_2 = a_1 + P_m, the mth primorial, giving that V is a multiple of P_m. So without parameters, there is no bound. If you want something in terms of V or the a_i, you might start with the idea that such a prime need be not much larger than the largest of (a_i - a_j), and is likely to be smaller.

Gerhard "Ask Me About System Design" Paseman, 2011.01.05

share|improve this answer
1  
In tha above, I assume V is nonzero. Gerhard "Ask Me About System Design" Paseman, 2011.01.05 –  Gerhard Paseman Jan 5 '11 at 23:57
    
Now that I see the conditions involving d, I'd say Mark's answer is the best you will get, namely n is near the lower bound for nonzero V. It is easy to construct examples which realize this bound. Gerhard "Ask Me About System Design" Paseman, 2011.01.05 –  Gerhard Paseman Jan 6 '11 at 0:05
1  
It is also easy to extend the above idea: let a_{i+1} = a_i + Q_i, where Q_i is a product of small primes with size of Q_i comparable to P_m. Many of the Q_i will sum to form multiples of larger primes. All that can be guaranteed is again from Mark's answer, that n <= p <= a_n + epsilon, which is likely less than d. Gerhard "Ask Me About System Design" Paseman, 2011.01.05 –  Gerhard Paseman Jan 6 '11 at 0:19
add comment

If $p<n$ then it must be that $p \mid V$. However if $p \ge n$ then it can be arranged that $p \nmid V$. If you set $a_i=2^m(i-1)+1$ then no prime greater than $n-1$ divides $V$. You could replace $2^m$ by $(n-1)!$ or anything else with all divisors less than $n$.

share|improve this answer
add comment

Considered as a polynomial in the $a_i$'s, $V$ is never divisible by p, since the monomial $a_1^{n-1}a_2^{n-2}\cdots a_{n-1}$ always appears with coefficient 1. However, by the magic of Fermat's little theorem, it can be that all of its values are divisible by p, even if the polynomial itself isn't. As Mark points out, this happens if and only if $p< n$.

share|improve this answer
    
Thanks for the addendum, Andres. Not sure what happened there. –  Ben Webster Jan 6 '11 at 3:44
add comment

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