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.
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

Contributor : Benjamin Girard <>
Submitted on : Sunday, June 29, 2014 - 11:32:20 AM
Last modification on : Sunday, March 31, 2019 - 1:37:13 AM
Long-term archiving on : Monday, September 29, 2014 - 10:40:36 AM


Files produced by the author(s)



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⟩



Record views


Files downloads