N integers

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

N integers

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: http://mathworld.wolfram.com/VandermondeDeterminant.html

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2607 posts

#1 h Oct 18, 2005, 5:29 PM • 2 Y

Y by Adventure10, Mango247

If $a_1,a_2,\ldots,a_n \in \mathbb{Z}$ then $\left. \prod_{i=1}^n (i-1)! \right| \prod_{i>j} (a_i-a_j) .$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

393 posts

tµtµ

#2 h Oct 18, 2005, 8:29 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

The source and the reference to Vandermonde is a precious clue !

Here is a, not elementary proof with heavy use of linear algebra, which, I think, works :

Let's write $X^i= \sum a_j^i L_j$ where $L_j$ is Lagrange interpolation polynomial such as $L_j(a_j)=1$ and $L_j(a_i)=0$

Then by Vandermonde, $\prod_{i>j} (a_i-a_j)$ is the determinant of the matrix from basis $X^i$ to $L_i$ .

If $M_j$ is Lagrange interpolation polynomial such as $L_j(j)=1$ and $L_j(i)=0$ , then $\prod_{i=1}^n (i-1)!$ is the determinant from basis $M_i$ to $X^i$ .

By composition, it suffices to prove that the matrix from $L_i$ to $M_i$ is an integer, i.e. if $M_i = \sum m_{ij} L_j$ then $det(m_{ij}) \in Z$
We have $m_ij = M_i(a_j)$ , it is a classical exercice to prove that if $P$ is a polynomial of degree $n$ such an $P(n)$ is an integer for $0, ..., n$ then $P(n)$ is an integer for all $n$ . Conclusion follows.

Hope it's correct and not too obscur

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2607 posts

#3 h Oct 18, 2005, 8:42 PM • 2 Y

Y by Adventure10, Mango247

tµtµ wrote:

Let's write $X^i= \sum a_j^i L_j$ where $L_j$ is Lagrange interpolation polynomial such as $L_j(a_j)=1$ and $L_j(a_i)=0$

Then by Vandermonde, $\prod_{i>j} (a_i-a_j)$ is the determinant of the matrix from basis $X^i$ to $L_i$ .

I don't understand how you define the $X^i$ 's... can you give an example for a special case (n=4 or smth like that)

And another thing: what does a matrix from a basis ... to ... mean?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

749 posts

#4 h Oct 19, 2005, 3:01 AM • 1 Y

Y by Adventure10

Consider prime factorization of $\prod_{i=1}^n (i-1)!$ . Prime p must have exponent $\displaystyle \sum_{k=1}^{n-1} \left \lfloor \frac{k}{p} \right \rfloor$ .

In product $\prod_{i>j} (a_i - a_j)$ , lets count how many factors p there are. If there are $b_i$ $a_i$ 's modulo p, then there are $\sum \frac{b_i(b_i-1)}{2}$ factors p. Obviously $\sum b_i = n$ . So there are $\frac{-n + \sum b_i^2}{2}$ factors p.

So it remains to prove $\frac{-n + \sum^p b_i^2}{2} \ge \sum_{k=1}^{n-1} \left \lfloor \frac{k}{p} \right \rfloor$

By induction on n. Extreme values are easy; else adding one to n adds $\lfloor \frac{n}{p} \rfloor$ to the RHS, but the minimum of the LHS increases by this plus one.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2607 posts

#5 h Oct 19, 2005, 8:20 AM • 1 Y

Y by Adventure10

Singular wrote:

Prime p must have exponent $\displaystyle \sum_{k=1}^{n-1} \left \lfloor \frac{k}{p} \right \rfloor$ .

Are you sure this is true?

I knew that power of a prime $p$ in $n!$ is $\displaystyle \sum_{i \geq 1} \left\lfloor \frac{n}{p^i} \right\rfloor$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6555 posts

#6 h Jun 22, 2007, 11:45 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

perfect_radio wrote:

I don't understand how you define the $X^{i}$ 's... can you give an example for a special case (n=4 or smth like that)

And another thing: what does a matrix from a basis ... to ... mean?

I just noticed this thread. Are the questions still to be answered?

First, some corrections to tµtµ's post (apparently he worked with $n+1$ integers $x_{0}$ , $x_{1}$ , ..., $x_{n}$ instead of the $n$ integers $x_{1}$ , $x_{2}$ , ..., $x_{n}$ and thus his notation doesn't quite fit with the notation of the problem):

tµtµ, corrected wrote:

