Antoine Bertout
email: antoine.bertout@lifl.fr

Julien Forget
email: julien.forget@lifl.fr

Richard Olejnik
email: richard.olejnik@lifl.fr

A heuristic to minimize the cardinality of a real-time task set by automated task clustering

We propose in this paper a method to automatically map functionalities (blocks of code corresponding to highlevel features) with real-time constraints to tasks (or threads). We aim at reducing the number of tasks functions are mapped to, while preserving the schedulability of the initial system. We consider independent tasks running on a single processor. Our approach has been applied with fixed-task or fixed-job priorities assigned in a Deadline Monotonic (DM) or a Earliest Deadline First (EDF) manner.

Introduction

Our work falls within the scope of real-time systems programming. Usually, real-time system developers design a system as a set of functionalities with real-time constraints. A functionality is here considered a block of code corresponding to a high-level feature. Implementing such systems requires to map each functionality to a real-time task (thread). On the one hand, the number of those functionalities is quite high. For instance, it ranges from 500 to 1000 in the flight control system of an aircraft or of a space vehicle [START_REF] Boniol | A framework for distributing real-time functions[END_REF][START_REF] Forget | A Synchronous Language for Critical Embedded Systems with Multiple Real-Time Constraints[END_REF]. On the other hand, a large number of threads implies a significant time overhead in context switching [START_REF] Scheickl | Automotive real time development using a timing-augmented AUTOSAR specification[END_REF][START_REF] Lee | The problem with threads[END_REF] and an important memory footprint (e.g. task control block, size of the stack, etc.). Thus, the number of tasks supported by embedded real-time operating systems is limited, rarely over one hundred, and developers cannot map each functionality to a different task. This mapping is currently mainly performed manually and, given the number of functionalities to process, this work can be tedious and error-prone.

In our work, we address this question from the scheduling point of view. We model a system as a set of tasks with real-time constraints, where each task is characterized by an execution time, an activation period and a deadline, in the same way as Liu and Layland's task model [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. With respect to this model, functionalities can simply be considered as finer grain tasks, while threads are just coarser tasks. Thus, mapping functionalities to tasks amounts to gathering several tasks into a single one, which we call task clustering. Clustering several tasks implies to choose only one deadline for the cluster, which effectively reduces some task deadlines. As a consequence, we have to check that the system schedulability is preserved after the clustering.

Related Work

In the literature, task clustering is most often studied in the context of distributed systems implementation, where it consists in distributing a set of tasks over a set of computing nodes (processors or cores). This is different from our context, because in the distributed systems context a cluster corresponds to the set of tasks allocated to the same computing resource. For instance, [START_REF] Ramamritham | Allocation and scheduling of precedence-related periodic tasks[END_REF][START_REF] Ahmadinia | Temporal task clustering for online placement on reconfigurable hardware[END_REF] aim at minimizing communications by clustering tasks that communicate a lot. The approaches in [START_REF] Palis | Task clustering and scheduling for distributed memory parallel architectures. Parallel and Distributed Systems[END_REF][START_REF] Guodong | Task clustering and scheduling to multiprocessors with duplication[END_REF] cluster tasks based on communications, in order to reduce the system makespan. The number of tasks of the resulting implementation is however not reduced.

Functionality to task mapping is known as runnableto-task mapping and is identified as a step of the de-velopment process in the augmented real-time specification for AUTomotive Open System ARchitecture (AU-TOSAR) [START_REF]RTE Standard Specifications[END_REF]. This document and [START_REF] Scheickl | Automotive real time development using a timing-augmented AUTOSAR specification[END_REF] also provide guidelines defining under which conditions runnables can be mapped to the same tasks. Authors in [START_REF] Zhang | Optimization issues in mapping AUTOSAR components to distributed multithreaded implementations[END_REF] propose an automated mapping in that context, but that work is restricted to functionalities that have deadlines equal to their periods. In [START_REF] Curic | Implementing Lustre Programs on Distributed Platforms with Real-time Constrains[END_REF][START_REF] Pagetti | Multi-task implementation of multiperiodic synchronous programs[END_REF], the authors study the multi-task implementation of multi-periodic synchronous programs and must allocate the different elements of the program to tasks. The clustering is out of the scope of [START_REF] Pagetti | Multi-task implementation of multiperiodic synchronous programs[END_REF], while the heuristic proposed in [START_REF] Curic | Implementing Lustre Programs on Distributed Platforms with Real-time Constrains[END_REF] is very specific to the language structure.

In [START_REF] Santinelli | Scheduling with functional and non-functional requirements: the sub-functional approach[END_REF], authors aim at reducing the number of tasks in order to reduce the complexity of the scheduling problem. However, they only focus on functional requirements to group tasks, without considering timing constraints.

This research Our objective is to automate the task clustering, so as to reach a minimal task number, while preserving the system schedulability. The number of possible clusterings of a task set is equal to the number of partitions of the set, which is in the range of the Bell number [START_REF] Rota | The number of partitions of a set[END_REF]. The Bell number is exponential with respect to the cardinality of the set, so given the huge number of possibilities to explore, we use a greedy heuristic to search the partitions space. For now, we do not consider communications and the execution platform is made up of a single processor. These are strong restrictions, which will be lifted in future work. The aim of the paper is to properly define the problem and to study it in a simple setting, so as to serve as a basis for future work.

Organization The rest of the paper is organized as follows. In Section 2, we describe our clustering model. Section 3 is dedicated to the verification of cluster schedulability. We describe the way we generate solutions and the heuristic applied in Section 4. Section 5 contains the experimental results conducted on large sets of tasks, randomly generated. Finally, we expose our conclusion and the future work involved in the Section 6.

Problem definition

Our model, illustrated in Figure 1, is based on Liu and Layland's model [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. A system consists of a synchronous (i.e. with offsets equal to zero) set of real-time tasks S = ({τ i (C i , D i , T i )} 1≤i≤n ) where C i is the worstcase execution time (WCET) of τ i , T i is the activation period, D i is the relative deadline with D i ≤ T i . We denote τ i.k the (k + 1) th (k ≥ 0) instance, or job, of τ i . The job τ i.k is released at time o i.k = kT i . Every job τ i.k must be completed before its absolute deadline

d i.k = o i.k + D i o i.0 Ci d i.0 D i o i.1 Ci d i.1 D i o i.2 0
T i T i Figure 1: Task Diagram.

Scheduling

In this paper, we focus on priority-based scheduling policies, either fixed-job with Earliest Deadline First (EDF) [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] or fixed-task priority policies with Deadline Monotonic (DM) [START_REF] Leung | On the complexity of fixed-priority scheduling of periodic, real-time tasks[END_REF].

Let J denote the infinite set of job J = {τ i.k , 1 ≤ i ≤ n, k ∈ N}. Given a priority assignment Φ, we define two functions s Φ , e Φ : J → N, where s Φ (τ i.k ) is the start time and e Φ (τ i.k ) is the completion time of τ i.k in the schedule produced by Φ. Definition 1. Let S = ({τ i } 1≤i≤n ) be a task set and Φ be a priority assignment. S is schedulable under Φ if and only if:

∀τ i.k , e Φ (τ i.k ) ≤ d i.k ∧ s Φ (τ i.k ) ≥ o i.k
In the sequel, we will also rely on the notion of laxity. Definition 2. Laxity L (or slack time) indicates the maximum delay that can be taken by the task without exceeding its deadline:

L i = D i -C i .

Clustering

Definition 3. Clustering τ i and τ j , where D i ≤ D j , produces a cluster τ ij with the following parameters:

C ij = C i + C j T ij = T i = T j D ij = D i
The cluster deadline is the shortest of the two tasks. Taking the minimum deadline ensures we respect both initial deadlines, even though the constraints will be, in general, more stringent than the initial constraints. By definition, we only group tasks with identical periods. Definition 4. Let S = ({τ i } 1≤i≤n ) be a task set and τ x and τ y be two tasks of S such that D x ≤ D y . We say that τ xy is a valid cluster if and only if:

1. L x ≥ C y

The task set obtained after clustering is schedulable

In industrial practices, functionalities of different periods are sometimes mapped together, especially when these functionalities interact a lot, to minimize communication as explained in [START_REF] Schliecker | System level performance analysis for real-time automotive multicore and network architectures[END_REF]. This possibility makes the clustering more complex because it requires to manage scheduling inside a cluster. For this reason, we do not deal with this option in this paper. Nevertheless, we could relax this assumption via, e.g., hierarchical scheduling [START_REF] Lipari | A methodology for designing hierarchical scheduling systems[END_REF].

The laxity test is just an optimization. It is redundant with the schedulability test but it is simpler to check (constant time). Laxity is depicted in Subfigure 2(a).

A schedulable system might become non schedulable after clustering, as illustrated in Figure 2. Indeed, we notice in Subfigure 2(b) that the task τ b misses its first deadline after the clustering of tasks τ a and τ c . Thus, we must check the resulting task set schedulability after clustering.

Checking cluster schedulability

Conditions 1 of the Definition 4 can be checked trivially in constant time. Nevertheless, condition 2 is more complex. Indeed, as we intend to check schedulability of a large number of solutions (i.e. at each step of the clustering process), considering a suitable schedulability test is important.

A schedulability test is called sufficient if all task sets considered schedulable by the test are actually schedulable. In the same manner, a schedulability test is called necessary if all task sets considered unschedulable by the test are in fact unschedulable. Schedulability tests that are both sufficient and necessary are referred to as exact.

In this section, we review existing schedulability tests that can be used for clustering under DM and EDF scheduling policies. We only consider exact or sufficient tests insuring that the task sets obtained after clustering are schedulable. Indeed, applying sufficient tests means that we might not get the minimum number of clusters but we are sure to obtain a valid clustering. Notice that we work with synchronous (with offsets equal to zero) task sets that have constrained deadlines (i.e. with D i ≤ T i ).

Exact schedulability tests

Authors in [START_REF] Davis | Efficient exact schedulability tests for fixed priority realtime systems[END_REF] distinguishe two types of tests: Boolean schedulability tests and response time tests. On the one hand, Boolean tests give a Boolean answer, determining only whether a task set is schedulable or not, for instance with processor demand analysis (PDA) as the Quick convergence Processor-demand Analysis (QPA) [START_REF] Zhang | Schedulability analysis for real-time systems with edf scheduling[END_REF]. On the other hand, exact tests based on response time analysis (RTA) provide worst response time for each task. The response time of a task is the time elapsed between its release and the time when it finishes its job.

Deadline Monotonic RTA [START_REF] Joseph | Finding response times in a real-time system[END_REF][START_REF] Audsley | Applying new scheduling theory to static priority pre-emptive scheduling[END_REF] of a task τ i is based on the concept of level-i busy period. The level-i busy period is the maximum continuous time interval during which a processor executes tasks of higher or equal priority to the priority of the considered task τ i , until τ i finishes its active job. Then, the computation of the worst response time for each task τ i is based on the length of level-i busy period. RTA for DM can be performed with a pseudo-polynomial time algorithm.

Earliest Deadline First Contrary to fixed-task priority (FP) systems, the worst response time is not necessarily found on the first processor busy period in a task set scheduled by EDF [START_REF] Spuri | Analysis of Deadline Scheduled Real-Time Systems[END_REF]. Thus, computing RTA for EDF is more complex and has an exponential complexity.

Sufficient schedulability conditions

