Roland Bacher

Constructions of some perfect integral lattices with minimum 4

We construct several families of perfect sublattices with minimum 4 of Z d . In particular, the number of d-dimensional perfect integral lattices with minimum 4 grows faster than d k for every exponent k.

Perfection and perfect lattices

A subset S of a real d-dimensional vector space V is a perfect subset of V (or perfect in V ) if the span of the set {v ⊗ v} v∈S is the full d+1 2 -dimensional vector space v,w∈V v ⊗w +w ⊗v of all symmetric tensor products in V ⊗V . In the sequel we speak simply of perfect sets if the ambient vector space is obvious.

A choice of a basis x 1 , . . . , x d of V identifies V with the vector space

Perfection of S is equivalent to the fact that the set    d i=1

 d i=1 a i x i ∈S
of all quadratic forms associated to elements in S spans the full d+1 2dimensional vector space of all quadratic forms (homogeneous polynomials of degree 2). Equivalently, S is perfect (in V ) if and only if the set of symmetric matrices {(a i a j ) 1≤i,j≤d } a i x i ∈S spans the vector space of all symmetric square-matrices of size d. The matrix (a i a j ) 1≤i,j≤d is, up to a scalar multiple, the orthogonal projection of V onto a i x i with respect to the scalar product with orthonormal basis x 1 , . . . , x n .

Perfect sets of vector spaces over real fields determine scalar products uniquely in the following way: A scalar product , : V × V -→ R on V × V is uniquely defined by the set { v, v } v∈S of norms of elements in S if and only if S is perfect.

Remark 1.1. Perfection can be generalized as follows: A subset S of a vector space V over a field of characteristic 0 or larger than

k is k-perfect in V if the elements of the set {v ⊗ v ⊗ • • • ⊗ v ∈ V ⊗ k | v ∈ S} span the n+k-1 k
-dimensional subspace spanned by all symmetric k-fold tensor powers

{ σ∈S k v σ(1) ⊗ v σ(2) ⊗ • • • ⊗ v σ(k) | v 1 , . . . , v k ∈ V } of V . A k-perfect subset of V is k ′ -perfect for k ′ ≤ k.
Given a subset S of a d-dimensional vector space V over a field K of characteristic 0, we denote by A k the vector space spanned by the set {v ⊗ v ⊗ • • • ⊗ v ∈ V ⊗ k | v ∈ S} and by α k = dim(A k ) the dimension of A k . We use the convention A 0 = K and α 0 = 1. The generating series ∞ k=0 α k t k ∈ N[t] is always a rational function of the form

P S (t)
1-t for P S ∈ N[t] a polynomial with non-negative integral coefficients. It would be interesting to understand all possible polynomials arising in this way. In dimension d = 2 we have P S = 1 + t + t 2 + • • • + t a-1 = 1-t a 1-t where a is the number of distinct lines {Kv} v∈S defined by all elements of S.

We will make repeated use of the following trivial observation which is assertion 1 of Proposition 3.5.3 in [START_REF] Martinet | Perfect Lattices in Euclidean Spaces[END_REF]: Proposition 1.2. Let S be a set of non-zero elements in a d-dimensional vector space V . Suppose that V contains a hyperplane H such that S ∩ H is perfect in H and suppose that the elements S \(S ∩H) of S in the complement V \ H of H generate V . Then S is perfect.

We apply Proposition 1.2 always in the case where V is a Euclidean vector space. The hyperplane H can then be described as the orthogonal subspace H = v ⊥ of a non-zero element v in V . Proof of Proposition 1.2 We extend a basis b 1 , . . . , b d-1 of H to a basis b 1 , . . . , b d of V . The vector space spanned by {v ⊗ v} v∈S∩H contains the vector space of all symmetric tensor products in H ⊗ H by perfection of S ∩ H. The fact that S \ (S ∩ H) generates V implies that the vector space spanned by {v ⊗ v} v∈S\(S∩H) contains all symmetric tensors b i ⊗ b d + b d ⊗ b i for i = 1, . . . , d. 2

Perfect lattices

A Euclidean lattice (or lattice in the sequel) is a discrete subgroup of a finitedimensional Euclidean vector space E. A lattice Λ of rank d = dim(Λ ⊗ Z R) is isomorphic to Z d as a group. Λ is integral if the scalar product E × E ∋ (u, v) -→ u, v ∈ R has an integral restriction , : Λ×Λ -→ Z. The norm of a lattice-element λ is in the sequel always the squared Euclidean length λ, λ of λ. An integral lattice is even if all its elements have even norm. We denote by Λ min the set of shortest non-zero elements, called minimal elements, in Λ and by min(Λ) the minimal norm v, v of a minimal element v in Λ min . The determinant det(Λ) of a lattice is the squared volume of a fundamental domain for the action (by translations) of Λ on (Λ ⊗ Z R).

The determinant det(Λ) is given by det(G) with (G) (d/2)! ) centered at all lattice points. Extreme lattices are lattices whose density is locally maximal (with respect to the obvious natural topology on the space of lattices of given dimension). Extreme lattices are perfect and eutactic (a positivity condition), cf. Theorem 3.4.6 in [START_REF] Martinet | Perfect Lattices in Euclidean Spaces[END_REF]. Perfection and eutaxy are however independent in the sense that one property does not necessarily imply the other. Thus there exist perfect lattices which are not extreme. All perfect lattices can be realized, up to similarity, as integral lattices (cf. Proposition 3.2.11 of [START_REF] Martinet | Perfect Lattices in Euclidean Spaces[END_REF]) and there are only finitely many of them (up to similarity and isometry) in any given dimension, cf. Theorem 3.5.4 in [START_REF] Martinet | Perfect Lattices in Euclidean Spaces[END_REF]. The following definition provides a measure for perfection: Given a lattice Λ of rank d, we denote by pd(Λ) its perfection-default (called co-rank in the monograph [START_REF] Martinet | Perfect Lattices in Euclidean Spaces[END_REF] devoted to perfect lattices) defined as d+1 2 dim(A) with A = v∈Λ min R v ⊗ v denoting the vector space spanned by {v ⊗ v} v∈Λ min . A lattice is perfect if and only if its perfection-default is zero.

The aim of this paper is the construction of a few integral lattices with minimum 4 (we describe also a family with minimum 3). All considered lattices are sublattices of Z n and are thus kernels of morphisms ϕ : Z n -→ A onto a suitable abelian group A. The specific form of ϕ is of crucial importance since it allows the deduction of perfection from combinatorial properties. Our construction is very flexible and gives rise to many inequivalent perfect lattices. In particular, we show in Theorem 2.7 that the number of inequivalent perfect integral lattices of minimum 4 and dimension d has no polynomial upper bound as a function of d.

The sequel of this paper is organized as follows: Section 2 describes the main construction and its generalization, obtained by considering suitable d-dimensional sublattices of the (d + 1)-dimensional root lattice of type A. The rest of the paper is essentially a variation on this theme. Section 3 avoids the use of the root lattice of type A by considering the orthogonal of an integral vector having only odd coefficients. Section 4 replaces the root lattice of type A by the root lattice of type D. Section 5 considers sublattices of finite index in root lattices of type A. Section 6 considers sublattices of finite index in root lattices of type D. Section 7 discusses briefly a family of perfect lattices having minimum 3 related to projective spaces over the field F 2 of 2 elements. The rest of the paper deals with other variations based on finite abelian groups and generalizations.

A sequence of perfect lattices

We denote by L d the even integral lattice of rank d defined by all vectors of Z d+2 orthogonal to both elements ( 2 -20 = 1 and is not perfect. The seven rows of the matrix

A =           1 -1 0 0 0 -1 1 0 0 0 0 0 1 -1 -1 1 0 0 1 0 -1 0 -1 0 1 0 0 0 1 -1 0 0 -1 1 0 0 0 -1 1 0 0 0 1 -1 0 1 -1 -1 1 0 0 0 0 0 1 -1 0 0 0 0 0 -1 1          
span the perfect lattice L 7 . The associated Gram matrix AA t with determinant

2 3 •3 4 •2•5 2 2 •3 = 2 2 • 3 3 • 5 is the reduced Gram matrix P 7 7 =           4 2 2 1 2 2 2 2 4 2 2 1 1 0 2 2 4 2 0 2 1 1 2 2 4 -1 0 -1 2 1 0 -1 4 0 2 2 1 2 0 0 4 2 2 0 1 -1 2 2 4          
at page 382 of [START_REF] Martinet | Les réseaux parfaits des espaces euclidiens[END_REF]. Gram-matrices for all perfect lattices up to dimension 7 are only given in the original French version [START_REF] Martinet | Les réseaux parfaits des espaces euclidiens[END_REF]. They are unfortunately missing in the English translation [START_REF] Martinet | Perfect Lattices in Euclidean Spaces[END_REF].

Proof of Theorem 2.1 The determinant of L d is equal to the determinant of the 2-dimensional lattice

Z d+2 ∩ (L d ⊗ Z R) ⊥ of Z d+2 which is orthogonal to L d . Thus the determinant of L d is given by det u, u u, v v, u v, v with u = (1, 1, . . . , 1), v = (1, 2, . . . , d + 2) ∈ Z d+2 ,
i + 2α + β ≤ d + 2. The lattice L d contains thus d-1 i=1 ⌊(d+1-i)/2⌋ α=1 d + 2 -i -2α
pairs of minimal vectors. This formula, restricted to even, respectively odd, natural integers, defines a polynomial function of degree 3. Explicit expressions can be found by interpolation of four values. We prove perfection of L d by induction on d. Perfection of the lattice L 7 considered above establishes the result for d = 7.

The identity (1, 2, 3, . . . , d+3)-(1, 1, 1, . . . , 1) = (0, 1, 2, . . . , d+2) shows that the sublattice of L d+1 orthogonal to (1, 0, 0, . . . , 0) is the lattice L d which is perfect by assumption. By Proposition 1.2 it is enough to show that the vector space spanned by the set of minimal vectors with first coordinate non-zero (i.e. with first coordinate ±1) has dimension d + 1. We set u = e 1 -e 3 -e 4 +e 6 and v i = e 1 -e 2 -e i-1 +e i for i = 4, . . . , d+3. Consideration of the last index i with non-zero coefficient of the vector v i shows linear independency of the d vectors v 4 , . . . , v d+3 . Computation of

v 5 + v 6 -u = e 1 -2e 2 + e 3
shows linear independency of u from v 4 , . . . , v d+3 and ends the proof. 2

A generalization

To a strictly increasing sequence 1 ≤ a 1 < a ) consisting of all elements with last coefficient zero is the lattice L d (a 1 , . . . , a k ) which is perfect by assumption. We have thus only to prove that the set of all minimal vectors in L d+1 (a 1 , . . . , a k ) with last coefficient non-zero spans a vector space of dimension d + 1. For simplicity, we work with I d+3 (a 1 , . . . , a k ) as the set of indices for the d+3 coefficients of elements in L d+1 (a 1 , . . . , a k ). We denote by ω ≤ d+ 3+ k, respectively ψ the largest, respectively second-largest, element of I d+3 (a 1 , . . . , a k ). For every index i ∈ I d+3 (a 1 , . . . , a k ) with i < ψ we construct a linear combination

u(i) = α v v of minimal elements v = (v 1 , .
. . , v ω ) ending with last nonzero coefficient v ω = 1 such that i is the index of the first non-zero coefficient in u(i). If i < ω -2k -3, there exists an integer j = j(i) in {1, . . . , k + 1} such that both integers i + j and ωj belong to I d+3 (a 1 , . . . , a k ) and we can take u(i) = e ie i+je ω-j + e ω . For i ∈ I d+3 (a 1 , . . . , a k ) such that i ∈ {ω -2k -2, . . . , ψ -1} we set α = ωi and β = ωψ. We have 1 ≤ β ≤ k + 1 and β ≤ α ≤ 2(k + 1). Since a 1 ≥ 2(k + 1) 2 + 2, all integers 6 1, 2, . . . , 1 + αβ ≤ 2(k + 1) 2 + 1 are in I and we can consider 2 Proof of Proposition 2.5 Theorem 2.1 shows the result for k = 0. We assume henceforth k ≥ 1 and max(2(k + 1) 2 + 1, 9) = 2(k + 1) 2 + 1.

