0
$\begingroup$

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$.

$\endgroup$
4
  • 3
    $\begingroup$ I don't understand the question. Do you have a particular choice of a_i in mind? $\endgroup$ Jan 5, 2011 at 23:51
  • 1
    $\begingroup$ I still don't understand the question. Do you want the smallest prime which does not have to divide V? $\endgroup$ Jan 6, 2011 at 0:05
  • $\begingroup$ 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. $\endgroup$
    – M.S.
    Jan 6, 2011 at 0:07
  • 2
    $\begingroup$ @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. $\endgroup$
    – user6976
    Jan 6, 2011 at 1:11

4 Answers 4

4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – M.S.
    Jan 6, 2011 at 0:04
  • $\begingroup$ 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. $\endgroup$ Jan 6, 2011 at 0:42
  • $\begingroup$ Sorry - last comment could allow n=p as a factor. $\endgroup$ Jan 6, 2011 at 0:46
  • $\begingroup$ It was my bedtime - use (i-1) in place of i as a factor $\endgroup$ Jan 6, 2011 at 8:29
1
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ In tha above, I assume V is nonzero. Gerhard "Ask Me About System Design" Paseman, 2011.01.05 $\endgroup$ Jan 5, 2011 at 23:57
  • $\begingroup$ 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 $\endgroup$ Jan 6, 2011 at 0:05
  • 1
    $\begingroup$ 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 $\endgroup$ Jan 6, 2011 at 0:19
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thanks for the addendum, Andres. Not sure what happened there. $\endgroup$
    – Ben Webster
    Jan 6, 2011 at 3:44

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