In order to reduce the complexity of the computations, we also considered linear sufficient schedulability tests. Audsley [START_REF] Audsley | Deadline monotonic scheduling[END_REF] and Devi [START_REF] Devi | An improved schedulability test for uniprocessor periodic task systems[END_REF] propose sufficient but not necessary schedulability tests, respectively for DM and EDF in O(n) complexity. As far as we know, there are no more efficient tests for DM and EDF in linear complexity. The first results show that the test for DM behaves well for clustering and better than that of EDF. Those two sufficient tests actually provide an approximate worst response time for each task. They can be considered an approximate RTA analysis.

Minimizing the number of tasks

In this section, we detail our approach for minimizing the size of the initial task set by successive clusterings. Due to size of the search space, we rely on a heuristic instead of an exact algorithm.

Search space

Our problem consists in finding a partition of the task set that is schedulable and with a minimum number of subsets. A partition of a set X is a set of nonempty subsets of X such that every element n in X is in exactly one of these subsets. The number of partitions of a set is the Bell number [START_REF] Rota | The number of partitions of a set[END_REF]. The Bell number is exponential with respect to the size of X and can be computed by the following recurrence relation:

B n+1 = n k=0 n k B k with B 0 = 1
As we only cluster tasks with identical periods, the search space can be restricted to m i=0 B ni where B ni is the Bell number of set i of n tasks with equal periods and m is the number of sets. Nevertheless, this number remains exponential. To give a better idea of the size of the search, notice that for instance, B 500 ≃ 10 844 .

Partitions enumeration

A naive solution might be to conduct an exhaustive search among all partitions of the initial task set, e.g. by applying partitions generation algorithms [START_REF] Arndt | Matters Computational: Ideas, Algorithms[END_REF][START_REF] Orlov | Efficient generation of set partitions[END_REF]. Nonetheless, our first experimentations show that, even using sufficient linear tests, this solution is not achievable due to the exponential number of partitions to explore. For instance, experiments conducted on a 2.3GHz Intel Core i7 quadcore with 4GByte memory, from an initial set of 20 tasks, lead to more than several days of computation. Thus, we think that it is necessary to limit the search space by applying a heuristic.

Our technique is derived from a simple recursive method found in Section 17.1 of [START_REF] Arndt | Matters Computational: Ideas, Algorithms[END_REF]. For instance, for the set {{A}, {B}, {C}} we generate the following 3 partitions in a first step:

{{A}, {B, C}} {{A, C}, {B}} {{A, B}, {C}}
We apply recursively this principle for each partition generated until we obtain a partition with a unique element. This situation corresponds to having all tasks regrouped in a single cluster. This enumeration produces a tree as illustrated in Figure 3. Notice that this recursive algorithm generates many duplicates. For example, we can observe in the Figure 3 that the partition {{A}, {B, C, D}} appears twice. However, our heuristic always selects a single child by recursive call so we do not encounter duplicates.

Heuristic

We start from an initial task set where each task is considered a cluster with one element, we gradually try to group more and more clusters together to minimize the cardinality of the task set. At each step, we try to group one cluster with another and we have, several candidates that fullfilled conditions 1 and 2. As some possiblities are better than the others, we must select the best candidate. This can be achieved by a heuristic cost (or evaluation) function that estimates which candidate will the most likely lead to the best clustering. We propose to achieve task clustering using classic heuristics based on cost functions.

Cost functions

We need a schedulability test to determine a valid task clustering because grouping tasks makes the resulting task set more and more difficult to schedule. Moreover, we need a relevant heuristic cost function to determine the best candidate for the clustering. We want a schedulability test that exhibits some features that might allow us to compare the potential of two task sets. Therefore, in this section, we explore the compatibility of the tests presented in Section 3 with a heuristic based on a cost function.

Boolean exact tests only give a Boolean answer on the schedulability of a task set. Thus, they do not exhibit any clear feature that could be considered a heuristic cost function.

On the one hand, exact tests based on RTA gives worst response times for each task. On the other hand, sufficient tests for DM and EDF presented below are based on a pessimistic approximation of the RTA. Considering a task τ k with its worst response time denoted R k , the closer to 1 R k D k is, the less we have margin to group the task τ k with another. Thus, we can use the sum of each task response time divided by its respective deadline as heuristic cost function in both cases. Then, we have a heuristic cost function h(S), such that

h(S) = |S| k=0 R k D k
The RTA for EDF has an exponential complexity and experiments show that the test is not practicable (it takes more than several days of computation for 20 tasks). However, even though the RTA for FP has a pseudo-polynomial complexity, experiments show that run-time is not significantly slower than run-time with sufficient test under DM when the former gives an exact answer.

As a consequence, we can use the exact test based on RTA for DM and the sufficient test for EDF to achieve the best task clustering possible in a reasonable time.

Algorithm

Several heuristics based on a cost function exist such as greedy best-first search (greedy BFS), A* algorithm, simulated annealing, etc. We do not aim in this paper at comparing their different performances but at proposing a tractable solution. We moved towards a heuristic based on greedy BFS [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF] detailed in Algorithm 1. The choice of the heuristic (as BFS here) is not central in this work. The main idea is the heuristic cost function that may also be applied with other heuristics, as those cited above. In this algorithm, we recursively enumerate partitions as explained in Section 4.2. At each recursive call, we choose the most promising local child (partition generated as in Section 4.2) according to a heuristic cost function as those presented in Section 4.3.1

Lemma 1. The complexity of Algorithm 1 with linear tests is O(n 4 ) and pseudo-polynomial with pseudopolynomial tests (RTA for DM).

Proof. The number of children (or direct successors) generated by the technique described in Section 4.2 from a partition of i elements is equal to i × (i -1)/2. We only explore one among all visited children at each step with our greedy heuristic. Thus, the maximum number of visited partitions is equal to

n i=0 i×(i-1) 2
. This sum corre-sponds to the sum of the first n triangular numbers (also called tetrahedral numbers) and its closed-form expression is

f (n) = n(n+1)(n+2)
6 [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]. Hence, this sequence complexity is O(n 3 ). We apply a sufficient schedulability test in O(n) complexity (whether with DM or EDF) on each visited partition, so the heuristic complexity is

O(n 3 ) × O(n) = O(n 4
). In a similar way, applying schedulability tests with a pseudo-polynomial complexity gives a pseudo-polynomial complexity to the whole algorithm.

Algorithm 1 Automated task clustering algorithm Function clustering(S)

Require: S = ({τ i } 1≤i≤n ): initial set of tasks in ascending deadline order minSumTests ← n + 1 minSet ← null for i = n -1 to 0 do //find the best child

for j = i -1 to 0 do if T i == T j then if C i + C j ≤ min(D i , D j ) then //

Task set generation

We chose the following model to generate random task sets:

• U i : each task utilization ( Ci Ti ) is computed following the classic UUnifast [START_REF] Bini | Biasing effects in schedulability measures[END_REF] method. We denote as u the overall utilization factor of the processor.

• T i : each task period is uniformly distributed between a set of 10 coprime periods. We observed that in industrial real-time embedded systems, the number of different tasks periods is usually limited (most often less than 10).

• C i = T i × U i • D i = round((T i -C i ) × rand(d1, d2)) + C i with 0 ≤ d1 ≤ d2.
This computation comes from [START_REF] Goossens | Limitation of the hyperperiod in real-time periodic task set generation[END_REF] and use the following functions: rand(d1, d2) which returns a pseudo-random real number uniformly distributed in the interval [d1, d2] and round(x) which returns the closest integer to x. We notice that d1 = d2 = 1 corresponds to implicit deadlines and d1 ≤ d2 = 1 to constrained deadlines.

Results

Unfortunately, as mentioned in Section 4.2, we cannot compare our heuristic with an optimal solution because the task clustering is not achievable with an exhaustive search among all partitions. Instead, we study how our heuristic behaves with various task set parameters (for example, deadline bounds).

We have implemented the heuristic in Scala [START_REF] Odersky | Programming in Scala, 2/e. Artima Series[END_REF]. Task sets range from 50 to 300 tasks by step of 50 tasks. Maximum utilization factor is fixed at 0.80 for DM and at 0.75 for EDF. Indeed, our tests show that there are only few schedulable task sets (according to the tests used) generated above those values. We only take into account task sets that are initially schedulable. We compute average results by executing several times the heuristic on randomly generated task sets with the same parameters.

We observe in Figure 4(a) that the technique is efficient under DM. Indeed, the number of tasks obtained after clustering is approximately linear in the number of tasks Clustering is less efficient, especially when the utilization goes over 0.6. This difference probably comes from the fact that the clustering affects more the test under EDF than the test under DM. Finally notice that, the higher the utilization factor is, the less the tasks are clustered.

Figure 5(a) and Figure 5(b) present the clustering depending on deadline bound variations with DM. For instance, [0.4 -1.0] on the horizontal axis means that the deadline is chosen between 40% and 100% of the period minus the execution time. We can see in Figure 5(a) that the number of clusters is minimal (equal to the number of different periods) when the deadline lower bound is about 40% of the period minus the execution time. These results show that the deadline bounds have the most significant impact on the clustering (even more than the number of tasks for DM). Both with DM and EDF, the clustering is the most efficient with deadlines bounds in the interval [0.5,1]. Indeed, the closer deadlines are to the period, the more margin is left for the clustering. The clustering is even maximal in that interval because we get as many tasks as the number of different periods, both for DM and EDF. Notice that according to further experiments, this remains true for a higher number of distinct periods.

Conclusion and future work

We proposed a heuristic to automatically reduce a large set of independent tasks to a smaller set, while preserving the schedulability of the task set. The current assumption that tasks are independent will be lifted in future work. The present work is meant to lay the foundations of automated task clustering, which, as far as we know, has not been studied formally before.

Experimental results point out that under some ranges of deadline bounds, the clusterings are maximal (i.e. the number of tasks equals the number of periods). As these ranges are actually realistic, it would be interesting to try to formally prove that we can always reach maximal clusterings for these bounds. Such a property would allow to directly gather all the tasks with the same periods without using any clustering algorithm.

  Initial schedulable system of tasks τa,τ b and τc under DM.

  Resulting unschedulable system after clustering of tasks τa and τc.

Figure 2 :

 2 Figure 2: Influence of task clustering on system schedulability.

Figure 3 :

 3 Figure 3: Recursive generation of partitions.

  Task clustering under EDF.

Figure 4 :

 4 Figure 4: Results of task clustering.

  Figure 5(b) shows that no clustering is possible before the upper bound gets to around 60%. Above that bound, the efficiency of the clustering improves steadily (the number of clusters decreases). 0-1.0] [0.2-1.0] [0.4-1.0] [0.6-1.0] [0.8-1.0] [1.0-1.0] Number of tasks after clustering Deadline bounds nb tasks=200, u=0.60 (a) Variation of deadline lower bound. 0-0.0] [0.0-0.2] [0.0-0.4] [0.0-0.6] [0.0-0.8] [0.0-1.0] Number of tasks after clustering Deadline bounds nb tasks=200, u=0.60 (b) Variation of deadline upper bound.

Figure 5 :

 5 Figure 5: Task clustering with DM: impact of deadline bounds.

Figure 6 (

 6 Figure 6(a) and Figure 6(b) present the clustering for the same deadline variations with EDF. The overall trends of the curves are similar, though the clustering is overall less efficient.These results show that the deadline bounds have the most significant impact on the clustering (even more than the number of tasks for DM). Both with DM and EDF, the clustering is the most efficient with deadlines bounds

  0-1.0] [0.2-1.0] [0.4-1.0] [0.6-1.0] [0.8-1.0] [1.0-1.0] Number of tasks after clustering Deadline bounds nb tasks=200, u=0.60 (a) Variation of deadline lower bound. 0-0.0] [0.0-0.2] [0.0-0.4] [0.0-0.6] [0.0-0.8] [0.0-1.0] Number of tasks after clustering Deadline bounds nb tasks=200, u=0.60 (b) Variation of deadline upper bound.

