ADDITION THEOREMS IN Fp VIA THE POLYNOMIAL METHODReport as inadecuate




ADDITION THEOREMS IN Fp VIA THE POLYNOMIAL METHOD - Download this document for free, or read online. Document in PDF available to download.

1 IMJ - Institut de Mathématiques de Jussieu

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 ⊂ Fp such that A ∩ −A = ∅ the cardinality of the set of subsums of at least α pairwise distinct elements of A is: |ΣαA| ≥ min p, |A||A| + 1-2 − αα + 1-2 + 1 , the only cases previously known were α ∈ {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.





Author: Eric Balandraud -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents