Rivisitazione $(W^2 + X^2 + Y^2 + Z^2) = (A^2 + B^2)$
Questa query presenta una domanda ristretta che è stata affrontata da alcune delle risposte alla seguente query: Può una somma di$n$ i quadrati devono essere espressi come la somma di $n/2$ piazze?
Non sono sicuro che la domanda che sto chiedendo specificamente fosse intesa dall'OP della query di riferimento sopra. Comunque...
Dati due numeri interi positivi fissi$A$ e $B$,
trova tutte le soluzioni di numeri interi positivi per
$(W^2 + X^2 + Y^2 + Z^2) = (A^2 + B^2)$
Quello che cerco è l'analisi + un elegante algoritmo da applicare al caso generale, al contrario di casi specifici [es. $(A^2 + B^2)$è inferiore a un certo numero]. Di seguito è mostrato l'unico algoritmo (brutto) che posso inventare. Mi sembra che questo algoritmo richieda il supporto del computer.
Questo algoritmo può essere migliorato? Particolarmente pertinente, è possibile utilizzare un'analisi sufficiente per risolvere il problema generale senza il supporto del computer.
In alternativa, supponi che non esista un algoritmo elegante. In tal caso è possibile:
(1) identificare le condizioni necessarie affinché esista una soluzione
(2) identificare condizioni sufficienti affinché esista una soluzione
(3) sia (1) che (2)
$\underline{\textbf{my ugly algorithm}}$
Permettere $C = (A^2 + B^2)$.
Permettere$S = \{(i,j) : i,j \in \mathbb{Z^+}, i \leq j, (i + j) = C\}.$
Passa attraverso ogni elemento di $S$ individualmente, individuando tutte le soluzioni $(W,X,Y,Z)$per ogni elemento. Per soluzione , intendo uno dei tre seguenti:
(un) $W^2 = i$ e $(X^2 + Y^2 + Z^2) = j.$
(b) $W^2 = j$ e $(X^2 + Y^2 + Z^2) = i.$
(c) $(W^2 + X^2) = i$ e $(Y^2 + Z^2) = j.$
Quando si ispeziona un singolo elemento da $S$, segui l'algoritmo nella sezione "Ispeziona singolo elemento" di seguito. Questa query si chiude con una sezione "Analisi attorno a terzine pitagoriche". Forse il meglio che può essere offerto è aggiungere altri casi speciali simili alla sezione di chiusura di questa query.
Ispeziona il singolo elemento
Se nessuno dei due $i$ né $j$risulta essere un quadrato perfetto, quindi le soluzioni di tipo (a) e (b) vengono immediatamente eliminate. Assumi quello di$i$ e $j$è un quadrato perfetto. Non conosco analisi che considerino la questione se (ad esempio) la Diofhantina$(X^2 + Y^2 + Z^2) = j$ (con $j$un numero fisso) è risolvibile e, in tal caso, come identificare tutte le possibili soluzioni. Supponendo che non esista tale analisi, non vedo alcun modo per attaccare la Diofhantina$(X^2 + Y^2 + Z^2) = j$ diverso da una ricerca del computer.
Il resto di questa sezione presume che indipendentemente dal fatto che $i$ o $j$è un quadrato perfetto, si cercheranno soluzioni di tipo (c). Ho visto analisi (teoria dei numeri elementari) sulla generazione di tutte le possibili terzine pitagoriche, ma non è chiaro come questa analisi possa essere utilizzata contro (ad esempio) la Diofhantina
$(W^2 + X^2) = i$,
dove$i$ è un numero intero positivo fisso che può essere o meno un quadrato perfetto.
Come nella ricerca di soluzioni di tipo (a) e (b), se nessuna analisi può essere applicata alle Diofantine coinvolte nel tipo (c), allora (di nuovo) penso che una ricerca al computer sia inevitabile.
Analisi intorno a terzine pitagoriche
Supponiamo (ad esempio) che quando si considera un elemento specifico di $S$, quello $i$ è un quadrato perfetto (es $i = k^2$).
Quindi si potrebbe invocare l'analisi intorno alla generazione di terzine pitagoriche. Cioè, in questo caso, qualsiasi soluzione di tipo (c) che coinvolge questo particolare elemento da$S$ deve coinvolgere una terzina pitagorica:
$W^2 + X^2 = k^2.$
Ciò significa che se si potesse stabilire che non è possibile alcuna tripletta pitagorica di questo tipo, questo implica $k^2$, allora hai stabilito che nessuna soluzione di tipo (c) è possibile per questo particolare elemento di S. Inoltre, se potessi enumerare tutte le possibili soluzioni per
$W^2 + X^2 = k^2$,
quindi qualsiasi soluzione di tipo (c) per questo particolare elemento da$S$ deve coinvolgere una di queste soluzioni di triplette pitagoriche.
Tuttavia, anche qui, ammesso che $j$ non è un quadrato perfetto che ti lascerebbe comunque risolvere $Y^2 + Z^2 = j.$
Addendum
Mentre esploravo il collegamento "Teorema dei quattro quadrati di Lagrange" nella risposta di John Omielan, io (penso di aver) scoperto un modo per raffinare moderatamente l'algoritmo, basato sul teorema della somma di due quadrati . In alternativa, forse sto interpretando male il teorema.
Supponiamo, per un elemento specifico $(i,j) \in S,$ nessuno dei due $i$ né $j$è un quadrato perfetto. Quindi le uniche soluzioni possibili che utilizzano questo elemento saranno di tipo (c). Se uno dei due$i$ o $j$ fallisce i criteri del teorema della "Somma di due quadrati", quindi questo specifico elemento di S non può essere utilizzato per generare una soluzione.
In alternativa, se $i$ e $j$ entrambi soddisfano i criteri del teorema della "Somma di due quadrati", quindi almeno una soluzione di tipo (c) (e forse più di una) sarà possibile con questo particolare elemento di $S$.
Addendum-2
Anche il "Teorema della somma di due quadrati" collegato nell'addendum influisce (indirettamente) sulla discussione nella sezione "Analisi intorno alle terzine pitagoriche". Supponiamo che per un elemento specifico$(i,j) \in S,$ quello $i$ è un quadrato perfetto (es $i = k^2$).
Supponi inoltre che (per il momento) tu stia esplorando solo soluzioni (possibili) di tipo (c) per questo elemento [in opposizione alle soluzioni di tipo (a)].
Supponi inoltre di aver usato "analisi pitagorica in terzine" per determinare che esiste almeno una soluzione $W^2 + X^2 = k^2.$
Come indicato nella sezione "Analisi intorno a terzine pitagoriche", questo lascia ancora il file $Y^2 + Z^2 = j$ Diophantine da risolvere.
Se $j$ sembra anche essere un quadrato perfetto (es $j = l^2$), quindi "analisi delle terzine pitagoriche" può (anche) essere usata per attaccare il file $Y^2 + Z^2 = l^2$ Diofhantina.
In alternativa, se $j$ non è un quadrato perfetto, quindi il "Teorema della somma di due quadrati" può essere utilizzato per attaccare il $Y^2 + Z^2 = j$ Diofhantina.
Addendum-3
Sebbene l'algebra nelle mie sezioni Addendum e Addendum-2 sembri valida, alla luce del commento pubblicato da Steven Stadnicki in seguito alla risposta di John Omielan, metto in dubbio l'utilità di queste due sezioni. Dati interi fissi$A$ e $B$che sono entrambi grandi , nulla nelle sezioni Addendum o Addendum-2 consente il problema specifico che coinvolge i valori specifici per$A$ e $B$ per essere attaccato in modo completo senza supporto del computer.
Di conseguenza, per valutare l'utilità delle sezioni Addendum e / o Addendum-2, si dovrebbe prima esaminare l'efficienza informatica degli algoritmi a cui fa riferimento Steven Stadnicki (che non capisco).
Quindi, si dovrebbe considerare il costo dell'identificazione di ogni elemento $(i,j) \in S,$e (forse) applicando il teorema della "Somma di due quadrati" a questo elemento. Ciò richiederebbe quello per ogni elemento$(i,j)$ dovresti (normalmente) calcolare le prime fattorizzazioni di entrambi $i$ e $j$. Tra le altre considerazioni, ciò significa che è necessaria una tabella di numeri primi per$\{1, 2, 3, 4, \cdots, [A^2 + B^2]\}.$
In una certa misura, il costo di costruzione della tabella dei numeri primi potrebbe essere "ammortizzato", se si risolvesse più di un problema alla volta. Ad ogni modo, il mio ( cieco ) istinto è che la mia analisi Addendum e Addenum-2 potrebbe non aver ottenuto nulla.
Si noti che anche se io metto in discussione l'utilità delle analisi che ho aggiunto nella mia Addendum e Addendum-2 sezioni, io non allo stesso modo in discussione l'utilità delle analisi fornita dalla risposta di John Omielan. Questo perché la sua analisi (ad esempio la determinazione del mod residuo 16 di un numero) mi sembra non intensiva al computer .
Infine, devo confessare che questa sezione (Addendum-3) è motivata da meta-barare. Il commento di Steven Stadnicki suggerisce che i "conigli" sono improbabili. Devo credere che qualcuno con una comprensione di livello universitario della teoria dei numeri (io), che si è appena imbattuto nel teorema della "Somma di due quadrati", abbia improvvisamente reinventato la ruota?
Addendum-4 Risposta al caso A nella risposta di Arnold.
Il caso A in questa risposta sembra far sorgere alcune domande:
(1)
Dati numeri interi positivi fissi$(p,q)$ con $p^2 + q^2 = r,$
può qualsiasi valore intero diverso da zero per$(a,b,c,d)$essere trovato
così$a^2 + b^2 + c^2 + d^2 = r$dove contemporaneamente il modello del caso A non si applica.
Le situazioni in cui il modello del caso A non si applica sarebbero che:
(1a)
Gli elementi in$\{a,b,c,d\}$non può essere accoppiato in modo che (ad esempio)
$(|a|+|b|) = p$ e $(|c|+|d|) = q.$
(1b)
Gli elementi in$\{a,b,c,d\}$non può essere accoppiato in modo che (ad esempio)
$(ab + cd) = 0.$
(2)
Ignorando le difficoltà muoversi (1) direttamente sopra, può l'analisi in caso A essere applicato a grandi valori di$(p,q)$ manualmente (cioè dove non viene utilizzato il supporto del computer)?
Ciò significa che (ad esempio) sebbene tu possa ( discutibilmente ) calcolare il residuo di$p$ o $q$ modulo un numero intero positivo, non è stato possibile calcolare le fattorizzazioni prime di $p$ o $q.~~$ Probabilmente , tu (anche) non avresti accesso a un elenco di numeri primi.
Ciò significa che con $(p,q)$ risolto , devi identificare analiticamente tutti i set soddisfacenti$[a,b,c,d]$ di numeri interi diversi da zero tali che $(|a|+|b|) = p, ~ (|c|+|d|) = q, ~ \text{and} ~ (ab + cd) = 0.$
(3)
Ignorando le difficoltà di (1) di cui sopra, e supponendo che l'approccio adottato nel procedimento A viene utilizzato [come descritto in (2) direttamente sopra], e in seguito assumendo che questo approccio non richiede supporto informatico, allora la (forse senza risposta ) la domanda è:
Come si confronta l'efficienza informatica del caso A con l'efficienza informatica degli algoritmi a cui fa riferimento Steven Stadnicki nel suo commento alla risposta di John Omielan?
Risposte
Non conosco nessun algoritmo elegante per trovare tutte le soluzioni nel caso generale, o alcun modo particolare per migliorare il tuo algoritmo. Tuttavia, nota gli stati del teorema dei quattro quadrati di Lagrange
Il teorema dei quattro quadrati di Lagrange , noto anche come congettura di Bachet , afferma che ogni numero naturale può essere rappresentato come la somma di quattro quadrati interi.
Tuttavia, questo include anche i casi in cui si trovano uno o più di questi quadrati $0$. Dal momento che dici tutto$4$i quadrati devono essere positivi, si noti che la sezione Unicità afferma che gli unici numeri interi positivi che non possono essere espressi come somma di quattro quadrati diversi da zero sono
... gli otto numeri dispari $1, 3, 5, 9, 11, 17, 29, 41$ e tutti i numeri del modulo $2(4^{k}),6(4^{k})$ o $14(4^{k})$.
Quindi, finché $A^2 + B^2$ non è uno di questi numeri (ad es. $A = 1$ e $B = 2$ non ha soluzione da allora $1 + 4 = 5$, e anche $A = B = 2^{n}$ per ogni $n \ge 0$non hanno neanche una soluzione), esiste almeno una soluzione. Ciò fornisce le condizioni necessarie e sufficienti per le quali hai chiesto una soluzione.
Aggiornamento: nel caso in cui non fossi già a conoscenza di questi, ci sono diversi modi abbastanza semplici ed efficienti per ridurre il numero di controlli che il tuo algoritmo, come indicato nella domanda, deve eseguire. Ad esempio, nota che tutti i quadrati perfetti sono congruenti a un elemento di$\{0, 1, 4, 9\}$ modulo $16$. Puoi usarlo per controllare$i$ nel caso (a) e $j$ nel tuo caso $b$.
Inoltre, la somma di $2$ i quadrati possono essere congruenti solo a un elemento di $\{0, 1, 2, 4, 5, 8, 9, 10, 13\}$ modulo $16$, che puoi utilizzare per controllare $i$ e $j$ nel tuo caso (c).
Infine, come mostrato nella Tabella 5 del libro "Modern Elementary Theory of Numbers" di Dickson , l'espressione$ax^2 + by^2 + cz^2$, dove $a = b = c = 1$, non può essere uguale a nessun numero intero positivo del modulo $A = 4^{k}(8n + 7)$. Puoi usarlo per controllare$j$ nel tuo caso (a) e $i$ nel tuo caso (b).
Possiamo sempre trovare $4$ piazze uguali $2$ quadrati se tutti i termini fanno parte di terne pitagoriche cioè dove $A_1^2+B_1^2+A_2^2+B_2^2=C_1^2+C_2^2.$
Cominciamo con la formula di Euclide $\quad A=m^2-k^2\quad B=2mk\quad C=m^2+k^2\quad$ e trova triple, se esistono, per due qualsiasi $C$-valori. Qualsiasi valore di C che restituisce un numero intero entro i limiti di$m$ fornisce il $m,k$ valori necessari per generare una tripla pitagorica.
$$C=m^2+k^2\implies k=\sqrt{C-m^2}\qquad\text{for}\qquad \bigg\lfloor\frac{ 1+\sqrt{2C-1}}{2}\bigg\rfloor \le m \le \lfloor\sqrt{C-1}\rfloor$$
Il limite inferiore garantisce $m>k$ e il limite superiore garantisce $k\in\mathbb{N}$. Per esempio:
$$C=65\implies \bigg\lfloor\frac{ 1+\sqrt{130-1}}{2}\bigg\rfloor=6 \le m \le \lfloor\sqrt{65-1}\rfloor=8\quad\land \quad m\in\{7,8\}\Rightarrow k\in\{4,1\}\\$$ $$F(7,4)=(33,56,65)\qquad \qquad F(8,1)=(63,16,65) $$ Questo esempio fornisce due coppie di file $A^2,B^2$ che si sommano a $65^2$ ma dobbiamo scegliere solo una delle coppie a meno che non vogliamo che la somma sia $2C^2$. Ora, usando la stessa tecnica per un altro noto$C$-valore:
$$C=85\implies \bigg\lfloor\frac{ 1+\sqrt{170-1}}{2}\bigg\rfloor=7 \le m \le \lfloor\sqrt{85-1}\rfloor=9\quad\land \quad m\in\{7,9\}\Rightarrow k\in\{6,2\}\\$$ $$F(7,6)=(13,84,85)\qquad \qquad F(9,2)=(77,36,85)$$
Ora abbiamo due serie di file $A^2,B^2$ (scegline uno) che si sommano a $65^2$, allo stesso modo per $85^2$e ci sono quattro modi per combinarli. Alcuni$C$-values avrà una o più coppie per $A,B$ ma se nessun valore di $m$ restituisce un numero intero $k$, quindi non esiste una tripla per questo $C$-valore.
Abbiamo l'identità:
Caso A
$(a,b,c,d)^2=(p,q)^2$
Dove, $(p,q)=[(a+b),(c+d)]$
E la condizione è: $(ab+cd=0)$
Per, $(a,b,c,d)=(9,7,-21,3)$ noi abbiamo:
$(p,q)=(16,18)$
Caso B:
$(a,b,c,d,e,f)^2=(p,q,r)^2$
Dove, $(p,q)=[(a+b),(c+d),(e+f)]$
E la condizione è: $(ab+cd+ef=0)$
Per, $(a,b,c,d)=(3,2,4,1,-10,1)$ noi abbiamo:
$(p,q,r)=(5,5,9)$
Caso C:
$(a,b,c,d,e,f,g,h)^2=(p,q,r,s)^2$
Dove, $(p,q)=[(a+b),(c+d),(e+f),(g+h)]$
E la condizione è: $(ab+cd+ef+gh=0)$
Per, $(a,b,c,d)=(15,13,12,9,8,4,-67,5)$ noi abbiamo:
$(p,q,r,s)=(28,21,12,62)$
Allo stesso modo si può applicare il metodo per $(2n)$ piazze
su LHS e ottieni $(n)$ quadrati sulla destra per ogni 'n' &
valori adeguati di $(a,b,c,d,-----)$.
Penso che quello che potresti perdere sia il divario di efficienza. La dimensione del tuo set$S$ è lineare in $N$, dove $N$è il numero espresso simultaneamente come somma di due e somma di quattro quadrati. Ciò significa che qualsiasi algoritmo che si basa sull'iterazione attraverso i membri di$S$ ci vorrà del tempo nella migliore delle ipotesi lineare $N$ e potrebbe richiedere più tempo a seconda di quante operazioni devono essere eseguite per ogni elemento.
Questo potrebbe non sembrare male in superficie, ma un cambiamento di prospettiva potrebbe aiutare a capire perché è "lento". Poiché un numero può essere scritto in modo "efficiente" utilizzando la notazione standard in base 2 o in base 10, per gli algoritmi di teoria dei numeri ciò che viene solitamente considerato "efficiente" si basa sul logaritmo dei numeri di input, o equivalentemente sulla dimensione (' in ricordo ') di loro. Non puoi contare 31415926senza impiegare molto tempo, ma sai come aggiungerlo 27182818in poche operazioni. Inoltre, utilizzando solo pochi passaggi in più potresti moltiplicare i due numeri insieme. In particolare, l'aggiunta di$n$-numeri di bit, ovvero numeri di dimensione $\leq N=2^n$ - può essere fatto in $O(n)$tempo. Questo è$O(\log N)$quando rappresentato in termini di numeri effettivi manipolati. Allo stesso modo, la moltiplicazione ingenua può essere eseguita in$O(n^2)$tempo, e si può dimostrare che la divisione può essere eseguita in tempi comparabili. Uno dei risultati fondamentalmente importanti in Informatica negli ultimi decenni è stato il risultato che i test di primalità possono essere eseguiti in un polinomio temporale della lunghezza del numero testato, vale a dire in$O(n^k)$ per qualche esponente $k$.
Pensato in questi termini, l'algoritmo per risolvere il problema dei quattro quadrati menzionato nel mio commento richiede tempo $O(n^2)$(forse fino a fattori molto più piccoli, sospetto); il tuo algoritmo, al contrario, richiede più o meno tempo$2^n$; è esponenzialmente peggiore dell'algoritmo probabilistico.
Spero che questo aiuti a dare un senso all'idea!