Figure 6 :

 6 Figure 6: Task clustering with EDF: impact of deadline bounds.

  laxity S ′ ← {S \ {τ i , τ j }} ∪ τ ij

	5 Experimental results
	if schedulable(S ′ ) then
	if h(S) < minSumTests then
	minSumTests ← h(S)
	minSet ← S ′
	end if
	end if
	end if
	end if
	end for
	end for
	if minSet = null then
	return clustering(minSet) //continue with best child
	else
	return S
	end if


Benjamin Girard
email: eric.balandraud@imj-prg.fr|benjamin.girard@imj-prg.fr.

A NULLSTELLENSATZ FOR SEQUENCES OVER F p

Keywords: 2010 Mathematics Subject Classification: 11D04, 11T06, 11D45, 11P70. IMJ, Équipe Combinatoire

Let p be a prime and let A = (a 1 , . . . , a ℓ ) be a sequence of nonzero elements in Fp. In this paper, we study the set of all 0-1 solutions to the equation

We prove that whenever ℓ p, this set actually characterizes A up to a nonzero multiplicative constant, which is no longer true for ℓ < p. The critical case ℓ = p is of particular interest. In this context, we prove that whenever ℓ = 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 ℓ = 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.

Introduction

The study of the existence and variety of 0-1 solutions to linear equations over a finite Abelian group is a central topic in zero-sum combinatorics. Promoted by applications in algebraic number theory, many results have been proved in this area since the seminal paper of Erdős, Ginzburg and Ziv [START_REF] Erdős | Theorem in the additive number theory[END_REF]. The interested reader is referred to [START_REF]Geroldinger Additive group theory and non-unique factorizations[END_REF][START_REF] Geroldinger | Halter-Koch Non-unique factorizations. Algebraic, combinatorial and analytic theory[END_REF] for an exposition and many references on this subject.

Let p be a prime and let A = (a 1 , . . . , a ℓ ) be a sequence of nonzero elements in F p . In this paper, we study the set S A of all 0-1 solutions to the equation ( 1)

a 1 x 1 + • • • + a ℓ x ℓ = 0.
Equivalently, one has S A = A ⊥ ∩ {0, 1} ℓ where A ⊥ = {x ∈ F ℓ p : A • x = 0} and A • x denotes the usual inner product of A and x over F ℓ p . This very definition readily makes of S A an ambivalent object that can be expressed as the intersection of an algebraic structure, namely a hyperplane of F ℓ p , and the ℓ-cube {0, 1} ℓ , which has a more combinatorial flavor. Seen as a set of vectors, S A will be studied through the subspace S A of A ⊥ . For this reason, we will set dim(A) = dim( S A ).

In particular, since dim(A ⊥ ) = ℓ -1, it can easily be noticed that dim(A) ℓ -1 always holds. Alternatively, every element of S A can be seen as a subset of [1, ℓ]. Therefore, it is not surprising that S A also has set theoretic properties. For instance, S A is easily seen to be closed under disjoint union. It is also closed under complement if and only if the sum σ(A) of all elements in A is equal to zero. In what follows, we will be particularly interested in the number of minimal elements in S A \ {0} ordered by inclusion.

In this paper, we address three problems which appear to be closely related. First, we determine the value of dim(A) for any sequence A of ℓ p -1 nonzero elements in F p . Then, we apply our results to solve the reconstruction problem of knowing whether S A characterizes A up to a nonzero multiplicative constant. Finally, we study the number of minimal elements in S A .

The main idea behind our results is the following. For every ℓ p -1, the equality dim(A) = ℓ -1 holds true except for a very limited number of exceptional sequences which can be fully determined. Our first theorem deals with large values of ℓ, namely ℓ > p.

Theorem 1.1. Let p be a prime and let A = (a 1 , . . . , a ℓ ) be a sequence of ℓ > p nonzero elements in F p . Then

dim(A) = ℓ -1.
Consequently, whenever A is a sequence of ℓ > p nonzero elements in F p , the hyperplane A ⊥ has a basis consisting solely of elements in S A , and is thus fully characterized by its intersection with the ℓ-cube. This solves the reconstruction problem for large values of ℓ.

Corollary 1.2. Let p be a prime. Let also A, B be two sequences of ℓ > p elements in F p such that the elements of A are nonzero. Then S A ⊂ S B if and only if A and B are collinear.

Theorem 1.1 also implies a lower bound on the number of minimal elements in S A . Indeed, one can notice that any basis of A ⊥ consisting of elements in S A can be turned into a basis of A ⊥ consisting exclusively of minimal elements in S A (see Proposition 3.3). This yields the following result.

Corollary 1.3. Let p be a prime and let A = (a 1 , . . . , a ℓ ) be a sequence of ℓ > p nonzero elements in F p . Then S A contains at least ℓ -1 minimal elements.

In the case ℓ = p, there are exceptional sequences A such that dim(A) < ℓ -1. However, such exceptions are very rare, since they have to be highly structured. The following analogue of Theorem 1.1 is our first result in this direction.

Theorem 1.4. Let p be a prime and let A = (a 1 , . . . , a p ) be a sequence of p nonzero elements in F p . Then one of the following statements holds.

(i) dim(A) = 1 and there exists r ∈ F * p such that (a 1 , . . . , a p ) = (r, . . . , r).

(ii) dim(A) = p -2 and there exist t ∈ [1, p -3], σ ∈ S p , r ∈ F * p such that (a σ(1) , . . . , a σ(p) ) = (r, . . . , r t , -r, . . . , -r p-2-t , -(t + 1)r, -(t + 1)r).

(iii) dim(A) = p -1.

Therefore, in all cases where dim(A) = p -1, the same argument as above readily implies that A ⊥ has a basis consisting of elements in S A . In addition, the two exceptional cases (i) and (ii) correspond to highly structured sequences, for which we can easily check by hand that S A characterizes A ⊥ indeed. This answers the reconstruction problem affirmatively in the case ℓ = p. Corollary 1.5. Let p be a prime. Let also A, B be two sequences of p nonzero elements in F p . Then S A = S B if and only if A and B are collinear.

In his last paper [START_REF] Olson | A problem of Erdős on abelian groups[END_REF], Olson proved a conjecture of Erdős stating that if A is a nonconstant sequence of p nonzero elements in F p , then S A contains at least p -1 nonzero elements. In this respect, Theorem 1.4 actually yields a strong version of the original conjecture of Erdős. More precisely, this conjecture still holds when we restrict ourselves to counting minimal elements in S A only. This gives the following refinement of Olson's theorem.

Corollary 1.6. Let p be a prime and let A = (a 1 , . . . , a p ) be a nonconstant sequence of p nonzero elements in F p . Then S A contains at least p -1 minimal elements.

In the case ℓ = p -1, the situation becomes a little more involved but similar results can still be proved. On the one hand, all sequences A with σ(A) = 0 can easily be handled (see Lemma 5.1). On the other hand, the following theorem fully describes the case of sequences A with σ(A) = 0, which will be called zero-sum sequences.

Theorem 1.7. Let p be a prime and let A = (a 1 , . . . , a p-1 ) be a zero-sum sequence of p -1 nonzero elements in F p . Then one of the following statements holds.

(i) dim(A) = 1 and there exist σ ∈ S p-1 , r ∈ F * p such that (a σ(1) , . . . , a σ(p-1) ) = (r, . . . , r, 2r). (v) p = 7, dim(A) = p -3 = 4 and there exists σ ∈ S 6 such that

(a σ(1) , . . . , a σ(6) ) = (-1, 1, -2, 2, -3, 3). (vi) dim(A) = p -2.
It turns out that ℓ = p actually is the critical case for our reconstruction problem, since there are sequences A of p -1 nonzero elements in F p for which S A does not fully characterize A ⊥ . However, we can prove there are essentially two families of such exceptions. (ii) (iii) p = 7 and there exist σ ∈ S 6 , λ ∈ F * 7 such that (a σ(1) , . . . , a σ( 6) ) = (-1, 1, -2, 2, -3, 3)

There exist t ∈ [1, p -4], σ ∈ S p-1 , r ∈ F * p , λ ∈ F * p such that (a σ(1) , . . . , a σ(p-1) ) = (r, . . . , r t , -r, . . . , -r p-3-t , -(t + 1)r, -(t + 2)r)
and (b σ(1) , . . . , b σ(6) ) = (-λ, λ, 3λ, -3λ, 2λ, -2λ).
As for the number of minimal elements in S A when ℓ = p-1, the following result easily follows from Theorem 1.7.

Corollary 1.9. Let p be a prime and let A = (a 1 , . . . , a p-1 ) be a sequence of p -1 nonzero elements in F p . Then S A contains at least p -3 minimal elements unless A has one of the following forms.

(i) There exists r ∈ F * p such that (a 1 , . . . , a p-1 ) = (r, . . . , r).

(ii) There exist σ ∈ S p-1 and r ∈ F * p such that (a σ(1) , . . . , a σ(p-1) ) = (r, . . . , r, 2r).

The outline of the paper is as follows. In Section 2, we recall some useful tools. In Section 3, we introduce the notion of a ratio set, which makes it possible to deduce our Theorem 1.1 from the Combinatorial Nullstellensatz. In Section 4, we prove Theorem 1.4 and its corollaries. Our method is similar in nature to the one used in Section 3, except that a Vosper type theorem comes into play. In Section 5, this approach is further refined to solve our three problems in the case ℓ = p -1. Finally, in Section 6, we extend our results to the affine setting.

Some tools

In this section, we present a series of results we will use throughout the paper. As already mentioned, our method relies on the Combinatorial Nullstellensatz [START_REF] Alon | Combinatorial Nullstellensatz[END_REF], a useful algebraic tool having a wide range of applications in Combinatorics.

Theorem 2.1 (Alon [START_REF] Alon | Combinatorial Nullstellensatz[END_REF]). Let F be an arbitrary field, and let P be a polynomial in F[X 1 , . . . , X d ]. Suppose that the degree of P is

d i=1 t i and the coefficient of d i=1 X ti i is nonzero. Then, for any subsets S 1 , . . . , S d of F with |S i | > t i , there exists (s 1 , . . . , s d ) ∈ S 1 × • • • × S d such that P (s 1 , . . . , s d ) = 0.
In Additive Combinatorics, this theorem provides a unified way to estimate the cardinality of all kinds of sumsets in F p . These objects often are restrictions of the Minkowski sum For any element a ∈ F * p , the total number of appearances of a and -a in the sequence A will be called the multiplicity of the pair {a, -a} in A.

