Discrete Mathematics & Theoretical Computer Science, Vol 13, No 4

Font Size:  Small  Medium  Large

On the minimal distance of a polynomial code

Péter Pál Pach, Csaba Szabó


For a polynomial f(x)∈ℤ2[x] it is natural to consider the near-ring code generated by the polynomials fˆx,fˆx2, … , fˆxk as a vectorspace. It is a 19 year old conjecture of Günter Pilz that for the polynomial f(x)= xn+xn-1+⋯+x the minimal distance of this code is n. The conjecture is equivalent to the following purely number theoretical problem. Let m={1,2, … ,m} and A⊂ℕ be an arbitrary finite subset of ℕ. Show that the number of products that occur odd many times in n·A is at least n. Pilz also formulated the conjecture for the special case when A=k. We show that for A=k the conjecture holds and that the minimal distance of the code is at least n/(log n)0.223. While proving the case A=k we use different number theoretical methods depending on the size of k (respect to n). Furthermore, we apply several estimates on the distribution of primes.

Full Text: PDF PostScript