Description
Combinatorics Seminar
Title: Lift of Reed-Solomon code with an application to Nikodym sets
Speaker: S. Venkitesh (IITB)
Date and Time: Feb 14, 2018, 2PM
Venue: Ramanujan Hall, Dept. of Mathematics
Abstract:
We will work over the finite field F_q, q = p^k. The Reed-Solomon code
with parameters (q,d), denoted as RS(q,d), is the linear space of all
polynomial functions from F_q to F_q with degree atmost d. The
Reed-Muller code with parameters (q,m,d), denoted as RM(q,m,d), is the
m-variable analog of RS(q,d), defined to be the linear space of all
polynomial functions from F_q^m to F_q with total degree atmost d.
A nonempty set N in F_q^m is called a Nikodym set if for every point p
in F_q^m, there is a line L passing through p such that all points on
L, except possibly p, are contained in N. Using the polynomial method
and the code RM(q,m,q-2), we can prove the lower bound |N| >= q^m /
m!. We will outline this proof.
We will then define a new linear code called the m-lift of RS(q,d),
denoted as L_m(RS(q,d)), and show that RM(q,m,d) is a proper subspace
of L_m(RS(q,d)). We will use this fact crucially, in a proof very
similar to the earlier one, to obtain the improved lower bound |N| >=
(1 - o(1)) * q^m, when we fix p and allow q to tend to infinity. This
result is due to Guo, Kopparty and Sudan.