u(i) = (
We denote by α the smallest integer such that {α, α+1, . . . , α+2(k+1) 2 } is contained in {1, 2, . . . } \ {a 1 , . . . , a k }. For α = 1 the proof follows from Proposition 2.4. Otherwise we establish the result by induction on k and d using Proposition 1.2. We assume α > 1 and we consider L d+1 (a 1 , . . . , a k ). Since L d+1 (a 1 , . . . , a k ) with a 1 = 1 is isomorphic to L d+1 (a 2 -1, a 3 -1, . . . , a k -1) (which is perfect by induction on k, the case k = 0 being covered by Theorem 2.1) we can assume a 1 > 1 . Since α > 1, the sublattice L d (a 1 -1, a 2 -1, . . . , a k -1) consisting of all vectors of L d+1 (a 1 , . . . , a k ) with first coefficient zero is perfect by induction on d. By Proposition 1.2 it is thus enough to show that the set of minimal elements of L d+1 (a 1 , . . . , a k ) with first coefficient non-zero spans a (d + 1)-dimensional vector space. The proof is analogous to the proof of Proposition 2.4 except that we work with small coordinates instead of large ones and that we use the 2(k + 1) 2 + 1 indices α, . . . , α + 2(k + 1) 2 instead of the set {1, . . . , 2(k + 1) 2 + 1}. 2

Examples for Theorem 2.3

Below we list a few lattices of dimension 7 or 8 illustrating Theorem 2.3 for k = 1, 2. For k = 1 we indicate the relevant integer a 1 missing in 1, 2, . . . , d+ 3 together with the determinant, the perfection-default pd

(L d (a 1 )) = d+1 2 - dim v∈L d (a 1 ) R v ⊗ v and the number mp of pairs of minimal vectors. The lattice L d (1) is obviously isomorphic to the lattice L d = L d (∅) studied previously. Since L d (i) and L d (d + 4 -i) are isomorphic, it is enough to consider the four cases i = 2, 3, 4, 5 for d = 7. lattice det pd mp L 7 (2) 2 2 • 5 • 31 1 31 L 7 (3) 2 3 • 5 • 17 1 29 L 7 (4) 2 4 • 3 2 • 5 0 28 L 7 (5) 2 2 • 5 • 37 4 28
The perfect lattice L 7 (4) of determinant 2 4 • 3 2 • 5 (and defined as the set of all integral vectors in Z 9 which are orthogonal to (1, 1, 1, 1, 1, 1, 1, 1, 1) and (1, 2, 3, 5, 6, 7, 8, 9, 10)) has a basis given by the rows of

A =           0 1 -1 0 0 0 0 -1 1 0 0 -1 1 0 1 0 -1 0 0 0 0 1 -1 0 0 -1 1 0 0 0 0 0 1 -1 -1 1 1 -1 0 0 -1 1 0 0 0 1 0 -1 0 0 0 -1 0 1 1 -1 0 0 0 0 0 -1 1          
with Gram matrix AA t given by the matrix

P 31 7 =           4 2 2 2 -1 2 1 2 4 2 2 1 1 1 2 2 4 2 1 1 2 2 2 2 4 1 2 2 -1 1 1 1 4 1 2 2 1 1 2 1 4 2 1 1 2 2 2 2 4          
at page 383 of [START_REF] Martinet | Les réseaux parfaits des espaces euclidiens[END_REF].

The list of lattices of the form L 8 (a i ) (with a i ∈ {2, . . . , 6} in order to avoid duplicates) with a few properties is given by

lattice det pd mp L 8 (2) 2 2 • 3 • 7 • 11 0 46 L 8 (3) 7 • 11 • 13 0 44 L 8 (4) 2 5 • 3 • 11 0 42 L 8 (5) 3 2 • 11 2 0 42 L 8 (6) 2 2 • 5 2 • 11 3 42
The following table lists all six perfect non-isomorphic lattices of the form L 8 (a 1 , a 2 ) obtained by removing two elements a 1 , a 2 from {2, . . . , 11} (we exclude a 1 = 1 in order to avoid perfect lattices of the form L 8 (a 1 )):

lattice det pd mp L 8 (2, 3) 3 • 347 0 43 L 8 (2, 5) 7 • 167 0 40 L 8 (2, 6) 2 4 • 3 • 5 2 0 39 L 8 (2, 9) 3 3 • 43 0 40 L 8 (2, 10) 2 4 • 3 • 23 0 41 L 8 (3, 5) 2 2 • 3 2 • 5 • 7 0 37

Bounds for perfection

Every finite sequence showing d 1 = 9.

a 1 < a 2 < • • • < a k determines a maximal subset P(a 1 , . . . , a k ) of N such that L d (
Remark 2.6. Analogues of the above numbers and bounds exist of course also for most subsequent constructions.

Automorphisms and growth

The aim of this Section is to sketch a proof of the following result:

Theorem 2.7. The number of non-isomorphic perfect integral lattices of dimension d and minimum 4 grows faster than any polynomial in d.

The proof of Theorem 2.7 is based on Theorem 2.3 and gives an explicit lower bound on the number of perfect integral lattices of dimension d and minimum 4. This lower bound is unlikely to be sharp: The construction underlying Theorem 2.3 yields probably only a small fraction of all nonisomorphic integral perfect lattices with minimum 4. Moreover, the bounds in Theorem 2.3 are certainly far from optimal.

Two minimal vectors v, w

∈ (L d ) min are neighbours if v, w = 2. We call the real number γ(v) = 2(i+α)+β 2(d+1) ∈ (0, 1) the (normalized) center and δ(v) = 2α+β d+1 ∈ (0, 1] the (normalized) diameter of a minimal vector v = ±(e i -e i+α -e i+α+β + e i+2α+β ) in L d . We have δ(v) ≤ 2 min(γ(v), 1 -γ(v)). Lemma 2.8. The number of neighbours in L d of a minimal vector v in L d is given by 2d (min(γ(v), 1 -γ(v)) + 2 -δ(v)) + O(1) . (1)
Formula ( 1) is bounded above by 5d with asymptotic equality for γ(v) = Proof of Lemma 2.8 Neighbours of a minimal vector v ∈ min(L d ) are partitioned into 6 = 4 2 families according to their two common non-zero coefficients. We denote these families by

F * * 00 , F * 0 * 0 , F * 00 * , F 0 * * 0 , F 0 * 0 * , F 00 * *
where * stands for a common non-zero coefficient with respect to the obvious linear order i < i + α < i + α + β < i + 2α + β on the indices of the four coefficients of v = e ie i+αe i+α+β + e i+2α+β . Neighbours in F * 00 * or in F 0 * * 0 share the center with v and there are roughly d min(γ(v), 1γ(v)) possibilities for the remaining smallest nonzero coordinate in each of these families.

The number of neighbours in F * * 00 (or in F 00 * * ) is roughly given by dα and the number of neighbours in F * 0 * 0 (or in F 0 * 0 * ) is roughly given by dαβ.

All errors are bounded by an absolute constant (which is small). Summing over all families and using the definitions of the normalized center and diameter ends the proof.

2 Sketch of proof for Theorem 2.7 We partition neighbours of a minimal vector v into six families as in the proof of Lemma 2.8. An element u of such a family F ∈ {F * * 00 , F * 0 * 0 , F * 00 * , F 0 * * 0 , F 0 * 0 * , F 00 * * } is adjacent to all other elements of F except perhaps for two elements u ′ , u ′′ for which we have u, u ′ = u, u ′′ = -1. In F * 00 * and F 0 * * 0 there are no exceptions: two distinct elements of F * 00 * or of F 0 * * 0 are always adjacent. Families associated to complementary pairs of indices, like F * 00 * , F 0 * * 0 or F * * 00 , F 00 * * or the remaining two sets F 0 * 0 * , F * 0 * 0 are called complementary. Complementary sets are related by a natural involution ι defined by ι(u) = u ′ for u ∈ F and u ′ ∈ F such that u, u ′ = -2. Complementary sets have the same number of elements, given by d min(γ(v), 1γ(v)) + O(1) for F * 00 * or for F 0 * * 0 . The sets F * * 00 , F 00 * * associated to v = e ie i+αe i+α+β + e i+2α+β have d-α+O(1) elements and the sets F 0 * 0 * , F * 0 * 0 have d-α-β+O(1) elements. An element u ∈ F is orthogonal to every element v of the complementary pair F, except for ι(u) and perhaps at most two other elements in F . The behaviour is simpler in the complementary pair F * 00 * , F 0 * * 0 : every element u of F * 00 * is orthogonal to every element of F 0 * * 0 \ {ι(u)}.

These properties allow to reconstruct (at least approximately, however exact coordinates can be found) the coordinates, up to the obvious symmetry e i -→ e d+3-i , of a minimal element v from the knowledge of all scalar products between elements of (L d ) min . This shows that the lattice L d has at most four automorphisms: ±1, perhaps followed by reversal of all coordinates. The same holds for the lattices L d (a 1 , . . . , a k ): Knowledge of all scalar products between the set (L d (a 1 , . . . , a k )) min of minimal elements determines, up to signs and global reversal of all coordinates, the coefficients (and thus also the missing integers a 1 , . . . , a k ). In particular, all lattices L d (a 1 , . . . , a k ) have at most four automorphisms. In the generic case, only the two trivial automorphisms ±1 occur. Thus the number of different lattices L d (a 1 , . . . , a k ) of large dimension d is at least equal to

1 2 d+2+k k ≥ d k 2•k! . Since k is
c d =    0 if d ≡ 0 (mod 3), 4 if d ≡ 1 (mod 3), 2 if d ≡ 2 (mod 3).
The lattice O d is perfect for d ≥ 8.

The lattice O 7 (with 29 pairs of minimal vectors) has perfection default 1 and is thus not perfect. Proof of Theorem 3.1 The squared Euclidean norm of (1, 3, 5, . . . , 2d + 1) is polynomial of degree 3 in d and the formula for the determinant of O d (given by 1 2 + 3 2 + 5 2 + • • • + (2d + 1) 2 ) can thus be checked using 4 values.

The lattice O d cannot contain roots and its minimum is obviously 4 (realized e.g. by the vector (1, -1, -1, 1, 0, 0, . . . )) if d ≥ 3. The number of pairs of minimal vectors are polynomial functions of degree 3 for d in arithmetic progressions of length 6. Computation of small examples gives enumerative formulae.

For proving perfection we use Proposition 1.

         1 1 1 0 -1 0 0 0 1 1 0 1 0 -1 0 0 1 1 0 0 1 0 -1 0 1 0 1 1 0 0 -1 0 1 1 0 0 0 1 0 -1 1 0 1 0 1 0 0 -1 0 1 1 1 0 0 0 -1          
of O 7 are linearly independent and span thus the full 7-dimensional vector space orthogonal to (1, 3, 5, 7, 9, 11, 13, 15). The union of these vectors (extended to elements of Z d+1 by appending zeros) with vectors

(1, 1, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, 0, . . . )

(1, 1, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, 0, . . . )

(1, 1, 0, 0, 0, 0, 0, 0, 1, 0, -1, 0, 0, 0, . . . ) . . .

is a basis of the d-dimensional vector space O d ⊗ Z R = (1, 3, . . . , 2d + 1) ⊥ . 2
For a finite increasing sequence 1 ≤ a 1 < a 2 < • • • < a k of k odd natural integers, we denote by O d (a 1 , . . . , a k ) ⊂ Z d+1 the d-dimensional lattice of all integral vectors orthogonal to (1, 3, . . . , a 1 -2, a 1 , a 1 + 2, . . . , a k -2, a k , a k + 2, . . . , 2(d + k) + 1) (elements a k carrying a magical hat are removed) with increasing coefficients given by the d+1 smallest elements of {1, 3, 5, 7, . . . }\ {a 1 , . . . , a k }.

The following analogue of Theorem 2.3 holds:

Theorem 3.2. Given a strictly increasing sequence 1 ≤ a 1 < a 2 < • • • < a k of k odd natural integers, the d-dimensional lattice O d (a 1 , . . . , a k ) is perfect for d ≥ max(10(k + 1) 3 + 5, 22(k + 1) + 2).
Proof We apply again Proposition 1.2. Since O d (a 1 , . . . , a k ) contains the lattice L d-1 ((a 1 + 1)/2, (a 2 + 1)/2, . . . , (a k + 1)/2)) defined by all elements of O d (a 1 , . . . , a k ) which are orthogonal to (1, 1, . . . , 1) and to 1 2 ((1, 1, . . . , 1) + (1, 3, 5, . . . , a 1 , . . . )), we suppose d large enough in order to ensure perfection of the sublattice L d-1 ((a+1)/2, (a 2 +1)/2, . . . , (a k +1)/2)) (which can be done using Theorem 2.3). We show now that minimal vectors e 2a+1 + e 2b+1 + e 2c+1e 2l+1 (with indices in {1, 3, 5, . . . }\{a 1 , . . . , a k }) of O d (a 1 , . . . , a k ) corresponding to sums 2l +1 = 2a+1+2b+1+2c+1 with 2l +1, 2a+1, 2b+1, 2c+1 ∈ {a 1 , . . . , a k }) span the d-dimensional vector space orthogonal to (1, 3, . . . , a 1 -2, a 1 , a 1 + 2, . . . , a k -2, a k , a k + 2, . . . , 2(d + k) + 1). This is done in two steps. First we show that for every possible index 2l+1 ≥ 12(k+1)+1 occurring in elements of O d (a 1 , . . . , a k ) there exists a minimal vector e 2a+1 +e 2b+1 +e 2c+1 -e 2l+1 in O d (a 1 , . . . , a k ). The second step deals with the remaining vectors involving only small indices.

