Generalized Vandermonde Determinants over the Chebyshev Basis

It is a well known fact that the generalized Vandermonde determinant can be expressed as the product of the standard Vandermonde determinant and a polynomial with nonnegative integer coefficients. In this paper we generalize this result to Vandermonde determinants over the Chebyshev basis. We apply this result to prove that the number of real roots in _U`baNced of a real polynomial is bounded by the number of its nonvanishing coefficients (sparsity) when represented over the Chebyshev basis. This bound on the number of real roots is used to prove finiteness of the Vapnik-Chervonenkis dimension (and thereby uniform learnability) of the class of polynomials of bounded sparsity over the Chebyshev basis.