$n$ numeri su $2n-1$ con somma divisibile per $n$

[dario2994]

Ecco l'hint... è più leggero e non porta a concludere, ma è un inizio:

Testo nascosto:

Provate a scrivere il problema in forma "polinomiale" mod n... insomma riconducetelo a trovare una soluzione ad un equazione o più equazioni mod n

[paga92aren]

Ci ho provato senza molto successo, l'idea mia era per induzione. Da $n$ a $n+1$ non portava a nessuna risultato (cambia il modulo) quindi ho pensato di usare l'induzione estesa sui primi di $n$, ma non vedendo nessun vantaggio limitando $n$ a un primo ho desistito. Visto il primo hint di dario ho provato su questa strada:

Tesi: se vale per $a$ e $b$ allora vale per $n=ab$ con $(a,b)=1$.
Ho $2ab-1$ elementi, ne prendo $2a-1$ a caso e tra questi posso sceglierne $a$ tali che la somma sia divisibile per $a$ ($a|S_1$) (i $a-1$ elementi di avanzo li rimetto insieme agli altri).
Rimangono $2ab-1-a$ elementi e ripeto il procedimento: prendo $2a-1$ elementi ne scelgo $a$ che formano $S_2$ tali che $a|S_2$. Ripeto il procedimento $2b-1$ volte, al penultimo passaggio ho $2a-1$ elementi quindi posso formare $S_{2b-1}$ con $a|S_{2b-1}$ e avanzano $a-1$ elementi.
Adesso ho $2b-1$ numeri interi ($S_i$) quindi posso sceglierne $b$ tali che la somma ($T$) sia divisibile per $b$.
$T$ è composto da elementi divisibili per $a$ quindi è divisibile per $a$, inoltre è composto da $b$ somme di $a$ elementi quindi è una somma di $ab=n$ elementi ed è divisibile sia per $a$ sia per $b$ allora è divisibile per $n$.

Ora manca la dimostrazione per i primi e le loro potenze.

[dario2994]

Ora manca la dimostrazione per i primi e le loro potenze.

In realtà mancano solo i primi

[paga92aren]

Per come lo scritto io non funziona, ma con qualche modifica tutto torna:
Prendo $S'_i=\frac{S_i}{a}$, $S'$ è sempre intero quindi posso scegliere $b$ elementi $S'_i$ tra i $2b-1$ tali che $b|T'$ (dove $T'$ è la somma degli $S'$).
Allora $T=aT'$ e $T$ è composto da $ab$ elementi iniziali e $ab|aT'=T$. Così sistemo le potenze di primi.

[Sonner]

Vista l'ora sarò lapidario

Uso questo teorema (che in teoria dovrei ancora dimostrare ma vabbè ):
Dato un sistema di n equazioni in k incognite modulo un primo, se il numero di incognite è maggiore del grado del sistema (definito come la somma dei gradi dei polinomi che costituiscono le n equazioni) allora il numero di soluzioni (di k-uple che soddisfano insomma) è multiplo di p.

Detta in breve, basta considerare questo sistema:
$ x_1^{p-1}+\dots +x_{2p-1}^{p-1}\equiv 0 \pmod p $
$ a_1x_1^{p-1}+\dots +a_{2p-1}x_{2p-1}^{p-1}\equiv 0 \pmod p $
Dove gli $ a_i $ sono i valori che scegliamo inizialmente. A questo punto vedo subito una soluzione banale (tutti gli $ x_i\equiv 0 \pmod p $) e inoltre la somma dei gradi è 2p-2 che è minore del numero di variabili 2p-1, quindi per il teorema di sopra so che ce n'è almeno un'altra. Se c'è una soluzione con almeno una delle variabili diversa da 0, allora dalla prima equazione trovo che ce ne sono esattamente p diverse da 0 e quindi dopo l'elevamento a potenza uguali ad 1, mentre le altre p-1 sono nulle (per Fermat infatti $ b^{p-1} $ fa 0 o 1 modulo p). Risostituendo i valori degli $ x_i $ trovati nell'equazione di sotto mi restano esattamente p termini che per ipotesi sono divisibili per p.

[paga92aren]

Uso questo teorema (che in teoria dovrei ancora dimostrare ma vabbè ):
Dato un sistema di n equazioni in k incognite modulo un primo, se il numero di incognite è minore del grado del sistema (definito come la somma dei gradi dei polinomi che costituiscono le n equazioni) allora il numero di soluzioni (di k-uple che soddisfano insomma) è multiplo di p.

Mi sembra sbagliato. Non tutti i sistemi di quel tipo anno soluzione, puoi avere cose del tipo quadrato uguale non residuo.

[dario2994]

Uso questo teorema (che in teoria dovrei ancora dimostrare ma vabbè ):
Dato un sistema di n equazioni in k incognite modulo un primo, se il numero di incognite è minore del grado del sistema (definito come la somma dei gradi dei polinomi che costituiscono le n equazioni) allora il numero di soluzioni (di k-uple che soddisfano insomma) è multiplo di p.

Mi sembra sbagliato. Non tutti i sistemi di quel tipo anno soluzione, puoi avere cose del tipo quadrato uguale non residuo.

E infatti 0 è divisibile per $p$. Ma in ogni caso la formulazione di Sonner è segata, il minore in realtà è un maggiore.
Comunque la soluzione di Sonner è giusta... ma resta da dimostrare il teorema, che si chiama "di Chevalley-Warning" (per gli amici solo Chevalley):