Every even integer 2m ≥ 4(k + 1) can be written in ⌊m/2⌋ ≥ k + 1 different ways as a sum of two odd natural numbers. For any odd integer 2l + 1 ≥ 12(k + 1) + 1 there exist thus three distinct odd natural numbers 2a+1, 2b+1, 2c+1 ∈ {a 1 , . . . , a k } with 2a+1, 2b+1 < 2c+1 and 2c+1 ∈ {2l+ 1-6(k+1), 2l+1-4(k+1)} such that 2l+1 = 2a+1+2b+1+2c+1: Indeed, we start by choosing an odd integer 2c + 1 ∈ {2l + 1 -6(k + 1), 2l + 1 -4(k + 1)}\{a 1 , . . . , a k }. The even integer 2l + 1-(2c+ 1) ∈ {4(k + 1), . . . , 6(k + 1)} can now be written as a sum of two distinct odd integers 2a + 1, 2b + 1 not in {a 1 , . . . , a k }. Since 2l + 1 ≥ 12(k + 1) + 1, we have 2c + 1 > 2l+1 2 and thus all three integers 2a + 1, 2b + 1, 2c + 1 ∈ {1, 3, 5, . . . , } \ {a 1 , . . . , a k } are distinct. This completes the proof of the first step.

We end now the proof by showing that the span of minimal vectors as above (i.e. of the form e 2a+1 + e 2b+1 + e 2c+1e 2l+1 ) with 2l + 1 ≥ 12(k + 1) + 1 contains the vector space V of all vectors which are orthogonal to (1, 3, . . . , a 1 , . . . ) and which involve only non-zero coefficients with indices ≤ A = max(6(k + 1) 3 + 3, 14(k + 1) + 1). We have 2a + 1 + 2b + 1 ≤ 2A -2 for two distinct odd integers a, b ≤ A. There exists thus an odd integer 2c + 1 ∈ {A+3, . . . , A+2(k+1)+3} such that 2c+1 and 2l+1 = 2a+1+2b+1+2c+1 ≤ 3A + 2(k + 1) + 1 ≤ max(20(k + 1) 3 + 10, 44(k + 1) + 4) ≤ 2d + 1 are different from a 1 , . . . , a k . Given four distinct odd integers 2a + 1, 2b + 1, 2α + 1, 2β + 1 in {1, 3, . . . , A} \ {a 1 , a 2 , . . . , a k } such that 2a + 1 + 2b + 1 = 2α + 1 + 2β + 1, we can consider the vector Since the vector space orthogonal to (1, 3, . . . , â1 , . . . ) involving no indices exceeding A is at least of dimension

A -1 2 -k -1 ≥ 6(k + 1) 3 + 2 2 -k -1 ≥ 2(k + 1)
(1) 2 • 3 • 5 • 59 2 59 O 9 (3) 2 • 881 0 56 O 9 (5) 2 • 3 2 • 97 0 56 O 9 (7) 2 • 3 • 7 • 41 0 56 O 9 (9) 2 • 5 • 13 2 0 57 O 9 (11) 2 • 3 • 5 2 • 11 0 58 O 9 (13) 2 • 3 2 • 89 0 59 O 9 (15) 2 • 773 0 60 O 9 (17) 2 • 3 • 13 • 19 0 62 O 9 (19) 2 • 3 • 5 • 47 0 64
The lattice O 10 (1) (with determinant 11 2 •19 and 81 pairs of minimal vectors) is perfect.

The even-sublattice construction

The even-sublattice construction is defined as the d-dimensional lattice M d consisting of all integral vectors (x 0 , . . . , x d ) ∈ Z d+1 which are orthogonal to (0, 1, 2, . . . , d) and have even coordinate-sum d i=0 x i ≡ 0 (mod 2). Its minimal vectors are (2, 0, 0, . . . ), vectors ± (e ie i+αe i+α+β + e i+2α+β ) with i ∈ {0, . . . , d} and α, β ≥ 1 such that i+2α+β ≤ d together with vectors ± (e h + e i + e je k ) where h, i, j, k are four distinct integers in {0, . . . , d} such that h + i + j = k. The lattice M d is perfect for d ≥ 8.

The vector space v∈(M 7 ) min R v⊗v associated to the 34 pairs of minimal vectors in M 7 is of dimension 27. The lattice M 7 with perfection-default 28 -27 = 1 is thus not perfect. Proof of Theorem 4.1 M d contains L d-1 as a sublattice. Since d ≥ 8, the lattice L d-1 is perfect by Theorem 2.1. Hence Proposition 1.2 shows that it is enough to prove that minimal vectors with non-zero coordinate-sum span the full d-dimensional space M d ⊗ Z R = (0, 1, 2, . . . , d) ⊥ ⊂ R d+1 . This holds for d ≥ 5 by linear independency of the five rows

2 0 0 0 0 0 -1 -1 -1 1 0 0 -1 -1 0 -1 1 0 -1 -1 0 0 -1 1 -1 0 -1 -1 0 1
(with a suitable number of additional zero-coordinates) together with minimal elements of the form -e 0e 1e i-1 + e i for i = 6, 7, . . . , d.

2 For a strictly increasing sequence 0 ≤ a 1 < a 2 < • • • < a k of k natural integers, we denote by M d (a 1 , . . . , a k ) the d-dimensional lattice of all integral vectors with even coordinate-sum which are orthogonal to (0, 1, . . . , a 1 -1, a 1 , a 1 + 1, . . . , a k -1, a k , a k + 1, . . . , d + k) ∈ Z d+1 .

The following analogue of Theorem 4.1 holds:

Theorem 4.2. Given a finite strictly increasing sequence

0 ≤ a 1 < a 2 < • • • < a k of k natural integers, the d-dimensional lattice M d (a 1 , . . . , a k ) is perfect for d large enough.
The proof, similar to the proof of Theorem 3.2, is left to the reader. A few data with pd indicating the perfection default and with mp indicating the number of minimal pairs in lattices M 8 (i) are

lattice det pd mp M 8 (0) 2 2 • 3 • 5 • 19 1 41 M 8 (1) 2 4 • 71 1 42 M 8 (2) 2 2 • 281 1 42 M 8 (3) 2 4 • 3 • 23 0 42 M 8 (4) 2 2 • 269 3 44 M 8 (5) 2 4 • 5 • 13 2 44 M 8 (6) 2 2 • 3 • 83 0 45 M 8 (7) 2 4 • 59 0 47 M 8 (8) 2 2 • 13 • 17 1 49
For the lattices M 9 (i) the data are

lattice det pd mp M 9 (0) 2 2 • 5 • 7 • 11 0 61 M 9 (1) 2 9 • 3 0 61 M 9 (2) 2 2 • 3 • 127 0 62 M 9 (3) 2 5 • 47 0 61 M 9 (4) 2 2 • 3 2 • 41 0 64 M 9 (5) 2 5 • 3 2 • 5 1 64 M 9 (6) 2 2 • 349 0 65 M 9 (7) 2 6 • 3 • 7 0 66 M 9 (8) 2 2 • 3 • 107 0 69 M 9 (9)
2 6 • 19 0 70

A construction using finite abelian groups

To a finite abelian group A indexing the coordinates of Z A we associate the integral lattice L(A) consisting of all elements v = (v a ) a∈A ∈ Z A such that a∈A v a = 0 ∈ Z and a∈A v a a = 0 ∈ A (i.e. vectors v ∈ Z A of coefficient-sum zero such that the element a v a a of A is the identity 0 of the finite additive group A). Equivalently, L(A) is the set of all elements in the kernel of the augmentation ideal in the group-algebra Z[A] of A over Z. The lattice L(A) is even and without roots. It has rank |A| -1 and determinant |A| 3 . The semidirect product Aut(A) ⋉ A acts isometrically on L(A) in the obvious way. Vectors of norm 4 in L(A) determine the group A uniquely as follows: An arbitrary index of a basis element can be chosen as the identity 0 of A. A vector e 0e ae b + e c yields the identity a + b = c in A.

The number of pairs of minimal vectors of norm 4 in L(A) is given by the following result:

Proposition 5.1. The number of pairs or vectors of norm 4 in L(A) is given by

|A| 1 - 1 2 c |A|/2 2 + |A| 2 c (|A| -2 c ) /2 2
where c is the minimal number of generators of the 2-torsion subgroup in A. Equivalently, c is the largest integer such that A contains a subgroup isomorphic to the c-dimensional vector space F c 2 over the field F 2 of two elements.

Proof We count for each element a of A the number N a of solutions of the equation x + y = a with x, y two different elements in A. The total number of pairs of vectors of norm 4 in L(A) is then given by a∈A Na/2 2 since such pairs are given by ± (e x 1 + e y 1 -(e x 2 + e y 2 )) with {x 1 , y 1 } = {x 2 , y 2 } such that we have the equality