A + B = {a + b : a ∈ A,
Theorem 2.3. Let p be a prime and let A = (a 1 , . . . , a ℓ ) be a sequence of ℓ 1 nonzero elements in F p . Let also ℓ 1 ℓ 2 • • • ℓ k be all multiplicities of the pairs {a, -a} in A listed in decreasing order. Then

|Σ(A)| min p, 1 + k i=1 iℓ i .
In this paper, we will also need structural information on sequences whose set of subsums is relatively small. For this purpose, the following two Vosper type results can easily be obtained from Theorem 2.3. Lemma 2.4. Let p be a prime and let A = (a 1 , . . . , a ℓ ) be a sequence of ℓ 1 nonzero elements in F p such that

|Σ(A)| = ℓ + 1 < p.
Then there exists r ∈ F * p such that a i ∈ {±r} for all i ∈ [1, ℓ].

Proof. Denoting by ℓ 1 ℓ 2 • • • ℓ k the multiplicities of the pairs {a, -a} in A, we readily obtain

k i=1 ℓ i = ℓ. Since ℓ + 1 < p, Theorem 2.3 yields 1 + k i=1 iℓ i ℓ + 1, so that k i=1 (i -1)ℓ i = 0. Then ℓ 1 = ℓ, which is the desired result.
Going one step further, we can also prove the following lemma.

Lemma 2.5. Let p be a prime and let A = (a 1 , . . . , a ℓ ) be a sequence of ℓ 2 nonzero elements in F p such that

|Σ(A)| = ℓ + 2 < p.
Then one of the following two statements holds.

(i) There exist r ∈ F * p and i 0 ∈ [1, ℓ] such that a i0 ∈ {±2r} and a i ∈ {±r} for all i = i 0 . (ii) One has ℓ = 2.

Proof. Denoting by ℓ 1 ℓ 2 • • • ℓ k the multiplicities of the pairs {a, -a} in A, we readily obtain

k i=1 ℓ i = ℓ. Since ℓ + 2 < p, Theorem 2.3 gives 1 + k i=1 iℓ i ℓ + 2, so that k i=1 (i -1)ℓ i 1. Then either ℓ 1 = ℓ or (ℓ 1 , ℓ 2 ) = (ℓ -1, 1). If ℓ 1 = ℓ, then there exists r ∈ F * p such that a i ∈ {±r} for all i ∈ [1, ℓ], which implies |Σ(A)| = ℓ+1, a contradiction. Now, suppose that (ℓ 1 , ℓ 2 ) = (ℓ -1, 1) and ℓ > 2. Then there exist r ∈ F * p and i 0 ∈ [1, ℓ] such that a i ∈ {±r} for all i = i 0 . It follows that Σ(A (a i0
)) and a i0 + Σ(A (a i0 )) both are arithmetic progressions of length ℓ > 2 with same difference r. Thus, for the equality

|Σ(A)| = |{0, a i0 } + Σ(A (a i0 ))| = ℓ + 2 to hold, we must have a i0 ∈ {±2r}.

Ratio sets and long sequences

Let p be a prime and let A be a sequence of ℓ 1 nonzero elements in F p . In this section, we describe first our general approach to proving dim(A) = ℓ -1. Then, we prove Theorem 1.1 and its corollaries.

3.1. Ratio sets. Let p be a prime. Let also A = (a 1 , . . . , a ℓ ) and B = (b 1 , . . . , b ℓ ) be two sequences of ℓ 1 elements in F p such that the elements of A are nonzero. For every λ ∈ F p , we consider the set

I λ = {i ∈ [1, ℓ] : b i /a i = λ} .
Any element λ ∈ F p such that I λ = ∅ will be called a ratio associated with (A, B). Now, let λ 1 , . . . , λ d be the pairwise distinct ratios associated with (A, B). For every i ∈ [1, d], we define the subsequence

S i = (a j : j ∈ I λi ).
In particular, one has

d i=1 |S i | = ℓ.
Finally, for every i ∈ [1, d], we introduce the ratio set

Σ i = Σ(S i ). It follows from Cauchy-Davenport Theorem that (2) |Σ i | min{p, |S i | + 1}.
In this paper, our main argument to prove that dim(A) = ℓ -1 is as follows. First, note that such an equality holds if and only if for every B ∈ S A ⊥ , A and B are collinear, that is to say, for every sequence B of ℓ elements in F p such that S A ⊂ S B , one has d = 1. In order to prove that d = 1 indeed, properties of the ratio sets Σ i will be deduced from the Combinatorial Nullstellensatz. Before stating our first result in this direction, we observe that the ratio sets Σ i associated with (A, B) readily have the following interesting feature. Lemma 3.1. Let p be a prime. Let A, B be two sequences of ℓ 1 elements in F p such that the elements of A are nonzero and S A ⊂ S B . Let also λ 1 , . . . , λ d be the ratios associated with (A, B).

Then Σ i ∩ (-Σ j ) = {0} for any two distinct elements i, j ∈ [1, d].
Proof. By definition, we readily have 0 ∈ Σ i for all i ∈ [1, d]. Now, assume there is an element s ∈ Σ i ∩ (-Σ j ) such that s = 0. By definition of Σ i and Σ j , there exist

J i ⊂ I λi and J j ⊂ I λj such that k∈Ji a k = s = -k∈Jj a k . Since S A ⊂ S B , then k∈Ji a k + k∈Jj a k = 0 yields k∈Ji b k + k∈Jj b k = 0 which is equivalent to k∈Ji λ i a k + k∈Jj λ j a k = 0 so that (λ i -λ j )s = 0, which is a contradiction.
On the one hand, an immediate corollary of Lemma 3.1 is that whenever d 2, one has

|Σ i | < p and |Σ i | |S i | + 1 for all i ∈ [1, d], so that (3) d i=1 (|Σ i | -1) ℓ.
On the other hand, the ratio sets also have the following general property, which will be useful throughout the paper. Theorem 3.2. Let p be a prime. Let A, B be two sequences of ℓ 1 elements in F p such that the elements of A are nonzero and S A ⊂ S B . Let also λ 1 , . . . , λ d be the ratios associated with (A, B).

If d 2, then d i=1 (|Σ i | -1) p. In addition, d i=1 (|Σ i | -1) = p implies d i=1 λ i (|Σ i | -1) = 0 in F p . Proof.
Let λ 1 , . . . , λ d be the ratios associated with (A, B) and assume d 2. We shall consider the polynomial

P (X 1 , . . . , X d ) = d i=1 λ i X i   d i=1 X i p-1 -1   ,
which has degree p. Since S A ⊂ S B , P is easily seen to vanish on d i=1 Σ i . In addition, the monomials of degree p in P are the same as those of

d i=1 λ i X i d i=1 X i p-1 = d i=1 λ i X i      (t1,...,t d ) d i=1 ti=p-1 (p -1)! d i=1 t i ! d i=1 X ti i      = d i=1 λ i X p i + (t1,...,t d ) d i=1 ti=p max{ti}<p (p -1)! d i=1 t i ! d i=1 λ i t i d i=1 X ti i . Assume d i=1 (|Σ i | -1) > p. Then there exists (t i ) i∈[1,d] such that d i=1 t i = p, where 0 t i |Σ i | -1 for all i ∈ [1, d], and two distinct elements i 0 , j 0 ∈ [1, d] such that t i0 > 0 and t j0 < |Σ j0 | -1. We define (t ′ i ) i∈[1,d] by t ′ i0 = t i0 -1, t ′ j0 = t
λ i t i - d i=1 λ i t ′ i = λ i0 -λ j0 = 0,
which is a contradiction. Thus, one of these coefficients is nonzero, and by Theorem 2.1, P cannot vanish on

d i=1 Σ i , a contradiction too. It follows that d i=1 (|Σ i | -1) p.
In addition, if one has

d i=1 (|Σ i | -1) = p, then since P vanishes on d i=1 Σ i , Theorem 2.1 implies that the coefficient of d i=1 X |Σi|-1 i in P is zero, that is to say d i=1 λ i (|Σ i | -1) = 0 in F p . 3.2.
The case of long sequences. Thanks to Theorem 3.2, it is now easy to deduce our first theorem and its corollaries.

Proof of Theorem 1.1. Let A be a sequence of ℓ > p nonzero elements in F p . For any given sequence B of ℓ > p elements in F p such that S A ⊂ S B , let λ 1 , . . . , λ d be the ratios associated with (A, B) and assume d 2. On the one hand, the inequality (3) implies that

d i=1 (|Σ i | -1) ℓ > p. On the other hand, it follows from Theorem 3.2 that d i=1 (|Σ i | -1)
p, which is a contradiction. Therefore d = 1, and the desired result is proved. Corollary 1.2 now is a straightforward consequence of Theorem 1.1. In addition, one can easily notice that Corollary 1.3 follows directly from Theorem 1.1 and the following general proposition. Proposition 3.3. Let p be a prime and let A be a sequence of ℓ 1 nonzero elements in F p such that dim(A) = ℓ -1. Then there exists a basis of A ⊥ consisting of minimal elements of S A .

Proof. Let (e 1 , . . . , e ℓ-1 ) be a basis of A ⊥ consisting of elements in S A . Let F be the set of all minimal elements in S A that are contained in at least one e i . Now, since each e i is a disjoint union of minimal elements in S A , we obtain

S A ⊂ F ⊂ A ⊥ . Since dim(A) = ℓ -1, it follows that F = A ⊥ and F contains a basis of A ⊥ .

Sequences of length p

Let p be a prime and let ℓ p. In this section, we introduce a special class of sequences A of ℓ nonzero elements in F p for which dim(A) < ℓ -1 readily holds. In the case ℓ = p, we determine all sequences in this class. We then refine the approach of Section 3 to prove that dim(A) = p -1 for all remaining sequences. 4.1. Exceptional and regular sequences. Let A be a sequence of ℓ p nonzero elements in F p . Then, A will be called exceptional whenever there exist two distinct elements i, j ∈ [1, ℓ] such that for all x ∈ S A , one has

|{i, j} ∩ x| ∈ {0, 2}.
Any sequence which is not exceptional will be called regular. In others terms, A is a regular sequence if and only if for any two distinct elements i, j ∈ [1, ℓ], there is x ∈ S A such that |{i, j} ∩ x| = 1.

On the one hand, regular sequences have the following useful property. Lemma 4.1. Let p be a prime. Let A be a regular sequence of ℓ elements in F * p , and B be a sequence of ℓ elements in F p such that S A ⊂ S B . Then

∀i, j ∈ [1, ℓ], (a i = a j ) =⇒ (b i = b j ).
Proof. Let i, j be two distinct elements of [1, ℓ] such that a i = a j . Since A is regular, there exists x ∈ S A such that |{i, j} ∩ x| = 1, say i ∈ x and j / ∈ x. Therefore, x ′ = (x {i}) ∪ {j} ∈ S A . By assumption, it follows that x, x ′ ∈ S B and

B • x -B • x ′ = b i -b j = 0, which is the desired result.
On the other hand, one can notice that dim(A) < ℓ -1 readily holds whenever A is exceptional. However, it turns out that for large values of ℓ, exceptional sequences are highly structured and can easily be determined. For instance, the following lemma fully characterizes all exceptional sequences in the case ℓ = p. Proposition 4.2. Let p be a prime and let A = (a 1 , . . . , a p ) be an exceptional sequence. Then one of the following statements holds.

(i) dim(A) = 1 and there exists r ∈ F * p such that (a 1 , . . . , a p ) = (r, . . . , r).

(ii) dim(A) = p -2 and there exist t ∈ [1, p -3], σ ∈ S p , r ∈ F * p such that (a σ(1) , . . . , a σ(p) ) = (r, . . . , r t , -r, . . . , -r p-2-t , -(t + 1)r, -(t + 1)r).
Proof. Since A is exceptional, there exist two distinct elements i, j ∈ [1, p] such that for all x ∈ S A , one has |{i, j} ∩ x| ∈ {0, 2}. Now, let A ′ be the sequence obtained from A by deleting a i and a j . Then, Cauchy-Davenport Theorem gives

|Σ(A ′ )| min{p, (p -2) + 1} = p -1.
By assumption, one has -a i / ∈ Σ(A ′ ) and -a j / ∈ Σ(A ′ ), so that |Σ(A ′ )| = p -1 and a i = a j . Thus, by Lemma 2.4, there exists r ∈ F * p such that a k ∈ {±r} for all k / ∈ {i, j}. If a k = r for all k / ∈ {i, j}, then one has -a i = (p -1)r, which gives a i = a j = r. Therefore, A is of the form given in (i), and it can easily be checked that dim(A) = p -1. Note that the same conclusion holds if a k = -r for all k / ∈ {i, j}. Otherwise, there is t ∈ [1, p -3] such that A ′ consists of t copies of r and p -2t copies of -r. In this case, we obtain a i = a j = -(t + 1)r, so that, by relabelling if necessary, A is of the form given in (ii). The following table then gives a basis of S A .

t p-2-t r . . . r -r . . . -r -(t + 1)r -(t + 1)r p -2 -t    1 1 (0) . . . (0) . . . t    1 1 (0) (0) . . . (0) . . . (0) 1 1 1 . . . 1 1 . . . 1 1 1 4.2.
Another property of ratio sets. Before proving Theorem 1.4, we need the following general result on ratio sets, which will not only be useful in the case ℓ = p, but in subsequent sections also.

Proposition 4.3. Let p be a prime. Let A, B be two sequences of ℓ 1 elements in F p such that the elements of A are nonzero and S A ⊂ S B . Let also λ 1 , . . . , λ d be the ratios associated with (A, B) and assume d 2. Given any two distinct elements i 0 , j 0 ∈ [1, d] and r i0 ∈ S i0 , define

Σ ′ i0 = Σ(S i0 (r i0 )), Σ ′ j0 = Σ(S j0 ∪ (r i0 )) = Σ j0 + {0, r i0 } and Σ ′ i = Σ i otherwise. Then the polynomial Q i0,j0 (X 1 , . . . , X d ) = d i=1 λ i X i d i=1 λ i X i -χ   d i=1 X i p-1 -1   ,
where χ = (λ j0λ i0 )r i0 , vanishes on

d i=1 Σ ′ i . In addition, the coefficient of a monomial d i=1 X ti i in Q i0,j0 with d i=1 t i = p+1 and max{t i } < p is (p -1)! d i=1 t i !   d i=1 λ i t i 2 - d i=1 λ 2 i t i   .
Proof. Since S A ⊂ S B , the polynomial

P (X 1 , . . . , X d ) = d i=1 λ i X i   d i=1 X i p-1 -1   vanishes on d i=1 Σ i and divides Q i0,j0 . Therefore, Q i0,j0 vanishes on d i=1 Σ i . Now, for any (x ′ i ) i∈[1,d] ∈ d i=1 Σ ′ i d i=1 Σ i , let us consider (x i ) i∈[1,d] defined by x i0 = x ′ i0 + r i0 , x j0 = x ′ j0 -r i0 and x i = x ′ i otherwise, which is an element of d i=1 Σ i . Note that d i=1 x ′ i = d i=1 x i . In addition, since S A ⊂ S B , the equality d i=1 x ′ i = 0 implies d i=1 λ i x i = 0, so that d i=1 λ i x ′ i =λ i0 (x i0 -r i0 ) + λ j0 (x j0 + r i0 ) + d i=1 i =i0, i =j0 λ i x i =(λ j0 -λ i0 )r i0 + d i=1 λ i x i =(λ j0 -λ i0 )r i0 , which proves that Q i0,j0 vanishes on d i=1 Σ ′ i .
Finally, Q i0,j0 clearly has degree p + 1 and the monomials of degree p + 1 in Q i0,j0 are the same as those of

d i=1 λ i X i 2 d i=1 X i p-1 =   d i=1 λ 2 i X 2 i + 2 1 i<j d λ i λ j X i X j        (t1,...,t d ) d i=1 ti=p-1 (p -1)! d i=1 t i ! d i=1 X ti i      = d i=1 λ 2 i X p+1 i + d i=1 d j=1 j =i (-λ 2 i + 2λ i λ j )X p i X j + (t1,...,t d ) d i=1 ti=p+1 max{ti}<p (p -1)! d i=1 t i !   d i=1 λ 2 i t i (t i -1) + 2 1 i<j d λ i λ j t i t j   d i=1 X ti i = d i=1 λ 2 i X p+1 i + d i=1 d j=1 j =i λ i (2λ j -λ i )X p i X j + (t1,...,t d ) d i=1 ti=p+1 max{ti}<p (p -1)! d i=1 t i !   d i=1 λ i t i 2 - d i=1 λ 2 i t i   d i=1
X ti i .

4.3.

Proof of Theorem 1.4. We can now prove the main result of this section and its corollaries.

(|Σ i | -1) = p and d i=1 λ i (|Σ i | -1) = 0 in F p . Suppose that d = 2. Since |Σ 1 | + |Σ 2 | p + 2, we obtain |Σ 1 ∩ (-Σ 2 )| 2,
|Σ i | < p -1 for all i ∈ [1, d]. It follows that |Σ i | = |S i | + 1 for all i ∈ [1, d],
and Lemma 2.4 implies that there exists r i ∈ F * p such that all elements of S i are equal to r i or -r i .

For any two distinct elements i 0 , j 0 ∈ [1, d] and any r i0 ∈ S i0 , let us consider the sets Σ ′ i defined by

Σ ′ i0 = Σ(S i0 (r i0 )), Σ ′ j0 = Σ(S j0 ∪ (r i0 )) = Σ j0 + {0, r i0 } and Σ ′ i = Σ i otherwise. Let also Q i0,j0
d i=1 t i = p + 1. Since d i=1 λ i (|Σ i | -1) = 0 in F p , Proposition 4.3 implies that, up to a nonzero multiplicative constant, the coefficient of d i=1 X ti i in Q i0,j0 is d i=1 λ i t i 2 - d i=1 λ 2 i t i =(2λ j0 -λ i0 ) 2 -2λ 2 j0 -λ 2 i0 + d i=1 λ 2 i (|Σ i | -1) =(2λ 2 j0 -4λ i0 λ j0 + 2λ 2 i0 ) - d i=1 λ 2 i (|Σ i | -1) =2(λ j0 -λ i0 ) 2 - d i=1 λ 2 i (|Σ i | -1).
Note that

d i=1 λ 2 i (|Σ i | -1
) is independent of i 0 and j 0 . In addition, the coefficient of

d i=1 X ti i in Q i0,j0 is zero if and only if (λ j0 -λ i0 ) 2 = 1 2 d i=1 λ 2 i (|Σ i | -1).
Since d 3, there is at least one pair (i 0 , j 0 ) such that this equality does not hold. It follows from Theorem 2.1 that for this actual pair, Q i0,j0 cannot vanish on Proof of Corollary 1.6. Let A be a nonconstant sequence of p nonzero elements in F p . By Theorem 1.4, there are two cases to consider. If dim(A) = p-1, the required result directly follows from Proposition 3.3. Otherwise, there exist t ∈ [1, p -3] and r ∈ F * p such that A consists of t copies of r, p -2t copies of -r and two copies of -(t + 1)r. Denoting the minimum and maximum of t and p -2t by m and M respectively, it is easily seen that the number of minimal elements in

S A is mM + M m . Now, if t ∈ [2, p -4]
, then p 7 and S A contains at least 2(p -4) p -1 minimal elements. If t ∈ {1, p -3}, then p 5 and S A contains exactly 2(p -3) p -1 minimal elements, which completes the proof.

Sequences of length p -1

Let p be prime and let A be a sequence of p -1 nonzero elements in F p . In this section, we start by showing that the dimension and structure of A can easily be deduced from Theorem 1.4 whenever σ(A) = 0. Then, we concentrate on the case where σ(A) = 0 and prove Theorem 1.7 as follows. On the one hand, we determine all exceptional zero-sum sequences. On the other hand, we further refine our general approach to handle the case of regular zero-sum sequences.

5.1. The case of nonzero-sum sequences. Given a sequence A = (a 1 , . . . , a ℓ ) of ℓ 1 nonzero elements in F p such that σ(A) = 0, we consider the sequence A ′ = (a 1 , . . . , a ℓ , -σ(A)). The aim of the following lemma is to show that the value of dim(A) can easily be derived from dim(A ′ ).

Lemma 5.1. Let p be a prime and let A be a sequence of ℓ 1 nonzero elements in F p such that σ(A) = 0. Then A ′ is a zero-sum sequence and

dim(A ′ ) = dim(A) + 1.
Proof. Let us set X = {(x 1 , . . . , x ℓ+1 ) ∈ S A ′ : x ℓ+1 = 0}. We clearly have σ(A ′ ) = 0, which implies that S A ′ is closed under complement. Therefore,

S A ′ = X ∪ {(1, . . . , 1)} .
In addition, it follows from the very definition of X that (1, . . . , 1) ∈ S A ′ \ X and dim(X) = dim(A). Thus,

dim(A ′ ) = dim( S A ′ ) = dim(X) + 1 = dim(A) + 1,
which completes the proof.

In particular, Lemma 5.1 implies that for every sequence A of p -1 nonzero elements in F p such that σ(A) = 0, either dim(A) = p -2, or dim(A) = 0 and A is constant, or dim(A) = p -3 and A can be obtained by deleting any element in a sequence of type (ii) in Theorem 1. [START_REF] Davenport | On the addition of residue classes[END_REF].

The reconstruction problems on A and A ′ are also closely related to each other.

Lemma 5.2. Let p be a prime and let A, B be two sequences of ℓ 1 nonzero elements in F p such that σ(A) = 0. Then S A ′ = S B ′ if and only if S A = S B .

Proof. Since σ(A ′ ) = 0, the desired result is a straightforward consequence of the fact that S A ′ is closed under complement.

For instance, let A, B be two sequences of p -1 nonzero elements in F p such that σ(A) = 0 and S A = S B . Specifying ℓ = p -1 in Lemma 5.2, we obtain that S A ′ = S B ′ . Then, it easily follows from Corollary 1.5 that A ′ and B ′ are collinear, and so are A and B. From now on, we thus consider zero-sum sequences only.

5.2.

The case of exceptional zero-sum sequences. We now state and prove the following lemma, which fully characterizes all exceptional zero-sum sequences in the case ℓ = p -1.

Proposition 5.3. Let p be a prime and let A = (a 1 , . . . , a p-1 ) be an exceptional zero-sum sequence. Then one of the following statements holds.

(i) dim(A) = 1 and there exist σ ∈ S p-1 , r ∈ F * p such that (a σ(1) , . . . , a σ(p-1) ) = (r, . . . , r, 2r).

(ii) dim(A) = p -4 and there exist σ ∈ S p-1 , r ∈ F * p such that (a σ(1) , . . . , a σ(p-1) ) = (r, . . . , r p-5 , -r, 2r, 2r, 2r). , -(t + 1)r, -(t + 2)r).

