Parmi 2n-1 entiers, la somme de n entiers ...

Bonjour

Si $n$ est impair, il suffit de prendre $n$ entiers consécutifs car modulo $n$ la somme sera $1+2 + \dots + n = \frac{n(n+1)}{2} \equiv 0 \bmod n$ car $2$ et $n$ sont premiers entre eux.
Le cas $n$ pair est plus intéressant j'imagine.

Cela m'évoque le théorème d' Erdös, Ginzburg, et Ziv.

Gilles:

Si je comprends l'énoncé on ne cherche pas à trouver une configuration des $2n-1$ entiers mais, au contraire, la configuration est donnée et rien ne dit que les $2n-1$ entiers sont consécutifs ou obéissent à une répartition particulière autre que celle à démontrer.

Cela m'évoque une application du principe des tiroirs sans que je sache préciser cette pensée.

$\def\F{\mathbb F}$Là, je m'amuse avec $n = p$ premier. Petit joueur, je fais $p=5$. Je ne vais pas considérer des entiers mais un anneau de polynômes à $2p-1$ indéterminées à coefficients dans $\F_p$.
D'abord, j'ai besoin de l'ensemble de toutes les parties à $p$ éléments de l'ensemble $\{1, 2, \cdots, 2p-1\}$

[color=#000000]
> p := 5 ;                     
> P := Subsets({1..2*p-1}, p) ;
> #P ;
126
> Random(P) ;
{ 2, 3, 5, 7, 8 }
[/color]

Je monte mon anneau de polynômes $A = \F_p[X_i, \ 1 \le i \le 2p-1]$ et je pose $S_I = \sum_{i \in I} X_i$

[color=#000000]
> Fp := GF(p) ;                
> A := PolynomialRing(Fp, 2*p-1) ;                             
> AssignNames(~A, ["X"*IntegerToString(i) : i in [1..2*p-1]]) ;
> A ;
Polynomial ring of rank 9 over GF(5)
Order: Lexicographical
Variables: X1, X2, X3, X4, X5, X6, X7, X8, X9
> S := func < I | &+[A.i : i in I] > ;
> 
> I := Random(P) ;
> I ;
{ 1, 3, 4, 5, 7 }
> S(I) ;
X1 + X3 + X4 + X5 + X7
[/color]

Attention, c'est du lourd : je (sic) calcule $S_I^{p-1}$.

[color=#000000]
> S(I)^(p-1) ;
X1^4 + 4*X1^3*X3 + 4*X1^3*X4 + 4*X1^3*X5 + 4*X1^3*X7 + X1^2*X3^2 + 2*X1^2*X3*X4 + 2*X1^2*X3*X5 + 2*X1^2*X3*X7 + X1^2*X4^2 +
    2*X1^2*X4*X5 + 2*X1^2*X4*X7 + X1^2*X5^2 + 2*X1^2*X5*X7 + X1^2*X7^2 + 4*X1*X3^3 + 2*X1*X3^2*X4 + 2*X1*X3^2*X5 + 
    2*X1*X3^2*X7 + 2*X1*X3*X4^2 + 4*X1*X3*X4*X5 + 4*X1*X3*X4*X7 + 2*X1*X3*X5^2 + 4*X1*X3*X5*X7 + 2*X1*X3*X7^2 + 4*X1*X4^3 +
    2*X1*X4^2*X5 + 2*X1*X4^2*X7 + 2*X1*X4*X5^2 + 4*X1*X4*X5*X7 + 2*X1*X4*X7^2 + 4*X1*X5^3 + 2*X1*X5^2*X7 + 2*X1*X5*X7^2 + 
    4*X1*X7^3 + X3^4 + 4*X3^3*X4 + 4*X3^3*X5 + 4*X3^3*X7 + X3^2*X4^2 + 2*X3^2*X4*X5 + 2*X3^2*X4*X7 + X3^2*X5^2 + 
    2*X3^2*X5*X7 + X3^2*X7^2 + 4*X3*X4^3 + 2*X3*X4^2*X5 + 2*X3*X4^2*X7 + 2*X3*X4*X5^2 + 4*X3*X4*X5*X7 + 2*X3*X4*X7^2 + 
    4*X3*X5^3 + 2*X3*X5^2*X7 + 2*X3*X5*X7^2 + 4*X3*X7^3 + X4^4 + 4*X4^3*X5 + 4*X4^3*X7 + X4^2*X5^2 + 2*X4^2*X5*X7 + 
    X4^2*X7^2 + 4*X4*X5^3 + 2*X4*X5^2*X7 + 2*X4*X5*X7^2 + 4*X4*X7^3 + X5^4 + 4*X5^3*X7 + X5^2*X7^2 + 4*X5*X7^3 + X7^4
[/color]

Et la somme $\sum_{\# I = p} S_I^{p-1}$

[color=#000000]
> time &+[S(I)^(p-1) : I in P] ;
0
Time: 0.040
[/color]

Cela fait 0, donc ``c'est bon''.

Par exemple $\ 5, 6, 10, 7$.
Alain

Bonjour,

Dans le pdf, on peut lire que la preuve proposée par Edos, Ginzburg et Ziv est élémentaire et courte.
Or en parcourant le pdf, je n'ai vu que le cas où $n$ est premier.
Auriez-vous cette preuve élémentaire et courte?

Al-Kashi

C'est du pinaillage, mais à la réflexion voici un code un peu plus compact et efficace et qui de plus donne les combinaisons en respectant l'ordre lexicographique de la liste initiale.

def combin(L,k):
    if k==0:
        return [[]]
    if k>len(L):
        return []
    return combin(L[1:],k)+[[L[0]]+M for M in combin(L[1:],k-1)]

def erdos(L):
    n=(len(L)+1)//2
    return [K for K in combin(L,n) if sum(K)%n==0]

>>> erdos([5, 9, 13, 6, 10, 14, 7])
[[5, 6, 10, 7], [5, 6, 14, 7], [5, 10, 14, 7], [9, 6, 10, 7], [9, 6, 14, 7], [9, 10, 14, 7], [13, 6, 10, 7], [13, 6, 14, 7], [13, 10, 14, 7]]

Bonjour,

J'ai bien compris qu'il suffisait de prouver le résultat pour un $n$ premier. j'ai aussi compris la conséquence du Lemme 2.2 pour prouver le résultat souhaité. Néanmoins, quelqu'un pourrait-il préciser le passage :
its not difficult to show that there is a $c\in\Z_p$ so that $B\cap (A+c)$ is a nonempty proper subset of $B$.

N'ayant pas vu encore l'utilisation du fait que $p$ soit supposé premier, je pense que c'est ici que l'on utilise cette hypothèse, non?

Al-Kashi

Bonjour,

En lisant cela Cauchy-Davenport-lemma avec une traduction et une compréhension approximative je ne comprends toujours pas où l'hypothèse $p$ premier est utile?

Al-Kashi

Bonjour,

J'ai aussi séché comme toi Yves de longues heures en cherchant une preuve.
J'ai d'abord prouvé aisément qu'il existe toujours une somme contenant au plus $i$ termes de la séquence $(a_1,a_2,...,a_{2n-1})$ nulle modulo $i$ pour toute valeur $i\leq 2n+1$.
On a donc en particulier une somme nulle modulo $n$ et contenant au plus $n$ termes.
J'ai ensuite essayé de construire une somme contenant exactement $n$ termes mais sans succès.

Al-Kashi