A nullstellensatz for sequences over F_p

Abstract : Let p be a prime and let A=(a_1,...,a_l) be a sequence of nonzero elements in F_p. In this paper, we study the set of all 0-1 solutions to the equation a_1 x_1 + ... + a_l x_l = 0. We prove that whenever l >= p, this set actually characterizes A up to a nonzero multiplicative constant, which is no longer true for l < p. The critical case l=p is of particular interest. In this context, we prove that whenever l=p and A is nonconstant, the above equation has at least p-1 minimal 0-1 solutions, thus refining a theorem of Olson. The subcritical case l=p-1 is studied in detail also. Our approach is algebraic in nature and relies on the Combinatorial Nullstellensatz as well as on a Vosper type theorem.
Type de document :
Article dans une revue
Combinatorica, Springer Verlag, 2014, 34 (6), pp.657-688. 〈10.1007/s00493-011-2961-4〉
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

http://hal.upmc.fr/hal-00684502
Contributeur : Benjamin Girard <>
Soumis le : dimanche 29 juin 2014 - 11:32:20
Dernière modification le : mardi 3 octobre 2017 - 19:57:48
Document(s) archivé(s) le : lundi 29 septembre 2014 - 10:40:36

Fichiers

Nullstellensatz_bis.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INSMI | UPMC | IMJ | USPC

Citation

Eric Balandraud, Benjamin Girard. A nullstellensatz for sequences over F_p. Combinatorica, Springer Verlag, 2014, 34 (6), pp.657-688. 〈10.1007/s00493-011-2961-4〉. 〈hal-00684502v2〉

Partager

Métriques

Consultations de la notice

417

Téléchargements de fichiers

67