Proof. Since A is exceptional, there exist two distinct elements i, j ∈ [1, p -1] such that for all x ∈ S A , one has |{i, j} ∩ x| ∈ {0, 2}. Now, let A ′ be the sequence obtained from A by deleting a i and a j . Then, Cauchy-Davenport Theorem gives

|Σ(A ′ )| min{p, (p -3) + 1} = p -2.
By assumption, one has -a i / ∈ Σ(A ′ ) and -a j / ∈ Σ(A ′ ). We now consider two cases.

• |Σ(A ′ )| = p -2.
Then, by Lemma 2.4, there exist t ∈ [0, p -3] and r ∈ F * p such that A ′ consists of t copies of r and p -3t copies of -r. Therefore, we obtain that {a i , a j } ⊂ {-(t + 1)r, -(t + 2)r}. If a i = a j , then a i + a j ∈ {-2(t + 1)r, -2(t + 2)r}. Since σ(A ′ ) = (2t + 3)r, we would have σ(A) = 0, which is a contradiction. Thus, one has a i = a j and, by relabelling if necessary, it follows that either t ∈ {0, p -3} and A is of the form given in (i), or t ∈ [1, p -4] and A is of the form given in (iv).

• |Σ(A ′ )| = p -1. Then, a i = a j and by Lemma 2.5, there exist t ∈ [0, p -4] and r ∈ F * p such that A ′ consists of t copies of r, p -4t copies of -r and one copy of 2r. If t = p -4, then Σ(A ′ ) = F p {-r} and a i = a j = r, so that A is of the form given in (i). If t = p -5, then Σ(A ′ ) = F p {-2r}, a i = a j = 2r and A is of the form given in (ii). Otherwise, one has t ∈ [0, p -6], Σ(A ′ ) = F p {(t + 3)r}, a i = a j = -(t + 3)r, and A is of the form given in (iii).

