La rappresentazione di Erdos-Suranyi dei naturali

[HiTLeuLeR]

Mostrare che, per ogni $ n \in \mathbb{N} $, esistono $ k \in \mathbb{N} $, $ a_1, a_2, \ldots, a_k \in \mathbb{N}^+ $ ed $ \epsilon_1, \epsilon_2, \ldots, \epsilon_k \in \{\pm 1\} $ tali che $ a_1 < a_2 < \ldots < a_k $ ed $ n = \sum_{i=1}^k \epsilon_i a_i^2 $. Provare inoltre che, in generale, e per infiniti $ n\in\mathbb{N} $, la rappresentazione non è unica.

EDIT: mi sia perdonata la svista - vedi oltre.

[edriv]

Posto così il problema si riduce moltissimo... cioè basta porre (se ho capito bene) tutti gli a_i uguali a 1, e per ottenere n devo sommare e sottrarre tante volte 1, che si può sempre fare in infiniti modi diversi.

Non è che manca qualche condizione per renderlo più interessante?

[Santana]

Mostrare che, per ogni $ n \in \mathbb{N} $, esistono $ k \in \mathbb{N} $, $ a_1, a_2, \ldots, a_k \in \mathbb{N}^+ $ ed $ \epsilon_1, \epsilon_2, \ldots, \epsilon_k \in \{\pm 1\} $ tali che $ a_1 \le a_2 \le \ldots \le a_k $ ed $ n = \sum_{i=1}^k \epsilon_i a_i^2 $. Provare inoltre che, in generale, la rappresentazione non è unica.

Sia $ n,m $ due numeri che si possono rappresentare in tale modo allora anche $ nm $ si può rappresentare così infatti $ \epsilon_1\epsilon_2 \in \{\pm 1\} $ per ogni $ \epsilon_1,\epsilon_2 $ e $ a^2b^2=(ab)^2 $. è sufficiente dimostrare che tale rappresentazione è possibile per ogni numero primo $ p $. Se $ p $ è dispari $ p=(\frac{p+1}{2})^2-(\frac{p-1}{2})^2 $, se $ p=2 $ invece $ p=1^2+1^2 $.

La rappresentazione non è unica, ecco un esempio

$ 65=1^2+8^2=4^2+7^2 $

[HiTLeuLeR]

Posto così il problema si riduce moltissimo... cioè basta porre (se ho capito bene) tutti gli a_i uguali a 1, e per ottenere n devo sommare e sottrarre tante volte 1, che si può sempre fare in infiniti modi diversi.

Non è che manca qualche condizione per renderlo più interessante?

Il fatto è che le disuguaglianze fra gli $ a_i $ sono strette - rimedio subito!

[edriv]

Beh in tal caso $ 2=3^2-2^2+7^2-6^2-4^2 $ (modi più brevi?) e la sua dimostrazione va bene.

[HiTLeuLeR]

Beh in tal caso $ 2=3^2-2^2+7^2-6^2-4^2 $ (modi più brevi?) e la sua dimostrazione va bene.

No, la soluzione di Santana non va più bene, perché nella versione corretta del problema nulla garantisce che il prodotto del tipo indicato sia ancora una rappresentazione dello stesso genere - anzi in generale non è vero certamente! Ad es., 3 = 2^2 - 1, e però 3^2 = 3 * 3 = (2^2 - 1)*(2^2 - 1) = 4^2 - 2^2 - 2^2 + 1. Senonché l'espressione a ultimo membro non fornisce una rappresentazione ammissibile.

[edriv]

Beh allora:
- funziona per ogni numero dispari (allo stesso modo in cui santana l'ha fatto sui primi dispari)
- ho n pari. Allora è 1^2 + (numero dispari precedente come differenza di quadrati)
alternativamente:
- ho n multiplo di 4. Allora lo posso scrivere come somma di due numeri dispari che distano di 6, che a loro volta si scrivono come differenze di quadrati (quattro quadrati tutti distinti, per il modo in cui li ho ottenuti prima).
- ho n congruo a 2 modulo 4. Lo posso scrivere come somma di due numeri dispari che distano di 4, e vale lo stesso ragionamento di prima.

Restano da sistemare solo i numeri pari molto piccoli, che si possono fare anche a mano. (2,4,6,8). 2 già fatto prima, 4 = 2^2, 6=3^2-2^2+1^2, 8=...

[HiTLeuLeR]

Ok. Adesso veniamo al risultato che dà il titolo al topic:

"Mostrare che, per ogni $ n\in\mathbb{Z} $, esistono $ k\in\mathbb{N}^+ $ ed $ \epsilon_1, \epsilon_2, \ldots, \epsilon_k \in \{\pm 1\} $ tali che $ n = \sum_{i=1}^k \epsilon_i i^2 $."

[Simo_the_wolf]

Imbianco la soluzione casomai qualcuno volesse provarci

Induzione: Passo base:

0=-1- 4 + 9 + 16 -25 -36+ 49
1=1
2=-1-4-9+16
3=-1+4
4=1-4-9+16

Passo induttivo n--> n+4

i^2 - (i+1)^2 - (i+2)^2 + (i+3)^2 =4

Quindi aggiungendo alla rappresentazione di n quattro quadrati preceduti rispettivamente da 1, -1, -1,1 avremo la rappresentazione di n+4.

Passo induttivo n-->-n è abbastanza ovvio che se nella rappresentazione di n cambio il segno a tutti gli epsilon ottengo una rappresentazione per -n

[HiTLeuLeR]

Simo_the_Wolf: sì, l'idea è tutta lì. Mancano ciò nonostante la trattazione dello 0 e degli interi negativi.

[Simo_the_wolf]

scusa... credevo fosse solo in $ N^+ $ sorry

[HiTLeuLeR]

Bene. A questo punto - per chiudere il thread in bellezza:

"Provare che esistono infiniti $ n\in\mathbb{Z} $ per i quali la rappresentazione di Erdos-Suranyi non è unica."

[Simo_the_wolf]

Beh so che $ (i-4)^2 - (i-3)^2 - (i-2)^2 + (i-1)^2 -i^2 $ $ + (i+1)^2 + (i+2)^2 - (i+3)^2 = 0 $ quindi nessun numero ha rappresentazione unica

[HiTLeuLeR]

Ok, fine della favola.