x 1 + y 1 = x 2 + y 2 in A.
The kernel of the endomorphism of A defined by x -→ 2x is an F 2 -vector space of dimension c. We denote by 2A its image (of size Remark 5.2. The algebraic identity

|A| 1 - 1 2 c |A|/2 + |A| 2 c (|A| -2 c ) /2 = |A| 2
encodes the fact that A contains |A| 2 pairs of distinct elements.

Theorem 5.3. The lattice L(A) associated to an abelian group having at least 9 elements is perfect.

Some lattices L(A) associated to abelian groups A with less than 9 elements are perfect. The lattice L((Z/4Z) ⊕ (Z/2Z)) is however not perfect (the other two abelian groups with 8 elements and the cyclic group with 7 elements give rise to perfect lattices, see Sections 5.2.2 and 5.2.1).

Given a subset A of a finite abelian group A, we define the lattice L(A) as the sublattice of L(A) generated by all vectors of L(A) involving no elements of A \ A.

We have the following generalization of Theorem 5.3:

Theorem 5.4. For a fixed integer k there are only finitely many isomorphism classes of pairs (A ⊂ A) where A is a finite abelian group and where A is a subset of A with A \ A containing at most k elements such that L(A) is not perfect.

Proofs

v N -3 = e 0 + e N -4 -e N -3 -e N -1 , v N -2 = e 0 + e N -3 -e N -2 -e N -1
defining the rows of the (N -3) × N matrix

M =          1 1 -1 0 0 0 0 0 0 -1 1 0 1 -1 0 0 0 0 0 -1 1 0 0 1 -1 0 0 0 0 -1 . . . . . . . . . . . . 1 0 0 0 0 0 1 -1 0 -1 1 0 0 0 0 0 0 1 -1 -1         
which has obviously rank N -3 (column indices are the representatives 0, 1, . . . , N -1 of Z/N Z). It is easy to check that M (acting on row-vectors) has a kernel spanned by the all one vector (1, 1, . . . , 1, 1) ∈ Z N and by the two elements w 1 = (1, 0, 0, 0, 0, . . . , 0, 0, 0, 1),

w 2 = (1, 2, 3, . . . , N -2, N -1, 0)
of Z N . We consider now two additional minimal vectors with signed indexsum N given by

v 0 = e 0 + e 1 -e 3 -e N -2 , v 1 = e 1 + e 2 -e 4 -e N -1 . Since w 1 , v 0 w 1 , v 1 w 2 , v 0 w 2 , v 1 = 1 -1 1 -N 0 is invertible, the vectors v 0 , . . . , v N -1 are linearly independent.
In the general case we have to show that linear combinations of rank 1 matrices with coefficients v a v b , a, b ∈ A for v = (v a ) a∈A ∈ L(A) min have arbitrary off-diagonal coefficients. Let (a, b) be the index of such an offdiagonal coefficient. By translation-invariance we can suppose a = 0. If b is contained in a cyclic group of order ≥ 7 we are in the previous case. We can thus assume that the cardinality of A is divisible only by primes ≤ 5.

If 5 and either 2 or 3 divide the cardinality of A, then every non-zero element of A is contained in a cyclic subgroup of order at least 10 and we are done. Otherwise, a non-trivial element of A is either contained in a cyclic group of order 25 (and we are done) or in (Z/5Z) ⊕ (Z/5Z) and L ((Z/5Z) ⊕ (Z/5Z)) is perfect by a direct computation (using a Computer-Algebra system).

We are left with the remaining cases where every cyclic subgroup containing b is of order 2, 3, 4 or 6. If b is only contained in a cyclic group of order 2, the result follows from perfection of the two groups L((Z/2Z) ⊕ (Z/2Z) ⊕ (Z/2Z)) and L((Z/2Z) ⊕ (Z/8Z). If b is only contained in a cyclic group of order 3, the result follows from perfection of L((Z/3Z)⊕(Z/3Z)). If b is contained in a cyclic group of order 6, the result follows from perfection of L((Z/6Z) ⊕ (Z/2Z)) and L((Z/6Z) ⊕ (Z/3Z)). 2

Proposition 5.5.

If N is large enough then L(Z/N Z \ {a 1 , . . . , a k }) is per- fect for every subset {a 1 , . . . , a k } of k elements in Z/N Z. Proof L(Z/N Z \ {a 1 , . . . , a k }) contains the lattice L N -k-2 (a 1 + 1, . . . , a k + 1)
as a sublattice (we represent elements of Z/N Z by natural integers in {0, . . . , N -1}) and this sublattice is perfect for N ≥ max(9 + k, 2(k + 1) 3 + k + 1) by Theorem 2.3. It is thus enough to show that minimal vectors with signed indices summing up to N generate the whole vectorspace L(Z/N Z \ {a 1 , . . . , a k }) ⊗ Z R. This can be done (with an effective lower bound on N ) as in the proof of Theorem 3.2. 2

Proposition 5.6. There exists an integer N = N k such that L(A) is perfect if the finite abelian group A containing A has an element of prime-order at least N and if A \ A has at most k elements.

Proof We identify tensor products v ⊗ v defined by elements v in L(A) with symmetric matrices whose rows and columns are indexed by A. It is enough to show that all such matrices with exactly two non-zero diagonal entries and two off-diagonal non-zero entries defining a symmetric submatrix of the form -1 1 1 -1 are sums of symmetric matrices associated to minimal elements in L(A). Up to a translation (of A and all indices) we can assume that the first diagonal entry is associated to the trivial element 0 in A. The second diagonal element is then associated to a certain non-zero element b ∈ A contained in a cyclic group of order at least N and we are done by Proposition 5.5. 2. Proof of Theorem 5.4 As in the proof of Proposition 5.6 we want to realize a symmetric matrix corresponding to -e 0 ⊗ e 0 + e 0 ⊗ e b + e b ⊗ e 0e b ⊗ e b (up to a suitable translation), perhaps modulo diagonal matrices. In particular, we can suppose that A contains the trivial element 0. Proposition 5.5 shows that we can assume that every cyclic group containing b is small. The group A (if it is huge) has then a huge number of distinct subgroups. In particular, we can suppose that it contains a non-trivial translate b + B = B of a group B containing a with L(B) perfect (this is the case if B has at least 9 elements by Theorem 5.3). We may now consider the symmetric matrix P associated to the tensor-product

v 1 ⊗ v 1 + v 2 ⊗ v 2 + • • • + v α ⊗ v α
where α is the order of a and where v i = e 0e a + e b+(i+1)ae b+ia for i = 1, . . . , α. We have P 0,a = P a,0 = α and all other non-zero coefficients of P are either diagonal or have both indices in b + B. Coefficients of the last form can be killed using perfection of L(B).

2

Remark 5.7. Our proof of Theorem 5.4 can be unravelled in order to yield effective bounds on the size of A.

Examples

There are no interesting examples in dimension < 6.

Dimension 6

The 6-dimensional lattice L(Z/7Z) associated to the unique group with seven elements has 21 pairs of minimal elements and is perfect. A basis is given by the six rows of

A =         0 1 -1 0 0 -1 1 0 1 0 -1 -1 0 1 1 1 0 -1 0 -1 0 0 1 -1 0 -1 1 0 0 1 -1 -1 1 0 0 1 0 -1 0 -1 0 1        
(with columns indexed by the representatives 0, 1, 2, 3, 4, 5, 6 of Z/7Z). Its Gram matrix is the matrix

P 5 6 =         4 2 2 1 2 2 2 4 2 2 1 2 2 2 4 0 2 1 1 2 0 4 1 2 2 1 2 1 4 0 2 2 1 2 0 4        
at page 381 in Chapter XIV of [START_REF] Martinet | Les réseaux parfaits des espaces euclidiens[END_REF].

Dimension 7

There are 3 groups with 8 elements.

For the cyclic group Z/8Z we get

8 2 4 2 + 4 3 2 = 36
pairs of minimal vectors in the associated 7-dimensional lattice L(Z/8Z) which is perfect and has a basis given by the seven rows of the matrix

A =           0 0 1 -1 0 -1 1 0 0 -1 1 0 0 0 1 -1 1 0 1 -1 0 0 0 -1 0 -1 1 0 1 -1 0 0 0 0 -1 -1 0 0 1 1 -1 0 0 1 1 0 0 -1 1 1 0 0 -1 -1 0 0          
with associated Gram matrix AA t the matrix

P 5 7 =           4 2 2 2 1 -1 1 2 4 2 2 -1 1 -1 2 2 4 1 -1 -1 1 2 2 1 4 -1 1 -1 1 -1 -1 -1 4 -2 0 -1 1 -1 1 -2 4 -2 1 -1 1 -1 0 -2 4          
of page 382 in [START_REF] Martinet | Les réseaux parfaits des espaces euclidiens[END_REF].

The lattice L((Z/4Z) ⊕ (Z/2Z)) (with 38 pairs of minimal vectors) has perfection-default 2 and is thus not perfect.

The lattice L((Z/2) ⊕ (Z/2Z) ⊕ (Z/2Z)) = L(F 3 2 ) with 42 pairs of minimal vectors has a basis given by the seven last rows of the table 000 001 010 011 100 101 110 111

0 0 1 -1 1 -1 0 0 -1 1 0 0 1 -1 0 0 0 1 1 0 0 -1 -1 0 0 0 1 -1 0 0 -1 1 -1 0 1 0 1 0 -1 0 0 1 0 -1 1 0 -1 0 0 0 0 0 1 -1 -1 1
(with the first row showing all elements of F 3 2 corresponding to columnindices). The associated Gram matrix has only even entries. Dividing it by 2 we get the matrix

P 4 7 =           2 1 1 1 1 1 1 1 2 1 0 1 1 1 1 1 2 1 1 1 1 1 0 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2          
(see page 382 in [START_REF] Martinet | Les réseaux parfaits des espaces euclidiens[END_REF]) defining the root lattice D 7 .

Remark 5.8. Even parity of all scalar products between minimal vectors fails for the lattices L(F k 2 ) with k ≥ 4.

Dimension 8

Both 8-dimensional lattices L(Z/9Z) and L((Z/3Z) ⊕ (Z/3Z)) have 54 pairs of minimal vectors and are perfect. They are non-isomorphic: Every pair of minimal vectors is orthogonal to exactly 15 pairs of minimal vectors in L(Z/9Z) and every such pair is orthogonal to exactly 9 pairs of minimal vectors in L((Z/3Z) ⊕ (Z/3Z)).

Examples with one missing element

The obvious action of A on itself shows that all the lattices L(A) are isomorphic if A is obtained by removing a unique element from A. The lattice

L(A \ {0}) has |A| 1 - 1 2 c |A|/2 -1 2 + |A| -2 c 2 c (|A| -2 c ) /2 -1 2 + (|A| -2 c ) /2 2
pairs of minimal vectors with norm 4 (where c denotes the dimension of the maximal F 2 -vector space occurring as a subgroup in A).

The root lattice A 6

Working with the set A = {001, 010, 011, 100, 101, 110, 111} of all seven nonzero elements in F 3 2 we get the perfect rescaled root lattice A 6 generated by the last seven rows (with the first row indicating the index-set A) of 001 010 011 100 101 110 111

0 0 0 1 1 -1 -1 0 1 1 0 0 -1 -1 -1 0 1 1 0 -1 0 -1 1 0 0 1 -1 0 -1 1 0 1 0 0 -1 -1 0 1 0 1 0 -1
Identifying the seven elements of A in the obvious way with the seven points of the Fano plane (projective plane over F 2 ) we can consider pairs of minimal vectors of L(A) (i.e. pairs of opposite roots of A 6 ) as projective lines endowed with marked points (or, dually, as points together with incident lines) as follows: The two coordinates corresponding to coefficients 1 and the two coordinates corresponding to coefficients -1 of a minimal vector define projective lines which meet at a point on the projective line associated to the three coordinates corresponding to coefficients 0. Up to multiplication by -1, this construction is one-to-one and yields the 21 = 7 × 3 pairs of roots of A 6 . The Gram matrix associated to the basis of L(A) given above is twice the matrix

P 7 6 =         2 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 2        
(which is the Gram matrix with respect to the basis e 0e 1 , . . . , e 0e 6 of A 6 ) in Chapter XIV of [START_REF] Martinet | Les réseaux parfaits des espaces euclidiens[END_REF].

Two perfect examples of dimension 7

Working with A = {1, . . . , 8} ⊂ Z/9Z, we get a perfect 7-dimensional lattice L(A) with 30 pairs of minimal vectors. A basis is given by the seven rows of the matrix

A =           1 0 1 0 -1 0 0 -1 0 -1 1 1 -1 0 0 0 0 -1 1 0 0 0 1 -1 1 0 0 1 0 -1 0 -1 1 -1 0 0 0 -1 1 0 0 1 1 0 0 -1 0 -1 0 0 0 1 -1 -1 1 0          
(with column-indices representing 1, . . . , 8 ∈ Z/9Z) with associated Gram matrix AA t given by the matrix

P 28 7 =           4 2 2 2 1 2 1 2 4 2 1 1 0 2 2 2 4 1 2 1 1 2 1 1 4 2 2 2 1 1 2 2 4 0 2 2 0 1 2 0 4 1 1 2 1 2 2 1 4          
(with determinant 2 3 • 3 4 ) of Chapter XIV in [START_REF] Martinet | Les réseaux parfaits des espaces euclidiens[END_REF].

The last seven rows of the table 01 02 10 11 12 20 21 22

1 -1 1 0 -1 0 0 0 1 0 1 0 0 -1 -1 0 0 0 1 -1 0 0 -1 1 1 0 0 -1 -1 0 0 1 1 -1 0 0 0 0 -1 1 0 0 1 0 -1 -1 0 1 0 0 0 -1 1 -1 0 1
(the first row displays the column indices αβ with (α, β) ∈ (Z/3Z) 2 \ {0, 0}) define the perfect 7-dimensional lattice L ((Z/3Z) + (Z/3Z) \ {0, 0}) with 30 pairs of minimal vectors. Its Gram matrix is

P 27 7 =           4 2 1 2 2 2 -1 2 4 2 1 2 2 1 1 2 4 2 2 2 2 2 1 2 4 2 2 1 2 2 2 2 4 1 1 2 2 2 2 1 4 1 -1 1 2 1 1 1 4          
in Chapter XIV of [START_REF] Martinet | Les réseaux parfaits des espaces euclidiens[END_REF].

6 The even sublattice construction for abelian groups

Given a finite abelian group A indexing the coordinates of Z A , we denote by M (A/(±1)) the even sublattice of Z A/(±1) consisting of all elements v = (v a ) a∈A/(±a) such that a∈A/(±1) v a ≡ 0 (mod 2) (this ensures evenness of M (A/(±1)) and such that a∈A/(±1) v a a = 0 ∈ A where A/(±1) denotes (somewhat abusively) a set of representatives of A under the involutive automorphism a -→ -a. Theorem 6.1. The lattice M ((Z/N Z)/(±1)) associated to a cyclic group of order ≥ 15 is perfect.

Theorem 6.1 can probably be generalized to arbitrary finite abelian groups which are sufficiently large. It should have a further generalization obtained by removing k elements from A/(±1). Proof of Theorem 6.1 We consider first a cyclic group A = Z/N Z of even order N = 2m. Representatives of A/(±1) are {0, 1, . . . , m}. For N ≥ 16, the lattice M (A/(±1)) contains the perfect sublattice M m-1 = M (A/(±1)) ∩ (0, 1, 2, . . . , m) ⊥ , see Theorem 4.1.

We set v i = -e i + e i+1 + e m-1 + e m for i = 0, . . . , m -3. The minimal elements v 0 , . . . , v m-3 together with 2e 0 = (e 0 +e 1 +e m-1 +e m )-(-e 0 +e 1 + e m-1 + e m ), 2e m and e 1 + e 2 + e m-2 + e m-1 are linearly independent. Since the corresponding signed index-sum -i + i + (m -1) + m = 2m (respectively 0 + 1 + (m -1) + m = 2m and 2m) is non-zero they are not orthogonal to (0, 1, 2, . . . , m). Perfection of M ((Z/N Z)/(±1)) for even N ≥ 16 follows now from Proposition 1.2.

For a cyclic group N = 2m+1 of odd order 2m+1 we proceed as follows: The m-3 linearly independent minimal elements -e i +e i+2 +e m-1 +e m , i = 0, . . . , m -4 can be completed to a base by adjoining the following four elements u 1 = (1, 0, 1, 0, 1, 0, 1, 0, . . . , 0, 0)

u 2 = (1, 1, 1, 1, . . . , 1, 1, 0, 0) u 3 = (0, 1, 2, 3, 4, 5, . . . , m -3, m -2, -1, -1)
u 4 = (0, 0, 0, 0, 0, . . . , 0, 0, 0, 1, -1) (u 1 has alternating coefficients 0, 1 except for the last two coefficients which are both zero) which are orthogonal to -e i + e i+2 + e m-1 + e m for i ∈ {0, . . . , m -4}. We consider now four minimal vectors given by The matrix S of scalar products S i,j = w i , u j equals

    2 2 0 0 1 + ǫ 3 m -1 2 + ǫ 3 m + 1 1 3 + ǫ 3 m + 1 1    
where ǫ = 0 if m is odd and ǫ = 1 if m is even. The matrix S has non-zero determinant 8m + 4 which ends the proof by Proposition 1.2. 2

6.1 A non-cyclic example giving E 8

All elements of the additive group F 3 2 are their own inverses and M ((F 2 ) 3 )/(±1)) is obtained from the lattice L(F 3 2 ) by considering L(F 3 2 ) + (2Z) F 3 2 . The resulting lattice is the (rescaled) exceptional root-lattice E 8 with basis the last eight rows of 000 001 010 011 100 101 110 111

2 0 0 0 0 0 0 0 -1 -1 -1 -1 0 0 0 0 0 2 0 0 0 0 0 0 0 -1 1 0 -1 0 0 -1 0 0 0 0 1 -1 1 1 0 0 0 0 0 2 0 0 0 0 0 0 -1 -1 -1 1 0 0 -1 1 0 0 -1 -1 having twice the Dynkin matrix             2 -1 0 0 0 0 0 0 -1 2 -1 0 0 0 0 0 0 -1 2 -1 0 0 0 0 0 0 -1 2 -1 0 0 0 0 0 0 -1 2 -1 0 -1 0 0 0 0 -1 2 -1 0 0 0 0 0 0 -1 2 0 0 0 0 0 -1 0 0 2            
of E 8 as its Gram matrix .

Removing an element

(One can in fact remove an arbitrary element from F 3 2 .) The even lattice associated to all 7 non-zero elements F 3 2 \ {0} of F 3 2 is the lattice generated by the seven vectors 001 010 011 100 101 110 111 0

0 0 1 1 1 -1 0 0 0 2 0 0 0 1 0 1 1 0 1 0 0 0 0 1 1 -1 -1 0 0 0 1 1 1 1 0 1 1 1 1 0 0 0 -1 1 1 1 0 0.
pairs of vectors of norm 3. It is perfect for c ≥ 3.

Proof The lattice T (F c 2 ) is the kernel of the augmentation-map. It is thus of index 2 c in Z 2 c -1 and has determinant (2 c ) 2 = 4 c . There are (2 c -1)(2 c -2)

3•2 = 1 3 2 c -1 2
projective lines in F c 2 \ {0} and every projective line determines 4 pairs of minimal vectors.

In order to prove perfection, we consider a symmetric matrix S with 2 c -1 rows and columns indexed by all non-zero elements of F c The construction cannot be adapted to other finite abelian groups (with F c 2 \ {0} replaced by representatives of all non-zero orbits of a finite abelian group A under the automorphism x -→ -x) without losing perfection.

7.1 Digression: The equiangular system of the perfect lattice T (F 3 2 ) and the Schläfli graph

Generalizations

All lattices constructed in this paper are of the form Λ = ker(ϕ(Z d+a )) for a surjective morphism ϕ from Z d+a onto an abelian group Z a ⊕ A with A finite. A suitable choice of ϕ ensures nice combinatorial properties of small elements in Λ. Up to this point (except in Section 7), we have worked with even lattices containing no roots and we have used properties of ϕ for proving perfection of the set Λ 4 of minimal vectors in Λ. It is of course tempting to consider ϕ such that the norm λ 2 1 + • • • + λ 2 d+a of every nonzero element (λ 1 , . . . , λ d+a ) ∈ Λ is at least equal to some larger integer m > 4. Sidon sets provide examples leading to minimum 6 (but do not ensure perfection) as follows: A Sidon set in an additive group A is a subset S such that x 1 + y 1 = x 2 + y 2 implies {x 1 , y 1 } = {x 2 , y 2 } as multisets for x 1 , y 1 , x 2 , y 2 ∈ S. The sublattice of all elements in Z S with zero coefficientsum x∈S λ x = 0 such that x∈S λ x x = 0 ∈ A is then even and without roots or vectors of norm 4. More generally, one might consider subsets S which have the m-lattice Sidon property: every non-zero vector in the lattice of all elements in Z S with zero coefficient-sum x∈S λ x = 0 such that x∈S λ x x = 0 ∈ A has (squared Euclidean) norm at least 2(m + 1). As a variation, one can drop the requirement x∈S λ x = 0 by replacing it with the evenness condition x∈S λ x ≡ 0 (mod 2) or by dropping it without any other requirement altogether (this puts of course an even stronger constraint on S).

Craig lattices

Given a finite field F q with q = p e a prime power and an integer k, we can consider the lattice C q-1,k defined by all vectors of Z Fq with zero coefficient sum x∈Fq λ x = 0 and such that x∈Fq λ x x i = 0 ∈ F q for i = 1, . . . , k (equality holds of course also for i = 0). For q = p a prime number, the lattice C q-1,k is a Craig lattice. The lattice C q-1,k is even and has determinant q 2k+1 . Proposition 8.1. The lattice C q-1,k has minimum ≥ 2k + 2 if k is smaller than the characteristic p of F q .

Proof Symmetric power-sums of degree up to p -1 define elementary symmetric polynomials of degree up to p -1. A minimal vector with strictly positive coefficients of indices a 1 , . . . , a l (with indices repeated according to the value of the associated integral coefficient) and strictly negative coefficients of indices b 1 , . . . , b l gives rise to two polynomials l i=1 (xa i ) and l i=1 (xb i ). Since symmetric power-sums of degree up to p -1 define elementary symmetric polynomials of degree up to p -1 this implies either of l > k or k ≥ p.

2

  i,j = b i , b j ) a Gram matrix defined by scalar products between basis elements b 1 , . . . , b d of the d-dimensional lattice Λ = ⊕ d i=1 Zb i . The density min(Λ) d 2 d det(Λ) π d/2 (d/2)! of a d-dimensional lattice Λ is the density of the associated sphere-packing obtained by packing the space Λ⊗ Z R with spheres of equal radius min(Λ)/2 (and delimiting balls of volume √ min(Λ) 2 d π d/2

e 1 -

 1 e 1+αe i + e ω ) + (e 1+αe 1+2αe i + e ω ) + • • • + (e 1+(β-1)αe 1+βαe i + e ω ) -(e 1e 1+βe ψ + e ω ) -(e 1+βe 1+2βe ψ + e ω ) -• • • -(e 1+(α-1)βe 1+αβe ψ + e ω ) = -βe i + αe ψ + (βα)e ω which ends the proof.

1 2

 1 and δ(v) = 0 and bounded below by 3d with asymptotic equality for γ(v) =1 2 and δ(v) = 1.

  2 with H = (1, 1, 1, . . . , 1) ⊥ ⊂ R d+1 . The inclusion of L d-1 = H ∩ O d in O d and perfection of L ≥7 (see Theorem 2.1) implies that it is enough to show that minimal vectors with non-zero coordinate-sum span a d-dimensional vector space. As already mentioned, such minimal elements are of the form ±(e a + e b + e ce k ) with (2a -1) + (2b -1) + (2c -1) = (2k -1) for four distinct elements a, b, c, k in {1, . . . , d + 1}. The seven minimal vectors given by the rows of 

(

  e 2a+1 + e 2b+1 + e 2c+1e 2(a+b+c)+3 ) -(e 2α+1 + e 2β+1 + e 2c+1e 2(a+b+c)+3 ) = e 2a+1e 2α+1e 2β+1 + e 2b+1 .

Theorem 4 . 1 .

 41 The lattice M d has determinant 2 3 d(d + 1)(2d + 1) and minimum 4. It has 1 36 4d 3 -3d 2 -6d + c d pairs of minimal vectors of norm 4 where c d depends only on d (mod 6) and is given by d (

|A| 2 c

 2 ) in A. For an element a ∈ A \ (2A) there are N a = |A| solutions to the equation x + y = a with x = y and there are |A| 1 -1 2 c elements in A \ (2A). If a is one of the |A| 2 c elements in 2A, there are 2 c solutions of 2x = a and the equation x + y = a has thus only N a = |A| -2 c solutions with x different from y. 2

Proof of Theorem 5. 3

 3 We establish Theorem 5.3 first for cyclic groups. It holds for A = Z/7Z and A = Z/8Z by a direct computation left to the reader (see also Sections 5.2.1 and 5.2.2). For N ≥ 9 the (N -1)-dimensional lattice L(Z/N Z) contains the perfect lattice L N -2 as a sublattice, see Theorem 2.1. By Proposition 1.2 we need to show that minimal vectors of L(Z/N Z) not orthogonal to (0, 1, 2, . . . , N -1) span the (N -1)-dimensional vector space (1, 1, . . . , 1) ⊥ .We consider first the N -3 minimal vectors v 2 = e 0 + e 1e 2e N -1 , v 3 = e 0 + e 2e 3e N -1 , v 4 = e 0 + e 3e 4e N -1 , . . .

w 1 =

 1 e 0 + e 2 + e m-1 + e m w 2 = e 0 + e 3 + e m-2 + e m w 3 = e 0 + e 4 + e m-2 + e m-1 w 4 = e 1 + e 3 + e m-2 + e m-1

2 . 4 v 4 v

 244 A non-zero diagonal coefficient c a,b of S can be eliminated by subtractingc a,b 4 -v +++ v t +++v +-+ v t +-+ + v ++-v t ++-+ v +--v t +-from S where v ǫ 1 ,ǫ 2 ǫ 3 = ǫ 1 e a + ǫ 2 e b + ǫ 3 e c with c = a + b ∈ F c 2 . The orthogonal projector 1 +++ v t +++ + v +-+ v t +-+ + v ++-v t ++-+ v +--v t +--has only three non-zero coefficients on the diagonal corresponding to rows (and columns) indexed by a, b and c = a + b. It is thus associated to the diagonal coefficient of a projective line over F 2 . The matrix A defined by the last seven rows (with the first row indicating the seven points of the projective plane over F 2 determinant -24 and is thus invertible. This shows that we can get rid of diagonal coefficients using the "diagonal" projectors onto projective lines by embedding them into projective planes. More precisely, given a point a ∈ F c of a projective plane Π, the projector projector onto the diagonal element indexed by a where P L is the projector1 +++ v t +++ + v +-+ v t +-+ + v ++-v t ++-+ v +--v t+--(with v ǫ 1 ǫ 2 ǫ 3 as above) associated to projective line {a, b, c = a + b} ⊂ Π. 2 Remark 7.2. (i) No elements (except subsets leaving the non-zero elements of a subgroup containing at least 8 elements) can be removed from the set F c 2 \ {0} in the construction of T (F c 2 ) without destroying perfection of the associated lattice.

The 7 -

 7 dimensional perfect lattice T (F 3 2 ) with 28 pairs of minimal vectors has a basis given by the last seven rows of 001

  1, 1, . . . , 1) and (1, 2, . . . , d + 2) of Z d+2 . Theorem 2.1. The lattice L d has determinant 1 12 (d + 1)(d + 2) 2 (d + 3) and contains no roots (vectors of norm 2). It has 1 24 d(d + 2)(2d -1) pairs of opposite vectors of (squared Euclidean) norm 4 if d is even and 1 24 (d-1)(d+ 1)(2d + 3) pairs of opposite vectors of norm 4 if d is odd. The lattice L d is perfect for d ≥ 7. Remark 2.2. The lattice L 6 has 22 pairs of minimal elements. The set {v ⊗ v} v∈min(L 6 ) spans a vector space of dimension 20. The lattice L 6 has thus perfection-default 7

  and checking the formula is straightforward.The lattice L d is obviously integral and even. Vectors of norm 2 in Z d+2 are of the form ±e i ± e j (with e 1 , . . . , e d+2 denoting the natural orthonormal basis of Z d+2 ) and are never orthogonal to both elements (1, . . . , 1) and (1, . . . , d + 2) of Z d+2 .

Vectors of norm 4 in L d are of the form e ie i+αe i+α+β + e i+2α+β with i ∈ {1, . . . , d -1} and α, β two natural numbers greater than 0 such that

  2 < • • • < a k of k natural integers a 1 , . . . , a k and an integer n we associate the set I n (a 1 , . . . , a k ) defined by the smallest n elements of {1, 2, . . . } \ {a 1 , . . . , a k }. We consider now the sequence of lattices L d (a 1 , . . . , a k ) consisting of all elements of Z d+2 which are orthogonal to (1, . . . , 1) ∈ Z d+2 and to the vector of Z d+2 with increasing coefficients given by the elements of I d+2 (a 1 , . . . , a k ). Equivalently, L d (a 1 , . . . , a k ) can be defined for d large enough as the sublattice of L d+k defined by all vectors with zero coefficients for indices in {a 1 , a 2 , . . . , a k }. The lattice L d (a 1 , . . . , a k ) is perfect if the subset I d (a 1 , . . . , a k ) defined by the d + 2 smallest elements of {1, 2, . . . } \ {a 1 , . . . , a k } contains max(2(k + 1) 2 + 1, 9) consecutive elements.

	The lattices L d (a 1 , . . . , a k ) and L d (d + 2 + k -a k , d + 2 + k -a k-1 , . . . , d + 2 + k -a 1 ) are obviously isomorphic for d > a k -k -2. Theorem 2.1 has the following generalization:
	Theorem 2.3. The lattice L d (a 1 , . . . , a k ) is perfect for d ≥ max(7, 2(k + 1) 3 -1).
	Theorem 2.3 is an easy consequence of the following two results:
	Proposition 2.4. The lattice L d (a 1 , . . . , a k ) with d ≥ 7 is perfect if a 1 ≥ 2(k + 1) 2 + 2.
	Proposition 2.5. Proof of Theorem 2.3 The result holds for k = 0 by Theorem 2.1. Re-
	moving a non-empty set of k integers from {1, 2, . . . } leaves (at most) k + 1 subsets of consecutive integers. A partition of 2(k +1) 3 -1+2 = 2(k +1) 3 +1 elements into (at most) k + 1 subsets of consecutive integers contains thus
	a subset having at least 2(k + 1) 2 + 1 consecutive elements and the result
	follows from Proposition 2.5.	2
	Proof of Proposition 2.4 Theorem 2.1 shows that the result holds for
	d ∈ {7, . . . , 2(k + 1) 2 -1}. As in the proof of Theorem 2.1 we use induction on d establishing the induction-step through Proposition 1.2. The sublattice
	of L d+1 (a 1 , . . . , a k

  We have d 0 = 7 by Theorem 2.1. For k = 1 we get the numbers

	a 1 D(a 1 ) 7 8 8 7 8 9 7 8 8 1 2 3 4 5 6 7 8 9 ≥ 10 7

a 1 , . . . , a k ) has minimum 4 and is perfect for d ∈ P(a 1 , . . . , a k ). We denote by D(a 1 , . . . , a k ) the successor of the largest missing integer in P(a 1 , . . . , a k ). We have D(a 1 , . . . , a k ) ≤ max(7, 2(k + 1) 3 -1) by Theorem 2.3. Since L d (a 1 , . . . , a k ) is perfect for every d ≥ max(7, 2(k + 1) 3 -1) ≥ D(a 1 , . . . , a k ) there exists a smallest integer d k = max a 1 ,...,a k D(a 1 , . . . , a k ) (bounded above by max(7, 2(k + 1) 3 -1)) such that L d (a 1 , . . . , a k ) is perfect for every d ≥ d k and for every {a 1 , . . . , a k } in {1, 2, . . . }.

  arbitrary, the number of perfect integral lattices of dimension d with minimum 4 grows faster than any polynomial in d. 2 3 The odd construction We denote by O d the d-dimensional lattice of all integral vectors in Z d+1 which are orthogonal to (1, 3, 5, . . . , 2d + 1). The lattice O d is even and contains no roots. Since (1, 3, 5, 7, . . . ) = 2(1, 2, 3, 4, . . . ) -(1, 1, 1, 1, . . . ) the lattice O

d contains L d-1 as a sublattice. Pairs of minimal vectors of O d not contained in the sublattice L d-1 are of the form e 2a-1 + e 2b-1 + e 2c-1e 2k-1 (with indices given by the coefficients of (1, 3, 5, . . . )) corresponding to sums 2k-1 = (2a-1)+(2b-1)+(2c-1) of three distinct odd natural integers 2a-1, 2b-1, 2c-1 ∈ {1, 3, 5, . . . , 2d-3} adding up to 2k-1 ∈ {9, 11, . . . , 2d+1}. Theorem 3.1. The lattice O d has determinant 1 3 (d + 1)(2d + 1)(2d + 3) and minimum 4 (for d ≥ 3). It has 1 18 2d 3 -3d 2 -3d + c d pairs of minimal vectors of norm 4 where

  The lattice M (A/(±1)) is without roots. It has rank |A/(±1)| and determinant 4|A| 2 . Vectors of norm 4 in M (A/(±1)) are of the form ±2e a if 2a = 0 in A for a ∈ A/(±1) or of the form ±e a 1 ± e a 2 ± e a 3 ± e a 4 if ±a 1 ± a 2 ± a 3 ± a 4 = 0 in A for four distinct elements a 1 , . . . , a 4 of A/(±1) with ± denoting suitable choices of signs.

	The subgroup of all elements of
	order at most 2 acts by isometries on M (A/(±1)) and the group A can be
	recovered (up to isometries) from the set of minimal vectors of norm 4 in
	M (A/(±1)).

Keywords: Perfect lattice, finite abelian group, projective plane, equiangular system, Schläfli graph, Sidon set, Craig lattice. Math. class: Primary: 11H55, Secondary: 11T06,

20K01, 05B30, 05E30.

Acknowledgements I thank Philippe Eyssidieux for an interesting discussion, Jacques Martinet and an anonymous referee for a careful reading and many helpful remarks.

 * This work has been partially supported by the LabEx PERSYVAL-Lab (ANR-11-LABX-0025). The author is a member of the project-team GALOIS supported by this LabEx.

lattice E 7 . Its 28 pairs of minimal vectors define a system of 28 equiangular lines (meeting two-by-two in a common angle given by arccos(1/3)) in R 7 . Supports of minimal vectors define projective lines in the Fano plane (projective plane over F 2 ). The automorphism group of T (F 3 2 ) acts transitively on the set of minimal vectors. Fixing a first minimal vector, say w = (1, 1, 1, 0, 0, 0, 0), we chose representatives v 1 , . . . , v 27 of the 27 minimal pairs different from ±w such that w, v i = 1. We encode the angles between v 1 , . . . , v 27 by a graph Γ with vertices v 1 , . . . , v 27 and edges v i , v j if v i , v j = -1. The characteristic polynomial of the adjacency matrix A of Γ (with diagonal zero and off-diagonal coefficients

) is given by (t -10)(t -1) 20 (t + 5) 6

and the graph Γ is thus a strongly regular graph on 27 vertices with parameters (v, k, λ, µ) = (27, 10, 1, 5). Otherwise stated, the graph Γ has v = 27 vertices. It is of degree k = 10 and diameter 2 such that two adjacent vertices in Γ have always λ = 1 common neighbours and two non-adjacent vertices of Γ have always µ = 5 common neighbours. λ = 1 is equivalent to the fact that every edge of Γ is contained in a unique triangle (complete graph on 3 vertices) of Γ.

Such a graph is unique and it (or sometimes its complement) is called the Schläfli graph.

Remark 7.3. (i) The even sublattice of the lattice T (F 2

3 ) is (up to rescaling) the root lattice E 7 consisting of all vectors of the lattice M (F 3 2 ) (see Section 6.2) not involving the basis vector e 0 associated to the identity 0 of the additive group F 3 2 . Its 63 pairs of minimal vectors can be described as follows: Every line {i, j, k} gives rise to 2 3 = 8 pairs of minimal vectors by considering a vector with zero coordinates corresponding to i, j, k and with coordinates ±1 associated to points not in {i, j, k}. This gives 7 • 8 = 56 pairs of minimal vectors (of norm 4). Seven additional pairs are given by ±2e i and are associated to the seven points of the projective plane.

(ii) Restricting to vectors with zero coordinate-sum of the even sublattice of T (F 3 2 ), we get the rescaled root lattice A 6 of Section 5.4.

Proposition 8.2. For k smaller than the characteristic p of F q , the number of pairs of elements of norm 2(k + 1) in C q-1,k is given by

where N (a 1 , . . . , a k ) ≤ q is the number of constants a 0 ∈ F q such that the polynomial x k+1 + k i=0 a i x i has exactly k + 1 distinct roots in F q .

Proof N (a 1 , . . . , a k ) is also the number of subsets {x 1 , . . . , x k+1 } of k + 1 distinct elements in F q such that k+1 i=1 x j i = b j with b 1 , . . . , b k the powersums corresponding to the elementary symmetric functions a k , a k-1 , . . . , a 1 . Such subsets are disjoint and pairs of two such subsets define indices of coefficients 1 and -1 in minimal vectors. 2

Corollary 8.3. The lattice C q-1,k (for k smaller than the characteristic p of F q ) has at least

2 pairs of vectors of norm 2(k + 1).

In particular, for a fixed value of k, the lattice C q-1,k has asymptotically at least q k+2 2((k+1)!) 2 pairs of minimal vectors of norm 2(k + 1).

Proof Since every subset of k + 1 elements in F q contributes 1 to exactly one of the numbers N (a 1 , . . . , a k ) we have

Convexity properties of the polynomial x 2 = x(x-1) 2 imply that ( 2) is minimal if all q k numbers N (a 1 , . . . , a k ) are equal.

2

Theorem 8.4. For k = 2, the number of minimal pairs in C q-1,2 is given by 1 72 q(q -1)(q 2 -10q + 33)

for q a prime-power congruent to 1 modulo 6 and by

for q a prime power congruent to 5 modulo 6.

Sketch of Proof

We have to evaluate Formula (2) for k = 2. Substituting x with x -a 2 3 we get N (a 1 , a 2 ) = N (a 1 -1 3 a 2 2 , 0). Formula (2) for k = 2 is thus given by q a∈Fq N (a, 0) 2 if q is not a power of 3. Since N (a, 0) depends only on the value a q of the quadratic character extending the Jacobi symbol, we have to compute N (a, 0) for a = 0, 1 and for a non-square of F q . These computations boil down to classical properties of binary quadratic forms over finite fields. (One can alternatively use a result of Stickelberger, as observed by the reviewer.) 2 Remark 8.5. A close relative of the lattice C q-1,2 is the lattice associated to the Sidon set {(x, x -1 )} x∈F * q ⊂ F 2 q for F q a finite field of odd characteristic. It is of dimension q -2, has minimum 6 (except for a few small values of q) and consist of all elements (λ x ) x∈F * q ∈ Z F * q (integral vectors with indices in F * q ) such that x∈F * q λ x = 0 and x∈F * q λ x x = x∈F * q λ x x -1 = 0 ∈ F q .

For k = 3, let c q be such that the number of pairs of minimal vectors (of norm 8) in C q-1,3 is given by 1 1152 q(q -1)(q 3 -21q 2 + 171qc q ). Writing c k as

we have the following result due to Noam D. Elkies, see [START_REF] Elkies | Answer to Mathoverflow question 158769[END_REF] (a preliminary draft of the present paper proposed the values corresponding to δ q = 0 conjecturally):

Theorem 8.6. If q is a prime ≤ 5, then δ q = 0 if -2 q = -1 (yielding the values

455

if q ≡ 5 (mod 24), 511 if q ≡ 7 (mod 24), 583 if q ≡ 13 (mod 24), 383 if q ≡ 23 (mod 24)

for c q in these cases) and δ q = 24(m 2 -2n 2 ) + 192 + 72 -1 q

where m and n are the unique natural integers such that q = m 2 + 2n 2 otherwise (i.e. for q ≥ 11 a prime such that -2 q = 1).

See [START_REF] Elkies | Answer to Mathoverflow question 158769[END_REF] for the fairly sophisticated proof.


Yanyan Yang

Shenle Pan

Eric Ballot
email: eric.ballot@mines-paristech.fr

An inventory control model with interconnected logistic services for vendor inventory management

Keywords: Inventory control, Physical Internet, Optimization

This paper proposes an inventory control model taking advantage of interconnected logistic services in the Physical Internet for fast-moving consumer goods (FMCG) sector. Unlike current hierarchical inventory model where the source of each is pre-assigned, the goods are stored and distributed in an interconnected and open network of PI-hubs which enables storage capacity and transportation sharing among different companies around the network. As a result, theoretically, the suppliers can push their goods all around the network and the retailers can be served by any hub in the network. A non-linear global optimization inventory model to minimize the total logistic costs is proposed and a heuristic using simulated annealing is applied to solve the problem. Numerical experiments are taken to compare the performance of the proposed PI inventory model and classic inventory control model for different settings of a typical supply network. Results suggest that the PI inventory control model can always reduce the total logistic cost while reaching a comparable or improved end customer service level.

Introduction

In the past decades, numbers of papers have dealt with inventory problems based on hierarchical inventory systems as inventory often accounts for a large proportion of a company's supply chain management costs. According to (Cachon and Terwiesch 2005), generally speaking in Fast Moving Consumer Goods -FMCG sector, the inventory cost represents averagely up to 40% of total logistics cost, in addition to the cost of shortages in retailers, i.e. around 7% of references in supermarket. Thus, efficiently managing inventory systems becomes quite crucial to improve a company's business performance. Nevertheless the efficiency to reduce inventories, the existing inventory model extensions are based on hierarchical inventory structure, which have been more and more challenged by the new practices of today's supply chains: the increasing uncertainty of customer demand, increasing service requirements reflected in the importance of narrow delivery time windows and pressure on lead time reduction, and also longer lead time from sourcing points to end customers due to the delocalization of warehouses [START_REF] Angel | Warehousing Space in Europe: Meeting Tomorrow's Demand. A Pan-European Warehousing Trends Study by Capgemini and ProLogis[END_REF]. Assuming that the hypothesis of hierarchical inventory systems is an inherent limit for current inventory models, we are interested here to study innovative models that are more open, flexible and horizontally collaborative.

In this paper, we propose an inventory control model with the recently proposed logistic concept -Physical Internet with interconnected logistic services and investigate its impacts compared to current inventory control models to different logistic network configurations. Inspired by the metaphor of Digital Internet, the Physical Internet (PI) aims to integrate heterogeneous and independent logistics networks into an open and interconnected global system through standard containers and routing protocols [START_REF] Sarraj | Interconnected logistic networks and protocols: simulation-based efficiency assessment[END_REF]. As an innovative concept in logistics, further studies about the concept of the network are carried out by [START_REF] Montreuil | Toward a Physical Internet: meeting the global logistics sustainability grand challenge[END_REF]Ballot, Montreuil, and Fontane 2011a;[START_REF] Montreuil | Physical Internet Foundations[END_REF]. [START_REF] Sarraj | Interconnected logistic networks and protocols: simulation-based efficiency assessment[END_REF]) study the transportation performance of PI network in terms of FMCG cases in France and assess the new organization can reduce up to 35% of actual transportation cost through the optimization of full truckload and integration of different transportation means.

