[This post, which is based on an ongoing discussion with Alex Russell and Ravi Sundaram, contains some unpublished results.]
Currently, we are asking whether all submatrices of the order- Vandermonde matrix over a finite extension of are invertible where is prime. The answer is “no” in general: there are examples of fields where the Vandermonde matrix has a singular submatrix.
We can ask an easier(?) question, though. What happens if we randomly sample a set of columns and look into submatrices formed by a subset of the sampled columns. With a touch of beautiful insight, Professor Russell has connected Szemeredi’s theorem on arithmetic progressions with this question.
Let denote an arithmetic progression of length $latek k$. Let for .
The Szemerédi theorem says, any “sufficiently dense” subset contains infinitely many for all . A finitary version says: Fix your favourite . Then, there exists a natural such that if you look any subset of size at least , you will find an . Yet another version says:
Szemerédi’s Theorem. The size of the largest subset without an cannot be too large; in particular, it is .
Recall that a function is if it grows too slow compared to , so that .
Continue reading “Vandermonde Submatrices and Arithmetic Progressions”
To this day, no method of finding a generator of is known to be more efficient than essentially trying 2, then 3, and so on. Who cares? Well, the difficulty of breaking a certain public key cryptosystem (due to El Gamal) depends on the difficulty of working with generators of . — Keith Conrad
An th root of unity in a finite field is an element satisfying , where is an integer. If is the smallest positive integer with this property, is called a primitive th root of unity. If is a primitive th root of unity, then all elements in the set are also roots of unity. Actually, the set form a cyclic group of order under multiplication, with generator .
Problem: Suppose you are given a finite field of degree , and you are promised that there indeed exists a primitive th root of unity for prime. Find , and in particular, produce a C++code that finds it.
In what follows, we talk about how to find such a root and provide my C++ code; the code uses the awesome NTL library.
Continue reading “Finding a Primitive p-th Root of Unity in a Finite Field, with C++ Code”
In this post, I will discuss my own understanding of the spectral sparsification paper by Daniel Spielman and Nikhil Srivastava (STOC 2008). I will assume the following:
- The reader is a beginner, like me, and have already glanced through the Spielman-Srivastava paper (from now on, the SS paper).
- The reader has, like me, a basic understanding of spectral sparsification and associated concepts of matrix analysis. I will assume that she has read and understood the Section 2 (Preliminaries) of the SS paper.
- The reader holds a copy of the SS paper while reading my post.
First, I will mention the main theorems (actually, I will mention only what they “roughly” say).
Continue reading “Spectral Sparsification by Spielman and Srivastava: How They Connected the Dots”