Numeri Fattorizzati

[hos-juzamdjinn]

La fattorizzazione in numeri primi di $r+1$ interi positivi ($r>=1$) conivolge in tutto solo $r$ primi. Provare che esiste un sottoinsieme di tali interi il cui prodotto sia un quadrato perfetto.

[Thomas]

Riscriviamo il problema in questo modo: siano $p_1,..,p_r$ i primi.

- dati $r+1$ numeri, si associ ad ognuno di essi una stringa di 0 e 1 lunga r, ove l'ennesimo elemento della stringa rappresenta la parità dell'esponente del primo n_esimo nel numero dato. Si denoti con $k(x)$ il valore della stringa al posto x del numero k_esimo. La tesi equivale a dire che esistono $m_1,...,m_k$ t.c. $m_1(i)+...+m_k(i)$ è uguale a 0 modulo 2 per ogni $i=1...r$;

Supponiamo di avere scelto r numeri senza avere mai trovato il sottoinsieme il cui prodotto è un quadrato perfetto.

Oss: le stringhe possibili sono in ogni caso $2^r-1$ (visto che la stringa fatta di tutti 0 equivale ad avere un quadrato perfetto nell'insieme)... [è un fatto noto];

Quindi se noi riusciamo ad escludere almeno $2^r-1$ stringhe per la scelta del $r+1_(esimo)$ numero abbiamo finito, non essendoci più scelte possibili... Basta provare che:

Claim: le stringhe non più ammissibili si trovano prendendo un sottoinsieme qualsiasi dei primi $r$ elementi e le loro relative stringhe, sommandole (come vettori) è prendendo la stringa "complementare" (ovvero sostitudendo gli 0 con gli 1). Queste stringhe sono $2^r-1$, ovvero sono tutte diverse da loro.

dim: che quelle stringhe non siano ammissibili risulta direttamente da come sono state costruite. Il fatto che siano tutte diverse segue dal fatto che se ce ne fossero due uguali riferite a due insiemi di elementi diverse, anche le stringhe riferite agli stessi insiemi di elementi privati dell'intersezione comune sarebbero uguali, e sommando questi elementi con lestringhe uguali si avrebbe un quadrato perfetto, contro le ipotesi.

Mi rendo conto di essere stato incasinato... dite se ci sono errori et similia...

ciao ciao

[fields]

Si può risolvere il problema anche con l'algebra lineare. I consideri la matrice A di dimensione $k\times (k+1)$ tale che $A(i,j)=0$ se il primo $p_i$ compare con esponente pari nella fattorizzazione di $r_j$, e $A(i,j)=1$ altrimenti. Questa è una matrice a coefficienti in un campo, il campo degli interi modulo 2. Poniamo ora $A=[F A_{k+1}]$, in cui $F$ è la matrice composta dalle prime $k$ colonne di $A$ e $A_{k+1}$ è la $(k+1)$-esima colonna di $A$. Se le colonne di $F$ sono linearmente dipendenti, allora esiste un vettore $x'!=0$ tale che $Fx'=0$, il che prova che esistono interi fra $r_1,...,r_k$ il cui prodotto è un quadrato perfetto. Se invece le colonne di $F$ sono linearmente indipendenti, allora $F$ è non singolare, dunque esiste un vettore $x'$ tale che $Fx'=A_{k+1}$ e dunque il vettore $[x' 1]$ è tale che $A[x' 1]^T=Fx'+A_{k+1}=A_{k+1}+A_{k+1}=0$, il che prova che esistono interi fra $r_1,...,r_{k+1}$ il cui prodotto è un quadrato perfetto.

[Thomas]

Bella fields ... mi piace il tuo utilizzo delle matrici in Z[2] (si chiama così quel campo, o no? vabbè ci siamo capiti... non studio mica algebra ) ...
guarderò sugli appunti di geometria se quanto hai usato funzia anche per i campi di caratteristica due, ma credo proprio di si... bello!!

[fields]

Bella fields ... mi piace il tuo utilizzo delle matrici in Z[2] (si chiama così quel campo, o no? vabbè ci siamo capiti... non studio mica algebra ) ...
guarderò sugli appunti di geometria se quanto hai usato funzia anche per i campi di caratteristica due, ma credo proprio di si... bello!!

Grazie, in effetti la nostra soluzione è simile, io ho solo visto la struttura soggiacente.