Concerning inventory problems in the Physical Internet, [START_REF] Pan | Perspectives of inventory control models in the Physical Internet: A simulation study[END_REF] is the first to describe the inventory problems in the Physical Internet and investigate the first perspectives of PI inventory models compared to classic inventory models. Instead of classical centralized and hierarchical storage organizations in current logistic systems, the PI network enables a distributed storage of goods in an open and interconnected network of hubs. The network of hubs may be managed by the Logistic Service Providers (LSP) and shared by companies including other suppliers and their customers (retailers). In other words, theoretically, each supplier is able to store their goods at any hub all around the network and each customer (retailers) can be served by any hub or directly by the suppliers, resulting in more supply options and increasing service level for retailers and potential reduced logistic costs by sharing of storage capacity and transportation means to supply the demand. The aim is to make current inventory systems more open, robust, and economic thus more sustainable. As a result, the sourcing points for each replenishment order are no longer pre-determined and can be dynamically decided according to source selection strategies and needs. Thus under this structure, the inventory decisions for vendors lie on: 1) how to respond to each replenishment order from retailers with required constraints; 2) how to push inventories in the PI-network to satisfy these orders with certain objectives.

To gain insight into the question, we study a single FMCG (fast moving consumer good) product inventory problem in a Physical Internet network of hubs supplying a group of retailers which face normal distributed end-customer demands. We adopt a centralized vendor-decision framework for the supplier who determines the inventory control policies for the warehouses and DCs or the hubs. The objective is to determine optimal inventory control policies of hubs to minimize the total cost of the distribution system while satisfying replenishment orders from retailers. We suppose the optimal replenishment parameters at retailers are obtained locally to minimize its own total cost and considered as input information for the distribution network. To solve the problem, a global nonlinear optimization model is proposed and a heuristic using simulated annealing is applied. A simulation study is taken to validate the optimized inventory control policies. Different settings of the typical network are analyzed. Our results suggest that the PI-inventory model with dynamic source selection strategies can significantly reduce the supply chain management cost compared to classic centralized inventory control strategy while reaching a similar or improved end customer service level at retailers (defined as the percentage of customer satisfied by inventory on hand).