The following tables give a basis of S A for cases (ii) to (iv).

(ii) dim(A) = p -4.

p-5 r . . . r -r 2r 2r 2r

p -5    1 (0) 1 . . . . . . (0) (0) 1 1 1 . . . 1 1 1 1 1 (iii) dim(A) = p -3 and t ∈ [1, p -6]. t p-4-t r . . . r -r . . . -r 2r -(t + 3)r -(t + 3)r p -4 -t    1 1 (0) . . . (0) . . . t    1 1 (0) (0) (0) . . . (0) . . . (0) 1 1 (0) 1 (0) 1 1 0 0 1 . . . 1 1 . . . 1 1 1 1
And whenever t = 0, p-4 -r -r . . . -r 2r -3r -3r

p -5    1 1 (0) 1 . . . . . . . . . ( 0
) (0) 1 (0) 1 1 0 1 (0) 1 1 0 0 1 1 . . . 1 1 1 1 (iv) dim(A) = p -3 and t ∈ [1, p -4]. t p-3-t r . . . r -r . . . -r -(t + 1)r -(t + 2)r p -3 -t    1 1 (0) . . . (0) . . . t    1 1 (0) (0) . . . (0) . . . (0) 1 1 1 . . . 1 1 . . . 1 1 1 5.3
. Preliminary results. In the proof of Theorem 1.7, we will need the following two lemmas to deal with the cases where the number of distinct ratios is small. The first one gives some nonvanishing properties of a particular quadratic polynomial.

Lemma 5.4. Let p 5 be a prime. Given u, v ∈ F p , let f be the quadratic polynomial

f (x, y) = 2x 2 -6xy + 6y 2 + 2u(3y -x) + v.
Then, for any three pairwise distinct elements α 1 , α 2 , α 3 ∈ F p , there exists σ ∈ S 3 such that one of the following holds.

(i) f (α σ(1) , α σ(2) ) f (α σ(1) , α σ(3) ) = 0, (ii) f (α σ(2) , α σ(1) ) f (α σ(3) , α σ(1) ) = 0, (iii) f (α σ(1) , α σ(2) ) f (α σ(2) , α σ(1) ) = 0, (iv) f (α σ(1) , α σ(2) ) f (α σ(2) , α σ(3) ) f (α σ(3) , α σ(1) ) = 0.
Proof. It is an easy exercise to show that, up to a nonzero multiplicative constant, the only quadratic polynomial vanishing on the six points (α 1 , α 2 ), (α 2 , α 1 ), (α 1 , α 3 ), (α 3 , α 1 ), (α 2 , α 3 ) and (α 3 , α 2 ) is

x 2 + y 2 + xy -(x + y)(α 1 + α 2 + α 3 ) + (α 1 α 2 + α 1 α 3 + α 2 α 3 ).
Thus, there exist two distinct elements i, j ∈ {1, 2, 3} such that f (α i , α j ) = 0. Now, let k be the remaining element of {1, 2, 3} and assume that for all σ ∈ S 3 , none of the properties (i) to (iv) holds. Then one has f (α j , α i ) = 0, f (α i , α k ) = 0 and f (α k , α j ) = 0. In addition, since f (α i , α j ) f (α j , α k ) f (α k , α i ) = 0, we have that either f (α j , α k ) = 0 or f (α k , α i ) = 0. Therefore, there exists σ ∈ S 3 such that

f α σ(1) , α σ(2) = f (α σ(2) , α σ(1) ) = f (α σ(1) , α σ(3) ) = f (α σ(3) , α σ(2) ) = 0.
We consider first the case where β = 0. Then, P 2 = {0, d, . . . , αd} and α 2. Also, there exists a unique pair of integers (q, u) such that p -(|P 1 | -(t + 1)) = qd + u and 1 u d.

Since P 1 ∩P 2 = {0}, we have qd+ u αd+ 1. Now, counting separately the missing elements of P 1 ∪ P 2 in the three intervals [0, d], [d + 1, αd -1] and [αd, p -1], we obtain that

|F p \ (P 1 ∪ P 2 )| = ((d -1) -t) + (α -1)(d -1) + ((qd + u) -(αd + 1)).
Since α, d 2, one has (α -1)(d -1) 1. We now distinguish two cases.

• In the case |P 1 | + |P 2 | = p, one has |P 1 ∪ P 2 | = p -1, so that α = d = q = 2
and u = t = 1. This is the structure of case (1) in the statement of the lemma.

• In the case |P 1 | + |P 2 | = p -1, one has |P 1 ∪ P 2 | = p -2, so that (qd + u) - (αd + 1) 1, which implies α = q.
-If q = 2 and d = 2, one has either u = 1 and t = 0, this is case (3), or u = 2 and t = 1, this is case (4). -If q = 3 and d = 2, one has u = 1 and t = 1, this is case [START_REF] Davenport | A historical note[END_REF].

-If q = 2 and d = 3, one has u = 1 and t = 2, this is case [START_REF] Erdős | Theorem in the additive number theory[END_REF]. We now turn to the case where β 1. Since We can now prove the last of our main theorems.

P 1 ⊂ [-d + 1, d -1], one has p -1 2 |P 1 | 2d -1. • If |P 2 | = 3,
Proof of Theorem 1.7. Let A = (a 1 , . . . , a p-1 ) be a zero-sum sequence of p -1 nonzero elements in F p not being of the forms given in (i) to (iv). Thanks to Proposition 5.3, we can assume that A is regular. For any given sequence B of p -1 elements in F p such that S A ⊂ S B , let λ 1 , . . . , λ d be the ratios associated with (A, B) and assume d 2. On the one hand, the inequality (3) implies that

|(Σ 1 {0}) + Σ 2 | (|Σ 1 | -1) + (|Σ 2 | -1) |S 1 | + |S 2 | = p -1.
Therefore, one has |Σ i | = |S i | + 1 for each i ∈ {1, 2}. Since |Σ i | < p by Lemma 3.1, it follows from Lemma 2.4 that there exists r i ∈ F * p such that all elements of S i are equal to r i or -r i . In addition, since A is a zero-sum sequence, Lemma 3.1 yields σ(S 1 ) = σ(S 2 ) = 0, so that r i occurs as many times as -r i in S i . Now, for each i ∈ {1, 2}, consider the subsequence S ′ i of S i which contains only the occurrences of r i , and set Σ ′ i = Σ(S ′ i ). We clearly have that

|S ′ 1 | + |S ′ 2 | = p -1 2 and |Σ ′ 1 | + |Σ ′ 2 | = p + 3 2 .
Suppose that there exist (x 1 , y 1 ) ∈ (Σ ′ 1 ) 2 and (x 2 , y 2 ) ∈ (Σ ′ 2 ) 2 such that x 1 + x 2 = y 1 + y 2 . Then, one has x 1y 1 = y 2x 2 , where x 1y 1 ∈ Σ 1 and x 2y 2 ∈ Σ 2 . Thus, Lemma 3.1 implies that x 1 = y 1 and x 2 = y 2 . This proves that all elements of Σ ′ 1 + Σ ′ 2 have a unique representation as a sum x 1 + x 2 , where (

x 1 , x 2 ) ∈ Σ ′ 1 × Σ ′ 2 , so that |Σ ′ 1 + Σ ′ 2 | = |Σ ′ 1 ||Σ ′ 2 | = |Σ ′ 1 | p + 3 2 -|Σ ′ 1 | . If 2 < |Σ ′ 1 | < p-1 2 , one has |Σ ′ 1 + Σ ′ 2 | > 2 p-1 2 = p -1. In addition, since p is prime, one cannot have |Σ ′ 1 + Σ ′ 2 | = |Σ ′ 1 ||Σ ′ 2 | = p either.
Therefore, one of the two sets, say Σ ′ 1 , has cardinality 2. Then |S ′ 1 | = 1 and S 1 = (r 1 , -r 1 ). Now, since A is regular, there is a subsequence T 2 of S 2 such that σ(S ′ 1 ) + σ(T 2 ) = 0. It follows from Lemma 3.1 that σ(S ′ 1 ) = r 1 = 0, which is a contradiction. p such that all elements of S i are equal to r i or -r i . Now, for any two distinct elements i 0 , j 0 ∈ [1, d] with i 0 = k, and any r i0 ∈ S i0 , let us consider the sets Σ ′ i defined by

Σ ′ i0 = Σ(S i0 (r i0 )), Σ ′ j0 = Σ(S j0 ∪ (r i0 )) = Σ j0 + {0, r i0 } and Σ ′ i = Σ i otherwise. Let also Q i0,j0
i ) i∈[1,d] by t i0 = |Σ i0 | -2, t j0 = |Σ j0 | + 1 and t i = |Σ i | -1 otherwise. In particular, t i |Σ ′ i | -1 < p for all i ∈ [1, d] and d i=1 t i = p + 1. By Theorem 3.2, we have that d i=1 λ i (|Σ i | -1) = 0 in F p . Thus, Proposition 4.3 implies that, up to a nonzero multiplicative constant, the coefficient of d i=1 X ti i in Q i0,j0 is d i=1 λ i t i 2 - d i=1 λ 2 i t i =(2λ j0 -λ i0 ) 2 -2λ 2 j0 -λ 2 i0 + d i=1 λ 2 i (|Σ i | -1) =(2λ 2 j0 -4λ i0 λ j0 + 2λ 2 i0 ) - d i=1 λ 2 i (|Σ i | -1) =2(λ j0 -λ i0 ) 2 - d i=1 λ 2 i (|Σ i | -1). Note that d i=1 λ 2 i (|Σ i | -1
) is independent of i 0 and j 0 . In addition, the coefficient of

d i=1 X ti i in Q i0,j0 is zero if and only if (λ j0 -λ i0 ) 2 = 1 2 d i=1 λ 2 i (|Σ i | -1).
Since d 3, there is at least one pair (i 0 , j 0 ) such that this equality does not hold. Since i 0 and j 0 play symmetric roles, i 0 can be chosen such that i 0 = k indeed. It follows from Theorem 2.1 that for this actual pair, Q i0,j0 cannot vanish on

i | < p -1 for all i ∈ [1, d]. It follows that |Σ i | = |S i | + 1 for all i ∈ [1, d],
and Lemma 2.4 implies that there exists r i ∈ F * p such that all elements of S i are equal to r i or -r i . Note, in particular, that one has ±r i = r j for any two distinct elements i, j ∈ [1, d].

In addition, if one of the ratio sets, say Σ 1 , has cardinality p -2, then d = 3 and