Teorema di Chevalley-Warning
Dato il sistema di $n$ equazioni e $k$ incognite modulo un primo $p$:
$\forall 1\le i \le n :\ P_i(x_1,x_2,\dots , x_k)\equiv 0 \pmod p$
Sia $d_i$ il grado totale di $P_i$ (ad esempio il grado di $x^2y^3$ è 5).
Se vale $\sum_{i=1}^nd_i<k$ allora il numero di soluzioni (ovviamente soluzioni in $\mathbb{F}_p$ quindi $0\le x_i<p$) è divisibile per $p$.

Come lo dimostro? Bon, anche per questo piazzo un hint nascosto, sperando che qualcuno ci provi:

Testo nascosto:

Riuscite a trovare un polinomio $P$ tale che se ci butto dentro una $k$-upla che è soluzione del sistema allora sputa fuori 1, altrimenti 0? (ovviamente sempre modulo $p$ )

[Sonner]

Ma in ogni caso la formulazione di Sonner è segata, il minore in realtà è un maggiore.

Ho corretto scusate

Dimostro l'hint (dimostrazione più passo passo di così... ).
Ecco il polinomio (sfruttando l'idea del problema originario nel caso n primo).
$ \displaystyle \prod_i (1-P_i(x_1,\dots ,x_k)^{p-1}) $
Consideriamolo modulo p. Per Fermat, questo fa 1 se e solo se la k-upla è soluzione di ogni $ P_i $, altimenti c'è almeno un fattore 0 e il prodotto fa 0.

Da qui provo a concludere.

Uso questo lemma: $ \sum_{i=1}^{p-1} i^m \equiv 0 \pmod p $ se $ p-1 \nmid m $, -1 altrimenti.
Dimostrazione.
a) Caso $ p-1 \nmid m $: sia g un generatore modulo p. Allora per ogni $ 0<i<p-1 $ posso scrivere $ i=g^{\alpha_i} $ dove gli $ \alpha_i $ sono una permutazione dei numeri da 1 a p-1. Ma allora $ \displaystyle \sum_{i=1}^{p-1} i^mk \equiv \sum_{i=1}^{p-1}g^{m\alpha_i}\equiv \sum_{i=0}^{p-2}g^{m\alpha_i}\equiv \frac{g^{m(p-1)}-1}{g^m-1}\equiv 0 \pmod p $ perchè il numeratore ha un fattore p mentre per ipotesi $ g^m\neq 1 \pmod p $ (m non divide p-1).
b) Caso $ p-1 \mid m $ (non mi serve ma già che ci sono... ): posso scrivere $ m=q(p-1) $ per q intero positivo, ma allora per ogni i vale $ i^m=(i^q)^{p-1}\equiv 1 \pmod p $ e quindi $ \sum_{i=1}^{p-1} i^m \equiv \sum_{i=1}^{p-1} 1 \equiv -1 \pmod p $.

Corollario è che la somma di tutti valori che un polinomio in k variabili di grado minore di k(p-1) assume (modulo p) se valutato in ognuna delle $ p^k $ k-uple è divisibile per p.
Consideriamo infatti un monomio del tipo $ x_1^{\alpha_1}\cdot \dots \cdot x_k^{\alpha_k} $: è facile vedere come la somma di tutti i valori che esso prende è $ \sum_{i=0}^{p-1} i^{\alpha_1}\cdot\sum_{i=0}^{p-1} i^{\alpha_2}\cdot\dots\cdot\sum_{i=0}^{p-1} i^{\alpha_k} $ che è divisibile per p siccome lo è almeno una delle sommatorie (*). Infatti, essendo il grado minore di k(p-1), in ogni monomio c'è almeno una variabile elevata ad un esponente minore di p-1, e in cui posso quindi applicare il punto a) del lemma di sopra.

Torniamo al polinomio dell'hint. L'idea è buttarci dentro ognuna delle $ p^k $ possibili k-uple e sommare tutti i valori (ovviamente in $ {0,1} $) che escono. In questo modo il numero di soluzioni del sistema corrispondono al numero di 1 che sommiamo. La tesi quindi diventa equivalente a "la somma dei valori del polinomione valutato in ogni k-upla è multipla di p". Questo è vero perchè, essendo il grado della bestia minore di k(p-1) per ipotesi, posso applicare il lemma di sopra. Fine

(*) Qui non saprei bene come esplicitare il conto. Si può però ragionare così: da una parte il numero di addendi una volta svolta quella sommatoria è $ p^k $ perchè ognuna delle k sommatorie contiene p numeri; d'altro canto i numeri delle sommatorie sono tutti distinti quindi non posso ottenere mai la stessa k-upla per 2 volte, quindi lì dentro ci sono proprio tutte e sole le k-uple contenenti numeri da 0 a p-1.

[dario2994]

Tutto giusto, mai complimenz (va detto che c'è stato qualche hint aggiuntivo )

Questo è vero perchè, essendo il grado della bestia minore di k(p-1) per ipotesi

Lo chiarisco (assumo $d_i\ge 1$... il caso $d_i=0$ è banale):
$\displaystyle\deg(\prod_{i=1}^n1-P_i^{p-1})= \sum_{i=1}^n\deg(1-P_i^{p-1})=\sum_{i=1}^nd_i\cdot (p-1)<k(p-1)$

[Sonner]

(va detto che c'è stato qualche hint aggiuntivo )

Già, rimaniamo sul qualche