The remainder of this paper is organized as follows. In Section 2, we discuss the related works in the literature. In Section 3, the optimization model developed to PI inventory problem will be presented. Then, in Section 4 the optimization model will be implemented in case studies of FMCG chains. A number of scenarios are proposed and studied in order to validate the model and study the pertinence of model in different configuration of network. Finally, Section 5 concludes this paper by giving some perspectives to the next works.

Literature Review

Within the literature we found the following three inventory control models based on current hierarchical inventory system close to the PI inventory modality: i) inventory models with lateral transshipments that allow inventory movements among members of the same echelon; ii) inventory models with multi-sourcing options which enables a replenishment order to be satisfied by multiple supplying points; iii) inventory routing problems which combines vehicle routing and inventory control problems and where a supplier decides when to visit its customers, how much to deliver to each of them and how to combine distribution flows into vehicle routes. Motivated foremost by the aim of reducing lead times, lateral transshipment refers to stock movements between the same echelon locations within an inventory system. Recent comprehensive overviews are provided by [START_REF] Paterson | Inventory models with lateral transshipments: A review[END_REF]. Two types of transshipments are often addressed according to the timing of the transshipments: 1) reactive transshipments in response to an existing stock-out as seen in [START_REF] Krishnan | Inventory control in N warehouses[END_REF]Robinson, 1990;Olsson, 2010); 2) proactive transshipments to prevent the future stock-out, as seen in [START_REF] Gross | Centralized inventory control in multilocation supply systems[END_REF][START_REF] Diks | Optimal control of a divergent multi-echelon inventory system[END_REF]Tagaras and Vlachos, 2002). The literature has shown that transshipment is quite profitable for retailers with long replenishment lead times from suppliers and who are located closer to one another or who have grand shortage penalty cost. In spite of the horizontal sharing of inventories in both transshipments and PI inventory model, the hubs in the Physical Internet are fully interconnected and the source selection is dynamically determined while in the lateral transshipments the source is preassigned and the transshipments are used as a support to regular replenishment orders.