|S 2 | = |S 3 | = 1.
Since A is regular, there would be a subsequence T 1 of S 1 such that σ(T 1 ) + σ(S 2 ) = 0. By Lemma 3.1, we would have σ(S 2 ) = 0, a contradiction. This proves that

|Σ i | < p -2 for all i ∈ [1, d].
Now, for any two distinct elements i 0 , j 0 ∈ [1, d] and any r i0 ∈ S i0 such that

|S j0 | > 1 and ± 1 2 r i0 / ∈ S j0 , let us consider the sets Σ ′ i defined by Σ ′ i0 = Σ(S i0 (r i0 )), Σ ′ j0 = Σ(S j0 ∪ (r i0 )) = Σ j0 + {0, r i0 } and Σ ′ i = Σ i otherwise. Let also Q i0,j0
d i=1 X ti i in Q i0,j0 is d i=1 λ i t i 2 - d i=1 λ 2 i t i = d i=1 λ i (|Σ i | -1) + 3λ j0 -λ i0 2 - d i=1 λ 2 i (|Σ i | -1) + 3λ 2 j0 -λ 2 i0 =(2λ 2 i0 -6λ i0 λ j0 + 6λ 2 i0 ) + 2 d i=1 λ i (|Σ i | -1) (3λ j0 -λ i0 ) + d i=1 λ i (|Σ i | -1) 2 - d i=1 λ 2 i (|Σ i | -1) . Since d i=1 λ i (|Σ i | -1) and d i=1 λ 2 i (|Σ i | -1
) are independent of i 0 and j 0 , this last expression is a quadratic polynomial f in λ i0 and λ j0 . In addition, the coefficient of

d i=1 X ti i in Q i0,j0 is zero if and only if f (λ i0 , λ j0 ) = 0. Case 3.1: If d 5, then choose any j 0 ∈ [1, d] such that |S j0 | > 1.
On the one hand, there are at most two ratios λ i such that f (λ i , λ j0 ) = 0. On the other hand, there is at most one set S i such that ± 1 2 r i ∈ S j0 . Since d 5, the pigeonhole principle implies that there is at least one pair (i 0 , j 0 ) such that f (λ i0 , λ j0 ) = 0 and ± 1 2 r i0 / ∈ S j0 . It follows from Theorem 2.1 that for this actual pair, Q i0,j0 cannot vanish on d i=1 Σ ′ i , which contradicts Proposition 4.3. Case 3.2: If d ∈ {3, 4} and there are at least three sets S i , such that |S i | > 1, then without loss of generality, we may assume that |S i | > 1 for each i ∈ {1, 2, 3}. In particular, p 7. Now, by Lemma 5.4, one of the following holds.

• If f (λ 1 , λ 2 ) f (λ 1 , λ 3 ) = 0, then there is j 0 ∈ {2, 3} such that ± 1 2 r 1 / ∈ S j0 . Therefore, setting i 0 = 1, we have f (λ i0 , λ j0 ) = 0 and ± 1 2 r i0 / ∈ S j0 indeed.

• If f (λ 2 , λ 1 ) f (λ 3 , λ 1 ) = 0, then there is i 0 ∈ {2, 3} such that ± 1 2 r i0 / ∈ S 1 . Therefore, setting j 0 = 1, we have f (λ i0 , λ j0 ) = 0 and ± 1 2 r i0 / ∈ S j0 indeed.

• If f (λ 1 , λ 2 ) f (λ 2 , λ 1 ) = 0, then p 7 implies that one cannot have both r 1 = ±2r 2 and r 2 = ±2r 1 . Thus, there are two distinct elements i 0 , j 0 ∈ {1, 2} such that f (λ i0 , λ j0 ) = 0 and ± 1 2 r i0 / ∈ S j0 indeed.

• If f (λ 1 , λ 2 ) f (λ 2 , λ 3 ) f (λ 3 , λ 1 ) = 0, then p 7 implies that the three equalities r 1 = ±2r 2 and r 2 = ±2r 3 and r 3 = ±2r 1 can occur only when r i = ±8r i , so that p = 7. Otherwise, there are two distinct elements i 0 , j 0 ∈ {1, 2, 3} such that f (λ i0 , λ j0 ) = 0 and ± 1 2 r i0 / ∈ S j0 indeed.

It follows that whenever p = 7, there is at least one pair (i 0 , j 0 ) such that f (λ i0 , λ j0 ) = 0 and ± 1 2 r i0 / ∈ S j0 . Theorem 2.1 then implies that for this actual pair, Q i0,j0 cannot vanish on • Σ 1 = {0, 1, 2}, Σ 2 = {0, 2, 4}, Σ 3 = {0, 4, 1}, which gives S 1 = (1, 1), S 2 = (2, 2) and S 3 = (-3, -3). It can easily be checked that such a sequence A satisfies dim(A) = p -2, so that d = 1, a contradiction. • Σ 1 = {-1, 0, 1}, Σ 2 = {-2, 0, 2}, Σ 3 = {-3, 0, 3}, which gives S 1 = (-1, 1), S 2 = (-2, 2) and S 3 = (-3, 3). Therefore, by relabelling if necessary, one has A = (-1, 1, -2, 2, -3, 3). The following table then gives a basis of S A .

-1 1 -2 2 -3 3 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 If d = 3, then p 7 and since σ(S 1 )+ σ(S 2 )+ σ(S 3 ) = 0, Lemma 3.1 implies that σ(S 1 ) and σ(S 2 ) are nonzero. Therefore, Lemma 5.5 implies there exists r ∈ F * p such that Σ 1 = {0, 2, 4}.r and Σ 2 = {-1, 0, 1, . . . , p -5}.r. On the one hand, this gives σ(S 1 ) + σ(S 2 ) = -2r. On the other hand, the single element of S 3 has to be in {3, 4}.r, so that σ(A) = 0, a contradiction.

If d = 4, then p 11 and since σ(S 1 ) + σ(S 2 ) + σ(S 3 ) + σ(S 4 ) = 0, Lemma 3.1 implies that either σ(S 1 ) or σ(S 2 ) is nonzero. Therefore, Lemma 5.5 implies there exists r ∈ F * p such that one of the following cases holds.

there is an affine transformation mapping S α A onto S AI , for a particular I ⊂ [1, ℓ]. Therefore, our results provide a full description of the dimension and structure of the sets S α A , for all α ∈ F p . Lemma 6.1. Let p be a prime and let A = (a 1 , . . . , a ℓ ) be a sequence of ℓ p -1 nonzero elements in F p . Then, for every α ∈ F p , there exists I ⊂ [1, ℓ] such that dim(A, α) = dim(A I ). Therefore, S AI is the image of S α A by the affine transformation (x 1 , . . . , x ℓ ) → (y 1 , . . . y ℓ ), where y i = 1x i if i ∈ I and y i = x i otherwise.

( 5 ,

 5 ii) dim(A) = p -4 and there exist σ ∈ S p-1 , r ∈ F * p such that (a σ(1) , . . . , a σ(p-1) ) = (r, . . . , r p--r, 2r, 2r, 2r). (iii) dim(A) = p -3 and there exist t ∈ [0, p -6], σ ∈ S p-1 , r ∈ F * p such that (a σ(1) , . . . , a σ(p-1) ) = (r, . . . , r t , -r, . . . , -r p-4-t , 2r, -(t + 3)r, -(t + 3)r). (iv) dim(A) = p -3 and there exist t ∈ [1, p -4], σ ∈ S p-1 , r ∈ F * p such that (a σ(1) , . . . , a σ(p-1) ) = (r, . . . , r t , -r, . . . , -r p-3-t , -(t + 1)r, -(t + 2)r).

Corollary 1 . 8 .

 18 Let p be a prime. Let also A, B be two sequences of p -1 nonzero elements in F p . Then S A = S B if and only if A and B are either collinear or have one of the following forms.(i) There exist σ ∈ S p-1 , r ∈ F * p , λ ∈ F * p such that (a σ(1) , . . . , a σ(p-1) ) = (r, . . . , r, r, 2r) and (b σ(1) , . . . , b σ(p-1) ) = (λr, . . . , λr, 2λr, λr).

and (b σ( 1 )

 1 , . . . , b σ(p-1) ) = (λr, . . . , λr t , -λr, . . . , -λr p-3-t , -(t + 2)λr, -(t + 1)λr).

  which would contradict Lemma 3.1. From now on, we thus assume d 3. Since A is regular, Lemmas 3.1 and 4.1 give

  i , which contradicts Proposition 4.3. Proof of Corollary 1.5. Let A, B be two sequences of p nonzero elements in F p . One direction of the implication is trivial. Thus, we shall prove that A and B are collinear whenever S A = S B . By Theorem 1.4, there are three cases to consider. If dim(A) = p -1, then S A ⊂ S B already implies the required result. If A is constant, it is also easily seen that S A = S B holds if and only if B is constant. Otherwise, A and B both are of the form given in Theorem 1.4 (ii). In particular, there exist t ∈ [1, p -3] and r ∈ F * p such that, by relabelling if necessary, one has A = (r, . . . , r t , -r, . . . , -r p-2-t , -(t + 1)r, -(t + 1)r). Since S A ⊂ S B , we deduce that B = (λr, . . . , λr t , -λr, . . . , -λr p-2-t , -(t + 1)λr + d, -(t + 1)λrd), for some λ ∈ F * p and d ∈ F p . Thus, B is of the form given in Theorem 1.4 (ii) if and only if d = 0, which completes the proof.

(

  iii) dim(A) = p -3 and there exist t ∈ [0, p -6], σ ∈ S p-1 , r ∈ F * p such that (a σ(1) , . . . , a σ(p-1) ) = (r, . . . , r t , -r, . . . , -r p-4-t , 2r, -(t + 3)r, -(t + 3)r).(iv) dim(A) = p -3 and there exist t ∈ [1, p -4], σ ∈ S p-1 , r ∈ F * p such that (a σ(1) , . . . , a σ(p-1) ) = (r, . . . , r t , -r, . . . , -r p-3-t

5 . 4 .

 54 then either |P 1 | = p -3 and d = (p -1)/2, which is case (2), or |P 1 | = p -4 and d ∈ {(p -3)/2, (p -1)/2}, which yields cases (7), (8), (9). • If |P 2 | 4, then α 2 or β 2. Therefore, one of the two intervals [d + 1, 2d -1] and [-2d + 1, -d -1] has to be disjoint from P 1 . Such an interval can contain at most one element of P 2 , and thus contains at least d -2 elements being neither in P 1 nor in P 2 . Since |P 1 | + |P 2 | p -1 and |P 1 ∩ P 2 | = 1, one has |P 1 ∪ P 2 | p -2 and then d -2 2. -If d = 2, then 4 |P 2 | |P 1 | 3, a contradiction. -If d = 3, then p 11 and 4 |P 2 | |P 1 | 5. Since |P 1 | + |P 2 | 8, it follows that p = 11 and |P 1 | = |P 2 | = 5, which gives (10.a). -If d = 4, then p 15 and 4 |P 2 | |P 1 | 7. Since |P 1 | + |P 2 | 8, it follows that either p = 11 and (10.b) or (10.c) holds, or p = 13 and (11) holds. Proof of Theorem 1.7.

d i=1 (

 i=1 |Σ i | -1) p -1. On the other hand, it follows from Theorem 3.2 that d i=1 (|Σ i | -1) p, which yields d i=1 (|Σ i | -1) ∈ {p -1, p}.Case 1: d = 2. By Lemma 3.1, one has 0 / ∈ (Σ 1 {0}) + Σ 2 and Cauchy-Davenport Theorem implies that

Case 2 :

 2 d 3 and d i=1 (|Σ i | -1) = p. On the one hand, since d 3 and A is regular, Lemmas 3.1 and 4.1 imply that |Σ i | < p -1 for all i ∈ [1, d]. On the other hand, there is k ∈ [1, d] such that |Σ i | = |S i | + 1 for all i = k. Using Lemma 2.4, we obtain that for every i = k, there exists r i ∈ F *

  i | -1) = p -1.Since A is regular, Lemmas 3.1 and 4.1 give |Σ

  d i=1 Σ ′ i , which contradicts Proposition 4.3. The only remaining case to consider is p = 7, d = 3 and |S i | = 2 for each i ∈ {1, 2, 3}. Therefore, by relabelling if necessary, there are only two possible cases.