The source and the reference to Vandermonde is a precious clue !

Here is a, not elementary proof with heavy use of linear algebra, which, I think, works :

Let's write $X^{i-1}= \sum_{j=1}^{n}a_{j}^{i-1}L_{j}$ where $L_{j}$ is Lagrange interpolation polynomial such as $L_{j}(a_{j})=1$ and $L_{j}(a_{i})=0$ for $i\neq j$ .

Then by Vandermonde, $\prod_{i>j}(a_{i}-a_{j})$ is the determinant of the transfer matrix from the basis $\left(1,X,X^{2},...,X^{n-1}\right)$ to the basis $\left(L_{1},L_{2},...,L_{n}\right)$ .

If $M_{j}$ is Lagrange interpolation polynomial such as $M_{j}(j)=1$ and $M_{j}(i)=0$ for $i\neq j$ , then $\prod_{i=1}^{n}(i-1)!$ is the determinant of the transfer matrix from the basis $\left(1,X,X^{2},...,X^{n-1}\right)$ to the basis $\left(M_{1},M_{2},...,M_{n}\right)$ .

By composition, it suffices to prove that the determinant of the transfer matrix from the basis $\left(M_{1},M_{2},...,M_{n}\right)$ to the basis $\left(L_{1},L_{2},...,L_{n}\right)$ is an integer, i.e. if $M_{i}= \sum_{j=1}^{n}m_{ij}L_{j}$ then $\det (m_{ij}) \in \mathbb{Z}$ .

But in fact, even all $m_{ij}$ are integers, since we have $m_{ij}= M_{i}(a_{j})$ , and this is integer since it is a classical exercise to prove that if $P$ is a polynomial of degree $\leq n-1$ such that $P(k)$ is an integer for all $k\in\left\{1, 2, ..., n\right\}$ then $P(k)$ is an integer for all $k\in\mathbb{Z}$ . Conclusion follows.

In fact, tµtµ works in the $n$ -dimensional $\mathbb{Q}$ -vector space of all polynomials of one variable $X$ over $\mathbb{Q}$ whose degree is $\leq n-1$ . Therefore, $\left(1,X,X^{2},...,X^{n-1}\right)$ is a basis of this vector space.

If $\left(a_{1},a_{2},...,a_{n}\right)$ and $\left(b_{1},b_{2},...,b_{n}\right)$ are two bases of a vector space, then the transfer matrix from the basis $\left(a_{1},a_{2},...,a_{n}\right)$ to the basis $\left(b_{1},b_{2},...,b_{n}\right)$ means (at least in tµtµ's notation) the matrix $\left(t_{ij}\right)_{1\leq i,j\leq n}$ satisfying $a_{i}=\sum_{j=1}^{n}t_{ij}b_{j}$ for every $i\in\left\{1,2,...,n\right\}$ .

The Lagrange interpolation polynomials for $n$ distinct (yes, they must be distinct) elements $x_{1}$ , $x_{2}$ , ..., $x_{n}$ of a field $K$ are $n$ special polynomials $N_{1}$ , $N_{2}$ , ..., $N_{n}$ of degree $n-1$ over $K$ which are defined as follows:

$N_{i}\left(X\right)=\prod_{1\leq j\leq n;\ j\neq i}\frac{X-x_{j}}{x_{i}-x_{j}}$ for every $i\in\left\{1,2,...,n\right\}$ .

They satisfy $N_{i}\left(x_{i}\right)=1$ for every $i\in\left\{1,2,...,n\right\}$ , and $N_{i}\left(x_{j}\right)=0$ for every $i,j\in\left\{1,2,...,n\right\}$ such that $i\neq j$ .

The name-giving property of these Lagrange interpolation polynomials is the following one: For every polynomial $S$ of degree $\leq n-1$ , we have $S=\sum_{i=1}^{n}S\left(x_{i}\right)N_{i}$ .

In tµtµ's solution,
- the polynomials $L_{1}$ , $L_{2}$ , ..., $L_{n}$ are defined as the the Lagrange interpolation polynomials for the elements $a_{1}$ , $a_{2}$ , ..., $a_{n}$ of the field $\mathbb{Q}$ ;
- the polynomials $M_{1}$ , $M_{2}$ , ..., $M_{n}$ are defined as the the Lagrange interpolation polynomials for the elements $1$ , $2$ , ..., $n$ of the field $\mathbb{Q}$ .

I hope I was able to clear up some things...

Darij

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a