The research of the multi-sourcing inventory model can be divided into two categories according to whether an order can be split into sub-quantities and met by several source supplying points: 1) without order splitting which focus on source substitution method, as seen in [START_REF] Ng | Coordinated replenishments with alternative supply sources in two-level supply chains[END_REF][START_REF] Çapar | A decision rule for coordination of inventory and transportation in a two-stage supply chain with alternative supply sources[END_REF][START_REF] Veeraraghavan | Now or later: A simple policy for effective dual sourcing in capacitated systems[END_REF]; 2) with order splitting which focus on inventory allocation method in addition to source substitution, as seen in [START_REF] Sculli | Stock control with two suppliers and normal lead times[END_REF][START_REF] Ryu | A stochastic inventory model of dual sourced supply chain with lead-time reduction[END_REF][START_REF] Song | Integrated inventory management and supplier base reduction in a supply chain with multiple uncertainties[END_REF]. The literature shows that the multi-sourcing can reduce the mean and variance of the effective lead time and a split order model always has lower stock levels than the equivalent non-split model. However, the multi-sourcing options in current multi-sourcing models are only restricted between the upper level stocking points and their successive demanding points. The same echelon stocking points are independent and no products flow at the same echelon stocking points are allowed. Therefore we conclude that our model differs from the existing multi-sourcing inventory models in literature.

Similarities are also found in the inventory -routing problems (IRPs). The pioneer contributions of IRPs can be date back to1980s [START_REF] Bell | Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer[END_REF]) and recent reviews are shown in [START_REF] Bertazzi | Inventory routing problems: an introduction[END_REF]. The existing literature demonstrates that this strategy can improve the supply chain performance by savings on distribution and production cost for suppliers by coordinating shipments to different customers. Despite the fact there may exist vehicle routing optimization in both models, the PI inventory models differ from the IRPs mainly from the following two facts:1) the transportation sharing in the PI network is realized by modularized and standardized containers and routing protocols including vehicle routing optimization, interconnection of multi-modal transport, and etc.; 2) the PI network is able to rebalance stocks in the PI network of hubs to satisfy replenishment orders from retailers while the balance of stocks among different retailer companies is not addressed in IRP. [START_REF] Pan | Perspectives of inventory control models in the Physical Internet: A simulation study[END_REF]) describe inventory problems based on the Physical Internet and propose a rule-based simulation inventory control model with different source selection strategies. However, due to the lack of optimization model, determination of optimal solutions as well as the quantitative study of different settings of the logistic network is not fully addressed in this paper. Hence, there exist no corresponding optimization inventory control model to the principles of proposed PI inventory model. It is a new research issue and a new topic in inventory management.

Assumptions and formulations

Assumptions

We consider single-product inventory problems of a typical FMCG network with a plant (a vendor) serving a group of Nr retailers through a network of M intermediate stocking points (hubs or DCs or WH). Two types of networks are taken into account: classic centralized hierarchical inventory network and PI inventory network. The Vendor-Managed Inventory (VMI) decision framework is adapted where the vendor accesses inventory information and decides inventory control decisions at intermediate stocking points (hubs or DCs or WH) to minimize the total logistic costs. The retailers face real demand data from the FMCG industrial sector and the optimal inventory control decisions of each retailer are computed locally based the model of [START_REF] Giard | Gestion de la production et des flux 3e Edition[END_REF]. The results are considered as the input to the optimization model for the vendor. The objective is to find optimal inventory control decisions of intermediate stocking points and source selection decisions to minimize the total logistic costs while satisfying demands from retailers with a similar end customer service level.

The following common assumptions are adapted for all scenarios: a) Each stocking facility including hubs, DCs, WH and retailers applies a (R, Q) continuous review policy; b) The plant is assumed to always have adequate stocks to meet the demands and there is no capacity constraint for hubs; c) Replenishment orders from retailers unmet immediately are considered with a penalty cost; d) The lead times among all the interconnected facilities are given and assumed to be constant; e) The orders are served on a first-come-first-served basis; f) No partial delivery is allowed; g) End customer demands to retailers are uncertain and subject to normal distribution; h) Vendor makes all source selections to supply the retailers; i) The optimal replenishment policies for retailers are determined by the algorithm proposed by [START_REF] Giard | Gestion de la production et des flux 3e Edition[END_REF]; j) Localizations of all sites remain the same in all scenarios for comparison sake.

Five logistic costs are considered: inventory holding cost, transportation cost, ordering cost, the penalty cost and handling cost. The holding cost are charged for each unit in stock per time unit at hubs or DCs or WH. The transportation cost for each delivery of goods are considered and includes three parts: upstream transportation cost from plants to hubs or WH, upstream transportation cost among hubs or towards DC, and downstream transportation cost to retailers. Each replenishment order placed incurs a fixed ordering cost. Penalty costs for retailers' orders unmet immediately are charged and assumed to be proportional to product value. Finally, handling cost are considered for each movement of stocks enter and leave hubs or DCs or WH.

Notations and formulations

To introduce the optimization model, we use the following notations. And we always refer to Stock Keeping Unit (SKU) to the minimum unit we consider in the model. (𝑢 𝑗 , 𝜎 𝑗 ): average and standard deviation of end customer demand at retailer 𝑗.

(𝑞 𝑗 , 𝑠 𝑗 ): replenishment policy of retailer j -𝑞 𝑗 for batch size and 𝑠 𝑗 for reorder point. Subject to:

0 ≤ ∑ 𝑥 𝑘𝑗𝑛 ≤ 1 ∀𝑗 ∈ 𝑁𝑟, ∀𝑛 = 1 … 𝑇 𝑀 𝑘=1 (6) 𝑥 𝑘𝑗𝑛 ∈ {0,1} ∀𝑘 ∈ 𝑀, ∀𝑗 ∈ 𝑁𝑟, ∀𝑛 = 1 … 𝑇 (7) 0 ≤ ∑ 𝑥 𝑘𝑖𝑛 ≤ 1 ∀𝑖 ∈ 𝑀, ∀𝑛 = 1 … 𝑇 𝑀 𝑘=0,𝑘≠𝑖 (8) 𝑥 𝑘𝑖𝑛 ∈ {0,1} ∀𝑖 ∈ 𝑀, ∀𝑘 ∈ 𝑀 ∪ {0}, 𝑖 ≠ 𝑘, ∀𝑛 = 1 … 𝑇 (9)
𝑅 𝑖 , 𝑄 𝑖0 , 𝑄 𝑖 : Integers, ∀𝑖 ∈ 𝑀 (10)

Where equation (1) represents the total annual holding cost at the hubs or DC or WH, equation (2) indicates the total annual transportation cost and handling cost to satisfy replenishment orders from retailers, equation (3) describes the total annual transportation cost, fixed ordering cost and handling cost to meet the replenishment orders of the hubs by other hubs or orders from DCs by WH, equation (4) the total annual transportation cost, fixed ordering cost and handling cost to meet the replenishment orders of the hubs by the sources or WH by the plant, equation ( 5) introduces the penalty cost for replenishment orders from retailers unmet immediately which is defined linear to the average demands and product value at retailers. Equation ( 6) -( 9) describe the constraints that the replenishment orders can only be met by one facility each time. Hence, order splitting is not allowed in the model. Equation ( 10) indicates that the demanding quantity cannot be allowed fractional or partial.

Results analysis

Experiments Design

With optimal replenishment parameters at retailers obtained by [START_REF] Giard | Gestion de la production et des flux 3e Edition[END_REF], the dynamic source selection strategy Source Substitution in [START_REF] Pan | Perspectives of inventory control models in the Physical Internet: A simulation study[END_REF]) is applied to determine the source selection variables 𝑥 0𝑖𝑛 /𝑥 𝑘𝑖𝑛 / 𝑥 𝑘𝑗𝑛 . Recall the Source Substitution strategy always chooses the nearest candidate to the ordering point among the candidates with inventory level bigger than the ordering quantity. A simulated annealing algorithm is constructed to optimize the replenishment parameters of intermediate stocking points. With the optimal replenishment parameters for each hub, we simulated the total system for 100 times and evaluate the average total cost of the hub system, the average total inventory level of all hubs, the average end customer level at retailers, and etc.