Case 3 . 3 :

 33 If d ∈ {3, 4} and there are exactly two sets S i such that |S i | > 1, then without loss of generality, we can suppose that these two sets are S 1 and S 2 , where |S 1 | |S 2 |. Therefore Σ 1 and Σ 2 are two arithmetic progressions such that|Σ 1 | + |Σ 2 | = p + 3d.In addition, it follows from Lemma 3.1 that Σ 1 and -Σ 2 satisfy the hypothesis of Lemma 5.5. We thus consider the following cases.

Proof.

  By Cauchy-Davenport Theorem, one has |Σ(A)| min{p, ℓ + 1} = p. Thus, there exists I ⊂ [1, ℓ] such that i∈I a i = α. Now, let A I = (a ′ 1 , . . . , a ′ ℓ ). Then, for every J ⊂ [1, ℓ], one has i∈J a i = α if and only if i∈J a i -

  be as in Proposition 4.3. Since Σ i0 is an arithmetic progression with difference r i0 , one has |Σ ′ i0 | = |Σ i0 |-1. In addition, since A is regular, Lemmas 3.1 and 4.1 imply that r i0 = ±r j0 . It follows from Lemma 2.4 that |Σ ′ j0 | |Σ j0 | + 2. We now define (t i ) i∈[1,d] by t i0 = |Σ i0 | -2, t j0 = |Σ j0 | + 1 and t i = |Σ i | -1 otherwise. In particular, t i |Σ ′

i | -1 < p for all i ∈ [1, d] and

  be as in Proposition 4.3. Then, one has |Σ ′ i0 | = |Σ i0 | -1. In addition, since A is regular, Lemmas 3.1 and 4.1 imply that ±r i0 / ∈ S j0 . It follows from Theorem 2.3 that |Σ ′ j0 | |Σ j0 | + 2. We now define (t

  be as in Proposition 4.3. Then, one has |Σ ′ i0 | = |Σ i0 | -1. In addition, since |S j0 | > 1 and neither ±r i0 nor ± 1 2 r i0 are elements of S j0 , it follows from Lemma 2.5 that |Σ ′ j0 | |Σ j0 | + 3. We now define (t i ) i∈[1,d] by t i0 = |Σ i0 | -2, t j0 = |Σ j0 | + 2 and t i = |Σ i | -1 otherwise. In particular, t i |Σ ′

	d i=1 t i = p + 1. Proposition 4.3 implies that, up to a nonzero multiplicative constant, the coefficient
	of

i | -1 < p for all i ∈ [1, d] and

Research supported by the French ANR Project "CAESAR" No. ANR-12-BS01-0011.

Without loss of generality, we may assume that σ is the identity, so that

Since α 1 , α 2 , α 3 are pairwise distinct, they are solution to the linear system   

Since p 5, the determinant of this system is 6 = 0 in F p . Therefore, this system has a unique solution, which is easily seen to be α 1 = α 2 = α 3 = -u. This contradicts the fact that α 1 , α 2 , α 3 are pairwise distinct, and the proof is complete.

Our second lemma gives the structure of a pair of arithmetic progressions covering almost all F p , but intersecting in only one element. Lemma 5.5. Let p be a prime. Let also P 1 and P 2 be two arithmetic progressions in F p with distinct differences, such that min{|P 1 |, |P 2 |} 3 and

then there exists r ∈ F * p such that P 1 and P 2 have one of the following forms.

(1) {0, 2, 4}.r and {5, 6, . . . , p -1, 0, 1}.r,

then there exists r ∈ F * p such that P 1 and P 2 have one of the following forms.

(3) {0, 2, 4}.r and {5, 6, . . . , p -1, 0}.r, (4) {0, 2, 4}.r and {6, 7, . . . , p -1, 0, 1}.r, (5) {0, 2, 4, 6}.r and {7, 8, . . . , p -1, 0, 1}.r, (6) {0, 3, 6}.r and {7, 8, . . . , 0, 1, 2}.r, (7) {-p-1 2 , 0, p-1 2 }.r and {-p-5 2 , -p-7 2 , . . . , p-7 2 , p-5 2 }.r, (8) {-p-1 2 , 0, p-1 2 }.r and {-p-7 2 , -p-9 2 , . . . , p-5 2 , p-3 2 }.r, (9) {-p-3 2 , 0, p-3 2 }.r and {-p-5 2 , -p-7 2 , . . . , p-7 2 , p-5 2 }.r, (10) p = 11 and (a) {-6, -3, 0, 3, 6}.r and {-2, -1, 0, 1, 2}.r, (b) {-4, 0, 4, 8}.r and {-2, -1, 0, 1, 2, 3}.r, (c) {-8, -4, 0, 4, 8}.r and {-2, -1, 0, 1, 2}.r, (11) p = 13 and {-8, -4, 0, 4, 8}.r and {-3, -2, -1, 0, 1, 2, 3}.r.

Proof. Without loss of generality, we can suppose that

Up to a nonzero multiplicative constant, we can also assume that P 1 has difference 1. Now, we set

where α and β are two nonnegative integers. Note that replacing (d, α, β) by (-d, β, α) yields the same arithmetic progression, so we may assume that d ∈ [2, (p -1)/2]. In addition, P 1 and P 2 satisfy the hypothesis of the lemma if and only if -P 1 and -P 2 do so, which allows us to suppose that d ∈ P 2 , that is α 1. Since P 1 ∩ P 2 = {0}, we obtain that

where 0 t < d.

• Σ 1 = {0, 2, 4}.r and Σ 2 = {0, 1, . . . , p -5}.r. Then, σ(S 1 ) + σ(S 2 ) = -r and the elements of S 3 and S 4 have to be in {3, 4}.r. Therefore, one has σ(A) = 0, which is a contradiction. • Σ 1 = {0, 2, 4}.r and Σ 2 = {-1, 0, 1, . . . , p-6}.r. Then, σ(S 1 )+σ(S 2 ) = -3r

and the elements of S 3 and S 4 have to be in {3, 4, 5}.r. Therefore, one has σ(A) = 0, which is a contradiction. • Σ 1 = {0, 2, 4, 6}.r and Σ 2 = {-1, 0, 1, . . . , p -7}.r. Then, σ(S 1 ) + σ(S 2 ) = -2r and the elements of S 3 and S 4 have to be in {3, 4, 6}.r when p = 11, and in {3, 4, 5, 6}.r whenever p 13. In all cases, one has σ(A) = 0, which is a contradiction.

-3r and the elements of S 3 and S 4 have to be in {4, 6}.r when p = 11, and in {4, 5, 6}.r whenever p 13. In all cases, one has σ(A) = 0, which is a contradiction.

2 , 0, p-1 2 }.r and Σ 2 = {-p-3 2 , . . . , -1, 0, 1, . . . , p-7 2 }.r Then, σ(S 1 )+σ(S 2 ) = -2r and the elements of S 3 and S 4 have to be in { p+3 2 , p+5 2 }.r. Therefore, one has σ(A) = 0, which is a contradiction.

• p = 11, Σ 1 = {-4, 0, 4, 8}.r and Σ 2 = {-2, -1, 0, 1, 2, 3}.r. Then, the elements of S 3 and S 4 have to be in {-5, 5}.r, which would contradict Lemma 3.1.

Case 3.4: If d ∈ {3, 4} and there is only one set S i such that |S i | > 1, then without loss of generality, we can suppose that this set is S 1 . If d = 3, and since A is regular, there is a subsequence T 1 of S 1 such that σ(T 1 ) + σ(S 2 ) = 0. It follows from Lemma 3.1 that σ(S 2 ) = 0, which is a contradiction. Thus, d = 4 and Lemma 3.1 implies that, by relabelling if necessary, there exist t ∈ [0, p -4] and r ∈ F * p such that Σ 1 = {-(p -4t), . . . , -1, 0, 1, . . . , t}.r, Σ 2 = {0, -(t + 1)}.r, Σ 3 = {0, -(t + 2)}.r, Σ 4 = {0, -(t + 3)}.r. Since t ∈ [0, p -4], one has σ(A) = -(t + 2)r = 0, which contradicts the fact that A is a zero-sum sequence.

Proof of Corollary 1.8. Let A, B be two sequences of p -1 nonzero elements in F p . It is easily checked that S A = S B whenever A and B are collinear, or have one of the forms given in (i), (ii) and (iii). Conversely, suppose that A, B are such that S A = S B . If σ(A) = 0 then Lemma 5.2 and Corollary 1.5 imply that A and B are collinear. If σ(A) = 0 then, using Theorem 1.7, there are six cases to consider.

• If dim(A) = p -2 then S A ⊂ S B already implies that A and B are collinear.

• If dim(A) = 1, then dim(B) = 1 and it is easily seen that there exist λ, r ∈ F * p such that A (resp. B) consists of p -2 copies of r (resp. λr) and one copy of 2r (resp. 2λr). Therefore, A and B either are collinear or have the form given in (i).

• If p = 7 and, by relabelling if necessary, one has

then it can be checked by hand that S A = S B if and only there is λ ∈ F * p such that B = (-λ, λ, -2λ, 2λ, -3λ, 3λ) or B = (-λ, λ, 3λ, -3λ, 2λ, -2λ).

Therefore, A and B either are collinear or have the form given in (iii).

• Proof of Corollary 1.9. Let A be a sequence of p -1 nonzero elements in F p not being of the forms given in (i) and (ii). If σ(A) = 0, then Lemma 5.1 and Theorem 1.4 readily imply that dim(A) p -3. Then, the desired result follows directly from Proposition 3.3. If σ(A) = 0 then, using Theorem 1.7, there are only two cases to consider. If dim(A) p -3, then Proposition 3.3 implies that the number of minimal elements in S A is at least p -3. If dim(A) = p -4, then there exist r ∈ F * p such that A consists of p -5 copies of r, one copy of -r and three copies of 2r. Now, either one has p = 5 and A has the form given in (ii), or p 7 and the number of minimal elements in S A is 2(p -5) p -3.

A concluding remark

Let p be a prime and let A = (a 1 , . . . , a ℓ ) be a sequence of ℓ 1 nonzero elements in F p . In this paper, we proved that for every ℓ p -1, the equality dim(A) = ℓ -1 holds except for a very limited number of exceptional sequences which can be fully determined. However, our results can easily be extended to the affine setting.

Given any element α ∈ F p , let S α A be the set of all 0-1 solutions to the equation a 1 x 1 + • • • + a ℓ x ℓ = α, and let dim(A, α) = dim(aff(S α A )) be the dimension of the affine hull of S α A . For any I ⊂ [1, ℓ], we consider the sequence A I = (a ′ 1 , . . . , a ′ ℓ ) defined by a ′ i = -a i if i ∈ I and a ′ i = a i otherwise. Whenever ℓ p -1, the following lemma shows that