Addition Theorems in Fp via the Polynomial Method

MaRDI QIDQ6283443zbMATH OpenFDO

Authors Éric Balandraud

Publication date 21 February 2017

Abstract: In this article, we use the Combinatorial Nullstellensatz to give new proofs of the Cauchy-Davenport, the Dias da Silva-Hamidoune and to generalize a previous addition theorem of the author. Precisely, this last result proves that for a set A $subset$ Fp such that A $cap$ (--A) = $emptyset$ the cardinality of the set of subsums of at least $alpha$ pairwise distinct elements of A is: |$Sigma$$alpha$(A)| $ge$ min (p, |A|(|A| + 1)/2 -- $alpha$($alpha$ + 1)/2 + 1) , the only cases previously known were $alpha$ $in$ {0, 1}. The Combinatorial Nullstellensatz is used, for the first time, in a direct and in a reverse way. The direct (and usual) way states that if some coefficient of a polynomial is non zero then there is a solution or a contradiction. The reverse way relies on the coefficient formula (equivalent to the Combinatorial Nullstellensatz). This formula gives an expression for the coefficient as a sum over any cartesian product. For these three addition theorems, some arithmetical progressions (that reach the bounds) will allow to consider cartesian products such that the coefficient formula is a sum all of whose terms are zero but exactly one. Thus we can conclude the proofs without computing the appropriate coefficients.

This page was built for publication: Addition Theorems in Fp via the Polynomial Method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6283443)