A single product network with a supplier company supplying two regional retailer companies is studied and the localization is shown in Figure 1. As seen in the picture, the three companies have common areas of logistic activities and geographically privileged areas. The points of sales R1 and R2 are geographically privileged to their own retailer company while the points of sales R3 and R4 are in the common area of the three companies. It indicates the three companies have great possibilities to share their logistic activities, i.e. transportation, storage capacity, and etc. The leadtime are assumed to be 5 days between the plant and the hubs, 1 day between hubs and 2 days between hubs and retailers. The route distance matrix (km) is described in the Table 1 as follows. The impact of the following four parameters are analyzed: fixed ordering cost A= 8/20/80 (monetary unit) per order (or 0 if the order is not satisfied), the average demand level at retailers (value range: high/low, seen in Table 2), the product value 0.5/50 (monetary unit) leading to different penalty cost and holding cost, and the handling cost 0/2 (monetary unit) for a pallet of goods enter and out of each stocking point. For this paper, the low standard deviation at retailers are considered and the values are shown in Table 2. A pallet of goods is assumed to be 1.73 𝑚 3 and a unit of goods is assumed to be 0.003 𝑚 3 (equivalent to 500ml or 750 ml bottle of beverage). A SKU is a container of 6 units of goods. A full truck-load is assumed to be 33 full pallets. The penalty cost for retailers' orders unmet immediately is considered as 20% of the product value in intermediate stocking points and 30% at retailers. The transportation cost from the plant to hubs and among hubs is assumed to be 1.4 (monetary unit) per full truckload per km and 2.0 per full truckload per km from hubs to retailers.

This assumption is based on the fact that the long-haul transportation cost is lower than that the last mile transportation cost. The holding cost per SKU is considered as the sum of two parts: the stocking cost per unit per day for storage space that is assumed to be 0.11 per 𝑚 3 /day in WH or DC or hubs (0.165 at retailers), and capital cost which is 8% of the product value per year. Therefore, for scenario of each network, there are 3*2*2*2=24 instances, as indexed in Table 3. With all these setups and the methods presented in [START_REF] Giard | Gestion de la production et des flux 3e Edition[END_REF], the optimal replenishment parameters (SKUs) for retailers are obtained to minimize its annual total cost including inventory holding cost, fixed ordering cost and penalty cost for lost sales with required lead time constraints. It is considered as the input data for the network of hubs, shown in Table 4. The optimal replenishment parameters for hubs are obtained by a simulated annealing heuristic method where the convergence ratio, the maximum temperature and the maximum iteration number are set to be 3%, 60, and 6000.

With the optimal replenishment parameters for each hub, we simulated the total system for 100 times and evaluate the average total cost of the hub system, the average total inventory level of all hubs, the average end customer level at retailers, and etc. All the experimental tests are developed in Mathematica® 10.0 on a PC with Intel (R) Core (TM) i7-3940XM CPU 3.20 GHz and 32 Go RAM.

Results analysis

We adapt the performance ratio defined in [START_REF] Ng | Coordinated replenishments with alternative supply sources in two-level supply chains[END_REF] to compare the performance of scenarios.

Here the classic inventory model is always used as the baseline and the performance ratio to other scenarios is the relative variations. Table 5 presents the average performance ratios of PI inventory model to classic inventory model with pre-determined sources. For example, for the instances where the average demand level is high as seen in Table 5, the average total cost of the distribution network are reduced 34% by the PI inventory model and 24% of the reduction comes from the holding cost while reaching a similar end customer service level at retailers. For all instances, we observe that the proposed PI inventory model can reduce the total logistic cost compared to classic inventory models while reaching a comparable or improved end customer service levels at retailers. In these instances compared to classic inventory model, the PI network has averagely 18% percent transportation cost profit perspective by direct shipping when the objective is to minimize the travel distance. However, as the objective is to minimize the annual total cost, the results shows direct shipping is not always the optimal solutions. And the transportation cost is not always reduced by 18%. We observe that in these scenarios the profits mainly come from the reduction of inventory holding cost and the average saving of the total cost reaches to 44% while reaching a similar end customer service level at retailers. Besides, the percentage of reduction of total cost increases with low demand level and high fixed ordering cost. Because with low level demand retailers at the network and high fixed ordering cost, the PI inventory model will compromise the downstream transportation cost from hubs to retailers to reduce the total inventory holding cost by grouping the distribution flows into one stocking point such as in Figure 2. 6 gives a quantitative description of interactions among hubs. The percentage of transshipment is defined as the percentage of replenishment orders of hubs satisfied by other hubs and the percentage of multi-sourcing refers to the percentage of retailer's orders satisfied by other hubs except the most regular hub. Results show that generally as the transportation cost set is linear to the quantity and distance travelled, the distribution flows of the network tend to be decentralized as to reduce the travel distances. However, the possibility of interactions among hubs increases when the product value and demand level at retailers increases as to reduce the total inventory holding cost and penalty cost for demands unmet immediately by pooling of the inventories among hubs. Besides, the augmenting fixed ordering cost and handling cost restrict the stock movements among hubs as expenses are charged for additional movements.

Conclusions

We have developed and evaluated a PI-inventory model in FMCG sector with a plant supplying a network of hubs and retailers. The optimal replenishment policies for hubs are determined to minimize the annual total cost of the distribution system including holding cost, fixed ordering cost, transportation cost and penalty cost for orders from retailers unmet immediately. A heuristic using simulated annealing is proposed to solve the optimization problem and then a simulation study is taken to evaluate the optimal policies under each sourcing strategy. The results show the PI inventory model can significantly reduce the average total cost compared to the current pre-determined inventory model while reaching a similar end customer service levels as the open and interconnected network enables more options. The profits are mainly come from the interactions among hubs to reduce the inventory levels around the network. Besides, as the source selection decisions are dynamically determined in PI network, a change in flexibility, i.e. fixed ordering cost, customer demand level, is immediately valued in the structure of the distribution flows, which improves the robustness of the inventory system to the perturbations of the economic environment. In a word, there is little doubt, this scheme proposes a drastic change compare to nowadays FMCG supply chain management that needs thus to be further investigated.

In this paper, the interactions among hubs are limited by the limited geography cover as well the small numbers of consignees in common logistic area. Great numbers of facilities in large common logistic area will lead to a significant change of the distribution scheme with more frequent transshipment among hubs and also more use of multi-sourcing in the downstream distribution flows.

Further research is also required to investigate performance of different source selection methods as discussed in our previous paper [START_REF] Pan | Perspectives of inventory control models in the Physical Internet: A simulation study[END_REF] for different configurations of the network. Finally, another important factor to study is the robustness of PI network to some disruptive effect, for example the effects when a hub becomes suddenly unserviceable.

  Notations:𝑀: set of intermediate stocking points (plant index by 0). 𝑁𝑟: set of retailers.𝑇: configuration time of the inventory system, indexed by 𝑛 (1 year = 365 days). 𝑑𝑖𝑠 𝑖𝑗 : distance between intermediate stocking point 𝑖 ∈ 𝑀 and retailer 𝑗 ∈ 𝑁𝑟. 𝑑𝑖𝑠 𝑘𝑖 : distance between intermediate stocking point 𝑘 ∈ 𝑀 and 𝑖 ∈ 𝑀. 𝑑𝑖𝑠 0𝑖 : distance between intermediate stocking point 𝑖 ∈ 𝑀 and the plant 0.

  𝐻 𝑖 : daily holding cost per SKU at intermediate stocking point 𝑖. hd: handling cost per SKU operated.𝑝 𝑗 : daily penalty cost per SKU of unmet orders from retailer 𝑗 ∈ 𝑁𝑟, proportional to product value.𝑐 1 : downstream transportation cost per kilometer per SKU from the hubs to retailer.𝑐 2 : upstream transportation cost per kilometer per SKU from the plant to hubs and among hubs.A : fixed ordering cost per order. 𝐼𝐿 𝑖𝑛 or 𝐼𝐿 𝑗𝑛 : inventory level at intermediate stocking point 𝑖 or retailer 𝑗 between 𝑛th and (𝑛 + 1)th day. The decision variables are: 𝑅 𝑖 : intermediate stocking point 𝑖's reorder point. 𝑄 𝑖0 : intermediate stocking point 𝑖's batch size (order quantity) from the plant. 𝑄 𝑖 : intermediate stocking point 𝑖's batch size (order quantity) from other intermediate stocking points. 𝑥 0𝑖𝑛 : binary variable of whether choose plant 0 to satisfy the demand of intermediate stocking point 𝑖 at time 𝑛th day, if so 𝑥 0𝑖𝑛 = 1, otherwise 0; 𝑥 𝑘𝑖𝑛 : binary variable of whether choose intermediate stocking point 𝑘 ∈ 𝑀 to satisfy the demand of intermediate stocking point 𝑖 (𝑖 ≠ 𝑘) at time 𝑛th day. 𝑥 𝑘𝑗𝑛 : binary variable of whether choose facility 𝑘 ∈ 𝑀 to satisfy the demand of retailer 𝑗 at time 𝑛th day∑ ∑ 𝑥 𝑘𝑗𝑛 [𝑐 1 𝑞 𝑗 𝑑𝑖𝑠 𝑘𝑗 + 𝑞 𝑗 * ℎ𝑑]

Figure 1 .

 1 Figure 1. Localization of the facilities in networks

  (a). However, in the classic inventory model like in Figure2.(b), the flow directions are always pre-determined and can't adapt to the changes of the economic environment changes.

Figure 2 .

 2 Figure 2. Distribution flow compare PI vs Classic

Figure 3 .

 3 Figure 3. Distribution flow PI network

Table 1 .

 1 Route Distance Matrix (km)

	Source Destination	Plant	HUB1	HUB2	HUB3
	HUB1	200	0	160	155
	HUB2	350	160	0	165
	HUB3	325	155	165	0
	R1		170	15	160
	R2		140	165	15
	R3		100	95	90
	R4		90	100	105

Table 2 .

 2 Daily demand level and standard deviation at retailers (units of goods)

	Nodes	R1	R2	R3	R4
	u1 (High)	240	288	144	192
	u2 (low)	30	45	20	46
	σ (Low)	3	4	2	3
		Table 3 List of instances
	Instances Index Handling cost Fixed ordering cost Product value Demand level
	1	0	8	0.5	u1
	2	0	8	0.5	u2
	3	0	8	50	u1
	4	0	8	50	u2
	5	0	20	0.5	u1
	6	0	20	0.5	u2
	7	0	20	50	u1
	8	0	20	50	u2
	9	0	80	0.5	u1
	10	0	80	0.5	u2
	11	0	80	50	u1
	12	0	80	50	u2
	13	2	8	0.5	u1
	14	2	8	0.5	u2
	15	2	8	50	u1
	16	2	8	50	u2
	17	2	20	0.5	u1

Table 4 .

 4 Optimal replenishment parameters of retailers(SKUs)

	Instances Index	R1 (q, s) SKUs	R2 (q, s) SKUs	R3 (q, s) SKUs	R4 (q, s) SKUs
	1	13	{420, 121}	{326, 74}	{460, 145}	{376, 97}
	2	14	{149, 16}	{183, 24}	{122, 11}	{184, 24}
	3	15	{97, 122}	{75, 75}	{106, 145}	{87, 98}
	4	16	{34, 17}	{42, 25}	{28, 11}	{42, 25}
	5	17	{664, 121}	{515, 73}	{728, 145}	{594, 97}
	6	18	{235, 16}	{288, 24}	{192, 10}	{291, 24}
	7	19	{153, 122}	{119, 75}	{168, 145}	{137, 98}
	8	20	{54, 17}	{67, 25}	{45, 11}	{67, 25}
	9	21	{1329, 121} {1029, 73} {1456, 145} {1188, 97}
	10	22	{470, 15}	{576, 23}	{384, 7}	{582, 23}
	11	23	{305, 122}	{237, 74}	{334, 145}	{273, 98}
	12	24	{108, 17}	{132, 25}	{88, 11}	{134, 25}

Table 5

 5

			. Average performance ratios: PI vs Classic
	Parameter	Demand level Handling cost	Product value	Fixed ordering cost
	Value	Low High	0	2	0.5	50	8	20	80
	Total cost	-54% -34% -43% -45% -44%	-44% -39%	-39%	-53%
	Service level	0%	0%	0%	0%	0%	0%	0%	0%	0%
	Holding	-48% -24% -38% -34% -36%	-36% -29%	-30%	-50%

Table 6

 6 Interactions among hubs in PI network

	Parameter	u		hd		c			A
	Value	Low High	0	2	0.5	50	8	20	80
	Percentage	0%	2%	2%	0%	0%	2%	0%	3%	0%
	transshipment
	Percentage	0% 10% 6%	4%	4%	6%	8%	4%	3%
	multi-sourcing