Published On Nov 6, 2023
In this lecture, we discuss fully reducible lacunary polynomials over finite fields. Fully reducible means that the polynomial splits into a product of linear factors, whereas lacunary implies that the polynomial has a long run of zeros in its coefficients. Rédei used such polynomials to prove several new results in finite geometry [Red70]; these ideas and further refinements are instances of thepolynomial method. For example, Blokhuis used Rédei polynomials to prove the celebrated result that the size of a non-trivial blocking set in PG(2, p) is at least 3(p+1)/2 when p is a prime [Blo94]. We follow the exposition in Szönyi's excellent article [Szo99] to discuss an application of Rédei polynomials in the theory of directions. In particular, we derive a lower bound on the number of directions (also called "slopes") determined by a finite point set in a finite projective plane. Assuming that the point set arises from a graph of a function y=f(x), the problem is about estimating the number of different values difference quotient (f(x)-f(y))/(x-y) takes as x, y range over elements of a finite field F_q. Fortunately, there is a genuine connection between the theory of directions and maximum cliques in Paley graphs.
https://mca.nsu.ru/lectAGT/