Search

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.

We solve two related extremal problems in the theory of permutations. A set $Q$ of permutations of the integers 1 to $n$ is inversion-complete (resp., pair-complete) if for every inversion $(j,i)$, where $1 \le i \textless{} j \le n$, (resp., for every pair $(i,j)$, where $i\not= j$) there exists a permutation in~$Q$ where $j$ is before~$i$. It is minimally inversion-complete if in addition no proper subset of~$Q$ is inversion-complete; and similarly for pair-completeness. The problems we consider are to determine the maximum cardinality of a minimal inversion-complete set of permutations, and that of a minimal pair-complete set of permutations. The latter problem arises in the determination of the Carath\'eodory numbers for certain abstract convexity structures on the $(n-1)$-dimensional real and integer vector spaces. Using Mantel's Theorem on the maximum number of edges in a triangle-free graph, we determine these two maximum cardinalities and we present a complete description of the optimal sets of permutations for each problem. Perhaps surprisingly (since there are twice as many pairs to cover as inversions), these two maximum cardinalities coincide whenever $n \ge 4$.

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., Comment: 23 pages

Denoting by Sigma(S) the set of subset sums of a subset S of a finite abelian group G, we prove that |Sigma(S)| >= |S|(|S|+2)/4-1 whenever S is symmetric, |G| is odd and Sigma(S) is aperiodic. Up to an additive constant of 2 this result is best possible, and we obtain the stronger (exact best possible) bound in almost all cases. We prove similar results in the case |G| is even. Our proof requires us to extend a theorem of Olson on the number of subset sums of anti-symmetric subsets S from the case of Z_p to the case of a general finite abelian group. To do so, we adapt Olson's method using a generalisation of Vosper's Theorem proved by Hamidoune and Plagne., Comment: 22 pages, submitted